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