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/Analysis/LoopPass.h"
  18 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  19 #include "llvm/Analysis/Dominators.h"
  20 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  21 #include "llvm/Transforms/Utils/Cloning.h"
  22 #include "llvm/Support/Compiler.h"
  23 #include "llvm/ADT/DepthFirstIterator.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.addRequired<DominanceFrontier>();
  52       AU.addPreserved<DominatorTree>();
  53       AU.addPreserved<DominanceFrontier>();
  54     }
  55
  56   private:
  57
  58     class SplitInfo {
  59     public:
  60       SplitInfo() : SplitValue(NULL), SplitCondition(NULL) {}
  61
  62       // Induction variable's range is split at this value.
  63       Value *SplitValue;
  64
  65       // This compare instruction compares IndVar against SplitValue.
  66       ICmpInst *SplitCondition;
  67
  68       // Clear split info.
  69       void clear() {
  70         SplitValue = NULL;
  71         SplitCondition = NULL;
  72       }
  73
  74     };
  75
  76   private:
  77     /// Find condition inside a loop that is suitable candidate for index split.
  78     void findSplitCondition();
  79
  80     /// Find loop's exit condition.
  81     void findLoopConditionals();
  82
  83     /// Return induction variable associated with value V.
  84     void findIndVar(Value *V, Loop *L);
  85
  86     /// processOneIterationLoop - Current loop L contains compare instruction
  87     /// that compares induction variable, IndVar, agains loop invariant. If
  88     /// entire (i.e. meaningful) loop body is dominated by this compare
  89     /// instruction then loop body is executed only for one iteration. In
  90     /// such case eliminate loop structure surrounding this loop body. For
  91     bool processOneIterationLoop(SplitInfo &SD);
  92
  93     /// If loop header includes loop variant instruction operands then
  94     /// this loop may not be eliminated.
  95     bool safeHeader(SplitInfo &SD,  BasicBlock *BB);
  96
  97     /// If Exiting block includes loop variant instructions then this
  98     /// loop may not be eliminated.
  99     bool safeExitingBlock(SplitInfo &SD, BasicBlock *BB);
 100
 101     /// removeBlocks - Remove basic block DeadBB and all blocks dominated by DeadBB.
 102     /// This routine is used to remove split condition's dead branch, dominated by
 103     /// DeadBB. LiveBB dominates split conidition's other branch.
 104     void removeBlocks(BasicBlock *DeadBB, Loop *LP, BasicBlock *LiveBB);
 105
 106     /// safeSplitCondition - Return true if it is possible to
 107     /// split loop using given split condition.
 108     bool safeSplitCondition(SplitInfo &SD);
 109
 110     /// splitLoop - Split current loop L in two loops using split information
 111     /// SD. Update dominator information. Maintain LCSSA form.
 112     bool splitLoop(SplitInfo &SD);
 113
 114     void initialize() {
 115       IndVar = NULL;
 116       IndVarIncrement = NULL;
 117       ExitCondition = NULL;
 118       StartValue = NULL;
 119       ExitValueNum = 0;
 120       SplitData.clear();
 121     }
 122
 123   private:
 124
 125     // Current Loop.
 126     Loop *L;
 127     LPPassManager *LPM;
 128     LoopInfo *LI;
 129     ScalarEvolution *SE;
 130     DominatorTree *DT;
 131     DominanceFrontier *DF;
 132     SmallVector<SplitInfo, 4> SplitData;
 133
 134     // Induction variable whose range is being split by this transformation.
 135     PHINode *IndVar;
 136     Instruction *IndVarIncrement;
 137
 138     // Loop exit condition.
 139     ICmpInst *ExitCondition;
 140
 141     // Induction variable's initial value.
 142     Value *StartValue;
 143
 144     // Induction variable's final loop exit value operand number in exit condition..
 145     unsigned ExitValueNum;
 146   };
 147
 148   char LoopIndexSplit::ID = 0;
 149   RegisterPass<LoopIndexSplit> X ("loop-index-split", "Index Split Loops");
 150 }
 151
 152 LoopPass *llvm::createLoopIndexSplitPass() {
 153   return new LoopIndexSplit();
 154 }
 155
 156 // Index split Loop L. Return true if loop is split.
 157 bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) {
 158   bool Changed = false;
 159   L = IncomingLoop;
 160   LPM = &LPM_Ref;
 161
 162   // FIXME - Nested loops make dominator info updates tricky.
 163   if (!L->getSubLoops().empty())
 164     return false;
 165
 166   SE = &getAnalysis<ScalarEvolution>();
 167   DT = &getAnalysis<DominatorTree>();
 168   LI = &getAnalysis<LoopInfo>();
 169   DF = &getAnalysis<DominanceFrontier>();
 170
 171   initialize();
 172
 173   findLoopConditionals();
 174
 175   if (!ExitCondition)
 176     return false;
 177
 178   findSplitCondition();
 179
 180   if (SplitData.empty())
 181     return false;
 182
 183   // First see if it is possible to eliminate loop itself or not.
 184   for (SmallVector<SplitInfo, 4>::iterator SI = SplitData.begin(),
 185          E = SplitData.end(); SI != E;) {
 186     SplitInfo &SD = *SI;
 187     if (SD.SplitCondition->getPredicate() == ICmpInst::ICMP_EQ) {
 188       Changed = processOneIterationLoop(SD);
 189       if (Changed) {
 190         ++NumIndexSplit;
 191         // If is loop is eliminated then nothing else to do here.
 192         return Changed;
 193       } else {
 194         SmallVector<SplitInfo, 4>::iterator Delete_SI = SI;
 195         ++SI;
 196         SplitData.erase(Delete_SI);
 197       }
 198     } else
 199       ++SI;
 200   }
 201
 202   // Split most profitiable condition.
 203   // FIXME : Implement cost analysis.
 204   unsigned MostProfitableSDIndex = 0;
 205   Changed = splitLoop(SplitData[MostProfitableSDIndex]);
 206
 207   if (Changed)
 208     ++NumIndexSplit;
 209
 210   return Changed;
 211 }
 212
 213 /// Return true if V is a induction variable or induction variable's
 214 /// increment for loop L.
 215 void LoopIndexSplit::findIndVar(Value *V, Loop *L) {
 216
 217   Instruction *I = dyn_cast<Instruction>(V);
 218   if (!I)
 219     return;
 220
 221   // Check if I is a phi node from loop header or not.
 222   if (PHINode *PN = dyn_cast<PHINode>(V)) {
 223     if (PN->getParent() == L->getHeader()) {
 224       IndVar = PN;
 225       return;
 226     }
 227   }
 228
 229   // Check if I is a add instruction whose one operand is
 230   // phi node from loop header and second operand is constant.
 231   if (I->getOpcode() != Instruction::Add)
 232     return;
 233
 234   Value *Op0 = I->getOperand(0);
 235   Value *Op1 = I->getOperand(1);
 236
 237   if (PHINode *PN = dyn_cast<PHINode>(Op0)) {
 238     if (PN->getParent() == L->getHeader()
 239         && isa<ConstantInt>(Op1)) {
 240       IndVar = PN;
 241       IndVarIncrement = I;
 242       return;
 243     }
 244   }
 245
 246   if (PHINode *PN = dyn_cast<PHINode>(Op1)) {
 247     if (PN->getParent() == L->getHeader()
 248         && isa<ConstantInt>(Op0)) {
 249       IndVar = PN;
 250       IndVarIncrement = I;
 251       return;
 252     }
 253   }
 254
 255   return;
 256 }
 257
 258 // Find loop's exit condition and associated induction variable.
 259 void LoopIndexSplit::findLoopConditionals() {
 260
 261   BasicBlock *ExitingBlock = NULL;
 262
 263   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 264        I != E; ++I) {
 265     BasicBlock *BB = *I;
 266     if (!L->isLoopExit(BB))
 267       continue;
 268     if (ExitingBlock)
 269       return;
 270     ExitingBlock = BB;
 271   }
 272
 273   if (!ExitingBlock)
 274     return;
 275
 276   // If exiting block is neither loop header nor loop latch then this loop is
 277   // not suitable.
 278   if (ExitingBlock != L->getHeader() && ExitingBlock != L->getLoopLatch())
 279     return;
 280
 281   // If exit block's terminator is conditional branch inst then we have found
 282   // exit condition.
 283   BranchInst *BR = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
 284   if (!BR || BR->isUnconditional())
 285     return;
 286
 287   ICmpInst *CI = dyn_cast<ICmpInst>(BR->getCondition());
 288   if (!CI)
 289     return;
 290
 291   ExitCondition = CI;
 292
 293   // Exit condition's one operand is loop invariant exit value and second
 294   // operand is SCEVAddRecExpr based on induction variable.
 295   Value *V0 = CI->getOperand(0);
 296   Value *V1 = CI->getOperand(1);
 297
 298   SCEVHandle SH0 = SE->getSCEV(V0);
 299   SCEVHandle SH1 = SE->getSCEV(V1);
 300
 301   if (SH0->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH1)) {
 302     ExitValueNum = 0;
 303     findIndVar(V1, L);
 304   }
 305   else if (SH1->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH0)) {
 306     ExitValueNum =  1;
 307     findIndVar(V0, L);
 308   }
 309
 310   if (!IndVar)
 311     ExitCondition = NULL;
 312   else if (IndVar) {
 313     BasicBlock *Preheader = L->getLoopPreheader();
 314     StartValue = IndVar->getIncomingValueForBlock(Preheader);
 315   }
 316 }
 317
 318 /// Find condition inside a loop that is suitable candidate for index split.
 319 void LoopIndexSplit::findSplitCondition() {
 320
 321   SplitInfo SD;
 322   // Check all basic block's terminators.
 323
 324   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 325        I != E; ++I) {
 326     BasicBlock *BB = *I;
 327
 328     // If this basic block does not terminate in a conditional branch
 329     // then terminator is not a suitable split condition.
 330     BranchInst *BR = dyn_cast<BranchInst>(BB->getTerminator());
 331     if (!BR)
 332       continue;
 333
 334     if (BR->isUnconditional())
 335       continue;
 336
 337     ICmpInst *CI = dyn_cast<ICmpInst>(BR->getCondition());
 338     if (!CI || CI == ExitCondition)
 339       return;
 340
 341     // If one operand is loop invariant and second operand is SCEVAddRecExpr
 342     // based on induction variable then CI is a candidate split condition.
 343     Value *V0 = CI->getOperand(0);
 344     Value *V1 = CI->getOperand(1);
 345
 346     SCEVHandle SH0 = SE->getSCEV(V0);
 347     SCEVHandle SH1 = SE->getSCEV(V1);
 348
 349     if (SH0->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH1)) {
 350       SD.SplitValue = V0;
 351       SD.SplitCondition = CI;
 352       if (PHINode *PN = dyn_cast<PHINode>(V1)) {
 353         if (PN == IndVar)
 354           SplitData.push_back(SD);
 355       }
 356       else  if (Instruction *Insn = dyn_cast<Instruction>(V1)) {
 357         if (IndVarIncrement && IndVarIncrement == Insn)
 358           SplitData.push_back(SD);
 359       }
 360     }
 361     else if (SH1->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH0)) {
 362       SD.SplitValue =  V1;
 363       SD.SplitCondition = CI;
 364       if (PHINode *PN = dyn_cast<PHINode>(V0)) {
 365         if (PN == IndVar)
 366           SplitData.push_back(SD);
 367       }
 368       else  if (Instruction *Insn = dyn_cast<Instruction>(V0)) {
 369         if (IndVarIncrement && IndVarIncrement == Insn)
 370           SplitData.push_back(SD);
 371       }
 372     }
 373   }
 374 }
 375
 376 /// processOneIterationLoop - Current loop L contains compare instruction
 377 /// that compares induction variable, IndVar, against loop invariant. If
 378 /// entire (i.e. meaningful) loop body is dominated by this compare
 379 /// instruction then loop body is executed only once. In such case eliminate
 380 /// loop structure surrounding this loop body. For example,
 381 ///     for (int i = start; i < end; ++i) {
 382 ///         if ( i == somevalue) {
 383 ///           loop_body
 384 ///         }
 385 ///     }
 386 /// can be transformed into
 387 ///     if (somevalue >= start && somevalue < end) {
 388 ///        i = somevalue;
 389 ///        loop_body
 390 ///     }
 391 bool LoopIndexSplit::processOneIterationLoop(SplitInfo &SD) {
 392
 393   BasicBlock *Header = L->getHeader();
 394
 395   // First of all, check if SplitCondition dominates entire loop body
 396   // or not.
 397
 398   // If SplitCondition is not in loop header then this loop is not suitable
 399   // for this transformation.
 400   if (SD.SplitCondition->getParent() != Header)
 401     return false;
 402
 403   // If loop header includes loop variant instruction operands then
 404   // this loop may not be eliminated.
 405   if (!safeHeader(SD, Header))
 406     return false;
 407
 408   // If Exiting block includes loop variant instructions then this
 409   // loop may not be eliminated.
 410   if (!safeExitingBlock(SD, ExitCondition->getParent()))
 411     return false;
 412
 413   // Update CFG.
 414
 415   // Replace index variable with split value in loop body. Loop body is executed
 416   // only when index variable is equal to split value.
 417   IndVar->replaceAllUsesWith(SD.SplitValue);
 418
 419   // Remove Latch to Header edge.
 420   BasicBlock *Latch = L->getLoopLatch();
 421   BasicBlock *LatchSucc = NULL;
 422   BranchInst *BR = dyn_cast<BranchInst>(Latch->getTerminator());
 423   if (!BR)
 424     return false;
 425   Header->removePredecessor(Latch);
 426   for (succ_iterator SI = succ_begin(Latch), E = succ_end(Latch);
 427        SI != E; ++SI) {
 428     if (Header != *SI)
 429       LatchSucc = *SI;
 430   }
 431   BR->setUnconditionalDest(LatchSucc);
 432
 433   Instruction *Terminator = Header->getTerminator();
 434   Value *ExitValue = ExitCondition->getOperand(ExitValueNum);
 435
 436   // Replace split condition in header.
 437   // Transform
 438   //      SplitCondition : icmp eq i32 IndVar, SplitValue
 439   // into
 440   //      c1 = icmp uge i32 SplitValue, StartValue
 441   //      c2 = icmp ult i32 vSplitValue, ExitValue
 442   //      and i32 c1, c2
 443   bool SignedPredicate = ExitCondition->isSignedPredicate();
 444   Instruction *C1 = new ICmpInst(SignedPredicate ?
 445                                  ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE,
 446                                  SD.SplitValue, StartValue, "lisplit",
 447                                  Terminator);
 448   Instruction *C2 = new ICmpInst(SignedPredicate ?
 449                                  ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 450                                  SD.SplitValue, ExitValue, "lisplit",
 451                                  Terminator);
 452   Instruction *NSplitCond = BinaryOperator::createAnd(C1, C2, "lisplit",
 453                                                       Terminator);
 454   SD.SplitCondition->replaceAllUsesWith(NSplitCond);
 455   SD.SplitCondition->eraseFromParent();
 456
 457   // Now, clear latch block. Remove instructions that are responsible
 458   // to increment induction variable.
 459   Instruction *LTerminator = Latch->getTerminator();
 460   for (BasicBlock::iterator LB = Latch->begin(), LE = Latch->end();
 461        LB != LE; ) {
 462     Instruction *I = LB;
 463     ++LB;
 464     if (isa<PHINode>(I) || I == LTerminator)
 465       continue;
 466
 467     if (I == IndVarIncrement)
 468       I->replaceAllUsesWith(ExitValue);
 469     else
 470       I->replaceAllUsesWith(UndefValue::get(I->getType()));
 471     I->eraseFromParent();
 472   }
 473
 474   LPM->deleteLoopFromQueue(L);
 475
 476   // Update Dominator Info.
 477   // Only CFG change done is to remove Latch to Header edge. This
 478   // does not change dominator tree because Latch did not dominate
 479   // Header.
 480   if (DF) {
 481     DominanceFrontier::iterator HeaderDF = DF->find(Header);
 482     if (HeaderDF != DF->end())
 483       DF->removeFromFrontier(HeaderDF, Header);
 484
 485     DominanceFrontier::iterator LatchDF = DF->find(Latch);
 486     if (LatchDF != DF->end())
 487       DF->removeFromFrontier(LatchDF, Header);
 488   }
 489   return true;
 490 }
 491
 492 // If loop header includes loop variant instruction operands then
 493 // this loop can not be eliminated. This is used by processOneIterationLoop().
 494 bool LoopIndexSplit::safeHeader(SplitInfo &SD, BasicBlock *Header) {
 495
 496   Instruction *Terminator = Header->getTerminator();
 497   for(BasicBlock::iterator BI = Header->begin(), BE = Header->end();
 498       BI != BE; ++BI) {
 499     Instruction *I = BI;
 500
 501     // PHI Nodes are OK.
 502     if (isa<PHINode>(I))
 503       continue;
 504
 505     // SplitCondition itself is OK.
 506     if (I == SD.SplitCondition)
 507       continue;
 508
 509     // Induction variable is OK.
 510     if (I == IndVar)
 511       continue;
 512
 513     // Induction variable increment is OK.
 514     if (I == IndVarIncrement)
 515       continue;
 516
 517     // Terminator is also harmless.
 518     if (I == Terminator)
 519       continue;
 520
 521     // Otherwise we have a instruction that may not be safe.
 522     return false;
 523   }
 524
 525   return true;
 526 }
 527
 528 // If Exiting block includes loop variant instructions then this
 529 // loop may not be eliminated. This is used by processOneIterationLoop().
 530 bool LoopIndexSplit::safeExitingBlock(SplitInfo &SD,
 531                                        BasicBlock *ExitingBlock) {
 532
 533   for (BasicBlock::iterator BI = ExitingBlock->begin(),
 534          BE = ExitingBlock->end(); BI != BE; ++BI) {
 535     Instruction *I = BI;
 536
 537     // PHI Nodes are OK.
 538     if (isa<PHINode>(I))
 539       continue;
 540
 541     // Induction variable increment is OK.
 542     if (IndVarIncrement && IndVarIncrement == I)
 543       continue;
 544
 545     // Check if I is induction variable increment instruction.
 546     if (!IndVarIncrement && I->getOpcode() == Instruction::Add) {
 547
 548       Value *Op0 = I->getOperand(0);
 549       Value *Op1 = I->getOperand(1);
 550       PHINode *PN = NULL;
 551       ConstantInt *CI = NULL;
 552
 553       if ((PN = dyn_cast<PHINode>(Op0))) {
 554         if ((CI = dyn_cast<ConstantInt>(Op1)))
 555           IndVarIncrement = I;
 556       } else
 557         if ((PN = dyn_cast<PHINode>(Op1))) {
 558           if ((CI = dyn_cast<ConstantInt>(Op0)))
 559             IndVarIncrement = I;
 560       }
 561
 562       if (IndVarIncrement && PN == IndVar && CI->isOne())
 563         continue;
 564     }
 565
 566     // I is an Exit condition if next instruction is block terminator.
 567     // Exit condition is OK if it compares loop invariant exit value,
 568     // which is checked below.
 569     else if (ICmpInst *EC = dyn_cast<ICmpInst>(I)) {
 570       if (EC == ExitCondition)
 571         continue;
 572     }
 573
 574     if (I == ExitingBlock->getTerminator())
 575       continue;
 576
 577     // Otherwise we have instruction that may not be safe.
 578     return false;
 579   }
 580
 581   // We could not find any reason to consider ExitingBlock unsafe.
 582   return true;
 583 }
 584
 585 /// removeBlocks - Remove basic block DeadBB and all blocks dominated by DeadBB.
 586 /// This routine is used to remove split condition's dead branch, dominated by
 587 /// DeadBB. LiveBB dominates split conidition's other branch.
 588 void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP,
 589                                   BasicBlock *LiveBB) {
 590
 591   // First update DeadBB's dominance frontier.
 592   SmallVector<BasicBlock *, 8> FrontierBBs;
 593   DominanceFrontier::iterator DeadBBDF = DF->find(DeadBB);
 594   if (DeadBBDF != DF->end()) {
 595     SmallVector<BasicBlock *, 8> PredBlocks;
 596
 597     DominanceFrontier::DomSetType DeadBBSet = DeadBBDF->second;
 598     for (DominanceFrontier::DomSetType::iterator DeadBBSetI = DeadBBSet.begin(),
 599            DeadBBSetE = DeadBBSet.end(); DeadBBSetI != DeadBBSetE; ++DeadBBSetI) {
 600       BasicBlock *FrontierBB = *DeadBBSetI;
 601       FrontierBBs.push_back(FrontierBB);
 602
 603       // Rremove any PHI incoming edge from blocks dominated by DeadBB.
 604       PredBlocks.clear();
 605       for(pred_iterator PI = pred_begin(FrontierBB), PE = pred_end(FrontierBB);
 606           PI != PE; ++PI) {
 607         BasicBlock *P = *PI;
 608         if (P == DeadBB || DT->dominates(DeadBB, P))
 609           PredBlocks.push_back(P);
 610       }
 611
 612       for(BasicBlock::iterator FBI = FrontierBB->begin(), FBE = FrontierBB->end();
 613           FBI != FBE; ++FBI) {
 614         if (PHINode *PN = dyn_cast<PHINode>(FBI)) {
 615           for(SmallVector<BasicBlock *, 8>::iterator PI = PredBlocks.begin(),
 616                 PE = PredBlocks.end(); PI != PE; ++PI) {
 617             BasicBlock *P = *PI;
 618             PN->removeIncomingValue(P);
 619           }
 620         }
 621         else
 622           break;
 623       }
 624     }
 625   }
 626
 627   // Now remove DeadBB and all nodes dominated by DeadBB in df order.
 628   SmallVector<BasicBlock *, 32> WorkList;
 629   DomTreeNode *DN = DT->getNode(DeadBB);
 630   for (df_iterator<DomTreeNode*> DI = df_begin(DN),
 631          E = df_end(DN); DI != E; ++DI) {
 632     BasicBlock *BB = DI->getBlock();
 633     WorkList.push_back(BB);
 634     BB->replaceAllUsesWith(UndefValue::get(Type::LabelTy));
 635   }
 636
 637   while (!WorkList.empty()) {
 638     BasicBlock *BB = WorkList.back(); WorkList.pop_back();
 639     for(BasicBlock::iterator BBI = BB->begin(), BBE = BB->end();
 640         BBI != BBE; ++BBI) {
 641       Instruction *I = BBI;
 642       I->replaceAllUsesWith(UndefValue::get(I->getType()));
 643       I->eraseFromParent();
 644     }
 645     LPM->deleteSimpleAnalysisValue(BB, LP);
 646     DT->eraseNode(BB);
 647     DF->removeBlock(BB);
 648     LI->removeBlock(BB);
 649     BB->eraseFromParent();
 650   }
 651
 652   // Update Frontier BBs' dominator info.
 653   while (!FrontierBBs.empty()) {
 654     BasicBlock *FBB = FrontierBBs.back(); FrontierBBs.pop_back();
 655     BasicBlock *NewDominator = FBB->getSinglePredecessor();
 656     if (!NewDominator) {
 657       pred_iterator PI = pred_begin(FBB), PE = pred_end(FBB);
 658       NewDominator = *PI;
 659       ++PI;
 660       if (NewDominator != LiveBB) {
 661         for(; PI != PE; ++PI) {
 662           BasicBlock *P = *PI;
 663           if (P == LiveBB) {
 664             NewDominator = LiveBB;
 665             break;
 666           }
 667           NewDominator = DT->findNearestCommonDominator(NewDominator, P);
 668         }
 669       }
 670     }
 671     assert (NewDominator && "Unable to fix dominator info.");
 672     DT->changeImmediateDominator(FBB, NewDominator);
 673     DF->changeImmediateDominator(FBB, NewDominator, DT);
 674   }
 675
 676 }
 677
 678 /// safeSplitCondition - Return true if it is possible to
 679 /// split loop using given split condition.
 680 bool LoopIndexSplit::safeSplitCondition(SplitInfo &SD) {
 681
 682   BasicBlock *SplitCondBlock = SD.SplitCondition->getParent();
 683
 684   // Unable to handle triange loops at the moment.
 685   // In triangle loop, split condition is in header and one of the
 686   // the split destination is loop latch. If split condition is EQ
 687   // then such loops are already handle in processOneIterationLoop().
 688   BasicBlock *Latch = L->getLoopLatch();
 689   BranchInst *SplitTerminator =
 690     cast<BranchInst>(SplitCondBlock->getTerminator());
 691   BasicBlock *Succ0 = SplitTerminator->getSuccessor(0);
 692   BasicBlock *Succ1 = SplitTerminator->getSuccessor(1);
 693   if (L->getHeader() == SplitCondBlock
 694       && (Latch == Succ0 || Latch == Succ1))
 695     return false;
 696
 697   // If one of the split condition branch is post dominating other then loop
 698   // index split is not appropriate.
 699   if (DT->dominates(Succ0, Latch) || DT->dominates(Succ1, Latch))
 700     return false;
 701
 702   // If one of the split condition branch is a predecessor of the other
 703   // split condition branch head then do not split loop on this condition.
 704   for(pred_iterator PI = pred_begin(Succ0), PE = pred_end(Succ0);
 705       PI != PE; ++PI)
 706     if (Succ1 == *PI)
 707       return false;
 708   for(pred_iterator PI = pred_begin(Succ1), PE = pred_end(Succ1);
 709       PI != PE; ++PI)
 710     if (Succ0 == *PI)
 711       return false;
 712
 713   // Finally this split condition is safe only if merge point for
 714   // split condition branch is loop latch. This check along with previous
 715   // check, to ensure that exit condition is in either loop latch or header,
 716   // filters all loops with non-empty loop body between merge point
 717   // and exit condition.
 718   DominanceFrontier::iterator Succ0DF = DF->find(Succ0);
 719   assert (Succ0DF != DF->end() && "Unable to find Succ0 dominance frontier");
 720   if (Succ0DF->second.count(Latch))
 721     return true;
 722
 723   DominanceFrontier::iterator Succ1DF = DF->find(Succ1);
 724   assert (Succ1DF != DF->end() && "Unable to find Succ1 dominance frontier");
 725   if (Succ1DF->second.count(Latch))
 726     return true;
 727
 728   return false;
 729 }
 730
 731 /// splitLoop - Split current loop L in two loops using split information
 732 /// SD. Update dominator information. Maintain LCSSA form.
 733 bool LoopIndexSplit::splitLoop(SplitInfo &SD) {
 734
 735   if (!safeSplitCondition(SD))
 736     return false;
 737
 738   // After loop is cloned there are two loops.
 739   //
 740   // First loop, referred as ALoop, executes first part of loop's iteration
 741   // space split.  Second loop, referred as BLoop, executes remaining
 742   // part of loop's iteration space.
 743   //
 744   // ALoop's exit edge enters BLoop's header through a forwarding block which
 745   // acts as a BLoop's preheader.
 746
 747   //[*] Calculate ALoop induction variable's new exiting value and
 748   //    BLoop induction variable's new starting value. Calculuate these
 749   //    values in original loop's preheader.
 750   //      A_ExitValue = min(SplitValue, OrignalLoopExitValue)
 751   //      B_StartValue = max(SplitValue, OriginalLoopStartValue)
 752   Value *A_ExitValue = NULL;
 753   Value *B_StartValue = NULL;
 754   if (isa<ConstantInt>(SD.SplitValue)) {
 755     A_ExitValue = SD.SplitValue;
 756     B_StartValue = SD.SplitValue;
 757   }
 758   else {
 759     BasicBlock *Preheader = L->getLoopPreheader();
 760     Instruction *PHTerminator = Preheader->getTerminator();
 761     bool SignedPredicate = ExitCondition->isSignedPredicate();
 762     Value *C1 = new ICmpInst(SignedPredicate ?
 763                             ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 764                             SD.SplitValue,
 765                              ExitCondition->getOperand(ExitValueNum),
 766                              "lsplit.ev", PHTerminator);
 767     A_ExitValue = new SelectInst(C1, SD.SplitValue,
 768                                  ExitCondition->getOperand(ExitValueNum),
 769                                  "lsplit.ev", PHTerminator);
 770
 771     Value *C2 = new ICmpInst(SignedPredicate ?
 772                              ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 773                              SD.SplitValue, StartValue, "lsplit.sv",
 774                              PHTerminator);
 775     B_StartValue = new SelectInst(C2, StartValue, SD.SplitValue,
 776                                    "lsplit.sv", PHTerminator);
 777   }
 778
 779   //[*] Clone loop.
 780   DenseMap<const Value *, Value *> ValueMap;
 781   Loop *BLoop = CloneLoop(L, LPM, LI, ValueMap, this);
 782   BasicBlock *B_Header = BLoop->getHeader();
 783
 784   //[*] ALoop's exiting edge BLoop's header.
 785   //    ALoop's original exit block becomes BLoop's exit block.
 786   PHINode *B_IndVar = cast<PHINode>(ValueMap[IndVar]);
 787   BasicBlock *A_ExitingBlock = ExitCondition->getParent();
 788   BranchInst *A_ExitInsn =
 789     dyn_cast<BranchInst>(A_ExitingBlock->getTerminator());
 790   assert (A_ExitInsn && "Unable to find suitable loop exit branch");
 791   BasicBlock *B_ExitBlock = A_ExitInsn->getSuccessor(1);
 792   if (L->contains(B_ExitBlock)) {
 793     B_ExitBlock = A_ExitInsn->getSuccessor(0);
 794     A_ExitInsn->setSuccessor(0, B_Header);
 795   } else
 796     A_ExitInsn->setSuccessor(1, B_Header);
 797
 798   //[*] Update ALoop's exit value using new exit value.
 799   ExitCondition->setOperand(ExitValueNum, A_ExitValue);
 800
 801   // [*] Update BLoop's header phi nodes. Remove incoming PHINode's from
 802   //     original loop's preheader. Add incoming PHINode values from
 803   //     ALoop's exiting block. Update BLoop header's domiantor info.
 804
 805   // Collect inverse map of Header PHINodes.
 806   DenseMap<Value *, Value *> InverseMap;
 807   for (BasicBlock::iterator BI = L->getHeader()->begin(),
 808          BE = L->getHeader()->end(); BI != BE; ++BI) {
 809     if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 810       PHINode *PNClone = cast<PHINode>(ValueMap[PN]);
 811       InverseMap[PNClone] = PN;
 812     } else
 813       break;
 814   }
 815   BasicBlock *Preheader = L->getLoopPreheader();
 816   for (BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end();
 817        BI != BE; ++BI) {
 818     if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 819       // Remove incoming value from original preheader.
 820       PN->removeIncomingValue(Preheader);
 821
 822       // Add incoming value from A_ExitingBlock.
 823       if (PN == B_IndVar)
 824         PN->addIncoming(B_StartValue, A_ExitingBlock);
 825       else {
 826         PHINode *OrigPN = cast<PHINode>(InverseMap[PN]);
 827         Value *V2 = OrigPN->getIncomingValueForBlock(A_ExitingBlock);
 828         PN->addIncoming(V2, A_ExitingBlock);
 829       }
 830     } else
 831       break;
 832   }
 833   DT->changeImmediateDominator(B_Header, A_ExitingBlock);
 834   DF->changeImmediateDominator(B_Header, A_ExitingBlock, DT);
 835
 836   // [*] Update BLoop's exit block. Its new predecessor is BLoop's exit
 837   //     block. Remove incoming PHINode values from ALoop's exiting block.
 838   //     Add new incoming values from BLoop's incoming exiting value.
 839   //     Update BLoop exit block's dominator info..
 840   BasicBlock *B_ExitingBlock = cast<BasicBlock>(ValueMap[A_ExitingBlock]);
 841   for (BasicBlock::iterator BI = B_ExitBlock->begin(), BE = B_ExitBlock->end();
 842        BI != BE; ++BI) {
 843     if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 844       PN->addIncoming(ValueMap[PN->getIncomingValueForBlock(A_ExitingBlock)],
 845                                                             B_ExitingBlock);
 846       PN->removeIncomingValue(A_ExitingBlock);
 847     } else
 848       break;
 849   }
 850
 851   DT->changeImmediateDominator(B_ExitBlock, B_ExitingBlock);
 852   DF->changeImmediateDominator(B_ExitBlock, B_ExitingBlock, DT);
 853
 854   //[*] Split ALoop's exit edge. This creates a new block which
 855   //    serves two purposes. First one is to hold PHINode defnitions
 856   //    to ensure that ALoop's LCSSA form. Second use it to act
 857   //    as a preheader for BLoop.
 858   BasicBlock *A_ExitBlock = SplitEdge(A_ExitingBlock, B_Header, this);
 859
 860   //[*] Preserve ALoop's LCSSA form. Create new forwarding PHINodes
 861   //    in A_ExitBlock to redefine outgoing PHI definitions from ALoop.
 862   for(BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end();
 863       BI != BE; ++BI) {
 864     if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 865       Value *V1 = PN->getIncomingValueForBlock(A_ExitBlock);
 866       PHINode *newPHI = new PHINode(PN->getType(), PN->getName());
 867       newPHI->addIncoming(V1, A_ExitingBlock);
 868       A_ExitBlock->getInstList().push_front(newPHI);
 869       PN->removeIncomingValue(A_ExitBlock);
 870       PN->addIncoming(newPHI, A_ExitBlock);
 871     } else
 872       break;
 873   }
 874
 875   //[*] Eliminate split condition's inactive branch from ALoop.
 876   BasicBlock *A_SplitCondBlock = SD.SplitCondition->getParent();
 877   BranchInst *A_BR = cast<BranchInst>(A_SplitCondBlock->getTerminator());
 878   BasicBlock *A_InactiveBranch = A_BR->getSuccessor(1);
 879   BasicBlock *A_ActiveBranch = A_BR->getSuccessor(0);
 880   A_BR->setUnconditionalDest(A_BR->getSuccessor(0));
 881   removeBlocks(A_InactiveBranch, L, A_ActiveBranch);
 882
 883   //[*] Eliminate split condition's inactive branch in from BLoop.
 884   BasicBlock *B_SplitCondBlock = cast<BasicBlock>(ValueMap[A_SplitCondBlock]);
 885   BranchInst *B_BR = cast<BranchInst>(B_SplitCondBlock->getTerminator());
 886   BasicBlock *B_InactiveBranch = B_BR->getSuccessor(0);
 887   BasicBlock *B_ActiveBranch = B_BR->getSuccessor(1);
 888   B_BR->setUnconditionalDest(B_BR->getSuccessor(1));
 889   removeBlocks(B_InactiveBranch, BLoop, B_ActiveBranch);
 890
 891   return true;
 892 }