Clang Project

clang_source_code/unittests/CodeGen/IRMatchers.h
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    PointerUnion3<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(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(*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///
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(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(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///
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>(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///
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(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>(&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///
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(Ty);
305    bool Res = TyM->match(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>(&M))
320      return MDS->getString().equals(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(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>(&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
359std::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
370std::shared_ptr<Matcher> MConstInt(uint64_t V, unsigned W = 0) {
371  return std::shared_ptr<Matcher>(new ConstantIntMatcher(V, W));
372}
373
374std::shared_ptr<EntityMatcher<Value>>
375 MValType(std::shared_ptr<EntityMatcher<Type>> T) {
376  return std::shared_ptr<EntityMatcher<Value>>(new ValueTypeMatcher(T));
377}
378
379std::shared_ptr<EntityMatcher<Value>> MValType(const Type *T) {
380  return std::shared_ptr<EntityMatcher<Value>>(new ValueTypeMatcher(T));
381}
382
383std::shared_ptr<EntityMatcher<Type>>
384MType(std::function<bool(const Type &)> C) {
385  return std::shared_ptr<EntityMatcher<Type>>(new CondMatcher<Type>(C));
386}
387
388std::shared_ptr<EntityMatcher<Metadata>> MMAny() {
389  return std::shared_ptr<EntityMatcher<Metadata>>(new AnyMatcher<Metadata>);
390}
391
392std::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
398std::shared_ptr<EntityMatcher<Metadata>>
399MMString(const char *Name) {
400  return std::shared_ptr<EntityMatcher<Metadata>>(new NameMetaMatcher(Name));
401}
402
403template<typename... T>
404std::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///
416const 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///
434const 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
llvm::MatcherContext::Query
llvm::MatcherContext::Query::Entity
llvm::MatcherContext::Query::OperandNo
llvm::MatcherContext::Query::get
llvm::MatcherContext::Query::getOperandNo
llvm::MatcherContext::push
llvm::MatcherContext::pop
llvm::MatcherContext::top
llvm::MatcherContext::size
llvm::MatcherContext::getOperandNo
llvm::MatcherContext::getQuery
llvm::MatcherContext::MatchStack
llvm::Matcher::match
llvm::EntityMatcher::match
llvm::EntityMatcher::matchEntity
llvm::AnyMatcher::matchEntity
llvm::CondMatcher::Condition
llvm::CondMatcher::matchEntity
llvm::SavingMatcher::Var
llvm::SavingMatcher::Next
llvm::SavingMatcher::matchEntity
llvm::SameAsMatcher::OpNo
llvm::SameAsMatcher::match
llvm::ConstantIntMatcher::IntValue
llvm::ConstantIntMatcher::Width
llvm::ConstantIntMatcher::match
llvm::InstructionMatcher::MetaMatcher
llvm::InstructionMatcher::Code
llvm::InstructionMatcher::push
llvm::InstructionMatcher::push
llvm::InstructionMatcher::matchInstruction
llvm::InstructionMatcher::matchEntity
llvm::ValueTypeMatcher::TyM
llvm::ValueTypeMatcher::matchEntity
llvm::NameMetaMatcher::Name
llvm::NameMetaMatcher::matchEntity
llvm::MTupleMatcher::push
llvm::MTupleMatcher::push
llvm::MTupleMatcher::matchEntity
CodeThinker, Enjoy your reading code