1 //===- GVNPRE.cpp - Eliminate redundant values and expressions ------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // 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 // Note that this pass does the value numbering itself, it does not use the
20 // ValueNumbering analysis passes.
22 //===----------------------------------------------------------------------===//
24 #define DEBUG_TYPE "gvnpre"
25 #include "llvm/Value.h"
26 #include "llvm/Transforms/Scalar.h"
27 #include "llvm/Instructions.h"
28 #include "llvm/Function.h"
29 #include "llvm/DerivedTypes.h"
30 #include "llvm/Analysis/Dominators.h"
31 #include "llvm/ADT/BitVector.h"
32 #include "llvm/ADT/DenseMap.h"
33 #include "llvm/ADT/DepthFirstIterator.h"
34 #include "llvm/ADT/PostOrderIterator.h"
35 #include "llvm/ADT/SmallPtrSet.h"
36 #include "llvm/ADT/SmallVector.h"
37 #include "llvm/ADT/Statistic.h"
38 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
39 #include "llvm/Support/CFG.h"
40 #include "llvm/Support/Compiler.h"
41 #include "llvm/Support/Debug.h"
47 //===----------------------------------------------------------------------===//
49 //===----------------------------------------------------------------------===//
53 /// This class holds the mapping between values and value numbers. It is used
54 /// as an efficient mechanism to determine the expression-wise equivalence of
58 enum ExpressionOpcode { ADD, FADD, SUB, FSUB, MUL, FMUL,
59 UDIV, SDIV, FDIV, UREM, SREM,
60 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
61 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
62 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
63 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
64 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
65 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
66 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
67 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
68 PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY,
71 ExpressionOpcode opcode;
76 SmallVector<uint32_t, 4> varargs;
79 explicit Expression(ExpressionOpcode o) : opcode(o) { }
81 bool operator==(const Expression &other) const {
82 if (opcode != other.opcode)
84 else if (opcode == EMPTY || opcode == TOMBSTONE)
86 else if (type != other.type)
88 else if (firstVN != other.firstVN)
90 else if (secondVN != other.secondVN)
92 else if (thirdVN != other.thirdVN)
95 if (varargs.size() != other.varargs.size())
98 for (size_t i = 0; i < varargs.size(); ++i)
99 if (varargs[i] != other.varargs[i])
106 bool operator!=(const Expression &other) const {
107 if (opcode != other.opcode)
109 else if (opcode == EMPTY || opcode == TOMBSTONE)
111 else if (type != other.type)
113 else if (firstVN != other.firstVN)
115 else if (secondVN != other.secondVN)
117 else if (thirdVN != other.thirdVN)
120 if (varargs.size() != other.varargs.size())
123 for (size_t i = 0; i < varargs.size(); ++i)
124 if (varargs[i] != other.varargs[i])
135 class VISIBILITY_HIDDEN ValueTable {
137 DenseMap<Value*, uint32_t> valueNumbering;
138 DenseMap<Expression, uint32_t> expressionNumbering;
140 uint32_t nextValueNumber;
142 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
143 Expression::ExpressionOpcode getOpcode(CmpInst* C);
144 Expression::ExpressionOpcode getOpcode(CastInst* C);
145 Expression create_expression(BinaryOperator* BO);
146 Expression create_expression(CmpInst* C);
147 Expression create_expression(ShuffleVectorInst* V);
148 Expression create_expression(ExtractElementInst* C);
149 Expression create_expression(InsertElementInst* V);
150 Expression create_expression(SelectInst* V);
151 Expression create_expression(CastInst* C);
152 Expression create_expression(GetElementPtrInst* G);
154 ValueTable() { nextValueNumber = 1; }
155 uint32_t lookup_or_add(Value* V);
156 uint32_t lookup(Value* V) const;
157 void add(Value* V, uint32_t num);
159 void erase(Value* v);
165 template <> struct DenseMapInfo<Expression> {
166 static inline Expression getEmptyKey() {
167 return Expression(Expression::EMPTY);
170 static inline Expression getTombstoneKey() {
171 return Expression(Expression::TOMBSTONE);
174 static unsigned getHashValue(const Expression e) {
175 unsigned hash = e.opcode;
177 hash = e.firstVN + hash * 37;
178 hash = e.secondVN + hash * 37;
179 hash = e.thirdVN + hash * 37;
181 hash = ((unsigned)((uintptr_t)e.type >> 4) ^
182 (unsigned)((uintptr_t)e.type >> 9)) +
185 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
186 E = e.varargs.end(); I != E; ++I)
187 hash = *I + hash * 37;
191 static bool isEqual(const Expression &LHS, const Expression &RHS) {
194 static bool isPod() { return true; }
198 //===----------------------------------------------------------------------===//
199 // ValueTable Internal Functions
200 //===----------------------------------------------------------------------===//
201 Expression::ExpressionOpcode
202 ValueTable::getOpcode(BinaryOperator* BO) {
203 switch(BO->getOpcode()) {
204 case Instruction::Add:
205 return Expression::ADD;
206 case Instruction::FAdd:
207 return Expression::FADD;
208 case Instruction::Sub:
209 return Expression::SUB;
210 case Instruction::FSub:
211 return Expression::FSUB;
212 case Instruction::Mul:
213 return Expression::MUL;
214 case Instruction::FMul:
215 return Expression::FMUL;
216 case Instruction::UDiv:
217 return Expression::UDIV;
218 case Instruction::SDiv:
219 return Expression::SDIV;
220 case Instruction::FDiv:
221 return Expression::FDIV;
222 case Instruction::URem:
223 return Expression::UREM;
224 case Instruction::SRem:
225 return Expression::SREM;
226 case Instruction::FRem:
227 return Expression::FREM;
228 case Instruction::Shl:
229 return Expression::SHL;
230 case Instruction::LShr:
231 return Expression::LSHR;
232 case Instruction::AShr:
233 return Expression::ASHR;
234 case Instruction::And:
235 return Expression::AND;
236 case Instruction::Or:
237 return Expression::OR;
238 case Instruction::Xor:
239 return Expression::XOR;
241 // THIS SHOULD NEVER HAPPEN
243 assert(0 && "Binary operator with unknown opcode?");
244 return Expression::ADD;
248 Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
249 if (C->getOpcode() == Instruction::ICmp) {
250 switch (C->getPredicate()) {
251 case ICmpInst::ICMP_EQ:
252 return Expression::ICMPEQ;
253 case ICmpInst::ICMP_NE:
254 return Expression::ICMPNE;
255 case ICmpInst::ICMP_UGT:
256 return Expression::ICMPUGT;
257 case ICmpInst::ICMP_UGE:
258 return Expression::ICMPUGE;
259 case ICmpInst::ICMP_ULT:
260 return Expression::ICMPULT;
261 case ICmpInst::ICMP_ULE:
262 return Expression::ICMPULE;
263 case ICmpInst::ICMP_SGT:
264 return Expression::ICMPSGT;
265 case ICmpInst::ICMP_SGE:
266 return Expression::ICMPSGE;
267 case ICmpInst::ICMP_SLT:
268 return Expression::ICMPSLT;
269 case ICmpInst::ICMP_SLE:
270 return Expression::ICMPSLE;
272 // THIS SHOULD NEVER HAPPEN
274 assert(0 && "Comparison with unknown predicate?");
275 return Expression::ICMPEQ;
278 switch (C->getPredicate()) {
279 case FCmpInst::FCMP_OEQ:
280 return Expression::FCMPOEQ;
281 case FCmpInst::FCMP_OGT:
282 return Expression::FCMPOGT;
283 case FCmpInst::FCMP_OGE:
284 return Expression::FCMPOGE;
285 case FCmpInst::FCMP_OLT:
286 return Expression::FCMPOLT;
287 case FCmpInst::FCMP_OLE:
288 return Expression::FCMPOLE;
289 case FCmpInst::FCMP_ONE:
290 return Expression::FCMPONE;
291 case FCmpInst::FCMP_ORD:
292 return Expression::FCMPORD;
293 case FCmpInst::FCMP_UNO:
294 return Expression::FCMPUNO;
295 case FCmpInst::FCMP_UEQ:
296 return Expression::FCMPUEQ;
297 case FCmpInst::FCMP_UGT:
298 return Expression::FCMPUGT;
299 case FCmpInst::FCMP_UGE:
300 return Expression::FCMPUGE;
301 case FCmpInst::FCMP_ULT:
302 return Expression::FCMPULT;
303 case FCmpInst::FCMP_ULE:
304 return Expression::FCMPULE;
305 case FCmpInst::FCMP_UNE:
306 return Expression::FCMPUNE;
308 // THIS SHOULD NEVER HAPPEN
310 assert(0 && "Comparison with unknown predicate?");
311 return Expression::FCMPOEQ;
316 Expression::ExpressionOpcode
317 ValueTable::getOpcode(CastInst* C) {
318 switch(C->getOpcode()) {
319 case Instruction::Trunc:
320 return Expression::TRUNC;
321 case Instruction::ZExt:
322 return Expression::ZEXT;
323 case Instruction::SExt:
324 return Expression::SEXT;
325 case Instruction::FPToUI:
326 return Expression::FPTOUI;
327 case Instruction::FPToSI:
328 return Expression::FPTOSI;
329 case Instruction::UIToFP:
330 return Expression::UITOFP;
331 case Instruction::SIToFP:
332 return Expression::SITOFP;
333 case Instruction::FPTrunc:
334 return Expression::FPTRUNC;
335 case Instruction::FPExt:
336 return Expression::FPEXT;
337 case Instruction::PtrToInt:
338 return Expression::PTRTOINT;
339 case Instruction::IntToPtr:
340 return Expression::INTTOPTR;
341 case Instruction::BitCast:
342 return Expression::BITCAST;
344 // THIS SHOULD NEVER HAPPEN
346 assert(0 && "Cast operator with unknown opcode?");
347 return Expression::BITCAST;
351 Expression ValueTable::create_expression(BinaryOperator* BO) {
354 e.firstVN = lookup_or_add(BO->getOperand(0));
355 e.secondVN = lookup_or_add(BO->getOperand(1));
357 e.type = BO->getType();
358 e.opcode = getOpcode(BO);
363 Expression ValueTable::create_expression(CmpInst* C) {
366 e.firstVN = lookup_or_add(C->getOperand(0));
367 e.secondVN = lookup_or_add(C->getOperand(1));
369 e.type = C->getType();
370 e.opcode = getOpcode(C);
375 Expression ValueTable::create_expression(CastInst* C) {
378 e.firstVN = lookup_or_add(C->getOperand(0));
381 e.type = C->getType();
382 e.opcode = getOpcode(C);
387 Expression ValueTable::create_expression(ShuffleVectorInst* S) {
390 e.firstVN = lookup_or_add(S->getOperand(0));
391 e.secondVN = lookup_or_add(S->getOperand(1));
392 e.thirdVN = lookup_or_add(S->getOperand(2));
393 e.type = S->getType();
394 e.opcode = Expression::SHUFFLE;
399 Expression ValueTable::create_expression(ExtractElementInst* E) {
402 e.firstVN = lookup_or_add(E->getOperand(0));
403 e.secondVN = lookup_or_add(E->getOperand(1));
405 e.type = E->getType();
406 e.opcode = Expression::EXTRACT;
411 Expression ValueTable::create_expression(InsertElementInst* I) {
414 e.firstVN = lookup_or_add(I->getOperand(0));
415 e.secondVN = lookup_or_add(I->getOperand(1));
416 e.thirdVN = lookup_or_add(I->getOperand(2));
417 e.type = I->getType();
418 e.opcode = Expression::INSERT;
423 Expression ValueTable::create_expression(SelectInst* I) {
426 e.firstVN = lookup_or_add(I->getCondition());
427 e.secondVN = lookup_or_add(I->getTrueValue());
428 e.thirdVN = lookup_or_add(I->getFalseValue());
429 e.type = I->getType();
430 e.opcode = Expression::SELECT;
435 Expression ValueTable::create_expression(GetElementPtrInst* G) {
438 e.firstVN = lookup_or_add(G->getPointerOperand());
441 e.type = G->getType();
442 e.opcode = Expression::GEP;
444 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
446 e.varargs.push_back(lookup_or_add(*I));
451 //===----------------------------------------------------------------------===//
452 // ValueTable External Functions
453 //===----------------------------------------------------------------------===//
455 /// lookup_or_add - Returns the value number for the specified value, assigning
456 /// it a new number if it did not have one before.
457 uint32_t ValueTable::lookup_or_add(Value* V) {
458 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
459 if (VI != valueNumbering.end())
463 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
464 Expression e = create_expression(BO);
466 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
467 if (EI != expressionNumbering.end()) {
468 valueNumbering.insert(std::make_pair(V, EI->second));
471 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
472 valueNumbering.insert(std::make_pair(V, nextValueNumber));
474 return nextValueNumber++;
476 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
477 Expression e = create_expression(C);
479 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
480 if (EI != expressionNumbering.end()) {
481 valueNumbering.insert(std::make_pair(V, EI->second));
484 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
485 valueNumbering.insert(std::make_pair(V, nextValueNumber));
487 return nextValueNumber++;
489 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
490 Expression e = create_expression(U);
492 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
493 if (EI != expressionNumbering.end()) {
494 valueNumbering.insert(std::make_pair(V, EI->second));
497 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
498 valueNumbering.insert(std::make_pair(V, nextValueNumber));
500 return nextValueNumber++;
502 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
503 Expression e = create_expression(U);
505 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
506 if (EI != expressionNumbering.end()) {
507 valueNumbering.insert(std::make_pair(V, EI->second));
510 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
511 valueNumbering.insert(std::make_pair(V, nextValueNumber));
513 return nextValueNumber++;
515 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
516 Expression e = create_expression(U);
518 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
519 if (EI != expressionNumbering.end()) {
520 valueNumbering.insert(std::make_pair(V, EI->second));
523 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
524 valueNumbering.insert(std::make_pair(V, nextValueNumber));
526 return nextValueNumber++;
528 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
529 Expression e = create_expression(U);
531 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
532 if (EI != expressionNumbering.end()) {
533 valueNumbering.insert(std::make_pair(V, EI->second));
536 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
537 valueNumbering.insert(std::make_pair(V, nextValueNumber));
539 return nextValueNumber++;
541 } else if (CastInst* U = dyn_cast<CastInst>(V)) {
542 Expression e = create_expression(U);
544 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
545 if (EI != expressionNumbering.end()) {
546 valueNumbering.insert(std::make_pair(V, EI->second));
549 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
550 valueNumbering.insert(std::make_pair(V, nextValueNumber));
552 return nextValueNumber++;
554 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
555 Expression e = create_expression(U);
557 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
558 if (EI != expressionNumbering.end()) {
559 valueNumbering.insert(std::make_pair(V, EI->second));
562 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
563 valueNumbering.insert(std::make_pair(V, nextValueNumber));
565 return nextValueNumber++;
568 valueNumbering.insert(std::make_pair(V, nextValueNumber));
569 return nextValueNumber++;
573 /// lookup - Returns the value number of the specified value. Fails if
574 /// the value has not yet been numbered.
575 uint32_t ValueTable::lookup(Value* V) const {
576 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
577 if (VI != valueNumbering.end())
580 assert(0 && "Value not numbered?");
585 /// add - Add the specified value with the given value number, removing
586 /// its old number, if any
587 void ValueTable::add(Value* V, uint32_t num) {
588 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
589 if (VI != valueNumbering.end())
590 valueNumbering.erase(VI);
591 valueNumbering.insert(std::make_pair(V, num));
594 /// clear - Remove all entries from the ValueTable
595 void ValueTable::clear() {
596 valueNumbering.clear();
597 expressionNumbering.clear();
601 /// erase - Remove a value from the value numbering
602 void ValueTable::erase(Value* V) {
603 valueNumbering.erase(V);
606 /// size - Return the number of assigned value numbers
607 unsigned ValueTable::size() {
608 // NOTE: zero is never assigned
609 return nextValueNumber;
614 //===----------------------------------------------------------------------===//
615 // ValueNumberedSet Class
616 //===----------------------------------------------------------------------===//
618 class ValueNumberedSet {
620 SmallPtrSet<Value*, 8> contents;
623 ValueNumberedSet() { numbers.resize(1); }
624 ValueNumberedSet(const ValueNumberedSet& other) {
625 numbers = other.numbers;
626 contents = other.contents;
629 typedef SmallPtrSet<Value*, 8>::iterator iterator;
631 iterator begin() { return contents.begin(); }
632 iterator end() { return contents.end(); }
634 bool insert(Value* v) { return contents.insert(v); }
635 void insert(iterator I, iterator E) { contents.insert(I, E); }
636 void erase(Value* v) { contents.erase(v); }
637 unsigned count(Value* v) { return contents.count(v); }
638 size_t size() { return contents.size(); }
640 void set(unsigned i) {
641 if (i >= numbers.size())
647 void operator=(const ValueNumberedSet& other) {
648 contents = other.contents;
649 numbers = other.numbers;
652 void reset(unsigned i) {
653 if (i < numbers.size())
657 bool test(unsigned i) {
658 if (i >= numbers.size())
661 return numbers.test(i);
672 //===----------------------------------------------------------------------===//
674 //===----------------------------------------------------------------------===//
678 class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
679 bool runOnFunction(Function &F);
681 static char ID; // Pass identification, replacement for typeid
682 GVNPRE() : FunctionPass(&ID) {}
686 SmallVector<Instruction*, 8> createdExpressions;
688 DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
689 DenseMap<BasicBlock*, ValueNumberedSet> anticipatedIn;
690 DenseMap<BasicBlock*, ValueNumberedSet> generatedPhis;
692 // This transformation requires dominator postdominator info
693 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
694 AU.setPreservesCFG();
695 AU.addRequiredID(BreakCriticalEdgesID);
696 AU.addRequired<UnifyFunctionExitNodes>();
697 AU.addRequired<DominatorTree>();
701 // FIXME: eliminate or document these better
702 void dump(ValueNumberedSet& s) const ;
703 void clean(ValueNumberedSet& set) ;
704 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ;
705 Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) ;
706 void phi_translate_set(ValueNumberedSet& anticIn, BasicBlock* pred,
707 BasicBlock* succ, ValueNumberedSet& out) ;
709 void topo_sort(ValueNumberedSet& set,
710 SmallVector<Value*, 8>& vec) ;
715 void val_insert(ValueNumberedSet& s, Value* v) ;
716 void val_replace(ValueNumberedSet& s, Value* v) ;
717 bool dependsOnInvoke(Value* V) ;
718 void buildsets_availout(BasicBlock::iterator I,
719 ValueNumberedSet& currAvail,
720 ValueNumberedSet& currPhis,
721 ValueNumberedSet& currExps,
722 SmallPtrSet<Value*, 16>& currTemps);
723 bool buildsets_anticout(BasicBlock* BB,
724 ValueNumberedSet& anticOut,
725 SmallPtrSet<BasicBlock*, 8>& visited);
726 unsigned buildsets_anticin(BasicBlock* BB,
727 ValueNumberedSet& anticOut,
728 ValueNumberedSet& currExps,
729 SmallPtrSet<Value*, 16>& currTemps,
730 SmallPtrSet<BasicBlock*, 8>& visited);
731 void buildsets(Function& F) ;
733 void insertion_pre(Value* e, BasicBlock* BB,
734 DenseMap<BasicBlock*, Value*>& avail,
735 std::map<BasicBlock*,ValueNumberedSet>& new_set);
736 unsigned insertion_mergepoint(SmallVector<Value*, 8>& workList,
737 df_iterator<DomTreeNode*>& D,
738 std::map<BasicBlock*, ValueNumberedSet>& new_set);
739 bool insertion(Function& F) ;
747 // createGVNPREPass - The public interface to this file...
748 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
750 static RegisterPass<GVNPRE> X("gvnpre",
751 "Global Value Numbering/Partial Redundancy Elimination");
754 STATISTIC(NumInsertedVals, "Number of values inserted");
755 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
756 STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
758 /// find_leader - Given a set and a value number, return the first
759 /// element of the set with that value number, or 0 if no such element
761 Value* GVNPRE::find_leader(ValueNumberedSet& vals, uint32_t v) {
765 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
767 if (v == VN.lookup(*I))
770 assert(0 && "No leader found, but present bit is set?");
774 /// val_insert - Insert a value into a set only if there is not a value
775 /// with the same value number already in the set
776 void GVNPRE::val_insert(ValueNumberedSet& s, Value* v) {
777 uint32_t num = VN.lookup(v);
782 /// val_replace - Insert a value into a set, replacing any values already in
783 /// the set that have the same value number
784 void GVNPRE::val_replace(ValueNumberedSet& s, Value* v) {
785 if (s.count(v)) return;
787 uint32_t num = VN.lookup(v);
788 Value* leader = find_leader(s, num);
795 /// phi_translate - Given a value, its parent block, and a predecessor of its
796 /// parent, translate the value into legal for the predecessor block. This
797 /// means translating its operands (and recursively, their operands) through
798 /// any phi nodes in the parent into values available in the predecessor
799 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
804 if (CastInst* U = dyn_cast<CastInst>(V)) {
806 if (isa<Instruction>(U->getOperand(0)))
807 newOp1 = phi_translate(U->getOperand(0), pred, succ);
809 newOp1 = U->getOperand(0);
814 if (newOp1 != U->getOperand(0)) {
815 Instruction* newVal = 0;
816 if (CastInst* C = dyn_cast<CastInst>(U))
817 newVal = CastInst::Create(C->getOpcode(),
818 newOp1, C->getType(),
819 C->getName()+".expr");
821 uint32_t v = VN.lookup_or_add(newVal);
823 Value* leader = find_leader(availableOut[pred], v);
825 createdExpressions.push_back(newVal);
835 } if (isa<BinaryOperator>(V) || isa<CmpInst>(V) ||
836 isa<ExtractElementInst>(V)) {
837 User* U = cast<User>(V);
840 if (isa<Instruction>(U->getOperand(0)))
841 newOp1 = phi_translate(U->getOperand(0), pred, succ);
843 newOp1 = U->getOperand(0);
849 if (isa<Instruction>(U->getOperand(1)))
850 newOp2 = phi_translate(U->getOperand(1), pred, succ);
852 newOp2 = U->getOperand(1);
857 if (newOp1 != U->getOperand(0) || newOp2 != U->getOperand(1)) {
858 Instruction* newVal = 0;
859 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
860 newVal = BinaryOperator::Create(BO->getOpcode(),
862 BO->getName()+".expr");
863 else if (CmpInst* C = dyn_cast<CmpInst>(U))
864 newVal = CmpInst::Create(C->getOpcode(),
867 C->getName()+".expr");
868 else if (ExtractElementInst* E = dyn_cast<ExtractElementInst>(U))
869 newVal = new ExtractElementInst(newOp1, newOp2, E->getName()+".expr");
871 uint32_t v = VN.lookup_or_add(newVal);
873 Value* leader = find_leader(availableOut[pred], v);
875 createdExpressions.push_back(newVal);
884 // Ternary Operations
885 } else if (isa<ShuffleVectorInst>(V) || isa<InsertElementInst>(V) ||
886 isa<SelectInst>(V)) {
887 User* U = cast<User>(V);
890 if (isa<Instruction>(U->getOperand(0)))
891 newOp1 = phi_translate(U->getOperand(0), pred, succ);
893 newOp1 = U->getOperand(0);
899 if (isa<Instruction>(U->getOperand(1)))
900 newOp2 = phi_translate(U->getOperand(1), pred, succ);
902 newOp2 = U->getOperand(1);
908 if (isa<Instruction>(U->getOperand(2)))
909 newOp3 = phi_translate(U->getOperand(2), pred, succ);
911 newOp3 = U->getOperand(2);
916 if (newOp1 != U->getOperand(0) ||
917 newOp2 != U->getOperand(1) ||
918 newOp3 != U->getOperand(2)) {
919 Instruction* newVal = 0;
920 if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
921 newVal = new ShuffleVectorInst(newOp1, newOp2, newOp3,
922 S->getName() + ".expr");
923 else if (InsertElementInst* I = dyn_cast<InsertElementInst>(U))
924 newVal = InsertElementInst::Create(newOp1, newOp2, newOp3,
925 I->getName() + ".expr");
926 else if (SelectInst* I = dyn_cast<SelectInst>(U))
927 newVal = SelectInst::Create(newOp1, newOp2, newOp3,
928 I->getName() + ".expr");
930 uint32_t v = VN.lookup_or_add(newVal);
932 Value* leader = find_leader(availableOut[pred], v);
934 createdExpressions.push_back(newVal);
944 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
946 if (isa<Instruction>(U->getPointerOperand()))
947 newOp1 = phi_translate(U->getPointerOperand(), pred, succ);
949 newOp1 = U->getPointerOperand();
954 bool changed_idx = false;
955 SmallVector<Value*, 4> newIdx;
956 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
958 if (isa<Instruction>(*I)) {
959 Value* newVal = phi_translate(*I, pred, succ);
960 newIdx.push_back(newVal);
964 newIdx.push_back(*I);
967 if (newOp1 != U->getPointerOperand() || changed_idx) {
968 Instruction* newVal =
969 GetElementPtrInst::Create(newOp1,
970 newIdx.begin(), newIdx.end(),
971 U->getName()+".expr");
973 uint32_t v = VN.lookup_or_add(newVal);
975 Value* leader = find_leader(availableOut[pred], v);
977 createdExpressions.push_back(newVal);
987 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
988 if (P->getParent() == succ)
989 return P->getIncomingValueForBlock(pred);
995 /// phi_translate_set - Perform phi translation on every element of a set
996 void GVNPRE::phi_translate_set(ValueNumberedSet& anticIn,
997 BasicBlock* pred, BasicBlock* succ,
998 ValueNumberedSet& out) {
999 for (ValueNumberedSet::iterator I = anticIn.begin(),
1000 E = anticIn.end(); I != E; ++I) {
1001 Value* V = phi_translate(*I, pred, succ);
1002 if (V != 0 && !out.test(VN.lookup_or_add(V))) {
1004 out.set(VN.lookup(V));
1009 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of
1010 /// whose inputs is an invoke instruction. If this is true, we cannot safely
1011 /// PRE the instruction or anything that depends on it.
1012 bool GVNPRE::dependsOnInvoke(Value* V) {
1013 if (PHINode* p = dyn_cast<PHINode>(V)) {
1014 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
1015 if (isa<InvokeInst>(*I))
1023 /// clean - Remove all non-opaque values from the set whose operands are not
1024 /// themselves in the set, as well as all values that depend on invokes (see
1026 void GVNPRE::clean(ValueNumberedSet& set) {
1027 SmallVector<Value*, 8> worklist;
1028 worklist.reserve(set.size());
1029 topo_sort(set, worklist);
1031 for (unsigned i = 0; i < worklist.size(); ++i) {
1032 Value* v = worklist[i];
1035 if (CastInst* U = dyn_cast<CastInst>(v)) {
1036 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1037 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1039 lhsValid = !dependsOnInvoke(U->getOperand(0));
1043 set.reset(VN.lookup(U));
1046 // Handle binary ops
1047 } else if (isa<BinaryOperator>(v) || isa<CmpInst>(v) ||
1048 isa<ExtractElementInst>(v)) {
1049 User* U = cast<User>(v);
1051 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1052 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1054 lhsValid = !dependsOnInvoke(U->getOperand(0));
1056 bool rhsValid = !isa<Instruction>(U->getOperand(1));
1057 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
1059 rhsValid = !dependsOnInvoke(U->getOperand(1));
1061 if (!lhsValid || !rhsValid) {
1063 set.reset(VN.lookup(U));
1066 // Handle ternary ops
1067 } else if (isa<ShuffleVectorInst>(v) || isa<InsertElementInst>(v) ||
1068 isa<SelectInst>(v)) {
1069 User* U = cast<User>(v);
1071 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1072 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1074 lhsValid = !dependsOnInvoke(U->getOperand(0));
1076 bool rhsValid = !isa<Instruction>(U->getOperand(1));
1077 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
1079 rhsValid = !dependsOnInvoke(U->getOperand(1));
1081 bool thirdValid = !isa<Instruction>(U->getOperand(2));
1082 thirdValid |= set.test(VN.lookup(U->getOperand(2)));
1084 thirdValid = !dependsOnInvoke(U->getOperand(2));
1086 if (!lhsValid || !rhsValid || !thirdValid) {
1088 set.reset(VN.lookup(U));
1091 // Handle varargs ops
1092 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(v)) {
1093 bool ptrValid = !isa<Instruction>(U->getPointerOperand());
1094 ptrValid |= set.test(VN.lookup(U->getPointerOperand()));
1096 ptrValid = !dependsOnInvoke(U->getPointerOperand());
1098 bool varValid = true;
1099 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
1102 varValid &= !isa<Instruction>(*I) || set.test(VN.lookup(*I));
1103 varValid &= !dependsOnInvoke(*I);
1106 if (!ptrValid || !varValid) {
1108 set.reset(VN.lookup(U));
1114 /// topo_sort - Given a set of values, sort them by topological
1115 /// order into the provided vector.
1116 void GVNPRE::topo_sort(ValueNumberedSet& set, SmallVector<Value*, 8>& vec) {
1117 SmallPtrSet<Value*, 16> visited;
1118 SmallVector<Value*, 8> stack;
1119 for (ValueNumberedSet::iterator I = set.begin(), E = set.end();
1121 if (visited.count(*I) == 0)
1122 stack.push_back(*I);
1124 while (!stack.empty()) {
1125 Value* e = stack.back();
1128 if (CastInst* U = dyn_cast<CastInst>(e)) {
1129 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1131 if (l != 0 && isa<Instruction>(l) &&
1132 visited.count(l) == 0)
1140 // Handle binary ops
1141 } else if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1142 isa<ExtractElementInst>(e)) {
1143 User* U = cast<User>(e);
1144 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1145 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1147 if (l != 0 && isa<Instruction>(l) &&
1148 visited.count(l) == 0)
1150 else if (r != 0 && isa<Instruction>(r) &&
1151 visited.count(r) == 0)
1159 // Handle ternary ops
1160 } else if (isa<InsertElementInst>(e) || isa<ShuffleVectorInst>(e) ||
1161 isa<SelectInst>(e)) {
1162 User* U = cast<User>(e);
1163 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1164 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1165 Value* m = find_leader(set, VN.lookup(U->getOperand(2)));
1167 if (l != 0 && isa<Instruction>(l) &&
1168 visited.count(l) == 0)
1170 else if (r != 0 && isa<Instruction>(r) &&
1171 visited.count(r) == 0)
1173 else if (m != 0 && isa<Instruction>(m) &&
1174 visited.count(m) == 0)
1182 // Handle vararg ops
1183 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(e)) {
1184 Value* p = find_leader(set, VN.lookup(U->getPointerOperand()));
1186 if (p != 0 && isa<Instruction>(p) &&
1187 visited.count(p) == 0)
1190 bool push_va = false;
1191 for (GetElementPtrInst::op_iterator I = U->idx_begin(),
1192 E = U->idx_end(); I != E; ++I) {
1193 Value * v = find_leader(set, VN.lookup(*I));
1194 if (v != 0 && isa<Instruction>(v) && visited.count(v) == 0) {
1207 // Handle opaque ops
1219 /// dump - Dump a set of values to standard error
1220 void GVNPRE::dump(ValueNumberedSet& s) const {
1222 for (ValueNumberedSet::iterator I = s.begin(), E = s.end();
1224 DOUT << "" << VN.lookup(*I) << ": ";
1225 DEBUG((*I)->dump());
1230 /// elimination - Phase 3 of the main algorithm. Perform full redundancy
1231 /// elimination by walking the dominator tree and removing any instruction that
1232 /// is dominated by another instruction with the same value number.
1233 bool GVNPRE::elimination() {
1234 bool changed_function = false;
1236 SmallVector<std::pair<Instruction*, Value*>, 8> replace;
1237 SmallVector<Instruction*, 8> erase;
1239 DominatorTree& DT = getAnalysis<DominatorTree>();
1241 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1242 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1243 BasicBlock* BB = DI->getBlock();
1245 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1248 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI) ||
1249 isa<ShuffleVectorInst>(BI) || isa<InsertElementInst>(BI) ||
1250 isa<ExtractElementInst>(BI) || isa<SelectInst>(BI) ||
1251 isa<CastInst>(BI) || isa<GetElementPtrInst>(BI)) {
1253 if (availableOut[BB].test(VN.lookup(BI)) &&
1254 !availableOut[BB].count(BI)) {
1255 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
1256 if (Instruction* Instr = dyn_cast<Instruction>(leader))
1257 if (Instr->getParent() != 0 && Instr != BI) {
1258 replace.push_back(std::make_pair(BI, leader));
1259 erase.push_back(BI);
1267 while (!replace.empty()) {
1268 std::pair<Instruction*, Value*> rep = replace.back();
1270 rep.first->replaceAllUsesWith(rep.second);
1271 changed_function = true;
1274 for (SmallVector<Instruction*, 8>::iterator I = erase.begin(),
1275 E = erase.end(); I != E; ++I)
1276 (*I)->eraseFromParent();
1278 return changed_function;
1281 /// cleanup - Delete any extraneous values that were created to represent
1282 /// expressions without leaders.
1283 void GVNPRE::cleanup() {
1284 while (!createdExpressions.empty()) {
1285 Instruction* I = createdExpressions.back();
1286 createdExpressions.pop_back();
1292 /// buildsets_availout - When calculating availability, handle an instruction
1293 /// by inserting it into the appropriate sets
1294 void GVNPRE::buildsets_availout(BasicBlock::iterator I,
1295 ValueNumberedSet& currAvail,
1296 ValueNumberedSet& currPhis,
1297 ValueNumberedSet& currExps,
1298 SmallPtrSet<Value*, 16>& currTemps) {
1300 if (PHINode* p = dyn_cast<PHINode>(I)) {
1301 unsigned num = VN.lookup_or_add(p);
1307 } else if (CastInst* U = dyn_cast<CastInst>(I)) {
1308 Value* leftValue = U->getOperand(0);
1310 unsigned num = VN.lookup_or_add(U);
1312 if (isa<Instruction>(leftValue))
1313 if (!currExps.test(VN.lookup(leftValue))) {
1314 currExps.insert(leftValue);
1315 currExps.set(VN.lookup(leftValue));
1318 if (!currExps.test(num)) {
1323 // Handle binary ops
1324 } else if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
1325 isa<ExtractElementInst>(I)) {
1326 User* U = cast<User>(I);
1327 Value* leftValue = U->getOperand(0);
1328 Value* rightValue = U->getOperand(1);
1330 unsigned num = VN.lookup_or_add(U);
1332 if (isa<Instruction>(leftValue))
1333 if (!currExps.test(VN.lookup(leftValue))) {
1334 currExps.insert(leftValue);
1335 currExps.set(VN.lookup(leftValue));
1338 if (isa<Instruction>(rightValue))
1339 if (!currExps.test(VN.lookup(rightValue))) {
1340 currExps.insert(rightValue);
1341 currExps.set(VN.lookup(rightValue));
1344 if (!currExps.test(num)) {
1349 // Handle ternary ops
1350 } else if (isa<InsertElementInst>(I) || isa<ShuffleVectorInst>(I) ||
1351 isa<SelectInst>(I)) {
1352 User* U = cast<User>(I);
1353 Value* leftValue = U->getOperand(0);
1354 Value* rightValue = U->getOperand(1);
1355 Value* thirdValue = U->getOperand(2);
1357 VN.lookup_or_add(U);
1359 unsigned num = VN.lookup_or_add(U);
1361 if (isa<Instruction>(leftValue))
1362 if (!currExps.test(VN.lookup(leftValue))) {
1363 currExps.insert(leftValue);
1364 currExps.set(VN.lookup(leftValue));
1366 if (isa<Instruction>(rightValue))
1367 if (!currExps.test(VN.lookup(rightValue))) {
1368 currExps.insert(rightValue);
1369 currExps.set(VN.lookup(rightValue));
1371 if (isa<Instruction>(thirdValue))
1372 if (!currExps.test(VN.lookup(thirdValue))) {
1373 currExps.insert(thirdValue);
1374 currExps.set(VN.lookup(thirdValue));
1377 if (!currExps.test(num)) {
1382 // Handle vararg ops
1383 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(I)) {
1384 Value* ptrValue = U->getPointerOperand();
1386 VN.lookup_or_add(U);
1388 unsigned num = VN.lookup_or_add(U);
1390 if (isa<Instruction>(ptrValue))
1391 if (!currExps.test(VN.lookup(ptrValue))) {
1392 currExps.insert(ptrValue);
1393 currExps.set(VN.lookup(ptrValue));
1396 for (GetElementPtrInst::op_iterator OI = U->idx_begin(), OE = U->idx_end();
1398 if (isa<Instruction>(*OI) && !currExps.test(VN.lookup(*OI))) {
1399 currExps.insert(*OI);
1400 currExps.set(VN.lookup(*OI));
1403 if (!currExps.test(VN.lookup(U))) {
1408 // Handle opaque ops
1409 } else if (!I->isTerminator()){
1410 VN.lookup_or_add(I);
1412 currTemps.insert(I);
1415 if (!I->isTerminator())
1416 if (!currAvail.test(VN.lookup(I))) {
1417 currAvail.insert(I);
1418 currAvail.set(VN.lookup(I));
1422 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
1423 /// set as a function of the ANTIC_IN set of the block's predecessors
1424 bool GVNPRE::buildsets_anticout(BasicBlock* BB,
1425 ValueNumberedSet& anticOut,
1426 SmallPtrSet<BasicBlock*, 8>& visited) {
1427 if (BB->getTerminator()->getNumSuccessors() == 1) {
1428 if (BB->getTerminator()->getSuccessor(0) != BB &&
1429 visited.count(BB->getTerminator()->getSuccessor(0)) == 0) {
1433 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
1434 BB, BB->getTerminator()->getSuccessor(0), anticOut);
1436 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
1437 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
1438 for (ValueNumberedSet::iterator I = anticipatedIn[first].begin(),
1439 E = anticipatedIn[first].end(); I != E; ++I) {
1440 anticOut.insert(*I);
1441 anticOut.set(VN.lookup(*I));
1444 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
1445 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
1446 ValueNumberedSet& succAnticIn = anticipatedIn[currSucc];
1448 SmallVector<Value*, 16> temp;
1450 for (ValueNumberedSet::iterator I = anticOut.begin(),
1451 E = anticOut.end(); I != E; ++I)
1452 if (!succAnticIn.test(VN.lookup(*I)))
1455 for (SmallVector<Value*, 16>::iterator I = temp.begin(), E = temp.end();
1458 anticOut.reset(VN.lookup(*I));
1466 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
1467 /// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN
1468 /// sets populated in buildsets_availout
1469 unsigned GVNPRE::buildsets_anticin(BasicBlock* BB,
1470 ValueNumberedSet& anticOut,
1471 ValueNumberedSet& currExps,
1472 SmallPtrSet<Value*, 16>& currTemps,
1473 SmallPtrSet<BasicBlock*, 8>& visited) {
1474 ValueNumberedSet& anticIn = anticipatedIn[BB];
1475 unsigned old = anticIn.size();
1477 bool defer = buildsets_anticout(BB, anticOut, visited);
1483 for (ValueNumberedSet::iterator I = anticOut.begin(),
1484 E = anticOut.end(); I != E; ++I) {
1486 anticIn.set(VN.lookup(*I));
1488 for (ValueNumberedSet::iterator I = currExps.begin(),
1489 E = currExps.end(); I != E; ++I) {
1490 if (!anticIn.test(VN.lookup(*I))) {
1492 anticIn.set(VN.lookup(*I));
1496 for (SmallPtrSet<Value*, 16>::iterator I = currTemps.begin(),
1497 E = currTemps.end(); I != E; ++I) {
1499 anticIn.reset(VN.lookup(*I));
1505 if (old != anticIn.size())
1511 /// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT
1512 /// and the ANTIC_IN sets.
1513 void GVNPRE::buildsets(Function& F) {
1514 DenseMap<BasicBlock*, ValueNumberedSet> generatedExpressions;
1515 DenseMap<BasicBlock*, SmallPtrSet<Value*, 16> > generatedTemporaries;
1517 DominatorTree &DT = getAnalysis<DominatorTree>();
1519 // Phase 1, Part 1: calculate AVAIL_OUT
1521 // Top-down walk of the dominator tree
1522 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1523 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1525 // Get the sets to update for this block
1526 ValueNumberedSet& currExps = generatedExpressions[DI->getBlock()];
1527 ValueNumberedSet& currPhis = generatedPhis[DI->getBlock()];
1528 SmallPtrSet<Value*, 16>& currTemps = generatedTemporaries[DI->getBlock()];
1529 ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
1531 BasicBlock* BB = DI->getBlock();
1533 // A block inherits AVAIL_OUT from its dominator
1534 if (DI->getIDom() != 0)
1535 currAvail = availableOut[DI->getIDom()->getBlock()];
1537 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1539 buildsets_availout(BI, currAvail, currPhis, currExps,
1544 // Phase 1, Part 2: calculate ANTIC_IN
1546 SmallPtrSet<BasicBlock*, 8> visited;
1547 SmallPtrSet<BasicBlock*, 4> block_changed;
1548 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
1549 block_changed.insert(FI);
1551 bool changed = true;
1552 unsigned iterations = 0;
1556 ValueNumberedSet anticOut;
1558 // Postorder walk of the CFG
1559 for (po_iterator<BasicBlock*> BBI = po_begin(&F.getEntryBlock()),
1560 BBE = po_end(&F.getEntryBlock()); BBI != BBE; ++BBI) {
1561 BasicBlock* BB = *BBI;
1563 if (block_changed.count(BB) != 0) {
1564 unsigned ret = buildsets_anticin(BB, anticOut,generatedExpressions[BB],
1565 generatedTemporaries[BB], visited);
1574 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1576 block_changed.insert(*PI);
1579 block_changed.erase(BB);
1581 changed |= (ret == 2);
1590 /// insertion_pre - When a partial redundancy has been identified, eliminate it
1591 /// by inserting appropriate values into the predecessors and a phi node in
1593 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
1594 DenseMap<BasicBlock*, Value*>& avail,
1595 std::map<BasicBlock*, ValueNumberedSet>& new_sets) {
1596 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1597 Value* e2 = avail[*PI];
1598 if (!availableOut[*PI].test(VN.lookup(e2))) {
1599 User* U = cast<User>(e2);
1602 if (isa<BinaryOperator>(U->getOperand(0)) ||
1603 isa<CmpInst>(U->getOperand(0)) ||
1604 isa<ShuffleVectorInst>(U->getOperand(0)) ||
1605 isa<ExtractElementInst>(U->getOperand(0)) ||
1606 isa<InsertElementInst>(U->getOperand(0)) ||
1607 isa<SelectInst>(U->getOperand(0)) ||
1608 isa<CastInst>(U->getOperand(0)) ||
1609 isa<GetElementPtrInst>(U->getOperand(0)))
1610 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1612 s1 = U->getOperand(0);
1616 if (isa<BinaryOperator>(U) ||
1618 isa<ShuffleVectorInst>(U) ||
1619 isa<ExtractElementInst>(U) ||
1620 isa<InsertElementInst>(U) ||
1621 isa<SelectInst>(U)) {
1622 if (isa<BinaryOperator>(U->getOperand(1)) ||
1623 isa<CmpInst>(U->getOperand(1)) ||
1624 isa<ShuffleVectorInst>(U->getOperand(1)) ||
1625 isa<ExtractElementInst>(U->getOperand(1)) ||
1626 isa<InsertElementInst>(U->getOperand(1)) ||
1627 isa<SelectInst>(U->getOperand(1)) ||
1628 isa<CastInst>(U->getOperand(1)) ||
1629 isa<GetElementPtrInst>(U->getOperand(1))) {
1630 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1632 s2 = U->getOperand(1);
1636 // Ternary Operators
1638 if (isa<ShuffleVectorInst>(U) ||
1639 isa<InsertElementInst>(U) ||
1640 isa<SelectInst>(U)) {
1641 if (isa<BinaryOperator>(U->getOperand(2)) ||
1642 isa<CmpInst>(U->getOperand(2)) ||
1643 isa<ShuffleVectorInst>(U->getOperand(2)) ||
1644 isa<ExtractElementInst>(U->getOperand(2)) ||
1645 isa<InsertElementInst>(U->getOperand(2)) ||
1646 isa<SelectInst>(U->getOperand(2)) ||
1647 isa<CastInst>(U->getOperand(2)) ||
1648 isa<GetElementPtrInst>(U->getOperand(2))) {
1649 s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2)));
1651 s3 = U->getOperand(2);
1656 SmallVector<Value*, 4> sVarargs;
1657 if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U)) {
1658 for (GetElementPtrInst::op_iterator OI = G->idx_begin(),
1659 OE = G->idx_end(); OI != OE; ++OI) {
1660 if (isa<BinaryOperator>(*OI) ||
1661 isa<CmpInst>(*OI) ||
1662 isa<ShuffleVectorInst>(*OI) ||
1663 isa<ExtractElementInst>(*OI) ||
1664 isa<InsertElementInst>(*OI) ||
1665 isa<SelectInst>(*OI) ||
1666 isa<CastInst>(*OI) ||
1667 isa<GetElementPtrInst>(*OI)) {
1668 sVarargs.push_back(find_leader(availableOut[*PI],
1671 sVarargs.push_back(*OI);
1677 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1678 newVal = BinaryOperator::Create(BO->getOpcode(), s1, s2,
1679 BO->getName()+".gvnpre",
1680 (*PI)->getTerminator());
1681 else if (CmpInst* C = dyn_cast<CmpInst>(U))
1682 newVal = CmpInst::Create(C->getOpcode(), C->getPredicate(), s1, s2,
1683 C->getName()+".gvnpre",
1684 (*PI)->getTerminator());
1685 else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
1686 newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre",
1687 (*PI)->getTerminator());
1688 else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U))
1689 newVal = InsertElementInst::Create(s1, s2, s3, S->getName()+".gvnpre",
1690 (*PI)->getTerminator());
1691 else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U))
1692 newVal = new ExtractElementInst(s1, s2, S->getName()+".gvnpre",
1693 (*PI)->getTerminator());
1694 else if (SelectInst* S = dyn_cast<SelectInst>(U))
1695 newVal = SelectInst::Create(s1, s2, s3, S->getName()+".gvnpre",
1696 (*PI)->getTerminator());
1697 else if (CastInst* C = dyn_cast<CastInst>(U))
1698 newVal = CastInst::Create(C->getOpcode(), s1, C->getType(),
1699 C->getName()+".gvnpre",
1700 (*PI)->getTerminator());
1701 else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U))
1702 newVal = GetElementPtrInst::Create(s1, sVarargs.begin(), sVarargs.end(),
1703 G->getName()+".gvnpre",
1704 (*PI)->getTerminator());
1706 VN.add(newVal, VN.lookup(U));
1708 ValueNumberedSet& predAvail = availableOut[*PI];
1709 val_replace(predAvail, newVal);
1710 val_replace(new_sets[*PI], newVal);
1711 predAvail.set(VN.lookup(newVal));
1713 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1714 if (av != avail.end())
1716 avail.insert(std::make_pair(*PI, newVal));
1724 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1726 p = PHINode::Create(avail[*PI]->getType(), "gvnpre-join", BB->begin());
1728 p->addIncoming(avail[*PI], *PI);
1731 VN.add(p, VN.lookup(e));
1732 val_replace(availableOut[BB], p);
1733 availableOut[BB].set(VN.lookup(e));
1734 generatedPhis[BB].insert(p);
1735 generatedPhis[BB].set(VN.lookup(e));
1736 new_sets[BB].insert(p);
1737 new_sets[BB].set(VN.lookup(e));
1742 /// insertion_mergepoint - When walking the dom tree, check at each merge
1743 /// block for the possibility of a partial redundancy. If present, eliminate it
1744 unsigned GVNPRE::insertion_mergepoint(SmallVector<Value*, 8>& workList,
1745 df_iterator<DomTreeNode*>& D,
1746 std::map<BasicBlock*, ValueNumberedSet >& new_sets) {
1747 bool changed_function = false;
1748 bool new_stuff = false;
1750 BasicBlock* BB = D->getBlock();
1751 for (unsigned i = 0; i < workList.size(); ++i) {
1752 Value* e = workList[i];
1754 if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1755 isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) ||
1756 isa<ShuffleVectorInst>(e) || isa<SelectInst>(e) || isa<CastInst>(e) ||
1757 isa<GetElementPtrInst>(e)) {
1758 if (availableOut[D->getIDom()->getBlock()].test(VN.lookup(e)))
1761 DenseMap<BasicBlock*, Value*> avail;
1762 bool by_some = false;
1763 bool all_same = true;
1764 Value * first_s = 0;
1766 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1768 Value *e2 = phi_translate(e, *PI, BB);
1769 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1772 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1773 if (av != avail.end())
1775 avail.insert(std::make_pair(*PI, e2));
1778 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1779 if (av != avail.end())
1781 avail.insert(std::make_pair(*PI, e3));
1786 else if (first_s != e3)
1791 if (by_some && !all_same &&
1792 !generatedPhis[BB].test(VN.lookup(e))) {
1793 insertion_pre(e, BB, avail, new_sets);
1795 changed_function = true;
1801 unsigned retval = 0;
1802 if (changed_function)
1810 /// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for
1811 /// merge points. When one is found, check for a partial redundancy. If one is
1812 /// present, eliminate it. Repeat this walk until no changes are made.
1813 bool GVNPRE::insertion(Function& F) {
1814 bool changed_function = false;
1816 DominatorTree &DT = getAnalysis<DominatorTree>();
1818 std::map<BasicBlock*, ValueNumberedSet> new_sets;
1819 bool new_stuff = true;
1822 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1823 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1824 BasicBlock* BB = DI->getBlock();
1829 ValueNumberedSet& availOut = availableOut[BB];
1830 ValueNumberedSet& anticIn = anticipatedIn[BB];
1832 // Replace leaders with leaders inherited from dominator
1833 if (DI->getIDom() != 0) {
1834 ValueNumberedSet& dom_set = new_sets[DI->getIDom()->getBlock()];
1835 for (ValueNumberedSet::iterator I = dom_set.begin(),
1836 E = dom_set.end(); I != E; ++I) {
1837 val_replace(new_sets[BB], *I);
1838 val_replace(availOut, *I);
1842 // If there is more than one predecessor...
1843 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
1844 SmallVector<Value*, 8> workList;
1845 workList.reserve(anticIn.size());
1846 topo_sort(anticIn, workList);
1848 unsigned result = insertion_mergepoint(workList, DI, new_sets);
1850 changed_function = true;
1857 return changed_function;
1860 // GVNPRE::runOnFunction - This is the main transformation entry point for a
1863 bool GVNPRE::runOnFunction(Function &F) {
1864 // Clean out global sets from any previous functions
1866 createdExpressions.clear();
1867 availableOut.clear();
1868 anticipatedIn.clear();
1869 generatedPhis.clear();
1871 bool changed_function = false;
1873 // Phase 1: BuildSets
1874 // This phase calculates the AVAIL_OUT and ANTIC_IN sets
1878 // This phase inserts values to make partially redundant values
1880 changed_function |= insertion(F);
1882 // Phase 3: Eliminate
1883 // This phase performs trivial full redundancy elimination
1884 changed_function |= elimination();
1887 // This phase cleans up values that were created solely
1888 // as leaders for expressions
1891 return changed_function;