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