X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FGVN.cpp;h=9d9dcca247483d2e4c49646c904056d4e9dbc411;hb=b70a571c99932464ed828fa425ea1e2783d08fab;hp=650612144adc4285cabab9e6ed19753271ab84a2;hpb=0f7ea1ab106ffb3c8e23a87c0687f85132d93ca1;p=oota-llvm.git

diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index 650612144ad..9d9dcca2474 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -10,20 +10,19 @@
 // This pass performs global value numbering to eliminate fully redundant
 // instructions.  It also performs simple dead load elimination.
 //
+// Note that this pass does the value numbering itself, it does not use the
+// ValueNumbering analysis passes.
+//
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "gvn"
-
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/BasicBlock.h"
 #include "llvm/Constants.h"
 #include "llvm/DerivedTypes.h"
 #include "llvm/Function.h"
-#include "llvm/IntrinsicInst.h"
 #include "llvm/Instructions.h"
-#include "llvm/ParameterAttributes.h"
 #include "llvm/Value.h"
-#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
@@ -33,10 +32,19 @@
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Support/CFG.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
-#include "llvm/Target/TargetData.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 using namespace llvm;
 
+STATISTIC(NumGVNInstr, "Number of instructions deleted");
+STATISTIC(NumGVNLoad, "Number of loads deleted");
+STATISTIC(NumGVNPRE, "Number of instructions PRE'd");
+
+static cl::opt<bool> EnablePRE("enable-pre",
+                               cl::init(true), cl::Hidden);
+
 //===----------------------------------------------------------------------===//
 //                         ValueTable Class
 //===----------------------------------------------------------------------===//
@@ -55,8 +63,8 @@ namespace {
                             FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
                             SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
                             FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 
-                            PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, EMPTY,
-                            TOMBSTONE };
+                            PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, CONSTANT,
+                            EMPTY, TOMBSTONE };
 
     ExpressionOpcode opcode;
     const Type* type;
