remove predicate simplifier, it never got the last bugs beaten

out of it, and jump threading, condprop and gvn are now getting
most of the benefit.  This was approved by Nicholas and Nicolas.



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

1 files changed, 0 insertions, 2704 deletions

diff --git a/lib/Transforms/Scalar/PredicateSimplifier.cpp b/lib/Transforms/Scalar/PredicateSimplifier.cpp
deleted file mode 100644
index b8ac1828db..0000000000
--- a/lib/Transforms/Scalar/PredicateSimplifier.cpp
+++ /dev/null
@@ -1,2704 +0,0 @@
-//===-- PredicateSimplifier.cpp - Path Sensitive Simplifier ---------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Path-sensitive optimizer. In a branch where x == y, replace uses of
-// x with y. Permits further optimization, such as the elimination of
-// the unreachable call:
-//
-// void test(int *p, int *q)
-// {
-//   if (p != q)
-//     return;
-// 
-//   if (*p != *q)
-//     foo(); // unreachable
-// }
-//
-//===----------------------------------------------------------------------===//
-//
-// The InequalityGraph focusses on four properties; equals, not equals,
-// less-than and less-than-or-equals-to. The greater-than forms are also held
-// just to allow walking from a lesser node to a greater one. These properties
-// are stored in a lattice; LE can become LT or EQ, NE can become LT or GT.
-//
-// These relationships define a graph between values of the same type. Each
-// Value is stored in a map table that retrieves the associated Node. This
-// is how EQ relationships are stored; the map contains pointers from equal
-// Value to the same node. The node contains a most canonical Value* form
-// and the list of known relationships with other nodes.
-//
-// If two nodes are known to be inequal, then they will contain pointers to
-// each other with an "NE" relationship. If node getNode(%x) is less than
-// getNode(%y), then the %x node will contain <%y, GT> and %y will contain
-// <%x, LT>. This allows us to tie nodes together into a graph like this:
-//
-//   %a < %b < %c < %d
-//
-// with four nodes representing the properties. The InequalityGraph provides
-// 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
-// responsible for analyzing the variable and seeing what new inferences
-// can be made from each property. For example:
-//
-//   %P = icmp ne i32* %ptr, null
-//   %a = and i1 %P, %Q
-//   br i1 %a label %cond_true, label %cond_false
-//
-// For the true branch, the VRPSolver will start with %a EQ true and look at
-// the definition of %a and find that it can infer that %P and %Q are both
-// true. From %P being true, it can infer that %ptr NE null. For the false
-// branch it can't infer anything from the "and" instruction.
-//
-// Besides branches, we can also infer properties from instruction that may
-// have undefined behaviour in certain cases. For example, the dividend of
-// a division may never be zero. After the division instruction, we may assume
-// that the dividend is not equal to zero.
-//
-//===----------------------------------------------------------------------===//
-//
-// The ValueRanges class stores the known integer bounds of a Value. When we
-// encounter i8 %a u< %b, the ValueRanges stores that %a = [1, 255] and
-// %b = [0, 254].
-//
-// It never stores an empty range, because that means that the code is
-// unreachable. It never stores a single-element range since that's an equality
-// relationship and better stored in the InequalityGraph, nor an empty range
-// since that is better stored in UnreachableBlocks.
-//
-//===----------------------------------------------------------------------===//
-
-#define DEBUG_TYPE "predsimplify"
-#include "llvm/Transforms/Scalar.h"
-#include "llvm/Constants.h"
-#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/SetVector.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/Analysis/Dominators.h"
-#include "llvm/Assembly/Writer.h"
-#include "llvm/Support/CFG.h"
-#include "llvm/Support/ConstantRange.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/InstVisitor.h"
-#include "llvm/Support/raw_ostream.h"
-#include "llvm/Target/TargetData.h"
-#include "llvm/Transforms/Utils/Local.h"
-#include <algorithm>
-#include <deque>
-#include <stack>
-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");
-STATISTIC(NumSnuggle     , "Number of comparisons snuggled");
-
-static const ConstantRange empty(1, false);
-
-namespace {
-  class DomTreeDFS {
-  public:
-    class Node {
-      friend class DomTreeDFS;
-    public:
-      typedef std::vector<Node *>::iterator       iterator;
-      typedef std::vector<Node *>::const_iterator const_iterator;
-
-      unsigned getDFSNumIn()  const { return DFSin;  }
-      unsigned getDFSNumOut() const { return DFSout; }
-
-      BasicBlock *getBlock() const { return BB; }
-
-      iterator begin() { return Children.begin(); }
-      iterator end()   { return Children.end();   }
-
-      const_iterator begin() const { return Children.begin(); }
-      const_iterator end()   const { return Children.end();   }
-
-      bool dominates(const Node *N) const {
-        return DFSin <= N->DFSin && DFSout >= N->DFSout;
-      }
-
-      bool DominatedBy(const Node *N) const {
-        return N->dominates(this);
-      }
-
-      /// Sorts by the number of descendants. With this, you can iterate
-      /// through a sorted list and the first matching entry is the most
-      /// specific match for your basic block. The order provided is stable;
-      /// DomTreeDFS::Nodes with the same number of descendants are sorted by
-      /// DFS in number.
-      bool operator<(const Node &N) const {
-        unsigned   spread =   DFSout -   DFSin;
-        unsigned N_spread = N.DFSout - N.DFSin;
-        if (spread == N_spread) return DFSin < N.DFSin;
-        return spread < N_spread;
-      }
-      bool operator>(const Node &N) const { return N < *this; }
-
-    private:
-      unsigned DFSin, DFSout;
-      BasicBlock *BB;
-
-      std::vector<Node *> Children;
-    };
-
-    // XXX: this may be slow. Instead of using "new" for each node, consider
-    // putting them in a vector to keep them contiguous.
-    explicit DomTreeDFS(DominatorTree *DT) {
-      std::stack<std::pair<Node *, DomTreeNode *> > S;
-
-      Entry = new Node;
-      Entry->BB = DT->getRootNode()->getBlock();
-      S.push(std::make_pair(Entry, DT->getRootNode()));
-
-      NodeMap[Entry->BB] = Entry;
-
-      while (!S.empty()) {
-        std::pair<Node *, DomTreeNode *> &Pair = S.top();
-        Node *N = Pair.first;
-        DomTreeNode *DTNode = Pair.second;
-        S.pop();
-
-        for (DomTreeNode::iterator I = DTNode->begin(), E = DTNode->end();
-             I != E; ++I) {
-          Node *NewNode = new Node;
-          NewNode->BB = (*I)->getBlock();
-          N->Children.push_back(NewNode);
-          S.push(std::make_pair(NewNode, *I));
-
-          NodeMap[NewNode->BB] = NewNode;
-        }
-      }
-
-      renumber();
-
-#ifndef NDEBUG
-      DEBUG(dump());
-#endif
-    }
-
-#ifndef NDEBUG
-    virtual
-#endif
-    ~DomTreeDFS() {
-      std::stack<Node *> S;
-
-      S.push(Entry);
-      while (!S.empty()) {
-        Node *N = S.top(); S.pop();
-
-        for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I)
-          S.push(*I);
-
-        delete N;
-      }
-    }
-
-    /// getRootNode - This returns the entry node for the CFG of the function.
-    Node *getRootNode() const { return Entry; }
-
-    /// getNodeForBlock - return the node for the specified basic block.
-    Node *getNodeForBlock(BasicBlock *BB) const {
-      if (!NodeMap.count(BB)) return 0;
-      return const_cast<DomTreeDFS*>(this)->NodeMap[BB];
-    }
-
-    /// dominates - returns true if the basic block for I1 dominates that of
-    /// the basic block for I2. If the instructions belong to the same basic
-    /// block, the instruction first instruction sequentially in the block is
-    /// considered dominating.
-    bool dominates(Instruction *I1, Instruction *I2) {
-      BasicBlock *BB1 = I1->getParent(),
-                 *BB2 = I2->getParent();
-      if (BB1 == BB2) {
-        if (isa<TerminatorInst>(I1)) return false;
-        if (isa<TerminatorInst>(I2)) return true;
-        if ( isa<PHINode>(I1) && !isa<PHINode>(I2)) return true;
-        if (!isa<PHINode>(I1) &&  isa<PHINode>(I2)) return false;
-
-        for (BasicBlock::const_iterator I = BB2->begin(), E = BB2->end();
-             I != E; ++I) {
-          if (&*I == I1) return true;
-          else if (&*I == I2) return false;
-        }
-        assert(!"Instructions not found in parent BasicBlock?");
-      } else {
-        Node *Node1 = getNodeForBlock(BB1),
-             *Node2 = getNodeForBlock(BB2);
-        return Node1 && Node2 && Node1->dominates(Node2);
-      }
-      return false; // Not reached
-    }
-
-  private:
-    /// renumber - calculates the depth first search numberings and applies
-    /// them onto the nodes.
-    void renumber() {
-      std::stack<std::pair<Node *, Node::iterator> > S;
-      unsigned n = 0;
-
-      Entry->DFSin = ++n;
-      S.push(std::make_pair(Entry, Entry->begin()));
-
-      while (!S.empty()) {
-        std::pair<Node *, Node::iterator> &Pair = S.top();
-        Node *N = Pair.first;
-        Node::iterator &I = Pair.second;
-
-        if (I == N->end()) {
-          N->DFSout = ++n;
-          S.pop();
-        } else {
-          Node *Next = *I++;
-          Next->DFSin = ++n;
-          S.push(std::make_pair(Next, Next->begin()));
-        }
-      }
-    }
-
-#ifndef NDEBUG
-    virtual void dump() const {
-      dump(errs());
-    }
-
-    void dump(raw_ostream &os) const {
-      os << "Predicate simplifier DomTreeDFS: \n";
-      dump(Entry, 0, os);
-      os << "\n\n";
-    }
-
-    void dump(Node *N, int depth, raw_ostream &os) const {
-      ++depth;
-      for (int i = 0; i < depth; ++i) { os << " "; }
-      os << "[" << depth << "] ";
-
-      os << N->getBlock()->getNameStr() << " (" << N->getDFSNumIn()
-         << ", " << N->getDFSNumOut() << ")\n";
-
-      for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I)
-        dump(*I, depth, os);
-    }
-#endif
-
-    Node *Entry;
-    std::map<BasicBlock *, Node *> NodeMap;
-  };
-
-  // 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 -- SGT                 14
-  //   0   1   1   1  1 -- SGE                 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 -- SLT                 22
-  //   1   0   1   1  1 -- SLE                 23
-  //   1   1   0   1  0 -- UGT                 26
-  //   1   1   0   1  1 -- UGE                 27
-  //   1   1   1   0  0 -- ULT                 28
-  //   1   1   1   0  1 -- ULE                 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,
-    ULT = SLT_BIT | SGT_BIT | ULT_BIT,
-    UGT = SLT_BIT | SGT_BIT | UGT_BIT,
-    SLT = SLT_BIT | ULT_BIT | UGT_BIT,
-    SGT = SGT_BIT | ULT_BIT | UGT_BIT,
-    SLE = SLT | EQ_BIT,
-    SGE = SGT | EQ_BIT,
-    ULE = ULT | EQ_BIT,
-    UGE = UGT | EQ_BIT
-  };
-
-#ifndef NDEBUG
-  /// validPredicate - determines whether a given value is actually a lattice
-  /// value. Only used in assertions or debugging.
-  static bool validPredicate(LatticeVal LV) {
-    switch (LV) {
-      case GT: case GE: case LT: case LE: case NE:
-      case SGTULT: case SGT: case SGEULE:
-      case SLTUGT: case SLT: case SLEUGE:
-      case ULT: case UGT:
-      case SLE: case SGE: case ULE: case UGE:
-        return true;
-      default:
-        return false;
-    }
-  }
-#endif
-
-  /// 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;
-  }
-
-  /// ValueNumbering stores the scope-specific value numbers for a given Value.
-  class ValueNumbering {
-
-    /// VNPair is a tuple of {Value, index number, DomTreeDFS::Node}. It
-    /// includes the comparison operators necessary to allow you to store it
-    /// in a sorted vector.
-    class VNPair {
-    public:
-      Value *V;
-      unsigned index;
-      DomTreeDFS::Node *Subtree;
-
-      VNPair(Value *V, unsigned index, DomTreeDFS::Node *Subtree)
-        : V(V), index(index), Subtree(Subtree) {}
-
-      bool operator==(const VNPair &RHS) const {
-        return V == RHS.V && Subtree == RHS.Subtree;
-      }
-
-      bool operator<(const VNPair &RHS) const {
-        if (V != RHS.V) return V < RHS.V;
-        return *Subtree < *RHS.Subtree;
-      }
-
-      bool operator<(Value *RHS) const {
-        return V < RHS;
-      }
-
-      bool operator>(Value *RHS) const {
-        return V > RHS;
-      }
-
-      friend bool operator<(Value *RHS, const VNPair &pair) {
-        return pair.operator>(RHS);
-      }
-    };
-
-    typedef std::vector<VNPair> VNMapType;
-    VNMapType VNMap;
-
-    /// The canonical choice for value number at index.
-    std::vector<Value *> Values;
-
-    DomTreeDFS *DTDFS;
-
-  public:
-#ifndef NDEBUG
-    virtual ~ValueNumbering() {}
-    virtual void dump() {
-      print(errs());
-    }
-
-    void print(raw_ostream &os) {
-      for (unsigned i = 1; i <= Values.size(); ++i) {
-        os << i << " = ";
-        WriteAsOperand(os, Values[i-1]);
-        os << " {";
-        for (unsigned j = 0; j < VNMap.size(); ++j) {
-          if (VNMap[j].index == i) {
-            WriteAsOperand(os, VNMap[j].V);
-            os << " (" << VNMap[j].Subtree->getDFSNumIn() << ")  ";
-          }
-        }
-        os << "}\n";
-      }
-    }
-#endif
-
-    /// compare - returns true if V1 is a better canonical value than V2.
-    bool compare(Value *V1, Value *V2) const {
-      if (isa<Constant>(V1))
-        return !isa<Constant>(V2);
-      else if (isa<Constant>(V2))
-        return false;
-      else if (isa<Argument>(V1))
-        return !isa<Argument>(V2);
-      else if (isa<Argument>(V2))
-        return false;
-
-      Instruction *I1 = dyn_cast<Instruction>(V1);
-      Instruction *I2 = dyn_cast<Instruction>(V2);
-
-      if (!I1 || !I2)
-        return V1->getNumUses() < V2->getNumUses();
-
-      return DTDFS->dominates(I1, I2);
-    }
-
-    ValueNumbering(DomTreeDFS *DTDFS) : DTDFS(DTDFS) {}
-
-    /// valueNumber - finds the value number for V under the Subtree. If
-    /// there is no value number, returns zero.
-    unsigned valueNumber(Value *V, DomTreeDFS::Node *Subtree) {
-      if (!(isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V)) || 
-          V->getType() == Type::getVoidTy(V->getContext())) return 0;
-
-      VNMapType::iterator E = VNMap.end();
-      VNPair pair(V, 0, Subtree);
-      VNMapType::iterator I = std::lower_bound(VNMap.begin(), E, pair);
-      while (I != E && I->V == V) {
-        if (I->Subtree->dominates(Subtree))
-          return I->index;
-        ++I;
-      }
-      return 0;
-    }
-
-    /// getOrInsertVN - always returns a value number, creating it if necessary.
-    unsigned getOrInsertVN(Value *V, DomTreeDFS::Node *Subtree) {
-      if (unsigned n = valueNumber(V, Subtree))
-        return n;
-      else
-        return newVN(V);
-    }
-
-    /// newVN - creates a new value number. Value V must not already have a
-    /// value number assigned.
-    unsigned newVN(Value *V) {
-      assert((isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V)) &&
-             "Bad Value for value numbering.");
-      assert(V->getType() != Type::getVoidTy(V->getContext()) &&
-             "Won't value number a void value");
-
-      Values.push_back(V);
-
-      VNPair pair = VNPair(V, Values.size(), DTDFS->getRootNode());
-      VNMapType::iterator I = std::lower_bound(VNMap.begin(), VNMap.end(), pair);
-      assert((I == VNMap.end() || value(I->index) != V) &&
-             "Attempt to create a duplicate value number.");
-      VNMap.insert(I, pair);
-
-      return Values.size();
-    }
-
-    /// value - returns the Value associated with a value number.
-    Value *value(unsigned index) const {
-      assert(index != 0 && "Zero index is reserved for not found.");
-      assert(index <= Values.size() && "Index out of range.");
-      return Values[index-1];
-    }
-
-    /// canonicalize - return a Value that is equal to V under Subtree.
-    Value *canonicalize(Value *V, DomTreeDFS::Node *Subtree) {
-      if (isa<Constant>(V)) return V;
-
-      if (unsigned n = valueNumber(V, Subtree))
-        return value(n);
-      else
-        return V;
-    }
-
-    /// addEquality - adds that value V belongs to the set of equivalent
-    /// values defined by value number n under Subtree.
-    void addEquality(unsigned n, Value *V, DomTreeDFS::Node *Subtree) {
-      assert(canonicalize(value(n), Subtree) == value(n) &&
-             "Node's 'canonical' choice isn't best within this subtree.");
-
-      // 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.
-
-      std::vector<Value *> ToRepoint(1, V);
-
-      if (unsigned Conflict = valueNumber(V, Subtree)) {
-        for (VNMapType::iterator I = VNMap.begin(), E = VNMap.end();
-             I != E; ++I) {
-          if (I->index == Conflict && I->Subtree->dominates(Subtree))
-            ToRepoint.push_back(I->V);
-        }
-      }
-
-      for (std::vector<Value *>::iterator VI = ToRepoint.begin(),
-           VE = ToRepoint.end(); VI != VE; ++VI) {
-        Value *V = *VI;
-
-        VNPair pair(V, n, Subtree);
-        VNMapType::iterator B = VNMap.begin(), E = VNMap.end();
-        VNMapType::iterator I = std::lower_bound(B, E, pair);
-        if (I != E && I->V == V && I->Subtree == Subtree)
-          I->index = n; // Update best choice
-        else
-          VNMap.insert(I, pair); // New Value
-
-        // XXX: we currently don't have to worry about updating values with
-        // more specific Subtrees, but we will need to for PHI node support.
-
-#ifndef NDEBUG
-        Value *V_n = value(n);
-        if (isa<Constant>(V) && isa<Constant>(V_n)) {
-          assert(V == V_n && "Constant equals different constant?");
-        }
-#endif
-      }
-    }
-
-    /// remove - removes all references to value V.
-    void remove(Value *V) {
-      VNMapType::iterator B = VNMap.begin(), E = VNMap.end();
-      VNPair pair(V, 0, DTDFS->getRootNode());
-      VNMapType::iterator J = std::upper_bound(B, E, pair);
-      VNMapType::iterator I = J;
-
-      while (I != B && (I == E || I->V == V)) --I;
-
-      VNMap.erase(I, J);
-    }
-  };
-
-  /// 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
-  /// consistency of the system.
-  ///
-  /// The InequalityGraph class may invalidate Node*s after any mutator call.
-  /// @brief The InequalityGraph stores the relationships between values.
-  class InequalityGraph {
-    ValueNumbering &VN;
-    DomTreeDFS::Node *TreeRoot;
-
-    InequalityGraph();                  // DO NOT IMPLEMENT
-    InequalityGraph(InequalityGraph &); // DO NOT IMPLEMENT
-  public:
-    InequalityGraph(ValueNumbering &VN, DomTreeDFS::Node *TreeRoot)
-      : VN(VN), TreeRoot(TreeRoot) {}
-
-    class Node;
-
-    /// 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 and an DomTreeDFS::Node specifying
-    /// the root in the dominator tree to which this edge applies.
-    class Edge {
-    public:
-      Edge(unsigned T, LatticeVal V, DomTreeDFS::Node *ST)
-        : To(T), LV(V), Subtree(ST) {}
-
-      unsigned To;
-      LatticeVal LV;
-      DomTreeDFS::Node *Subtree;
-
-      bool operator<(const Edge &edge) const {
-        if (To != edge.To) return To < edge.To;
-        return *Subtree < *edge.Subtree;
-      }
-
-      bool operator<(unsigned to) const {
-        return To < to;
-      }
-
-      bool operator>(unsigned to) const {
-        return To > to;
-      }
-
-      friend bool operator<(unsigned to, const Edge &edge) {
-        return edge.operator>(to);
-      }
-    };
-
-    /// A single node in the InequalityGraph. This stores the canonical Value
-    /// for the node, as well as the relationships with the neighbours.
-    ///
-    /// @brief A single node in the InequalityGraph.
-    class Node {
-      friend class InequalityGraph;
-
-      typedef SmallVector<Edge, 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;
-
-#ifndef NDEBUG
-      virtual ~Node() {}
-      virtual void dump() const {
-        dump(errs());
-      }
-    private:
-      void dump(raw_ostream &os) const {
-        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" };
-        for (Node::const_iterator NI = begin(), NE = end(); NI != NE; ++NI) {
-          os << names[NI->LV] << " " << NI->To
-             << " (" << NI->Subtree->getDFSNumIn() << "), ";
-        }
-      }
-    public:
-#endif
-
-      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, DomTreeDFS::Node *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, DomTreeDFS::Node *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;
-      }
-
-      /// update - updates the lattice value for a given node, creating a new
-      /// entry if one doesn't exist. The new lattice value must not be
-      /// inconsistent with any previously existing value.
-      void update(unsigned n, LatticeVal R, DomTreeDFS::Node *Subtree) {
-        assert(validPredicate(R) && "Invalid predicate.");
-
-        Edge edge(n, R, Subtree);
-        iterator B = begin(), E = end();
-        iterator I = std::lower_bound(B, E, edge);
-
-        iterator J = I;
-        while (J != E && J->To == n) {
-          if (Subtree->DominatedBy(J->Subtree))
-            break;
-          ++J;
-        }
-
-        if (J != E && J->To == n) {
-          edge.LV = static_cast<LatticeVal>(J->LV & R);
-          assert(validPredicate(edge.LV) && "Invalid union of lattice values.");
-
-          if (edge.LV == J->LV)
-            return; // This update adds nothing new.
-        }
-
-        if (I != B) {
-          // We also have to tighten any edge beneath our update.
-          for (iterator K = I - 1; K->To == n; --K) {
-            if (K->Subtree->DominatedBy(Subtree)) {
-              LatticeVal LV = static_cast<LatticeVal>(K->LV & edge.LV);
-              assert(validPredicate(LV) && "Invalid union of lattice values");
-              K->LV = LV;
-            }
-            if (K == B) break;
-          }
-        }
-
-        // Insert new edge at Subtree if it isn't already there.
-        if (I == E || I->To != n || Subtree != I->Subtree)
-          Relations.insert(I, edge);
-      }
-    };
-
-  private:
-
-    std::vector<Node> Nodes;
-
-  public:
-    /// node - returns the node object at a given value number. The pointer
-    /// returned may be invalidated on the next call to node().
-    Node *node(unsigned index) {
-      assert(VN.value(index)); // This triggers the necessary checks.
-      if (Nodes.size() < index) Nodes.resize(index);
-      return &Nodes[index-1];
-    }
-
-    /// isRelatedBy - true iff n1 op n2
-    bool isRelatedBy(unsigned n1, unsigned n2, DomTreeDFS::Node *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.
-
-    /// 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, DomTreeDFS::Node *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.");
-
-      // 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) {
-        // Break up the relationship into signed and unsigned comparison parts.
-        // If the signed parts of %a op1 %n1 match that of %n1 op2 %n2, and
-        // op1 and op2 aren't NE, then add %a op3 %n2. The new relationship
-        // should have the EQ_BIT iff it's set for both op1 and op2.
-
-        unsigned LV1_s = LV1 & (SLT_BIT|SGT_BIT);
-        unsigned LV1_u = LV1 & (ULT_BIT|UGT_BIT);
-
-        for (Node::iterator I = node(n1)->begin(), E = node(n1)->end(); I != E; ++I) {
-          if (I->LV != NE && I->To != n2) {
-
-            DomTreeDFS::Node *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);
-                node(n2)->update(I->To, reversePredicate(NewLV), Local_Subtree);
-              }
-            }
-          }
-        }
-
-        for (Node::iterator I = node(n2)->begin(), E = node(n2)->end(); I != E; ++I) {
-          if (I->LV != NE && I->To != n1) {
-            DomTreeDFS::Node *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);
-
-                node(n1)->update(I->To, NewLV, Local_Subtree);
-                node(I->To)->update(n1, reversePredicate(NewLV), Local_Subtree);
-              }
-            }
-          }
-        }
-      }
-
-      node(n1)->update(n2, LV1, Subtree);
-      node(n2)->update(n1, reversePredicate(LV1), Subtree);
-    }
-
-    /// remove - removes a node from the graph by removing all references to
-    /// and from it.
-    void remove(unsigned n) {
-      Node *N = node(n);
-      for (Node::iterator NI = N->begin(), NE = N->end(); NI != NE; ++NI) {
-        Node::iterator Iter = node(NI->To)->find(n, TreeRoot);
-        do {
-          node(NI->To)->Relations.erase(Iter);
-          Iter = node(NI->To)->find(n, TreeRoot);
-        } while (Iter != node(NI->To)->end());
-      }
-      N->Relations.clear();
-    }
-
-#ifndef NDEBUG
-    virtual ~InequalityGraph() {}
-    virtual void dump() {
-      dump(errs());
-    }
-
-    void dump(raw_ostream &os) {
-      for (unsigned i = 1; i <= Nodes.size(); ++i) {
-        os << i << " = {";
-        node(i)->dump(os);
-        os << "}\n";
-      }
-    }
-#endif
-  };
-
-  class VRPSolver;
-
-  /// ValueRanges tracks the known integer ranges and anti-ranges of the nodes
-  /// in the InequalityGraph.
-  class ValueRanges {
-    ValueNumbering &VN;
-    TargetData *TD;
-    LLVMContext *Context;
-
-    class ScopedRange {
-      typedef std::vector<std::pair<DomTreeDFS::Node *, ConstantRange> >
-              RangeListType;
-      RangeListType RangeList;
-
-      static bool swo(const std::pair<DomTreeDFS::Node *, ConstantRange> &LHS,
-                      const std::pair<DomTreeDFS::Node *, ConstantRange> &RHS) {
-        return *LHS.first < *RHS.first;
-      }
-
-    public:
-#ifndef NDEBUG
-      virtual ~ScopedRange() {}
-      virtual void dump() const {
-        dump(errs());
-      }
-
-      void dump(raw_ostream &os) const {
-        os << "{";
-        for (const_iterator I = begin(), E = end(); I != E; ++I) {
-          os << &I->second << " (" << I->first->getDFSNumIn() << "), ";
-        }
-        os << "}";
-      }
-#endif
-
-      typedef RangeListType::iterator       iterator;
-      typedef RangeListType::const_iterator const_iterator;
-
-      iterator begin() { return RangeList.begin(); }
-      iterator end()   { return RangeList.end(); }
-      const_iterator begin() const { return RangeList.begin(); }
-      const_iterator end()   const { return RangeList.end(); }
-
-      iterator find(DomTreeDFS::Node *Subtree) {
-        iterator E = end();
-        iterator I = std::lower_bound(begin(), E,
-                                      std::make_pair(Subtree, empty), swo);
-
-        while (I != E && !I->first->dominates(Subtree)) ++I;
-        return I;
-      }
-
-      const_iterator find(DomTreeDFS::Node *Subtree) const {<