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