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