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 BB and all blocks dominated by BB.
 101     void removeBlocks(BasicBlock *InBB);
 102
 103     /// Find cost of spliting loop L.
 104     unsigned findSplitCost(Loop *L, SplitInfo &SD);
 105     bool splitLoop(SplitInfo &SD);
 106
 107     void initialize() {
 108       IndVar = NULL;
 109       IndVarIncrement = NULL;
 110       ExitCondition = NULL;
 111       StartValue = NULL;
 112       ExitValueNum = 0;
 113       SplitData.clear();
 114     }
 115
 116   private:
 117
 118     // Current Loop.
 119     Loop *L;
 120     LPPassManager *LPM;
 121     LoopInfo *LI;
 122     ScalarEvolution *SE;
 123     DominatorTree *DT;
 124     SmallVector<SplitInfo, 4> SplitData;
 125
 126     // Induction variable whose range is being split by this transformation.
 127     PHINode *IndVar;
 128     Instruction *IndVarIncrement;
 129
 130     // Loop exit condition.
 131     ICmpInst *ExitCondition;
 132
 133     // Induction variable's initial value.
 134     Value *StartValue;
 135
 136     // Induction variable's final loop exit value operand number in exit condition..
 137     unsigned ExitValueNum;
 138   };
 139
 140   char LoopIndexSplit::ID = 0;
 141   RegisterPass<LoopIndexSplit> X ("loop-index-split", "Index Split Loops");
 142 }
 143
 144 LoopPass *llvm::createLoopIndexSplitPass() {
 145   return new LoopIndexSplit();
 146 }
 147
 148 // Index split Loop L. Return true if loop is split.
 149 bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) {
 150   bool Changed = false;
 151   L = IncomingLoop;
 152   LPM = &LPM_Ref;
 153
 154   SE = &getAnalysis<ScalarEvolution>();
 155   DT = &getAnalysis<DominatorTree>();
 156   LI = &getAnalysis<LoopInfo>();
 157
 158   initialize();
 159
 160   findLoopConditionals();
 161
 162   if (!ExitCondition)
 163     return false;
 164
 165   findSplitCondition();
 166
 167   if (SplitData.empty())
 168     return false;
 169
 170   // First see if it is possible to eliminate loop itself or not.
 171   for (SmallVector<SplitInfo, 4>::iterator SI = SplitData.begin(),
 172          E = SplitData.end(); SI != E; ++SI) {
 173     SplitInfo &SD = *SI;
 174     if (SD.SplitCondition->getPredicate() == ICmpInst::ICMP_EQ) {
 175       Changed = processOneIterationLoop(SD);
 176       if (Changed) {
 177         ++NumIndexSplit;
 178         // If is loop is eliminated then nothing else to do here.
 179         return Changed;
 180       }
 181     }
 182   }
 183
 184   unsigned MaxCost = 99;
 185   unsigned Index = 0;
 186   unsigned MostProfitableSDIndex = 0;
 187   for (SmallVector<SplitInfo, 4>::iterator SI = SplitData.begin(),
 188          E = SplitData.end(); SI != E; ++SI, ++Index) {
 189     SplitInfo SD = *SI;
 190
 191     // ICM_EQs are already handled above.
 192     if (SD.SplitCondition->getPredicate() == ICmpInst::ICMP_EQ)
 193       continue;
 194
 195     unsigned Cost = findSplitCost(L, SD);
 196     if (Cost < MaxCost)
 197       MostProfitableSDIndex = Index;
 198   }
 199
 200   // Split most profitiable condition.
 201   Changed = splitLoop(SplitData[MostProfitableSDIndex]);
 202
 203   if (Changed)
 204     ++NumIndexSplit;
 205
 206   return Changed;
 207 }
 208
 209 /// Return true if V is a induction variable or induction variable's
 210 /// increment for loop L.
 211 void LoopIndexSplit::findIndVar(Value *V, Loop *L) {
 212
 213   Instruction *I = dyn_cast<Instruction>(V);
 214   if (!I)
 215     return;
 216
 217   // Check if I is a phi node from loop header or not.
 218   if (PHINode *PN = dyn_cast<PHINode>(V)) {
 219     if (PN->getParent() == L->getHeader()) {
 220       IndVar = PN;
 221       return;
 222     }
 223   }
 224
 225   // Check if I is a add instruction whose one operand is
 226   // phi node from loop header and second operand is constant.
 227   if (I->getOpcode() != Instruction::Add)
 228     return;
 229
 230   Value *Op0 = I->getOperand(0);
 231   Value *Op1 = I->getOperand(1);
 232
 233   if (PHINode *PN = dyn_cast<PHINode>(Op0)) {
 234     if (PN->getParent() == L->getHeader()
 235         && isa<ConstantInt>(Op1)) {
 236       IndVar = PN;
 237       IndVarIncrement = I;
 238       return;
 239     }
 240   }
 241
 242   if (PHINode *PN = dyn_cast<PHINode>(Op1)) {
 243     if (PN->getParent() == L->getHeader()
 244         && isa<ConstantInt>(Op0)) {
 245       IndVar = PN;
 246       IndVarIncrement = I;
 247       return;
 248     }
 249   }
 250
 251   return;
 252 }
 253
 254 // Find loop's exit condition and associated induction variable.
 255 void LoopIndexSplit::findLoopConditionals() {
 256
 257   BasicBlock *ExitBlock = NULL;
 258
 259   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 260        I != E; ++I) {
 261     BasicBlock *BB = *I;
 262     if (!L->isLoopExit(BB))
 263       continue;
 264     if (ExitBlock)
 265       return;
 266     ExitBlock = BB;
 267   }
 268
 269   if (!ExitBlock)
 270     return;
 271
 272   // If exit block's terminator is conditional branch inst then we have found
 273   // exit condition.
 274   BranchInst *BR = dyn_cast<BranchInst>(ExitBlock->getTerminator());
 275   if (!BR || BR->isUnconditional())
 276     return;
 277
 278   ICmpInst *CI = dyn_cast<ICmpInst>(BR->getCondition());
 279   if (!CI)
 280     return;
 281
 282   ExitCondition = CI;
 283
 284   // Exit condition's one operand is loop invariant exit value and second
 285   // operand is SCEVAddRecExpr based on induction variable.
 286   Value *V0 = CI->getOperand(0);
 287   Value *V1 = CI->getOperand(1);
 288
 289   SCEVHandle SH0 = SE->getSCEV(V0);
 290   SCEVHandle SH1 = SE->getSCEV(V1);
 291
 292   if (SH0->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH1)) {
 293     ExitValueNum = 0;
 294     findIndVar(V1, L);
 295   }
 296   else if (SH1->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH0)) {
 297     ExitValueNum =  1;
 298     findIndVar(V0, L);
 299   }
 300
 301   if (!IndVar)
 302     ExitCondition = NULL;
 303   else if (IndVar) {
 304     BasicBlock *Preheader = L->getLoopPreheader();
 305     StartValue = IndVar->getIncomingValueForBlock(Preheader);
 306   }
 307 }
 308
 309 /// Find condition inside a loop that is suitable candidate for index split.
 310 void LoopIndexSplit::findSplitCondition() {
 311
 312   SplitInfo SD;
 313   // Check all basic block's terminators.
 314
 315   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 316        I != E; ++I) {
 317     BasicBlock *BB = *I;
 318
 319     // If this basic block does not terminate in a conditional branch
 320     // then terminator is not a suitable split condition.
 321     BranchInst *BR = dyn_cast<BranchInst>(BB->getTerminator());
 322     if (!BR)
 323       continue;
 324
 325     if (BR->isUnconditional())
 326       continue;
 327
 328     ICmpInst *CI = dyn_cast<ICmpInst>(BR->getCondition());
 329     if (!CI || CI == ExitCondition)
 330       return;
 331
 332     // If one operand is loop invariant and second operand is SCEVAddRecExpr
 333     // based on induction variable then CI is a candidate split condition.
 334     Value *V0 = CI->getOperand(0);
 335     Value *V1 = CI->getOperand(1);
 336
 337     SCEVHandle SH0 = SE->getSCEV(V0);
 338     SCEVHandle SH1 = SE->getSCEV(V1);
 339
 340     if (SH0->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH1)) {
 341       SD.SplitValue = V0;
 342       SD.SplitCondition = CI;
 343       if (PHINode *PN = dyn_cast<PHINode>(V1)) {
 344         if (PN == IndVar)
 345           SplitData.push_back(SD);
 346       }
 347       else  if (Instruction *Insn = dyn_cast<Instruction>(V1)) {
 348         if (IndVarIncrement && IndVarIncrement == Insn)
 349           SplitData.push_back(SD);
 350       }
 351     }
 352     else if (SH1->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH0)) {
 353       SD.SplitValue =  V1;
 354       SD.SplitCondition = CI;
 355       if (PHINode *PN = dyn_cast<PHINode>(V0)) {
 356         if (PN == IndVar)
 357           SplitData.push_back(SD);
 358       }
 359       else  if (Instruction *Insn = dyn_cast<Instruction>(V0)) {
 360         if (IndVarIncrement && IndVarIncrement == Insn)
 361           SplitData.push_back(SD);
 362       }
 363     }
 364   }
 365 }
 366
 367 /// processOneIterationLoop - Current loop L contains compare instruction
 368 /// that compares induction variable, IndVar, against loop invariant. If
 369 /// entire (i.e. meaningful) loop body is dominated by this compare
 370 /// instruction then loop body is executed only once. In such case eliminate
 371 /// loop structure surrounding this loop body. For example,
 372 ///     for (int i = start; i < end; ++i) {
 373 ///         if ( i == somevalue) {
 374 ///           loop_body
 375 ///         }
 376 ///     }
 377 /// can be transformed into
 378 ///     if (somevalue >= start && somevalue < end) {
 379 ///        i = somevalue;
 380 ///        loop_body
 381 ///     }
 382 bool LoopIndexSplit::processOneIterationLoop(SplitInfo &SD) {
 383
 384   BasicBlock *Header = L->getHeader();
 385
 386   // First of all, check if SplitCondition dominates entire loop body
 387   // or not.
 388
 389   // If SplitCondition is not in loop header then this loop is not suitable
 390   // for this transformation.
 391   if (SD.SplitCondition->getParent() != Header)
 392     return false;
 393
 394   // If loop header includes loop variant instruction operands then
 395   // this loop may not be eliminated.
 396   if (!safeHeader(SD, Header))
 397     return false;
 398
 399   // If Exit block includes loop variant instructions then this
 400   // loop may not be eliminated.
 401   if (!safeExitBlock(SD, ExitCondition->getParent()))
 402     return false;
 403
 404   // Update CFG.
 405
 406   // As a first step to break this loop, remove Latch to Header edge.
 407   BasicBlock *Latch = L->getLoopLatch();
 408   BasicBlock *LatchSucc = NULL;
 409   BranchInst *BR = dyn_cast<BranchInst>(Latch->getTerminator());
 410   if (!BR)
 411     return false;
 412   Header->removePredecessor(Latch);
 413   for (succ_iterator SI = succ_begin(Latch), E = succ_end(Latch);
 414        SI != E; ++SI) {
 415     if (Header != *SI)
 416       LatchSucc = *SI;
 417   }
 418   BR->setUnconditionalDest(LatchSucc);
 419
 420   BasicBlock *Preheader = L->getLoopPreheader();
 421   Instruction *Terminator = Header->getTerminator();
 422   StartValue = IndVar->getIncomingValueForBlock(Preheader);
 423
 424   // Replace split condition in header.
 425   // Transform
 426   //      SplitCondition : icmp eq i32 IndVar, SplitValue
 427   // into
 428   //      c1 = icmp uge i32 SplitValue, StartValue
 429   //      c2 = icmp ult i32 vSplitValue, ExitValue
 430   //      and i32 c1, c2
 431   bool SignedPredicate = ExitCondition->isSignedPredicate();
 432   Instruction *C1 = new ICmpInst(SignedPredicate ?
 433                                  ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE,
 434                                  SD.SplitValue, StartValue, "lisplit",
 435                                  Terminator);
 436   Instruction *C2 = new ICmpInst(SignedPredicate ?
 437                                  ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 438                                  SD.SplitValue,
 439                                  ExitCondition->getOperand(ExitValueNum), "lisplit",
 440                                  Terminator);
 441   Instruction *NSplitCond = BinaryOperator::createAnd(C1, C2, "lisplit",
 442                                                       Terminator);
 443   SD.SplitCondition->replaceAllUsesWith(NSplitCond);
 444   SD.SplitCondition->eraseFromParent();
 445
 446   // Now, clear latch block. Remove instructions that are responsible
 447   // to increment induction variable.
 448   Instruction *LTerminator = Latch->getTerminator();
 449   for (BasicBlock::iterator LB = Latch->begin(), LE = Latch->end();
 450        LB != LE; ) {
 451     Instruction *I = LB;
 452     ++LB;
 453     if (isa<PHINode>(I) || I == LTerminator)
 454       continue;
 455
 456     I->replaceAllUsesWith(UndefValue::get(I->getType()));
 457     I->eraseFromParent();
 458   }
 459
 460   LPM->deleteLoopFromQueue(L);
 461
 462   // Update Dominator Info.
 463   // Only CFG change done is to remove Latch to Header edge. This
 464   // does not change dominator tree because Latch did not dominate
 465   // Header.
 466   if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) {
 467     DominanceFrontier::iterator HeaderDF = DF->find(Header);
 468     if (HeaderDF != DF->end())
 469       DF->removeFromFrontier(HeaderDF, Header);
 470
 471     DominanceFrontier::iterator LatchDF = DF->find(Latch);
 472     if (LatchDF != DF->end())
 473       DF->removeFromFrontier(LatchDF, Header);
 474   }
 475   return true;
 476 }
 477
 478 // If loop header includes loop variant instruction operands then
 479 // this loop can not be eliminated. This is used by processOneIterationLoop().
 480 bool LoopIndexSplit::safeHeader(SplitInfo &SD, BasicBlock *Header) {
 481
 482   Instruction *Terminator = Header->getTerminator();
 483   for(BasicBlock::iterator BI = Header->begin(), BE = Header->end();
 484       BI != BE; ++BI) {
 485     Instruction *I = BI;
 486
 487     // PHI Nodes are OK. FIXME : Handle last value assignments.
 488     if (isa<PHINode>(I))
 489       continue;
 490
 491     // SplitCondition itself is OK.
 492     if (I == SD.SplitCondition)
 493       continue;
 494
 495     // Induction variable is OK.
 496     if (I == IndVar)
 497       continue;
 498
 499     // Induction variable increment is OK.
 500     if (I == IndVarIncrement)
 501       continue;
 502
 503     // Terminator is also harmless.
 504     if (I == Terminator)
 505       continue;
 506
 507     // Otherwise we have a instruction that may not be safe.
 508     return false;
 509   }
 510
 511   return true;
 512 }
 513
 514 // If Exit block includes loop variant instructions then this
 515 // loop may not be eliminated. This is used by processOneIterationLoop().
 516 bool LoopIndexSplit::safeExitBlock(SplitInfo &SD, BasicBlock *ExitBlock) {
 517
 518   for (BasicBlock::iterator BI = ExitBlock->begin(), BE = ExitBlock->end();
 519        BI != BE; ++BI) {
 520     Instruction *I = BI;
 521
 522     // PHI Nodes are OK. FIXME : Handle last value assignments.
 523     if (isa<PHINode>(I))
 524       continue;
 525
 526     // Induction variable increment is OK.
 527     if (IndVarIncrement && IndVarIncrement == I)
 528       continue;
 529
 530     // Check if I is induction variable increment instruction.
 531     if (!IndVarIncrement && I->getOpcode() == Instruction::Add) {
 532
 533       Value *Op0 = I->getOperand(0);
 534       Value *Op1 = I->getOperand(1);
 535       PHINode *PN = NULL;
 536       ConstantInt *CI = NULL;
 537
 538       if ((PN = dyn_cast<PHINode>(Op0))) {
 539         if ((CI = dyn_cast<ConstantInt>(Op1)))
 540           IndVarIncrement = I;
 541       } else
 542         if ((PN = dyn_cast<PHINode>(Op1))) {
 543           if ((CI = dyn_cast<ConstantInt>(Op0)))
 544             IndVarIncrement = I;
 545       }
 546
 547       if (IndVarIncrement && PN == IndVar && CI->isOne())
 548         continue;
 549     }
 550
 551     // I is an Exit condition if next instruction is block terminator.
 552     // Exit condition is OK if it compares loop invariant exit value,
 553     // which is checked below.
 554     else if (ICmpInst *EC = dyn_cast<ICmpInst>(I)) {
 555       if (EC == ExitCondition)
 556         continue;
 557     }
 558
 559     if (I == ExitBlock->getTerminator())
 560       continue;
 561
 562     // Otherwise we have instruction that may not be safe.
 563     return false;
 564   }
 565
 566   // We could not find any reason to consider ExitBlock unsafe.
 567   return true;
 568 }
 569
 570 /// Find cost of spliting loop L. Cost is measured in terms of size growth.
 571 /// Size is growth is calculated based on amount of code duplicated in second
 572 /// loop.
 573 unsigned LoopIndexSplit::findSplitCost(Loop *L, SplitInfo &SD) {
 574
 575   unsigned Cost = 0;
 576   BasicBlock *SDBlock = SD.SplitCondition->getParent();
 577   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 578        I != E; ++I) {
 579     BasicBlock *BB = *I;
 580     // If a block is not dominated by split condition block then
 581     // it must be duplicated in both loops.
 582     if (!DT->dominates(SDBlock, BB))
 583       Cost += BB->size();
 584   }
 585
 586   return Cost;
 587 }
 588
 589 /// removeBlocks - Remove basic block BB and all blocks dominated by BB.
 590 void LoopIndexSplit::removeBlocks(BasicBlock *InBB) {
 591
 592   SmallVector<BasicBlock *, 8> WorkList;
 593   WorkList.push_back(InBB);
 594   while (!WorkList.empty()) {
 595     BasicBlock *BB = WorkList.back(); WorkList.pop_back();
 596
 597     // First process all successor
 598     for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) {
 599       BasicBlock *SuccBB = *SI;
 600       if (DT->dominates(BB, SuccBB)) {
 601         WorkList.push_back(SuccBB);
 602         continue;
 603       }
 604
 605       // If SuccBB is not dominated by BB then it is not removed, however remove
 606       // any PHI incoming edge from BB.
 607       for(BasicBlock::iterator SBI = SuccBB->begin(), SBE = SuccBB->end();
 608           SBI != SBE; ++SBI) {
 609         if (PHINode *PN = dyn_cast<PHINode>(SBI))
 610           PN->removeIncomingValue(BB);
 611         else
 612           break;
 613       }
 614     }
 615
 616     // Now delete BB;
 617     for(BasicBlock::iterator BBI = BB->begin(), BBE = BB->end();
 618         BBI != BBE; ++BBI) {
 619       Instruction *I = BBI;
 620       I->replaceAllUsesWith(UndefValue::get(I->getType()));
 621       I->eraseFromParent();
 622     }
 623     LI->removeBlock(BB);
 624     BB->eraseFromParent();
 625   }
 626 }
 627
 628 bool LoopIndexSplit::splitLoop(SplitInfo &SD) {
 629
 630   BasicBlock *Preheader = L->getLoopPreheader();
 631
 632   // True loop is original loop. False loop is cloned loop.
 633
 634   bool SignedPredicate = ExitCondition->isSignedPredicate();
 635   //[*] Calculate True loop's new Exit Value in loop preheader.
 636   //      TLExitValue = min(SplitValue, ExitValue)
 637   //[*] Calculate False loop's new Start Value in loop preheader.
 638   //      FLStartValue = min(SplitValue, TrueLoop.StartValue)
 639   Value *TLExitValue = NULL;
 640   Value *FLStartValue = NULL;
 641   if (isa<ConstantInt>(SD.SplitValue)) {
 642     TLExitValue = SD.SplitValue;
 643     FLStartValue = SD.SplitValue;
 644   }
 645   else {
 646     Value *C1 = new ICmpInst(SignedPredicate ?
 647                             ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 648                             SD.SplitValue,
 649                              ExitCondition->getOperand(ExitValueNum),
 650                              "lsplit.ev",
 651                             Preheader->getTerminator());
 652     TLExitValue = new SelectInst(C1, SD.SplitValue,
 653                                  ExitCondition->getOperand(ExitValueNum),
 654                                  "lsplit.ev", Preheader->getTerminator());
 655
 656     Value *C2 = new ICmpInst(SignedPredicate ?
 657                              ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 658                              SD.SplitValue, StartValue, "lsplit.sv",
 659                              Preheader->getTerminator());
 660     FLStartValue = new SelectInst(C2, SD.SplitValue, StartValue,
 661                                   "lsplit.sv", Preheader->getTerminator());
 662   }
 663
 664   //[*] Clone loop. Avoid true destination of split condition and
 665   //    the blocks dominated by true destination.
 666   DenseMap<const Value *, Value *> ValueMap;
 667   Loop *FalseLoop = CloneLoop(L, LPM, LI, ValueMap, this);
 668   BasicBlock *FalseHeader = FalseLoop->getHeader();
 669
 670   //[*] True loop's exit edge enters False loop.
 671   PHINode *IndVarClone = cast<PHINode>(ValueMap[IndVar]);
 672   BasicBlock *ExitBlock = ExitCondition->getParent();
 673   BranchInst *ExitInsn = dyn_cast<BranchInst>(ExitBlock->getTerminator());
 674   assert (ExitInsn && "Unable to find suitable loop exit branch");
 675   BasicBlock *ExitDest = ExitInsn->getSuccessor(1);
 676
 677   for (BasicBlock::iterator BI = FalseHeader->begin(), BE = FalseHeader->end();
 678        BI != BE; ++BI) {
 679     if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 680       PN->removeIncomingValue(Preheader);
 681       if (PN == IndVarClone)
 682         PN->addIncoming(FLStartValue, ExitBlock);
 683       // else { FIXME : Handl last value assignments.}
 684     }
 685     else
 686       break;
 687   }
 688
 689   if (L->contains(ExitDest)) {
 690     ExitDest = ExitInsn->getSuccessor(0);
 691     ExitInsn->setSuccessor(0, FalseHeader);
 692   } else
 693     ExitInsn->setSuccessor(1, FalseHeader);
 694
 695   assert (!L->contains(ExitDest) && " Unable to find exit edge destination");
 696
 697   //[*] Split Exit Edge.
 698   SplitEdge(ExitBlock, FalseHeader, this);
 699
 700   //[*] Eliminate split condition's false branch from True loop.
 701   //    Update true loop dom info (FIXME).
 702   BasicBlock *SplitBlock = SD.SplitCondition->getParent();
 703   BranchInst *BR = cast<BranchInst>(SplitBlock->getTerminator());
 704   BasicBlock *FBB = BR->getSuccessor(1);
 705   BR->setUnconditionalDest(BR->getSuccessor(0));
 706   removeBlocks(FBB);
 707
 708   //[*] Update True loop's exit value using new exit value.
 709   ExitCondition->setOperand(ExitValueNum, TLExitValue);
 710
 711   //[*] Eliminate split condition's  true branch in False loop CFG.
 712   //    Update false loop dom info (FXME).
 713   BasicBlock *FSplitBlock = cast<BasicBlock>(ValueMap[SplitBlock]);
 714   BranchInst *FBR = cast<BranchInst>(FSplitBlock->getTerminator());
 715   BasicBlock *TBB = FBR->getSuccessor(0);
 716   FBR->setUnconditionalDest(FBR->getSuccessor(1));
 717   removeBlocks(TBB);
 718
 719   //[*] Update dom info in general (FIXME).
 720   return true;
 721 }
 722