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"
30 static Statistic<> NumInstRemoved("gcse\t\t- Number of instructions removed");
31 static Statistic<> NumLoadRemoved("gcse\t\t- Number of loads removed");
34 class GCSE : public FunctionPass, public InstVisitor<GCSE, bool> {
35 set<Instruction*> WorkList;
36 DominatorSet *DomSetInfo;
37 ImmediateDominators *ImmDominator;
39 // BBContainsStore - Contains a value that indicates whether a basic block
40 // has a store or call instruction in it. This map is demand populated, so
41 // not having an entry means that the basic block has not been scanned yet.
43 map<BasicBlock*, bool> BBContainsStore;
45 virtual bool runOnFunction(Function &F);
47 // Visitation methods, these are invoked depending on the type of
48 // instruction being checked. They should return true if a common
49 // subexpression was folded.
51 bool visitUnaryOperator(Instruction &I);
52 bool visitBinaryOperator(Instruction &I);
53 bool visitGetElementPtrInst(GetElementPtrInst &I);
54 bool visitCastInst(CastInst &I){return visitUnaryOperator((Instruction&)I);}
55 bool visitShiftInst(ShiftInst &I) {
56 return visitBinaryOperator((Instruction&)I);
58 bool visitLoadInst(LoadInst &LI);
59 bool visitInstruction(Instruction &) { return false; }
62 void ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI);
63 void CommonSubExpressionFound(Instruction *I, Instruction *Other);
65 // TryToRemoveALoad - Try to remove one of L1 or L2. The problem with
66 // removing loads is that intervening stores might make otherwise identical
67 // load's yield different values. To ensure that this is not the case, we
68 // check that there are no intervening stores or calls between the
71 bool TryToRemoveALoad(LoadInst *L1, LoadInst *L2);
73 // CheckForInvalidatingInst - Return true if BB or any of the predecessors
74 // of BB (until DestBB) contain a store (or other invalidating) instruction.
76 bool CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
77 set<BasicBlock*> &VisitedSet);
79 // This transformation requires dominator and immediate dominator info
80 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
82 AU.addRequired<DominatorSet>();
83 AU.addRequired<ImmediateDominators>();
87 RegisterOpt<GCSE> X("gcse", "Global Common Subexpression Elimination");
90 // createGCSEPass - The public interface to this file...
91 Pass *createGCSEPass() { return new GCSE(); }
94 // GCSE::runOnFunction - This is the main transformation entry point for a
97 bool GCSE::runOnFunction(Function &F) {
100 DomSetInfo = &getAnalysis<DominatorSet>();
101 ImmDominator = &getAnalysis<ImmediateDominators>();
103 // Step #1: Add all instructions in the function to the worklist for
104 // processing. All of the instructions are considered to be our
105 // subexpressions to eliminate if possible.
107 WorkList.insert(inst_begin(F), inst_end(F));
109 // Step #2: WorkList processing. Iterate through all of the instructions,
110 // checking to see if there are any additionally defined subexpressions in the
111 // program. If so, eliminate them!
113 while (!WorkList.empty()) {
114 Instruction &I = **WorkList.begin(); // Get an instruction from the worklist
115 WorkList.erase(WorkList.begin());
117 // Visit the instruction, dispatching to the correct visit function based on
118 // the instruction type. This does the checking.
123 // Clear out data structure so that next function starts fresh
124 BBContainsStore.clear();
126 // When the worklist is empty, return whether or not we changed anything...
131 // ReplaceInstWithInst - Destroy the instruction pointed to by SI, making all
132 // uses of the instruction use First now instead.
134 void GCSE::ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI) {
135 Instruction &Second = *SI;
137 //cerr << "DEL " << (void*)Second << Second;
139 // Add the first instruction back to the worklist
140 WorkList.insert(First);
142 // Add all uses of the second instruction to the worklist
143 for (Value::use_iterator UI = Second.use_begin(), UE = Second.use_end();
145 WorkList.insert(cast<Instruction>(*UI));
147 // Make all users of 'Second' now use 'First'
148 Second.replaceAllUsesWith(First);
150 // Erase the second instruction from the program
151 Second.getParent()->getInstList().erase(SI);
154 // CommonSubExpressionFound - The two instruction I & Other have been found to
155 // be common subexpressions. This function is responsible for eliminating one
156 // of them, and for fixing the worklist to be correct.
158 void GCSE::CommonSubExpressionFound(Instruction *I, Instruction *Other) {
162 WorkList.erase(Other); // Other may not actually be on the worklist anymore...
164 ++NumInstRemoved; // Keep track of number of instructions eliminated
166 // Handle the easy case, where both instructions are in the same basic block
167 BasicBlock *BB1 = I->getParent(), *BB2 = Other->getParent();
169 // Eliminate the second occuring instruction. Add all uses of the second
170 // instruction to the worklist.
172 // Scan the basic block looking for the "first" instruction
173 BasicBlock::iterator BI = BB1->begin();
174 while (&*BI != I && &*BI != Other) {
176 assert(BI != BB1->end() && "Instructions not found in parent BB!");
179 // Keep track of which instructions occurred first & second
180 Instruction *First = BI;
181 Instruction *Second = I != First ? I : Other; // Get iterator to second inst
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 ReplaceInstWithInst(I, Other);
192 } else if (DomSetInfo->dominates(BB2, BB1)) { // Other dom I?
193 ReplaceInstWithInst(Other, I);
195 // This code is disabled because it has several problems:
196 // One, the actual assumption is wrong, as shown by this code:
197 // int "test"(int %X, int %Y) {
198 // %Z = add int %X, %Y
201 // %Q = add int %X, %Y
205 // Here there are no shared dominators. Additionally, this had the habit of
206 // moving computations where they were not always computed. For example, in
215 // In thiscase, the expression would be hoisted to outside the 'if' stmt,
216 // causing the expression to be evaluated, even for the if (d) path, which
217 // could cause problems, if, for example, it caused a divide by zero. In
218 // general the problem this case is trying to solve is better addressed with
223 // Handle the most general case now. In this case, neither I dom Other nor
224 // Other dom I. Because we are in SSA form, we are guaranteed that the
225 // operands of the two instructions both dominate the uses, so we _know_
226 // that there must exist a block that dominates both instructions (if the
227 // operands of the instructions are globals or constants, worst case we
228 // would get the entry node of the function). Search for this block now.
231 // Search up the immediate dominator chain of BB1 for the shared dominator
232 BasicBlock *SharedDom = (*ImmDominator)[BB1];
233 while (!DomSetInfo->dominates(SharedDom, BB2))
234 SharedDom = (*ImmDominator)[SharedDom];
236 // At this point, shared dom must dominate BOTH BB1 and BB2...
237 assert(SharedDom && DomSetInfo->dominates(SharedDom, BB1) &&
238 DomSetInfo->dominates(SharedDom, BB2) && "Dominators broken!");
240 // Rip 'I' out of BB1, and move it to the end of SharedDom.
241 BB1->getInstList().remove(I);
242 SharedDom->getInstList().insert(--SharedDom->end(), I);
244 // Eliminate 'Other' now.
245 ReplaceInstWithInst(I, Other);
250 //===----------------------------------------------------------------------===//
252 // Visitation methods, these are invoked depending on the type of instruction
253 // being checked. They should return true if a common subexpression was folded.
255 //===----------------------------------------------------------------------===//
257 bool GCSE::visitUnaryOperator(Instruction &I) {
258 Value *Op = I.getOperand(0);
259 Function *F = I.getParent()->getParent();
261 for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
263 if (Instruction *Other = dyn_cast<Instruction>(*UI))
264 // Check to see if this new binary operator is not I, but same operand...
265 if (Other != &I && Other->getOpcode() == I.getOpcode() &&
266 Other->getOperand(0) == Op && // Is the operand the same?
267 // Is it embeded in the same function? (This could be false if LHS
268 // is a constant or global!)
269 Other->getParent()->getParent() == F &&
271 // Check that the types are the same, since this code handles casts...
272 Other->getType() == I.getType()) {
274 // These instructions are identical. Handle the situation.
275 CommonSubExpressionFound(&I, Other);
276 return true; // One instruction eliminated!
282 // isIdenticalBinaryInst - Return true if the two binary instructions are
285 static inline bool isIdenticalBinaryInst(const Instruction &I1,
286 const Instruction *I2) {
287 // Is it embeded in the same function? (This could be false if LHS
288 // is a constant or global!)
289 if (I1.getOpcode() != I2->getOpcode() ||
290 I1.getParent()->getParent() != I2->getParent()->getParent())
293 // They are identical if both operands are the same!
294 if (I1.getOperand(0) == I2->getOperand(0) &&
295 I1.getOperand(1) == I2->getOperand(1))
298 // If the instruction is commutative and associative, the instruction can
299 // match if the operands are swapped!
301 if ((I1.getOperand(0) == I2->getOperand(1) &&
302 I1.getOperand(1) == I2->getOperand(0)) &&
303 (I1.getOpcode() == Instruction::Add ||
304 I1.getOpcode() == Instruction::Mul ||
305 I1.getOpcode() == Instruction::And ||
306 I1.getOpcode() == Instruction::Or ||
307 I1.getOpcode() == Instruction::Xor))
313 bool GCSE::visitBinaryOperator(Instruction &I) {
314 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
315 Function *F = I.getParent()->getParent();
317 for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end();
319 if (Instruction *Other = dyn_cast<Instruction>(*UI))
320 // Check to see if this new binary operator is not I, but same operand...
321 if (Other != &I && isIdenticalBinaryInst(I, Other)) {
322 // These instructions are identical. Handle the situation.
323 CommonSubExpressionFound(&I, Other);
324 return true; // One instruction eliminated!
330 // IdenticalComplexInst - Return true if the two instructions are the same, by
331 // using a brute force comparison.
333 static bool IdenticalComplexInst(const Instruction *I1, const Instruction *I2) {
334 assert(I1->getOpcode() == I2->getOpcode());
335 // Equal if they are in the same function...
336 return I1->getParent()->getParent() == I2->getParent()->getParent() &&
337 // And return the same type...
338 I1->getType() == I2->getType() &&
339 // And have the same number of operands...
340 I1->getNumOperands() == I2->getNumOperands() &&
341 // And all of the operands are equal.
342 std::equal(I1->op_begin(), I1->op_end(), I2->op_begin());
345 bool GCSE::visitGetElementPtrInst(GetElementPtrInst &I) {
346 Value *Op = I.getOperand(0);
347 Function *F = I.getParent()->getParent();
349 for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
351 if (GetElementPtrInst *Other = dyn_cast<GetElementPtrInst>(*UI))
352 // Check to see if this new getelementptr is not I, but same operand...
353 if (Other != &I && IdenticalComplexInst(&I, Other)) {
354 // These instructions are identical. Handle the situation.
355 CommonSubExpressionFound(&I, Other);
356 return true; // One instruction eliminated!
362 bool GCSE::visitLoadInst(LoadInst &LI) {
363 Value *Op = LI.getOperand(0);
364 Function *F = LI.getParent()->getParent();
366 for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
368 if (LoadInst *Other = dyn_cast<LoadInst>(*UI))
369 // Check to see if this new load is not LI, but has the same operands...
370 if (Other != &LI && IdenticalComplexInst(&LI, Other) &&
371 TryToRemoveALoad(&LI, Other))
372 return true; // An instruction was eliminated!
377 static inline bool isInvalidatingInst(const Instruction &I) {
378 return I.getOpcode() == Instruction::Store ||
379 I.getOpcode() == Instruction::Call ||
380 I.getOpcode() == Instruction::Invoke;
383 // TryToRemoveALoad - Try to remove one of L1 or L2. The problem with removing
384 // loads is that intervening stores might make otherwise identical load's yield
385 // different values. To ensure that this is not the case, we check that there
386 // are no intervening stores or calls between the instructions.
388 bool GCSE::TryToRemoveALoad(LoadInst *L1, LoadInst *L2) {
389 // Figure out which load dominates the other one. If neither dominates the
390 // other we cannot eliminate one...
392 if (DomSetInfo->dominates(L2, L1))
393 std::swap(L1, L2); // Make L1 dominate L2
394 else if (!DomSetInfo->dominates(L1, L2))
395 return false; // Neither instruction dominates the other one...
397 BasicBlock *BB1 = L1->getParent(), *BB2 = L2->getParent();
399 BasicBlock::iterator L1I = L1;
401 // L1 now dominates L2. Check to see if the intervening instructions between
402 // the two loads include a store or call...
404 if (BB1 == BB2) { // In same basic block?
405 // In this degenerate case, no checking of global basic blocks has to occur
406 // just check the instructions BETWEEN L1 & L2...
408 for (++L1I; &*L1I != L2; ++L1I)
409 if (isInvalidatingInst(*L1I))
410 return false; // Cannot eliminate load
413 CommonSubExpressionFound(L1, L2);
416 // Make sure that there are no store instructions between L1 and the end of
417 // it's basic block...
419 for (++L1I; L1I != BB1->end(); ++L1I)
420 if (isInvalidatingInst(*L1I)) {
421 BBContainsStore[BB1] = true;
422 return false; // Cannot eliminate load
425 // Make sure that there are no store instructions between the start of BB2
426 // and the second load instruction...
428 for (BasicBlock::iterator II = BB2->begin(); &*II != L2; ++II)
429 if (isInvalidatingInst(*II)) {
430 BBContainsStore[BB2] = true;
431 return false; // Cannot eliminate load
434 // Do a depth first traversal of the inverse CFG starting at L2's block,
435 // looking for L1's block. The inverse CFG is made up of the predecessor
436 // nodes of a block... so all of the edges in the graph are "backward".
438 set<BasicBlock*> VisitedSet;
439 for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
440 if (CheckForInvalidatingInst(*PI, BB1, VisitedSet))
444 CommonSubExpressionFound(L1, L2);
450 // CheckForInvalidatingInst - Return true if BB or any of the predecessors of BB
451 // (until DestBB) contain a store (or other invalidating) instruction.
453 bool GCSE::CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
454 set<BasicBlock*> &VisitedSet) {
455 // Found the termination point!
456 if (BB == DestBB || VisitedSet.count(BB)) return false;
458 // Avoid infinite recursion!
459 VisitedSet.insert(BB);
461 // Have we already checked this block?
462 map<BasicBlock*, bool>::iterator MI = BBContainsStore.find(BB);
464 if (MI != BBContainsStore.end()) {
465 // If this block is known to contain a store, exit the recursion early...
466 if (MI->second) return true;
467 // Otherwise continue checking predecessors...
469 // We don't know if this basic block contains an invalidating instruction.
471 bool HasStore = std::find_if(BB->begin(), BB->end(),
472 isInvalidatingInst) != BB->end();
473 if ((BBContainsStore[BB] = HasStore)) // Update map
474 return true; // Exit recursion early...
477 // Check all of our predecessor blocks...
478 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
479 if (CheckForInvalidatingInst(*PI, DestBB, VisitedSet))
482 // None of our predecessor blocks contain a store, and we don't either!