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