New predicate simplifier!

Please do not enable, there is still some known miscompile problem.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@33066 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 1155 insertions, 974 deletions

diff --git a/lib/Transforms/Scalar/PredicateSimplifier.cpp b/lib/Transforms/Scalar/PredicateSimplifier.cpp
index 6578bccff1..16cc20c06a 100644
--- a/lib/Transforms/Scalar/PredicateSimplifier.cpp
+++ b/lib/Transforms/Scalar/PredicateSimplifier.cpp
@@ -41,11 +41,11 @@
 //   %a < %b < %c < %d
 //
 // with four nodes representing the properties. The InequalityGraph provides
-// queries (such as "isEqual") and mutators (such as "addEqual"). To implement
-// "isLess(%a, %c)", we start with getNode(%c) and walk downwards until
-// we reach %a or the leaf node. Note that the graph is directed and acyclic,
-// but may contain joins, meaning that this walk is not a linear time
-// algorithm.
+// querying with "isRelatedBy" and mutators "addEquality" and "addInequality".
+// To find a relationship, we start with one of the nodes any binary search
+// through its list to find where the relationships with the second node start.
+// Then we iterate through those to find the first relationship that dominates
+// our context node.
 //
 // To create these properties, we wait until a branch or switch instruction
 // implies that a particular value is true (or false). The VRPSolver is
@@ -74,13 +74,13 @@
 #include "llvm/DerivedTypes.h"
 #include "llvm/Instructions.h"
 #include "llvm/Pass.h"
+#include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Analysis/ET-Forest.h"
-#include "llvm/Assembly/Writer.h"
 #include "llvm/Support/CFG.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
@@ -89,14 +89,82 @@
 #include <algorithm>
 #include <deque>
 #include <sstream>
-#include <map>
 using namespace llvm;
 
 STATISTIC(NumVarsReplaced, "Number of argument substitutions");
 STATISTIC(NumInstruction , "Number of instructions removed");
 STATISTIC(NumSimple      , "Number of simple replacements");
