LLVM  7.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"
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.
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.
57 
58  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.
74 public:
75  /// This enum represents the kinds of recurrences that we support.
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.
97  MRK_FloatMax
98  };
99 
100  RecurrenceDescriptor() = default;
101 
103  MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT,
105  : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK),
106  UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) {
107  CastInsts.insert(CI.begin(), CI.end());
108  }
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  UnsafeAlgebraInst(UAI) {}
116 
118  : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
119  UnsafeAlgebraInst(UAI) {}
120 
121  bool isRecurrence() { return IsRecurrence; }
122 
123  bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
124 
125  Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
126 
127  MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }
128 
129  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,
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,
195  DominatorTree *DT);
196 
198 
200 
202 
203  Instruction *getLoopExitInstr() { return LoopExitInstr; }
204 
205  /// Returns true if the recurrence has unsafe algebra which requires a relaxed
206  /// floating-point model.
207  bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
208 
209  /// Returns first unsafe algebra instruction in the PHI node's use-chain.
210  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,
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,
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  Type *getRecurrenceType() { return RecurrenceType; }
242 
243  /// Returns a reference to the instructions used for type-promoting the
244  /// recurrence.
246 
247  /// Returns true if all source operands of the recurrence are SExtInsts.
248  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.
268 };
269 
270 /// A struct for saving information about induction variables.
272 public:
273  /// This enum represents the kinds of inductions that we support.
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  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.
298  const DataLayout& DL) const;
299 
300  Value *getStartValue() const { return StartValue; }
301  InductionKind getKind() const { return IK; }
302  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. If the def-use chain
310  /// associated with the phi includes casts (that we know we can ignore
311  /// under proper runtime checks), they are passed through \p CastsToIgnore.
312  static bool
313  isInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE,
314  InductionDescriptor &D, const SCEV *Expr = nullptr,
315  SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr);
316 
317  /// Returns true if \p Phi is a floating point induction in the loop \p L.
318  /// If \p Phi is an induction, the induction descriptor \p D will contain
319  /// the data describing this induction.
320  static bool isFPInductionPHI(PHINode *Phi, const Loop* L,
322 
323  /// Returns true if \p Phi is a loop \p L induction, in the context associated
324  /// with the run-time predicate of PSE. If \p Assume is true, this can add
325  /// further SCEV predicates to \p PSE in order to prove that \p Phi is an
326  /// induction.
327  /// If \p Phi is an induction, \p D will contain the data describing this
328  /// induction.
329  static bool isInductionPHI(PHINode *Phi, const Loop* L,
331  InductionDescriptor &D, bool Assume = false);
332 
333  /// Returns true if the induction type is FP and the binary operator does
334  /// not have the "fast-math" property. Such operation requires a relaxed FP
335  /// mode.
337  return InductionBinOp && !cast<FPMathOperator>(InductionBinOp)->isFast();
338  }
339 
340  /// Returns induction operator that does not have "fast-math" property
341  /// and requires FP unsafe mode.
343  if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast())
344  return nullptr;
345  return InductionBinOp;
346  }
347 
348  /// Returns binary opcode of the induction operator.
350  return InductionBinOp ? InductionBinOp->getOpcode() :
351  Instruction::BinaryOpsEnd;
352  }
353 
354  /// Returns a reference to the type cast instructions in the induction
355  /// update chain, that are redundant when guarded with a runtime
356  /// SCEV overflow check.
358  return RedundantCasts;
359  }
360 
361 private:
362  /// Private constructor - used by \c isInductionPHI.
363  InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
364  BinaryOperator *InductionBinOp = nullptr,
365  SmallVectorImpl<Instruction *> *Casts = nullptr);
366 
367  /// Start value.
368  TrackingVH<Value> StartValue;
369  /// Induction kind.
370  InductionKind IK = IK_NoInduction;
371  /// Step value.
372  const SCEV *Step = nullptr;
373  // Instruction that advances induction variable.
374  BinaryOperator *InductionBinOp = nullptr;
375  // Instructions used for type-casts of the induction variable,
376  // that are redundant when guarded with a runtime SCEV overflow check.
377  SmallVector<Instruction *, 2> RedundantCasts;
378 };
379 
381  bool PreserveLCSSA);
382 
383 /// Ensure that all exit blocks of the loop are dedicated exits.
384 ///
385 /// For any loop exit block with non-loop predecessors, we split the loop
386 /// predecessors to use a dedicated loop exit block. We update the dominator
387 /// tree and loop info if provided, and will preserve LCSSA if requested.
389  bool PreserveLCSSA);
390 
391 /// Ensures LCSSA form for every instruction from the Worklist in the scope of
392 /// innermost containing loop.
393 ///
394 /// For the given instruction which have uses outside of the loop, an LCSSA PHI
395 /// node is inserted and the uses outside the loop are rewritten to use this
396 /// node.
397 ///
398 /// LoopInfo and DominatorTree are required and, since the routine makes no
399 /// changes to CFG, preserved.
400 ///
401 /// Returns true if any modifications are made.
403  DominatorTree &DT, LoopInfo &LI);
404 
405 /// \brief Put loop into LCSSA form.
406 ///
407 /// Looks at all instructions in the loop which have uses outside of the
408 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
409 /// the loop are rewritten to use this node.
410 ///
411 /// LoopInfo and DominatorTree are required and preserved.
412 ///
413 /// If ScalarEvolution is passed in, it will be preserved.
414 ///
415 /// Returns true if any modifications are made to the loop.
416 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE);
417 
418 /// \brief Put a loop nest into LCSSA form.
419 ///
420 /// This recursively forms LCSSA for a loop nest.
421 ///
422 /// LoopInfo and DominatorTree are required and preserved.
423 ///
424 /// If ScalarEvolution is passed in, it will be preserved.
425 ///
426 /// Returns true if any modifications are made to the loop.
428  ScalarEvolution *SE);
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
432 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
433 /// uses before definitions, allowing us to sink a loop body in one pass without
434 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
435 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
436 /// instructions of the loop and loop safety information as
437 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
442 
443 /// \brief Walk the specified region of the CFG (defined by all blocks
444 /// dominated by the specified block, and that are in the current loop) in depth
445 /// first order w.r.t the DominatorTree. This allows us to visit definitions
446 /// before uses, allowing us to hoist a loop body in one pass without iteration.
447 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
448 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
449 /// loop and loop safety information as arguments. Diagnostics is emitted via \p
450 /// ORE. It returns changed status.
454 
455 /// This function deletes dead loops. The caller of this function needs to
456 /// guarantee that the loop is infact dead.
457 /// The function requires a bunch or prerequisites to be present:
458 /// - The loop needs to be in LCSSA form
459 /// - The loop needs to have a Preheader
460 /// - A unique dedicated exit block must exist
461 ///
462 /// This also updates the relevant analysis information in \p DT, \p SE, and \p
463 /// LI if pointers to those are provided.
464 /// It also updates the loop PM if an updater struct is provided.
465 
467  LoopInfo *LI);
468 
469 /// \brief Try to promote memory values to scalars by sinking stores out of
470 /// the loop and moving loads to before the loop. We do this by looping over
471 /// the stores in the loop, looking for stores to Must pointers which are
472 /// loop invariant. It takes a set of must-alias values, Loop exit blocks
473 /// vector, loop exit blocks insertion point vector, PredIteratorCache,
474 /// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions
475 /// of the loop and loop safety information as arguments.
476 /// Diagnostics is emitted via \p ORE. It returns changed status.
481  DominatorTree *, const TargetLibraryInfo *,
484 
485 /// Does a BFS from a given node to all of its children inside a given loop.
486 /// The returned vector of nodes includes the starting point.
488  const Loop *CurLoop);
489 
490 /// \brief Computes safety information for a loop
491 /// checks loop body & header for the possibility of may throw
492 /// exception, it takes LoopSafetyInfo and loop as argument.
493 /// Updates safety information in LoopSafetyInfo argument.
495 
496 /// Returns true if the instruction in a loop is guaranteed to execute at least
497 /// once.
498 bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT,
499  const Loop *CurLoop,
500  const LoopSafetyInfo *SafetyInfo);
501 
502 /// \brief Returns the instructions that use values defined in the loop.
504 
505 /// \brief Find string metadata for loop
506 ///
507 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
508 /// operand or null otherwise. If the string metadata is not found return
509 /// Optional's not-a-value.
511  StringRef Name);
512 
513 /// \brief Set input string into loop metadata by keeping other values intact.
514 void addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
515  unsigned V = 0);
516 
517 /// \brief Get a loop's estimated trip count based on branch weight metadata.
518 /// Returns 0 when the count is estimated to be 0, or None when a meaningful
519 /// estimate can not be made.
521 
522 /// Helper to consistently add the set of standard passes to a loop pass's \c
523 /// AnalysisUsage.
524 ///
525 /// All loop passes should call this as part of implementing their \c
526 /// getAnalysisUsage.
528 
529 /// Returns true if the hoister and sinker can handle this instruction.
530 /// If SafetyInfo is null, we are checking for sinking instructions from
531 /// preheader to loop body (no speculation).
532 /// If SafetyInfo is not null, we are checking for hoisting/sinking
533 /// instructions from loop body to preheader/exit. Check if the instruction
534 /// can execute speculatively.
535 /// If \p ORE is set use it to emit optimization remarks.
537  Loop *CurLoop, AliasSetTracker *CurAST,
538  LoopSafetyInfo *SafetyInfo,
539  OptimizationRemarkEmitter *ORE = nullptr);
540 
541 /// Generates a vector reduction using shufflevectors to reduce the value.
542 Value *getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op,
546 
547 /// Create a target reduction of the given vector. The reduction operation
548 /// is described by the \p Opcode parameter. min/max reductions require
549 /// additional information supplied in \p Flags.
550 /// The target is queried to determine if intrinsics or shuffle sequences are
551 /// required to implement the reduction.
552 Value *
554  unsigned Opcode, Value *Src,
558 
559 /// Create a generic target reduction using a recurrence descriptor \p Desc
560 /// The target is queried to determine if intrinsics or shuffle sequences are
561 /// required to implement the reduction.
563  RecurrenceDescriptor &Desc, Value *Src,
564  bool NoNaN = false);
565 
566 /// Get the intersection (logical and) of all of the potential IR flags
567 /// of each scalar operation (VL) that will be converted into a vector (I).
568 /// If OpValue is non-null, we only consider operations similar to OpValue
569 /// when intersecting.
570 /// Flag set: NSW, NUW, exact, and all of fast-math.
571 void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr);
572 
573 } // end namespace llvm
574 
575 #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
Bitwise or logical XOR of numbers.
Definition: LoopUtils.h:82
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Instruction * getUnsafeAlgebraInst()
Returns first unsafe algebra instruction in the PHI node&#39;s use-chain.
Definition: LoopUtils.h:210
Various leaf nodes.
Definition: ISDOpcodes.h:60
Min/max implemented in terms of select(cmp()).
Definition: LoopUtils.h:83
InstDesc(bool IsRecur, Instruction *I, Instruction *UAI=nullptr)
Definition: LoopUtils.h:113
Instruction::BinaryOps getInductionOpcode() const
Returns binary opcode of the induction operator.
Definition: LoopUtils.h:349
The main scalar evolution driver.
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...
MinMaxRecurrenceKind getMinMaxRecurrenceKind()
Definition: LoopUtils.h:199
InductionKind getKind() const
Definition: LoopUtils.h:301
Value * getStartValue() const
Definition: LoopUtils.h:300
DenseMap< BasicBlock *, ColorVector > BlockColors
Definition: LoopUtils.h:56
bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:333
bool isSigned()
Returns true if all source operands of the recurrence are SExtInsts.
Definition: LoopUtils.h:248
bool hasUnsafeAlgebra()
Returns true if the recurrence has unsafe algebra which requires a relaxed floating-point model...
Definition: LoopUtils.h:207
Value * getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op, RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind=RecurrenceDescriptor::MRK_Invalid, ArrayRef< Value *> RedOps=ArrayRef< Value *>())
Generates a vector reduction using shufflevectors to reduce the value.
Definition: LoopUtils.cpp:1499
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:668
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
Definition: LoopUtils.cpp:1131
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI)
This function deletes dead loops.
Definition: LoopUtils.cpp:1266
void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *)
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: LICM.cpp:509
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
LoopSafetyInfo()=default
Not an induction variable.
Definition: LoopUtils.h:275
This POD struct holds information about a potential recurrence operation.
Definition: LoopUtils.h:111
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:1209
void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
Bitwise or logical AND of numbers.
Definition: LoopUtils.h:81
Pointer induction var. Step = C / sizeof(elem).
Definition: LoopUtils.h:277
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:73
Integer induction variable. Step = C.
Definition: LoopUtils.h:276
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
Flags describing the kind of vector reduction.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
Value * createSimpleTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, unsigned Opcode, Value *Src, TargetTransformInfo::ReductionFlags Flags=TargetTransformInfo::ReductionFlags(), ArrayRef< Value *> RedOps=ArrayRef< Value *>())
Create a target reduction of the given vector.
Definition: LoopUtils.cpp:1542
Value handle that tracks a Value across RAUW.
Definition: ValueHandle.h:337
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:365
This is an important base class in LLVM.
Definition: Constant.h:42
Instruction * getUnsafeAlgebraInst()
Returns induction operator that does not have "fast-math" property and requires FP unsafe mode...
Definition: LoopUtils.h:342
const SCEV * getStep() const
Definition: LoopUtils.h:302
InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI=nullptr)
Definition: LoopUtils.h:117
Represent the analysis usage information of a pass.
Optional< unsigned > getLoopEstimatedTripCount(Loop *L)
Get a loop&#39;s estimated trip count based on branch weight metadata.
Definition: LoopUtils.cpp:1454
RecurrenceKind getRecurrenceKind()
Definition: LoopUtils.h:197
Optional< const MDOperand * > findStringMetadataForLoop(Loop *TheLoop, StringRef Name)
Find string metadata for loop.
Definition: LoopUtils.cpp:1212
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:1657
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: LoopUtils.h:73
bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Definition: LCSSA.cpp:278
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
MinMaxRecurrenceKind getMinMaxKind()
Definition: LoopUtils.h:127
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
A struct for saving information about induction variables.
Definition: LoopUtils.h:271
Bitwise or logical OR of numbers.
Definition: LoopUtils.h:80
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K, MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT, bool Signed, SmallPtrSetImpl< Instruction *> &CI)
Definition: LoopUtils.h:102
Provides information about what library functions are available for the current target.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
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:430
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:1618
bool hasUnsafeAlgebra()
Returns true if the induction type is FP and the binary operator does not have the "fast-math" proper...
Definition: LoopUtils.h:336
const SmallVectorImpl< Instruction * > & getCastInsts() const
Returns a reference to the type cast instructions in the induction update chain, that are redundant w...
Definition: LoopUtils.h:357
Basic Alias true
Captures loop safety information.
Definition: LoopUtils.h:51
iterator begin() const
Definition: SmallPtrSet.h:397
This class represents an analyzed expression in the program.
Instruction * getLoopExitInstr()
Definition: LoopUtils.h:203
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:439
#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:1149
iterator end() const
Definition: SmallPtrSet.h:402
OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere...
Definition: STLExtras.h:896
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:1248
const unsigned Kind
SmallPtrSet< Instruction *, 8 > & getCastInsts()
Returns a reference to the instructions used for type-promoting the recurrence.
Definition: LoopUtils.h:245
LLVM Value Representation.
Definition: Value.h:73
TrackingVH< Value > getRecurrenceStartValue()
Definition: LoopUtils.h:201
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
Definition: LoopUtils.cpp:1067
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
A single uniqued string.
Definition: Metadata.h:602
This pass exposes codegen information to IR-level passes.
bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE=nullptr)
Returns true if the hoister and sinker can handle this instruction.
Definition: LICM.cpp:596
InductionKind
This enum represents the kinds of inductions that we support.
Definition: LoopUtils.h:274
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo)
Returns true if the instruction in a loop is guaranteed to execute at least once. ...
Definition: LoopUtils.cpp:1414
The optimization diagnostic interface.
RecurrenceKind
This enum represents the kinds of recurrences that we support.
Definition: LoopUtils.h:76
Type * getRecurrenceType()
Returns the type of the recurrence.
Definition: LoopUtils.h:241