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