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/DenseMap.h"
29 #include "llvm/ADT/DepthFirstIterator.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/Support/CFG.h"
32 #include "llvm/Support/Compiler.h"
33 #include "llvm/Support/Debug.h"
41 //===----------------------------------------------------------------------===//
43 //===----------------------------------------------------------------------===//
45 /// This class holds the mapping between values and value numbers. It is used
46 /// as an efficient mechanism to determine the expression-wise equivalence of
50 class VISIBILITY_HIDDEN ValueTable {
53 enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
54 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
55 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
56 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
57 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
58 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
59 FCMPULT, FCMPULE, FCMPUNE };
61 ExpressionOpcode opcode;
65 bool operator< (const Expression& other) const {
66 if (opcode < other.opcode)
68 else if (opcode > other.opcode)
70 else if (leftVN < other.leftVN)
72 else if (leftVN > other.leftVN)
74 else if (rightVN < other.rightVN)
76 else if (rightVN > other.rightVN)
84 DenseMap<Value*, uint32_t> valueNumbering;
85 std::map<Expression, uint32_t> expressionNumbering;
87 std::set<Expression> maximalExpressions;
88 std::set<Value*> maximalValues;
90 uint32_t nextValueNumber;
92 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
93 Expression::ExpressionOpcode getOpcode(CmpInst* C);
94 Expression create_expression(BinaryOperator* BO);
95 Expression create_expression(CmpInst* C);
97 ValueTable() { nextValueNumber = 1; }
98 uint32_t lookup_or_add(Value* V);
99 uint32_t lookup(Value* V);
100 void add(Value* V, uint32_t num);
102 std::set<Expression>& getMaximalExpressions() {
103 return maximalExpressions;
106 std::set<Value*>& getMaximalValues() { return maximalValues; }
107 void erase(Value* v);
111 //===----------------------------------------------------------------------===//
112 // ValueTable Internal Functions
113 //===----------------------------------------------------------------------===//
114 ValueTable::Expression::ExpressionOpcode
115 ValueTable::getOpcode(BinaryOperator* BO) {
116 switch(BO->getOpcode()) {
117 case Instruction::Add:
118 return Expression::ADD;
119 case Instruction::Sub:
120 return Expression::SUB;
121 case Instruction::Mul:
122 return Expression::MUL;
123 case Instruction::UDiv:
124 return Expression::UDIV;
125 case Instruction::SDiv:
126 return Expression::SDIV;
127 case Instruction::FDiv:
128 return Expression::FDIV;
129 case Instruction::URem:
130 return Expression::UREM;
131 case Instruction::SRem:
132 return Expression::SREM;
133 case Instruction::FRem:
134 return Expression::FREM;
135 case Instruction::Shl:
136 return Expression::SHL;
137 case Instruction::LShr:
138 return Expression::LSHR;
139 case Instruction::AShr:
140 return Expression::ASHR;
141 case Instruction::And:
142 return Expression::AND;
143 case Instruction::Or:
144 return Expression::OR;
145 case Instruction::Xor:
146 return Expression::XOR;
148 // THIS SHOULD NEVER HAPPEN
150 assert(0 && "Binary operator with unknown opcode?");
151 return Expression::ADD;
155 ValueTable::Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
156 if (C->getOpcode() == Instruction::ICmp) {
157 switch (C->getPredicate()) {
158 case ICmpInst::ICMP_EQ:
159 return Expression::ICMPEQ;
160 case ICmpInst::ICMP_NE:
161 return Expression::ICMPNE;
162 case ICmpInst::ICMP_UGT:
163 return Expression::ICMPUGT;
164 case ICmpInst::ICMP_UGE:
165 return Expression::ICMPUGE;
166 case ICmpInst::ICMP_ULT:
167 return Expression::ICMPULT;
168 case ICmpInst::ICMP_ULE:
169 return Expression::ICMPULE;
170 case ICmpInst::ICMP_SGT:
171 return Expression::ICMPSGT;
172 case ICmpInst::ICMP_SGE:
173 return Expression::ICMPSGE;
174 case ICmpInst::ICMP_SLT:
175 return Expression::ICMPSLT;
176 case ICmpInst::ICMP_SLE:
177 return Expression::ICMPSLE;
179 // THIS SHOULD NEVER HAPPEN
181 assert(0 && "Comparison with unknown predicate?");
182 return Expression::ICMPEQ;
185 switch (C->getPredicate()) {
186 case FCmpInst::FCMP_OEQ:
187 return Expression::FCMPOEQ;
188 case FCmpInst::FCMP_OGT:
189 return Expression::FCMPOGT;
190 case FCmpInst::FCMP_OGE:
191 return Expression::FCMPOGE;
192 case FCmpInst::FCMP_OLT:
193 return Expression::FCMPOLT;
194 case FCmpInst::FCMP_OLE:
195 return Expression::FCMPOLE;
196 case FCmpInst::FCMP_ONE:
197 return Expression::FCMPONE;
198 case FCmpInst::FCMP_ORD:
199 return Expression::FCMPORD;
200 case FCmpInst::FCMP_UNO:
201 return Expression::FCMPUNO;
202 case FCmpInst::FCMP_UEQ:
203 return Expression::FCMPUEQ;
204 case FCmpInst::FCMP_UGT:
205 return Expression::FCMPUGT;
206 case FCmpInst::FCMP_UGE:
207 return Expression::FCMPUGE;
208 case FCmpInst::FCMP_ULT:
209 return Expression::FCMPULT;
210 case FCmpInst::FCMP_ULE:
211 return Expression::FCMPULE;
212 case FCmpInst::FCMP_UNE:
213 return Expression::FCMPUNE;
215 // THIS SHOULD NEVER HAPPEN
217 assert(0 && "Comparison with unknown predicate?");
218 return Expression::FCMPOEQ;
223 ValueTable::Expression ValueTable::create_expression(BinaryOperator* BO) {
226 e.leftVN = lookup_or_add(BO->getOperand(0));
227 e.rightVN = lookup_or_add(BO->getOperand(1));
228 e.opcode = getOpcode(BO);
230 maximalExpressions.insert(e);
235 ValueTable::Expression ValueTable::create_expression(CmpInst* C) {
238 e.leftVN = lookup_or_add(C->getOperand(0));
239 e.rightVN = lookup_or_add(C->getOperand(1));
240 e.opcode = getOpcode(C);
242 maximalExpressions.insert(e);
247 //===----------------------------------------------------------------------===//
248 // ValueTable External Functions
249 //===----------------------------------------------------------------------===//
251 /// lookup_or_add - Returns the value number for the specified value, assigning
252 /// it a new number if it did not have one before.
253 uint32_t ValueTable::lookup_or_add(Value* V) {
254 maximalValues.insert(V);
256 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
257 if (VI != valueNumbering.end())
261 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
262 Expression e = create_expression(BO);
264 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
265 if (EI != expressionNumbering.end()) {
266 valueNumbering.insert(std::make_pair(V, EI->second));
269 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
270 valueNumbering.insert(std::make_pair(V, nextValueNumber));
272 return nextValueNumber++;
274 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
275 Expression e = create_expression(C);
277 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
278 if (EI != expressionNumbering.end()) {
279 valueNumbering.insert(std::make_pair(V, EI->second));
282 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
283 valueNumbering.insert(std::make_pair(V, nextValueNumber));
285 return nextValueNumber++;
288 valueNumbering.insert(std::make_pair(V, nextValueNumber));
289 return nextValueNumber++;
293 /// lookup - Returns the value number of the specified value. Fails if
294 /// the value has not yet been numbered.
295 uint32_t ValueTable::lookup(Value* V) {
296 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
297 if (VI != valueNumbering.end())
300 assert(0 && "Value not numbered?");
305 /// add - Add the specified value with the given value number, removing
306 /// its old number, if any
307 void ValueTable::add(Value* V, uint32_t num) {
308 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
309 if (VI != valueNumbering.end())
310 valueNumbering.erase(VI);
311 valueNumbering.insert(std::make_pair(V, num));
314 /// clear - Remove all entries from the ValueTable and the maximal sets
315 void ValueTable::clear() {
316 valueNumbering.clear();
317 expressionNumbering.clear();
318 maximalExpressions.clear();
319 maximalValues.clear();
323 /// erase - Remove a value from the value numbering and maximal sets
324 void ValueTable::erase(Value* V) {
325 maximalValues.erase(V);
326 valueNumbering.erase(V);
327 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V))
328 maximalExpressions.erase(create_expression(BO));
329 else if (CmpInst* C = dyn_cast<CmpInst>(V))
330 maximalExpressions.erase(create_expression(C));
333 //===----------------------------------------------------------------------===//
335 //===----------------------------------------------------------------------===//
339 class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
340 bool runOnFunction(Function &F);
342 static char ID; // Pass identification, replacement for typeid
343 GVNPRE() : FunctionPass((intptr_t)&ID) { }
347 std::vector<Instruction*> createdExpressions;
349 std::map<BasicBlock*, std::set<Value*> > availableOut;
350 std::map<BasicBlock*, std::set<Value*> > anticipatedIn;
352 // This transformation requires dominator postdominator info
353 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
354 AU.setPreservesCFG();
355 AU.addRequired<DominatorTree>();
356 AU.addRequired<PostDominatorTree>();
360 // FIXME: eliminate or document these better
361 void dump(const std::set<Value*>& s) const;
362 void clean(std::set<Value*>& set);
363 Value* find_leader(std::set<Value*>& vals,
365 Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ);
366 void phi_translate_set(std::set<Value*>& anticIn, BasicBlock* pred,
367 BasicBlock* succ, std::set<Value*>& out);
369 void topo_sort(std::set<Value*>& set,
370 std::vector<Value*>& vec);
375 void val_insert(std::set<Value*>& s, Value* v);
376 void val_replace(std::set<Value*>& s, Value* v);
377 bool dependsOnInvoke(Value* V);
378 void buildsets_availout(BasicBlock::iterator I,
379 std::set<Value*>& currAvail,
380 std::set<PHINode*>& currPhis,
381 std::set<Value*>& currExps,
382 std::set<Value*>& currTemps);
383 void buildsets_anticout(BasicBlock* BB,
384 std::set<Value*>& anticOut,
385 std::set<BasicBlock*>& visited);
386 bool buildsets_anticin(BasicBlock* BB,
387 std::set<Value*>& anticOut,
388 std::set<Value*>& currExps,
389 std::set<Value*>& currTemps,
390 std::set<BasicBlock*>& visited);
391 unsigned buildsets(Function& F);
393 void insertion_pre(Value* e, BasicBlock* BB,
394 std::map<BasicBlock*, Value*>& avail,
395 std::set<Value*>& new_set);
396 unsigned insertion_mergepoint(std::vector<Value*>& workList,
397 df_iterator<DomTreeNode*> D,
398 std::set<Value*>& new_set);
399 bool insertion(Function& F);
407 // createGVNPREPass - The public interface to this file...
408 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
410 RegisterPass<GVNPRE> X("gvnpre",
411 "Global Value Numbering/Partial Redundancy Elimination");
414 STATISTIC(NumInsertedVals, "Number of values inserted");
415 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
416 STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
418 /// find_leader - Given a set and a value number, return the first
419 /// element of the set with that value number, or 0 if no such element
421 Value* GVNPRE::find_leader(std::set<Value*>& vals, uint32_t v) {
422 for (std::set<Value*>::iterator I = vals.begin(), E = vals.end();
424 if (v == VN.lookup(*I))
430 /// val_insert - Insert a value into a set only if there is not a value
431 /// with the same value number already in the set
432 void GVNPRE::val_insert(std::set<Value*>& s, Value* v) {
433 uint32_t num = VN.lookup(v);
434 Value* leader = find_leader(s, num);
439 /// val_replace - Insert a value into a set, replacing any values already in
440 /// the set that have the same value number
441 void GVNPRE::val_replace(std::set<Value*>& s, Value* v) {
442 uint32_t num = VN.lookup(v);
443 Value* leader = find_leader(s, num);
444 while (leader != 0) {
446 leader = find_leader(s, num);
451 /// phi_translate - Given a value, its parent block, and a predecessor of its
452 /// parent, translate the value into legal for the predecessor block. This
453 /// means translating its operands (and recursively, their operands) through
454 /// any phi nodes in the parent into values available in the predecessor
455 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
459 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
461 if (isa<Instruction>(BO->getOperand(0)))
462 newOp1 = phi_translate(find_leader(anticipatedIn[succ],
463 VN.lookup(BO->getOperand(0))),
466 newOp1 = BO->getOperand(0);
472 if (isa<Instruction>(BO->getOperand(1)))
473 newOp2 = phi_translate(find_leader(anticipatedIn[succ],
474 VN.lookup(BO->getOperand(1))),
477 newOp2 = BO->getOperand(1);
482 if (newOp1 != BO->getOperand(0) || newOp2 != BO->getOperand(1)) {
483 Instruction* newVal = BinaryOperator::create(BO->getOpcode(),
485 BO->getName()+".expr");
487 uint32_t v = VN.lookup_or_add(newVal);
489 Value* leader = find_leader(availableOut[pred], v);
491 createdExpressions.push_back(newVal);
499 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
500 if (P->getParent() == succ)
501 return P->getIncomingValueForBlock(pred);
502 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
504 if (isa<Instruction>(C->getOperand(0)))
505 newOp1 = phi_translate(find_leader(anticipatedIn[succ],
506 VN.lookup(C->getOperand(0))),
509 newOp1 = C->getOperand(0);
515 if (isa<Instruction>(C->getOperand(1)))
516 newOp2 = phi_translate(find_leader(anticipatedIn[succ],
517 VN.lookup(C->getOperand(1))),
520 newOp2 = C->getOperand(1);
525 if (newOp1 != C->getOperand(0) || newOp2 != C->getOperand(1)) {
526 Instruction* newVal = CmpInst::create(C->getOpcode(),
529 C->getName()+".expr");
531 uint32_t v = VN.lookup_or_add(newVal);
533 Value* leader = find_leader(availableOut[pred], v);
535 createdExpressions.push_back(newVal);
548 /// phi_translate_set - Perform phi translation on every element of a set
549 void GVNPRE::phi_translate_set(std::set<Value*>& anticIn,
550 BasicBlock* pred, BasicBlock* succ,
551 std::set<Value*>& out) {
552 for (std::set<Value*>::iterator I = anticIn.begin(),
553 E = anticIn.end(); I != E; ++I) {
554 Value* V = phi_translate(*I, pred, succ);
560 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of
561 /// whose inputs is an invoke instruction. If this is true, we cannot safely
562 /// PRE the instruction or anything that depends on it.
563 bool GVNPRE::dependsOnInvoke(Value* V) {
564 if (PHINode* p = dyn_cast<PHINode>(V)) {
565 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
566 if (isa<InvokeInst>(*I))
574 /// clean - Remove all non-opaque values from the set whose operands are not
575 /// themselves in the set, as well as all values that depend on invokes (see
577 void GVNPRE::clean(std::set<Value*>& set) {
578 std::vector<Value*> worklist;
579 topo_sort(set, worklist);
581 for (unsigned i = 0; i < worklist.size(); ++i) {
582 Value* v = worklist[i];
584 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(v)) {
585 bool lhsValid = !isa<Instruction>(BO->getOperand(0));
587 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
589 if (VN.lookup(*I) == VN.lookup(BO->getOperand(0))) {
594 lhsValid = !dependsOnInvoke(BO->getOperand(0));
596 bool rhsValid = !isa<Instruction>(BO->getOperand(1));
598 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
600 if (VN.lookup(*I) == VN.lookup(BO->getOperand(1))) {
605 rhsValid = !dependsOnInvoke(BO->getOperand(1));
607 if (!lhsValid || !rhsValid)
609 } else if (CmpInst* C = dyn_cast<CmpInst>(v)) {
610 bool lhsValid = !isa<Instruction>(C->getOperand(0));
612 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
614 if (VN.lookup(*I) == VN.lookup(C->getOperand(0))) {
619 lhsValid = !dependsOnInvoke(C->getOperand(0));
621 bool rhsValid = !isa<Instruction>(C->getOperand(1));
623 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
625 if (VN.lookup(*I) == VN.lookup(C->getOperand(1))) {
630 rhsValid = !dependsOnInvoke(C->getOperand(1));
632 if (!lhsValid || !rhsValid)
638 /// topo_sort - Given a set of values, sort them by topological
639 /// order into the provided vector.
640 void GVNPRE::topo_sort(std::set<Value*>& set, std::vector<Value*>& vec) {
641 std::set<Value*> toErase;
642 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
644 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(*I))
645 for (std::set<Value*>::iterator SI = set.begin(); SI != E; ++SI) {
646 if (VN.lookup(BO->getOperand(0)) == VN.lookup(*SI) ||
647 VN.lookup(BO->getOperand(1)) == VN.lookup(*SI)) {
651 else if (CmpInst* C = dyn_cast<CmpInst>(*I))
652 for (std::set<Value*>::iterator SI = set.begin(); SI != E; ++SI) {
653 if (VN.lookup(C->getOperand(0)) == VN.lookup(*SI) ||
654 VN.lookup(C->getOperand(1)) == VN.lookup(*SI)) {
660 std::vector<Value*> Q;
661 for (std::set<Value*>::iterator I = set.begin(), E = set.end();
663 if (toErase.find(*I) == toErase.end())
667 std::set<Value*> visited;
671 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(e)) {
672 Value* l = find_leader(set, VN.lookup(BO->getOperand(0)));
673 Value* r = find_leader(set, VN.lookup(BO->getOperand(1)));
675 if (l != 0 && isa<Instruction>(l) &&
676 visited.find(l) == visited.end())
678 else if (r != 0 && isa<Instruction>(r) &&
679 visited.find(r) == visited.end())
686 } else if (CmpInst* C = dyn_cast<CmpInst>(e)) {
687 Value* l = find_leader(set, VN.lookup(C->getOperand(0)));
688 Value* r = find_leader(set, VN.lookup(C->getOperand(1)));
690 if (l != 0 && isa<Instruction>(l) &&
691 visited.find(l) == visited.end())
693 else if (r != 0 && isa<Instruction>(r) &&
694 visited.find(r) == visited.end())
709 /// dump - Dump a set of values to standard error
710 void GVNPRE::dump(const std::set<Value*>& s) const {
712 for (std::set<Value*>::iterator I = s.begin(), E = s.end();
719 /// elimination - Phase 3 of the main algorithm. Perform full redundancy
720 /// elimination by walking the dominator tree and removing any instruction that
721 /// is dominated by another instruction with the same value number.
722 bool GVNPRE::elimination() {
723 DOUT << "\n\nPhase 3: Elimination\n\n";
725 bool changed_function = false;
727 std::vector<std::pair<Instruction*, Value*> > replace;
728 std::vector<Instruction*> erase;
730 DominatorTree& DT = getAnalysis<DominatorTree>();
732 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
733 E = df_end(DT.getRootNode()); DI != E; ++DI) {
734 BasicBlock* BB = DI->getBlock();
736 DOUT << "Block: " << BB->getName() << "\n";
737 dump(availableOut[BB]);
740 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
743 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI)) {
744 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
747 if (Instruction* Instr = dyn_cast<Instruction>(leader))
748 if (Instr->getParent() != 0 && Instr != BI) {
749 replace.push_back(std::make_pair(BI, leader));
757 while (!replace.empty()) {
758 std::pair<Instruction*, Value*> rep = replace.back();
760 rep.first->replaceAllUsesWith(rep.second);
761 changed_function = true;
764 for (std::vector<Instruction*>::iterator I = erase.begin(), E = erase.end();
766 (*I)->eraseFromParent();
768 return changed_function;
771 /// cleanup - Delete any extraneous values that were created to represent
772 /// expressions without leaders.
773 void GVNPRE::cleanup() {
774 while (!createdExpressions.empty()) {
775 Instruction* I = createdExpressions.back();
776 createdExpressions.pop_back();
782 /// buildsets_availout - When calculating availability, handle an instruction
783 /// by inserting it into the appropriate sets
784 void GVNPRE::buildsets_availout(BasicBlock::iterator I,
785 std::set<Value*>& currAvail,
786 std::set<PHINode*>& currPhis,
787 std::set<Value*>& currExps,
788 std::set<Value*>& currTemps) {
789 // Handle PHI nodes...
790 if (PHINode* p = dyn_cast<PHINode>(I)) {
794 // Handle binary ops...
795 } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(I)) {
796 Value* leftValue = BO->getOperand(0);
797 Value* rightValue = BO->getOperand(1);
799 VN.lookup_or_add(BO);
801 if (isa<Instruction>(leftValue))
802 val_insert(currExps, leftValue);
803 if (isa<Instruction>(rightValue))
804 val_insert(currExps, rightValue);
805 val_insert(currExps, BO);
808 } else if (CmpInst* C = dyn_cast<CmpInst>(I)) {
809 Value* leftValue = C->getOperand(0);
810 Value* rightValue = C->getOperand(1);
814 if (isa<Instruction>(leftValue))
815 val_insert(currExps, leftValue);
816 if (isa<Instruction>(rightValue))
817 val_insert(currExps, rightValue);
818 val_insert(currExps, C);
820 // Handle unsupported ops
821 } else if (!I->isTerminator()){
826 if (!I->isTerminator())
827 val_insert(currAvail, I);
830 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
831 /// set as a function of the ANTIC_IN set of the block's predecessors
832 void GVNPRE::buildsets_anticout(BasicBlock* BB,
833 std::set<Value*>& anticOut,
834 std::set<BasicBlock*>& visited) {
835 if (BB->getTerminator()->getNumSuccessors() == 1) {
836 if (visited.find(BB->getTerminator()->getSuccessor(0)) == visited.end())
837 phi_translate_set(VN.getMaximalValues(), BB,
838 BB->getTerminator()->getSuccessor(0), anticOut);
840 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
841 BB, BB->getTerminator()->getSuccessor(0), anticOut);
842 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
843 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
844 anticOut.insert(anticipatedIn[first].begin(), anticipatedIn[first].end());
846 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
847 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
848 std::set<Value*>& succAnticIn = anticipatedIn[currSucc];
850 std::set<Value*> temp;
851 std::insert_iterator<std::set<Value*> > temp_ins(temp, temp.begin());
852 std::set_intersection(anticOut.begin(), anticOut.end(),
853 succAnticIn.begin(), succAnticIn.end(), temp_ins);
856 anticOut.insert(temp.begin(), temp.end());
861 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
862 /// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN
863 /// sets populated in buildsets_availout
864 bool GVNPRE::buildsets_anticin(BasicBlock* BB,
865 std::set<Value*>& anticOut,
866 std::set<Value*>& currExps,
867 std::set<Value*>& currTemps,
868 std::set<BasicBlock*>& visited) {
869 std::set<Value*>& anticIn = anticipatedIn[BB];
870 std::set<Value*> old (anticIn.begin(), anticIn.end());
872 buildsets_anticout(BB, anticOut, visited);
875 std::insert_iterator<std::set<Value*> > s_ins(S, S.begin());
876 std::set_difference(anticOut.begin(), anticOut.end(),
877 currTemps.begin(), currTemps.end(), s_ins);
880 std::insert_iterator<std::set<Value*> > ai_ins(anticIn, anticIn.begin());
881 std::set_difference(currExps.begin(), currExps.end(),
882 currTemps.begin(), currTemps.end(), ai_ins);
884 for (std::set<Value*>::iterator I = S.begin(), E = S.end();
886 // For non-opaque values, we should already have a value numbering.
887 // However, for opaques, such as constants within PHI nodes, it is
888 // possible that they have not yet received a number. Make sure they do
891 if (isa<BinaryOperator>(*I) || isa<CmpInst>(*I))
892 valNum = VN.lookup(*I);
894 valNum = VN.lookup_or_add(*I);
895 if (find_leader(anticIn, valNum) == 0)
896 val_insert(anticIn, *I);
902 if (old.size() != anticIn.size())
908 /// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT
909 /// and the ANTIC_IN sets.
910 unsigned GVNPRE::buildsets(Function& F) {
911 std::map<BasicBlock*, std::set<Value*> > generatedExpressions;
912 std::map<BasicBlock*, std::set<PHINode*> > generatedPhis;
913 std::map<BasicBlock*, std::set<Value*> > generatedTemporaries;
915 DominatorTree &DT = getAnalysis<DominatorTree>();
917 // Phase 1, Part 1: calculate AVAIL_OUT
919 // Top-down walk of the dominator tree
920 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
921 E = df_end(DT.getRootNode()); DI != E; ++DI) {
923 // Get the sets to update for this block
924 std::set<Value*>& currExps = generatedExpressions[DI->getBlock()];
925 std::set<PHINode*>& currPhis = generatedPhis[DI->getBlock()];
926 std::set<Value*>& currTemps = generatedTemporaries[DI->getBlock()];
927 std::set<Value*>& currAvail = availableOut[DI->getBlock()];
929 BasicBlock* BB = DI->getBlock();
931 // A block inherits AVAIL_OUT from its dominator
932 if (DI->getIDom() != 0)
933 currAvail.insert(availableOut[DI->getIDom()->getBlock()].begin(),
934 availableOut[DI->getIDom()->getBlock()].end());
937 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
939 buildsets_availout(BI, currAvail, currPhis, currExps, currTemps);
943 // If function has no exit blocks, only perform GVN
944 PostDominatorTree &PDT = getAnalysis<PostDominatorTree>();
945 if (PDT[&F.getEntryBlock()] == 0) {
946 bool changed_function = elimination();
949 if (changed_function)
950 return 2; // Bailed early, made changes
952 return 1; // Bailed early, no changes
956 // Phase 1, Part 2: calculate ANTIC_IN
958 std::set<BasicBlock*> visited;
961 unsigned iterations = 0;
964 std::set<Value*> anticOut;
966 // Top-down walk of the postdominator tree
967 for (df_iterator<DomTreeNode*> PDI =
968 df_begin(PDT.getRootNode()), E = df_end(PDT.getRootNode());
970 BasicBlock* BB = PDI->getBlock();
976 changed |= buildsets_anticin(BB, anticOut, generatedTemporaries[BB],
977 generatedExpressions[BB], visited);
983 return 0; // No bail, no changes
986 /// insertion_pre - When a partial redundancy has been identified, eliminate it
987 /// by inserting appropriate values into the predecessors and a phi node in
989 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
990 std::map<BasicBlock*, Value*>& avail,
991 std::set<Value*>& new_set) {
992 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
993 Value* e2 = avail[*PI];
994 if (!find_leader(availableOut[*PI], VN.lookup(e2))) {
995 User* U = cast<User>(e2);
998 if (isa<BinaryOperator>(U->getOperand(0)) ||
999 isa<CmpInst>(U->getOperand(0)))
1000 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1002 s1 = U->getOperand(0);
1005 if (isa<BinaryOperator>(U->getOperand(1)) ||
1006 isa<CmpInst>(U->getOperand(1)))
1007 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1009 s2 = U->getOperand(1);
1012 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1013 newVal = BinaryOperator::create(BO->getOpcode(), s1, s2,
1014 BO->getName()+".gvnpre",
1015 (*PI)->getTerminator());
1016 else if (CmpInst* C = dyn_cast<CmpInst>(U))
1017 newVal = CmpInst::create(C->getOpcode(), C->getPredicate(), s1, s2,
1018 C->getName()+".gvnpre",
1019 (*PI)->getTerminator());
1021 VN.add(newVal, VN.lookup(U));
1023 std::set<Value*>& predAvail = availableOut[*PI];
1024 val_replace(predAvail, newVal);
1026 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1027 if (av != avail.end())
1029 avail.insert(std::make_pair(*PI, newVal));
1037 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1039 p = new PHINode(avail[*PI]->getType(), "gvnpre-join", BB->begin());
1041 p->addIncoming(avail[*PI], *PI);
1044 VN.add(p, VN.lookup(e));
1045 val_replace(availableOut[BB], p);
1051 /// insertion_mergepoint - When walking the dom tree, check at each merge
1052 /// block for the possibility of a partial redundancy. If present, eliminate it
1053 unsigned GVNPRE::insertion_mergepoint(std::vector<Value*>& workList,
1054 df_iterator<DomTreeNode*> D,
1055 std::set<Value*>& new_set) {
1056 bool changed_function = false;
1057 bool new_stuff = false;
1059 BasicBlock* BB = D->getBlock();
1060 for (unsigned i = 0; i < workList.size(); ++i) {
1061 Value* e = workList[i];
1063 if (isa<BinaryOperator>(e) || isa<CmpInst>(e)) {
1064 if (find_leader(availableOut[D->getIDom()->getBlock()],
1068 std::map<BasicBlock*, Value*> avail;
1069 bool by_some = false;
1072 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1074 Value *e2 = phi_translate(e, *PI, BB);
1075 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1078 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1079 if (av != avail.end())
1081 avail.insert(std::make_pair(*PI, e2));
1083 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1084 if (av != avail.end())
1086 avail.insert(std::make_pair(*PI, e3));
1093 if (by_some && num_avail < std::distance(pred_begin(BB), pred_end(BB))) {
1094 insertion_pre(e, BB, avail, new_set);
1096 changed_function = true;
1102 unsigned retval = 0;
1103 if (changed_function)
1111 /// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for
1112 /// merge points. When one is found, check for a partial redundancy. If one is
1113 /// present, eliminate it. Repeat this walk until no changes are made.
1114 bool GVNPRE::insertion(Function& F) {
1115 bool changed_function = false;
1117 DominatorTree &DT = getAnalysis<DominatorTree>();
1119 std::map<BasicBlock*, std::set<Value*> > new_sets;
1120 bool new_stuff = true;
1123 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1124 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1125 BasicBlock* BB = DI->getBlock();
1130 std::set<Value*>& new_set = new_sets[BB];
1131 std::set<Value*>& availOut = availableOut[BB];
1132 std::set<Value*>& anticIn = anticipatedIn[BB];
1136 // Replace leaders with leaders inherited from dominator
1137 if (DI->getIDom() != 0) {
1138 std::set<Value*>& dom_set = new_sets[DI->getIDom()->getBlock()];
1139 for (std::set<Value*>::iterator I = dom_set.begin(),
1140 E = dom_set.end(); I != E; ++I) {
1142 val_replace(availOut, *I);
1146 // If there is more than one predecessor...
1147 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
1148 std::vector<Value*> workList;
1149 topo_sort(anticIn, workList);
1151 DOUT << "Merge Block: " << BB->getName() << "\n";
1152 DOUT << "ANTIC_IN: ";
1156 unsigned result = insertion_mergepoint(workList, DI, new_set);
1158 changed_function = true;
1165 return changed_function;
1168 // GVNPRE::runOnFunction - This is the main transformation entry point for a
1171 bool GVNPRE::runOnFunction(Function &F) {
1172 // Clean out global sets from any previous functions
1174 createdExpressions.clear();
1175 availableOut.clear();
1176 anticipatedIn.clear();
1178 bool changed_function = false;
1180 // Phase 1: BuildSets
1181 // This phase calculates the AVAIL_OUT and ANTIC_IN sets
1182 // NOTE: If full postdom information is no available, this will bail
1183 // early, performing GVN but not PRE
1184 unsigned bail = buildsets(F);
1185 //If a bail occurred, terminate early
1190 // This phase inserts values to make partially redundant values
1192 changed_function |= insertion(F);
1194 // Phase 3: Eliminate
1195 // This phase performs trivial full redundancy elimination
1196 changed_function |= elimination();
1199 // This phase cleans up values that were created solely
1200 // as leaders for expressions
1203 return changed_function;