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