1 //===-- GCSE.cpp - SSA based Global Common Subexpr Elimination ------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass is designed to be a very quick global transformation that
11 // eliminates global common subexpressions from a function. It does this by
12 // using an existing value numbering implementation to identify the common
13 // subexpressions, eliminating them when possible.
15 //===----------------------------------------------------------------------===//
17 #include "llvm/Transforms/Scalar.h"
18 #include "llvm/iMemory.h"
19 #include "llvm/iOther.h"
20 #include "llvm/Type.h"
21 #include "llvm/Analysis/Dominators.h"
22 #include "llvm/Analysis/ValueNumbering.h"
23 #include "llvm/Support/InstIterator.h"
24 #include "Support/Statistic.h"
25 #include "Support/Debug.h"
30 Statistic<> NumInstRemoved("gcse", "Number of instructions removed");
31 Statistic<> NumLoadRemoved("gcse", "Number of loads removed");
32 Statistic<> NumCallRemoved("gcse", "Number of calls removed");
33 Statistic<> NumNonInsts ("gcse", "Number of instructions removed due "
34 "to non-instruction values");
36 class GCSE : public FunctionPass {
37 std::set<Instruction*> WorkList;
38 DominatorSet *DomSetInfo;
41 virtual bool runOnFunction(Function &F);
44 bool EliminateRedundancies(Instruction *I,std::vector<Value*> &EqualValues);
45 Instruction *EliminateCSE(Instruction *I, Instruction *Other);
46 void ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI);
48 // This transformation requires dominator and immediate dominator info
49 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
51 AU.addRequired<DominatorSet>();
52 AU.addRequired<ImmediateDominators>();
53 AU.addRequired<ValueNumbering>();
57 RegisterOpt<GCSE> X("gcse", "Global Common Subexpression Elimination");
60 // createGCSEPass - The public interface to this file...
61 FunctionPass *llvm::createGCSEPass() { return new GCSE(); }
63 // GCSE::runOnFunction - This is the main transformation entry point for a
66 bool GCSE::runOnFunction(Function &F) {
69 // Get pointers to the analysis results that we will be using...
70 DomSetInfo = &getAnalysis<DominatorSet>();
71 VN = &getAnalysis<ValueNumbering>();
73 // Step #1: Add all instructions in the function to the worklist for
74 // processing. All of the instructions are considered to be our
75 // subexpressions to eliminate if possible.
77 WorkList.insert(inst_begin(F), inst_end(F));
79 // Step #2: WorkList processing. Iterate through all of the instructions,
80 // checking to see if there are any additionally defined subexpressions in the
81 // program. If so, eliminate them!
83 while (!WorkList.empty()) {
84 Instruction &I = **WorkList.begin(); // Get an instruction from the worklist
85 WorkList.erase(WorkList.begin());
87 // If this instruction computes a value, try to fold together common
88 // instructions that compute it.
90 if (I.getType() != Type::VoidTy) {
91 std::vector<Value*> EqualValues;
92 VN->getEqualNumberNodes(&I, EqualValues);
94 if (!EqualValues.empty())
95 Changed |= EliminateRedundancies(&I, EqualValues);
99 // When the worklist is empty, return whether or not we changed anything...
103 bool GCSE::EliminateRedundancies(Instruction *I,
104 std::vector<Value*> &EqualValues) {
105 // If the EqualValues set contains any non-instruction values, then we know
106 // that all of the instructions can be replaced with the non-instruction value
107 // because it is guaranteed to dominate all of the instructions in the
108 // function. We only have to do hard work if all we have are instructions.
110 for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
111 if (!isa<Instruction>(EqualValues[i])) {
112 // Found a non-instruction. Replace all instructions with the
115 Value *Replacement = EqualValues[i];
117 // Make sure we get I as well...
120 // Replace all instructions with the Replacement value.
121 for (i = 0; i != e; ++i)
122 if (Instruction *I = dyn_cast<Instruction>(EqualValues[i])) {
123 // Change all users of I to use Replacement.
124 I->replaceAllUsesWith(Replacement);
126 if (isa<LoadInst>(I))
127 ++NumLoadRemoved; // Keep track of loads eliminated
128 if (isa<CallInst>(I))
129 ++NumCallRemoved; // Keep track of calls eliminated
130 ++NumInstRemoved; // Keep track of number of instructions eliminated
131 ++NumNonInsts; // Keep track of number of insts repl with values
133 // Erase the instruction from the program.
134 I->getParent()->getInstList().erase(I);
141 // Remove duplicate entries from EqualValues...
142 std::sort(EqualValues.begin(), EqualValues.end());
143 EqualValues.erase(std::unique(EqualValues.begin(), EqualValues.end()),
146 // From this point on, EqualValues is logically a vector of instructions.
148 bool Changed = false;
149 EqualValues.push_back(I); // Make sure I is included...
150 while (EqualValues.size() > 1) {
151 // FIXME, this could be done better than simple iteration!
152 Instruction *Test = cast<Instruction>(EqualValues.back());
153 EqualValues.pop_back();
155 for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
156 if (Instruction *Ret = EliminateCSE(Test,
157 cast<Instruction>(EqualValues[i]))) {
158 if (Ret == Test) // Eliminated EqualValues[i]
159 EqualValues[i] = Test; // Make sure that we reprocess I at some point
168 // ReplaceInstWithInst - Destroy the instruction pointed to by SI, making all
169 // uses of the instruction use First now instead.
171 void GCSE::ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI) {
172 Instruction &Second = *SI;
174 DEBUG(std::cerr << "GCSE: Substituting %" << First->getName() << " for: "
177 //cerr << "DEL " << (void*)Second << Second;
179 // Add the first instruction back to the worklist
180 WorkList.insert(First);
182 // Add all uses of the second instruction to the worklist
183 for (Value::use_iterator UI = Second.use_begin(), UE = Second.use_end();
185 WorkList.insert(cast<Instruction>(*UI));
187 // Make all users of 'Second' now use 'First'
188 Second.replaceAllUsesWith(First);
190 // Erase the second instruction from the program
191 Second.getParent()->getInstList().erase(SI);
194 // EliminateCSE - The two instruction I & Other have been found to be common
195 // subexpressions. This function is responsible for eliminating one of them,
196 // and for fixing the worklist to be correct. The instruction that is preserved
197 // is returned from the function if the other is eliminated, otherwise null is
200 Instruction *GCSE::EliminateCSE(Instruction *I, Instruction *Other) {
204 WorkList.erase(Other); // Other may not actually be on the worklist anymore...
206 // Handle the easy case, where both instructions are in the same basic block
207 BasicBlock *BB1 = I->getParent(), *BB2 = Other->getParent();
208 Instruction *Ret = 0;
211 // Eliminate the second occurring instruction. Add all uses of the second
212 // instruction to the worklist.
214 // Scan the basic block looking for the "first" instruction
215 BasicBlock::iterator BI = BB1->begin();
216 while (&*BI != I && &*BI != Other) {
218 assert(BI != BB1->end() && "Instructions not found in parent BB!");
221 // Keep track of which instructions occurred first & second
222 Instruction *First = BI;
223 Instruction *Second = I != First ? I : Other; // Get iterator to second inst
226 if (isa<LoadInst>(Second))
227 ++NumLoadRemoved; // Keep track of loads eliminated
228 if (isa<CallInst>(Second))
229 ++NumCallRemoved; // Keep track of calls eliminated
231 // Destroy Second, using First instead.
232 ReplaceInstWithInst(First, BI);
235 // Otherwise, the two instructions are in different basic blocks. If one
236 // dominates the other instruction, we can simply use it
238 } else if (DomSetInfo->dominates(BB1, BB2)) { // I dom Other?
239 if (isa<LoadInst>(Other))
240 ++NumLoadRemoved; // Keep track of loads eliminated
241 if (isa<CallInst>(Other))
242 ++NumCallRemoved; // Keep track of calls eliminated
244 ReplaceInstWithInst(I, Other);
246 } else if (DomSetInfo->dominates(BB2, BB1)) { // Other dom I?
247 if (isa<LoadInst>(I))
248 ++NumLoadRemoved; // Keep track of loads eliminated
249 if (isa<CallInst>(I))
250 ++NumCallRemoved; // Keep track of calls eliminated
252 ReplaceInstWithInst(Other, I);
255 // This code is disabled because it has several problems:
256 // One, the actual assumption is wrong, as shown by this code:
257 // int "test"(int %X, int %Y) {
258 // %Z = add int %X, %Y
261 // %Q = add int %X, %Y
265 // Here there are no shared dominators. Additionally, this had the habit of
266 // moving computations where they were not always computed. For example, in
275 // In this case, the expression would be hoisted to outside the 'if' stmt,
276 // causing the expression to be evaluated, even for the if (d) path, which
277 // could cause problems, if, for example, it caused a divide by zero. In
278 // general the problem this case is trying to solve is better addressed with
284 ++NumInstRemoved; // Keep track of number of instructions eliminated
286 // Add all users of Ret to the worklist...
287 for (Value::use_iterator I = Ret->use_begin(), E = Ret->use_end(); I != E;++I)
288 if (Instruction *Inst = dyn_cast<Instruction>(*I))
289 WorkList.insert(Inst);