lib/Transforms/Scalar/ADCE.cpp

   1 //===- ADCE.cpp - Code to perform agressive dead code elimination ---------===//
   2 //
   3 // This file implements "agressive" dead code elimination.  ADCE is DCe where
   4 // values are assumed to be dead until proven otherwise.  This is similar to
   5 // SCCP, except applied to the liveness of values.
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/Optimizations/DCE.h"
  10 #include "llvm/Instruction.h"
  11 #include "llvm/Type.h"
  12 #include "llvm/Analysis/Dominators.h"
  13 #include "llvm/Support/STLExtras.h"
  14 #include "llvm/Analysis/Writer.h"
  15 #include "llvm/CFG.h"
  16 #include "llvm/iTerminators.h"
  17 #include <set>
  18 #include <algorithm>
  19
  20 #define DEBUG_ADCE 1
  21
  22 //===----------------------------------------------------------------------===//
  23 // ADCE Class
  24 //
  25 // This class does all of the work of Agressive Dead Code Elimination.
  26 // It's public interface consists of a constructor and a doADCE() method.
  27 //
  28 class ADCE {
  29   Method *M;                            // The method that we are working on...
  30   vector<Instruction*>   WorkList;      // Instructions that just became live
  31   set<Instruction*>      LiveSet;       // The set of live instructions
  32   bool MadeChanges;
  33
  34   //===--------------------------------------------------------------------===//
  35   // The public interface for this class
  36   //
  37 public:
  38   // ADCE Ctor - Save the method to operate on...
  39   inline ADCE(Method *m) : M(m), MadeChanges(false) {}
  40
  41   // doADCE() - Run the Agressive Dead Code Elimination algorithm, returning
  42   // true if the method was modified.
  43   bool doADCE();
  44
  45   //===--------------------------------------------------------------------===//
  46   // The implementation of this class
  47   //
  48 private:
  49   inline void markInstructionLive(Instruction *I) {
  50     if (LiveSet.count(I)) return;
  51 #ifdef DEBUG_ADCE
  52     cerr << "Insn Live: " << I;
  53 #endif
  54     LiveSet.insert(I);
  55     WorkList.push_back(I);
  56   }
  57
  58   inline void markTerminatorLive(const BasicBlock *BB) {
  59 #ifdef DEBUG_ADCE
  60     cerr << "Terminat Live: " << BB->getTerminator();
  61 #endif
  62     markInstructionLive((Instruction*)BB->getTerminator());
  63   }
  64
  65   // fixupCFG - Walk the CFG in depth first order, eliminating references to
  66   // dead blocks.
  67   //
  68   BasicBlock *fixupCFG(BasicBlock *Head, set<BasicBlock*> &VisitedBlocks,
  69                        const set<BasicBlock*> &AliveBlocks);
  70 };
  71
  72
  73
  74 // doADCE() - Run the Agressive Dead Code Elimination algorithm, returning
  75 // true if the method was modified.
  76 //
  77 bool ADCE::doADCE() {
  78   // Compute the control dependence graph...  Note that this has a side effect
  79   // on the CFG: a new return bb is added and all returns are merged here.
  80   //
  81   cfg::DominanceFrontier CDG(cfg::DominatorSet(M, true));
  82
  83 #ifdef DEBUG_ADCE
  84   cerr << "Method: " << M;
  85 #endif
  86
  87   // Iterate over all of the instructions in the method, eliminating trivially
  88   // dead instructions, and marking instructions live that are known to be
  89   // needed.  Perform the walk in depth first order so that we avoid marking any
  90   // instructions live in basic blocks that are unreachable.  These blocks will
  91   // be eliminated later, along with the instructions inside.
  92   //
  93   for (cfg::df_iterator BBI = cfg::df_begin(M), BBE = cfg::df_end(M);
  94        BBI != BBE; ++BBI) {
  95     BasicBlock *BB = *BBI;
  96     for (BasicBlock::iterator II = BB->begin(), EI = BB->end(); II != EI; ) {
  97       Instruction *I = *II;
  98
  99       if (I->hasSideEffects() || I->getOpcode() == Instruction::Ret) {
 100         markInstructionLive(I);
 101       } else {
 102         // Check to see if anything is trivially dead
 103         if (I->use_size() == 0 && I->getType() != Type::VoidTy) {
 104           // Remove the instruction from it's basic block...
 105           delete BB->getInstList().remove(II);
 106           MadeChanges = true;
 107           continue;  // Don't increment the iterator past the current slot
 108         }
 109       }
 110
 111       ++II;  // Increment the inst iterator if the inst wasn't deleted
 112     }
 113   }
 114
 115 #ifdef DEBUG_ADCE
 116   cerr << "Processing work list\n";
 117 #endif
 118
 119   // AliveBlocks - Set of basic blocks that we know have instructions that are
 120   // alive in them...
 121   //
 122   set<BasicBlock*> AliveBlocks;
 123
 124   // Process the work list of instructions that just became live... if they
 125   // became live, then that means that all of their operands are neccesary as
 126   // well... make them live as well.
 127   //
 128   while (!WorkList.empty()) {
 129     Instruction *I = WorkList.back(); // Get an instruction that became live...
 130     WorkList.pop_back();
 131
 132     BasicBlock *BB = I->getParent();
 133     if (AliveBlocks.count(BB) == 0) {   // Basic block not alive yet...
 134       // Mark the basic block as being newly ALIVE... and mark all branches that
 135       // this block is control dependant on as being alive also...
 136       //
 137       AliveBlocks.insert(BB);   // Block is now ALIVE!
 138       cfg::DominanceFrontier::const_iterator It = CDG.find(BB);
 139       if (It != CDG.end()) {
 140         // Get the blocks that this node is control dependant on...
 141         const cfg::DominanceFrontier::DomSetType &CDB = It->second;
 142         for_each(CDB.begin(), CDB.end(),   // Mark all their terminators as live
 143                  bind_obj(this, &ADCE::markTerminatorLive));
 144       }
 145
 146       // If this basic block is live, then the terminator must be as well!
 147       markTerminatorLive(BB);
 148     }
 149
 150     // Loop over all of the operands of the live instruction, making sure that
 151     // they are known to be alive as well...
 152     //
 153     for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op) {
 154       if (Instruction *Operand = I->getOperand(op)->castInstruction())
 155         markInstructionLive(Operand);
 156     }
 157   }
 158
 159 #ifdef DEBUG_ADCE
 160   cerr << "Current Method: X = Live\n";
 161   for (Method::inst_iterator IL = M->inst_begin(); IL != M->inst_end(); ++IL) {
 162     if (LiveSet.count(*IL)) cerr << "X ";
 163     cerr << *IL;
 164   }
 165 #endif
 166
 167   // After the worklist is processed, recursively walk the CFG in depth first
 168   // order, patching up references to dead blocks...
 169   //
 170   set<BasicBlock*> VisitedBlocks;
 171   BasicBlock *EntryBlock = fixupCFG(M->front(), VisitedBlocks, AliveBlocks);
 172   if (EntryBlock && EntryBlock != M->front()) {
 173     if (EntryBlock->front()->isPHINode()) {
 174       // Cannot make the first block be a block with a PHI node in it! Instead,
 175       // strip the first basic block of the method to contain no instructions,
 176       // then add a simple branch to the "real" entry node...
 177       //
 178       BasicBlock *E = M->front();
 179       if (!E->front()->isTerminator() ||   // Check for an actual change...
 180           ((TerminatorInst*)E->front())->getNumSuccessors() != 1 ||
 181           ((TerminatorInst*)E->front())->getSuccessor(0) != EntryBlock) {
 182         E->getInstList().delete_all();      // Delete all instructions in block
 183         E->getInstList().push_back(new BranchInst(EntryBlock));
 184         MadeChanges = true;
 185       }
 186       AliveBlocks.insert(E);
 187
 188       // Next we need to change any PHI nodes in the entry block to refer to the
 189       // new predecessor node...
 190
 191
 192     } else {
 193       // We need to move the new entry block to be the first bb of the method.
 194       Method::iterator EBI = find(M->begin(), M->end(), EntryBlock);
 195       swap(*EBI, *M->begin());  // Exchange old location with start of method
 196       MadeChanges = true;
 197     }
 198   }
 199
 200   // Now go through and tell dead blocks to drop all of their references so they
 201   // can be safely deleted.
 202   //
 203   for (Method::iterator BI = M->begin(), BE = M->end(); BI != BE; ++BI) {
 204     BasicBlock *BB = *BI;
 205     if (!AliveBlocks.count(BB)) {
 206       BB->dropAllReferences();
 207     }
 208   }
 209
 210   // Now loop through all of the blocks and delete them.  We can safely do this
 211   // now because we know that there are no references to dead blocks (because
 212   // they have dropped all of their references...
 213   //
 214   for (Method::iterator BI = M->begin(); BI != M->end();) {
 215     if (!AliveBlocks.count(*BI)) {
 216       delete M->getBasicBlocks().remove(BI);
 217       MadeChanges = true;
 218       continue;                                     // Don't increment iterator
 219     }
 220     ++BI;                                           // Increment iterator...
 221   }
 222
 223   return MadeChanges;
 224 }
 225
 226
 227 // fixupCFG - Walk the CFG in depth first order, eliminating references to
 228 // dead blocks:
 229 //  If the BB is alive (in AliveBlocks):
 230 //   1. Eliminate all dead instructions in the BB
 231 //   2. Recursively traverse all of the successors of the BB:
 232 //      - If the returned successor is non-null, update our terminator to
 233 //         reference the returned BB
 234 //   3. Return 0 (no update needed)
 235 //
 236 //  If the BB is dead (not in AliveBlocks):
 237 //   1. Add the BB to the dead set
 238 //   2. Recursively traverse all of the successors of the block:
 239 //      - Only one shall return a nonnull value (or else this block should have
 240 //        been in the alive set).
 241 //   3. Return the nonnull child, or 0 if no non-null children.
 242 //
 243 BasicBlock *ADCE::fixupCFG(BasicBlock *BB, set<BasicBlock*> &VisitedBlocks,
 244                            const set<BasicBlock*> &AliveBlocks) {
 245   if (VisitedBlocks.count(BB)) return 0;   // Revisiting a node? No update.
 246   VisitedBlocks.insert(BB);                // We have now visited this node!
 247
 248 #ifdef DEBUG_ADCE
 249   cerr << "Fixing up BB: " << BB;
 250 #endif
 251
 252   if (AliveBlocks.count(BB)) {             // Is the block alive?
 253     // Yes it's alive: loop through and eliminate all dead instructions in block
 254     for (BasicBlock::iterator II = BB->begin(); II != BB->end()-1; ) {
 255       Instruction *I = *II;
 256       if (!LiveSet.count(I)) {             // Is this instruction alive?
 257         // Nope... remove the instruction from it's basic block...
 258         delete BB->getInstList().remove(II);
 259         MadeChanges = true;
 260         continue;                          // Don't increment II
 261       }
 262       ++II;
 263     }
 264
 265     // Recursively traverse successors of this basic block.
 266     cfg::succ_iterator SI = cfg::succ_begin(BB), SE = cfg::succ_end(BB);
 267     for (; SI != SE; ++SI) {
 268       BasicBlock *Succ = *SI;
 269       BasicBlock *Repl = fixupCFG(Succ, VisitedBlocks, AliveBlocks);
 270       if (Repl && Repl != Succ) {          // We have to replace the successor
 271         Succ->replaceAllUsesWith(Repl);
 272         MadeChanges = true;
 273       }
 274     }
 275     return BB;
 276   } else {                                 // Otherwise the block is dead...
 277     BasicBlock *ReturnBB = 0;              // Default to nothing live down here
 278
 279     // Recursively traverse successors of this basic block.
 280     cfg::succ_iterator SI = cfg::succ_begin(BB), SE = cfg::succ_end(BB);
 281     for (; SI != SE; ++SI) {
 282       BasicBlock *RetBB = fixupCFG(*SI, VisitedBlocks, AliveBlocks);
 283       if (RetBB) {
 284         assert(ReturnBB == 0 && "One one live child allowed!");
 285         ReturnBB = RetBB;
 286       }
 287     }
 288     return ReturnBB;                       // Return the result of traversal
 289   }
 290 }
 291
 292
 293
 294 // DoADCE - Execute the Agressive Dead Code Elimination Algorithm
 295 //
 296 bool opt::DoADCE(Method *M) {
 297   if (M->isExternal()) return false;
 298   ADCE DCE(M);
 299   return DCE.doADCE();
 300 }