1 //===- llvm/Transforms/Utils/OrderedInstructions.h -------------*- 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 // 10 // This file defines an efficient way to check for dominance relation between 2 11 // instructions. 12 // 13 // This interface dispatches to appropriate dominance check given 2 14 // instructions, i.e. in case the instructions are in the same basic block, 15 // OrderedBasicBlock (with instruction numbering and caching) are used. 16 // Otherwise, dominator tree is used. 17 // 18 //===----------------------------------------------------------------------===// 19 20 #ifndef LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H 21 #define LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H 22 23 #include "llvm/ADT/DenseMap.h" 24 #include "llvm/Analysis/OrderedBasicBlock.h" 25 #include "llvm/IR/Dominators.h" 26 #include "llvm/IR/Operator.h" 27 28 namespace llvm { 29 30 class OrderedInstructions { 31 /// Used to check dominance for instructions in same basic block. 32 mutable DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> 33 OBBMap; 34 35 /// The dominator tree of the parent function. 36 DominatorTree *DT; 37 38 /// Return true if the first instruction comes before the second in the 39 /// same basic block. It will create an ordered basic block, if it does 40 /// not yet exist in OBBMap. 41 bool localDominates(const Instruction *, const Instruction *) const; 42 43 public: 44 /// Constructor. OrderedInstructions(DominatorTree * DT)45 OrderedInstructions(DominatorTree *DT) : DT(DT) {} 46 47 /// Return true if first instruction dominates the second. 48 bool dominates(const Instruction *, const Instruction *) const; 49 50 /// Return true if the first instruction comes before the second in the 51 /// dominator tree DFS traversal if they are in different basic blocks, 52 /// or if the first instruction comes before the second in the same basic 53 /// block. 54 bool dfsBefore(const Instruction *, const Instruction *) const; 55 56 /// Invalidate the OrderedBasicBlock cache when its basic block changes. 57 /// i.e. If an instruction is deleted or added to the basic block, the user 58 /// should call this function to invalidate the OrderedBasicBlock cache for 59 /// this basic block. invalidateBlock(const BasicBlock * BB)60 void invalidateBlock(const BasicBlock *BB) { OBBMap.erase(BB); } 61 }; 62 63 } // end namespace llvm 64 65 #endif // LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H 66