LLVM  6.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.
310  static bool isInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE,
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,
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,
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.
334  return InductionBinOp && !cast<FPMathOperator>(InductionBinOp)->isFast();
335  }
336 
337  /// Returns induction operator that does not have "fast-math" property
338  /// and requires FP unsafe mode.
340  if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast())
341  return nullptr;
342  return InductionBinOp;
343  }
344 
345  /// Returns binary opcode of the induction operator.
347  return InductionBinOp ? InductionBinOp->getOpcode() :
348  Instruction::BinaryOpsEnd;
349  }
350 
351 private:
352  /// Private constructor - used by \c isInductionPHI.
353  InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
354  BinaryOperator *InductionBinOp = nullptr);
355 
356  /// Start value.
357  TrackingVH<Value> StartValue;
358  /// Induction kind.
359  InductionKind IK = IK_NoInduction;
360  /// Step value.
361  const SCEV *Step = nullptr;
362  // Instruction that advances induction variable.
363  BinaryOperator *InductionBinOp = nullptr;
364 };
365 
367  bool PreserveLCSSA);
368 
369 /// Ensure that all exit blocks of the loop are dedicated exits.
370 ///
371 /// For any loop exit block with non-loop predecessors, we split the loop
372 /// predecessors to use a dedicated loop exit block. We update the dominator
373 /// tree and loop info if provided, and will preserve LCSSA if requested.
375  bool PreserveLCSSA);
376 
377 /// Ensures LCSSA form for every instruction from the Worklist in the scope of
378 /// innermost containing loop.
379 ///
380 /// For the given instruction which have uses outside of the loop, an LCSSA PHI
381 /// node is inserted and the uses outside the loop are rewritten to use this
382 /// node.
383 ///
384 /// LoopInfo and DominatorTree are required and, since the routine makes no
385 /// changes to CFG, preserved.
386 ///
387 /// Returns true if any modifications are made.
389  DominatorTree &DT, LoopInfo &LI);
390 
391 /// \brief Put loop into LCSSA form.
392 ///
393 /// Looks at all instructions in the loop which have uses outside of the
394 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
395 /// the loop are rewritten to use this node.
396 ///
397 /// LoopInfo and DominatorTree are required and preserved.
398 ///
399 /// If ScalarEvolution is passed in, it will be preserved.
400 ///
401 /// Returns true if any modifications are made to the loop.
402 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE);
403 
404 /// \brief Put a loop nest into LCSSA form.
405 ///
406 /// This recursively forms LCSSA for a loop nest.
407 ///
408 /// LoopInfo and DominatorTree are required and preserved.
409 ///
410 /// If ScalarEvolution is passed in, it will be preserved.
411 ///
412 /// Returns true if any modifications are made to the loop.
414  ScalarEvolution *SE);
415 
416 /// \brief Walk the specified region of the CFG (defined by all blocks
417 /// dominated by the specified block, and that are in the current loop) in
418 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
419 /// uses before definitions, allowing us to sink a loop body in one pass without
420 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
421 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
422 /// instructions of the loop and loop safety information as
423 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
427 
428 /// \brief Walk the specified region of the CFG (defined by all blocks
429 /// dominated by the specified block, and that are in the current loop) in depth
430 /// first order w.r.t the DominatorTree. This allows us to visit definitions
431 /// before uses, allowing us to hoist a loop body in one pass without iteration.
432 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
433 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
434 /// loop and loop safety information as arguments. Diagnostics is emitted via \p
435 /// ORE. It returns changed status.
439 
440 /// This function deletes dead loops. The caller of this function needs to
441 /// guarantee that the loop is infact dead.
442 /// The function requires a bunch or prerequisites to be present:
443 /// - The loop needs to be in LCSSA form
444 /// - The loop needs to have a Preheader
445 /// - A unique dedicated exit block must exist
446 ///
447 /// This also updates the relevant analysis information in \p DT, \p SE, and \p
448 /// LI if pointers to those are provided.
449 /// It also updates the loop PM if an updater struct is provided.
450 
452  LoopInfo *LI);
453 
454 /// \brief Try to promote memory values to scalars by sinking stores out of
455 /// the loop and moving loads to before the loop. We do this by looping over
456 /// the stores in the loop, looking for stores to Must pointers which are
457 /// loop invariant. It takes a set of must-alias values, Loop exit blocks
458 /// vector, loop exit blocks insertion point vector, PredIteratorCache,
459 /// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions
460 /// of the loop and loop safety information as arguments.
461 /// Diagnostics is emitted via \p ORE. It returns changed status.
466  DominatorTree *, const TargetLibraryInfo *,
469 
470 /// Does a BFS from a given node to all of its children inside a given loop.
471 /// The returned vector of nodes includes the starting point.
473  const Loop *CurLoop);
474 
475 /// \brief Computes safety information for a loop
476 /// checks loop body & header for the possibility of may throw
477 /// exception, it takes LoopSafetyInfo and loop as argument.
478 /// Updates safety information in LoopSafetyInfo argument.
480 
481 /// Returns true if the instruction in a loop is guaranteed to execute at least
482 /// once.
483 bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT,
484  const Loop *CurLoop,
485  const LoopSafetyInfo *SafetyInfo);
486 
487 /// \brief Returns the instructions that use values defined in the loop.
489 
490 /// \brief Find string metadata for loop
491 ///
492 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
493 /// operand or null otherwise. If the string metadata is not found return
494 /// Optional's not-a-value.
496  StringRef Name);
497 
498 /// \brief Set input string into loop metadata by keeping other values intact.
499 void addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
500  unsigned V = 0);
501 
502 /// \brief Get a loop's estimated trip count based on branch weight metadata.
503 /// Returns 0 when the count is estimated to be 0, or None when a meaningful
504 /// estimate can not be made.
506 
507 /// Helper to consistently add the set of standard passes to a loop pass's \c
508 /// AnalysisUsage.
509 ///
510 /// All loop passes should call this as part of implementing their \c
511 /// getAnalysisUsage.
513 
514 /// Returns true if the hoister and sinker can handle this instruction.
515 /// If SafetyInfo is null, we are checking for sinking instructions from
516 /// preheader to loop body (no speculation).
517 /// If SafetyInfo is not null, we are checking for hoisting/sinking
518 /// instructions from loop body to preheader/exit. Check if the instruction
519 /// can execute speculatively.
520 /// If \p ORE is set use it to emit optimization remarks.
522  Loop *CurLoop, AliasSetTracker *CurAST,
523  LoopSafetyInfo *SafetyInfo,
524  OptimizationRemarkEmitter *ORE = nullptr);
525 
526 /// Generates a vector reduction using shufflevectors to reduce the value.
527 Value *getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op,
531 
532 /// Create a target reduction of the given vector. The reduction operation
533 /// is described by the \p Opcode parameter. min/max reductions require
534 /// additional information supplied in \p Flags.
535 /// The target is queried to determine if intrinsics or shuffle sequences are
536 /// required to implement the reduction.
537 Value *
539  unsigned Opcode, Value *Src,
543 
544 /// Create a generic target reduction using a recurrence descriptor \p Desc
545 /// The target is queried to determine if intrinsics or shuffle sequences are
546 /// required to implement the reduction.
548  RecurrenceDescriptor &Desc, Value *Src,
549  bool NoNaN = false);
550 
551 /// Get the intersection (logical and) of all of the potential IR flags
552 /// of each scalar operation (VL) that will be converted into a vector (I).
553 /// If OpValue is non-null, we only consider operations similar to OpValue
554 /// when intersecting.
555 /// Flag set: NSW, NUW, exact, and all of fast-math.
556 void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr);
557 
558 } // end namespace llvm
559 
560 #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:346
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:332
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:1349
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:1005
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI)
This function deletes dead loops.
Definition: LoopUtils.cpp:1140
void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *)
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: LICM.cpp:493
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:1151
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:72
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:1392
Value handle that tracks a Value across RAUW.
Definition: ValueHandle.h:337
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:339
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:1304
RecurrenceKind getRecurrenceKind()
Definition: LoopUtils.h:197
Optional< const MDOperand * > findStringMetadataForLoop(Loop *TheLoop, StringRef Name)
Find string metadata for loop.
Definition: LoopUtils.cpp:1086
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:1523
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:277
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:864
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:414
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:1468
bool sinkRegion(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:353
bool hasUnsafeAlgebra()
Returns true if the induction type is FP and the binary operator does not have the "fast-math" proper...
Definition: LoopUtils.h:333
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:420
#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:1023
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:845
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:1122
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:941
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:580
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:1264
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