GVN.cpp revision 7b45e33107b59275cfb11f7e8b2de26db7530f3c 
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
45static DominatorTree* DT;
46static AliasAnalysis* AA;
47static MemoryDependenceAnalysis* MD;
48
49/// This class holds the mapping between values and value numbers.  It is used
50/// as an efficient mechanism to determine the expression-wise equivalence of
51/// two values.
52namespace {
53  struct VISIBILITY_HIDDEN Expression {
54    enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
55                            FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
56                            ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
57                            ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
58                            FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
59                            FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
60                            FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
61                            SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
62                            FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
63                            PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, EMPTY,
64                            TOMBSTONE };
65
66    ExpressionOpcode opcode;
67    const Type* type;
68    uint32_t firstVN;
69    uint32_t secondVN;
70    uint32_t thirdVN;
71    SmallVector<uint32_t, 4> varargs;
72    Value* function;
73
74    Expression() { }
75    Expression(ExpressionOpcode o) : opcode(o) { }
76
77    bool operator==(const Expression &other) const {
78      if (opcode != other.opcode)
79        return false;
80      else if (opcode == EMPTY || opcode == TOMBSTONE)
81        return true;
82      else if (type != other.type)
83        return false;
84      else if (function != other.function)
85        return false;
86      else if (firstVN != other.firstVN)
87        return false;
88      else if (secondVN != other.secondVN)
89        return false;
90      else if (thirdVN != other.thirdVN)
91        return false;
92      else {
93        if (varargs.size() != other.varargs.size())
94          return false;
95
96        for (size_t i = 0; i < varargs.size(); ++i)
97          if (varargs[i] != other.varargs[i])
98            return false;
99
100        return true;
101      }
102    }
103
104    bool operator!=(const Expression &other) const {
105      if (opcode != other.opcode)
106        return true;
107      else if (opcode == EMPTY || opcode == TOMBSTONE)
108        return false;
109      else if (type != other.type)
110        return true;
111      else if (function != other.function)
112        return true;
113      else if (firstVN != other.firstVN)
114        return true;
115      else if (secondVN != other.secondVN)
116        return true;
117      else if (thirdVN != other.thirdVN)
118        return true;
119      else {
120        if (varargs.size() != other.varargs.size())
121          return true;
122
123        for (size_t i = 0; i < varargs.size(); ++i)
124          if (varargs[i] != other.varargs[i])
125            return true;
126
127          return false;
128      }
129    }
130  };
131
132  class VISIBILITY_HIDDEN ValueTable {
133    private:
134      DenseMap<Value*, uint32_t> valueNumbering;
135      DenseMap<Expression, uint32_t> expressionNumbering;
136
137      uint32_t nextValueNumber;
138
139      Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
140      Expression::ExpressionOpcode getOpcode(CmpInst* C);
141      Expression::ExpressionOpcode getOpcode(CastInst* C);
142      Expression create_expression(BinaryOperator* BO);
143      Expression create_expression(CmpInst* C);
144      Expression create_expression(ShuffleVectorInst* V);
145      Expression create_expression(ExtractElementInst* C);
146      Expression create_expression(InsertElementInst* V);
147      Expression create_expression(SelectInst* V);
148      Expression create_expression(CastInst* C);
149      Expression create_expression(GetElementPtrInst* G);
150      Expression create_expression(CallInst* C);
151    public:
152      ValueTable() : nextValueNumber(1) { }
153      uint32_t lookup_or_add(Value* V);
154      uint32_t lookup(Value* V) const;
155      void add(Value* V, uint32_t num);
156      void clear();
157      void erase(Value* v);
158      unsigned size();
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  Value* constVal = p->hasConstantValue();
738
739  if (!constVal) return 0;
740
741  Instruction* inst = dyn_cast<Instruction>(constVal);
742  if (!inst)
743    return constVal;
744
745  if (DT->dominates(inst, p))
746    if (isSafeReplacement(p, inst))
747      return inst;
748  return 0;
749}
750
751bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) {
752  if (!isa<PHINode>(inst))
753    return true;
754
755  for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end();
756       UI != E; ++UI)
757    if (PHINode* use_phi = dyn_cast<PHINode>(UI))
758      if (use_phi->getParent() == inst->getParent())
759        return false;
760
761  return true;
762}
763
764/// GetValueForBlock - Get the value to use within the specified basic block.
765/// available values are in Phis.
766Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
767                             DenseMap<BasicBlock*, Value*> &Phis,
768                             bool top_level) {
769
770  // If we have already computed this value, return the previously computed val.
771  DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB);
772  if (V != Phis.end() && !top_level) return V->second;
773
774  BasicBlock* singlePred = BB->getSinglePredecessor();
775  if (singlePred) {
776    Value *ret = GetValueForBlock(singlePred, orig, Phis);
777    Phis[BB] = ret;
778    return ret;
779  }
780
781  // Otherwise, the idom is the loop, so we need to insert a PHI node.  Do so
782  // now, then get values to fill in the incoming values for the PHI.
783  PHINode *PN = PHINode::Create(orig->getType(), orig->getName()+".rle",
784                                BB->begin());
785  PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB)));
786
787  if (Phis.count(BB) == 0)
788    Phis.insert(std::make_pair(BB, PN));
789
790  // Fill in the incoming values for the block.
791  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
792    Value* val = GetValueForBlock(*PI, orig, Phis);
793    PN->addIncoming(val, *PI);
794  }
795
796  AA->copyValue(orig, PN);
797
798  // Attempt to collapse PHI nodes that are trivially redundant
799  Value* v = CollapsePhi(PN);
800  if (!v) {
801    // Cache our phi construction results
802    phiMap[orig->getPointerOperand()].insert(PN);
803    return PN;
804  }
805
806  MD->removeInstruction(PN);
807  PN->replaceAllUsesWith(v);
808
809  for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
810       E = Phis.end(); I != E; ++I)
811    if (I->second == PN)
812      I->second = v;
813
814  PN->eraseFromParent();
815
816  Phis[BB] = v;
817  return v;
818}
819
820/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are
821/// non-local by performing PHI construction.
822bool GVN::processNonLocalLoad(LoadInst* L,
823                              SmallVectorImpl<Instruction*> &toErase) {
824  // Find the non-local dependencies of the load
825  DenseMap<BasicBlock*, Value*> deps;
826  MD->getNonLocalDependency(L, deps);
827
828  DenseMap<BasicBlock*, Value*> repl;
829
830  // Filter out useless results (non-locals, etc)
831  for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end();
832       I != E; ++I) {
833    if (I->second == MemoryDependenceAnalysis::None)
834      return false;
835
836    if (I->second == MemoryDependenceAnalysis::NonLocal)
837      continue;
838
839    if (StoreInst* S = dyn_cast<StoreInst>(I->second)) {
840      if (S->getPointerOperand() != L->getPointerOperand())
841        return false;
842      repl[I->first] = S->getOperand(0);
843    } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) {
844      if (LD->getPointerOperand() != L->getPointerOperand())
845        return false;
846      repl[I->first] = LD;
847    } else {
848      return false;
849    }
850  }
851
852  // Use cached PHI construction information from previous runs
853  SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()];
854  for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end();
855       I != E; ++I) {
856    if ((*I)->getParent() == L->getParent()) {
857      MD->removeInstruction(L);
858      L->replaceAllUsesWith(*I);
859      toErase.push_back(L);
860      NumGVNLoad++;
861      return true;
862    }
863
864    repl.insert(std::make_pair((*I)->getParent(), *I));
865  }
866
867  // Perform PHI construction
868  SmallPtrSet<BasicBlock*, 4> visited;
869  Value* v = GetValueForBlock(L->getParent(), L, repl, true);
870
871  MD->removeInstruction(L);
872  L->replaceAllUsesWith(v);
873  toErase.push_back(L);
874  NumGVNLoad++;
875
876  return true;
877}
878
879/// processLoad - Attempt to eliminate a load, first by eliminating it
880/// locally, and then attempting non-local elimination if that fails.
881bool GVN::processLoad(LoadInst *L, DenseMap<Value*, LoadInst*> &lastLoad,
882                      SmallVectorImpl<Instruction*> &toErase) {
883  if (L->isVolatile()) {
884    lastLoad[L->getPointerOperand()] = L;
885    return false;
886  }
887
888  Value* pointer = L->getPointerOperand();
889  LoadInst*& last = lastLoad[pointer];
890
891  // ... to a pointer that has been loaded from before...
892  bool removedNonLocal = false;
893  Instruction* dep = MD->getDependency(L);
894  if (dep == MemoryDependenceAnalysis::NonLocal &&
895      L->getParent() != &L->getParent()->getParent()->getEntryBlock()) {
896    removedNonLocal = processNonLocalLoad(L, toErase);
897
898    if (!removedNonLocal)
899      last = L;
900
901    return removedNonLocal;
902  }
903
904
905  bool deletedLoad = false;
906
907  // Walk up the dependency chain until we either find
908  // a dependency we can use, or we can't walk any further
909  while (dep != MemoryDependenceAnalysis::None &&
910         dep != MemoryDependenceAnalysis::NonLocal &&
911         (isa<LoadInst>(dep) || isa<StoreInst>(dep))) {
912    // ... that depends on a store ...
913    if (StoreInst* S = dyn_cast<StoreInst>(dep)) {
914      if (S->getPointerOperand() == pointer) {
915        // Remove it!
916        MD->removeInstruction(L);
917
918        L->replaceAllUsesWith(S->getOperand(0));
919        toErase.push_back(L);
920        deletedLoad = true;
921        NumGVNLoad++;
922      }
923
924      // Whether we removed it or not, we can't
925      // go any further
926      break;
927    } else if (!last) {
928      // If we don't depend on a store, and we haven't
929      // been loaded before, bail.
930      break;
931    } else if (dep == last) {
932      // Remove it!
933      MD->removeInstruction(L);
934
935      L->replaceAllUsesWith(last);
936      toErase.push_back(L);
937      deletedLoad = true;
938      NumGVNLoad++;
939
940      break;
941    } else {
942      dep = MD->getDependency(L, dep);
943    }
944  }
945
946  if (dep != MemoryDependenceAnalysis::None &&
947      dep != MemoryDependenceAnalysis::NonLocal &&
948      isa<AllocationInst>(dep)) {
949    // Check that this load is actually from the
950    // allocation we found
951    Value* v = L->getOperand(0);
952    while (true) {
953      if (BitCastInst *BC = dyn_cast<BitCastInst>(v))
954        v = BC->getOperand(0);
955      else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(v))
956        v = GEP->getOperand(0);
957      else
958        break;
959    }
960    if (v == dep) {
961      // If this load depends directly on an allocation, there isn't
962      // anything stored there; therefore, we can optimize this load
963      // to undef.
964      MD->removeInstruction(L);
965
966      L->replaceAllUsesWith(UndefValue::get(L->getType()));
967      toErase.push_back(L);
968      deletedLoad = true;
969      NumGVNLoad++;
970    }
971  }
972
973  if (!deletedLoad)
974    last = L;
975
976  return deletedLoad;
977}
978
979/// processInstruction - When calculating availability, handle an instruction
980/// by inserting it into the appropriate sets
981bool GVN::processInstruction(Instruction *I, ValueNumberedSet &currAvail,
982                             DenseMap<Value*, LoadInst*> &lastSeenLoad,
983                             SmallVectorImpl<Instruction*> &toErase) {
984  if (LoadInst* L = dyn_cast<LoadInst>(I))
985    return processLoad(L, lastSeenLoad, toErase);
986
987  // Allocations are always uniquely numbered, so we can save time and memory
988  // by fast failing them.
989  if (isa<AllocationInst>(I))
990    return false;
991
992  unsigned num = VN.lookup_or_add(I);
993
994  // Collapse PHI nodes
995  if (PHINode* p = dyn_cast<PHINode>(I)) {
996    Value* constVal = CollapsePhi(p);
997
998    if (constVal) {
999      for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end();
1000           PI != PE; ++PI)
1001        if (PI->second.count(p))
1002          PI->second.erase(p);
1003
1004      p->replaceAllUsesWith(constVal);
1005      toErase.push_back(p);
1006    }
1007  // Perform value-number based elimination
1008  } else if (currAvail.test(num)) {
1009    Value* repl = find_leader(currAvail, num);
1010
1011    // Remove it!
1012    MD->removeInstruction(I);
1013
1014    VN.erase(I);
1015    I->replaceAllUsesWith(repl);
1016    toErase.push_back(I);
1017    return true;
1018  } else if (!I->isTerminator()) {
1019    currAvail.set(num);
1020    currAvail.insert(I);
1021  }
1022
1023  return false;
1024}
1025
1026// GVN::runOnFunction - This is the main transformation entry point for a
1027// function.
1028//
1029bool GVN::runOnFunction(Function& F) {
1030  DT = &getAnalysis<DominatorTree>();
1031  AA = &getAnalysis<AliasAnalysis>();
1032  MD = &getAnalysis<MemoryDependenceAnalysis>();
1033
1034  bool changed = false;
1035  bool shouldContinue = true;
1036
1037  while (shouldContinue) {
1038    shouldContinue = iterateOnFunction(F);
1039    changed |= shouldContinue;
1040  }
1041
1042  return changed;
1043}
1044
1045
1046// GVN::iterateOnFunction - Executes one iteration of GVN
1047bool GVN::iterateOnFunction(Function &F) {
1048  // Clean out global sets from any previous functions
1049  VN.clear();
1050  availableOut.clear();
1051  phiMap.clear();
1052
1053  bool changed_function = false;
1054
1055  SmallVector<Instruction*, 8> toErase;
1056  DenseMap<Value*, LoadInst*> lastSeenLoad;
1057  DenseMap<DomTreeNode*, size_t> numChildrenVisited;
1058
1059  // Top-down walk of the dominator tree
1060  for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()),
1061         E = df_end(DT->getRootNode()); DI != E; ++DI) {
1062
1063    // Get the set to update for this block
1064    ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
1065    lastSeenLoad.clear();
1066
1067    BasicBlock* BB = DI->getBlock();
1068
1069    // A block inherits AVAIL_OUT from its dominator
1070    if (DI->getIDom() != 0) {
1071      currAvail = availableOut[DI->getIDom()->getBlock()];
1072
1073      numChildrenVisited[DI->getIDom()]++;
1074
1075      if (numChildrenVisited[DI->getIDom()] == DI->getIDom()->getNumChildren()) {
1076        availableOut.erase(DI->getIDom()->getBlock());
1077        numChildrenVisited.erase(DI->getIDom());
1078      }
1079    }
1080
1081    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1082         BI != BE;) {
1083      changed_function |= processInstruction(BI, currAvail,
1084                                             lastSeenLoad, toErase);
1085      if (toErase.empty()) {
1086        ++BI;
1087        continue;
1088      }
1089
1090      // If we need some instructions deleted, do it now.
1091      NumGVNInstr += toErase.size();
1092
1093      // Avoid iterator invalidation.
1094      bool AtStart = BI == BB->begin();
1095      if (!AtStart)
1096        --BI;
1097
1098      for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(),
1099           E = toErase.end(); I != E; ++I)
1100        (*I)->eraseFromParent();
1101
1102      if (AtStart)
1103        BI = BB->begin();
1104      else
1105        ++BI;
1106
1107      toErase.clear();
1108    }
1109  }
1110
1111  return changed_function;
1112}
1113