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