LLVM  8.0.0svn
LoopUtils.h
Go to the documentation of this file.
1 //===- llvm/Transforms/Utils/LoopUtils.h - Loop utilities -------*- 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 //
10 // This file defines some loop transformation utilities.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
15 #define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
16 
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/Optional.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/StringRef.h"
29 #include "llvm/IR/Dominators.h"
30 #include "llvm/IR/IRBuilder.h"
31 #include "llvm/IR/InstrTypes.h"
32 #include "llvm/IR/Operator.h"
33 #include "llvm/IR/ValueHandle.h"
34 #include "llvm/Support/Casting.h"
35 
36 namespace llvm {
37 
38 class AliasSet;
39 class AliasSetTracker;
40 class BasicBlock;
41 class DataLayout;
42 class Loop;
43 class LoopInfo;
44 class OptimizationRemarkEmitter;
45 class PredicatedScalarEvolution;
46 class PredIteratorCache;
47 class ScalarEvolution;
48 class SCEV;
49 class TargetLibraryInfo;
50 class TargetTransformInfo;
51 
52 BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
53  bool PreserveLCSSA);
54 
55 /// Ensure that all exit blocks of the loop are dedicated exits.
56 ///
57 /// For any loop exit block with non-loop predecessors, we split the loop
58 /// predecessors to use a dedicated loop exit block. We update the dominator
59 /// tree and loop info if provided, and will preserve LCSSA if requested.
60 bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
61  bool PreserveLCSSA);
62 
63 /// Ensures LCSSA form for every instruction from the Worklist in the scope of
64 /// innermost containing loop.
65 ///
66 /// For the given instruction which have uses outside of the loop, an LCSSA PHI
67 /// node is inserted and the uses outside the loop are rewritten to use this
68 /// node.
69 ///
70 /// LoopInfo and DominatorTree are required and, since the routine makes no
71 /// changes to CFG, preserved.
72 ///
73 /// Returns true if any modifications are made.
74 bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
75  DominatorTree &DT, LoopInfo &LI);
76 
77 /// Put loop into LCSSA form.
78 ///
79 /// Looks at all instructions in the loop which have uses outside of the
80 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
81 /// the loop are rewritten to use this node.
82 ///
83 /// LoopInfo and DominatorTree are required and preserved.
84 ///
85 /// If ScalarEvolution is passed in, it will be preserved.
86 ///
87 /// Returns true if any modifications are made to the loop.
88 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE);
89 
90 /// Put a loop nest into LCSSA form.
91 ///
92 /// This recursively forms LCSSA for a loop nest.
93 ///
94 /// LoopInfo and DominatorTree are required and preserved.
95 ///
96 /// If ScalarEvolution is passed in, it will be preserved.
97 ///
98 /// Returns true if any modifications are made to the loop.
99 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
100  ScalarEvolution *SE);
101 
102 /// Walk the specified region of the CFG (defined by all blocks
103 /// dominated by the specified block, and that are in the current loop) in
104 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
105 /// uses before definitions, allowing us to sink a loop body in one pass without
106 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
107 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
108 /// instructions of the loop and loop safety information as
109 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
110 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
111  TargetLibraryInfo *, TargetTransformInfo *, Loop *,
112  AliasSetTracker *, LoopSafetyInfo *,
113  OptimizationRemarkEmitter *ORE);
114 
115 /// Walk the specified region of the CFG (defined by all blocks
116 /// dominated by the specified block, and that are in the current loop) in depth
117 /// first order w.r.t the DominatorTree. This allows us to visit definitions
118 /// before uses, allowing us to hoist a loop body in one pass without iteration.
119 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
120 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
121 /// loop and loop safety information as arguments. Diagnostics is emitted via \p
122 /// ORE. It returns changed status.
123 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
124  TargetLibraryInfo *, Loop *, AliasSetTracker *,
125  LoopSafetyInfo *, OptimizationRemarkEmitter *ORE);
126 
127 /// This function deletes dead loops. The caller of this function needs to
128 /// guarantee that the loop is infact dead.
129 /// The function requires a bunch or prerequisites to be present:
130 /// - The loop needs to be in LCSSA form
131 /// - The loop needs to have a Preheader
132 /// - A unique dedicated exit block must exist
133 ///
134 /// This also updates the relevant analysis information in \p DT, \p SE, and \p
135 /// LI if pointers to those are provided.
136 /// It also updates the loop PM if an updater struct is provided.
137 
138 void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE,
139  LoopInfo *LI);
140 
141 /// Try to promote memory values to scalars by sinking stores out of
142 /// the loop and moving loads to before the loop. We do this by looping over
143 /// the stores in the loop, looking for stores to Must pointers which are
144 /// loop invariant. It takes a set of must-alias values, Loop exit blocks
145 /// vector, loop exit blocks insertion point vector, PredIteratorCache,
146 /// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions
147 /// of the loop and loop safety information as arguments.
148 /// Diagnostics is emitted via \p ORE. It returns changed status.
149 bool promoteLoopAccessesToScalars(const SmallSetVector<Value *, 8> &,
150  SmallVectorImpl<BasicBlock *> &,
151  SmallVectorImpl<Instruction *> &,
152  PredIteratorCache &, LoopInfo *,
153  DominatorTree *, const TargetLibraryInfo *,
154  Loop *, AliasSetTracker *, LoopSafetyInfo *,
155  OptimizationRemarkEmitter *);
156 
157 /// Does a BFS from a given node to all of its children inside a given loop.
158 /// The returned vector of nodes includes the starting point.
159 SmallVector<DomTreeNode *, 16> collectChildrenInLoop(DomTreeNode *N,
160  const Loop *CurLoop);
161 
162 /// Returns the instructions that use values defined in the loop.
163 SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);
164 
165 /// Find string metadata for loop
166 ///
167 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
168 /// operand or null otherwise. If the string metadata is not found return
169 /// Optional's not-a-value.
170 Optional<const MDOperand *> findStringMetadataForLoop(Loop *TheLoop,
171  StringRef Name);
172 
173 /// Set input string into loop metadata by keeping other values intact.
174 void addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
175  unsigned V = 0);
176 
177 /// Get a loop's estimated trip count based on branch weight metadata.
178 /// Returns 0 when the count is estimated to be 0, or None when a meaningful
179 /// estimate can not be made.
180 Optional<unsigned> getLoopEstimatedTripCount(Loop *L);
181 
182 /// Check inner loop (L) backedge count is known to be invariant on all
183 /// iterations of its outer loop. If the loop has no parent, this is trivially
184 /// true.
185 bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE);
186 
187 /// Helper to consistently add the set of standard passes to a loop pass's \c
188 /// AnalysisUsage.
189 ///
190 /// All loop passes should call this as part of implementing their \c
191 /// getAnalysisUsage.
192 void getLoopAnalysisUsage(AnalysisUsage &AU);
193 
194 /// Returns true if is legal to hoist or sink this instruction disregarding the
195 /// possible introduction of faults. Reasoning about potential faulting
196 /// instructions is the responsibility of the caller since it is challenging to
197 /// do efficiently from within this routine.
198 /// \p TargetExecutesOncePerLoop is true only when it is guaranteed that the
199 /// target executes at most once per execution of the loop body. This is used
200 /// to assess the legality of duplicating atomic loads. Generally, this is
201 /// true when moving out of loop and not true when moving into loops.
202 /// If \p ORE is set use it to emit optimization remarks.
203 bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
204  Loop *CurLoop, AliasSetTracker *CurAST,
205  bool TargetExecutesOncePerLoop,
206  OptimizationRemarkEmitter *ORE = nullptr);
207 
208 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
209 Value *createMinMaxOp(IRBuilder<> &Builder,
211  Value *Left, Value *Right);
212 
213 /// Generates an ordered vector reduction using extracts to reduce the value.
214 Value *
215 getOrderedReduction(IRBuilder<> &Builder, Value *Acc, Value *Src, unsigned Op,
218  ArrayRef<Value *> RedOps = None);
219 
220 /// Generates a vector reduction using shufflevectors to reduce the value.
221 Value *getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op,
224  ArrayRef<Value *> RedOps = None);
225 
226 /// Create a target reduction of the given vector. The reduction operation
227 /// is described by the \p Opcode parameter. min/max reductions require
228 /// additional information supplied in \p Flags.
229 /// The target is queried to determine if intrinsics or shuffle sequences are
230 /// required to implement the reduction.
231 Value *createSimpleTargetReduction(IRBuilder<> &B,
232  const TargetTransformInfo *TTI,
233  unsigned Opcode, Value *Src,
234  TargetTransformInfo::ReductionFlags Flags =
235  TargetTransformInfo::ReductionFlags(),
236  ArrayRef<Value *> RedOps = None);
237 
238 /// Create a generic target reduction using a recurrence descriptor \p Desc
239 /// The target is queried to determine if intrinsics or shuffle sequences are
240 /// required to implement the reduction.
241 Value *createTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI,
242  RecurrenceDescriptor &Desc, Value *Src,
243  bool NoNaN = false);
244 
245 /// Get the intersection (logical and) of all of the potential IR flags
246 /// of each scalar operation (VL) that will be converted into a vector (I).
247 /// If OpValue is non-null, we only consider operations similar to OpValue
248 /// when intersecting.
249 /// Flag set: NSW, NUW, exact, and all of fast-math.
250 void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr);
251 
252 } // end namespace llvm
253 
254 #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
const NoneType None
Definition: None.h:24
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Various leaf nodes.
Definition: ISDOpcodes.h:60
BasicBlock * InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA)
InsertPreheaderForLoop - Once we discover that a loop doesn&#39;t have a preheader, this method is called...
Value * createSimpleTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, unsigned Opcode, Value *Src, TargetTransformInfo::ReductionFlags Flags=TargetTransformInfo::ReductionFlags(), ArrayRef< Value *> RedOps=None)
Create a target reduction of the given vector.
Definition: LoopUtils.cpp:577
bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, AliasSetTracker *CurAST, bool TargetExecutesOncePerLoop, OptimizationRemarkEmitter *ORE=nullptr)
Returns true if is legal to hoist or sink this instruction disregarding the possible introduction of ...
Definition: LICM.cpp:629
bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE)
Check inner loop (L) backedge count is known to be invariant on all iterations of its outer loop...
Definition: LoopUtils.cpp:425
Value * getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op, RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind=RecurrenceDescriptor::MRK_Invalid, ArrayRef< Value *> RedOps=None)
Generates a vector reduction using shufflevectors to reduce the value.
Definition: LoopUtils.cpp:535
bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:360
amdgpu Simplify well known AMD library false Value Value const Twine & Name
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
Definition: LoopUtils.cpp:110
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI)
This function deletes dead loops.
Definition: LoopUtils.cpp:245
Value * getOrderedReduction(IRBuilder<> &Builder, Value *Acc, Value *Src, unsigned Op, RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind=RecurrenceDescriptor::MRK_Invalid, ArrayRef< Value *> RedOps=None)
Generates an ordered vector reduction using extracts to reduce the value.
Definition: LoopUtils.cpp:504
bool promoteLoopAccessesToScalars(const SmallSetVector< Value *, 8 > &, SmallVectorImpl< BasicBlock *> &, SmallVectorImpl< Instruction *> &, PredIteratorCache &, LoopInfo *, DominatorTree *, const TargetLibraryInfo *, Loop *, AliasSetTracker *, LoopSafetyInfo *, OptimizationRemarkEmitter *)
Try to promote memory values to scalars by sinking stores out of the loop and moving loads to before ...
Definition: LICM.cpp:1275
void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
bool formLCSSAForInstructions(SmallVectorImpl< Instruction *> &Worklist, DominatorTree &DT, LoopInfo &LI)
Ensures LCSSA form for every instruction from the Worklist in the scope of innermost containing loop...
Definition: LCSSA.cpp:75
AAResults AliasAnalysis
Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, TargetTransformInfo *, Loop *, AliasSetTracker *, LoopSafetyInfo *, OptimizationRemarkEmitter *ORE)
Walk the specified region of the CFG (defined by all blocks dominated by the specified block...
Definition: LICM.cpp:374
Value * createMinMaxOp(IRBuilder<> &Builder, RecurrenceDescriptor::MinMaxRecurrenceKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
Definition: LoopUtils.cpp:457
Optional< unsigned > getLoopEstimatedTripCount(Loop *L)
Get a loop&#39;s estimated trip count based on branch weight metadata.
Definition: LoopUtils.cpp:392
Optional< const MDOperand * > findStringMetadataForLoop(Loop *TheLoop, StringRef Name)
Find string metadata for loop.
Definition: LoopUtils.cpp:191
void propagateIRFlags(Value *I, ArrayRef< Value *> VL, Value *OpValue=nullptr)
Get the intersection (logical and) of all of the potential IR flags of each scalar operation (VL) tha...
Definition: LoopUtils.cpp:692
bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Definition: LCSSA.cpp:305
bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, LoopSafetyInfo *, OptimizationRemarkEmitter *ORE)
Walk the specified region of the CFG (defined by all blocks dominated by the specified block...
Definition: LICM.cpp:441
Value * createTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, RecurrenceDescriptor &Desc, Value *Src, bool NoNaN=false)
Create a generic target reduction using a recurrence descriptor Desc The target is queried to determi...
Definition: LoopUtils.cpp:653
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:128
SmallVector< DomTreeNode *, 16 > collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop)
Does a BFS from a given node to all of its children inside a given loop.
Definition: LoopUtils.cpp:227
DomTreeNodeBase< BasicBlock > DomTreeNode
Definition: Dominators.h:75
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
Definition: LoopUtils.cpp:45
This pass exposes codegen information to IR-level passes.