X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FABCD.cpp;h=20f90839c97da186d2f245f3fad3a1eaaf3d36d7;hp=a644973f9a0b647903a2924fb0c39dcf4aa84a3c;hb=1f74590e9d1b9cf0f1f81a156efea73f76546e05;hpb=40cc524edee857eab238338200d2cc80f840f52f

diff --git a/lib/Transforms/Scalar/ABCD.cpp b/lib/Transforms/Scalar/ABCD.cpp
index a644973f9a0..20f90839c97 100644
--- a/lib/Transforms/Scalar/ABCD.cpp
+++ b/lib/Transforms/Scalar/ABCD.cpp
@@ -14,7 +14,7 @@
 // languages. This implementation expands the idea and removes any conditional
 // branches that can be proved redundant, not only those used in array bound
 // checks. With the SSI representation, each variable has a
-// constraint. By analyzing these constraints we can proof that a branch is
+// constraint. By analyzing these constraints we can prove that a branch is
 // redundant. When a branch is proved redundant it means that
 // one direction will always be taken; thus, we can change this branch into an
 // unconditional jump.
@@ -27,6 +27,7 @@
 
 #define DEBUG_TYPE "abcd"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/OwningPtr.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Constants.h"
@@ -43,7 +44,7 @@ using namespace llvm;
 STATISTIC(NumBranchTested, "Number of conditional branches analyzed");
 STATISTIC(NumBranchRemoved, "Number of conditional branches removed");
 
