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