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) {
804 LLVMContext &Context = V->getContext();
807 if (CastInst* U = dyn_cast<CastInst>(V)) {
809 if (isa<Instruction>(U->getOperand(0)))
810 newOp1 = phi_translate(U->getOperand(0), pred, succ);
812 newOp1 = U->getOperand(0);
817 if (newOp1 != U->getOperand(0)) {
818 Instruction* newVal = 0;
819 if (CastInst* C = dyn_cast<CastInst>(U))
820 newVal = CastInst::Create(C->getOpcode(),
821 newOp1, C->getType(),
822 C->getName()+".expr");
824 uint32_t v = VN.lookup_or_add(newVal);
826 Value* leader = find_leader(availableOut[pred], v);
828 createdExpressions.push_back(newVal);
838 } if (isa<BinaryOperator>(V) || isa<CmpInst>(V) ||
839 isa<ExtractElementInst>(V)) {
840 User* U = cast<User>(V);
843 if (isa<Instruction>(U->getOperand(0)))
844 newOp1 = phi_translate(U->getOperand(0), pred, succ);
846 newOp1 = U->getOperand(0);
852 if (isa<Instruction>(U->getOperand(1)))
853 newOp2 = phi_translate(U->getOperand(1), pred, succ);
855 newOp2 = U->getOperand(1);
860 if (newOp1 != U->getOperand(0) || newOp2 != U->getOperand(1)) {
861 Instruction* newVal = 0;
862 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
863 newVal = BinaryOperator::Create(BO->getOpcode(),
865 BO->getName()+".expr");
866 else if (CmpInst* C = dyn_cast<CmpInst>(U))
867 newVal = CmpInst::Create(Context, C->getOpcode(),
870 C->getName()+".expr");
871 else if (ExtractElementInst* E = dyn_cast<ExtractElementInst>(U))
872 newVal = ExtractElementInst::Create(newOp1, newOp2, E->getName()+".expr");
874 uint32_t v = VN.lookup_or_add(newVal);
876 Value* leader = find_leader(availableOut[pred], v);
878 createdExpressions.push_back(newVal);
887 // Ternary Operations
888 } else if (isa<ShuffleVectorInst>(V) || isa<InsertElementInst>(V) ||
889 isa<SelectInst>(V)) {
890 User* U = cast<User>(V);
893 if (isa<Instruction>(U->getOperand(0)))
894 newOp1 = phi_translate(U->getOperand(0), pred, succ);
896 newOp1 = U->getOperand(0);
902 if (isa<Instruction>(U->getOperand(1)))
903 newOp2 = phi_translate(U->getOperand(1), pred, succ);
905 newOp2 = U->getOperand(1);
911 if (isa<Instruction>(U->getOperand(2)))
912 newOp3 = phi_translate(U->getOperand(2), pred, succ);
914 newOp3 = U->getOperand(2);
919 if (newOp1 != U->getOperand(0) ||
920 newOp2 != U->getOperand(1) ||
921 newOp3 != U->getOperand(2)) {
922 Instruction* newVal = 0;
923 if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
924 newVal = new ShuffleVectorInst(newOp1, newOp2, newOp3,
925 S->getName() + ".expr");
926 else if (InsertElementInst* I = dyn_cast<InsertElementInst>(U))
927 newVal = InsertElementInst::Create(newOp1, newOp2, newOp3,
928 I->getName() + ".expr");
929 else if (SelectInst* I = dyn_cast<SelectInst>(U))
930 newVal = SelectInst::Create(newOp1, newOp2, newOp3,
931 I->getName() + ".expr");
933 uint32_t v = VN.lookup_or_add(newVal);
935 Value* leader = find_leader(availableOut[pred], v);
937 createdExpressions.push_back(newVal);
947 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
949 if (isa<Instruction>(U->getPointerOperand()))
950 newOp1 = phi_translate(U->getPointerOperand(), pred, succ);
952 newOp1 = U->getPointerOperand();
957 bool changed_idx = false;
958 SmallVector<Value*, 4> newIdx;
959 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
961 if (isa<Instruction>(*I)) {
962 Value* newVal = phi_translate(*I, pred, succ);
963 newIdx.push_back(newVal);
967 newIdx.push_back(*I);
970 if (newOp1 != U->getPointerOperand() || changed_idx) {
971 Instruction* newVal =
972 GetElementPtrInst::Create(newOp1,
973 newIdx.begin(), newIdx.end(),
974 U->getName()+".expr");
976 uint32_t v = VN.lookup_or_add(newVal);
978 Value* leader = find_leader(availableOut[pred], v);
980 createdExpressions.push_back(newVal);
990 } else if (PHINode* P = dyn_cast<PHINode>(V)) {
991 if (P->getParent() == succ)
992 return P->getIncomingValueForBlock(pred);
998 /// phi_translate_set - Perform phi translation on every element of a set
999 void GVNPRE::phi_translate_set(ValueNumberedSet& anticIn,
1000 BasicBlock* pred, BasicBlock* succ,
1001 ValueNumberedSet& out) {
1002 for (ValueNumberedSet::iterator I = anticIn.begin(),
1003 E = anticIn.end(); I != E; ++I) {
1004 Value* V = phi_translate(*I, pred, succ);
1005 if (V != 0 && !out.test(VN.lookup_or_add(V))) {
1007 out.set(VN.lookup(V));
1012 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of
1013 /// whose inputs is an invoke instruction. If this is true, we cannot safely
1014 /// PRE the instruction or anything that depends on it.
1015 bool GVNPRE::dependsOnInvoke(Value* V) {
1016 if (PHINode* p = dyn_cast<PHINode>(V)) {
1017 for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
1018 if (isa<InvokeInst>(*I))
1026 /// clean - Remove all non-opaque values from the set whose operands are not
1027 /// themselves in the set, as well as all values that depend on invokes (see
1029 void GVNPRE::clean(ValueNumberedSet& set) {
1030 SmallVector<Value*, 8> worklist;
1031 worklist.reserve(set.size());
1032 topo_sort(set, worklist);
1034 for (unsigned i = 0; i < worklist.size(); ++i) {
1035 Value* v = worklist[i];
1038 if (CastInst* U = dyn_cast<CastInst>(v)) {
1039 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1040 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1042 lhsValid = !dependsOnInvoke(U->getOperand(0));
1046 set.reset(VN.lookup(U));
1049 // Handle binary ops
1050 } else if (isa<BinaryOperator>(v) || isa<CmpInst>(v) ||
1051 isa<ExtractElementInst>(v)) {
1052 User* U = cast<User>(v);
1054 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1055 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1057 lhsValid = !dependsOnInvoke(U->getOperand(0));
1059 bool rhsValid = !isa<Instruction>(U->getOperand(1));
1060 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
1062 rhsValid = !dependsOnInvoke(U->getOperand(1));
1064 if (!lhsValid || !rhsValid) {
1066 set.reset(VN.lookup(U));
1069 // Handle ternary ops
1070 } else if (isa<ShuffleVectorInst>(v) || isa<InsertElementInst>(v) ||
1071 isa<SelectInst>(v)) {
1072 User* U = cast<User>(v);
1074 bool lhsValid = !isa<Instruction>(U->getOperand(0));
1075 lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1077 lhsValid = !dependsOnInvoke(U->getOperand(0));
1079 bool rhsValid = !isa<Instruction>(U->getOperand(1));
1080 rhsValid |= set.test(VN.lookup(U->getOperand(1)));
1082 rhsValid = !dependsOnInvoke(U->getOperand(1));
1084 bool thirdValid = !isa<Instruction>(U->getOperand(2));
1085 thirdValid |= set.test(VN.lookup(U->getOperand(2)));
1087 thirdValid = !dependsOnInvoke(U->getOperand(2));
1089 if (!lhsValid || !rhsValid || !thirdValid) {
1091 set.reset(VN.lookup(U));
1094 // Handle varargs ops
1095 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(v)) {
1096 bool ptrValid = !isa<Instruction>(U->getPointerOperand());
1097 ptrValid |= set.test(VN.lookup(U->getPointerOperand()));
1099 ptrValid = !dependsOnInvoke(U->getPointerOperand());
1101 bool varValid = true;
1102 for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
1105 varValid &= !isa<Instruction>(*I) || set.test(VN.lookup(*I));
1106 varValid &= !dependsOnInvoke(*I);
1109 if (!ptrValid || !varValid) {
1111 set.reset(VN.lookup(U));
1117 /// topo_sort - Given a set of values, sort them by topological
1118 /// order into the provided vector.
1119 void GVNPRE::topo_sort(ValueNumberedSet& set, SmallVector<Value*, 8>& vec) {
1120 SmallPtrSet<Value*, 16> visited;
1121 SmallVector<Value*, 8> stack;
1122 for (ValueNumberedSet::iterator I = set.begin(), E = set.end();
1124 if (visited.count(*I) == 0)
1125 stack.push_back(*I);
1127 while (!stack.empty()) {
1128 Value* e = stack.back();
1131 if (CastInst* U = dyn_cast<CastInst>(e)) {
1132 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1134 if (l != 0 && isa<Instruction>(l) &&
1135 visited.count(l) == 0)
1143 // Handle binary ops
1144 } else if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1145 isa<ExtractElementInst>(e)) {
1146 User* U = cast<User>(e);
1147 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1148 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1150 if (l != 0 && isa<Instruction>(l) &&
1151 visited.count(l) == 0)
1153 else if (r != 0 && isa<Instruction>(r) &&
1154 visited.count(r) == 0)
1162 // Handle ternary ops
1163 } else if (isa<InsertElementInst>(e) || isa<ShuffleVectorInst>(e) ||
1164 isa<SelectInst>(e)) {
1165 User* U = cast<User>(e);
1166 Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1167 Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1168 Value* m = find_leader(set, VN.lookup(U->getOperand(2)));
1170 if (l != 0 && isa<Instruction>(l) &&
1171 visited.count(l) == 0)
1173 else if (r != 0 && isa<Instruction>(r) &&
1174 visited.count(r) == 0)
1176 else if (m != 0 && isa<Instruction>(m) &&
1177 visited.count(m) == 0)
1185 // Handle vararg ops
1186 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(e)) {
1187 Value* p = find_leader(set, VN.lookup(U->getPointerOperand()));
1189 if (p != 0 && isa<Instruction>(p) &&
1190 visited.count(p) == 0)
1193 bool push_va = false;
1194 for (GetElementPtrInst::op_iterator I = U->idx_begin(),
1195 E = U->idx_end(); I != E; ++I) {
1196 Value * v = find_leader(set, VN.lookup(*I));
1197 if (v != 0 && isa<Instruction>(v) && visited.count(v) == 0) {
1210 // Handle opaque ops
1222 /// dump - Dump a set of values to standard error
1223 void GVNPRE::dump(ValueNumberedSet& s) const {
1225 for (ValueNumberedSet::iterator I = s.begin(), E = s.end();
1227 DOUT << "" << VN.lookup(*I) << ": ";
1228 DEBUG((*I)->dump());
1233 /// elimination - Phase 3 of the main algorithm. Perform full redundancy
1234 /// elimination by walking the dominator tree and removing any instruction that
1235 /// is dominated by another instruction with the same value number.
1236 bool GVNPRE::elimination() {
1237 bool changed_function = false;
1239 SmallVector<std::pair<Instruction*, Value*>, 8> replace;
1240 SmallVector<Instruction*, 8> erase;
1242 DominatorTree& DT = getAnalysis<DominatorTree>();
1244 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1245 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1246 BasicBlock* BB = DI->getBlock();
1248 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1251 if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI) ||
1252 isa<ShuffleVectorInst>(BI) || isa<InsertElementInst>(BI) ||
1253 isa<ExtractElementInst>(BI) || isa<SelectInst>(BI) ||
1254 isa<CastInst>(BI) || isa<GetElementPtrInst>(BI)) {
1256 if (availableOut[BB].test(VN.lookup(BI)) &&
1257 !availableOut[BB].count(BI)) {
1258 Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
1259 if (Instruction* Instr = dyn_cast<Instruction>(leader))
1260 if (Instr->getParent() != 0 && Instr != BI) {
1261 replace.push_back(std::make_pair(BI, leader));
1262 erase.push_back(BI);
1270 while (!replace.empty()) {
1271 std::pair<Instruction*, Value*> rep = replace.back();
1273 rep.first->replaceAllUsesWith(rep.second);
1274 changed_function = true;
1277 for (SmallVector<Instruction*, 8>::iterator I = erase.begin(),
1278 E = erase.end(); I != E; ++I)
1279 (*I)->eraseFromParent();
1281 return changed_function;
1284 /// cleanup - Delete any extraneous values that were created to represent
1285 /// expressions without leaders.
1286 void GVNPRE::cleanup() {
1287 while (!createdExpressions.empty()) {
1288 Instruction* I = createdExpressions.back();
1289 createdExpressions.pop_back();
1295 /// buildsets_availout - When calculating availability, handle an instruction
1296 /// by inserting it into the appropriate sets
1297 void GVNPRE::buildsets_availout(BasicBlock::iterator I,
1298 ValueNumberedSet& currAvail,
1299 ValueNumberedSet& currPhis,
1300 ValueNumberedSet& currExps,
1301 SmallPtrSet<Value*, 16>& currTemps) {
1303 if (PHINode* p = dyn_cast<PHINode>(I)) {
1304 unsigned num = VN.lookup_or_add(p);
1310 } else if (CastInst* U = dyn_cast<CastInst>(I)) {
1311 Value* leftValue = U->getOperand(0);
1313 unsigned num = VN.lookup_or_add(U);
1315 if (isa<Instruction>(leftValue))
1316 if (!currExps.test(VN.lookup(leftValue))) {
1317 currExps.insert(leftValue);
1318 currExps.set(VN.lookup(leftValue));
1321 if (!currExps.test(num)) {
1326 // Handle binary ops
1327 } else if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
1328 isa<ExtractElementInst>(I)) {
1329 User* U = cast<User>(I);
1330 Value* leftValue = U->getOperand(0);
1331 Value* rightValue = U->getOperand(1);
1333 unsigned num = VN.lookup_or_add(U);
1335 if (isa<Instruction>(leftValue))
1336 if (!currExps.test(VN.lookup(leftValue))) {
1337 currExps.insert(leftValue);
1338 currExps.set(VN.lookup(leftValue));
1341 if (isa<Instruction>(rightValue))
1342 if (!currExps.test(VN.lookup(rightValue))) {
1343 currExps.insert(rightValue);
1344 currExps.set(VN.lookup(rightValue));
1347 if (!currExps.test(num)) {
1352 // Handle ternary ops
1353 } else if (isa<InsertElementInst>(I) || isa<ShuffleVectorInst>(I) ||
1354 isa<SelectInst>(I)) {
1355 User* U = cast<User>(I);
1356 Value* leftValue = U->getOperand(0);
1357 Value* rightValue = U->getOperand(1);
1358 Value* thirdValue = U->getOperand(2);
1360 VN.lookup_or_add(U);
1362 unsigned num = VN.lookup_or_add(U);
1364 if (isa<Instruction>(leftValue))
1365 if (!currExps.test(VN.lookup(leftValue))) {
1366 currExps.insert(leftValue);
1367 currExps.set(VN.lookup(leftValue));
1369 if (isa<Instruction>(rightValue))
1370 if (!currExps.test(VN.lookup(rightValue))) {
1371 currExps.insert(rightValue);
1372 currExps.set(VN.lookup(rightValue));
1374 if (isa<Instruction>(thirdValue))
1375 if (!currExps.test(VN.lookup(thirdValue))) {
1376 currExps.insert(thirdValue);
1377 currExps.set(VN.lookup(thirdValue));
1380 if (!currExps.test(num)) {
1385 // Handle vararg ops
1386 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(I)) {
1387 Value* ptrValue = U->getPointerOperand();
1389 VN.lookup_or_add(U);
1391 unsigned num = VN.lookup_or_add(U);
1393 if (isa<Instruction>(ptrValue))
1394 if (!currExps.test(VN.lookup(ptrValue))) {
1395 currExps.insert(ptrValue);
1396 currExps.set(VN.lookup(ptrValue));
1399 for (GetElementPtrInst::op_iterator OI = U->idx_begin(), OE = U->idx_end();
1401 if (isa<Instruction>(*OI) && !currExps.test(VN.lookup(*OI))) {
1402 currExps.insert(*OI);
1403 currExps.set(VN.lookup(*OI));
1406 if (!currExps.test(VN.lookup(U))) {
1411 // Handle opaque ops
1412 } else if (!I->isTerminator()){
1413 VN.lookup_or_add(I);
1415 currTemps.insert(I);
1418 if (!I->isTerminator())
1419 if (!currAvail.test(VN.lookup(I))) {
1420 currAvail.insert(I);
1421 currAvail.set(VN.lookup(I));
1425 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
1426 /// set as a function of the ANTIC_IN set of the block's predecessors
1427 bool GVNPRE::buildsets_anticout(BasicBlock* BB,
1428 ValueNumberedSet& anticOut,
1429 SmallPtrSet<BasicBlock*, 8>& visited) {
1430 if (BB->getTerminator()->getNumSuccessors() == 1) {
1431 if (BB->getTerminator()->getSuccessor(0) != BB &&
1432 visited.count(BB->getTerminator()->getSuccessor(0)) == 0) {
1436 phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
1437 BB, BB->getTerminator()->getSuccessor(0), anticOut);
1439 } else if (BB->getTerminator()->getNumSuccessors() > 1) {
1440 BasicBlock* first = BB->getTerminator()->getSuccessor(0);
1441 for (ValueNumberedSet::iterator I = anticipatedIn[first].begin(),
1442 E = anticipatedIn[first].end(); I != E; ++I) {
1443 anticOut.insert(*I);
1444 anticOut.set(VN.lookup(*I));
1447 for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
1448 BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
1449 ValueNumberedSet& succAnticIn = anticipatedIn[currSucc];
1451 SmallVector<Value*, 16> temp;
1453 for (ValueNumberedSet::iterator I = anticOut.begin(),
1454 E = anticOut.end(); I != E; ++I)
1455 if (!succAnticIn.test(VN.lookup(*I)))
1458 for (SmallVector<Value*, 16>::iterator I = temp.begin(), E = temp.end();
1461 anticOut.reset(VN.lookup(*I));
1469 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
1470 /// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN
1471 /// sets populated in buildsets_availout
1472 unsigned GVNPRE::buildsets_anticin(BasicBlock* BB,
1473 ValueNumberedSet& anticOut,
1474 ValueNumberedSet& currExps,
1475 SmallPtrSet<Value*, 16>& currTemps,
1476 SmallPtrSet<BasicBlock*, 8>& visited) {
1477 ValueNumberedSet& anticIn = anticipatedIn[BB];
1478 unsigned old = anticIn.size();
1480 bool defer = buildsets_anticout(BB, anticOut, visited);
1486 for (ValueNumberedSet::iterator I = anticOut.begin(),
1487 E = anticOut.end(); I != E; ++I) {
1489 anticIn.set(VN.lookup(*I));
1491 for (ValueNumberedSet::iterator I = currExps.begin(),
1492 E = currExps.end(); I != E; ++I) {
1493 if (!anticIn.test(VN.lookup(*I))) {
1495 anticIn.set(VN.lookup(*I));
1499 for (SmallPtrSet<Value*, 16>::iterator I = currTemps.begin(),
1500 E = currTemps.end(); I != E; ++I) {
1502 anticIn.reset(VN.lookup(*I));
1508 if (old != anticIn.size())
1514 /// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT
1515 /// and the ANTIC_IN sets.
1516 void GVNPRE::buildsets(Function& F) {
1517 DenseMap<BasicBlock*, ValueNumberedSet> generatedExpressions;
1518 DenseMap<BasicBlock*, SmallPtrSet<Value*, 16> > generatedTemporaries;
1520 DominatorTree &DT = getAnalysis<DominatorTree>();
1522 // Phase 1, Part 1: calculate AVAIL_OUT
1524 // Top-down walk of the dominator tree
1525 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1526 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1528 // Get the sets to update for this block
1529 ValueNumberedSet& currExps = generatedExpressions[DI->getBlock()];
1530 ValueNumberedSet& currPhis = generatedPhis[DI->getBlock()];
1531 SmallPtrSet<Value*, 16>& currTemps = generatedTemporaries[DI->getBlock()];
1532 ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
1534 BasicBlock* BB = DI->getBlock();
1536 // A block inherits AVAIL_OUT from its dominator
1537 if (DI->getIDom() != 0)
1538 currAvail = availableOut[DI->getIDom()->getBlock()];
1540 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1542 buildsets_availout(BI, currAvail, currPhis, currExps,
1547 // Phase 1, Part 2: calculate ANTIC_IN
1549 SmallPtrSet<BasicBlock*, 8> visited;
1550 SmallPtrSet<BasicBlock*, 4> block_changed;
1551 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
1552 block_changed.insert(FI);
1554 bool changed = true;
1555 unsigned iterations = 0;
1559 ValueNumberedSet anticOut;
1561 // Postorder walk of the CFG
1562 for (po_iterator<BasicBlock*> BBI = po_begin(&F.getEntryBlock()),
1563 BBE = po_end(&F.getEntryBlock()); BBI != BBE; ++BBI) {
1564 BasicBlock* BB = *BBI;
1566 if (block_changed.count(BB) != 0) {
1567 unsigned ret = buildsets_anticin(BB, anticOut,generatedExpressions[BB],
1568 generatedTemporaries[BB], visited);
1577 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1579 block_changed.insert(*PI);
1582 block_changed.erase(BB);
1584 changed |= (ret == 2);
1593 /// insertion_pre - When a partial redundancy has been identified, eliminate it
1594 /// by inserting appropriate values into the predecessors and a phi node in
1596 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
1597 DenseMap<BasicBlock*, Value*>& avail,
1598 std::map<BasicBlock*, ValueNumberedSet>& new_sets) {
1599 LLVMContext &Context = e->getContext();
1600 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1601 Value* e2 = avail[*PI];
1602 if (!availableOut[*PI].test(VN.lookup(e2))) {
1603 User* U = cast<User>(e2);
1606 if (isa<BinaryOperator>(U->getOperand(0)) ||
1607 isa<CmpInst>(U->getOperand(0)) ||
1608 isa<ShuffleVectorInst>(U->getOperand(0)) ||
1609 isa<ExtractElementInst>(U->getOperand(0)) ||
1610 isa<InsertElementInst>(U->getOperand(0)) ||
1611 isa<SelectInst>(U->getOperand(0)) ||
1612 isa<CastInst>(U->getOperand(0)) ||
1613 isa<GetElementPtrInst>(U->getOperand(0)))
1614 s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1616 s1 = U->getOperand(0);
1620 if (isa<BinaryOperator>(U) ||
1622 isa<ShuffleVectorInst>(U) ||
1623 isa<ExtractElementInst>(U) ||
1624 isa<InsertElementInst>(U) ||
1625 isa<SelectInst>(U)) {
1626 if (isa<BinaryOperator>(U->getOperand(1)) ||
1627 isa<CmpInst>(U->getOperand(1)) ||
1628 isa<ShuffleVectorInst>(U->getOperand(1)) ||
1629 isa<ExtractElementInst>(U->getOperand(1)) ||
1630 isa<InsertElementInst>(U->getOperand(1)) ||
1631 isa<SelectInst>(U->getOperand(1)) ||
1632 isa<CastInst>(U->getOperand(1)) ||
1633 isa<GetElementPtrInst>(U->getOperand(1))) {
1634 s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1636 s2 = U->getOperand(1);
1640 // Ternary Operators
1642 if (isa<ShuffleVectorInst>(U) ||
1643 isa<InsertElementInst>(U) ||
1644 isa<SelectInst>(U)) {
1645 if (isa<BinaryOperator>(U->getOperand(2)) ||
1646 isa<CmpInst>(U->getOperand(2)) ||
1647 isa<ShuffleVectorInst>(U->getOperand(2)) ||
1648 isa<ExtractElementInst>(U->getOperand(2)) ||
1649 isa<InsertElementInst>(U->getOperand(2)) ||
1650 isa<SelectInst>(U->getOperand(2)) ||
1651 isa<CastInst>(U->getOperand(2)) ||
1652 isa<GetElementPtrInst>(U->getOperand(2))) {
1653 s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2)));
1655 s3 = U->getOperand(2);
1660 SmallVector<Value*, 4> sVarargs;
1661 if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U)) {
1662 for (GetElementPtrInst::op_iterator OI = G->idx_begin(),
1663 OE = G->idx_end(); OI != OE; ++OI) {
1664 if (isa<BinaryOperator>(*OI) ||
1665 isa<CmpInst>(*OI) ||
1666 isa<ShuffleVectorInst>(*OI) ||
1667 isa<ExtractElementInst>(*OI) ||
1668 isa<InsertElementInst>(*OI) ||
1669 isa<SelectInst>(*OI) ||
1670 isa<CastInst>(*OI) ||
1671 isa<GetElementPtrInst>(*OI)) {
1672 sVarargs.push_back(find_leader(availableOut[*PI],
1675 sVarargs.push_back(*OI);
1681 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1682 newVal = BinaryOperator::Create(BO->getOpcode(), s1, s2,
1683 BO->getName()+".gvnpre",
1684 (*PI)->getTerminator());
1685 else if (CmpInst* C = dyn_cast<CmpInst>(U))
1686 newVal = CmpInst::Create(Context, C->getOpcode(),
1687 C->getPredicate(), s1, s2,
1688 C->getName()+".gvnpre",
1689 (*PI)->getTerminator());
1690 else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
1691 newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre",
1692 (*PI)->getTerminator());
1693 else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U))
1694 newVal = InsertElementInst::Create(s1, s2, s3, S->getName()+".gvnpre",
1695 (*PI)->getTerminator());
1696 else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U))
1697 newVal = ExtractElementInst::Create(s1, s2, S->getName()+".gvnpre",
1698 (*PI)->getTerminator());
1699 else if (SelectInst* S = dyn_cast<SelectInst>(U))
1700 newVal = SelectInst::Create(s1, s2, s3, S->getName()+".gvnpre",
1701 (*PI)->getTerminator());
1702 else if (CastInst* C = dyn_cast<CastInst>(U))
1703 newVal = CastInst::Create(C->getOpcode(), s1, C->getType(),
1704 C->getName()+".gvnpre",
1705 (*PI)->getTerminator());
1706 else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U))
1707 newVal = GetElementPtrInst::Create(s1, sVarargs.begin(), sVarargs.end(),
1708 G->getName()+".gvnpre",
1709 (*PI)->getTerminator());
1711 VN.add(newVal, VN.lookup(U));
1713 ValueNumberedSet& predAvail = availableOut[*PI];
1714 val_replace(predAvail, newVal);
1715 val_replace(new_sets[*PI], newVal);
1716 predAvail.set(VN.lookup(newVal));
1718 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1719 if (av != avail.end())
1721 avail.insert(std::make_pair(*PI, newVal));
1729 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1731 p = PHINode::Create(avail[*PI]->getType(), "gvnpre-join", BB->begin());
1733 p->addIncoming(avail[*PI], *PI);
1736 VN.add(p, VN.lookup(e));
1737 val_replace(availableOut[BB], p);
1738 availableOut[BB].set(VN.lookup(e));
1739 generatedPhis[BB].insert(p);
1740 generatedPhis[BB].set(VN.lookup(e));
1741 new_sets[BB].insert(p);
1742 new_sets[BB].set(VN.lookup(e));
1747 /// insertion_mergepoint - When walking the dom tree, check at each merge
1748 /// block for the possibility of a partial redundancy. If present, eliminate it
1749 unsigned GVNPRE::insertion_mergepoint(SmallVector<Value*, 8>& workList,
1750 df_iterator<DomTreeNode*>& D,
1751 std::map<BasicBlock*, ValueNumberedSet >& new_sets) {
1752 bool changed_function = false;
1753 bool new_stuff = false;
1755 BasicBlock* BB = D->getBlock();
1756 for (unsigned i = 0; i < workList.size(); ++i) {
1757 Value* e = workList[i];
1759 if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1760 isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) ||
1761 isa<ShuffleVectorInst>(e) || isa<SelectInst>(e) || isa<CastInst>(e) ||
1762 isa<GetElementPtrInst>(e)) {
1763 if (availableOut[D->getIDom()->getBlock()].test(VN.lookup(e)))
1766 DenseMap<BasicBlock*, Value*> avail;
1767 bool by_some = false;
1768 bool all_same = true;
1769 Value * first_s = 0;
1771 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1773 Value *e2 = phi_translate(e, *PI, BB);
1774 Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1777 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1778 if (av != avail.end())
1780 avail.insert(std::make_pair(*PI, e2));
1783 DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1784 if (av != avail.end())
1786 avail.insert(std::make_pair(*PI, e3));
1791 else if (first_s != e3)
1796 if (by_some && !all_same &&
1797 !generatedPhis[BB].test(VN.lookup(e))) {
1798 insertion_pre(e, BB, avail, new_sets);
1800 changed_function = true;
1806 unsigned retval = 0;
1807 if (changed_function)
1815 /// insert - Phase 2 of the main algorithm. Walk the dominator tree looking for
1816 /// merge points. When one is found, check for a partial redundancy. If one is
1817 /// present, eliminate it. Repeat this walk until no changes are made.
1818 bool GVNPRE::insertion(Function& F) {
1819 bool changed_function = false;
1821 DominatorTree &DT = getAnalysis<DominatorTree>();
1823 std::map<BasicBlock*, ValueNumberedSet> new_sets;
1824 bool new_stuff = true;
1827 for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1828 E = df_end(DT.getRootNode()); DI != E; ++DI) {
1829 BasicBlock* BB = DI->getBlock();
1834 ValueNumberedSet& availOut = availableOut[BB];
1835 ValueNumberedSet& anticIn = anticipatedIn[BB];
1837 // Replace leaders with leaders inherited from dominator
1838 if (DI->getIDom() != 0) {
1839 ValueNumberedSet& dom_set = new_sets[DI->getIDom()->getBlock()];
1840 for (ValueNumberedSet::iterator I = dom_set.begin(),
1841 E = dom_set.end(); I != E; ++I) {
1842 val_replace(new_sets[BB], *I);
1843 val_replace(availOut, *I);
1847 // If there is more than one predecessor...
1848 if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
1849 SmallVector<Value*, 8> workList;
1850 workList.reserve(anticIn.size());
1851 topo_sort(anticIn, workList);
1853 unsigned result = insertion_mergepoint(workList, DI, new_sets);
1855 changed_function = true;
1862 return changed_function;
1865 // GVNPRE::runOnFunction - This is the main transformation entry point for a
1868 bool GVNPRE::runOnFunction(Function &F) {
1869 // Clean out global sets from any previous functions
1871 createdExpressions.clear();
1872 availableOut.clear();
1873 anticipatedIn.clear();
1874 generatedPhis.clear();
1876 bool changed_function = false;
1878 // Phase 1: BuildSets
1879 // This phase calculates the AVAIL_OUT and ANTIC_IN sets
1883 // This phase inserts values to make partially redundant values
1885 changed_function |= insertion(F);
1887 // Phase 3: Eliminate
1888 // This phase performs trivial full redundancy elimination
1889 changed_function |= elimination();
1892 // This phase cleans up values that were created solely
1893 // as leaders for expressions
1896 return changed_function;