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 optimization works by substituting %q for %p when protected by a
  26 // conditional that assures us of that fact. Properties are stored as
  27 // relationships between two values.
  28 //
  29 //===------------------------------------------------------------------===//
  30
  31 #define DEBUG_TYPE "predsimplify"
  32 #include "llvm/Transforms/Scalar.h"
  33 #include "llvm/Constants.h"
  34 #include "llvm/Instructions.h"
  35 #include "llvm/Pass.h"
  36 #include "llvm/ADT/Statistic.h"
  37 #include "llvm/ADT/STLExtras.h"
  38 #include "llvm/Analysis/Dominators.h"
  39 #include "llvm/Support/CFG.h"
  40 #include "llvm/Support/Debug.h"
  41 #include "llvm/Support/InstVisitor.h"
  42 #include <iostream>
  43 using namespace llvm;
  44
  45 typedef DominatorTree::Node DTNodeType;
  46
  47 namespace {
  48   Statistic<>
  49   NumVarsReplaced("predsimplify", "Number of argument substitutions");
  50   Statistic<>
  51   NumInstruction("predsimplify", "Number of instructions removed");
  52
  53   class PropertySet;
  54
  55   /// Similar to EquivalenceClasses, this stores the set of equivalent
  56   /// types. Beyond EquivalenceClasses, it allows us to specify which
  57   /// element will act as leader.
  58   template<typename ElemTy>
  59   class VISIBILITY_HIDDEN Synonyms {
  60     std::map<ElemTy, unsigned> mapping;
  61     std::vector<ElemTy> leaders;
  62     PropertySet *PS;
  63
  64   public:
  65     typedef unsigned iterator;
  66     typedef const unsigned const_iterator;
  67
  68     Synonyms(PropertySet *PS) : PS(PS) {}
  69
  70     // Inspection
  71
  72     bool empty() const {
  73       return leaders.empty();
  74     }
  75
  76     iterator findLeader(ElemTy e) {
  77       typename std::map<ElemTy, unsigned>::iterator MI = mapping.find(e);
  78       if (MI == mapping.end()) return 0;
  79
  80       return MI->second;
  81     }
  82
  83     const_iterator findLeader(ElemTy e) const {
  84       typename std::map<ElemTy, unsigned>::const_iterator MI =
  85           mapping.find(e);
  86       if (MI == mapping.end()) return 0;
  87
  88       return MI->second;
  89     }
  90
  91     ElemTy &getLeader(iterator I) {
  92       assert(I && I <= leaders.size() && "Illegal leader to get.");
  93       return leaders[I-1];
  94     }
  95
  96     const ElemTy &getLeader(const_iterator I) const {
  97       assert(I && I <= leaders.size() && "Illegal leaders to get.");
  98       return leaders[I-1];
  99     }
 100
 101 #ifdef DEBUG
 102     void debug(std::ostream &os) const {
 103       for (unsigned i = 1, e = leaders.size()+1; i != e; ++i) {
 104         os << i << ". " << *getLeader(i) << ": [";
 105         for (std::map<Value *, unsigned>::const_iterator
 106              I = mapping.begin(), E = mapping.end(); I != E; ++I) {
 107           if ((*I).second == i && (*I).first != leaders[i-1]) {
 108             os << *(*I).first << "  ";
 109           }
 110         }
 111         os << "]\n";
 112       }
 113     }
 114 #endif
 115
 116     // Mutators
 117
 118     /// Combine two sets referring to the same element, inserting the
 119     /// elements as needed. Returns a valid iterator iff two already
 120     /// existing disjoint synonym sets were combined. The iterator
 121     /// points to the no longer existing element.
 122     iterator unionSets(ElemTy E1, ElemTy E2);
 123
 124     /// Returns an iterator pointing to the synonym set containing
 125     /// element e. If none exists, a new one is created and returned.
 126     iterator findOrInsert(ElemTy e) {
 127       iterator I = findLeader(e);
 128       if (I) return I;
 129
 130       leaders.push_back(e);
 131       I = leaders.size();
 132       mapping[e] = I;
 133       return I;
 134     }
 135   };
 136
 137   /// Represents the set of equivalent Value*s and provides insertion
 138   /// and fast lookup. Also stores the set of inequality relationships.
 139   class PropertySet {
 140     /// Returns true if V1 is a better choice than V2.
 141     bool compare(Value *V1, Value *V2) const {
 142       if (isa<Constant>(V1)) {
 143         if (!isa<Constant>(V2)) {
 144           return true;
 145         }
 146       } else if (isa<Argument>(V1)) {
 147         if (!isa<Constant>(V2) && !isa<Argument>(V2)) {
 148           return true;
 149         }
 150       }
 151       if (Instruction *I1 = dyn_cast<Instruction>(V1)) {
 152         if (Instruction *I2 = dyn_cast<Instruction>(V2)) {
 153           BasicBlock *BB1 = I1->getParent(),
 154                      *BB2 = I2->getParent();
 155           if (BB1 == BB2) {
 156             for (BasicBlock::const_iterator I = BB1->begin(), E = BB1->end();
 157                  I != E; ++I) {
 158               if (&*I == I1) return true;
 159               if (&*I == I2) return false;
 160             }
 161             assert(0 && "Instructions not found in parent BasicBlock?");
 162           } else
 163             return DT->getNode(BB1)->properlyDominates(DT->getNode(BB2));
 164         }
 165       }
 166       return false;
 167     }
 168
 169     struct Property;
 170   public:
 171     /// Choose the canonical Value in a synonym set.
 172     /// Leaves the more canonical choice in V1.
 173     void order(Value *&V1, Value *&V2) const {
 174       if (compare(V2, V1)) std::swap(V1, V2);
 175     }
 176
 177     PropertySet(DominatorTree *DT) : union_find(this), DT(DT) {}
 178
 179     Synonyms<Value *> union_find;
 180
 181     typedef std::vector<Property>::iterator       PropertyIterator;
 182     typedef std::vector<Property>::const_iterator ConstPropertyIterator;
 183     typedef Synonyms<Value *>::iterator  SynonymIterator;
 184
 185     enum Ops {
 186       EQ,
 187       NE
 188     };
 189
 190     Value *canonicalize(Value *V) const {
 191       Value *C = lookup(V);
 192       return C ? C : V;
 193     }
 194
 195     Value *lookup(Value *V) const {
 196       SynonymIterator SI = union_find.findLeader(V);
 197       if (!SI) return NULL;
 198       return union_find.getLeader(SI);
 199     }
 200
 201     bool empty() const {
 202       return union_find.empty();
 203     }
 204
 205     void addEqual(Value *V1, Value *V2) {
 206       // If %x = 0. and %y = -0., seteq %x, %y is true, but
 207       // copysign(%x) is not the same as copysign(%y).
 208       if (V1->getType()->isFloatingPoint()) return;
 209
 210       order(V1, V2);
 211       if (isa<Constant>(V2)) return; // refuse to set false == true.
 212
 213       SynonymIterator deleted = union_find.unionSets(V1, V2);
 214       if (deleted) {
 215         SynonymIterator replacement = union_find.findLeader(V1);
 216         // Move Properties
 217         for (PropertyIterator I = Properties.begin(), E = Properties.end();
 218              I != E; ++I) {
 219           if (I->I1 == deleted) I->I1 = replacement;
 220           else if (I->I1 > deleted) --I->I1;
 221           if (I->I2 == deleted) I->I2 = replacement;
 222           else if (I->I2 > deleted) --I->I2;
 223         }
 224       }
 225       addImpliedProperties(EQ, V1, V2);
 226     }
 227
 228     void addNotEqual(Value *V1, Value *V2) {
 229       // If %x = NAN then seteq %x, %x is false.
 230       if (V1->getType()->isFloatingPoint()) return;
 231
 232       // For example, %x = setne int 0, 0 causes "0 != 0".
 233       if (isa<Constant>(V1) && isa<Constant>(V2)) return;
 234
 235       if (findProperty(NE, V1, V2) != Properties.end())
 236         return; // found.
 237
 238       // Add the property.
 239       SynonymIterator I1 = union_find.findOrInsert(V1),
 240                       I2 = union_find.findOrInsert(V2);
 241
 242       // Technically this means that the block is unreachable.
 243       if (I1 == I2) return;
 244
 245       Properties.push_back(Property(NE, I1, I2));
 246       addImpliedProperties(NE, V1, V2);
 247     }
 248
 249     PropertyIterator findProperty(Ops Opcode, Value *V1, Value *V2) {
 250       assert(Opcode != EQ && "Can't findProperty on EQ."
 251              "Use the lookup method instead.");
 252
 253       SynonymIterator I1 = union_find.findLeader(V1),
 254                       I2 = union_find.findLeader(V2);
 255       if (!I1 || !I2) return Properties.end();
 256
 257       return
 258       find(Properties.begin(), Properties.end(), Property(Opcode, I1, I2));
 259     }
 260
 261     ConstPropertyIterator
 262     findProperty(Ops Opcode, Value *V1, Value *V2) const {
 263       assert(Opcode != EQ && "Can't findProperty on EQ."
 264              "Use the lookup method instead.");
 265
 266       SynonymIterator I1 = union_find.findLeader(V1),
 267                       I2 = union_find.findLeader(V2);
 268       if (!I1 || !I2) return Properties.end();
 269
 270       return
 271       find(Properties.begin(), Properties.end(), Property(Opcode, I1, I2));
 272     }
 273
 274   private:
 275     // Represents Head OP [Tail1, Tail2, ...]
 276     // For example: %x != %a, %x != %b.
 277     struct VISIBILITY_HIDDEN Property {
 278       typedef SynonymIterator Iter;
 279
 280       Property(Ops opcode, Iter i1, Iter i2)
 281         : Opcode(opcode), I1(i1), I2(i2)
 282       { assert(opcode != EQ && "Equality belongs in the synonym set, "
 283                                "not a property."); }
 284
 285       bool operator==(const Property &P) const {
 286         return (Opcode == P.Opcode) &&
 287                ((I1 == P.I1 && I2 == P.I2) ||
 288                 (I1 == P.I2 && I2 == P.I1));
 289       }
 290
 291       Ops Opcode;
 292       Iter I1, I2;
 293     };
 294
 295     void add(Ops Opcode, Value *V1, Value *V2, bool invert) {
 296       switch (Opcode) {
 297         case EQ:
 298           if (invert) addNotEqual(V1, V2);
 299           else        addEqual(V1, V2);
 300           break;
 301         case NE:
 302           if (invert) addEqual(V1, V2);
 303           else        addNotEqual(V1, V2);
 304           break;
 305         default:
 306           assert(0 && "Unknown property opcode.");
 307       }
 308     }
 309
 310     // Finds the properties implied by an equivalence and adds them too.
 311     // Example: ("seteq %a, %b", true,  EQ) --> (%a, %b, EQ)
 312     //          ("seteq %a, %b", false, EQ) --> (%a, %b, NE)
 313     void addImpliedProperties(Ops Opcode, Value *V1, Value *V2) {
 314       order(V1, V2);
 315
 316       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V2)) {
 317         switch (BO->getOpcode()) {
 318         case Instruction::SetEQ:
 319           if (ConstantBool *V1CB = dyn_cast<ConstantBool>(V1))
 320             add(Opcode, BO->getOperand(0), BO->getOperand(1),!V1CB->getValue());
 321           break;
 322         case Instruction::SetNE:
 323           if (ConstantBool *V1CB = dyn_cast<ConstantBool>(V1))
 324             add(Opcode, BO->getOperand(0), BO->getOperand(1), V1CB->getValue());
 325           break;
 326         case Instruction::SetLT:
 327         case Instruction::SetGT:
 328           if (V1 == ConstantBool::getTrue())
 329             add(Opcode, BO->getOperand(0), BO->getOperand(1), true);
 330           break;
 331         case Instruction::SetLE:
 332         case Instruction::SetGE:
 333           if (V1 == ConstantBool::getFalse())
 334             add(Opcode, BO->getOperand(0), BO->getOperand(1), true);
 335           break;
 336         case Instruction::And:
 337           if (V1 == ConstantBool::getTrue()) {
 338             add(Opcode, V1, BO->getOperand(0), false);
 339             add(Opcode, V1, BO->getOperand(1), false);
 340           }
 341           break;
 342         case Instruction::Or:
 343           if (V1 == ConstantBool::getFalse()) {
 344             add(Opcode, V1, BO->getOperand(0), false);
 345             add(Opcode, V1, BO->getOperand(1), false);
 346           }
 347           break;
 348         case Instruction::Xor:
 349           if (V1 == ConstantBool::getTrue()) {
 350             if (BO->getOperand(0) == V1)
 351               add(Opcode, ConstantBool::getFalse(), BO->getOperand(1), false);
 352             if (BO->getOperand(1) == V1)
 353               add(Opcode, ConstantBool::getFalse(), BO->getOperand(0), false);
 354           }
 355           if (V1 == ConstantBool::getFalse()) {
 356             if (BO->getOperand(0) == ConstantBool::getTrue())
 357               add(Opcode, ConstantBool::getTrue(), BO->getOperand(1), false);
 358             if (BO->getOperand(1) == ConstantBool::getTrue())
 359               add(Opcode, ConstantBool::getTrue(), BO->getOperand(0), false);
 360           }
 361           break;
 362         default:
 363           break;
 364         }
 365       } else if (SelectInst *SI = dyn_cast<SelectInst>(V2)) {
 366         if (Opcode != EQ && Opcode != NE) return;
 367
 368         ConstantBool *True  = ConstantBool::get(Opcode==EQ),
 369                      *False = ConstantBool::get(Opcode!=EQ);
 370
 371         if (V1 == SI->getTrueValue())
 372           addEqual(SI->getCondition(), True);
 373         else if (V1 == SI->getFalseValue())
 374           addEqual(SI->getCondition(), False);
 375         else if (Opcode == EQ)
 376           assert("Result of select not equal to either value.");
 377       }
 378     }
 379
 380     DominatorTree *DT;
 381   public:
 382 #ifdef DEBUG
 383     void debug(std::ostream &os) const {
 384       static const char *OpcodeTable[] = { "EQ", "NE" };
 385
 386       union_find.debug(os);
 387       for (std::vector<Property>::const_iterator I = Properties.begin(),
 388            E = Properties.end(); I != E; ++I) {
 389         os << (*I).I1 << " " << OpcodeTable[(*I).Opcode] << " "
 390            << (*I).I2 << "\n";
 391       }
 392       os << "\n";
 393     }
 394 #endif
 395
 396     std::vector<Property> Properties;
 397   };
 398
 399   /// PredicateSimplifier - This class is a simplifier that replaces
 400   /// one equivalent variable with another. It also tracks what
 401   /// can't be equal and will solve setcc instructions when possible.
 402   class PredicateSimplifier : public FunctionPass {
 403   public:
 404     bool runOnFunction(Function &F);
 405     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 406
 407   private:
 408     /// Backwards - Try to replace the Use of the instruction with
 409     /// something simpler. This resolves a value by walking backwards
 410     /// through its definition and the operands of that definition to
 411     /// see if any values can now be solved for with the properties
 412     /// that are in effect now, but weren't at definition time.
 413     class Backwards : public InstVisitor<Backwards, Value &> {
 414       friend class InstVisitor<Backwards, Value &>;
 415       const PropertySet &KP;
 416
 417       Value &visitSetCondInst(SetCondInst &SCI);
 418       Value &visitBinaryOperator(BinaryOperator &BO);
 419       Value &visitSelectInst(SelectInst &SI);
 420       Value &visitInstruction(Instruction &I);
 421
 422     public:
 423       explicit Backwards(const PropertySet &KP) : KP(KP) {}
 424
 425       Value *resolve(Value *V);
 426     };
 427
 428     /// Forwards - Adds new properties into PropertySet and uses them to
 429     /// simplify instructions. Because new properties sometimes apply to
 430     /// a transition from one BasicBlock to another, this will use the
 431     /// PredicateSimplifier::proceedToSuccessor(s) interface to enter the
 432     /// basic block with the new PropertySet.
 433     class Forwards : public InstVisitor<Forwards> {
 434       friend class InstVisitor<Forwards>;
 435       PredicateSimplifier *PS;
 436     public:
 437       PropertySet &KP;
 438
 439       Forwards(PredicateSimplifier *PS, PropertySet &KP) : PS(PS), KP(KP) {}
 440
 441       // Tries to simplify each Instruction and add new properties to
 442       // the PropertySet. Returns true if it erase the instruction.
 443       //void visitInstruction(Instruction *I);
 444
 445       void visitTerminatorInst(TerminatorInst &TI);
 446       void visitBranchInst(BranchInst &BI);
 447       void visitSwitchInst(SwitchInst &SI);
 448
 449       void visitLoadInst(LoadInst &LI);
 450       void visitStoreInst(StoreInst &SI);
 451       void visitBinaryOperator(BinaryOperator &BO);
 452     };
 453
 454     // Used by terminator instructions to proceed from the current basic
 455     // block to the next. Verifies that "current" dominates "next",
 456     // then calls visitBasicBlock.
 457     void proceedToSuccessors(PropertySet &CurrentPS, BasicBlock *Current);
 458     void proceedToSuccessor(PropertySet &Properties, BasicBlock *Next);
 459
 460     // Visits each instruction in the basic block.
 461     void visitBasicBlock(BasicBlock *Block, PropertySet &KnownProperties);
 462
 463     // Tries to simplify each Instruction and add new properties to
 464     // the PropertySet.
 465     void visitInstruction(Instruction *I, PropertySet &);
 466
 467     DominatorTree *DT;
 468     bool modified;
 469   };
 470
 471   RegisterPass<PredicateSimplifier> X("predsimplify",
 472                                       "Predicate Simplifier");
 473
 474   template <typename ElemTy>
 475   typename Synonyms<ElemTy>::iterator
 476   Synonyms<ElemTy>::unionSets(ElemTy E1, ElemTy E2) {
 477     PS->order(E1, E2);
 478
 479     iterator I1 = findLeader(E1),
 480              I2 = findLeader(E2);
 481
 482     if (!I1 && !I2) { // neither entry is in yet
 483       leaders.push_back(E1);
 484       I1 = leaders.size();
 485       mapping[E1] = I1;
 486       mapping[E2] = I1;
 487       return 0;
 488     }
 489
 490     if (!I1 && I2) {
 491       mapping[E1] = I2;
 492       std::swap(getLeader(I2), E1);
 493       return 0;
 494     }
 495
 496     if (I1 && !I2) {
 497       mapping[E2] = I1;
 498       return 0;
 499     }
 500
 501     if (I1 == I2) return 0;
 502
 503     // This is the case where we have two sets, [%a1, %a2, %a3] and
 504     // [%p1, %p2, %p3] and someone says that %a2 == %p3. We need to
 505     // combine the two synsets.
 506
 507     if (I1 > I2) --I1;
 508
 509     for (std::map<Value *, unsigned>::iterator I = mapping.begin(),
 510          E = mapping.end(); I != E; ++I) {
 511       if (I->second == I2) I->second = I1;
 512       else if (I->second > I2) --I->second;
 513     }
 514
 515     leaders.erase(leaders.begin() + I2 - 1);
 516
 517     return I2;
 518   }
 519 }
 520
 521 FunctionPass *llvm::createPredicateSimplifierPass() {
 522   return new PredicateSimplifier();
 523 }
 524
 525 bool PredicateSimplifier::runOnFunction(Function &F) {
 526   DT = &getAnalysis<DominatorTree>();
 527
 528   modified = false;
 529   PropertySet KnownProperties(DT);
 530   visitBasicBlock(DT->getRootNode()->getBlock(), KnownProperties);
 531   return modified;
 532 }
 533
 534 void PredicateSimplifier::getAnalysisUsage(AnalysisUsage &AU) const {
 535   AU.addRequiredID(BreakCriticalEdgesID);
 536   AU.addRequired<DominatorTree>();
 537   AU.setPreservesCFG();
 538   AU.addPreservedID(BreakCriticalEdgesID);
 539 }
 540
 541 Value &PredicateSimplifier::Backwards::visitSetCondInst(SetCondInst &SCI) {
 542   Value &vBO = visitBinaryOperator(SCI);
 543   if (&vBO !=  &SCI) return vBO;
 544
 545   Value *SCI0 = resolve(SCI.getOperand(0)),
 546         *SCI1 = resolve(SCI.getOperand(1));
 547
 548   PropertySet::ConstPropertyIterator NE =
 549       KP.findProperty(PropertySet::NE, SCI0, SCI1);
 550
 551   if (NE != KP.Properties.end()) {
 552     switch (SCI.getOpcode()) {
 553       case Instruction::SetEQ: return *ConstantBool::getFalse();
 554       case Instruction::SetNE: return *ConstantBool::getTrue();
 555       case Instruction::SetLE:
 556       case Instruction::SetGE:
 557       case Instruction::SetLT:
 558       case Instruction::SetGT:
 559         break;
 560       default:
 561         assert(0 && "Unknown opcode in SetCondInst.");
 562         break;
 563     }
 564   }
 565   return SCI;
 566 }
 567
 568 Value &PredicateSimplifier::Backwards::visitBinaryOperator(BinaryOperator &BO) {
 569   Value *V = KP.canonicalize(&BO);
 570   if (V != &BO) return *V;
 571
 572   Value *lhs = resolve(BO.getOperand(0)),
 573         *rhs = resolve(BO.getOperand(1));
 574
 575   ConstantIntegral *CI1 = dyn_cast<ConstantIntegral>(lhs),
 576                    *CI2 = dyn_cast<ConstantIntegral>(rhs);
 577
 578   if (CI1 && CI2) return *ConstantExpr::get(BO.getOpcode(), CI1, CI2);
 579
 580   return BO;
 581 }
 582
 583 Value &PredicateSimplifier::Backwards::visitSelectInst(SelectInst &SI) {
 584   Value *V = KP.canonicalize(&SI);
 585   if (V != &SI) return *V;
 586
 587   Value *Condition = resolve(SI.getCondition());
 588   if (ConstantBool *CB = dyn_cast<ConstantBool>(Condition))
 589     return *resolve(CB->getValue() ? SI.getTrueValue() : SI.getFalseValue());
 590   return SI;
 591 }
 592
 593 Value &PredicateSimplifier::Backwards::visitInstruction(Instruction &I) {
 594   return *KP.canonicalize(&I);
 595 }
 596
 597 Value *PredicateSimplifier::Backwards::resolve(Value *V) {
 598   if (isa<Constant>(V) || isa<BasicBlock>(V) || KP.empty()) return V;
 599
 600   if (Instruction *I = dyn_cast<Instruction>(V)) return &visit(*I);
 601   return KP.canonicalize(V);
 602 }
 603
 604 void PredicateSimplifier::visitBasicBlock(BasicBlock *BB,
 605                                           PropertySet &KnownProperties) {
 606   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
 607     visitInstruction(I++, KnownProperties);
 608   }
 609 }
 610
 611 void PredicateSimplifier::visitInstruction(Instruction *I,
 612                                            PropertySet &KnownProperties) {
 613   // Try to replace the whole instruction.
 614   Backwards resolve(KnownProperties);
 615   Value *V = resolve.resolve(I);
 616   if (V != I) {
 617     modified = true;
 618     ++NumInstruction;
 619     DEBUG(std::cerr << "Removing " << *I);
 620     I->replaceAllUsesWith(V);
 621     I->eraseFromParent();
 622     return;
 623   }
 624
 625   // Try to substitute operands.
 626   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 627     Value *Oper = I->getOperand(i);
 628     Value *V = resolve.resolve(Oper);
 629     if (V != Oper) {
 630       modified = true;
 631       ++NumVarsReplaced;
 632       DEBUG(std::cerr << "Resolving " << *I);
 633       I->setOperand(i, V);
 634       DEBUG(std::cerr << "into " << *I);
 635     }
 636   }
 637
 638   Forwards visit(this, KnownProperties);
 639   visit.visit(*I);
 640 }
 641
 642 void PredicateSimplifier::proceedToSuccessors(PropertySet &KP,
 643                                               BasicBlock *BBCurrent) {
 644   DTNodeType *Current = DT->getNode(BBCurrent);
 645   for (DTNodeType::iterator I = Current->begin(), E = Current->end();
 646        I != E; ++I) {
 647     PropertySet Copy(KP);
 648     visitBasicBlock((*I)->getBlock(), Copy);
 649   }
 650 }
 651
 652 void PredicateSimplifier::proceedToSuccessor(PropertySet &KP, BasicBlock *BB) {
 653   visitBasicBlock(BB, KP);
 654 }
 655
 656 void PredicateSimplifier::Forwards::visitTerminatorInst(TerminatorInst &TI) {
 657   PS->proceedToSuccessors(KP, TI.getParent());
 658 }
 659
 660 void PredicateSimplifier::Forwards::visitBranchInst(BranchInst &BI) {
 661   BasicBlock *BB = BI.getParent();
 662
 663   if (BI.isUnconditional()) {
 664     PS->proceedToSuccessors(KP, BB);
 665     return;
 666   }
 667
 668   Value *Condition = BI.getCondition();
 669
 670   BasicBlock *TrueDest  = BI.getSuccessor(0),
 671              *FalseDest = BI.getSuccessor(1);
 672
 673   if (isa<ConstantBool>(Condition) || TrueDest == FalseDest) {
 674     PS->proceedToSuccessors(KP, BB);
 675     return;
 676   }
 677
 678   DTNodeType *Node = PS->DT->getNode(BB);
 679   for (DTNodeType::iterator I = Node->begin(), E = Node->end(); I != E; ++I) {
 680     BasicBlock *Dest = (*I)->getBlock();
 681     PropertySet DestProperties(KP);
 682
 683     if (Dest == TrueDest)
 684       DestProperties.addEqual(ConstantBool::getTrue(), Condition);
 685     else if (Dest == FalseDest)
 686       DestProperties.addEqual(ConstantBool::getFalse(), Condition);
 687
 688     PS->proceedToSuccessor(DestProperties, Dest);
 689   }
 690 }
 691
 692 void PredicateSimplifier::Forwards::visitSwitchInst(SwitchInst &SI) {
 693   Value *Condition = SI.getCondition();
 694
 695   // Set the EQProperty in each of the cases BBs,
 696   // and the NEProperties in the default BB.
 697   PropertySet DefaultProperties(KP);
 698
 699   DTNodeType *Node = PS->DT->getNode(SI.getParent());
 700   for (DTNodeType::iterator I = Node->begin(), E = Node->end(); I != E; ++I) {
 701     BasicBlock *BB = (*I)->getBlock();
 702
 703     PropertySet BBProperties(KP);
 704     if (BB == SI.getDefaultDest()) {
 705       for (unsigned i = 1, e = SI.getNumCases(); i < e; ++i)
 706         if (SI.getSuccessor(i) != BB)
 707           BBProperties.addNotEqual(Condition, SI.getCaseValue(i));
 708     } else if (ConstantInt *CI = SI.findCaseDest(BB)) {
 709       BBProperties.addEqual(Condition, CI);
 710     }
 711     PS->proceedToSuccessor(BBProperties, BB);
 712   }
 713 }
 714
 715 void PredicateSimplifier::Forwards::visitLoadInst(LoadInst &LI) {
 716   Value *Ptr = LI.getPointerOperand();
 717   KP.addNotEqual(Constant::getNullValue(Ptr->getType()), Ptr);
 718 }
 719
 720 void PredicateSimplifier::Forwards::visitStoreInst(StoreInst &SI) {
 721   Value *Ptr = SI.getPointerOperand();
 722   KP.addNotEqual(Constant::getNullValue(Ptr->getType()), Ptr);
 723 }
 724
 725 void PredicateSimplifier::Forwards::visitBinaryOperator(BinaryOperator &BO) {
 726   Instruction::BinaryOps ops = BO.getOpcode();
 727
 728   switch (ops) {
 729     case Instruction::Div:
 730     case Instruction::Rem: {
 731       Value *Divisor = BO.getOperand(1);
 732       KP.addNotEqual(Constant::getNullValue(Divisor->getType()), Divisor);
 733       break;
 734     }
 735     default:
 736       break;
 737   }
 738 }