Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 1 | //===- GVNPRE.cpp - Eliminate redundant values and expressions ------------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by the Owen Anderson and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This pass performs a hybrid of global value numbering and partial redundancy |
| 11 | // elimination, known as GVN-PRE. It performs partial redundancy elimination on |
| 12 | // values, rather than lexical expressions, allowing a more comprehensive view |
| 13 | // the optimization. It replaces redundant values with uses of earlier |
| 14 | // occurences of the same value. While this is beneficial in that it eliminates |
| 15 | // unneeded computation, it also increases register pressure by creating large |
Owen Anderson | b232efa | 2007-06-08 20:57:08 +0000 | [diff] [blame] | 16 | // live ranges, and should be used with caution on platforms that are very |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 17 | // sensitive to register pressure. |
| 18 | // |
| 19 | //===----------------------------------------------------------------------===// |
| 20 | |
| 21 | #define DEBUG_TYPE "gvnpre" |
| 22 | #include "llvm/Value.h" |
| 23 | #include "llvm/Transforms/Scalar.h" |
| 24 | #include "llvm/Instructions.h" |
| 25 | #include "llvm/Function.h" |
| 26 | #include "llvm/Analysis/Dominators.h" |
| 27 | #include "llvm/Analysis/PostDominators.h" |
| 28 | #include "llvm/ADT/DepthFirstIterator.h" |
| 29 | #include "llvm/ADT/Statistic.h" |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 30 | #include "llvm/Support/CFG.h" |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 31 | #include "llvm/Support/Compiler.h" |
Owen Anderson | 4a6ec8f | 2007-05-29 23:15:21 +0000 | [diff] [blame] | 32 | #include "llvm/Support/Debug.h" |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 33 | #include <algorithm> |
Owen Anderson | 331bf6a | 2007-05-31 22:44:11 +0000 | [diff] [blame] | 34 | #include <deque> |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 35 | #include <map> |
Owen Anderson | 331bf6a | 2007-05-31 22:44:11 +0000 | [diff] [blame] | 36 | #include <vector> |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 37 | #include <set> |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 38 | using namespace llvm; |
| 39 | |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 40 | struct ExprLT { |
| 41 | bool operator()(Value* left, Value* right) { |
| 42 | if (!isa<BinaryOperator>(left) || !isa<BinaryOperator>(right)) |
| 43 | return left < right; |
| 44 | |
| 45 | BinaryOperator* BO1 = cast<BinaryOperator>(left); |
| 46 | BinaryOperator* BO2 = cast<BinaryOperator>(right); |
| 47 | |
Owen Anderson | 55994f2 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 48 | if (BO1->getOpcode() != BO2->getOpcode()) |
| 49 | return BO1->getOpcode() < BO2->getOpcode(); |
| 50 | else if ((*this)(BO1->getOperand(0), BO2->getOperand(0))) |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 51 | return true; |
| 52 | else if ((*this)(BO2->getOperand(0), BO1->getOperand(0))) |
| 53 | return false; |
| 54 | else |
| 55 | return (*this)(BO1->getOperand(1), BO2->getOperand(1)); |
| 56 | } |
| 57 | }; |
| 58 | |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 59 | namespace { |
| 60 | |
| 61 | class VISIBILITY_HIDDEN GVNPRE : public FunctionPass { |
| 62 | bool runOnFunction(Function &F); |
| 63 | public: |
| 64 | static char ID; // Pass identification, replacement for typeid |
| 65 | GVNPRE() : FunctionPass((intptr_t)&ID) { nextValueNumber = 0; } |
| 66 | |
| 67 | private: |
| 68 | uint32_t nextValueNumber; |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 69 | typedef std::map<Value*, uint32_t, ExprLT> ValueTable; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 70 | ValueTable VN; |
| 71 | std::set<Value*, ExprLT> MS; |
| 72 | std::set<Instruction*> createdExpressions; |
Owen Anderson | 81d156e | 2007-05-31 00:42:15 +0000 | [diff] [blame] | 73 | |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 74 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 75 | AU.setPreservesCFG(); |
| 76 | AU.addRequired<DominatorTree>(); |
| 77 | AU.addRequired<PostDominatorTree>(); |
| 78 | } |
| 79 | |
| 80 | // Helper fuctions |
| 81 | // FIXME: eliminate or document these better |
Owen Anderson | 2e5efc3 | 2007-06-08 01:52:45 +0000 | [diff] [blame] | 82 | void dump(const std::set<Value*>& s) const; |
| 83 | void dump_unique(const std::set<Value*, ExprLT>& s) const; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 84 | void clean(std::set<Value*, ExprLT>& set); |
| 85 | bool add(Value* V, uint32_t number); |
| 86 | Value* find_leader(std::set<Value*, ExprLT>& vals, |
| 87 | Value* v); |
| 88 | Value* phi_translate(std::set<Value*, ExprLT>& set, |
Owen Anderson | 38b6b22 | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 89 | Value* V, BasicBlock* pred); |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 90 | void phi_translate_set(std::set<Value*, ExprLT>& anticIn, BasicBlock* B, |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 91 | std::set<Value*, ExprLT>& out); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 92 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 93 | void topo_sort(std::set<Value*, ExprLT>& set, |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 94 | std::vector<Value*>& vec); |
Owen Anderson | 331bf6a | 2007-05-31 22:44:11 +0000 | [diff] [blame] | 95 | |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 96 | // For a given block, calculate the generated expressions, temporaries, |
| 97 | // and the AVAIL_OUT set |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 98 | void CalculateAvailOut(DomTreeNode* DI, |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 99 | std::set<Value*, ExprLT>& currExps, |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 100 | std::set<PHINode*>& currPhis, |
Owen Anderson | 0eca9aa | 2007-06-03 22:02:14 +0000 | [diff] [blame] | 101 | std::set<Value*>& currTemps, |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 102 | std::set<Value*, ExprLT>& currAvail, |
| 103 | std::map<BasicBlock*, std::set<Value*, ExprLT> > availOut); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 104 | |
| 105 | }; |
| 106 | |
| 107 | char GVNPRE::ID = 0; |
| 108 | |
| 109 | } |
| 110 | |
| 111 | FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); } |
| 112 | |
| 113 | RegisterPass<GVNPRE> X("gvnpre", |
| 114 | "Global Value Numbering/Partial Redundancy Elimination"); |
| 115 | |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 116 | |
Owen Anderson | 7d76b2a | 2007-06-08 22:02:36 +0000 | [diff] [blame^] | 117 | STATISTIC(NumInsertedVals, "Number of values inserted"); |
| 118 | STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted"); |
| 119 | STATISTIC(NumEliminated, "Number of redundant instructions eliminated"); |
| 120 | |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 121 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 122 | bool GVNPRE::add(Value* V, uint32_t number) { |
| 123 | std::pair<ValueTable::iterator, bool> ret = VN.insert(std::make_pair(V, number)); |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 124 | if (isa<BinaryOperator>(V) || isa<PHINode>(V)) |
| 125 | MS.insert(V); |
| 126 | return ret.second; |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 127 | } |
| 128 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 129 | Value* GVNPRE::find_leader(std::set<Value*, ExprLT>& vals, Value* v) { |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 130 | for (std::set<Value*, ExprLT>::iterator I = vals.begin(), E = vals.end(); |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 131 | I != E; ++I) { |
| 132 | assert(VN.find(v) != VN.end() && "Value not numbered?"); |
| 133 | assert(VN.find(*I) != VN.end() && "Value not numbered?"); |
| 134 | if (VN[v] == VN[*I]) |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 135 | return *I; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 136 | } |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 137 | |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 138 | return 0; |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 139 | } |
| 140 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 141 | Value* GVNPRE::phi_translate(std::set<Value*, ExprLT>& set, |
Owen Anderson | 38b6b22 | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 142 | Value* V, BasicBlock* pred) { |
| 143 | if (V == 0) |
| 144 | return 0; |
| 145 | |
| 146 | if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { |
Owen Anderson | 3df5299 | 2007-06-04 23:28:33 +0000 | [diff] [blame] | 147 | Value* newOp1 = isa<Instruction>(BO->getOperand(0)) |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 148 | ? phi_translate(set, |
Owen Anderson | 634a063 | 2007-06-06 01:27:49 +0000 | [diff] [blame] | 149 | find_leader(set, BO->getOperand(0)), |
Owen Anderson | 3df5299 | 2007-06-04 23:28:33 +0000 | [diff] [blame] | 150 | pred) |
| 151 | : BO->getOperand(0); |
Owen Anderson | 38b6b22 | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 152 | if (newOp1 == 0) |
| 153 | return 0; |
| 154 | |
Owen Anderson | 3df5299 | 2007-06-04 23:28:33 +0000 | [diff] [blame] | 155 | Value* newOp2 = isa<Instruction>(BO->getOperand(1)) |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 156 | ? phi_translate(set, |
Owen Anderson | 634a063 | 2007-06-06 01:27:49 +0000 | [diff] [blame] | 157 | find_leader(set, BO->getOperand(1)), |
Owen Anderson | 3df5299 | 2007-06-04 23:28:33 +0000 | [diff] [blame] | 158 | pred) |
| 159 | : BO->getOperand(1); |
Owen Anderson | 38b6b22 | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 160 | if (newOp2 == 0) |
| 161 | return 0; |
| 162 | |
| 163 | if (newOp1 != BO->getOperand(0) || newOp2 != BO->getOperand(1)) { |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 164 | Instruction* newVal = BinaryOperator::create(BO->getOpcode(), |
Owen Anderson | 38b6b22 | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 165 | newOp1, newOp2, |
| 166 | BO->getName()+".gvnpre"); |
Owen Anderson | 55994f2 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 167 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 168 | if (add(newVal, nextValueNumber)) |
| 169 | nextValueNumber++; |
Owen Anderson | 634a063 | 2007-06-06 01:27:49 +0000 | [diff] [blame] | 170 | if (!find_leader(set, newVal)) { |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 171 | DOUT << "Creating value: " << std::hex << newVal << std::dec << "\n"; |
| 172 | createdExpressions.insert(newVal); |
Owen Anderson | 38b6b22 | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 173 | return newVal; |
Owen Anderson | c847209 | 2007-06-05 22:11:49 +0000 | [diff] [blame] | 174 | } else { |
Owen Anderson | 55994f2 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 175 | ValueTable::iterator I = VN.find(newVal); |
| 176 | if (I->first == newVal) |
| 177 | VN.erase(newVal); |
| 178 | |
| 179 | std::set<Value*, ExprLT>::iterator F = MS.find(newVal); |
| 180 | if (*F == newVal) |
| 181 | MS.erase(newVal); |
| 182 | |
Owen Anderson | c847209 | 2007-06-05 22:11:49 +0000 | [diff] [blame] | 183 | delete newVal; |
Owen Anderson | 38b6b22 | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 184 | return 0; |
Owen Anderson | c847209 | 2007-06-05 22:11:49 +0000 | [diff] [blame] | 185 | } |
Owen Anderson | 38b6b22 | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 186 | } |
| 187 | } else if (PHINode* P = dyn_cast<PHINode>(V)) { |
| 188 | if (P->getParent() == pred->getTerminator()->getSuccessor(0)) |
| 189 | return P->getIncomingValueForBlock(pred); |
| 190 | } |
| 191 | |
| 192 | return V; |
| 193 | } |
| 194 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 195 | void GVNPRE::phi_translate_set(std::set<Value*, ExprLT>& anticIn, BasicBlock* B, |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 196 | std::set<Value*, ExprLT>& out) { |
Owen Anderson | 38b6b22 | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 197 | for (std::set<Value*, ExprLT>::iterator I = anticIn.begin(), |
| 198 | E = anticIn.end(); I != E; ++I) { |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 199 | Value* V = phi_translate(anticIn, *I, B); |
Owen Anderson | 38b6b22 | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 200 | if (V != 0) |
| 201 | out.insert(V); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 202 | } |
| 203 | } |
| 204 | |
| 205 | // Remove all expressions whose operands are not themselves in the set |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 206 | void GVNPRE::clean(std::set<Value*, ExprLT>& set) { |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 207 | std::vector<Value*> worklist; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 208 | topo_sort(set, worklist); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 209 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 210 | for (unsigned i = 0; i < worklist.size(); ++i) { |
| 211 | Value* v = worklist[i]; |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 212 | |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 213 | if (BinaryOperator* BO = dyn_cast<BinaryOperator>(v)) { |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 214 | bool lhsValid = !isa<Instruction>(BO->getOperand(0)); |
| 215 | if (!lhsValid) |
| 216 | for (std::set<Value*, ExprLT>::iterator I = set.begin(), E = set.end(); |
| 217 | I != E; ++I) |
| 218 | if (VN[*I] == VN[BO->getOperand(0)]) { |
| 219 | lhsValid = true; |
| 220 | break; |
| 221 | } |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 222 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 223 | bool rhsValid = !isa<Instruction>(BO->getOperand(1)); |
| 224 | if (!rhsValid) |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 225 | for (std::set<Value*, ExprLT>::iterator I = set.begin(), E = set.end(); |
| 226 | I != E; ++I) |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 227 | if (VN[*I] == VN[BO->getOperand(1)]) { |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 228 | rhsValid = true; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 229 | break; |
| 230 | } |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 231 | |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 232 | if (!lhsValid || !rhsValid) |
| 233 | set.erase(BO); |
| 234 | } |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 235 | } |
| 236 | } |
| 237 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 238 | void GVNPRE::topo_sort(std::set<Value*, ExprLT>& set, |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 239 | std::vector<Value*>& vec) { |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 240 | std::set<Value*, ExprLT> toErase; |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 241 | for (std::set<Value*, ExprLT>::iterator I = set.begin(), E = set.end(); |
Owen Anderson | 331bf6a | 2007-05-31 22:44:11 +0000 | [diff] [blame] | 242 | I != E; ++I) { |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 243 | if (BinaryOperator* BO = dyn_cast<BinaryOperator>(*I)) |
| 244 | for (std::set<Value*, ExprLT>::iterator SI = set.begin(); SI != E; ++SI) { |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 245 | if (VN[BO->getOperand(0)] == VN[*SI] || |
| 246 | VN[BO->getOperand(1)] == VN[*SI]) { |
| 247 | toErase.insert(*SI); |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 248 | } |
Owen Anderson | 331bf6a | 2007-05-31 22:44:11 +0000 | [diff] [blame] | 249 | } |
| 250 | } |
| 251 | |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 252 | std::vector<Value*> Q; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 253 | for (std::set<Value*, ExprLT>::iterator I = set.begin(), E = set.end(); |
| 254 | I != E; ++I) { |
| 255 | if (toErase.find(*I) == toErase.end()) |
| 256 | Q.push_back(*I); |
| 257 | } |
Owen Anderson | 331bf6a | 2007-05-31 22:44:11 +0000 | [diff] [blame] | 258 | |
Owen Anderson | ddbe430 | 2007-06-05 23:46:12 +0000 | [diff] [blame] | 259 | std::set<Value*> visited; |
Owen Anderson | 331bf6a | 2007-05-31 22:44:11 +0000 | [diff] [blame] | 260 | while (!Q.empty()) { |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 261 | Value* e = Q.back(); |
| 262 | |
| 263 | if (BinaryOperator* BO = dyn_cast<BinaryOperator>(e)) { |
Owen Anderson | 634a063 | 2007-06-06 01:27:49 +0000 | [diff] [blame] | 264 | Value* l = find_leader(set, BO->getOperand(0)); |
| 265 | Value* r = find_leader(set, BO->getOperand(1)); |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 266 | |
Owen Anderson | ddbe430 | 2007-06-05 23:46:12 +0000 | [diff] [blame] | 267 | if (l != 0 && isa<Instruction>(l) && |
| 268 | visited.find(l) == visited.end()) |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 269 | Q.push_back(l); |
Owen Anderson | ddbe430 | 2007-06-05 23:46:12 +0000 | [diff] [blame] | 270 | else if (r != 0 && isa<Instruction>(r) && |
| 271 | visited.find(r) == visited.end()) |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 272 | Q.push_back(r); |
| 273 | else { |
| 274 | vec.push_back(e); |
| 275 | visited.insert(e); |
| 276 | Q.pop_back(); |
| 277 | } |
| 278 | } else { |
Owen Anderson | 331bf6a | 2007-05-31 22:44:11 +0000 | [diff] [blame] | 279 | visited.insert(e); |
| 280 | vec.push_back(e); |
| 281 | Q.pop_back(); |
Owen Anderson | 331bf6a | 2007-05-31 22:44:11 +0000 | [diff] [blame] | 282 | } |
| 283 | } |
| 284 | } |
| 285 | |
Owen Anderson | 0eca9aa | 2007-06-03 22:02:14 +0000 | [diff] [blame] | 286 | |
Owen Anderson | 2e5efc3 | 2007-06-08 01:52:45 +0000 | [diff] [blame] | 287 | void GVNPRE::dump(const std::set<Value*>& s) const { |
Owen Anderson | 4a6ec8f | 2007-05-29 23:15:21 +0000 | [diff] [blame] | 288 | DOUT << "{ "; |
Owen Anderson | 0eca9aa | 2007-06-03 22:02:14 +0000 | [diff] [blame] | 289 | for (std::set<Value*>::iterator I = s.begin(), E = s.end(); |
| 290 | I != E; ++I) { |
| 291 | DEBUG((*I)->dump()); |
| 292 | } |
| 293 | DOUT << "}\n\n"; |
| 294 | } |
| 295 | |
Owen Anderson | 2e5efc3 | 2007-06-08 01:52:45 +0000 | [diff] [blame] | 296 | void GVNPRE::dump_unique(const std::set<Value*, ExprLT>& s) const { |
Owen Anderson | 0eca9aa | 2007-06-03 22:02:14 +0000 | [diff] [blame] | 297 | DOUT << "{ "; |
| 298 | for (std::set<Value*>::iterator I = s.begin(), E = s.end(); |
Owen Anderson | 331bf6a | 2007-05-31 22:44:11 +0000 | [diff] [blame] | 299 | I != E; ++I) { |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 300 | DEBUG((*I)->dump()); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 301 | } |
Owen Anderson | 4a6ec8f | 2007-05-29 23:15:21 +0000 | [diff] [blame] | 302 | DOUT << "}\n\n"; |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 303 | } |
| 304 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 305 | void GVNPRE::CalculateAvailOut(DomTreeNode* DI, |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 306 | std::set<Value*, ExprLT>& currExps, |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 307 | std::set<PHINode*>& currPhis, |
Owen Anderson | 0eca9aa | 2007-06-03 22:02:14 +0000 | [diff] [blame] | 308 | std::set<Value*>& currTemps, |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 309 | std::set<Value*, ExprLT>& currAvail, |
| 310 | std::map<BasicBlock*, std::set<Value*, ExprLT> > availOut) { |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 311 | |
| 312 | BasicBlock* BB = DI->getBlock(); |
| 313 | |
| 314 | // A block inherits AVAIL_OUT from its dominator |
| 315 | if (DI->getIDom() != 0) |
| 316 | currAvail.insert(availOut[DI->getIDom()->getBlock()].begin(), |
| 317 | availOut[DI->getIDom()->getBlock()].end()); |
| 318 | |
| 319 | |
| 320 | for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); |
| 321 | BI != BE; ++BI) { |
| 322 | |
| 323 | // Handle PHI nodes... |
| 324 | if (PHINode* p = dyn_cast<PHINode>(BI)) { |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 325 | if (add(p, nextValueNumber)) |
| 326 | nextValueNumber++; |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 327 | currPhis.insert(p); |
| 328 | |
| 329 | // Handle binary ops... |
| 330 | } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(BI)) { |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 331 | Value* leftValue = BO->getOperand(0); |
| 332 | Value* rightValue = BO->getOperand(1); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 333 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 334 | if (add(BO, nextValueNumber)) |
| 335 | nextValueNumber++; |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 336 | |
Owen Anderson | 3df5299 | 2007-06-04 23:28:33 +0000 | [diff] [blame] | 337 | if (isa<Instruction>(leftValue)) |
| 338 | currExps.insert(leftValue); |
| 339 | if (isa<Instruction>(rightValue)) |
| 340 | currExps.insert(rightValue); |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 341 | currExps.insert(BO); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 342 | |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 343 | // Handle unsupported ops |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 344 | } else if (!BI->isTerminator()){ |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 345 | if (add(BI, nextValueNumber)) |
| 346 | nextValueNumber++; |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 347 | currTemps.insert(BI); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 348 | } |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 349 | |
| 350 | if (!BI->isTerminator()) |
| 351 | currAvail.insert(BI); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 352 | } |
| 353 | } |
| 354 | |
| 355 | bool GVNPRE::runOnFunction(Function &F) { |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 356 | VN.clear(); |
| 357 | MS.clear(); |
| 358 | createdExpressions.clear(); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 359 | |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 360 | std::map<BasicBlock*, std::set<Value*, ExprLT> > generatedExpressions; |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 361 | std::map<BasicBlock*, std::set<PHINode*> > generatedPhis; |
Owen Anderson | 0eca9aa | 2007-06-03 22:02:14 +0000 | [diff] [blame] | 362 | std::map<BasicBlock*, std::set<Value*> > generatedTemporaries; |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 363 | std::map<BasicBlock*, std::set<Value*, ExprLT> > availableOut; |
| 364 | std::map<BasicBlock*, std::set<Value*, ExprLT> > anticipatedIn; |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 365 | |
| 366 | DominatorTree &DT = getAnalysis<DominatorTree>(); |
| 367 | |
Owen Anderson | 634a063 | 2007-06-06 01:27:49 +0000 | [diff] [blame] | 368 | // Phase 1: BuildSets |
| 369 | |
| 370 | // Phase 1, Part 1: calculate AVAIL_OUT |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 371 | |
| 372 | // Top-down walk of the dominator tree |
Devang Patel | bdd1aae | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 373 | for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 374 | E = df_end(DT.getRootNode()); DI != E; ++DI) { |
| 375 | |
| 376 | // Get the sets to update for this block |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 377 | std::set<Value*, ExprLT>& currExps = generatedExpressions[DI->getBlock()]; |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 378 | std::set<PHINode*>& currPhis = generatedPhis[DI->getBlock()]; |
Owen Anderson | 0eca9aa | 2007-06-03 22:02:14 +0000 | [diff] [blame] | 379 | std::set<Value*>& currTemps = generatedTemporaries[DI->getBlock()]; |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 380 | std::set<Value*, ExprLT>& currAvail = availableOut[DI->getBlock()]; |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 381 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 382 | CalculateAvailOut(*DI, currExps, currPhis, |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 383 | currTemps, currAvail, availableOut); |
| 384 | } |
| 385 | |
Owen Anderson | 9b89e4b | 2007-06-05 17:31:23 +0000 | [diff] [blame] | 386 | DOUT << "Maximal Set: "; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 387 | dump_unique(MS); |
Owen Anderson | 9b89e4b | 2007-06-05 17:31:23 +0000 | [diff] [blame] | 388 | DOUT << "\n"; |
| 389 | |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 390 | PostDominatorTree &PDT = getAnalysis<PostDominatorTree>(); |
| 391 | |
Owen Anderson | 634a063 | 2007-06-06 01:27:49 +0000 | [diff] [blame] | 392 | // Phase 1, Part 2: calculate ANTIC_IN |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 393 | |
Owen Anderson | 0c42307 | 2007-05-29 23:26:30 +0000 | [diff] [blame] | 394 | std::set<BasicBlock*> visited; |
| 395 | |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 396 | bool changed = true; |
| 397 | unsigned iterations = 0; |
| 398 | while (changed) { |
| 399 | changed = false; |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 400 | std::set<Value*, ExprLT> anticOut; |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 401 | |
| 402 | // Top-down walk of the postdominator tree |
Devang Patel | bdd1aae | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 403 | for (df_iterator<DomTreeNode*> PDI = |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 404 | df_begin(PDT.getRootNode()), E = df_end(PDT.getRootNode()); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 405 | PDI != E; ++PDI) { |
| 406 | BasicBlock* BB = PDI->getBlock(); |
Owen Anderson | 3df5299 | 2007-06-04 23:28:33 +0000 | [diff] [blame] | 407 | DOUT << "Block: " << BB->getName() << "\n"; |
| 408 | DOUT << "TMP_GEN: "; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 409 | dump(generatedTemporaries[BB]); |
Owen Anderson | 3df5299 | 2007-06-04 23:28:33 +0000 | [diff] [blame] | 410 | DOUT << "\n"; |
| 411 | |
| 412 | DOUT << "EXP_GEN: "; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 413 | dump_unique(generatedExpressions[BB]); |
Owen Anderson | 0c42307 | 2007-05-29 23:26:30 +0000 | [diff] [blame] | 414 | visited.insert(BB); |
| 415 | |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 416 | std::set<Value*, ExprLT>& anticIn = anticipatedIn[BB]; |
| 417 | std::set<Value*, ExprLT> old (anticIn.begin(), anticIn.end()); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 418 | |
| 419 | if (BB->getTerminator()->getNumSuccessors() == 1) { |
Owen Anderson | 9b89e4b | 2007-06-05 17:31:23 +0000 | [diff] [blame] | 420 | if (visited.find(BB->getTerminator()->getSuccessor(0)) == |
| 421 | visited.end()) |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 422 | phi_translate_set(MS, BB, anticOut); |
Owen Anderson | 81d156e | 2007-05-31 00:42:15 +0000 | [diff] [blame] | 423 | else |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 424 | phi_translate_set( |
Owen Anderson | 9b89e4b | 2007-06-05 17:31:23 +0000 | [diff] [blame] | 425 | anticipatedIn[BB->getTerminator()->getSuccessor(0)], BB, anticOut); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 426 | } else if (BB->getTerminator()->getNumSuccessors() > 1) { |
Owen Anderson | 3df5299 | 2007-06-04 23:28:33 +0000 | [diff] [blame] | 427 | BasicBlock* first = BB->getTerminator()->getSuccessor(0); |
| 428 | anticOut.insert(anticipatedIn[first].begin(), |
| 429 | anticipatedIn[first].end()); |
| 430 | for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) { |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 431 | BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i); |
Owen Anderson | 3df5299 | 2007-06-04 23:28:33 +0000 | [diff] [blame] | 432 | std::set<Value*, ExprLT>& succAnticIn = anticipatedIn[currSucc]; |
| 433 | |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 434 | std::set<Value*, ExprLT> temp; |
Owen Anderson | 3df5299 | 2007-06-04 23:28:33 +0000 | [diff] [blame] | 435 | std::insert_iterator<std::set<Value*, ExprLT> > temp_ins(temp, |
| 436 | temp.begin()); |
| 437 | std::set_intersection(anticOut.begin(), anticOut.end(), |
| 438 | succAnticIn.begin(), succAnticIn.end(), |
| 439 | temp_ins, ExprLT()); |
| 440 | |
| 441 | anticOut.clear(); |
| 442 | anticOut.insert(temp.begin(), temp.end()); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 443 | } |
| 444 | } |
| 445 | |
Owen Anderson | 3df5299 | 2007-06-04 23:28:33 +0000 | [diff] [blame] | 446 | DOUT << "ANTIC_OUT: "; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 447 | dump_unique(anticOut); |
Owen Anderson | 3df5299 | 2007-06-04 23:28:33 +0000 | [diff] [blame] | 448 | DOUT << "\n"; |
| 449 | |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 450 | std::set<Value*, ExprLT> S; |
| 451 | std::insert_iterator<std::set<Value*, ExprLT> > s_ins(S, S.begin()); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 452 | std::set_union(anticOut.begin(), anticOut.end(), |
| 453 | generatedExpressions[BB].begin(), |
| 454 | generatedExpressions[BB].end(), |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 455 | s_ins, ExprLT()); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 456 | |
| 457 | anticIn.clear(); |
Owen Anderson | 3c9d8ee | 2007-06-04 23:34:56 +0000 | [diff] [blame] | 458 | |
| 459 | for (std::set<Value*, ExprLT>::iterator I = S.begin(), E = S.end(); |
| 460 | I != E; ++I) { |
| 461 | if (generatedTemporaries[BB].find(*I) == generatedTemporaries[BB].end()) |
| 462 | anticIn.insert(*I); |
| 463 | } |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 464 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 465 | clean(anticIn); |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 466 | |
Owen Anderson | 3df5299 | 2007-06-04 23:28:33 +0000 | [diff] [blame] | 467 | DOUT << "ANTIC_IN: "; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 468 | dump_unique(anticIn); |
Owen Anderson | 3df5299 | 2007-06-04 23:28:33 +0000 | [diff] [blame] | 469 | DOUT << "\n"; |
| 470 | |
Owen Anderson | ddbe430 | 2007-06-05 23:46:12 +0000 | [diff] [blame] | 471 | if (old.size() != anticIn.size()) |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 472 | changed = true; |
| 473 | |
| 474 | anticOut.clear(); |
| 475 | } |
Owen Anderson | 38b6b22 | 2007-06-04 18:05:26 +0000 | [diff] [blame] | 476 | |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 477 | iterations++; |
| 478 | } |
| 479 | |
Owen Anderson | 4a6ec8f | 2007-05-29 23:15:21 +0000 | [diff] [blame] | 480 | DOUT << "Iterations: " << iterations << "\n"; |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 481 | |
| 482 | for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { |
Owen Anderson | 4a6ec8f | 2007-05-29 23:15:21 +0000 | [diff] [blame] | 483 | DOUT << "Name: " << I->getName().c_str() << "\n"; |
| 484 | |
| 485 | DOUT << "TMP_GEN: "; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 486 | dump(generatedTemporaries[I]); |
Owen Anderson | 4a6ec8f | 2007-05-29 23:15:21 +0000 | [diff] [blame] | 487 | DOUT << "\n"; |
| 488 | |
| 489 | DOUT << "EXP_GEN: "; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 490 | dump_unique(generatedExpressions[I]); |
Owen Anderson | 4a6ec8f | 2007-05-29 23:15:21 +0000 | [diff] [blame] | 491 | DOUT << "\n"; |
| 492 | |
| 493 | DOUT << "ANTIC_IN: "; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 494 | dump_unique(anticipatedIn[I]); |
Owen Anderson | 4a6ec8f | 2007-05-29 23:15:21 +0000 | [diff] [blame] | 495 | DOUT << "\n"; |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 496 | |
| 497 | DOUT << "AVAIL_OUT: "; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 498 | dump_unique(availableOut[I]); |
Owen Anderson | 0b68cda | 2007-06-03 05:55:58 +0000 | [diff] [blame] | 499 | DOUT << "\n"; |
Owen Anderson | 4a6ec8f | 2007-05-29 23:15:21 +0000 | [diff] [blame] | 500 | } |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 501 | |
Owen Anderson | 634a063 | 2007-06-06 01:27:49 +0000 | [diff] [blame] | 502 | |
| 503 | // Phase 2: Insert |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 504 | DOUT<< "\nPhase 2: Insertion\n"; |
| 505 | |
| 506 | std::map<BasicBlock*, std::set<Value*, ExprLT> > new_sets; |
| 507 | unsigned i_iterations = 0; |
| 508 | bool new_stuff = true; |
| 509 | while (new_stuff) { |
| 510 | new_stuff = false; |
| 511 | DOUT << "Iteration: " << i_iterations << "\n\n"; |
| 512 | for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), |
| 513 | E = df_end(DT.getRootNode()); DI != E; ++DI) { |
| 514 | BasicBlock* BB = DI->getBlock(); |
| 515 | |
| 516 | std::set<Value*, ExprLT>& new_set = new_sets[BB]; |
| 517 | std::set<Value*, ExprLT>& availOut = availableOut[BB]; |
| 518 | std::set<Value*, ExprLT>& anticIn = anticipatedIn[BB]; |
| 519 | |
Owen Anderson | 55994f2 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 520 | new_set.clear(); |
| 521 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 522 | // Replace leaders with leaders inherited from dominator |
| 523 | if (DI->getIDom() != 0) { |
| 524 | std::set<Value*, ExprLT>& dom_set = new_sets[DI->getIDom()->getBlock()]; |
| 525 | for (std::set<Value*, ExprLT>::iterator I = dom_set.begin(), |
| 526 | E = dom_set.end(); I != E; ++I) { |
| 527 | new_set.insert(*I); |
| 528 | |
Owen Anderson | 55994f2 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 529 | Value* val = find_leader(availOut, *I); |
| 530 | while (val != 0) { |
Owen Anderson | 2e5efc3 | 2007-06-08 01:52:45 +0000 | [diff] [blame] | 531 | availOut.erase(val); |
Owen Anderson | 55994f2 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 532 | val = find_leader(availOut, *I); |
| 533 | } |
Owen Anderson | 2e5efc3 | 2007-06-08 01:52:45 +0000 | [diff] [blame] | 534 | availOut.insert(*I); |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 535 | } |
| 536 | } |
| 537 | |
| 538 | // If there is more than one predecessor... |
| 539 | if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) { |
| 540 | std::vector<Value*> workList; |
| 541 | topo_sort(anticIn, workList); |
| 542 | |
| 543 | DOUT << "Merge Block: " << BB->getName() << "\n"; |
| 544 | DOUT << "ANTIC_IN: "; |
| 545 | dump_unique(anticIn); |
| 546 | DOUT << "\n"; |
| 547 | |
| 548 | while (!workList.empty()) { |
| 549 | Value* e = workList.back(); |
| 550 | workList.pop_back(); |
| 551 | |
| 552 | if (isa<BinaryOperator>(e)) { |
| 553 | if (find_leader(availableOut[DI->getIDom()->getBlock()], e) != 0) |
| 554 | continue; |
| 555 | |
| 556 | std::map<BasicBlock*, Value*> avail; |
| 557 | bool by_some = false; |
| 558 | int num_avail = 0; |
| 559 | |
| 560 | for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; |
| 561 | ++PI) { |
| 562 | Value *e2 = phi_translate(anticIn, e, *PI); |
| 563 | Value *e3 = find_leader(availableOut[*PI], e2); |
| 564 | |
| 565 | if (e3 == 0) { |
| 566 | std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI); |
| 567 | if (av != avail.end()) |
| 568 | avail.erase(av); |
| 569 | avail.insert(std::make_pair(*PI, e2)); |
| 570 | } else { |
| 571 | std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI); |
| 572 | if (av != avail.end()) |
| 573 | avail.erase(av); |
| 574 | avail.insert(std::make_pair(*PI, e3)); |
| 575 | |
| 576 | by_some = true; |
| 577 | num_avail++; |
| 578 | } |
| 579 | } |
| 580 | |
| 581 | if (by_some && |
| 582 | num_avail < std::distance(pred_begin(BB), pred_end(BB))) { |
| 583 | DOUT << "Processing Value: "; |
| 584 | DEBUG(e->dump()); |
| 585 | DOUT << "\n\n"; |
| 586 | |
| 587 | for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); |
| 588 | PI != PE; ++PI) { |
| 589 | Value* e2 = avail[*PI]; |
| 590 | if (!find_leader(availableOut[*PI], e2)) { |
| 591 | BinaryOperator* BO = cast<BinaryOperator>(e2); |
| 592 | |
| 593 | Value* s1 = 0; |
| 594 | if (isa<Instruction>(BO->getOperand(0))) |
| 595 | s1 = find_leader(availableOut[*PI], BO->getOperand(0)); |
| 596 | else |
| 597 | s1 = BO->getOperand(0); |
| 598 | |
| 599 | Value* s2 = 0; |
| 600 | if (isa<Instruction>(BO->getOperand(1))) |
| 601 | s2 = find_leader(availableOut[*PI], BO->getOperand(1)); |
| 602 | else |
| 603 | s2 = BO->getOperand(1); |
| 604 | |
| 605 | Value* newVal = BinaryOperator::create(BO->getOpcode(), |
| 606 | s1, s2, |
| 607 | BO->getName()+".gvnpre", |
| 608 | (*PI)->getTerminator()); |
| 609 | add(newVal, VN[BO]); |
Owen Anderson | 55994f2 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 610 | |
| 611 | std::set<Value*, ExprLT>& predAvail = availableOut[*PI]; |
| 612 | Value* val = find_leader(predAvail, newVal); |
| 613 | while (val != 0) { |
| 614 | predAvail.erase(val); |
| 615 | val = find_leader(predAvail, newVal); |
| 616 | } |
| 617 | predAvail.insert(newVal); |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 618 | |
| 619 | DOUT << "Creating value: " << std::hex << newVal << std::dec << "\n"; |
| 620 | |
| 621 | std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI); |
| 622 | if (av != avail.end()) |
| 623 | avail.erase(av); |
| 624 | avail.insert(std::make_pair(*PI, newVal)); |
Owen Anderson | 7d76b2a | 2007-06-08 22:02:36 +0000 | [diff] [blame^] | 625 | |
| 626 | ++NumInsertedVals; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 627 | } |
| 628 | } |
| 629 | |
| 630 | PHINode* p = 0; |
| 631 | |
| 632 | for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); |
| 633 | PI != PE; ++PI) { |
| 634 | if (p == 0) |
| 635 | p = new PHINode(avail[*PI]->getType(), "gvnpre-join", |
| 636 | BB->begin()); |
| 637 | |
| 638 | p->addIncoming(avail[*PI], *PI); |
| 639 | } |
| 640 | |
| 641 | add(p, VN[e]); |
| 642 | DOUT << "Creating value: " << std::hex << p << std::dec << "\n"; |
| 643 | |
Owen Anderson | 55994f2 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 644 | Value* val = find_leader(availOut, p); |
| 645 | while (val != 0) { |
| 646 | availOut.erase(val); |
| 647 | val = find_leader(availOut, p); |
| 648 | } |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 649 | availOut.insert(p); |
Owen Anderson | 55994f2 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 650 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 651 | new_stuff = true; |
| 652 | |
| 653 | DOUT << "Preds After Processing: "; |
| 654 | for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); |
| 655 | PI != PE; ++PI) |
| 656 | DEBUG((*PI)->dump()); |
| 657 | DOUT << "\n\n"; |
| 658 | |
| 659 | DOUT << "Merge Block After Processing: "; |
| 660 | DEBUG(BB->dump()); |
| 661 | DOUT << "\n\n"; |
| 662 | |
| 663 | new_set.insert(p); |
Owen Anderson | 7d76b2a | 2007-06-08 22:02:36 +0000 | [diff] [blame^] | 664 | |
| 665 | ++NumInsertedPhis; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 666 | } |
| 667 | } |
| 668 | } |
| 669 | } |
| 670 | } |
| 671 | i_iterations++; |
| 672 | } |
Owen Anderson | 634a063 | 2007-06-06 01:27:49 +0000 | [diff] [blame] | 673 | |
| 674 | // Phase 3: Eliminate |
Owen Anderson | 55994f2 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 675 | DOUT << "\n\nPhase 3: Elimination\n\n"; |
| 676 | |
| 677 | std::vector<std::pair<Instruction*, Value*> > replace; |
| 678 | std::vector<Instruction*> erase; |
| 679 | |
Owen Anderson | 634a063 | 2007-06-06 01:27:49 +0000 | [diff] [blame] | 680 | for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), |
| 681 | E = df_end(DT.getRootNode()); DI != E; ++DI) { |
| 682 | BasicBlock* BB = DI->getBlock(); |
| 683 | |
Owen Anderson | 55994f2 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 684 | DOUT << "Block: " << BB->getName() << "\n"; |
| 685 | dump_unique(availableOut[BB]); |
| 686 | DOUT << "\n\n"; |
Owen Anderson | 634a063 | 2007-06-06 01:27:49 +0000 | [diff] [blame] | 687 | |
| 688 | for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); |
| 689 | BI != BE; ++BI) { |
Owen Anderson | 55994f2 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 690 | |
| 691 | if (isa<BinaryOperator>(BI)) { |
| 692 | Value *leader = find_leader(availableOut[BB], BI); |
| 693 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 694 | if (leader != 0) |
| 695 | if (Instruction* Instr = dyn_cast<Instruction>(leader)) |
| 696 | if (Instr->getParent() != 0 && Instr != BI) { |
Owen Anderson | 55994f2 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 697 | replace.push_back(std::make_pair(BI, leader)); |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 698 | erase.push_back(BI); |
Owen Anderson | 7d76b2a | 2007-06-08 22:02:36 +0000 | [diff] [blame^] | 699 | ++NumEliminated; |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 700 | } |
| 701 | } |
Owen Anderson | 634a063 | 2007-06-06 01:27:49 +0000 | [diff] [blame] | 702 | } |
Owen Anderson | 634a063 | 2007-06-06 01:27:49 +0000 | [diff] [blame] | 703 | } |
| 704 | |
Owen Anderson | 55994f2 | 2007-06-08 20:44:02 +0000 | [diff] [blame] | 705 | while (!replace.empty()) { |
| 706 | std::pair<Instruction*, Value*> rep = replace.back(); |
| 707 | replace.pop_back(); |
| 708 | |
| 709 | rep.first->replaceAllUsesWith(rep.second); |
| 710 | } |
| 711 | |
| 712 | for (std::vector<Instruction*>::iterator I = erase.begin(), E = erase.end(); |
| 713 | I != E; ++I) |
| 714 | (*I)->eraseFromParent(); |
| 715 | |
Owen Anderson | be80240 | 2007-06-08 01:03:01 +0000 | [diff] [blame] | 716 | // Phase 4: Cleanup |
| 717 | for (std::set<Instruction*>::iterator I = createdExpressions.begin(), |
| 718 | E = createdExpressions.end(); I != E; ++I) { |
| 719 | delete *I; |
| 720 | } |
| 721 | |
Owen Anderson | 5fba6c1 | 2007-05-29 21:53:49 +0000 | [diff] [blame] | 722 | return false; |
| 723 | } |