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