452 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8/// \file9/// This file provides a simple mechanism for performing search operations over10/// IR including metadata and types. It allows writing complex search patterns11/// using understandable syntax. For instance, the code:12///13/// \code14/// 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/// \endcode27///28/// searches the basic block BB for the 'store' instruction, first argument of29/// which is 'i8 4', and the attached metadata has an item described by the30/// given tree.31//===----------------------------------------------------------------------===//32 33#ifndef CLANG_UNITTESTS_CODEGEN_IRMATCHERS_H34#define CLANG_UNITTESTS_CODEGEN_IRMATCHERS_H35 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 to48/// use queries like "this operand is the same as n-th operand", which are49/// 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(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 satisfies112 /// 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 specified142/// 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 the156// 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 the174/// 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 specified292/// 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() == 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 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 specified411/// matcher inside the given basic block.412/// \returns Pointer to the found instruction or nullptr if such instruction413/// 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(&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 specified429/// 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(&*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#endif452