blob: 4588a7f24c5b68c7b8d5d2deda78e2d48ea8f834 [file] [log] [blame]
Owen Andersonea12a062007-05-29 21:53:49 +00001//===- GVNPRE.cpp - Eliminate redundant values and expressions ------------===//
2//
3// The LLVM Compiler Infrastructure
4//
Chris Lattner4ee451d2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Owen Andersonea12a062007-05-29 21:53:49 +00007//
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 Andersona7f916c2007-06-08 20:57:08 +000016// live ranges, and should be used with caution on platforms that are very
Owen Andersonea12a062007-05-29 21:53:49 +000017// sensitive to register pressure.
18//
Matthijs Kooijman845f5242008-06-05 07:55:49 +000019// Note that this pass does the value numbering itself, it does not use the
20// ValueNumbering analysis passes.
21//
Owen Andersonea12a062007-05-29 21:53:49 +000022//===----------------------------------------------------------------------===//
23
24#define DEBUG_TYPE "gvnpre"
25#include "llvm/Value.h"
26#include "llvm/Transforms/Scalar.h"
27#include "llvm/Instructions.h"
28#include "llvm/Function.h"
Owen Anderson40dc00e2007-06-29 00:40:05 +000029#include "llvm/DerivedTypes.h"
Owen Andersonea12a062007-05-29 21:53:49 +000030#include "llvm/Analysis/Dominators.h"
Owen Anderson82575d82007-06-22 00:20:30 +000031#include "llvm/ADT/BitVector.h"
Owen Anderson4f703ec2007-06-19 23:23:54 +000032#include "llvm/ADT/DenseMap.h"
Owen Andersonea12a062007-05-29 21:53:49 +000033#include "llvm/ADT/DepthFirstIterator.h"
Owen Anderson9030d382007-06-25 18:25:31 +000034#include "llvm/ADT/PostOrderIterator.h"
Owen Anderson66fd9062007-06-21 17:57:53 +000035#include "llvm/ADT/SmallPtrSet.h"
Owen Andersonfb665412007-07-19 06:13:15 +000036#include "llvm/ADT/SmallVector.h"
Owen Andersonea12a062007-05-29 21:53:49 +000037#include "llvm/ADT/Statistic.h"
Owen Anderson2a5c9d82007-07-05 23:11:26 +000038#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
Owen Anderson397d4052007-06-08 01:03:01 +000039#include "llvm/Support/CFG.h"
Owen Andersonea12a062007-05-29 21:53:49 +000040#include "llvm/Support/Compiler.h"
Owen Andersoncdf8efd2007-05-29 23:15:21 +000041#include "llvm/Support/Debug.h"
Torok Edwinc25e7582009-07-11 20:10:48 +000042#include "llvm/Support/ErrorHandling.h"
Owen Andersonea12a062007-05-29 21:53:49 +000043#include <algorithm>
Owen Anderson243f3482007-05-31 22:44:11 +000044#include <deque>
Owen Andersonea12a062007-05-29 21:53:49 +000045#include <map>
Owen Andersonea12a062007-05-29 21:53:49 +000046using namespace llvm;
47
Owen Anderson086f5f32007-06-19 03:31:41 +000048//===----------------------------------------------------------------------===//
49// ValueTable Class
50//===----------------------------------------------------------------------===//
51
Dan Gohman844731a2008-05-13 00:00:25 +000052namespace {
53
Owen Anderson9cb56012007-06-21 00:19:05 +000054/// This class holds the mapping between values and value numbers. It is used
55/// as an efficient mechanism to determine the expression-wise equivalence of
56/// two values.
Owen Anderson086f5f32007-06-19 03:31:41 +000057
Owen Andersonfb665412007-07-19 06:13:15 +000058struct Expression {
Dan Gohmanae3a0be2009-06-04 22:49:04 +000059 enum ExpressionOpcode { ADD, FADD, SUB, FSUB, MUL, FMUL,
60 UDIV, SDIV, FDIV, UREM, SREM,
Owen Andersonfb665412007-07-19 06:13:15 +000061 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
62 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
63 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
64 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
65 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
66 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
67 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
68 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
69 PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY,
70 TOMBSTONE };
71
72 ExpressionOpcode opcode;
73 const Type* type;
74 uint32_t firstVN;
75 uint32_t secondVN;
76 uint32_t thirdVN;
77 SmallVector<uint32_t, 4> varargs;
78
79 Expression() { }
Dan Gohman746767b2007-09-24 15:48:49 +000080 explicit Expression(ExpressionOpcode o) : opcode(o) { }
Owen Andersonfb665412007-07-19 06:13:15 +000081
82 bool operator==(const Expression &other) const {
83 if (opcode != other.opcode)
84 return false;
85 else if (opcode == EMPTY || opcode == TOMBSTONE)
86 return true;
87 else if (type != other.type)
88 return false;
89 else if (firstVN != other.firstVN)
90 return false;
91 else if (secondVN != other.secondVN)
92 return false;
93 else if (thirdVN != other.thirdVN)
94 return false;
95 else {
96 if (varargs.size() != other.varargs.size())
97 return false;
98
99 for (size_t i = 0; i < varargs.size(); ++i)
100 if (varargs[i] != other.varargs[i])
101 return false;
102
103 return true;
104 }
105 }
106
107 bool operator!=(const Expression &other) const {
108 if (opcode != other.opcode)
109 return true;
110 else if (opcode == EMPTY || opcode == TOMBSTONE)
111 return false;
112 else if (type != other.type)
113 return true;
114 else if (firstVN != other.firstVN)
115 return true;
116 else if (secondVN != other.secondVN)
117 return true;
118 else if (thirdVN != other.thirdVN)
119 return true;
120 else {
121 if (varargs.size() != other.varargs.size())
122 return true;
123
124 for (size_t i = 0; i < varargs.size(); ++i)
125 if (varargs[i] != other.varargs[i])
126 return true;
127
128 return false;
129 }
130 }
131};
132
Dan Gohman844731a2008-05-13 00:00:25 +0000133}
Owen Andersonfb665412007-07-19 06:13:15 +0000134
Owen Anderson086f5f32007-06-19 03:31:41 +0000135namespace {
136 class VISIBILITY_HIDDEN ValueTable {
Owen Anderson086f5f32007-06-19 03:31:41 +0000137 private:
Owen Anderson4f703ec2007-06-19 23:23:54 +0000138 DenseMap<Value*, uint32_t> valueNumbering;
Owen Andersonfb665412007-07-19 06:13:15 +0000139 DenseMap<Expression, uint32_t> expressionNumbering;
Owen Anderson086f5f32007-06-19 03:31:41 +0000140
Owen Anderson086f5f32007-06-19 03:31:41 +0000141 uint32_t nextValueNumber;
142
143 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
144 Expression::ExpressionOpcode getOpcode(CmpInst* C);
Owen Andersonca6c31c2007-06-29 00:51:03 +0000145 Expression::ExpressionOpcode getOpcode(CastInst* C);
Owen Anderson9cb56012007-06-21 00:19:05 +0000146 Expression create_expression(BinaryOperator* BO);
147 Expression create_expression(CmpInst* C);
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000148 Expression create_expression(ShuffleVectorInst* V);
149 Expression create_expression(ExtractElementInst* C);
150 Expression create_expression(InsertElementInst* V);
Owen Anderson890e1a02007-06-28 23:51:21 +0000151 Expression create_expression(SelectInst* V);
Owen Andersonca6c31c2007-06-29 00:51:03 +0000152 Expression create_expression(CastInst* C);
Owen Andersoneb216862007-07-03 22:50:56 +0000153 Expression create_expression(GetElementPtrInst* G);
Owen Anderson086f5f32007-06-19 03:31:41 +0000154 public:
155 ValueTable() { nextValueNumber = 1; }
156 uint32_t lookup_or_add(Value* V);
Owen Anderson890e1a02007-06-28 23:51:21 +0000157 uint32_t lookup(Value* V) const;
Owen Anderson086f5f32007-06-19 03:31:41 +0000158 void add(Value* V, uint32_t num);
159 void clear();
Owen Anderson20cb51f2007-06-19 05:37:32 +0000160 void erase(Value* v);
Owen Anderson82575d82007-06-22 00:20:30 +0000161 unsigned size();
Owen Anderson086f5f32007-06-19 03:31:41 +0000162 };
163}
164
Owen Andersonfb665412007-07-19 06:13:15 +0000165namespace llvm {
Chris Lattner76c1b972007-09-17 18:34:04 +0000166template <> struct DenseMapInfo<Expression> {
Owen Anderson9fed5892007-08-02 18:20:52 +0000167 static inline Expression getEmptyKey() {
168 return Expression(Expression::EMPTY);
169 }
170
171 static inline Expression getTombstoneKey() {
172 return Expression(Expression::TOMBSTONE);
173 }
Owen Andersonfb665412007-07-19 06:13:15 +0000174
175 static unsigned getHashValue(const Expression e) {
176 unsigned hash = e.opcode;
177
178 hash = e.firstVN + hash * 37;
179 hash = e.secondVN + hash * 37;
180 hash = e.thirdVN + hash * 37;
181
Anton Korobeynikov07e6e562008-02-20 11:26:25 +0000182 hash = ((unsigned)((uintptr_t)e.type >> 4) ^
183 (unsigned)((uintptr_t)e.type >> 9)) +
184 hash * 37;
Owen Andersonfb665412007-07-19 06:13:15 +0000185
Owen Anderson9fed5892007-08-02 18:20:52 +0000186 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
187 E = e.varargs.end(); I != E; ++I)
Owen Andersonfb665412007-07-19 06:13:15 +0000188 hash = *I + hash * 37;
189
190 return hash;
191 }
Chris Lattner76c1b972007-09-17 18:34:04 +0000192 static bool isEqual(const Expression &LHS, const Expression &RHS) {
193 return LHS == RHS;
194 }
Owen Andersonfb665412007-07-19 06:13:15 +0000195 static bool isPod() { return true; }
196};
197}
198
Owen Anderson9cb56012007-06-21 00:19:05 +0000199//===----------------------------------------------------------------------===//
200// ValueTable Internal Functions
201//===----------------------------------------------------------------------===//
Owen Andersonfb665412007-07-19 06:13:15 +0000202Expression::ExpressionOpcode
Owen Anderson9cb56012007-06-21 00:19:05 +0000203 ValueTable::getOpcode(BinaryOperator* BO) {
Owen Anderson086f5f32007-06-19 03:31:41 +0000204 switch(BO->getOpcode()) {
205 case Instruction::Add:
206 return Expression::ADD;
Dan Gohmanae3a0be2009-06-04 22:49:04 +0000207 case Instruction::FAdd:
208 return Expression::FADD;
Owen Anderson086f5f32007-06-19 03:31:41 +0000209 case Instruction::Sub:
210 return Expression::SUB;
Dan Gohmanae3a0be2009-06-04 22:49:04 +0000211 case Instruction::FSub:
212 return Expression::FSUB;
Owen Anderson086f5f32007-06-19 03:31:41 +0000213 case Instruction::Mul:
214 return Expression::MUL;
Dan Gohmanae3a0be2009-06-04 22:49:04 +0000215 case Instruction::FMul:
216 return Expression::FMUL;
Owen Anderson086f5f32007-06-19 03:31:41 +0000217 case Instruction::UDiv:
218 return Expression::UDIV;
219 case Instruction::SDiv:
220 return Expression::SDIV;
221 case Instruction::FDiv:
222 return Expression::FDIV;
223 case Instruction::URem:
224 return Expression::UREM;
225 case Instruction::SRem:
226 return Expression::SREM;
227 case Instruction::FRem:
228 return Expression::FREM;
229 case Instruction::Shl:
230 return Expression::SHL;
231 case Instruction::LShr:
232 return Expression::LSHR;
233 case Instruction::AShr:
234 return Expression::ASHR;
235 case Instruction::And:
236 return Expression::AND;
237 case Instruction::Or:
238 return Expression::OR;
239 case Instruction::Xor:
240 return Expression::XOR;
241
242 // THIS SHOULD NEVER HAPPEN
243 default:
Torok Edwinc23197a2009-07-14 16:55:14 +0000244 llvm_unreachable("Binary operator with unknown opcode?");
Owen Anderson086f5f32007-06-19 03:31:41 +0000245 return Expression::ADD;
246 }
247}
248
Owen Andersonfb665412007-07-19 06:13:15 +0000249Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
Owen Anderson086f5f32007-06-19 03:31:41 +0000250 if (C->getOpcode() == Instruction::ICmp) {
251 switch (C->getPredicate()) {
252 case ICmpInst::ICMP_EQ:
253 return Expression::ICMPEQ;
254 case ICmpInst::ICMP_NE:
255 return Expression::ICMPNE;
256 case ICmpInst::ICMP_UGT:
257 return Expression::ICMPUGT;
258 case ICmpInst::ICMP_UGE:
259 return Expression::ICMPUGE;
260 case ICmpInst::ICMP_ULT:
261 return Expression::ICMPULT;
262 case ICmpInst::ICMP_ULE:
263 return Expression::ICMPULE;
264 case ICmpInst::ICMP_SGT:
265 return Expression::ICMPSGT;
266 case ICmpInst::ICMP_SGE:
267 return Expression::ICMPSGE;
268 case ICmpInst::ICMP_SLT:
269 return Expression::ICMPSLT;
270 case ICmpInst::ICMP_SLE:
271 return Expression::ICMPSLE;
272
273 // THIS SHOULD NEVER HAPPEN
274 default:
Torok Edwinc23197a2009-07-14 16:55:14 +0000275 llvm_unreachable("Comparison with unknown predicate?");
Owen Anderson086f5f32007-06-19 03:31:41 +0000276 return Expression::ICMPEQ;
277 }
278 } else {
279 switch (C->getPredicate()) {
280 case FCmpInst::FCMP_OEQ:
281 return Expression::FCMPOEQ;
282 case FCmpInst::FCMP_OGT:
283 return Expression::FCMPOGT;
284 case FCmpInst::FCMP_OGE:
285 return Expression::FCMPOGE;
286 case FCmpInst::FCMP_OLT:
287 return Expression::FCMPOLT;
288 case FCmpInst::FCMP_OLE:
289 return Expression::FCMPOLE;
290 case FCmpInst::FCMP_ONE:
291 return Expression::FCMPONE;
292 case FCmpInst::FCMP_ORD:
293 return Expression::FCMPORD;
294 case FCmpInst::FCMP_UNO:
295 return Expression::FCMPUNO;
296 case FCmpInst::FCMP_UEQ:
297 return Expression::FCMPUEQ;
298 case FCmpInst::FCMP_UGT:
299 return Expression::FCMPUGT;
300 case FCmpInst::FCMP_UGE:
301 return Expression::FCMPUGE;
302 case FCmpInst::FCMP_ULT:
303 return Expression::FCMPULT;
304 case FCmpInst::FCMP_ULE:
305 return Expression::FCMPULE;
306 case FCmpInst::FCMP_UNE:
307 return Expression::FCMPUNE;
308
309 // THIS SHOULD NEVER HAPPEN
310 default:
Torok Edwinc23197a2009-07-14 16:55:14 +0000311 llvm_unreachable("Comparison with unknown predicate?");
Owen Anderson086f5f32007-06-19 03:31:41 +0000312 return Expression::FCMPOEQ;
Owen Anderson139fe842007-06-09 18:35:31 +0000313 }
314 }
Owen Anderson086f5f32007-06-19 03:31:41 +0000315}
316
Owen Andersonfb665412007-07-19 06:13:15 +0000317Expression::ExpressionOpcode
Owen Andersonca6c31c2007-06-29 00:51:03 +0000318 ValueTable::getOpcode(CastInst* C) {
319 switch(C->getOpcode()) {
320 case Instruction::Trunc:
321 return Expression::TRUNC;
322 case Instruction::ZExt:
323 return Expression::ZEXT;
324 case Instruction::SExt:
325 return Expression::SEXT;
326 case Instruction::FPToUI:
327 return Expression::FPTOUI;
328 case Instruction::FPToSI:
329 return Expression::FPTOSI;
330 case Instruction::UIToFP:
331 return Expression::UITOFP;
332 case Instruction::SIToFP:
333 return Expression::SITOFP;
334 case Instruction::FPTrunc:
335 return Expression::FPTRUNC;
336 case Instruction::FPExt:
337 return Expression::FPEXT;
338 case Instruction::PtrToInt:
339 return Expression::PTRTOINT;
340 case Instruction::IntToPtr:
341 return Expression::INTTOPTR;
342 case Instruction::BitCast:
343 return Expression::BITCAST;
344
345 // THIS SHOULD NEVER HAPPEN
346 default:
Torok Edwinc23197a2009-07-14 16:55:14 +0000347 llvm_unreachable("Cast operator with unknown opcode?");
Owen Andersonca6c31c2007-06-29 00:51:03 +0000348 return Expression::BITCAST;
349 }
350}
351
Owen Andersonfb665412007-07-19 06:13:15 +0000352Expression ValueTable::create_expression(BinaryOperator* BO) {
Owen Anderson9cb56012007-06-21 00:19:05 +0000353 Expression e;
354
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000355 e.firstVN = lookup_or_add(BO->getOperand(0));
356 e.secondVN = lookup_or_add(BO->getOperand(1));
357 e.thirdVN = 0;
Owen Anderson40dc00e2007-06-29 00:40:05 +0000358 e.type = BO->getType();
Owen Anderson9cb56012007-06-21 00:19:05 +0000359 e.opcode = getOpcode(BO);
360
Owen Anderson9cb56012007-06-21 00:19:05 +0000361 return e;
362}
363
Owen Andersonfb665412007-07-19 06:13:15 +0000364Expression ValueTable::create_expression(CmpInst* C) {
Owen Anderson9cb56012007-06-21 00:19:05 +0000365 Expression e;
366
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000367 e.firstVN = lookup_or_add(C->getOperand(0));
368 e.secondVN = lookup_or_add(C->getOperand(1));
369 e.thirdVN = 0;
Owen Anderson40dc00e2007-06-29 00:40:05 +0000370 e.type = C->getType();
Owen Anderson9cb56012007-06-21 00:19:05 +0000371 e.opcode = getOpcode(C);
372
Owen Anderson9cb56012007-06-21 00:19:05 +0000373 return e;
374}
375
Owen Andersonfb665412007-07-19 06:13:15 +0000376Expression ValueTable::create_expression(CastInst* C) {
Owen Andersonca6c31c2007-06-29 00:51:03 +0000377 Expression e;
378
379 e.firstVN = lookup_or_add(C->getOperand(0));
380 e.secondVN = 0;
381 e.thirdVN = 0;
382 e.type = C->getType();
383 e.opcode = getOpcode(C);
384
385 return e;
386}
387
Owen Andersonfb665412007-07-19 06:13:15 +0000388Expression ValueTable::create_expression(ShuffleVectorInst* S) {
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000389 Expression e;
390
391 e.firstVN = lookup_or_add(S->getOperand(0));
392 e.secondVN = lookup_or_add(S->getOperand(1));
393 e.thirdVN = lookup_or_add(S->getOperand(2));
Owen Anderson40dc00e2007-06-29 00:40:05 +0000394 e.type = S->getType();
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000395 e.opcode = Expression::SHUFFLE;
396
397 return e;
398}
399
Owen Andersonfb665412007-07-19 06:13:15 +0000400Expression ValueTable::create_expression(ExtractElementInst* E) {
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000401 Expression e;
402
403 e.firstVN = lookup_or_add(E->getOperand(0));
404 e.secondVN = lookup_or_add(E->getOperand(1));
405 e.thirdVN = 0;
Owen Anderson40dc00e2007-06-29 00:40:05 +0000406 e.type = E->getType();
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000407 e.opcode = Expression::EXTRACT;
408
409 return e;
410}
411
Owen Andersonfb665412007-07-19 06:13:15 +0000412Expression ValueTable::create_expression(InsertElementInst* I) {
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000413 Expression e;
414
415 e.firstVN = lookup_or_add(I->getOperand(0));
416 e.secondVN = lookup_or_add(I->getOperand(1));
417 e.thirdVN = lookup_or_add(I->getOperand(2));
Owen Anderson40dc00e2007-06-29 00:40:05 +0000418 e.type = I->getType();
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000419 e.opcode = Expression::INSERT;
420
421 return e;
422}
423
Owen Andersonfb665412007-07-19 06:13:15 +0000424Expression ValueTable::create_expression(SelectInst* I) {
Owen Anderson890e1a02007-06-28 23:51:21 +0000425 Expression e;
426
427 e.firstVN = lookup_or_add(I->getCondition());
428 e.secondVN = lookup_or_add(I->getTrueValue());
429 e.thirdVN = lookup_or_add(I->getFalseValue());
Owen Anderson40dc00e2007-06-29 00:40:05 +0000430 e.type = I->getType();
Owen Anderson890e1a02007-06-28 23:51:21 +0000431 e.opcode = Expression::SELECT;
432
433 return e;
434}
435
Owen Andersonfb665412007-07-19 06:13:15 +0000436Expression ValueTable::create_expression(GetElementPtrInst* G) {
Owen Andersoneb216862007-07-03 22:50:56 +0000437 Expression e;
438
439 e.firstVN = lookup_or_add(G->getPointerOperand());
440 e.secondVN = 0;
441 e.thirdVN = 0;
442 e.type = G->getType();
Owen Andersonc9399be2007-07-20 08:19:20 +0000443 e.opcode = Expression::GEP;
Owen Andersoneb216862007-07-03 22:50:56 +0000444
445 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
446 I != E; ++I)
447 e.varargs.push_back(lookup_or_add(*I));
448
449 return e;
450}
451
Owen Anderson9cb56012007-06-21 00:19:05 +0000452//===----------------------------------------------------------------------===//
453// ValueTable External Functions
454//===----------------------------------------------------------------------===//
455
456/// lookup_or_add - Returns the value number for the specified value, assigning
457/// it a new number if it did not have one before.
Owen Anderson086f5f32007-06-19 03:31:41 +0000458uint32_t ValueTable::lookup_or_add(Value* V) {
Owen Anderson4f703ec2007-06-19 23:23:54 +0000459 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
Owen Anderson086f5f32007-06-19 03:31:41 +0000460 if (VI != valueNumbering.end())
461 return VI->second;
Owen Anderson139fe842007-06-09 18:35:31 +0000462
Owen Anderson139fe842007-06-09 18:35:31 +0000463
Owen Anderson086f5f32007-06-19 03:31:41 +0000464 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
465 Expression e = create_expression(BO);
466
Owen Andersonfb665412007-07-19 06:13:15 +0000467 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Anderson086f5f32007-06-19 03:31:41 +0000468 if (EI != expressionNumbering.end()) {
469 valueNumbering.insert(std::make_pair(V, EI->second));
470 return EI->second;
471 } else {
472 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
473 valueNumbering.insert(std::make_pair(V, nextValueNumber));
474
475 return nextValueNumber++;
476 }
477 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
478 Expression e = create_expression(C);
479
Owen Andersonfb665412007-07-19 06:13:15 +0000480 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Anderson086f5f32007-06-19 03:31:41 +0000481 if (EI != expressionNumbering.end()) {
482 valueNumbering.insert(std::make_pair(V, EI->second));
483 return EI->second;
484 } else {
485 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
486 valueNumbering.insert(std::make_pair(V, nextValueNumber));
487
488 return nextValueNumber++;
489 }
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000490 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
491 Expression e = create_expression(U);
492
Owen Andersonfb665412007-07-19 06:13:15 +0000493 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000494 if (EI != expressionNumbering.end()) {
495 valueNumbering.insert(std::make_pair(V, EI->second));
496 return EI->second;
497 } else {
498 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
499 valueNumbering.insert(std::make_pair(V, nextValueNumber));
500
501 return nextValueNumber++;
502 }
503 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
504 Expression e = create_expression(U);
505
Owen Andersonfb665412007-07-19 06:13:15 +0000506 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000507 if (EI != expressionNumbering.end()) {
508 valueNumbering.insert(std::make_pair(V, EI->second));
509 return EI->second;
510 } else {
511 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
512 valueNumbering.insert(std::make_pair(V, nextValueNumber));
513
514 return nextValueNumber++;
515 }
516 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
517 Expression e = create_expression(U);
518
Owen Andersonfb665412007-07-19 06:13:15 +0000519 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000520 if (EI != expressionNumbering.end()) {
521 valueNumbering.insert(std::make_pair(V, EI->second));
522 return EI->second;
523 } else {
524 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
525 valueNumbering.insert(std::make_pair(V, nextValueNumber));
526
527 return nextValueNumber++;
528 }
Owen Anderson890e1a02007-06-28 23:51:21 +0000529 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
530 Expression e = create_expression(U);
531
Owen Andersonfb665412007-07-19 06:13:15 +0000532 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Anderson890e1a02007-06-28 23:51:21 +0000533 if (EI != expressionNumbering.end()) {
534 valueNumbering.insert(std::make_pair(V, EI->second));
535 return EI->second;
536 } else {
537 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
538 valueNumbering.insert(std::make_pair(V, nextValueNumber));
539
540 return nextValueNumber++;
541 }
Owen Andersonca6c31c2007-06-29 00:51:03 +0000542 } else if (CastInst* U = dyn_cast<CastInst>(V)) {
543 Expression e = create_expression(U);
544
Owen Andersonfb665412007-07-19 06:13:15 +0000545 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Andersonca6c31c2007-06-29 00:51:03 +0000546 if (EI != expressionNumbering.end()) {
547 valueNumbering.insert(std::make_pair(V, EI->second));
548 return EI->second;
549 } else {
550 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
551 valueNumbering.insert(std::make_pair(V, nextValueNumber));
552
553 return nextValueNumber++;
554 }
Owen Anderson56533222007-07-03 23:51:19 +0000555 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
556 Expression e = create_expression(U);
557
Owen Andersonfb665412007-07-19 06:13:15 +0000558 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Anderson56533222007-07-03 23:51:19 +0000559 if (EI != expressionNumbering.end()) {
560 valueNumbering.insert(std::make_pair(V, EI->second));
561 return EI->second;
562 } else {
563 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
564 valueNumbering.insert(std::make_pair(V, nextValueNumber));
565
566 return nextValueNumber++;
567 }
Owen Anderson086f5f32007-06-19 03:31:41 +0000568 } else {
569 valueNumbering.insert(std::make_pair(V, nextValueNumber));
570 return nextValueNumber++;
Owen Andersona724ac12007-06-03 05:55:58 +0000571 }
Owen Anderson086f5f32007-06-19 03:31:41 +0000572}
573
Owen Anderson9cb56012007-06-21 00:19:05 +0000574/// lookup - Returns the value number of the specified value. Fails if
575/// the value has not yet been numbered.
Owen Anderson890e1a02007-06-28 23:51:21 +0000576uint32_t ValueTable::lookup(Value* V) const {
Owen Anderson4f703ec2007-06-19 23:23:54 +0000577 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
Owen Anderson086f5f32007-06-19 03:31:41 +0000578 if (VI != valueNumbering.end())
579 return VI->second;
580 else
Torok Edwinc23197a2009-07-14 16:55:14 +0000581 llvm_unreachable("Value not numbered?");
Owen Anderson086f5f32007-06-19 03:31:41 +0000582
583 return 0;
584}
585
Owen Anderson9cb56012007-06-21 00:19:05 +0000586/// add - Add the specified value with the given value number, removing
587/// its old number, if any
Owen Anderson086f5f32007-06-19 03:31:41 +0000588void ValueTable::add(Value* V, uint32_t num) {
Owen Anderson4f703ec2007-06-19 23:23:54 +0000589 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
Owen Anderson086f5f32007-06-19 03:31:41 +0000590 if (VI != valueNumbering.end())
591 valueNumbering.erase(VI);
592 valueNumbering.insert(std::make_pair(V, num));
593}
594
Owen Andersonf62c44a2007-06-25 05:41:12 +0000595/// clear - Remove all entries from the ValueTable
Owen Anderson086f5f32007-06-19 03:31:41 +0000596void ValueTable::clear() {
597 valueNumbering.clear();
598 expressionNumbering.clear();
599 nextValueNumber = 1;
600}
Owen Andersona724ac12007-06-03 05:55:58 +0000601
Owen Andersonf62c44a2007-06-25 05:41:12 +0000602/// erase - Remove a value from the value numbering
Owen Anderson20cb51f2007-06-19 05:37:32 +0000603void ValueTable::erase(Value* V) {
Owen Anderson20cb51f2007-06-19 05:37:32 +0000604 valueNumbering.erase(V);
Owen Anderson20cb51f2007-06-19 05:37:32 +0000605}
606
Owen Anderson82575d82007-06-22 00:20:30 +0000607/// size - Return the number of assigned value numbers
608unsigned ValueTable::size() {
609 // NOTE: zero is never assigned
610 return nextValueNumber;
611}
612
Dan Gohman844731a2008-05-13 00:00:25 +0000613namespace {
614
Owen Anderson9cb56012007-06-21 00:19:05 +0000615//===----------------------------------------------------------------------===//
Owen Andersonab3fd052007-07-09 16:43:55 +0000616// ValueNumberedSet Class
Owen Anderson0616dff2007-07-09 06:50:06 +0000617//===----------------------------------------------------------------------===//
618
619class ValueNumberedSet {
620 private:
621 SmallPtrSet<Value*, 8> contents;
622 BitVector numbers;
623 public:
624 ValueNumberedSet() { numbers.resize(1); }
Owen Anderson81c2a6e2007-07-10 00:27:22 +0000625 ValueNumberedSet(const ValueNumberedSet& other) {
626 numbers = other.numbers;
627 contents = other.contents;
628 }
Owen Anderson0616dff2007-07-09 06:50:06 +0000629
630 typedef SmallPtrSet<Value*, 8>::iterator iterator;
631
632 iterator begin() { return contents.begin(); }
633 iterator end() { return contents.end(); }
634
635 bool insert(Value* v) { return contents.insert(v); }
636 void insert(iterator I, iterator E) { contents.insert(I, E); }
637 void erase(Value* v) { contents.erase(v); }
Owen Andersona05a81b2007-07-10 00:09:25 +0000638 unsigned count(Value* v) { return contents.count(v); }
Owen Anderson0616dff2007-07-09 06:50:06 +0000639 size_t size() { return contents.size(); }
640
Owen Andersonb9eeb1a2007-07-09 07:56:55 +0000641 void set(unsigned i) {
Owen Anderson0616dff2007-07-09 06:50:06 +0000642 if (i >= numbers.size())
643 numbers.resize(i+1);
644
645 numbers.set(i);
646 }
647
Owen Andersondfa24352007-07-09 22:29:50 +0000648 void operator=(const ValueNumberedSet& other) {
649 contents = other.contents;
Owen Andersonb9eeb1a2007-07-09 07:56:55 +0000650 numbers = other.numbers;
651 }
652
653 void reset(unsigned i) {
Owen Anderson0616dff2007-07-09 06:50:06 +0000654 if (i < numbers.size())
655 numbers.reset(i);
656 }
657
Owen Andersonb9eeb1a2007-07-09 07:56:55 +0000658 bool test(unsigned i) {
Owen Anderson0616dff2007-07-09 06:50:06 +0000659 if (i >= numbers.size())
660 return false;
661
662 return numbers.test(i);
663 }
664
665 void clear() {
666 contents.clear();
667 numbers.clear();
668 }
669};
670
Dan Gohman844731a2008-05-13 00:00:25 +0000671}
672
Owen Anderson0616dff2007-07-09 06:50:06 +0000673//===----------------------------------------------------------------------===//
Owen Anderson9cb56012007-06-21 00:19:05 +0000674// GVNPRE Pass
675//===----------------------------------------------------------------------===//
676
Owen Andersonea12a062007-05-29 21:53:49 +0000677namespace {
678
679 class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
680 bool runOnFunction(Function &F);
681 public:
682 static char ID; // Pass identification, replacement for typeid
Dan Gohmanae73dc12008-09-04 17:05:41 +0000683 GVNPRE() : FunctionPass(&ID) {}
Owen Andersonea12a062007-05-29 21:53:49 +0000684
685 private:
Owen Anderson397d4052007-06-08 01:03:01 +0000686 ValueTable VN;
Owen Anderson19bc4a82007-07-19 06:37:56 +0000687 SmallVector<Instruction*, 8> createdExpressions;
Owen Anderson8214d502007-05-31 00:42:15 +0000688
Owen Anderson81c2a6e2007-07-10 00:27:22 +0000689 DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
690 DenseMap<BasicBlock*, ValueNumberedSet> anticipatedIn;
691 DenseMap<BasicBlock*, ValueNumberedSet> generatedPhis;
Owen Anderson71fcebc2007-06-12 22:43:57 +0000692
Owen Anderson9cb56012007-06-21 00:19:05 +0000693 // This transformation requires dominator postdominator info
Owen Andersonea12a062007-05-29 21:53:49 +0000694 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
695 AU.setPreservesCFG();
Owen Anderson2c194e62007-07-06 18:12:36 +0000696 AU.addRequiredID(BreakCriticalEdgesID);
Owen Anderson2a5c9d82007-07-05 23:11:26 +0000697 AU.addRequired<UnifyFunctionExitNodes>();
Owen Andersonea12a062007-05-29 21:53:49 +0000698 AU.addRequired<DominatorTree>();
Owen Andersonea12a062007-05-29 21:53:49 +0000699 }
700
701 // Helper fuctions
702 // FIXME: eliminate or document these better
Owen Andersonb9eeb1a2007-07-09 07:56:55 +0000703 void dump(ValueNumberedSet& s) const ;
704 void clean(ValueNumberedSet& set) ;
705 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ;
706 Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) ;
Owen Anderson0616dff2007-07-09 06:50:06 +0000707 void phi_translate_set(ValueNumberedSet& anticIn, BasicBlock* pred,
Owen Andersonb9eeb1a2007-07-09 07:56:55 +0000708 BasicBlock* succ, ValueNumberedSet& out) ;
Owen Andersonea12a062007-05-29 21:53:49 +0000709
Owen Anderson0616dff2007-07-09 06:50:06 +0000710 void topo_sort(ValueNumberedSet& set,
Owen Anderson19bc4a82007-07-19 06:37:56 +0000711 SmallVector<Value*, 8>& vec) ;
Owen Anderson243f3482007-05-31 22:44:11 +0000712
Owen Andersonb9eeb1a2007-07-09 07:56:55 +0000713 void cleanup() ;
714 bool elimination() ;
Owen Andersonbbf11972007-06-18 04:42:29 +0000715
Owen Andersonb9eeb1a2007-07-09 07:56:55 +0000716 void val_insert(ValueNumberedSet& s, Value* v) ;
717 void val_replace(ValueNumberedSet& s, Value* v) ;
718 bool dependsOnInvoke(Value* V) ;
Owen Anderson3eaca712007-06-20 22:10:02 +0000719 void buildsets_availout(BasicBlock::iterator I,
Owen Anderson0616dff2007-07-09 06:50:06 +0000720 ValueNumberedSet& currAvail,
721 ValueNumberedSet& currPhis,
722 ValueNumberedSet& currExps,
Owen Anderson19bc4a82007-07-19 06:37:56 +0000723 SmallPtrSet<Value*, 16>& currTemps);
Owen Anderson82575d82007-06-22 00:20:30 +0000724 bool buildsets_anticout(BasicBlock* BB,
Owen Anderson0616dff2007-07-09 06:50:06 +0000725 ValueNumberedSet& anticOut,
Owen Anderson19bc4a82007-07-19 06:37:56 +0000726 SmallPtrSet<BasicBlock*, 8>& visited);
Owen Anderson82575d82007-06-22 00:20:30 +0000727 unsigned buildsets_anticin(BasicBlock* BB,
Owen Anderson0616dff2007-07-09 06:50:06 +0000728 ValueNumberedSet& anticOut,
729 ValueNumberedSet& currExps,
Owen Andersona20f35d2007-06-28 00:34:34 +0000730 SmallPtrSet<Value*, 16>& currTemps,
Owen Anderson19bc4a82007-07-19 06:37:56 +0000731 SmallPtrSet<BasicBlock*, 8>& visited);
Owen Andersonb9eeb1a2007-07-09 07:56:55 +0000732 void buildsets(Function& F) ;
Owen Anderson3eaca712007-06-20 22:10:02 +0000733
734 void insertion_pre(Value* e, BasicBlock* BB,
Owen Anderson19bc4a82007-07-19 06:37:56 +0000735 DenseMap<BasicBlock*, Value*>& avail,
736 std::map<BasicBlock*,ValueNumberedSet>& new_set);
737 unsigned insertion_mergepoint(SmallVector<Value*, 8>& workList,
Owen Anderson82575d82007-06-22 00:20:30 +0000738 df_iterator<DomTreeNode*>& D,
Owen Anderson19bc4a82007-07-19 06:37:56 +0000739 std::map<BasicBlock*, ValueNumberedSet>& new_set);
Owen Andersonb9eeb1a2007-07-09 07:56:55 +0000740 bool insertion(Function& F) ;
Owen Andersonea12a062007-05-29 21:53:49 +0000741
742 };
743
744 char GVNPRE::ID = 0;
745
746}
747
Owen Anderson9cb56012007-06-21 00:19:05 +0000748// createGVNPREPass - The public interface to this file...
Owen Andersonea12a062007-05-29 21:53:49 +0000749FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
750
Owen Anderson16a72bb2007-07-10 20:20:19 +0000751static RegisterPass<GVNPRE> X("gvnpre",
Owen Anderson9fed5892007-08-02 18:20:52 +0000752 "Global Value Numbering/Partial Redundancy Elimination");
Owen Andersonea12a062007-05-29 21:53:49 +0000753
Owen Andersonea12a062007-05-29 21:53:49 +0000754
Owen Andersonb8b873c2007-06-08 22:02:36 +0000755STATISTIC(NumInsertedVals, "Number of values inserted");
756STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
757STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
758
Owen Anderson9cb56012007-06-21 00:19:05 +0000759/// find_leader - Given a set and a value number, return the first
760/// element of the set with that value number, or 0 if no such element
761/// is present
Owen Anderson0616dff2007-07-09 06:50:06 +0000762Value* GVNPRE::find_leader(ValueNumberedSet& vals, uint32_t v) {
763 if (!vals.test(v))
764 return 0;
765
766 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
Owen Anderson086f5f32007-06-19 03:31:41 +0000767 I != E; ++I)
768 if (v == VN.lookup(*I))
Owen Andersona724ac12007-06-03 05:55:58 +0000769 return *I;
Owen Andersonea12a062007-05-29 21:53:49 +0000770
Torok Edwinc23197a2009-07-14 16:55:14 +0000771 llvm_unreachable("No leader found, but present bit is set?");
Owen Andersona724ac12007-06-03 05:55:58 +0000772 return 0;
Owen Andersonea12a062007-05-29 21:53:49 +0000773}
774
Owen Anderson9cb56012007-06-21 00:19:05 +0000775/// val_insert - Insert a value into a set only if there is not a value
776/// with the same value number already in the set
Owen Anderson0616dff2007-07-09 06:50:06 +0000777void GVNPRE::val_insert(ValueNumberedSet& s, Value* v) {
Owen Anderson086f5f32007-06-19 03:31:41 +0000778 uint32_t num = VN.lookup(v);
Owen Anderson0616dff2007-07-09 06:50:06 +0000779 if (!s.test(num))
Owen Anderson086f5f32007-06-19 03:31:41 +0000780 s.insert(v);
781}
782
Owen Anderson9cb56012007-06-21 00:19:05 +0000783/// val_replace - Insert a value into a set, replacing any values already in
784/// the set that have the same value number
Owen Anderson0616dff2007-07-09 06:50:06 +0000785void GVNPRE::val_replace(ValueNumberedSet& s, Value* v) {
Owen Andersonb83e56f2007-07-19 19:57:13 +0000786 if (s.count(v)) return;
787
Owen Anderson086f5f32007-06-19 03:31:41 +0000788 uint32_t num = VN.lookup(v);
789 Value* leader = find_leader(s, num);
Owen Andersondfa24352007-07-09 22:29:50 +0000790 if (leader != 0)
Owen Anderson086f5f32007-06-19 03:31:41 +0000791 s.erase(leader);
Owen Anderson086f5f32007-06-19 03:31:41 +0000792 s.insert(v);
Owen Andersondfa24352007-07-09 22:29:50 +0000793 s.set(num);
Owen Anderson086f5f32007-06-19 03:31:41 +0000794}
795
Owen Anderson9cb56012007-06-21 00:19:05 +0000796/// phi_translate - Given a value, its parent block, and a predecessor of its
797/// parent, translate the value into legal for the predecessor block. This
798/// means translating its operands (and recursively, their operands) through
799/// any phi nodes in the parent into values available in the predecessor
Owen Anderson71fcebc2007-06-12 22:43:57 +0000800Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
Owen Anderson5ea069f2007-06-04 18:05:26 +0000801 if (V == 0)
802 return 0;
Owen Andersone922c022009-07-22 00:24:57 +0000803
804 LLVMContext &Context = V->getContext();
Owen Anderson5ea069f2007-06-04 18:05:26 +0000805
Owen Anderson216394f2007-07-03 18:37:08 +0000806 // Unary Operations
Owen Anderson3d6fac32007-07-03 19:01:42 +0000807 if (CastInst* U = dyn_cast<CastInst>(V)) {
Owen Anderson216394f2007-07-03 18:37:08 +0000808 Value* newOp1 = 0;
809 if (isa<Instruction>(U->getOperand(0)))
810 newOp1 = phi_translate(U->getOperand(0), pred, succ);
811 else
812 newOp1 = U->getOperand(0);
813
814 if (newOp1 == 0)
815 return 0;
816
817 if (newOp1 != U->getOperand(0)) {
818 Instruction* newVal = 0;
819 if (CastInst* C = dyn_cast<CastInst>(U))
Gabor Greif7cbd8a32008-05-16 19:29:10 +0000820 newVal = CastInst::Create(C->getOpcode(),
Owen Anderson216394f2007-07-03 18:37:08 +0000821 newOp1, C->getType(),
822 C->getName()+".expr");
823
824 uint32_t v = VN.lookup_or_add(newVal);
825
826 Value* leader = find_leader(availableOut[pred], v);
827 if (leader == 0) {
828 createdExpressions.push_back(newVal);
829 return newVal;
830 } else {
831 VN.erase(newVal);
832 delete newVal;
833 return leader;
834 }
835 }
836
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000837 // Binary Operations
Owen Anderson216394f2007-07-03 18:37:08 +0000838 } if (isa<BinaryOperator>(V) || isa<CmpInst>(V) ||
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000839 isa<ExtractElementInst>(V)) {
Owen Andersonf62c44a2007-06-25 05:41:12 +0000840 User* U = cast<User>(V);
841
Owen Anderson086f5f32007-06-19 03:31:41 +0000842 Value* newOp1 = 0;
Owen Andersonf62c44a2007-06-25 05:41:12 +0000843 if (isa<Instruction>(U->getOperand(0)))
844 newOp1 = phi_translate(U->getOperand(0), pred, succ);
Owen Anderson086f5f32007-06-19 03:31:41 +0000845 else
Owen Andersonf62c44a2007-06-25 05:41:12 +0000846 newOp1 = U->getOperand(0);
Owen Anderson086f5f32007-06-19 03:31:41 +0000847
Owen Anderson5ea069f2007-06-04 18:05:26 +0000848 if (newOp1 == 0)
849 return 0;
850
Owen Anderson086f5f32007-06-19 03:31:41 +0000851 Value* newOp2 = 0;
Owen Andersonf62c44a2007-06-25 05:41:12 +0000852 if (isa<Instruction>(U->getOperand(1)))
853 newOp2 = phi_translate(U->getOperand(1), pred, succ);
Owen Anderson086f5f32007-06-19 03:31:41 +0000854 else
Owen Andersonf62c44a2007-06-25 05:41:12 +0000855 newOp2 = U->getOperand(1);
Owen Anderson086f5f32007-06-19 03:31:41 +0000856
Owen Anderson5ea069f2007-06-04 18:05:26 +0000857 if (newOp2 == 0)
858 return 0;
859
Owen Andersonf62c44a2007-06-25 05:41:12 +0000860 if (newOp1 != U->getOperand(0) || newOp2 != U->getOperand(1)) {
861 Instruction* newVal = 0;
862 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
Gabor Greif7cbd8a32008-05-16 19:29:10 +0000863 newVal = BinaryOperator::Create(BO->getOpcode(),
Owen Andersonf62c44a2007-06-25 05:41:12 +0000864 newOp1, newOp2,
865 BO->getName()+".expr");
866 else if (CmpInst* C = dyn_cast<CmpInst>(U))
Owen Andersone922c022009-07-22 00:24:57 +0000867 newVal = CmpInst::Create(Context, C->getOpcode(),
Owen Andersonf62c44a2007-06-25 05:41:12 +0000868 C->getPredicate(),
869 newOp1, newOp2,
870 C->getName()+".expr");
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000871 else if (ExtractElementInst* E = dyn_cast<ExtractElementInst>(U))
Eric Christophera3500da2009-07-25 02:28:41 +0000872 newVal = ExtractElementInst::Create(newOp1, newOp2, E->getName()+".expr");
Owen Anderson8338ff52007-06-08 20:44:02 +0000873
Owen Anderson086f5f32007-06-19 03:31:41 +0000874 uint32_t v = VN.lookup_or_add(newVal);
Owen Anderson71fcebc2007-06-12 22:43:57 +0000875
Owen Anderson086f5f32007-06-19 03:31:41 +0000876 Value* leader = find_leader(availableOut[pred], v);
Owen Anderson71fcebc2007-06-12 22:43:57 +0000877 if (leader == 0) {
Owen Anderson65d28622007-06-12 00:50:47 +0000878 createdExpressions.push_back(newVal);
Owen Anderson5ea069f2007-06-04 18:05:26 +0000879 return newVal;
Owen Anderson8f862c82007-06-05 22:11:49 +0000880 } else {
Owen Anderson20cb51f2007-06-19 05:37:32 +0000881 VN.erase(newVal);
Owen Anderson8f862c82007-06-05 22:11:49 +0000882 delete newVal;
Owen Anderson71fcebc2007-06-12 22:43:57 +0000883 return leader;
Owen Anderson8f862c82007-06-05 22:11:49 +0000884 }
Owen Anderson5ea069f2007-06-04 18:05:26 +0000885 }
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000886
887 // Ternary Operations
Owen Anderson890e1a02007-06-28 23:51:21 +0000888 } else if (isa<ShuffleVectorInst>(V) || isa<InsertElementInst>(V) ||
889 isa<SelectInst>(V)) {
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000890 User* U = cast<User>(V);
891
892 Value* newOp1 = 0;
893 if (isa<Instruction>(U->getOperand(0)))
894 newOp1 = phi_translate(U->getOperand(0), pred, succ);
895 else
896 newOp1 = U->getOperand(0);
897
898 if (newOp1 == 0)
899 return 0;
900
901 Value* newOp2 = 0;
902 if (isa<Instruction>(U->getOperand(1)))
903 newOp2 = phi_translate(U->getOperand(1), pred, succ);
904 else
905 newOp2 = U->getOperand(1);
906
907 if (newOp2 == 0)
908 return 0;
909
910 Value* newOp3 = 0;
911 if (isa<Instruction>(U->getOperand(2)))
912 newOp3 = phi_translate(U->getOperand(2), pred, succ);
913 else
914 newOp3 = U->getOperand(2);
915
916 if (newOp3 == 0)
917 return 0;
918
919 if (newOp1 != U->getOperand(0) ||
920 newOp2 != U->getOperand(1) ||
921 newOp3 != U->getOperand(2)) {
922 Instruction* newVal = 0;
923 if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
924 newVal = new ShuffleVectorInst(newOp1, newOp2, newOp3,
Gabor Greifb1dbcd82008-05-15 10:04:30 +0000925 S->getName() + ".expr");
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000926 else if (InsertElementInst* I = dyn_cast<InsertElementInst>(U))
Gabor Greif051a9502008-04-06 20:25:17 +0000927 newVal = InsertElementInst::Create(newOp1, newOp2, newOp3,
Gabor Greifb1dbcd82008-05-15 10:04:30 +0000928 I->getName() + ".expr");
Owen Anderson890e1a02007-06-28 23:51:21 +0000929 else if (SelectInst* I = dyn_cast<SelectInst>(U))
Gabor Greifb1dbcd82008-05-15 10:04:30 +0000930 newVal = SelectInst::Create(newOp1, newOp2, newOp3,
931 I->getName() + ".expr");
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000932
933 uint32_t v = VN.lookup_or_add(newVal);
934
935 Value* leader = find_leader(availableOut[pred], v);
936 if (leader == 0) {
937 createdExpressions.push_back(newVal);
938 return newVal;
939 } else {
940 VN.erase(newVal);
941 delete newVal;
942 return leader;
943 }
944 }
945
Owen Anderson56533222007-07-03 23:51:19 +0000946 // Varargs operators
947 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
948 Value* newOp1 = 0;
949 if (isa<Instruction>(U->getPointerOperand()))
950 newOp1 = phi_translate(U->getPointerOperand(), pred, succ);
951 else
952 newOp1 = U->getPointerOperand();
953
954 if (newOp1 == 0)
955 return 0;
956
957 bool changed_idx = false;
Owen Anderson19bc4a82007-07-19 06:37:56 +0000958 SmallVector<Value*, 4> newIdx;
Owen Anderson56533222007-07-03 23:51:19 +0000959 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
960 I != E; ++I)
961 if (isa<Instruction>(*I)) {
962 Value* newVal = phi_translate(*I, pred, succ);
963 newIdx.push_back(newVal);
964 if (newVal != *I)
965 changed_idx = true;
966 } else {
967 newIdx.push_back(*I);
968 }
969
970 if (newOp1 != U->getPointerOperand() || changed_idx) {
Gabor Greif051a9502008-04-06 20:25:17 +0000971 Instruction* newVal =
972 GetElementPtrInst::Create(newOp1,
973 newIdx.begin(), newIdx.end(),
974 U->getName()+".expr");
Owen Anderson56533222007-07-03 23:51:19 +0000975
976 uint32_t v = VN.lookup_or_add(newVal);
977
978 Value* leader = find_leader(availableOut[pred], v);
979 if (leader == 0) {
980 createdExpressions.push_back(newVal);
981 return newVal;
982 } else {
983 VN.erase(newVal);
984 delete newVal;
985 return leader;
986 }
987 }
988
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000989 // PHI Nodes
Owen Anderson5ea069f2007-06-04 18:05:26 +0000990 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
Owen Anderson65d28622007-06-12 00:50:47 +0000991 if (P->getParent() == succ)
Owen Anderson5ea069f2007-06-04 18:05:26 +0000992 return P->getIncomingValueForBlock(pred);
993 }
994
995 return V;
996}
997
Owen Anderson9cb56012007-06-21 00:19:05 +0000998/// phi_translate_set - Perform phi translation on every element of a set
Owen Anderson0616dff2007-07-09 06:50:06 +0000999void GVNPRE::phi_translate_set(ValueNumberedSet& anticIn,
Owen Anderson65d28622007-06-12 00:50:47 +00001000 BasicBlock* pred, BasicBlock* succ,
Owen Anderson0616dff2007-07-09 06:50:06 +00001001 ValueNumberedSet& out) {
1002 for (ValueNumberedSet::iterator I = anticIn.begin(),
Owen Anderson5ea069f2007-06-04 18:05:26 +00001003 E = anticIn.end(); I != E; ++I) {
Owen Anderson71fcebc2007-06-12 22:43:57 +00001004 Value* V = phi_translate(*I, pred, succ);
Owen Anderson0616dff2007-07-09 06:50:06 +00001005 if (V != 0 && !out.test(VN.lookup_or_add(V))) {
Owen Anderson5ea069f2007-06-04 18:05:26 +00001006 out.insert(V);
Owen Anderson0616dff2007-07-09 06:50:06 +00001007 out.set(VN.lookup(V));
1008 }
Owen Andersonea12a062007-05-29 21:53:49 +00001009 }
1010}
1011
Owen Anderson9cb56012007-06-21 00:19:05 +00001012/// dependsOnInvoke - Test if a value has an phi node as an operand, any of
1013/// whose inputs is an invoke instruction. If this is true, we cannot safely
1014/// PRE the instruction or anything that depends on it.
Owen Andersonbbf11972007-06-18 04:42:29 +00001015bool GVNPRE::dependsOnInvoke(Value* V) {
Owen Anderson52471b12007-06-19 23:07:16 +00001016 if (PHINode* p = dyn_cast<PHINode>(V)) {
1017 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
1018 if (isa<InvokeInst>(*I))
Owen Andersonbbf11972007-06-18 04:42:29 +00001019 return true;
Owen Anderson52471b12007-06-19 23:07:16 +00001020 return false;
1021 } else {
1022 return false;
Owen Anderson32bc7892007-06-16 00:26:54 +00001023 }
Owen Anderson32bc7892007-06-16 00:26:54 +00001024}
1025
Owen Anderson9cb56012007-06-21 00:19:05 +00001026/// clean - Remove all non-opaque values from the set whose operands are not
1027/// themselves in the set, as well as all values that depend on invokes (see
1028/// above)
Owen Anderson0616dff2007-07-09 06:50:06 +00001029void GVNPRE::clean(ValueNumberedSet& set) {
Owen Anderson19bc4a82007-07-19 06:37:56 +00001030 SmallVector<Value*, 8> worklist;
Owen Andersone8138ff2007-06-22 00:43:22 +00001031 worklist.reserve(set.size());
Owen Anderson397d4052007-06-08 01:03:01 +00001032 topo_sort(set, worklist);
Owen Andersonea12a062007-05-29 21:53:49 +00001033
Owen Anderson397d4052007-06-08 01:03:01 +00001034 for (unsigned i = 0; i < worklist.size(); ++i) {
1035 Value* v = worklist[i];
Owen Andersonea12a062007-05-29 21:53:49 +00001036
Owen Anderson216394f2007-07-03 18:37:08 +00001037 // Handle unary ops
Owen Anderson3d6fac32007-07-03 19:01:42 +00001038 if (CastInst* U = dyn_cast<CastInst>(v)) {
Owen Anderson216394f2007-07-03 18:37:08 +00001039 bool lhsValid = !isa<Instruction>(U->getOperand(0));
Owen Anderson0616dff2007-07-09 06:50:06 +00001040 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
Owen Anderson216394f2007-07-03 18:37:08 +00001041 if (lhsValid)
1042 lhsValid = !dependsOnInvoke(U->getOperand(0));
1043
1044 if (!lhsValid) {
1045 set.erase(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001046 set.reset(VN.lookup(U));
Owen Anderson216394f2007-07-03 18:37:08 +00001047 }
1048
Owen Anderson7b317d22007-06-27 17:03:03 +00001049 // Handle binary ops
Owen Anderson216394f2007-07-03 18:37:08 +00001050 } else if (isa<BinaryOperator>(v) || isa<CmpInst>(v) ||
Owen Anderson7b317d22007-06-27 17:03:03 +00001051 isa<ExtractElementInst>(v)) {
1052 User* U = cast<User>(v);
1053
1054 bool lhsValid = !isa<Instruction>(U->getOperand(0));
Owen Anderson0616dff2007-07-09 06:50:06 +00001055 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
Owen Anderson60e17442007-06-18 04:30:44 +00001056 if (lhsValid)
Owen Anderson7b317d22007-06-27 17:03:03 +00001057 lhsValid = !dependsOnInvoke(U->getOperand(0));
Owen Andersona724ac12007-06-03 05:55:58 +00001058
Owen Anderson7b317d22007-06-27 17:03:03 +00001059 bool rhsValid = !isa<Instruction>(U->getOperand(1));
Owen Anderson0616dff2007-07-09 06:50:06 +00001060 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
Owen Anderson60e17442007-06-18 04:30:44 +00001061 if (rhsValid)
Owen Anderson7b317d22007-06-27 17:03:03 +00001062 rhsValid = !dependsOnInvoke(U->getOperand(1));
Owen Andersonea12a062007-05-29 21:53:49 +00001063
Owen Anderson68cb52e2007-06-27 17:38:29 +00001064 if (!lhsValid || !rhsValid) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001065 set.erase(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001066 set.reset(VN.lookup(U));
Owen Anderson68cb52e2007-06-27 17:38:29 +00001067 }
Owen Anderson139fe842007-06-09 18:35:31 +00001068
Owen Anderson7b317d22007-06-27 17:03:03 +00001069 // Handle ternary ops
Owen Anderson890e1a02007-06-28 23:51:21 +00001070 } else if (isa<ShuffleVectorInst>(v) || isa<InsertElementInst>(v) ||
1071 isa<SelectInst>(v)) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001072 User* U = cast<User>(v);
1073
1074 bool lhsValid = !isa<Instruction>(U->getOperand(0));
Owen Anderson0616dff2007-07-09 06:50:06 +00001075 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001076 if (lhsValid)
Owen Anderson7b317d22007-06-27 17:03:03 +00001077 lhsValid = !dependsOnInvoke(U->getOperand(0));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001078
Owen Anderson7b317d22007-06-27 17:03:03 +00001079 bool rhsValid = !isa<Instruction>(U->getOperand(1));
Owen Anderson0616dff2007-07-09 06:50:06 +00001080 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001081 if (rhsValid)
Owen Anderson7b317d22007-06-27 17:03:03 +00001082 rhsValid = !dependsOnInvoke(U->getOperand(1));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001083
Owen Anderson7b317d22007-06-27 17:03:03 +00001084 bool thirdValid = !isa<Instruction>(U->getOperand(2));
Owen Anderson0616dff2007-07-09 06:50:06 +00001085 thirdValid |= set.test(VN.lookup(U->getOperand(2)));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001086 if (thirdValid)
Owen Anderson7b317d22007-06-27 17:03:03 +00001087 thirdValid = !dependsOnInvoke(U->getOperand(2));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001088
Owen Anderson68cb52e2007-06-27 17:38:29 +00001089 if (!lhsValid || !rhsValid || !thirdValid) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001090 set.erase(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001091 set.reset(VN.lookup(U));
Owen Anderson68cb52e2007-06-27 17:38:29 +00001092 }
Owen Anderson56533222007-07-03 23:51:19 +00001093
1094 // Handle varargs ops
1095 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(v)) {
1096 bool ptrValid = !isa<Instruction>(U->getPointerOperand());
Owen Anderson0616dff2007-07-09 06:50:06 +00001097 ptrValid |= set.test(VN.lookup(U->getPointerOperand()));
Owen Anderson56533222007-07-03 23:51:19 +00001098 if (ptrValid)
1099 ptrValid = !dependsOnInvoke(U->getPointerOperand());
1100
1101 bool varValid = true;
1102 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
1103 I != E; ++I)
1104 if (varValid) {
Owen Anderson0616dff2007-07-09 06:50:06 +00001105 varValid &= !isa<Instruction>(*I) || set.test(VN.lookup(*I));
Owen Anderson56533222007-07-03 23:51:19 +00001106 varValid &= !dependsOnInvoke(*I);
1107 }
1108
1109 if (!ptrValid || !varValid) {
1110 set.erase(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001111 set.reset(VN.lookup(U));
Owen Anderson56533222007-07-03 23:51:19 +00001112 }
Owen Andersona724ac12007-06-03 05:55:58 +00001113 }
Owen Andersonea12a062007-05-29 21:53:49 +00001114 }
1115}
1116
Owen Anderson9cb56012007-06-21 00:19:05 +00001117/// topo_sort - Given a set of values, sort them by topological
1118/// order into the provided vector.
Owen Anderson19bc4a82007-07-19 06:37:56 +00001119void GVNPRE::topo_sort(ValueNumberedSet& set, SmallVector<Value*, 8>& vec) {
Owen Andersona20f35d2007-06-28 00:34:34 +00001120 SmallPtrSet<Value*, 16> visited;
Owen Anderson19bc4a82007-07-19 06:37:56 +00001121 SmallVector<Value*, 8> stack;
Owen Anderson0616dff2007-07-09 06:50:06 +00001122 for (ValueNumberedSet::iterator I = set.begin(), E = set.end();
Owen Anderson64758042007-06-22 21:31:16 +00001123 I != E; ++I) {
1124 if (visited.count(*I) == 0)
1125 stack.push_back(*I);
1126
1127 while (!stack.empty()) {
1128 Value* e = stack.back();
Owen Anderson216394f2007-07-03 18:37:08 +00001129
1130 // Handle unary ops
Owen Anderson3d6fac32007-07-03 19:01:42 +00001131 if (CastInst* U = dyn_cast<CastInst>(e)) {
Owen Anderson216394f2007-07-03 18:37:08 +00001132 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1133
1134 if (l != 0 && isa<Instruction>(l) &&
1135 visited.count(l) == 0)
1136 stack.push_back(l);
1137 else {
1138 vec.push_back(e);
1139 visited.insert(e);
1140 stack.pop_back();
1141 }
1142
Owen Anderson7b317d22007-06-27 17:03:03 +00001143 // Handle binary ops
Owen Anderson216394f2007-07-03 18:37:08 +00001144 } else if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
Owen Anderson7b317d22007-06-27 17:03:03 +00001145 isa<ExtractElementInst>(e)) {
1146 User* U = cast<User>(e);
1147 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1148 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
Owen Anderson64758042007-06-22 21:31:16 +00001149
1150 if (l != 0 && isa<Instruction>(l) &&
1151 visited.count(l) == 0)
1152 stack.push_back(l);
1153 else if (r != 0 && isa<Instruction>(r) &&
1154 visited.count(r) == 0)
1155 stack.push_back(r);
1156 else {
1157 vec.push_back(e);
1158 visited.insert(e);
1159 stack.pop_back();
1160 }
Owen Andersona724ac12007-06-03 05:55:58 +00001161
Owen Anderson7b317d22007-06-27 17:03:03 +00001162 // Handle ternary ops
Owen Anderson890e1a02007-06-28 23:51:21 +00001163 } else if (isa<InsertElementInst>(e) || isa<ShuffleVectorInst>(e) ||
1164 isa<SelectInst>(e)) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001165 User* U = cast<User>(e);
1166 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1167 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1168 Value* m = find_leader(set, VN.lookup(U->getOperand(2)));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001169
1170 if (l != 0 && isa<Instruction>(l) &&
1171 visited.count(l) == 0)
1172 stack.push_back(l);
1173 else if (r != 0 && isa<Instruction>(r) &&
1174 visited.count(r) == 0)
1175 stack.push_back(r);
1176 else if (m != 0 && isa<Instruction>(m) &&
1177 visited.count(m) == 0)
Owen Andersondf30b632007-07-04 18:26:18 +00001178 stack.push_back(m);
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001179 else {
1180 vec.push_back(e);
1181 visited.insert(e);
1182 stack.pop_back();
1183 }
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001184
Owen Anderson56533222007-07-03 23:51:19 +00001185 // Handle vararg ops
1186 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(e)) {
1187 Value* p = find_leader(set, VN.lookup(U->getPointerOperand()));
1188
1189 if (p != 0 && isa<Instruction>(p) &&
1190 visited.count(p) == 0)
1191 stack.push_back(p);
1192 else {
1193 bool push_va = false;
1194 for (GetElementPtrInst::op_iterator I = U->idx_begin(),
1195 E = U->idx_end(); I != E; ++I) {
1196 Value * v = find_leader(set, VN.lookup(*I));
1197 if (v != 0 && isa<Instruction>(v) && visited.count(v) == 0) {
1198 stack.push_back(v);
1199 push_va = true;
1200 }
1201 }
1202
1203 if (!push_va) {
1204 vec.push_back(e);
1205 visited.insert(e);
1206 stack.pop_back();
1207 }
1208 }
1209
Owen Anderson7b317d22007-06-27 17:03:03 +00001210 // Handle opaque ops
Owen Anderson64758042007-06-22 21:31:16 +00001211 } else {
Owen Andersona724ac12007-06-03 05:55:58 +00001212 visited.insert(e);
Owen Anderson139fe842007-06-09 18:35:31 +00001213 vec.push_back(e);
Owen Anderson64758042007-06-22 21:31:16 +00001214 stack.pop_back();
Owen Anderson139fe842007-06-09 18:35:31 +00001215 }
Owen Anderson243f3482007-05-31 22:44:11 +00001216 }
Owen Anderson64758042007-06-22 21:31:16 +00001217
1218 stack.clear();
Owen Anderson243f3482007-05-31 22:44:11 +00001219 }
1220}
1221
Owen Anderson9cb56012007-06-21 00:19:05 +00001222/// dump - Dump a set of values to standard error
Owen Anderson0616dff2007-07-09 06:50:06 +00001223void GVNPRE::dump(ValueNumberedSet& s) const {
Owen Andersoncdf8efd2007-05-29 23:15:21 +00001224 DOUT << "{ ";
Owen Anderson0616dff2007-07-09 06:50:06 +00001225 for (ValueNumberedSet::iterator I = s.begin(), E = s.end();
Owen Anderson0fa6b372007-06-03 22:02:14 +00001226 I != E; ++I) {
Owen Anderson890e1a02007-06-28 23:51:21 +00001227 DOUT << "" << VN.lookup(*I) << ": ";
Owen Anderson0fa6b372007-06-03 22:02:14 +00001228 DEBUG((*I)->dump());
1229 }
1230 DOUT << "}\n\n";
1231}
1232
Owen Anderson9cb56012007-06-21 00:19:05 +00001233/// elimination - Phase 3 of the main algorithm. Perform full redundancy
1234/// elimination by walking the dominator tree and removing any instruction that
1235/// is dominated by another instruction with the same value number.
Owen Anderson3eaca712007-06-20 22:10:02 +00001236bool GVNPRE::elimination() {
Owen Anderson3eaca712007-06-20 22:10:02 +00001237 bool changed_function = false;
1238
Owen Anderson19bc4a82007-07-19 06:37:56 +00001239 SmallVector<std::pair<Instruction*, Value*>, 8> replace;
1240 SmallVector<Instruction*, 8> erase;
Owen Anderson239e7122007-06-12 16:57:50 +00001241
1242 DominatorTree& DT = getAnalysis<DominatorTree>();
1243
1244 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1245 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1246 BasicBlock* BB = DI->getBlock();
1247
Owen Anderson239e7122007-06-12 16:57:50 +00001248 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1249 BI != BE; ++BI) {
1250
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001251 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI) ||
1252 isa<ShuffleVectorInst>(BI) || isa<InsertElementInst>(BI) ||
Owen Anderson216394f2007-07-03 18:37:08 +00001253 isa<ExtractElementInst>(BI) || isa<SelectInst>(BI) ||
Owen Anderson56533222007-07-03 23:51:19 +00001254 isa<CastInst>(BI) || isa<GetElementPtrInst>(BI)) {
Owen Andersona05a81b2007-07-10 00:09:25 +00001255
Owen Anderson9fed5892007-08-02 18:20:52 +00001256 if (availableOut[BB].test(VN.lookup(BI)) &&
1257 !availableOut[BB].count(BI)) {
Owen Andersona05a81b2007-07-10 00:09:25 +00001258 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
Owen Anderson239e7122007-06-12 16:57:50 +00001259 if (Instruction* Instr = dyn_cast<Instruction>(leader))
1260 if (Instr->getParent() != 0 && Instr != BI) {
1261 replace.push_back(std::make_pair(BI, leader));
1262 erase.push_back(BI);
1263 ++NumEliminated;
1264 }
Owen Andersona05a81b2007-07-10 00:09:25 +00001265 }
Owen Anderson239e7122007-06-12 16:57:50 +00001266 }
1267 }
1268 }
1269
1270 while (!replace.empty()) {
1271 std::pair<Instruction*, Value*> rep = replace.back();
1272 replace.pop_back();
1273 rep.first->replaceAllUsesWith(rep.second);
Owen Anderson0304b2b2007-06-20 18:30:20 +00001274 changed_function = true;
Owen Anderson239e7122007-06-12 16:57:50 +00001275 }
1276
Owen Anderson9fed5892007-08-02 18:20:52 +00001277 for (SmallVector<Instruction*, 8>::iterator I = erase.begin(),
1278 E = erase.end(); I != E; ++I)
Owen Anderson239e7122007-06-12 16:57:50 +00001279 (*I)->eraseFromParent();
Owen Anderson3eaca712007-06-20 22:10:02 +00001280
1281 return changed_function;
Owen Anderson239e7122007-06-12 16:57:50 +00001282}
1283
Owen Anderson9cb56012007-06-21 00:19:05 +00001284/// cleanup - Delete any extraneous values that were created to represent
1285/// expressions without leaders.
Owen Anderson239e7122007-06-12 16:57:50 +00001286void GVNPRE::cleanup() {
1287 while (!createdExpressions.empty()) {
1288 Instruction* I = createdExpressions.back();
1289 createdExpressions.pop_back();
1290
1291 delete I;
1292 }
1293}
1294
Owen Anderson9cb56012007-06-21 00:19:05 +00001295/// buildsets_availout - When calculating availability, handle an instruction
1296/// by inserting it into the appropriate sets
Owen Anderson3eaca712007-06-20 22:10:02 +00001297void GVNPRE::buildsets_availout(BasicBlock::iterator I,
Owen Anderson0616dff2007-07-09 06:50:06 +00001298 ValueNumberedSet& currAvail,
1299 ValueNumberedSet& currPhis,
1300 ValueNumberedSet& currExps,
1301 SmallPtrSet<Value*, 16>& currTemps) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001302 // Handle PHI nodes
Owen Anderson3eaca712007-06-20 22:10:02 +00001303 if (PHINode* p = dyn_cast<PHINode>(I)) {
Owen Anderson0616dff2007-07-09 06:50:06 +00001304 unsigned num = VN.lookup_or_add(p);
Owen Anderson12408462007-06-22 03:14:03 +00001305
Owen Anderson3eaca712007-06-20 22:10:02 +00001306 currPhis.insert(p);
Owen Anderson0616dff2007-07-09 06:50:06 +00001307 currPhis.set(num);
Owen Anderson216394f2007-07-03 18:37:08 +00001308
1309 // Handle unary ops
Owen Anderson3d6fac32007-07-03 19:01:42 +00001310 } else if (CastInst* U = dyn_cast<CastInst>(I)) {
Owen Anderson216394f2007-07-03 18:37:08 +00001311 Value* leftValue = U->getOperand(0);
Owen Anderson3eaca712007-06-20 22:10:02 +00001312
Owen Anderson216394f2007-07-03 18:37:08 +00001313 unsigned num = VN.lookup_or_add(U);
Owen Anderson216394f2007-07-03 18:37:08 +00001314
1315 if (isa<Instruction>(leftValue))
Owen Anderson0616dff2007-07-09 06:50:06 +00001316 if (!currExps.test(VN.lookup(leftValue))) {
Owen Anderson216394f2007-07-03 18:37:08 +00001317 currExps.insert(leftValue);
Owen Anderson0616dff2007-07-09 06:50:06 +00001318 currExps.set(VN.lookup(leftValue));
Owen Anderson216394f2007-07-03 18:37:08 +00001319 }
1320
Owen Anderson0616dff2007-07-09 06:50:06 +00001321 if (!currExps.test(num)) {
Owen Anderson216394f2007-07-03 18:37:08 +00001322 currExps.insert(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001323 currExps.set(num);
Owen Anderson216394f2007-07-03 18:37:08 +00001324 }
1325
Owen Anderson7b317d22007-06-27 17:03:03 +00001326 // Handle binary ops
1327 } else if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
1328 isa<ExtractElementInst>(I)) {
1329 User* U = cast<User>(I);
1330 Value* leftValue = U->getOperand(0);
1331 Value* rightValue = U->getOperand(1);
Owen Anderson3eaca712007-06-20 22:10:02 +00001332
Owen Anderson7b317d22007-06-27 17:03:03 +00001333 unsigned num = VN.lookup_or_add(U);
Owen Anderson3eaca712007-06-20 22:10:02 +00001334
1335 if (isa<Instruction>(leftValue))
Owen Anderson0616dff2007-07-09 06:50:06 +00001336 if (!currExps.test(VN.lookup(leftValue))) {
Owen Anderson12408462007-06-22 03:14:03 +00001337 currExps.insert(leftValue);
Owen Anderson0616dff2007-07-09 06:50:06 +00001338 currExps.set(VN.lookup(leftValue));
Owen Anderson12408462007-06-22 03:14:03 +00001339 }
1340
Owen Anderson3eaca712007-06-20 22:10:02 +00001341 if (isa<Instruction>(rightValue))
Owen Anderson0616dff2007-07-09 06:50:06 +00001342 if (!currExps.test(VN.lookup(rightValue))) {
Owen Anderson12408462007-06-22 03:14:03 +00001343 currExps.insert(rightValue);
Owen Anderson0616dff2007-07-09 06:50:06 +00001344 currExps.set(VN.lookup(rightValue));
Owen Anderson12408462007-06-22 03:14:03 +00001345 }
1346
Owen Anderson0616dff2007-07-09 06:50:06 +00001347 if (!currExps.test(num)) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001348 currExps.insert(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001349 currExps.set(num);
Owen Anderson12408462007-06-22 03:14:03 +00001350 }
Owen Anderson3eaca712007-06-20 22:10:02 +00001351
Owen Anderson7b317d22007-06-27 17:03:03 +00001352 // Handle ternary ops
Owen Anderson890e1a02007-06-28 23:51:21 +00001353 } else if (isa<InsertElementInst>(I) || isa<ShuffleVectorInst>(I) ||
1354 isa<SelectInst>(I)) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001355 User* U = cast<User>(I);
1356 Value* leftValue = U->getOperand(0);
1357 Value* rightValue = U->getOperand(1);
1358 Value* thirdValue = U->getOperand(2);
Owen Anderson3eaca712007-06-20 22:10:02 +00001359
Owen Anderson7b317d22007-06-27 17:03:03 +00001360 VN.lookup_or_add(U);
Owen Anderson12408462007-06-22 03:14:03 +00001361
Owen Anderson7b317d22007-06-27 17:03:03 +00001362 unsigned num = VN.lookup_or_add(U);
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001363
1364 if (isa<Instruction>(leftValue))
Owen Anderson0616dff2007-07-09 06:50:06 +00001365 if (!currExps.test(VN.lookup(leftValue))) {
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001366 currExps.insert(leftValue);
Owen Anderson0616dff2007-07-09 06:50:06 +00001367 currExps.set(VN.lookup(leftValue));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001368 }
1369 if (isa<Instruction>(rightValue))
Owen Anderson0616dff2007-07-09 06:50:06 +00001370 if (!currExps.test(VN.lookup(rightValue))) {
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001371 currExps.insert(rightValue);
Owen Anderson0616dff2007-07-09 06:50:06 +00001372 currExps.set(VN.lookup(rightValue));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001373 }
1374 if (isa<Instruction>(thirdValue))
Owen Anderson0616dff2007-07-09 06:50:06 +00001375 if (!currExps.test(VN.lookup(thirdValue))) {
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001376 currExps.insert(thirdValue);
Owen Anderson0616dff2007-07-09 06:50:06 +00001377 currExps.set(VN.lookup(thirdValue));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001378 }
1379
Owen Anderson0616dff2007-07-09 06:50:06 +00001380 if (!currExps.test(num)) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001381 currExps.insert(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001382 currExps.set(num);
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001383 }
1384
Owen Anderson56533222007-07-03 23:51:19 +00001385 // Handle vararg ops
1386 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(I)) {
1387 Value* ptrValue = U->getPointerOperand();
1388
1389 VN.lookup_or_add(U);
1390
1391 unsigned num = VN.lookup_or_add(U);
Owen Anderson56533222007-07-03 23:51:19 +00001392
1393 if (isa<Instruction>(ptrValue))
Owen Anderson0616dff2007-07-09 06:50:06 +00001394 if (!currExps.test(VN.lookup(ptrValue))) {
Owen Anderson56533222007-07-03 23:51:19 +00001395 currExps.insert(ptrValue);
Owen Anderson0616dff2007-07-09 06:50:06 +00001396 currExps.set(VN.lookup(ptrValue));
Owen Anderson56533222007-07-03 23:51:19 +00001397 }
1398
1399 for (GetElementPtrInst::op_iterator OI = U->idx_begin(), OE = U->idx_end();
1400 OI != OE; ++OI)
Owen Anderson0616dff2007-07-09 06:50:06 +00001401 if (isa<Instruction>(*OI) && !currExps.test(VN.lookup(*OI))) {
Owen Anderson56533222007-07-03 23:51:19 +00001402 currExps.insert(*OI);
Owen Anderson0616dff2007-07-09 06:50:06 +00001403 currExps.set(VN.lookup(*OI));
Owen Anderson56533222007-07-03 23:51:19 +00001404 }
1405
Owen Anderson0616dff2007-07-09 06:50:06 +00001406 if (!currExps.test(VN.lookup(U))) {
Owen Anderson56533222007-07-03 23:51:19 +00001407 currExps.insert(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001408 currExps.set(num);
Owen Anderson56533222007-07-03 23:51:19 +00001409 }
1410
Owen Anderson7b317d22007-06-27 17:03:03 +00001411 // Handle opaque ops
1412 } else if (!I->isTerminator()){
Owen Anderson3eaca712007-06-20 22:10:02 +00001413 VN.lookup_or_add(I);
Owen Anderson12408462007-06-22 03:14:03 +00001414
Owen Anderson3eaca712007-06-20 22:10:02 +00001415 currTemps.insert(I);
1416 }
1417
1418 if (!I->isTerminator())
Owen Anderson0616dff2007-07-09 06:50:06 +00001419 if (!currAvail.test(VN.lookup(I))) {
Owen Anderson12408462007-06-22 03:14:03 +00001420 currAvail.insert(I);
Owen Anderson0616dff2007-07-09 06:50:06 +00001421 currAvail.set(VN.lookup(I));
Owen Anderson12408462007-06-22 03:14:03 +00001422 }
Owen Anderson3eaca712007-06-20 22:10:02 +00001423}
Owen Andersonea12a062007-05-29 21:53:49 +00001424
Owen Anderson9cb56012007-06-21 00:19:05 +00001425/// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
1426/// set as a function of the ANTIC_IN set of the block's predecessors
Owen Anderson82575d82007-06-22 00:20:30 +00001427bool GVNPRE::buildsets_anticout(BasicBlock* BB,
Owen Anderson0616dff2007-07-09 06:50:06 +00001428 ValueNumberedSet& anticOut,
Owen Andersonb9781982007-07-19 03:32:44 +00001429 SmallPtrSet<BasicBlock*, 8>& visited) {
Owen Anderson3eaca712007-06-20 22:10:02 +00001430 if (BB->getTerminator()->getNumSuccessors() == 1) {
Owen Andersonf62c44a2007-06-25 05:41:12 +00001431 if (BB->getTerminator()->getSuccessor(0) != BB &&
1432 visited.count(BB->getTerminator()->getSuccessor(0)) == 0) {
Owen Anderson82575d82007-06-22 00:20:30 +00001433 return true;
Owen Andersonf62c44a2007-06-25 05:41:12 +00001434 }
1435 else {
Owen Anderson3eaca712007-06-20 22:10:02 +00001436 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
1437 BB, BB->getTerminator()->getSuccessor(0), anticOut);
Owen Andersonf62c44a2007-06-25 05:41:12 +00001438 }
Owen Anderson3eaca712007-06-20 22:10:02 +00001439 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
1440 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
Owen Anderson0616dff2007-07-09 06:50:06 +00001441 for (ValueNumberedSet::iterator I = anticipatedIn[first].begin(),
1442 E = anticipatedIn[first].end(); I != E; ++I) {
1443 anticOut.insert(*I);
1444 anticOut.set(VN.lookup(*I));
1445 }
Owen Anderson3eaca712007-06-20 22:10:02 +00001446
1447 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
1448 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
Owen Anderson0616dff2007-07-09 06:50:06 +00001449 ValueNumberedSet& succAnticIn = anticipatedIn[currSucc];
Owen Anderson3eaca712007-06-20 22:10:02 +00001450
Owen Anderson19bc4a82007-07-19 06:37:56 +00001451 SmallVector<Value*, 16> temp;
Owen Anderson66fd9062007-06-21 17:57:53 +00001452
Owen Anderson0616dff2007-07-09 06:50:06 +00001453 for (ValueNumberedSet::iterator I = anticOut.begin(),
Owen Anderson66fd9062007-06-21 17:57:53 +00001454 E = anticOut.end(); I != E; ++I)
Owen Anderson0616dff2007-07-09 06:50:06 +00001455 if (!succAnticIn.test(VN.lookup(*I)))
Owen Anderson66fd9062007-06-21 17:57:53 +00001456 temp.push_back(*I);
1457
Owen Anderson19bc4a82007-07-19 06:37:56 +00001458 for (SmallVector<Value*, 16>::iterator I = temp.begin(), E = temp.end();
Owen Anderson0616dff2007-07-09 06:50:06 +00001459 I != E; ++I) {
Owen Anderson66fd9062007-06-21 17:57:53 +00001460 anticOut.erase(*I);
Owen Anderson0616dff2007-07-09 06:50:06 +00001461 anticOut.reset(VN.lookup(*I));
1462 }
Owen Anderson3eaca712007-06-20 22:10:02 +00001463 }
1464 }
Owen Anderson82575d82007-06-22 00:20:30 +00001465
1466 return false;
Owen Anderson3eaca712007-06-20 22:10:02 +00001467}
1468
Owen Anderson9cb56012007-06-21 00:19:05 +00001469/// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
1470/// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN
1471/// sets populated in buildsets_availout
Owen Anderson82575d82007-06-22 00:20:30 +00001472unsigned GVNPRE::buildsets_anticin(BasicBlock* BB,
Owen Anderson0616dff2007-07-09 06:50:06 +00001473 ValueNumberedSet& anticOut,
1474 ValueNumberedSet& currExps,
Owen Andersona20f35d2007-06-28 00:34:34 +00001475 SmallPtrSet<Value*, 16>& currTemps,
Owen Andersonb9781982007-07-19 03:32:44 +00001476 SmallPtrSet<BasicBlock*, 8>& visited) {
Owen Anderson0616dff2007-07-09 06:50:06 +00001477 ValueNumberedSet& anticIn = anticipatedIn[BB];
Owen Anderson2106f612007-06-22 18:27:04 +00001478 unsigned old = anticIn.size();
Owen Anderson3eaca712007-06-20 22:10:02 +00001479
Owen Anderson82575d82007-06-22 00:20:30 +00001480 bool defer = buildsets_anticout(BB, anticOut, visited);
1481 if (defer)
1482 return 0;
Owen Anderson66fd9062007-06-21 17:57:53 +00001483
Owen Anderson3eaca712007-06-20 22:10:02 +00001484 anticIn.clear();
Owen Anderson66fd9062007-06-21 17:57:53 +00001485
Owen Anderson0616dff2007-07-09 06:50:06 +00001486 for (ValueNumberedSet::iterator I = anticOut.begin(),
Owen Anderson2106f612007-06-22 18:27:04 +00001487 E = anticOut.end(); I != E; ++I) {
Owen Anderson0616dff2007-07-09 06:50:06 +00001488 anticIn.insert(*I);
1489 anticIn.set(VN.lookup(*I));
Owen Anderson3eaca712007-06-20 22:10:02 +00001490 }
Owen Anderson0616dff2007-07-09 06:50:06 +00001491 for (ValueNumberedSet::iterator I = currExps.begin(),
Owen Anderson2106f612007-06-22 18:27:04 +00001492 E = currExps.end(); I != E; ++I) {
Owen Anderson0616dff2007-07-09 06:50:06 +00001493 if (!anticIn.test(VN.lookup(*I))) {
Owen Anderson2106f612007-06-22 18:27:04 +00001494 anticIn.insert(*I);
Owen Anderson0616dff2007-07-09 06:50:06 +00001495 anticIn.set(VN.lookup(*I));
Owen Anderson2106f612007-06-22 18:27:04 +00001496 }
1497 }
1498
Owen Andersona20f35d2007-06-28 00:34:34 +00001499 for (SmallPtrSet<Value*, 16>::iterator I = currTemps.begin(),
Owen Anderson68cb52e2007-06-27 17:38:29 +00001500 E = currTemps.end(); I != E; ++I) {
Owen Anderson2106f612007-06-22 18:27:04 +00001501 anticIn.erase(*I);
Owen Anderson0616dff2007-07-09 06:50:06 +00001502 anticIn.reset(VN.lookup(*I));
Owen Anderson68cb52e2007-06-27 17:38:29 +00001503 }
Owen Anderson2106f612007-06-22 18:27:04 +00001504
Owen Anderson0616dff2007-07-09 06:50:06 +00001505 clean(anticIn);
Owen Anderson68cb52e2007-06-27 17:38:29 +00001506 anticOut.clear();
Owen Anderson3eaca712007-06-20 22:10:02 +00001507
Owen Anderson68cb52e2007-06-27 17:38:29 +00001508 if (old != anticIn.size())
Owen Anderson82575d82007-06-22 00:20:30 +00001509 return 2;
Owen Anderson68cb52e2007-06-27 17:38:29 +00001510 else
Owen Anderson82575d82007-06-22 00:20:30 +00001511 return 1;
Owen Anderson3eaca712007-06-20 22:10:02 +00001512}
1513
Owen Anderson9cb56012007-06-21 00:19:05 +00001514/// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT
1515/// and the ANTIC_IN sets.
Owen Anderson6032a5b2007-06-26 23:29:41 +00001516void GVNPRE::buildsets(Function& F) {
Owen Andersonb9781982007-07-19 03:32:44 +00001517 DenseMap<BasicBlock*, ValueNumberedSet> generatedExpressions;
1518 DenseMap<BasicBlock*, SmallPtrSet<Value*, 16> > generatedTemporaries;
Owen Anderson3eaca712007-06-20 22:10:02 +00001519
Owen Andersonea12a062007-05-29 21:53:49 +00001520 DominatorTree &DT = getAnalysis<DominatorTree>();
1521
Owen Anderson12112af2007-06-06 01:27:49 +00001522 // Phase 1, Part 1: calculate AVAIL_OUT
Owen Andersonea12a062007-05-29 21:53:49 +00001523
1524 // Top-down walk of the dominator tree
Devang Patel26042422007-06-04 00:32:22 +00001525 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
Owen Andersonea12a062007-05-29 21:53:49 +00001526 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1527
1528 // Get the sets to update for this block
Owen Anderson0616dff2007-07-09 06:50:06 +00001529 ValueNumberedSet& currExps = generatedExpressions[DI->getBlock()];
1530 ValueNumberedSet& currPhis = generatedPhis[DI->getBlock()];
Owen Andersona20f35d2007-06-28 00:34:34 +00001531 SmallPtrSet<Value*, 16>& currTemps = generatedTemporaries[DI->getBlock()];
Owen Anderson0616dff2007-07-09 06:50:06 +00001532 ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
Owen Andersonea12a062007-05-29 21:53:49 +00001533
Owen Anderson086f5f32007-06-19 03:31:41 +00001534 BasicBlock* BB = DI->getBlock();
1535
1536 // A block inherits AVAIL_OUT from its dominator
Owen Andersondfa24352007-07-09 22:29:50 +00001537 if (DI->getIDom() != 0)
1538 currAvail = availableOut[DI->getIDom()->getBlock()];
Owen Anderson0616dff2007-07-09 06:50:06 +00001539
Owen Anderson086f5f32007-06-19 03:31:41 +00001540 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
Owen Anderson3eaca712007-06-20 22:10:02 +00001541 BI != BE; ++BI)
Owen Anderson12408462007-06-22 03:14:03 +00001542 buildsets_availout(BI, currAvail, currPhis, currExps,
Owen Anderson0616dff2007-07-09 06:50:06 +00001543 currTemps);
Owen Anderson086f5f32007-06-19 03:31:41 +00001544
Owen Andersonea12a062007-05-29 21:53:49 +00001545 }
Owen Andersonf62c44a2007-06-25 05:41:12 +00001546
1547 // Phase 1, Part 2: calculate ANTIC_IN
Owen Andersonea12a062007-05-29 21:53:49 +00001548
Owen Andersonb9781982007-07-19 03:32:44 +00001549 SmallPtrSet<BasicBlock*, 8> visited;
Owen Anderson6032a5b2007-06-26 23:29:41 +00001550 SmallPtrSet<BasicBlock*, 4> block_changed;
1551 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
1552 block_changed.insert(FI);
Owen Andersone3072b22007-05-29 23:26:30 +00001553
Owen Andersonea12a062007-05-29 21:53:49 +00001554 bool changed = true;
1555 unsigned iterations = 0;
Owen Anderson6032a5b2007-06-26 23:29:41 +00001556
Owen Andersonea12a062007-05-29 21:53:49 +00001557 while (changed) {
1558 changed = false;
Owen Anderson0616dff2007-07-09 06:50:06 +00001559 ValueNumberedSet anticOut;
Owen Andersonea12a062007-05-29 21:53:49 +00001560
Owen Anderson6032a5b2007-06-26 23:29:41 +00001561 // Postorder walk of the CFG
Owen Anderson9030d382007-06-25 18:25:31 +00001562 for (po_iterator<BasicBlock*> BBI = po_begin(&F.getEntryBlock()),
1563 BBE = po_end(&F.getEntryBlock()); BBI != BBE; ++BBI) {
Owen Andersonf62c44a2007-06-25 05:41:12 +00001564 BasicBlock* BB = *BBI;
Owen Anderson0e714662007-06-11 16:25:17 +00001565
Owen Anderson6032a5b2007-06-26 23:29:41 +00001566 if (block_changed.count(BB) != 0) {
1567 unsigned ret = buildsets_anticin(BB, anticOut,generatedExpressions[BB],
1568 generatedTemporaries[BB], visited);
Owen Anderson82575d82007-06-22 00:20:30 +00001569
Owen Anderson6032a5b2007-06-26 23:29:41 +00001570 if (ret == 0) {
1571 changed = true;
1572 continue;
1573 } else {
1574 visited.insert(BB);
1575
1576 if (ret == 2)
1577 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1578 PI != PE; ++PI) {
1579 block_changed.insert(*PI);
1580 }
1581 else
1582 block_changed.erase(BB);
1583
1584 changed |= (ret == 2);
Owen Andersonf62c44a2007-06-25 05:41:12 +00001585 }
Owen Anderson82575d82007-06-22 00:20:30 +00001586 }
Owen Andersonea12a062007-05-29 21:53:49 +00001587 }
Owen Anderson5ea069f2007-06-04 18:05:26 +00001588
Owen Andersonea12a062007-05-29 21:53:49 +00001589 iterations++;
1590 }
Owen Anderson3eaca712007-06-20 22:10:02 +00001591}
1592
Owen Anderson9cb56012007-06-21 00:19:05 +00001593/// insertion_pre - When a partial redundancy has been identified, eliminate it
1594/// by inserting appropriate values into the predecessors and a phi node in
1595/// the main block
Owen Anderson3eaca712007-06-20 22:10:02 +00001596void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
Owen Anderson19bc4a82007-07-19 06:37:56 +00001597 DenseMap<BasicBlock*, Value*>& avail,
Owen Anderson0616dff2007-07-09 06:50:06 +00001598 std::map<BasicBlock*, ValueNumberedSet>& new_sets) {
Owen Andersone922c022009-07-22 00:24:57 +00001599 LLVMContext &Context = e->getContext();
Owen Anderson3eaca712007-06-20 22:10:02 +00001600 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1601 Value* e2 = avail[*PI];
Owen Anderson0616dff2007-07-09 06:50:06 +00001602 if (!availableOut[*PI].test(VN.lookup(e2))) {
Owen Anderson3eaca712007-06-20 22:10:02 +00001603 User* U = cast<User>(e2);
1604
1605 Value* s1 = 0;
1606 if (isa<BinaryOperator>(U->getOperand(0)) ||
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001607 isa<CmpInst>(U->getOperand(0)) ||
1608 isa<ShuffleVectorInst>(U->getOperand(0)) ||
1609 isa<ExtractElementInst>(U->getOperand(0)) ||
Owen Anderson890e1a02007-06-28 23:51:21 +00001610 isa<InsertElementInst>(U->getOperand(0)) ||
Owen Anderson216394f2007-07-03 18:37:08 +00001611 isa<SelectInst>(U->getOperand(0)) ||
Owen Anderson56533222007-07-03 23:51:19 +00001612 isa<CastInst>(U->getOperand(0)) ||
1613 isa<GetElementPtrInst>(U->getOperand(0)))
Owen Anderson3eaca712007-06-20 22:10:02 +00001614 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1615 else
1616 s1 = U->getOperand(0);
1617
1618 Value* s2 = 0;
Owen Anderson216394f2007-07-03 18:37:08 +00001619
1620 if (isa<BinaryOperator>(U) ||
1621 isa<CmpInst>(U) ||
1622 isa<ShuffleVectorInst>(U) ||
1623 isa<ExtractElementInst>(U) ||
1624 isa<InsertElementInst>(U) ||
Anton Korobeynikov07e6e562008-02-20 11:26:25 +00001625 isa<SelectInst>(U)) {
Owen Anderson216394f2007-07-03 18:37:08 +00001626 if (isa<BinaryOperator>(U->getOperand(1)) ||
1627 isa<CmpInst>(U->getOperand(1)) ||
1628 isa<ShuffleVectorInst>(U->getOperand(1)) ||
1629 isa<ExtractElementInst>(U->getOperand(1)) ||
1630 isa<InsertElementInst>(U->getOperand(1)) ||
1631 isa<SelectInst>(U->getOperand(1)) ||
Owen Anderson56533222007-07-03 23:51:19 +00001632 isa<CastInst>(U->getOperand(1)) ||
1633 isa<GetElementPtrInst>(U->getOperand(1))) {
Owen Anderson216394f2007-07-03 18:37:08 +00001634 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1635 } else {
1636 s2 = U->getOperand(1);
1637 }
Anton Korobeynikov07e6e562008-02-20 11:26:25 +00001638 }
Owen Anderson7b317d22007-06-27 17:03:03 +00001639
1640 // Ternary Operators
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001641 Value* s3 = 0;
1642 if (isa<ShuffleVectorInst>(U) ||
Owen Anderson890e1a02007-06-28 23:51:21 +00001643 isa<InsertElementInst>(U) ||
Anton Korobeynikov07e6e562008-02-20 11:26:25 +00001644 isa<SelectInst>(U)) {
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001645 if (isa<BinaryOperator>(U->getOperand(2)) ||
1646 isa<CmpInst>(U->getOperand(2)) ||
1647 isa<ShuffleVectorInst>(U->getOperand(2)) ||
1648 isa<ExtractElementInst>(U->getOperand(2)) ||
Owen Anderson890e1a02007-06-28 23:51:21 +00001649 isa<InsertElementInst>(U->getOperand(2)) ||
Owen Anderson216394f2007-07-03 18:37:08 +00001650 isa<SelectInst>(U->getOperand(2)) ||
Owen Anderson56533222007-07-03 23:51:19 +00001651 isa<CastInst>(U->getOperand(2)) ||
1652 isa<GetElementPtrInst>(U->getOperand(2))) {
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001653 s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2)));
Owen Anderson216394f2007-07-03 18:37:08 +00001654 } else {
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001655 s3 = U->getOperand(2);
Owen Anderson216394f2007-07-03 18:37:08 +00001656 }
Anton Korobeynikov07e6e562008-02-20 11:26:25 +00001657 }
Owen Anderson3eaca712007-06-20 22:10:02 +00001658
Owen Anderson56533222007-07-03 23:51:19 +00001659 // Vararg operators
Owen Anderson19bc4a82007-07-19 06:37:56 +00001660 SmallVector<Value*, 4> sVarargs;
Owen Anderson56533222007-07-03 23:51:19 +00001661 if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U)) {
1662 for (GetElementPtrInst::op_iterator OI = G->idx_begin(),
1663 OE = G->idx_end(); OI != OE; ++OI) {
1664 if (isa<BinaryOperator>(*OI) ||
1665 isa<CmpInst>(*OI) ||
1666 isa<ShuffleVectorInst>(*OI) ||
1667 isa<ExtractElementInst>(*OI) ||
1668 isa<InsertElementInst>(*OI) ||
1669 isa<SelectInst>(*OI) ||
1670 isa<CastInst>(*OI) ||
1671 isa<GetElementPtrInst>(*OI)) {
1672 sVarargs.push_back(find_leader(availableOut[*PI],
1673 VN.lookup(*OI)));
1674 } else {
1675 sVarargs.push_back(*OI);
1676 }
1677 }
1678 }
1679
Owen Anderson3eaca712007-06-20 22:10:02 +00001680 Value* newVal = 0;
1681 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
Gabor Greif7cbd8a32008-05-16 19:29:10 +00001682 newVal = BinaryOperator::Create(BO->getOpcode(), s1, s2,
Owen Anderson3eaca712007-06-20 22:10:02 +00001683 BO->getName()+".gvnpre",
1684 (*PI)->getTerminator());
1685 else if (CmpInst* C = dyn_cast<CmpInst>(U))
Owen Andersone922c022009-07-22 00:24:57 +00001686 newVal = CmpInst::Create(Context, C->getOpcode(),
Owen Anderson333c4002009-07-09 23:48:35 +00001687 C->getPredicate(), s1, s2,
Owen Anderson3eaca712007-06-20 22:10:02 +00001688 C->getName()+".gvnpre",
1689 (*PI)->getTerminator());
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001690 else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
1691 newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre",
1692 (*PI)->getTerminator());
1693 else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U))
Gabor Greif051a9502008-04-06 20:25:17 +00001694 newVal = InsertElementInst::Create(s1, s2, s3, S->getName()+".gvnpre",
1695 (*PI)->getTerminator());
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001696 else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U))
Eric Christophera3500da2009-07-25 02:28:41 +00001697 newVal = ExtractElementInst::Create(s1, s2, S->getName()+".gvnpre",
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001698 (*PI)->getTerminator());
Owen Anderson890e1a02007-06-28 23:51:21 +00001699 else if (SelectInst* S = dyn_cast<SelectInst>(U))
Gabor Greif051a9502008-04-06 20:25:17 +00001700 newVal = SelectInst::Create(s1, s2, s3, S->getName()+".gvnpre",
1701 (*PI)->getTerminator());
Owen Anderson216394f2007-07-03 18:37:08 +00001702 else if (CastInst* C = dyn_cast<CastInst>(U))
Gabor Greif7cbd8a32008-05-16 19:29:10 +00001703 newVal = CastInst::Create(C->getOpcode(), s1, C->getType(),
Owen Anderson216394f2007-07-03 18:37:08 +00001704 C->getName()+".gvnpre",
1705 (*PI)->getTerminator());
Owen Anderson56533222007-07-03 23:51:19 +00001706 else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U))
Gabor Greif051a9502008-04-06 20:25:17 +00001707 newVal = GetElementPtrInst::Create(s1, sVarargs.begin(), sVarargs.end(),
1708 G->getName()+".gvnpre",
1709 (*PI)->getTerminator());
1710
Owen Anderson3eaca712007-06-20 22:10:02 +00001711 VN.add(newVal, VN.lookup(U));
1712
Owen Anderson0616dff2007-07-09 06:50:06 +00001713 ValueNumberedSet& predAvail = availableOut[*PI];
Owen Anderson3eaca712007-06-20 22:10:02 +00001714 val_replace(predAvail, newVal);
Owen Anderson2a5c9d82007-07-05 23:11:26 +00001715 val_replace(new_sets[*PI], newVal);
Owen Anderson0616dff2007-07-09 06:50:06 +00001716 predAvail.set(VN.lookup(newVal));
Owen Anderson9cb56012007-06-21 00:19:05 +00001717
Owen Anderson19bc4a82007-07-19 06:37:56 +00001718 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
Owen Anderson3eaca712007-06-20 22:10:02 +00001719 if (av != avail.end())
1720 avail.erase(av);
1721 avail.insert(std::make_pair(*PI, newVal));
1722
1723 ++NumInsertedVals;
1724 }
1725 }
1726
1727 PHINode* p = 0;
1728
1729 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1730 if (p == 0)
Gabor Greif051a9502008-04-06 20:25:17 +00001731 p = PHINode::Create(avail[*PI]->getType(), "gvnpre-join", BB->begin());
Owen Anderson2a5c9d82007-07-05 23:11:26 +00001732
Owen Anderson3eaca712007-06-20 22:10:02 +00001733 p->addIncoming(avail[*PI], *PI);
1734 }
1735
1736 VN.add(p, VN.lookup(e));
Owen Anderson3eaca712007-06-20 22:10:02 +00001737 val_replace(availableOut[BB], p);
Owen Anderson0616dff2007-07-09 06:50:06 +00001738 availableOut[BB].set(VN.lookup(e));
Owen Andersonec5614b2007-07-06 20:29:43 +00001739 generatedPhis[BB].insert(p);
Owen Anderson0616dff2007-07-09 06:50:06 +00001740 generatedPhis[BB].set(VN.lookup(e));
Owen Anderson2a5c9d82007-07-05 23:11:26 +00001741 new_sets[BB].insert(p);
Owen Anderson0616dff2007-07-09 06:50:06 +00001742 new_sets[BB].set(VN.lookup(e));
Owen Anderson3eaca712007-06-20 22:10:02 +00001743
1744 ++NumInsertedPhis;
1745}
1746
Owen Anderson9cb56012007-06-21 00:19:05 +00001747/// insertion_mergepoint - When walking the dom tree, check at each merge
1748/// block for the possibility of a partial redundancy. If present, eliminate it
Owen Anderson19bc4a82007-07-19 06:37:56 +00001749unsigned GVNPRE::insertion_mergepoint(SmallVector<Value*, 8>& workList,
Owen Anderson82575d82007-06-22 00:20:30 +00001750 df_iterator<DomTreeNode*>& D,
Owen Anderson0616dff2007-07-09 06:50:06 +00001751 std::map<BasicBlock*, ValueNumberedSet >& new_sets) {
Owen Anderson3eaca712007-06-20 22:10:02 +00001752 bool changed_function = false;
1753 bool new_stuff = false;
1754
1755 BasicBlock* BB = D->getBlock();
1756 for (unsigned i = 0; i < workList.size(); ++i) {
1757 Value* e = workList[i];
1758
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001759 if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1760 isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) ||
Owen Anderson56533222007-07-03 23:51:19 +00001761 isa<ShuffleVectorInst>(e) || isa<SelectInst>(e) || isa<CastInst>(e) ||
1762 isa<GetElementPtrInst>(e)) {
Owen Anderson0616dff2007-07-09 06:50:06 +00001763 if (availableOut[D->getIDom()->getBlock()].test(VN.lookup(e)))
Owen Anderson3eaca712007-06-20 22:10:02 +00001764 continue;
1765
Owen Anderson19bc4a82007-07-19 06:37:56 +00001766 DenseMap<BasicBlock*, Value*> avail;
Owen Anderson3eaca712007-06-20 22:10:02 +00001767 bool by_some = false;
Owen Andersonec5614b2007-07-06 20:29:43 +00001768 bool all_same = true;
1769 Value * first_s = 0;
Owen Anderson3eaca712007-06-20 22:10:02 +00001770
1771 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1772 ++PI) {
1773 Value *e2 = phi_translate(e, *PI, BB);
1774 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1775
1776 if (e3 == 0) {
Owen Anderson19bc4a82007-07-19 06:37:56 +00001777 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
Owen Anderson3eaca712007-06-20 22:10:02 +00001778 if (av != avail.end())
1779 avail.erase(av);
1780 avail.insert(std::make_pair(*PI, e2));
Owen Andersonec5614b2007-07-06 20:29:43 +00001781 all_same = false;
Owen Anderson3eaca712007-06-20 22:10:02 +00001782 } else {
Owen Anderson19bc4a82007-07-19 06:37:56 +00001783 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
Owen Anderson3eaca712007-06-20 22:10:02 +00001784 if (av != avail.end())
1785 avail.erase(av);
1786 avail.insert(std::make_pair(*PI, e3));
1787
1788 by_some = true;
Owen Andersonec5614b2007-07-06 20:29:43 +00001789 if (first_s == 0)
1790 first_s = e3;
1791 else if (first_s != e3)
1792 all_same = false;
Owen Anderson3eaca712007-06-20 22:10:02 +00001793 }
1794 }
1795
Owen Andersonec5614b2007-07-06 20:29:43 +00001796 if (by_some && !all_same &&
Owen Anderson0616dff2007-07-09 06:50:06 +00001797 !generatedPhis[BB].test(VN.lookup(e))) {
Owen Anderson2a5c9d82007-07-05 23:11:26 +00001798 insertion_pre(e, BB, avail, new_sets);
Owen Anderson3eaca712007-06-20 22:10:02 +00001799
1800 changed_function = true;
1801 new_stuff = true;
1802 }
1803 }
1804 }
1805
1806 unsigned retval = 0;
1807 if (changed_function)
1808 retval += 1;
1809 if (new_stuff)
1810 retval += 2;
1811
1812 return retval;
1813}
1814
Owen Anderson9cb56012007-06-21 00:19:05 +00001815/// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for
1816/// merge points. When one is found, check for a partial redundancy. If one is
1817/// present, eliminate it. Repeat this walk until no changes are made.
Owen Anderson3eaca712007-06-20 22:10:02 +00001818bool GVNPRE::insertion(Function& F) {
1819 bool changed_function = false;
1820
1821 DominatorTree &DT = getAnalysis<DominatorTree>();
Owen Anderson397d4052007-06-08 01:03:01 +00001822
Owen Anderson0616dff2007-07-09 06:50:06 +00001823 std::map<BasicBlock*, ValueNumberedSet> new_sets;
Owen Anderson397d4052007-06-08 01:03:01 +00001824 bool new_stuff = true;
1825 while (new_stuff) {
1826 new_stuff = false;
Owen Anderson397d4052007-06-08 01:03:01 +00001827 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1828 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1829 BasicBlock* BB = DI->getBlock();
1830
Owen Anderson0e714662007-06-11 16:25:17 +00001831 if (BB == 0)
1832 continue;
1833
Owen Anderson0616dff2007-07-09 06:50:06 +00001834 ValueNumberedSet& availOut = availableOut[BB];
1835 ValueNumberedSet& anticIn = anticipatedIn[BB];
Owen Anderson397d4052007-06-08 01:03:01 +00001836
1837 // Replace leaders with leaders inherited from dominator
1838 if (DI->getIDom() != 0) {
Owen Anderson0616dff2007-07-09 06:50:06 +00001839 ValueNumberedSet& dom_set = new_sets[DI->getIDom()->getBlock()];
1840 for (ValueNumberedSet::iterator I = dom_set.begin(),
Owen Anderson397d4052007-06-08 01:03:01 +00001841 E = dom_set.end(); I != E; ++I) {
Owen Anderson2a5c9d82007-07-05 23:11:26 +00001842 val_replace(new_sets[BB], *I);
Owen Anderson086f5f32007-06-19 03:31:41 +00001843 val_replace(availOut, *I);
Owen Anderson397d4052007-06-08 01:03:01 +00001844 }
1845 }
1846
1847 // If there is more than one predecessor...
1848 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
Owen Anderson19bc4a82007-07-19 06:37:56 +00001849 SmallVector<Value*, 8> workList;
Owen Andersone8138ff2007-06-22 00:43:22 +00001850 workList.reserve(anticIn.size());
Owen Anderson397d4052007-06-08 01:03:01 +00001851 topo_sort(anticIn, workList);
1852
Owen Anderson2a5c9d82007-07-05 23:11:26 +00001853 unsigned result = insertion_mergepoint(workList, DI, new_sets);
Owen Anderson3eaca712007-06-20 22:10:02 +00001854 if (result & 1)
1855 changed_function = true;
1856 if (result & 2)
1857 new_stuff = true;
Owen Anderson397d4052007-06-08 01:03:01 +00001858 }
1859 }
Owen Anderson397d4052007-06-08 01:03:01 +00001860 }
Owen Anderson12112af2007-06-06 01:27:49 +00001861
Owen Anderson3eaca712007-06-20 22:10:02 +00001862 return changed_function;
1863}
1864
Owen Anderson9cb56012007-06-21 00:19:05 +00001865// GVNPRE::runOnFunction - This is the main transformation entry point for a
1866// function.
1867//
Owen Anderson3eaca712007-06-20 22:10:02 +00001868bool GVNPRE::runOnFunction(Function &F) {
Owen Anderson9cb56012007-06-21 00:19:05 +00001869 // Clean out global sets from any previous functions
Owen Anderson3eaca712007-06-20 22:10:02 +00001870 VN.clear();
1871 createdExpressions.clear();
1872 availableOut.clear();
1873 anticipatedIn.clear();
Owen Andersonec5614b2007-07-06 20:29:43 +00001874 generatedPhis.clear();
1875
Owen Anderson3eaca712007-06-20 22:10:02 +00001876 bool changed_function = false;
1877
1878 // Phase 1: BuildSets
Owen Anderson9cb56012007-06-21 00:19:05 +00001879 // This phase calculates the AVAIL_OUT and ANTIC_IN sets
Owen Anderson6032a5b2007-06-26 23:29:41 +00001880 buildsets(F);
Owen Anderson3eaca712007-06-20 22:10:02 +00001881
1882 // Phase 2: Insert
Owen Anderson9cb56012007-06-21 00:19:05 +00001883 // This phase inserts values to make partially redundant values
1884 // fully redundant
Owen Anderson3eaca712007-06-20 22:10:02 +00001885 changed_function |= insertion(F);
1886
Owen Anderson12112af2007-06-06 01:27:49 +00001887 // Phase 3: Eliminate
Owen Anderson9cb56012007-06-21 00:19:05 +00001888 // This phase performs trivial full redundancy elimination
Owen Anderson3eaca712007-06-20 22:10:02 +00001889 changed_function |= elimination();
Owen Anderson8338ff52007-06-08 20:44:02 +00001890
Owen Anderson397d4052007-06-08 01:03:01 +00001891 // Phase 4: Cleanup
Owen Anderson9cb56012007-06-21 00:19:05 +00001892 // This phase cleans up values that were created solely
1893 // as leaders for expressions
Owen Anderson239e7122007-06-12 16:57:50 +00001894 cleanup();
Owen Anderson397d4052007-06-08 01:03:01 +00001895
Owen Anderson0304b2b2007-06-20 18:30:20 +00001896 return changed_function;
Owen Andersonea12a062007-05-29 21:53:49 +00001897}