LLVM API Documentation
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 }