blob: 61bc3673cf56eca77dc1735698077b344b187b27 [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 Andersonb56fba02007-06-19 03:31:41 +000040//===----------------------------------------------------------------------===//
41// ValueTable Class
42//===----------------------------------------------------------------------===//
43
44/// This class holds the mapping between values and value numbers.
45
46namespace {
47 class VISIBILITY_HIDDEN ValueTable {
48 public:
49 struct Expression {
50 enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
51 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
52 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
53 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
54 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
55 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
56 FCMPULT, FCMPULE, FCMPUNE };
57
58 ExpressionOpcode opcode;
59 uint32_t leftVN;
60 uint32_t rightVN;
61
62 bool operator< (const Expression& other) const {
63 if (opcode < other.opcode)
64 return true;
65 else if (opcode > other.opcode)
66 return false;
67 else if (leftVN < other.leftVN)
68 return true;
69 else if (leftVN > other.leftVN)
70 return false;
71 else if (rightVN < other.rightVN)
72 return true;
73 else if (rightVN > other.rightVN)
74 return false;
75 else
76 return false;
Owen Andersona75dd4d2007-06-12 00:50:47 +000077 }
Owen Andersonb56fba02007-06-19 03:31:41 +000078 };
79
80 private:
81 std::map<Value*, uint32_t> valueNumbering;
82 std::map<Expression, uint32_t> expressionNumbering;
83
84 std::set<Expression> maximalExpressions;
85 std::set<Value*> maximalValues;
86
87 uint32_t nextValueNumber;
88
89 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
90 Expression::ExpressionOpcode getOpcode(CmpInst* C);
91 public:
92 ValueTable() { nextValueNumber = 1; }
93 uint32_t lookup_or_add(Value* V);
94 uint32_t lookup(Value* V);
95 void add(Value* V, uint32_t num);
96 void clear();
97 std::set<Expression>& getMaximalExpressions() {
98 return maximalExpressions;
99
100 }
101 std::set<Value*>& getMaximalValues() { return maximalValues; }
102 Expression create_expression(BinaryOperator* BO);
103 Expression create_expression(CmpInst* C);
Owen Anderson91c54952007-06-19 05:37:32 +0000104 void erase(Value* v);
Owen Andersonb56fba02007-06-19 03:31:41 +0000105 };
106}
107
108ValueTable::Expression::ExpressionOpcode
109 ValueTable::getOpcode(BinaryOperator* BO) {
110 switch(BO->getOpcode()) {
111 case Instruction::Add:
112 return Expression::ADD;
113 case Instruction::Sub:
114 return Expression::SUB;
115 case Instruction::Mul:
116 return Expression::MUL;
117 case Instruction::UDiv:
118 return Expression::UDIV;
119 case Instruction::SDiv:
120 return Expression::SDIV;
121 case Instruction::FDiv:
122 return Expression::FDIV;
123 case Instruction::URem:
124 return Expression::UREM;
125 case Instruction::SRem:
126 return Expression::SREM;
127 case Instruction::FRem:
128 return Expression::FREM;
129 case Instruction::Shl:
130 return Expression::SHL;
131 case Instruction::LShr:
132 return Expression::LSHR;
133 case Instruction::AShr:
134 return Expression::ASHR;
135 case Instruction::And:
136 return Expression::AND;
137 case Instruction::Or:
138 return Expression::OR;
139 case Instruction::Xor:
140 return Expression::XOR;
141
142 // THIS SHOULD NEVER HAPPEN
143 default:
144 assert(0 && "Binary operator with unknown opcode?");
145 return Expression::ADD;
146 }
147}
148
149ValueTable::Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
150 if (C->getOpcode() == Instruction::ICmp) {
151 switch (C->getPredicate()) {
152 case ICmpInst::ICMP_EQ:
153 return Expression::ICMPEQ;
154 case ICmpInst::ICMP_NE:
155 return Expression::ICMPNE;
156 case ICmpInst::ICMP_UGT:
157 return Expression::ICMPUGT;
158 case ICmpInst::ICMP_UGE:
159 return Expression::ICMPUGE;
160 case ICmpInst::ICMP_ULT:
161 return Expression::ICMPULT;
162 case ICmpInst::ICMP_ULE:
163 return Expression::ICMPULE;
164 case ICmpInst::ICMP_SGT:
165 return Expression::ICMPSGT;
166 case ICmpInst::ICMP_SGE:
167 return Expression::ICMPSGE;
168 case ICmpInst::ICMP_SLT:
169 return Expression::ICMPSLT;
170 case ICmpInst::ICMP_SLE:
171 return Expression::ICMPSLE;
172
173 // THIS SHOULD NEVER HAPPEN
174 default:
175 assert(0 && "Comparison with unknown predicate?");
176 return Expression::ICMPEQ;
177 }
178 } else {
179 switch (C->getPredicate()) {
180 case FCmpInst::FCMP_OEQ:
181 return Expression::FCMPOEQ;
182 case FCmpInst::FCMP_OGT:
183 return Expression::FCMPOGT;
184 case FCmpInst::FCMP_OGE:
185 return Expression::FCMPOGE;
186 case FCmpInst::FCMP_OLT:
187 return Expression::FCMPOLT;
188 case FCmpInst::FCMP_OLE:
189 return Expression::FCMPOLE;
190 case FCmpInst::FCMP_ONE:
191 return Expression::FCMPONE;
192 case FCmpInst::FCMP_ORD:
193 return Expression::FCMPORD;
194 case FCmpInst::FCMP_UNO:
195 return Expression::FCMPUNO;
196 case FCmpInst::FCMP_UEQ:
197 return Expression::FCMPUEQ;
198 case FCmpInst::FCMP_UGT:
199 return Expression::FCMPUGT;
200 case FCmpInst::FCMP_UGE:
201 return Expression::FCMPUGE;
202 case FCmpInst::FCMP_ULT:
203 return Expression::FCMPULT;
204 case FCmpInst::FCMP_ULE:
205 return Expression::FCMPULE;
206 case FCmpInst::FCMP_UNE:
207 return Expression::FCMPUNE;
208
209 // THIS SHOULD NEVER HAPPEN
210 default:
211 assert(0 && "Comparison with unknown predicate?");
212 return Expression::FCMPOEQ;
Owen Anderson223718c2007-06-09 18:35:31 +0000213 }
214 }
Owen Andersonb56fba02007-06-19 03:31:41 +0000215}
216
217uint32_t ValueTable::lookup_or_add(Value* V) {
218 maximalValues.insert(V);
219
220 std::map<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
221 if (VI != valueNumbering.end())
222 return VI->second;
Owen Anderson223718c2007-06-09 18:35:31 +0000223
Owen Anderson223718c2007-06-09 18:35:31 +0000224
Owen Andersonb56fba02007-06-19 03:31:41 +0000225 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
226 Expression e = create_expression(BO);
227
228 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
229 if (EI != expressionNumbering.end()) {
230 valueNumbering.insert(std::make_pair(V, EI->second));
231 return EI->second;
232 } else {
233 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
234 valueNumbering.insert(std::make_pair(V, nextValueNumber));
235
236 return nextValueNumber++;
237 }
238 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
239 Expression e = create_expression(C);
240
241 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
242 if (EI != expressionNumbering.end()) {
243 valueNumbering.insert(std::make_pair(V, EI->second));
244 return EI->second;
245 } else {
246 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
247 valueNumbering.insert(std::make_pair(V, nextValueNumber));
248
249 return nextValueNumber++;
250 }
251 } else {
252 valueNumbering.insert(std::make_pair(V, nextValueNumber));
253 return nextValueNumber++;
Owen Anderson0b68cda2007-06-03 05:55:58 +0000254 }
Owen Andersonb56fba02007-06-19 03:31:41 +0000255}
256
257uint32_t ValueTable::lookup(Value* V) {
258 std::map<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
259 if (VI != valueNumbering.end())
260 return VI->second;
261 else
262 assert(0 && "Value not numbered?");
263
264 return 0;
265}
266
267void ValueTable::add(Value* V, uint32_t num) {
268 std::map<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
269 if (VI != valueNumbering.end())
270 valueNumbering.erase(VI);
271 valueNumbering.insert(std::make_pair(V, num));
272}
273
274ValueTable::Expression ValueTable::create_expression(BinaryOperator* BO) {
275 Expression e;
276
277 e.leftVN = lookup_or_add(BO->getOperand(0));
278 e.rightVN = lookup_or_add(BO->getOperand(1));
279 e.opcode = getOpcode(BO);
280
281 maximalExpressions.insert(e);
282
283 return e;
284}
285
286ValueTable::Expression ValueTable::create_expression(CmpInst* C) {
287 Expression e;
288
289 e.leftVN = lookup_or_add(C->getOperand(0));
290 e.rightVN = lookup_or_add(C->getOperand(1));
291 e.opcode = getOpcode(C);
292
293 maximalExpressions.insert(e);
294
295 return e;
296}
297
298void ValueTable::clear() {
299 valueNumbering.clear();
300 expressionNumbering.clear();
Owen Andersonb9cbaed2007-06-19 04:32:55 +0000301 maximalExpressions.clear();
302 maximalValues.clear();
Owen Andersonb56fba02007-06-19 03:31:41 +0000303 nextValueNumber = 1;
304}
Owen Anderson0b68cda2007-06-03 05:55:58 +0000305
Owen Anderson91c54952007-06-19 05:37:32 +0000306void ValueTable::erase(Value* V) {
307 maximalValues.erase(V);
308 valueNumbering.erase(V);
309 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V))
310 maximalExpressions.erase(create_expression(BO));
311 else if (CmpInst* C = dyn_cast<CmpInst>(V))
312 maximalExpressions.erase(create_expression(C));
313}
314
Owen Anderson5fba6c12007-05-29 21:53:49 +0000315namespace {
316
317 class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
318 bool runOnFunction(Function &F);
319 public:
320 static char ID; // Pass identification, replacement for typeid
Owen Andersonb9cbaed2007-06-19 04:32:55 +0000321 GVNPRE() : FunctionPass((intptr_t)&ID) { }
Owen Anderson5fba6c12007-05-29 21:53:49 +0000322
323 private:
Owen Andersonbe802402007-06-08 01:03:01 +0000324 ValueTable VN;
Owen Andersona75dd4d2007-06-12 00:50:47 +0000325 std::vector<Instruction*> createdExpressions;
Owen Anderson81d156e2007-05-31 00:42:15 +0000326
Owen Andersonb56fba02007-06-19 03:31:41 +0000327 std::map<BasicBlock*, std::set<Value*> > availableOut;
328 std::map<BasicBlock*, std::set<Value*> > anticipatedIn;
Owen Andersondd998e12007-06-18 04:42:29 +0000329 std::map<User*, bool> invokeDep;
Owen Anderson4036ad42007-06-12 22:43:57 +0000330
Owen Anderson5fba6c12007-05-29 21:53:49 +0000331 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
332 AU.setPreservesCFG();
333 AU.addRequired<DominatorTree>();
334 AU.addRequired<PostDominatorTree>();
335 }
336
337 // Helper fuctions
338 // FIXME: eliminate or document these better
Owen Anderson2e5efc32007-06-08 01:52:45 +0000339 void dump(const std::set<Value*>& s) const;
Owen Andersonb56fba02007-06-19 03:31:41 +0000340 void dump_unique(const std::set<Value*>& s) const;
341 void clean(std::set<Value*>& set);
342 Value* find_leader(std::set<Value*>& vals,
343 uint32_t v);
Owen Anderson4036ad42007-06-12 22:43:57 +0000344 Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ);
Owen Andersonb56fba02007-06-19 03:31:41 +0000345 void phi_translate_set(std::set<Value*>& anticIn, BasicBlock* pred,
346 BasicBlock* succ, std::set<Value*>& out);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000347
Owen Andersonb56fba02007-06-19 03:31:41 +0000348 void topo_sort(std::set<Value*>& set,
Owen Anderson0b68cda2007-06-03 05:55:58 +0000349 std::vector<Value*>& vec);
Owen Anderson331bf6a2007-05-31 22:44:11 +0000350
Owen Anderson5fba6c12007-05-29 21:53:49 +0000351 // For a given block, calculate the generated expressions, temporaries,
352 // and the AVAIL_OUT set
Owen Anderson42769842007-06-12 16:57:50 +0000353 void cleanup();
Owen Anderson4036ad42007-06-12 22:43:57 +0000354 void elimination();
Owen Andersondd998e12007-06-18 04:42:29 +0000355
Owen Andersonb56fba02007-06-19 03:31:41 +0000356 void val_insert(std::set<Value*>& s, Value* v);
357 void val_replace(std::set<Value*>& s, Value* v);
Owen Andersondd998e12007-06-18 04:42:29 +0000358 bool dependsOnInvoke(Value* V);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000359
360 };
361
362 char GVNPRE::ID = 0;
363
364}
365
366FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
367
368RegisterPass<GVNPRE> X("gvnpre",
369 "Global Value Numbering/Partial Redundancy Elimination");
370
Owen Anderson5fba6c12007-05-29 21:53:49 +0000371
Owen Anderson7d76b2a2007-06-08 22:02:36 +0000372STATISTIC(NumInsertedVals, "Number of values inserted");
373STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
374STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
375
Owen Andersonb56fba02007-06-19 03:31:41 +0000376Value* GVNPRE::find_leader(std::set<Value*>& vals, uint32_t v) {
377 for (std::set<Value*>::iterator I = vals.begin(), E = vals.end();
378 I != E; ++I)
379 if (v == VN.lookup(*I))
Owen Anderson0b68cda2007-06-03 05:55:58 +0000380 return *I;
Owen Anderson5fba6c12007-05-29 21:53:49 +0000381
Owen Anderson0b68cda2007-06-03 05:55:58 +0000382 return 0;
Owen Anderson5fba6c12007-05-29 21:53:49 +0000383}
384
Owen Andersonb56fba02007-06-19 03:31:41 +0000385void GVNPRE::val_insert(std::set<Value*>& s, Value* v) {
386 uint32_t num = VN.lookup(v);
387 Value* leader = find_leader(s, num);
388 if (leader == 0)
389 s.insert(v);
390}
391
392void GVNPRE::val_replace(std::set<Value*>& s, Value* v) {
393 uint32_t num = VN.lookup(v);
394 Value* leader = find_leader(s, num);
395 while (leader != 0) {
396 s.erase(leader);
397 leader = find_leader(s, num);
398 }
399 s.insert(v);
400}
401
Owen Anderson4036ad42007-06-12 22:43:57 +0000402Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
Owen Anderson38b6b222007-06-04 18:05:26 +0000403 if (V == 0)
404 return 0;
405
406 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
Owen Andersonb56fba02007-06-19 03:31:41 +0000407 Value* newOp1 = 0;
408 if (isa<Instruction>(BO->getOperand(0)))
409 newOp1 = phi_translate(find_leader(anticipatedIn[succ],
410 VN.lookup(BO->getOperand(0))),
411 pred, succ);
412 else
413 newOp1 = BO->getOperand(0);
414
Owen Anderson38b6b222007-06-04 18:05:26 +0000415 if (newOp1 == 0)
416 return 0;
417
Owen Andersonb56fba02007-06-19 03:31:41 +0000418 Value* newOp2 = 0;
419 if (isa<Instruction>(BO->getOperand(1)))
420 newOp2 = phi_translate(find_leader(anticipatedIn[succ],
421 VN.lookup(BO->getOperand(1))),
422 pred, succ);
423 else
424 newOp2 = BO->getOperand(1);
425
Owen Anderson38b6b222007-06-04 18:05:26 +0000426 if (newOp2 == 0)
427 return 0;
428
429 if (newOp1 != BO->getOperand(0) || newOp2 != BO->getOperand(1)) {
Owen Andersonbe802402007-06-08 01:03:01 +0000430 Instruction* newVal = BinaryOperator::create(BO->getOpcode(),
Owen Anderson38b6b222007-06-04 18:05:26 +0000431 newOp1, newOp2,
Owen Anderson91c54952007-06-19 05:37:32 +0000432 BO->getName()+".expr");
Owen Anderson55994f22007-06-08 20:44:02 +0000433
Owen Andersonb56fba02007-06-19 03:31:41 +0000434 uint32_t v = VN.lookup_or_add(newVal);
Owen Anderson4036ad42007-06-12 22:43:57 +0000435
Owen Andersonb56fba02007-06-19 03:31:41 +0000436 Value* leader = find_leader(availableOut[pred], v);
Owen Anderson4036ad42007-06-12 22:43:57 +0000437 if (leader == 0) {
Owen Andersona75dd4d2007-06-12 00:50:47 +0000438 createdExpressions.push_back(newVal);
Owen Anderson38b6b222007-06-04 18:05:26 +0000439 return newVal;
Owen Andersonc8472092007-06-05 22:11:49 +0000440 } else {
Owen Anderson91c54952007-06-19 05:37:32 +0000441 VN.erase(newVal);
Owen Andersonc8472092007-06-05 22:11:49 +0000442 delete newVal;
Owen Anderson4036ad42007-06-12 22:43:57 +0000443 return leader;
Owen Andersonc8472092007-06-05 22:11:49 +0000444 }
Owen Anderson38b6b222007-06-04 18:05:26 +0000445 }
446 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
Owen Andersona75dd4d2007-06-12 00:50:47 +0000447 if (P->getParent() == succ)
Owen Anderson38b6b222007-06-04 18:05:26 +0000448 return P->getIncomingValueForBlock(pred);
Owen Anderson223718c2007-06-09 18:35:31 +0000449 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
Owen Andersonb56fba02007-06-19 03:31:41 +0000450 Value* newOp1 = 0;
451 if (isa<Instruction>(C->getOperand(0)))
452 newOp1 = phi_translate(find_leader(anticipatedIn[succ],
453 VN.lookup(C->getOperand(0))),
454 pred, succ);
455 else
456 newOp1 = C->getOperand(0);
457
Owen Anderson223718c2007-06-09 18:35:31 +0000458 if (newOp1 == 0)
459 return 0;
460
Owen Andersonb56fba02007-06-19 03:31:41 +0000461 Value* newOp2 = 0;
462 if (isa<Instruction>(C->getOperand(1)))
463 newOp2 = phi_translate(find_leader(anticipatedIn[succ],
464 VN.lookup(C->getOperand(1))),
465 pred, succ);
466 else
467 newOp2 = C->getOperand(1);
468
Owen Anderson223718c2007-06-09 18:35:31 +0000469 if (newOp2 == 0)
470 return 0;
471
472 if (newOp1 != C->getOperand(0) || newOp2 != C->getOperand(1)) {
473 Instruction* newVal = CmpInst::create(C->getOpcode(),
474 C->getPredicate(),
475 newOp1, newOp2,
Owen Anderson91c54952007-06-19 05:37:32 +0000476 C->getName()+".expr");
Owen Anderson223718c2007-06-09 18:35:31 +0000477
Owen Andersonb56fba02007-06-19 03:31:41 +0000478 uint32_t v = VN.lookup_or_add(newVal);
Owen Anderson4036ad42007-06-12 22:43:57 +0000479
Owen Andersonb56fba02007-06-19 03:31:41 +0000480 Value* leader = find_leader(availableOut[pred], v);
Owen Anderson4036ad42007-06-12 22:43:57 +0000481 if (leader == 0) {
Owen Andersona75dd4d2007-06-12 00:50:47 +0000482 createdExpressions.push_back(newVal);
Owen Anderson223718c2007-06-09 18:35:31 +0000483 return newVal;
484 } else {
Owen Anderson91c54952007-06-19 05:37:32 +0000485 VN.erase(newVal);
Owen Anderson223718c2007-06-09 18:35:31 +0000486 delete newVal;
Owen Anderson4036ad42007-06-12 22:43:57 +0000487 return leader;
Owen Anderson223718c2007-06-09 18:35:31 +0000488 }
489 }
Owen Anderson38b6b222007-06-04 18:05:26 +0000490 }
491
492 return V;
493}
494
Owen Andersonb56fba02007-06-19 03:31:41 +0000495void GVNPRE::phi_translate_set(std::set<Value*>& anticIn,
Owen Andersona75dd4d2007-06-12 00:50:47 +0000496 BasicBlock* pred, BasicBlock* succ,
Owen Andersonb56fba02007-06-19 03:31:41 +0000497 std::set<Value*>& out) {
498 for (std::set<Value*>::iterator I = anticIn.begin(),
Owen Anderson38b6b222007-06-04 18:05:26 +0000499 E = anticIn.end(); I != E; ++I) {
Owen Anderson4036ad42007-06-12 22:43:57 +0000500 Value* V = phi_translate(*I, pred, succ);
Owen Anderson38b6b222007-06-04 18:05:26 +0000501 if (V != 0)
502 out.insert(V);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000503 }
504}
505
Owen Andersondd998e12007-06-18 04:42:29 +0000506bool GVNPRE::dependsOnInvoke(Value* V) {
Owen Anderson2320d432007-06-19 23:07:16 +0000507 if (PHINode* p = dyn_cast<PHINode>(V)) {
508 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
509 if (isa<InvokeInst>(*I))
Owen Andersondd998e12007-06-18 04:42:29 +0000510 return true;
Owen Anderson2320d432007-06-19 23:07:16 +0000511 return false;
512 } else {
513 return false;
Owen Anderson658f2c42007-06-16 00:26:54 +0000514 }
Owen Anderson658f2c42007-06-16 00:26:54 +0000515}
516
Owen Anderson5fba6c12007-05-29 21:53:49 +0000517// Remove all expressions whose operands are not themselves in the set
Owen Andersonb56fba02007-06-19 03:31:41 +0000518void GVNPRE::clean(std::set<Value*>& set) {
Owen Anderson0b68cda2007-06-03 05:55:58 +0000519 std::vector<Value*> worklist;
Owen Andersonbe802402007-06-08 01:03:01 +0000520 topo_sort(set, worklist);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000521
Owen Andersonbe802402007-06-08 01:03:01 +0000522 for (unsigned i = 0; i < worklist.size(); ++i) {
523 Value* v = worklist[i];
Owen Anderson5fba6c12007-05-29 21:53:49 +0000524
Owen Anderson0b68cda2007-06-03 05:55:58 +0000525 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(v)) {
Owen Andersonbe802402007-06-08 01:03:01 +0000526 bool lhsValid = !isa<Instruction>(BO->getOperand(0));
527 if (!lhsValid)
Owen Andersonb56fba02007-06-19 03:31:41 +0000528 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
Owen Andersonbe802402007-06-08 01:03:01 +0000529 I != E; ++I)
Owen Andersonb56fba02007-06-19 03:31:41 +0000530 if (VN.lookup(*I) == VN.lookup(BO->getOperand(0))) {
Owen Andersonbe802402007-06-08 01:03:01 +0000531 lhsValid = true;
532 break;
533 }
Owen Andersonb364b412007-06-18 04:30:44 +0000534 if (lhsValid)
535 lhsValid = !dependsOnInvoke(BO->getOperand(0));
Owen Anderson0b68cda2007-06-03 05:55:58 +0000536
Owen Andersonbe802402007-06-08 01:03:01 +0000537 bool rhsValid = !isa<Instruction>(BO->getOperand(1));
538 if (!rhsValid)
Owen Andersonb56fba02007-06-19 03:31:41 +0000539 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
Owen Andersonf1c04e12007-06-18 04:31:21 +0000540 I != E; ++I)
Owen Andersonb56fba02007-06-19 03:31:41 +0000541 if (VN.lookup(*I) == VN.lookup(BO->getOperand(1))) {
Owen Andersonf1c04e12007-06-18 04:31:21 +0000542 rhsValid = true;
543 break;
544 }
Owen Andersonb364b412007-06-18 04:30:44 +0000545 if (rhsValid)
546 rhsValid = !dependsOnInvoke(BO->getOperand(1));
Owen Anderson5fba6c12007-05-29 21:53:49 +0000547
Owen Anderson0b68cda2007-06-03 05:55:58 +0000548 if (!lhsValid || !rhsValid)
549 set.erase(BO);
Owen Anderson223718c2007-06-09 18:35:31 +0000550 } else if (CmpInst* C = dyn_cast<CmpInst>(v)) {
551 bool lhsValid = !isa<Instruction>(C->getOperand(0));
552 if (!lhsValid)
Owen Andersonb56fba02007-06-19 03:31:41 +0000553 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
Owen Anderson223718c2007-06-09 18:35:31 +0000554 I != E; ++I)
Owen Andersonb56fba02007-06-19 03:31:41 +0000555 if (VN.lookup(*I) == VN.lookup(C->getOperand(0))) {
Owen Anderson223718c2007-06-09 18:35:31 +0000556 lhsValid = true;
557 break;
558 }
Owen Anderson2320d432007-06-19 23:07:16 +0000559 if (lhsValid)
560 lhsValid = !dependsOnInvoke(C->getOperand(0));
Owen Anderson658f2c42007-06-16 00:26:54 +0000561
Owen Anderson223718c2007-06-09 18:35:31 +0000562 bool rhsValid = !isa<Instruction>(C->getOperand(1));
563 if (!rhsValid)
Owen Andersonb56fba02007-06-19 03:31:41 +0000564 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
Owen Anderson223718c2007-06-09 18:35:31 +0000565 I != E; ++I)
Owen Andersonb56fba02007-06-19 03:31:41 +0000566 if (VN.lookup(*I) == VN.lookup(C->getOperand(1))) {
Owen Anderson223718c2007-06-09 18:35:31 +0000567 rhsValid = true;
568 break;
569 }
Owen Anderson2320d432007-06-19 23:07:16 +0000570 if (rhsValid)
571 rhsValid = !dependsOnInvoke(C->getOperand(1));
Owen Anderson223718c2007-06-09 18:35:31 +0000572
573 if (!lhsValid || !rhsValid)
574 set.erase(C);
Owen Anderson0b68cda2007-06-03 05:55:58 +0000575 }
Owen Anderson5fba6c12007-05-29 21:53:49 +0000576 }
577}
578
Owen Andersonb56fba02007-06-19 03:31:41 +0000579void GVNPRE::topo_sort(std::set<Value*>& set,
Owen Anderson0b68cda2007-06-03 05:55:58 +0000580 std::vector<Value*>& vec) {
Owen Andersonb56fba02007-06-19 03:31:41 +0000581 std::set<Value*> toErase;
582 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
Owen Anderson331bf6a2007-05-31 22:44:11 +0000583 I != E; ++I) {
Owen Anderson0b68cda2007-06-03 05:55:58 +0000584 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(*I))
Owen Andersonb56fba02007-06-19 03:31:41 +0000585 for (std::set<Value*>::iterator SI = set.begin(); SI != E; ++SI) {
586 if (VN.lookup(BO->getOperand(0)) == VN.lookup(*SI) ||
587 VN.lookup(BO->getOperand(1)) == VN.lookup(*SI)) {
Owen Andersonbe802402007-06-08 01:03:01 +0000588 toErase.insert(*SI);
Owen Anderson0b68cda2007-06-03 05:55:58 +0000589 }
Owen Anderson223718c2007-06-09 18:35:31 +0000590 }
591 else if (CmpInst* C = dyn_cast<CmpInst>(*I))
Owen Andersonb56fba02007-06-19 03:31:41 +0000592 for (std::set<Value*>::iterator SI = set.begin(); SI != E; ++SI) {
593 if (VN.lookup(C->getOperand(0)) == VN.lookup(*SI) ||
594 VN.lookup(C->getOperand(1)) == VN.lookup(*SI)) {
Owen Anderson223718c2007-06-09 18:35:31 +0000595 toErase.insert(*SI);
596 }
597 }
Owen Anderson331bf6a2007-05-31 22:44:11 +0000598 }
599
Owen Anderson0b68cda2007-06-03 05:55:58 +0000600 std::vector<Value*> Q;
Owen Andersonb56fba02007-06-19 03:31:41 +0000601 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
Owen Andersonbe802402007-06-08 01:03:01 +0000602 I != E; ++I) {
603 if (toErase.find(*I) == toErase.end())
604 Q.push_back(*I);
605 }
Owen Anderson331bf6a2007-05-31 22:44:11 +0000606
Owen Andersonddbe4302007-06-05 23:46:12 +0000607 std::set<Value*> visited;
Owen Anderson331bf6a2007-05-31 22:44:11 +0000608 while (!Q.empty()) {
Owen Anderson0b68cda2007-06-03 05:55:58 +0000609 Value* e = Q.back();
610
611 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(e)) {
Owen Andersonb56fba02007-06-19 03:31:41 +0000612 Value* l = find_leader(set, VN.lookup(BO->getOperand(0)));
613 Value* r = find_leader(set, VN.lookup(BO->getOperand(1)));
Owen Anderson0b68cda2007-06-03 05:55:58 +0000614
Owen Andersonddbe4302007-06-05 23:46:12 +0000615 if (l != 0 && isa<Instruction>(l) &&
616 visited.find(l) == visited.end())
Owen Anderson0b68cda2007-06-03 05:55:58 +0000617 Q.push_back(l);
Owen Andersonddbe4302007-06-05 23:46:12 +0000618 else if (r != 0 && isa<Instruction>(r) &&
619 visited.find(r) == visited.end())
Owen Anderson0b68cda2007-06-03 05:55:58 +0000620 Q.push_back(r);
621 else {
622 vec.push_back(e);
623 visited.insert(e);
624 Q.pop_back();
625 }
Owen Anderson223718c2007-06-09 18:35:31 +0000626 } else if (CmpInst* C = dyn_cast<CmpInst>(e)) {
Owen Andersonb56fba02007-06-19 03:31:41 +0000627 Value* l = find_leader(set, VN.lookup(C->getOperand(0)));
628 Value* r = find_leader(set, VN.lookup(C->getOperand(1)));
Owen Anderson223718c2007-06-09 18:35:31 +0000629
630 if (l != 0 && isa<Instruction>(l) &&
631 visited.find(l) == visited.end())
632 Q.push_back(l);
633 else if (r != 0 && isa<Instruction>(r) &&
634 visited.find(r) == visited.end())
635 Q.push_back(r);
636 else {
637 vec.push_back(e);
638 visited.insert(e);
639 Q.pop_back();
640 }
Owen Anderson0b68cda2007-06-03 05:55:58 +0000641 } else {
Owen Anderson331bf6a2007-05-31 22:44:11 +0000642 visited.insert(e);
643 vec.push_back(e);
644 Q.pop_back();
Owen Anderson331bf6a2007-05-31 22:44:11 +0000645 }
646 }
647}
648
Owen Anderson0eca9aa2007-06-03 22:02:14 +0000649
Owen Anderson2e5efc32007-06-08 01:52:45 +0000650void GVNPRE::dump(const std::set<Value*>& s) const {
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000651 DOUT << "{ ";
Owen Anderson0eca9aa2007-06-03 22:02:14 +0000652 for (std::set<Value*>::iterator I = s.begin(), E = s.end();
653 I != E; ++I) {
654 DEBUG((*I)->dump());
655 }
656 DOUT << "}\n\n";
657}
658
Owen Andersonb56fba02007-06-19 03:31:41 +0000659void GVNPRE::dump_unique(const std::set<Value*>& s) const {
Owen Anderson0eca9aa2007-06-03 22:02:14 +0000660 DOUT << "{ ";
661 for (std::set<Value*>::iterator I = s.begin(), E = s.end();
Owen Anderson331bf6a2007-05-31 22:44:11 +0000662 I != E; ++I) {
Owen Anderson0b68cda2007-06-03 05:55:58 +0000663 DEBUG((*I)->dump());
Owen Anderson5fba6c12007-05-29 21:53:49 +0000664 }
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000665 DOUT << "}\n\n";
Owen Anderson5fba6c12007-05-29 21:53:49 +0000666}
667
Owen Anderson4036ad42007-06-12 22:43:57 +0000668void GVNPRE::elimination() {
Owen Anderson42769842007-06-12 16:57:50 +0000669 DOUT << "\n\nPhase 3: Elimination\n\n";
670
671 std::vector<std::pair<Instruction*, Value*> > replace;
672 std::vector<Instruction*> erase;
673
674 DominatorTree& DT = getAnalysis<DominatorTree>();
675
676 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
677 E = df_end(DT.getRootNode()); DI != E; ++DI) {
678 BasicBlock* BB = DI->getBlock();
679
680 DOUT << "Block: " << BB->getName() << "\n";
681 dump_unique(availableOut[BB]);
682 DOUT << "\n\n";
683
684 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
685 BI != BE; ++BI) {
686
687 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI)) {
Owen Andersonb56fba02007-06-19 03:31:41 +0000688 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
Owen Anderson42769842007-06-12 16:57:50 +0000689
690 if (leader != 0)
691 if (Instruction* Instr = dyn_cast<Instruction>(leader))
692 if (Instr->getParent() != 0 && Instr != BI) {
693 replace.push_back(std::make_pair(BI, leader));
694 erase.push_back(BI);
695 ++NumEliminated;
696 }
697 }
698 }
699 }
700
701 while (!replace.empty()) {
702 std::pair<Instruction*, Value*> rep = replace.back();
703 replace.pop_back();
704 rep.first->replaceAllUsesWith(rep.second);
705 }
706
707 for (std::vector<Instruction*>::iterator I = erase.begin(), E = erase.end();
708 I != E; ++I)
709 (*I)->eraseFromParent();
710}
711
712
713void GVNPRE::cleanup() {
714 while (!createdExpressions.empty()) {
715 Instruction* I = createdExpressions.back();
716 createdExpressions.pop_back();
717
718 delete I;
719 }
720}
721
Owen Anderson5fba6c12007-05-29 21:53:49 +0000722bool GVNPRE::runOnFunction(Function &F) {
Owen Andersonbe802402007-06-08 01:03:01 +0000723 VN.clear();
Owen Andersonbe802402007-06-08 01:03:01 +0000724 createdExpressions.clear();
Owen Anderson4036ad42007-06-12 22:43:57 +0000725 availableOut.clear();
726 anticipatedIn.clear();
Owen Andersondd998e12007-06-18 04:42:29 +0000727 invokeDep.clear();
Owen Anderson5fba6c12007-05-29 21:53:49 +0000728
Owen Andersonb56fba02007-06-19 03:31:41 +0000729 std::map<BasicBlock*, std::set<Value*> > generatedExpressions;
Owen Anderson5fba6c12007-05-29 21:53:49 +0000730 std::map<BasicBlock*, std::set<PHINode*> > generatedPhis;
Owen Anderson0eca9aa2007-06-03 22:02:14 +0000731 std::map<BasicBlock*, std::set<Value*> > generatedTemporaries;
Owen Anderson4036ad42007-06-12 22:43:57 +0000732
Owen Anderson5fba6c12007-05-29 21:53:49 +0000733
734 DominatorTree &DT = getAnalysis<DominatorTree>();
735
Owen Anderson634a0632007-06-06 01:27:49 +0000736 // Phase 1: BuildSets
737
738 // Phase 1, Part 1: calculate AVAIL_OUT
Owen Anderson5fba6c12007-05-29 21:53:49 +0000739
740 // Top-down walk of the dominator tree
Devang Patelbdd1aae2007-06-04 00:32:22 +0000741 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
Owen Anderson5fba6c12007-05-29 21:53:49 +0000742 E = df_end(DT.getRootNode()); DI != E; ++DI) {
743
744 // Get the sets to update for this block
Owen Andersonb56fba02007-06-19 03:31:41 +0000745 std::set<Value*>& currExps = generatedExpressions[DI->getBlock()];
Owen Anderson5fba6c12007-05-29 21:53:49 +0000746 std::set<PHINode*>& currPhis = generatedPhis[DI->getBlock()];
Owen Anderson0eca9aa2007-06-03 22:02:14 +0000747 std::set<Value*>& currTemps = generatedTemporaries[DI->getBlock()];
Owen Andersonb56fba02007-06-19 03:31:41 +0000748 std::set<Value*>& currAvail = availableOut[DI->getBlock()];
Owen Anderson5fba6c12007-05-29 21:53:49 +0000749
Owen Andersonb56fba02007-06-19 03:31:41 +0000750 BasicBlock* BB = DI->getBlock();
751
752 // A block inherits AVAIL_OUT from its dominator
753 if (DI->getIDom() != 0)
754 currAvail.insert(availableOut[DI->getIDom()->getBlock()].begin(),
755 availableOut[DI->getIDom()->getBlock()].end());
756
757
758 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
759 BI != BE; ++BI) {
760
761 // Handle PHI nodes...
762 if (PHINode* p = dyn_cast<PHINode>(BI)) {
763 VN.lookup_or_add(p);
764 currPhis.insert(p);
765
766 // Handle binary ops...
767 } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(BI)) {
768 Value* leftValue = BO->getOperand(0);
769 Value* rightValue = BO->getOperand(1);
770
771 VN.lookup_or_add(BO);
772
773 if (isa<Instruction>(leftValue))
774 val_insert(currExps, leftValue);
775 if (isa<Instruction>(rightValue))
776 val_insert(currExps, rightValue);
777 val_insert(currExps, BO);
778
779 // Handle cmp ops...
780 } else if (CmpInst* C = dyn_cast<CmpInst>(BI)) {
781 Value* leftValue = C->getOperand(0);
782 Value* rightValue = C->getOperand(1);
783
784 VN.lookup_or_add(C);
785
786 if (isa<Instruction>(leftValue))
787 val_insert(currExps, leftValue);
788 if (isa<Instruction>(rightValue))
789 val_insert(currExps, rightValue);
790 val_insert(currExps, C);
791
792 // Handle unsupported ops
793 } else if (!BI->isTerminator()){
794 VN.lookup_or_add(BI);
795 currTemps.insert(BI);
796 }
797
798 if (!BI->isTerminator())
799 val_insert(currAvail, BI);
800 }
Owen Anderson5fba6c12007-05-29 21:53:49 +0000801 }
802
Owen Anderson9b89e4b2007-06-05 17:31:23 +0000803 DOUT << "Maximal Set: ";
Owen Andersonb56fba02007-06-19 03:31:41 +0000804 dump_unique(VN.getMaximalValues());
Owen Anderson9b89e4b2007-06-05 17:31:23 +0000805 DOUT << "\n";
806
Owen Anderson42769842007-06-12 16:57:50 +0000807 // If function has no exit blocks, only perform GVN
Owen Anderson5fba6c12007-05-29 21:53:49 +0000808 PostDominatorTree &PDT = getAnalysis<PostDominatorTree>();
Owen Anderson42769842007-06-12 16:57:50 +0000809 if (PDT[&F.getEntryBlock()] == 0) {
Owen Anderson4036ad42007-06-12 22:43:57 +0000810 elimination();
Owen Anderson42769842007-06-12 16:57:50 +0000811 cleanup();
812
813 return true;
814 }
815
Owen Anderson5fba6c12007-05-29 21:53:49 +0000816
Owen Anderson634a0632007-06-06 01:27:49 +0000817 // Phase 1, Part 2: calculate ANTIC_IN
Owen Anderson5fba6c12007-05-29 21:53:49 +0000818
Owen Anderson0c423072007-05-29 23:26:30 +0000819 std::set<BasicBlock*> visited;
820
Owen Anderson5fba6c12007-05-29 21:53:49 +0000821 bool changed = true;
822 unsigned iterations = 0;
823 while (changed) {
824 changed = false;
Owen Andersonb56fba02007-06-19 03:31:41 +0000825 std::set<Value*> anticOut;
Owen Anderson5fba6c12007-05-29 21:53:49 +0000826
827 // Top-down walk of the postdominator tree
Devang Patelbdd1aae2007-06-04 00:32:22 +0000828 for (df_iterator<DomTreeNode*> PDI =
Owen Andersonbe802402007-06-08 01:03:01 +0000829 df_begin(PDT.getRootNode()), E = df_end(PDT.getRootNode());
Owen Anderson5fba6c12007-05-29 21:53:49 +0000830 PDI != E; ++PDI) {
831 BasicBlock* BB = PDI->getBlock();
Owen Andersond184c182007-06-11 16:25:17 +0000832 if (BB == 0)
833 continue;
834
Owen Anderson3df52992007-06-04 23:28:33 +0000835 DOUT << "Block: " << BB->getName() << "\n";
836 DOUT << "TMP_GEN: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000837 dump(generatedTemporaries[BB]);
Owen Anderson3df52992007-06-04 23:28:33 +0000838 DOUT << "\n";
839
840 DOUT << "EXP_GEN: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000841 dump_unique(generatedExpressions[BB]);
Owen Anderson0c423072007-05-29 23:26:30 +0000842 visited.insert(BB);
843
Owen Andersonb56fba02007-06-19 03:31:41 +0000844 std::set<Value*>& anticIn = anticipatedIn[BB];
845 std::set<Value*> old (anticIn.begin(), anticIn.end());
Owen Anderson5fba6c12007-05-29 21:53:49 +0000846
847 if (BB->getTerminator()->getNumSuccessors() == 1) {
Owen Anderson9b89e4b2007-06-05 17:31:23 +0000848 if (visited.find(BB->getTerminator()->getSuccessor(0)) ==
849 visited.end())
Owen Andersonb56fba02007-06-19 03:31:41 +0000850 phi_translate_set(VN.getMaximalValues(), BB,
851 BB->getTerminator()->getSuccessor(0),
Owen Andersona75dd4d2007-06-12 00:50:47 +0000852 anticOut);
Owen Anderson81d156e2007-05-31 00:42:15 +0000853 else
Owen Andersonb56fba02007-06-19 03:31:41 +0000854 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
855 BB, BB->getTerminator()->getSuccessor(0),
856 anticOut);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000857 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
Owen Anderson3df52992007-06-04 23:28:33 +0000858 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
859 anticOut.insert(anticipatedIn[first].begin(),
860 anticipatedIn[first].end());
861 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
Owen Anderson5fba6c12007-05-29 21:53:49 +0000862 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
Owen Andersonb56fba02007-06-19 03:31:41 +0000863 std::set<Value*>& succAnticIn = anticipatedIn[currSucc];
Owen Anderson3df52992007-06-04 23:28:33 +0000864
Owen Andersonb56fba02007-06-19 03:31:41 +0000865 std::set<Value*> temp;
866 std::insert_iterator<std::set<Value*> > temp_ins(temp,
867 temp.begin());
Owen Anderson3df52992007-06-04 23:28:33 +0000868 std::set_intersection(anticOut.begin(), anticOut.end(),
869 succAnticIn.begin(), succAnticIn.end(),
Owen Andersonb56fba02007-06-19 03:31:41 +0000870 temp_ins);
Owen Anderson3df52992007-06-04 23:28:33 +0000871
872 anticOut.clear();
873 anticOut.insert(temp.begin(), temp.end());
Owen Anderson5fba6c12007-05-29 21:53:49 +0000874 }
875 }
876
Owen Anderson3df52992007-06-04 23:28:33 +0000877 DOUT << "ANTIC_OUT: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000878 dump_unique(anticOut);
Owen Anderson3df52992007-06-04 23:28:33 +0000879 DOUT << "\n";
880
Owen Andersonb56fba02007-06-19 03:31:41 +0000881 std::set<Value*> S;
882 std::insert_iterator<std::set<Value*> > s_ins(S, S.begin());
883 std::set_difference(anticOut.begin(), anticOut.end(),
884 generatedTemporaries[BB].begin(),
885 generatedTemporaries[BB].end(),
886 s_ins);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000887
888 anticIn.clear();
Owen Andersonb56fba02007-06-19 03:31:41 +0000889 std::insert_iterator<std::set<Value*> > ai_ins(anticIn, anticIn.begin());
890 std::set_difference(generatedExpressions[BB].begin(),
891 generatedExpressions[BB].end(),
892 generatedTemporaries[BB].begin(),
893 generatedTemporaries[BB].end(),
894 ai_ins);
Owen Anderson3c9d8ee2007-06-04 23:34:56 +0000895
Owen Andersonb56fba02007-06-19 03:31:41 +0000896 for (std::set<Value*>::iterator I = S.begin(), E = S.end();
Owen Anderson3c9d8ee2007-06-04 23:34:56 +0000897 I != E; ++I) {
Owen Anderson1370faf2007-06-19 07:35:36 +0000898 // For non-opaque values, we should already have a value numbering.
899 // However, for opaques, such as constants within PHI nodes, it is
900 // possible that they have not yet received a number. Make sure they do
901 // so now.
902 uint32_t valNum = 0;
903 if (isa<BinaryOperator>(*I) || isa<CmpInst>(*I))
904 valNum = VN.lookup(*I);
905 else
906 valNum = VN.lookup_or_add(*I);
907 if (find_leader(anticIn, valNum) == 0)
Owen Andersonb56fba02007-06-19 03:31:41 +0000908 val_insert(anticIn, *I);
Owen Anderson3c9d8ee2007-06-04 23:34:56 +0000909 }
Owen Anderson5fba6c12007-05-29 21:53:49 +0000910
Owen Andersonbe802402007-06-08 01:03:01 +0000911 clean(anticIn);
Owen Anderson5fba6c12007-05-29 21:53:49 +0000912
Owen Anderson3df52992007-06-04 23:28:33 +0000913 DOUT << "ANTIC_IN: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000914 dump_unique(anticIn);
Owen Anderson3df52992007-06-04 23:28:33 +0000915 DOUT << "\n";
916
Owen Andersonddbe4302007-06-05 23:46:12 +0000917 if (old.size() != anticIn.size())
Owen Anderson5fba6c12007-05-29 21:53:49 +0000918 changed = true;
919
920 anticOut.clear();
921 }
Owen Anderson38b6b222007-06-04 18:05:26 +0000922
Owen Anderson5fba6c12007-05-29 21:53:49 +0000923 iterations++;
924 }
925
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000926 DOUT << "Iterations: " << iterations << "\n";
Owen Anderson5fba6c12007-05-29 21:53:49 +0000927
928 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000929 DOUT << "Name: " << I->getName().c_str() << "\n";
930
931 DOUT << "TMP_GEN: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000932 dump(generatedTemporaries[I]);
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000933 DOUT << "\n";
934
935 DOUT << "EXP_GEN: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000936 dump_unique(generatedExpressions[I]);
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000937 DOUT << "\n";
938
939 DOUT << "ANTIC_IN: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000940 dump_unique(anticipatedIn[I]);
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000941 DOUT << "\n";
Owen Anderson0b68cda2007-06-03 05:55:58 +0000942
943 DOUT << "AVAIL_OUT: ";
Owen Andersonbe802402007-06-08 01:03:01 +0000944 dump_unique(availableOut[I]);
Owen Anderson0b68cda2007-06-03 05:55:58 +0000945 DOUT << "\n";
Owen Anderson4a6ec8f2007-05-29 23:15:21 +0000946 }
Owen Anderson5fba6c12007-05-29 21:53:49 +0000947
Owen Anderson634a0632007-06-06 01:27:49 +0000948 // Phase 2: Insert
Owen Andersonbe802402007-06-08 01:03:01 +0000949 DOUT<< "\nPhase 2: Insertion\n";
950
Owen Andersonb56fba02007-06-19 03:31:41 +0000951 std::map<BasicBlock*, std::set<Value*> > new_sets;
Owen Andersonbe802402007-06-08 01:03:01 +0000952 unsigned i_iterations = 0;
953 bool new_stuff = true;
954 while (new_stuff) {
955 new_stuff = false;
956 DOUT << "Iteration: " << i_iterations << "\n\n";
957 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
958 E = df_end(DT.getRootNode()); DI != E; ++DI) {
959 BasicBlock* BB = DI->getBlock();
960
Owen Andersond184c182007-06-11 16:25:17 +0000961 if (BB == 0)
962 continue;
963
Owen Andersonb56fba02007-06-19 03:31:41 +0000964 std::set<Value*>& new_set = new_sets[BB];
965 std::set<Value*>& availOut = availableOut[BB];
966 std::set<Value*>& anticIn = anticipatedIn[BB];
Owen Andersonbe802402007-06-08 01:03:01 +0000967
Owen Anderson55994f22007-06-08 20:44:02 +0000968 new_set.clear();
969
Owen Andersonbe802402007-06-08 01:03:01 +0000970 // Replace leaders with leaders inherited from dominator
971 if (DI->getIDom() != 0) {
Owen Andersonb56fba02007-06-19 03:31:41 +0000972 std::set<Value*>& dom_set = new_sets[DI->getIDom()->getBlock()];
973 for (std::set<Value*>::iterator I = dom_set.begin(),
Owen Andersonbe802402007-06-08 01:03:01 +0000974 E = dom_set.end(); I != E; ++I) {
975 new_set.insert(*I);
Owen Andersonb56fba02007-06-19 03:31:41 +0000976 val_replace(availOut, *I);
Owen Andersonbe802402007-06-08 01:03:01 +0000977 }
978 }
979
980 // If there is more than one predecessor...
981 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
982 std::vector<Value*> workList;
983 topo_sort(anticIn, workList);
984
985 DOUT << "Merge Block: " << BB->getName() << "\n";
986 DOUT << "ANTIC_IN: ";
987 dump_unique(anticIn);
988 DOUT << "\n";
989
Owen Andersona75dd4d2007-06-12 00:50:47 +0000990 for (unsigned i = 0; i < workList.size(); ++i) {
991 Value* e = workList[i];
Owen Andersonbe802402007-06-08 01:03:01 +0000992
Owen Anderson223718c2007-06-09 18:35:31 +0000993 if (isa<BinaryOperator>(e) || isa<CmpInst>(e)) {
Owen Andersonb56fba02007-06-19 03:31:41 +0000994 if (find_leader(availableOut[DI->getIDom()->getBlock()], VN.lookup(e)) != 0)
Owen Andersonbe802402007-06-08 01:03:01 +0000995 continue;
996
997 std::map<BasicBlock*, Value*> avail;
998 bool by_some = false;
999 int num_avail = 0;
1000
1001 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1002 ++PI) {
Owen Anderson4036ad42007-06-12 22:43:57 +00001003 Value *e2 = phi_translate(e, *PI, BB);
Owen Andersonb56fba02007-06-19 03:31:41 +00001004 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
Owen Andersonbe802402007-06-08 01:03:01 +00001005
1006 if (e3 == 0) {
1007 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1008 if (av != avail.end())
1009 avail.erase(av);
1010 avail.insert(std::make_pair(*PI, e2));
1011 } else {
1012 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1013 if (av != avail.end())
1014 avail.erase(av);
1015 avail.insert(std::make_pair(*PI, e3));
1016
1017 by_some = true;
1018 num_avail++;
1019 }
1020 }
1021
1022 if (by_some &&
1023 num_avail < std::distance(pred_begin(BB), pred_end(BB))) {
1024 DOUT << "Processing Value: ";
1025 DEBUG(e->dump());
1026 DOUT << "\n\n";
1027
1028 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1029 PI != PE; ++PI) {
1030 Value* e2 = avail[*PI];
Owen Andersonb56fba02007-06-19 03:31:41 +00001031 if (!find_leader(availableOut[*PI], VN.lookup(e2))) {
Owen Anderson223718c2007-06-09 18:35:31 +00001032 User* U = cast<User>(e2);
Owen Andersonbe802402007-06-08 01:03:01 +00001033
1034 Value* s1 = 0;
Owen Anderson658f2c42007-06-16 00:26:54 +00001035 if (isa<BinaryOperator>(U->getOperand(0)) ||
1036 isa<CmpInst>(U->getOperand(0)))
Owen Andersonb56fba02007-06-19 03:31:41 +00001037 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
Owen Andersonbe802402007-06-08 01:03:01 +00001038 else
Owen Anderson223718c2007-06-09 18:35:31 +00001039 s1 = U->getOperand(0);
Owen Andersonbe802402007-06-08 01:03:01 +00001040
1041 Value* s2 = 0;
Owen Anderson658f2c42007-06-16 00:26:54 +00001042 if (isa<BinaryOperator>(U->getOperand(1)) ||
1043 isa<CmpInst>(U->getOperand(1)))
Owen Andersonb56fba02007-06-19 03:31:41 +00001044 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
Owen Andersonbe802402007-06-08 01:03:01 +00001045 else
Owen Anderson223718c2007-06-09 18:35:31 +00001046 s2 = U->getOperand(1);
Owen Andersonbe802402007-06-08 01:03:01 +00001047
Owen Anderson223718c2007-06-09 18:35:31 +00001048 Value* newVal = 0;
1049 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1050 newVal = BinaryOperator::create(BO->getOpcode(),
Owen Andersonbe802402007-06-08 01:03:01 +00001051 s1, s2,
1052 BO->getName()+".gvnpre",
1053 (*PI)->getTerminator());
Owen Anderson223718c2007-06-09 18:35:31 +00001054 else if (CmpInst* C = dyn_cast<CmpInst>(U))
1055 newVal = CmpInst::create(C->getOpcode(),
1056 C->getPredicate(),
1057 s1, s2,
1058 C->getName()+".gvnpre",
1059 (*PI)->getTerminator());
1060
Owen Andersonb56fba02007-06-19 03:31:41 +00001061 VN.add(newVal, VN.lookup(U));
Owen Anderson55994f22007-06-08 20:44:02 +00001062
Owen Andersonb56fba02007-06-19 03:31:41 +00001063 std::set<Value*>& predAvail = availableOut[*PI];
1064 val_replace(predAvail, newVal);
Owen Andersonbe802402007-06-08 01:03:01 +00001065
1066 DOUT << "Creating value: " << std::hex << newVal << std::dec << "\n";
1067
1068 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1069 if (av != avail.end())
1070 avail.erase(av);
1071 avail.insert(std::make_pair(*PI, newVal));
Owen Anderson7d76b2a2007-06-08 22:02:36 +00001072
1073 ++NumInsertedVals;
Owen Andersonbe802402007-06-08 01:03:01 +00001074 }
1075 }
1076
1077 PHINode* p = 0;
1078
1079 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1080 PI != PE; ++PI) {
1081 if (p == 0)
1082 p = new PHINode(avail[*PI]->getType(), "gvnpre-join",
1083 BB->begin());
1084
1085 p->addIncoming(avail[*PI], *PI);
1086 }
1087
Owen Andersonb56fba02007-06-19 03:31:41 +00001088 VN.add(p, VN.lookup(e));
Owen Andersonbe802402007-06-08 01:03:01 +00001089 DOUT << "Creating value: " << std::hex << p << std::dec << "\n";
1090
Owen Andersonb56fba02007-06-19 03:31:41 +00001091 val_replace(availOut, p);
Owen Andersonbe802402007-06-08 01:03:01 +00001092 availOut.insert(p);
Owen Anderson55994f22007-06-08 20:44:02 +00001093
Owen Andersonbe802402007-06-08 01:03:01 +00001094 new_stuff = true;
1095
1096 DOUT << "Preds After Processing: ";
1097 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1098 PI != PE; ++PI)
1099 DEBUG((*PI)->dump());
1100 DOUT << "\n\n";
1101
1102 DOUT << "Merge Block After Processing: ";
1103 DEBUG(BB->dump());
1104 DOUT << "\n\n";
1105
1106 new_set.insert(p);
Owen Anderson7d76b2a2007-06-08 22:02:36 +00001107
1108 ++NumInsertedPhis;
Owen Andersonbe802402007-06-08 01:03:01 +00001109 }
1110 }
1111 }
1112 }
1113 }
1114 i_iterations++;
1115 }
Owen Anderson634a0632007-06-06 01:27:49 +00001116
1117 // Phase 3: Eliminate
Owen Anderson4036ad42007-06-12 22:43:57 +00001118 elimination();
Owen Anderson55994f22007-06-08 20:44:02 +00001119
Owen Andersonbe802402007-06-08 01:03:01 +00001120 // Phase 4: Cleanup
Owen Anderson42769842007-06-12 16:57:50 +00001121 cleanup();
Owen Andersonbe802402007-06-08 01:03:01 +00001122
Owen Anderson42769842007-06-12 16:57:50 +00001123 return true;
Owen Anderson5fba6c12007-05-29 21:53:49 +00001124}