1 //===- InductiveRangeCheckElimination.cpp - -------------------------------===// 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 // The InductiveRangeCheckElimination pass splits a loop's iteration space into 11 // three disjoint ranges. It does that in a way such that the loop running in 12 // the middle loop provably does not need range checks. As an example, it will 13 // convert 14 // 15 // len = < known positive > 16 // for (i = 0; i < n; i++) { 17 // if (0 <= i && i < len) { 18 // do_something(); 19 // } else { 20 // throw_out_of_bounds(); 21 // } 22 // } 23 // 24 // to 25 // 26 // len = < known positive > 27 // limit = smin(n, len) 28 // // no first segment 29 // for (i = 0; i < limit; i++) { 30 // if (0 <= i && i < len) { // this check is fully redundant 31 // do_something(); 32 // } else { 33 // throw_out_of_bounds(); 34 // } 35 // } 36 // for (i = limit; i < n; i++) { 37 // if (0 <= i && i < len) { 38 // do_something(); 39 // } else { 40 // throw_out_of_bounds(); 41 // } 42 // } 43 // 44 //===----------------------------------------------------------------------===// 45 46 #include "llvm/Transforms/Scalar/InductiveRangeCheckElimination.h" 47 #include "llvm/ADT/APInt.h" 48 #include "llvm/ADT/ArrayRef.h" 49 #include "llvm/ADT/None.h" 50 #include "llvm/ADT/Optional.h" 51 #include "llvm/ADT/SmallPtrSet.h" 52 #include "llvm/ADT/SmallVector.h" 53 #include "llvm/ADT/StringRef.h" 54 #include "llvm/ADT/Twine.h" 55 #include "llvm/Analysis/BranchProbabilityInfo.h" 56 #include "llvm/Analysis/LoopAnalysisManager.h" 57 #include "llvm/Analysis/LoopInfo.h" 58 #include "llvm/Analysis/LoopPass.h" 59 #include "llvm/Analysis/ScalarEvolution.h" 60 #include "llvm/Analysis/ScalarEvolutionExpander.h" 61 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 62 #include "llvm/IR/BasicBlock.h" 63 #include "llvm/IR/CFG.h" 64 #include "llvm/IR/Constants.h" 65 #include "llvm/IR/DerivedTypes.h" 66 #include "llvm/IR/Dominators.h" 67 #include "llvm/IR/Function.h" 68 #include "llvm/IR/IRBuilder.h" 69 #include "llvm/IR/InstrTypes.h" 70 #include "llvm/IR/Instructions.h" 71 #include "llvm/IR/Metadata.h" 72 #include "llvm/IR/Module.h" 73 #include "llvm/IR/PatternMatch.h" 74 #include "llvm/IR/Type.h" 75 #include "llvm/IR/Use.h" 76 #include "llvm/IR/User.h" 77 #include "llvm/IR/Value.h" 78 #include "llvm/Pass.h" 79 #include "llvm/Support/BranchProbability.h" 80 #include "llvm/Support/Casting.h" 81 #include "llvm/Support/CommandLine.h" 82 #include "llvm/Support/Compiler.h" 83 #include "llvm/Support/Debug.h" 84 #include "llvm/Support/ErrorHandling.h" 85 #include "llvm/Support/raw_ostream.h" 86 #include "llvm/Transforms/Scalar.h" 87 #include "llvm/Transforms/Utils/Cloning.h" 88 #include "llvm/Transforms/Utils/LoopSimplify.h" 89 #include "llvm/Transforms/Utils/LoopUtils.h" 90 #include "llvm/Transforms/Utils/ValueMapper.h" 91 #include <algorithm> 92 #include <cassert> 93 #include <iterator> 94 #include <limits> 95 #include <utility> 96 #include <vector> 97 98 using namespace llvm; 99 using namespace llvm::PatternMatch; 100 101 static cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden, 102 cl::init(64)); 103 104 static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden, 105 cl::init(false)); 106 107 static cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden, 108 cl::init(false)); 109 110 static cl::opt<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal", 111 cl::Hidden, cl::init(10)); 112 113 static cl::opt<bool> SkipProfitabilityChecks("irce-skip-profitability-checks", 114 cl::Hidden, cl::init(false)); 115 116 static cl::opt<bool> AllowUnsignedLatchCondition("irce-allow-unsigned-latch", 117 cl::Hidden, cl::init(true)); 118 119 static const char *ClonedLoopTag = "irce.loop.clone"; 120 121 #define DEBUG_TYPE "irce" 122 123 namespace { 124 125 /// An inductive range check is conditional branch in a loop with 126 /// 127 /// 1. a very cold successor (i.e. the branch jumps to that successor very 128 /// rarely) 129 /// 130 /// and 131 /// 132 /// 2. a condition that is provably true for some contiguous range of values 133 /// taken by the containing loop's induction variable. 134 /// 135 class InductiveRangeCheck { 136 // Classifies a range check 137 enum RangeCheckKind : unsigned { 138 // Range check of the form "0 <= I". 139 RANGE_CHECK_LOWER = 1, 140 141 // Range check of the form "I < L" where L is known positive. 142 RANGE_CHECK_UPPER = 2, 143 144 // The logical and of the RANGE_CHECK_LOWER and RANGE_CHECK_UPPER 145 // conditions. 146 RANGE_CHECK_BOTH = RANGE_CHECK_LOWER | RANGE_CHECK_UPPER, 147 148 // Unrecognized range check condition. 149 RANGE_CHECK_UNKNOWN = (unsigned)-1 150 }; 151 152 static StringRef rangeCheckKindToStr(RangeCheckKind); 153 154 const SCEV *Begin = nullptr; 155 const SCEV *Step = nullptr; 156 const SCEV *End = nullptr; 157 Use *CheckUse = nullptr; 158 RangeCheckKind Kind = RANGE_CHECK_UNKNOWN; 159 bool IsSigned = true; 160 161 static RangeCheckKind parseRangeCheckICmp(Loop *L, ICmpInst *ICI, 162 ScalarEvolution &SE, Value *&Index, 163 Value *&Length, bool &IsSigned); 164 165 static void 166 extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse, 167 SmallVectorImpl<InductiveRangeCheck> &Checks, 168 SmallPtrSetImpl<Value *> &Visited); 169 170 public: 171 const SCEV *getBegin() const { return Begin; } 172 const SCEV *getStep() const { return Step; } 173 const SCEV *getEnd() const { return End; } 174 bool isSigned() const { return IsSigned; } 175 176 void print(raw_ostream &OS) const { 177 OS << "InductiveRangeCheck:\n"; 178 OS << " Kind: " << rangeCheckKindToStr(Kind) << "\n"; 179 OS << " Begin: "; 180 Begin->print(OS); 181 OS << " Step: "; 182 Step->print(OS); 183 OS << " End: "; 184 End->print(OS); 185 OS << "\n CheckUse: "; 186 getCheckUse()->getUser()->print(OS); 187 OS << " Operand: " << getCheckUse()->getOperandNo() << "\n"; 188 } 189 190 LLVM_DUMP_METHOD 191 void dump() { 192 print(dbgs()); 193 } 194 195 Use *getCheckUse() const { return CheckUse; } 196 197 /// Represents an signed integer range [Range.getBegin(), Range.getEnd()). If 198 /// R.getEnd() le R.getBegin(), then R denotes the empty range. 199 200 class Range { 201 const SCEV *Begin; 202 const SCEV *End; 203 204 public: 205 Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) { 206 assert(Begin->getType() == End->getType() && "ill-typed range!"); 207 } 208 209 Type *getType() const { return Begin->getType(); } 210 const SCEV *getBegin() const { return Begin; } 211 const SCEV *getEnd() const { return End; } 212 bool isEmpty(ScalarEvolution &SE, bool IsSigned) const { 213 if (Begin == End) 214 return true; 215 if (IsSigned) 216 return SE.isKnownPredicate(ICmpInst::ICMP_SGE, Begin, End); 217 else 218 return SE.isKnownPredicate(ICmpInst::ICMP_UGE, Begin, End); 219 } 220 }; 221 222 /// This is the value the condition of the branch needs to evaluate to for the 223 /// branch to take the hot successor (see (1) above). 224 bool getPassingDirection() { return true; } 225 226 /// Computes a range for the induction variable (IndVar) in which the range 227 /// check is redundant and can be constant-folded away. The induction 228 /// variable is not required to be the canonical {0,+,1} induction variable. 229 Optional<Range> computeSafeIterationSpace(ScalarEvolution &SE, 230 const SCEVAddRecExpr *IndVar, 231 bool IsLatchSigned) const; 232 233 /// Parse out a set of inductive range checks from \p BI and append them to \p 234 /// Checks. 235 /// 236 /// NB! There may be conditions feeding into \p BI that aren't inductive range 237 /// checks, and hence don't end up in \p Checks. 238 static void 239 extractRangeChecksFromBranch(BranchInst *BI, Loop *L, ScalarEvolution &SE, 240 BranchProbabilityInfo *BPI, 241 SmallVectorImpl<InductiveRangeCheck> &Checks); 242 }; 243 244 class InductiveRangeCheckElimination { 245 ScalarEvolution &SE; 246 BranchProbabilityInfo *BPI; 247 DominatorTree &DT; 248 LoopInfo &LI; 249 250 public: 251 InductiveRangeCheckElimination(ScalarEvolution &SE, 252 BranchProbabilityInfo *BPI, DominatorTree &DT, 253 LoopInfo &LI) 254 : SE(SE), BPI(BPI), DT(DT), LI(LI) {} 255 256 bool run(Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop); 257 }; 258 259 class IRCELegacyPass : public LoopPass { 260 public: 261 static char ID; 262 263 IRCELegacyPass() : LoopPass(ID) { 264 initializeIRCELegacyPassPass(*PassRegistry::getPassRegistry()); 265 } 266 267 void getAnalysisUsage(AnalysisUsage &AU) const override { 268 AU.addRequired<BranchProbabilityInfoWrapperPass>(); 269 getLoopAnalysisUsage(AU); 270 } 271 272 bool runOnLoop(Loop *L, LPPassManager &LPM) override; 273 }; 274 275 } // end anonymous namespace 276 277 char IRCELegacyPass::ID = 0; 278 279 INITIALIZE_PASS_BEGIN(IRCELegacyPass, "irce", 280 "Inductive range check elimination", false, false) 281 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass) 282 INITIALIZE_PASS_DEPENDENCY(LoopPass) 283 INITIALIZE_PASS_END(IRCELegacyPass, "irce", "Inductive range check elimination", 284 false, false) 285 286 StringRef InductiveRangeCheck::rangeCheckKindToStr( 287 InductiveRangeCheck::RangeCheckKind RCK) { 288 switch (RCK) { 289 case InductiveRangeCheck::RANGE_CHECK_UNKNOWN: 290 return "RANGE_CHECK_UNKNOWN"; 291 292 case InductiveRangeCheck::RANGE_CHECK_UPPER: 293 return "RANGE_CHECK_UPPER"; 294 295 case InductiveRangeCheck::RANGE_CHECK_LOWER: 296 return "RANGE_CHECK_LOWER"; 297 298 case InductiveRangeCheck::RANGE_CHECK_BOTH: 299 return "RANGE_CHECK_BOTH"; 300 } 301 302 llvm_unreachable("unknown range check type!"); 303 } 304 305 /// Parse a single ICmp instruction, `ICI`, into a range check. If `ICI` cannot 306 /// be interpreted as a range check, return `RANGE_CHECK_UNKNOWN` and set 307 /// `Index` and `Length` to `nullptr`. Otherwise set `Index` to the value being 308 /// range checked, and set `Length` to the upper limit `Index` is being range 309 /// checked with if (and only if) the range check type is stronger or equal to 310 /// RANGE_CHECK_UPPER. 311 InductiveRangeCheck::RangeCheckKind 312 InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI, 313 ScalarEvolution &SE, Value *&Index, 314 Value *&Length, bool &IsSigned) { 315 auto IsLoopInvariant = [&SE, L](Value *V) { 316 return SE.isLoopInvariant(SE.getSCEV(V), L); 317 }; 318 319 ICmpInst::Predicate Pred = ICI->getPredicate(); 320 Value *LHS = ICI->getOperand(0); 321 Value *RHS = ICI->getOperand(1); 322 323 switch (Pred) { 324 default: 325 return RANGE_CHECK_UNKNOWN; 326 327 case ICmpInst::ICMP_SLE: 328 std::swap(LHS, RHS); 329 LLVM_FALLTHROUGH; 330 case ICmpInst::ICMP_SGE: 331 IsSigned = true; 332 if (match(RHS, m_ConstantInt<0>())) { 333 Index = LHS; 334 return RANGE_CHECK_LOWER; 335 } 336 return RANGE_CHECK_UNKNOWN; 337 338 case ICmpInst::ICMP_SLT: 339 std::swap(LHS, RHS); 340 LLVM_FALLTHROUGH; 341 case ICmpInst::ICMP_SGT: 342 IsSigned = true; 343 if (match(RHS, m_ConstantInt<-1>())) { 344 Index = LHS; 345 return RANGE_CHECK_LOWER; 346 } 347 348 if (IsLoopInvariant(LHS)) { 349 Index = RHS; 350 Length = LHS; 351 return RANGE_CHECK_UPPER; 352 } 353 return RANGE_CHECK_UNKNOWN; 354 355 case ICmpInst::ICMP_ULT: 356 std::swap(LHS, RHS); 357 LLVM_FALLTHROUGH; 358 case ICmpInst::ICMP_UGT: 359 IsSigned = false; 360 if (IsLoopInvariant(LHS)) { 361 Index = RHS; 362 Length = LHS; 363 return RANGE_CHECK_BOTH; 364 } 365 return RANGE_CHECK_UNKNOWN; 366 } 367 368 llvm_unreachable("default clause returns!"); 369 } 370 371 void InductiveRangeCheck::extractRangeChecksFromCond( 372 Loop *L, ScalarEvolution &SE, Use &ConditionUse, 373 SmallVectorImpl<InductiveRangeCheck> &Checks, 374 SmallPtrSetImpl<Value *> &Visited) { 375 Value *Condition = ConditionUse.get(); 376 if (!Visited.insert(Condition).second) 377 return; 378 379 // TODO: Do the same for OR, XOR, NOT etc? 380 if (match(Condition, m_And(m_Value(), m_Value()))) { 381 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0), 382 Checks, Visited); 383 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1), 384 Checks, Visited); 385 return; 386 } 387 388 ICmpInst *ICI = dyn_cast<ICmpInst>(Condition); 389 if (!ICI) 390 return; 391 392 Value *Length = nullptr, *Index; 393 bool IsSigned; 394 auto RCKind = parseRangeCheckICmp(L, ICI, SE, Index, Length, IsSigned); 395 if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN) 396 return; 397 398 const auto *IndexAddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Index)); 399 bool IsAffineIndex = 400 IndexAddRec && (IndexAddRec->getLoop() == L) && IndexAddRec->isAffine(); 401 402 if (!IsAffineIndex) 403 return; 404 405 const SCEV *End = nullptr; 406 // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L". 407 // We can potentially do much better here. 408 if (Length) 409 End = SE.getSCEV(Length); 410 else { 411 assert(RCKind == InductiveRangeCheck::RANGE_CHECK_LOWER && "invariant!"); 412 // So far we can only reach this point for Signed range check. This may 413 // change in future. In this case we will need to pick Unsigned max for the 414 // unsigned range check. 415 unsigned BitWidth = cast<IntegerType>(IndexAddRec->getType())->getBitWidth(); 416 const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth)); 417 End = SIntMax; 418 } 419 420 InductiveRangeCheck IRC; 421 IRC.End = End; 422 IRC.Begin = IndexAddRec->getStart(); 423 IRC.Step = IndexAddRec->getStepRecurrence(SE); 424 IRC.CheckUse = &ConditionUse; 425 IRC.Kind = RCKind; 426 IRC.IsSigned = IsSigned; 427 Checks.push_back(IRC); 428 } 429 430 void InductiveRangeCheck::extractRangeChecksFromBranch( 431 BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI, 432 SmallVectorImpl<InductiveRangeCheck> &Checks) { 433 if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch()) 434 return; 435 436 BranchProbability LikelyTaken(15, 16); 437 438 if (!SkipProfitabilityChecks && BPI && 439 BPI->getEdgeProbability(BI->getParent(), (unsigned)0) < LikelyTaken) 440 return; 441 442 SmallPtrSet<Value *, 8> Visited; 443 InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->getOperandUse(0), 444 Checks, Visited); 445 } 446 447 // Add metadata to the loop L to disable loop optimizations. Callers need to 448 // confirm that optimizing loop L is not beneficial. 449 static void DisableAllLoopOptsOnLoop(Loop &L) { 450 // We do not care about any existing loopID related metadata for L, since we 451 // are setting all loop metadata to false. 452 LLVMContext &Context = L.getHeader()->getContext(); 453 // Reserve first location for self reference to the LoopID metadata node. 454 MDNode *Dummy = MDNode::get(Context, {}); 455 MDNode *DisableUnroll = MDNode::get( 456 Context, {MDString::get(Context, "llvm.loop.unroll.disable")}); 457 Metadata *FalseVal = 458 ConstantAsMetadata::get(ConstantInt::get(Type::getInt1Ty(Context), 0)); 459 MDNode *DisableVectorize = MDNode::get( 460 Context, 461 {MDString::get(Context, "llvm.loop.vectorize.enable"), FalseVal}); 462 MDNode *DisableLICMVersioning = MDNode::get( 463 Context, {MDString::get(Context, "llvm.loop.licm_versioning.disable")}); 464 MDNode *DisableDistribution= MDNode::get( 465 Context, 466 {MDString::get(Context, "llvm.loop.distribute.enable"), FalseVal}); 467 MDNode *NewLoopID = 468 MDNode::get(Context, {Dummy, DisableUnroll, DisableVectorize, 469 DisableLICMVersioning, DisableDistribution}); 470 // Set operand 0 to refer to the loop id itself. 471 NewLoopID->replaceOperandWith(0, NewLoopID); 472 L.setLoopID(NewLoopID); 473 } 474 475 namespace { 476 477 // Keeps track of the structure of a loop. This is similar to llvm::Loop, 478 // except that it is more lightweight and can track the state of a loop through 479 // changing and potentially invalid IR. This structure also formalizes the 480 // kinds of loops we can deal with -- ones that have a single latch that is also 481 // an exiting block *and* have a canonical induction variable. 482 struct LoopStructure { 483 const char *Tag = ""; 484 485 BasicBlock *Header = nullptr; 486 BasicBlock *Latch = nullptr; 487 488 // `Latch's terminator instruction is `LatchBr', and it's `LatchBrExitIdx'th 489 // successor is `LatchExit', the exit block of the loop. 490 BranchInst *LatchBr = nullptr; 491 BasicBlock *LatchExit = nullptr; 492 unsigned LatchBrExitIdx = std::numeric_limits<unsigned>::max(); 493 494 // The loop represented by this instance of LoopStructure is semantically 495 // equivalent to: 496 // 497 // intN_ty inc = IndVarIncreasing ? 1 : -1; 498 // pred_ty predicate = IndVarIncreasing ? ICMP_SLT : ICMP_SGT; 499 // 500 // for (intN_ty iv = IndVarStart; predicate(iv, LoopExitAt); iv = IndVarBase) 501 // ... body ... 502 503 Value *IndVarBase = nullptr; 504 Value *IndVarStart = nullptr; 505 Value *IndVarStep = nullptr; 506 Value *LoopExitAt = nullptr; 507 bool IndVarIncreasing = false; 508 bool IsSignedPredicate = true; 509 510 LoopStructure() = default; 511 512 template <typename M> LoopStructure map(M Map) const { 513 LoopStructure Result; 514 Result.Tag = Tag; 515 Result.Header = cast<BasicBlock>(Map(Header)); 516 Result.Latch = cast<BasicBlock>(Map(Latch)); 517 Result.LatchBr = cast<BranchInst>(Map(LatchBr)); 518 Result.LatchExit = cast<BasicBlock>(Map(LatchExit)); 519 Result.LatchBrExitIdx = LatchBrExitIdx; 520 Result.IndVarBase = Map(IndVarBase); 521 Result.IndVarStart = Map(IndVarStart); 522 Result.IndVarStep = Map(IndVarStep); 523 Result.LoopExitAt = Map(LoopExitAt); 524 Result.IndVarIncreasing = IndVarIncreasing; 525 Result.IsSignedPredicate = IsSignedPredicate; 526 return Result; 527 } 528 529 static Optional<LoopStructure> parseLoopStructure(ScalarEvolution &, 530 BranchProbabilityInfo *BPI, 531 Loop &, const char *&); 532 }; 533 534 /// This class is used to constrain loops to run within a given iteration space. 535 /// The algorithm this class implements is given a Loop and a range [Begin, 536 /// End). The algorithm then tries to break out a "main loop" out of the loop 537 /// it is given in a way that the "main loop" runs with the induction variable 538 /// in a subset of [Begin, End). The algorithm emits appropriate pre and post 539 /// loops to run any remaining iterations. The pre loop runs any iterations in 540 /// which the induction variable is < Begin, and the post loop runs any 541 /// iterations in which the induction variable is >= End. 542 class LoopConstrainer { 543 // The representation of a clone of the original loop we started out with. 544 struct ClonedLoop { 545 // The cloned blocks 546 std::vector<BasicBlock *> Blocks; 547 548 // `Map` maps values in the clonee into values in the cloned version 549 ValueToValueMapTy Map; 550 551 // An instance of `LoopStructure` for the cloned loop 552 LoopStructure Structure; 553 }; 554 555 // Result of rewriting the range of a loop. See changeIterationSpaceEnd for 556 // more details on what these fields mean. 557 struct RewrittenRangeInfo { 558 BasicBlock *PseudoExit = nullptr; 559 BasicBlock *ExitSelector = nullptr; 560 std::vector<PHINode *> PHIValuesAtPseudoExit; 561 PHINode *IndVarEnd = nullptr; 562 563 RewrittenRangeInfo() = default; 564 }; 565 566 // Calculated subranges we restrict the iteration space of the main loop to. 567 // See the implementation of `calculateSubRanges' for more details on how 568 // these fields are computed. `LowLimit` is None if there is no restriction 569 // on low end of the restricted iteration space of the main loop. `HighLimit` 570 // is None if there is no restriction on high end of the restricted iteration 571 // space of the main loop. 572 573 struct SubRanges { 574 Optional<const SCEV *> LowLimit; 575 Optional<const SCEV *> HighLimit; 576 }; 577 578 // A utility function that does a `replaceUsesOfWith' on the incoming block 579 // set of a `PHINode' -- replaces instances of `Block' in the `PHINode's 580 // incoming block list with `ReplaceBy'. 581 static void replacePHIBlock(PHINode *PN, BasicBlock *Block, 582 BasicBlock *ReplaceBy); 583 584 // Compute a safe set of limits for the main loop to run in -- effectively the 585 // intersection of `Range' and the iteration space of the original loop. 586 // Return None if unable to compute the set of subranges. 587 Optional<SubRanges> calculateSubRanges(bool IsSignedPredicate) const; 588 589 // Clone `OriginalLoop' and return the result in CLResult. The IR after 590 // running `cloneLoop' is well formed except for the PHI nodes in CLResult -- 591 // the PHI nodes say that there is an incoming edge from `OriginalPreheader` 592 // but there is no such edge. 593 void cloneLoop(ClonedLoop &CLResult, const char *Tag) const; 594 595 // Create the appropriate loop structure needed to describe a cloned copy of 596 // `Original`. The clone is described by `VM`. 597 Loop *createClonedLoopStructure(Loop *Original, Loop *Parent, 598 ValueToValueMapTy &VM, bool IsSubloop); 599 600 // Rewrite the iteration space of the loop denoted by (LS, Preheader). The 601 // iteration space of the rewritten loop ends at ExitLoopAt. The start of the 602 // iteration space is not changed. `ExitLoopAt' is assumed to be slt 603 // `OriginalHeaderCount'. 604 // 605 // If there are iterations left to execute, control is made to jump to 606 // `ContinuationBlock', otherwise they take the normal loop exit. The 607 // returned `RewrittenRangeInfo' object is populated as follows: 608 // 609 // .PseudoExit is a basic block that unconditionally branches to 610 // `ContinuationBlock'. 611 // 612 // .ExitSelector is a basic block that decides, on exit from the loop, 613 // whether to branch to the "true" exit or to `PseudoExit'. 614 // 615 // .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value 616 // for each PHINode in the loop header on taking the pseudo exit. 617 // 618 // After changeIterationSpaceEnd, `Preheader' is no longer a legitimate 619 // preheader because it is made to branch to the loop header only 620 // conditionally. 621 RewrittenRangeInfo 622 changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *Preheader, 623 Value *ExitLoopAt, 624 BasicBlock *ContinuationBlock) const; 625 626 // The loop denoted by `LS' has `OldPreheader' as its preheader. This 627 // function creates a new preheader for `LS' and returns it. 628 BasicBlock *createPreheader(const LoopStructure &LS, BasicBlock *OldPreheader, 629 const char *Tag) const; 630 631 // `ContinuationBlockAndPreheader' was the continuation block for some call to 632 // `changeIterationSpaceEnd' and is the preheader to the loop denoted by `LS'. 633 // This function rewrites the PHI nodes in `LS.Header' to start with the 634 // correct value. 635 void rewriteIncomingValuesForPHIs( 636 LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader, 637 const LoopConstrainer::RewrittenRangeInfo &RRI) const; 638 639 // Even though we do not preserve any passes at this time, we at least need to 640 // keep the parent loop structure consistent. The `LPPassManager' seems to 641 // verify this after running a loop pass. This function adds the list of 642 // blocks denoted by BBs to this loops parent loop if required. 643 void addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs); 644 645 // Some global state. 646 Function &F; 647 LLVMContext &Ctx; 648 ScalarEvolution &SE; 649 DominatorTree &DT; 650 LoopInfo &LI; 651 function_ref<void(Loop *, bool)> LPMAddNewLoop; 652 653 // Information about the original loop we started out with. 654 Loop &OriginalLoop; 655 656 const SCEV *LatchTakenCount = nullptr; 657 BasicBlock *OriginalPreheader = nullptr; 658 659 // The preheader of the main loop. This may or may not be different from 660 // `OriginalPreheader'. 661 BasicBlock *MainLoopPreheader = nullptr; 662 663 // The range we need to run the main loop in. 664 InductiveRangeCheck::Range Range; 665 666 // The structure of the main loop (see comment at the beginning of this class 667 // for a definition) 668 LoopStructure MainLoopStructure; 669 670 public: 671 LoopConstrainer(Loop &L, LoopInfo &LI, 672 function_ref<void(Loop *, bool)> LPMAddNewLoop, 673 const LoopStructure &LS, ScalarEvolution &SE, 674 DominatorTree &DT, InductiveRangeCheck::Range R) 675 : F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()), 676 SE(SE), DT(DT), LI(LI), LPMAddNewLoop(LPMAddNewLoop), OriginalLoop(L), 677 Range(R), MainLoopStructure(LS) {} 678 679 // Entry point for the algorithm. Returns true on success. 680 bool run(); 681 }; 682 683 } // end anonymous namespace 684 685 void LoopConstrainer::replacePHIBlock(PHINode *PN, BasicBlock *Block, 686 BasicBlock *ReplaceBy) { 687 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 688 if (PN->getIncomingBlock(i) == Block) 689 PN->setIncomingBlock(i, ReplaceBy); 690 } 691 692 static bool CannotBeMaxInLoop(const SCEV *BoundSCEV, Loop *L, 693 ScalarEvolution &SE, bool Signed) { 694 unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth(); 695 APInt Max = Signed ? APInt::getSignedMaxValue(BitWidth) : 696 APInt::getMaxValue(BitWidth); 697 auto Predicate = Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; 698 return SE.isAvailableAtLoopEntry(BoundSCEV, L) && 699 SE.isLoopEntryGuardedByCond(L, Predicate, BoundSCEV, 700 SE.getConstant(Max)); 701 } 702 703 /// Given a loop with an deccreasing induction variable, is it possible to 704 /// safely calculate the bounds of a new loop using the given Predicate. 705 static bool isSafeDecreasingBound(const SCEV *Start, 706 const SCEV *BoundSCEV, const SCEV *Step, 707 ICmpInst::Predicate Pred, 708 unsigned LatchBrExitIdx, 709 Loop *L, ScalarEvolution &SE) { 710 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT && 711 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT) 712 return false; 713 714 if (!SE.isAvailableAtLoopEntry(BoundSCEV, L)) 715 return false; 716 717 assert(SE.isKnownNegative(Step) && "expecting negative step"); 718 719 LLVM_DEBUG(dbgs() << "irce: isSafeDecreasingBound with:\n"); 720 LLVM_DEBUG(dbgs() << "irce: Start: " << *Start << "\n"); 721 LLVM_DEBUG(dbgs() << "irce: Step: " << *Step << "\n"); 722 LLVM_DEBUG(dbgs() << "irce: BoundSCEV: " << *BoundSCEV << "\n"); 723 LLVM_DEBUG(dbgs() << "irce: Pred: " << ICmpInst::getPredicateName(Pred) 724 << "\n"); 725 LLVM_DEBUG(dbgs() << "irce: LatchExitBrIdx: " << LatchBrExitIdx << "\n"); 726 727 bool IsSigned = ICmpInst::isSigned(Pred); 728 // The predicate that we need to check that the induction variable lies 729 // within bounds. 730 ICmpInst::Predicate BoundPred = 731 IsSigned ? CmpInst::ICMP_SGT : CmpInst::ICMP_UGT; 732 733 if (LatchBrExitIdx == 1) 734 return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, BoundSCEV); 735 736 assert(LatchBrExitIdx == 0 && 737 "LatchBrExitIdx should be either 0 or 1"); 738 739 const SCEV *StepPlusOne = SE.getAddExpr(Step, SE.getOne(Step->getType())); 740 unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth(); 741 APInt Min = IsSigned ? APInt::getSignedMinValue(BitWidth) : 742 APInt::getMinValue(BitWidth); 743 const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Min), StepPlusOne); 744 745 const SCEV *MinusOne = 746 SE.getMinusSCEV(BoundSCEV, SE.getOne(BoundSCEV->getType())); 747 748 return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, MinusOne) && 749 SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit); 750 751 } 752 753 /// Given a loop with an increasing induction variable, is it possible to 754 /// safely calculate the bounds of a new loop using the given Predicate. 755 static bool isSafeIncreasingBound(const SCEV *Start, 756 const SCEV *BoundSCEV, const SCEV *Step, 757 ICmpInst::Predicate Pred, 758 unsigned LatchBrExitIdx, 759 Loop *L, ScalarEvolution &SE) { 760 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT && 761 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT) 762 return false; 763 764 if (!SE.isAvailableAtLoopEntry(BoundSCEV, L)) 765 return false; 766 767 LLVM_DEBUG(dbgs() << "irce: isSafeIncreasingBound with:\n"); 768 LLVM_DEBUG(dbgs() << "irce: Start: " << *Start << "\n"); 769 LLVM_DEBUG(dbgs() << "irce: Step: " << *Step << "\n"); 770 LLVM_DEBUG(dbgs() << "irce: BoundSCEV: " << *BoundSCEV << "\n"); 771 LLVM_DEBUG(dbgs() << "irce: Pred: " << ICmpInst::getPredicateName(Pred) 772 << "\n"); 773 LLVM_DEBUG(dbgs() << "irce: LatchExitBrIdx: " << LatchBrExitIdx << "\n"); 774 775 bool IsSigned = ICmpInst::isSigned(Pred); 776 // The predicate that we need to check that the induction variable lies 777 // within bounds. 778 ICmpInst::Predicate BoundPred = 779 IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT; 780 781 if (LatchBrExitIdx == 1) 782 return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, BoundSCEV); 783 784 assert(LatchBrExitIdx == 0 && "LatchBrExitIdx should be 0 or 1"); 785 786 const SCEV *StepMinusOne = 787 SE.getMinusSCEV(Step, SE.getOne(Step->getType())); 788 unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth(); 789 APInt Max = IsSigned ? APInt::getSignedMaxValue(BitWidth) : 790 APInt::getMaxValue(BitWidth); 791 const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Max), StepMinusOne); 792 793 return (SE.isLoopEntryGuardedByCond(L, BoundPred, Start, 794 SE.getAddExpr(BoundSCEV, Step)) && 795 SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit)); 796 } 797 798 static bool CannotBeMinInLoop(const SCEV *BoundSCEV, Loop *L, 799 ScalarEvolution &SE, bool Signed) { 800 unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth(); 801 APInt Min = Signed ? APInt::getSignedMinValue(BitWidth) : 802 APInt::getMinValue(BitWidth); 803 auto Predicate = Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; 804 return SE.isAvailableAtLoopEntry(BoundSCEV, L) && 805 SE.isLoopEntryGuardedByCond(L, Predicate, BoundSCEV, 806 SE.getConstant(Min)); 807 } 808 809 static bool isKnownNonNegativeInLoop(const SCEV *BoundSCEV, const Loop *L, 810 ScalarEvolution &SE) { 811 const SCEV *Zero = SE.getZero(BoundSCEV->getType()); 812 return SE.isAvailableAtLoopEntry(BoundSCEV, L) && 813 SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, BoundSCEV, Zero); 814 } 815 816 static bool isKnownNegativeInLoop(const SCEV *BoundSCEV, const Loop *L, 817 ScalarEvolution &SE) { 818 const SCEV *Zero = SE.getZero(BoundSCEV->getType()); 819 return SE.isAvailableAtLoopEntry(BoundSCEV, L) && 820 SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, BoundSCEV, Zero); 821 } 822 823 Optional<LoopStructure> 824 LoopStructure::parseLoopStructure(ScalarEvolution &SE, 825 BranchProbabilityInfo *BPI, Loop &L, 826 const char *&FailureReason) { 827 if (!L.isLoopSimplifyForm()) { 828 FailureReason = "loop not in LoopSimplify form"; 829 return None; 830 } 831 832 BasicBlock *Latch = L.getLoopLatch(); 833 assert(Latch && "Simplified loops only have one latch!"); 834 835 if (Latch->getTerminator()->getMetadata(ClonedLoopTag)) { 836 FailureReason = "loop has already been cloned"; 837 return None; 838 } 839 840 if (!L.isLoopExiting(Latch)) { 841 FailureReason = "no loop latch"; 842 return None; 843 } 844 845 BasicBlock *Header = L.getHeader(); 846 BasicBlock *Preheader = L.getLoopPreheader(); 847 if (!Preheader) { 848 FailureReason = "no preheader"; 849 return None; 850 } 851 852 BranchInst *LatchBr = dyn_cast<BranchInst>(Latch->getTerminator()); 853 if (!LatchBr || LatchBr->isUnconditional()) { 854 FailureReason = "latch terminator not conditional branch"; 855 return None; 856 } 857 858 unsigned LatchBrExitIdx = LatchBr->getSuccessor(0) == Header ? 1 : 0; 859 860 BranchProbability ExitProbability = 861 BPI ? BPI->getEdgeProbability(LatchBr->getParent(), LatchBrExitIdx) 862 : BranchProbability::getZero(); 863 864 if (!SkipProfitabilityChecks && 865 ExitProbability > BranchProbability(1, MaxExitProbReciprocal)) { 866 FailureReason = "short running loop, not profitable"; 867 return None; 868 } 869 870 ICmpInst *ICI = dyn_cast<ICmpInst>(LatchBr->getCondition()); 871 if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType())) { 872 FailureReason = "latch terminator branch not conditional on integral icmp"; 873 return None; 874 } 875 876 const SCEV *LatchCount = SE.getExitCount(&L, Latch); 877 if (isa<SCEVCouldNotCompute>(LatchCount)) { 878 FailureReason = "could not compute latch count"; 879 return None; 880 } 881 882 ICmpInst::Predicate Pred = ICI->getPredicate(); 883 Value *LeftValue = ICI->getOperand(0); 884 const SCEV *LeftSCEV = SE.getSCEV(LeftValue); 885 IntegerType *IndVarTy = cast<IntegerType>(LeftValue->getType()); 886 887 Value *RightValue = ICI->getOperand(1); 888 const SCEV *RightSCEV = SE.getSCEV(RightValue); 889 890 // We canonicalize `ICI` such that `LeftSCEV` is an add recurrence. 891 if (!isa<SCEVAddRecExpr>(LeftSCEV)) { 892 if (isa<SCEVAddRecExpr>(RightSCEV)) { 893 std::swap(LeftSCEV, RightSCEV); 894 std::swap(LeftValue, RightValue); 895 Pred = ICmpInst::getSwappedPredicate(Pred); 896 } else { 897 FailureReason = "no add recurrences in the icmp"; 898 return None; 899 } 900 } 901 902 auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) { 903 if (AR->getNoWrapFlags(SCEV::FlagNSW)) 904 return true; 905 906 IntegerType *Ty = cast<IntegerType>(AR->getType()); 907 IntegerType *WideTy = 908 IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2); 909 910 const SCEVAddRecExpr *ExtendAfterOp = 911 dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy)); 912 if (ExtendAfterOp) { 913 const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy); 914 const SCEV *ExtendedStep = 915 SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy); 916 917 bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart && 918 ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep; 919 920 if (NoSignedWrap) 921 return true; 922 } 923 924 // We may have proved this when computing the sign extension above. 925 return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap; 926 }; 927 928 // `ICI` is interpreted as taking the backedge if the *next* value of the 929 // induction variable satisfies some constraint. 930 931 const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(LeftSCEV); 932 if (!IndVarBase->isAffine()) { 933 FailureReason = "LHS in icmp not induction variable"; 934 return None; 935 } 936 const SCEV* StepRec = IndVarBase->getStepRecurrence(SE); 937 if (!isa<SCEVConstant>(StepRec)) { 938 FailureReason = "LHS in icmp not induction variable"; 939 return None; 940 } 941 ConstantInt *StepCI = cast<SCEVConstant>(StepRec)->getValue(); 942 943 if (ICI->isEquality() && !HasNoSignedWrap(IndVarBase)) { 944 FailureReason = "LHS in icmp needs nsw for equality predicates"; 945 return None; 946 } 947 948 assert(!StepCI->isZero() && "Zero step?"); 949 bool IsIncreasing = !StepCI->isNegative(); 950 bool IsSignedPredicate = ICmpInst::isSigned(Pred); 951 const SCEV *StartNext = IndVarBase->getStart(); 952 const SCEV *Addend = SE.getNegativeSCEV(IndVarBase->getStepRecurrence(SE)); 953 const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend); 954 const SCEV *Step = SE.getSCEV(StepCI); 955 956 ConstantInt *One = ConstantInt::get(IndVarTy, 1); 957 if (IsIncreasing) { 958 bool DecreasedRightValueByOne = false; 959 if (StepCI->isOne()) { 960 // Try to turn eq/ne predicates to those we can work with. 961 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1) 962 // while (++i != len) { while (++i < len) { 963 // ... ---> ... 964 // } } 965 // If both parts are known non-negative, it is profitable to use 966 // unsigned comparison in increasing loop. This allows us to make the 967 // comparison check against "RightSCEV + 1" more optimistic. 968 if (isKnownNonNegativeInLoop(IndVarStart, &L, SE) && 969 isKnownNonNegativeInLoop(RightSCEV, &L, SE)) 970 Pred = ICmpInst::ICMP_ULT; 971 else 972 Pred = ICmpInst::ICMP_SLT; 973 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) { 974 // while (true) { while (true) { 975 // if (++i == len) ---> if (++i > len - 1) 976 // break; break; 977 // ... ... 978 // } } 979 if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) && 980 CannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/false)) { 981 Pred = ICmpInst::ICMP_UGT; 982 RightSCEV = SE.getMinusSCEV(RightSCEV, 983 SE.getOne(RightSCEV->getType())); 984 DecreasedRightValueByOne = true; 985 } else if (CannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/true)) { 986 Pred = ICmpInst::ICMP_SGT; 987 RightSCEV = SE.getMinusSCEV(RightSCEV, 988 SE.getOne(RightSCEV->getType())); 989 DecreasedRightValueByOne = true; 990 } 991 } 992 } 993 994 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT); 995 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT); 996 bool FoundExpectedPred = 997 (LTPred && LatchBrExitIdx == 1) || (GTPred && LatchBrExitIdx == 0); 998 999 if (!FoundExpectedPred) { 1000 FailureReason = "expected icmp slt semantically, found something else"; 1001 return None; 1002 } 1003 1004 IsSignedPredicate = ICmpInst::isSigned(Pred); 1005 if (!IsSignedPredicate && !AllowUnsignedLatchCondition) { 1006 FailureReason = "unsigned latch conditions are explicitly prohibited"; 1007 return None; 1008 } 1009 1010 if (!isSafeIncreasingBound(IndVarStart, RightSCEV, Step, Pred, 1011 LatchBrExitIdx, &L, SE)) { 1012 FailureReason = "Unsafe loop bounds"; 1013 return None; 1014 } 1015 if (LatchBrExitIdx == 0) { 1016 // We need to increase the right value unless we have already decreased 1017 // it virtually when we replaced EQ with SGT. 1018 if (!DecreasedRightValueByOne) { 1019 IRBuilder<> B(Preheader->getTerminator()); 1020 RightValue = B.CreateAdd(RightValue, One); 1021 } 1022 } else { 1023 assert(!DecreasedRightValueByOne && 1024 "Right value can be decreased only for LatchBrExitIdx == 0!"); 1025 } 1026 } else { 1027 bool IncreasedRightValueByOne = false; 1028 if (StepCI->isMinusOne()) { 1029 // Try to turn eq/ne predicates to those we can work with. 1030 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1) 1031 // while (--i != len) { while (--i > len) { 1032 // ... ---> ... 1033 // } } 1034 // We intentionally don't turn the predicate into UGT even if we know 1035 // that both operands are non-negative, because it will only pessimize 1036 // our check against "RightSCEV - 1". 1037 Pred = ICmpInst::ICMP_SGT; 1038 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) { 1039 // while (true) { while (true) { 1040 // if (--i == len) ---> if (--i < len + 1) 1041 // break; break; 1042 // ... ... 1043 // } } 1044 if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) && 1045 CannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ false)) { 1046 Pred = ICmpInst::ICMP_ULT; 1047 RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType())); 1048 IncreasedRightValueByOne = true; 1049 } else if (CannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ true)) { 1050 Pred = ICmpInst::ICMP_SLT; 1051 RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType())); 1052 IncreasedRightValueByOne = true; 1053 } 1054 } 1055 } 1056 1057 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT); 1058 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT); 1059 1060 bool FoundExpectedPred = 1061 (GTPred && LatchBrExitIdx == 1) || (LTPred && LatchBrExitIdx == 0); 1062 1063 if (!FoundExpectedPred) { 1064 FailureReason = "expected icmp sgt semantically, found something else"; 1065 return None; 1066 } 1067 1068 IsSignedPredicate = 1069 Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT; 1070 1071 if (!IsSignedPredicate && !AllowUnsignedLatchCondition) { 1072 FailureReason = "unsigned latch conditions are explicitly prohibited"; 1073 return None; 1074 } 1075 1076 if (!isSafeDecreasingBound(IndVarStart, RightSCEV, Step, Pred, 1077 LatchBrExitIdx, &L, SE)) { 1078 FailureReason = "Unsafe bounds"; 1079 return None; 1080 } 1081 1082 if (LatchBrExitIdx == 0) { 1083 // We need to decrease the right value unless we have already increased 1084 // it virtually when we replaced EQ with SLT. 1085 if (!IncreasedRightValueByOne) { 1086 IRBuilder<> B(Preheader->getTerminator()); 1087 RightValue = B.CreateSub(RightValue, One); 1088 } 1089 } else { 1090 assert(!IncreasedRightValueByOne && 1091 "Right value can be increased only for LatchBrExitIdx == 0!"); 1092 } 1093 } 1094 BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx); 1095 1096 assert(SE.getLoopDisposition(LatchCount, &L) == 1097 ScalarEvolution::LoopInvariant && 1098 "loop variant exit count doesn't make sense!"); 1099 1100 assert(!L.contains(LatchExit) && "expected an exit block!"); 1101 const DataLayout &DL = Preheader->getModule()->getDataLayout(); 1102 Value *IndVarStartV = 1103 SCEVExpander(SE, DL, "irce") 1104 .expandCodeFor(IndVarStart, IndVarTy, Preheader->getTerminator()); 1105 IndVarStartV->setName("indvar.start"); 1106 1107 LoopStructure Result; 1108 1109 Result.Tag = "main"; 1110 Result.Header = Header; 1111 Result.Latch = Latch; 1112 Result.LatchBr = LatchBr; 1113 Result.LatchExit = LatchExit; 1114 Result.LatchBrExitIdx = LatchBrExitIdx; 1115 Result.IndVarStart = IndVarStartV; 1116 Result.IndVarStep = StepCI; 1117 Result.IndVarBase = LeftValue; 1118 Result.IndVarIncreasing = IsIncreasing; 1119 Result.LoopExitAt = RightValue; 1120 Result.IsSignedPredicate = IsSignedPredicate; 1121 1122 FailureReason = nullptr; 1123 1124 return Result; 1125 } 1126 1127 Optional<LoopConstrainer::SubRanges> 1128 LoopConstrainer::calculateSubRanges(bool IsSignedPredicate) const { 1129 IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType()); 1130 1131 if (Range.getType() != Ty) 1132 return None; 1133 1134 LoopConstrainer::SubRanges Result; 1135 1136 // I think we can be more aggressive here and make this nuw / nsw if the 1137 // addition that feeds into the icmp for the latch's terminating branch is nuw 1138 // / nsw. In any case, a wrapping 2's complement addition is safe. 1139 const SCEV *Start = SE.getSCEV(MainLoopStructure.IndVarStart); 1140 const SCEV *End = SE.getSCEV(MainLoopStructure.LoopExitAt); 1141 1142 bool Increasing = MainLoopStructure.IndVarIncreasing; 1143 1144 // We compute `Smallest` and `Greatest` such that [Smallest, Greatest), or 1145 // [Smallest, GreatestSeen] is the range of values the induction variable 1146 // takes. 1147 1148 const SCEV *Smallest = nullptr, *Greatest = nullptr, *GreatestSeen = nullptr; 1149 1150 const SCEV *One = SE.getOne(Ty); 1151 if (Increasing) { 1152 Smallest = Start; 1153 Greatest = End; 1154 // No overflow, because the range [Smallest, GreatestSeen] is not empty. 1155 GreatestSeen = SE.getMinusSCEV(End, One); 1156 } else { 1157 // These two computations may sign-overflow. Here is why that is okay: 1158 // 1159 // We know that the induction variable does not sign-overflow on any 1160 // iteration except the last one, and it starts at `Start` and ends at 1161 // `End`, decrementing by one every time. 1162 // 1163 // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the 1164 // induction variable is decreasing we know that that the smallest value 1165 // the loop body is actually executed with is `INT_SMIN` == `Smallest`. 1166 // 1167 // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In 1168 // that case, `Clamp` will always return `Smallest` and 1169 // [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`) 1170 // will be an empty range. Returning an empty range is always safe. 1171 1172 Smallest = SE.getAddExpr(End, One); 1173 Greatest = SE.getAddExpr(Start, One); 1174 GreatestSeen = Start; 1175 } 1176 1177 auto Clamp = [this, Smallest, Greatest, IsSignedPredicate](const SCEV *S) { 1178 return IsSignedPredicate 1179 ? SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S)) 1180 : SE.getUMaxExpr(Smallest, SE.getUMinExpr(Greatest, S)); 1181 }; 1182 1183 // In some cases we can prove that we don't need a pre or post loop. 1184 ICmpInst::Predicate PredLE = 1185 IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; 1186 ICmpInst::Predicate PredLT = 1187 IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; 1188 1189 bool ProvablyNoPreloop = 1190 SE.isKnownPredicate(PredLE, Range.getBegin(), Smallest); 1191 if (!ProvablyNoPreloop) 1192 Result.LowLimit = Clamp(Range.getBegin()); 1193 1194 bool ProvablyNoPostLoop = 1195 SE.isKnownPredicate(PredLT, GreatestSeen, Range.getEnd()); 1196 if (!ProvablyNoPostLoop) 1197 Result.HighLimit = Clamp(Range.getEnd()); 1198 1199 return Result; 1200 } 1201 1202 void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result, 1203 const char *Tag) const { 1204 for (BasicBlock *BB : OriginalLoop.getBlocks()) { 1205 BasicBlock *Clone = CloneBasicBlock(BB, Result.Map, Twine(".") + Tag, &F); 1206 Result.Blocks.push_back(Clone); 1207 Result.Map[BB] = Clone; 1208 } 1209 1210 auto GetClonedValue = [&Result](Value *V) { 1211 assert(V && "null values not in domain!"); 1212 auto It = Result.Map.find(V); 1213 if (It == Result.Map.end()) 1214 return V; 1215 return static_cast<Value *>(It->second); 1216 }; 1217 1218 auto *ClonedLatch = 1219 cast<BasicBlock>(GetClonedValue(OriginalLoop.getLoopLatch())); 1220 ClonedLatch->getTerminator()->setMetadata(ClonedLoopTag, 1221 MDNode::get(Ctx, {})); 1222 1223 Result.Structure = MainLoopStructure.map(GetClonedValue); 1224 Result.Structure.Tag = Tag; 1225 1226 for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) { 1227 BasicBlock *ClonedBB = Result.Blocks[i]; 1228 BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i]; 1229 1230 assert(Result.Map[OriginalBB] == ClonedBB && "invariant!"); 1231 1232 for (Instruction &I : *ClonedBB) 1233 RemapInstruction(&I, Result.Map, 1234 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); 1235 1236 // Exit blocks will now have one more predecessor and their PHI nodes need 1237 // to be edited to reflect that. No phi nodes need to be introduced because 1238 // the loop is in LCSSA. 1239 1240 for (auto *SBB : successors(OriginalBB)) { 1241 if (OriginalLoop.contains(SBB)) 1242 continue; // not an exit block 1243 1244 for (PHINode &PN : SBB->phis()) { 1245 Value *OldIncoming = PN.getIncomingValueForBlock(OriginalBB); 1246 PN.addIncoming(GetClonedValue(OldIncoming), ClonedBB); 1247 } 1248 } 1249 } 1250 } 1251 1252 LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd( 1253 const LoopStructure &LS, BasicBlock *Preheader, Value *ExitSubloopAt, 1254 BasicBlock *ContinuationBlock) const { 1255 // We start with a loop with a single latch: 1256 // 1257 // +--------------------+ 1258 // | | 1259 // | preheader | 1260 // | | 1261 // +--------+-----------+ 1262 // | ----------------\ 1263 // | / | 1264 // +--------v----v------+ | 1265 // | | | 1266 // | header | | 1267 // | | | 1268 // +--------------------+ | 1269 // | 1270 // ..... | 1271 // | 1272 // +--------------------+ | 1273 // | | | 1274 // | latch >----------/ 1275 // | | 1276 // +-------v------------+ 1277 // | 1278 // | 1279 // | +--------------------+ 1280 // | | | 1281 // +---> original exit | 1282 // | | 1283 // +--------------------+ 1284 // 1285 // We change the control flow to look like 1286 // 1287 // 1288 // +--------------------+ 1289 // | | 1290 // | preheader >-------------------------+ 1291 // | | | 1292 // +--------v-----------+ | 1293 // | /-------------+ | 1294 // | / | | 1295 // +--------v--v--------+ | | 1296 // | | | | 1297 // | header | | +--------+ | 1298 // | | | | | | 1299 // +--------------------+ | | +-----v-----v-----------+ 1300 // | | | | 1301 // | | | .pseudo.exit | 1302 // | | | | 1303 // | | +-----------v-----------+ 1304 // | | | 1305 // ..... | | | 1306 // | | +--------v-------------+ 1307 // +--------------------+ | | | | 1308 // | | | | | ContinuationBlock | 1309 // | latch >------+ | | | 1310 // | | | +----------------------+ 1311 // +---------v----------+ | 1312 // | | 1313 // | | 1314 // | +---------------^-----+ 1315 // | | | 1316 // +-----> .exit.selector | 1317 // | | 1318 // +----------v----------+ 1319 // | 1320 // +--------------------+ | 1321 // | | | 1322 // | original exit <----+ 1323 // | | 1324 // +--------------------+ 1325 1326 RewrittenRangeInfo RRI; 1327 1328 BasicBlock *BBInsertLocation = LS.Latch->getNextNode(); 1329 RRI.ExitSelector = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".exit.selector", 1330 &F, BBInsertLocation); 1331 RRI.PseudoExit = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".pseudo.exit", &F, 1332 BBInsertLocation); 1333 1334 BranchInst *PreheaderJump = cast<BranchInst>(Preheader->getTerminator()); 1335 bool Increasing = LS.IndVarIncreasing; 1336 bool IsSignedPredicate = LS.IsSignedPredicate; 1337 1338 IRBuilder<> B(PreheaderJump); 1339 1340 // EnterLoopCond - is it okay to start executing this `LS'? 1341 Value *EnterLoopCond = nullptr; 1342 if (Increasing) 1343 EnterLoopCond = IsSignedPredicate 1344 ? B.CreateICmpSLT(LS.IndVarStart, ExitSubloopAt) 1345 : B.CreateICmpULT(LS.IndVarStart, ExitSubloopAt); 1346 else 1347 EnterLoopCond = IsSignedPredicate 1348 ? B.CreateICmpSGT(LS.IndVarStart, ExitSubloopAt) 1349 : B.CreateICmpUGT(LS.IndVarStart, ExitSubloopAt); 1350 1351 B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit); 1352 PreheaderJump->eraseFromParent(); 1353 1354 LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector); 1355 B.SetInsertPoint(LS.LatchBr); 1356 Value *TakeBackedgeLoopCond = nullptr; 1357 if (Increasing) 1358 TakeBackedgeLoopCond = IsSignedPredicate 1359 ? B.CreateICmpSLT(LS.IndVarBase, ExitSubloopAt) 1360 : B.CreateICmpULT(LS.IndVarBase, ExitSubloopAt); 1361 else 1362 TakeBackedgeLoopCond = IsSignedPredicate 1363 ? B.CreateICmpSGT(LS.IndVarBase, ExitSubloopAt) 1364 : B.CreateICmpUGT(LS.IndVarBase, ExitSubloopAt); 1365 Value *CondForBranch = LS.LatchBrExitIdx == 1 1366 ? TakeBackedgeLoopCond 1367 : B.CreateNot(TakeBackedgeLoopCond); 1368 1369 LS.LatchBr->setCondition(CondForBranch); 1370 1371 B.SetInsertPoint(RRI.ExitSelector); 1372 1373 // IterationsLeft - are there any more iterations left, given the original 1374 // upper bound on the induction variable? If not, we branch to the "real" 1375 // exit. 1376 Value *IterationsLeft = nullptr; 1377 if (Increasing) 1378 IterationsLeft = IsSignedPredicate 1379 ? B.CreateICmpSLT(LS.IndVarBase, LS.LoopExitAt) 1380 : B.CreateICmpULT(LS.IndVarBase, LS.LoopExitAt); 1381 else 1382 IterationsLeft = IsSignedPredicate 1383 ? B.CreateICmpSGT(LS.IndVarBase, LS.LoopExitAt) 1384 : B.CreateICmpUGT(LS.IndVarBase, LS.LoopExitAt); 1385 B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit); 1386 1387 BranchInst *BranchToContinuation = 1388 BranchInst::Create(ContinuationBlock, RRI.PseudoExit); 1389 1390 // We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of 1391 // each of the PHI nodes in the loop header. This feeds into the initial 1392 // value of the same PHI nodes if/when we continue execution. 1393 for (PHINode &PN : LS.Header->phis()) { 1394 PHINode *NewPHI = PHINode::Create(PN.getType(), 2, PN.getName() + ".copy", 1395 BranchToContinuation); 1396 1397 NewPHI->addIncoming(PN.getIncomingValueForBlock(Preheader), Preheader); 1398 NewPHI->addIncoming(PN.getIncomingValueForBlock(LS.Latch), 1399 RRI.ExitSelector); 1400 RRI.PHIValuesAtPseudoExit.push_back(NewPHI); 1401 } 1402 1403 RRI.IndVarEnd = PHINode::Create(LS.IndVarBase->getType(), 2, "indvar.end", 1404 BranchToContinuation); 1405 RRI.IndVarEnd->addIncoming(LS.IndVarStart, Preheader); 1406 RRI.IndVarEnd->addIncoming(LS.IndVarBase, RRI.ExitSelector); 1407 1408 // The latch exit now has a branch from `RRI.ExitSelector' instead of 1409 // `LS.Latch'. The PHI nodes need to be updated to reflect that. 1410 for (PHINode &PN : LS.LatchExit->phis()) 1411 replacePHIBlock(&PN, LS.Latch, RRI.ExitSelector); 1412 1413 return RRI; 1414 } 1415 1416 void LoopConstrainer::rewriteIncomingValuesForPHIs( 1417 LoopStructure &LS, BasicBlock *ContinuationBlock, 1418 const LoopConstrainer::RewrittenRangeInfo &RRI) const { 1419 unsigned PHIIndex = 0; 1420 for (PHINode &PN : LS.Header->phis()) 1421 for (unsigned i = 0, e = PN.getNumIncomingValues(); i < e; ++i) 1422 if (PN.getIncomingBlock(i) == ContinuationBlock) 1423 PN.setIncomingValue(i, RRI.PHIValuesAtPseudoExit[PHIIndex++]); 1424 1425 LS.IndVarStart = RRI.IndVarEnd; 1426 } 1427 1428 BasicBlock *LoopConstrainer::createPreheader(const LoopStructure &LS, 1429 BasicBlock *OldPreheader, 1430 const char *Tag) const { 1431 BasicBlock *Preheader = BasicBlock::Create(Ctx, Tag, &F, LS.Header); 1432 BranchInst::Create(LS.Header, Preheader); 1433 1434 for (PHINode &PN : LS.Header->phis()) 1435 for (unsigned i = 0, e = PN.getNumIncomingValues(); i < e; ++i) 1436 replacePHIBlock(&PN, OldPreheader, Preheader); 1437 1438 return Preheader; 1439 } 1440 1441 void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) { 1442 Loop *ParentLoop = OriginalLoop.getParentLoop(); 1443 if (!ParentLoop) 1444 return; 1445 1446 for (BasicBlock *BB : BBs) 1447 ParentLoop->addBasicBlockToLoop(BB, LI); 1448 } 1449 1450 Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent, 1451 ValueToValueMapTy &VM, 1452 bool IsSubloop) { 1453 Loop &New = *LI.AllocateLoop(); 1454 if (Parent) 1455 Parent->addChildLoop(&New); 1456 else 1457 LI.addTopLevelLoop(&New); 1458 LPMAddNewLoop(&New, IsSubloop); 1459 1460 // Add all of the blocks in Original to the new loop. 1461 for (auto *BB : Original->blocks()) 1462 if (LI.getLoopFor(BB) == Original) 1463 New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), LI); 1464 1465 // Add all of the subloops to the new loop. 1466 for (Loop *SubLoop : *Original) 1467 createClonedLoopStructure(SubLoop, &New, VM, /* IsSubloop */ true); 1468 1469 return &New; 1470 } 1471 1472 bool LoopConstrainer::run() { 1473 BasicBlock *Preheader = nullptr; 1474 LatchTakenCount = SE.getExitCount(&OriginalLoop, MainLoopStructure.Latch); 1475 Preheader = OriginalLoop.getLoopPreheader(); 1476 assert(!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader != nullptr && 1477 "preconditions!"); 1478 1479 OriginalPreheader = Preheader; 1480 MainLoopPreheader = Preheader; 1481 1482 bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate; 1483 Optional<SubRanges> MaybeSR = calculateSubRanges(IsSignedPredicate); 1484 if (!MaybeSR.hasValue()) { 1485 LLVM_DEBUG(dbgs() << "irce: could not compute subranges\n"); 1486 return false; 1487 } 1488 1489 SubRanges SR = MaybeSR.getValue(); 1490 bool Increasing = MainLoopStructure.IndVarIncreasing; 1491 IntegerType *IVTy = 1492 cast<IntegerType>(MainLoopStructure.IndVarBase->getType()); 1493 1494 SCEVExpander Expander(SE, F.getParent()->getDataLayout(), "irce"); 1495 Instruction *InsertPt = OriginalPreheader->getTerminator(); 1496 1497 // It would have been better to make `PreLoop' and `PostLoop' 1498 // `Optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy 1499 // constructor. 1500 ClonedLoop PreLoop, PostLoop; 1501 bool NeedsPreLoop = 1502 Increasing ? SR.LowLimit.hasValue() : SR.HighLimit.hasValue(); 1503 bool NeedsPostLoop = 1504 Increasing ? SR.HighLimit.hasValue() : SR.LowLimit.hasValue(); 1505 1506 Value *ExitPreLoopAt = nullptr; 1507 Value *ExitMainLoopAt = nullptr; 1508 const SCEVConstant *MinusOneS = 1509 cast<SCEVConstant>(SE.getConstant(IVTy, -1, true /* isSigned */)); 1510 1511 if (NeedsPreLoop) { 1512 const SCEV *ExitPreLoopAtSCEV = nullptr; 1513 1514 if (Increasing) 1515 ExitPreLoopAtSCEV = *SR.LowLimit; 1516 else { 1517 if (CannotBeMinInLoop(*SR.HighLimit, &OriginalLoop, SE, 1518 IsSignedPredicate)) 1519 ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS); 1520 else { 1521 LLVM_DEBUG(dbgs() << "irce: could not prove no-overflow when computing " 1522 << "preloop exit limit. HighLimit = " 1523 << *(*SR.HighLimit) << "\n"); 1524 return false; 1525 } 1526 } 1527 1528 if (!isSafeToExpandAt(ExitPreLoopAtSCEV, InsertPt, SE)) { 1529 LLVM_DEBUG(dbgs() << "irce: could not prove that it is safe to expand the" 1530 << " preloop exit limit " << *ExitPreLoopAtSCEV 1531 << " at block " << InsertPt->getParent()->getName() 1532 << "\n"); 1533 return false; 1534 } 1535 1536 ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt); 1537 ExitPreLoopAt->setName("exit.preloop.at"); 1538 } 1539 1540 if (NeedsPostLoop) { 1541 const SCEV *ExitMainLoopAtSCEV = nullptr; 1542 1543 if (Increasing) 1544 ExitMainLoopAtSCEV = *SR.HighLimit; 1545 else { 1546 if (CannotBeMinInLoop(*SR.LowLimit, &OriginalLoop, SE, 1547 IsSignedPredicate)) 1548 ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS); 1549 else { 1550 LLVM_DEBUG(dbgs() << "irce: could not prove no-overflow when computing " 1551 << "mainloop exit limit. LowLimit = " 1552 << *(*SR.LowLimit) << "\n"); 1553 return false; 1554 } 1555 } 1556 1557 if (!isSafeToExpandAt(ExitMainLoopAtSCEV, InsertPt, SE)) { 1558 LLVM_DEBUG(dbgs() << "irce: could not prove that it is safe to expand the" 1559 << " main loop exit limit " << *ExitMainLoopAtSCEV 1560 << " at block " << InsertPt->getParent()->getName() 1561 << "\n"); 1562 return false; 1563 } 1564 1565 ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt); 1566 ExitMainLoopAt->setName("exit.mainloop.at"); 1567 } 1568 1569 // We clone these ahead of time so that we don't have to deal with changing 1570 // and temporarily invalid IR as we transform the loops. 1571 if (NeedsPreLoop) 1572 cloneLoop(PreLoop, "preloop"); 1573 if (NeedsPostLoop) 1574 cloneLoop(PostLoop, "postloop"); 1575 1576 RewrittenRangeInfo PreLoopRRI; 1577 1578 if (NeedsPreLoop) { 1579 Preheader->getTerminator()->replaceUsesOfWith(MainLoopStructure.Header, 1580 PreLoop.Structure.Header); 1581 1582 MainLoopPreheader = 1583 createPreheader(MainLoopStructure, Preheader, "mainloop"); 1584 PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader, 1585 ExitPreLoopAt, MainLoopPreheader); 1586 rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader, 1587 PreLoopRRI); 1588 } 1589 1590 BasicBlock *PostLoopPreheader = nullptr; 1591 RewrittenRangeInfo PostLoopRRI; 1592 1593 if (NeedsPostLoop) { 1594 PostLoopPreheader = 1595 createPreheader(PostLoop.Structure, Preheader, "postloop"); 1596 PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader, 1597 ExitMainLoopAt, PostLoopPreheader); 1598 rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader, 1599 PostLoopRRI); 1600 } 1601 1602 BasicBlock *NewMainLoopPreheader = 1603 MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr; 1604 BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit, 1605 PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit, 1606 PostLoopRRI.ExitSelector, NewMainLoopPreheader}; 1607 1608 // Some of the above may be nullptr, filter them out before passing to 1609 // addToParentLoopIfNeeded. 1610 auto NewBlocksEnd = 1611 std::remove(std::begin(NewBlocks), std::end(NewBlocks), nullptr); 1612 1613 addToParentLoopIfNeeded(makeArrayRef(std::begin(NewBlocks), NewBlocksEnd)); 1614 1615 DT.recalculate(F); 1616 1617 // We need to first add all the pre and post loop blocks into the loop 1618 // structures (as part of createClonedLoopStructure), and then update the 1619 // LCSSA form and LoopSimplifyForm. This is necessary for correctly updating 1620 // LI when LoopSimplifyForm is generated. 1621 Loop *PreL = nullptr, *PostL = nullptr; 1622 if (!PreLoop.Blocks.empty()) { 1623 PreL = createClonedLoopStructure(&OriginalLoop, 1624 OriginalLoop.getParentLoop(), PreLoop.Map, 1625 /* IsSubLoop */ false); 1626 } 1627 1628 if (!PostLoop.Blocks.empty()) { 1629 PostL = 1630 createClonedLoopStructure(&OriginalLoop, OriginalLoop.getParentLoop(), 1631 PostLoop.Map, /* IsSubLoop */ false); 1632 } 1633 1634 // This function canonicalizes the loop into Loop-Simplify and LCSSA forms. 1635 auto CanonicalizeLoop = [&] (Loop *L, bool IsOriginalLoop) { 1636 formLCSSARecursively(*L, DT, &LI, &SE); 1637 simplifyLoop(L, &DT, &LI, &SE, nullptr, true); 1638 // Pre/post loops are slow paths, we do not need to perform any loop 1639 // optimizations on them. 1640 if (!IsOriginalLoop) 1641 DisableAllLoopOptsOnLoop(*L); 1642 }; 1643 if (PreL) 1644 CanonicalizeLoop(PreL, false); 1645 if (PostL) 1646 CanonicalizeLoop(PostL, false); 1647 CanonicalizeLoop(&OriginalLoop, true); 1648 1649 return true; 1650 } 1651 1652 /// Computes and returns a range of values for the induction variable (IndVar) 1653 /// in which the range check can be safely elided. If it cannot compute such a 1654 /// range, returns None. 1655 Optional<InductiveRangeCheck::Range> 1656 InductiveRangeCheck::computeSafeIterationSpace( 1657 ScalarEvolution &SE, const SCEVAddRecExpr *IndVar, 1658 bool IsLatchSigned) const { 1659 // IndVar is of the form "A + B * I" (where "I" is the canonical induction 1660 // variable, that may or may not exist as a real llvm::Value in the loop) and 1661 // this inductive range check is a range check on the "C + D * I" ("C" is 1662 // getBegin() and "D" is getStep()). We rewrite the value being range 1663 // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA". 1664 // 1665 // The actual inequalities we solve are of the form 1666 // 1667 // 0 <= M + 1 * IndVar < L given L >= 0 (i.e. N == 1) 1668 // 1669 // Here L stands for upper limit of the safe iteration space. 1670 // The inequality is satisfied by (0 - M) <= IndVar < (L - M). To avoid 1671 // overflows when calculating (0 - M) and (L - M) we, depending on type of 1672 // IV's iteration space, limit the calculations by borders of the iteration 1673 // space. For example, if IndVar is unsigned, (0 - M) overflows for any M > 0. 1674 // If we figured out that "anything greater than (-M) is safe", we strengthen 1675 // this to "everything greater than 0 is safe", assuming that values between 1676 // -M and 0 just do not exist in unsigned iteration space, and we don't want 1677 // to deal with overflown values. 1678 1679 if (!IndVar->isAffine()) 1680 return None; 1681 1682 const SCEV *A = IndVar->getStart(); 1683 const SCEVConstant *B = dyn_cast<SCEVConstant>(IndVar->getStepRecurrence(SE)); 1684 if (!B) 1685 return None; 1686 assert(!B->isZero() && "Recurrence with zero step?"); 1687 1688 const SCEV *C = getBegin(); 1689 const SCEVConstant *D = dyn_cast<SCEVConstant>(getStep()); 1690 if (D != B) 1691 return None; 1692 1693 assert(!D->getValue()->isZero() && "Recurrence with zero step?"); 1694 unsigned BitWidth = cast<IntegerType>(IndVar->getType())->getBitWidth(); 1695 const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth)); 1696 1697 // Subtract Y from X so that it does not go through border of the IV 1698 // iteration space. Mathematically, it is equivalent to: 1699 // 1700 // ClampedSubtract(X, Y) = min(max(X - Y, INT_MIN), INT_MAX). [1] 1701 // 1702 // In [1], 'X - Y' is a mathematical subtraction (result is not bounded to 1703 // any width of bit grid). But after we take min/max, the result is 1704 // guaranteed to be within [INT_MIN, INT_MAX]. 1705 // 1706 // In [1], INT_MAX and INT_MIN are respectively signed and unsigned max/min 1707 // values, depending on type of latch condition that defines IV iteration 1708 // space. 1709 auto ClampedSubtract = [&](const SCEV *X, const SCEV *Y) { 1710 // FIXME: The current implementation assumes that X is in [0, SINT_MAX]. 1711 // This is required to ensure that SINT_MAX - X does not overflow signed and 1712 // that X - Y does not overflow unsigned if Y is negative. Can we lift this 1713 // restriction and make it work for negative X either? 1714 if (IsLatchSigned) { 1715 // X is a number from signed range, Y is interpreted as signed. 1716 // Even if Y is SINT_MAX, (X - Y) does not reach SINT_MIN. So the only 1717 // thing we should care about is that we didn't cross SINT_MAX. 1718 // So, if Y is positive, we subtract Y safely. 1719 // Rule 1: Y > 0 ---> Y. 1720 // If 0 <= -Y <= (SINT_MAX - X), we subtract Y safely. 1721 // Rule 2: Y >=s (X - SINT_MAX) ---> Y. 1722 // If 0 <= (SINT_MAX - X) < -Y, we can only subtract (X - SINT_MAX). 1723 // Rule 3: Y <s (X - SINT_MAX) ---> (X - SINT_MAX). 1724 // It gives us smax(Y, X - SINT_MAX) to subtract in all cases. 1725 const SCEV *XMinusSIntMax = SE.getMinusSCEV(X, SIntMax); 1726 return SE.getMinusSCEV(X, SE.getSMaxExpr(Y, XMinusSIntMax), 1727 SCEV::FlagNSW); 1728 } else 1729 // X is a number from unsigned range, Y is interpreted as signed. 1730 // Even if Y is SINT_MIN, (X - Y) does not reach UINT_MAX. So the only 1731 // thing we should care about is that we didn't cross zero. 1732 // So, if Y is negative, we subtract Y safely. 1733 // Rule 1: Y <s 0 ---> Y. 1734 // If 0 <= Y <= X, we subtract Y safely. 1735 // Rule 2: Y <=s X ---> Y. 1736 // If 0 <= X < Y, we should stop at 0 and can only subtract X. 1737 // Rule 3: Y >s X ---> X. 1738 // It gives us smin(X, Y) to subtract in all cases. 1739 return SE.getMinusSCEV(X, SE.getSMinExpr(X, Y), SCEV::FlagNUW); 1740 }; 1741 const SCEV *M = SE.getMinusSCEV(C, A); 1742 const SCEV *Zero = SE.getZero(M->getType()); 1743 1744 // This function returns SCEV equal to 1 if X is non-negative 0 otherwise. 1745 auto SCEVCheckNonNegative = [&](const SCEV *X) { 1746 const Loop *L = IndVar->getLoop(); 1747 const SCEV *One = SE.getOne(X->getType()); 1748 // Can we trivially prove that X is a non-negative or negative value? 1749 if (isKnownNonNegativeInLoop(X, L, SE)) 1750 return One; 1751 else if (isKnownNegativeInLoop(X, L, SE)) 1752 return Zero; 1753 // If not, we will have to figure it out during the execution. 1754 // Function smax(smin(X, 0), -1) + 1 equals to 1 if X >= 0 and 0 if X < 0. 1755 const SCEV *NegOne = SE.getNegativeSCEV(One); 1756 return SE.getAddExpr(SE.getSMaxExpr(SE.getSMinExpr(X, Zero), NegOne), One); 1757 }; 1758 // FIXME: Current implementation of ClampedSubtract implicitly assumes that 1759 // X is non-negative (in sense of a signed value). We need to re-implement 1760 // this function in a way that it will correctly handle negative X as well. 1761 // We use it twice: for X = 0 everything is fine, but for X = getEnd() we can 1762 // end up with a negative X and produce wrong results. So currently we ensure 1763 // that if getEnd() is negative then both ends of the safe range are zero. 1764 // Note that this may pessimize elimination of unsigned range checks against 1765 // negative values. 1766 const SCEV *REnd = getEnd(); 1767 const SCEV *EndIsNonNegative = SCEVCheckNonNegative(REnd); 1768 1769 const SCEV *Begin = SE.getMulExpr(ClampedSubtract(Zero, M), EndIsNonNegative); 1770 const SCEV *End = SE.getMulExpr(ClampedSubtract(REnd, M), EndIsNonNegative); 1771 return InductiveRangeCheck::Range(Begin, End); 1772 } 1773 1774 static Optional<InductiveRangeCheck::Range> 1775 IntersectSignedRange(ScalarEvolution &SE, 1776 const Optional<InductiveRangeCheck::Range> &R1, 1777 const InductiveRangeCheck::Range &R2) { 1778 if (R2.isEmpty(SE, /* IsSigned */ true)) 1779 return None; 1780 if (!R1.hasValue()) 1781 return R2; 1782 auto &R1Value = R1.getValue(); 1783 // We never return empty ranges from this function, and R1 is supposed to be 1784 // a result of intersection. Thus, R1 is never empty. 1785 assert(!R1Value.isEmpty(SE, /* IsSigned */ true) && 1786 "We should never have empty R1!"); 1787 1788 // TODO: we could widen the smaller range and have this work; but for now we 1789 // bail out to keep things simple. 1790 if (R1Value.getType() != R2.getType()) 1791 return None; 1792 1793 const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin()); 1794 const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd()); 1795 1796 // If the resulting range is empty, just return None. 1797 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd); 1798 if (Ret.isEmpty(SE, /* IsSigned */ true)) 1799 return None; 1800 return Ret; 1801 } 1802 1803 static Optional<InductiveRangeCheck::Range> 1804 IntersectUnsignedRange(ScalarEvolution &SE, 1805 const Optional<InductiveRangeCheck::Range> &R1, 1806 const InductiveRangeCheck::Range &R2) { 1807 if (R2.isEmpty(SE, /* IsSigned */ false)) 1808 return None; 1809 if (!R1.hasValue()) 1810 return R2; 1811 auto &R1Value = R1.getValue(); 1812 // We never return empty ranges from this function, and R1 is supposed to be 1813 // a result of intersection. Thus, R1 is never empty. 1814 assert(!R1Value.isEmpty(SE, /* IsSigned */ false) && 1815 "We should never have empty R1!"); 1816 1817 // TODO: we could widen the smaller range and have this work; but for now we 1818 // bail out to keep things simple. 1819 if (R1Value.getType() != R2.getType()) 1820 return None; 1821 1822 const SCEV *NewBegin = SE.getUMaxExpr(R1Value.getBegin(), R2.getBegin()); 1823 const SCEV *NewEnd = SE.getUMinExpr(R1Value.getEnd(), R2.getEnd()); 1824 1825 // If the resulting range is empty, just return None. 1826 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd); 1827 if (Ret.isEmpty(SE, /* IsSigned */ false)) 1828 return None; 1829 return Ret; 1830 } 1831 1832 PreservedAnalyses IRCEPass::run(Loop &L, LoopAnalysisManager &AM, 1833 LoopStandardAnalysisResults &AR, 1834 LPMUpdater &U) { 1835 Function *F = L.getHeader()->getParent(); 1836 const auto &FAM = 1837 AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager(); 1838 auto *BPI = FAM.getCachedResult<BranchProbabilityAnalysis>(*F); 1839 InductiveRangeCheckElimination IRCE(AR.SE, BPI, AR.DT, AR.LI); 1840 auto LPMAddNewLoop = [&U](Loop *NL, bool IsSubloop) { 1841 if (!IsSubloop) 1842 U.addSiblingLoops(NL); 1843 }; 1844 bool Changed = IRCE.run(&L, LPMAddNewLoop); 1845 if (!Changed) 1846 return PreservedAnalyses::all(); 1847 1848 return getLoopPassPreservedAnalyses(); 1849 } 1850 1851 bool IRCELegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) { 1852 if (skipLoop(L)) 1853 return false; 1854 1855 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 1856 BranchProbabilityInfo &BPI = 1857 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI(); 1858 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1859 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 1860 InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI); 1861 auto LPMAddNewLoop = [&LPM](Loop *NL, bool /* IsSubLoop */) { 1862 LPM.addLoop(*NL); 1863 }; 1864 return IRCE.run(L, LPMAddNewLoop); 1865 } 1866 1867 bool InductiveRangeCheckElimination::run( 1868 Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop) { 1869 if (L->getBlocks().size() >= LoopSizeCutoff) { 1870 LLVM_DEBUG(dbgs() << "irce: giving up constraining loop, too large\n"); 1871 return false; 1872 } 1873 1874 BasicBlock *Preheader = L->getLoopPreheader(); 1875 if (!Preheader) { 1876 LLVM_DEBUG(dbgs() << "irce: loop has no preheader, leaving\n"); 1877 return false; 1878 } 1879 1880 LLVMContext &Context = Preheader->getContext(); 1881 SmallVector<InductiveRangeCheck, 16> RangeChecks; 1882 1883 for (auto BBI : L->getBlocks()) 1884 if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator())) 1885 InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI, 1886 RangeChecks); 1887 1888 if (RangeChecks.empty()) 1889 return false; 1890 1891 auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) { 1892 OS << "irce: looking at loop "; L->print(OS); 1893 OS << "irce: loop has " << RangeChecks.size() 1894 << " inductive range checks: \n"; 1895 for (InductiveRangeCheck &IRC : RangeChecks) 1896 IRC.print(OS); 1897 }; 1898 1899 LLVM_DEBUG(PrintRecognizedRangeChecks(dbgs())); 1900 1901 if (PrintRangeChecks) 1902 PrintRecognizedRangeChecks(errs()); 1903 1904 const char *FailureReason = nullptr; 1905 Optional<LoopStructure> MaybeLoopStructure = 1906 LoopStructure::parseLoopStructure(SE, BPI, *L, FailureReason); 1907 if (!MaybeLoopStructure.hasValue()) { 1908 LLVM_DEBUG(dbgs() << "irce: could not parse loop structure: " 1909 << FailureReason << "\n";); 1910 return false; 1911 } 1912 LoopStructure LS = MaybeLoopStructure.getValue(); 1913 const SCEVAddRecExpr *IndVar = 1914 cast<SCEVAddRecExpr>(SE.getMinusSCEV(SE.getSCEV(LS.IndVarBase), SE.getSCEV(LS.IndVarStep))); 1915 1916 Optional<InductiveRangeCheck::Range> SafeIterRange; 1917 Instruction *ExprInsertPt = Preheader->getTerminator(); 1918 1919 SmallVector<InductiveRangeCheck, 4> RangeChecksToEliminate; 1920 // Basing on the type of latch predicate, we interpret the IV iteration range 1921 // as signed or unsigned range. We use different min/max functions (signed or 1922 // unsigned) when intersecting this range with safe iteration ranges implied 1923 // by range checks. 1924 auto IntersectRange = 1925 LS.IsSignedPredicate ? IntersectSignedRange : IntersectUnsignedRange; 1926 1927 IRBuilder<> B(ExprInsertPt); 1928 for (InductiveRangeCheck &IRC : RangeChecks) { 1929 auto Result = IRC.computeSafeIterationSpace(SE, IndVar, 1930 LS.IsSignedPredicate); 1931 if (Result.hasValue()) { 1932 auto MaybeSafeIterRange = 1933 IntersectRange(SE, SafeIterRange, Result.getValue()); 1934 if (MaybeSafeIterRange.hasValue()) { 1935 assert( 1936 !MaybeSafeIterRange.getValue().isEmpty(SE, LS.IsSignedPredicate) && 1937 "We should never return empty ranges!"); 1938 RangeChecksToEliminate.push_back(IRC); 1939 SafeIterRange = MaybeSafeIterRange.getValue(); 1940 } 1941 } 1942 } 1943 1944 if (!SafeIterRange.hasValue()) 1945 return false; 1946 1947 LoopConstrainer LC(*L, LI, LPMAddNewLoop, LS, SE, DT, 1948 SafeIterRange.getValue()); 1949 bool Changed = LC.run(); 1950 1951 if (Changed) { 1952 auto PrintConstrainedLoopInfo = [L]() { 1953 dbgs() << "irce: in function "; 1954 dbgs() << L->getHeader()->getParent()->getName() << ": "; 1955 dbgs() << "constrained "; 1956 L->print(dbgs()); 1957 }; 1958 1959 LLVM_DEBUG(PrintConstrainedLoopInfo()); 1960 1961 if (PrintChangedLoops) 1962 PrintConstrainedLoopInfo(); 1963 1964 // Optimize away the now-redundant range checks. 1965 1966 for (InductiveRangeCheck &IRC : RangeChecksToEliminate) { 1967 ConstantInt *FoldedRangeCheck = IRC.getPassingDirection() 1968 ? ConstantInt::getTrue(Context) 1969 : ConstantInt::getFalse(Context); 1970 IRC.getCheckUse()->set(FoldedRangeCheck); 1971 } 1972 } 1973 1974 return Changed; 1975 } 1976 1977 Pass *llvm::createInductiveRangeCheckEliminationPass() { 1978 return new IRCELegacyPass(); 1979 } 1980