GVN.cpp revision 9cffa9a6ed754a480dc73db0e8a5b0d846ba2dde 
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  };
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/// isReturnSlotOptznProfitable - Determine if performing a return slot
1059/// fusion with the slot dest is profitable
1060static bool isReturnSlotOptznProfitable(Value* dest, MemCpyInst* cpy) {
1061  // We currently consider it profitable if dest is otherwise dead.
1062  SmallVector<User*, 8> useList(dest->use_begin(), dest->use_end());
1063  while (!useList.empty()) {
1064    User* UI = useList.back();
1065
1066    if (isa<GetElementPtrInst>(UI) || isa<BitCastInst>(UI)) {
1067      useList.pop_back();
1068      for (User::use_iterator I = UI->use_begin(), E = UI->use_end();
1069           I != E; ++I)
1070        useList.push_back(*I);
1071    } else if (UI == cpy)
1072      useList.pop_back();
1073    else
1074      return false;
1075  }
1076
1077  return true;
1078}
1079
1080/// performReturnSlotOptzn - takes a memcpy and a call that it depends on,
1081/// and checks for the possibility of a return slot optimization by having
1082/// the call write its result directly into the callees return parameter
1083/// rather than using memcpy
1084bool GVN::performReturnSlotOptzn(MemCpyInst* cpy, CallInst* C,
1085                                 SmallVector<Instruction*, 4>& toErase) {
1086  Value* cpyDest = cpy->getDest();
1087  Value* cpySrc = cpy->getSource();
1088  CallSite CS = CallSite::get(C);
1089
1090  // Since this is a return slot optimization, we need to make sure that
1091  // the value being copied is, in fact, in a return slot.  We also need to
1092  // check that the return slot parameter is marked noalias, so that we can
1093  // be sure that changing it will not cause unexpected behavior changes due
1094  // to it being accessed through a global or another parameter.
1095  if (CS.arg_size() == 0 ||
1096      cpySrc != CS.getArgument(0) ||
1097      !CS.paramHasAttr(1, ParamAttr::NoAlias | ParamAttr::StructRet))
1098    return false;
1099
1100  // We only perform the transformation if it will be profitable.
1101  if (!isReturnSlotOptznProfitable(cpyDest, cpy))
1102    return false;
1103
1104  // Check that something sneaky is not happening involving casting
1105  // return slot types around.
1106  if (CS.getArgument(0)->getType() != cpyDest->getType())
1107    return false;
1108
1109  // We can only perform the transformation if the size of the memcpy
1110  // is constant and equal to the size of the structure.
1111  if (!isa<ConstantInt>(cpy->getLength()))
1112    return false;
1113
1114  ConstantInt* cpyLength = cast<ConstantInt>(cpy->getLength());
1115  TargetData& TD = getAnalysis<TargetData>();
1116  if (TD.getTypeStoreSize(cpyDest->getType()) == cpyLength->getZExtValue())
1117    return false;
1118
1119  // In addition to knowing that the call does not access the return slot
1120  // in some unexpected manner, which we derive from the noalias attribute,
1121  // we also need to know that it does not sneakily modify the destination
1122  // slot in the caller.  We don't have parameter attributes to go by
1123  // for this one, so we just rely on AA to figure it out for us.
1124  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
1125  if (AA.getModRefInfo(C, cpy->getRawDest(), cpyLength->getZExtValue()) !=
1126      AliasAnalysis::NoModRef)
1127    return false;
1128
1129  // If all the checks have passed, then we're alright to do the transformation.
1130  CS.setArgument(0, cpyDest);
1131
1132  // Drop any cached information about the call, because we may have changed
1133  // its dependence information by changing its parameter.
1134  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1135  MD.dropInstruction(C);
1136
1137  // Remove the memcpy
1138  toErase.push_back(cpy);
1139
1140  return true;
1141}
1142
1143/// processMemCpy - perform simplication of memcpy's.  If we have memcpy A which
1144/// copies X to Y, and memcpy B which copies Y to Z, then we can rewrite B to be
1145/// a memcpy from X to Z (or potentially a memmove, depending on circumstances).
1146///  This allows later passes to remove the first memcpy altogether.
1147bool GVN::processMemCpy(MemCpyInst* M, MemCpyInst* MDep,
1148                        SmallVector<Instruction*, 4>& toErase) {
1149  // We can only transforms memcpy's where the dest of one is the source of the
1150  // other
1151  if (M->getSource() != MDep->getDest())
1152    return false;
1153
1154  // Second, the length of the memcpy's must be the same, or the preceeding one
1155  // must be larger than the following one.
1156  ConstantInt* C1 = dyn_cast<ConstantInt>(MDep->getLength());
1157  ConstantInt* C2 = dyn_cast<ConstantInt>(M->getLength());
1158  if (!C1 || !C2)
1159    return false;
1160
1161  uint64_t CpySize = C1->getValue().getZExtValue();
1162  uint64_t DepSize = C2->getValue().getZExtValue();
1163
1164  if (DepSize < CpySize)
1165    return false;
1166
1167  // Finally, we have to make sure that the dest of the second does not
1168  // alias the source of the first
1169  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
1170  if (AA.alias(M->getRawDest(), CpySize, MDep->getRawSource(), DepSize) !=
1171      AliasAnalysis::NoAlias)
1172    return false;
1173  else if (AA.alias(M->getRawDest(), CpySize, M->getRawSource(), CpySize) !=
1174           AliasAnalysis::NoAlias)
1175    return false;
1176  else if (AA.alias(MDep->getRawDest(), DepSize, MDep->getRawSource(), DepSize)
1177           != AliasAnalysis::NoAlias)
1178    return false;
1179
1180  // If all checks passed, then we can transform these memcpy's
1181  Function* MemCpyFun = Intrinsic::getDeclaration(
1182                                 M->getParent()->getParent()->getParent(),
1183                                 M->getIntrinsicID());
1184
1185  std::vector<Value*> args;
1186  args.push_back(M->getRawDest());
1187  args.push_back(MDep->getRawSource());
1188  args.push_back(M->getLength());
1189  args.push_back(M->getAlignment());
1190
1191  CallInst* C = new CallInst(MemCpyFun, args.begin(), args.end(), "", M);
1192
1193  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1194  if (MD.getDependency(C) == MDep) {
1195    MD.dropInstruction(M);
1196    toErase.push_back(M);
1197    return true;
1198  } else {
1199    MD.removeInstruction(C);
1200    toErase.push_back(C);
1201    return false;
1202  }
1203}
1204
1205/// processInstruction - When calculating availability, handle an instruction
1206/// by inserting it into the appropriate sets
1207bool GVN::processInstruction(Instruction* I,
1208                                ValueNumberedSet& currAvail,
1209                                DenseMap<Value*, LoadInst*>& lastSeenLoad,
1210                                SmallVector<Instruction*, 4>& toErase) {
1211  if (LoadInst* L = dyn_cast<LoadInst>(I)) {
1212    return processLoad(L, lastSeenLoad, toErase);
1213  } else if (MemCpyInst* M = dyn_cast<MemCpyInst>(I)) {
1214    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1215
1216    // The are two possible optimizations we can do for memcpy:
1217    //   a) memcpy-memcpy xform which exposes redundance for DSE
1218    //   b) call-memcpy xform for sret return slot optimization
1219    Instruction* dep = MD.getDependency(M);
1220    if (dep == MemoryDependenceAnalysis::None ||
1221        dep == MemoryDependenceAnalysis::NonLocal)
1222      return false;
1223    else if (CallInst* C = dyn_cast<CallInst>(dep)) {
1224      if (!isa<MemCpyInst>(C))
1225        return performReturnSlotOptzn(M, C, toErase);
1226    } else if (!isa<MemCpyInst>(dep))
1227      return false;
1228
1229    return processMemCpy(M, cast<MemCpyInst>(dep), toErase);
1230  }
1231
1232  unsigned num = VN.lookup_or_add(I);
1233
1234  // Collapse PHI nodes
1235  if (PHINode* p = dyn_cast<PHINode>(I)) {
1236    Value* constVal = CollapsePhi(p);
1237
1238    if (constVal) {
1239      for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end();
1240           PI != PE; ++PI)
1241        if (PI->second.count(p))
1242          PI->second.erase(p);
1243
1244      p->replaceAllUsesWith(constVal);
1245      toErase.push_back(p);
1246    }
1247  // Perform value-number based elimination
1248  } else if (currAvail.test(num)) {
1249    Value* repl = find_leader(currAvail, num);
1250
1251    if (CallInst* CI = dyn_cast<CallInst>(I)) {
1252      AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
1253      if (!AA.doesNotAccessMemory(CI)) {
1254        MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1255        if (cast<Instruction>(repl)->getParent() != CI->getParent() ||
1256            MD.getDependency(CI) != MD.getDependency(cast<CallInst>(repl))) {
1257          // There must be an intervening may-alias store, so nothing from
1258          // this point on will be able to be replaced with the preceding call
1259          currAvail.erase(repl);
1260          currAvail.insert(I);
1261
1262          return false;
1263        }
1264      }
1265    }
1266
1267    // Remove it!
1268    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1269    MD.removeInstruction(I);
1270
1271    VN.erase(I);
1272    I->replaceAllUsesWith(repl);
1273    toErase.push_back(I);
1274    return true;
1275  } else if (!I->isTerminator()) {
1276    currAvail.set(num);
1277    currAvail.insert(I);
1278  }
1279
1280  return false;
1281}
1282
1283// GVN::runOnFunction - This is the main transformation entry point for a
1284// function.
1285//
1286bool GVN::runOnFunction(Function& F) {
1287  VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>());
1288
1289  bool changed = false;
1290  bool shouldContinue = true;
1291
1292  while (shouldContinue) {
1293    shouldContinue = iterateOnFunction(F);
1294    changed |= shouldContinue;
1295  }
1296
1297  return changed;
1298}
1299
1300
1301// GVN::iterateOnFunction - Executes one iteration of GVN
1302bool GVN::iterateOnFunction(Function &F) {
1303  // Clean out global sets from any previous functions
1304  VN.clear();
1305  availableOut.clear();
1306  phiMap.clear();
1307
1308  bool changed_function = false;
1309
1310  DominatorTree &DT = getAnalysis<DominatorTree>();
1311
1312  SmallVector<Instruction*, 4> toErase;
1313
1314  // Top-down walk of the dominator tree
1315  for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1316         E = df_end(DT.getRootNode()); DI != E; ++DI) {
1317
1318    // Get the set to update for this block
1319    ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
1320    DenseMap<Value*, LoadInst*> lastSeenLoad;
1321
1322    BasicBlock* BB = DI->getBlock();
1323
1324    // A block inherits AVAIL_OUT from its dominator
1325    if (DI->getIDom() != 0)
1326      currAvail = availableOut[DI->getIDom()->getBlock()];
1327
1328    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1329         BI != BE; ) {
1330      changed_function |= processInstruction(BI, currAvail,
1331                                             lastSeenLoad, toErase);
1332
1333      NumGVNInstr += toErase.size();
1334
1335      // Avoid iterator invalidation
1336      ++BI;
1337
1338      for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(),
1339           E = toErase.end(); I != E; ++I) {
1340        (*I)->eraseFromParent();
1341      }
1342
1343      toErase.clear();
1344    }
1345  }
1346
1347  return changed_function;
1348}
1349