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