/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/Transforms/Utils/LoopUtils.h
Line | Count | Source (jump to first uncovered line) |
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/EHPersonalities.h" |
25 | | #include "llvm/Analysis/TargetTransformInfo.h" |
26 | | #include "llvm/IR/Dominators.h" |
27 | | #include "llvm/IR/IRBuilder.h" |
28 | | #include "llvm/IR/InstrTypes.h" |
29 | | #include "llvm/IR/Operator.h" |
30 | | #include "llvm/IR/ValueHandle.h" |
31 | | #include "llvm/Support/Casting.h" |
32 | | |
33 | | namespace llvm { |
34 | | |
35 | | class AliasSet; |
36 | | class AliasSetTracker; |
37 | | class BasicBlock; |
38 | | class DataLayout; |
39 | | class Loop; |
40 | | class LoopInfo; |
41 | | class OptimizationRemarkEmitter; |
42 | | class PredicatedScalarEvolution; |
43 | | class PredIteratorCache; |
44 | | class ScalarEvolution; |
45 | | class SCEV; |
46 | | class TargetLibraryInfo; |
47 | | class TargetTransformInfo; |
48 | | |
49 | | /// \brief Captures loop safety information. |
50 | | /// It keep information for loop & its header may throw exception. |
51 | | struct LoopSafetyInfo { |
52 | | bool MayThrow = false; // The current loop contains an instruction which |
53 | | // may throw. |
54 | | bool HeaderMayThrow = false; // Same as previous, but specific to loop header |
55 | | // Used to update funclet bundle operands. |
56 | | DenseMap<BasicBlock *, ColorVector> BlockColors; |
57 | | |
58 | 1.18M | LoopSafetyInfo() = default; |
59 | | }; |
60 | | |
61 | | /// The RecurrenceDescriptor is used to identify recurrences variables in a |
62 | | /// loop. Reduction is a special case of recurrence that has uses of the |
63 | | /// recurrence variable outside the loop. The method isReductionPHI identifies |
64 | | /// reductions that are basic recurrences. |
65 | | /// |
66 | | /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min, |
67 | | /// or max of a set of terms. For example: for(i=0; i<n; i++) { total += |
68 | | /// array[i]; } is a summation of array elements. Basic recurrences are a |
69 | | /// special case of chains of recurrences (CR). See ScalarEvolution for CR |
70 | | /// references. |
71 | | |
72 | | /// This struct holds information about recurrence variables. |
73 | | class RecurrenceDescriptor { |
74 | | public: |
75 | | /// This enum represents the kinds of recurrences that we support. |
76 | | enum RecurrenceKind { |
77 | | RK_NoRecurrence, ///< Not a recurrence. |
78 | | RK_IntegerAdd, ///< Sum of integers. |
79 | | RK_IntegerMult, ///< Product of integers. |
80 | | RK_IntegerOr, ///< Bitwise or logical OR of numbers. |
81 | | RK_IntegerAnd, ///< Bitwise or logical AND of numbers. |
82 | | RK_IntegerXor, ///< Bitwise or logical XOR of numbers. |
83 | | RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()). |
84 | | RK_FloatAdd, ///< Sum of floats. |
85 | | RK_FloatMult, ///< Product of floats. |
86 | | RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()). |
87 | | }; |
88 | | |
89 | | // This enum represents the kind of minmax recurrence. |
90 | | enum MinMaxRecurrenceKind { |
91 | | MRK_Invalid, |
92 | | MRK_UIntMin, |
93 | | MRK_UIntMax, |
94 | | MRK_SIntMin, |
95 | | MRK_SIntMax, |
96 | | MRK_FloatMin, |
97 | | MRK_FloatMax |
98 | | }; |
99 | | |
100 | 192k | RecurrenceDescriptor() = default; |
101 | | |
102 | | RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K, |
103 | | MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT, |
104 | | bool Signed, SmallPtrSetImpl<Instruction *> &CI) |
105 | | : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK), |
106 | 13.3k | UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) { |
107 | 13.3k | CastInsts.insert(CI.begin(), CI.end()); |
108 | 13.3k | } |
109 | | |
110 | | /// This POD struct holds information about a potential recurrence operation. |
111 | | class InstDesc { |
112 | | public: |
113 | | InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr) |
114 | | : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid), |
115 | 4.51M | UnsafeAlgebraInst(UAI) {} |
116 | | |
117 | | InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr) |
118 | | : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K), |
119 | 2.95k | UnsafeAlgebraInst(UAI) {} |
120 | | |
121 | 649k | bool isRecurrence() { return IsRecurrence; } |
122 | | |
123 | 0 | bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; } |
124 | | |
125 | 662k | Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; } |
126 | | |
127 | 14.4k | MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; } |
128 | | |
129 | 0 | Instruction *getPatternInst() { return PatternLastInst; } |
130 | | |
131 | | private: |
132 | | // Is this instruction a recurrence candidate. |
133 | | bool IsRecurrence; |
134 | | // The last instruction in a min/max pattern (select of the select(icmp()) |
135 | | // pattern), or the current recurrence instruction otherwise. |
136 | | Instruction *PatternLastInst; |
137 | | // If this is a min/max pattern the comparison predicate. |
138 | | MinMaxRecurrenceKind MinMaxKind; |
139 | | // Recurrence has unsafe algebra. |
140 | | Instruction *UnsafeAlgebraInst; |
141 | | }; |
142 | | |
143 | | /// Returns a struct describing if the instruction 'I' can be a recurrence |
144 | | /// variable of type 'Kind'. If the recurrence is a min/max pattern of |
145 | | /// select(icmp()) this function advances the instruction pointer 'I' from the |
146 | | /// compare instruction to the select instruction and stores this pointer in |
147 | | /// 'PatternLastInst' member of the returned struct. |
148 | | static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind, |
149 | | InstDesc &Prev, bool HasFunNoNaNAttr); |
150 | | |
151 | | /// Returns true if instruction I has multiple uses in Insts |
152 | | static bool hasMultipleUsesOf(Instruction *I, |
153 | | SmallPtrSetImpl<Instruction *> &Insts); |
154 | | |
155 | | /// Returns true if all uses of the instruction I is within the Set. |
156 | | static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set); |
157 | | |
158 | | /// Returns a struct describing if the instruction if the instruction is a |
159 | | /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y) |
160 | | /// or max(X, Y). |
161 | | static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev); |
162 | | |
163 | | /// Returns identity corresponding to the RecurrenceKind. |
164 | | static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp); |
165 | | |
166 | | /// Returns the opcode of binary operation corresponding to the |
167 | | /// RecurrenceKind. |
168 | | static unsigned getRecurrenceBinOp(RecurrenceKind Kind); |
169 | | |
170 | | /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind. |
171 | | static Value *createMinMaxOp(IRBuilder<> &Builder, MinMaxRecurrenceKind RK, |
172 | | Value *Left, Value *Right); |
173 | | |
174 | | /// Returns true if Phi is a reduction of type Kind and adds it to the |
175 | | /// RecurrenceDescriptor. |
176 | | static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop, |
177 | | bool HasFunNoNaNAttr, |
178 | | RecurrenceDescriptor &RedDes); |
179 | | |
180 | | /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor is |
181 | | /// returned in RedDes. |
182 | | static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, |
183 | | RecurrenceDescriptor &RedDes); |
184 | | |
185 | | /// Returns true if Phi is a first-order recurrence. A first-order recurrence |
186 | | /// is a non-reduction recurrence relation in which the value of the |
187 | | /// recurrence in the current loop iteration equals a value defined in the |
188 | | /// previous iteration. \p SinkAfter includes pairs of instructions where the |
189 | | /// first will be rescheduled to appear after the second if/when the loop is |
190 | | /// vectorized. It may be augmented with additional pairs if needed in order |
191 | | /// to handle Phi as a first-order recurrence. |
192 | | static bool |
193 | | isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop, |
194 | | DenseMap<Instruction *, Instruction *> &SinkAfter, |
195 | | DominatorTree *DT); |
196 | | |
197 | 2.67k | RecurrenceKind getRecurrenceKind() { return Kind; } |
198 | | |
199 | 1.57k | MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; } |
200 | | |
201 | 1.51k | TrackingVH<Value> getRecurrenceStartValue() { return StartValue; } |
202 | | |
203 | 14.8k | Instruction *getLoopExitInstr() { return LoopExitInstr; } |
204 | | |
205 | | /// Returns true if the recurrence has unsafe algebra which requires a relaxed |
206 | | /// floating-point model. |
207 | 13.3k | bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; } |
208 | | |
209 | | /// Returns first unsafe algebra instruction in the PHI node's use-chain. |
210 | 2.51k | Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; } |
211 | | |
212 | | /// Returns true if the recurrence kind is an integer kind. |
213 | | static bool isIntegerRecurrenceKind(RecurrenceKind Kind); |
214 | | |
215 | | /// Returns true if the recurrence kind is a floating point kind. |
216 | | static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind); |
217 | | |
218 | | /// Returns true if the recurrence kind is an arithmetic kind. |
219 | | static bool isArithmeticRecurrenceKind(RecurrenceKind Kind); |
220 | | |
221 | | /// Determines if Phi may have been type-promoted. If Phi has a single user |
222 | | /// that ANDs the Phi with a type mask, return the user. RT is updated to |
223 | | /// account for the narrower bit width represented by the mask, and the AND |
224 | | /// instruction is added to CI. |
225 | | static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT, |
226 | | SmallPtrSetImpl<Instruction *> &Visited, |
227 | | SmallPtrSetImpl<Instruction *> &CI); |
228 | | |
229 | | /// Returns true if all the source operands of a recurrence are either |
230 | | /// SExtInsts or ZExtInsts. This function is intended to be used with |
231 | | /// lookThroughAnd to determine if the recurrence has been type-promoted. The |
232 | | /// source operands are added to CI, and IsSigned is updated to indicate if |
233 | | /// all source operands are SExtInsts. |
234 | | static bool getSourceExtensionKind(Instruction *Start, Instruction *Exit, |
235 | | Type *RT, bool &IsSigned, |
236 | | SmallPtrSetImpl<Instruction *> &Visited, |
237 | | SmallPtrSetImpl<Instruction *> &CI); |
238 | | |
239 | | /// Returns the type of the recurrence. This type can be narrower than the |
240 | | /// actual type of the Phi if the recurrence has been type-promoted. |
241 | 6.66k | Type *getRecurrenceType() { return RecurrenceType; } |
242 | | |
243 | | /// Returns a reference to the instructions used for type-promoting the |
244 | | /// recurrence. |
245 | 4.33k | SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; } |
246 | | |
247 | | /// Returns true if all source operands of the recurrence are SExtInsts. |
248 | 6 | bool isSigned() { return IsSigned; } |
249 | | |
250 | | private: |
251 | | // The starting value of the recurrence. |
252 | | // It does not have to be zero! |
253 | | TrackingVH<Value> StartValue; |
254 | | // The instruction who's value is used outside the loop. |
255 | | Instruction *LoopExitInstr = nullptr; |
256 | | // The kind of the recurrence. |
257 | | RecurrenceKind Kind = RK_NoRecurrence; |
258 | | // If this a min/max recurrence the kind of recurrence. |
259 | | MinMaxRecurrenceKind MinMaxKind = MRK_Invalid; |
260 | | // First occurrence of unasfe algebra in the PHI's use-chain. |
261 | | Instruction *UnsafeAlgebraInst = nullptr; |
262 | | // The type of the recurrence. |
263 | | Type *RecurrenceType = nullptr; |
264 | | // True if all source operands of the recurrence are SExtInsts. |
265 | | bool IsSigned = false; |
266 | | // Instructions used for type-promoting the recurrence. |
267 | | SmallPtrSet<Instruction *, 8> CastInsts; |
268 | | }; |
269 | | |
270 | | /// A struct for saving information about induction variables. |
271 | | class InductionDescriptor { |
272 | | public: |
273 | | /// This enum represents the kinds of inductions that we support. |
274 | | enum InductionKind { |
275 | | IK_NoInduction, ///< Not an induction variable. |
276 | | IK_IntInduction, ///< Integer induction variable. Step = C. |
277 | | IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem). |
278 | | IK_FpInduction ///< Floating point induction variable. |
279 | | }; |
280 | | |
281 | | public: |
282 | | /// Default constructor - creates an invalid induction. |
283 | 282k | InductionDescriptor() = default; |
284 | | |
285 | | /// Get the consecutive direction. Returns: |
286 | | /// 0 - unknown or non-consecutive. |
287 | | /// 1 - consecutive and increasing. |
288 | | /// -1 - consecutive and decreasing. |
289 | | int getConsecutiveDirection() const; |
290 | | |
291 | | /// Compute the transformed value of Index at offset StartValue using step |
292 | | /// StepValue. |
293 | | /// For integer induction, returns StartValue + Index * StepValue. |
294 | | /// For pointer induction, returns StartValue[Index * StepValue]. |
295 | | /// FIXME: The newly created binary instructions should contain nsw/nuw |
296 | | /// flags, which can be found from the original scalar operations. |
297 | | Value *transform(IRBuilder<> &B, Value *Index, ScalarEvolution *SE, |
298 | | const DataLayout& DL) const; |
299 | | |
300 | 196k | Value *getStartValue() const { return StartValue; } |
301 | 310k | InductionKind getKind() const { return IK; } |
302 | 65.0k | const SCEV *getStep() const { return Step; } |
303 | | ConstantInt *getConstIntStepValue() const; |
304 | | |
305 | | /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an |
306 | | /// induction, the induction descriptor \p D will contain the data describing |
307 | | /// this induction. If by some other means the caller has a better SCEV |
308 | | /// expression for \p Phi than the one returned by the ScalarEvolution |
309 | | /// analysis, it can be passed through \p Expr. |
310 | | static bool isInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE, |
311 | | InductionDescriptor &D, |
312 | | const SCEV *Expr = nullptr); |
313 | | |
314 | | /// Returns true if \p Phi is a floating point induction in the loop \p L. |
315 | | /// If \p Phi is an induction, the induction descriptor \p D will contain |
316 | | /// the data describing this induction. |
317 | | static bool isFPInductionPHI(PHINode *Phi, const Loop* L, |
318 | | ScalarEvolution *SE, InductionDescriptor &D); |
319 | | |
320 | | /// Returns true if \p Phi is a loop \p L induction, in the context associated |
321 | | /// with the run-time predicate of PSE. If \p Assume is true, this can add |
322 | | /// further SCEV predicates to \p PSE in order to prove that \p Phi is an |
323 | | /// induction. |
324 | | /// If \p Phi is an induction, \p D will contain the data describing this |
325 | | /// induction. |
326 | | static bool isInductionPHI(PHINode *Phi, const Loop* L, |
327 | | PredicatedScalarEvolution &PSE, |
328 | | InductionDescriptor &D, bool Assume = false); |
329 | | |
330 | | /// Returns true if the induction type is FP and the binary operator does |
331 | | /// not have the "fast-math" property. Such operation requires a relaxed FP |
332 | | /// mode. |
333 | 108k | bool hasUnsafeAlgebra() { |
334 | 108k | return InductionBinOp && |
335 | 88 | !cast<FPMathOperator>(InductionBinOp)->hasUnsafeAlgebra(); |
336 | 108k | } |
337 | | |
338 | | /// Returns induction operator that does not have "fast-math" property |
339 | | /// and requires FP unsafe mode. |
340 | 62 | Instruction *getUnsafeAlgebraInst() { |
341 | 62 | if (!InductionBinOp || |
342 | 62 | cast<FPMathOperator>(InductionBinOp)->hasUnsafeAlgebra()) |
343 | 0 | return nullptr; |
344 | 62 | return InductionBinOp; |
345 | 62 | } |
346 | | |
347 | | /// Returns binary opcode of the induction operator. |
348 | 42.2k | Instruction::BinaryOps getInductionOpcode() const { |
349 | 55 | return InductionBinOp ? InductionBinOp->getOpcode() : |
350 | 42.1k | Instruction::BinaryOpsEnd; |
351 | 42.2k | } |
352 | | |
353 | | private: |
354 | | /// Private constructor - used by \c isInductionPHI. |
355 | | InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step, |
356 | | BinaryOperator *InductionBinOp = nullptr); |
357 | | |
358 | | /// Start value. |
359 | | TrackingVH<Value> StartValue; |
360 | | /// Induction kind. |
361 | | InductionKind IK = IK_NoInduction; |
362 | | /// Step value. |
363 | | const SCEV *Step = nullptr; |
364 | | // Instruction that advances induction variable. |
365 | | BinaryOperator *InductionBinOp = nullptr; |
366 | | }; |
367 | | |
368 | | BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, |
369 | | bool PreserveLCSSA); |
370 | | |
371 | | /// Ensure that all exit blocks of the loop are dedicated exits. |
372 | | /// |
373 | | /// For any loop exit block with non-loop predecessors, we split the loop |
374 | | /// predecessors to use a dedicated loop exit block. We update the dominator |
375 | | /// tree and loop info if provided, and will preserve LCSSA if requested. |
376 | | bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, |
377 | | bool PreserveLCSSA); |
378 | | |
379 | | /// Ensures LCSSA form for every instruction from the Worklist in the scope of |
380 | | /// innermost containing loop. |
381 | | /// |
382 | | /// For the given instruction which have uses outside of the loop, an LCSSA PHI |
383 | | /// node is inserted and the uses outside the loop are rewritten to use this |
384 | | /// node. |
385 | | /// |
386 | | /// LoopInfo and DominatorTree are required and, since the routine makes no |
387 | | /// changes to CFG, preserved. |
388 | | /// |
389 | | /// Returns true if any modifications are made. |
390 | | bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist, |
391 | | DominatorTree &DT, LoopInfo &LI); |
392 | | |
393 | | /// \brief Put loop into LCSSA form. |
394 | | /// |
395 | | /// Looks at all instructions in the loop which have uses outside of the |
396 | | /// current loop. For each, an LCSSA PHI node is inserted and the uses outside |
397 | | /// the loop are rewritten to use this node. |
398 | | /// |
399 | | /// LoopInfo and DominatorTree are required and preserved. |
400 | | /// |
401 | | /// If ScalarEvolution is passed in, it will be preserved. |
402 | | /// |
403 | | /// Returns true if any modifications are made to the loop. |
404 | | bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE); |
405 | | |
406 | | /// \brief Put a loop nest into LCSSA form. |
407 | | /// |
408 | | /// This recursively forms LCSSA for a loop nest. |
409 | | /// |
410 | | /// LoopInfo and DominatorTree are required and preserved. |
411 | | /// |
412 | | /// If ScalarEvolution is passed in, it will be preserved. |
413 | | /// |
414 | | /// Returns true if any modifications are made to the loop. |
415 | | bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, |
416 | | ScalarEvolution *SE); |
417 | | |
418 | | /// \brief Walk the specified region of the CFG (defined by all blocks |
419 | | /// dominated by the specified block, and that are in the current loop) in |
420 | | /// reverse depth first order w.r.t the DominatorTree. This allows us to visit |
421 | | /// uses before definitions, allowing us to sink a loop body in one pass without |
422 | | /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, |
423 | | /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all |
424 | | /// instructions of the loop and loop safety information as |
425 | | /// arguments. Diagnostics is emitted via \p ORE. It returns changed status. |
426 | | bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, |
427 | | TargetLibraryInfo *, Loop *, AliasSetTracker *, |
428 | | LoopSafetyInfo *, OptimizationRemarkEmitter *ORE); |
429 | | |
430 | | /// \brief Walk the specified region of the CFG (defined by all blocks |
431 | | /// dominated by the specified block, and that are in the current loop) in depth |
432 | | /// first order w.r.t the DominatorTree. This allows us to visit definitions |
433 | | /// before uses, allowing us to hoist a loop body in one pass without iteration. |
434 | | /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout, |
435 | | /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the |
436 | | /// loop and loop safety information as arguments. Diagnostics is emitted via \p |
437 | | /// ORE. It returns changed status. |
438 | | bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, |
439 | | TargetLibraryInfo *, Loop *, AliasSetTracker *, |
440 | | LoopSafetyInfo *, OptimizationRemarkEmitter *ORE); |
441 | | |
442 | | /// \brief Try to promote memory values to scalars by sinking stores out of |
443 | | /// the loop and moving loads to before the loop. We do this by looping over |
444 | | /// the stores in the loop, looking for stores to Must pointers which are |
445 | | /// loop invariant. It takes a set of must-alias values, Loop exit blocks |
446 | | /// vector, loop exit blocks insertion point vector, PredIteratorCache, |
447 | | /// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions |
448 | | /// of the loop and loop safety information as arguments. |
449 | | /// Diagnostics is emitted via \p ORE. It returns changed status. |
450 | | bool promoteLoopAccessesToScalars(const SmallSetVector<Value *, 8> &, |
451 | | SmallVectorImpl<BasicBlock *> &, |
452 | | SmallVectorImpl<Instruction *> &, |
453 | | PredIteratorCache &, LoopInfo *, |
454 | | DominatorTree *, const TargetLibraryInfo *, |
455 | | Loop *, AliasSetTracker *, LoopSafetyInfo *, |
456 | | OptimizationRemarkEmitter *); |
457 | | |
458 | | /// Does a BFS from a given node to all of its children inside a given loop. |
459 | | /// The returned vector of nodes includes the starting point. |
460 | | SmallVector<DomTreeNode *, 16> collectChildrenInLoop(DomTreeNode *N, |
461 | | const Loop *CurLoop); |
462 | | |
463 | | /// \brief Computes safety information for a loop |
464 | | /// checks loop body & header for the possibility of may throw |
465 | | /// exception, it takes LoopSafetyInfo and loop as argument. |
466 | | /// Updates safety information in LoopSafetyInfo argument. |
467 | | void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *); |
468 | | |
469 | | /// Returns true if the instruction in a loop is guaranteed to execute at least |
470 | | /// once. |
471 | | bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, |
472 | | const Loop *CurLoop, |
473 | | const LoopSafetyInfo *SafetyInfo); |
474 | | |
475 | | /// \brief Returns the instructions that use values defined in the loop. |
476 | | SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L); |
477 | | |
478 | | /// \brief Find string metadata for loop |
479 | | /// |
480 | | /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an |
481 | | /// operand or null otherwise. If the string metadata is not found return |
482 | | /// Optional's not-a-value. |
483 | | Optional<const MDOperand *> findStringMetadataForLoop(Loop *TheLoop, |
484 | | StringRef Name); |
485 | | |
486 | | /// \brief Set input string into loop metadata by keeping other values intact. |
487 | | void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, |
488 | | unsigned V = 0); |
489 | | |
490 | | /// \brief Get a loop's estimated trip count based on branch weight metadata. |
491 | | /// Returns 0 when the count is estimated to be 0, or None when a meaningful |
492 | | /// estimate can not be made. |
493 | | Optional<unsigned> getLoopEstimatedTripCount(Loop *L); |
494 | | |
495 | | /// Helper to consistently add the set of standard passes to a loop pass's \c |
496 | | /// AnalysisUsage. |
497 | | /// |
498 | | /// All loop passes should call this as part of implementing their \c |
499 | | /// getAnalysisUsage. |
500 | | void getLoopAnalysisUsage(AnalysisUsage &AU); |
501 | | |
502 | | /// Returns true if the hoister and sinker can handle this instruction. |
503 | | /// If SafetyInfo is null, we are checking for sinking instructions from |
504 | | /// preheader to loop body (no speculation). |
505 | | /// If SafetyInfo is not null, we are checking for hoisting/sinking |
506 | | /// instructions from loop body to preheader/exit. Check if the instruction |
507 | | /// can execute speculatively. |
508 | | /// If \p ORE is set use it to emit optimization remarks. |
509 | | bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, |
510 | | Loop *CurLoop, AliasSetTracker *CurAST, |
511 | | LoopSafetyInfo *SafetyInfo, |
512 | | OptimizationRemarkEmitter *ORE = nullptr); |
513 | | |
514 | | /// Generates a vector reduction using shufflevectors to reduce the value. |
515 | | Value *getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op, |
516 | | RecurrenceDescriptor::MinMaxRecurrenceKind |
517 | | MinMaxKind = RecurrenceDescriptor::MRK_Invalid, |
518 | | ArrayRef<Value *> RedOps = ArrayRef<Value *>()); |
519 | | |
520 | | /// Create a target reduction of the given vector. The reduction operation |
521 | | /// is described by the \p Opcode parameter. min/max reductions require |
522 | | /// additional information supplied in \p Flags. |
523 | | /// The target is queried to determine if intrinsics or shuffle sequences are |
524 | | /// required to implement the reduction. |
525 | | Value * |
526 | | createSimpleTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, |
527 | | unsigned Opcode, Value *Src, |
528 | | TargetTransformInfo::ReductionFlags Flags = |
529 | | TargetTransformInfo::ReductionFlags(), |
530 | | ArrayRef<Value *> RedOps = ArrayRef<Value *>()); |
531 | | |
532 | | /// Create a generic target reduction using a recurrence descriptor \p Desc |
533 | | /// The target is queried to determine if intrinsics or shuffle sequences are |
534 | | /// required to implement the reduction. |
535 | | Value *createTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, |
536 | | RecurrenceDescriptor &Desc, Value *Src, |
537 | | bool NoNaN = false); |
538 | | |
539 | | /// Get the intersection (logical and) of all of the potential IR flags |
540 | | /// of each scalar operation (VL) that will be converted into a vector (I). |
541 | | /// If OpValue is non-null, we only consider operations similar to OpValue |
542 | | /// when intersecting. |
543 | | /// Flag set: NSW, NUW, exact, and all of fast-math. |
544 | | void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr); |
545 | | |
546 | | } // end namespace llvm |
547 | | |
548 | | #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H |