LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

SCCP.cpp

Go to the documentation of this file.
00001 //===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements sparse conditional constant propagation and merging:
00011 //
00012 // Specifically, this:
00013 //   * Assumes values are constant unless proven otherwise
00014 //   * Assumes BasicBlocks are dead unless proven otherwise
00015 //   * Proves values to be constant, and replaces them with constants
00016 //   * Proves conditional branches to be unconditional
00017 //
00018 // Notice that:
00019 //   * This pass has a habit of making definitions be dead.  It is a good idea
00020 //     to to run a DCE pass sometime after running this pass.
00021 //
00022 //===----------------------------------------------------------------------===//
00023 
00024 #define DEBUG_TYPE "sccp"
00025 #include "llvm/Transforms/Scalar.h"
00026 #include "llvm/Constants.h"
00027 #include "llvm/Function.h"
00028 #include "llvm/GlobalVariable.h"
00029 #include "llvm/Instructions.h"
00030 #include "llvm/Pass.h"
00031 #include "llvm/Type.h"
00032 #include "llvm/Support/InstVisitor.h"
00033 #include "llvm/Transforms/Utils/Local.h"
00034 #include "llvm/Support/Debug.h"
00035 #include "llvm/ADT/hash_map"
00036 #include "llvm/ADT/Statistic.h"
00037 #include "llvm/ADT/STLExtras.h"
00038 #include <algorithm>
00039 #include <set>
00040 using namespace llvm;
00041 
00042 // LatticeVal class - This class represents the different lattice values that an
00043 // instruction may occupy.  It is a simple class with value semantics.
00044 //
00045 namespace {
00046   Statistic<> NumInstRemoved("sccp", "Number of instructions removed");
00047   Statistic<> NumDeadBlocks ("sccp", "Number of basic blocks unreachable");
00048 
00049 class LatticeVal {
00050   enum { 
00051     undefined,           // This instruction has no known value
00052     constant,            // This instruction has a constant value
00053     overdefined          // This instruction has an unknown value
00054   } LatticeValue;        // The current lattice position
00055   Constant *ConstantVal; // If Constant value, the current value
00056 public:
00057   inline LatticeVal() : LatticeValue(undefined), ConstantVal(0) {}
00058 
00059   // markOverdefined - Return true if this is a new status to be in...
00060   inline bool markOverdefined() {
00061     if (LatticeValue != overdefined) {
00062       LatticeValue = overdefined;
00063       return true;
00064     }
00065     return false;
00066   }
00067 
00068   // markConstant - Return true if this is a new status for us...
00069   inline bool markConstant(Constant *V) {
00070     if (LatticeValue != constant) {
00071       LatticeValue = constant;
00072       ConstantVal = V;
00073       return true;
00074     } else {
00075       assert(ConstantVal == V && "Marking constant with different value");
00076     }
00077     return false;
00078   }
00079 
00080   inline bool isUndefined()   const { return LatticeValue == undefined; }
00081   inline bool isConstant()    const { return LatticeValue == constant; }
00082   inline bool isOverdefined() const { return LatticeValue == overdefined; }
00083 
00084   inline Constant *getConstant() const {
00085     assert(isConstant() && "Cannot get the constant of a non-constant!");
00086     return ConstantVal;
00087   }
00088 };
00089 
00090 } // end anonymous namespace
00091 
00092 
00093 //===----------------------------------------------------------------------===//
00094 //
00095 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional
00096 /// Constant Propagation.
00097 ///
00098 class SCCPSolver : public InstVisitor<SCCPSolver> {
00099   std::set<BasicBlock*>     BBExecutable;// The basic blocks that are executable
00100   hash_map<Value*, LatticeVal> ValueState;  // The state each value is in...
00101 
00102   // The reason for two worklists is that overdefined is the lowest state
00103   // on the lattice, and moving things to overdefined as fast as possible
00104   // makes SCCP converge much faster.
00105   // By having a separate worklist, we accomplish this because everything
00106   // possibly overdefined will become overdefined at the soonest possible
00107   // point.
00108   std::vector<Instruction*> OverdefinedInstWorkList;// The overdefined 
00109                                                     // instruction work list
00110   std::vector<Instruction*> InstWorkList;// The instruction work list
00111 
00112 
00113   std::vector<BasicBlock*>  BBWorkList;  // The BasicBlock work list
00114 
00115   /// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not
00116   /// overdefined, despite the fact that the PHI node is overdefined.
00117   std::multimap<PHINode*, Instruction*> UsersOfOverdefinedPHIs;
00118 
00119   /// KnownFeasibleEdges - Entries in this set are edges which have already had
00120   /// PHI nodes retriggered.
00121   typedef std::pair<BasicBlock*,BasicBlock*> Edge;
00122   std::set<Edge> KnownFeasibleEdges;
00123 public:
00124 
00125   /// MarkBlockExecutable - This method can be used by clients to mark all of
00126   /// the blocks that are known to be intrinsically live in the processed unit.
00127   void MarkBlockExecutable(BasicBlock *BB) {
00128     DEBUG(std::cerr << "Marking Block Executable: " << BB->getName() << "\n");
00129     BBExecutable.insert(BB);   // Basic block is executable!
00130     BBWorkList.push_back(BB);  // Add the block to the work list!
00131   }
00132 
00133   /// Solve - Solve for constants and executable blocks.
00134   ///
00135   void Solve();
00136 
00137   /// getExecutableBlocks - Once we have solved for constants, return the set of
00138   /// blocks that is known to be executable.
00139   std::set<BasicBlock*> &getExecutableBlocks() {
00140     return BBExecutable;
00141   }
00142 
00143   /// getValueMapping - Once we have solved for constants, return the mapping of
00144   /// LLVM values to LatticeVals.
00145   hash_map<Value*, LatticeVal> &getValueMapping() {
00146     return ValueState;
00147   }
00148 
00149 private:
00150   // markConstant - Make a value be marked as "constant".  If the value
00151   // is not already a constant, add it to the instruction work list so that 
00152   // the users of the instruction are updated later.
00153   //
00154   inline void markConstant(LatticeVal &IV, Instruction *I, Constant *C) {
00155     if (IV.markConstant(C)) {
00156       DEBUG(std::cerr << "markConstant: " << *C << ": " << *I);
00157       InstWorkList.push_back(I);
00158     }
00159   }
00160   inline void markConstant(Instruction *I, Constant *C) {
00161     markConstant(ValueState[I], I, C);
00162   }
00163 
00164   // markOverdefined - Make a value be marked as "overdefined". If the
00165   // value is not already overdefined, add it to the overdefined instruction 
00166   // work list so that the users of the instruction are updated later.
00167   
00168   inline void markOverdefined(LatticeVal &IV, Instruction *I) {
00169     if (IV.markOverdefined()) {
00170       DEBUG(std::cerr << "markOverdefined: " << *I);
00171       // Only instructions go on the work list
00172       OverdefinedInstWorkList.push_back(I);
00173     }
00174   }
00175   inline void markOverdefined(Instruction *I) {
00176     markOverdefined(ValueState[I], I);
00177   }
00178 
00179   // getValueState - Return the LatticeVal object that corresponds to the value.
00180   // This function is necessary because not all values should start out in the
00181   // underdefined state... Argument's should be overdefined, and
00182   // constants should be marked as constants.  If a value is not known to be an
00183   // Instruction object, then use this accessor to get its value from the map.
00184   //
00185   inline LatticeVal &getValueState(Value *V) {
00186     hash_map<Value*, LatticeVal>::iterator I = ValueState.find(V);
00187     if (I != ValueState.end()) return I->second;  // Common case, in the map
00188 
00189     if (Constant *CPV = dyn_cast<Constant>(V)) {
00190       if (isa<UndefValue>(V)) {
00191         // Nothing to do, remain undefined.
00192       } else {
00193         ValueState[CPV].markConstant(CPV);          // Constants are constant
00194       }
00195     }
00196     // All others are underdefined by default...
00197     return ValueState[V];
00198   }
00199 
00200   // markEdgeExecutable - Mark a basic block as executable, adding it to the BB 
00201   // work list if it is not already executable...
00202   // 
00203   void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
00204     if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
00205       return;  // This edge is already known to be executable!
00206 
00207     if (BBExecutable.count(Dest)) {
00208       DEBUG(std::cerr << "Marking Edge Executable: " << Source->getName()
00209                       << " -> " << Dest->getName() << "\n");
00210 
00211       // The destination is already executable, but we just made an edge
00212       // feasible that wasn't before.  Revisit the PHI nodes in the block
00213       // because they have potentially new operands.
00214       for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I) {
00215         PHINode *PN = cast<PHINode>(I);
00216         visitPHINode(*PN);
00217       }
00218 
00219     } else {
00220       MarkBlockExecutable(Dest);
00221     }
00222   }
00223 
00224   // getFeasibleSuccessors - Return a vector of booleans to indicate which
00225   // successors are reachable from a given terminator instruction.
00226   //
00227   void getFeasibleSuccessors(TerminatorInst &TI, std::vector<bool> &Succs);
00228 
00229   // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
00230   // block to the 'To' basic block is currently feasible...
00231   //
00232   bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
00233 
00234   // OperandChangedState - This method is invoked on all of the users of an
00235   // instruction that was just changed state somehow....  Based on this
00236   // information, we need to update the specified user of this instruction.
00237   //
00238   void OperandChangedState(User *U) {
00239     // Only instructions use other variable values!
00240     Instruction &I = cast<Instruction>(*U);
00241     if (BBExecutable.count(I.getParent()))   // Inst is executable?
00242       visit(I);
00243   }
00244 
00245 private:
00246   friend class InstVisitor<SCCPSolver>;
00247 
00248   // visit implementations - Something changed in this instruction... Either an 
00249   // operand made a transition, or the instruction is newly executable.  Change
00250   // the value type of I to reflect these changes if appropriate.
00251   //
00252   void visitPHINode(PHINode &I);
00253 
00254   // Terminators
00255   void visitReturnInst(ReturnInst &I) { /*does not have an effect*/ }
00256   void visitTerminatorInst(TerminatorInst &TI);
00257 
00258   void visitCastInst(CastInst &I);
00259   void visitSelectInst(SelectInst &I);
00260   void visitBinaryOperator(Instruction &I);
00261   void visitShiftInst(ShiftInst &I) { visitBinaryOperator(I); }
00262 
00263   // Instructions that cannot be folded away...
00264   void visitStoreInst     (Instruction &I) { /*returns void*/ }
00265   void visitLoadInst      (LoadInst &I);
00266   void visitGetElementPtrInst(GetElementPtrInst &I);
00267   void visitCallInst      (CallInst &I);
00268   void visitInvokeInst    (TerminatorInst &I) {
00269     if (I.getType() != Type::VoidTy) markOverdefined(&I);
00270     visitTerminatorInst(I);
00271   }
00272   void visitUnwindInst    (TerminatorInst &I) { /*returns void*/ }
00273   void visitUnreachableInst(TerminatorInst &I) { /*returns void*/ }
00274   void visitAllocationInst(Instruction &I) { markOverdefined(&I); }
00275   void visitVANextInst    (Instruction &I) { markOverdefined(&I); }
00276   void visitVAArgInst     (Instruction &I) { markOverdefined(&I); }
00277   void visitFreeInst      (Instruction &I) { /*returns void*/ }
00278 
00279   void visitInstruction(Instruction &I) {
00280     // If a new instruction is added to LLVM that we don't handle...
00281     std::cerr << "SCCP: Don't know how to handle: " << I;
00282     markOverdefined(&I);   // Just in case
00283   }
00284 };
00285 
00286 // getFeasibleSuccessors - Return a vector of booleans to indicate which
00287 // successors are reachable from a given terminator instruction.
00288 //
00289 void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI,
00290                                        std::vector<bool> &Succs) {
00291   Succs.resize(TI.getNumSuccessors());
00292   if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
00293     if (BI->isUnconditional()) {
00294       Succs[0] = true;
00295     } else {
00296       LatticeVal &BCValue = getValueState(BI->getCondition());
00297       if (BCValue.isOverdefined() ||
00298           (BCValue.isConstant() && !isa<ConstantBool>(BCValue.getConstant()))) {
00299         // Overdefined condition variables, and branches on unfoldable constant
00300         // conditions, mean the branch could go either way.
00301         Succs[0] = Succs[1] = true;
00302       } else if (BCValue.isConstant()) {
00303         // Constant condition variables mean the branch can only go a single way
00304         Succs[BCValue.getConstant() == ConstantBool::False] = true;
00305       }
00306     }
00307   } else if (InvokeInst *II = dyn_cast<InvokeInst>(&TI)) {
00308     // Invoke instructions successors are always executable.
00309     Succs[0] = Succs[1] = true;
00310   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) {
00311     LatticeVal &SCValue = getValueState(SI->getCondition());
00312     if (SCValue.isOverdefined() ||   // Overdefined condition?
00313         (SCValue.isConstant() && !isa<ConstantInt>(SCValue.getConstant()))) {
00314       // All destinations are executable!
00315       Succs.assign(TI.getNumSuccessors(), true);
00316     } else if (SCValue.isConstant()) {
00317       Constant *CPV = SCValue.getConstant();
00318       // Make sure to skip the "default value" which isn't a value
00319       for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) {
00320         if (SI->getSuccessorValue(i) == CPV) {// Found the right branch...
00321           Succs[i] = true;
00322           return;
00323         }
00324       }
00325 
00326       // Constant value not equal to any of the branches... must execute
00327       // default branch then...
00328       Succs[0] = true;
00329     }
00330   } else {
00331     std::cerr << "SCCP: Don't know how to handle: " << TI;
00332     Succs.assign(TI.getNumSuccessors(), true);
00333   }
00334 }
00335 
00336 
00337 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
00338 // block to the 'To' basic block is currently feasible...
00339 //
00340 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) {
00341   assert(BBExecutable.count(To) && "Dest should always be alive!");
00342 
00343   // Make sure the source basic block is executable!!
00344   if (!BBExecutable.count(From)) return false;
00345   
00346   // Check to make sure this edge itself is actually feasible now...
00347   TerminatorInst *TI = From->getTerminator();
00348   if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
00349     if (BI->isUnconditional())
00350       return true;
00351     else {
00352       LatticeVal &BCValue = getValueState(BI->getCondition());
00353       if (BCValue.isOverdefined()) {
00354         // Overdefined condition variables mean the branch could go either way.
00355         return true;
00356       } else if (BCValue.isConstant()) {
00357         // Not branching on an evaluatable constant?
00358         if (!isa<ConstantBool>(BCValue.getConstant())) return true;
00359 
00360         // Constant condition variables mean the branch can only go a single way
00361         return BI->getSuccessor(BCValue.getConstant() == 
00362                                        ConstantBool::False) == To;
00363       }
00364       return false;
00365     }
00366   } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
00367     // Invoke instructions successors are always executable.
00368     return true;
00369   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
00370     LatticeVal &SCValue = getValueState(SI->getCondition());
00371     if (SCValue.isOverdefined()) {  // Overdefined condition?
00372       // All destinations are executable!
00373       return true;
00374     } else if (SCValue.isConstant()) {
00375       Constant *CPV = SCValue.getConstant();
00376       if (!isa<ConstantInt>(CPV))
00377         return true;  // not a foldable constant?
00378 
00379       // Make sure to skip the "default value" which isn't a value
00380       for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i)
00381         if (SI->getSuccessorValue(i) == CPV) // Found the taken branch...
00382           return SI->getSuccessor(i) == To;
00383 
00384       // Constant value not equal to any of the branches... must execute
00385       // default branch then...
00386       return SI->getDefaultDest() == To;
00387     }
00388     return false;
00389   } else {
00390     std::cerr << "Unknown terminator instruction: " << *TI;
00391     abort();
00392   }
00393 }
00394 
00395 // visit Implementations - Something changed in this instruction... Either an
00396 // operand made a transition, or the instruction is newly executable.  Change
00397 // the value type of I to reflect these changes if appropriate.  This method
00398 // makes sure to do the following actions:
00399 //
00400 // 1. If a phi node merges two constants in, and has conflicting value coming
00401 //    from different branches, or if the PHI node merges in an overdefined
00402 //    value, then the PHI node becomes overdefined.
00403 // 2. If a phi node merges only constants in, and they all agree on value, the
00404 //    PHI node becomes a constant value equal to that.
00405 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
00406 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
00407 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
00408 // 6. If a conditional branch has a value that is constant, make the selected
00409 //    destination executable
00410 // 7. If a conditional branch has a value that is overdefined, make all
00411 //    successors executable.
00412 //
00413 void SCCPSolver::visitPHINode(PHINode &PN) {
00414   LatticeVal &PNIV = getValueState(&PN);
00415   if (PNIV.isOverdefined()) {
00416     // There may be instructions using this PHI node that are not overdefined
00417     // themselves.  If so, make sure that they know that the PHI node operand
00418     // changed.
00419     std::multimap<PHINode*, Instruction*>::iterator I, E;
00420     tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN);
00421     if (I != E) {
00422       std::vector<Instruction*> Users;
00423       Users.reserve(std::distance(I, E));
00424       for (; I != E; ++I) Users.push_back(I->second);
00425       while (!Users.empty()) {
00426         visit(Users.back());
00427         Users.pop_back();
00428       }
00429     }
00430     return;  // Quick exit
00431   }
00432 
00433   // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
00434   // and slow us down a lot.  Just mark them overdefined.
00435   if (PN.getNumIncomingValues() > 64) {
00436     markOverdefined(PNIV, &PN);
00437     return;
00438   }
00439 
00440   // Look at all of the executable operands of the PHI node.  If any of them
00441   // are overdefined, the PHI becomes overdefined as well.  If they are all
00442   // constant, and they agree with each other, the PHI becomes the identical
00443   // constant.  If they are constant and don't agree, the PHI is overdefined.
00444   // If there are no executable operands, the PHI remains undefined.
00445   //
00446   Constant *OperandVal = 0;
00447   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
00448     LatticeVal &IV = getValueState(PN.getIncomingValue(i));
00449     if (IV.isUndefined()) continue;  // Doesn't influence PHI node.
00450     
00451     if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) {
00452       if (IV.isOverdefined()) {   // PHI node becomes overdefined!
00453         markOverdefined(PNIV, &PN);
00454         return;
00455       }
00456 
00457       if (OperandVal == 0) {   // Grab the first value...
00458         OperandVal = IV.getConstant();
00459       } else {                // Another value is being merged in!
00460         // There is already a reachable operand.  If we conflict with it,
00461         // then the PHI node becomes overdefined.  If we agree with it, we
00462         // can continue on.
00463         
00464         // Check to see if there are two different constants merging...
00465         if (IV.getConstant() != OperandVal) {
00466           // Yes there is.  This means the PHI node is not constant.
00467           // You must be overdefined poor PHI.
00468           //
00469           markOverdefined(PNIV, &PN);    // The PHI node now becomes overdefined
00470           return;    // I'm done analyzing you
00471         }
00472       }
00473     }
00474   }
00475 
00476   // If we exited the loop, this means that the PHI node only has constant
00477   // arguments that agree with each other(and OperandVal is the constant) or
00478   // OperandVal is null because there are no defined incoming arguments.  If
00479   // this is the case, the PHI remains undefined.
00480   //
00481   if (OperandVal)
00482     markConstant(PNIV, &PN, OperandVal);      // Acquire operand value
00483 }
00484 
00485 void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) {
00486   std::vector<bool> SuccFeasible;
00487   getFeasibleSuccessors(TI, SuccFeasible);
00488 
00489   BasicBlock *BB = TI.getParent();
00490 
00491   // Mark all feasible successors executable...
00492   for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
00493     if (SuccFeasible[i])
00494       markEdgeExecutable(BB, TI.getSuccessor(i));
00495 }
00496 
00497 void SCCPSolver::visitCastInst(CastInst &I) {
00498   Value *V = I.getOperand(0);
00499   LatticeVal &VState = getValueState(V);
00500   if (VState.isOverdefined())          // Inherit overdefinedness of operand
00501     markOverdefined(&I);
00502   else if (VState.isConstant())        // Propagate constant value
00503     markConstant(&I, ConstantExpr::getCast(VState.getConstant(), I.getType()));
00504 }
00505 
00506 void SCCPSolver::visitSelectInst(SelectInst &I) {
00507   LatticeVal &CondValue = getValueState(I.getCondition());
00508   if (CondValue.isOverdefined())
00509     markOverdefined(&I);
00510   else if (CondValue.isConstant()) {
00511     if (CondValue.getConstant() == ConstantBool::True) {
00512       LatticeVal &Val = getValueState(I.getTrueValue());
00513       if (Val.isOverdefined())
00514         markOverdefined(&I);
00515       else if (Val.isConstant())
00516         markConstant(&I, Val.getConstant());
00517     } else if (CondValue.getConstant() == ConstantBool::False) {
00518       LatticeVal &Val = getValueState(I.getFalseValue());
00519       if (Val.isOverdefined())
00520         markOverdefined(&I);
00521       else if (Val.isConstant())
00522         markConstant(&I, Val.getConstant());
00523     } else
00524       markOverdefined(&I);
00525   }
00526 }
00527 
00528 // Handle BinaryOperators and Shift Instructions...
00529 void SCCPSolver::visitBinaryOperator(Instruction &I) {
00530   LatticeVal &IV = ValueState[&I];
00531   if (IV.isOverdefined()) return;
00532 
00533   LatticeVal &V1State = getValueState(I.getOperand(0));
00534   LatticeVal &V2State = getValueState(I.getOperand(1));
00535 
00536   if (V1State.isOverdefined() || V2State.isOverdefined()) {
00537     // If both operands are PHI nodes, it is possible that this instruction has
00538     // a constant value, despite the fact that the PHI node doesn't.  Check for
00539     // this condition now.
00540     if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0)))
00541       if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1)))
00542         if (PN1->getParent() == PN2->getParent()) {
00543           // Since the two PHI nodes are in the same basic block, they must have
00544           // entries for the same predecessors.  Walk the predecessor list, and
00545           // if all of the incoming values are constants, and the result of
00546           // evaluating this expression with all incoming value pairs is the
00547           // same, then this expression is a constant even though the PHI node
00548           // is not a constant!
00549           LatticeVal Result;
00550           for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) {
00551             LatticeVal &In1 = getValueState(PN1->getIncomingValue(i));
00552             BasicBlock *InBlock = PN1->getIncomingBlock(i);
00553             LatticeVal &In2 =
00554               getValueState(PN2->getIncomingValueForBlock(InBlock));
00555 
00556             if (In1.isOverdefined() || In2.isOverdefined()) {
00557               Result.markOverdefined();
00558               break;  // Cannot fold this operation over the PHI nodes!
00559             } else if (In1.isConstant() && In2.isConstant()) {
00560               Constant *V = ConstantExpr::get(I.getOpcode(), In1.getConstant(),
00561                                               In2.getConstant());
00562               if (Result.isUndefined())
00563                 Result.markConstant(V);
00564               else if (Result.isConstant() && Result.getConstant() != V) {
00565                 Result.markOverdefined();
00566                 break;
00567               }
00568             }
00569           }
00570 
00571           // If we found a constant value here, then we know the instruction is
00572           // constant despite the fact that the PHI nodes are overdefined.
00573           if (Result.isConstant()) {
00574             markConstant(IV, &I, Result.getConstant());
00575             // Remember that this instruction is virtually using the PHI node
00576             // operands.
00577             UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I));
00578             UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I));
00579             return;
00580           } else if (Result.isUndefined()) {
00581             return;
00582           }
00583 
00584           // Okay, this really is overdefined now.  Since we might have
00585           // speculatively thought that this was not overdefined before, and
00586           // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs,
00587           // make sure to clean out any entries that we put there, for
00588           // efficiency.
00589           std::multimap<PHINode*, Instruction*>::iterator It, E;
00590           tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1);
00591           while (It != E) {
00592             if (It->second == &I) {
00593               UsersOfOverdefinedPHIs.erase(It++);
00594             } else
00595               ++It;
00596           }
00597           tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2);
00598           while (It != E) {
00599             if (It->second == &I) {
00600               UsersOfOverdefinedPHIs.erase(It++);
00601             } else
00602               ++It;
00603           }
00604         }
00605 
00606     markOverdefined(IV, &I);
00607   } else if (V1State.isConstant() && V2State.isConstant()) {
00608     markConstant(IV, &I, ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
00609                                            V2State.getConstant()));
00610   }
00611 }
00612 
00613 // Handle getelementptr instructions... if all operands are constants then we
00614 // can turn this into a getelementptr ConstantExpr.
00615 //
00616 void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) {
00617   LatticeVal &IV = ValueState[&I];
00618   if (IV.isOverdefined()) return;
00619 
00620   std::vector<Constant*> Operands;
00621   Operands.reserve(I.getNumOperands());
00622 
00623   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
00624     LatticeVal &State = getValueState(I.getOperand(i));
00625     if (State.isUndefined())
00626       return;  // Operands are not resolved yet...
00627     else if (State.isOverdefined()) {
00628       markOverdefined(IV, &I);
00629       return;
00630     }
00631     assert(State.isConstant() && "Unknown state!");
00632     Operands.push_back(State.getConstant());
00633   }
00634 
00635   Constant *Ptr = Operands[0];
00636   Operands.erase(Operands.begin());  // Erase the pointer from idx list...
00637 
00638   markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, Operands));  
00639 }
00640 
00641 /// GetGEPGlobalInitializer - Given a constant and a getelementptr constantexpr,
00642 /// return the constant value being addressed by the constant expression, or
00643 /// null if something is funny.
00644 ///
00645 static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) {
00646   if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType()))
00647     return 0;  // Do not allow stepping over the value!
00648 
00649   // Loop over all of the operands, tracking down which value we are
00650   // addressing...
00651   for (unsigned i = 2, e = CE->getNumOperands(); i != e; ++i)
00652     if (ConstantUInt *CU = dyn_cast<ConstantUInt>(CE->getOperand(i))) {
00653       ConstantStruct *CS = dyn_cast<ConstantStruct>(C);
00654       if (CS == 0) return 0;
00655       if (CU->getValue() >= CS->getNumOperands()) return 0;
00656       C = CS->getOperand(CU->getValue());
00657     } else if (ConstantSInt *CS = dyn_cast<ConstantSInt>(CE->getOperand(i))) {
00658       ConstantArray *CA = dyn_cast<ConstantArray>(C);
00659       if (CA == 0) return 0;
00660       if ((uint64_t)CS->getValue() >= CA->getNumOperands()) return 0;
00661       C = CA->getOperand(CS->getValue());
00662     } else
00663       return 0;
00664   return C;
00665 }
00666 
00667 // Handle load instructions.  If the operand is a constant pointer to a constant
00668 // global, we can replace the load with the loaded constant value!
00669 void SCCPSolver::visitLoadInst(LoadInst &I) {
00670   LatticeVal &IV = ValueState[&I];
00671   if (IV.isOverdefined()) return;
00672 
00673   LatticeVal &PtrVal = getValueState(I.getOperand(0));
00674   if (PtrVal.isUndefined()) return;   // The pointer is not resolved yet!
00675   if (PtrVal.isConstant() && !I.isVolatile()) {
00676     Value *Ptr = PtrVal.getConstant();
00677     if (isa<ConstantPointerNull>(Ptr)) {
00678       // load null -> null
00679       markConstant(IV, &I, Constant::getNullValue(I.getType()));
00680       return;
00681     }
00682       
00683     // Transform load (constant global) into the value loaded.
00684     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr))
00685       if (GV->isConstant() && !GV->isExternal()) {
00686         markConstant(IV, &I, GV->getInitializer());
00687         return;
00688       }
00689 
00690     // Transform load (constantexpr_GEP global, 0, ...) into the value loaded.
00691     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
00692       if (CE->getOpcode() == Instruction::GetElementPtr)
00693   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
00694     if (GV->isConstant() && !GV->isExternal())
00695       if (Constant *V = 
00696     GetGEPGlobalInitializer(GV->getInitializer(), CE)) {
00697         markConstant(IV, &I, V);
00698         return;
00699       }
00700   }
00701 
00702   // Otherwise we cannot say for certain what value this load will produce.
00703   // Bail out.
00704   markOverdefined(IV, &I);
00705 }
00706 
00707 void SCCPSolver::visitCallInst(CallInst &I) {
00708   LatticeVal &IV = ValueState[&I];
00709   if (IV.isOverdefined()) return;
00710 
00711   Function *F = I.getCalledFunction();
00712   if (F == 0 || !canConstantFoldCallTo(F)) {
00713     markOverdefined(IV, &I);
00714     return;
00715   }
00716 
00717   std::vector<Constant*> Operands;
00718   Operands.reserve(I.getNumOperands()-1);
00719 
00720   for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) {
00721     LatticeVal &State = getValueState(I.getOperand(i));
00722     if (State.isUndefined())
00723       return;  // Operands are not resolved yet...
00724     else if (State.isOverdefined()) {
00725       markOverdefined(IV, &I);
00726       return;
00727     }
00728     assert(State.isConstant() && "Unknown state!");
00729     Operands.push_back(State.getConstant());
00730   }
00731 
00732   if (Constant *C = ConstantFoldCall(F, Operands))
00733     markConstant(IV, &I, C);
00734   else
00735     markOverdefined(IV, &I);
00736 }
00737 
00738 
00739 void SCCPSolver::Solve() {
00740   // Process the work lists until they are empty!
00741   while (!BBWorkList.empty() || !InstWorkList.empty() || 
00742    !OverdefinedInstWorkList.empty()) {
00743     // Process the instruction work list...
00744     while (!OverdefinedInstWorkList.empty()) {
00745       Instruction *I = OverdefinedInstWorkList.back();
00746       OverdefinedInstWorkList.pop_back();
00747 
00748       DEBUG(std::cerr << "\nPopped off OI-WL: " << I);
00749       
00750       // "I" got into the work list because it either made the transition from
00751       // bottom to constant
00752       //
00753       // Anything on this worklist that is overdefined need not be visited
00754       // since all of its users will have already been marked as overdefined
00755       // Update all of the users of this instruction's value...
00756       //
00757       for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
00758            UI != E; ++UI)
00759         OperandChangedState(*UI);
00760     }
00761     // Process the instruction work list...
00762     while (!InstWorkList.empty()) {
00763       Instruction *I = InstWorkList.back();
00764       InstWorkList.pop_back();
00765 
00766       DEBUG(std::cerr << "\nPopped off I-WL: " << *I);
00767       
00768       // "I" got into the work list because it either made the transition from
00769       // bottom to constant
00770       //
00771       // Anything on this worklist that is overdefined need not be visited
00772       // since all of its users will have already been marked as overdefined.
00773       // Update all of the users of this instruction's value...
00774       //
00775       if (!getValueState(I).isOverdefined())
00776         for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
00777              UI != E; ++UI)
00778           OperandChangedState(*UI);
00779     }
00780     
00781     // Process the basic block work list...
00782     while (!BBWorkList.empty()) {
00783       BasicBlock *BB = BBWorkList.back();
00784       BBWorkList.pop_back();
00785       
00786       DEBUG(std::cerr << "\nPopped off BBWL: " << *BB);
00787       
00788       // Notify all instructions in this basic block that they are newly
00789       // executable.
00790       visit(BB);
00791     }
00792   }
00793 }
00794 
00795 
00796 namespace {
00797   //===--------------------------------------------------------------------===//
00798   //
00799   /// SCCP Class - This class uses the SCCPSolver to implement a per-function
00800   /// Sparse Conditional COnstant Propagator.
00801   ///
00802   struct SCCP : public FunctionPass {
00803     // runOnFunction - Run the Sparse Conditional Constant Propagation
00804     // algorithm, and return true if the function was modified.
00805     //
00806     bool runOnFunction(Function &F);
00807     
00808     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00809       AU.setPreservesCFG();
00810     }
00811   };
00812 
00813   RegisterOpt<SCCP> X("sccp", "Sparse Conditional Constant Propagation");
00814 } // end anonymous namespace
00815 
00816 
00817 // createSCCPPass - This is the public interface to this file...
00818 FunctionPass *llvm::createSCCPPass() {
00819   return new SCCP();
00820 }
00821 
00822 
00823 // runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm,
00824 // and return true if the function was modified.
00825 //
00826 bool SCCP::runOnFunction(Function &F) {
00827   DEBUG(std::cerr << "SCCP on function '" << F.getName() << "'\n");
00828   SCCPSolver Solver;
00829 
00830   // Mark the first block of the function as being executable.
00831   Solver.MarkBlockExecutable(F.begin());
00832 
00833   // Mark all arguments to the function as being overdefined.
00834   hash_map<Value*, LatticeVal> &Values = Solver.getValueMapping();
00835   for (Function::aiterator AI = F.abegin(), E = F.aend(); AI != E; ++AI)
00836     Values[AI].markOverdefined();
00837 
00838   // Solve for constants.
00839   Solver.Solve();
00840 
00841   bool MadeChanges = false;
00842 
00843   // If we decided that there are basic blocks that are dead in this function,
00844   // delete their contents now.  Note that we cannot actually delete the blocks,
00845   // as we cannot modify the CFG of the function.
00846   //
00847   std::set<BasicBlock*> &ExecutableBBs = Solver.getExecutableBlocks();
00848   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
00849     if (!ExecutableBBs.count(BB)) {
00850       DEBUG(std::cerr << "  BasicBlock Dead:" << *BB);
00851       ++NumDeadBlocks;
00852 
00853       // Delete the instructions backwards, as it has a reduced likelihood of
00854       // having to update as many def-use and use-def chains.
00855       std::vector<Instruction*> Insts;
00856       for (BasicBlock::iterator I = BB->begin(), E = BB->getTerminator();
00857            I != E; ++I)
00858         Insts.push_back(I);
00859       while (!Insts.empty()) {
00860         Instruction *I = Insts.back();
00861         Insts.pop_back();
00862         if (!I->use_empty())
00863           I->replaceAllUsesWith(UndefValue::get(I->getType()));
00864         BB->getInstList().erase(I);
00865         MadeChanges = true;
00866         ++NumInstRemoved;
00867       }
00868     }
00869 
00870   // Iterate over all of the instructions in a function, replacing them with
00871   // constants if we have found them to be of constant values.
00872   //
00873   for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB)
00874     for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
00875       Instruction *Inst = BI++;
00876       if (Inst->getType() != Type::VoidTy) {
00877         LatticeVal &IV = Values[Inst];
00878         if (IV.isConstant() || IV.isUndefined() && !isa<TerminatorInst>(Inst)) {
00879           Constant *Const;
00880           if (IV.isConstant()) {
00881             Const = IV.getConstant();
00882             DEBUG(std::cerr << "  Constant: " << *Const << " = " << *Inst);
00883           } else {
00884             Const = UndefValue::get(Inst->getType());
00885             DEBUG(std::cerr << "  Undefined: " << *Inst);
00886           }
00887           
00888           // Replaces all of the uses of a variable with uses of the constant.
00889           Inst->replaceAllUsesWith(Const);
00890           
00891           // Delete the instruction.
00892           BB->getInstList().erase(Inst);
00893           
00894           // Hey, we just changed something!
00895           MadeChanges = true;
00896           ++NumInstRemoved;
00897         }
00898       }
00899     }
00900 
00901   return MadeChanges;
00902 }