Chris Lattner | 057f78a | 2004-05-23 21:19:55 +0000 | [diff] [blame] | 1 | //===-- GCSE.cpp - SSA-based Global Common Subexpression Elimination ------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame^] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 9 | // |
| 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 |
Chris Lattner | 2964f36 | 2002-08-30 22:53:30 +0000 | [diff] [blame] | 12 | // using an existing value numbering implementation to identify the common |
| 13 | // subexpressions, eliminating them when possible. |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 14 | // |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 15 | //===----------------------------------------------------------------------===// |
| 16 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 17 | #define DEBUG_TYPE "gcse" |
Chris Lattner | 022103b | 2002-05-07 20:03:00 +0000 | [diff] [blame] | 18 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 38e66bd | 2004-04-10 21:11:11 +0000 | [diff] [blame] | 19 | #include "llvm/Instructions.h" |
Chris Lattner | 79066fa | 2007-01-30 23:46:24 +0000 | [diff] [blame] | 20 | #include "llvm/Function.h" |
Chris Lattner | 2964f36 | 2002-08-30 22:53:30 +0000 | [diff] [blame] | 21 | #include "llvm/Type.h" |
Chris Lattner | 79066fa | 2007-01-30 23:46:24 +0000 | [diff] [blame] | 22 | #include "llvm/Analysis/ConstantFolding.h" |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 23 | #include "llvm/Analysis/Dominators.h" |
Chris Lattner | 14987f1 | 2002-08-30 20:22:29 +0000 | [diff] [blame] | 24 | #include "llvm/Analysis/ValueNumbering.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 25 | #include "llvm/ADT/DepthFirstIterator.h" |
| 26 | #include "llvm/ADT/Statistic.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 27 | #include "llvm/Support/Compiler.h" |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 28 | #include <algorithm> |
Chris Lattner | d745602 | 2004-01-09 06:02:20 +0000 | [diff] [blame] | 29 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 30 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 31 | STATISTIC(NumInstRemoved, "Number of instructions removed"); |
| 32 | STATISTIC(NumLoadRemoved, "Number of loads removed"); |
| 33 | STATISTIC(NumCallRemoved, "Number of calls removed"); |
| 34 | STATISTIC(NumNonInsts , "Number of instructions removed due " |
| 35 | "to non-instruction values"); |
| 36 | STATISTIC(NumArgsRepl , "Number of function arguments replaced " |
| 37 | "with constant values"); |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 38 | namespace { |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 39 | struct VISIBILITY_HIDDEN GCSE : public FunctionPass { |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 40 | static char ID; // Pass identification, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 41 | GCSE() : FunctionPass((intptr_t)&ID) {} |
| 42 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 43 | virtual bool runOnFunction(Function &F); |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 44 | |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 45 | private: |
Chris Lattner | 38e66bd | 2004-04-10 21:11:11 +0000 | [diff] [blame] | 46 | void ReplaceInstructionWith(Instruction *I, Value *V); |
Chris Lattner | 18fb2a6 | 2002-05-14 05:02:40 +0000 | [diff] [blame] | 47 | |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 48 | // This transformation requires dominator and immediate dominator info |
| 49 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Chris Lattner | cb2610e | 2002-10-21 20:00:28 +0000 | [diff] [blame] | 50 | AU.setPreservesCFG(); |
Chris Lattner | 38e66bd | 2004-04-10 21:11:11 +0000 | [diff] [blame] | 51 | AU.addRequired<DominatorTree>(); |
Chris Lattner | 14987f1 | 2002-08-30 20:22:29 +0000 | [diff] [blame] | 52 | AU.addRequired<ValueNumbering>(); |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 53 | } |
| 54 | }; |
Chris Lattner | f629309 | 2002-07-23 18:06:35 +0000 | [diff] [blame] | 55 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 56 | char GCSE::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 57 | RegisterPass<GCSE> X("gcse", "Global Common Subexpression Elimination"); |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 58 | } |
| 59 | |
| 60 | // createGCSEPass - The public interface to this file... |
Chris Lattner | d745602 | 2004-01-09 06:02:20 +0000 | [diff] [blame] | 61 | FunctionPass *llvm::createGCSEPass() { return new GCSE(); } |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 62 | |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 63 | // GCSE::runOnFunction - This is the main transformation entry point for a |
| 64 | // function. |
| 65 | // |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 66 | bool GCSE::runOnFunction(Function &F) { |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 67 | bool Changed = false; |
| 68 | |
Chris Lattner | d456ec9 | 2002-08-22 18:24:48 +0000 | [diff] [blame] | 69 | // Get pointers to the analysis results that we will be using... |
Chris Lattner | 38e66bd | 2004-04-10 21:11:11 +0000 | [diff] [blame] | 70 | DominatorTree &DT = getAnalysis<DominatorTree>(); |
Devang Patel | 387b8cb | 2007-06-07 18:40:55 +0000 | [diff] [blame] | 71 | ValueNumbering &VN = getAnalysis<ValueNumbering>(); |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 72 | |
Chris Lattner | 38e66bd | 2004-04-10 21:11:11 +0000 | [diff] [blame] | 73 | std::vector<Value*> EqualValues; |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 74 | |
Chris Lattner | 057f78a | 2004-05-23 21:19:55 +0000 | [diff] [blame] | 75 | // Check for value numbers of arguments. If the value numbering |
| 76 | // implementation can prove that an incoming argument is a constant or global |
| 77 | // value address, substitute it, making the argument dead. |
Chris Lattner | e34e9a2 | 2007-04-14 23:32:02 +0000 | [diff] [blame] | 78 | for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;++AI) |
Chris Lattner | 057f78a | 2004-05-23 21:19:55 +0000 | [diff] [blame] | 79 | if (!AI->use_empty()) { |
| 80 | VN.getEqualNumberNodes(AI, EqualValues); |
| 81 | if (!EqualValues.empty()) { |
| 82 | for (unsigned i = 0, e = EqualValues.size(); i != e; ++i) |
Reid Spencer | 460f16c | 2004-07-18 00:32:14 +0000 | [diff] [blame] | 83 | if (isa<Constant>(EqualValues[i])) { |
Chris Lattner | 057f78a | 2004-05-23 21:19:55 +0000 | [diff] [blame] | 84 | AI->replaceAllUsesWith(EqualValues[i]); |
| 85 | ++NumArgsRepl; |
| 86 | Changed = true; |
| 87 | break; |
| 88 | } |
| 89 | EqualValues.clear(); |
| 90 | } |
| 91 | } |
| 92 | |
Chris Lattner | 38e66bd | 2004-04-10 21:11:11 +0000 | [diff] [blame] | 93 | // Traverse the CFG of the function in dominator order, so that we see each |
| 94 | // instruction after we see its operands. |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 95 | for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), |
Chris Lattner | 38e66bd | 2004-04-10 21:11:11 +0000 | [diff] [blame] | 96 | E = df_end(DT.getRootNode()); DI != E; ++DI) { |
| 97 | BasicBlock *BB = DI->getBlock(); |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 98 | |
Chris Lattner | 38e66bd | 2004-04-10 21:11:11 +0000 | [diff] [blame] | 99 | // Remember which instructions we've seen in this basic block as we scan. |
| 100 | std::set<Instruction*> BlockInsts; |
Chris Lattner | 14987f1 | 2002-08-30 20:22:29 +0000 | [diff] [blame] | 101 | |
Chris Lattner | 38e66bd | 2004-04-10 21:11:11 +0000 | [diff] [blame] | 102 | for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { |
| 103 | Instruction *Inst = I++; |
| 104 | |
Chris Lattner | fb851ab | 2004-12-12 18:23:20 +0000 | [diff] [blame] | 105 | if (Constant *C = ConstantFoldInstruction(Inst)) { |
| 106 | ReplaceInstructionWith(Inst, C); |
| 107 | } else if (Inst->getType() != Type::VoidTy) { |
| 108 | // If this instruction computes a value, try to fold together common |
| 109 | // instructions that compute it. |
| 110 | // |
Chris Lattner | 38e66bd | 2004-04-10 21:11:11 +0000 | [diff] [blame] | 111 | VN.getEqualNumberNodes(Inst, EqualValues); |
| 112 | |
| 113 | // If this instruction computes a value that is already computed |
| 114 | // elsewhere, try to recycle the old value. |
| 115 | if (!EqualValues.empty()) { |
| 116 | if (Inst == &*BB->begin()) |
| 117 | I = BB->end(); |
| 118 | else { |
| 119 | I = Inst; --I; |
| 120 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 121 | |
Chris Lattner | 38e66bd | 2004-04-10 21:11:11 +0000 | [diff] [blame] | 122 | // First check to see if we were able to value number this instruction |
| 123 | // to a non-instruction value. If so, prefer that value over other |
| 124 | // instructions which may compute the same thing. |
| 125 | for (unsigned i = 0, e = EqualValues.size(); i != e; ++i) |
| 126 | if (!isa<Instruction>(EqualValues[i])) { |
| 127 | ++NumNonInsts; // Keep track of # of insts repl with values |
| 128 | |
| 129 | // Change all users of Inst to use the replacement and remove it |
| 130 | // from the program. |
| 131 | ReplaceInstructionWith(Inst, EqualValues[i]); |
| 132 | Inst = 0; |
| 133 | EqualValues.clear(); // don't enter the next loop |
| 134 | break; |
| 135 | } |
| 136 | |
| 137 | // If there were no non-instruction values that this instruction |
| 138 | // produces, find a dominating instruction that produces the same |
| 139 | // value. If we find one, use it's value instead of ours. |
| 140 | for (unsigned i = 0, e = EqualValues.size(); i != e; ++i) { |
| 141 | Instruction *OtherI = cast<Instruction>(EqualValues[i]); |
| 142 | bool Dominates = false; |
| 143 | if (OtherI->getParent() == BB) |
| 144 | Dominates = BlockInsts.count(OtherI); |
| 145 | else |
Devang Patel | a97e040 | 2007-06-07 18:45:06 +0000 | [diff] [blame] | 146 | Dominates = DT.dominates(OtherI->getParent(), BB); |
Chris Lattner | 38e66bd | 2004-04-10 21:11:11 +0000 | [diff] [blame] | 147 | |
| 148 | if (Dominates) { |
| 149 | // Okay, we found an instruction with the same value as this one |
| 150 | // and that dominates this one. Replace this instruction with the |
| 151 | // specified one. |
| 152 | ReplaceInstructionWith(Inst, OtherI); |
| 153 | Inst = 0; |
| 154 | break; |
| 155 | } |
| 156 | } |
| 157 | |
| 158 | EqualValues.clear(); |
| 159 | |
| 160 | if (Inst) { |
| 161 | I = Inst; ++I; // Deleted no instructions |
| 162 | } else if (I == BB->end()) { // Deleted first instruction |
| 163 | I = BB->begin(); |
| 164 | } else { // Deleted inst in middle of block. |
| 165 | ++I; |
| 166 | } |
| 167 | } |
| 168 | |
| 169 | if (Inst) |
| 170 | BlockInsts.insert(Inst); |
| 171 | } |
Chris Lattner | 14987f1 | 2002-08-30 20:22:29 +0000 | [diff] [blame] | 172 | } |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 173 | } |
Chris Lattner | 18fb2a6 | 2002-05-14 05:02:40 +0000 | [diff] [blame] | 174 | |
Chris Lattner | d80e973 | 2002-04-28 00:47:11 +0000 | [diff] [blame] | 175 | // When the worklist is empty, return whether or not we changed anything... |
| 176 | return Changed; |
| 177 | } |
| 178 | |
Chris Lattner | 14987f1 | 2002-08-30 20:22:29 +0000 | [diff] [blame] | 179 | |
Chris Lattner | 38e66bd | 2004-04-10 21:11:11 +0000 | [diff] [blame] | 180 | void GCSE::ReplaceInstructionWith(Instruction *I, Value *V) { |
| 181 | if (isa<LoadInst>(I)) |
| 182 | ++NumLoadRemoved; // Keep track of loads eliminated |
| 183 | if (isa<CallInst>(I)) |
| 184 | ++NumCallRemoved; // Keep track of calls eliminated |
| 185 | ++NumInstRemoved; // Keep track of number of insts eliminated |
Chris Lattner | 14987f1 | 2002-08-30 20:22:29 +0000 | [diff] [blame] | 186 | |
Chris Lattner | adb7c0d | 2004-04-10 22:33:34 +0000 | [diff] [blame] | 187 | // Update value numbering |
Chris Lattner | 057f78a | 2004-05-23 21:19:55 +0000 | [diff] [blame] | 188 | getAnalysis<ValueNumbering>().deleteValue(I); |
Chris Lattner | adb7c0d | 2004-04-10 22:33:34 +0000 | [diff] [blame] | 189 | |
Chris Lattner | fb851ab | 2004-12-12 18:23:20 +0000 | [diff] [blame] | 190 | I->replaceAllUsesWith(V); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 191 | |
Chris Lattner | 1708d12 | 2004-04-12 05:15:13 +0000 | [diff] [blame] | 192 | if (InvokeInst *II = dyn_cast<InvokeInst>(I)) { |
| 193 | // Removing an invoke instruction requires adding a branch to the normal |
| 194 | // destination and removing PHI node entries in the exception destination. |
| 195 | new BranchInst(II->getNormalDest(), II); |
| 196 | II->getUnwindDest()->removePredecessor(II->getParent()); |
| 197 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 198 | |
Chris Lattner | 38e66bd | 2004-04-10 21:11:11 +0000 | [diff] [blame] | 199 | // Erase the instruction from the program. |
| 200 | I->getParent()->getInstList().erase(I); |
Chris Lattner | 18fb2a6 | 2002-05-14 05:02:40 +0000 | [diff] [blame] | 201 | } |