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