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/BasicBlock.h"
19 #include "llvm/Constant.h"
20 #include "llvm/Instructions.h"
21 #include "llvm/Type.h"
22 #include "llvm/Analysis/Dominators.h"
23 #include "llvm/Analysis/ValueNumbering.h"
24 #include "llvm/Transforms/Utils/Local.h"
25 #include "Support/DepthFirstIterator.h"
26 #include "Support/Statistic.h"
31 Statistic<> NumInstRemoved("gcse", "Number of instructions removed");
32 Statistic<> NumLoadRemoved("gcse", "Number of loads removed");
33 Statistic<> NumCallRemoved("gcse", "Number of calls removed");
34 Statistic<> NumNonInsts ("gcse", "Number of instructions removed due "
35 "to non-instruction values");
37 struct GCSE : public FunctionPass {
38 virtual bool runOnFunction(Function &F);
41 void ReplaceInstructionWith(Instruction *I, Value *V);
43 // This transformation requires dominator and immediate dominator info
44 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
46 AU.addRequired<DominatorSet>();
47 AU.addRequired<DominatorTree>();
48 AU.addRequired<ValueNumbering>();
52 RegisterOpt<GCSE> X("gcse", "Global Common Subexpression Elimination");
55 // createGCSEPass - The public interface to this file...
56 FunctionPass *llvm::createGCSEPass() { return new GCSE(); }
58 // GCSE::runOnFunction - This is the main transformation entry point for a
61 bool GCSE::runOnFunction(Function &F) {
64 // Get pointers to the analysis results that we will be using...
65 DominatorSet &DS = getAnalysis<DominatorSet>();
66 ValueNumbering &VN = getAnalysis<ValueNumbering>();
67 DominatorTree &DT = getAnalysis<DominatorTree>();
69 std::vector<Value*> EqualValues;
71 // Traverse the CFG of the function in dominator order, so that we see each
72 // instruction after we see its operands.
73 for (df_iterator<DominatorTree::Node*> DI = df_begin(DT.getRootNode()),
74 E = df_end(DT.getRootNode()); DI != E; ++DI) {
75 BasicBlock *BB = DI->getBlock();
77 // Remember which instructions we've seen in this basic block as we scan.
78 std::set<Instruction*> BlockInsts;
80 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
81 Instruction *Inst = I++;
83 // If this instruction computes a value, try to fold together common
84 // instructions that compute it.
86 if (Inst->getType() != Type::VoidTy) {
87 VN.getEqualNumberNodes(Inst, EqualValues);
89 // If this instruction computes a value that is already computed
90 // elsewhere, try to recycle the old value.
91 if (!EqualValues.empty()) {
92 if (Inst == &*BB->begin())
98 // First check to see if we were able to value number this instruction
99 // to a non-instruction value. If so, prefer that value over other
100 // instructions which may compute the same thing.
101 for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
102 if (!isa<Instruction>(EqualValues[i])) {
103 ++NumNonInsts; // Keep track of # of insts repl with values
105 // Change all users of Inst to use the replacement and remove it
107 ReplaceInstructionWith(Inst, EqualValues[i]);
109 EqualValues.clear(); // don't enter the next loop
113 // If there were no non-instruction values that this instruction
114 // produces, find a dominating instruction that produces the same
115 // value. If we find one, use it's value instead of ours.
116 for (unsigned i = 0, e = EqualValues.size(); i != e; ++i) {
117 Instruction *OtherI = cast<Instruction>(EqualValues[i]);
118 bool Dominates = false;
119 if (OtherI->getParent() == BB)
120 Dominates = BlockInsts.count(OtherI);
122 Dominates = DS.dominates(OtherI->getParent(), BB);
125 // Okay, we found an instruction with the same value as this one
126 // and that dominates this one. Replace this instruction with the
128 ReplaceInstructionWith(Inst, OtherI);
137 I = Inst; ++I; // Deleted no instructions
138 } else if (I == BB->end()) { // Deleted first instruction
140 } else { // Deleted inst in middle of block.
146 BlockInsts.insert(Inst);
151 // When the worklist is empty, return whether or not we changed anything...
156 void GCSE::ReplaceInstructionWith(Instruction *I, Value *V) {
157 if (isa<LoadInst>(I))
158 ++NumLoadRemoved; // Keep track of loads eliminated
159 if (isa<CallInst>(I))
160 ++NumCallRemoved; // Keep track of calls eliminated
161 ++NumInstRemoved; // Keep track of number of insts eliminated
163 // Update value numbering
164 getAnalysis<ValueNumbering>().deleteInstruction(I);
166 // If we are not replacing the instruction with a constant, we cannot do
168 if (!isa<Constant>(V)) {
169 I->replaceAllUsesWith(V);
171 if (InvokeInst *II = dyn_cast<InvokeInst>(I)) {
172 // Removing an invoke instruction requires adding a branch to the normal
173 // destination and removing PHI node entries in the exception destination.
174 new BranchInst(II->getNormalDest(), II);
175 II->getUnwindDest()->removePredecessor(II->getParent());
178 // Erase the instruction from the program.
179 I->getParent()->getInstList().erase(I);
183 Constant *C = cast<Constant>(V);
184 std::vector<User*> Users(I->use_begin(), I->use_end());
186 // Perform the replacement.
187 I->replaceAllUsesWith(C);
189 if (InvokeInst *II = dyn_cast<InvokeInst>(I)) {
190 // Removing an invoke instruction requires adding a branch to the normal
191 // destination and removing PHI node entries in the exception destination.
192 new BranchInst(II->getNormalDest(), II);
193 II->getUnwindDest()->removePredecessor(II->getParent());
196 // Erase the instruction from the program.
197 I->getParent()->getInstList().erase(I);
199 // Check each user to see if we can constant fold it.
200 while (!Users.empty()) {
201 Instruction *U = cast<Instruction>(Users.back());
204 if (Constant *C = ConstantFoldInstruction(U)) {
205 ReplaceInstructionWith(U, C);
207 // If the instruction used I more than once, it could be on the user list
208 // multiple times. Make sure we don't reprocess it.
209 std::vector<User*>::iterator It = std::find(Users.begin(), Users.end(),U);
210 while (It != Users.end()) {
212 It = std::find(Users.begin(), Users.end(), U);