1*73471bf0Spatrick //===------- LoopBoundSplit.cpp - Split Loop Bound --------------*- C++ -*-===// 2*73471bf0Spatrick // 3*73471bf0Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*73471bf0Spatrick // See https://llvm.org/LICENSE.txt for license information. 5*73471bf0Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*73471bf0Spatrick // 7*73471bf0Spatrick //===----------------------------------------------------------------------===// 8*73471bf0Spatrick 9*73471bf0Spatrick #include "llvm/Transforms/Scalar/LoopBoundSplit.h" 10*73471bf0Spatrick #include "llvm/Analysis/LoopAccessAnalysis.h" 11*73471bf0Spatrick #include "llvm/Analysis/LoopAnalysisManager.h" 12*73471bf0Spatrick #include "llvm/Analysis/LoopInfo.h" 13*73471bf0Spatrick #include "llvm/Analysis/LoopIterator.h" 14*73471bf0Spatrick #include "llvm/Analysis/LoopPass.h" 15*73471bf0Spatrick #include "llvm/Analysis/MemorySSA.h" 16*73471bf0Spatrick #include "llvm/Analysis/MemorySSAUpdater.h" 17*73471bf0Spatrick #include "llvm/Analysis/ScalarEvolution.h" 18*73471bf0Spatrick #include "llvm/Analysis/ScalarEvolutionExpressions.h" 19*73471bf0Spatrick #include "llvm/IR/PatternMatch.h" 20*73471bf0Spatrick #include "llvm/Transforms/Utils/BasicBlockUtils.h" 21*73471bf0Spatrick #include "llvm/Transforms/Utils/Cloning.h" 22*73471bf0Spatrick #include "llvm/Transforms/Utils/LoopSimplify.h" 23*73471bf0Spatrick #include "llvm/Transforms/Utils/LoopUtils.h" 24*73471bf0Spatrick #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" 25*73471bf0Spatrick 26*73471bf0Spatrick #define DEBUG_TYPE "loop-bound-split" 27*73471bf0Spatrick 28*73471bf0Spatrick namespace llvm { 29*73471bf0Spatrick 30*73471bf0Spatrick using namespace PatternMatch; 31*73471bf0Spatrick 32*73471bf0Spatrick namespace { 33*73471bf0Spatrick struct ConditionInfo { 34*73471bf0Spatrick /// Branch instruction with this condition 35*73471bf0Spatrick BranchInst *BI; 36*73471bf0Spatrick /// ICmp instruction with this condition 37*73471bf0Spatrick ICmpInst *ICmp; 38*73471bf0Spatrick /// Preciate info 39*73471bf0Spatrick ICmpInst::Predicate Pred; 40*73471bf0Spatrick /// AddRec llvm value 41*73471bf0Spatrick Value *AddRecValue; 42*73471bf0Spatrick /// Bound llvm value 43*73471bf0Spatrick Value *BoundValue; 44*73471bf0Spatrick /// AddRec SCEV 45*73471bf0Spatrick const SCEV *AddRecSCEV; 46*73471bf0Spatrick /// Bound SCEV 47*73471bf0Spatrick const SCEV *BoundSCEV; 48*73471bf0Spatrick 49*73471bf0Spatrick ConditionInfo() 50*73471bf0Spatrick : BI(nullptr), ICmp(nullptr), Pred(ICmpInst::BAD_ICMP_PREDICATE), 51*73471bf0Spatrick AddRecValue(nullptr), BoundValue(nullptr), AddRecSCEV(nullptr), 52*73471bf0Spatrick BoundSCEV(nullptr) {} 53*73471bf0Spatrick }; 54*73471bf0Spatrick } // namespace 55*73471bf0Spatrick 56*73471bf0Spatrick static void analyzeICmp(ScalarEvolution &SE, ICmpInst *ICmp, 57*73471bf0Spatrick ConditionInfo &Cond) { 58*73471bf0Spatrick Cond.ICmp = ICmp; 59*73471bf0Spatrick if (match(ICmp, m_ICmp(Cond.Pred, m_Value(Cond.AddRecValue), 60*73471bf0Spatrick m_Value(Cond.BoundValue)))) { 61*73471bf0Spatrick Cond.AddRecSCEV = SE.getSCEV(Cond.AddRecValue); 62*73471bf0Spatrick Cond.BoundSCEV = SE.getSCEV(Cond.BoundValue); 63*73471bf0Spatrick // Locate AddRec in LHSSCEV and Bound in RHSSCEV. 64*73471bf0Spatrick if (isa<SCEVAddRecExpr>(Cond.BoundSCEV) && 65*73471bf0Spatrick !isa<SCEVAddRecExpr>(Cond.AddRecSCEV)) { 66*73471bf0Spatrick std::swap(Cond.AddRecValue, Cond.BoundValue); 67*73471bf0Spatrick std::swap(Cond.AddRecSCEV, Cond.BoundSCEV); 68*73471bf0Spatrick Cond.Pred = ICmpInst::getSwappedPredicate(Cond.Pred); 69*73471bf0Spatrick } 70*73471bf0Spatrick } 71*73471bf0Spatrick } 72*73471bf0Spatrick 73*73471bf0Spatrick static bool calculateUpperBound(const Loop &L, ScalarEvolution &SE, 74*73471bf0Spatrick ConditionInfo &Cond, bool IsExitCond) { 75*73471bf0Spatrick if (IsExitCond) { 76*73471bf0Spatrick const SCEV *ExitCount = SE.getExitCount(&L, Cond.ICmp->getParent()); 77*73471bf0Spatrick if (isa<SCEVCouldNotCompute>(ExitCount)) 78*73471bf0Spatrick return false; 79*73471bf0Spatrick 80*73471bf0Spatrick Cond.BoundSCEV = ExitCount; 81*73471bf0Spatrick return true; 82*73471bf0Spatrick } 83*73471bf0Spatrick 84*73471bf0Spatrick // For non-exit condtion, if pred is LT, keep existing bound. 85*73471bf0Spatrick if (Cond.Pred == ICmpInst::ICMP_SLT || Cond.Pred == ICmpInst::ICMP_ULT) 86*73471bf0Spatrick return true; 87*73471bf0Spatrick 88*73471bf0Spatrick // For non-exit condition, if pre is LE, try to convert it to LT. 89*73471bf0Spatrick // Range Range 90*73471bf0Spatrick // AddRec <= Bound --> AddRec < Bound + 1 91*73471bf0Spatrick if (Cond.Pred != ICmpInst::ICMP_ULE && Cond.Pred != ICmpInst::ICMP_SLE) 92*73471bf0Spatrick return false; 93*73471bf0Spatrick 94*73471bf0Spatrick if (IntegerType *BoundSCEVIntType = 95*73471bf0Spatrick dyn_cast<IntegerType>(Cond.BoundSCEV->getType())) { 96*73471bf0Spatrick unsigned BitWidth = BoundSCEVIntType->getBitWidth(); 97*73471bf0Spatrick APInt Max = ICmpInst::isSigned(Cond.Pred) 98*73471bf0Spatrick ? APInt::getSignedMaxValue(BitWidth) 99*73471bf0Spatrick : APInt::getMaxValue(BitWidth); 100*73471bf0Spatrick const SCEV *MaxSCEV = SE.getConstant(Max); 101*73471bf0Spatrick // Check Bound < INT_MAX 102*73471bf0Spatrick ICmpInst::Predicate Pred = 103*73471bf0Spatrick ICmpInst::isSigned(Cond.Pred) ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; 104*73471bf0Spatrick if (SE.isKnownPredicate(Pred, Cond.BoundSCEV, MaxSCEV)) { 105*73471bf0Spatrick const SCEV *BoundPlusOneSCEV = 106*73471bf0Spatrick SE.getAddExpr(Cond.BoundSCEV, SE.getOne(BoundSCEVIntType)); 107*73471bf0Spatrick Cond.BoundSCEV = BoundPlusOneSCEV; 108*73471bf0Spatrick Cond.Pred = Pred; 109*73471bf0Spatrick return true; 110*73471bf0Spatrick } 111*73471bf0Spatrick } 112*73471bf0Spatrick 113*73471bf0Spatrick // ToDo: Support ICMP_NE/EQ. 114*73471bf0Spatrick 115*73471bf0Spatrick return false; 116*73471bf0Spatrick } 117*73471bf0Spatrick 118*73471bf0Spatrick static bool hasProcessableCondition(const Loop &L, ScalarEvolution &SE, 119*73471bf0Spatrick ICmpInst *ICmp, ConditionInfo &Cond, 120*73471bf0Spatrick bool IsExitCond) { 121*73471bf0Spatrick analyzeICmp(SE, ICmp, Cond); 122*73471bf0Spatrick 123*73471bf0Spatrick // The BoundSCEV should be evaluated at loop entry. 124*73471bf0Spatrick if (!SE.isAvailableAtLoopEntry(Cond.BoundSCEV, &L)) 125*73471bf0Spatrick return false; 126*73471bf0Spatrick 127*73471bf0Spatrick const SCEVAddRecExpr *AddRecSCEV = dyn_cast<SCEVAddRecExpr>(Cond.AddRecSCEV); 128*73471bf0Spatrick // Allowed AddRec as induction variable. 129*73471bf0Spatrick if (!AddRecSCEV) 130*73471bf0Spatrick return false; 131*73471bf0Spatrick 132*73471bf0Spatrick if (!AddRecSCEV->isAffine()) 133*73471bf0Spatrick return false; 134*73471bf0Spatrick 135*73471bf0Spatrick const SCEV *StepRecSCEV = AddRecSCEV->getStepRecurrence(SE); 136*73471bf0Spatrick // Allowed constant step. 137*73471bf0Spatrick if (!isa<SCEVConstant>(StepRecSCEV)) 138*73471bf0Spatrick return false; 139*73471bf0Spatrick 140*73471bf0Spatrick ConstantInt *StepCI = cast<SCEVConstant>(StepRecSCEV)->getValue(); 141*73471bf0Spatrick // Allowed positive step for now. 142*73471bf0Spatrick // TODO: Support negative step. 143*73471bf0Spatrick if (StepCI->isNegative() || StepCI->isZero()) 144*73471bf0Spatrick return false; 145*73471bf0Spatrick 146*73471bf0Spatrick // Calculate upper bound. 147*73471bf0Spatrick if (!calculateUpperBound(L, SE, Cond, IsExitCond)) 148*73471bf0Spatrick return false; 149*73471bf0Spatrick 150*73471bf0Spatrick return true; 151*73471bf0Spatrick } 152*73471bf0Spatrick 153*73471bf0Spatrick static bool isProcessableCondBI(const ScalarEvolution &SE, 154*73471bf0Spatrick const BranchInst *BI) { 155*73471bf0Spatrick BasicBlock *TrueSucc = nullptr; 156*73471bf0Spatrick BasicBlock *FalseSucc = nullptr; 157*73471bf0Spatrick ICmpInst::Predicate Pred; 158*73471bf0Spatrick Value *LHS, *RHS; 159*73471bf0Spatrick if (!match(BI, m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)), 160*73471bf0Spatrick m_BasicBlock(TrueSucc), m_BasicBlock(FalseSucc)))) 161*73471bf0Spatrick return false; 162*73471bf0Spatrick 163*73471bf0Spatrick if (!SE.isSCEVable(LHS->getType())) 164*73471bf0Spatrick return false; 165*73471bf0Spatrick assert(SE.isSCEVable(RHS->getType()) && "Expected RHS's type is SCEVable"); 166*73471bf0Spatrick 167*73471bf0Spatrick if (TrueSucc == FalseSucc) 168*73471bf0Spatrick return false; 169*73471bf0Spatrick 170*73471bf0Spatrick return true; 171*73471bf0Spatrick } 172*73471bf0Spatrick 173*73471bf0Spatrick static bool canSplitLoopBound(const Loop &L, const DominatorTree &DT, 174*73471bf0Spatrick ScalarEvolution &SE, ConditionInfo &Cond) { 175*73471bf0Spatrick // Skip function with optsize. 176*73471bf0Spatrick if (L.getHeader()->getParent()->hasOptSize()) 177*73471bf0Spatrick return false; 178*73471bf0Spatrick 179*73471bf0Spatrick // Split only innermost loop. 180*73471bf0Spatrick if (!L.isInnermost()) 181*73471bf0Spatrick return false; 182*73471bf0Spatrick 183*73471bf0Spatrick // Check loop is in simplified form. 184*73471bf0Spatrick if (!L.isLoopSimplifyForm()) 185*73471bf0Spatrick return false; 186*73471bf0Spatrick 187*73471bf0Spatrick // Check loop is in LCSSA form. 188*73471bf0Spatrick if (!L.isLCSSAForm(DT)) 189*73471bf0Spatrick return false; 190*73471bf0Spatrick 191*73471bf0Spatrick // Skip loop that cannot be cloned. 192*73471bf0Spatrick if (!L.isSafeToClone()) 193*73471bf0Spatrick return false; 194*73471bf0Spatrick 195*73471bf0Spatrick BasicBlock *ExitingBB = L.getExitingBlock(); 196*73471bf0Spatrick // Assumed only one exiting block. 197*73471bf0Spatrick if (!ExitingBB) 198*73471bf0Spatrick return false; 199*73471bf0Spatrick 200*73471bf0Spatrick BranchInst *ExitingBI = dyn_cast<BranchInst>(ExitingBB->getTerminator()); 201*73471bf0Spatrick if (!ExitingBI) 202*73471bf0Spatrick return false; 203*73471bf0Spatrick 204*73471bf0Spatrick // Allowed only conditional branch with ICmp. 205*73471bf0Spatrick if (!isProcessableCondBI(SE, ExitingBI)) 206*73471bf0Spatrick return false; 207*73471bf0Spatrick 208*73471bf0Spatrick // Check the condition is processable. 209*73471bf0Spatrick ICmpInst *ICmp = cast<ICmpInst>(ExitingBI->getCondition()); 210*73471bf0Spatrick if (!hasProcessableCondition(L, SE, ICmp, Cond, /*IsExitCond*/ true)) 211*73471bf0Spatrick return false; 212*73471bf0Spatrick 213*73471bf0Spatrick Cond.BI = ExitingBI; 214*73471bf0Spatrick return true; 215*73471bf0Spatrick } 216*73471bf0Spatrick 217*73471bf0Spatrick static bool isProfitableToTransform(const Loop &L, const BranchInst *BI) { 218*73471bf0Spatrick // If the conditional branch splits a loop into two halves, we could 219*73471bf0Spatrick // generally say it is profitable. 220*73471bf0Spatrick // 221*73471bf0Spatrick // ToDo: Add more profitable cases here. 222*73471bf0Spatrick 223*73471bf0Spatrick // Check this branch causes diamond CFG. 224*73471bf0Spatrick BasicBlock *Succ0 = BI->getSuccessor(0); 225*73471bf0Spatrick BasicBlock *Succ1 = BI->getSuccessor(1); 226*73471bf0Spatrick 227*73471bf0Spatrick BasicBlock *Succ0Succ = Succ0->getSingleSuccessor(); 228*73471bf0Spatrick BasicBlock *Succ1Succ = Succ1->getSingleSuccessor(); 229*73471bf0Spatrick if (!Succ0Succ || !Succ1Succ || Succ0Succ != Succ1Succ) 230*73471bf0Spatrick return false; 231*73471bf0Spatrick 232*73471bf0Spatrick // ToDo: Calculate each successor's instruction cost. 233*73471bf0Spatrick 234*73471bf0Spatrick return true; 235*73471bf0Spatrick } 236*73471bf0Spatrick 237*73471bf0Spatrick static BranchInst *findSplitCandidate(const Loop &L, ScalarEvolution &SE, 238*73471bf0Spatrick ConditionInfo &ExitingCond, 239*73471bf0Spatrick ConditionInfo &SplitCandidateCond) { 240*73471bf0Spatrick for (auto *BB : L.blocks()) { 241*73471bf0Spatrick // Skip condition of backedge. 242*73471bf0Spatrick if (L.getLoopLatch() == BB) 243*73471bf0Spatrick continue; 244*73471bf0Spatrick 245*73471bf0Spatrick auto *BI = dyn_cast<BranchInst>(BB->getTerminator()); 246*73471bf0Spatrick if (!BI) 247*73471bf0Spatrick continue; 248*73471bf0Spatrick 249*73471bf0Spatrick // Check conditional branch with ICmp. 250*73471bf0Spatrick if (!isProcessableCondBI(SE, BI)) 251*73471bf0Spatrick continue; 252*73471bf0Spatrick 253*73471bf0Spatrick // Skip loop invariant condition. 254*73471bf0Spatrick if (L.isLoopInvariant(BI->getCondition())) 255*73471bf0Spatrick continue; 256*73471bf0Spatrick 257*73471bf0Spatrick // Check the condition is processable. 258*73471bf0Spatrick ICmpInst *ICmp = cast<ICmpInst>(BI->getCondition()); 259*73471bf0Spatrick if (!hasProcessableCondition(L, SE, ICmp, SplitCandidateCond, 260*73471bf0Spatrick /*IsExitCond*/ false)) 261*73471bf0Spatrick continue; 262*73471bf0Spatrick 263*73471bf0Spatrick if (ExitingCond.BoundSCEV->getType() != 264*73471bf0Spatrick SplitCandidateCond.BoundSCEV->getType()) 265*73471bf0Spatrick continue; 266*73471bf0Spatrick 267*73471bf0Spatrick SplitCandidateCond.BI = BI; 268*73471bf0Spatrick return BI; 269*73471bf0Spatrick } 270*73471bf0Spatrick 271*73471bf0Spatrick return nullptr; 272*73471bf0Spatrick } 273*73471bf0Spatrick 274*73471bf0Spatrick static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI, 275*73471bf0Spatrick ScalarEvolution &SE, LPMUpdater &U) { 276*73471bf0Spatrick ConditionInfo SplitCandidateCond; 277*73471bf0Spatrick ConditionInfo ExitingCond; 278*73471bf0Spatrick 279*73471bf0Spatrick // Check we can split this loop's bound. 280*73471bf0Spatrick if (!canSplitLoopBound(L, DT, SE, ExitingCond)) 281*73471bf0Spatrick return false; 282*73471bf0Spatrick 283*73471bf0Spatrick if (!findSplitCandidate(L, SE, ExitingCond, SplitCandidateCond)) 284*73471bf0Spatrick return false; 285*73471bf0Spatrick 286*73471bf0Spatrick if (!isProfitableToTransform(L, SplitCandidateCond.BI)) 287*73471bf0Spatrick return false; 288*73471bf0Spatrick 289*73471bf0Spatrick // Now, we have a split candidate. Let's build a form as below. 290*73471bf0Spatrick // +--------------------+ 291*73471bf0Spatrick // | preheader | 292*73471bf0Spatrick // | set up newbound | 293*73471bf0Spatrick // +--------------------+ 294*73471bf0Spatrick // | /----------------\ 295*73471bf0Spatrick // +--------v----v------+ | 296*73471bf0Spatrick // | header |---\ | 297*73471bf0Spatrick // | with true condition| | | 298*73471bf0Spatrick // +--------------------+ | | 299*73471bf0Spatrick // | | | 300*73471bf0Spatrick // +--------v-----------+ | | 301*73471bf0Spatrick // | if.then.BB | | | 302*73471bf0Spatrick // +--------------------+ | | 303*73471bf0Spatrick // | | | 304*73471bf0Spatrick // +--------v-----------<---/ | 305*73471bf0Spatrick // | latch >----------/ 306*73471bf0Spatrick // | with newbound | 307*73471bf0Spatrick // +--------------------+ 308*73471bf0Spatrick // | 309*73471bf0Spatrick // +--------v-----------+ 310*73471bf0Spatrick // | preheader2 |--------------\ 311*73471bf0Spatrick // | if (AddRec i != | | 312*73471bf0Spatrick // | org bound) | | 313*73471bf0Spatrick // +--------------------+ | 314*73471bf0Spatrick // | /----------------\ | 315*73471bf0Spatrick // +--------v----v------+ | | 316*73471bf0Spatrick // | header2 |---\ | | 317*73471bf0Spatrick // | conditional branch | | | | 318*73471bf0Spatrick // |with false condition| | | | 319*73471bf0Spatrick // +--------------------+ | | | 320*73471bf0Spatrick // | | | | 321*73471bf0Spatrick // +--------v-----------+ | | | 322*73471bf0Spatrick // | if.then.BB2 | | | | 323*73471bf0Spatrick // +--------------------+ | | | 324*73471bf0Spatrick // | | | | 325*73471bf0Spatrick // +--------v-----------<---/ | | 326*73471bf0Spatrick // | latch2 >----------/ | 327*73471bf0Spatrick // | with org bound | | 328*73471bf0Spatrick // +--------v-----------+ | 329*73471bf0Spatrick // | | 330*73471bf0Spatrick // | +---------------+ | 331*73471bf0Spatrick // +--> exit <-------/ 332*73471bf0Spatrick // +---------------+ 333*73471bf0Spatrick 334*73471bf0Spatrick // Let's create post loop. 335*73471bf0Spatrick SmallVector<BasicBlock *, 8> PostLoopBlocks; 336*73471bf0Spatrick Loop *PostLoop; 337*73471bf0Spatrick ValueToValueMapTy VMap; 338*73471bf0Spatrick BasicBlock *PreHeader = L.getLoopPreheader(); 339*73471bf0Spatrick BasicBlock *SplitLoopPH = SplitEdge(PreHeader, L.getHeader(), &DT, &LI); 340*73471bf0Spatrick PostLoop = cloneLoopWithPreheader(L.getExitBlock(), SplitLoopPH, &L, VMap, 341*73471bf0Spatrick ".split", &LI, &DT, PostLoopBlocks); 342*73471bf0Spatrick remapInstructionsInBlocks(PostLoopBlocks, VMap); 343*73471bf0Spatrick 344*73471bf0Spatrick // Add conditional branch to check we can skip post-loop in its preheader. 345*73471bf0Spatrick BasicBlock *PostLoopPreHeader = PostLoop->getLoopPreheader(); 346*73471bf0Spatrick IRBuilder<> Builder(PostLoopPreHeader); 347*73471bf0Spatrick Instruction *OrigBI = PostLoopPreHeader->getTerminator(); 348*73471bf0Spatrick ICmpInst::Predicate Pred = ICmpInst::ICMP_NE; 349*73471bf0Spatrick Value *Cond = 350*73471bf0Spatrick Builder.CreateICmp(Pred, ExitingCond.AddRecValue, ExitingCond.BoundValue); 351*73471bf0Spatrick Builder.CreateCondBr(Cond, PostLoop->getHeader(), PostLoop->getExitBlock()); 352*73471bf0Spatrick OrigBI->eraseFromParent(); 353*73471bf0Spatrick 354*73471bf0Spatrick // Create new loop bound and add it into preheader of pre-loop. 355*73471bf0Spatrick const SCEV *NewBoundSCEV = ExitingCond.BoundSCEV; 356*73471bf0Spatrick const SCEV *SplitBoundSCEV = SplitCandidateCond.BoundSCEV; 357*73471bf0Spatrick NewBoundSCEV = ICmpInst::isSigned(ExitingCond.Pred) 358*73471bf0Spatrick ? SE.getSMinExpr(NewBoundSCEV, SplitBoundSCEV) 359*73471bf0Spatrick : SE.getUMinExpr(NewBoundSCEV, SplitBoundSCEV); 360*73471bf0Spatrick 361*73471bf0Spatrick SCEVExpander Expander( 362*73471bf0Spatrick SE, L.getHeader()->getParent()->getParent()->getDataLayout(), "split"); 363*73471bf0Spatrick Instruction *InsertPt = SplitLoopPH->getTerminator(); 364*73471bf0Spatrick Value *NewBoundValue = 365*73471bf0Spatrick Expander.expandCodeFor(NewBoundSCEV, NewBoundSCEV->getType(), InsertPt); 366*73471bf0Spatrick NewBoundValue->setName("new.bound"); 367*73471bf0Spatrick 368*73471bf0Spatrick // Replace exiting bound value of pre-loop NewBound. 369*73471bf0Spatrick ExitingCond.ICmp->setOperand(1, NewBoundValue); 370*73471bf0Spatrick 371*73471bf0Spatrick // Replace IV's start value of post-loop by NewBound. 372*73471bf0Spatrick for (PHINode &PN : L.getHeader()->phis()) { 373*73471bf0Spatrick // Find PHI with exiting condition from pre-loop. 374*73471bf0Spatrick if (SE.isSCEVable(PN.getType()) && isa<SCEVAddRecExpr>(SE.getSCEV(&PN))) { 375*73471bf0Spatrick for (Value *Op : PN.incoming_values()) { 376*73471bf0Spatrick if (Op == ExitingCond.AddRecValue) { 377*73471bf0Spatrick // Find cloned PHI for post-loop. 378*73471bf0Spatrick PHINode *PostLoopPN = cast<PHINode>(VMap[&PN]); 379*73471bf0Spatrick PostLoopPN->setIncomingValueForBlock(PostLoopPreHeader, 380*73471bf0Spatrick NewBoundValue); 381*73471bf0Spatrick } 382*73471bf0Spatrick } 383*73471bf0Spatrick } 384*73471bf0Spatrick } 385*73471bf0Spatrick 386*73471bf0Spatrick // Replace SplitCandidateCond.BI's condition of pre-loop by True. 387*73471bf0Spatrick LLVMContext &Context = PreHeader->getContext(); 388*73471bf0Spatrick SplitCandidateCond.BI->setCondition(ConstantInt::getTrue(Context)); 389*73471bf0Spatrick 390*73471bf0Spatrick // Replace cloned SplitCandidateCond.BI's condition in post-loop by False. 391*73471bf0Spatrick BranchInst *ClonedSplitCandidateBI = 392*73471bf0Spatrick cast<BranchInst>(VMap[SplitCandidateCond.BI]); 393*73471bf0Spatrick ClonedSplitCandidateBI->setCondition(ConstantInt::getFalse(Context)); 394*73471bf0Spatrick 395*73471bf0Spatrick // Replace exit branch target of pre-loop by post-loop's preheader. 396*73471bf0Spatrick if (L.getExitBlock() == ExitingCond.BI->getSuccessor(0)) 397*73471bf0Spatrick ExitingCond.BI->setSuccessor(0, PostLoopPreHeader); 398*73471bf0Spatrick else 399*73471bf0Spatrick ExitingCond.BI->setSuccessor(1, PostLoopPreHeader); 400*73471bf0Spatrick 401*73471bf0Spatrick // Update dominator tree. 402*73471bf0Spatrick DT.changeImmediateDominator(PostLoopPreHeader, L.getExitingBlock()); 403*73471bf0Spatrick DT.changeImmediateDominator(PostLoop->getExitBlock(), PostLoopPreHeader); 404*73471bf0Spatrick 405*73471bf0Spatrick // Invalidate cached SE information. 406*73471bf0Spatrick SE.forgetLoop(&L); 407*73471bf0Spatrick 408*73471bf0Spatrick // Canonicalize loops. 409*73471bf0Spatrick // TODO: Try to update LCSSA information according to above change. 410*73471bf0Spatrick formLCSSA(L, DT, &LI, &SE); 411*73471bf0Spatrick simplifyLoop(&L, &DT, &LI, &SE, nullptr, nullptr, true); 412*73471bf0Spatrick formLCSSA(*PostLoop, DT, &LI, &SE); 413*73471bf0Spatrick simplifyLoop(PostLoop, &DT, &LI, &SE, nullptr, nullptr, true); 414*73471bf0Spatrick 415*73471bf0Spatrick // Add new post-loop to loop pass manager. 416*73471bf0Spatrick U.addSiblingLoops(PostLoop); 417*73471bf0Spatrick 418*73471bf0Spatrick return true; 419*73471bf0Spatrick } 420*73471bf0Spatrick 421*73471bf0Spatrick PreservedAnalyses LoopBoundSplitPass::run(Loop &L, LoopAnalysisManager &AM, 422*73471bf0Spatrick LoopStandardAnalysisResults &AR, 423*73471bf0Spatrick LPMUpdater &U) { 424*73471bf0Spatrick Function &F = *L.getHeader()->getParent(); 425*73471bf0Spatrick (void)F; 426*73471bf0Spatrick 427*73471bf0Spatrick LLVM_DEBUG(dbgs() << "Spliting bound of loop in " << F.getName() << ": " << L 428*73471bf0Spatrick << "\n"); 429*73471bf0Spatrick 430*73471bf0Spatrick if (!splitLoopBound(L, AR.DT, AR.LI, AR.SE, U)) 431*73471bf0Spatrick return PreservedAnalyses::all(); 432*73471bf0Spatrick 433*73471bf0Spatrick assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast)); 434*73471bf0Spatrick AR.LI.verify(AR.DT); 435*73471bf0Spatrick 436*73471bf0Spatrick return getLoopPassPreservedAnalyses(); 437*73471bf0Spatrick } 438*73471bf0Spatrick 439*73471bf0Spatrick } // end namespace llvm 440