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