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 // TODO:
  32 // * Check handling of NAN in floating point types
  33
  34 #define DEBUG_TYPE "predsimplify"
  35 #include "llvm/Transforms/Scalar.h"
  36 #include "llvm/Constants.h"
  37 #include "llvm/Instructions.h"
  38 #include "llvm/Pass.h"
  39 #include "llvm/ADT/EquivalenceClasses.h"
  40 #include "llvm/ADT/Statistic.h"
  41 #include "llvm/ADT/STLExtras.h"
  42 #include "llvm/Analysis/Dominators.h"
  43 #include "llvm/Support/CFG.h"
  44 #include "llvm/Support/Debug.h"
  45 #include <iostream>
  46 using namespace llvm;
  47
  48 namespace {
  49   Statistic<>
  50   NumVarsReplaced("predsimplify", "Number of argument substitutions");
  51   Statistic<>
  52   NumInstruction("predsimplify", "Number of instructions removed");
  53   Statistic<>
  54   NumSwitchCases("predsimplify", "Number of switch cases removed");
  55   Statistic<>
  56   NumBranches("predsimplify", "Number of branches made unconditional");
  57
  58   /// Used for choosing the canonical Value in a synonym set.
  59   /// Leaves the better one in V1. Returns whether a swap took place.
  60   static void order(Value *&V1, Value *&V2) {
  61     if (isa<Constant>(V2)) {
  62       if (!isa<Constant>(V1)) {
  63         std::swap(V1, V2);
  64         return;
  65       }
  66     } else if (isa<Argument>(V2)) {
  67       if (!isa<Constant>(V1) && !isa<Argument>(V1)) {
  68         std::swap(V1, V2);
  69         return;
  70       }
  71     }
  72     if (User *U1 = dyn_cast<User>(V1)) {
  73       for (User::const_op_iterator I = U1->op_begin(), E = U1->op_end();
  74            I != E; ++I) {
  75         if (*I == V2) {
  76           std::swap(V1, V2);
  77           return;
  78         }
  79       }
  80     }
  81     return;
  82   }
  83
  84   /// Represents the set of equivalent Value*s and provides insertion
  85   /// and fast lookup. Also stores the set of inequality relationships.
  86   class PropertySet {
  87     struct Property;
  88     class EquivalenceClasses<Value *> union_find;
  89   public:
  90     typedef std::vector<Property>::iterator       PropertyIterator;
  91     typedef std::vector<Property>::const_iterator ConstPropertyIterator;
  92
  93     enum Ops {
  94       EQ,
  95       NE
  96     };
  97
  98     Value *canonicalize(Value *V) const {
  99       Value *C = lookup(V);
 100       return C ? C : V;
 101     }
 102
 103     Value *lookup(Value *V) const {
 104       EquivalenceClasses<Value *>::member_iterator SI =
 105           union_find.findLeader(V);
 106       if (SI == union_find.member_end()) return NULL;
 107       return *SI;
 108     }
 109
 110     bool empty() const {
 111       return union_find.empty();
 112     }
 113
 114     void addEqual(Value *V1, Value *V2) {
 115       order(V1, V2);
 116       if (isa<Constant>(V2)) return; // refuse to set false == true.
 117
 118       union_find.unionSets(V1, V2);
 119       addImpliedProperties(EQ, V1, V2);
 120     }
 121
 122     void addNotEqual(Value *V1, Value *V2) {
 123       DEBUG(std::cerr << "not equal: " << *V1 << " and " << *V2 << "\n");
 124       V1 = canonicalize(V1);
 125       V2 = canonicalize(V2);
 126
 127       // Does the property already exist?
 128       for (PropertyIterator I = Properties.begin(), E = Properties.end();
 129            I != E; ++I) {
 130         if (I->Opcode != NE) continue;
 131
 132         I->V1 = canonicalize(I->V1);
 133         I->V2 = canonicalize(I->V2);
 134         if ((I->V1 == V1 && I->V2 == V2) ||
 135             (I->V1 == V2 && I->V2 == V1)) {
 136           return; // Found.
 137         }
 138       }
 139
 140       // Add the property.
 141       Properties.push_back(Property(NE, V1, V2));
 142       addImpliedProperties(NE, V1, V2);
 143     }
 144
 145     PropertyIterator findProperty(Ops Opcode, Value *V1, Value *V2) {
 146       assert(Opcode != EQ && "Can't findProperty on EQ."
 147              "Use the lookup method instead.");
 148
 149       V1 = lookup(V1);
 150       V2 = lookup(V2);
 151       if (!V1 || !V2) return Properties.end();
 152
 153       // Does the property already exist?
 154       for (PropertyIterator I = Properties.begin(), E = Properties.end();
 155            I != E; ++I) {
 156         if (I->Opcode != Opcode) continue;
 157
 158         I->V1 = canonicalize(I->V1);
 159         I->V2 = canonicalize(I->V2);
 160         if ((I->V1 == V1 && I->V2 == V2) ||
 161             (I->V1 == V2 && I->V2 == V1)) {
 162           return I; // Found.
 163         }
 164       }
 165       return Properties.end();
 166     }
 167
 168     ConstPropertyIterator
 169     findProperty(Ops Opcode, Value *V1, Value *V2) const {
 170       assert(Opcode != EQ && "Can't findProperty on EQ."
 171              "Use the lookup method instead.");
 172
 173       V1 = lookup(V1);
 174       V2 = lookup(V2);
 175       if (!V1 || !V2) return Properties.end();
 176
 177       // Does the property already exist?
 178       for (ConstPropertyIterator I = Properties.begin(),
 179            E = Properties.end(); I != E; ++I) {
 180         if (I->Opcode != Opcode) continue;
 181
 182         Value *v1 = lookup(I->V1),
 183               *v2 = lookup(I->V2);
 184         if (!v1 || !v2) continue;
 185         if ((v1 == V1 && v2 == V2) ||
 186             (v1 == V2 && v2 == V1)) {
 187           return I; // Found.
 188         }
 189       }
 190       return Properties.end();
 191     }
 192
 193   private:
 194     // Represents Head OP [Tail1, Tail2, ...]
 195     // For example: %x != %a, %x != %b.
 196     struct Property {
 197       Property(Ops opcode, Value *v1, Value *v2)
 198         : Opcode(opcode), V1(v1), V2(v2)
 199       { assert(opcode != EQ && "Equality belongs in the synonym set,"
 200                "not a property."); }
 201
 202       bool operator<(const Property &rhs) const {
 203         if (Opcode != rhs.Opcode) return Opcode < rhs.Opcode;
 204         if (V1 != rhs.V1) return V1 < rhs.V1;
 205         return V2 < rhs.V2;
 206       }
 207
 208       Ops Opcode;
 209       Value *V1, *V2;
 210     };
 211
 212     void add(Ops Opcode, Value *V1, Value *V2, bool invert) {
 213       switch (Opcode) {
 214         case EQ:
 215           if (invert) addNotEqual(V1, V2);
 216           else        addEqual(V1, V2);
 217           break;
 218         case NE:
 219           if (invert) addEqual(V1, V2);
 220           else        addNotEqual(V1, V2);
 221           break;
 222         default:
 223           assert(0 && "Unknown property opcode.");
 224       }
 225     }
 226
 227     // Finds the properties implied by a synonym and adds them too.
 228     // Example: ("seteq %a, %b", true,  EQ) --> (%a, %b, EQ)
 229     //          ("seteq %a, %b", false, EQ) --> (%a, %b, NE)
 230     void addImpliedProperties(Ops Opcode, Value *V1, Value *V2) {
 231       order(V1, V2);
 232
 233       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V2)) {
 234         switch (BO->getOpcode()) {
 235         case Instruction::SetEQ:
 236           if (V1 == ConstantBool::True)
 237             add(Opcode, BO->getOperand(0), BO->getOperand(1), false);
 238           if (V1 == ConstantBool::False)
 239             add(Opcode, BO->getOperand(0), BO->getOperand(1), true);
 240           break;
 241         case Instruction::SetNE:
 242           if (V1 == ConstantBool::True)
 243             add(Opcode, BO->getOperand(0), BO->getOperand(1), true);
 244           if (V1 == ConstantBool::False)
 245             add(Opcode, BO->getOperand(0), BO->getOperand(1), false);
 246           break;
 247         case Instruction::SetLT:
 248         case Instruction::SetGT:
 249           if (V1 == ConstantBool::True)
 250             add(Opcode, BO->getOperand(0), BO->getOperand(1), true);
 251           break;
 252         case Instruction::SetLE:
 253         case Instruction::SetGE:
 254           if (V1 == ConstantBool::False)
 255             add(Opcode, BO->getOperand(0), BO->getOperand(1), true);
 256           break;
 257         case Instruction::And:
 258           if (V1 == ConstantBool::True) {
 259             add(Opcode, ConstantBool::True, BO->getOperand(0), false);
 260             add(Opcode, ConstantBool::True, BO->getOperand(1), false);
 261           }
 262           break;
 263         case Instruction::Or:
 264           if (V1 == ConstantBool::False) {
 265             add(Opcode, ConstantBool::False, BO->getOperand(0), false);
 266             add(Opcode, ConstantBool::False, BO->getOperand(1), false);
 267           }
 268           break;
 269         case Instruction::Xor:
 270           if (V1 == ConstantBool::True) {
 271             if (BO->getOperand(0) == ConstantBool::True)
 272               add(Opcode, ConstantBool::False, BO->getOperand(1), false);
 273             if (BO->getOperand(1) == ConstantBool::True)
 274               add(Opcode, ConstantBool::False, BO->getOperand(0), false);
 275           }
 276           if (V1 == ConstantBool::False) {
 277             if (BO->getOperand(0) == ConstantBool::True)
 278               add(Opcode, ConstantBool::True, BO->getOperand(1), false);
 279             if (BO->getOperand(1) == ConstantBool::True)
 280               add(Opcode, ConstantBool::True, BO->getOperand(0), false);
 281           }
 282           break;
 283         default:
 284           break;
 285         }
 286       }
 287     }
 288
 289     std::map<Value *, unsigned> SynonymMap;
 290     std::vector<Value *> Synonyms;
 291
 292   public:
 293     void debug(std::ostream &os) const {
 294     }
 295
 296     std::vector<Property> Properties;
 297   };
 298
 299   /// PredicateSimplifier - This class is a simplifier that replaces
 300   /// one equivalent variable with another. It also tracks what
 301   /// can't be equal and will solve setcc instructions when possible.
 302   class PredicateSimplifier : public FunctionPass {
 303   public:
 304     bool runOnFunction(Function &F);
 305     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 306
 307   private:
 308     // Try to replace the Use of the instruction with something simpler.
 309     Value *resolve(SetCondInst *SCI, const PropertySet &);
 310     Value *resolve(BinaryOperator *BO, const PropertySet &);
 311     Value *resolve(SelectInst *SI, const PropertySet &);
 312     Value *resolve(Value *V, const PropertySet &);
 313
 314     // Used by terminator instructions to proceed from the current basic
 315     // block to the next. Verifies that "current" dominates "next",
 316     // then calls visitBasicBlock.
 317     void proceedToSuccessor(PropertySet &CurrentPS, PropertySet &NextPS,
 318                   DominatorTree::Node *Current, DominatorTree::Node *Next);
 319     void proceedToSuccessor(PropertySet &CurrentPS,
 320                   DominatorTree::Node *Current, DominatorTree::Node *Next);
 321
 322     // Visits each instruction in the basic block.
 323     void visitBasicBlock(DominatorTree::Node *DTNode,
 324                          PropertySet &KnownProperties);
 325
 326     // For each instruction, add the properties to KnownProperties.
 327     void visit(Instruction *I, DominatorTree::Node *, PropertySet &);
 328     void visit(TerminatorInst *TI, DominatorTree::Node *, PropertySet &);
 329     void visit(BranchInst *BI, DominatorTree::Node *, PropertySet &);
 330     void visit(SwitchInst *SI, DominatorTree::Node *, PropertySet);
 331     void visit(LoadInst *LI, DominatorTree::Node *, PropertySet &);
 332     void visit(StoreInst *SI, DominatorTree::Node *, PropertySet &);
 333     void visit(BinaryOperator *BO, DominatorTree::Node *, PropertySet &);
 334
 335     DominatorTree *DT;
 336     bool modified;
 337   };
 338
 339   RegisterPass<PredicateSimplifier> X("predsimplify",
 340                                       "Predicate Simplifier");
 341 }
 342
 343 FunctionPass *llvm::createPredicateSimplifierPass() {
 344   return new PredicateSimplifier();
 345 }
 346
 347 bool PredicateSimplifier::runOnFunction(Function &F) {
 348   DT = &getAnalysis<DominatorTree>();
 349
 350   modified = false;
 351   PropertySet KnownProperties;
 352   visitBasicBlock(DT->getRootNode(), KnownProperties);
 353   return modified;
 354 }
 355
 356 void PredicateSimplifier::getAnalysisUsage(AnalysisUsage &AU) const {
 357   AU.addRequired<DominatorTree>();
 358 }
 359
 360 // resolve catches cases addProperty won't because it wasn't used as a
 361 // condition in the branch, and that visit won't, because the instruction
 362 // was defined outside of the range that the properties apply to.
 363 Value *PredicateSimplifier::resolve(SetCondInst *SCI,
 364                                     const PropertySet &KP) {
 365   // Attempt to resolve the SetCondInst to a boolean.
 366
 367   Value *SCI0 = SCI->getOperand(0),
 368         *SCI1 = SCI->getOperand(1);
 369   PropertySet::ConstPropertyIterator NE =
 370                    KP.findProperty(PropertySet::NE, SCI0, SCI1);
 371
 372   if (NE != KP.Properties.end()) {
 373     switch (SCI->getOpcode()) {
 374       case Instruction::SetEQ:
 375         return ConstantBool::False;
 376       case Instruction::SetNE:
 377         return ConstantBool::True;
 378       case Instruction::SetLE:
 379       case Instruction::SetGE:
 380       case Instruction::SetLT:
 381       case Instruction::SetGT:
 382         break;
 383       default:
 384         assert(0 && "Unknown opcode in SetCondInst.");
 385         break;
 386     }
 387   }
 388
 389   SCI0 = KP.canonicalize(SCI0);
 390   SCI1 = KP.canonicalize(SCI1);
 391
 392   ConstantIntegral *CI1 = dyn_cast<ConstantIntegral>(SCI0),
 393                    *CI2 = dyn_cast<ConstantIntegral>(SCI1);
 394
 395   if (!CI1 || !CI2) return SCI;
 396
 397   switch(SCI->getOpcode()) {
 398     case Instruction::SetLE:
 399     case Instruction::SetGE:
 400     case Instruction::SetEQ:
 401       if (CI1->getRawValue() == CI2->getRawValue())
 402         return ConstantBool::True;
 403       else
 404         return ConstantBool::False;
 405     case Instruction::SetLT:
 406     case Instruction::SetGT:
 407     case Instruction::SetNE:
 408       if (CI1->getRawValue() == CI2->getRawValue())
 409         return ConstantBool::False;
 410       else
 411         return ConstantBool::True;
 412     default:
 413       assert(0 && "Unknown opcode in SetContInst.");
 414       break;
 415   }
 416 }
 417
 418 Value *PredicateSimplifier::resolve(BinaryOperator *BO,
 419                                     const PropertySet &KP) {
 420   if (SetCondInst *SCI = dyn_cast<SetCondInst>(BO))
 421     return resolve(SCI, KP);
 422
 423   DEBUG(std::cerr << "BO->getOperand(1) = " << *BO->getOperand(1) << "\n");
 424
 425   Value *lhs = resolve(BO->getOperand(0), KP),
 426         *rhs = resolve(BO->getOperand(1), KP);
 427   ConstantIntegral *CI1 = dyn_cast<ConstantIntegral>(lhs);
 428   ConstantIntegral *CI2 = dyn_cast<ConstantIntegral>(rhs);
 429
 430   DEBUG(std::cerr << "resolveBO: lhs = " << *lhs
 431                   << ", rhs = " << *rhs << "\n");
 432   if (CI1) DEBUG(std::cerr << "CI1 = " << *CI1);
 433   if (CI2) DEBUG(std::cerr << "CI2 = " << *CI2);
 434
 435   if (!CI1 || !CI2) return BO;
 436
 437   Value *V = ConstantExpr::get(BO->getOpcode(), CI1, CI2);
 438   if (V) return V;
 439   return BO;
 440 }
 441
 442 Value *PredicateSimplifier::resolve(SelectInst *SI, const PropertySet &KP) {
 443   Value *Condition = resolve(SI->getCondition(), KP);
 444   if (Condition == ConstantBool::True)
 445     return resolve(SI->getTrueValue(), KP);
 446   else if (Condition == ConstantBool::False)
 447     return resolve(SI->getFalseValue(), KP);
 448   return SI;
 449 }
 450
 451 Value *PredicateSimplifier::resolve(Value *V, const PropertySet &KP) {
 452   if (isa<Constant>(V) || isa<BasicBlock>(V) || KP.empty()) return V;
 453
 454   V = KP.canonicalize(V);
 455
 456   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
 457     return resolve(BO, KP);
 458   else if (SelectInst *SI = dyn_cast<SelectInst>(V))
 459     return resolve(SI, KP);
 460
 461   return V;
 462 }
 463
 464 void PredicateSimplifier::visitBasicBlock(DominatorTree::Node *DTNode,
 465                                           PropertySet &KnownProperties) {
 466   BasicBlock *BB = DTNode->getBlock();
 467   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
 468     visit(I, DTNode, KnownProperties);
 469   }
 470 }
 471
 472 void PredicateSimplifier::visit(Instruction *I, DominatorTree::Node *DTNode,
 473                                 PropertySet &KnownProperties) {
 474   DEBUG(std::cerr << "Considering instruction " << *I << "\n");
 475   DEBUG(KnownProperties.debug(std::cerr));
 476
 477   // Substitute values known to be equal.
 478   for (unsigned i = 0, E = I->getNumOperands(); i != E; ++i) {
 479     Value *Oper = I->getOperand(i);
 480     Value *V = resolve(Oper, KnownProperties);
 481     assert(V && "resolve not supposed to return NULL.");
 482     if (V != Oper) {
 483       modified = true;
 484       ++NumVarsReplaced;
 485       DEBUG(std::cerr << "resolving " << *I);
 486       I->setOperand(i, V);
 487       DEBUG(std::cerr << "into " << *I);
 488     }
 489   }
 490
 491   Value *V = resolve(I, KnownProperties);
 492   assert(V && "resolve not supposed to return NULL.");
 493   if (V != I) {
 494     modified = true;
 495     ++NumInstruction;
 496     I->replaceAllUsesWith(V);
 497     I->eraseFromParent();
 498   }
 499
 500   if (TerminatorInst *TI = dyn_cast<TerminatorInst>(I))
 501     visit(TI, DTNode, KnownProperties);
 502   else if (LoadInst *LI = dyn_cast<LoadInst>(I))
 503     visit(LI, DTNode, KnownProperties);
 504   else if (StoreInst *SI = dyn_cast<StoreInst>(I))
 505     visit(SI, DTNode, KnownProperties);
 506   else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I))
 507     visit(BO, DTNode, KnownProperties);
 508 }
 509
 510 void PredicateSimplifier::proceedToSuccessor(PropertySet &CurrentPS,
 511     PropertySet &NextPS, DominatorTree::Node *Current,
 512     DominatorTree::Node *Next) {
 513   if (Next->getBlock()->getSinglePredecessor() == Current->getBlock())
 514     proceedToSuccessor(NextPS, Current, Next);
 515   else
 516     proceedToSuccessor(CurrentPS, Current, Next);
 517 }
 518
 519 void PredicateSimplifier::proceedToSuccessor(PropertySet &KP,
 520     DominatorTree::Node *Current, DominatorTree::Node *Next) {
 521   if (Current->properlyDominates(Next))
 522     visitBasicBlock(Next, KP);
 523 }
 524
 525 void PredicateSimplifier::visit(TerminatorInst *TI,
 526                                 DominatorTree::Node *Node, PropertySet &KP){
 527   if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 528     visit(BI, Node, KP);
 529     return;
 530   }
 531   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 532     visit(SI, Node, KP);
 533     return;
 534   }
 535
 536   for (unsigned i = 0, E = TI->getNumSuccessors(); i != E; ++i) {
 537     BasicBlock *BB = TI->getSuccessor(i);
 538     PropertySet KPcopy(KP);
 539     proceedToSuccessor(KPcopy, Node, DT->getNode(TI->getSuccessor(i)));
 540   }
 541 }
 542
 543 void PredicateSimplifier::visit(BranchInst *BI,
 544                                 DominatorTree::Node *Node, PropertySet &KP){
 545   if (BI->isUnconditional()) {
 546     proceedToSuccessor(KP, Node, DT->getNode(BI->getSuccessor(0)));
 547     return;
 548   }
 549
 550   Value *Condition = BI->getCondition();
 551
 552   BasicBlock *TrueDest  = BI->getSuccessor(0),
 553              *FalseDest = BI->getSuccessor(1);
 554
 555   if (Condition == ConstantBool::True) {
 556     FalseDest->removePredecessor(BI->getParent());
 557     BI->setUnconditionalDest(TrueDest);
 558     modified = true;
 559     ++NumBranches;
 560     proceedToSuccessor(KP, Node, DT->getNode(TrueDest));
 561     return;
 562   } else if (Condition == ConstantBool::False) {
 563     TrueDest->removePredecessor(BI->getParent());
 564     BI->setUnconditionalDest(FalseDest);
 565     modified = true;
 566     ++NumBranches;
 567     proceedToSuccessor(KP, Node, DT->getNode(FalseDest));
 568     return;
 569   }
 570
 571   PropertySet TrueProperties(KP), FalseProperties(KP);
 572   DEBUG(std::cerr << "true set:\n");
 573   TrueProperties.addEqual(ConstantBool::True,   Condition);
 574   DEBUG(std::cerr << "false set:\n");
 575   FalseProperties.addEqual(ConstantBool::False, Condition);
 576
 577   PropertySet KPcopy(KP);
 578   proceedToSuccessor(KP,     TrueProperties,  Node, DT->getNode(TrueDest));
 579   proceedToSuccessor(KPcopy, FalseProperties, Node, DT->getNode(FalseDest));
 580 }
 581
 582 void PredicateSimplifier::visit(SwitchInst *SI,
 583                              DominatorTree::Node *DTNode, PropertySet KP) {
 584   Value *Condition = SI->getCondition();
 585
 586   // If there's an NEProperty covering this SwitchInst, we may be able to
 587   // eliminate one of the cases.
 588   if (Value *C = KP.lookup(Condition)) {
 589     Condition = C;
 590     for (PropertySet::ConstPropertyIterator I = KP.Properties.begin(),
 591          E = KP.Properties.end(); I != E; ++I) {
 592       if (I->Opcode != PropertySet::NE) continue;
 593       Value *V1 = KP.lookup(I->V1),
 594             *V2 = KP.lookup(I->V2);
 595       if (V1 != C && V2 != C) continue;
 596
 597       // Is one side a number?
 598       ConstantInt *CI = dyn_cast<ConstantInt>(KP.lookup(I->V1));
 599       if (!CI)     CI = dyn_cast<ConstantInt>(KP.lookup(I->V2));
 600
 601       if (CI) {
 602         unsigned i = SI->findCaseValue(CI);
 603         if (i != 0) {
 604           SI->getSuccessor(i)->removePredecessor(SI->getParent());
 605           SI->removeCase(i);
 606           modified = true;
 607           ++NumSwitchCases;
 608         }
 609       }
 610     }
 611   }
 612
 613   // Set the EQProperty in each of the cases BBs,
 614   // and the NEProperties in the default BB.
 615   PropertySet DefaultProperties(KP);
 616
 617   DominatorTree::Node *Node        = DT->getNode(SI->getParent()),
 618                       *DefaultNode = DT->getNode(SI->getSuccessor(0));
 619   if (!Node->dominates(DefaultNode)) DefaultNode = NULL;
 620
 621   for (unsigned I = 1, E = SI->getNumCases(); I < E; ++I) {
 622     ConstantInt *CI = SI->getCaseValue(I);
 623
 624     BasicBlock *SuccBB = SI->getSuccessor(I);
 625     PropertySet copy(KP);
 626     if (SuccBB->getSinglePredecessor()) {
 627       PropertySet NewProperties(KP);
 628       NewProperties.addEqual(Condition, CI);
 629       proceedToSuccessor(copy, NewProperties, DTNode, DT->getNode(SuccBB));
 630     } else
 631       proceedToSuccessor(copy, DTNode, DT->getNode(SuccBB));
 632
 633     if (DefaultNode)
 634       DefaultProperties.addNotEqual(Condition, CI);
 635   }
 636
 637   if (DefaultNode)
 638     proceedToSuccessor(DefaultProperties, DTNode, DefaultNode);
 639 }
 640
 641 void PredicateSimplifier::visit(LoadInst *LI,
 642                                 DominatorTree::Node *, PropertySet &KP) {
 643   Value *Ptr = LI->getPointerOperand();
 644   KP.addNotEqual(Constant::getNullValue(Ptr->getType()), Ptr);
 645 }
 646
 647 void PredicateSimplifier::visit(StoreInst *SI,
 648                                 DominatorTree::Node *, PropertySet &KP) {
 649   Value *Ptr = SI->getPointerOperand();
 650   KP.addNotEqual(Constant::getNullValue(Ptr->getType()), Ptr);
 651 }
 652
 653 void PredicateSimplifier::visit(BinaryOperator *BO,
 654                                 DominatorTree::Node *, PropertySet &KP) {
 655   Instruction::BinaryOps ops = BO->getOpcode();
 656
 657   switch (ops) {
 658     case Instruction::Div:
 659     case Instruction::Rem: {
 660       Value *Divisor = BO->getOperand(1);
 661       KP.addNotEqual(Constant::getNullValue(Divisor->getType()), Divisor);
 662       break;
 663     }
 664     default:
 665       break;
 666   }
 667
 668   // Some other things we could do:
 669   // In f=x*y, if x != 1 && y != 1 then f != x && f != y.
 670   // In f=x+y, if x != 0 then f != y and if y != 0 then f != x.
 671 }