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 //===----------------------------------------------------------------------===//
10 #include "llvm/Transforms/Scalar.h"
11 #include "llvm/InstrTypes.h"
12 #include "llvm/iMemory.h"
13 #include "llvm/Analysis/Dominators.h"
14 #include "llvm/Analysis/AliasAnalysis.h"
15 #include "llvm/Support/InstVisitor.h"
16 #include "llvm/Support/InstIterator.h"
17 #include "llvm/Support/CFG.h"
18 #include "Support/StatisticReporter.h"
24 static Statistic<> NumInstRemoved("gcse\t\t- Number of instructions removed");
25 static Statistic<> NumLoadRemoved("gcse\t\t- Number of loads removed");
28 class GCSE : public FunctionPass, public InstVisitor<GCSE, bool> {
29 set<Instruction*> WorkList;
30 DominatorSet *DomSetInfo;
31 ImmediateDominators *ImmDominator;
35 virtual bool runOnFunction(Function &F);
37 // Visitation methods, these are invoked depending on the type of
38 // instruction being checked. They should return true if a common
39 // subexpression was folded.
41 bool visitBinaryOperator(Instruction &I);
42 bool visitGetElementPtrInst(GetElementPtrInst &I);
43 bool visitCastInst(CastInst &I);
44 bool visitShiftInst(ShiftInst &I) {
45 return visitBinaryOperator((Instruction&)I);
47 bool visitLoadInst(LoadInst &LI);
48 bool visitInstruction(Instruction &) { return false; }
51 void ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI);
52 bool CommonSubExpressionFound(Instruction *I, Instruction *Other);
54 // TryToRemoveALoad - Try to remove one of L1 or L2. The problem with
55 // removing loads is that intervening stores might make otherwise identical
56 // load's yield different values. To ensure that this is not the case, we
57 // check that there are no intervening stores or calls between the
60 bool TryToRemoveALoad(LoadInst *L1, LoadInst *L2);
62 // CheckForInvalidatingInst - Return true if BB or any of the predecessors
63 // of BB (until DestBB) contain an instruction that might invalidate Ptr.
65 bool CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
66 Value *Ptr, set<BasicBlock*> &VisitedSet);
68 // This transformation requires dominator and immediate dominator info
69 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
71 AU.addRequired<DominatorSet>();
72 AU.addRequired<ImmediateDominators>();
73 AU.addRequired<AliasAnalysis>();
77 RegisterOpt<GCSE> X("gcse", "Global Common Subexpression Elimination");
80 // createGCSEPass - The public interface to this file...
81 Pass *createGCSEPass() { return new GCSE(); }
84 // GCSE::runOnFunction - This is the main transformation entry point for a
87 bool GCSE::runOnFunction(Function &F) {
90 // Get pointers to the analysis results that we will be using...
91 DomSetInfo = &getAnalysis<DominatorSet>();
92 ImmDominator = &getAnalysis<ImmediateDominators>();
93 AA = &getAnalysis<AliasAnalysis>();
95 // Step #1: Add all instructions in the function to the worklist for
96 // processing. All of the instructions are considered to be our
97 // subexpressions to eliminate if possible.
99 WorkList.insert(inst_begin(F), inst_end(F));
101 // Step #2: WorkList processing. Iterate through all of the instructions,
102 // checking to see if there are any additionally defined subexpressions in the
103 // program. If so, eliminate them!
105 while (!WorkList.empty()) {
106 Instruction &I = **WorkList.begin(); // Get an instruction from the worklist
107 WorkList.erase(WorkList.begin());
109 // Visit the instruction, dispatching to the correct visit function based on
110 // the instruction type. This does the checking.
115 // When the worklist is empty, return whether or not we changed anything...
120 // ReplaceInstWithInst - Destroy the instruction pointed to by SI, making all
121 // uses of the instruction use First now instead.
123 void GCSE::ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI) {
124 Instruction &Second = *SI;
126 //cerr << "DEL " << (void*)Second << Second;
128 // Add the first instruction back to the worklist
129 WorkList.insert(First);
131 // Add all uses of the second instruction to the worklist
132 for (Value::use_iterator UI = Second.use_begin(), UE = Second.use_end();
134 WorkList.insert(cast<Instruction>(*UI));
136 // Make all users of 'Second' now use 'First'
137 Second.replaceAllUsesWith(First);
139 // Erase the second instruction from the program
140 Second.getParent()->getInstList().erase(SI);
143 // CommonSubExpressionFound - The two instruction I & Other have been found to
144 // be common subexpressions. This function is responsible for eliminating one
145 // of them, and for fixing the worklist to be correct.
147 bool GCSE::CommonSubExpressionFound(Instruction *I, Instruction *Other) {
151 WorkList.erase(Other); // Other may not actually be on the worklist anymore...
153 ++NumInstRemoved; // Keep track of number of instructions eliminated
155 // Handle the easy case, where both instructions are in the same basic block
156 BasicBlock *BB1 = I->getParent(), *BB2 = Other->getParent();
158 // Eliminate the second occuring instruction. Add all uses of the second
159 // instruction to the worklist.
161 // Scan the basic block looking for the "first" instruction
162 BasicBlock::iterator BI = BB1->begin();
163 while (&*BI != I && &*BI != Other) {
165 assert(BI != BB1->end() && "Instructions not found in parent BB!");
168 // Keep track of which instructions occurred first & second
169 Instruction *First = BI;
170 Instruction *Second = I != First ? I : Other; // Get iterator to second inst
173 // Destroy Second, using First instead.
174 ReplaceInstWithInst(First, BI);
176 // Otherwise, the two instructions are in different basic blocks. If one
177 // dominates the other instruction, we can simply use it
179 } else if (DomSetInfo->dominates(BB1, BB2)) { // I dom Other?
180 ReplaceInstWithInst(I, Other);
181 } else if (DomSetInfo->dominates(BB2, BB1)) { // Other dom I?
182 ReplaceInstWithInst(Other, I);
184 // This code is disabled because it has several problems:
185 // One, the actual assumption is wrong, as shown by this code:
186 // int "test"(int %X, int %Y) {
187 // %Z = add int %X, %Y
190 // %Q = add int %X, %Y
194 // Here there are no shared dominators. Additionally, this had the habit of
195 // moving computations where they were not always computed. For example, in
204 // In thiscase, the expression would be hoisted to outside the 'if' stmt,
205 // causing the expression to be evaluated, even for the if (d) path, which
206 // could cause problems, if, for example, it caused a divide by zero. In
207 // general the problem this case is trying to solve is better addressed with
213 // Handle the most general case now. In this case, neither I dom Other nor
214 // Other dom I. Because we are in SSA form, we are guaranteed that the
215 // operands of the two instructions both dominate the uses, so we _know_
216 // that there must exist a block that dominates both instructions (if the
217 // operands of the instructions are globals or constants, worst case we
218 // would get the entry node of the function). Search for this block now.
221 // Search up the immediate dominator chain of BB1 for the shared dominator
222 BasicBlock *SharedDom = (*ImmDominator)[BB1];
223 while (!DomSetInfo->dominates(SharedDom, BB2))
224 SharedDom = (*ImmDominator)[SharedDom];
226 // At this point, shared dom must dominate BOTH BB1 and BB2...
227 assert(SharedDom && DomSetInfo->dominates(SharedDom, BB1) &&
228 DomSetInfo->dominates(SharedDom, BB2) && "Dominators broken!");
230 // Rip 'I' out of BB1, and move it to the end of SharedDom.
231 BB1->getInstList().remove(I);
232 SharedDom->getInstList().insert(--SharedDom->end(), I);
234 // Eliminate 'Other' now.
235 ReplaceInstWithInst(I, Other);
241 //===----------------------------------------------------------------------===//
243 // Visitation methods, these are invoked depending on the type of instruction
244 // being checked. They should return true if a common subexpression was folded.
246 //===----------------------------------------------------------------------===//
248 bool GCSE::visitCastInst(CastInst &CI) {
249 Instruction &I = (Instruction&)CI;
250 Value *Op = I.getOperand(0);
251 Function *F = I.getParent()->getParent();
253 for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
255 if (Instruction *Other = dyn_cast<Instruction>(*UI))
256 // Check to see if this new cast is not I, but has the same operand...
257 if (Other != &I && Other->getOpcode() == I.getOpcode() &&
258 Other->getOperand(0) == Op && // Is the operand the same?
259 // Is it embeded in the same function? (This could be false if LHS
260 // is a constant or global!)
261 Other->getParent()->getParent() == F &&
263 // Check that the types are the same, since this code handles casts...
264 Other->getType() == I.getType()) {
266 // These instructions are identical. Handle the situation.
267 if (CommonSubExpressionFound(&I, Other))
268 return true; // One instruction eliminated!
274 // isIdenticalBinaryInst - Return true if the two binary instructions are
277 static inline bool isIdenticalBinaryInst(const Instruction &I1,
278 const Instruction *I2) {
279 // Is it embeded in the same function? (This could be false if LHS
280 // is a constant or global!)
281 if (I1.getOpcode() != I2->getOpcode() ||
282 I1.getParent()->getParent() != I2->getParent()->getParent())
285 // They are identical if both operands are the same!
286 if (I1.getOperand(0) == I2->getOperand(0) &&
287 I1.getOperand(1) == I2->getOperand(1))
290 // If the instruction is commutative and associative, the instruction can
291 // match if the operands are swapped!
293 if ((I1.getOperand(0) == I2->getOperand(1) &&
294 I1.getOperand(1) == I2->getOperand(0)) &&
295 (I1.getOpcode() == Instruction::Add ||
296 I1.getOpcode() == Instruction::Mul ||
297 I1.getOpcode() == Instruction::And ||
298 I1.getOpcode() == Instruction::Or ||
299 I1.getOpcode() == Instruction::Xor))
305 bool GCSE::visitBinaryOperator(Instruction &I) {
306 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
307 Function *F = I.getParent()->getParent();
309 for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end();
311 if (Instruction *Other = dyn_cast<Instruction>(*UI))
312 // Check to see if this new binary operator is not I, but same operand...
313 if (Other != &I && isIdenticalBinaryInst(I, Other)) {
314 // These instructions are identical. Handle the situation.
315 if (CommonSubExpressionFound(&I, Other))
316 return true; // One instruction eliminated!
322 // IdenticalComplexInst - Return true if the two instructions are the same, by
323 // using a brute force comparison.
325 static bool IdenticalComplexInst(const Instruction *I1, const Instruction *I2) {
326 assert(I1->getOpcode() == I2->getOpcode());
327 // Equal if they are in the same function...
328 return I1->getParent()->getParent() == I2->getParent()->getParent() &&
329 // And return the same type...
330 I1->getType() == I2->getType() &&
331 // And have the same number of operands...
332 I1->getNumOperands() == I2->getNumOperands() &&
333 // And all of the operands are equal.
334 std::equal(I1->op_begin(), I1->op_end(), I2->op_begin());
337 bool GCSE::visitGetElementPtrInst(GetElementPtrInst &I) {
338 Value *Op = I.getOperand(0);
339 Function *F = I.getParent()->getParent();
341 for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
343 if (GetElementPtrInst *Other = dyn_cast<GetElementPtrInst>(*UI))
344 // Check to see if this new getelementptr is not I, but same operand...
345 if (Other != &I && IdenticalComplexInst(&I, Other)) {
346 // These instructions are identical. Handle the situation.
347 if (CommonSubExpressionFound(&I, Other))
348 return true; // One instruction eliminated!
354 bool GCSE::visitLoadInst(LoadInst &LI) {
355 Value *Op = LI.getOperand(0);
356 Function *F = LI.getParent()->getParent();
358 for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
360 if (LoadInst *Other = dyn_cast<LoadInst>(*UI))
361 // Check to see if this new load is not LI, but has the same operands...
362 if (Other != &LI && IdenticalComplexInst(&LI, Other) &&
363 TryToRemoveALoad(&LI, Other))
364 return true; // An instruction was eliminated!
369 // TryToRemoveALoad - Try to remove one of L1 or L2. The problem with removing
370 // loads is that intervening stores might make otherwise identical load's yield
371 // different values. To ensure that this is not the case, we check that there
372 // are no intervening stores or calls between the instructions.
374 bool GCSE::TryToRemoveALoad(LoadInst *L1, LoadInst *L2) {
375 // Figure out which load dominates the other one. If neither dominates the
376 // other we cannot eliminate one...
378 if (DomSetInfo->dominates(L2, L1))
379 std::swap(L1, L2); // Make L1 dominate L2
380 else if (!DomSetInfo->dominates(L1, L2))
381 return false; // Neither instruction dominates the other one...
383 BasicBlock *BB1 = L1->getParent(), *BB2 = L2->getParent();
385 assert(!L1->hasIndices());
386 Value *LoadAddress = L1->getOperand(0);
388 // L1 now dominates L2. Check to see if the intervening instructions between
389 // the two loads include a store or call...
391 if (BB1 == BB2) { // In same basic block?
392 // In this degenerate case, no checking of global basic blocks has to occur
393 // just check the instructions BETWEEN L1 & L2...
395 if (AA->canInstructionRangeModify(*L1, *L2, LoadAddress))
396 return false; // Cannot eliminate load
399 if (CommonSubExpressionFound(L1, L2))
402 // Make sure that there are no store instructions between L1 and the end of
403 // it's basic block...
405 if (AA->canInstructionRangeModify(*L1, *BB1->getTerminator(), LoadAddress))
406 return false; // Cannot eliminate load
408 // Make sure that there are no store instructions between the start of BB2
409 // and the second load instruction...
411 if (AA->canInstructionRangeModify(BB2->front(), *L2, LoadAddress))
412 return false; // Cannot eliminate load
414 // Do a depth first traversal of the inverse CFG starting at L2's block,
415 // looking for L1's block. The inverse CFG is made up of the predecessor
416 // nodes of a block... so all of the edges in the graph are "backward".
418 set<BasicBlock*> VisitedSet;
419 for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
420 if (CheckForInvalidatingInst(*PI, BB1, LoadAddress, VisitedSet))
424 return CommonSubExpressionFound(L1, L2);
429 // CheckForInvalidatingInst - Return true if BB or any of the predecessors of BB
430 // (until DestBB) contain an instruction that might invalidate Ptr.
432 bool GCSE::CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
433 Value *Ptr, set<BasicBlock*> &VisitedSet) {
434 // Found the termination point!
435 if (BB == DestBB || VisitedSet.count(BB)) return false;
437 // Avoid infinite recursion!
438 VisitedSet.insert(BB);
440 // Can this basic block modify Ptr?
441 if (AA->canBasicBlockModify(*BB, Ptr))
444 // Check all of our predecessor blocks...
445 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
446 if (CheckForInvalidatingInst(*PI, DestBB, Ptr, VisitedSet))
449 // None of our predecessor blocks contain a store, and we don't either!