Coverage Report

Created: 2017-10-03 07:32

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