lib/Transforms/Utils/SimplifyCFG.cpp

   1 //===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Peephole optimize the CFG.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "simplifycfg"
  15 #include "llvm/Transforms/Utils/Local.h"
  16 #include "llvm/Constants.h"
  17 #include "llvm/Instructions.h"
  18 #include "llvm/Type.h"
  19 #include "llvm/Support/CFG.h"
  20 #include "llvm/Support/Debug.h"
  21 #include <algorithm>
  22 #include <functional>
  23 #include <set>
  24 #include <map>
  25 using namespace llvm;
  26
  27 /// SafeToMergeTerminators - Return true if it is safe to merge these two
  28 /// terminator instructions together.
  29 ///
  30 static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) {
  31   if (SI1 == SI2) return false;  // Can't merge with self!
  32
  33   // It is not safe to merge these two switch instructions if they have a common
  34   // successor, and if that successor has a PHI node, and if *that* PHI node has
  35   // conflicting incoming values from the two switch blocks.
  36   BasicBlock *SI1BB = SI1->getParent();
  37   BasicBlock *SI2BB = SI2->getParent();
  38   std::set<BasicBlock*> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
  39
  40   for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I)
  41     if (SI1Succs.count(*I))
  42       for (BasicBlock::iterator BBI = (*I)->begin();
  43            isa<PHINode>(BBI); ++BBI) {
  44         PHINode *PN = cast<PHINode>(BBI);
  45         if (PN->getIncomingValueForBlock(SI1BB) !=
  46             PN->getIncomingValueForBlock(SI2BB))
  47           return false;
  48       }
  49
  50   return true;
  51 }
  52
  53 /// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will
  54 /// now be entries in it from the 'NewPred' block.  The values that will be
  55 /// flowing into the PHI nodes will be the same as those coming in from
  56 /// ExistPred, an existing predecessor of Succ.
  57 static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred,
  58                                   BasicBlock *ExistPred) {
  59   assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) !=
  60          succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!");
  61   if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do
  62
  63   for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
  64     PHINode *PN = cast<PHINode>(I);
  65     Value *V = PN->getIncomingValueForBlock(ExistPred);
  66     PN->addIncoming(V, NewPred);
  67   }
  68 }
  69
  70 // CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an
  71 // almost-empty BB ending in an unconditional branch to Succ, into succ.
  72 //
  73 // Assumption: Succ is the single successor for BB.
  74 //
  75 static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
  76   assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
  77
  78   // Check to see if one of the predecessors of BB is already a predecessor of
  79   // Succ.  If so, we cannot do the transformation if there are any PHI nodes
  80   // with incompatible values coming in from the two edges!
  81   //
  82   if (isa<PHINode>(Succ->front())) {
  83     std::set<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB));
  84     for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ);\
  85          PI != PE; ++PI)
  86       if (std::find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) {
  87         // Loop over all of the PHI nodes checking to see if there are
  88         // incompatible values coming in.
  89         for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
  90           PHINode *PN = cast<PHINode>(I);
  91           // Loop up the entries in the PHI node for BB and for *PI if the
  92           // values coming in are non-equal, we cannot merge these two blocks
  93           // (instead we should insert a conditional move or something, then
  94           // merge the blocks).
  95           if (PN->getIncomingValueForBlock(BB) !=
  96               PN->getIncomingValueForBlock(*PI))
  97             return false;  // Values are not equal...
  98         }
  99       }
 100   }
 101
 102   // Finally, if BB has PHI nodes that are used by things other than the PHIs in
 103   // Succ and Succ has predecessors that are not Succ and not Pred, we cannot
 104   // fold these blocks, as we don't know whether BB dominates Succ or not to
 105   // update the PHI nodes correctly.
 106   if (!isa<PHINode>(BB->begin()) || Succ->getSinglePredecessor()) return true;
 107
 108   // If the predecessors of Succ are only BB and Succ itself, we can handle this.
 109   bool IsSafe = true;
 110   for (pred_iterator PI = pred_begin(Succ), E = pred_end(Succ); PI != E; ++PI)
 111     if (*PI != Succ && *PI != BB) {
 112       IsSafe = false;
 113       break;
 114     }
 115   if (IsSafe) return true;
 116
 117   // If the PHI nodes in BB are only used by instructions in Succ, we are ok.
 118   IsSafe = true;
 119   for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I) && IsSafe; ++I) {
 120     PHINode *PN = cast<PHINode>(I);
 121     for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end(); UI != E;
 122          ++UI)
 123       if (cast<Instruction>(*UI)->getParent() != Succ) {
 124         IsSafe = false;
 125         break;
 126       }
 127   }
 128
 129   return IsSafe;
 130 }
 131
 132 /// TryToSimplifyUncondBranchFromEmptyBlock - BB contains an unconditional
 133 /// branch to Succ, and contains no instructions other than PHI nodes and the
 134 /// branch.  If possible, eliminate BB.
 135 static bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
 136                                                     BasicBlock *Succ) {
 137   // If our successor has PHI nodes, then we need to update them to include
 138   // entries for BB's predecessors, not for BB itself.  Be careful though,
 139   // if this transformation fails (returns true) then we cannot do this
 140   // transformation!
 141   //
 142   if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;
 143
 144   DEBUG(std::cerr << "Killing Trivial BB: \n" << *BB);
 145
 146   if (isa<PHINode>(Succ->begin())) {
 147     // If there is more than one pred of succ, and there are PHI nodes in
 148     // the successor, then we need to add incoming edges for the PHI nodes
 149     //
 150     const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB));
 151
 152     // Loop over all of the PHI nodes in the successor of BB.
 153     for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
 154       PHINode *PN = cast<PHINode>(I);
 155       Value *OldVal = PN->removeIncomingValue(BB, false);
 156       assert(OldVal && "No entry in PHI for Pred BB!");
 157
 158       // If this incoming value is one of the PHI nodes in BB, the new entries
 159       // in the PHI node are the entries from the old PHI.
 160       if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
 161         PHINode *OldValPN = cast<PHINode>(OldVal);
 162         for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i)
 163           PN->addIncoming(OldValPN->getIncomingValue(i),
 164                           OldValPN->getIncomingBlock(i));
 165       } else {
 166         for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(),
 167              End = BBPreds.end(); PredI != End; ++PredI) {
 168           // Add an incoming value for each of the new incoming values...
 169           PN->addIncoming(OldVal, *PredI);
 170         }
 171       }
 172     }
 173   }
 174
 175   if (isa<PHINode>(&BB->front())) {
 176     std::vector<BasicBlock*>
 177     OldSuccPreds(pred_begin(Succ), pred_end(Succ));
 178
 179     // Move all PHI nodes in BB to Succ if they are alive, otherwise
 180     // delete them.
 181     while (PHINode *PN = dyn_cast<PHINode>(&BB->front()))
 182       if (PN->use_empty()) {
 183         // Just remove the dead phi.  This happens if Succ's PHIs were the only
 184         // users of the PHI nodes.
 185         PN->eraseFromParent();
 186       } else {
 187         // The instruction is alive, so this means that Succ must have
 188         // *ONLY* had BB as a predecessor, and the PHI node is still valid
 189         // now.  Simply move it into Succ, because we know that BB
 190         // strictly dominated Succ.
 191         Succ->getInstList().splice(Succ->begin(),
 192                                    BB->getInstList(), BB->begin());
 193
 194         // We need to add new entries for the PHI node to account for
 195         // predecessors of Succ that the PHI node does not take into
 196         // account.  At this point, since we know that BB dominated succ,
 197         // this means that we should any newly added incoming edges should
 198         // use the PHI node as the value for these edges, because they are
 199         // loop back edges.
 200         for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i)
 201           if (OldSuccPreds[i] != BB)
 202             PN->addIncoming(PN, OldSuccPreds[i]);
 203       }
 204   }
 205
 206   // Everything that jumped to BB now goes to Succ.
 207   std::string OldName = BB->getName();
 208   BB->replaceAllUsesWith(Succ);
 209   BB->eraseFromParent();              // Delete the old basic block.
 210
 211   if (!OldName.empty() && !Succ->hasName())  // Transfer name if we can
 212     Succ->setName(OldName);
 213   return true;
 214 }
 215
 216 /// GetIfCondition - Given a basic block (BB) with two predecessors (and
 217 /// presumably PHI nodes in it), check to see if the merge at this block is due
 218 /// to an "if condition".  If so, return the boolean condition that determines
 219 /// which entry into BB will be taken.  Also, return by references the block
 220 /// that will be entered from if the condition is true, and the block that will
 221 /// be entered if the condition is false.
 222 ///
 223 ///
 224 static Value *GetIfCondition(BasicBlock *BB,
 225                              BasicBlock *&IfTrue, BasicBlock *&IfFalse) {
 226   assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 &&
 227          "Function can only handle blocks with 2 predecessors!");
 228   BasicBlock *Pred1 = *pred_begin(BB);
 229   BasicBlock *Pred2 = *++pred_begin(BB);
 230
 231   // We can only handle branches.  Other control flow will be lowered to
 232   // branches if possible anyway.
 233   if (!isa<BranchInst>(Pred1->getTerminator()) ||
 234       !isa<BranchInst>(Pred2->getTerminator()))
 235     return 0;
 236   BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator());
 237   BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator());
 238
 239   // Eliminate code duplication by ensuring that Pred1Br is conditional if
 240   // either are.
 241   if (Pred2Br->isConditional()) {
 242     // If both branches are conditional, we don't have an "if statement".  In
 243     // reality, we could transform this case, but since the condition will be
 244     // required anyway, we stand no chance of eliminating it, so the xform is
 245     // probably not profitable.
 246     if (Pred1Br->isConditional())
 247       return 0;
 248
 249     std::swap(Pred1, Pred2);
 250     std::swap(Pred1Br, Pred2Br);
 251   }
 252
 253   if (Pred1Br->isConditional()) {
 254     // If we found a conditional branch predecessor, make sure that it branches
 255     // to BB and Pred2Br.  If it doesn't, this isn't an "if statement".
 256     if (Pred1Br->getSuccessor(0) == BB &&
 257         Pred1Br->getSuccessor(1) == Pred2) {
 258       IfTrue = Pred1;
 259       IfFalse = Pred2;
 260     } else if (Pred1Br->getSuccessor(0) == Pred2 &&
 261                Pred1Br->getSuccessor(1) == BB) {
 262       IfTrue = Pred2;
 263       IfFalse = Pred1;
 264     } else {
 265       // We know that one arm of the conditional goes to BB, so the other must
 266       // go somewhere unrelated, and this must not be an "if statement".
 267       return 0;
 268     }
 269
 270     // The only thing we have to watch out for here is to make sure that Pred2
 271     // doesn't have incoming edges from other blocks.  If it does, the condition
 272     // doesn't dominate BB.
 273     if (++pred_begin(Pred2) != pred_end(Pred2))
 274       return 0;
 275
 276     return Pred1Br->getCondition();
 277   }
 278
 279   // Ok, if we got here, both predecessors end with an unconditional branch to
 280   // BB.  Don't panic!  If both blocks only have a single (identical)
 281   // predecessor, and THAT is a conditional branch, then we're all ok!
 282   if (pred_begin(Pred1) == pred_end(Pred1) ||
 283       ++pred_begin(Pred1) != pred_end(Pred1) ||
 284       pred_begin(Pred2) == pred_end(Pred2) ||
 285       ++pred_begin(Pred2) != pred_end(Pred2) ||
 286       *pred_begin(Pred1) != *pred_begin(Pred2))
 287     return 0;
 288
 289   // Otherwise, if this is a conditional branch, then we can use it!
 290   BasicBlock *CommonPred = *pred_begin(Pred1);
 291   if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) {
 292     assert(BI->isConditional() && "Two successors but not conditional?");
 293     if (BI->getSuccessor(0) == Pred1) {
 294       IfTrue = Pred1;
 295       IfFalse = Pred2;
 296     } else {
 297       IfTrue = Pred2;
 298       IfFalse = Pred1;
 299     }
 300     return BI->getCondition();
 301   }
 302   return 0;
 303 }
 304
 305
 306 // If we have a merge point of an "if condition" as accepted above, return true
 307 // if the specified value dominates the block.  We don't handle the true
 308 // generality of domination here, just a special case which works well enough
 309 // for us.
 310 //
 311 // If AggressiveInsts is non-null, and if V does not dominate BB, we check to
 312 // see if V (which must be an instruction) is cheap to compute and is
 313 // non-trapping.  If both are true, the instruction is inserted into the set and
 314 // true is returned.
 315 static bool DominatesMergePoint(Value *V, BasicBlock *BB,
 316                                 std::set<Instruction*> *AggressiveInsts) {
 317   Instruction *I = dyn_cast<Instruction>(V);
 318   if (!I) return true;    // Non-instructions all dominate instructions.
 319   BasicBlock *PBB = I->getParent();
 320
 321   // We don't want to allow weird loops that might have the "if condition" in
 322   // the bottom of this block.
 323   if (PBB == BB) return false;
 324
 325   // If this instruction is defined in a block that contains an unconditional
 326   // branch to BB, then it must be in the 'conditional' part of the "if
 327   // statement".
 328   if (BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator()))
 329     if (BI->isUnconditional() && BI->getSuccessor(0) == BB) {
 330       if (!AggressiveInsts) return false;
 331       // Okay, it looks like the instruction IS in the "condition".  Check to
 332       // see if its a cheap instruction to unconditionally compute, and if it
 333       // only uses stuff defined outside of the condition.  If so, hoist it out.
 334       switch (I->getOpcode()) {
 335       default: return false;  // Cannot hoist this out safely.
 336       case Instruction::Load:
 337         // We can hoist loads that are non-volatile and obviously cannot trap.
 338         if (cast<LoadInst>(I)->isVolatile())
 339           return false;
 340         if (!isa<AllocaInst>(I->getOperand(0)) &&
 341             !isa<Constant>(I->getOperand(0)))
 342           return false;
 343
 344         // Finally, we have to check to make sure there are no instructions
 345         // before the load in its basic block, as we are going to hoist the loop
 346         // out to its predecessor.
 347         if (PBB->begin() != BasicBlock::iterator(I))
 348           return false;
 349         break;
 350       case Instruction::Add:
 351       case Instruction::Sub:
 352       case Instruction::And:
 353       case Instruction::Or:
 354       case Instruction::Xor:
 355       case Instruction::Shl:
 356       case Instruction::Shr:
 357       case Instruction::SetEQ:
 358       case Instruction::SetNE:
 359       case Instruction::SetLT:
 360       case Instruction::SetGT:
 361       case Instruction::SetLE:
 362       case Instruction::SetGE:
 363         break;   // These are all cheap and non-trapping instructions.
 364       }
 365
 366       // Okay, we can only really hoist these out if their operands are not
 367       // defined in the conditional region.
 368       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 369         if (!DominatesMergePoint(I->getOperand(i), BB, 0))
 370           return false;
 371       // Okay, it's safe to do this!  Remember this instruction.
 372       AggressiveInsts->insert(I);
 373     }
 374
 375   return true;
 376 }
 377
 378 // GatherConstantSetEQs - Given a potentially 'or'd together collection of seteq
 379 // instructions that compare a value against a constant, return the value being
 380 // compared, and stick the constant into the Values vector.
 381 static Value *GatherConstantSetEQs(Value *V, std::vector<ConstantInt*> &Values){
 382   if (Instruction *Inst = dyn_cast<Instruction>(V))
 383     if (Inst->getOpcode() == Instruction::SetEQ) {
 384       if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) {
 385         Values.push_back(C);
 386         return Inst->getOperand(0);
 387       } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) {
 388         Values.push_back(C);
 389         return Inst->getOperand(1);
 390       }
 391     } else if (Inst->getOpcode() == Instruction::Or) {
 392       if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values))
 393         if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values))
 394           if (LHS == RHS)
 395             return LHS;
 396     }
 397   return 0;
 398 }
 399
 400 // GatherConstantSetNEs - Given a potentially 'and'd together collection of
 401 // setne instructions that compare a value against a constant, return the value
 402 // being compared, and stick the constant into the Values vector.
 403 static Value *GatherConstantSetNEs(Value *V, std::vector<ConstantInt*> &Values){
 404   if (Instruction *Inst = dyn_cast<Instruction>(V))
 405     if (Inst->getOpcode() == Instruction::SetNE) {
 406       if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) {
 407         Values.push_back(C);
 408         return Inst->getOperand(0);
 409       } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) {
 410         Values.push_back(C);
 411         return Inst->getOperand(1);
 412       }
 413     } else if (Inst->getOpcode() == Instruction::Cast) {
 414       // Cast of X to bool is really a comparison against zero.
 415       assert(Inst->getType() == Type::BoolTy && "Can only handle bool values!");
 416       Values.push_back(ConstantInt::get(Inst->getOperand(0)->getType(), 0));
 417       return Inst->getOperand(0);
 418     } else if (Inst->getOpcode() == Instruction::And) {
 419       if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values))
 420         if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values))
 421           if (LHS == RHS)
 422             return LHS;
 423     }
 424   return 0;
 425 }
 426
 427
 428
 429 /// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a
 430 /// bunch of comparisons of one value against constants, return the value and
 431 /// the constants being compared.
 432 static bool GatherValueComparisons(Instruction *Cond, Value *&CompVal,
 433                                    std::vector<ConstantInt*> &Values) {
 434   if (Cond->getOpcode() == Instruction::Or) {
 435     CompVal = GatherConstantSetEQs(Cond, Values);
 436
 437     // Return true to indicate that the condition is true if the CompVal is
 438     // equal to one of the constants.
 439     return true;
 440   } else if (Cond->getOpcode() == Instruction::And) {
 441     CompVal = GatherConstantSetNEs(Cond, Values);
 442
 443     // Return false to indicate that the condition is false if the CompVal is
 444     // equal to one of the constants.
 445     return false;
 446   }
 447   return false;
 448 }
 449
 450 /// ErasePossiblyDeadInstructionTree - If the specified instruction is dead and
 451 /// has no side effects, nuke it.  If it uses any instructions that become dead
 452 /// because the instruction is now gone, nuke them too.
 453 static void ErasePossiblyDeadInstructionTree(Instruction *I) {
 454   if (isInstructionTriviallyDead(I)) {
 455     std::vector<Value*> Operands(I->op_begin(), I->op_end());
 456     I->getParent()->getInstList().erase(I);
 457     for (unsigned i = 0, e = Operands.size(); i != e; ++i)
 458       if (Instruction *OpI = dyn_cast<Instruction>(Operands[i]))
 459         ErasePossiblyDeadInstructionTree(OpI);
 460   }
 461 }
 462
 463 // isValueEqualityComparison - Return true if the specified terminator checks to
 464 // see if a value is equal to constant integer value.
 465 static Value *isValueEqualityComparison(TerminatorInst *TI) {
 466   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 467     // Do not permit merging of large switch instructions into their
 468     // predecessors unless there is only one predecessor.
 469     if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()),
 470                                                pred_end(SI->getParent())) > 128)
 471       return 0;
 472
 473     return SI->getCondition();
 474   }
 475   if (BranchInst *BI = dyn_cast<BranchInst>(TI))
 476     if (BI->isConditional() && BI->getCondition()->hasOneUse())
 477       if (SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition()))
 478         if ((SCI->getOpcode() == Instruction::SetEQ ||
 479              SCI->getOpcode() == Instruction::SetNE) &&
 480             isa<ConstantInt>(SCI->getOperand(1)))
 481           return SCI->getOperand(0);
 482   return 0;
 483 }
 484
 485 // Given a value comparison instruction, decode all of the 'cases' that it
 486 // represents and return the 'default' block.
 487 static BasicBlock *
 488 GetValueEqualityComparisonCases(TerminatorInst *TI,
 489                                 std::vector<std::pair<ConstantInt*,
 490                                                       BasicBlock*> > &Cases) {
 491   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 492     Cases.reserve(SI->getNumCases());
 493     for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i)
 494       Cases.push_back(std::make_pair(SI->getCaseValue(i), SI->getSuccessor(i)));
 495     return SI->getDefaultDest();
 496   }
 497
 498   BranchInst *BI = cast<BranchInst>(TI);
 499   SetCondInst *SCI = cast<SetCondInst>(BI->getCondition());
 500   Cases.push_back(std::make_pair(cast<ConstantInt>(SCI->getOperand(1)),
 501                                  BI->getSuccessor(SCI->getOpcode() ==
 502                                                         Instruction::SetNE)));
 503   return BI->getSuccessor(SCI->getOpcode() == Instruction::SetEQ);
 504 }
 505
 506
 507 // EliminateBlockCases - Given an vector of bb/value pairs, remove any entries
 508 // in the list that match the specified block.
 509 static void EliminateBlockCases(BasicBlock *BB,
 510                std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases) {
 511   for (unsigned i = 0, e = Cases.size(); i != e; ++i)
 512     if (Cases[i].second == BB) {
 513       Cases.erase(Cases.begin()+i);
 514       --i; --e;
 515     }
 516 }
 517
 518 // ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as
 519 // well.
 520 static bool
 521 ValuesOverlap(std::vector<std::pair<ConstantInt*, BasicBlock*> > &C1,
 522               std::vector<std::pair<ConstantInt*, BasicBlock*> > &C2) {
 523   std::vector<std::pair<ConstantInt*, BasicBlock*> > *V1 = &C1, *V2 = &C2;
 524
 525   // Make V1 be smaller than V2.
 526   if (V1->size() > V2->size())
 527     std::swap(V1, V2);
 528
 529   if (V1->size() == 0) return false;
 530   if (V1->size() == 1) {
 531     // Just scan V2.
 532     ConstantInt *TheVal = (*V1)[0].first;
 533     for (unsigned i = 0, e = V2->size(); i != e; ++i)
 534       if (TheVal == (*V2)[i].first)
 535         return true;
 536   }
 537
 538   // Otherwise, just sort both lists and compare element by element.
 539   std::sort(V1->begin(), V1->end());
 540   std::sort(V2->begin(), V2->end());
 541   unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
 542   while (i1 != e1 && i2 != e2) {
 543     if ((*V1)[i1].first == (*V2)[i2].first)
 544       return true;
 545     if ((*V1)[i1].first < (*V2)[i2].first)
 546       ++i1;
 547     else
 548       ++i2;
 549   }
 550   return false;
 551 }
 552
 553 // SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a
 554 // terminator instruction and its block is known to only have a single
 555 // predecessor block, check to see if that predecessor is also a value
 556 // comparison with the same value, and if that comparison determines the outcome
 557 // of this comparison.  If so, simplify TI.  This does a very limited form of
 558 // jump threading.
 559 static bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
 560                                                           BasicBlock *Pred) {
 561   Value *PredVal = isValueEqualityComparison(Pred->getTerminator());
 562   if (!PredVal) return false;  // Not a value comparison in predecessor.
 563
 564   Value *ThisVal = isValueEqualityComparison(TI);
 565   assert(ThisVal && "This isn't a value comparison!!");
 566   if (ThisVal != PredVal) return false;  // Different predicates.
 567
 568   // Find out information about when control will move from Pred to TI's block.
 569   std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases;
 570   BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(),
 571                                                         PredCases);
 572   EliminateBlockCases(PredDef, PredCases);  // Remove default from cases.
 573
 574   // Find information about how control leaves this block.
 575   std::vector<std::pair<ConstantInt*, BasicBlock*> > ThisCases;
 576   BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
 577   EliminateBlockCases(ThisDef, ThisCases);  // Remove default from cases.
 578
 579   // If TI's block is the default block from Pred's comparison, potentially
 580   // simplify TI based on this knowledge.
 581   if (PredDef == TI->getParent()) {
 582     // If we are here, we know that the value is none of those cases listed in
 583     // PredCases.  If there are any cases in ThisCases that are in PredCases, we
 584     // can simplify TI.
 585     if (ValuesOverlap(PredCases, ThisCases)) {
 586       if (BranchInst *BTI = dyn_cast<BranchInst>(TI)) {
 587         // Okay, one of the successors of this condbr is dead.  Convert it to a
 588         // uncond br.
 589         assert(ThisCases.size() == 1 && "Branch can only have one case!");
 590         Value *Cond = BTI->getCondition();
 591         // Insert the new branch.
 592         Instruction *NI = new BranchInst(ThisDef, TI);
 593
 594         // Remove PHI node entries for the dead edge.
 595         ThisCases[0].second->removePredecessor(TI->getParent());
 596
 597         DEBUG(std::cerr << "Threading pred instr: " << *Pred->getTerminator()
 598               << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n");
 599
 600         TI->eraseFromParent();   // Nuke the old one.
 601         // If condition is now dead, nuke it.
 602         if (Instruction *CondI = dyn_cast<Instruction>(Cond))
 603           ErasePossiblyDeadInstructionTree(CondI);
 604         return true;
 605
 606       } else {
 607         SwitchInst *SI = cast<SwitchInst>(TI);
 608         // Okay, TI has cases that are statically dead, prune them away.
 609         std::set<Constant*> DeadCases;
 610         for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
 611           DeadCases.insert(PredCases[i].first);
 612
 613         DEBUG(std::cerr << "Threading pred instr: " << *Pred->getTerminator()
 614                   << "Through successor TI: " << *TI);
 615
 616         for (unsigned i = SI->getNumCases()-1; i != 0; --i)
 617           if (DeadCases.count(SI->getCaseValue(i))) {
 618             SI->getSuccessor(i)->removePredecessor(TI->getParent());
 619             SI->removeCase(i);
 620           }
 621
 622         DEBUG(std::cerr << "Leaving: " << *TI << "\n");
 623         return true;
 624       }
 625     }
 626
 627   } else {
 628     // Otherwise, TI's block must correspond to some matched value.  Find out
 629     // which value (or set of values) this is.
 630     ConstantInt *TIV = 0;
 631     BasicBlock *TIBB = TI->getParent();
 632     for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
 633       if (PredCases[i].second == TIBB)
 634         if (TIV == 0)
 635           TIV = PredCases[i].first;
 636         else
 637           return false;  // Cannot handle multiple values coming to this block.
 638     assert(TIV && "No edge from pred to succ?");
 639
 640     // Okay, we found the one constant that our value can be if we get into TI's
 641     // BB.  Find out which successor will unconditionally be branched to.
 642     BasicBlock *TheRealDest = 0;
 643     for (unsigned i = 0, e = ThisCases.size(); i != e; ++i)
 644       if (ThisCases[i].first == TIV) {
 645         TheRealDest = ThisCases[i].second;
 646         break;
 647       }
 648
 649     // If not handled by any explicit cases, it is handled by the default case.
 650     if (TheRealDest == 0) TheRealDest = ThisDef;
 651
 652     // Remove PHI node entries for dead edges.
 653     BasicBlock *CheckEdge = TheRealDest;
 654     for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI)
 655       if (*SI != CheckEdge)
 656         (*SI)->removePredecessor(TIBB);
 657       else
 658         CheckEdge = 0;
 659
 660     // Insert the new branch.
 661     Instruction *NI = new BranchInst(TheRealDest, TI);
 662
 663     DEBUG(std::cerr << "Threading pred instr: " << *Pred->getTerminator()
 664           << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n");
 665     Instruction *Cond = 0;
 666     if (BranchInst *BI = dyn_cast<BranchInst>(TI))
 667       Cond = dyn_cast<Instruction>(BI->getCondition());
 668     TI->eraseFromParent();   // Nuke the old one.
 669
 670     if (Cond) ErasePossiblyDeadInstructionTree(Cond);
 671     return true;
 672   }
 673   return false;
 674 }
 675
 676 // FoldValueComparisonIntoPredecessors - The specified terminator is a value
 677 // equality comparison instruction (either a switch or a branch on "X == c").
 678 // See if any of the predecessors of the terminator block are value comparisons
 679 // on the same value.  If so, and if safe to do so, fold them together.
 680 static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) {
 681   BasicBlock *BB = TI->getParent();
 682   Value *CV = isValueEqualityComparison(TI);  // CondVal
 683   assert(CV && "Not a comparison?");
 684   bool Changed = false;
 685
 686   std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB));
 687   while (!Preds.empty()) {
 688     BasicBlock *Pred = Preds.back();
 689     Preds.pop_back();
 690
 691     // See if the predecessor is a comparison with the same value.
 692     TerminatorInst *PTI = Pred->getTerminator();
 693     Value *PCV = isValueEqualityComparison(PTI);  // PredCondVal
 694
 695     if (PCV == CV && SafeToMergeTerminators(TI, PTI)) {
 696       // Figure out which 'cases' to copy from SI to PSI.
 697       std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases;
 698       BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
 699
 700       std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases;
 701       BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
 702
 703       // Based on whether the default edge from PTI goes to BB or not, fill in
 704       // PredCases and PredDefault with the new switch cases we would like to
 705       // build.
 706       std::vector<BasicBlock*> NewSuccessors;
 707
 708       if (PredDefault == BB) {
 709         // If this is the default destination from PTI, only the edges in TI
 710         // that don't occur in PTI, or that branch to BB will be activated.
 711         std::set<ConstantInt*> PTIHandled;
 712         for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
 713           if (PredCases[i].second != BB)
 714             PTIHandled.insert(PredCases[i].first);
 715           else {
 716             // The default destination is BB, we don't need explicit targets.
 717             std::swap(PredCases[i], PredCases.back());
 718             PredCases.pop_back();
 719             --i; --e;
 720           }
 721
 722         // Reconstruct the new switch statement we will be building.
 723         if (PredDefault != BBDefault) {
 724           PredDefault->removePredecessor(Pred);
 725           PredDefault = BBDefault;
 726           NewSuccessors.push_back(BBDefault);
 727         }
 728         for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
 729           if (!PTIHandled.count(BBCases[i].first) &&
 730               BBCases[i].second != BBDefault) {
 731             PredCases.push_back(BBCases[i]);
 732             NewSuccessors.push_back(BBCases[i].second);
 733           }
 734
 735       } else {
 736         // If this is not the default destination from PSI, only the edges
 737         // in SI that occur in PSI with a destination of BB will be
 738         // activated.
 739         std::set<ConstantInt*> PTIHandled;
 740         for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
 741           if (PredCases[i].second == BB) {
 742             PTIHandled.insert(PredCases[i].first);
 743             std::swap(PredCases[i], PredCases.back());
 744             PredCases.pop_back();
 745             --i; --e;
 746           }
 747
 748         // Okay, now we know which constants were sent to BB from the
 749         // predecessor.  Figure out where they will all go now.
 750         for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
 751           if (PTIHandled.count(BBCases[i].first)) {
 752             // If this is one we are capable of getting...
 753             PredCases.push_back(BBCases[i]);
 754             NewSuccessors.push_back(BBCases[i].second);
 755             PTIHandled.erase(BBCases[i].first);// This constant is taken care of
 756           }
 757
 758         // If there are any constants vectored to BB that TI doesn't handle,
 759         // they must go to the default destination of TI.
 760         for (std::set<ConstantInt*>::iterator I = PTIHandled.begin(),
 761                E = PTIHandled.end(); I != E; ++I) {
 762           PredCases.push_back(std::make_pair(*I, BBDefault));
 763           NewSuccessors.push_back(BBDefault);
 764         }
 765       }
 766
 767       // Okay, at this point, we know which new successor Pred will get.  Make
 768       // sure we update the number of entries in the PHI nodes for these
 769       // successors.
 770       for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i)
 771         AddPredecessorToBlock(NewSuccessors[i], Pred, BB);
 772
 773       // Now that the successors are updated, create the new Switch instruction.
 774       SwitchInst *NewSI = new SwitchInst(CV, PredDefault, PredCases.size(),PTI);
 775       for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
 776         NewSI->addCase(PredCases[i].first, PredCases[i].second);
 777
 778       Instruction *DeadCond = 0;
 779       if (BranchInst *BI = dyn_cast<BranchInst>(PTI))
 780         // If PTI is a branch, remember the condition.
 781         DeadCond = dyn_cast<Instruction>(BI->getCondition());
 782       Pred->getInstList().erase(PTI);
 783
 784       // If the condition is dead now, remove the instruction tree.
 785       if (DeadCond) ErasePossiblyDeadInstructionTree(DeadCond);
 786
 787       // Okay, last check.  If BB is still a successor of PSI, then we must
 788       // have an infinite loop case.  If so, add an infinitely looping block
 789       // to handle the case to preserve the behavior of the code.
 790       BasicBlock *InfLoopBlock = 0;
 791       for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i)
 792         if (NewSI->getSuccessor(i) == BB) {
 793           if (InfLoopBlock == 0) {
 794             // Insert it at the end of the loop, because it's either code,
 795             // or it won't matter if it's hot. :)
 796             InfLoopBlock = new BasicBlock("infloop", BB->getParent());
 797             new BranchInst(InfLoopBlock, InfLoopBlock);
 798           }
 799           NewSI->setSuccessor(i, InfLoopBlock);
 800         }
 801
 802       Changed = true;
 803     }
 804   }
 805   return Changed;
 806 }
 807
 808 /// HoistThenElseCodeToIf - Given a conditional branch that codes to BB1 and
 809 /// BB2, hoist any common code in the two blocks up into the branch block.  The
 810 /// caller of this function guarantees that BI's block dominates BB1 and BB2.
 811 static bool HoistThenElseCodeToIf(BranchInst *BI) {
 812   // This does very trivial matching, with limited scanning, to find identical
 813   // instructions in the two blocks.  In particular, we don't want to get into
 814   // O(M*N) situations here where M and N are the sizes of BB1 and BB2.  As
 815   // such, we currently just scan for obviously identical instructions in an
 816   // identical order.
 817   BasicBlock *BB1 = BI->getSuccessor(0);  // The true destination.
 818   BasicBlock *BB2 = BI->getSuccessor(1);  // The false destination
 819
 820   Instruction *I1 = BB1->begin(), *I2 = BB2->begin();
 821   if (I1->getOpcode() != I2->getOpcode() || !I1->isIdenticalTo(I2))
 822     return false;
 823
 824   // If we get here, we can hoist at least one instruction.
 825   BasicBlock *BIParent = BI->getParent();
 826
 827   do {
 828     // If we are hoisting the terminator instruction, don't move one (making a
 829     // broken BB), instead clone it, and remove BI.
 830     if (isa<TerminatorInst>(I1))
 831       goto HoistTerminator;
 832
 833     // For a normal instruction, we just move one to right before the branch,
 834     // then replace all uses of the other with the first.  Finally, we remove
 835     // the now redundant second instruction.
 836     BIParent->getInstList().splice(BI, BB1->getInstList(), I1);
 837     if (!I2->use_empty())
 838       I2->replaceAllUsesWith(I1);
 839     BB2->getInstList().erase(I2);
 840
 841     I1 = BB1->begin();
 842     I2 = BB2->begin();
 843   } while (I1->getOpcode() == I2->getOpcode() && I1->isIdenticalTo(I2));
 844
 845   return true;
 846
 847 HoistTerminator:
 848   // Okay, it is safe to hoist the terminator.
 849   Instruction *NT = I1->clone();
 850   BIParent->getInstList().insert(BI, NT);
 851   if (NT->getType() != Type::VoidTy) {
 852     I1->replaceAllUsesWith(NT);
 853     I2->replaceAllUsesWith(NT);
 854     NT->setName(I1->getName());
 855   }
 856
 857   // Hoisting one of the terminators from our successor is a great thing.
 858   // Unfortunately, the successors of the if/else blocks may have PHI nodes in
 859   // them.  If they do, all PHI entries for BB1/BB2 must agree for all PHI
 860   // nodes, so we insert select instruction to compute the final result.
 861   std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects;
 862   for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) {
 863     PHINode *PN;
 864     for (BasicBlock::iterator BBI = SI->begin();
 865          (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
 866       Value *BB1V = PN->getIncomingValueForBlock(BB1);
 867       Value *BB2V = PN->getIncomingValueForBlock(BB2);
 868       if (BB1V != BB2V) {
 869         // These values do not agree.  Insert a select instruction before NT
 870         // that determines the right value.
 871         SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
 872         if (SI == 0)
 873           SI = new SelectInst(BI->getCondition(), BB1V, BB2V,
 874                               BB1V->getName()+"."+BB2V->getName(), NT);
 875         // Make the PHI node use the select for all incoming values for BB1/BB2
 876         for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 877           if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2)
 878             PN->setIncomingValue(i, SI);
 879       }
 880     }
 881   }
 882
 883   // Update any PHI nodes in our new successors.
 884   for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI)
 885     AddPredecessorToBlock(*SI, BIParent, BB1);
 886
 887   BI->eraseFromParent();
 888   return true;
 889 }
 890
 891 namespace {
 892   /// ConstantIntOrdering - This class implements a stable ordering of constant
 893   /// integers that does not depend on their address.  This is important for
 894   /// applications that sort ConstantInt's to ensure uniqueness.
 895   struct ConstantIntOrdering {
 896     bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const {
 897       return LHS->getRawValue() < RHS->getRawValue();
 898     }
 899   };
 900 }
 901
 902 // SimplifyCFG - This function is used to do simplification of a CFG.  For
 903 // example, it adjusts branches to branches to eliminate the extra hop, it
 904 // eliminates unreachable basic blocks, and does other "peephole" optimization
 905 // of the CFG.  It returns true if a modification was made.
 906 //
 907 // WARNING:  The entry node of a function may not be simplified.
 908 //
 909 bool llvm::SimplifyCFG(BasicBlock *BB) {
 910   bool Changed = false;
 911   Function *M = BB->getParent();
 912
 913   assert(BB && BB->getParent() && "Block not embedded in function!");
 914   assert(BB->getTerminator() && "Degenerate basic block encountered!");
 915   assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!");
 916
 917   // Remove basic blocks that have no predecessors... which are unreachable.
 918   if (pred_begin(BB) == pred_end(BB) ||
 919       *pred_begin(BB) == BB && ++pred_begin(BB) == pred_end(BB)) {
 920     DEBUG(std::cerr << "Removing BB: \n" << *BB);
 921
 922     // Loop through all of our successors and make sure they know that one
 923     // of their predecessors is going away.
 924     for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
 925       SI->removePredecessor(BB);
 926
 927     while (!BB->empty()) {
 928       Instruction &I = BB->back();
 929       // If this instruction is used, replace uses with an arbitrary
 930       // value.  Because control flow can't get here, we don't care
 931       // what we replace the value with.  Note that since this block is
 932       // unreachable, and all values contained within it must dominate their
 933       // uses, that all uses will eventually be removed.
 934       if (!I.use_empty())
 935         // Make all users of this instruction use undef instead
 936         I.replaceAllUsesWith(UndefValue::get(I.getType()));
 937
 938       // Remove the instruction from the basic block
 939       BB->getInstList().pop_back();
 940     }
 941     M->getBasicBlockList().erase(BB);
 942     return true;
 943   }
 944
 945   // Check to see if we can constant propagate this terminator instruction
 946   // away...
 947   Changed |= ConstantFoldTerminator(BB);
 948
 949   // If this is a returning block with only PHI nodes in it, fold the return
 950   // instruction into any unconditional branch predecessors.
 951   //
 952   // If any predecessor is a conditional branch that just selects among
 953   // different return values, fold the replace the branch/return with a select
 954   // and return.
 955   if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
 956     BasicBlock::iterator BBI = BB->getTerminator();
 957     if (BBI == BB->begin() || isa<PHINode>(--BBI)) {
 958       // Find predecessors that end with branches.
 959       std::vector<BasicBlock*> UncondBranchPreds;
 960       std::vector<BranchInst*> CondBranchPreds;
 961       for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 962         TerminatorInst *PTI = (*PI)->getTerminator();
 963         if (BranchInst *BI = dyn_cast<BranchInst>(PTI))
 964           if (BI->isUnconditional())
 965             UncondBranchPreds.push_back(*PI);
 966           else
 967             CondBranchPreds.push_back(BI);
 968       }
 969
 970       // If we found some, do the transformation!
 971       if (!UncondBranchPreds.empty()) {
 972         while (!UncondBranchPreds.empty()) {
 973           BasicBlock *Pred = UncondBranchPreds.back();
 974           UncondBranchPreds.pop_back();
 975           Instruction *UncondBranch = Pred->getTerminator();
 976           // Clone the return and add it to the end of the predecessor.
 977           Instruction *NewRet = RI->clone();
 978           Pred->getInstList().push_back(NewRet);
 979
 980           // If the return instruction returns a value, and if the value was a
 981           // PHI node in "BB", propagate the right value into the return.
 982           if (NewRet->getNumOperands() == 1)
 983             if (PHINode *PN = dyn_cast<PHINode>(NewRet->getOperand(0)))
 984               if (PN->getParent() == BB)
 985                 NewRet->setOperand(0, PN->getIncomingValueForBlock(Pred));
 986           // Update any PHI nodes in the returning block to realize that we no
 987           // longer branch to them.
 988           BB->removePredecessor(Pred);
 989           Pred->getInstList().erase(UncondBranch);
 990         }
 991
 992         // If we eliminated all predecessors of the block, delete the block now.
 993         if (pred_begin(BB) == pred_end(BB))
 994           // We know there are no successors, so just nuke the block.
 995           M->getBasicBlockList().erase(BB);
 996
 997         return true;
 998       }
 999
1000       // Check out all of the conditional branches going to this return
1001       // instruction.  If any of them just select between returns, change the
1002       // branch itself into a select/return pair.
1003       while (!CondBranchPreds.empty()) {
1004         BranchInst *BI = CondBranchPreds.back();
1005         CondBranchPreds.pop_back();
1006         BasicBlock *TrueSucc = BI->getSuccessor(0);
1007         BasicBlock *FalseSucc = BI->getSuccessor(1);
1008         BasicBlock *OtherSucc = TrueSucc == BB ? FalseSucc : TrueSucc;
1009
1010         // Check to see if the non-BB successor is also a return block.
1011         if (isa<ReturnInst>(OtherSucc->getTerminator())) {
1012           // Check to see if there are only PHI instructions in this block.
1013           BasicBlock::iterator OSI = OtherSucc->getTerminator();
1014           if (OSI == OtherSucc->begin() || isa<PHINode>(--OSI)) {
1015             // Okay, we found a branch that is going to two return nodes.  If
1016             // there is no return value for this function, just change the
1017             // branch into a return.
1018             if (RI->getNumOperands() == 0) {
1019               TrueSucc->removePredecessor(BI->getParent());
1020               FalseSucc->removePredecessor(BI->getParent());
1021               new ReturnInst(0, BI);
1022               BI->getParent()->getInstList().erase(BI);
1023               return true;
1024             }
1025
1026             // Otherwise, figure out what the true and false return values are
1027             // so we can insert a new select instruction.
1028             Value *TrueValue = TrueSucc->getTerminator()->getOperand(0);
1029             Value *FalseValue = FalseSucc->getTerminator()->getOperand(0);
1030
1031             // Unwrap any PHI nodes in the return blocks.
1032             if (PHINode *TVPN = dyn_cast<PHINode>(TrueValue))
1033               if (TVPN->getParent() == TrueSucc)
1034                 TrueValue = TVPN->getIncomingValueForBlock(BI->getParent());
1035             if (PHINode *FVPN = dyn_cast<PHINode>(FalseValue))
1036               if (FVPN->getParent() == FalseSucc)
1037                 FalseValue = FVPN->getIncomingValueForBlock(BI->getParent());
1038
1039             TrueSucc->removePredecessor(BI->getParent());
1040             FalseSucc->removePredecessor(BI->getParent());
1041
1042             // Insert a new select instruction.
1043             Value *NewRetVal;
1044             Value *BrCond = BI->getCondition();
1045             if (TrueValue != FalseValue)
1046               NewRetVal = new SelectInst(BrCond, TrueValue,
1047                                          FalseValue, "retval", BI);
1048             else
1049               NewRetVal = TrueValue;
1050
1051             new ReturnInst(NewRetVal, BI);
1052             BI->getParent()->getInstList().erase(BI);
1053             if (BrCond->use_empty())
1054               if (Instruction *BrCondI = dyn_cast<Instruction>(BrCond))
1055                 BrCondI->getParent()->getInstList().erase(BrCondI);
1056             return true;
1057           }
1058         }
1059       }
1060     }
1061   } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->begin())) {
1062     // Check to see if the first instruction in this block is just an unwind.
1063     // If so, replace any invoke instructions which use this as an exception
1064     // destination with call instructions, and any unconditional branch
1065     // predecessor with an unwind.
1066     //
1067     std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB));
1068     while (!Preds.empty()) {
1069       BasicBlock *Pred = Preds.back();
1070       if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator())) {
1071         if (BI->isUnconditional()) {
1072           Pred->getInstList().pop_back();  // nuke uncond branch
1073           new UnwindInst(Pred);            // Use unwind.
1074           Changed = true;
1075         }
1076       } else if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator()))
1077         if (II->getUnwindDest() == BB) {
1078           // Insert a new branch instruction before the invoke, because this
1079           // is now a fall through...
1080           BranchInst *BI = new BranchInst(II->getNormalDest(), II);
1081           Pred->getInstList().remove(II);   // Take out of symbol table
1082
1083           // Insert the call now...
1084           std::vector<Value*> Args(II->op_begin()+3, II->op_end());
1085           CallInst *CI = new CallInst(II->getCalledValue(), Args,
1086                                       II->getName(), BI);
1087           CI->setCallingConv(II->getCallingConv());
1088           // If the invoke produced a value, the Call now does instead
1089           II->replaceAllUsesWith(CI);
1090           delete II;
1091           Changed = true;
1092         }
1093
1094       Preds.pop_back();
1095     }
1096
1097     // If this block is now dead, remove it.
1098     if (pred_begin(BB) == pred_end(BB)) {
1099       // We know there are no successors, so just nuke the block.
1100       M->getBasicBlockList().erase(BB);
1101       return true;
1102     }
1103
1104   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
1105     if (isValueEqualityComparison(SI)) {
1106       // If we only have one predecessor, and if it is a branch on this value,
1107       // see if that predecessor totally determines the outcome of this switch.
1108       if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
1109         if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred))
1110           return SimplifyCFG(BB) || 1;
1111
1112       // If the block only contains the switch, see if we can fold the block
1113       // away into any preds.
1114       if (SI == &BB->front())
1115         if (FoldValueComparisonIntoPredecessors(SI))
1116           return SimplifyCFG(BB) || 1;
1117     }
1118   } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
1119     if (BI->isUnconditional()) {
1120       BasicBlock::iterator BBI = BB->begin();  // Skip over phi nodes...
1121       while (isa<PHINode>(*BBI)) ++BBI;
1122
1123       BasicBlock *Succ = BI->getSuccessor(0);
1124       if (BBI->isTerminator() &&  // Terminator is the only non-phi instruction!
1125           Succ != BB)             // Don't hurt infinite loops!
1126         if (TryToSimplifyUncondBranchFromEmptyBlock(BB, Succ))
1127           return 1;
1128
1129     } else {  // Conditional branch
1130       if (Value *CompVal = isValueEqualityComparison(BI)) {
1131         // If we only have one predecessor, and if it is a branch on this value,
1132         // see if that predecessor totally determines the outcome of this
1133         // switch.
1134         if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
1135           if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred))
1136             return SimplifyCFG(BB) || 1;
1137
1138         // This block must be empty, except for the setcond inst, if it exists.
1139         BasicBlock::iterator I = BB->begin();
1140         if (&*I == BI ||
1141             (&*I == cast<Instruction>(BI->getCondition()) &&
1142              &*++I == BI))
1143           if (FoldValueComparisonIntoPredecessors(BI))
1144             return SimplifyCFG(BB) | true;
1145       }
1146
1147       // If this basic block is ONLY a setcc and a branch, and if a predecessor
1148       // branches to us and one of our successors, fold the setcc into the
1149       // predecessor and use logical operations to pick the right destination.
1150       BasicBlock *TrueDest  = BI->getSuccessor(0);
1151       BasicBlock *FalseDest = BI->getSuccessor(1);
1152       if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(BI->getCondition()))
1153         if (Cond->getParent() == BB && &BB->front() == Cond &&
1154             Cond->getNext() == BI && Cond->hasOneUse() &&
1155             TrueDest != BB && FalseDest != BB)
1156           for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI!=E; ++PI)
1157             if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
1158               if (PBI->isConditional() && SafeToMergeTerminators(BI, PBI)) {
1159                 BasicBlock *PredBlock = *PI;
1160                 if (PBI->getSuccessor(0) == FalseDest ||
1161                     PBI->getSuccessor(1) == TrueDest) {
1162                   // Invert the predecessors condition test (xor it with true),
1163                   // which allows us to write this code once.
1164                   Value *NewCond =
1165                     BinaryOperator::createNot(PBI->getCondition(),
1166                                     PBI->getCondition()->getName()+".not", PBI);
1167                   PBI->setCondition(NewCond);
1168                   BasicBlock *OldTrue = PBI->getSuccessor(0);
1169                   BasicBlock *OldFalse = PBI->getSuccessor(1);
1170                   PBI->setSuccessor(0, OldFalse);
1171                   PBI->setSuccessor(1, OldTrue);
1172                 }
1173
1174                 if (PBI->getSuccessor(0) == TrueDest ||
1175                     PBI->getSuccessor(1) == FalseDest) {
1176                   // Clone Cond into the predecessor basic block, and or/and the
1177                   // two conditions together.
1178                   Instruction *New = Cond->clone();
1179                   New->setName(Cond->getName());
1180                   Cond->setName(Cond->getName()+".old");
1181                   PredBlock->getInstList().insert(PBI, New);
1182                   Instruction::BinaryOps Opcode =
1183                     PBI->getSuccessor(0) == TrueDest ?
1184                     Instruction::Or : Instruction::And;
1185                   Value *NewCond =
1186                     BinaryOperator::create(Opcode, PBI->getCondition(),
1187                                            New, "bothcond", PBI);
1188                   PBI->setCondition(NewCond);
1189                   if (PBI->getSuccessor(0) == BB) {
1190                     AddPredecessorToBlock(TrueDest, PredBlock, BB);
1191                     PBI->setSuccessor(0, TrueDest);
1192                   }
1193                   if (PBI->getSuccessor(1) == BB) {
1194                     AddPredecessorToBlock(FalseDest, PredBlock, BB);
1195                     PBI->setSuccessor(1, FalseDest);
1196                   }
1197                   return SimplifyCFG(BB) | 1;
1198                 }
1199               }
1200
1201       // If this block ends with a branch instruction, and if there is one
1202       // predecessor, see if the previous block ended with a branch on the same
1203       // condition, which makes this conditional branch redundant.
1204       if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
1205         if (BranchInst *PBI = dyn_cast<BranchInst>(OnlyPred->getTerminator()))
1206           if (PBI->isConditional() &&
1207               PBI->getCondition() == BI->getCondition() &&
1208               (PBI->getSuccessor(0) != BB || PBI->getSuccessor(1) != BB)) {
1209             // Okay, the outcome of this conditional branch is statically
1210             // knowable.  Delete the outgoing CFG edge that is impossible to
1211             // execute.
1212             bool CondIsTrue = PBI->getSuccessor(0) == BB;
1213             BI->getSuccessor(CondIsTrue)->removePredecessor(BB);
1214             new BranchInst(BI->getSuccessor(!CondIsTrue), BB);
1215             BB->getInstList().erase(BI);
1216             return SimplifyCFG(BB) | true;
1217           }
1218     }
1219   } else if (isa<UnreachableInst>(BB->getTerminator())) {
1220     // If there are any instructions immediately before the unreachable that can
1221     // be removed, do so.
1222     Instruction *Unreachable = BB->getTerminator();
1223     while (Unreachable != BB->begin()) {
1224       BasicBlock::iterator BBI = Unreachable;
1225       --BBI;
1226       if (isa<CallInst>(BBI)) break;
1227       // Delete this instruction
1228       BB->getInstList().erase(BBI);
1229       Changed = true;
1230     }
1231
1232     // If the unreachable instruction is the first in the block, take a gander
1233     // at all of the predecessors of this instruction, and simplify them.
1234     if (&BB->front() == Unreachable) {
1235       std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB));
1236       for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
1237         TerminatorInst *TI = Preds[i]->getTerminator();
1238
1239         if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1240           if (BI->isUnconditional()) {
1241             if (BI->getSuccessor(0) == BB) {
1242               new UnreachableInst(TI);
1243               TI->eraseFromParent();
1244               Changed = true;
1245             }
1246           } else {
1247             if (BI->getSuccessor(0) == BB) {
1248               new BranchInst(BI->getSuccessor(1), BI);
1249               BI->eraseFromParent();
1250             } else if (BI->getSuccessor(1) == BB) {
1251               new BranchInst(BI->getSuccessor(0), BI);
1252               BI->eraseFromParent();
1253               Changed = true;
1254             }
1255           }
1256         } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
1257           for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i)
1258             if (SI->getSuccessor(i) == BB) {
1259               BB->removePredecessor(SI->getParent());
1260               SI->removeCase(i);
1261               --i; --e;
1262               Changed = true;
1263             }
1264           // If the default value is unreachable, figure out the most popular
1265           // destination and make it the default.
1266           if (SI->getSuccessor(0) == BB) {
1267             std::map<BasicBlock*, unsigned> Popularity;
1268             for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i)
1269               Popularity[SI->getSuccessor(i)]++;
1270
1271             // Find the most popular block.
1272             unsigned MaxPop = 0;
1273             BasicBlock *MaxBlock = 0;
1274             for (std::map<BasicBlock*, unsigned>::iterator
1275                    I = Popularity.begin(), E = Popularity.end(); I != E; ++I) {
1276               if (I->second > MaxPop) {
1277                 MaxPop = I->second;
1278                 MaxBlock = I->first;
1279               }
1280             }
1281             if (MaxBlock) {
1282               // Make this the new default, allowing us to delete any explicit
1283               // edges to it.
1284               SI->setSuccessor(0, MaxBlock);
1285               Changed = true;
1286
1287               // If MaxBlock has phinodes in it, remove MaxPop-1 entries from
1288               // it.
1289               if (isa<PHINode>(MaxBlock->begin()))
1290                 for (unsigned i = 0; i != MaxPop-1; ++i)
1291                   MaxBlock->removePredecessor(SI->getParent());
1292
1293               for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i)
1294                 if (SI->getSuccessor(i) == MaxBlock) {
1295                   SI->removeCase(i);
1296                   --i; --e;
1297                 }
1298             }
1299           }
1300         } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
1301           if (II->getUnwindDest() == BB) {
1302             // Convert the invoke to a call instruction.  This would be a good
1303             // place to note that the call does not throw though.
1304             BranchInst *BI = new BranchInst(II->getNormalDest(), II);
1305             II->removeFromParent();   // Take out of symbol table
1306
1307             // Insert the call now...
1308             std::vector<Value*> Args(II->op_begin()+3, II->op_end());
1309             CallInst *CI = new CallInst(II->getCalledValue(), Args,
1310                                         II->getName(), BI);
1311             CI->setCallingConv(II->getCallingConv());
1312             // If the invoke produced a value, the Call does now instead.
1313             II->replaceAllUsesWith(CI);
1314             delete II;
1315             Changed = true;
1316           }
1317         }
1318       }
1319
1320       // If this block is now dead, remove it.
1321       if (pred_begin(BB) == pred_end(BB)) {
1322         // We know there are no successors, so just nuke the block.
1323         M->getBasicBlockList().erase(BB);
1324         return true;
1325       }
1326     }
1327   }
1328
1329   // Merge basic blocks into their predecessor if there is only one distinct
1330   // pred, and if there is only one distinct successor of the predecessor, and
1331   // if there are no PHI nodes.
1332   //
1333   pred_iterator PI(pred_begin(BB)), PE(pred_end(BB));
1334   BasicBlock *OnlyPred = *PI++;
1335   for (; PI != PE; ++PI)  // Search all predecessors, see if they are all same
1336     if (*PI != OnlyPred) {
1337       OnlyPred = 0;       // There are multiple different predecessors...
1338       break;
1339     }
1340
1341   BasicBlock *OnlySucc = 0;
1342   if (OnlyPred && OnlyPred != BB &&    // Don't break self loops
1343       OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) {
1344     // Check to see if there is only one distinct successor...
1345     succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred));
1346     OnlySucc = BB;
1347     for (; SI != SE; ++SI)
1348       if (*SI != OnlySucc) {
1349         OnlySucc = 0;     // There are multiple distinct successors!
1350         break;
1351       }
1352   }
1353
1354   if (OnlySucc) {
1355     DEBUG(std::cerr << "Merging: " << *BB << "into: " << *OnlyPred);
1356     TerminatorInst *Term = OnlyPred->getTerminator();
1357
1358     // Resolve any PHI nodes at the start of the block.  They are all
1359     // guaranteed to have exactly one entry if they exist, unless there are
1360     // multiple duplicate (but guaranteed to be equal) entries for the
1361     // incoming edges.  This occurs when there are multiple edges from
1362     // OnlyPred to OnlySucc.
1363     //
1364     while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
1365       PN->replaceAllUsesWith(PN->getIncomingValue(0));
1366       BB->getInstList().pop_front();  // Delete the phi node...
1367     }
1368
1369     // Delete the unconditional branch from the predecessor...
1370     OnlyPred->getInstList().pop_back();
1371
1372     // Move all definitions in the successor to the predecessor...
1373     OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
1374
1375     // Make all PHI nodes that referred to BB now refer to Pred as their
1376     // source...
1377     BB->replaceAllUsesWith(OnlyPred);
1378
1379     std::string OldName = BB->getName();
1380
1381     // Erase basic block from the function...
1382     M->getBasicBlockList().erase(BB);
1383
1384     // Inherit predecessors name if it exists...
1385     if (!OldName.empty() && !OnlyPred->hasName())
1386       OnlyPred->setName(OldName);
1387
1388     return true;
1389   }
1390
1391   // Otherwise, if this block only has a single predecessor, and if that block
1392   // is a conditional branch, see if we can hoist any code from this block up
1393   // into our predecessor.
1394   if (OnlyPred)
1395     if (BranchInst *BI = dyn_cast<BranchInst>(OnlyPred->getTerminator()))
1396       if (BI->isConditional()) {
1397         // Get the other block.
1398         BasicBlock *OtherBB = BI->getSuccessor(BI->getSuccessor(0) == BB);
1399         PI = pred_begin(OtherBB);
1400         ++PI;
1401         if (PI == pred_end(OtherBB)) {
1402           // We have a conditional branch to two blocks that are only reachable
1403           // from the condbr.  We know that the condbr dominates the two blocks,
1404           // so see if there is any identical code in the "then" and "else"
1405           // blocks.  If so, we can hoist it up to the branching block.
1406           Changed |= HoistThenElseCodeToIf(BI);
1407         }
1408       }
1409
1410   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
1411     if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator()))
1412       // Change br (X == 0 | X == 1), T, F into a switch instruction.
1413       if (BI->isConditional() && isa<Instruction>(BI->getCondition())) {
1414         Instruction *Cond = cast<Instruction>(BI->getCondition());
1415         // If this is a bunch of seteq's or'd together, or if it's a bunch of
1416         // 'setne's and'ed together, collect them.
1417         Value *CompVal = 0;
1418         std::vector<ConstantInt*> Values;
1419         bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values);
1420         if (CompVal && CompVal->getType()->isInteger()) {
1421           // There might be duplicate constants in the list, which the switch
1422           // instruction can't handle, remove them now.
1423           std::sort(Values.begin(), Values.end(), ConstantIntOrdering());
1424           Values.erase(std::unique(Values.begin(), Values.end()), Values.end());
1425
1426           // Figure out which block is which destination.
1427           BasicBlock *DefaultBB = BI->getSuccessor(1);
1428           BasicBlock *EdgeBB    = BI->getSuccessor(0);
1429           if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB);
1430
1431           // Create the new switch instruction now.
1432           SwitchInst *New = new SwitchInst(CompVal, DefaultBB,Values.size(),BI);
1433
1434           // Add all of the 'cases' to the switch instruction.
1435           for (unsigned i = 0, e = Values.size(); i != e; ++i)
1436             New->addCase(Values[i], EdgeBB);
1437
1438           // We added edges from PI to the EdgeBB.  As such, if there were any
1439           // PHI nodes in EdgeBB, they need entries to be added corresponding to
1440           // the number of edges added.
1441           for (BasicBlock::iterator BBI = EdgeBB->begin();
1442                isa<PHINode>(BBI); ++BBI) {
1443             PHINode *PN = cast<PHINode>(BBI);
1444             Value *InVal = PN->getIncomingValueForBlock(*PI);
1445             for (unsigned i = 0, e = Values.size()-1; i != e; ++i)
1446               PN->addIncoming(InVal, *PI);
1447           }
1448
1449           // Erase the old branch instruction.
1450           (*PI)->getInstList().erase(BI);
1451
1452           // Erase the potentially condition tree that was used to computed the
1453           // branch condition.
1454           ErasePossiblyDeadInstructionTree(Cond);
1455           return true;
1456         }
1457       }
1458
1459   // If there is a trivial two-entry PHI node in this basic block, and we can
1460   // eliminate it, do so now.
1461   if (PHINode *PN = dyn_cast<PHINode>(BB->begin()))
1462     if (PN->getNumIncomingValues() == 2) {
1463       // Ok, this is a two entry PHI node.  Check to see if this is a simple "if
1464       // statement", which has a very simple dominance structure.  Basically, we
1465       // are trying to find the condition that is being branched on, which
1466       // subsequently causes this merge to happen.  We really want control
1467       // dependence information for this check, but simplifycfg can't keep it up
1468       // to date, and this catches most of the cases we care about anyway.
1469       //
1470       BasicBlock *IfTrue, *IfFalse;
1471       if (Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse)) {
1472         DEBUG(std::cerr << "FOUND IF CONDITION!  " << *IfCond << "  T: "
1473               << IfTrue->getName() << "  F: " << IfFalse->getName() << "\n");
1474
1475         // Loop over the PHI's seeing if we can promote them all to select
1476         // instructions.  While we are at it, keep track of the instructions
1477         // that need to be moved to the dominating block.
1478         std::set<Instruction*> AggressiveInsts;
1479         bool CanPromote = true;
1480
1481         BasicBlock::iterator AfterPHIIt = BB->begin();
1482         while (isa<PHINode>(AfterPHIIt)) {
1483           PHINode *PN = cast<PHINode>(AfterPHIIt++);
1484           if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) {
1485             if (PN->getIncomingValue(0) != PN)
1486               PN->replaceAllUsesWith(PN->getIncomingValue(0));
1487             else
1488               PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
1489           } else if (!DominatesMergePoint(PN->getIncomingValue(0), BB,
1490                                           &AggressiveInsts) ||
1491                      !DominatesMergePoint(PN->getIncomingValue(1), BB,
1492                                           &AggressiveInsts)) {
1493             CanPromote = false;
1494             break;
1495           }
1496         }
1497
1498         // Did we eliminate all PHI's?
1499         CanPromote |= AfterPHIIt == BB->begin();
1500
1501         // If we all PHI nodes are promotable, check to make sure that all
1502         // instructions in the predecessor blocks can be promoted as well.  If
1503         // not, we won't be able to get rid of the control flow, so it's not
1504         // worth promoting to select instructions.
1505         BasicBlock *DomBlock = 0, *IfBlock1 = 0, *IfBlock2 = 0;
1506         if (CanPromote) {
1507           PN = cast<PHINode>(BB->begin());
1508           BasicBlock *Pred = PN->getIncomingBlock(0);
1509           if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) {
1510             IfBlock1 = Pred;
1511             DomBlock = *pred_begin(Pred);
1512             for (BasicBlock::iterator I = Pred->begin();
1513                  !isa<TerminatorInst>(I); ++I)
1514               if (!AggressiveInsts.count(I)) {
1515                 // This is not an aggressive instruction that we can promote.
1516                 // Because of this, we won't be able to get rid of the control
1517                 // flow, so the xform is not worth it.
1518                 CanPromote = false;
1519                 break;
1520               }
1521           }
1522
1523           Pred = PN->getIncomingBlock(1);
1524           if (CanPromote &&
1525               cast<BranchInst>(Pred->getTerminator())->isUnconditional()) {
1526             IfBlock2 = Pred;
1527             DomBlock = *pred_begin(Pred);
1528             for (BasicBlock::iterator I = Pred->begin();
1529                  !isa<TerminatorInst>(I); ++I)
1530               if (!AggressiveInsts.count(I)) {
1531                 // This is not an aggressive instruction that we can promote.
1532                 // Because of this, we won't be able to get rid of the control
1533                 // flow, so the xform is not worth it.
1534                 CanPromote = false;
1535                 break;
1536               }
1537           }
1538         }
1539
1540         // If we can still promote the PHI nodes after this gauntlet of tests,
1541         // do all of the PHI's now.
1542         if (CanPromote) {
1543           // Move all 'aggressive' instructions, which are defined in the
1544           // conditional parts of the if's up to the dominating block.
1545           if (IfBlock1) {
1546             DomBlock->getInstList().splice(DomBlock->getTerminator(),
1547                                            IfBlock1->getInstList(),
1548                                            IfBlock1->begin(),
1549                                            IfBlock1->getTerminator());
1550           }
1551           if (IfBlock2) {
1552             DomBlock->getInstList().splice(DomBlock->getTerminator(),
1553                                            IfBlock2->getInstList(),
1554                                            IfBlock2->begin(),
1555                                            IfBlock2->getTerminator());
1556           }
1557
1558           while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
1559             // Change the PHI node into a select instruction.
1560             Value *TrueVal =
1561               PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse);
1562             Value *FalseVal =
1563               PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue);
1564
1565             std::string Name = PN->getName(); PN->setName("");
1566             PN->replaceAllUsesWith(new SelectInst(IfCond, TrueVal, FalseVal,
1567                                                   Name, AfterPHIIt));
1568             BB->getInstList().erase(PN);
1569           }
1570           Changed = true;
1571         }
1572       }
1573     }
1574
1575   return Changed;
1576 }