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 //
  11 // TODO: This should REALLY be recursive instead of iterative.  Right now, we
  12 // scan linearly through values, removing unused ones as we go.  The problem is
  13 // that this may cause other earlier values to become unused.  To make sure that
  14 // we get them all, we iterate until things stop changing.  Instead, when
  15 // removing a value, recheck all of its operands to see if they are now unused.
  16 // Piece of cake, and more efficient as well.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #include "llvm/Module.h"
  21 #include "llvm/Method.h"
  22 #include "llvm/BasicBlock.h"
  23 #include "llvm/iTerminators.h"
  24 #include "llvm/Opt/AllOpts.h"
  25
  26 struct ConstPoolDCE {
  27   enum { EndOffs = 0 };
  28   static bool isDCEable(const Value *) { return true; }
  29 };
  30
  31 struct BasicBlockDCE {
  32   enum { EndOffs = 1 };
  33   static bool isDCEable(const Instruction *I) {
  34     return !I->hasSideEffects();
  35   }
  36 };
  37
  38 template<class ValueSubclass, class ItemParentType, class DCEController>
  39 static bool RemoveUnusedDefs(ValueHolder<ValueSubclass, ItemParentType> &Vals,
  40                              DCEController DCEControl) {
  41   bool Changed = false;
  42   typedef ValueHolder<ValueSubclass, ItemParentType> Container;
  43
  44   int Offset = DCEController::EndOffs;
  45   for (Container::iterator DI = Vals.begin(); DI != Vals.end()-Offset; ) {
  46     // Look for un"used" definitions...
  47     if ((*DI)->use_empty() && DCEController::isDCEable(*DI)) {
  48       // Bye bye
  49       delete Vals.remove(DI);
  50       Changed = true;
  51     } else {
  52       DI++;
  53     }
  54   }
  55   return Changed;
  56 }
  57
  58
  59 bool DoRemoveUnusedConstants(SymTabValue *S) {
  60   bool Changed = false;
  61   ConstantPool &CP = S->getConstantPool();
  62   for (ConstantPool::plane_iterator PI = CP.begin(); PI != CP.end(); ++PI)
  63     Changed |= RemoveUnusedDefs(**PI, ConstPoolDCE());
  64   return Changed;
  65 }
  66
  67
  68 static void ReplaceUsesWithConstant(Instruction *I) {
  69   // Get the method level constant pool
  70   ConstantPool &CP = I->getParent()->getParent()->getConstantPool();
  71
  72   ConstPoolVal *CPV = 0;
  73   ConstantPool::PlaneType *P;
  74   if (!CP.getPlane(I->getType(), P)) {  // Does plane exist?
  75     // Yes, is it empty?
  76     if (!P->empty()) CPV = P->front();
  77   }
  78
  79   if (CPV == 0) { // We don't have an existing constant to reuse.  Just add one.
  80     CPV = ConstPoolVal::getNullConstant(I->getType());  // Create a new constant
  81
  82     // Add the new value to the constant pool...
  83     CP.insert(CPV);
  84   }
  85
  86   // Make all users of this instruction reference the constant instead
  87   I->replaceAllUsesWith(CPV);
  88 }
  89
  90 static bool DoDCEPass(Method *M) {
  91   Method::BasicBlocksType::iterator BBIt;
  92   Method::BasicBlocksType &BBs = M->getBasicBlocks();
  93   bool Changed = false;
  94
  95   // Loop through now and remove instructions that have no uses...
  96   for (BBIt = BBs.begin(); BBIt != BBs.end(); BBIt++)
  97     Changed |= RemoveUnusedDefs((*BBIt)->getInstList(), BasicBlockDCE());
  98
  99   // Scan through and remove basic blocks that have no predecessors (except,
 100   // of course, the first one.  :)  (so skip first block)
 101   //
 102   for (BBIt = BBs.begin(), ++BBIt; BBIt != BBs.end(); BBIt++) {
 103     BasicBlock *BB = *BBIt;
 104     assert(BB->getTerminator() &&
 105            "Degenerate basic block encountered!");  // Empty bb???
 106
 107     if (BB->pred_begin() == BB->pred_end() &&
 108         !BB->hasConstantPoolReferences()) {
 109
 110       while (!BB->getInstList().empty()) {
 111         Instruction *I = BB->getInstList().front();
 112         // If this instruction is used, replace uses with an arbitrary
 113         // constant value.  Because control flow can't get here, we don't care
 114         // what we replace the value with.
 115         if (!I->use_empty()) ReplaceUsesWithConstant(I);
 116
 117         // Remove the instruction from the basic block
 118         BasicBlock::InstListType::iterator f = BB->getInstList().begin();
 119         delete BB->getInstList().remove(f);
 120       }
 121
 122       delete BBs.remove(BBIt);
 123       ++BBIt;  // remove puts use on the previous block, we want the next one
 124       Changed = true;
 125     }
 126   }
 127
 128   // Loop through an merge basic blocks into their predecessor if there is only
 129   // one, and if there is only one successor of the predecessor.
 130   //
 131   for (BBIt = BBs.begin(); BBIt != BBs.end(); BBIt++) {
 132     BasicBlock *BB = *BBIt;
 133
 134     // Is there exactly one predecessor to this block?
 135     BasicBlock::pred_iterator PI(BB->pred_begin());
 136     if (PI != BB->pred_end() && ++PI == BB->pred_end() &&
 137         !BB->hasConstantPoolReferences()) {
 138       BasicBlock *Pred = *BB->pred_begin();
 139       TerminatorInst *Term = Pred->getTerminator();
 140       if (Term == 0) continue; // Err... malformed basic block!
 141
 142       // Is it an unconditional branch?
 143       if (Term->getInstType() != Instruction::Br ||
 144           !((BranchInst*)Term)->isUnconditional())
 145         continue;  // Nope, maybe next time...
 146
 147       Changed = true;
 148
 149       // Make all branches to the predecessor now point to the successor...
 150       Pred->replaceAllUsesWith(BB);
 151
 152       // Move all definitions in the predecessor to the successor...
 153       BasicBlock::InstListType::iterator DI = Pred->getInstList().end();
 154       assert(Pred->getTerminator() &&
 155              "Degenerate basic block encountered!");  // Empty bb???
 156       delete Pred->getInstList().remove(--DI); // Remove terminator
 157
 158       while (Pred->getInstList().begin() != (DI = Pred->getInstList().end())) {
 159         Instruction *Def = Pred->getInstList().remove(--DI); // Remove from end
 160         BB->getInstList().push_front(Def);                   // Add to front...
 161       }
 162
 163       // Remove basic block from the method...
 164       BBs.remove(Pred);
 165
 166       // Always inherit predecessors name if it exists...
 167       if (Pred->hasName()) BB->setName(Pred->getName());
 168
 169       // So long you waste of a basic block you...
 170       delete Pred;
 171     }
 172   }
 173
 174   // Remove unused constants
 175   Changed |= DoRemoveUnusedConstants(M);
 176   return Changed;
 177 }
 178
 179
 180 // It is possible that we may require multiple passes over the code to fully
 181 // eliminate dead code.  Iterate until we are done.
 182 //
 183 bool DoDeadCodeElimination(Method *M) {
 184   bool Changed = false;
 185   while (DoDCEPass(M)) Changed = true;
 186   return Changed;
 187 }
 188
 189 bool DoDeadCodeElimination(Module *C) {
 190   bool Val = ApplyOptToAllMethods(C, DoDeadCodeElimination);
 191   while (DoRemoveUnusedConstants(C)) Val = true;
 192   return Val;
 193 }