1 //===-- GCSE.cpp - SSA-based Global Common Subexpression Elimination ------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
15 // This pass is deprecated by the Global Value Numbering pass (which does a
16 // better job with its own value numbering).
18 //===----------------------------------------------------------------------===//
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"
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");
42 struct VISIBILITY_HIDDEN GCSE : public FunctionPass {
43 static char ID; // Pass identification, replacement for typeid
44 GCSE() : FunctionPass((intptr_t)&ID) {}
46 virtual bool runOnFunction(Function &F);
49 void ReplaceInstructionWith(Instruction *I, Value *V);
51 // This transformation requires dominator and immediate dominator info
52 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
54 AU.addRequired<DominatorTree>();
55 AU.addRequired<ValueNumbering>();
61 static RegisterPass<GCSE>
62 X("gcse", "Global Common Subexpression Elimination");
64 // createGCSEPass - The public interface to this file...
65 FunctionPass *llvm::createGCSEPass() { return new GCSE(); }
67 // GCSE::runOnFunction - This is the main transformation entry point for a
70 bool GCSE::runOnFunction(Function &F) {
73 // Get pointers to the analysis results that we will be using...
74 DominatorTree &DT = getAnalysis<DominatorTree>();
75 ValueNumbering &VN = getAnalysis<ValueNumbering>();
77 std::vector<Value*> EqualValues;
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]);
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();
103 // Remember which instructions we've seen in this basic block as we scan.
104 std::set<Instruction*> BlockInsts;
106 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
107 Instruction *Inst = I++;
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.
115 VN.getEqualNumberNodes(Inst, EqualValues);
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())
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
133 // Change all users of Inst to use the replacement and remove it
135 ReplaceInstructionWith(Inst, EqualValues[i]);
137 EqualValues.clear(); // don't enter the next loop
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);
150 Dominates = DT.dominates(OtherI->getParent(), BB);
153 // Okay, we found an instruction with the same value as this one
154 // and that dominates this one. Replace this instruction with the
156 ReplaceInstructionWith(Inst, OtherI);
165 I = Inst; ++I; // Deleted no instructions
166 } else if (I == BB->end()) { // Deleted first instruction
168 } else { // Deleted inst in middle of block.
174 BlockInsts.insert(Inst);
179 // When the worklist is empty, return whether or not we changed anything...
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
191 // Update value numbering
192 getAnalysis<ValueNumbering>().deleteValue(I);
194 I->replaceAllUsesWith(V);
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());
203 // Erase the instruction from the program.
204 I->eraseFromParent();