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 // PropagatePredecessorsForPHIs - This gets "Succ" ready to have the
  28 // predecessors from "BB".  This is a little tricky because "Succ" has PHI
  29 // nodes, which need to have extra slots added to them to hold the merge edges
  30 // from BB's predecessors, and BB itself might have had PHI nodes in it.  This
  31 // function returns true (failure) if the Succ BB already has a predecessor that
  32 // is a predecessor of BB and incoming PHI arguments would not be discernible.
  33 //
  34 // Assumption: Succ is the single successor for BB.
  35 //
  36 static bool PropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
  37   assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
  38
  39   if (!isa<PHINode>(Succ->front()))
  40     return false;  // We can make the transformation, no problem.
  41
  42   // If there is more than one predecessor, and there are PHI nodes in
  43   // the successor, then we need to add incoming edges for the PHI nodes
  44   //
  45   const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB));
  46
  47   // Check to see if one of the predecessors of BB is already a predecessor of
  48   // Succ.  If so, we cannot do the transformation if there are any PHI nodes
  49   // with incompatible values coming in from the two edges!
  50   //
  51   for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); PI != PE; ++PI)
  52     if (std::find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) {
  53       // Loop over all of the PHI nodes checking to see if there are
  54       // incompatible values coming in.
  55       for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
  56         PHINode *PN = cast<PHINode>(I);
  57         // Loop up the entries in the PHI node for BB and for *PI if the values
  58         // coming in are non-equal, we cannot merge these two blocks (instead we
  59         // should insert a conditional move or something, then merge the
  60         // blocks).
  61         int Idx1 = PN->getBasicBlockIndex(BB);
  62         int Idx2 = PN->getBasicBlockIndex(*PI);
  63         assert(Idx1 != -1 && Idx2 != -1 &&
  64                "Didn't have entries for my predecessors??");
  65         if (PN->getIncomingValue(Idx1) != PN->getIncomingValue(Idx2))
  66           return true;  // Values are not equal...
  67       }
  68     }
  69
  70   // Loop over all of the PHI nodes in the successor BB.
  71   for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
  72     PHINode *PN = cast<PHINode>(I);
  73     Value *OldVal = PN->removeIncomingValue(BB, false);
  74     assert(OldVal && "No entry in PHI for Pred BB!");
  75
  76     // If this incoming value is one of the PHI nodes in BB, the new entries in
  77     // the PHI node are the entries from the old PHI.
  78     if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
  79       PHINode *OldValPN = cast<PHINode>(OldVal);
  80       for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i)
  81         PN->addIncoming(OldValPN->getIncomingValue(i),
  82                         OldValPN->getIncomingBlock(i));
  83     } else {
  84       for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(),
  85              End = BBPreds.end(); PredI != End; ++PredI) {
  86         // Add an incoming value for each of the new incoming values...
  87         PN->addIncoming(OldVal, *PredI);
  88       }
  89     }
  90   }
  91   return false;
  92 }
  93
  94 /// GetIfCondition - Given a basic block (BB) with two predecessors (and
  95 /// presumably PHI nodes in it), check to see if the merge at this block is due
  96 /// to an "if condition".  If so, return the boolean condition that determines
  97 /// which entry into BB will be taken.  Also, return by references the block
  98 /// that will be entered from if the condition is true, and the block that will
  99 /// be entered if the condition is false.
 100 ///
 101 ///
 102 static Value *GetIfCondition(BasicBlock *BB,
 103                              BasicBlock *&IfTrue, BasicBlock *&IfFalse) {
 104   assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 &&
 105          "Function can only handle blocks with 2 predecessors!");
 106   BasicBlock *Pred1 = *pred_begin(BB);
 107   BasicBlock *Pred2 = *++pred_begin(BB);
 108
 109   // We can only handle branches.  Other control flow will be lowered to
 110   // branches if possible anyway.
 111   if (!isa<BranchInst>(Pred1->getTerminator()) ||
 112       !isa<BranchInst>(Pred2->getTerminator()))
 113     return 0;
 114   BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator());
 115   BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator());
 116
 117   // Eliminate code duplication by ensuring that Pred1Br is conditional if
 118   // either are.
 119   if (Pred2Br->isConditional()) {
 120     // If both branches are conditional, we don't have an "if statement".  In
 121     // reality, we could transform this case, but since the condition will be
 122     // required anyway, we stand no chance of eliminating it, so the xform is
 123     // probably not profitable.
 124     if (Pred1Br->isConditional())
 125       return 0;
 126
 127     std::swap(Pred1, Pred2);
 128     std::swap(Pred1Br, Pred2Br);
 129   }
 130
 131   if (Pred1Br->isConditional()) {
 132     // If we found a conditional branch predecessor, make sure that it branches
 133     // to BB and Pred2Br.  If it doesn't, this isn't an "if statement".
 134     if (Pred1Br->getSuccessor(0) == BB &&
 135         Pred1Br->getSuccessor(1) == Pred2) {
 136       IfTrue = Pred1;
 137       IfFalse = Pred2;
 138     } else if (Pred1Br->getSuccessor(0) == Pred2 &&
 139                Pred1Br->getSuccessor(1) == BB) {
 140       IfTrue = Pred2;
 141       IfFalse = Pred1;
 142     } else {
 143       // We know that one arm of the conditional goes to BB, so the other must
 144       // go somewhere unrelated, and this must not be an "if statement".
 145       return 0;
 146     }
 147
 148     // The only thing we have to watch out for here is to make sure that Pred2
 149     // doesn't have incoming edges from other blocks.  If it does, the condition
 150     // doesn't dominate BB.
 151     if (++pred_begin(Pred2) != pred_end(Pred2))
 152       return 0;
 153
 154     return Pred1Br->getCondition();
 155   }
 156
 157   // Ok, if we got here, both predecessors end with an unconditional branch to
 158   // BB.  Don't panic!  If both blocks only have a single (identical)
 159   // predecessor, and THAT is a conditional branch, then we're all ok!
 160   if (pred_begin(Pred1) == pred_end(Pred1) ||
 161       ++pred_begin(Pred1) != pred_end(Pred1) ||
 162       pred_begin(Pred2) == pred_end(Pred2) ||
 163       ++pred_begin(Pred2) != pred_end(Pred2) ||
 164       *pred_begin(Pred1) != *pred_begin(Pred2))
 165     return 0;
 166
 167   // Otherwise, if this is a conditional branch, then we can use it!
 168   BasicBlock *CommonPred = *pred_begin(Pred1);
 169   if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) {
 170     assert(BI->isConditional() && "Two successors but not conditional?");
 171     if (BI->getSuccessor(0) == Pred1) {
 172       IfTrue = Pred1;
 173       IfFalse = Pred2;
 174     } else {
 175       IfTrue = Pred2;
 176       IfFalse = Pred1;
 177     }
 178     return BI->getCondition();
 179   }
 180   return 0;
 181 }
 182
 183
 184 // If we have a merge point of an "if condition" as accepted above, return true
 185 // if the specified value dominates the block.  We don't handle the true
 186 // generality of domination here, just a special case which works well enough
 187 // for us.
 188 //
 189 // If AggressiveInsts is non-null, and if V does not dominate BB, we check to
 190 // see if V (which must be an instruction) is cheap to compute and is
 191 // non-trapping.  If both are true, the instruction is inserted into the set and
 192 // true is returned.
 193 static bool DominatesMergePoint(Value *V, BasicBlock *BB,
 194                                 std::set<Instruction*> *AggressiveInsts) {
 195   Instruction *I = dyn_cast<Instruction>(V);
 196   if (!I) return true;    // Non-instructions all dominate instructions.
 197   BasicBlock *PBB = I->getParent();
 198
 199   // We don't want to allow wierd loops that might have the "if condition" in
 200   // the bottom of this block.
 201   if (PBB == BB) return false;
 202
 203   // If this instruction is defined in a block that contains an unconditional
 204   // branch to BB, then it must be in the 'conditional' part of the "if
 205   // statement".
 206   if (BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator()))
 207     if (BI->isUnconditional() && BI->getSuccessor(0) == BB) {
 208       if (!AggressiveInsts) return false;
 209       // Okay, it looks like the instruction IS in the "condition".  Check to
 210       // see if its a cheap instruction to unconditionally compute, and if it
 211       // only uses stuff defined outside of the condition.  If so, hoist it out.
 212       switch (I->getOpcode()) {
 213       default: return false;  // Cannot hoist this out safely.
 214       case Instruction::Load:
 215         // We can hoist loads that are non-volatile and obviously cannot trap.
 216         if (cast<LoadInst>(I)->isVolatile())
 217           return false;
 218         if (!isa<AllocaInst>(I->getOperand(0)) &&
 219             !isa<Constant>(I->getOperand(0)))
 220           return false;
 221
 222         // Finally, we have to check to make sure there are no instructions
 223         // before the load in its basic block, as we are going to hoist the loop
 224         // out to its predecessor.
 225         if (PBB->begin() != BasicBlock::iterator(I))
 226           return false;
 227         break;
 228       case Instruction::Add:
 229       case Instruction::Sub:
 230       case Instruction::And:
 231       case Instruction::Or:
 232       case Instruction::Xor:
 233       case Instruction::Shl:
 234       case Instruction::Shr:
 235         break;   // These are all cheap and non-trapping instructions.
 236       }
 237
 238       // Okay, we can only really hoist these out if their operands are not
 239       // defined in the conditional region.
 240       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 241         if (!DominatesMergePoint(I->getOperand(i), BB, 0))
 242           return false;
 243       // Okay, it's safe to do this!  Remember this instruction.
 244       AggressiveInsts->insert(I);
 245     }
 246
 247   return true;
 248 }
 249
 250 // GatherConstantSetEQs - Given a potentially 'or'd together collection of seteq
 251 // instructions that compare a value against a constant, return the value being
 252 // compared, and stick the constant into the Values vector.
 253 static Value *GatherConstantSetEQs(Value *V, std::vector<ConstantInt*> &Values){
 254   if (Instruction *Inst = dyn_cast<Instruction>(V))
 255     if (Inst->getOpcode() == Instruction::SetEQ) {
 256       if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) {
 257         Values.push_back(C);
 258         return Inst->getOperand(0);
 259       } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) {
 260         Values.push_back(C);
 261         return Inst->getOperand(1);
 262       }
 263     } else if (Inst->getOpcode() == Instruction::Or) {
 264       if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values))
 265         if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values))
 266           if (LHS == RHS)
 267             return LHS;
 268     }
 269   return 0;
 270 }
 271
 272 // GatherConstantSetNEs - Given a potentially 'and'd together collection of
 273 // setne instructions that compare a value against a constant, return the value
 274 // being compared, and stick the constant into the Values vector.
 275 static Value *GatherConstantSetNEs(Value *V, std::vector<ConstantInt*> &Values){
 276   if (Instruction *Inst = dyn_cast<Instruction>(V))
 277     if (Inst->getOpcode() == Instruction::SetNE) {
 278       if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) {
 279         Values.push_back(C);
 280         return Inst->getOperand(0);
 281       } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) {
 282         Values.push_back(C);
 283         return Inst->getOperand(1);
 284       }
 285     } else if (Inst->getOpcode() == Instruction::Cast) {
 286       // Cast of X to bool is really a comparison against zero.
 287       assert(Inst->getType() == Type::BoolTy && "Can only handle bool values!");
 288       Values.push_back(ConstantInt::get(Inst->getOperand(0)->getType(), 0));
 289       return Inst->getOperand(0);
 290     } else if (Inst->getOpcode() == Instruction::And) {
 291       if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values))
 292         if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values))
 293           if (LHS == RHS)
 294             return LHS;
 295     }
 296   return 0;
 297 }
 298
 299
 300
 301 /// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a
 302 /// bunch of comparisons of one value against constants, return the value and
 303 /// the constants being compared.
 304 static bool GatherValueComparisons(Instruction *Cond, Value *&CompVal,
 305                                    std::vector<ConstantInt*> &Values) {
 306   if (Cond->getOpcode() == Instruction::Or) {
 307     CompVal = GatherConstantSetEQs(Cond, Values);
 308
 309     // Return true to indicate that the condition is true if the CompVal is
 310     // equal to one of the constants.
 311     return true;
 312   } else if (Cond->getOpcode() == Instruction::And) {
 313     CompVal = GatherConstantSetNEs(Cond, Values);
 314
 315     // Return false to indicate that the condition is false if the CompVal is
 316     // equal to one of the constants.
 317     return false;
 318   }
 319   return false;
 320 }
 321
 322 /// ErasePossiblyDeadInstructionTree - If the specified instruction is dead and
 323 /// has no side effects, nuke it.  If it uses any instructions that become dead
 324 /// because the instruction is now gone, nuke them too.
 325 static void ErasePossiblyDeadInstructionTree(Instruction *I) {
 326   if (isInstructionTriviallyDead(I)) {
 327     std::vector<Value*> Operands(I->op_begin(), I->op_end());
 328     I->getParent()->getInstList().erase(I);
 329     for (unsigned i = 0, e = Operands.size(); i != e; ++i)
 330       if (Instruction *OpI = dyn_cast<Instruction>(Operands[i]))
 331         ErasePossiblyDeadInstructionTree(OpI);
 332   }
 333 }
 334
 335 /// SafeToMergeTerminators - Return true if it is safe to merge these two
 336 /// terminator instructions together.
 337 ///
 338 static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) {
 339   if (SI1 == SI2) return false;  // Can't merge with self!
 340
 341   // It is not safe to merge these two switch instructions if they have a common
 342   // successor, and if that successor has a PHI node, and if *that* PHI node has
 343   // conflicting incoming values from the two switch blocks.
 344   BasicBlock *SI1BB = SI1->getParent();
 345   BasicBlock *SI2BB = SI2->getParent();
 346   std::set<BasicBlock*> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
 347
 348   for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I)
 349     if (SI1Succs.count(*I))
 350       for (BasicBlock::iterator BBI = (*I)->begin();
 351            isa<PHINode>(BBI); ++BBI) {
 352         PHINode *PN = cast<PHINode>(BBI);
 353         if (PN->getIncomingValueForBlock(SI1BB) !=
 354             PN->getIncomingValueForBlock(SI2BB))
 355           return false;
 356       }
 357
 358   return true;
 359 }
 360
 361 /// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will
 362 /// now be entries in it from the 'NewPred' block.  The values that will be
 363 /// flowing into the PHI nodes will be the same as those coming in from
 364 /// ExistPred, an existing predecessor of Succ.
 365 static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred,
 366                                   BasicBlock *ExistPred) {
 367   assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) !=
 368          succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!");
 369   if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do
 370
 371   for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
 372     PHINode *PN = cast<PHINode>(I);
 373     Value *V = PN->getIncomingValueForBlock(ExistPred);
 374     PN->addIncoming(V, NewPred);
 375   }
 376 }
 377
 378 // isValueEqualityComparison - Return true if the specified terminator checks to
 379 // see if a value is equal to constant integer value.
 380 static Value *isValueEqualityComparison(TerminatorInst *TI) {
 381   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 382     // Do not permit merging of large switch instructions into their
 383     // predecessors unless there is only one predecessor.
 384     if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()),
 385                                                pred_end(SI->getParent())) > 128)
 386       return 0;
 387
 388     return SI->getCondition();
 389   }
 390   if (BranchInst *BI = dyn_cast<BranchInst>(TI))
 391     if (BI->isConditional() && BI->getCondition()->hasOneUse())
 392       if (SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition()))
 393         if ((SCI->getOpcode() == Instruction::SetEQ ||
 394              SCI->getOpcode() == Instruction::SetNE) &&
 395             isa<ConstantInt>(SCI->getOperand(1)))
 396           return SCI->getOperand(0);
 397   return 0;
 398 }
 399
 400 // Given a value comparison instruction, decode all of the 'cases' that it
 401 // represents and return the 'default' block.
 402 static BasicBlock *
 403 GetValueEqualityComparisonCases(TerminatorInst *TI,
 404                                 std::vector<std::pair<ConstantInt*,
 405                                                       BasicBlock*> > &Cases) {
 406   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 407     Cases.reserve(SI->getNumCases());
 408     for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i)
 409       Cases.push_back(std::make_pair(cast<ConstantInt>(SI->getCaseValue(i)),
 410                                      SI->getSuccessor(i)));
 411     return SI->getDefaultDest();
 412   }
 413
 414   BranchInst *BI = cast<BranchInst>(TI);
 415   SetCondInst *SCI = cast<SetCondInst>(BI->getCondition());
 416   Cases.push_back(std::make_pair(cast<ConstantInt>(SCI->getOperand(1)),
 417                                  BI->getSuccessor(SCI->getOpcode() ==
 418                                                         Instruction::SetNE)));
 419   return BI->getSuccessor(SCI->getOpcode() == Instruction::SetEQ);
 420 }
 421
 422
 423 // FoldValueComparisonIntoPredecessors - The specified terminator is a value
 424 // equality comparison instruction (either a switch or a branch on "X == c").
 425 // See if any of the predecessors of the terminator block are value comparisons
 426 // on the same value.  If so, and if safe to do so, fold them together.
 427 static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) {
 428   BasicBlock *BB = TI->getParent();
 429   Value *CV = isValueEqualityComparison(TI);  // CondVal
 430   assert(CV && "Not a comparison?");
 431   bool Changed = false;
 432
 433   std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB));
 434   while (!Preds.empty()) {
 435     BasicBlock *Pred = Preds.back();
 436     Preds.pop_back();
 437
 438     // See if the predecessor is a comparison with the same value.
 439     TerminatorInst *PTI = Pred->getTerminator();
 440     Value *PCV = isValueEqualityComparison(PTI);  // PredCondVal
 441
 442     if (PCV == CV && SafeToMergeTerminators(TI, PTI)) {
 443       // Figure out which 'cases' to copy from SI to PSI.
 444       std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases;
 445       BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
 446
 447       std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases;
 448       BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
 449
 450       // Based on whether the default edge from PTI goes to BB or not, fill in
 451       // PredCases and PredDefault with the new switch cases we would like to
 452       // build.
 453       std::vector<BasicBlock*> NewSuccessors;
 454
 455       if (PredDefault == BB) {
 456         // If this is the default destination from PTI, only the edges in TI
 457         // that don't occur in PTI, or that branch to BB will be activated.
 458         std::set<ConstantInt*> PTIHandled;
 459         for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
 460           if (PredCases[i].second != BB)
 461             PTIHandled.insert(PredCases[i].first);
 462           else {
 463             // The default destination is BB, we don't need explicit targets.
 464             std::swap(PredCases[i], PredCases.back());
 465             PredCases.pop_back();
 466             --i; --e;
 467           }
 468
 469         // Reconstruct the new switch statement we will be building.
 470         if (PredDefault != BBDefault) {
 471           PredDefault->removePredecessor(Pred);
 472           PredDefault = BBDefault;
 473           NewSuccessors.push_back(BBDefault);
 474         }
 475         for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
 476           if (!PTIHandled.count(BBCases[i].first) &&
 477               BBCases[i].second != BBDefault) {
 478             PredCases.push_back(BBCases[i]);
 479             NewSuccessors.push_back(BBCases[i].second);
 480           }
 481
 482       } else {
 483         // If this is not the default destination from PSI, only the edges
 484         // in SI that occur in PSI with a destination of BB will be
 485         // activated.
 486         std::set<ConstantInt*> PTIHandled;
 487         for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
 488           if (PredCases[i].second == BB) {
 489             PTIHandled.insert(PredCases[i].first);
 490             std::swap(PredCases[i], PredCases.back());
 491             PredCases.pop_back();
 492             --i; --e;
 493           }
 494
 495         // Okay, now we know which constants were sent to BB from the
 496         // predecessor.  Figure out where they will all go now.
 497         for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
 498           if (PTIHandled.count(BBCases[i].first)) {
 499             // If this is one we are capable of getting...
 500             PredCases.push_back(BBCases[i]);
 501             NewSuccessors.push_back(BBCases[i].second);
 502             PTIHandled.erase(BBCases[i].first);// This constant is taken care of
 503           }
 504
 505         // If there are any constants vectored to BB that TI doesn't handle,
 506         // they must go to the default destination of TI.
 507         for (std::set<ConstantInt*>::iterator I = PTIHandled.begin(),
 508                E = PTIHandled.end(); I != E; ++I) {
 509           PredCases.push_back(std::make_pair(*I, BBDefault));
 510           NewSuccessors.push_back(BBDefault);
 511         }
 512       }
 513
 514       // Okay, at this point, we know which new successor Pred will get.  Make
 515       // sure we update the number of entries in the PHI nodes for these
 516       // successors.
 517       for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i)
 518         AddPredecessorToBlock(NewSuccessors[i], Pred, BB);
 519
 520       // Now that the successors are updated, create the new Switch instruction.
 521       SwitchInst *NewSI = new SwitchInst(CV, PredDefault, PTI);
 522       for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
 523         NewSI->addCase(PredCases[i].first, PredCases[i].second);
 524       Pred->getInstList().erase(PTI);
 525
 526       // Okay, last check.  If BB is still a successor of PSI, then we must
 527       // have an infinite loop case.  If so, add an infinitely looping block
 528       // to handle the case to preserve the behavior of the code.
 529       BasicBlock *InfLoopBlock = 0;
 530       for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i)
 531         if (NewSI->getSuccessor(i) == BB) {
 532           if (InfLoopBlock == 0) {
 533             // Insert it at the end of the loop, because it's either code,
 534             // or it won't matter if it's hot. :)
 535             InfLoopBlock = new BasicBlock("infloop", BB->getParent());
 536             new BranchInst(InfLoopBlock, InfLoopBlock);
 537           }
 538           NewSI->setSuccessor(i, InfLoopBlock);
 539         }
 540
 541       Changed = true;
 542     }
 543   }
 544   return Changed;
 545 }
 546
 547 namespace {
 548   /// ConstantIntOrdering - This class implements a stable ordering of constant
 549   /// integers that does not depend on their address.  This is important for
 550   /// applications that sort ConstantInt's to ensure uniqueness.
 551   struct ConstantIntOrdering {
 552     bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const {
 553       return LHS->getRawValue() < RHS->getRawValue();
 554     }
 555   };
 556 }
 557
 558
 559 // SimplifyCFG - This function is used to do simplification of a CFG.  For
 560 // example, it adjusts branches to branches to eliminate the extra hop, it
 561 // eliminates unreachable basic blocks, and does other "peephole" optimization
 562 // of the CFG.  It returns true if a modification was made.
 563 //
 564 // WARNING:  The entry node of a function may not be simplified.
 565 //
 566 bool llvm::SimplifyCFG(BasicBlock *BB) {
 567   bool Changed = false;
 568   Function *M = BB->getParent();
 569
 570   assert(BB && BB->getParent() && "Block not embedded in function!");
 571   assert(BB->getTerminator() && "Degenerate basic block encountered!");
 572   assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!");
 573
 574   // Remove basic blocks that have no predecessors... which are unreachable.
 575   if (pred_begin(BB) == pred_end(BB) ||
 576       *pred_begin(BB) == BB && ++pred_begin(BB) == pred_end(BB)) {
 577     DEBUG(std::cerr << "Removing BB: \n" << *BB);
 578
 579     // Loop through all of our successors and make sure they know that one
 580     // of their predecessors is going away.
 581     for_each(succ_begin(BB), succ_end(BB),
 582              std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB));
 583
 584     while (!BB->empty()) {
 585       Instruction &I = BB->back();
 586       // If this instruction is used, replace uses with an arbitrary
 587       // constant value.  Because control flow can't get here, we don't care
 588       // what we replace the value with.  Note that since this block is
 589       // unreachable, and all values contained within it must dominate their
 590       // uses, that all uses will eventually be removed.
 591       if (!I.use_empty())
 592         // Make all users of this instruction reference the constant instead
 593         I.replaceAllUsesWith(Constant::getNullValue(I.getType()));
 594
 595       // Remove the instruction from the basic block
 596       BB->getInstList().pop_back();
 597     }
 598     M->getBasicBlockList().erase(BB);
 599     return true;
 600   }
 601
 602   // Check to see if we can constant propagate this terminator instruction
 603   // away...
 604   Changed |= ConstantFoldTerminator(BB);
 605
 606   // Check to see if this block has no non-phi instructions and only a single
 607   // successor.  If so, replace references to this basic block with references
 608   // to the successor.
 609   succ_iterator SI(succ_begin(BB));
 610   if (SI != succ_end(BB) && ++SI == succ_end(BB)) {  // One succ?
 611
 612     BasicBlock::iterator BBI = BB->begin();  // Skip over phi nodes...
 613     while (isa<PHINode>(*BBI)) ++BBI;
 614
 615     if (BBI->isTerminator()) {   // Terminator is the only non-phi instruction!
 616       BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor
 617
 618       if (Succ != BB) {   // Arg, don't hurt infinite loops!
 619         // If our successor has PHI nodes, then we need to update them to
 620         // include entries for BB's predecessors, not for BB itself.
 621         // Be careful though, if this transformation fails (returns true) then
 622         // we cannot do this transformation!
 623         //
 624         if (!PropagatePredecessorsForPHIs(BB, Succ)) {
 625           DEBUG(std::cerr << "Killing Trivial BB: \n" << *BB);
 626           std::string OldName = BB->getName();
 627
 628           std::vector<BasicBlock*>
 629             OldSuccPreds(pred_begin(Succ), pred_end(Succ));
 630
 631           // Move all PHI nodes in BB to Succ if they are alive, otherwise
 632           // delete them.
 633           while (PHINode *PN = dyn_cast<PHINode>(&BB->front()))
 634             if (PN->use_empty())
 635               BB->getInstList().erase(BB->begin());  // Nuke instruction...
 636             else {
 637               // The instruction is alive, so this means that Succ must have
 638               // *ONLY* had BB as a predecessor, and the PHI node is still valid
 639               // now.  Simply move it into Succ, because we know that BB
 640               // strictly dominated Succ.
 641               BB->getInstList().remove(BB->begin());
 642               Succ->getInstList().push_front(PN);
 643
 644               // We need to add new entries for the PHI node to account for
 645               // predecessors of Succ that the PHI node does not take into
 646               // account.  At this point, since we know that BB dominated succ,
 647               // this means that we should any newly added incoming edges should
 648               // use the PHI node as the value for these edges, because they are
 649               // loop back edges.
 650               for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i)
 651                 if (OldSuccPreds[i] != BB)
 652                   PN->addIncoming(PN, OldSuccPreds[i]);
 653             }
 654
 655           // Everything that jumped to BB now goes to Succ...
 656           BB->replaceAllUsesWith(Succ);
 657
 658           // Delete the old basic block...
 659           M->getBasicBlockList().erase(BB);
 660
 661           if (!OldName.empty() && !Succ->hasName())  // Transfer name if we can
 662             Succ->setName(OldName);
 663           return true;
 664         }
 665       }
 666     }
 667   }
 668
 669   // If this is a returning block with only PHI nodes in it, fold the return
 670   // instruction into any unconditional branch predecessors.
 671   //
 672   // If any predecessor is a conditional branch that just selects among
 673   // different return values, fold the replace the branch/return with a select
 674   // and return.
 675   if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
 676     BasicBlock::iterator BBI = BB->getTerminator();
 677     if (BBI == BB->begin() || isa<PHINode>(--BBI)) {
 678       // Find predecessors that end with branches.
 679       std::vector<BasicBlock*> UncondBranchPreds;
 680       std::vector<BranchInst*> CondBranchPreds;
 681       for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 682         TerminatorInst *PTI = (*PI)->getTerminator();
 683         if (BranchInst *BI = dyn_cast<BranchInst>(PTI))
 684           if (BI->isUnconditional())
 685             UncondBranchPreds.push_back(*PI);
 686           else
 687             CondBranchPreds.push_back(BI);
 688       }
 689
 690       // If we found some, do the transformation!
 691       if (!UncondBranchPreds.empty()) {
 692         while (!UncondBranchPreds.empty()) {
 693           BasicBlock *Pred = UncondBranchPreds.back();
 694           UncondBranchPreds.pop_back();
 695           Instruction *UncondBranch = Pred->getTerminator();
 696           // Clone the return and add it to the end of the predecessor.
 697           Instruction *NewRet = RI->clone();
 698           Pred->getInstList().push_back(NewRet);
 699
 700           // If the return instruction returns a value, and if the value was a
 701           // PHI node in "BB", propagate the right value into the return.
 702           if (NewRet->getNumOperands() == 1)
 703             if (PHINode *PN = dyn_cast<PHINode>(NewRet->getOperand(0)))
 704               if (PN->getParent() == BB)
 705                 NewRet->setOperand(0, PN->getIncomingValueForBlock(Pred));
 706           // Update any PHI nodes in the returning block to realize that we no
 707           // longer branch to them.
 708           BB->removePredecessor(Pred);
 709           Pred->getInstList().erase(UncondBranch);
 710         }
 711
 712         // If we eliminated all predecessors of the block, delete the block now.
 713         if (pred_begin(BB) == pred_end(BB))
 714           // We know there are no successors, so just nuke the block.
 715           M->getBasicBlockList().erase(BB);
 716
 717         return true;
 718       }
 719
 720       // Check out all of the conditional branches going to this return
 721       // instruction.  If any of them just select between returns, change the
 722       // branch itself into a select/return pair.
 723       while (!CondBranchPreds.empty()) {
 724         BranchInst *BI = CondBranchPreds.back();
 725         CondBranchPreds.pop_back();
 726         BasicBlock *TrueSucc = BI->getSuccessor(0);
 727         BasicBlock *FalseSucc = BI->getSuccessor(1);
 728         BasicBlock *OtherSucc = TrueSucc == BB ? FalseSucc : TrueSucc;
 729
 730         // Check to see if the non-BB successor is also a return block.
 731         if (isa<ReturnInst>(OtherSucc->getTerminator())) {
 732           // Check to see if there are only PHI instructions in this block.
 733           BasicBlock::iterator OSI = OtherSucc->getTerminator();
 734           if (OSI == OtherSucc->begin() || isa<PHINode>(--OSI)) {
 735             // Okay, we found a branch that is going to two return nodes.  If
 736             // there is no return value for this function, just change the
 737             // branch into a return.
 738             if (RI->getNumOperands() == 0) {
 739               TrueSucc->removePredecessor(BI->getParent());
 740               FalseSucc->removePredecessor(BI->getParent());
 741               new ReturnInst(0, BI);
 742               BI->getParent()->getInstList().erase(BI);
 743               return true;
 744             }
 745
 746             // Otherwise, figure out what the true and false return values are
 747             // so we can insert a new select instruction.
 748             Value *TrueValue = TrueSucc->getTerminator()->getOperand(0);
 749             Value *FalseValue = FalseSucc->getTerminator()->getOperand(0);
 750
 751             // Unwrap any PHI nodes in the return blocks.
 752             if (PHINode *TVPN = dyn_cast<PHINode>(TrueValue))
 753               if (TVPN->getParent() == TrueSucc)
 754                 TrueValue = TVPN->getIncomingValueForBlock(BI->getParent());
 755             if (PHINode *FVPN = dyn_cast<PHINode>(FalseValue))
 756               if (FVPN->getParent() == FalseSucc)
 757                 FalseValue = FVPN->getIncomingValueForBlock(BI->getParent());
 758
 759             TrueSucc->removePredecessor(BI->getParent());
 760             FalseSucc->removePredecessor(BI->getParent());
 761
 762             // Insert a new select instruction.
 763             Value *NewRetVal;
 764             Value *BrCond = BI->getCondition();
 765             if (TrueValue != FalseValue)
 766               NewRetVal = new SelectInst(BrCond, TrueValue,
 767                                          FalseValue, "retval", BI);
 768             else
 769               NewRetVal = TrueValue;
 770
 771             new ReturnInst(NewRetVal, BI);
 772             BI->getParent()->getInstList().erase(BI);
 773             if (BrCond->use_empty())
 774               if (Instruction *BrCondI = dyn_cast<Instruction>(BrCond))
 775                 BrCondI->getParent()->getInstList().erase(BrCondI);
 776             return true;
 777           }
 778         }
 779       }
 780     }
 781   } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->begin())) {
 782     // Check to see if the first instruction in this block is just an unwind.
 783     // If so, replace any invoke instructions which use this as an exception
 784     // destination with call instructions, and any unconditional branch
 785     // predecessor with an unwind.
 786     //
 787     std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB));
 788     while (!Preds.empty()) {
 789       BasicBlock *Pred = Preds.back();
 790       if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator())) {
 791         if (BI->isUnconditional()) {
 792           Pred->getInstList().pop_back();  // nuke uncond branch
 793           new UnwindInst(Pred);            // Use unwind.
 794           Changed = true;
 795         }
 796       } else if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator()))
 797         if (II->getUnwindDest() == BB) {
 798           // Insert a new branch instruction before the invoke, because this
 799           // is now a fall through...
 800           BranchInst *BI = new BranchInst(II->getNormalDest(), II);
 801           Pred->getInstList().remove(II);   // Take out of symbol table
 802
 803           // Insert the call now...
 804           std::vector<Value*> Args(II->op_begin()+3, II->op_end());
 805           CallInst *CI = new CallInst(II->getCalledValue(), Args,
 806                                       II->getName(), BI);
 807           // If the invoke produced a value, the Call now does instead
 808           II->replaceAllUsesWith(CI);
 809           delete II;
 810           Changed = true;
 811         }
 812
 813       Preds.pop_back();
 814     }
 815
 816     // If this block is now dead, remove it.
 817     if (pred_begin(BB) == pred_end(BB)) {
 818       // We know there are no successors, so just nuke the block.
 819       M->getBasicBlockList().erase(BB);
 820       return true;
 821     }
 822
 823   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->begin())) {
 824     if (isValueEqualityComparison(SI))
 825       if (FoldValueComparisonIntoPredecessors(SI))
 826         return SimplifyCFG(BB) || 1;
 827   } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
 828     if (BI->isConditional()) {
 829       if (Value *CompVal = isValueEqualityComparison(BI)) {
 830         // This block must be empty, except for the setcond inst, if it exists.
 831         BasicBlock::iterator I = BB->begin();
 832         if (&*I == BI ||
 833             (&*I == cast<Instruction>(BI->getCondition()) &&
 834              &*++I == BI))
 835           if (FoldValueComparisonIntoPredecessors(BI))
 836             return SimplifyCFG(BB) | true;
 837       }
 838
 839       // If this basic block is ONLY a setcc and a branch, and if a predecessor
 840       // branches to us and one of our successors, fold the setcc into the
 841       // predecessor and use logical operations to pick the right destination.
 842       BasicBlock *TrueDest  = BI->getSuccessor(0);
 843       BasicBlock *FalseDest = BI->getSuccessor(1);
 844       if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(BI->getCondition()))
 845         if (Cond->getParent() == BB && &BB->front() == Cond &&
 846             Cond->getNext() == BI && Cond->hasOneUse() &&
 847             TrueDest != BB && FalseDest != BB)
 848           for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI!=E; ++PI)
 849             if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
 850               if (PBI->isConditional() && SafeToMergeTerminators(BI, PBI)) {
 851                 BasicBlock *PredBlock = *PI;
 852                 if (PBI->getSuccessor(0) == FalseDest ||
 853                     PBI->getSuccessor(1) == TrueDest) {
 854                   // Invert the predecessors condition test (xor it with true),
 855                   // which allows us to write this code once.
 856                   Value *NewCond =
 857                     BinaryOperator::createNot(PBI->getCondition(),
 858                                     PBI->getCondition()->getName()+".not", PBI);
 859                   PBI->setCondition(NewCond);
 860                   BasicBlock *OldTrue = PBI->getSuccessor(0);
 861                   BasicBlock *OldFalse = PBI->getSuccessor(1);
 862                   PBI->setSuccessor(0, OldFalse);
 863                   PBI->setSuccessor(1, OldTrue);
 864                 }
 865
 866                 if (PBI->getSuccessor(0) == TrueDest ||
 867                     PBI->getSuccessor(1) == FalseDest) {
 868                   // Clone Cond into the predecessor basic block, and or/and the
 869                   // two conditions together.
 870                   Instruction *New = Cond->clone();
 871                   New->setName(Cond->getName());
 872                   Cond->setName(Cond->getName()+".old");
 873                   PredBlock->getInstList().insert(PBI, New);
 874                   Instruction::BinaryOps Opcode =
 875                     PBI->getSuccessor(0) == TrueDest ?
 876                     Instruction::Or : Instruction::And;
 877                   Value *NewCond =
 878                     BinaryOperator::create(Opcode, PBI->getCondition(),
 879                                            New, "bothcond", PBI);
 880                   PBI->setCondition(NewCond);
 881                   if (PBI->getSuccessor(0) == BB) {
 882                     AddPredecessorToBlock(TrueDest, PredBlock, BB);
 883                     PBI->setSuccessor(0, TrueDest);
 884                   }
 885                   if (PBI->getSuccessor(1) == BB) {
 886                     AddPredecessorToBlock(FalseDest, PredBlock, BB);
 887                     PBI->setSuccessor(1, FalseDest);
 888                   }
 889                   return SimplifyCFG(BB) | 1;
 890                 }
 891               }
 892
 893       // If this block ends with a branch instruction, and if there is one
 894       // predecessor, see if the previous block ended with a branch on the same
 895       // condition, which makes this conditional branch redundant.
 896       pred_iterator PI(pred_begin(BB)), PE(pred_end(BB));
 897       BasicBlock *OnlyPred = *PI++;
 898       for (; PI != PE; ++PI)// Search all predecessors, see if they are all same
 899         if (*PI != OnlyPred) {
 900           OnlyPred = 0;       // There are multiple different predecessors...
 901           break;
 902         }
 903
 904       if (OnlyPred)
 905         if (BranchInst *PBI = dyn_cast<BranchInst>(OnlyPred->getTerminator()))
 906           if (PBI->isConditional() &&
 907               PBI->getCondition() == BI->getCondition() &&
 908               (PBI->getSuccessor(0) != BB || PBI->getSuccessor(1) != BB)) {
 909             // Okay, the outcome of this conditional branch is statically
 910             // knowable.  Delete the outgoing CFG edge that is impossible to
 911             // execute.
 912             bool CondIsTrue = PBI->getSuccessor(0) == BB;
 913             BI->getSuccessor(CondIsTrue)->removePredecessor(BB);
 914             new BranchInst(BI->getSuccessor(!CondIsTrue), BB);
 915             BB->getInstList().erase(BI);
 916             return SimplifyCFG(BB) | true;
 917           }
 918     }
 919   } else if (isa<UnreachableInst>(BB->getTerminator())) {
 920     // If there are any instructions immediately before the unreachable that can
 921     // be removed, do so.
 922     Instruction *Unreachable = BB->getTerminator();
 923     while (Unreachable != BB->begin()) {
 924       BasicBlock::iterator BBI = Unreachable;
 925       --BBI;
 926       if (isa<CallInst>(BBI)) break;
 927       // Delete this instruction
 928       BB->getInstList().erase(BBI);
 929       Changed = true;
 930     }
 931
 932     // If the unreachable instruction is the first in the block, take a gander
 933     // at all of the predecessors of this instruction, and simplify them.
 934     if (&BB->front() == Unreachable) {
 935       std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB));
 936       for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
 937         TerminatorInst *TI = Preds[i]->getTerminator();
 938
 939         if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 940           if (BI->isUnconditional()) {
 941             if (BI->getSuccessor(0) == BB) {
 942               new UnreachableInst(TI);
 943               TI->eraseFromParent();
 944               Changed = true;
 945             }
 946           } else {
 947             if (BI->getSuccessor(0) == BB) {
 948               new BranchInst(BI->getSuccessor(1), BI);
 949               BI->eraseFromParent();
 950             } else if (BI->getSuccessor(1) == BB) {
 951               new BranchInst(BI->getSuccessor(0), BI);
 952               BI->eraseFromParent();
 953               Changed = true;
 954             }
 955           }
 956         } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 957           for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i)
 958             if (SI->getSuccessor(i) == BB) {
 959               SI->removeCase(i);
 960               --i; --e;
 961               Changed = true;
 962             }
 963           // If the default value is unreachable, figure out the most popular
 964           // destination and make it the default.
 965           if (SI->getSuccessor(0) == BB) {
 966             std::map<BasicBlock*, unsigned> Popularity;
 967             for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i)
 968               Popularity[SI->getSuccessor(i)]++;
 969
 970             // Find the most popular block.
 971             unsigned MaxPop = 0;
 972             BasicBlock *MaxBlock = 0;
 973             for (std::map<BasicBlock*, unsigned>::iterator
 974                    I = Popularity.begin(), E = Popularity.end(); I != E; ++I) {
 975               if (I->second > MaxPop) {
 976                 MaxPop = I->second;
 977                 MaxBlock = I->first;
 978               }
 979             }
 980             if (MaxBlock) {
 981               // Make this the new default, allowing us to delete any explicit
 982               // edges to it.
 983               SI->setSuccessor(0, MaxBlock);
 984               Changed = true;
 985
 986               for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i)
 987                 if (SI->getSuccessor(i) == MaxBlock) {
 988                   SI->removeCase(i);
 989                   --i; --e;
 990                 }
 991             }
 992           }
 993         } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
 994           if (II->getUnwindDest() == BB) {
 995             // Convert the invoke to a call instruction.  This would be a good
 996             // place to note that the call does not throw though.
 997             BranchInst *BI = new BranchInst(II->getNormalDest(), II);
 998             II->removeFromParent();   // Take out of symbol table
 999
1000             // Insert the call now...
1001             std::vector<Value*> Args(II->op_begin()+3, II->op_end());
1002             CallInst *CI = new CallInst(II->getCalledValue(), Args,
1003                                         II->getName(), BI);
1004             // If the invoke produced a value, the Call does now instead.
1005             II->replaceAllUsesWith(CI);
1006             delete II;
1007             Changed = true;
1008           }
1009         }
1010       }
1011
1012       // If this block is now dead, remove it.
1013       if (pred_begin(BB) == pred_end(BB)) {
1014         // We know there are no successors, so just nuke the block.
1015         M->getBasicBlockList().erase(BB);
1016         return true;
1017       }
1018     }
1019   }
1020
1021   // Merge basic blocks into their predecessor if there is only one distinct
1022   // pred, and if there is only one distinct successor of the predecessor, and
1023   // if there are no PHI nodes.
1024   //
1025   pred_iterator PI(pred_begin(BB)), PE(pred_end(BB));
1026   BasicBlock *OnlyPred = *PI++;
1027   for (; PI != PE; ++PI)  // Search all predecessors, see if they are all same
1028     if (*PI != OnlyPred) {
1029       OnlyPred = 0;       // There are multiple different predecessors...
1030       break;
1031     }
1032
1033   BasicBlock *OnlySucc = 0;
1034   if (OnlyPred && OnlyPred != BB &&    // Don't break self loops
1035       OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) {
1036     // Check to see if there is only one distinct successor...
1037     succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred));
1038     OnlySucc = BB;
1039     for (; SI != SE; ++SI)
1040       if (*SI != OnlySucc) {
1041         OnlySucc = 0;     // There are multiple distinct successors!
1042         break;
1043       }
1044   }
1045
1046   if (OnlySucc) {
1047     DEBUG(std::cerr << "Merging: " << *BB << "into: " << *OnlyPred);
1048     TerminatorInst *Term = OnlyPred->getTerminator();
1049
1050     // Resolve any PHI nodes at the start of the block.  They are all
1051     // guaranteed to have exactly one entry if they exist, unless there are
1052     // multiple duplicate (but guaranteed to be equal) entries for the
1053     // incoming edges.  This occurs when there are multiple edges from
1054     // OnlyPred to OnlySucc.
1055     //
1056     while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
1057       PN->replaceAllUsesWith(PN->getIncomingValue(0));
1058       BB->getInstList().pop_front();  // Delete the phi node...
1059     }
1060
1061     // Delete the unconditional branch from the predecessor...
1062     OnlyPred->getInstList().pop_back();
1063
1064     // Move all definitions in the successor to the predecessor...
1065     OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
1066
1067     // Make all PHI nodes that referred to BB now refer to Pred as their
1068     // source...
1069     BB->replaceAllUsesWith(OnlyPred);
1070
1071     std::string OldName = BB->getName();
1072
1073     // Erase basic block from the function...
1074     M->getBasicBlockList().erase(BB);
1075
1076     // Inherit predecessors name if it exists...
1077     if (!OldName.empty() && !OnlyPred->hasName())
1078       OnlyPred->setName(OldName);
1079
1080     return true;
1081   }
1082
1083   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
1084     if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator()))
1085       // Change br (X == 0 | X == 1), T, F into a switch instruction.
1086       if (BI->isConditional() && isa<Instruction>(BI->getCondition())) {
1087         Instruction *Cond = cast<Instruction>(BI->getCondition());
1088         // If this is a bunch of seteq's or'd together, or if it's a bunch of
1089         // 'setne's and'ed together, collect them.
1090         Value *CompVal = 0;
1091         std::vector<ConstantInt*> Values;
1092         bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values);
1093         if (CompVal && CompVal->getType()->isInteger()) {
1094           // There might be duplicate constants in the list, which the switch
1095           // instruction can't handle, remove them now.
1096           std::sort(Values.begin(), Values.end(), ConstantIntOrdering());
1097           Values.erase(std::unique(Values.begin(), Values.end()), Values.end());
1098
1099           // Figure out which block is which destination.
1100           BasicBlock *DefaultBB = BI->getSuccessor(1);
1101           BasicBlock *EdgeBB    = BI->getSuccessor(0);
1102           if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB);
1103
1104           // Create the new switch instruction now.
1105           SwitchInst *New = new SwitchInst(CompVal, DefaultBB, BI);
1106
1107           // Add all of the 'cases' to the switch instruction.
1108           for (unsigned i = 0, e = Values.size(); i != e; ++i)
1109             New->addCase(Values[i], EdgeBB);
1110
1111           // We added edges from PI to the EdgeBB.  As such, if there were any
1112           // PHI nodes in EdgeBB, they need entries to be added corresponding to
1113           // the number of edges added.
1114           for (BasicBlock::iterator BBI = EdgeBB->begin();
1115                isa<PHINode>(BBI); ++BBI) {
1116             PHINode *PN = cast<PHINode>(BBI);
1117             Value *InVal = PN->getIncomingValueForBlock(*PI);
1118             for (unsigned i = 0, e = Values.size()-1; i != e; ++i)
1119               PN->addIncoming(InVal, *PI);
1120           }
1121
1122           // Erase the old branch instruction.
1123           (*PI)->getInstList().erase(BI);
1124
1125           // Erase the potentially condition tree that was used to computed the
1126           // branch condition.
1127           ErasePossiblyDeadInstructionTree(Cond);
1128           return true;
1129         }
1130       }
1131
1132   // If there is a trivial two-entry PHI node in this basic block, and we can
1133   // eliminate it, do so now.
1134   if (PHINode *PN = dyn_cast<PHINode>(BB->begin()))
1135     if (PN->getNumIncomingValues() == 2) {
1136       // Ok, this is a two entry PHI node.  Check to see if this is a simple "if
1137       // statement", which has a very simple dominance structure.  Basically, we
1138       // are trying to find the condition that is being branched on, which
1139       // subsequently causes this merge to happen.  We really want control
1140       // dependence information for this check, but simplifycfg can't keep it up
1141       // to date, and this catches most of the cases we care about anyway.
1142       //
1143       BasicBlock *IfTrue, *IfFalse;
1144       if (Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse)) {
1145         DEBUG(std::cerr << "FOUND IF CONDITION!  " << *IfCond << "  T: "
1146               << IfTrue->getName() << "  F: " << IfFalse->getName() << "\n");
1147
1148         // Loop over the PHI's seeing if we can promote them all to select
1149         // instructions.  While we are at it, keep track of the instructions
1150         // that need to be moved to the dominating block.
1151         std::set<Instruction*> AggressiveInsts;
1152         bool CanPromote = true;
1153
1154         BasicBlock::iterator AfterPHIIt = BB->begin();
1155         while (isa<PHINode>(AfterPHIIt)) {
1156           PHINode *PN = cast<PHINode>(AfterPHIIt++);
1157           if (PN->getIncomingValue(0) == PN->getIncomingValue(1))
1158             PN->replaceAllUsesWith(PN->getIncomingValue(0));
1159           else if (!DominatesMergePoint(PN->getIncomingValue(0), BB,
1160                                         &AggressiveInsts) ||
1161                    !DominatesMergePoint(PN->getIncomingValue(1), BB,
1162                                         &AggressiveInsts)) {
1163             CanPromote = false;
1164             break;
1165           }
1166         }
1167
1168         // Did we eliminate all PHI's?
1169         CanPromote |= AfterPHIIt == BB->begin();
1170
1171         // If we all PHI nodes are promotable, check to make sure that all
1172         // instructions in the predecessor blocks can be promoted as well.  If
1173         // not, we won't be able to get rid of the control flow, so it's not
1174         // worth promoting to select instructions.
1175         BasicBlock *DomBlock, *IfBlock1 = 0, *IfBlock2 = 0;
1176         if (CanPromote) {
1177           PN = cast<PHINode>(BB->begin());
1178           BasicBlock *Pred = PN->getIncomingBlock(0);
1179           if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) {
1180             IfBlock1 = Pred;
1181             DomBlock = *pred_begin(Pred);
1182             for (BasicBlock::iterator I = Pred->begin();
1183                  !isa<TerminatorInst>(I); ++I)
1184               if (!AggressiveInsts.count(I)) {
1185                 // This is not an aggressive instruction that we can promote.
1186                 // Because of this, we won't be able to get rid of the control
1187                 // flow, so the xform is not worth it.
1188                 CanPromote = false;
1189                 break;
1190               }
1191           }
1192
1193           Pred = PN->getIncomingBlock(1);
1194           if (CanPromote &&
1195               cast<BranchInst>(Pred->getTerminator())->isUnconditional()) {
1196             IfBlock2 = Pred;
1197             DomBlock = *pred_begin(Pred);
1198             for (BasicBlock::iterator I = Pred->begin();
1199                  !isa<TerminatorInst>(I); ++I)
1200               if (!AggressiveInsts.count(I)) {
1201                 // This is not an aggressive instruction that we can promote.
1202                 // Because of this, we won't be able to get rid of the control
1203                 // flow, so the xform is not worth it.
1204                 CanPromote = false;
1205                 break;
1206               }
1207           }
1208         }
1209
1210         // If we can still promote the PHI nodes after this gauntlet of tests,
1211         // do all of the PHI's now.
1212         if (CanPromote) {
1213           // Move all 'aggressive' instructions, which are defined in the
1214           // conditional parts of the if's up to the dominating block.
1215           if (IfBlock1) {
1216             DomBlock->getInstList().splice(DomBlock->getTerminator(),
1217                                            IfBlock1->getInstList(),
1218                                            IfBlock1->begin(),
1219                                            IfBlock1->getTerminator());
1220           }
1221           if (IfBlock2) {
1222             DomBlock->getInstList().splice(DomBlock->getTerminator(),
1223                                            IfBlock2->getInstList(),
1224                                            IfBlock2->begin(),
1225                                            IfBlock2->getTerminator());
1226           }
1227
1228           while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
1229             // Change the PHI node into a select instruction.
1230             Value *TrueVal =
1231               PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse);
1232             Value *FalseVal =
1233               PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue);
1234
1235             std::string Name = PN->getName(); PN->setName("");
1236             PN->replaceAllUsesWith(new SelectInst(IfCond, TrueVal, FalseVal,
1237                                                   Name, AfterPHIIt));
1238             BB->getInstList().erase(PN);
1239           }
1240           Changed = true;
1241         }
1242       }
1243     }
1244
1245   return Changed;
1246 }