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 // examining the SSA value graph of the function, instead of doing slow, dense,
6 // bit-vector computations.
8 // This pass works best if it is proceeded with a simple constant propogation
9 // pass and an instruction combination pass because this pass does not do any
10 // value numbering (in order to be speedy).
12 // This pass does not attempt to CSE load instructions, because it does not use
13 // pointer analysis to determine when it is safe.
15 //===----------------------------------------------------------------------===//
17 #include "llvm/Transforms/Scalar.h"
18 #include "llvm/InstrTypes.h"
19 #include "llvm/iMemory.h"
20 #include "llvm/Analysis/Dominators.h"
21 #include "llvm/Support/InstVisitor.h"
22 #include "llvm/Support/InstIterator.h"
23 #include "Support/StatisticReporter.h"
26 static Statistic<> NumInstRemoved("gcse\t\t- Number of instructions removed");
29 class GCSE : public FunctionPass, public InstVisitor<GCSE, bool> {
30 set<Instruction*> WorkList;
31 DominatorSet *DomSetInfo;
32 ImmediateDominators *ImmDominator;
34 const char *getPassName() const {
35 return "Global Common Subexpression Elimination";
38 virtual bool runOnFunction(Function *F);
40 // Visitation methods, these are invoked depending on the type of
41 // instruction being checked. They should return true if a common
42 // subexpression was folded.
44 bool visitUnaryOperator(Instruction *I);
45 bool visitBinaryOperator(Instruction *I);
46 bool visitGetElementPtrInst(GetElementPtrInst *I);
47 bool visitCastInst(CastInst *I){return visitUnaryOperator((Instruction*)I);}
48 bool visitShiftInst(ShiftInst *I) {
49 return visitBinaryOperator((Instruction*)I);
51 bool visitInstruction(Instruction *) { return false; }
54 void ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI);
55 void CommonSubExpressionFound(Instruction *I, Instruction *Other);
57 // This transformation requires dominator and immediate dominator info
58 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
60 AU.addRequired(DominatorSet::ID);
61 AU.addRequired(ImmediateDominators::ID);
66 // createGCSEPass - The public interface to this file...
67 Pass *createGCSEPass() { return new GCSE(); }
70 // GCSE::runOnFunction - This is the main transformation entry point for a
73 bool GCSE::runOnFunction(Function *F) {
76 DomSetInfo = &getAnalysis<DominatorSet>();
77 ImmDominator = &getAnalysis<ImmediateDominators>();
79 // Step #1: Add all instructions in the function to the worklist for
80 // processing. All of the instructions are considered to be our
81 // subexpressions to eliminate if possible.
83 WorkList.insert(inst_begin(F), inst_end(F));
85 // Step #2: WorkList processing. Iterate through all of the instructions,
86 // checking to see if there are any additionally defined subexpressions in the
87 // program. If so, eliminate them!
89 while (!WorkList.empty()) {
90 Instruction *I = *WorkList.begin(); // Get an instruction from the worklist
91 WorkList.erase(WorkList.begin());
93 // Visit the instruction, dispatching to the correct visit function based on
94 // the instruction type. This does the checking.
99 // When the worklist is empty, return whether or not we changed anything...
104 // ReplaceInstWithInst - Destroy the instruction pointed to by SI, making all
105 // uses of the instruction use First now instead.
107 void GCSE::ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI) {
108 Instruction *Second = *SI;
110 //cerr << "DEL " << (void*)Second << Second;
112 // Add the first instruction back to the worklist
113 WorkList.insert(First);
115 // Add all uses of the second instruction to the worklist
116 for (Value::use_iterator UI = Second->use_begin(), UE = Second->use_end();
118 WorkList.insert(cast<Instruction>(*UI));
120 // Make all users of 'Second' now use 'First'
121 Second->replaceAllUsesWith(First);
123 // Erase the second instruction from the program
124 delete Second->getParent()->getInstList().remove(SI);
127 // CommonSubExpressionFound - The two instruction I & Other have been found to
128 // be common subexpressions. This function is responsible for eliminating one
129 // of them, and for fixing the worklist to be correct.
131 void GCSE::CommonSubExpressionFound(Instruction *I, Instruction *Other) {
132 // I has already been removed from the worklist, Other needs to be.
133 assert(I != Other && WorkList.count(I) == 0 && "I shouldn't be on worklist!");
135 WorkList.erase(Other); // Other may not actually be on the worklist anymore...
137 ++NumInstRemoved; // Keep track of number of instructions eliminated
139 // Handle the easy case, where both instructions are in the same basic block
140 BasicBlock *BB1 = I->getParent(), *BB2 = Other->getParent();
142 // Eliminate the second occuring instruction. Add all uses of the second
143 // instruction to the worklist.
145 // Scan the basic block looking for the "first" instruction
146 BasicBlock::iterator BI = BB1->begin();
147 while (*BI != I && *BI != Other) {
149 assert(BI != BB1->end() && "Instructions not found in parent BB!");
152 // Keep track of which instructions occurred first & second
153 Instruction *First = *BI;
154 Instruction *Second = I != First ? I : Other; // Get iterator to second inst
155 BI = find(BI, BB1->end(), Second);
156 assert(BI != BB1->end() && "Second instruction not found in parent block!");
158 // Destroy Second, using First instead.
159 ReplaceInstWithInst(First, BI);
161 // Otherwise, the two instructions are in different basic blocks. If one
162 // dominates the other instruction, we can simply use it
164 } else if (DomSetInfo->dominates(BB1, BB2)) { // I dom Other?
165 BasicBlock::iterator BI = find(BB2->begin(), BB2->end(), Other);
166 assert(BI != BB2->end() && "Other not in parent basic block!");
167 ReplaceInstWithInst(I, BI);
168 } else if (DomSetInfo->dominates(BB2, BB1)) { // Other dom I?
169 BasicBlock::iterator BI = find(BB1->begin(), BB1->end(), I);
170 assert(BI != BB1->end() && "I not in parent basic block!");
171 ReplaceInstWithInst(Other, BI);
173 // Handle the most general case now. In this case, neither I dom Other nor
174 // Other dom I. Because we are in SSA form, we are guaranteed that the
175 // operands of the two instructions both dominate the uses, so we _know_
176 // that there must exist a block that dominates both instructions (if the
177 // operands of the instructions are globals or constants, worst case we
178 // would get the entry node of the function). Search for this block now.
181 // Search up the immediate dominator chain of BB1 for the shared dominator
182 BasicBlock *SharedDom = (*ImmDominator)[BB1];
183 while (!DomSetInfo->dominates(SharedDom, BB2))
184 SharedDom = (*ImmDominator)[SharedDom];
186 // At this point, shared dom must dominate BOTH BB1 and BB2...
187 assert(SharedDom && DomSetInfo->dominates(SharedDom, BB1) &&
188 DomSetInfo->dominates(SharedDom, BB2) && "Dominators broken!");
190 // Rip 'I' out of BB1, and move it to the end of SharedDom.
191 BB1->getInstList().remove(I);
192 SharedDom->getInstList().insert(SharedDom->end()-1, I);
194 // Eliminate 'Other' now.
195 BasicBlock::iterator BI = find(BB2->begin(), BB2->end(), Other);
196 assert(BI != BB2->end() && "I not in parent basic block!");
197 ReplaceInstWithInst(I, BI);
201 //===----------------------------------------------------------------------===//
203 // Visitation methods, these are invoked depending on the type of instruction
204 // being checked. They should return true if a common subexpression was folded.
206 //===----------------------------------------------------------------------===//
208 bool GCSE::visitUnaryOperator(Instruction *I) {
209 Value *Op = I->getOperand(0);
210 Function *F = I->getParent()->getParent();
212 for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
214 if (Instruction *Other = dyn_cast<Instruction>(*UI))
215 // Check to see if this new binary operator is not I, but same operand...
216 if (Other != I && Other->getOpcode() == I->getOpcode() &&
217 Other->getOperand(0) == Op && // Is the operand the same?
218 // Is it embeded in the same function? (This could be false if LHS
219 // is a constant or global!)
220 Other->getParent()->getParent() == F &&
222 // Check that the types are the same, since this code handles casts...
223 Other->getType() == I->getType()) {
225 // These instructions are identical. Handle the situation.
226 CommonSubExpressionFound(I, Other);
227 return true; // One instruction eliminated!
233 bool GCSE::visitBinaryOperator(Instruction *I) {
234 Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
235 Function *F = I->getParent()->getParent();
237 for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end();
239 if (Instruction *Other = dyn_cast<Instruction>(*UI))
240 // Check to see if this new binary operator is not I, but same operand...
241 if (Other != I && Other->getOpcode() == I->getOpcode() &&
242 // Are the LHS and RHS the same?
243 Other->getOperand(0) == LHS && Other->getOperand(1) == RHS &&
244 // Is it embeded in the same function? (This could be false if LHS
245 // is a constant or global!)
246 Other->getParent()->getParent() == F) {
248 // These instructions are identical. Handle the situation.
249 CommonSubExpressionFound(I, Other);
250 return true; // One instruction eliminated!
256 bool GCSE::visitGetElementPtrInst(GetElementPtrInst *I) {
257 Value *Op = I->getOperand(0);
258 Function *F = I->getParent()->getParent();
260 for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
262 if (GetElementPtrInst *Other = dyn_cast<GetElementPtrInst>(*UI))
263 // Check to see if this new binary operator is not I, but same operand...
264 if (Other != I && Other->getParent()->getParent() == F &&
265 Other->getType() == I->getType()) {
267 // Check to see that all operators past the 0th are the same...
268 unsigned i = 1, e = I->getNumOperands();
270 if (I->getOperand(i) != Other->getOperand(i)) break;
273 // These instructions are identical. Handle the situation.
274 CommonSubExpressionFound(I, Other);
275 return true; // One instruction eliminated!