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