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 "llvm/Support/CFG.h"
24 #include "Support/StatisticReporter.h"
27 static Statistic<> NumInstRemoved("gcse\t\t- Number of instructions removed");
28 static Statistic<> NumLoadRemoved("gcse\t\t- Number of loads removed");
31 class GCSE : public FunctionPass, public InstVisitor<GCSE, bool> {
32 set<Instruction*> WorkList;
33 DominatorSet *DomSetInfo;
34 ImmediateDominators *ImmDominator;
36 // BBContainsStore - Contains a value that indicates whether a basic block
37 // has a store or call instruction in it. This map is demand populated, so
38 // not having an entry means that the basic block has not been scanned yet.
40 map<BasicBlock*, bool> BBContainsStore;
42 const char *getPassName() const {
43 return "Global Common Subexpression Elimination";
46 virtual bool runOnFunction(Function *F);
48 // Visitation methods, these are invoked depending on the type of
49 // instruction being checked. They should return true if a common
50 // subexpression was folded.
52 bool visitUnaryOperator(Instruction *I);
53 bool visitBinaryOperator(Instruction *I);
54 bool visitGetElementPtrInst(GetElementPtrInst *I);
55 bool visitCastInst(CastInst *I){return visitUnaryOperator((Instruction*)I);}
56 bool visitShiftInst(ShiftInst *I) {
57 return visitBinaryOperator((Instruction*)I);
59 bool visitLoadInst(LoadInst *LI);
60 bool visitInstruction(Instruction *) { return false; }
63 void ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI);
64 void CommonSubExpressionFound(Instruction *I, Instruction *Other);
66 // TryToRemoveALoad - Try to remove one of L1 or L2. The problem with
67 // removing loads is that intervening stores might make otherwise identical
68 // load's yield different values. To ensure that this is not the case, we
69 // check that there are no intervening stores or calls between the
72 bool TryToRemoveALoad(LoadInst *L1, LoadInst *L2);
74 // CheckForInvalidatingInst - Return true if BB or any of the predecessors
75 // of BB (until DestBB) contain a store (or other invalidating) instruction.
77 bool CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
78 set<BasicBlock*> &VisitedSet);
80 // This transformation requires dominator and immediate dominator info
81 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
83 AU.addRequired(DominatorSet::ID);
84 AU.addRequired(ImmediateDominators::ID);
89 // createGCSEPass - The public interface to this file...
90 Pass *createGCSEPass() { return new GCSE(); }
93 // GCSE::runOnFunction - This is the main transformation entry point for a
96 bool GCSE::runOnFunction(Function *F) {
99 DomSetInfo = &getAnalysis<DominatorSet>();
100 ImmDominator = &getAnalysis<ImmediateDominators>();
102 // Step #1: Add all instructions in the function to the worklist for
103 // processing. All of the instructions are considered to be our
104 // subexpressions to eliminate if possible.
106 WorkList.insert(inst_begin(F), inst_end(F));
108 // Step #2: WorkList processing. Iterate through all of the instructions,
109 // checking to see if there are any additionally defined subexpressions in the
110 // program. If so, eliminate them!
112 while (!WorkList.empty()) {
113 Instruction *I = *WorkList.begin(); // Get an instruction from the worklist
114 WorkList.erase(WorkList.begin());
116 // Visit the instruction, dispatching to the correct visit function based on
117 // the instruction type. This does the checking.
122 // Clear out data structure so that next function starts fresh
123 BBContainsStore.clear();
125 // When the worklist is empty, return whether or not we changed anything...
130 // ReplaceInstWithInst - Destroy the instruction pointed to by SI, making all
131 // uses of the instruction use First now instead.
133 void GCSE::ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI) {
134 Instruction *Second = *SI;
136 //cerr << "DEL " << (void*)Second << Second;
138 // Add the first instruction back to the worklist
139 WorkList.insert(First);
141 // Add all uses of the second instruction to the worklist
142 for (Value::use_iterator UI = Second->use_begin(), UE = Second->use_end();
144 WorkList.insert(cast<Instruction>(*UI));
146 // Make all users of 'Second' now use 'First'
147 Second->replaceAllUsesWith(First);
149 // Erase the second instruction from the program
150 delete Second->getParent()->getInstList().remove(SI);
153 // CommonSubExpressionFound - The two instruction I & Other have been found to
154 // be common subexpressions. This function is responsible for eliminating one
155 // of them, and for fixing the worklist to be correct.
157 void GCSE::CommonSubExpressionFound(Instruction *I, Instruction *Other) {
161 WorkList.erase(Other); // Other may not actually be on the worklist anymore...
163 ++NumInstRemoved; // Keep track of number of instructions eliminated
165 // Handle the easy case, where both instructions are in the same basic block
166 BasicBlock *BB1 = I->getParent(), *BB2 = Other->getParent();
168 // Eliminate the second occuring instruction. Add all uses of the second
169 // instruction to the worklist.
171 // Scan the basic block looking for the "first" instruction
172 BasicBlock::iterator BI = BB1->begin();
173 while (*BI != I && *BI != Other) {
175 assert(BI != BB1->end() && "Instructions not found in parent BB!");
178 // Keep track of which instructions occurred first & second
179 Instruction *First = *BI;
180 Instruction *Second = I != First ? I : Other; // Get iterator to second inst
181 BI = find(BI, BB1->end(), Second);
182 assert(BI != BB1->end() && "Second instruction not found in parent block!");
184 // Destroy Second, using First instead.
185 ReplaceInstWithInst(First, BI);
187 // Otherwise, the two instructions are in different basic blocks. If one
188 // dominates the other instruction, we can simply use it
190 } else if (DomSetInfo->dominates(BB1, BB2)) { // I dom Other?
191 BasicBlock::iterator BI = find(BB2->begin(), BB2->end(), Other);
192 assert(BI != BB2->end() && "Other not in parent basic block!");
193 ReplaceInstWithInst(I, BI);
194 } else if (DomSetInfo->dominates(BB2, BB1)) { // Other dom I?
195 BasicBlock::iterator BI = find(BB1->begin(), BB1->end(), I);
196 assert(BI != BB1->end() && "I not in parent basic block!");
197 ReplaceInstWithInst(Other, BI);
199 // Handle the most general case now. In this case, neither I dom Other nor
200 // Other dom I. Because we are in SSA form, we are guaranteed that the
201 // operands of the two instructions both dominate the uses, so we _know_
202 // that there must exist a block that dominates both instructions (if the
203 // operands of the instructions are globals or constants, worst case we
204 // would get the entry node of the function). Search for this block now.
207 // Search up the immediate dominator chain of BB1 for the shared dominator
208 BasicBlock *SharedDom = (*ImmDominator)[BB1];
209 while (!DomSetInfo->dominates(SharedDom, BB2))
210 SharedDom = (*ImmDominator)[SharedDom];
212 // At this point, shared dom must dominate BOTH BB1 and BB2...
213 assert(SharedDom && DomSetInfo->dominates(SharedDom, BB1) &&
214 DomSetInfo->dominates(SharedDom, BB2) && "Dominators broken!");
216 // Rip 'I' out of BB1, and move it to the end of SharedDom.
217 BB1->getInstList().remove(I);
218 SharedDom->getInstList().insert(SharedDom->end()-1, I);
220 // Eliminate 'Other' now.
221 BasicBlock::iterator BI = find(BB2->begin(), BB2->end(), Other);
222 assert(BI != BB2->end() && "I not in parent basic block!");
223 ReplaceInstWithInst(I, BI);
227 //===----------------------------------------------------------------------===//
229 // Visitation methods, these are invoked depending on the type of instruction
230 // being checked. They should return true if a common subexpression was folded.
232 //===----------------------------------------------------------------------===//
234 bool GCSE::visitUnaryOperator(Instruction *I) {
235 Value *Op = I->getOperand(0);
236 Function *F = I->getParent()->getParent();
238 for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
240 if (Instruction *Other = dyn_cast<Instruction>(*UI))
241 // Check to see if this new binary operator is not I, but same operand...
242 if (Other != I && Other->getOpcode() == I->getOpcode() &&
243 Other->getOperand(0) == Op && // Is the operand the same?
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 // Check that the types are the same, since this code handles casts...
249 Other->getType() == I->getType()) {
251 // These instructions are identical. Handle the situation.
252 CommonSubExpressionFound(I, Other);
253 return true; // One instruction eliminated!
259 bool GCSE::visitBinaryOperator(Instruction *I) {
260 Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
261 Function *F = I->getParent()->getParent();
263 for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end();
265 if (Instruction *Other = dyn_cast<Instruction>(*UI))
266 // Check to see if this new binary operator is not I, but same operand...
267 if (Other != I && Other->getOpcode() == I->getOpcode() &&
268 // Are the LHS and RHS the same?
269 Other->getOperand(0) == LHS && Other->getOperand(1) == RHS &&
270 // Is it embeded in the same function? (This could be false if LHS
271 // is a constant or global!)
272 Other->getParent()->getParent() == F) {
274 // These instructions are identical. Handle the situation.
275 CommonSubExpressionFound(I, Other);
276 return true; // One instruction eliminated!
282 // IdenticalComplexInst - Return true if the two instructions are the same, by
283 // using a brute force comparison.
285 static bool IdenticalComplexInst(const Instruction *I1, const Instruction *I2) {
286 assert(I1->getOpcode() == I2->getOpcode());
287 // Equal if they are in the same function...
288 return I1->getParent()->getParent() == I2->getParent()->getParent() &&
289 // And return the same type...
290 I1->getType() == I2->getType() &&
291 // And have the same number of operands...
292 I1->getNumOperands() == I2->getNumOperands() &&
293 // And all of the operands are equal.
294 std::equal(I1->op_begin(), I1->op_end(), I2->op_begin());
297 bool GCSE::visitGetElementPtrInst(GetElementPtrInst *I) {
298 Value *Op = I->getOperand(0);
299 Function *F = I->getParent()->getParent();
301 for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
303 if (GetElementPtrInst *Other = dyn_cast<GetElementPtrInst>(*UI))
304 // Check to see if this new getelementptr is not I, but same operand...
305 if (Other != I && IdenticalComplexInst(I, Other)) {
306 // These instructions are identical. Handle the situation.
307 CommonSubExpressionFound(I, Other);
308 return true; // One instruction eliminated!
314 bool GCSE::visitLoadInst(LoadInst *LI) {
315 Value *Op = LI->getOperand(0);
316 Function *F = LI->getParent()->getParent();
318 for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
320 if (LoadInst *Other = dyn_cast<LoadInst>(*UI))
321 // Check to see if this new load is not LI, but has the same operands...
322 if (Other != LI && IdenticalComplexInst(LI, Other) &&
323 TryToRemoveALoad(LI, Other))
324 return true; // An instruction was eliminated!
329 static inline bool isInvalidatingInst(const Instruction *I) {
330 return I->getOpcode() == Instruction::Store ||
331 I->getOpcode() == Instruction::Call ||
332 I->getOpcode() == Instruction::Invoke;
335 // TryToRemoveALoad - Try to remove one of L1 or L2. The problem with removing
336 // loads is that intervening stores might make otherwise identical load's yield
337 // different values. To ensure that this is not the case, we check that there
338 // are no intervening stores or calls between the instructions.
340 bool GCSE::TryToRemoveALoad(LoadInst *L1, LoadInst *L2) {
341 // Figure out which load dominates the other one. If neither dominates the
342 // other we cannot eliminate one...
344 if (DomSetInfo->dominates(L2, L1))
345 std::swap(L1, L2); // Make L1 dominate L2
346 else if (!DomSetInfo->dominates(L1, L2))
347 return false; // Neither instruction dominates the other one...
349 BasicBlock *BB1 = L1->getParent(), *BB2 = L2->getParent();
351 // FIXME: This is incredibly painful with broken rep
352 BasicBlock::iterator L1I = std::find(BB1->begin(), BB1->end(), L1);
353 assert(L1I != BB1->end() && "Inst not in own parent?");
355 // L1 now dominates L2. Check to see if the intervening instructions between
356 // the two loads include a store or call...
358 if (BB1 == BB2) { // In same basic block?
359 // In this degenerate case, no checking of global basic blocks has to occur
360 // just check the instructions BETWEEN L1 & L2...
362 for (++L1I; *L1I != L2; ++L1I)
363 if (isInvalidatingInst(*L1I))
364 return false; // Cannot eliminate load
367 CommonSubExpressionFound(L1, L2);
370 // Make sure that there are no store instructions between L1 and the end of
371 // it's basic block...
373 for (++L1I; L1I != BB1->end(); ++L1I)
374 if (isInvalidatingInst(*L1I)) {
375 BBContainsStore[BB1] = true;
376 return false; // Cannot eliminate load
379 // Make sure that there are no store instructions between the start of BB2
380 // and the second load instruction...
382 for (BasicBlock::iterator II = BB2->begin(); *II != L2; ++II)
383 if (isInvalidatingInst(*II)) {
384 BBContainsStore[BB2] = true;
385 return false; // Cannot eliminate load
388 // Do a depth first traversal of the inverse CFG starting at L2's block,
389 // looking for L1's block. The inverse CFG is made up of the predecessor
390 // nodes of a block... so all of the edges in the graph are "backward".
392 set<BasicBlock*> VisitedSet;
393 for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
394 if (CheckForInvalidatingInst(*PI, BB1, VisitedSet))
398 CommonSubExpressionFound(L1, L2);
404 // CheckForInvalidatingInst - Return true if BB or any of the predecessors of BB
405 // (until DestBB) contain a store (or other invalidating) instruction.
407 bool GCSE::CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
408 set<BasicBlock*> &VisitedSet) {
409 // Found the termination point!
410 if (BB == DestBB || VisitedSet.count(BB)) return false;
412 // Avoid infinite recursion!
413 VisitedSet.insert(BB);
415 // Have we already checked this block?
416 map<BasicBlock*, bool>::iterator MI = BBContainsStore.find(BB);
418 if (MI != BBContainsStore.end()) {
419 // If this block is known to contain a store, exit the recursion early...
420 if (MI->second) return true;
421 // Otherwise continue checking predecessors...
423 // We don't know if this basic block contains an invalidating instruction.
425 bool HasStore = std::find_if(BB->begin(), BB->end(),
426 isInvalidatingInst) != BB->end();
427 if ((BBContainsStore[BB] = HasStore)) // Update map
428 return true; // Exit recursion early...
431 // Check all of our predecessor blocks...
432 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
433 if (CheckForInvalidatingInst(*PI, DestBB, VisitedSet))
436 // None of our predecessor blocks contain a store, and we don't either!