lib/Transforms/Scalar/ADCE.cpp

   1 //===- ADCE.cpp - Code to perform aggressive dead code elimination --------===//
   2 //
   3 // This file implements "aggressive" 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.h"
  10 #include "llvm/Transforms/Utils/Local.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/Constant.h"
  17 #include "llvm/Support/CFG.h"
  18 #include "Support/STLExtras.h"
  19 #include "Support/DepthFirstIterator.h"
  20 #include "Support/StatisticReporter.h"
  21 #include <algorithm>
  22 #include <iostream>
  23 using std::cerr;
  24
  25 static Statistic<> NumBlockRemoved("adce\t\t- Number of basic blocks removed");
  26 static Statistic<> NumInstRemoved ("adce\t\t- Number of instructions removed");
  27
  28 namespace {
  29
  30 //===----------------------------------------------------------------------===//
  31 // ADCE Class
  32 //
  33 // This class does all of the work of Aggressive Dead Code Elimination.
  34 // It's public interface consists of a constructor and a doADCE() method.
  35 //
  36 class ADCE : public FunctionPass {
  37   Function *Func;                       // The function that we are working on
  38   std::vector<Instruction*> WorkList;   // Instructions that just became live
  39   std::set<Instruction*>    LiveSet;    // The set of live instructions
  40
  41   //===--------------------------------------------------------------------===//
  42   // The public interface for this class
  43   //
  44 public:
  45   const char *getPassName() const { return "Aggressive Dead Code Elimination"; }
  46
  47   // Execute the Aggressive Dead Code Elimination Algorithm
  48   //
  49   virtual bool runOnFunction(Function *F) {
  50     Func = F;
  51     bool Changed = doADCE();
  52     assert(WorkList.empty());
  53     LiveSet.clear();
  54     return Changed;
  55   }
  56   // getAnalysisUsage - We require post dominance frontiers (aka Control
  57   // Dependence Graph)
  58   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  59     AU.addRequired(DominatorTree::PostDomID);
  60     AU.addRequired(DominanceFrontier::PostDomID);
  61   }
  62
  63
  64   //===--------------------------------------------------------------------===//
  65   // The implementation of this class
  66   //
  67 private:
  68   // doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning
  69   // true if the function was modified.
  70   //
  71   bool doADCE();
  72
  73   void markBlockAlive(BasicBlock *BB);
  74
  75   inline void markInstructionLive(Instruction *I) {
  76     if (LiveSet.count(I)) return;
  77     DEBUG(cerr << "Insn Live: " << I);
  78     LiveSet.insert(I);
  79     WorkList.push_back(I);
  80   }
  81
  82   inline void markTerminatorLive(const BasicBlock *BB) {
  83     DEBUG(cerr << "Terminat Live: " << BB->getTerminator());
  84     markInstructionLive((Instruction*)BB->getTerminator());
  85   }
  86 };
  87
  88 } // End of anonymous namespace
  89
  90 Pass *createAggressiveDCEPass() { return new ADCE(); }
  91
  92
  93 void ADCE::markBlockAlive(BasicBlock *BB) {
  94   // Mark the basic block as being newly ALIVE... and mark all branches that
  95   // this block is control dependant on as being alive also...
  96   //
  97   DominanceFrontier &CDG =
  98     getAnalysis<DominanceFrontier>(DominanceFrontier::PostDomID);
  99
 100   DominanceFrontier::const_iterator It = CDG.find(BB);
 101   if (It != CDG.end()) {
 102     // Get the blocks that this node is control dependant on...
 103     const DominanceFrontier::DomSetType &CDB = It->second;
 104     for_each(CDB.begin(), CDB.end(),   // Mark all their terminators as live
 105              bind_obj(this, &ADCE::markTerminatorLive));
 106   }
 107
 108   // If this basic block is live, then the terminator must be as well!
 109   markTerminatorLive(BB);
 110 }
 111
 112
 113 // doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning
 114 // true if the function was modified.
 115 //
 116 bool ADCE::doADCE() {
 117   bool MadeChanges = false;
 118
 119   // Iterate over all of the instructions in the function, eliminating trivially
 120   // dead instructions, and marking instructions live that are known to be
 121   // needed.  Perform the walk in depth first order so that we avoid marking any
 122   // instructions live in basic blocks that are unreachable.  These blocks will
 123   // be eliminated later, along with the instructions inside.
 124   //
 125   for (df_iterator<Function*> BBI = df_begin(Func), BBE = df_end(Func);
 126        BBI != BBE; ++BBI) {
 127     BasicBlock *BB = *BBI;
 128     for (BasicBlock::iterator II = BB->begin(), EI = BB->end(); II != EI; ) {
 129       Instruction *I = *II;
 130
 131       if (I->hasSideEffects() || I->getOpcode() == Instruction::Ret) {
 132         markInstructionLive(I);
 133         ++II;  // Increment the inst iterator if the inst wasn't deleted
 134       } else if (isInstructionTriviallyDead(I)) {
 135         // Remove the instruction from it's basic block...
 136         delete BB->getInstList().remove(II);
 137         ++NumInstRemoved;
 138         MadeChanges = true;
 139       } else {
 140         ++II;  // Increment the inst iterator if the inst wasn't deleted
 141       }
 142     }
 143   }
 144
 145   DEBUG(cerr << "Processing work list\n");
 146
 147   // AliveBlocks - Set of basic blocks that we know have instructions that are
 148   // alive in them...
 149   //
 150   std::set<BasicBlock*> AliveBlocks;
 151
 152   // Process the work list of instructions that just became live... if they
 153   // became live, then that means that all of their operands are neccesary as
 154   // well... make them live as well.
 155   //
 156   while (!WorkList.empty()) {
 157     Instruction *I = WorkList.back(); // Get an instruction that became live...
 158     WorkList.pop_back();
 159
 160     BasicBlock *BB = I->getParent();
 161     if (!AliveBlocks.count(BB)) {     // Basic block not alive yet...
 162       AliveBlocks.insert(BB);         // Block is now ALIVE!
 163       markBlockAlive(BB);             // Make it so now!
 164     }
 165
 166     // PHI nodes are a special case, because the incoming values are actually
 167     // defined in the predecessor nodes of this block, meaning that the PHI
 168     // makes the predecessors alive.
 169     //
 170     if (PHINode *PN = dyn_cast<PHINode>(I))
 171       for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
 172         if (!AliveBlocks.count(*PI)) {
 173           AliveBlocks.insert(BB);         // Block is now ALIVE!
 174           markBlockAlive(*PI);
 175         }
 176
 177     // Loop over all of the operands of the live instruction, making sure that
 178     // they are known to be alive as well...
 179     //
 180     for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op)
 181       if (Instruction *Operand = dyn_cast<Instruction>(I->getOperand(op)))
 182         markInstructionLive(Operand);
 183   }
 184
 185   if (DebugFlag) {
 186     cerr << "Current Function: X = Live\n";
 187     for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I)
 188       for (BasicBlock::iterator BI = (*I)->begin(), BE = (*I)->end();
 189            BI != BE; ++BI) {
 190         if (LiveSet.count(*BI)) cerr << "X ";
 191         cerr << *BI;
 192       }
 193   }
 194
 195   // Find the first postdominator of the entry node that is alive.  Make it the
 196   // new entry node...
 197   //
 198   DominatorTree &DT = getAnalysis<DominatorTree>(DominatorTree::PostDomID);
 199
 200   // If there are some blocks dead...
 201   if (AliveBlocks.size() != Func->size()) {
 202     // Insert a new entry node to eliminate the entry node as a special case.
 203     BasicBlock *NewEntry = new BasicBlock();
 204     NewEntry->getInstList().push_back(new BranchInst(Func->front()));
 205     Func->getBasicBlocks().push_front(NewEntry);
 206     AliveBlocks.insert(NewEntry);    // This block is always alive!
 207
 208     // Loop over all of the alive blocks in the function.  If any successor
 209     // blocks are not alive, we adjust the outgoing branches to branch to the
 210     // first live postdominator of the live block, adjusting any PHI nodes in
 211     // the block to reflect this.
 212     //
 213     for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I)
 214       if (AliveBlocks.count(*I)) {
 215         BasicBlock *BB = *I;
 216         TerminatorInst *TI = BB->getTerminator();
 217
 218         // Loop over all of the successors, looking for ones that are not alive
 219         for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 220           if (!AliveBlocks.count(TI->getSuccessor(i))) {
 221             // Scan up the postdominator tree, looking for the first
 222             // postdominator that is alive, and the last postdominator that is
 223             // dead...
 224             //
 225             DominatorTree::Node *LastNode = DT[TI->getSuccessor(i)];
 226             DominatorTree::Node *NextNode = LastNode->getIDom();
 227             while (!AliveBlocks.count(NextNode->getNode())) {
 228               LastNode = NextNode;
 229               NextNode = NextNode->getIDom();
 230             }
 231
 232             // Get the basic blocks that we need...
 233             BasicBlock *LastDead = LastNode->getNode();
 234             BasicBlock *NextAlive = NextNode->getNode();
 235
 236             // Make the conditional branch now go to the next alive block...
 237             TI->getSuccessor(i)->removePredecessor(BB);
 238             TI->setSuccessor(i, NextAlive);
 239
 240             // If there are PHI nodes in NextAlive, we need to add entries to
 241             // the PHI nodes for the new incoming edge.  The incoming values
 242             // should be identical to the incoming values for LastDead.
 243             //
 244             for (BasicBlock::iterator II = NextAlive->begin();
 245                  PHINode *PN = dyn_cast<PHINode>(*II); ++II) {
 246               // Get the incoming value for LastDead...
 247               int OldIdx = PN->getBasicBlockIndex(LastDead);
 248               assert(OldIdx != -1 && "LastDead is not a pred of NextAlive!");
 249               Value *InVal = PN->getIncomingValue(OldIdx);
 250
 251               // Add an incoming value for BB now...
 252               PN->addIncoming(InVal, BB);
 253             }
 254           }
 255
 256         // Now loop over all of the instructions in the basic block, telling
 257         // dead instructions to drop their references.  This is so that the next
 258         // sweep over the program can safely delete dead instructions without
 259         // other dead instructions still refering to them.
 260         //
 261         for (BasicBlock::iterator I = BB->begin(), E = BB->end()-1; I != E; ++I)
 262           if (!LiveSet.count(*I))               // Is this instruction alive?
 263             (*I)->dropAllReferences();          // Nope, drop references...
 264       }
 265   }
 266
 267   // Loop over all of the basic blocks in the function, removing dead
 268   // instructions from alive blocks, and dropping references of the dead blocks
 269   //
 270   for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) {
 271     BasicBlock *BB = *I;
 272     if (AliveBlocks.count(BB)) {
 273       for (BasicBlock::iterator II = BB->begin(); II != BB->end()-1; )
 274         if (!LiveSet.count(*II)) {             // Is this instruction alive?
 275           // Nope... remove the instruction from it's basic block...
 276           delete BB->getInstList().remove(II);
 277           ++NumInstRemoved;
 278           MadeChanges = true;
 279         } else {
 280           ++II;
 281         }
 282     } else {
 283       // Remove all outgoing edges from this basic block and convert the
 284       // terminator into a return instruction.
 285       vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB));
 286
 287       if (!Succs.empty()) {
 288         // Loop over all of the successors, removing this block from PHI node
 289         // entries that might be in the block...
 290         while (!Succs.empty()) {
 291           Succs.back()->removePredecessor(BB);
 292           Succs.pop_back();
 293         }
 294
 295         // Delete the old terminator instruction...
 296         delete BB->getInstList().remove(BB->end()-1);
 297         const Type *RetTy = Func->getReturnType();
 298         Instruction *New = new ReturnInst(RetTy != Type::VoidTy ?
 299                                           Constant::getNullValue(RetTy) : 0);
 300         BB->getInstList().push_back(New);
 301       }
 302
 303       BB->dropAllReferences();
 304       ++NumBlockRemoved;
 305       MadeChanges = true;
 306     }
 307   }
 308
 309   // Now loop through all of the blocks and delete them.  We can safely do this
 310   // now because we know that there are no references to dead blocks (because
 311   // they have dropped all of their references...
 312   //
 313   for (Function::iterator BI = Func->begin(); BI != Func->end(); )
 314     if (!AliveBlocks.count(*BI))
 315       delete Func->getBasicBlocks().remove(BI);
 316     else
 317       ++BI;                                           // Increment iterator...
 318
 319   return MadeChanges;
 320 }