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"
42 #include "llvm/Support/ErrorHandling.h"
48 //===----------------------------------------------------------------------===//
50 //===----------------------------------------------------------------------===//
54 /// This class holds the mapping between values and value numbers. It is used
55 /// as an efficient mechanism to determine the expression-wise equivalence of
59 enum ExpressionOpcode { ADD, FADD, SUB, FSUB, MUL, FMUL,
60 UDIV, SDIV, FDIV, UREM, SREM,
61 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
62 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
63 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
64 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
65 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
66 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
67 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
68 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
69 PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY,
72 ExpressionOpcode opcode;
77 SmallVector<uint32_t, 4> varargs;
80 explicit Expression(ExpressionOpcode o) : opcode(o) { }
82 bool operator==(const Expression &other) const {
83 if (opcode != other.opcode)
85 else if (opcode == EMPTY || opcode == TOMBSTONE)
87 else if (type != other.type)
89 else if (firstVN != other.firstVN)
91 else if (secondVN != other.secondVN)
93 else if (thirdVN != other.thirdVN)
96 if (varargs.size() != other.varargs.size())
99 for (size_t i = 0; i < varargs.size(); ++i)
100 if (varargs[i] != other.varargs[i])
107 bool operator!=(const Expression &other) const {
108 if (opcode != other.opcode)
110 else if (opcode == EMPTY || opcode == TOMBSTONE)
112 else if (type != other.type)
114 else if (firstVN != other.firstVN)
116 else if (secondVN != other.secondVN)
118 else if (thirdVN != other.thirdVN)
121 if (varargs.size() != other.varargs.size())
124 for (size_t i = 0; i < varargs.size(); ++i)
125 if (varargs[i] != other.varargs[i])
136 class VISIBILITY_HIDDEN ValueTable {
138 DenseMap<Value*, uint32_t> valueNumbering;
139 DenseMap<Expression, uint32_t> expressionNumbering;
141 uint32_t nextValueNumber;
143 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
144 Expression::ExpressionOpcode getOpcode(CmpInst* C);
145 Expression::ExpressionOpcode getOpcode(CastInst* C);
146 Expression create_expression(BinaryOperator* BO);
147 Expression create_expression(CmpInst* C);
148 Expression create_expression(ShuffleVectorInst* V);
149 Expression create_expression(ExtractElementInst* C);
150 Expression create_expression(InsertElementInst* V);
151 Expression create_expression(SelectInst* V);
152 Expression create_expression(CastInst* C);
153 Expression create_expression(GetElementPtrInst* G);
155 ValueTable() { nextValueNumber = 1; }
156 uint32_t lookup_or_add(Value* V);
157 uint32_t lookup(Value* V) const;
158 void add(Value* V, uint32_t num);
160 void erase(Value* v);
166 template <> struct DenseMapInfo<Expression> {
167 static inline Expression getEmptyKey() {
168 return Expression(Expression::EMPTY);
171 static inline Expression getTombstoneKey() {
172 return Expression(Expression::TOMBSTONE);
175 static unsigned getHashValue(const Expression e) {
176 unsigned hash = e.opcode;
178 hash = e.firstVN + hash * 37;
179 hash = e.secondVN + hash * 37;
180 hash = e.thirdVN + hash * 37;
182 hash = ((unsigned)((uintptr_t)e.type >> 4) ^
183 (unsigned)((uintptr_t)e.type >> 9)) +
186 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
187 E = e.varargs.end(); I != E; ++I)
188 hash = *I + hash * 37;
192 static bool isEqual(const Expression &LHS, const Expression &RHS) {
195 static bool isPod() { return true; }
199 //===----------------------------------------------------------------------===//
200 // ValueTable Internal Functions
201 //===----------------------------------------------------------------------===//
202 Expression::ExpressionOpcode
203 ValueTable::getOpcode(BinaryOperator* BO) {
204 switch(BO->getOpcode()) {
205 case Instruction::Add:
206 return Expression::ADD;
207 case Instruction::FAdd:
208 return Expression::FADD;
209 case Instruction::Sub:
210 return Expression::SUB;
211 case Instruction::FSub:
212 return Expression::FSUB;
213 case Instruction::Mul:
214 return Expression::MUL;
215 case Instruction::FMul:
216 return Expression::FMUL;
217 case Instruction::UDiv:
218 return Expression::UDIV;
219 case Instruction::SDiv:
220 return Expression::SDIV;
221 case Instruction::FDiv:
222 return Expression::FDIV;
223 case Instruction::URem:
224 return Expression::UREM;
225 case Instruction::SRem:
226 return Expression::SREM;
227 case Instruction::FRem:
228 return Expression::FREM;
229 case Instruction::Shl:
230 return Expression::SHL;
231 case Instruction::LShr:
232 return Expression::LSHR;
233 case Instruction::AShr:
234 return Expression::ASHR;
235 case Instruction::And:
236 return Expression::AND;
237 case Instruction::Or:
238 return Expression::OR;
239 case Instruction::Xor:
240 return Expression::XOR;
242 // THIS SHOULD NEVER HAPPEN
244 llvm_unreachable("Binary operator with unknown opcode?");
245 return Expression::ADD;
249 Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
250 if (C->getOpcode() == Instruction::ICmp) {
251 switch (C->getPredicate()) {
252 case ICmpInst::ICMP_EQ:
253 return Expression::ICMPEQ;
254 case ICmpInst::ICMP_NE:
255 return Expression::ICMPNE;
256 case ICmpInst::ICMP_UGT:
257 return Expression::ICMPUGT;
258 case ICmpInst::ICMP_UGE:
259 return Expression::ICMPUGE;
260 case ICmpInst::ICMP_ULT:
261 return Expression::ICMPULT;
262 case ICmpInst::ICMP_ULE:
263 return Expression::ICMPULE;
264 case ICmpInst::ICMP_SGT:
265 return Expression::ICMPSGT;
266 case ICmpInst::ICMP_SGE:
267 return Expression::ICMPSGE;
268 case ICmpInst::ICMP_SLT:
269 return Expression::ICMPSLT;
270 case ICmpInst::ICMP_SLE:
271 return Expression::ICMPSLE;
273 // THIS SHOULD NEVER HAPPEN
275 llvm_unreachable("Comparison with unknown predicate?");
276 return Expression::ICMPEQ;
279 switch (C->getPredicate()) {
280 case FCmpInst::FCMP_OEQ:
281 return Expression::FCMPOEQ;
282 case FCmpInst::FCMP_OGT:
283 return Expression::FCMPOGT;
284 case FCmpInst::FCMP_OGE:
285 return Expression::FCMPOGE;
286 case FCmpInst::FCMP_OLT:
287 return Expression::FCMPOLT;
288 case FCmpInst::FCMP_OLE:
289 return Expression::FCMPOLE;
290 case FCmpInst::FCMP_ONE:
291 return Expression::FCMPONE;
292 case FCmpInst::FCMP_ORD:
293 return Expression::FCMPORD;
294 case FCmpInst::FCMP_UNO:
295 return Expression::FCMPUNO;
296 case FCmpInst::FCMP_UEQ:
297 return Expression::FCMPUEQ;
298 case FCmpInst::FCMP_UGT:
299 return Expression::FCMPUGT;
300 case FCmpInst::FCMP_UGE:
301 return Expression::FCMPUGE;
302 case FCmpInst::FCMP_ULT:
303 return Expression::FCMPULT;
304 case FCmpInst::FCMP_ULE:
305 return Expression::FCMPULE;
306 case FCmpInst::FCMP_UNE:
307 return Expression::FCMPUNE;
309 // THIS SHOULD NEVER HAPPEN
311 llvm_unreachable("Comparison with unknown predicate?");
312 return Expression::FCMPOEQ;
317 Expression::ExpressionOpcode
318 ValueTable::getOpcode(CastInst* C) {
319 switch(C->getOpcode()) {
320 case Instruction::Trunc:
321 return Expression::TRUNC;
322 case Instruction::ZExt:
323 return Expression::ZEXT;
324 case Instruction::SExt:
325 return Expression::SEXT;
326 case Instruction::FPToUI:
327 return Expression::FPTOUI;
328 case Instruction::FPToSI:
329 return Expression::FPTOSI;
330 case Instruction::UIToFP:
331 return Expression::UITOFP;
332 case Instruction::SIToFP:
333 return Expression::SITOFP;
334 case Instruction::FPTrunc:
335 return Expression::FPTRUNC;
336 case Instruction::FPExt:
337 return Expression::FPEXT;
338 case Instruction::PtrToInt:
339 return Expression::PTRTOINT;
340 case Instruction::IntToPtr:
341 return Expression::INTTOPTR;
342 case Instruction::BitCast:
343 return Expression::BITCAST;
345 // THIS SHOULD NEVER HAPPEN
347 llvm_unreachable("Cast operator with unknown opcode?");
348 return Expression::BITCAST;
352 Expression ValueTable::create_expression(BinaryOperator* BO) {
355 e.firstVN = lookup_or_add(BO->getOperand(0));
356 e.secondVN = lookup_or_add(BO->getOperand(1));
358 e.type = BO->getType();
359 e.opcode = getOpcode(BO);
364 Expression ValueTable::create_expression(CmpInst* C) {
367 e.firstVN = lookup_or_add(C->getOperand(0));
368 e.secondVN = lookup_or_add(C->getOperand(1));
370 e.type = C->getType();
371 e.opcode = getOpcode(C);
376 Expression ValueTable::create_expression(CastInst* C) {
379 e.firstVN = lookup_or_add(C->getOperand(0));
382 e.type = C->getType();
383 e.opcode = getOpcode(C);
388 Expression ValueTable::create_expression(ShuffleVectorInst* S) {
391 e.firstVN = lookup_or_add(S->getOperand(0));
392 e.secondVN = lookup_or_add(S->getOperand(1));
393 e.thirdVN = lookup_or_add(S->getOperand(2));
394 e.type = S->getType();
395 e.opcode = Expression::SHUFFLE;
400 Expression ValueTable::create_expression(ExtractElementInst* E) {
403 e.firstVN = lookup_or_add(E->getOperand(0));
404 e.secondVN = lookup_or_add(E->getOperand(1));
406 e.type = E->getType();
407 e.opcode = Expression::EXTRACT;
412 Expression ValueTable::create_expression(InsertElementInst* I) {
415 e.firstVN = lookup_or_add(I->getOperand(0));
416 e.secondVN = lookup_or_add(I->getOperand(1));
417 e.thirdVN = lookup_or_add(I->getOperand(2));
418 e.type = I->getType();
419 e.opcode = Expression::INSERT;
424 Expression ValueTable::create_expression(SelectInst* I) {
427 e.firstVN = lookup_or_add(I->getCondition());
428 e.secondVN = lookup_or_add(I->getTrueValue());
429 e.thirdVN = lookup_or_add(I->getFalseValue());
430 e.type = I->getType();
431 e.opcode = Expression::SELECT;
436 Expression ValueTable::create_expression(GetElementPtrInst* G) {
439 e.firstVN = lookup_or_add(G->getPointerOperand());
442 e.type = G->getType();
443 e.opcode = Expression::GEP;
445 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
447 e.varargs.push_back(lookup_or_add(*I));
452 //===----------------------------------------------------------------------===//
453 // ValueTable External Functions
454 //===----------------------------------------------------------------------===//
456 /// lookup_or_add - Returns the value number for the specified value, assigning
457 /// it a new number if it did not have one before.
458 uint32_t ValueTable::lookup_or_add(Value* V) {
459 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
460 if (VI != valueNumbering.end())
464 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
465 Expression e = create_expression(BO);
467 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
468 if (EI != expressionNumbering.end()) {
469 valueNumbering.insert(std::make_pair(V, EI->second));
472 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
473 valueNumbering.insert(std::make_pair(V, nextValueNumber));
475 return nextValueNumber++;
477 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
478 Expression e = create_expression(C);
480 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
481 if (EI != expressionNumbering.end()) {
482 valueNumbering.insert(std::make_pair(V, EI->second));
485 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
486 valueNumbering.insert(std::make_pair(V, nextValueNumber));
488 return nextValueNumber++;
490 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
491 Expression e = create_expression(U);
493 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
494 if (EI != expressionNumbering.end()) {
495 valueNumbering.insert(std::make_pair(V, EI->second));
498 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
499 valueNumbering.insert(std::make_pair(V, nextValueNumber));
501 return nextValueNumber++;
503 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
504 Expression e = create_expression(U);
506 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
507 if (EI != expressionNumbering.end()) {
508 valueNumbering.insert(std::make_pair(V, EI->second));
511 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
512 valueNumbering.insert(std::make_pair(V, nextValueNumber));
514 return nextValueNumber++;
516 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
517 Expression e = create_expression(U);
519 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
520 if (EI != expressionNumbering.end()) {
521 valueNumbering.insert(std::make_pair(V, EI->second));
524 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
525 valueNumbering.insert(std::make_pair(V, nextValueNumber));
527 return nextValueNumber++;
529 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
530 Expression e = create_expression(U);
532 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
533 if (EI != expressionNumbering.end()) {
534 valueNumbering.insert(std::make_pair(V, EI->second));
537 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
538 valueNumbering.insert(std::make_pair(V, nextValueNumber));
540 return nextValueNumber++;
542 } else if (CastInst* U = dyn_cast<CastInst>(V)) {
543 Expression e = create_expression(U);
545 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
546 if (EI != expressionNumbering.end()) {
547 valueNumbering.insert(std::make_pair(V, EI->second));
550 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
551 valueNumbering.insert(std::make_pair(V, nextValueNumber));
553 return nextValueNumber++;
555 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
556 Expression e = create_expression(U);
558 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
559 if (EI != expressionNumbering.end()) {
560 valueNumbering.insert(std::make_pair(V, EI->second));
563 expressionNumbering.insert(std::make_pair(e, nextValueNumber));
564 valueNumbering.insert(std::make_pair(V, nextValueNumber));
566 return nextValueNumber++;
569 valueNumbering.insert(std::make_pair(V, nextValueNumber));
570 return nextValueNumber++;
574 /// lookup - Returns the value number of the specified value. Fails if
575 /// the value has not yet been numbered.
576 uint32_t ValueTable::lookup(Value* V) const {
577 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
578 if (VI != valueNumbering.end())
581 llvm_unreachable("Value not numbered?");
586 /// add - Add the specified value with the given value number, removing
587 /// its old number, if any
588 void ValueTable::add(Value* V, uint32_t num) {
589 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
590 if (VI != valueNumbering.end())
591 valueNumbering.erase(VI);
592 valueNumbering.insert(std::make_pair(V, num));
595 /// clear - Remove all entries from the ValueTable
596 void ValueTable::clear() {
597 valueNumbering.clear();
598 expressionNumbering.clear();
602 /// erase - Remove a value from the value numbering
603 void ValueTable::erase(Value* V) {
604 valueNumbering.erase(V);
607 /// size - Return the number of assigned value numbers
608 unsigned ValueTable::size() {
609 // NOTE: zero is never assigned
610 return nextValueNumber;
615 //===----------------------------------------------------------------------===//
616 // ValueNumberedSet Class
617 //===----------------------------------------------------------------------===//
619 class ValueNumberedSet {
621 SmallPtrSet<Value*, 8> contents;
624 ValueNumberedSet() { numbers.resize(1); }
625 ValueNumberedSet(const ValueNumberedSet& other) {
626 numbers = other.numbers;
627 contents = other.contents;
630 typedef SmallPtrSet<Value*, 8>::iterator iterator;
632 iterator begin() { return contents.begin(); }
633 iterator end() { return contents.end(); }
635 bool insert(Value* v) { return contents.insert(v); }
636 void insert(iterator I, iterator E) { contents.insert(I, E); }
637 void erase(Value* v) { contents.erase(v); }
638 unsigned count(Value* v) { return contents.count(v); }
639 size_t size() { return contents.size(); }
641 void set(unsigned i) {
642 if (i >= numbers.size())
648 void operator=(const ValueNumberedSet& other) {
649 contents = other.contents;
650 numbers = other.numbers;
653 void reset(unsigned i) {
654 if (i < numbers.size())
658 bool test(unsigned i) {
659 if (i >= numbers.size())
662 return numbers.test(i);
673 //===----------------------------------------------------------------------===//
675 //===----------------------------------------------------------------------===//
679 class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
680 bool runOnFunction(Function &F);
682 static char ID; // Pass identification, replacement for typeid
683 GVNPRE() : FunctionPass(&ID) {}
687 SmallVector<Instruction*, 8> createdExpressions;
689 DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
690 DenseMap<BasicBlock*, ValueNumberedSet> anticipatedIn;
691 DenseMap<BasicBlock*, ValueNumberedSet> generatedPhis;
693 // This transformation requires dominator postdominator info
694 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
695 AU.setPreservesCFG();
696 AU.addRequiredID(BreakCriticalEdgesID);
697 AU.addRequired<UnifyFunctionExitNodes>();
698 AU.addRequired<DominatorTree>();
702 // FIXME: eliminate or document these better
703 void dump(ValueNumberedSet& s) const ;
704 void clean(ValueNumberedSet& set) ;
705 Value* find_leader(ValueNumberedSet& vals, uint32_t v) ;
706 Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) ;
707 void phi_translate_set(ValueNumberedSet& anticIn, BasicBlock* pred,
708 BasicBlock* succ, ValueNumberedSet& out) ;
710 void topo_sort(ValueNumberedSet& set,
711 SmallVector<Value*, 8>& vec) ;
716 void val_insert(ValueNumberedSet& s, Value* v) ;
717 void val_replace(ValueNumberedSet& s, Value* v) ;
718 bool dependsOnInvoke(Value* V) ;
719 void buildsets_availout(BasicBlock::iterator I,
720 ValueNumberedSet& currAvail,
721 ValueNumberedSet& currPhis,
722 ValueNumberedSet& currExps,
723 SmallPtrSet<Value*, 16>& currTemps);
724 bool buildsets_anticout(BasicBlock* BB,
725 ValueNumberedSet& anticOut,
726 SmallPtrSet<BasicBlock*, 8>& visited);
727 unsigned buildsets_anticin(BasicBlock* BB,
728 ValueNumberedSet& anticOut,
729 ValueNumberedSet& currExps,
730 SmallPtrSet<Value*, 16>& currTemps,
731 SmallPtrSet<BasicBlock*, 8>& visited);
732 void buildsets(Function& F) ;
734 void insertion_pre(Value* e, BasicBlock* BB,
735 DenseMap<BasicBlock*, Value*>& avail,
736 std::map<BasicBlock*,ValueNumberedSet>& new_set);
737 unsigned insertion_mergepoint(SmallVector<Value*, 8>& workList,
738 df_iterator<DomTreeNode*>& D,
739 std::map<BasicBlock*, ValueNumberedSet>& new_set);
740 bool insertion(Function& F) ;
748 // createGVNPREPass - The public interface to this file...
749 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
751 static RegisterPass<GVNPRE> X("gvnpre",
752 "Global Value Numbering/Partial Redundancy Elimination");
755 STATISTIC(NumInsertedVals, "Number of values inserted");
756 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
757 STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
759 /// find_leader - Given a set and a value number, return the first
760 /// element of the set with that value number, or 0 if no such element
762 Value* GVNPRE::find_leader(ValueNumberedSet& vals, uint32_t v) {
766 for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
768 if (v == VN.lookup(*I))
771 llvm_unreachable("No leader found, but present bit is set?");
775 /// val_insert - Insert a value into a set only if there is not a value
776 /// with the same value number already in the set
777 void GVNPRE::val_insert(ValueNumberedSet& s, Value* v) {
778 uint32_t num = VN.lookup(v);
783 /// val_replace - Insert a value into a set, replacing any values already in
784 /// the set that have the same value number
785 void GVNPRE::val_replace(ValueNumberedSet& s, Value* v) {
786 if (s.count(v)) return;
788 uint32_t num = VN.lookup(v);
789 Value* leader = find_leader(s, num);
796 /// phi_translate - Given a value, its parent block, and a predecessor of its
797 /// parent, translate the value into legal for the predecessor block. This
798 /// means translating its operands (and recursively, their operands) through
799 /// any phi nodes in the parent into values available in the predecessor
800 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
805 if (CastInst* U = dyn_cast<CastInst>(V)) {
807 if (isa<Instruction>(U->getOperand(0)))
808 newOp1 = phi_translate(U->getOperand(0), pred, succ);
810 newOp1 = U->getOperand(0);
815 if (newOp1 != U->getOperand(0)) {
816 Instruction* newVal = 0;
817 if (CastInst* C = dyn_cast<CastInst>(U))
818 newVal = CastInst::Create(C->getOpcode(),
819 newOp1, C->getType(),
820 C->getName()+".expr");
822 uint32_t v = VN.lookup_or_add(newVal);
824 Value* leader = find_leader(availableOut[pred], v);
826 createdExpressions.push_back(newVal);
836 } if (isa<BinaryOperator>(V) || isa<CmpInst>(V) ||
837 isa<ExtractElementInst>(V)) {
838 User* U = cast<User>(V);
841 if (isa<Instruction>(U->getOperand(0)))
842 newOp1 = phi_translate(U->getOperand(0), pred, succ);
844 newOp1 = U->getOperand(0);
850 if (isa<Instruction>(U->getOperand(1)))
851 newOp2 = phi_translate(U->getOperand(1), pred, succ);
853 newOp2 = U->getOperand(1);
858 if (newOp1 != U->getOperand(0) || newOp2 != U->getOperand(1)) {
859 Instruction* newVal = 0;
860 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
861 newVal = BinaryOperator::Create(BO->getOpcode(),
863 BO->getName()+".expr");
864 else if (CmpInst* C = dyn_cast<CmpInst>(U))
865 newVal = CmpInst::Create(C->getOpcode(),
868 C->getName()+".expr");
869 else if (ExtractElementInst* E = dyn_cast<ExtractElementInst>(U))
870 newVal = ExtractElementInst::Create(newOp1, newOp2,
871 E->getName()+".expr");
873 uint32_t v = VN.lookup_or_add(newVal);
875 Value* leader = find_leader(availableOut[pred], v);
877 createdExpressions.push_back(newVal);
886 // Ternary Operations
887 } else if (isa<ShuffleVectorInst>(V) || isa<InsertElementInst>(V) ||
888 isa<SelectInst>(V)) {
889 User* U = cast<User>(V);
892 if (isa<Instruction>(U->getOperand(0)))
893 newOp1 = phi_translate(U->getOperand(0), pred, succ);
895 newOp1 = U->getOperand(0);
901 if (isa<Instruction>(U->getOperand(1)))
902 newOp2 = phi_translate(U->getOperand(1), pred, succ);
904 newOp2 = U->getOperand(1);
910 if (isa<Instruction>(U->getOperand(2)))
911 newOp3 = phi_translate(U->getOperand(2), pred, succ);
913 newOp3 = U->getOperand(2);
918 if (newOp1 != U->getOperand(0) ||
919 newOp2 != U->getOperand(1) ||
920 newOp3 != U->getOperand(2)) {
921 Instruction* newVal = 0;
922 if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
923 newVal = new ShuffleVectorInst(newOp1, newOp2, newOp3,
924 S->getName() + ".expr");
925 else if (InsertElementInst* I = dyn_cast<InsertElementInst>(U))
926 newVal = InsertElementInst::Create(newOp1, newOp2, newOp3,
927 I->getName() + ".expr");
928 else if (SelectInst* I = dyn_cast<SelectInst>(U))
929 newVal = SelectInst::Create(newOp1, newOp2, newOp3,
930 I->getName() + ".expr");
932 uint32_t v = VN.lookup_or_add(newVal);
934 Value* leader = find_leader(availableOut[pred], v);
936 createdExpressions.push_back(newVal);
946 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
948 if (isa<Instruction>(U->getPointerOperand()))
949 newOp1 = phi_translate(U->getPointerOperand(), pred, succ);
951 newOp1 = U->getPointerOperand();
956 bool changed_idx = false;
957 SmallVector<Value*, 4> newIdx;
958 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
960 if (isa<Instruction>(*I)) {
961 Value* newVal = phi_translate(*I, pred, succ);
962 newIdx.push_back(newVal);
966 newIdx.push_back(*I);
969 if (newOp1 != U->getPointerOperand() || changed_idx) {
970 Instruction* newVal =
971 GetElementPtrInst::Create(newOp1,
972 newIdx.begin(), newIdx.end(),
973 U->getName()+".expr");
975 uint32_t v = VN.lookup_or_add(newVal);
977 Value* leader = find_leader(availableOut[pred], v);
979 createdExpressions.push_back(newVal);
989 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
990 if (P->getParent() == succ)
991 return P->getIncomingValueForBlock(pred);
997 /// phi_translate_set - Perform phi translation on every element of a set
998 void GVNPRE::phi_translate_set(ValueNumberedSet& anticIn,
999 BasicBlock* pred, BasicBlock* succ,
1000 ValueNumberedSet& out) {
1001 for (ValueNumberedSet::iterator I = anticIn.begin(),
1002 E = anticIn.end(); I != E; ++I) {
1003 Value* V = phi_translate(*I, pred, succ);
1004 if (V != 0 && !out.test(VN.lookup_or_add(V))) {
1006 out.set(VN.lookup(V));
1011 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of
1012 /// whose inputs is an invoke instruction. If this is true, we cannot safely
1013 /// PRE the instruction or anything that depends on it.
1014 bool GVNPRE::dependsOnInvoke(Value* V) {
1015 if (PHINode* p = dyn_cast<PHINode>(V)) {
1016 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
1017 if (isa<InvokeInst>(*I))
1025 /// clean - Remove all non-opaque values from the set whose operands are not
1026 /// themselves in the set, as well as all values that depend on invokes (see
1028 void GVNPRE::clean(ValueNumberedSet& set) {
1029 SmallVector<Value*, 8> worklist;
1030 worklist.reserve(set.size());
1031 topo_sort(set, worklist);
1033 for (unsigned i = 0; i < worklist.size(); ++i) {
1034 Value* v = worklist[i];
1037 if (CastInst* U = dyn_cast<CastInst>(v)) {
1038 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1039 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1041 lhsValid = !dependsOnInvoke(U->getOperand(0));
1045 set.reset(VN.lookup(U));
1048 // Handle binary ops
1049 } else if (isa<BinaryOperator>(v) || isa<CmpInst>(v) ||
1050 isa<ExtractElementInst>(v)) {
1051 User* U = cast<User>(v);
1053 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1054 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1056 lhsValid = !dependsOnInvoke(U->getOperand(0));
1058 bool rhsValid = !isa<Instruction>(U->getOperand(1));
1059 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
1061 rhsValid = !dependsOnInvoke(U->getOperand(1));
1063 if (!lhsValid || !rhsValid) {
1065 set.reset(VN.lookup(U));
1068 // Handle ternary ops
1069 } else if (isa<ShuffleVectorInst>(v) || isa<InsertElementInst>(v) ||
1070 isa<SelectInst>(v)) {
1071 User* U = cast<User>(v);
1073 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1074 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1076 lhsValid = !dependsOnInvoke(U->getOperand(0));
1078 bool rhsValid = !isa<Instruction>(U->getOperand(1));
1079 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
1081 rhsValid = !dependsOnInvoke(U->getOperand(1));
1083 bool thirdValid = !isa<Instruction>(U->getOperand(2));
1084 thirdValid |= set.test(VN.lookup(U->getOperand(2)));
1086 thirdValid = !dependsOnInvoke(U->getOperand(2));
1088 if (!lhsValid || !rhsValid || !thirdValid) {
1090 set.reset(VN.lookup(U));
1093 // Handle varargs ops
1094 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(v)) {
1095 bool ptrValid = !isa<Instruction>(U->getPointerOperand());
1096 ptrValid |= set.test(VN.lookup(U->getPointerOperand()));
1098 ptrValid = !dependsOnInvoke(U->getPointerOperand());
1100 bool varValid = true;
1101 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
1104 varValid &= !isa<Instruction>(*I) || set.test(VN.lookup(*I));
1105 varValid &= !dependsOnInvoke(*I);
1108 if (!ptrValid || !varValid) {
1110 set.reset(VN.lookup(U));
1116 /// topo_sort - Given a set of values, sort them by topological
1117 /// order into the provided vector.
1118 void GVNPRE::topo_sort(ValueNumberedSet& set, SmallVector<Value*, 8>& vec) {
1119 SmallPtrSet<Value*, 16> visited;
1120 SmallVector<Value*, 8> stack;
1121 for (ValueNumberedSet::iterator I = set.begin(), E = set.end();
1123 if (visited.count(*I) == 0)
1124 stack.push_back(*I);
1126 while (!stack.empty()) {
1127 Value* e = stack.back();
1130 if (CastInst* U = dyn_cast<CastInst>(e)) {
1131 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1133 if (l != 0 && isa<Instruction>(l) &&
1134 visited.count(l) == 0)
1142 // Handle binary ops
1143 } else if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1144 isa<ExtractElementInst>(e)) {
1145 User* U = cast<User>(e);
1146 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1147 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1149 if (l != 0 && isa<Instruction>(l) &&
1150 visited.count(l) == 0)
1152 else if (r != 0 && isa<Instruction>(r) &&
1153 visited.count(r) == 0)
1161 // Handle ternary ops
1162 } else if (isa<InsertElementInst>(e) || isa<ShuffleVectorInst>(e) ||
1163 isa<SelectInst>(e)) {
1164 User* U = cast<User>(e);
1165 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1166 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1167 Value* m = find_leader(set, VN.lookup(U->getOperand(2)));
1169 if (l != 0 && isa<Instruction>(l) &&
1170 visited.count(l) == 0)
1172 else if (r != 0 && isa<Instruction>(r) &&
1173 visited.count(r) == 0)
1175 else if (m != 0 && isa<Instruction>(m) &&
1176 visited.count(m) == 0)
1184 // Handle vararg ops
1185 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(e)) {
1186 Value* p = find_leader(set, VN.lookup(U->getPointerOperand()));
1188 if (p != 0 && isa<Instruction>(p) &&
1189 visited.count(p) == 0)
1192 bool push_va = false;
1193 for (GetElementPtrInst::op_iterator I = U->idx_begin(),
1194 E = U->idx_end(); I != E; ++I) {
1195 Value * v = find_leader(set, VN.lookup(*I));
1196 if (v != 0 && isa<Instruction>(v) && visited.count(v) == 0) {
1209 // Handle opaque ops
1221 /// dump - Dump a set of values to standard error
1222 void GVNPRE::dump(ValueNumberedSet& s) const {
1223 DEBUG(errs() << "{ ");
1224 for (ValueNumberedSet::iterator I = s.begin(), E = s.end();
1226 DEBUG(errs() << "" << VN.lookup(*I) << ": ");
1227 DEBUG((*I)->dump());
1229 DEBUG(errs() << "}\n\n");
1232 /// elimination - Phase 3 of the main algorithm. Perform full redundancy
1233 /// elimination by walking the dominator tree and removing any instruction that
1234 /// is dominated by another instruction with the same value number.
1235 bool GVNPRE::elimination() {
1236 bool changed_function = false;
1238 SmallVector<std::pair<Instruction*, Value*>, 8> replace;
1239 SmallVector<Instruction*, 8> erase;
1241 DominatorTree& DT = getAnalysis<DominatorTree>();
1243 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1244 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1245 BasicBlock* BB = DI->getBlock();
1247 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1250 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI) ||
1251 isa<ShuffleVectorInst>(BI) || isa<InsertElementInst>(BI) ||
1252 isa<ExtractElementInst>(BI) || isa<SelectInst>(BI) ||
1253 isa<CastInst>(BI) || isa<GetElementPtrInst>(BI)) {
1255 if (availableOut[BB].test(VN.lookup(BI)) &&
1256 !availableOut[BB].count(BI)) {
1257 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
1258 if (Instruction* Instr = dyn_cast<Instruction>(leader))
1259 if (Instr->getParent() != 0 && Instr != BI) {
1260 replace.push_back(std::make_pair(BI, leader));
1261 erase.push_back(BI);
1269 while (!replace.empty()) {
1270 std::pair<Instruction*, Value*> rep = replace.back();
1272 rep.first->replaceAllUsesWith(rep.second);
1273 changed_function = true;
1276 for (SmallVector<Instruction*, 8>::iterator I = erase.begin(),
1277 E = erase.end(); I != E; ++I)
1278 (*I)->eraseFromParent();
1280 return changed_function;
1283 /// cleanup - Delete any extraneous values that were created to represent
1284 /// expressions without leaders.
1285 void GVNPRE::cleanup() {
1286 while (!createdExpressions.empty()) {
1287 Instruction* I = createdExpressions.back();
1288 createdExpressions.pop_back();
1294 /// buildsets_availout - When calculating availability, handle an instruction
1295 /// by inserting it into the appropriate sets
1296 void GVNPRE::buildsets_availout(BasicBlock::iterator I,
1297 ValueNumberedSet& currAvail,
1298 ValueNumberedSet& currPhis,
1299 ValueNumberedSet& currExps,
1300 SmallPtrSet<Value*, 16>& currTemps) {
1302 if (PHINode* p = dyn_cast<PHINode>(I)) {
1303 unsigned num = VN.lookup_or_add(p);
1309 } else if (CastInst* U = dyn_cast<CastInst>(I)) {
1310 Value* leftValue = U->getOperand(0);
1312 unsigned num = VN.lookup_or_add(U);
1314 if (isa<Instruction>(leftValue))
1315 if (!currExps.test(VN.lookup(leftValue))) {
1316 currExps.insert(leftValue);
1317 currExps.set(VN.lookup(leftValue));
1320 if (!currExps.test(num)) {
1325 // Handle binary ops
1326 } else if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
1327 isa<ExtractElementInst>(I)) {
1328 User* U = cast<User>(I);
1329 Value* leftValue = U->getOperand(0);
1330 Value* rightValue = U->getOperand(1);
1332 unsigned num = VN.lookup_or_add(U);
1334 if (isa<Instruction>(leftValue))
1335 if (!currExps.test(VN.lookup(leftValue))) {
1336 currExps.insert(leftValue);
1337 currExps.set(VN.lookup(leftValue));
1340 if (isa<Instruction>(rightValue))
1341 if (!currExps.test(VN.lookup(rightValue))) {
1342 currExps.insert(rightValue);
1343 currExps.set(VN.lookup(rightValue));
1346 if (!currExps.test(num)) {
1351 // Handle ternary ops
1352 } else if (isa<InsertElementInst>(I) || isa<ShuffleVectorInst>(I) ||
1353 isa<SelectInst>(I)) {
1354 User* U = cast<User>(I);
1355 Value* leftValue = U->getOperand(0);
1356 Value* rightValue = U->getOperand(1);
1357 Value* thirdValue = U->getOperand(2);
1359 VN.lookup_or_add(U);
1361 unsigned num = VN.lookup_or_add(U);
1363 if (isa<Instruction>(leftValue))
1364 if (!currExps.test(VN.lookup(leftValue))) {
1365 currExps.insert(leftValue);
1366 currExps.set(VN.lookup(leftValue));
1368 if (isa<Instruction>(rightValue))
1369 if (!currExps.test(VN.lookup(rightValue))) {
1370 currExps.insert(rightValue);
1371 currExps.set(VN.lookup(rightValue));
1373 if (isa<Instruction>(thirdValue))
1374 if (!currExps.test(VN.lookup(thirdValue))) {
1375 currExps.insert(thirdValue);
1376 currExps.set(VN.lookup(thirdValue));
1379 if (!currExps.test(num)) {
1384 // Handle vararg ops
1385 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(I)) {
1386 Value* ptrValue = U->getPointerOperand();
1388 VN.lookup_or_add(U);
1390 unsigned num = VN.lookup_or_add(U);
1392 if (isa<Instruction>(ptrValue))
1393 if (!currExps.test(VN.lookup(ptrValue))) {
1394 currExps.insert(ptrValue);
1395 currExps.set(VN.lookup(ptrValue));
1398 for (GetElementPtrInst::op_iterator OI = U->idx_begin(), OE = U->idx_end();
1400 if (isa<Instruction>(*OI) && !currExps.test(VN.lookup(*OI))) {
1401 currExps.insert(*OI);
1402 currExps.set(VN.lookup(*OI));
1405 if (!currExps.test(VN.lookup(U))) {
1410 // Handle opaque ops
1411 } else if (!I->isTerminator()){
1412 VN.lookup_or_add(I);
1414 currTemps.insert(I);
1417 if (!I->isTerminator())
1418 if (!currAvail.test(VN.lookup(I))) {
1419 currAvail.insert(I);
1420 currAvail.set(VN.lookup(I));
1424 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
1425 /// set as a function of the ANTIC_IN set of the block's predecessors
1426 bool GVNPRE::buildsets_anticout(BasicBlock* BB,
1427 ValueNumberedSet& anticOut,
1428 SmallPtrSet<BasicBlock*, 8>& visited) {
1429 if (BB->getTerminator()->getNumSuccessors() == 1) {
1430 if (BB->getTerminator()->getSuccessor(0) != BB &&
1431 visited.count(BB->getTerminator()->getSuccessor(0)) == 0) {
1435 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
1436 BB, BB->getTerminator()->getSuccessor(0), anticOut);
1438 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
1439 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
1440 for (ValueNumberedSet::iterator I = anticipatedIn[first].begin(),
1441 E = anticipatedIn[first].end(); I != E; ++I) {
1442 anticOut.insert(*I);
1443 anticOut.set(VN.lookup(*I));
1446 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
1447 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
1448 ValueNumberedSet& succAnticIn = anticipatedIn[currSucc];
1450 SmallVector<Value*, 16> temp;
1452 for (ValueNumberedSet::iterator I = anticOut.begin(),
1453 E = anticOut.end(); I != E; ++I)
1454 if (!succAnticIn.test(VN.lookup(*I)))
1457 for (SmallVector<Value*, 16>::iterator I = temp.begin(), E = temp.end();
1460 anticOut.reset(VN.lookup(*I));
1468 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
1469 /// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN
1470 /// sets populated in buildsets_availout
1471 unsigned GVNPRE::buildsets_anticin(BasicBlock* BB,
1472 ValueNumberedSet& anticOut,
1473 ValueNumberedSet& currExps,
1474 SmallPtrSet<Value*, 16>& currTemps,
1475 SmallPtrSet<BasicBlock*, 8>& visited) {
1476 ValueNumberedSet& anticIn = anticipatedIn[BB];
1477 unsigned old = anticIn.size();
1479 bool defer = buildsets_anticout(BB, anticOut, visited);
1485 for (ValueNumberedSet::iterator I = anticOut.begin(),
1486 E = anticOut.end(); I != E; ++I) {
1488 anticIn.set(VN.lookup(*I));
1490 for (ValueNumberedSet::iterator I = currExps.begin(),
1491 E = currExps.end(); I != E; ++I) {
1492 if (!anticIn.test(VN.lookup(*I))) {
1494 anticIn.set(VN.lookup(*I));
1498 for (SmallPtrSet<Value*, 16>::iterator I = currTemps.begin(),
1499 E = currTemps.end(); I != E; ++I) {
1501 anticIn.reset(VN.lookup(*I));
1507 if (old != anticIn.size())
1513 /// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT
1514 /// and the ANTIC_IN sets.
1515 void GVNPRE::buildsets(Function& F) {
1516 DenseMap<BasicBlock*, ValueNumberedSet> generatedExpressions;
1517 DenseMap<BasicBlock*, SmallPtrSet<Value*, 16> > generatedTemporaries;
1519 DominatorTree &DT = getAnalysis<DominatorTree>();
1521 // Phase 1, Part 1: calculate AVAIL_OUT
1523 // Top-down walk of the dominator tree
1524 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1525 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1527 // Get the sets to update for this block
1528 ValueNumberedSet& currExps = generatedExpressions[DI->getBlock()];
1529 ValueNumberedSet& currPhis = generatedPhis[DI->getBlock()];
1530 SmallPtrSet<Value*, 16>& currTemps = generatedTemporaries[DI->getBlock()];
1531 ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
1533 BasicBlock* BB = DI->getBlock();
1535 // A block inherits AVAIL_OUT from its dominator
1536 if (DI->getIDom() != 0)
1537 currAvail = availableOut[DI->getIDom()->getBlock()];
1539 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1541 buildsets_availout(BI, currAvail, currPhis, currExps,
1546 // Phase 1, Part 2: calculate ANTIC_IN
1548 SmallPtrSet<BasicBlock*, 8> visited;
1549 SmallPtrSet<BasicBlock*, 4> block_changed;
1550 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
1551 block_changed.insert(FI);
1553 bool changed = true;
1554 unsigned iterations = 0;
1558 ValueNumberedSet anticOut;
1560 // Postorder walk of the CFG
1561 for (po_iterator<BasicBlock*> BBI = po_begin(&F.getEntryBlock()),
1562 BBE = po_end(&F.getEntryBlock()); BBI != BBE; ++BBI) {
1563 BasicBlock* BB = *BBI;
1565 if (block_changed.count(BB) != 0) {
1566 unsigned ret = buildsets_anticin(BB, anticOut,generatedExpressions[BB],
1567 generatedTemporaries[BB], visited);
1576 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1578 block_changed.insert(*PI);
1581 block_changed.erase(BB);
1583 changed |= (ret == 2);
1592 /// insertion_pre - When a partial redundancy has been identified, eliminate it
1593 /// by inserting appropriate values into the predecessors and a phi node in
1595 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
1596 DenseMap<BasicBlock*, Value*>& avail,
1597 std::map<BasicBlock*, ValueNumberedSet>& new_sets) {
1598 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1599 Value* e2 = avail[*PI];
1600 if (!availableOut[*PI].test(VN.lookup(e2))) {
1601 User* U = cast<User>(e2);
1604 if (isa<BinaryOperator>(U->getOperand(0)) ||
1605 isa<CmpInst>(U->getOperand(0)) ||
1606 isa<ShuffleVectorInst>(U->getOperand(0)) ||
1607 isa<ExtractElementInst>(U->getOperand(0)) ||
1608 isa<InsertElementInst>(U->getOperand(0)) ||
1609 isa<SelectInst>(U->getOperand(0)) ||
1610 isa<CastInst>(U->getOperand(0)) ||
1611 isa<GetElementPtrInst>(U->getOperand(0)))
1612 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1614 s1 = U->getOperand(0);
1618 if (isa<BinaryOperator>(U) ||
1620 isa<ShuffleVectorInst>(U) ||
1621 isa<ExtractElementInst>(U) ||
1622 isa<InsertElementInst>(U) ||
1623 isa<SelectInst>(U)) {
1624 if (isa<BinaryOperator>(U->getOperand(1)) ||
1625 isa<CmpInst>(U->getOperand(1)) ||
1626 isa<ShuffleVectorInst>(U->getOperand(1)) ||
1627 isa<ExtractElementInst>(U->getOperand(1)) ||
1628 isa<InsertElementInst>(U->getOperand(1)) ||
1629 isa<SelectInst>(U->getOperand(1)) ||
1630 isa<CastInst>(U->getOperand(1)) ||
1631 isa<GetElementPtrInst>(U->getOperand(1))) {
1632 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1634 s2 = U->getOperand(1);
1638 // Ternary Operators
1640 if (isa<ShuffleVectorInst>(U) ||
1641 isa<InsertElementInst>(U) ||
1642 isa<SelectInst>(U)) {
1643 if (isa<BinaryOperator>(U->getOperand(2)) ||
1644 isa<CmpInst>(U->getOperand(2)) ||
1645 isa<ShuffleVectorInst>(U->getOperand(2)) ||
1646 isa<ExtractElementInst>(U->getOperand(2)) ||
1647 isa<InsertElementInst>(U->getOperand(2)) ||
1648 isa<SelectInst>(U->getOperand(2)) ||
1649 isa<CastInst>(U->getOperand(2)) ||
1650 isa<GetElementPtrInst>(U->getOperand(2))) {
1651 s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2)));
1653 s3 = U->getOperand(2);
1658 SmallVector<Value*, 4> sVarargs;
1659 if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U)) {
1660 for (GetElementPtrInst::op_iterator OI = G->idx_begin(),
1661 OE = G->idx_end(); OI != OE; ++OI) {
1662 if (isa<BinaryOperator>(*OI) ||
1663 isa<CmpInst>(*OI) ||
1664 isa<ShuffleVectorInst>(*OI) ||
1665 isa<ExtractElementInst>(*OI) ||
1666 isa<InsertElementInst>(*OI) ||
1667 isa<SelectInst>(*OI) ||
1668 isa<CastInst>(*OI) ||
1669 isa<GetElementPtrInst>(*OI)) {
1670 sVarargs.push_back(find_leader(availableOut[*PI],
1673 sVarargs.push_back(*OI);
1679 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1680 newVal = BinaryOperator::Create(BO->getOpcode(), s1, s2,
1681 BO->getName()+".gvnpre",
1682 (*PI)->getTerminator());
1683 else if (CmpInst* C = dyn_cast<CmpInst>(U))
1684 newVal = CmpInst::Create(C->getOpcode(),
1685 C->getPredicate(), s1, s2,
1686 C->getName()+".gvnpre",
1687 (*PI)->getTerminator());
1688 else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
1689 newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre",
1690 (*PI)->getTerminator());
1691 else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U))
1692 newVal = InsertElementInst::Create(s1, s2, s3, S->getName()+".gvnpre",
1693 (*PI)->getTerminator());
1694 else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U))
1695 newVal = ExtractElementInst::Create(s1, s2, S->getName()+".gvnpre",
1696 (*PI)->getTerminator());
1697 else if (SelectInst* S = dyn_cast<SelectInst>(U))
1698 newVal = SelectInst::Create(s1, s2, s3, S->getName()+".gvnpre",
1699 (*PI)->getTerminator());
1700 else if (CastInst* C = dyn_cast<CastInst>(U))
1701 newVal = CastInst::Create(C->getOpcode(), s1, C->getType(),
1702 C->getName()+".gvnpre",
1703 (*PI)->getTerminator());
1704 else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U))
1705 newVal = GetElementPtrInst::Create(s1, sVarargs.begin(), sVarargs.end(),
1706 G->getName()+".gvnpre",
1707 (*PI)->getTerminator());
1709 VN.add(newVal, VN.lookup(U));
1711 ValueNumberedSet& predAvail = availableOut[*PI];
1712 val_replace(predAvail, newVal);
1713 val_replace(new_sets[*PI], newVal);
1714 predAvail.set(VN.lookup(newVal));
1716 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1717 if (av != avail.end())
1719 avail.insert(std::make_pair(*PI, newVal));
1727 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1729 p = PHINode::Create(avail[*PI]->getType(), "gvnpre-join", BB->begin());
1731 p->addIncoming(avail[*PI], *PI);
1734 VN.add(p, VN.lookup(e));
1735 val_replace(availableOut[BB], p);
1736 availableOut[BB].set(VN.lookup(e));
1737 generatedPhis[BB].insert(p);
1738 generatedPhis[BB].set(VN.lookup(e));
1739 new_sets[BB].insert(p);
1740 new_sets[BB].set(VN.lookup(e));
1745 /// insertion_mergepoint - When walking the dom tree, check at each merge
1746 /// block for the possibility of a partial redundancy. If present, eliminate it
1747 unsigned GVNPRE::insertion_mergepoint(SmallVector<Value*, 8>& workList,
1748 df_iterator<DomTreeNode*>& D,
1749 std::map<BasicBlock*, ValueNumberedSet >& new_sets) {
1750 bool changed_function = false;
1751 bool new_stuff = false;
1753 BasicBlock* BB = D->getBlock();
1754 for (unsigned i = 0; i < workList.size(); ++i) {
1755 Value* e = workList[i];
1757 if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1758 isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) ||
1759 isa<ShuffleVectorInst>(e) || isa<SelectInst>(e) || isa<CastInst>(e) ||
1760 isa<GetElementPtrInst>(e)) {
1761 if (availableOut[D->getIDom()->getBlock()].test(VN.lookup(e)))
1764 DenseMap<BasicBlock*, Value*> avail;
1765 bool by_some = false;
1766 bool all_same = true;
1767 Value * first_s = 0;
1769 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1771 Value *e2 = phi_translate(e, *PI, BB);
1772 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1775 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1776 if (av != avail.end())
1778 avail.insert(std::make_pair(*PI, e2));
1781 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1782 if (av != avail.end())
1784 avail.insert(std::make_pair(*PI, e3));
1789 else if (first_s != e3)
1794 if (by_some && !all_same &&
1795 !generatedPhis[BB].test(VN.lookup(e))) {
1796 insertion_pre(e, BB, avail, new_sets);
1798 changed_function = true;
1804 unsigned retval = 0;
1805 if (changed_function)
1813 /// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for
1814 /// merge points. When one is found, check for a partial redundancy. If one is
1815 /// present, eliminate it. Repeat this walk until no changes are made.
1816 bool GVNPRE::insertion(Function& F) {
1817 bool changed_function = false;
1819 DominatorTree &DT = getAnalysis<DominatorTree>();
1821 std::map<BasicBlock*, ValueNumberedSet> new_sets;
1822 bool new_stuff = true;
1825 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1826 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1827 BasicBlock* BB = DI->getBlock();
1832 ValueNumberedSet& availOut = availableOut[BB];
1833 ValueNumberedSet& anticIn = anticipatedIn[BB];
1835 // Replace leaders with leaders inherited from dominator
1836 if (DI->getIDom() != 0) {
1837 ValueNumberedSet& dom_set = new_sets[DI->getIDom()->getBlock()];
1838 for (ValueNumberedSet::iterator I = dom_set.begin(),
1839 E = dom_set.end(); I != E; ++I) {
1840 val_replace(new_sets[BB], *I);
1841 val_replace(availOut, *I);
1845 // If there is more than one predecessor...
1846 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
1847 SmallVector<Value*, 8> workList;
1848 workList.reserve(anticIn.size());
1849 topo_sort(anticIn, workList);
1851 unsigned result = insertion_mergepoint(workList, DI, new_sets);
1853 changed_function = true;
1860 return changed_function;
1863 // GVNPRE::runOnFunction - This is the main transformation entry point for a
1866 bool GVNPRE::runOnFunction(Function &F) {
1867 // Clean out global sets from any previous functions
1869 createdExpressions.clear();
1870 availableOut.clear();
1871 anticipatedIn.clear();
1872 generatedPhis.clear();
1874 bool changed_function = false;
1876 // Phase 1: BuildSets
1877 // This phase calculates the AVAIL_OUT and ANTIC_IN sets
1881 // This phase inserts values to make partially redundant values
1883 changed_function |= insertion(F);
1885 // Phase 3: Eliminate
1886 // This phase performs trivial full redundancy elimination
1887 changed_function |= elimination();
1890 // This phase cleans up values that were created solely
1891 // as leaders for expressions
1894 return changed_function;