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