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 (CI->getPredicate() == ICmpInst::ICMP_NE)
 342       return;
 343
 344     // If one operand is loop invariant and second operand is SCEVAddRecExpr
 345     // based on induction variable then CI is a candidate split condition.
 346     Value *V0 = CI->getOperand(0);
 347     Value *V1 = CI->getOperand(1);
 348
 349     SCEVHandle SH0 = SE->getSCEV(V0);
 350     SCEVHandle SH1 = SE->getSCEV(V1);
 351
 352     if (SH0->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH1)) {
 353       SD.SplitValue = V0;
 354       SD.SplitCondition = CI;
 355       if (PHINode *PN = dyn_cast<PHINode>(V1)) {
 356         if (PN == IndVar)
 357           SplitData.push_back(SD);
 358       }
 359       else  if (Instruction *Insn = dyn_cast<Instruction>(V1)) {
 360         if (IndVarIncrement && IndVarIncrement == Insn)
 361           SplitData.push_back(SD);
 362       }
 363     }
 364     else if (SH1->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH0)) {
 365       SD.SplitValue =  V1;
 366       SD.SplitCondition = CI;
 367       if (PHINode *PN = dyn_cast<PHINode>(V0)) {
 368         if (PN == IndVar)
 369           SplitData.push_back(SD);
 370       }
 371       else  if (Instruction *Insn = dyn_cast<Instruction>(V0)) {
 372         if (IndVarIncrement && IndVarIncrement == Insn)
 373           SplitData.push_back(SD);
 374       }
 375     }
 376   }
 377 }
 378
 379 /// processOneIterationLoop - Current loop L contains compare instruction
 380 /// that compares induction variable, IndVar, against loop invariant. If
 381 /// entire (i.e. meaningful) loop body is dominated by this compare
 382 /// instruction then loop body is executed only once. In such case eliminate
 383 /// loop structure surrounding this loop body. For example,
 384 ///     for (int i = start; i < end; ++i) {
 385 ///         if ( i == somevalue) {
 386 ///           loop_body
 387 ///         }
 388 ///     }
 389 /// can be transformed into
 390 ///     if (somevalue >= start && somevalue < end) {
 391 ///        i = somevalue;
 392 ///        loop_body
 393 ///     }
 394 bool LoopIndexSplit::processOneIterationLoop(SplitInfo &SD) {
 395
 396   BasicBlock *Header = L->getHeader();
 397
 398   // First of all, check if SplitCondition dominates entire loop body
 399   // or not.
 400
 401   // If SplitCondition is not in loop header then this loop is not suitable
 402   // for this transformation.
 403   if (SD.SplitCondition->getParent() != Header)
 404     return false;
 405
 406   // If loop header includes loop variant instruction operands then
 407   // this loop may not be eliminated.
 408   if (!safeHeader(SD, Header))
 409     return false;
 410
 411   // If Exiting block includes loop variant instructions then this
 412   // loop may not be eliminated.
 413   if (!safeExitingBlock(SD, ExitCondition->getParent()))
 414     return false;
 415
 416   // Update CFG.
 417
 418   // Replace index variable with split value in loop body. Loop body is executed
 419   // only when index variable is equal to split value.
 420   IndVar->replaceAllUsesWith(SD.SplitValue);
 421
 422   // Remove Latch to Header edge.
 423   BasicBlock *Latch = L->getLoopLatch();
 424   BasicBlock *LatchSucc = NULL;
 425   BranchInst *BR = dyn_cast<BranchInst>(Latch->getTerminator());
 426   if (!BR)
 427     return false;
 428   Header->removePredecessor(Latch);
 429   for (succ_iterator SI = succ_begin(Latch), E = succ_end(Latch);
 430        SI != E; ++SI) {
 431     if (Header != *SI)
 432       LatchSucc = *SI;
 433   }
 434   BR->setUnconditionalDest(LatchSucc);
 435
 436   Instruction *Terminator = Header->getTerminator();
 437   Value *ExitValue = ExitCondition->getOperand(ExitValueNum);
 438
 439   // Replace split condition in header.
 440   // Transform
 441   //      SplitCondition : icmp eq i32 IndVar, SplitValue
 442   // into
 443   //      c1 = icmp uge i32 SplitValue, StartValue
 444   //      c2 = icmp ult i32 vSplitValue, ExitValue
 445   //      and i32 c1, c2
 446   bool SignedPredicate = ExitCondition->isSignedPredicate();
 447   Instruction *C1 = new ICmpInst(SignedPredicate ?
 448                                  ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE,
 449                                  SD.SplitValue, StartValue, "lisplit",
 450                                  Terminator);
 451   Instruction *C2 = new ICmpInst(SignedPredicate ?
 452                                  ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 453                                  SD.SplitValue, ExitValue, "lisplit",
 454                                  Terminator);
 455   Instruction *NSplitCond = BinaryOperator::createAnd(C1, C2, "lisplit",
 456                                                       Terminator);
 457   SD.SplitCondition->replaceAllUsesWith(NSplitCond);
 458   SD.SplitCondition->eraseFromParent();
 459
 460   // Now, clear latch block. Remove instructions that are responsible
 461   // to increment induction variable.
 462   Instruction *LTerminator = Latch->getTerminator();
 463   for (BasicBlock::iterator LB = Latch->begin(), LE = Latch->end();
 464        LB != LE; ) {
 465     Instruction *I = LB;
 466     ++LB;
 467     if (isa<PHINode>(I) || I == LTerminator)
 468       continue;
 469
 470     if (I == IndVarIncrement)
 471       I->replaceAllUsesWith(ExitValue);
 472     else
 473       I->replaceAllUsesWith(UndefValue::get(I->getType()));
 474     I->eraseFromParent();
 475   }
 476
 477   LPM->deleteLoopFromQueue(L);
 478
 479   // Update Dominator Info.
 480   // Only CFG change done is to remove Latch to Header edge. This
 481   // does not change dominator tree because Latch did not dominate
 482   // Header.
 483   if (DF) {
 484     DominanceFrontier::iterator HeaderDF = DF->find(Header);
 485     if (HeaderDF != DF->end())
 486       DF->removeFromFrontier(HeaderDF, Header);
 487
 488     DominanceFrontier::iterator LatchDF = DF->find(Latch);
 489     if (LatchDF != DF->end())
 490       DF->removeFromFrontier(LatchDF, Header);
 491   }
 492   return true;
 493 }
 494
 495 // If loop header includes loop variant instruction operands then
 496 // this loop can not be eliminated. This is used by processOneIterationLoop().
 497 bool LoopIndexSplit::safeHeader(SplitInfo &SD, BasicBlock *Header) {
 498
 499   Instruction *Terminator = Header->getTerminator();
 500   for(BasicBlock::iterator BI = Header->begin(), BE = Header->end();
 501       BI != BE; ++BI) {
 502     Instruction *I = BI;
 503
 504     // PHI Nodes are OK.
 505     if (isa<PHINode>(I))
 506       continue;
 507
 508     // SplitCondition itself is OK.
 509     if (I == SD.SplitCondition)
 510       continue;
 511
 512     // Induction variable is OK.
 513     if (I == IndVar)
 514       continue;
 515
 516     // Induction variable increment is OK.
 517     if (I == IndVarIncrement)
 518       continue;
 519
 520     // Terminator is also harmless.
 521     if (I == Terminator)
 522       continue;
 523
 524     // Otherwise we have a instruction that may not be safe.
 525     return false;
 526   }
 527
 528   return true;
 529 }
 530
 531 // If Exiting block includes loop variant instructions then this
 532 // loop may not be eliminated. This is used by processOneIterationLoop().
 533 bool LoopIndexSplit::safeExitingBlock(SplitInfo &SD,
 534                                        BasicBlock *ExitingBlock) {
 535
 536   for (BasicBlock::iterator BI = ExitingBlock->begin(),
 537          BE = ExitingBlock->end(); BI != BE; ++BI) {
 538     Instruction *I = BI;
 539
 540     // PHI Nodes are OK.
 541     if (isa<PHINode>(I))
 542       continue;
 543
 544     // Induction variable increment is OK.
 545     if (IndVarIncrement && IndVarIncrement == I)
 546       continue;
 547
 548     // Check if I is induction variable increment instruction.
 549     if (!IndVarIncrement && I->getOpcode() == Instruction::Add) {
 550
 551       Value *Op0 = I->getOperand(0);
 552       Value *Op1 = I->getOperand(1);
 553       PHINode *PN = NULL;
 554       ConstantInt *CI = NULL;
 555
 556       if ((PN = dyn_cast<PHINode>(Op0))) {
 557         if ((CI = dyn_cast<ConstantInt>(Op1)))
 558           IndVarIncrement = I;
 559       } else
 560         if ((PN = dyn_cast<PHINode>(Op1))) {
 561           if ((CI = dyn_cast<ConstantInt>(Op0)))
 562             IndVarIncrement = I;
 563       }
 564
 565       if (IndVarIncrement && PN == IndVar && CI->isOne())
 566         continue;
 567     }
 568
 569     // I is an Exit condition if next instruction is block terminator.
 570     // Exit condition is OK if it compares loop invariant exit value,
 571     // which is checked below.
 572     else if (ICmpInst *EC = dyn_cast<ICmpInst>(I)) {
 573       if (EC == ExitCondition)
 574         continue;
 575     }
 576
 577     if (I == ExitingBlock->getTerminator())
 578       continue;
 579
 580     // Otherwise we have instruction that may not be safe.
 581     return false;
 582   }
 583
 584   // We could not find any reason to consider ExitingBlock unsafe.
 585   return true;
 586 }
 587
 588 /// removeBlocks - Remove basic block DeadBB and all blocks dominated by DeadBB.
 589 /// This routine is used to remove split condition's dead branch, dominated by
 590 /// DeadBB. LiveBB dominates split conidition's other branch.
 591 void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP,
 592                                   BasicBlock *LiveBB) {
 593
 594   // First update DeadBB's dominance frontier.
 595   SmallVector<BasicBlock *, 8> FrontierBBs;
 596   DominanceFrontier::iterator DeadBBDF = DF->find(DeadBB);
 597   if (DeadBBDF != DF->end()) {
 598     SmallVector<BasicBlock *, 8> PredBlocks;
 599
 600     DominanceFrontier::DomSetType DeadBBSet = DeadBBDF->second;
 601     for (DominanceFrontier::DomSetType::iterator DeadBBSetI = DeadBBSet.begin(),
 602            DeadBBSetE = DeadBBSet.end(); DeadBBSetI != DeadBBSetE; ++DeadBBSetI) {
 603       BasicBlock *FrontierBB = *DeadBBSetI;
 604       FrontierBBs.push_back(FrontierBB);
 605
 606       // Rremove any PHI incoming edge from blocks dominated by DeadBB.
 607       PredBlocks.clear();
 608       for(pred_iterator PI = pred_begin(FrontierBB), PE = pred_end(FrontierBB);
 609           PI != PE; ++PI) {
 610         BasicBlock *P = *PI;
 611         if (P == DeadBB || DT->dominates(DeadBB, P))
 612           PredBlocks.push_back(P);
 613       }
 614
 615       for(BasicBlock::iterator FBI = FrontierBB->begin(), FBE = FrontierBB->end();
 616           FBI != FBE; ++FBI) {
 617         if (PHINode *PN = dyn_cast<PHINode>(FBI)) {
 618           for(SmallVector<BasicBlock *, 8>::iterator PI = PredBlocks.begin(),
 619                 PE = PredBlocks.end(); PI != PE; ++PI) {
 620             BasicBlock *P = *PI;
 621             PN->removeIncomingValue(P);
 622           }
 623         }
 624         else
 625           break;
 626       }
 627     }
 628   }
 629
 630   // Now remove DeadBB and all nodes dominated by DeadBB in df order.
 631   SmallVector<BasicBlock *, 32> WorkList;
 632   DomTreeNode *DN = DT->getNode(DeadBB);
 633   for (df_iterator<DomTreeNode*> DI = df_begin(DN),
 634          E = df_end(DN); DI != E; ++DI) {
 635     BasicBlock *BB = DI->getBlock();
 636     WorkList.push_back(BB);
 637     BB->replaceAllUsesWith(UndefValue::get(Type::LabelTy));
 638   }
 639
 640   while (!WorkList.empty()) {
 641     BasicBlock *BB = WorkList.back(); WorkList.pop_back();
 642     for(BasicBlock::iterator BBI = BB->begin(), BBE = BB->end();
 643         BBI != BBE; ++BBI) {
 644       Instruction *I = BBI;
 645       I->replaceAllUsesWith(UndefValue::get(I->getType()));
 646       I->eraseFromParent();
 647     }
 648     LPM->deleteSimpleAnalysisValue(BB, LP);
 649     DT->eraseNode(BB);
 650     DF->removeBlock(BB);
 651     LI->removeBlock(BB);
 652     BB->eraseFromParent();
 653   }
 654
 655   // Update Frontier BBs' dominator info.
 656   while (!FrontierBBs.empty()) {
 657     BasicBlock *FBB = FrontierBBs.back(); FrontierBBs.pop_back();
 658     BasicBlock *NewDominator = FBB->getSinglePredecessor();
 659     if (!NewDominator) {
 660       pred_iterator PI = pred_begin(FBB), PE = pred_end(FBB);
 661       NewDominator = *PI;
 662       ++PI;
 663       if (NewDominator != LiveBB) {
 664         for(; PI != PE; ++PI) {
 665           BasicBlock *P = *PI;
 666           if (P == LiveBB) {
 667             NewDominator = LiveBB;
 668             break;
 669           }
 670           NewDominator = DT->findNearestCommonDominator(NewDominator, P);
 671         }
 672       }
 673     }
 674     assert (NewDominator && "Unable to fix dominator info.");
 675     DT->changeImmediateDominator(FBB, NewDominator);
 676     DF->changeImmediateDominator(FBB, NewDominator, DT);
 677   }
 678
 679 }
 680
 681 /// safeSplitCondition - Return true if it is possible to
 682 /// split loop using given split condition.
 683 bool LoopIndexSplit::safeSplitCondition(SplitInfo &SD) {
 684
 685   BasicBlock *SplitCondBlock = SD.SplitCondition->getParent();
 686
 687   // Unable to handle triange loops at the moment.
 688   // In triangle loop, split condition is in header and one of the
 689   // the split destination is loop latch. If split condition is EQ
 690   // then such loops are already handle in processOneIterationLoop().
 691   BasicBlock *Latch = L->getLoopLatch();
 692   BranchInst *SplitTerminator =
 693     cast<BranchInst>(SplitCondBlock->getTerminator());
 694   BasicBlock *Succ0 = SplitTerminator->getSuccessor(0);
 695   BasicBlock *Succ1 = SplitTerminator->getSuccessor(1);
 696   if (L->getHeader() == SplitCondBlock
 697       && (Latch == Succ0 || Latch == Succ1))
 698     return false;
 699
 700   // If one of the split condition branch is post dominating other then loop
 701   // index split is not appropriate.
 702   if (DT->dominates(Succ0, Latch) || DT->dominates(Succ1, Latch))
 703     return false;
 704
 705   // If one of the split condition branch is a predecessor of the other
 706   // split condition branch head then do not split loop on this condition.
 707   for(pred_iterator PI = pred_begin(Succ0), PE = pred_end(Succ0);
 708       PI != PE; ++PI)
 709     if (Succ1 == *PI)
 710       return false;
 711   for(pred_iterator PI = pred_begin(Succ1), PE = pred_end(Succ1);
 712       PI != PE; ++PI)
 713     if (Succ0 == *PI)
 714       return false;
 715
 716   // Finally this split condition is safe only if merge point for
 717   // split condition branch is loop latch. This check along with previous
 718   // check, to ensure that exit condition is in either loop latch or header,
 719   // filters all loops with non-empty loop body between merge point
 720   // and exit condition.
 721   DominanceFrontier::iterator Succ0DF = DF->find(Succ0);
 722   assert (Succ0DF != DF->end() && "Unable to find Succ0 dominance frontier");
 723   if (Succ0DF->second.count(Latch))
 724     return true;
 725
 726   DominanceFrontier::iterator Succ1DF = DF->find(Succ1);
 727   assert (Succ1DF != DF->end() && "Unable to find Succ1 dominance frontier");
 728   if (Succ1DF->second.count(Latch))
 729     return true;
 730
 731   return false;
 732 }
 733
 734 /// splitLoop - Split current loop L in two loops using split information
 735 /// SD. Update dominator information. Maintain LCSSA form.
 736 bool LoopIndexSplit::splitLoop(SplitInfo &SD) {
 737
 738   if (!safeSplitCondition(SD))
 739     return false;
 740
 741   // After loop is cloned there are two loops.
 742   //
 743   // First loop, referred as ALoop, executes first part of loop's iteration
 744   // space split.  Second loop, referred as BLoop, executes remaining
 745   // part of loop's iteration space.
 746   //
 747   // ALoop's exit edge enters BLoop's header through a forwarding block which
 748   // acts as a BLoop's preheader.
 749
 750   //[*] Calculate ALoop induction variable's new exiting value and
 751   //    BLoop induction variable's new starting value. Calculuate these
 752   //    values in original loop's preheader.
 753   //      A_ExitValue = min(SplitValue, OrignalLoopExitValue)
 754   //      B_StartValue = max(SplitValue, OriginalLoopStartValue)
 755   Value *A_ExitValue = NULL;
 756   Value *B_StartValue = NULL;
 757   if (isa<ConstantInt>(SD.SplitValue)) {
 758     A_ExitValue = SD.SplitValue;
 759     B_StartValue = SD.SplitValue;
 760   }
 761   else {
 762     BasicBlock *Preheader = L->getLoopPreheader();
 763     Instruction *PHTerminator = Preheader->getTerminator();
 764     bool SignedPredicate = ExitCondition->isSignedPredicate();
 765     Value *C1 = new ICmpInst(SignedPredicate ?
 766                             ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 767                             SD.SplitValue,
 768                              ExitCondition->getOperand(ExitValueNum),
 769                              "lsplit.ev", PHTerminator);
 770     A_ExitValue = new SelectInst(C1, SD.SplitValue,
 771                                  ExitCondition->getOperand(ExitValueNum),
 772                                  "lsplit.ev", PHTerminator);
 773
 774     Value *C2 = new ICmpInst(SignedPredicate ?
 775                              ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 776                              SD.SplitValue, StartValue, "lsplit.sv",
 777                              PHTerminator);
 778     B_StartValue = new SelectInst(C2, StartValue, SD.SplitValue,
 779                                    "lsplit.sv", PHTerminator);
 780   }
 781
 782   //[*] Clone loop.
 783   DenseMap<const Value *, Value *> ValueMap;
 784   Loop *BLoop = CloneLoop(L, LPM, LI, ValueMap, this);
 785   BasicBlock *B_Header = BLoop->getHeader();
 786
 787   //[*] ALoop's exiting edge BLoop's header.
 788   //    ALoop's original exit block becomes BLoop's exit block.
 789   PHINode *B_IndVar = cast<PHINode>(ValueMap[IndVar]);
 790   BasicBlock *A_ExitingBlock = ExitCondition->getParent();
 791   BranchInst *A_ExitInsn =
 792     dyn_cast<BranchInst>(A_ExitingBlock->getTerminator());
 793   assert (A_ExitInsn && "Unable to find suitable loop exit branch");
 794   BasicBlock *B_ExitBlock = A_ExitInsn->getSuccessor(1);
 795   if (L->contains(B_ExitBlock)) {
 796     B_ExitBlock = A_ExitInsn->getSuccessor(0);
 797     A_ExitInsn->setSuccessor(0, B_Header);
 798   } else
 799     A_ExitInsn->setSuccessor(1, B_Header);
 800
 801   //[*] Update ALoop's exit value using new exit value.
 802   ExitCondition->setOperand(ExitValueNum, A_ExitValue);
 803
 804   // [*] Update BLoop's header phi nodes. Remove incoming PHINode's from
 805   //     original loop's preheader. Add incoming PHINode values from
 806   //     ALoop's exiting block. Update BLoop header's domiantor info.
 807
 808   // Collect inverse map of Header PHINodes.
 809   DenseMap<Value *, Value *> InverseMap;
 810   for (BasicBlock::iterator BI = L->getHeader()->begin(),
 811          BE = L->getHeader()->end(); BI != BE; ++BI) {
 812     if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 813       PHINode *PNClone = cast<PHINode>(ValueMap[PN]);
 814       InverseMap[PNClone] = PN;
 815     } else
 816       break;
 817   }
 818   BasicBlock *Preheader = L->getLoopPreheader();
 819   for (BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end();
 820        BI != BE; ++BI) {
 821     if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 822       // Remove incoming value from original preheader.
 823       PN->removeIncomingValue(Preheader);
 824
 825       // Add incoming value from A_ExitingBlock.
 826       if (PN == B_IndVar)
 827         PN->addIncoming(B_StartValue, A_ExitingBlock);
 828       else {
 829         PHINode *OrigPN = cast<PHINode>(InverseMap[PN]);
 830         Value *V2 = OrigPN->getIncomingValueForBlock(A_ExitingBlock);
 831         PN->addIncoming(V2, A_ExitingBlock);
 832       }
 833     } else
 834       break;
 835   }
 836   DT->changeImmediateDominator(B_Header, A_ExitingBlock);
 837   DF->changeImmediateDominator(B_Header, A_ExitingBlock, DT);
 838
 839   // [*] Update BLoop's exit block. Its new predecessor is BLoop's exit
 840   //     block. Remove incoming PHINode values from ALoop's exiting block.
 841   //     Add new incoming values from BLoop's incoming exiting value.
 842   //     Update BLoop exit block's dominator info..
 843   BasicBlock *B_ExitingBlock = cast<BasicBlock>(ValueMap[A_ExitingBlock]);
 844   for (BasicBlock::iterator BI = B_ExitBlock->begin(), BE = B_ExitBlock->end();
 845        BI != BE; ++BI) {
 846     if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 847       PN->addIncoming(ValueMap[PN->getIncomingValueForBlock(A_ExitingBlock)],
 848                                                             B_ExitingBlock);
 849       PN->removeIncomingValue(A_ExitingBlock);
 850     } else
 851       break;
 852   }
 853
 854   DT->changeImmediateDominator(B_ExitBlock, B_ExitingBlock);
 855   DF->changeImmediateDominator(B_ExitBlock, B_ExitingBlock, DT);
 856
 857   //[*] Split ALoop's exit edge. This creates a new block which
 858   //    serves two purposes. First one is to hold PHINode defnitions
 859   //    to ensure that ALoop's LCSSA form. Second use it to act
 860   //    as a preheader for BLoop.
 861   BasicBlock *A_ExitBlock = SplitEdge(A_ExitingBlock, B_Header, this);
 862
 863   //[*] Preserve ALoop's LCSSA form. Create new forwarding PHINodes
 864   //    in A_ExitBlock to redefine outgoing PHI definitions from ALoop.
 865   for(BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end();
 866       BI != BE; ++BI) {
 867     if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 868       Value *V1 = PN->getIncomingValueForBlock(A_ExitBlock);
 869       PHINode *newPHI = new PHINode(PN->getType(), PN->getName());
 870       newPHI->addIncoming(V1, A_ExitingBlock);
 871       A_ExitBlock->getInstList().push_front(newPHI);
 872       PN->removeIncomingValue(A_ExitBlock);
 873       PN->addIncoming(newPHI, A_ExitBlock);
 874     } else
 875       break;
 876   }
 877
 878   //[*] Eliminate split condition's inactive branch from ALoop.
 879   BasicBlock *A_SplitCondBlock = SD.SplitCondition->getParent();
 880   BranchInst *A_BR = cast<BranchInst>(A_SplitCondBlock->getTerminator());
 881   BasicBlock *A_InactiveBranch = A_BR->getSuccessor(1);
 882   BasicBlock *A_ActiveBranch = A_BR->getSuccessor(0);
 883   A_BR->setUnconditionalDest(A_BR->getSuccessor(0));
 884   removeBlocks(A_InactiveBranch, L, A_ActiveBranch);
 885
 886   //[*] Eliminate split condition's inactive branch in from BLoop.
 887   BasicBlock *B_SplitCondBlock = cast<BasicBlock>(ValueMap[A_SplitCondBlock]);
 888   BranchInst *B_BR = cast<BranchInst>(B_SplitCondBlock->getTerminator());
 889   BasicBlock *B_InactiveBranch = B_BR->getSuccessor(0);
 890   BasicBlock *B_ActiveBranch = B_BR->getSuccessor(1);
 891   B_BR->setUnconditionalDest(B_BR->getSuccessor(1));
 892   removeBlocks(B_InactiveBranch, BLoop, B_ActiveBranch);
 893
 894   return true;
 895 }