lib/Transforms/Scalar/DCE.cpp

   1 //===- DCE.cpp - Code to perform dead code elimination --------------------===//
   2 //
   3 // This file implements dead code elimination and basic block merging.
   4 //
   5 // Specifically, this:
   6 //   * removes definitions with no uses (including unused constants)
   7 //   * removes basic blocks with no predecessors
   8 //   * merges a basic block into its predecessor if there is only one and the
   9 //     predecessor only has one successor.
  10 //   * Eliminates PHI nodes for basic blocks with a single predecessor
  11 //   * Eliminates a basic block that only contains an unconditional branch
  12 //
  13 // TODO: This should REALLY be worklist driven instead of iterative.  Right now,
  14 // we scan linearly through values, removing unused ones as we go.  The problem
  15 // is that this may cause other earlier values to become unused.  To make sure
  16 // that we get them all, we iterate until things stop changing.  Instead, when
  17 // removing a value, recheck all of its operands to see if they are now unused.
  18 // Piece of cake, and more efficient as well.
  19 //
  20 // Note, this is not trivial, because we have to worry about invalidating
  21 // iterators.  :(
  22 //
  23 //===----------------------------------------------------------------------===//
  24
  25 #include "llvm/Module.h"
  26 #include "llvm/Method.h"
  27 #include "llvm/BasicBlock.h"
  28 #include "llvm/iTerminators.h"
  29 #include "llvm/iOther.h"
  30 #include "llvm/Opt/AllOpts.h"
  31 #include "llvm/Assembly/Writer.h"
  32 #include "llvm/CFG.h"
  33 #include "llvm/Tools/STLExtras.h"
  34 #include <algorithm>
  35
  36 using namespace cfg;
  37
  38 struct ConstPoolDCE {
  39   enum { EndOffs = 0 };
  40   static bool isDCEable(const Value *) { return true; }
  41 };
  42
  43 struct BasicBlockDCE {
  44   enum { EndOffs = 1 };
  45   static bool isDCEable(const Instruction *I) {
  46     return !I->hasSideEffects();
  47   }
  48 };
  49
  50
  51 template<class ValueSubclass, class ItemParentType, class DCEController>
  52 static bool RemoveUnusedDefs(ValueHolder<ValueSubclass, ItemParentType> &Vals,
  53                              DCEController DCEControl) {
  54   bool Changed = false;
  55   typedef ValueHolder<ValueSubclass, ItemParentType> Container;
  56
  57   int Offset = DCEController::EndOffs;
  58   for (Container::iterator DI = Vals.begin(); DI != Vals.end()-Offset; ) {
  59     // Look for un"used" definitions...
  60     if ((*DI)->use_empty() && DCEController::isDCEable(*DI)) {
  61       // Bye bye
  62       //cerr << "Removing: " << *DI;
  63       delete Vals.remove(DI);
  64       Changed = true;
  65     } else {
  66       ++DI;
  67     }
  68   }
  69   return Changed;
  70 }
  71
  72 // RemoveSingularPHIs - This removes PHI nodes from basic blocks that have only
  73 // a single predecessor.  This means that the PHI node must only have a single
  74 // RHS value and can be eliminated.
  75 //
  76 // This routine is very simple because we know that PHI nodes must be the first
  77 // things in a basic block, if they are present.
  78 //
  79 static bool RemoveSingularPHIs(BasicBlock *BB) {
  80   pred_iterator PI(pred_begin(BB));
  81   if (PI == pred_end(BB) || ++PI != pred_end(BB))
  82     return false;   // More than one predecessor...
  83
  84   Instruction *I = BB->front();
  85   if (!I->isPHINode()) return false;  // No PHI nodes
  86
  87   //cerr << "Killing PHIs from " << BB;
  88   //cerr << "Pred #0 = " << *pred_begin(BB);
  89
  90   //cerr << "Method == " << BB->getParent();
  91
  92   do {
  93     PHINode *PN = (PHINode*)I;
  94     assert(PN->getOperand(2) == 0 && "PHI node should only have one value!");
  95     Value *V = PN->getOperand(0);
  96
  97     PN->replaceAllUsesWith(V);      // Replace PHI node with its single value.
  98     delete BB->getInstList().remove(BB->begin());
  99
 100     I = BB->front();
 101   } while (I->isPHINode());
 102
 103   return true;  // Yes, we nuked at least one phi node
 104 }
 105
 106 bool DoRemoveUnusedConstants(SymTabValue *S) {
 107   bool Changed = false;
 108   ConstantPool &CP = S->getConstantPool();
 109   for (ConstantPool::plane_iterator PI = CP.begin(); PI != CP.end(); ++PI)
 110     Changed |= RemoveUnusedDefs(**PI, ConstPoolDCE());
 111   return Changed;
 112 }
 113
 114 static void ReplaceUsesWithConstant(Instruction *I) {
 115   // Get the method level constant pool
 116   ConstantPool &CP = I->getParent()->getParent()->getConstantPool();
 117
 118   ConstPoolVal *CPV = 0;
 119   ConstantPool::PlaneType *P;
 120   if (!CP.getPlane(I->getType(), P)) {  // Does plane exist?
 121     // Yes, is it empty?
 122     if (!P->empty()) CPV = P->front();
 123   }
 124
 125   if (CPV == 0) { // We don't have an existing constant to reuse.  Just add one.
 126     CPV = ConstPoolVal::getNullConstant(I->getType());  // Create a new constant
 127
 128     // Add the new value to the constant pool...
 129     CP.insert(CPV);
 130   }
 131
 132   // Make all users of this instruction reference the constant instead
 133   I->replaceAllUsesWith(CPV);
 134 }
 135
 136 // PropogatePredecessors - This gets "Succ" ready to have the predecessors from
 137 // "BB".  This is a little tricky because "Succ" has PHI nodes, which need to
 138 // have extra slots added to them to hold the merge edges from BB's
 139 // predecessors.
 140 //
 141 // Assumption: BB is the single predecessor of Succ.
 142 //
 143 static void PropogatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
 144   assert(Succ->front()->isPHINode() && "Only works on PHId BBs!");
 145
 146   // If there is more than one predecessor, and there are PHI nodes in
 147   // the successor, then we need to add incoming edges for the PHI nodes
 148   //
 149   const vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB));
 150
 151   BasicBlock::iterator I = Succ->begin();
 152   do {                     // Loop over all of the PHI nodes in the successor BB
 153     PHINode *PN = (PHINode*)*I;
 154     Value *OldVal = PN->removeIncomingValue(BB);
 155     assert(OldVal && "No entry in PHI for Pred BB!");
 156
 157     for (vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(),
 158            End = BBPreds.end(); PredI != End; ++PredI) {
 159       // Add an incoming value for each of the new incoming values...
 160       PN->addIncoming(OldVal, *PredI);
 161     }
 162
 163     ++I;
 164   } while ((*I)->isPHINode());
 165 }
 166
 167 static bool DoDCEPass(Method *M) {
 168   Method::iterator BBIt, BBEnd = M->end();
 169   if (M->begin() == BBEnd) return false;  // Nothing to do
 170   bool Changed = false;
 171
 172   // Loop through now and remove instructions that have no uses...
 173   for (BBIt = M->begin(); BBIt != BBEnd; ++BBIt) {
 174     Changed |= RemoveUnusedDefs((*BBIt)->getInstList(), BasicBlockDCE());
 175     Changed |= RemoveSingularPHIs(*BBIt);
 176   }
 177
 178   // Loop over all of the basic blocks (except the first one) and remove them
 179   // if they are unneeded...
 180   //
 181   for (BBIt = M->begin(), ++BBIt; BBIt != M->end(); ++BBIt) {
 182     BasicBlock *BB = *BBIt;
 183     assert(BB->getTerminator() && "Degenerate basic block encountered!");
 184
 185     // Remove basic blocks that have no predecessors... which are unreachable.
 186     if (pred_begin(BB) == pred_end(BB) &&
 187         !BB->hasConstantPoolReferences() && 0) {
 188       //cerr << "Removing BB: \n" << BB;
 189
 190       // Loop through all of our successors and make sure they know that one
 191       // of their predecessors is going away.
 192       for_each(succ_begin(BB), succ_end(BB),
 193                bind_obj(BB, &BasicBlock::removePredecessor));
 194
 195       while (!BB->empty()) {
 196         Instruction *I = BB->front();
 197         // If this instruction is used, replace uses with an arbitrary
 198         // constant value.  Because control flow can't get here, we don't care
 199         // what we replace the value with.
 200         if (!I->use_empty()) ReplaceUsesWithConstant(I);
 201
 202         // Remove the instruction from the basic block
 203         delete BB->getInstList().remove(BB->begin());
 204       }
 205       delete M->getBasicBlocks().remove(BBIt);
 206       --BBIt;  // remove puts use on the next block, we want the previous one
 207       Changed = true;
 208       continue;
 209     }
 210
 211     // Check to see if this block has no instructions and only a single
 212     // successor.  If so, replace block references with successor.
 213     succ_iterator SI(succ_begin(BB));
 214     if (SI != succ_end(BB) && ++SI == succ_end(BB)) {  // One succ?
 215       Instruction *I = BB->front();
 216       if (I->isTerminator()) {   // Terminator is the only instruction!
 217         BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor
 218         //cerr << "Killing Trivial BB: \n" << BB;
 219
 220         if (Succ != BB) {   // Arg, don't hurt infinite loops!
 221           if (Succ->front()->isPHINode()) {
 222             // If our successor has PHI nodes, then we need to update them to
 223             // include entries for BB's predecessors, not for BB itself.
 224             //
 225             PropogatePredecessorsForPHIs(BB, Succ);
 226           }
 227
 228           BB->replaceAllUsesWith(Succ);
 229
 230           BB = M->getBasicBlocks().remove(BBIt);
 231           --BBIt; // remove puts use on the next block, we want the previous one
 232
 233           if (BB->hasName() && !Succ->hasName())  // Transfer name if we can
 234             Succ->setName(BB->getName());
 235           delete BB;                              // Delete basic block
 236
 237           //cerr << "Method after removal: \n" << M;
 238           Changed = true;
 239           continue;
 240         }
 241       }
 242     }
 243
 244     // Merge basic blocks into their predecessor if there is only one pred,
 245     // and if there is only one successor of the predecessor.
 246     pred_iterator PI(pred_begin(BB));
 247     if (PI != pred_end(BB) && *PI != BB &&    // Not empty?  Not same BB?
 248         ++PI == pred_end(BB) && !BB->hasConstantPoolReferences()) {
 249       BasicBlock *Pred = *pred_begin(BB);
 250       TerminatorInst *Term = Pred->getTerminator();
 251       assert(Term != 0 && "malformed basic block without terminator!");
 252
 253       // Does the predecessor block only have a single successor?
 254       succ_iterator SI(succ_begin(Pred));
 255       if (++SI == succ_end(Pred)) {
 256         //cerr << "Merging: " << BB << "into: " << Pred;
 257
 258         // Delete the unconditianal branch from the predecessor...
 259         BasicBlock::iterator DI = Pred->end();
 260         assert(Pred->getTerminator() &&
 261                "Degenerate basic block encountered!");  // Empty bb???
 262         delete Pred->getInstList().remove(--DI);        // Destroy uncond branch
 263
 264         // Move all definitions in the succecessor to the predecessor...
 265         while (!BB->empty()) {
 266           DI = BB->begin();
 267           Instruction *Def = BB->getInstList().remove(DI); // Remove from front
 268           Pred->getInstList().push_back(Def);              // Add to end...
 269         }
 270
 271         // Remove basic block from the method... and advance iterator to the
 272         // next valid block...
 273         BB = M->getBasicBlocks().remove(BBIt);
 274         --BBIt;  // remove puts us on the NEXT bb.  We want the prev BB
 275         Changed = true;
 276
 277         // Make all PHI nodes that refered to BB now refer to Pred as their
 278         // source...
 279         BB->replaceAllUsesWith(Pred);
 280
 281         // Inherit predecessors name if it exists...
 282         if (BB->hasName() && !Pred->hasName()) Pred->setName(BB->getName());
 283
 284         // You ARE the weakest link... goodbye
 285         delete BB;
 286
 287         //WriteToVCG(M, "MergedInto");
 288       }
 289     }
 290   }
 291
 292   // Remove unused constants
 293   Changed |= DoRemoveUnusedConstants(M);
 294   return Changed;
 295 }
 296
 297
 298 // It is possible that we may require multiple passes over the code to fully
 299 // eliminate dead code.  Iterate until we are done.
 300 //
 301 bool DoDeadCodeElimination(Method *M) {
 302   bool Changed = false;
 303   while (DoDCEPass(M)) Changed = true;
 304   return Changed;
 305 }
 306
 307 bool DoDeadCodeElimination(Module *C) {
 308   bool Val = ApplyOptToAllMethods(C, DoDeadCodeElimination);
 309   while (DoRemoveUnusedConstants(C)) Val = true;
 310   return Val;
 311 }