lib/Transforms/Scalar/GCSE.cpp

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