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