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/Constant.h"
  16 #include "llvm/Intrinsics.h"
  17 #include "llvm/iPHINode.h"
  18 #include "llvm/iTerminators.h"
  19 #include "llvm/iOther.h"
  20 #include "llvm/Support/CFG.h"
  21 #include <algorithm>
  22 #include <functional>
  23
  24 namespace llvm {
  25
  26 // PropagatePredecessors - This gets "Succ" ready to have the predecessors from
  27 // "BB".  This is a little tricky because "Succ" has PHI nodes, which need to
  28 // have extra slots added to them to hold the merge edges from BB's
  29 // predecessors, and BB itself might have had PHI nodes in it.  This function
  30 // returns true (failure) if the Succ BB already has a predecessor that is a
  31 // predecessor of BB and incoming PHI arguments would not be discernible.
  32 //
  33 // Assumption: Succ is the single successor for BB.
  34 //
  35 static bool PropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
  36   assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
  37
  38   if (!isa<PHINode>(Succ->front()))
  39     return false;  // We can make the transformation, no problem.
  40
  41   // If there is more than one predecessor, and there are PHI nodes in
  42   // the successor, then we need to add incoming edges for the PHI nodes
  43   //
  44   const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB));
  45
  46   // Check to see if one of the predecessors of BB is already a predecessor of
  47   // Succ.  If so, we cannot do the transformation if there are any PHI nodes
  48   // with incompatible values coming in from the two edges!
  49   //
  50   for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); PI != PE; ++PI)
  51     if (find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) {
  52       // Loop over all of the PHI nodes checking to see if there are
  53       // incompatible values coming in.
  54       for (BasicBlock::iterator I = Succ->begin();
  55            PHINode *PN = dyn_cast<PHINode>(I); ++I) {
  56         // Loop up the entries in the PHI node for BB and for *PI if the values
  57         // coming in are non-equal, we cannot merge these two blocks (instead we
  58         // should insert a conditional move or something, then merge the
  59         // blocks).
  60         int Idx1 = PN->getBasicBlockIndex(BB);
  61         int Idx2 = PN->getBasicBlockIndex(*PI);
  62         assert(Idx1 != -1 && Idx2 != -1 &&
  63                "Didn't have entries for my predecessors??");
  64         if (PN->getIncomingValue(Idx1) != PN->getIncomingValue(Idx2))
  65           return true;  // Values are not equal...
  66       }
  67     }
  68
  69   // Loop over all of the PHI nodes in the successor BB
  70   for (BasicBlock::iterator I = Succ->begin();
  71        PHINode *PN = dyn_cast<PHINode>(I); ++I) {
  72     Value *OldVal = PN->removeIncomingValue(BB, false);
  73     assert(OldVal && "No entry in PHI for Pred BB!");
  74
  75     // If this incoming value is one of the PHI nodes in BB...
  76     if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
  77       PHINode *OldValPN = cast<PHINode>(OldVal);
  78       for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(),
  79              End = BBPreds.end(); PredI != End; ++PredI) {
  80         PN->addIncoming(OldValPN->getIncomingValueForBlock(*PredI), *PredI);
  81       }
  82     } else {
  83       for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(),
  84              End = BBPreds.end(); PredI != End; ++PredI) {
  85         // Add an incoming value for each of the new incoming values...
  86         PN->addIncoming(OldVal, *PredI);
  87       }
  88     }
  89   }
  90   return false;
  91 }
  92
  93
  94 // SimplifyCFG - This function is used to do simplification of a CFG.  For
  95 // example, it adjusts branches to branches to eliminate the extra hop, it
  96 // eliminates unreachable basic blocks, and does other "peephole" optimization
  97 // of the CFG.  It returns true if a modification was made.
  98 //
  99 // WARNING:  The entry node of a function may not be simplified.
 100 //
 101 bool SimplifyCFG(BasicBlock *BB) {
 102   bool Changed = false;
 103   Function *M = BB->getParent();
 104
 105   assert(BB && BB->getParent() && "Block not embedded in function!");
 106   assert(BB->getTerminator() && "Degenerate basic block encountered!");
 107   assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!");
 108
 109   // Check to see if the first instruction in this block is just an
 110   // 'llvm.unwind'.  If so, replace any invoke instructions which use this as an
 111   // exception destination with call instructions.
 112   //
 113   if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator()))
 114     if (BB->begin() == BasicBlock::iterator(UI)) {  // Empty block?
 115       std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB));
 116       while (!Preds.empty()) {
 117         BasicBlock *Pred = Preds.back();
 118         if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator()))
 119           if (II->getExceptionalDest() == BB) {
 120             // Insert a new branch instruction before the invoke, because this
 121             // is now a fall through...
 122             BranchInst *BI = new BranchInst(II->getNormalDest(), II);
 123             Pred->getInstList().remove(II);   // Take out of symbol table
 124
 125             // Insert the call now...
 126             std::vector<Value*> Args(II->op_begin()+3, II->op_end());
 127             CallInst *CI = new CallInst(II->getCalledValue(), Args,
 128                                         II->getName(), BI);
 129             // If the invoke produced a value, the Call now does instead
 130             II->replaceAllUsesWith(CI);
 131             delete II;
 132             Changed = true;
 133           }
 134
 135         Preds.pop_back();
 136       }
 137     }
 138
 139   // Remove basic blocks that have no predecessors... which are unreachable.
 140   if (pred_begin(BB) == pred_end(BB) &&
 141       !BB->hasConstantReferences()) {
 142     //cerr << "Removing BB: \n" << BB;
 143
 144     // Loop through all of our successors and make sure they know that one
 145     // of their predecessors is going away.
 146     for_each(succ_begin(BB), succ_end(BB),
 147              std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB));
 148
 149     while (!BB->empty()) {
 150       Instruction &I = BB->back();
 151       // If this instruction is used, replace uses with an arbitrary
 152       // constant value.  Because control flow can't get here, we don't care
 153       // what we replace the value with.  Note that since this block is
 154       // unreachable, and all values contained within it must dominate their
 155       // uses, that all uses will eventually be removed.
 156       if (!I.use_empty())
 157         // Make all users of this instruction reference the constant instead
 158         I.replaceAllUsesWith(Constant::getNullValue(I.getType()));
 159
 160       // Remove the instruction from the basic block
 161       BB->getInstList().pop_back();
 162     }
 163     M->getBasicBlockList().erase(BB);
 164     return true;
 165   }
 166
 167   // Check to see if we can constant propagate this terminator instruction
 168   // away...
 169   Changed |= ConstantFoldTerminator(BB);
 170
 171   // Check to see if this block has no non-phi instructions and only a single
 172   // successor.  If so, replace references to this basic block with references
 173   // to the successor.
 174   succ_iterator SI(succ_begin(BB));
 175   if (SI != succ_end(BB) && ++SI == succ_end(BB)) {  // One succ?
 176
 177     BasicBlock::iterator BBI = BB->begin();  // Skip over phi nodes...
 178     while (isa<PHINode>(*BBI)) ++BBI;
 179
 180     if (BBI->isTerminator()) {   // Terminator is the only non-phi instruction!
 181       BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor
 182
 183       if (Succ != BB) {   // Arg, don't hurt infinite loops!
 184         // If our successor has PHI nodes, then we need to update them to
 185         // include entries for BB's predecessors, not for BB itself.
 186         // Be careful though, if this transformation fails (returns true) then
 187         // we cannot do this transformation!
 188         //
 189         if (!PropagatePredecessorsForPHIs(BB, Succ)) {
 190           //cerr << "Killing Trivial BB: \n" << BB;
 191           std::string OldName = BB->getName();
 192
 193           std::vector<BasicBlock*>
 194             OldSuccPreds(pred_begin(Succ), pred_end(Succ));
 195
 196           // Move all PHI nodes in BB to Succ if they are alive, otherwise
 197           // delete them.
 198           while (PHINode *PN = dyn_cast<PHINode>(&BB->front()))
 199             if (PN->use_empty())
 200               BB->getInstList().erase(BB->begin());  // Nuke instruction...
 201             else {
 202               // The instruction is alive, so this means that Succ must have
 203               // *ONLY* had BB as a predecessor, and the PHI node is still valid
 204               // now.  Simply move it into Succ, because we know that BB
 205               // strictly dominated Succ.
 206               BB->getInstList().remove(BB->begin());
 207               Succ->getInstList().push_front(PN);
 208
 209               // We need to add new entries for the PHI node to account for
 210               // predecessors of Succ that the PHI node does not take into
 211               // account.  At this point, since we know that BB dominated succ,
 212               // this means that we should any newly added incoming edges should
 213               // use the PHI node as the value for these edges, because they are
 214               // loop back edges.
 215
 216               for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i)
 217                 if (OldSuccPreds[i] != BB)
 218                   PN->addIncoming(PN, OldSuccPreds[i]);
 219             }
 220
 221           // Everything that jumped to BB now goes to Succ...
 222           BB->replaceAllUsesWith(Succ);
 223
 224           // Delete the old basic block...
 225           M->getBasicBlockList().erase(BB);
 226
 227           if (!OldName.empty() && !Succ->hasName())  // Transfer name if we can
 228             Succ->setName(OldName);
 229
 230           //cerr << "Function after removal: \n" << M;
 231           return true;
 232         }
 233       }
 234     }
 235   }
 236
 237   // Merge basic blocks into their predecessor if there is only one distinct
 238   // pred, and if there is only one distinct successor of the predecessor, and
 239   // if there are no PHI nodes.
 240   //
 241   if (!BB->hasConstantReferences()) {
 242     pred_iterator PI(pred_begin(BB)), PE(pred_end(BB));
 243     BasicBlock *OnlyPred = *PI++;
 244     for (; PI != PE; ++PI)  // Search all predecessors, see if they are all same
 245       if (*PI != OnlyPred) {
 246         OnlyPred = 0;       // There are multiple different predecessors...
 247         break;
 248       }
 249
 250     BasicBlock *OnlySucc = 0;
 251     if (OnlyPred && OnlyPred != BB &&    // Don't break self loops
 252         OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) {
 253       // Check to see if there is only one distinct successor...
 254       succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred));
 255       OnlySucc = BB;
 256       for (; SI != SE; ++SI)
 257         if (*SI != OnlySucc) {
 258           OnlySucc = 0;     // There are multiple distinct successors!
 259           break;
 260         }
 261     }
 262
 263     if (OnlySucc) {
 264       //cerr << "Merging: " << BB << "into: " << OnlyPred;
 265       TerminatorInst *Term = OnlyPred->getTerminator();
 266
 267       // Resolve any PHI nodes at the start of the block.  They are all
 268       // guaranteed to have exactly one entry if they exist, unless there are
 269       // multiple duplicate (but guaranteed to be equal) entries for the
 270       // incoming edges.  This occurs when there are multiple edges from
 271       // OnlyPred to OnlySucc.
 272       //
 273       while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
 274         PN->replaceAllUsesWith(PN->getIncomingValue(0));
 275         BB->getInstList().pop_front();  // Delete the phi node...
 276       }
 277
 278       // Delete the unconditional branch from the predecessor...
 279       OnlyPred->getInstList().pop_back();
 280
 281       // Move all definitions in the successor to the predecessor...
 282       OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
 283
 284       // Make all PHI nodes that referred to BB now refer to Pred as their
 285       // source...
 286       BB->replaceAllUsesWith(OnlyPred);
 287
 288       std::string OldName = BB->getName();
 289
 290       // Erase basic block from the function...
 291       M->getBasicBlockList().erase(BB);
 292
 293       // Inherit predecessors name if it exists...
 294       if (!OldName.empty() && !OnlyPred->hasName())
 295         OnlyPred->setName(OldName);
 296
 297       return true;
 298     }
 299   }
 300
 301   return Changed;
 302 }
 303
 304 } // End llvm namespace