lib/Transforms/Scalar/LoopIndexSplit.cpp

   1 //===- LoopIndexSplit.cpp - Loop Index Splitting Pass ---------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Devang Patel and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements Loop Index Splitting Pass.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "loop-index-split"
  15
  16 #include "llvm/Transforms/Scalar.h"
  17 #include "llvm/Function.h"
  18 #include "llvm/Analysis/LoopPass.h"
  19 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  20 #include "llvm/Analysis/Dominators.h"
  21 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  22 #include "llvm/Transforms/Utils/Cloning.h"
  23 #include "llvm/Support/Compiler.h"
  24 #include "llvm/ADT/Statistic.h"
  25
  26 using namespace llvm;
  27
  28 STATISTIC(NumIndexSplit, "Number of loops index split");
  29
  30 namespace {
  31
  32   class VISIBILITY_HIDDEN LoopIndexSplit : public LoopPass {
  33
  34   public:
  35     static char ID; // Pass ID, replacement for typeid
  36     LoopIndexSplit() : LoopPass((intptr_t)&ID) {}
  37
  38     // Index split Loop L. Return true if loop is split.
  39     bool runOnLoop(Loop *L, LPPassManager &LPM);
  40
  41     void getAnalysisUsage(AnalysisUsage &AU) const {
  42       AU.addRequired<ScalarEvolution>();
  43       AU.addPreserved<ScalarEvolution>();
  44       AU.addRequiredID(LCSSAID);
  45       AU.addPreservedID(LCSSAID);
  46       AU.addRequired<LoopInfo>();
  47       AU.addPreserved<LoopInfo>();
  48       AU.addRequiredID(LoopSimplifyID);
  49       AU.addPreservedID(LoopSimplifyID);
  50       AU.addRequired<DominatorTree>();
  51       AU.addPreserved<DominatorTree>();
  52       AU.addPreserved<DominanceFrontier>();
  53     }
  54
  55   private:
  56
  57     class SplitInfo {
  58     public:
  59       SplitInfo() : SplitValue(NULL), SplitCondition(NULL) {}
  60
  61       // Induction variable's range is split at this value.
  62       Value *SplitValue;
  63
  64       // This compare instruction compares IndVar against SplitValue.
  65       ICmpInst *SplitCondition;
  66
  67       // Clear split info.
  68       void clear() {
  69         SplitValue = NULL;
  70         SplitCondition = NULL;
  71       }
  72
  73     };
  74
  75   private:
  76     /// Find condition inside a loop that is suitable candidate for index split.
  77     void findSplitCondition();
  78
  79     /// Find loop's exit condition.
  80     void findLoopConditionals();
  81
  82     /// Return induction variable associated with value V.
  83     void findIndVar(Value *V, Loop *L);
  84
  85     /// processOneIterationLoop - Current loop L contains compare instruction
  86     /// that compares induction variable, IndVar, agains loop invariant. If
  87     /// entire (i.e. meaningful) loop body is dominated by this compare
  88     /// instruction then loop body is executed only for one iteration. In
  89     /// such case eliminate loop structure surrounding this loop body. For
  90     bool processOneIterationLoop(SplitInfo &SD);
  91
  92     /// If loop header includes loop variant instruction operands then
  93     /// this loop may not be eliminated.
  94     bool safeHeader(SplitInfo &SD,  BasicBlock *BB);
  95
  96     /// If Exit block includes loop variant instructions then this
  97     /// loop may not be eliminated.
  98     bool safeExitBlock(SplitInfo &SD, BasicBlock *BB);
  99
 100     /// removeBlocks - Remove basic block DeadBB and all blocks dominated by DeadBB.
 101     /// This routine is used to remove split condition's dead branch, dominated by
 102     /// DeadBB. LiveBB dominates split conidition's other branch.
 103     void removeBlocks(BasicBlock *DeadBB, Loop *LP, BasicBlock *LiveBB);
 104
 105     /// Find cost of spliting loop L.
 106     unsigned findSplitCost(Loop *L, SplitInfo &SD);
 107     bool splitLoop(SplitInfo &SD);
 108
 109     void initialize() {
 110       IndVar = NULL;
 111       IndVarIncrement = NULL;
 112       ExitCondition = NULL;
 113       StartValue = NULL;
 114       ExitValueNum = 0;
 115       SplitData.clear();
 116     }
 117
 118   private:
 119
 120     // Current Loop.
 121     Loop *L;
 122     LPPassManager *LPM;
 123     LoopInfo *LI;
 124     ScalarEvolution *SE;
 125     DominatorTree *DT;
 126     DominanceFrontier *DF;
 127     SmallVector<SplitInfo, 4> SplitData;
 128
 129     // Induction variable whose range is being split by this transformation.
 130     PHINode *IndVar;
 131     Instruction *IndVarIncrement;
 132
 133     // Loop exit condition.
 134     ICmpInst *ExitCondition;
 135
 136     // Induction variable's initial value.
 137     Value *StartValue;
 138
 139     // Induction variable's final loop exit value operand number in exit condition..
 140     unsigned ExitValueNum;
 141   };
 142
 143   char LoopIndexSplit::ID = 0;
 144   RegisterPass<LoopIndexSplit> X ("loop-index-split", "Index Split Loops");
 145 }
 146
 147 LoopPass *llvm::createLoopIndexSplitPass() {
 148   return new LoopIndexSplit();
 149 }
 150
 151 // Index split Loop L. Return true if loop is split.
 152 bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) {
 153   bool Changed = false;
 154   L = IncomingLoop;
 155   LPM = &LPM_Ref;
 156
 157   // FIXME - Nested loops makes dominator info updates tricky.
 158   if (!L->getSubLoops().empty())
 159     return false;
 160
 161   SE = &getAnalysis<ScalarEvolution>();
 162   DT = &getAnalysis<DominatorTree>();
 163   LI = &getAnalysis<LoopInfo>();
 164   DF = getAnalysisToUpdate<DominanceFrontier>();
 165
 166   initialize();
 167
 168   findLoopConditionals();
 169
 170   if (!ExitCondition)
 171     return false;
 172
 173   findSplitCondition();
 174
 175   if (SplitData.empty())
 176     return false;
 177
 178   // First see if it is possible to eliminate loop itself or not.
 179   for (SmallVector<SplitInfo, 4>::iterator SI = SplitData.begin(),
 180          E = SplitData.end(); SI != E; ++SI) {
 181     SplitInfo &SD = *SI;
 182     if (SD.SplitCondition->getPredicate() == ICmpInst::ICMP_EQ) {
 183       Changed = processOneIterationLoop(SD);
 184       if (Changed) {
 185         ++NumIndexSplit;
 186         // If is loop is eliminated then nothing else to do here.
 187         return Changed;
 188       }
 189     }
 190   }
 191
 192   unsigned MaxCost = 99;
 193   unsigned Index = 0;
 194   unsigned MostProfitableSDIndex = 0;
 195   for (SmallVector<SplitInfo, 4>::iterator SI = SplitData.begin(),
 196          E = SplitData.end(); SI != E; ++SI, ++Index) {
 197     SplitInfo SD = *SI;
 198
 199     // ICM_EQs are already handled above.
 200     if (SD.SplitCondition->getPredicate() == ICmpInst::ICMP_EQ)
 201       continue;
 202
 203     unsigned Cost = findSplitCost(L, SD);
 204     if (Cost < MaxCost)
 205       MostProfitableSDIndex = Index;
 206   }
 207
 208   // Split most profitiable condition.
 209   Changed = splitLoop(SplitData[MostProfitableSDIndex]);
 210
 211   if (Changed)
 212     ++NumIndexSplit;
 213
 214   return Changed;
 215 }
 216
 217 /// Return true if V is a induction variable or induction variable's
 218 /// increment for loop L.
 219 void LoopIndexSplit::findIndVar(Value *V, Loop *L) {
 220
 221   Instruction *I = dyn_cast<Instruction>(V);
 222   if (!I)
 223     return;
 224
 225   // Check if I is a phi node from loop header or not.
 226   if (PHINode *PN = dyn_cast<PHINode>(V)) {
 227     if (PN->getParent() == L->getHeader()) {
 228       IndVar = PN;
 229       return;
 230     }
 231   }
 232
 233   // Check if I is a add instruction whose one operand is
 234   // phi node from loop header and second operand is constant.
 235   if (I->getOpcode() != Instruction::Add)
 236     return;
 237
 238   Value *Op0 = I->getOperand(0);
 239   Value *Op1 = I->getOperand(1);
 240
 241   if (PHINode *PN = dyn_cast<PHINode>(Op0)) {
 242     if (PN->getParent() == L->getHeader()
 243         && isa<ConstantInt>(Op1)) {
 244       IndVar = PN;
 245       IndVarIncrement = I;
 246       return;
 247     }
 248   }
 249
 250   if (PHINode *PN = dyn_cast<PHINode>(Op1)) {
 251     if (PN->getParent() == L->getHeader()
 252         && isa<ConstantInt>(Op0)) {
 253       IndVar = PN;
 254       IndVarIncrement = I;
 255       return;
 256     }
 257   }
 258
 259   return;
 260 }
 261
 262 // Find loop's exit condition and associated induction variable.
 263 void LoopIndexSplit::findLoopConditionals() {
 264
 265   BasicBlock *ExitBlock = NULL;
 266
 267   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 268        I != E; ++I) {
 269     BasicBlock *BB = *I;
 270     if (!L->isLoopExit(BB))
 271       continue;
 272     if (ExitBlock)
 273       return;
 274     ExitBlock = BB;
 275   }
 276
 277   if (!ExitBlock)
 278     return;
 279
 280   // If exit block's terminator is conditional branch inst then we have found
 281   // exit condition.
 282   BranchInst *BR = dyn_cast<BranchInst>(ExitBlock->getTerminator());
 283   if (!BR || BR->isUnconditional())
 284     return;
 285
 286   ICmpInst *CI = dyn_cast<ICmpInst>(BR->getCondition());
 287   if (!CI)
 288     return;
 289
 290   ExitCondition = CI;
 291
 292   // Exit condition's one operand is loop invariant exit value and second
 293   // operand is SCEVAddRecExpr based on induction variable.
 294   Value *V0 = CI->getOperand(0);
 295   Value *V1 = CI->getOperand(1);
 296
 297   SCEVHandle SH0 = SE->getSCEV(V0);
 298   SCEVHandle SH1 = SE->getSCEV(V1);
 299
 300   if (SH0->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH1)) {
 301     ExitValueNum = 0;
 302     findIndVar(V1, L);
 303   }
 304   else if (SH1->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH0)) {
 305     ExitValueNum =  1;
 306     findIndVar(V0, L);
 307   }
 308
 309   if (!IndVar)
 310     ExitCondition = NULL;
 311   else if (IndVar) {
 312     BasicBlock *Preheader = L->getLoopPreheader();
 313     StartValue = IndVar->getIncomingValueForBlock(Preheader);
 314   }
 315 }
 316
 317 /// Find condition inside a loop that is suitable candidate for index split.
 318 void LoopIndexSplit::findSplitCondition() {
 319
 320   SplitInfo SD;
 321   // Check all basic block's terminators.
 322
 323   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 324        I != E; ++I) {
 325     BasicBlock *BB = *I;
 326
 327     // If this basic block does not terminate in a conditional branch
 328     // then terminator is not a suitable split condition.
 329     BranchInst *BR = dyn_cast<BranchInst>(BB->getTerminator());
 330     if (!BR)
 331       continue;
 332
 333     if (BR->isUnconditional())
 334       continue;
 335
 336     ICmpInst *CI = dyn_cast<ICmpInst>(BR->getCondition());
 337     if (!CI || CI == ExitCondition)
 338       return;
 339
 340     // If one operand is loop invariant and second operand is SCEVAddRecExpr
 341     // based on induction variable then CI is a candidate split condition.
 342     Value *V0 = CI->getOperand(0);
 343     Value *V1 = CI->getOperand(1);
 344
 345     SCEVHandle SH0 = SE->getSCEV(V0);
 346     SCEVHandle SH1 = SE->getSCEV(V1);
 347
 348     if (SH0->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH1)) {
 349       SD.SplitValue = V0;
 350       SD.SplitCondition = CI;
 351       if (PHINode *PN = dyn_cast<PHINode>(V1)) {
 352         if (PN == IndVar)
 353           SplitData.push_back(SD);
 354       }
 355       else  if (Instruction *Insn = dyn_cast<Instruction>(V1)) {
 356         if (IndVarIncrement && IndVarIncrement == Insn)
 357           SplitData.push_back(SD);
 358       }
 359     }
 360     else if (SH1->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH0)) {
 361       SD.SplitValue =  V1;
 362       SD.SplitCondition = CI;
 363       if (PHINode *PN = dyn_cast<PHINode>(V0)) {
 364         if (PN == IndVar)
 365           SplitData.push_back(SD);
 366       }
 367       else  if (Instruction *Insn = dyn_cast<Instruction>(V0)) {
 368         if (IndVarIncrement && IndVarIncrement == Insn)
 369           SplitData.push_back(SD);
 370       }
 371     }
 372   }
 373 }
 374
 375 /// processOneIterationLoop - Current loop L contains compare instruction
 376 /// that compares induction variable, IndVar, against loop invariant. If
 377 /// entire (i.e. meaningful) loop body is dominated by this compare
 378 /// instruction then loop body is executed only once. In such case eliminate
 379 /// loop structure surrounding this loop body. For example,
 380 ///     for (int i = start; i < end; ++i) {
 381 ///         if ( i == somevalue) {
 382 ///           loop_body
 383 ///         }
 384 ///     }
 385 /// can be transformed into
 386 ///     if (somevalue >= start && somevalue < end) {
 387 ///        i = somevalue;
 388 ///        loop_body
 389 ///     }
 390 bool LoopIndexSplit::processOneIterationLoop(SplitInfo &SD) {
 391
 392   BasicBlock *Header = L->getHeader();
 393
 394   // First of all, check if SplitCondition dominates entire loop body
 395   // or not.
 396
 397   // If SplitCondition is not in loop header then this loop is not suitable
 398   // for this transformation.
 399   if (SD.SplitCondition->getParent() != Header)
 400     return false;
 401
 402   // If loop header includes loop variant instruction operands then
 403   // this loop may not be eliminated.
 404   if (!safeHeader(SD, Header))
 405     return false;
 406
 407   // If Exit block includes loop variant instructions then this
 408   // loop may not be eliminated.
 409   if (!safeExitBlock(SD, ExitCondition->getParent()))
 410     return false;
 411
 412   // Update CFG.
 413
 414   // As a first step to break this loop, remove Latch to Header edge.
 415   BasicBlock *Latch = L->getLoopLatch();
 416   BasicBlock *LatchSucc = NULL;
 417   BranchInst *BR = dyn_cast<BranchInst>(Latch->getTerminator());
 418   if (!BR)
 419     return false;
 420   Header->removePredecessor(Latch);
 421   for (succ_iterator SI = succ_begin(Latch), E = succ_end(Latch);
 422        SI != E; ++SI) {
 423     if (Header != *SI)
 424       LatchSucc = *SI;
 425   }
 426   BR->setUnconditionalDest(LatchSucc);
 427
 428   Instruction *Terminator = Header->getTerminator();
 429   Value *ExitValue = ExitCondition->getOperand(ExitValueNum);
 430
 431   // Replace split condition in header.
 432   // Transform
 433   //      SplitCondition : icmp eq i32 IndVar, SplitValue
 434   // into
 435   //      c1 = icmp uge i32 SplitValue, StartValue
 436   //      c2 = icmp ult i32 vSplitValue, ExitValue
 437   //      and i32 c1, c2
 438   bool SignedPredicate = ExitCondition->isSignedPredicate();
 439   Instruction *C1 = new ICmpInst(SignedPredicate ?
 440                                  ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE,
 441                                  SD.SplitValue, StartValue, "lisplit",
 442                                  Terminator);
 443   Instruction *C2 = new ICmpInst(SignedPredicate ?
 444                                  ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 445                                  SD.SplitValue, ExitValue, "lisplit",
 446                                  Terminator);
 447   Instruction *NSplitCond = BinaryOperator::createAnd(C1, C2, "lisplit",
 448                                                       Terminator);
 449   SD.SplitCondition->replaceAllUsesWith(NSplitCond);
 450   SD.SplitCondition->eraseFromParent();
 451
 452   // Now, clear latch block. Remove instructions that are responsible
 453   // to increment induction variable.
 454   Instruction *LTerminator = Latch->getTerminator();
 455   for (BasicBlock::iterator LB = Latch->begin(), LE = Latch->end();
 456        LB != LE; ) {
 457     Instruction *I = LB;
 458     ++LB;
 459     if (isa<PHINode>(I) || I == LTerminator)
 460       continue;
 461
 462     if (I == IndVarIncrement)
 463       I->replaceAllUsesWith(ExitValue);
 464     else
 465       I->replaceAllUsesWith(UndefValue::get(I->getType()));
 466     I->eraseFromParent();
 467   }
 468
 469   LPM->deleteLoopFromQueue(L);
 470
 471   // Update Dominator Info.
 472   // Only CFG change done is to remove Latch to Header edge. This
 473   // does not change dominator tree because Latch did not dominate
 474   // Header.
 475   if (DF) {
 476     DominanceFrontier::iterator HeaderDF = DF->find(Header);
 477     if (HeaderDF != DF->end())
 478       DF->removeFromFrontier(HeaderDF, Header);
 479
 480     DominanceFrontier::iterator LatchDF = DF->find(Latch);
 481     if (LatchDF != DF->end())
 482       DF->removeFromFrontier(LatchDF, Header);
 483   }
 484   return true;
 485 }
 486
 487 // If loop header includes loop variant instruction operands then
 488 // this loop can not be eliminated. This is used by processOneIterationLoop().
 489 bool LoopIndexSplit::safeHeader(SplitInfo &SD, BasicBlock *Header) {
 490
 491   Instruction *Terminator = Header->getTerminator();
 492   for(BasicBlock::iterator BI = Header->begin(), BE = Header->end();
 493       BI != BE; ++BI) {
 494     Instruction *I = BI;
 495
 496     // PHI Nodes are OK.
 497     if (isa<PHINode>(I))
 498       continue;
 499
 500     // SplitCondition itself is OK.
 501     if (I == SD.SplitCondition)
 502       continue;
 503
 504     // Induction variable is OK.
 505     if (I == IndVar)
 506       continue;
 507
 508     // Induction variable increment is OK.
 509     if (I == IndVarIncrement)
 510       continue;
 511
 512     // Terminator is also harmless.
 513     if (I == Terminator)
 514       continue;
 515
 516     // Otherwise we have a instruction that may not be safe.
 517     return false;
 518   }
 519
 520   return true;
 521 }
 522
 523 // If Exit block includes loop variant instructions then this
 524 // loop may not be eliminated. This is used by processOneIterationLoop().
 525 bool LoopIndexSplit::safeExitBlock(SplitInfo &SD, BasicBlock *ExitBlock) {
 526
 527   for (BasicBlock::iterator BI = ExitBlock->begin(), BE = ExitBlock->end();
 528        BI != BE; ++BI) {
 529     Instruction *I = BI;
 530
 531     // PHI Nodes are OK.
 532     if (isa<PHINode>(I))
 533       continue;
 534
 535     // Induction variable increment is OK.
 536     if (IndVarIncrement && IndVarIncrement == I)
 537       continue;
 538
 539     // Check if I is induction variable increment instruction.
 540     if (!IndVarIncrement && I->getOpcode() == Instruction::Add) {
 541
 542       Value *Op0 = I->getOperand(0);
 543       Value *Op1 = I->getOperand(1);
 544       PHINode *PN = NULL;
 545       ConstantInt *CI = NULL;
 546
 547       if ((PN = dyn_cast<PHINode>(Op0))) {
 548         if ((CI = dyn_cast<ConstantInt>(Op1)))
 549           IndVarIncrement = I;
 550       } else
 551         if ((PN = dyn_cast<PHINode>(Op1))) {
 552           if ((CI = dyn_cast<ConstantInt>(Op0)))
 553             IndVarIncrement = I;
 554       }
 555
 556       if (IndVarIncrement && PN == IndVar && CI->isOne())
 557         continue;
 558     }
 559
 560     // I is an Exit condition if next instruction is block terminator.
 561     // Exit condition is OK if it compares loop invariant exit value,
 562     // which is checked below.
 563     else if (ICmpInst *EC = dyn_cast<ICmpInst>(I)) {
 564       if (EC == ExitCondition)
 565         continue;
 566     }
 567
 568     if (I == ExitBlock->getTerminator())
 569       continue;
 570
 571     // Otherwise we have instruction that may not be safe.
 572     return false;
 573   }
 574
 575   // We could not find any reason to consider ExitBlock unsafe.
 576   return true;
 577 }
 578
 579 /// Find cost of spliting loop L. Cost is measured in terms of size growth.
 580 /// Size is growth is calculated based on amount of code duplicated in second
 581 /// loop.
 582 unsigned LoopIndexSplit::findSplitCost(Loop *L, SplitInfo &SD) {
 583
 584   unsigned Cost = 0;
 585   BasicBlock *SDBlock = SD.SplitCondition->getParent();
 586   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 587        I != E; ++I) {
 588     BasicBlock *BB = *I;
 589     // If a block is not dominated by split condition block then
 590     // it must be duplicated in both loops.
 591     if (!DT->dominates(SDBlock, BB))
 592       Cost += BB->size();
 593   }
 594
 595   return Cost;
 596 }
 597
 598 /// removeBlocks - Remove basic block DeadBB and all blocks dominated by DeadBB.
 599 /// This routine is used to remove split condition's dead branch, dominated by
 600 /// DeadBB. LiveBB dominates split conidition's other branch.
 601 void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP,
 602                                   BasicBlock *LiveBB) {
 603
 604   SmallVector<std::pair<BasicBlock *, succ_iterator>, 8> WorkList;
 605   WorkList.push_back(std::make_pair(DeadBB, succ_begin(DeadBB)));
 606   while (!WorkList.empty()) {
 607     BasicBlock *BB = WorkList.back(). first;
 608     succ_iterator SIter =WorkList.back().second;
 609
 610     // If all successor's are processed then remove this block.
 611     if (SIter == succ_end(BB)) {
 612       WorkList.pop_back();
 613       for(BasicBlock::iterator BBI = BB->begin(), BBE = BB->end();
 614           BBI != BBE; ++BBI) {
 615         Instruction *I = BBI;
 616         I->replaceAllUsesWith(UndefValue::get(I->getType()));
 617         I->eraseFromParent();
 618       }
 619       LPM->deleteSimpleAnalysisValue(BB, LP);
 620       DT->eraseNode(BB);
 621       DF->removeBlock(BB);
 622       LI->removeBlock(BB);
 623       BB->eraseFromParent();
 624     } else {
 625       BasicBlock *SuccBB = *SIter;
 626       ++WorkList.back().second;
 627
 628       if (DT->dominates(BB, SuccBB)) {
 629         WorkList.push_back(std::make_pair(SuccBB, succ_begin(SuccBB)));
 630         continue;
 631       } else {
 632         // If SuccBB is not dominated by BB then it is not removed, however remove
 633         // any PHI incoming edge from BB.
 634         for(BasicBlock::iterator SBI = SuccBB->begin(), SBE = SuccBB->end();
 635             SBI != SBE; ++SBI) {
 636           if (PHINode *PN = dyn_cast<PHINode>(SBI))
 637             PN->removeIncomingValue(BB);
 638           else
 639             break;
 640         }
 641
 642         DT->changeImmediateDominator(SuccBB, LiveBB);
 643
 644         // If BB is not dominating SuccBB then SuccBB is in BB's dominance
 645         // frontiner.
 646         DominanceFrontier::iterator BBDF = DF->find(BB);
 647         DF->removeFromFrontier(BBDF, SuccBB);
 648
 649         // LiveBB is now  dominating SuccBB. Which means SuccBB's dominance
 650         // frontier is member of LiveBB's dominance frontier. However, SuccBB
 651         // itself is not member of LiveBB's dominance frontier.
 652         DominanceFrontier::iterator LiveDF = DF->find(LiveBB);
 653         DominanceFrontier::iterator SuccDF = DF->find(SuccBB);
 654         DominanceFrontier::DomSetType SuccBBSet = SuccDF->second;
 655         for (DominanceFrontier::DomSetType::iterator SuccBBSetI = SuccBBSet.begin(),
 656                SuccBBSetE = SuccBBSet.end(); SuccBBSetI != SuccBBSetE; ++SuccBBSetI) {
 657           BasicBlock *DFMember = *SuccBBSetI;
 658           // Insert only if LiveBB dominates DFMember.
 659           if (!DT->dominates(LiveBB, DFMember))
 660             LiveDF->second.insert(DFMember);
 661         }
 662         DF->removeFromFrontier(LiveDF, SuccBB);
 663
 664       }
 665     }
 666   }
 667 }
 668
 669 bool LoopIndexSplit::splitLoop(SplitInfo &SD) {
 670
 671   BasicBlock *Preheader = L->getLoopPreheader();
 672
 673   // True loop is original loop. False loop is cloned loop.
 674
 675   bool SignedPredicate = ExitCondition->isSignedPredicate();
 676   //[*] Calculate True loop's new Exit Value in loop preheader.
 677   //      TLExitValue = min(SplitValue, ExitValue)
 678   //[*] Calculate False loop's new Start Value in loop preheader.
 679   //      FLStartValue = min(SplitValue, TrueLoop.StartValue)
 680   Value *TLExitValue = NULL;
 681   Value *FLStartValue = NULL;
 682   if (isa<ConstantInt>(SD.SplitValue)) {
 683     TLExitValue = SD.SplitValue;
 684     FLStartValue = SD.SplitValue;
 685   }
 686   else {
 687     Value *C1 = new ICmpInst(SignedPredicate ?
 688                             ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 689                             SD.SplitValue,
 690                              ExitCondition->getOperand(ExitValueNum),
 691                              "lsplit.ev",
 692                             Preheader->getTerminator());
 693     TLExitValue = new SelectInst(C1, SD.SplitValue,
 694                                  ExitCondition->getOperand(ExitValueNum),
 695                                  "lsplit.ev", Preheader->getTerminator());
 696
 697     Value *C2 = new ICmpInst(SignedPredicate ?
 698                              ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 699                              SD.SplitValue, StartValue, "lsplit.sv",
 700                              Preheader->getTerminator());
 701     FLStartValue = new SelectInst(C2, SD.SplitValue, StartValue,
 702                                   "lsplit.sv", Preheader->getTerminator());
 703   }
 704
 705   //[*] Clone loop. Avoid true destination of split condition and
 706   //    the blocks dominated by true destination.
 707   DenseMap<const Value *, Value *> ValueMap;
 708   Loop *FalseLoop = CloneLoop(L, LPM, LI, ValueMap, this);
 709   BasicBlock *FalseHeader = FalseLoop->getHeader();
 710
 711   //[*] True loop's exit edge enters False loop.
 712   PHINode *IndVarClone = cast<PHINode>(ValueMap[IndVar]);
 713   BasicBlock *ExitBlock = ExitCondition->getParent();
 714   BranchInst *ExitInsn = dyn_cast<BranchInst>(ExitBlock->getTerminator());
 715   assert (ExitInsn && "Unable to find suitable loop exit branch");
 716   BasicBlock *ExitDest = ExitInsn->getSuccessor(1);
 717
 718   if (L->contains(ExitDest)) {
 719     ExitDest = ExitInsn->getSuccessor(0);
 720     ExitInsn->setSuccessor(0, FalseHeader);
 721   } else
 722     ExitInsn->setSuccessor(1, FalseHeader);
 723
 724   // Collect inverse map of Header PHINodes.
 725   DenseMap<Value *, Value *> InverseMap;
 726   for (BasicBlock::iterator BI = L->getHeader()->begin(),
 727          BE = L->getHeader()->end(); BI != BE; ++BI) {
 728     if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 729       PHINode *PNClone = cast<PHINode>(ValueMap[PN]);
 730       InverseMap[PNClone] = PN;
 731     } else
 732       break;
 733   }
 734
 735   // Update False loop's header
 736   for (BasicBlock::iterator BI = FalseHeader->begin(), BE = FalseHeader->end();
 737        BI != BE; ++BI) {
 738     if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 739       PN->removeIncomingValue(Preheader);
 740       if (PN == IndVarClone)
 741         PN->addIncoming(FLStartValue, ExitBlock);
 742       else {
 743         PHINode *OrigPN = cast<PHINode>(InverseMap[PN]);
 744         Value *V2 = OrigPN->getIncomingValueForBlock(ExitBlock);
 745         PN->addIncoming(V2, ExitBlock);
 746       }
 747     } else
 748       break;
 749   }
 750
 751   // Update ExitDest. Now it's predecessor is False loop's exit block.
 752   BasicBlock *ExitBlockClone = cast<BasicBlock>(ValueMap[ExitBlock]);
 753   for (BasicBlock::iterator BI = ExitDest->begin(), BE = ExitDest->end();
 754        BI != BE; ++BI) {
 755     if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 756       PN->addIncoming(ValueMap[PN->getIncomingValueForBlock(ExitBlock)], ExitBlockClone);
 757       PN->removeIncomingValue(ExitBlock);
 758     } else
 759       break;
 760   }
 761
 762   if (DT) {
 763     DT->changeImmediateDominator(FalseHeader, ExitBlock);
 764     DT->changeImmediateDominator(ExitDest, cast<BasicBlock>(ValueMap[ExitBlock]));
 765   }
 766
 767   assert (!L->contains(ExitDest) && " Unable to find exit edge destination");
 768
 769   //[*] Split Exit Edge.
 770   SplitEdge(ExitBlock, FalseHeader, this);
 771
 772   //[*] Eliminate split condition's false branch from True loop.
 773   BasicBlock *SplitBlock = SD.SplitCondition->getParent();
 774   BranchInst *BR = cast<BranchInst>(SplitBlock->getTerminator());
 775   BasicBlock *FBB = BR->getSuccessor(1);
 776   BR->setUnconditionalDest(BR->getSuccessor(0));
 777   removeBlocks(FBB, L, BR->getSuccessor(0));
 778
 779   //[*] Update True loop's exit value using new exit value.
 780   ExitCondition->setOperand(ExitValueNum, TLExitValue);
 781
 782   //[*] Eliminate split condition's  true branch in False loop CFG.
 783   BasicBlock *FSplitBlock = cast<BasicBlock>(ValueMap[SplitBlock]);
 784   BranchInst *FBR = cast<BranchInst>(FSplitBlock->getTerminator());
 785   BasicBlock *TBB = FBR->getSuccessor(0);
 786   FBR->setUnconditionalDest(FBR->getSuccessor(1));
 787   removeBlocks(TBB, FalseLoop, cast<BasicBlock>(FBR->getSuccessor(0)));
 788
 789   return true;
 790 }
 791