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