-//namespace {
+namespace {
 
 class ABCD : public FunctionPass {
  public:
@@ -57,6 +58,7 @@ class ABCD : public FunctionPass {
   bool runOnFunction(Function &F);
 
  private:
+  /// Keep track of whether we've modified the program yet.
   bool modified;
 
   enum ProveResult {
@@ -76,10 +78,10 @@ class ABCD : public FunctionPass {
   class Bound {
    public:
     Bound(APInt v, bool upper) : value(v), upper_bound(upper) {}
-    Bound(const Bound *b, int cnst)
-      : value(b->value - cnst), upper_bound(b->upper_bound) {}
-    Bound(const Bound *b, const APInt &cnst)
-      : value(b->value - cnst), upper_bound(b->upper_bound) {}
+    Bound(const Bound &b, int cnst)
+      : value(b.value - cnst), upper_bound(b.upper_bound) {}
+    Bound(const Bound &b, const APInt &cnst)
+      : value(b.value - cnst), upper_bound(b.upper_bound) {}
 
     /// Test if Bound is an upper bound
     bool isUpperBound() const { return upper_bound; }
@@ -88,15 +90,15 @@ class ABCD : public FunctionPass {
     int32_t getBitWidth() const { return value.getBitWidth(); }
 
     /// Creates a Bound incrementing the one received
-    static Bound *createIncrement(const Bound *b) {
-      return new Bound(b->isUpperBound() ? b->value+1 : b->value-1,
-                       b->upper_bound);
+    static Bound createIncrement(const Bound &b) {
+      return Bound(b.isUpperBound() ? b.value+1 : b.value-1,
+                   b.upper_bound);
     }
 
     /// Creates a Bound decrementing the one received
-    static Bound *createDecrement(const Bound *b) {
-      return new Bound(b->isUpperBound() ? b->value-1 : b->value+1,
-                       b->upper_bound);
+    static Bound createDecrement(const Bound &b) {
+      return Bound(b.isUpperBound() ? b.value-1 : b.value+1,
+                   b.upper_bound);
     }
 
     /// Test if two bounds are equal
@@ -108,36 +110,31 @@ class ABCD : public FunctionPass {
     }
 
     /// Test if val is less than or equal to Bound b
-    static bool leq(APInt val, const Bound *b) {
-      if (!b) return false;
-      return b->isUpperBound() ? val.sle(b->value) : val.sge(b->value);
+    static bool leq(APInt val, const Bound &b) {
+      return b.isUpperBound() ? val.sle(b.value) : val.sge(b.value);
     }
 
     /// Test if Bound a is less then or equal to Bound
-    static bool leq(const Bound *a, const Bound *b) {
-      if (!a || !b) return false;
-
-      assert(a->isUpperBound() == b->isUpperBound());
-      return a->isUpperBound() ? a->value.sle(b->value) :
-                                 a->value.sge(b->value);
+    static bool leq(const Bound &a, const Bound &b) {
+      assert(a.isUpperBound() == b.isUpperBound());
+      return a.isUpperBound() ? a.value.sle(b.value) :
+                                a.value.sge(b.value);
     }
 
     /// Test if Bound a is less then Bound b
-    static bool lt(const Bound *a, const Bound *b) {
-      if (!a || !b) return false;
-
-      assert(a->isUpperBound() == b->isUpperBound());
-      return a->isUpperBound() ? a->value.slt(b->value) :
-                                 a->value.sgt(b->value);
+    static bool lt(const Bound &a, const Bound &b) {
+      assert(a.isUpperBound() == b.isUpperBound());
+      return a.isUpperBound() ? a.value.slt(b.value) :
+                                a.value.sgt(b.value);
     }
 
     /// Test if Bound b is greater then or equal val
-    static bool geq(const Bound *b, APInt val) {
+    static bool geq(const Bound &b, APInt val) {
       return leq(val, b);
     }
 
     /// Test if Bound a is greater then or equal Bound b
-    static bool geq(const Bound *a, const Bound *b) {
+    static bool geq(const Bound &a, const Bound &b) {
       return leq(b, a);
     }
 
@@ -151,29 +148,36 @@ class ABCD : public FunctionPass {
   /// minimum true and minimum reduced results are stored
   class MemoizedResultChart {
    public:
-     MemoizedResultChart() : max_false(NULL), min_true(NULL),
-			     min_reduced(NULL) {}
+     MemoizedResultChart() {}
+     MemoizedResultChart(const MemoizedResultChart &other) {
+       if (other.max_false)
+         max_false.reset(new Bound(*other.max_false));
+       if (other.min_true)
+         min_true.reset(new Bound(*other.min_true));
+       if (other.min_reduced)
+         min_reduced.reset(new Bound(*other.min_reduced));
+     }
 
     /// Returns the max false
-    Bound *getFalse() const { return max_false; }
+    const Bound *getFalse() const { return max_false.get(); }
 
     /// Returns the min true
-    Bound *getTrue() const { return min_true; }
+    const Bound *getTrue() const { return min_true.get(); }
 
     /// Returns the min reduced
-    Bound *getReduced() const { return min_reduced; }
+    const Bound *getReduced() const { return min_reduced.get(); }
 
     /// Return the stored result for this bound
-    ProveResult getResult(const Bound *bound) const;
+    ProveResult getResult(const Bound &bound) const;
 
     /// Stores a false found
-    void addFalse(Bound *bound);
+    void addFalse(const Bound &bound);
 
     /// Stores a true found
-    void addTrue(Bound *bound);
+    void addTrue(const Bound &bound);
 
     /// Stores a Reduced found
-    void addReduced(Bound *bound);
+    void addReduced(const Bound &bound);
 
     /// Clears redundant reduced
     /// If a min_true is smaller than a min_reduced then the min_reduced
@@ -182,42 +186,42 @@ class ABCD : public FunctionPass {
     void clearRedundantReduced();
 
     void clear() {
-      delete max_false;
-      delete min_true;
-      delete min_reduced;
+      max_false.reset();
+      min_true.reset();
+      min_reduced.reset();
     }
 
   private:
-    Bound *max_false, *min_true, *min_reduced;
+    OwningPtr<Bound> max_false, min_true, min_reduced;
   };
 
   /// This class stores the result found for a node of the graph,
-  /// so these results do not need to be recalculate and only searched for.
+  /// so these results do not need to be recalculated, only searched for.
   class MemoizedResult {
   public:
     /// Test if there is true result stored from b to a
     /// that is less then the bound
-    bool hasTrue(Value *b, const Bound *bound) const {
-      Bound *trueBound = map.lookup(b).getTrue();
-      return trueBound && Bound::leq(trueBound, bound);
+    bool hasTrue(Value *b, const Bound &bound) const {
+      const Bound *trueBound = map.lookup(b).getTrue();
+      return trueBound && Bound::leq(*trueBound, bound);
     }
 
     /// Test if there is false result stored from b to a
     /// that is less then the bound
-    bool hasFalse(Value *b, const Bound *bound) const {
-      Bound *falseBound = map.lookup(b).getFalse();
-      return falseBound && Bound::leq(falseBound, bound);
+    bool hasFalse(Value *b, const Bound &bound) const {
+      const Bound *falseBound = map.lookup(b).getFalse();
+      return falseBound && Bound::leq(*falseBound, bound);
     }
 
     /// Test if there is reduced result stored from b to a
     /// that is less then the bound
-    bool hasReduced(Value *b, const Bound *bound) const {
-      Bound *reducedBound = map.lookup(b).getReduced();
-      return reducedBound && Bound::leq(reducedBound, bound);
+    bool hasReduced(Value *b, const Bound &bound) const {
+      const Bound *reducedBound = map.lookup(b).getReduced();
+      return reducedBound && Bound::leq(*reducedBound, bound);
     }
 
     /// Returns the stored bound for b
-    ProveResult getBoundResult(Value *b, Bound *bound) {
+    ProveResult getBoundResult(Value *b, const Bound &bound) {
       return map[b].getResult(bound);
     }
 
@@ -226,13 +230,13 @@ class ABCD : public FunctionPass {
       DenseMapIterator<Value*, MemoizedResultChart> begin = map.begin();
       DenseMapIterator<Value*, MemoizedResultChart> end = map.end();
       for (; begin != end; ++begin) {
-	begin->second.clear();
+        begin->second.clear();
       }
       map.clear();
     }
 
     /// Stores the bound found
-    void updateBound(Value *b, Bound *bound, const ProveResult res);
+    void updateBound(Value *b, const Bound &bound, const ProveResult res);
 
   private:
     // Maps a nod in the graph with its results found.
@@ -244,9 +248,8 @@ class ABCD : public FunctionPass {
   /// we could infer a constraint v <= u + c in the source program.
   class Edge {
   public:
-    Edge(Value *V, APInt val, bool upper) : vertex(V), value(val),
-					    upper_bound(upper)
-    {}
+    Edge(Value *V, APInt val, bool upper)
+      : vertex(V), value(val), upper_bound(upper) {}
 
     Value *getVertex() const { return vertex; }
     const APInt &getValue() const { return value; }
@@ -274,7 +277,7 @@ class ABCD : public FunctionPass {
     bool hasEdge(Value *V, bool upper) const;
 
     /// Returns all edges pointed by vertex V
-    SmallPtrSet<Edge *, 16> getEdges(Value *V) const {
+    SmallVector<Edge, 16> getEdges(Value *V) const {
       return graph.lookup(V);
     }
 
@@ -292,13 +295,7 @@ class ABCD : public FunctionPass {
     }
 
   private:
-    DenseMap<Value *, SmallPtrSet<Edge *, 16> > graph;
-
-    /// Adds a Node to the graph.
-    DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator addNode(Value *V) {
-      SmallPtrSet<Edge *, 16> p;
-      return graph.insert(std::make_pair(V, p)).first;
-    }
+    DenseMap<Value *, SmallVector<Edge, 16> > graph;
 
     /// Prints the header of the dot file
     void printHeader(raw_ostream &OS, Function &F) const;
@@ -315,7 +312,7 @@ class ABCD : public FunctionPass {
     void printVertex(raw_ostream &OS, Value *source) const;
 
     /// Prints the edge to the dot file
-    void printEdge(raw_ostream &OS, Value *source, Edge *edge) const;
+    void printEdge(raw_ostream &OS, Value *source, const Edge &edge) const;
 
     void printName(raw_ostream &OS, Value *info) const;
   };
@@ -399,8 +396,8 @@ class ABCD : public FunctionPass {
   /// this case the method returns true, otherwise false. It also obtains the
   /// Instruction and ConstantInt from the BinaryOperator and returns it.
   bool createBinaryOperatorInfo(BinaryOperator *BO, Instruction **I1,
-				Instruction **I2, ConstantInt **C1,
-				ConstantInt **C2);
+                                Instruction **I2, ConstantInt **C1,
+                                ConstantInt **C2);
 
   /// This method creates a constraint between a Sigma and an Instruction.
   /// These constraints are created as soon as we find a comparator that uses a
@@ -412,7 +409,9 @@ class ABCD : public FunctionPass {
   /// If PN_op1 and PN_o2 are different from NULL, create a constraint
   /// PN_op2 -> PN_op1 with value. In case any of them is NULL, replace
   /// with the respective V_op#, if V_op# is a ConstantInt.
-  void createConstraintSigSig(PHINode *SIG_op1, PHINode *SIG_op2, APInt value);
+  void createConstraintSigSig(PHINode *SIG_op1, PHINode *SIG_op2, 
+                              ConstantInt *V_op1, ConstantInt *V_op2,
+                              APInt value);
 
   /// Returns the sigma representing the Instruction I in BasicBlock BB.
   /// Returns NULL in case there is no sigma for this Instruction in this
@@ -426,30 +425,31 @@ class ABCD : public FunctionPass {
   bool demandProve(Value *a, Value *b, int c, bool upper_bound);
 
   /// Prove that distance between b and a is <= bound
-  ProveResult prove(Value *a, Value *b, Bound *bound, unsigned level);
+  ProveResult prove(Value *a, Value *b, const Bound &bound, unsigned level);
 
   /// Updates the distance value for a and b
-  void updateMemDistance(Value *a, Value *b, Bound *bound, unsigned level,
+  void updateMemDistance(Value *a, Value *b, const Bound &bound, unsigned level,
                          meet_function meet);
 
   InequalityGraph inequality_graph;
   MemoizedResult mem_result;
-  DenseMap<Value*, Bound*> active;
+  DenseMap<Value*, const Bound*> active;
   SmallPtrSet<Value*, 16> created;
   SmallVector<PHINode *, 16> phis_to_remove;
 };
 
-//}  // end anonymous namespace.
+}  // end anonymous namespace.
 
 char ABCD::ID = 0;
-static RegisterPass<ABCD> X("abcd", "ABCD: Eliminating Array Bounds Checks on Demand");
-
+INITIALIZE_PASS(ABCD, "abcd",
+                "ABCD: Eliminating Array Bounds Checks on Demand",
+                false, false);
 
 bool ABCD::runOnFunction(Function &F) {
   modified = false;
   createSSI(F);
   executeABCD(F);
-  DEBUG(inequality_graph.printGraph(errs(), F));
+  DEBUG(inequality_graph.printGraph(dbgs(), F));
   removePhis();
 
   inequality_graph.clear();
@@ -503,7 +503,7 @@ void ABCD::executeABCD(Function &F) {
       continue;
 
     ICmpInst *ICI = dyn_cast<ICmpInst>(TI->getOperand(0));
-    if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType()))
+    if (!ICI || !ICI->getOperand(0)->getType()->isIntegerTy())
       continue;
 
     createConstraintCmpInst(ICI, TI);
@@ -600,7 +600,7 @@ void ABCD::fixPhi(BasicBlock *BB, BasicBlock *Succ) {
 
 /// Removes phis that have no predecessor
 void ABCD::removePhis() {
-  for (unsigned i = 0, end = phis_to_remove.size(); i < end; ++i) {
+  for (unsigned i = 0, e = phis_to_remove.size(); i != e; ++i) {
     PHINode *PN = phis_to_remove[i];
     PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
     PN->eraseFromParent();
@@ -666,9 +666,8 @@ void ABCD::createConstraintBinaryOperator(BinaryOperator *BO) {
       return;
   }
 
-  APInt MinusOne = APInt::getAllOnesValue(value.getBitWidth());
   inequality_graph.addEdge(I, BO, value, true);
-  inequality_graph.addEdge(BO, I, value * MinusOne, false);
+  inequality_graph.addEdge(BO, I, -value, false);
   createConstraintInstruction(I);
 }
 
@@ -712,7 +711,7 @@ void ABCD::createConstraintCmpInst(ICmpInst *ICI, TerminatorInst *TI) {
   Value *V_op1 = ICI->getOperand(0);
   Value *V_op2 = ICI->getOperand(1);
 
-  if (!isa<IntegerType>(V_op1->getType()))
+  if (!V_op1->getType()->isIntegerTy())
     return;
 
   Instruction *I_op1 = dyn_cast<Instruction>(V_op1);
@@ -728,35 +727,35 @@ void ABCD::createConstraintCmpInst(ICmpInst *ICI, TerminatorInst *TI) {
   PHINode *SIG_op1_t = NULL, *SIG_op1_f = NULL,
           *SIG_op2_t = NULL, *SIG_op2_f = NULL;
 
-  createConstraintSigInst(I_op1, BB_succ_t, BB_succ_f,
-                          &SIG_op1_t, &SIG_op1_f);
-  createConstraintSigInst(I_op2, BB_succ_t, BB_succ_f,
-                          &SIG_op2_t, &SIG_op2_f);
+  createConstraintSigInst(I_op1, BB_succ_t, BB_succ_f, &SIG_op1_t, &SIG_op1_f);
+  createConstraintSigInst(I_op2, BB_succ_t, BB_succ_f, &SIG_op2_t, &SIG_op2_f);
 
   int32_t width = cast<IntegerType>(V_op1->getType())->getBitWidth();
   APInt MinusOne = APInt::getAllOnesValue(width);
   APInt Zero = APInt::getNullValue(width);
 
   CmpInst::Predicate Pred = ICI->getPredicate();
+  ConstantInt *CI1 = dyn_cast<ConstantInt>(V_op1);
+  ConstantInt *CI2 = dyn_cast<ConstantInt>(V_op2);
   switch (Pred) {
-  case CmpInst::ICMP_SGT: // signed greater than
-    createConstraintSigSig(SIG_op2_t, SIG_op1_t, MinusOne);
-    createConstraintSigSig(SIG_op1_f, SIG_op2_f, Zero);
+  case CmpInst::ICMP_SGT:  // signed greater than
+    createConstraintSigSig(SIG_op2_t, SIG_op1_t, CI2, CI1, MinusOne);
+    createConstraintSigSig(SIG_op1_f, SIG_op2_f, CI1, CI2, Zero);
     break;
 
-  case CmpInst::ICMP_SGE: // signed greater or equal
-    createConstraintSigSig(SIG_op2_t, SIG_op1_t, Zero);
-    createConstraintSigSig(SIG_op1_f, SIG_op2_f, MinusOne);
+  case CmpInst::ICMP_SGE:  // signed greater or equal
+    createConstraintSigSig(SIG_op2_t, SIG_op1_t, CI2, CI1, Zero);
+    createConstraintSigSig(SIG_op1_f, SIG_op2_f, CI1, CI2, MinusOne);
     break;
 
-  case CmpInst::ICMP_SLT: // signed less than
-    createConstraintSigSig(SIG_op1_t, SIG_op2_t, MinusOne);
-    createConstraintSigSig(SIG_op2_f, SIG_op1_f, Zero);
+  case CmpInst::ICMP_SLT:  // signed less than
+    createConstraintSigSig(SIG_op1_t, SIG_op2_t, CI1, CI2, MinusOne);
+    createConstraintSigSig(SIG_op2_f, SIG_op1_f, CI2, CI1, Zero);
     break;
 
-  case CmpInst::ICMP_SLE: // signed less or equal
-    createConstraintSigSig(SIG_op1_t, SIG_op2_t, Zero);
-    createConstraintSigSig(SIG_op2_f, SIG_op1_f, MinusOne);
+  case CmpInst::ICMP_SLE:  // signed less or equal
+    createConstraintSigSig(SIG_op1_t, SIG_op2_t, CI1, CI2, Zero);
+    createConstraintSigSig(SIG_op2_f, SIG_op1_f, CI2, CI1, MinusOne);
     break;
 
   default:
@@ -775,8 +774,12 @@ void ABCD::createConstraintCmpInst(ICmpInst *ICI, TerminatorInst *TI) {
 /// b->a and c->a with weight 0 in the lower bound graph, and the edges
 /// a->b and a->c with weight 0 in the upper bound graph.
 void ABCD::createConstraintPHINode(PHINode *PN) {
+  // FIXME: We really want to disallow sigma nodes, but I don't know the best
+  // way to detect the other than this.
+  if (PN->getNumOperands() == 2) return;
+  
   int32_t width = cast<IntegerType>(PN->getType())->getBitWidth();
-  for (unsigned i = 0, end = PN->getNumIncomingValues(); i < end; ++i) {
+  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     Value *V = PN->getIncomingValue(i);
     if (Instruction *I = dyn_cast<Instruction>(V)) {
       createConstraintInstruction(I);
@@ -799,13 +802,11 @@ void ABCD::createConstraintSigInst(Instruction *I_op, BasicBlock *BB_succ_t,
     int32_t width = cast<IntegerType>((*SIG_op_t)->getType())->getBitWidth();
     inequality_graph.addEdge(I_op, *SIG_op_t, APInt(width, 0), true);
     inequality_graph.addEdge(*SIG_op_t, I_op, APInt(width, 0), false);
-    created.insert(*SIG_op_t);
   }
   if (*SIG_op_f) {
     int32_t width = cast<IntegerType>((*SIG_op_f)->getType())->getBitWidth();
     inequality_graph.addEdge(I_op, *SIG_op_f, APInt(width, 0), true);
     inequality_graph.addEdge(*SIG_op_f, I_op, APInt(width, 0), false);
-    created.insert(*SIG_op_f);
   }
 }
 
@@ -813,11 +814,17 @@ void ABCD::createConstraintSigInst(Instruction *I_op, BasicBlock *BB_succ_t,
 /// PN_op2 -> PN_op1 with value. In case any of them is NULL, replace
 /// with the respective V_op#, if V_op# is a ConstantInt.
 void ABCD::createConstraintSigSig(PHINode *SIG_op1, PHINode *SIG_op2,
+                                  ConstantInt *V_op1, ConstantInt *V_op2,
                                   APInt value) {
   if (SIG_op1 && SIG_op2) {
-    APInt MinusOne = APInt::getAllOnesValue(value.getBitWidth());
     inequality_graph.addEdge(SIG_op2, SIG_op1, value, true);
-    inequality_graph.addEdge(SIG_op1, SIG_op2, value * MinusOne, false);
+    inequality_graph.addEdge(SIG_op1, SIG_op2, -value, false);
+  } else if (SIG_op1 && V_op2) {
+    inequality_graph.addEdge(V_op2, SIG_op1, value, true);
+    inequality_graph.addEdge(SIG_op1, V_op2, -value, false);
+  } else if (SIG_op2 && V_op1) {
+    inequality_graph.addEdge(SIG_op2, V_op1, value, true);
+    inequality_graph.addEdge(V_op1, SIG_op2, -value, false);
   }
 }
 
@@ -848,7 +855,7 @@ PHINode *ABCD::findSigma(BasicBlock *BB, Instruction *I) {
 /// This implementation works on any kind of inequality branch.
 bool ABCD::demandProve(Value *a, Value *b, int c, bool upper_bound) {
   int32_t width = cast<IntegerType>(a->getType())->getBitWidth();
-  Bound *bound = new Bound(APInt(width, c), upper_bound);
+  Bound bound(APInt(width, c), upper_bound);
 
   mem_result.clear();
   active.clear();
@@ -858,7 +865,7 @@ bool ABCD::demandProve(Value *a, Value *b, int c, bool upper_bound) {
 }
 
 /// Prove that distance between b and a is <= bound
-ABCD::ProveResult ABCD::prove(Value *a, Value *b, Bound *bound,
+ABCD::ProveResult ABCD::prove(Value *a, Value *b, const Bound &bound,
                               unsigned level) {
   // if (C[b-a<=e] == True for some e <= bound
   // Same or stronger difference was already proven
@@ -876,22 +883,22 @@ ABCD::ProveResult ABCD::prove(Value *a, Value *b, Bound *bound,
     return Reduced;
 
   // traversal reached the source vertex
-  if (a == b && Bound::geq(bound, APInt(bound->getBitWidth(), 0, true)))
+  if (a == b && Bound::geq(bound, APInt(bound.getBitWidth(), 0, true)))
     return True;
 
   // if b has no predecessor then fail
-  if (!inequality_graph.hasEdge(b, bound->isUpperBound()))
+  if (!inequality_graph.hasEdge(b, bound.isUpperBound()))
     return False;
 
   // a cycle was encountered
   if (active.count(b)) {
-    if (Bound::leq(active.lookup(b), bound))
+    if (Bound::leq(*active.lookup(b), bound))
       return Reduced; // a "harmless" cycle
 
     return False; // an amplifying cycle
   }
 
-  active[b] = bound;
+  active[b] = &bound;
   PHINode *PN = dyn_cast<PHINode>(b);
 
   // Test if a Value is a Phi. If it is a PHINode with more than 1 incoming
@@ -908,23 +915,23 @@ ABCD::ProveResult ABCD::prove(Value *a, Value *b, Bound *bound,
 }
 
 /// Updates the distance value for a and b
-void ABCD::updateMemDistance(Value *a, Value *b, Bound *bound, unsigned level,
-                             meet_function meet) {
+void ABCD::updateMemDistance(Value *a, Value *b, const Bound &bound,
+                             unsigned level, meet_function meet) {
   ABCD::ProveResult res = (meet == max) ? False : True;
 
-  SmallPtrSet<Edge *, 16> Edges = inequality_graph.getEdges(b);
-  SmallPtrSet<Edge *, 16>::iterator begin = Edges.begin(), end = Edges.end();
+  SmallVector<Edge, 16> Edges = inequality_graph.getEdges(b);
+  SmallVector<Edge, 16>::iterator begin = Edges.begin(), end = Edges.end();
 
   for (; begin != end ; ++begin) {
     if (((res >= Reduced) && (meet == max)) ||
        ((res == False) && (meet == min))) {
-        break;
+      break;
     }
-    Edge *in = *begin;
-    if (in->isUpperBound() == bound->isUpperBound()) {
-      Value *succ = in->getVertex();
-      res = meet(res, prove(a, succ, new Bound(bound, in->getValue()),
-                 level+1));
+    const Edge &in = *begin;
+    if (in.isUpperBound() == bound.isUpperBound()) {
+      Value *succ = in.getVertex();
+      res = meet(res, prove(a, succ, Bound(bound, in.getValue()),
+                            level+1));
     }
   }
 
@@ -932,53 +939,53 @@ void ABCD::updateMemDistance(Value *a, Value *b, Bound *bound, unsigned level,
 }
 
 /// Return the stored result for this bound
-ABCD::ProveResult ABCD::MemoizedResultChart::getResult(const Bound *bound)const{
-  if (max_false && Bound::leq(bound, max_false))
+ABCD::ProveResult ABCD::MemoizedResultChart::getResult(const Bound &bound)const{
+  if (max_false && Bound::leq(bound, *max_false))
     return False;
-  if (min_true && Bound::leq(min_true, bound))
+  if (min_true && Bound::leq(*min_true, bound))
     return True;
-  if (min_reduced && Bound::leq(min_reduced, bound))
+  if (min_reduced && Bound::leq(*min_reduced, bound))
     return Reduced;
   return False;
 }
 
 /// Stores a false found
-void ABCD::MemoizedResultChart::addFalse(Bound *bound) {
-  if (!max_false || Bound::leq(max_false, bound))
-    max_false = bound;
-
-  if (Bound::eq(max_false, min_reduced))
-    min_reduced = Bound::createIncrement(min_reduced);
-  if (Bound::eq(max_false, min_true))
-    min_true = Bound::createIncrement(min_true);
-  if (Bound::eq(min_reduced, min_true))
-    min_reduced = NULL;
+void ABCD::MemoizedResultChart::addFalse(const Bound &bound) {
+  if (!max_false || Bound::leq(*max_false, bound))
+    max_false.reset(new Bound(bound));
+
+  if (Bound::eq(max_false.get(), min_reduced.get()))
+    min_reduced.reset(new Bound(Bound::createIncrement(*min_reduced)));
+  if (Bound::eq(max_false.get(), min_true.get()))
+    min_true.reset(new Bound(Bound::createIncrement(*min_true)));
+  if (Bound::eq(min_reduced.get(), min_true.get()))
+    min_reduced.reset();
   clearRedundantReduced();
 }
 
 /// Stores a true found
-void ABCD::MemoizedResultChart::addTrue(Bound *bound) {
-  if (!min_true || Bound::leq(bound, min_true))
-    min_true = bound;
-
-  if (Bound::eq(min_true, min_reduced))
-    min_reduced = Bound::createDecrement(min_reduced);
-  if (Bound::eq(min_true, max_false))
-    max_false = Bound::createDecrement(max_false);
-  if (Bound::eq(max_false, min_reduced))
-    min_reduced = NULL;
+void ABCD::MemoizedResultChart::addTrue(const Bound &bound) {
+  if (!min_true || Bound::leq(bound, *min_true))
+    min_true.reset(new Bound(bound));
+
+  if (Bound::eq(min_true.get(), min_reduced.get()))
+    min_reduced.reset(new Bound(Bound::createDecrement(*min_reduced)));
+  if (Bound::eq(min_true.get(), max_false.get()))
+    max_false.reset(new Bound(Bound::createDecrement(*max_false)));
+  if (Bound::eq(max_false.get(), min_reduced.get()))
+    min_reduced.reset();
   clearRedundantReduced();
 }
 
 /// Stores a Reduced found
-void ABCD::MemoizedResultChart::addReduced(Bound *bound) {
-  if (!min_reduced || Bound::leq(bound, min_reduced))
-    min_reduced = bound;
-
-  if (Bound::eq(min_reduced, min_true))
-    min_true = Bound::createIncrement(min_true);
-  if (Bound::eq(min_reduced, max_false))
-    max_false = Bound::createDecrement(max_false);
+void ABCD::MemoizedResultChart::addReduced(const Bound &bound) {
+  if (!min_reduced || Bound::leq(bound, *min_reduced))
+    min_reduced.reset(new Bound(bound));
+
+  if (Bound::eq(min_reduced.get(), min_true.get()))
+    min_true.reset(new Bound(Bound::createIncrement(*min_true)));
+  if (Bound::eq(min_reduced.get(), max_false.get()))
+    max_false.reset(new Bound(Bound::createDecrement(*max_false)));
 }
 
 /// Clears redundant reduced
@@ -986,14 +993,14 @@ void ABCD::MemoizedResultChart::addReduced(Bound *bound) {
 /// is unnecessary and then removed. It also works for min_reduced
 /// begin smaller than max_false.
 void ABCD::MemoizedResultChart::clearRedundantReduced() {
-  if (min_true && min_reduced && Bound::lt(min_true, min_reduced))
-    min_reduced = NULL;
-  if (max_false && min_reduced && Bound::lt(min_reduced, max_false))
-    min_reduced = NULL;
+  if (min_true && min_reduced && Bound::lt(*min_true, *min_reduced))
+    min_reduced.reset();
+  if (max_false && min_reduced && Bound::lt(*min_reduced, *max_false))
+    min_reduced.reset();
 }
 
 /// Stores the bound found
-void ABCD::MemoizedResult::updateBound(Value *b, Bound *bound,
+void ABCD::MemoizedResult::updateBound(Value *b, const Bound &bound,
                                        const ProveResult res) {
   if (res == False) {
     map[b].addFalse(bound);
@@ -1006,24 +1013,22 @@ void ABCD::MemoizedResult::updateBound(Value *b, Bound *bound,
 
 /// Adds an edge from V_from to V_to with weight value
 void ABCD::InequalityGraph::addEdge(Value *V_to, Value *V_from,
-                              APInt value, bool upper) {
+                                    APInt value, bool upper) {
   assert(V_from->getType() == V_to->getType());
   assert(cast<IntegerType>(V_from->getType())->getBitWidth() ==
          value.getBitWidth());
 
-  DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator from;
-  from = addNode(V_from);
-  from->second.insert(new Edge(V_to, value, upper));
+  graph[V_from].push_back(Edge(V_to, value, upper));
 }
 
 /// Test if there is any edge from V in the upper direction
 bool ABCD::InequalityGraph::hasEdge(Value *V, bool upper) const {
-  SmallPtrSet<Edge *, 16> it = graph.lookup(V);
+  SmallVector<Edge, 16> it = graph.lookup(V);
 
-  SmallPtrSet<Edge *, 16>::iterator begin = it.begin();
-  SmallPtrSet<Edge *, 16>::iterator end = it.end();
+  SmallVector<Edge, 16>::iterator begin = it.begin();
+  SmallVector<Edge, 16>::iterator end = it.end();
   for (; begin != end; ++begin) {
-    if ((*begin)->isUpperBound() == upper) {
+    if (begin->isUpperBound() == upper) {
       return true;
     }
   }
@@ -1040,18 +1045,18 @@ void ABCD::InequalityGraph::printHeader(raw_ostream &OS, Function &F) const {
 
 /// Prints the body of the dot file
 void ABCD::InequalityGraph::printBody(raw_ostream &OS) const {
-  DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator begin =
+  DenseMap<Value *, SmallVector<Edge, 16> >::const_iterator begin =
       graph.begin(), end = graph.end();
 
   for (; begin != end ; ++begin) {
-    SmallPtrSet<Edge *, 16>::iterator begin_par =
+    SmallVector<Edge, 16>::const_iterator begin_par =
         begin->second.begin(), end_par = begin->second.end();
     Value *source = begin->first;
 
     printVertex(OS, source);
 
     for (; begin_par != end_par ; ++begin_par) {
-      Edge *edge = *begin_par;
+      const Edge &edge = *begin_par;
       printEdge(OS, source, edge);
     }
   }
@@ -1070,10 +1075,10 @@ void ABCD::InequalityGraph::printVertex(raw_ostream &OS, Value *source) const {
 
 /// Prints the edge to the dot file
 void ABCD::InequalityGraph::printEdge(raw_ostream &OS, Value *source,
-                                      Edge *edge) const {
-  Value *dest = edge->getVertex();
-  APInt value = edge->getValue();
-  bool upper = edge->isUpperBound();
+                                      const Edge &edge) const {
+  Value *dest = edge.getVertex();
+  APInt value = edge.getValue();
+  bool upper = edge.isUpperBound();
 
   OS << "\"";
   printName(OS, source);
@@ -1093,9 +1098,9 @@ void ABCD::InequalityGraph::printEdge(raw_ostream &OS, Value *source,
 
 void ABCD::InequalityGraph::printName(raw_ostream &OS, Value *info) const {
   if (ConstantInt *CI = dyn_cast<ConstantInt>(info)) {
-    OS << *CI->getValue().getRawData();
+    OS << *CI;
   } else {
-    if (info->getName() == "") {
+    if (!info->hasName()) {
       info->setName("V");
     }
     OS << info->getNameStr();