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/Analysis/AliasAnalysis.h"
22 #include "llvm/Support/InstVisitor.h"
23 #include "llvm/Support/InstIterator.h"
24 #include "llvm/Support/CFG.h"
25 #include "Support/StatisticReporter.h"
31 static Statistic<> NumInstRemoved("gcse\t\t- Number of instructions removed");
32 static Statistic<> NumLoadRemoved("gcse\t\t- Number of loads removed");
35 class GCSE : public FunctionPass, public InstVisitor<GCSE, bool> {
36 set<Instruction*> WorkList;
37 DominatorSet *DomSetInfo;
38 ImmediateDominators *ImmDominator;
42 virtual bool runOnFunction(Function &F);
44 // Visitation methods, these are invoked depending on the type of
45 // instruction being checked. They should return true if a common
46 // subexpression was folded.
48 bool visitBinaryOperator(Instruction &I);
49 bool visitGetElementPtrInst(GetElementPtrInst &I);
50 bool visitCastInst(CastInst &I);
51 bool visitShiftInst(ShiftInst &I) {
52 return visitBinaryOperator((Instruction&)I);
54 bool visitLoadInst(LoadInst &LI);
55 bool visitInstruction(Instruction &) { return false; }
58 void ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI);
59 bool CommonSubExpressionFound(Instruction *I, Instruction *Other);
61 // TryToRemoveALoad - Try to remove one of L1 or L2. The problem with
62 // removing loads is that intervening stores might make otherwise identical
63 // load's yield different values. To ensure that this is not the case, we
64 // check that there are no intervening stores or calls between the
67 bool TryToRemoveALoad(LoadInst *L1, LoadInst *L2);
69 // CheckForInvalidatingInst - Return true if BB or any of the predecessors
70 // of BB (until DestBB) contain an instruction that might invalidate Ptr.
72 bool CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
73 Value *Ptr, set<BasicBlock*> &VisitedSet);
75 // This transformation requires dominator and immediate dominator info
76 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
78 AU.addRequired<DominatorSet>();
79 AU.addRequired<ImmediateDominators>();
80 AU.addRequired<AliasAnalysis>();
84 RegisterOpt<GCSE> X("gcse", "Global Common Subexpression Elimination");
87 // createGCSEPass - The public interface to this file...
88 Pass *createGCSEPass() { return new GCSE(); }
91 // GCSE::runOnFunction - This is the main transformation entry point for a
94 bool GCSE::runOnFunction(Function &F) {
97 // Get pointers to the analysis results that we will be using...
98 DomSetInfo = &getAnalysis<DominatorSet>();
99 ImmDominator = &getAnalysis<ImmediateDominators>();
100 AA = &getAnalysis<AliasAnalysis>();
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 // When the worklist is empty, return whether or not we changed anything...
127 // ReplaceInstWithInst - Destroy the instruction pointed to by SI, making all
128 // uses of the instruction use First now instead.
130 void GCSE::ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI) {
131 Instruction &Second = *SI;
133 //cerr << "DEL " << (void*)Second << Second;
135 // Add the first instruction back to the worklist
136 WorkList.insert(First);
138 // Add all uses of the second instruction to the worklist
139 for (Value::use_iterator UI = Second.use_begin(), UE = Second.use_end();
141 WorkList.insert(cast<Instruction>(*UI));
143 // Make all users of 'Second' now use 'First'
144 Second.replaceAllUsesWith(First);
146 // Erase the second instruction from the program
147 Second.getParent()->getInstList().erase(SI);
150 // CommonSubExpressionFound - The two instruction I & Other have been found to
151 // be common subexpressions. This function is responsible for eliminating one
152 // of them, and for fixing the worklist to be correct.
154 bool GCSE::CommonSubExpressionFound(Instruction *I, Instruction *Other) {
158 WorkList.erase(Other); // Other may not actually be on the worklist anymore...
160 ++NumInstRemoved; // Keep track of number of instructions eliminated
162 // Handle the easy case, where both instructions are in the same basic block
163 BasicBlock *BB1 = I->getParent(), *BB2 = Other->getParent();
165 // Eliminate the second occuring instruction. Add all uses of the second
166 // instruction to the worklist.
168 // Scan the basic block looking for the "first" instruction
169 BasicBlock::iterator BI = BB1->begin();
170 while (&*BI != I && &*BI != Other) {
172 assert(BI != BB1->end() && "Instructions not found in parent BB!");
175 // Keep track of which instructions occurred first & second
176 Instruction *First = BI;
177 Instruction *Second = I != First ? I : Other; // Get iterator to second inst
180 // Destroy Second, using First instead.
181 ReplaceInstWithInst(First, BI);
183 // Otherwise, the two instructions are in different basic blocks. If one
184 // dominates the other instruction, we can simply use it
186 } else if (DomSetInfo->dominates(BB1, BB2)) { // I dom Other?
187 ReplaceInstWithInst(I, Other);
188 } else if (DomSetInfo->dominates(BB2, BB1)) { // Other dom I?
189 ReplaceInstWithInst(Other, I);
191 // This code is disabled because it has several problems:
192 // One, the actual assumption is wrong, as shown by this code:
193 // int "test"(int %X, int %Y) {
194 // %Z = add int %X, %Y
197 // %Q = add int %X, %Y
201 // Here there are no shared dominators. Additionally, this had the habit of
202 // moving computations where they were not always computed. For example, in
211 // In thiscase, the expression would be hoisted to outside the 'if' stmt,
212 // causing the expression to be evaluated, even for the if (d) path, which
213 // could cause problems, if, for example, it caused a divide by zero. In
214 // general the problem this case is trying to solve is better addressed with
220 // Handle the most general case now. In this case, neither I dom Other nor
221 // Other dom I. Because we are in SSA form, we are guaranteed that the
222 // operands of the two instructions both dominate the uses, so we _know_
223 // that there must exist a block that dominates both instructions (if the
224 // operands of the instructions are globals or constants, worst case we
225 // would get the entry node of the function). Search for this block now.
228 // Search up the immediate dominator chain of BB1 for the shared dominator
229 BasicBlock *SharedDom = (*ImmDominator)[BB1];
230 while (!DomSetInfo->dominates(SharedDom, BB2))
231 SharedDom = (*ImmDominator)[SharedDom];
233 // At this point, shared dom must dominate BOTH BB1 and BB2...
234 assert(SharedDom && DomSetInfo->dominates(SharedDom, BB1) &&
235 DomSetInfo->dominates(SharedDom, BB2) && "Dominators broken!");
237 // Rip 'I' out of BB1, and move it to the end of SharedDom.
238 BB1->getInstList().remove(I);
239 SharedDom->getInstList().insert(--SharedDom->end(), I);
241 // Eliminate 'Other' now.
242 ReplaceInstWithInst(I, Other);
248 //===----------------------------------------------------------------------===//
250 // Visitation methods, these are invoked depending on the type of instruction
251 // being checked. They should return true if a common subexpression was folded.
253 //===----------------------------------------------------------------------===//
255 bool GCSE::visitCastInst(CastInst &CI) {
256 Instruction &I = (Instruction&)CI;
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 (Instruction *Other = dyn_cast<Instruction>(*UI))
263 // Check to see if this new cast is not I, but has the same operand...
264 if (Other != &I && Other->getOpcode() == I.getOpcode() &&
265 Other->getOperand(0) == Op && // Is the operand the same?
266 // Is it embeded in the same function? (This could be false if LHS
267 // is a constant or global!)
268 Other->getParent()->getParent() == F &&
270 // Check that the types are the same, since this code handles casts...
271 Other->getType() == I.getType()) {
273 // These instructions are identical. Handle the situation.
274 if (CommonSubExpressionFound(&I, Other))
275 return true; // One instruction eliminated!
281 // isIdenticalBinaryInst - Return true if the two binary instructions are
284 static inline bool isIdenticalBinaryInst(const Instruction &I1,
285 const Instruction *I2) {
286 // Is it embeded in the same function? (This could be false if LHS
287 // is a constant or global!)
288 if (I1.getOpcode() != I2->getOpcode() ||
289 I1.getParent()->getParent() != I2->getParent()->getParent())
292 // They are identical if both operands are the same!
293 if (I1.getOperand(0) == I2->getOperand(0) &&
294 I1.getOperand(1) == I2->getOperand(1))
297 // If the instruction is commutative and associative, the instruction can
298 // match if the operands are swapped!
300 if ((I1.getOperand(0) == I2->getOperand(1) &&
301 I1.getOperand(1) == I2->getOperand(0)) &&
302 (I1.getOpcode() == Instruction::Add ||
303 I1.getOpcode() == Instruction::Mul ||
304 I1.getOpcode() == Instruction::And ||
305 I1.getOpcode() == Instruction::Or ||
306 I1.getOpcode() == Instruction::Xor))
312 bool GCSE::visitBinaryOperator(Instruction &I) {
313 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
314 Function *F = I.getParent()->getParent();
316 for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end();
318 if (Instruction *Other = dyn_cast<Instruction>(*UI))
319 // Check to see if this new binary operator is not I, but same operand...
320 if (Other != &I && isIdenticalBinaryInst(I, Other)) {
321 // These instructions are identical. Handle the situation.
322 if (CommonSubExpressionFound(&I, Other))
323 return true; // One instruction eliminated!
329 // IdenticalComplexInst - Return true if the two instructions are the same, by
330 // using a brute force comparison.
332 static bool IdenticalComplexInst(const Instruction *I1, const Instruction *I2) {
333 assert(I1->getOpcode() == I2->getOpcode());
334 // Equal if they are in the same function...
335 return I1->getParent()->getParent() == I2->getParent()->getParent() &&
336 // And return the same type...
337 I1->getType() == I2->getType() &&
338 // And have the same number of operands...
339 I1->getNumOperands() == I2->getNumOperands() &&
340 // And all of the operands are equal.
341 std::equal(I1->op_begin(), I1->op_end(), I2->op_begin());
344 bool GCSE::visitGetElementPtrInst(GetElementPtrInst &I) {
345 Value *Op = I.getOperand(0);
346 Function *F = I.getParent()->getParent();
348 for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
350 if (GetElementPtrInst *Other = dyn_cast<GetElementPtrInst>(*UI))
351 // Check to see if this new getelementptr is not I, but same operand...
352 if (Other != &I && IdenticalComplexInst(&I, Other)) {
353 // These instructions are identical. Handle the situation.
354 if (CommonSubExpressionFound(&I, Other))
355 return true; // One instruction eliminated!
361 bool GCSE::visitLoadInst(LoadInst &LI) {
362 Value *Op = LI.getOperand(0);
363 Function *F = LI.getParent()->getParent();
365 for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
367 if (LoadInst *Other = dyn_cast<LoadInst>(*UI))
368 // Check to see if this new load is not LI, but has the same operands...
369 if (Other != &LI && IdenticalComplexInst(&LI, Other) &&
370 TryToRemoveALoad(&LI, Other))
371 return true; // An instruction was eliminated!
376 // TryToRemoveALoad - Try to remove one of L1 or L2. The problem with removing
377 // loads is that intervening stores might make otherwise identical load's yield
378 // different values. To ensure that this is not the case, we check that there
379 // are no intervening stores or calls between the instructions.
381 bool GCSE::TryToRemoveALoad(LoadInst *L1, LoadInst *L2) {
382 // Figure out which load dominates the other one. If neither dominates the
383 // other we cannot eliminate one...
385 if (DomSetInfo->dominates(L2, L1))
386 std::swap(L1, L2); // Make L1 dominate L2
387 else if (!DomSetInfo->dominates(L1, L2))
388 return false; // Neither instruction dominates the other one...
390 BasicBlock *BB1 = L1->getParent(), *BB2 = L2->getParent();
392 assert(!L1->hasIndices());
393 Value *LoadAddress = L1->getOperand(0);
395 // L1 now dominates L2. Check to see if the intervening instructions between
396 // the two loads include a store or call...
398 if (BB1 == BB2) { // In same basic block?
399 // In this degenerate case, no checking of global basic blocks has to occur
400 // just check the instructions BETWEEN L1 & L2...
402 if (AA->canInstructionRangeModify(*L1, *L2, LoadAddress))
403 return false; // Cannot eliminate load
406 if (CommonSubExpressionFound(L1, L2))
409 // Make sure that there are no store instructions between L1 and the end of
410 // it's basic block...
412 if (AA->canInstructionRangeModify(*L1, *BB1->getTerminator(), LoadAddress))
413 return false; // Cannot eliminate load
415 // Make sure that there are no store instructions between the start of BB2
416 // and the second load instruction...
418 if (AA->canInstructionRangeModify(BB2->front(), *L2, LoadAddress))
419 return false; // Cannot eliminate load
421 // Do a depth first traversal of the inverse CFG starting at L2's block,
422 // looking for L1's block. The inverse CFG is made up of the predecessor
423 // nodes of a block... so all of the edges in the graph are "backward".
425 set<BasicBlock*> VisitedSet;
426 for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
427 if (CheckForInvalidatingInst(*PI, BB1, LoadAddress, VisitedSet))
431 return CommonSubExpressionFound(L1, L2);
436 // CheckForInvalidatingInst - Return true if BB or any of the predecessors of BB
437 // (until DestBB) contain an instruction that might invalidate Ptr.
439 bool GCSE::CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
440 Value *Ptr, set<BasicBlock*> &VisitedSet) {
441 // Found the termination point!
442 if (BB == DestBB || VisitedSet.count(BB)) return false;
444 // Avoid infinite recursion!
445 VisitedSet.insert(BB);
447 // Can this basic block modify Ptr?
448 if (AA->canBasicBlockModify(*BB, Ptr))
451 // Check all of our predecessor blocks...
452 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
453 if (CheckForInvalidatingInst(*PI, DestBB, Ptr, VisitedSet))
456 // None of our predecessor blocks contain a store, and we don't either!