GVN.cpp revision 237a8287454389a5b940e18c1efb2201fc443208 
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      MemDepResult local_dep = MD->getDependency(C);
460
461      if (local_dep.isNone()) {
462        valueNumbering.insert(std::make_pair(V, nextValueNumber));
463        return nextValueNumber++;
464      } else if (Instruction *LocalDepInst = local_dep.getInst()) {
465        // FIXME: INDENT PROPERLY!
466        if (!isa<CallInst>(LocalDepInst)) {
467          valueNumbering.insert(std::make_pair(V, nextValueNumber));
468          return nextValueNumber++;
469        }
470
471        CallInst* local_cdep = cast<CallInst>(LocalDepInst);
472
473        // FIXME: INDENT PROPERLY.
474        if (local_cdep->getCalledFunction() != C->getCalledFunction() ||
475            local_cdep->getNumOperands() != C->getNumOperands()) {
476          valueNumbering.insert(std::make_pair(V, nextValueNumber));
477          return nextValueNumber++;
478        } else if (!C->getCalledFunction()) {
479          valueNumbering.insert(std::make_pair(V, nextValueNumber));
480          return nextValueNumber++;
481        } else {
482          for (unsigned i = 1; i < C->getNumOperands(); ++i) {
483            uint32_t c_vn = lookup_or_add(C->getOperand(i));
484            uint32_t cd_vn = lookup_or_add(local_cdep->getOperand(i));
485            if (c_vn != cd_vn) {
486              valueNumbering.insert(std::make_pair(V, nextValueNumber));
487              return nextValueNumber++;
488            }
489          }
490
491          uint32_t v = lookup_or_add(local_cdep);
492          valueNumbering.insert(std::make_pair(V, v));
493          return v;
494        }
495      }
496
497
498      SmallVector<std::pair<BasicBlock*, MemDepResult>, 32> deps;
499      MD->getNonLocalDependency(C, deps);
500      CallInst* cdep = 0;
501
502      for (SmallVector<std::pair<BasicBlock*, MemDepResult>, 32>
503             ::iterator I = deps.begin(), E = deps.end(); I != E; ++I) {
504        if (I->second.isNone()) {
505          valueNumbering.insert(std::make_pair(V, nextValueNumber));
506
507          return nextValueNumber++;
508        } else if (Instruction *NonLocalDepInst = I->second.getInst()) {
509          // FIXME: INDENT PROPERLY
510          // FIXME: All duplicated with non-local case.
511          if (cdep == 0 && DT->properlyDominates(I->first, C->getParent())) {
512            if (CallInst* CD = dyn_cast<CallInst>(NonLocalDepInst))
513              cdep = CD;
514            else {
515              valueNumbering.insert(std::make_pair(V, nextValueNumber));
516              return nextValueNumber++;
517            }
518          } else {
519            valueNumbering.insert(std::make_pair(V, nextValueNumber));
520            return nextValueNumber++;
521          }
522        }
523      }
524
525      if (!cdep) {
526        valueNumbering.insert(std::make_pair(V, nextValueNumber));
527        return nextValueNumber++;
528      }
529
530      // FIXME: THIS ISN'T SAFE: CONSIDER:
531      // X = strlen(str)
532      //   if (C)
533      //     str[0] = 1;
534      // Y = strlen(str)
535      // This doesn't guarantee all-paths availability!
536      if (cdep->getCalledFunction() != C->getCalledFunction() ||
537          cdep->getNumOperands() != C->getNumOperands()) {
538        valueNumbering.insert(std::make_pair(V, nextValueNumber));
539        return nextValueNumber++;
540      } else if (!C->getCalledFunction()) {
541        valueNumbering.insert(std::make_pair(V, nextValueNumber));
542        return nextValueNumber++;
543      } else {
544        for (unsigned i = 1; i < C->getNumOperands(); ++i) {
545          uint32_t c_vn = lookup_or_add(C->getOperand(i));
546          uint32_t cd_vn = lookup_or_add(cdep->getOperand(i));
547          if (c_vn != cd_vn) {
548            valueNumbering.insert(std::make_pair(V, nextValueNumber));
549            return nextValueNumber++;
550          }
551        }
552
553        uint32_t v = lookup_or_add(cdep);
554        valueNumbering.insert(std::make_pair(V, v));
555        return v;
556      }
557
558    } else {
559      valueNumbering.insert(std::make_pair(V, nextValueNumber));
560      return nextValueNumber++;
561    }
562  } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
563    Expression e = create_expression(BO);
564
565    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
566    if (EI != expressionNumbering.end()) {
567      valueNumbering.insert(std::make_pair(V, EI->second));
568      return EI->second;
569    } else {
570      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
571      valueNumbering.insert(std::make_pair(V, nextValueNumber));
572
573      return nextValueNumber++;
574    }
575  } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
576    Expression e = create_expression(C);
577
578    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
579    if (EI != expressionNumbering.end()) {
580      valueNumbering.insert(std::make_pair(V, EI->second));
581      return EI->second;
582    } else {
583      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
584      valueNumbering.insert(std::make_pair(V, nextValueNumber));
585
586      return nextValueNumber++;
587    }
588  } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
589    Expression e = create_expression(U);
590
591    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
592    if (EI != expressionNumbering.end()) {
593      valueNumbering.insert(std::make_pair(V, EI->second));
594      return EI->second;
595    } else {
596      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
597      valueNumbering.insert(std::make_pair(V, nextValueNumber));
598
599      return nextValueNumber++;
600    }
601  } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
602    Expression e = create_expression(U);
603
604    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
605    if (EI != expressionNumbering.end()) {
606      valueNumbering.insert(std::make_pair(V, EI->second));
607      return EI->second;
608    } else {
609      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
610      valueNumbering.insert(std::make_pair(V, nextValueNumber));
611
612      return nextValueNumber++;
613    }
614  } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
615    Expression e = create_expression(U);
616
617    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
618    if (EI != expressionNumbering.end()) {
619      valueNumbering.insert(std::make_pair(V, EI->second));
620      return EI->second;
621    } else {
622      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
623      valueNumbering.insert(std::make_pair(V, nextValueNumber));
624
625      return nextValueNumber++;
626    }
627  } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
628    Expression e = create_expression(U);
629
630    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
631    if (EI != expressionNumbering.end()) {
632      valueNumbering.insert(std::make_pair(V, EI->second));
633      return EI->second;
634    } else {
635      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
636      valueNumbering.insert(std::make_pair(V, nextValueNumber));
637
638      return nextValueNumber++;
639    }
640  } else if (CastInst* U = dyn_cast<CastInst>(V)) {
641    Expression e = create_expression(U);
642
643    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
644    if (EI != expressionNumbering.end()) {
645      valueNumbering.insert(std::make_pair(V, EI->second));
646      return EI->second;
647    } else {
648      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
649      valueNumbering.insert(std::make_pair(V, nextValueNumber));
650
651      return nextValueNumber++;
652    }
653  } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
654    Expression e = create_expression(U);
655
656    DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
657    if (EI != expressionNumbering.end()) {
658      valueNumbering.insert(std::make_pair(V, EI->second));
659      return EI->second;
660    } else {
661      expressionNumbering.insert(std::make_pair(e, nextValueNumber));
662      valueNumbering.insert(std::make_pair(V, nextValueNumber));
663
664      return nextValueNumber++;
665    }
666  } else {
667    valueNumbering.insert(std::make_pair(V, nextValueNumber));
668    return nextValueNumber++;
669  }
670}
671
672/// lookup - Returns the value number of the specified value. Fails if
673/// the value has not yet been numbered.
674uint32_t ValueTable::lookup(Value* V) const {
675  DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
676  assert(VI != valueNumbering.end() && "Value not numbered?");
677  return VI->second;
678}
679
680/// clear - Remove all entries from the ValueTable
681void ValueTable::clear() {
682  valueNumbering.clear();
683  expressionNumbering.clear();
684  nextValueNumber = 1;
685}
686
687/// erase - Remove a value from the value numbering
688void ValueTable::erase(Value* V) {
689  valueNumbering.erase(V);
690}
691
692//===----------------------------------------------------------------------===//
693//                         GVN Pass
694//===----------------------------------------------------------------------===//
695
696namespace {
697  struct VISIBILITY_HIDDEN ValueNumberScope {
698    ValueNumberScope* parent;
699    DenseMap<uint32_t, Value*> table;
700
701    ValueNumberScope(ValueNumberScope* p) : parent(p) { }
702  };
703}
704
705namespace {
706
707  class VISIBILITY_HIDDEN GVN : public FunctionPass {
708    bool runOnFunction(Function &F);
709  public:
710    static char ID; // Pass identification, replacement for typeid
711    GVN() : FunctionPass(&ID) { }
712
713  private:
714    ValueTable VN;
715    DenseMap<BasicBlock*, ValueNumberScope*> localAvail;
716
717    typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType;
718    PhiMapType phiMap;
719
720
721    // This transformation requires dominator postdominator info
722    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
723      AU.addRequired<DominatorTree>();
724      AU.addRequired<MemoryDependenceAnalysis>();
725      AU.addRequired<AliasAnalysis>();
726
727      AU.addPreserved<DominatorTree>();
728      AU.addPreserved<AliasAnalysis>();
729    }
730
731    // Helper fuctions
732    // FIXME: eliminate or document these better
733    bool processLoad(LoadInst* L,
734                     DenseMap<Value*, LoadInst*> &lastLoad,
735                     SmallVectorImpl<Instruction*> &toErase);
736    bool processInstruction(Instruction* I,
737                            DenseMap<Value*, LoadInst*>& lastSeenLoad,
738                            SmallVectorImpl<Instruction*> &toErase);
739    bool processNonLocalLoad(LoadInst* L,
740                             SmallVectorImpl<Instruction*> &toErase);
741    bool processBlock(DomTreeNode* DTN);
742    Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig,
743                            DenseMap<BasicBlock*, Value*> &Phis,
744                            bool top_level = false);
745    void dump(DenseMap<uint32_t, Value*>& d);
746    bool iterateOnFunction(Function &F);
747    Value* CollapsePhi(PHINode* p);
748    bool isSafeReplacement(PHINode* p, Instruction* inst);
749    bool performPRE(Function& F);
750    Value* lookupNumber(BasicBlock* BB, uint32_t num);
751    bool mergeBlockIntoPredecessor(BasicBlock* BB);
752    void cleanupGlobalSets();
753  };
754
755  char GVN::ID = 0;
756}
757
758// createGVNPass - The public interface to this file...
759FunctionPass *llvm::createGVNPass() { return new GVN(); }
760
761static RegisterPass<GVN> X("gvn",
762                           "Global Value Numbering");
763
764void GVN::dump(DenseMap<uint32_t, Value*>& d) {
765  printf("{\n");
766  for (DenseMap<uint32_t, Value*>::iterator I = d.begin(),
767       E = d.end(); I != E; ++I) {
768      printf("%d\n", I->first);
769      I->second->dump();
770  }
771  printf("}\n");
772}
773
774Value* GVN::CollapsePhi(PHINode* p) {
775  DominatorTree &DT = getAnalysis<DominatorTree>();
776  Value* constVal = p->hasConstantValue();
777
778  if (!constVal) return 0;
779
780  Instruction* inst = dyn_cast<Instruction>(constVal);
781  if (!inst)
782    return constVal;
783
784  if (DT.dominates(inst, p))
785    if (isSafeReplacement(p, inst))
786      return inst;
787  return 0;
788}
789
790bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) {
791  if (!isa<PHINode>(inst))
792    return true;
793
794  for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end();
795       UI != E; ++UI)
796    if (PHINode* use_phi = dyn_cast<PHINode>(UI))
797      if (use_phi->getParent() == inst->getParent())
798        return false;
799
800  return true;
801}
802
803/// GetValueForBlock - Get the value to use within the specified basic block.
804/// available values are in Phis.
805Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
806                             DenseMap<BasicBlock*, Value*> &Phis,
807                             bool top_level) {
808
809  // If we have already computed this value, return the previously computed val.
810  DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB);
811  if (V != Phis.end() && !top_level) return V->second;
812
813  // If the block is unreachable, just return undef, since this path
814  // can't actually occur at runtime.
815  if (!getAnalysis<DominatorTree>().isReachableFromEntry(BB))
816    return Phis[BB] = UndefValue::get(orig->getType());
817
818  BasicBlock* singlePred = BB->getSinglePredecessor();
819  if (singlePred) {
820    Value *ret = GetValueForBlock(singlePred, orig, Phis);
821    Phis[BB] = ret;
822    return ret;
823  }
824
825  // Otherwise, the idom is the loop, so we need to insert a PHI node.  Do so
826  // now, then get values to fill in the incoming values for the PHI.
827  PHINode *PN = PHINode::Create(orig->getType(), orig->getName()+".rle",
828                                BB->begin());
829  PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB)));
830
831  if (Phis.count(BB) == 0)
832    Phis.insert(std::make_pair(BB, PN));
833
834  // Fill in the incoming values for the block.
835  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
836    Value* val = GetValueForBlock(*PI, orig, Phis);
837    PN->addIncoming(val, *PI);
838  }
839
840  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
841  AA.copyValue(orig, PN);
842
843  // Attempt to collapse PHI nodes that are trivially redundant
844  Value* v = CollapsePhi(PN);
845  if (!v) {
846    // Cache our phi construction results
847    phiMap[orig->getPointerOperand()].insert(PN);
848    return PN;
849  }
850
851  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
852
853  MD.removeInstruction(PN);
854  PN->replaceAllUsesWith(v);
855
856  for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
857       E = Phis.end(); I != E; ++I)
858    if (I->second == PN)
859      I->second = v;
860
861  PN->eraseFromParent();
862
863  Phis[BB] = v;
864  return v;
865}
866
867/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are
868/// non-local by performing PHI construction.
869bool GVN::processNonLocalLoad(LoadInst* L,
870                              SmallVectorImpl<Instruction*> &toErase) {
871  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
872
873  // Find the non-local dependencies of the load
874  SmallVector<std::pair<BasicBlock*, MemDepResult>, 32> deps;
875  MD.getNonLocalDependency(L, deps);
876
877  // If we had to process more than one hundred blocks to find the
878  // dependencies, this load isn't worth worrying about.  Optimizing
879  // it will be too expensive.
880  if (deps.size() > 100)
881    return false;
882
883  BasicBlock *EntryBlock = &L->getParent()->getParent()->getEntryBlock();
884
885  DenseMap<BasicBlock*, Value*> repl;
886
887  // Filter out useless results (non-locals, etc)
888  for (SmallVector<std::pair<BasicBlock*, MemDepResult>, 32>::iterator
889       I = deps.begin(), E = deps.end(); I != E; ++I) {
890    if (I->second.isNone()) {
891      repl[I->first] = UndefValue::get(L->getType());
892      continue;
893    }
894
895    if (I->second.isNonLocal()) {
896      // If this is a non-local dependency in the entry block, then we depend on
897      // the value live-in at the start of the function.  We could insert a load
898      // in the entry block to get this, but for now we'll just bail out.
899      // FIXME: Consider emitting a load in the entry block to catch this case!
900      if (I->first == EntryBlock)
901        return false;
902      continue;
903    }
904
905    if (StoreInst* S = dyn_cast<StoreInst>(I->second.getInst())) {
906      if (S->getPointerOperand() != L->getPointerOperand())
907        return false;
908      repl[I->first] = S->getOperand(0);
909    } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second.getInst())) {
910      if (LD->getPointerOperand() != L->getPointerOperand())
911        return false;
912      repl[I->first] = LD;
913    } else {
914      return false;
915    }
916  }
917
918  // Use cached PHI construction information from previous runs
919  SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()];
920  for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end();
921       I != E; ++I) {
922    if ((*I)->getParent() == L->getParent()) {
923      MD.removeInstruction(L);
924      L->replaceAllUsesWith(*I);
925      toErase.push_back(L);
926      NumGVNLoad++;
927      return true;
928    }
929
930    repl.insert(std::make_pair((*I)->getParent(), *I));
931  }
932
933  // Perform PHI construction
934  SmallPtrSet<BasicBlock*, 4> visited;
935  Value* v = GetValueForBlock(L->getParent(), L, repl, true);
936
937  MD.removeInstruction(L);
938  L->replaceAllUsesWith(v);
939  toErase.push_back(L);
940  NumGVNLoad++;
941
942  return true;
943}
944
945/// processLoad - Attempt to eliminate a load, first by eliminating it
946/// locally, and then attempting non-local elimination if that fails.
947bool GVN::processLoad(LoadInst *L, DenseMap<Value*, LoadInst*> &lastLoad,
948                      SmallVectorImpl<Instruction*> &toErase) {
949  if (L->isVolatile()) {
950    lastLoad[L->getPointerOperand()] = L;
951    return false;
952  }
953
954  Value* pointer = L->getPointerOperand();
955  LoadInst*& last = lastLoad[pointer];
956
957  // ... to a pointer that has been loaded from before...
958  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
959  bool removedNonLocal = false;
960  MemDepResult dep = MD.getDependency(L);
961  if (dep.isNonLocal() &&
962      L->getParent() != &L->getParent()->getParent()->getEntryBlock()) {
963    removedNonLocal = processNonLocalLoad(L, toErase);
964
965    if (!removedNonLocal)
966      last = L;
967
968    return removedNonLocal;
969  }
970
971
972  bool deletedLoad = false;
973
974  // Walk up the dependency chain until we either find
975  // a dependency we can use, or we can't walk any further
976  while (Instruction *DepInst = dep.getInst()) {
977    // ... that depends on a store ...
978    if (StoreInst* S = dyn_cast<StoreInst>(DepInst)) {
979      if (S->getPointerOperand() == pointer) {
980        // Remove it!
981        MD.removeInstruction(L);
982
983        L->replaceAllUsesWith(S->getOperand(0));
984        toErase.push_back(L);
985        deletedLoad = true;
986        NumGVNLoad++;
987      }
988
989      // Whether we removed it or not, we can't
990      // go any further
991      break;
992    } else if (!isa<LoadInst>(DepInst)) {
993      // Only want to handle loads below.
994      break;
995    } else if (!last) {
996      // If we don't depend on a store, and we haven't
997      // been loaded before, bail.
998      break;
999    } else if (DepInst == last) {
1000      // Remove it!
1001      MD.removeInstruction(L);
1002
1003      L->replaceAllUsesWith(last);
1004      toErase.push_back(L);
1005      deletedLoad = true;
1006      NumGVNLoad++;
1007      break;
1008    } else {
1009      dep = MD.getDependencyFrom(L, DepInst, DepInst->getParent());
1010    }
1011  }
1012
1013  // If this load really doesn't depend on anything, then we must be loading an
1014  // undef value.  This can happen when loading for a fresh allocation with no
1015  // intervening stores, for example.
1016  if (dep.isNone()) {
1017    // If this load depends directly on an allocation, there isn't
1018    // anything stored there; therefore, we can optimize this load
1019    // to undef.
1020    MD.removeInstruction(L);
1021    L->replaceAllUsesWith(UndefValue::get(L->getType()));
1022    toErase.push_back(L);
1023    deletedLoad = true;
1024    NumGVNLoad++;
1025  }
1026
1027  if (!deletedLoad)
1028    last = L;
1029
1030  return deletedLoad;
1031}
1032
1033Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) {
1034  DenseMap<BasicBlock*, ValueNumberScope*>::iterator I = localAvail.find(BB);
1035  if (I == localAvail.end())
1036    return 0;
1037
1038  ValueNumberScope* locals = I->second;
1039
1040  while (locals) {
1041    DenseMap<uint32_t, Value*>::iterator I = locals->table.find(num);
1042    if (I != locals->table.end())
1043      return I->second;
1044    else
1045      locals = locals->parent;
1046  }
1047
1048  return 0;
1049}
1050
1051/// processInstruction - When calculating availability, handle an instruction
1052/// by inserting it into the appropriate sets
1053bool GVN::processInstruction(Instruction *I,
1054                             DenseMap<Value*, LoadInst*> &lastSeenLoad,
1055                             SmallVectorImpl<Instruction*> &toErase) {
1056  if (LoadInst* L = dyn_cast<LoadInst>(I)) {
1057    bool changed = processLoad(L, lastSeenLoad, toErase);
1058
1059    if (!changed) {
1060      unsigned num = VN.lookup_or_add(L);
1061      localAvail[I->getParent()]->table.insert(std::make_pair(num, L));
1062    }
1063
1064    return changed;
1065  }
1066
1067  uint32_t nextNum = VN.getNextUnusedValueNumber();
1068  unsigned num = VN.lookup_or_add(I);
1069
1070  // Allocations are always uniquely numbered, so we can save time and memory
1071  // by fast failing them.
1072  if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) {
1073    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
1074    return false;
1075  }
1076
1077  // Collapse PHI nodes
1078  if (PHINode* p = dyn_cast<PHINode>(I)) {
1079    Value* constVal = CollapsePhi(p);
1080
1081    if (constVal) {
1082      for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end();
1083           PI != PE; ++PI)
1084        if (PI->second.count(p))
1085          PI->second.erase(p);
1086
1087      p->replaceAllUsesWith(constVal);
1088      toErase.push_back(p);
1089    } else {
1090      localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
1091    }
1092
1093  // If the number we were assigned was a brand new VN, then we don't
1094  // need to do a lookup to see if the number already exists
1095  // somewhere in the domtree: it can't!
1096  } else if (num == nextNum) {
1097    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
1098
1099  // Perform value-number based elimination
1100  } else if (Value* repl = lookupNumber(I->getParent(), num)) {
1101    // Remove it!
1102    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1103    MD.removeInstruction(I);
1104
1105    VN.erase(I);
1106    I->replaceAllUsesWith(repl);
1107    toErase.push_back(I);
1108    return true;
1109  } else {
1110    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
1111  }
1112
1113  return false;
1114}
1115
1116// GVN::runOnFunction - This is the main transformation entry point for a
1117// function.
1118//
1119bool GVN::runOnFunction(Function& F) {
1120  VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>());
1121  VN.setMemDep(&getAnalysis<MemoryDependenceAnalysis>());
1122  VN.setDomTree(&getAnalysis<DominatorTree>());
1123
1124  bool changed = false;
1125  bool shouldContinue = true;
1126
1127  // Merge unconditional branches, allowing PRE to catch more
1128  // optimization opportunities.
1129  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) {
1130    BasicBlock* BB = FI;
1131    ++FI;
1132    bool removedBlock = MergeBlockIntoPredecessor(BB, this);
1133    if (removedBlock) NumGVNBlocks++;
1134
1135    changed |= removedBlock;
1136  }
1137
1138  while (shouldContinue) {
1139    shouldContinue = iterateOnFunction(F);
1140    changed |= shouldContinue;
1141  }
1142
1143  if (EnablePRE) {
1144    bool PREChanged = true;
1145    while (PREChanged) {
1146      PREChanged = performPRE(F);
1147      changed |= PREChanged;
1148    }
1149  }
1150
1151  cleanupGlobalSets();
1152
1153  return changed;
1154}
1155
1156
1157bool GVN::processBlock(DomTreeNode* DTN) {
1158  BasicBlock* BB = DTN->getBlock();
1159
1160  SmallVector<Instruction*, 8> toErase;
1161  DenseMap<Value*, LoadInst*> lastSeenLoad;
1162  bool changed_function = false;
1163
1164  if (DTN->getIDom())
1165    localAvail[BB] =
1166                  new ValueNumberScope(localAvail[DTN->getIDom()->getBlock()]);
1167  else
1168    localAvail[BB] = new ValueNumberScope(0);
1169
1170  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1171       BI != BE;) {
1172    changed_function |= processInstruction(BI, lastSeenLoad, toErase);
1173    if (toErase.empty()) {
1174      ++BI;
1175      continue;
1176    }
1177
1178    // If we need some instructions deleted, do it now.
1179    NumGVNInstr += toErase.size();
1180
1181    // Avoid iterator invalidation.
1182    bool AtStart = BI == BB->begin();
1183    if (!AtStart)
1184      --BI;
1185
1186    for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(),
1187         E = toErase.end(); I != E; ++I)
1188      (*I)->eraseFromParent();
1189
1190    if (AtStart)
1191      BI = BB->begin();
1192    else
1193      ++BI;
1194
1195    toErase.clear();
1196  }
1197
1198  return changed_function;
1199}
1200
1201/// performPRE - Perform a purely local form of PRE that looks for diamond
1202/// control flow patterns and attempts to perform simple PRE at the join point.
1203bool GVN::performPRE(Function& F) {
1204  bool changed = false;
1205  SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit;
1206  for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()),
1207       DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) {
1208    BasicBlock* CurrentBlock = *DI;
1209
1210    // Nothing to PRE in the entry block.
1211    if (CurrentBlock == &F.getEntryBlock()) continue;
1212
1213    for (BasicBlock::iterator BI = CurrentBlock->begin(),
1214         BE = CurrentBlock->end(); BI != BE; ) {
1215      if (isa<AllocationInst>(BI) || isa<TerminatorInst>(BI) ||
1216          isa<PHINode>(BI) || BI->mayReadFromMemory() ||
1217          BI->mayWriteToMemory()) {
1218        BI++;
1219        continue;
1220      }
1221
1222      uint32_t valno = VN.lookup(BI);
1223
1224      // Look for the predecessors for PRE opportunities.  We're
1225      // only trying to solve the basic diamond case, where
1226      // a value is computed in the successor and one predecessor,
1227      // but not the other.  We also explicitly disallow cases
1228      // where the successor is its own predecessor, because they're
1229      // more complicated to get right.
1230      unsigned numWith = 0;
1231      unsigned numWithout = 0;
1232      BasicBlock* PREPred = 0;
1233      DenseMap<BasicBlock*, Value*> predMap;
1234      for (pred_iterator PI = pred_begin(CurrentBlock),
1235           PE = pred_end(CurrentBlock); PI != PE; ++PI) {
1236        // We're not interested in PRE where the block is its
1237        // own predecessor, on in blocks with predecessors
1238        // that are not reachable.
1239        if (*PI == CurrentBlock) {
1240          numWithout = 2;
1241          break;
1242        } else if (!localAvail.count(*PI))  {
1243          numWithout = 2;
1244          break;
1245        }
1246
1247        DenseMap<uint32_t, Value*>::iterator predV =
1248                                            localAvail[*PI]->table.find(valno);
1249        if (predV == localAvail[*PI]->table.end()) {
1250          PREPred = *PI;
1251          numWithout++;
1252        } else if (predV->second == BI) {
1253          numWithout = 2;
1254        } else {
1255          predMap[*PI] = predV->second;
1256          numWith++;
1257        }
1258      }
1259
1260      // Don't do PRE when it might increase code size, i.e. when
1261      // we would need to insert instructions in more than one pred.
1262      if (numWithout != 1 || numWith == 0) {
1263        BI++;
1264        continue;
1265      }
1266
1267      // We can't do PRE safely on a critical edge, so instead we schedule
1268      // the edge to be split and perform the PRE the next time we iterate
1269      // on the function.
1270      unsigned succNum = 0;
1271      for (unsigned i = 0, e = PREPred->getTerminator()->getNumSuccessors();
1272           i != e; ++i)
1273        if (PREPred->getTerminator()->getSuccessor(i) == CurrentBlock) {
1274          succNum = i;
1275          break;
1276        }
1277
1278      if (isCriticalEdge(PREPred->getTerminator(), succNum)) {
1279        toSplit.push_back(std::make_pair(PREPred->getTerminator(), succNum));
1280        changed = true;
1281        BI++;
1282        continue;
1283      }
1284
1285      // Instantiate the expression the in predecessor that lacked it.
1286      // Because we are going top-down through the block, all value numbers
1287      // will be available in the predecessor by the time we need them.  Any
1288      // that weren't original present will have been instantiated earlier
1289      // in this loop.
1290      Instruction* PREInstr = BI->clone();
1291      bool success = true;
1292      for (unsigned i = 0; i < BI->getNumOperands(); ++i) {
1293        Value* op = BI->getOperand(i);
1294        if (isa<Argument>(op) || isa<Constant>(op) || isa<GlobalValue>(op))
1295          PREInstr->setOperand(i, op);
1296        else {
1297          Value* V = lookupNumber(PREPred, VN.lookup(op));
1298          if (!V) {
1299            success = false;
1300            break;
1301          } else
1302            PREInstr->setOperand(i, V);
1303        }
1304      }
1305
1306      // Fail out if we encounter an operand that is not available in
1307      // the PRE predecessor.  This is typically because of loads which
1308      // are not value numbered precisely.
1309      if (!success) {
1310        delete PREInstr;
1311        BI++;
1312        continue;
1313      }
1314
1315      PREInstr->insertBefore(PREPred->getTerminator());
1316      PREInstr->setName(BI->getName() + ".pre");
1317      predMap[PREPred] = PREInstr;
1318      VN.add(PREInstr, valno);
1319      NumGVNPRE++;
1320
1321      // Update the availability map to include the new instruction.
1322      localAvail[PREPred]->table.insert(std::make_pair(valno, PREInstr));
1323
1324      // Create a PHI to make the value available in this block.
1325      PHINode* Phi = PHINode::Create(BI->getType(),
1326                                     BI->getName() + ".pre-phi",
1327                                     CurrentBlock->begin());
1328      for (pred_iterator PI = pred_begin(CurrentBlock),
1329           PE = pred_end(CurrentBlock); PI != PE; ++PI)
1330        Phi->addIncoming(predMap[*PI], *PI);
1331
1332      VN.add(Phi, valno);
1333      localAvail[CurrentBlock]->table[valno] = Phi;
1334
1335      BI->replaceAllUsesWith(Phi);
1336      VN.erase(BI);
1337
1338      Instruction* erase = BI;
1339      BI++;
1340      erase->eraseFromParent();
1341
1342      changed = true;
1343    }
1344  }
1345
1346  for (SmallVector<std::pair<TerminatorInst*, unsigned>, 4>::iterator
1347       I = toSplit.begin(), E = toSplit.end(); I != E; ++I)
1348    SplitCriticalEdge(I->first, I->second, this);
1349
1350  return changed || toSplit.size();
1351}
1352
1353// iterateOnFunction - Executes one iteration of GVN
1354bool GVN::iterateOnFunction(Function &F) {
1355  DominatorTree &DT = getAnalysis<DominatorTree>();
1356
1357  cleanupGlobalSets();
1358
1359  // Top-down walk of the dominator tree
1360  bool changed = false;
1361  for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1362       DE = df_end(DT.getRootNode()); DI != DE; ++DI)
1363    changed |= processBlock(*DI);
1364
1365  return changed;
1366}
1367
1368void GVN::cleanupGlobalSets() {
1369  VN.clear();
1370  phiMap.clear();
1371
1372  for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator
1373       I = localAvail.begin(), E = localAvail.end(); I != E; ++I)
1374    delete I->second;
1375  localAvail.clear();
1376}
1377