GVN.cpp revision 6bb0bd52ecf7481c26cb2d211d6f4f41a6edc855 
1//===- GVN.cpp - Eliminate redundant values and loads ------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This pass performs global value numbering to eliminate fully redundant
11// instructions.  It also performs simple dead load elimination.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "gvn"
16
17#include "llvm/Transforms/Scalar.h"
18#include "llvm/BasicBlock.h"
19#include "llvm/Constants.h"
20#include "llvm/DerivedTypes.h"
21#include "llvm/Function.h"
22#include "llvm/IntrinsicInst.h"
23#include "llvm/Instructions.h"
24#include "llvm/ParameterAttributes.h"
25#include "llvm/Value.h"
26#include "llvm/ADT/BitVector.h"
27#include "llvm/ADT/DenseMap.h"
28#include "llvm/ADT/DepthFirstIterator.h"
29#include "llvm/ADT/SmallPtrSet.h"
30#include "llvm/ADT/SmallVector.h"
31#include "llvm/ADT/Statistic.h"
32#include "llvm/Analysis/Dominators.h"
33#include "llvm/Analysis/AliasAnalysis.h"
34#include "llvm/Analysis/MemoryDependenceAnalysis.h"
35#include "llvm/Support/CFG.h"
36#include "llvm/Support/Compiler.h"
37#include "llvm/Target/TargetData.h"
38using namespace llvm;
39
40//===----------------------------------------------------------------------===//
41//                         ValueTable Class
42//===----------------------------------------------------------------------===//
43
44/// This class holds the mapping between values and value numbers.  It is used
45/// as an efficient mechanism to determine the expression-wise equivalence of
46/// two values.
47namespace {
48  struct VISIBILITY_HIDDEN Expression {
49    enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
50                            FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
51                            ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
52                            ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
53                            FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
54                            FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
55                            FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
56                            SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
57                            FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
58                            PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, EMPTY,
59                            TOMBSTONE };
60
61    ExpressionOpcode opcode;
62    const Type* type;
63    uint32_t firstVN;
64    uint32_t secondVN;
65    uint32_t thirdVN;
66    SmallVector<uint32_t, 4> varargs;
67    Value* function;
68
69    Expression() { }
70    Expression(ExpressionOpcode o) : opcode(o) { }
71
72    bool operator==(const Expression &other) const {
73      if (opcode != other.opcode)
74        return false;
75      else if (opcode == EMPTY || opcode == TOMBSTONE)
76        return true;
77      else if (type != other.type)
78        return false;
79      else if (function != other.function)
80        return false;
81      else if (firstVN != other.firstVN)
82        return false;
83      else if (secondVN != other.secondVN)
84        return false;
85      else if (thirdVN != other.thirdVN)
86        return false;
87      else {
88        if (varargs.size() != other.varargs.size())
89          return false;
90
91        for (size_t i = 0; i < varargs.size(); ++i)
92          if (varargs[i] != other.varargs[i])
93            return false;
94
95        return true;
96      }
97    }
98
99    bool operator!=(const Expression &other) const {
100      if (opcode != other.opcode)
101        return true;
102      else if (opcode == EMPTY || opcode == TOMBSTONE)
103        return false;
104      else if (type != other.type)
105        return true;
106      else if (function != other.function)
107        return true;
108      else if (firstVN != other.firstVN)
109        return true;
110      else if (secondVN != other.secondVN)
111        return true;
112      else if (thirdVN != other.thirdVN)
113        return true;
114      else {
115        if (varargs.size() != other.varargs.size())
116          return true;
117
118        for (size_t i = 0; i < varargs.size(); ++i)
119          if (varargs[i] != other.varargs[i])
120            return true;
121
122          return false;
123      }
124    }
125  };
126
127  class VISIBILITY_HIDDEN ValueTable {
128    private:
129      DenseMap<Value*, uint32_t> valueNumbering;
130      DenseMap<Expression, uint32_t> expressionNumbering;
131      AliasAnalysis* AA;
132
133      uint32_t nextValueNumber;
134
135      Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
136      Expression::ExpressionOpcode getOpcode(CmpInst* C);
137      Expression::ExpressionOpcode getOpcode(CastInst* C);
138      Expression create_expression(BinaryOperator* BO);
139      Expression create_expression(CmpInst* C);
140      Expression create_expression(ShuffleVectorInst* V);
141      Expression create_expression(ExtractElementInst* C);
142      Expression create_expression(InsertElementInst* V);
143      Expression create_expression(SelectInst* V);
144      Expression create_expression(CastInst* C);
145      Expression create_expression(GetElementPtrInst* G);
146      Expression create_expression(CallInst* C);
147    public:
148      ValueTable() : nextValueNumber(1) { }
149      uint32_t lookup_or_add(Value* V);
150      uint32_t lookup(Value* V) const;
151      void add(Value* V, uint32_t num);
152      void clear();
153      void erase(Value* v);
154      unsigned size();
155      void setAliasAnalysis(AliasAnalysis* A) { AA = A; }
156      uint32_t hash_operand(Value* v);
157  };
158}
159
160namespace llvm {
161template <> struct DenseMapInfo<Expression> {
162  static inline Expression getEmptyKey() {
163    return Expression(Expression::EMPTY);
164  }
165
166  static inline Expression getTombstoneKey() {
167    return Expression(Expression::TOMBSTONE);
168  }
169
170  static unsigned getHashValue(const Expression e) {
171    unsigned hash = e.opcode;
172
173    hash = e.firstVN + hash * 37;
174    hash = e.secondVN + hash * 37;
175    hash = e.thirdVN + hash * 37;
176
177    hash = ((unsigned)((uintptr_t)e.type >> 4) ^
178            (unsigned)((uintptr_t)e.type >> 9)) +
179           hash * 37;
180
181    for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
182         E = e.varargs.end(); I != E; ++I)
183      hash = *I + hash * 37;
184
185    hash = ((unsigned)((uintptr_t)e.function >> 4) ^
186            (unsigned)((uintptr_t)e.function >> 9)) +
187           hash * 37;
188
189    return hash;
190  }
191  static bool isEqual(const Expression &LHS, const Expression &RHS) {
192    return LHS == RHS;
193  }
194  static bool isPod() { return true; }
195};
196}
197
198//===----------------------------------------------------------------------===//
199//                     ValueTable Internal Functions
200//===----------------------------------------------------------------------===//
201Expression::ExpressionOpcode
202                             ValueTable::getOpcode(BinaryOperator* BO) {
203  switch(BO->getOpcode()) {
204    case Instruction::Add:
205      return Expression::ADD;
206    case Instruction::Sub:
207      return Expression::SUB;
208    case Instruction::Mul:
209      return Expression::MUL;
210    case Instruction::UDiv:
211      return Expression::UDIV;
212    case Instruction::SDiv:
213      return Expression::SDIV;
214    case Instruction::FDiv:
215      return Expression::FDIV;
216    case Instruction::URem:
217      return Expression::UREM;
218    case Instruction::SRem:
219      return Expression::SREM;
220    case Instruction::FRem:
221      return Expression::FREM;
222    case Instruction::Shl:
223      return Expression::SHL;
224    case Instruction::LShr:
225      return Expression::LSHR;
226    case Instruction::AShr:
227      return Expression::ASHR;
228    case Instruction::And:
229      return Expression::AND;
230    case Instruction::Or:
231      return Expression::OR;
232    case Instruction::Xor:
233      return Expression::XOR;
234
235    // THIS SHOULD NEVER HAPPEN
236    default:
237      assert(0 && "Binary operator with unknown opcode?");
238      return Expression::ADD;
239  }
240}
241
242Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
243  if (C->getOpcode() == Instruction::ICmp) {
244    switch (C->getPredicate()) {
245      case ICmpInst::ICMP_EQ:
246        return Expression::ICMPEQ;
247      case ICmpInst::ICMP_NE:
248        return Expression::ICMPNE;
249      case ICmpInst::ICMP_UGT:
250        return Expression::ICMPUGT;
251      case ICmpInst::ICMP_UGE:
252        return Expression::ICMPUGE;
253      case ICmpInst::ICMP_ULT:
254        return Expression::ICMPULT;
255      case ICmpInst::ICMP_ULE:
256        return Expression::ICMPULE;
257      case ICmpInst::ICMP_SGT:
258        return Expression::ICMPSGT;
259      case ICmpInst::ICMP_SGE:
260        return Expression::ICMPSGE;
261      case ICmpInst::ICMP_SLT:
262        return Expression::ICMPSLT;
263      case ICmpInst::ICMP_SLE:
264        return Expression::ICMPSLE;
265
266      // THIS SHOULD NEVER HAPPEN
267      default:
268        assert(0 && "Comparison with unknown predicate?");
269        return Expression::ICMPEQ;
270    }
271  } else {
272    switch (C->getPredicate()) {
273      case FCmpInst::FCMP_OEQ:
274        return Expression::FCMPOEQ;
275      case FCmpInst::FCMP_OGT:
276        return Expression::FCMPOGT;
277      case FCmpInst::FCMP_OGE:
278        return Expression::FCMPOGE;
279      case FCmpInst::FCMP_OLT:
280        return Expression::FCMPOLT;
281      case FCmpInst::FCMP_OLE:
282        return Expression::FCMPOLE;
283      case FCmpInst::FCMP_ONE:
284        return Expression::FCMPONE;
285      case FCmpInst::FCMP_ORD:
286        return Expression::FCMPORD;
287      case FCmpInst::FCMP_UNO:
288        return Expression::FCMPUNO;
289      case FCmpInst::FCMP_UEQ:
290        return Expression::FCMPUEQ;
291      case FCmpInst::FCMP_UGT:
292        return Expression::FCMPUGT;
293      case FCmpInst::FCMP_UGE:
294        return Expression::FCMPUGE;
295      case FCmpInst::FCMP_ULT:
296        return Expression::FCMPULT;
297      case FCmpInst::FCMP_ULE:
298        return Expression::FCMPULE;
299      case FCmpInst::FCMP_UNE:
300        return Expression::FCMPUNE;
301
302      // THIS SHOULD NEVER HAPPEN
303      default:
304        assert(0 && "Comparison with unknown predicate?");
305        return Expression::FCMPOEQ;
306    }
307  }
308}
309
310Expression::ExpressionOpcode
311                             ValueTable::getOpcode(CastInst* C) {
312  switch(C->getOpcode()) {
313    case Instruction::Trunc:
314      return Expression::TRUNC;
315    case Instruction::ZExt:
316      return Expression::ZEXT;
317    case Instruction::SExt:
318      return Expression::SEXT;
319    case Instruction::FPToUI:
320      return Expression::FPTOUI;
321    case Instruction::FPToSI:
322      return Expression::FPTOSI;
323    case Instruction::UIToFP:
324      return Expression::UITOFP;
325    case Instruction::SIToFP:
326      return Expression::SITOFP;
327    case Instruction::FPTrunc:
328      return Expression::FPTRUNC;
329    case Instruction::FPExt:
330      return Expression::FPEXT;
331    case Instruction::PtrToInt:
332      return Expression::PTRTOINT;
333    case Instruction::IntToPtr:
334      return Expression::INTTOPTR;
335    case Instruction::BitCast:
336      return Expression::BITCAST;
337
338    // THIS SHOULD NEVER HAPPEN
339    default:
340      assert(0 && "Cast operator with unknown opcode?");
341      return Expression::BITCAST;
342  }
343}
344
345uint32_t ValueTable::hash_operand(Value* v) {
346  if (CallInst* CI = dyn_cast<CallInst>(v))
347    if (!AA->doesNotAccessMemory(CI))
348      return nextValueNumber++;
349
350  return lookup_or_add(v);
351}
352
353Expression ValueTable::create_expression(CallInst* C) {
354  Expression e;
355
356  e.type = C->getType();
357  e.firstVN = 0;
358  e.secondVN = 0;
359  e.thirdVN = 0;
360  e.function = C->getCalledFunction();
361  e.opcode = Expression::CALL;
362
363  for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end();
364       I != E; ++I)
365    e.varargs.push_back(hash_operand(*I));
366
367  return e;
368}
369
370Expression ValueTable::create_expression(BinaryOperator* BO) {
371  Expression e;
372
373  e.firstVN = hash_operand(BO->getOperand(0));
374  e.secondVN = hash_operand(BO->getOperand(1));
375  e.thirdVN = 0;
376  e.function = 0;
377  e.type = BO->getType();
378  e.opcode = getOpcode(BO);
379
380  return e;
381}
382
383Expression ValueTable::create_expression(CmpInst* C) {
384  Expression e;
385
386  e.firstVN = hash_operand(C->getOperand(0));
387  e.secondVN = hash_operand(C->getOperand(1));
388  e.thirdVN = 0;
389  e.function = 0;
390  e.type = C->getType();
391  e.opcode = getOpcode(C);
392
393  return e;
394}
395
396Expression ValueTable::create_expression(CastInst* C) {
397  Expression e;
398
399  e.firstVN = hash_operand(C->getOperand(0));
400  e.secondVN = 0;
401  e.thirdVN = 0;
402  e.function = 0;
403  e.type = C->getType();
404  e.opcode = getOpcode(C);
405
406  return e;
407}
408
409Expression ValueTable::create_expression(ShuffleVectorInst* S) {
410  Expression e;
411
412  e.firstVN = hash_operand(S->getOperand(0));
413  e.secondVN = hash_operand(S->getOperand(1));
414  e.thirdVN = hash_operand(S->getOperand(2));
415  e.function = 0;
416  e.type = S->getType();
417  e.opcode = Expression::SHUFFLE;
418
419  return e;
420}
421
422Expression ValueTable::create_expression(ExtractElementInst* E) {
423  Expression e;
424
425  e.firstVN = hash_operand(E->getOperand(0));
426  e.secondVN = hash_operand(E->getOperand(1));
427  e.thirdVN = 0;
428  e.function = 0;
429  e.type = E->getType();
430  e.opcode = Expression::EXTRACT;
431
432  return e;
433}
434
435Expression ValueTable::create_expression(InsertElementInst* I) {
436  Expression e;
437
438  e.firstVN = hash_operand(I->getOperand(0));
439  e.secondVN = hash_operand(I->getOperand(1));
440  e.thirdVN = hash_operand(I->getOperand(2));
441  e.function = 0;
442  e.type = I->getType();
443  e.opcode = Expression::INSERT;
444
445  return e;
446}
447
448Expression ValueTable::create_expression(SelectInst* I) {
449  Expression e;
450
451  e.firstVN = hash_operand(I->getCondition());
452  e.secondVN = hash_operand(I->getTrueValue());
453  e.thirdVN = hash_operand(I->getFalseValue());
454  e.function = 0;
455  e.type = I->getType();
456  e.opcode = Expression::SELECT;
457
458  return e;
459}
460
461Expression ValueTable::create_expression(GetElementPtrInst* G) {
462  Expression e;
463
464  e.firstVN = hash_operand(G->getPointerOperand());
465  e.secondVN = 0;
466  e.thirdVN = 0;
467  e.function = 0;
468  e.type = G->getType();
469  e.opcode = Expression::GEP;
470
471  for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
472       I != E; ++I)
473    e.varargs.push_back(hash_operand(*I));
474
475  return e;
476}
477
478//===----------------------------------------------------------------------===//
479//                     ValueTable External Functions
480//===----------------------------------------------------------------------===//
481
482/// lookup_or_add - Returns the value number for the specified value, assigning
483/// it a new number if it did not have one before.
484uint32_t ValueTable::lookup_or_add(Value* V) {
485  DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
486  if (VI != valueNumbering.end())
487    return VI->second;
488
489  if (CallInst* C = dyn_cast<CallInst>(V)) {
490    if (AA->onlyReadsMemory(C)) { // includes doesNotAccessMemory
491      Expression e = create_expression(C);
492
493      DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
494      if (EI != expressionNumbering.end()) {
495        valueNumbering.insert(std::make_pair(V, EI->second));
496        return EI->second;
497      } else {
498        expressionNumbering.insert(std::make_pair(e, nextValueNumber));
499        valueNumbering.insert(std::make_pair(V, nextValueNumber));
500
501        return nextValueNumber++;
502      }
503    } else {
504      valueNumbering.insert(std::make_pair(V, nextValueNumber));
505      return nextValueNumber++;
506    }
507  } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
508    Expression e = create_expression(BO);
509
510    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
511    if (EI != expressionNumbering.end()) {
512      valueNumbering.insert(std::make_pair(V, EI->second));
513      return EI->second;
514    } else {
515      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
516      valueNumbering.insert(std::make_pair(V, nextValueNumber));
517
518      return nextValueNumber++;
519    }
520  } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
521    Expression e = create_expression(C);
522
523    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
524    if (EI != expressionNumbering.end()) {
525      valueNumbering.insert(std::make_pair(V, EI->second));
526      return EI->second;
527    } else {
528      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
529      valueNumbering.insert(std::make_pair(V, nextValueNumber));
530
531      return nextValueNumber++;
532    }
533  } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
534    Expression e = create_expression(U);
535
536    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
537    if (EI != expressionNumbering.end()) {
538      valueNumbering.insert(std::make_pair(V, EI->second));
539      return EI->second;
540    } else {
541      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
542      valueNumbering.insert(std::make_pair(V, nextValueNumber));
543
544      return nextValueNumber++;
545    }
546  } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
547    Expression e = create_expression(U);
548
549    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
550    if (EI != expressionNumbering.end()) {
551      valueNumbering.insert(std::make_pair(V, EI->second));
552      return EI->second;
553    } else {
554      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
555      valueNumbering.insert(std::make_pair(V, nextValueNumber));
556
557      return nextValueNumber++;
558    }
559  } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
560    Expression e = create_expression(U);
561
562    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
563    if (EI != expressionNumbering.end()) {
564      valueNumbering.insert(std::make_pair(V, EI->second));
565      return EI->second;
566    } else {
567      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
568      valueNumbering.insert(std::make_pair(V, nextValueNumber));
569
570      return nextValueNumber++;
571    }
572  } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
573    Expression e = create_expression(U);
574
575    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
576    if (EI != expressionNumbering.end()) {
577      valueNumbering.insert(std::make_pair(V, EI->second));
578      return EI->second;
579    } else {
580      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
581      valueNumbering.insert(std::make_pair(V, nextValueNumber));
582
583      return nextValueNumber++;
584    }
585  } else if (CastInst* U = dyn_cast<CastInst>(V)) {
586    Expression e = create_expression(U);
587
588    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
589    if (EI != expressionNumbering.end()) {
590      valueNumbering.insert(std::make_pair(V, EI->second));
591      return EI->second;
592    } else {
593      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
594      valueNumbering.insert(std::make_pair(V, nextValueNumber));
595
596      return nextValueNumber++;
597    }
598  } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
599    Expression e = create_expression(U);
600
601    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
602    if (EI != expressionNumbering.end()) {
603      valueNumbering.insert(std::make_pair(V, EI->second));
604      return EI->second;
605    } else {
606      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
607      valueNumbering.insert(std::make_pair(V, nextValueNumber));
608
609      return nextValueNumber++;
610    }
611  } else {
612    valueNumbering.insert(std::make_pair(V, nextValueNumber));
613    return nextValueNumber++;
614  }
615}
616
617/// lookup - Returns the value number of the specified value. Fails if
618/// the value has not yet been numbered.
619uint32_t ValueTable::lookup(Value* V) const {
620  DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
621  if (VI != valueNumbering.end())
622    return VI->second;
623  else
624    assert(0 && "Value not numbered?");
625
626  return 0;
627}
628
629/// clear - Remove all entries from the ValueTable
630void ValueTable::clear() {
631  valueNumbering.clear();
632  expressionNumbering.clear();
633  nextValueNumber = 1;
634}
635
636/// erase - Remove a value from the value numbering
637void ValueTable::erase(Value* V) {
638  valueNumbering.erase(V);
639}
640
641//===----------------------------------------------------------------------===//
642//                       ValueNumberedSet Class
643//===----------------------------------------------------------------------===//
644namespace {
645class ValueNumberedSet {
646  private:
647    SmallPtrSet<Value*, 8> contents;
648    BitVector numbers;
649  public:
650    ValueNumberedSet() { numbers.resize(1); }
651    ValueNumberedSet(const ValueNumberedSet& other) {
652      numbers = other.numbers;
653      contents = other.contents;
654    }
655
656    typedef SmallPtrSet<Value*, 8>::iterator iterator;
657
658    iterator begin() { return contents.begin(); }
659    iterator end() { return contents.end(); }
660
661    bool insert(Value* v) { return contents.insert(v); }
662    void insert(iterator I, iterator E) { contents.insert(I, E); }
663    void erase(Value* v) { contents.erase(v); }
664    unsigned count(Value* v) { return contents.count(v); }
665    size_t size() { return contents.size(); }
666
667    void set(unsigned i)  {
668      if (i >= numbers.size())
669        numbers.resize(i+1);
670
671      numbers.set(i);
672    }
673
674    void operator=(const ValueNumberedSet& other) {
675      contents = other.contents;
676      numbers = other.numbers;
677    }
678
679    void reset(unsigned i)  {
680      if (i < numbers.size())
681        numbers.reset(i);
682    }
683
684    bool test(unsigned i)  {
685      if (i >= numbers.size())
686        return false;
687
688      return numbers.test(i);
689    }
690
691    void clear() {
692      contents.clear();
693      numbers.clear();
694    }
695};
696}
697
698//===----------------------------------------------------------------------===//
699//                         GVN Pass
700//===----------------------------------------------------------------------===//
701
702namespace {
703
704  class VISIBILITY_HIDDEN GVN : public FunctionPass {
705    bool runOnFunction(Function &F);
706  public:
707    static char ID; // Pass identification, replacement for typeid
708    GVN() : FunctionPass((intptr_t)&ID) { }
709
710  private:
711    ValueTable VN;
712
713    DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
714
715    typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType;
716    PhiMapType phiMap;
717
718
719    // This transformation requires dominator postdominator info
720    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
721      AU.setPreservesCFG();
722      AU.addRequired<DominatorTree>();
723      AU.addRequired<MemoryDependenceAnalysis>();
724      AU.addRequired<AliasAnalysis>();
725      AU.addRequired<TargetData>();
726      AU.addPreserved<AliasAnalysis>();
727      AU.addPreserved<MemoryDependenceAnalysis>();
728      AU.addPreserved<TargetData>();
729    }
730
731    // Helper fuctions
732    // FIXME: eliminate or document these better
733    Value* find_leader(ValueNumberedSet& vals, uint32_t v) ;
734    void val_insert(ValueNumberedSet& s, Value* v);
735    bool processLoad(LoadInst* L,
736                     DenseMap<Value*, LoadInst*>& lastLoad,
737                     SmallVector<Instruction*, 4>& toErase);
738    bool processInstruction(Instruction* I,
739                            ValueNumberedSet& currAvail,
740                            DenseMap<Value*, LoadInst*>& lastSeenLoad,
741                            SmallVector<Instruction*, 4>& toErase);
742    bool processNonLocalLoad(LoadInst* L,
743                             SmallVector<Instruction*, 4>& toErase);
744    bool processMemCpy(MemCpyInst* M, MemCpyInst* MDep,
745                       SmallVector<Instruction*, 4>& toErase);
746    bool performCallSlotOptzn(MemCpyInst* cpy, CallInst* C,
747                              SmallVector<Instruction*, 4>& toErase);
748    Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig,
749                            DenseMap<BasicBlock*, Value*> &Phis,
750                            bool top_level = false);
751    void dump(DenseMap<BasicBlock*, Value*>& d);
752    bool iterateOnFunction(Function &F);
753    Value* CollapsePhi(PHINode* p);
754    bool isSafeReplacement(PHINode* p, Instruction* inst);
755  };
756
757  char GVN::ID = 0;
758
759}
760
761// createGVNPass - The public interface to this file...
762FunctionPass *llvm::createGVNPass() { return new GVN(); }
763
764static RegisterPass<GVN> X("gvn",
765                           "Global Value Numbering");
766
767STATISTIC(NumGVNInstr, "Number of instructions deleted");
768STATISTIC(NumGVNLoad, "Number of loads deleted");
769
770/// find_leader - Given a set and a value number, return the first
771/// element of the set with that value number, or 0 if no such element
772/// is present
773Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) {
774  if (!vals.test(v))
775    return 0;
776
777  for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
778       I != E; ++I)
779    if (v == VN.lookup(*I))
780      return *I;
781
782  assert(0 && "No leader found, but present bit is set?");
783  return 0;
784}
785
786/// val_insert - Insert a value into a set only if there is not a value
787/// with the same value number already in the set
788void GVN::val_insert(ValueNumberedSet& s, Value* v) {
789  uint32_t num = VN.lookup(v);
790  if (!s.test(num))
791    s.insert(v);
792}
793
794void GVN::dump(DenseMap<BasicBlock*, Value*>& d) {
795  printf("{\n");
796  for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(),
797       E = d.end(); I != E; ++I) {
798    if (I->second == MemoryDependenceAnalysis::None)
799      printf("None\n");
800    else
801      I->second->dump();
802  }
803  printf("}\n");
804}
805
806Value* GVN::CollapsePhi(PHINode* p) {
807  DominatorTree &DT = getAnalysis<DominatorTree>();
808  Value* constVal = p->hasConstantValue();
809
810  if (constVal) {
811    if (Instruction* inst = dyn_cast<Instruction>(constVal)) {
812      if (DT.dominates(inst, p))
813        if (isSafeReplacement(p, inst))
814          return inst;
815    } else {
816      return constVal;
817    }
818  }
819
820  return 0;
821}
822
823bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) {
824  if (!isa<PHINode>(inst))
825    return true;
826
827  for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end();
828       UI != E; ++UI)
829    if (PHINode* use_phi = dyn_cast<PHINode>(UI))
830      if (use_phi->getParent() == inst->getParent())
831        return false;
832
833  return true;
834}
835
836/// GetValueForBlock - Get the value to use within the specified basic block.
837/// available values are in Phis.
838Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
839                               DenseMap<BasicBlock*, Value*> &Phis,
840                               bool top_level) {
841
842  // If we have already computed this value, return the previously computed val.
843  DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB);
844  if (V != Phis.end() && !top_level) return V->second;
845
846  BasicBlock* singlePred = BB->getSinglePredecessor();
847  if (singlePred) {
848    Value *ret = GetValueForBlock(singlePred, orig, Phis);
849    Phis[BB] = ret;
850    return ret;
851  }
852  // Otherwise, the idom is the loop, so we need to insert a PHI node.  Do so
853  // now, then get values to fill in the incoming values for the PHI.
854  PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle",
855                            BB->begin());
856  PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB)));
857
858  if (Phis.count(BB) == 0)
859    Phis.insert(std::make_pair(BB, PN));
860
861  // Fill in the incoming values for the block.
862  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
863    Value* val = GetValueForBlock(*PI, orig, Phis);
864
865    PN->addIncoming(val, *PI);
866  }
867  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
868  AA.copyValue(orig, PN);
869
870  // Attempt to collapse PHI nodes that are trivially redundant
871  Value* v = CollapsePhi(PN);
872  if (v) {
873    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
874
875    MD.removeInstruction(PN);
876    PN->replaceAllUsesWith(v);
877
878    for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
879         E = Phis.end(); I != E; ++I)
880      if (I->second == PN)
881        I->second = v;
882
883    PN->eraseFromParent();
884
885    Phis[BB] = v;
886
887    return v;
888  }
889
890  // Cache our phi construction results
891  phiMap[orig->getPointerOperand()].insert(PN);
892  return PN;
893}
894
895/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are
896/// non-local by performing PHI construction.
897bool GVN::processNonLocalLoad(LoadInst* L,
898                              SmallVector<Instruction*, 4>& toErase) {
899  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
900
901  // Find the non-local dependencies of the load
902  DenseMap<BasicBlock*, Value*> deps;
903  MD.getNonLocalDependency(L, deps);
904
905  DenseMap<BasicBlock*, Value*> repl;
906
907  // Filter out useless results (non-locals, etc)
908  for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end();
909       I != E; ++I)
910    if (I->second == MemoryDependenceAnalysis::None) {
911      return false;
912    } else if (I->second == MemoryDependenceAnalysis::NonLocal) {
913      continue;
914    } else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) {
915      if (S->getPointerOperand() == L->getPointerOperand())
916        repl[I->first] = S->getOperand(0);
917      else
918        return false;
919    } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) {
920      if (LD->getPointerOperand() == L->getPointerOperand())
921        repl[I->first] = LD;
922      else
923        return false;
924    } else {
925      return false;
926    }
927
928  // Use cached PHI construction information from previous runs
929  SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()];
930  for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end();
931       I != E; ++I) {
932    if ((*I)->getParent() == L->getParent()) {
933      MD.removeInstruction(L);
934      L->replaceAllUsesWith(*I);
935      toErase.push_back(L);
936      NumGVNLoad++;
937
938      return true;
939    } else {
940      repl.insert(std::make_pair((*I)->getParent(), *I));
941    }
942  }
943
944  // Perform PHI construction
945  SmallPtrSet<BasicBlock*, 4> visited;
946  Value* v = GetValueForBlock(L->getParent(), L, repl, true);
947
948  MD.removeInstruction(L);
949  L->replaceAllUsesWith(v);
950  toErase.push_back(L);
951  NumGVNLoad++;
952
953  return true;
954}
955
956/// processLoad - Attempt to eliminate a load, first by eliminating it
957/// locally, and then attempting non-local elimination if that fails.
958bool GVN::processLoad(LoadInst* L,
959                         DenseMap<Value*, LoadInst*>& lastLoad,
960                         SmallVector<Instruction*, 4>& toErase) {
961  if (L->isVolatile()) {
962    lastLoad[L->getPointerOperand()] = L;
963    return false;
964  }
965
966  Value* pointer = L->getPointerOperand();
967  LoadInst*& last = lastLoad[pointer];
968
969  // ... to a pointer that has been loaded from before...
970  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
971  bool removedNonLocal = false;
972  Instruction* dep = MD.getDependency(L);
973  if (dep == MemoryDependenceAnalysis::NonLocal &&
974      L->getParent() != &L->getParent()->getParent()->getEntryBlock()) {
975    removedNonLocal = processNonLocalLoad(L, toErase);
976
977    if (!removedNonLocal)
978      last = L;
979
980    return removedNonLocal;
981  }
982
983
984  bool deletedLoad = false;
985
986  // Walk up the dependency chain until we either find
987  // a dependency we can use, or we can't walk any further
988  while (dep != MemoryDependenceAnalysis::None &&
989         dep != MemoryDependenceAnalysis::NonLocal &&
990         (isa<LoadInst>(dep) || isa<StoreInst>(dep))) {
991    // ... that depends on a store ...
992    if (StoreInst* S = dyn_cast<StoreInst>(dep)) {
993      if (S->getPointerOperand() == pointer) {
994        // Remove it!
995        MD.removeInstruction(L);
996
997        L->replaceAllUsesWith(S->getOperand(0));
998        toErase.push_back(L);
999        deletedLoad = true;
1000        NumGVNLoad++;
1001      }
1002
1003      // Whether we removed it or not, we can't
1004      // go any further
1005      break;
1006    } else if (!last) {
1007      // If we don't depend on a store, and we haven't
1008      // been loaded before, bail.
1009      break;
1010    } else if (dep == last) {
1011      // Remove it!
1012      MD.removeInstruction(L);
1013
1014      L->replaceAllUsesWith(last);
1015      toErase.push_back(L);
1016      deletedLoad = true;
1017      NumGVNLoad++;
1018
1019      break;
1020    } else {
1021      dep = MD.getDependency(L, dep);
1022    }
1023  }
1024
1025  if (dep != MemoryDependenceAnalysis::None &&
1026      dep != MemoryDependenceAnalysis::NonLocal &&
1027      isa<AllocationInst>(dep)) {
1028    // Check that this load is actually from the
1029    // allocation we found
1030    Value* v = L->getOperand(0);
1031    while (true) {
1032      if (BitCastInst *BC = dyn_cast<BitCastInst>(v))
1033        v = BC->getOperand(0);
1034      else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(v))
1035        v = GEP->getOperand(0);
1036      else
1037        break;
1038    }
1039    if (v == dep) {
1040      // If this load depends directly on an allocation, there isn't
1041      // anything stored there; therefore, we can optimize this load
1042      // to undef.
1043      MD.removeInstruction(L);
1044
1045      L->replaceAllUsesWith(UndefValue::get(L->getType()));
1046      toErase.push_back(L);
1047      deletedLoad = true;
1048      NumGVNLoad++;
1049    }
1050  }
1051
1052  if (!deletedLoad)
1053    last = L;
1054
1055  return deletedLoad;
1056}
1057
1058/// performCallSlotOptzn - takes a memcpy and a call that it depends on,
1059/// and checks for the possibility of a call slot optimization by having
1060/// the call write its result directly into the destination of the memcpy.
1061bool GVN::performCallSlotOptzn(MemCpyInst* cpy, CallInst* C,
1062                               SmallVector<Instruction*, 4>& toErase) {
1063  // The general transformation to keep in mind is
1064  //
1065  //   call @func(..., src, ...)
1066  //   memcpy(dest, src, ...)
1067  //
1068  // ->
1069  //
1070  //   memcpy(dest, src, ...)
1071  //   call @func(..., dest, ...)
1072  //
1073  // Since moving the memcpy is technically awkward, we additionally check that
1074  // src only holds uninitialized values at the moment of the call, meaning that
1075  // the memcpy can be discarded rather than moved.
1076
1077  // Deliberately get the source and destination with bitcasts stripped away,
1078  // because we'll need to do type comparisons based on the underlying type.
1079  Value* cpyDest = cpy->getDest();
1080  Value* cpySrc = cpy->getSource();
1081  CallSite CS = CallSite::get(C);
1082
1083  // We need to be able to reason about the size of the memcpy, so we require
1084  // that it be a constant.
1085  ConstantInt* cpyLength = dyn_cast<ConstantInt>(cpy->getLength());
1086  if (!cpyLength)
1087    return false;
1088
1089  // Require that src be an alloca.  This simplifies the reasoning considerably.
1090  AllocaInst* srcAlloca = dyn_cast<AllocaInst>(cpySrc);
1091  if (!srcAlloca)
1092    return false;
1093
1094  // Check that all of src is copied to dest.
1095  TargetData& TD = getAnalysis<TargetData>();
1096
1097  ConstantInt* srcArraySize = dyn_cast<ConstantInt>(srcAlloca->getArraySize());
1098  if (!srcArraySize)
1099    return false;
1100
1101  uint64_t srcSize = TD.getABITypeSize(srcAlloca->getAllocatedType()) *
1102    srcArraySize->getZExtValue();
1103
1104  if (cpyLength->getZExtValue() < srcSize)
1105    return false;
1106
1107  // Check that accessing the first srcSize bytes of dest will not cause a
1108  // trap.  Otherwise the transform is invalid since it might cause a trap
1109  // to occur earlier than it otherwise would.
1110  if (AllocaInst* A = dyn_cast<AllocaInst>(cpyDest)) {
1111    // The destination is an alloca.  Check it is larger than srcSize.
1112    ConstantInt* destArraySize = dyn_cast<ConstantInt>(A->getArraySize());
1113    if (!destArraySize)
1114      return false;
1115
1116    uint64_t destSize = TD.getABITypeSize(A->getAllocatedType()) *
1117      destArraySize->getZExtValue();
1118
1119    if (destSize < srcSize)
1120      return false;
1121  } else if (Argument* A = dyn_cast<Argument>(cpyDest)) {
1122    // If the destination is an sret parameter then only accesses that are
1123    // outside of the returned struct type can trap.
1124    if (!A->hasStructRetAttr())
1125      return false;
1126
1127    const Type* StructTy = cast<PointerType>(A->getType())->getElementType();
1128    uint64_t destSize = TD.getABITypeSize(StructTy);
1129
1130    if (destSize < srcSize)
1131      return false;
1132  } else {
1133    return false;
1134  }
1135
1136  // Check that src is not accessed except via the call and the memcpy.  This
1137  // guarantees that it holds only undefined values when passed in (so the final
1138  // memcpy can be dropped), that it is not read or written between the call and
1139  // the memcpy, and that writing beyond the end of it is undefined.
1140
1141  SmallVector<User*, 8> srcUseList(srcAlloca->use_begin(),
1142                                   srcAlloca->use_end());
1143  while (!srcUseList.empty()) {
1144    User* UI = srcUseList.back();
1145    srcUseList.pop_back();
1146
1147    if (isa<GetElementPtrInst>(UI) || isa<BitCastInst>(UI)) {
1148      for (User::use_iterator I = UI->use_begin(), E = UI->use_end();
1149           I != E; ++I)
1150        srcUseList.push_back(*I);
1151    } else if (UI != C && UI != cpy) {
1152      return false;
1153    }
1154  }
1155
1156  // Since we're changing the parameter to the callsite, we need to make sure
1157  // that what would be the new parameter dominates the callsite.
1158  DominatorTree& DT = getAnalysis<DominatorTree>();
1159  if (Instruction* cpyDestInst = dyn_cast<Instruction>(cpyDest))
1160    if (!DT.dominates(cpyDestInst, C))
1161      return false;
1162
1163  // In addition to knowing that the call does not access src in some
1164  // unexpected manner, for example via a global, which we deduce from
1165  // the use analysis, we also need to know that it does not sneakily
1166  // access dest.  We rely on AA to figure this out for us.
1167  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
1168  if (AA.getModRefInfo(C, cpy->getRawDest(), srcSize) !=
1169      AliasAnalysis::NoModRef)
1170    return false;
1171
1172  // All the checks have passed, so do the transformation.
1173  for (unsigned i = 0; i < CS.arg_size(); ++i)
1174    if (CS.getArgument(i) == cpySrc)
1175      CS.setArgument(i, cpyDest);
1176
1177  // Drop any cached information about the call, because we may have changed
1178  // its dependence information by changing its parameter.
1179  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1180  MD.dropInstruction(C);
1181
1182  // Remove the memcpy
1183  MD.removeInstruction(cpy);
1184  toErase.push_back(cpy);
1185
1186  return true;
1187}
1188
1189/// processMemCpy - perform simplication of memcpy's.  If we have memcpy A which
1190/// copies X to Y, and memcpy B which copies Y to Z, then we can rewrite B to be
1191/// a memcpy from X to Z (or potentially a memmove, depending on circumstances).
1192///  This allows later passes to remove the first memcpy altogether.
1193bool GVN::processMemCpy(MemCpyInst* M, MemCpyInst* MDep,
1194                        SmallVector<Instruction*, 4>& toErase) {
1195  // We can only transforms memcpy's where the dest of one is the source of the
1196  // other
1197  if (M->getSource() != MDep->getDest())
1198    return false;
1199
1200  // Second, the length of the memcpy's must be the same, or the preceeding one
1201  // must be larger than the following one.
1202  ConstantInt* C1 = dyn_cast<ConstantInt>(MDep->getLength());
1203  ConstantInt* C2 = dyn_cast<ConstantInt>(M->getLength());
1204  if (!C1 || !C2)
1205    return false;
1206
1207  uint64_t DepSize = C1->getValue().getZExtValue();
1208  uint64_t CpySize = C2->getValue().getZExtValue();
1209
1210  if (DepSize < CpySize)
1211    return false;
1212
1213  // Finally, we have to make sure that the dest of the second does not
1214  // alias the source of the first
1215  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
1216  if (AA.alias(M->getRawDest(), CpySize, MDep->getRawSource(), DepSize) !=
1217      AliasAnalysis::NoAlias)
1218    return false;
1219  else if (AA.alias(M->getRawDest(), CpySize, M->getRawSource(), CpySize) !=
1220           AliasAnalysis::NoAlias)
1221    return false;
1222  else if (AA.alias(MDep->getRawDest(), DepSize, MDep->getRawSource(), DepSize)
1223           != AliasAnalysis::NoAlias)
1224    return false;
1225
1226  // If all checks passed, then we can transform these memcpy's
1227  Function* MemCpyFun = Intrinsic::getDeclaration(
1228                                 M->getParent()->getParent()->getParent(),
1229                                 M->getIntrinsicID());
1230
1231  std::vector<Value*> args;
1232  args.push_back(M->getRawDest());
1233  args.push_back(MDep->getRawSource());
1234  args.push_back(M->getLength());
1235  args.push_back(M->getAlignment());
1236
1237  CallInst* C = new CallInst(MemCpyFun, args.begin(), args.end(), "", M);
1238
1239  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1240  if (MD.getDependency(C) == MDep) {
1241    MD.dropInstruction(M);
1242    toErase.push_back(M);
1243    return true;
1244  } else {
1245    MD.removeInstruction(C);
1246    toErase.push_back(C);
1247    return false;
1248  }
1249}
1250
1251/// processInstruction - When calculating availability, handle an instruction
1252/// by inserting it into the appropriate sets
1253bool GVN::processInstruction(Instruction* I,
1254                                ValueNumberedSet& currAvail,
1255                                DenseMap<Value*, LoadInst*>& lastSeenLoad,
1256                                SmallVector<Instruction*, 4>& toErase) {
1257  if (LoadInst* L = dyn_cast<LoadInst>(I)) {
1258    return processLoad(L, lastSeenLoad, toErase);
1259  } else if (MemCpyInst* M = dyn_cast<MemCpyInst>(I)) {
1260    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1261
1262    // The are two possible optimizations we can do for memcpy:
1263    //   a) memcpy-memcpy xform which exposes redundance for DSE
1264    //   b) call-memcpy xform for return slot optimization
1265    Instruction* dep = MD.getDependency(M);
1266    if (dep == MemoryDependenceAnalysis::None ||
1267        dep == MemoryDependenceAnalysis::NonLocal)
1268      return false;
1269    if (MemCpyInst *MemCpy = dyn_cast<MemCpyInst>(dep))
1270      return processMemCpy(M, MemCpy, toErase);
1271    if (CallInst* C = dyn_cast<CallInst>(dep))
1272      return performCallSlotOptzn(M, C, toErase);
1273    return false;
1274  }
1275
1276  unsigned num = VN.lookup_or_add(I);
1277
1278  // Collapse PHI nodes
1279  if (PHINode* p = dyn_cast<PHINode>(I)) {
1280    Value* constVal = CollapsePhi(p);
1281
1282    if (constVal) {
1283      for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end();
1284           PI != PE; ++PI)
1285        if (PI->second.count(p))
1286          PI->second.erase(p);
1287
1288      p->replaceAllUsesWith(constVal);
1289      toErase.push_back(p);
1290    }
1291  // Perform value-number based elimination
1292  } else if (currAvail.test(num)) {
1293    Value* repl = find_leader(currAvail, num);
1294
1295    if (CallInst* CI = dyn_cast<CallInst>(I)) {
1296      AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
1297      if (!AA.doesNotAccessMemory(CI)) {
1298        MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1299        if (cast<Instruction>(repl)->getParent() != CI->getParent() ||
1300            MD.getDependency(CI) != MD.getDependency(cast<CallInst>(repl))) {
1301          // There must be an intervening may-alias store, so nothing from
1302          // this point on will be able to be replaced with the preceding call
1303          currAvail.erase(repl);
1304          currAvail.insert(I);
1305
1306          return false;
1307        }
1308      }
1309    }
1310
1311    // Remove it!
1312    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1313    MD.removeInstruction(I);
1314
1315    VN.erase(I);
1316    I->replaceAllUsesWith(repl);
1317    toErase.push_back(I);
1318    return true;
1319  } else if (!I->isTerminator()) {
1320    currAvail.set(num);
1321    currAvail.insert(I);
1322  }
1323
1324  return false;
1325}
1326
1327// GVN::runOnFunction - This is the main transformation entry point for a
1328// function.
1329//
1330bool GVN::runOnFunction(Function& F) {
1331  VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>());
1332
1333  bool changed = false;
1334  bool shouldContinue = true;
1335
1336  while (shouldContinue) {
1337    shouldContinue = iterateOnFunction(F);
1338    changed |= shouldContinue;
1339  }
1340
1341  return changed;
1342}
1343
1344
1345// GVN::iterateOnFunction - Executes one iteration of GVN
1346bool GVN::iterateOnFunction(Function &F) {
1347  // Clean out global sets from any previous functions
1348  VN.clear();
1349  availableOut.clear();
1350  phiMap.clear();
1351
1352  bool changed_function = false;
1353
1354  DominatorTree &DT = getAnalysis<DominatorTree>();
1355
1356  SmallVector<Instruction*, 4> toErase;
1357
1358  // Top-down walk of the dominator tree
1359  for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1360         E = df_end(DT.getRootNode()); DI != E; ++DI) {
1361
1362    // Get the set to update for this block
1363    ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
1364    DenseMap<Value*, LoadInst*> lastSeenLoad;
1365
1366    BasicBlock* BB = DI->getBlock();
1367
1368    // A block inherits AVAIL_OUT from its dominator
1369    if (DI->getIDom() != 0)
1370      currAvail = availableOut[DI->getIDom()->getBlock()];
1371
1372    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1373         BI != BE; ) {
1374      changed_function |= processInstruction(BI, currAvail,
1375                                             lastSeenLoad, toErase);
1376
1377      NumGVNInstr += toErase.size();
1378
1379      // Avoid iterator invalidation
1380      ++BI;
1381
1382      for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(),
1383           E = toErase.end(); I != E; ++I) {
1384        (*I)->eraseFromParent();
1385      }
1386
1387      toErase.clear();
1388    }
1389  }
1390
1391  return changed_function;
1392}
1393