1 //===- GVNPRE.cpp - Eliminate redundant values and expressions ------------===//
3 // The LLVM Compiler Infrastructure
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.
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"
45 //===----------------------------------------------------------------------===//
47 //===----------------------------------------------------------------------===//
49 /// This class holds the mapping between values and value numbers. It is used
50 /// as an efficient mechanism to determine the expression-wise equivalence of
54 enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
55 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
56 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
57 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
58 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
59 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
60 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
61 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
62 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
63 PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY,
66 ExpressionOpcode opcode;
71 SmallVector<uint32_t, 4> varargs;
74 Expression(ExpressionOpcode o) : opcode(o) { }
76 bool operator==(const Expression &other) const {
77 if (opcode != other.opcode)
79 else if (opcode == EMPTY || opcode == TOMBSTONE)
81 else if (type != other.type)
83 else if (firstVN != other.firstVN)
85 else if (secondVN != other.secondVN)
87 else if (thirdVN != other.thirdVN)
90 if (varargs.size() != other.varargs.size())
93 for (size_t i = 0; i < varargs.size(); ++i)
94 if (varargs[i] != other.varargs[i])
101 bool operator!=(const Expression &other) const {
102 if (opcode != other.opcode)
104 else if (opcode == EMPTY || opcode == TOMBSTONE)
106 else if (type != other.type)
108 else if (firstVN != other.firstVN)
110 else if (secondVN != other.secondVN)
112 else if (thirdVN != other.thirdVN)
115 if (varargs.size() != other.varargs.size())
118 for (size_t i = 0; i < varargs.size(); ++i)
119 if (varargs[i] != other.varargs[i])
129 class VISIBILITY_HIDDEN ValueTable {
131 DenseMap<Value*, uint32_t> valueNumbering;
132 DenseMap<Expression, uint32_t> expressionNumbering;
134 uint32_t nextValueNumber;
136 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
137 Expression::ExpressionOpcode getOpcode(CmpInst* C);
138 Expression::ExpressionOpcode getOpcode(CastInst* C);
139 Expression create_expression(BinaryOperator* BO);
140 Expression create_expression(CmpInst* C);
141 Expression create_expression(ShuffleVectorInst* V);
142 Expression create_expression(ExtractElementInst* C);
143 Expression create_expression(InsertElementInst* V);
144 Expression create_expression(SelectInst* V);
145 Expression create_expression(CastInst* C);
146 Expression create_expression(GetElementPtrInst* G);
148 ValueTable() { nextValueNumber = 1; }
149 uint32_t lookup_or_add(Value* V);
150 uint32_t lookup(Value* V) const;
151 void add(Value* V, uint32_t num);
153 void erase(Value* v);
159 template <> struct DenseMapKeyInfo<Expression> {
160 static inline Expression getEmptyKey() { return Expression(Expression::EMPTY); }
161 static inline Expression getTombstoneKey() { return Expression(Expression::TOMBSTONE); }
163 static unsigned getHashValue(const Expression e) {
164 unsigned hash = e.opcode;
166 hash = e.firstVN + hash * 37;
167 hash = e.secondVN + hash * 37;
168 hash = e.thirdVN + hash * 37;
170 hash = (unsigned)((uintptr_t)e.type >> 4) ^
171 (unsigned)((uintptr_t)e.type >> 9) +
174 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), E = e.varargs.end();
176 hash = *I + hash * 37;
180 static bool isPod() { return true; }
184 //===----------------------------------------------------------------------===//
185 // ValueTable Internal Functions
186 //===----------------------------------------------------------------------===//
187 Expression::ExpressionOpcode
188 ValueTable::getOpcode(BinaryOperator* BO) {
189 switch(BO->getOpcode()) {
190 case Instruction::Add:
191 return Expression::ADD;
192 case Instruction::Sub:
193 return Expression::SUB;
194 case Instruction::Mul:
195 return Expression::MUL;
196 case Instruction::UDiv:
197 return Expression::UDIV;
198 case Instruction::SDiv:
199 return Expression::SDIV;
200 case Instruction::FDiv:
201 return Expression::FDIV;
202 case Instruction::URem:
203 return Expression::UREM;
204 case Instruction::SRem:
205 return Expression::SREM;
206 case Instruction::FRem:
207 return Expression::FREM;
208 case Instruction::Shl:
209 return Expression::SHL;
210 case Instruction::LShr:
211 return Expression::LSHR;
212 case Instruction::AShr:
213 return Expression::ASHR;
214 case Instruction::And:
215 return Expression::AND;
216 case Instruction::Or:
217 return Expression::OR;
218 case Instruction::Xor:
219 return Expression::XOR;
221 // THIS SHOULD NEVER HAPPEN
223 assert(0 && "Binary operator with unknown opcode?");
224 return Expression::ADD;
228 Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
229 if (C->getOpcode() == Instruction::ICmp) {
230 switch (C->getPredicate()) {
231 case ICmpInst::ICMP_EQ:
232 return Expression::ICMPEQ;
233 case ICmpInst::ICMP_NE:
234 return Expression::ICMPNE;
235 case ICmpInst::ICMP_UGT:
236 return Expression::ICMPUGT;
237 case ICmpInst::ICMP_UGE:
238 return Expression::ICMPUGE;
239 case ICmpInst::ICMP_ULT:
240 return Expression::ICMPULT;
241 case ICmpInst::ICMP_ULE:
242 return Expression::ICMPULE;
243 case ICmpInst::ICMP_SGT:
244 return Expression::ICMPSGT;
245 case ICmpInst::ICMP_SGE:
246 return Expression::ICMPSGE;
247 case ICmpInst::ICMP_SLT:
248 return Expression::ICMPSLT;
249 case ICmpInst::ICMP_SLE:
250 return Expression::ICMPSLE;
252 // THIS SHOULD NEVER HAPPEN
254 assert(0 && "Comparison with unknown predicate?");
255 return Expression::ICMPEQ;
258 switch (C->getPredicate()) {
259 case FCmpInst::FCMP_OEQ:
260 return Expression::FCMPOEQ;
261 case FCmpInst::FCMP_OGT:
262 return Expression::FCMPOGT;
263 case FCmpInst::FCMP_OGE:
264 return Expression::FCMPOGE;
265 case FCmpInst::FCMP_OLT:
266 return Expression::FCMPOLT;
267 case FCmpInst::FCMP_OLE:
268 return Expression::FCMPOLE;
269 case FCmpInst::FCMP_ONE:
270 return Expression::FCMPONE;
271 case FCmpInst::FCMP_ORD:
272 return Expression::FCMPORD;
273 case FCmpInst::FCMP_UNO:
274 return Expression::FCMPUNO;
275 case FCmpInst::FCMP_UEQ:
276 return Expression::FCMPUEQ;
277 case FCmpInst::FCMP_UGT:
278 return Expression::FCMPUGT;
279 case FCmpInst::FCMP_UGE:
280 return Expression::FCMPUGE;
281 case FCmpInst::FCMP_ULT:
282 return Expression::FCMPULT;
283 case FCmpInst::FCMP_ULE:
284 return Expression::FCMPULE;
285 case FCmpInst::FCMP_UNE:
286 return Expression::FCMPUNE;
288 // THIS SHOULD NEVER HAPPEN
290 assert(0 && "Comparison with unknown predicate?");
291 return Expression::FCMPOEQ;
296 Expression::ExpressionOpcode
297 ValueTable::getOpcode(CastInst* C) {
298 switch(C->getOpcode()) {
299 case Instruction::Trunc:
300 return Expression::TRUNC;
301 case Instruction::ZExt:
302 return Expression::ZEXT;
303 case Instruction::SExt:
304 return Expression::SEXT;
305 case Instruction::FPToUI:
306 return Expression::FPTOUI;
307 case Instruction::FPToSI:
308 return Expression::FPTOSI;
309 case Instruction::UIToFP:
310 return Expression::UITOFP;
311 case Instruction::SIToFP:
312 return Expression::SITOFP;
313 case Instruction::FPTrunc:
314 return Expression::FPTRUNC;
315 case Instruction::FPExt:
316 return Expression::FPEXT;
317 case Instruction::PtrToInt:
318 return Expression::PTRTOINT;
319 case Instruction::IntToPtr:
320 return Expression::INTTOPTR;
321 case Instruction::BitCast:
322 return Expression::BITCAST;
324 // THIS SHOULD NEVER HAPPEN
326 assert(0 && "Cast operator with unknown opcode?");
327 return Expression::BITCAST;
331 Expression ValueTable::create_expression(BinaryOperator* BO) {
334 e.firstVN = lookup_or_add(BO->getOperand(0));
335 e.secondVN = lookup_or_add(BO->getOperand(1));
337 e.type = BO->getType();
338 e.opcode = getOpcode(BO);
343 Expression ValueTable::create_expression(CmpInst* C) {
346 e.firstVN = lookup_or_add(C->getOperand(0));
347 e.secondVN = lookup_or_add(C->getOperand(1));
349 e.type = C->getType();
350 e.opcode = getOpcode(C);
355 Expression ValueTable::create_expression(CastInst* C) {
358 e.firstVN = lookup_or_add(C->getOperand(0));
361 e.type = C->getType();
362 e.opcode = getOpcode(C);
367 Expression ValueTable::create_expression(ShuffleVectorInst* S) {
370 e.firstVN = lookup_or_add(S->getOperand(0));
371 e.secondVN = lookup_or_add(S->getOperand(1));
372 e.thirdVN = lookup_or_add(S->getOperand(2));
373 e.type = S->getType();
374 e.opcode = Expression::SHUFFLE;
379 Expression ValueTable::create_expression(ExtractElementInst* E) {
382 e.firstVN = lookup_or_add(E->getOperand(0));
383 e.secondVN = lookup_or_add(E->getOperand(1));
385 e.type = E->getType();
386 e.opcode = Expression::EXTRACT;
391 Expression ValueTable::create_expression(InsertElementInst* I) {
394 e.firstVN = lookup_or_add(I->getOperand(0));
395 e.secondVN = lookup_or_add(I->getOperand(1));
396 e.thirdVN = lookup_or_add(I->getOperand(2));
397 e.type = I->getType();
398 e.opcode = Expression::INSERT;
403 Expression ValueTable::create_expression(SelectInst* I) {
406 e.firstVN = lookup_or_add(I->getCondition());
407 e.secondVN = lookup_or_add(I->getTrueValue());
408 e.thirdVN = lookup_or_add(I->getFalseValue());
409 e.type = I->getType();
410 e.opcode = Expression::SELECT;
415 Expression ValueTable::create_expression(GetElementPtrInst* G) {
418 e.firstVN = lookup_or_add(G->getPointerOperand());
421 e.type = G->getType();
422 e.opcode = Expression::SELECT;
424 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
426 e.varargs.push_back(lookup_or_add(*I));
431 //===----------------------------------------------------------------------===//
432 // ValueTable External Functions
433 //===----------------------------------------------------------------------===//
435 /// lookup_or_add - Returns the value number for the specified value, assigning
436 /// it a new number if it did not have one before.
437 uint32_t ValueTable::lookup_or_add(Value* V) {
438 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
439 if (VI != valueNumbering.end())
443 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
444 Expression e = create_expression(BO);
446 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
447 if (EI != expressionNumbering.end()) {
448 valueNumbering.insert(std::make_pair(V, EI->second));
451 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
452 valueNumbering.insert(std::make_pair(V, nextValueNumber));
454 return nextValueNumber++;
456 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
457 Expression e = create_expression(C);
459 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
460 if (EI != expressionNumbering.end()) {
461 valueNumbering.insert(std::make_pair(V, EI->second));
464 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
465 valueNumbering.insert(std::make_pair(V, nextValueNumber));
467 return nextValueNumber++;
469 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
470 Expression e = create_expression(U);
472 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
473 if (EI != expressionNumbering.end()) {
474 valueNumbering.insert(std::make_pair(V, EI->second));
477 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
478 valueNumbering.insert(std::make_pair(V, nextValueNumber));
480 return nextValueNumber++;
482 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
483 Expression e = create_expression(U);
485 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
486 if (EI != expressionNumbering.end()) {
487 valueNumbering.insert(std::make_pair(V, EI->second));
490 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
491 valueNumbering.insert(std::make_pair(V, nextValueNumber));
493 return nextValueNumber++;
495 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
496 Expression e = create_expression(U);
498 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
499 if (EI != expressionNumbering.end()) {
500 valueNumbering.insert(std::make_pair(V, EI->second));
503 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
504 valueNumbering.insert(std::make_pair(V, nextValueNumber));
506 return nextValueNumber++;
508 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
509 Expression e = create_expression(U);
511 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
512 if (EI != expressionNumbering.end()) {
513 valueNumbering.insert(std::make_pair(V, EI->second));
516 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
517 valueNumbering.insert(std::make_pair(V, nextValueNumber));
519 return nextValueNumber++;
521 } else if (CastInst* U = dyn_cast<CastInst>(V)) {
522 Expression e = create_expression(U);
524 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
525 if (EI != expressionNumbering.end()) {
526 valueNumbering.insert(std::make_pair(V, EI->second));
529 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
530 valueNumbering.insert(std::make_pair(V, nextValueNumber));
532 return nextValueNumber++;
534 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
535 Expression e = create_expression(U);
537 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
538 if (EI != expressionNumbering.end()) {
539 valueNumbering.insert(std::make_pair(V, EI->second));
542 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
543 valueNumbering.insert(std::make_pair(V, nextValueNumber));
545 return nextValueNumber++;
548 valueNumbering.insert(std::make_pair(V, nextValueNumber));
549 return nextValueNumber++;
553 /// lookup - Returns the value number of the specified value. Fails if
554 /// the value has not yet been numbered.
555 uint32_t ValueTable::lookup(Value* V) const {
556 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
557 if (VI != valueNumbering.end())
560 assert(0 && "Value not numbered?");
565 /// add - Add the specified value with the given value number, removing
566 /// its old number, if any
567 void ValueTable::add(Value* V, uint32_t num) {
568 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
569 if (VI != valueNumbering.end())
570 valueNumbering.erase(VI);
571 valueNumbering.insert(std::make_pair(V, num));
574 /// clear - Remove all entries from the ValueTable
575 void ValueTable::clear() {
576 valueNumbering.clear();
577 expressionNumbering.clear();
581 /// erase - Remove a value from the value numbering
582 void ValueTable::erase(Value* V) {
583 valueNumbering.erase(V);
586 /// size - Return the number of assigned value numbers
587 unsigned ValueTable::size() {
588 // NOTE: zero is never assigned
589 return nextValueNumber;
592 //===----------------------------------------------------------------------===//
593 // ValueNumberedSet Class
594 //===----------------------------------------------------------------------===//
596 class ValueNumberedSet {
598 SmallPtrSet<Value*, 8> contents;
601 ValueNumberedSet() { numbers.resize(1); }
602 ValueNumberedSet(const ValueNumberedSet& other) {
603 numbers = other.numbers;
604 contents = other.contents;
607 typedef SmallPtrSet<Value*, 8>::iterator iterator;
609 iterator begin() { return contents.begin(); }
610 iterator end() { return contents.end(); }
612 bool insert(Value* v) { return contents.insert(v); }
613 void insert(iterator I, iterator E) { contents.insert(I, E); }
614 void erase(Value* v) { contents.erase(v); }
615 unsigned count(Value* v) { return contents.count(v); }
616 size_t size() { return contents.size(); }
618 void set(unsigned i) {
619 if (i >= numbers.size())
625 void operator=(const ValueNumberedSet& other) {
626 contents = other.contents;
627 numbers = other.numbers;
630 void reset(unsigned i) {
631 if (i < numbers.size())
635 bool test(unsigned i) {
636 if (i >= numbers.size())
639 return numbers.test(i);
648 //===----------------------------------------------------------------------===//
650 //===----------------------------------------------------------------------===//
654 class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
655 bool runOnFunction(Function &F);
657 static char ID; // Pass identification, replacement for typeid
658 GVNPRE() : FunctionPass((intptr_t)&ID) { }
662 std::vector<Instruction*> createdExpressions;
664 DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
665 DenseMap<BasicBlock*, ValueNumberedSet> anticipatedIn;
666 DenseMap<BasicBlock*, ValueNumberedSet> generatedPhis;
668 // This transformation requires dominator postdominator info
669 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
670 AU.setPreservesCFG();
671 AU.addRequiredID(BreakCriticalEdgesID);
672 AU.addRequired<UnifyFunctionExitNodes>();
673 AU.addRequired<DominatorTree>();
677 // FIXME: eliminate or document these better
678 void dump(ValueNumberedSet& s) const ;
679 void clean(ValueNumberedSet& set) ;
680 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ;
681 Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) ;
682 void phi_translate_set(ValueNumberedSet& anticIn, BasicBlock* pred,
683 BasicBlock* succ, ValueNumberedSet& out) ;
685 void topo_sort(ValueNumberedSet& set,
686 std::vector<Value*>& vec) ;
691 void val_insert(ValueNumberedSet& s, Value* v) ;
692 void val_replace(ValueNumberedSet& s, Value* v) ;
693 bool dependsOnInvoke(Value* V) ;
694 void buildsets_availout(BasicBlock::iterator I,
695 ValueNumberedSet& currAvail,
696 ValueNumberedSet& currPhis,
697 ValueNumberedSet& currExps,
698 SmallPtrSet<Value*, 16>& currTemps) ;
699 bool buildsets_anticout(BasicBlock* BB,
700 ValueNumberedSet& anticOut,
701 SmallPtrSet<BasicBlock*, 8>& visited) ;
702 unsigned buildsets_anticin(BasicBlock* BB,
703 ValueNumberedSet& anticOut,
704 ValueNumberedSet& currExps,
705 SmallPtrSet<Value*, 16>& currTemps,
706 SmallPtrSet<BasicBlock*, 8>& visited) ;
707 void buildsets(Function& F) ;
709 void insertion_pre(Value* e, BasicBlock* BB,
710 std::map<BasicBlock*, Value*>& avail,
711 std::map<BasicBlock*,ValueNumberedSet>& new_set) ;
712 unsigned insertion_mergepoint(std::vector<Value*>& workList,
713 df_iterator<DomTreeNode*>& D,
714 std::map<BasicBlock*, ValueNumberedSet>& new_set) ;
715 bool insertion(Function& F) ;
723 // createGVNPREPass - The public interface to this file...
724 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
726 static RegisterPass<GVNPRE> X("gvnpre",
727 "Global Value Numbering/Partial Redundancy Elimination");
730 STATISTIC(NumInsertedVals, "Number of values inserted");
731 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
732 STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
734 /// find_leader - Given a set and a value number, return the first
735 /// element of the set with that value number, or 0 if no such element
737 Value* GVNPRE::find_leader(ValueNumberedSet& vals, uint32_t v) {
741 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
743 if (v == VN.lookup(*I))
746 assert(0 && "No leader found, but present bit is set?");
750 /// val_insert - Insert a value into a set only if there is not a value
751 /// with the same value number already in the set
752 void GVNPRE::val_insert(ValueNumberedSet& s, Value* v) {
753 uint32_t num = VN.lookup(v);
758 /// val_replace - Insert a value into a set, replacing any values already in
759 /// the set that have the same value number
760 void GVNPRE::val_replace(ValueNumberedSet& s, Value* v) {
761 uint32_t num = VN.lookup(v);
762 Value* leader = find_leader(s, num);
769 /// phi_translate - Given a value, its parent block, and a predecessor of its
770 /// parent, translate the value into legal for the predecessor block. This
771 /// means translating its operands (and recursively, their operands) through
772 /// any phi nodes in the parent into values available in the predecessor
773 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
778 if (CastInst* U = dyn_cast<CastInst>(V)) {
780 if (isa<Instruction>(U->getOperand(0)))
781 newOp1 = phi_translate(U->getOperand(0), pred, succ);
783 newOp1 = U->getOperand(0);
788 if (newOp1 != U->getOperand(0)) {
789 Instruction* newVal = 0;
790 if (CastInst* C = dyn_cast<CastInst>(U))
791 newVal = CastInst::create(C->getOpcode(),
792 newOp1, C->getType(),
793 C->getName()+".expr");
795 uint32_t v = VN.lookup_or_add(newVal);
797 Value* leader = find_leader(availableOut[pred], v);
799 createdExpressions.push_back(newVal);
809 } if (isa<BinaryOperator>(V) || isa<CmpInst>(V) ||
810 isa<ExtractElementInst>(V)) {
811 User* U = cast<User>(V);
814 if (isa<Instruction>(U->getOperand(0)))
815 newOp1 = phi_translate(U->getOperand(0), pred, succ);
817 newOp1 = U->getOperand(0);
823 if (isa<Instruction>(U->getOperand(1)))
824 newOp2 = phi_translate(U->getOperand(1), pred, succ);
826 newOp2 = U->getOperand(1);
831 if (newOp1 != U->getOperand(0) || newOp2 != U->getOperand(1)) {
832 Instruction* newVal = 0;
833 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
834 newVal = BinaryOperator::create(BO->getOpcode(),
836 BO->getName()+".expr");
837 else if (CmpInst* C = dyn_cast<CmpInst>(U))
838 newVal = CmpInst::create(C->getOpcode(),
841 C->getName()+".expr");
842 else if (ExtractElementInst* E = dyn_cast<ExtractElementInst>(U))
843 newVal = new ExtractElementInst(newOp1, newOp2, E->getName()+".expr");
845 uint32_t v = VN.lookup_or_add(newVal);
847 Value* leader = find_leader(availableOut[pred], v);
849 createdExpressions.push_back(newVal);
858 // Ternary Operations
859 } else if (isa<ShuffleVectorInst>(V) || isa<InsertElementInst>(V) ||
860 isa<SelectInst>(V)) {
861 User* U = cast<User>(V);
864 if (isa<Instruction>(U->getOperand(0)))
865 newOp1 = phi_translate(U->getOperand(0), pred, succ);
867 newOp1 = U->getOperand(0);
873 if (isa<Instruction>(U->getOperand(1)))
874 newOp2 = phi_translate(U->getOperand(1), pred, succ);
876 newOp2 = U->getOperand(1);
882 if (isa<Instruction>(U->getOperand(2)))
883 newOp3 = phi_translate(U->getOperand(2), pred, succ);
885 newOp3 = U->getOperand(2);
890 if (newOp1 != U->getOperand(0) ||
891 newOp2 != U->getOperand(1) ||
892 newOp3 != U->getOperand(2)) {
893 Instruction* newVal = 0;
894 if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
895 newVal = new ShuffleVectorInst(newOp1, newOp2, newOp3,
896 S->getName()+".expr");
897 else if (InsertElementInst* I = dyn_cast<InsertElementInst>(U))
898 newVal = new InsertElementInst(newOp1, newOp2, newOp3,
899 I->getName()+".expr");
900 else if (SelectInst* I = dyn_cast<SelectInst>(U))
901 newVal = new SelectInst(newOp1, newOp2, newOp3, I->getName()+".expr");
903 uint32_t v = VN.lookup_or_add(newVal);
905 Value* leader = find_leader(availableOut[pred], v);
907 createdExpressions.push_back(newVal);
917 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
919 if (isa<Instruction>(U->getPointerOperand()))
920 newOp1 = phi_translate(U->getPointerOperand(), pred, succ);
922 newOp1 = U->getPointerOperand();
927 bool changed_idx = false;
928 std::vector<Value*> newIdx;
929 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
931 if (isa<Instruction>(*I)) {
932 Value* newVal = phi_translate(*I, pred, succ);
933 newIdx.push_back(newVal);
937 newIdx.push_back(*I);
940 if (newOp1 != U->getPointerOperand() || changed_idx) {
941 Instruction* newVal = new GetElementPtrInst(newOp1,
942 &newIdx[0], newIdx.size(),
943 U->getName()+".expr");
945 uint32_t v = VN.lookup_or_add(newVal);
947 Value* leader = find_leader(availableOut[pred], v);
949 createdExpressions.push_back(newVal);
959 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
960 if (P->getParent() == succ)
961 return P->getIncomingValueForBlock(pred);
967 /// phi_translate_set - Perform phi translation on every element of a set
968 void GVNPRE::phi_translate_set(ValueNumberedSet& anticIn,
969 BasicBlock* pred, BasicBlock* succ,
970 ValueNumberedSet& out) {
971 for (ValueNumberedSet::iterator I = anticIn.begin(),
972 E = anticIn.end(); I != E; ++I) {
973 Value* V = phi_translate(*I, pred, succ);
974 if (V != 0 && !out.test(VN.lookup_or_add(V))) {
976 out.set(VN.lookup(V));
981 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of
982 /// whose inputs is an invoke instruction. If this is true, we cannot safely
983 /// PRE the instruction or anything that depends on it.
984 bool GVNPRE::dependsOnInvoke(Value* V) {
985 if (PHINode* p = dyn_cast<PHINode>(V)) {
986 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
987 if (isa<InvokeInst>(*I))
995 /// clean - Remove all non-opaque values from the set whose operands are not
996 /// themselves in the set, as well as all values that depend on invokes (see
998 void GVNPRE::clean(ValueNumberedSet& set) {
999 std::vector<Value*> worklist;
1000 worklist.reserve(set.size());
1001 topo_sort(set, worklist);
1003 for (unsigned i = 0; i < worklist.size(); ++i) {
1004 Value* v = worklist[i];
1007 if (CastInst* U = dyn_cast<CastInst>(v)) {
1008 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1009 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1011 lhsValid = !dependsOnInvoke(U->getOperand(0));
1015 set.reset(VN.lookup(U));
1018 // Handle binary ops
1019 } else if (isa<BinaryOperator>(v) || isa<CmpInst>(v) ||
1020 isa<ExtractElementInst>(v)) {
1021 User* U = cast<User>(v);
1023 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1024 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1026 lhsValid = !dependsOnInvoke(U->getOperand(0));
1028 bool rhsValid = !isa<Instruction>(U->getOperand(1));
1029 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
1031 rhsValid = !dependsOnInvoke(U->getOperand(1));
1033 if (!lhsValid || !rhsValid) {
1035 set.reset(VN.lookup(U));
1038 // Handle ternary ops
1039 } else if (isa<ShuffleVectorInst>(v) || isa<InsertElementInst>(v) ||
1040 isa<SelectInst>(v)) {
1041 User* U = cast<User>(v);
1043 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1044 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1046 lhsValid = !dependsOnInvoke(U->getOperand(0));
1048 bool rhsValid = !isa<Instruction>(U->getOperand(1));
1049 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
1051 rhsValid = !dependsOnInvoke(U->getOperand(1));
1053 bool thirdValid = !isa<Instruction>(U->getOperand(2));
1054 thirdValid |= set.test(VN.lookup(U->getOperand(2)));
1056 thirdValid = !dependsOnInvoke(U->getOperand(2));
1058 if (!lhsValid || !rhsValid || !thirdValid) {
1060 set.reset(VN.lookup(U));
1063 // Handle varargs ops
1064 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(v)) {
1065 bool ptrValid = !isa<Instruction>(U->getPointerOperand());
1066 ptrValid |= set.test(VN.lookup(U->getPointerOperand()));
1068 ptrValid = !dependsOnInvoke(U->getPointerOperand());
1070 bool varValid = true;
1071 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
1074 varValid &= !isa<Instruction>(*I) || set.test(VN.lookup(*I));
1075 varValid &= !dependsOnInvoke(*I);
1078 if (!ptrValid || !varValid) {
1080 set.reset(VN.lookup(U));
1086 /// topo_sort - Given a set of values, sort them by topological
1087 /// order into the provided vector.
1088 void GVNPRE::topo_sort(ValueNumberedSet& set, std::vector<Value*>& vec) {
1089 SmallPtrSet<Value*, 16> visited;
1090 std::vector<Value*> stack;
1091 for (ValueNumberedSet::iterator I = set.begin(), E = set.end();
1093 if (visited.count(*I) == 0)
1094 stack.push_back(*I);
1096 while (!stack.empty()) {
1097 Value* e = stack.back();
1100 if (CastInst* U = dyn_cast<CastInst>(e)) {
1101 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1103 if (l != 0 && isa<Instruction>(l) &&
1104 visited.count(l) == 0)
1112 // Handle binary ops
1113 } else if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1114 isa<ExtractElementInst>(e)) {
1115 User* U = cast<User>(e);
1116 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1117 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1119 if (l != 0 && isa<Instruction>(l) &&
1120 visited.count(l) == 0)
1122 else if (r != 0 && isa<Instruction>(r) &&
1123 visited.count(r) == 0)
1131 // Handle ternary ops
1132 } else if (isa<InsertElementInst>(e) || isa<ShuffleVectorInst>(e) ||
1133 isa<SelectInst>(e)) {
1134 User* U = cast<User>(e);
1135 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1136 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1137 Value* m = find_leader(set, VN.lookup(U->getOperand(2)));
1139 if (l != 0 && isa<Instruction>(l) &&
1140 visited.count(l) == 0)
1142 else if (r != 0 && isa<Instruction>(r) &&
1143 visited.count(r) == 0)
1145 else if (m != 0 && isa<Instruction>(m) &&
1146 visited.count(m) == 0)
1154 // Handle vararg ops
1155 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(e)) {
1156 Value* p = find_leader(set, VN.lookup(U->getPointerOperand()));
1158 if (p != 0 && isa<Instruction>(p) &&
1159 visited.count(p) == 0)
1162 bool push_va = false;
1163 for (GetElementPtrInst::op_iterator I = U->idx_begin(),
1164 E = U->idx_end(); I != E; ++I) {
1165 Value * v = find_leader(set, VN.lookup(*I));
1166 if (v != 0 && isa<Instruction>(v) && visited.count(v) == 0) {
1179 // Handle opaque ops
1191 /// dump - Dump a set of values to standard error
1192 void GVNPRE::dump(ValueNumberedSet& s) const {
1194 for (ValueNumberedSet::iterator I = s.begin(), E = s.end();
1196 DOUT << "" << VN.lookup(*I) << ": ";
1197 DEBUG((*I)->dump());
1202 /// elimination - Phase 3 of the main algorithm. Perform full redundancy
1203 /// elimination by walking the dominator tree and removing any instruction that
1204 /// is dominated by another instruction with the same value number.
1205 bool GVNPRE::elimination() {
1206 bool changed_function = false;
1208 std::vector<std::pair<Instruction*, Value*> > replace;
1209 std::vector<Instruction*> erase;
1211 DominatorTree& DT = getAnalysis<DominatorTree>();
1213 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1214 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1215 BasicBlock* BB = DI->getBlock();
1217 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1220 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI) ||
1221 isa<ShuffleVectorInst>(BI) || isa<InsertElementInst>(BI) ||
1222 isa<ExtractElementInst>(BI) || isa<SelectInst>(BI) ||
1223 isa<CastInst>(BI) || isa<GetElementPtrInst>(BI)) {
1225 if (availableOut[BB].test(VN.lookup(BI)) && !availableOut[BB].count(BI)) {
1226 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
1227 if (Instruction* Instr = dyn_cast<Instruction>(leader))
1228 if (Instr->getParent() != 0 && Instr != BI) {
1229 replace.push_back(std::make_pair(BI, leader));
1230 erase.push_back(BI);
1238 while (!replace.empty()) {
1239 std::pair<Instruction*, Value*> rep = replace.back();
1241 rep.first->replaceAllUsesWith(rep.second);
1242 changed_function = true;
1245 for (std::vector<Instruction*>::iterator I = erase.begin(), E = erase.end();
1247 (*I)->eraseFromParent();
1249 return changed_function;
1252 /// cleanup - Delete any extraneous values that were created to represent
1253 /// expressions without leaders.
1254 void GVNPRE::cleanup() {
1255 while (!createdExpressions.empty()) {
1256 Instruction* I = createdExpressions.back();
1257 createdExpressions.pop_back();
1263 /// buildsets_availout - When calculating availability, handle an instruction
1264 /// by inserting it into the appropriate sets
1265 void GVNPRE::buildsets_availout(BasicBlock::iterator I,
1266 ValueNumberedSet& currAvail,
1267 ValueNumberedSet& currPhis,
1268 ValueNumberedSet& currExps,
1269 SmallPtrSet<Value*, 16>& currTemps) {
1271 if (PHINode* p = dyn_cast<PHINode>(I)) {
1272 unsigned num = VN.lookup_or_add(p);
1278 } else if (CastInst* U = dyn_cast<CastInst>(I)) {
1279 Value* leftValue = U->getOperand(0);
1281 unsigned num = VN.lookup_or_add(U);
1283 if (isa<Instruction>(leftValue))
1284 if (!currExps.test(VN.lookup(leftValue))) {
1285 currExps.insert(leftValue);
1286 currExps.set(VN.lookup(leftValue));
1289 if (!currExps.test(num)) {
1294 // Handle binary ops
1295 } else if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
1296 isa<ExtractElementInst>(I)) {
1297 User* U = cast<User>(I);
1298 Value* leftValue = U->getOperand(0);
1299 Value* rightValue = U->getOperand(1);
1301 unsigned num = VN.lookup_or_add(U);
1303 if (isa<Instruction>(leftValue))
1304 if (!currExps.test(VN.lookup(leftValue))) {
1305 currExps.insert(leftValue);
1306 currExps.set(VN.lookup(leftValue));
1309 if (isa<Instruction>(rightValue))
1310 if (!currExps.test(VN.lookup(rightValue))) {
1311 currExps.insert(rightValue);
1312 currExps.set(VN.lookup(rightValue));
1315 if (!currExps.test(num)) {
1320 // Handle ternary ops
1321 } else if (isa<InsertElementInst>(I) || isa<ShuffleVectorInst>(I) ||
1322 isa<SelectInst>(I)) {
1323 User* U = cast<User>(I);
1324 Value* leftValue = U->getOperand(0);
1325 Value* rightValue = U->getOperand(1);
1326 Value* thirdValue = U->getOperand(2);
1328 VN.lookup_or_add(U);
1330 unsigned num = VN.lookup_or_add(U);
1332 if (isa<Instruction>(leftValue))
1333 if (!currExps.test(VN.lookup(leftValue))) {
1334 currExps.insert(leftValue);
1335 currExps.set(VN.lookup(leftValue));
1337 if (isa<Instruction>(rightValue))
1338 if (!currExps.test(VN.lookup(rightValue))) {
1339 currExps.insert(rightValue);
1340 currExps.set(VN.lookup(rightValue));
1342 if (isa<Instruction>(thirdValue))
1343 if (!currExps.test(VN.lookup(thirdValue))) {
1344 currExps.insert(thirdValue);
1345 currExps.set(VN.lookup(thirdValue));
1348 if (!currExps.test(num)) {
1353 // Handle vararg ops
1354 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(I)) {
1355 Value* ptrValue = U->getPointerOperand();
1357 VN.lookup_or_add(U);
1359 unsigned num = VN.lookup_or_add(U);
1361 if (isa<Instruction>(ptrValue))
1362 if (!currExps.test(VN.lookup(ptrValue))) {
1363 currExps.insert(ptrValue);
1364 currExps.set(VN.lookup(ptrValue));
1367 for (GetElementPtrInst::op_iterator OI = U->idx_begin(), OE = U->idx_end();
1369 if (isa<Instruction>(*OI) && !currExps.test(VN.lookup(*OI))) {
1370 currExps.insert(*OI);
1371 currExps.set(VN.lookup(*OI));
1374 if (!currExps.test(VN.lookup(U))) {
1379 // Handle opaque ops
1380 } else if (!I->isTerminator()){
1381 VN.lookup_or_add(I);
1383 currTemps.insert(I);
1386 if (!I->isTerminator())
1387 if (!currAvail.test(VN.lookup(I))) {
1388 currAvail.insert(I);
1389 currAvail.set(VN.lookup(I));
1393 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
1394 /// set as a function of the ANTIC_IN set of the block's predecessors
1395 bool GVNPRE::buildsets_anticout(BasicBlock* BB,
1396 ValueNumberedSet& anticOut,
1397 SmallPtrSet<BasicBlock*, 8>& visited) {
1398 if (BB->getTerminator()->getNumSuccessors() == 1) {
1399 if (BB->getTerminator()->getSuccessor(0) != BB &&
1400 visited.count(BB->getTerminator()->getSuccessor(0)) == 0) {
1404 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
1405 BB, BB->getTerminator()->getSuccessor(0), anticOut);
1407 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
1408 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
1409 for (ValueNumberedSet::iterator I = anticipatedIn[first].begin(),
1410 E = anticipatedIn[first].end(); I != E; ++I) {
1411 anticOut.insert(*I);
1412 anticOut.set(VN.lookup(*I));
1415 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
1416 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
1417 ValueNumberedSet& succAnticIn = anticipatedIn[currSucc];
1419 std::vector<Value*> temp;
1421 for (ValueNumberedSet::iterator I = anticOut.begin(),
1422 E = anticOut.end(); I != E; ++I)
1423 if (!succAnticIn.test(VN.lookup(*I)))
1426 for (std::vector<Value*>::iterator I = temp.begin(), E = temp.end();
1429 anticOut.reset(VN.lookup(*I));
1437 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
1438 /// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN
1439 /// sets populated in buildsets_availout
1440 unsigned GVNPRE::buildsets_anticin(BasicBlock* BB,
1441 ValueNumberedSet& anticOut,
1442 ValueNumberedSet& currExps,
1443 SmallPtrSet<Value*, 16>& currTemps,
1444 SmallPtrSet<BasicBlock*, 8>& visited) {
1445 ValueNumberedSet& anticIn = anticipatedIn[BB];
1446 unsigned old = anticIn.size();
1448 bool defer = buildsets_anticout(BB, anticOut, visited);
1454 for (ValueNumberedSet::iterator I = anticOut.begin(),
1455 E = anticOut.end(); I != E; ++I) {
1457 anticIn.set(VN.lookup(*I));
1459 for (ValueNumberedSet::iterator I = currExps.begin(),
1460 E = currExps.end(); I != E; ++I) {
1461 if (!anticIn.test(VN.lookup(*I))) {
1463 anticIn.set(VN.lookup(*I));
1467 for (SmallPtrSet<Value*, 16>::iterator I = currTemps.begin(),
1468 E = currTemps.end(); I != E; ++I) {
1470 anticIn.reset(VN.lookup(*I));
1476 if (old != anticIn.size())
1482 /// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT
1483 /// and the ANTIC_IN sets.
1484 void GVNPRE::buildsets(Function& F) {
1485 DenseMap<BasicBlock*, ValueNumberedSet> generatedExpressions;
1486 DenseMap<BasicBlock*, SmallPtrSet<Value*, 16> > generatedTemporaries;
1488 DominatorTree &DT = getAnalysis<DominatorTree>();
1490 // Phase 1, Part 1: calculate AVAIL_OUT
1492 // Top-down walk of the dominator tree
1493 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1494 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1496 // Get the sets to update for this block
1497 ValueNumberedSet& currExps = generatedExpressions[DI->getBlock()];
1498 ValueNumberedSet& currPhis = generatedPhis[DI->getBlock()];
1499 SmallPtrSet<Value*, 16>& currTemps = generatedTemporaries[DI->getBlock()];
1500 ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
1502 BasicBlock* BB = DI->getBlock();
1504 // A block inherits AVAIL_OUT from its dominator
1505 if (DI->getIDom() != 0)
1506 currAvail = availableOut[DI->getIDom()->getBlock()];
1508 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1510 buildsets_availout(BI, currAvail, currPhis, currExps,
1515 // Phase 1, Part 2: calculate ANTIC_IN
1517 SmallPtrSet<BasicBlock*, 8> visited;
1518 SmallPtrSet<BasicBlock*, 4> block_changed;
1519 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
1520 block_changed.insert(FI);
1522 bool changed = true;
1523 unsigned iterations = 0;
1527 ValueNumberedSet anticOut;
1529 // Postorder walk of the CFG
1530 for (po_iterator<BasicBlock*> BBI = po_begin(&F.getEntryBlock()),
1531 BBE = po_end(&F.getEntryBlock()); BBI != BBE; ++BBI) {
1532 BasicBlock* BB = *BBI;
1534 if (block_changed.count(BB) != 0) {
1535 unsigned ret = buildsets_anticin(BB, anticOut,generatedExpressions[BB],
1536 generatedTemporaries[BB], visited);
1545 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1547 block_changed.insert(*PI);
1550 block_changed.erase(BB);
1552 changed |= (ret == 2);
1561 /// insertion_pre - When a partial redundancy has been identified, eliminate it
1562 /// by inserting appropriate values into the predecessors and a phi node in
1564 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
1565 std::map<BasicBlock*, Value*>& avail,
1566 std::map<BasicBlock*, ValueNumberedSet>& new_sets) {
1567 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1568 Value* e2 = avail[*PI];
1569 if (!availableOut[*PI].test(VN.lookup(e2))) {
1570 User* U = cast<User>(e2);
1573 if (isa<BinaryOperator>(U->getOperand(0)) ||
1574 isa<CmpInst>(U->getOperand(0)) ||
1575 isa<ShuffleVectorInst>(U->getOperand(0)) ||
1576 isa<ExtractElementInst>(U->getOperand(0)) ||
1577 isa<InsertElementInst>(U->getOperand(0)) ||
1578 isa<SelectInst>(U->getOperand(0)) ||
1579 isa<CastInst>(U->getOperand(0)) ||
1580 isa<GetElementPtrInst>(U->getOperand(0)))
1581 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1583 s1 = U->getOperand(0);
1587 if (isa<BinaryOperator>(U) ||
1589 isa<ShuffleVectorInst>(U) ||
1590 isa<ExtractElementInst>(U) ||
1591 isa<InsertElementInst>(U) ||
1593 if (isa<BinaryOperator>(U->getOperand(1)) ||
1594 isa<CmpInst>(U->getOperand(1)) ||
1595 isa<ShuffleVectorInst>(U->getOperand(1)) ||
1596 isa<ExtractElementInst>(U->getOperand(1)) ||
1597 isa<InsertElementInst>(U->getOperand(1)) ||
1598 isa<SelectInst>(U->getOperand(1)) ||
1599 isa<CastInst>(U->getOperand(1)) ||
1600 isa<GetElementPtrInst>(U->getOperand(1))) {
1601 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1603 s2 = U->getOperand(1);
1606 // Ternary Operators
1608 if (isa<ShuffleVectorInst>(U) ||
1609 isa<InsertElementInst>(U) ||
1611 if (isa<BinaryOperator>(U->getOperand(2)) ||
1612 isa<CmpInst>(U->getOperand(2)) ||
1613 isa<ShuffleVectorInst>(U->getOperand(2)) ||
1614 isa<ExtractElementInst>(U->getOperand(2)) ||
1615 isa<InsertElementInst>(U->getOperand(2)) ||
1616 isa<SelectInst>(U->getOperand(2)) ||
1617 isa<CastInst>(U->getOperand(2)) ||
1618 isa<GetElementPtrInst>(U->getOperand(2))) {
1619 s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2)));
1621 s3 = U->getOperand(2);
1625 std::vector<Value*> sVarargs;
1626 if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U)) {
1627 for (GetElementPtrInst::op_iterator OI = G->idx_begin(),
1628 OE = G->idx_end(); OI != OE; ++OI) {
1629 if (isa<BinaryOperator>(*OI) ||
1630 isa<CmpInst>(*OI) ||
1631 isa<ShuffleVectorInst>(*OI) ||
1632 isa<ExtractElementInst>(*OI) ||
1633 isa<InsertElementInst>(*OI) ||
1634 isa<SelectInst>(*OI) ||
1635 isa<CastInst>(*OI) ||
1636 isa<GetElementPtrInst>(*OI)) {
1637 sVarargs.push_back(find_leader(availableOut[*PI],
1640 sVarargs.push_back(*OI);
1646 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1647 newVal = BinaryOperator::create(BO->getOpcode(), s1, s2,
1648 BO->getName()+".gvnpre",
1649 (*PI)->getTerminator());
1650 else if (CmpInst* C = dyn_cast<CmpInst>(U))
1651 newVal = CmpInst::create(C->getOpcode(), C->getPredicate(), s1, s2,
1652 C->getName()+".gvnpre",
1653 (*PI)->getTerminator());
1654 else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
1655 newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre",
1656 (*PI)->getTerminator());
1657 else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U))
1658 newVal = new InsertElementInst(s1, s2, s3, S->getName()+".gvnpre",
1659 (*PI)->getTerminator());
1660 else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U))
1661 newVal = new ExtractElementInst(s1, s2, S->getName()+".gvnpre",
1662 (*PI)->getTerminator());
1663 else if (SelectInst* S = dyn_cast<SelectInst>(U))
1664 newVal = new SelectInst(s1, s2, s3, S->getName()+".gvnpre",
1665 (*PI)->getTerminator());
1666 else if (CastInst* C = dyn_cast<CastInst>(U))
1667 newVal = CastInst::create(C->getOpcode(), s1, C->getType(),
1668 C->getName()+".gvnpre",
1669 (*PI)->getTerminator());
1670 else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U))
1671 newVal = new GetElementPtrInst(s1, &sVarargs[0], sVarargs.size(),
1672 G->getName()+".gvnpre",
1673 (*PI)->getTerminator());
1676 VN.add(newVal, VN.lookup(U));
1678 ValueNumberedSet& predAvail = availableOut[*PI];
1679 val_replace(predAvail, newVal);
1680 val_replace(new_sets[*PI], newVal);
1681 predAvail.set(VN.lookup(newVal));
1683 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1684 if (av != avail.end())
1686 avail.insert(std::make_pair(*PI, newVal));
1694 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1696 p = new PHINode(avail[*PI]->getType(), "gvnpre-join", BB->begin());
1698 p->addIncoming(avail[*PI], *PI);
1701 VN.add(p, VN.lookup(e));
1702 val_replace(availableOut[BB], p);
1703 availableOut[BB].set(VN.lookup(e));
1704 generatedPhis[BB].insert(p);
1705 generatedPhis[BB].set(VN.lookup(e));
1706 new_sets[BB].insert(p);
1707 new_sets[BB].set(VN.lookup(e));
1712 /// insertion_mergepoint - When walking the dom tree, check at each merge
1713 /// block for the possibility of a partial redundancy. If present, eliminate it
1714 unsigned GVNPRE::insertion_mergepoint(std::vector<Value*>& workList,
1715 df_iterator<DomTreeNode*>& D,
1716 std::map<BasicBlock*, ValueNumberedSet >& new_sets) {
1717 bool changed_function = false;
1718 bool new_stuff = false;
1720 BasicBlock* BB = D->getBlock();
1721 for (unsigned i = 0; i < workList.size(); ++i) {
1722 Value* e = workList[i];
1724 if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1725 isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) ||
1726 isa<ShuffleVectorInst>(e) || isa<SelectInst>(e) || isa<CastInst>(e) ||
1727 isa<GetElementPtrInst>(e)) {
1728 if (availableOut[D->getIDom()->getBlock()].test(VN.lookup(e)))
1731 std::map<BasicBlock*, Value*> avail;
1732 bool by_some = false;
1733 bool all_same = true;
1734 Value * first_s = 0;
1736 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1738 Value *e2 = phi_translate(e, *PI, BB);
1739 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1742 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1743 if (av != avail.end())
1745 avail.insert(std::make_pair(*PI, e2));
1748 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1749 if (av != avail.end())
1751 avail.insert(std::make_pair(*PI, e3));
1756 else if (first_s != e3)
1761 if (by_some && !all_same &&
1762 !generatedPhis[BB].test(VN.lookup(e))) {
1763 insertion_pre(e, BB, avail, new_sets);
1765 changed_function = true;
1771 unsigned retval = 0;
1772 if (changed_function)
1780 /// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for
1781 /// merge points. When one is found, check for a partial redundancy. If one is
1782 /// present, eliminate it. Repeat this walk until no changes are made.
1783 bool GVNPRE::insertion(Function& F) {
1784 bool changed_function = false;
1786 DominatorTree &DT = getAnalysis<DominatorTree>();
1788 std::map<BasicBlock*, ValueNumberedSet> new_sets;
1789 bool new_stuff = true;
1792 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1793 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1794 BasicBlock* BB = DI->getBlock();
1799 ValueNumberedSet& availOut = availableOut[BB];
1800 ValueNumberedSet& anticIn = anticipatedIn[BB];
1802 // Replace leaders with leaders inherited from dominator
1803 if (DI->getIDom() != 0) {
1804 ValueNumberedSet& dom_set = new_sets[DI->getIDom()->getBlock()];
1805 for (ValueNumberedSet::iterator I = dom_set.begin(),
1806 E = dom_set.end(); I != E; ++I) {
1807 val_replace(new_sets[BB], *I);
1808 val_replace(availOut, *I);
1812 // If there is more than one predecessor...
1813 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
1814 std::vector<Value*> workList;
1815 workList.reserve(anticIn.size());
1816 topo_sort(anticIn, workList);
1818 unsigned result = insertion_mergepoint(workList, DI, new_sets);
1820 changed_function = true;
1827 return changed_function;
1830 // GVNPRE::runOnFunction - This is the main transformation entry point for a
1833 bool GVNPRE::runOnFunction(Function &F) {
1834 // Clean out global sets from any previous functions
1836 createdExpressions.clear();
1837 availableOut.clear();
1838 anticipatedIn.clear();
1839 generatedPhis.clear();
1841 bool changed_function = false;
1843 // Phase 1: BuildSets
1844 // This phase calculates the AVAIL_OUT and ANTIC_IN sets
1848 // This phase inserts values to make partially redundant values
1850 changed_function |= insertion(F);
1852 // Phase 3: Eliminate
1853 // This phase performs trivial full redundancy elimination
1854 changed_function |= elimination();
1857 // This phase cleans up values that were created solely
1858 // as leaders for expressions
1861 return changed_function;