1 //===-- InstructionPrecedenceTracking.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 // Implements a class that is able to define some instructions as "special" 10 // (e.g. as having implicit control flow, or writing memory, or having another 11 // interesting property) and then efficiently answers queries of the types: 12 // 1. Are there any special instructions in the block of interest? 13 // 2. Return first of the special instructions in the given block; 14 // 3. Check if the given instruction is preceeded by the first special 15 // instruction in the same block. 16 // The class provides caching that allows to answer these queries quickly. The 17 // user must make sure that the cached data is invalidated properly whenever 18 // a content of some tracked block is changed. 19 //===----------------------------------------------------------------------===// 20 21 #ifndef LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H 22 #define LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H 23 24 #include "llvm/IR/Dominators.h" 25 #include "llvm/Analysis/OrderedInstructions.h" 26 27 namespace llvm { 28 29 class InstructionPrecedenceTracking { 30 // Maps a block to the topmost special instruction in it. If the value is 31 // nullptr, it means that it is known that this block does not contain any 32 // special instructions. 33 DenseMap<const BasicBlock *, const Instruction *> FirstSpecialInsts; 34 // Allows to answer queries about precedence of instructions within one block. 35 OrderedInstructions OI; 36 37 // Fills information about the given block's special instructions. 38 void fill(const BasicBlock *BB); 39 40 #ifndef NDEBUG 41 /// Asserts that the cached info for \p BB is up-to-date. This helps to catch 42 /// the usage error of accessing a block without properly invalidating after a 43 /// previous transform. 44 void validate(const BasicBlock *BB) const; 45 46 /// Asserts whether or not the contents of this tracking is up-to-date. This 47 /// helps to catch the usage error of accessing a block without properly 48 /// invalidating after a previous transform. 49 void validateAll() const; 50 #endif 51 52 protected: InstructionPrecedenceTracking(DominatorTree * DT)53 InstructionPrecedenceTracking(DominatorTree *DT) 54 : OI(OrderedInstructions(DT)) {} 55 56 /// Returns the topmost special instruction from the block \p BB. Returns 57 /// nullptr if there is no special instructions in the block. 58 const Instruction *getFirstSpecialInstruction(const BasicBlock *BB); 59 60 /// Returns true iff at least one instruction from the basic block \p BB is 61 /// special. 62 bool hasSpecialInstructions(const BasicBlock *BB); 63 64 /// Returns true iff the first special instruction of \p Insn's block exists 65 /// and dominates \p Insn. 66 bool isPreceededBySpecialInstruction(const Instruction *Insn); 67 68 /// A predicate that defines whether or not the instruction \p Insn is 69 /// considered special and needs to be tracked. Implementing this method in 70 /// children classes allows to implement tracking of implicit control flow, 71 /// memory writing instructions or any other kinds of instructions we might 72 /// be interested in. 73 virtual bool isSpecialInstruction(const Instruction *Insn) const = 0; 74 75 virtual ~InstructionPrecedenceTracking() = default; 76 77 public: 78 /// Notifies this tracking that we are going to insert a new instruction \p 79 /// Inst to the basic block \p BB. It makes all necessary updates to internal 80 /// caches to keep them consistent. 81 void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB); 82 83 /// Notifies this tracking that we are going to remove the instruction \p Inst 84 /// It makes all necessary updates to internal caches to keep them consistent. 85 void removeInstruction(const Instruction *Inst); 86 87 /// Invalidates all information from this tracking. 88 void clear(); 89 }; 90 91 /// This class allows to keep track on instructions with implicit control flow. 92 /// These are instructions that may not pass execution to their successors. For 93 /// example, throwing calls and guards do not always do this. If we need to know 94 /// for sure that some instruction is guaranteed to execute if the given block 95 /// is reached, then we need to make sure that there is no implicit control flow 96 /// instruction (ICFI) preceeding it. For example, this check is required if we 97 /// perform PRE moving non-speculable instruction to other place. 98 class ImplicitControlFlowTracking : public InstructionPrecedenceTracking { 99 public: ImplicitControlFlowTracking(DominatorTree * DT)100 ImplicitControlFlowTracking(DominatorTree *DT) 101 : InstructionPrecedenceTracking(DT) {} 102 103 /// Returns the topmost instruction with implicit control flow from the given 104 /// basic block. Returns nullptr if there is no such instructions in the block. getFirstICFI(const BasicBlock * BB)105 const Instruction *getFirstICFI(const BasicBlock *BB) { 106 return getFirstSpecialInstruction(BB); 107 } 108 109 /// Returns true if at least one instruction from the given basic block has 110 /// implicit control flow. hasICF(const BasicBlock * BB)111 bool hasICF(const BasicBlock *BB) { 112 return hasSpecialInstructions(BB); 113 } 114 115 /// Returns true if the first ICFI of Insn's block exists and dominates Insn. isDominatedByICFIFromSameBlock(const Instruction * Insn)116 bool isDominatedByICFIFromSameBlock(const Instruction *Insn) { 117 return isPreceededBySpecialInstruction(Insn); 118 } 119 120 virtual bool isSpecialInstruction(const Instruction *Insn) const; 121 }; 122 123 class MemoryWriteTracking : public InstructionPrecedenceTracking { 124 public: MemoryWriteTracking(DominatorTree * DT)125 MemoryWriteTracking(DominatorTree *DT) : InstructionPrecedenceTracking(DT) {} 126 127 /// Returns the topmost instruction that may write memory from the given 128 /// basic block. Returns nullptr if there is no such instructions in the block. getFirstMemoryWrite(const BasicBlock * BB)129 const Instruction *getFirstMemoryWrite(const BasicBlock *BB) { 130 return getFirstSpecialInstruction(BB); 131 } 132 133 /// Returns true if at least one instruction from the given basic block may 134 /// write memory. mayWriteToMemory(const BasicBlock * BB)135 bool mayWriteToMemory(const BasicBlock *BB) { 136 return hasSpecialInstructions(BB); 137 } 138 139 /// Returns true if the first memory writing instruction of Insn's block 140 /// exists and dominates Insn. isDominatedByMemoryWriteFromSameBlock(const Instruction * Insn)141 bool isDominatedByMemoryWriteFromSameBlock(const Instruction *Insn) { 142 return isPreceededBySpecialInstruction(Insn); 143 } 144 145 virtual bool isSpecialInstruction(const Instruction *Insn) const; 146 }; 147 148 } // llvm 149 150 #endif // LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H 151