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