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 #include "llvm/Transforms/Utils/Local.h"
  15 #include "llvm/Constants.h"
  16 #include "llvm/Instructions.h"
  17 #include "llvm/Type.h"
  18 #include "llvm/Support/CFG.h"
  19 #include <algorithm>
  20 #include <functional>
  21 using namespace llvm;
  22
  23 // PropagatePredecessorsForPHIs - This gets "Succ" ready to have the
  24 // predecessors from "BB".  This is a little tricky because "Succ" has PHI
  25 // nodes, which need to have extra slots added to them to hold the merge edges
  26 // from BB's predecessors, and BB itself might have had PHI nodes in it.  This
  27 // function returns true (failure) if the Succ BB already has a predecessor that
  28 // is a predecessor of BB and incoming PHI arguments would not be discernible.
  29 //
  30 // Assumption: Succ is the single successor for BB.
  31 //
  32 static bool PropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
  33   assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
  34
  35   if (!isa<PHINode>(Succ->front()))
  36     return false;  // We can make the transformation, no problem.
  37
  38   // If there is more than one predecessor, and there are PHI nodes in
  39   // the successor, then we need to add incoming edges for the PHI nodes
  40   //
  41   const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB));
  42
  43   // Check to see if one of the predecessors of BB is already a predecessor of
  44   // Succ.  If so, we cannot do the transformation if there are any PHI nodes
  45   // with incompatible values coming in from the two edges!
  46   //
  47   for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); PI != PE; ++PI)
  48     if (find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) {
  49       // Loop over all of the PHI nodes checking to see if there are
  50       // incompatible values coming in.
  51       for (BasicBlock::iterator I = Succ->begin();
  52            PHINode *PN = dyn_cast<PHINode>(I); ++I) {
  53         // Loop up the entries in the PHI node for BB and for *PI if the values
  54         // coming in are non-equal, we cannot merge these two blocks (instead we
  55         // should insert a conditional move or something, then merge the
  56         // blocks).
  57         int Idx1 = PN->getBasicBlockIndex(BB);
  58         int Idx2 = PN->getBasicBlockIndex(*PI);
  59         assert(Idx1 != -1 && Idx2 != -1 &&
  60                "Didn't have entries for my predecessors??");
  61         if (PN->getIncomingValue(Idx1) != PN->getIncomingValue(Idx2))
  62           return true;  // Values are not equal...
  63       }
  64     }
  65
  66   // Loop over all of the PHI nodes in the successor BB
  67   for (BasicBlock::iterator I = Succ->begin();
  68        PHINode *PN = dyn_cast<PHINode>(I); ++I) {
  69     Value *OldVal = PN->removeIncomingValue(BB, false);
  70     assert(OldVal && "No entry in PHI for Pred BB!");
  71
  72     // If this incoming value is one of the PHI nodes in BB...
  73     if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
  74       PHINode *OldValPN = cast<PHINode>(OldVal);
  75       for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(),
  76              End = BBPreds.end(); PredI != End; ++PredI) {
  77         PN->addIncoming(OldValPN->getIncomingValueForBlock(*PredI), *PredI);
  78       }
  79     } else {
  80       for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(),
  81              End = BBPreds.end(); PredI != End; ++PredI) {
  82         // Add an incoming value for each of the new incoming values...
  83         PN->addIncoming(OldVal, *PredI);
  84       }
  85     }
  86   }
  87   return false;
  88 }
  89
  90 /// GetIfCondition - Given a basic block (BB) with two predecessors (and
  91 /// presumably PHI nodes in it), check to see if the merge at this block is due
  92 /// to an "if condition".  If so, return the boolean condition that determines
  93 /// which entry into BB will be taken.  Also, return by references the block
  94 /// that will be entered from if the condition is true, and the block that will
  95 /// be entered if the condition is false.
  96 ///
  97 ///
  98 static Value *GetIfCondition(BasicBlock *BB,
  99                              BasicBlock *&IfTrue, BasicBlock *&IfFalse) {
 100   assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 &&
 101          "Function can only handle blocks with 2 predecessors!");
 102   BasicBlock *Pred1 = *pred_begin(BB);
 103   BasicBlock *Pred2 = *++pred_begin(BB);
 104
 105   // We can only handle branches.  Other control flow will be lowered to
 106   // branches if possible anyway.
 107   if (!isa<BranchInst>(Pred1->getTerminator()) ||
 108       !isa<BranchInst>(Pred2->getTerminator()))
 109     return 0;
 110   BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator());
 111   BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator());
 112
 113   // Eliminate code duplication by ensuring that Pred1Br is conditional if
 114   // either are.
 115   if (Pred2Br->isConditional()) {
 116     // If both branches are conditional, we don't have an "if statement".  In
 117     // reality, we could transform this case, but since the condition will be
 118     // required anyway, we stand no chance of eliminating it, so the xform is
 119     // probably not profitable.
 120     if (Pred1Br->isConditional())
 121       return 0;
 122
 123     std::swap(Pred1, Pred2);
 124     std::swap(Pred1Br, Pred2Br);
 125   }
 126
 127   if (Pred1Br->isConditional()) {
 128     // If we found a conditional branch predecessor, make sure that it branches
 129     // to BB and Pred2Br.  If it doesn't, this isn't an "if statement".
 130     if (Pred1Br->getSuccessor(0) == BB &&
 131         Pred1Br->getSuccessor(1) == Pred2) {
 132       IfTrue = Pred1;
 133       IfFalse = Pred2;
 134     } else if (Pred1Br->getSuccessor(0) == Pred2 &&
 135                Pred1Br->getSuccessor(1) == BB) {
 136       IfTrue = Pred2;
 137       IfFalse = Pred1;
 138     } else {
 139       // We know that one arm of the conditional goes to BB, so the other must
 140       // go somewhere unrelated, and this must not be an "if statement".
 141       return 0;
 142     }
 143
 144     // The only thing we have to watch out for here is to make sure that Pred2
 145     // doesn't have incoming edges from other blocks.  If it does, the condition
 146     // doesn't dominate BB.
 147     if (++pred_begin(Pred2) != pred_end(Pred2))
 148       return 0;
 149
 150     return Pred1Br->getCondition();
 151   }
 152
 153   // Ok, if we got here, both predecessors end with an unconditional branch to
 154   // BB.  Don't panic!  If both blocks only have a single (identical)
 155   // predecessor, and THAT is a conditional branch, then we're all ok!
 156   if (pred_begin(Pred1) == pred_end(Pred1) ||
 157       ++pred_begin(Pred1) != pred_end(Pred1) ||
 158       pred_begin(Pred2) == pred_end(Pred2) ||
 159       ++pred_begin(Pred2) != pred_end(Pred2) ||
 160       *pred_begin(Pred1) != *pred_begin(Pred2))
 161     return 0;
 162
 163   // Otherwise, if this is a conditional branch, then we can use it!
 164   BasicBlock *CommonPred = *pred_begin(Pred1);
 165   if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) {
 166     assert(BI->isConditional() && "Two successors but not conditional?");
 167     if (BI->getSuccessor(0) == Pred1) {
 168       IfTrue = Pred1;
 169       IfFalse = Pred2;
 170     } else {
 171       IfTrue = Pred2;
 172       IfFalse = Pred1;
 173     }
 174     return BI->getCondition();
 175   }
 176   return 0;
 177 }
 178
 179
 180 // If we have a merge point of an "if condition" as accepted above, return true
 181 // if the specified value dominates the block.  We don't handle the true
 182 // generality of domination here, just a special case which works well enough
 183 // for us.
 184 static bool DominatesMergePoint(Value *V, BasicBlock *BB) {
 185   if (Instruction *I = dyn_cast<Instruction>(V)) {
 186     BasicBlock *PBB = I->getParent();
 187     // If this instruction is defined in a block that contains an unconditional
 188     // branch to BB, then it must be in the 'conditional' part of the "if
 189     // statement".
 190     if (isa<BranchInst>(PBB->getTerminator()) &&
 191         cast<BranchInst>(PBB->getTerminator())->isUnconditional() &&
 192         cast<BranchInst>(PBB->getTerminator())->getSuccessor(0) == BB)
 193       return false;
 194
 195     // We also don't want to allow wierd loops that might have the "if
 196     // condition" in the bottom of this block.
 197     if (PBB == BB) return false;
 198   }
 199
 200   // Non-instructions all dominate instructions.
 201   return true;
 202 }
 203
 204 // GatherConstantSetEQs - Given a potentially 'or'd together collection of seteq
 205 // instructions that compare a value against a constant, return the value being
 206 // compared, and stick the constant into the Values vector.
 207 static Value *GatherConstantSetEQs(Value *V, std::vector<Constant*> &Values) {
 208   if (Instruction *Inst = dyn_cast<Instruction>(V))
 209     if (Inst->getOpcode() == Instruction::SetEQ) {
 210       if (Constant *C = dyn_cast<Constant>(Inst->getOperand(1))) {
 211         Values.push_back(C);
 212         return Inst->getOperand(0);
 213       } else if (Constant *C = dyn_cast<Constant>(Inst->getOperand(0))) {
 214         Values.push_back(C);
 215         return Inst->getOperand(1);
 216       }
 217     } else if (Inst->getOpcode() == Instruction::Or) {
 218       if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values))
 219         if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values))
 220           if (LHS == RHS)
 221             return LHS;
 222     }
 223   return 0;
 224 }
 225
 226 // GatherConstantSetNEs - Given a potentially 'and'd together collection of
 227 // setne instructions that compare a value against a constant, return the value
 228 // being compared, and stick the constant into the Values vector.
 229 static Value *GatherConstantSetNEs(Value *V, std::vector<Constant*> &Values) {
 230   if (Instruction *Inst = dyn_cast<Instruction>(V))
 231     if (Inst->getOpcode() == Instruction::SetNE) {
 232       if (Constant *C = dyn_cast<Constant>(Inst->getOperand(1))) {
 233         Values.push_back(C);
 234         return Inst->getOperand(0);
 235       } else if (Constant *C = dyn_cast<Constant>(Inst->getOperand(0))) {
 236         Values.push_back(C);
 237         return Inst->getOperand(1);
 238       }
 239     } else if (Inst->getOpcode() == Instruction::Cast) {
 240       // Cast of X to bool is really a comparison against zero.
 241       assert(Inst->getType() == Type::BoolTy && "Can only handle bool values!");
 242       Values.push_back(Constant::getNullValue(Inst->getOperand(0)->getType()));
 243       return Inst->getOperand(0);
 244     } else if (Inst->getOpcode() == Instruction::And) {
 245       if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values))
 246         if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values))
 247           if (LHS == RHS)
 248             return LHS;
 249     }
 250   return 0;
 251 }
 252
 253
 254
 255 /// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a
 256 /// bunch of comparisons of one value against constants, return the value and
 257 /// the constants being compared.
 258 static bool GatherValueComparisons(Instruction *Cond, Value *&CompVal,
 259                                    std::vector<Constant*> &Values) {
 260   if (Cond->getOpcode() == Instruction::Or) {
 261     CompVal = GatherConstantSetEQs(Cond, Values);
 262
 263     // Return true to indicate that the condition is true if the CompVal is
 264     // equal to one of the constants.
 265     return true;
 266   } else if (Cond->getOpcode() == Instruction::And) {
 267     CompVal = GatherConstantSetNEs(Cond, Values);
 268
 269     // Return false to indicate that the condition is false if the CompVal is
 270     // equal to one of the constants.
 271     return false;
 272   }
 273   return false;
 274 }
 275
 276 /// ErasePossiblyDeadInstructionTree - If the specified instruction is dead and
 277 /// has no side effects, nuke it.  If it uses any instructions that become dead
 278 /// because the instruction is now gone, nuke them too.
 279 static void ErasePossiblyDeadInstructionTree(Instruction *I) {
 280   if (isInstructionTriviallyDead(I)) {
 281     std::vector<Value*> Operands(I->op_begin(), I->op_end());
 282     I->getParent()->getInstList().erase(I);
 283     for (unsigned i = 0, e = Operands.size(); i != e; ++i)
 284       if (Instruction *OpI = dyn_cast<Instruction>(Operands[i]))
 285         ErasePossiblyDeadInstructionTree(OpI);
 286   }
 287 }
 288
 289 // SimplifyCFG - This function is used to do simplification of a CFG.  For
 290 // example, it adjusts branches to branches to eliminate the extra hop, it
 291 // eliminates unreachable basic blocks, and does other "peephole" optimization
 292 // of the CFG.  It returns true if a modification was made.
 293 //
 294 // WARNING:  The entry node of a function may not be simplified.
 295 //
 296 bool llvm::SimplifyCFG(BasicBlock *BB) {
 297   bool Changed = false;
 298   Function *M = BB->getParent();
 299
 300   assert(BB && BB->getParent() && "Block not embedded in function!");
 301   assert(BB->getTerminator() && "Degenerate basic block encountered!");
 302   assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!");
 303
 304   // Check to see if the first instruction in this block is just an unwind.  If
 305   // so, replace any invoke instructions which use this as an exception
 306   // destination with call instructions.
 307   //
 308   if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator()))
 309     if (BB->begin() == BasicBlock::iterator(UI)) {  // Empty block?
 310       std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB));
 311       while (!Preds.empty()) {
 312         BasicBlock *Pred = Preds.back();
 313         if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator()))
 314           if (II->getUnwindDest() == BB) {
 315             // Insert a new branch instruction before the invoke, because this
 316             // is now a fall through...
 317             BranchInst *BI = new BranchInst(II->getNormalDest(), II);
 318             Pred->getInstList().remove(II);   // Take out of symbol table
 319
 320             // Insert the call now...
 321             std::vector<Value*> Args(II->op_begin()+3, II->op_end());
 322             CallInst *CI = new CallInst(II->getCalledValue(), Args,
 323                                         II->getName(), BI);
 324             // If the invoke produced a value, the Call now does instead
 325             II->replaceAllUsesWith(CI);
 326             delete II;
 327             Changed = true;
 328           }
 329
 330         Preds.pop_back();
 331       }
 332     }
 333
 334   // Remove basic blocks that have no predecessors... which are unreachable.
 335   if (pred_begin(BB) == pred_end(BB)) {
 336     //cerr << "Removing BB: \n" << BB;
 337
 338     // Loop through all of our successors and make sure they know that one
 339     // of their predecessors is going away.
 340     for_each(succ_begin(BB), succ_end(BB),
 341              std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB));
 342
 343     while (!BB->empty()) {
 344       Instruction &I = BB->back();
 345       // If this instruction is used, replace uses with an arbitrary
 346       // constant value.  Because control flow can't get here, we don't care
 347       // what we replace the value with.  Note that since this block is
 348       // unreachable, and all values contained within it must dominate their
 349       // uses, that all uses will eventually be removed.
 350       if (!I.use_empty())
 351         // Make all users of this instruction reference the constant instead
 352         I.replaceAllUsesWith(Constant::getNullValue(I.getType()));
 353
 354       // Remove the instruction from the basic block
 355       BB->getInstList().pop_back();
 356     }
 357     M->getBasicBlockList().erase(BB);
 358     return true;
 359   }
 360
 361   // Check to see if we can constant propagate this terminator instruction
 362   // away...
 363   Changed |= ConstantFoldTerminator(BB);
 364
 365   // Check to see if this block has no non-phi instructions and only a single
 366   // successor.  If so, replace references to this basic block with references
 367   // to the successor.
 368   succ_iterator SI(succ_begin(BB));
 369   if (SI != succ_end(BB) && ++SI == succ_end(BB)) {  // One succ?
 370
 371     BasicBlock::iterator BBI = BB->begin();  // Skip over phi nodes...
 372     while (isa<PHINode>(*BBI)) ++BBI;
 373
 374     if (BBI->isTerminator()) {   // Terminator is the only non-phi instruction!
 375       BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor
 376
 377       if (Succ != BB) {   // Arg, don't hurt infinite loops!
 378         // If our successor has PHI nodes, then we need to update them to
 379         // include entries for BB's predecessors, not for BB itself.
 380         // Be careful though, if this transformation fails (returns true) then
 381         // we cannot do this transformation!
 382         //
 383         if (!PropagatePredecessorsForPHIs(BB, Succ)) {
 384           //cerr << "Killing Trivial BB: \n" << BB;
 385           std::string OldName = BB->getName();
 386
 387           std::vector<BasicBlock*>
 388             OldSuccPreds(pred_begin(Succ), pred_end(Succ));
 389
 390           // Move all PHI nodes in BB to Succ if they are alive, otherwise
 391           // delete them.
 392           while (PHINode *PN = dyn_cast<PHINode>(&BB->front()))
 393             if (PN->use_empty())
 394               BB->getInstList().erase(BB->begin());  // Nuke instruction...
 395             else {
 396               // The instruction is alive, so this means that Succ must have
 397               // *ONLY* had BB as a predecessor, and the PHI node is still valid
 398               // now.  Simply move it into Succ, because we know that BB
 399               // strictly dominated Succ.
 400               BB->getInstList().remove(BB->begin());
 401               Succ->getInstList().push_front(PN);
 402
 403               // We need to add new entries for the PHI node to account for
 404               // predecessors of Succ that the PHI node does not take into
 405               // account.  At this point, since we know that BB dominated succ,
 406               // this means that we should any newly added incoming edges should
 407               // use the PHI node as the value for these edges, because they are
 408               // loop back edges.
 409
 410               for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i)
 411                 if (OldSuccPreds[i] != BB)
 412                   PN->addIncoming(PN, OldSuccPreds[i]);
 413             }
 414
 415           // Everything that jumped to BB now goes to Succ...
 416           BB->replaceAllUsesWith(Succ);
 417
 418           // Delete the old basic block...
 419           M->getBasicBlockList().erase(BB);
 420
 421           if (!OldName.empty() && !Succ->hasName())  // Transfer name if we can
 422             Succ->setName(OldName);
 423
 424           //cerr << "Function after removal: \n" << M;
 425           return true;
 426         }
 427       }
 428     }
 429   }
 430
 431   // If this is a returning block with only PHI nodes in it, fold the return
 432   // instruction into any unconditional branch predecessors.
 433   if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
 434     BasicBlock::iterator BBI = BB->getTerminator();
 435     if (BBI == BB->begin() || isa<PHINode>(--BBI)) {
 436       // Find predecessors that end with unconditional branches.
 437       std::vector<BasicBlock*> UncondBranchPreds;
 438       for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 439         TerminatorInst *PTI = (*PI)->getTerminator();
 440         if (BranchInst *BI = dyn_cast<BranchInst>(PTI))
 441           if (BI->isUnconditional())
 442             UncondBranchPreds.push_back(*PI);
 443       }
 444
 445       // If we found some, do the transformation!
 446       if (!UncondBranchPreds.empty()) {
 447         while (!UncondBranchPreds.empty()) {
 448           BasicBlock *Pred = UncondBranchPreds.back();
 449           UncondBranchPreds.pop_back();
 450           Instruction *UncondBranch = Pred->getTerminator();
 451           // Clone the return and add it to the end of the predecessor.
 452           Instruction *NewRet = RI->clone();
 453           Pred->getInstList().push_back(NewRet);
 454
 455           // If the return instruction returns a value, and if the value was a
 456           // PHI node in "BB", propagate the right value into the return.
 457           if (NewRet->getNumOperands() == 1)
 458             if (PHINode *PN = dyn_cast<PHINode>(NewRet->getOperand(0)))
 459               if (PN->getParent() == BB)
 460                 NewRet->setOperand(0, PN->getIncomingValueForBlock(Pred));
 461           // Update any PHI nodes in the returning block to realize that we no
 462           // longer branch to them.
 463           BB->removePredecessor(Pred);
 464           Pred->getInstList().erase(UncondBranch);
 465         }
 466
 467         // If we eliminated all predecessors of the block, delete the block now.
 468         if (pred_begin(BB) == pred_end(BB))
 469           // We know there are no successors, so just nuke the block.
 470           M->getBasicBlockList().erase(BB);
 471
 472
 473         return true;
 474       }
 475     }
 476   }
 477
 478   // Merge basic blocks into their predecessor if there is only one distinct
 479   // pred, and if there is only one distinct successor of the predecessor, and
 480   // if there are no PHI nodes.
 481   //
 482   pred_iterator PI(pred_begin(BB)), PE(pred_end(BB));
 483   BasicBlock *OnlyPred = *PI++;
 484   for (; PI != PE; ++PI)  // Search all predecessors, see if they are all same
 485     if (*PI != OnlyPred) {
 486       OnlyPred = 0;       // There are multiple different predecessors...
 487       break;
 488     }
 489
 490   BasicBlock *OnlySucc = 0;
 491   if (OnlyPred && OnlyPred != BB &&    // Don't break self loops
 492       OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) {
 493     // Check to see if there is only one distinct successor...
 494     succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred));
 495     OnlySucc = BB;
 496     for (; SI != SE; ++SI)
 497       if (*SI != OnlySucc) {
 498         OnlySucc = 0;     // There are multiple distinct successors!
 499         break;
 500       }
 501   }
 502
 503   if (OnlySucc) {
 504     //cerr << "Merging: " << BB << "into: " << OnlyPred;
 505     TerminatorInst *Term = OnlyPred->getTerminator();
 506
 507     // Resolve any PHI nodes at the start of the block.  They are all
 508     // guaranteed to have exactly one entry if they exist, unless there are
 509     // multiple duplicate (but guaranteed to be equal) entries for the
 510     // incoming edges.  This occurs when there are multiple edges from
 511     // OnlyPred to OnlySucc.
 512     //
 513     while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
 514       PN->replaceAllUsesWith(PN->getIncomingValue(0));
 515       BB->getInstList().pop_front();  // Delete the phi node...
 516     }
 517
 518     // Delete the unconditional branch from the predecessor...
 519     OnlyPred->getInstList().pop_back();
 520
 521     // Move all definitions in the successor to the predecessor...
 522     OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
 523
 524     // Make all PHI nodes that referred to BB now refer to Pred as their
 525     // source...
 526     BB->replaceAllUsesWith(OnlyPred);
 527
 528     std::string OldName = BB->getName();
 529
 530     // Erase basic block from the function...
 531     M->getBasicBlockList().erase(BB);
 532
 533     // Inherit predecessors name if it exists...
 534     if (!OldName.empty() && !OnlyPred->hasName())
 535       OnlyPred->setName(OldName);
 536
 537     return true;
 538   }
 539
 540   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
 541     if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator()))
 542       // Change br (X == 0 | X == 1), T, F into a switch instruction.
 543       if (BI->isConditional() && isa<Instruction>(BI->getCondition())) {
 544         Instruction *Cond = cast<Instruction>(BI->getCondition());
 545         // If this is a bunch of seteq's or'd together, or if it's a bunch of
 546         // 'setne's and'ed together, collect them.
 547         Value *CompVal = 0;
 548         std::vector<Constant*> Values;
 549         bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values);
 550         if (CompVal && CompVal->getType()->isInteger()) {
 551           // There might be duplicate constants in the list, which the switch
 552           // instruction can't handle, remove them now.
 553           std::sort(Values.begin(), Values.end());
 554           Values.erase(std::unique(Values.begin(), Values.end()), Values.end());
 555
 556           // Figure out which block is which destination.
 557           BasicBlock *DefaultBB = BI->getSuccessor(1);
 558           BasicBlock *EdgeBB    = BI->getSuccessor(0);
 559           if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB);
 560
 561           // Create the new switch instruction now.
 562           SwitchInst *New = new SwitchInst(CompVal, DefaultBB, BI);
 563
 564           // Add all of the 'cases' to the switch instruction.
 565           for (unsigned i = 0, e = Values.size(); i != e; ++i)
 566             New->addCase(Values[i], EdgeBB);
 567
 568           // We added edges from PI to the EdgeBB.  As such, if there were any
 569           // PHI nodes in EdgeBB, they need entries to be added corresponding to
 570           // the number of edges added.
 571           for (BasicBlock::iterator BBI = EdgeBB->begin();
 572                PHINode *PN = dyn_cast<PHINode>(BBI); ++BBI) {
 573             Value *InVal = PN->getIncomingValueForBlock(*PI);
 574             for (unsigned i = 0, e = Values.size()-1; i != e; ++i)
 575               PN->addIncoming(InVal, *PI);
 576           }
 577
 578           // Erase the old branch instruction.
 579           (*PI)->getInstList().erase(BI);
 580
 581           // Erase the potentially condition tree that was used to computed the
 582           // branch condition.
 583           ErasePossiblyDeadInstructionTree(Cond);
 584           return true;
 585         }
 586       }
 587
 588   // If there is a trivial two-entry PHI node in this basic block, and we can
 589   // eliminate it, do so now.
 590   if (PHINode *PN = dyn_cast<PHINode>(BB->begin()))
 591     if (PN->getNumIncomingValues() == 2) {
 592       // Ok, this is a two entry PHI node.  Check to see if this is a simple "if
 593       // statement", which has a very simple dominance structure.  Basically, we
 594       // are trying to find the condition that is being branched on, which
 595       // subsequently causes this merge to happen.  We really want control
 596       // dependence information for this check, but simplifycfg can't keep it up
 597       // to date, and this catches most of the cases we care about anyway.
 598       //
 599       BasicBlock *IfTrue, *IfFalse;
 600       if (Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse)) {
 601         //std::cerr << "FOUND IF CONDITION!  " << *IfCond << "  T: "
 602         //       << IfTrue->getName() << "  F: " << IfFalse->getName() << "\n";
 603
 604         // Figure out where to insert instructions as necessary.
 605         BasicBlock::iterator AfterPHIIt = BB->begin();
 606         while (isa<PHINode>(AfterPHIIt)) ++AfterPHIIt;
 607
 608         BasicBlock::iterator I = BB->begin();
 609         while (PHINode *PN = dyn_cast<PHINode>(I)) {
 610           ++I;
 611
 612           // If we can eliminate this PHI by directly computing it based on the
 613           // condition, do so now.  We can't eliminate PHI nodes where the
 614           // incoming values are defined in the conditional parts of the branch,
 615           // so check for this.
 616           //
 617           if (DominatesMergePoint(PN->getIncomingValue(0), BB) &&
 618               DominatesMergePoint(PN->getIncomingValue(1), BB)) {
 619             Value *TrueVal =
 620               PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse);
 621             Value *FalseVal =
 622               PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue);
 623
 624             // FIXME: when we have a 'select' statement, we can be completely
 625             // generic and clean here and let the instcombine pass clean up
 626             // after us, by folding the select instructions away when possible.
 627             //
 628             if (TrueVal == FalseVal) {
 629               // Degenerate case...
 630               PN->replaceAllUsesWith(TrueVal);
 631               BB->getInstList().erase(PN);
 632               Changed = true;
 633             } else if (isa<ConstantBool>(TrueVal) &&
 634                        isa<ConstantBool>(FalseVal)) {
 635               if (TrueVal == ConstantBool::True) {
 636                 // The PHI node produces the same thing as the condition.
 637                 PN->replaceAllUsesWith(IfCond);
 638               } else {
 639                 // The PHI node produces the inverse of the condition.  Insert a
 640                 // "NOT" instruction, which is really a XOR.
 641                 Value *InverseCond =
 642                   BinaryOperator::createNot(IfCond, IfCond->getName()+".inv",
 643                                             AfterPHIIt);
 644                 PN->replaceAllUsesWith(InverseCond);
 645               }
 646               BB->getInstList().erase(PN);
 647               Changed = true;
 648             } else if (isa<ConstantInt>(TrueVal) && isa<ConstantInt>(FalseVal)){
 649               // If this is a PHI of two constant integers, we insert a cast of
 650               // the boolean to the integer type in question, giving us 0 or 1.
 651               // Then we multiply this by the difference of the two constants,
 652               // giving us 0 if false, and the difference if true.  We add this
 653               // result to the base constant, giving us our final value.  We
 654               // rely on the instruction combiner to eliminate many special
 655               // cases, like turning multiplies into shifts when possible.
 656               std::string Name = PN->getName(); PN->setName("");
 657               Value *TheCast = new CastInst(IfCond, TrueVal->getType(),
 658                                             Name, AfterPHIIt);
 659               Constant *TheDiff = ConstantExpr::get(Instruction::Sub,
 660                                                     cast<Constant>(TrueVal),
 661                                                     cast<Constant>(FalseVal));
 662               Value *V = TheCast;
 663               if (TheDiff != ConstantInt::get(TrueVal->getType(), 1))
 664                 V = BinaryOperator::create(Instruction::Mul, TheCast,
 665                                            TheDiff, TheCast->getName()+".scale",
 666                                            AfterPHIIt);
 667               if (!cast<Constant>(FalseVal)->isNullValue())
 668                 V = BinaryOperator::create(Instruction::Add, V, FalseVal,
 669                                            V->getName()+".offs", AfterPHIIt);
 670               PN->replaceAllUsesWith(V);
 671               BB->getInstList().erase(PN);
 672               Changed = true;
 673             } else if (isa<ConstantInt>(FalseVal) &&
 674                        cast<Constant>(FalseVal)->isNullValue()) {
 675               // If the false condition is an integral zero value, we can
 676               // compute the PHI by multiplying the condition by the other
 677               // value.
 678               std::string Name = PN->getName(); PN->setName("");
 679               Value *TheCast = new CastInst(IfCond, TrueVal->getType(),
 680                                             Name+".c", AfterPHIIt);
 681               Value *V = BinaryOperator::create(Instruction::Mul, TrueVal,
 682                                                 TheCast, Name, AfterPHIIt);
 683               PN->replaceAllUsesWith(V);
 684               BB->getInstList().erase(PN);
 685               Changed = true;
 686             } else if (isa<ConstantInt>(TrueVal) &&
 687                        cast<Constant>(TrueVal)->isNullValue()) {
 688               // If the true condition is an integral zero value, we can compute
 689               // the PHI by multiplying the inverse condition by the other
 690               // value.
 691               std::string Name = PN->getName(); PN->setName("");
 692               Value *NotCond = BinaryOperator::createNot(IfCond, Name+".inv",
 693                                                          AfterPHIIt);
 694               Value *TheCast = new CastInst(NotCond, TrueVal->getType(),
 695                                             Name+".inv", AfterPHIIt);
 696               Value *V = BinaryOperator::create(Instruction::Mul, FalseVal,
 697                                                 TheCast, Name, AfterPHIIt);
 698               PN->replaceAllUsesWith(V);
 699               BB->getInstList().erase(PN);
 700               Changed = true;
 701             }
 702           }
 703         }
 704       }
 705     }
 706
 707   return Changed;
 708 }