lib/Transforms/Scalar/PredicateSimplifier.cpp

   1 //===-- PredicateSimplifier.cpp - Path Sensitive Simplifier ---------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Nick Lewycky and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Path-sensitive optimizer. In a branch where x == y, replace uses of
  11 // x with y. Permits further optimization, such as the elimination of
  12 // the unreachable call:
  13 //
  14 // void test(int *p, int *q)
  15 // {
  16 //   if (p != q)
  17 //     return;
  18 //
  19 //   if (*p != *q)
  20 //     foo(); // unreachable
  21 // }
  22 //
  23 //===----------------------------------------------------------------------===//
  24 //
  25 // The InequalityGraph focusses on four properties; equals, not equals,
  26 // less-than and less-than-or-equals-to. The greater-than forms are also held
  27 // just to allow walking from a lesser node to a greater one. These properties
  28 // are stored in a lattice; LE can become LT or EQ, NE can become LT or GT.
  29 //
  30 // These relationships define a graph between values of the same type. Each
  31 // Value is stored in a map table that retrieves the associated Node. This
  32 // is how EQ relationships are stored; the map contains pointers from equal
  33 // Value to the same node. The node contains a most canonical Value* form
  34 // and the list of known relationships with other nodes.
  35 //
  36 // If two nodes are known to be inequal, then they will contain pointers to
  37 // each other with an "NE" relationship. If node getNode(%x) is less than
  38 // getNode(%y), then the %x node will contain <%y, GT> and %y will contain
  39 // <%x, LT>. This allows us to tie nodes together into a graph like this:
  40 //
  41 //   %a < %b < %c < %d
  42 //
  43 // with four nodes representing the properties. The InequalityGraph provides
  44 // querying with "isRelatedBy" and mutators "addEquality" and "addInequality".
  45 // To find a relationship, we start with one of the nodes any binary search
  46 // through its list to find where the relationships with the second node start.
  47 // Then we iterate through those to find the first relationship that dominates
  48 // our context node.
  49 //
  50 // To create these properties, we wait until a branch or switch instruction
  51 // implies that a particular value is true (or false). The VRPSolver is
  52 // responsible for analyzing the variable and seeing what new inferences
  53 // can be made from each property. For example:
  54 //
  55 //   %P = icmp ne i32* %ptr, null
  56 //   %a = and i1 %P, %Q
  57 //   br i1 %a label %cond_true, label %cond_false
  58 //
  59 // For the true branch, the VRPSolver will start with %a EQ true and look at
  60 // the definition of %a and find that it can infer that %P and %Q are both
  61 // true. From %P being true, it can infer that %ptr NE null. For the false
  62 // branch it can't infer anything from the "and" instruction.
  63 //
  64 // Besides branches, we can also infer properties from instruction that may
  65 // have undefined behaviour in certain cases. For example, the dividend of
  66 // a division may never be zero. After the division instruction, we may assume
  67 // that the dividend is not equal to zero.
  68 //
  69 //===----------------------------------------------------------------------===//
  70 //
  71 // The ValueRanges class stores the known integer bounds of a Value. When we
  72 // encounter i8 %a u< %b, the ValueRanges stores that %a = [1, 255] and
  73 // %b = [0, 254]. Because we store these by Value*, you should always
  74 // canonicalize through the InequalityGraph first.
  75 //
  76 // It never stores an empty range, because that means that the code is
  77 // unreachable. It never stores a single-element range since that's an equality
  78 // relationship and better stored in the InequalityGraph.
  79 //
  80 //===----------------------------------------------------------------------===//
  81
  82 #define DEBUG_TYPE "predsimplify"
  83 #include "llvm/Transforms/Scalar.h"
  84 #include "llvm/Constants.h"
  85 #include "llvm/DerivedTypes.h"
  86 #include "llvm/Instructions.h"
  87 #include "llvm/Pass.h"
  88 #include "llvm/ADT/DepthFirstIterator.h"
  89 #include "llvm/ADT/SetOperations.h"
  90 #include "llvm/ADT/SetVector.h"
  91 #include "llvm/ADT/Statistic.h"
  92 #include "llvm/ADT/STLExtras.h"
  93 #include "llvm/Analysis/Dominators.h"
  94 #include "llvm/Analysis/ET-Forest.h"
  95 #include "llvm/Support/CFG.h"
  96 #include "llvm/Support/Compiler.h"
  97 #include "llvm/Support/ConstantRange.h"
  98 #include "llvm/Support/Debug.h"
  99 #include "llvm/Support/InstVisitor.h"
 100 #include "llvm/Transforms/Utils/Local.h"
 101 #include <algorithm>
 102 #include <deque>
 103 #include <sstream>
 104 using namespace llvm;
 105
 106 STATISTIC(NumVarsReplaced, "Number of argument substitutions");
 107 STATISTIC(NumInstruction , "Number of instructions removed");
 108 STATISTIC(NumSimple      , "Number of simple replacements");
 109 STATISTIC(NumBlocks      , "Number of blocks marked unreachable");
 110 STATISTIC(NumSnuggle     , "Number of comparisons snuggled");
 111
 112 namespace {
 113   // SLT SGT ULT UGT EQ
 114   //   0   1   0   1  0 -- GT                  10
 115   //   0   1   0   1  1 -- GE                  11
 116   //   0   1   1   0  0 -- SGTULT              12
 117   //   0   1   1   0  1 -- SGEULE              13
 118   //   0   1   1   1  0 -- SGT                 14
 119   //   0   1   1   1  1 -- SGE                 15
 120   //   1   0   0   1  0 -- SLTUGT              18
 121   //   1   0   0   1  1 -- SLEUGE              19
 122   //   1   0   1   0  0 -- LT                  20
 123   //   1   0   1   0  1 -- LE                  21
 124   //   1   0   1   1  0 -- SLT                 22
 125   //   1   0   1   1  1 -- SLE                 23
 126   //   1   1   0   1  0 -- UGT                 26
 127   //   1   1   0   1  1 -- UGE                 27
 128   //   1   1   1   0  0 -- ULT                 28
 129   //   1   1   1   0  1 -- ULE                 29
 130   //   1   1   1   1  0 -- NE                  30
 131   enum LatticeBits {
 132     EQ_BIT = 1, UGT_BIT = 2, ULT_BIT = 4, SGT_BIT = 8, SLT_BIT = 16
 133   };
 134   enum LatticeVal {
 135     GT = SGT_BIT | UGT_BIT,
 136     GE = GT | EQ_BIT,
 137     LT = SLT_BIT | ULT_BIT,
 138     LE = LT | EQ_BIT,
 139     NE = SLT_BIT | SGT_BIT | ULT_BIT | UGT_BIT,
 140     SGTULT = SGT_BIT | ULT_BIT,
 141     SGEULE = SGTULT | EQ_BIT,
 142     SLTUGT = SLT_BIT | UGT_BIT,
 143     SLEUGE = SLTUGT | EQ_BIT,
 144     ULT = SLT_BIT | SGT_BIT | ULT_BIT,
 145     UGT = SLT_BIT | SGT_BIT | UGT_BIT,
 146     SLT = SLT_BIT | ULT_BIT | UGT_BIT,
 147     SGT = SGT_BIT | ULT_BIT | UGT_BIT,
 148     SLE = SLT | EQ_BIT,
 149     SGE = SGT | EQ_BIT,
 150     ULE = ULT | EQ_BIT,
 151     UGE = UGT | EQ_BIT
 152   };
 153
 154   static bool validPredicate(LatticeVal LV) {
 155     switch (LV) {
 156       case GT: case GE: case LT: case LE: case NE:
 157       case SGTULT: case SGT: case SGEULE:
 158       case SLTUGT: case SLT: case SLEUGE:
 159       case ULT: case UGT:
 160       case SLE: case SGE: case ULE: case UGE:
 161         return true;
 162       default:
 163         return false;
 164     }
 165   }
 166
 167   /// reversePredicate - reverse the direction of the inequality
 168   static LatticeVal reversePredicate(LatticeVal LV) {
 169     unsigned reverse = LV ^ (SLT_BIT|SGT_BIT|ULT_BIT|UGT_BIT); //preserve EQ_BIT
 170
 171     if ((reverse & (SLT_BIT|SGT_BIT)) == 0)
 172       reverse |= (SLT_BIT|SGT_BIT);
 173
 174     if ((reverse & (ULT_BIT|UGT_BIT)) == 0)
 175       reverse |= (ULT_BIT|UGT_BIT);
 176
 177     LatticeVal Rev = static_cast<LatticeVal>(reverse);
 178     assert(validPredicate(Rev) && "Failed reversing predicate.");
 179     return Rev;
 180   }
 181
 182   /// This is a StrictWeakOrdering predicate that sorts ETNodes by how many
 183   /// descendants they have. With this, you can iterate through a list sorted
 184   /// by this operation and the first matching entry is the most specific
 185   /// match for your basic block. The order provided is stable; ETNodes with
 186   /// the same number of children are sorted by pointer address.
 187   struct VISIBILITY_HIDDEN OrderByDominance {
 188     bool operator()(const ETNode *LHS, const ETNode *RHS) const {
 189       unsigned LHS_spread = LHS->getDFSNumOut() - LHS->getDFSNumIn();
 190       unsigned RHS_spread = RHS->getDFSNumOut() - RHS->getDFSNumIn();
 191       if (LHS_spread != RHS_spread) return LHS_spread < RHS_spread;
 192       else return LHS < RHS;
 193     }
 194   };
 195
 196   /// The InequalityGraph stores the relationships between values.
 197   /// Each Value in the graph is assigned to a Node. Nodes are pointer
 198   /// comparable for equality. The caller is expected to maintain the logical
 199   /// consistency of the system.
 200   ///
 201   /// The InequalityGraph class may invalidate Node*s after any mutator call.
 202   /// @brief The InequalityGraph stores the relationships between values.
 203   class VISIBILITY_HIDDEN InequalityGraph {
 204     ETNode *TreeRoot;
 205
 206     InequalityGraph();                  // DO NOT IMPLEMENT
 207     InequalityGraph(InequalityGraph &); // DO NOT IMPLEMENT
 208   public:
 209     explicit InequalityGraph(ETNode *TreeRoot) : TreeRoot(TreeRoot) {}
 210
 211     class Node;
 212
 213     /// An Edge is contained inside a Node making one end of the edge implicit
 214     /// and contains a pointer to the other end. The edge contains a lattice
 215     /// value specifying the relationship and an ETNode specifying the root
 216     /// in the dominator tree to which this edge applies.
 217     class VISIBILITY_HIDDEN Edge {
 218     public:
 219       Edge(unsigned T, LatticeVal V, ETNode *ST)
 220         : To(T), LV(V), Subtree(ST) {}
 221
 222       unsigned To;
 223       LatticeVal LV;
 224       ETNode *Subtree;
 225
 226       bool operator<(const Edge &edge) const {
 227         if (To != edge.To) return To < edge.To;
 228         else return OrderByDominance()(Subtree, edge.Subtree);
 229       }
 230       bool operator<(unsigned to) const {
 231         return To < to;
 232       }
 233     };
 234
 235     /// A single node in the InequalityGraph. This stores the canonical Value
 236     /// for the node, as well as the relationships with the neighbours.
 237     ///
 238     /// @brief A single node in the InequalityGraph.
 239     class VISIBILITY_HIDDEN Node {
 240       friend class InequalityGraph;
 241
 242       typedef SmallVector<Edge, 4> RelationsType;
 243       RelationsType Relations;
 244
 245       Value *Canonical;
 246
 247       // TODO: can this idea improve performance?
 248       //friend class std::vector<Node>;
 249       //Node(Node &N) { RelationsType.swap(N.RelationsType); }
 250
 251     public:
 252       typedef RelationsType::iterator       iterator;
 253       typedef RelationsType::const_iterator const_iterator;
 254
 255       Node(Value *V) : Canonical(V) {}
 256
 257     private:
 258 #ifndef NDEBUG
 259     public:
 260       virtual ~Node() {}
 261       virtual void dump() const {
 262         dump(*cerr.stream());
 263       }
 264     private:
 265       void dump(std::ostream &os) const  {
 266         os << *getValue() << ":\n";
 267         for (Node::const_iterator NI = begin(), NE = end(); NI != NE; ++NI) {
 268           static const std::string names[32] =
 269             { "000000", "000001", "000002", "000003", "000004", "000005",
 270               "000006", "000007", "000008", "000009", "     >", "    >=",
 271               "  s>u<", "s>=u<=", "    s>", "   s>=", "000016", "000017",
 272               "  s<u>", "s<=u>=", "     <", "    <=", "    s<", "   s<=",
 273               "000024", "000025", "    u>", "   u>=", "    u<", "   u<=",
 274               "    !=", "000031" };
 275           os << "  " << names[NI->LV] << " " << NI->To
 276              << " (" << NI->Subtree->getDFSNumIn() << ")\n";
 277         }
 278       }
 279 #endif
 280
 281     public:
 282       iterator begin()             { return Relations.begin(); }
 283       iterator end()               { return Relations.end();   }
 284       const_iterator begin() const { return Relations.begin(); }
 285       const_iterator end()   const { return Relations.end();   }
 286
 287       iterator find(unsigned n, ETNode *Subtree) {
 288         iterator E = end();
 289         for (iterator I = std::lower_bound(begin(), E, n);
 290              I != E && I->To == n; ++I) {
 291           if (Subtree->DominatedBy(I->Subtree))
 292             return I;
 293         }
 294         return E;
 295       }
 296
 297       const_iterator find(unsigned n, ETNode *Subtree) const {
 298         const_iterator E = end();
 299         for (const_iterator I = std::lower_bound(begin(), E, n);
 300              I != E && I->To == n; ++I) {
 301           if (Subtree->DominatedBy(I->Subtree))
 302             return I;
 303         }
 304         return E;
 305       }
 306
 307       Value *getValue() const
 308       {
 309         return Canonical;
 310       }
 311
 312       /// Updates the lattice value for a given node. Create a new entry if
 313       /// one doesn't exist, otherwise it merges the values. The new lattice
 314       /// value must not be inconsistent with any previously existing value.
 315       void update(unsigned n, LatticeVal R, ETNode *Subtree) {
 316         assert(validPredicate(R) && "Invalid predicate.");
 317         iterator I = find(n, Subtree);
 318         if (I == end()) {
 319           Edge edge(n, R, Subtree);
 320           iterator Insert = std::lower_bound(begin(), end(), edge);
 321           Relations.insert(Insert, edge);
 322         } else {
 323           LatticeVal LV = static_cast<LatticeVal>(I->LV & R);
 324           assert(validPredicate(LV) && "Invalid union of lattice values.");
 325           if (LV != I->LV) {
 326             if (Subtree != I->Subtree) {
 327               assert(Subtree->DominatedBy(I->Subtree) &&
 328                      "Find returned subtree that doesn't apply.");
 329
 330               Edge edge(n, R, Subtree);
 331               iterator Insert = std::lower_bound(begin(), end(), edge);
 332               Relations.insert(Insert, edge); // invalidates I
 333               I = find(n, Subtree);
 334             }
 335
 336             // Also, we have to tighten any edge that Subtree dominates.
 337             for (iterator B = begin(); I->To == n; --I) {
 338               if (I->Subtree->DominatedBy(Subtree)) {
 339                 LatticeVal LV = static_cast<LatticeVal>(I->LV & R);
 340                 assert(validPredicate(LV) && "Invalid union of lattice values.");
 341                 I->LV = LV;
 342               }
 343               if (I == B) break;
 344             }
 345           }
 346         }
 347       }
 348     };
 349
 350   private:
 351     struct VISIBILITY_HIDDEN NodeMapEdge {
 352       Value *V;
 353       unsigned index;
 354       ETNode *Subtree;
 355
 356       NodeMapEdge(Value *V, unsigned index, ETNode *Subtree)
 357         : V(V), index(index), Subtree(Subtree) {}
 358
 359       bool operator==(const NodeMapEdge &RHS) const {
 360         return V == RHS.V &&
 361                Subtree == RHS.Subtree;
 362       }
 363
 364       bool operator<(const NodeMapEdge &RHS) const {
 365         if (V != RHS.V) return V < RHS.V;
 366         return OrderByDominance()(Subtree, RHS.Subtree);
 367       }
 368
 369       bool operator<(Value *RHS) const {
 370         return V < RHS;
 371       }
 372     };
 373
 374     typedef std::vector<NodeMapEdge> NodeMapType;
 375     NodeMapType NodeMap;
 376
 377     std::vector<Node> Nodes;
 378
 379   public:
 380     /// node - returns the node object at a given index retrieved from getNode.
 381     /// Index zero is reserved and may not be passed in here. The pointer
 382     /// returned is valid until the next call to newNode or getOrInsertNode.
 383     Node *node(unsigned index) {
 384       assert(index != 0 && "Zero index is reserved for not found.");
 385       assert(index <= Nodes.size() && "Index out of range.");
 386       return &Nodes[index-1];
 387     }
 388
 389     /// Returns the node currently representing Value V, or zero if no such
 390     /// node exists.
 391     unsigned getNode(Value *V, ETNode *Subtree) {
 392       NodeMapType::iterator E = NodeMap.end();
 393       NodeMapEdge Edge(V, 0, Subtree);
 394       NodeMapType::iterator I = std::lower_bound(NodeMap.begin(), E, Edge);
 395       while (I != E && I->V == V) {
 396         if (Subtree->DominatedBy(I->Subtree))
 397           return I->index;
 398         ++I;
 399       }
 400       return 0;
 401     }
 402
 403     /// getOrInsertNode - always returns a valid node index, creating a node
 404     /// to match the Value if needed.
 405     unsigned getOrInsertNode(Value *V, ETNode *Subtree) {
 406       if (unsigned n = getNode(V, Subtree))
 407         return n;
 408       else
 409         return newNode(V);
 410     }
 411
 412     /// newNode - creates a new node for a given Value and returns the index.
 413     unsigned newNode(Value *V) {
 414       Nodes.push_back(Node(V));
 415
 416       NodeMapEdge MapEntry = NodeMapEdge(V, Nodes.size(), TreeRoot);
 417       assert(!std::binary_search(NodeMap.begin(), NodeMap.end(), MapEntry) &&
 418              "Attempt to create a duplicate Node.");
 419       NodeMap.insert(std::lower_bound(NodeMap.begin(), NodeMap.end(),
 420                                       MapEntry), MapEntry);
 421       return MapEntry.index;
 422     }
 423
 424     /// If the Value is in the graph, return the canonical form. Otherwise,
 425     /// return the original Value.
 426     Value *canonicalize(Value *V, ETNode *Subtree) {
 427       if (isa<Constant>(V)) return V;
 428
 429       if (unsigned n = getNode(V, Subtree))
 430         return node(n)->getValue();
 431       else
 432         return V;
 433     }
 434
 435     /// isRelatedBy - true iff n1 op n2
 436     bool isRelatedBy(unsigned n1, unsigned n2, ETNode *Subtree, LatticeVal LV) {
 437       if (n1 == n2) return LV & EQ_BIT;
 438
 439       Node *N1 = node(n1);
 440       Node::iterator I = N1->find(n2, Subtree), E = N1->end();
 441       if (I != E) return (I->LV & LV) == I->LV;
 442
 443       return false;
 444     }
 445
 446     // The add* methods assume that your input is logically valid and may
 447     // assertion-fail or infinitely loop if you attempt a contradiction.
 448
 449     void addEquality(unsigned n, Value *V, ETNode *Subtree) {
 450       assert(canonicalize(node(n)->getValue(), Subtree) == node(n)->getValue()
 451              && "Node's 'canonical' choice isn't best within this subtree.");
 452
 453       // Suppose that we are given "%x -> node #1 (%y)". The problem is that
 454       // we may already have "%z -> node #2 (%x)" somewhere above us in the
 455       // graph. We need to find those edges and add "%z -> node #1 (%y)"
 456       // to keep the lookups canonical.
 457
 458       std::vector<Value *> ToRepoint;
 459       ToRepoint.push_back(V);
 460
 461       if (unsigned Conflict = getNode(V, Subtree)) {
 462         // XXX: NodeMap.size() exceeds 68,000 entries compiling kimwitu++!
 463         for (NodeMapType::iterator I = NodeMap.begin(), E = NodeMap.end();
 464              I != E; ++I) {
 465           if (I->index == Conflict && Subtree->DominatedBy(I->Subtree))
 466             ToRepoint.push_back(I->V);
 467         }
 468       }
 469
 470       for (std::vector<Value *>::iterator VI = ToRepoint.begin(),
 471            VE = ToRepoint.end(); VI != VE; ++VI) {
 472         Value *V = *VI;
 473
 474         // XXX: review this code. This may be doing too many insertions.
 475         NodeMapEdge Edge(V, n, Subtree);
 476         NodeMapType::iterator E = NodeMap.end();
 477         NodeMapType::iterator I = std::lower_bound(NodeMap.begin(), E, Edge);
 478         if (I == E || I->V != V || I->Subtree != Subtree) {
 479           // New Value
 480           NodeMap.insert(I, Edge);
 481         } else if (I != E && I->V == V && I->Subtree == Subtree) {
 482           // Update best choice
 483           I->index = n;
 484         }
 485
 486 #ifndef NDEBUG
 487         Node *N = node(n);
 488         if (isa<Constant>(V)) {
 489           if (isa<Constant>(N->getValue())) {
 490             assert(V == N->getValue() && "Constant equals different constant?");
 491           }
 492         }
 493 #endif
 494       }
 495     }
 496
 497     /// addInequality - Sets n1 op n2.
 498     /// It is also an error to call this on an inequality that is already true.
 499     void addInequality(unsigned n1, unsigned n2, ETNode *Subtree,
 500                        LatticeVal LV1) {
 501       assert(n1 != n2 && "A node can't be inequal to itself.");
 502
 503       if (LV1 != NE)
 504         assert(!isRelatedBy(n1, n2, Subtree, reversePredicate(LV1)) &&
 505                "Contradictory inequality.");
 506
 507       Node *N1 = node(n1);
 508       Node *N2 = node(n2);
 509
 510       // Suppose we're adding %n1 < %n2. Find all the %a < %n1 and
 511       // add %a < %n2 too. This keeps the graph fully connected.
 512       if (LV1 != NE) {
 513         // Someone with a head for this sort of logic, please review this.
 514         // Given that %x SLTUGT %y and %a SLE %x, what is the relationship
 515         // between %a and %y? I believe the below code is correct, but I don't
 516         // think it's the most efficient solution.
 517
 518         unsigned LV1_s = LV1 & (SLT_BIT|SGT_BIT);
 519         unsigned LV1_u = LV1 & (ULT_BIT|UGT_BIT);
 520         for (Node::iterator I = N1->begin(), E = N1->end(); I != E; ++I) {
 521           if (I->LV != NE && I->To != n2) {
 522             ETNode *Local_Subtree = NULL;
 523             if (Subtree->DominatedBy(I->Subtree))
 524               Local_Subtree = Subtree;
 525             else if (I->Subtree->DominatedBy(Subtree))
 526               Local_Subtree = I->Subtree;
 527
 528             if (Local_Subtree) {
 529               unsigned new_relationship = 0;
 530               LatticeVal ILV = reversePredicate(I->LV);
 531               unsigned ILV_s = ILV & (SLT_BIT|SGT_BIT);
 532               unsigned ILV_u = ILV & (ULT_BIT|UGT_BIT);
 533
 534               if (LV1_s != (SLT_BIT|SGT_BIT) && ILV_s == LV1_s)
 535                 new_relationship |= ILV_s;
 536
 537               if (LV1_u != (ULT_BIT|UGT_BIT) && ILV_u == LV1_u)
 538                 new_relationship |= ILV_u;
 539
 540               if (new_relationship) {
 541                 if ((new_relationship & (SLT_BIT|SGT_BIT)) == 0)
 542                   new_relationship |= (SLT_BIT|SGT_BIT);
 543                 if ((new_relationship & (ULT_BIT|UGT_BIT)) == 0)
 544                   new_relationship |= (ULT_BIT|UGT_BIT);
 545                 if ((LV1 & EQ_BIT) && (ILV & EQ_BIT))
 546                   new_relationship |= EQ_BIT;
 547
 548                 LatticeVal NewLV = static_cast<LatticeVal>(new_relationship);
 549
 550                 node(I->To)->update(n2, NewLV, Local_Subtree);
 551                 N2->update(I->To, reversePredicate(NewLV), Local_Subtree);
 552               }
 553             }
 554           }
 555         }
 556
 557         for (Node::iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
 558           if (I->LV != NE && I->To != n1) {
 559             ETNode *Local_Subtree = NULL;
 560             if (Subtree->DominatedBy(I->Subtree))
 561               Local_Subtree = Subtree;
 562             else if (I->Subtree->DominatedBy(Subtree))
 563               Local_Subtree = I->Subtree;
 564
 565             if (Local_Subtree) {
 566               unsigned new_relationship = 0;
 567               unsigned ILV_s = I->LV & (SLT_BIT|SGT_BIT);
 568               unsigned ILV_u = I->LV & (ULT_BIT|UGT_BIT);
 569
 570               if (LV1_s != (SLT_BIT|SGT_BIT) && ILV_s == LV1_s)
 571                 new_relationship |= ILV_s;
 572
 573               if (LV1_u != (ULT_BIT|UGT_BIT) && ILV_u == LV1_u)
 574                 new_relationship |= ILV_u;
 575
 576               if (new_relationship) {
 577                 if ((new_relationship & (SLT_BIT|SGT_BIT)) == 0)
 578                   new_relationship |= (SLT_BIT|SGT_BIT);
 579                 if ((new_relationship & (ULT_BIT|UGT_BIT)) == 0)
 580                   new_relationship |= (ULT_BIT|UGT_BIT);
 581                 if ((LV1 & EQ_BIT) && (I->LV & EQ_BIT))
 582                   new_relationship |= EQ_BIT;
 583
 584                 LatticeVal NewLV = static_cast<LatticeVal>(new_relationship);
 585
 586                 N1->update(I->To, NewLV, Local_Subtree);
 587                 node(I->To)->update(n1, reversePredicate(NewLV), Local_Subtree);
 588               }
 589             }
 590           }
 591         }
 592       }
 593
 594       N1->update(n2, LV1, Subtree);
 595       N2->update(n1, reversePredicate(LV1), Subtree);
 596     }
 597
 598     /// remove - Removes a Value from the graph. If the value is the canonical
 599     /// choice for a Node, destroys the Node from the graph deleting all edges
 600     /// to and from it. This method does not renumber the nodes.
 601     void remove(Value *V) {
 602       for (unsigned i = 0; i < NodeMap.size();) {
 603         NodeMapType::iterator I = NodeMap.begin()+i;
 604         if (I->V == V) {
 605           Node *N = node(I->index);
 606           if (node(I->index)->getValue() == V) {
 607             for (Node::iterator NI = N->begin(), NE = N->end(); NI != NE; ++NI){
 608               Node::iterator Iter = node(NI->To)->find(I->index, TreeRoot);
 609               do {
 610                 node(NI->To)->Relations.erase(Iter);
 611                 Iter = node(NI->To)->find(I->index, TreeRoot);
 612               } while (Iter != node(NI->To)->end());
 613             }
 614             N->Canonical = NULL;
 615           }
 616           N->Relations.clear();
 617           NodeMap.erase(I);
 618         } else ++i;
 619       }
 620     }
 621
 622 #ifndef NDEBUG
 623     virtual ~InequalityGraph() {}
 624     virtual void dump() {
 625       dump(*cerr.stream());
 626     }
 627
 628     void dump(std::ostream &os) {
 629     std::set<Node *> VisitedNodes;
 630     for (NodeMapType::const_iterator I = NodeMap.begin(), E = NodeMap.end();
 631          I != E; ++I) {
 632       Node *N = node(I->index);
 633       os << *I->V << " == " << I->index
 634          << "(" << I->Subtree->getDFSNumIn() << ")\n";
 635       if (VisitedNodes.insert(N).second) {
 636         os << I->index << ". ";
 637         if (!N->getValue()) os << "(deleted node)\n";
 638         else N->dump(os);
 639       }
 640     }
 641   }
 642 #endif
 643   };
 644
 645   class VRPSolver;
 646
 647   /// ValueRanges tracks the known integer ranges and anti-ranges of the nodes
 648   /// in the InequalityGraph.
 649   class VISIBILITY_HIDDEN ValueRanges {
 650
 651     /// A ScopedRange ties an InequalityGraph node with a ConstantRange under
 652     /// the scope of a rooted subtree in the dominator tree.
 653     class VISIBILITY_HIDDEN ScopedRange {
 654     public:
 655       ScopedRange(Value *V, ConstantRange CR, ETNode *ST)
 656         : V(V), CR(CR), Subtree(ST) {}
 657
 658       Value *V;
 659       ConstantRange CR;
 660       ETNode *Subtree;
 661
 662       bool operator<(const ScopedRange &range) const {
 663         if (V != range.V) return V < range.V;
 664         else return OrderByDominance()(Subtree, range.Subtree);
 665       }
 666
 667       bool operator<(const Value *value) const {
 668         return V < value;
 669       }
 670     };
 671
 672     std::vector<ScopedRange> Ranges;
 673     typedef std::vector<ScopedRange>::iterator iterator;
 674
 675     // XXX: this is a copy of the code in InequalityGraph::Node. Perhaps a
 676     // intrusive domtree-scoped container is in order?
 677
 678     iterator begin() { return Ranges.begin(); }
 679     iterator end()   { return Ranges.end();   }
 680
 681     iterator find(Value *V, ETNode *Subtree) {
 682       iterator E = end();
 683       for (iterator I = std::lower_bound(begin(), E, V);
 684            I != E && I->V == V; ++I) {
 685         if (Subtree->DominatedBy(I->Subtree))
 686           return I;
 687       }
 688       return E;
 689     }
 690
 691     void update(Value *V, ConstantRange CR, ETNode *Subtree) {
 692       assert(!CR.isEmptySet() && "Empty ConstantRange!");
 693       if (CR.isFullSet()) return;
 694
 695       iterator I = find(V, Subtree);
 696       if (I == end()) {
 697         ScopedRange range(V, CR, Subtree);
 698         iterator Insert = std::lower_bound(begin(), end(), range);
 699         Ranges.insert(Insert, range);
 700       } else {
 701         CR = CR.intersectWith(I->CR);
 702         assert(!CR.isEmptySet() && "Empty intersection of ConstantRanges!");
 703
 704         if (CR != I->CR) {
 705           if (Subtree != I->Subtree) {
 706             assert(Subtree->DominatedBy(I->Subtree) &&
 707                    "Find returned subtree that doesn't apply.");
 708
 709             ScopedRange range(V, CR, Subtree);
 710             iterator Insert = std::lower_bound(begin(), end(), range);
 711             Ranges.insert(Insert, range); // invalidates I
 712             I = find(V, Subtree);
 713           }
 714
 715           // Also, we have to tighten any edge that Subtree dominates.
 716           for (iterator B = begin(); I->V == V; --I) {
 717             if (I->Subtree->DominatedBy(Subtree)) {
 718               CR = CR.intersectWith(I->CR);
 719               assert(!CR.isEmptySet() &&
 720                      "Empty intersection of ConstantRanges!");
 721               I->CR = CR;
 722             }
 723             if (I == B) break;
 724           }
 725         }
 726       }
 727     }
 728
 729     /// range - Creates a ConstantRange representing the set of all values
 730     /// that match the ICmpInst::Predicate with any of the values in CR.
 731     ConstantRange range(ICmpInst::Predicate ICmpOpcode,
 732                         const ConstantRange &CR) {
 733       uint32_t W = CR.getBitWidth();
 734       switch (ICmpOpcode) {
 735         default: assert(!"Invalid ICmp opcode to range()");
 736         case ICmpInst::ICMP_EQ:
 737           return ConstantRange(CR.getLower(), CR.getUpper());
 738         case ICmpInst::ICMP_NE:
 739           if (CR.isSingleElement())
 740             return ConstantRange(CR.getUpper(), CR.getLower());
 741           return ConstantRange(W);
 742         case ICmpInst::ICMP_ULT:
 743           return ConstantRange(APInt::getMinValue(W), CR.getUnsignedMax());
 744         case ICmpInst::ICMP_SLT:
 745           return ConstantRange(APInt::getSignedMinValue(W), CR.getSignedMax());
 746         case ICmpInst::ICMP_ULE: {
 747           APInt UMax = CR.getUnsignedMax();
 748           if (UMax == APInt::getMaxValue(W))
 749             return ConstantRange(W);
 750           return ConstantRange(APInt::getMinValue(W), UMax + 1);
 751         }
 752         case ICmpInst::ICMP_SLE: {
 753           APInt SMax = CR.getSignedMax();
 754           if (SMax     == APInt::getSignedMaxValue(W) ||
 755               SMax + 1 == APInt::getSignedMaxValue(W))
 756             return ConstantRange(W);
 757           return ConstantRange(APInt::getSignedMinValue(W), SMax + 1);
 758         }
 759         case ICmpInst::ICMP_UGT:
 760           return ConstantRange(CR.getUnsignedMin() + 1,
 761                                APInt::getMaxValue(W) + 1);
 762         case ICmpInst::ICMP_SGT:
 763           return ConstantRange(CR.getSignedMin() + 1,
 764                                APInt::getSignedMaxValue(W) + 1);
 765         case ICmpInst::ICMP_UGE: {
 766           APInt UMin = CR.getUnsignedMin();
 767           if (UMin == APInt::getMinValue(W))
 768             return ConstantRange(W);
 769           return ConstantRange(UMin, APInt::getMaxValue(W) + 1);
 770         }
 771         case ICmpInst::ICMP_SGE: {
 772           APInt SMin = CR.getSignedMin();
 773           if (SMin == APInt::getSignedMinValue(W))
 774             return ConstantRange(W);
 775           return ConstantRange(SMin, APInt::getSignedMaxValue(W) + 1);
 776         }
 777       }
 778     }
 779
 780     /// create - Creates a ConstantRange that matches the given LatticeVal
 781     /// relation with a given integer.
 782     ConstantRange create(LatticeVal LV, const ConstantRange &CR) {
 783       assert(!CR.isEmptySet() && "Can't deal with empty set.");
 784
 785       if (LV == NE)
 786         return range(ICmpInst::ICMP_NE, CR);
 787
 788       unsigned LV_s = LV & (SGT_BIT|SLT_BIT);
 789       unsigned LV_u = LV & (UGT_BIT|ULT_BIT);
 790       bool hasEQ = LV & EQ_BIT;
 791
 792       ConstantRange Range(CR.getBitWidth());
 793
 794       if (LV_s == SGT_BIT) {
 795         Range = Range.intersectWith(range(
 796                     hasEQ ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_SGT, CR));
 797       } else if (LV_s == SLT_BIT) {
 798         Range = Range.intersectWith(range(
 799                     hasEQ ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_SLT, CR));
 800       }
 801
 802       if (LV_u == UGT_BIT) {
 803         Range = Range.intersectWith(range(
 804                     hasEQ ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_UGT, CR));
 805       } else if (LV_u == ULT_BIT) {
 806         Range = Range.intersectWith(range(
 807                     hasEQ ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_ULT, CR));
 808       }
 809
 810       return Range;
 811     }
 812
 813     ConstantRange rangeFromValue(Value *V, ETNode *Subtree, uint32_t W) {
 814       ConstantInt *C = dyn_cast<ConstantInt>(V);
 815       if (C) {
 816         return ConstantRange(C->getValue());
 817       } else {
 818         iterator I = find(V, Subtree);
 819         if (I != end())
 820           return I->CR;
 821       }
 822       return ConstantRange(W);
 823     }
 824
 825     static uint32_t widthOfValue(Value *V) {
 826       const Type *Ty = V->getType();
 827       if (const IntegerType *ITy = dyn_cast<IntegerType>(Ty))
 828         return ITy->getBitWidth();
 829
 830       // XXX: I'd like to transform T* into the appropriate integer by
 831       // bit length, however that data may not be available.
 832
 833       return 0;
 834     }
 835
 836 #ifndef NDEBUG
 837     bool isCanonical(Value *V, ETNode *Subtree, VRPSolver *VRP);
 838 #endif
 839
 840   public:
 841
 842     bool isRelatedBy(Value *V1, Value *V2, ETNode *Subtree, LatticeVal LV) {
 843       uint32_t W = widthOfValue(V1);
 844       if (!W) return false;
 845
 846       ConstantRange CR1 = rangeFromValue(V1, Subtree, W);
 847       ConstantRange CR2 = rangeFromValue(V2, Subtree, W);
 848
 849       // True iff all values in CR1 are LV to all values in CR2.
 850       switch (LV) {
 851       default: assert(!"Impossible lattice value!");
 852       case NE:
 853         return CR1.intersectWith(CR2).isEmptySet();
 854       case ULT:
 855         return CR1.getUnsignedMax().ult(CR2.getUnsignedMin());
 856       case ULE:
 857         return CR1.getUnsignedMax().ule(CR2.getUnsignedMin());
 858       case UGT:
 859         return CR1.getUnsignedMin().ugt(CR2.getUnsignedMax());
 860       case UGE:
 861         return CR1.getUnsignedMin().uge(CR2.getUnsignedMax());
 862       case SLT:
 863         return CR1.getSignedMax().slt(CR2.getSignedMin());
 864       case SLE:
 865         return CR1.getSignedMax().sle(CR2.getSignedMin());
 866       case SGT:
 867         return CR1.getSignedMin().sgt(CR2.getSignedMax());
 868       case SGE:
 869         return CR1.getSignedMin().sge(CR2.getSignedMax());
 870       case LT:
 871         return CR1.getUnsignedMax().ult(CR2.getUnsignedMin()) &&
 872                CR1.getSignedMax().slt(CR2.getUnsignedMin());
 873       case LE:
 874         return CR1.getUnsignedMax().ule(CR2.getUnsignedMin()) &&
 875                CR1.getSignedMax().sle(CR2.getUnsignedMin());
 876       case GT:
 877         return CR1.getUnsignedMin().ugt(CR2.getUnsignedMax()) &&
 878                CR1.getSignedMin().sgt(CR2.getSignedMax());
 879       case GE:
 880         return CR1.getUnsignedMin().uge(CR2.getUnsignedMax()) &&
 881                CR1.getSignedMin().sge(CR2.getSignedMax());
 882       case SLTUGT:
 883         return CR1.getSignedMax().slt(CR2.getSignedMin()) &&
 884                CR1.getUnsignedMin().ugt(CR2.getUnsignedMax());
 885       case SLEUGE:
 886         return CR1.getSignedMax().sle(CR2.getSignedMin()) &&
 887                CR1.getUnsignedMin().uge(CR2.getUnsignedMax());
 888       case SGTULT:
 889         return CR1.getSignedMin().sgt(CR2.getSignedMax()) &&
 890                CR1.getUnsignedMax().ult(CR2.getUnsignedMin());
 891       case SGEULE:
 892         return CR1.getSignedMin().sge(CR2.getSignedMax()) &&
 893                CR1.getUnsignedMax().ule(CR2.getUnsignedMin());
 894       }
 895     }
 896
 897     void addToWorklist(Value *V, const APInt *I, ICmpInst::Predicate Pred,
 898                        VRPSolver *VRP);
 899
 900     void mergeInto(Value **I, unsigned n, Value *New, ETNode *Subtree,
 901                    VRPSolver *VRP) {
 902       assert(isCanonical(New, Subtree, VRP) && "Best choice not canonical?");
 903
 904       uint32_t W = widthOfValue(New);
 905       if (!W) return;
 906
 907       ConstantRange CR_New = rangeFromValue(New, Subtree, W);
 908       ConstantRange Merged = CR_New;
 909
 910       for (; n != 0; ++I, --n) {
 911         ConstantRange CR_Kill = rangeFromValue(*I, Subtree, W);
 912         if (CR_Kill.isFullSet()) continue;
 913         Merged = Merged.intersectWith(CR_Kill);
 914       }
 915
 916       if (Merged.isFullSet() || Merged == CR_New) return;
 917
 918       if (Merged.isSingleElement())
 919         addToWorklist(New, Merged.getSingleElement(),
 920                       ICmpInst::ICMP_EQ, VRP);
 921       else
 922         update(New, Merged, Subtree);
 923     }
 924
 925     void addInequality(Value *V1, Value *V2, ETNode *Subtree, LatticeVal LV,
 926                        VRPSolver *VRP) {
 927       assert(!isRelatedBy(V1, V2, Subtree, LV) && "Asked to do useless work.");
 928
 929       assert(isCanonical(V1, Subtree, VRP) && "Value not canonical.");
 930       assert(isCanonical(V2, Subtree, VRP) && "Value not canonical.");
 931
 932       if (LV == NE) return; // we can't represent those.
 933       // XXX: except in the case where isSingleElement and equal to either
 934       // Lower or Upper. That's probably not profitable. (Type::Int1Ty?)
 935
 936       uint32_t W = widthOfValue(V1);
 937       if (!W) return;
 938
 939       ConstantRange CR1 = rangeFromValue(V1, Subtree, W);
 940       ConstantRange CR2 = rangeFromValue(V2, Subtree, W);
 941
 942       if (!CR1.isSingleElement()) {
 943         ConstantRange NewCR1 = CR1.intersectWith(create(LV, CR2));
 944         if (NewCR1 != CR1) {
 945           if (NewCR1.isSingleElement())
 946             addToWorklist(V1, NewCR1.getSingleElement(),
 947                           ICmpInst::ICMP_EQ, VRP);
 948           else
 949             update(V1, NewCR1, Subtree);
 950         }
 951       }
 952
 953       if (!CR2.isSingleElement()) {
 954         ConstantRange NewCR2 = CR2.intersectWith(create(reversePredicate(LV),
 955                                                         CR1));
 956         if (NewCR2 != CR2) {
 957           if (NewCR2.isSingleElement())
 958             addToWorklist(V2, NewCR2.getSingleElement(),
 959                           ICmpInst::ICMP_EQ, VRP);
 960           else
 961             update(V2, NewCR2, Subtree);
 962         }
 963       }
 964     }
 965   };
 966
 967   /// UnreachableBlocks keeps tracks of blocks that are for one reason or
 968   /// another discovered to be unreachable. This is used to cull the graph when
 969   /// analyzing instructions, and to mark blocks with the "unreachable"
 970   /// terminator instruction after the function has executed.
 971   class VISIBILITY_HIDDEN UnreachableBlocks {
 972   private:
 973     std::vector<BasicBlock *> DeadBlocks;
 974
 975   public:
 976     /// mark - mark a block as dead
 977     void mark(BasicBlock *BB) {
 978       std::vector<BasicBlock *>::iterator E = DeadBlocks.end();
 979       std::vector<BasicBlock *>::iterator I =
 980         std::lower_bound(DeadBlocks.begin(), E, BB);
 981
 982       if (I == E || *I != BB) DeadBlocks.insert(I, BB);
 983     }
 984
 985     /// isDead - returns whether a block is known to be dead already
 986     bool isDead(BasicBlock *BB) {
 987       std::vector<BasicBlock *>::iterator E = DeadBlocks.end();
 988       std::vector<BasicBlock *>::iterator I =
 989         std::lower_bound(DeadBlocks.begin(), E, BB);
 990
 991       return I != E && *I == BB;
 992     }
 993
 994     /// kill - replace the dead blocks' terminator with an UnreachableInst.
 995     bool kill() {
 996       bool modified = false;
 997       for (std::vector<BasicBlock *>::iterator I = DeadBlocks.begin(),
 998            E = DeadBlocks.end(); I != E; ++I) {
 999         BasicBlock *BB = *I;
1000
1001         DOUT << "unreachable block: " << BB->getName() << "\n";
1002
1003         for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
1004              SI != SE; ++SI) {
1005           BasicBlock *Succ = *SI;
1006           Succ->removePredecessor(BB);
1007         }
1008
1009         TerminatorInst *TI = BB->getTerminator();
1010         TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
1011         TI->eraseFromParent();
1012         new UnreachableInst(BB);
1013         ++NumBlocks;
1014         modified = true;
1015       }
1016       DeadBlocks.clear();
1017       return modified;
1018     }
1019   };
1020
1021   /// VRPSolver keeps track of how changes to one variable affect other
1022   /// variables, and forwards changes along to the InequalityGraph. It
1023   /// also maintains the correct choice for "canonical" in the IG.
1024   /// @brief VRPSolver calculates inferences from a new relationship.
1025   class VISIBILITY_HIDDEN VRPSolver {
1026   private:
1027     friend class ValueRanges;
1028
1029     struct Operation {
1030       Value *LHS, *RHS;
1031       ICmpInst::Predicate Op;
1032
1033       BasicBlock *ContextBB;
1034       Instruction *ContextInst;
1035     };
1036     std::deque<Operation> WorkList;
1037
1038     InequalityGraph &IG;
1039     UnreachableBlocks &UB;
1040     ValueRanges &VR;
1041
1042     ETForest *Forest;
1043     ETNode *Top;
1044     BasicBlock *TopBB;
1045     Instruction *TopInst;
1046     bool &modified;
1047
1048     typedef InequalityGraph::Node Node;
1049
1050     /// IdomI - Determines whether one Instruction dominates another.
1051     bool IdomI(Instruction *I1, Instruction *I2) const {
1052       BasicBlock *BB1 = I1->getParent(),
1053                  *BB2 = I2->getParent();
1054       if (BB1 == BB2) {
1055         if (isa<TerminatorInst>(I1)) return false;
1056         if (isa<TerminatorInst>(I2)) return true;
1057         if (isa<PHINode>(I1) && !isa<PHINode>(I2)) return true;
1058         if (!isa<PHINode>(I1) && isa<PHINode>(I2)) return false;
1059
1060         for (BasicBlock::const_iterator I = BB1->begin(), E = BB1->end();
1061              I != E; ++I) {
1062           if (&*I == I1) return true;
1063           if (&*I == I2) return false;
1064         }
1065         assert(!"Instructions not found in parent BasicBlock?");
1066       } else {
1067         return Forest->properlyDominates(BB1, BB2);
1068       }
1069       return false;
1070     }
1071
1072     /// Returns true if V1 is a better canonical value than V2.
1073     bool compare(Value *V1, Value *V2) const {
1074       if (isa<Constant>(V1))
1075         return !isa<Constant>(V2);
1076       else if (isa<Constant>(V2))
1077         return false;
1078       else if (isa<Argument>(V1))
1079         return !isa<Argument>(V2);
1080       else if (isa<Argument>(V2))
1081         return false;
1082
1083       Instruction *I1 = dyn_cast<Instruction>(V1);
1084       Instruction *I2 = dyn_cast<Instruction>(V2);
1085
1086       if (!I1 || !I2)
1087         return V1->getNumUses() < V2->getNumUses();
1088
1089       return IdomI(I1, I2);
1090     }
1091
1092     // below - true if the Instruction is dominated by the current context
1093     // block or instruction
1094     bool below(Instruction *I) {
1095       if (TopInst)
1096         return IdomI(TopInst, I);
1097       else {
1098         ETNode *Node = Forest->getNodeForBlock(I->getParent());
1099         return Node->DominatedBy(Top);
1100       }
1101     }
1102
1103     bool makeEqual(Value *V1, Value *V2) {
1104       DOUT << "makeEqual(" << *V1 << ", " << *V2 << ")\n";
1105
1106       if (V1 == V2) return true;
1107
1108       if (isa<Constant>(V1) && isa<Constant>(V2))
1109         return false;
1110
1111       unsigned n1 = IG.getNode(V1, Top), n2 = IG.getNode(V2, Top);
1112
1113       if (n1 && n2) {
1114         if (n1 == n2) return true;
1115         if (IG.isRelatedBy(n1, n2, Top, NE)) return false;
1116       }
1117
1118       if (n1) assert(V1 == IG.node(n1)->getValue() && "Value isn't canonical.");
1119       if (n2) assert(V2 == IG.node(n2)->getValue() && "Value isn't canonical.");
1120
1121       assert(!compare(V2, V1) && "Please order parameters to makeEqual.");
1122
1123       assert(!isa<Constant>(V2) && "Tried to remove a constant.");
1124
1125       SetVector<unsigned> Remove;
1126       if (n2) Remove.insert(n2);
1127
1128       if (n1 && n2) {
1129         // Suppose we're being told that %x == %y, and %x <= %z and %y >= %z.
1130         // We can't just merge %x and %y because the relationship with %z would
1131         // be EQ and that's invalid. What we're doing is looking for any nodes
1132         // %z such that %x <= %z and %y >= %z, and vice versa.
1133
1134         Node *N1 = IG.node(n1);
1135         Node *N2 = IG.node(n2);
1136         Node::iterator end = N2->end();
1137
1138         // Find the intersection between N1 and N2 which is dominated by
1139         // Top. If we find %x where N1 <= %x <= N2 (or >=) then add %x to
1140         // Remove.
1141         for (Node::iterator I = N1->begin(), E = N1->end(); I != E; ++I) {
1142           if (!(I->LV & EQ_BIT) || !Top->DominatedBy(I->Subtree)) continue;
1143
1144           unsigned ILV_s = I->LV & (SLT_BIT|SGT_BIT);
1145           unsigned ILV_u = I->LV & (ULT_BIT|UGT_BIT);
1146           Node::iterator NI = N2->find(I->To, Top);
1147           if (NI != end) {
1148             LatticeVal NILV = reversePredicate(NI->LV);
1149             unsigned NILV_s = NILV & (SLT_BIT|SGT_BIT);
1150             unsigned NILV_u = NILV & (ULT_BIT|UGT_BIT);
1151
1152             if ((ILV_s != (SLT_BIT|SGT_BIT) && ILV_s == NILV_s) ||
1153                 (ILV_u != (ULT_BIT|UGT_BIT) && ILV_u == NILV_u))
1154               Remove.insert(I->To);
1155           }
1156         }
1157
1158         // See if one of the nodes about to be removed is actually a better
1159         // canonical choice than n1.
1160         unsigned orig_n1 = n1;
1161         SetVector<unsigned>::iterator DontRemove = Remove.end();
1162         for (SetVector<unsigned>::iterator I = Remove.begin()+1 /* skip n2 */,
1163              E = Remove.end(); I != E; ++I) {
1164           unsigned n = *I;
1165           Value *V = IG.node(n)->getValue();
1166           if (compare(V, V1)) {
1167             V1 = V;
1168             n1 = n;
1169             DontRemove = I;
1170           }
1171         }
1172         if (DontRemove != Remove.end()) {
1173           unsigned n = *DontRemove;
1174           Remove.remove(n);
1175           Remove.insert(orig_n1);
1176         }
1177       }
1178
1179       // We'd like to allow makeEqual on two values to perform a simple
1180       // substitution without every creating nodes in the IG whenever possible.
1181       //
1182       // The first iteration through this loop operates on V2 before going
1183       // through the Remove list and operating on those too. If all of the
1184       // iterations performed simple replacements then we exit early.
1185       bool mergeIGNode = false;
1186       unsigned i = 0;
1187       for (Value *R = V2; i == 0 || i < Remove.size(); ++i) {
1188         if (i) R = IG.node(Remove[i])->getValue(); // skip n2.
1189
1190         // Try to replace the whole instruction. If we can, we're done.
1191         Instruction *I2 = dyn_cast<Instruction>(R);
1192         if (I2 && below(I2)) {
1193           std::vector<Instruction *> ToNotify;
1194           for (Value::use_iterator UI = R->use_begin(), UE = R->use_end();
1195                UI != UE;) {
1196             Use &TheUse = UI.getUse();
1197             ++UI;
1198             if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser()))
1199               ToNotify.push_back(I);
1200           }
1201
1202           DOUT << "Simply removing " << *I2
1203                << ", replacing with " << *V1 << "\n";
1204           I2->replaceAllUsesWith(V1);
1205           // leave it dead; it'll get erased later.
1206           ++NumInstruction;
1207           modified = true;
1208
1209           for (std::vector<Instruction *>::iterator II = ToNotify.begin(),
1210                IE = ToNotify.end(); II != IE; ++II) {
1211             opsToDef(*II);
1212           }
1213
1214           continue;
1215         }
1216
1217         // Otherwise, replace all dominated uses.
1218         for (Value::use_iterator UI = R->use_begin(), UE = R->use_end();
1219              UI != UE;) {
1220           Use &TheUse = UI.getUse();
1221           ++UI;
1222           if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
1223             if (below(I)) {
1224               TheUse.set(V1);
1225               modified = true;
1226               ++NumVarsReplaced;
1227               opsToDef(I);
1228             }
1229           }
1230         }
1231
1232         // If that killed the instruction, stop here.
1233         if (I2 && isInstructionTriviallyDead(I2)) {
1234           DOUT << "Killed all uses of " << *I2
1235                << ", replacing with " << *V1 << "\n";
1236           continue;
1237         }
1238
1239         // If we make it to here, then we will need to create a node for N1.
1240         // Otherwise, we can skip out early!
1241         mergeIGNode = true;
1242       }
1243
1244       if (!isa<Constant>(V1)) {
1245         if (Remove.empty()) {
1246           VR.mergeInto(&V2, 1, V1, Top, this);
1247         } else {
1248           std::vector<Value*> RemoveVals;
1249           RemoveVals.reserve(Remove.size());
1250
1251           for (SetVector<unsigned>::iterator I = Remove.begin(),
1252                E = Remove.end(); I != E; ++I) {
1253             Value *V = IG.node(*I)->getValue();
1254             if (!V->use_empty())
1255               RemoveVals.push_back(V);
1256           }
1257           VR.mergeInto(&RemoveVals[0], RemoveVals.size(), V1, Top, this);
1258         }
1259       }
1260
1261       if (mergeIGNode) {
1262         // Create N1.
1263         if (!n1) n1 = IG.newNode(V1);
1264
1265         // Migrate relationships from removed nodes to N1.
1266         Node *N1 = IG.node(n1);
1267         for (SetVector<unsigned>::iterator I = Remove.begin(), E = Remove.end();
1268              I != E; ++I) {
1269           unsigned n = *I;
1270           Node *N = IG.node(n);
1271           for (Node::iterator NI = N->begin(), NE = N->end(); NI != NE; ++NI) {
1272             if (NI->Subtree->DominatedBy(Top)) {
1273               if (NI->To == n1) {
1274                 assert((NI->LV & EQ_BIT) && "Node inequal to itself.");
1275                 continue;
1276               }
1277               if (Remove.count(NI->To))
1278                 continue;
1279
1280               IG.node(NI->To)->update(n1, reversePredicate(NI->LV), Top);
1281               N1->update(NI->To, NI->LV, Top);
1282             }
1283           }
1284         }
1285
1286         // Point V2 (and all items in Remove) to N1.
1287         if (!n2)
1288           IG.addEquality(n1, V2, Top);
1289         else {
1290           for (SetVector<unsigned>::iterator I = Remove.begin(),
1291                E = Remove.end(); I != E; ++I) {
1292             IG.addEquality(n1, IG.node(*I)->getValue(), Top);
1293           }
1294         }
1295
1296         // If !Remove.empty() then V2 = Remove[0]->getValue().
1297         // Even when Remove is empty, we still want to process V2.
1298         i = 0;
1299         for (Value *R = V2; i == 0 || i < Remove.size(); ++i) {
1300           if (i) R = IG.node(Remove[i])->getValue(); // skip n2.
1301
1302           if (Instruction *I2 = dyn_cast<Instruction>(R)) {
1303             if (below(I2) ||
1304                 Top->DominatedBy(Forest->getNodeForBlock(I2->getParent())))
1305             defToOps(I2);
1306           }
1307           for (Value::use_iterator UI = V2->use_begin(), UE = V2->use_end();
1308                UI != UE;) {
1309             Use &TheUse = UI.getUse();
1310             ++UI;
1311             if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
1312               if (below(I) ||
1313                   Top->DominatedBy(Forest->getNodeForBlock(I->getParent())))
1314                 opsToDef(I);
1315             }
1316           }
1317         }
1318       }
1319
1320       // re-opsToDef all dominated users of V1.
1321       if (Instruction *I = dyn_cast<Instruction>(V1)) {
1322         for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
1323              UI != UE;) {
1324           Use &TheUse = UI.getUse();
1325           ++UI;
1326           Value *V = TheUse.getUser();
1327           if (!V->use_empty()) {
1328             if (Instruction *Inst = dyn_cast<Instruction>(V)) {
1329               if (below(Inst) ||
1330                   Top->DominatedBy(Forest->getNodeForBlock(Inst->getParent())))
1331                 opsToDef(Inst);
1332             }
1333           }
1334         }
1335       }
1336
1337       return true;
1338     }
1339
1340     /// cmpInstToLattice - converts an CmpInst::Predicate to lattice value
1341     /// Requires that the lattice value be valid; does not accept ICMP_EQ.
1342     static LatticeVal cmpInstToLattice(ICmpInst::Predicate Pred) {
1343       switch (Pred) {
1344         case ICmpInst::ICMP_EQ:
1345           assert(!"No matching lattice value.");
1346           return static_cast<LatticeVal>(EQ_BIT);
1347         default:
1348           assert(!"Invalid 'icmp' predicate.");
1349         case ICmpInst::ICMP_NE:
1350           return NE;
1351         case ICmpInst::ICMP_UGT:
1352           return UGT;
1353         case ICmpInst::ICMP_UGE:
1354           return UGE;
1355         case ICmpInst::ICMP_ULT:
1356           return ULT;
1357         case ICmpInst::ICMP_ULE:
1358           return ULE;
1359         case ICmpInst::ICMP_SGT:
1360           return SGT;
1361         case ICmpInst::ICMP_SGE:
1362           return SGE;
1363         case ICmpInst::ICMP_SLT:
1364           return SLT;
1365         case ICmpInst::ICMP_SLE:
1366           return SLE;
1367       }
1368     }
1369
1370   public:
1371     VRPSolver(InequalityGraph &IG, UnreachableBlocks &UB, ValueRanges &VR,
1372               ETForest *Forest, bool &modified, BasicBlock *TopBB)
1373       : IG(IG),
1374         UB(UB),
1375         VR(VR),
1376         Forest(Forest),
1377         Top(Forest->getNodeForBlock(TopBB)),
1378         TopBB(TopBB),
1379         TopInst(NULL),
1380         modified(modified) {}
1381
1382     VRPSolver(InequalityGraph &IG, UnreachableBlocks &UB, ValueRanges &VR,
1383               ETForest *Forest, bool &modified, Instruction *TopInst)
1384       : IG(IG),
1385         UB(UB),
1386         VR(VR),
1387         Forest(Forest),
1388         TopInst(TopInst),
1389         modified(modified)
1390     {
1391       TopBB = TopInst->getParent();
1392       Top = Forest->getNodeForBlock(TopBB);
1393     }
1394
1395     bool isRelatedBy(Value *V1, Value *V2, ICmpInst::Predicate Pred) const {
1396       if (Constant *C1 = dyn_cast<Constant>(V1))
1397         if (Constant *C2 = dyn_cast<Constant>(V2))
1398           return ConstantExpr::getCompare(Pred, C1, C2) ==
1399                  ConstantInt::getTrue();
1400
1401       if (unsigned n1 = IG.getNode(V1, Top))
1402         if (unsigned n2 = IG.getNode(V2, Top)) {
1403           if (n1 == n2) return Pred == ICmpInst::ICMP_EQ ||
1404                                Pred == ICmpInst::ICMP_ULE ||
1405                                Pred == ICmpInst::ICMP_UGE ||
1406                                Pred == ICmpInst::ICMP_SLE ||
1407                                Pred == ICmpInst::ICMP_SGE;
1408           if (Pred == ICmpInst::ICMP_EQ) return false;
1409           if (IG.isRelatedBy(n1, n2, Top, cmpInstToLattice(Pred))) return true;
1410         }
1411
1412       if (Pred == ICmpInst::ICMP_EQ) return V1 == V2;
1413       return VR.isRelatedBy(V1, V2, Top, cmpInstToLattice(Pred));
1414     }
1415
1416     /// add - adds a new property to the work queue
1417     void add(Value *V1, Value *V2, ICmpInst::Predicate Pred,
1418              Instruction *I = NULL) {
1419       DOUT << "adding " << *V1 << " " << Pred << " " << *V2;
1420       if (I) DOUT << " context: " << *I;
1421       else DOUT << " default context";
1422       DOUT << "\n";
1423
1424       WorkList.push_back(Operation());
1425       Operation &O = WorkList.back();
1426       O.LHS = V1, O.RHS = V2, O.Op = Pred, O.ContextInst = I;
1427       O.ContextBB = I ? I->getParent() : TopBB;
1428     }
1429
1430     /// defToOps - Given an instruction definition that we've learned something
1431     /// new about, find any new relationships between its operands.
1432     void defToOps(Instruction *I) {
1433       Instruction *NewContext = below(I) ? I : TopInst;
1434       Value *Canonical = IG.canonicalize(I, Top);
1435
1436       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
1437         const Type *Ty = BO->getType();
1438         assert(!Ty->isFPOrFPVector() && "Float in work queue!");
1439
1440         Value *Op0 = IG.canonicalize(BO->getOperand(0), Top);
1441         Value *Op1 = IG.canonicalize(BO->getOperand(1), Top);
1442
1443         // TODO: "and i32 -1, %x" EQ %y then %x EQ %y.
1444
1445         switch (BO->getOpcode()) {
1446           case Instruction::And: {
1447             // "and i32 %a, %b" EQ -1 then %a EQ -1 and %b EQ -1
1448             ConstantInt *CI = ConstantInt::getAllOnesValue(Ty);
1449             if (Canonical == CI) {
1450               add(CI, Op0, ICmpInst::ICMP_EQ, NewContext);
1451               add(CI, Op1, ICmpInst::ICMP_EQ, NewContext);
1452             }
1453           } break;
1454           case Instruction::Or: {
1455             // "or i32 %a, %b" EQ 0 then %a EQ 0 and %b EQ 0
1456             Constant *Zero = Constant::getNullValue(Ty);
1457             if (Canonical == Zero) {
1458               add(Zero, Op0, ICmpInst::ICMP_EQ, NewContext);
1459               add(Zero, Op1, ICmpInst::ICMP_EQ, NewContext);
1460             }
1461           } break;
1462           case Instruction::Xor: {
1463             // "xor i32 %c, %a" EQ %b then %a EQ %c ^ %b
1464             // "xor i32 %c, %a" EQ %c then %a EQ 0
1465             // "xor i32 %c, %a" NE %c then %a NE 0
1466             // Repeat the above, with order of operands reversed.
1467             Value *LHS = Op0;
1468             Value *RHS = Op1;
1469             if (!isa<Constant>(LHS)) std::swap(LHS, RHS);
1470
1471             if (ConstantInt *CI = dyn_cast<ConstantInt>(Canonical)) {
1472               if (ConstantInt *Arg = dyn_cast<ConstantInt>(LHS)) {
1473                 add(RHS, ConstantInt::get(CI->getValue() ^ Arg->getValue()),
1474                     ICmpInst::ICMP_EQ, NewContext);
1475               }
1476             }
1477             if (Canonical == LHS) {
1478               if (isa<ConstantInt>(Canonical))
1479                 add(RHS, Constant::getNullValue(Ty), ICmpInst::ICMP_EQ,
1480                     NewContext);
1481             } else if (isRelatedBy(LHS, Canonical, ICmpInst::ICMP_NE)) {
1482               add(RHS, Constant::getNullValue(Ty), ICmpInst::ICMP_NE,
1483                   NewContext);
1484             }
1485           } break;
1486           default:
1487             break;
1488         }
1489       } else if (ICmpInst *IC = dyn_cast<ICmpInst>(I)) {
1490         // "icmp ult i32 %a, %y" EQ true then %a u< y
1491         // etc.
1492
1493         if (Canonical == ConstantInt::getTrue()) {
1494           add(IC->getOperand(0), IC->getOperand(1), IC->getPredicate(),
1495               NewContext);
1496         } else if (Canonical == ConstantInt::getFalse()) {
1497           add(IC->getOperand(0), IC->getOperand(1),
1498               ICmpInst::getInversePredicate(IC->getPredicate()), NewContext);
1499         }
1500       } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
1501         if (I->getType()->isFPOrFPVector()) return;
1502
1503         // Given: "%a = select i1 %x, i32 %b, i32 %c"
1504         // %a EQ %b and %b NE %c then %x EQ true
1505         // %a EQ %c and %b NE %c then %x EQ false
1506
1507         Value *True  = SI->getTrueValue();
1508         Value *False = SI->getFalseValue();
1509         if (isRelatedBy(True, False, ICmpInst::ICMP_NE)) {
1510           if (Canonical == IG.canonicalize(True, Top) ||
1511               isRelatedBy(Canonical, False, ICmpInst::ICMP_NE))
1512             add(SI->getCondition(), ConstantInt::getTrue(),
1513                 ICmpInst::ICMP_EQ, NewContext);
1514           else if (Canonical == IG.canonicalize(False, Top) ||
1515                    isRelatedBy(Canonical, True, ICmpInst::ICMP_NE))
1516             add(SI->getCondition(), ConstantInt::getFalse(),
1517                 ICmpInst::ICMP_EQ, NewContext);
1518         }
1519       }
1520       // TODO: CastInst "%a = cast ... %b" where %a is EQ or NE a constant.
1521     }
1522
1523     /// opsToDef - A new relationship was discovered involving one of this
1524     /// instruction's operands. Find any new relationship involving the
1525     /// definition.
1526     void opsToDef(Instruction *I) {
1527       Instruction *NewContext = below(I) ? I : TopInst;
1528
1529       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
1530         Value *Op0 = IG.canonicalize(BO->getOperand(0), Top);
1531         Value *Op1 = IG.canonicalize(BO->getOperand(1), Top);
1532
1533         if (ConstantInt *CI0 = dyn_cast<ConstantInt>(Op0))
1534           if (ConstantInt *CI1 = dyn_cast<ConstantInt>(Op1)) {
1535             add(BO, ConstantExpr::get(BO->getOpcode(), CI0, CI1),
1536                 ICmpInst::ICMP_EQ, NewContext);
1537             return;
1538           }
1539
1540         // "%y = and i1 true, %x" then %x EQ %y
1541         // "%y = or i1 false, %x" then %x EQ %y
1542         // "%x = add i32 %y, 0" then %x EQ %y
1543         // "%x = mul i32 %y, 0" then %x EQ 0
1544
1545         Instruction::BinaryOps Opcode = BO->getOpcode();
1546
1547         switch (Opcode) {
1548           default: break;
1549           case Instruction::Sub:
1550           case Instruction::Add:
1551           case Instruction::Or: {
1552             Constant *Zero = Constant::getNullValue(BO->getType());
1553             if (Op0 == Zero) {
1554               add(BO, Op1, ICmpInst::ICMP_EQ, NewContext);
1555               return;
1556             } else if (Op1 == Zero) {
1557               add(BO, Op0, ICmpInst::ICMP_EQ, NewContext);
1558               return;
1559             }
1560           } break;
1561           case Instruction::And: {
1562             Constant *AllOnes = ConstantInt::getAllOnesValue(BO->getType());
1563             if (Op0 == AllOnes) {
1564               add(BO, Op1, ICmpInst::ICMP_EQ, NewContext);
1565               return;
1566             } else if (Op1 == AllOnes) {
1567               add(BO, Op0, ICmpInst::ICMP_EQ, NewContext);
1568               return;
1569             }
1570           } break;
1571           case Instruction::Mul: {
1572             Constant *Zero = Constant::getNullValue(BO->getType());
1573             if (Op0 == Zero) {
1574               add(BO, Zero, ICmpInst::ICMP_EQ, NewContext);
1575               return;
1576             } else if (Op1 == Zero) {
1577               add(BO, Zero, ICmpInst::ICMP_EQ, NewContext);
1578               return;
1579             }
1580           } break;
1581         }
1582
1583         // "%x = add i32 %y, %z" and %x EQ %y then %z EQ 0
1584         // "%x = mul i32 %y, %z" and %x EQ %y then %z EQ 1
1585         // 1. Repeat all of the above, with order of operands reversed.
1586         // "%x = udiv i32 %y, %z" and %x EQ %y then %z EQ 1
1587
1588         const Type *Ty = BO->getType();
1589         assert(!Ty->isFPOrFPVector() && "Float in work queue!");
1590
1591         Value *Known = Op0, *Unknown = Op1;
1592         if (Known != BO) std::swap(Known, Unknown);
1593         if (Known == BO) {
1594           switch (Opcode) {
1595             default: break;
1596             case Instruction::Xor:
1597             case Instruction::Add:
1598             case Instruction::Sub:
1599               add(Unknown, Constant::getNullValue(Ty), ICmpInst::ICMP_EQ,
1600                   NewContext);
1601               break;
1602             case Instruction::UDiv:
1603             case Instruction::SDiv:
1604               if (Unknown == Op0) break; // otherwise, fallthrough
1605             case Instruction::Mul:
1606               if (isa<ConstantInt>(Unknown)) {
1607                 Constant *One = ConstantInt::get(Ty, 1);
1608                 add(Unknown, One, ICmpInst::ICMP_EQ, NewContext);
1609               }
1610               break;
1611           }
1612         }
1613
1614         // TODO: "%a = add i32 %b, 1" and %b > %z then %a >= %z.
1615
1616       } else if (ICmpInst *IC = dyn_cast<ICmpInst>(I)) {
1617         // "%a = icmp ult i32 %b, %c" and %b u<  %c then %a EQ true
1618         // "%a = icmp ult i32 %b, %c" and %b u>= %c then %a EQ false
1619         // etc.
1620
1621         Value *Op0 = IG.canonicalize(IC->getOperand(0), Top);
1622         Value *Op1 = IG.canonicalize(IC->getOperand(1), Top);
1623
1624         ICmpInst::Predicate Pred = IC->getPredicate();
1625         if (isRelatedBy(Op0, Op1, Pred)) {
1626           add(IC, ConstantInt::getTrue(), ICmpInst::ICMP_EQ, NewContext);
1627         } else if (isRelatedBy(Op0, Op1, ICmpInst::getInversePredicate(Pred))) {
1628           add(IC, ConstantInt::getFalse(), ICmpInst::ICMP_EQ, NewContext);
1629         }
1630
1631       } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
1632         // Given: "%a = select i1 %x, i32 %b, i32 %c"
1633         // %x EQ true  then %a EQ %b
1634         // %x EQ false then %a EQ %c
1635         // %b EQ %c then %a EQ %b
1636
1637         Value *Canonical = IG.canonicalize(SI->getCondition(), Top);
1638         if (Canonical == ConstantInt::getTrue()) {
1639           add(SI, SI->getTrueValue(), ICmpInst::ICMP_EQ, NewContext);
1640         } else if (Canonical == ConstantInt::getFalse()) {
1641           add(SI, SI->getFalseValue(), ICmpInst::ICMP_EQ, NewContext);
1642         } else if (IG.canonicalize(SI->getTrueValue(), Top) ==
1643                    IG.canonicalize(SI->getFalseValue(), Top)) {
1644           add(SI, SI->getTrueValue(), ICmpInst::ICMP_EQ, NewContext);
1645         }
1646       } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
1647         const Type *Ty = CI->getDestTy();
1648         if (Ty->isFPOrFPVector()) return;
1649
1650         if (Constant *C = dyn_cast<Constant>(
1651                 IG.canonicalize(CI->getOperand(0), Top))) {
1652           add(CI, ConstantExpr::getCast(CI->getOpcode(), C, Ty),
1653               ICmpInst::ICMP_EQ, NewContext);
1654         }
1655
1656         // TODO: "%a = cast ... %b" where %b is NE/LT/GT a constant.
1657       }
1658     }
1659
1660     /// solve - process the work queue
1661     /// Return false if a logical contradiction occurs.
1662     void solve() {
1663       //DOUT << "WorkList entry, size: " << WorkList.size() << "\n";
1664       while (!WorkList.empty()) {
1665         //DOUT << "WorkList size: " << WorkList.size() << "\n";
1666
1667         Operation &O = WorkList.front();
1668         TopInst = O.ContextInst;
1669         TopBB = O.ContextBB;
1670         Top = Forest->getNodeForBlock(TopBB);
1671
1672         O.LHS = IG.canonicalize(O.LHS, Top);
1673         O.RHS = IG.canonicalize(O.RHS, Top);
1674
1675         assert(O.LHS == IG.canonicalize(O.LHS, Top) && "Canonicalize isn't.");
1676         assert(O.RHS == IG.canonicalize(O.RHS, Top) && "Canonicalize isn't.");
1677
1678         DOUT << "solving " << *O.LHS << " " << O.Op << " " << *O.RHS;
1679         if (O.ContextInst) DOUT << " context inst: " << *O.ContextInst;
1680         else DOUT << " context block: " << O.ContextBB->getName();
1681         DOUT << "\n";
1682
1683         DEBUG(IG.dump());
1684
1685         // If they're both Constant, skip it. Check for contradiction and mark
1686         // the BB as unreachable if so.
1687         if (Constant *CI_L = dyn_cast<Constant>(O.LHS)) {
1688           if (Constant *CI_R = dyn_cast<Constant>(O.RHS)) {
1689             if (ConstantExpr::getCompare(O.Op, CI_L, CI_R) ==
1690                 ConstantInt::getFalse())
1691               UB.mark(TopBB);
1692
1693             WorkList.pop_front();
1694             continue;
1695           }
1696         }
1697
1698         if (compare(O.LHS, O.RHS)) {
1699           std::swap(O.LHS, O.RHS);
1700           O.Op = ICmpInst::getSwappedPredicate(O.Op);
1701         }
1702
1703         if (O.Op == ICmpInst::ICMP_EQ) {
1704           if (!makeEqual(O.RHS, O.LHS))
1705             UB.mark(TopBB);
1706         } else {
1707           LatticeVal LV = cmpInstToLattice(O.Op);
1708
1709           if ((LV & EQ_BIT) &&
1710               isRelatedBy(O.LHS, O.RHS, ICmpInst::getSwappedPredicate(O.Op))) {
1711             if (!makeEqual(O.RHS, O.LHS))
1712               UB.mark(TopBB);
1713           } else {
1714             if (isRelatedBy(O.LHS, O.RHS, ICmpInst::getInversePredicate(O.Op))){
1715               UB.mark(TopBB);
1716               WorkList.pop_front();
1717               continue;
1718             }
1719
1720             unsigned n1 = IG.getNode(O.LHS, Top);
1721             unsigned n2 = IG.getNode(O.RHS, Top);
1722
1723             if (n1 && n1 == n2) {
1724               if (O.Op != ICmpInst::ICMP_UGE && O.Op != ICmpInst::ICMP_ULE &&
1725                   O.Op != ICmpInst::ICMP_SGE && O.Op != ICmpInst::ICMP_SLE)
1726                 UB.mark(TopBB);
1727
1728               WorkList.pop_front();
1729               continue;
1730             }
1731
1732             if (VR.isRelatedBy(O.LHS, O.RHS, Top, LV) ||
1733                 (n1 && n2 && IG.isRelatedBy(n1, n2, Top, LV))) {
1734               WorkList.pop_front();
1735               continue;
1736             }
1737
1738             VR.addInequality(O.LHS, O.RHS, Top, LV, this);
1739             if ((!isa<ConstantInt>(O.RHS) && !isa<ConstantInt>(O.LHS)) ||
1740                 LV == NE) {
1741               if (!n1) n1 = IG.newNode(O.LHS);
1742               if (!n2) n2 = IG.newNode(O.RHS);
1743               IG.addInequality(n1, n2, Top, LV);
1744             }
1745
1746             if (Instruction *I1 = dyn_cast<Instruction>(O.LHS)) {
1747               if (below(I1) ||
1748                   Top->DominatedBy(Forest->getNodeForBlock(I1->getParent())))
1749                 defToOps(I1);
1750             }
1751             if (isa<Instruction>(O.LHS) || isa<Argument>(O.LHS)) {
1752               for (Value::use_iterator UI = O.LHS->use_begin(),
1753                    UE = O.LHS->use_end(); UI != UE;) {
1754                 Use &TheUse = UI.getUse();
1755                 ++UI;
1756                 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
1757                   if (below(I) ||
1758                       Top->DominatedBy(Forest->getNodeForBlock(I->getParent())))
1759                     opsToDef(I);
1760                 }
1761               }
1762             }
1763             if (Instruction *I2 = dyn_cast<Instruction>(O.RHS)) {
1764               if (below(I2) ||
1765                   Top->DominatedBy(Forest->getNodeForBlock(I2->getParent())))
1766               defToOps(I2);
1767             }
1768             if (isa<Instruction>(O.RHS) || isa<Argument>(O.RHS)) {
1769               for (Value::use_iterator UI = O.RHS->use_begin(),
1770                    UE = O.RHS->use_end(); UI != UE;) {
1771                 Use &TheUse = UI.getUse();
1772                 ++UI;
1773                 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
1774                   if (below(I) ||
1775                       Top->DominatedBy(Forest->getNodeForBlock(I->getParent())))
1776
1777                     opsToDef(I);
1778                 }
1779               }
1780             }
1781           }
1782         }
1783         WorkList.pop_front();
1784       }
1785     }
1786   };
1787
1788   void ValueRanges::addToWorklist(Value *V, const APInt *I,
1789                                   ICmpInst::Predicate Pred, VRPSolver *VRP) {
1790     VRP->add(V, ConstantInt::get(*I), Pred, VRP->TopInst);
1791   }
1792
1793 #ifndef NDEBUG
1794   bool ValueRanges::isCanonical(Value *V, ETNode *Subtree, VRPSolver *VRP) {
1795     return V == VRP->IG.canonicalize(V, Subtree);
1796   }
1797 #endif
1798
1799   /// PredicateSimplifier - This class is a simplifier that replaces
1800   /// one equivalent variable with another. It also tracks what
1801   /// can't be equal and will solve setcc instructions when possible.
1802   /// @brief Root of the predicate simplifier optimization.
1803   class VISIBILITY_HIDDEN PredicateSimplifier : public FunctionPass {
1804     DominatorTree *DT;
1805     ETForest *Forest;
1806     bool modified;
1807     InequalityGraph *IG;
1808     UnreachableBlocks UB;
1809     ValueRanges *VR;
1810
1811     std::vector<DominatorTree::Node *> WorkList;
1812
1813   public:
1814     bool runOnFunction(Function &F);
1815
1816     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1817       AU.addRequiredID(BreakCriticalEdgesID);
1818       AU.addRequired<DominatorTree>();
1819       AU.addRequired<ETForest>();
1820     }
1821
1822   private:
1823     /// Forwards - Adds new properties into PropertySet and uses them to
1824     /// simplify instructions. Because new properties sometimes apply to
1825     /// a transition from one BasicBlock to another, this will use the
1826     /// PredicateSimplifier::proceedToSuccessor(s) interface to enter the
1827     /// basic block with the new PropertySet.
1828     /// @brief Performs abstract execution of the program.
1829     class VISIBILITY_HIDDEN Forwards : public InstVisitor<Forwards> {
1830       friend class InstVisitor<Forwards>;
1831       PredicateSimplifier *PS;
1832       DominatorTree::Node *DTNode;
1833
1834     public:
1835       InequalityGraph &IG;
1836       UnreachableBlocks &UB;
1837       ValueRanges &VR;
1838
1839       Forwards(PredicateSimplifier *PS, DominatorTree::Node *DTNode)
1840         : PS(PS), DTNode(DTNode), IG(*PS->IG), UB(PS->UB), VR(*PS->VR) {}
1841
1842       void visitTerminatorInst(TerminatorInst &TI);
1843       void visitBranchInst(BranchInst &BI);
1844       void visitSwitchInst(SwitchInst &SI);
1845
1846       void visitAllocaInst(AllocaInst &AI);
1847       void visitLoadInst(LoadInst &LI);
1848       void visitStoreInst(StoreInst &SI);
1849
1850       void visitSExtInst(SExtInst &SI);
1851       void visitZExtInst(ZExtInst &ZI);
1852
1853       void visitBinaryOperator(BinaryOperator &BO);
1854       void visitICmpInst(ICmpInst &IC);
1855     };
1856
1857     // Used by terminator instructions to proceed from the current basic
1858     // block to the next. Verifies that "current" dominates "next",
1859     // then calls visitBasicBlock.
1860     void proceedToSuccessors(DominatorTree::Node *Current) {
1861       for (DominatorTree::Node::iterator I = Current->begin(),
1862            E = Current->end(); I != E; ++I) {
1863         WorkList.push_back(*I);
1864       }
1865     }
1866
1867     void proceedToSuccessor(DominatorTree::Node *Next) {
1868       WorkList.push_back(Next);
1869     }
1870
1871     // Visits each instruction in the basic block.
1872     void visitBasicBlock(DominatorTree::Node *Node) {
1873       BasicBlock *BB = Node->getBlock();
1874       ETNode *ET = Forest->getNodeForBlock(BB);
1875       DOUT << "Entering Basic Block: " << BB->getName()
1876            << " (" << ET->getDFSNumIn() << ")\n";
1877       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
1878         visitInstruction(I++, Node, ET);
1879       }
1880     }
1881
1882     // Tries to simplify each Instruction and add new properties to
1883     // the PropertySet.
1884     void visitInstruction(Instruction *I, DominatorTree::Node *DT, ETNode *ET) {
1885       DOUT << "Considering instruction " << *I << "\n";
1886       DEBUG(IG->dump());
1887
1888       // Sometimes instructions are killed in earlier analysis.
1889       if (isInstructionTriviallyDead(I)) {
1890         ++NumSimple;
1891         modified = true;
1892         IG->remove(I);
1893         I->eraseFromParent();
1894         return;
1895       }
1896
1897 #ifndef NDEBUG
1898       // Try to replace the whole instruction.
1899       Value *V = IG->canonicalize(I, ET);
1900       assert(V == I && "Late instruction canonicalization.");
1901       if (V != I) {
1902         modified = true;
1903         ++NumInstruction;
1904         DOUT << "Removing " << *I << ", replacing with " << *V << "\n";
1905         IG->remove(I);
1906         I->replaceAllUsesWith(V);
1907         I->eraseFromParent();
1908         return;
1909       }
1910
1911       // Try to substitute operands.
1912       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
1913         Value *Oper = I->getOperand(i);
1914         Value *V = IG->canonicalize(Oper, ET);
1915         assert(V == Oper && "Late operand canonicalization.");
1916         if (V != Oper) {
1917           modified = true;
1918           ++NumVarsReplaced;
1919           DOUT << "Resolving " << *I;
1920           I->setOperand(i, V);
1921           DOUT << " into " << *I;
1922         }
1923       }
1924 #endif
1925
1926       std::string name = I->getParent()->getName();
1927       DOUT << "push (%" << name << ")\n";
1928       Forwards visit(this, DT);
1929       visit.visit(*I);
1930       DOUT << "pop (%" << name << ")\n";
1931     }
1932   };
1933
1934   bool PredicateSimplifier::runOnFunction(Function &F) {
1935     DT = &getAnalysis<DominatorTree>();
1936     Forest = &getAnalysis<ETForest>();
1937
1938     Forest->updateDFSNumbers(); // XXX: should only act when numbers are out of date
1939
1940     DOUT << "Entering Function: " << F.getName() << "\n";
1941
1942     modified = false;
1943     BasicBlock *RootBlock = &F.getEntryBlock();
1944     IG = new InequalityGraph(Forest->getNodeForBlock(RootBlock));
1945     VR = new ValueRanges();
1946     WorkList.push_back(DT->getRootNode());
1947
1948     do {
1949       DominatorTree::Node *DTNode = WorkList.back();
1950       WorkList.pop_back();
1951       if (!UB.isDead(DTNode->getBlock())) visitBasicBlock(DTNode);
1952     } while (!WorkList.empty());
1953
1954     delete VR;
1955     delete IG;
1956
1957     modified |= UB.kill();
1958
1959     return modified;
1960   }
1961
1962   void PredicateSimplifier::Forwards::visitTerminatorInst(TerminatorInst &TI) {
1963     PS->proceedToSuccessors(DTNode);
1964   }
1965
1966   void PredicateSimplifier::Forwards::visitBranchInst(BranchInst &BI) {
1967     if (BI.isUnconditional()) {
1968       PS->proceedToSuccessors(DTNode);
1969       return;
1970     }
1971
1972     Value *Condition = BI.getCondition();
1973     BasicBlock *TrueDest  = BI.getSuccessor(0);
1974     BasicBlock *FalseDest = BI.getSuccessor(1);
1975
1976     if (isa<Constant>(Condition) || TrueDest == FalseDest) {
1977       PS->proceedToSuccessors(DTNode);
1978       return;
1979     }
1980
1981     for (DominatorTree::Node::iterator I = DTNode->begin(), E = DTNode->end();
1982          I != E; ++I) {
1983       BasicBlock *Dest = (*I)->getBlock();
1984       DOUT << "Branch thinking about %" << Dest->getName()
1985            << "(" << PS->Forest->getNodeForBlock(Dest)->getDFSNumIn() << ")\n";
1986
1987       if (Dest == TrueDest) {
1988         DOUT << "(" << DTNode->getBlock()->getName() << ") true set:\n";
1989         VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, Dest);
1990         VRP.add(ConstantInt::getTrue(), Condition, ICmpInst::ICMP_EQ);
1991         VRP.solve();
1992         DEBUG(IG.dump());
1993       } else if (Dest == FalseDest) {
1994         DOUT << "(" << DTNode->getBlock()->getName() << ") false set:\n";
1995         VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, Dest);
1996         VRP.add(ConstantInt::getFalse(), Condition, ICmpInst::ICMP_EQ);
1997         VRP.solve();
1998         DEBUG(IG.dump());
1999       }
2000
2001       PS->proceedToSuccessor(*I);
2002     }
2003   }
2004
2005   void PredicateSimplifier::Forwards::visitSwitchInst(SwitchInst &SI) {
2006     Value *Condition = SI.getCondition();
2007
2008     // Set the EQProperty in each of the cases BBs, and the NEProperties
2009     // in the default BB.
2010
2011     for (DominatorTree::Node::iterator I = DTNode->begin(), E = DTNode->end();
2012          I != E; ++I) {
2013       BasicBlock *BB = (*I)->getBlock();
2014       DOUT << "Switch thinking about BB %" << BB->getName()
2015            << "(" << PS->Forest->getNodeForBlock(BB)->getDFSNumIn() << ")\n";
2016
2017       VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, BB);
2018       if (BB == SI.getDefaultDest()) {
2019         for (unsigned i = 1, e = SI.getNumCases(); i < e; ++i)
2020           if (SI.getSuccessor(i) != BB)
2021             VRP.add(Condition, SI.getCaseValue(i), ICmpInst::ICMP_NE);
2022         VRP.solve();
2023       } else if (ConstantInt *CI = SI.findCaseDest(BB)) {
2024         VRP.add(Condition, CI, ICmpInst::ICMP_EQ);
2025         VRP.solve();
2026       }
2027       PS->proceedToSuccessor(*I);
2028     }
2029   }
2030
2031   void PredicateSimplifier::Forwards::visitAllocaInst(AllocaInst &AI) {
2032     VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, &AI);
2033     VRP.add(Constant::getNullValue(AI.getType()), &AI, ICmpInst::ICMP_NE);
2034     VRP.solve();
2035   }
2036
2037   void PredicateSimplifier::Forwards::visitLoadInst(LoadInst &LI) {
2038     Value *Ptr = LI.getPointerOperand();
2039     // avoid "load uint* null" -> null NE null.
2040     if (isa<Constant>(Ptr)) return;
2041
2042     VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, &LI);
2043     VRP.add(Constant::getNullValue(Ptr->getType()), Ptr, ICmpInst::ICMP_NE);
2044     VRP.solve();
2045   }
2046
2047   void PredicateSimplifier::Forwards::visitStoreInst(StoreInst &SI) {
2048     Value *Ptr = SI.getPointerOperand();
2049     if (isa<Constant>(Ptr)) return;
2050
2051     VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, &SI);
2052     VRP.add(Constant::getNullValue(Ptr->getType()), Ptr, ICmpInst::ICMP_NE);
2053     VRP.solve();
2054   }
2055
2056   void PredicateSimplifier::Forwards::visitSExtInst(SExtInst &SI) {
2057     VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, &SI);
2058     uint32_t SrcBitWidth = cast<IntegerType>(SI.getSrcTy())->getBitWidth();
2059     uint32_t DstBitWidth = cast<IntegerType>(SI.getDestTy())->getBitWidth();
2060     APInt Min(APInt::getSignedMinValue(SrcBitWidth));
2061     APInt Max(APInt::getSignedMaxValue(SrcBitWidth));
2062     Min.sext(DstBitWidth);
2063     Max.sext(DstBitWidth);
2064     VRP.add(ConstantInt::get(Min), &SI, ICmpInst::ICMP_SLE);
2065     VRP.add(ConstantInt::get(Max), &SI, ICmpInst::ICMP_SGE);
2066     VRP.solve();
2067   }
2068
2069   void PredicateSimplifier::Forwards::visitZExtInst(ZExtInst &ZI) {
2070     VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, &ZI);
2071     uint32_t SrcBitWidth = cast<IntegerType>(ZI.getSrcTy())->getBitWidth();
2072     uint32_t DstBitWidth = cast<IntegerType>(ZI.getDestTy())->getBitWidth();
2073     APInt Max(APInt::getMaxValue(SrcBitWidth));
2074     Max.zext(DstBitWidth);
2075     VRP.add(ConstantInt::get(Max), &ZI, ICmpInst::ICMP_UGE);
2076     VRP.solve();
2077   }
2078
2079   void PredicateSimplifier::Forwards::visitBinaryOperator(BinaryOperator &BO) {
2080     Instruction::BinaryOps ops = BO.getOpcode();
2081
2082     switch (ops) {
2083     default: break;
2084       case Instruction::URem:
2085       case Instruction::SRem:
2086       case Instruction::UDiv:
2087       case Instruction::SDiv: {
2088         Value *Divisor = BO.getOperand(1);
2089         VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, &BO);
2090         VRP.add(Constant::getNullValue(Divisor->getType()), Divisor,
2091                 ICmpInst::ICMP_NE);
2092         VRP.solve();
2093         break;
2094       }
2095     }
2096
2097     switch (ops) {
2098       default: break;
2099       case Instruction::Shl: {
2100         VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, &BO);
2101         VRP.add(&BO, BO.getOperand(0), ICmpInst::ICMP_UGE);
2102         VRP.solve();
2103       } break;
2104       case Instruction::AShr: {
2105         VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, &BO);
2106         VRP.add(&BO, BO.getOperand(0), ICmpInst::ICMP_SLE);
2107         VRP.solve();
2108       } break;
2109       case Instruction::LShr:
2110       case Instruction::UDiv: {
2111         VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, &BO);
2112         VRP.add(&BO, BO.getOperand(0), ICmpInst::ICMP_ULE);
2113         VRP.solve();
2114       } break;
2115       case Instruction::URem: {
2116         VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, &BO);
2117         VRP.add(&BO, BO.getOperand(1), ICmpInst::ICMP_ULE);
2118         VRP.solve();
2119       } break;
2120       case Instruction::And: {
2121         VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, &BO);
2122         VRP.add(&BO, BO.getOperand(0), ICmpInst::ICMP_ULE);
2123         VRP.add(&BO, BO.getOperand(1), ICmpInst::ICMP_ULE);
2124         VRP.solve();
2125       } break;
2126       case Instruction::Or: {
2127         VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, &BO);
2128         VRP.add(&BO, BO.getOperand(0), ICmpInst::ICMP_UGE);
2129         VRP.add(&BO, BO.getOperand(1), ICmpInst::ICMP_UGE);
2130         VRP.solve();
2131       } break;
2132     }
2133   }
2134
2135   void PredicateSimplifier::Forwards::visitICmpInst(ICmpInst &IC) {
2136     // If possible, squeeze the ICmp predicate into something simpler.
2137     // Eg., if x = [0, 4) and we're being asked icmp uge %x, 3 then change
2138     // the predicate to eq.
2139
2140     ICmpInst::Predicate Pred = IC.getPredicate();
2141
2142     if (ConstantInt *Op1 = dyn_cast<ConstantInt>(IC.getOperand(1))) {
2143       ConstantInt *NextVal = 0;
2144       switch(Pred) {
2145         default: break;
2146         case ICmpInst::ICMP_SLT:
2147         case ICmpInst::ICMP_ULT:
2148           if (Op1->getValue() != 0)
2149             NextVal = cast<ConstantInt>(ConstantExpr::getSub(
2150                           Op1, ConstantInt::get(Op1->getType(), 1)));
2151          break;
2152         case ICmpInst::ICMP_SGT:
2153         case ICmpInst::ICMP_UGT:
2154           if (!Op1->getValue().isAllOnesValue())
2155             NextVal = cast<ConstantInt>(ConstantExpr::getAdd(
2156                           Op1, ConstantInt::get(Op1->getType(), 1)));
2157          break;
2158
2159       }
2160       if (NextVal) {
2161         VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, &IC);
2162         if (VRP.isRelatedBy(IC.getOperand(0), NextVal,
2163                             ICmpInst::getInversePredicate(Pred))) {
2164           ICmpInst *NewIC = new ICmpInst(ICmpInst::ICMP_EQ, IC.getOperand(0),
2165                                          NextVal, "", &IC);
2166           NewIC->takeName(&IC);
2167           IC.replaceAllUsesWith(NewIC);
2168           IG.remove(&IC); // XXX: prove this isn't necessary
2169           IC.eraseFromParent();
2170           ++NumSnuggle;
2171           PS->modified = true;
2172           return;
2173         }
2174       }
2175     }
2176
2177     switch(Pred) {
2178       default: return;
2179       case ICmpInst::ICMP_ULE: Pred = ICmpInst::ICMP_ULT; break;
2180       case ICmpInst::ICMP_UGE: Pred = ICmpInst::ICMP_UGT; break;
2181       case ICmpInst::ICMP_SLE: Pred = ICmpInst::ICMP_SLT; break;
2182       case ICmpInst::ICMP_SGE: Pred = ICmpInst::ICMP_SGT; break;
2183     }
2184     VRPSolver VRP(IG, UB, VR, PS->Forest, PS->modified, &IC);
2185     if (VRP.isRelatedBy(IC.getOperand(1), IC.getOperand(0), Pred)) {
2186       ++NumSnuggle;
2187       PS->modified = true;
2188       IC.setPredicate(Pred);
2189     }
2190   }
2191
2192   RegisterPass<PredicateSimplifier> X("predsimplify",
2193                                       "Predicate Simplifier");
2194 }
2195
2196 FunctionPass *llvm::createPredicateSimplifierPass() {
2197   return new PredicateSimplifier();
2198 }