blob: c43603e6ddc65d6bdf50cec66347a75a5626a3c6 [file] [log] [blame]
Owen Anderson5fba6c12007-05-29 21:53:49 +00001//===- 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 Andersonb232efa2007-06-08 20:57:08 +000016// live ranges, and should be used with caution on platforms that are very
Owen Anderson5fba6c12007-05-29 21:53:49 +000017// 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 Andersonbe802402007-06-08 01:03:01 +000030#include "llvm/Support/CFG.h"
Owen Anderson5fba6c12007-05-29 21:53:49 +000031#include "llvm/Support/Compiler.h"
Owen Anderson4a6ec8f2007-05-29 23:15:21 +000032#include "llvm/Support/Debug.h"
Owen Anderson5fba6c12007-05-29 21:53:49 +000033#include <algorithm>
Owen Anderson331bf6a2007-05-31 22:44:11 +000034#include <deque>
Owen Anderson5fba6c12007-05-29 21:53:49 +000035#include <map>
Owen Anderson331bf6a2007-05-31 22:44:11 +000036#include <vector>
Owen Anderson5fba6c12007-05-29 21:53:49 +000037#include <set>
Owen Anderson5fba6c12007-05-29 21:53:49 +000038using namespace llvm;
39
Owen Anderson0b68cda2007-06-03 05:55:58 +000040struct ExprLT {
41 bool operator()(Value* left, Value* right) {
Owen Anderson223718c2007-06-09 18:35:31 +000042 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 Anderson0b68cda2007-06-03 05:55:58 +000053 return left < right;
Owen Anderson223718c2007-06-09 18:35:31 +000054 }
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 Anderson0b68cda2007-06-03 05:55:58 +000061 return true;
Owen Anderson223718c2007-06-09 18:35:31 +000062 else if ((*this)(right->getOperand(0), left->getOperand(0)))
Owen Anderson0b68cda2007-06-03 05:55:58 +000063 return false;
64 else
Owen Anderson223718c2007-06-09 18:35:31 +000065 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 Anderson0b68cda2007-06-03 05:55:58 +000079 }
80};
81
Owen Anderson5fba6c12007-05-29 21:53:49 +000082namespace {
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 Anderson223718c2007-06-09 18:35:31 +000088 GVNPRE() : FunctionPass((intptr_t)&ID) { nextValueNumber = 1; }
Owen Anderson5fba6c12007-05-29 21:53:49 +000089
90 private:
91 uint32_t nextValueNumber;
Owen Anderson0b68cda2007-06-03 05:55:58 +000092 typedef std::map<Value*, uint32_t, ExprLT> ValueTable;
Owen Andersonbe802402007-06-08 01:03:01 +000093 ValueTable VN;
94 std::set<Value*, ExprLT> MS;
95 std::set<Instruction*> createdExpressions;
Owen Anderson81d156e2007-05-31 00:42:15 +000096
Owen Anderson5fba6c12007-05-29 21:53:49 +000097 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 Anderson2e5efc32007-06-08 01:52:45 +0000105 void dump(const std::set<Value*>& s) const;
106 void dump_unique(const std::set<Value*, ExprLT>& s) const;
Owen Andersonbe802402007-06-08 01:03:01 +0000107 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 Anderson38b6b222007-06-04 18:05:26 +0000112 Value* V, BasicBlock* pred);
Owen Andersonbe802402007-06-08 01:03:01 +0000113 void phi_translate_set(std::set<Value*, ExprLT>& anticIn, BasicBlock* B,
Owen Anderson0b68cda2007-06-03 05:55:58 +0000114 std::set<Value*, ExprLT>& out);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000115
Owen Andersonbe802402007-06-08 01:03:01 +0000116 void topo_sort(std::set<Value*, ExprLT>& set,
Owen Anderson0b68cda2007-06-03 05:55:58 +0000117 std::vector<Value*>& vec);
Owen Anderson331bf6a2007-05-31 22:44:11 +0000118
Owen Anderson5fba6c12007-05-29 21:53:49 +0000119 // For a given block, calculate the generated expressions, temporaries,
120 // and the AVAIL_OUT set
Owen Andersonbe802402007-06-08 01:03:01 +0000121 void CalculateAvailOut(DomTreeNode* DI,
Owen Anderson0b68cda2007-06-03 05:55:58 +0000122 std::set<Value*, ExprLT>& currExps,
Owen Anderson5fba6c12007-05-29 21:53:49 +0000123 std::set<PHINode*>& currPhis,
Owen Anderson0eca9aa2007-06-03 22:02:14 +0000124 std::set<Value*>& currTemps,
Owen Anderson0b68cda2007-06-03 05:55:58 +0000125 std::set<Value*, ExprLT>& currAvail,
126 std::map<BasicBlock*, std::set<Value*, ExprLT> > availOut);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000127
128 };
129
130 char GVNPRE::ID = 0;
131
132}
133
134FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
135
136RegisterPass<GVNPRE> X("gvnpre",
137 "Global Value Numbering/Partial Redundancy Elimination");
138
Owen Anderson5fba6c12007-05-29 21:53:49 +0000139
Owen Anderson7d76b2a2007-06-08 22:02:36 +0000140STATISTIC(NumInsertedVals, "Number of values inserted");
141STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
142STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
143
Owen Anderson0b68cda2007-06-03 05:55:58 +0000144
Owen Andersonbe802402007-06-08 01:03:01 +0000145bool GVNPRE::add(Value* V, uint32_t number) {
146 std::pair<ValueTable::iterator, bool> ret = VN.insert(std::make_pair(V, number));
Owen Anderson223718c2007-06-09 18:35:31 +0000147 if (isa<BinaryOperator>(V) || isa<PHINode>(V) || isa<CmpInst>(V))
Owen Anderson0b68cda2007-06-03 05:55:58 +0000148 MS.insert(V);
149 return ret.second;
Owen Anderson5fba6c12007-05-29 21:53:49 +0000150}
151
Owen Andersonbe802402007-06-08 01:03:01 +0000152Value* GVNPRE::find_leader(std::set<Value*, ExprLT>& vals, Value* v) {
Owen Anderson0b68cda2007-06-03 05:55:58 +0000153 for (std::set<Value*, ExprLT>::iterator I = vals.begin(), E = vals.end();
Owen Andersonbe802402007-06-08 01:03:01 +0000154 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 Anderson0b68cda2007-06-03 05:55:58 +0000158 return *I;
Owen Andersonbe802402007-06-08 01:03:01 +0000159 }
Owen Anderson5fba6c12007-05-29 21:53:49 +0000160
Owen Anderson0b68cda2007-06-03 05:55:58 +0000161 return 0;
Owen Anderson5fba6c12007-05-29 21:53:49 +0000162}
163
Owen Andersonbe802402007-06-08 01:03:01 +0000164Value* GVNPRE::phi_translate(std::set<Value*, ExprLT>& set,
Owen Anderson38b6b222007-06-04 18:05:26 +0000165 Value* V, BasicBlock* pred) {
166 if (V == 0)
167 return 0;
168
169 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
Owen Anderson3df52992007-06-04 23:28:33 +0000170 Value* newOp1 = isa<Instruction>(BO->getOperand(0))
Owen Andersonbe802402007-06-08 01:03:01 +0000171 ? phi_translate(set,
Owen Anderson634a0632007-06-06 01:27:49 +0000172 find_leader(set, BO->getOperand(0)),
Owen Anderson3df52992007-06-04 23:28:33 +0000173 pred)
174 : BO->getOperand(0);
Owen Anderson38b6b222007-06-04 18:05:26 +0000175 if (newOp1 == 0)
176 return 0;
177
Owen Anderson3df52992007-06-04 23:28:33 +0000178 Value* newOp2 = isa<Instruction>(BO->getOperand(1))
Owen Andersonbe802402007-06-08 01:03:01 +0000179 ? phi_translate(set,
Owen Anderson634a0632007-06-06 01:27:49 +0000180 find_leader(set, BO->getOperand(1)),
Owen Anderson3df52992007-06-04 23:28:33 +0000181 pred)
182 : BO->getOperand(1);
Owen Anderson38b6b222007-06-04 18:05:26 +0000183 if (newOp2 == 0)
184 return 0;
185
186 if (newOp1 != BO->getOperand(0) || newOp2 != BO->getOperand(1)) {
Owen Andersonbe802402007-06-08 01:03:01 +0000187 Instruction* newVal = BinaryOperator::create(BO->getOpcode(),
Owen Anderson38b6b222007-06-04 18:05:26 +0000188 newOp1, newOp2,
189 BO->getName()+".gvnpre");
Owen Anderson55994f22007-06-08 20:44:02 +0000190
Owen Andersonbe802402007-06-08 01:03:01 +0000191 if (add(newVal, nextValueNumber))
192 nextValueNumber++;
Owen Anderson634a0632007-06-06 01:27:49 +0000193 if (!find_leader(set, newVal)) {
Owen Andersonbe802402007-06-08 01:03:01 +0000194 DOUT << "Creating value: " << std::hex << newVal << std::dec << "\n";
195 createdExpressions.insert(newVal);
Owen Anderson38b6b222007-06-04 18:05:26 +0000196 return newVal;
Owen Andersonc8472092007-06-05 22:11:49 +0000197 } else {
Owen Anderson55994f22007-06-08 20:44:02 +0000198 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 Andersonc8472092007-06-05 22:11:49 +0000206 delete newVal;
Owen Anderson38b6b222007-06-04 18:05:26 +0000207 return 0;
Owen Andersonc8472092007-06-05 22:11:49 +0000208 }
Owen Anderson38b6b222007-06-04 18:05:26 +0000209 }
210 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
211 if (P->getParent() == pred->getTerminator()->getSuccessor(0))
212 return P->getIncomingValueForBlock(pred);
Owen Anderson223718c2007-06-09 18:35:31 +0000213 } 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 Anderson38b6b222007-06-04 18:05:26 +0000255 }
256
257 return V;
258}
259
Owen Andersonbe802402007-06-08 01:03:01 +0000260void GVNPRE::phi_translate_set(std::set<Value*, ExprLT>& anticIn, BasicBlock* B,
Owen Anderson0b68cda2007-06-03 05:55:58 +0000261 std::set<Value*, ExprLT>& out) {
Owen Anderson38b6b222007-06-04 18:05:26 +0000262 for (std::set<Value*, ExprLT>::iterator I = anticIn.begin(),
263 E = anticIn.end(); I != E; ++I) {
Owen Andersonbe802402007-06-08 01:03:01 +0000264 Value* V = phi_translate(anticIn, *I, B);
Owen Anderson38b6b222007-06-04 18:05:26 +0000265 if (V != 0)
266 out.insert(V);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000267 }
268}
269
270// Remove all expressions whose operands are not themselves in the set
Owen Andersonbe802402007-06-08 01:03:01 +0000271void GVNPRE::clean(std::set<Value*, ExprLT>& set) {
Owen Anderson0b68cda2007-06-03 05:55:58 +0000272 std::vector<Value*> worklist;
Owen Andersonbe802402007-06-08 01:03:01 +0000273 topo_sort(set, worklist);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000274
Owen Andersonbe802402007-06-08 01:03:01 +0000275 for (unsigned i = 0; i < worklist.size(); ++i) {
276 Value* v = worklist[i];
Owen Anderson5fba6c12007-05-29 21:53:49 +0000277
Owen Anderson0b68cda2007-06-03 05:55:58 +0000278 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(v)) {
Owen Andersonbe802402007-06-08 01:03:01 +0000279 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 Anderson0b68cda2007-06-03 05:55:58 +0000287
Owen Andersonbe802402007-06-08 01:03:01 +0000288 bool rhsValid = !isa<Instruction>(BO->getOperand(1));
289 if (!rhsValid)
Owen Anderson0b68cda2007-06-03 05:55:58 +0000290 for (std::set<Value*, ExprLT>::iterator I = set.begin(), E = set.end();
291 I != E; ++I)
Owen Andersonbe802402007-06-08 01:03:01 +0000292 if (VN[*I] == VN[BO->getOperand(1)]) {
Owen Anderson0b68cda2007-06-03 05:55:58 +0000293 rhsValid = true;
Owen Andersonbe802402007-06-08 01:03:01 +0000294 break;
295 }
Owen Anderson5fba6c12007-05-29 21:53:49 +0000296
Owen Anderson0b68cda2007-06-03 05:55:58 +0000297 if (!lhsValid || !rhsValid)
298 set.erase(BO);
Owen Anderson223718c2007-06-09 18:35:31 +0000299 } 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 Anderson0b68cda2007-06-03 05:55:58 +0000320 }
Owen Anderson5fba6c12007-05-29 21:53:49 +0000321 }
322}
323
Owen Andersonbe802402007-06-08 01:03:01 +0000324void GVNPRE::topo_sort(std::set<Value*, ExprLT>& set,
Owen Anderson0b68cda2007-06-03 05:55:58 +0000325 std::vector<Value*>& vec) {
Owen Andersonbe802402007-06-08 01:03:01 +0000326 std::set<Value*, ExprLT> toErase;
Owen Anderson0b68cda2007-06-03 05:55:58 +0000327 for (std::set<Value*, ExprLT>::iterator I = set.begin(), E = set.end();
Owen Anderson331bf6a2007-05-31 22:44:11 +0000328 I != E; ++I) {
Owen Anderson0b68cda2007-06-03 05:55:58 +0000329 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(*I))
330 for (std::set<Value*, ExprLT>::iterator SI = set.begin(); SI != E; ++SI) {
Owen Andersonbe802402007-06-08 01:03:01 +0000331 if (VN[BO->getOperand(0)] == VN[*SI] ||
332 VN[BO->getOperand(1)] == VN[*SI]) {
333 toErase.insert(*SI);
Owen Anderson0b68cda2007-06-03 05:55:58 +0000334 }
Owen Anderson223718c2007-06-09 18:35:31 +0000335 }
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 Anderson331bf6a2007-05-31 22:44:11 +0000343 }
344
Owen Anderson0b68cda2007-06-03 05:55:58 +0000345 std::vector<Value*> Q;
Owen Andersonbe802402007-06-08 01:03:01 +0000346 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 Anderson331bf6a2007-05-31 22:44:11 +0000351
Owen Andersonddbe4302007-06-05 23:46:12 +0000352 std::set<Value*> visited;
Owen Anderson331bf6a2007-05-31 22:44:11 +0000353 while (!Q.empty()) {
Owen Anderson0b68cda2007-06-03 05:55:58 +0000354 Value* e = Q.back();
355
356 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(e)) {
Owen Anderson634a0632007-06-06 01:27:49 +0000357 Value* l = find_leader(set, BO->getOperand(0));
358 Value* r = find_leader(set, BO->getOperand(1));
Owen Anderson0b68cda2007-06-03 05:55:58 +0000359
Owen Andersonddbe4302007-06-05 23:46:12 +0000360 if (l != 0 && isa<Instruction>(l) &&
361 visited.find(l) == visited.end())
Owen Anderson0b68cda2007-06-03 05:55:58 +0000362 Q.push_back(l);
Owen Andersonddbe4302007-06-05 23:46:12 +0000363 else if (r != 0 && isa<Instruction>(r) &&
364 visited.find(r) == visited.end())
Owen Anderson0b68cda2007-06-03 05:55:58 +0000365 Q.push_back(r);
366 else {
367 vec.push_back(e);
368 visited.insert(e);
369 Q.pop_back();
370 }
Owen Anderson223718c2007-06-09 18:35:31 +0000371 } 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 Anderson0b68cda2007-06-03 05:55:58 +0000386 } else {
Owen Anderson331bf6a2007-05-31 22:44:11 +0000387 visited.insert(e);
388 vec.push_back(e);
389 Q.pop_back();
Owen Anderson331bf6a2007-05-31 22:44:11 +0000390 }
391 }
392}
393
Owen Anderson0eca9aa2007-06-03 22:02:14 +0000394
Owen Anderson2e5efc32007-06-08 01:52:45 +0000395void GVNPRE::dump(const std::set<Value*>& s) const {
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000396 DOUT << "{ ";
Owen Anderson0eca9aa2007-06-03 22:02:14 +0000397 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 Anderson2e5efc32007-06-08 01:52:45 +0000404void GVNPRE::dump_unique(const std::set<Value*, ExprLT>& s) const {
Owen Anderson0eca9aa2007-06-03 22:02:14 +0000405 DOUT << "{ ";
406 for (std::set<Value*>::iterator I = s.begin(), E = s.end();
Owen Anderson331bf6a2007-05-31 22:44:11 +0000407 I != E; ++I) {
Owen Anderson0b68cda2007-06-03 05:55:58 +0000408 DEBUG((*I)->dump());
Owen Anderson5fba6c12007-05-29 21:53:49 +0000409 }
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000410 DOUT << "}\n\n";
Owen Anderson5fba6c12007-05-29 21:53:49 +0000411}
412
Owen Andersonbe802402007-06-08 01:03:01 +0000413void GVNPRE::CalculateAvailOut(DomTreeNode* DI,
Owen Anderson0b68cda2007-06-03 05:55:58 +0000414 std::set<Value*, ExprLT>& currExps,
Owen Anderson5fba6c12007-05-29 21:53:49 +0000415 std::set<PHINode*>& currPhis,
Owen Anderson0eca9aa2007-06-03 22:02:14 +0000416 std::set<Value*>& currTemps,
Owen Anderson0b68cda2007-06-03 05:55:58 +0000417 std::set<Value*, ExprLT>& currAvail,
418 std::map<BasicBlock*, std::set<Value*, ExprLT> > availOut) {
Owen Anderson5fba6c12007-05-29 21:53:49 +0000419
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 Andersonbe802402007-06-08 01:03:01 +0000433 if (add(p, nextValueNumber))
434 nextValueNumber++;
Owen Anderson5fba6c12007-05-29 21:53:49 +0000435 currPhis.insert(p);
436
437 // Handle binary ops...
438 } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(BI)) {
Owen Anderson0b68cda2007-06-03 05:55:58 +0000439 Value* leftValue = BO->getOperand(0);
440 Value* rightValue = BO->getOperand(1);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000441
Owen Andersonbe802402007-06-08 01:03:01 +0000442 if (add(BO, nextValueNumber))
443 nextValueNumber++;
Owen Anderson5fba6c12007-05-29 21:53:49 +0000444
Owen Anderson3df52992007-06-04 23:28:33 +0000445 if (isa<Instruction>(leftValue))
446 currExps.insert(leftValue);
447 if (isa<Instruction>(rightValue))
448 currExps.insert(rightValue);
Owen Anderson0b68cda2007-06-03 05:55:58 +0000449 currExps.insert(BO);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000450
Owen Anderson223718c2007-06-09 18:35:31 +0000451 // 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 Anderson5fba6c12007-05-29 21:53:49 +0000465 // Handle unsupported ops
Owen Anderson0b68cda2007-06-03 05:55:58 +0000466 } else if (!BI->isTerminator()){
Owen Andersonbe802402007-06-08 01:03:01 +0000467 if (add(BI, nextValueNumber))
468 nextValueNumber++;
Owen Anderson0b68cda2007-06-03 05:55:58 +0000469 currTemps.insert(BI);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000470 }
Owen Anderson0b68cda2007-06-03 05:55:58 +0000471
472 if (!BI->isTerminator())
473 currAvail.insert(BI);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000474 }
475}
476
477bool GVNPRE::runOnFunction(Function &F) {
Owen Andersonbe802402007-06-08 01:03:01 +0000478 VN.clear();
479 MS.clear();
480 createdExpressions.clear();
Owen Anderson5fba6c12007-05-29 21:53:49 +0000481
Owen Anderson0b68cda2007-06-03 05:55:58 +0000482 std::map<BasicBlock*, std::set<Value*, ExprLT> > generatedExpressions;
Owen Anderson5fba6c12007-05-29 21:53:49 +0000483 std::map<BasicBlock*, std::set<PHINode*> > generatedPhis;
Owen Anderson0eca9aa2007-06-03 22:02:14 +0000484 std::map<BasicBlock*, std::set<Value*> > generatedTemporaries;
Owen Anderson0b68cda2007-06-03 05:55:58 +0000485 std::map<BasicBlock*, std::set<Value*, ExprLT> > availableOut;
486 std::map<BasicBlock*, std::set<Value*, ExprLT> > anticipatedIn;
Owen Anderson5fba6c12007-05-29 21:53:49 +0000487
488 DominatorTree &DT = getAnalysis<DominatorTree>();
489
Owen Anderson634a0632007-06-06 01:27:49 +0000490 // Phase 1: BuildSets
491
492 // Phase 1, Part 1: calculate AVAIL_OUT
Owen Anderson5fba6c12007-05-29 21:53:49 +0000493
494 // Top-down walk of the dominator tree
Devang Patelbdd1aae2007-06-04 00:32:22 +0000495 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
Owen Anderson5fba6c12007-05-29 21:53:49 +0000496 E = df_end(DT.getRootNode()); DI != E; ++DI) {
497
498 // Get the sets to update for this block
Owen Anderson0b68cda2007-06-03 05:55:58 +0000499 std::set<Value*, ExprLT>& currExps = generatedExpressions[DI->getBlock()];
Owen Anderson5fba6c12007-05-29 21:53:49 +0000500 std::set<PHINode*>& currPhis = generatedPhis[DI->getBlock()];
Owen Anderson0eca9aa2007-06-03 22:02:14 +0000501 std::set<Value*>& currTemps = generatedTemporaries[DI->getBlock()];
Owen Anderson0b68cda2007-06-03 05:55:58 +0000502 std::set<Value*, ExprLT>& currAvail = availableOut[DI->getBlock()];
Owen Anderson5fba6c12007-05-29 21:53:49 +0000503
Owen Andersonbe802402007-06-08 01:03:01 +0000504 CalculateAvailOut(*DI, currExps, currPhis,
Owen Anderson5fba6c12007-05-29 21:53:49 +0000505 currTemps, currAvail, availableOut);
506 }
507
Owen Anderson9b89e4b2007-06-05 17:31:23 +0000508 DOUT << "Maximal Set: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000509 dump_unique(MS);
Owen Anderson9b89e4b2007-06-05 17:31:23 +0000510 DOUT << "\n";
511
Owen Anderson5fba6c12007-05-29 21:53:49 +0000512 PostDominatorTree &PDT = getAnalysis<PostDominatorTree>();
513
Owen Anderson634a0632007-06-06 01:27:49 +0000514 // Phase 1, Part 2: calculate ANTIC_IN
Owen Anderson5fba6c12007-05-29 21:53:49 +0000515
Owen Anderson0c423072007-05-29 23:26:30 +0000516 std::set<BasicBlock*> visited;
517
Owen Anderson5fba6c12007-05-29 21:53:49 +0000518 bool changed = true;
519 unsigned iterations = 0;
520 while (changed) {
521 changed = false;
Owen Anderson0b68cda2007-06-03 05:55:58 +0000522 std::set<Value*, ExprLT> anticOut;
Owen Anderson5fba6c12007-05-29 21:53:49 +0000523
524 // Top-down walk of the postdominator tree
Devang Patelbdd1aae2007-06-04 00:32:22 +0000525 for (df_iterator<DomTreeNode*> PDI =
Owen Andersonbe802402007-06-08 01:03:01 +0000526 df_begin(PDT.getRootNode()), E = df_end(PDT.getRootNode());
Owen Anderson5fba6c12007-05-29 21:53:49 +0000527 PDI != E; ++PDI) {
528 BasicBlock* BB = PDI->getBlock();
Owen Andersond184c182007-06-11 16:25:17 +0000529 if (BB == 0)
530 continue;
531
Owen Anderson3df52992007-06-04 23:28:33 +0000532 DOUT << "Block: " << BB->getName() << "\n";
533 DOUT << "TMP_GEN: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000534 dump(generatedTemporaries[BB]);
Owen Anderson3df52992007-06-04 23:28:33 +0000535 DOUT << "\n";
536
537 DOUT << "EXP_GEN: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000538 dump_unique(generatedExpressions[BB]);
Owen Anderson0c423072007-05-29 23:26:30 +0000539 visited.insert(BB);
540
Owen Anderson0b68cda2007-06-03 05:55:58 +0000541 std::set<Value*, ExprLT>& anticIn = anticipatedIn[BB];
542 std::set<Value*, ExprLT> old (anticIn.begin(), anticIn.end());
Owen Anderson5fba6c12007-05-29 21:53:49 +0000543
544 if (BB->getTerminator()->getNumSuccessors() == 1) {
Owen Anderson9b89e4b2007-06-05 17:31:23 +0000545 if (visited.find(BB->getTerminator()->getSuccessor(0)) ==
546 visited.end())
Owen Andersonbe802402007-06-08 01:03:01 +0000547 phi_translate_set(MS, BB, anticOut);
Owen Anderson81d156e2007-05-31 00:42:15 +0000548 else
Owen Andersonbe802402007-06-08 01:03:01 +0000549 phi_translate_set(
Owen Anderson9b89e4b2007-06-05 17:31:23 +0000550 anticipatedIn[BB->getTerminator()->getSuccessor(0)], BB, anticOut);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000551 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
Owen Anderson3df52992007-06-04 23:28:33 +0000552 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 Anderson5fba6c12007-05-29 21:53:49 +0000556 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
Owen Anderson3df52992007-06-04 23:28:33 +0000557 std::set<Value*, ExprLT>& succAnticIn = anticipatedIn[currSucc];
558
Owen Anderson0b68cda2007-06-03 05:55:58 +0000559 std::set<Value*, ExprLT> temp;
Owen Anderson3df52992007-06-04 23:28:33 +0000560 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 Anderson5fba6c12007-05-29 21:53:49 +0000568 }
569 }
570
Owen Anderson3df52992007-06-04 23:28:33 +0000571 DOUT << "ANTIC_OUT: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000572 dump_unique(anticOut);
Owen Anderson3df52992007-06-04 23:28:33 +0000573 DOUT << "\n";
574
Owen Anderson0b68cda2007-06-03 05:55:58 +0000575 std::set<Value*, ExprLT> S;
576 std::insert_iterator<std::set<Value*, ExprLT> > s_ins(S, S.begin());
Owen Anderson5fba6c12007-05-29 21:53:49 +0000577 std::set_union(anticOut.begin(), anticOut.end(),
578 generatedExpressions[BB].begin(),
579 generatedExpressions[BB].end(),
Owen Anderson0b68cda2007-06-03 05:55:58 +0000580 s_ins, ExprLT());
Owen Anderson5fba6c12007-05-29 21:53:49 +0000581
582 anticIn.clear();
Owen Anderson3c9d8ee2007-06-04 23:34:56 +0000583
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 Anderson5fba6c12007-05-29 21:53:49 +0000589
Owen Andersonbe802402007-06-08 01:03:01 +0000590 clean(anticIn);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000591
Owen Anderson3df52992007-06-04 23:28:33 +0000592 DOUT << "ANTIC_IN: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000593 dump_unique(anticIn);
Owen Anderson3df52992007-06-04 23:28:33 +0000594 DOUT << "\n";
595
Owen Andersonddbe4302007-06-05 23:46:12 +0000596 if (old.size() != anticIn.size())
Owen Anderson5fba6c12007-05-29 21:53:49 +0000597 changed = true;
598
599 anticOut.clear();
600 }
Owen Anderson38b6b222007-06-04 18:05:26 +0000601
Owen Anderson5fba6c12007-05-29 21:53:49 +0000602 iterations++;
603 }
604
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000605 DOUT << "Iterations: " << iterations << "\n";
Owen Anderson5fba6c12007-05-29 21:53:49 +0000606
607 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000608 DOUT << "Name: " << I->getName().c_str() << "\n";
609
610 DOUT << "TMP_GEN: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000611 dump(generatedTemporaries[I]);
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000612 DOUT << "\n";
613
614 DOUT << "EXP_GEN: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000615 dump_unique(generatedExpressions[I]);
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000616 DOUT << "\n";
617
618 DOUT << "ANTIC_IN: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000619 dump_unique(anticipatedIn[I]);
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000620 DOUT << "\n";
Owen Anderson0b68cda2007-06-03 05:55:58 +0000621
622 DOUT << "AVAIL_OUT: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000623 dump_unique(availableOut[I]);
Owen Anderson0b68cda2007-06-03 05:55:58 +0000624 DOUT << "\n";
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000625 }
Owen Anderson5fba6c12007-05-29 21:53:49 +0000626
Owen Anderson634a0632007-06-06 01:27:49 +0000627
628 // Phase 2: Insert
Owen Andersonbe802402007-06-08 01:03:01 +0000629 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 Andersond184c182007-06-11 16:25:17 +0000641 if (BB == 0)
642 continue;
643
Owen Andersonbe802402007-06-08 01:03:01 +0000644 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 Anderson55994f22007-06-08 20:44:02 +0000648 new_set.clear();
649
Owen Andersonbe802402007-06-08 01:03:01 +0000650 // 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 Anderson55994f22007-06-08 20:44:02 +0000657 Value* val = find_leader(availOut, *I);
658 while (val != 0) {
Owen Anderson2e5efc32007-06-08 01:52:45 +0000659 availOut.erase(val);
Owen Anderson55994f22007-06-08 20:44:02 +0000660 val = find_leader(availOut, *I);
661 }
Owen Anderson2e5efc32007-06-08 01:52:45 +0000662 availOut.insert(*I);
Owen Andersonbe802402007-06-08 01:03:01 +0000663 }
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 Anderson223718c2007-06-09 18:35:31 +0000680 if (isa<BinaryOperator>(e) || isa<CmpInst>(e)) {
Owen Andersonbe802402007-06-08 01:03:01 +0000681 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 Anderson223718c2007-06-09 18:35:31 +0000719 User* U = cast<User>(e2);
Owen Andersonbe802402007-06-08 01:03:01 +0000720
721 Value* s1 = 0;
Owen Anderson223718c2007-06-09 18:35:31 +0000722 if (isa<Instruction>(U->getOperand(0)))
723 s1 = find_leader(availableOut[*PI], U->getOperand(0));
Owen Andersonbe802402007-06-08 01:03:01 +0000724 else
Owen Anderson223718c2007-06-09 18:35:31 +0000725 s1 = U->getOperand(0);
Owen Andersonbe802402007-06-08 01:03:01 +0000726
727 Value* s2 = 0;
Owen Anderson223718c2007-06-09 18:35:31 +0000728 if (isa<Instruction>(U->getOperand(1)))
729 s2 = find_leader(availableOut[*PI], U->getOperand(1));
Owen Andersonbe802402007-06-08 01:03:01 +0000730 else
Owen Anderson223718c2007-06-09 18:35:31 +0000731 s2 = U->getOperand(1);
Owen Andersonbe802402007-06-08 01:03:01 +0000732
Owen Anderson223718c2007-06-09 18:35:31 +0000733 Value* newVal = 0;
734 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
735 newVal = BinaryOperator::create(BO->getOpcode(),
Owen Andersonbe802402007-06-08 01:03:01 +0000736 s1, s2,
737 BO->getName()+".gvnpre",
738 (*PI)->getTerminator());
Owen Anderson223718c2007-06-09 18:35:31 +0000739 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 Anderson55994f22007-06-08 20:44:02 +0000747
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 Andersonbe802402007-06-08 01:03:01 +0000755
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 Anderson7d76b2a2007-06-08 22:02:36 +0000762
763 ++NumInsertedVals;
Owen Andersonbe802402007-06-08 01:03:01 +0000764 }
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 Anderson55994f22007-06-08 20:44:02 +0000781 Value* val = find_leader(availOut, p);
782 while (val != 0) {
783 availOut.erase(val);
784 val = find_leader(availOut, p);
785 }
Owen Andersonbe802402007-06-08 01:03:01 +0000786 availOut.insert(p);
Owen Anderson55994f22007-06-08 20:44:02 +0000787
Owen Andersonbe802402007-06-08 01:03:01 +0000788 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 Anderson7d76b2a2007-06-08 22:02:36 +0000801
802 ++NumInsertedPhis;
Owen Andersonbe802402007-06-08 01:03:01 +0000803 }
804 }
805 }
806 }
807 }
808 i_iterations++;
809 }
Owen Anderson634a0632007-06-06 01:27:49 +0000810
811 // Phase 3: Eliminate
Owen Anderson55994f22007-06-08 20:44:02 +0000812 DOUT << "\n\nPhase 3: Elimination\n\n";
813
814 std::vector<std::pair<Instruction*, Value*> > replace;
815 std::vector<Instruction*> erase;
816
Owen Anderson634a0632007-06-06 01:27:49 +0000817 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 Anderson55994f22007-06-08 20:44:02 +0000821 DOUT << "Block: " << BB->getName() << "\n";
822 dump_unique(availableOut[BB]);
823 DOUT << "\n\n";
Owen Anderson634a0632007-06-06 01:27:49 +0000824
825 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
826 BI != BE; ++BI) {
Owen Anderson55994f22007-06-08 20:44:02 +0000827
Owen Anderson223718c2007-06-09 18:35:31 +0000828 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI)) {
Owen Anderson55994f22007-06-08 20:44:02 +0000829 Value *leader = find_leader(availableOut[BB], BI);
830
Owen Andersonbe802402007-06-08 01:03:01 +0000831 if (leader != 0)
832 if (Instruction* Instr = dyn_cast<Instruction>(leader))
833 if (Instr->getParent() != 0 && Instr != BI) {
Owen Anderson55994f22007-06-08 20:44:02 +0000834 replace.push_back(std::make_pair(BI, leader));
Owen Andersonbe802402007-06-08 01:03:01 +0000835 erase.push_back(BI);
Owen Anderson7d76b2a2007-06-08 22:02:36 +0000836 ++NumEliminated;
Owen Andersonbe802402007-06-08 01:03:01 +0000837 }
838 }
Owen Anderson634a0632007-06-06 01:27:49 +0000839 }
Owen Anderson634a0632007-06-06 01:27:49 +0000840 }
841
Owen Anderson55994f22007-06-08 20:44:02 +0000842 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 Andersonbe802402007-06-08 01:03:01 +0000853 // 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 Anderson5fba6c12007-05-29 21:53:49 +0000859 return false;
860}