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 proceedToSuccessor(TerminatorInst *TI, unsigned edge,
 417                             PropertySet &CurrentPS, PropertySet &NextPS);
 418     void proceedToSuccessors(PropertySet &CurrentPS, BasicBlock *Current);
 419
 420     // Visits each instruction in the basic block.
 421     void visitBasicBlock(BasicBlock *Block, PropertySet &KnownProperties);
 422
 423     // Tries to simplify each Instruction and add new properties to
 424     // the PropertySet. Returns true if it erase the instruction.
 425     void visitInstruction(Instruction *I, PropertySet &);
 426     // For each instruction, add the properties to KnownProperties.
 427
 428     void visit(TerminatorInst *TI, PropertySet &);
 429     void visit(BranchInst *BI, PropertySet &);
 430     void visit(SwitchInst *SI, PropertySet);
 431     void visit(LoadInst *LI, PropertySet &);
 432     void visit(StoreInst *SI, PropertySet &);
 433     void visit(BinaryOperator *BO, PropertySet &);
 434
 435     DominatorTree *DT;
 436     bool modified;
 437   };
 438
 439   RegisterPass<PredicateSimplifier> X("predsimplify",
 440                                       "Predicate Simplifier");
 441
 442   template <typename ElemTy>
 443   typename Synonyms<ElemTy>::iterator
 444   Synonyms<ElemTy>::unionSets(ElemTy E1, ElemTy E2) {
 445     PS->order(E1, E2);
 446
 447     iterator I1 = findLeader(E1),
 448              I2 = findLeader(E2);
 449
 450     if (!I1 && !I2) { // neither entry is in yet
 451       leaders.push_back(E1);
 452       I1 = leaders.size();
 453       mapping[E1] = I1;
 454       mapping[E2] = I1;
 455       return 0;
 456     }
 457
 458     if (!I1 && I2) {
 459       mapping[E1] = I2;
 460       std::swap(getLeader(I2), E1);
 461       return 0;
 462     }
 463
 464     if (I1 && !I2) {
 465       mapping[E2] = I1;
 466       return 0;
 467     }
 468
 469     if (I1 == I2) return 0;
 470
 471     // This is the case where we have two sets, [%a1, %a2, %a3] and
 472     // [%p1, %p2, %p3] and someone says that %a2 == %p3. We need to
 473     // combine the two synsets.
 474
 475     if (I1 > I2) --I1;
 476
 477     for (std::map<Value *, unsigned>::iterator I = mapping.begin(),
 478          E = mapping.end(); I != E; ++I) {
 479       if (I->second == I2) I->second = I1;
 480       else if (I->second > I2) --I->second;
 481     }
 482
 483     leaders.erase(leaders.begin() + I2 - 1);
 484
 485     return I2;
 486   }
 487 }
 488
 489 FunctionPass *llvm::createPredicateSimplifierPass() {
 490   return new PredicateSimplifier();
 491 }
 492
 493 bool PredicateSimplifier::runOnFunction(Function &F) {
 494   DT = &getAnalysis<DominatorTree>();
 495
 496   modified = false;
 497   PropertySet KnownProperties(DT);
 498   visitBasicBlock(DT->getRootNode()->getBlock(), KnownProperties);
 499   return modified;
 500 }
 501
 502 void PredicateSimplifier::getAnalysisUsage(AnalysisUsage &AU) const {
 503   AU.addRequiredID(BreakCriticalEdgesID);
 504   AU.addRequired<DominatorTree>();
 505   AU.setPreservesCFG();
 506   AU.addPreservedID(BreakCriticalEdgesID);
 507 }
 508
 509 // resolve catches cases addProperty won't because it wasn't used as a
 510 // condition in the branch, and that visit won't, because the instruction
 511 // was defined outside of the scope that the properties apply to.
 512 Value *PredicateSimplifier::resolve(SetCondInst *SCI,
 513                                     const PropertySet &KP) {
 514   // Attempt to resolve the SetCondInst to a boolean.
 515
 516   Value *SCI0 = resolve(SCI->getOperand(0), KP),
 517         *SCI1 = resolve(SCI->getOperand(1), KP);
 518
 519   PropertySet::ConstPropertyIterator NE =
 520       KP.findProperty(PropertySet::NE, SCI0, SCI1);
 521
 522   if (NE != KP.Properties.end()) {
 523     switch (SCI->getOpcode()) {
 524       case Instruction::SetEQ: return ConstantBool::getFalse();
 525       case Instruction::SetNE: return ConstantBool::getTrue();
 526       case Instruction::SetLE:
 527       case Instruction::SetGE:
 528       case Instruction::SetLT:
 529       case Instruction::SetGT:
 530         break;
 531       default:
 532         assert(0 && "Unknown opcode in SetCondInst.");
 533         break;
 534     }
 535   }
 536   return SCI;
 537 }
 538
 539 Value *PredicateSimplifier::resolve(BinaryOperator *BO,
 540                                     const PropertySet &KP) {
 541   Value *lhs = resolve(BO->getOperand(0), KP),
 542         *rhs = resolve(BO->getOperand(1), KP);
 543
 544   ConstantIntegral *CI1 = dyn_cast<ConstantIntegral>(lhs),
 545                    *CI2 = dyn_cast<ConstantIntegral>(rhs);
 546
 547   if (CI1 && CI2) return ConstantExpr::get(BO->getOpcode(), CI1, CI2);
 548
 549   if (SetCondInst *SCI = dyn_cast<SetCondInst>(BO))
 550     return resolve(SCI, KP);
 551
 552   return BO;
 553 }
 554
 555 Value *PredicateSimplifier::resolve(SelectInst *SI, const PropertySet &KP) {
 556   Value *Condition = resolve(SI->getCondition(), KP);
 557   if (ConstantBool *CB = dyn_cast<ConstantBool>(Condition))
 558     return resolve(CB->getValue() ? SI->getTrueValue() : SI->getFalseValue(),
 559                    KP);
 560   return SI;
 561 }
 562
 563 Value *PredicateSimplifier::resolve(Value *V, const PropertySet &KP) {
 564   if (isa<Constant>(V) || isa<BasicBlock>(V) || KP.empty()) return V;
 565
 566   V = KP.canonicalize(V);
 567
 568   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
 569     return resolve(BO, KP);
 570   else if (SelectInst *SI = dyn_cast<SelectInst>(V))
 571     return resolve(SI, KP);
 572
 573   return V;
 574 }
 575
 576 void PredicateSimplifier::visitBasicBlock(BasicBlock *BB,
 577                                           PropertySet &KnownProperties) {
 578   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
 579     visitInstruction(I++, KnownProperties);
 580   }
 581 }
 582
 583 void PredicateSimplifier::visitInstruction(Instruction *I,
 584                                            PropertySet &KnownProperties) {
 585   // Try to replace the whole instruction.
 586   Value *V = resolve(I, KnownProperties);
 587   if (V != I) {
 588     modified = true;
 589     ++NumInstruction;
 590     DEBUG(std::cerr << "Removing " << *I);
 591     I->replaceAllUsesWith(V);
 592     I->eraseFromParent();
 593     return;
 594   }
 595
 596   // Try to substitute operands.
 597   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 598     Value *Oper = I->getOperand(i);
 599     Value *V = resolve(Oper, KnownProperties);
 600     if (V != Oper) {
 601       modified = true;
 602       ++NumVarsReplaced;
 603       DEBUG(std::cerr << "Resolving " << *I);
 604       I->setOperand(i, V);
 605       DEBUG(std::cerr << "into " << *I);
 606     }
 607   }
 608
 609   if (TerminatorInst *TI = dyn_cast<TerminatorInst>(I))
 610     visit(TI, KnownProperties);
 611   else if (LoadInst *LI = dyn_cast<LoadInst>(I))
 612     visit(LI, KnownProperties);
 613   else if (StoreInst *SI = dyn_cast<StoreInst>(I))
 614     visit(SI, KnownProperties);
 615   else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I))
 616     visit(BO, KnownProperties);
 617 }
 618
 619 // The basic block on the target of the specified edge must be known
 620 // to be immediately dominated by the parent of the TerminatorInst.
 621 void PredicateSimplifier::proceedToSuccessor(TerminatorInst *TI,
 622                                              unsigned edge,
 623                                              PropertySet &CurrentPS,
 624                                              PropertySet &NextPS) {
 625   assert(edge < TI->getNumSuccessors() && "Invalid index for edge.");
 626
 627   visitBasicBlock(TI->getSuccessor(edge), NextPS);
 628 }
 629
 630 void PredicateSimplifier::proceedToSuccessors(PropertySet &KP,
 631                                               BasicBlock *BBCurrent) {
 632   DTNodeType *Current = DT->getNode(BBCurrent);
 633   for (DTNodeType::iterator I = Current->begin(), E = Current->end();
 634        I != E; ++I) {
 635     PropertySet Copy(KP);
 636     visitBasicBlock((*I)->getBlock(), Copy);
 637   }
 638 }
 639
 640 void PredicateSimplifier::visit(TerminatorInst *TI, PropertySet &KP) {
 641   if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 642     visit(BI, KP);
 643     return;
 644   }
 645   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 646     visit(SI, KP);
 647     return;
 648   }
 649
 650   proceedToSuccessors(KP, TI->getParent());
 651 }
 652
 653 void PredicateSimplifier::visit(BranchInst *BI, PropertySet &KP) {
 654   BasicBlock *BB = BI->getParent();
 655
 656   if (BI->isUnconditional()) {
 657     proceedToSuccessors(KP, BB);
 658     return;
 659   }
 660
 661   Value *Condition = BI->getCondition();
 662
 663   BasicBlock *TrueDest  = BI->getSuccessor(0),
 664              *FalseDest = BI->getSuccessor(1);
 665
 666   if (Condition == ConstantBool::getTrue() || TrueDest == FalseDest) {
 667     proceedToSuccessors(KP, BB);
 668     return;
 669   } else if (Condition == ConstantBool::getFalse()) {
 670     proceedToSuccessors(KP, BB);
 671     return;
 672   }
 673
 674   DTNodeType *Node = DT->getNode(BB);
 675   for (DTNodeType::iterator I = Node->begin(), E = Node->end(); I != E; ++I) {
 676     if ((*I)->getBlock() == TrueDest) {
 677       PropertySet TrueProperties(KP);
 678       TrueProperties.addEqual(ConstantBool::getTrue(), Condition);
 679       proceedToSuccessor(BI, 0, KP, TrueProperties);
 680       continue;
 681     }
 682
 683     if ((*I)->getBlock() == FalseDest) {
 684       PropertySet FalseProperties(KP);
 685       FalseProperties.addEqual(ConstantBool::getFalse(), Condition);
 686       proceedToSuccessor(BI, 1, KP, FalseProperties);
 687       continue;
 688     }
 689
 690     visitBasicBlock((*I)->getBlock(), KP);
 691   }
 692 }
 693
 694 void PredicateSimplifier::visit(SwitchInst *SI, PropertySet KP) {
 695   Value *Condition = SI->getCondition();
 696
 697   // Set the EQProperty in each of the cases BBs,
 698   // and the NEProperties in the default BB.
 699   PropertySet DefaultProperties(KP);
 700
 701   DTNodeType *Node = DT->getNode(SI->getParent());
 702   for (DTNodeType::iterator I = Node->begin(), E = Node->end(); I != E; ++I) {
 703     BasicBlock *BB = (*I)->getBlock();
 704
 705     PropertySet Copy(KP);
 706
 707     if (BB == SI->getDefaultDest()) {
 708       PropertySet NewProperties(KP);
 709       for (unsigned i = 1, e = SI->getNumCases(); i < e; ++i)
 710         NewProperties.addNotEqual(Condition, SI->getCaseValue(i));
 711
 712       proceedToSuccessor(SI, 0, Copy, NewProperties);
 713     } else if (ConstantInt *CI = SI->findCaseDest(BB)) {
 714       PropertySet NewProperties(KP);
 715       NewProperties.addEqual(Condition, CI);
 716       proceedToSuccessor(SI, SI->findCaseValue(CI), Copy, NewProperties);
 717     } else
 718       visitBasicBlock(BB, Copy);
 719   }
 720 }
 721
 722 void PredicateSimplifier::visit(LoadInst *LI, PropertySet &KP) {
 723   Value *Ptr = LI->getPointerOperand();
 724   KP.addNotEqual(Constant::getNullValue(Ptr->getType()), Ptr);
 725 }
 726
 727 void PredicateSimplifier::visit(StoreInst *SI, PropertySet &KP) {
 728   Value *Ptr = SI->getPointerOperand();
 729   KP.addNotEqual(Constant::getNullValue(Ptr->getType()), Ptr);
 730 }
 731
 732 void PredicateSimplifier::visit(BinaryOperator *BO, PropertySet &KP) {
 733   Instruction::BinaryOps ops = BO->getOpcode();
 734
 735   switch (ops) {
 736     case Instruction::Div:
 737     case Instruction::Rem: {
 738       Value *Divisor = BO->getOperand(1);
 739       KP.addNotEqual(Constant::getNullValue(Divisor->getType()), Divisor);
 740       break;
 741     }
 742     default:
 743       break;
 744   }
 745 }