Line data Source code
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 : /// Collect all blocks from \p CurLoop which lie on all possible paths from
53 : /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
54 : /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
55 : void collectTransitivePredecessors(
56 : const Loop *CurLoop, const BasicBlock *BB,
57 : SmallPtrSetImpl<const BasicBlock *> &Predecessors) const;
58 :
59 : protected:
60 : /// Computes block colors.
61 : void computeBlockColors(const Loop *CurLoop);
62 :
63 : public:
64 : /// Returns block colors map that is used to update funclet operand bundles.
65 : const DenseMap<BasicBlock *, ColorVector> &getBlockColors() const;
66 :
67 : /// Copy colors of block \p Old into the block \p New.
68 : void copyColors(BasicBlock *New, BasicBlock *Old);
69 :
70 : /// Returns true iff the block \p BB potentially may throw exception. It can
71 : /// be false-positive in cases when we want to avoid complex analysis.
72 : virtual bool blockMayThrow(const BasicBlock *BB) const = 0;
73 :
74 : /// Returns true iff any block of the loop for which this info is contains an
75 : /// instruction that may throw or otherwise exit abnormally.
76 : virtual bool anyBlockMayThrow() const = 0;
77 :
78 : /// Return true if we must reach the block \p BB under assumption that the
79 : /// loop \p CurLoop is entered.
80 : bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB,
81 : const DominatorTree *DT) const;
82 :
83 : /// Computes safety information for a loop checks loop body & header for
84 : /// the possibility of may throw exception, it takes LoopSafetyInfo and loop
85 : /// as argument. Updates safety information in LoopSafetyInfo argument.
86 : /// Note: This is defined to clear and reinitialize an already initialized
87 : /// LoopSafetyInfo. Some callers rely on this fact.
88 : virtual void computeLoopSafetyInfo(const Loop *CurLoop) = 0;
89 :
90 : /// Returns true if the instruction in a loop is guaranteed to execute at
91 : /// least once (under the assumption that the loop is entered).
92 : virtual bool isGuaranteedToExecute(const Instruction &Inst,
93 : const DominatorTree *DT,
94 : const Loop *CurLoop) const = 0;
95 :
96 17538 : LoopSafetyInfo() = default;
97 :
98 16220 : virtual ~LoopSafetyInfo() = default;
99 : };
100 :
101 :
102 : /// Simple and conservative implementation of LoopSafetyInfo that can give
103 : /// false-positive answers to its queries in order to avoid complicated
104 : /// analysis.
105 : class SimpleLoopSafetyInfo: public LoopSafetyInfo {
106 : bool MayThrow = false; // The current loop contains an instruction which
107 : // may throw.
108 : bool HeaderMayThrow = false; // Same as previous, but specific to loop header
109 :
110 : public:
111 : virtual bool blockMayThrow(const BasicBlock *BB) const;
112 :
113 : virtual bool anyBlockMayThrow() const;
114 :
115 : virtual void computeLoopSafetyInfo(const Loop *CurLoop);
116 :
117 : virtual bool isGuaranteedToExecute(const Instruction &Inst,
118 : const DominatorTree *DT,
119 : const Loop *CurLoop) const;
120 :
121 17538 : SimpleLoopSafetyInfo() : LoopSafetyInfo() {};
122 :
123 16153 : virtual ~SimpleLoopSafetyInfo() {};
124 : };
125 :
126 : /// This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to
127 : /// give precise answers on "may throw" queries. This implementation uses cache
128 : /// that should be invalidated by calling the method dropCachedInfo whenever we
129 : /// modify a basic block's contents by adding or removing instructions.
130 : class ICFLoopSafetyInfo: public LoopSafetyInfo {
131 : bool MayThrow = false; // The current loop contains an instruction which
132 : // may throw.
133 : // Contains information about implicit control flow in this loop's blocks.
134 : mutable ImplicitControlFlowTracking ICF;
135 :
136 : public:
137 : virtual bool blockMayThrow(const BasicBlock *BB) const;
138 :
139 : virtual bool anyBlockMayThrow() const;
140 :
141 : virtual void computeLoopSafetyInfo(const Loop *CurLoop);
142 :
143 : virtual bool isGuaranteedToExecute(const Instruction &Inst,
144 : const DominatorTree *DT,
145 : const Loop *CurLoop) const;
146 :
147 : /// Drops cached information regarding the implicit control flow in block
148 : /// \p BB. It should be called for every block in which we add or remove any
149 : /// instructions to a block before we make queries to it.
150 : void dropCachedInfo(const BasicBlock *BB);
151 :
152 : ICFLoopSafetyInfo(DominatorTree *DT) : LoopSafetyInfo(), ICF(DT) {};
153 :
154 0 : virtual ~ICFLoopSafetyInfo() {};
155 : };
156 :
157 : }
158 :
159 : #endif
|
