LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

GCSE.cpp

Go to the documentation of this file.
00001 //===-- GCSE.cpp - SSA-based Global Common Subexpression Elimination ------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass is designed to be a very quick global transformation that
00011 // eliminates global common subexpressions from a function.  It does this by
00012 // using an existing value numbering implementation to identify the common
00013 // subexpressions, eliminating them when possible.
00014 //
00015 //===----------------------------------------------------------------------===//
00016 
00017 #include "llvm/Transforms/Scalar.h"
00018 #include "llvm/BasicBlock.h"
00019 #include "llvm/Constant.h"
00020 #include "llvm/Instructions.h"
00021 #include "llvm/Type.h"
00022 #include "llvm/Analysis/Dominators.h"
00023 #include "llvm/Analysis/ValueNumbering.h"
00024 #include "llvm/Transforms/Utils/Local.h"
00025 #include "llvm/ADT/DepthFirstIterator.h"
00026 #include "llvm/ADT/Statistic.h"
00027 #include <algorithm>
00028 using namespace llvm;
00029 
00030 namespace {
00031   Statistic<> NumInstRemoved("gcse", "Number of instructions removed");
00032   Statistic<> NumLoadRemoved("gcse", "Number of loads removed");
00033   Statistic<> NumCallRemoved("gcse", "Number of calls removed");
00034   Statistic<> NumNonInsts   ("gcse", "Number of instructions removed due "
00035                              "to non-instruction values");
00036   Statistic<> NumArgsRepl   ("gcse", "Number of function arguments replaced "
00037                              "with constant values");
00038 
00039   struct GCSE : public FunctionPass {
00040     virtual bool runOnFunction(Function &F);
00041 
00042   private:
00043     void ReplaceInstructionWith(Instruction *I, Value *V);
00044 
00045     // This transformation requires dominator and immediate dominator info
00046     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00047       AU.setPreservesCFG();
00048       AU.addRequired<DominatorSet>();
00049       AU.addRequired<DominatorTree>();
00050       AU.addRequired<ValueNumbering>();
00051     }
00052   };
00053 
00054   RegisterOpt<GCSE> X("gcse", "Global Common Subexpression Elimination");
00055 }
00056 
00057 // createGCSEPass - The public interface to this file...
00058 FunctionPass *llvm::createGCSEPass() { return new GCSE(); }
00059 
00060 // GCSE::runOnFunction - This is the main transformation entry point for a
00061 // function.
00062 //
00063 bool GCSE::runOnFunction(Function &F) {
00064   bool Changed = false;
00065 
00066   // Get pointers to the analysis results that we will be using...
00067   DominatorSet &DS = getAnalysis<DominatorSet>();
00068   ValueNumbering &VN = getAnalysis<ValueNumbering>();
00069   DominatorTree &DT = getAnalysis<DominatorTree>();
00070 
00071   std::vector<Value*> EqualValues;
00072 
00073   // Check for value numbers of arguments.  If the value numbering
00074   // implementation can prove that an incoming argument is a constant or global
00075   // value address, substitute it, making the argument dead.
00076   for (Function::aiterator AI = F.abegin(), E = F.aend(); AI != E; ++AI)
00077     if (!AI->use_empty()) {
00078       VN.getEqualNumberNodes(AI, EqualValues);
00079       if (!EqualValues.empty()) {
00080         for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
00081           if (isa<Constant>(EqualValues[i])) {
00082             AI->replaceAllUsesWith(EqualValues[i]);
00083             ++NumArgsRepl;
00084             Changed = true;
00085             break;
00086           }
00087         EqualValues.clear();
00088       }
00089     }
00090 
00091   // Traverse the CFG of the function in dominator order, so that we see each
00092   // instruction after we see its operands.
00093   for (df_iterator<DominatorTree::Node*> DI = df_begin(DT.getRootNode()),
00094          E = df_end(DT.getRootNode()); DI != E; ++DI) {
00095     BasicBlock *BB = DI->getBlock();
00096 
00097     // Remember which instructions we've seen in this basic block as we scan.
00098     std::set<Instruction*> BlockInsts;
00099 
00100     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
00101       Instruction *Inst = I++;
00102 
00103       // If this instruction computes a value, try to fold together common
00104       // instructions that compute it.
00105       //
00106       if (Inst->getType() != Type::VoidTy) {
00107         VN.getEqualNumberNodes(Inst, EqualValues);
00108 
00109         // If this instruction computes a value that is already computed
00110         // elsewhere, try to recycle the old value.
00111         if (!EqualValues.empty()) {
00112           if (Inst == &*BB->begin())
00113             I = BB->end();
00114           else {
00115             I = Inst; --I;
00116           }
00117           
00118           // First check to see if we were able to value number this instruction
00119           // to a non-instruction value.  If so, prefer that value over other
00120           // instructions which may compute the same thing.
00121           for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
00122             if (!isa<Instruction>(EqualValues[i])) {
00123               ++NumNonInsts;      // Keep track of # of insts repl with values
00124 
00125               // Change all users of Inst to use the replacement and remove it
00126               // from the program.
00127               ReplaceInstructionWith(Inst, EqualValues[i]);
00128               Inst = 0;
00129               EqualValues.clear();  // don't enter the next loop
00130               break;
00131             }
00132 
00133           // If there were no non-instruction values that this instruction
00134           // produces, find a dominating instruction that produces the same
00135           // value.  If we find one, use it's value instead of ours.
00136           for (unsigned i = 0, e = EqualValues.size(); i != e; ++i) {
00137             Instruction *OtherI = cast<Instruction>(EqualValues[i]);
00138             bool Dominates = false;
00139             if (OtherI->getParent() == BB)
00140               Dominates = BlockInsts.count(OtherI);
00141             else
00142               Dominates = DS.dominates(OtherI->getParent(), BB);
00143 
00144             if (Dominates) {
00145               // Okay, we found an instruction with the same value as this one
00146               // and that dominates this one.  Replace this instruction with the
00147               // specified one.
00148               ReplaceInstructionWith(Inst, OtherI);
00149               Inst = 0;
00150               break;
00151             }
00152           }
00153 
00154           EqualValues.clear();
00155 
00156           if (Inst) {
00157             I = Inst; ++I;             // Deleted no instructions
00158           } else if (I == BB->end()) { // Deleted first instruction
00159             I = BB->begin();
00160           } else {                     // Deleted inst in middle of block.
00161             ++I;
00162           }
00163         }
00164 
00165         if (Inst)
00166           BlockInsts.insert(Inst);
00167       }
00168     }
00169   }
00170 
00171   // When the worklist is empty, return whether or not we changed anything...
00172   return Changed;
00173 }
00174 
00175 
00176 void GCSE::ReplaceInstructionWith(Instruction *I, Value *V) {
00177   if (isa<LoadInst>(I))
00178     ++NumLoadRemoved; // Keep track of loads eliminated
00179   if (isa<CallInst>(I))
00180     ++NumCallRemoved; // Keep track of calls eliminated
00181   ++NumInstRemoved;   // Keep track of number of insts eliminated
00182 
00183   // Update value numbering
00184   getAnalysis<ValueNumbering>().deleteValue(I);
00185 
00186   // If we are not replacing the instruction with a constant, we cannot do
00187   // anything special.
00188   if (!isa<Constant>(V)) {
00189     I->replaceAllUsesWith(V);
00190 
00191     if (InvokeInst *II = dyn_cast<InvokeInst>(I)) {
00192       // Removing an invoke instruction requires adding a branch to the normal
00193       // destination and removing PHI node entries in the exception destination.
00194       new BranchInst(II->getNormalDest(), II);
00195       II->getUnwindDest()->removePredecessor(II->getParent());
00196     }
00197     
00198     // Erase the instruction from the program.
00199     I->getParent()->getInstList().erase(I);
00200     return;
00201   }
00202 
00203   Constant *C = cast<Constant>(V);
00204   std::vector<User*> Users(I->use_begin(), I->use_end());
00205 
00206   // Perform the replacement.
00207   I->replaceAllUsesWith(C);
00208 
00209   if (InvokeInst *II = dyn_cast<InvokeInst>(I)) {
00210     // Removing an invoke instruction requires adding a branch to the normal
00211     // destination and removing PHI node entries in the exception destination.
00212     new BranchInst(II->getNormalDest(), II);
00213     II->getUnwindDest()->removePredecessor(II->getParent());
00214   }
00215 
00216   // Erase the instruction from the program.
00217   I->getParent()->getInstList().erase(I);
00218   
00219   // Check each user to see if we can constant fold it.
00220   while (!Users.empty()) {
00221     Instruction *U = cast<Instruction>(Users.back());
00222     Users.pop_back();
00223 
00224     if (Constant *C = ConstantFoldInstruction(U)) {
00225       ReplaceInstructionWith(U, C);
00226 
00227       // If the instruction used I more than once, it could be on the user list
00228       // multiple times.  Make sure we don't reprocess it.
00229       std::vector<User*>::iterator It = std::find(Users.begin(), Users.end(),U);
00230       while (It != Users.end()) {
00231         Users.erase(It);
00232         It = std::find(Users.begin(), Users.end(), U);
00233       }
00234     }
00235   }
00236 }