1 //===- GVNPRE.cpp - Eliminate redundant values and expressions ------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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
16 // live ranges, and should be used with caution on platforms that are very
17 // sensitive to register pressure.
19 //===----------------------------------------------------------------------===//
21 #define DEBUG_TYPE "gvnpre"
22 #include "llvm/Value.h"
23 #include "llvm/Transforms/Scalar.h"
24 #include "llvm/Instructions.h"
25 #include "llvm/Function.h"
26 #include "llvm/DerivedTypes.h"
27 #include "llvm/Analysis/Dominators.h"
28 #include "llvm/ADT/BitVector.h"
29 #include "llvm/ADT/DenseMap.h"
30 #include "llvm/ADT/DepthFirstIterator.h"
31 #include "llvm/ADT/PostOrderIterator.h"
32 #include "llvm/ADT/SmallPtrSet.h"
33 #include "llvm/ADT/SmallVector.h"
34 #include "llvm/ADT/Statistic.h"
35 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
36 #include "llvm/Support/CFG.h"
37 #include "llvm/Support/Compiler.h"
38 #include "llvm/Support/Debug.h"
44 //===----------------------------------------------------------------------===//
46 //===----------------------------------------------------------------------===//
48 /// 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
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,
65 ExpressionOpcode opcode;
70 SmallVector<uint32_t, 4> varargs;
73 explicit Expression(ExpressionOpcode o) : opcode(o) { }
75 bool operator==(const Expression &other) const {
76 if (opcode != other.opcode)
78 else if (opcode == EMPTY || opcode == TOMBSTONE)
80 else if (type != other.type)
82 else if (firstVN != other.firstVN)
84 else if (secondVN != other.secondVN)
86 else if (thirdVN != other.thirdVN)
89 if (varargs.size() != other.varargs.size())
92 for (size_t i = 0; i < varargs.size(); ++i)
93 if (varargs[i] != other.varargs[i])
100 bool operator!=(const Expression &other) const {
101 if (opcode != other.opcode)
103 else if (opcode == EMPTY || opcode == TOMBSTONE)
105 else if (type != other.type)
107 else if (firstVN != other.firstVN)
109 else if (secondVN != other.secondVN)
111 else if (thirdVN != other.thirdVN)
114 if (varargs.size() != other.varargs.size())
117 for (size_t i = 0; i < varargs.size(); ++i)
118 if (varargs[i] != other.varargs[i])
128 class VISIBILITY_HIDDEN ValueTable {
130 DenseMap<Value*, uint32_t> valueNumbering;
131 DenseMap<Expression, uint32_t> expressionNumbering;
133 uint32_t nextValueNumber;
135 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
136 Expression::ExpressionOpcode getOpcode(CmpInst* C);
137 Expression::ExpressionOpcode getOpcode(CastInst* C);
138 Expression create_expression(BinaryOperator* BO);
139 Expression create_expression(CmpInst* C);
140 Expression create_expression(ShuffleVectorInst* V);
141 Expression create_expression(ExtractElementInst* C);
142 Expression create_expression(InsertElementInst* V);
143 Expression create_expression(SelectInst* V);
144 Expression create_expression(CastInst* C);
145 Expression create_expression(GetElementPtrInst* G);
147 ValueTable() { nextValueNumber = 1; }
148 uint32_t lookup_or_add(Value* V);
149 uint32_t lookup(Value* V) const;
150 void add(Value* V, uint32_t num);
152 void erase(Value* v);
158 template <> struct DenseMapInfo<Expression> {
159 static inline Expression getEmptyKey() {
160 return Expression(Expression::EMPTY);
163 static inline Expression getTombstoneKey() {
164 return Expression(Expression::TOMBSTONE);
167 static unsigned getHashValue(const Expression e) {
168 unsigned hash = e.opcode;
170 hash = e.firstVN + hash * 37;
171 hash = e.secondVN + hash * 37;
172 hash = e.thirdVN + hash * 37;
174 hash = (unsigned)((uintptr_t)e.type >> 4) ^
175 (unsigned)((uintptr_t)e.type >> 9) +
178 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
179 E = e.varargs.end(); I != E; ++I)
180 hash = *I + hash * 37;
184 static bool isEqual(const Expression &LHS, const Expression &RHS) {
187 static bool isPod() { return true; }
191 //===----------------------------------------------------------------------===//
192 // ValueTable Internal Functions
193 //===----------------------------------------------------------------------===//
194 Expression::ExpressionOpcode
195 ValueTable::getOpcode(BinaryOperator* BO) {
196 switch(BO->getOpcode()) {
197 case Instruction::Add:
198 return Expression::ADD;
199 case Instruction::Sub:
200 return Expression::SUB;
201 case Instruction::Mul:
202 return Expression::MUL;
203 case Instruction::UDiv:
204 return Expression::UDIV;
205 case Instruction::SDiv:
206 return Expression::SDIV;
207 case Instruction::FDiv:
208 return Expression::FDIV;
209 case Instruction::URem:
210 return Expression::UREM;
211 case Instruction::SRem:
212 return Expression::SREM;
213 case Instruction::FRem:
214 return Expression::FREM;
215 case Instruction::Shl:
216 return Expression::SHL;
217 case Instruction::LShr:
218 return Expression::LSHR;
219 case Instruction::AShr:
220 return Expression::ASHR;
221 case Instruction::And:
222 return Expression::AND;
223 case Instruction::Or:
224 return Expression::OR;
225 case Instruction::Xor:
226 return Expression::XOR;
228 // THIS SHOULD NEVER HAPPEN
230 assert(0 && "Binary operator with unknown opcode?");
231 return Expression::ADD;
235 Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
236 if (C->getOpcode() == Instruction::ICmp) {
237 switch (C->getPredicate()) {
238 case ICmpInst::ICMP_EQ:
239 return Expression::ICMPEQ;
240 case ICmpInst::ICMP_NE:
241 return Expression::ICMPNE;
242 case ICmpInst::ICMP_UGT:
243 return Expression::ICMPUGT;
244 case ICmpInst::ICMP_UGE:
245 return Expression::ICMPUGE;
246 case ICmpInst::ICMP_ULT:
247 return Expression::ICMPULT;
248 case ICmpInst::ICMP_ULE:
249 return Expression::ICMPULE;
250 case ICmpInst::ICMP_SGT:
251 return Expression::ICMPSGT;
252 case ICmpInst::ICMP_SGE:
253 return Expression::ICMPSGE;
254 case ICmpInst::ICMP_SLT:
255 return Expression::ICMPSLT;
256 case ICmpInst::ICMP_SLE:
257 return Expression::ICMPSLE;
259 // THIS SHOULD NEVER HAPPEN
261 assert(0 && "Comparison with unknown predicate?");
262 return Expression::ICMPEQ;
265 switch (C->getPredicate()) {
266 case FCmpInst::FCMP_OEQ:
267 return Expression::FCMPOEQ;
268 case FCmpInst::FCMP_OGT:
269 return Expression::FCMPOGT;
270 case FCmpInst::FCMP_OGE:
271 return Expression::FCMPOGE;
272 case FCmpInst::FCMP_OLT:
273 return Expression::FCMPOLT;
274 case FCmpInst::FCMP_OLE:
275 return Expression::FCMPOLE;
276 case FCmpInst::FCMP_ONE:
277 return Expression::FCMPONE;
278 case FCmpInst::FCMP_ORD:
279 return Expression::FCMPORD;
280 case FCmpInst::FCMP_UNO:
281 return Expression::FCMPUNO;
282 case FCmpInst::FCMP_UEQ:
283 return Expression::FCMPUEQ;
284 case FCmpInst::FCMP_UGT:
285 return Expression::FCMPUGT;
286 case FCmpInst::FCMP_UGE:
287 return Expression::FCMPUGE;
288 case FCmpInst::FCMP_ULT:
289 return Expression::FCMPULT;
290 case FCmpInst::FCMP_ULE:
291 return Expression::FCMPULE;
292 case FCmpInst::FCMP_UNE:
293 return Expression::FCMPUNE;
295 // THIS SHOULD NEVER HAPPEN
297 assert(0 && "Comparison with unknown predicate?");
298 return Expression::FCMPOEQ;
303 Expression::ExpressionOpcode
304 ValueTable::getOpcode(CastInst* C) {
305 switch(C->getOpcode()) {
306 case Instruction::Trunc:
307 return Expression::TRUNC;
308 case Instruction::ZExt:
309 return Expression::ZEXT;
310 case Instruction::SExt:
311 return Expression::SEXT;
312 case Instruction::FPToUI:
313 return Expression::FPTOUI;
314 case Instruction::FPToSI:
315 return Expression::FPTOSI;
316 case Instruction::UIToFP:
317 return Expression::UITOFP;
318 case Instruction::SIToFP:
319 return Expression::SITOFP;
320 case Instruction::FPTrunc:
321 return Expression::FPTRUNC;
322 case Instruction::FPExt:
323 return Expression::FPEXT;
324 case Instruction::PtrToInt:
325 return Expression::PTRTOINT;
326 case Instruction::IntToPtr:
327 return Expression::INTTOPTR;
328 case Instruction::BitCast:
329 return Expression::BITCAST;
331 // THIS SHOULD NEVER HAPPEN
333 assert(0 && "Cast operator with unknown opcode?");
334 return Expression::BITCAST;
338 Expression ValueTable::create_expression(BinaryOperator* BO) {
341 e.firstVN = lookup_or_add(BO->getOperand(0));
342 e.secondVN = lookup_or_add(BO->getOperand(1));
344 e.type = BO->getType();
345 e.opcode = getOpcode(BO);
350 Expression ValueTable::create_expression(CmpInst* C) {
353 e.firstVN = lookup_or_add(C->getOperand(0));
354 e.secondVN = lookup_or_add(C->getOperand(1));
356 e.type = C->getType();
357 e.opcode = getOpcode(C);
362 Expression ValueTable::create_expression(CastInst* C) {
365 e.firstVN = lookup_or_add(C->getOperand(0));
368 e.type = C->getType();
369 e.opcode = getOpcode(C);
374 Expression ValueTable::create_expression(ShuffleVectorInst* S) {
377 e.firstVN = lookup_or_add(S->getOperand(0));
378 e.secondVN = lookup_or_add(S->getOperand(1));
379 e.thirdVN = lookup_or_add(S->getOperand(2));
380 e.type = S->getType();
381 e.opcode = Expression::SHUFFLE;
386 Expression ValueTable::create_expression(ExtractElementInst* E) {
389 e.firstVN = lookup_or_add(E->getOperand(0));
390 e.secondVN = lookup_or_add(E->getOperand(1));
392 e.type = E->getType();
393 e.opcode = Expression::EXTRACT;
398 Expression ValueTable::create_expression(InsertElementInst* I) {
401 e.firstVN = lookup_or_add(I->getOperand(0));
402 e.secondVN = lookup_or_add(I->getOperand(1));
403 e.thirdVN = lookup_or_add(I->getOperand(2));
404 e.type = I->getType();
405 e.opcode = Expression::INSERT;
410 Expression ValueTable::create_expression(SelectInst* I) {
413 e.firstVN = lookup_or_add(I->getCondition());
414 e.secondVN = lookup_or_add(I->getTrueValue());
415 e.thirdVN = lookup_or_add(I->getFalseValue());
416 e.type = I->getType();
417 e.opcode = Expression::SELECT;
422 Expression ValueTable::create_expression(GetElementPtrInst* G) {
425 e.firstVN = lookup_or_add(G->getPointerOperand());
428 e.type = G->getType();
429 e.opcode = Expression::GEP;
431 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
433 e.varargs.push_back(lookup_or_add(*I));
438 //===----------------------------------------------------------------------===//
439 // ValueTable External Functions
440 //===----------------------------------------------------------------------===//
442 /// lookup_or_add - Returns the value number for the specified value, assigning
443 /// it a new number if it did not have one before.
444 uint32_t ValueTable::lookup_or_add(Value* V) {
445 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
446 if (VI != valueNumbering.end())
450 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
451 Expression e = create_expression(BO);
453 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
454 if (EI != expressionNumbering.end()) {
455 valueNumbering.insert(std::make_pair(V, EI->second));
458 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
459 valueNumbering.insert(std::make_pair(V, nextValueNumber));
461 return nextValueNumber++;
463 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
464 Expression e = create_expression(C);
466 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
467 if (EI != expressionNumbering.end()) {
468 valueNumbering.insert(std::make_pair(V, EI->second));
471 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
472 valueNumbering.insert(std::make_pair(V, nextValueNumber));
474 return nextValueNumber++;
476 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
477 Expression e = create_expression(U);
479 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
480 if (EI != expressionNumbering.end()) {
481 valueNumbering.insert(std::make_pair(V, EI->second));
484 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
485 valueNumbering.insert(std::make_pair(V, nextValueNumber));
487 return nextValueNumber++;
489 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
490 Expression e = create_expression(U);
492 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
493 if (EI != expressionNumbering.end()) {
494 valueNumbering.insert(std::make_pair(V, EI->second));
497 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
498 valueNumbering.insert(std::make_pair(V, nextValueNumber));
500 return nextValueNumber++;
502 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
503 Expression e = create_expression(U);
505 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
506 if (EI != expressionNumbering.end()) {
507 valueNumbering.insert(std::make_pair(V, EI->second));
510 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
511 valueNumbering.insert(std::make_pair(V, nextValueNumber));
513 return nextValueNumber++;
515 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
516 Expression e = create_expression(U);
518 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
519 if (EI != expressionNumbering.end()) {
520 valueNumbering.insert(std::make_pair(V, EI->second));
523 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
524 valueNumbering.insert(std::make_pair(V, nextValueNumber));
526 return nextValueNumber++;
528 } else if (CastInst* U = dyn_cast<CastInst>(V)) {
529 Expression e = create_expression(U);
531 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
532 if (EI != expressionNumbering.end()) {
533 valueNumbering.insert(std::make_pair(V, EI->second));
536 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
537 valueNumbering.insert(std::make_pair(V, nextValueNumber));
539 return nextValueNumber++;
541 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
542 Expression e = create_expression(U);
544 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
545 if (EI != expressionNumbering.end()) {
546 valueNumbering.insert(std::make_pair(V, EI->second));
549 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
550 valueNumbering.insert(std::make_pair(V, nextValueNumber));
552 return nextValueNumber++;
555 valueNumbering.insert(std::make_pair(V, nextValueNumber));
556 return nextValueNumber++;
560 /// lookup - Returns the value number of the specified value. Fails if
561 /// the value has not yet been numbered.
562 uint32_t ValueTable::lookup(Value* V) const {
563 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
564 if (VI != valueNumbering.end())
567 assert(0 && "Value not numbered?");
572 /// add - Add the specified value with the given value number, removing
573 /// its old number, if any
574 void ValueTable::add(Value* V, uint32_t num) {
575 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
576 if (VI != valueNumbering.end())
577 valueNumbering.erase(VI);
578 valueNumbering.insert(std::make_pair(V, num));
581 /// clear - Remove all entries from the ValueTable
582 void ValueTable::clear() {
583 valueNumbering.clear();
584 expressionNumbering.clear();
588 /// erase - Remove a value from the value numbering
589 void ValueTable::erase(Value* V) {
590 valueNumbering.erase(V);
593 /// size - Return the number of assigned value numbers
594 unsigned ValueTable::size() {
595 // NOTE: zero is never assigned
596 return nextValueNumber;
599 //===----------------------------------------------------------------------===//
600 // ValueNumberedSet Class
601 //===----------------------------------------------------------------------===//
603 class ValueNumberedSet {
605 SmallPtrSet<Value*, 8> contents;
608 ValueNumberedSet() { numbers.resize(1); }
609 ValueNumberedSet(const ValueNumberedSet& other) {
610 numbers = other.numbers;
611 contents = other.contents;
614 typedef SmallPtrSet<Value*, 8>::iterator iterator;
616 iterator begin() { return contents.begin(); }
617 iterator end() { return contents.end(); }
619 bool insert(Value* v) { return contents.insert(v); }
620 void insert(iterator I, iterator E) { contents.insert(I, E); }
621 void erase(Value* v) { contents.erase(v); }
622 unsigned count(Value* v) { return contents.count(v); }
623 size_t size() { return contents.size(); }
625 void set(unsigned i) {
626 if (i >= numbers.size())
632 void operator=(const ValueNumberedSet& other) {
633 contents = other.contents;
634 numbers = other.numbers;
637 void reset(unsigned i) {
638 if (i < numbers.size())
642 bool test(unsigned i) {
643 if (i >= numbers.size())
646 return numbers.test(i);
655 //===----------------------------------------------------------------------===//
657 //===----------------------------------------------------------------------===//
661 class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
662 bool runOnFunction(Function &F);
664 static char ID; // Pass identification, replacement for typeid
665 GVNPRE() : FunctionPass((intptr_t)&ID) { }
669 SmallVector<Instruction*, 8> createdExpressions;
671 DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
672 DenseMap<BasicBlock*, ValueNumberedSet> anticipatedIn;
673 DenseMap<BasicBlock*, ValueNumberedSet> generatedPhis;
675 // This transformation requires dominator postdominator info
676 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
677 AU.setPreservesCFG();
678 AU.addRequiredID(BreakCriticalEdgesID);
679 AU.addRequired<UnifyFunctionExitNodes>();
680 AU.addRequired<DominatorTree>();
684 // FIXME: eliminate or document these better
685 void dump(ValueNumberedSet& s) const ;
686 void clean(ValueNumberedSet& set) ;
687 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ;
688 Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) ;
689 void phi_translate_set(ValueNumberedSet& anticIn, BasicBlock* pred,
690 BasicBlock* succ, ValueNumberedSet& out) ;
692 void topo_sort(ValueNumberedSet& set,
693 SmallVector<Value*, 8>& vec) ;
698 void val_insert(ValueNumberedSet& s, Value* v) ;
699 void val_replace(ValueNumberedSet& s, Value* v) ;
700 bool dependsOnInvoke(Value* V) ;
701 void buildsets_availout(BasicBlock::iterator I,
702 ValueNumberedSet& currAvail,
703 ValueNumberedSet& currPhis,
704 ValueNumberedSet& currExps,
705 SmallPtrSet<Value*, 16>& currTemps);
706 bool buildsets_anticout(BasicBlock* BB,
707 ValueNumberedSet& anticOut,
708 SmallPtrSet<BasicBlock*, 8>& visited);
709 unsigned buildsets_anticin(BasicBlock* BB,
710 ValueNumberedSet& anticOut,
711 ValueNumberedSet& currExps,
712 SmallPtrSet<Value*, 16>& currTemps,
713 SmallPtrSet<BasicBlock*, 8>& visited);
714 void buildsets(Function& F) ;
716 void insertion_pre(Value* e, BasicBlock* BB,
717 DenseMap<BasicBlock*, Value*>& avail,
718 std::map<BasicBlock*,ValueNumberedSet>& new_set);
719 unsigned insertion_mergepoint(SmallVector<Value*, 8>& workList,
720 df_iterator<DomTreeNode*>& D,
721 std::map<BasicBlock*, ValueNumberedSet>& new_set);
722 bool insertion(Function& F) ;
730 // createGVNPREPass - The public interface to this file...
731 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
733 static RegisterPass<GVNPRE> X("gvnpre",
734 "Global Value Numbering/Partial Redundancy Elimination");
737 STATISTIC(NumInsertedVals, "Number of values inserted");
738 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
739 STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
741 /// find_leader - Given a set and a value number, return the first
742 /// element of the set with that value number, or 0 if no such element
744 Value* GVNPRE::find_leader(ValueNumberedSet& vals, uint32_t v) {
748 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
750 if (v == VN.lookup(*I))
753 assert(0 && "No leader found, but present bit is set?");
757 /// val_insert - Insert a value into a set only if there is not a value
758 /// with the same value number already in the set
759 void GVNPRE::val_insert(ValueNumberedSet& s, Value* v) {
760 uint32_t num = VN.lookup(v);
765 /// val_replace - Insert a value into a set, replacing any values already in
766 /// the set that have the same value number
767 void GVNPRE::val_replace(ValueNumberedSet& s, Value* v) {
768 if (s.count(v)) return;
770 uint32_t num = VN.lookup(v);
771 Value* leader = find_leader(s, num);
778 /// phi_translate - Given a value, its parent block, and a predecessor of its
779 /// parent, translate the value into legal for the predecessor block. This
780 /// means translating its operands (and recursively, their operands) through
781 /// any phi nodes in the parent into values available in the predecessor
782 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
787 if (CastInst* U = dyn_cast<CastInst>(V)) {
789 if (isa<Instruction>(U->getOperand(0)))
790 newOp1 = phi_translate(U->getOperand(0), pred, succ);
792 newOp1 = U->getOperand(0);
797 if (newOp1 != U->getOperand(0)) {
798 Instruction* newVal = 0;
799 if (CastInst* C = dyn_cast<CastInst>(U))
800 newVal = CastInst::create(C->getOpcode(),
801 newOp1, C->getType(),
802 C->getName()+".expr");
804 uint32_t v = VN.lookup_or_add(newVal);
806 Value* leader = find_leader(availableOut[pred], v);
808 createdExpressions.push_back(newVal);
818 } if (isa<BinaryOperator>(V) || isa<CmpInst>(V) ||
819 isa<ExtractElementInst>(V)) {
820 User* U = cast<User>(V);
823 if (isa<Instruction>(U->getOperand(0)))
824 newOp1 = phi_translate(U->getOperand(0), pred, succ);
826 newOp1 = U->getOperand(0);
832 if (isa<Instruction>(U->getOperand(1)))
833 newOp2 = phi_translate(U->getOperand(1), pred, succ);
835 newOp2 = U->getOperand(1);
840 if (newOp1 != U->getOperand(0) || newOp2 != U->getOperand(1)) {
841 Instruction* newVal = 0;
842 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
843 newVal = BinaryOperator::create(BO->getOpcode(),
845 BO->getName()+".expr");
846 else if (CmpInst* C = dyn_cast<CmpInst>(U))
847 newVal = CmpInst::create(C->getOpcode(),
850 C->getName()+".expr");
851 else if (ExtractElementInst* E = dyn_cast<ExtractElementInst>(U))
852 newVal = new ExtractElementInst(newOp1, newOp2, E->getName()+".expr");
854 uint32_t v = VN.lookup_or_add(newVal);
856 Value* leader = find_leader(availableOut[pred], v);
858 createdExpressions.push_back(newVal);
867 // Ternary Operations
868 } else if (isa<ShuffleVectorInst>(V) || isa<InsertElementInst>(V) ||
869 isa<SelectInst>(V)) {
870 User* U = cast<User>(V);
873 if (isa<Instruction>(U->getOperand(0)))
874 newOp1 = phi_translate(U->getOperand(0), pred, succ);
876 newOp1 = U->getOperand(0);
882 if (isa<Instruction>(U->getOperand(1)))
883 newOp2 = phi_translate(U->getOperand(1), pred, succ);
885 newOp2 = U->getOperand(1);
891 if (isa<Instruction>(U->getOperand(2)))
892 newOp3 = phi_translate(U->getOperand(2), pred, succ);
894 newOp3 = U->getOperand(2);
899 if (newOp1 != U->getOperand(0) ||
900 newOp2 != U->getOperand(1) ||
901 newOp3 != U->getOperand(2)) {
902 Instruction* newVal = 0;
903 if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
904 newVal = new ShuffleVectorInst(newOp1, newOp2, newOp3,
905 S->getName()+".expr");
906 else if (InsertElementInst* I = dyn_cast<InsertElementInst>(U))
907 newVal = new InsertElementInst(newOp1, newOp2, newOp3,
908 I->getName()+".expr");
909 else if (SelectInst* I = dyn_cast<SelectInst>(U))
910 newVal = new SelectInst(newOp1, newOp2, newOp3, I->getName()+".expr");
912 uint32_t v = VN.lookup_or_add(newVal);
914 Value* leader = find_leader(availableOut[pred], v);
916 createdExpressions.push_back(newVal);
926 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
928 if (isa<Instruction>(U->getPointerOperand()))
929 newOp1 = phi_translate(U->getPointerOperand(), pred, succ);
931 newOp1 = U->getPointerOperand();
936 bool changed_idx = false;
937 SmallVector<Value*, 4> newIdx;
938 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
940 if (isa<Instruction>(*I)) {
941 Value* newVal = phi_translate(*I, pred, succ);
942 newIdx.push_back(newVal);
946 newIdx.push_back(*I);
949 if (newOp1 != U->getPointerOperand() || changed_idx) {
950 Instruction* newVal = new GetElementPtrInst(newOp1,
951 newIdx.begin(), newIdx.end(),
952 U->getName()+".expr");
954 uint32_t v = VN.lookup_or_add(newVal);
956 Value* leader = find_leader(availableOut[pred], v);
958 createdExpressions.push_back(newVal);
968 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
969 if (P->getParent() == succ)
970 return P->getIncomingValueForBlock(pred);
976 /// phi_translate_set - Perform phi translation on every element of a set
977 void GVNPRE::phi_translate_set(ValueNumberedSet& anticIn,
978 BasicBlock* pred, BasicBlock* succ,
979 ValueNumberedSet& out) {
980 for (ValueNumberedSet::iterator I = anticIn.begin(),
981 E = anticIn.end(); I != E; ++I) {
982 Value* V = phi_translate(*I, pred, succ);
983 if (V != 0 && !out.test(VN.lookup_or_add(V))) {
985 out.set(VN.lookup(V));
990 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of
991 /// whose inputs is an invoke instruction. If this is true, we cannot safely
992 /// PRE the instruction or anything that depends on it.
993 bool GVNPRE::dependsOnInvoke(Value* V) {
994 if (PHINode* p = dyn_cast<PHINode>(V)) {
995 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
996 if (isa<InvokeInst>(*I))
1004 /// clean - Remove all non-opaque values from the set whose operands are not
1005 /// themselves in the set, as well as all values that depend on invokes (see
1007 void GVNPRE::clean(ValueNumberedSet& set) {
1008 SmallVector<Value*, 8> worklist;
1009 worklist.reserve(set.size());
1010 topo_sort(set, worklist);
1012 for (unsigned i = 0; i < worklist.size(); ++i) {
1013 Value* v = worklist[i];
1016 if (CastInst* U = dyn_cast<CastInst>(v)) {
1017 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1018 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1020 lhsValid = !dependsOnInvoke(U->getOperand(0));
1024 set.reset(VN.lookup(U));
1027 // Handle binary ops
1028 } else if (isa<BinaryOperator>(v) || isa<CmpInst>(v) ||
1029 isa<ExtractElementInst>(v)) {
1030 User* U = cast<User>(v);
1032 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1033 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1035 lhsValid = !dependsOnInvoke(U->getOperand(0));
1037 bool rhsValid = !isa<Instruction>(U->getOperand(1));
1038 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
1040 rhsValid = !dependsOnInvoke(U->getOperand(1));
1042 if (!lhsValid || !rhsValid) {
1044 set.reset(VN.lookup(U));
1047 // Handle ternary ops
1048 } else if (isa<ShuffleVectorInst>(v) || isa<InsertElementInst>(v) ||
1049 isa<SelectInst>(v)) {
1050 User* U = cast<User>(v);
1052 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1053 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1055 lhsValid = !dependsOnInvoke(U->getOperand(0));
1057 bool rhsValid = !isa<Instruction>(U->getOperand(1));
1058 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
1060 rhsValid = !dependsOnInvoke(U->getOperand(1));
1062 bool thirdValid = !isa<Instruction>(U->getOperand(2));
1063 thirdValid |= set.test(VN.lookup(U->getOperand(2)));
1065 thirdValid = !dependsOnInvoke(U->getOperand(2));
1067 if (!lhsValid || !rhsValid || !thirdValid) {
1069 set.reset(VN.lookup(U));
1072 // Handle varargs ops
1073 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(v)) {
1074 bool ptrValid = !isa<Instruction>(U->getPointerOperand());
1075 ptrValid |= set.test(VN.lookup(U->getPointerOperand()));
1077 ptrValid = !dependsOnInvoke(U->getPointerOperand());
1079 bool varValid = true;
1080 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
1083 varValid &= !isa<Instruction>(*I) || set.test(VN.lookup(*I));
1084 varValid &= !dependsOnInvoke(*I);
1087 if (!ptrValid || !varValid) {
1089 set.reset(VN.lookup(U));
1095 /// topo_sort - Given a set of values, sort them by topological
1096 /// order into the provided vector.
1097 void GVNPRE::topo_sort(ValueNumberedSet& set, SmallVector<Value*, 8>& vec) {
1098 SmallPtrSet<Value*, 16> visited;
1099 SmallVector<Value*, 8> stack;
1100 for (ValueNumberedSet::iterator I = set.begin(), E = set.end();
1102 if (visited.count(*I) == 0)
1103 stack.push_back(*I);
1105 while (!stack.empty()) {
1106 Value* e = stack.back();
1109 if (CastInst* U = dyn_cast<CastInst>(e)) {
1110 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1112 if (l != 0 && isa<Instruction>(l) &&
1113 visited.count(l) == 0)
1121 // Handle binary ops
1122 } else if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1123 isa<ExtractElementInst>(e)) {
1124 User* U = cast<User>(e);
1125 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1126 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1128 if (l != 0 && isa<Instruction>(l) &&
1129 visited.count(l) == 0)
1131 else if (r != 0 && isa<Instruction>(r) &&
1132 visited.count(r) == 0)
1140 // Handle ternary ops
1141 } else if (isa<InsertElementInst>(e) || isa<ShuffleVectorInst>(e) ||
1142 isa<SelectInst>(e)) {
1143 User* U = cast<User>(e);
1144 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1145 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1146 Value* m = find_leader(set, VN.lookup(U->getOperand(2)));
1148 if (l != 0 && isa<Instruction>(l) &&
1149 visited.count(l) == 0)
1151 else if (r != 0 && isa<Instruction>(r) &&
1152 visited.count(r) == 0)
1154 else if (m != 0 && isa<Instruction>(m) &&
1155 visited.count(m) == 0)
1163 // Handle vararg ops
1164 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(e)) {
1165 Value* p = find_leader(set, VN.lookup(U->getPointerOperand()));
1167 if (p != 0 && isa<Instruction>(p) &&
1168 visited.count(p) == 0)
1171 bool push_va = false;
1172 for (GetElementPtrInst::op_iterator I = U->idx_begin(),
1173 E = U->idx_end(); I != E; ++I) {
1174 Value * v = find_leader(set, VN.lookup(*I));
1175 if (v != 0 && isa<Instruction>(v) && visited.count(v) == 0) {
1188 // Handle opaque ops
1200 /// dump - Dump a set of values to standard error
1201 void GVNPRE::dump(ValueNumberedSet& s) const {
1203 for (ValueNumberedSet::iterator I = s.begin(), E = s.end();
1205 DOUT << "" << VN.lookup(*I) << ": ";
1206 DEBUG((*I)->dump());
1211 /// elimination - Phase 3 of the main algorithm. Perform full redundancy
1212 /// elimination by walking the dominator tree and removing any instruction that
1213 /// is dominated by another instruction with the same value number.
1214 bool GVNPRE::elimination() {
1215 bool changed_function = false;
1217 SmallVector<std::pair<Instruction*, Value*>, 8> replace;
1218 SmallVector<Instruction*, 8> erase;
1220 DominatorTree& DT = getAnalysis<DominatorTree>();
1222 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1223 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1224 BasicBlock* BB = DI->getBlock();
1226 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1229 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI) ||
1230 isa<ShuffleVectorInst>(BI) || isa<InsertElementInst>(BI) ||
1231 isa<ExtractElementInst>(BI) || isa<SelectInst>(BI) ||
1232 isa<CastInst>(BI) || isa<GetElementPtrInst>(BI)) {
1234 if (availableOut[BB].test(VN.lookup(BI)) &&
1235 !availableOut[BB].count(BI)) {
1236 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
1237 if (Instruction* Instr = dyn_cast<Instruction>(leader))
1238 if (Instr->getParent() != 0 && Instr != BI) {
1239 replace.push_back(std::make_pair(BI, leader));
1240 erase.push_back(BI);
1248 while (!replace.empty()) {
1249 std::pair<Instruction*, Value*> rep = replace.back();
1251 rep.first->replaceAllUsesWith(rep.second);
1252 changed_function = true;
1255 for (SmallVector<Instruction*, 8>::iterator I = erase.begin(),
1256 E = erase.end(); I != E; ++I)
1257 (*I)->eraseFromParent();
1259 return changed_function;
1262 /// cleanup - Delete any extraneous values that were created to represent
1263 /// expressions without leaders.
1264 void GVNPRE::cleanup() {
1265 while (!createdExpressions.empty()) {
1266 Instruction* I = createdExpressions.back();
1267 createdExpressions.pop_back();
1273 /// buildsets_availout - When calculating availability, handle an instruction
1274 /// by inserting it into the appropriate sets
1275 void GVNPRE::buildsets_availout(BasicBlock::iterator I,
1276 ValueNumberedSet& currAvail,
1277 ValueNumberedSet& currPhis,
1278 ValueNumberedSet& currExps,
1279 SmallPtrSet<Value*, 16>& currTemps) {
1281 if (PHINode* p = dyn_cast<PHINode>(I)) {
1282 unsigned num = VN.lookup_or_add(p);
1288 } else if (CastInst* U = dyn_cast<CastInst>(I)) {
1289 Value* leftValue = U->getOperand(0);
1291 unsigned num = VN.lookup_or_add(U);
1293 if (isa<Instruction>(leftValue))
1294 if (!currExps.test(VN.lookup(leftValue))) {
1295 currExps.insert(leftValue);
1296 currExps.set(VN.lookup(leftValue));
1299 if (!currExps.test(num)) {
1304 // Handle binary ops
1305 } else if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
1306 isa<ExtractElementInst>(I)) {
1307 User* U = cast<User>(I);
1308 Value* leftValue = U->getOperand(0);
1309 Value* rightValue = U->getOperand(1);
1311 unsigned num = VN.lookup_or_add(U);
1313 if (isa<Instruction>(leftValue))
1314 if (!currExps.test(VN.lookup(leftValue))) {
1315 currExps.insert(leftValue);
1316 currExps.set(VN.lookup(leftValue));
1319 if (isa<Instruction>(rightValue))
1320 if (!currExps.test(VN.lookup(rightValue))) {
1321 currExps.insert(rightValue);
1322 currExps.set(VN.lookup(rightValue));
1325 if (!currExps.test(num)) {
1330 // Handle ternary ops
1331 } else if (isa<InsertElementInst>(I) || isa<ShuffleVectorInst>(I) ||
1332 isa<SelectInst>(I)) {
1333 User* U = cast<User>(I);
1334 Value* leftValue = U->getOperand(0);
1335 Value* rightValue = U->getOperand(1);
1336 Value* thirdValue = U->getOperand(2);
1338 VN.lookup_or_add(U);
1340 unsigned num = VN.lookup_or_add(U);
1342 if (isa<Instruction>(leftValue))
1343 if (!currExps.test(VN.lookup(leftValue))) {
1344 currExps.insert(leftValue);
1345 currExps.set(VN.lookup(leftValue));
1347 if (isa<Instruction>(rightValue))
1348 if (!currExps.test(VN.lookup(rightValue))) {
1349 currExps.insert(rightValue);
1350 currExps.set(VN.lookup(rightValue));
1352 if (isa<Instruction>(thirdValue))
1353 if (!currExps.test(VN.lookup(thirdValue))) {
1354 currExps.insert(thirdValue);
1355 currExps.set(VN.lookup(thirdValue));
1358 if (!currExps.test(num)) {
1363 // Handle vararg ops
1364 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(I)) {
1365 Value* ptrValue = U->getPointerOperand();
1367 VN.lookup_or_add(U);
1369 unsigned num = VN.lookup_or_add(U);
1371 if (isa<Instruction>(ptrValue))
1372 if (!currExps.test(VN.lookup(ptrValue))) {
1373 currExps.insert(ptrValue);
1374 currExps.set(VN.lookup(ptrValue));
1377 for (GetElementPtrInst::op_iterator OI = U->idx_begin(), OE = U->idx_end();
1379 if (isa<Instruction>(*OI) && !currExps.test(VN.lookup(*OI))) {
1380 currExps.insert(*OI);
1381 currExps.set(VN.lookup(*OI));
1384 if (!currExps.test(VN.lookup(U))) {
1389 // Handle opaque ops
1390 } else if (!I->isTerminator()){
1391 VN.lookup_or_add(I);
1393 currTemps.insert(I);
1396 if (!I->isTerminator())
1397 if (!currAvail.test(VN.lookup(I))) {
1398 currAvail.insert(I);
1399 currAvail.set(VN.lookup(I));
1403 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
1404 /// set as a function of the ANTIC_IN set of the block's predecessors
1405 bool GVNPRE::buildsets_anticout(BasicBlock* BB,
1406 ValueNumberedSet& anticOut,
1407 SmallPtrSet<BasicBlock*, 8>& visited) {
1408 if (BB->getTerminator()->getNumSuccessors() == 1) {
1409 if (BB->getTerminator()->getSuccessor(0) != BB &&
1410 visited.count(BB->getTerminator()->getSuccessor(0)) == 0) {
1414 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
1415 BB, BB->getTerminator()->getSuccessor(0), anticOut);
1417 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
1418 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
1419 for (ValueNumberedSet::iterator I = anticipatedIn[first].begin(),
1420 E = anticipatedIn[first].end(); I != E; ++I) {
1421 anticOut.insert(*I);
1422 anticOut.set(VN.lookup(*I));
1425 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
1426 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
1427 ValueNumberedSet& succAnticIn = anticipatedIn[currSucc];
1429 SmallVector<Value*, 16> temp;
1431 for (ValueNumberedSet::iterator I = anticOut.begin(),
1432 E = anticOut.end(); I != E; ++I)
1433 if (!succAnticIn.test(VN.lookup(*I)))
1436 for (SmallVector<Value*, 16>::iterator I = temp.begin(), E = temp.end();
1439 anticOut.reset(VN.lookup(*I));
1447 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
1448 /// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN
1449 /// sets populated in buildsets_availout
1450 unsigned GVNPRE::buildsets_anticin(BasicBlock* BB,
1451 ValueNumberedSet& anticOut,
1452 ValueNumberedSet& currExps,
1453 SmallPtrSet<Value*, 16>& currTemps,
1454 SmallPtrSet<BasicBlock*, 8>& visited) {
1455 ValueNumberedSet& anticIn = anticipatedIn[BB];
1456 unsigned old = anticIn.size();
1458 bool defer = buildsets_anticout(BB, anticOut, visited);
1464 for (ValueNumberedSet::iterator I = anticOut.begin(),
1465 E = anticOut.end(); I != E; ++I) {
1467 anticIn.set(VN.lookup(*I));
1469 for (ValueNumberedSet::iterator I = currExps.begin(),
1470 E = currExps.end(); I != E; ++I) {
1471 if (!anticIn.test(VN.lookup(*I))) {
1473 anticIn.set(VN.lookup(*I));
1477 for (SmallPtrSet<Value*, 16>::iterator I = currTemps.begin(),
1478 E = currTemps.end(); I != E; ++I) {
1480 anticIn.reset(VN.lookup(*I));
1486 if (old != anticIn.size())
1492 /// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT
1493 /// and the ANTIC_IN sets.
1494 void GVNPRE::buildsets(Function& F) {
1495 DenseMap<BasicBlock*, ValueNumberedSet> generatedExpressions;
1496 DenseMap<BasicBlock*, SmallPtrSet<Value*, 16> > generatedTemporaries;
1498 DominatorTree &DT = getAnalysis<DominatorTree>();
1500 // Phase 1, Part 1: calculate AVAIL_OUT
1502 // Top-down walk of the dominator tree
1503 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1504 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1506 // Get the sets to update for this block
1507 ValueNumberedSet& currExps = generatedExpressions[DI->getBlock()];
1508 ValueNumberedSet& currPhis = generatedPhis[DI->getBlock()];
1509 SmallPtrSet<Value*, 16>& currTemps = generatedTemporaries[DI->getBlock()];
1510 ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
1512 BasicBlock* BB = DI->getBlock();
1514 // A block inherits AVAIL_OUT from its dominator
1515 if (DI->getIDom() != 0)
1516 currAvail = availableOut[DI->getIDom()->getBlock()];
1518 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1520 buildsets_availout(BI, currAvail, currPhis, currExps,
1525 // Phase 1, Part 2: calculate ANTIC_IN
1527 SmallPtrSet<BasicBlock*, 8> visited;
1528 SmallPtrSet<BasicBlock*, 4> block_changed;
1529 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
1530 block_changed.insert(FI);
1532 bool changed = true;
1533 unsigned iterations = 0;
1537 ValueNumberedSet anticOut;
1539 // Postorder walk of the CFG
1540 for (po_iterator<BasicBlock*> BBI = po_begin(&F.getEntryBlock()),
1541 BBE = po_end(&F.getEntryBlock()); BBI != BBE; ++BBI) {
1542 BasicBlock* BB = *BBI;
1544 if (block_changed.count(BB) != 0) {
1545 unsigned ret = buildsets_anticin(BB, anticOut,generatedExpressions[BB],
1546 generatedTemporaries[BB], visited);
1555 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1557 block_changed.insert(*PI);
1560 block_changed.erase(BB);
1562 changed |= (ret == 2);
1571 /// insertion_pre - When a partial redundancy has been identified, eliminate it
1572 /// by inserting appropriate values into the predecessors and a phi node in
1574 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
1575 DenseMap<BasicBlock*, Value*>& avail,
1576 std::map<BasicBlock*, ValueNumberedSet>& new_sets) {
1577 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1578 Value* e2 = avail[*PI];
1579 if (!availableOut[*PI].test(VN.lookup(e2))) {
1580 User* U = cast<User>(e2);
1583 if (isa<BinaryOperator>(U->getOperand(0)) ||
1584 isa<CmpInst>(U->getOperand(0)) ||
1585 isa<ShuffleVectorInst>(U->getOperand(0)) ||
1586 isa<ExtractElementInst>(U->getOperand(0)) ||
1587 isa<InsertElementInst>(U->getOperand(0)) ||
1588 isa<SelectInst>(U->getOperand(0)) ||
1589 isa<CastInst>(U->getOperand(0)) ||
1590 isa<GetElementPtrInst>(U->getOperand(0)))
1591 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1593 s1 = U->getOperand(0);
1597 if (isa<BinaryOperator>(U) ||
1599 isa<ShuffleVectorInst>(U) ||
1600 isa<ExtractElementInst>(U) ||
1601 isa<InsertElementInst>(U) ||
1603 if (isa<BinaryOperator>(U->getOperand(1)) ||
1604 isa<CmpInst>(U->getOperand(1)) ||
1605 isa<ShuffleVectorInst>(U->getOperand(1)) ||
1606 isa<ExtractElementInst>(U->getOperand(1)) ||
1607 isa<InsertElementInst>(U->getOperand(1)) ||
1608 isa<SelectInst>(U->getOperand(1)) ||
1609 isa<CastInst>(U->getOperand(1)) ||
1610 isa<GetElementPtrInst>(U->getOperand(1))) {
1611 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1613 s2 = U->getOperand(1);
1616 // Ternary Operators
1618 if (isa<ShuffleVectorInst>(U) ||
1619 isa<InsertElementInst>(U) ||
1621 if (isa<BinaryOperator>(U->getOperand(2)) ||
1622 isa<CmpInst>(U->getOperand(2)) ||
1623 isa<ShuffleVectorInst>(U->getOperand(2)) ||
1624 isa<ExtractElementInst>(U->getOperand(2)) ||
1625 isa<InsertElementInst>(U->getOperand(2)) ||
1626 isa<SelectInst>(U->getOperand(2)) ||
1627 isa<CastInst>(U->getOperand(2)) ||
1628 isa<GetElementPtrInst>(U->getOperand(2))) {
1629 s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2)));
1631 s3 = U->getOperand(2);
1635 SmallVector<Value*, 4> sVarargs;
1636 if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U)) {
1637 for (GetElementPtrInst::op_iterator OI = G->idx_begin(),
1638 OE = G->idx_end(); OI != OE; ++OI) {
1639 if (isa<BinaryOperator>(*OI) ||
1640 isa<CmpInst>(*OI) ||
1641 isa<ShuffleVectorInst>(*OI) ||
1642 isa<ExtractElementInst>(*OI) ||
1643 isa<InsertElementInst>(*OI) ||
1644 isa<SelectInst>(*OI) ||
1645 isa<CastInst>(*OI) ||
1646 isa<GetElementPtrInst>(*OI)) {
1647 sVarargs.push_back(find_leader(availableOut[*PI],
1650 sVarargs.push_back(*OI);
1656 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1657 newVal = BinaryOperator::create(BO->getOpcode(), s1, s2,
1658 BO->getName()+".gvnpre",
1659 (*PI)->getTerminator());
1660 else if (CmpInst* C = dyn_cast<CmpInst>(U))
1661 newVal = CmpInst::create(C->getOpcode(), C->getPredicate(), s1, s2,
1662 C->getName()+".gvnpre",
1663 (*PI)->getTerminator());
1664 else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
1665 newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre",
1666 (*PI)->getTerminator());
1667 else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U))
1668 newVal = new InsertElementInst(s1, s2, s3, S->getName()+".gvnpre",
1669 (*PI)->getTerminator());
1670 else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U))
1671 newVal = new ExtractElementInst(s1, s2, S->getName()+".gvnpre",
1672 (*PI)->getTerminator());
1673 else if (SelectInst* S = dyn_cast<SelectInst>(U))
1674 newVal = new SelectInst(s1, s2, s3, S->getName()+".gvnpre",
1675 (*PI)->getTerminator());
1676 else if (CastInst* C = dyn_cast<CastInst>(U))
1677 newVal = CastInst::create(C->getOpcode(), s1, C->getType(),
1678 C->getName()+".gvnpre",
1679 (*PI)->getTerminator());
1680 else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U))
1681 newVal = new GetElementPtrInst(s1, sVarargs.begin(), sVarargs.end(),
1682 G->getName()+".gvnpre",
1683 (*PI)->getTerminator());
1686 VN.add(newVal, VN.lookup(U));
1688 ValueNumberedSet& predAvail = availableOut[*PI];
1689 val_replace(predAvail, newVal);
1690 val_replace(new_sets[*PI], newVal);
1691 predAvail.set(VN.lookup(newVal));
1693 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1694 if (av != avail.end())
1696 avail.insert(std::make_pair(*PI, newVal));
1704 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1706 p = new PHINode(avail[*PI]->getType(), "gvnpre-join", BB->begin());
1708 p->addIncoming(avail[*PI], *PI);
1711 VN.add(p, VN.lookup(e));
1712 val_replace(availableOut[BB], p);
1713 availableOut[BB].set(VN.lookup(e));
1714 generatedPhis[BB].insert(p);
1715 generatedPhis[BB].set(VN.lookup(e));
1716 new_sets[BB].insert(p);
1717 new_sets[BB].set(VN.lookup(e));
1722 /// insertion_mergepoint - When walking the dom tree, check at each merge
1723 /// block for the possibility of a partial redundancy. If present, eliminate it
1724 unsigned GVNPRE::insertion_mergepoint(SmallVector<Value*, 8>& workList,
1725 df_iterator<DomTreeNode*>& D,
1726 std::map<BasicBlock*, ValueNumberedSet >& new_sets) {
1727 bool changed_function = false;
1728 bool new_stuff = false;
1730 BasicBlock* BB = D->getBlock();
1731 for (unsigned i = 0; i < workList.size(); ++i) {
1732 Value* e = workList[i];
1734 if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1735 isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) ||
1736 isa<ShuffleVectorInst>(e) || isa<SelectInst>(e) || isa<CastInst>(e) ||
1737 isa<GetElementPtrInst>(e)) {
1738 if (availableOut[D->getIDom()->getBlock()].test(VN.lookup(e)))
1741 DenseMap<BasicBlock*, Value*> avail;
1742 bool by_some = false;
1743 bool all_same = true;
1744 Value * first_s = 0;
1746 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1748 Value *e2 = phi_translate(e, *PI, BB);
1749 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1752 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1753 if (av != avail.end())
1755 avail.insert(std::make_pair(*PI, e2));
1758 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1759 if (av != avail.end())
1761 avail.insert(std::make_pair(*PI, e3));
1766 else if (first_s != e3)
1771 if (by_some && !all_same &&
1772 !generatedPhis[BB].test(VN.lookup(e))) {
1773 insertion_pre(e, BB, avail, new_sets);
1775 changed_function = true;
1781 unsigned retval = 0;
1782 if (changed_function)
1790 /// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for
1791 /// merge points. When one is found, check for a partial redundancy. If one is
1792 /// present, eliminate it. Repeat this walk until no changes are made.
1793 bool GVNPRE::insertion(Function& F) {
1794 bool changed_function = false;
1796 DominatorTree &DT = getAnalysis<DominatorTree>();
1798 std::map<BasicBlock*, ValueNumberedSet> new_sets;
1799 bool new_stuff = true;
1802 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1803 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1804 BasicBlock* BB = DI->getBlock();
1809 ValueNumberedSet& availOut = availableOut[BB];
1810 ValueNumberedSet& anticIn = anticipatedIn[BB];
1812 // Replace leaders with leaders inherited from dominator
1813 if (DI->getIDom() != 0) {
1814 ValueNumberedSet& dom_set = new_sets[DI->getIDom()->getBlock()];
1815 for (ValueNumberedSet::iterator I = dom_set.begin(),
1816 E = dom_set.end(); I != E; ++I) {
1817 val_replace(new_sets[BB], *I);
1818 val_replace(availOut, *I);
1822 // If there is more than one predecessor...
1823 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
1824 SmallVector<Value*, 8> workList;
1825 workList.reserve(anticIn.size());
1826 topo_sort(anticIn, workList);
1828 unsigned result = insertion_mergepoint(workList, DI, new_sets);
1830 changed_function = true;
1837 return changed_function;
1840 // GVNPRE::runOnFunction - This is the main transformation entry point for a
1843 bool GVNPRE::runOnFunction(Function &F) {
1844 // Clean out global sets from any previous functions
1846 createdExpressions.clear();
1847 availableOut.clear();
1848 anticipatedIn.clear();
1849 generatedPhis.clear();
1851 bool changed_function = false;
1853 // Phase 1: BuildSets
1854 // This phase calculates the AVAIL_OUT and ANTIC_IN sets
1858 // This phase inserts values to make partially redundant values
1860 changed_function |= insertion(F);
1862 // Phase 3: Eliminate
1863 // This phase performs trivial full redundancy elimination
1864 changed_function |= elimination();
1867 // This phase cleans up values that were created solely
1868 // as leaders for expressions
1871 return changed_function;