1 //===- MustExecute.h - Is an instruction known to execute--------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
15 //===----------------------------------------------------------------------===//
17 #ifndef LLVM_ANALYSIS_MUSTEXECUTE_H
18 #define LLVM_ANALYSIS_MUSTEXECUTE_H
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"
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;
53 /// Computes block colors.
54 void computeBlockColors(const Loop *CurLoop);
57 /// Returns block colors map that is used to update funclet operand bundles.
58 const DenseMap<BasicBlock *, ColorVector> &getBlockColors() const;
60 /// Copy colors of block \p Old into the block \p New.
61 void copyColors(BasicBlock *New, BasicBlock *Old);
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;
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;
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;
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;
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;
89 LoopSafetyInfo() = default;
91 virtual ~LoopSafetyInfo() = default;
95 /// Simple and conservative implementation of LoopSafetyInfo that can give
96 /// false-positive answers to its queries in order to avoid complicated
98 class SimpleLoopSafetyInfo: public LoopSafetyInfo {
99 bool MayThrow = false; // The current loop contains an instruction which
101 bool HeaderMayThrow = false; // Same as previous, but specific to loop header
104 virtual bool blockMayThrow(const BasicBlock *BB) const;
106 virtual bool anyBlockMayThrow() const;
108 virtual void computeLoopSafetyInfo(const Loop *CurLoop);
110 virtual bool isGuaranteedToExecute(const Instruction &Inst,
111 const DominatorTree *DT,
112 const Loop *CurLoop) const;
114 SimpleLoopSafetyInfo() : LoopSafetyInfo() {};
116 virtual ~SimpleLoopSafetyInfo() {};
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
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;
133 virtual bool blockMayThrow(const BasicBlock *BB) const;
135 virtual bool anyBlockMayThrow() const;
137 virtual void computeLoopSafetyInfo(const Loop *CurLoop);
139 virtual bool isGuaranteedToExecute(const Instruction &Inst,
140 const DominatorTree *DT,
141 const Loop *CurLoop) const;
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)
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)
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);
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
161 void removeInstruction(const Instruction *Inst);
163 ICFLoopSafetyInfo(DominatorTree *DT) : LoopSafetyInfo(), ICF(DT), MW(DT) {};
165 virtual ~ICFLoopSafetyInfo() {};