+ /// 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;