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