+STATISTIC(NumBlocks      , "Number of blocks marked unreachable");
 
 namespace {
+  // SLT SGT ULT UGT EQ
+  //   0   1   0   1  0 -- GT                  10
+  //   0   1   0   1  1 -- GE                  11
+  //   0   1   1   0  0 -- SGTULT              12
+  //   0   1   1   0  1 -- SGEULE              13
+  //   0   1   1   1  0 -- SGTUNE              14
+  //   0   1   1   1  1 -- SGEUANY             15
+  //   1   0   0   1  0 -- SLTUGT              18
+  //   1   0   0   1  1 -- SLEUGE              19
+  //   1   0   1   0  0 -- LT                  20
+  //   1   0   1   0  1 -- LE                  21
+  //   1   0   1   1  0 -- SLTUNE              22
+  //   1   0   1   1  1 -- SLEUANY             23
+  //   1   1   0   1  0 -- SNEUGT              26
+  //   1   1   0   1  1 -- SANYUGE             27
+  //   1   1   1   0  0 -- SNEULT              28
+  //   1   1   1   0  1 -- SANYULE             29
+  //   1   1   1   1  0 -- NE                  30
+  enum LatticeBits {
+    EQ_BIT = 1, UGT_BIT = 2, ULT_BIT = 4, SGT_BIT = 8, SLT_BIT = 16
+  };
+  enum LatticeVal {
+    GT = SGT_BIT | UGT_BIT,
+    GE = GT | EQ_BIT,
+    LT = SLT_BIT | ULT_BIT,
+    LE = LT | EQ_BIT,
+    NE = SLT_BIT | SGT_BIT | ULT_BIT | UGT_BIT,
+    SGTULT = SGT_BIT | ULT_BIT,
+    SGEULE = SGTULT | EQ_BIT,
+    SLTUGT = SLT_BIT | UGT_BIT,
+    SLEUGE = SLTUGT | EQ_BIT,
+    SNEULT = SLT_BIT | SGT_BIT | ULT_BIT,
+    SNEUGT = SLT_BIT | SGT_BIT | UGT_BIT,
+    SLTUNE = SLT_BIT | ULT_BIT | UGT_BIT,
+    SGTUNE = SGT_BIT | ULT_BIT | UGT_BIT,
+    SLEUANY = SLT_BIT | ULT_BIT | UGT_BIT | EQ_BIT,
+    SGEUANY = SGT_BIT | ULT_BIT | UGT_BIT | EQ_BIT,
+    SANYULE = SLT_BIT | SGT_BIT | ULT_BIT | EQ_BIT,
+    SANYUGE = SLT_BIT | SGT_BIT | UGT_BIT | EQ_BIT
+  };
+
+  static bool validPredicate(LatticeVal LV) {
+    switch (LV) {
+    case GT: case GE: case LT: case LE: case NE:
+    case SGTULT: case SGTUNE: case SGEULE:
+    case SLTUGT: case SLTUNE: case SLEUGE:
+    case SNEULT: case SNEUGT:
+    case SLEUANY: case SGEUANY: case SANYULE: case SANYUGE:
+      return true;
+    default:
+      return false;
+    }
+  }
+
+  /// reversePredicate - reverse the direction of the inequality
+  static LatticeVal reversePredicate(LatticeVal LV) {
+    unsigned reverse = LV ^ (SLT_BIT|SGT_BIT|ULT_BIT|UGT_BIT); //preserve EQ_BIT
+    if ((reverse & (SLT_BIT|SGT_BIT)) == 0)
+      reverse |= (SLT_BIT|SGT_BIT);
+
+    if ((reverse & (ULT_BIT|UGT_BIT)) == 0)
+      reverse |= (ULT_BIT|UGT_BIT);
+
+    LatticeVal Rev = static_cast<LatticeVal>(reverse);
+    assert(validPredicate(Rev) && "Failed reversing predicate.");
+    return Rev;
+  }
+
   /// The InequalityGraph stores the relationships between values.
   /// Each Value in the graph is assigned to a Node. Nodes are pointer
   /// comparable for equality. The caller is expected to maintain the logical
@@ -105,38 +173,51 @@ namespace {
   /// The InequalityGraph class may invalidate Node*s after any mutator call.
   /// @brief The InequalityGraph stores the relationships between values.
   class VISIBILITY_HIDDEN InequalityGraph {
+    ETNode *TreeRoot;
+
+    InequalityGraph();                  // DO NOT IMPLEMENT
+    InequalityGraph(InequalityGraph &); // DO NOT IMPLEMENT
   public:
+    explicit InequalityGraph(ETNode *TreeRoot) : TreeRoot(TreeRoot) {}
+
     class Node;
 
-    // LT GT EQ
-    //  0  0  0 -- invalid (false)
-    //  0  0  1 -- invalid (EQ)
-    //  0  1  0 -- GT
-    //  0  1  1 -- GE
-    //  1  0  0 -- LT
-    //  1  0  1 -- LE
-    //  1  1  0 -- NE
-    //  1  1  1 -- invalid (true)
-    enum LatticeBits {
-      EQ_BIT = 1, GT_BIT = 2, LT_BIT = 4
-    };
-    enum LatticeVal {
-      GT = GT_BIT, GE = GT_BIT | EQ_BIT,
-      LT = LT_BIT, LE = LT_BIT | EQ_BIT,
-      NE = GT_BIT | LT_BIT
+    /// This is a StrictWeakOrdering predicate that sorts ETNodes by how many
+    /// children they have. With this, you can iterate through a list sorted by
+    /// this operation and the first matching entry is the most specific match
+    /// for your basic block. The order provided is total; ETNodes with the
+    /// same number of children are sorted by pointer address.
+    struct VISIBILITY_HIDDEN OrderByDominance {
+      bool operator()(const ETNode *LHS, const ETNode *RHS) const {
+        unsigned LHS_spread = LHS->getDFSNumOut() - LHS->getDFSNumIn();
+        unsigned RHS_spread = RHS->getDFSNumOut() - RHS->getDFSNumIn();
+        if (LHS_spread != RHS_spread) return LHS_spread < RHS_spread;
+        else return LHS < RHS;
+      }
     };
 
-    static bool validPredicate(LatticeVal LV) {
-      return LV > 1 && LV < 7;
-    }
+    /// An Edge is contained inside a Node making one end of the edge implicit
+    /// and contains a pointer to the other end. The edge contains a lattice
+    /// value specifying the relationship between the two nodes. Further, there
+    /// is an ETNode specifying which subtree of the dominator the edge applies.
+    class VISIBILITY_HIDDEN Edge {
+    public:
+      Edge(unsigned T, LatticeVal V, ETNode *ST)
+        : To(T), LV(V), Subtree(ST) {}
 
-  private:
-    typedef std::map<Value *, Node *> NodeMapType;
-    NodeMapType Nodes;
+      unsigned To;
+      LatticeVal LV;
+      ETNode *Subtree;
 
-    const InequalityGraph *ConcreteIG;
+      bool operator<(const Edge &edge) const {
+        if (To != edge.To) return To < edge.To;
+        else return OrderByDominance()(Subtree, edge.Subtree);
+      }
+      bool operator<(unsigned to) const {
+        return To < to;
+      }
+    };
 
-  public:
     /// A single node in the InequalityGraph. This stores the canonical Value
     /// for the node, as well as the relationships with the neighbours.
     ///
@@ -148,367 +229,488 @@ namespace {
     class VISIBILITY_HIDDEN Node {
       friend class InequalityGraph;
 
+      typedef SmallVector<Edge, 4> RelationsType;
+      RelationsType Relations;
+
       Value *Canonical;
 
-      typedef SmallVector<std::pair<Node *, LatticeVal>, 4> RelationsType;
-      RelationsType Relations;
+      // TODO: can this idea improve performance?
+      //friend class std::vector<Node>;
+      //Node(Node &N) { RelationsType.swap(N.RelationsType); }
+
     public:
       typedef RelationsType::iterator       iterator;
       typedef RelationsType::const_iterator const_iterator;
 
+      Node(Value *V) : Canonical(V) {}
+
     private:
+#ifndef NDEBUG
+    public:
+      virtual void dump() const {
+        dump(*cerr.stream());
+      }
+    private:
+      void dump(std::ostream &os) const  {
+        os << *getValue() << ":\n";
+        for (Node::const_iterator NI = begin(), NE = end(); NI != NE; ++NI) {
+          static const std::string names[32] =
+            { "000000", "000001", "000002", "000003", "000004", "000005",
+              "000006", "000007", "000008", "000009", "     >", "    >=",
+              "  s>u<", "s>=u<=", "    s>", "   s>=", "000016", "000017",
+              "  s<u>", "s<=u>=", "     <", "    <=", "    s<", "   s<=",
+              "000024", "000025", "    u>", "   u>=", "    u<", "   u<=",
+              "    !=", "000031" };
+          os << "  " << names[NI->LV] << " " << NI->To
+             << "(" << NI->Subtree << ")\n";
+        }
+      }
+#endif
+
+    public:
+      iterator begin()             { return Relations.begin(); }
+      iterator end()               { return Relations.end();   }
+      const_iterator begin() const { return Relations.begin(); }
+      const_iterator end()   const { return Relations.end();   }
+
+      iterator find(unsigned n, ETNode *Subtree) {
+        iterator E = end();
+        for (iterator I = std::lower_bound(begin(), E, n);
+             I != E && I->To == n; ++I) {
+          if (Subtree->DominatedBy(I->Subtree))
+            return I;
+        }
+        return E;
+      }
+
+      const_iterator find(unsigned n, ETNode *Subtree) const {
+        const_iterator E = end();
+        for (const_iterator I = std::lower_bound(begin(), E, n);
+             I != E && I->To == n; ++I) {
+          if (Subtree->DominatedBy(I->Subtree))
+            return I;
+        }
+        return E;
+      }
+
+      Value *getValue() const
+      {
+        return Canonical;
+      }
+
       /// Updates the lattice value for a given node. Create a new entry if
       /// one doesn't exist, otherwise it merges the values. The new lattice
       /// value must not be inconsistent with any previously existing value.
-      void update(Node *N, LatticeVal R) {
-        iterator I = find(N);
+      void update(unsigned n, LatticeVal R, ETNode *Subtree) {
+        assert(validPredicate(R) && "Invalid predicate.");
+        iterator I = find(n, Subtree);
         if (I == end()) {
-          Relations.push_back(std::make_pair(N, R));
+          Edge edge(n, R, Subtree);
+          iterator Insert = std::lower_bound(begin(), end(), edge);
+          Relations.insert(Insert, edge);
         } else {
-          I->second = static_cast<LatticeVal>(I->second & R);
-          assert(validPredicate(I->second) &&
-                 "Invalid union of lattice values.");
+          LatticeVal LV = static_cast<LatticeVal>(I->LV & R);
+          assert(validPredicate(LV) && "Invalid union of lattice values.");
+          if (LV != I->LV) {
+            if (Subtree == I->Subtree)
+              I->LV = LV;
+            else {
+              assert(Subtree->DominatedBy(I->Subtree) &&
+                     "Find returned subtree that doesn't apply.");
+
+              Edge edge(n, R, Subtree);
+              iterator Insert = std::lower_bound(begin(), end(), edge);
+              Relations.insert(Insert, edge);
+            }
+          }
         }
       }
+    };
 
-      void assign(Node *N, LatticeVal R) {
-        iterator I = find(N);
-        if (I != end()) I->second = R;
+  private:
+    struct VISIBILITY_HIDDEN NodeMapEdge {
+      Value *V;
+      unsigned index;
+      ETNode *Subtree;
 
-        Relations.push_back(std::make_pair(N, R));
-      }
+      NodeMapEdge(Value *V, unsigned index, ETNode *Subtree)
+        : V(V), index(index), Subtree(Subtree) {}
 
-    public:
-      iterator begin()       { return Relations.begin(); }
-      iterator end()         { return Relations.end();   }
-      iterator find(Node *N) {
-        iterator I = begin();
-        for (iterator E = end(); I != E; ++I)
-          if (I->first == N) break;
-        return I;
+      bool operator==(const NodeMapEdge &RHS) const {
+        return V == RHS.V &&
+               Subtree == RHS.Subtree;
       }
 
-      const_iterator begin()       const { return Relations.begin(); }
-      const_iterator end()         const { return Relations.end();   }
-      const_iterator find(Node *N) const {
-        const_iterator I = begin();
-        for (const_iterator E = end(); I != E; ++I)
-          if (I->first == N) break;
-        return I;
+      bool operator<(const NodeMapEdge &RHS) const {
+        if (V != RHS.V) return V < RHS.V;
+        return OrderByDominance()(Subtree, RHS.Subtree);
       }
 
-      unsigned findIndex(Node *N) {
-        unsigned i = 0;
-        iterator I = begin();
-        for (iterator E = end(); I != E; ++I, ++i)
-          if (I->first == N) return i;
-        return (unsigned)-1;
+      bool operator<(Value *RHS) const {
+        return V < RHS;
       }
-
-      void erase(iterator i) { Relations.erase(i); }
-
-      Value *getValue() const { return Canonical; }
-      void setValue(Value *V) { Canonical = V; }
-
-      void addNotEqual(Node *N)     { update(N, NE); }
-      void addLess(Node *N)         { update(N, LT); }
-      void addLessEqual(Node *N)    { update(N, LE); }
-      void addGreater(Node *N)      { update(N, GT); }
-      void addGreaterEqual(Node *N) { update(N, GE); }
     };
 
-    InequalityGraph() : ConcreteIG(NULL) {}
-
-    InequalityGraph(const InequalityGraph &_IG) {
-#if 0 // disable COW
-      if (_IG.ConcreteIG) ConcreteIG = _IG.ConcreteIG;
-      else ConcreteIG = &_IG;
-#else
-      ConcreteIG = &_IG;
-      materialize();
-#endif
+    typedef std::vector<NodeMapEdge> NodeMapType;
+    NodeMapType NodeMap;
+
+    std::vector<Node> Nodes;
+
+    std::vector<std::pair<ConstantIntegral *, unsigned> > Constants;
+    void initializeConstant(Constant *C, unsigned index) {
+      ConstantIntegral *CI = dyn_cast<ConstantIntegral>(C);
+      if (!CI) return;
+
+      // XXX: instead of O(n) calls to addInequality, just find the 2, 3 or 4
+      // nodes that are nearest less than or greater than (signed or unsigned).
+      for (std::vector<std::pair<ConstantIntegral *, unsigned> >::iterator
+           I = Constants.begin(), E = Constants.end(); I != E; ++I) {
+        ConstantIntegral *Other = I->first;
+        if (CI->getType() == Other->getType()) {
+          unsigned lv = 0;
+
+          if (CI->getZExtValue() < Other->getZExtValue())
+            lv |= ULT_BIT;
+          else
+            lv |= UGT_BIT;
+
+          if (CI->getSExtValue() < Other->getSExtValue())
+            lv |= SLT_BIT;
+          else
+            lv |= SGT_BIT;
+
+          LatticeVal LV = static_cast<LatticeVal>(lv);
+          assert(validPredicate(LV) && "Not a valid predicate.");
+          if (!isRelatedBy(index, I->second, TreeRoot, LV))
+            addInequality(index, I->second, TreeRoot, LV);
+        }
+      }
+      Constants.push_back(std::make_pair(CI, index));
     }
 
-    ~InequalityGraph();
-
-  private:
-    void materialize();
-
   public:
-    /// If the Value is in the graph, return the canonical form. Otherwise,
-    /// return the original Value.
-    Value *canonicalize(Value *V) const {  
-      if (const Node *N = getNode(V))
-        return N->getValue();
-      else 
-        return V;
+    /// node - returns the node object at a given index retrieved from getNode.
+    /// Index zero is reserved and may not be passed in here. The pointer
+    /// returned is valid until the next call to newNode or getOrInsertNode.
+    Node *node(unsigned index) {
+      assert(index != 0 && "Zero index is reserved for not found.");
+      assert(index <= Nodes.size() && "Index out of range.");
+      return &Nodes[index-1];
     }
 
-    /// Returns the node currently representing Value V, or null if no such
+    /// Returns the node currently representing Value V, or zero if no such
     /// node exists.
-    Node *getNode(Value *V) {
-      materialize();
-
-      NodeMapType::const_iterator I = Nodes.find(V);
-      return (I != Nodes.end()) ? I->second : 0;
-    }
-
-    const Node *getNode(Value *V) const {
-      if (ConcreteIG) return ConcreteIG->getNode(V);
-
-      NodeMapType::const_iterator I = Nodes.find(V);
-      return (I != Nodes.end()) ? I->second : 0;
+    unsigned getNode(Value *V, ETNode *Subtree) {
+      NodeMapType::iterator E = NodeMap.end();
+      NodeMapEdge Edge(V, 0, Subtree);
+      NodeMapType::iterator I = std::lower_bound(NodeMap.begin(), E, Edge);
+      while (I != E && I->V == V) {
+        if (Subtree->DominatedBy(I->Subtree))
+          return I->index;
+        ++I;
+      }
+      return 0;
     }
 
-    Node *getOrInsertNode(Value *V) {
-      if (Node *N = getNode(V))
-        return N;
+    /// getOrInsertNode - always returns a valid node index, creating a node
+    /// to match the Value if needed.
+    unsigned getOrInsertNode(Value *V, ETNode *Subtree) {
+      if (unsigned n = getNode(V, Subtree))
+        return n;
       else
         return newNode(V);
     }
 
-    Node *newNode(Value *V) {
-      //DOUT << "new node: " << *V << "\n";
-      materialize();
-      Node *&N = Nodes[V];
-      assert(N == 0 && "Node already exists for value.");
-      N = new Node();
-      N->setValue(V);
-      return N;
-    }
+    /// newNode - creates a new node for a given Value and returns the index.
+    unsigned newNode(Value *V) {
+      Nodes.push_back(Node(V));
 
-    /// Returns true iff the nodes are provably inequal.
-    bool isNotEqual(const Node *N1, const Node *N2) const {
-      if (N1 == N2) return false;
-      for (Node::const_iterator I = N1->begin(), E = N1->end(); I != E; ++I) {
-        if (I->first == N2)
-          return (I->second & EQ_BIT) == 0;
-      }
-      return isLess(N1, N2) || isGreater(N1, N2);
-    }
+      NodeMapEdge MapEntry = NodeMapEdge(V, Nodes.size(), TreeRoot);
+      assert(!std::binary_search(NodeMap.begin(), NodeMap.end(), MapEntry) &&
+             "Attempt to create a duplicate Node.");
+      NodeMap.insert(std::lower_bound(NodeMap.begin(), NodeMap.end(),
+                                      MapEntry), MapEntry);
 
-    /// Returns true iff N1 is provably less than N2.
-    bool isLess(const Node *N1, const Node *N2) const {
-      if (N1 == N2) return false;
-      for (Node::const_iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
-        if (I->first == N1)
-          return I->second == LT;
-      }
-      for (Node::const_iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
-        if ((I->second & (LT_BIT | GT_BIT)) == LT_BIT)
-          if (isLess(N1, I->first)) return true;
-      }
-      return false;
-    }
+#if 1
+      // This is the missing piece to turn on VRP.
+      if (Constant *C = dyn_cast<Constant>(V))
+        initializeConstant(C, MapEntry.index);
+#endif
 
-    /// Returns true iff N1 is provably less than or equal to N2.
-    bool isLessEqual(const Node *N1, const Node *N2) const {
-      if (N1 == N2) return true;
-      for (Node::const_iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
-        if (I->first == N1)
-          return (I->second & (LT_BIT | GT_BIT)) == LT_BIT;
-      }
-      for (Node::const_iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
-        if ((I->second & (LT_BIT | GT_BIT)) == LT_BIT)
-          if (isLessEqual(N1, I->first)) return true;
-      }
-      return false;
+      return MapEntry.index;
     }
 
-    /// Returns true iff N1 is provably greater than N2.
-    bool isGreater(const Node *N1, const Node *N2) const {
-      return isLess(N2, N1);
+    /// If the Value is in the graph, return the canonical form. Otherwise,
+    /// return the original Value.
+    Value *canonicalize(Value *V, ETNode *Subtree) {
+      if (isa<Constant>(V)) return V;
+
+      if (unsigned n = getNode(V, Subtree))
+        return node(n)->getValue();
+      else 
+        return V;
     }
 
-    /// Returns true iff N1 is provably greater than or equal to N2.
-    bool isGreaterEqual(const Node *N1, const Node *N2) const {
-      return isLessEqual(N2, N1);
+    /// isRelatedBy - true iff n1 op n2
+    bool isRelatedBy(unsigned n1, unsigned n2, ETNode *Subtree, LatticeVal LV) {
+      if (n1 == n2) return LV & EQ_BIT;
+
+      Node *N1 = node(n1);
+      Node::iterator I = N1->find(n2, Subtree), E = N1->end();
+      if (I != E) return (I->LV & LV) == I->LV;
+
+      return false;
     }
 
     // The add* methods assume that your input is logically valid and may 
     // assertion-fail or infinitely loop if you attempt a contradiction.
 
-    void addEqual(Node *N, Value *V) {
-      materialize();
-      Nodes[V] = N;
-    }
+    void addEquality(unsigned n, Value *V, ETNode *Subtree) {
+      assert(canonicalize(node(n)->getValue(), Subtree) == node(n)->getValue()
+             && "Node's 'canonical' choice isn't best within this subtree.");
 
-    void addNotEqual(Node *N1, Node *N2) {
-      assert(N1 != N2 && "A node can't be inequal to itself.");
-      materialize();
-      N1->addNotEqual(N2);
-      N2->addNotEqual(N1);
-    }
+      // Suppose that we are given "%x -> node #1 (%y)". The problem is that
+      // we may already have "%z -> node #2 (%x)" somewhere above us in the
+      // graph. We need to find those edges and add "%z -> node #1 (%y)"
+      // to keep the lookups canonical.
 
-    /// N1 is less than N2.
-    void addLess(Node *N1, Node *N2) {
-      assert(N1 != N2 && !isLess(N2, N1) && "Attempt to create < cycle.");
-      materialize();
-      N2->addLess(N1);
-      N1->addGreater(N2);
-    }
+      std::vector<Value *> ToRepoint;
+      ToRepoint.push_back(V);
 
-    /// N1 is less than or equal to N2.
-    void addLessEqual(Node *N1, Node *N2) {
-      assert(N1 != N2 && "Nodes are equal. Use mergeNodes instead.");
-      assert(!isGreater(N1, N2) && "Impossible: Adding x <= y when x > y.");
-      materialize();
-      N2->addLessEqual(N1);
-      N1->addGreaterEqual(N2);
-    }
+      if (unsigned Conflict = getNode(V, Subtree)) {
+        // XXX: NodeMap.size() exceeds 68000 entries compiling kimwitu++!
+        // This adds 57 seconds to the otherwise 3 second build. Unacceptable.
+        //
+        // IDEA: could we iterate 1..Nodes.size() calling getNode? It's
+        // O(n log n) but kimwitu++ only has about 300 nodes.
+        for (NodeMapType::iterator I = NodeMap.begin(), E = NodeMap.end();
+             I != E; ++I) {
+          if (I->index == Conflict && Subtree->DominatedBy(I->Subtree))
+            ToRepoint.push_back(I->V);
+        }
+      }
+
+      for (std::vector<Value *>::iterator VI = ToRepoint.begin(),
+           VE = ToRepoint.end(); VI != VE; ++VI) {
+        Value *V = *VI;
+
+        // XXX: review this code. This may be doing too many insertions.
+        NodeMapEdge Edge(V, n, Subtree);
+        NodeMapType::iterator E = NodeMap.end();
+        NodeMapType::iterator I = std::lower_bound(NodeMap.begin(), E, Edge);
+        if (I == E || I->V != V || I->Subtree != Subtree) {
+          // New Value
+          NodeMap.insert(I, Edge);
+        } else if (I != E && I->V == V && I->Subtree == Subtree) {
+          // Update best choice
+          I->index = n;
+        }
 
-    /// Find the transitive closure starting at a node walking down the edges
-    /// of type Val. Type Inserter must be an inserter that accepts Node *.
-    template <typename Inserter>
-    void transitiveClosure(Node *N, LatticeVal Val, Inserter insert) {
-      for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I) {
-        if (I->second == Val) {
-          *insert = I->first;
-          transitiveClosure(I->first, Val, insert);
+#ifndef NDEBUG
+        Node *N = node(n);
+        if (isa<Constant>(V)) {
+          if (isa<Constant>(N->getValue())) {
+            assert(V == N->getValue() && "Constant equals different constant?");
+          }
         }
+#endif
       }
     }
 
-    /// Kills off all the nodes in Kill by replicating their properties into
-    /// node N. The elements of Kill must be unique. After merging, N's new
-    /// canonical value is NewCanonical. Type C must be a container of Node *.
-    template <typename C>
-    void mergeNodes(Node *N, C &Kill, Value *NewCanonical);
+    /// addInequality - Sets n1 op n2.
+    /// It is also an error to call this on an inequality that is already true.
+    void addInequality(unsigned n1, unsigned n2, ETNode *Subtree,
+                       LatticeVal LV1) {
+      assert(n1 != n2 && "A node can't be inequal to itself.");
+
+      if (LV1 != NE)
+        assert(!isRelatedBy(n1, n2, Subtree, reversePredicate(LV1)) &&
+               "Contradictory inequality.");
+
+      Node *N1 = node(n1);
+      Node *N2 = node(n2);
+
+      // Suppose we're adding %n1 < %n2. Find all the %a < %n1 and
+      // add %a < %n2 too. This keeps the graph fully connected.
+      if (LV1 != NE) {
+        // Someone with a head for this sort of logic, please review this.
+        // Given that %x SLTUGT %y and %a SLEUANY %x, what is the relationship
+        // between %a and %y? I believe the below code is correct, but I don't
+        // think it's the most efficient solution.
+
+        unsigned LV1_s = LV1 & (SLT_BIT|SGT_BIT);
+        unsigned LV1_u = LV1 & (ULT_BIT|UGT_BIT);
+        for (Node::iterator I = N1->begin(), E = N1->end(); I != E; ++I) {
+          if (I->LV != NE && I->To != n2) {
+            ETNode *Local_Subtree = NULL;
+            if (Subtree->DominatedBy(I->Subtree))
+              Local_Subtree = Subtree;
+            else if (I->Subtree->DominatedBy(Subtree))
+              Local_Subtree = I->Subtree;
+
+            if (Local_Subtree) {
+              unsigned new_relationship = 0;
+              LatticeVal ILV = reversePredicate(I->LV);
+              unsigned ILV_s = ILV & (SLT_BIT|SGT_BIT);
+              unsigned ILV_u = ILV & (ULT_BIT|UGT_BIT);
+
+              if (LV1_s != (SLT_BIT|SGT_BIT) && ILV_s == LV1_s)
+                new_relationship |= ILV_s;
+
+              if (LV1_u != (ULT_BIT|UGT_BIT) && ILV_u == LV1_u)
+                new_relationship |= ILV_u;
+
+              if (new_relationship) {
+                if ((new_relationship & (SLT_BIT|SGT_BIT)) == 0)
+                  new_relationship |= (SLT_BIT|SGT_BIT);
+                if ((new_relationship & (ULT_BIT|UGT_BIT)) == 0)
+                  new_relationship |= (ULT_BIT|UGT_BIT);
+                if ((LV1 & EQ_BIT) && (ILV & EQ_BIT))
+                  new_relationship |= EQ_BIT;
+
+                LatticeVal NewLV = static_cast<LatticeVal>(new_relationship);
+
+                node(I->To)->update(n2, NewLV, Local_Subtree);
+                N2->update(I->To, reversePredicate(NewLV), Local_Subtree);
+              }
+            }
+          }
+        }
+
+        for (Node::iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
+          if (I->LV != NE && I->To != n1) {
+            ETNode *Local_Subtree = NULL;
+            if (Subtree->DominatedBy(I->Subtree))
+              Local_Subtree = Subtree;
+            else if (I->Subtree->DominatedBy(Subtree))
+              Local_Subtree = I->Subtree;
+
+            if (Local_Subtree) {
+              unsigned new_relationship = 0;
+              unsigned ILV_s = I->LV & (SLT_BIT|SGT_BIT);
+              unsigned ILV_u = I->LV & (ULT_BIT|UGT_BIT);
+
+              if (LV1_s != (SLT_BIT|SGT_BIT) && ILV_s == LV1_s)
+                new_relationship |= ILV_s;
+
+              if (LV1_u != (ULT_BIT|UGT_BIT) && ILV_u == LV1_u)
+                new_relationship |= ILV_u;
+
+              if (new_relationship) {
+                if ((new_relationship & (SLT_BIT|SGT_BIT)) == 0)
+                  new_relationship |= (SLT_BIT|SGT_BIT);
+                if ((new_relationship & (ULT_BIT|UGT_BIT)) == 0)
+                  new_relationship |= (ULT_BIT|UGT_BIT);
+                if ((LV1 & EQ_BIT) && (I->LV & EQ_BIT))
+                  new_relationship |= EQ_BIT;
+
+                LatticeVal NewLV = static_cast<LatticeVal>(new_relationship);
+
+                N1->update(I->To, NewLV, Local_Subtree);
+                node(I->To)->update(n1, reversePredicate(NewLV), Local_Subtree);
+              }
+            }
+          }
+        }
+      }
+
+      N1->update(n2, LV1, Subtree);
+      N2->update(n1, reversePredicate(LV1), Subtree);
+    }
 
     /// Removes a Value from the graph, but does not delete any nodes. As this
     /// method does not delete Nodes, V may not be the canonical choice for
-    /// any node.
+    /// a node with any relationships. It is invalid to call newNode on a Value
+    /// that has been removed.
     void remove(Value *V) {
-      materialize();
-
-      for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E;) {
-        NodeMapType::iterator J = I++;
-        assert(J->second->getValue() != V && "Can't delete canonical choice.");
-        if (J->first == V) Nodes.erase(J);
+      for (unsigned i = 0; i < NodeMap.size();) {
+        NodeMapType::iterator I = NodeMap.begin()+i;
+        assert((node(I->index)->getValue() != V || node(I->index)->begin() ==
+                node(I->index)->end()) && "Tried to delete in-use node.");
+        if (I->V == V) {
+#ifndef NDEBUG
+          if (node(I->index)->getValue() == V)
+            node(I->index)->Canonical = NULL;
+#endif
+          NodeMap.erase(I);
+        } else ++i;
       }
     }
 
 #ifndef NDEBUG
-    void debug(std::ostream &os) const {
+    virtual void dump() {
+      dump(*cerr.stream());
+    }
+
+    void dump(std::ostream &os) {
     std::set<Node *> VisitedNodes;
-    for (NodeMapType::const_iterator I = Nodes.begin(), E = Nodes.end();
+    for (NodeMapType::const_iterator I = NodeMap.begin(), E = NodeMap.end();
          I != E; ++I) {
-      Node *N = I->second;
-      os << *I->first << " == " << *N->getValue() << "\n";
+      Node *N = node(I->index);
+      os << *I->V << " == " << I->index << "(" << I->Subtree << ")\n";
       if (VisitedNodes.insert(N).second) {
-        os << *N->getValue() << ":\n";
-        for (Node::const_iterator NI = N->begin(), NE = N->end();
-             NI != NE; ++NI) {
-          static const std::string names[8] =
-              { "00", "01", " <", "<=", " >", ">=", "!=", "07" };
-          os << "  " << names[NI->second] << " "
-             << *NI->first->getValue() << "\n";
-        }
+        os << I->index << ". ";
+        if (!N->getValue()) os << "(deleted node)\n";
+        else N->dump(os);
       }
     }
   }
 #endif
   };
 
-  InequalityGraph::~InequalityGraph() {
-    if (ConcreteIG) return;
-
-    std::vector<Node *> Remove;
-    for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end();
-         I != E; ++I) {
-      if (I->first == I->second->getValue())
-        Remove.push_back(I->second);
-    }
-    for (std::vector<Node *>::iterator I = Remove.begin(), E = Remove.end();
-         I != E; ++I) {
-      delete *I;
-    }
-  }
-
-  template <typename C>
-  void InequalityGraph::mergeNodes(Node *N, C &Kill, Value *NewCanonical) {
-    materialize();
-
-    // Merge the relationships from the members of Kill into N.
-    for (typename C::iterator KI = Kill.begin(), KE = Kill.end();
-         KI != KE; ++KI) {
-
-      for (Node::iterator I = (*KI)->begin(), E = (*KI)->end(); I != E; ++I) {
-        if (I->first == N) continue;
-
-        Node::iterator NI = N->find(I->first);
-        if (NI == N->end()) {
-          N->Relations.push_back(std::make_pair(I->first, I->second));
-        } else {
-          unsigned char LV = NI->second & I->second;
-          if (LV == EQ_BIT) {
-
-            assert(std::find(Kill.begin(), Kill.end(), I->first) != Kill.end()
-                    && "Lost EQ property.");
-            N->erase(NI);
-          } else {
-            NI->second = static_cast<LatticeVal>(LV);
-            assert(InequalityGraph::validPredicate(NI->second) &&
-                   "Invalid union of lattice values.");
-          }
-        }
+  /// UnreachableBlocks keeps tracks of blocks that are for one reason or
+  /// another discovered to be unreachable. This is used to cull the graph when
+  /// analyzing instructions, and to mark blocks with the "unreachable"
+  /// terminator instruction after the function has executed.
+  class VISIBILITY_HIDDEN UnreachableBlocks {
+  private:
+    std::vector<BasicBlock *> DeadBlocks;
 
-        // All edges are reciprocal; every Node that Kill points to also
-        // contains a pointer to Kill. Replace those with pointers with N.
-        unsigned iter = I->first->findIndex(*KI);
-        assert(iter != (unsigned)-1 && "Edge not reciprocal.");
-        I->first->assign(N, (I->first->begin()+iter)->second);
-        I->first->erase(I->first->begin()+iter);
-      }
+  public:
+    /// mark - mark a block as dead
+    void mark(BasicBlock *BB) {
+      std::vector<BasicBlock *>::iterator E = DeadBlocks.end();
+      std::vector<BasicBlock *>::iterator I =
+        std::lower_bound(DeadBlocks.begin(), E, BB);
 
-      // Removing references from N to Kill.
-      Node::iterator NI = N->find(*KI);
-      if (NI != N->end()) {
-        N->erase(NI); // breaks reciprocity until Kill is deleted.
-      }
+      if (I == E || *I != BB) DeadBlocks.insert(I, BB);
     }
 
-    N->setValue(NewCanonical);
+    /// isDead - returns whether a block is known to be dead already
+    bool isDead(BasicBlock *BB) {
+      std::vector<BasicBlock *>::iterator E = DeadBlocks.end();
+      std::vector<BasicBlock *>::iterator I =
+        std::lower_bound(DeadBlocks.begin(), E, BB);
 
-    // Update value mapping to point to the merged node.
-    for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end();
-         I != E; ++I) {
-      if (std::find(Kill.begin(), Kill.end(), I->second) != Kill.end())
-        I->second = N;
+      return I != E && *I == BB;
     }
 
-    for (typename C::iterator KI = Kill.begin(), KE = Kill.end();
-         KI != KE; ++KI) {
-      delete *KI;
-    }
-  }
+    /// kill - replace the dead blocks' terminator with an UnreachableInst.
+    bool kill() {
+      bool modified = false;
+      for (std::vector<BasicBlock *>::iterator I = DeadBlocks.begin(),
+           E = DeadBlocks.end(); I != E; ++I) {
+        BasicBlock *BB = *I;
 
-  void InequalityGraph::materialize() {
-    if (!ConcreteIG) return;
-    const InequalityGraph *IG = ConcreteIG;
-    ConcreteIG = NULL;