blob: 5150ca40fb42622ad914c1240c79007d82dc5a82 [file] [log] [blame]
Serge Pavlovccdac232017-12-22 15:22:45 +00001//=== unittests/CodeGen/IRMatchers.h - Match on the LLVM IR -----*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9/// \file
10/// This file provides a simple mechanism for performing search operations over
11/// IR including metadata and types. It allows writing complex search patterns
12/// using understandable syntax. For instance, the code:
13///
14/// \code
15/// const BasicBlock *BB = ...
16/// const Instruction *I = match(BB,
17/// MInstruction(Instruction::Store,
18/// MConstInt(4, 8),
19/// MMTuple(
20/// MMTuple(
21/// MMString("omnipotent char"),
22/// MMTuple(
23/// MMString("Simple C/C++ TBAA")),
24/// MConstInt(0, 64)),
25/// MSameAs(0),
26/// MConstInt(0))));
27/// \endcode
28///
29/// searches the basic block BB for the 'store' instruction, first argument of
30/// which is 'i8 4', and the attached metadata has an item described by the
31/// given tree.
32//===----------------------------------------------------------------------===//
33
34#ifndef CLANG_UNITTESTS_CODEGEN_IRMATCHERS_H
35#define CLANG_UNITTESTS_CODEGEN_IRMATCHERS_H
36
37#include "llvm/ADT/PointerUnion.h"
38#include "llvm/IR/BasicBlock.h"
39#include "llvm/IR/Constants.h"
40#include "llvm/IR/Instruction.h"
41#include "llvm/IR/Metadata.h"
42#include "llvm/IR/Value.h"
43
44namespace llvm {
45
46/// Keeps information about pending match queries.
47///
48/// This class stores state of all unfinished match actions. It allows to
49/// use queries like "this operand is the same as n-th operand", which are
50/// hard to implement otherwise.
51///
52class MatcherContext {
53public:
54
55 /// Describes pending match query.
56 ///
57 /// The query is represented by the current entity being investigated (type,
58 /// value or metadata). If the entity is a member of a list (like arguments),
59 /// the query also keeps the entity number in that list.
60 ///
61 class Query {
62 PointerUnion3<const Value *, const Metadata *, const Type *> Entity;
63 unsigned OperandNo;
64
65 public:
66 Query(const Value *V, unsigned N) : Entity(V), OperandNo(N) {}
67 Query(const Metadata *M, unsigned N) : Entity(M), OperandNo(N) {}
68 Query(const Type *T, unsigned N) : Entity(T), OperandNo(N) {}
69
70 template<typename T>
71 const T *get() const {
72 return Entity.dyn_cast<const T *>();
73 }
74
75 unsigned getOperandNo() const { return OperandNo; }
76 };
77
78 template<typename T>
79 void push(const T *V, unsigned N = ~0) {
80 MatchStack.push_back(Query(V, N));
81 }
82
83 void pop() { MatchStack.pop_back(); }
84
85 template<typename T>
86 const T *top() const { return MatchStack.back().get<T>(); }
87
88 size_t size() const { return MatchStack.size(); }
89
90 unsigned getOperandNo() const { return MatchStack.back().getOperandNo(); }
91
92 /// Returns match query at the given offset from the top of queries.
93 ///
94 /// Offset 0 corresponds to the topmost query.
95 ///
96 const Query &getQuery(unsigned Offset) const {
97 assert(MatchStack.size() > Offset);
98 return MatchStack[MatchStack.size() - 1 - Offset];
99 }
100
101private:
102 SmallVector<Query, 8> MatchStack;
103};
104
105
106/// Base of all matcher classes.
107///
108class Matcher {
109public:
110 virtual ~Matcher() {}
111
112 /// Returns true if the entity on the top of the specified context satisfies
113 /// the matcher condition.
114 ///
115 virtual bool match(MatcherContext &MC) = 0;
116};
117
118
119/// Base class of matchers that test particular entity.
120///
121template<typename T>
122class EntityMatcher : public Matcher {
123public:
124 bool match(MatcherContext &MC) override {
125 if (auto V = MC.top<T>())
126 return matchEntity(*V, MC);
127 return false;
128 }
129 virtual bool matchEntity(const T &M, MatcherContext &C) = 0;
130};
131
132
133/// Matcher that matches any entity of the specified kind.
134///
135template<typename T>
136class AnyMatcher : public EntityMatcher<T> {
137public:
138 bool matchEntity(const T &M, MatcherContext &C) override { return true; }
139};
140
141
142/// Matcher that tests if the current entity satisfies the specified
143/// condition.
144///
145template<typename T>
146class CondMatcher : public EntityMatcher<T> {
147 std::function<bool(const T &)> Condition;
148public:
149 CondMatcher(std::function<bool(const T &)> C) : Condition(C) {}
150 bool matchEntity(const T &V, MatcherContext &C) override {
151 return Condition(V);
152 }
153};
154
155
156/// Matcher that save pointer to the entity that satisfies condition of the
157// specified matcher.
158///
159template<typename T>
160class SavingMatcher : public EntityMatcher<T> {
161 const T *&Var;
162 std::shared_ptr<Matcher> Next;
163public:
164 SavingMatcher(const T *&V, std::shared_ptr<Matcher> N) : Var(V), Next(N) {}
165 bool matchEntity(const T &V, MatcherContext &C) override {
166 bool Result = Next->match(C);
167 if (Result)
168 Var = &V;
169 return Result;
170 }
171};
172
173
174/// Matcher that checks that the entity is identical to another entity in the
175/// same container.
176///
177class SameAsMatcher : public Matcher {
178 unsigned OpNo;
179public:
180 SameAsMatcher(unsigned N) : OpNo(N) {}
181 bool match(MatcherContext &C) override {
182 if (C.getOperandNo() != ~0U) {
183 // Handle all known containers here.
184 const MatcherContext::Query &StackRec = C.getQuery(1);
185 if (const Metadata *MR = StackRec.get<Metadata>()) {
186 if (const auto *MT = dyn_cast<MDTuple>(MR)) {
187 if (OpNo < MT->getNumOperands())
188 return C.top<Metadata>() == MT->getOperand(OpNo).get();
189 return false;
190 }
191 llvm_unreachable("Unknown metadata container");
192 }
193 if (const Value *VR = StackRec.get<Value>()) {
194 if (const auto *Insn = dyn_cast<Instruction>(VR)) {
195 if (OpNo < Insn->getNumOperands())
196 return C.top<Value>() == Insn->getOperand(OpNo);
197 return false;
198 }
199 llvm_unreachable("Unknown value container");
200 }
201 llvm_unreachable("Unknown type container");
202 }
203 return false;
204 }
205};
206
207
208/// Matcher that tests if the entity is a constant integer.
209///
210class ConstantIntMatcher : public Matcher {
211 uint64_t IntValue;
212 unsigned Width;
213public:
214 ConstantIntMatcher(uint64_t V, unsigned W = 0) : IntValue(V), Width(W) {}
215 bool match(MatcherContext &Ctx) override {
216 if (const Value *V = Ctx.top<Value>()) {
217 if (const auto *CI = dyn_cast<ConstantInt>(V))
218 return (Width == 0 || CI->getBitWidth() == Width) &&
219 CI->getLimitedValue() == IntValue;
220 }
221 if (const Metadata *M = Ctx.top<Metadata>()) {
222 if (const auto *MT = dyn_cast<ValueAsMetadata>(M))
223 if (const auto *C = dyn_cast<ConstantInt>(MT->getValue()))
224 return (Width == 0 || C->getBitWidth() == Width) &&
225 C->getLimitedValue() == IntValue;
226 }
227 return false;
228 }
229};
230
231
232/// Value matcher tuned to test instructions.
233///
234class InstructionMatcher : public EntityMatcher<Value> {
235 SmallVector<std::shared_ptr<Matcher>, 8> OperandMatchers;
236 std::shared_ptr<EntityMatcher<Metadata>> MetaMatcher = nullptr;
237 unsigned Code;
238public:
239 InstructionMatcher(unsigned C) : Code(C) {}
240
241 void push(std::shared_ptr<EntityMatcher<Metadata>> M) {
242 assert(!MetaMatcher && "Only one metadata matcher may be specified");
243 MetaMatcher = M;
244 }
245 void push(std::shared_ptr<Matcher> V) { OperandMatchers.push_back(V); }
246 template<typename... Args>
247 void push(std::shared_ptr<Matcher> V, Args... A) {
248 push(V);
249 push(A...);
250 }
251
252 virtual bool matchInstruction(const Instruction &I) {
253 return I.getOpcode() == Code;
254 }
255
256 bool matchEntity(const Value &V, MatcherContext &C) override {
257 if (const auto *I = dyn_cast<Instruction>(&V)) {
258 if (!matchInstruction(*I))
259 return false;
260 if (OperandMatchers.size() > I->getNumOperands())
261 return false;
262 for (unsigned N = 0, E = OperandMatchers.size(); N != E; ++N) {
263 C.push(I->getOperand(N), N);
264 if (!OperandMatchers[N]->match(C)) {
265 C.pop();
266 return false;
267 }
268 C.pop();
269 }
270 if (MetaMatcher) {
271 SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
272 I->getAllMetadata(MDs);
273 bool Found = false;
274 for (auto Item : MDs) {
275 C.push(Item.second);
276 if (MetaMatcher->match(C)) {
277 Found = true;
278 C.pop();
279 break;
280 }
281 C.pop();
282 }
283 return Found;
284 }
285 return true;
286 }
287 return false;
288 }
289};
290
291
292/// Matcher that tests type of the current value using the specified
293/// type matcher.
294///
295class ValueTypeMatcher : public EntityMatcher<Value> {
296 std::shared_ptr<EntityMatcher<Type>> TyM;
297public:
298 ValueTypeMatcher(std::shared_ptr<EntityMatcher<Type>> T) : TyM(T) {}
299 ValueTypeMatcher(const Type *T)
300 : TyM(new CondMatcher<Type>([T](const Type &Ty) -> bool {
301 return &Ty == T;
302 })) {}
303 bool matchEntity(const Value &V, MatcherContext &Ctx) override {
304 Type *Ty = V.getType();
305 Ctx.push(Ty);
306 bool Res = TyM->match(Ctx);
307 Ctx.pop();
308 return Res;
309 }
310};
311
312
313/// Matcher that matches string metadata.
314///
315class NameMetaMatcher : public EntityMatcher<Metadata> {
316 StringRef Name;
317public:
318 NameMetaMatcher(StringRef N) : Name(N) {}
319 bool matchEntity(const Metadata &M, MatcherContext &C) override {
320 if (auto *MDS = dyn_cast<MDString>(&M))
321 return MDS->getString().equals(Name);
322 return false;
323 }
324};
325
326
327/// Matcher that matches metadata tuples.
328///
329class MTupleMatcher : public EntityMatcher<Metadata> {
330 SmallVector<std::shared_ptr<Matcher>, 4> Operands;
331public:
332 void push(std::shared_ptr<Matcher> M) { Operands.push_back(M); }
333 template<typename... Args>
334 void push(std::shared_ptr<Matcher> M, Args... A) {
335 push(M);
336 push(A...);
337 }
338 bool matchEntity(const Metadata &M, MatcherContext &C) override {
339 if (const auto *MT = dyn_cast<MDTuple>(&M)) {
340 if (MT->getNumOperands() != Operands.size())
341 return false;
342 for (unsigned I = 0, E = MT->getNumOperands(); I != E; ++I) {
343 const MDOperand &Op = MT->getOperand(I);
344 C.push(Op.get(), I);
345 if (!Operands[I]->match(C)) {
346 C.pop();
347 return false;
348 }
349 C.pop();
350 }
351 return true;
352 }
353 return false;
354 }
355};
356
357
358// Helper function used to construct matchers.
359
360std::shared_ptr<Matcher> MSameAs(unsigned N) {
361 return std::shared_ptr<Matcher>(new SameAsMatcher(N));
362}
363
364template<typename... T>
365std::shared_ptr<InstructionMatcher> MInstruction(unsigned C, T... Args) {
366 auto Result = new InstructionMatcher(C);
367 Result->push(Args...);
368 return std::shared_ptr<InstructionMatcher>(Result);
369}
370
371std::shared_ptr<Matcher> MConstInt(uint64_t V, unsigned W = 0) {
372 return std::shared_ptr<Matcher>(new ConstantIntMatcher(V, W));
373}
374
375std::shared_ptr<EntityMatcher<Value>>
376 MValType(std::shared_ptr<EntityMatcher<Type>> T) {
377 return std::shared_ptr<EntityMatcher<Value>>(new ValueTypeMatcher(T));
378}
379
380std::shared_ptr<EntityMatcher<Value>> MValType(const Type *T) {
381 return std::shared_ptr<EntityMatcher<Value>>(new ValueTypeMatcher(T));
382}
383
384std::shared_ptr<EntityMatcher<Type>>
385MType(std::function<bool(const Type &)> C) {
386 return std::shared_ptr<EntityMatcher<Type>>(new CondMatcher<Type>(C));
387}
388
389std::shared_ptr<EntityMatcher<Metadata>> MMAny() {
390 return std::shared_ptr<EntityMatcher<Metadata>>(new AnyMatcher<Metadata>);
391}
392
393std::shared_ptr<EntityMatcher<Metadata>>
394MMSave(const Metadata *&V, std::shared_ptr<EntityMatcher<Metadata>> M) {
395 return std::shared_ptr<EntityMatcher<Metadata>>(
396 new SavingMatcher<Metadata>(V, M));
397}
398
399std::shared_ptr<EntityMatcher<Metadata>>
400MMString(const char *Name) {
401 return std::shared_ptr<EntityMatcher<Metadata>>(new NameMetaMatcher(Name));
402}
403
404template<typename... T>
405std::shared_ptr<EntityMatcher<Metadata>> MMTuple(T... Args) {
406 auto Res = new MTupleMatcher();
407 Res->push(Args...);
408 return std::shared_ptr<EntityMatcher<Metadata>>(Res);
409}
410
411
412/// Looks for the instruction that satisfies condition of the specified
413/// matcher inside the given basic block.
414/// \returns Pointer to the found instruction or nullptr if such instruction
415/// was not found.
416///
417const Instruction *match(const BasicBlock *BB, std::shared_ptr<Matcher> M) {
418 MatcherContext MC;
419 for (const auto &I : *BB) {
420 MC.push(&I);
421 if (M->match(MC))
422 return &I;
423 MC.pop();
424 }
425 assert(MC.size() == 0);
426 return nullptr;
427}
428
429
430/// Looks for the instruction that satisfies condition of the specified
431/// matcher starting from the specified instruction inside the same basic block.
432///
433/// The given instruction is not checked.
434///
435const Instruction *matchNext(const Instruction *I, std::shared_ptr<Matcher> M) {
436 if (!I)
437 return nullptr;
438 MatcherContext MC;
439 const BasicBlock *BB = I->getParent();
440 if (!BB)
441 return nullptr;
442 for (auto P = ++BasicBlock::const_iterator(I), E = BB->end(); P != E; ++P) {
443 MC.push(&*P);
444 if (M->match(MC))
445 return &*P;
446 MC.pop();
447 }
448 assert(MC.size() == 0);
449 return nullptr;
450}
451
452}
453#endif