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<BinaryOperator>(V) || isa<CmpInst>(V) ||
634 isa<ExtractElementInst>(V)) {
635 User* U = cast<User>(V);
638 if (isa<Instruction>(U->getOperand(0)))
639 newOp1 = phi_translate(U->getOperand(0), pred, succ);
641 newOp1 = U->getOperand(0);
647 if (isa<Instruction>(U->getOperand(1)))
648 newOp2 = phi_translate(U->getOperand(1), pred, succ);
650 newOp2 = U->getOperand(1);
655 if (newOp1 != U->getOperand(0) || newOp2 != U->getOperand(1)) {
656 Instruction* newVal = 0;
657 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
658 newVal = BinaryOperator::create(BO->getOpcode(),
660 BO->getName()+".expr");
661 else if (CmpInst* C = dyn_cast<CmpInst>(U))
662 newVal = CmpInst::create(C->getOpcode(),
665 C->getName()+".expr");
666 else if (ExtractElementInst* E = dyn_cast<ExtractElementInst>(U))
667 newVal = new ExtractElementInst(newOp1, newOp2, E->getName()+".expr");
669 uint32_t v = VN.lookup_or_add(newVal);
671 Value* leader = find_leader(availableOut[pred], v);
673 createdExpressions.push_back(newVal);
682 // Ternary Operations
683 } else if (isa<ShuffleVectorInst>(V) || isa<InsertElementInst>(V) ||
684 isa<SelectInst>(V)) {
685 User* U = cast<User>(V);
688 if (isa<Instruction>(U->getOperand(0)))
689 newOp1 = phi_translate(U->getOperand(0), pred, succ);
691 newOp1 = U->getOperand(0);
697 if (isa<Instruction>(U->getOperand(1)))
698 newOp2 = phi_translate(U->getOperand(1), pred, succ);
700 newOp2 = U->getOperand(1);
706 if (isa<Instruction>(U->getOperand(2)))
707 newOp3 = phi_translate(U->getOperand(2), pred, succ);
709 newOp3 = U->getOperand(2);
714 if (newOp1 != U->getOperand(0) ||
715 newOp2 != U->getOperand(1) ||
716 newOp3 != U->getOperand(2)) {
717 Instruction* newVal = 0;
718 if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
719 newVal = new ShuffleVectorInst(newOp1, newOp2, newOp3,
720 S->getName()+".expr");
721 else if (InsertElementInst* I = dyn_cast<InsertElementInst>(U))
722 newVal = new InsertElementInst(newOp1, newOp2, newOp3,
723 I->getName()+".expr");
724 else if (SelectInst* I = dyn_cast<SelectInst>(U))
725 newVal = new SelectInst(newOp1, newOp2, newOp3, I->getName()+".expr");
727 uint32_t v = VN.lookup_or_add(newVal);
729 Value* leader = find_leader(availableOut[pred], v);
731 createdExpressions.push_back(newVal);
741 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
742 if (P->getParent() == succ)
743 return P->getIncomingValueForBlock(pred);
749 /// phi_translate_set - Perform phi translation on every element of a set
750 void GVNPRE::phi_translate_set(SmallPtrSet<Value*, 16>& anticIn,
751 BasicBlock* pred, BasicBlock* succ,
752 SmallPtrSet<Value*, 16>& out) {
753 for (SmallPtrSet<Value*, 16>::iterator I = anticIn.begin(),
754 E = anticIn.end(); I != E; ++I) {
755 Value* V = phi_translate(*I, pred, succ);
761 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of
762 /// whose inputs is an invoke instruction. If this is true, we cannot safely
763 /// PRE the instruction or anything that depends on it.
764 bool GVNPRE::dependsOnInvoke(Value* V) {
765 if (PHINode* p = dyn_cast<PHINode>(V)) {
766 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
767 if (isa<InvokeInst>(*I))
775 /// clean - Remove all non-opaque values from the set whose operands are not
776 /// themselves in the set, as well as all values that depend on invokes (see
778 void GVNPRE::clean(SmallPtrSet<Value*, 16>& set, BitVector& presentInSet) {
779 std::vector<Value*> worklist;
780 worklist.reserve(set.size());
781 topo_sort(set, worklist);
783 for (unsigned i = 0; i < worklist.size(); ++i) {
784 Value* v = worklist[i];
787 if (isa<BinaryOperator>(v) || isa<CmpInst>(v) ||
788 isa<ExtractElementInst>(v)) {
789 User* U = cast<User>(v);
791 bool lhsValid = !isa<Instruction>(U->getOperand(0));
792 lhsValid |= presentInSet.test(VN.lookup(U->getOperand(0)));
794 lhsValid = !dependsOnInvoke(U->getOperand(0));
796 bool rhsValid = !isa<Instruction>(U->getOperand(1));
797 rhsValid |= presentInSet.test(VN.lookup(U->getOperand(1)));
799 rhsValid = !dependsOnInvoke(U->getOperand(1));
801 if (!lhsValid || !rhsValid) {
803 presentInSet.flip(VN.lookup(U));
806 // Handle ternary ops
807 } else if (isa<ShuffleVectorInst>(v) || isa<InsertElementInst>(v) ||
808 isa<SelectInst>(v)) {
809 User* U = cast<User>(v);
811 bool lhsValid = !isa<Instruction>(U->getOperand(0));
812 lhsValid |= presentInSet.test(VN.lookup(U->getOperand(0)));
814 lhsValid = !dependsOnInvoke(U->getOperand(0));
816 bool rhsValid = !isa<Instruction>(U->getOperand(1));
817 rhsValid |= presentInSet.test(VN.lookup(U->getOperand(1)));
819 rhsValid = !dependsOnInvoke(U->getOperand(1));
821 bool thirdValid = !isa<Instruction>(U->getOperand(2));
822 thirdValid |= presentInSet.test(VN.lookup(U->getOperand(2)));
824 thirdValid = !dependsOnInvoke(U->getOperand(2));
826 if (!lhsValid || !rhsValid || !thirdValid) {
828 presentInSet.flip(VN.lookup(U));
834 /// topo_sort - Given a set of values, sort them by topological
835 /// order into the provided vector.
836 void GVNPRE::topo_sort(SmallPtrSet<Value*, 16>& set, std::vector<Value*>& vec) {
837 SmallPtrSet<Value*, 16> visited;
838 std::vector<Value*> stack;
839 for (SmallPtrSet<Value*, 16>::iterator I = set.begin(), E = set.end();
841 if (visited.count(*I) == 0)
844 while (!stack.empty()) {
845 Value* e = stack.back();
848 if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
849 isa<ExtractElementInst>(e)) {
850 User* U = cast<User>(e);
851 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
852 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
854 if (l != 0 && isa<Instruction>(l) &&
855 visited.count(l) == 0)
857 else if (r != 0 && isa<Instruction>(r) &&
858 visited.count(r) == 0)
866 // Handle ternary ops
867 } else if (isa<InsertElementInst>(e) || isa<ShuffleVectorInst>(e) ||
868 isa<SelectInst>(e)) {
869 User* U = cast<User>(e);
870 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
871 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
872 Value* m = find_leader(set, VN.lookup(U->getOperand(2)));
874 if (l != 0 && isa<Instruction>(l) &&
875 visited.count(l) == 0)
877 else if (r != 0 && isa<Instruction>(r) &&
878 visited.count(r) == 0)
880 else if (m != 0 && isa<Instruction>(m) &&
881 visited.count(m) == 0)
901 /// dump - Dump a set of values to standard error
902 void GVNPRE::dump(const SmallPtrSet<Value*, 16>& s) const {
904 for (SmallPtrSet<Value*, 16>::iterator I = s.begin(), E = s.end();
906 DOUT << "" << VN.lookup(*I) << ": ";
912 /// elimination - Phase 3 of the main algorithm. Perform full redundancy
913 /// elimination by walking the dominator tree and removing any instruction that
914 /// is dominated by another instruction with the same value number.
915 bool GVNPRE::elimination() {
916 DOUT << "\n\nPhase 3: Elimination\n\n";
918 bool changed_function = false;
920 std::vector<std::pair<Instruction*, Value*> > replace;
921 std::vector<Instruction*> erase;
923 DominatorTree& DT = getAnalysis<DominatorTree>();
925 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
926 E = df_end(DT.getRootNode()); DI != E; ++DI) {
927 BasicBlock* BB = DI->getBlock();
929 //DOUT << "Block: " << BB->getName() << "\n";
930 //dump(availableOut[BB]);
933 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
936 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI) ||
937 isa<ShuffleVectorInst>(BI) || isa<InsertElementInst>(BI) ||
938 isa<ExtractElementInst>(BI) || isa<SelectInst>(BI)) {
939 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
942 if (Instruction* Instr = dyn_cast<Instruction>(leader))
943 if (Instr->getParent() != 0 && Instr != BI) {
944 replace.push_back(std::make_pair(BI, leader));
952 while (!replace.empty()) {
953 std::pair<Instruction*, Value*> rep = replace.back();
955 rep.first->replaceAllUsesWith(rep.second);
956 changed_function = true;
959 for (std::vector<Instruction*>::iterator I = erase.begin(), E = erase.end();
961 (*I)->eraseFromParent();
963 return changed_function;
966 /// cleanup - Delete any extraneous values that were created to represent
967 /// expressions without leaders.
968 void GVNPRE::cleanup() {
969 while (!createdExpressions.empty()) {
970 Instruction* I = createdExpressions.back();
971 createdExpressions.pop_back();
977 /// buildsets_availout - When calculating availability, handle an instruction
978 /// by inserting it into the appropriate sets
979 void GVNPRE::buildsets_availout(BasicBlock::iterator I,
980 SmallPtrSet<Value*, 16>& currAvail,
981 SmallPtrSet<PHINode*, 16>& currPhis,
982 SmallPtrSet<Value*, 16>& currExps,
983 SmallPtrSet<Value*, 16>& currTemps,
984 BitVector& availNumbers,
985 BitVector& expNumbers) {
987 if (PHINode* p = dyn_cast<PHINode>(I)) {
989 expNumbers.resize(VN.size());
990 availNumbers.resize(VN.size());
995 } else if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
996 isa<ExtractElementInst>(I)) {
997 User* U = cast<User>(I);
998 Value* leftValue = U->getOperand(0);
999 Value* rightValue = U->getOperand(1);
1001 unsigned num = VN.lookup_or_add(U);
1002 expNumbers.resize(VN.size());
1003 availNumbers.resize(VN.size());
1005 if (isa<Instruction>(leftValue))
1006 if (!expNumbers.test(VN.lookup(leftValue))) {
1007 currExps.insert(leftValue);
1008 expNumbers.set(VN.lookup(leftValue));
1011 if (isa<Instruction>(rightValue))
1012 if (!expNumbers.test(VN.lookup(rightValue))) {
1013 currExps.insert(rightValue);
1014 expNumbers.set(VN.lookup(rightValue));
1017 if (!expNumbers.test(VN.lookup(U))) {
1019 expNumbers.set(num);
1022 // Handle ternary ops
1023 } else if (isa<InsertElementInst>(I) || isa<ShuffleVectorInst>(I) ||
1024 isa<SelectInst>(I)) {
1025 User* U = cast<User>(I);
1026 Value* leftValue = U->getOperand(0);
1027 Value* rightValue = U->getOperand(1);
1028 Value* thirdValue = U->getOperand(2);
1030 VN.lookup_or_add(U);
1032 unsigned num = VN.lookup_or_add(U);
1033 expNumbers.resize(VN.size());
1034 availNumbers.resize(VN.size());
1036 if (isa<Instruction>(leftValue))
1037 if (!expNumbers.test(VN.lookup(leftValue))) {
1038 currExps.insert(leftValue);
1039 expNumbers.set(VN.lookup(leftValue));
1041 if (isa<Instruction>(rightValue))
1042 if (!expNumbers.test(VN.lookup(rightValue))) {
1043 currExps.insert(rightValue);
1044 expNumbers.set(VN.lookup(rightValue));
1046 if (isa<Instruction>(thirdValue))
1047 if (!expNumbers.test(VN.lookup(thirdValue))) {
1048 currExps.insert(thirdValue);
1049 expNumbers.set(VN.lookup(thirdValue));
1052 if (!expNumbers.test(VN.lookup(U))) {
1054 expNumbers.set(num);
1057 // Handle opaque ops
1058 } else if (!I->isTerminator()){
1059 VN.lookup_or_add(I);
1060 expNumbers.resize(VN.size());
1061 availNumbers.resize(VN.size());
1063 currTemps.insert(I);
1066 if (!I->isTerminator())
1067 if (!availNumbers.test(VN.lookup(I))) {
1068 currAvail.insert(I);
1069 availNumbers.set(VN.lookup(I));
1073 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
1074 /// set as a function of the ANTIC_IN set of the block's predecessors
1075 bool GVNPRE::buildsets_anticout(BasicBlock* BB,
1076 SmallPtrSet<Value*, 16>& anticOut,
1077 std::set<BasicBlock*>& visited) {
1078 if (BB->getTerminator()->getNumSuccessors() == 1) {
1079 if (BB->getTerminator()->getSuccessor(0) != BB &&
1080 visited.count(BB->getTerminator()->getSuccessor(0)) == 0) {
1081 DOUT << "DEFER: " << BB->getName() << "\n";
1085 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
1086 BB, BB->getTerminator()->getSuccessor(0), anticOut);
1088 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
1089 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
1090 anticOut.insert(anticipatedIn[first].begin(), anticipatedIn[first].end());
1092 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
1093 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
1094 SmallPtrSet<Value*, 16>& succAnticIn = anticipatedIn[currSucc];
1096 std::vector<Value*> temp;
1098 for (SmallPtrSet<Value*, 16>::iterator I = anticOut.begin(),
1099 E = anticOut.end(); I != E; ++I)
1100 if (succAnticIn.count(*I) == 0)
1103 for (std::vector<Value*>::iterator I = temp.begin(), E = temp.end();
1112 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
1113 /// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN
1114 /// sets populated in buildsets_availout
1115 unsigned GVNPRE::buildsets_anticin(BasicBlock* BB,
1116 SmallPtrSet<Value*, 16>& anticOut,
1117 SmallPtrSet<Value*, 16>& currExps,
1118 SmallPtrSet<Value*, 16>& currTemps,
1119 std::set<BasicBlock*>& visited) {
1120 SmallPtrSet<Value*, 16>& anticIn = anticipatedIn[BB];
1121 unsigned old = anticIn.size();
1123 bool defer = buildsets_anticout(BB, anticOut, visited);
1129 BitVector numbers(VN.size());
1130 for (SmallPtrSet<Value*, 16>::iterator I = anticOut.begin(),
1131 E = anticOut.end(); I != E; ++I) {
1132 unsigned num = VN.lookup_or_add(*I);
1133 numbers.resize(VN.size());
1135 if (isa<Instruction>(*I)) {
1140 for (SmallPtrSet<Value*, 16>::iterator I = currExps.begin(),
1141 E = currExps.end(); I != E; ++I) {
1142 if (!numbers.test(VN.lookup_or_add(*I))) {
1144 numbers.set(VN.lookup(*I));
1148 for (SmallPtrSet<Value*, 16>::iterator I = currTemps.begin(),
1149 E = currTemps.end(); I != E; ++I) {
1151 numbers.flip(VN.lookup(*I));
1154 clean(anticIn, numbers);
1157 if (old != anticIn.size())
1163 /// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT
1164 /// and the ANTIC_IN sets.
1165 void GVNPRE::buildsets(Function& F) {
1166 std::map<BasicBlock*, SmallPtrSet<Value*, 16> > generatedExpressions;
1167 std::map<BasicBlock*, SmallPtrSet<PHINode*, 16> > generatedPhis;
1168 std::map<BasicBlock*, SmallPtrSet<Value*, 16> > generatedTemporaries;
1170 DominatorTree &DT = getAnalysis<DominatorTree>();
1172 // Phase 1, Part 1: calculate AVAIL_OUT
1174 // Top-down walk of the dominator tree
1175 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1176 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1178 // Get the sets to update for this block
1179 SmallPtrSet<Value*, 16>& currExps = generatedExpressions[DI->getBlock()];
1180 SmallPtrSet<PHINode*, 16>& currPhis = generatedPhis[DI->getBlock()];
1181 SmallPtrSet<Value*, 16>& currTemps = generatedTemporaries[DI->getBlock()];
1182 SmallPtrSet<Value*, 16>& currAvail = availableOut[DI->getBlock()];
1184 BasicBlock* BB = DI->getBlock();
1186 // A block inherits AVAIL_OUT from its dominator
1187 if (DI->getIDom() != 0)
1188 currAvail.insert(availableOut[DI->getIDom()->getBlock()].begin(),
1189 availableOut[DI->getIDom()->getBlock()].end());
1191 BitVector availNumbers(VN.size());
1192 for (SmallPtrSet<Value*, 16>::iterator I = currAvail.begin(),
1193 E = currAvail.end(); I != E; ++I)
1194 availNumbers.set(VN.lookup(*I));
1196 BitVector expNumbers(VN.size());
1197 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1199 buildsets_availout(BI, currAvail, currPhis, currExps,
1200 currTemps, availNumbers, expNumbers);
1204 // Phase 1, Part 2: calculate ANTIC_IN
1206 std::set<BasicBlock*> visited;
1207 SmallPtrSet<BasicBlock*, 4> block_changed;
1208 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
1209 block_changed.insert(FI);
1211 bool changed = true;
1212 unsigned iterations = 0;
1216 SmallPtrSet<Value*, 16> anticOut;
1218 // Postorder walk of the CFG
1219 for (po_iterator<BasicBlock*> BBI = po_begin(&F.getEntryBlock()),
1220 BBE = po_end(&F.getEntryBlock()); BBI != BBE; ++BBI) {
1221 BasicBlock* BB = *BBI;
1223 if (block_changed.count(BB) != 0) {
1224 unsigned ret = buildsets_anticin(BB, anticOut,generatedExpressions[BB],
1225 generatedTemporaries[BB], visited);
1234 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1236 block_changed.insert(*PI);
1239 block_changed.erase(BB);
1241 changed |= (ret == 2);
1249 DOUT << "ITERATIONS: " << iterations << "\n";
1252 /// insertion_pre - When a partial redundancy has been identified, eliminate it
1253 /// by inserting appropriate values into the predecessors and a phi node in
1255 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
1256 std::map<BasicBlock*, Value*>& avail,
1257 SmallPtrSet<Value*, 16>& new_set) {
1258 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1259 Value* e2 = avail[*PI];
1260 if (!find_leader(availableOut[*PI], VN.lookup(e2))) {
1261 User* U = cast<User>(e2);
1264 if (isa<BinaryOperator>(U->getOperand(0)) ||
1265 isa<CmpInst>(U->getOperand(0)) ||
1266 isa<ShuffleVectorInst>(U->getOperand(0)) ||
1267 isa<ExtractElementInst>(U->getOperand(0)) ||
1268 isa<InsertElementInst>(U->getOperand(0)) ||
1269 isa<SelectInst>(U->getOperand(0)))
1270 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1272 s1 = U->getOperand(0);
1275 if (isa<BinaryOperator>(U->getOperand(1)) ||
1276 isa<CmpInst>(U->getOperand(1)) ||
1277 isa<ShuffleVectorInst>(U->getOperand(1)) ||
1278 isa<ExtractElementInst>(U->getOperand(1)) ||
1279 isa<InsertElementInst>(U->getOperand(1)) ||
1280 isa<SelectInst>(U->getOperand(1)))
1281 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1283 s2 = U->getOperand(1);
1285 // Ternary Operators
1287 if (isa<ShuffleVectorInst>(U) ||
1288 isa<InsertElementInst>(U) ||
1290 if (isa<BinaryOperator>(U->getOperand(2)) ||
1291 isa<CmpInst>(U->getOperand(2)) ||
1292 isa<ShuffleVectorInst>(U->getOperand(2)) ||
1293 isa<ExtractElementInst>(U->getOperand(2)) ||
1294 isa<InsertElementInst>(U->getOperand(2)) ||
1295 isa<SelectInst>(U->getOperand(2)))
1296 s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2)));
1298 s3 = U->getOperand(2);
1301 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1302 newVal = BinaryOperator::create(BO->getOpcode(), s1, s2,
1303 BO->getName()+".gvnpre",
1304 (*PI)->getTerminator());
1305 else if (CmpInst* C = dyn_cast<CmpInst>(U))
1306 newVal = CmpInst::create(C->getOpcode(), C->getPredicate(), s1, s2,
1307 C->getName()+".gvnpre",
1308 (*PI)->getTerminator());
1309 else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
1310 newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre",
1311 (*PI)->getTerminator());
1312 else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U))
1313 newVal = new InsertElementInst(s1, s2, s3, S->getName()+".gvnpre",
1314 (*PI)->getTerminator());
1315 else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U))
1316 newVal = new ExtractElementInst(s1, s2, S->getName()+".gvnpre",
1317 (*PI)->getTerminator());
1318 else if (SelectInst* S = dyn_cast<SelectInst>(U))
1319 newVal = new SelectInst(S->getCondition(), S->getTrueValue(),
1320 S->getFalseValue(), S->getName()+".gvnpre",
1321 (*PI)->getTerminator());
1324 VN.add(newVal, VN.lookup(U));
1326 SmallPtrSet<Value*, 16>& predAvail = availableOut[*PI];
1327 val_replace(predAvail, newVal);
1329 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1330 if (av != avail.end())
1332 avail.insert(std::make_pair(*PI, newVal));
1340 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1342 p = new PHINode(avail[*PI]->getType(), "gvnpre-join", BB->begin());
1344 p->addIncoming(avail[*PI], *PI);
1347 VN.add(p, VN.lookup(e));
1348 val_replace(availableOut[BB], p);
1354 /// insertion_mergepoint - When walking the dom tree, check at each merge
1355 /// block for the possibility of a partial redundancy. If present, eliminate it
1356 unsigned GVNPRE::insertion_mergepoint(std::vector<Value*>& workList,
1357 df_iterator<DomTreeNode*>& D,
1358 SmallPtrSet<Value*, 16>& new_set) {
1359 bool changed_function = false;
1360 bool new_stuff = false;
1362 BasicBlock* BB = D->getBlock();
1363 for (unsigned i = 0; i < workList.size(); ++i) {
1364 Value* e = workList[i];
1366 if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1367 isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) ||
1368 isa<ShuffleVectorInst>(e) || isa<SelectInst>(e)) {
1369 if (find_leader(availableOut[D->getIDom()->getBlock()],
1373 std::map<BasicBlock*, Value*> avail;
1374 bool by_some = false;
1377 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1379 Value *e2 = phi_translate(e, *PI, BB);
1380 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1383 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1384 if (av != avail.end())
1386 avail.insert(std::make_pair(*PI, e2));
1388 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1389 if (av != avail.end())
1391 avail.insert(std::make_pair(*PI, e3));
1398 if (by_some && num_avail < std::distance(pred_begin(BB), pred_end(BB))) {
1399 insertion_pre(e, BB, avail, new_set);
1401 changed_function = true;
1407 unsigned retval = 0;
1408 if (changed_function)
1416 /// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for
1417 /// merge points. When one is found, check for a partial redundancy. If one is
1418 /// present, eliminate it. Repeat this walk until no changes are made.
1419 bool GVNPRE::insertion(Function& F) {
1420 bool changed_function = false;
1422 DominatorTree &DT = getAnalysis<DominatorTree>();
1424 std::map<BasicBlock*, SmallPtrSet<Value*, 16> > new_sets;
1425 bool new_stuff = true;
1428 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1429 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1430 BasicBlock* BB = DI->getBlock();
1435 SmallPtrSet<Value*, 16>& new_set = new_sets[BB];
1436 SmallPtrSet<Value*, 16>& availOut = availableOut[BB];
1437 SmallPtrSet<Value*, 16>& anticIn = anticipatedIn[BB];
1441 // Replace leaders with leaders inherited from dominator
1442 if (DI->getIDom() != 0) {
1443 SmallPtrSet<Value*, 16>& dom_set = new_sets[DI->getIDom()->getBlock()];
1444 for (SmallPtrSet<Value*, 16>::iterator I = dom_set.begin(),
1445 E = dom_set.end(); I != E; ++I) {
1447 val_replace(availOut, *I);
1451 // If there is more than one predecessor...
1452 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
1453 std::vector<Value*> workList;
1454 workList.reserve(anticIn.size());
1455 topo_sort(anticIn, workList);
1457 unsigned result = insertion_mergepoint(workList, DI, new_set);
1459 changed_function = true;
1466 return changed_function;
1469 // GVNPRE::runOnFunction - This is the main transformation entry point for a
1472 bool GVNPRE::runOnFunction(Function &F) {
1473 // Clean out global sets from any previous functions
1475 createdExpressions.clear();
1476 availableOut.clear();
1477 anticipatedIn.clear();
1479 bool changed_function = false;
1481 // Phase 1: BuildSets
1482 // This phase calculates the AVAIL_OUT and ANTIC_IN sets
1485 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
1486 DOUT << "AVAIL_OUT: " << FI->getName() << "\n";
1487 dump(availableOut[FI]);
1489 DOUT << "ANTIC_IN: " << FI->getName() << "\n";
1490 dump(anticipatedIn[FI]);
1495 // This phase inserts values to make partially redundant values
1497 changed_function |= insertion(F);
1499 // Phase 3: Eliminate
1500 // This phase performs trivial full redundancy elimination
1501 changed_function |= elimination();
1504 // This phase cleans up values that were created solely
1505 // as leaders for expressions
1508 return changed_function;