GVN.cpp revision 7cdd9ee088343026dd79b4b35da293a6d49d7044 
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// Note that this pass does the value numbering itself, it does not use the
14// ValueNumbering analysis passes.
15//
16//===----------------------------------------------------------------------===//
17
18#define DEBUG_TYPE "gvn"
19#include "llvm/Transforms/Scalar.h"
20#include "llvm/BasicBlock.h"
21#include "llvm/Constants.h"
22#include "llvm/DerivedTypes.h"
23#include "llvm/Function.h"
24#include "llvm/Instructions.h"
25#include "llvm/Value.h"
26#include "llvm/ADT/DenseMap.h"
27#include "llvm/ADT/DepthFirstIterator.h"
28#include "llvm/ADT/SmallPtrSet.h"
29#include "llvm/ADT/SmallVector.h"
30#include "llvm/ADT/Statistic.h"
31#include "llvm/Analysis/Dominators.h"
32#include "llvm/Analysis/AliasAnalysis.h"
33#include "llvm/Analysis/MemoryDependenceAnalysis.h"
34#include "llvm/Support/CFG.h"
35#include "llvm/Support/CommandLine.h"
36#include "llvm/Support/Compiler.h"
37#include "llvm/Support/Debug.h"
38#include "llvm/Transforms/Utils/BasicBlockUtils.h"
39#include <cstdio>
40using namespace llvm;
41
42STATISTIC(NumGVNInstr, "Number of instructions deleted");
43STATISTIC(NumGVNLoad, "Number of loads deleted");
44STATISTIC(NumGVNPRE, "Number of instructions PRE'd");
45STATISTIC(NumGVNBlocks, "Number of blocks merged");
46
47static cl::opt<bool> EnablePRE("enable-pre",
48                               cl::init(true), cl::Hidden);
49
50//===----------------------------------------------------------------------===//
51//                         ValueTable Class
52//===----------------------------------------------------------------------===//
53
54/// This class holds the mapping between values and value numbers.  It is used
55/// as an efficient mechanism to determine the expression-wise equivalence of
56/// two values.
57namespace {
58  struct VISIBILITY_HIDDEN Expression {
59    enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
60                            FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
61                            ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
62                            ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
63                            FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
64                            FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
65                            FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
66                            SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
67                            FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
68                            PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, CONSTANT,
69                            EMPTY, TOMBSTONE };
70
71    ExpressionOpcode opcode;
72    const Type* type;
73    uint32_t firstVN;
74    uint32_t secondVN;
75    uint32_t thirdVN;
76    SmallVector<uint32_t, 4> varargs;
77    Value* function;
78
79    Expression() { }
80    Expression(ExpressionOpcode o) : opcode(o) { }
81
82    bool operator==(const Expression &other) const {
83      if (opcode != other.opcode)
84        return false;
85      else if (opcode == EMPTY || opcode == TOMBSTONE)
86        return true;
87      else if (type != other.type)
88        return false;
89      else if (function != other.function)
90        return false;
91      else if (firstVN != other.firstVN)
92        return false;
93      else if (secondVN != other.secondVN)
94        return false;
95      else if (thirdVN != other.thirdVN)
96        return false;
97      else {
98        if (varargs.size() != other.varargs.size())
99          return false;
100
101        for (size_t i = 0; i < varargs.size(); ++i)
102          if (varargs[i] != other.varargs[i])
103            return false;
104
105        return true;
106      }
107    }
108
109    bool operator!=(const Expression &other) const {
110      if (opcode != other.opcode)
111        return true;
112      else if (opcode == EMPTY || opcode == TOMBSTONE)
113        return false;
114      else if (type != other.type)
115        return true;
116      else if (function != other.function)
117        return true;
118      else if (firstVN != other.firstVN)
119        return true;
120      else if (secondVN != other.secondVN)
121        return true;
122      else if (thirdVN != other.thirdVN)
123        return true;
124      else {
125        if (varargs.size() != other.varargs.size())
126          return true;
127
128        for (size_t i = 0; i < varargs.size(); ++i)
129          if (varargs[i] != other.varargs[i])
130            return true;
131
132          return false;
133      }
134    }
135  };
136
137  class VISIBILITY_HIDDEN ValueTable {
138    private:
139      DenseMap<Value*, uint32_t> valueNumbering;
140      DenseMap<Expression, uint32_t> expressionNumbering;
141      AliasAnalysis* AA;
142      MemoryDependenceAnalysis* MD;
143      DominatorTree* DT;
144
145      uint32_t nextValueNumber;
146
147      Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
148      Expression::ExpressionOpcode getOpcode(CmpInst* C);
149      Expression::ExpressionOpcode getOpcode(CastInst* C);
150      Expression create_expression(BinaryOperator* BO);
151      Expression create_expression(CmpInst* C);
152      Expression create_expression(ShuffleVectorInst* V);
153      Expression create_expression(ExtractElementInst* C);
154      Expression create_expression(InsertElementInst* V);
155      Expression create_expression(SelectInst* V);
156      Expression create_expression(CastInst* C);
157      Expression create_expression(GetElementPtrInst* G);
158      Expression create_expression(CallInst* C);
159      Expression create_expression(Constant* C);
160    public:
161      ValueTable() : nextValueNumber(1) { }
162      uint32_t lookup_or_add(Value* V);
163      uint32_t lookup(Value* V) const;
164      void add(Value* V, uint32_t num);
165      void clear();
166      void erase(Value* v);
167      unsigned size();
168      void setAliasAnalysis(AliasAnalysis* A) { AA = A; }
169      void setMemDep(MemoryDependenceAnalysis* M) { MD = M; }
170      void setDomTree(DominatorTree* D) { DT = D; }
171      uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
172  };
173}
174
175namespace llvm {
176template <> struct DenseMapInfo<Expression> {
177  static inline Expression getEmptyKey() {
178    return Expression(Expression::EMPTY);
179  }
180
181  static inline Expression getTombstoneKey() {
182    return Expression(Expression::TOMBSTONE);
183  }
184
185  static unsigned getHashValue(const Expression e) {
186    unsigned hash = e.opcode;
187
188    hash = e.firstVN + hash * 37;
189    hash = e.secondVN + hash * 37;
190    hash = e.thirdVN + hash * 37;
191
192    hash = ((unsigned)((uintptr_t)e.type >> 4) ^
193            (unsigned)((uintptr_t)e.type >> 9)) +
194           hash * 37;
195
196    for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
197         E = e.varargs.end(); I != E; ++I)
198      hash = *I + hash * 37;
199
200    hash = ((unsigned)((uintptr_t)e.function >> 4) ^
201            (unsigned)((uintptr_t)e.function >> 9)) +
202           hash * 37;
203
204    return hash;
205  }
206  static bool isEqual(const Expression &LHS, const Expression &RHS) {
207    return LHS == RHS;
208  }
209  static bool isPod() { return true; }
210};
211}
212
213//===----------------------------------------------------------------------===//
214//                     ValueTable Internal Functions
215//===----------------------------------------------------------------------===//
216Expression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) {
217  switch(BO->getOpcode()) {
218  default: // THIS SHOULD NEVER HAPPEN
219    assert(0 && "Binary operator with unknown opcode?");
220  case Instruction::Add:  return Expression::ADD;
221  case Instruction::Sub:  return Expression::SUB;
222  case Instruction::Mul:  return Expression::MUL;
223  case Instruction::UDiv: return Expression::UDIV;
224  case Instruction::SDiv: return Expression::SDIV;
225  case Instruction::FDiv: return Expression::FDIV;
226  case Instruction::URem: return Expression::UREM;
227  case Instruction::SRem: return Expression::SREM;
228  case Instruction::FRem: return Expression::FREM;
229  case Instruction::Shl:  return Expression::SHL;
230  case Instruction::LShr: return Expression::LSHR;
231  case Instruction::AShr: return Expression::ASHR;
232  case Instruction::And:  return Expression::AND;
233  case Instruction::Or:   return Expression::OR;
234  case Instruction::Xor:  return Expression::XOR;
235  }
236}
237
238Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
239  if (isa<ICmpInst>(C) || isa<VICmpInst>(C)) {
240    switch (C->getPredicate()) {
241    default:  // THIS SHOULD NEVER HAPPEN
242      assert(0 && "Comparison with unknown predicate?");
243    case ICmpInst::ICMP_EQ:  return Expression::ICMPEQ;
244    case ICmpInst::ICMP_NE:  return Expression::ICMPNE;
245    case ICmpInst::ICMP_UGT: return Expression::ICMPUGT;
246    case ICmpInst::ICMP_UGE: return Expression::ICMPUGE;
247    case ICmpInst::ICMP_ULT: return Expression::ICMPULT;
248    case ICmpInst::ICMP_ULE: return Expression::ICMPULE;
249    case ICmpInst::ICMP_SGT: return Expression::ICMPSGT;
250    case ICmpInst::ICMP_SGE: return Expression::ICMPSGE;
251    case ICmpInst::ICMP_SLT: return Expression::ICMPSLT;
252    case ICmpInst::ICMP_SLE: return Expression::ICMPSLE;
253    }
254  }
255  assert((isa<FCmpInst>(C) || isa<VFCmpInst>(C)) && "Unknown compare");
256  switch (C->getPredicate()) {
257  default: // THIS SHOULD NEVER HAPPEN
258    assert(0 && "Comparison with unknown predicate?");
259  case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ;
260  case FCmpInst::FCMP_OGT: return Expression::FCMPOGT;
261  case FCmpInst::FCMP_OGE: return Expression::FCMPOGE;
262  case FCmpInst::FCMP_OLT: return Expression::FCMPOLT;
263  case FCmpInst::FCMP_OLE: return Expression::FCMPOLE;
264  case FCmpInst::FCMP_ONE: return Expression::FCMPONE;
265  case FCmpInst::FCMP_ORD: return Expression::FCMPORD;
266  case FCmpInst::FCMP_UNO: return Expression::FCMPUNO;
267  case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ;
268  case FCmpInst::FCMP_UGT: return Expression::FCMPUGT;
269  case FCmpInst::FCMP_UGE: return Expression::FCMPUGE;
270  case FCmpInst::FCMP_ULT: return Expression::FCMPULT;
271  case FCmpInst::FCMP_ULE: return Expression::FCMPULE;
272  case FCmpInst::FCMP_UNE: return Expression::FCMPUNE;
273  }
274}
275
276Expression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) {
277  switch(C->getOpcode()) {
278  default: // THIS SHOULD NEVER HAPPEN
279    assert(0 && "Cast operator with unknown opcode?");
280  case Instruction::Trunc:    return Expression::TRUNC;
281  case Instruction::ZExt:     return Expression::ZEXT;
282  case Instruction::SExt:     return Expression::SEXT;
283  case Instruction::FPToUI:   return Expression::FPTOUI;
284  case Instruction::FPToSI:   return Expression::FPTOSI;
285  case Instruction::UIToFP:   return Expression::UITOFP;
286  case Instruction::SIToFP:   return Expression::SITOFP;
287  case Instruction::FPTrunc:  return Expression::FPTRUNC;
288  case Instruction::FPExt:    return Expression::FPEXT;
289  case Instruction::PtrToInt: return Expression::PTRTOINT;
290  case Instruction::IntToPtr: return Expression::INTTOPTR;
291  case Instruction::BitCast:  return Expression::BITCAST;
292  }
293}
294
295Expression ValueTable::create_expression(CallInst* C) {
296  Expression e;
297
298  e.type = C->getType();
299  e.firstVN = 0;
300  e.secondVN = 0;
301  e.thirdVN = 0;
302  e.function = C->getCalledFunction();
303  e.opcode = Expression::CALL;
304
305  for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end();
306       I != E; ++I)
307    e.varargs.push_back(lookup_or_add(*I));
308
309  return e;
310}
311
312Expression ValueTable::create_expression(BinaryOperator* BO) {
313  Expression e;
314
315  e.firstVN = lookup_or_add(BO->getOperand(0));
316  e.secondVN = lookup_or_add(BO->getOperand(1));
317  e.thirdVN = 0;
318  e.function = 0;
319  e.type = BO->getType();
320  e.opcode = getOpcode(BO);
321
322  return e;
323}
324
325Expression ValueTable::create_expression(CmpInst* C) {
326  Expression e;
327
328  e.firstVN = lookup_or_add(C->getOperand(0));
329  e.secondVN = lookup_or_add(C->getOperand(1));
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(CastInst* C) {
339  Expression e;
340
341  e.firstVN = lookup_or_add(C->getOperand(0));
342  e.secondVN = 0;
343  e.thirdVN = 0;
344  e.function = 0;
345  e.type = C->getType();
346  e.opcode = getOpcode(C);
347
348  return e;
349}
350
351Expression ValueTable::create_expression(ShuffleVectorInst* S) {
352  Expression e;
353
354  e.firstVN = lookup_or_add(S->getOperand(0));
355  e.secondVN = lookup_or_add(S->getOperand(1));
356  e.thirdVN = lookup_or_add(S->getOperand(2));
357  e.function = 0;
358  e.type = S->getType();
359  e.opcode = Expression::SHUFFLE;
360
361  return e;
362}
363
364Expression ValueTable::create_expression(ExtractElementInst* E) {
365  Expression e;
366
367  e.firstVN = lookup_or_add(E->getOperand(0));
368  e.secondVN = lookup_or_add(E->getOperand(1));
369  e.thirdVN = 0;
370  e.function = 0;
371  e.type = E->getType();
372  e.opcode = Expression::EXTRACT;
373
374  return e;
375}
376
377Expression ValueTable::create_expression(InsertElementInst* I) {
378  Expression e;
379
380  e.firstVN = lookup_or_add(I->getOperand(0));
381  e.secondVN = lookup_or_add(I->getOperand(1));
382  e.thirdVN = lookup_or_add(I->getOperand(2));
383  e.function = 0;
384  e.type = I->getType();
385  e.opcode = Expression::INSERT;
386
387  return e;
388}
389
390Expression ValueTable::create_expression(SelectInst* I) {
391  Expression e;
392
393  e.firstVN = lookup_or_add(I->getCondition());
394  e.secondVN = lookup_or_add(I->getTrueValue());
395  e.thirdVN = lookup_or_add(I->getFalseValue());
396  e.function = 0;
397  e.type = I->getType();
398  e.opcode = Expression::SELECT;
399
400  return e;
401}
402
403Expression ValueTable::create_expression(GetElementPtrInst* G) {
404  Expression e;
405
406  e.firstVN = lookup_or_add(G->getPointerOperand());
407  e.secondVN = 0;
408  e.thirdVN = 0;
409  e.function = 0;
410  e.type = G->getType();
411  e.opcode = Expression::GEP;
412
413  for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
414       I != E; ++I)
415    e.varargs.push_back(lookup_or_add(*I));
416
417  return e;
418}
419
420//===----------------------------------------------------------------------===//
421//                     ValueTable External Functions
422//===----------------------------------------------------------------------===//
423
424/// add - Insert a value into the table with a specified value number.
425void ValueTable::add(Value* V, uint32_t num) {
426  valueNumbering.insert(std::make_pair(V, num));
427}
428
429/// lookup_or_add - Returns the value number for the specified value, assigning
430/// it a new number if it did not have one before.
431uint32_t ValueTable::lookup_or_add(Value* V) {
432  DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
433  if (VI != valueNumbering.end())
434    return VI->second;
435
436  if (CallInst* C = dyn_cast<CallInst>(V)) {
437    if (AA->doesNotAccessMemory(C)) {
438      Expression e = create_expression(C);
439
440      DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
441      if (EI != expressionNumbering.end()) {
442        valueNumbering.insert(std::make_pair(V, EI->second));
443        return EI->second;
444      } else {
445        expressionNumbering.insert(std::make_pair(e, nextValueNumber));
446        valueNumbering.insert(std::make_pair(V, nextValueNumber));
447
448        return nextValueNumber++;
449      }
450    } else if (AA->onlyReadsMemory(C)) {
451      Expression e = create_expression(C);
452
453      if (expressionNumbering.find(e) == expressionNumbering.end()) {
454        expressionNumbering.insert(std::make_pair(e, nextValueNumber));
455        valueNumbering.insert(std::make_pair(V, nextValueNumber));
456        return nextValueNumber++;
457      }
458
459      Instruction* local_dep = MD->getDependency(C);
460
461      if (local_dep == MemoryDependenceAnalysis::None) {
462        valueNumbering.insert(std::make_pair(V, nextValueNumber));
463        return nextValueNumber++;
464      } else if (local_dep != MemoryDependenceAnalysis::NonLocal) {
465        if (!isa<CallInst>(local_dep)) {
466          valueNumbering.insert(std::make_pair(V, nextValueNumber));
467          return nextValueNumber++;
468        }
469
470        CallInst* local_cdep = cast<CallInst>(local_dep);
471
472        if (local_cdep->getCalledFunction() != C->getCalledFunction() ||
473            local_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(local_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 = lookup_or_add(local_cdep);
490          valueNumbering.insert(std::make_pair(V, v));
491          return v;
492        }
493      }
494
495
496      DenseMap<BasicBlock*, Value*> deps;
497      MD->getNonLocalDependency(C, deps);
498      CallInst* cdep = 0;
499
500      for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(),
501           E = deps.end(); I != E; ++I) {
502        if (I->second == MemoryDependenceAnalysis::None) {
503          valueNumbering.insert(std::make_pair(V, nextValueNumber));
504
505          return nextValueNumber++;
506        } else if (I->second != MemoryDependenceAnalysis::NonLocal) {
507          if (DT->properlyDominates(I->first, C->getParent())) {
508            if (CallInst* CD = dyn_cast<CallInst>(I->second))
509              cdep = CD;
510            else {
511              valueNumbering.insert(std::make_pair(V, nextValueNumber));
512              return nextValueNumber++;
513            }
514          } else {
515            valueNumbering.insert(std::make_pair(V, nextValueNumber));
516            return nextValueNumber++;
517          }
518        }
519      }
520
521      if (!cdep) {
522        valueNumbering.insert(std::make_pair(V, nextValueNumber));
523        return nextValueNumber++;
524      }
525
526      if (cdep->getCalledFunction() != C->getCalledFunction() ||
527          cdep->getNumOperands() != C->getNumOperands()) {
528        valueNumbering.insert(std::make_pair(V, nextValueNumber));
529        return nextValueNumber++;
530      } else if (!C->getCalledFunction()) {
531        valueNumbering.insert(std::make_pair(V, nextValueNumber));
532        return nextValueNumber++;
533      } else {
534        for (unsigned i = 1; i < C->getNumOperands(); ++i) {
535          uint32_t c_vn = lookup_or_add(C->getOperand(i));
536          uint32_t cd_vn = lookup_or_add(cdep->getOperand(i));
537          if (c_vn != cd_vn) {
538            valueNumbering.insert(std::make_pair(V, nextValueNumber));
539            return nextValueNumber++;
540          }
541        }
542
543        uint32_t v = lookup_or_add(cdep);
544        valueNumbering.insert(std::make_pair(V, v));
545        return v;
546      }
547
548    } else {
549      valueNumbering.insert(std::make_pair(V, nextValueNumber));
550      return nextValueNumber++;
551    }
552  } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
553    Expression e = create_expression(BO);
554
555    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
556    if (EI != expressionNumbering.end()) {
557      valueNumbering.insert(std::make_pair(V, EI->second));
558      return EI->second;
559    } else {
560      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
561      valueNumbering.insert(std::make_pair(V, nextValueNumber));
562
563      return nextValueNumber++;
564    }
565  } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
566    Expression e = create_expression(C);
567
568    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
569    if (EI != expressionNumbering.end()) {
570      valueNumbering.insert(std::make_pair(V, EI->second));
571      return EI->second;
572    } else {
573      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
574      valueNumbering.insert(std::make_pair(V, nextValueNumber));
575
576      return nextValueNumber++;
577    }
578  } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
579    Expression e = create_expression(U);
580
581    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
582    if (EI != expressionNumbering.end()) {
583      valueNumbering.insert(std::make_pair(V, EI->second));
584      return EI->second;
585    } else {
586      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
587      valueNumbering.insert(std::make_pair(V, nextValueNumber));
588
589      return nextValueNumber++;
590    }
591  } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
592    Expression e = create_expression(U);
593
594    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
595    if (EI != expressionNumbering.end()) {
596      valueNumbering.insert(std::make_pair(V, EI->second));
597      return EI->second;
598    } else {
599      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
600      valueNumbering.insert(std::make_pair(V, nextValueNumber));
601
602      return nextValueNumber++;
603    }
604  } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
605    Expression e = create_expression(U);
606
607    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
608    if (EI != expressionNumbering.end()) {
609      valueNumbering.insert(std::make_pair(V, EI->second));
610      return EI->second;
611    } else {
612      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
613      valueNumbering.insert(std::make_pair(V, nextValueNumber));
614
615      return nextValueNumber++;
616    }
617  } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
618    Expression e = create_expression(U);
619
620    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
621    if (EI != expressionNumbering.end()) {
622      valueNumbering.insert(std::make_pair(V, EI->second));
623      return EI->second;
624    } else {
625      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
626      valueNumbering.insert(std::make_pair(V, nextValueNumber));
627
628      return nextValueNumber++;
629    }
630  } else if (CastInst* U = dyn_cast<CastInst>(V)) {
631    Expression e = create_expression(U);
632
633    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
634    if (EI != expressionNumbering.end()) {
635      valueNumbering.insert(std::make_pair(V, EI->second));
636      return EI->second;
637    } else {
638      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
639      valueNumbering.insert(std::make_pair(V, nextValueNumber));
640
641      return nextValueNumber++;
642    }
643  } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
644    Expression e = create_expression(U);
645
646    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
647    if (EI != expressionNumbering.end()) {
648      valueNumbering.insert(std::make_pair(V, EI->second));
649      return EI->second;
650    } else {
651      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
652      valueNumbering.insert(std::make_pair(V, nextValueNumber));
653
654      return nextValueNumber++;
655    }
656  } else {
657    valueNumbering.insert(std::make_pair(V, nextValueNumber));
658    return nextValueNumber++;
659  }
660}
661
662/// lookup - Returns the value number of the specified value. Fails if
663/// the value has not yet been numbered.
664uint32_t ValueTable::lookup(Value* V) const {
665  DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
666  assert(VI != valueNumbering.end() && "Value not numbered?");
667  return VI->second;
668}
669
670/// clear - Remove all entries from the ValueTable
671void ValueTable::clear() {
672  valueNumbering.clear();
673  expressionNumbering.clear();
674  nextValueNumber = 1;
675}
676
677/// erase - Remove a value from the value numbering
678void ValueTable::erase(Value* V) {
679  valueNumbering.erase(V);
680}
681
682//===----------------------------------------------------------------------===//
683//                         GVN Pass
684//===----------------------------------------------------------------------===//
685
686namespace {
687  struct VISIBILITY_HIDDEN ValueNumberScope {
688    ValueNumberScope* parent;
689    DenseMap<uint32_t, Value*> table;
690
691    ValueNumberScope(ValueNumberScope* p) : parent(p) { }
692  };
693}
694
695namespace {
696
697  class VISIBILITY_HIDDEN GVN : public FunctionPass {
698    bool runOnFunction(Function &F);
699  public:
700    static char ID; // Pass identification, replacement for typeid
701    GVN() : FunctionPass(&ID) { }
702
703  private:
704    ValueTable VN;
705    DenseMap<BasicBlock*, ValueNumberScope*> localAvail;
706
707    typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType;
708    PhiMapType phiMap;
709
710
711    // This transformation requires dominator postdominator info
712    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
713      AU.addRequired<DominatorTree>();
714      AU.addRequired<MemoryDependenceAnalysis>();
715      AU.addRequired<AliasAnalysis>();
716
717      AU.addPreserved<DominatorTree>();
718      AU.addPreserved<AliasAnalysis>();
719    }
720
721    // Helper fuctions
722    // FIXME: eliminate or document these better
723    bool processLoad(LoadInst* L,
724                     DenseMap<Value*, LoadInst*> &lastLoad,
725                     SmallVectorImpl<Instruction*> &toErase);
726    bool processInstruction(Instruction* I,
727                            DenseMap<Value*, LoadInst*>& lastSeenLoad,
728                            SmallVectorImpl<Instruction*> &toErase);
729    bool processNonLocalLoad(LoadInst* L,
730                             SmallVectorImpl<Instruction*> &toErase);
731    bool processBlock(DomTreeNode* DTN);
732    Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig,
733                            DenseMap<BasicBlock*, Value*> &Phis,
734                            bool top_level = false);
735    void dump(DenseMap<uint32_t, Value*>& d);
736    bool iterateOnFunction(Function &F);
737    Value* CollapsePhi(PHINode* p);
738    bool isSafeReplacement(PHINode* p, Instruction* inst);
739    bool performPRE(Function& F);
740    Value* lookupNumber(BasicBlock* BB, uint32_t num);
741    bool mergeBlockIntoPredecessor(BasicBlock* BB);
742    void cleanupGlobalSets();
743  };
744
745  char GVN::ID = 0;
746}
747
748// createGVNPass - The public interface to this file...
749FunctionPass *llvm::createGVNPass() { return new GVN(); }
750
751static RegisterPass<GVN> X("gvn",
752                           "Global Value Numbering");
753
754void GVN::dump(DenseMap<uint32_t, Value*>& d) {
755  printf("{\n");
756  for (DenseMap<uint32_t, Value*>::iterator I = d.begin(),
757       E = d.end(); I != E; ++I) {
758      printf("%d\n", I->first);
759      I->second->dump();
760  }
761  printf("}\n");
762}
763
764Value* GVN::CollapsePhi(PHINode* p) {
765  DominatorTree &DT = getAnalysis<DominatorTree>();
766  Value* constVal = p->hasConstantValue();
767
768  if (!constVal) return 0;
769
770  Instruction* inst = dyn_cast<Instruction>(constVal);
771  if (!inst)
772    return constVal;
773
774  if (DT.dominates(inst, p))
775    if (isSafeReplacement(p, inst))
776      return inst;
777  return 0;
778}
779
780bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) {
781  if (!isa<PHINode>(inst))
782    return true;
783
784  for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end();
785       UI != E; ++UI)
786    if (PHINode* use_phi = dyn_cast<PHINode>(UI))
787      if (use_phi->getParent() == inst->getParent())
788        return false;
789
790  return true;
791}
792
793/// GetValueForBlock - Get the value to use within the specified basic block.
794/// available values are in Phis.
795Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
796                             DenseMap<BasicBlock*, Value*> &Phis,
797                             bool top_level) {
798
799  // If we have already computed this value, return the previously computed val.
800  DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB);
801  if (V != Phis.end() && !top_level) return V->second;
802
803  // If the block is unreachable, just return undef, since this path
804  // can't actually occur at runtime.
805  if (!getAnalysis<DominatorTree>().isReachableFromEntry(BB))
806    return Phis[BB] = UndefValue::get(orig->getType());
807
808  BasicBlock* singlePred = BB->getSinglePredecessor();
809  if (singlePred) {
810    Value *ret = GetValueForBlock(singlePred, orig, Phis);
811    Phis[BB] = ret;
812    return ret;
813  }
814
815  // Otherwise, the idom is the loop, so we need to insert a PHI node.  Do so
816  // now, then get values to fill in the incoming values for the PHI.
817  PHINode *PN = PHINode::Create(orig->getType(), orig->getName()+".rle",
818                                BB->begin());
819  PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB)));
820
821  if (Phis.count(BB) == 0)
822    Phis.insert(std::make_pair(BB, PN));
823
824  // Fill in the incoming values for the block.
825  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
826    Value* val = GetValueForBlock(*PI, orig, Phis);
827    PN->addIncoming(val, *PI);
828  }
829
830  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
831  AA.copyValue(orig, PN);
832
833  // Attempt to collapse PHI nodes that are trivially redundant
834  Value* v = CollapsePhi(PN);
835  if (!v) {
836    // Cache our phi construction results
837    phiMap[orig->getPointerOperand()].insert(PN);
838    return PN;
839  }
840
841  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
842
843  MD.removeInstruction(PN);
844  PN->replaceAllUsesWith(v);
845
846  for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
847       E = Phis.end(); I != E; ++I)
848    if (I->second == PN)
849      I->second = v;
850
851  PN->eraseFromParent();
852
853  Phis[BB] = v;
854  return v;
855}
856
857/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are
858/// non-local by performing PHI construction.
859bool GVN::processNonLocalLoad(LoadInst* L,
860                              SmallVectorImpl<Instruction*> &toErase) {
861  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
862
863  // Find the non-local dependencies of the load
864  DenseMap<BasicBlock*, Value*> deps;
865  MD.getNonLocalDependency(L, deps);
866
867  // If we had to process more than one hundred blocks to find the
868  // dependencies, this load isn't worth worrying about.  Optimizing
869  // it will be too expensive.
870  if (deps.size() > 100)
871    return false;
872
873  DenseMap<BasicBlock*, Value*> repl;
874
875  // Filter out useless results (non-locals, etc)
876  for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end();
877       I != E; ++I) {
878    if (I->second == MemoryDependenceAnalysis::None)
879      return false;
880
881    if (I->second == MemoryDependenceAnalysis::NonLocal)
882      continue;
883
884    if (StoreInst* S = dyn_cast<StoreInst>(I->second)) {
885      if (S->getPointerOperand() != L->getPointerOperand())
886        return false;
887      repl[I->first] = S->getOperand(0);
888    } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) {
889      if (LD->getPointerOperand() != L->getPointerOperand())
890        return false;
891      repl[I->first] = LD;
892    } else {
893      return false;
894    }
895  }
896
897  // Use cached PHI construction information from previous runs
898  SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()];
899  for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end();
900       I != E; ++I) {
901    if ((*I)->getParent() == L->getParent()) {
902      MD.removeInstruction(L);
903      L->replaceAllUsesWith(*I);
904      toErase.push_back(L);
905      NumGVNLoad++;
906      return true;
907    }
908
909    repl.insert(std::make_pair((*I)->getParent(), *I));
910  }
911
912  // Perform PHI construction
913  SmallPtrSet<BasicBlock*, 4> visited;
914  Value* v = GetValueForBlock(L->getParent(), L, repl, true);
915
916  MD.removeInstruction(L);
917  L->replaceAllUsesWith(v);
918  toErase.push_back(L);
919  NumGVNLoad++;
920
921  return true;
922}
923
924/// processLoad - Attempt to eliminate a load, first by eliminating it
925/// locally, and then attempting non-local elimination if that fails.
926bool GVN::processLoad(LoadInst *L, DenseMap<Value*, LoadInst*> &lastLoad,
927                      SmallVectorImpl<Instruction*> &toErase) {
928  if (L->isVolatile()) {
929    lastLoad[L->getPointerOperand()] = L;
930    return false;
931  }
932
933  Value* pointer = L->getPointerOperand();
934  LoadInst*& last = lastLoad[pointer];
935
936  // ... to a pointer that has been loaded from before...
937  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
938  bool removedNonLocal = false;
939  Instruction* dep = MD.getDependency(L);
940  if (dep == MemoryDependenceAnalysis::NonLocal &&
941      L->getParent() != &L->getParent()->getParent()->getEntryBlock()) {
942    removedNonLocal = processNonLocalLoad(L, toErase);
943
944    if (!removedNonLocal)
945      last = L;
946
947    return removedNonLocal;
948  }
949
950
951  bool deletedLoad = false;
952
953  // Walk up the dependency chain until we either find
954  // a dependency we can use, or we can't walk any further
955  while (dep != MemoryDependenceAnalysis::None &&
956         dep != MemoryDependenceAnalysis::NonLocal &&
957         (isa<LoadInst>(dep) || isa<StoreInst>(dep))) {
958    // ... that depends on a store ...
959    if (StoreInst* S = dyn_cast<StoreInst>(dep)) {
960      if (S->getPointerOperand() == pointer) {
961        // Remove it!
962        MD.removeInstruction(L);
963
964        L->replaceAllUsesWith(S->getOperand(0));
965        toErase.push_back(L);
966        deletedLoad = true;
967        NumGVNLoad++;
968      }
969
970      // Whether we removed it or not, we can't
971      // go any further
972      break;
973    } else if (!last) {
974      // If we don't depend on a store, and we haven't
975      // been loaded before, bail.
976      break;
977    } else if (dep == last) {
978      // Remove it!
979      MD.removeInstruction(L);
980
981      L->replaceAllUsesWith(last);
982      toErase.push_back(L);
983      deletedLoad = true;
984      NumGVNLoad++;
985
986      break;
987    } else {
988      dep = MD.getDependency(L, dep);
989    }
990  }
991
992  if (dep != MemoryDependenceAnalysis::None &&
993      dep != MemoryDependenceAnalysis::NonLocal &&
994      isa<AllocationInst>(dep)) {
995    // Check that this load is actually from the
996    // allocation we found
997    if (L->getOperand(0)->getUnderlyingObject() == dep) {
998      // If this load depends directly on an allocation, there isn't
999      // anything stored there; therefore, we can optimize this load
1000      // to undef.
1001      MD.removeInstruction(L);
1002
1003      L->replaceAllUsesWith(UndefValue::get(L->getType()));
1004      toErase.push_back(L);
1005      deletedLoad = true;
1006      NumGVNLoad++;
1007    }
1008  }
1009
1010  if (!deletedLoad)
1011    last = L;
1012
1013  return deletedLoad;
1014}
1015
1016Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) {
1017  DenseMap<BasicBlock*, ValueNumberScope*>::iterator I = localAvail.find(BB);
1018  if (I == localAvail.end())
1019    return 0;
1020
1021  ValueNumberScope* locals = I->second;
1022
1023  while (locals) {
1024    DenseMap<uint32_t, Value*>::iterator I = locals->table.find(num);
1025    if (I != locals->table.end())
1026      return I->second;
1027    else
1028      locals = locals->parent;
1029  }
1030
1031  return 0;
1032}
1033
1034/// processInstruction - When calculating availability, handle an instruction
1035/// by inserting it into the appropriate sets
1036bool GVN::processInstruction(Instruction *I,
1037                             DenseMap<Value*, LoadInst*> &lastSeenLoad,
1038                             SmallVectorImpl<Instruction*> &toErase) {
1039  if (LoadInst* L = dyn_cast<LoadInst>(I)) {
1040    bool changed = processLoad(L, lastSeenLoad, toErase);
1041
1042    if (!changed) {
1043      unsigned num = VN.lookup_or_add(L);
1044      localAvail[I->getParent()]->table.insert(std::make_pair(num, L));
1045    }
1046
1047    return changed;
1048  }
1049
1050  uint32_t nextNum = VN.getNextUnusedValueNumber();
1051  unsigned num = VN.lookup_or_add(I);
1052
1053  // Allocations are always uniquely numbered, so we can save time and memory
1054  // by fast failing them.
1055  if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) {
1056    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
1057    return false;
1058  }
1059
1060  // Collapse PHI nodes
1061  if (PHINode* p = dyn_cast<PHINode>(I)) {
1062    Value* constVal = CollapsePhi(p);
1063
1064    if (constVal) {
1065      for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end();
1066           PI != PE; ++PI)
1067        if (PI->second.count(p))
1068          PI->second.erase(p);
1069
1070      p->replaceAllUsesWith(constVal);
1071      toErase.push_back(p);
1072    } else {
1073      localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
1074    }
1075
1076  // If the number we were assigned was a brand new VN, then we don't
1077  // need to do a lookup to see if the number already exists
1078  // somewhere in the domtree: it can't!
1079  } else if (num == nextNum) {
1080    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
1081
1082  // Perform value-number based elimination
1083  } else if (Value* repl = lookupNumber(I->getParent(), num)) {
1084    // Remove it!
1085    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1086    MD.removeInstruction(I);
1087
1088    VN.erase(I);
1089    I->replaceAllUsesWith(repl);
1090    toErase.push_back(I);
1091    return true;
1092  } else {
1093    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
1094  }
1095
1096  return false;
1097}
1098
1099// GVN::runOnFunction - This is the main transformation entry point for a
1100// function.
1101//
1102bool GVN::runOnFunction(Function& F) {
1103  VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>());
1104  VN.setMemDep(&getAnalysis<MemoryDependenceAnalysis>());
1105  VN.setDomTree(&getAnalysis<DominatorTree>());
1106
1107  bool changed = false;
1108  bool shouldContinue = true;
1109
1110  // Merge unconditional branches, allowing PRE to catch more
1111  // optimization opportunities.
1112  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) {
1113    BasicBlock* BB = FI;
1114    ++FI;
1115    bool removedBlock = MergeBlockIntoPredecessor(BB, this);
1116    if (removedBlock) NumGVNBlocks++;
1117
1118    changed |= removedBlock;
1119  }
1120
1121  while (shouldContinue) {
1122    shouldContinue = iterateOnFunction(F);
1123    changed |= shouldContinue;
1124  }
1125
1126  if (EnablePRE) {
1127    bool PREChanged = true;
1128    while (PREChanged) {
1129      PREChanged = performPRE(F);
1130      changed |= PREChanged;
1131    }
1132  }
1133
1134  cleanupGlobalSets();
1135
1136  return changed;
1137}
1138
1139
1140bool GVN::processBlock(DomTreeNode* DTN) {
1141  BasicBlock* BB = DTN->getBlock();
1142
1143  SmallVector<Instruction*, 8> toErase;
1144  DenseMap<Value*, LoadInst*> lastSeenLoad;
1145  bool changed_function = false;
1146
1147  if (DTN->getIDom())
1148    localAvail[BB] =
1149                  new ValueNumberScope(localAvail[DTN->getIDom()->getBlock()]);
1150  else
1151    localAvail[BB] = new ValueNumberScope(0);
1152
1153  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1154       BI != BE;) {
1155    changed_function |= processInstruction(BI, lastSeenLoad, toErase);
1156    if (toErase.empty()) {
1157      ++BI;
1158      continue;
1159    }
1160
1161    // If we need some instructions deleted, do it now.
1162    NumGVNInstr += toErase.size();
1163
1164    // Avoid iterator invalidation.
1165    bool AtStart = BI == BB->begin();
1166    if (!AtStart)
1167      --BI;
1168
1169    for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(),
1170         E = toErase.end(); I != E; ++I)
1171      (*I)->eraseFromParent();
1172
1173    if (AtStart)
1174      BI = BB->begin();
1175    else
1176      ++BI;
1177
1178    toErase.clear();
1179  }
1180
1181  return changed_function;
1182}
1183
1184/// performPRE - Perform a purely local form of PRE that looks for diamond
1185/// control flow patterns and attempts to perform simple PRE at the join point.
1186bool GVN::performPRE(Function& F) {
1187  bool changed = false;
1188  SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit;
1189  for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()),
1190       DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) {
1191    BasicBlock* CurrentBlock = *DI;
1192
1193    // Nothing to PRE in the entry block.
1194    if (CurrentBlock == &F.getEntryBlock()) continue;
1195
1196    for (BasicBlock::iterator BI = CurrentBlock->begin(),
1197         BE = CurrentBlock->end(); BI != BE; ) {
1198      if (isa<AllocationInst>(BI) || isa<TerminatorInst>(BI) ||
1199          isa<PHINode>(BI) || BI->mayReadFromMemory() ||
1200          BI->mayWriteToMemory()) {
1201        BI++;
1202        continue;
1203      }
1204
1205      uint32_t valno = VN.lookup(BI);
1206
1207      // Look for the predecessors for PRE opportunities.  We're
1208      // only trying to solve the basic diamond case, where
1209      // a value is computed in the successor and one predecessor,
1210      // but not the other.  We also explicitly disallow cases
1211      // where the successor is its own predecessor, because they're
1212      // more complicated to get right.
1213      unsigned numWith = 0;
1214      unsigned numWithout = 0;
1215      BasicBlock* PREPred = 0;
1216      DenseMap<BasicBlock*, Value*> predMap;
1217      for (pred_iterator PI = pred_begin(CurrentBlock),
1218           PE = pred_end(CurrentBlock); PI != PE; ++PI) {
1219        // We're not interested in PRE where the block is its
1220        // own predecessor, on in blocks with predecessors
1221        // that are not reachable.
1222        if (*PI == CurrentBlock) {
1223          numWithout = 2;
1224          break;
1225        } else if (!localAvail.count(*PI))  {
1226          numWithout = 2;
1227          break;
1228        }
1229
1230        DenseMap<uint32_t, Value*>::iterator predV =
1231                                            localAvail[*PI]->table.find(valno);
1232        if (predV == localAvail[*PI]->table.end()) {
1233          PREPred = *PI;
1234          numWithout++;
1235        } else if (predV->second == BI) {
1236          numWithout = 2;
1237        } else {
1238          predMap[*PI] = predV->second;
1239          numWith++;
1240        }
1241      }
1242
1243      // Don't do PRE when it might increase code size, i.e. when
1244      // we would need to insert instructions in more than one pred.
1245      if (numWithout != 1 || numWith == 0) {
1246        BI++;
1247        continue;
1248      }
1249
1250      // We can't do PRE safely on a critical edge, so instead we schedule
1251      // the edge to be split and perform the PRE the next time we iterate
1252      // on the function.
1253      unsigned succNum = 0;
1254      for (unsigned i = 0, e = PREPred->getTerminator()->getNumSuccessors();
1255           i != e; ++i)
1256        if (PREPred->getTerminator()->getSuccessor(i) == CurrentBlock) {
1257          succNum = i;
1258          break;
1259        }
1260
1261      if (isCriticalEdge(PREPred->getTerminator(), succNum)) {
1262        toSplit.push_back(std::make_pair(PREPred->getTerminator(), succNum));
1263        changed = true;
1264        BI++;
1265        continue;
1266      }
1267
1268      // Instantiate the expression the in predecessor that lacked it.
1269      // Because we are going top-down through the block, all value numbers
1270      // will be available in the predecessor by the time we need them.  Any
1271      // that weren't original present will have been instantiated earlier
1272      // in this loop.
1273      Instruction* PREInstr = BI->clone();
1274      bool success = true;
1275      for (unsigned i = 0; i < BI->getNumOperands(); ++i) {
1276        Value* op = BI->getOperand(i);
1277        if (isa<Argument>(op) || isa<Constant>(op) || isa<GlobalValue>(op))
1278          PREInstr->setOperand(i, op);
1279        else {
1280          Value* V = lookupNumber(PREPred, VN.lookup(op));
1281          if (!V) {
1282            success = false;
1283            break;
1284          } else
1285            PREInstr->setOperand(i, V);
1286        }
1287      }
1288
1289      // Fail out if we encounter an operand that is not available in
1290      // the PRE predecessor.  This is typically because of loads which
1291      // are not value numbered precisely.
1292      if (!success) {
1293        delete PREInstr;
1294        BI++;
1295        continue;
1296      }
1297
1298      PREInstr->insertBefore(PREPred->getTerminator());
1299      PREInstr->setName(BI->getName() + ".pre");
1300      predMap[PREPred] = PREInstr;
1301      VN.add(PREInstr, valno);
1302      NumGVNPRE++;
1303
1304      // Update the availability map to include the new instruction.
1305      localAvail[PREPred]->table.insert(std::make_pair(valno, PREInstr));
1306
1307      // Create a PHI to make the value available in this block.
1308      PHINode* Phi = PHINode::Create(BI->getType(),
1309                                     BI->getName() + ".pre-phi",
1310                                     CurrentBlock->begin());
1311      for (pred_iterator PI = pred_begin(CurrentBlock),
1312           PE = pred_end(CurrentBlock); PI != PE; ++PI)
1313        Phi->addIncoming(predMap[*PI], *PI);
1314
1315      VN.add(Phi, valno);
1316      localAvail[CurrentBlock]->table[valno] = Phi;
1317
1318      BI->replaceAllUsesWith(Phi);
1319      VN.erase(BI);
1320
1321      Instruction* erase = BI;
1322      BI++;
1323      erase->eraseFromParent();
1324
1325      changed = true;
1326    }
1327  }
1328
1329  for (SmallVector<std::pair<TerminatorInst*, unsigned>, 4>::iterator
1330       I = toSplit.begin(), E = toSplit.end(); I != E; ++I)
1331    SplitCriticalEdge(I->first, I->second, this);
1332
1333  return changed || toSplit.size();
1334}
1335
1336// iterateOnFunction - Executes one iteration of GVN
1337bool GVN::iterateOnFunction(Function &F) {
1338  DominatorTree &DT = getAnalysis<DominatorTree>();
1339
1340  cleanupGlobalSets();
1341
1342  // Top-down walk of the dominator tree
1343  bool changed = false;
1344  for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1345       DE = df_end(DT.getRootNode()); DI != DE; ++DI)
1346    changed |= processBlock(*DI);
1347
1348  return changed;
1349}
1350
1351void GVN::cleanupGlobalSets() {
1352  VN.clear();
1353  phiMap.clear();
1354
1355  for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator
1356       I = localAvail.begin(), E = localAvail.end(); I != E; ++I)
1357    delete I->second;
1358  localAvail.clear();
1359}
1360