lib/Transforms/Scalar/GCSE.cpp

   1 //===-- GCSE.cpp - SSA based Global Common Subexpr 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 #include "llvm/Transforms/Scalar.h"
  18 #include "llvm/BasicBlock.h"
  19 #include "llvm/Constant.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/Type.h"
  22 #include "llvm/Analysis/Dominators.h"
  23 #include "llvm/Analysis/ValueNumbering.h"
  24 #include "llvm/Transforms/Utils/Local.h"
  25 #include "Support/DepthFirstIterator.h"
  26 #include "Support/Statistic.h"
  27 #include <algorithm>
  28 using namespace llvm;
  29
  30 namespace {
  31   Statistic<> NumInstRemoved("gcse", "Number of instructions removed");
  32   Statistic<> NumLoadRemoved("gcse", "Number of loads removed");
  33   Statistic<> NumCallRemoved("gcse", "Number of calls removed");
  34   Statistic<> NumNonInsts   ("gcse", "Number of instructions removed due "
  35                              "to non-instruction values");
  36
  37   struct GCSE : public FunctionPass {
  38     virtual bool runOnFunction(Function &F);
  39
  40   private:
  41     void ReplaceInstructionWith(Instruction *I, Value *V);
  42
  43     // This transformation requires dominator and immediate dominator info
  44     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  45       AU.setPreservesCFG();
  46       AU.addRequired<DominatorSet>();
  47       AU.addRequired<DominatorTree>();
  48       AU.addRequired<ValueNumbering>();
  49     }
  50   };
  51
  52   RegisterOpt<GCSE> X("gcse", "Global Common Subexpression Elimination");
  53 }
  54
  55 // createGCSEPass - The public interface to this file...
  56 FunctionPass *llvm::createGCSEPass() { return new GCSE(); }
  57
  58 // GCSE::runOnFunction - This is the main transformation entry point for a
  59 // function.
  60 //
  61 bool GCSE::runOnFunction(Function &F) {
  62   bool Changed = false;
  63
  64   // Get pointers to the analysis results that we will be using...
  65   DominatorSet &DS = getAnalysis<DominatorSet>();
  66   ValueNumbering &VN = getAnalysis<ValueNumbering>();
  67   DominatorTree &DT = getAnalysis<DominatorTree>();
  68
  69   std::vector<Value*> EqualValues;
  70
  71   // Traverse the CFG of the function in dominator order, so that we see each
  72   // instruction after we see its operands.
  73   for (df_iterator<DominatorTree::Node*> DI = df_begin(DT.getRootNode()),
  74          E = df_end(DT.getRootNode()); DI != E; ++DI) {
  75     BasicBlock *BB = DI->getBlock();
  76
  77     // Remember which instructions we've seen in this basic block as we scan.
  78     std::set<Instruction*> BlockInsts;
  79
  80     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
  81       Instruction *Inst = I++;
  82
  83       // If this instruction computes a value, try to fold together common
  84       // instructions that compute it.
  85       //
  86       if (Inst->getType() != Type::VoidTy) {
  87         VN.getEqualNumberNodes(Inst, EqualValues);
  88
  89         // If this instruction computes a value that is already computed
  90         // elsewhere, try to recycle the old value.
  91         if (!EqualValues.empty()) {
  92           if (Inst == &*BB->begin())
  93             I = BB->end();
  94           else {
  95             I = Inst; --I;
  96           }
  97
  98           // First check to see if we were able to value number this instruction
  99           // to a non-instruction value.  If so, prefer that value over other
 100           // instructions which may compute the same thing.
 101           for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
 102             if (!isa<Instruction>(EqualValues[i])) {
 103               ++NumNonInsts;      // Keep track of # of insts repl with values
 104
 105               // Change all users of Inst to use the replacement and remove it
 106               // from the program.
 107               ReplaceInstructionWith(Inst, EqualValues[i]);
 108               Inst = 0;
 109               EqualValues.clear();  // don't enter the next loop
 110               break;
 111             }
 112
 113           // If there were no non-instruction values that this instruction
 114           // produces, find a dominating instruction that produces the same
 115           // value.  If we find one, use it's value instead of ours.
 116           for (unsigned i = 0, e = EqualValues.size(); i != e; ++i) {
 117             Instruction *OtherI = cast<Instruction>(EqualValues[i]);
 118             bool Dominates = false;
 119             if (OtherI->getParent() == BB)
 120               Dominates = BlockInsts.count(OtherI);
 121             else
 122               Dominates = DS.dominates(OtherI->getParent(), BB);
 123
 124             if (Dominates) {
 125               // Okay, we found an instruction with the same value as this one
 126               // and that dominates this one.  Replace this instruction with the
 127               // specified one.
 128               ReplaceInstructionWith(Inst, OtherI);
 129               Inst = 0;
 130               break;
 131             }
 132           }
 133
 134           EqualValues.clear();
 135
 136           if (Inst) {
 137             I = Inst; ++I;             // Deleted no instructions
 138           } else if (I == BB->end()) { // Deleted first instruction
 139             I = BB->begin();
 140           } else {                     // Deleted inst in middle of block.
 141             ++I;
 142           }
 143         }
 144
 145         if (Inst)
 146           BlockInsts.insert(Inst);
 147       }
 148     }
 149   }
 150
 151   // When the worklist is empty, return whether or not we changed anything...
 152   return Changed;
 153 }
 154
 155
 156 void GCSE::ReplaceInstructionWith(Instruction *I, Value *V) {
 157   if (isa<LoadInst>(I))
 158     ++NumLoadRemoved; // Keep track of loads eliminated
 159   if (isa<CallInst>(I))
 160     ++NumCallRemoved; // Keep track of calls eliminated
 161   ++NumInstRemoved;   // Keep track of number of insts eliminated
 162
 163   // Update value numbering
 164   getAnalysis<ValueNumbering>().deleteInstruction(I);
 165
 166   // If we are not replacing the instruction with a constant, we cannot do
 167   // anything special.
 168   if (!isa<Constant>(V)) {
 169     I->replaceAllUsesWith(V);
 170
 171     // Erase the instruction from the program.
 172     I->getParent()->getInstList().erase(I);
 173     return;
 174   }
 175
 176   Constant *C = cast<Constant>(V);
 177   std::vector<User*> Users(I->use_begin(), I->use_end());
 178
 179   // Perform the replacement.
 180   I->replaceAllUsesWith(C);
 181
 182   // Erase the instruction from the program.
 183   I->getParent()->getInstList().erase(I);
 184
 185   // Check each user to see if we can constant fold it.
 186   while (!Users.empty()) {
 187     Instruction *U = cast<Instruction>(Users.back());
 188     Users.pop_back();
 189
 190     if (Constant *C = ConstantFoldInstruction(U)) {
 191       ReplaceInstructionWith(U, C);
 192
 193       // If the instruction used I more than once, it could be on the user list
 194       // multiple times.  Make sure we don't reprocess it.
 195       std::vector<User*>::iterator It = std::find(Users.begin(), Users.end(),U);
 196       while (It != Users.end()) {
 197         Users.erase(It);
 198         It = std::find(Users.begin(), Users.end(), U);
 199       }
 200     }
 201   }
 202 }