GVN.cpp revision 77db50f68f9fa5cade9f3a368af4722a76e0c8c5 
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 performReturnSlotOptzn(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    bool valueHasOnlyOneUseAfter(Value* val, MemCpyInst* use,
756                                 Instruction* cutoff);
757  };
758
759  char GVN::ID = 0;
760
761}
762
763// createGVNPass - The public interface to this file...
764FunctionPass *llvm::createGVNPass() { return new GVN(); }
765
766static RegisterPass<GVN> X("gvn",
767                           "Global Value Numbering");
768
769STATISTIC(NumGVNInstr, "Number of instructions deleted");
770STATISTIC(NumGVNLoad, "Number of loads deleted");
771
772/// find_leader - Given a set and a value number, return the first
773/// element of the set with that value number, or 0 if no such element
774/// is present
775Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) {
776  if (!vals.test(v))
777    return 0;
778
779  for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
780       I != E; ++I)
781    if (v == VN.lookup(*I))
782      return *I;
783
784  assert(0 && "No leader found, but present bit is set?");
785  return 0;
786}
787
788/// val_insert - Insert a value into a set only if there is not a value
789/// with the same value number already in the set
790void GVN::val_insert(ValueNumberedSet& s, Value* v) {
791  uint32_t num = VN.lookup(v);
792  if (!s.test(num))
793    s.insert(v);
794}
795
796void GVN::dump(DenseMap<BasicBlock*, Value*>& d) {
797  printf("{\n");
798  for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(),
799       E = d.end(); I != E; ++I) {
800    if (I->second == MemoryDependenceAnalysis::None)
801      printf("None\n");
802    else
803      I->second->dump();
804  }
805  printf("}\n");
806}
807
808Value* GVN::CollapsePhi(PHINode* p) {
809  DominatorTree &DT = getAnalysis<DominatorTree>();
810  Value* constVal = p->hasConstantValue();
811
812  if (constVal) {
813    if (Instruction* inst = dyn_cast<Instruction>(constVal)) {
814      if (DT.dominates(inst, p))
815        if (isSafeReplacement(p, inst))
816          return inst;
817    } else {
818      return constVal;
819    }
820  }
821
822  return 0;
823}
824
825bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) {
826  if (!isa<PHINode>(inst))
827    return true;
828
829  for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end();
830       UI != E; ++UI)
831    if (PHINode* use_phi = dyn_cast<PHINode>(UI))
832      if (use_phi->getParent() == inst->getParent())
833        return false;
834
835  return true;
836}
837
838/// GetValueForBlock - Get the value to use within the specified basic block.
839/// available values are in Phis.
840Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
841                               DenseMap<BasicBlock*, Value*> &Phis,
842                               bool top_level) {
843
844  // If we have already computed this value, return the previously computed val.
845  DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB);
846  if (V != Phis.end() && !top_level) return V->second;
847
848  BasicBlock* singlePred = BB->getSinglePredecessor();
849  if (singlePred) {
850    Value *ret = GetValueForBlock(singlePred, orig, Phis);
851    Phis[BB] = ret;
852    return ret;
853  }
854  // Otherwise, the idom is the loop, so we need to insert a PHI node.  Do so
855  // now, then get values to fill in the incoming values for the PHI.
856  PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle",
857                            BB->begin());
858  PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB)));
859
860  if (Phis.count(BB) == 0)
861    Phis.insert(std::make_pair(BB, PN));
862
863  // Fill in the incoming values for the block.
864  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
865    Value* val = GetValueForBlock(*PI, orig, Phis);
866
867    PN->addIncoming(val, *PI);
868  }
869  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
870  AA.copyValue(orig, PN);
871
872  // Attempt to collapse PHI nodes that are trivially redundant
873  Value* v = CollapsePhi(PN);
874  if (v) {
875    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
876
877    MD.removeInstruction(PN);
878    PN->replaceAllUsesWith(v);
879
880    for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
881         E = Phis.end(); I != E; ++I)
882      if (I->second == PN)
883        I->second = v;
884
885    PN->eraseFromParent();
886
887    Phis[BB] = v;
888
889    return v;
890  }
891
892  // Cache our phi construction results
893  phiMap[orig->getPointerOperand()].insert(PN);
894  return PN;
895}
896
897/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are
898/// non-local by performing PHI construction.
899bool GVN::processNonLocalLoad(LoadInst* L,
900                              SmallVector<Instruction*, 4>& toErase) {
901  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
902
903  // Find the non-local dependencies of the load
904  DenseMap<BasicBlock*, Value*> deps;
905  MD.getNonLocalDependency(L, deps);
906
907  DenseMap<BasicBlock*, Value*> repl;
908
909  // Filter out useless results (non-locals, etc)
910  for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end();
911       I != E; ++I)
912    if (I->second == MemoryDependenceAnalysis::None) {
913      return false;
914    } else if (I->second == MemoryDependenceAnalysis::NonLocal) {
915      continue;
916    } else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) {
917      if (S->getPointerOperand() == L->getPointerOperand())
918        repl[I->first] = S->getOperand(0);
919      else
920        return false;
921    } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) {
922      if (LD->getPointerOperand() == L->getPointerOperand())
923        repl[I->first] = LD;
924      else
925        return false;
926    } else {
927      return false;
928    }
929
930  // Use cached PHI construction information from previous runs
931  SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()];
932  for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end();
933       I != E; ++I) {
934    if ((*I)->getParent() == L->getParent()) {
935      MD.removeInstruction(L);
936      L->replaceAllUsesWith(*I);
937      toErase.push_back(L);
938      NumGVNLoad++;
939
940      return true;
941    } else {
942      repl.insert(std::make_pair((*I)->getParent(), *I));
943    }
944  }
945
946  // Perform PHI construction
947  SmallPtrSet<BasicBlock*, 4> visited;
948  Value* v = GetValueForBlock(L->getParent(), L, repl, true);
949
950  MD.removeInstruction(L);
951  L->replaceAllUsesWith(v);
952  toErase.push_back(L);
953  NumGVNLoad++;
954
955  return true;
956}
957
958/// processLoad - Attempt to eliminate a load, first by eliminating it
959/// locally, and then attempting non-local elimination if that fails.
960bool GVN::processLoad(LoadInst* L,
961                         DenseMap<Value*, LoadInst*>& lastLoad,
962                         SmallVector<Instruction*, 4>& toErase) {
963  if (L->isVolatile()) {
964    lastLoad[L->getPointerOperand()] = L;
965    return false;
966  }
967
968  Value* pointer = L->getPointerOperand();
969  LoadInst*& last = lastLoad[pointer];
970
971  // ... to a pointer that has been loaded from before...
972  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
973  bool removedNonLocal = false;
974  Instruction* dep = MD.getDependency(L);
975  if (dep == MemoryDependenceAnalysis::NonLocal &&
976      L->getParent() != &L->getParent()->getParent()->getEntryBlock()) {
977    removedNonLocal = processNonLocalLoad(L, toErase);
978
979    if (!removedNonLocal)
980      last = L;
981
982    return removedNonLocal;
983  }
984
985
986  bool deletedLoad = false;
987
988  // Walk up the dependency chain until we either find
989  // a dependency we can use, or we can't walk any further
990  while (dep != MemoryDependenceAnalysis::None &&
991         dep != MemoryDependenceAnalysis::NonLocal &&
992         (isa<LoadInst>(dep) || isa<StoreInst>(dep))) {
993    // ... that depends on a store ...
994    if (StoreInst* S = dyn_cast<StoreInst>(dep)) {
995      if (S->getPointerOperand() == pointer) {
996        // Remove it!
997        MD.removeInstruction(L);
998
999        L->replaceAllUsesWith(S->getOperand(0));
1000        toErase.push_back(L);
1001        deletedLoad = true;
1002        NumGVNLoad++;
1003      }
1004
1005      // Whether we removed it or not, we can't
1006      // go any further
1007      break;
1008    } else if (!last) {
1009      // If we don't depend on a store, and we haven't
1010      // been loaded before, bail.
1011      break;
1012    } else if (dep == last) {
1013      // Remove it!
1014      MD.removeInstruction(L);
1015
1016      L->replaceAllUsesWith(last);
1017      toErase.push_back(L);
1018      deletedLoad = true;
1019      NumGVNLoad++;
1020
1021      break;
1022    } else {
1023      dep = MD.getDependency(L, dep);
1024    }
1025  }
1026
1027  if (dep != MemoryDependenceAnalysis::None &&
1028      dep != MemoryDependenceAnalysis::NonLocal &&
1029      isa<AllocationInst>(dep)) {
1030    // Check that this load is actually from the
1031    // allocation we found
1032    Value* v = L->getOperand(0);
1033    while (true) {
1034      if (BitCastInst *BC = dyn_cast<BitCastInst>(v))
1035        v = BC->getOperand(0);
1036      else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(v))
1037        v = GEP->getOperand(0);
1038      else
1039        break;
1040    }
1041    if (v == dep) {
1042      // If this load depends directly on an allocation, there isn't
1043      // anything stored there; therefore, we can optimize this load
1044      // to undef.
1045      MD.removeInstruction(L);
1046
1047      L->replaceAllUsesWith(UndefValue::get(L->getType()));
1048      toErase.push_back(L);
1049      deletedLoad = true;
1050      NumGVNLoad++;
1051    }
1052  }
1053
1054  if (!deletedLoad)
1055    last = L;
1056
1057  return deletedLoad;
1058}
1059
1060/// valueHasOnlyOneUse - Returns true if a value has only one use after the
1061/// cutoff that is in the current same block and is the same as the use
1062/// parameter.
1063bool GVN::valueHasOnlyOneUseAfter(Value* val, MemCpyInst* use,
1064                                  Instruction* cutoff) {
1065  DominatorTree& DT = getAnalysis<DominatorTree>();
1066
1067  SmallVector<User*, 8> useList(val->use_begin(), val->use_end());
1068  while (!useList.empty()) {
1069    User* UI = useList.back();
1070
1071
1072    if (isa<GetElementPtrInst>(UI) || isa<BitCastInst>(UI)) {
1073      useList.pop_back();
1074      for (User::use_iterator I = UI->use_begin(), E = UI->use_end();
1075           I != E; ++I)
1076        useList.push_back(*I);
1077    } else if (UI == use) {
1078      useList.pop_back();
1079    } else if (Instruction* inst = dyn_cast<Instruction>(UI)) {
1080      if (inst->getParent() == use->getParent() &&
1081          (inst == cutoff || !DT.dominates(cutoff, inst))) {
1082        useList.pop_back();
1083      } else
1084        return false;
1085    } else
1086      return false;
1087  }
1088
1089  return true;
1090}
1091
1092/// performReturnSlotOptzn - takes a memcpy and a call that it depends on,
1093/// and checks for the possibility of a return slot optimization by having
1094/// the call write its result directly into the callees return parameter
1095/// rather than using memcpy
1096bool GVN::performReturnSlotOptzn(MemCpyInst* cpy, CallInst* C,
1097                                 SmallVector<Instruction*, 4>& toErase) {
1098  // Deliberately get the source and destination with bitcasts stripped away,
1099  // because we'll need to do type comparisons based on the underlying type.
1100  Value* cpyDest = cpy->getDest();
1101  Value* cpySrc = cpy->getSource();
1102  CallSite CS = CallSite::get(C);
1103
1104  // Since this is a return slot optimization, we need to make sure that
1105  // the value being copied is, in fact, in a return slot.  We also need to
1106  // check that the return slot parameter is marked noalias, so that we can
1107  // be sure that changing it will not cause unexpected behavior changes due
1108  // to it being accessed through a global or another parameter.
1109  if (CS.arg_size() == 0 ||
1110      cpySrc != CS.getArgument(0) ||
1111      !CS.paramHasAttr(1, ParamAttr::NoAlias | ParamAttr::StructRet))
1112    return false;
1113
1114  // Since we're changing the parameter to the callsite, we need to make sure
1115  // that what would be the new parameter dominates the callsite.
1116  DominatorTree& DT = getAnalysis<DominatorTree>();
1117  if (Instruction* cpyDestInst = dyn_cast<Instruction>(cpyDest))
1118    if (!DT.dominates(cpyDestInst, C))
1119      return false;
1120
1121  // Check that something sneaky is not happening involving casting
1122  // return slot types around.
1123  if (CS.getArgument(0)->getType() != cpyDest->getType())
1124    return false;
1125  // sret --> pointer
1126  const PointerType* PT = cast<PointerType>(cpyDest->getType());
1127
1128  // We can only perform the transformation if the size of the memcpy
1129  // is constant and equal to the size of the structure.
1130  ConstantInt* cpyLength = dyn_cast<ConstantInt>(cpy->getLength());
1131  if (!cpyLength)
1132    return false;
1133
1134  TargetData& TD = getAnalysis<TargetData>();
1135  if (TD.getTypeStoreSize(PT->getElementType()) != cpyLength->getZExtValue())
1136    return false;
1137
1138  // For safety, we must ensure that the output parameter of the call only has
1139  // a single use, the memcpy.  Otherwise this can introduce an invalid
1140  // transformation.
1141  if (!valueHasOnlyOneUseAfter(CS.getArgument(0), cpy, C))
1142    return false;
1143
1144  // We only perform the transformation if it will be profitable.
1145  if (!valueHasOnlyOneUseAfter(cpyDest, cpy, C))
1146    return false;
1147
1148  // In addition to knowing that the call does not access the return slot
1149  // in some unexpected manner, which we derive from the noalias attribute,
1150  // we also need to know that it does not sneakily modify the destination
1151  // slot in the caller.  We don't have parameter attributes to go by
1152  // for this one, so we just rely on AA to figure it out for us.
1153  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
1154  if (AA.getModRefInfo(C, cpy->getRawDest(), cpyLength->getZExtValue()) !=
1155      AliasAnalysis::NoModRef)
1156    return false;
1157
1158  // If all the checks have passed, then we're alright to do the transformation.
1159  CS.setArgument(0, cpyDest);
1160
1161  // Drop any cached information about the call, because we may have changed
1162  // its dependence information by changing its parameter.
1163  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1164  MD.dropInstruction(C);
1165
1166  // Remove the memcpy
1167  MD.removeInstruction(cpy);
1168  toErase.push_back(cpy);
1169
1170  return true;
1171}
1172
1173/// processMemCpy - perform simplication of memcpy's.  If we have memcpy A which
1174/// copies X to Y, and memcpy B which copies Y to Z, then we can rewrite B to be
1175/// a memcpy from X to Z (or potentially a memmove, depending on circumstances).
1176///  This allows later passes to remove the first memcpy altogether.
1177bool GVN::processMemCpy(MemCpyInst* M, MemCpyInst* MDep,
1178                        SmallVector<Instruction*, 4>& toErase) {
1179  // We can only transforms memcpy's where the dest of one is the source of the
1180  // other
1181  if (M->getSource() != MDep->getDest())
1182    return false;
1183
1184  // Second, the length of the memcpy's must be the same, or the preceeding one
1185  // must be larger than the following one.
1186  ConstantInt* C1 = dyn_cast<ConstantInt>(MDep->getLength());
1187  ConstantInt* C2 = dyn_cast<ConstantInt>(M->getLength());
1188  if (!C1 || !C2)
1189    return false;
1190
1191  uint64_t DepSize = C1->getValue().getZExtValue();
1192  uint64_t CpySize = C2->getValue().getZExtValue();
1193
1194  if (DepSize < CpySize)
1195    return false;
1196
1197  // Finally, we have to make sure that the dest of the second does not
1198  // alias the source of the first
1199  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
1200  if (AA.alias(M->getRawDest(), CpySize, MDep->getRawSource(), DepSize) !=
1201      AliasAnalysis::NoAlias)
1202    return false;
1203  else if (AA.alias(M->getRawDest(), CpySize, M->getRawSource(), CpySize) !=
1204           AliasAnalysis::NoAlias)
1205    return false;
1206  else if (AA.alias(MDep->getRawDest(), DepSize, MDep->getRawSource(), DepSize)
1207           != AliasAnalysis::NoAlias)
1208    return false;
1209
1210  // If all checks passed, then we can transform these memcpy's
1211  Function* MemCpyFun = Intrinsic::getDeclaration(
1212                                 M->getParent()->getParent()->getParent(),
1213                                 M->getIntrinsicID());
1214
1215  std::vector<Value*> args;
1216  args.push_back(M->getRawDest());
1217  args.push_back(MDep->getRawSource());
1218  args.push_back(M->getLength());
1219  args.push_back(M->getAlignment());
1220
1221  CallInst* C = new CallInst(MemCpyFun, args.begin(), args.end(), "", M);
1222
1223  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1224  if (MD.getDependency(C) == MDep) {
1225    MD.dropInstruction(M);
1226    toErase.push_back(M);
1227    return true;
1228  } else {
1229    MD.removeInstruction(C);
1230    toErase.push_back(C);
1231    return false;
1232  }
1233}
1234
1235/// processInstruction - When calculating availability, handle an instruction
1236/// by inserting it into the appropriate sets
1237bool GVN::processInstruction(Instruction* I,
1238                                ValueNumberedSet& currAvail,
1239                                DenseMap<Value*, LoadInst*>& lastSeenLoad,
1240                                SmallVector<Instruction*, 4>& toErase) {
1241  if (LoadInst* L = dyn_cast<LoadInst>(I)) {
1242    return processLoad(L, lastSeenLoad, toErase);
1243  } else if (MemCpyInst* M = dyn_cast<MemCpyInst>(I)) {
1244    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1245
1246    // The are two possible optimizations we can do for memcpy:
1247    //   a) memcpy-memcpy xform which exposes redundance for DSE
1248    //   b) call-memcpy xform for sret return slot optimization
1249    Instruction* dep = MD.getDependency(M);
1250    if (dep == MemoryDependenceAnalysis::None ||
1251        dep == MemoryDependenceAnalysis::NonLocal)
1252      return false;
1253    if (MemCpyInst *MemCpy = dyn_cast<MemCpyInst>(dep))
1254      return processMemCpy(M, MemCpy, toErase);
1255    if (CallInst* C = dyn_cast<CallInst>(dep))
1256      return performReturnSlotOptzn(M, C, toErase);
1257    return false;
1258  }
1259
1260  unsigned num = VN.lookup_or_add(I);
1261
1262  // Collapse PHI nodes
1263  if (PHINode* p = dyn_cast<PHINode>(I)) {
1264    Value* constVal = CollapsePhi(p);
1265
1266    if (constVal) {
1267      for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end();
1268           PI != PE; ++PI)
1269        if (PI->second.count(p))
1270          PI->second.erase(p);
1271
1272      p->replaceAllUsesWith(constVal);
1273      toErase.push_back(p);
1274    }
1275  // Perform value-number based elimination
1276  } else if (currAvail.test(num)) {
1277    Value* repl = find_leader(currAvail, num);
1278
1279    if (CallInst* CI = dyn_cast<CallInst>(I)) {
1280      AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
1281      if (!AA.doesNotAccessMemory(CI)) {
1282        MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1283        if (cast<Instruction>(repl)->getParent() != CI->getParent() ||
1284            MD.getDependency(CI) != MD.getDependency(cast<CallInst>(repl))) {
1285          // There must be an intervening may-alias store, so nothing from
1286          // this point on will be able to be replaced with the preceding call
1287          currAvail.erase(repl);
1288          currAvail.insert(I);
1289
1290          return false;
1291        }
1292      }
1293    }
1294
1295    // Remove it!
1296    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1297    MD.removeInstruction(I);
1298
1299    VN.erase(I);
1300    I->replaceAllUsesWith(repl);
1301    toErase.push_back(I);
1302    return true;
1303  } else if (!I->isTerminator()) {
1304    currAvail.set(num);
1305    currAvail.insert(I);
1306  }
1307
1308  return false;
1309}
1310
1311// GVN::runOnFunction - This is the main transformation entry point for a
1312// function.
1313//
1314bool GVN::runOnFunction(Function& F) {
1315  VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>());
1316
1317  bool changed = false;
1318  bool shouldContinue = true;
1319
1320  while (shouldContinue) {
1321    shouldContinue = iterateOnFunction(F);
1322    changed |= shouldContinue;
1323  }
1324
1325  return changed;
1326}
1327
1328
1329// GVN::iterateOnFunction - Executes one iteration of GVN
1330bool GVN::iterateOnFunction(Function &F) {
1331  // Clean out global sets from any previous functions
1332  VN.clear();
1333  availableOut.clear();
1334  phiMap.clear();
1335
1336  bool changed_function = false;
1337
1338  DominatorTree &DT = getAnalysis<DominatorTree>();
1339
1340  SmallVector<Instruction*, 4> toErase;
1341
1342  // Top-down walk of the dominator tree
1343  for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1344         E = df_end(DT.getRootNode()); DI != E; ++DI) {
1345
1346    // Get the set to update for this block
1347    ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
1348    DenseMap<Value*, LoadInst*> lastSeenLoad;
1349
1350    BasicBlock* BB = DI->getBlock();
1351
1352    // A block inherits AVAIL_OUT from its dominator
1353    if (DI->getIDom() != 0)
1354      currAvail = availableOut[DI->getIDom()->getBlock()];
1355
1356    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1357         BI != BE; ) {
1358      changed_function |= processInstruction(BI, currAvail,
1359                                             lastSeenLoad, toErase);
1360
1361      NumGVNInstr += toErase.size();
1362
1363      // Avoid iterator invalidation
1364      ++BI;
1365
1366      for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(),
1367           E = toErase.end(); I != E; ++I) {
1368        (*I)->eraseFromParent();
1369      }
1370
1371      toErase.clear();
1372    }
1373  }
1374
1375  return changed_function;
1376}
1377