lib/Transforms/Scalar/PredicateSimplifier.cpp

   1 //===-- PredicateSimplifier.cpp - Path Sensitive Simplifier ---------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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].
  74 //
  75 // It never stores an empty range, because that means that the code is
  76 // unreachable. It never stores a single-element range since that's an equality
  77 // relationship and better stored in the InequalityGraph, nor an empty range
  78 // since that is better stored in UnreachableBlocks.
  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/Assembly/Writer.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/Target/TargetData.h"
 101 #include "llvm/Transforms/Utils/Local.h"
 102 #include <algorithm>
 103 #include <deque>
 104 #include <stack>
 105 using namespace llvm;
 106
 107 STATISTIC(NumVarsReplaced, "Number of argument substitutions");
 108 STATISTIC(NumInstruction , "Number of instructions removed");
 109 STATISTIC(NumSimple      , "Number of simple replacements");
 110 STATISTIC(NumBlocks      , "Number of blocks marked unreachable");
 111 STATISTIC(NumSnuggle     , "Number of comparisons snuggled");
 112
 113 namespace {
 114   class DomTreeDFS {
 115   public:
 116     class Node {
 117       friend class DomTreeDFS;
 118     public:
 119       typedef std::vector<Node *>::iterator       iterator;
 120       typedef std::vector<Node *>::const_iterator const_iterator;
 121
 122       unsigned getDFSNumIn()  const { return DFSin;  }
 123       unsigned getDFSNumOut() const { return DFSout; }
 124
 125       BasicBlock *getBlock() const { return BB; }
 126
 127       iterator begin() { return Children.begin(); }
 128       iterator end()   { return Children.end();   }
 129
 130       const_iterator begin() const { return Children.begin(); }
 131       const_iterator end()   const { return Children.end();   }
 132
 133       bool dominates(const Node *N) const {
 134         return DFSin <= N->DFSin && DFSout >= N->DFSout;
 135       }
 136
 137       bool DominatedBy(const Node *N) const {
 138         return N->dominates(this);
 139       }
 140
 141       /// Sorts by the number of descendants. With this, you can iterate
 142       /// through a sorted list and the first matching entry is the most
 143       /// specific match for your basic block. The order provided is stable;
 144       /// DomTreeDFS::Nodes with the same number of descendants are sorted by
 145       /// DFS in number.
 146       bool operator<(const Node &N) const {
 147         unsigned   spread =   DFSout -   DFSin;
 148         unsigned N_spread = N.DFSout - N.DFSin;
 149         if (spread == N_spread) return DFSin < N.DFSin;
 150         return spread < N_spread;
 151       }
 152       bool operator>(const Node &N) const { return N < *this; }
 153
 154     private:
 155       unsigned DFSin, DFSout;
 156       BasicBlock *BB;
 157
 158       std::vector<Node *> Children;
 159     };
 160
 161     // XXX: this may be slow. Instead of using "new" for each node, consider
 162     // putting them in a vector to keep them contiguous.
 163     explicit DomTreeDFS(DominatorTree *DT) {
 164       std::stack<std::pair<Node *, DomTreeNode *> > S;
 165
 166       Entry = new Node;
 167       Entry->BB = DT->getRootNode()->getBlock();
 168       S.push(std::make_pair(Entry, DT->getRootNode()));
 169
 170       NodeMap[Entry->BB] = Entry;
 171
 172       while (!S.empty()) {
 173         std::pair<Node *, DomTreeNode *> &Pair = S.top();
 174         Node *N = Pair.first;
 175         DomTreeNode *DTNode = Pair.second;
 176         S.pop();
 177
 178         for (DomTreeNode::iterator I = DTNode->begin(), E = DTNode->end();
 179              I != E; ++I) {
 180           Node *NewNode = new Node;
 181           NewNode->BB = (*I)->getBlock();
 182           N->Children.push_back(NewNode);
 183           S.push(std::make_pair(NewNode, *I));
 184
 185           NodeMap[NewNode->BB] = NewNode;
 186         }
 187       }
 188
 189       renumber();
 190
 191 #ifndef NDEBUG
 192       DEBUG(dump());
 193 #endif
 194     }
 195
 196 #ifndef NDEBUG
 197     virtual
 198 #endif
 199     ~DomTreeDFS() {
 200       std::stack<Node *> S;
 201
 202       S.push(Entry);
 203       while (!S.empty()) {
 204         Node *N = S.top(); S.pop();
 205
 206         for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I)
 207           S.push(*I);
 208
 209         delete N;
 210       }
 211     }
 212
 213     /// getRootNode - This returns the entry node for the CFG of the function.
 214     Node *getRootNode() const { return Entry; }
 215
 216     /// getNodeForBlock - return the node for the specified basic block.
 217     Node *getNodeForBlock(BasicBlock *BB) const {
 218       if (!NodeMap.count(BB)) return 0;
 219       return const_cast<DomTreeDFS*>(this)->NodeMap[BB];
 220     }
 221
 222     /// dominates - returns true if the basic block for I1 dominates that of
 223     /// the basic block for I2. If the instructions belong to the same basic
 224     /// block, the instruction first instruction sequentially in the block is
 225     /// considered dominating.
 226     bool dominates(Instruction *I1, Instruction *I2) {
 227       BasicBlock *BB1 = I1->getParent(),
 228                  *BB2 = I2->getParent();
 229       if (BB1 == BB2) {
 230         if (isa<TerminatorInst>(I1)) return false;
 231         if (isa<TerminatorInst>(I2)) return true;
 232         if ( isa<PHINode>(I1) && !isa<PHINode>(I2)) return true;
 233         if (!isa<PHINode>(I1) &&  isa<PHINode>(I2)) return false;
 234
 235         for (BasicBlock::const_iterator I = BB2->begin(), E = BB2->end();
 236              I != E; ++I) {
 237           if (&*I == I1) return true;
 238           else if (&*I == I2) return false;
 239         }
 240         assert(!"Instructions not found in parent BasicBlock?");
 241       } else {
 242         Node *Node1 = getNodeForBlock(BB1),
 243              *Node2 = getNodeForBlock(BB2);
 244         return Node1 && Node2 && Node1->dominates(Node2);
 245       }
 246       return false; // Not reached
 247     }
 248
 249   private:
 250     /// renumber - calculates the depth first search numberings and applies
 251     /// them onto the nodes.
 252     void renumber() {
 253       std::stack<std::pair<Node *, Node::iterator> > S;
 254       unsigned n = 0;
 255
 256       Entry->DFSin = ++n;
 257       S.push(std::make_pair(Entry, Entry->begin()));
 258
 259       while (!S.empty()) {
 260         std::pair<Node *, Node::iterator> &Pair = S.top();
 261         Node *N = Pair.first;
 262         Node::iterator &I = Pair.second;
 263
 264         if (I == N->end()) {
 265           N->DFSout = ++n;
 266           S.pop();
 267         } else {
 268           Node *Next = *I++;
 269           Next->DFSin = ++n;
 270           S.push(std::make_pair(Next, Next->begin()));
 271         }
 272       }
 273     }
 274
 275 #ifndef NDEBUG
 276     virtual void dump() const {
 277       dump(*cerr.stream());
 278     }
 279
 280     void dump(std::ostream &os) const {
 281       os << "Predicate simplifier DomTreeDFS: \n";
 282       dump(Entry, 0, os);
 283       os << "\n\n";
 284     }
 285
 286     void dump(Node *N, int depth, std::ostream &os) const {
 287       ++depth;
 288       for (int i = 0; i < depth; ++i) { os << " "; }
 289       os << "[" << depth << "] ";
 290
 291       os << N->getBlock()->getName() << " (" << N->getDFSNumIn()
 292          << ", " << N->getDFSNumOut() << ")\n";
 293
 294       for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I)
 295         dump(*I, depth, os);
 296     }
 297 #endif
 298
 299     Node *Entry;
 300     std::map<BasicBlock *, Node *> NodeMap;
 301   };
 302
 303   // SLT SGT ULT UGT EQ
 304   //   0   1   0   1  0 -- GT                  10
 305   //   0   1   0   1  1 -- GE                  11
 306   //   0   1   1   0  0 -- SGTULT              12
 307   //   0   1   1   0  1 -- SGEULE              13
 308   //   0   1   1   1  0 -- SGT                 14
 309   //   0   1   1   1  1 -- SGE                 15
 310   //   1   0   0   1  0 -- SLTUGT              18
 311   //   1   0   0   1  1 -- SLEUGE              19
 312   //   1   0   1   0  0 -- LT                  20
 313   //   1   0   1   0  1 -- LE                  21
 314   //   1   0   1   1  0 -- SLT                 22
 315   //   1   0   1   1  1 -- SLE                 23
 316   //   1   1   0   1  0 -- UGT                 26
 317   //   1   1   0   1  1 -- UGE                 27
 318   //   1   1   1   0  0 -- ULT                 28
 319   //   1   1   1   0  1 -- ULE                 29
 320   //   1   1   1   1  0 -- NE                  30
 321   enum LatticeBits {
 322     EQ_BIT = 1, UGT_BIT = 2, ULT_BIT = 4, SGT_BIT = 8, SLT_BIT = 16
 323   };
 324   enum LatticeVal {
 325     GT = SGT_BIT | UGT_BIT,
 326     GE = GT | EQ_BIT,
 327     LT = SLT_BIT | ULT_BIT,
 328     LE = LT | EQ_BIT,
 329     NE = SLT_BIT | SGT_BIT | ULT_BIT | UGT_BIT,
 330     SGTULT = SGT_BIT | ULT_BIT,
 331     SGEULE = SGTULT | EQ_BIT,
 332     SLTUGT = SLT_BIT | UGT_BIT,
 333     SLEUGE = SLTUGT | EQ_BIT,
 334     ULT = SLT_BIT | SGT_BIT | ULT_BIT,
 335     UGT = SLT_BIT | SGT_BIT | UGT_BIT,
 336     SLT = SLT_BIT | ULT_BIT | UGT_BIT,
 337     SGT = SGT_BIT | ULT_BIT | UGT_BIT,
 338     SLE = SLT | EQ_BIT,
 339     SGE = SGT | EQ_BIT,
 340     ULE = ULT | EQ_BIT,
 341     UGE = UGT | EQ_BIT
 342   };
 343
 344 #ifndef NDEBUG
 345   /// validPredicate - determines whether a given value is actually a lattice
 346   /// value. Only used in assertions or debugging.
 347   static bool validPredicate(LatticeVal LV) {
 348     switch (LV) {
 349       case GT: case GE: case LT: case LE: case NE:
 350       case SGTULT: case SGT: case SGEULE:
 351       case SLTUGT: case SLT: case SLEUGE:
 352       case ULT: case UGT:
 353       case SLE: case SGE: case ULE: case UGE:
 354         return true;
 355       default:
 356         return false;
 357     }
 358   }
 359 #endif
 360
 361   /// reversePredicate - reverse the direction of the inequality
 362   static LatticeVal reversePredicate(LatticeVal LV) {
 363     unsigned reverse = LV ^ (SLT_BIT|SGT_BIT|ULT_BIT|UGT_BIT); //preserve EQ_BIT
 364
 365     if ((reverse & (SLT_BIT|SGT_BIT)) == 0)
 366       reverse |= (SLT_BIT|SGT_BIT);
 367
 368     if ((reverse & (ULT_BIT|UGT_BIT)) == 0)
 369       reverse |= (ULT_BIT|UGT_BIT);
 370
 371     LatticeVal Rev = static_cast<LatticeVal>(reverse);
 372     assert(validPredicate(Rev) && "Failed reversing predicate.");
 373     return Rev;
 374   }
 375
 376   /// ValueNumbering stores the scope-specific value numbers for a given Value.
 377   class VISIBILITY_HIDDEN ValueNumbering {
 378
 379     /// VNPair is a tuple of {Value, index number, DomTreeDFS::Node}. It
 380     /// includes the comparison operators necessary to allow you to store it
 381     /// in a sorted vector.
 382     class VISIBILITY_HIDDEN VNPair {
 383     public:
 384       Value *V;
 385       unsigned index;
 386       DomTreeDFS::Node *Subtree;
 387
 388       VNPair(Value *V, unsigned index, DomTreeDFS::Node *Subtree)
 389         : V(V), index(index), Subtree(Subtree) {}
 390
 391       bool operator==(const VNPair &RHS) const {
 392         return V == RHS.V && Subtree == RHS.Subtree;
 393       }
 394
 395       bool operator<(const VNPair &RHS) const {
 396         if (V != RHS.V) return V < RHS.V;
 397         return *Subtree < *RHS.Subtree;
 398       }
 399
 400       bool operator<(Value *RHS) const {
 401         return V < RHS;
 402       }
 403
 404       bool operator>(Value *RHS) const {
 405         return V > RHS;
 406       }
 407
 408       friend bool operator<(Value *RHS, const VNPair &pair) {
 409         return pair.operator>(RHS);
 410       }
 411     };
 412
 413     typedef std::vector<VNPair> VNMapType;
 414     VNMapType VNMap;
 415
 416     /// The canonical choice for value number at index.
 417     std::vector<Value *> Values;
 418
 419     DomTreeDFS *DTDFS;
 420
 421   public:
 422 #ifndef NDEBUG
 423     virtual ~ValueNumbering() {}
 424     virtual void dump() {
 425       dump(*cerr.stream());
 426     }
 427
 428     void dump(std::ostream &os) {
 429       for (unsigned i = 1; i <= Values.size(); ++i) {
 430         os << i << " = ";
 431         WriteAsOperand(os, Values[i-1]);
 432         os << " {";
 433         for (unsigned j = 0; j < VNMap.size(); ++j) {
 434           if (VNMap[j].index == i) {
 435             WriteAsOperand(os, VNMap[j].V);
 436             os << " (" << VNMap[j].Subtree->getDFSNumIn() << ")  ";
 437           }
 438         }
 439         os << "}\n";
 440       }
 441     }
 442 #endif
 443
 444     /// compare - returns true if V1 is a better canonical value than V2.
 445     bool compare(Value *V1, Value *V2) const {
 446       if (isa<Constant>(V1))
 447         return !isa<Constant>(V2);
 448       else if (isa<Constant>(V2))
 449         return false;
 450       else if (isa<Argument>(V1))
 451         return !isa<Argument>(V2);
 452       else if (isa<Argument>(V2))
 453         return false;
 454
 455       Instruction *I1 = dyn_cast<Instruction>(V1);
 456       Instruction *I2 = dyn_cast<Instruction>(V2);
 457
 458       if (!I1 || !I2)
 459         return V1->getNumUses() < V2->getNumUses();
 460
 461       return DTDFS->dominates(I1, I2);
 462     }
 463
 464     ValueNumbering(DomTreeDFS *DTDFS) : DTDFS(DTDFS) {}
 465
 466     /// valueNumber - finds the value number for V under the Subtree. If
 467     /// there is no value number, returns zero.
 468     unsigned valueNumber(Value *V, DomTreeDFS::Node *Subtree) {
 469       if (!(isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V))
 470           || V->getType() == Type::VoidTy) return 0;
 471
 472       VNMapType::iterator E = VNMap.end();
 473       VNPair pair(V, 0, Subtree);
 474       VNMapType::iterator I = std::lower_bound(VNMap.begin(), E, pair);
 475       while (I != E && I->V == V) {
 476         if (I->Subtree->dominates(Subtree))
 477           return I->index;
 478         ++I;
 479       }
 480       return 0;
 481     }
 482
 483     /// getOrInsertVN - always returns a value number, creating it if necessary.
 484     unsigned getOrInsertVN(Value *V, DomTreeDFS::Node *Subtree) {
 485       if (unsigned n = valueNumber(V, Subtree))
 486         return n;
 487       else
 488         return newVN(V);
 489     }
 490
 491     /// newVN - creates a new value number. Value V must not already have a
 492     /// value number assigned.
 493     unsigned newVN(Value *V) {
 494       assert((isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V)) &&
 495              "Bad Value for value numbering.");
 496       assert(V->getType() != Type::VoidTy && "Won't value number a void value");
 497
 498       Values.push_back(V);
 499
 500       VNPair pair = VNPair(V, Values.size(), DTDFS->getRootNode());
 501       VNMapType::iterator I = std::lower_bound(VNMap.begin(), VNMap.end(), pair);
 502       assert((I == VNMap.end() || value(I->index) != V) &&
 503              "Attempt to create a duplicate value number.");
 504       VNMap.insert(I, pair);
 505
 506       return Values.size();
 507     }
 508
 509     /// value - returns the Value associated with a value number.
 510     Value *value(unsigned index) const {
 511       assert(index != 0 && "Zero index is reserved for not found.");
 512       assert(index <= Values.size() && "Index out of range.");
 513       return Values[index-1];
 514     }
 515
 516     /// canonicalize - return a Value that is equal to V under Subtree.
 517     Value *canonicalize(Value *V, DomTreeDFS::Node *Subtree) {
 518       if (isa<Constant>(V)) return V;
 519
 520       if (unsigned n = valueNumber(V, Subtree))
 521         return value(n);
 522       else
 523         return V;
 524     }
 525
 526     /// addEquality - adds that value V belongs to the set of equivalent
 527     /// values defined by value number n under Subtree.
 528     void addEquality(unsigned n, Value *V, DomTreeDFS::Node *Subtree) {
 529       assert(canonicalize(value(n), Subtree) == value(n) &&
 530              "Node's 'canonical' choice isn't best within this subtree.");
 531
 532       // Suppose that we are given "%x -> node #1 (%y)". The problem is that
 533       // we may already have "%z -> node #2 (%x)" somewhere above us in the
 534       // graph. We need to find those edges and add "%z -> node #1 (%y)"
 535       // to keep the lookups canonical.
 536
 537       std::vector<Value *> ToRepoint(1, V);
 538
 539       if (unsigned Conflict = valueNumber(V, Subtree)) {
 540         for (VNMapType::iterator I = VNMap.begin(), E = VNMap.end();
 541              I != E; ++I) {
 542           if (I->index == Conflict && I->Subtree->dominates(Subtree))
 543             ToRepoint.push_back(I->V);
 544         }
 545       }
 546
 547       for (std::vector<Value *>::iterator VI = ToRepoint.begin(),
 548            VE = ToRepoint.end(); VI != VE; ++VI) {
 549         Value *V = *VI;
 550
 551         VNPair pair(V, n, Subtree);
 552         VNMapType::iterator B = VNMap.begin(), E = VNMap.end();
 553         VNMapType::iterator I = std::lower_bound(B, E, pair);
 554         if (I != E && I->V == V && I->Subtree == Subtree)
 555           I->index = n; // Update best choice
 556         else
 557           VNMap.insert(I, pair); // New Value
 558
 559         // XXX: we currently don't have to worry about updating values with
 560         // more specific Subtrees, but we will need to for PHI node support.
 561
 562 #ifndef NDEBUG
 563         Value *V_n = value(n);
 564         if (isa<Constant>(V) && isa<Constant>(V_n)) {
 565           assert(V == V_n && "Constant equals different constant?");
 566         }
 567 #endif
 568       }
 569     }
 570
 571     /// remove - removes all references to value V.
 572     void remove(Value *V) {
 573       VNMapType::iterator B = VNMap.begin(), E = VNMap.end();
 574       VNPair pair(V, 0, DTDFS->getRootNode());
 575       VNMapType::iterator J = std::upper_bound(B, E, pair);
 576       VNMapType::iterator I = J;
 577
 578       while (I != B && (I == E || I->V == V)) --I;
 579
 580       VNMap.erase(I, J);
 581     }
 582   };
 583
 584   /// The InequalityGraph stores the relationships between values.
 585   /// Each Value in the graph is assigned to a Node. Nodes are pointer
 586   /// comparable for equality. The caller is expected to maintain the logical
 587   /// consistency of the system.
 588   ///
 589   /// The InequalityGraph class may invalidate Node*s after any mutator call.
 590   /// @brief The InequalityGraph stores the relationships between values.
 591   class VISIBILITY_HIDDEN InequalityGraph {
 592     ValueNumbering &VN;
 593     DomTreeDFS::Node *TreeRoot;
 594
 595     InequalityGraph();                  // DO NOT IMPLEMENT
 596     InequalityGraph(InequalityGraph &); // DO NOT IMPLEMENT
 597   public:
 598     InequalityGraph(ValueNumbering &VN, DomTreeDFS::Node *TreeRoot)
 599       : VN(VN), TreeRoot(TreeRoot) {}
 600
 601     class Node;
 602
 603     /// An Edge is contained inside a Node making one end of the edge implicit
 604     /// and contains a pointer to the other end. The edge contains a lattice
 605     /// value specifying the relationship and an DomTreeDFS::Node specifying
 606     /// the root in the dominator tree to which this edge applies.
 607     class VISIBILITY_HIDDEN Edge {
 608     public:
 609       Edge(unsigned T, LatticeVal V, DomTreeDFS::Node *ST)
 610         : To(T), LV(V), Subtree(ST) {}
 611
 612       unsigned To;
 613       LatticeVal LV;
 614       DomTreeDFS::Node *Subtree;
 615
 616       bool operator<(const Edge &edge) const {
 617         if (To != edge.To) return To < edge.To;
 618         return *Subtree < *edge.Subtree;
 619       }
 620
 621       bool operator<(unsigned to) const {
 622         return To < to;
 623       }
 624
 625       bool operator>(unsigned to) const {
 626         return To > to;
 627       }
 628
 629       friend bool operator<(unsigned to, const Edge &edge) {
 630         return edge.operator>(to);
 631       }
 632     };
 633
 634     /// A single node in the InequalityGraph. This stores the canonical Value
 635     /// for the node, as well as the relationships with the neighbours.
 636     ///
 637     /// @brief A single node in the InequalityGraph.
 638     class VISIBILITY_HIDDEN Node {
 639       friend class InequalityGraph;
 640
 641       typedef SmallVector<Edge, 4> RelationsType;
 642       RelationsType Relations;
 643
 644       // TODO: can this idea improve performance?
 645       //friend class std::vector<Node>;
 646       //Node(Node &N) { RelationsType.swap(N.RelationsType); }
 647
 648     public:
 649       typedef RelationsType::iterator       iterator;
 650       typedef RelationsType::const_iterator const_iterator;
 651
 652 #ifndef NDEBUG
 653       virtual ~Node() {}
 654       virtual void dump() const {
 655         dump(*cerr.stream());
 656       }
 657     private:
 658       void dump(std::ostream &os) const {
 659         static const std::string names[32] =
 660           { "000000", "000001", "000002", "000003", "000004", "000005",
 661             "000006", "000007", "000008", "000009", "     >", "    >=",
 662             "  s>u<", "s>=u<=", "    s>", "   s>=", "000016", "000017",
 663             "  s<u>", "s<=u>=", "     <", "    <=", "    s<", "   s<=",
 664             "000024", "000025", "    u>", "   u>=", "    u<", "   u<=",
 665             "    !=", "000031" };
 666         for (Node::const_iterator NI = begin(), NE = end(); NI != NE; ++NI) {
 667           os << names[NI->LV] << " " << NI->To
 668              << " (" << NI->Subtree->getDFSNumIn() << "), ";
 669         }
 670       }
 671     public:
 672 #endif
 673
 674       iterator begin()             { return Relations.begin(); }
 675       iterator end()               { return Relations.end();   }
 676       const_iterator begin() const { return Relations.begin(); }
 677       const_iterator end()   const { return Relations.end();   }
 678
 679       iterator find(unsigned n, DomTreeDFS::Node *Subtree) {
 680         iterator E = end();
 681         for (iterator I = std::lower_bound(begin(), E, n);
 682              I != E && I->To == n; ++I) {
 683           if (Subtree->DominatedBy(I->Subtree))
 684             return I;
 685         }
 686         return E;
 687       }
 688
 689       const_iterator find(unsigned n, DomTreeDFS::Node *Subtree) const {
 690         const_iterator E = end();
 691         for (const_iterator I = std::lower_bound(begin(), E, n);
 692              I != E && I->To == n; ++I) {
 693           if (Subtree->DominatedBy(I->Subtree))
 694             return I;
 695         }
 696         return E;
 697       }
 698
 699       /// update - updates the lattice value for a given node, creating a new
 700       /// entry if one doesn't exist. The new lattice value must not be
 701       /// inconsistent with any previously existing value.
 702       void update(unsigned n, LatticeVal R, DomTreeDFS::Node *Subtree) {
 703         assert(validPredicate(R) && "Invalid predicate.");
 704
 705         Edge edge(n, R, Subtree);
 706         iterator B = begin(), E = end();
 707         iterator I = std::lower_bound(B, E, edge);
 708
 709         iterator J = I;
 710         while (J != E && J->To == n) {
 711           if (Subtree->DominatedBy(J->Subtree))
 712             break;
 713           ++J;
 714         }
 715
 716         if (J != E && J->To == n) {
 717           edge.LV = static_cast<LatticeVal>(J->LV & R);
 718           assert(validPredicate(edge.LV) && "Invalid union of lattice values.");
 719
 720           if (edge.LV == J->LV)
 721             return; // This update adds nothing new.
 722         }
 723
 724         if (I != B) {
 725           // We also have to tighten any edge beneath our update.
 726           for (iterator K = I - 1; K->To == n; --K) {
 727             if (K->Subtree->DominatedBy(Subtree)) {
 728               LatticeVal LV = static_cast<LatticeVal>(K->LV & edge.LV);
 729               assert(validPredicate(LV) && "Invalid union of lattice values");
 730               K->LV = LV;
 731             }
 732             if (K == B) break;
 733           }
 734         }
 735
 736         // Insert new edge at Subtree if it isn't already there.
 737         if (I == E || I->To != n || Subtree != I->Subtree)
 738           Relations.insert(I, edge);
 739       }
 740     };
 741
 742   private:
 743
 744     std::vector<Node> Nodes;
 745
 746   public:
 747     /// node - returns the node object at a given value number. The pointer
 748     /// returned may be invalidated on the next call to node().
 749     Node *node(unsigned index) {
 750       assert(VN.value(index)); // This triggers the necessary checks.
 751       if (Nodes.size() < index) Nodes.resize(index);
 752       return &Nodes[index-1];
 753     }
 754
 755     /// isRelatedBy - true iff n1 op n2
 756     bool isRelatedBy(unsigned n1, unsigned n2, DomTreeDFS::Node *Subtree,
 757                      LatticeVal LV) {
 758       if (n1 == n2) return LV & EQ_BIT;
 759
 760       Node *N1 = node(n1);
 761       Node::iterator I = N1->find(n2, Subtree), E = N1->end();
 762       if (I != E) return (I->LV & LV) == I->LV;
 763
 764       return false;
 765     }
 766
 767     // The add* methods assume that your input is logically valid and may
 768     // assertion-fail or infinitely loop if you attempt a contradiction.
 769
 770     /// addInequality - Sets n1 op n2.
 771     /// It is also an error to call this on an inequality that is already true.
 772     void addInequality(unsigned n1, unsigned n2, DomTreeDFS::Node *Subtree,
 773                        LatticeVal LV1) {
 774       assert(n1 != n2 && "A node can't be inequal to itself.");
 775
 776       if (LV1 != NE)
 777         assert(!isRelatedBy(n1, n2, Subtree, reversePredicate(LV1)) &&
 778                "Contradictory inequality.");
 779
 780       // Suppose we're adding %n1 < %n2. Find all the %a < %n1 and
 781       // add %a < %n2 too. This keeps the graph fully connected.
 782       if (LV1 != NE) {
 783         // Break up the relationship into signed and unsigned comparison parts.
 784         // If the signed parts of %a op1 %n1 match that of %n1 op2 %n2, and
 785         // op1 and op2 aren't NE, then add %a op3 %n2. The new relationship
 786         // should have the EQ_BIT iff it's set for both op1 and op2.
 787
 788         unsigned LV1_s = LV1 & (SLT_BIT|SGT_BIT);
 789         unsigned LV1_u = LV1 & (ULT_BIT|UGT_BIT);
 790
 791         for (Node::iterator I = node(n1)->begin(), E = node(n1)->end(); I != E; ++I) {
 792           if (I->LV != NE && I->To != n2) {
 793
 794             DomTreeDFS::Node *Local_Subtree = NULL;
 795             if (Subtree->DominatedBy(I->Subtree))
 796               Local_Subtree = Subtree;
 797             else if (I->Subtree->DominatedBy(Subtree))
 798               Local_Subtree = I->Subtree;
 799
 800             if (Local_Subtree) {
 801               unsigned new_relationship = 0;
 802               LatticeVal ILV = reversePredicate(I->LV);
 803               unsigned ILV_s = ILV & (SLT_BIT|SGT_BIT);
 804               unsigned ILV_u = ILV & (ULT_BIT|UGT_BIT);
 805
 806               if (LV1_s != (SLT_BIT|SGT_BIT) && ILV_s == LV1_s)
 807                 new_relationship |= ILV_s;
 808               if (LV1_u != (ULT_BIT|UGT_BIT) && ILV_u == LV1_u)
 809                 new_relationship |= ILV_u;
 810
 811               if (new_relationship) {
 812                 if ((new_relationship & (SLT_BIT|SGT_BIT)) == 0)
 813                   new_relationship |= (SLT_BIT|SGT_BIT);
 814                 if ((new_relationship & (ULT_BIT|UGT_BIT)) == 0)
 815                   new_relationship |= (ULT_BIT|UGT_BIT);
 816                 if ((LV1 & EQ_BIT) && (ILV & EQ_BIT))
 817                   new_relationship |= EQ_BIT;
 818
 819                 LatticeVal NewLV = static_cast<LatticeVal>(new_relationship);
 820
 821                 node(I->To)->update(n2, NewLV, Local_Subtree);
 822                 node(n2)->update(I->To, reversePredicate(NewLV), Local_Subtree);
 823               }
 824             }
 825           }
 826         }
 827
 828         for (Node::iterator I = node(n2)->begin(), E = node(n2)->end(); I != E; ++I) {
 829           if (I->LV != NE && I->To != n1) {
 830             DomTreeDFS::Node *Local_Subtree = NULL;
 831             if (Subtree->DominatedBy(I->Subtree))
 832               Local_Subtree = Subtree;
 833             else if (I->Subtree->DominatedBy(Subtree))
 834               Local_Subtree = I->Subtree;
 835
 836             if (Local_Subtree) {
 837               unsigned new_relationship = 0;
 838               unsigned ILV_s = I->LV & (SLT_BIT|SGT_BIT);
 839               unsigned ILV_u = I->LV & (ULT_BIT|UGT_BIT);
 840
 841               if (LV1_s != (SLT_BIT|SGT_BIT) && ILV_s == LV1_s)
 842                 new_relationship |= ILV_s;
 843
 844               if (LV1_u != (ULT_BIT|UGT_BIT) && ILV_u == LV1_u)
 845                 new_relationship |= ILV_u;
 846
 847               if (new_relationship) {
 848                 if ((new_relationship & (SLT_BIT|SGT_BIT)) == 0)
 849                   new_relationship |= (SLT_BIT|SGT_BIT);
 850                 if ((new_relationship & (ULT_BIT|UGT_BIT)) == 0)
 851                   new_relationship |= (ULT_BIT|UGT_BIT);
 852                 if ((LV1 & EQ_BIT) && (I->LV & EQ_BIT))
 853                   new_relationship |= EQ_BIT;
 854
 855                 LatticeVal NewLV = static_cast<LatticeVal>(new_relationship);
 856
 857                 node(n1)->update(I->To, NewLV, Local_Subtree);
 858                 node(I->To)->update(n1, reversePredicate(NewLV), Local_Subtree);
 859               }
 860             }
 861           }
 862         }
 863       }
 864
 865       node(n1)->update(n2, LV1, Subtree);
 866       node(n2)->update(n1, reversePredicate(LV1), Subtree);
 867     }
 868
 869     /// remove - removes a node from the graph by removing all references to
 870     /// and from it.
 871     void remove(unsigned n) {
 872       Node *N = node(n);
 873       for (Node::iterator NI = N->begin(), NE = N->end(); NI != NE; ++NI) {
 874         Node::iterator Iter = node(NI->To)->find(n, TreeRoot);
 875         do {
 876           node(NI->To)->Relations.erase(Iter);
 877           Iter = node(NI->To)->find(n, TreeRoot);
 878         } while (Iter != node(NI->To)->end());
 879       }
 880       N->Relations.clear();
 881     }
 882
 883 #ifndef NDEBUG
 884     virtual ~InequalityGraph() {}
 885     virtual void dump() {
 886       dump(*cerr.stream());
 887     }
 888
 889     void dump(std::ostream &os) {
 890       for (unsigned i = 1; i <= Nodes.size(); ++i) {
 891         os << i << " = {";
 892         node(i)->dump(os);
 893         os << "}\n";
 894       }
 895     }
 896 #endif
 897   };
 898
 899   class VRPSolver;
 900
 901   /// ValueRanges tracks the known integer ranges and anti-ranges of the nodes
 902   /// in the InequalityGraph.
 903   class VISIBILITY_HIDDEN ValueRanges {
 904     ValueNumbering &VN;
 905     TargetData *TD;
 906
 907     class VISIBILITY_HIDDEN ScopedRange {
 908       typedef std::vector<std::pair<DomTreeDFS::Node *, ConstantRange> >
 909               RangeListType;
 910       RangeListType RangeList;
 911
 912       static bool swo(const std::pair<DomTreeDFS::Node *, ConstantRange> &LHS,
 913                       const std::pair<DomTreeDFS::Node *, ConstantRange> &RHS) {
 914         return *LHS.first < *RHS.first;
 915       }
 916
 917     public:
 918 #ifndef NDEBUG
 919       virtual ~ScopedRange() {}
 920       virtual void dump() const {
 921         dump(*cerr.stream());
 922       }
 923
 924       void dump(std::ostream &os) const {
 925         os << "{";
 926         for (const_iterator I = begin(), E = end(); I != E; ++I) {
 927           os << &I->second << " (" << I->first->getDFSNumIn() << "), ";
 928         }
 929         os << "}";
 930       }
 931 #endif
 932
 933       typedef RangeListType::iterator       iterator;
 934       typedef RangeListType::const_iterator const_iterator;
 935
 936       iterator begin() { return RangeList.begin(); }
 937       iterator end()   { return RangeList.end(); }
 938       const_iterator begin() const { return RangeList.begin(); }
 939       const_iterator end()   const { return RangeList.end(); }
 940
 941       iterator find(DomTreeDFS::Node *Subtree) {
 942         static ConstantRange empty(1, false);
 943         iterator E = end();
 944         iterator I = std::lower_bound(begin(), E,
 945                                       std::make_pair(Subtree, empty), swo);
 946
 947         while (I != E && !I->first->dominates(Subtree)) ++I;
 948         return I;
 949       }
 950
 951       const_iterator find(DomTreeDFS::Node *Subtree) const {
 952         static const ConstantRange empty(1, false);
 953         const_iterator E = end();
 954         const_iterator I = std::lower_bound(begin(), E,
 955                                             std::make_pair(Subtree, empty), swo);
 956
 957         while (I != E && !I->first->dominates(Subtree)) ++I;
 958         return I;
 959       }
 960
 961       void update(const ConstantRange &CR, DomTreeDFS::Node *Subtree) {
 962         assert(!CR.isEmptySet() && "Empty ConstantRange.");
 963         assert(!CR.isSingleElement() && "Refusing to store single element.");
 964
 965         static ConstantRange empty(1, false);
 966         iterator E = end();
 967         iterator I =
 968             std::lower_bound(begin(), E, std::make_pair(Subtree, empty), swo);
 969
 970         if (I != end() && I->first == Subtree) {
 971           ConstantRange CR2 = I->second.maximalIntersectWith(CR);
 972           assert(!CR2.isEmptySet() && !CR2.isSingleElement() &&
 973                  "Invalid union of ranges.");
 974           I->second = CR2;
 975         } else
 976           RangeList.insert(I, std::make_pair(Subtree, CR));
 977       }
 978     };
 979
 980     std::vector<ScopedRange> Ranges;
 981
 982     void update(unsigned n, const ConstantRange &CR, DomTreeDFS::Node *Subtree){
 983       if (CR.isFullSet()) return;
 984       if (Ranges.size() < n) Ranges.resize(n);
 985       Ranges[n-1].update(CR, Subtree);
 986     }
 987
 988     /// create - Creates a ConstantRange that matches the given LatticeVal
 989     /// relation with a given integer.
 990     ConstantRange create(LatticeVal LV, const ConstantRange &CR) {
 991       assert(!CR.isEmptySet() && "Can't deal with empty set.");
 992
 993       if (LV == NE)
 994         return makeConstantRange(ICmpInst::ICMP_NE, CR);
 995
 996       unsigned LV_s = LV & (SGT_BIT|SLT_BIT);
 997       unsigned LV_u = LV & (UGT_BIT|ULT_BIT);
 998       bool hasEQ = LV & EQ_BIT;
 999
1000       ConstantRange Range(CR.getBitWidth());
1001
1002       if (LV_s == SGT_BIT) {
1003         Range = Range.maximalIntersectWith(makeConstantRange(
1004                     hasEQ ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_SGT, CR));
1005       } else if (LV_s == SLT_BIT) {
1006         Range = Range.maximalIntersectWith(makeConstantRange(
1007                     hasEQ ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_SLT, CR));
1008       }
1009
1010       if (LV_u == UGT_BIT) {
1011         Range = Range.maximalIntersectWith(makeConstantRange(
1012                     hasEQ ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_UGT, CR));
1013       } else if (LV_u == ULT_BIT) {
1014         Range = Range.maximalIntersectWith(makeConstantRange(
1015                     hasEQ ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_ULT, CR));
1016       }
1017
1018       return Range;
1019     }
1020
1021     /// makeConstantRange - Creates a ConstantRange representing the set of all
1022     /// value that match the ICmpInst::Predicate with any of the values in CR.
1023     ConstantRange makeConstantRange(ICmpInst::Predicate ICmpOpcode,
1024                                     const ConstantRange &CR) {
1025       uint32_t W = CR.getBitWidth();
1026       switch (ICmpOpcode) {
1027         default: assert(!"Invalid ICmp opcode to makeConstantRange()");
1028         case ICmpInst::ICMP_EQ:
1029           return ConstantRange(CR.getLower(), CR.getUpper());
1030         case ICmpInst::ICMP_NE:
1031           if (CR.isSingleElement())
1032             return ConstantRange(CR.getUpper(), CR.getLower());
1033           return ConstantRange(W);
1034         case ICmpInst::ICMP_ULT:
1035           return ConstantRange(APInt::getMinValue(W), CR.getUnsignedMax());
1036         case ICmpInst::ICMP_SLT:
1037           return ConstantRange(APInt::getSignedMinValue(W), CR.getSignedMax());
1038         case ICmpInst::ICMP_ULE: {
1039           APInt UMax(CR.getUnsignedMax());
1040           if (UMax.isMaxValue())
1041             return ConstantRange(W);
1042           return ConstantRange(APInt::getMinValue(W), UMax + 1);
1043         }
1044         case ICmpInst::ICMP_SLE: {
1045           APInt SMax(CR.getSignedMax());
1046           if (SMax.isMaxSignedValue() || (SMax+1).isMaxSignedValue())
1047             return ConstantRange(W);
1048           return ConstantRange(APInt::getSignedMinValue(W), SMax + 1);
1049         }
1050         case ICmpInst::ICMP_UGT:
1051           return ConstantRange(CR.getUnsignedMin() + 1, APInt::getNullValue(W));
1052         case ICmpInst::ICMP_SGT:
1053           return ConstantRange(CR.getSignedMin() + 1,
1054                                APInt::getSignedMinValue(W));
1055         case ICmpInst::ICMP_UGE: {
1056           APInt UMin(CR.getUnsignedMin());
1057           if (UMin.isMinValue())
1058             return ConstantRange(W);
1059           return ConstantRange(UMin, APInt::getNullValue(W));
1060         }
1061         case ICmpInst::ICMP_SGE: {
1062           APInt SMin(CR.getSignedMin());
1063           if (SMin.isMinSignedValue())
1064             return ConstantRange(W);
1065           return ConstantRange(SMin, APInt::getSignedMinValue(W));
1066         }
1067       }
1068     }
1069
1070 #ifndef NDEBUG
1071     bool isCanonical(Value *V, DomTreeDFS::Node *Subtree) {
1072       return V == VN.canonicalize(V, Subtree);
1073     }
1074 #endif
1075
1076   public:
1077
1078     ValueRanges(ValueNumbering &VN, TargetData *TD) : VN(VN), TD(TD) {}
1079
1080 #ifndef NDEBUG
1081     virtual ~ValueRanges() {}
1082
1083     virtual void dump() const {
1084       dump(*cerr.stream());
1085     }
1086
1087     void dump(std::ostream &os) const {
1088       for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1089         os << (i+1) << " = ";
1090         Ranges[i].dump(os);
1091         os << "\n";
1092       }
1093     }
1094 #endif
1095
1096     /// range - looks up the ConstantRange associated with a value number.
1097     ConstantRange range(unsigned n, DomTreeDFS::Node *Subtree) {
1098       assert(VN.value(n)); // performs range checks
1099
1100       if (n <= Ranges.size()) {
1101         ScopedRange::iterator I = Ranges[n-1].find(Subtree);
1102         if (I != Ranges[n-1].end()) return I->second;
1103       }
1104
1105       Value *V = VN.value(n);
1106       ConstantRange CR = range(V);
1107       return CR;
1108     }
1109
1110     /// range - determine a range from a Value without performing any lookups.
1111     ConstantRange range(Value *V) const {
1112       if (ConstantInt *C = dyn_cast<ConstantInt>(V))
1113         return ConstantRange(C->getValue());
1114       else if (isa<ConstantPointerNull>(V))
1115         return ConstantRange(APInt::getNullValue(typeToWidth(V->getType())));
1116       else
1117         return ConstantRange(typeToWidth(V->getType()));
1118     }
1119
1120     // typeToWidth - returns the number of bits necessary to store a value of
1121     // this type, or zero if unknown.
1122     uint32_t typeToWidth(const Type *Ty) const {
1123       if (TD)
1124         return TD->getTypeSizeInBits(Ty);
1125       else
1126         return Ty->getPrimitiveSizeInBits();
1127     }
1128
1129     static bool isRelatedBy(const ConstantRange &CR1, const ConstantRange &CR2,
1130                             LatticeVal LV) {
1131       switch (LV) {
1132       default: assert(!"Impossible lattice value!");
1133       case NE:
1134         return CR1.maximalIntersectWith(CR2).isEmptySet();
1135       case ULT:
1136         return CR1.getUnsignedMax().ult(CR2.getUnsignedMin());
1137       case ULE:
1138         return CR1.getUnsignedMax().ule(CR2.getUnsignedMin());
1139       case UGT:
1140         return CR1.getUnsignedMin().ugt(CR2.getUnsignedMax());
1141       case UGE:
1142         return CR1.getUnsignedMin().uge(CR2.getUnsignedMax());
1143       case SLT:
1144         return CR1.getSignedMax().slt(CR2.getSignedMin());
1145       case SLE:
1146         return CR1.getSignedMax().sle(CR2.getSignedMin());
1147       case SGT:
1148         return CR1.getSignedMin().sgt(CR2.getSignedMax());
1149       case SGE:
1150         return CR1.getSignedMin().sge(CR2.getSignedMax());
1151       case LT:
1152         return CR1.getUnsignedMax().ult(CR2.getUnsignedMin()) &&
1153                CR1.getSignedMax().slt(CR2.getUnsignedMin());
1154       case LE:
1155         return CR1.getUnsignedMax().ule(CR2.getUnsignedMin()) &&
1156                CR1.getSignedMax().sle(CR2.getUnsignedMin());
1157       case GT:
1158         return CR1.getUnsignedMin().ugt(CR2.getUnsignedMax()) &&
1159                CR1.getSignedMin().sgt(CR2.getSignedMax());
1160       case GE:
1161         return CR1.getUnsignedMin().uge(CR2.getUnsignedMax()) &&
1162                CR1.getSignedMin().sge(CR2.getSignedMax());
1163       case SLTUGT:
1164         return CR1.getSignedMax().slt(CR2.getSignedMin()) &&
1165                CR1.getUnsignedMin().ugt(CR2.getUnsignedMax());
1166       case SLEUGE:
1167         return CR1.getSignedMax().sle(CR2.getSignedMin()) &&
1168                CR1.getUnsignedMin().uge(CR2.getUnsignedMax());
1169       case SGTULT:
1170         return CR1.getSignedMin().sgt(CR2.getSignedMax()) &&
1171                CR1.getUnsignedMax().ult(CR2.getUnsignedMin());
1172       case SGEULE:
1173         return CR1.getSignedMin().sge(CR2.getSignedMax()) &&
1174                CR1.getUnsignedMax().ule(CR2.getUnsignedMin());
1175       }
1176     }
1177
1178     bool isRelatedBy(unsigned n1, unsigned n2, DomTreeDFS::Node *Subtree,
1179                      LatticeVal LV) {
1180       ConstantRange CR1 = range(n1, Subtree);
1181       ConstantRange CR2 = range(n2, Subtree);
1182
1183       // True iff all values in CR1 are LV to all values in CR2.
1184       return isRelatedBy(CR1, CR2, LV);
1185     }
1186
1187     void addToWorklist(Value *V, Constant *C, ICmpInst::Predicate Pred,
1188                        VRPSolver *VRP);
1189     void markBlock(VRPSolver *VRP);
1190
1191     void mergeInto(Value **I, unsigned n, unsigned New,
1192                    DomTreeDFS::Node *Subtree, VRPSolver *VRP) {
1193       ConstantRange CR_New = range(New, Subtree);
1194       ConstantRange Merged = CR_New;
1195
1196       for (; n != 0; ++I, --n) {
1197         unsigned i = VN.valueNumber(*I, Subtree);
1198         ConstantRange CR_Kill = i ? range(i, Subtree) : range(*I);
1199         if (CR_Kill.isFullSet()) continue;
1200         Merged = Merged.maximalIntersectWith(CR_Kill);
1201       }
1202
1203       if (Merged.isFullSet() || Merged == CR_New) return;
1204
1205       applyRange(New, Merged, Subtree, VRP);
1206     }
1207
1208     void applyRange(unsigned n, const ConstantRange &CR,
1209                     DomTreeDFS::Node *Subtree, VRPSolver *VRP) {
1210       ConstantRange Merged = CR.maximalIntersectWith(range(n, Subtree));
1211       if (Merged.isEmptySet()) {
1212         markBlock(VRP);
1213         return;
1214       }
1215
1216       if (const APInt *I = Merged.getSingleElement()) {
1217         Value *V = VN.value(n); // XXX: redesign worklist.
1218         const Type *Ty = V->getType();
1219         if (Ty->isInteger()) {
1220           addToWorklist(V, ConstantInt::get(*I), ICmpInst::ICMP_EQ, VRP);
1221           return;
1222         } else if (const PointerType *PTy = dyn_cast<PointerType>(Ty)) {
1223           assert(*I == 0 && "Pointer is null but not zero?");
1224           addToWorklist(V, ConstantPointerNull::get(PTy),
1225                         ICmpInst::ICMP_EQ, VRP);
1226           return;
1227         }
1228       }
1229
1230       update(n, Merged, Subtree);
1231     }
1232
1233     void addNotEquals(unsigned n1, unsigned n2, DomTreeDFS::Node *Subtree,
1234                       VRPSolver *VRP) {
1235       ConstantRange CR1 = range(n1, Subtree);
1236       ConstantRange CR2 = range(n2, Subtree);
1237
1238       uint32_t W = CR1.getBitWidth();
1239
1240       if (const APInt *I = CR1.getSingleElement()) {
1241         if (CR2.isFullSet()) {
1242           ConstantRange NewCR2(CR1.getUpper(), CR1.getLower());
1243           applyRange(n2, NewCR2, Subtree, VRP);
1244         } else if (*I == CR2.getLower()) {
1245           APInt NewLower(CR2.getLower() + 1),
1246                 NewUpper(CR2.getUpper());
1247           if (NewLower == NewUpper)
1248             NewLower = NewUpper = APInt::getMinValue(W);
1249
1250           ConstantRange NewCR2(NewLower, NewUpper);
1251           applyRange(n2, NewCR2, Subtree, VRP);
1252         } else if (*I == CR2.getUpper() - 1) {
1253           APInt NewLower(CR2.getLower()),
1254                 NewUpper(CR2.getUpper() - 1);
1255           if (NewLower == NewUpper)
1256             NewLower = NewUpper = APInt::getMinValue(W);
1257
1258           ConstantRange NewCR2(NewLower, NewUpper);
1259           applyRange(n2, NewCR2, Subtree, VRP);
1260         }
1261       }
1262
1263       if (const APInt *I = CR2.getSingleElement()) {
1264         if (CR1.isFullSet()) {
1265           ConstantRange NewCR1(CR2.getUpper(), CR2.getLower());
1266           applyRange(n1, NewCR1, Subtree, VRP);
1267         } else if (*I == CR1.getLower()) {
1268           APInt NewLower(CR1.getLower() + 1),
1269                 NewUpper(CR1.getUpper());
1270           if (NewLower == NewUpper)
1271             NewLower = NewUpper = APInt::getMinValue(W);
1272
1273           ConstantRange NewCR1(NewLower, NewUpper);
1274           applyRange(n1, NewCR1, Subtree, VRP);
1275         } else if (*I == CR1.getUpper() - 1) {
1276           APInt NewLower(CR1.getLower()),
1277                 NewUpper(CR1.getUpper() - 1);
1278           if (NewLower == NewUpper)
1279             NewLower = NewUpper = APInt::getMinValue(W);
1280
1281           ConstantRange NewCR1(NewLower, NewUpper);
1282           applyRange(n1, NewCR1, Subtree, VRP);
1283         }
1284       }
1285     }
1286
1287     void addInequality(unsigned n1, unsigned n2, DomTreeDFS::Node *Subtree,
1288                        LatticeVal LV, VRPSolver *VRP) {
1289       assert(!isRelatedBy(n1, n2, Subtree, LV) && "Asked to do useless work.");
1290
1291       if (LV == NE) {
1292         addNotEquals(n1, n2, Subtree, VRP);
1293         return;
1294       }
1295
1296       ConstantRange CR1 = range(n1, Subtree);
1297       ConstantRange CR2 = range(n2, Subtree);
1298
1299       if (!CR1.isSingleElement()) {
1300         ConstantRange NewCR1 = CR1.maximalIntersectWith(create(LV, CR2));
1301         if (NewCR1 != CR1)
1302           applyRange(n1, NewCR1, Subtree, VRP);
1303       }
1304
1305       if (!CR2.isSingleElement()) {
1306         ConstantRange NewCR2 = CR2.maximalIntersectWith(
1307                                        create(reversePredicate(LV), CR1));
1308         if (NewCR2 != CR2)
1309           applyRange(n2, NewCR2, Subtree, VRP);
1310       }
1311     }
1312   };
1313
1314   /// UnreachableBlocks keeps tracks of blocks that are for one reason or
1315   /// another discovered to be unreachable. This is used to cull the graph when
1316   /// analyzing instructions, and to mark blocks with the "unreachable"
1317   /// terminator instruction after the function has executed.
1318   class VISIBILITY_HIDDEN UnreachableBlocks {
1319   private:
1320     std::vector<BasicBlock *> DeadBlocks;
1321
1322   public:
1323     /// mark - mark a block as dead
1324     void mark(BasicBlock *BB) {
1325       std::vector<BasicBlock *>::iterator E = DeadBlocks.end();
1326       std::vector<BasicBlock *>::iterator I =
1327         std::lower_bound(DeadBlocks.begin(), E, BB);
1328
1329       if (I == E || *I != BB) DeadBlocks.insert(I, BB);
1330     }
1331
1332     /// isDead - returns whether a block is known to be dead already
1333     bool isDead(BasicBlock *BB) {
1334       std::vector<BasicBlock *>::iterator E = DeadBlocks.end();
1335       std::vector<BasicBlock *>::iterator I =
1336         std::lower_bound(DeadBlocks.begin(), E, BB);
1337
1338       return I != E && *I == BB;
1339     }
1340
1341     /// kill - replace the dead blocks' terminator with an UnreachableInst.
1342     bool kill() {
1343       bool modified = false;
1344       for (std::vector<BasicBlock *>::iterator I = DeadBlocks.begin(),
1345            E = DeadBlocks.end(); I != E; ++I) {
1346         BasicBlock *BB = *I;
1347
1348         DOUT << "unreachable block: " << BB->getName() << "\n";
1349
1350         for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
1351              SI != SE; ++SI) {
1352           BasicBlock *Succ = *SI;
1353           Succ->removePredecessor(BB);
1354         }
1355
1356         TerminatorInst *TI = BB->getTerminator();
1357         TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
1358         TI->eraseFromParent();
1359         new UnreachableInst(BB);
1360         ++NumBlocks;
1361         modified = true;
1362       }
1363       DeadBlocks.clear();
1364       return modified;
1365     }
1366   };
1367
1368   /// VRPSolver keeps track of how changes to one variable affect other
1369   /// variables, and forwards changes along to the InequalityGraph. It
1370   /// also maintains the correct choice for "canonical" in the IG.
1371   /// @brief VRPSolver calculates inferences from a new relationship.
1372   class VISIBILITY_HIDDEN VRPSolver {
1373   private:
1374     friend class ValueRanges;
1375
1376     struct Operation {
1377       Value *LHS, *RHS;
1378       ICmpInst::Predicate Op;
1379
1380       BasicBlock *ContextBB; // XXX use a DomTreeDFS::Node instead
1381       Instruction *ContextInst;
1382     };
1383     std::deque<Operation> WorkList;
1384
1385     ValueNumbering &VN;
1386     InequalityGraph &IG;
1387     UnreachableBlocks &UB;
1388     ValueRanges &VR;
1389     DomTreeDFS *DTDFS;
1390     DomTreeDFS::Node *Top;
1391     BasicBlock *TopBB;
1392     Instruction *TopInst;
1393     bool &modified;
1394
1395     typedef InequalityGraph::Node Node;
1396
1397     // below - true if the Instruction is dominated by the current context
1398     // block or instruction
1399     bool below(Instruction *I) {
1400       BasicBlock *BB = I->getParent();
1401       if (TopInst && TopInst->getParent() == BB) {
1402         if (isa<TerminatorInst>(TopInst)) return false;
1403         if (isa<TerminatorInst>(I)) return true;
1404         if ( isa<PHINode>(TopInst) && !isa<PHINode>(I)) return true;
1405         if (!isa<PHINode>(TopInst) &&  isa<PHINode>(I)) return false;
1406
1407         for (BasicBlock::const_iterator Iter = BB->begin(), E = BB->end();
1408              Iter != E; ++Iter) {
1409           if (&*Iter == TopInst) return true;
1410           else if (&*Iter == I) return false;
1411         }
1412         assert(!"Instructions not found in parent BasicBlock?");
1413       } else {
1414         DomTreeDFS::Node *Node = DTDFS->getNodeForBlock(BB);
1415         if (!Node) return false;
1416         return Top->dominates(Node);
1417       }
1418       return false; // Not reached
1419     }
1420
1421     // aboveOrBelow - true if the Instruction either dominates or is dominated
1422     // by the current context block or instruction
1423     bool aboveOrBelow(Instruction *I) {
1424       BasicBlock *BB = I->getParent();
1425       DomTreeDFS::Node *Node = DTDFS->getNodeForBlock(BB);
1426       if (!Node) return false;
1427
1428       return Top == Node || Top->dominates(Node) || Node->dominates(Top);
1429     }
1430
1431     bool makeEqual(Value *V1, Value *V2) {
1432       DOUT << "makeEqual(" << *V1 << ", " << *V2 << ")\n";
1433       DOUT << "context is ";
1434       if (TopInst) DOUT << "I: " << *TopInst << "\n";
1435       else DOUT << "BB: " << TopBB->getName()
1436                 << "(" << Top->getDFSNumIn() << ")\n";
1437
1438       assert(V1->getType() == V2->getType() &&
1439              "Can't make two values with different types equal.");
1440
1441       if (V1 == V2) return true;
1442
1443       if (isa<Constant>(V1) && isa<Constant>(V2))
1444         return false;
1445
1446       unsigned n1 = VN.valueNumber(V1, Top), n2 = VN.valueNumber(V2, Top);
1447
1448       if (n1 && n2) {
1449         if (n1 == n2) return true;
1450         if (IG.isRelatedBy(n1, n2, Top, NE)) return false;
1451       }
1452
1453       if (n1) assert(V1 == VN.value(n1) && "Value isn't canonical.");
1454       if (n2) assert(V2 == VN.value(n2) && "Value isn't canonical.");
1455
1456       assert(!VN.compare(V2, V1) && "Please order parameters to makeEqual.");
1457
1458       assert(!isa<Constant>(V2) && "Tried to remove a constant.");
1459
1460       SetVector<unsigned> Remove;
1461       if (n2) Remove.insert(n2);
1462
1463       if (n1 && n2) {
1464         // Suppose we're being told that %x == %y, and %x <= %z and %y >= %z.
1465         // We can't just merge %x and %y because the relationship with %z would
1466         // be EQ and that's invalid. What we're doing is looking for any nodes
1467         // %z such that %x <= %z and %y >= %z, and vice versa.
1468
1469         Node::iterator end = IG.node(n2)->end();
1470
1471         // Find the intersection between N1 and N2 which is dominated by
1472         // Top. If we find %x where N1 <= %x <= N2 (or >=) then add %x to
1473         // Remove.
1474         for (Node::iterator I = IG.node(n1)->begin(), E = IG.node(n1)->end();
1475              I != E; ++I) {
1476           if (!(I->LV & EQ_BIT) || !Top->DominatedBy(I->Subtree)) continue;
1477
1478           unsigned ILV_s = I->LV & (SLT_BIT|SGT_BIT);
1479           unsigned ILV_u = I->LV & (ULT_BIT|UGT_BIT);
1480           Node::iterator NI = IG.node(n2)->find(I->To, Top);
1481           if (NI != end) {
1482             LatticeVal NILV = reversePredicate(NI->LV);
1483             unsigned NILV_s = NILV & (SLT_BIT|SGT_BIT);
1484             unsigned NILV_u = NILV & (ULT_BIT|UGT_BIT);
1485
1486             if ((ILV_s != (SLT_BIT|SGT_BIT) && ILV_s == NILV_s) ||
1487                 (ILV_u != (ULT_BIT|UGT_BIT) && ILV_u == NILV_u))
1488               Remove.insert(I->To);
1489           }
1490         }
1491
1492         // See if one of the nodes about to be removed is actually a better
1493         // canonical choice than n1.
1494         unsigned orig_n1 = n1;
1495         SetVector<unsigned>::iterator DontRemove = Remove.end();
1496         for (SetVector<unsigned>::iterator I = Remove.begin()+1 /* skip n2 */,
1497              E = Remove.end(); I != E; ++I) {
1498           unsigned n = *I;
1499           Value *V = VN.value(n);
1500           if (VN.compare(V, V1)) {
1501             V1 = V;
1502             n1 = n;
1503             DontRemove = I;
1504           }
1505         }
1506         if (DontRemove != Remove.end()) {
1507           unsigned n = *DontRemove;
1508           Remove.remove(n);
1509           Remove.insert(orig_n1);
1510         }
1511       }
1512
1513       // We'd like to allow makeEqual on two values to perform a simple
1514       // substitution without creating nodes in the IG whenever possible.
1515       //
1516       // The first iteration through this loop operates on V2 before going
1517       // through the Remove list and operating on those too. If all of the
1518       // iterations performed simple replacements then we exit early.
1519       bool mergeIGNode = false;
1520       unsigned i = 0;
1521       for (Value *R = V2; i == 0 || i < Remove.size(); ++i) {
1522         if (i) R = VN.value(Remove[i]); // skip n2.
1523
1524         // Try to replace the whole instruction. If we can, we're done.
1525         Instruction *I2 = dyn_cast<Instruction>(R);
1526         if (I2 && below(I2)) {
1527           std::vector<Instruction *> ToNotify;
1528           for (Value::use_iterator UI = R->use_begin(), UE = R->use_end();
1529                UI != UE;) {
1530             Use &TheUse = UI.getUse();
1531             ++UI;
1532             if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser()))
1533               ToNotify.push_back(I);
1534           }
1535
1536           DOUT << "Simply removing " << *I2
1537                << ", replacing with " << *V1 << "\n";
1538           I2->replaceAllUsesWith(V1);
1539           // leave it dead; it'll get erased later.
1540           ++NumInstruction;
1541           modified = true;
1542
1543           for (std::vector<Instruction *>::iterator II = ToNotify.begin(),
1544                IE = ToNotify.end(); II != IE; ++II) {
1545             opsToDef(*II);
1546           }
1547
1548           continue;
1549         }
1550
1551         // Otherwise, replace all dominated uses.
1552         for (Value::use_iterator UI = R->use_begin(), UE = R->use_end();
1553              UI != UE;) {
1554           Use &TheUse = UI.getUse();
1555           ++UI;
1556           if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
1557             if (below(I)) {
1558               TheUse.set(V1);
1559               modified = true;
1560               ++NumVarsReplaced;
1561               opsToDef(I);
1562             }
1563           }
1564         }
1565
1566         // If that killed the instruction, stop here.
1567         if (I2 && isInstructionTriviallyDead(I2)) {
1568           DOUT << "Killed all uses of " << *I2
1569                << ", replacing with " << *V1 << "\n";
1570           continue;
1571         }
1572
1573         // If we make it to here, then we will need to create a node for N1.
1574         // Otherwise, we can skip out early!
1575         mergeIGNode = true;
1576       }
1577
1578       if (!isa<Constant>(V1)) {
1579         if (Remove.empty()) {
1580           VR.mergeInto(&V2, 1, VN.getOrInsertVN(V1, Top), Top, this);
1581         } else {
1582           std::vector<Value*> RemoveVals;
1583           RemoveVals.reserve(Remove.size());
1584
1585           for (SetVector<unsigned>::iterator I = Remove.begin(),
1586                E = Remove.end(); I != E; ++I) {
1587             Value *V = VN.value(*I);
1588             if (!V->use_empty())
1589               RemoveVals.push_back(V);
1590           }
1591           VR.mergeInto(&RemoveVals[0], RemoveVals.size(),
1592                        VN.getOrInsertVN(V1, Top), Top, this);
1593         }
1594       }
1595
1596       if (mergeIGNode) {
1597         // Create N1.
1598         if (!n1) n1 = VN.getOrInsertVN(V1, Top);
1599         IG.node(n1); // Ensure that IG.Nodes won't get resized
1600
1601         // Migrate relationships from removed nodes to N1.
1602         for (SetVector<unsigned>::iterator I = Remove.begin(), E = Remove.end();
1603              I != E; ++I) {
1604           unsigned n = *I;
1605           for (Node::iterator NI = IG.node(n)->begin(), NE = IG.node(n)->end();
1606                NI != NE; ++NI) {
1607             if (NI->Subtree->DominatedBy(Top)) {
1608               if (NI->To == n1) {
1609                 assert((NI->LV & EQ_BIT) && "Node inequal to itself.");
1610                 continue;
1611               }
1612               if (Remove.count(NI->To))
1613                 continue;
1614
1615               IG.node(NI->To)->update(n1, reversePredicate(NI->LV), Top);
1616               IG.node(n1)->update(NI->To, NI->LV, Top);
1617             }
1618           }
1619         }
1620
1621         // Point V2 (and all items in Remove) to N1.
1622         if (!n2)
1623           VN.addEquality(n1, V2, Top);
1624         else {
1625           for (SetVector<unsigned>::iterator I = Remove.begin(),
1626                E = Remove.end(); I != E; ++I) {
1627             VN.addEquality(n1, VN.value(*I), Top);
1628           }
1629         }
1630
1631         // If !Remove.empty() then V2 = Remove[0]->getValue().
1632         // Even when Remove is empty, we still want to process V2.
1633         i = 0;
1634         for (Value *R = V2; i == 0 || i < Remove.size(); ++i) {
1635           if (i) R = VN.value(Remove[i]); // skip n2.
1636
1637           if (Instruction *I2 = dyn_cast<Instruction>(R)) {
1638             if (aboveOrBelow(I2))
1639             defToOps(I2);
1640           }
1641           for (Value::use_iterator UI = V2->use_begin(), UE = V2->use_end();
1642                UI != UE;) {
1643             Use &TheUse = UI.getUse();
1644             ++UI;
1645             if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
1646               if (aboveOrBelow(I))
1647                 opsToDef(I);
1648             }
1649           }
1650         }
1651       }
1652
1653       // re-opsToDef all dominated users of V1.
1654       if (Instruction *I = dyn_cast<Instruction>(V1)) {
1655         for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
1656              UI != UE;) {
1657           Use &TheUse = UI.getUse();
1658           ++UI;
1659           Value *V = TheUse.getUser();
1660           if (!V->use_empty()) {
1661             if (Instruction *Inst = dyn_cast<Instruction>(V)) {
1662               if (aboveOrBelow(Inst))
1663                 opsToDef(Inst);
1664             }
1665           }
1666         }
1667       }
1668
1669       return true;
1670     }
1671
1672     /// cmpInstToLattice - converts an CmpInst::Predicate to lattice value
1673     /// Requires that the lattice value be valid; does not accept ICMP_EQ.
1674     static LatticeVal cmpInstToLattice(ICmpInst::Predicate Pred) {
1675       switch (Pred) {
1676         case ICmpInst::ICMP_EQ:
1677           assert(!"No matching lattice value.");
1678           return static_cast<LatticeVal>(EQ_BIT);
1679         default:
1680           assert(!"Invalid 'icmp' predicate.");
1681         case ICmpInst::ICMP_NE:
1682           return NE;
1683         case ICmpInst::ICMP_UGT:
1684           return UGT;
1685         case ICmpInst::ICMP_UGE:
1686           return UGE;
1687         case ICmpInst::ICMP_ULT:
1688           return ULT;
1689         case ICmpInst::ICMP_ULE:
1690           return ULE;
1691         case ICmpInst::ICMP_SGT:
1692           return SGT;
1693         case ICmpInst::ICMP_SGE:
1694           return SGE;
1695         case ICmpInst::ICMP_SLT:
1696           return SLT;
1697         case ICmpInst::ICMP_SLE:
1698           return SLE;
1699       }
1700     }
1701
1702   public:
1703     VRPSolver(ValueNumbering &VN, InequalityGraph &IG, UnreachableBlocks &UB,
1704               ValueRanges &VR, DomTreeDFS *DTDFS, bool &modified,
1705               BasicBlock *TopBB)
1706       : VN(VN),
1707         IG(IG),
1708         UB(UB),
1709         VR(VR),
1710         DTDFS(DTDFS),
1711         Top(DTDFS->getNodeForBlock(TopBB)),
1712         TopBB(TopBB),
1713         TopInst(NULL),
1714         modified(modified)
1715     {
1716       assert(Top && "VRPSolver created for unreachable basic block.");
1717     }
1718
1719     VRPSolver(ValueNumbering &VN, InequalityGraph &IG, UnreachableBlocks &UB,
1720               ValueRanges &VR, DomTreeDFS *DTDFS, bool &modified,
1721               Instruction *TopInst)
1722       : VN(VN),
1723         IG(IG),
1724         UB(UB),
1725         VR(VR),
1726         DTDFS(DTDFS),
1727         Top(DTDFS->getNodeForBlock(TopInst->getParent())),
1728         TopBB(TopInst->getParent()),
1729         TopInst(TopInst),
1730         modified(modified)
1731     {
1732       assert(Top && "VRPSolver created for unreachable basic block.");
1733       assert(Top->getBlock() == TopInst->getParent() && "Context mismatch.");
1734     }
1735
1736     bool isRelatedBy(Value *V1, Value *V2, ICmpInst::Predicate Pred) const {
1737       if (Constant *C1 = dyn_cast<Constant>(V1))
1738         if (Constant *C2 = dyn_cast<Constant>(V2))
1739           return ConstantExpr::getCompare(Pred, C1, C2) ==
1740                  ConstantInt::getTrue();
1741
1742       unsigned n1 = VN.valueNumber(V1, Top);
1743       unsigned n2 = VN.valueNumber(V2, Top);
1744
1745       if (n1 && n2) {
1746         if (n1 == n2) return Pred == ICmpInst::ICMP_EQ ||
1747                              Pred == ICmpInst::ICMP_ULE ||
1748                              Pred == ICmpInst::ICMP_UGE ||
1749                              Pred == ICmpInst::ICMP_SLE ||
1750                              Pred == ICmpInst::ICMP_SGE;
1751         if (Pred == ICmpInst::ICMP_EQ) return false;
1752         if (IG.isRelatedBy(n1, n2, Top, cmpInstToLattice(Pred))) return true;
1753         if (VR.isRelatedBy(n1, n2, Top, cmpInstToLattice(Pred))) return true;
1754       }
1755
1756       if ((n1 && !n2 && isa<Constant>(V2)) ||
1757           (n2 && !n1 && isa<Constant>(V1))) {
1758         ConstantRange CR1 = n1 ? VR.range(n1, Top) : VR.range(V1);
1759         ConstantRange CR2 = n2 ? VR.range(n2, Top) : VR.range(V2);
1760
1761         if (Pred == ICmpInst::ICMP_EQ)
1762           return CR1.isSingleElement() &&
1763                  CR1.getSingleElement() == CR2.getSingleElement();
1764
1765         return VR.isRelatedBy(CR1, CR2, cmpInstToLattice(Pred));
1766       }
1767       if (Pred == ICmpInst::ICMP_EQ) return V1 == V2;
1768       return false;
1769     }
1770
1771     /// add - adds a new property to the work queue
1772     void add(Value *V1, Value *V2, ICmpInst::Predicate Pred,
1773              Instruction *I = NULL) {
1774       DOUT << "adding " << *V1 << " " << Pred << " " << *V2;
1775       if (I) DOUT << " context: " << *I;
1776       else DOUT << " default context (" << Top->getDFSNumIn() << ")";
1777       DOUT << "\n";
1778
1779       assert(V1->getType() == V2->getType() &&
1780              "Can't relate two values with different types.");
1781
1782       WorkList.push_back(Operation());
1783       Operation &O = WorkList.back();
1784       O.LHS = V1, O.RHS = V2, O.Op = Pred, O.ContextInst = I;
1785       O.ContextBB = I ? I->getParent() : TopBB;
1786     }
1787
1788     /// defToOps - Given an instruction definition that we've learned something
1789     /// new about, find any new relationships between its operands.
1790     void defToOps(Instruction *I) {
1791       Instruction *NewContext = below(I) ? I : TopInst;
1792       Value *Canonical = VN.canonicalize(I, Top);
1793
1794       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
1795         const Type *Ty = BO->getType();
1796         assert(!Ty->isFPOrFPVector() && "Float in work queue!");
1797
1798         Value *Op0 = VN.canonicalize(BO->getOperand(0), Top);
1799         Value *Op1 = VN.canonicalize(BO->getOperand(1), Top);
1800
1801         // TODO: "and i32 -1, %x" EQ %y then %x EQ %y.
1802
1803         switch (BO->getOpcode()) {
1804           case Instruction::And: {
1805             // "and i32 %a, %b" EQ -1 then %a EQ -1 and %b EQ -1
1806             ConstantInt *CI = ConstantInt::getAllOnesValue(Ty);
1807             if (Canonical == CI) {
1808               add(CI, Op0, ICmpInst::ICMP_EQ, NewContext);
1809               add(CI, Op1, ICmpInst::ICMP_EQ, NewContext);
1810             }
1811           } break;
1812           case Instruction::Or: {
1813             // "or i32 %a, %b" EQ 0 then %a EQ 0 and %b EQ 0
1814             Constant *Zero = Constant::getNullValue(Ty);
1815             if (Canonical == Zero) {
1816               add(Zero, Op0, ICmpInst::ICMP_EQ, NewContext);
1817               add(Zero, Op1, ICmpInst::ICMP_EQ, NewContext);
1818             }
1819           } break;
1820           case Instruction::Xor: {
1821             // "xor i32 %c, %a" EQ %b then %a EQ %c ^ %b
1822             // "xor i32 %c, %a" EQ %c then %a EQ 0
1823             // "xor i32 %c, %a" NE %c then %a NE 0
1824             // Repeat the above, with order of operands reversed.
1825             Value *LHS = Op0;
1826             Value *RHS = Op1;
1827             if (!isa<Constant>(LHS)) std::swap(LHS, RHS);
1828
1829             if (ConstantInt *CI = dyn_cast<ConstantInt>(Canonical)) {
1830               if (ConstantInt *Arg = dyn_cast<ConstantInt>(LHS)) {
1831                 add(RHS, ConstantInt::get(CI->getValue() ^ Arg->getValue()),
1832                     ICmpInst::ICMP_EQ, NewContext);
1833               }
1834             }
1835             if (Canonical == LHS) {
1836               if (isa<ConstantInt>(Canonical))
1837                 add(RHS, Constant::getNullValue(Ty), ICmpInst::ICMP_EQ,
1838                     NewContext);
1839             } else if (isRelatedBy(LHS, Canonical, ICmpInst::ICMP_NE)) {
1840               add(RHS, Constant::getNullValue(Ty), ICmpInst::ICMP_NE,
1841                   NewContext);
1842             }
1843           } break;
1844           default:
1845             break;
1846         }
1847       } else if (ICmpInst *IC = dyn_cast<ICmpInst>(I)) {
1848         // "icmp ult i32 %a, %y" EQ true then %a u< y
1849         // etc.
1850
1851         if (Canonical == ConstantInt::getTrue()) {
1852           add(IC->getOperand(0), IC->getOperand(1), IC->getPredicate(),
1853               NewContext);
1854         } else if (Canonical == ConstantInt::getFalse()) {
1855           add(IC->getOperand(0), IC->getOperand(1),
1856               ICmpInst::getInversePredicate(IC->getPredicate()), NewContext);
1857         }
1858       } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
1859         if (I->getType()->isFPOrFPVector()) return;
1860
1861         // Given: "%a = select i1 %x, i32 %b, i32 %c"
1862         // %a EQ %b and %b NE %c then %x EQ true
1863         // %a EQ %c and %b NE %c then %x EQ false
1864
1865         Value *True  = SI->getTrueValue();
1866         Value *False = SI->getFalseValue();
1867         if (isRelatedBy(True, False, ICmpInst::ICMP_NE)) {
1868           if (Canonical == VN.canonicalize(True, Top) ||
1869               isRelatedBy(Canonical, False, ICmpInst::ICMP_NE))
1870             add(SI->getCondition(), ConstantInt::getTrue(),
1871                 ICmpInst::ICMP_EQ, NewContext);
1872           else if (Canonical == VN.canonicalize(False, Top) ||
1873                    isRelatedBy(Canonical, True, ICmpInst::ICMP_NE))
1874             add(SI->getCondition(), ConstantInt::getFalse(),
1875                 ICmpInst::ICMP_EQ, NewContext);
1876         }
1877       } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
1878         for (GetElementPtrInst::op_iterator OI = GEPI->idx_begin(),
1879              OE = GEPI->idx_end(); OI != OE; ++OI) {
1880           ConstantInt *Op = dyn_cast<ConstantInt>(VN.canonicalize(*OI, Top));
1881           if (!Op || !Op->isZero()) return;
1882         }
1883         // TODO: The GEPI indices are all zero. Copy from definition to operand,
1884         // jumping the type plane as needed.
1885         if (isRelatedBy(GEPI, Constant::getNullValue(GEPI->getType()),
1886                         ICmpInst::ICMP_NE)) {
1887           Value *Ptr = GEPI->getPointerOperand();
1888           add(Ptr, Constant::getNullValue(Ptr->getType()), ICmpInst::ICMP_NE,
1889               NewContext);
1890         }
1891       } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
1892         const Type *SrcTy = CI->getSrcTy();
1893
1894         unsigned ci = VN.getOrInsertVN(CI, Top);
1895         uint32_t W = VR.typeToWidth(SrcTy);
1896         if (!W) return;
1897         ConstantRange CR = VR.range(ci, Top);
1898
1899         if (CR.isFullSet()) return;
1900
1901         switch (CI->getOpcode()) {
1902           default: break;
1903           case Instruction::ZExt:
1904           case Instruction::SExt:
1905             VR.applyRange(VN.getOrInsertVN(CI->getOperand(0), Top),
1906                           CR.truncate(W), Top, this);
1907             break;
1908           case Instruction::BitCast:
1909             VR.applyRange(VN.getOrInsertVN(CI->getOperand(0), Top),
1910                           CR, Top, this);
1911             break;
1912         }
1913       }
1914     }
1915
1916     /// opsToDef - A new relationship was discovered involving one of this
1917     /// instruction's operands. Find any new relationship involving the
1918     /// definition, or another operand.
1919     void opsToDef(Instruction *I) {
1920       Instruction *NewContext = below(I) ? I : TopInst;
1921
1922       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
1923         Value *Op0 = VN.canonicalize(BO->getOperand(0), Top);
1924         Value *Op1 = VN.canonicalize(BO->getOperand(1), Top);
1925
1926         if (ConstantInt *CI0 = dyn_cast<ConstantInt>(Op0))
1927           if (ConstantInt *CI1 = dyn_cast<ConstantInt>(Op1)) {
1928             add(BO, ConstantExpr::get(BO->getOpcode(), CI0, CI1),
1929                 ICmpInst::ICMP_EQ, NewContext);
1930             return;
1931           }
1932
1933         // "%y = and i1 true, %x" then %x EQ %y
1934         // "%y = or i1 false, %x" then %x EQ %y
1935         // "%x = add i32 %y, 0" then %x EQ %y
1936         // "%x = mul i32 %y, 0" then %x EQ 0
1937
1938         Instruction::BinaryOps Opcode = BO->getOpcode();
1939         const Type *Ty = BO->getType();
1940         assert(!Ty->isFPOrFPVector() && "Float in work queue!");
1941
1942         Constant *Zero = Constant::getNullValue(Ty);
1943         Constant *One = ConstantInt::get(Ty, 1);
1944         ConstantInt *AllOnes = ConstantInt::getAllOnesValue(Ty);
1945
1946         switch (Opcode) {
1947           default: break;
1948           case Instruction::LShr:
1949           case Instruction::AShr:
1950           case Instruction::Shl:
1951             if (Op1 == Zero) {
1952               add(BO, Op0, ICmpInst::ICMP_EQ, NewContext);
1953               return;
1954             }
1955             break;
1956           case Instruction::Sub:
1957             if (Op1 == Zero) {
1958               add(BO, Op0, ICmpInst::ICMP_EQ, NewContext);
1959               return;
1960             }
1961             if (ConstantInt *CI0 = dyn_cast<ConstantInt>(Op0)) {
1962               unsigned n_ci0 = VN.getOrInsertVN(Op1, Top);
1963               ConstantRange CR = VR.range(n_ci0, Top);
1964               if (!CR.isFullSet()) {
1965                 CR.subtract(CI0->getValue());
1966                 unsigned n_bo = VN.getOrInsertVN(BO, Top);
1967                 VR.applyRange(n_bo, CR, Top, this);
1968                 return;
1969               }
1970             }
1971             if (ConstantInt *CI1 = dyn_cast<ConstantInt>(Op1)) {
1972               unsigned n_ci1 = VN.getOrInsertVN(Op0, Top);
1973               ConstantRange CR = VR.range(n_ci1, Top);
1974               if (!CR.isFullSet()) {
1975                 CR.subtract(CI1->getValue());
1976                 unsigned n_bo = VN.getOrInsertVN(BO, Top);
1977                 VR.applyRange(n_bo, CR, Top, this);
1978                 return;
1979               }
1980             }
1981             break;
1982           case Instruction::Or:
1983             if (Op0 == AllOnes || Op1 == AllOnes) {
1984               add(BO, AllOnes, ICmpInst::ICMP_EQ, NewContext);
1985               return;
1986             }
1987             if (Op0 == Zero) {
1988               add(BO, Op1, ICmpInst::ICMP_EQ, NewContext);
1989               return;
1990             } else if (Op1 == Zero) {
1991               add(BO, Op0, ICmpInst::ICMP_EQ, NewContext);
1992               return;
1993             }
1994             break;
1995           case Instruction::Add:
1996             if (ConstantInt *CI0 = dyn_cast<ConstantInt>(Op0)) {
1997               unsigned n_ci0 = VN.getOrInsertVN(Op1, Top);
1998               ConstantRange CR = VR.range(n_ci0, Top);
1999               if (!CR.isFullSet()) {
2000                 CR.subtract(-CI0->getValue());
2001                 unsigned n_bo = VN.getOrInsertVN(BO, Top);
2002                 VR.applyRange(n_bo, CR, Top, this);
2003                 return;
2004               }
2005             }
2006             if (ConstantInt *CI1 = dyn_cast<ConstantInt>(Op1)) {
2007               unsigned n_ci1 = VN.getOrInsertVN(Op0, Top);
2008               ConstantRange CR = VR.range(n_ci1, Top);
2009               if (!CR.isFullSet()) {
2010                 CR.subtract(-CI1->getValue());
2011                 unsigned n_bo = VN.getOrInsertVN(BO, Top);
2012                 VR.applyRange(n_bo, CR, Top, this);
2013                 return;
2014               }
2015             }
2016             // fall-through
2017           case Instruction::Xor:
2018             if (Op0 == Zero) {
2019               add(BO, Op1, ICmpInst::ICMP_EQ, NewContext);
2020               return;
2021             } else if (Op1 == Zero) {
2022               add(BO, Op0, ICmpInst::ICMP_EQ, NewContext);
2023               return;
2024             }
2025             break;
2026           case Instruction::And:
2027             if (Op0 == AllOnes) {
2028               add(BO, Op1, ICmpInst::ICMP_EQ, NewContext);
2029               return;
2030             } else if (Op1 == AllOnes) {
2031               add(BO, Op0, ICmpInst::ICMP_EQ, NewContext);
2032               return;
2033             }
2034             if (Op0 == Zero || Op1 == Zero) {
2035               add(BO, Zero, ICmpInst::ICMP_EQ, NewContext);
2036               return;
2037             }
2038             break;
2039           case Instruction::Mul:
2040             if (Op0 == Zero || Op1 == Zero) {
2041               add(BO, Zero, ICmpInst::ICMP_EQ, NewContext);
2042               return;
2043             }
2044             if (Op0 == One) {
2045               add(BO, Op1, ICmpInst::ICMP_EQ, NewContext);
2046               return;
2047             } else if (Op1 == One) {
2048               add(BO, Op0, ICmpInst::ICMP_EQ, NewContext);
2049               return;
2050             }
2051             break;
2052         }
2053
2054         // "%x = add i32 %y, %z" and %x EQ %y then %z EQ 0
2055         // "%x = add i32 %y, %z" and %x EQ %z then %y EQ 0
2056         // "%x = shl i32 %y, %z" and %x EQ %y and %y NE 0 then %z EQ 0
2057         // "%x = udiv i32 %y, %z" and %x EQ %y and %y NE 0 then %z EQ 1
2058
2059         Value *Known = Op0, *Unknown = Op1,
2060               *TheBO = VN.canonicalize(BO, Top);
2061         if (Known != TheBO) std::swap(Known, Unknown);
2062         if (Known == TheBO) {
2063           switch (Opcode) {
2064             default: break;
2065             case Instruction::LShr:
2066             case Instruction::AShr:
2067             case Instruction::Shl:
2068               if (!isRelatedBy(Known, Zero, ICmpInst::ICMP_NE)) break;
2069               // otherwise, fall-through.
2070             case Instruction::Sub:
2071               if (Unknown == Op0) break;
2072               // otherwise, fall-through.
2073             case Instruction::Xor:
2074             case Instruction::Add:
2075               add(Unknown, Zero, ICmpInst::ICMP_EQ, NewContext);
2076               break;
2077             case Instruction::UDiv:
2078             case Instruction::SDiv:
2079               if (Unknown == Op1) break;
2080               if (isRelatedBy(Known, Zero, ICmpInst::ICMP_NE))
2081                 add(Unknown, One, ICmpInst::ICMP_EQ, NewContext);
2082               break;
2083           }
2084         }
2085
2086         // TODO: "%a = add i32 %b, 1" and %b > %z then %a >= %z.
2087
2088       } else if (ICmpInst *IC = dyn_cast<ICmpInst>(I)) {
2089         // "%a = icmp ult i32 %b, %c" and %b u<  %c then %a EQ true
2090         // "%a = icmp ult i32 %b, %c" and %b u>= %c then %a EQ false
2091         // etc.
2092
2093         Value *Op0 = VN.canonicalize(IC->getOperand(0), Top);
2094         Value *Op1 = VN.canonicalize(IC->getOperand(1), Top);
2095
2096         ICmpInst::Predicate Pred = IC->getPredicate();
2097         if (isRelatedBy(Op0, Op1, Pred))
2098           add(IC, ConstantInt::getTrue(), ICmpInst::ICMP_EQ, NewContext);
2099         else if (isRelatedBy(Op0, Op1, ICmpInst::getInversePredicate(Pred)))
2100           add(IC, ConstantInt::getFalse(), ICmpInst::ICMP_EQ, NewContext);
2101
2102       } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
2103         if (I->getType()->isFPOrFPVector()) return;
2104
2105         // Given: "%a = select i1 %x, i32 %b, i32 %c"
2106         // %x EQ true  then %a EQ %b
2107         // %x EQ false then %a EQ %c
2108         // %b EQ %c then %a EQ %b
2109
2110         Value *Canonical = VN.canonicalize(SI->getCondition(), Top);
2111         if (Canonical == ConstantInt::getTrue()) {
2112           add(SI, SI->getTrueValue(), ICmpInst::ICMP_EQ, NewContext);
2113         } else if (Canonical == ConstantInt::getFalse()) {
2114           add(SI, SI->getFalseValue(), ICmpInst::ICMP_EQ, NewContext);
2115         } else if (VN.canonicalize(SI->getTrueValue(), Top) ==
2116                    VN.canonicalize(SI->getFalseValue(), Top)) {
2117           add(SI, SI->getTrueValue(), ICmpInst::ICMP_EQ, NewContext);
2118         }
2119       } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
2120         const Type *DestTy = CI->getDestTy();
2121         if (DestTy->isFPOrFPVector()) return;
2122
2123         Value *Op = VN.canonicalize(CI->getOperand(0), Top);
2124         Instruction::CastOps Opcode = CI->getOpcode();
2125
2126         if (Constant *C = dyn_cast<Constant>(Op)) {
2127           add(CI, ConstantExpr::getCast(Opcode, C, DestTy),
2128               ICmpInst::ICMP_EQ, NewContext);
2129         }
2130
2131         uint32_t W = VR.typeToWidth(DestTy);
2132         unsigned ci = VN.getOrInsertVN(CI, Top);
2133         ConstantRange CR = VR.range(VN.getOrInsertVN(Op, Top), Top);
2134
2135         if (!CR.isFullSet()) {
2136           switch (Opcode) {
2137             default: break;
2138             case Instruction::ZExt:
2139               VR.applyRange(ci, CR.zeroExtend(W), Top, this);
2140               break;
2141             case Instruction::SExt:
2142               VR.applyRange(ci, CR.signExtend(W), Top, this);
2143               break;
2144             case Instruction::Trunc: {
2145               ConstantRange Result = CR.truncate(W);
2146               if (!Result.isFullSet())
2147                 VR.applyRange(ci, Result, Top, this);
2148             } break;
2149             case Instruction::BitCast:
2150               VR.applyRange(ci, CR, Top, this);
2151               break;
2152             // TODO: other casts?
2153           }
2154         }
2155       } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
2156         for (GetElementPtrInst::op_iterator OI = GEPI->idx_begin(),
2157              OE = GEPI->idx_end(); OI != OE; ++OI) {
2158           ConstantInt *Op = dyn_cast<ConstantInt>(VN.canonicalize(*OI, Top));
2159           if (!Op || !Op->isZero()) return;
2160         }
2161         // TODO: The GEPI indices are all zero. Copy from operand to definition,
2162         // jumping the type plane as needed.
2163         Value *Ptr = GEPI->getPointerOperand();
2164         if (isRelatedBy(Ptr, Constant::getNullValue(Ptr->getType()),
2165                         ICmpInst::ICMP_NE)) {
2166           add(GEPI, Constant::getNullValue(GEPI->getType()), ICmpInst::ICMP_NE,
2167               NewContext);
2168         }
2169       }
2170     }
2171
2172     /// solve - process the work queue
2173     void solve() {
2174       //DOUT << "WorkList entry, size: " << WorkList.size() << "\n";
2175       while (!WorkList.empty()) {
2176         //DOUT << "WorkList size: " << WorkList.size() << "\n";
2177
2178         Operation &O = WorkList.front();
2179         TopInst = O.ContextInst;
2180         TopBB = O.ContextBB;
2181         Top = DTDFS->getNodeForBlock(TopBB); // XXX move this into Context
2182
2183         O.LHS = VN.canonicalize(O.LHS, Top);
2184         O.RHS = VN.canonicalize(O.RHS, Top);
2185
2186         assert(O.LHS == VN.canonicalize(O.LHS, Top) && "Canonicalize isn't.");
2187         assert(O.RHS == VN.canonicalize(O.RHS, Top) && "Canonicalize isn't.");
2188
2189         DOUT << "solving " << *O.LHS << " " << O.Op << " " << *O.RHS;
2190         if (O.ContextInst) DOUT << " context inst: " << *O.ContextInst;
2191         else DOUT << " context block: " << O.ContextBB->getName();
2192         DOUT << "\n";
2193
2194         DEBUG(VN.dump());
2195         DEBUG(IG.dump());
2196         DEBUG(VR.dump());
2197
2198         // If they're both Constant, skip it. Check for contradiction and mark
2199         // the BB as unreachable if so.
2200         if (Constant *CI_L = dyn_cast<Constant>(O.LHS)) {
2201           if (Constant *CI_R = dyn_cast<Constant>(O.RHS)) {
2202             if (ConstantExpr::getCompare(O.Op, CI_L, CI_R) ==
2203                 ConstantInt::getFalse())
2204               UB.mark(TopBB);
2205
2206             WorkList.pop_front();
2207             continue;
2208           }
2209         }
2210
2211         if (VN.compare(O.LHS, O.RHS)) {
2212           std::swap(O.LHS, O.RHS);
2213           O.Op = ICmpInst::getSwappedPredicate(O.Op);
2214         }
2215
2216         if (O.Op == ICmpInst::ICMP_EQ) {
2217           if (!makeEqual(O.RHS, O.LHS))
2218             UB.mark(TopBB);
2219         } else {
2220           LatticeVal LV = cmpInstToLattice(O.Op);
2221
2222           if ((LV & EQ_BIT) &&
2223               isRelatedBy(O.LHS, O.RHS, ICmpInst::getSwappedPredicate(O.Op))) {
2224             if (!makeEqual(O.RHS, O.LHS))
2225               UB.mark(TopBB);
2226           } else {
2227             if (isRelatedBy(O.LHS, O.RHS, ICmpInst::getInversePredicate(O.Op))){
2228               UB.mark(TopBB);
2229               WorkList.pop_front();
2230               continue;
2231             }
2232
2233             unsigned n1 = VN.getOrInsertVN(O.LHS, Top);
2234             unsigned n2 = VN.getOrInsertVN(O.RHS, Top);
2235
2236             if (n1 == n2) {
2237               if (O.Op != ICmpInst::ICMP_UGE && O.Op != ICmpInst::ICMP_ULE &&
2238                   O.Op != ICmpInst::ICMP_SGE && O.Op != ICmpInst::ICMP_SLE)
2239                 UB.mark(TopBB);
2240
2241               WorkList.pop_front();
2242               continue;
2243             }
2244
2245             if (VR.isRelatedBy(n1, n2, Top, LV) ||
2246                 IG.isRelatedBy(n1, n2, Top, LV)) {
2247               WorkList.pop_front();
2248               continue;
2249             }
2250
2251             VR.addInequality(n1, n2, Top, LV, this);
2252             if ((!isa<ConstantInt>(O.RHS) && !isa<ConstantInt>(O.LHS)) ||
2253                 LV == NE)
2254               IG.addInequality(n1, n2, Top, LV);
2255
2256             if (Instruction *I1 = dyn_cast<Instruction>(O.LHS)) {
2257               if (aboveOrBelow(I1))
2258                 defToOps(I1);
2259             }
2260             if (isa<Instruction>(O.LHS) || isa<Argument>(O.LHS)) {
2261               for (Value::use_iterator UI = O.LHS->use_begin(),
2262                    UE = O.LHS->use_end(); UI != UE;) {
2263                 Use &TheUse = UI.getUse();
2264                 ++UI;
2265                 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
2266                   if (aboveOrBelow(I))
2267                     opsToDef(I);
2268                 }
2269               }
2270             }
2271             if (Instruction *I2 = dyn_cast<Instruction>(O.RHS)) {
2272               if (aboveOrBelow(I2))
2273               defToOps(I2);
2274             }
2275             if (isa<Instruction>(O.RHS) || isa<Argument>(O.RHS)) {
2276               for (Value::use_iterator UI = O.RHS->use_begin(),
2277                    UE = O.RHS->use_end(); UI != UE;) {
2278                 Use &TheUse = UI.getUse();
2279                 ++UI;
2280                 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
2281                   if (aboveOrBelow(I))
2282                     opsToDef(I);
2283                 }
2284               }
2285             }
2286           }
2287         }
2288         WorkList.pop_front();
2289       }
2290     }
2291   };
2292
2293   void ValueRanges::addToWorklist(Value *V, Constant *C,
2294                                   ICmpInst::Predicate Pred, VRPSolver *VRP) {
2295     VRP->add(V, C, Pred, VRP->TopInst);
2296   }
2297
2298   void ValueRanges::markBlock(VRPSolver *VRP) {
2299     VRP->UB.mark(VRP->TopBB);
2300   }
2301
2302   /// PredicateSimplifier - This class is a simplifier that replaces
2303   /// one equivalent variable with another. It also tracks what
2304   /// can't be equal and will solve setcc instructions when possible.
2305   /// @brief Root of the predicate simplifier optimization.
2306   class VISIBILITY_HIDDEN PredicateSimplifier : public FunctionPass {
2307     DomTreeDFS *DTDFS;
2308     bool modified;
2309     ValueNumbering *VN;
2310     InequalityGraph *IG;
2311     UnreachableBlocks UB;
2312     ValueRanges *VR;
2313
2314     std::vector<DomTreeDFS::Node *> WorkList;
2315
2316   public:
2317     static char ID; // Pass identification, replacement for typeid
2318     PredicateSimplifier() : FunctionPass(&ID) {}
2319
2320     bool runOnFunction(Function &F);
2321
2322     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
2323       AU.addRequiredID(BreakCriticalEdgesID);
2324       AU.addRequired<DominatorTree>();
2325       AU.addRequired<TargetData>();
2326       AU.addPreserved<TargetData>();
2327     }
2328
2329   private:
2330     /// Forwards - Adds new properties to VRPSolver and uses them to
2331     /// simplify instructions. Because new properties sometimes apply to
2332     /// a transition from one BasicBlock to another, this will use the
2333     /// PredicateSimplifier::proceedToSuccessor(s) interface to enter the
2334     /// basic block.
2335     /// @brief Performs abstract execution of the program.
2336     class VISIBILITY_HIDDEN Forwards : public InstVisitor<Forwards> {
2337       friend class InstVisitor<Forwards>;
2338       PredicateSimplifier *PS;
2339       DomTreeDFS::Node *DTNode;
2340
2341     public:
2342       ValueNumbering &VN;
2343       InequalityGraph &IG;
2344       UnreachableBlocks &UB;
2345       ValueRanges &VR;
2346
2347       Forwards(PredicateSimplifier *PS, DomTreeDFS::Node *DTNode)
2348         : PS(PS), DTNode(DTNode), VN(*PS->VN), IG(*PS->IG), UB(PS->UB),
2349           VR(*PS->VR) {}
2350
2351       void visitTerminatorInst(TerminatorInst &TI);
2352       void visitBranchInst(BranchInst &BI);
2353       void visitSwitchInst(SwitchInst &SI);
2354
2355       void visitAllocaInst(AllocaInst &AI);
2356       void visitLoadInst(LoadInst &LI);
2357       void visitStoreInst(StoreInst &SI);
2358
2359       void visitSExtInst(SExtInst &SI);
2360       void visitZExtInst(ZExtInst &ZI);
2361
2362       void visitBinaryOperator(BinaryOperator &BO);
2363       void visitICmpInst(ICmpInst &IC);
2364     };
2365
2366     // Used by terminator instructions to proceed from the current basic
2367     // block to the next. Verifies that "current" dominates "next",
2368     // then calls visitBasicBlock.
2369     void proceedToSuccessors(DomTreeDFS::Node *Current) {
2370       for (DomTreeDFS::Node::iterator I = Current->begin(),
2371            E = Current->end(); I != E; ++I) {
2372         WorkList.push_back(*I);
2373       }
2374     }
2375
2376     void proceedToSuccessor(DomTreeDFS::Node *Next) {
2377       WorkList.push_back(Next);
2378     }
2379
2380     // Visits each instruction in the basic block.
2381     void visitBasicBlock(DomTreeDFS::Node *Node) {
2382       BasicBlock *BB = Node->getBlock();
2383       DOUT << "Entering Basic Block: " << BB->getName()
2384            << " (" << Node->getDFSNumIn() << ")\n";
2385       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
2386         visitInstruction(I++, Node);
2387       }
2388     }
2389
2390     // Tries to simplify each Instruction and add new properties.
2391     void visitInstruction(Instruction *I, DomTreeDFS::Node *DT) {
2392       DOUT << "Considering instruction " << *I << "\n";
2393       DEBUG(VN->dump());
2394       DEBUG(IG->dump());
2395       DEBUG(VR->dump());
2396
2397       // Sometimes instructions are killed in earlier analysis.
2398       if (isInstructionTriviallyDead(I)) {
2399         ++NumSimple;
2400         modified = true;
2401         if (unsigned n = VN->valueNumber(I, DTDFS->getRootNode()))
2402           if (VN->value(n) == I) IG->remove(n);
2403         VN->remove(I);
2404         I->eraseFromParent();
2405         return;
2406       }
2407
2408 #ifndef NDEBUG
2409       // Try to replace the whole instruction.
2410       Value *V = VN->canonicalize(I, DT);
2411       assert(V == I && "Late instruction canonicalization.");
2412       if (V != I) {
2413         modified = true;
2414         ++NumInstruction;
2415         DOUT << "Removing " << *I << ", replacing with " << *V << "\n";
2416         if (unsigned n = VN->valueNumber(I, DTDFS->getRootNode()))
2417           if (VN->value(n) == I) IG->remove(n);
2418         VN->remove(I);
2419         I->replaceAllUsesWith(V);
2420         I->eraseFromParent();
2421         return;
2422       }
2423
2424       // Try to substitute operands.
2425       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
2426         Value *Oper = I->getOperand(i);
2427         Value *V = VN->canonicalize(Oper, DT);
2428         assert(V == Oper && "Late operand canonicalization.");
2429         if (V != Oper) {
2430           modified = true;
2431           ++NumVarsReplaced;
2432           DOUT << "Resolving " << *I;
2433           I->setOperand(i, V);
2434           DOUT << " into " << *I;
2435         }
2436       }
2437 #endif
2438
2439       std::string name = I->getParent()->getName();
2440       DOUT << "push (%" << name << ")\n";
2441       Forwards visit(this, DT);
2442       visit.visit(*I);
2443       DOUT << "pop (%" << name << ")\n";
2444     }
2445   };
2446
2447   bool PredicateSimplifier::runOnFunction(Function &F) {
2448     DominatorTree *DT = &getAnalysis<DominatorTree>();
2449     DTDFS = new DomTreeDFS(DT);
2450     TargetData *TD = &getAnalysis<TargetData>();
2451
2452     DOUT << "Entering Function: " << F.getName() << "\n";
2453
2454     modified = false;
2455     DomTreeDFS::Node *Root = DTDFS->getRootNode();
2456     VN = new ValueNumbering(DTDFS);
2457     IG = new InequalityGraph(*VN, Root);
2458     VR = new ValueRanges(*VN, TD);
2459     WorkList.push_back(Root);
2460
2461     do {
2462       DomTreeDFS::Node *DTNode = WorkList.back();
2463       WorkList.pop_back();
2464       if (!UB.isDead(DTNode->getBlock())) visitBasicBlock(DTNode);
2465     } while (!WorkList.empty());
2466
2467     delete DTDFS;
2468     delete VR;
2469     delete IG;
2470     delete VN;
2471
2472     modified |= UB.kill();
2473
2474     return modified;
2475   }
2476
2477   void PredicateSimplifier::Forwards::visitTerminatorInst(TerminatorInst &TI) {
2478     PS->proceedToSuccessors(DTNode);
2479   }
2480
2481   void PredicateSimplifier::Forwards::visitBranchInst(BranchInst &BI) {
2482     if (BI.isUnconditional()) {
2483       PS->proceedToSuccessors(DTNode);
2484       return;
2485     }
2486
2487     Value *Condition = BI.getCondition();
2488     BasicBlock *TrueDest  = BI.getSuccessor(0);
2489     BasicBlock *FalseDest = BI.getSuccessor(1);
2490
2491     if (isa<Constant>(Condition) || TrueDest == FalseDest) {
2492       PS->proceedToSuccessors(DTNode);
2493       return;
2494     }
2495
2496     for (DomTreeDFS::Node::iterator I = DTNode->begin(), E = DTNode->end();
2497          I != E; ++I) {
2498       BasicBlock *Dest = (*I)->getBlock();
2499       DOUT << "Branch thinking about %" << Dest->getName()
2500            << "(" << PS->DTDFS->getNodeForBlock(Dest)->getDFSNumIn() << ")\n";
2501
2502       if (Dest == TrueDest) {
2503         DOUT << "(" << DTNode->getBlock()->getName() << ") true set:\n";
2504         VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, Dest);
2505         VRP.add(ConstantInt::getTrue(), Condition, ICmpInst::ICMP_EQ);
2506         VRP.solve();
2507         DEBUG(VN.dump());
2508         DEBUG(IG.dump());
2509         DEBUG(VR.dump());
2510       } else if (Dest == FalseDest) {
2511         DOUT << "(" << DTNode->getBlock()->getName() << ") false set:\n";
2512         VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, Dest);
2513         VRP.add(ConstantInt::getFalse(), Condition, ICmpInst::ICMP_EQ);
2514         VRP.solve();
2515         DEBUG(VN.dump());
2516         DEBUG(IG.dump());
2517         DEBUG(VR.dump());
2518       }
2519
2520       PS->proceedToSuccessor(*I);
2521     }
2522   }
2523
2524   void PredicateSimplifier::Forwards::visitSwitchInst(SwitchInst &SI) {
2525     Value *Condition = SI.getCondition();
2526
2527     // Set the EQProperty in each of the cases BBs, and the NEProperties
2528     // in the default BB.
2529
2530     for (DomTreeDFS::Node::iterator I = DTNode->begin(), E = DTNode->end();
2531          I != E; ++I) {
2532       BasicBlock *BB = (*I)->getBlock();
2533       DOUT << "Switch thinking about BB %" << BB->getName()
2534            << "(" << PS->DTDFS->getNodeForBlock(BB)->getDFSNumIn() << ")\n";
2535
2536       VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, BB);
2537       if (BB == SI.getDefaultDest()) {
2538         for (unsigned i = 1, e = SI.getNumCases(); i < e; ++i)
2539           if (SI.getSuccessor(i) != BB)
2540             VRP.add(Condition, SI.getCaseValue(i), ICmpInst::ICMP_NE);
2541         VRP.solve();
2542       } else if (ConstantInt *CI = SI.findCaseDest(BB)) {
2543         VRP.add(Condition, CI, ICmpInst::ICMP_EQ);
2544         VRP.solve();
2545       }
2546       PS->proceedToSuccessor(*I);
2547     }
2548   }
2549
2550   void PredicateSimplifier::Forwards::visitAllocaInst(AllocaInst &AI) {
2551     VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, &AI);
2552     VRP.add(Constant::getNullValue(AI.getType()), &AI, ICmpInst::ICMP_NE);
2553     VRP.solve();
2554   }
2555
2556   void PredicateSimplifier::Forwards::visitLoadInst(LoadInst &LI) {
2557     Value *Ptr = LI.getPointerOperand();
2558     // avoid "load i8* null" -> null NE null.
2559     if (isa<Constant>(Ptr)) return;
2560
2561     VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, &LI);
2562     VRP.add(Constant::getNullValue(Ptr->getType()), Ptr, ICmpInst::ICMP_NE);
2563     VRP.solve();
2564   }
2565
2566   void PredicateSimplifier::Forwards::visitStoreInst(StoreInst &SI) {
2567     Value *Ptr = SI.getPointerOperand();
2568     if (isa<Constant>(Ptr)) return;
2569
2570     VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, &SI);
2571     VRP.add(Constant::getNullValue(Ptr->getType()), Ptr, ICmpInst::ICMP_NE);
2572     VRP.solve();
2573   }
2574
2575   void PredicateSimplifier::Forwards::visitSExtInst(SExtInst &SI) {
2576     VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, &SI);
2577     uint32_t SrcBitWidth = cast<IntegerType>(SI.getSrcTy())->getBitWidth();
2578     uint32_t DstBitWidth = cast<IntegerType>(SI.getDestTy())->getBitWidth();
2579     APInt Min(APInt::getHighBitsSet(DstBitWidth, DstBitWidth-SrcBitWidth+1));
2580     APInt Max(APInt::getLowBitsSet(DstBitWidth, SrcBitWidth-1));
2581     VRP.add(ConstantInt::get(Min), &SI, ICmpInst::ICMP_SLE);
2582     VRP.add(ConstantInt::get(Max), &SI, ICmpInst::ICMP_SGE);
2583     VRP.solve();
2584   }
2585
2586   void PredicateSimplifier::Forwards::visitZExtInst(ZExtInst &ZI) {
2587     VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, &ZI);
2588     uint32_t SrcBitWidth = cast<IntegerType>(ZI.getSrcTy())->getBitWidth();
2589     uint32_t DstBitWidth = cast<IntegerType>(ZI.getDestTy())->getBitWidth();
2590     APInt Max(APInt::getLowBitsSet(DstBitWidth, SrcBitWidth));
2591     VRP.add(ConstantInt::get(Max), &ZI, ICmpInst::ICMP_UGE);
2592     VRP.solve();
2593   }
2594
2595   void PredicateSimplifier::Forwards::visitBinaryOperator(BinaryOperator &BO) {
2596     Instruction::BinaryOps ops = BO.getOpcode();
2597
2598     switch (ops) {
2599     default: break;
2600       case Instruction::URem:
2601       case Instruction::SRem:
2602       case Instruction::UDiv:
2603       case Instruction::SDiv: {
2604         Value *Divisor = BO.getOperand(1);
2605         VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, &BO);
2606         VRP.add(Constant::getNullValue(Divisor->getType()), Divisor,
2607                 ICmpInst::ICMP_NE);
2608         VRP.solve();
2609         break;
2610       }
2611     }
2612
2613     switch (ops) {
2614       default: break;
2615       case Instruction::Shl: {
2616         VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, &BO);
2617         VRP.add(&BO, BO.getOperand(0), ICmpInst::ICMP_UGE);
2618         VRP.solve();
2619       } break;
2620       case Instruction::AShr: {
2621         VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, &BO);
2622         VRP.add(&BO, BO.getOperand(0), ICmpInst::ICMP_SLE);
2623         VRP.solve();
2624       } break;
2625       case Instruction::LShr:
2626       case Instruction::UDiv: {
2627         VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, &BO);
2628         VRP.add(&BO, BO.getOperand(0), ICmpInst::ICMP_ULE);
2629         VRP.solve();
2630       } break;
2631       case Instruction::URem: {
2632         VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, &BO);
2633         VRP.add(&BO, BO.getOperand(1), ICmpInst::ICMP_ULE);
2634         VRP.solve();
2635       } break;
2636       case Instruction::And: {
2637         VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, &BO);
2638         VRP.add(&BO, BO.getOperand(0), ICmpInst::ICMP_ULE);
2639         VRP.add(&BO, BO.getOperand(1), ICmpInst::ICMP_ULE);
2640         VRP.solve();
2641       } break;
2642       case Instruction::Or: {
2643         VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, &BO);
2644         VRP.add(&BO, BO.getOperand(0), ICmpInst::ICMP_UGE);
2645         VRP.add(&BO, BO.getOperand(1), ICmpInst::ICMP_UGE);
2646         VRP.solve();
2647       } break;
2648     }
2649   }
2650
2651   void PredicateSimplifier::Forwards::visitICmpInst(ICmpInst &IC) {
2652     // If possible, squeeze the ICmp predicate into something simpler.
2653     // Eg., if x = [0, 4) and we're being asked icmp uge %x, 3 then change
2654     // the predicate to eq.
2655
2656     // XXX: once we do full PHI handling, modifying the instruction in the
2657     // Forwards visitor will cause missed optimizations.
2658
2659     ICmpInst::Predicate Pred = IC.getPredicate();
2660
2661     switch (Pred) {
2662       default: break;
2663       case ICmpInst::ICMP_ULE: Pred = ICmpInst::ICMP_ULT; break;
2664       case ICmpInst::ICMP_UGE: Pred = ICmpInst::ICMP_UGT; break;
2665       case ICmpInst::ICMP_SLE: Pred = ICmpInst::ICMP_SLT; break;
2666       case ICmpInst::ICMP_SGE: Pred = ICmpInst::ICMP_SGT; break;
2667     }
2668     if (Pred != IC.getPredicate()) {
2669       VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, &IC);
2670       if (VRP.isRelatedBy(IC.getOperand(1), IC.getOperand(0),
2671                           ICmpInst::ICMP_NE)) {
2672         ++NumSnuggle;
2673         PS->modified = true;
2674         IC.setPredicate(Pred);
2675       }
2676     }
2677
2678     Pred = IC.getPredicate();
2679
2680     if (ConstantInt *Op1 = dyn_cast<ConstantInt>(IC.getOperand(1))) {
2681       ConstantInt *NextVal = 0;
2682       switch (Pred) {
2683         default: break;
2684         case ICmpInst::ICMP_SLT:
2685         case ICmpInst::ICMP_ULT:
2686           if (Op1->getValue() != 0)
2687             NextVal = ConstantInt::get(Op1->getValue()-1);
2688          break;
2689         case ICmpInst::ICMP_SGT:
2690         case ICmpInst::ICMP_UGT:
2691           if (!Op1->getValue().isAllOnesValue())
2692             NextVal = ConstantInt::get(Op1->getValue()+1);
2693          break;
2694       }
2695
2696       if (NextVal) {
2697         VRPSolver VRP(VN, IG, UB, VR, PS->DTDFS, PS->modified, &IC);
2698         if (VRP.isRelatedBy(IC.getOperand(0), NextVal,
2699                             ICmpInst::getInversePredicate(Pred))) {
2700           ICmpInst *NewIC = new ICmpInst(ICmpInst::ICMP_EQ, IC.getOperand(0),
2701                                          NextVal, "", &IC);
2702           NewIC->takeName(&IC);
2703           IC.replaceAllUsesWith(NewIC);
2704
2705           // XXX: prove this isn't necessary
2706           if (unsigned n = VN.valueNumber(&IC, PS->DTDFS->getRootNode()))
2707             if (VN.value(n) == &IC) IG.remove(n);
2708           VN.remove(&IC);
2709
2710           IC.eraseFromParent();
2711           ++NumSnuggle;
2712           PS->modified = true;
2713         }
2714       }
2715     }
2716   }
2717 }
2718
2719 char PredicateSimplifier::ID = 0;
2720 static RegisterPass<PredicateSimplifier>
2721 X("predsimplify", "Predicate Simplifier");
2722
2723 FunctionPass *llvm::createPredicateSimplifierPass() {
2724   return new PredicateSimplifier();
2725 }