lib/Transforms/Scalar/GCSE.cpp

   1 //===-- GCSE.cpp - SSA-based Global Common Subexpression Elimination ------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass is designed to be a very quick global transformation that
  11 // eliminates global common subexpressions from a function.  It does this by
  12 // using an existing value numbering implementation to identify the common
  13 // subexpressions, eliminating them when possible.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #define DEBUG_TYPE "gcse"
  18 #include "llvm/Transforms/Scalar.h"
  19 #include "llvm/Instructions.h"
  20 #include "llvm/Function.h"
  21 #include "llvm/Type.h"
  22 #include "llvm/Analysis/ConstantFolding.h"
  23 #include "llvm/Analysis/Dominators.h"
  24 #include "llvm/Analysis/ValueNumbering.h"
  25 #include "llvm/ADT/DepthFirstIterator.h"
  26 #include "llvm/ADT/Statistic.h"
  27 #include <algorithm>
  28 using namespace llvm;
  29
  30 STATISTIC(NumInstRemoved, "Number of instructions removed");
  31 STATISTIC(NumLoadRemoved, "Number of loads removed");
  32 STATISTIC(NumCallRemoved, "Number of calls removed");
  33 STATISTIC(NumNonInsts   , "Number of instructions removed due "
  34                           "to non-instruction values");
  35 STATISTIC(NumArgsRepl   , "Number of function arguments replaced "
  36                           "with constant values");
  37 namespace {
  38   struct GCSE : public FunctionPass {
  39     virtual bool runOnFunction(Function &F);
  40
  41   private:
  42     void ReplaceInstructionWith(Instruction *I, Value *V);
  43
  44     // This transformation requires dominator and immediate dominator info
  45     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  46       AU.setPreservesCFG();
  47       AU.addRequired<ETForest>();
  48       AU.addRequired<DominatorTree>();
  49       AU.addRequired<ValueNumbering>();
  50     }
  51   };
  52
  53   RegisterPass<GCSE> X("gcse", "Global Common Subexpression Elimination");
  54 }
  55
  56 // createGCSEPass - The public interface to this file...
  57 FunctionPass *llvm::createGCSEPass() { return new GCSE(); }
  58
  59 // GCSE::runOnFunction - This is the main transformation entry point for a
  60 // function.
  61 //
  62 bool GCSE::runOnFunction(Function &F) {
  63   bool Changed = false;
  64
  65   // Get pointers to the analysis results that we will be using...
  66   ETForest &EF = getAnalysis<ETForest>();
  67   ValueNumbering &VN = getAnalysis<ValueNumbering>();
  68   DominatorTree &DT = getAnalysis<DominatorTree>();
  69
  70   std::vector<Value*> EqualValues;
  71
  72   // Check for value numbers of arguments.  If the value numbering
  73   // implementation can prove that an incoming argument is a constant or global
  74   // value address, substitute it, making the argument dead.
  75   for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E; ++AI)
  76     if (!AI->use_empty()) {
  77       VN.getEqualNumberNodes(AI, EqualValues);
  78       if (!EqualValues.empty()) {
  79         for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
  80           if (isa<Constant>(EqualValues[i])) {
  81             AI->replaceAllUsesWith(EqualValues[i]);
  82             ++NumArgsRepl;
  83             Changed = true;
  84             break;
  85           }
  86         EqualValues.clear();
  87       }
  88     }
  89
  90   // Traverse the CFG of the function in dominator order, so that we see each
  91   // instruction after we see its operands.
  92   for (df_iterator<DominatorTree::Node*> DI = df_begin(DT.getRootNode()),
  93          E = df_end(DT.getRootNode()); DI != E; ++DI) {
  94     BasicBlock *BB = DI->getBlock();
  95
  96     // Remember which instructions we've seen in this basic block as we scan.
  97     std::set<Instruction*> BlockInsts;
  98
  99     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
 100       Instruction *Inst = I++;
 101
 102       if (Constant *C = ConstantFoldInstruction(Inst)) {
 103         ReplaceInstructionWith(Inst, C);
 104       } else if (Inst->getType() != Type::VoidTy) {
 105         // If this instruction computes a value, try to fold together common
 106         // instructions that compute it.
 107         //
 108         VN.getEqualNumberNodes(Inst, EqualValues);
 109
 110         // If this instruction computes a value that is already computed
 111         // elsewhere, try to recycle the old value.
 112         if (!EqualValues.empty()) {
 113           if (Inst == &*BB->begin())
 114             I = BB->end();
 115           else {
 116             I = Inst; --I;
 117           }
 118
 119           // First check to see if we were able to value number this instruction
 120           // to a non-instruction value.  If so, prefer that value over other
 121           // instructions which may compute the same thing.
 122           for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
 123             if (!isa<Instruction>(EqualValues[i])) {
 124               ++NumNonInsts;      // Keep track of # of insts repl with values
 125
 126               // Change all users of Inst to use the replacement and remove it
 127               // from the program.
 128               ReplaceInstructionWith(Inst, EqualValues[i]);
 129               Inst = 0;
 130               EqualValues.clear();  // don't enter the next loop
 131               break;
 132             }
 133
 134           // If there were no non-instruction values that this instruction
 135           // produces, find a dominating instruction that produces the same
 136           // value.  If we find one, use it's value instead of ours.
 137           for (unsigned i = 0, e = EqualValues.size(); i != e; ++i) {
 138             Instruction *OtherI = cast<Instruction>(EqualValues[i]);
 139             bool Dominates = false;
 140             if (OtherI->getParent() == BB)
 141               Dominates = BlockInsts.count(OtherI);
 142             else
 143               Dominates = EF.dominates(OtherI->getParent(), BB);
 144
 145             if (Dominates) {
 146               // Okay, we found an instruction with the same value as this one
 147               // and that dominates this one.  Replace this instruction with the
 148               // specified one.
 149               ReplaceInstructionWith(Inst, OtherI);
 150               Inst = 0;
 151               break;
 152             }
 153           }
 154
 155           EqualValues.clear();
 156
 157           if (Inst) {
 158             I = Inst; ++I;             // Deleted no instructions
 159           } else if (I == BB->end()) { // Deleted first instruction
 160             I = BB->begin();
 161           } else {                     // Deleted inst in middle of block.
 162             ++I;
 163           }
 164         }
 165
 166         if (Inst)
 167           BlockInsts.insert(Inst);
 168       }
 169     }
 170   }
 171
 172   // When the worklist is empty, return whether or not we changed anything...
 173   return Changed;
 174 }
 175
 176
 177 void GCSE::ReplaceInstructionWith(Instruction *I, Value *V) {
 178   if (isa<LoadInst>(I))
 179     ++NumLoadRemoved; // Keep track of loads eliminated
 180   if (isa<CallInst>(I))
 181     ++NumCallRemoved; // Keep track of calls eliminated
 182   ++NumInstRemoved;   // Keep track of number of insts eliminated
 183
 184   // Update value numbering
 185   getAnalysis<ValueNumbering>().deleteValue(I);
 186
 187   I->replaceAllUsesWith(V);
 188
 189   if (InvokeInst *II = dyn_cast<InvokeInst>(I)) {
 190     // Removing an invoke instruction requires adding a branch to the normal
 191     // destination and removing PHI node entries in the exception destination.
 192     new BranchInst(II->getNormalDest(), II);
 193     II->getUnwindDest()->removePredecessor(II->getParent());
 194   }
 195
 196   // Erase the instruction from the program.
 197   I->getParent()->getInstList().erase(I);
 198 }