blob: bb5686704cf6ad74db9af8c605cabc99089a6f4a [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))
Dan Gohman1c8a23c2009-08-25 23:17:54 +0000867 newVal = CmpInst::Create(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))
Daniel Dunbar6e0d1cb2009-07-25 04:41:11 +0000872 newVal = ExtractElementInst::Create(newOp1, newOp2,
873 E->getName()+".expr");
Owen Anderson8338ff52007-06-08 20:44:02 +0000874
Owen Anderson086f5f32007-06-19 03:31:41 +0000875 uint32_t v = VN.lookup_or_add(newVal);
Owen Anderson71fcebc2007-06-12 22:43:57 +0000876
Owen Anderson086f5f32007-06-19 03:31:41 +0000877 Value* leader = find_leader(availableOut[pred], v);
Owen Anderson71fcebc2007-06-12 22:43:57 +0000878 if (leader == 0) {
Owen Anderson65d28622007-06-12 00:50:47 +0000879 createdExpressions.push_back(newVal);
Owen Anderson5ea069f2007-06-04 18:05:26 +0000880 return newVal;
Owen Anderson8f862c82007-06-05 22:11:49 +0000881 } else {
Owen Anderson20cb51f2007-06-19 05:37:32 +0000882 VN.erase(newVal);
Owen Anderson8f862c82007-06-05 22:11:49 +0000883 delete newVal;
Owen Anderson71fcebc2007-06-12 22:43:57 +0000884 return leader;
Owen Anderson8f862c82007-06-05 22:11:49 +0000885 }
Owen Anderson5ea069f2007-06-04 18:05:26 +0000886 }
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000887
888 // Ternary Operations
Owen Anderson890e1a02007-06-28 23:51:21 +0000889 } else if (isa<ShuffleVectorInst>(V) || isa<InsertElementInst>(V) ||
890 isa<SelectInst>(V)) {
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000891 User* U = cast<User>(V);
892
893 Value* newOp1 = 0;
894 if (isa<Instruction>(U->getOperand(0)))
895 newOp1 = phi_translate(U->getOperand(0), pred, succ);
896 else
897 newOp1 = U->getOperand(0);
898
899 if (newOp1 == 0)
900 return 0;
901
902 Value* newOp2 = 0;
903 if (isa<Instruction>(U->getOperand(1)))
904 newOp2 = phi_translate(U->getOperand(1), pred, succ);
905 else
906 newOp2 = U->getOperand(1);
907
908 if (newOp2 == 0)
909 return 0;
910
911 Value* newOp3 = 0;
912 if (isa<Instruction>(U->getOperand(2)))
913 newOp3 = phi_translate(U->getOperand(2), pred, succ);
914 else
915 newOp3 = U->getOperand(2);
916
917 if (newOp3 == 0)
918 return 0;
919
920 if (newOp1 != U->getOperand(0) ||
921 newOp2 != U->getOperand(1) ||
922 newOp3 != U->getOperand(2)) {
923 Instruction* newVal = 0;
924 if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
925 newVal = new ShuffleVectorInst(newOp1, newOp2, newOp3,
Gabor Greifb1dbcd82008-05-15 10:04:30 +0000926 S->getName() + ".expr");
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000927 else if (InsertElementInst* I = dyn_cast<InsertElementInst>(U))
Gabor Greif051a9502008-04-06 20:25:17 +0000928 newVal = InsertElementInst::Create(newOp1, newOp2, newOp3,
Gabor Greifb1dbcd82008-05-15 10:04:30 +0000929 I->getName() + ".expr");
Owen Anderson890e1a02007-06-28 23:51:21 +0000930 else if (SelectInst* I = dyn_cast<SelectInst>(U))
Gabor Greifb1dbcd82008-05-15 10:04:30 +0000931 newVal = SelectInst::Create(newOp1, newOp2, newOp3,
932 I->getName() + ".expr");
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000933
934 uint32_t v = VN.lookup_or_add(newVal);
935
936 Value* leader = find_leader(availableOut[pred], v);
937 if (leader == 0) {
938 createdExpressions.push_back(newVal);
939 return newVal;
940 } else {
941 VN.erase(newVal);
942 delete newVal;
943 return leader;
944 }
945 }
946
Owen Anderson56533222007-07-03 23:51:19 +0000947 // Varargs operators
948 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
949 Value* newOp1 = 0;
950 if (isa<Instruction>(U->getPointerOperand()))
951 newOp1 = phi_translate(U->getPointerOperand(), pred, succ);
952 else
953 newOp1 = U->getPointerOperand();
954
955 if (newOp1 == 0)
956 return 0;
957
958 bool changed_idx = false;
Owen Anderson19bc4a82007-07-19 06:37:56 +0000959 SmallVector<Value*, 4> newIdx;
Owen Anderson56533222007-07-03 23:51:19 +0000960 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
961 I != E; ++I)
962 if (isa<Instruction>(*I)) {
963 Value* newVal = phi_translate(*I, pred, succ);
964 newIdx.push_back(newVal);
965 if (newVal != *I)
966 changed_idx = true;
967 } else {
968 newIdx.push_back(*I);
969 }
970
971 if (newOp1 != U->getPointerOperand() || changed_idx) {
Gabor Greif051a9502008-04-06 20:25:17 +0000972 Instruction* newVal =
973 GetElementPtrInst::Create(newOp1,
974 newIdx.begin(), newIdx.end(),
975 U->getName()+".expr");
Owen Anderson56533222007-07-03 23:51:19 +0000976
977 uint32_t v = VN.lookup_or_add(newVal);
978
979 Value* leader = find_leader(availableOut[pred], v);
980 if (leader == 0) {
981 createdExpressions.push_back(newVal);
982 return newVal;
983 } else {
984 VN.erase(newVal);
985 delete newVal;
986 return leader;
987 }
988 }
989
Owen Anderson62cf8ba2007-06-27 04:10:46 +0000990 // PHI Nodes
Owen Anderson5ea069f2007-06-04 18:05:26 +0000991 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
Owen Anderson65d28622007-06-12 00:50:47 +0000992 if (P->getParent() == succ)
Owen Anderson5ea069f2007-06-04 18:05:26 +0000993 return P->getIncomingValueForBlock(pred);
994 }
995
996 return V;
997}
998
Owen Anderson9cb56012007-06-21 00:19:05 +0000999/// phi_translate_set - Perform phi translation on every element of a set
Owen Anderson0616dff2007-07-09 06:50:06 +00001000void GVNPRE::phi_translate_set(ValueNumberedSet& anticIn,
Owen Anderson65d28622007-06-12 00:50:47 +00001001 BasicBlock* pred, BasicBlock* succ,
Owen Anderson0616dff2007-07-09 06:50:06 +00001002 ValueNumberedSet& out) {
1003 for (ValueNumberedSet::iterator I = anticIn.begin(),
Owen Anderson5ea069f2007-06-04 18:05:26 +00001004 E = anticIn.end(); I != E; ++I) {
Owen Anderson71fcebc2007-06-12 22:43:57 +00001005 Value* V = phi_translate(*I, pred, succ);
Owen Anderson0616dff2007-07-09 06:50:06 +00001006 if (V != 0 && !out.test(VN.lookup_or_add(V))) {
Owen Anderson5ea069f2007-06-04 18:05:26 +00001007 out.insert(V);
Owen Anderson0616dff2007-07-09 06:50:06 +00001008 out.set(VN.lookup(V));
1009 }
Owen Andersonea12a062007-05-29 21:53:49 +00001010 }
1011}
1012
Owen Anderson9cb56012007-06-21 00:19:05 +00001013/// dependsOnInvoke - Test if a value has an phi node as an operand, any of
1014/// whose inputs is an invoke instruction. If this is true, we cannot safely
1015/// PRE the instruction or anything that depends on it.
Owen Andersonbbf11972007-06-18 04:42:29 +00001016bool GVNPRE::dependsOnInvoke(Value* V) {
Owen Anderson52471b12007-06-19 23:07:16 +00001017 if (PHINode* p = dyn_cast<PHINode>(V)) {
1018 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
1019 if (isa<InvokeInst>(*I))
Owen Andersonbbf11972007-06-18 04:42:29 +00001020 return true;
Owen Anderson52471b12007-06-19 23:07:16 +00001021 return false;
1022 } else {
1023 return false;
Owen Anderson32bc7892007-06-16 00:26:54 +00001024 }
Owen Anderson32bc7892007-06-16 00:26:54 +00001025}
1026
Owen Anderson9cb56012007-06-21 00:19:05 +00001027/// clean - Remove all non-opaque values from the set whose operands are not
1028/// themselves in the set, as well as all values that depend on invokes (see
1029/// above)
Owen Anderson0616dff2007-07-09 06:50:06 +00001030void GVNPRE::clean(ValueNumberedSet& set) {
Owen Anderson19bc4a82007-07-19 06:37:56 +00001031 SmallVector<Value*, 8> worklist;
Owen Andersone8138ff2007-06-22 00:43:22 +00001032 worklist.reserve(set.size());
Owen Anderson397d4052007-06-08 01:03:01 +00001033 topo_sort(set, worklist);
Owen Andersonea12a062007-05-29 21:53:49 +00001034
Owen Anderson397d4052007-06-08 01:03:01 +00001035 for (unsigned i = 0; i < worklist.size(); ++i) {
1036 Value* v = worklist[i];
Owen Andersonea12a062007-05-29 21:53:49 +00001037
Owen Anderson216394f2007-07-03 18:37:08 +00001038 // Handle unary ops
Owen Anderson3d6fac32007-07-03 19:01:42 +00001039 if (CastInst* U = dyn_cast<CastInst>(v)) {
Owen Anderson216394f2007-07-03 18:37:08 +00001040 bool lhsValid = !isa<Instruction>(U->getOperand(0));
Owen Anderson0616dff2007-07-09 06:50:06 +00001041 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
Owen Anderson216394f2007-07-03 18:37:08 +00001042 if (lhsValid)
1043 lhsValid = !dependsOnInvoke(U->getOperand(0));
1044
1045 if (!lhsValid) {
1046 set.erase(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001047 set.reset(VN.lookup(U));
Owen Anderson216394f2007-07-03 18:37:08 +00001048 }
1049
Owen Anderson7b317d22007-06-27 17:03:03 +00001050 // Handle binary ops
Owen Anderson216394f2007-07-03 18:37:08 +00001051 } else if (isa<BinaryOperator>(v) || isa<CmpInst>(v) ||
Owen Anderson7b317d22007-06-27 17:03:03 +00001052 isa<ExtractElementInst>(v)) {
1053 User* U = cast<User>(v);
1054
1055 bool lhsValid = !isa<Instruction>(U->getOperand(0));
Owen Anderson0616dff2007-07-09 06:50:06 +00001056 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
Owen Anderson60e17442007-06-18 04:30:44 +00001057 if (lhsValid)
Owen Anderson7b317d22007-06-27 17:03:03 +00001058 lhsValid = !dependsOnInvoke(U->getOperand(0));
Owen Andersona724ac12007-06-03 05:55:58 +00001059
Owen Anderson7b317d22007-06-27 17:03:03 +00001060 bool rhsValid = !isa<Instruction>(U->getOperand(1));
Owen Anderson0616dff2007-07-09 06:50:06 +00001061 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
Owen Anderson60e17442007-06-18 04:30:44 +00001062 if (rhsValid)
Owen Anderson7b317d22007-06-27 17:03:03 +00001063 rhsValid = !dependsOnInvoke(U->getOperand(1));
Owen Andersonea12a062007-05-29 21:53:49 +00001064
Owen Anderson68cb52e2007-06-27 17:38:29 +00001065 if (!lhsValid || !rhsValid) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001066 set.erase(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001067 set.reset(VN.lookup(U));
Owen Anderson68cb52e2007-06-27 17:38:29 +00001068 }
Owen Anderson139fe842007-06-09 18:35:31 +00001069
Owen Anderson7b317d22007-06-27 17:03:03 +00001070 // Handle ternary ops
Owen Anderson890e1a02007-06-28 23:51:21 +00001071 } else if (isa<ShuffleVectorInst>(v) || isa<InsertElementInst>(v) ||
1072 isa<SelectInst>(v)) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001073 User* U = cast<User>(v);
1074
1075 bool lhsValid = !isa<Instruction>(U->getOperand(0));
Owen Anderson0616dff2007-07-09 06:50:06 +00001076 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001077 if (lhsValid)
Owen Anderson7b317d22007-06-27 17:03:03 +00001078 lhsValid = !dependsOnInvoke(U->getOperand(0));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001079
Owen Anderson7b317d22007-06-27 17:03:03 +00001080 bool rhsValid = !isa<Instruction>(U->getOperand(1));
Owen Anderson0616dff2007-07-09 06:50:06 +00001081 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001082 if (rhsValid)
Owen Anderson7b317d22007-06-27 17:03:03 +00001083 rhsValid = !dependsOnInvoke(U->getOperand(1));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001084
Owen Anderson7b317d22007-06-27 17:03:03 +00001085 bool thirdValid = !isa<Instruction>(U->getOperand(2));
Owen Anderson0616dff2007-07-09 06:50:06 +00001086 thirdValid |= set.test(VN.lookup(U->getOperand(2)));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001087 if (thirdValid)
Owen Anderson7b317d22007-06-27 17:03:03 +00001088 thirdValid = !dependsOnInvoke(U->getOperand(2));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001089
Owen Anderson68cb52e2007-06-27 17:38:29 +00001090 if (!lhsValid || !rhsValid || !thirdValid) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001091 set.erase(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001092 set.reset(VN.lookup(U));
Owen Anderson68cb52e2007-06-27 17:38:29 +00001093 }
Owen Anderson56533222007-07-03 23:51:19 +00001094
1095 // Handle varargs ops
1096 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(v)) {
1097 bool ptrValid = !isa<Instruction>(U->getPointerOperand());
Owen Anderson0616dff2007-07-09 06:50:06 +00001098 ptrValid |= set.test(VN.lookup(U->getPointerOperand()));
Owen Anderson56533222007-07-03 23:51:19 +00001099 if (ptrValid)
1100 ptrValid = !dependsOnInvoke(U->getPointerOperand());
1101
1102 bool varValid = true;
1103 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
1104 I != E; ++I)
1105 if (varValid) {
Owen Anderson0616dff2007-07-09 06:50:06 +00001106 varValid &= !isa<Instruction>(*I) || set.test(VN.lookup(*I));
Owen Anderson56533222007-07-03 23:51:19 +00001107 varValid &= !dependsOnInvoke(*I);
1108 }
1109
1110 if (!ptrValid || !varValid) {
1111 set.erase(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001112 set.reset(VN.lookup(U));
Owen Anderson56533222007-07-03 23:51:19 +00001113 }
Owen Andersona724ac12007-06-03 05:55:58 +00001114 }
Owen Andersonea12a062007-05-29 21:53:49 +00001115 }
1116}
1117
Owen Anderson9cb56012007-06-21 00:19:05 +00001118/// topo_sort - Given a set of values, sort them by topological
1119/// order into the provided vector.
Owen Anderson19bc4a82007-07-19 06:37:56 +00001120void GVNPRE::topo_sort(ValueNumberedSet& set, SmallVector<Value*, 8>& vec) {
Owen Andersona20f35d2007-06-28 00:34:34 +00001121 SmallPtrSet<Value*, 16> visited;
Owen Anderson19bc4a82007-07-19 06:37:56 +00001122 SmallVector<Value*, 8> stack;
Owen Anderson0616dff2007-07-09 06:50:06 +00001123 for (ValueNumberedSet::iterator I = set.begin(), E = set.end();
Owen Anderson64758042007-06-22 21:31:16 +00001124 I != E; ++I) {
1125 if (visited.count(*I) == 0)
1126 stack.push_back(*I);
1127
1128 while (!stack.empty()) {
1129 Value* e = stack.back();
Owen Anderson216394f2007-07-03 18:37:08 +00001130
1131 // Handle unary ops
Owen Anderson3d6fac32007-07-03 19:01:42 +00001132 if (CastInst* U = dyn_cast<CastInst>(e)) {
Owen Anderson216394f2007-07-03 18:37:08 +00001133 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1134
1135 if (l != 0 && isa<Instruction>(l) &&
1136 visited.count(l) == 0)
1137 stack.push_back(l);
1138 else {
1139 vec.push_back(e);
1140 visited.insert(e);
1141 stack.pop_back();
1142 }
1143
Owen Anderson7b317d22007-06-27 17:03:03 +00001144 // Handle binary ops
Owen Anderson216394f2007-07-03 18:37:08 +00001145 } else if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
Owen Anderson7b317d22007-06-27 17:03:03 +00001146 isa<ExtractElementInst>(e)) {
1147 User* U = cast<User>(e);
1148 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1149 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
Owen Anderson64758042007-06-22 21:31:16 +00001150
1151 if (l != 0 && isa<Instruction>(l) &&
1152 visited.count(l) == 0)
1153 stack.push_back(l);
1154 else if (r != 0 && isa<Instruction>(r) &&
1155 visited.count(r) == 0)
1156 stack.push_back(r);
1157 else {
1158 vec.push_back(e);
1159 visited.insert(e);
1160 stack.pop_back();
1161 }
Owen Andersona724ac12007-06-03 05:55:58 +00001162
Owen Anderson7b317d22007-06-27 17:03:03 +00001163 // Handle ternary ops
Owen Anderson890e1a02007-06-28 23:51:21 +00001164 } else if (isa<InsertElementInst>(e) || isa<ShuffleVectorInst>(e) ||
1165 isa<SelectInst>(e)) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001166 User* U = cast<User>(e);
1167 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1168 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1169 Value* m = find_leader(set, VN.lookup(U->getOperand(2)));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001170
1171 if (l != 0 && isa<Instruction>(l) &&
1172 visited.count(l) == 0)
1173 stack.push_back(l);
1174 else if (r != 0 && isa<Instruction>(r) &&
1175 visited.count(r) == 0)
1176 stack.push_back(r);
1177 else if (m != 0 && isa<Instruction>(m) &&
1178 visited.count(m) == 0)
Owen Andersondf30b632007-07-04 18:26:18 +00001179 stack.push_back(m);
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001180 else {
1181 vec.push_back(e);
1182 visited.insert(e);
1183 stack.pop_back();
1184 }
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001185
Owen Anderson56533222007-07-03 23:51:19 +00001186 // Handle vararg ops
1187 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(e)) {
1188 Value* p = find_leader(set, VN.lookup(U->getPointerOperand()));
1189
1190 if (p != 0 && isa<Instruction>(p) &&
1191 visited.count(p) == 0)
1192 stack.push_back(p);
1193 else {
1194 bool push_va = false;
1195 for (GetElementPtrInst::op_iterator I = U->idx_begin(),
1196 E = U->idx_end(); I != E; ++I) {
1197 Value * v = find_leader(set, VN.lookup(*I));
1198 if (v != 0 && isa<Instruction>(v) && visited.count(v) == 0) {
1199 stack.push_back(v);
1200 push_va = true;
1201 }
1202 }
1203
1204 if (!push_va) {
1205 vec.push_back(e);
1206 visited.insert(e);
1207 stack.pop_back();
1208 }
1209 }
1210
Owen Anderson7b317d22007-06-27 17:03:03 +00001211 // Handle opaque ops
Owen Anderson64758042007-06-22 21:31:16 +00001212 } else {
Owen Andersona724ac12007-06-03 05:55:58 +00001213 visited.insert(e);
Owen Anderson139fe842007-06-09 18:35:31 +00001214 vec.push_back(e);
Owen Anderson64758042007-06-22 21:31:16 +00001215 stack.pop_back();
Owen Anderson139fe842007-06-09 18:35:31 +00001216 }
Owen Anderson243f3482007-05-31 22:44:11 +00001217 }
Owen Anderson64758042007-06-22 21:31:16 +00001218
1219 stack.clear();
Owen Anderson243f3482007-05-31 22:44:11 +00001220 }
1221}
1222
Owen Anderson9cb56012007-06-21 00:19:05 +00001223/// dump - Dump a set of values to standard error
Owen Anderson0616dff2007-07-09 06:50:06 +00001224void GVNPRE::dump(ValueNumberedSet& s) const {
Chris Lattnerbbbfa992009-08-23 06:35:02 +00001225 DEBUG(errs() << "{ ");
Owen Anderson0616dff2007-07-09 06:50:06 +00001226 for (ValueNumberedSet::iterator I = s.begin(), E = s.end();
Owen Anderson0fa6b372007-06-03 22:02:14 +00001227 I != E; ++I) {
Chris Lattnerbbbfa992009-08-23 06:35:02 +00001228 DEBUG(errs() << "" << VN.lookup(*I) << ": ");
Owen Anderson0fa6b372007-06-03 22:02:14 +00001229 DEBUG((*I)->dump());
1230 }
Chris Lattnerbbbfa992009-08-23 06:35:02 +00001231 DEBUG(errs() << "}\n\n");
Owen Anderson0fa6b372007-06-03 22:02:14 +00001232}
1233
Owen Anderson9cb56012007-06-21 00:19:05 +00001234/// elimination - Phase 3 of the main algorithm. Perform full redundancy
1235/// elimination by walking the dominator tree and removing any instruction that
1236/// is dominated by another instruction with the same value number.
Owen Anderson3eaca712007-06-20 22:10:02 +00001237bool GVNPRE::elimination() {
Owen Anderson3eaca712007-06-20 22:10:02 +00001238 bool changed_function = false;
1239
Owen Anderson19bc4a82007-07-19 06:37:56 +00001240 SmallVector<std::pair<Instruction*, Value*>, 8> replace;
1241 SmallVector<Instruction*, 8> erase;
Owen Anderson239e7122007-06-12 16:57:50 +00001242
1243 DominatorTree& DT = getAnalysis<DominatorTree>();
1244
1245 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1246 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1247 BasicBlock* BB = DI->getBlock();
1248
Owen Anderson239e7122007-06-12 16:57:50 +00001249 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1250 BI != BE; ++BI) {
1251
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001252 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI) ||
1253 isa<ShuffleVectorInst>(BI) || isa<InsertElementInst>(BI) ||
Owen Anderson216394f2007-07-03 18:37:08 +00001254 isa<ExtractElementInst>(BI) || isa<SelectInst>(BI) ||
Owen Anderson56533222007-07-03 23:51:19 +00001255 isa<CastInst>(BI) || isa<GetElementPtrInst>(BI)) {
Owen Andersona05a81b2007-07-10 00:09:25 +00001256
Owen Anderson9fed5892007-08-02 18:20:52 +00001257 if (availableOut[BB].test(VN.lookup(BI)) &&
1258 !availableOut[BB].count(BI)) {
Owen Andersona05a81b2007-07-10 00:09:25 +00001259 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
Owen Anderson239e7122007-06-12 16:57:50 +00001260 if (Instruction* Instr = dyn_cast<Instruction>(leader))
1261 if (Instr->getParent() != 0 && Instr != BI) {
1262 replace.push_back(std::make_pair(BI, leader));
1263 erase.push_back(BI);
1264 ++NumEliminated;
1265 }
Owen Andersona05a81b2007-07-10 00:09:25 +00001266 }
Owen Anderson239e7122007-06-12 16:57:50 +00001267 }
1268 }
1269 }
1270
1271 while (!replace.empty()) {
1272 std::pair<Instruction*, Value*> rep = replace.back();
1273 replace.pop_back();
1274 rep.first->replaceAllUsesWith(rep.second);
Owen Anderson0304b2b2007-06-20 18:30:20 +00001275 changed_function = true;
Owen Anderson239e7122007-06-12 16:57:50 +00001276 }
1277
Owen Anderson9fed5892007-08-02 18:20:52 +00001278 for (SmallVector<Instruction*, 8>::iterator I = erase.begin(),
1279 E = erase.end(); I != E; ++I)
Owen Anderson239e7122007-06-12 16:57:50 +00001280 (*I)->eraseFromParent();
Owen Anderson3eaca712007-06-20 22:10:02 +00001281
1282 return changed_function;
Owen Anderson239e7122007-06-12 16:57:50 +00001283}
1284
Owen Anderson9cb56012007-06-21 00:19:05 +00001285/// cleanup - Delete any extraneous values that were created to represent
1286/// expressions without leaders.
Owen Anderson239e7122007-06-12 16:57:50 +00001287void GVNPRE::cleanup() {
1288 while (!createdExpressions.empty()) {
1289 Instruction* I = createdExpressions.back();
1290 createdExpressions.pop_back();
1291
1292 delete I;
1293 }
1294}
1295
Owen Anderson9cb56012007-06-21 00:19:05 +00001296/// buildsets_availout - When calculating availability, handle an instruction
1297/// by inserting it into the appropriate sets
Owen Anderson3eaca712007-06-20 22:10:02 +00001298void GVNPRE::buildsets_availout(BasicBlock::iterator I,
Owen Anderson0616dff2007-07-09 06:50:06 +00001299 ValueNumberedSet& currAvail,
1300 ValueNumberedSet& currPhis,
1301 ValueNumberedSet& currExps,
1302 SmallPtrSet<Value*, 16>& currTemps) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001303 // Handle PHI nodes
Owen Anderson3eaca712007-06-20 22:10:02 +00001304 if (PHINode* p = dyn_cast<PHINode>(I)) {
Owen Anderson0616dff2007-07-09 06:50:06 +00001305 unsigned num = VN.lookup_or_add(p);
Owen Anderson12408462007-06-22 03:14:03 +00001306
Owen Anderson3eaca712007-06-20 22:10:02 +00001307 currPhis.insert(p);
Owen Anderson0616dff2007-07-09 06:50:06 +00001308 currPhis.set(num);
Owen Anderson216394f2007-07-03 18:37:08 +00001309
1310 // Handle unary ops
Owen Anderson3d6fac32007-07-03 19:01:42 +00001311 } else if (CastInst* U = dyn_cast<CastInst>(I)) {
Owen Anderson216394f2007-07-03 18:37:08 +00001312 Value* leftValue = U->getOperand(0);
Owen Anderson3eaca712007-06-20 22:10:02 +00001313
Owen Anderson216394f2007-07-03 18:37:08 +00001314 unsigned num = VN.lookup_or_add(U);
Owen Anderson216394f2007-07-03 18:37:08 +00001315
1316 if (isa<Instruction>(leftValue))
Owen Anderson0616dff2007-07-09 06:50:06 +00001317 if (!currExps.test(VN.lookup(leftValue))) {
Owen Anderson216394f2007-07-03 18:37:08 +00001318 currExps.insert(leftValue);
Owen Anderson0616dff2007-07-09 06:50:06 +00001319 currExps.set(VN.lookup(leftValue));
Owen Anderson216394f2007-07-03 18:37:08 +00001320 }
1321
Owen Anderson0616dff2007-07-09 06:50:06 +00001322 if (!currExps.test(num)) {
Owen Anderson216394f2007-07-03 18:37:08 +00001323 currExps.insert(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001324 currExps.set(num);
Owen Anderson216394f2007-07-03 18:37:08 +00001325 }
1326
Owen Anderson7b317d22007-06-27 17:03:03 +00001327 // Handle binary ops
1328 } else if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
1329 isa<ExtractElementInst>(I)) {
1330 User* U = cast<User>(I);
1331 Value* leftValue = U->getOperand(0);
1332 Value* rightValue = U->getOperand(1);
Owen Anderson3eaca712007-06-20 22:10:02 +00001333
Owen Anderson7b317d22007-06-27 17:03:03 +00001334 unsigned num = VN.lookup_or_add(U);
Owen Anderson3eaca712007-06-20 22:10:02 +00001335
1336 if (isa<Instruction>(leftValue))
Owen Anderson0616dff2007-07-09 06:50:06 +00001337 if (!currExps.test(VN.lookup(leftValue))) {
Owen Anderson12408462007-06-22 03:14:03 +00001338 currExps.insert(leftValue);
Owen Anderson0616dff2007-07-09 06:50:06 +00001339 currExps.set(VN.lookup(leftValue));
Owen Anderson12408462007-06-22 03:14:03 +00001340 }
1341
Owen Anderson3eaca712007-06-20 22:10:02 +00001342 if (isa<Instruction>(rightValue))
Owen Anderson0616dff2007-07-09 06:50:06 +00001343 if (!currExps.test(VN.lookup(rightValue))) {
Owen Anderson12408462007-06-22 03:14:03 +00001344 currExps.insert(rightValue);
Owen Anderson0616dff2007-07-09 06:50:06 +00001345 currExps.set(VN.lookup(rightValue));
Owen Anderson12408462007-06-22 03:14:03 +00001346 }
1347
Owen Anderson0616dff2007-07-09 06:50:06 +00001348 if (!currExps.test(num)) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001349 currExps.insert(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001350 currExps.set(num);
Owen Anderson12408462007-06-22 03:14:03 +00001351 }
Owen Anderson3eaca712007-06-20 22:10:02 +00001352
Owen Anderson7b317d22007-06-27 17:03:03 +00001353 // Handle ternary ops
Owen Anderson890e1a02007-06-28 23:51:21 +00001354 } else if (isa<InsertElementInst>(I) || isa<ShuffleVectorInst>(I) ||
1355 isa<SelectInst>(I)) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001356 User* U = cast<User>(I);
1357 Value* leftValue = U->getOperand(0);
1358 Value* rightValue = U->getOperand(1);
1359 Value* thirdValue = U->getOperand(2);
Owen Anderson3eaca712007-06-20 22:10:02 +00001360
Owen Anderson7b317d22007-06-27 17:03:03 +00001361 VN.lookup_or_add(U);
Owen Anderson12408462007-06-22 03:14:03 +00001362
Owen Anderson7b317d22007-06-27 17:03:03 +00001363 unsigned num = VN.lookup_or_add(U);
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001364
1365 if (isa<Instruction>(leftValue))
Owen Anderson0616dff2007-07-09 06:50:06 +00001366 if (!currExps.test(VN.lookup(leftValue))) {
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001367 currExps.insert(leftValue);
Owen Anderson0616dff2007-07-09 06:50:06 +00001368 currExps.set(VN.lookup(leftValue));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001369 }
1370 if (isa<Instruction>(rightValue))
Owen Anderson0616dff2007-07-09 06:50:06 +00001371 if (!currExps.test(VN.lookup(rightValue))) {
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001372 currExps.insert(rightValue);
Owen Anderson0616dff2007-07-09 06:50:06 +00001373 currExps.set(VN.lookup(rightValue));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001374 }
1375 if (isa<Instruction>(thirdValue))
Owen Anderson0616dff2007-07-09 06:50:06 +00001376 if (!currExps.test(VN.lookup(thirdValue))) {
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001377 currExps.insert(thirdValue);
Owen Anderson0616dff2007-07-09 06:50:06 +00001378 currExps.set(VN.lookup(thirdValue));
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001379 }
1380
Owen Anderson0616dff2007-07-09 06:50:06 +00001381 if (!currExps.test(num)) {
Owen Anderson7b317d22007-06-27 17:03:03 +00001382 currExps.insert(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001383 currExps.set(num);
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001384 }
1385
Owen Anderson56533222007-07-03 23:51:19 +00001386 // Handle vararg ops
1387 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(I)) {
1388 Value* ptrValue = U->getPointerOperand();
1389
1390 VN.lookup_or_add(U);
1391
1392 unsigned num = VN.lookup_or_add(U);
Owen Anderson56533222007-07-03 23:51:19 +00001393
1394 if (isa<Instruction>(ptrValue))
Owen Anderson0616dff2007-07-09 06:50:06 +00001395 if (!currExps.test(VN.lookup(ptrValue))) {
Owen Anderson56533222007-07-03 23:51:19 +00001396 currExps.insert(ptrValue);
Owen Anderson0616dff2007-07-09 06:50:06 +00001397 currExps.set(VN.lookup(ptrValue));
Owen Anderson56533222007-07-03 23:51:19 +00001398 }
1399
1400 for (GetElementPtrInst::op_iterator OI = U->idx_begin(), OE = U->idx_end();
1401 OI != OE; ++OI)
Owen Anderson0616dff2007-07-09 06:50:06 +00001402 if (isa<Instruction>(*OI) && !currExps.test(VN.lookup(*OI))) {
Owen Anderson56533222007-07-03 23:51:19 +00001403 currExps.insert(*OI);
Owen Anderson0616dff2007-07-09 06:50:06 +00001404 currExps.set(VN.lookup(*OI));
Owen Anderson56533222007-07-03 23:51:19 +00001405 }
1406
Owen Anderson0616dff2007-07-09 06:50:06 +00001407 if (!currExps.test(VN.lookup(U))) {
Owen Anderson56533222007-07-03 23:51:19 +00001408 currExps.insert(U);
Owen Anderson0616dff2007-07-09 06:50:06 +00001409 currExps.set(num);
Owen Anderson56533222007-07-03 23:51:19 +00001410 }
1411
Owen Anderson7b317d22007-06-27 17:03:03 +00001412 // Handle opaque ops
1413 } else if (!I->isTerminator()){
Owen Anderson3eaca712007-06-20 22:10:02 +00001414 VN.lookup_or_add(I);
Owen Anderson12408462007-06-22 03:14:03 +00001415
Owen Anderson3eaca712007-06-20 22:10:02 +00001416 currTemps.insert(I);
1417 }
1418
1419 if (!I->isTerminator())
Owen Anderson0616dff2007-07-09 06:50:06 +00001420 if (!currAvail.test(VN.lookup(I))) {
Owen Anderson12408462007-06-22 03:14:03 +00001421 currAvail.insert(I);
Owen Anderson0616dff2007-07-09 06:50:06 +00001422 currAvail.set(VN.lookup(I));
Owen Anderson12408462007-06-22 03:14:03 +00001423 }
Owen Anderson3eaca712007-06-20 22:10:02 +00001424}
Owen Andersonea12a062007-05-29 21:53:49 +00001425
Owen Anderson9cb56012007-06-21 00:19:05 +00001426/// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
1427/// set as a function of the ANTIC_IN set of the block's predecessors
Owen Anderson82575d82007-06-22 00:20:30 +00001428bool GVNPRE::buildsets_anticout(BasicBlock* BB,
Owen Anderson0616dff2007-07-09 06:50:06 +00001429 ValueNumberedSet& anticOut,
Owen Andersonb9781982007-07-19 03:32:44 +00001430 SmallPtrSet<BasicBlock*, 8>& visited) {
Owen Anderson3eaca712007-06-20 22:10:02 +00001431 if (BB->getTerminator()->getNumSuccessors() == 1) {
Owen Andersonf62c44a2007-06-25 05:41:12 +00001432 if (BB->getTerminator()->getSuccessor(0) != BB &&
1433 visited.count(BB->getTerminator()->getSuccessor(0)) == 0) {
Owen Anderson82575d82007-06-22 00:20:30 +00001434 return true;
Owen Andersonf62c44a2007-06-25 05:41:12 +00001435 }
1436 else {
Owen Anderson3eaca712007-06-20 22:10:02 +00001437 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
1438 BB, BB->getTerminator()->getSuccessor(0), anticOut);
Owen Andersonf62c44a2007-06-25 05:41:12 +00001439 }
Owen Anderson3eaca712007-06-20 22:10:02 +00001440 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
1441 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
Owen Anderson0616dff2007-07-09 06:50:06 +00001442 for (ValueNumberedSet::iterator I = anticipatedIn[first].begin(),
1443 E = anticipatedIn[first].end(); I != E; ++I) {
1444 anticOut.insert(*I);
1445 anticOut.set(VN.lookup(*I));
1446 }
Owen Anderson3eaca712007-06-20 22:10:02 +00001447
1448 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
1449 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
Owen Anderson0616dff2007-07-09 06:50:06 +00001450 ValueNumberedSet& succAnticIn = anticipatedIn[currSucc];
Owen Anderson3eaca712007-06-20 22:10:02 +00001451
Owen Anderson19bc4a82007-07-19 06:37:56 +00001452 SmallVector<Value*, 16> temp;
Owen Anderson66fd9062007-06-21 17:57:53 +00001453
Owen Anderson0616dff2007-07-09 06:50:06 +00001454 for (ValueNumberedSet::iterator I = anticOut.begin(),
Owen Anderson66fd9062007-06-21 17:57:53 +00001455 E = anticOut.end(); I != E; ++I)
Owen Anderson0616dff2007-07-09 06:50:06 +00001456 if (!succAnticIn.test(VN.lookup(*I)))
Owen Anderson66fd9062007-06-21 17:57:53 +00001457 temp.push_back(*I);
1458
Owen Anderson19bc4a82007-07-19 06:37:56 +00001459 for (SmallVector<Value*, 16>::iterator I = temp.begin(), E = temp.end();
Owen Anderson0616dff2007-07-09 06:50:06 +00001460 I != E; ++I) {
Owen Anderson66fd9062007-06-21 17:57:53 +00001461 anticOut.erase(*I);
Owen Anderson0616dff2007-07-09 06:50:06 +00001462 anticOut.reset(VN.lookup(*I));
1463 }
Owen Anderson3eaca712007-06-20 22:10:02 +00001464 }
1465 }
Owen Anderson82575d82007-06-22 00:20:30 +00001466
1467 return false;
Owen Anderson3eaca712007-06-20 22:10:02 +00001468}
1469
Owen Anderson9cb56012007-06-21 00:19:05 +00001470/// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
1471/// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN
1472/// sets populated in buildsets_availout
Owen Anderson82575d82007-06-22 00:20:30 +00001473unsigned GVNPRE::buildsets_anticin(BasicBlock* BB,
Owen Anderson0616dff2007-07-09 06:50:06 +00001474 ValueNumberedSet& anticOut,
1475 ValueNumberedSet& currExps,
Owen Andersona20f35d2007-06-28 00:34:34 +00001476 SmallPtrSet<Value*, 16>& currTemps,
Owen Andersonb9781982007-07-19 03:32:44 +00001477 SmallPtrSet<BasicBlock*, 8>& visited) {
Owen Anderson0616dff2007-07-09 06:50:06 +00001478 ValueNumberedSet& anticIn = anticipatedIn[BB];
Owen Anderson2106f612007-06-22 18:27:04 +00001479 unsigned old = anticIn.size();
Owen Anderson3eaca712007-06-20 22:10:02 +00001480
Owen Anderson82575d82007-06-22 00:20:30 +00001481 bool defer = buildsets_anticout(BB, anticOut, visited);
1482 if (defer)
1483 return 0;
Owen Anderson66fd9062007-06-21 17:57:53 +00001484
Owen Anderson3eaca712007-06-20 22:10:02 +00001485 anticIn.clear();
Owen Anderson66fd9062007-06-21 17:57:53 +00001486
Owen Anderson0616dff2007-07-09 06:50:06 +00001487 for (ValueNumberedSet::iterator I = anticOut.begin(),
Owen Anderson2106f612007-06-22 18:27:04 +00001488 E = anticOut.end(); I != E; ++I) {
Owen Anderson0616dff2007-07-09 06:50:06 +00001489 anticIn.insert(*I);
1490 anticIn.set(VN.lookup(*I));
Owen Anderson3eaca712007-06-20 22:10:02 +00001491 }
Owen Anderson0616dff2007-07-09 06:50:06 +00001492 for (ValueNumberedSet::iterator I = currExps.begin(),
Owen Anderson2106f612007-06-22 18:27:04 +00001493 E = currExps.end(); I != E; ++I) {
Owen Anderson0616dff2007-07-09 06:50:06 +00001494 if (!anticIn.test(VN.lookup(*I))) {
Owen Anderson2106f612007-06-22 18:27:04 +00001495 anticIn.insert(*I);
Owen Anderson0616dff2007-07-09 06:50:06 +00001496 anticIn.set(VN.lookup(*I));
Owen Anderson2106f612007-06-22 18:27:04 +00001497 }
1498 }
1499
Owen Andersona20f35d2007-06-28 00:34:34 +00001500 for (SmallPtrSet<Value*, 16>::iterator I = currTemps.begin(),
Owen Anderson68cb52e2007-06-27 17:38:29 +00001501 E = currTemps.end(); I != E; ++I) {
Owen Anderson2106f612007-06-22 18:27:04 +00001502 anticIn.erase(*I);
Owen Anderson0616dff2007-07-09 06:50:06 +00001503 anticIn.reset(VN.lookup(*I));
Owen Anderson68cb52e2007-06-27 17:38:29 +00001504 }
Owen Anderson2106f612007-06-22 18:27:04 +00001505
Owen Anderson0616dff2007-07-09 06:50:06 +00001506 clean(anticIn);
Owen Anderson68cb52e2007-06-27 17:38:29 +00001507 anticOut.clear();
Owen Anderson3eaca712007-06-20 22:10:02 +00001508
Owen Anderson68cb52e2007-06-27 17:38:29 +00001509 if (old != anticIn.size())
Owen Anderson82575d82007-06-22 00:20:30 +00001510 return 2;
Owen Anderson68cb52e2007-06-27 17:38:29 +00001511 else
Owen Anderson82575d82007-06-22 00:20:30 +00001512 return 1;
Owen Anderson3eaca712007-06-20 22:10:02 +00001513}
1514
Owen Anderson9cb56012007-06-21 00:19:05 +00001515/// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT
1516/// and the ANTIC_IN sets.
Owen Anderson6032a5b2007-06-26 23:29:41 +00001517void GVNPRE::buildsets(Function& F) {
Owen Andersonb9781982007-07-19 03:32:44 +00001518 DenseMap<BasicBlock*, ValueNumberedSet> generatedExpressions;
1519 DenseMap<BasicBlock*, SmallPtrSet<Value*, 16> > generatedTemporaries;
Owen Anderson3eaca712007-06-20 22:10:02 +00001520
Owen Andersonea12a062007-05-29 21:53:49 +00001521 DominatorTree &DT = getAnalysis<DominatorTree>();
1522
Owen Anderson12112af2007-06-06 01:27:49 +00001523 // Phase 1, Part 1: calculate AVAIL_OUT
Owen Andersonea12a062007-05-29 21:53:49 +00001524
1525 // Top-down walk of the dominator tree
Devang Patel26042422007-06-04 00:32:22 +00001526 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
Owen Andersonea12a062007-05-29 21:53:49 +00001527 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1528
1529 // Get the sets to update for this block
Owen Anderson0616dff2007-07-09 06:50:06 +00001530 ValueNumberedSet& currExps = generatedExpressions[DI->getBlock()];
1531 ValueNumberedSet& currPhis = generatedPhis[DI->getBlock()];
Owen Andersona20f35d2007-06-28 00:34:34 +00001532 SmallPtrSet<Value*, 16>& currTemps = generatedTemporaries[DI->getBlock()];
Owen Anderson0616dff2007-07-09 06:50:06 +00001533 ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
Owen Andersonea12a062007-05-29 21:53:49 +00001534
Owen Anderson086f5f32007-06-19 03:31:41 +00001535 BasicBlock* BB = DI->getBlock();
1536
1537 // A block inherits AVAIL_OUT from its dominator
Owen Andersondfa24352007-07-09 22:29:50 +00001538 if (DI->getIDom() != 0)
1539 currAvail = availableOut[DI->getIDom()->getBlock()];
Owen Anderson0616dff2007-07-09 06:50:06 +00001540
Owen Anderson086f5f32007-06-19 03:31:41 +00001541 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
Owen Anderson3eaca712007-06-20 22:10:02 +00001542 BI != BE; ++BI)
Owen Anderson12408462007-06-22 03:14:03 +00001543 buildsets_availout(BI, currAvail, currPhis, currExps,
Owen Anderson0616dff2007-07-09 06:50:06 +00001544 currTemps);
Owen Anderson086f5f32007-06-19 03:31:41 +00001545
Owen Andersonea12a062007-05-29 21:53:49 +00001546 }
Owen Andersonf62c44a2007-06-25 05:41:12 +00001547
1548 // Phase 1, Part 2: calculate ANTIC_IN
Owen Andersonea12a062007-05-29 21:53:49 +00001549
Owen Andersonb9781982007-07-19 03:32:44 +00001550 SmallPtrSet<BasicBlock*, 8> visited;
Owen Anderson6032a5b2007-06-26 23:29:41 +00001551 SmallPtrSet<BasicBlock*, 4> block_changed;
1552 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
1553 block_changed.insert(FI);
Owen Andersone3072b22007-05-29 23:26:30 +00001554
Owen Andersonea12a062007-05-29 21:53:49 +00001555 bool changed = true;
1556 unsigned iterations = 0;
Owen Anderson6032a5b2007-06-26 23:29:41 +00001557
Owen Andersonea12a062007-05-29 21:53:49 +00001558 while (changed) {
1559 changed = false;
Owen Anderson0616dff2007-07-09 06:50:06 +00001560 ValueNumberedSet anticOut;
Owen Andersonea12a062007-05-29 21:53:49 +00001561
Owen Anderson6032a5b2007-06-26 23:29:41 +00001562 // Postorder walk of the CFG
Owen Anderson9030d382007-06-25 18:25:31 +00001563 for (po_iterator<BasicBlock*> BBI = po_begin(&F.getEntryBlock()),
1564 BBE = po_end(&F.getEntryBlock()); BBI != BBE; ++BBI) {
Owen Andersonf62c44a2007-06-25 05:41:12 +00001565 BasicBlock* BB = *BBI;
Owen Anderson0e714662007-06-11 16:25:17 +00001566
Owen Anderson6032a5b2007-06-26 23:29:41 +00001567 if (block_changed.count(BB) != 0) {
1568 unsigned ret = buildsets_anticin(BB, anticOut,generatedExpressions[BB],
1569 generatedTemporaries[BB], visited);
Owen Anderson82575d82007-06-22 00:20:30 +00001570
Owen Anderson6032a5b2007-06-26 23:29:41 +00001571 if (ret == 0) {
1572 changed = true;
1573 continue;
1574 } else {
1575 visited.insert(BB);
1576
1577 if (ret == 2)
1578 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1579 PI != PE; ++PI) {
1580 block_changed.insert(*PI);
1581 }
1582 else
1583 block_changed.erase(BB);
1584
1585 changed |= (ret == 2);
Owen Andersonf62c44a2007-06-25 05:41:12 +00001586 }
Owen Anderson82575d82007-06-22 00:20:30 +00001587 }
Owen Andersonea12a062007-05-29 21:53:49 +00001588 }
Owen Anderson5ea069f2007-06-04 18:05:26 +00001589
Owen Andersonea12a062007-05-29 21:53:49 +00001590 iterations++;
1591 }
Owen Anderson3eaca712007-06-20 22:10:02 +00001592}
1593
Owen Anderson9cb56012007-06-21 00:19:05 +00001594/// insertion_pre - When a partial redundancy has been identified, eliminate it
1595/// by inserting appropriate values into the predecessors and a phi node in
1596/// the main block
Owen Anderson3eaca712007-06-20 22:10:02 +00001597void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
Owen Anderson19bc4a82007-07-19 06:37:56 +00001598 DenseMap<BasicBlock*, Value*>& avail,
Owen Anderson0616dff2007-07-09 06:50:06 +00001599 std::map<BasicBlock*, ValueNumberedSet>& new_sets) {
Owen Andersone922c022009-07-22 00:24:57 +00001600 LLVMContext &Context = e->getContext();
Owen Anderson3eaca712007-06-20 22:10:02 +00001601 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1602 Value* e2 = avail[*PI];
Owen Anderson0616dff2007-07-09 06:50:06 +00001603 if (!availableOut[*PI].test(VN.lookup(e2))) {
Owen Anderson3eaca712007-06-20 22:10:02 +00001604 User* U = cast<User>(e2);
1605
1606 Value* s1 = 0;
1607 if (isa<BinaryOperator>(U->getOperand(0)) ||
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001608 isa<CmpInst>(U->getOperand(0)) ||
1609 isa<ShuffleVectorInst>(U->getOperand(0)) ||
1610 isa<ExtractElementInst>(U->getOperand(0)) ||
Owen Anderson890e1a02007-06-28 23:51:21 +00001611 isa<InsertElementInst>(U->getOperand(0)) ||
Owen Anderson216394f2007-07-03 18:37:08 +00001612 isa<SelectInst>(U->getOperand(0)) ||
Owen Anderson56533222007-07-03 23:51:19 +00001613 isa<CastInst>(U->getOperand(0)) ||
1614 isa<GetElementPtrInst>(U->getOperand(0)))
Owen Anderson3eaca712007-06-20 22:10:02 +00001615 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1616 else
1617 s1 = U->getOperand(0);
1618
1619 Value* s2 = 0;
Owen Anderson216394f2007-07-03 18:37:08 +00001620
1621 if (isa<BinaryOperator>(U) ||
1622 isa<CmpInst>(U) ||
1623 isa<ShuffleVectorInst>(U) ||
1624 isa<ExtractElementInst>(U) ||
1625 isa<InsertElementInst>(U) ||
Anton Korobeynikov07e6e562008-02-20 11:26:25 +00001626 isa<SelectInst>(U)) {
Owen Anderson216394f2007-07-03 18:37:08 +00001627 if (isa<BinaryOperator>(U->getOperand(1)) ||
1628 isa<CmpInst>(U->getOperand(1)) ||
1629 isa<ShuffleVectorInst>(U->getOperand(1)) ||
1630 isa<ExtractElementInst>(U->getOperand(1)) ||
1631 isa<InsertElementInst>(U->getOperand(1)) ||
1632 isa<SelectInst>(U->getOperand(1)) ||
Owen Anderson56533222007-07-03 23:51:19 +00001633 isa<CastInst>(U->getOperand(1)) ||
1634 isa<GetElementPtrInst>(U->getOperand(1))) {
Owen Anderson216394f2007-07-03 18:37:08 +00001635 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1636 } else {
1637 s2 = U->getOperand(1);
1638 }
Anton Korobeynikov07e6e562008-02-20 11:26:25 +00001639 }
Owen Anderson7b317d22007-06-27 17:03:03 +00001640
1641 // Ternary Operators
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001642 Value* s3 = 0;
1643 if (isa<ShuffleVectorInst>(U) ||
Owen Anderson890e1a02007-06-28 23:51:21 +00001644 isa<InsertElementInst>(U) ||
Anton Korobeynikov07e6e562008-02-20 11:26:25 +00001645 isa<SelectInst>(U)) {
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001646 if (isa<BinaryOperator>(U->getOperand(2)) ||
1647 isa<CmpInst>(U->getOperand(2)) ||
1648 isa<ShuffleVectorInst>(U->getOperand(2)) ||
1649 isa<ExtractElementInst>(U->getOperand(2)) ||
Owen Anderson890e1a02007-06-28 23:51:21 +00001650 isa<InsertElementInst>(U->getOperand(2)) ||
Owen Anderson216394f2007-07-03 18:37:08 +00001651 isa<SelectInst>(U->getOperand(2)) ||
Owen Anderson56533222007-07-03 23:51:19 +00001652 isa<CastInst>(U->getOperand(2)) ||
1653 isa<GetElementPtrInst>(U->getOperand(2))) {
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001654 s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2)));
Owen Anderson216394f2007-07-03 18:37:08 +00001655 } else {
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001656 s3 = U->getOperand(2);
Owen Anderson216394f2007-07-03 18:37:08 +00001657 }
Anton Korobeynikov07e6e562008-02-20 11:26:25 +00001658 }
Owen Anderson3eaca712007-06-20 22:10:02 +00001659
Owen Anderson56533222007-07-03 23:51:19 +00001660 // Vararg operators
Owen Anderson19bc4a82007-07-19 06:37:56 +00001661 SmallVector<Value*, 4> sVarargs;
Owen Anderson56533222007-07-03 23:51:19 +00001662 if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U)) {
1663 for (GetElementPtrInst::op_iterator OI = G->idx_begin(),
1664 OE = G->idx_end(); OI != OE; ++OI) {
1665 if (isa<BinaryOperator>(*OI) ||
1666 isa<CmpInst>(*OI) ||
1667 isa<ShuffleVectorInst>(*OI) ||
1668 isa<ExtractElementInst>(*OI) ||
1669 isa<InsertElementInst>(*OI) ||
1670 isa<SelectInst>(*OI) ||
1671 isa<CastInst>(*OI) ||
1672 isa<GetElementPtrInst>(*OI)) {
1673 sVarargs.push_back(find_leader(availableOut[*PI],
1674 VN.lookup(*OI)));
1675 } else {
1676 sVarargs.push_back(*OI);
1677 }
1678 }
1679 }
1680
Owen Anderson3eaca712007-06-20 22:10:02 +00001681 Value* newVal = 0;
1682 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
Gabor Greif7cbd8a32008-05-16 19:29:10 +00001683 newVal = BinaryOperator::Create(BO->getOpcode(), s1, s2,
Owen Anderson3eaca712007-06-20 22:10:02 +00001684 BO->getName()+".gvnpre",
1685 (*PI)->getTerminator());
1686 else if (CmpInst* C = dyn_cast<CmpInst>(U))
Dan Gohman1c8a23c2009-08-25 23:17:54 +00001687 newVal = CmpInst::Create(C->getOpcode(),
Owen Anderson333c4002009-07-09 23:48:35 +00001688 C->getPredicate(), s1, s2,
Owen Anderson3eaca712007-06-20 22:10:02 +00001689 C->getName()+".gvnpre",
1690 (*PI)->getTerminator());
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001691 else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
1692 newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre",
1693 (*PI)->getTerminator());
1694 else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U))
Gabor Greif051a9502008-04-06 20:25:17 +00001695 newVal = InsertElementInst::Create(s1, s2, s3, S->getName()+".gvnpre",
1696 (*PI)->getTerminator());
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001697 else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U))
Eric Christophera3500da2009-07-25 02:28:41 +00001698 newVal = ExtractElementInst::Create(s1, s2, S->getName()+".gvnpre",
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001699 (*PI)->getTerminator());
Owen Anderson890e1a02007-06-28 23:51:21 +00001700 else if (SelectInst* S = dyn_cast<SelectInst>(U))
Gabor Greif051a9502008-04-06 20:25:17 +00001701 newVal = SelectInst::Create(s1, s2, s3, S->getName()+".gvnpre",
1702 (*PI)->getTerminator());
Owen Anderson216394f2007-07-03 18:37:08 +00001703 else if (CastInst* C = dyn_cast<CastInst>(U))
Gabor Greif7cbd8a32008-05-16 19:29:10 +00001704 newVal = CastInst::Create(C->getOpcode(), s1, C->getType(),
Owen Anderson216394f2007-07-03 18:37:08 +00001705 C->getName()+".gvnpre",
1706 (*PI)->getTerminator());
Owen Anderson56533222007-07-03 23:51:19 +00001707 else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U))
Gabor Greif051a9502008-04-06 20:25:17 +00001708 newVal = GetElementPtrInst::Create(s1, sVarargs.begin(), sVarargs.end(),
1709 G->getName()+".gvnpre",
1710 (*PI)->getTerminator());
1711
Owen Anderson3eaca712007-06-20 22:10:02 +00001712 VN.add(newVal, VN.lookup(U));
1713
Owen Anderson0616dff2007-07-09 06:50:06 +00001714 ValueNumberedSet& predAvail = availableOut[*PI];
Owen Anderson3eaca712007-06-20 22:10:02 +00001715 val_replace(predAvail, newVal);
Owen Anderson2a5c9d82007-07-05 23:11:26 +00001716 val_replace(new_sets[*PI], newVal);
Owen Anderson0616dff2007-07-09 06:50:06 +00001717 predAvail.set(VN.lookup(newVal));
Owen Anderson9cb56012007-06-21 00:19:05 +00001718
Owen Anderson19bc4a82007-07-19 06:37:56 +00001719 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
Owen Anderson3eaca712007-06-20 22:10:02 +00001720 if (av != avail.end())
1721 avail.erase(av);
1722 avail.insert(std::make_pair(*PI, newVal));
1723
1724 ++NumInsertedVals;
1725 }
1726 }
1727
1728 PHINode* p = 0;
1729
1730 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1731 if (p == 0)
Gabor Greif051a9502008-04-06 20:25:17 +00001732 p = PHINode::Create(avail[*PI]->getType(), "gvnpre-join", BB->begin());
Owen Anderson2a5c9d82007-07-05 23:11:26 +00001733
Owen Anderson3eaca712007-06-20 22:10:02 +00001734 p->addIncoming(avail[*PI], *PI);
1735 }
1736
1737 VN.add(p, VN.lookup(e));
Owen Anderson3eaca712007-06-20 22:10:02 +00001738 val_replace(availableOut[BB], p);
Owen Anderson0616dff2007-07-09 06:50:06 +00001739 availableOut[BB].set(VN.lookup(e));
Owen Andersonec5614b2007-07-06 20:29:43 +00001740 generatedPhis[BB].insert(p);
Owen Anderson0616dff2007-07-09 06:50:06 +00001741 generatedPhis[BB].set(VN.lookup(e));
Owen Anderson2a5c9d82007-07-05 23:11:26 +00001742 new_sets[BB].insert(p);
Owen Anderson0616dff2007-07-09 06:50:06 +00001743 new_sets[BB].set(VN.lookup(e));
Owen Anderson3eaca712007-06-20 22:10:02 +00001744
1745 ++NumInsertedPhis;
1746}
1747
Owen Anderson9cb56012007-06-21 00:19:05 +00001748/// insertion_mergepoint - When walking the dom tree, check at each merge
1749/// block for the possibility of a partial redundancy. If present, eliminate it
Owen Anderson19bc4a82007-07-19 06:37:56 +00001750unsigned GVNPRE::insertion_mergepoint(SmallVector<Value*, 8>& workList,
Owen Anderson82575d82007-06-22 00:20:30 +00001751 df_iterator<DomTreeNode*>& D,
Owen Anderson0616dff2007-07-09 06:50:06 +00001752 std::map<BasicBlock*, ValueNumberedSet >& new_sets) {
Owen Anderson3eaca712007-06-20 22:10:02 +00001753 bool changed_function = false;
1754 bool new_stuff = false;
1755
1756 BasicBlock* BB = D->getBlock();
1757 for (unsigned i = 0; i < workList.size(); ++i) {
1758 Value* e = workList[i];
1759
Owen Anderson62cf8ba2007-06-27 04:10:46 +00001760 if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1761 isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) ||
Owen Anderson56533222007-07-03 23:51:19 +00001762 isa<ShuffleVectorInst>(e) || isa<SelectInst>(e) || isa<CastInst>(e) ||
1763 isa<GetElementPtrInst>(e)) {
Owen Anderson0616dff2007-07-09 06:50:06 +00001764 if (availableOut[D->getIDom()->getBlock()].test(VN.lookup(e)))
Owen Anderson3eaca712007-06-20 22:10:02 +00001765 continue;
1766
Owen Anderson19bc4a82007-07-19 06:37:56 +00001767 DenseMap<BasicBlock*, Value*> avail;
Owen Anderson3eaca712007-06-20 22:10:02 +00001768 bool by_some = false;
Owen Andersonec5614b2007-07-06 20:29:43 +00001769 bool all_same = true;
1770 Value * first_s = 0;
Owen Anderson3eaca712007-06-20 22:10:02 +00001771
1772 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1773 ++PI) {
1774 Value *e2 = phi_translate(e, *PI, BB);
1775 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1776
1777 if (e3 == 0) {
Owen Anderson19bc4a82007-07-19 06:37:56 +00001778 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
Owen Anderson3eaca712007-06-20 22:10:02 +00001779 if (av != avail.end())
1780 avail.erase(av);
1781 avail.insert(std::make_pair(*PI, e2));
Owen Andersonec5614b2007-07-06 20:29:43 +00001782 all_same = false;
Owen Anderson3eaca712007-06-20 22:10:02 +00001783 } else {
Owen Anderson19bc4a82007-07-19 06:37:56 +00001784 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
Owen Anderson3eaca712007-06-20 22:10:02 +00001785 if (av != avail.end())
1786 avail.erase(av);
1787 avail.insert(std::make_pair(*PI, e3));
1788
1789 by_some = true;
Owen Andersonec5614b2007-07-06 20:29:43 +00001790 if (first_s == 0)
1791 first_s = e3;
1792 else if (first_s != e3)
1793 all_same = false;
Owen Anderson3eaca712007-06-20 22:10:02 +00001794 }
1795 }
1796
Owen Andersonec5614b2007-07-06 20:29:43 +00001797 if (by_some && !all_same &&
Owen Anderson0616dff2007-07-09 06:50:06 +00001798 !generatedPhis[BB].test(VN.lookup(e))) {
Owen Anderson2a5c9d82007-07-05 23:11:26 +00001799 insertion_pre(e, BB, avail, new_sets);
Owen Anderson3eaca712007-06-20 22:10:02 +00001800
1801 changed_function = true;
1802 new_stuff = true;
1803 }
1804 }
1805 }
1806
1807 unsigned retval = 0;
1808 if (changed_function)
1809 retval += 1;
1810 if (new_stuff)
1811 retval += 2;
1812
1813 return retval;
1814}
1815
Owen Anderson9cb56012007-06-21 00:19:05 +00001816/// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for
1817/// merge points. When one is found, check for a partial redundancy. If one is
1818/// present, eliminate it. Repeat this walk until no changes are made.
Owen Anderson3eaca712007-06-20 22:10:02 +00001819bool GVNPRE::insertion(Function& F) {
1820 bool changed_function = false;
1821
1822 DominatorTree &DT = getAnalysis<DominatorTree>();
Owen Anderson397d4052007-06-08 01:03:01 +00001823
Owen Anderson0616dff2007-07-09 06:50:06 +00001824 std::map<BasicBlock*, ValueNumberedSet> new_sets;
Owen Anderson397d4052007-06-08 01:03:01 +00001825 bool new_stuff = true;
1826 while (new_stuff) {
1827 new_stuff = false;
Owen Anderson397d4052007-06-08 01:03:01 +00001828 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1829 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1830 BasicBlock* BB = DI->getBlock();
1831
Owen Anderson0e714662007-06-11 16:25:17 +00001832 if (BB == 0)
1833 continue;
1834
Owen Anderson0616dff2007-07-09 06:50:06 +00001835 ValueNumberedSet& availOut = availableOut[BB];
1836 ValueNumberedSet& anticIn = anticipatedIn[BB];
Owen Anderson397d4052007-06-08 01:03:01 +00001837
1838 // Replace leaders with leaders inherited from dominator
1839 if (DI->getIDom() != 0) {
Owen Anderson0616dff2007-07-09 06:50:06 +00001840 ValueNumberedSet& dom_set = new_sets[DI->getIDom()->getBlock()];
1841 for (ValueNumberedSet::iterator I = dom_set.begin(),
Owen Anderson397d4052007-06-08 01:03:01 +00001842 E = dom_set.end(); I != E; ++I) {
Owen Anderson2a5c9d82007-07-05 23:11:26 +00001843 val_replace(new_sets[BB], *I);
Owen Anderson086f5f32007-06-19 03:31:41 +00001844 val_replace(availOut, *I);
Owen Anderson397d4052007-06-08 01:03:01 +00001845 }
1846 }
1847
1848 // If there is more than one predecessor...
1849 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
Owen Anderson19bc4a82007-07-19 06:37:56 +00001850 SmallVector<Value*, 8> workList;
Owen Andersone8138ff2007-06-22 00:43:22 +00001851 workList.reserve(anticIn.size());
Owen Anderson397d4052007-06-08 01:03:01 +00001852 topo_sort(anticIn, workList);
1853
Owen Anderson2a5c9d82007-07-05 23:11:26 +00001854 unsigned result = insertion_mergepoint(workList, DI, new_sets);
Owen Anderson3eaca712007-06-20 22:10:02 +00001855 if (result & 1)
1856 changed_function = true;
1857 if (result & 2)
1858 new_stuff = true;
Owen Anderson397d4052007-06-08 01:03:01 +00001859 }
1860 }
Owen Anderson397d4052007-06-08 01:03:01 +00001861 }
Owen Anderson12112af2007-06-06 01:27:49 +00001862
Owen Anderson3eaca712007-06-20 22:10:02 +00001863 return changed_function;
1864}
1865
Owen Anderson9cb56012007-06-21 00:19:05 +00001866// GVNPRE::runOnFunction - This is the main transformation entry point for a
1867// function.
1868//
Owen Anderson3eaca712007-06-20 22:10:02 +00001869bool GVNPRE::runOnFunction(Function &F) {
Owen Anderson9cb56012007-06-21 00:19:05 +00001870 // Clean out global sets from any previous functions
Owen Anderson3eaca712007-06-20 22:10:02 +00001871 VN.clear();
1872 createdExpressions.clear();
1873 availableOut.clear();
1874 anticipatedIn.clear();
Owen Andersonec5614b2007-07-06 20:29:43 +00001875 generatedPhis.clear();
1876
Owen Anderson3eaca712007-06-20 22:10:02 +00001877 bool changed_function = false;
1878
1879 // Phase 1: BuildSets
Owen Anderson9cb56012007-06-21 00:19:05 +00001880 // This phase calculates the AVAIL_OUT and ANTIC_IN sets
Owen Anderson6032a5b2007-06-26 23:29:41 +00001881 buildsets(F);
Owen Anderson3eaca712007-06-20 22:10:02 +00001882
1883 // Phase 2: Insert
Owen Anderson9cb56012007-06-21 00:19:05 +00001884 // This phase inserts values to make partially redundant values
1885 // fully redundant
Owen Anderson3eaca712007-06-20 22:10:02 +00001886 changed_function |= insertion(F);
1887
Owen Anderson12112af2007-06-06 01:27:49 +00001888 // Phase 3: Eliminate
Owen Anderson9cb56012007-06-21 00:19:05 +00001889 // This phase performs trivial full redundancy elimination
Owen Anderson3eaca712007-06-20 22:10:02 +00001890 changed_function |= elimination();
Owen Anderson8338ff52007-06-08 20:44:02 +00001891
Owen Anderson397d4052007-06-08 01:03:01 +00001892 // Phase 4: Cleanup
Owen Anderson9cb56012007-06-21 00:19:05 +00001893 // This phase cleans up values that were created solely
1894 // as leaders for expressions
Owen Anderson239e7122007-06-12 16:57:50 +00001895 cleanup();
Owen Anderson397d4052007-06-08 01:03:01 +00001896
Owen Anderson0304b2b2007-06-20 18:30:20 +00001897 return changed_function;
Owen Andersonea12a062007-05-29 21:53:49 +00001898}