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