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
 334   // Instructions that cannot be folded away...
 335   void visitStoreInst     (Instruction &I);
 336   void visitLoadInst      (LoadInst &I);
 337   void visitGetElementPtrInst(GetElementPtrInst &I);
 338   void visitCallInst      (CallInst &I) { visitCallSite(CallSite::get(&I)); }
 339   void visitInvokeInst    (InvokeInst &II) {
 340     visitCallSite(CallSite::get(&II));
 341     visitTerminatorInst(II);
 342   }
 343   void visitCallSite      (CallSite CS);
 344   void visitUnwindInst    (TerminatorInst &I) { /*returns void*/ }
 345   void visitUnreachableInst(TerminatorInst &I) { /*returns void*/ }
 346   void visitAllocationInst(Instruction &I) { markOverdefined(&I); }
 347   void visitVANextInst    (Instruction &I) { markOverdefined(&I); }
 348   void visitVAArgInst     (Instruction &I) { markOverdefined(&I); }
 349   void visitFreeInst      (Instruction &I) { /*returns void*/ }
 350
 351   void visitInstruction(Instruction &I) {
 352     // If a new instruction is added to LLVM that we don't handle...
 353     std::cerr << "SCCP: Don't know how to handle: " << I;
 354     markOverdefined(&I);   // Just in case
 355   }
 356 };
 357
 358 // getFeasibleSuccessors - Return a vector of booleans to indicate which
 359 // successors are reachable from a given terminator instruction.
 360 //
 361 void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI,
 362                                        std::vector<bool> &Succs) {
 363   Succs.resize(TI.getNumSuccessors());
 364   if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
 365     if (BI->isUnconditional()) {
 366       Succs[0] = true;
 367     } else {
 368       LatticeVal &BCValue = getValueState(BI->getCondition());
 369       if (BCValue.isOverdefined() ||
 370           (BCValue.isConstant() && !isa<ConstantBool>(BCValue.getConstant()))) {
 371         // Overdefined condition variables, and branches on unfoldable constant
 372         // conditions, mean the branch could go either way.
 373         Succs[0] = Succs[1] = true;
 374       } else if (BCValue.isConstant()) {
 375         // Constant condition variables mean the branch can only go a single way
 376         Succs[BCValue.getConstant() == ConstantBool::False] = true;
 377       }
 378     }
 379   } else if (InvokeInst *II = dyn_cast<InvokeInst>(&TI)) {
 380     // Invoke instructions successors are always executable.
 381     Succs[0] = Succs[1] = true;
 382   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) {
 383     LatticeVal &SCValue = getValueState(SI->getCondition());
 384     if (SCValue.isOverdefined() ||   // Overdefined condition?
 385         (SCValue.isConstant() && !isa<ConstantInt>(SCValue.getConstant()))) {
 386       // All destinations are executable!
 387       Succs.assign(TI.getNumSuccessors(), true);
 388     } else if (SCValue.isConstant()) {
 389       Constant *CPV = SCValue.getConstant();
 390       // Make sure to skip the "default value" which isn't a value
 391       for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) {
 392         if (SI->getSuccessorValue(i) == CPV) {// Found the right branch...
 393           Succs[i] = true;
 394           return;
 395         }
 396       }
 397
 398       // Constant value not equal to any of the branches... must execute
 399       // default branch then...
 400       Succs[0] = true;
 401     }
 402   } else {
 403     std::cerr << "SCCP: Don't know how to handle: " << TI;
 404     Succs.assign(TI.getNumSuccessors(), true);
 405   }
 406 }
 407
 408
 409 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
 410 // block to the 'To' basic block is currently feasible...
 411 //
 412 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) {
 413   assert(BBExecutable.count(To) && "Dest should always be alive!");
 414
 415   // Make sure the source basic block is executable!!
 416   if (!BBExecutable.count(From)) return false;
 417
 418   // Check to make sure this edge itself is actually feasible now...
 419   TerminatorInst *TI = From->getTerminator();
 420   if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 421     if (BI->isUnconditional())
 422       return true;
 423     else {
 424       LatticeVal &BCValue = getValueState(BI->getCondition());
 425       if (BCValue.isOverdefined()) {
 426         // Overdefined condition variables mean the branch could go either way.
 427         return true;
 428       } else if (BCValue.isConstant()) {
 429         // Not branching on an evaluatable constant?
 430         if (!isa<ConstantBool>(BCValue.getConstant())) return true;
 431
 432         // Constant condition variables mean the branch can only go a single way
 433         return BI->getSuccessor(BCValue.getConstant() ==
 434                                        ConstantBool::False) == To;
 435       }
 436       return false;
 437     }
 438   } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
 439     // Invoke instructions successors are always executable.
 440     return true;
 441   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 442     LatticeVal &SCValue = getValueState(SI->getCondition());
 443     if (SCValue.isOverdefined()) {  // Overdefined condition?
 444       // All destinations are executable!
 445       return true;
 446     } else if (SCValue.isConstant()) {
 447       Constant *CPV = SCValue.getConstant();
 448       if (!isa<ConstantInt>(CPV))
 449         return true;  // not a foldable constant?
 450
 451       // Make sure to skip the "default value" which isn't a value
 452       for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i)
 453         if (SI->getSuccessorValue(i) == CPV) // Found the taken branch...
 454           return SI->getSuccessor(i) == To;
 455
 456       // Constant value not equal to any of the branches... must execute
 457       // default branch then...
 458       return SI->getDefaultDest() == To;
 459     }
 460     return false;
 461   } else {
 462     std::cerr << "Unknown terminator instruction: " << *TI;
 463     abort();
 464   }
 465 }
 466
 467 // visit Implementations - Something changed in this instruction... Either an
 468 // operand made a transition, or the instruction is newly executable.  Change
 469 // the value type of I to reflect these changes if appropriate.  This method
 470 // makes sure to do the following actions:
 471 //
 472 // 1. If a phi node merges two constants in, and has conflicting value coming
 473 //    from different branches, or if the PHI node merges in an overdefined
 474 //    value, then the PHI node becomes overdefined.
 475 // 2. If a phi node merges only constants in, and they all agree on value, the
 476 //    PHI node becomes a constant value equal to that.
 477 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
 478 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
 479 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
 480 // 6. If a conditional branch has a value that is constant, make the selected
 481 //    destination executable
 482 // 7. If a conditional branch has a value that is overdefined, make all
 483 //    successors executable.
 484 //
 485 void SCCPSolver::visitPHINode(PHINode &PN) {
 486   LatticeVal &PNIV = getValueState(&PN);
 487   if (PNIV.isOverdefined()) {
 488     // There may be instructions using this PHI node that are not overdefined
 489     // themselves.  If so, make sure that they know that the PHI node operand
 490     // changed.
 491     std::multimap<PHINode*, Instruction*>::iterator I, E;
 492     tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN);
 493     if (I != E) {
 494       std::vector<Instruction*> Users;
 495       Users.reserve(std::distance(I, E));
 496       for (; I != E; ++I) Users.push_back(I->second);
 497       while (!Users.empty()) {
 498         visit(Users.back());
 499         Users.pop_back();
 500       }
 501     }
 502     return;  // Quick exit
 503   }
 504
 505   // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
 506   // and slow us down a lot.  Just mark them overdefined.
 507   if (PN.getNumIncomingValues() > 64) {
 508     markOverdefined(PNIV, &PN);
 509     return;
 510   }
 511
 512   // Look at all of the executable operands of the PHI node.  If any of them
 513   // are overdefined, the PHI becomes overdefined as well.  If they are all
 514   // constant, and they agree with each other, the PHI becomes the identical
 515   // constant.  If they are constant and don't agree, the PHI is overdefined.
 516   // If there are no executable operands, the PHI remains undefined.
 517   //
 518   Constant *OperandVal = 0;
 519   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
 520     LatticeVal &IV = getValueState(PN.getIncomingValue(i));
 521     if (IV.isUndefined()) continue;  // Doesn't influence PHI node.
 522
 523     if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) {
 524       if (IV.isOverdefined()) {   // PHI node becomes overdefined!
 525         markOverdefined(PNIV, &PN);
 526         return;
 527       }
 528
 529       if (OperandVal == 0) {   // Grab the first value...
 530         OperandVal = IV.getConstant();
 531       } else {                // Another value is being merged in!
 532         // There is already a reachable operand.  If we conflict with it,
 533         // then the PHI node becomes overdefined.  If we agree with it, we
 534         // can continue on.
 535
 536         // Check to see if there are two different constants merging...
 537         if (IV.getConstant() != OperandVal) {
 538           // Yes there is.  This means the PHI node is not constant.
 539           // You must be overdefined poor PHI.
 540           //
 541           markOverdefined(PNIV, &PN);    // The PHI node now becomes overdefined
 542           return;    // I'm done analyzing you
 543         }
 544       }
 545     }
 546   }
 547
 548   // If we exited the loop, this means that the PHI node only has constant
 549   // arguments that agree with each other(and OperandVal is the constant) or
 550   // OperandVal is null because there are no defined incoming arguments.  If
 551   // this is the case, the PHI remains undefined.
 552   //
 553   if (OperandVal)
 554     markConstant(PNIV, &PN, OperandVal);      // Acquire operand value
 555 }
 556
 557 void SCCPSolver::visitReturnInst(ReturnInst &I) {
 558   if (I.getNumOperands() == 0) return;  // Ret void
 559
 560   // If we are tracking the return value of this function, merge it in.
 561   Function *F = I.getParent()->getParent();
 562   if (F->hasInternalLinkage() && !TrackedFunctionRetVals.empty()) {
 563     hash_map<Function*, LatticeVal>::iterator TFRVI =
 564       TrackedFunctionRetVals.find(F);
 565     if (TFRVI != TrackedFunctionRetVals.end() &&
 566         !TFRVI->second.isOverdefined()) {
 567       LatticeVal &IV = getValueState(I.getOperand(0));
 568       mergeInValue(TFRVI->second, F, IV);
 569     }
 570   }
 571 }
 572
 573
 574 void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) {
 575   std::vector<bool> SuccFeasible;
 576   getFeasibleSuccessors(TI, SuccFeasible);
 577
 578   BasicBlock *BB = TI.getParent();
 579
 580   // Mark all feasible successors executable...
 581   for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
 582     if (SuccFeasible[i])
 583       markEdgeExecutable(BB, TI.getSuccessor(i));
 584 }
 585
 586 void SCCPSolver::visitCastInst(CastInst &I) {
 587   Value *V = I.getOperand(0);
 588   LatticeVal &VState = getValueState(V);
 589   if (VState.isOverdefined())          // Inherit overdefinedness of operand
 590     markOverdefined(&I);
 591   else if (VState.isConstant())        // Propagate constant value
 592     markConstant(&I, ConstantExpr::getCast(VState.getConstant(), I.getType()));
 593 }
 594
 595 void SCCPSolver::visitSelectInst(SelectInst &I) {
 596   LatticeVal &CondValue = getValueState(I.getCondition());
 597   if (CondValue.isUndefined())
 598     return;
 599   if (CondValue.isConstant()) {
 600     Value *InVal = 0;
 601     if (CondValue.getConstant() == ConstantBool::True) {
 602       mergeInValue(&I, getValueState(I.getTrueValue()));
 603       return;
 604     } else if (CondValue.getConstant() == ConstantBool::False) {
 605       mergeInValue(&I, getValueState(I.getFalseValue()));
 606       return;
 607     }
 608   }
 609
 610   // Otherwise, the condition is overdefined or a constant we can't evaluate.
 611   // See if we can produce something better than overdefined based on the T/F
 612   // value.
 613   LatticeVal &TVal = getValueState(I.getTrueValue());
 614   LatticeVal &FVal = getValueState(I.getFalseValue());
 615
 616   // select ?, C, C -> C.
 617   if (TVal.isConstant() && FVal.isConstant() &&
 618       TVal.getConstant() == FVal.getConstant()) {
 619     markConstant(&I, FVal.getConstant());
 620     return;
 621   }
 622
 623   if (TVal.isUndefined()) {  // select ?, undef, X -> X.
 624     mergeInValue(&I, FVal);
 625   } else if (FVal.isUndefined()) {  // select ?, X, undef -> X.
 626     mergeInValue(&I, TVal);
 627   } else {
 628     markOverdefined(&I);
 629   }
 630 }
 631
 632 // Handle BinaryOperators and Shift Instructions...
 633 void SCCPSolver::visitBinaryOperator(Instruction &I) {
 634   LatticeVal &IV = ValueState[&I];
 635   if (IV.isOverdefined()) return;
 636
 637   LatticeVal &V1State = getValueState(I.getOperand(0));
 638   LatticeVal &V2State = getValueState(I.getOperand(1));
 639
 640   if (V1State.isOverdefined() || V2State.isOverdefined()) {
 641     // If this is an AND or OR with 0 or -1, it doesn't matter that the other
 642     // operand is overdefined.
 643     if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Or) {
 644       LatticeVal *NonOverdefVal = 0;
 645       if (!V1State.isOverdefined()) {
 646         NonOverdefVal = &V1State;
 647       } else if (!V2State.isOverdefined()) {
 648         NonOverdefVal = &V2State;
 649       }
 650
 651       if (NonOverdefVal) {
 652         if (NonOverdefVal->isUndefined()) {
 653           // Could annihilate value.
 654           if (I.getOpcode() == Instruction::And)
 655             markConstant(IV, &I, Constant::getNullValue(I.getType()));
 656           else
 657             markConstant(IV, &I, ConstantInt::getAllOnesValue(I.getType()));
 658           return;
 659         } else {
 660           if (I.getOpcode() == Instruction::And) {
 661             if (NonOverdefVal->getConstant()->isNullValue()) {
 662               markConstant(IV, &I, NonOverdefVal->getConstant());
 663               return;      // X or 0 = -1
 664             }
 665           } else {
 666             if (ConstantIntegral *CI =
 667                      dyn_cast<ConstantIntegral>(NonOverdefVal->getConstant()))
 668               if (CI->isAllOnesValue()) {
 669                 markConstant(IV, &I, NonOverdefVal->getConstant());
 670                 return;    // X or -1 = -1
 671               }
 672           }
 673         }
 674       }
 675     }
 676
 677
 678     // If both operands are PHI nodes, it is possible that this instruction has
 679     // a constant value, despite the fact that the PHI node doesn't.  Check for
 680     // this condition now.
 681     if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0)))
 682       if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1)))
 683         if (PN1->getParent() == PN2->getParent()) {
 684           // Since the two PHI nodes are in the same basic block, they must have
 685           // entries for the same predecessors.  Walk the predecessor list, and
 686           // if all of the incoming values are constants, and the result of
 687           // evaluating this expression with all incoming value pairs is the
 688           // same, then this expression is a constant even though the PHI node
 689           // is not a constant!
 690           LatticeVal Result;
 691           for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) {
 692             LatticeVal &In1 = getValueState(PN1->getIncomingValue(i));
 693             BasicBlock *InBlock = PN1->getIncomingBlock(i);
 694             LatticeVal &In2 =
 695               getValueState(PN2->getIncomingValueForBlock(InBlock));
 696
 697             if (In1.isOverdefined() || In2.isOverdefined()) {
 698               Result.markOverdefined();
 699               break;  // Cannot fold this operation over the PHI nodes!
 700             } else if (In1.isConstant() && In2.isConstant()) {
 701               Constant *V = ConstantExpr::get(I.getOpcode(), In1.getConstant(),
 702                                               In2.getConstant());
 703               if (Result.isUndefined())
 704                 Result.markConstant(V);
 705               else if (Result.isConstant() && Result.getConstant() != V) {
 706                 Result.markOverdefined();
 707                 break;
 708               }
 709             }
 710           }
 711
 712           // If we found a constant value here, then we know the instruction is
 713           // constant despite the fact that the PHI nodes are overdefined.
 714           if (Result.isConstant()) {
 715             markConstant(IV, &I, Result.getConstant());
 716             // Remember that this instruction is virtually using the PHI node
 717             // operands.
 718             UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I));
 719             UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I));
 720             return;
 721           } else if (Result.isUndefined()) {
 722             return;
 723           }
 724
 725           // Okay, this really is overdefined now.  Since we might have
 726           // speculatively thought that this was not overdefined before, and
 727           // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs,
 728           // make sure to clean out any entries that we put there, for
 729           // efficiency.
 730           std::multimap<PHINode*, Instruction*>::iterator It, E;
 731           tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1);
 732           while (It != E) {
 733             if (It->second == &I) {
 734               UsersOfOverdefinedPHIs.erase(It++);
 735             } else
 736               ++It;
 737           }
 738           tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2);
 739           while (It != E) {
 740             if (It->second == &I) {
 741               UsersOfOverdefinedPHIs.erase(It++);
 742             } else
 743               ++It;
 744           }
 745         }
 746
 747     markOverdefined(IV, &I);
 748   } else if (V1State.isConstant() && V2State.isConstant()) {
 749     markConstant(IV, &I, ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
 750                                            V2State.getConstant()));
 751   }
 752 }
 753
 754 void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) {
 755   LatticeVal &ValState = getValueState(I.getOperand(0));
 756   LatticeVal &IdxState = getValueState(I.getOperand(1));
 757
 758   if (ValState.isOverdefined() || IdxState.isOverdefined())
 759     markOverdefined(&I);
 760   else if(ValState.isConstant() && IdxState.isConstant())
 761     markConstant(&I, ConstantExpr::getExtractElement(ValState.getConstant(),
 762                                                      IdxState.getConstant()));
 763 }
 764
 765 void SCCPSolver::visitInsertElementInst(InsertElementInst &I) {
 766   LatticeVal &ValState = getValueState(I.getOperand(0));
 767   LatticeVal &EltState = getValueState(I.getOperand(1));
 768   LatticeVal &IdxState = getValueState(I.getOperand(2));
 769
 770   if (ValState.isOverdefined() || EltState.isOverdefined() ||
 771       IdxState.isOverdefined())
 772     markOverdefined(&I);
 773   else if(ValState.isConstant() && EltState.isConstant() &&
 774           IdxState.isConstant())
 775     markConstant(&I, ConstantExpr::getInsertElement(ValState.getConstant(),
 776                                                     EltState.getConstant(),
 777                                                     IdxState.getConstant()));
 778   else if (ValState.isUndefined() && EltState.isConstant() &&
 779            IdxState.isConstant())
 780     markConstant(&I, ConstantExpr::getInsertElement(UndefValue::get(I.getType()),
 781                                                     EltState.getConstant(),
 782                                                     IdxState.getConstant()));
 783 }
 784
 785 // Handle getelementptr instructions... if all operands are constants then we
 786 // can turn this into a getelementptr ConstantExpr.
 787 //
 788 void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) {
 789   LatticeVal &IV = ValueState[&I];
 790   if (IV.isOverdefined()) return;
 791
 792   std::vector<Constant*> Operands;
 793   Operands.reserve(I.getNumOperands());
 794
 795   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
 796     LatticeVal &State = getValueState(I.getOperand(i));
 797     if (State.isUndefined())
 798       return;  // Operands are not resolved yet...
 799     else if (State.isOverdefined()) {
 800       markOverdefined(IV, &I);
 801       return;
 802     }
 803     assert(State.isConstant() && "Unknown state!");
 804     Operands.push_back(State.getConstant());
 805   }
 806
 807   Constant *Ptr = Operands[0];
 808   Operands.erase(Operands.begin());  // Erase the pointer from idx list...
 809
 810   markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, Operands));
 811 }
 812
 813 void SCCPSolver::visitStoreInst(Instruction &SI) {
 814   if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1)))
 815     return;
 816   GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1));
 817   hash_map<GlobalVariable*, LatticeVal>::iterator I = TrackedGlobals.find(GV);
 818   if (I == TrackedGlobals.end() || I->second.isOverdefined()) return;
 819
 820   // Get the value we are storing into the global.
 821   LatticeVal &PtrVal = getValueState(SI.getOperand(0));
 822
 823   mergeInValue(I->second, GV, PtrVal);
 824   if (I->second.isOverdefined())
 825     TrackedGlobals.erase(I);      // No need to keep tracking this!
 826 }
 827
 828
 829 // Handle load instructions.  If the operand is a constant pointer to a constant
 830 // global, we can replace the load with the loaded constant value!
 831 void SCCPSolver::visitLoadInst(LoadInst &I) {
 832   LatticeVal &IV = ValueState[&I];
 833   if (IV.isOverdefined()) return;
 834
 835   LatticeVal &PtrVal = getValueState(I.getOperand(0));
 836   if (PtrVal.isUndefined()) return;   // The pointer is not resolved yet!
 837   if (PtrVal.isConstant() && !I.isVolatile()) {
 838     Value *Ptr = PtrVal.getConstant();
 839     if (isa<ConstantPointerNull>(Ptr)) {
 840       // load null -> null
 841       markConstant(IV, &I, Constant::getNullValue(I.getType()));
 842       return;
 843     }
 844
 845     // Transform load (constant global) into the value loaded.
 846     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
 847       if (GV->isConstant()) {
 848         if (!GV->isExternal()) {
 849           markConstant(IV, &I, GV->getInitializer());
 850           return;
 851         }
 852       } else if (!TrackedGlobals.empty()) {
 853         // If we are tracking this global, merge in the known value for it.
 854         hash_map<GlobalVariable*, LatticeVal>::iterator It =
 855           TrackedGlobals.find(GV);
 856         if (It != TrackedGlobals.end()) {
 857           mergeInValue(IV, &I, It->second);
 858           return;
 859         }
 860       }
 861     }
 862
 863     // Transform load (constantexpr_GEP global, 0, ...) into the value loaded.
 864     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
 865       if (CE->getOpcode() == Instruction::GetElementPtr)
 866     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
 867       if (GV->isConstant() && !GV->isExternal())
 868         if (Constant *V =
 869              ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE)) {
 870           markConstant(IV, &I, V);
 871           return;
 872         }
 873   }
 874
 875   // Otherwise we cannot say for certain what value this load will produce.
 876   // Bail out.
 877   markOverdefined(IV, &I);
 878 }
 879
 880 void SCCPSolver::visitCallSite(CallSite CS) {
 881   Function *F = CS.getCalledFunction();
 882
 883   // If we are tracking this function, we must make sure to bind arguments as
 884   // appropriate.
 885   hash_map<Function*, LatticeVal>::iterator TFRVI =TrackedFunctionRetVals.end();
 886   if (F && F->hasInternalLinkage())
 887     TFRVI = TrackedFunctionRetVals.find(F);
 888
 889   if (TFRVI != TrackedFunctionRetVals.end()) {
 890     // If this is the first call to the function hit, mark its entry block
 891     // executable.
 892     if (!BBExecutable.count(F->begin()))
 893       MarkBlockExecutable(F->begin());
 894
 895     CallSite::arg_iterator CAI = CS.arg_begin();
 896     for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
 897          AI != E; ++AI, ++CAI) {
 898       LatticeVal &IV = ValueState[AI];
 899       if (!IV.isOverdefined())
 900         mergeInValue(IV, AI, getValueState(*CAI));
 901     }
 902   }
 903   Instruction *I = CS.getInstruction();
 904   if (I->getType() == Type::VoidTy) return;
 905
 906   LatticeVal &IV = ValueState[I];
 907   if (IV.isOverdefined()) return;
 908
 909   // Propagate the return value of the function to the value of the instruction.
 910   if (TFRVI != TrackedFunctionRetVals.end()) {
 911     mergeInValue(IV, I, TFRVI->second);
 912     return;
 913   }
 914
 915   if (F == 0 || !F->isExternal() || !canConstantFoldCallTo(F)) {
 916     markOverdefined(IV, I);
 917     return;
 918   }
 919
 920   std::vector<Constant*> Operands;
 921   Operands.reserve(I->getNumOperands()-1);
 922
 923   for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 924        AI != E; ++AI) {
 925     LatticeVal &State = getValueState(*AI);
 926     if (State.isUndefined())
 927       return;  // Operands are not resolved yet...
 928     else if (State.isOverdefined()) {
 929       markOverdefined(IV, I);
 930       return;
 931     }
 932     assert(State.isConstant() && "Unknown state!");
 933     Operands.push_back(State.getConstant());
 934   }
 935
 936   if (Constant *C = ConstantFoldCall(F, Operands))
 937     markConstant(IV, I, C);
 938   else
 939     markOverdefined(IV, I);
 940 }
 941
 942
 943 void SCCPSolver::Solve() {
 944   // Process the work lists until they are empty!
 945   while (!BBWorkList.empty() || !InstWorkList.empty() ||
 946          !OverdefinedInstWorkList.empty()) {
 947     // Process the instruction work list...
 948     while (!OverdefinedInstWorkList.empty()) {
 949       Value *I = OverdefinedInstWorkList.back();
 950       OverdefinedInstWorkList.pop_back();
 951
 952       DEBUG(std::cerr << "\nPopped off OI-WL: " << *I);
 953
 954       // "I" got into the work list because it either made the transition from
 955       // bottom to constant
 956       //
 957       // Anything on this worklist that is overdefined need not be visited
 958       // since all of its users will have already been marked as overdefined
 959       // Update all of the users of this instruction's value...
 960       //
 961       for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
 962            UI != E; ++UI)
 963         OperandChangedState(*UI);
 964     }
 965     // Process the instruction work list...
 966     while (!InstWorkList.empty()) {
 967       Value *I = InstWorkList.back();
 968       InstWorkList.pop_back();
 969
 970       DEBUG(std::cerr << "\nPopped off I-WL: " << *I);
 971
 972       // "I" got into the work list because it either made the transition from
 973       // bottom to constant
 974       //
 975       // Anything on this worklist that is overdefined need not be visited
 976       // since all of its users will have already been marked as overdefined.
 977       // Update all of the users of this instruction's value...
 978       //
 979       if (!getValueState(I).isOverdefined())
 980         for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
 981              UI != E; ++UI)
 982           OperandChangedState(*UI);
 983     }
 984
 985     // Process the basic block work list...
 986     while (!BBWorkList.empty()) {
 987       BasicBlock *BB = BBWorkList.back();
 988       BBWorkList.pop_back();
 989
 990       DEBUG(std::cerr << "\nPopped off BBWL: " << *BB);
 991
 992       // Notify all instructions in this basic block that they are newly
 993       // executable.
 994       visit(BB);
 995     }
 996   }
 997 }
 998
 999 /// ResolveBranchesIn - While solving the dataflow for a function, we assume
