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/SmallPtrSet.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/Support/CFG.h"
33 #include "llvm/Support/Compiler.h"
34 #include "llvm/Support/Debug.h"
42 //===----------------------------------------------------------------------===//
44 //===----------------------------------------------------------------------===//
46 /// This class holds the mapping between values and value numbers. It is used
47 /// as an efficient mechanism to determine the expression-wise equivalence of
51 class VISIBILITY_HIDDEN ValueTable {
54 enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
55 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
56 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
57 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
58 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
59 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
60 FCMPULT, FCMPULE, FCMPUNE };
62 ExpressionOpcode opcode;
66 bool operator< (const Expression& other) const {
67 if (opcode < other.opcode)
69 else if (opcode > other.opcode)
71 else if (leftVN < other.leftVN)
73 else if (leftVN > other.leftVN)
75 else if (rightVN < other.rightVN)
77 else if (rightVN > other.rightVN)
85 DenseMap<Value*, uint32_t> valueNumbering;
86 std::map<Expression, uint32_t> expressionNumbering;
88 std::set<Expression> maximalExpressions;
89 SmallPtrSet<Value*, 32> maximalValues;
91 uint32_t nextValueNumber;
93 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
94 Expression::ExpressionOpcode getOpcode(CmpInst* C);
95 Expression create_expression(BinaryOperator* BO);
96 Expression create_expression(CmpInst* C);
98 ValueTable() { nextValueNumber = 1; }
99 uint32_t lookup_or_add(Value* V);
100 uint32_t lookup(Value* V);
101 void add(Value* V, uint32_t num);
103 std::set<Expression>& getMaximalExpressions() {
104 return maximalExpressions;
107 SmallPtrSet<Value*, 32>& getMaximalValues() { return maximalValues; }
108 void erase(Value* v);
112 //===----------------------------------------------------------------------===//
113 // ValueTable Internal Functions
114 //===----------------------------------------------------------------------===//
115 ValueTable::Expression::ExpressionOpcode
116 ValueTable::getOpcode(BinaryOperator* BO) {
117 switch(BO->getOpcode()) {
118 case Instruction::Add:
119 return Expression::ADD;
120 case Instruction::Sub:
121 return Expression::SUB;
122 case Instruction::Mul:
123 return Expression::MUL;
124 case Instruction::UDiv:
125 return Expression::UDIV;
126 case Instruction::SDiv:
127 return Expression::SDIV;
128 case Instruction::FDiv:
129 return Expression::FDIV;
130 case Instruction::URem:
131 return Expression::UREM;
132 case Instruction::SRem:
133 return Expression::SREM;
134 case Instruction::FRem:
135 return Expression::FREM;
136 case Instruction::Shl:
137 return Expression::SHL;
138 case Instruction::LShr:
139 return Expression::LSHR;
140 case Instruction::AShr:
141 return Expression::ASHR;
142 case Instruction::And:
143 return Expression::AND;
144 case Instruction::Or:
145 return Expression::OR;
146 case Instruction::Xor:
147 return Expression::XOR;
149 // THIS SHOULD NEVER HAPPEN
151 assert(0 && "Binary operator with unknown opcode?");
152 return Expression::ADD;
156 ValueTable::Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
157 if (C->getOpcode() == Instruction::ICmp) {
158 switch (C->getPredicate()) {
159 case ICmpInst::ICMP_EQ:
160 return Expression::ICMPEQ;
161 case ICmpInst::ICMP_NE:
162 return Expression::ICMPNE;
163 case ICmpInst::ICMP_UGT:
164 return Expression::ICMPUGT;
165 case ICmpInst::ICMP_UGE:
166 return Expression::ICMPUGE;
167 case ICmpInst::ICMP_ULT:
168 return Expression::ICMPULT;
169 case ICmpInst::ICMP_ULE:
170 return Expression::ICMPULE;
171 case ICmpInst::ICMP_SGT:
172 return Expression::ICMPSGT;
173 case ICmpInst::ICMP_SGE:
174 return Expression::ICMPSGE;
175 case ICmpInst::ICMP_SLT:
176 return Expression::ICMPSLT;
177 case ICmpInst::ICMP_SLE:
178 return Expression::ICMPSLE;
180 // THIS SHOULD NEVER HAPPEN
182 assert(0 && "Comparison with unknown predicate?");
183 return Expression::ICMPEQ;
186 switch (C->getPredicate()) {
187 case FCmpInst::FCMP_OEQ:
188 return Expression::FCMPOEQ;
189 case FCmpInst::FCMP_OGT:
190 return Expression::FCMPOGT;
191 case FCmpInst::FCMP_OGE:
192 return Expression::FCMPOGE;
193 case FCmpInst::FCMP_OLT:
194 return Expression::FCMPOLT;
195 case FCmpInst::FCMP_OLE:
196 return Expression::FCMPOLE;
197 case FCmpInst::FCMP_ONE:
198 return Expression::FCMPONE;
199 case FCmpInst::FCMP_ORD:
200 return Expression::FCMPORD;
201 case FCmpInst::FCMP_UNO:
202 return Expression::FCMPUNO;
203 case FCmpInst::FCMP_UEQ:
204 return Expression::FCMPUEQ;
205 case FCmpInst::FCMP_UGT:
206 return Expression::FCMPUGT;
207 case FCmpInst::FCMP_UGE:
208 return Expression::FCMPUGE;
209 case FCmpInst::FCMP_ULT:
210 return Expression::FCMPULT;
211 case FCmpInst::FCMP_ULE:
212 return Expression::FCMPULE;
213 case FCmpInst::FCMP_UNE:
214 return Expression::FCMPUNE;
216 // THIS SHOULD NEVER HAPPEN
218 assert(0 && "Comparison with unknown predicate?");
219 return Expression::FCMPOEQ;
224 ValueTable::Expression ValueTable::create_expression(BinaryOperator* BO) {
227 e.leftVN = lookup_or_add(BO->getOperand(0));
228 e.rightVN = lookup_or_add(BO->getOperand(1));
229 e.opcode = getOpcode(BO);
231 maximalExpressions.insert(e);
236 ValueTable::Expression ValueTable::create_expression(CmpInst* C) {
239 e.leftVN = lookup_or_add(C->getOperand(0));
240 e.rightVN = lookup_or_add(C->getOperand(1));
241 e.opcode = getOpcode(C);
243 maximalExpressions.insert(e);
248 //===----------------------------------------------------------------------===//
249 // ValueTable External Functions
250 //===----------------------------------------------------------------------===//
252 /// lookup_or_add - Returns the value number for the specified value, assigning
253 /// it a new number if it did not have one before.
254 uint32_t ValueTable::lookup_or_add(Value* V) {
255 maximalValues.insert(V);
257 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
258 if (VI != valueNumbering.end())
262 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
263 Expression e = create_expression(BO);
265 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
266 if (EI != expressionNumbering.end()) {
267 valueNumbering.insert(std::make_pair(V, EI->second));
270 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
271 valueNumbering.insert(std::make_pair(V, nextValueNumber));
273 return nextValueNumber++;
275 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
276 Expression e = create_expression(C);
278 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
279 if (EI != expressionNumbering.end()) {
280 valueNumbering.insert(std::make_pair(V, EI->second));
283 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
284 valueNumbering.insert(std::make_pair(V, nextValueNumber));
286 return nextValueNumber++;
289 valueNumbering.insert(std::make_pair(V, nextValueNumber));
290 return nextValueNumber++;
294 /// lookup - Returns the value number of the specified value. Fails if
295 /// the value has not yet been numbered.
296 uint32_t ValueTable::lookup(Value* V) {
297 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
298 if (VI != valueNumbering.end())
301 assert(0 && "Value not numbered?");
306 /// add - Add the specified value with the given value number, removing
307 /// its old number, if any
308 void ValueTable::add(Value* V, uint32_t num) {
309 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
310 if (VI != valueNumbering.end())
311 valueNumbering.erase(VI);
312 valueNumbering.insert(std::make_pair(V, num));
315 /// clear - Remove all entries from the ValueTable and the maximal sets
316 void ValueTable::clear() {
317 valueNumbering.clear();
318 expressionNumbering.clear();
319 maximalExpressions.clear();
320 maximalValues.clear();
324 /// erase - Remove a value from the value numbering and maximal sets
325 void ValueTable::erase(Value* V) {
326 maximalValues.erase(V);
327 valueNumbering.erase(V);
328 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V))
329 maximalExpressions.erase(create_expression(BO));
330 else if (CmpInst* C = dyn_cast<CmpInst>(V))
331 maximalExpressions.erase(create_expression(C));
334 //===----------------------------------------------------------------------===//
336 //===----------------------------------------------------------------------===//
340 class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
341 bool runOnFunction(Function &F);
343 static char ID; // Pass identification, replacement for typeid
344 GVNPRE() : FunctionPass((intptr_t)&ID) { }
348 std::vector<Instruction*> createdExpressions;
350 std::map<BasicBlock*, SmallPtrSet<Value*, 32> > availableOut;
351 std::map<BasicBlock*, SmallPtrSet<Value*, 32> > anticipatedIn;
353 // This transformation requires dominator postdominator info
354 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
355 AU.setPreservesCFG();
356 AU.addRequired<DominatorTree>();
357 AU.addRequired<PostDominatorTree>();
361 // FIXME: eliminate or document these better
362 void dump(const SmallPtrSet<Value*, 32>& s) const;
363 void clean(SmallPtrSet<Value*, 32>& set);
364 Value* find_leader(SmallPtrSet<Value*, 32>& vals,
366 Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ);
367 void phi_translate_set(SmallPtrSet<Value*, 32>& anticIn, BasicBlock* pred,
368 BasicBlock* succ, SmallPtrSet<Value*, 32>& out);
370 void topo_sort(SmallPtrSet<Value*, 32>& set,
371 std::vector<Value*>& vec);
376 void val_insert(SmallPtrSet<Value*, 32>& s, Value* v);
377 void val_replace(SmallPtrSet<Value*, 32>& s, Value* v);
378 bool dependsOnInvoke(Value* V);
379 void buildsets_availout(BasicBlock::iterator I,
380 SmallPtrSet<Value*, 32>& currAvail,
381 SmallPtrSet<PHINode*, 32>& currPhis,
382 SmallPtrSet<Value*, 32>& currExps,
383 SmallPtrSet<Value*, 32>& currTemps);
384 void buildsets_anticout(BasicBlock* BB,
385 SmallPtrSet<Value*, 32>& anticOut,
386 std::set<BasicBlock*>& visited);
387 bool buildsets_anticin(BasicBlock* BB,
388 SmallPtrSet<Value*, 32>& anticOut,
389 SmallPtrSet<Value*, 32>& currExps,
390 SmallPtrSet<Value*, 32>& currTemps,
391 std::set<BasicBlock*>& visited);
392 unsigned buildsets(Function& F);
394 void insertion_pre(Value* e, BasicBlock* BB,
395 std::map<BasicBlock*, Value*>& avail,
396 SmallPtrSet<Value*, 32>& new_set);
397 unsigned insertion_mergepoint(std::vector<Value*>& workList,
398 df_iterator<DomTreeNode*> D,
399 SmallPtrSet<Value*, 32>& new_set);
400 bool insertion(Function& F);
408 // createGVNPREPass - The public interface to this file...
409 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
411 RegisterPass<GVNPRE> X("gvnpre",
412 "Global Value Numbering/Partial Redundancy Elimination");
415 STATISTIC(NumInsertedVals, "Number of values inserted");
416 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
417 STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
419 /// find_leader - Given a set and a value number, return the first
420 /// element of the set with that value number, or 0 if no such element
422 Value* GVNPRE::find_leader(SmallPtrSet<Value*, 32>& vals, uint32_t v) {
423 for (SmallPtrSet<Value*, 32>::iterator I = vals.begin(), E = vals.end();
425 if (v == VN.lookup(*I))
431 /// val_insert - Insert a value into a set only if there is not a value
432 /// with the same value number already in the set
433 void GVNPRE::val_insert(SmallPtrSet<Value*, 32>& s, Value* v) {
434 uint32_t num = VN.lookup(v);
435 Value* leader = find_leader(s, num);
440 /// val_replace - Insert a value into a set, replacing any values already in
441 /// the set that have the same value number
442 void GVNPRE::val_replace(SmallPtrSet<Value*, 32>& s, Value* v) {
443 uint32_t num = VN.lookup(v);
444 Value* leader = find_leader(s, num);
445 while (leader != 0) {
447 leader = find_leader(s, num);
452 /// phi_translate - Given a value, its parent block, and a predecessor of its
453 /// parent, translate the value into legal for the predecessor block. This
454 /// means translating its operands (and recursively, their operands) through
455 /// any phi nodes in the parent into values available in the predecessor
456 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
460 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
462 if (isa<Instruction>(BO->getOperand(0)))
463 newOp1 = phi_translate(find_leader(anticipatedIn[succ],
464 VN.lookup(BO->getOperand(0))),
467 newOp1 = BO->getOperand(0);
473 if (isa<Instruction>(BO->getOperand(1)))
474 newOp2 = phi_translate(find_leader(anticipatedIn[succ],
475 VN.lookup(BO->getOperand(1))),
478 newOp2 = BO->getOperand(1);
483 if (newOp1 != BO->getOperand(0) || newOp2 != BO->getOperand(1)) {
484 Instruction* newVal = BinaryOperator::create(BO->getOpcode(),
486 BO->getName()+".expr");
488 uint32_t v = VN.lookup_or_add(newVal);
490 Value* leader = find_leader(availableOut[pred], v);
492 createdExpressions.push_back(newVal);
500 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
501 if (P->getParent() == succ)
502 return P->getIncomingValueForBlock(pred);
503 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
505 if (isa<Instruction>(C->getOperand(0)))
506 newOp1 = phi_translate(find_leader(anticipatedIn[succ],
507 VN.lookup(C->getOperand(0))),
510 newOp1 = C->getOperand(0);
516 if (isa<Instruction>(C->getOperand(1)))
517 newOp2 = phi_translate(find_leader(anticipatedIn[succ],
518 VN.lookup(C->getOperand(1))),
521 newOp2 = C->getOperand(1);
526 if (newOp1 != C->getOperand(0) || newOp2 != C->getOperand(1)) {
527 Instruction* newVal = CmpInst::create(C->getOpcode(),
530 C->getName()+".expr");
532 uint32_t v = VN.lookup_or_add(newVal);
534 Value* leader = find_leader(availableOut[pred], v);
536 createdExpressions.push_back(newVal);
549 /// phi_translate_set - Perform phi translation on every element of a set
550 void GVNPRE::phi_translate_set(SmallPtrSet<Value*, 32>& anticIn,
551 BasicBlock* pred, BasicBlock* succ,
552 SmallPtrSet<Value*, 32>& out) {
553 for (SmallPtrSet<Value*, 32>::iterator I = anticIn.begin(),
554 E = anticIn.end(); I != E; ++I) {
555 Value* V = phi_translate(*I, pred, succ);
561 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of
562 /// whose inputs is an invoke instruction. If this is true, we cannot safely
563 /// PRE the instruction or anything that depends on it.
564 bool GVNPRE::dependsOnInvoke(Value* V) {
565 if (PHINode* p = dyn_cast<PHINode>(V)) {
566 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
567 if (isa<InvokeInst>(*I))
575 /// clean - Remove all non-opaque values from the set whose operands are not
576 /// themselves in the set, as well as all values that depend on invokes (see
578 void GVNPRE::clean(SmallPtrSet<Value*, 32>& set) {
579 std::vector<Value*> worklist;
580 topo_sort(set, worklist);
582 for (unsigned i = 0; i < worklist.size(); ++i) {
583 Value* v = worklist[i];
585 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(v)) {
586 bool lhsValid = !isa<Instruction>(BO->getOperand(0));
588 for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
590 if (VN.lookup(*I) == VN.lookup(BO->getOperand(0))) {
595 lhsValid = !dependsOnInvoke(BO->getOperand(0));
597 bool rhsValid = !isa<Instruction>(BO->getOperand(1));
599 for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
601 if (VN.lookup(*I) == VN.lookup(BO->getOperand(1))) {
606 rhsValid = !dependsOnInvoke(BO->getOperand(1));
608 if (!lhsValid || !rhsValid)
610 } else if (CmpInst* C = dyn_cast<CmpInst>(v)) {
611 bool lhsValid = !isa<Instruction>(C->getOperand(0));
613 for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
615 if (VN.lookup(*I) == VN.lookup(C->getOperand(0))) {
620 lhsValid = !dependsOnInvoke(C->getOperand(0));
622 bool rhsValid = !isa<Instruction>(C->getOperand(1));
624 for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
626 if (VN.lookup(*I) == VN.lookup(C->getOperand(1))) {
631 rhsValid = !dependsOnInvoke(C->getOperand(1));
633 if (!lhsValid || !rhsValid)
639 /// topo_sort - Given a set of values, sort them by topological
640 /// order into the provided vector.
641 void GVNPRE::topo_sort(SmallPtrSet<Value*, 32>& set, std::vector<Value*>& vec) {
642 SmallPtrSet<Value*, 32> toErase;
643 for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
645 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(*I))
646 for (SmallPtrSet<Value*, 32>::iterator SI = set.begin(); SI != E; ++SI) {
647 if (VN.lookup(BO->getOperand(0)) == VN.lookup(*SI) ||
648 VN.lookup(BO->getOperand(1)) == VN.lookup(*SI)) {
652 else if (CmpInst* C = dyn_cast<CmpInst>(*I))
653 for (SmallPtrSet<Value*, 32>::iterator SI = set.begin(); SI != E; ++SI) {
654 if (VN.lookup(C->getOperand(0)) == VN.lookup(*SI) ||
655 VN.lookup(C->getOperand(1)) == VN.lookup(*SI)) {
661 std::vector<Value*> Q;
662 for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
664 if (toErase.count(*I) == 0)
668 SmallPtrSet<Value*, 32> visited;
672 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(e)) {
673 Value* l = find_leader(set, VN.lookup(BO->getOperand(0)));
674 Value* r = find_leader(set, VN.lookup(BO->getOperand(1)));
676 if (l != 0 && isa<Instruction>(l) &&
677 visited.count(l) == 0)
679 else if (r != 0 && isa<Instruction>(r) &&
680 visited.count(r) == 0)
687 } else if (CmpInst* C = dyn_cast<CmpInst>(e)) {
688 Value* l = find_leader(set, VN.lookup(C->getOperand(0)));
689 Value* r = find_leader(set, VN.lookup(C->getOperand(1)));
691 if (l != 0 && isa<Instruction>(l) &&
692 visited.count(l) == 0)
694 else if (r != 0 && isa<Instruction>(r) &&
695 visited.count(r) == 0)
710 /// dump - Dump a set of values to standard error
711 void GVNPRE::dump(const SmallPtrSet<Value*, 32>& s) const {
713 for (SmallPtrSet<Value*, 32>::iterator I = s.begin(), E = s.end();
720 /// elimination - Phase 3 of the main algorithm. Perform full redundancy
721 /// elimination by walking the dominator tree and removing any instruction that
722 /// is dominated by another instruction with the same value number.
723 bool GVNPRE::elimination() {
724 DOUT << "\n\nPhase 3: Elimination\n\n";
726 bool changed_function = false;
728 std::vector<std::pair<Instruction*, Value*> > replace;
729 std::vector<Instruction*> erase;
731 DominatorTree& DT = getAnalysis<DominatorTree>();
733 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
734 E = df_end(DT.getRootNode()); DI != E; ++DI) {
735 BasicBlock* BB = DI->getBlock();
737 DOUT << "Block: " << BB->getName() << "\n";
738 dump(availableOut[BB]);
741 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
744 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI)) {
745 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
748 if (Instruction* Instr = dyn_cast<Instruction>(leader))
749 if (Instr->getParent() != 0 && Instr != BI) {
750 replace.push_back(std::make_pair(BI, leader));
758 while (!replace.empty()) {
759 std::pair<Instruction*, Value*> rep = replace.back();
761 rep.first->replaceAllUsesWith(rep.second);
762 changed_function = true;
765 for (std::vector<Instruction*>::iterator I = erase.begin(), E = erase.end();
767 (*I)->eraseFromParent();
769 return changed_function;
772 /// cleanup - Delete any extraneous values that were created to represent
773 /// expressions without leaders.
774 void GVNPRE::cleanup() {
775 while (!createdExpressions.empty()) {
776 Instruction* I = createdExpressions.back();
777 createdExpressions.pop_back();
783 /// buildsets_availout - When calculating availability, handle an instruction
784 /// by inserting it into the appropriate sets
785 void GVNPRE::buildsets_availout(BasicBlock::iterator I,
786 SmallPtrSet<Value*, 32>& currAvail,
787 SmallPtrSet<PHINode*, 32>& currPhis,
788 SmallPtrSet<Value*, 32>& currExps,
789 SmallPtrSet<Value*, 32>& currTemps) {
790 // Handle PHI nodes...
791 if (PHINode* p = dyn_cast<PHINode>(I)) {
795 // Handle binary ops...
796 } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(I)) {
797 Value* leftValue = BO->getOperand(0);
798 Value* rightValue = BO->getOperand(1);
800 VN.lookup_or_add(BO);
802 if (isa<Instruction>(leftValue))
803 val_insert(currExps, leftValue);
804 if (isa<Instruction>(rightValue))
805 val_insert(currExps, rightValue);
806 val_insert(currExps, BO);
809 } else if (CmpInst* C = dyn_cast<CmpInst>(I)) {
810 Value* leftValue = C->getOperand(0);
811 Value* rightValue = C->getOperand(1);
815 if (isa<Instruction>(leftValue))
816 val_insert(currExps, leftValue);
817 if (isa<Instruction>(rightValue))
818 val_insert(currExps, rightValue);
819 val_insert(currExps, C);
821 // Handle unsupported ops
822 } else if (!I->isTerminator()){
827 if (!I->isTerminator())
828 val_insert(currAvail, I);
831 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
832 /// set as a function of the ANTIC_IN set of the block's predecessors
833 void GVNPRE::buildsets_anticout(BasicBlock* BB,
834 SmallPtrSet<Value*, 32>& anticOut,
835 std::set<BasicBlock*>& visited) {
836 if (BB->getTerminator()->getNumSuccessors() == 1) {
837 if (visited.find(BB->getTerminator()->getSuccessor(0)) == visited.end())
838 phi_translate_set(VN.getMaximalValues(), BB,
839 BB->getTerminator()->getSuccessor(0), anticOut);
841 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
842 BB, BB->getTerminator()->getSuccessor(0), anticOut);
843 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
844 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
845 anticOut.insert(anticipatedIn[first].begin(), anticipatedIn[first].end());
847 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
848 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
849 SmallPtrSet<Value*, 32>& succAnticIn = anticipatedIn[currSucc];
851 std::vector<Value*> temp;
853 for (SmallPtrSet<Value*, 32>::iterator I = anticOut.begin(),
854 E = anticOut.end(); I != E; ++I)
855 if (succAnticIn.count(*I) == 0)
858 for (std::vector<Value*>::iterator I = temp.begin(), E = temp.end();
865 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
866 /// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN
867 /// sets populated in buildsets_availout
868 bool GVNPRE::buildsets_anticin(BasicBlock* BB,
869 SmallPtrSet<Value*, 32>& anticOut,
870 SmallPtrSet<Value*, 32>& currExps,
871 SmallPtrSet<Value*, 32>& currTemps,
872 std::set<BasicBlock*>& visited) {
873 SmallPtrSet<Value*, 32>& anticIn = anticipatedIn[BB];
874 SmallPtrSet<Value*, 32> old (anticIn.begin(), anticIn.end());
876 buildsets_anticout(BB, anticOut, visited);
878 SmallPtrSet<Value*, 32> S;
879 for (SmallPtrSet<Value*, 32>::iterator I = anticOut.begin(),
880 E = anticOut.end(); I != E; ++I)
881 if (currTemps.count(*I) == 0)
886 for (SmallPtrSet<Value*, 32>::iterator I = currExps.begin(),
887 E = currExps.end(); I != E; ++I)
888 if (currTemps.count(*I) == 0)
891 for (SmallPtrSet<Value*, 32>::iterator I = S.begin(), E = S.end();
893 // For non-opaque values, we should already have a value numbering.
894 // However, for opaques, such as constants within PHI nodes, it is
895 // possible that they have not yet received a number. Make sure they do
897 if (!isa<BinaryOperator>(*I) && !isa<CmpInst>(*I))
898 VN.lookup_or_add(*I);
899 val_insert(anticIn, *I);
905 if (old.size() != anticIn.size())
911 /// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT
912 /// and the ANTIC_IN sets.
913 unsigned GVNPRE::buildsets(Function& F) {
914 std::map<BasicBlock*, SmallPtrSet<Value*, 32> > generatedExpressions;
915 std::map<BasicBlock*, SmallPtrSet<PHINode*, 32> > generatedPhis;
916 std::map<BasicBlock*, SmallPtrSet<Value*, 32> > generatedTemporaries;
918 DominatorTree &DT = getAnalysis<DominatorTree>();
920 // Phase 1, Part 1: calculate AVAIL_OUT
922 // Top-down walk of the dominator tree
923 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
924 E = df_end(DT.getRootNode()); DI != E; ++DI) {
926 // Get the sets to update for this block
927 SmallPtrSet<Value*, 32>& currExps = generatedExpressions[DI->getBlock()];
928 SmallPtrSet<PHINode*, 32>& currPhis = generatedPhis[DI->getBlock()];
929 SmallPtrSet<Value*, 32>& currTemps = generatedTemporaries[DI->getBlock()];
930 SmallPtrSet<Value*, 32>& currAvail = availableOut[DI->getBlock()];
932 BasicBlock* BB = DI->getBlock();
934 // A block inherits AVAIL_OUT from its dominator
935 if (DI->getIDom() != 0)
936 currAvail.insert(availableOut[DI->getIDom()->getBlock()].begin(),
937 availableOut[DI->getIDom()->getBlock()].end());
940 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
942 buildsets_availout(BI, currAvail, currPhis, currExps, currTemps);
946 // If function has no exit blocks, only perform GVN
947 PostDominatorTree &PDT = getAnalysis<PostDominatorTree>();
948 if (PDT[&F.getEntryBlock()] == 0) {
949 bool changed_function = elimination();
952 if (changed_function)
953 return 2; // Bailed early, made changes
955 return 1; // Bailed early, no changes
959 // Phase 1, Part 2: calculate ANTIC_IN
961 std::set<BasicBlock*> visited;
964 unsigned iterations = 0;
967 SmallPtrSet<Value*, 32> anticOut;
969 // Top-down walk of the postdominator tree
970 for (df_iterator<DomTreeNode*> PDI =
971 df_begin(PDT.getRootNode()), E = df_end(PDT.getRootNode());
973 BasicBlock* BB = PDI->getBlock();
979 changed |= buildsets_anticin(BB, anticOut, generatedTemporaries[BB],
980 generatedExpressions[BB], visited);
986 return 0; // No bail, no changes
989 /// insertion_pre - When a partial redundancy has been identified, eliminate it
990 /// by inserting appropriate values into the predecessors and a phi node in
992 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
993 std::map<BasicBlock*, Value*>& avail,
994 SmallPtrSet<Value*, 32>& new_set) {
995 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
996 Value* e2 = avail[*PI];
997 if (!find_leader(availableOut[*PI], VN.lookup(e2))) {
998 User* U = cast<User>(e2);
1001 if (isa<BinaryOperator>(U->getOperand(0)) ||
1002 isa<CmpInst>(U->getOperand(0)))
1003 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1005 s1 = U->getOperand(0);
1008 if (isa<BinaryOperator>(U->getOperand(1)) ||
1009 isa<CmpInst>(U->getOperand(1)))
1010 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1012 s2 = U->getOperand(1);
1015 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1016 newVal = BinaryOperator::create(BO->getOpcode(), s1, s2,
1017 BO->getName()+".gvnpre",
1018 (*PI)->getTerminator());
1019 else if (CmpInst* C = dyn_cast<CmpInst>(U))
1020 newVal = CmpInst::create(C->getOpcode(), C->getPredicate(), s1, s2,
1021 C->getName()+".gvnpre",
1022 (*PI)->getTerminator());
1024 VN.add(newVal, VN.lookup(U));
1026 SmallPtrSet<Value*, 32>& predAvail = availableOut[*PI];
1027 val_replace(predAvail, newVal);
1029 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1030 if (av != avail.end())
1032 avail.insert(std::make_pair(*PI, newVal));
1040 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1042 p = new PHINode(avail[*PI]->getType(), "gvnpre-join", BB->begin());
1044 p->addIncoming(avail[*PI], *PI);
1047 VN.add(p, VN.lookup(e));
1048 val_replace(availableOut[BB], p);
1054 /// insertion_mergepoint - When walking the dom tree, check at each merge
1055 /// block for the possibility of a partial redundancy. If present, eliminate it
1056 unsigned GVNPRE::insertion_mergepoint(std::vector<Value*>& workList,
1057 df_iterator<DomTreeNode*> D,
1058 SmallPtrSet<Value*, 32>& new_set) {
1059 bool changed_function = false;
1060 bool new_stuff = false;
1062 BasicBlock* BB = D->getBlock();
1063 for (unsigned i = 0; i < workList.size(); ++i) {
1064 Value* e = workList[i];
1066 if (isa<BinaryOperator>(e) || isa<CmpInst>(e)) {
1067 if (find_leader(availableOut[D->getIDom()->getBlock()],
1071 std::map<BasicBlock*, Value*> avail;
1072 bool by_some = false;
1075 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1077 Value *e2 = phi_translate(e, *PI, BB);
1078 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1081 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1082 if (av != avail.end())
1084 avail.insert(std::make_pair(*PI, e2));
1086 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1087 if (av != avail.end())
1089 avail.insert(std::make_pair(*PI, e3));
1096 if (by_some && num_avail < std::distance(pred_begin(BB), pred_end(BB))) {
1097 insertion_pre(e, BB, avail, new_set);
1099 changed_function = true;
1105 unsigned retval = 0;
1106 if (changed_function)
1114 /// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for
1115 /// merge points. When one is found, check for a partial redundancy. If one is
1116 /// present, eliminate it. Repeat this walk until no changes are made.
1117 bool GVNPRE::insertion(Function& F) {
1118 bool changed_function = false;
1120 DominatorTree &DT = getAnalysis<DominatorTree>();
1122 std::map<BasicBlock*, SmallPtrSet<Value*, 32> > new_sets;
1123 bool new_stuff = true;
1126 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1127 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1128 BasicBlock* BB = DI->getBlock();
1133 SmallPtrSet<Value*, 32>& new_set = new_sets[BB];
1134 SmallPtrSet<Value*, 32>& availOut = availableOut[BB];
1135 SmallPtrSet<Value*, 32>& anticIn = anticipatedIn[BB];
1139 // Replace leaders with leaders inherited from dominator
1140 if (DI->getIDom() != 0) {
1141 SmallPtrSet<Value*, 32>& dom_set = new_sets[DI->getIDom()->getBlock()];
1142 for (SmallPtrSet<Value*, 32>::iterator I = dom_set.begin(),
1143 E = dom_set.end(); I != E; ++I) {
1145 val_replace(availOut, *I);
1149 // If there is more than one predecessor...
1150 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
1151 std::vector<Value*> workList;
1152 topo_sort(anticIn, workList);
1154 DOUT << "Merge Block: " << BB->getName() << "\n";
1155 DOUT << "ANTIC_IN: ";
1159 unsigned result = insertion_mergepoint(workList, DI, new_set);
1161 changed_function = true;
1168 return changed_function;
1171 // GVNPRE::runOnFunction - This is the main transformation entry point for a
1174 bool GVNPRE::runOnFunction(Function &F) {
1175 // Clean out global sets from any previous functions
1177 createdExpressions.clear();
1178 availableOut.clear();
1179 anticipatedIn.clear();
1181 bool changed_function = false;
1183 // Phase 1: BuildSets
1184 // This phase calculates the AVAIL_OUT and ANTIC_IN sets
1185 // NOTE: If full postdom information is no available, this will bail
1186 // early, performing GVN but not PRE
1187 unsigned bail = buildsets(F);
1188 //If a bail occurred, terminate early
1193 // This phase inserts values to make partially redundant values
1195 changed_function |= insertion(F);
1197 // Phase 3: Eliminate
1198 // This phase performs trivial full redundancy elimination
1199 changed_function |= elimination();
1202 // This phase cleans up values that were created solely
1203 // as leaders for expressions
1206 return changed_function;