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