lib/Transforms/Scalar/SCCP.cpp

   1 //===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements sparse conditional constant propagation and merging:
  11 //
  12 // Specifically, this:
  13 //   * Assumes values are constant unless proven otherwise
  14 //   * Assumes BasicBlocks are dead unless proven otherwise
  15 //   * Proves values to be constant, and replaces them with constants
  16 //   * Proves conditional branches to be unconditional
  17 //
  18 // Notice that:
  19 //   * This pass has a habit of making definitions be dead.  It is a good idea
  20 //     to to run a DCE pass sometime after running this pass.
  21 //
  22 //===----------------------------------------------------------------------===//
  23
  24 #include "llvm/Transforms/Scalar.h"
  25 #include "llvm/Constants.h"
  26 #include "llvm/Function.h"
  27 #include "llvm/GlobalVariable.h"
  28 #include "llvm/Instructions.h"
  29 #include "llvm/Pass.h"
  30 #include "llvm/Type.h"
  31 #include "llvm/Support/InstVisitor.h"
  32 #include "llvm/Transforms/Utils/Local.h"
  33 #include "Support/Debug.h"
  34 #include "Support/Statistic.h"
  35 #include "Support/STLExtras.h"
  36 #include <algorithm>
  37 #include <set>
  38 using namespace llvm;
  39
  40 // InstVal class - This class represents the different lattice values that an
  41 // instruction may occupy.  It is a simple class with value semantics.
  42 //
  43 namespace {
  44   Statistic<> NumInstRemoved("sccp", "Number of instructions removed");
  45
  46 class InstVal {
  47   enum {
  48     undefined,           // This instruction has no known value
  49     constant,            // This instruction has a constant value
  50     overdefined          // This instruction has an unknown value
  51   } LatticeValue;        // The current lattice position
  52   Constant *ConstantVal; // If Constant value, the current value
  53 public:
  54   inline InstVal() : LatticeValue(undefined), ConstantVal(0) {}
  55
  56   // markOverdefined - Return true if this is a new status to be in...
  57   inline bool markOverdefined() {
  58     if (LatticeValue != overdefined) {
  59       LatticeValue = overdefined;
  60       return true;
  61     }
  62     return false;
  63   }
  64
  65   // markConstant - Return true if this is a new status for us...
  66   inline bool markConstant(Constant *V) {
  67     if (LatticeValue != constant) {
  68       LatticeValue = constant;
  69       ConstantVal = V;
  70       return true;
  71     } else {
  72       assert(ConstantVal == V && "Marking constant with different value");
  73     }
  74     return false;
  75   }
  76
  77   inline bool isUndefined()   const { return LatticeValue == undefined; }
  78   inline bool isConstant()    const { return LatticeValue == constant; }
  79   inline bool isOverdefined() const { return LatticeValue == overdefined; }
  80
  81   inline Constant *getConstant() const {
  82     assert(isConstant() && "Cannot get the constant of a non-constant!");
  83     return ConstantVal;
  84   }
  85 };
  86
  87 } // end anonymous namespace
  88
  89
  90 //===----------------------------------------------------------------------===//
  91 // SCCP Class
  92 //
  93 // This class does all of the work of Sparse Conditional Constant Propagation.
  94 //
  95 namespace {
  96 class SCCP : public FunctionPass, public InstVisitor<SCCP> {
  97   std::set<BasicBlock*>     BBExecutable;// The basic blocks that are executable
  98   std::map<Value*, InstVal> ValueState;  // The state each value is in...
  99
 100   std::vector<Instruction*> InstWorkList;// The instruction work list
 101   std::vector<BasicBlock*>  BBWorkList;  // The BasicBlock work list
 102
 103   /// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not
 104   /// overdefined, despite the fact that the PHI node is overdefined.
 105   std::multimap<PHINode*, Instruction*> UsersOfOverdefinedPHIs;
 106
 107   /// KnownFeasibleEdges - Entries in this set are edges which have already had
 108   /// PHI nodes retriggered.
 109   typedef std::pair<BasicBlock*,BasicBlock*> Edge;
 110   std::set<Edge> KnownFeasibleEdges;
 111 public:
 112
 113   // runOnFunction - Run the Sparse Conditional Constant Propagation algorithm,
 114   // and return true if the function was modified.
 115   //
 116   bool runOnFunction(Function &F);
 117
 118   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 119     AU.setPreservesCFG();
 120   }
 121
 122
 123   //===--------------------------------------------------------------------===//
 124   // The implementation of this class
 125   //
 126 private:
 127   friend class InstVisitor<SCCP>;        // Allow callbacks from visitor
 128
 129   // markValueOverdefined - Make a value be marked as "constant".  If the value
 130   // is not already a constant, add it to the instruction work list so that
 131   // the users of the instruction are updated later.
 132   //
 133   inline void markConstant(InstVal &IV, Instruction *I, Constant *C) {
 134     if (IV.markConstant(C)) {
 135       DEBUG(std::cerr << "markConstant: " << *C << ": " << *I);
 136       InstWorkList.push_back(I);
 137     }
 138   }
 139   inline void markConstant(Instruction *I, Constant *C) {
 140     markConstant(ValueState[I], I, C);
 141   }
 142
 143   // markValueOverdefined - Make a value be marked as "overdefined". If the
 144   // value is not already overdefined, add it to the instruction work list so
 145   // that the users of the instruction are updated later.
 146   //
 147   inline void markOverdefined(InstVal &IV, Instruction *I) {
 148     if (IV.markOverdefined()) {
 149       DEBUG(std::cerr << "markOverdefined: " << *I);
 150       InstWorkList.push_back(I);  // Only instructions go on the work list
 151     }
 152   }
 153   inline void markOverdefined(Instruction *I) {
 154     markOverdefined(ValueState[I], I);
 155   }
 156
 157   // getValueState - Return the InstVal object that corresponds to the value.
 158   // This function is necessary because not all values should start out in the
 159   // underdefined state... Argument's should be overdefined, and
 160   // constants should be marked as constants.  If a value is not known to be an
 161   // Instruction object, then use this accessor to get its value from the map.
 162   //
 163   inline InstVal &getValueState(Value *V) {
 164     std::map<Value*, InstVal>::iterator I = ValueState.find(V);
 165     if (I != ValueState.end()) return I->second;  // Common case, in the map
 166
 167     if (Constant *CPV = dyn_cast<Constant>(V)) {  // Constants are constant
 168       ValueState[CPV].markConstant(CPV);
 169     } else if (isa<Argument>(V)) {                // Arguments are overdefined
 170       ValueState[V].markOverdefined();
 171     } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 172       // The address of a global is a constant...
 173       ValueState[V].markConstant(ConstantPointerRef::get(GV));
 174     }
 175     // All others are underdefined by default...
 176     return ValueState[V];
 177   }
 178
 179   // markEdgeExecutable - Mark a basic block as executable, adding it to the BB
 180   // work list if it is not already executable...
 181   //
 182   void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
 183     if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
 184       return;  // This edge is already known to be executable!
 185
 186     if (BBExecutable.count(Dest)) {
 187       DEBUG(std::cerr << "Marking Edge Executable: " << Source->getName()
 188                       << " -> " << Dest->getName() << "\n");
 189
 190       // The destination is already executable, but we just made an edge
 191       // feasible that wasn't before.  Revisit the PHI nodes in the block
 192       // because they have potentially new operands.
 193       for (BasicBlock::iterator I = Dest->begin();
 194            PHINode *PN = dyn_cast<PHINode>(I); ++I)
 195         visitPHINode(*PN);
 196
 197     } else {
 198       DEBUG(std::cerr << "Marking Block Executable: " << Dest->getName()<<"\n");
 199       BBExecutable.insert(Dest);   // Basic block is executable!
 200       BBWorkList.push_back(Dest);  // Add the block to the work list!
 201     }
 202   }
 203
 204
 205   // visit implementations - Something changed in this instruction... Either an
 206   // operand made a transition, or the instruction is newly executable.  Change
 207   // the value type of I to reflect these changes if appropriate.
 208   //
 209   void visitPHINode(PHINode &I);
 210
 211   // Terminators
 212   void visitReturnInst(ReturnInst &I) { /*does not have an effect*/ }
 213   void visitTerminatorInst(TerminatorInst &TI);
 214
 215   void visitCastInst(CastInst &I);
 216   void visitSelectInst(SelectInst &I);
 217   void visitBinaryOperator(Instruction &I);
 218   void visitShiftInst(ShiftInst &I) { visitBinaryOperator(I); }
 219
 220   // Instructions that cannot be folded away...
 221   void visitStoreInst     (Instruction &I) { /*returns void*/ }
 222   void visitLoadInst      (LoadInst &I);
 223   void visitGetElementPtrInst(GetElementPtrInst &I);
 224   void visitCallInst      (CallInst &I);
 225   void visitInvokeInst    (TerminatorInst &I) {
 226     if (I.getType() != Type::VoidTy) markOverdefined(&I);
 227     visitTerminatorInst(I);
 228   }
 229   void visitUnwindInst    (TerminatorInst &I) { /*returns void*/ }
 230   void visitAllocationInst(Instruction &I) { markOverdefined(&I); }
 231   void visitVANextInst    (Instruction &I) { markOverdefined(&I); }
 232   void visitVAArgInst     (Instruction &I) { markOverdefined(&I); }
 233   void visitFreeInst      (Instruction &I) { /*returns void*/ }
 234
 235   void visitInstruction(Instruction &I) {
 236     // If a new instruction is added to LLVM that we don't handle...
 237     std::cerr << "SCCP: Don't know how to handle: " << I;
 238     markOverdefined(&I);   // Just in case
 239   }
 240
 241   // getFeasibleSuccessors - Return a vector of booleans to indicate which
 242   // successors are reachable from a given terminator instruction.
 243   //
 244   void getFeasibleSuccessors(TerminatorInst &TI, std::vector<bool> &Succs);
 245
 246   // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
 247   // block to the 'To' basic block is currently feasible...
 248   //
 249   bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
 250
 251   // OperandChangedState - This method is invoked on all of the users of an
 252   // instruction that was just changed state somehow....  Based on this
 253   // information, we need to update the specified user of this instruction.
 254   //
 255   void OperandChangedState(User *U) {
 256     // Only instructions use other variable values!
 257     Instruction &I = cast<Instruction>(*U);
 258     if (BBExecutable.count(I.getParent()))   // Inst is executable?
 259       visit(I);
 260   }
 261 };
 262
 263   RegisterOpt<SCCP> X("sccp", "Sparse Conditional Constant Propagation");
 264 } // end anonymous namespace
 265
 266
 267 // createSCCPPass - This is the public interface to this file...
 268 Pass *llvm::createSCCPPass() {
 269   return new SCCP();
 270 }
 271
 272
 273 //===----------------------------------------------------------------------===//
 274 // SCCP Class Implementation
 275
 276
 277 // runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm,
 278 // and return true if the function was modified.
 279 //
 280 bool SCCP::runOnFunction(Function &F) {
 281   // Mark the first block of the function as being executable...
 282   BBExecutable.insert(F.begin());   // Basic block is executable!
 283   BBWorkList.push_back(F.begin());  // Add the block to the work list!
 284
 285   // Process the work lists until their are empty!
 286   while (!BBWorkList.empty() || !InstWorkList.empty()) {
 287     // Process the instruction work list...
 288     while (!InstWorkList.empty()) {
 289       Instruction *I = InstWorkList.back();
 290       InstWorkList.pop_back();
 291
 292       DEBUG(std::cerr << "\nPopped off I-WL: " << I);
 293
 294       // "I" got into the work list because it either made the transition from
 295       // bottom to constant, or to Overdefined.
 296       //
 297       // Update all of the users of this instruction's value...
 298       //
 299       for_each(I->use_begin(), I->use_end(),
 300                bind_obj(this, &SCCP::OperandChangedState));
 301     }
 302
 303     // Process the basic block work list...
 304     while (!BBWorkList.empty()) {
 305       BasicBlock *BB = BBWorkList.back();
 306       BBWorkList.pop_back();
 307
 308       DEBUG(std::cerr << "\nPopped off BBWL: " << BB);
 309
 310       // Notify all instructions in this basic block that they are newly
 311       // executable.
 312       visit(BB);
 313     }
 314   }
 315
 316   if (DebugFlag) {
 317     for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 318       if (!BBExecutable.count(I))
 319         std::cerr << "BasicBlock Dead:" << *I;
 320   }
 321
 322   // Iterate over all of the instructions in a function, replacing them with
 323   // constants if we have found them to be of constant values.
 324   //
 325   bool MadeChanges = false;
 326   for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB)
 327     for (BasicBlock::iterator BI = BB->begin(); BI != BB->end();) {
 328       Instruction &Inst = *BI;
 329       InstVal &IV = ValueState[&Inst];
 330       if (IV.isConstant()) {
 331         Constant *Const = IV.getConstant();
 332         DEBUG(std::cerr << "Constant: " << Const << " = " << Inst);
 333
 334         // Replaces all of the uses of a variable with uses of the constant.
 335         Inst.replaceAllUsesWith(Const);
 336
 337         // Remove the operator from the list of definitions... and delete it.
 338         BI = BB->getInstList().erase(BI);
 339
 340         // Hey, we just changed something!
 341         MadeChanges = true;
 342         ++NumInstRemoved;
 343       } else {
 344         ++BI;
 345       }
 346     }
 347
 348   // Reset state so that the next invocation will have empty data structures
 349   BBExecutable.clear();
 350   ValueState.clear();
 351   std::vector<Instruction*>().swap(InstWorkList);
 352   std::vector<BasicBlock*>().swap(BBWorkList);
 353
 354   return MadeChanges;
 355 }
 356
 357
 358 // getFeasibleSuccessors - Return a vector of booleans to indicate which
 359 // successors are reachable from a given terminator instruction.
 360 //
 361 void SCCP::getFeasibleSuccessors(TerminatorInst &TI, std::vector<bool> &Succs) {
 362   Succs.resize(TI.getNumSuccessors());
 363   if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
 364     if (BI->isUnconditional()) {
 365       Succs[0] = true;
 366     } else {
 367       InstVal &BCValue = getValueState(BI->getCondition());
 368       if (BCValue.isOverdefined() ||
 369           (BCValue.isConstant() && !isa<ConstantBool>(BCValue.getConstant()))) {
 370         // Overdefined condition variables, and branches on unfoldable constant
 371         // conditions, mean the branch could go either way.
 372         Succs[0] = Succs[1] = true;
 373       } else if (BCValue.isConstant()) {
 374         // Constant condition variables mean the branch can only go a single way
 375         Succs[BCValue.getConstant() == ConstantBool::False] = true;
 376       }
 377     }
 378   } else if (InvokeInst *II = dyn_cast<InvokeInst>(&TI)) {
 379     // Invoke instructions successors are always executable.
 380     Succs[0] = Succs[1] = true;
 381   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) {
 382     InstVal &SCValue = getValueState(SI->getCondition());
 383     if (SCValue.isOverdefined() ||   // Overdefined condition?
 384         (SCValue.isConstant() && !isa<ConstantInt>(SCValue.getConstant()))) {
 385       // All destinations are executable!
 386       Succs.assign(TI.getNumSuccessors(), true);
 387     } else if (SCValue.isConstant()) {
 388       Constant *CPV = SCValue.getConstant();
 389       // Make sure to skip the "default value" which isn't a value
 390       for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) {
 391         if (SI->getSuccessorValue(i) == CPV) {// Found the right branch...
 392           Succs[i] = true;
 393           return;
 394         }
 395       }
 396
 397       // Constant value not equal to any of the branches... must execute
 398       // default branch then...
 399       Succs[0] = true;
 400     }
 401   } else {
 402     std::cerr << "SCCP: Don't know how to handle: " << TI;
 403     Succs.assign(TI.getNumSuccessors(), true);
 404   }
 405 }
 406
 407
 408 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
 409 // block to the 'To' basic block is currently feasible...
 410 //
 411 bool SCCP::isEdgeFeasible(BasicBlock *From, BasicBlock *To) {
 412   assert(BBExecutable.count(To) && "Dest should always be alive!");
 413
 414   // Make sure the source basic block is executable!!
 415   if (!BBExecutable.count(From)) return false;
 416
 417   // Check to make sure this edge itself is actually feasible now...
 418   TerminatorInst *TI = From->getTerminator();
 419   if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 420     if (BI->isUnconditional())
 421       return true;
 422     else {
 423       InstVal &BCValue = getValueState(BI->getCondition());
 424       if (BCValue.isOverdefined()) {
 425         // Overdefined condition variables mean the branch could go either way.
 426         return true;
 427       } else if (BCValue.isConstant()) {
 428         // Not branching on an evaluatable constant?
 429         if (!isa<ConstantBool>(BCValue.getConstant())) return true;
 430
 431         // Constant condition variables mean the branch can only go a single way
 432         return BI->getSuccessor(BCValue.getConstant() ==
 433                                        ConstantBool::False) == To;
 434       }
 435       return false;
 436     }
 437   } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
 438     // Invoke instructions successors are always executable.
 439     return true;
 440   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 441     InstVal &SCValue = getValueState(SI->getCondition());
 442     if (SCValue.isOverdefined()) {  // Overdefined condition?
 443       // All destinations are executable!
 444       return true;
 445     } else if (SCValue.isConstant()) {
 446       Constant *CPV = SCValue.getConstant();
 447       if (!isa<ConstantInt>(CPV))
 448         return true;  // not a foldable constant?
 449
 450       // Make sure to skip the "default value" which isn't a value
 451       for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i)
 452         if (SI->getSuccessorValue(i) == CPV) // Found the taken branch...
 453           return SI->getSuccessor(i) == To;
 454
 455       // Constant value not equal to any of the branches... must execute
 456       // default branch then...
 457       return SI->getDefaultDest() == To;
 458     }
 459     return false;
 460   } else {
 461     std::cerr << "Unknown terminator instruction: " << *TI;
 462     abort();
 463   }
 464 }
 465
 466 // visit Implementations - Something changed in this instruction... Either an
 467 // operand made a transition, or the instruction is newly executable.  Change
 468 // the value type of I to reflect these changes if appropriate.  This method
 469 // makes sure to do the following actions:
 470 //
 471 // 1. If a phi node merges two constants in, and has conflicting value coming
 472 //    from different branches, or if the PHI node merges in an overdefined
 473 //    value, then the PHI node becomes overdefined.
 474 // 2. If a phi node merges only constants in, and they all agree on value, the
 475 //    PHI node becomes a constant value equal to that.
 476 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
 477 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
 478 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
 479 // 6. If a conditional branch has a value that is constant, make the selected
 480 //    destination executable
 481 // 7. If a conditional branch has a value that is overdefined, make all
 482 //    successors executable.
 483 //
 484 void SCCP::visitPHINode(PHINode &PN) {
 485   InstVal &PNIV = getValueState(&PN);
 486   if (PNIV.isOverdefined()) {
 487     // There may be instructions using this PHI node that are not overdefined
 488     // themselves.  If so, make sure that they know that the PHI node operand
 489     // changed.
 490     std::multimap<PHINode*, Instruction*>::iterator I, E;
 491     tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN);
 492     if (I != E) {
 493       std::vector<Instruction*> Users;
 494       Users.reserve(std::distance(I, E));
 495       for (; I != E; ++I) Users.push_back(I->second);
 496       while (!Users.empty()) {
 497         visit(Users.back());
 498         Users.pop_back();
 499       }
 500     }
 501     return;  // Quick exit
 502   }
 503
 504   // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
 505   // and slow us down a lot.  Just mark them overdefined.
 506   if (PN.getNumIncomingValues() > 64) {
 507     markOverdefined(PNIV, &PN);
 508     return;
 509   }
 510
 511   // Look at all of the executable operands of the PHI node.  If any of them
 512   // are overdefined, the PHI becomes overdefined as well.  If they are all
 513   // constant, and they agree with each other, the PHI becomes the identical
 514   // constant.  If they are constant and don't agree, the PHI is overdefined.
 515   // If there are no executable operands, the PHI remains undefined.
 516   //
 517   Constant *OperandVal = 0;
 518   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
 519     InstVal &IV = getValueState(PN.getIncomingValue(i));
 520     if (IV.isUndefined()) continue;  // Doesn't influence PHI node.
 521
 522     if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) {
 523       if (IV.isOverdefined()) {   // PHI node becomes overdefined!
 524         markOverdefined(PNIV, &PN);
 525         return;
 526       }
 527
 528       if (OperandVal == 0) {   // Grab the first value...
 529         OperandVal = IV.getConstant();
 530       } else {                // Another value is being merged in!
 531         // There is already a reachable operand.  If we conflict with it,
 532         // then the PHI node becomes overdefined.  If we agree with it, we
 533         // can continue on.
 534
 535         // Check to see if there are two different constants merging...
 536         if (IV.getConstant() != OperandVal) {
 537           // Yes there is.  This means the PHI node is not constant.
 538           // You must be overdefined poor PHI.
 539           //
 540           markOverdefined(PNIV, &PN);    // The PHI node now becomes overdefined
 541           return;    // I'm done analyzing you
 542         }
 543       }
 544     }
 545   }
 546
 547   // If we exited the loop, this means that the PHI node only has constant
 548   // arguments that agree with each other(and OperandVal is the constant) or
 549   // OperandVal is null because there are no defined incoming arguments.  If
 550   // this is the case, the PHI remains undefined.
 551   //
 552   if (OperandVal)
 553     markConstant(PNIV, &PN, OperandVal);      // Acquire operand value
 554 }
 555
 556 void SCCP::visitTerminatorInst(TerminatorInst &TI) {
 557   std::vector<bool> SuccFeasible;
 558   getFeasibleSuccessors(TI, SuccFeasible);
 559
 560   BasicBlock *BB = TI.getParent();
 561
 562   // Mark all feasible successors executable...
 563   for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
 564     if (SuccFeasible[i])
 565       markEdgeExecutable(BB, TI.getSuccessor(i));
 566 }
 567
 568 void SCCP::visitCastInst(CastInst &I) {
 569   Value *V = I.getOperand(0);
 570   InstVal &VState = getValueState(V);
 571   if (VState.isOverdefined())          // Inherit overdefinedness of operand
 572     markOverdefined(&I);
 573   else if (VState.isConstant())        // Propagate constant value
 574     markConstant(&I, ConstantExpr::getCast(VState.getConstant(), I.getType()));
 575 }
 576
 577 void SCCP::visitSelectInst(SelectInst &I) {
 578   InstVal &CondValue = getValueState(I.getCondition());
 579   if (CondValue.isOverdefined())
 580     markOverdefined(&I);
 581   else if (CondValue.isConstant()) {
 582     if (CondValue.getConstant() == ConstantBool::True) {
 583       InstVal &Val = getValueState(I.getTrueValue());
 584       if (Val.isOverdefined())
 585         markOverdefined(&I);
 586       else if (Val.isConstant())
 587         markConstant(&I, Val.getConstant());
 588     } else if (CondValue.getConstant() == ConstantBool::False) {
 589       InstVal &Val = getValueState(I.getFalseValue());
 590       if (Val.isOverdefined())
 591         markOverdefined(&I);
 592       else if (Val.isConstant())
 593         markConstant(&I, Val.getConstant());
 594     } else
 595       markOverdefined(&I);
 596   }
 597 }
 598
 599 // Handle BinaryOperators and Shift Instructions...
 600 void SCCP::visitBinaryOperator(Instruction &I) {
 601   InstVal &IV = ValueState[&I];
 602   if (IV.isOverdefined()) return;
 603
 604   InstVal &V1State = getValueState(I.getOperand(0));
 605   InstVal &V2State = getValueState(I.getOperand(1));
 606
 607   if (V1State.isOverdefined() || V2State.isOverdefined()) {
 608     // If both operands are PHI nodes, it is possible that this instruction has
 609     // a constant value, despite the fact that the PHI node doesn't.  Check for
 610     // this condition now.
 611     if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0)))
 612       if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1)))
 613         if (PN1->getParent() == PN2->getParent()) {
 614           // Since the two PHI nodes are in the same basic block, they must have
 615           // entries for the same predecessors.  Walk the predecessor list, and
 616           // if all of the incoming values are constants, and the result of
 617           // evaluating this expression with all incoming value pairs is the
 618           // same, then this expression is a constant even though the PHI node
 619           // is not a constant!
 620           InstVal Result;
 621           for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) {
 622             InstVal &In1 = getValueState(PN1->getIncomingValue(i));
 623             BasicBlock *InBlock = PN1->getIncomingBlock(i);
 624             InstVal &In2 =getValueState(PN2->getIncomingValueForBlock(InBlock));
 625
 626             if (In1.isOverdefined() || In2.isOverdefined()) {
 627               Result.markOverdefined();
 628               break;  // Cannot fold this operation over the PHI nodes!
 629             } else if (In1.isConstant() && In2.isConstant()) {
 630               Constant *V = ConstantExpr::get(I.getOpcode(), In1.getConstant(),
 631                                               In2.getConstant());
 632               if (Result.isUndefined())
 633                 Result.markConstant(V);
 634               else if (Result.isConstant() && Result.getConstant() != V) {
 635                 Result.markOverdefined();
 636                 break;
 637               }
 638             }
 639           }
 640
 641           // If we found a constant value here, then we know the instruction is
 642           // constant despite the fact that the PHI nodes are overdefined.
 643           if (Result.isConstant()) {
 644             markConstant(IV, &I, Result.getConstant());
 645             // Remember that this instruction is virtually using the PHI node
 646             // operands.
 647             UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I));
 648             UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I));
 649             return;
 650           } else if (Result.isUndefined()) {
 651             return;
 652           }
 653
 654           // Okay, this really is overdefined now.  Since we might have
 655           // speculatively thought that this was not overdefined before, and
 656           // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs,
 657           // make sure to clean out any entries that we put there, for
 658           // efficiency.
 659           std::multimap<PHINode*, Instruction*>::iterator It, E;
 660           tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1);
 661           while (It != E) {
 662             if (It->second == &I) {
 663               UsersOfOverdefinedPHIs.erase(It++);
 664             } else
 665               ++It;
 666           }
 667           tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2);
 668           while (It != E) {
 669             if (It->second == &I) {
 670               UsersOfOverdefinedPHIs.erase(It++);
 671             } else
 672               ++It;
 673           }
 674         }
 675
 676     markOverdefined(IV, &I);
 677   } else if (V1State.isConstant() && V2State.isConstant()) {
 678     markConstant(IV, &I, ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
 679                                            V2State.getConstant()));
 680   }
 681 }
 682
 683 // Handle getelementptr instructions... if all operands are constants then we
 684 // can turn this into a getelementptr ConstantExpr.
 685 //
 686 void SCCP::visitGetElementPtrInst(GetElementPtrInst &I) {
 687   InstVal &IV = ValueState[&I];
 688   if (IV.isOverdefined()) return;
 689
 690   std::vector<Constant*> Operands;
 691   Operands.reserve(I.getNumOperands());
 692
 693   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
 694     InstVal &State = getValueState(I.getOperand(i));
 695     if (State.isUndefined())
 696       return;  // Operands are not resolved yet...
 697     else if (State.isOverdefined()) {
 698       markOverdefined(IV, &I);
 699       return;
 700     }
 701     assert(State.isConstant() && "Unknown state!");
 702     Operands.push_back(State.getConstant());
 703   }
 704
 705   Constant *Ptr = Operands[0];
 706   Operands.erase(Operands.begin());  // Erase the pointer from idx list...
 707
 708   markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, Operands));
 709 }
 710
 711 /// GetGEPGlobalInitializer - Given a constant and a getelementptr constantexpr,
 712 /// return the constant value being addressed by the constant expression, or
 713 /// null if something is funny.
 714 ///
 715 static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) {
 716   if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType()))
 717     return 0;  // Do not allow stepping over the value!
 718
 719   // Loop over all of the operands, tracking down which value we are
 720   // addressing...
 721   for (unsigned i = 2, e = CE->getNumOperands(); i != e; ++i)
 722     if (ConstantUInt *CU = dyn_cast<ConstantUInt>(CE->getOperand(i))) {
 723       ConstantStruct *CS = dyn_cast<ConstantStruct>(C);
 724       if (CS == 0) return 0;
 725       if (CU->getValue() >= CS->getValues().size()) return 0;
 726       C = cast<Constant>(CS->getValues()[CU->getValue()]);
 727     } else if (ConstantSInt *CS = dyn_cast<ConstantSInt>(CE->getOperand(i))) {
 728       ConstantArray *CA = dyn_cast<ConstantArray>(C);
 729       if (CA == 0) return 0;
 730       if ((uint64_t)CS->getValue() >= CA->getValues().size()) return 0;
 731       C = cast<Constant>(CA->getValues()[CS->getValue()]);
 732     } else
 733       return 0;
 734   return C;
 735 }
 736
 737 // Handle load instructions.  If the operand is a constant pointer to a constant
 738 // global, we can replace the load with the loaded constant value!
 739 void SCCP::visitLoadInst(LoadInst &I) {
 740   InstVal &IV = ValueState[&I];
 741   if (IV.isOverdefined()) return;
 742
 743   InstVal &PtrVal = getValueState(I.getOperand(0));
 744   if (PtrVal.isUndefined()) return;   // The pointer is not resolved yet!
 745   if (PtrVal.isConstant() && !I.isVolatile()) {
 746     Value *Ptr = PtrVal.getConstant();
 747     if (isa<ConstantPointerNull>(Ptr)) {
 748       // load null -> null
 749       markConstant(IV, &I, Constant::getNullValue(I.getType()));
 750       return;
 751     }
 752
 753     if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(Ptr))
 754       Ptr = CPR->getValue();
 755
 756     // Transform load (constant global) into the value loaded.
 757     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr))
 758       if (GV->isConstant() && !GV->isExternal()) {
 759         markConstant(IV, &I, GV->getInitializer());
 760         return;
 761       }
 762
 763     // Transform load (constantexpr_GEP global, 0, ...) into the value loaded.
 764     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
 765       if (CE->getOpcode() == Instruction::GetElementPtr)
 766         if (ConstantPointerRef *G
 767             = dyn_cast<ConstantPointerRef>(CE->getOperand(0)))
 768           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getValue()))
 769             if (GV->isConstant() && !GV->isExternal())
 770               if (Constant *V =
 771                   GetGEPGlobalInitializer(GV->getInitializer(), CE)) {
 772                 markConstant(IV, &I, V);
 773                 return;
 774               }
 775   }
 776
 777   // Otherwise we cannot say for certain what value this load will produce.
 778   // Bail out.
 779   markOverdefined(IV, &I);
 780 }
 781
 782 void SCCP::visitCallInst(CallInst &I) {
 783   InstVal &IV = ValueState[&I];
 784   if (IV.isOverdefined()) return;
 785
 786   Function *F = I.getCalledFunction();
 787   if (F == 0 || !canConstantFoldCallTo(F)) {
 788     markOverdefined(IV, &I);
 789     return;
 790   }
 791
 792   std::vector<Constant*> Operands;
 793   Operands.reserve(I.getNumOperands()-1);
 794
 795   for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) {
 796     InstVal &State = getValueState(I.getOperand(i));
 797     if (State.isUndefined())
 798       return;  // Operands are not resolved yet...
 799     else if (State.isOverdefined()) {
 800       markOverdefined(IV, &I);
 801       return;
 802     }
 803     assert(State.isConstant() && "Unknown state!");
 804     Operands.push_back(State.getConstant());
 805   }
 806
 807   if (Constant *C = ConstantFoldCall(F, Operands))
 808     markConstant(IV, &I, C);
 809   else
 810     markOverdefined(IV, &I);
 811 }