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
43namespace 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///
51class MatcherContext {
52public:
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 PointerUnion<const Value *, const Metadata *, const Type *> Entity;
62 unsigned OperandNo;
63
64 public:
65 Query(const Value *V, unsigned N) : Entity(V), OperandNo(N) {}
66 Query(const Metadata *M, unsigned N) : Entity(M), OperandNo(N) {}
67 Query(const Type *T, unsigned N) : Entity(T), OperandNo(N) {}
68
69 template<typename T>
70 const T *get() const {
71 return Entity.dyn_cast<const T *>();
72 }
73
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(Elt: Query(V, N));
80 }
81
82 void pop() { MatchStack.pop_back(); }
83
84 template<typename T>
85 const T *top() const { return MatchStack.back().get<T>(); }
86
87 size_t size() const { return MatchStack.size(); }
88
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 ///
95 const Query &getQuery(unsigned Offset) const {
96 assert(MatchStack.size() > Offset);
97 return MatchStack[MatchStack.size() - 1 - Offset];
98 }
99
100private:
101 SmallVector<Query, 8> MatchStack;
102};
103
104
105/// Base of all matcher classes.
106///
107class Matcher {
108public:
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///
120template<typename T>
121class EntityMatcher : public Matcher {
122public:
123 bool match(MatcherContext &MC) override {
124 if (auto V = MC.top<T>())
125 return matchEntity(M: *V, C&: 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///
134template<typename T>
135class AnyMatcher : public EntityMatcher<T> {
136public:
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///
144template<typename T>
145class CondMatcher : public EntityMatcher<T> {
146 std::function<bool(const T &)> Condition;
147public:
148 CondMatcher(std::function<bool(const T &)> C) : Condition(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///
158template<typename T>
159class SavingMatcher : public EntityMatcher<T> {
160 const T *&Var;
161 std::shared_ptr<Matcher> Next;
162public:
163 SavingMatcher(const T *&V, std::shared_ptr<Matcher> N) : Var(V), Next(N) {}
164 bool matchEntity(const T &V, MatcherContext &C) override {
165 bool Result = Next->match(MC&: 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///
176class SameAsMatcher : public Matcher {
177 unsigned OpNo;
178public:
179 SameAsMatcher(unsigned N) : OpNo(N) {}
180 bool match(MatcherContext &C) override {
181 if (C.getOperandNo() != ~0U) {
182 // Handle all known containers here.
183 const MatcherContext::Query &StackRec = C.getQuery(Offset: 1);
184 if (const Metadata *MR = StackRec.get<Metadata>()) {
185 if (const auto *MT = dyn_cast<MDTuple>(Val: MR)) {
186 if (OpNo < MT->getNumOperands())
187 return C.top<Metadata>() == MT->getOperand(I: 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>(Val: VR)) {
194 if (OpNo < Insn->getNumOperands())
195 return C.top<Value>() == Insn->getOperand(i: 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///
209class ConstantIntMatcher : public Matcher {
210 uint64_t IntValue;
211 unsigned Width;
212public:
213 ConstantIntMatcher(uint64_t V, unsigned W = 0) : IntValue(V), Width(W) {}
214 bool match(MatcherContext &Ctx) override {
215 if (const Value *V = Ctx.top<Value>()) {
216 if (const auto *CI = dyn_cast<ConstantInt>(Val: 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>(Val: M))
222 if (const auto *C = dyn_cast<ConstantInt>(Val: 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///
233class InstructionMatcher : public EntityMatcher<Value> {
234 SmallVector<std::shared_ptr<Matcher>, 8> OperandMatchers;
235 std::shared_ptr<EntityMatcher<Metadata>> MetaMatcher = nullptr;
236 unsigned Code;
237public:
238 InstructionMatcher(unsigned C) : Code(C) {}
239
240 void push(std::shared_ptr<EntityMatcher<Metadata>> M) {
241 assert(!MetaMatcher && "Only one metadata matcher may be specified");
242 MetaMatcher = M;
243 }
244 void push(std::shared_ptr<Matcher> V) { OperandMatchers.push_back(Elt: V); }
245 template<typename... Args>
246 void push(std::shared_ptr<Matcher> V, Args... A) {
247 push(V);
248 push(A...);
249 }
250
251 virtual bool matchInstruction(const Instruction &I) {
252 return I.getOpcode() == Code;
253 }
254
255 bool matchEntity(const Value &V, MatcherContext &C) override {
256 if (const auto *I = dyn_cast<Instruction>(Val: &V)) {
257 if (!matchInstruction(I: *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(V: I->getOperand(i: N), N);
263 if (!OperandMatchers[N]->match(MC&: 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(V: Item.second);
275 if (MetaMatcher->match(MC&: 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///
294class ValueTypeMatcher : public EntityMatcher<Value> {
295 std::shared_ptr<EntityMatcher<Type>> TyM;
296public:
297 ValueTypeMatcher(std::shared_ptr<EntityMatcher<Type>> T) : TyM(T) {}
298 ValueTypeMatcher(const Type *T)
299 : TyM(new CondMatcher<Type>([T](const Type &Ty) -> bool {
300 return &Ty == T;
301 })) {}
302 bool matchEntity(const Value &V, MatcherContext &Ctx) override {
303 Type *Ty = V.getType();
304 Ctx.push(V: Ty);
305 bool Res = TyM->match(MC&: Ctx);
306 Ctx.pop();
307 return Res;
308 }
309};
310
311
312/// Matcher that matches string metadata.
313///
314class NameMetaMatcher : public EntityMatcher<Metadata> {
315 StringRef Name;
316public:
317 NameMetaMatcher(StringRef N) : Name(N) {}
318 bool matchEntity(const Metadata &M, MatcherContext &C) override {
319 if (auto *MDS = dyn_cast<MDString>(Val: &M))
320 return MDS->getString().equals(RHS: Name);
321 return false;
322 }
323};
324
325
326/// Matcher that matches metadata tuples.
327///
328class MTupleMatcher : public EntityMatcher<Metadata> {
329 SmallVector<std::shared_ptr<Matcher>, 4> Operands;
330public:
331 void push(std::shared_ptr<Matcher> M) { Operands.push_back(Elt: M); }
332 template<typename... Args>
333 void push(std::shared_ptr<Matcher> M, Args... A) {
334 push(M);
335 push(A...);
336 }
337 bool matchEntity(const Metadata &M, MatcherContext &C) override {
338 if (const auto *MT = dyn_cast<MDTuple>(Val: &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(V: Op.get(), N: I);
344 if (!Operands[I]->match(MC&: 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
359inline std::shared_ptr<Matcher> MSameAs(unsigned N) {
360 return std::shared_ptr<Matcher>(new SameAsMatcher(N));
361}
362
363template<typename... T>
364std::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
370inline std::shared_ptr<Matcher> MConstInt(uint64_t V, unsigned W = 0) {
371 return std::shared_ptr<Matcher>(new ConstantIntMatcher(V, W));
372}
373
374inline std::shared_ptr<EntityMatcher<Value>>
375MValType(std::shared_ptr<EntityMatcher<Type>> T) {
376 return std::shared_ptr<EntityMatcher<Value>>(new ValueTypeMatcher(T));
377}
378
379inline std::shared_ptr<EntityMatcher<Value>> MValType(const Type *T) {
380 return std::shared_ptr<EntityMatcher<Value>>(new ValueTypeMatcher(T));
381}
382
383inline std::shared_ptr<EntityMatcher<Type>>
384MType(std::function<bool(const Type &)> C) {
385 return std::shared_ptr<EntityMatcher<Type>>(new CondMatcher<Type>(C));
386}
387
388inline std::shared_ptr<EntityMatcher<Metadata>> MMAny() {
389 return std::shared_ptr<EntityMatcher<Metadata>>(new AnyMatcher<Metadata>);
390}
391
392inline std::shared_ptr<EntityMatcher<Metadata>>
393MMSave(const Metadata *&V, std::shared_ptr<EntityMatcher<Metadata>> M) {
394 return std::shared_ptr<EntityMatcher<Metadata>>(
395 new SavingMatcher<Metadata>(V, M));
396}
397
398inline std::shared_ptr<EntityMatcher<Metadata>> MMString(const char *Name) {
399 return std::shared_ptr<EntityMatcher<Metadata>>(new NameMetaMatcher(Name));
400}
401
402template<typename... T>
403std::shared_ptr<EntityMatcher<Metadata>> MMTuple(T... Args) {
404 auto Res = new MTupleMatcher();
405 Res->push(Args...);
406 return std::shared_ptr<EntityMatcher<Metadata>>(Res);
407}
408
409
410/// Looks for the instruction that satisfies condition of the specified
411/// matcher inside the given basic block.
412/// \returns Pointer to the found instruction or nullptr if such instruction
413/// was not found.
414///
415inline const Instruction *match(const BasicBlock *BB,
416 std::shared_ptr<Matcher> M) {
417 MatcherContext MC;
418 for (const auto &I : *BB) {
419 MC.push(V: &I);
420 if (M->match(MC))
421 return &I;
422 MC.pop();
423 }
424 assert(MC.size() == 0);
425 return nullptr;
426}
427
428/// Looks for the instruction that satisfies condition of the specified
429/// matcher starting from the specified instruction inside the same basic block.
430///
431/// The given instruction is not checked.
432///
433inline const Instruction *matchNext(const Instruction *I, std::shared_ptr<Matcher> M) {
434 if (!I)
435 return nullptr;
436 MatcherContext MC;
437 const BasicBlock *BB = I->getParent();
438 if (!BB)
439 return nullptr;
440 for (auto P = ++BasicBlock::const_iterator(I), E = BB->end(); P != E; ++P) {
441 MC.push(V: &*P);
442 if (M->match(MC))
443 return &*P;
444 MC.pop();
445 }
446 assert(MC.size() == 0);
447 return nullptr;
448}
449
450}
451#endif
452

source code of clang/unittests/CodeGen/IRMatchers.h