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