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"
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.
65 public:
66  /// This enum represents the kinds of recurrences that we support.
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.
89  };
90 
91  RecurrenceDescriptor() = default;
92 
96  : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK),
97  UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) {
98  CastInsts.insert(CI.begin(), CI.end());
99  }
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  : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
106  UnsafeAlgebraInst(UAI) {}
107 
109  : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
110  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.
140  InstDesc &Prev, bool HasFunNoNaNAttr);
141 
142  /// Returns true if instruction I has multiple uses in Insts
143  static bool hasMultipleUsesOf(Instruction *I,
145 
146  /// Returns true if all uses of the instruction I is within the 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).
153 
154  /// Returns identity corresponding to the RecurrenceKind.
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.
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,
196  DominatorTree *DT);
197 
199 
201 
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.
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.
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.
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.
251 };
252 
253 /// A struct for saving information about induction variables.
255 public:
256  /// This enum represents the kinds of inductions that we support.
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  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.
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,
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,
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.
320  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.
326  if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast())
327  return nullptr;
328  return InductionBinOp;
329  }
330 
331  /// Returns binary opcode of the induction operator.
333  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.
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 
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.
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.
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.
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.
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.
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 
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.
464  DominatorTree *, const TargetLibraryInfo *,
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.
471  const Loop *CurLoop);
472 
473 /// Returns the instructions that use values defined in the loop.
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.
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.
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.
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.
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,
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,
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 *
532  unsigned Opcode, Value *Src,
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.
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
Bitwise or logical XOR of numbers.
Definition: LoopUtils.h:73
static bool isArithmeticRecurrenceKind(RecurrenceKind Kind)
Returns true if the recurrence kind is an arithmetic kind.
Definition: LoopUtils.cpp:71
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
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:211
Various leaf nodes.
Definition: ISDOpcodes.h:60
Min/max implemented in terms of select(cmp()).
Definition: LoopUtils.h:74
InstDesc(bool IsRecur, Instruction *I, Instruction *UAI=nullptr)
Definition: LoopUtils.h:104
Instruction::BinaryOps getInductionOpcode() const
Returns binary opcode of the induction operator.
Definition: LoopUtils.h:332
static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop, bool HasFunNoNaNAttr, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Returns true if Phi is a reduction of type Kind and adds it to the RecurrenceDescriptor.
Definition: LoopUtils.cpp:191
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...
A cache of @llvm.assume calls within a function.
Value * createSimpleTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, unsigned Opcode, Value *Src, TargetTransformInfo::ReductionFlags Flags=TargetTransformInfo::ReductionFlags(), ArrayRef< Value *> RedOps=None)
Create a target reduction of the given vector.
Definition: LoopUtils.cpp:1609
MinMaxRecurrenceKind getMinMaxRecurrenceKind()
Definition: LoopUtils.h:200
InductionKind getKind() const
Definition: LoopUtils.h:284
Value * getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op, RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind=RecurrenceDescriptor::MRK_Invalid, ArrayRef< Value *> RedOps=None)
Generates a vector reduction using shufflevectors to reduce the value.
Definition: LoopUtils.cpp:1566
Value * getStartValue() const
Definition: LoopUtils.h:283
static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind, InstDesc &Prev, bool HasFunNoNaNAttr)
Returns a struct describing if the instruction &#39;I&#39; can be a recurrence variable of type &#39;Kind&#39;...
Definition: LoopUtils.cpp:495
static bool hasMultipleUsesOf(Instruction *I, SmallPtrSetImpl< Instruction *> &Insts)
Returns true if instruction I has multiple uses in Insts.
Definition: LoopUtils.cpp:533
bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:343
bool isSigned()
Returns true if all source operands of the recurrence are SExtInsts.
Definition: LoopUtils.h:231
bool hasUnsafeAlgebra()
Returns true if the recurrence has unsafe algebra which requires a relaxed floating-point model...
Definition: LoopUtils.h:208
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:731
static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl< Instruction *> &Set)
Returns true if all uses of the instruction I is within the Set.
Definition: LoopUtils.cpp:44
static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev)
Returns a struct describing if the instruction if the instruction is a Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y) or max(X, Y).
Definition: LoopUtils.cpp:446
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
Definition: LoopUtils.cpp:1208
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI)
This function deletes dead loops.
Definition: LoopUtils.cpp:1343
Value * getOrderedReduction(IRBuilder<> &Builder, Value *Acc, Value *Src, unsigned Op, RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind=RecurrenceDescriptor::MRK_Invalid, ArrayRef< Value *> RedOps=None)
Generates an ordered vector reduction using extracts to reduce the value.
Definition: LoopUtils.cpp:1534
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
Not an induction variable.
Definition: LoopUtils.h:258
This POD struct holds information about a potential recurrence operation.
Definition: LoopUtils.h:102
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:1212
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:142
Bitwise or logical AND of numbers.
Definition: LoopUtils.h:72
Pointer induction var. Step = C / sizeof(elem).
Definition: LoopUtils.h:260
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:74
Integer induction variable. Step = C.
Definition: LoopUtils.h:259
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
Min/max implemented in terms of select(cmp()).
Definition: LoopUtils.h:77
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:369
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:325
const SCEV * getStep() const
Definition: LoopUtils.h:285
InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI=nullptr)
Definition: LoopUtils.h:108
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:1489
static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Returns true if Phi is a reduction in TheLoop.
Definition: LoopUtils.cpp:546
RecurrenceKind getRecurrenceKind()
Definition: LoopUtils.h:198
Optional< const MDOperand * > findStringMetadataForLoop(Loop *TheLoop, StringRef Name)
Find string metadata for loop.
Definition: LoopUtils.cpp:1289
static unsigned getRecurrenceBinOp(RecurrenceKind Kind)
Returns the opcode of binary operation corresponding to the RecurrenceKind.
Definition: LoopUtils.cpp:686
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:1724
static bool isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop, DenseMap< Instruction *, Instruction *> &SinkAfter, DominatorTree *DT)
Returns true if Phi is a first-order recurrence.
Definition: LoopUtils.cpp:606
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: LoopUtils.h:64
bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Definition: LCSSA.cpp:288
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
MinMaxRecurrenceKind getMinMaxKind()
Definition: LoopUtils.h:118
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:254
Bitwise or logical OR of numbers.
Definition: LoopUtils.h:71
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:861
RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K, MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT, bool Signed, SmallPtrSetImpl< Instruction *> &CI)
Definition: LoopUtils.h:93
Provides information about what library functions are available for the current target.
static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind)
Returns true if the recurrence kind is a floating point kind.
Definition: LoopUtils.cpp:67
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:435
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:1685
static Constant * getRecurrenceIdentity(RecurrenceKind K, Type *Tp)
Returns identity corresponding to the RecurrenceKind.
Definition: LoopUtils.cpp:660
static Value * createMinMaxOp(IRBuilder<> &Builder, MinMaxRecurrenceKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
Definition: LoopUtils.cpp:711
bool hasUnsafeAlgebra()
Returns true if the induction type is FP and the binary operator does not have the "fast-math" proper...
Definition: LoopUtils.h:319
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:340
Basic Alias true
Captures loop safety information.
Definition: MustExecute.h:39
iterator begin() const
Definition: SmallPtrSet.h:397
This class represents an analyzed expression in the program.
static bool isIntegerRecurrenceKind(RecurrenceKind Kind)
Returns true if the recurrence kind is an integer kind.
Definition: LoopUtils.cpp:52
Instruction * getLoopExitInstr()
Definition: LoopUtils.h:204
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
#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:1226
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:990
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:1325
SmallPtrSet< Instruction *, 8 > & getCastInsts()
Returns a reference to the instructions used for type-promoting the recurrence.
Definition: LoopUtils.h:228
LLVM Value Representation.
Definition: Value.h:73
TrackingVH< Value > getRecurrenceStartValue()
Definition: LoopUtils.h:202
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
Definition: LoopUtils.cpp:1143
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:578
InductionKind
This enum represents the kinds of inductions that we support.
Definition: LoopUtils.h:257
The optimization diagnostic interface.
RecurrenceKind
This enum represents the kinds of recurrences that we support.
Definition: LoopUtils.h:67
Type * getRecurrenceType()
Returns the type of the recurrence.
Definition: LoopUtils.h:224