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/Analysis/Dominators.h"
27 #include "llvm/Analysis/PostDominators.h"
28 #include "llvm/ADT/DepthFirstIterator.h"
29 #include "llvm/ADT/Statistic.h"
30 #include "llvm/Support/CFG.h"
31 #include "llvm/Support/Compiler.h"
32 #include "llvm/Support/Debug.h"
40 //===----------------------------------------------------------------------===//
42 //===----------------------------------------------------------------------===//
44 /// This class holds the mapping between values and value numbers.
47 class VISIBILITY_HIDDEN ValueTable {
50 enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
51 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
52 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
53 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
54 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
55 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
56 FCMPULT, FCMPULE, FCMPUNE };
58 ExpressionOpcode opcode;
62 bool operator< (const Expression& other) const {
63 if (opcode < other.opcode)
65 else if (opcode > other.opcode)
67 else if (leftVN < other.leftVN)
69 else if (leftVN > other.leftVN)
71 else if (rightVN < other.rightVN)
73 else if (rightVN > other.rightVN)
81 std::map<Value*, uint32_t> valueNumbering;
82 std::map<Expression, uint32_t> expressionNumbering;
84 std::set<Expression> maximalExpressions;
85 std::set<Value*> maximalValues;
87 uint32_t nextValueNumber;
89 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
90 Expression::ExpressionOpcode getOpcode(CmpInst* C);
92 ValueTable() { nextValueNumber = 1; }
93 uint32_t lookup_or_add(Value* V);
94 uint32_t lookup(Value* V);
95 void add(Value* V, uint32_t num);
97 std::set<Expression>& getMaximalExpressions() {
98 return maximalExpressions;
101 std::set<Value*>& getMaximalValues() { return maximalValues; }
102 Expression create_expression(BinaryOperator* BO);
103 Expression create_expression(CmpInst* C);
107 ValueTable::Expression::ExpressionOpcode
108 ValueTable::getOpcode(BinaryOperator* BO) {
109 switch(BO->getOpcode()) {
110 case Instruction::Add:
111 return Expression::ADD;
112 case Instruction::Sub:
113 return Expression::SUB;
114 case Instruction::Mul:
115 return Expression::MUL;
116 case Instruction::UDiv:
117 return Expression::UDIV;
118 case Instruction::SDiv:
119 return Expression::SDIV;
120 case Instruction::FDiv:
121 return Expression::FDIV;
122 case Instruction::URem:
123 return Expression::UREM;
124 case Instruction::SRem:
125 return Expression::SREM;
126 case Instruction::FRem:
127 return Expression::FREM;
128 case Instruction::Shl:
129 return Expression::SHL;
130 case Instruction::LShr:
131 return Expression::LSHR;
132 case Instruction::AShr:
133 return Expression::ASHR;
134 case Instruction::And:
135 return Expression::AND;
136 case Instruction::Or:
137 return Expression::OR;
138 case Instruction::Xor:
139 return Expression::XOR;
141 // THIS SHOULD NEVER HAPPEN
143 assert(0 && "Binary operator with unknown opcode?");
144 return Expression::ADD;
148 ValueTable::Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
149 if (C->getOpcode() == Instruction::ICmp) {
150 switch (C->getPredicate()) {
151 case ICmpInst::ICMP_EQ:
152 return Expression::ICMPEQ;
153 case ICmpInst::ICMP_NE:
154 return Expression::ICMPNE;
155 case ICmpInst::ICMP_UGT:
156 return Expression::ICMPUGT;
157 case ICmpInst::ICMP_UGE:
158 return Expression::ICMPUGE;
159 case ICmpInst::ICMP_ULT:
160 return Expression::ICMPULT;
161 case ICmpInst::ICMP_ULE:
162 return Expression::ICMPULE;
163 case ICmpInst::ICMP_SGT:
164 return Expression::ICMPSGT;
165 case ICmpInst::ICMP_SGE:
166 return Expression::ICMPSGE;
167 case ICmpInst::ICMP_SLT:
168 return Expression::ICMPSLT;
169 case ICmpInst::ICMP_SLE:
170 return Expression::ICMPSLE;
172 // THIS SHOULD NEVER HAPPEN
174 assert(0 && "Comparison with unknown predicate?");
175 return Expression::ICMPEQ;
178 switch (C->getPredicate()) {
179 case FCmpInst::FCMP_OEQ:
180 return Expression::FCMPOEQ;
181 case FCmpInst::FCMP_OGT:
182 return Expression::FCMPOGT;
183 case FCmpInst::FCMP_OGE:
184 return Expression::FCMPOGE;
185 case FCmpInst::FCMP_OLT:
186 return Expression::FCMPOLT;
187 case FCmpInst::FCMP_OLE:
188 return Expression::FCMPOLE;
189 case FCmpInst::FCMP_ONE:
190 return Expression::FCMPONE;
191 case FCmpInst::FCMP_ORD:
192 return Expression::FCMPORD;
193 case FCmpInst::FCMP_UNO:
194 return Expression::FCMPUNO;
195 case FCmpInst::FCMP_UEQ:
196 return Expression::FCMPUEQ;
197 case FCmpInst::FCMP_UGT:
198 return Expression::FCMPUGT;
199 case FCmpInst::FCMP_UGE:
200 return Expression::FCMPUGE;
201 case FCmpInst::FCMP_ULT:
202 return Expression::FCMPULT;
203 case FCmpInst::FCMP_ULE:
204 return Expression::FCMPULE;
205 case FCmpInst::FCMP_UNE:
206 return Expression::FCMPUNE;
208 // THIS SHOULD NEVER HAPPEN
210 assert(0 && "Comparison with unknown predicate?");
211 return Expression::FCMPOEQ;
216 uint32_t ValueTable::lookup_or_add(Value* V) {
217 maximalValues.insert(V);
219 std::map<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
220 if (VI != valueNumbering.end())
224 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
225 Expression e = create_expression(BO);
227 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
228 if (EI != expressionNumbering.end()) {
229 valueNumbering.insert(std::make_pair(V, EI->second));
232 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
233 valueNumbering.insert(std::make_pair(V, nextValueNumber));
235 return nextValueNumber++;
237 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
238 Expression e = create_expression(C);
240 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
241 if (EI != expressionNumbering.end()) {
242 valueNumbering.insert(std::make_pair(V, EI->second));
245 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
246 valueNumbering.insert(std::make_pair(V, nextValueNumber));
248 return nextValueNumber++;
251 valueNumbering.insert(std::make_pair(V, nextValueNumber));
252 return nextValueNumber++;
256 uint32_t ValueTable::lookup(Value* V) {
257 std::map<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
258 if (VI != valueNumbering.end())
261 assert(0 && "Value not numbered?");
266 void ValueTable::add(Value* V, uint32_t num) {
267 std::map<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
268 if (VI != valueNumbering.end())
269 valueNumbering.erase(VI);
270 valueNumbering.insert(std::make_pair(V, num));
273 ValueTable::Expression ValueTable::create_expression(BinaryOperator* BO) {
276 e.leftVN = lookup_or_add(BO->getOperand(0));
277 e.rightVN = lookup_or_add(BO->getOperand(1));
278 e.opcode = getOpcode(BO);
280 maximalExpressions.insert(e);
285 ValueTable::Expression ValueTable::create_expression(CmpInst* C) {
288 e.leftVN = lookup_or_add(C->getOperand(0));
289 e.rightVN = lookup_or_add(C->getOperand(1));
290 e.opcode = getOpcode(C);
292 maximalExpressions.insert(e);
297 void ValueTable::clear() {
298 valueNumbering.clear();
299 expressionNumbering.clear();
305 class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
306 bool runOnFunction(Function &F);
308 static char ID; // Pass identification, replacement for typeid
309 GVNPRE() : FunctionPass((intptr_t)&ID) { nextValueNumber = 1; }
312 uint32_t nextValueNumber;
314 std::vector<Instruction*> createdExpressions;
316 std::map<BasicBlock*, std::set<Value*> > availableOut;
317 std::map<BasicBlock*, std::set<Value*> > anticipatedIn;
318 std::map<User*, bool> invokeDep;
320 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
321 AU.setPreservesCFG();
322 AU.addRequired<DominatorTree>();
323 AU.addRequired<PostDominatorTree>();
327 // FIXME: eliminate or document these better
328 void dump(const std::set<Value*>& s) const;
329 void dump_unique(const std::set<Value*>& s) const;
330 void clean(std::set<Value*>& set);
331 Value* find_leader(std::set<Value*>& vals,
333 Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ);
334 void phi_translate_set(std::set<Value*>& anticIn, BasicBlock* pred,
335 BasicBlock* succ, std::set<Value*>& out);
337 void topo_sort(std::set<Value*>& set,
338 std::vector<Value*>& vec);
340 // For a given block, calculate the generated expressions, temporaries,
341 // and the AVAIL_OUT set
345 void val_insert(std::set<Value*>& s, Value* v);
346 void val_replace(std::set<Value*>& s, Value* v);
347 bool dependsOnInvoke(Value* V);
355 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
357 RegisterPass<GVNPRE> X("gvnpre",
358 "Global Value Numbering/Partial Redundancy Elimination");
361 STATISTIC(NumInsertedVals, "Number of values inserted");
362 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
363 STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
365 Value* GVNPRE::find_leader(std::set<Value*>& vals, uint32_t v) {
366 for (std::set<Value*>::iterator I = vals.begin(), E = vals.end();
368 if (v == VN.lookup(*I))
374 void GVNPRE::val_insert(std::set<Value*>& s, Value* v) {
375 uint32_t num = VN.lookup(v);
376 Value* leader = find_leader(s, num);
381 void GVNPRE::val_replace(std::set<Value*>& s, Value* v) {
382 uint32_t num = VN.lookup(v);
383 Value* leader = find_leader(s, num);
384 while (leader != 0) {
386 leader = find_leader(s, num);
391 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
395 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
397 if (isa<Instruction>(BO->getOperand(0)))
398 newOp1 = phi_translate(find_leader(anticipatedIn[succ],
399 VN.lookup(BO->getOperand(0))),
402 newOp1 = BO->getOperand(0);
408 if (isa<Instruction>(BO->getOperand(1)))
409 newOp2 = phi_translate(find_leader(anticipatedIn[succ],
410 VN.lookup(BO->getOperand(1))),
413 newOp2 = BO->getOperand(1);
418 if (newOp1 != BO->getOperand(0) || newOp2 != BO->getOperand(1)) {
419 Instruction* newVal = BinaryOperator::create(BO->getOpcode(),
421 BO->getName()+".gvnpre");
423 uint32_t v = VN.lookup_or_add(newVal);
425 Value* leader = find_leader(availableOut[pred], v);
427 createdExpressions.push_back(newVal);
434 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
435 if (P->getParent() == succ)
436 return P->getIncomingValueForBlock(pred);
437 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
439 if (isa<Instruction>(C->getOperand(0)))
440 newOp1 = phi_translate(find_leader(anticipatedIn[succ],
441 VN.lookup(C->getOperand(0))),
444 newOp1 = C->getOperand(0);
450 if (isa<Instruction>(C->getOperand(1)))
451 newOp2 = phi_translate(find_leader(anticipatedIn[succ],
452 VN.lookup(C->getOperand(1))),
455 newOp2 = C->getOperand(1);
460 if (newOp1 != C->getOperand(0) || newOp2 != C->getOperand(1)) {
461 Instruction* newVal = CmpInst::create(C->getOpcode(),
464 C->getName()+".gvnpre");
466 uint32_t v = VN.lookup_or_add(newVal);
468 Value* leader = find_leader(availableOut[pred], v);
470 createdExpressions.push_back(newVal);
482 void GVNPRE::phi_translate_set(std::set<Value*>& anticIn,
483 BasicBlock* pred, BasicBlock* succ,
484 std::set<Value*>& out) {
485 for (std::set<Value*>::iterator I = anticIn.begin(),
486 E = anticIn.end(); I != E; ++I) {
487 Value* V = phi_translate(*I, pred, succ);
493 bool GVNPRE::dependsOnInvoke(Value* V) {
497 User* U = cast<User>(V);
498 std::map<User*, bool>::iterator I = invokeDep.find(U);
499 if (I != invokeDep.end())
502 std::vector<Value*> worklist(U->op_begin(), U->op_end());
503 std::set<Value*> visited;
505 while (!worklist.empty()) {
506 Value* current = worklist.back();
508 visited.insert(current);
510 if (!isa<User>(current))
512 else if (isa<InvokeInst>(current))
515 User* curr = cast<User>(current);
516 std::map<User*, bool>::iterator CI = invokeDep.find(curr);
517 if (CI != invokeDep.end()) {
521 for (unsigned i = 0; i < curr->getNumOperands(); ++i)
522 if (visited.find(curr->getOperand(i)) == visited.end())
523 worklist.push_back(curr->getOperand(i));
530 // Remove all expressions whose operands are not themselves in the set
531 void GVNPRE::clean(std::set<Value*>& set) {
532 std::vector<Value*> worklist;
533 topo_sort(set, worklist);
535 for (unsigned i = 0; i < worklist.size(); ++i) {
536 Value* v = worklist[i];
538 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(v)) {
539 bool lhsValid = !isa<Instruction>(BO->getOperand(0));
541 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
543 if (VN.lookup(*I) == VN.lookup(BO->getOperand(0))) {
548 // Check for dependency on invoke insts
549 // NOTE: This check is expensive, so don't do it if we
552 lhsValid = !dependsOnInvoke(BO->getOperand(0));
554 bool rhsValid = !isa<Instruction>(BO->getOperand(1));
556 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
558 if (VN.lookup(*I) == VN.lookup(BO->getOperand(1))) {
563 // Check for dependency on invoke insts
564 // NOTE: This check is expensive, so don't do it if we
567 rhsValid = !dependsOnInvoke(BO->getOperand(1));
569 if (!lhsValid || !rhsValid)
571 } else if (CmpInst* C = dyn_cast<CmpInst>(v)) {
572 bool lhsValid = !isa<Instruction>(C->getOperand(0));
574 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
576 if (VN.lookup(*I) == VN.lookup(C->getOperand(0))) {
580 lhsValid &= !dependsOnInvoke(C->getOperand(0));
582 bool rhsValid = !isa<Instruction>(C->getOperand(1));
584 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
586 if (VN.lookup(*I) == VN.lookup(C->getOperand(1))) {
590 rhsValid &= !dependsOnInvoke(C->getOperand(1));
592 if (!lhsValid || !rhsValid)
598 void GVNPRE::topo_sort(std::set<Value*>& set,
599 std::vector<Value*>& vec) {
600 std::set<Value*> toErase;
601 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
603 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(*I))
604 for (std::set<Value*>::iterator SI = set.begin(); SI != E; ++SI) {
605 if (VN.lookup(BO->getOperand(0)) == VN.lookup(*SI) ||
606 VN.lookup(BO->getOperand(1)) == VN.lookup(*SI)) {
610 else if (CmpInst* C = dyn_cast<CmpInst>(*I))
611 for (std::set<Value*>::iterator SI = set.begin(); SI != E; ++SI) {
612 if (VN.lookup(C->getOperand(0)) == VN.lookup(*SI) ||
613 VN.lookup(C->getOperand(1)) == VN.lookup(*SI)) {
619 std::vector<Value*> Q;
620 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
622 if (toErase.find(*I) == toErase.end())
626 std::set<Value*> visited;
630 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(e)) {
631 Value* l = find_leader(set, VN.lookup(BO->getOperand(0)));
632 Value* r = find_leader(set, VN.lookup(BO->getOperand(1)));
634 if (l != 0 && isa<Instruction>(l) &&
635 visited.find(l) == visited.end())
637 else if (r != 0 && isa<Instruction>(r) &&
638 visited.find(r) == visited.end())
645 } else if (CmpInst* C = dyn_cast<CmpInst>(e)) {
646 Value* l = find_leader(set, VN.lookup(C->getOperand(0)));
647 Value* r = find_leader(set, VN.lookup(C->getOperand(1)));
649 if (l != 0 && isa<Instruction>(l) &&
650 visited.find(l) == visited.end())
652 else if (r != 0 && isa<Instruction>(r) &&
653 visited.find(r) == visited.end())
669 void GVNPRE::dump(const std::set<Value*>& s) const {
671 for (std::set<Value*>::iterator I = s.begin(), E = s.end();
678 void GVNPRE::dump_unique(const std::set<Value*>& s) const {
680 for (std::set<Value*>::iterator I = s.begin(), E = s.end();
687 void GVNPRE::elimination() {
688 DOUT << "\n\nPhase 3: Elimination\n\n";
690 std::vector<std::pair<Instruction*, Value*> > replace;
691 std::vector<Instruction*> erase;
693 DominatorTree& DT = getAnalysis<DominatorTree>();
695 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
696 E = df_end(DT.getRootNode()); DI != E; ++DI) {
697 BasicBlock* BB = DI->getBlock();
699 DOUT << "Block: " << BB->getName() << "\n";
700 dump_unique(availableOut[BB]);
703 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
706 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI)) {
707 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
710 if (Instruction* Instr = dyn_cast<Instruction>(leader))
711 if (Instr->getParent() != 0 && Instr != BI) {
712 replace.push_back(std::make_pair(BI, leader));
720 while (!replace.empty()) {
721 std::pair<Instruction*, Value*> rep = replace.back();
723 rep.first->replaceAllUsesWith(rep.second);
726 for (std::vector<Instruction*>::iterator I = erase.begin(), E = erase.end();
728 (*I)->eraseFromParent();
732 void GVNPRE::cleanup() {
733 while (!createdExpressions.empty()) {
734 Instruction* I = createdExpressions.back();
735 createdExpressions.pop_back();
741 bool GVNPRE::runOnFunction(Function &F) {
743 createdExpressions.clear();
744 availableOut.clear();
745 anticipatedIn.clear();
748 std::map<BasicBlock*, std::set<Value*> > generatedExpressions;
749 std::map<BasicBlock*, std::set<PHINode*> > generatedPhis;
750 std::map<BasicBlock*, std::set<Value*> > generatedTemporaries;
753 DominatorTree &DT = getAnalysis<DominatorTree>();
755 // Phase 1: BuildSets
757 // Phase 1, Part 1: calculate AVAIL_OUT
759 // Top-down walk of the dominator tree
760 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
761 E = df_end(DT.getRootNode()); DI != E; ++DI) {
763 // Get the sets to update for this block
764 std::set<Value*>& currExps = generatedExpressions[DI->getBlock()];
765 std::set<PHINode*>& currPhis = generatedPhis[DI->getBlock()];
766 std::set<Value*>& currTemps = generatedTemporaries[DI->getBlock()];
767 std::set<Value*>& currAvail = availableOut[DI->getBlock()];
769 BasicBlock* BB = DI->getBlock();
771 // A block inherits AVAIL_OUT from its dominator
772 if (DI->getIDom() != 0)
773 currAvail.insert(availableOut[DI->getIDom()->getBlock()].begin(),
774 availableOut[DI->getIDom()->getBlock()].end());
777 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
780 // Handle PHI nodes...
781 if (PHINode* p = dyn_cast<PHINode>(BI)) {
785 // Handle binary ops...
786 } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(BI)) {
787 Value* leftValue = BO->getOperand(0);
788 Value* rightValue = BO->getOperand(1);
790 VN.lookup_or_add(BO);
792 if (isa<Instruction>(leftValue))
793 val_insert(currExps, leftValue);
794 if (isa<Instruction>(rightValue))
795 val_insert(currExps, rightValue);
796 val_insert(currExps, BO);
799 } else if (CmpInst* C = dyn_cast<CmpInst>(BI)) {
800 Value* leftValue = C->getOperand(0);
801 Value* rightValue = C->getOperand(1);
805 if (isa<Instruction>(leftValue))
806 val_insert(currExps, leftValue);
807 if (isa<Instruction>(rightValue))
808 val_insert(currExps, rightValue);
809 val_insert(currExps, C);
811 // Handle unsupported ops
812 } else if (!BI->isTerminator()){
813 VN.lookup_or_add(BI);
814 currTemps.insert(BI);
817 if (!BI->isTerminator())
818 val_insert(currAvail, BI);
822 DOUT << "Maximal Set: ";
823 dump_unique(VN.getMaximalValues());
826 // If function has no exit blocks, only perform GVN
827 PostDominatorTree &PDT = getAnalysis<PostDominatorTree>();
828 if (PDT[&F.getEntryBlock()] == 0) {
836 // Phase 1, Part 2: calculate ANTIC_IN
838 std::set<BasicBlock*> visited;
841 unsigned iterations = 0;
844 std::set<Value*> anticOut;
846 // Top-down walk of the postdominator tree
847 for (df_iterator<DomTreeNode*> PDI =
848 df_begin(PDT.getRootNode()), E = df_end(PDT.getRootNode());
850 BasicBlock* BB = PDI->getBlock();
854 DOUT << "Block: " << BB->getName() << "\n";
856 dump(generatedTemporaries[BB]);
860 dump_unique(generatedExpressions[BB]);
863 std::set<Value*>& anticIn = anticipatedIn[BB];
864 std::set<Value*> old (anticIn.begin(), anticIn.end());
866 if (BB->getTerminator()->getNumSuccessors() == 1) {
867 if (visited.find(BB->getTerminator()->getSuccessor(0)) ==
869 phi_translate_set(VN.getMaximalValues(), BB,
870 BB->getTerminator()->getSuccessor(0),
873 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
874 BB, BB->getTerminator()->getSuccessor(0),
876 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
877 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
878 anticOut.insert(anticipatedIn[first].begin(),
879 anticipatedIn[first].end());
880 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
881 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
882 std::set<Value*>& succAnticIn = anticipatedIn[currSucc];
884 std::set<Value*> temp;
885 std::insert_iterator<std::set<Value*> > temp_ins(temp,
887 std::set_intersection(anticOut.begin(), anticOut.end(),
888 succAnticIn.begin(), succAnticIn.end(),
892 anticOut.insert(temp.begin(), temp.end());
896 DOUT << "ANTIC_OUT: ";
897 dump_unique(anticOut);
901 std::insert_iterator<std::set<Value*> > s_ins(S, S.begin());
902 std::set_difference(anticOut.begin(), anticOut.end(),
903 generatedTemporaries[BB].begin(),
904 generatedTemporaries[BB].end(),
908 std::insert_iterator<std::set<Value*> > ai_ins(anticIn, anticIn.begin());
909 std::set_difference(generatedExpressions[BB].begin(),
910 generatedExpressions[BB].end(),
911 generatedTemporaries[BB].begin(),
912 generatedTemporaries[BB].end(),
915 for (std::set<Value*>::iterator I = S.begin(), E = S.end();
917 if (find_leader(anticIn, VN.lookup(*I)) == 0)
918 val_insert(anticIn, *I);
923 DOUT << "ANTIC_IN: ";
924 dump_unique(anticIn);
927 if (old.size() != anticIn.size())
936 DOUT << "Iterations: " << iterations << "\n";
938 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
939 DOUT << "Name: " << I->getName().c_str() << "\n";
942 dump(generatedTemporaries[I]);
946 dump_unique(generatedExpressions[I]);
949 DOUT << "ANTIC_IN: ";
950 dump_unique(anticipatedIn[I]);
953 DOUT << "AVAIL_OUT: ";
954 dump_unique(availableOut[I]);
959 DOUT<< "\nPhase 2: Insertion\n";
961 std::map<BasicBlock*, std::set<Value*> > new_sets;
962 unsigned i_iterations = 0;
963 bool new_stuff = true;
966 DOUT << "Iteration: " << i_iterations << "\n\n";
967 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
968 E = df_end(DT.getRootNode()); DI != E; ++DI) {
969 BasicBlock* BB = DI->getBlock();
974 std::set<Value*>& new_set = new_sets[BB];
975 std::set<Value*>& availOut = availableOut[BB];
976 std::set<Value*>& anticIn = anticipatedIn[BB];
980 // Replace leaders with leaders inherited from dominator
981 if (DI->getIDom() != 0) {
982 std::set<Value*>& dom_set = new_sets[DI->getIDom()->getBlock()];
983 for (std::set<Value*>::iterator I = dom_set.begin(),
984 E = dom_set.end(); I != E; ++I) {
986 val_replace(availOut, *I);
990 // If there is more than one predecessor...
991 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
992 std::vector<Value*> workList;
993 topo_sort(anticIn, workList);
995 DOUT << "Merge Block: " << BB->getName() << "\n";
996 DOUT << "ANTIC_IN: ";
997 dump_unique(anticIn);
1000 for (unsigned i = 0; i < workList.size(); ++i) {
1001 Value* e = workList[i];
1003 if (isa<BinaryOperator>(e) || isa<CmpInst>(e)) {
1004 if (find_leader(availableOut[DI->getIDom()->getBlock()], VN.lookup(e)) != 0)
1007 std::map<BasicBlock*, Value*> avail;
1008 bool by_some = false;
1011 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1013 Value *e2 = phi_translate(e, *PI, BB);
1014 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1017 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1018 if (av != avail.end())
1020 avail.insert(std::make_pair(*PI, e2));
1022 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1023 if (av != avail.end())
1025 avail.insert(std::make_pair(*PI, e3));
1033 num_avail < std::distance(pred_begin(BB), pred_end(BB))) {
1034 DOUT << "Processing Value: ";
1038 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1040 Value* e2 = avail[*PI];
1041 if (!find_leader(availableOut[*PI], VN.lookup(e2))) {
1042 User* U = cast<User>(e2);
1045 if (isa<BinaryOperator>(U->getOperand(0)) ||
1046 isa<CmpInst>(U->getOperand(0)))
1047 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1049 s1 = U->getOperand(0);
1052 if (isa<BinaryOperator>(U->getOperand(1)) ||
1053 isa<CmpInst>(U->getOperand(1)))
1054 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1056 s2 = U->getOperand(1);
1059 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1060 newVal = BinaryOperator::create(BO->getOpcode(),
1062 BO->getName()+".gvnpre",
1063 (*PI)->getTerminator());
1064 else if (CmpInst* C = dyn_cast<CmpInst>(U))
1065 newVal = CmpInst::create(C->getOpcode(),
1068 C->getName()+".gvnpre",
1069 (*PI)->getTerminator());
1071 VN.add(newVal, VN.lookup(U));
1073 std::set<Value*>& predAvail = availableOut[*PI];
1074 val_replace(predAvail, newVal);
1076 DOUT << "Creating value: " << std::hex << newVal << std::dec << "\n";
1078 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1079 if (av != avail.end())
1081 avail.insert(std::make_pair(*PI, newVal));
1089 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1092 p = new PHINode(avail[*PI]->getType(), "gvnpre-join",
1095 p->addIncoming(avail[*PI], *PI);
1098 VN.add(p, VN.lookup(e));
1099 DOUT << "Creating value: " << std::hex << p << std::dec << "\n";
1101 val_replace(availOut, p);
1106 DOUT << "Preds After Processing: ";
1107 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1109 DEBUG((*PI)->dump());
1112 DOUT << "Merge Block After Processing: ";
1127 // Phase 3: Eliminate