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/BitVector.h"
29 #include "llvm/ADT/DenseMap.h"
30 #include "llvm/ADT/DepthFirstIterator.h"
31 #include "llvm/ADT/SmallPtrSet.h"
32 #include "llvm/ADT/Statistic.h"
33 #include "llvm/Support/CFG.h"
34 #include "llvm/Support/Compiler.h"
35 #include "llvm/Support/Debug.h"
43 //===----------------------------------------------------------------------===//
45 //===----------------------------------------------------------------------===//
47 /// This class holds the mapping between values and value numbers. It is used
48 /// as an efficient mechanism to determine the expression-wise equivalence of
52 class VISIBILITY_HIDDEN ValueTable {
55 enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
56 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
57 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
58 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
59 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
60 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
61 FCMPULT, FCMPULE, FCMPUNE };
63 ExpressionOpcode opcode;
67 bool operator< (const Expression& other) const {
68 if (opcode < other.opcode)
70 else if (opcode > other.opcode)
72 else if (leftVN < other.leftVN)
74 else if (leftVN > other.leftVN)
76 else if (rightVN < other.rightVN)
78 else if (rightVN > other.rightVN)
86 DenseMap<Value*, uint32_t> valueNumbering;
87 std::map<Expression, uint32_t> expressionNumbering;
89 std::set<Expression> maximalExpressions;
90 SmallPtrSet<Value*, 32> maximalValues;
92 uint32_t nextValueNumber;
94 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
95 Expression::ExpressionOpcode getOpcode(CmpInst* C);
96 Expression create_expression(BinaryOperator* BO);
97 Expression create_expression(CmpInst* C);
99 ValueTable() { nextValueNumber = 1; }
100 uint32_t lookup_or_add(Value* V);
101 uint32_t lookup(Value* V);
102 void add(Value* V, uint32_t num);
104 std::set<Expression>& getMaximalExpressions() {
105 return maximalExpressions;
108 SmallPtrSet<Value*, 32>& getMaximalValues() { return maximalValues; }
109 void erase(Value* v);
114 //===----------------------------------------------------------------------===//
115 // ValueTable Internal Functions
116 //===----------------------------------------------------------------------===//
117 ValueTable::Expression::ExpressionOpcode
118 ValueTable::getOpcode(BinaryOperator* BO) {
119 switch(BO->getOpcode()) {
120 case Instruction::Add:
121 return Expression::ADD;
122 case Instruction::Sub:
123 return Expression::SUB;
124 case Instruction::Mul:
125 return Expression::MUL;
126 case Instruction::UDiv:
127 return Expression::UDIV;
128 case Instruction::SDiv:
129 return Expression::SDIV;
130 case Instruction::FDiv:
131 return Expression::FDIV;
132 case Instruction::URem:
133 return Expression::UREM;
134 case Instruction::SRem:
135 return Expression::SREM;
136 case Instruction::FRem:
137 return Expression::FREM;
138 case Instruction::Shl:
139 return Expression::SHL;
140 case Instruction::LShr:
141 return Expression::LSHR;
142 case Instruction::AShr:
143 return Expression::ASHR;
144 case Instruction::And:
145 return Expression::AND;
146 case Instruction::Or:
147 return Expression::OR;
148 case Instruction::Xor:
149 return Expression::XOR;
151 // THIS SHOULD NEVER HAPPEN
153 assert(0 && "Binary operator with unknown opcode?");
154 return Expression::ADD;
158 ValueTable::Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
159 if (C->getOpcode() == Instruction::ICmp) {
160 switch (C->getPredicate()) {
161 case ICmpInst::ICMP_EQ:
162 return Expression::ICMPEQ;
163 case ICmpInst::ICMP_NE:
164 return Expression::ICMPNE;
165 case ICmpInst::ICMP_UGT:
166 return Expression::ICMPUGT;
167 case ICmpInst::ICMP_UGE:
168 return Expression::ICMPUGE;
169 case ICmpInst::ICMP_ULT:
170 return Expression::ICMPULT;
171 case ICmpInst::ICMP_ULE:
172 return Expression::ICMPULE;
173 case ICmpInst::ICMP_SGT:
174 return Expression::ICMPSGT;
175 case ICmpInst::ICMP_SGE:
176 return Expression::ICMPSGE;
177 case ICmpInst::ICMP_SLT:
178 return Expression::ICMPSLT;
179 case ICmpInst::ICMP_SLE:
180 return Expression::ICMPSLE;
182 // THIS SHOULD NEVER HAPPEN
184 assert(0 && "Comparison with unknown predicate?");
185 return Expression::ICMPEQ;
188 switch (C->getPredicate()) {
189 case FCmpInst::FCMP_OEQ:
190 return Expression::FCMPOEQ;
191 case FCmpInst::FCMP_OGT:
192 return Expression::FCMPOGT;
193 case FCmpInst::FCMP_OGE:
194 return Expression::FCMPOGE;
195 case FCmpInst::FCMP_OLT:
196 return Expression::FCMPOLT;
197 case FCmpInst::FCMP_OLE:
198 return Expression::FCMPOLE;
199 case FCmpInst::FCMP_ONE:
200 return Expression::FCMPONE;
201 case FCmpInst::FCMP_ORD:
202 return Expression::FCMPORD;
203 case FCmpInst::FCMP_UNO:
204 return Expression::FCMPUNO;
205 case FCmpInst::FCMP_UEQ:
206 return Expression::FCMPUEQ;
207 case FCmpInst::FCMP_UGT:
208 return Expression::FCMPUGT;
209 case FCmpInst::FCMP_UGE:
210 return Expression::FCMPUGE;
211 case FCmpInst::FCMP_ULT:
212 return Expression::FCMPULT;
213 case FCmpInst::FCMP_ULE:
214 return Expression::FCMPULE;
215 case FCmpInst::FCMP_UNE:
216 return Expression::FCMPUNE;
218 // THIS SHOULD NEVER HAPPEN
220 assert(0 && "Comparison with unknown predicate?");
221 return Expression::FCMPOEQ;
226 ValueTable::Expression ValueTable::create_expression(BinaryOperator* BO) {
229 e.leftVN = lookup_or_add(BO->getOperand(0));
230 e.rightVN = lookup_or_add(BO->getOperand(1));
231 e.opcode = getOpcode(BO);
233 maximalExpressions.insert(e);
238 ValueTable::Expression ValueTable::create_expression(CmpInst* C) {
241 e.leftVN = lookup_or_add(C->getOperand(0));
242 e.rightVN = lookup_or_add(C->getOperand(1));
243 e.opcode = getOpcode(C);
245 maximalExpressions.insert(e);
250 //===----------------------------------------------------------------------===//
251 // ValueTable External Functions
252 //===----------------------------------------------------------------------===//
254 /// lookup_or_add - Returns the value number for the specified value, assigning
255 /// it a new number if it did not have one before.
256 uint32_t ValueTable::lookup_or_add(Value* V) {
257 maximalValues.insert(V);
259 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
260 if (VI != valueNumbering.end())
264 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
265 Expression e = create_expression(BO);
267 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
268 if (EI != expressionNumbering.end()) {
269 valueNumbering.insert(std::make_pair(V, EI->second));
272 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
273 valueNumbering.insert(std::make_pair(V, nextValueNumber));
275 return nextValueNumber++;
277 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
278 Expression e = create_expression(C);
280 std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
281 if (EI != expressionNumbering.end()) {
282 valueNumbering.insert(std::make_pair(V, EI->second));
285 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
286 valueNumbering.insert(std::make_pair(V, nextValueNumber));
288 return nextValueNumber++;
291 valueNumbering.insert(std::make_pair(V, nextValueNumber));
292 return nextValueNumber++;
296 /// lookup - Returns the value number of the specified value. Fails if
297 /// the value has not yet been numbered.
298 uint32_t ValueTable::lookup(Value* V) {
299 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
300 if (VI != valueNumbering.end())
303 assert(0 && "Value not numbered?");
308 /// add - Add the specified value with the given value number, removing
309 /// its old number, if any
310 void ValueTable::add(Value* V, uint32_t num) {
311 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
312 if (VI != valueNumbering.end())
313 valueNumbering.erase(VI);
314 valueNumbering.insert(std::make_pair(V, num));
317 /// clear - Remove all entries from the ValueTable and the maximal sets
318 void ValueTable::clear() {
319 valueNumbering.clear();
320 expressionNumbering.clear();
321 maximalExpressions.clear();
322 maximalValues.clear();
326 /// erase - Remove a value from the value numbering and maximal sets
327 void ValueTable::erase(Value* V) {
328 maximalValues.erase(V);
329 valueNumbering.erase(V);
330 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V))
331 maximalExpressions.erase(create_expression(BO));
332 else if (CmpInst* C = dyn_cast<CmpInst>(V))
333 maximalExpressions.erase(create_expression(C));
336 /// size - Return the number of assigned value numbers
337 unsigned ValueTable::size() {
338 // NOTE: zero is never assigned
339 return nextValueNumber;
342 //===----------------------------------------------------------------------===//
344 //===----------------------------------------------------------------------===//
348 class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
349 bool runOnFunction(Function &F);
351 static char ID; // Pass identification, replacement for typeid
352 GVNPRE() : FunctionPass((intptr_t)&ID) { }
356 std::vector<Instruction*> createdExpressions;
358 std::map<BasicBlock*, SmallPtrSet<Value*, 32> > availableOut;
359 std::map<BasicBlock*, SmallPtrSet<Value*, 32> > anticipatedIn;
361 // This transformation requires dominator postdominator info
362 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
363 AU.setPreservesCFG();
364 AU.addRequired<DominatorTree>();
365 AU.addRequired<PostDominatorTree>();
369 // FIXME: eliminate or document these better
370 void dump(const SmallPtrSet<Value*, 32>& s) const;
371 void clean(SmallPtrSet<Value*, 32>& set);
372 Value* find_leader(SmallPtrSet<Value*, 32>& vals,
374 Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ);
375 void phi_translate_set(SmallPtrSet<Value*, 32>& anticIn, BasicBlock* pred,
376 BasicBlock* succ, SmallPtrSet<Value*, 32>& out);
378 void topo_sort(SmallPtrSet<Value*, 32>& set,
379 std::vector<Value*>& vec);
384 void val_insert(SmallPtrSet<Value*, 32>& s, Value* v);
385 void val_replace(SmallPtrSet<Value*, 32>& s, Value* v);
386 bool dependsOnInvoke(Value* V);
387 void buildsets_availout(BasicBlock::iterator I,
388 SmallPtrSet<Value*, 32>& currAvail,
389 SmallPtrSet<PHINode*, 32>& currPhis,
390 SmallPtrSet<Value*, 32>& currExps,
391 SmallPtrSet<Value*, 32>& currTemps,
392 BitVector& availNumbers,
393 BitVector& expNumbers);
394 bool buildsets_anticout(BasicBlock* BB,
395 SmallPtrSet<Value*, 32>& anticOut,
396 std::set<BasicBlock*>& visited);
397 unsigned buildsets_anticin(BasicBlock* BB,
398 SmallPtrSet<Value*, 32>& anticOut,
399 SmallPtrSet<Value*, 32>& currExps,
400 SmallPtrSet<Value*, 32>& currTemps,
401 std::set<BasicBlock*>& visited);
402 unsigned buildsets(Function& F);
404 void insertion_pre(Value* e, BasicBlock* BB,
405 std::map<BasicBlock*, Value*>& avail,
406 SmallPtrSet<Value*, 32>& new_set);
407 unsigned insertion_mergepoint(std::vector<Value*>& workList,
408 df_iterator<DomTreeNode*>& D,
409 SmallPtrSet<Value*, 32>& new_set);
410 bool insertion(Function& F);
418 // createGVNPREPass - The public interface to this file...
419 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
421 RegisterPass<GVNPRE> X("gvnpre",
422 "Global Value Numbering/Partial Redundancy Elimination");
425 STATISTIC(NumInsertedVals, "Number of values inserted");
426 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
427 STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
429 /// find_leader - Given a set and a value number, return the first
430 /// element of the set with that value number, or 0 if no such element
432 Value* GVNPRE::find_leader(SmallPtrSet<Value*, 32>& vals, uint32_t v) {
433 for (SmallPtrSet<Value*, 32>::iterator I = vals.begin(), E = vals.end();
435 if (v == VN.lookup(*I))
441 /// val_insert - Insert a value into a set only if there is not a value
442 /// with the same value number already in the set
443 void GVNPRE::val_insert(SmallPtrSet<Value*, 32>& s, Value* v) {
444 uint32_t num = VN.lookup(v);
445 Value* leader = find_leader(s, num);
450 /// val_replace - Insert a value into a set, replacing any values already in
451 /// the set that have the same value number
452 void GVNPRE::val_replace(SmallPtrSet<Value*, 32>& s, Value* v) {
453 uint32_t num = VN.lookup(v);
454 Value* leader = find_leader(s, num);
455 while (leader != 0) {
457 leader = find_leader(s, num);
462 /// phi_translate - Given a value, its parent block, and a predecessor of its
463 /// parent, translate the value into legal for the predecessor block. This
464 /// means translating its operands (and recursively, their operands) through
465 /// any phi nodes in the parent into values available in the predecessor
466 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
470 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
472 if (isa<Instruction>(BO->getOperand(0)))
473 newOp1 = phi_translate(find_leader(anticipatedIn[succ],
474 VN.lookup(BO->getOperand(0))),
477 newOp1 = BO->getOperand(0);
483 if (isa<Instruction>(BO->getOperand(1)))
484 newOp2 = phi_translate(find_leader(anticipatedIn[succ],
485 VN.lookup(BO->getOperand(1))),
488 newOp2 = BO->getOperand(1);
493 if (newOp1 != BO->getOperand(0) || newOp2 != BO->getOperand(1)) {
494 Instruction* newVal = BinaryOperator::create(BO->getOpcode(),
496 BO->getName()+".expr");
498 uint32_t v = VN.lookup_or_add(newVal);
500 Value* leader = find_leader(availableOut[pred], v);
502 createdExpressions.push_back(newVal);
510 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
511 if (P->getParent() == succ)
512 return P->getIncomingValueForBlock(pred);
513 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
515 if (isa<Instruction>(C->getOperand(0)))
516 newOp1 = phi_translate(find_leader(anticipatedIn[succ],
517 VN.lookup(C->getOperand(0))),
520 newOp1 = C->getOperand(0);
526 if (isa<Instruction>(C->getOperand(1)))
527 newOp2 = phi_translate(find_leader(anticipatedIn[succ],
528 VN.lookup(C->getOperand(1))),
531 newOp2 = C->getOperand(1);
536 if (newOp1 != C->getOperand(0) || newOp2 != C->getOperand(1)) {
537 Instruction* newVal = CmpInst::create(C->getOpcode(),
540 C->getName()+".expr");
542 uint32_t v = VN.lookup_or_add(newVal);
544 Value* leader = find_leader(availableOut[pred], v);
546 createdExpressions.push_back(newVal);
559 /// phi_translate_set - Perform phi translation on every element of a set
560 void GVNPRE::phi_translate_set(SmallPtrSet<Value*, 32>& anticIn,
561 BasicBlock* pred, BasicBlock* succ,
562 SmallPtrSet<Value*, 32>& out) {
563 for (SmallPtrSet<Value*, 32>::iterator I = anticIn.begin(),
564 E = anticIn.end(); I != E; ++I) {
565 Value* V = phi_translate(*I, pred, succ);
571 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of
572 /// whose inputs is an invoke instruction. If this is true, we cannot safely
573 /// PRE the instruction or anything that depends on it.
574 bool GVNPRE::dependsOnInvoke(Value* V) {
575 if (PHINode* p = dyn_cast<PHINode>(V)) {
576 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
577 if (isa<InvokeInst>(*I))
585 /// clean - Remove all non-opaque values from the set whose operands are not
586 /// themselves in the set, as well as all values that depend on invokes (see
588 void GVNPRE::clean(SmallPtrSet<Value*, 32>& set) {
589 std::vector<Value*> worklist;
590 worklist.reserve(set.size());
591 topo_sort(set, worklist);
593 for (unsigned i = 0; i < worklist.size(); ++i) {
594 Value* v = worklist[i];
596 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(v)) {
597 bool lhsValid = !isa<Instruction>(BO->getOperand(0));
599 for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
601 if (VN.lookup(*I) == VN.lookup(BO->getOperand(0))) {
606 lhsValid = !dependsOnInvoke(BO->getOperand(0));
608 bool rhsValid = !isa<Instruction>(BO->getOperand(1));
610 for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
612 if (VN.lookup(*I) == VN.lookup(BO->getOperand(1))) {
617 rhsValid = !dependsOnInvoke(BO->getOperand(1));
619 if (!lhsValid || !rhsValid)
621 } else if (CmpInst* C = dyn_cast<CmpInst>(v)) {
622 bool lhsValid = !isa<Instruction>(C->getOperand(0));
624 for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
626 if (VN.lookup(*I) == VN.lookup(C->getOperand(0))) {
631 lhsValid = !dependsOnInvoke(C->getOperand(0));
633 bool rhsValid = !isa<Instruction>(C->getOperand(1));
635 for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
637 if (VN.lookup(*I) == VN.lookup(C->getOperand(1))) {
642 rhsValid = !dependsOnInvoke(C->getOperand(1));
644 if (!lhsValid || !rhsValid)
650 /// topo_sort - Given a set of values, sort them by topological
651 /// order into the provided vector.
652 void GVNPRE::topo_sort(SmallPtrSet<Value*, 32>& set, std::vector<Value*>& vec) {
653 SmallPtrSet<Value*, 32> toErase;
654 for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
656 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(*I))
657 for (SmallPtrSet<Value*, 32>::iterator SI = set.begin(); SI != E; ++SI) {
658 if (VN.lookup(BO->getOperand(0)) == VN.lookup(*SI) ||
659 VN.lookup(BO->getOperand(1)) == VN.lookup(*SI)) {
663 else if (CmpInst* C = dyn_cast<CmpInst>(*I))
664 for (SmallPtrSet<Value*, 32>::iterator SI = set.begin(); SI != E; ++SI) {
665 if (VN.lookup(C->getOperand(0)) == VN.lookup(*SI) ||
666 VN.lookup(C->getOperand(1)) == VN.lookup(*SI)) {
672 std::vector<Value*> Q;
673 for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
675 if (toErase.count(*I) == 0)
679 SmallPtrSet<Value*, 32> visited;
683 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(e)) {
684 Value* l = find_leader(set, VN.lookup(BO->getOperand(0)));
685 Value* r = find_leader(set, VN.lookup(BO->getOperand(1)));
687 if (l != 0 && isa<Instruction>(l) &&
688 visited.count(l) == 0)
690 else if (r != 0 && isa<Instruction>(r) &&
691 visited.count(r) == 0)
698 } else if (CmpInst* C = dyn_cast<CmpInst>(e)) {
699 Value* l = find_leader(set, VN.lookup(C->getOperand(0)));
700 Value* r = find_leader(set, VN.lookup(C->getOperand(1)));
702 if (l != 0 && isa<Instruction>(l) &&
703 visited.count(l) == 0)
705 else if (r != 0 && isa<Instruction>(r) &&
706 visited.count(r) == 0)
721 /// dump - Dump a set of values to standard error
722 void GVNPRE::dump(const SmallPtrSet<Value*, 32>& s) const {
724 for (SmallPtrSet<Value*, 32>::iterator I = s.begin(), E = s.end();
731 /// elimination - Phase 3 of the main algorithm. Perform full redundancy
732 /// elimination by walking the dominator tree and removing any instruction that
733 /// is dominated by another instruction with the same value number.
734 bool GVNPRE::elimination() {
735 DOUT << "\n\nPhase 3: Elimination\n\n";
737 bool changed_function = false;
739 std::vector<std::pair<Instruction*, Value*> > replace;
740 std::vector<Instruction*> erase;
742 DominatorTree& DT = getAnalysis<DominatorTree>();
744 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
745 E = df_end(DT.getRootNode()); DI != E; ++DI) {
746 BasicBlock* BB = DI->getBlock();
748 DOUT << "Block: " << BB->getName() << "\n";
749 dump(availableOut[BB]);
752 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
755 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI)) {
756 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
759 if (Instruction* Instr = dyn_cast<Instruction>(leader))
760 if (Instr->getParent() != 0 && Instr != BI) {
761 replace.push_back(std::make_pair(BI, leader));
769 while (!replace.empty()) {
770 std::pair<Instruction*, Value*> rep = replace.back();
772 rep.first->replaceAllUsesWith(rep.second);
773 changed_function = true;
776 for (std::vector<Instruction*>::iterator I = erase.begin(), E = erase.end();
778 (*I)->eraseFromParent();
780 return changed_function;
783 /// cleanup - Delete any extraneous values that were created to represent
784 /// expressions without leaders.
785 void GVNPRE::cleanup() {
786 while (!createdExpressions.empty()) {
787 Instruction* I = createdExpressions.back();
788 createdExpressions.pop_back();
794 /// buildsets_availout - When calculating availability, handle an instruction
795 /// by inserting it into the appropriate sets
796 void GVNPRE::buildsets_availout(BasicBlock::iterator I,
797 SmallPtrSet<Value*, 32>& currAvail,
798 SmallPtrSet<PHINode*, 32>& currPhis,
799 SmallPtrSet<Value*, 32>& currExps,
800 SmallPtrSet<Value*, 32>& currTemps,
801 BitVector& availNumbers,
802 BitVector& expNumbers) {
803 // Handle PHI nodes...
804 if (PHINode* p = dyn_cast<PHINode>(I)) {
806 expNumbers.resize(VN.size());
807 availNumbers.resize(VN.size());
811 // Handle binary ops...
812 } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(I)) {
813 Value* leftValue = BO->getOperand(0);
814 Value* rightValue = BO->getOperand(1);
816 unsigned num = VN.lookup_or_add(BO);
817 expNumbers.resize(VN.size());
818 availNumbers.resize(VN.size());
820 if (isa<Instruction>(leftValue))
821 if (!expNumbers.test(VN.lookup(leftValue)-1)) {
822 currExps.insert(leftValue);
823 expNumbers.set(VN.lookup(leftValue)-1);
826 if (isa<Instruction>(rightValue))
827 if (!expNumbers.test(VN.lookup(rightValue)-1)) {
828 currExps.insert(rightValue);
829 expNumbers.set(VN.lookup(rightValue)-1);
832 if (!expNumbers.test(VN.lookup(BO)-1)) {
834 expNumbers.set(num-1);
838 } else if (CmpInst* C = dyn_cast<CmpInst>(I)) {
839 Value* leftValue = C->getOperand(0);
840 Value* rightValue = C->getOperand(1);
844 unsigned num = VN.lookup_or_add(C);
845 expNumbers.resize(VN.size());
846 availNumbers.resize(VN.size());
848 if (isa<Instruction>(leftValue))
849 if (!expNumbers.test(VN.lookup(leftValue)-1)) {
850 currExps.insert(leftValue);
851 expNumbers.set(VN.lookup(leftValue)-1);
853 if (isa<Instruction>(rightValue))
854 if (!expNumbers.test(VN.lookup(rightValue)-1)) {
855 currExps.insert(rightValue);
856 expNumbers.set(VN.lookup(rightValue)-1);
859 if (!expNumbers.test(VN.lookup(C)-1)) {
861 expNumbers.set(num-1);
864 // Handle unsupported ops
865 } else if (!I->isTerminator()){
867 expNumbers.resize(VN.size());
868 availNumbers.resize(VN.size());
873 if (!I->isTerminator())
874 if (!availNumbers.test(VN.lookup(I)-1)) {
876 availNumbers.set(VN.lookup(I)-1);
880 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
881 /// set as a function of the ANTIC_IN set of the block's predecessors
882 bool GVNPRE::buildsets_anticout(BasicBlock* BB,
883 SmallPtrSet<Value*, 32>& anticOut,
884 std::set<BasicBlock*>& visited) {
885 if (BB->getTerminator()->getNumSuccessors() == 1) {
886 if (visited.count(BB->getTerminator()->getSuccessor(0)) == 0)
889 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
890 BB, BB->getTerminator()->getSuccessor(0), anticOut);
891 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
892 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
893 anticOut.insert(anticipatedIn[first].begin(), anticipatedIn[first].end());
895 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
896 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
897 SmallPtrSet<Value*, 32>& succAnticIn = anticipatedIn[currSucc];
899 std::vector<Value*> temp;
901 for (SmallPtrSet<Value*, 32>::iterator I = anticOut.begin(),
902 E = anticOut.end(); I != E; ++I)
903 if (succAnticIn.count(*I) == 0)
906 for (std::vector<Value*>::iterator I = temp.begin(), E = temp.end();
915 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
916 /// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN
917 /// sets populated in buildsets_availout
918 unsigned GVNPRE::buildsets_anticin(BasicBlock* BB,
919 SmallPtrSet<Value*, 32>& anticOut,
920 SmallPtrSet<Value*, 32>& currExps,
921 SmallPtrSet<Value*, 32>& currTemps,
922 std::set<BasicBlock*>& visited) {
923 SmallPtrSet<Value*, 32>& anticIn = anticipatedIn[BB];
924 SmallPtrSet<Value*, 32> old (anticIn.begin(), anticIn.end());
926 bool defer = buildsets_anticout(BB, anticOut, visited);
930 SmallPtrSet<Value*, 32> S;
931 for (SmallPtrSet<Value*, 32>::iterator I = anticOut.begin(),
932 E = anticOut.end(); I != E; ++I)
933 if (currTemps.count(*I) == 0)
938 for (SmallPtrSet<Value*, 32>::iterator I = currExps.begin(),
939 E = currExps.end(); I != E; ++I)
940 if (currTemps.count(*I) == 0)
943 BitVector numbers(VN.size());
944 for (SmallPtrSet<Value*, 32>::iterator I = anticIn.begin(),
945 E = anticIn.end(); I != E; ++I)
946 numbers.set(VN.lookup(*I)-1);
947 for (SmallPtrSet<Value*, 32>::iterator I = S.begin(), E = S.end();
949 // For non-opaque values, we should already have a value numbering.
950 // However, for opaques, such as constants within PHI nodes, it is
951 // possible that they have not yet received a number. Make sure they do
953 if (!isa<BinaryOperator>(*I) && !isa<CmpInst>(*I))
954 VN.lookup_or_add(*I);
955 if (!numbers.test(VN.lookup(*I)-1))
962 if (old.size() != anticIn.size())
968 /// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT
969 /// and the ANTIC_IN sets.
970 unsigned GVNPRE::buildsets(Function& F) {
971 std::map<BasicBlock*, SmallPtrSet<Value*, 32> > generatedExpressions;
972 std::map<BasicBlock*, SmallPtrSet<PHINode*, 32> > generatedPhis;
973 std::map<BasicBlock*, SmallPtrSet<Value*, 32> > generatedTemporaries;
975 DominatorTree &DT = getAnalysis<DominatorTree>();
977 // Phase 1, Part 1: calculate AVAIL_OUT
979 // Top-down walk of the dominator tree
980 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
981 E = df_end(DT.getRootNode()); DI != E; ++DI) {
983 // Get the sets to update for this block
984 SmallPtrSet<Value*, 32>& currExps = generatedExpressions[DI->getBlock()];
985 SmallPtrSet<PHINode*, 32>& currPhis = generatedPhis[DI->getBlock()];
986 SmallPtrSet<Value*, 32>& currTemps = generatedTemporaries[DI->getBlock()];
987 SmallPtrSet<Value*, 32>& currAvail = availableOut[DI->getBlock()];
989 BasicBlock* BB = DI->getBlock();
991 // A block inherits AVAIL_OUT from its dominator
992 if (DI->getIDom() != 0)
993 currAvail.insert(availableOut[DI->getIDom()->getBlock()].begin(),
994 availableOut[DI->getIDom()->getBlock()].end());
996 BitVector availNumbers(VN.size());
997 for (SmallPtrSet<Value*, 32>::iterator I = currAvail.begin(),
998 E = currAvail.end(); I != E; ++I)
999 availNumbers.set(VN.lookup(*I));
1001 BitVector expNumbers(VN.size());
1002 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1004 buildsets_availout(BI, currAvail, currPhis, currExps,
1005 currTemps, availNumbers, expNumbers);
1009 // If function has no exit blocks, only perform GVN
1010 PostDominatorTree &PDT = getAnalysis<PostDominatorTree>();
1011 if (PDT[&F.getEntryBlock()] == 0) {
1012 bool changed_function = elimination();
1015 if (changed_function)
1016 return 2; // Bailed early, made changes
1018 return 1; // Bailed early, no changes
1022 // Phase 1, Part 2: calculate ANTIC_IN
1024 std::set<BasicBlock*> visited;
1026 bool changed = true;
1027 unsigned iterations = 0;
1030 SmallPtrSet<Value*, 32> anticOut;
1032 // Top-down walk of the postdominator tree
1033 for (df_iterator<DomTreeNode*> PDI =
1034 df_begin(PDT.getRootNode()), E = df_end(PDT.getRootNode());
1036 BasicBlock* BB = PDI->getBlock();
1042 unsigned ret = buildsets_anticin(BB, anticOut, generatedTemporaries[BB],
1043 generatedExpressions[BB], visited);
1050 changed |= (ret == 2);
1057 return 0; // No bail, no changes
1060 /// insertion_pre - When a partial redundancy has been identified, eliminate it
1061 /// by inserting appropriate values into the predecessors and a phi node in
1063 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
1064 std::map<BasicBlock*, Value*>& avail,
1065 SmallPtrSet<Value*, 32>& new_set) {
1066 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1067 Value* e2 = avail[*PI];
1068 if (!find_leader(availableOut[*PI], VN.lookup(e2))) {
1069 User* U = cast<User>(e2);
1072 if (isa<BinaryOperator>(U->getOperand(0)) ||
1073 isa<CmpInst>(U->getOperand(0)))
1074 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1076 s1 = U->getOperand(0);
1079 if (isa<BinaryOperator>(U->getOperand(1)) ||
1080 isa<CmpInst>(U->getOperand(1)))
1081 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1083 s2 = U->getOperand(1);
1086 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1087 newVal = BinaryOperator::create(BO->getOpcode(), s1, s2,
1088 BO->getName()+".gvnpre",
1089 (*PI)->getTerminator());
1090 else if (CmpInst* C = dyn_cast<CmpInst>(U))
1091 newVal = CmpInst::create(C->getOpcode(), C->getPredicate(), s1, s2,
1092 C->getName()+".gvnpre",
1093 (*PI)->getTerminator());
1095 VN.add(newVal, VN.lookup(U));
1097 SmallPtrSet<Value*, 32>& predAvail = availableOut[*PI];
1098 val_replace(predAvail, newVal);
1100 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1101 if (av != avail.end())
1103 avail.insert(std::make_pair(*PI, newVal));
1111 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1113 p = new PHINode(avail[*PI]->getType(), "gvnpre-join", BB->begin());
1115 p->addIncoming(avail[*PI], *PI);
1118 VN.add(p, VN.lookup(e));
1119 val_replace(availableOut[BB], p);
1125 /// insertion_mergepoint - When walking the dom tree, check at each merge
1126 /// block for the possibility of a partial redundancy. If present, eliminate it
1127 unsigned GVNPRE::insertion_mergepoint(std::vector<Value*>& workList,
1128 df_iterator<DomTreeNode*>& D,
1129 SmallPtrSet<Value*, 32>& new_set) {
1130 bool changed_function = false;
1131 bool new_stuff = false;
1133 BasicBlock* BB = D->getBlock();
1134 for (unsigned i = 0; i < workList.size(); ++i) {
1135 Value* e = workList[i];
1137 if (isa<BinaryOperator>(e) || isa<CmpInst>(e)) {
1138 if (find_leader(availableOut[D->getIDom()->getBlock()],
1142 std::map<BasicBlock*, Value*> avail;
1143 bool by_some = false;
1146 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1148 Value *e2 = phi_translate(e, *PI, BB);
1149 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1152 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1153 if (av != avail.end())
1155 avail.insert(std::make_pair(*PI, e2));
1157 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1158 if (av != avail.end())
1160 avail.insert(std::make_pair(*PI, e3));
1167 if (by_some && num_avail < std::distance(pred_begin(BB), pred_end(BB))) {
1168 insertion_pre(e, BB, avail, new_set);
1170 changed_function = true;
1176 unsigned retval = 0;
1177 if (changed_function)
1185 /// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for
1186 /// merge points. When one is found, check for a partial redundancy. If one is
1187 /// present, eliminate it. Repeat this walk until no changes are made.
1188 bool GVNPRE::insertion(Function& F) {
1189 bool changed_function = false;
1191 DominatorTree &DT = getAnalysis<DominatorTree>();
1193 std::map<BasicBlock*, SmallPtrSet<Value*, 32> > new_sets;
1194 bool new_stuff = true;
1197 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1198 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1199 BasicBlock* BB = DI->getBlock();
1204 SmallPtrSet<Value*, 32>& new_set = new_sets[BB];
1205 SmallPtrSet<Value*, 32>& availOut = availableOut[BB];
1206 SmallPtrSet<Value*, 32>& anticIn = anticipatedIn[BB];
1210 // Replace leaders with leaders inherited from dominator
1211 if (DI->getIDom() != 0) {
1212 SmallPtrSet<Value*, 32>& dom_set = new_sets[DI->getIDom()->getBlock()];
1213 for (SmallPtrSet<Value*, 32>::iterator I = dom_set.begin(),
1214 E = dom_set.end(); I != E; ++I) {
1216 val_replace(availOut, *I);
1220 // If there is more than one predecessor...
1221 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
1222 std::vector<Value*> workList;
1223 workList.reserve(anticIn.size());
1224 topo_sort(anticIn, workList);
1226 DOUT << "Merge Block: " << BB->getName() << "\n";
1227 DOUT << "ANTIC_IN: ";
1231 unsigned result = insertion_mergepoint(workList, DI, new_set);
1233 changed_function = true;
1240 return changed_function;
1243 // GVNPRE::runOnFunction - This is the main transformation entry point for a
1246 bool GVNPRE::runOnFunction(Function &F) {
1247 // Clean out global sets from any previous functions
1249 createdExpressions.clear();
1250 availableOut.clear();
1251 anticipatedIn.clear();
1253 bool changed_function = false;
1255 // Phase 1: BuildSets
1256 // This phase calculates the AVAIL_OUT and ANTIC_IN sets
1257 // NOTE: If full postdom information is no available, this will bail
1258 // early, performing GVN but not PRE
1259 unsigned bail = buildsets(F);
1260 //If a bail occurred, terminate early
1265 // This phase inserts values to make partially redundant values
1267 changed_function |= insertion(F);
1269 // Phase 3: Eliminate
1270 // This phase performs trivial full redundancy elimination
1271 changed_function |= elimination();
1274 // This phase cleans up values that were created solely
1275 // as leaders for expressions
1278 return changed_function;