1 //===-- GCSE.cpp - SSA based Global Common Subexpr Elimination ------------===//
3 // This pass is designed to be a very quick global transformation that
4 // eliminates global common subexpressions from a function. It does this by
5 // using an existing value numbering implementation to identify the common
6 // subexpressions, eliminating them when possible.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/Transforms/Scalar.h"
11 #include "llvm/iMemory.h"
12 #include "llvm/Type.h"
13 #include "llvm/Analysis/Dominators.h"
14 #include "llvm/Analysis/ValueNumbering.h"
15 #include "llvm/Support/InstIterator.h"
16 #include "Support/StatisticReporter.h"
20 Statistic<> NumInstRemoved("gcse\t\t- Number of instructions removed");
21 Statistic<> NumLoadRemoved("gcse\t\t- Number of loads removed");
22 Statistic<> NumNonInsts ("gcse\t\t- Number of instructions removed due "
23 "to non-instruction values");
25 class GCSE : public FunctionPass {
26 std::set<Instruction*> WorkList;
27 DominatorSet *DomSetInfo;
29 ImmediateDominators *ImmDominator;
33 virtual bool runOnFunction(Function &F);
36 bool EliminateRedundancies(Instruction *I,std::vector<Value*> &EqualValues);
37 Instruction *EliminateCSE(Instruction *I, Instruction *Other);
38 void ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI);
40 // This transformation requires dominator and immediate dominator info
41 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
43 AU.addRequired<DominatorSet>();
44 AU.addRequired<ImmediateDominators>();
45 AU.addRequired<ValueNumbering>();
49 RegisterOpt<GCSE> X("gcse", "Global Common Subexpression Elimination");
52 // createGCSEPass - The public interface to this file...
53 Pass *createGCSEPass() { return new GCSE(); }
56 // GCSE::runOnFunction - This is the main transformation entry point for a
59 bool GCSE::runOnFunction(Function &F) {
62 // Get pointers to the analysis results that we will be using...
63 DomSetInfo = &getAnalysis<DominatorSet>();
65 ImmDominator = &getAnalysis<ImmediateDominators>();
67 VN = &getAnalysis<ValueNumbering>();
69 // Step #1: Add all instructions in the function to the worklist for
70 // processing. All of the instructions are considered to be our
71 // subexpressions to eliminate if possible.
73 WorkList.insert(inst_begin(F), inst_end(F));
75 // Step #2: WorkList processing. Iterate through all of the instructions,
76 // checking to see if there are any additionally defined subexpressions in the
77 // program. If so, eliminate them!
79 while (!WorkList.empty()) {
80 Instruction &I = **WorkList.begin(); // Get an instruction from the worklist
81 WorkList.erase(WorkList.begin());
83 // If this instruction computes a value, try to fold together common
84 // instructions that compute it.
86 if (I.getType() != Type::VoidTy) {
87 std::vector<Value*> EqualValues;
88 VN->getEqualNumberNodes(&I, EqualValues);
90 if (!EqualValues.empty())
91 Changed |= EliminateRedundancies(&I, EqualValues);
95 // When the worklist is empty, return whether or not we changed anything...
99 bool GCSE::EliminateRedundancies(Instruction *I,
100 std::vector<Value*> &EqualValues) {
101 // If the EqualValues set contains any non-instruction values, then we know
102 // that all of the instructions can be replaced with the non-instruction value
103 // because it is guaranteed to dominate all of the instructions in the
104 // function. We only have to do hard work if all we have are instructions.
106 for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
107 if (!isa<Instruction>(EqualValues[i])) {
108 // Found a non-instruction. Replace all instructions with the
111 Value *Replacement = EqualValues[i];
113 // Make sure we get I as well...
116 // Replace all instructions with the Replacement value.
117 for (i = 0; i != e; ++i)
118 if (Instruction *I = dyn_cast<Instruction>(EqualValues[i])) {
119 // Change all users of I to use Replacement.
120 I->replaceAllUsesWith(Replacement);
122 if (isa<LoadInst>(I))
123 ++NumLoadRemoved; // Keep track of loads eliminated
124 ++NumInstRemoved; // Keep track of number of instructions eliminated
125 ++NumNonInsts; // Keep track of number of insts repl with values
127 // Erase the instruction from the program.
128 I->getParent()->getInstList().erase(I);
134 // Remove duplicate entries from EqualValues...
135 std::sort(EqualValues.begin(), EqualValues.end());
136 EqualValues.erase(std::unique(EqualValues.begin(), EqualValues.end()),
139 // From this point on, EqualValues is logically a vector of instructions.
141 bool Changed = false;
142 EqualValues.push_back(I); // Make sure I is included...
143 while (EqualValues.size() > 1) {
144 // FIXME, this could be done better than simple iteration!
145 Instruction *Test = cast<Instruction>(EqualValues.back());
146 EqualValues.pop_back();
148 for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
149 if (Instruction *Ret = EliminateCSE(Test,
150 cast<Instruction>(EqualValues[i]))) {
151 if (Ret == Test) // Eliminated EqualValues[i]
152 EqualValues[i] = Test; // Make sure that we reprocess I at some point
161 // ReplaceInstWithInst - Destroy the instruction pointed to by SI, making all
162 // uses of the instruction use First now instead.
164 void GCSE::ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI) {
165 Instruction &Second = *SI;
167 //cerr << "DEL " << (void*)Second << Second;
169 // Add the first instruction back to the worklist
170 WorkList.insert(First);
172 // Add all uses of the second instruction to the worklist
173 for (Value::use_iterator UI = Second.use_begin(), UE = Second.use_end();
175 WorkList.insert(cast<Instruction>(*UI));
177 // Make all users of 'Second' now use 'First'
178 Second.replaceAllUsesWith(First);
180 // Erase the second instruction from the program
181 Second.getParent()->getInstList().erase(SI);
184 // EliminateCSE - The two instruction I & Other have been found to be common
185 // subexpressions. This function is responsible for eliminating one of them,
186 // and for fixing the worklist to be correct. The instruction that is preserved
187 // is returned from the function if the other is eliminated, otherwise null is
190 Instruction *GCSE::EliminateCSE(Instruction *I, Instruction *Other) {
194 WorkList.erase(Other); // Other may not actually be on the worklist anymore...
196 // Handle the easy case, where both instructions are in the same basic block
197 BasicBlock *BB1 = I->getParent(), *BB2 = Other->getParent();
198 Instruction *Ret = 0;
201 // Eliminate the second occuring instruction. Add all uses of the second
202 // instruction to the worklist.
204 // Scan the basic block looking for the "first" instruction
205 BasicBlock::iterator BI = BB1->begin();
206 while (&*BI != I && &*BI != Other) {
208 assert(BI != BB1->end() && "Instructions not found in parent BB!");
211 // Keep track of which instructions occurred first & second
212 Instruction *First = BI;
213 Instruction *Second = I != First ? I : Other; // Get iterator to second inst
216 // Destroy Second, using First instead.
217 ReplaceInstWithInst(First, BI);
220 // Otherwise, the two instructions are in different basic blocks. If one
221 // dominates the other instruction, we can simply use it
223 } else if (DomSetInfo->dominates(BB1, BB2)) { // I dom Other?
224 ReplaceInstWithInst(I, Other);
226 } else if (DomSetInfo->dominates(BB2, BB1)) { // Other dom I?
227 ReplaceInstWithInst(Other, I);
230 // This code is disabled because it has several problems:
231 // One, the actual assumption is wrong, as shown by this code:
232 // int "test"(int %X, int %Y) {
233 // %Z = add int %X, %Y
236 // %Q = add int %X, %Y
240 // Here there are no shared dominators. Additionally, this had the habit of
241 // moving computations where they were not always computed. For example, in
250 // In thiscase, the expression would be hoisted to outside the 'if' stmt,
251 // causing the expression to be evaluated, even for the if (d) path, which
252 // could cause problems, if, for example, it caused a divide by zero. In
253 // general the problem this case is trying to solve is better addressed with
259 // Handle the most general case now. In this case, neither I dom Other nor
260 // Other dom I. Because we are in SSA form, we are guaranteed that the
261 // operands of the two instructions both dominate the uses, so we _know_
262 // that there must exist a block that dominates both instructions (if the
263 // operands of the instructions are globals or constants, worst case we
264 // would get the entry node of the function). Search for this block now.
267 // Search up the immediate dominator chain of BB1 for the shared dominator
268 BasicBlock *SharedDom = (*ImmDominator)[BB1];
269 while (!DomSetInfo->dominates(SharedDom, BB2))
270 SharedDom = (*ImmDominator)[SharedDom];
272 // At this point, shared dom must dominate BOTH BB1 and BB2...
273 assert(SharedDom && DomSetInfo->dominates(SharedDom, BB1) &&
274 DomSetInfo->dominates(SharedDom, BB2) && "Dominators broken!");
276 // Rip 'I' out of BB1, and move it to the end of SharedDom.
277 BB1->getInstList().remove(I);
278 SharedDom->getInstList().insert(--SharedDom->end(), I);
280 // Eliminate 'Other' now.
281 ReplaceInstWithInst(I, Other);
285 if (isa<LoadInst>(Ret))
286 ++NumLoadRemoved; // Keep track of loads eliminated
287 ++NumInstRemoved; // Keep track of number of instructions eliminated
289 // Add all users of Ret to the worklist...
290 for (Value::use_iterator I = Ret->use_begin(), E = Ret->use_end(); I != E;++I)
291 if (Instruction *Inst = dyn_cast<Instruction>(*I))
292 WorkList.insert(Inst);