blob: 69e5f733f731a17bc93a87325759450d75573754 [file] [log] [blame]
Owen Anderson5fba6c12007-05-29 21:53:49 +00001//===- GVNPRE.cpp - Eliminate redundant values and expressions ------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file was developed by the Owen Anderson and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This pass performs a hybrid of global value numbering and partial redundancy
11// elimination, known as GVN-PRE. It performs partial redundancy elimination on
12// values, rather than lexical expressions, allowing a more comprehensive view
13// the optimization. It replaces redundant values with uses of earlier
14// occurences of the same value. While this is beneficial in that it eliminates
15// unneeded computation, it also increases register pressure by creating large
Owen Andersonb232efa2007-06-08 20:57:08 +000016// live ranges, and should be used with caution on platforms that are very
Owen Anderson5fba6c12007-05-29 21:53:49 +000017// sensitive to register pressure.
18//
19//===----------------------------------------------------------------------===//
20
21#define DEBUG_TYPE "gvnpre"
22#include "llvm/Value.h"
23#include "llvm/Transforms/Scalar.h"
24#include "llvm/Instructions.h"
25#include "llvm/Function.h"
Owen Andersonc738f7c2007-06-29 00:40:05 +000026#include "llvm/DerivedTypes.h"
Owen Anderson5fba6c12007-05-29 21:53:49 +000027#include "llvm/Analysis/Dominators.h"
Owen Anderson28a2d442007-06-22 00:20:30 +000028#include "llvm/ADT/BitVector.h"
Owen Anderson1ad2c102007-06-19 23:23:54 +000029#include "llvm/ADT/DenseMap.h"
Owen Anderson5fba6c12007-05-29 21:53:49 +000030#include "llvm/ADT/DepthFirstIterator.h"
Owen Anderson43ca4b42007-06-25 18:25:31 +000031#include "llvm/ADT/PostOrderIterator.h"
Owen Anderson2ff912b2007-06-21 17:57:53 +000032#include "llvm/ADT/SmallPtrSet.h"
Owen Anderson75a244d2007-07-19 06:13:15 +000033#include "llvm/ADT/SmallVector.h"
Owen Anderson5fba6c12007-05-29 21:53:49 +000034#include "llvm/ADT/Statistic.h"
Owen Anderson02e96982007-07-05 23:11:26 +000035#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
Owen Andersonbe802402007-06-08 01:03:01 +000036#include "llvm/Support/CFG.h"
Owen Anderson5fba6c12007-05-29 21:53:49 +000037#include "llvm/Support/Compiler.h"
Owen Anderson4a6ec8f2007-05-29 23:15:21 +000038#include "llvm/Support/Debug.h"
Owen Anderson5fba6c12007-05-29 21:53:49 +000039#include <algorithm>
Owen Anderson331bf6a2007-05-31 22:44:11 +000040#include <deque>
Owen Anderson5fba6c12007-05-29 21:53:49 +000041#include <map>
Owen Anderson5fba6c12007-05-29 21:53:49 +000042using namespace llvm;
43
Owen Andersonb56fba02007-06-19 03:31:41 +000044//===----------------------------------------------------------------------===//
45// ValueTable Class
46//===----------------------------------------------------------------------===//
47
Owen Andersonfd5683a2007-06-21 00:19:05 +000048/// This class holds the mapping between values and value numbers. It is used
49/// as an efficient mechanism to determine the expression-wise equivalence of
50/// two values.
Owen Andersonb56fba02007-06-19 03:31:41 +000051
Owen Anderson75a244d2007-07-19 06:13:15 +000052struct Expression {
53 enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
54 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
55 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
56 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
57 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
58 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
59 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
60 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
61 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
62 PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY,
63 TOMBSTONE };
64
65 ExpressionOpcode opcode;
66 const Type* type;
67 uint32_t firstVN;
68 uint32_t secondVN;
69 uint32_t thirdVN;
70 SmallVector<uint32_t, 4> varargs;
71
72 Expression() { }
73 Expression(ExpressionOpcode o) : opcode(o) { }
74
75 bool operator==(const Expression &other) const {
76 if (opcode != other.opcode)
77 return false;
78 else if (opcode == EMPTY || opcode == TOMBSTONE)
79 return true;
80 else if (type != other.type)
81 return false;
82 else if (firstVN != other.firstVN)
83 return false;
84 else if (secondVN != other.secondVN)
85 return false;
86 else if (thirdVN != other.thirdVN)
87 return false;
88 else {
89 if (varargs.size() != other.varargs.size())
90 return false;
91
92 for (size_t i = 0; i < varargs.size(); ++i)
93 if (varargs[i] != other.varargs[i])
94 return false;
95
96 return true;
97 }
98 }
99
100 bool operator!=(const Expression &other) const {
101 if (opcode != other.opcode)
102 return true;
103 else if (opcode == EMPTY || opcode == TOMBSTONE)
104 return false;
105 else if (type != other.type)
106 return true;
107 else if (firstVN != other.firstVN)
108 return true;
109 else if (secondVN != other.secondVN)
110 return true;
111 else if (thirdVN != other.thirdVN)
112 return true;
113 else {
114 if (varargs.size() != other.varargs.size())
115 return true;
116
117 for (size_t i = 0; i < varargs.size(); ++i)
118 if (varargs[i] != other.varargs[i])
119 return true;
120
121 return false;
122 }
123 }
124};
125
126
Owen Andersonb56fba02007-06-19 03:31:41 +0000127namespace {
128 class VISIBILITY_HIDDEN ValueTable {
Owen Andersonb56fba02007-06-19 03:31:41 +0000129 private:
Owen Anderson1ad2c102007-06-19 23:23:54 +0000130 DenseMap<Value*, uint32_t> valueNumbering;
Owen Anderson75a244d2007-07-19 06:13:15 +0000131 DenseMap<Expression, uint32_t> expressionNumbering;
Owen Andersonb56fba02007-06-19 03:31:41 +0000132
Owen Andersonb56fba02007-06-19 03:31:41 +0000133 uint32_t nextValueNumber;
134
135 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
136 Expression::ExpressionOpcode getOpcode(CmpInst* C);
Owen Anderson67799d42007-06-29 00:51:03 +0000137 Expression::ExpressionOpcode getOpcode(CastInst* C);
Owen Andersonfd5683a2007-06-21 00:19:05 +0000138 Expression create_expression(BinaryOperator* BO);
139 Expression create_expression(CmpInst* C);
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000140 Expression create_expression(ShuffleVectorInst* V);
141 Expression create_expression(ExtractElementInst* C);
142 Expression create_expression(InsertElementInst* V);
Owen Anderson8a9fa5d2007-06-28 23:51:21 +0000143 Expression create_expression(SelectInst* V);
Owen Anderson67799d42007-06-29 00:51:03 +0000144 Expression create_expression(CastInst* C);
Owen Andersonb9a494a2007-07-03 22:50:56 +0000145 Expression create_expression(GetElementPtrInst* G);
Owen Andersonb56fba02007-06-19 03:31:41 +0000146 public:
147 ValueTable() { nextValueNumber = 1; }
148 uint32_t lookup_or_add(Value* V);
Owen Anderson8a9fa5d2007-06-28 23:51:21 +0000149 uint32_t lookup(Value* V) const;
Owen Andersonb56fba02007-06-19 03:31:41 +0000150 void add(Value* V, uint32_t num);
151 void clear();
Owen Anderson91c54952007-06-19 05:37:32 +0000152 void erase(Value* v);
Owen Anderson28a2d442007-06-22 00:20:30 +0000153 unsigned size();
Owen Andersonb56fba02007-06-19 03:31:41 +0000154 };
155}
156
Owen Anderson75a244d2007-07-19 06:13:15 +0000157namespace llvm {
158template <> struct DenseMapKeyInfo<Expression> {
159 static inline Expression getEmptyKey() { return Expression(Expression::EMPTY); }
160 static inline Expression getTombstoneKey() { return Expression(Expression::TOMBSTONE); }
161
162 static unsigned getHashValue(const Expression e) {
163 unsigned hash = e.opcode;
164
165 hash = e.firstVN + hash * 37;
166 hash = e.secondVN + hash * 37;
167 hash = e.thirdVN + hash * 37;
168
169 hash = (unsigned)((uintptr_t)e.type >> 4) ^
170 (unsigned)((uintptr_t)e.type >> 9) +
171 hash * 37;
172
173 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), E = e.varargs.end();
174 I != E; ++I)
175 hash = *I + hash * 37;
176
177 return hash;
178 }
179 static bool isPod() { return true; }
180};
181}
182
Owen Andersonfd5683a2007-06-21 00:19:05 +0000183//===----------------------------------------------------------------------===//
184// ValueTable Internal Functions
185//===----------------------------------------------------------------------===//
Owen Anderson75a244d2007-07-19 06:13:15 +0000186Expression::ExpressionOpcode
Owen Andersonfd5683a2007-06-21 00:19:05 +0000187 ValueTable::getOpcode(BinaryOperator* BO) {
Owen Andersonb56fba02007-06-19 03:31:41 +0000188 switch(BO->getOpcode()) {
189 case Instruction::Add:
190 return Expression::ADD;
191 case Instruction::Sub:
192 return Expression::SUB;
193 case Instruction::Mul:
194 return Expression::MUL;
195 case Instruction::UDiv:
196 return Expression::UDIV;
197 case Instruction::SDiv:
198 return Expression::SDIV;
199 case Instruction::FDiv:
200 return Expression::FDIV;
201 case Instruction::URem:
202 return Expression::UREM;
203 case Instruction::SRem:
204 return Expression::SREM;
205 case Instruction::FRem:
206 return Expression::FREM;
207 case Instruction::Shl:
208 return Expression::SHL;
209 case Instruction::LShr:
210 return Expression::LSHR;
211 case Instruction::AShr:
212 return Expression::ASHR;
213 case Instruction::And:
214 return Expression::AND;
215 case Instruction::Or:
216 return Expression::OR;
217 case Instruction::Xor:
218 return Expression::XOR;
219
220 // THIS SHOULD NEVER HAPPEN
221 default:
222 assert(0 && "Binary operator with unknown opcode?");
223 return Expression::ADD;
224 }
225}
226
Owen Anderson75a244d2007-07-19 06:13:15 +0000227Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
Owen Andersonb56fba02007-06-19 03:31:41 +0000228 if (C->getOpcode() == Instruction::ICmp) {
229 switch (C->getPredicate()) {
230 case ICmpInst::ICMP_EQ:
231 return Expression::ICMPEQ;
232 case ICmpInst::ICMP_NE:
233 return Expression::ICMPNE;
234 case ICmpInst::ICMP_UGT:
235 return Expression::ICMPUGT;
236 case ICmpInst::ICMP_UGE:
237 return Expression::ICMPUGE;
238 case ICmpInst::ICMP_ULT:
239 return Expression::ICMPULT;
240 case ICmpInst::ICMP_ULE:
241 return Expression::ICMPULE;
242 case ICmpInst::ICMP_SGT:
243 return Expression::ICMPSGT;
244 case ICmpInst::ICMP_SGE:
245 return Expression::ICMPSGE;
246 case ICmpInst::ICMP_SLT:
247 return Expression::ICMPSLT;
248 case ICmpInst::ICMP_SLE:
249 return Expression::ICMPSLE;
250
251 // THIS SHOULD NEVER HAPPEN
252 default:
253 assert(0 && "Comparison with unknown predicate?");
254 return Expression::ICMPEQ;
255 }
256 } else {
257 switch (C->getPredicate()) {
258 case FCmpInst::FCMP_OEQ:
259 return Expression::FCMPOEQ;
260 case FCmpInst::FCMP_OGT:
261 return Expression::FCMPOGT;
262 case FCmpInst::FCMP_OGE:
263 return Expression::FCMPOGE;
264 case FCmpInst::FCMP_OLT:
265 return Expression::FCMPOLT;
266 case FCmpInst::FCMP_OLE:
267 return Expression::FCMPOLE;
268 case FCmpInst::FCMP_ONE:
269 return Expression::FCMPONE;
270 case FCmpInst::FCMP_ORD:
271 return Expression::FCMPORD;
272 case FCmpInst::FCMP_UNO:
273 return Expression::FCMPUNO;
274 case FCmpInst::FCMP_UEQ:
275 return Expression::FCMPUEQ;
276 case FCmpInst::FCMP_UGT:
277 return Expression::FCMPUGT;
278 case FCmpInst::FCMP_UGE:
279 return Expression::FCMPUGE;
280 case FCmpInst::FCMP_ULT:
281 return Expression::FCMPULT;
282 case FCmpInst::FCMP_ULE:
283 return Expression::FCMPULE;
284 case FCmpInst::FCMP_UNE:
285 return Expression::FCMPUNE;
286
287 // THIS SHOULD NEVER HAPPEN
288 default:
289 assert(0 && "Comparison with unknown predicate?");
290 return Expression::FCMPOEQ;
Owen Anderson223718c2007-06-09 18:35:31 +0000291 }
292 }
Owen Andersonb56fba02007-06-19 03:31:41 +0000293}
294
Owen Anderson75a244d2007-07-19 06:13:15 +0000295Expression::ExpressionOpcode
Owen Anderson67799d42007-06-29 00:51:03 +0000296 ValueTable::getOpcode(CastInst* C) {
297 switch(C->getOpcode()) {
298 case Instruction::Trunc:
299 return Expression::TRUNC;
300 case Instruction::ZExt:
301 return Expression::ZEXT;
302 case Instruction::SExt:
303 return Expression::SEXT;
304 case Instruction::FPToUI:
305 return Expression::FPTOUI;
306 case Instruction::FPToSI:
307 return Expression::FPTOSI;
308 case Instruction::UIToFP:
309 return Expression::UITOFP;
310 case Instruction::SIToFP:
311 return Expression::SITOFP;
312 case Instruction::FPTrunc:
313 return Expression::FPTRUNC;
314 case Instruction::FPExt:
315 return Expression::FPEXT;
316 case Instruction::PtrToInt:
317 return Expression::PTRTOINT;
318 case Instruction::IntToPtr:
319 return Expression::INTTOPTR;
320 case Instruction::BitCast:
321 return Expression::BITCAST;
322
323 // THIS SHOULD NEVER HAPPEN
324 default:
325 assert(0 && "Cast operator with unknown opcode?");
326 return Expression::BITCAST;
327 }
328}
329
Owen Anderson75a244d2007-07-19 06:13:15 +0000330Expression ValueTable::create_expression(BinaryOperator* BO) {
Owen Andersonfd5683a2007-06-21 00:19:05 +0000331 Expression e;
332
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000333 e.firstVN = lookup_or_add(BO->getOperand(0));
334 e.secondVN = lookup_or_add(BO->getOperand(1));
335 e.thirdVN = 0;
Owen Andersonc738f7c2007-06-29 00:40:05 +0000336 e.type = BO->getType();
Owen Andersonfd5683a2007-06-21 00:19:05 +0000337 e.opcode = getOpcode(BO);
338
Owen Andersonfd5683a2007-06-21 00:19:05 +0000339 return e;
340}
341
Owen Anderson75a244d2007-07-19 06:13:15 +0000342Expression ValueTable::create_expression(CmpInst* C) {
Owen Andersonfd5683a2007-06-21 00:19:05 +0000343 Expression e;
344
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000345 e.firstVN = lookup_or_add(C->getOperand(0));
346 e.secondVN = lookup_or_add(C->getOperand(1));
347 e.thirdVN = 0;
Owen Andersonc738f7c2007-06-29 00:40:05 +0000348 e.type = C->getType();
Owen Andersonfd5683a2007-06-21 00:19:05 +0000349 e.opcode = getOpcode(C);
350
Owen Andersonfd5683a2007-06-21 00:19:05 +0000351 return e;
352}
353
Owen Anderson75a244d2007-07-19 06:13:15 +0000354Expression ValueTable::create_expression(CastInst* C) {
Owen Anderson67799d42007-06-29 00:51:03 +0000355 Expression e;
356
357 e.firstVN = lookup_or_add(C->getOperand(0));
358 e.secondVN = 0;
359 e.thirdVN = 0;
360 e.type = C->getType();
361 e.opcode = getOpcode(C);
362
363 return e;
364}
365
Owen Anderson75a244d2007-07-19 06:13:15 +0000366Expression ValueTable::create_expression(ShuffleVectorInst* S) {
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000367 Expression e;
368
369 e.firstVN = lookup_or_add(S->getOperand(0));
370 e.secondVN = lookup_or_add(S->getOperand(1));
371 e.thirdVN = lookup_or_add(S->getOperand(2));
Owen Andersonc738f7c2007-06-29 00:40:05 +0000372 e.type = S->getType();
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000373 e.opcode = Expression::SHUFFLE;
374
375 return e;
376}
377
Owen Anderson75a244d2007-07-19 06:13:15 +0000378Expression ValueTable::create_expression(ExtractElementInst* E) {
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000379 Expression e;
380
381 e.firstVN = lookup_or_add(E->getOperand(0));
382 e.secondVN = lookup_or_add(E->getOperand(1));
383 e.thirdVN = 0;
Owen Andersonc738f7c2007-06-29 00:40:05 +0000384 e.type = E->getType();
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000385 e.opcode = Expression::EXTRACT;
386
387 return e;
388}
389
Owen Anderson75a244d2007-07-19 06:13:15 +0000390Expression ValueTable::create_expression(InsertElementInst* I) {
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000391 Expression e;
392
393 e.firstVN = lookup_or_add(I->getOperand(0));
394 e.secondVN = lookup_or_add(I->getOperand(1));
395 e.thirdVN = lookup_or_add(I->getOperand(2));
Owen Andersonc738f7c2007-06-29 00:40:05 +0000396 e.type = I->getType();
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000397 e.opcode = Expression::INSERT;
398
399 return e;
400}
401
Owen Anderson75a244d2007-07-19 06:13:15 +0000402Expression ValueTable::create_expression(SelectInst* I) {
Owen Anderson8a9fa5d2007-06-28 23:51:21 +0000403 Expression e;
404
405 e.firstVN = lookup_or_add(I->getCondition());
406 e.secondVN = lookup_or_add(I->getTrueValue());
407 e.thirdVN = lookup_or_add(I->getFalseValue());
Owen Andersonc738f7c2007-06-29 00:40:05 +0000408 e.type = I->getType();
Owen Anderson8a9fa5d2007-06-28 23:51:21 +0000409 e.opcode = Expression::SELECT;
410
411 return e;
412}
413
Owen Anderson75a244d2007-07-19 06:13:15 +0000414Expression ValueTable::create_expression(GetElementPtrInst* G) {
Owen Andersonb9a494a2007-07-03 22:50:56 +0000415 Expression e;
416
417 e.firstVN = lookup_or_add(G->getPointerOperand());
418 e.secondVN = 0;
419 e.thirdVN = 0;
420 e.type = G->getType();
421 e.opcode = Expression::SELECT;
422
423 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
424 I != E; ++I)
425 e.varargs.push_back(lookup_or_add(*I));
426
427 return e;
428}
429
Owen Andersonfd5683a2007-06-21 00:19:05 +0000430//===----------------------------------------------------------------------===//
431// ValueTable External Functions
432//===----------------------------------------------------------------------===//
433
434/// lookup_or_add - Returns the value number for the specified value, assigning
435/// it a new number if it did not have one before.
Owen Andersonb56fba02007-06-19 03:31:41 +0000436uint32_t ValueTable::lookup_or_add(Value* V) {
Owen Anderson1ad2c102007-06-19 23:23:54 +0000437 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
Owen Andersonb56fba02007-06-19 03:31:41 +0000438 if (VI != valueNumbering.end())
439 return VI->second;
Owen Anderson223718c2007-06-09 18:35:31 +0000440
Owen Anderson223718c2007-06-09 18:35:31 +0000441
Owen Andersonb56fba02007-06-19 03:31:41 +0000442 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
443 Expression e = create_expression(BO);
444
Owen Anderson75a244d2007-07-19 06:13:15 +0000445 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Andersonb56fba02007-06-19 03:31:41 +0000446 if (EI != expressionNumbering.end()) {
447 valueNumbering.insert(std::make_pair(V, EI->second));
448 return EI->second;
449 } else {
450 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
451 valueNumbering.insert(std::make_pair(V, nextValueNumber));
452
453 return nextValueNumber++;
454 }
455 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
456 Expression e = create_expression(C);
457
Owen Anderson75a244d2007-07-19 06:13:15 +0000458 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Andersonb56fba02007-06-19 03:31:41 +0000459 if (EI != expressionNumbering.end()) {
460 valueNumbering.insert(std::make_pair(V, EI->second));
461 return EI->second;
462 } else {
463 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
464 valueNumbering.insert(std::make_pair(V, nextValueNumber));
465
466 return nextValueNumber++;
467 }
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000468 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
469 Expression e = create_expression(U);
470
Owen Anderson75a244d2007-07-19 06:13:15 +0000471 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000472 if (EI != expressionNumbering.end()) {
473 valueNumbering.insert(std::make_pair(V, EI->second));
474 return EI->second;
475 } else {
476 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
477 valueNumbering.insert(std::make_pair(V, nextValueNumber));
478
479 return nextValueNumber++;
480 }
481 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
482 Expression e = create_expression(U);
483
Owen Anderson75a244d2007-07-19 06:13:15 +0000484 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000485 if (EI != expressionNumbering.end()) {
486 valueNumbering.insert(std::make_pair(V, EI->second));
487 return EI->second;
488 } else {
489 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
490 valueNumbering.insert(std::make_pair(V, nextValueNumber));
491
492 return nextValueNumber++;
493 }
494 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
495 Expression e = create_expression(U);
496
Owen Anderson75a244d2007-07-19 06:13:15 +0000497 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000498 if (EI != expressionNumbering.end()) {
499 valueNumbering.insert(std::make_pair(V, EI->second));
500 return EI->second;
501 } else {
502 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
503 valueNumbering.insert(std::make_pair(V, nextValueNumber));
504
505 return nextValueNumber++;
506 }
Owen Anderson8a9fa5d2007-06-28 23:51:21 +0000507 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
508 Expression e = create_expression(U);
509
Owen Anderson75a244d2007-07-19 06:13:15 +0000510 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Anderson8a9fa5d2007-06-28 23:51:21 +0000511 if (EI != expressionNumbering.end()) {
512 valueNumbering.insert(std::make_pair(V, EI->second));
513 return EI->second;
514 } else {
515 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
516 valueNumbering.insert(std::make_pair(V, nextValueNumber));
517
518 return nextValueNumber++;
519 }
Owen Anderson67799d42007-06-29 00:51:03 +0000520 } else if (CastInst* U = dyn_cast<CastInst>(V)) {
521 Expression e = create_expression(U);
522
Owen Anderson75a244d2007-07-19 06:13:15 +0000523 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Anderson67799d42007-06-29 00:51:03 +0000524 if (EI != expressionNumbering.end()) {
525 valueNumbering.insert(std::make_pair(V, EI->second));
526 return EI->second;
527 } else {
528 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
529 valueNumbering.insert(std::make_pair(V, nextValueNumber));
530
531 return nextValueNumber++;
532 }
Owen Anderson2e4b6fea2007-07-03 23:51:19 +0000533 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
534 Expression e = create_expression(U);
535
Owen Anderson75a244d2007-07-19 06:13:15 +0000536 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
Owen Anderson2e4b6fea2007-07-03 23:51:19 +0000537 if (EI != expressionNumbering.end()) {
538 valueNumbering.insert(std::make_pair(V, EI->second));
539 return EI->second;
540 } else {
541 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
542 valueNumbering.insert(std::make_pair(V, nextValueNumber));
543
544 return nextValueNumber++;
545 }
Owen Andersonb56fba02007-06-19 03:31:41 +0000546 } else {
547 valueNumbering.insert(std::make_pair(V, nextValueNumber));
548 return nextValueNumber++;
Owen Anderson0b68cda2007-06-03 05:55:58 +0000549 }
Owen Andersonb56fba02007-06-19 03:31:41 +0000550}
551
Owen Andersonfd5683a2007-06-21 00:19:05 +0000552/// lookup - Returns the value number of the specified value. Fails if
553/// the value has not yet been numbered.
Owen Anderson8a9fa5d2007-06-28 23:51:21 +0000554uint32_t ValueTable::lookup(Value* V) const {
Owen Anderson1ad2c102007-06-19 23:23:54 +0000555 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
Owen Andersonb56fba02007-06-19 03:31:41 +0000556 if (VI != valueNumbering.end())
557 return VI->second;
558 else
559 assert(0 && "Value not numbered?");
560
561 return 0;
562}
563
Owen Andersonfd5683a2007-06-21 00:19:05 +0000564/// add - Add the specified value with the given value number, removing
565/// its old number, if any
Owen Andersonb56fba02007-06-19 03:31:41 +0000566void ValueTable::add(Value* V, uint32_t num) {
Owen Anderson1ad2c102007-06-19 23:23:54 +0000567 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
Owen Andersonb56fba02007-06-19 03:31:41 +0000568 if (VI != valueNumbering.end())
569 valueNumbering.erase(VI);
570 valueNumbering.insert(std::make_pair(V, num));
571}
572
Owen Anderson191eb062007-06-25 05:41:12 +0000573/// clear - Remove all entries from the ValueTable
Owen Andersonb56fba02007-06-19 03:31:41 +0000574void ValueTable::clear() {
575 valueNumbering.clear();
576 expressionNumbering.clear();
577 nextValueNumber = 1;
578}
Owen Anderson0b68cda2007-06-03 05:55:58 +0000579
Owen Anderson191eb062007-06-25 05:41:12 +0000580/// erase - Remove a value from the value numbering
Owen Anderson91c54952007-06-19 05:37:32 +0000581void ValueTable::erase(Value* V) {
Owen Anderson91c54952007-06-19 05:37:32 +0000582 valueNumbering.erase(V);
Owen Anderson91c54952007-06-19 05:37:32 +0000583}
584
Owen Anderson28a2d442007-06-22 00:20:30 +0000585/// size - Return the number of assigned value numbers
586unsigned ValueTable::size() {
587 // NOTE: zero is never assigned
588 return nextValueNumber;
589}
590
Owen Andersonfd5683a2007-06-21 00:19:05 +0000591//===----------------------------------------------------------------------===//
Owen Anderson56b01eb2007-07-09 16:43:55 +0000592// ValueNumberedSet Class
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000593//===----------------------------------------------------------------------===//
594
595class ValueNumberedSet {
596 private:
597 SmallPtrSet<Value*, 8> contents;
598 BitVector numbers;
599 public:
600 ValueNumberedSet() { numbers.resize(1); }
Owen Anderson4c4b2382007-07-10 00:27:22 +0000601 ValueNumberedSet(const ValueNumberedSet& other) {
602 numbers = other.numbers;
603 contents = other.contents;
604 }
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000605
606 typedef SmallPtrSet<Value*, 8>::iterator iterator;
607
608 iterator begin() { return contents.begin(); }
609 iterator end() { return contents.end(); }
610
611 bool insert(Value* v) { return contents.insert(v); }
612 void insert(iterator I, iterator E) { contents.insert(I, E); }
613 void erase(Value* v) { contents.erase(v); }
Owen Anderson41c2cab2007-07-10 00:09:25 +0000614 unsigned count(Value* v) { return contents.count(v); }
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000615 size_t size() { return contents.size(); }
616
Owen Anderson267ba452007-07-09 07:56:55 +0000617 void set(unsigned i) {
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000618 if (i >= numbers.size())
619 numbers.resize(i+1);
620
621 numbers.set(i);
622 }
623
Owen Andersoneffc7a72007-07-09 22:29:50 +0000624 void operator=(const ValueNumberedSet& other) {
625 contents = other.contents;
Owen Anderson267ba452007-07-09 07:56:55 +0000626 numbers = other.numbers;
627 }
628
629 void reset(unsigned i) {
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000630 if (i < numbers.size())
631 numbers.reset(i);
632 }
633
Owen Anderson267ba452007-07-09 07:56:55 +0000634 bool test(unsigned i) {
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000635 if (i >= numbers.size())
636 return false;
637
638 return numbers.test(i);
639 }
640
641 void clear() {
642 contents.clear();
643 numbers.clear();
644 }
645};
646
647//===----------------------------------------------------------------------===//
Owen Andersonfd5683a2007-06-21 00:19:05 +0000648// GVNPRE Pass
649//===----------------------------------------------------------------------===//
650
Owen Anderson5fba6c12007-05-29 21:53:49 +0000651namespace {
652
653 class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
654 bool runOnFunction(Function &F);
655 public:
656 static char ID; // Pass identification, replacement for typeid
Owen Andersonb9cbaed2007-06-19 04:32:55 +0000657 GVNPRE() : FunctionPass((intptr_t)&ID) { }
Owen Anderson5fba6c12007-05-29 21:53:49 +0000658
659 private:
Owen Andersonbe802402007-06-08 01:03:01 +0000660 ValueTable VN;
Owen Anderson6aa17f12007-07-19 06:37:56 +0000661 SmallVector<Instruction*, 8> createdExpressions;
Owen Anderson81d156e2007-05-31 00:42:15 +0000662
Owen Anderson4c4b2382007-07-10 00:27:22 +0000663 DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
664 DenseMap<BasicBlock*, ValueNumberedSet> anticipatedIn;
665 DenseMap<BasicBlock*, ValueNumberedSet> generatedPhis;
Owen Anderson4036ad42007-06-12 22:43:57 +0000666
Owen Andersonfd5683a2007-06-21 00:19:05 +0000667 // This transformation requires dominator postdominator info
Owen Anderson5fba6c12007-05-29 21:53:49 +0000668 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
669 AU.setPreservesCFG();
Owen Anderson3c3dd902007-07-06 18:12:36 +0000670 AU.addRequiredID(BreakCriticalEdgesID);
Owen Anderson02e96982007-07-05 23:11:26 +0000671 AU.addRequired<UnifyFunctionExitNodes>();
Owen Anderson5fba6c12007-05-29 21:53:49 +0000672 AU.addRequired<DominatorTree>();
Owen Anderson5fba6c12007-05-29 21:53:49 +0000673 }
674
675 // Helper fuctions
676 // FIXME: eliminate or document these better
Owen Anderson267ba452007-07-09 07:56:55 +0000677 void dump(ValueNumberedSet& s) const ;
678 void clean(ValueNumberedSet& set) ;
679 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ;
680 Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) ;
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000681 void phi_translate_set(ValueNumberedSet& anticIn, BasicBlock* pred,
Owen Anderson267ba452007-07-09 07:56:55 +0000682 BasicBlock* succ, ValueNumberedSet& out) ;
Owen Anderson5fba6c12007-05-29 21:53:49 +0000683
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000684 void topo_sort(ValueNumberedSet& set,
Owen Anderson6aa17f12007-07-19 06:37:56 +0000685 SmallVector<Value*, 8>& vec) ;
Owen Anderson331bf6a2007-05-31 22:44:11 +0000686
Owen Anderson267ba452007-07-09 07:56:55 +0000687 void cleanup() ;
688 bool elimination() ;
Owen Andersondd998e12007-06-18 04:42:29 +0000689
Owen Anderson267ba452007-07-09 07:56:55 +0000690 void val_insert(ValueNumberedSet& s, Value* v) ;
691 void val_replace(ValueNumberedSet& s, Value* v) ;
692 bool dependsOnInvoke(Value* V) ;
Owen Anderson06c1e582007-06-20 22:10:02 +0000693 void buildsets_availout(BasicBlock::iterator I,
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000694 ValueNumberedSet& currAvail,
695 ValueNumberedSet& currPhis,
696 ValueNumberedSet& currExps,
Owen Anderson6aa17f12007-07-19 06:37:56 +0000697 SmallPtrSet<Value*, 16>& currTemps);
Owen Anderson28a2d442007-06-22 00:20:30 +0000698 bool buildsets_anticout(BasicBlock* BB,
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000699 ValueNumberedSet& anticOut,
Owen Anderson6aa17f12007-07-19 06:37:56 +0000700 SmallPtrSet<BasicBlock*, 8>& visited);
Owen Anderson28a2d442007-06-22 00:20:30 +0000701 unsigned buildsets_anticin(BasicBlock* BB,
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000702 ValueNumberedSet& anticOut,
703 ValueNumberedSet& currExps,
Owen Andersone02da552007-06-28 00:34:34 +0000704 SmallPtrSet<Value*, 16>& currTemps,
Owen Anderson6aa17f12007-07-19 06:37:56 +0000705 SmallPtrSet<BasicBlock*, 8>& visited);
Owen Anderson267ba452007-07-09 07:56:55 +0000706 void buildsets(Function& F) ;
Owen Anderson06c1e582007-06-20 22:10:02 +0000707
708 void insertion_pre(Value* e, BasicBlock* BB,
Owen Anderson6aa17f12007-07-19 06:37:56 +0000709 DenseMap<BasicBlock*, Value*>& avail,
710 std::map<BasicBlock*,ValueNumberedSet>& new_set);
711 unsigned insertion_mergepoint(SmallVector<Value*, 8>& workList,
Owen Anderson28a2d442007-06-22 00:20:30 +0000712 df_iterator<DomTreeNode*>& D,
Owen Anderson6aa17f12007-07-19 06:37:56 +0000713 std::map<BasicBlock*, ValueNumberedSet>& new_set);
Owen Anderson267ba452007-07-09 07:56:55 +0000714 bool insertion(Function& F) ;
Owen Anderson5fba6c12007-05-29 21:53:49 +0000715
716 };
717
718 char GVNPRE::ID = 0;
719
720}
721
Owen Andersonfd5683a2007-06-21 00:19:05 +0000722// createGVNPREPass - The public interface to this file...
Owen Anderson5fba6c12007-05-29 21:53:49 +0000723FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
724
Owen Anderson084d3c22007-07-10 20:20:19 +0000725static RegisterPass<GVNPRE> X("gvnpre",
726 "Global Value Numbering/Partial Redundancy Elimination");
Owen Anderson5fba6c12007-05-29 21:53:49 +0000727
Owen Anderson5fba6c12007-05-29 21:53:49 +0000728
Owen Anderson7d76b2a2007-06-08 22:02:36 +0000729STATISTIC(NumInsertedVals, "Number of values inserted");
730STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
731STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
732
Owen Andersonfd5683a2007-06-21 00:19:05 +0000733/// find_leader - Given a set and a value number, return the first
734/// element of the set with that value number, or 0 if no such element
735/// is present
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000736Value* GVNPRE::find_leader(ValueNumberedSet& vals, uint32_t v) {
737 if (!vals.test(v))
738 return 0;
739
740 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
Owen Andersonb56fba02007-06-19 03:31:41 +0000741 I != E; ++I)
742 if (v == VN.lookup(*I))
Owen Anderson0b68cda2007-06-03 05:55:58 +0000743 return *I;
Owen Anderson5fba6c12007-05-29 21:53:49 +0000744
Owen Anderson7ee197e2007-07-09 23:57:18 +0000745 assert(0 && "No leader found, but present bit is set?");
Owen Anderson0b68cda2007-06-03 05:55:58 +0000746 return 0;
Owen Anderson5fba6c12007-05-29 21:53:49 +0000747}
748
Owen Andersonfd5683a2007-06-21 00:19:05 +0000749/// val_insert - Insert a value into a set only if there is not a value
750/// with the same value number already in the set
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000751void GVNPRE::val_insert(ValueNumberedSet& s, Value* v) {
Owen Andersonb56fba02007-06-19 03:31:41 +0000752 uint32_t num = VN.lookup(v);
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000753 if (!s.test(num))
Owen Andersonb56fba02007-06-19 03:31:41 +0000754 s.insert(v);
755}
756
Owen Andersonfd5683a2007-06-21 00:19:05 +0000757/// val_replace - Insert a value into a set, replacing any values already in
758/// the set that have the same value number
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000759void GVNPRE::val_replace(ValueNumberedSet& s, Value* v) {
Owen Andersonb56fba02007-06-19 03:31:41 +0000760 uint32_t num = VN.lookup(v);
761 Value* leader = find_leader(s, num);
Owen Andersoneffc7a72007-07-09 22:29:50 +0000762 if (leader != 0)
Owen Andersonb56fba02007-06-19 03:31:41 +0000763 s.erase(leader);
Owen Andersonb56fba02007-06-19 03:31:41 +0000764 s.insert(v);
Owen Andersoneffc7a72007-07-09 22:29:50 +0000765 s.set(num);
Owen Andersonb56fba02007-06-19 03:31:41 +0000766}
767
Owen Andersonfd5683a2007-06-21 00:19:05 +0000768/// phi_translate - Given a value, its parent block, and a predecessor of its
769/// parent, translate the value into legal for the predecessor block. This
770/// means translating its operands (and recursively, their operands) through
771/// any phi nodes in the parent into values available in the predecessor
Owen Anderson4036ad42007-06-12 22:43:57 +0000772Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
Owen Anderson38b6b222007-06-04 18:05:26 +0000773 if (V == 0)
774 return 0;
775
Owen Anderson59bd0532007-07-03 18:37:08 +0000776 // Unary Operations
Owen Anderson6b958c72007-07-03 19:01:42 +0000777 if (CastInst* U = dyn_cast<CastInst>(V)) {
Owen Anderson59bd0532007-07-03 18:37:08 +0000778 Value* newOp1 = 0;
779 if (isa<Instruction>(U->getOperand(0)))
780 newOp1 = phi_translate(U->getOperand(0), pred, succ);
781 else
782 newOp1 = U->getOperand(0);
783
784 if (newOp1 == 0)
785 return 0;
786
787 if (newOp1 != U->getOperand(0)) {
788 Instruction* newVal = 0;
789 if (CastInst* C = dyn_cast<CastInst>(U))
790 newVal = CastInst::create(C->getOpcode(),
791 newOp1, C->getType(),
792 C->getName()+".expr");
793
794 uint32_t v = VN.lookup_or_add(newVal);
795
796 Value* leader = find_leader(availableOut[pred], v);
797 if (leader == 0) {
798 createdExpressions.push_back(newVal);
799 return newVal;
800 } else {
801 VN.erase(newVal);
802 delete newVal;
803 return leader;
804 }
805 }
806
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000807 // Binary Operations
Owen Anderson59bd0532007-07-03 18:37:08 +0000808 } if (isa<BinaryOperator>(V) || isa<CmpInst>(V) ||
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000809 isa<ExtractElementInst>(V)) {
Owen Anderson191eb062007-06-25 05:41:12 +0000810 User* U = cast<User>(V);
811
Owen Andersonb56fba02007-06-19 03:31:41 +0000812 Value* newOp1 = 0;
Owen Anderson191eb062007-06-25 05:41:12 +0000813 if (isa<Instruction>(U->getOperand(0)))
814 newOp1 = phi_translate(U->getOperand(0), pred, succ);
Owen Andersonb56fba02007-06-19 03:31:41 +0000815 else
Owen Anderson191eb062007-06-25 05:41:12 +0000816 newOp1 = U->getOperand(0);
Owen Andersonb56fba02007-06-19 03:31:41 +0000817
Owen Anderson38b6b222007-06-04 18:05:26 +0000818 if (newOp1 == 0)
819 return 0;
820
Owen Andersonb56fba02007-06-19 03:31:41 +0000821 Value* newOp2 = 0;
Owen Anderson191eb062007-06-25 05:41:12 +0000822 if (isa<Instruction>(U->getOperand(1)))
823 newOp2 = phi_translate(U->getOperand(1), pred, succ);
Owen Andersonb56fba02007-06-19 03:31:41 +0000824 else
Owen Anderson191eb062007-06-25 05:41:12 +0000825 newOp2 = U->getOperand(1);
Owen Andersonb56fba02007-06-19 03:31:41 +0000826
Owen Anderson38b6b222007-06-04 18:05:26 +0000827 if (newOp2 == 0)
828 return 0;
829
Owen Anderson191eb062007-06-25 05:41:12 +0000830 if (newOp1 != U->getOperand(0) || newOp2 != U->getOperand(1)) {
831 Instruction* newVal = 0;
832 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
833 newVal = BinaryOperator::create(BO->getOpcode(),
834 newOp1, newOp2,
835 BO->getName()+".expr");
836 else if (CmpInst* C = dyn_cast<CmpInst>(U))
837 newVal = CmpInst::create(C->getOpcode(),
838 C->getPredicate(),
839 newOp1, newOp2,
840 C->getName()+".expr");
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000841 else if (ExtractElementInst* E = dyn_cast<ExtractElementInst>(U))
842 newVal = new ExtractElementInst(newOp1, newOp2, E->getName()+".expr");
Owen Anderson55994f22007-06-08 20:44:02 +0000843
Owen Andersonb56fba02007-06-19 03:31:41 +0000844 uint32_t v = VN.lookup_or_add(newVal);
Owen Anderson4036ad42007-06-12 22:43:57 +0000845
Owen Andersonb56fba02007-06-19 03:31:41 +0000846 Value* leader = find_leader(availableOut[pred], v);
Owen Anderson4036ad42007-06-12 22:43:57 +0000847 if (leader == 0) {
Owen Andersona75dd4d2007-06-12 00:50:47 +0000848 createdExpressions.push_back(newVal);
Owen Anderson38b6b222007-06-04 18:05:26 +0000849 return newVal;
Owen Andersonc8472092007-06-05 22:11:49 +0000850 } else {
Owen Anderson91c54952007-06-19 05:37:32 +0000851 VN.erase(newVal);
Owen Andersonc8472092007-06-05 22:11:49 +0000852 delete newVal;
Owen Anderson4036ad42007-06-12 22:43:57 +0000853 return leader;
Owen Andersonc8472092007-06-05 22:11:49 +0000854 }
Owen Anderson38b6b222007-06-04 18:05:26 +0000855 }
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000856
857 // Ternary Operations
Owen Anderson8a9fa5d2007-06-28 23:51:21 +0000858 } else if (isa<ShuffleVectorInst>(V) || isa<InsertElementInst>(V) ||
859 isa<SelectInst>(V)) {
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000860 User* U = cast<User>(V);
861
862 Value* newOp1 = 0;
863 if (isa<Instruction>(U->getOperand(0)))
864 newOp1 = phi_translate(U->getOperand(0), pred, succ);
865 else
866 newOp1 = U->getOperand(0);
867
868 if (newOp1 == 0)
869 return 0;
870
871 Value* newOp2 = 0;
872 if (isa<Instruction>(U->getOperand(1)))
873 newOp2 = phi_translate(U->getOperand(1), pred, succ);
874 else
875 newOp2 = U->getOperand(1);
876
877 if (newOp2 == 0)
878 return 0;
879
880 Value* newOp3 = 0;
881 if (isa<Instruction>(U->getOperand(2)))
882 newOp3 = phi_translate(U->getOperand(2), pred, succ);
883 else
884 newOp3 = U->getOperand(2);
885
886 if (newOp3 == 0)
887 return 0;
888
889 if (newOp1 != U->getOperand(0) ||
890 newOp2 != U->getOperand(1) ||
891 newOp3 != U->getOperand(2)) {
892 Instruction* newVal = 0;
893 if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
894 newVal = new ShuffleVectorInst(newOp1, newOp2, newOp3,
895 S->getName()+".expr");
896 else if (InsertElementInst* I = dyn_cast<InsertElementInst>(U))
897 newVal = new InsertElementInst(newOp1, newOp2, newOp3,
898 I->getName()+".expr");
Owen Anderson8a9fa5d2007-06-28 23:51:21 +0000899 else if (SelectInst* I = dyn_cast<SelectInst>(U))
900 newVal = new SelectInst(newOp1, newOp2, newOp3, I->getName()+".expr");
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000901
902 uint32_t v = VN.lookup_or_add(newVal);
903
904 Value* leader = find_leader(availableOut[pred], v);
905 if (leader == 0) {
906 createdExpressions.push_back(newVal);
907 return newVal;
908 } else {
909 VN.erase(newVal);
910 delete newVal;
911 return leader;
912 }
913 }
914
Owen Anderson2e4b6fea2007-07-03 23:51:19 +0000915 // Varargs operators
916 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
917 Value* newOp1 = 0;
918 if (isa<Instruction>(U->getPointerOperand()))
919 newOp1 = phi_translate(U->getPointerOperand(), pred, succ);
920 else
921 newOp1 = U->getPointerOperand();
922
923 if (newOp1 == 0)
924 return 0;
925
926 bool changed_idx = false;
Owen Anderson6aa17f12007-07-19 06:37:56 +0000927 SmallVector<Value*, 4> newIdx;
Owen Anderson2e4b6fea2007-07-03 23:51:19 +0000928 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
929 I != E; ++I)
930 if (isa<Instruction>(*I)) {
931 Value* newVal = phi_translate(*I, pred, succ);
932 newIdx.push_back(newVal);
933 if (newVal != *I)
934 changed_idx = true;
935 } else {
936 newIdx.push_back(*I);
937 }
938
939 if (newOp1 != U->getPointerOperand() || changed_idx) {
Owen Anderson664e2602007-07-04 04:51:16 +0000940 Instruction* newVal = new GetElementPtrInst(newOp1,
Owen Anderson2e4b6fea2007-07-03 23:51:19 +0000941 &newIdx[0], newIdx.size(),
942 U->getName()+".expr");
943
944 uint32_t v = VN.lookup_or_add(newVal);
945
946 Value* leader = find_leader(availableOut[pred], v);
947 if (leader == 0) {
948 createdExpressions.push_back(newVal);
949 return newVal;
950 } else {
951 VN.erase(newVal);
952 delete newVal;
953 return leader;
954 }
955 }
956
Owen Andersonb6a39fc2007-06-27 04:10:46 +0000957 // PHI Nodes
Owen Anderson38b6b222007-06-04 18:05:26 +0000958 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
Owen Andersona75dd4d2007-06-12 00:50:47 +0000959 if (P->getParent() == succ)
Owen Anderson38b6b222007-06-04 18:05:26 +0000960 return P->getIncomingValueForBlock(pred);
961 }
962
963 return V;
964}
965
Owen Andersonfd5683a2007-06-21 00:19:05 +0000966/// phi_translate_set - Perform phi translation on every element of a set
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000967void GVNPRE::phi_translate_set(ValueNumberedSet& anticIn,
Owen Andersona75dd4d2007-06-12 00:50:47 +0000968 BasicBlock* pred, BasicBlock* succ,
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000969 ValueNumberedSet& out) {
970 for (ValueNumberedSet::iterator I = anticIn.begin(),
Owen Anderson38b6b222007-06-04 18:05:26 +0000971 E = anticIn.end(); I != E; ++I) {
Owen Anderson4036ad42007-06-12 22:43:57 +0000972 Value* V = phi_translate(*I, pred, succ);
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000973 if (V != 0 && !out.test(VN.lookup_or_add(V))) {
Owen Anderson38b6b222007-06-04 18:05:26 +0000974 out.insert(V);
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000975 out.set(VN.lookup(V));
976 }
Owen Anderson5fba6c12007-05-29 21:53:49 +0000977 }
978}
979
Owen Andersonfd5683a2007-06-21 00:19:05 +0000980/// dependsOnInvoke - Test if a value has an phi node as an operand, any of
981/// whose inputs is an invoke instruction. If this is true, we cannot safely
982/// PRE the instruction or anything that depends on it.
Owen Andersondd998e12007-06-18 04:42:29 +0000983bool GVNPRE::dependsOnInvoke(Value* V) {
Owen Anderson2320d432007-06-19 23:07:16 +0000984 if (PHINode* p = dyn_cast<PHINode>(V)) {
985 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
986 if (isa<InvokeInst>(*I))
Owen Andersondd998e12007-06-18 04:42:29 +0000987 return true;
Owen Anderson2320d432007-06-19 23:07:16 +0000988 return false;
989 } else {
990 return false;
Owen Anderson658f2c42007-06-16 00:26:54 +0000991 }
Owen Anderson658f2c42007-06-16 00:26:54 +0000992}
993
Owen Andersonfd5683a2007-06-21 00:19:05 +0000994/// clean - Remove all non-opaque values from the set whose operands are not
995/// themselves in the set, as well as all values that depend on invokes (see
996/// above)
Owen Anderson1c83b5d2007-07-09 06:50:06 +0000997void GVNPRE::clean(ValueNumberedSet& set) {
Owen Anderson6aa17f12007-07-19 06:37:56 +0000998 SmallVector<Value*, 8> worklist;
Owen Andersond50a29d2007-06-22 00:43:22 +0000999 worklist.reserve(set.size());
Owen Andersonbe802402007-06-08 01:03:01 +00001000 topo_sort(set, worklist);
Owen Anderson5fba6c12007-05-29 21:53:49 +00001001
Owen Andersonbe802402007-06-08 01:03:01 +00001002 for (unsigned i = 0; i < worklist.size(); ++i) {
1003 Value* v = worklist[i];
Owen Anderson5fba6c12007-05-29 21:53:49 +00001004
Owen Anderson59bd0532007-07-03 18:37:08 +00001005 // Handle unary ops
Owen Anderson6b958c72007-07-03 19:01:42 +00001006 if (CastInst* U = dyn_cast<CastInst>(v)) {
Owen Anderson59bd0532007-07-03 18:37:08 +00001007 bool lhsValid = !isa<Instruction>(U->getOperand(0));
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001008 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
Owen Anderson59bd0532007-07-03 18:37:08 +00001009 if (lhsValid)
1010 lhsValid = !dependsOnInvoke(U->getOperand(0));
1011
1012 if (!lhsValid) {
1013 set.erase(U);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001014 set.reset(VN.lookup(U));
Owen Anderson59bd0532007-07-03 18:37:08 +00001015 }
1016
Owen Anderson0eb26572007-06-27 17:03:03 +00001017 // Handle binary ops
Owen Anderson59bd0532007-07-03 18:37:08 +00001018 } else if (isa<BinaryOperator>(v) || isa<CmpInst>(v) ||
Owen Anderson0eb26572007-06-27 17:03:03 +00001019 isa<ExtractElementInst>(v)) {
1020 User* U = cast<User>(v);
1021
1022 bool lhsValid = !isa<Instruction>(U->getOperand(0));
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001023 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
Owen Andersonb364b412007-06-18 04:30:44 +00001024 if (lhsValid)
Owen Anderson0eb26572007-06-27 17:03:03 +00001025 lhsValid = !dependsOnInvoke(U->getOperand(0));
Owen Anderson0b68cda2007-06-03 05:55:58 +00001026
Owen Anderson0eb26572007-06-27 17:03:03 +00001027 bool rhsValid = !isa<Instruction>(U->getOperand(1));
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001028 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
Owen Andersonb364b412007-06-18 04:30:44 +00001029 if (rhsValid)
Owen Anderson0eb26572007-06-27 17:03:03 +00001030 rhsValid = !dependsOnInvoke(U->getOperand(1));
Owen Anderson5fba6c12007-05-29 21:53:49 +00001031
Owen Anderson7dae8ef2007-06-27 17:38:29 +00001032 if (!lhsValid || !rhsValid) {
Owen Anderson0eb26572007-06-27 17:03:03 +00001033 set.erase(U);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001034 set.reset(VN.lookup(U));
Owen Anderson7dae8ef2007-06-27 17:38:29 +00001035 }
Owen Anderson223718c2007-06-09 18:35:31 +00001036
Owen Anderson0eb26572007-06-27 17:03:03 +00001037 // Handle ternary ops
Owen Anderson8a9fa5d2007-06-28 23:51:21 +00001038 } else if (isa<ShuffleVectorInst>(v) || isa<InsertElementInst>(v) ||
1039 isa<SelectInst>(v)) {
Owen Anderson0eb26572007-06-27 17:03:03 +00001040 User* U = cast<User>(v);
1041
1042 bool lhsValid = !isa<Instruction>(U->getOperand(0));
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001043 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001044 if (lhsValid)
Owen Anderson0eb26572007-06-27 17:03:03 +00001045 lhsValid = !dependsOnInvoke(U->getOperand(0));
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001046
Owen Anderson0eb26572007-06-27 17:03:03 +00001047 bool rhsValid = !isa<Instruction>(U->getOperand(1));
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001048 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001049 if (rhsValid)
Owen Anderson0eb26572007-06-27 17:03:03 +00001050 rhsValid = !dependsOnInvoke(U->getOperand(1));
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001051
Owen Anderson0eb26572007-06-27 17:03:03 +00001052 bool thirdValid = !isa<Instruction>(U->getOperand(2));
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001053 thirdValid |= set.test(VN.lookup(U->getOperand(2)));
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001054 if (thirdValid)
Owen Anderson0eb26572007-06-27 17:03:03 +00001055 thirdValid = !dependsOnInvoke(U->getOperand(2));
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001056
Owen Anderson7dae8ef2007-06-27 17:38:29 +00001057 if (!lhsValid || !rhsValid || !thirdValid) {
Owen Anderson0eb26572007-06-27 17:03:03 +00001058 set.erase(U);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001059 set.reset(VN.lookup(U));
Owen Anderson7dae8ef2007-06-27 17:38:29 +00001060 }
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001061
1062 // Handle varargs ops
1063 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(v)) {
1064 bool ptrValid = !isa<Instruction>(U->getPointerOperand());
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001065 ptrValid |= set.test(VN.lookup(U->getPointerOperand()));
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001066 if (ptrValid)
1067 ptrValid = !dependsOnInvoke(U->getPointerOperand());
1068
1069 bool varValid = true;
1070 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
1071 I != E; ++I)
1072 if (varValid) {
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001073 varValid &= !isa<Instruction>(*I) || set.test(VN.lookup(*I));
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001074 varValid &= !dependsOnInvoke(*I);
1075 }
1076
1077 if (!ptrValid || !varValid) {
1078 set.erase(U);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001079 set.reset(VN.lookup(U));
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001080 }
Owen Anderson0b68cda2007-06-03 05:55:58 +00001081 }
Owen Anderson5fba6c12007-05-29 21:53:49 +00001082 }
1083}
1084
Owen Andersonfd5683a2007-06-21 00:19:05 +00001085/// topo_sort - Given a set of values, sort them by topological
1086/// order into the provided vector.
Owen Anderson6aa17f12007-07-19 06:37:56 +00001087void GVNPRE::topo_sort(ValueNumberedSet& set, SmallVector<Value*, 8>& vec) {
Owen Andersone02da552007-06-28 00:34:34 +00001088 SmallPtrSet<Value*, 16> visited;
Owen Anderson6aa17f12007-07-19 06:37:56 +00001089 SmallVector<Value*, 8> stack;
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001090 for (ValueNumberedSet::iterator I = set.begin(), E = set.end();
Owen Anderson49409f62007-06-22 21:31:16 +00001091 I != E; ++I) {
1092 if (visited.count(*I) == 0)
1093 stack.push_back(*I);
1094
1095 while (!stack.empty()) {
1096 Value* e = stack.back();
Owen Anderson59bd0532007-07-03 18:37:08 +00001097
1098 // Handle unary ops
Owen Anderson6b958c72007-07-03 19:01:42 +00001099 if (CastInst* U = dyn_cast<CastInst>(e)) {
Owen Anderson59bd0532007-07-03 18:37:08 +00001100 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1101
1102 if (l != 0 && isa<Instruction>(l) &&
1103 visited.count(l) == 0)
1104 stack.push_back(l);
1105 else {
1106 vec.push_back(e);
1107 visited.insert(e);
1108 stack.pop_back();
1109 }
1110
Owen Anderson0eb26572007-06-27 17:03:03 +00001111 // Handle binary ops
Owen Anderson59bd0532007-07-03 18:37:08 +00001112 } else if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
Owen Anderson0eb26572007-06-27 17:03:03 +00001113 isa<ExtractElementInst>(e)) {
1114 User* U = cast<User>(e);
1115 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1116 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
Owen Anderson49409f62007-06-22 21:31:16 +00001117
1118 if (l != 0 && isa<Instruction>(l) &&
1119 visited.count(l) == 0)
1120 stack.push_back(l);
1121 else if (r != 0 && isa<Instruction>(r) &&
1122 visited.count(r) == 0)
1123 stack.push_back(r);
1124 else {
1125 vec.push_back(e);
1126 visited.insert(e);
1127 stack.pop_back();
1128 }
Owen Anderson0b68cda2007-06-03 05:55:58 +00001129
Owen Anderson0eb26572007-06-27 17:03:03 +00001130 // Handle ternary ops
Owen Anderson8a9fa5d2007-06-28 23:51:21 +00001131 } else if (isa<InsertElementInst>(e) || isa<ShuffleVectorInst>(e) ||
1132 isa<SelectInst>(e)) {
Owen Anderson0eb26572007-06-27 17:03:03 +00001133 User* U = cast<User>(e);
1134 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1135 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1136 Value* m = find_leader(set, VN.lookup(U->getOperand(2)));
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001137
1138 if (l != 0 && isa<Instruction>(l) &&
1139 visited.count(l) == 0)
1140 stack.push_back(l);
1141 else if (r != 0 && isa<Instruction>(r) &&
1142 visited.count(r) == 0)
1143 stack.push_back(r);
1144 else if (m != 0 && isa<Instruction>(m) &&
1145 visited.count(m) == 0)
Owen Andersoncd94fc92007-07-04 18:26:18 +00001146 stack.push_back(m);
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001147 else {
1148 vec.push_back(e);
1149 visited.insert(e);
1150 stack.pop_back();
1151 }
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001152
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001153 // Handle vararg ops
1154 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(e)) {
1155 Value* p = find_leader(set, VN.lookup(U->getPointerOperand()));
1156
1157 if (p != 0 && isa<Instruction>(p) &&
1158 visited.count(p) == 0)
1159 stack.push_back(p);
1160 else {
1161 bool push_va = false;
1162 for (GetElementPtrInst::op_iterator I = U->idx_begin(),
1163 E = U->idx_end(); I != E; ++I) {
1164 Value * v = find_leader(set, VN.lookup(*I));
1165 if (v != 0 && isa<Instruction>(v) && visited.count(v) == 0) {
1166 stack.push_back(v);
1167 push_va = true;
1168 }
1169 }
1170
1171 if (!push_va) {
1172 vec.push_back(e);
1173 visited.insert(e);
1174 stack.pop_back();
1175 }
1176 }
1177
Owen Anderson0eb26572007-06-27 17:03:03 +00001178 // Handle opaque ops
Owen Anderson49409f62007-06-22 21:31:16 +00001179 } else {
Owen Anderson0b68cda2007-06-03 05:55:58 +00001180 visited.insert(e);
Owen Anderson223718c2007-06-09 18:35:31 +00001181 vec.push_back(e);
Owen Anderson49409f62007-06-22 21:31:16 +00001182 stack.pop_back();
Owen Anderson223718c2007-06-09 18:35:31 +00001183 }
Owen Anderson331bf6a2007-05-31 22:44:11 +00001184 }
Owen Anderson49409f62007-06-22 21:31:16 +00001185
1186 stack.clear();
Owen Anderson331bf6a2007-05-31 22:44:11 +00001187 }
1188}
1189
Owen Andersonfd5683a2007-06-21 00:19:05 +00001190/// dump - Dump a set of values to standard error
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001191void GVNPRE::dump(ValueNumberedSet& s) const {
Owen Anderson4a6ec8f2007-05-29 23:15:21 +00001192 DOUT << "{ ";
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001193 for (ValueNumberedSet::iterator I = s.begin(), E = s.end();
Owen Anderson0eca9aa2007-06-03 22:02:14 +00001194 I != E; ++I) {
Owen Anderson8a9fa5d2007-06-28 23:51:21 +00001195 DOUT << "" << VN.lookup(*I) << ": ";
Owen Anderson0eca9aa2007-06-03 22:02:14 +00001196 DEBUG((*I)->dump());
1197 }
1198 DOUT << "}\n\n";
1199}
1200
Owen Andersonfd5683a2007-06-21 00:19:05 +00001201/// elimination - Phase 3 of the main algorithm. Perform full redundancy
1202/// elimination by walking the dominator tree and removing any instruction that
1203/// is dominated by another instruction with the same value number.
Owen Anderson06c1e582007-06-20 22:10:02 +00001204bool GVNPRE::elimination() {
Owen Anderson06c1e582007-06-20 22:10:02 +00001205 bool changed_function = false;
1206
Owen Anderson6aa17f12007-07-19 06:37:56 +00001207 SmallVector<std::pair<Instruction*, Value*>, 8> replace;
1208 SmallVector<Instruction*, 8> erase;
Owen Anderson42769842007-06-12 16:57:50 +00001209
1210 DominatorTree& DT = getAnalysis<DominatorTree>();
1211
1212 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1213 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1214 BasicBlock* BB = DI->getBlock();
1215
Owen Anderson42769842007-06-12 16:57:50 +00001216 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1217 BI != BE; ++BI) {
1218
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001219 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI) ||
1220 isa<ShuffleVectorInst>(BI) || isa<InsertElementInst>(BI) ||
Owen Anderson59bd0532007-07-03 18:37:08 +00001221 isa<ExtractElementInst>(BI) || isa<SelectInst>(BI) ||
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001222 isa<CastInst>(BI) || isa<GetElementPtrInst>(BI)) {
Owen Anderson41c2cab2007-07-10 00:09:25 +00001223
Owen Anderson4c4b2382007-07-10 00:27:22 +00001224 if (availableOut[BB].test(VN.lookup(BI)) && !availableOut[BB].count(BI)) {
Owen Anderson41c2cab2007-07-10 00:09:25 +00001225 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
Owen Anderson42769842007-06-12 16:57:50 +00001226 if (Instruction* Instr = dyn_cast<Instruction>(leader))
1227 if (Instr->getParent() != 0 && Instr != BI) {
1228 replace.push_back(std::make_pair(BI, leader));
1229 erase.push_back(BI);
1230 ++NumEliminated;
1231 }
Owen Anderson41c2cab2007-07-10 00:09:25 +00001232 }
Owen Anderson42769842007-06-12 16:57:50 +00001233 }
1234 }
1235 }
1236
1237 while (!replace.empty()) {
1238 std::pair<Instruction*, Value*> rep = replace.back();
1239 replace.pop_back();
1240 rep.first->replaceAllUsesWith(rep.second);
Owen Andersonb0714bb2007-06-20 18:30:20 +00001241 changed_function = true;
Owen Anderson42769842007-06-12 16:57:50 +00001242 }
1243
Owen Anderson6aa17f12007-07-19 06:37:56 +00001244 for (SmallVector<Instruction*, 8>::iterator I = erase.begin(), E = erase.end();
Owen Anderson42769842007-06-12 16:57:50 +00001245 I != E; ++I)
1246 (*I)->eraseFromParent();
Owen Anderson06c1e582007-06-20 22:10:02 +00001247
1248 return changed_function;
Owen Anderson42769842007-06-12 16:57:50 +00001249}
1250
Owen Andersonfd5683a2007-06-21 00:19:05 +00001251/// cleanup - Delete any extraneous values that were created to represent
1252/// expressions without leaders.
Owen Anderson42769842007-06-12 16:57:50 +00001253void GVNPRE::cleanup() {
1254 while (!createdExpressions.empty()) {
1255 Instruction* I = createdExpressions.back();
1256 createdExpressions.pop_back();
1257
1258 delete I;
1259 }
1260}
1261
Owen Andersonfd5683a2007-06-21 00:19:05 +00001262/// buildsets_availout - When calculating availability, handle an instruction
1263/// by inserting it into the appropriate sets
Owen Anderson06c1e582007-06-20 22:10:02 +00001264void GVNPRE::buildsets_availout(BasicBlock::iterator I,
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001265 ValueNumberedSet& currAvail,
1266 ValueNumberedSet& currPhis,
1267 ValueNumberedSet& currExps,
1268 SmallPtrSet<Value*, 16>& currTemps) {
Owen Anderson0eb26572007-06-27 17:03:03 +00001269 // Handle PHI nodes
Owen Anderson06c1e582007-06-20 22:10:02 +00001270 if (PHINode* p = dyn_cast<PHINode>(I)) {
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001271 unsigned num = VN.lookup_or_add(p);
Owen Andersonf6e21872007-06-22 03:14:03 +00001272
Owen Anderson06c1e582007-06-20 22:10:02 +00001273 currPhis.insert(p);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001274 currPhis.set(num);
Owen Anderson59bd0532007-07-03 18:37:08 +00001275
1276 // Handle unary ops
Owen Anderson6b958c72007-07-03 19:01:42 +00001277 } else if (CastInst* U = dyn_cast<CastInst>(I)) {
Owen Anderson59bd0532007-07-03 18:37:08 +00001278 Value* leftValue = U->getOperand(0);
Owen Anderson06c1e582007-06-20 22:10:02 +00001279
Owen Anderson59bd0532007-07-03 18:37:08 +00001280 unsigned num = VN.lookup_or_add(U);
Owen Anderson59bd0532007-07-03 18:37:08 +00001281
1282 if (isa<Instruction>(leftValue))
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001283 if (!currExps.test(VN.lookup(leftValue))) {
Owen Anderson59bd0532007-07-03 18:37:08 +00001284 currExps.insert(leftValue);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001285 currExps.set(VN.lookup(leftValue));
Owen Anderson59bd0532007-07-03 18:37:08 +00001286 }
1287
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001288 if (!currExps.test(num)) {
Owen Anderson59bd0532007-07-03 18:37:08 +00001289 currExps.insert(U);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001290 currExps.set(num);
Owen Anderson59bd0532007-07-03 18:37:08 +00001291 }
1292
Owen Anderson0eb26572007-06-27 17:03:03 +00001293 // Handle binary ops
1294 } else if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
1295 isa<ExtractElementInst>(I)) {
1296 User* U = cast<User>(I);
1297 Value* leftValue = U->getOperand(0);
1298 Value* rightValue = U->getOperand(1);
Owen Anderson06c1e582007-06-20 22:10:02 +00001299
Owen Anderson0eb26572007-06-27 17:03:03 +00001300 unsigned num = VN.lookup_or_add(U);
Owen Anderson06c1e582007-06-20 22:10:02 +00001301
1302 if (isa<Instruction>(leftValue))
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001303 if (!currExps.test(VN.lookup(leftValue))) {
Owen Andersonf6e21872007-06-22 03:14:03 +00001304 currExps.insert(leftValue);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001305 currExps.set(VN.lookup(leftValue));
Owen Andersonf6e21872007-06-22 03:14:03 +00001306 }
1307
Owen Anderson06c1e582007-06-20 22:10:02 +00001308 if (isa<Instruction>(rightValue))
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001309 if (!currExps.test(VN.lookup(rightValue))) {
Owen Andersonf6e21872007-06-22 03:14:03 +00001310 currExps.insert(rightValue);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001311 currExps.set(VN.lookup(rightValue));
Owen Andersonf6e21872007-06-22 03:14:03 +00001312 }
1313
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001314 if (!currExps.test(num)) {
Owen Anderson0eb26572007-06-27 17:03:03 +00001315 currExps.insert(U);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001316 currExps.set(num);
Owen Andersonf6e21872007-06-22 03:14:03 +00001317 }
Owen Anderson06c1e582007-06-20 22:10:02 +00001318
Owen Anderson0eb26572007-06-27 17:03:03 +00001319 // Handle ternary ops
Owen Anderson8a9fa5d2007-06-28 23:51:21 +00001320 } else if (isa<InsertElementInst>(I) || isa<ShuffleVectorInst>(I) ||
1321 isa<SelectInst>(I)) {
Owen Anderson0eb26572007-06-27 17:03:03 +00001322 User* U = cast<User>(I);
1323 Value* leftValue = U->getOperand(0);
1324 Value* rightValue = U->getOperand(1);
1325 Value* thirdValue = U->getOperand(2);
Owen Anderson06c1e582007-06-20 22:10:02 +00001326
Owen Anderson0eb26572007-06-27 17:03:03 +00001327 VN.lookup_or_add(U);
Owen Andersonf6e21872007-06-22 03:14:03 +00001328
Owen Anderson0eb26572007-06-27 17:03:03 +00001329 unsigned num = VN.lookup_or_add(U);
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001330
1331 if (isa<Instruction>(leftValue))
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001332 if (!currExps.test(VN.lookup(leftValue))) {
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001333 currExps.insert(leftValue);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001334 currExps.set(VN.lookup(leftValue));
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001335 }
1336 if (isa<Instruction>(rightValue))
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001337 if (!currExps.test(VN.lookup(rightValue))) {
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001338 currExps.insert(rightValue);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001339 currExps.set(VN.lookup(rightValue));
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001340 }
1341 if (isa<Instruction>(thirdValue))
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001342 if (!currExps.test(VN.lookup(thirdValue))) {
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001343 currExps.insert(thirdValue);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001344 currExps.set(VN.lookup(thirdValue));
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001345 }
1346
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001347 if (!currExps.test(num)) {
Owen Anderson0eb26572007-06-27 17:03:03 +00001348 currExps.insert(U);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001349 currExps.set(num);
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001350 }
1351
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001352 // Handle vararg ops
1353 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(I)) {
1354 Value* ptrValue = U->getPointerOperand();
1355
1356 VN.lookup_or_add(U);
1357
1358 unsigned num = VN.lookup_or_add(U);
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001359
1360 if (isa<Instruction>(ptrValue))
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001361 if (!currExps.test(VN.lookup(ptrValue))) {
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001362 currExps.insert(ptrValue);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001363 currExps.set(VN.lookup(ptrValue));
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001364 }
1365
1366 for (GetElementPtrInst::op_iterator OI = U->idx_begin(), OE = U->idx_end();
1367 OI != OE; ++OI)
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001368 if (isa<Instruction>(*OI) && !currExps.test(VN.lookup(*OI))) {
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001369 currExps.insert(*OI);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001370 currExps.set(VN.lookup(*OI));
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001371 }
1372
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001373 if (!currExps.test(VN.lookup(U))) {
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001374 currExps.insert(U);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001375 currExps.set(num);
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001376 }
1377
Owen Anderson0eb26572007-06-27 17:03:03 +00001378 // Handle opaque ops
1379 } else if (!I->isTerminator()){
Owen Anderson06c1e582007-06-20 22:10:02 +00001380 VN.lookup_or_add(I);
Owen Andersonf6e21872007-06-22 03:14:03 +00001381
Owen Anderson06c1e582007-06-20 22:10:02 +00001382 currTemps.insert(I);
1383 }
1384
1385 if (!I->isTerminator())
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001386 if (!currAvail.test(VN.lookup(I))) {
Owen Andersonf6e21872007-06-22 03:14:03 +00001387 currAvail.insert(I);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001388 currAvail.set(VN.lookup(I));
Owen Andersonf6e21872007-06-22 03:14:03 +00001389 }
Owen Anderson06c1e582007-06-20 22:10:02 +00001390}
Owen Anderson5fba6c12007-05-29 21:53:49 +00001391
Owen Andersonfd5683a2007-06-21 00:19:05 +00001392/// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
1393/// set as a function of the ANTIC_IN set of the block's predecessors
Owen Anderson28a2d442007-06-22 00:20:30 +00001394bool GVNPRE::buildsets_anticout(BasicBlock* BB,
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001395 ValueNumberedSet& anticOut,
Owen Anderson6a4ff852007-07-19 03:32:44 +00001396 SmallPtrSet<BasicBlock*, 8>& visited) {
Owen Anderson06c1e582007-06-20 22:10:02 +00001397 if (BB->getTerminator()->getNumSuccessors() == 1) {
Owen Anderson191eb062007-06-25 05:41:12 +00001398 if (BB->getTerminator()->getSuccessor(0) != BB &&
1399 visited.count(BB->getTerminator()->getSuccessor(0)) == 0) {
Owen Anderson28a2d442007-06-22 00:20:30 +00001400 return true;
Owen Anderson191eb062007-06-25 05:41:12 +00001401 }
1402 else {
Owen Anderson06c1e582007-06-20 22:10:02 +00001403 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
1404 BB, BB->getTerminator()->getSuccessor(0), anticOut);
Owen Anderson191eb062007-06-25 05:41:12 +00001405 }
Owen Anderson06c1e582007-06-20 22:10:02 +00001406 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
1407 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001408 for (ValueNumberedSet::iterator I = anticipatedIn[first].begin(),
1409 E = anticipatedIn[first].end(); I != E; ++I) {
1410 anticOut.insert(*I);
1411 anticOut.set(VN.lookup(*I));
1412 }
Owen Anderson06c1e582007-06-20 22:10:02 +00001413
1414 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
1415 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001416 ValueNumberedSet& succAnticIn = anticipatedIn[currSucc];
Owen Anderson06c1e582007-06-20 22:10:02 +00001417
Owen Anderson6aa17f12007-07-19 06:37:56 +00001418 SmallVector<Value*, 16> temp;
Owen Anderson2ff912b2007-06-21 17:57:53 +00001419
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001420 for (ValueNumberedSet::iterator I = anticOut.begin(),
Owen Anderson2ff912b2007-06-21 17:57:53 +00001421 E = anticOut.end(); I != E; ++I)
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001422 if (!succAnticIn.test(VN.lookup(*I)))
Owen Anderson2ff912b2007-06-21 17:57:53 +00001423 temp.push_back(*I);
1424
Owen Anderson6aa17f12007-07-19 06:37:56 +00001425 for (SmallVector<Value*, 16>::iterator I = temp.begin(), E = temp.end();
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001426 I != E; ++I) {
Owen Anderson2ff912b2007-06-21 17:57:53 +00001427 anticOut.erase(*I);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001428 anticOut.reset(VN.lookup(*I));
1429 }
Owen Anderson06c1e582007-06-20 22:10:02 +00001430 }
1431 }
Owen Anderson28a2d442007-06-22 00:20:30 +00001432
1433 return false;
Owen Anderson06c1e582007-06-20 22:10:02 +00001434}
1435
Owen Andersonfd5683a2007-06-21 00:19:05 +00001436/// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
1437/// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN
1438/// sets populated in buildsets_availout
Owen Anderson28a2d442007-06-22 00:20:30 +00001439unsigned GVNPRE::buildsets_anticin(BasicBlock* BB,
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001440 ValueNumberedSet& anticOut,
1441 ValueNumberedSet& currExps,
Owen Andersone02da552007-06-28 00:34:34 +00001442 SmallPtrSet<Value*, 16>& currTemps,
Owen Anderson6a4ff852007-07-19 03:32:44 +00001443 SmallPtrSet<BasicBlock*, 8>& visited) {
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001444 ValueNumberedSet& anticIn = anticipatedIn[BB];
Owen Anderson21a11312007-06-22 18:27:04 +00001445 unsigned old = anticIn.size();
Owen Anderson06c1e582007-06-20 22:10:02 +00001446
Owen Anderson28a2d442007-06-22 00:20:30 +00001447 bool defer = buildsets_anticout(BB, anticOut, visited);
1448 if (defer)
1449 return 0;
Owen Anderson2ff912b2007-06-21 17:57:53 +00001450
Owen Anderson06c1e582007-06-20 22:10:02 +00001451 anticIn.clear();
Owen Anderson2ff912b2007-06-21 17:57:53 +00001452
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001453 for (ValueNumberedSet::iterator I = anticOut.begin(),
Owen Anderson21a11312007-06-22 18:27:04 +00001454 E = anticOut.end(); I != E; ++I) {
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001455 anticIn.insert(*I);
1456 anticIn.set(VN.lookup(*I));
Owen Anderson06c1e582007-06-20 22:10:02 +00001457 }
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001458 for (ValueNumberedSet::iterator I = currExps.begin(),
Owen Anderson21a11312007-06-22 18:27:04 +00001459 E = currExps.end(); I != E; ++I) {
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001460 if (!anticIn.test(VN.lookup(*I))) {
Owen Anderson21a11312007-06-22 18:27:04 +00001461 anticIn.insert(*I);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001462 anticIn.set(VN.lookup(*I));
Owen Anderson21a11312007-06-22 18:27:04 +00001463 }
1464 }
1465
Owen Andersone02da552007-06-28 00:34:34 +00001466 for (SmallPtrSet<Value*, 16>::iterator I = currTemps.begin(),
Owen Anderson7dae8ef2007-06-27 17:38:29 +00001467 E = currTemps.end(); I != E; ++I) {
Owen Anderson21a11312007-06-22 18:27:04 +00001468 anticIn.erase(*I);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001469 anticIn.reset(VN.lookup(*I));
Owen Anderson7dae8ef2007-06-27 17:38:29 +00001470 }
Owen Anderson21a11312007-06-22 18:27:04 +00001471
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001472 clean(anticIn);
Owen Anderson7dae8ef2007-06-27 17:38:29 +00001473 anticOut.clear();
Owen Anderson06c1e582007-06-20 22:10:02 +00001474
Owen Anderson7dae8ef2007-06-27 17:38:29 +00001475 if (old != anticIn.size())
Owen Anderson28a2d442007-06-22 00:20:30 +00001476 return 2;
Owen Anderson7dae8ef2007-06-27 17:38:29 +00001477 else
Owen Anderson28a2d442007-06-22 00:20:30 +00001478 return 1;
Owen Anderson06c1e582007-06-20 22:10:02 +00001479}
1480
Owen Andersonfd5683a2007-06-21 00:19:05 +00001481/// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT
1482/// and the ANTIC_IN sets.
Owen Anderson5477c542007-06-26 23:29:41 +00001483void GVNPRE::buildsets(Function& F) {
Owen Anderson6a4ff852007-07-19 03:32:44 +00001484 DenseMap<BasicBlock*, ValueNumberedSet> generatedExpressions;
1485 DenseMap<BasicBlock*, SmallPtrSet<Value*, 16> > generatedTemporaries;
Owen Anderson06c1e582007-06-20 22:10:02 +00001486
Owen Anderson5fba6c12007-05-29 21:53:49 +00001487 DominatorTree &DT = getAnalysis<DominatorTree>();
1488
Owen Anderson634a0632007-06-06 01:27:49 +00001489 // Phase 1, Part 1: calculate AVAIL_OUT
Owen Anderson5fba6c12007-05-29 21:53:49 +00001490
1491 // Top-down walk of the dominator tree
Devang Patelbdd1aae2007-06-04 00:32:22 +00001492 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
Owen Anderson5fba6c12007-05-29 21:53:49 +00001493 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1494
1495 // Get the sets to update for this block
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001496 ValueNumberedSet& currExps = generatedExpressions[DI->getBlock()];
1497 ValueNumberedSet& currPhis = generatedPhis[DI->getBlock()];
Owen Andersone02da552007-06-28 00:34:34 +00001498 SmallPtrSet<Value*, 16>& currTemps = generatedTemporaries[DI->getBlock()];
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001499 ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
Owen Anderson5fba6c12007-05-29 21:53:49 +00001500
Owen Andersonb56fba02007-06-19 03:31:41 +00001501 BasicBlock* BB = DI->getBlock();
1502
1503 // A block inherits AVAIL_OUT from its dominator
Owen Andersoneffc7a72007-07-09 22:29:50 +00001504 if (DI->getIDom() != 0)
1505 currAvail = availableOut[DI->getIDom()->getBlock()];
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001506
Owen Andersonb56fba02007-06-19 03:31:41 +00001507 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
Owen Anderson06c1e582007-06-20 22:10:02 +00001508 BI != BE; ++BI)
Owen Andersonf6e21872007-06-22 03:14:03 +00001509 buildsets_availout(BI, currAvail, currPhis, currExps,
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001510 currTemps);
Owen Andersonb56fba02007-06-19 03:31:41 +00001511
Owen Anderson5fba6c12007-05-29 21:53:49 +00001512 }
Owen Anderson191eb062007-06-25 05:41:12 +00001513
1514 // Phase 1, Part 2: calculate ANTIC_IN
Owen Anderson5fba6c12007-05-29 21:53:49 +00001515
Owen Anderson6a4ff852007-07-19 03:32:44 +00001516 SmallPtrSet<BasicBlock*, 8> visited;
Owen Anderson5477c542007-06-26 23:29:41 +00001517 SmallPtrSet<BasicBlock*, 4> block_changed;
1518 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
1519 block_changed.insert(FI);
Owen Anderson0c423072007-05-29 23:26:30 +00001520
Owen Anderson5fba6c12007-05-29 21:53:49 +00001521 bool changed = true;
1522 unsigned iterations = 0;
Owen Anderson5477c542007-06-26 23:29:41 +00001523
Owen Anderson5fba6c12007-05-29 21:53:49 +00001524 while (changed) {
1525 changed = false;
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001526 ValueNumberedSet anticOut;
Owen Anderson5fba6c12007-05-29 21:53:49 +00001527
Owen Anderson5477c542007-06-26 23:29:41 +00001528 // Postorder walk of the CFG
Owen Anderson43ca4b42007-06-25 18:25:31 +00001529 for (po_iterator<BasicBlock*> BBI = po_begin(&F.getEntryBlock()),
1530 BBE = po_end(&F.getEntryBlock()); BBI != BBE; ++BBI) {
Owen Anderson191eb062007-06-25 05:41:12 +00001531 BasicBlock* BB = *BBI;
Owen Andersond184c182007-06-11 16:25:17 +00001532
Owen Anderson5477c542007-06-26 23:29:41 +00001533 if (block_changed.count(BB) != 0) {
1534 unsigned ret = buildsets_anticin(BB, anticOut,generatedExpressions[BB],
1535 generatedTemporaries[BB], visited);
Owen Anderson28a2d442007-06-22 00:20:30 +00001536
Owen Anderson5477c542007-06-26 23:29:41 +00001537 if (ret == 0) {
1538 changed = true;
1539 continue;
1540 } else {
1541 visited.insert(BB);
1542
1543 if (ret == 2)
1544 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1545 PI != PE; ++PI) {
1546 block_changed.insert(*PI);
1547 }
1548 else
1549 block_changed.erase(BB);
1550
1551 changed |= (ret == 2);
Owen Anderson191eb062007-06-25 05:41:12 +00001552 }
Owen Anderson28a2d442007-06-22 00:20:30 +00001553 }
Owen Anderson5fba6c12007-05-29 21:53:49 +00001554 }
Owen Anderson38b6b222007-06-04 18:05:26 +00001555
Owen Anderson5fba6c12007-05-29 21:53:49 +00001556 iterations++;
1557 }
Owen Anderson06c1e582007-06-20 22:10:02 +00001558}
1559
Owen Andersonfd5683a2007-06-21 00:19:05 +00001560/// insertion_pre - When a partial redundancy has been identified, eliminate it
1561/// by inserting appropriate values into the predecessors and a phi node in
1562/// the main block
Owen Anderson06c1e582007-06-20 22:10:02 +00001563void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
Owen Anderson6aa17f12007-07-19 06:37:56 +00001564 DenseMap<BasicBlock*, Value*>& avail,
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001565 std::map<BasicBlock*, ValueNumberedSet>& new_sets) {
Owen Anderson06c1e582007-06-20 22:10:02 +00001566 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1567 Value* e2 = avail[*PI];
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001568 if (!availableOut[*PI].test(VN.lookup(e2))) {
Owen Anderson06c1e582007-06-20 22:10:02 +00001569 User* U = cast<User>(e2);
1570
1571 Value* s1 = 0;
1572 if (isa<BinaryOperator>(U->getOperand(0)) ||
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001573 isa<CmpInst>(U->getOperand(0)) ||
1574 isa<ShuffleVectorInst>(U->getOperand(0)) ||
1575 isa<ExtractElementInst>(U->getOperand(0)) ||
Owen Anderson8a9fa5d2007-06-28 23:51:21 +00001576 isa<InsertElementInst>(U->getOperand(0)) ||
Owen Anderson59bd0532007-07-03 18:37:08 +00001577 isa<SelectInst>(U->getOperand(0)) ||
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001578 isa<CastInst>(U->getOperand(0)) ||
1579 isa<GetElementPtrInst>(U->getOperand(0)))
Owen Anderson06c1e582007-06-20 22:10:02 +00001580 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1581 else
1582 s1 = U->getOperand(0);
1583
1584 Value* s2 = 0;
Owen Anderson59bd0532007-07-03 18:37:08 +00001585
1586 if (isa<BinaryOperator>(U) ||
1587 isa<CmpInst>(U) ||
1588 isa<ShuffleVectorInst>(U) ||
1589 isa<ExtractElementInst>(U) ||
1590 isa<InsertElementInst>(U) ||
1591 isa<SelectInst>(U))
1592 if (isa<BinaryOperator>(U->getOperand(1)) ||
1593 isa<CmpInst>(U->getOperand(1)) ||
1594 isa<ShuffleVectorInst>(U->getOperand(1)) ||
1595 isa<ExtractElementInst>(U->getOperand(1)) ||
1596 isa<InsertElementInst>(U->getOperand(1)) ||
1597 isa<SelectInst>(U->getOperand(1)) ||
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001598 isa<CastInst>(U->getOperand(1)) ||
1599 isa<GetElementPtrInst>(U->getOperand(1))) {
Owen Anderson59bd0532007-07-03 18:37:08 +00001600 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1601 } else {
1602 s2 = U->getOperand(1);
1603 }
Owen Anderson0eb26572007-06-27 17:03:03 +00001604
1605 // Ternary Operators
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001606 Value* s3 = 0;
1607 if (isa<ShuffleVectorInst>(U) ||
Owen Anderson8a9fa5d2007-06-28 23:51:21 +00001608 isa<InsertElementInst>(U) ||
1609 isa<SelectInst>(U))
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001610 if (isa<BinaryOperator>(U->getOperand(2)) ||
1611 isa<CmpInst>(U->getOperand(2)) ||
1612 isa<ShuffleVectorInst>(U->getOperand(2)) ||
1613 isa<ExtractElementInst>(U->getOperand(2)) ||
Owen Anderson8a9fa5d2007-06-28 23:51:21 +00001614 isa<InsertElementInst>(U->getOperand(2)) ||
Owen Anderson59bd0532007-07-03 18:37:08 +00001615 isa<SelectInst>(U->getOperand(2)) ||
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001616 isa<CastInst>(U->getOperand(2)) ||
1617 isa<GetElementPtrInst>(U->getOperand(2))) {
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001618 s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2)));
Owen Anderson59bd0532007-07-03 18:37:08 +00001619 } else {
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001620 s3 = U->getOperand(2);
Owen Anderson59bd0532007-07-03 18:37:08 +00001621 }
Owen Anderson06c1e582007-06-20 22:10:02 +00001622
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001623 // Vararg operators
Owen Anderson6aa17f12007-07-19 06:37:56 +00001624 SmallVector<Value*, 4> sVarargs;
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001625 if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U)) {
1626 for (GetElementPtrInst::op_iterator OI = G->idx_begin(),
1627 OE = G->idx_end(); OI != OE; ++OI) {
1628 if (isa<BinaryOperator>(*OI) ||
1629 isa<CmpInst>(*OI) ||
1630 isa<ShuffleVectorInst>(*OI) ||
1631 isa<ExtractElementInst>(*OI) ||
1632 isa<InsertElementInst>(*OI) ||
1633 isa<SelectInst>(*OI) ||
1634 isa<CastInst>(*OI) ||
1635 isa<GetElementPtrInst>(*OI)) {
1636 sVarargs.push_back(find_leader(availableOut[*PI],
1637 VN.lookup(*OI)));
1638 } else {
1639 sVarargs.push_back(*OI);
1640 }
1641 }
1642 }
1643
Owen Anderson06c1e582007-06-20 22:10:02 +00001644 Value* newVal = 0;
1645 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1646 newVal = BinaryOperator::create(BO->getOpcode(), s1, s2,
1647 BO->getName()+".gvnpre",
1648 (*PI)->getTerminator());
1649 else if (CmpInst* C = dyn_cast<CmpInst>(U))
1650 newVal = CmpInst::create(C->getOpcode(), C->getPredicate(), s1, s2,
1651 C->getName()+".gvnpre",
1652 (*PI)->getTerminator());
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001653 else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
1654 newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre",
1655 (*PI)->getTerminator());
1656 else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U))
1657 newVal = new InsertElementInst(s1, s2, s3, S->getName()+".gvnpre",
1658 (*PI)->getTerminator());
1659 else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U))
1660 newVal = new ExtractElementInst(s1, s2, S->getName()+".gvnpre",
1661 (*PI)->getTerminator());
Owen Anderson8a9fa5d2007-06-28 23:51:21 +00001662 else if (SelectInst* S = dyn_cast<SelectInst>(U))
Owen Andersonca1a1842007-07-04 22:33:23 +00001663 newVal = new SelectInst(s1, s2, s3, S->getName()+".gvnpre",
Owen Anderson8a9fa5d2007-06-28 23:51:21 +00001664 (*PI)->getTerminator());
Owen Anderson59bd0532007-07-03 18:37:08 +00001665 else if (CastInst* C = dyn_cast<CastInst>(U))
1666 newVal = CastInst::create(C->getOpcode(), s1, C->getType(),
1667 C->getName()+".gvnpre",
1668 (*PI)->getTerminator());
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001669 else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U))
1670 newVal = new GetElementPtrInst(s1, &sVarargs[0], sVarargs.size(),
1671 G->getName()+".gvnpre",
1672 (*PI)->getTerminator());
Owen Anderson8a9fa5d2007-06-28 23:51:21 +00001673
Owen Anderson06c1e582007-06-20 22:10:02 +00001674
1675 VN.add(newVal, VN.lookup(U));
1676
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001677 ValueNumberedSet& predAvail = availableOut[*PI];
Owen Anderson06c1e582007-06-20 22:10:02 +00001678 val_replace(predAvail, newVal);
Owen Anderson02e96982007-07-05 23:11:26 +00001679 val_replace(new_sets[*PI], newVal);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001680 predAvail.set(VN.lookup(newVal));
Owen Andersonfd5683a2007-06-21 00:19:05 +00001681
Owen Anderson6aa17f12007-07-19 06:37:56 +00001682 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
Owen Anderson06c1e582007-06-20 22:10:02 +00001683 if (av != avail.end())
1684 avail.erase(av);
1685 avail.insert(std::make_pair(*PI, newVal));
1686
1687 ++NumInsertedVals;
1688 }
1689 }
1690
1691 PHINode* p = 0;
1692
1693 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1694 if (p == 0)
1695 p = new PHINode(avail[*PI]->getType(), "gvnpre-join", BB->begin());
Owen Anderson02e96982007-07-05 23:11:26 +00001696
Owen Anderson06c1e582007-06-20 22:10:02 +00001697 p->addIncoming(avail[*PI], *PI);
1698 }
1699
1700 VN.add(p, VN.lookup(e));
Owen Anderson06c1e582007-06-20 22:10:02 +00001701 val_replace(availableOut[BB], p);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001702 availableOut[BB].set(VN.lookup(e));
Owen Anderson7d4bbc12007-07-06 20:29:43 +00001703 generatedPhis[BB].insert(p);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001704 generatedPhis[BB].set(VN.lookup(e));
Owen Anderson02e96982007-07-05 23:11:26 +00001705 new_sets[BB].insert(p);
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001706 new_sets[BB].set(VN.lookup(e));
Owen Anderson06c1e582007-06-20 22:10:02 +00001707
1708 ++NumInsertedPhis;
1709}
1710
Owen Andersonfd5683a2007-06-21 00:19:05 +00001711/// insertion_mergepoint - When walking the dom tree, check at each merge
1712/// block for the possibility of a partial redundancy. If present, eliminate it
Owen Anderson6aa17f12007-07-19 06:37:56 +00001713unsigned GVNPRE::insertion_mergepoint(SmallVector<Value*, 8>& workList,
Owen Anderson28a2d442007-06-22 00:20:30 +00001714 df_iterator<DomTreeNode*>& D,
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001715 std::map<BasicBlock*, ValueNumberedSet >& new_sets) {
Owen Anderson06c1e582007-06-20 22:10:02 +00001716 bool changed_function = false;
1717 bool new_stuff = false;
1718
1719 BasicBlock* BB = D->getBlock();
1720 for (unsigned i = 0; i < workList.size(); ++i) {
1721 Value* e = workList[i];
1722
Owen Andersonb6a39fc2007-06-27 04:10:46 +00001723 if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1724 isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) ||
Owen Anderson2e4b6fea2007-07-03 23:51:19 +00001725 isa<ShuffleVectorInst>(e) || isa<SelectInst>(e) || isa<CastInst>(e) ||
1726 isa<GetElementPtrInst>(e)) {
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001727 if (availableOut[D->getIDom()->getBlock()].test(VN.lookup(e)))
Owen Anderson06c1e582007-06-20 22:10:02 +00001728 continue;
1729
Owen Anderson6aa17f12007-07-19 06:37:56 +00001730 DenseMap<BasicBlock*, Value*> avail;
Owen Anderson06c1e582007-06-20 22:10:02 +00001731 bool by_some = false;
Owen Anderson7d4bbc12007-07-06 20:29:43 +00001732 bool all_same = true;
1733 Value * first_s = 0;
Owen Anderson06c1e582007-06-20 22:10:02 +00001734
1735 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1736 ++PI) {
1737 Value *e2 = phi_translate(e, *PI, BB);
1738 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1739
1740 if (e3 == 0) {
Owen Anderson6aa17f12007-07-19 06:37:56 +00001741 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
Owen Anderson06c1e582007-06-20 22:10:02 +00001742 if (av != avail.end())
1743 avail.erase(av);
1744 avail.insert(std::make_pair(*PI, e2));
Owen Anderson7d4bbc12007-07-06 20:29:43 +00001745 all_same = false;
Owen Anderson06c1e582007-06-20 22:10:02 +00001746 } else {
Owen Anderson6aa17f12007-07-19 06:37:56 +00001747 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
Owen Anderson06c1e582007-06-20 22:10:02 +00001748 if (av != avail.end())
1749 avail.erase(av);
1750 avail.insert(std::make_pair(*PI, e3));
1751
1752 by_some = true;
Owen Anderson7d4bbc12007-07-06 20:29:43 +00001753 if (first_s == 0)
1754 first_s = e3;
1755 else if (first_s != e3)
1756 all_same = false;
Owen Anderson06c1e582007-06-20 22:10:02 +00001757 }
1758 }
1759
Owen Anderson7d4bbc12007-07-06 20:29:43 +00001760 if (by_some && !all_same &&
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001761 !generatedPhis[BB].test(VN.lookup(e))) {
Owen Anderson02e96982007-07-05 23:11:26 +00001762 insertion_pre(e, BB, avail, new_sets);
Owen Anderson06c1e582007-06-20 22:10:02 +00001763
1764 changed_function = true;
1765 new_stuff = true;
1766 }
1767 }
1768 }
1769
1770 unsigned retval = 0;
1771 if (changed_function)
1772 retval += 1;
1773 if (new_stuff)
1774 retval += 2;
1775
1776 return retval;
1777}
1778
Owen Andersonfd5683a2007-06-21 00:19:05 +00001779/// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for
1780/// merge points. When one is found, check for a partial redundancy. If one is
1781/// present, eliminate it. Repeat this walk until no changes are made.
Owen Anderson06c1e582007-06-20 22:10:02 +00001782bool GVNPRE::insertion(Function& F) {
1783 bool changed_function = false;
1784
1785 DominatorTree &DT = getAnalysis<DominatorTree>();
Owen Andersonbe802402007-06-08 01:03:01 +00001786
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001787 std::map<BasicBlock*, ValueNumberedSet> new_sets;
Owen Andersonbe802402007-06-08 01:03:01 +00001788 bool new_stuff = true;
1789 while (new_stuff) {
1790 new_stuff = false;
Owen Andersonbe802402007-06-08 01:03:01 +00001791 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1792 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1793 BasicBlock* BB = DI->getBlock();
1794
Owen Andersond184c182007-06-11 16:25:17 +00001795 if (BB == 0)
1796 continue;
1797
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001798 ValueNumberedSet& availOut = availableOut[BB];
1799 ValueNumberedSet& anticIn = anticipatedIn[BB];
Owen Andersonbe802402007-06-08 01:03:01 +00001800
1801 // Replace leaders with leaders inherited from dominator
1802 if (DI->getIDom() != 0) {
Owen Anderson1c83b5d2007-07-09 06:50:06 +00001803 ValueNumberedSet& dom_set = new_sets[DI->getIDom()->getBlock()];
1804 for (ValueNumberedSet::iterator I = dom_set.begin(),
Owen Andersonbe802402007-06-08 01:03:01 +00001805 E = dom_set.end(); I != E; ++I) {
Owen Anderson02e96982007-07-05 23:11:26 +00001806 val_replace(new_sets[BB], *I);
Owen Andersonb56fba02007-06-19 03:31:41 +00001807 val_replace(availOut, *I);
Owen Andersonbe802402007-06-08 01:03:01 +00001808 }
1809 }
1810
1811 // If there is more than one predecessor...
1812 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
Owen Anderson6aa17f12007-07-19 06:37:56 +00001813 SmallVector<Value*, 8> workList;
Owen Andersond50a29d2007-06-22 00:43:22 +00001814 workList.reserve(anticIn.size());
Owen Andersonbe802402007-06-08 01:03:01 +00001815 topo_sort(anticIn, workList);
1816
Owen Anderson02e96982007-07-05 23:11:26 +00001817 unsigned result = insertion_mergepoint(workList, DI, new_sets);
Owen Anderson06c1e582007-06-20 22:10:02 +00001818 if (result & 1)
1819 changed_function = true;
1820 if (result & 2)
1821 new_stuff = true;
Owen Andersonbe802402007-06-08 01:03:01 +00001822 }
1823 }
Owen Andersonbe802402007-06-08 01:03:01 +00001824 }
Owen Anderson634a0632007-06-06 01:27:49 +00001825
Owen Anderson06c1e582007-06-20 22:10:02 +00001826 return changed_function;
1827}
1828
Owen Andersonfd5683a2007-06-21 00:19:05 +00001829// GVNPRE::runOnFunction - This is the main transformation entry point for a
1830// function.
1831//
Owen Anderson06c1e582007-06-20 22:10:02 +00001832bool GVNPRE::runOnFunction(Function &F) {
Owen Andersonfd5683a2007-06-21 00:19:05 +00001833 // Clean out global sets from any previous functions
Owen Anderson06c1e582007-06-20 22:10:02 +00001834 VN.clear();
1835 createdExpressions.clear();
1836 availableOut.clear();
1837 anticipatedIn.clear();
Owen Anderson7d4bbc12007-07-06 20:29:43 +00001838 generatedPhis.clear();
1839
Owen Anderson06c1e582007-06-20 22:10:02 +00001840 bool changed_function = false;
1841
1842 // Phase 1: BuildSets
Owen Andersonfd5683a2007-06-21 00:19:05 +00001843 // This phase calculates the AVAIL_OUT and ANTIC_IN sets
Owen Anderson5477c542007-06-26 23:29:41 +00001844 buildsets(F);
Owen Anderson06c1e582007-06-20 22:10:02 +00001845
1846 // Phase 2: Insert
Owen Andersonfd5683a2007-06-21 00:19:05 +00001847 // This phase inserts values to make partially redundant values
1848 // fully redundant
Owen Anderson06c1e582007-06-20 22:10:02 +00001849 changed_function |= insertion(F);
1850
Owen Anderson634a0632007-06-06 01:27:49 +00001851 // Phase 3: Eliminate
Owen Andersonfd5683a2007-06-21 00:19:05 +00001852 // This phase performs trivial full redundancy elimination
Owen Anderson06c1e582007-06-20 22:10:02 +00001853 changed_function |= elimination();
Owen Anderson55994f22007-06-08 20:44:02 +00001854
Owen Andersonbe802402007-06-08 01:03:01 +00001855 // Phase 4: Cleanup
Owen Andersonfd5683a2007-06-21 00:19:05 +00001856 // This phase cleans up values that were created solely
1857 // as leaders for expressions
Owen Anderson42769842007-06-12 16:57:50 +00001858 cleanup();
Owen Andersonbe802402007-06-08 01:03:01 +00001859
Owen Andersonb0714bb2007-06-20 18:30:20 +00001860 return changed_function;
Owen Anderson5fba6c12007-05-29 21:53:49 +00001861}