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/Statistic.h"
34 #include "llvm/Support/CFG.h"
35 #include "llvm/Support/Compiler.h"
36 #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 class VISIBILITY_HIDDEN ValueTable {
56 enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
57 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
58 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
59 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
60 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
61 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
62 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
63 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
64 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
65 PTRTOINT, INTTOPTR, BITCAST};
67 ExpressionOpcode opcode;
73 bool operator< (const Expression& other) const {
74 if (opcode < other.opcode)
76 else if (opcode > other.opcode)
78 else if (type < other.type)
80 else if (type > other.type)
82 else if (firstVN < other.firstVN)
84 else if (firstVN > other.firstVN)
86 else if (secondVN < other.secondVN)
88 else if (secondVN > other.secondVN)
90 else if (thirdVN < other.thirdVN)
92 else if (thirdVN > other.thirdVN)
100 DenseMap<Value*, uint32_t> valueNumbering;
101 std::map<Expression, uint32_t> expressionNumbering;
103 uint32_t nextValueNumber;
105 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
106 Expression::ExpressionOpcode getOpcode(CmpInst* C);
107 Expression::ExpressionOpcode getOpcode(CastInst* C);
108 Expression create_expression(BinaryOperator* BO);
109 Expression create_expression(CmpInst* C);
110 Expression create_expression(ShuffleVectorInst* V);
111 Expression create_expression(ExtractElementInst* C);
112 Expression create_expression(InsertElementInst* V);
113 Expression create_expression(SelectInst* V);
114 Expression create_expression(CastInst* C);
116 ValueTable() { nextValueNumber = 1; }
117 uint32_t lookup_or_add(Value* V);
118 uint32_t lookup(Value* V) const;
119 void add(Value* V, uint32_t num);
121 void erase(Value* v);
126 //===----------------------------------------------------------------------===//
127 // ValueTable Internal Functions
128 //===----------------------------------------------------------------------===//
129 ValueTable::Expression::ExpressionOpcode
130 ValueTable::getOpcode(BinaryOperator* BO) {
131 switch(BO->getOpcode()) {
132 case Instruction::Add:
133 return Expression::ADD;
134 case Instruction::Sub:
135 return Expression::SUB;
136 case Instruction::Mul:
137 return Expression::MUL;
138 case Instruction::UDiv:
139 return Expression::UDIV;
140 case Instruction::SDiv:
141 return Expression::SDIV;
142 case Instruction::FDiv:
143 return Expression::FDIV;
144 case Instruction::URem:
145 return Expression::UREM;
146 case Instruction::SRem:
147 return Expression::SREM;
148 case Instruction::FRem:
149 return Expression::FREM;
150 case Instruction::Shl:
151 return Expression::SHL;
152 case Instruction::LShr:
153 return Expression::LSHR;
154 case Instruction::AShr:
155 return Expression::ASHR;
156 case Instruction::And:
157 return Expression::AND;
158 case Instruction::Or:
159 return Expression::OR;
160 case Instruction::Xor:
161 return Expression::XOR;
163 // THIS SHOULD NEVER HAPPEN
165 assert(0 && "Binary operator with unknown opcode?");
166 return Expression::ADD;
170 ValueTable::Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
171 if (C->getOpcode() == Instruction::ICmp) {
172 switch (C->getPredicate()) {
173 case ICmpInst::ICMP_EQ:
174 return Expression::ICMPEQ;
175 case ICmpInst::ICMP_NE:
176 return Expression::ICMPNE;
177 case ICmpInst::ICMP_UGT:
178 return Expression::ICMPUGT;
179 case ICmpInst::ICMP_UGE:
180 return Expression::ICMPUGE;
181 case ICmpInst::ICMP_ULT:
182 return Expression::ICMPULT;
183 case ICmpInst::ICMP_ULE:
184 return Expression::ICMPULE;
185 case ICmpInst::ICMP_SGT:
186 return Expression::ICMPSGT;
187 case ICmpInst::ICMP_SGE:
188 return Expression::ICMPSGE;
189 case ICmpInst::ICMP_SLT:
190 return Expression::ICMPSLT;
191 case ICmpInst::ICMP_SLE:
192 return Expression::ICMPSLE;
194 // THIS SHOULD NEVER HAPPEN
196 assert(0 && "Comparison with unknown predicate?");
197 return Expression::ICMPEQ;
200 switch (C->getPredicate()) {
201 case FCmpInst::FCMP_OEQ:
202 return Expression::FCMPOEQ;
203 case FCmpInst::FCMP_OGT:
204 return Expression::FCMPOGT;
205 case FCmpInst::FCMP_OGE:
206 return Expression::FCMPOGE;
207 case FCmpInst::FCMP_OLT:
208 return Expression::FCMPOLT;
209 case FCmpInst::FCMP_OLE:
210 return Expression::FCMPOLE;
211 case FCmpInst::FCMP_ONE:
212 return Expression::FCMPONE;
213 case FCmpInst::FCMP_ORD:
214 return Expression::FCMPORD;
215 case FCmpInst::FCMP_UNO:
216 return Expression::FCMPUNO;
217 case FCmpInst::FCMP_UEQ:
218 return Expression::FCMPUEQ;
219 case FCmpInst::FCMP_UGT:
220 return Expression::FCMPUGT;
221 case FCmpInst::FCMP_UGE:
222 return Expression::FCMPUGE;
223 case FCmpInst::FCMP_ULT:
224 return Expression::FCMPULT;
225 case FCmpInst::FCMP_ULE:
226 return Expression::FCMPULE;
227 case FCmpInst::FCMP_UNE:
228 return Expression::FCMPUNE;
230 // THIS SHOULD NEVER HAPPEN
232 assert(0 && "Comparison with unknown predicate?");
233 return Expression::FCMPOEQ;
238 ValueTable::Expression::ExpressionOpcode
239 ValueTable::getOpcode(CastInst* C) {
240 switch(C->getOpcode()) {
241 case Instruction::Trunc:
242 return Expression::TRUNC;
243 case Instruction::ZExt:
244 return Expression::ZEXT;
245 case Instruction::SExt:
246 return Expression::SEXT;
247 case Instruction::FPToUI:
248 return Expression::FPTOUI;
249 case Instruction::FPToSI:
250 return Expression::FPTOSI;
251 case Instruction::UIToFP:
252 return Expression::UITOFP;
253 case Instruction::SIToFP:
254 return Expression::SITOFP;
255 case Instruction::FPTrunc:
256 return Expression::FPTRUNC;
257 case Instruction::FPExt:
258 return Expression::FPEXT;
259 case Instruction::PtrToInt:
260 return Expression::PTRTOINT;
261 case Instruction::IntToPtr:
262 return Expression::INTTOPTR;
263 case Instruction::BitCast:
264 return Expression::BITCAST;
266 // THIS SHOULD NEVER HAPPEN
268 assert(0 && "Cast operator with unknown opcode?");
269 return Expression::BITCAST;
273 ValueTable::Expression ValueTable::create_expression(BinaryOperator* BO) {
276 e.firstVN = lookup_or_add(BO->getOperand(0));
277 e.secondVN = lookup_or_add(BO->getOperand(1));
279 e.type = BO->getType();
280 e.opcode = getOpcode(BO);
285 ValueTable::Expression ValueTable::create_expression(CmpInst* C) {
288 e.firstVN = lookup_or_add(C->getOperand(0));
289 e.secondVN = lookup_or_add(C->getOperand(1));
291 e.type = C->getType();
292 e.opcode = getOpcode(C);
297 ValueTable::Expression ValueTable::create_expression(CastInst* C) {
300 e.firstVN = lookup_or_add(C->getOperand(0));
303 e.type = C->getType();
304 e.opcode = getOpcode(C);
309 ValueTable::Expression ValueTable::create_expression(ShuffleVectorInst* S) {
312 e.firstVN = lookup_or_add(S->getOperand(0));
313 e.secondVN = lookup_or_add(S->getOperand(1));
314 e.thirdVN = lookup_or_add(S->getOperand(2));
315 e.type = S->getType();
316 e.opcode = Expression::SHUFFLE;
321 ValueTable::Expression ValueTable::create_expression(ExtractElementInst* E) {
324 e.firstVN = lookup_or_add(E->getOperand(0));
325 e.secondVN = lookup_or_add(E->getOperand(1));
327 e.type = E->getType();
328 e.opcode = Expression::EXTRACT;
333 ValueTable::Expression ValueTable::create_expression(InsertElementInst* I) {
336 e.firstVN = lookup_or_add(I->getOperand(0));
337 e.secondVN = lookup_or_add(I->getOperand(1));
338 e.thirdVN = lookup_or_add(I->getOperand(2));
339 e.type = I->getType();
340 e.opcode = Expression::INSERT;
345 ValueTable::Expression ValueTable::create_expression(SelectInst* I) {
348 e.firstVN = lookup_or_add(I->getCondition());
349 e.secondVN = lookup_or_add(I->getTrueValue());
350 e.thirdVN = lookup_or_add(I->getFalseValue());
351 e.type = I->getType();
352 e.opcode = Expression::SELECT;
357 //===----------------------------------------------------------------------===//
358 // ValueTable External Functions
359 //===----------------------------------------------------------------------===//
361 /// lookup_or_add - Returns the value number for the specified value, assigning
362 /// it a new number if it did not have one before.
363 uint32_t ValueTable::lookup_or_add(Value* V) {
364 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
365 if (VI != valueNumbering.end())
369 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
370 Expression e = create_expression(BO);
372 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
373 if (EI != expressionNumbering.end()) {
374 valueNumbering.insert(std::make_pair(V, EI->second));
377 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
378 valueNumbering.insert(std::make_pair(V, nextValueNumber));
380 return nextValueNumber++;
382 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
383 Expression e = create_expression(C);
385 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
386 if (EI != expressionNumbering.end()) {
387 valueNumbering.insert(std::make_pair(V, EI->second));
390 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
391 valueNumbering.insert(std::make_pair(V, nextValueNumber));
393 return nextValueNumber++;
395 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
396 Expression e = create_expression(U);
398 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
399 if (EI != expressionNumbering.end()) {
400 valueNumbering.insert(std::make_pair(V, EI->second));
403 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
404 valueNumbering.insert(std::make_pair(V, nextValueNumber));
406 return nextValueNumber++;
408 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
409 Expression e = create_expression(U);
411 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
412 if (EI != expressionNumbering.end()) {
413 valueNumbering.insert(std::make_pair(V, EI->second));
416 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
417 valueNumbering.insert(std::make_pair(V, nextValueNumber));
419 return nextValueNumber++;
421 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
422 Expression e = create_expression(U);
424 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
425 if (EI != expressionNumbering.end()) {
426 valueNumbering.insert(std::make_pair(V, EI->second));
429 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
430 valueNumbering.insert(std::make_pair(V, nextValueNumber));
432 return nextValueNumber++;
434 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
435 Expression e = create_expression(U);
437 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
438 if (EI != expressionNumbering.end()) {
439 valueNumbering.insert(std::make_pair(V, EI->second));
442 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
443 valueNumbering.insert(std::make_pair(V, nextValueNumber));
445 return nextValueNumber++;
447 } else if (CastInst* U = dyn_cast<CastInst>(V)) {
448 Expression e = create_expression(U);
450 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
451 if (EI != expressionNumbering.end()) {
452 valueNumbering.insert(std::make_pair(V, EI->second));
455 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
456 valueNumbering.insert(std::make_pair(V, nextValueNumber));
458 return nextValueNumber++;
461 valueNumbering.insert(std::make_pair(V, nextValueNumber));
462 return nextValueNumber++;
466 /// lookup - Returns the value number of the specified value. Fails if
467 /// the value has not yet been numbered.
468 uint32_t ValueTable::lookup(Value* V) const {
469 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
470 if (VI != valueNumbering.end())
473 assert(0 && "Value not numbered?");
478 /// add - Add the specified value with the given value number, removing
479 /// its old number, if any
480 void ValueTable::add(Value* V, uint32_t num) {
481 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
482 if (VI != valueNumbering.end())
483 valueNumbering.erase(VI);
484 valueNumbering.insert(std::make_pair(V, num));
487 /// clear - Remove all entries from the ValueTable
488 void ValueTable::clear() {
489 valueNumbering.clear();
490 expressionNumbering.clear();
494 /// erase - Remove a value from the value numbering
495 void ValueTable::erase(Value* V) {
496 valueNumbering.erase(V);
499 /// size - Return the number of assigned value numbers
500 unsigned ValueTable::size() {
501 // NOTE: zero is never assigned
502 return nextValueNumber;
505 //===----------------------------------------------------------------------===//
507 //===----------------------------------------------------------------------===//
511 class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
512 bool runOnFunction(Function &F);
514 static char ID; // Pass identification, replacement for typeid
515 GVNPRE() : FunctionPass((intptr_t)&ID) { }
519 std::vector<Instruction*> createdExpressions;
521 std::map<BasicBlock*, SmallPtrSet<Value*, 16> > availableOut;
522 std::map<BasicBlock*, SmallPtrSet<Value*, 16> > anticipatedIn;
524 // This transformation requires dominator postdominator info
525 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
526 AU.setPreservesCFG();
527 AU.addRequired<DominatorTree>();
531 // FIXME: eliminate or document these better
532 void dump(const SmallPtrSet<Value*, 16>& s) const;
533 void clean(SmallPtrSet<Value*, 16>& set, BitVector& presentInSet);
534 Value* find_leader(SmallPtrSet<Value*, 16>& vals,
536 Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ);
537 void phi_translate_set(SmallPtrSet<Value*, 16>& anticIn, BasicBlock* pred,
538 BasicBlock* succ, SmallPtrSet<Value*, 16>& out);
540 void topo_sort(SmallPtrSet<Value*, 16>& set,
541 std::vector<Value*>& vec);
546 void val_insert(SmallPtrSet<Value*, 16>& s, Value* v);
547 void val_replace(SmallPtrSet<Value*, 16>& s, Value* v);
548 bool dependsOnInvoke(Value* V);
549 void buildsets_availout(BasicBlock::iterator I,
550 SmallPtrSet<Value*, 16>& currAvail,
551 SmallPtrSet<PHINode*, 16>& currPhis,
552 SmallPtrSet<Value*, 16>& currExps,
553 SmallPtrSet<Value*, 16>& currTemps,
554 BitVector& availNumbers,
555 BitVector& expNumbers);
556 bool buildsets_anticout(BasicBlock* BB,
557 SmallPtrSet<Value*, 16>& anticOut,
558 std::set<BasicBlock*>& visited);
559 unsigned buildsets_anticin(BasicBlock* BB,
560 SmallPtrSet<Value*, 16>& anticOut,
561 SmallPtrSet<Value*, 16>& currExps,
562 SmallPtrSet<Value*, 16>& currTemps,
563 std::set<BasicBlock*>& visited);
564 void buildsets(Function& F);
566 void insertion_pre(Value* e, BasicBlock* BB,
567 std::map<BasicBlock*, Value*>& avail,
568 SmallPtrSet<Value*, 16>& new_set);
569 unsigned insertion_mergepoint(std::vector<Value*>& workList,
570 df_iterator<DomTreeNode*>& D,
571 SmallPtrSet<Value*, 16>& new_set);
572 bool insertion(Function& F);
580 // createGVNPREPass - The public interface to this file...
581 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
583 RegisterPass<GVNPRE> X("gvnpre",
584 "Global Value Numbering/Partial Redundancy Elimination");
587 STATISTIC(NumInsertedVals, "Number of values inserted");
588 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
589 STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
591 /// find_leader - Given a set and a value number, return the first
592 /// element of the set with that value number, or 0 if no such element
594 Value* GVNPRE::find_leader(SmallPtrSet<Value*, 16>& vals, uint32_t v) {
595 for (SmallPtrSet<Value*, 16>::iterator I = vals.begin(), E = vals.end();
597 if (v == VN.lookup(*I))
603 /// val_insert - Insert a value into a set only if there is not a value
604 /// with the same value number already in the set
605 void GVNPRE::val_insert(SmallPtrSet<Value*, 16>& s, Value* v) {
606 uint32_t num = VN.lookup(v);
607 Value* leader = find_leader(s, num);
612 /// val_replace - Insert a value into a set, replacing any values already in
613 /// the set that have the same value number
614 void GVNPRE::val_replace(SmallPtrSet<Value*, 16>& s, Value* v) {
615 uint32_t num = VN.lookup(v);
616 Value* leader = find_leader(s, num);
617 while (leader != 0) {
619 leader = find_leader(s, num);
624 /// phi_translate - Given a value, its parent block, and a predecessor of its
625 /// parent, translate the value into legal for the predecessor block. This
626 /// means translating its operands (and recursively, their operands) through
627 /// any phi nodes in the parent into values available in the predecessor
628 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
633 if (isa<CastInst>(V)) {
634 User* U = cast<User>(V);
637 if (isa<Instruction>(U->getOperand(0)))
638 newOp1 = phi_translate(U->getOperand(0), pred, succ);
640 newOp1 = U->getOperand(0);
645 if (newOp1 != U->getOperand(0)) {
646 Instruction* newVal = 0;
647 if (CastInst* C = dyn_cast<CastInst>(U))
648 newVal = CastInst::create(C->getOpcode(),
649 newOp1, C->getType(),
650 C->getName()+".expr");
652 uint32_t v = VN.lookup_or_add(newVal);
654 Value* leader = find_leader(availableOut[pred], v);
656 createdExpressions.push_back(newVal);
666 } if (isa<BinaryOperator>(V) || isa<CmpInst>(V) ||
667 isa<ExtractElementInst>(V)) {
668 User* U = cast<User>(V);
671 if (isa<Instruction>(U->getOperand(0)))
672 newOp1 = phi_translate(U->getOperand(0), pred, succ);
674 newOp1 = U->getOperand(0);
680 if (isa<Instruction>(U->getOperand(1)))
681 newOp2 = phi_translate(U->getOperand(1), pred, succ);
683 newOp2 = U->getOperand(1);
688 if (newOp1 != U->getOperand(0) || newOp2 != U->getOperand(1)) {
689 Instruction* newVal = 0;
690 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
691 newVal = BinaryOperator::create(BO->getOpcode(),
693 BO->getName()+".expr");
694 else if (CmpInst* C = dyn_cast<CmpInst>(U))
695 newVal = CmpInst::create(C->getOpcode(),
698 C->getName()+".expr");
699 else if (ExtractElementInst* E = dyn_cast<ExtractElementInst>(U))
700 newVal = new ExtractElementInst(newOp1, newOp2, E->getName()+".expr");
702 uint32_t v = VN.lookup_or_add(newVal);
704 Value* leader = find_leader(availableOut[pred], v);
706 createdExpressions.push_back(newVal);
715 // Ternary Operations
716 } else if (isa<ShuffleVectorInst>(V) || isa<InsertElementInst>(V) ||
717 isa<SelectInst>(V)) {
718 User* U = cast<User>(V);
721 if (isa<Instruction>(U->getOperand(0)))
722 newOp1 = phi_translate(U->getOperand(0), pred, succ);
724 newOp1 = U->getOperand(0);
730 if (isa<Instruction>(U->getOperand(1)))
731 newOp2 = phi_translate(U->getOperand(1), pred, succ);
733 newOp2 = U->getOperand(1);
739 if (isa<Instruction>(U->getOperand(2)))
740 newOp3 = phi_translate(U->getOperand(2), pred, succ);
742 newOp3 = U->getOperand(2);
747 if (newOp1 != U->getOperand(0) ||
748 newOp2 != U->getOperand(1) ||
749 newOp3 != U->getOperand(2)) {
750 Instruction* newVal = 0;
751 if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
752 newVal = new ShuffleVectorInst(newOp1, newOp2, newOp3,
753 S->getName()+".expr");
754 else if (InsertElementInst* I = dyn_cast<InsertElementInst>(U))
755 newVal = new InsertElementInst(newOp1, newOp2, newOp3,
756 I->getName()+".expr");
757 else if (SelectInst* I = dyn_cast<SelectInst>(U))
758 newVal = new SelectInst(newOp1, newOp2, newOp3, I->getName()+".expr");
760 uint32_t v = VN.lookup_or_add(newVal);
762 Value* leader = find_leader(availableOut[pred], v);
764 createdExpressions.push_back(newVal);
774 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
775 if (P->getParent() == succ)
776 return P->getIncomingValueForBlock(pred);
782 /// phi_translate_set - Perform phi translation on every element of a set
783 void GVNPRE::phi_translate_set(SmallPtrSet<Value*, 16>& anticIn,
784 BasicBlock* pred, BasicBlock* succ,
785 SmallPtrSet<Value*, 16>& out) {
786 for (SmallPtrSet<Value*, 16>::iterator I = anticIn.begin(),
787 E = anticIn.end(); I != E; ++I) {
788 Value* V = phi_translate(*I, pred, succ);
794 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of
795 /// whose inputs is an invoke instruction. If this is true, we cannot safely
796 /// PRE the instruction or anything that depends on it.
797 bool GVNPRE::dependsOnInvoke(Value* V) {
798 if (PHINode* p = dyn_cast<PHINode>(V)) {
799 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
800 if (isa<InvokeInst>(*I))
808 /// clean - Remove all non-opaque values from the set whose operands are not
809 /// themselves in the set, as well as all values that depend on invokes (see
811 void GVNPRE::clean(SmallPtrSet<Value*, 16>& set, BitVector& presentInSet) {
812 std::vector<Value*> worklist;
813 worklist.reserve(set.size());
814 topo_sort(set, worklist);
816 for (unsigned i = 0; i < worklist.size(); ++i) {
817 Value* v = worklist[i];
820 if (isa<CastInst>(v)) {
821 User* U = cast<User>(v);
823 bool lhsValid = !isa<Instruction>(U->getOperand(0));
824 lhsValid |= presentInSet.test(VN.lookup(U->getOperand(0)));
826 lhsValid = !dependsOnInvoke(U->getOperand(0));
830 presentInSet.flip(VN.lookup(U));
834 } else if (isa<BinaryOperator>(v) || isa<CmpInst>(v) ||
835 isa<ExtractElementInst>(v)) {
836 User* U = cast<User>(v);
838 bool lhsValid = !isa<Instruction>(U->getOperand(0));
839 lhsValid |= presentInSet.test(VN.lookup(U->getOperand(0)));
841 lhsValid = !dependsOnInvoke(U->getOperand(0));
843 bool rhsValid = !isa<Instruction>(U->getOperand(1));
844 rhsValid |= presentInSet.test(VN.lookup(U->getOperand(1)));
846 rhsValid = !dependsOnInvoke(U->getOperand(1));
848 if (!lhsValid || !rhsValid) {
850 presentInSet.flip(VN.lookup(U));
853 // Handle ternary ops
854 } else if (isa<ShuffleVectorInst>(v) || isa<InsertElementInst>(v) ||
855 isa<SelectInst>(v)) {
856 User* U = cast<User>(v);
858 bool lhsValid = !isa<Instruction>(U->getOperand(0));
859 lhsValid |= presentInSet.test(VN.lookup(U->getOperand(0)));
861 lhsValid = !dependsOnInvoke(U->getOperand(0));
863 bool rhsValid = !isa<Instruction>(U->getOperand(1));
864 rhsValid |= presentInSet.test(VN.lookup(U->getOperand(1)));
866 rhsValid = !dependsOnInvoke(U->getOperand(1));
868 bool thirdValid = !isa<Instruction>(U->getOperand(2));
869 thirdValid |= presentInSet.test(VN.lookup(U->getOperand(2)));
871 thirdValid = !dependsOnInvoke(U->getOperand(2));
873 if (!lhsValid || !rhsValid || !thirdValid) {
875 presentInSet.flip(VN.lookup(U));
881 /// topo_sort - Given a set of values, sort them by topological
882 /// order into the provided vector.
883 void GVNPRE::topo_sort(SmallPtrSet<Value*, 16>& set, std::vector<Value*>& vec) {
884 SmallPtrSet<Value*, 16> visited;
885 std::vector<Value*> stack;
886 for (SmallPtrSet<Value*, 16>::iterator I = set.begin(), E = set.end();
888 if (visited.count(*I) == 0)
891 while (!stack.empty()) {
892 Value* e = stack.back();
895 if (isa<CastInst>(e)) {
896 User* U = cast<User>(e);
897 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
899 if (l != 0 && isa<Instruction>(l) &&
900 visited.count(l) == 0)
909 } else if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
910 isa<ExtractElementInst>(e)) {
911 User* U = cast<User>(e);
912 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
913 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
915 if (l != 0 && isa<Instruction>(l) &&
916 visited.count(l) == 0)
918 else if (r != 0 && isa<Instruction>(r) &&
919 visited.count(r) == 0)
927 // Handle ternary ops
928 } else if (isa<InsertElementInst>(e) || isa<ShuffleVectorInst>(e) ||
929 isa<SelectInst>(e)) {
930 User* U = cast<User>(e);
931 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
932 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
933 Value* m = find_leader(set, VN.lookup(U->getOperand(2)));
935 if (l != 0 && isa<Instruction>(l) &&
936 visited.count(l) == 0)
938 else if (r != 0 && isa<Instruction>(r) &&
939 visited.count(r) == 0)
941 else if (m != 0 && isa<Instruction>(m) &&
942 visited.count(m) == 0)
962 /// dump - Dump a set of values to standard error
963 void GVNPRE::dump(const SmallPtrSet<Value*, 16>& s) const {
965 for (SmallPtrSet<Value*, 16>::iterator I = s.begin(), E = s.end();
967 DOUT << "" << VN.lookup(*I) << ": ";
973 /// elimination - Phase 3 of the main algorithm. Perform full redundancy
974 /// elimination by walking the dominator tree and removing any instruction that
975 /// is dominated by another instruction with the same value number.
976 bool GVNPRE::elimination() {
977 DOUT << "\n\nPhase 3: Elimination\n\n";
979 bool changed_function = false;
981 std::vector<std::pair<Instruction*, Value*> > replace;
982 std::vector<Instruction*> erase;
984 DominatorTree& DT = getAnalysis<DominatorTree>();
986 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
987 E = df_end(DT.getRootNode()); DI != E; ++DI) {
988 BasicBlock* BB = DI->getBlock();
990 //DOUT << "Block: " << BB->getName() << "\n";
991 //dump(availableOut[BB]);
994 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
997 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI) ||
998 isa<ShuffleVectorInst>(BI) || isa<InsertElementInst>(BI) ||
999 isa<ExtractElementInst>(BI) || isa<SelectInst>(BI) ||
1000 isa<CastInst>(BI)) {
1001 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
1004 if (Instruction* Instr = dyn_cast<Instruction>(leader))
1005 if (Instr->getParent() != 0 && Instr != BI) {
1006 replace.push_back(std::make_pair(BI, leader));
1007 erase.push_back(BI);
1014 while (!replace.empty()) {
1015 std::pair<Instruction*, Value*> rep = replace.back();
1017 rep.first->replaceAllUsesWith(rep.second);
1018 changed_function = true;
1021 for (std::vector<Instruction*>::iterator I = erase.begin(), E = erase.end();
1023 (*I)->eraseFromParent();
1025 return changed_function;
1028 /// cleanup - Delete any extraneous values that were created to represent
1029 /// expressions without leaders.
1030 void GVNPRE::cleanup() {
1031 while (!createdExpressions.empty()) {
1032 Instruction* I = createdExpressions.back();
1033 createdExpressions.pop_back();
1039 /// buildsets_availout - When calculating availability, handle an instruction
1040 /// by inserting it into the appropriate sets
1041 void GVNPRE::buildsets_availout(BasicBlock::iterator I,
1042 SmallPtrSet<Value*, 16>& currAvail,
1043 SmallPtrSet<PHINode*, 16>& currPhis,
1044 SmallPtrSet<Value*, 16>& currExps,
1045 SmallPtrSet<Value*, 16>& currTemps,
1046 BitVector& availNumbers,
1047 BitVector& expNumbers) {
1049 if (PHINode* p = dyn_cast<PHINode>(I)) {
1050 VN.lookup_or_add(p);
1051 expNumbers.resize(VN.size());
1052 availNumbers.resize(VN.size());
1057 } else if (isa<CastInst>(I)) {
1058 User* U = cast<User>(I);
1059 Value* leftValue = U->getOperand(0);
1061 unsigned num = VN.lookup_or_add(U);
1062 expNumbers.resize(VN.size());
1063 availNumbers.resize(VN.size());
1065 if (isa<Instruction>(leftValue))
1066 if (!expNumbers.test(VN.lookup(leftValue))) {
1067 currExps.insert(leftValue);
1068 expNumbers.set(VN.lookup(leftValue));
1071 if (!expNumbers.test(VN.lookup(U))) {
1073 expNumbers.set(num);
1076 // Handle binary ops
1077 } else if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
1078 isa<ExtractElementInst>(I)) {
1079 User* U = cast<User>(I);
1080 Value* leftValue = U->getOperand(0);
1081 Value* rightValue = U->getOperand(1);
1083 unsigned num = VN.lookup_or_add(U);
1084 expNumbers.resize(VN.size());
1085 availNumbers.resize(VN.size());
1087 if (isa<Instruction>(leftValue))
1088 if (!expNumbers.test(VN.lookup(leftValue))) {
1089 currExps.insert(leftValue);
1090 expNumbers.set(VN.lookup(leftValue));
1093 if (isa<Instruction>(rightValue))
1094 if (!expNumbers.test(VN.lookup(rightValue))) {
1095 currExps.insert(rightValue);
1096 expNumbers.set(VN.lookup(rightValue));
1099 if (!expNumbers.test(VN.lookup(U))) {
1101 expNumbers.set(num);
1104 // Handle ternary ops
1105 } else if (isa<InsertElementInst>(I) || isa<ShuffleVectorInst>(I) ||
1106 isa<SelectInst>(I)) {
1107 User* U = cast<User>(I);
1108 Value* leftValue = U->getOperand(0);
1109 Value* rightValue = U->getOperand(1);
1110 Value* thirdValue = U->getOperand(2);
1112 VN.lookup_or_add(U);
1114 unsigned num = VN.lookup_or_add(U);
1115 expNumbers.resize(VN.size());
1116 availNumbers.resize(VN.size());
1118 if (isa<Instruction>(leftValue))
1119 if (!expNumbers.test(VN.lookup(leftValue))) {
1120 currExps.insert(leftValue);
1121 expNumbers.set(VN.lookup(leftValue));
1123 if (isa<Instruction>(rightValue))
1124 if (!expNumbers.test(VN.lookup(rightValue))) {
1125 currExps.insert(rightValue);
1126 expNumbers.set(VN.lookup(rightValue));
1128 if (isa<Instruction>(thirdValue))
1129 if (!expNumbers.test(VN.lookup(thirdValue))) {
1130 currExps.insert(thirdValue);
1131 expNumbers.set(VN.lookup(thirdValue));
1134 if (!expNumbers.test(VN.lookup(U))) {
1136 expNumbers.set(num);
1139 // Handle opaque ops
1140 } else if (!I->isTerminator()){
1141 VN.lookup_or_add(I);
1142 expNumbers.resize(VN.size());
1143 availNumbers.resize(VN.size());
1145 currTemps.insert(I);
1148 if (!I->isTerminator())
1149 if (!availNumbers.test(VN.lookup(I))) {
1150 currAvail.insert(I);
1151 availNumbers.set(VN.lookup(I));
1155 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
1156 /// set as a function of the ANTIC_IN set of the block's predecessors
1157 bool GVNPRE::buildsets_anticout(BasicBlock* BB,
1158 SmallPtrSet<Value*, 16>& anticOut,
1159 std::set<BasicBlock*>& visited) {
1160 if (BB->getTerminator()->getNumSuccessors() == 1) {
1161 if (BB->getTerminator()->getSuccessor(0) != BB &&
1162 visited.count(BB->getTerminator()->getSuccessor(0)) == 0) {
1163 DOUT << "DEFER: " << BB->getName() << "\n";
1167 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
1168 BB, BB->getTerminator()->getSuccessor(0), anticOut);
1170 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
1171 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
1172 anticOut.insert(anticipatedIn[first].begin(), anticipatedIn[first].end());
1174 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
1175 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
1176 SmallPtrSet<Value*, 16>& succAnticIn = anticipatedIn[currSucc];
1178 std::vector<Value*> temp;
1180 for (SmallPtrSet<Value*, 16>::iterator I = anticOut.begin(),
1181 E = anticOut.end(); I != E; ++I)
1182 if (succAnticIn.count(*I) == 0)
1185 for (std::vector<Value*>::iterator I = temp.begin(), E = temp.end();
1194 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
1195 /// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN
1196 /// sets populated in buildsets_availout
1197 unsigned GVNPRE::buildsets_anticin(BasicBlock* BB,
1198 SmallPtrSet<Value*, 16>& anticOut,
1199 SmallPtrSet<Value*, 16>& currExps,
1200 SmallPtrSet<Value*, 16>& currTemps,
1201 std::set<BasicBlock*>& visited) {
1202 SmallPtrSet<Value*, 16>& anticIn = anticipatedIn[BB];
1203 unsigned old = anticIn.size();
1205 bool defer = buildsets_anticout(BB, anticOut, visited);
1211 BitVector numbers(VN.size());
1212 for (SmallPtrSet<Value*, 16>::iterator I = anticOut.begin(),
1213 E = anticOut.end(); I != E; ++I) {
1214 unsigned num = VN.lookup_or_add(*I);
1215 numbers.resize(VN.size());
1217 if (isa<Instruction>(*I)) {
1222 for (SmallPtrSet<Value*, 16>::iterator I = currExps.begin(),
1223 E = currExps.end(); I != E; ++I) {
1224 if (!numbers.test(VN.lookup_or_add(*I))) {
1226 numbers.set(VN.lookup(*I));
1230 for (SmallPtrSet<Value*, 16>::iterator I = currTemps.begin(),
1231 E = currTemps.end(); I != E; ++I) {
1233 numbers.flip(VN.lookup(*I));
1236 clean(anticIn, numbers);
1239 if (old != anticIn.size())
1245 /// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT
1246 /// and the ANTIC_IN sets.
1247 void GVNPRE::buildsets(Function& F) {
1248 std::map<BasicBlock*, SmallPtrSet<Value*, 16> > generatedExpressions;
1249 std::map<BasicBlock*, SmallPtrSet<PHINode*, 16> > generatedPhis;
1250 std::map<BasicBlock*, SmallPtrSet<Value*, 16> > generatedTemporaries;
1252 DominatorTree &DT = getAnalysis<DominatorTree>();
1254 // Phase 1, Part 1: calculate AVAIL_OUT
1256 // Top-down walk of the dominator tree
1257 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1258 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1260 // Get the sets to update for this block
1261 SmallPtrSet<Value*, 16>& currExps = generatedExpressions[DI->getBlock()];
1262 SmallPtrSet<PHINode*, 16>& currPhis = generatedPhis[DI->getBlock()];
1263 SmallPtrSet<Value*, 16>& currTemps = generatedTemporaries[DI->getBlock()];
1264 SmallPtrSet<Value*, 16>& currAvail = availableOut[DI->getBlock()];
1266 BasicBlock* BB = DI->getBlock();
1268 // A block inherits AVAIL_OUT from its dominator
1269 if (DI->getIDom() != 0)
1270 currAvail.insert(availableOut[DI->getIDom()->getBlock()].begin(),
1271 availableOut[DI->getIDom()->getBlock()].end());
1273 BitVector availNumbers(VN.size());
1274 for (SmallPtrSet<Value*, 16>::iterator I = currAvail.begin(),
1275 E = currAvail.end(); I != E; ++I)
1276 availNumbers.set(VN.lookup(*I));
1278 BitVector expNumbers(VN.size());
1279 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1281 buildsets_availout(BI, currAvail, currPhis, currExps,
1282 currTemps, availNumbers, expNumbers);
1286 // Phase 1, Part 2: calculate ANTIC_IN
1288 std::set<BasicBlock*> visited;
1289 SmallPtrSet<BasicBlock*, 4> block_changed;
1290 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
1291 block_changed.insert(FI);
1293 bool changed = true;
1294 unsigned iterations = 0;
1298 SmallPtrSet<Value*, 16> anticOut;
1300 // Postorder walk of the CFG
1301 for (po_iterator<BasicBlock*> BBI = po_begin(&F.getEntryBlock()),
1302 BBE = po_end(&F.getEntryBlock()); BBI != BBE; ++BBI) {
1303 BasicBlock* BB = *BBI;
1305 if (block_changed.count(BB) != 0) {
1306 unsigned ret = buildsets_anticin(BB, anticOut,generatedExpressions[BB],
1307 generatedTemporaries[BB], visited);
1316 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1318 block_changed.insert(*PI);
1321 block_changed.erase(BB);
1323 changed |= (ret == 2);
1331 DOUT << "ITERATIONS: " << iterations << "\n";
1334 /// insertion_pre - When a partial redundancy has been identified, eliminate it
1335 /// by inserting appropriate values into the predecessors and a phi node in
1337 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
1338 std::map<BasicBlock*, Value*>& avail,
1339 SmallPtrSet<Value*, 16>& new_set) {
1340 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1341 Value* e2 = avail[*PI];
1342 if (!find_leader(availableOut[*PI], VN.lookup(e2))) {
1343 User* U = cast<User>(e2);
1346 if (isa<BinaryOperator>(U->getOperand(0)) ||
1347 isa<CmpInst>(U->getOperand(0)) ||
1348 isa<ShuffleVectorInst>(U->getOperand(0)) ||
1349 isa<ExtractElementInst>(U->getOperand(0)) ||
1350 isa<InsertElementInst>(U->getOperand(0)) ||
1351 isa<SelectInst>(U->getOperand(0)) ||
1352 isa<CastInst>(U->getOperand(0)))
1353 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1355 s1 = U->getOperand(0);
1359 if (isa<BinaryOperator>(U) ||
1361 isa<ShuffleVectorInst>(U) ||
1362 isa<ExtractElementInst>(U) ||
1363 isa<InsertElementInst>(U) ||
1365 if (isa<BinaryOperator>(U->getOperand(1)) ||
1366 isa<CmpInst>(U->getOperand(1)) ||
1367 isa<ShuffleVectorInst>(U->getOperand(1)) ||
1368 isa<ExtractElementInst>(U->getOperand(1)) ||
1369 isa<InsertElementInst>(U->getOperand(1)) ||
1370 isa<SelectInst>(U->getOperand(1)) ||
1371 isa<CastInst>(U->getOperand(1))) {
1372 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1374 s2 = U->getOperand(1);
1377 // Ternary Operators
1379 if (isa<ShuffleVectorInst>(U) ||
1380 isa<InsertElementInst>(U) ||
1382 if (isa<BinaryOperator>(U->getOperand(2)) ||
1383 isa<CmpInst>(U->getOperand(2)) ||
1384 isa<ShuffleVectorInst>(U->getOperand(2)) ||
1385 isa<ExtractElementInst>(U->getOperand(2)) ||
1386 isa<InsertElementInst>(U->getOperand(2)) ||
1387 isa<SelectInst>(U->getOperand(2)) ||
1388 isa<CastInst>(U->getOperand(2))) {
1389 s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2)));
1391 s3 = U->getOperand(2);
1395 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1396 newVal = BinaryOperator::create(BO->getOpcode(), s1, s2,
1397 BO->getName()+".gvnpre",
1398 (*PI)->getTerminator());
1399 else if (CmpInst* C = dyn_cast<CmpInst>(U))
1400 newVal = CmpInst::create(C->getOpcode(), C->getPredicate(), s1, s2,
1401 C->getName()+".gvnpre",
1402 (*PI)->getTerminator());
1403 else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
1404 newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre",
1405 (*PI)->getTerminator());
1406 else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U))
1407 newVal = new InsertElementInst(s1, s2, s3, S->getName()+".gvnpre",
1408 (*PI)->getTerminator());
1409 else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U))
1410 newVal = new ExtractElementInst(s1, s2, S->getName()+".gvnpre",
1411 (*PI)->getTerminator());
1412 else if (SelectInst* S = dyn_cast<SelectInst>(U))
1413 newVal = new SelectInst(S->getCondition(), S->getTrueValue(),
1414 S->getFalseValue(), S->getName()+".gvnpre",
1415 (*PI)->getTerminator());
1416 else if (CastInst* C = dyn_cast<CastInst>(U))
1417 newVal = CastInst::create(C->getOpcode(), s1, C->getType(),
1418 C->getName()+".gvnpre",
1419 (*PI)->getTerminator());
1422 VN.add(newVal, VN.lookup(U));
1424 SmallPtrSet<Value*, 16>& predAvail = availableOut[*PI];
1425 val_replace(predAvail, newVal);
1427 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1428 if (av != avail.end())
1430 avail.insert(std::make_pair(*PI, newVal));
1438 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1440 p = new PHINode(avail[*PI]->getType(), "gvnpre-join", BB->begin());
1442 p->addIncoming(avail[*PI], *PI);
1445 VN.add(p, VN.lookup(e));
1446 val_replace(availableOut[BB], p);
1452 /// insertion_mergepoint - When walking the dom tree, check at each merge
1453 /// block for the possibility of a partial redundancy. If present, eliminate it
1454 unsigned GVNPRE::insertion_mergepoint(std::vector<Value*>& workList,
1455 df_iterator<DomTreeNode*>& D,
1456 SmallPtrSet<Value*, 16>& new_set) {
1457 bool changed_function = false;
1458 bool new_stuff = false;
1460 BasicBlock* BB = D->getBlock();
1461 for (unsigned i = 0; i < workList.size(); ++i) {
1462 Value* e = workList[i];
1464 if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1465 isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) ||
1466 isa<ShuffleVectorInst>(e) || isa<SelectInst>(e) || isa<CastInst>(e)) {
1467 if (find_leader(availableOut[D->getIDom()->getBlock()],
1471 std::map<BasicBlock*, Value*> avail;
1472 bool by_some = false;
1475 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1477 Value *e2 = phi_translate(e, *PI, BB);
1478 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1481 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1482 if (av != avail.end())
1484 avail.insert(std::make_pair(*PI, e2));
1486 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1487 if (av != avail.end())
1489 avail.insert(std::make_pair(*PI, e3));
1496 if (by_some && num_avail < std::distance(pred_begin(BB), pred_end(BB))) {
1497 insertion_pre(e, BB, avail, new_set);
1499 changed_function = true;
1505 unsigned retval = 0;
1506 if (changed_function)
1514 /// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for
1515 /// merge points. When one is found, check for a partial redundancy. If one is
1516 /// present, eliminate it. Repeat this walk until no changes are made.
1517 bool GVNPRE::insertion(Function& F) {
1518 bool changed_function = false;
1520 DominatorTree &DT = getAnalysis<DominatorTree>();
1522 std::map<BasicBlock*, SmallPtrSet<Value*, 16> > new_sets;
1523 bool new_stuff = true;
1526 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1527 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1528 BasicBlock* BB = DI->getBlock();
1533 SmallPtrSet<Value*, 16>& new_set = new_sets[BB];
1534 SmallPtrSet<Value*, 16>& availOut = availableOut[BB];
1535 SmallPtrSet<Value*, 16>& anticIn = anticipatedIn[BB];
1539 // Replace leaders with leaders inherited from dominator
1540 if (DI->getIDom() != 0) {
1541 SmallPtrSet<Value*, 16>& dom_set = new_sets[DI->getIDom()->getBlock()];
1542 for (SmallPtrSet<Value*, 16>::iterator I = dom_set.begin(),
1543 E = dom_set.end(); I != E; ++I) {
1545 val_replace(availOut, *I);
1549 // If there is more than one predecessor...
1550 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
1551 std::vector<Value*> workList;
1552 workList.reserve(anticIn.size());
1553 topo_sort(anticIn, workList);
1555 unsigned result = insertion_mergepoint(workList, DI, new_set);
1557 changed_function = true;
1564 return changed_function;
1567 // GVNPRE::runOnFunction - This is the main transformation entry point for a
1570 bool GVNPRE::runOnFunction(Function &F) {
1571 // Clean out global sets from any previous functions
1573 createdExpressions.clear();
1574 availableOut.clear();
1575 anticipatedIn.clear();
1577 bool changed_function = false;
1579 // Phase 1: BuildSets
1580 // This phase calculates the AVAIL_OUT and ANTIC_IN sets
1583 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
1584 DOUT << "AVAIL_OUT: " << FI->getName() << "\n";
1585 dump(availableOut[FI]);
1587 DOUT << "ANTIC_IN: " << FI->getName() << "\n";
1588 dump(anticipatedIn[FI]);
1593 // This phase inserts values to make partially redundant values
1595 changed_function |= insertion(F);
1597 // Phase 3: Eliminate
1598 // This phase performs trivial full redundancy elimination
1599 changed_function |= elimination();
1602 // This phase cleans up values that were created solely
1603 // as leaders for expressions
1606 return changed_function;