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"
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 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 DenseMapKeyInfo<Expression> {
159 static inline Expression getEmptyKey() { return Expression(Expression::EMPTY); }
160 static inline Expression getTombstoneKey() { return Expression(Expression::TOMBSTONE); }
162 static unsigned getHashValue(const Expression e) {
163 unsigned hash = e.opcode;
165 hash = e.firstVN + hash * 37;
166 hash = e.secondVN + hash * 37;
167 hash = e.thirdVN + hash * 37;
169 hash = (unsigned)((uintptr_t)e.type >> 4) ^
170 (unsigned)((uintptr_t)e.type >> 9) +
173 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), E = e.varargs.end();
175 hash = *I + hash * 37;
179 static bool isPod() { return true; }
183 //===----------------------------------------------------------------------===//
184 // ValueTable Internal Functions
185 //===----------------------------------------------------------------------===//
186 Expression::ExpressionOpcode
187 ValueTable::getOpcode(BinaryOperator* BO) {
188 switch(BO->getOpcode()) {
189 case Instruction::Add:
190 return Expression::ADD;
191 case Instruction::Sub:
192 return Expression::SUB;
193 case Instruction::Mul:
194 return Expression::MUL;
195 case Instruction::UDiv:
196 return Expression::UDIV;
197 case Instruction::SDiv:
198 return Expression::SDIV;
199 case Instruction::FDiv:
200 return Expression::FDIV;
201 case Instruction::URem:
202 return Expression::UREM;
203 case Instruction::SRem:
204 return Expression::SREM;
205 case Instruction::FRem:
206 return Expression::FREM;
207 case Instruction::Shl:
208 return Expression::SHL;
209 case Instruction::LShr:
210 return Expression::LSHR;
211 case Instruction::AShr:
212 return Expression::ASHR;
213 case Instruction::And:
214 return Expression::AND;
215 case Instruction::Or:
216 return Expression::OR;
217 case Instruction::Xor:
218 return Expression::XOR;
220 // THIS SHOULD NEVER HAPPEN
222 assert(0 && "Binary operator with unknown opcode?");
223 return Expression::ADD;
227 Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
228 if (C->getOpcode() == Instruction::ICmp) {
229 switch (C->getPredicate()) {
230 case ICmpInst::ICMP_EQ:
231 return Expression::ICMPEQ;
232 case ICmpInst::ICMP_NE:
233 return Expression::ICMPNE;
234 case ICmpInst::ICMP_UGT:
235 return Expression::ICMPUGT;
236 case ICmpInst::ICMP_UGE:
237 return Expression::ICMPUGE;
238 case ICmpInst::ICMP_ULT:
239 return Expression::ICMPULT;
240 case ICmpInst::ICMP_ULE:
241 return Expression::ICMPULE;
242 case ICmpInst::ICMP_SGT:
243 return Expression::ICMPSGT;
244 case ICmpInst::ICMP_SGE:
245 return Expression::ICMPSGE;
246 case ICmpInst::ICMP_SLT:
247 return Expression::ICMPSLT;
248 case ICmpInst::ICMP_SLE:
249 return Expression::ICMPSLE;
251 // THIS SHOULD NEVER HAPPEN
253 assert(0 && "Comparison with unknown predicate?");
254 return Expression::ICMPEQ;
257 switch (C->getPredicate()) {
258 case FCmpInst::FCMP_OEQ:
259 return Expression::FCMPOEQ;
260 case FCmpInst::FCMP_OGT:
261 return Expression::FCMPOGT;
262 case FCmpInst::FCMP_OGE:
263 return Expression::FCMPOGE;
264 case FCmpInst::FCMP_OLT:
265 return Expression::FCMPOLT;
266 case FCmpInst::FCMP_OLE:
267 return Expression::FCMPOLE;
268 case FCmpInst::FCMP_ONE:
269 return Expression::FCMPONE;
270 case FCmpInst::FCMP_ORD:
271 return Expression::FCMPORD;
272 case FCmpInst::FCMP_UNO:
273 return Expression::FCMPUNO;
274 case FCmpInst::FCMP_UEQ:
275 return Expression::FCMPUEQ;
276 case FCmpInst::FCMP_UGT:
277 return Expression::FCMPUGT;
278 case FCmpInst::FCMP_UGE:
279 return Expression::FCMPUGE;
280 case FCmpInst::FCMP_ULT:
281 return Expression::FCMPULT;
282 case FCmpInst::FCMP_ULE:
283 return Expression::FCMPULE;
284 case FCmpInst::FCMP_UNE:
285 return Expression::FCMPUNE;
287 // THIS SHOULD NEVER HAPPEN
289 assert(0 && "Comparison with unknown predicate?");
290 return Expression::FCMPOEQ;
295 Expression::ExpressionOpcode
296 ValueTable::getOpcode(CastInst* C) {
297 switch(C->getOpcode()) {
298 case Instruction::Trunc:
299 return Expression::TRUNC;
300 case Instruction::ZExt:
301 return Expression::ZEXT;
302 case Instruction::SExt:
303 return Expression::SEXT;
304 case Instruction::FPToUI:
305 return Expression::FPTOUI;
306 case Instruction::FPToSI:
307 return Expression::FPTOSI;
308 case Instruction::UIToFP:
309 return Expression::UITOFP;
310 case Instruction::SIToFP:
311 return Expression::SITOFP;
312 case Instruction::FPTrunc:
313 return Expression::FPTRUNC;
314 case Instruction::FPExt:
315 return Expression::FPEXT;
316 case Instruction::PtrToInt:
317 return Expression::PTRTOINT;
318 case Instruction::IntToPtr:
319 return Expression::INTTOPTR;
320 case Instruction::BitCast:
321 return Expression::BITCAST;
323 // THIS SHOULD NEVER HAPPEN
325 assert(0 && "Cast operator with unknown opcode?");
326 return Expression::BITCAST;
330 Expression ValueTable::create_expression(BinaryOperator* BO) {
333 e.firstVN = lookup_or_add(BO->getOperand(0));
334 e.secondVN = lookup_or_add(BO->getOperand(1));
336 e.type = BO->getType();
337 e.opcode = getOpcode(BO);
342 Expression ValueTable::create_expression(CmpInst* C) {
345 e.firstVN = lookup_or_add(C->getOperand(0));
346 e.secondVN = lookup_or_add(C->getOperand(1));
348 e.type = C->getType();
349 e.opcode = getOpcode(C);
354 Expression ValueTable::create_expression(CastInst* C) {
357 e.firstVN = lookup_or_add(C->getOperand(0));
360 e.type = C->getType();
361 e.opcode = getOpcode(C);
366 Expression ValueTable::create_expression(ShuffleVectorInst* S) {
369 e.firstVN = lookup_or_add(S->getOperand(0));
370 e.secondVN = lookup_or_add(S->getOperand(1));
371 e.thirdVN = lookup_or_add(S->getOperand(2));
372 e.type = S->getType();
373 e.opcode = Expression::SHUFFLE;
378 Expression ValueTable::create_expression(ExtractElementInst* E) {
381 e.firstVN = lookup_or_add(E->getOperand(0));
382 e.secondVN = lookup_or_add(E->getOperand(1));
384 e.type = E->getType();
385 e.opcode = Expression::EXTRACT;
390 Expression ValueTable::create_expression(InsertElementInst* I) {
393 e.firstVN = lookup_or_add(I->getOperand(0));
394 e.secondVN = lookup_or_add(I->getOperand(1));
395 e.thirdVN = lookup_or_add(I->getOperand(2));
396 e.type = I->getType();
397 e.opcode = Expression::INSERT;
402 Expression ValueTable::create_expression(SelectInst* I) {
405 e.firstVN = lookup_or_add(I->getCondition());
406 e.secondVN = lookup_or_add(I->getTrueValue());
407 e.thirdVN = lookup_or_add(I->getFalseValue());
408 e.type = I->getType();
409 e.opcode = Expression::SELECT;
414 Expression ValueTable::create_expression(GetElementPtrInst* G) {
417 e.firstVN = lookup_or_add(G->getPointerOperand());
420 e.type = G->getType();
421 e.opcode = Expression::GEP;
423 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
425 e.varargs.push_back(lookup_or_add(*I));
430 //===----------------------------------------------------------------------===//
431 // ValueTable External Functions
432 //===----------------------------------------------------------------------===//
434 /// lookup_or_add - Returns the value number for the specified value, assigning
435 /// it a new number if it did not have one before.
436 uint32_t ValueTable::lookup_or_add(Value* V) {
437 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
438 if (VI != valueNumbering.end())
442 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
443 Expression e = create_expression(BO);
445 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
446 if (EI != expressionNumbering.end()) {
447 valueNumbering.insert(std::make_pair(V, EI->second));
450 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
451 valueNumbering.insert(std::make_pair(V, nextValueNumber));
453 return nextValueNumber++;
455 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
456 Expression e = create_expression(C);
458 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
459 if (EI != expressionNumbering.end()) {
460 valueNumbering.insert(std::make_pair(V, EI->second));
463 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
464 valueNumbering.insert(std::make_pair(V, nextValueNumber));
466 return nextValueNumber++;
468 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
469 Expression e = create_expression(U);
471 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
472 if (EI != expressionNumbering.end()) {
473 valueNumbering.insert(std::make_pair(V, EI->second));
476 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
477 valueNumbering.insert(std::make_pair(V, nextValueNumber));
479 return nextValueNumber++;
481 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
482 Expression e = create_expression(U);
484 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
485 if (EI != expressionNumbering.end()) {
486 valueNumbering.insert(std::make_pair(V, EI->second));
489 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
490 valueNumbering.insert(std::make_pair(V, nextValueNumber));
492 return nextValueNumber++;
494 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
495 Expression e = create_expression(U);
497 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
498 if (EI != expressionNumbering.end()) {
499 valueNumbering.insert(std::make_pair(V, EI->second));
502 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
503 valueNumbering.insert(std::make_pair(V, nextValueNumber));
505 return nextValueNumber++;
507 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
508 Expression e = create_expression(U);
510 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
511 if (EI != expressionNumbering.end()) {
512 valueNumbering.insert(std::make_pair(V, EI->second));
515 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
516 valueNumbering.insert(std::make_pair(V, nextValueNumber));
518 return nextValueNumber++;
520 } else if (CastInst* U = dyn_cast<CastInst>(V)) {
521 Expression e = create_expression(U);
523 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
524 if (EI != expressionNumbering.end()) {
525 valueNumbering.insert(std::make_pair(V, EI->second));
528 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
529 valueNumbering.insert(std::make_pair(V, nextValueNumber));
531 return nextValueNumber++;
533 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
534 Expression e = create_expression(U);
536 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
537 if (EI != expressionNumbering.end()) {
538 valueNumbering.insert(std::make_pair(V, EI->second));
541 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
542 valueNumbering.insert(std::make_pair(V, nextValueNumber));
544 return nextValueNumber++;
547 valueNumbering.insert(std::make_pair(V, nextValueNumber));
548 return nextValueNumber++;
552 /// lookup - Returns the value number of the specified value. Fails if
553 /// the value has not yet been numbered.
554 uint32_t ValueTable::lookup(Value* V) const {
555 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
556 if (VI != valueNumbering.end())
559 assert(0 && "Value not numbered?");
564 /// add - Add the specified value with the given value number, removing
565 /// its old number, if any
566 void ValueTable::add(Value* V, uint32_t num) {
567 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
568 if (VI != valueNumbering.end())
569 valueNumbering.erase(VI);
570 valueNumbering.insert(std::make_pair(V, num));
573 /// clear - Remove all entries from the ValueTable
574 void ValueTable::clear() {
575 valueNumbering.clear();
576 expressionNumbering.clear();
580 /// erase - Remove a value from the value numbering
581 void ValueTable::erase(Value* V) {
582 valueNumbering.erase(V);
585 /// size - Return the number of assigned value numbers
586 unsigned ValueTable::size() {
587 // NOTE: zero is never assigned
588 return nextValueNumber;
591 //===----------------------------------------------------------------------===//
592 // ValueNumberedSet Class
593 //===----------------------------------------------------------------------===//
595 class ValueNumberedSet {
597 SmallPtrSet<Value*, 8> contents;
600 ValueNumberedSet() { numbers.resize(1); }
601 ValueNumberedSet(const ValueNumberedSet& other) {
602 numbers = other.numbers;
603 contents = other.contents;
606 typedef SmallPtrSet<Value*, 8>::iterator iterator;
608 iterator begin() { return contents.begin(); }
609 iterator end() { return contents.end(); }
611 bool insert(Value* v) { return contents.insert(v); }
612 void insert(iterator I, iterator E) { contents.insert(I, E); }
613 void erase(Value* v) { contents.erase(v); }
614 unsigned count(Value* v) { return contents.count(v); }
615 size_t size() { return contents.size(); }
617 void set(unsigned i) {
618 if (i >= numbers.size())
624 void operator=(const ValueNumberedSet& other) {
625 contents = other.contents;
626 numbers = other.numbers;
629 void reset(unsigned i) {
630 if (i < numbers.size())
634 bool test(unsigned i) {
635 if (i >= numbers.size())
638 return numbers.test(i);
647 //===----------------------------------------------------------------------===//
649 //===----------------------------------------------------------------------===//
653 class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
654 bool runOnFunction(Function &F);
656 static char ID; // Pass identification, replacement for typeid
657 GVNPRE() : FunctionPass((intptr_t)&ID) { }
661 SmallVector<Instruction*, 8> createdExpressions;
663 DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
664 DenseMap<BasicBlock*, ValueNumberedSet> anticipatedIn;
665 DenseMap<BasicBlock*, ValueNumberedSet> generatedPhis;
667 // This transformation requires dominator postdominator info
668 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
669 AU.setPreservesCFG();
670 AU.addRequiredID(BreakCriticalEdgesID);
671 AU.addRequired<UnifyFunctionExitNodes>();
672 AU.addRequired<DominatorTree>();
676 // FIXME: eliminate or document these better
677 void dump(ValueNumberedSet& s) const ;
678 void clean(ValueNumberedSet& set) ;
679 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ;
680 Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) ;
681 void phi_translate_set(ValueNumberedSet& anticIn, BasicBlock* pred,
682 BasicBlock* succ, ValueNumberedSet& out) ;
684 void topo_sort(ValueNumberedSet& set,
685 SmallVector<Value*, 8>& vec) ;
690 void val_insert(ValueNumberedSet& s, Value* v) ;
691 void val_replace(ValueNumberedSet& s, Value* v) ;
692 bool dependsOnInvoke(Value* V) ;
693 void buildsets_availout(BasicBlock::iterator I,
694 ValueNumberedSet& currAvail,
695 ValueNumberedSet& currPhis,
696 ValueNumberedSet& currExps,
697 SmallPtrSet<Value*, 16>& currTemps);
698 bool buildsets_anticout(BasicBlock* BB,
699 ValueNumberedSet& anticOut,
700 SmallPtrSet<BasicBlock*, 8>& visited);
701 unsigned buildsets_anticin(BasicBlock* BB,
702 ValueNumberedSet& anticOut,
703 ValueNumberedSet& currExps,
704 SmallPtrSet<Value*, 16>& currTemps,
705 SmallPtrSet<BasicBlock*, 8>& visited);
706 void buildsets(Function& F) ;
708 void insertion_pre(Value* e, BasicBlock* BB,
709 DenseMap<BasicBlock*, Value*>& avail,
710 std::map<BasicBlock*,ValueNumberedSet>& new_set);
711 unsigned insertion_mergepoint(SmallVector<Value*, 8>& workList,
712 df_iterator<DomTreeNode*>& D,
713 std::map<BasicBlock*, ValueNumberedSet>& new_set);
714 bool insertion(Function& F) ;
722 // createGVNPREPass - The public interface to this file...
723 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
725 static RegisterPass<GVNPRE> X("gvnpre",
726 "Global Value Numbering/Partial Redundancy Elimination");
729 STATISTIC(NumInsertedVals, "Number of values inserted");
730 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
731 STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
733 /// find_leader - Given a set and a value number, return the first
734 /// element of the set with that value number, or 0 if no such element
736 Value* GVNPRE::find_leader(ValueNumberedSet& vals, uint32_t v) {
740 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
742 if (v == VN.lookup(*I))
745 assert(0 && "No leader found, but present bit is set?");
749 /// val_insert - Insert a value into a set only if there is not a value
750 /// with the same value number already in the set
751 void GVNPRE::val_insert(ValueNumberedSet& s, Value* v) {
752 uint32_t num = VN.lookup(v);
757 /// val_replace - Insert a value into a set, replacing any values already in
758 /// the set that have the same value number
759 void GVNPRE::val_replace(ValueNumberedSet& s, Value* v) {
760 if (s.count(v)) return;
762 uint32_t num = VN.lookup(v);
763 Value* leader = find_leader(s, num);
770 /// phi_translate - Given a value, its parent block, and a predecessor of its
771 /// parent, translate the value into legal for the predecessor block. This
772 /// means translating its operands (and recursively, their operands) through
773 /// any phi nodes in the parent into values available in the predecessor
774 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
779 if (CastInst* U = dyn_cast<CastInst>(V)) {
781 if (isa<Instruction>(U->getOperand(0)))
782 newOp1 = phi_translate(U->getOperand(0), pred, succ);
784 newOp1 = U->getOperand(0);
789 if (newOp1 != U->getOperand(0)) {
790 Instruction* newVal = 0;
791 if (CastInst* C = dyn_cast<CastInst>(U))
792 newVal = CastInst::create(C->getOpcode(),
793 newOp1, C->getType(),
794 C->getName()+".expr");
796 uint32_t v = VN.lookup_or_add(newVal);
798 Value* leader = find_leader(availableOut[pred], v);
800 createdExpressions.push_back(newVal);
810 } if (isa<BinaryOperator>(V) || isa<CmpInst>(V) ||
811 isa<ExtractElementInst>(V)) {
812 User* U = cast<User>(V);
815 if (isa<Instruction>(U->getOperand(0)))
816 newOp1 = phi_translate(U->getOperand(0), pred, succ);
818 newOp1 = U->getOperand(0);
824 if (isa<Instruction>(U->getOperand(1)))
825 newOp2 = phi_translate(U->getOperand(1), pred, succ);
827 newOp2 = U->getOperand(1);
832 if (newOp1 != U->getOperand(0) || newOp2 != U->getOperand(1)) {
833 Instruction* newVal = 0;
834 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
835 newVal = BinaryOperator::create(BO->getOpcode(),
837 BO->getName()+".expr");
838 else if (CmpInst* C = dyn_cast<CmpInst>(U))
839 newVal = CmpInst::create(C->getOpcode(),
842 C->getName()+".expr");
843 else if (ExtractElementInst* E = dyn_cast<ExtractElementInst>(U))
844 newVal = new ExtractElementInst(newOp1, newOp2, E->getName()+".expr");
846 uint32_t v = VN.lookup_or_add(newVal);
848 Value* leader = find_leader(availableOut[pred], v);
850 createdExpressions.push_back(newVal);
859 // Ternary Operations
860 } else if (isa<ShuffleVectorInst>(V) || isa<InsertElementInst>(V) ||
861 isa<SelectInst>(V)) {
862 User* U = cast<User>(V);
865 if (isa<Instruction>(U->getOperand(0)))
866 newOp1 = phi_translate(U->getOperand(0), pred, succ);
868 newOp1 = U->getOperand(0);
874 if (isa<Instruction>(U->getOperand(1)))
875 newOp2 = phi_translate(U->getOperand(1), pred, succ);
877 newOp2 = U->getOperand(1);
883 if (isa<Instruction>(U->getOperand(2)))
884 newOp3 = phi_translate(U->getOperand(2), pred, succ);
886 newOp3 = U->getOperand(2);
891 if (newOp1 != U->getOperand(0) ||
892 newOp2 != U->getOperand(1) ||
893 newOp3 != U->getOperand(2)) {
894 Instruction* newVal = 0;
895 if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
896 newVal = new ShuffleVectorInst(newOp1, newOp2, newOp3,
897 S->getName()+".expr");
898 else if (InsertElementInst* I = dyn_cast<InsertElementInst>(U))
899 newVal = new InsertElementInst(newOp1, newOp2, newOp3,
900 I->getName()+".expr");
901 else if (SelectInst* I = dyn_cast<SelectInst>(U))
902 newVal = new SelectInst(newOp1, newOp2, newOp3, I->getName()+".expr");
904 uint32_t v = VN.lookup_or_add(newVal);
906 Value* leader = find_leader(availableOut[pred], v);
908 createdExpressions.push_back(newVal);
918 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
920 if (isa<Instruction>(U->getPointerOperand()))
921 newOp1 = phi_translate(U->getPointerOperand(), pred, succ);
923 newOp1 = U->getPointerOperand();
928 bool changed_idx = false;
929 SmallVector<Value*, 4> newIdx;
930 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
932 if (isa<Instruction>(*I)) {
933 Value* newVal = phi_translate(*I, pred, succ);
934 newIdx.push_back(newVal);
938 newIdx.push_back(*I);
941 if (newOp1 != U->getPointerOperand() || changed_idx) {
942 Instruction* newVal = new GetElementPtrInst(newOp1,
943 &newIdx[0], newIdx.size(),
944 U->getName()+".expr");
946 uint32_t v = VN.lookup_or_add(newVal);
948 Value* leader = find_leader(availableOut[pred], v);
950 createdExpressions.push_back(newVal);
960 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
961 if (P->getParent() == succ)
962 return P->getIncomingValueForBlock(pred);
968 /// phi_translate_set - Perform phi translation on every element of a set
969 void GVNPRE::phi_translate_set(ValueNumberedSet& anticIn,
970 BasicBlock* pred, BasicBlock* succ,
971 ValueNumberedSet& out) {
972 for (ValueNumberedSet::iterator I = anticIn.begin(),
973 E = anticIn.end(); I != E; ++I) {
974 Value* V = phi_translate(*I, pred, succ);
975 if (V != 0 && !out.test(VN.lookup_or_add(V))) {
977 out.set(VN.lookup(V));
982 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of
983 /// whose inputs is an invoke instruction. If this is true, we cannot safely
984 /// PRE the instruction or anything that depends on it.
985 bool GVNPRE::dependsOnInvoke(Value* V) {
986 if (PHINode* p = dyn_cast<PHINode>(V)) {
987 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
988 if (isa<InvokeInst>(*I))
996 /// clean - Remove all non-opaque values from the set whose operands are not
997 /// themselves in the set, as well as all values that depend on invokes (see
999 void GVNPRE::clean(ValueNumberedSet& set) {
1000 SmallVector<Value*, 8> worklist;
1001 worklist.reserve(set.size());
1002 topo_sort(set, worklist);
1004 for (unsigned i = 0; i < worklist.size(); ++i) {
1005 Value* v = worklist[i];
1008 if (CastInst* U = dyn_cast<CastInst>(v)) {
1009 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1010 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1012 lhsValid = !dependsOnInvoke(U->getOperand(0));
1016 set.reset(VN.lookup(U));
1019 // Handle binary ops
1020 } else if (isa<BinaryOperator>(v) || isa<CmpInst>(v) ||
1021 isa<ExtractElementInst>(v)) {
1022 User* U = cast<User>(v);
1024 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1025 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1027 lhsValid = !dependsOnInvoke(U->getOperand(0));
1029 bool rhsValid = !isa<Instruction>(U->getOperand(1));
1030 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
1032 rhsValid = !dependsOnInvoke(U->getOperand(1));
1034 if (!lhsValid || !rhsValid) {
1036 set.reset(VN.lookup(U));
1039 // Handle ternary ops
1040 } else if (isa<ShuffleVectorInst>(v) || isa<InsertElementInst>(v) ||
1041 isa<SelectInst>(v)) {
1042 User* U = cast<User>(v);
1044 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1045 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1047 lhsValid = !dependsOnInvoke(U->getOperand(0));
1049 bool rhsValid = !isa<Instruction>(U->getOperand(1));
1050 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
1052 rhsValid = !dependsOnInvoke(U->getOperand(1));
1054 bool thirdValid = !isa<Instruction>(U->getOperand(2));
1055 thirdValid |= set.test(VN.lookup(U->getOperand(2)));
1057 thirdValid = !dependsOnInvoke(U->getOperand(2));
1059 if (!lhsValid || !rhsValid || !thirdValid) {
1061 set.reset(VN.lookup(U));
1064 // Handle varargs ops
1065 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(v)) {
1066 bool ptrValid = !isa<Instruction>(U->getPointerOperand());
1067 ptrValid |= set.test(VN.lookup(U->getPointerOperand()));
1069 ptrValid = !dependsOnInvoke(U->getPointerOperand());
1071 bool varValid = true;
1072 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
1075 varValid &= !isa<Instruction>(*I) || set.test(VN.lookup(*I));
1076 varValid &= !dependsOnInvoke(*I);
1079 if (!ptrValid || !varValid) {
1081 set.reset(VN.lookup(U));
1087 /// topo_sort - Given a set of values, sort them by topological
1088 /// order into the provided vector.
1089 void GVNPRE::topo_sort(ValueNumberedSet& set, SmallVector<Value*, 8>& vec) {
1090 SmallPtrSet<Value*, 16> visited;
1091 SmallVector<Value*, 8> stack;
1092 for (ValueNumberedSet::iterator I = set.begin(), E = set.end();
1094 if (visited.count(*I) == 0)
1095 stack.push_back(*I);
1097 while (!stack.empty()) {
1098 Value* e = stack.back();
1101 if (CastInst* U = dyn_cast<CastInst>(e)) {
1102 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1104 if (l != 0 && isa<Instruction>(l) &&
1105 visited.count(l) == 0)
1113 // Handle binary ops
1114 } else if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1115 isa<ExtractElementInst>(e)) {
1116 User* U = cast<User>(e);
1117 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1118 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1120 if (l != 0 && isa<Instruction>(l) &&
1121 visited.count(l) == 0)
1123 else if (r != 0 && isa<Instruction>(r) &&
1124 visited.count(r) == 0)
1132 // Handle ternary ops
1133 } else if (isa<InsertElementInst>(e) || isa<ShuffleVectorInst>(e) ||
1134 isa<SelectInst>(e)) {
1135 User* U = cast<User>(e);
1136 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1137 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1138 Value* m = find_leader(set, VN.lookup(U->getOperand(2)));
1140 if (l != 0 && isa<Instruction>(l) &&
1141 visited.count(l) == 0)
1143 else if (r != 0 && isa<Instruction>(r) &&
1144 visited.count(r) == 0)
1146 else if (m != 0 && isa<Instruction>(m) &&
1147 visited.count(m) == 0)
1155 // Handle vararg ops
1156 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(e)) {
1157 Value* p = find_leader(set, VN.lookup(U->getPointerOperand()));
1159 if (p != 0 && isa<Instruction>(p) &&
1160 visited.count(p) == 0)
1163 bool push_va = false;
1164 for (GetElementPtrInst::op_iterator I = U->idx_begin(),
1165 E = U->idx_end(); I != E; ++I) {
1166 Value * v = find_leader(set, VN.lookup(*I));
1167 if (v != 0 && isa<Instruction>(v) && visited.count(v) == 0) {
1180 // Handle opaque ops
1192 /// dump - Dump a set of values to standard error
1193 void GVNPRE::dump(ValueNumberedSet& s) const {
1195 for (ValueNumberedSet::iterator I = s.begin(), E = s.end();
1197 DOUT << "" << VN.lookup(*I) << ": ";
1198 DEBUG((*I)->dump());
1203 /// elimination - Phase 3 of the main algorithm. Perform full redundancy
1204 /// elimination by walking the dominator tree and removing any instruction that
1205 /// is dominated by another instruction with the same value number.
1206 bool GVNPRE::elimination() {
1207 bool changed_function = false;
1209 SmallVector<std::pair<Instruction*, Value*>, 8> replace;
1210 SmallVector<Instruction*, 8> erase;
1212 DominatorTree& DT = getAnalysis<DominatorTree>();
1214 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1215 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1216 BasicBlock* BB = DI->getBlock();
1218 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1221 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI) ||
1222 isa<ShuffleVectorInst>(BI) || isa<InsertElementInst>(BI) ||
1223 isa<ExtractElementInst>(BI) || isa<SelectInst>(BI) ||
1224 isa<CastInst>(BI) || isa<GetElementPtrInst>(BI)) {
1226 if (availableOut[BB].test(VN.lookup(BI)) && !availableOut[BB].count(BI)) {
1227 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
1228 if (Instruction* Instr = dyn_cast<Instruction>(leader))
1229 if (Instr->getParent() != 0 && Instr != BI) {
1230 replace.push_back(std::make_pair(BI, leader));
1231 erase.push_back(BI);
1239 while (!replace.empty()) {
1240 std::pair<Instruction*, Value*> rep = replace.back();
1242 rep.first->replaceAllUsesWith(rep.second);
1243 changed_function = true;
1246 for (SmallVector<Instruction*, 8>::iterator I = erase.begin(), E = erase.end();
1248 (*I)->eraseFromParent();
1250 return changed_function;
1253 /// cleanup - Delete any extraneous values that were created to represent
1254 /// expressions without leaders.
1255 void GVNPRE::cleanup() {
1256 while (!createdExpressions.empty()) {
1257 Instruction* I = createdExpressions.back();
1258 createdExpressions.pop_back();
1264 /// buildsets_availout - When calculating availability, handle an instruction
1265 /// by inserting it into the appropriate sets
1266 void GVNPRE::buildsets_availout(BasicBlock::iterator I,
1267 ValueNumberedSet& currAvail,
1268 ValueNumberedSet& currPhis,
1269 ValueNumberedSet& currExps,
1270 SmallPtrSet<Value*, 16>& currTemps) {
1272 if (PHINode* p = dyn_cast<PHINode>(I)) {
1273 unsigned num = VN.lookup_or_add(p);
1279 } else if (CastInst* U = dyn_cast<CastInst>(I)) {
1280 Value* leftValue = U->getOperand(0);
1282 unsigned num = VN.lookup_or_add(U);
1284 if (isa<Instruction>(leftValue))
1285 if (!currExps.test(VN.lookup(leftValue))) {
1286 currExps.insert(leftValue);
1287 currExps.set(VN.lookup(leftValue));
1290 if (!currExps.test(num)) {
1295 // Handle binary ops
1296 } else if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
1297 isa<ExtractElementInst>(I)) {
1298 User* U = cast<User>(I);
1299 Value* leftValue = U->getOperand(0);
1300 Value* rightValue = U->getOperand(1);
1302 unsigned num = VN.lookup_or_add(U);
1304 if (isa<Instruction>(leftValue))
1305 if (!currExps.test(VN.lookup(leftValue))) {
1306 currExps.insert(leftValue);
1307 currExps.set(VN.lookup(leftValue));
1310 if (isa<Instruction>(rightValue))
1311 if (!currExps.test(VN.lookup(rightValue))) {
1312 currExps.insert(rightValue);
1313 currExps.set(VN.lookup(rightValue));
1316 if (!currExps.test(num)) {
1321 // Handle ternary ops
1322 } else if (isa<InsertElementInst>(I) || isa<ShuffleVectorInst>(I) ||
1323 isa<SelectInst>(I)) {
1324 User* U = cast<User>(I);
1325 Value* leftValue = U->getOperand(0);
1326 Value* rightValue = U->getOperand(1);
1327 Value* thirdValue = U->getOperand(2);
1329 VN.lookup_or_add(U);
1331 unsigned num = VN.lookup_or_add(U);
1333 if (isa<Instruction>(leftValue))
1334 if (!currExps.test(VN.lookup(leftValue))) {
1335 currExps.insert(leftValue);
1336 currExps.set(VN.lookup(leftValue));
1338 if (isa<Instruction>(rightValue))
1339 if (!currExps.test(VN.lookup(rightValue))) {
1340 currExps.insert(rightValue);
1341 currExps.set(VN.lookup(rightValue));
1343 if (isa<Instruction>(thirdValue))
1344 if (!currExps.test(VN.lookup(thirdValue))) {
1345 currExps.insert(thirdValue);
1346 currExps.set(VN.lookup(thirdValue));
1349 if (!currExps.test(num)) {
1354 // Handle vararg ops
1355 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(I)) {
1356 Value* ptrValue = U->getPointerOperand();
1358 VN.lookup_or_add(U);
1360 unsigned num = VN.lookup_or_add(U);
1362 if (isa<Instruction>(ptrValue))
1363 if (!currExps.test(VN.lookup(ptrValue))) {
1364 currExps.insert(ptrValue);
1365 currExps.set(VN.lookup(ptrValue));
1368 for (GetElementPtrInst::op_iterator OI = U->idx_begin(), OE = U->idx_end();
1370 if (isa<Instruction>(*OI) && !currExps.test(VN.lookup(*OI))) {
1371 currExps.insert(*OI);
1372 currExps.set(VN.lookup(*OI));
1375 if (!currExps.test(VN.lookup(U))) {
1380 // Handle opaque ops
1381 } else if (!I->isTerminator()){
1382 VN.lookup_or_add(I);
1384 currTemps.insert(I);
1387 if (!I->isTerminator())
1388 if (!currAvail.test(VN.lookup(I))) {
1389 currAvail.insert(I);
1390 currAvail.set(VN.lookup(I));
1394 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
1395 /// set as a function of the ANTIC_IN set of the block's predecessors
1396 bool GVNPRE::buildsets_anticout(BasicBlock* BB,
1397 ValueNumberedSet& anticOut,
1398 SmallPtrSet<BasicBlock*, 8>& visited) {
1399 if (BB->getTerminator()->getNumSuccessors() == 1) {
1400 if (BB->getTerminator()->getSuccessor(0) != BB &&
1401 visited.count(BB->getTerminator()->getSuccessor(0)) == 0) {
1405 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
1406 BB, BB->getTerminator()->getSuccessor(0), anticOut);
1408 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
1409 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
1410 for (ValueNumberedSet::iterator I = anticipatedIn[first].begin(),
1411 E = anticipatedIn[first].end(); I != E; ++I) {
1412 anticOut.insert(*I);
1413 anticOut.set(VN.lookup(*I));
1416 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
1417 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
1418 ValueNumberedSet& succAnticIn = anticipatedIn[currSucc];
1420 SmallVector<Value*, 16> temp;
1422 for (ValueNumberedSet::iterator I = anticOut.begin(),
1423 E = anticOut.end(); I != E; ++I)
1424 if (!succAnticIn.test(VN.lookup(*I)))
1427 for (SmallVector<Value*, 16>::iterator I = temp.begin(), E = temp.end();
1430 anticOut.reset(VN.lookup(*I));
1438 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
1439 /// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN
1440 /// sets populated in buildsets_availout
1441 unsigned GVNPRE::buildsets_anticin(BasicBlock* BB,
1442 ValueNumberedSet& anticOut,
1443 ValueNumberedSet& currExps,
1444 SmallPtrSet<Value*, 16>& currTemps,
1445 SmallPtrSet<BasicBlock*, 8>& visited) {
1446 ValueNumberedSet& anticIn = anticipatedIn[BB];
1447 unsigned old = anticIn.size();
1449 bool defer = buildsets_anticout(BB, anticOut, visited);
1455 for (ValueNumberedSet::iterator I = anticOut.begin(),
1456 E = anticOut.end(); I != E; ++I) {
1458 anticIn.set(VN.lookup(*I));
1460 for (ValueNumberedSet::iterator I = currExps.begin(),
1461 E = currExps.end(); I != E; ++I) {
1462 if (!anticIn.test(VN.lookup(*I))) {
1464 anticIn.set(VN.lookup(*I));
1468 for (SmallPtrSet<Value*, 16>::iterator I = currTemps.begin(),
1469 E = currTemps.end(); I != E; ++I) {
1471 anticIn.reset(VN.lookup(*I));
1477 if (old != anticIn.size())
1483 /// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT
1484 /// and the ANTIC_IN sets.
1485 void GVNPRE::buildsets(Function& F) {
1486 DenseMap<BasicBlock*, ValueNumberedSet> generatedExpressions;
1487 DenseMap<BasicBlock*, SmallPtrSet<Value*, 16> > generatedTemporaries;
1489 DominatorTree &DT = getAnalysis<DominatorTree>();
1491 // Phase 1, Part 1: calculate AVAIL_OUT
1493 // Top-down walk of the dominator tree
1494 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1495 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1497 // Get the sets to update for this block
1498 ValueNumberedSet& currExps = generatedExpressions[DI->getBlock()];
1499 ValueNumberedSet& currPhis = generatedPhis[DI->getBlock()];
1500 SmallPtrSet<Value*, 16>& currTemps = generatedTemporaries[DI->getBlock()];
1501 ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
1503 BasicBlock* BB = DI->getBlock();
1505 // A block inherits AVAIL_OUT from its dominator
1506 if (DI->getIDom() != 0)
1507 currAvail = availableOut[DI->getIDom()->getBlock()];
1509 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1511 buildsets_availout(BI, currAvail, currPhis, currExps,
1516 // Phase 1, Part 2: calculate ANTIC_IN
1518 SmallPtrSet<BasicBlock*, 8> visited;
1519 SmallPtrSet<BasicBlock*, 4> block_changed;
1520 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
1521 block_changed.insert(FI);
1523 bool changed = true;
1524 unsigned iterations = 0;
1528 ValueNumberedSet anticOut;
1530 // Postorder walk of the CFG
1531 for (po_iterator<BasicBlock*> BBI = po_begin(&F.getEntryBlock()),
1532 BBE = po_end(&F.getEntryBlock()); BBI != BBE; ++BBI) {
1533 BasicBlock* BB = *BBI;
1535 if (block_changed.count(BB) != 0) {
1536 unsigned ret = buildsets_anticin(BB, anticOut,generatedExpressions[BB],
1537 generatedTemporaries[BB], visited);
1546 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1548 block_changed.insert(*PI);
1551 block_changed.erase(BB);
1553 changed |= (ret == 2);
1562 /// insertion_pre - When a partial redundancy has been identified, eliminate it
1563 /// by inserting appropriate values into the predecessors and a phi node in
1565 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
1566 DenseMap<BasicBlock*, Value*>& avail,
1567 std::map<BasicBlock*, ValueNumberedSet>& new_sets) {
1568 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1569 Value* e2 = avail[*PI];
1570 if (!availableOut[*PI].test(VN.lookup(e2))) {
1571 User* U = cast<User>(e2);
1574 if (isa<BinaryOperator>(U->getOperand(0)) ||
1575 isa<CmpInst>(U->getOperand(0)) ||
1576 isa<ShuffleVectorInst>(U->getOperand(0)) ||
1577 isa<ExtractElementInst>(U->getOperand(0)) ||
1578 isa<InsertElementInst>(U->getOperand(0)) ||
1579 isa<SelectInst>(U->getOperand(0)) ||
1580 isa<CastInst>(U->getOperand(0)) ||
1581 isa<GetElementPtrInst>(U->getOperand(0)))
1582 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1584 s1 = U->getOperand(0);
1588 if (isa<BinaryOperator>(U) ||
1590 isa<ShuffleVectorInst>(U) ||
1591 isa<ExtractElementInst>(U) ||
1592 isa<InsertElementInst>(U) ||
1594 if (isa<BinaryOperator>(U->getOperand(1)) ||
1595 isa<CmpInst>(U->getOperand(1)) ||
1596 isa<ShuffleVectorInst>(U->getOperand(1)) ||
1597 isa<ExtractElementInst>(U->getOperand(1)) ||
1598 isa<InsertElementInst>(U->getOperand(1)) ||
1599 isa<SelectInst>(U->getOperand(1)) ||
1600 isa<CastInst>(U->getOperand(1)) ||
1601 isa<GetElementPtrInst>(U->getOperand(1))) {
1602 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1604 s2 = U->getOperand(1);
1607 // Ternary Operators
1609 if (isa<ShuffleVectorInst>(U) ||
1610 isa<InsertElementInst>(U) ||
1612 if (isa<BinaryOperator>(U->getOperand(2)) ||
1613 isa<CmpInst>(U->getOperand(2)) ||
1614 isa<ShuffleVectorInst>(U->getOperand(2)) ||
1615 isa<ExtractElementInst>(U->getOperand(2)) ||
1616 isa<InsertElementInst>(U->getOperand(2)) ||
1617 isa<SelectInst>(U->getOperand(2)) ||
1618 isa<CastInst>(U->getOperand(2)) ||
1619 isa<GetElementPtrInst>(U->getOperand(2))) {
1620 s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2)));
1622 s3 = U->getOperand(2);
1626 SmallVector<Value*, 4> sVarargs;
1627 if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U)) {
1628 for (GetElementPtrInst::op_iterator OI = G->idx_begin(),
1629 OE = G->idx_end(); OI != OE; ++OI) {
1630 if (isa<BinaryOperator>(*OI) ||
1631 isa<CmpInst>(*OI) ||
1632 isa<ShuffleVectorInst>(*OI) ||
1633 isa<ExtractElementInst>(*OI) ||
1634 isa<InsertElementInst>(*OI) ||
1635 isa<SelectInst>(*OI) ||
1636 isa<CastInst>(*OI) ||
1637 isa<GetElementPtrInst>(*OI)) {
1638 sVarargs.push_back(find_leader(availableOut[*PI],
1641 sVarargs.push_back(*OI);
1647 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1648 newVal = BinaryOperator::create(BO->getOpcode(), s1, s2,
1649 BO->getName()+".gvnpre",
1650 (*PI)->getTerminator());
1651 else if (CmpInst* C = dyn_cast<CmpInst>(U))
1652 newVal = CmpInst::create(C->getOpcode(), C->getPredicate(), s1, s2,
1653 C->getName()+".gvnpre",
1654 (*PI)->getTerminator());
1655 else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
1656 newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre",
1657 (*PI)->getTerminator());
1658 else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U))
1659 newVal = new InsertElementInst(s1, s2, s3, S->getName()+".gvnpre",
1660 (*PI)->getTerminator());
1661 else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U))
1662 newVal = new ExtractElementInst(s1, s2, S->getName()+".gvnpre",
1663 (*PI)->getTerminator());
1664 else if (SelectInst* S = dyn_cast<SelectInst>(U))
1665 newVal = new SelectInst(s1, s2, s3, S->getName()+".gvnpre",
1666 (*PI)->getTerminator());
1667 else if (CastInst* C = dyn_cast<CastInst>(U))
1668 newVal = CastInst::create(C->getOpcode(), s1, C->getType(),
1669 C->getName()+".gvnpre",
1670 (*PI)->getTerminator());
1671 else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U))
1672 newVal = new GetElementPtrInst(s1, &sVarargs[0], sVarargs.size(),
1673 G->getName()+".gvnpre",
1674 (*PI)->getTerminator());
1677 VN.add(newVal, VN.lookup(U));
1679 ValueNumberedSet& predAvail = availableOut[*PI];
1680 val_replace(predAvail, newVal);
1681 val_replace(new_sets[*PI], newVal);
1682 predAvail.set(VN.lookup(newVal));
1684 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1685 if (av != avail.end())
1687 avail.insert(std::make_pair(*PI, newVal));
1695 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1697 p = new PHINode(avail[*PI]->getType(), "gvnpre-join", BB->begin());
1699 p->addIncoming(avail[*PI], *PI);
1702 VN.add(p, VN.lookup(e));
1703 val_replace(availableOut[BB], p);
1704 availableOut[BB].set(VN.lookup(e));
1705 generatedPhis[BB].insert(p);
1706 generatedPhis[BB].set(VN.lookup(e));
1707 new_sets[BB].insert(p);
1708 new_sets[BB].set(VN.lookup(e));
1713 /// insertion_mergepoint - When walking the dom tree, check at each merge
1714 /// block for the possibility of a partial redundancy. If present, eliminate it
1715 unsigned GVNPRE::insertion_mergepoint(SmallVector<Value*, 8>& workList,
1716 df_iterator<DomTreeNode*>& D,
1717 std::map<BasicBlock*, ValueNumberedSet >& new_sets) {
1718 bool changed_function = false;
1719 bool new_stuff = false;
1721 BasicBlock* BB = D->getBlock();
1722 for (unsigned i = 0; i < workList.size(); ++i) {
1723 Value* e = workList[i];
1725 if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1726 isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) ||
1727 isa<ShuffleVectorInst>(e) || isa<SelectInst>(e) || isa<CastInst>(e) ||
1728 isa<GetElementPtrInst>(e)) {
1729 if (availableOut[D->getIDom()->getBlock()].test(VN.lookup(e)))
1732 DenseMap<BasicBlock*, Value*> avail;
1733 bool by_some = false;
1734 bool all_same = true;
1735 Value * first_s = 0;
1737 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1739 Value *e2 = phi_translate(e, *PI, BB);
1740 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1743 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1744 if (av != avail.end())
1746 avail.insert(std::make_pair(*PI, e2));
1749 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1750 if (av != avail.end())
1752 avail.insert(std::make_pair(*PI, e3));
1757 else if (first_s != e3)
1762 if (by_some && !all_same &&
1763 !generatedPhis[BB].test(VN.lookup(e))) {
1764 insertion_pre(e, BB, avail, new_sets);
1766 changed_function = true;
1772 unsigned retval = 0;
1773 if (changed_function)
1781 /// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for
1782 /// merge points. When one is found, check for a partial redundancy. If one is
1783 /// present, eliminate it. Repeat this walk until no changes are made.
1784 bool GVNPRE::insertion(Function& F) {
1785 bool changed_function = false;
1787 DominatorTree &DT = getAnalysis<DominatorTree>();
1789 std::map<BasicBlock*, ValueNumberedSet> new_sets;
1790 bool new_stuff = true;
1793 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1794 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1795 BasicBlock* BB = DI->getBlock();
1800 ValueNumberedSet& availOut = availableOut[BB];
1801 ValueNumberedSet& anticIn = anticipatedIn[BB];
1803 // Replace leaders with leaders inherited from dominator
1804 if (DI->getIDom() != 0) {
1805 ValueNumberedSet& dom_set = new_sets[DI->getIDom()->getBlock()];
1806 for (ValueNumberedSet::iterator I = dom_set.begin(),
1807 E = dom_set.end(); I != E; ++I) {
1808 val_replace(new_sets[BB], *I);
1809 val_replace(availOut, *I);
1813 // If there is more than one predecessor...
1814 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
1815 SmallVector<Value*, 8> workList;
1816 workList.reserve(anticIn.size());
1817 topo_sort(anticIn, workList);
1819 unsigned result = insertion_mergepoint(workList, DI, new_sets);
1821 changed_function = true;
1828 return changed_function;
1831 // GVNPRE::runOnFunction - This is the main transformation entry point for a
1834 bool GVNPRE::runOnFunction(Function &F) {
1835 // Clean out global sets from any previous functions
1837 createdExpressions.clear();
1838 availableOut.clear();
1839 anticipatedIn.clear();
1840 generatedPhis.clear();
1842 bool changed_function = false;
1844 // Phase 1: BuildSets
1845 // This phase calculates the AVAIL_OUT and ANTIC_IN sets
1849 // This phase inserts values to make partially redundant values
1851 changed_function |= insertion(F);
1853 // Phase 3: Eliminate
1854 // This phase performs trivial full redundancy elimination
1855 changed_function |= elimination();
1858 // This phase cleans up values that were created solely
1859 // as leaders for expressions
1862 return changed_function;