1 //===- MustExecute.h - Is an instruction known to execute--------*- 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 /// Contains a collection of routines for determining if a given instruction is 11 /// guaranteed to execute if a given point in control flow is reached. The most 12 /// common example is an instruction within a loop being provably executed if we 13 /// branch to the header of it's containing loop. 14 /// 15 //===----------------------------------------------------------------------===// 16 17 #ifndef LLVM_ANALYSIS_MUSTEXECUTE_H 18 #define LLVM_ANALYSIS_MUSTEXECUTE_H 19 20 #include "llvm/ADT/DenseMap.h" 21 #include "llvm/Analysis/EHPersonalities.h" 22 #include "llvm/Analysis/InstructionPrecedenceTracking.h" 23 #include "llvm/Analysis/LoopInfo.h" 24 #include "llvm/IR/BasicBlock.h" 25 #include "llvm/IR/Dominators.h" 26 #include "llvm/IR/Instruction.h" 27 28 namespace llvm { 29 30 class Instruction; 31 class DominatorTree; 32 class Loop; 33 34 /// Captures loop safety information. 35 /// It keep information for loop blocks may throw exception or otherwise 36 /// exit abnormaly on any iteration of the loop which might actually execute 37 /// at runtime. The primary way to consume this infromation is via 38 /// isGuaranteedToExecute below, but some callers bailout or fallback to 39 /// alternate reasoning if a loop contains any implicit control flow. 40 /// NOTE: LoopSafetyInfo contains cached information regarding loops and their 41 /// particular blocks. This information is only dropped on invocation of 42 /// computeLoopSafetyInfo. If the loop or any of its block is deleted, or if 43 /// any thrower instructions have been added or removed from them, or if the 44 /// control flow has changed, or in case of other meaningful modifications, the 45 /// LoopSafetyInfo needs to be recomputed. If a meaningful modifications to the 46 /// loop were made and the info wasn't recomputed properly, the behavior of all 47 /// methods except for computeLoopSafetyInfo is undefined. 48 class LoopSafetyInfo { 49 // Used to update funclet bundle operands. 50 DenseMap<BasicBlock *, ColorVector> BlockColors; 51 52 protected: 53 /// Computes block colors. 54 void computeBlockColors(const Loop *CurLoop); 55 56 public: 57 /// Returns block colors map that is used to update funclet operand bundles. 58 const DenseMap<BasicBlock *, ColorVector> &getBlockColors() const; 59 60 /// Copy colors of block \p Old into the block \p New. 61 void copyColors(BasicBlock *New, BasicBlock *Old); 62 63 /// Returns true iff the block \p BB potentially may throw exception. It can 64 /// be false-positive in cases when we want to avoid complex analysis. 65 virtual bool blockMayThrow(const BasicBlock *BB) const = 0; 66 67 /// Returns true iff any block of the loop for which this info is contains an 68 /// instruction that may throw or otherwise exit abnormally. 69 virtual bool anyBlockMayThrow() const = 0; 70 71 /// Return true if we must reach the block \p BB under assumption that the 72 /// loop \p CurLoop is entered. 73 bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB, 74 const DominatorTree *DT) const; 75 76 /// Computes safety information for a loop checks loop body & header for 77 /// the possibility of may throw exception, it takes LoopSafetyInfo and loop 78 /// as argument. Updates safety information in LoopSafetyInfo argument. 79 /// Note: This is defined to clear and reinitialize an already initialized 80 /// LoopSafetyInfo. Some callers rely on this fact. 81 virtual void computeLoopSafetyInfo(const Loop *CurLoop) = 0; 82 83 /// Returns true if the instruction in a loop is guaranteed to execute at 84 /// least once (under the assumption that the loop is entered). 85 virtual bool isGuaranteedToExecute(const Instruction &Inst, 86 const DominatorTree *DT, 87 const Loop *CurLoop) const = 0; 88 89 LoopSafetyInfo() = default; 90 91 virtual ~LoopSafetyInfo() = default; 92 }; 93 94 95 /// Simple and conservative implementation of LoopSafetyInfo that can give 96 /// false-positive answers to its queries in order to avoid complicated 97 /// analysis. 98 class SimpleLoopSafetyInfo: public LoopSafetyInfo { 99 bool MayThrow = false; // The current loop contains an instruction which 100 // may throw. 101 bool HeaderMayThrow = false; // Same as previous, but specific to loop header 102 103 public: 104 virtual bool blockMayThrow(const BasicBlock *BB) const; 105 106 virtual bool anyBlockMayThrow() const; 107 108 virtual void computeLoopSafetyInfo(const Loop *CurLoop); 109 110 virtual bool isGuaranteedToExecute(const Instruction &Inst, 111 const DominatorTree *DT, 112 const Loop *CurLoop) const; 113 SimpleLoopSafetyInfo()114 SimpleLoopSafetyInfo() : LoopSafetyInfo() {}; 115 ~SimpleLoopSafetyInfo()116 virtual ~SimpleLoopSafetyInfo() {}; 117 }; 118 119 /// This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to 120 /// give precise answers on "may throw" queries. This implementation uses cache 121 /// that should be invalidated by calling the methods insertInstructionTo and 122 /// removeInstruction whenever we modify a basic block's contents by adding or 123 /// removing instructions. 124 class ICFLoopSafetyInfo: public LoopSafetyInfo { 125 bool MayThrow = false; // The current loop contains an instruction which 126 // may throw. 127 // Contains information about implicit control flow in this loop's blocks. 128 mutable ImplicitControlFlowTracking ICF; 129 // Contains information about instruction that may possibly write memory. 130 mutable MemoryWriteTracking MW; 131 132 public: 133 virtual bool blockMayThrow(const BasicBlock *BB) const; 134 135 virtual bool anyBlockMayThrow() const; 136 137 virtual void computeLoopSafetyInfo(const Loop *CurLoop); 138 139 virtual bool isGuaranteedToExecute(const Instruction &Inst, 140 const DominatorTree *DT, 141 const Loop *CurLoop) const; 142 143 /// Returns true if we could not execute a memory-modifying instruction before 144 /// we enter \p BB under assumption that \p CurLoop is entered. 145 bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop) 146 const; 147 148 /// Returns true if we could not execute a memory-modifying instruction before 149 /// we execute \p I under assumption that \p CurLoop is entered. 150 bool doesNotWriteMemoryBefore(const Instruction &I, const Loop *CurLoop) 151 const; 152 153 /// Inform the safety info that we are planning to insert a new instruction 154 /// \p Inst into the basic block \p BB. It will make all cache updates to keep 155 /// it correct after this insertion. 156 void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB); 157 158 /// Inform safety info that we are planning to remove the instruction \p Inst 159 /// from its block. It will make all cache updates to keep it correct after 160 /// this removal. 161 void removeInstruction(const Instruction *Inst); 162 ICFLoopSafetyInfo(DominatorTree * DT)163 ICFLoopSafetyInfo(DominatorTree *DT) : LoopSafetyInfo(), ICF(DT), MW(DT) {}; 164 ~ICFLoopSafetyInfo()165 virtual ~ICFLoopSafetyInfo() {}; 166 }; 167 168 } 169 170 #endif 171