lib/Transforms/Scalar/PredicateSimplifier.cpp

   1 //===-- PredicateSimplifier.cpp - Path Sensitive Simplifier ---------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Nick Lewycky and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Path-sensitive optimizer. In a branch where x == y, replace uses of
  11 // x with y. Permits further optimization, such as the elimination of
  12 // the unreachable call:
  13 //
  14 // void test(int *p, int *q)
  15 // {
  16 //   if (p != q)
  17 //     return;
  18 //
  19 //   if (*p != *q)
  20 //     foo(); // unreachable
  21 // }
  22 //
  23 //===----------------------------------------------------------------------===//
  24 //
  25 // This pass focusses on four properties; equals, not equals, less-than
  26 // and less-than-or-equals-to. The greater-than forms are also held just
  27 // 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 to the
  33 // same node. The node contains a most canonical Value* form and the list of
  34 // known relationships.
  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 // queries (such as "isEqual") and mutators (such as "addEqual"). To implement
  45 // "isLess(%a, %c)", we start with getNode(%c) and walk downwards until
  46 // we reach %a or the leaf node. Note that the graph is directed and acyclic,
  47 // but may contain joins, meaning that this walk is not a linear time
  48 // algorithm.
  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 = seteq int* %ptr, null
  56 //   %a = or bool %P, %Q
  57 //   br bool %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 "or" 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 #define DEBUG_TYPE "predsimplify"
  72 #include "llvm/Transforms/Scalar.h"
  73 #include "llvm/Constants.h"
  74 #include "llvm/DerivedTypes.h"
  75 #include "llvm/Instructions.h"
  76 #include "llvm/Pass.h"
  77 #include "llvm/ADT/SetOperations.h"
  78 #include "llvm/ADT/SmallVector.h"
  79 #include "llvm/ADT/Statistic.h"
  80 #include "llvm/ADT/STLExtras.h"
  81 #include "llvm/Analysis/Dominators.h"
  82 #include "llvm/Analysis/ET-Forest.h"
  83 #include "llvm/Assembly/Writer.h"
  84 #include "llvm/Support/CFG.h"
  85 #include "llvm/Support/Compiler.h"
  86 #include "llvm/Support/Debug.h"
  87 #include "llvm/Support/InstVisitor.h"
  88 #include "llvm/Transforms/Utils/Local.h"
  89 #include <algorithm>
  90 #include <deque>
  91 #include <sstream>
  92 #include <map>
  93 using namespace llvm;
  94
  95 STATISTIC(NumVarsReplaced, "Number of argument substitutions");
  96 STATISTIC(NumInstruction , "Number of instructions removed");
  97 STATISTIC(NumSimple      , "Number of simple replacements");
  98
  99 namespace {
 100   /// The InequalityGraph stores the relationships between values.
 101   /// Each Value in the graph is assigned to a Node. Nodes are pointer
 102   /// comparable for equality. The caller is expected to maintain the logical
 103   /// consistency of the system.
 104   ///
 105   /// The InequalityGraph class may invalidate Node*s after any mutator call.
 106   /// @brief The InequalityGraph stores the relationships between values.
 107   class VISIBILITY_HIDDEN InequalityGraph {
 108   public:
 109     class Node;
 110
 111     // LT GT EQ
 112     //  0  0  0 -- invalid (false)
 113     //  0  0  1 -- invalid (EQ)
 114     //  0  1  0 -- GT
 115     //  0  1  1 -- GE
 116     //  1  0  0 -- LT
 117     //  1  0  1 -- LE
 118     //  1  1  0 -- NE
 119     //  1  1  1 -- invalid (true)
 120     enum LatticeBits {
 121       EQ_BIT = 1, GT_BIT = 2, LT_BIT = 4
 122     };
 123     enum LatticeVal {
 124       GT = GT_BIT, GE = GT_BIT | EQ_BIT,
 125       LT = LT_BIT, LE = LT_BIT | EQ_BIT,
 126       NE = GT_BIT | LT_BIT
 127     };
 128
 129     static bool validPredicate(LatticeVal LV) {
 130       return LV > 1 && LV < 7;
 131     }
 132
 133   private:
 134     typedef std::map<Value *, Node *> NodeMapType;
 135     NodeMapType Nodes;
 136
 137     const InequalityGraph *ConcreteIG;
 138
 139   public:
 140     /// A single node in the InequalityGraph. This stores the canonical Value
 141     /// for the node, as well as the relationships with the neighbours.
 142     ///
 143     /// Because the lists are intended to be used for traversal, it is invalid
 144     /// for the node to list itself in LessEqual or GreaterEqual lists. The
 145     /// fact that a node is equal to itself is implied, and may be checked
 146     /// with pointer comparison.
 147     /// @brief A single node in the InequalityGraph.
 148     class VISIBILITY_HIDDEN Node {
 149       friend class InequalityGraph;
 150
 151       Value *Canonical;
 152
 153       typedef SmallVector<std::pair<Node *, LatticeVal>, 4> RelationsType;
 154       RelationsType Relations;
 155     public:
 156       typedef RelationsType::iterator       iterator;
 157       typedef RelationsType::const_iterator const_iterator;
 158
 159     private:
 160       /// Updates the lattice value for a given node. Create a new entry if
 161       /// one doesn't exist, otherwise it merges the values. The new lattice
 162       /// value must not be inconsistent with any previously existing value.
 163       void update(Node *N, LatticeVal R) {
 164         iterator I = find(N);
 165         if (I == end()) {
 166           Relations.push_back(std::make_pair(N, R));
 167         } else {
 168           I->second = static_cast<LatticeVal>(I->second & R);
 169           assert(validPredicate(I->second) &&
 170                  "Invalid union of lattice values.");
 171         }
 172       }
 173
 174       void assign(Node *N, LatticeVal R) {
 175         iterator I = find(N);
 176         if (I != end()) I->second = R;
 177
 178         Relations.push_back(std::make_pair(N, R));
 179       }
 180
 181     public:
 182       iterator begin()       { return Relations.begin(); }
 183       iterator end()         { return Relations.end();   }
 184       iterator find(Node *N) {
 185         iterator I = begin();
 186         for (iterator E = end(); I != E; ++I)
 187           if (I->first == N) break;
 188         return I;
 189       }
 190
 191       const_iterator begin()       const { return Relations.begin(); }
 192       const_iterator end()         const { return Relations.end();   }
 193       const_iterator find(Node *N) const {
 194         const_iterator I = begin();
 195         for (const_iterator E = end(); I != E; ++I)
 196           if (I->first == N) break;
 197         return I;
 198       }
 199
 200       unsigned findIndex(Node *N) {
 201         unsigned i = 0;
 202         iterator I = begin();
 203         for (iterator E = end(); I != E; ++I, ++i)
 204           if (I->first == N) return i;
 205         return (unsigned)-1;
 206       }
 207
 208       void erase(iterator i) { Relations.erase(i); }
 209
 210       Value *getValue() const { return Canonical; }
 211       void setValue(Value *V) { Canonical = V; }
 212
 213       void addNotEqual(Node *N)     { update(N, NE); }
 214       void addLess(Node *N)         { update(N, LT); }
 215       void addLessEqual(Node *N)    { update(N, LE); }
 216       void addGreater(Node *N)      { update(N, GT); }
 217       void addGreaterEqual(Node *N) { update(N, GE); }
 218     };
 219
 220     InequalityGraph() : ConcreteIG(NULL) {}
 221
 222     InequalityGraph(const InequalityGraph &_IG) {
 223 #if 0 // disable COW
 224       if (_IG.ConcreteIG) ConcreteIG = _IG.ConcreteIG;
 225       else ConcreteIG = &_IG;
 226 #else
 227       ConcreteIG = &_IG;
 228       materialize();
 229 #endif
 230     }
 231
 232     ~InequalityGraph();
 233
 234   private:
 235     void materialize();
 236
 237   public:
 238     /// If the Value is in the graph, return the canonical form. Otherwise,
 239     /// return the original Value.
 240     Value *canonicalize(Value *V) const {
 241       if (const Node *N = getNode(V))
 242         return N->getValue();
 243       else
 244         return V;
 245     }
 246
 247     /// Returns the node currently representing Value V, or null if no such
 248     /// node exists.
 249     Node *getNode(Value *V) {
 250       materialize();
 251
 252       NodeMapType::const_iterator I = Nodes.find(V);
 253       return (I != Nodes.end()) ? I->second : 0;
 254     }
 255
 256     const Node *getNode(Value *V) const {
 257       if (ConcreteIG) return ConcreteIG->getNode(V);
 258
 259       NodeMapType::const_iterator I = Nodes.find(V);
 260       return (I != Nodes.end()) ? I->second : 0;
 261     }
 262
 263     Node *getOrInsertNode(Value *V) {
 264       if (Node *N = getNode(V))
 265         return N;
 266       else
 267         return newNode(V);
 268     }
 269
 270     Node *newNode(Value *V) {
 271       //DOUT << "new node: " << *V << "\n";
 272       materialize();
 273       Node *&N = Nodes[V];
 274       assert(N == 0 && "Node already exists for value.");
 275       N = new Node();
 276       N->setValue(V);
 277       return N;
 278     }
 279
 280     /// Returns true iff the nodes are provably inequal.
 281     bool isNotEqual(const Node *N1, const Node *N2) const {
 282       if (N1 == N2) return false;
 283       for (Node::const_iterator I = N1->begin(), E = N1->end(); I != E; ++I) {
 284         if (I->first == N2)
 285           return (I->second & EQ_BIT) == 0;
 286       }
 287       return isLess(N1, N2) || isGreater(N1, N2);
 288     }
 289
 290     /// Returns true iff N1 is provably less than N2.
 291     bool isLess(const Node *N1, const Node *N2) const {
 292       if (N1 == N2) return false;
 293       for (Node::const_iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
 294         if (I->first == N1)
 295           return I->second == LT;
 296       }
 297       for (Node::const_iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
 298         if ((I->second & (LT_BIT | GT_BIT)) == LT_BIT)
 299           if (isLess(N1, I->first)) return true;
 300       }
 301       return false;
 302     }
 303
 304     /// Returns true iff N1 is provably less than or equal to N2.
 305     bool isLessEqual(const Node *N1, const Node *N2) const {
 306       if (N1 == N2) return true;
 307       for (Node::const_iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
 308         if (I->first == N1)
 309           return (I->second & (LT_BIT | GT_BIT)) == LT_BIT;
 310       }
 311       for (Node::const_iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
 312         if ((I->second & (LT_BIT | GT_BIT)) == LT_BIT)
 313           if (isLessEqual(N1, I->first)) return true;
 314       }
 315       return false;
 316     }
 317
 318     /// Returns true iff N1 is provably greater than N2.
 319     bool isGreater(const Node *N1, const Node *N2) const {
 320       return isLess(N2, N1);
 321     }
 322
 323     /// Returns true iff N1 is provably greater than or equal to N2.
 324     bool isGreaterEqual(const Node *N1, const Node *N2) const {
 325       return isLessEqual(N2, N1);
 326     }
 327
 328     // The add* methods assume that your input is logically valid and may
 329     // assertion-fail or infinitely loop if you attempt a contradiction.
 330
 331     void addEqual(Node *N, Value *V) {
 332       materialize();
 333       Nodes[V] = N;
 334     }
 335
 336     void addNotEqual(Node *N1, Node *N2) {
 337       assert(N1 != N2 && "A node can't be inequal to itself.");
 338       materialize();
 339       N1->addNotEqual(N2);
 340       N2->addNotEqual(N1);
 341     }
 342
 343     /// N1 is less than N2.
 344     void addLess(Node *N1, Node *N2) {
 345       assert(N1 != N2 && !isLess(N2, N1) && "Attempt to create < cycle.");
 346       materialize();
 347       N2->addLess(N1);
 348       N1->addGreater(N2);
 349     }
 350
 351     /// N1 is less than or equal to N2.
 352     void addLessEqual(Node *N1, Node *N2) {
 353       assert(N1 != N2 && "Nodes are equal. Use mergeNodes instead.");
 354       assert(!isGreater(N1, N2) && "Impossible: Adding x <= y when x > y.");
 355       materialize();
 356       N2->addLessEqual(N1);
 357       N1->addGreaterEqual(N2);
 358     }
 359
 360     /// Find the transitive closure starting at a node walking down the edges
 361     /// of type Val. Type Inserter must be an inserter that accepts Node *.
 362     template <typename Inserter>
 363     void transitiveClosure(Node *N, LatticeVal Val, Inserter insert) {
 364       for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I) {
 365         if (I->second == Val) {
 366           *insert = I->first;
 367           transitiveClosure(I->first, Val, insert);
 368         }
 369       }
 370     }
 371
 372     /// Kills off all the nodes in Kill by replicating their properties into
 373     /// node N. The elements of Kill must be unique. After merging, N's new
 374     /// canonical value is NewCanonical. Type C must be a container of Node *.
 375     template <typename C>
 376     void mergeNodes(Node *N, C &Kill, Value *NewCanonical);
 377
 378     /// Removes a Value from the graph, but does not delete any nodes. As this
 379     /// method does not delete Nodes, V may not be the canonical choice for
 380     /// any node.
 381     void remove(Value *V) {
 382       materialize();
 383
 384       for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E;) {
 385         NodeMapType::iterator J = I++;
 386         assert(J->second->getValue() != V && "Can't delete canonical choice.");
 387         if (J->first == V) Nodes.erase(J);
 388       }
 389     }
 390
 391 #ifndef NDEBUG
 392     void debug(std::ostream &os) const {
 393     std::set<Node *> VisitedNodes;
 394     for (NodeMapType::const_iterator I = Nodes.begin(), E = Nodes.end();
 395          I != E; ++I) {
 396       Node *N = I->second;
 397       os << *I->first << " == " << *N->getValue() << "\n";
 398       if (VisitedNodes.insert(N).second) {
 399         os << *N->getValue() << ":\n";
 400         for (Node::const_iterator NI = N->begin(), NE = N->end();
 401              NI != NE; ++NI) {
 402           static const std::string names[8] =
 403               { "00", "01", " <", "<=", " >", ">=", "!=", "07" };
 404           os << "  " << names[NI->second] << " "
 405              << *NI->first->getValue() << "\n";
 406         }
 407       }
 408     }
 409   }
 410 #endif
 411   };
 412
 413   InequalityGraph::~InequalityGraph() {
 414     if (ConcreteIG) return;
 415
 416     std::vector<Node *> Remove;
 417     for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end();
 418          I != E; ++I) {
 419       if (I->first == I->second->getValue())
 420         Remove.push_back(I->second);
 421     }
 422     for (std::vector<Node *>::iterator I = Remove.begin(), E = Remove.end();
 423          I != E; ++I) {
 424       delete *I;
 425     }
 426   }
 427
 428   template <typename C>
 429   void InequalityGraph::mergeNodes(Node *N, C &Kill, Value *NewCanonical) {
 430     materialize();
 431
 432     // Merge the relationships from the members of Kill into N.
 433     for (typename C::iterator KI = Kill.begin(), KE = Kill.end();
 434          KI != KE; ++KI) {
 435
 436       for (Node::iterator I = (*KI)->begin(), E = (*KI)->end(); I != E; ++I) {
 437         if (I->first == N) continue;
 438
 439         Node::iterator NI = N->find(I->first);
 440         if (NI == N->end()) {
 441           N->Relations.push_back(std::make_pair(I->first, I->second));
 442         } else {
 443           unsigned char LV = NI->second & I->second;
 444           if (LV == EQ_BIT) {
 445
 446             assert(std::find(Kill.begin(), Kill.end(), I->first) != Kill.end()
 447                     && "Lost EQ property.");
 448             N->erase(NI);
 449           } else {
 450             NI->second = static_cast<LatticeVal>(LV);
 451             assert(InequalityGraph::validPredicate(NI->second) &&
 452                    "Invalid union of lattice values.");
 453           }
 454         }
 455
 456         // All edges are reciprocal; every Node that Kill points to also
 457         // contains a pointer to Kill. Replace those with pointers with N.
 458         unsigned iter = I->first->findIndex(*KI);
 459         assert(iter != (unsigned)-1 && "Edge not reciprocal.");
 460         I->first->assign(N, (I->first->begin()+iter)->second);
 461         I->first->erase(I->first->begin()+iter);
 462       }
 463
 464       // Removing references from N to Kill.
 465       Node::iterator NI = N->find(*KI);
 466       if (NI != N->end()) {
 467         N->erase(NI); // breaks reciprocity until Kill is deleted.
 468       }
 469     }
 470
 471     N->setValue(NewCanonical);
 472
 473     // Update value mapping to point to the merged node.
 474     for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end();
 475          I != E; ++I) {
 476       if (std::find(Kill.begin(), Kill.end(), I->second) != Kill.end())
 477         I->second = N;
 478     }
 479
 480     for (typename C::iterator KI = Kill.begin(), KE = Kill.end();
 481          KI != KE; ++KI) {
 482       delete *KI;
 483     }
 484   }
 485
 486   void InequalityGraph::materialize() {
 487     if (!ConcreteIG) return;
 488     const InequalityGraph *IG = ConcreteIG;
 489     ConcreteIG = NULL;
 490
 491     for (NodeMapType::const_iterator I = IG->Nodes.begin(),
 492          E = IG->Nodes.end(); I != E; ++I) {
 493       if (I->first == I->second->getValue()) {
 494         Node *N = newNode(I->first);
 495         N->Relations.reserve(N->Relations.size());
 496       }
 497     }
 498     for (NodeMapType::const_iterator I = IG->Nodes.begin(),
 499          E = IG->Nodes.end(); I != E; ++I) {
 500       if (I->first != I->second->getValue()) {
 501         Nodes[I->first] = getNode(I->second->getValue());
 502       } else {
 503         Node *Old = I->second;
 504         Node *N = getNode(I->first);
 505         for (Node::const_iterator NI = Old->begin(), NE = Old->end();
 506              NI != NE; ++NI) {
 507           N->assign(getNode(NI->first->getValue()), NI->second);
 508         }
 509       }
 510     }
 511   }
 512
 513   /// VRPSolver keeps track of how changes to one variable affect other
 514   /// variables, and forwards changes along to the InequalityGraph. It
 515   /// also maintains the correct choice for "canonical" in the IG.
 516   /// @brief VRPSolver calculates inferences from a new relationship.
 517   class VISIBILITY_HIDDEN VRPSolver {
 518   private:
 519     std::deque<Instruction *> WorkList;
 520
 521     InequalityGraph &IG;
 522     const InequalityGraph &cIG;
 523     ETForest *Forest;
 524     ETNode *Top;
 525
 526     typedef InequalityGraph::Node Node;
 527
 528     /// Returns true if V1 is a better canonical value than V2.
 529     bool compare(Value *V1, Value *V2) const {
 530       if (isa<Constant>(V1))
 531         return !isa<Constant>(V2);
 532       else if (isa<Constant>(V2))
 533         return false;
 534       else if (isa<Argument>(V1))
 535         return !isa<Argument>(V2);
 536       else if (isa<Argument>(V2))
 537         return false;
 538
 539       Instruction *I1 = dyn_cast<Instruction>(V1);
 540       Instruction *I2 = dyn_cast<Instruction>(V2);
 541
 542       if (!I1 || !I2) return false;
 543
 544       BasicBlock *BB1 = I1->getParent(),
 545                  *BB2 = I2->getParent();
 546       if (BB1 == BB2) {
 547         for (BasicBlock::const_iterator I = BB1->begin(), E = BB1->end();
 548              I != E; ++I) {
 549           if (&*I == I1) return true;
 550           if (&*I == I2) return false;
 551         }
 552         assert(!"Instructions not found in parent BasicBlock?");
 553       } else {
 554         return Forest->properlyDominates(BB1, BB2);
 555       }
 556       return false;
 557     }
 558
 559     void addToWorklist(Instruction *I) {
 560       //DOUT << "addToWorklist: " << *I << "\n";
 561
 562       if (!isa<BinaryOperator>(I) && !isa<SelectInst>(I)) return;
 563
 564       const Type *Ty = I->getType();
 565       if (Ty == Type::VoidTy || Ty->isFPOrFPVector()) return;
 566
 567       if (isInstructionTriviallyDead(I)) return;
 568
 569       WorkList.push_back(I);
 570     }
 571
 572     void addRecursive(Value *V) {
 573       //DOUT << "addRecursive: " << *V << "\n";
 574
 575       Instruction *I = dyn_cast<Instruction>(V);
 576       if (I)
 577         addToWorklist(I);
 578       else if (!isa<Argument>(V))
 579         return;
 580
 581       //DOUT << "addRecursive uses...\n";
 582       for (Value::use_iterator UI = V->use_begin(), UE = V->use_end();
 583            UI != UE; ++UI) {
 584         // Use must be either be dominated by Top, or dominate Top.
 585         if (Instruction *Inst = dyn_cast<Instruction>(*UI)) {
 586           ETNode *INode = Forest->getNodeForBlock(Inst->getParent());
 587           if (INode->DominatedBy(Top) || Top->DominatedBy(INode))
 588             addToWorklist(Inst);
 589         }
 590       }
 591
 592       if (I) {
 593         //DOUT << "addRecursive ops...\n";
 594         for (User::op_iterator OI = I->op_begin(), OE = I->op_end();
 595              OI != OE; ++OI) {
 596           if (Instruction *Inst = dyn_cast<Instruction>(*OI))
 597             addToWorklist(Inst);
 598         }
 599       }
 600       //DOUT << "exit addRecursive (" << *V << ").\n";
 601     }
 602
 603   public:
 604     VRPSolver(InequalityGraph &IG, ETForest *Forest, BasicBlock *TopBB)
 605       : IG(IG), cIG(IG), Forest(Forest), Top(Forest->getNodeForBlock(TopBB)) {}
 606
 607     bool isEqual(Value *V1, Value *V2) const {
 608       if (V1 == V2) return true;
 609       if (const Node *N1 = cIG.getNode(V1))
 610         return N1 == cIG.getNode(V2);
 611       return false;
 612     }
 613
 614     bool isNotEqual(Value *V1, Value *V2) const {
 615       if (V1 == V2) return false;
 616       if (const Node *N1 = cIG.getNode(V1))
 617         if (const Node *N2 = cIG.getNode(V2))
 618           return cIG.isNotEqual(N1, N2);
 619       return false;
 620     }
 621
 622     bool isLess(Value *V1, Value *V2) const {
 623       if (V1 == V2) return false;
 624       if (const Node *N1 = cIG.getNode(V1))
 625         if (const Node *N2 = cIG.getNode(V2))
 626           return cIG.isLess(N1, N2);
 627       return false;
 628     }
 629
 630     bool isLessEqual(Value *V1, Value *V2) const {
 631       if (V1 == V2) return true;
 632       if (const Node *N1 = cIG.getNode(V1))
 633         if (const Node *N2 = cIG.getNode(V2))
 634           return cIG.isLessEqual(N1, N2);
 635       return false;
 636     }
 637
 638     bool isGreater(Value *V1, Value *V2) const {
 639       if (V1 == V2) return false;
 640       if (const Node *N1 = cIG.getNode(V1))
 641         if (const Node *N2 = cIG.getNode(V2))
 642           return cIG.isGreater(N1, N2);
 643       return false;
 644     }
 645
 646     bool isGreaterEqual(Value *V1, Value *V2) const {
 647       if (V1 == V2) return true;
 648       if (const Node *N1 = IG.getNode(V1))
 649         if (const Node *N2 = IG.getNode(V2))
 650           return cIG.isGreaterEqual(N1, N2);
 651       return false;
 652     }
 653
 654     // All of the add* functions return true if the InequalityGraph represents
 655     // the property, and false if there is a logical contradiction. On false,
 656     // you may no longer perform any queries on the InequalityGraph.
 657
 658     bool addEqual(Value *V1, Value *V2) {
 659       //DOUT << "addEqual(" << *V1 << ", " << *V2 << ")\n";
 660       if (isEqual(V1, V2)) return true;
 661
 662       const Node *cN1 = cIG.getNode(V1), *cN2 = cIG.getNode(V2);
 663
 664       if (cN1 && cN2 && cIG.isNotEqual(cN1, cN2))
 665           return false;
 666
 667       if (compare(V2, V1)) { std::swap(V1, V2); std::swap(cN1, cN2); }
 668
 669       if (cN1) {
 670         if (ConstantBool *CB = dyn_cast<ConstantBool>(V1)) {
 671           Node *N1 = IG.getNode(V1);
 672
 673           // When "addEqual" is performed and the new value is a ConstantBool,
 674           // iterate through the NE set and fix them up to be EQ of the
 675           // opposite bool.
 676
 677           for (Node::iterator I = N1->begin(), E = N1->end(); I != E; ++I)
 678             if ((I->second & 1) == 0) {
 679               assert(N1 != I->first && "Node related to itself?");
 680               addEqual(I->first->getValue(),
 681                        ConstantBool::get(!CB->getValue()));
 682             }
 683         }
 684       }
 685
 686       if (!cN2) {
 687         if (Instruction *I2 = dyn_cast<Instruction>(V2)) {
 688           ETNode *Node_I2 = Forest->getNodeForBlock(I2->getParent());
 689           if (Top != Node_I2 && Node_I2->DominatedBy(Top)) {
 690             Value *V = V1;
 691             if (cN1 && compare(V1, cN1->getValue())) V = cN1->getValue();
 692             //DOUT << "Simply removing " << *I2
 693             //     << ", replacing with " << *V << "\n";
 694             I2->replaceAllUsesWith(V);
 695             // leave it dead; it'll get erased later.
 696             ++NumSimple;
 697             addRecursive(V1);
 698             return true;
 699           }
 700         }
 701       }
 702
 703       Node *N1 = IG.getNode(V1), *N2 = IG.getNode(V2);
 704
 705       if ( N1 && !N2) {
 706         IG.addEqual(N1, V2);
 707         if (compare(V1, N1->getValue())) N1->setValue(V1);
 708       }
 709       if (!N1 &&  N2) {
 710         IG.addEqual(N2, V1);
 711         if (compare(V1, N2->getValue())) N2->setValue(V1);
 712       }
 713       if ( N1 &&  N2) {
 714         // Suppose we're being told that %x == %y, and %x <= %z and %y >= %z.
 715         // We can't just merge %x and %y because the relationship with %z would
 716         // be EQ and that's invalid; they need to be the same Node.
 717         //
 718         // What we're doing is looking for any chain of nodes reaching %z such
 719         // that %x <= %z and %y >= %z, and vice versa. The cool part is that
 720         // every node in between is also equal because of the squeeze principle.
 721
 722         std::vector<Node *> N1_GE, N2_LE, N1_LE, N2_GE;
 723         IG.transitiveClosure(N1, InequalityGraph::GE, back_inserter(N1_GE));
 724         std::sort(N1_GE.begin(), N1_GE.end());
 725         N1_GE.erase(std::unique(N1_GE.begin(), N1_GE.end()), N1_GE.end());
 726         IG.transitiveClosure(N2, InequalityGraph::LE, back_inserter(N2_LE));
 727         std::sort(N1_LE.begin(), N1_LE.end());
 728         N1_LE.erase(std::unique(N1_LE.begin(), N1_LE.end()), N1_LE.end());
 729         IG.transitiveClosure(N1, InequalityGraph::LE, back_inserter(N1_LE));
 730         std::sort(N2_GE.begin(), N2_GE.end());
 731         N2_GE.erase(std::unique(N2_GE.begin(), N2_GE.end()), N2_GE.end());
 732         std::unique(N2_GE.begin(), N2_GE.end());
 733         IG.transitiveClosure(N2, InequalityGraph::GE, back_inserter(N2_GE));
 734         std::sort(N2_LE.begin(), N2_LE.end());
 735         N2_LE.erase(std::unique(N2_LE.begin(), N2_LE.end()), N2_LE.end());
 736
 737         std::vector<Node *> Set1, Set2;
 738         std::set_intersection(N1_GE.begin(), N1_GE.end(),
 739                               N2_LE.begin(), N2_LE.end(),
 740                               back_inserter(Set1));
 741         std::set_intersection(N1_LE.begin(), N1_LE.end(),
 742                               N2_GE.begin(), N2_GE.end(),
 743                               back_inserter(Set2));
 744
 745         std::vector<Node *> Equal;
 746         std::set_union(Set1.begin(), Set1.end(), Set2.begin(), Set2.end(),
 747                        back_inserter(Equal));
 748
 749         Value *Best = N1->getValue();
 750         if (compare(N2->getValue(), Best)) Best = N2->getValue();
 751
 752         for (std::vector<Node *>::iterator I = Equal.begin(), E = Equal.end();
 753              I != E; ++I) {
 754           Value *V = (*I)->getValue();
 755           if (compare(V, Best)) Best = V;
 756         }
 757
 758         Equal.push_back(N2);
 759         IG.mergeNodes(N1, Equal, Best);
 760       }
 761       if (!N1 && !N2) IG.addEqual(IG.newNode(V1), V2);
 762
 763       addRecursive(V1);
 764       addRecursive(V2);
 765
 766       return true;
 767     }
 768
 769     bool addNotEqual(Value *V1, Value *V2) {
 770       //DOUT << "addNotEqual(" << *V1 << ", " << *V2 << ")\n");
 771       if (isNotEqual(V1, V2)) return true;
 772
 773       // Never permit %x NE true/false.
 774       if (ConstantBool *B1 = dyn_cast<ConstantBool>(V1)) {
 775         return addEqual(ConstantBool::get(!B1->getValue()), V2);
 776       } else if (ConstantBool *B2 = dyn_cast<ConstantBool>(V2)) {
 777         return addEqual(V1, ConstantBool::get(!B2->getValue()));
 778       }
 779
 780       Node *N1 = IG.getOrInsertNode(V1),
 781            *N2 = IG.getOrInsertNode(V2);
 782
 783       if (N1 == N2) return false;
 784
 785       IG.addNotEqual(N1, N2);
 786
 787       addRecursive(V1);
 788       addRecursive(V2);
 789
 790       return true;
 791     }
 792
 793     /// Set V1 less than V2.
 794     bool addLess(Value *V1, Value *V2) {
 795       if (isLess(V1, V2)) return true;
 796       if (isGreaterEqual(V1, V2)) return false;
 797
 798       Node *N1 = IG.getOrInsertNode(V1), *N2 = IG.getOrInsertNode(V2);
 799
 800       if (N1 == N2) return false;
 801
 802       IG.addLess(N1, N2);
 803
 804       addRecursive(V1);
 805       addRecursive(V2);
 806
 807       return true;
 808     }
 809
 810     /// Set V1 less than or equal to V2.
 811     bool addLessEqual(Value *V1, Value *V2) {
 812       if (isLessEqual(V1, V2)) return true;
 813       if (V1 == V2) return true;
 814
 815       if (isLessEqual(V2, V1))
 816         return addEqual(V1, V2);
 817
 818       if (isGreater(V1, V2)) return false;
 819
 820       Node *N1 = IG.getOrInsertNode(V1),
 821            *N2 = IG.getOrInsertNode(V2);
 822
 823       if (N1 == N2) return true;
 824
 825       IG.addLessEqual(N1, N2);
 826
 827       addRecursive(V1);
 828       addRecursive(V2);
 829
 830       return true;
 831     }
 832
 833     void solve() {
 834       DOUT << "WorkList entry, size: " << WorkList.size() << "\n";
 835       while (!WorkList.empty()) {
 836         DOUT << "WorkList size: " << WorkList.size() << "\n";
 837
 838         Instruction *I = WorkList.front();
 839         WorkList.pop_front();
 840
 841         Value *Canonical = cIG.canonicalize(I);
 842         const Type *Ty = I->getType();
 843
 844         //DOUT << "solving: " << *I << "\n";
 845         //DEBUG(IG.debug(*cerr.stream()));
 846
 847         if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
 848           Value *Op0 = cIG.canonicalize(BO->getOperand(0)),
 849                 *Op1 = cIG.canonicalize(BO->getOperand(1));
 850
 851           ConstantIntegral *CI1 = dyn_cast<ConstantIntegral>(Op0),
 852                            *CI2 = dyn_cast<ConstantIntegral>(Op1);
 853
 854           if (CI1 && CI2)
 855             addEqual(BO, ConstantExpr::get(BO->getOpcode(), CI1, CI2));
 856
 857           switch (BO->getOpcode()) {
 858             case Instruction::SetEQ:
 859               // "seteq int %a, %b" EQ true  then %a EQ %b
 860               // "seteq int %a, %b" EQ false then %a NE %b
 861               if (Canonical == ConstantBool::getTrue())
 862                 addEqual(Op0, Op1);
 863               else if (Canonical == ConstantBool::getFalse())
 864                 addNotEqual(Op0, Op1);
 865
 866               // %a EQ %b then "seteq int %a, %b" EQ true
 867               // %a NE %b then "seteq int %a, %b" EQ false
 868               if (isEqual(Op0, Op1))
 869                 addEqual(BO, ConstantBool::getTrue());
 870               else if (isNotEqual(Op0, Op1))
 871                 addEqual(BO, ConstantBool::getFalse());
 872
 873               break;
 874             case Instruction::SetNE:
 875               // "setne int %a, %b" EQ true  then %a NE %b
 876               // "setne int %a, %b" EQ false then %a EQ %b
 877               if (Canonical == ConstantBool::getTrue())
 878                 addNotEqual(Op0, Op1);
 879               else if (Canonical == ConstantBool::getFalse())
 880                 addEqual(Op0, Op1);
 881
 882               // %a EQ %b then "setne int %a, %b" EQ false
 883               // %a NE %b then "setne int %a, %b" EQ true
 884               if (isEqual(Op0, Op1))
 885                 addEqual(BO, ConstantBool::getFalse());
 886               else if (isNotEqual(Op0, Op1))
 887                 addEqual(BO, ConstantBool::getTrue());
 888
 889               break;
 890             case Instruction::SetLT:
 891               // "setlt int %a, %b" EQ true  then %a LT %b
 892               // "setlt int %a, %b" EQ false then %b LE %a
 893               if (Canonical == ConstantBool::getTrue())
 894                 addLess(Op0, Op1);
 895               else if (Canonical == ConstantBool::getFalse())
 896                 addLessEqual(Op1, Op0);
 897
 898               // %a LT %b then "setlt int %a, %b" EQ true
 899               // %a GE %b then "setlt int %a, %b" EQ false
 900               if (isLess(Op0, Op1))
 901                 addEqual(BO, ConstantBool::getTrue());
 902               else if (isGreaterEqual(Op0, Op1))
 903                 addEqual(BO, ConstantBool::getFalse());
 904
 905               break;
 906             case Instruction::SetLE:
 907               // "setle int %a, %b" EQ true  then %a LE %b
 908               // "setle int %a, %b" EQ false then %b LT %a
 909               if (Canonical == ConstantBool::getTrue())
 910                 addLessEqual(Op0, Op1);
 911               else if (Canonical == ConstantBool::getFalse())
 912                 addLess(Op1, Op0);
 913
 914               // %a LE %b then "setle int %a, %b" EQ true
 915               // %a GT %b then "setle int %a, %b" EQ false
 916               if (isLessEqual(Op0, Op1))
 917                 addEqual(BO, ConstantBool::getTrue());
 918               else if (isGreater(Op0, Op1))
 919                 addEqual(BO, ConstantBool::getFalse());
 920
 921               break;
 922             case Instruction::SetGT:
 923               // "setgt int %a, %b" EQ true  then %b LT %a
 924               // "setgt int %a, %b" EQ false then %a LE %b
 925               if (Canonical == ConstantBool::getTrue())
 926                 addLess(Op1, Op0);
 927               else if (Canonical == ConstantBool::getFalse())
 928                 addLessEqual(Op0, Op1);
 929
 930               // %a GT %b then "setgt int %a, %b" EQ true
 931               // %a LE %b then "setgt int %a, %b" EQ false
 932               if (isGreater(Op0, Op1))
 933                 addEqual(BO, ConstantBool::getTrue());
 934               else if (isLessEqual(Op0, Op1))
 935                 addEqual(BO, ConstantBool::getFalse());
 936
 937               break;
 938             case Instruction::SetGE:
 939               // "setge int %a, %b" EQ true  then %b LE %a
 940               // "setge int %a, %b" EQ false then %a LT %b
 941               if (Canonical == ConstantBool::getTrue())
 942                 addLessEqual(Op1, Op0);
 943               else if (Canonical == ConstantBool::getFalse())
 944                 addLess(Op0, Op1);
 945
 946               // %a GE %b then "setge int %a, %b" EQ true
 947               // %a LT %b then "setlt int %a, %b" EQ false
 948               if (isGreaterEqual(Op0, Op1))
 949                 addEqual(BO, ConstantBool::getTrue());
 950               else if (isLess(Op0, Op1))
 951                 addEqual(BO, ConstantBool::getFalse());
 952
 953               break;
 954             case Instruction::And: {
 955               // "and int %a, %b"  EQ -1   then %a EQ -1   and %b EQ -1
 956               // "and bool %a, %b" EQ true then %a EQ true and %b EQ true
 957               ConstantIntegral *CI = ConstantIntegral::getAllOnesValue(Ty);
 958               if (Canonical == CI) {
 959                 addEqual(CI, Op0);
 960                 addEqual(CI, Op1);
 961               }
 962             } break;
 963             case Instruction::Or: {
 964               // "or int %a, %b"  EQ 0     then %a EQ 0     and %b EQ 0
 965               // "or bool %a, %b" EQ false then %a EQ false and %b EQ false
 966               Constant *Zero = Constant::getNullValue(Ty);
 967               if (Canonical == Zero) {
 968                 addEqual(Zero, Op0);
 969                 addEqual(Zero, Op1);
 970               }
 971             } break;
 972             case Instruction::Xor: {
 973               // "xor bool true,  %a" EQ true  then %a EQ false
 974               // "xor bool true,  %a" EQ false then %a EQ true
 975               // "xor bool false, %a" EQ true  then %a EQ true
 976               // "xor bool false, %a" EQ false then %a EQ false
 977               // "xor int %c, %a" EQ %c then %a EQ 0
 978               // "xor int %c, %a" NE %c then %a NE 0
 979               // 1. Repeat all of the above, with order of operands reversed.
 980               Value *LHS = Op0, *RHS = Op1;
 981               if (!isa<Constant>(LHS)) std::swap(LHS, RHS);
 982
 983               if (ConstantBool *CB = dyn_cast<ConstantBool>(Canonical)) {
 984                 if (ConstantBool *A = dyn_cast<ConstantBool>(LHS))
 985                   addEqual(RHS, ConstantBool::get(A->getValue() ^
 986                                                   CB->getValue()));
 987               }
 988               if (Canonical == LHS) {
 989                 if (isa<ConstantIntegral>(Canonical))
 990                   addEqual(RHS, Constant::getNullValue(Ty));
 991               } else if (isNotEqual(LHS, Canonical)) {
 992                 addNotEqual(RHS, Constant::getNullValue(Ty));
 993               }
 994             } break;
 995             default:
 996               break;
 997           }
 998
 999           // "%x = add int %y, %z" and %x EQ %y then %z EQ 0
1000           // "%x = mul int %y, %z" and %x EQ %y then %z EQ 1
1001           // 1. Repeat all of the above, with order of operands reversed.
1002           // "%x = fdiv float %y, %z" and %x EQ %y then %z EQ 1
1003           Value *Known = Op0, *Unknown = Op1;
1004           if (Known != BO) std::swap(Known, Unknown);
1005           if (Known == BO) {
1006             switch (BO->getOpcode()) {
1007               default: break;
1008               case Instruction::Xor:
1009               case Instruction::Or:
1010               case Instruction::Add:
1011               case Instruction::Sub:
1012                 if (!Ty->isFloatingPoint())
1013                   addEqual(Unknown, Constant::getNullValue(Ty));
1014                 break;
1015               case Instruction::UDiv:
1016               case Instruction::SDiv:
1017               case Instruction::FDiv:
1018                 if (Unknown == Op0) break; // otherwise, fallthrough
1019               case Instruction::And:
1020               case Instruction::Mul:
1021                 Constant *One = NULL;
1022                 if (isa<ConstantInt>(Unknown))
1023                   One = ConstantInt::get(Ty, 1);
1024                 else if (isa<ConstantFP>(Unknown))
1025                   One = ConstantFP::get(Ty, 1);
1026                 else if (isa<ConstantBool>(Unknown))
1027                   One = ConstantBool::getTrue();
1028
1029                 if (One) addEqual(Unknown, One);
1030                 break;
1031             }
1032           }
1033         } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
1034           // Given: "%a = select bool %x, int %b, int %c"
1035           // %a EQ %b then %x EQ true
1036           // %a EQ %c then %x EQ false
1037           if (isEqual(I, SI->getTrueValue()) ||
1038               isNotEqual(I, SI->getFalseValue()))
1039             addEqual(SI->getCondition(), ConstantBool::getTrue());
1040           else if (isEqual(I, SI->getFalseValue()) ||
1041                    isNotEqual(I, SI->getTrueValue()))
1042             addEqual(SI->getCondition(), ConstantBool::getFalse());
1043
1044           // %x EQ true  then %a EQ %b
1045           // %x EQ false then %a NE %b
1046           if (isEqual(SI->getCondition(), ConstantBool::getTrue()))
1047             addEqual(SI, SI->getTrueValue());
1048           else if (isEqual(SI->getCondition(), ConstantBool::getFalse()))
1049             addEqual(SI, SI->getFalseValue());
1050         }
1051       }
1052     }
1053   };
1054
1055   /// PredicateSimplifier - This class is a simplifier that replaces
1056   /// one equivalent variable with another. It also tracks what
1057   /// can't be equal and will solve setcc instructions when possible.
1058   /// @brief Root of the predicate simplifier optimization.
1059   class VISIBILITY_HIDDEN PredicateSimplifier : public FunctionPass {
1060     DominatorTree *DT;
1061     ETForest *Forest;
1062     bool modified;
1063
1064     class State {
1065     public:
1066       BasicBlock *ToVisit;
1067       InequalityGraph *IG;
1068
1069       State(BasicBlock *BB, InequalityGraph *IG) : ToVisit(BB), IG(IG) {}
1070     };
1071
1072     std::vector<State> WorkList;
1073
1074   public:
1075     bool runOnFunction(Function &F);
1076
1077     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1078       AU.addRequiredID(BreakCriticalEdgesID);
1079       AU.addRequired<DominatorTree>();
1080       AU.addRequired<ETForest>();
1081       AU.setPreservesCFG();
1082       AU.addPreservedID(BreakCriticalEdgesID);
1083     }
1084
1085   private:
1086     /// Forwards - Adds new properties into PropertySet and uses them to
1087     /// simplify instructions. Because new properties sometimes apply to
1088     /// a transition from one BasicBlock to another, this will use the
1089     /// PredicateSimplifier::proceedToSuccessor(s) interface to enter the
1090     /// basic block with the new PropertySet.
1091     /// @brief Performs abstract execution of the program.
1092     class VISIBILITY_HIDDEN Forwards : public InstVisitor<Forwards> {
1093       friend class InstVisitor<Forwards>;
1094       PredicateSimplifier *PS;
1095
1096     public:
1097       InequalityGraph &IG;
1098
1099       Forwards(PredicateSimplifier *PS, InequalityGraph &IG)
1100         : PS(PS), IG(IG) {}
1101
1102       void visitTerminatorInst(TerminatorInst &TI);
1103       void visitBranchInst(BranchInst &BI);
1104       void visitSwitchInst(SwitchInst &SI);
1105
1106       void visitAllocaInst(AllocaInst &AI);
1107       void visitLoadInst(LoadInst &LI);
1108       void visitStoreInst(StoreInst &SI);
1109
1110       void visitBinaryOperator(BinaryOperator &BO);
1111     };
1112
1113     // Used by terminator instructions to proceed from the current basic
1114     // block to the next. Verifies that "current" dominates "next",
1115     // then calls visitBasicBlock.
1116     void proceedToSuccessors(const InequalityGraph &IG, BasicBlock *BBCurrent) {
1117       DominatorTree::Node *Current = DT->getNode(BBCurrent);
1118       for (DominatorTree::Node::iterator I = Current->begin(),
1119            E = Current->end(); I != E; ++I) {
1120         //visitBasicBlock((*I)->getBlock(), IG);
1121         WorkList.push_back(State((*I)->getBlock(), new InequalityGraph(IG)));
1122       }
1123     }
1124
1125     void proceedToSuccessor(InequalityGraph *NextIG, BasicBlock *Next) {
1126       //visitBasicBlock(Next, NextIG);
1127       WorkList.push_back(State(Next, NextIG));
1128     }
1129
1130     // Visits each instruction in the basic block.
1131     void visitBasicBlock(BasicBlock *BB, InequalityGraph &IG) {
1132       DOUT << "Entering Basic Block: " << BB->getName() << "\n";
1133       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
1134         visitInstruction(I++, IG);
1135       }
1136     }
1137
1138     // Tries to simplify each Instruction and add new properties to
1139     // the PropertySet.
1140     void visitInstruction(Instruction *I, InequalityGraph &IG) {
1141       DOUT << "Considering instruction " << *I << "\n";
1142       DEBUG(IG.debug(*cerr.stream()));
1143
1144       // Sometimes instructions are made dead due to earlier analysis.
1145       if (isInstructionTriviallyDead(I)) {
1146         I->eraseFromParent();
1147         return;
1148       }
1149
1150       // Try to replace the whole instruction.
1151       Value *V = IG.canonicalize(I);
1152       if (V != I) {
1153         modified = true;
1154         ++NumInstruction;
1155         DOUT << "Removing " << *I << ", replacing with " << *V << "\n";
1156         IG.remove(I);
1157         I->replaceAllUsesWith(V);
1158         I->eraseFromParent();
1159         return;
1160       }
1161
1162       // Try to substitute operands.
1163       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
1164         Value *Oper = I->getOperand(i);
1165         Value *V = IG.canonicalize(Oper);
1166         if (V != Oper) {
1167           modified = true;
1168           ++NumVarsReplaced;
1169           DOUT << "Resolving " << *I;
1170           I->setOperand(i, V);
1171           DOUT << " into " << *I;
1172         }
1173       }
1174
1175       //DOUT << "push (%" << I->getParent()->getName() << ")\n";
1176       Forwards visit(this, IG);
1177       visit.visit(*I);
1178       //DOUT << "pop (%" << I->getParent()->getName() << ")\n";
1179     }
1180   };
1181
1182   bool PredicateSimplifier::runOnFunction(Function &F) {
1183     DT = &getAnalysis<DominatorTree>();
1184     Forest = &getAnalysis<ETForest>();
1185
1186     DOUT << "Entering Function: " << F.getName() << "\n";
1187
1188     modified = false;
1189     WorkList.push_back(State(DT->getRoot(), new InequalityGraph()));
1190
1191     do {
1192       State S = WorkList.back();
1193       WorkList.pop_back();
1194       visitBasicBlock(S.ToVisit, *S.IG);
1195       delete S.IG;
1196     } while (!WorkList.empty());
1197
1198     //DEBUG(F.viewCFG());
1199
1200     return modified;
1201   }
1202
1203   void PredicateSimplifier::Forwards::visitTerminatorInst(TerminatorInst &TI) {
1204     PS->proceedToSuccessors(IG, TI.getParent());
1205   }
1206
1207   void PredicateSimplifier::Forwards::visitBranchInst(BranchInst &BI) {
1208     BasicBlock *BB = BI.getParent();
1209
1210     if (BI.isUnconditional()) {
1211       PS->proceedToSuccessors(IG, BB);
1212       return;
1213     }
1214
1215     Value *Condition = BI.getCondition();
1216     BasicBlock *TrueDest  = BI.getSuccessor(0),
1217                *FalseDest = BI.getSuccessor(1);
1218
1219     if (isa<ConstantBool>(Condition) || TrueDest == FalseDest) {
1220       PS->proceedToSuccessors(IG, BB);
1221       return;
1222     }
1223
1224     DominatorTree::Node *Node = PS->DT->getNode(BB);
1225     for (DominatorTree::Node::iterator I = Node->begin(), E = Node->end();
1226          I != E; ++I) {
1227       BasicBlock *Dest = (*I)->getBlock();
1228       InequalityGraph *DestProperties = new InequalityGraph(IG);
1229       VRPSolver Solver(*DestProperties, PS->Forest, Dest);
1230
1231       if (Dest == TrueDest) {
1232         DOUT << "(" << BB->getName() << ") true set:\n";
1233         if (!Solver.addEqual(ConstantBool::getTrue(), Condition)) continue;
1234         Solver.solve();
1235         DEBUG(DestProperties->debug(*cerr.stream()));
1236       } else if (Dest == FalseDest) {
1237         DOUT << "(" << BB->getName() << ") false set:\n";
1238         if (!Solver.addEqual(ConstantBool::getFalse(), Condition)) continue;
1239         Solver.solve();
1240         DEBUG(DestProperties->debug(*cerr.stream()));
1241       }
1242
1243       PS->proceedToSuccessor(DestProperties, Dest);
1244     }
1245   }
1246
1247   void PredicateSimplifier::Forwards::visitSwitchInst(SwitchInst &SI) {
1248     Value *Condition = SI.getCondition();
1249
1250     // Set the EQProperty in each of the cases BBs, and the NEProperties
1251     // in the default BB.
1252     // InequalityGraph DefaultProperties(IG);
1253
1254     DominatorTree::Node *Node = PS->DT->getNode(SI.getParent());
1255     for (DominatorTree::Node::iterator I = Node->begin(), E = Node->end();
1256          I != E; ++I) {
1257       BasicBlock *BB = (*I)->getBlock();
1258
1259       InequalityGraph *BBProperties = new InequalityGraph(IG);
1260       VRPSolver Solver(*BBProperties, PS->Forest, BB);
1261       if (BB == SI.getDefaultDest()) {
1262         for (unsigned i = 1, e = SI.getNumCases(); i < e; ++i)
1263           if (SI.getSuccessor(i) != BB)
1264             if (!Solver.addNotEqual(Condition, SI.getCaseValue(i))) continue;
1265         Solver.solve();
1266       } else if (ConstantInt *CI = SI.findCaseDest(BB)) {
1267         if (!Solver.addEqual(Condition, CI)) continue;
1268         Solver.solve();
1269       }
1270       PS->proceedToSuccessor(BBProperties, BB);
1271     }
1272   }
1273
1274   void PredicateSimplifier::Forwards::visitAllocaInst(AllocaInst &AI) {
1275     VRPSolver VRP(IG, PS->Forest, AI.getParent());
1276     VRP.addNotEqual(Constant::getNullValue(AI.getType()), &AI);
1277     VRP.solve();
1278   }
1279
1280   void PredicateSimplifier::Forwards::visitLoadInst(LoadInst &LI) {
1281     Value *Ptr = LI.getPointerOperand();
1282     // avoid "load uint* null" -> null NE null.
1283     if (isa<Constant>(Ptr)) return;
1284
1285     VRPSolver VRP(IG, PS->Forest, LI.getParent());
1286     VRP.addNotEqual(Constant::getNullValue(Ptr->getType()), Ptr);
1287     VRP.solve();
1288   }
1289
1290   void PredicateSimplifier::Forwards::visitStoreInst(StoreInst &SI) {
1291     Value *Ptr = SI.getPointerOperand();
1292     if (isa<Constant>(Ptr)) return;
1293
1294     VRPSolver VRP(IG, PS->Forest, SI.getParent());
1295     VRP.addNotEqual(Constant::getNullValue(Ptr->getType()), Ptr);
1296     VRP.solve();
1297   }
1298
1299   void PredicateSimplifier::Forwards::visitBinaryOperator(BinaryOperator &BO) {
1300     Instruction::BinaryOps ops = BO.getOpcode();
1301
1302     switch (ops) {
1303     case Instruction::URem:
1304     case Instruction::SRem:
1305     case Instruction::FRem:
1306     case Instruction::UDiv:
1307     case Instruction::SDiv:
1308     case Instruction::FDiv: {
1309       Value *Divisor = BO.getOperand(1);
1310       VRPSolver VRP(IG, PS->Forest, BO.getParent());
1311       VRP.addNotEqual(Constant::getNullValue(Divisor->getType()), Divisor);
1312       VRP.solve();
1313       break;
1314     }
1315     default:
1316       break;
1317     }
1318   }
1319
1320
1321   RegisterPass<PredicateSimplifier> X("predsimplify",
1322                                       "Predicate Simplifier");
1323 }
1324
1325 FunctionPass *llvm::createPredicateSimplifierPass() {
1326   return new PredicateSimplifier();
1327 }