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 #define DEBUG_TYPE "sccp"
  25 #include "llvm/Transforms/Scalar.h"
  26 #include "llvm/Transforms/IPO.h"
  27 #include "llvm/Constants.h"
  28 #include "llvm/Function.h"
  29 #include "llvm/GlobalVariable.h"
  30 #include "llvm/Instructions.h"
  31 #include "llvm/Pass.h"
  32 #include "llvm/Type.h"
  33 #include "llvm/Support/InstVisitor.h"
  34 #include "llvm/Transforms/Utils/Local.h"
  35 #include "llvm/Support/CallSite.h"
  36 #include "llvm/Support/Debug.h"
  37 #include "llvm/ADT/hash_map"
  38 #include "llvm/ADT/Statistic.h"
  39 #include "llvm/ADT/STLExtras.h"
  40 #include <algorithm>
  41 #include <set>
  42 using namespace llvm;
  43
  44 // LatticeVal class - This class represents the different lattice values that an
  45 // instruction may occupy.  It is a simple class with value semantics.
  46 //
  47 namespace {
  48
  49 class LatticeVal {
  50   enum {
  51     undefined,           // This instruction has no known value
  52     constant,            // This instruction has a constant value
  53     overdefined          // This instruction has an unknown value
  54   } LatticeValue;        // The current lattice position
  55   Constant *ConstantVal; // If Constant value, the current value
  56 public:
  57   inline LatticeVal() : LatticeValue(undefined), ConstantVal(0) {}
  58
  59   // markOverdefined - Return true if this is a new status to be in...
  60   inline bool markOverdefined() {
  61     if (LatticeValue != overdefined) {
  62       LatticeValue = overdefined;
  63       return true;
  64     }
  65     return false;
  66   }
  67
  68   // markConstant - Return true if this is a new status for us...
  69   inline bool markConstant(Constant *V) {
  70     if (LatticeValue != constant) {
  71       LatticeValue = constant;
  72       ConstantVal = V;
  73       return true;
  74     } else {
  75       assert(ConstantVal == V && "Marking constant with different value");
  76     }
  77     return false;
  78   }
  79
  80   inline bool isUndefined()   const { return LatticeValue == undefined; }
  81   inline bool isConstant()    const { return LatticeValue == constant; }
  82   inline bool isOverdefined() const { return LatticeValue == overdefined; }
  83
  84   inline Constant *getConstant() const {
  85     assert(isConstant() && "Cannot get the constant of a non-constant!");
  86     return ConstantVal;
  87   }
  88 };
  89
  90 } // end anonymous namespace
  91
  92
  93 //===----------------------------------------------------------------------===//
  94 //
  95 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional
  96 /// Constant Propagation.
  97 ///
  98 class SCCPSolver : public InstVisitor<SCCPSolver> {
  99   std::set<BasicBlock*>     BBExecutable;// The basic blocks that are executable
 100   hash_map<Value*, LatticeVal> ValueState;  // The state each value is in...
 101
 102   /// TrackedFunctionRetVals - If we are tracking arguments into and the return
 103   /// value out of a function, it will have an entry in this map, indicating
 104   /// what the known return value for the function is.
 105   hash_map<Function*, LatticeVal> TrackedFunctionRetVals;
 106
 107   // The reason for two worklists is that overdefined is the lowest state
 108   // on the lattice, and moving things to overdefined as fast as possible
 109   // makes SCCP converge much faster.
 110   // By having a separate worklist, we accomplish this because everything
 111   // possibly overdefined will become overdefined at the soonest possible
 112   // point.
 113   std::vector<Value*> OverdefinedInstWorkList;
 114   std::vector<Value*> InstWorkList;
 115
 116
 117   std::vector<BasicBlock*>  BBWorkList;  // The BasicBlock work list
 118
 119   /// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not
 120   /// overdefined, despite the fact that the PHI node is overdefined.
 121   std::multimap<PHINode*, Instruction*> UsersOfOverdefinedPHIs;
 122
 123   /// KnownFeasibleEdges - Entries in this set are edges which have already had
 124   /// PHI nodes retriggered.
 125   typedef std::pair<BasicBlock*,BasicBlock*> Edge;
 126   std::set<Edge> KnownFeasibleEdges;
 127 public:
 128
 129   /// MarkBlockExecutable - This method can be used by clients to mark all of
 130   /// the blocks that are known to be intrinsically live in the processed unit.
 131   void MarkBlockExecutable(BasicBlock *BB) {
 132     DEBUG(std::cerr << "Marking Block Executable: " << BB->getName() << "\n");
 133     BBExecutable.insert(BB);   // Basic block is executable!
 134     BBWorkList.push_back(BB);  // Add the block to the work list!
 135   }
 136
 137   /// TrackValueOfGlobalVariableIfPossible - Clients can use this method to
 138   /// inform the SCCPSolver that it should track loads and stores to the
 139   /// specified global variable if it can.  This is only legal to call if
 140   /// performing Interprocedural SCCP.
 141   void TrackValueOfGlobalVariableIfPossible(GlobalVariable *GV);
 142
 143   /// AddTrackedFunction - If the SCCP solver is supposed to track calls into
 144   /// and out of the specified function (which cannot have its address taken),
 145   /// this method must be called.
 146   void AddTrackedFunction(Function *F) {
 147     assert(F->hasInternalLinkage() && "Can only track internal functions!");
 148     // Add an entry, F -> undef.
 149     TrackedFunctionRetVals[F];
 150   }
 151
 152   /// Solve - Solve for constants and executable blocks.
 153   ///
 154   void Solve();
 155
 156   /// ResolveBranchesIn - While solving the dataflow for a function, we assume
 157   /// that branches on undef values cannot reach any of their successors.
 158   /// However, this is not a safe assumption.  After we solve dataflow, this
 159   /// method should be use to handle this.  If this returns true, the solver
 160   /// should be rerun.
 161   bool ResolveBranchesIn(Function &F);
 162
 163   /// getExecutableBlocks - Once we have solved for constants, return the set of
 164   /// blocks that is known to be executable.
 165   std::set<BasicBlock*> &getExecutableBlocks() {
 166     return BBExecutable;
 167   }
 168
 169   /// getValueMapping - Once we have solved for constants, return the mapping of
 170   /// LLVM values to LatticeVals.
 171   hash_map<Value*, LatticeVal> &getValueMapping() {
 172     return ValueState;
 173   }
 174
 175 private:
 176   // markConstant - Make a value be marked as "constant".  If the value
 177   // is not already a constant, add it to the instruction work list so that
 178   // the users of the instruction are updated later.
 179   //
 180   inline void markConstant(LatticeVal &IV, Value *V, Constant *C) {
 181     if (IV.markConstant(C)) {
 182       DEBUG(std::cerr << "markConstant: " << *C << ": " << *V);
 183       InstWorkList.push_back(V);
 184     }
 185   }
 186   inline void markConstant(Value *V, Constant *C) {
 187     markConstant(ValueState[V], V, C);
 188   }
 189
 190   // markOverdefined - Make a value be marked as "overdefined". If the
 191   // value is not already overdefined, add it to the overdefined instruction
 192   // work list so that the users of the instruction are updated later.
 193
 194   inline void markOverdefined(LatticeVal &IV, Value *V) {
 195     if (IV.markOverdefined()) {
 196       DEBUG(std::cerr << "markOverdefined: " << *V);
 197       // Only instructions go on the work list
 198       OverdefinedInstWorkList.push_back(V);
 199     }
 200   }
 201   inline void markOverdefined(Value *V) {
 202     markOverdefined(ValueState[V], V);
 203   }
 204
 205   inline void mergeInValue(LatticeVal &IV, Value *V, LatticeVal &MergeWithV) {
 206     if (IV.isOverdefined() || MergeWithV.isUndefined())
 207       return;  // Noop.
 208     if (MergeWithV.isOverdefined())
 209       markOverdefined(IV, V);
 210     else if (IV.isUndefined())
 211       markConstant(IV, V, MergeWithV.getConstant());
 212     else if (IV.getConstant() != MergeWithV.getConstant())
 213       markOverdefined(IV, V);
 214   }
 215
 216   // getValueState - Return the LatticeVal object that corresponds to the value.
 217   // This function is necessary because not all values should start out in the
 218   // underdefined state... Argument's should be overdefined, and
 219   // constants should be marked as constants.  If a value is not known to be an
 220   // Instruction object, then use this accessor to get its value from the map.
 221   //
 222   inline LatticeVal &getValueState(Value *V) {
 223     hash_map<Value*, LatticeVal>::iterator I = ValueState.find(V);
 224     if (I != ValueState.end()) return I->second;  // Common case, in the map
 225
 226     if (Constant *CPV = dyn_cast<Constant>(V)) {
 227       if (isa<UndefValue>(V)) {
 228         // Nothing to do, remain undefined.
 229       } else {
 230         ValueState[CPV].markConstant(CPV);          // Constants are constant
 231       }
 232     }
 233     // All others are underdefined by default...
 234     return ValueState[V];
 235   }
 236
 237   // markEdgeExecutable - Mark a basic block as executable, adding it to the BB
 238   // work list if it is not already executable...
 239   //
 240   void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
 241     if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
 242       return;  // This edge is already known to be executable!
 243
 244     if (BBExecutable.count(Dest)) {
 245       DEBUG(std::cerr << "Marking Edge Executable: " << Source->getName()
 246                       << " -> " << Dest->getName() << "\n");
 247
 248       // The destination is already executable, but we just made an edge
 249       // feasible that wasn't before.  Revisit the PHI nodes in the block
 250       // because they have potentially new operands.
 251       for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I)
 252         visitPHINode(*cast<PHINode>(I));
 253
 254     } else {
 255       MarkBlockExecutable(Dest);
 256     }
 257   }
 258
 259   // getFeasibleSuccessors - Return a vector of booleans to indicate which
 260   // successors are reachable from a given terminator instruction.
 261   //
 262   void getFeasibleSuccessors(TerminatorInst &TI, std::vector<bool> &Succs);
 263
 264   // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
 265   // block to the 'To' basic block is currently feasible...
 266   //
 267   bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
 268
 269   // OperandChangedState - This method is invoked on all of the users of an
 270   // instruction that was just changed state somehow....  Based on this
 271   // information, we need to update the specified user of this instruction.
 272   //
 273   void OperandChangedState(User *U) {
 274     // Only instructions use other variable values!
 275     Instruction &I = cast<Instruction>(*U);
 276     if (BBExecutable.count(I.getParent()))   // Inst is executable?
 277       visit(I);
 278   }
 279
 280 private:
 281   friend class InstVisitor<SCCPSolver>;
 282
 283   // visit implementations - Something changed in this instruction... Either an
 284   // operand made a transition, or the instruction is newly executable.  Change
 285   // the value type of I to reflect these changes if appropriate.
 286   //
 287   void visitPHINode(PHINode &I);
 288
 289   // Terminators
 290   void visitReturnInst(ReturnInst &I);
 291   void visitTerminatorInst(TerminatorInst &TI);
 292
 293   void visitCastInst(CastInst &I);
 294   void visitSelectInst(SelectInst &I);
 295   void visitBinaryOperator(Instruction &I);
 296   void visitShiftInst(ShiftInst &I) { visitBinaryOperator(I); }
 297
 298   // Instructions that cannot be folded away...
 299   void visitStoreInst     (Instruction &I) { /*returns void*/ }
 300   void visitLoadInst      (LoadInst &I);
 301   void visitGetElementPtrInst(GetElementPtrInst &I);
 302   void visitCallInst      (CallInst &I) { visitCallSite(CallSite::get(&I)); }
 303   void visitInvokeInst    (InvokeInst &II) {
 304     visitCallSite(CallSite::get(&II));
 305     visitTerminatorInst(II);
 306   }
 307   void visitCallSite      (CallSite CS);
 308   void visitUnwindInst    (TerminatorInst &I) { /*returns void*/ }
 309   void visitUnreachableInst(TerminatorInst &I) { /*returns void*/ }
 310   void visitAllocationInst(Instruction &I) { markOverdefined(&I); }
 311   void visitVANextInst    (Instruction &I) { markOverdefined(&I); }
 312   void visitVAArgInst     (Instruction &I) { markOverdefined(&I); }
 313   void visitFreeInst      (Instruction &I) { /*returns void*/ }
 314
 315   void visitInstruction(Instruction &I) {
 316     // If a new instruction is added to LLVM that we don't handle...
 317     std::cerr << "SCCP: Don't know how to handle: " << I;
 318     markOverdefined(&I);   // Just in case
 319   }
 320 };
 321
 322 // getFeasibleSuccessors - Return a vector of booleans to indicate which
 323 // successors are reachable from a given terminator instruction.
 324 //
 325 void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI,
 326                                        std::vector<bool> &Succs) {
 327   Succs.resize(TI.getNumSuccessors());
 328   if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
 329     if (BI->isUnconditional()) {
 330       Succs[0] = true;
 331     } else {
 332       LatticeVal &BCValue = getValueState(BI->getCondition());
 333       if (BCValue.isOverdefined() ||
 334           (BCValue.isConstant() && !isa<ConstantBool>(BCValue.getConstant()))) {
 335         // Overdefined condition variables, and branches on unfoldable constant
 336         // conditions, mean the branch could go either way.
 337         Succs[0] = Succs[1] = true;
 338       } else if (BCValue.isConstant()) {
 339         // Constant condition variables mean the branch can only go a single way
 340         Succs[BCValue.getConstant() == ConstantBool::False] = true;
 341       }
 342     }
 343   } else if (InvokeInst *II = dyn_cast<InvokeInst>(&TI)) {
 344     // Invoke instructions successors are always executable.
 345     Succs[0] = Succs[1] = true;
 346   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) {
 347     LatticeVal &SCValue = getValueState(SI->getCondition());
 348     if (SCValue.isOverdefined() ||   // Overdefined condition?
 349         (SCValue.isConstant() && !isa<ConstantInt>(SCValue.getConstant()))) {
 350       // All destinations are executable!
 351       Succs.assign(TI.getNumSuccessors(), true);
 352     } else if (SCValue.isConstant()) {
 353       Constant *CPV = SCValue.getConstant();
 354       // Make sure to skip the "default value" which isn't a value
 355       for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) {
 356         if (SI->getSuccessorValue(i) == CPV) {// Found the right branch...
 357           Succs[i] = true;
 358           return;
 359         }
 360       }
 361
 362       // Constant value not equal to any of the branches... must execute
 363       // default branch then...
 364       Succs[0] = true;
 365     }
 366   } else {
 367     std::cerr << "SCCP: Don't know how to handle: " << TI;
 368     Succs.assign(TI.getNumSuccessors(), true);
 369   }
 370 }
 371
 372
 373 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
 374 // block to the 'To' basic block is currently feasible...
 375 //
 376 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) {
 377   assert(BBExecutable.count(To) && "Dest should always be alive!");
 378
 379   // Make sure the source basic block is executable!!
 380   if (!BBExecutable.count(From)) return false;
 381
 382   // Check to make sure this edge itself is actually feasible now...
 383   TerminatorInst *TI = From->getTerminator();
 384   if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 385     if (BI->isUnconditional())
 386       return true;
 387     else {
 388       LatticeVal &BCValue = getValueState(BI->getCondition());
 389       if (BCValue.isOverdefined()) {
 390         // Overdefined condition variables mean the branch could go either way.
 391         return true;
 392       } else if (BCValue.isConstant()) {
 393         // Not branching on an evaluatable constant?
 394         if (!isa<ConstantBool>(BCValue.getConstant())) return true;
 395
 396         // Constant condition variables mean the branch can only go a single way
 397         return BI->getSuccessor(BCValue.getConstant() ==
 398                                        ConstantBool::False) == To;
 399       }
 400       return false;
 401     }
 402   } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
 403     // Invoke instructions successors are always executable.
 404     return true;
 405   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 406     LatticeVal &SCValue = getValueState(SI->getCondition());
 407     if (SCValue.isOverdefined()) {  // Overdefined condition?
 408       // All destinations are executable!
 409       return true;
 410     } else if (SCValue.isConstant()) {
 411       Constant *CPV = SCValue.getConstant();
 412       if (!isa<ConstantInt>(CPV))
 413         return true;  // not a foldable constant?
 414
 415       // Make sure to skip the "default value" which isn't a value
 416       for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i)
 417         if (SI->getSuccessorValue(i) == CPV) // Found the taken branch...
 418           return SI->getSuccessor(i) == To;
 419
 420       // Constant value not equal to any of the branches... must execute
 421       // default branch then...
 422       return SI->getDefaultDest() == To;
 423     }
 424     return false;
 425   } else {
 426     std::cerr << "Unknown terminator instruction: " << *TI;
 427     abort();
 428   }
 429 }
 430
 431 // visit Implementations - Something changed in this instruction... Either an
 432 // operand made a transition, or the instruction is newly executable.  Change
 433 // the value type of I to reflect these changes if appropriate.  This method
 434 // makes sure to do the following actions:
 435 //
 436 // 1. If a phi node merges two constants in, and has conflicting value coming
 437 //    from different branches, or if the PHI node merges in an overdefined
 438 //    value, then the PHI node becomes overdefined.
 439 // 2. If a phi node merges only constants in, and they all agree on value, the
 440 //    PHI node becomes a constant value equal to that.
 441 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
 442 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
 443 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
 444 // 6. If a conditional branch has a value that is constant, make the selected
 445 //    destination executable
 446 // 7. If a conditional branch has a value that is overdefined, make all
 447 //    successors executable.
 448 //
 449 void SCCPSolver::visitPHINode(PHINode &PN) {
 450   LatticeVal &PNIV = getValueState(&PN);
 451   if (PNIV.isOverdefined()) {
 452     // There may be instructions using this PHI node that are not overdefined
 453     // themselves.  If so, make sure that they know that the PHI node operand
 454     // changed.
 455     std::multimap<PHINode*, Instruction*>::iterator I, E;
 456     tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN);
 457     if (I != E) {
 458       std::vector<Instruction*> Users;
 459       Users.reserve(std::distance(I, E));
 460       for (; I != E; ++I) Users.push_back(I->second);
 461       while (!Users.empty()) {
 462         visit(Users.back());
 463         Users.pop_back();
 464       }
 465     }
 466     return;  // Quick exit
 467   }
 468
 469   // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
 470   // and slow us down a lot.  Just mark them overdefined.
 471   if (PN.getNumIncomingValues() > 64) {
 472     markOverdefined(PNIV, &PN);
 473     return;
 474   }
 475
 476   // Look at all of the executable operands of the PHI node.  If any of them
 477   // are overdefined, the PHI becomes overdefined as well.  If they are all
 478   // constant, and they agree with each other, the PHI becomes the identical
 479   // constant.  If they are constant and don't agree, the PHI is overdefined.
 480   // If there are no executable operands, the PHI remains undefined.
 481   //
 482   Constant *OperandVal = 0;
 483   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
 484     LatticeVal &IV = getValueState(PN.getIncomingValue(i));
 485     if (IV.isUndefined()) continue;  // Doesn't influence PHI node.
 486
 487     if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) {
 488       if (IV.isOverdefined()) {   // PHI node becomes overdefined!
 489         markOverdefined(PNIV, &PN);
 490         return;
 491       }
 492
 493       if (OperandVal == 0) {   // Grab the first value...
 494         OperandVal = IV.getConstant();
 495       } else {                // Another value is being merged in!
 496         // There is already a reachable operand.  If we conflict with it,
 497         // then the PHI node becomes overdefined.  If we agree with it, we
 498         // can continue on.
 499
 500         // Check to see if there are two different constants merging...
 501         if (IV.getConstant() != OperandVal) {
 502           // Yes there is.  This means the PHI node is not constant.
 503           // You must be overdefined poor PHI.
 504           //
 505           markOverdefined(PNIV, &PN);    // The PHI node now becomes overdefined
 506           return;    // I'm done analyzing you
 507         }
 508       }
 509     }
 510   }
 511
 512   // If we exited the loop, this means that the PHI node only has constant
 513   // arguments that agree with each other(and OperandVal is the constant) or
 514   // OperandVal is null because there are no defined incoming arguments.  If
 515   // this is the case, the PHI remains undefined.
 516   //
 517   if (OperandVal)
 518     markConstant(PNIV, &PN, OperandVal);      // Acquire operand value
 519 }
 520
 521 void SCCPSolver::visitReturnInst(ReturnInst &I) {
 522   if (I.getNumOperands() == 0) return;  // Ret void
 523
 524   // If we are tracking the return value of this function, merge it in.
 525   Function *F = I.getParent()->getParent();
 526   if (F->hasInternalLinkage() && !TrackedFunctionRetVals.empty()) {
 527     hash_map<Function*, LatticeVal>::iterator TFRVI =
 528       TrackedFunctionRetVals.find(F);
 529     if (TFRVI != TrackedFunctionRetVals.end() &&
 530         !TFRVI->second.isOverdefined()) {
 531       LatticeVal &IV = getValueState(I.getOperand(0));
 532       mergeInValue(TFRVI->second, F, IV);
 533     }
 534   }
 535 }
 536
 537
 538 void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) {
 539   std::vector<bool> SuccFeasible;
 540   getFeasibleSuccessors(TI, SuccFeasible);
 541
 542   BasicBlock *BB = TI.getParent();
 543
 544   // Mark all feasible successors executable...
 545   for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
 546     if (SuccFeasible[i])
 547       markEdgeExecutable(BB, TI.getSuccessor(i));
 548 }
 549
 550 void SCCPSolver::visitCastInst(CastInst &I) {
 551   Value *V = I.getOperand(0);
 552   LatticeVal &VState = getValueState(V);
 553   if (VState.isOverdefined())          // Inherit overdefinedness of operand
 554     markOverdefined(&I);
 555   else if (VState.isConstant())        // Propagate constant value
 556     markConstant(&I, ConstantExpr::getCast(VState.getConstant(), I.getType()));
 557 }
 558
 559 void SCCPSolver::visitSelectInst(SelectInst &I) {
 560   LatticeVal &CondValue = getValueState(I.getCondition());
 561   if (CondValue.isOverdefined())
 562     markOverdefined(&I);
 563   else if (CondValue.isConstant()) {
 564     if (CondValue.getConstant() == ConstantBool::True) {
 565       LatticeVal &Val = getValueState(I.getTrueValue());
 566       if (Val.isOverdefined())
 567         markOverdefined(&I);
 568       else if (Val.isConstant())
 569         markConstant(&I, Val.getConstant());
 570     } else if (CondValue.getConstant() == ConstantBool::False) {
 571       LatticeVal &Val = getValueState(I.getFalseValue());
 572       if (Val.isOverdefined())
 573         markOverdefined(&I);
 574       else if (Val.isConstant())
 575         markConstant(&I, Val.getConstant());
 576     } else
 577       markOverdefined(&I);
 578   }
 579 }
 580
 581 // Handle BinaryOperators and Shift Instructions...
 582 void SCCPSolver::visitBinaryOperator(Instruction &I) {
 583   LatticeVal &IV = ValueState[&I];
 584   if (IV.isOverdefined()) return;
 585
 586   LatticeVal &V1State = getValueState(I.getOperand(0));
 587   LatticeVal &V2State = getValueState(I.getOperand(1));
 588
 589   if (V1State.isOverdefined() || V2State.isOverdefined()) {
 590     // If both operands are PHI nodes, it is possible that this instruction has
 591     // a constant value, despite the fact that the PHI node doesn't.  Check for
 592     // this condition now.
 593     if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0)))
 594       if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1)))
 595         if (PN1->getParent() == PN2->getParent()) {
 596           // Since the two PHI nodes are in the same basic block, they must have
 597           // entries for the same predecessors.  Walk the predecessor list, and
 598           // if all of the incoming values are constants, and the result of
 599           // evaluating this expression with all incoming value pairs is the
 600           // same, then this expression is a constant even though the PHI node
 601           // is not a constant!
 602           LatticeVal Result;
 603           for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) {
 604             LatticeVal &In1 = getValueState(PN1->getIncomingValue(i));
 605             BasicBlock *InBlock = PN1->getIncomingBlock(i);
 606             LatticeVal &In2 =
 607               getValueState(PN2->getIncomingValueForBlock(InBlock));
 608
 609             if (In1.isOverdefined() || In2.isOverdefined()) {
 610               Result.markOverdefined();
 611               break;  // Cannot fold this operation over the PHI nodes!
 612             } else if (In1.isConstant() && In2.isConstant()) {
 613               Constant *V = ConstantExpr::get(I.getOpcode(), In1.getConstant(),
 614                                               In2.getConstant());
 615               if (Result.isUndefined())
 616                 Result.markConstant(V);
 617               else if (Result.isConstant() && Result.getConstant() != V) {
 618                 Result.markOverdefined();
 619                 break;
 620               }
 621             }
 622           }
 623
 624           // If we found a constant value here, then we know the instruction is
 625           // constant despite the fact that the PHI nodes are overdefined.
 626           if (Result.isConstant()) {
 627             markConstant(IV, &I, Result.getConstant());
 628             // Remember that this instruction is virtually using the PHI node
 629             // operands.
 630             UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I));
 631             UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I));
 632             return;
 633           } else if (Result.isUndefined()) {
 634             return;
 635           }
 636
 637           // Okay, this really is overdefined now.  Since we might have
 638           // speculatively thought that this was not overdefined before, and
 639           // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs,
 640           // make sure to clean out any entries that we put there, for
 641           // efficiency.
 642           std::multimap<PHINode*, Instruction*>::iterator It, E;
 643           tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1);
 644           while (It != E) {
 645             if (It->second == &I) {
 646               UsersOfOverdefinedPHIs.erase(It++);
 647             } else
 648               ++It;
 649           }
 650           tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2);
 651           while (It != E) {
 652             if (It->second == &I) {
 653               UsersOfOverdefinedPHIs.erase(It++);
 654             } else
 655               ++It;
 656           }
 657         }
 658
 659     markOverdefined(IV, &I);
 660   } else if (V1State.isConstant() && V2State.isConstant()) {
 661     markConstant(IV, &I, ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
 662                                            V2State.getConstant()));
 663   }
 664 }
 665
 666 // Handle getelementptr instructions... if all operands are constants then we
 667 // can turn this into a getelementptr ConstantExpr.
 668 //
 669 void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) {
 670   LatticeVal &IV = ValueState[&I];
 671   if (IV.isOverdefined()) return;
 672
 673   std::vector<Constant*> Operands;
 674   Operands.reserve(I.getNumOperands());
 675
 676   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
 677     LatticeVal &State = getValueState(I.getOperand(i));
 678     if (State.isUndefined())
 679       return;  // Operands are not resolved yet...
 680     else if (State.isOverdefined()) {
 681       markOverdefined(IV, &I);
 682       return;
 683     }
 684     assert(State.isConstant() && "Unknown state!");
 685     Operands.push_back(State.getConstant());
 686   }
 687
 688   Constant *Ptr = Operands[0];
 689   Operands.erase(Operands.begin());  // Erase the pointer from idx list...
 690
 691   markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, Operands));
 692 }
 693
 694 /// GetGEPGlobalInitializer - Given a constant and a getelementptr constantexpr,
 695 /// return the constant value being addressed by the constant expression, or
 696 /// null if something is funny.
 697 ///
 698 static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) {
 699   if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType()))
 700     return 0;  // Do not allow stepping over the value!
 701
 702   // Loop over all of the operands, tracking down which value we are
 703   // addressing...
 704   for (unsigned i = 2, e = CE->getNumOperands(); i != e; ++i)
 705     if (ConstantUInt *CU = dyn_cast<ConstantUInt>(CE->getOperand(i))) {
 706       ConstantStruct *CS = dyn_cast<ConstantStruct>(C);
 707       if (CS == 0) return 0;
 708       if (CU->getValue() >= CS->getNumOperands()) return 0;
 709       C = CS->getOperand(CU->getValue());
 710     } else if (ConstantSInt *CS = dyn_cast<ConstantSInt>(CE->getOperand(i))) {
 711       ConstantArray *CA = dyn_cast<ConstantArray>(C);
 712       if (CA == 0) return 0;
 713       if ((uint64_t)CS->getValue() >= CA->getNumOperands()) return 0;
 714       C = CA->getOperand(CS->getValue());
 715     } else
 716       return 0;
 717   return C;
 718 }
 719
 720 // Handle load instructions.  If the operand is a constant pointer to a constant
 721 // global, we can replace the load with the loaded constant value!
 722 void SCCPSolver::visitLoadInst(LoadInst &I) {
 723   LatticeVal &IV = ValueState[&I];
 724   if (IV.isOverdefined()) return;
 725
 726   LatticeVal &PtrVal = getValueState(I.getOperand(0));
 727   if (PtrVal.isUndefined()) return;   // The pointer is not resolved yet!
 728   if (PtrVal.isConstant() && !I.isVolatile()) {
 729     Value *Ptr = PtrVal.getConstant();
 730     if (isa<ConstantPointerNull>(Ptr)) {
 731       // load null -> null
 732       markConstant(IV, &I, Constant::getNullValue(I.getType()));
 733       return;
 734     }
 735
 736     // Transform load (constant global) into the value loaded.
 737     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr))
 738       if (GV->isConstant() && !GV->isExternal()) {
 739         markConstant(IV, &I, GV->getInitializer());
 740         return;
 741       }
 742
 743     // Transform load (constantexpr_GEP global, 0, ...) into the value loaded.
 744     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
 745       if (CE->getOpcode() == Instruction::GetElementPtr)
 746         if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
 747           if (GV->isConstant() && !GV->isExternal())
 748             if (Constant *V =
 749                 GetGEPGlobalInitializer(GV->getInitializer(), CE)) {
 750               markConstant(IV, &I, V);
 751               return;
 752             }
 753   }
 754
 755   // Otherwise we cannot say for certain what value this load will produce.
 756   // Bail out.
 757   markOverdefined(IV, &I);
 758 }
 759
 760 void SCCPSolver::visitCallSite(CallSite CS) {
 761   Function *F = CS.getCalledFunction();
 762
 763   // If we are tracking this function, we must make sure to bind arguments as
 764   // appropriate.
 765   hash_map<Function*, LatticeVal>::iterator TFRVI =TrackedFunctionRetVals.end();
 766   if (F && F->hasInternalLinkage())
 767     TFRVI = TrackedFunctionRetVals.find(F);
 768
 769   if (TFRVI != TrackedFunctionRetVals.end()) {
 770     // If this is the first call to the function hit, mark its entry block
 771     // executable.
 772     if (!BBExecutable.count(F->begin()))
 773       MarkBlockExecutable(F->begin());
 774
 775     CallSite::arg_iterator CAI = CS.arg_begin();
 776     for (Function::aiterator AI = F->abegin(), E = F->aend();
 777          AI != E; ++AI, ++CAI) {
 778       LatticeVal &IV = ValueState[AI];
 779       if (!IV.isOverdefined())
 780         mergeInValue(IV, AI, getValueState(*CAI));
 781     }
 782   }
 783   Instruction *I = CS.getInstruction();
 784   if (I->getType() == Type::VoidTy) return;
 785
 786   LatticeVal &IV = ValueState[I];
 787   if (IV.isOverdefined()) return;
 788
 789   // Propagate the return value of the function to the value of the instruction.
 790   if (TFRVI != TrackedFunctionRetVals.end()) {
 791     mergeInValue(IV, I, TFRVI->second);
 792     return;
 793   }
 794
 795   if (F == 0 || !F->isExternal() || !canConstantFoldCallTo(F)) {
 796     markOverdefined(IV, I);
 797     return;
 798   }
 799
 800   std::vector<Constant*> Operands;
 801   Operands.reserve(I->getNumOperands()-1);
 802
 803   for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 804        AI != E; ++AI) {
 805     LatticeVal &State = getValueState(*AI);
 806     if (State.isUndefined())
 807       return;  // Operands are not resolved yet...
 808     else if (State.isOverdefined()) {
 809       markOverdefined(IV, I);
 810       return;
 811     }
 812     assert(State.isConstant() && "Unknown state!");
 813     Operands.push_back(State.getConstant());
 814   }
 815
 816   if (Constant *C = ConstantFoldCall(F, Operands))
 817     markConstant(IV, I, C);
 818   else
 819     markOverdefined(IV, I);
 820 }
 821
 822
 823 void SCCPSolver::Solve() {
 824   // Process the work lists until they are empty!
 825   while (!BBWorkList.empty() || !InstWorkList.empty() ||
 826          !OverdefinedInstWorkList.empty()) {
 827     // Process the instruction work list...
 828     while (!OverdefinedInstWorkList.empty()) {
 829       Value *I = OverdefinedInstWorkList.back();
 830       OverdefinedInstWorkList.pop_back();
 831
 832       DEBUG(std::cerr << "\nPopped off OI-WL: " << *I);
 833
 834       // "I" got into the work list because it either made the transition from
 835       // bottom to constant
 836       //
 837       // Anything on this worklist that is overdefined need not be visited
 838       // since all of its users will have already been marked as overdefined
 839       // Update all of the users of this instruction's value...
 840       //
 841       for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
 842            UI != E; ++UI)
 843         OperandChangedState(*UI);
 844     }
 845     // Process the instruction work list...
 846     while (!InstWorkList.empty()) {
 847       Value *I = InstWorkList.back();
 848       InstWorkList.pop_back();
 849
 850       DEBUG(std::cerr << "\nPopped off I-WL: " << *I);
 851
 852       // "I" got into the work list because it either made the transition from
 853       // bottom to constant
 854       //
 855       // Anything on this worklist that is overdefined need not be visited
 856       // since all of its users will have already been marked as overdefined.
 857       // Update all of the users of this instruction's value...
 858       //
 859       if (!getValueState(I).isOverdefined())
 860         for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
 861              UI != E; ++UI)
 862           OperandChangedState(*UI);
 863     }
 864
 865     // Process the basic block work list...
 866     while (!BBWorkList.empty()) {
 867       BasicBlock *BB = BBWorkList.back();
 868       BBWorkList.pop_back();
 869
 870       DEBUG(std::cerr << "\nPopped off BBWL: " << *BB);
 871
 872       // Notify all instructions in this basic block that they are newly
 873       // executable.
 874       visit(BB);
 875     }
 876   }
 877 }
 878
 879 /// ResolveBranchesIn - While solving the dataflow for a function, we assume
 880 /// that branches on undef values cannot reach any of their successors.
 881 /// However, this is not a safe assumption.  After we solve dataflow, this
 882 /// method should be use to handle this.  If this returns true, the solver
 883 /// should be rerun.
 884 bool SCCPSolver::ResolveBranchesIn(Function &F) {
 885   bool BranchesResolved = false;
 886   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
 887     TerminatorInst *TI = BB->getTerminator();
 888     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 889       if (BI->isConditional()) {
 890         LatticeVal &BCValue = getValueState(BI->getCondition());
 891         if (BCValue.isUndefined()) {
 892           BI->setCondition(ConstantBool::True);
 893           BranchesResolved = true;
 894           visit(BI);
 895         }
 896       }
 897     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 898       LatticeVal &SCValue = getValueState(SI->getCondition());
 899       if (SCValue.isUndefined()) {
 900         SI->setCondition(Constant::getNullValue(SI->getCondition()->getType()));
 901         BranchesResolved = true;
 902         visit(SI);
 903       }
 904     }
 905   }
 906   return BranchesResolved;
 907 }
 908
 909
 910 namespace {
 911   Statistic<> NumInstRemoved("sccp", "Number of instructions removed");
 912   Statistic<> NumDeadBlocks ("sccp", "Number of basic blocks unreachable");
 913
 914   //===--------------------------------------------------------------------===//
 915   //
 916   /// SCCP Class - This class uses the SCCPSolver to implement a per-function
 917   /// Sparse Conditional COnstant Propagator.
 918   ///
 919   struct SCCP : public FunctionPass {
 920     // runOnFunction - Run the Sparse Conditional Constant Propagation
 921     // algorithm, and return true if the function was modified.
 922     //
 923     bool runOnFunction(Function &F);
 924
 925     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 926       AU.setPreservesCFG();
 927     }
 928   };
 929
 930   RegisterOpt<SCCP> X("sccp", "Sparse Conditional Constant Propagation");
 931 } // end anonymous namespace
 932
 933
 934 // createSCCPPass - This is the public interface to this file...
 935 FunctionPass *llvm::createSCCPPass() {
 936   return new SCCP();
 937 }
 938
 939
 940 // runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm,
 941 // and return true if the function was modified.
 942 //
 943 bool SCCP::runOnFunction(Function &F) {
 944   DEBUG(std::cerr << "SCCP on function '" << F.getName() << "'\n");
 945   SCCPSolver Solver;
 946
 947   // Mark the first block of the function as being executable.
 948   Solver.MarkBlockExecutable(F.begin());
 949
 950   // Mark all arguments to the function as being overdefined.
 951   hash_map<Value*, LatticeVal> &Values = Solver.getValueMapping();
 952   for (Function::aiterator AI = F.abegin(), E = F.aend(); AI != E; ++AI)
 953     Values[AI].markOverdefined();
 954
 955   // Solve for constants.
 956   bool ResolvedBranches = true;
 957   while (ResolvedBranches) {
 958     Solver.Solve();
 959     ResolvedBranches = Solver.ResolveBranchesIn(F);
 960   }
 961
 962   bool MadeChanges = false;
 963
 964   // If we decided that there are basic blocks that are dead in this function,
 965   // delete their contents now.  Note that we cannot actually delete the blocks,
 966   // as we cannot modify the CFG of the function.
 967   //
 968   std::set<BasicBlock*> &ExecutableBBs = Solver.getExecutableBlocks();
 969   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 970     if (!ExecutableBBs.count(BB)) {
 971       DEBUG(std::cerr << "  BasicBlock Dead:" << *BB);
 972       ++NumDeadBlocks;
 973
 974       // Delete the instructions backwards, as it has a reduced likelihood of
 975       // having to update as many def-use and use-def chains.
 976       std::vector<Instruction*> Insts;
 977       for (BasicBlock::iterator I = BB->begin(), E = BB->getTerminator();
 978            I != E; ++I)
 979         Insts.push_back(I);
 980       while (!Insts.empty()) {
 981         Instruction *I = Insts.back();
 982         Insts.pop_back();
 983         if (!I->use_empty())
 984           I->replaceAllUsesWith(UndefValue::get(I->getType()));
 985         BB->getInstList().erase(I);
 986         MadeChanges = true;
 987         ++NumInstRemoved;
 988       }
 989     } else {
 990       // Iterate over all of the instructions in a function, replacing them with
 991       // constants if we have found them to be of constant values.
 992       //
 993       for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
 994         Instruction *Inst = BI++;
 995         if (Inst->getType() != Type::VoidTy) {
 996           LatticeVal &IV = Values[Inst];
 997           if (IV.isConstant() || IV.isUndefined() &&
 998               !isa<TerminatorInst>(Inst)) {
 999             Constant *Const = IV.isConstant()
1000               ? IV.getConstant() : UndefValue::get(Inst->getType());
1001             DEBUG(std::cerr << "  Constant: " << *Const << " = " << *Inst);
1002
1003             // Replaces all of the uses of a variable with uses of the constant.
1004             Inst->replaceAllUsesWith(Const);
1005
1006             // Delete the instruction.
1007             BB->getInstList().erase(Inst);
1008
1009             // Hey, we just changed something!
1010             MadeChanges = true;
1011             ++NumInstRemoved;
1012           }
1013         }
1014       }
1015     }
1016
1017   return MadeChanges;
1018 }
1019
1020 namespace {
1021   Statistic<> IPNumInstRemoved("ipsccp", "Number of instructions removed");
1022   Statistic<> IPNumDeadBlocks ("ipsccp", "Number of basic blocks unreachable");
1023   Statistic<> IPNumArgsElimed ("ipsccp",
1024                                "Number of arguments constant propagated");
1025
1026   //===--------------------------------------------------------------------===//
1027   //
1028   /// IPSCCP Class - This class implements interprocedural Sparse Conditional
1029   /// Constant Propagation.
1030   ///
1031   struct IPSCCP : public ModulePass {
1032     bool runOnModule(Module &M);
1033   };
1034
1035   RegisterOpt<IPSCCP>
1036   Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation");
1037 } // end anonymous namespace
1038
1039 // createIPSCCPPass - This is the public interface to this file...
1040 ModulePass *llvm::createIPSCCPPass() {
1041   return new IPSCCP();
1042 }
1043
1044
1045 static bool AddressIsTaken(GlobalValue *GV) {
1046   for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end();
1047        UI != E; ++UI)
1048     if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
1049       if (SI->getOperand(0) == GV) return true;  // Storing addr of GV.
1050     } else if (isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) {
1051       // Make sure we are calling the function, not passing the address.
1052       CallSite CS = CallSite::get(cast<Instruction>(*UI));
1053       for (CallSite::arg_iterator AI = CS.arg_begin(),
1054              E = CS.arg_end(); AI != E; ++AI)
1055         if (*AI == GV)
1056           return true;
1057     } else if (!isa<LoadInst>(*UI)) {
1058       return true;
1059     }
1060   return false;
1061 }
1062
1063 bool IPSCCP::runOnModule(Module &M) {
1064   SCCPSolver Solver;
1065
1066   // Loop over all functions, marking arguments to those with their addresses
1067   // taken or that are external as overdefined.
1068   //
1069   hash_map<Value*, LatticeVal> &Values = Solver.getValueMapping();
1070   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
1071     if (!F->hasInternalLinkage() || AddressIsTaken(F)) {
1072       if (!F->isExternal())
1073         Solver.MarkBlockExecutable(F->begin());
1074       for (Function::aiterator AI = F->abegin(), E = F->aend(); AI != E; ++AI)
1075         Values[AI].markOverdefined();
1076     } else {
1077       Solver.AddTrackedFunction(F);
1078     }
1079
1080   // Solve for constants.
1081   bool ResolvedBranches = true;
1082   while (ResolvedBranches) {
1083     Solver.Solve();
1084
1085     ResolvedBranches = false;
1086     for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
1087       ResolvedBranches |= Solver.ResolveBranchesIn(*F);
1088   }
1089
1090   bool MadeChanges = false;
1091
1092   // Iterate over all of the instructions in the module, replacing them with
1093   // constants if we have found them to be of constant values.
1094   //
1095   std::set<BasicBlock*> &ExecutableBBs = Solver.getExecutableBlocks();
1096   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
1097     for (Function::aiterator AI = F->abegin(), E = F->aend(); AI != E; ++AI)
1098       if (!AI->use_empty()) {
1099         LatticeVal &IV = Values[AI];
1100         if (IV.isConstant() || IV.isUndefined()) {
1101           Constant *CST = IV.isConstant() ?
1102             IV.getConstant() : UndefValue::get(AI->getType());
1103           DEBUG(std::cerr << "***  Arg " << *AI << " = " << *CST <<"\n");
1104
1105           // Replaces all of the uses of a variable with uses of the
1106           // constant.
1107           AI->replaceAllUsesWith(CST);
1108           ++IPNumArgsElimed;
1109         }
1110       }
1111
1112     for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
1113       if (!ExecutableBBs.count(BB)) {
1114         DEBUG(std::cerr << "  BasicBlock Dead:" << *BB);
1115         ++IPNumDeadBlocks;
1116
1117         // Delete the instructions backwards, as it has a reduced likelihood of
1118         // having to update as many def-use and use-def chains.
1119         std::vector<Instruction*> Insts;
1120         for (BasicBlock::iterator I = BB->begin(), E = BB->getTerminator();
1121              I != E; ++I)
1122           Insts.push_back(I);
1123         while (!Insts.empty()) {
1124           Instruction *I = Insts.back();
1125           Insts.pop_back();
1126           if (!I->use_empty())
1127             I->replaceAllUsesWith(UndefValue::get(I->getType()));
1128           BB->getInstList().erase(I);
1129           MadeChanges = true;
1130           ++IPNumInstRemoved;
1131         }
1132       } else {
1133         for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
1134           Instruction *Inst = BI++;
1135           if (Inst->getType() != Type::VoidTy) {
1136             LatticeVal &IV = Values[Inst];
1137             if (IV.isConstant() || IV.isUndefined() &&
1138                 !isa<TerminatorInst>(Inst)) {
1139               Constant *Const = IV.isConstant()
1140                 ? IV.getConstant() : UndefValue::get(Inst->getType());
1141               DEBUG(std::cerr << "  Constant: " << *Const << " = " << *Inst);
1142
1143               // Replaces all of the uses of a variable with uses of the
1144               // constant.
1145               Inst->replaceAllUsesWith(Const);
1146
1147               // Delete the instruction.
1148               if (!isa<TerminatorInst>(Inst) && !isa<CallInst>(Inst))
1149                 BB->getInstList().erase(Inst);
1150
1151               // Hey, we just changed something!
1152               MadeChanges = true;
1153               ++IPNumInstRemoved;
1154             }
1155           }
1156         }
1157       }
1158   }
1159   return MadeChanges;
1160 }