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 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 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 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 117 InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr) 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, 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 RecurrenceKind getRecurrenceKind() { return Kind; } 198 199 MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; } 200 201 TrackingVH<Value> getRecurrenceStartValue() { return StartValue; } 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, 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 Type *getRecurrenceType() { return RecurrenceType; } 242 243 /// Returns a reference to the instructions used for type-promoting the 244 /// recurrence. 245 SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; } 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. 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 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 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, 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 bool hasUnsafeAlgebra() { 334 return InductionBinOp && 335 !cast<FPMathOperator>(InductionBinOp)->hasUnsafeAlgebra(); 336 } 337 338 /// Returns induction operator that does not have "fast-math" property 339 /// and requires FP unsafe mode. 340 Instruction *getUnsafeAlgebraInst() { 341 if (!InductionBinOp || 342 cast<FPMathOperator>(InductionBinOp)->hasUnsafeAlgebra()) 343 return nullptr; 344 return InductionBinOp; 345 } 346 347 /// Returns binary opcode of the induction operator. 348 Instruction::BinaryOps getInductionOpcode() const { 349 return InductionBinOp ? InductionBinOp->getOpcode() : 350 Instruction::BinaryOpsEnd; 351 } 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 /// This function deletes dead loops. The caller of this function needs to 443 /// guarantee that the loop is infact dead. 444 /// The function requires a bunch or prerequisites to be present: 445 /// - The loop needs to be in LCSSA form 446 /// - The loop needs to have a Preheader 447 /// - A unique dedicated exit block must exist 448 /// 449 /// This also updates the relevant analysis information in \p DT, \p SE, and \p 450 /// LI if pointers to those are provided. 451 /// It also updates the loop PM if an updater struct is provided. 452 453 void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, 454 LoopInfo *LI); 455 456 /// \brief Try to promote memory values to scalars by sinking stores out of 457 /// the loop and moving loads to before the loop. We do this by looping over 458 /// the stores in the loop, looking for stores to Must pointers which are 459 /// loop invariant. It takes a set of must-alias values, Loop exit blocks 460 /// vector, loop exit blocks insertion point vector, PredIteratorCache, 461 /// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions 462 /// of the loop and loop safety information as arguments. 463 /// Diagnostics is emitted via \p ORE. It returns changed status. 464 bool promoteLoopAccessesToScalars(const SmallSetVector<Value *, 8> &, 465 SmallVectorImpl<BasicBlock *> &, 466 SmallVectorImpl<Instruction *> &, 467 PredIteratorCache &, LoopInfo *, 468 DominatorTree *, const TargetLibraryInfo *, 469 Loop *, AliasSetTracker *, LoopSafetyInfo *, 470 OptimizationRemarkEmitter *); 471 472 /// Does a BFS from a given node to all of its children inside a given loop. 473 /// The returned vector of nodes includes the starting point. 474 SmallVector<DomTreeNode *, 16> collectChildrenInLoop(DomTreeNode *N, 475 const Loop *CurLoop); 476 477 /// \brief Computes safety information for a loop 478 /// checks loop body & header for the possibility of may throw 479 /// exception, it takes LoopSafetyInfo and loop as argument. 480 /// Updates safety information in LoopSafetyInfo argument. 481 void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *); 482 483 /// Returns true if the instruction in a loop is guaranteed to execute at least 484 /// once. 485 bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, 486 const Loop *CurLoop, 487 const LoopSafetyInfo *SafetyInfo); 488 489 /// \brief Returns the instructions that use values defined in the loop. 490 SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L); 491 492 /// \brief Find string metadata for loop 493 /// 494 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an 495 /// operand or null otherwise. If the string metadata is not found return 496 /// Optional's not-a-value. 497 Optional<const MDOperand *> findStringMetadataForLoop(Loop *TheLoop, 498 StringRef Name); 499 500 /// \brief Set input string into loop metadata by keeping other values intact. 501 void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, 502 unsigned V = 0); 503 504 /// \brief Get a loop's estimated trip count based on branch weight metadata. 505 /// Returns 0 when the count is estimated to be 0, or None when a meaningful 506 /// estimate can not be made. 507 Optional<unsigned> getLoopEstimatedTripCount(Loop *L); 508 509 /// Helper to consistently add the set of standard passes to a loop pass's \c 510 /// AnalysisUsage. 511 /// 512 /// All loop passes should call this as part of implementing their \c 513 /// getAnalysisUsage. 514 void getLoopAnalysisUsage(AnalysisUsage &AU); 515 516 /// Returns true if the hoister and sinker can handle this instruction. 517 /// If SafetyInfo is null, we are checking for sinking instructions from 518 /// preheader to loop body (no speculation). 519 /// If SafetyInfo is not null, we are checking for hoisting/sinking 520 /// instructions from loop body to preheader/exit. Check if the instruction 521 /// can execute speculatively. 522 /// If \p ORE is set use it to emit optimization remarks. 523 bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, 524 Loop *CurLoop, AliasSetTracker *CurAST, 525 LoopSafetyInfo *SafetyInfo, 526 OptimizationRemarkEmitter *ORE = nullptr); 527 528 /// Generates a vector reduction using shufflevectors to reduce the value. 529 Value *getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op, 530 RecurrenceDescriptor::MinMaxRecurrenceKind 531 MinMaxKind = RecurrenceDescriptor::MRK_Invalid, 532 ArrayRef<Value *> RedOps = ArrayRef<Value *>()); 533 534 /// Create a target reduction of the given vector. The reduction operation 535 /// is described by the \p Opcode parameter. min/max reductions require 536 /// additional information supplied in \p Flags. 537 /// The target is queried to determine if intrinsics or shuffle sequences are 538 /// required to implement the reduction. 539 Value * 540 createSimpleTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, 541 unsigned Opcode, Value *Src, 542 TargetTransformInfo::ReductionFlags Flags = 543 TargetTransformInfo::ReductionFlags(), 544 ArrayRef<Value *> RedOps = ArrayRef<Value *>()); 545 546 /// Create a generic target reduction using a recurrence descriptor \p Desc 547 /// The target is queried to determine if intrinsics or shuffle sequences are 548 /// required to implement the reduction. 549 Value *createTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, 550 RecurrenceDescriptor &Desc, Value *Src, 551 bool NoNaN = false); 552 553 /// Get the intersection (logical and) of all of the potential IR flags 554 /// of each scalar operation (VL) that will be converted into a vector (I). 555 /// If OpValue is non-null, we only consider operations similar to OpValue 556 /// when intersecting. 557 /// Flag set: NSW, NUW, exact, and all of fast-math. 558 void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr); 559 560 } // end namespace llvm 561 562 #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H 563