GVN.cpp revision 4bda6e47e95204e6d9e7bf2b82e8099e911c722a 
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#include "llvm/Transforms/Scalar.h"
17#include "llvm/BasicBlock.h"
18#include "llvm/Constants.h"
19#include "llvm/DerivedTypes.h"
20#include "llvm/Function.h"
21#include "llvm/Instructions.h"
22#include "llvm/Value.h"
23#include "llvm/ADT/DenseMap.h"
24#include "llvm/ADT/DepthFirstIterator.h"
25#include "llvm/ADT/SmallPtrSet.h"
26#include "llvm/ADT/SmallVector.h"
27#include "llvm/ADT/SparseBitVector.h"
28#include "llvm/ADT/Statistic.h"
29#include "llvm/Analysis/Dominators.h"
30#include "llvm/Analysis/AliasAnalysis.h"
31#include "llvm/Analysis/MemoryDependenceAnalysis.h"
32#include "llvm/Support/CFG.h"
33#include "llvm/Support/Compiler.h"
34#include "llvm/Support/Debug.h"
35#include <list>
36using namespace llvm;
37
38STATISTIC(NumGVNInstr, "Number of instructions deleted");
39STATISTIC(NumGVNLoad, "Number of loads deleted");
40
41//===----------------------------------------------------------------------===//
42//                         ValueTable Class
43//===----------------------------------------------------------------------===//
44
45/// This class holds the mapping between values and value numbers.  It is used
46/// as an efficient mechanism to determine the expression-wise equivalence of
47/// two values.
48namespace {
49  struct VISIBILITY_HIDDEN Expression {
50    enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
51                            FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
52                            ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
53                            ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
54                            FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
55                            FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
56                            FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
57                            SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
58                            FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
59                            PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, EMPTY,
60                            TOMBSTONE };
61
62    ExpressionOpcode opcode;
63    const Type* type;
64    uint32_t firstVN;
65    uint32_t secondVN;
66    uint32_t thirdVN;
67    SmallVector<uint32_t, 4> varargs;
68    Value* function;
69
70    Expression() { }
71    Expression(ExpressionOpcode o) : opcode(o) { }
72
73    bool operator==(const Expression &other) const {
74      if (opcode != other.opcode)
75        return false;
76      else if (opcode == EMPTY || opcode == TOMBSTONE)
77        return true;
78      else if (type != other.type)
79        return false;
80      else if (function != other.function)
81        return false;
82      else if (firstVN != other.firstVN)
83        return false;
84      else if (secondVN != other.secondVN)
85        return false;
86      else if (thirdVN != other.thirdVN)
87        return false;
88      else {
89        if (varargs.size() != other.varargs.size())
90          return false;
91
92        for (size_t i = 0; i < varargs.size(); ++i)
93          if (varargs[i] != other.varargs[i])
94            return false;
95
96        return true;
97      }
98    }
99
100    bool operator!=(const Expression &other) const {
101      if (opcode != other.opcode)
102        return true;
103      else if (opcode == EMPTY || opcode == TOMBSTONE)
104        return false;
105      else if (type != other.type)
106        return true;
107      else if (function != other.function)
108        return true;
109      else if (firstVN != other.firstVN)
110        return true;
111      else if (secondVN != other.secondVN)
112        return true;
113      else if (thirdVN != other.thirdVN)
114        return true;
115      else {
116        if (varargs.size() != other.varargs.size())
117          return true;
118
119        for (size_t i = 0; i < varargs.size(); ++i)
120          if (varargs[i] != other.varargs[i])
121            return true;
122
123          return false;
124      }
125    }
126  };
127
128  class VISIBILITY_HIDDEN ValueTable {
129    private:
130      DenseMap<Value*, uint32_t> valueNumbering;
131      DenseMap<Expression, uint32_t> expressionNumbering;
132      AliasAnalysis* AA;
133      MemoryDependenceAnalysis* MD;
134
135      uint32_t nextValueNumber;
136
137      Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
138      Expression::ExpressionOpcode getOpcode(CmpInst* C);
139      Expression::ExpressionOpcode getOpcode(CastInst* C);
140      Expression create_expression(BinaryOperator* BO);
141      Expression create_expression(CmpInst* C);
142      Expression create_expression(ShuffleVectorInst* V);
143      Expression create_expression(ExtractElementInst* C);
144      Expression create_expression(InsertElementInst* V);
145      Expression create_expression(SelectInst* V);
146      Expression create_expression(CastInst* C);
147      Expression create_expression(GetElementPtrInst* G);
148      Expression create_expression(CallInst* C);
149    public:
150      ValueTable() : nextValueNumber(1) { }
151      uint32_t lookup_or_add(Value* V);
152      uint32_t lookup(Value* V) const;
153      void add(Value* V, uint32_t num);
154      void clear();
155      void erase(Value* v);
156      unsigned size();
157      void setAliasAnalysis(AliasAnalysis* A) { AA = A; }
158      void setMemDep(MemoryDependenceAnalysis* M) { MD = M; }
159  };
160}
161
162namespace llvm {
163template <> struct DenseMapInfo<Expression> {
164  static inline Expression getEmptyKey() {
165    return Expression(Expression::EMPTY);
166  }
167
168  static inline Expression getTombstoneKey() {
169    return Expression(Expression::TOMBSTONE);
170  }
171
172  static unsigned getHashValue(const Expression e) {
173    unsigned hash = e.opcode;
174
175    hash = e.firstVN + hash * 37;
176    hash = e.secondVN + hash * 37;
177    hash = e.thirdVN + hash * 37;
178
179    hash = ((unsigned)((uintptr_t)e.type >> 4) ^
180            (unsigned)((uintptr_t)e.type >> 9)) +
181           hash * 37;
182
183    for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
184         E = e.varargs.end(); I != E; ++I)
185      hash = *I + hash * 37;
186
187    hash = ((unsigned)((uintptr_t)e.function >> 4) ^
188            (unsigned)((uintptr_t)e.function >> 9)) +
189           hash * 37;
190
191    return hash;
192  }
193  static bool isEqual(const Expression &LHS, const Expression &RHS) {
194    return LHS == RHS;
195  }
196  static bool isPod() { return true; }
197};
198}
199
200//===----------------------------------------------------------------------===//
201//                     ValueTable Internal Functions
202//===----------------------------------------------------------------------===//
203Expression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) {
204  switch(BO->getOpcode()) {
205  default: // THIS SHOULD NEVER HAPPEN
206    assert(0 && "Binary operator with unknown opcode?");
207  case Instruction::Add:  return Expression::ADD;
208  case Instruction::Sub:  return Expression::SUB;
209  case Instruction::Mul:  return Expression::MUL;
210  case Instruction::UDiv: return Expression::UDIV;
211  case Instruction::SDiv: return Expression::SDIV;
212  case Instruction::FDiv: return Expression::FDIV;
213  case Instruction::URem: return Expression::UREM;
214  case Instruction::SRem: return Expression::SREM;
215  case Instruction::FRem: return Expression::FREM;
216  case Instruction::Shl:  return Expression::SHL;
217  case Instruction::LShr: return Expression::LSHR;
218  case Instruction::AShr: return Expression::ASHR;
219  case Instruction::And:  return Expression::AND;
220  case Instruction::Or:   return Expression::OR;
221  case Instruction::Xor:  return Expression::XOR;
222  }
223}
224
225Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
226  if (isa<ICmpInst>(C)) {
227    switch (C->getPredicate()) {
228    default:  // THIS SHOULD NEVER HAPPEN
229      assert(0 && "Comparison with unknown predicate?");
230    case ICmpInst::ICMP_EQ:  return Expression::ICMPEQ;
231    case ICmpInst::ICMP_NE:  return Expression::ICMPNE;
232    case ICmpInst::ICMP_UGT: return Expression::ICMPUGT;
233    case ICmpInst::ICMP_UGE: return Expression::ICMPUGE;
234    case ICmpInst::ICMP_ULT: return Expression::ICMPULT;
235    case ICmpInst::ICMP_ULE: return Expression::ICMPULE;
236    case ICmpInst::ICMP_SGT: return Expression::ICMPSGT;
237    case ICmpInst::ICMP_SGE: return Expression::ICMPSGE;
238    case ICmpInst::ICMP_SLT: return Expression::ICMPSLT;
239    case ICmpInst::ICMP_SLE: return Expression::ICMPSLE;
240    }
241  }
242  assert(isa<FCmpInst>(C) && "Unknown compare");
243  switch (C->getPredicate()) {
244  default: // THIS SHOULD NEVER HAPPEN
245    assert(0 && "Comparison with unknown predicate?");
246  case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ;
247  case FCmpInst::FCMP_OGT: return Expression::FCMPOGT;
248  case FCmpInst::FCMP_OGE: return Expression::FCMPOGE;
249  case FCmpInst::FCMP_OLT: return Expression::FCMPOLT;
250  case FCmpInst::FCMP_OLE: return Expression::FCMPOLE;
251  case FCmpInst::FCMP_ONE: return Expression::FCMPONE;
252  case FCmpInst::FCMP_ORD: return Expression::FCMPORD;
253  case FCmpInst::FCMP_UNO: return Expression::FCMPUNO;
254  case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ;
255  case FCmpInst::FCMP_UGT: return Expression::FCMPUGT;
256  case FCmpInst::FCMP_UGE: return Expression::FCMPUGE;
257  case FCmpInst::FCMP_ULT: return Expression::FCMPULT;
258  case FCmpInst::FCMP_ULE: return Expression::FCMPULE;
259  case FCmpInst::FCMP_UNE: return Expression::FCMPUNE;
260  }
261}
262
263Expression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) {
264  switch(C->getOpcode()) {
265  default: // THIS SHOULD NEVER HAPPEN
266    assert(0 && "Cast operator with unknown opcode?");
267  case Instruction::Trunc:    return Expression::TRUNC;
268  case Instruction::ZExt:     return Expression::ZEXT;
269  case Instruction::SExt:     return Expression::SEXT;
270  case Instruction::FPToUI:   return Expression::FPTOUI;
271  case Instruction::FPToSI:   return Expression::FPTOSI;
272  case Instruction::UIToFP:   return Expression::UITOFP;
273  case Instruction::SIToFP:   return Expression::SITOFP;
274  case Instruction::FPTrunc:  return Expression::FPTRUNC;
275  case Instruction::FPExt:    return Expression::FPEXT;
276  case Instruction::PtrToInt: return Expression::PTRTOINT;
277  case Instruction::IntToPtr: return Expression::INTTOPTR;
278  case Instruction::BitCast:  return Expression::BITCAST;
279  }
280}
281
282Expression ValueTable::create_expression(CallInst* C) {
283  Expression e;
284
285  e.type = C->getType();
286  e.firstVN = 0;
287  e.secondVN = 0;
288  e.thirdVN = 0;
289  e.function = C->getCalledFunction();
290  e.opcode = Expression::CALL;
291
292  for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end();
293       I != E; ++I)
294    e.varargs.push_back(lookup_or_add(*I));
295
296  return e;
297}
298
299Expression ValueTable::create_expression(BinaryOperator* BO) {
300  Expression e;
301
302  e.firstVN = lookup_or_add(BO->getOperand(0));
303  e.secondVN = lookup_or_add(BO->getOperand(1));
304  e.thirdVN = 0;
305  e.function = 0;
306  e.type = BO->getType();
307  e.opcode = getOpcode(BO);
308
309  return e;
310}
311
312Expression ValueTable::create_expression(CmpInst* C) {
313  Expression e;
314
315  e.firstVN = lookup_or_add(C->getOperand(0));
316  e.secondVN = lookup_or_add(C->getOperand(1));
317  e.thirdVN = 0;
318  e.function = 0;
319  e.type = C->getType();
320  e.opcode = getOpcode(C);
321
322  return e;
323}
324
325Expression ValueTable::create_expression(CastInst* C) {
326  Expression e;
327
328  e.firstVN = lookup_or_add(C->getOperand(0));
329  e.secondVN = 0;
330  e.thirdVN = 0;
331  e.function = 0;
332  e.type = C->getType();
333  e.opcode = getOpcode(C);
334
335  return e;
336}
337
338Expression ValueTable::create_expression(ShuffleVectorInst* S) {
339  Expression e;
340
341  e.firstVN = lookup_or_add(S->getOperand(0));
342  e.secondVN = lookup_or_add(S->getOperand(1));
343  e.thirdVN = lookup_or_add(S->getOperand(2));
344  e.function = 0;
345  e.type = S->getType();
346  e.opcode = Expression::SHUFFLE;
347
348  return e;
349}
350
351Expression ValueTable::create_expression(ExtractElementInst* E) {
352  Expression e;
353
354  e.firstVN = lookup_or_add(E->getOperand(0));
355  e.secondVN = lookup_or_add(E->getOperand(1));
356  e.thirdVN = 0;
357  e.function = 0;
358  e.type = E->getType();
359  e.opcode = Expression::EXTRACT;
360
361  return e;
362}
363
364Expression ValueTable::create_expression(InsertElementInst* I) {
365  Expression e;
366
367  e.firstVN = lookup_or_add(I->getOperand(0));
368  e.secondVN = lookup_or_add(I->getOperand(1));
369  e.thirdVN = lookup_or_add(I->getOperand(2));
370  e.function = 0;
371  e.type = I->getType();
372  e.opcode = Expression::INSERT;
373
374  return e;
375}
376
377Expression ValueTable::create_expression(SelectInst* I) {
378  Expression e;
379
380  e.firstVN = lookup_or_add(I->getCondition());
381  e.secondVN = lookup_or_add(I->getTrueValue());
382  e.thirdVN = lookup_or_add(I->getFalseValue());
383  e.function = 0;
384  e.type = I->getType();
385  e.opcode = Expression::SELECT;
386
387  return e;
388}
389
390Expression ValueTable::create_expression(GetElementPtrInst* G) {
391  Expression e;
392
393  e.firstVN = lookup_or_add(G->getPointerOperand());
394  e.secondVN = 0;
395  e.thirdVN = 0;
396  e.function = 0;
397  e.type = G->getType();
398  e.opcode = Expression::GEP;
399
400  for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
401       I != E; ++I)
402    e.varargs.push_back(lookup_or_add(*I));
403
404  return e;
405}
406
407//===----------------------------------------------------------------------===//
408//                     ValueTable External Functions
409//===----------------------------------------------------------------------===//
410
411/// lookup_or_add - Returns the value number for the specified value, assigning
412/// it a new number if it did not have one before.
413uint32_t ValueTable::lookup_or_add(Value* V) {
414  DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
415  if (VI != valueNumbering.end())
416    return VI->second;
417
418  if (CallInst* C = dyn_cast<CallInst>(V)) {
419    if (AA->doesNotAccessMemory(C)) {
420      Expression e = create_expression(C);
421
422      DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
423      if (EI != expressionNumbering.end()) {
424        valueNumbering.insert(std::make_pair(V, EI->second));
425        return EI->second;
426      } else {
427        expressionNumbering.insert(std::make_pair(e, nextValueNumber));
428        valueNumbering.insert(std::make_pair(V, nextValueNumber));
429
430        return nextValueNumber++;
431      }
432    } else if (AA->onlyReadsMemory(C)) {
433      Expression e = create_expression(C);
434
435      Instruction* dep = MD->getDependency(C);
436
437      if (dep == MemoryDependenceAnalysis::NonLocal ||
438          !isa<CallInst>(dep)) {
439        expressionNumbering.insert(std::make_pair(e, nextValueNumber));
440        valueNumbering.insert(std::make_pair(V, nextValueNumber));
441
442        return nextValueNumber++;
443      }
444
445      CallInst* cdep = cast<CallInst>(dep);
446      Expression d_exp = create_expression(cdep);
447
448      if (e != d_exp) {
449        expressionNumbering.insert(std::make_pair(e, nextValueNumber));
450        valueNumbering.insert(std::make_pair(V, nextValueNumber));
451
452        return nextValueNumber++;
453      } else {
454        uint32_t v = expressionNumbering[d_exp];
455        valueNumbering.insert(std::make_pair(V, v));
456        return v;
457      }
458
459    } else {
460      valueNumbering.insert(std::make_pair(V, nextValueNumber));
461      return nextValueNumber++;
462    }
463  } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
464    Expression e = create_expression(BO);
465
466    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
467    if (EI != expressionNumbering.end()) {
468      valueNumbering.insert(std::make_pair(V, EI->second));
469      return EI->second;
470    } else {
471      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
472      valueNumbering.insert(std::make_pair(V, nextValueNumber));
473
474      return nextValueNumber++;
475    }
476  } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
477    Expression e = create_expression(C);
478
479    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
480    if (EI != expressionNumbering.end()) {
481      valueNumbering.insert(std::make_pair(V, EI->second));
482      return EI->second;
483    } else {
484      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
485      valueNumbering.insert(std::make_pair(V, nextValueNumber));
486
487      return nextValueNumber++;
488    }
489  } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
490    Expression e = create_expression(U);
491
492    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
493    if (EI != expressionNumbering.end()) {
494      valueNumbering.insert(std::make_pair(V, EI->second));
495      return EI->second;
496    } else {
497      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
498      valueNumbering.insert(std::make_pair(V, nextValueNumber));
499
500      return nextValueNumber++;
501    }
502  } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
503    Expression e = create_expression(U);
504
505    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
506    if (EI != expressionNumbering.end()) {
507      valueNumbering.insert(std::make_pair(V, EI->second));
508      return EI->second;
509    } else {
510      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
511      valueNumbering.insert(std::make_pair(V, nextValueNumber));
512
513      return nextValueNumber++;
514    }
515  } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
516    Expression e = create_expression(U);
517
518    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
519    if (EI != expressionNumbering.end()) {
520      valueNumbering.insert(std::make_pair(V, EI->second));
521      return EI->second;
522    } else {
523      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
524      valueNumbering.insert(std::make_pair(V, nextValueNumber));
525
526      return nextValueNumber++;
527    }
528  } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
529    Expression e = create_expression(U);
530
531    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
532    if (EI != expressionNumbering.end()) {
533      valueNumbering.insert(std::make_pair(V, EI->second));
534      return EI->second;
535    } else {
536      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
537      valueNumbering.insert(std::make_pair(V, nextValueNumber));
538
539      return nextValueNumber++;
540    }
541  } else if (CastInst* U = dyn_cast<CastInst>(V)) {
542    Expression e = create_expression(U);
543
544    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
545    if (EI != expressionNumbering.end()) {
546      valueNumbering.insert(std::make_pair(V, EI->second));
547      return EI->second;
548    } else {
549      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
550      valueNumbering.insert(std::make_pair(V, nextValueNumber));
551
552      return nextValueNumber++;
553    }
554  } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
555    Expression e = create_expression(U);
556
557    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
558    if (EI != expressionNumbering.end()) {
559      valueNumbering.insert(std::make_pair(V, EI->second));
560      return EI->second;
561    } else {
562      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
563      valueNumbering.insert(std::make_pair(V, nextValueNumber));
564
565      return nextValueNumber++;
566    }
567  } else {
568    valueNumbering.insert(std::make_pair(V, nextValueNumber));
569    return nextValueNumber++;
570  }
571}
572
573/// lookup - Returns the value number of the specified value. Fails if
574/// the value has not yet been numbered.
575uint32_t ValueTable::lookup(Value* V) const {
576  DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
577  assert(VI != valueNumbering.end() && "Value not numbered?");
578  return VI->second;
579}
580
581/// clear - Remove all entries from the ValueTable
582void ValueTable::clear() {
583  valueNumbering.clear();
584  expressionNumbering.clear();
585  nextValueNumber = 1;
586}
587
588/// erase - Remove a value from the value numbering
589void ValueTable::erase(Value* V) {
590  valueNumbering.erase(V);
591}
592
593//===----------------------------------------------------------------------===//
594//                       ValueNumberedSet Class
595//===----------------------------------------------------------------------===//
596namespace {
597class VISIBILITY_HIDDEN ValueNumberedSet {
598  private:
599    SmallPtrSet<Value*, 8> contents;
600    SparseBitVector<64> numbers;
601  public:
602    ValueNumberedSet() { }
603    ValueNumberedSet(const ValueNumberedSet& other) {
604      numbers = other.numbers;
605      contents = other.contents;
606    }
607
608    typedef SmallPtrSet<Value*, 8>::iterator iterator;
609
610    iterator begin() { return contents.begin(); }
611    iterator end() { return contents.end(); }
612
613    bool insert(Value* v) { return contents.insert(v); }
614    void insert(iterator I, iterator E) { contents.insert(I, E); }
615    void erase(Value* v) { contents.erase(v); }
616    unsigned count(Value* v) { return contents.count(v); }
617    size_t size() { return contents.size(); }
618
619    void set(unsigned i)  {
620      numbers.set(i);
621    }
622
623    void operator=(const ValueNumberedSet& other) {
624      contents = other.contents;
625      numbers = other.numbers;
626    }
627
628    void reset(unsigned i)  {
629      numbers.reset(i);
630    }
631
632    bool test(unsigned i)  {
633      return numbers.test(i);
634    }
635};
636}
637
638//===----------------------------------------------------------------------===//
639//                         GVN Pass
640//===----------------------------------------------------------------------===//
641
642namespace {
643
644  class VISIBILITY_HIDDEN GVN : public FunctionPass {
645    bool runOnFunction(Function &F);
646  public:
647    static char ID; // Pass identification, replacement for typeid
648    GVN() : FunctionPass((intptr_t)&ID) { }
649
650  private:
651    ValueTable VN;
652
653    DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
654
655    typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType;
656    PhiMapType phiMap;
657
658
659    // This transformation requires dominator postdominator info
660    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
661      AU.setPreservesCFG();
662      AU.addRequired<DominatorTree>();
663      AU.addRequired<MemoryDependenceAnalysis>();
664      AU.addRequired<AliasAnalysis>();
665      AU.addPreserved<AliasAnalysis>();
666      AU.addPreserved<MemoryDependenceAnalysis>();
667    }
668
669    // Helper fuctions
670    // FIXME: eliminate or document these better
671    Value* find_leader(ValueNumberedSet& vals, uint32_t v) ;
672    void val_insert(ValueNumberedSet& s, Value* v);
673    bool processLoad(LoadInst* L,
674                     DenseMap<Value*, LoadInst*> &lastLoad,
675                     SmallVectorImpl<Instruction*> &toErase);
676    bool processInstruction(Instruction* I,
677                            ValueNumberedSet& currAvail,
678                            DenseMap<Value*, LoadInst*>& lastSeenLoad,
679                            SmallVectorImpl<Instruction*> &toErase);
680    bool processNonLocalLoad(LoadInst* L,
681                             SmallVectorImpl<Instruction*> &toErase);
682    Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig,
683                            DenseMap<BasicBlock*, Value*> &Phis,
684                            bool top_level = false);
685    void dump(DenseMap<BasicBlock*, Value*>& d);
686    bool iterateOnFunction(Function &F);
687    Value* CollapsePhi(PHINode* p);
688    bool isSafeReplacement(PHINode* p, Instruction* inst);
689  };
690
691  char GVN::ID = 0;
692}
693
694// createGVNPass - The public interface to this file...
695FunctionPass *llvm::createGVNPass() { return new GVN(); }
696
697static RegisterPass<GVN> X("gvn",
698                           "Global Value Numbering");
699
700/// find_leader - Given a set and a value number, return the first
701/// element of the set with that value number, or 0 if no such element
702/// is present
703Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) {
704  if (!vals.test(v))
705    return 0;
706
707  for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
708       I != E; ++I)
709    if (v == VN.lookup(*I))
710      return *I;
711
712  assert(0 && "No leader found, but present bit is set?");
713  return 0;
714}
715
716/// val_insert - Insert a value into a set only if there is not a value
717/// with the same value number already in the set
718void GVN::val_insert(ValueNumberedSet& s, Value* v) {
719  uint32_t num = VN.lookup(v);
720  if (!s.test(num))
721    s.insert(v);
722}
723
724void GVN::dump(DenseMap<BasicBlock*, Value*>& d) {
725  printf("{\n");
726  for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(),
727       E = d.end(); I != E; ++I) {
728    if (I->second == MemoryDependenceAnalysis::None)
729      printf("None\n");
730    else
731      I->second->dump();
732  }
733  printf("}\n");
734}
735
736Value* GVN::CollapsePhi(PHINode* p) {
737  DominatorTree &DT = getAnalysis<DominatorTree>();
738  Value* constVal = p->hasConstantValue();
739
740  if (!constVal) return 0;
741
742  Instruction* inst = dyn_cast<Instruction>(constVal);
743  if (!inst)
744    return constVal;
745
746  if (DT.dominates(inst, p))
747    if (isSafeReplacement(p, inst))
748      return inst;
749  return 0;
750}
751
752bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) {
753  if (!isa<PHINode>(inst))
754    return true;
755
756  for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end();
757       UI != E; ++UI)
758    if (PHINode* use_phi = dyn_cast<PHINode>(UI))
759      if (use_phi->getParent() == inst->getParent())
760        return false;
761
762  return true;
763}
764
765/// GetValueForBlock - Get the value to use within the specified basic block.
766/// available values are in Phis.
767Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
768                             DenseMap<BasicBlock*, Value*> &Phis,
769                             bool top_level) {
770
771  // If we have already computed this value, return the previously computed val.
772  DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB);
773  if (V != Phis.end() && !top_level) return V->second;
774
775  BasicBlock* singlePred = BB->getSinglePredecessor();
776  if (singlePred) {
777    Value *ret = GetValueForBlock(singlePred, orig, Phis);
778    Phis[BB] = ret;
779    return ret;
780  }
781
782  // Otherwise, the idom is the loop, so we need to insert a PHI node.  Do so
783  // now, then get values to fill in the incoming values for the PHI.
784  PHINode *PN = PHINode::Create(orig->getType(), orig->getName()+".rle",
785                                BB->begin());
786  PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB)));
787
788  if (Phis.count(BB) == 0)
789    Phis.insert(std::make_pair(BB, PN));
790
791  // Fill in the incoming values for the block.
792  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
793    Value* val = GetValueForBlock(*PI, orig, Phis);
794    PN->addIncoming(val, *PI);
795  }
796
797  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
798  AA.copyValue(orig, PN);
799
800  // Attempt to collapse PHI nodes that are trivially redundant
801  Value* v = CollapsePhi(PN);
802  if (!v) {
803    // Cache our phi construction results
804    phiMap[orig->getPointerOperand()].insert(PN);
805    return PN;
806  }
807
808  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
809
810  MD.removeInstruction(PN);
811  PN->replaceAllUsesWith(v);
812
813  for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
814       E = Phis.end(); I != E; ++I)
815    if (I->second == PN)
816      I->second = v;
817
818  PN->eraseFromParent();
819
820  Phis[BB] = v;
821  return v;
822}
823
824/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are
825/// non-local by performing PHI construction.
826bool GVN::processNonLocalLoad(LoadInst* L,
827                              SmallVectorImpl<Instruction*> &toErase) {
828  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
829
830  // Find the non-local dependencies of the load
831  DenseMap<BasicBlock*, Value*> deps;
832  MD.getNonLocalDependency(L, deps);
833
834  DenseMap<BasicBlock*, Value*> repl;
835
836  // Filter out useless results (non-locals, etc)
837  for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end();
838       I != E; ++I) {
839    if (I->second == MemoryDependenceAnalysis::None)
840      return false;
841
842    if (I->second == MemoryDependenceAnalysis::NonLocal)
843      continue;
844
845    if (StoreInst* S = dyn_cast<StoreInst>(I->second)) {
846      if (S->getPointerOperand() != L->getPointerOperand())
847        return false;
848      repl[I->first] = S->getOperand(0);
849    } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) {
850      if (LD->getPointerOperand() != L->getPointerOperand())
851        return false;
852      repl[I->first] = LD;
853    } else {
854      return false;
855    }
856  }
857
858  // Use cached PHI construction information from previous runs
859  SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()];
860  for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end();
861       I != E; ++I) {
862    if ((*I)->getParent() == L->getParent()) {
863      MD.removeInstruction(L);
864      L->replaceAllUsesWith(*I);
865      toErase.push_back(L);
866      NumGVNLoad++;
867      return true;
868    }
869
870    repl.insert(std::make_pair((*I)->getParent(), *I));
871  }
872
873  // Perform PHI construction
874  SmallPtrSet<BasicBlock*, 4> visited;
875  Value* v = GetValueForBlock(L->getParent(), L, repl, true);
876
877  MD.removeInstruction(L);
878  L->replaceAllUsesWith(v);
879  toErase.push_back(L);
880  NumGVNLoad++;
881
882  return true;
883}
884
885/// processLoad - Attempt to eliminate a load, first by eliminating it
886/// locally, and then attempting non-local elimination if that fails.
887bool GVN::processLoad(LoadInst *L, DenseMap<Value*, LoadInst*> &lastLoad,
888                      SmallVectorImpl<Instruction*> &toErase) {
889  if (L->isVolatile()) {
890    lastLoad[L->getPointerOperand()] = L;
891    return false;
892  }
893
894  Value* pointer = L->getPointerOperand();
895  LoadInst*& last = lastLoad[pointer];
896
897  // ... to a pointer that has been loaded from before...
898  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
899  bool removedNonLocal = false;
900  Instruction* dep = MD.getDependency(L);
901  if (dep == MemoryDependenceAnalysis::NonLocal &&
902      L->getParent() != &L->getParent()->getParent()->getEntryBlock()) {
903    removedNonLocal = processNonLocalLoad(L, toErase);
904
905    if (!removedNonLocal)
906      last = L;
907
908    return removedNonLocal;
909  }
910
911
912  bool deletedLoad = false;
913
914  // Walk up the dependency chain until we either find
915  // a dependency we can use, or we can't walk any further
916  while (dep != MemoryDependenceAnalysis::None &&
917         dep != MemoryDependenceAnalysis::NonLocal &&
918         (isa<LoadInst>(dep) || isa<StoreInst>(dep))) {
919    // ... that depends on a store ...
920    if (StoreInst* S = dyn_cast<StoreInst>(dep)) {
921      if (S->getPointerOperand() == pointer) {
922        // Remove it!
923        MD.removeInstruction(L);
924
925        L->replaceAllUsesWith(S->getOperand(0));
926        toErase.push_back(L);
927        deletedLoad = true;
928        NumGVNLoad++;
929      }
930
931      // Whether we removed it or not, we can't
932      // go any further
933      break;
934    } else if (!last) {
935      // If we don't depend on a store, and we haven't
936      // been loaded before, bail.
937      break;
938    } else if (dep == last) {
939      // Remove it!
940      MD.removeInstruction(L);
941
942      L->replaceAllUsesWith(last);
943      toErase.push_back(L);
944      deletedLoad = true;
945      NumGVNLoad++;
946
947      break;
948    } else {
949      dep = MD.getDependency(L, dep);
950    }
951  }
952
953  if (dep != MemoryDependenceAnalysis::None &&
954      dep != MemoryDependenceAnalysis::NonLocal &&
955      isa<AllocationInst>(dep)) {
956    // Check that this load is actually from the
957    // allocation we found
958    Value* v = L->getOperand(0);
959    while (true) {
960      if (BitCastInst *BC = dyn_cast<BitCastInst>(v))
961        v = BC->getOperand(0);
962      else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(v))
963        v = GEP->getOperand(0);
964      else
965        break;
966    }
967    if (v == dep) {
968      // If this load depends directly on an allocation, there isn't
969      // anything stored there; therefore, we can optimize this load
970      // to undef.
971      MD.removeInstruction(L);
972
973      L->replaceAllUsesWith(UndefValue::get(L->getType()));
974      toErase.push_back(L);
975      deletedLoad = true;
976      NumGVNLoad++;
977    }
978  }
979
980  if (!deletedLoad)
981    last = L;
982
983  return deletedLoad;
984}
985
986/// processInstruction - When calculating availability, handle an instruction
987/// by inserting it into the appropriate sets
988bool GVN::processInstruction(Instruction *I, ValueNumberedSet &currAvail,
989                             DenseMap<Value*, LoadInst*> &lastSeenLoad,
990                             SmallVectorImpl<Instruction*> &toErase) {
991  if (LoadInst* L = dyn_cast<LoadInst>(I))
992    return processLoad(L, lastSeenLoad, toErase);
993
994  // Allocations are always uniquely numbered, so we can save time and memory
995  // by fast failing them.
996  if (isa<AllocationInst>(I))
997    return false;
998
999  unsigned num = VN.lookup_or_add(I);
1000
1001  // Collapse PHI nodes
1002  if (PHINode* p = dyn_cast<PHINode>(I)) {
1003    Value* constVal = CollapsePhi(p);
1004
1005    if (constVal) {
1006      for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end();
1007           PI != PE; ++PI)
1008        if (PI->second.count(p))
1009          PI->second.erase(p);
1010
1011      p->replaceAllUsesWith(constVal);
1012      toErase.push_back(p);
1013    }
1014  // Perform value-number based elimination
1015  } else if (currAvail.test(num)) {
1016    Value* repl = find_leader(currAvail, num);
1017
1018    // Remove it!
1019    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1020    MD.removeInstruction(I);
1021
1022    VN.erase(I);
1023    I->replaceAllUsesWith(repl);
1024    toErase.push_back(I);
1025    return true;
1026  } else if (!I->isTerminator()) {
1027    currAvail.set(num);
1028    currAvail.insert(I);
1029  }
1030
1031  return false;
1032}
1033
1034// GVN::runOnFunction - This is the main transformation entry point for a
1035// function.
1036//
1037bool GVN::runOnFunction(Function& F) {
1038  VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>());
1039  VN.setMemDep(&getAnalysis<MemoryDependenceAnalysis>());
1040
1041  bool changed = false;
1042  bool shouldContinue = true;
1043
1044  while (shouldContinue) {
1045    shouldContinue = iterateOnFunction(F);
1046    changed |= shouldContinue;
1047  }
1048
1049  return changed;
1050}
1051
1052
1053// GVN::iterateOnFunction - Executes one iteration of GVN
1054bool GVN::iterateOnFunction(Function &F) {
1055  // Clean out global sets from any previous functions
1056  VN.clear();
1057  availableOut.clear();
1058  phiMap.clear();
1059
1060  bool changed_function = false;
1061
1062  DominatorTree &DT = getAnalysis<DominatorTree>();
1063
1064  SmallVector<Instruction*, 8> toErase;
1065  DenseMap<Value*, LoadInst*> lastSeenLoad;
1066  DenseMap<DomTreeNode*, size_t> numChildrenVisited;
1067
1068  // Top-down walk of the dominator tree
1069  for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1070         E = df_end(DT.getRootNode()); DI != E; ++DI) {
1071
1072    // Get the set to update for this block
1073    ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
1074    lastSeenLoad.clear();
1075
1076    BasicBlock* BB = DI->getBlock();
1077
1078    // A block inherits AVAIL_OUT from its dominator
1079    if (DI->getIDom() != 0) {
1080      currAvail = availableOut[DI->getIDom()->getBlock()];
1081
1082      numChildrenVisited[DI->getIDom()]++;
1083
1084      if (numChildrenVisited[DI->getIDom()] == DI->getIDom()->getNumChildren()) {
1085        availableOut.erase(DI->getIDom()->getBlock());
1086        numChildrenVisited.erase(DI->getIDom());
1087      }
1088    }
1089
1090    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1091         BI != BE;) {
1092      changed_function |= processInstruction(BI, currAvail,
1093                                             lastSeenLoad, toErase);
1094      if (toErase.empty()) {
1095        ++BI;
1096        continue;
1097      }
1098
1099      // If we need some instructions deleted, do it now.
1100      NumGVNInstr += toErase.size();
1101
1102      // Avoid iterator invalidation.
1103      bool AtStart = BI == BB->begin();
1104      if (!AtStart)
1105        --BI;
1106
1107      for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(),
1108           E = toErase.end(); I != E; ++I)
1109        (*I)->eraseFromParent();
1110
1111      if (AtStart)
1112        BI = BB->begin();
1113      else
1114        ++BI;
1115
1116      toErase.clear();
1117    }
1118  }
1119
1120  return changed_function;
1121}
1122