llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

   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