clang/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
  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     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(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
 100 private:
 101   SmallVector<Query, 8> MatchStack;
 102 };
 103
 104
 105 /// Base of all matcher classes.
 106 ///
 107 class Matcher {
 108 public:
 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:
 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:
 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:
 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 ///
 158 template<typename T>
 159 class SavingMatcher : public EntityMatcher<T> {
 160   const T *&Var;
 161   std::shared_ptr<Matcher> Next;
 162 public:
 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 ///
 176 class SameAsMatcher : public Matcher {
 177   unsigned OpNo;
 178 public:
 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 ///
 209 class ConstantIntMatcher : public Matcher {
 210   uint64_t IntValue;
 211   unsigned Width;
 212 public:
 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 ///
 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:
 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 ///
 294 class ValueTypeMatcher : public EntityMatcher<Value> {
 295   std::shared_ptr<EntityMatcher<Type>> TyM;
 296 public:
 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 ///
 314 class NameMetaMatcher : public EntityMatcher<Metadata> {
 315   StringRef Name;
 316 public:
 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() == 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:
 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
 359 inline std::shared_ptr<Matcher> MSameAs(unsigned N) {
 360   return std::shared_ptr<Matcher>(new SameAsMatcher(N));
 361 }
 362
 363 template<typename... T>
 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 inline std::shared_ptr<Matcher> MConstInt(uint64_t V, unsigned W = 0) {
 371   return std::shared_ptr<Matcher>(new ConstantIntMatcher(V, W));
 372 }
 373
 374 inline std::shared_ptr<EntityMatcher<Value>>
 375 MValType(std::shared_ptr<EntityMatcher<Type>> T) {
 376   return std::shared_ptr<EntityMatcher<Value>>(new ValueTypeMatcher(T));
 377 }
 378
 379 inline std::shared_ptr<EntityMatcher<Value>> MValType(const Type *T) {
 380   return std::shared_ptr<EntityMatcher<Value>>(new ValueTypeMatcher(T));
 381 }
 382
 383 inline std::shared_ptr<EntityMatcher<Type>>
 384 MType(std::function<bool(const Type &)> C) {
 385   return std::shared_ptr<EntityMatcher<Type>>(new CondMatcher<Type>(C));
 386 }
 387
 388 inline std::shared_ptr<EntityMatcher<Metadata>> MMAny() {
 389   return std::shared_ptr<EntityMatcher<Metadata>>(new AnyMatcher<Metadata>);
 390 }
 391
 392 inline std::shared_ptr<EntityMatcher<Metadata>>
 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 inline std::shared_ptr<EntityMatcher<Metadata>> MMString(const char *Name) {
 399   return std::shared_ptr<EntityMatcher<Metadata>>(new NameMetaMatcher(Name));
 400 }
 401
 402 template<typename... T>
 403 std::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 ///
 415 inline const Instruction *match(const BasicBlock *BB,
 416                                 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 /// 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 ///
 433 inline 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(&*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