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"
23 #include "llvm/Analysis/AliasAnalysis.h"
24 #include "llvm/Analysis/DemandedBits.h"
25 #include "llvm/Analysis/EHPersonalities.h"
26 #include "llvm/Analysis/IVDescriptors.h"
27 #include "llvm/Analysis/MustExecute.h"
28 #include "llvm/Analysis/TargetTransformInfo.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 MemorySSAUpdater;
45 class OptimizationRemarkEmitter;
46 class PredicatedScalarEvolution;
47 class PredIteratorCache;
48 class ScalarEvolution;
49 class SCEV;
50 class TargetLibraryInfo;
51 class TargetTransformInfo;
52 
53 BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
54                                    bool PreserveLCSSA);
55 
56 /// Ensure that all exit blocks of the loop are dedicated exits.
57 ///
58 /// For any loop exit block with non-loop predecessors, we split the loop
59 /// predecessors to use a dedicated loop exit block. We update the dominator
60 /// tree and loop info if provided, and will preserve LCSSA if requested.
61 bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
62                              bool PreserveLCSSA);
63 
64 /// Ensures LCSSA form for every instruction from the Worklist in the scope of
65 /// innermost containing loop.
66 ///
67 /// For the given instruction which have uses outside of the loop, an LCSSA PHI
68 /// node is inserted and the uses outside the loop are rewritten to use this
69 /// node.
70 ///
71 /// LoopInfo and DominatorTree are required and, since the routine makes no
72 /// changes to CFG, preserved.
73 ///
74 /// Returns true if any modifications are made.
75 bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
76                               DominatorTree &DT, LoopInfo &LI);
77 
78 /// Put loop into LCSSA form.
79 ///
80 /// Looks at all instructions in the loop which have uses outside of the
81 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
82 /// the loop are rewritten to use this node.
83 ///
84 /// LoopInfo and DominatorTree are required and preserved.
85 ///
86 /// If ScalarEvolution is passed in, it will be preserved.
87 ///
88 /// Returns true if any modifications are made to the loop.
89 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE);
90 
91 /// Put a loop nest into LCSSA form.
92 ///
93 /// This recursively forms LCSSA for a loop nest.
94 ///
95 /// LoopInfo and DominatorTree are required and preserved.
96 ///
97 /// If ScalarEvolution is passed in, it will be preserved.
98 ///
99 /// Returns true if any modifications are made to the loop.
100 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
101                           ScalarEvolution *SE);
102 
103 /// Walk the specified region of the CFG (defined by all blocks
104 /// dominated by the specified block, and that are in the current loop) in
105 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
106 /// uses before definitions, allowing us to sink a loop body in one pass without
107 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
108 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
109 /// instructions of the loop and loop safety information as
110 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
111 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
112                 TargetLibraryInfo *, TargetTransformInfo *, Loop *,
113                 AliasSetTracker *, MemorySSAUpdater *, ICFLoopSafetyInfo *,
114                 OptimizationRemarkEmitter *ORE);
115 
116 /// Walk the specified region of the CFG (defined by all blocks
117 /// dominated by the specified block, and that are in the current loop) in depth
118 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
119 /// before uses, allowing us to hoist a loop body in one pass without iteration.
120 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
121 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
122 /// loop and loop safety information as arguments. Diagnostics is emitted via \p
123 /// ORE. It returns changed status.
124 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
125                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
126                  MemorySSAUpdater *, ICFLoopSafetyInfo *,
127                  OptimizationRemarkEmitter *ORE);
128 
129 /// This function deletes dead loops. The caller of this function needs to
130 /// guarantee that the loop is infact dead.
131 /// The function requires a bunch or prerequisites to be present:
132 ///   - The loop needs to be in LCSSA form
133 ///   - The loop needs to have a Preheader
134 ///   - A unique dedicated exit block must exist
135 ///
136 /// This also updates the relevant analysis information in \p DT, \p SE, and \p
137 /// LI if pointers to those are provided.
138 /// It also updates the loop PM if an updater struct is provided.
139 
140 void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE,
141                     LoopInfo *LI);
142 
143 /// Try to promote memory values to scalars by sinking stores out of
144 /// the loop and moving loads to before the loop.  We do this by looping over
145 /// the stores in the loop, looking for stores to Must pointers which are
146 /// loop invariant. It takes a set of must-alias values, Loop exit blocks
147 /// vector, loop exit blocks insertion point vector, PredIteratorCache,
148 /// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions
149 /// of the loop and loop safety information as arguments.
150 /// Diagnostics is emitted via \p ORE. It returns changed status.
151 bool promoteLoopAccessesToScalars(const SmallSetVector<Value *, 8> &,
152                                   SmallVectorImpl<BasicBlock *> &,
153                                   SmallVectorImpl<Instruction *> &,
154                                   PredIteratorCache &, LoopInfo *,
155                                   DominatorTree *, const TargetLibraryInfo *,
156                                   Loop *, AliasSetTracker *,
157                                   ICFLoopSafetyInfo *,
158                                   OptimizationRemarkEmitter *);
159 
160 /// Does a BFS from a given node to all of its children inside a given loop.
161 /// The returned vector of nodes includes the starting point.
162 SmallVector<DomTreeNode *, 16> collectChildrenInLoop(DomTreeNode *N,
163                                                      const Loop *CurLoop);
164 
165 /// Returns the instructions that use values defined in the loop.
166 SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);
167 
168 /// Find string metadata for loop
169 ///
170 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
171 /// operand or null otherwise.  If the string metadata is not found return
172 /// Optional's not-a-value.
173 Optional<const MDOperand *> findStringMetadataForLoop(const Loop *TheLoop,
174                                                       StringRef Name);
175 
176 /// Find named metadata for a loop with an integer value.
177 llvm::Optional<int> getOptionalIntLoopAttribute(Loop *TheLoop, StringRef Name);
178 
179 /// Create a new loop identifier for a loop created from a loop transformation.
180 ///
181 /// @param OrigLoopID The loop ID of the loop before the transformation.
182 /// @param FollowupAttrs List of attribute names that contain attributes to be
183 ///                      added to the new loop ID.
184 /// @param InheritOptionsAttrsPrefix Selects which attributes should be inherited
185 ///                                  from the original loop. The following values
186 ///                                  are considered:
187 ///        nullptr   : Inherit all attributes from @p OrigLoopID.
188 ///        ""        : Do not inherit any attribute from @p OrigLoopID; only use
189 ///                    those specified by a followup attribute.
190 ///        "<prefix>": Inherit all attributes except those which start with
191 ///                    <prefix>; commonly used to remove metadata for the
192 ///                    applied transformation.
193 /// @param AlwaysNew If true, do not try to reuse OrigLoopID and never return
194 ///                  None.
195 ///
196 /// @return The loop ID for the after-transformation loop. The following values
197 ///         can be returned:
198 ///         None         : No followup attribute was found; it is up to the
199 ///                        transformation to choose attributes that make sense.
200 ///         @p OrigLoopID: The original identifier can be reused.
201 ///         nullptr      : The new loop has no attributes.
202 ///         MDNode*      : A new unique loop identifier.
203 Optional<MDNode *>
204 makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef<StringRef> FollowupAttrs,
205                    const char *InheritOptionsAttrsPrefix = "",
206                    bool AlwaysNew = false);
207 
208 /// Look for the loop attribute that disables all transformation heuristic.
209 bool hasDisableAllTransformsHint(const Loop *L);
210 
211 /// The mode sets how eager a transformation should be applied.
212 enum TransformationMode {
213   /// The pass can use heuristics to determine whether a transformation should
214   /// be applied.
215   TM_Unspecified,
216 
217   /// The transformation should be applied without considering a cost model.
218   TM_Enable,
219 
220   /// The transformation should not be applied.
221   TM_Disable,
222 
223   /// Force is a flag and should not be used alone.
224   TM_Force = 0x04,
225 
226   /// The transformation was directed by the user, e.g. by a #pragma in
227   /// the source code. If the transformation could not be applied, a
228   /// warning should be emitted.
229   TM_ForcedByUser = TM_Enable | TM_Force,
230 
231   /// The transformation must not be applied. For instance, `#pragma clang loop
232   /// unroll(disable)` explicitly forbids any unrolling to take place. Unlike
233   /// general loop metadata, it must not be dropped. Most passes should not
234   /// behave differently under TM_Disable and TM_SuppressedByUser.
235   TM_SuppressedByUser = TM_Disable | TM_Force
236 };
237 
238 /// @{
239 /// Get the mode for LLVM's supported loop transformations.
240 TransformationMode hasUnrollTransformation(Loop *L);
241 TransformationMode hasUnrollAndJamTransformation(Loop *L);
242 TransformationMode hasVectorizeTransformation(Loop *L);
243 TransformationMode hasDistributeTransformation(Loop *L);
244 TransformationMode hasLICMVersioningTransformation(Loop *L);
245 /// @}
246 
247 /// Set input string into loop metadata by keeping other values intact.
248 void addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
249                              unsigned V = 0);
250 
251 /// Get a loop's estimated trip count based on branch weight metadata.
252 /// Returns 0 when the count is estimated to be 0, or None when a meaningful
253 /// estimate can not be made.
254 Optional<unsigned> getLoopEstimatedTripCount(Loop *L);
255 
256 /// Check inner loop (L) backedge count is known to be invariant on all
257 /// iterations of its outer loop. If the loop has no parent, this is trivially
258 /// true.
259 bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE);
260 
261 /// Helper to consistently add the set of standard passes to a loop pass's \c
262 /// AnalysisUsage.
263 ///
264 /// All loop passes should call this as part of implementing their \c
265 /// getAnalysisUsage.
266 void getLoopAnalysisUsage(AnalysisUsage &AU);
267 
268 /// Returns true if is legal to hoist or sink this instruction disregarding the
269 /// possible introduction of faults.  Reasoning about potential faulting
270 /// instructions is the responsibility of the caller since it is challenging to
271 /// do efficiently from within this routine.
272 /// \p TargetExecutesOncePerLoop is true only when it is guaranteed that the
273 /// target executes at most once per execution of the loop body.  This is used
274 /// to assess the legality of duplicating atomic loads.  Generally, this is
275 /// true when moving out of loop and not true when moving into loops.
276 /// If \p ORE is set use it to emit optimization remarks.
277 bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
278                         Loop *CurLoop, AliasSetTracker *CurAST,
279                         MemorySSAUpdater *MSSAU, bool TargetExecutesOncePerLoop,
280                         OptimizationRemarkEmitter *ORE = nullptr);
281 
282 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
283 Value *createMinMaxOp(IRBuilder<> &Builder,
284                       RecurrenceDescriptor::MinMaxRecurrenceKind RK,
285                       Value *Left, Value *Right);
286 
287 /// Generates an ordered vector reduction using extracts to reduce the value.
288 Value *
289 getOrderedReduction(IRBuilder<> &Builder, Value *Acc, Value *Src, unsigned Op,
290                     RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind =
291                         RecurrenceDescriptor::MRK_Invalid,
292                     ArrayRef<Value *> RedOps = None);
293 
294 /// Generates a vector reduction using shufflevectors to reduce the value.
295 Value *getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op,
296                            RecurrenceDescriptor::MinMaxRecurrenceKind
297                                MinMaxKind = RecurrenceDescriptor::MRK_Invalid,
298                            ArrayRef<Value *> RedOps = None);
299 
300 /// Create a target reduction of the given vector. The reduction operation
301 /// is described by the \p Opcode parameter. min/max reductions require
302 /// additional information supplied in \p Flags.
303 /// The target is queried to determine if intrinsics or shuffle sequences are
304 /// required to implement the reduction.
305 Value *createSimpleTargetReduction(IRBuilder<> &B,
306                                    const TargetTransformInfo *TTI,
307                                    unsigned Opcode, Value *Src,
308                                    TargetTransformInfo::ReductionFlags Flags =
309                                        TargetTransformInfo::ReductionFlags(),
310                                    ArrayRef<Value *> RedOps = None);
311 
312 /// Create a generic target reduction using a recurrence descriptor \p Desc
313 /// The target is queried to determine if intrinsics or shuffle sequences are
314 /// required to implement the reduction.
315 Value *createTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI,
316                              RecurrenceDescriptor &Desc, Value *Src,
317                              bool NoNaN = false);
318 
319 /// Get the intersection (logical and) of all of the potential IR flags
320 /// of each scalar operation (VL) that will be converted into a vector (I).
321 /// If OpValue is non-null, we only consider operations similar to OpValue
322 /// when intersecting.
323 /// Flag set: NSW, NUW, exact, and all of fast-math.
324 void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr);
325 
326 /// Returns true if we can prove that \p S is defined and always negative in
327 /// loop \p L.
328 bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE);
329 
330 /// Returns true if we can prove that \p S is defined and always non-negative in
331 /// loop \p L.
332 bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,
333                               ScalarEvolution &SE);
334 
335 /// Returns true if \p S is defined and never is equal to signed/unsigned max.
336 bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
337                        bool Signed);
338 
339 /// Returns true if \p S is defined and never is equal to signed/unsigned min.
340 bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
341                        bool Signed);
342 
343 } // end namespace llvm
344 
345 #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
346