@@ -129,6 +137,8 @@ namespace {
       DenseMap<Value*, uint32_t> valueNumbering;
       DenseMap<Expression, uint32_t> expressionNumbering;
       AliasAnalysis* AA;
+      MemoryDependenceAnalysis* MD;
+      DominatorTree* DT;
   
       uint32_t nextValueNumber;
     
@@ -144,6 +154,7 @@ namespace {
       Expression create_expression(CastInst* C);
       Expression create_expression(GetElementPtrInst* G);
       Expression create_expression(CallInst* C);
+      Expression create_expression(Constant* C);
     public:
       ValueTable() : nextValueNumber(1) { }
       uint32_t lookup_or_add(Value* V);
@@ -153,7 +164,8 @@ namespace {
       void erase(Value* v);
       unsigned size();
       void setAliasAnalysis(AliasAnalysis* A) { AA = A; }
-      uint32_t hash_operand(Value* v);
+      void setMemDep(MemoryDependenceAnalysis* M) { MD = M; }
+      void setDomTree(DominatorTree* D) { DT = D; }
   };
 }
 
@@ -198,158 +210,85 @@ template <> struct DenseMapInfo<Expression> {
 //===----------------------------------------------------------------------===//
 //                     ValueTable Internal Functions
 //===----------------------------------------------------------------------===//
-Expression::ExpressionOpcode 
-                             ValueTable::getOpcode(BinaryOperator* BO) {
+Expression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) {
   switch(BO->getOpcode()) {
-    case Instruction::Add:
-      return Expression::ADD;
-    case Instruction::Sub:
-      return Expression::SUB;
-    case Instruction::Mul:
-      return Expression::MUL;
-    case Instruction::UDiv:
-      return Expression::UDIV;
-    case Instruction::SDiv:
-      return Expression::SDIV;
-    case Instruction::FDiv:
-      return Expression::FDIV;
-    case Instruction::URem:
-      return Expression::UREM;
-    case Instruction::SRem:
-      return Expression::SREM;
-    case Instruction::FRem:
-      return Expression::FREM;
-    case Instruction::Shl:
-      return Expression::SHL;
-    case Instruction::LShr:
-      return Expression::LSHR;
-    case Instruction::AShr:
-      return Expression::ASHR;
-    case Instruction::And:
-      return Expression::AND;
-    case Instruction::Or:
-      return Expression::OR;
-    case Instruction::Xor:
-      return Expression::XOR;
-    
-    // THIS SHOULD NEVER HAPPEN
-    default:
-      assert(0 && "Binary operator with unknown opcode?");
-      return Expression::ADD;
+  default: // THIS SHOULD NEVER HAPPEN
+    assert(0 && "Binary operator with unknown opcode?");
+  case Instruction::Add:  return Expression::ADD;
+  case Instruction::Sub:  return Expression::SUB;
+  case Instruction::Mul:  return Expression::MUL;
+  case Instruction::UDiv: return Expression::UDIV;
+  case Instruction::SDiv: return Expression::SDIV;
+  case Instruction::FDiv: return Expression::FDIV;
+  case Instruction::URem: return Expression::UREM;
+  case Instruction::SRem: return Expression::SREM;
+  case Instruction::FRem: return Expression::FREM;
+  case Instruction::Shl:  return Expression::SHL;
+  case Instruction::LShr: return Expression::LSHR;
+  case Instruction::AShr: return Expression::ASHR;
+  case Instruction::And:  return Expression::AND;
+  case Instruction::Or:   return Expression::OR;
+  case Instruction::Xor:  return Expression::XOR;
   }
 }
 
 Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
-  if (C->getOpcode() == Instruction::ICmp) {
-    switch (C->getPredicate()) {
-      case ICmpInst::ICMP_EQ:
-        return Expression::ICMPEQ;
-      case ICmpInst::ICMP_NE:
-        return Expression::ICMPNE;
-      case ICmpInst::ICMP_UGT:
-        return Expression::ICMPUGT;
-      case ICmpInst::ICMP_UGE:
-        return Expression::ICMPUGE;
-      case ICmpInst::ICMP_ULT:
-        return Expression::ICMPULT;
-      case ICmpInst::ICMP_ULE:
-        return Expression::ICMPULE;
-      case ICmpInst::ICMP_SGT:
-        return Expression::ICMPSGT;
-      case ICmpInst::ICMP_SGE:
-        return Expression::ICMPSGE;
-      case ICmpInst::ICMP_SLT:
-        return Expression::ICMPSLT;
-      case ICmpInst::ICMP_SLE:
-        return Expression::ICMPSLE;
-      
-      // THIS SHOULD NEVER HAPPEN
-      default:
-        assert(0 && "Comparison with unknown predicate?");
-        return Expression::ICMPEQ;
-    }
-  } else {
+  if (isa<ICmpInst>(C) || isa<VICmpInst>(C)) {
     switch (C->getPredicate()) {
-      case FCmpInst::FCMP_OEQ:
-        return Expression::FCMPOEQ;
-      case FCmpInst::FCMP_OGT:
-        return Expression::FCMPOGT;
-      case FCmpInst::FCMP_OGE:
-        return Expression::FCMPOGE;
-      case FCmpInst::FCMP_OLT:
-        return Expression::FCMPOLT;
-      case FCmpInst::FCMP_OLE:
-        return Expression::FCMPOLE;
-      case FCmpInst::FCMP_ONE:
-        return Expression::FCMPONE;
-      case FCmpInst::FCMP_ORD:
-        return Expression::FCMPORD;
-      case FCmpInst::FCMP_UNO:
-        return Expression::FCMPUNO;
-      case FCmpInst::FCMP_UEQ:
-        return Expression::FCMPUEQ;
-      case FCmpInst::FCMP_UGT:
-        return Expression::FCMPUGT;
-      case FCmpInst::FCMP_UGE:
-        return Expression::FCMPUGE;
-      case FCmpInst::FCMP_ULT:
-        return Expression::FCMPULT;
-      case FCmpInst::FCMP_ULE:
-        return Expression::FCMPULE;
-      case FCmpInst::FCMP_UNE:
-        return Expression::FCMPUNE;
-      
-      // THIS SHOULD NEVER HAPPEN
-      default:
-        assert(0 && "Comparison with unknown predicate?");
-        return Expression::FCMPOEQ;
+    default:  // THIS SHOULD NEVER HAPPEN
+      assert(0 && "Comparison with unknown predicate?");
+    case ICmpInst::ICMP_EQ:  return Expression::ICMPEQ;
+    case ICmpInst::ICMP_NE:  return Expression::ICMPNE;
+    case ICmpInst::ICMP_UGT: return Expression::ICMPUGT;
+    case ICmpInst::ICMP_UGE: return Expression::ICMPUGE;
+    case ICmpInst::ICMP_ULT: return Expression::ICMPULT;
+    case ICmpInst::ICMP_ULE: return Expression::ICMPULE;
+    case ICmpInst::ICMP_SGT: return Expression::ICMPSGT;
+    case ICmpInst::ICMP_SGE: return Expression::ICMPSGE;
+    case ICmpInst::ICMP_SLT: return Expression::ICMPSLT;
+    case ICmpInst::ICMP_SLE: return Expression::ICMPSLE;
     }
   }
+  assert((isa<FCmpInst>(C) || isa<VFCmpInst>(C)) && "Unknown compare");
+  switch (C->getPredicate()) {
+  default: // THIS SHOULD NEVER HAPPEN
+    assert(0 && "Comparison with unknown predicate?");
+  case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ;
+  case FCmpInst::FCMP_OGT: return Expression::FCMPOGT;
+  case FCmpInst::FCMP_OGE: return Expression::FCMPOGE;
+  case FCmpInst::FCMP_OLT: return Expression::FCMPOLT;
+  case FCmpInst::FCMP_OLE: return Expression::FCMPOLE;
+  case FCmpInst::FCMP_ONE: return Expression::FCMPONE;
+  case FCmpInst::FCMP_ORD: return Expression::FCMPORD;
+  case FCmpInst::FCMP_UNO: return Expression::FCMPUNO;
+  case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ;
+  case FCmpInst::FCMP_UGT: return Expression::FCMPUGT;
+  case FCmpInst::FCMP_UGE: return Expression::FCMPUGE;
+  case FCmpInst::FCMP_ULT: return Expression::FCMPULT;
+  case FCmpInst::FCMP_ULE: return Expression::FCMPULE;
+  case FCmpInst::FCMP_UNE: return Expression::FCMPUNE;
+  }
 }
 
-Expression::ExpressionOpcode 
-                             ValueTable::getOpcode(CastInst* C) {
+Expression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) {
   switch(C->getOpcode()) {
-    case Instruction::Trunc:
-      return Expression::TRUNC;
-    case Instruction::ZExt:
-      return Expression::ZEXT;
-    case Instruction::SExt:
-      return Expression::SEXT;
-    case Instruction::FPToUI:
-      return Expression::FPTOUI;
-    case Instruction::FPToSI:
-      return Expression::FPTOSI;
-    case Instruction::UIToFP:
-      return Expression::UITOFP;
-    case Instruction::SIToFP:
-      return Expression::SITOFP;
-    case Instruction::FPTrunc:
-      return Expression::FPTRUNC;
-    case Instruction::FPExt:
-      return Expression::FPEXT;
-    case Instruction::PtrToInt:
-      return Expression::PTRTOINT;
-    case Instruction::IntToPtr:
-      return Expression::INTTOPTR;
-    case Instruction::BitCast:
-      return Expression::BITCAST;
-    
-    // THIS SHOULD NEVER HAPPEN
-    default:
-      assert(0 && "Cast operator with unknown opcode?");
-      return Expression::BITCAST;
+  default: // THIS SHOULD NEVER HAPPEN
+    assert(0 && "Cast operator with unknown opcode?");
+  case Instruction::Trunc:    return Expression::TRUNC;
+  case Instruction::ZExt:     return Expression::ZEXT;
+  case Instruction::SExt:     return Expression::SEXT;
+  case Instruction::FPToUI:   return Expression::FPTOUI;
+  case Instruction::FPToSI:   return Expression::FPTOSI;
+  case Instruction::UIToFP:   return Expression::UITOFP;
+  case Instruction::SIToFP:   return Expression::SITOFP;
+  case Instruction::FPTrunc:  return Expression::FPTRUNC;
+  case Instruction::FPExt:    return Expression::FPEXT;
+  case Instruction::PtrToInt: return Expression::PTRTOINT;
+  case Instruction::IntToPtr: return Expression::INTTOPTR;
+  case Instruction::BitCast:  return Expression::BITCAST;
   }
 }
 
-uint32_t ValueTable::hash_operand(Value* v) {
-  if (CallInst* CI = dyn_cast<CallInst>(v))
-    if (!AA->doesNotAccessMemory(CI))
-      return nextValueNumber++;
-  
-  return lookup_or_add(v);
-}
-
 Expression ValueTable::create_expression(CallInst* C) {
   Expression e;
   
@@ -362,7 +301,7 @@ Expression ValueTable::create_expression(CallInst* C) {
   
   for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end();
        I != E; ++I)
-    e.varargs.push_back(hash_operand(*I));
+    e.varargs.push_back(lookup_or_add(*I));
   
   return e;
 }
@@ -370,8 +309,8 @@ Expression ValueTable::create_expression(CallInst* C) {
 Expression ValueTable::create_expression(BinaryOperator* BO) {
   Expression e;
     
-  e.firstVN = hash_operand(BO->getOperand(0));
-  e.secondVN = hash_operand(BO->getOperand(1));
+  e.firstVN = lookup_or_add(BO->getOperand(0));
+  e.secondVN = lookup_or_add(BO->getOperand(1));
   e.thirdVN = 0;
   e.function = 0;
   e.type = BO->getType();
@@ -383,8 +322,8 @@ Expression ValueTable::create_expression(BinaryOperator* BO) {
 Expression ValueTable::create_expression(CmpInst* C) {
   Expression e;
     
-  e.firstVN = hash_operand(C->getOperand(0));
-  e.secondVN = hash_operand(C->getOperand(1));
+  e.firstVN = lookup_or_add(C->getOperand(0));
+  e.secondVN = lookup_or_add(C->getOperand(1));
   e.thirdVN = 0;
   e.function = 0;
   e.type = C->getType();
@@ -396,7 +335,7 @@ Expression ValueTable::create_expression(CmpInst* C) {
 Expression ValueTable::create_expression(CastInst* C) {
   Expression e;
     
-  e.firstVN = hash_operand(C->getOperand(0));
+  e.firstVN = lookup_or_add(C->getOperand(0));
   e.secondVN = 0;
   e.thirdVN = 0;
   e.function = 0;
@@ -409,9 +348,9 @@ Expression ValueTable::create_expression(CastInst* C) {
 Expression ValueTable::create_expression(ShuffleVectorInst* S) {
   Expression e;
     
-  e.firstVN = hash_operand(S->getOperand(0));
-  e.secondVN = hash_operand(S->getOperand(1));
-  e.thirdVN = hash_operand(S->getOperand(2));
+  e.firstVN = lookup_or_add(S->getOperand(0));
+  e.secondVN = lookup_or_add(S->getOperand(1));
+  e.thirdVN = lookup_or_add(S->getOperand(2));
   e.function = 0;
   e.type = S->getType();
   e.opcode = Expression::SHUFFLE;
@@ -422,8 +361,8 @@ Expression ValueTable::create_expression(ShuffleVectorInst* S) {
 Expression ValueTable::create_expression(ExtractElementInst* E) {
   Expression e;
     
-  e.firstVN = hash_operand(E->getOperand(0));
-  e.secondVN = hash_operand(E->getOperand(1));
+  e.firstVN = lookup_or_add(E->getOperand(0));
+  e.secondVN = lookup_or_add(E->getOperand(1));
   e.thirdVN = 0;
   e.function = 0;
   e.type = E->getType();
@@ -435,9 +374,9 @@ Expression ValueTable::create_expression(ExtractElementInst* E) {
 Expression ValueTable::create_expression(InsertElementInst* I) {
   Expression e;
     
-  e.firstVN = hash_operand(I->getOperand(0));
-  e.secondVN = hash_operand(I->getOperand(1));
-  e.thirdVN = hash_operand(I->getOperand(2));
+  e.firstVN = lookup_or_add(I->getOperand(0));
+  e.secondVN = lookup_or_add(I->getOperand(1));
+  e.thirdVN = lookup_or_add(I->getOperand(2));
   e.function = 0;
   e.type = I->getType();
   e.opcode = Expression::INSERT;
@@ -448,9 +387,9 @@ Expression ValueTable::create_expression(InsertElementInst* I) {
 Expression ValueTable::create_expression(SelectInst* I) {
   Expression e;
     
-  e.firstVN = hash_operand(I->getCondition());
-  e.secondVN = hash_operand(I->getTrueValue());
-  e.thirdVN = hash_operand(I->getFalseValue());
+  e.firstVN = lookup_or_add(I->getCondition());
+  e.secondVN = lookup_or_add(I->getTrueValue());
+  e.thirdVN = lookup_or_add(I->getFalseValue());
   e.function = 0;
   e.type = I->getType();
   e.opcode = Expression::SELECT;
@@ -460,8 +399,8 @@ Expression ValueTable::create_expression(SelectInst* I) {
 
 Expression ValueTable::create_expression(GetElementPtrInst* G) {
   Expression e;
-    
-  e.firstVN = hash_operand(G->getPointerOperand());
+  
+  e.firstVN = lookup_or_add(G->getPointerOperand());
   e.secondVN = 0;
   e.thirdVN = 0;
   e.function = 0;
@@ -470,7 +409,7 @@ Expression ValueTable::create_expression(GetElementPtrInst* G) {
   
   for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
        I != E; ++I)
-    e.varargs.push_back(hash_operand(*I));
+    e.varargs.push_back(lookup_or_add(*I));
   
   return e;
 }
@@ -479,6 +418,11 @@ Expression ValueTable::create_expression(GetElementPtrInst* G) {
 //                     ValueTable External Functions
 //===----------------------------------------------------------------------===//
 
+/// add - Insert a value into the table with a specified value number.
+void ValueTable::add(Value* V, uint32_t num) {
+  valueNumbering.insert(std::make_pair(V, num));
+}
+
 /// lookup_or_add - Returns the value number for the specified value, assigning
 /// it a new number if it did not have one before.
 uint32_t ValueTable::lookup_or_add(Value* V) {
@@ -487,7 +431,7 @@ uint32_t ValueTable::lookup_or_add(Value* V) {
     return VI->second;
   
   if (CallInst* C = dyn_cast<CallInst>(V)) {
-    if (AA->onlyReadsMemory(C)) { // includes doesNotAccessMemory
+    if (AA->doesNotAccessMemory(C)) {
       Expression e = create_expression(C);
     
       DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
@@ -500,6 +444,104 @@ uint32_t ValueTable::lookup_or_add(Value* V) {
       
         return nextValueNumber++;
       }
+    } else if (AA->onlyReadsMemory(C)) {
+      Expression e = create_expression(C);
+      
+      if (expressionNumbering.find(e) == expressionNumbering.end()) {
+        expressionNumbering.insert(std::make_pair(e, nextValueNumber));
+        valueNumbering.insert(std::make_pair(V, nextValueNumber));
+        return nextValueNumber++;
+      }
+      
+      Instruction* local_dep = MD->getDependency(C);
+      
+      if (local_dep == MemoryDependenceAnalysis::None) {
+        valueNumbering.insert(std::make_pair(V, nextValueNumber));
+        return nextValueNumber++;
+      } else if (local_dep != MemoryDependenceAnalysis::NonLocal) {
+        if (!isa<CallInst>(local_dep)) {
+          valueNumbering.insert(std::make_pair(V, nextValueNumber));
+          return nextValueNumber++;
+        }
+        
+        CallInst* local_cdep = cast<CallInst>(local_dep);
+        
+        if (local_cdep->getCalledFunction() != C->getCalledFunction() ||
+            local_cdep->getNumOperands() != C->getNumOperands()) {
+          valueNumbering.insert(std::make_pair(V, nextValueNumber));
+          return nextValueNumber++;
+        } else if (!C->getCalledFunction()) { 
+          valueNumbering.insert(std::make_pair(V, nextValueNumber));
+          return nextValueNumber++;
+        } else {
+          for (unsigned i = 1; i < C->getNumOperands(); ++i) {
+            uint32_t c_vn = lookup_or_add(C->getOperand(i));
+            uint32_t cd_vn = lookup_or_add(local_cdep->getOperand(i));
+            if (c_vn != cd_vn) {
+              valueNumbering.insert(std::make_pair(V, nextValueNumber));
+              return nextValueNumber++;
+            }
+          }
+        
+          uint32_t v = lookup_or_add(local_cdep);
+          valueNumbering.insert(std::make_pair(V, v));
+          return v;
+        }
+      }
+      
+      
+      DenseMap<BasicBlock*, Value*> deps;
+      MD->getNonLocalDependency(C, deps);
+      CallInst* cdep = 0;
+      
+      for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(),
+           E = deps.end(); I != E; ++I) {
+        if (I->second == MemoryDependenceAnalysis::None) {
+          valueNumbering.insert(std::make_pair(V, nextValueNumber));
+
+          return nextValueNumber++;
+        } else if (I->second != MemoryDependenceAnalysis::NonLocal) {
+          if (DT->properlyDominates(I->first, C->getParent())) {
+            if (CallInst* CD = dyn_cast<CallInst>(I->second))
+              cdep = CD;
+            else {
+              valueNumbering.insert(std::make_pair(V, nextValueNumber));
+              return nextValueNumber++;
+            }
+          } else {
+            valueNumbering.insert(std::make_pair(V, nextValueNumber));
+            return nextValueNumber++;
+          }
+        }
+      }
+      
+      if (!cdep) {
+        valueNumbering.insert(std::make_pair(V, nextValueNumber));
+        return nextValueNumber++;
+      }
+      
+      if (cdep->getCalledFunction() != C->getCalledFunction() ||
+          cdep->getNumOperands() != C->getNumOperands()) {
+        valueNumbering.insert(std::make_pair(V, nextValueNumber));
+        return nextValueNumber++;
+      } else if (!C->getCalledFunction()) { 
+        valueNumbering.insert(std::make_pair(V, nextValueNumber));
+        return nextValueNumber++;
+      } else {
+        for (unsigned i = 1; i < C->getNumOperands(); ++i) {
+          uint32_t c_vn = lookup_or_add(C->getOperand(i));
+          uint32_t cd_vn = lookup_or_add(cdep->getOperand(i));
+          if (c_vn != cd_vn) {
+            valueNumbering.insert(std::make_pair(V, nextValueNumber));
+            return nextValueNumber++;
+          }
+        }
+        
+        uint32_t v = lookup_or_add(cdep);
+        valueNumbering.insert(std::make_pair(V, v));
+        return v;
+      }
+      
     } else {
       valueNumbering.insert(std::make_pair(V, nextValueNumber));
       return nextValueNumber++;
@@ -618,12 +660,8 @@ uint32_t ValueTable::lookup_or_add(Value* V) {
 /// the value has not yet been numbered.
 uint32_t ValueTable::lookup(Value* V) const {
   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
-  if (VI != valueNumbering.end())
-    return VI->second;
-  else
-    assert(0 && "Value not numbered?");
-  
-  return 0;
+  assert(VI != valueNumbering.end() && "Value not numbered?");
+  return VI->second;
 }
 
 /// clear - Remove all entries from the ValueTable
@@ -639,65 +677,29 @@ void ValueTable::erase(Value* V) {
 }
 
 //===----------------------------------------------------------------------===//
-//                       ValueNumberedSet Class
+//                         GVN Pass
 //===----------------------------------------------------------------------===//
-namespace {
-class ValueNumberedSet {
-  private:
-    SmallPtrSet<Value*, 8> contents;
-    BitVector numbers;
-  public:
-    ValueNumberedSet() { numbers.resize(1); }
-    ValueNumberedSet(const ValueNumberedSet& other) {
-      numbers = other.numbers;
-      contents = other.contents;
-    }
-    
-    typedef SmallPtrSet<Value*, 8>::iterator iterator;
-    
-    iterator begin() { return contents.begin(); }
-    iterator end() { return contents.end(); }
-    
-    bool insert(Value* v) { return contents.insert(v); }
-    void insert(iterator I, iterator E) { contents.insert(I, E); }
-    void erase(Value* v) { contents.erase(v); }
-    unsigned count(Value* v) { return contents.count(v); }
-    size_t size() { return contents.size(); }
-    
-    void set(unsigned i)  {
-      if (i >= numbers.size())
-        numbers.resize(i+1);
-      
-      numbers.set(i);
-    }
-    
-    void operator=(const ValueNumberedSet& other) {
-      contents = other.contents;
-      numbers = other.numbers;
-    }
-    
-    void reset(unsigned i)  {
-      if (i < numbers.size())
-        numbers.reset(i);
-    }
-    
-    bool test(unsigned i)  {
-      if (i >= numbers.size())
-        return false;
-      
-      return numbers.test(i);
-    }
-    
-    void clear() {
-      contents.clear();
-      numbers.clear();
+
+namespace llvm {
+  template<> struct DenseMapInfo<uint32_t> {
+    static inline uint32_t getEmptyKey() { return ~0; }
+    static inline uint32_t getTombstoneKey() { return ~0 - 1; }
+    static unsigned getHashValue(const uint32_t& Val) { return Val * 37; }
+    static bool isPod() { return true; }
+    static bool isEqual(const uint32_t& LHS, const uint32_t& RHS) {
+      return LHS == RHS;
     }
-};
+  };
 }
 
-//===----------------------------------------------------------------------===//
-//                         GVN Pass
-//===----------------------------------------------------------------------===//
+namespace {
+  struct VISIBILITY_HIDDEN ValueNumberScope {
+    ValueNumberScope* parent;
+    DenseMap<uint32_t, Value*> table;
+    
+    ValueNumberScope(ValueNumberScope* p) : parent(p) { }
+  };
+}
 
 namespace {
 
@@ -709,8 +711,7 @@ namespace {
 
   private:
     ValueTable VN;
-    
-    DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
+    DenseMap<BasicBlock*, ValueNumberScope*> localAvail;
     
     typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType;
     PhiMapType phiMap;
@@ -718,44 +719,38 @@ namespace {
     
     // This transformation requires dominator postdominator info
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-      AU.setPreservesCFG();
       AU.addRequired<DominatorTree>();
       AU.addRequired<MemoryDependenceAnalysis>();
       AU.addRequired<AliasAnalysis>();
-      AU.addRequired<TargetData>();
+      
+      AU.addPreserved<DominatorTree>();
       AU.addPreserved<AliasAnalysis>();
       AU.addPreserved<MemoryDependenceAnalysis>();
-      AU.addPreserved<TargetData>();
     }
   
     // Helper fuctions
     // FIXME: eliminate or document these better
-    Value* find_leader(ValueNumberedSet& vals, uint32_t v) ;
-    void val_insert(ValueNumberedSet& s, Value* v);
     bool processLoad(LoadInst* L,
-                     DenseMap<Value*, LoadInst*>& lastLoad,
-                     SmallVector<Instruction*, 4>& toErase);
+                     DenseMap<Value*, LoadInst*> &lastLoad,
+                     SmallVectorImpl<Instruction*> &toErase);
     bool processInstruction(Instruction* I,
-                            ValueNumberedSet& currAvail,
                             DenseMap<Value*, LoadInst*>& lastSeenLoad,
-                            SmallVector<Instruction*, 4>& toErase);
+                            SmallVectorImpl<Instruction*> &toErase);
     bool processNonLocalLoad(LoadInst* L,
-                             SmallVector<Instruction*, 4>& toErase);
-    bool processMemCpy(MemCpyInst* M, MemCpyInst* MDep,
-                       SmallVector<Instruction*, 4>& toErase);
-    bool performReturnSlotOptzn(MemCpyInst* cpy, CallInst* C,
-                                SmallVector<Instruction*, 4>& toErase);
+                             SmallVectorImpl<Instruction*> &toErase);
+    bool processBlock(DomTreeNode* DTN);
     Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig,
                             DenseMap<BasicBlock*, Value*> &Phis,
                             bool top_level = false);
-    void dump(DenseMap<BasicBlock*, Value*>& d);
+    void dump(DenseMap<uint32_t, Value*>& d);
     bool iterateOnFunction(Function &F);
     Value* CollapsePhi(PHINode* p);
     bool isSafeReplacement(PHINode* p, Instruction* inst);
+    bool performPRE(Function& F);
+    Value* lookupNumber(BasicBlock* BB, uint32_t num);
   };
   
   char GVN::ID = 0;
-  
 }
 
 // createGVNPass - The public interface to this file...
@@ -764,40 +759,11 @@ FunctionPass *llvm::createGVNPass() { return new GVN(); }
 static RegisterPass<GVN> X("gvn",
                            "Global Value Numbering");
 
-STATISTIC(NumGVNInstr, "Number of instructions deleted");
-STATISTIC(NumGVNLoad, "Number of loads deleted");
-
-/// find_leader - Given a set and a value number, return the first
-/// element of the set with that value number, or 0 if no such element
-/// is present
-Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) {
-  if (!vals.test(v))
-    return 0;
-  
-  for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
-       I != E; ++I)
-    if (v == VN.lookup(*I))
-      return *I;
-  
-  assert(0 && "No leader found, but present bit is set?");
-  return 0;
-}
-
-/// val_insert - Insert a value into a set only if there is not a value
-/// with the same value number already in the set
-void GVN::val_insert(ValueNumberedSet& s, Value* v) {
-  uint32_t num = VN.lookup(v);
-  if (!s.test(num))
-    s.insert(v);
-}
-
-void GVN::dump(DenseMap<BasicBlock*, Value*>& d) {
+void GVN::dump(DenseMap<uint32_t, Value*>& d) {
   printf("{\n");
-  for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(),
+  for (DenseMap<uint32_t, Value*>::iterator I = d.begin(),
        E = d.end(); I != E; ++I) {
-    if (I->second == MemoryDependenceAnalysis::None)
-      printf("None\n");
-    else
+      printf("%d\n", I->first);
       I->second->dump();
   }
   printf("}\n");
@@ -807,16 +773,15 @@ Value* GVN::CollapsePhi(PHINode* p) {
   DominatorTree &DT = getAnalysis<DominatorTree>();
   Value* constVal = p->hasConstantValue();
   
-  if (constVal) {
-    if (Instruction* inst = dyn_cast<Instruction>(constVal)) {
-      if (DT.dominates(inst, p))
-        if (isSafeReplacement(p, inst))
-          return inst;
-    } else {
-      return constVal;
-    }
-  }
+  if (!constVal) return 0;
   
+  Instruction* inst = dyn_cast<Instruction>(constVal);
+  if (!inst)
+    return constVal;
+    
+  if (DT.dominates(inst, p))
+    if (isSafeReplacement(p, inst))
+      return inst;
   return 0;
 }
 
@@ -836,8 +801,8 @@ bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) {
 /// GetValueForBlock - Get the value to use within the specified basic block.
 /// available values are in Phis.
 Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
-                               DenseMap<BasicBlock*, Value*> &Phis,
-                               bool top_level) { 
+                             DenseMap<BasicBlock*, Value*> &Phis,
+                             bool top_level) { 
                                  
   // If we have already computed this value, return the previously computed val.
   DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB);
@@ -849,10 +814,11 @@ Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
     Phis[BB] = ret;
     return ret;
   }
+  
   // Otherwise, the idom is the loop, so we need to insert a PHI node.  Do so
   // now, then get values to fill in the incoming values for the PHI.
-  PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle",
-                            BB->begin());
+  PHINode *PN = PHINode::Create(orig->getType(), orig->getName()+".rle",
+                                BB->begin());
   PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB)));
   
   if (Phis.count(BB) == 0)
@@ -861,41 +827,40 @@ Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
   // Fill in the incoming values for the block.
   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
     Value* val = GetValueForBlock(*PI, orig, Phis);
-    
     PN->addIncoming(val, *PI);
   }
+  
   AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
   AA.copyValue(orig, PN);
   
   // Attempt to collapse PHI nodes that are trivially redundant
   Value* v = CollapsePhi(PN);
-  if (v) {
-    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
-
-    MD.removeInstruction(PN);
-    PN->replaceAllUsesWith(v);
-
-    for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
-         E = Phis.end(); I != E; ++I)
-      if (I->second == PN)
-        I->second = v;
+  if (!v) {
+    // Cache our phi construction results
+    phiMap[orig->getPointerOperand()].insert(PN);
+    return PN;
+  }
+    
+  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
 
-    PN->eraseFromParent();
+  MD.removeInstruction(PN);
+  PN->replaceAllUsesWith(v);
 
-    Phis[BB] = v;
+  for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
+       E = Phis.end(); I != E; ++I)
+    if (I->second == PN)
+      I->second = v;
 
-    return v;
-  }
+  PN->eraseFromParent();
 
-  // Cache our phi construction results
-  phiMap[orig->getPointerOperand()].insert(PN);
-  return PN;
+  Phis[BB] = v;
+  return v;
 }
 
 /// processNonLocalLoad - Attempt to eliminate a load whose dependencies are
 /// non-local by performing PHI construction.
 bool GVN::processNonLocalLoad(LoadInst* L,
-                              SmallVector<Instruction*, 4>& toErase) {
+                              SmallVectorImpl<Instruction*> &toErase) {
   MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
   
   // Find the non-local dependencies of the load
@@ -906,24 +871,25 @@ bool GVN::processNonLocalLoad(LoadInst* L,
   
   // Filter out useless results (non-locals, etc)
   for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end();
-       I != E; ++I)
-    if (I->second == MemoryDependenceAnalysis::None) {
+       I != E; ++I) {
+    if (I->second == MemoryDependenceAnalysis::None)
       return false;
-    } else if (I->second == MemoryDependenceAnalysis::NonLocal) {
+  
+    if (I->second == MemoryDependenceAnalysis::NonLocal)
       continue;
-    } else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) {
-      if (S->getPointerOperand() == L->getPointerOperand())
-        repl[I->first] = S->getOperand(0);
-      else
+  
+    if (StoreInst* S = dyn_cast<StoreInst>(I->second)) {
+      if (S->getPointerOperand() != L->getPointerOperand())
         return false;
+      repl[I->first] = S->getOperand(0);
     } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) {
-      if (LD->getPointerOperand() == L->getPointerOperand())
-        repl[I->first] = LD;
-      else
+      if (LD->getPointerOperand() != L->getPointerOperand())
         return false;
+      repl[I->first] = LD;
     } else {
       return false;
     }
+  }
   
   // Use cached PHI construction information from previous runs
   SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()];
@@ -934,11 +900,10 @@ bool GVN::processNonLocalLoad(LoadInst* L,
       L->replaceAllUsesWith(*I);
       toErase.push_back(L);
       NumGVNLoad++;
-      
       return true;
-    } else {
-      repl.insert(std::make_pair((*I)->getParent(), *I));
     }
+    
+    repl.insert(std::make_pair((*I)->getParent(), *I));
   }
   
   // Perform PHI construction
@@ -955,9 +920,8 @@ bool GVN::processNonLocalLoad(LoadInst* L,
 
 /// processLoad - Attempt to eliminate a load, first by eliminating it
 /// locally, and then attempting non-local elimination if that fails.
-bool GVN::processLoad(LoadInst* L,
-                         DenseMap<Value*, LoadInst*>& lastLoad,
-                         SmallVector<Instruction*, 4>& toErase) {
+bool GVN::processLoad(LoadInst *L, DenseMap<Value*, LoadInst*> &lastLoad,
+                      SmallVectorImpl<Instruction*> &toErase) {
   if (L->isVolatile()) {
     lastLoad[L->getPointerOperand()] = L;
     return false;
@@ -1055,192 +1019,49 @@ bool GVN::processLoad(LoadInst* L,
   return deletedLoad;
 }
 
-/// isReturnSlotOptznProfitable - Determine if performing a return slot 
-/// fusion with the slot dest is profitable
-static bool isReturnSlotOptznProfitable(Value* dest, MemCpyInst* cpy) {
-  // We currently consider it profitable if dest is otherwise dead.
-  SmallVector<User*, 8> useList(dest->use_begin(), dest->use_end());
-  while (!useList.empty()) {
-    User* UI = useList.back();
-    
-    if (isa<GetElementPtrInst>(UI) || isa<BitCastInst>(UI)) {
-      useList.pop_back();
-      for (User::use_iterator I = UI->use_begin(), E = UI->use_end();
-           I != E; ++I)
-        useList.push_back(*I);
-    } else if (UI == cpy)
-      useList.pop_back();
-    else
-      return false;
-  }
-  
-  return true;
-}
-
-/// performReturnSlotOptzn - takes a memcpy and a call that it depends on,
-/// and checks for the possibility of a return slot optimization by having
-/// the call write its result directly into the callees return parameter
-/// rather than using memcpy
-bool GVN::performReturnSlotOptzn(MemCpyInst* cpy, CallInst* C,
-                                 SmallVector<Instruction*, 4>& toErase) {
-  // Deliberately get the source and destination with bitcasts stripped away,
-  // because we'll need to do type comparisons based on the underlying type.
-  Value* cpyDest = cpy->getDest();
-  Value* cpySrc = cpy->getSource();
-  CallSite CS = CallSite::get(C);
-  
-  // Since this is a return slot optimization, we need to make sure that
-  // the value being copied is, in fact, in a return slot.  We also need to
-  // check that the return slot parameter is marked noalias, so that we can
-  // be sure that changing it will not cause unexpected behavior changes due
-  // to it being accessed through a global or another parameter.
-  if (CS.arg_size() == 0 ||
-      cpySrc != CS.getArgument(0) ||
-      !CS.paramHasAttr(1, ParamAttr::NoAlias | ParamAttr::StructRet))
-    return false;
-  
-  // Since we're changing the parameter to the callsite, we need to make sure
-  // that what would be the new parameter dominates the callsite.
-  DominatorTree& DT = getAnalysis<DominatorTree>();
-  if (Instruction* cpyDestInst = dyn_cast<Instruction>(cpyDest))
-    if (!DT.dominates(cpyDestInst, C))
-      return false;
-  
-  // Check that something sneaky is not happening involving casting
-  // return slot types around.
-  if (CS.getArgument(0)->getType() != cpyDest->getType())
-    return false;
-  // sret --> pointer
-  const PointerType* PT = cast<PointerType>(cpyDest->getType()); 
-  
-  // We can only perform the transformation if the size of the memcpy
-  // is constant and equal to the size of the structure.
-  ConstantInt* cpyLength = dyn_cast<ConstantInt>(cpy->getLength());
-  if (!cpyLength)
-    return false;
-  
-  TargetData& TD = getAnalysis<TargetData>();
-  if (TD.getTypeStoreSize(PT->getElementType()) != cpyLength->getZExtValue())
-    return false;
-  
-  // We only perform the transformation if it will be profitable. 
-  if (!isReturnSlotOptznProfitable(cpyDest, cpy))
-    return false;
-  
-  // In addition to knowing that the call does not access the return slot
-  // in some unexpected manner, which we derive from the noalias attribute,
-  // we also need to know that it does not sneakily modify the destination
-  // slot in the caller.  We don't have parameter attributes to go by
-  // for this one, so we just rely on AA to figure it out for us.
-  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
-  if (AA.getModRefInfo(C, cpy->getRawDest(), cpyLength->getZExtValue()) !=
-      AliasAnalysis::NoModRef)
-    return false;
-  
-  // If all the checks have passed, then we're alright to do the transformation.
-  CS.setArgument(0, cpyDest);
-  
-  // Drop any cached information about the call, because we may have changed
-  // its dependence information by changing its parameter.
-  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
-  MD.dropInstruction(C);
-  
-  // Remove the memcpy
-  MD.removeInstruction(cpy);
-  toErase.push_back(cpy);
-  
-  return true;
-}
-
-/// processMemCpy - perform simplication of memcpy's.  If we have memcpy A which
-/// copies X to Y, and memcpy B which copies Y to Z, then we can rewrite B to be
-/// a memcpy from X to Z (or potentially a memmove, depending on circumstances).
-///  This allows later passes to remove the first memcpy altogether.
-bool GVN::processMemCpy(MemCpyInst* M, MemCpyInst* MDep,
-                        SmallVector<Instruction*, 4>& toErase) {
-  // We can only transforms memcpy's where the dest of one is the source of the
-  // other
-  if (M->getSource() != MDep->getDest())
-    return false;
-  
-  // Second, the length of the memcpy's must be the same, or the preceeding one
-  // must be larger than the following one.
-  ConstantInt* C1 = dyn_cast<ConstantInt>(MDep->getLength());
-  ConstantInt* C2 = dyn_cast<ConstantInt>(M->getLength());
-  if (!C1 || !C2)
-    return false;
-  
-  uint64_t CpySize = C1->getValue().getZExtValue();
-  uint64_t DepSize = C2->getValue().getZExtValue();
-  
-  if (DepSize < CpySize)
-    return false;
-  
-  // Finally, we have to make sure that the dest of the second does not
-  // alias the source of the first
-  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
-  if (AA.alias(M->getRawDest(), CpySize, MDep->getRawSource(), DepSize) !=
-      AliasAnalysis::NoAlias)
-    return false;
-  else if (AA.alias(M->getRawDest(), CpySize, M->getRawSource(), CpySize) !=
-           AliasAnalysis::NoAlias)
-    return false;
-  else if (AA.alias(MDep->getRawDest(), DepSize, MDep->getRawSource(), DepSize)
-           != AliasAnalysis::NoAlias)
-    return false;
-  
-  // If all checks passed, then we can transform these memcpy's
-  Function* MemCpyFun = Intrinsic::getDeclaration(
-                                 M->getParent()->getParent()->getParent(),
-                                 M->getIntrinsicID());
-    
-  std::vector<Value*> args;
-  args.push_back(M->getRawDest());
-  args.push_back(MDep->getRawSource());
-  args.push_back(M->getLength());
-  args.push_back(M->getAlignment());
+Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) {
+  DenseMap<BasicBlock*, ValueNumberScope*>::iterator I = localAvail.find(BB);
+  if (I == localAvail.end())
+    return 0;
   
-  CallInst* C = new CallInst(MemCpyFun, args.begin(), args.end(), "", M);
+  ValueNumberScope* locals = I->second;
   
-  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
-  if (MD.getDependency(C) == MDep) {
-    MD.dropInstruction(M);
-    toErase.push_back(M);
-    return true;
-  } else {
-    MD.removeInstruction(C);
-    toErase.push_back(C);
-    return false;
+  while (locals) {
+    DenseMap<uint32_t, Value*>::iterator I = locals->table.find(num);
+    if (I != locals->table.end())
+      return I->second;
+    else
+      locals = locals->parent;
   }
+  
+  return 0;
 }
 
 /// processInstruction - When calculating availability, handle an instruction
 /// by inserting it into the appropriate sets
-bool GVN::processInstruction(Instruction* I,
-                                ValueNumberedSet& currAvail,
-                                DenseMap<Value*, LoadInst*>& lastSeenLoad,
-                                SmallVector<Instruction*, 4>& toErase) {
+bool GVN::processInstruction(Instruction *I,
+                             DenseMap<Value*, LoadInst*> &lastSeenLoad,
+                             SmallVectorImpl<Instruction*> &toErase) {
   if (LoadInst* L = dyn_cast<LoadInst>(I)) {
-    return processLoad(L, lastSeenLoad, toErase);
-  } else if (MemCpyInst* M = dyn_cast<MemCpyInst>(I)) {
-    MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
-
-    // The are two possible optimizations we can do for memcpy:
-    //   a) memcpy-memcpy xform which exposes redundance for DSE
-    //   b) call-memcpy xform for sret return slot optimization
-    Instruction* dep = MD.getDependency(M);
-    if (dep == MemoryDependenceAnalysis::None ||
-        dep == MemoryDependenceAnalysis::NonLocal)
-      return false;
-    if (MemCpyInst *MemCpy = dyn_cast<MemCpyInst>(dep))
-      return processMemCpy(M, MemCpy, toErase);
-    if (CallInst* C = dyn_cast<CallInst>(dep))
-      return performReturnSlotOptzn(M, C, toErase);
-    return false;
+    bool changed = processLoad(L, lastSeenLoad, toErase);
+    
+    if (!changed) {
+      unsigned num = VN.lookup_or_add(L);
+      localAvail[I->getParent()]->table.insert(std::make_pair(num, L));
+    }
+    
+    return changed;
   }
   
   unsigned num = VN.lookup_or_add(I);
   
+  // Allocations are always uniquely numbered, so we can save time and memory
+  // by fast failing them.
+  if (isa<AllocationInst>(I)) {
+    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
+    return false;
+  }
+  
   // Collapse PHI nodes
   if (PHINode* p = dyn_cast<PHINode>(I)) {
     Value* constVal = CollapsePhi(p);
@@ -1253,27 +1074,11 @@ bool GVN::processInstruction(Instruction* I,
         
       p->replaceAllUsesWith(constVal);
       toErase.push_back(p);
+    } else {
+      localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
     }
   // Perform value-number based elimination
-  } else if (currAvail.test(num)) {
-    Value* repl = find_leader(currAvail, num);
-    
-    if (CallInst* CI = dyn_cast<CallInst>(I)) {
-      AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
-      if (!AA.doesNotAccessMemory(CI)) {
-        MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
-        if (cast<Instruction>(repl)->getParent() != CI->getParent() ||
-            MD.getDependency(CI) != MD.getDependency(cast<CallInst>(repl))) {
-          // There must be an intervening may-alias store, so nothing from
-          // this point on will be able to be replaced with the preceding call
-          currAvail.erase(repl);
-          currAvail.insert(I);
-          
-          return false;
-        }
-      }
-    }
-    
+  } else if (Value* repl = lookupNumber(I->getParent(), num)) {
     // Remove it!
     MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
     MD.removeInstruction(I);
@@ -1283,8 +1088,7 @@ bool GVN::processInstruction(Instruction* I,
     toErase.push_back(I);
     return true;
   } else if (!I->isTerminator()) {
-    currAvail.set(num);
-    currAvail.insert(I);
+    localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
   }
   
   return false;
@@ -1295,6 +1099,8 @@ bool GVN::processInstruction(Instruction* I,
 //
 bool GVN::runOnFunction(Function& F) {
   VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>());
+  VN.setMemDep(&getAnalysis<MemoryDependenceAnalysis>());
+  VN.setDomTree(&getAnalysis<DominatorTree>());
   
   bool changed = false;
   bool shouldContinue = true;
@@ -1308,51 +1114,220 @@ bool GVN::runOnFunction(Function& F) {
 }
 
 
-// GVN::iterateOnFunction - Executes one iteration of GVN
-bool GVN::iterateOnFunction(Function &F) {
-  // Clean out global sets from any previous functions
-  VN.clear();
-  availableOut.clear();
-  phiMap.clear();
- 
+bool GVN::processBlock(DomTreeNode* DTN) {
+  BasicBlock* BB = DTN->getBlock();
+
+  SmallVector<Instruction*, 8> toErase;
+  DenseMap<Value*, LoadInst*> lastSeenLoad;
   bool changed_function = false;
   
-  DominatorTree &DT = getAnalysis<DominatorTree>();   
-  
-  SmallVector<Instruction*, 4> toErase;
+  if (DTN->getIDom())
+    localAvail[BB] =
+                  new ValueNumberScope(localAvail[DTN->getIDom()->getBlock()]);
+  else
+    localAvail[BB] = new ValueNumberScope(0);
   
-  // Top-down walk of the dominator tree
-  for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
-         E = df_end(DT.getRootNode()); DI != E; ++DI) {
+  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
+       BI != BE;) {
+    changed_function |= processInstruction(BI, lastSeenLoad, toErase);
+    if (toErase.empty()) {
+      ++BI;
+      continue;
+    }
     
-    // Get the set to update for this block
-    ValueNumberedSet& currAvail = availableOut[DI->getBlock()];     
-    DenseMap<Value*, LoadInst*> lastSeenLoad;
+    // If we need some instructions deleted, do it now.
+    NumGVNInstr += toErase.size();
+    
+    // Avoid iterator invalidation.
+    bool AtStart = BI == BB->begin();
+    if (!AtStart)
+      --BI;
+
+    for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(),
+         E = toErase.end(); I != E; ++I)
+      (*I)->eraseFromParent();
+
+    if (AtStart)
+      BI = BB->begin();
+    else
+      ++BI;
     
-    BasicBlock* BB = DI->getBlock();
+    toErase.clear();
+  }
   
-    // A block inherits AVAIL_OUT from its dominator
-    if (DI->getIDom() != 0)
-      currAvail = availableOut[DI->getIDom()->getBlock()];
+  return changed_function;
+}
 
-    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
-         BI != BE; ) {
-      changed_function |= processInstruction(BI, currAvail,
-                                             lastSeenLoad, toErase);
+/// performPRE - Perform a purely local form of PRE that looks for diamond
+/// control flow patterns and attempts to perform simple PRE at the join point.
+bool GVN::performPRE(Function& F) {
+  bool changed = false;
+  SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit;
+  for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()),
+       DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) {
+    BasicBlock* CurrentBlock = *DI;
+    
+    // Nothing to PRE in the entry block.
+    if (CurrentBlock == &F.getEntryBlock()) continue;
+    
+    for (BasicBlock::iterator BI = CurrentBlock->begin(),
+         BE = CurrentBlock->end(); BI != BE; ) {
+      if (isa<AllocationInst>(BI) || isa<TerminatorInst>(BI) ||
+          isa<PHINode>(BI) || BI->mayReadFromMemory() ||
+          BI->mayWriteToMemory()) {
+        BI++;
+        continue;
+      }
       
-      NumGVNInstr += toErase.size();
+      uint32_t valno = VN.lookup(BI);
       
-      // Avoid iterator invalidation
-      ++BI;
-
-      for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(),
-           E = toErase.end(); I != E; ++I) {
-        (*I)->eraseFromParent();
+      // Look for the predecessors for PRE opportunities.  We're
+      // only trying to solve the basic diamond case, where
+      // a value is computed in the successor and one predecessor,
+      // but not the other.  We also explicitly disallow cases
+      // where the successor is its own predecessor, because they're
+      // more complicated to get right.
+      unsigned numWith = 0;
+      unsigned numWithout = 0;
+      BasicBlock* PREPred = 0;
+      DenseMap<BasicBlock*, Value*> predMap;
+      for (pred_iterator PI = pred_begin(CurrentBlock),
+           PE = pred_end(CurrentBlock); PI != PE; ++PI) {
+        // We're not interested in PRE where the block is its
+        // own predecessor, on in blocks with predecessors
+        // that are not reachable.
+        if (*PI == CurrentBlock) {
+          numWithout = 2;
+          break;
+        } else if (!localAvail.count(*PI))  {
+          numWithout = 2;
+          break;
+        }
+        
+        DenseMap<uint32_t, Value*>::iterator predV = 
+                                            localAvail[*PI]->table.find(valno);
+        if (predV == localAvail[*PI]->table.end()) {
+          PREPred = *PI;
+          numWithout++;
+        } else if (predV->second == BI) {
+          numWithout = 2;
+        } else {
+          predMap[*PI] = predV->second;
+          numWith++;
+        }
       }
-
-      toErase.clear();
+      
+      // Don't do PRE when it might increase code size, i.e. when
+      // we would need to insert instructions in more than one pred.
+      if (numWithout != 1 || numWith == 0) {
+        BI++;
+        continue;
+      }
+      
+      // We can't do PRE safely on a critical edge, so instead we schedule
+      // the edge to be split and perform the PRE the next time we iterate
+      // on the function.
+      unsigned succNum = 0;
+      for (unsigned i = 0, e = PREPred->getTerminator()->getNumSuccessors();
+           i != e; ++i)
+        if (PREPred->getTerminator()->getSuccessor(i) == PREPred) {
+          succNum = i;
+          break;
+        }
+        
+      if (isCriticalEdge(PREPred->getTerminator(), succNum)) {
+        toSplit.push_back(std::make_pair(PREPred->getTerminator(), succNum));
+        changed = true;
+        BI++;
+        continue;
+      }
+      
+      // Instantiate the expression the in predecessor that lacked it.
+      // Because we are going top-down through the block, all value numbers
+      // will be available in the predecessor by the time we need them.  Any
+      // that weren't original present will have been instantiated earlier
+      // in this loop.
+      Instruction* PREInstr = BI->clone();
+      bool success = true;
+      for (unsigned i = 0; i < BI->getNumOperands(); ++i) {
+        Value* op = BI->getOperand(i);
+        if (isa<Argument>(op) || isa<Constant>(op) || isa<GlobalValue>(op))
+          PREInstr->setOperand(i, op);
+        else if (!lookupNumber(PREPred, VN.lookup(op))) {
+          success = false;
+          break;
+        } else
+          PREInstr->setOperand(i, lookupNumber(PREPred, VN.lookup(op)));
+      }
+      
+      // Fail out if we encounter an operand that is not available in
+      // the PRE predecessor.  This is typically because of loads which 
+      // are not value numbered precisely.
+      if (!success) {
+        delete PREInstr;
+        BI++;
+        continue;
+      }
+      
+      PREInstr->insertBefore(PREPred->getTerminator());
+      PREInstr->setName(BI->getName() + ".pre");
+      predMap[PREPred] = PREInstr;
+      VN.add(PREInstr, valno);
+      NumGVNPRE++;
+      
+      // Update the availability map to include the new instruction.
+      localAvail[PREPred]->table.insert(std::make_pair(valno, PREInstr));
+      
+      // Create a PHI to make the value available in this block.
+      PHINode* Phi = PHINode::Create(BI->getType(),
+                                     BI->getName() + ".pre-phi",
+                                     CurrentBlock->begin());
+      for (pred_iterator PI = pred_begin(CurrentBlock),
+           PE = pred_end(CurrentBlock); PI != PE; ++PI)
+        Phi->addIncoming(predMap[*PI], *PI);
+      
+      VN.add(Phi, valno);
+      localAvail[CurrentBlock]->table[valno] = Phi;
+      
+      BI->replaceAllUsesWith(Phi);
+      VN.erase(BI);
+      
+      Instruction* erase = BI;
+      BI++;
+      erase->eraseFromParent();
+      
+      changed = true;
     }
   }
   
-  return changed_function;
+  for (SmallVector<std::pair<TerminatorInst*, unsigned>, 4>::iterator
+       I = toSplit.begin(), E = toSplit.end(); I != E; ++I)
+    SplitCriticalEdge(I->first, I->second, this);
+  
+  return changed;
+}
+
+// GVN::iterateOnFunction - Executes one iteration of GVN
+bool GVN::iterateOnFunction(Function &F) {
+  // Clean out global sets from any previous functions
+  VN.clear();
+  phiMap.clear();
+  
+  for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator
+       I = localAvail.begin(), E = localAvail.end(); I != E; ++I)
+    delete I->second;
+  localAvail.clear();
+  
+  DominatorTree &DT = getAnalysis<DominatorTree>();   
+
+  // Top-down walk of the dominator tree
+  bool changed = false;
+  for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
+       DE = df_end(DT.getRootNode()); DI != DE; ++DI)
+    changed |= processBlock(*DI);
+  
+  if (EnablePRE)
+    changed |= performPRE(F);
+  
+  return changed;
 }