1000 /// that branches on undef values cannot reach any of their successors.
1001 /// However, this is not a safe assumption.  After we solve dataflow, this
1002 /// method should be use to handle this.  If this returns true, the solver
1003 /// should be rerun.
1004 bool SCCPSolver::ResolveBranchesIn(Function &F) {
1005   bool BranchesResolved = false;
1006   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
1007     if (BBExecutable.count(BB)) {
1008       TerminatorInst *TI = BB->getTerminator();
1009       if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1010         if (BI->isConditional()) {
1011           LatticeVal &BCValue = getValueState(BI->getCondition());
1012           if (BCValue.isUndefined()) {
1013             BI->setCondition(ConstantBool::True);
1014             BranchesResolved = true;
1015             visit(BI);
1016           }
1017         }
1018       } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
1019         LatticeVal &SCValue = getValueState(SI->getCondition());
1020         if (SCValue.isUndefined()) {
1021           const Type *CondTy = SI->getCondition()->getType();
1022           SI->setCondition(Constant::getNullValue(CondTy));
1023           BranchesResolved = true;
1024           visit(SI);
1025         }
1026       }
1027     }
1028
1029   return BranchesResolved;
1030 }
1031
1032
1033 namespace {
1034   Statistic<> NumInstRemoved("sccp", "Number of instructions removed");
1035   Statistic<> NumDeadBlocks ("sccp", "Number of basic blocks unreachable");
1036
1037   //===--------------------------------------------------------------------===//
1038   //
1039   /// SCCP Class - This class uses the SCCPSolver to implement a per-function
1040   /// Sparse Conditional COnstant Propagator.
1041   ///
1042   struct SCCP : public FunctionPass {
1043     // runOnFunction - Run the Sparse Conditional Constant Propagation
1044     // algorithm, and return true if the function was modified.
1045     //
1046     bool runOnFunction(Function &F);
1047
1048     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1049       AU.setPreservesCFG();
1050     }
1051   };
1052
1053   RegisterOpt<SCCP> X("sccp", "Sparse Conditional Constant Propagation");
1054 } // end anonymous namespace
1055
1056
1057 // createSCCPPass - This is the public interface to this file...
1058 FunctionPass *llvm::createSCCPPass() {
1059   return new SCCP();
1060 }
1061
1062
1063 // runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm,
1064 // and return true if the function was modified.
1065 //
1066 bool SCCP::runOnFunction(Function &F) {
1067   DEBUG(std::cerr << "SCCP on function '" << F.getName() << "'\n");
1068   SCCPSolver Solver;
1069
1070   // Mark the first block of the function as being executable.
1071   Solver.MarkBlockExecutable(F.begin());
1072
1073   // Mark all arguments to the function as being overdefined.
1074   hash_map<Value*, LatticeVal> &Values = Solver.getValueMapping();
1075   for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E; ++AI)
1076     Values[AI].markOverdefined();
1077
1078   // Solve for constants.
1079   bool ResolvedBranches = true;
1080   while (ResolvedBranches) {
1081     Solver.Solve();
1082     DEBUG(std::cerr << "RESOLVING UNDEF BRANCHES\n");
1083     ResolvedBranches = Solver.ResolveBranchesIn(F);
1084   }
1085
1086   bool MadeChanges = false;
1087
1088   // If we decided that there are basic blocks that are dead in this function,
1089   // delete their contents now.  Note that we cannot actually delete the blocks,
1090   // as we cannot modify the CFG of the function.
1091   //
1092   std::set<BasicBlock*> &ExecutableBBs = Solver.getExecutableBlocks();
1093   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
1094     if (!ExecutableBBs.count(BB)) {
1095       DEBUG(std::cerr << "  BasicBlock Dead:" << *BB);
1096       ++NumDeadBlocks;
1097
1098       // Delete the instructions backwards, as it has a reduced likelihood of
1099       // having to update as many def-use and use-def chains.
1100       std::vector<Instruction*> Insts;
1101       for (BasicBlock::iterator I = BB->begin(), E = BB->getTerminator();
1102            I != E; ++I)
1103         Insts.push_back(I);
1104       while (!Insts.empty()) {
1105         Instruction *I = Insts.back();
1106         Insts.pop_back();
1107         if (!I->use_empty())
1108           I->replaceAllUsesWith(UndefValue::get(I->getType()));
1109         BB->getInstList().erase(I);
1110         MadeChanges = true;
1111         ++NumInstRemoved;
1112       }
1113     } else {
1114       // Iterate over all of the instructions in a function, replacing them with
1115       // constants if we have found them to be of constant values.
1116       //
1117       for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
1118         Instruction *Inst = BI++;
1119         if (Inst->getType() != Type::VoidTy) {
1120           LatticeVal &IV = Values[Inst];
1121           if (IV.isConstant() || IV.isUndefined() &&
1122               !isa<TerminatorInst>(Inst)) {
1123             Constant *Const = IV.isConstant()
1124               ? IV.getConstant() : UndefValue::get(Inst->getType());
1125             DEBUG(std::cerr << "  Constant: " << *Const << " = " << *Inst);
1126
1127             // Replaces all of the uses of a variable with uses of the constant.
1128             Inst->replaceAllUsesWith(Const);
1129
1130             // Delete the instruction.
1131             BB->getInstList().erase(Inst);
1132
1133             // Hey, we just changed something!
1134             MadeChanges = true;
1135             ++NumInstRemoved;
1136           }
1137         }
1138       }
1139     }
1140
1141   return MadeChanges;
1142 }
1143
1144 namespace {
1145   Statistic<> IPNumInstRemoved("ipsccp", "Number of instructions removed");
1146   Statistic<> IPNumDeadBlocks ("ipsccp", "Number of basic blocks unreachable");
1147   Statistic<> IPNumArgsElimed ("ipsccp",
1148                                "Number of arguments constant propagated");
1149   Statistic<> IPNumGlobalConst("ipsccp",
1150                                "Number of globals found to be constant");
1151
1152   //===--------------------------------------------------------------------===//
1153   //
1154   /// IPSCCP Class - This class implements interprocedural Sparse Conditional
1155   /// Constant Propagation.
1156   ///
1157   struct IPSCCP : public ModulePass {
1158     bool runOnModule(Module &M);
1159   };
1160
1161   RegisterOpt<IPSCCP>
1162   Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation");
1163 } // end anonymous namespace
1164
1165 // createIPSCCPPass - This is the public interface to this file...
1166 ModulePass *llvm::createIPSCCPPass() {
1167   return new IPSCCP();
1168 }
1169
1170
1171 static bool AddressIsTaken(GlobalValue *GV) {
1172   // Delete any dead constantexpr klingons.
1173   GV->removeDeadConstantUsers();
1174
1175   for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end();
1176        UI != E; ++UI)
1177     if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
1178       if (SI->getOperand(0) == GV || SI->isVolatile())
1179         return true;  // Storing addr of GV.
1180     } else if (isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) {
1181       // Make sure we are calling the function, not passing the address.
1182       CallSite CS = CallSite::get(cast<Instruction>(*UI));
1183       for (CallSite::arg_iterator AI = CS.arg_begin(),
1184              E = CS.arg_end(); AI != E; ++AI)
1185         if (*AI == GV)
1186           return true;
1187     } else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
1188       if (LI->isVolatile())
1189         return true;
1190     } else {
1191       return true;
1192     }
1193   return false;
1194 }
1195
1196 bool IPSCCP::runOnModule(Module &M) {
1197   SCCPSolver Solver;
1198
1199   // Loop over all functions, marking arguments to those with their addresses
1200   // taken or that are external as overdefined.
1201   //
1202   hash_map<Value*, LatticeVal> &Values = Solver.getValueMapping();
1203   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
1204     if (!F->hasInternalLinkage() || AddressIsTaken(F)) {
1205       if (!F->isExternal())
1206         Solver.MarkBlockExecutable(F->begin());
1207       for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
1208            AI != E; ++AI)
1209         Values[AI].markOverdefined();
1210     } else {
1211       Solver.AddTrackedFunction(F);
1212     }
1213
1214   // Loop over global variables.  We inform the solver about any internal global
1215   // variables that do not have their 'addresses taken'.  If they don't have
1216   // their addresses taken, we can propagate constants through them.
1217   for (Module::global_iterator G = M.global_begin(), E = M.global_end();
1218        G != E; ++G)
1219     if (!G->isConstant() && G->hasInternalLinkage() && !AddressIsTaken(G))
1220       Solver.TrackValueOfGlobalVariable(G);
1221
1222   // Solve for constants.
1223   bool ResolvedBranches = true;
1224   while (ResolvedBranches) {
1225     Solver.Solve();
1226
1227     DEBUG(std::cerr << "RESOLVING UNDEF BRANCHES\n");
1228     ResolvedBranches = false;
1229     for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
1230       ResolvedBranches |= Solver.ResolveBranchesIn(*F);
1231   }
1232
1233   bool MadeChanges = false;
1234
1235   // Iterate over all of the instructions in the module, replacing them with
1236   // constants if we have found them to be of constant values.
1237   //
1238   std::set<BasicBlock*> &ExecutableBBs = Solver.getExecutableBlocks();
1239   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
1240     for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
1241          AI != E; ++AI)
1242       if (!AI->use_empty()) {
1243         LatticeVal &IV = Values[AI];
1244         if (IV.isConstant() || IV.isUndefined()) {
1245           Constant *CST = IV.isConstant() ?
1246             IV.getConstant() : UndefValue::get(AI->getType());
1247           DEBUG(std::cerr << "***  Arg " << *AI << " = " << *CST <<"\n");
1248
1249           // Replaces all of the uses of a variable with uses of the
1250           // constant.
1251           AI->replaceAllUsesWith(CST);
1252           ++IPNumArgsElimed;
1253         }
1254       }
1255
1256     std::vector<BasicBlock*> BlocksToErase;
1257     for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
1258       if (!ExecutableBBs.count(BB)) {
1259         DEBUG(std::cerr << "  BasicBlock Dead:" << *BB);
1260         ++IPNumDeadBlocks;
1261
1262         // Delete the instructions backwards, as it has a reduced likelihood of
1263         // having to update as many def-use and use-def chains.
1264         std::vector<Instruction*> Insts;
1265         TerminatorInst *TI = BB->getTerminator();
1266         for (BasicBlock::iterator I = BB->begin(), E = TI; I != E; ++I)
1267           Insts.push_back(I);
1268
1269         while (!Insts.empty()) {
1270           Instruction *I = Insts.back();
1271           Insts.pop_back();
1272           if (!I->use_empty())
1273             I->replaceAllUsesWith(UndefValue::get(I->getType()));
1274           BB->getInstList().erase(I);
1275           MadeChanges = true;
1276           ++IPNumInstRemoved;
1277         }
1278
1279         for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
1280           BasicBlock *Succ = TI->getSuccessor(i);
1281           if (Succ->begin() != Succ->end() && isa<PHINode>(Succ->begin()))
1282             TI->getSuccessor(i)->removePredecessor(BB);
1283         }
1284         if (!TI->use_empty())
1285           TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
1286         BB->getInstList().erase(TI);
1287
1288         if (&*BB != &F->front())
1289           BlocksToErase.push_back(BB);
1290         else
1291           new UnreachableInst(BB);
1292
1293       } else {
1294         for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
1295           Instruction *Inst = BI++;
1296           if (Inst->getType() != Type::VoidTy) {
1297             LatticeVal &IV = Values[Inst];
1298             if (IV.isConstant() || IV.isUndefined() &&
1299                 !isa<TerminatorInst>(Inst)) {
1300               Constant *Const = IV.isConstant()
1301                 ? IV.getConstant() : UndefValue::get(Inst->getType());
1302               DEBUG(std::cerr << "  Constant: " << *Const << " = " << *Inst);
1303
1304               // Replaces all of the uses of a variable with uses of the
1305               // constant.
1306               Inst->replaceAllUsesWith(Const);
1307
1308               // Delete the instruction.
1309               if (!isa<TerminatorInst>(Inst) && !isa<CallInst>(Inst))
1310                 BB->getInstList().erase(Inst);
1311
1312               // Hey, we just changed something!
1313               MadeChanges = true;
1314               ++IPNumInstRemoved;
1315             }
1316           }
1317         }
1318       }
1319
1320     // Now that all instructions in the function are constant folded, erase dead
1321     // blocks, because we can now use ConstantFoldTerminator to get rid of
1322     // in-edges.
1323     for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) {
1324       // If there are any PHI nodes in this successor, drop entries for BB now.
1325       BasicBlock *DeadBB = BlocksToErase[i];
1326       while (!DeadBB->use_empty()) {
1327         Instruction *I = cast<Instruction>(DeadBB->use_back());
1328         bool Folded = ConstantFoldTerminator(I->getParent());
1329         assert(Folded && "Didn't fold away reference to block!");
1330       }
1331
1332       // Finally, delete the basic block.
1333       F->getBasicBlockList().erase(DeadBB);
1334     }
1335   }
1336
1337   // If we inferred constant or undef return values for a function, we replaced
1338   // all call uses with the inferred value.  This means we don't need to bother
1339   // actually returning anything from the function.  Replace all return
1340   // instructions with return undef.
1341   const hash_map<Function*, LatticeVal> &RV =Solver.getTrackedFunctionRetVals();
1342   for (hash_map<Function*, LatticeVal>::const_iterator I = RV.begin(),
1343          E = RV.end(); I != E; ++I)
1344     if (!I->second.isOverdefined() &&
1345         I->first->getReturnType() != Type::VoidTy) {
1346       Function *F = I->first;
1347       for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
1348         if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
1349           if (!isa<UndefValue>(RI->getOperand(0)))
1350             RI->setOperand(0, UndefValue::get(F->getReturnType()));
1351     }
1352
1353   // If we infered constant or undef values for globals variables, we can delete
1354   // the global and any stores that remain to it.
1355   const hash_map<GlobalVariable*, LatticeVal> &TG = Solver.getTrackedGlobals();
1356   for (hash_map<GlobalVariable*, LatticeVal>::const_iterator I = TG.begin(),
1357          E = TG.end(); I != E; ++I) {
1358     GlobalVariable *GV = I->first;
1359     assert(!I->second.isOverdefined() &&
1360            "Overdefined values should have been taken out of the map!");
1361     DEBUG(std::cerr << "Found that GV '" << GV->getName()<< "' is constant!\n");
1362     while (!GV->use_empty()) {
1363       StoreInst *SI = cast<StoreInst>(GV->use_back());
1364       SI->eraseFromParent();
1365     }
1366     M.getGlobalList().erase(GV);
1367     ++IPNumGlobalConst;
1368   }
1369
1370   return MadeChanges;
1371 }