LLVM API Documentation

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 is distributed under the University of Illinois Open Source
00006 // 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/Transforms/IPO.h"
00027 #include "llvm/Constants.h"
00028 #include "llvm/DerivedTypes.h"
00029 #include "llvm/Instructions.h"
00030 #include "llvm/LLVMContext.h"
00031 #include "llvm/Pass.h"
00032 #include "llvm/Analysis/ConstantFolding.h"
00033 #include "llvm/Analysis/ValueTracking.h"
00034 #include "llvm/Transforms/Utils/Local.h"
00035 #include "llvm/Support/CallSite.h"
00036 #include "llvm/Support/Compiler.h"
00037 #include "llvm/Support/Debug.h"
00038 #include "llvm/Support/ErrorHandling.h"
00039 #include "llvm/Support/InstVisitor.h"
00040 #include "llvm/Support/raw_ostream.h"
00041 #include "llvm/ADT/DenseMap.h"
00042 #include "llvm/ADT/DenseSet.h"
00043 #include "llvm/ADT/SmallSet.h"
00044 #include "llvm/ADT/SmallVector.h"
00045 #include "llvm/ADT/Statistic.h"
00046 #include "llvm/ADT/STLExtras.h"
00047 #include <algorithm>
00048 #include <map>
00049 using namespace llvm;
00050 
00051 STATISTIC(NumInstRemoved, "Number of instructions removed");
00052 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
00053 
00054 STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP");
00055 STATISTIC(IPNumDeadBlocks , "Number of basic blocks unreachable by IPSCCP");
00056 STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP");
00057 STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP");
00058 
00059 namespace {
00060 /// LatticeVal class - This class represents the different lattice values that
00061 /// an LLVM value may occupy.  It is a simple class with value semantics.
00062 ///
00063 class VISIBILITY_HIDDEN LatticeVal {
00064   enum {
00065     /// undefined - This LLVM Value has no known value yet.
00066     undefined,
00067     
00068     /// constant - This LLVM Value has a specific constant value.
00069     constant,
00070 
00071     /// forcedconstant - This LLVM Value was thought to be undef until
00072     /// ResolvedUndefsIn.  This is treated just like 'constant', but if merged
00073     /// with another (different) constant, it goes to overdefined, instead of
00074     /// asserting.
00075     forcedconstant,
00076     
00077     /// overdefined - This instruction is not known to be constant, and we know
00078     /// it has a value.
00079     overdefined
00080   } LatticeValue;    // The current lattice position
00081   
00082   Constant *ConstantVal; // If Constant value, the current value
00083 public:
00084   inline LatticeVal() : LatticeValue(undefined), ConstantVal(0) {}
00085   
00086   // markOverdefined - Return true if this is a new status to be in...
00087   inline bool markOverdefined() {
00088     if (LatticeValue != overdefined) {
00089       LatticeValue = overdefined;
00090       return true;
00091     }
00092     return false;
00093   }
00094 
00095   // markConstant - Return true if this is a new status for us.
00096   inline bool markConstant(Constant *V) {
00097     if (LatticeValue != constant) {
00098       if (LatticeValue == undefined) {
00099         LatticeValue = constant;
00100         assert(V && "Marking constant with NULL");
00101         ConstantVal = V;
00102       } else {
00103         assert(LatticeValue == forcedconstant && 
00104                "Cannot move from overdefined to constant!");
00105         // Stay at forcedconstant if the constant is the same.
00106         if (V == ConstantVal) return false;
00107         
00108         // Otherwise, we go to overdefined.  Assumptions made based on the
00109         // forced value are possibly wrong.  Assuming this is another constant
00110         // could expose a contradiction.
00111         LatticeValue = overdefined;
00112       }
00113       return true;
00114     } else {
00115       assert(ConstantVal == V && "Marking constant with different value");
00116     }
00117     return false;
00118   }
00119 
00120   inline void markForcedConstant(Constant *V) {
00121     assert(LatticeValue == undefined && "Can't force a defined value!");
00122     LatticeValue = forcedconstant;
00123     ConstantVal = V;
00124   }
00125   
00126   inline bool isUndefined() const { return LatticeValue == undefined; }
00127   inline bool isConstant() const {
00128     return LatticeValue == constant || LatticeValue == forcedconstant;
00129   }
00130   inline bool isOverdefined() const { return LatticeValue == overdefined; }
00131 
00132   inline Constant *getConstant() const {
00133     assert(isConstant() && "Cannot get the constant of a non-constant!");
00134     return ConstantVal;
00135   }
00136 };
00137 
00138 //===----------------------------------------------------------------------===//
00139 //
00140 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional
00141 /// Constant Propagation.
00142 ///
00143 class SCCPSolver : public InstVisitor<SCCPSolver> {
00144   LLVMContext *Context;
00145   DenseSet<BasicBlock*> BBExecutable;// The basic blocks that are executable
00146   std::map<Value*, LatticeVal> ValueState;  // The state each value is in.
00147 
00148   /// GlobalValue - If we are tracking any values for the contents of a global
00149   /// variable, we keep a mapping from the constant accessor to the element of
00150   /// the global, to the currently known value.  If the value becomes
00151   /// overdefined, it's entry is simply removed from this map.
00152   DenseMap<GlobalVariable*, LatticeVal> TrackedGlobals;
00153 
00154   /// TrackedRetVals - If we are tracking arguments into and the return
00155   /// value out of a function, it will have an entry in this map, indicating
00156   /// what the known return value for the function is.
00157   DenseMap<Function*, LatticeVal> TrackedRetVals;
00158 
00159   /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
00160   /// that return multiple values.
00161   DenseMap<std::pair<Function*, unsigned>, LatticeVal> TrackedMultipleRetVals;
00162 
00163   // The reason for two worklists is that overdefined is the lowest state
00164   // on the lattice, and moving things to overdefined as fast as possible
00165   // makes SCCP converge much faster.
00166   // By having a separate worklist, we accomplish this because everything
00167   // possibly overdefined will become overdefined at the soonest possible
00168   // point.
00169   SmallVector<Value*, 64> OverdefinedInstWorkList;
00170   SmallVector<Value*, 64> InstWorkList;
00171 
00172 
00173   SmallVector<BasicBlock*, 64>  BBWorkList;  // The BasicBlock work list
00174 
00175   /// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not
00176   /// overdefined, despite the fact that the PHI node is overdefined.
00177   std::multimap<PHINode*, Instruction*> UsersOfOverdefinedPHIs;
00178 
00179   /// KnownFeasibleEdges - Entries in this set are edges which have already had
00180   /// PHI nodes retriggered.
00181   typedef std::pair<BasicBlock*, BasicBlock*> Edge;
00182   DenseSet<Edge> KnownFeasibleEdges;
00183 public:
00184   void setContext(LLVMContext *C) { Context = C; }
00185 
00186   /// MarkBlockExecutable - This method can be used by clients to mark all of
00187   /// the blocks that are known to be intrinsically live in the processed unit.
00188   void MarkBlockExecutable(BasicBlock *BB) {
00189     DEBUG(errs() << "Marking Block Executable: " << BB->getName() << "\n");
00190     BBExecutable.insert(BB);   // Basic block is executable!
00191     BBWorkList.push_back(BB);  // Add the block to the work list!
00192   }
00193 
00194   /// TrackValueOfGlobalVariable - Clients can use this method to
00195   /// inform the SCCPSolver that it should track loads and stores to the
00196   /// specified global variable if it can.  This is only legal to call if
00197   /// performing Interprocedural SCCP.
00198   void TrackValueOfGlobalVariable(GlobalVariable *GV) {
00199     const Type *ElTy = GV->getType()->getElementType();
00200     if (ElTy->isFirstClassType()) {
00201       LatticeVal &IV = TrackedGlobals[GV];
00202       if (!isa<UndefValue>(GV->getInitializer()))
00203         IV.markConstant(GV->getInitializer());
00204     }
00205   }
00206 
00207   /// AddTrackedFunction - If the SCCP solver is supposed to track calls into
00208   /// and out of the specified function (which cannot have its address taken),
00209   /// this method must be called.
00210   void AddTrackedFunction(Function *F) {
00211     assert(F->hasLocalLinkage() && "Can only track internal functions!");
00212     // Add an entry, F -> undef.
00213     if (const StructType *STy = dyn_cast<StructType>(F->getReturnType())) {
00214       for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
00215         TrackedMultipleRetVals.insert(std::make_pair(std::make_pair(F, i),
00216                                                      LatticeVal()));
00217     } else
00218       TrackedRetVals.insert(std::make_pair(F, LatticeVal()));
00219   }
00220 
00221   /// Solve - Solve for constants and executable blocks.
00222   ///
00223   void Solve();
00224 
00225   /// ResolvedUndefsIn - While solving the dataflow for a function, we assume
00226   /// that branches on undef values cannot reach any of their successors.
00227   /// However, this is not a safe assumption.  After we solve dataflow, this
00228   /// method should be use to handle this.  If this returns true, the solver
00229   /// should be rerun.
00230   bool ResolvedUndefsIn(Function &F);
00231 
00232   bool isBlockExecutable(BasicBlock *BB) const {
00233     return BBExecutable.count(BB);
00234   }
00235 
00236   /// getValueMapping - Once we have solved for constants, return the mapping of
00237   /// LLVM values to LatticeVals.
00238   std::map<Value*, LatticeVal> &getValueMapping() {
00239     return ValueState;
00240   }
00241 
00242   /// getTrackedRetVals - Get the inferred return value map.
00243   ///
00244   const DenseMap<Function*, LatticeVal> &getTrackedRetVals() {
00245     return TrackedRetVals;
00246   }
00247 
00248   /// getTrackedGlobals - Get and return the set of inferred initializers for
00249   /// global variables.
00250   const DenseMap<GlobalVariable*, LatticeVal> &getTrackedGlobals() {
00251     return TrackedGlobals;
00252   }
00253 
00254   inline void markOverdefined(Value *V) {
00255     markOverdefined(ValueState[V], V);
00256   }
00257 
00258 private:
00259   // markConstant - Make a value be marked as "constant".  If the value
00260   // is not already a constant, add it to the instruction work list so that
00261   // the users of the instruction are updated later.
00262   //
00263   inline void markConstant(LatticeVal &IV, Value *V, Constant *C) {
00264     if (IV.markConstant(C)) {
00265       DEBUG(errs() << "markConstant: " << *C << ": " << *V << '\n');
00266       InstWorkList.push_back(V);
00267     }
00268   }
00269   
00270   inline void markForcedConstant(LatticeVal &IV, Value *V, Constant *C) {
00271     IV.markForcedConstant(C);
00272     DEBUG(errs() << "markForcedConstant: " << *C << ": " << *V << '\n');
00273     InstWorkList.push_back(V);
00274   }
00275   
00276   inline void markConstant(Value *V, Constant *C) {
00277     markConstant(ValueState[V], V, C);
00278   }
00279 
00280   // markOverdefined - Make a value be marked as "overdefined". If the
00281   // value is not already overdefined, add it to the overdefined instruction
00282   // work list so that the users of the instruction are updated later.
00283   inline void markOverdefined(LatticeVal &IV, Value *V) {
00284     if (IV.markOverdefined()) {
00285       DEBUG(errs() << "markOverdefined: ";
00286             if (Function *F = dyn_cast<Function>(V))
00287               errs() << "Function '" << F->getName() << "'\n";
00288             else
00289               errs() << *V << '\n');
00290       // Only instructions go on the work list
00291       OverdefinedInstWorkList.push_back(V);
00292     }
00293   }
00294 
00295   inline void mergeInValue(LatticeVal &IV, Value *V, LatticeVal &MergeWithV) {
00296     if (IV.isOverdefined() || MergeWithV.isUndefined())
00297       return;  // Noop.
00298     if (MergeWithV.isOverdefined())
00299       markOverdefined(IV, V);
00300     else if (IV.isUndefined())
00301       markConstant(IV, V, MergeWithV.getConstant());
00302     else if (IV.getConstant() != MergeWithV.getConstant())
00303       markOverdefined(IV, V);
00304   }
00305   
00306   inline void mergeInValue(Value *V, LatticeVal &MergeWithV) {
00307     return mergeInValue(ValueState[V], V, MergeWithV);
00308   }
00309 
00310 
00311   // getValueState - Return the LatticeVal object that corresponds to the value.
00312   // This function is necessary because not all values should start out in the
00313   // underdefined state... Argument's should be overdefined, and
00314   // constants should be marked as constants.  If a value is not known to be an
00315   // Instruction object, then use this accessor to get its value from the map.
00316   //
00317   inline LatticeVal &getValueState(Value *V) {
00318     std::map<Value*, LatticeVal>::iterator I = ValueState.find(V);
00319     if (I != ValueState.end()) return I->second;  // Common case, in the map
00320 
00321     if (Constant *C = dyn_cast<Constant>(V)) {
00322       if (isa<UndefValue>(V)) {
00323         // Nothing to do, remain undefined.
00324       } else {
00325         LatticeVal &LV = ValueState[C];
00326         LV.markConstant(C);          // Constants are constant
00327         return LV;
00328       }
00329     }
00330     // All others are underdefined by default...
00331     return ValueState[V];
00332   }
00333 
00334   // markEdgeExecutable - Mark a basic block as executable, adding it to the BB
00335   // work list if it is not already executable...
00336   //
00337   void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
00338     if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
00339       return;  // This edge is already known to be executable!
00340 
00341     if (BBExecutable.count(Dest)) {
00342       DEBUG(errs() << "Marking Edge Executable: " << Source->getName()
00343             << " -> " << Dest->getName() << "\n");
00344 
00345       // The destination is already executable, but we just made an edge
00346       // feasible that wasn't before.  Revisit the PHI nodes in the block
00347       // because they have potentially new operands.
00348       for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I)
00349         visitPHINode(*cast<PHINode>(I));
00350 
00351     } else {
00352       MarkBlockExecutable(Dest);
00353     }
00354   }
00355 
00356   // getFeasibleSuccessors - Return a vector of booleans to indicate which
00357   // successors are reachable from a given terminator instruction.
00358   //
00359   void getFeasibleSuccessors(TerminatorInst &TI, SmallVector<bool, 16> &Succs);
00360 
00361   // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
00362   // block to the 'To' basic block is currently feasible...
00363   //
00364   bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
00365 
00366   // OperandChangedState - This method is invoked on all of the users of an
00367   // instruction that was just changed state somehow....  Based on this
00368   // information, we need to update the specified user of this instruction.
00369   //
00370   void OperandChangedState(User *U) {
00371     // Only instructions use other variable values!
00372     Instruction &I = cast<Instruction>(*U);
00373     if (BBExecutable.count(I.getParent()))   // Inst is executable?
00374       visit(I);
00375   }
00376 
00377 private:
00378   friend class InstVisitor<SCCPSolver>;
00379 
00380   // visit implementations - Something changed in this instruction... Either an
00381   // operand made a transition, or the instruction is newly executable.  Change
00382   // the value type of I to reflect these changes if appropriate.
00383   //
00384   void visitPHINode(PHINode &I);
00385 
00386   // Terminators
00387   void visitReturnInst(ReturnInst &I);
00388   void visitTerminatorInst(TerminatorInst &TI);
00389 
00390   void visitCastInst(CastInst &I);
00391   void visitSelectInst(SelectInst &I);
00392   void visitBinaryOperator(Instruction &I);
00393   void visitCmpInst(CmpInst &I);
00394   void visitExtractElementInst(ExtractElementInst &I);
00395   void visitInsertElementInst(InsertElementInst &I);
00396   void visitShuffleVectorInst(ShuffleVectorInst &I);
00397   void visitExtractValueInst(ExtractValueInst &EVI);
00398   void visitInsertValueInst(InsertValueInst &IVI);
00399 
00400   // Instructions that cannot be folded away...
00401   void visitStoreInst     (Instruction &I);
00402   void visitLoadInst      (LoadInst &I);
00403   void visitGetElementPtrInst(GetElementPtrInst &I);
00404   void visitCallInst      (CallInst &I) { visitCallSite(CallSite::get(&I)); }
00405   void visitInvokeInst    (InvokeInst &II) {
00406     visitCallSite(CallSite::get(&II));
00407     visitTerminatorInst(II);
00408   }
00409   void visitCallSite      (CallSite CS);
00410   void visitUnwindInst    (TerminatorInst &I) { /*returns void*/ }
00411   void visitUnreachableInst(TerminatorInst &I) { /*returns void*/ }
00412   void visitAllocationInst(Instruction &I) { markOverdefined(&I); }
00413   void visitVANextInst    (Instruction &I) { markOverdefined(&I); }
00414   void visitVAArgInst     (Instruction &I) { markOverdefined(&I); }
00415   void visitFreeInst      (Instruction &I) { /*returns void*/ }
00416 
00417   void visitInstruction(Instruction &I) {
00418     // If a new instruction is added to LLVM that we don't handle...
00419     cerr << "SCCP: Don't know how to handle: " << I;
00420     markOverdefined(&I);   // Just in case
00421   }
00422 };
00423 
00424 } // end anonymous namespace
00425 
00426 
00427 // getFeasibleSuccessors - Return a vector of booleans to indicate which
00428 // successors are reachable from a given terminator instruction.
00429 //
00430 void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI,
00431                                        SmallVector<bool, 16> &Succs) {
00432   Succs.resize(TI.getNumSuccessors());
00433   if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
00434     if (BI->isUnconditional()) {
00435       Succs[0] = true;
00436     } else {
00437       LatticeVal &BCValue = getValueState(BI->getCondition());
00438       if (BCValue.isOverdefined() ||
00439           (BCValue.isConstant() && !isa<ConstantInt>(BCValue.getConstant()))) {
00440         // Overdefined condition variables, and branches on unfoldable constant
00441         // conditions, mean the branch could go either way.
00442         Succs[0] = Succs[1] = true;
00443       } else if (BCValue.isConstant()) {
00444         // Constant condition variables mean the branch can only go a single way
00445         Succs[BCValue.getConstant() == ConstantInt::getFalse(*Context)] = true;
00446       }
00447     }
00448   } else if (isa<InvokeInst>(&TI)) {
00449     // Invoke instructions successors are always executable.
00450     Succs[0] = Succs[1] = true;
00451   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) {
00452     LatticeVal &SCValue = getValueState(SI->getCondition());
00453     if (SCValue.isOverdefined() ||   // Overdefined condition?
00454         (SCValue.isConstant() && !isa<ConstantInt>(SCValue.getConstant()))) {
00455       // All destinations are executable!
00456       Succs.assign(TI.getNumSuccessors(), true);
00457     } else if (SCValue.isConstant())
00458       Succs[SI->findCaseValue(cast<ConstantInt>(SCValue.getConstant()))] = true;
00459   } else {
00460     llvm_unreachable("SCCP: Don't know how to handle this terminator!");
00461   }
00462 }
00463 
00464 
00465 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
00466 // block to the 'To' basic block is currently feasible...
00467 //
00468 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) {
00469   assert(BBExecutable.count(To) && "Dest should always be alive!");
00470 
00471   // Make sure the source basic block is executable!!
00472   if (!BBExecutable.count(From)) return false;
00473 
00474   // Check to make sure this edge itself is actually feasible now...
00475   TerminatorInst *TI = From->getTerminator();
00476   if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
00477     if (BI->isUnconditional())
00478       return true;
00479     else {
00480       LatticeVal &BCValue = getValueState(BI->getCondition());
00481       if (BCValue.isOverdefined()) {
00482         // Overdefined condition variables mean the branch could go either way.
00483         return true;
00484       } else if (BCValue.isConstant()) {
00485         // Not branching on an evaluatable constant?
00486         if (!isa<ConstantInt>(BCValue.getConstant())) return true;
00487 
00488         // Constant condition variables mean the branch can only go a single way
00489         return BI->getSuccessor(BCValue.getConstant() ==
00490                                        ConstantInt::getFalse(*Context)) == To;
00491       }
00492       return false;
00493     }
00494   } else if (isa<InvokeInst>(TI)) {
00495     // Invoke instructions successors are always executable.
00496     return true;
00497   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
00498     LatticeVal &SCValue = getValueState(SI->getCondition());
00499     if (SCValue.isOverdefined()) {  // Overdefined condition?
00500       // All destinations are executable!
00501       return true;
00502     } else if (SCValue.isConstant()) {
00503       Constant *CPV = SCValue.getConstant();
00504       if (!isa<ConstantInt>(CPV))
00505         return true;  // not a foldable constant?
00506 
00507       // Make sure to skip the "default value" which isn't a value
00508       for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i)
00509         if (SI->getSuccessorValue(i) == CPV) // Found the taken branch...
00510           return SI->getSuccessor(i) == To;
00511 
00512       // Constant value not equal to any of the branches... must execute
00513       // default branch then...
00514       return SI->getDefaultDest() == To;
00515     }
00516     return false;
00517   } else {
00518 #ifndef NDEBUG
00519     cerr << "Unknown terminator instruction: " << *TI << '\n';
00520 #endif
00521     llvm_unreachable(0);
00522   }
00523 }
00524 
00525 // visit Implementations - Something changed in this instruction... Either an
00526 // operand made a transition, or the instruction is newly executable.  Change
00527 // the value type of I to reflect these changes if appropriate.  This method
00528 // makes sure to do the following actions:
00529 //
00530 // 1. If a phi node merges two constants in, and has conflicting value coming
00531 //    from different branches, or if the PHI node merges in an overdefined
00532 //    value, then the PHI node becomes overdefined.
00533 // 2. If a phi node merges only constants in, and they all agree on value, the
00534 //    PHI node becomes a constant value equal to that.
00535 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
00536 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
00537 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
00538 // 6. If a conditional branch has a value that is constant, make the selected
00539 //    destination executable
00540 // 7. If a conditional branch has a value that is overdefined, make all
00541 //    successors executable.
00542 //
00543 void SCCPSolver::visitPHINode(PHINode &PN) {
00544   LatticeVal &PNIV = getValueState(&PN);
00545   if (PNIV.isOverdefined()) {
00546     // There may be instructions using this PHI node that are not overdefined
00547     // themselves.  If so, make sure that they know that the PHI node operand
00548     // changed.
00549     std::multimap<PHINode*, Instruction*>::iterator I, E;
00550     tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN);
00551     if (I != E) {
00552       SmallVector<Instruction*, 16> Users;
00553       for (; I != E; ++I) Users.push_back(I->second);
00554       while (!Users.empty()) {
00555         visit(Users.back());
00556         Users.pop_back();
00557       }
00558     }
00559     return;  // Quick exit
00560   }
00561 
00562   // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
00563   // and slow us down a lot.  Just mark them overdefined.
00564   if (PN.getNumIncomingValues() > 64) {
00565     markOverdefined(PNIV, &PN);
00566     return;
00567   }
00568 
00569   // Look at all of the executable operands of the PHI node.  If any of them
00570   // are overdefined, the PHI becomes overdefined as well.  If they are all
00571   // constant, and they agree with each other, the PHI becomes the identical
00572   // constant.  If they are constant and don't agree, the PHI is overdefined.
00573   // If there are no executable operands, the PHI remains undefined.
00574   //
00575   Constant *OperandVal = 0;
00576   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
00577     LatticeVal &IV = getValueState(PN.getIncomingValue(i));
00578     if (IV.isUndefined()) continue;  // Doesn't influence PHI node.
00579 
00580     if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) {
00581       if (IV.isOverdefined()) {   // PHI node becomes overdefined!
00582         markOverdefined(&PN);
00583         return;
00584       }
00585 
00586       if (OperandVal == 0) {   // Grab the first value...
00587         OperandVal = IV.getConstant();
00588       } else {                // Another value is being merged in!
00589         // There is already a reachable operand.  If we conflict with it,
00590         // then the PHI node becomes overdefined.  If we agree with it, we
00591         // can continue on.
00592 
00593         // Check to see if there are two different constants merging...
00594         if (IV.getConstant() != OperandVal) {
00595           // Yes there is.  This means the PHI node is not constant.
00596           // You must be overdefined poor PHI.
00597           //
00598           markOverdefined(&PN);    // The PHI node now becomes overdefined
00599           return;    // I'm done analyzing you
00600         }
00601       }
00602     }
00603   }
00604 
00605   // If we exited the loop, this means that the PHI node only has constant
00606   // arguments that agree with each other(and OperandVal is the constant) or
00607   // OperandVal is null because there are no defined incoming arguments.  If
00608   // this is the case, the PHI remains undefined.
00609   //
00610   if (OperandVal)
00611     markConstant(&PN, OperandVal);      // Acquire operand value
00612 }
00613 
00614 void SCCPSolver::visitReturnInst(ReturnInst &I) {
00615   if (I.getNumOperands() == 0) return;  // Ret void
00616 
00617   Function *F = I.getParent()->getParent();
00618   // If we are tracking the return value of this function, merge it in.
00619   if (!F->hasLocalLinkage())
00620     return;
00621 
00622   if (!TrackedRetVals.empty() && I.getNumOperands() == 1) {
00623     DenseMap<Function*, LatticeVal>::iterator TFRVI =
00624       TrackedRetVals.find(F);
00625     if (TFRVI != TrackedRetVals.end() &&
00626         !TFRVI->second.isOverdefined()) {
00627       LatticeVal &IV = getValueState(I.getOperand(0));
00628       mergeInValue(TFRVI->second, F, IV);
00629       return;
00630     }
00631   }
00632   
00633   // Handle functions that return multiple values.
00634   if (!TrackedMultipleRetVals.empty() && I.getNumOperands() > 1) {
00635     for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
00636       DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator
00637         It = TrackedMultipleRetVals.find(std::make_pair(F, i));
00638       if (It == TrackedMultipleRetVals.end()) break;
00639       mergeInValue(It->second, F, getValueState(I.getOperand(i)));
00640     }
00641   } else if (!TrackedMultipleRetVals.empty() &&
00642              I.getNumOperands() == 1 &&
00643              isa<StructType>(I.getOperand(0)->getType())) {
00644     for (unsigned i = 0, e = I.getOperand(0)->getType()->getNumContainedTypes();
00645          i != e; ++i) {
00646       DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator
00647         It = TrackedMultipleRetVals.find(std::make_pair(F, i));
00648       if (It == TrackedMultipleRetVals.end()) break;
00649       if (Value *Val = FindInsertedValue(I.getOperand(0), i, I.getContext()))
00650         mergeInValue(It->second, F, getValueState(Val));
00651     }
00652   }
00653 }
00654 
00655 void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) {
00656   SmallVector<bool, 16> SuccFeasible;
00657   getFeasibleSuccessors(TI, SuccFeasible);
00658 
00659   BasicBlock *BB = TI.getParent();
00660 
00661   // Mark all feasible successors executable...
00662   for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
00663     if (SuccFeasible[i])
00664       markEdgeExecutable(BB, TI.getSuccessor(i));
00665 }
00666 
00667 void SCCPSolver::visitCastInst(CastInst &I) {
00668   Value *V = I.getOperand(0);
00669   LatticeVal &VState = getValueState(V);
00670   if (VState.isOverdefined())          // Inherit overdefinedness of operand
00671     markOverdefined(&I);
00672   else if (VState.isConstant())        // Propagate constant value
00673     markConstant(&I, ConstantExpr::getCast(I.getOpcode(), 
00674                                            VState.getConstant(), I.getType()));
00675 }
00676 
00677 void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) {
00678   Value *Aggr = EVI.getAggregateOperand();
00679 
00680   // If the operand to the extractvalue is an undef, the result is undef.
00681   if (isa<UndefValue>(Aggr))
00682     return;
00683 
00684   // Currently only handle single-index extractvalues.
00685   if (EVI.getNumIndices() != 1) {
00686     markOverdefined(&EVI);
00687     return;
00688   }
00689   
00690   Function *F = 0;
00691   if (CallInst *CI = dyn_cast<CallInst>(Aggr))
00692     F = CI->getCalledFunction();
00693   else if (InvokeInst *II = dyn_cast<InvokeInst>(Aggr))
00694     F = II->getCalledFunction();
00695 
00696   // TODO: If IPSCCP resolves the callee of this function, we could propagate a
00697   // result back!
00698   if (F == 0 || TrackedMultipleRetVals.empty()) {
00699     markOverdefined(&EVI);
00700     return;
00701   }
00702   
00703   // See if we are tracking the result of the callee.  If not tracking this
00704   // function (for example, it is a declaration) just move to overdefined.
00705   if (!TrackedMultipleRetVals.count(std::make_pair(F, *EVI.idx_begin()))) {
00706     markOverdefined(&EVI);
00707     return;
00708   }
00709   
00710   // Otherwise, the value will be merged in here as a result of CallSite
00711   // handling.
00712 }
00713 
00714 void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) {
00715   Value *Aggr = IVI.getAggregateOperand();
00716   Value *Val = IVI.getInsertedValueOperand();
00717 
00718   // If the operands to the insertvalue are undef, the result is undef.
00719   if (isa<UndefValue>(Aggr) && isa<UndefValue>(Val))
00720     return;
00721 
00722   // Currently only handle single-index insertvalues.
00723   if (IVI.getNumIndices() != 1) {
00724     markOverdefined(&IVI);
00725     return;
00726   }
00727 
00728   // Currently only handle insertvalue instructions that are in a single-use
00729   // chain that builds up a return value.
00730   for (const InsertValueInst *TmpIVI = &IVI; ; ) {
00731     if (!TmpIVI->hasOneUse()) {
00732       markOverdefined(&IVI);
00733       return;
00734     }
00735     const Value *V = *TmpIVI->use_begin();
00736     if (isa<ReturnInst>(V))
00737       break;
00738     TmpIVI = dyn_cast<InsertValueInst>(V);
00739     if (!TmpIVI) {
00740       markOverdefined(&IVI);
00741       return;
00742     }
00743   }
00744   
00745   // See if we are tracking the result of the callee.
00746   Function *F = IVI.getParent()->getParent();
00747   DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator
00748     It = TrackedMultipleRetVals.find(std::make_pair(F, *IVI.idx_begin()));
00749 
00750   // Merge in the inserted member value.
00751   if (It != TrackedMultipleRetVals.end())
00752     mergeInValue(It->second, F, getValueState(Val));
00753 
00754   // Mark the aggregate result of the IVI overdefined; any tracking that we do
00755   // will be done on the individual member values.
00756   markOverdefined(&IVI);
00757 }
00758 
00759 void SCCPSolver::visitSelectInst(SelectInst &I) {
00760   LatticeVal &CondValue = getValueState(I.getCondition());
00761   if (CondValue.isUndefined())
00762     return;
00763   if (CondValue.isConstant()) {
00764     if (ConstantInt *CondCB = dyn_cast<ConstantInt>(CondValue.getConstant())){
00765       mergeInValue(&I, getValueState(CondCB->getZExtValue() ? I.getTrueValue()
00766                                                           : I.getFalseValue()));
00767       return;
00768     }
00769   }
00770   
00771   // Otherwise, the condition is overdefined or a constant we can't evaluate.
00772   // See if we can produce something better than overdefined based on the T/F
00773   // value.
00774   LatticeVal &TVal = getValueState(I.getTrueValue());
00775   LatticeVal &FVal = getValueState(I.getFalseValue());
00776   
00777   // select ?, C, C -> C.
00778   if (TVal.isConstant() && FVal.isConstant() && 
00779       TVal.getConstant() == FVal.getConstant()) {
00780     markConstant(&I, FVal.getConstant());
00781     return;
00782   }
00783 
00784   if (TVal.isUndefined()) {  // select ?, undef, X -> X.
00785     mergeInValue(&I, FVal);
00786   } else if (FVal.isUndefined()) {  // select ?, X, undef -> X.
00787     mergeInValue(&I, TVal);
00788   } else {
00789     markOverdefined(&I);
00790   }
00791 }
00792 
00793 // Handle BinaryOperators and Shift Instructions...
00794 void SCCPSolver::visitBinaryOperator(Instruction &I) {
00795   LatticeVal &IV = ValueState[&I];
00796   if (IV.isOverdefined()) return;
00797 
00798   LatticeVal &V1State = getValueState(I.getOperand(0));
00799   LatticeVal &V2State = getValueState(I.getOperand(1));
00800 
00801   if (V1State.isOverdefined() || V2State.isOverdefined()) {
00802     // If this is an AND or OR with 0 or -1, it doesn't matter that the other
00803     // operand is overdefined.
00804     if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Or) {
00805       LatticeVal *NonOverdefVal = 0;
00806       if (!V1State.isOverdefined()) {
00807         NonOverdefVal = &V1State;
00808       } else if (!V2State.isOverdefined()) {
00809         NonOverdefVal = &V2State;
00810       }
00811 
00812       if (NonOverdefVal) {
00813         if (NonOverdefVal->isUndefined()) {
00814           // Could annihilate value.
00815           if (I.getOpcode() == Instruction::And)
00816             markConstant(IV, &I, Constant::getNullValue(I.getType()));
00817           else if (const VectorType *PT = dyn_cast<VectorType>(I.getType()))
00818             markConstant(IV, &I, Constant::getAllOnesValue(PT));
00819           else
00820             markConstant(IV, &I,
00821                          Constant::getAllOnesValue(I.getType()));
00822           return;
00823         } else {
00824           if (I.getOpcode() == Instruction::And) {
00825             if (NonOverdefVal->getConstant()->isNullValue()) {
00826               markConstant(IV, &I, NonOverdefVal->getConstant());
00827               return;      // X and 0 = 0
00828             }
00829           } else {
00830             if (ConstantInt *CI =
00831                      dyn_cast<ConstantInt>(NonOverdefVal->getConstant()))
00832               if (CI->isAllOnesValue()) {
00833                 markConstant(IV, &I, NonOverdefVal->getConstant());
00834                 return;    // X or -1 = -1
00835               }
00836           }
00837         }
00838       }
00839     }
00840 
00841 
00842     // If both operands are PHI nodes, it is possible that this instruction has
00843     // a constant value, despite the fact that the PHI node doesn't.  Check for
00844     // this condition now.
00845     if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0)))
00846       if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1)))
00847         if (PN1->getParent() == PN2->getParent()) {
00848           // Since the two PHI nodes are in the same basic block, they must have
00849           // entries for the same predecessors.  Walk the predecessor list, and
00850           // if all of the incoming values are constants, and the result of
00851           // evaluating this expression with all incoming value pairs is the
00852           // same, then this expression is a constant even though the PHI node
00853           // is not a constant!
00854           LatticeVal Result;
00855           for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) {
00856             LatticeVal &In1 = getValueState(PN1->getIncomingValue(i));
00857             BasicBlock *InBlock = PN1->getIncomingBlock(i);
00858             LatticeVal &In2 =
00859               getValueState(PN2->getIncomingValueForBlock(InBlock));
00860 
00861             if (In1.isOverdefined() || In2.isOverdefined()) {
00862               Result.markOverdefined();
00863               break;  // Cannot fold this operation over the PHI nodes!
00864             } else if (In1.isConstant() && In2.isConstant()) {
00865               Constant *V =
00866                      ConstantExpr::get(I.getOpcode(), In1.getConstant(),
00867                                               In2.getConstant());
00868               if (Result.isUndefined())
00869                 Result.markConstant(V);
00870               else if (Result.isConstant() && Result.getConstant() != V) {
00871                 Result.markOverdefined();
00872                 break;
00873               }
00874             }
00875           }
00876 
00877           // If we found a constant value here, then we know the instruction is
00878           // constant despite the fact that the PHI nodes are overdefined.
00879           if (Result.isConstant()) {
00880             markConstant(IV, &I, Result.getConstant());
00881             // Remember that this instruction is virtually using the PHI node
00882             // operands.
00883             UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I));
00884             UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I));
00885             return;
00886           } else if (Result.isUndefined()) {
00887             return;
00888           }
00889 
00890           // Okay, this really is overdefined now.  Since we might have
00891           // speculatively thought that this was not overdefined before, and
00892           // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs,
00893           // make sure to clean out any entries that we put there, for
00894           // efficiency.
00895           std::multimap<PHINode*, Instruction*>::iterator It, E;
00896           tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1);
00897           while (It != E) {
00898             if (It->second == &I) {
00899               UsersOfOverdefinedPHIs.erase(It++);
00900             } else
00901               ++It;
00902           }
00903           tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2);
00904           while (It != E) {
00905             if (It->second == &I) {
00906               UsersOfOverdefinedPHIs.erase(It++);
00907             } else
00908               ++It;
00909           }
00910         }
00911 
00912     markOverdefined(IV, &I);
00913   } else if (V1State.isConstant() && V2State.isConstant()) {
00914     markConstant(IV, &I,
00915                 ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
00916                                            V2State.getConstant()));
00917   }
00918 }
00919 
00920 // Handle ICmpInst instruction...
00921 void SCCPSolver::visitCmpInst(CmpInst &I) {
00922   LatticeVal &IV = ValueState[&I];
00923   if (IV.isOverdefined()) return;
00924 
00925   LatticeVal &V1State = getValueState(I.getOperand(0));
00926   LatticeVal &V2State = getValueState(I.getOperand(1));
00927 
00928   if (V1State.isOverdefined() || V2State.isOverdefined()) {
00929     // If both operands are PHI nodes, it is possible that this instruction has
00930     // a constant value, despite the fact that the PHI node doesn't.  Check for
00931     // this condition now.
00932     if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0)))
00933       if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1)))
00934         if (PN1->getParent() == PN2->getParent()) {
00935           // Since the two PHI nodes are in the same basic block, they must have
00936           // entries for the same predecessors.  Walk the predecessor list, and
00937           // if all of the incoming values are constants, and the result of
00938           // evaluating this expression with all incoming value pairs is the
00939           // same, then this expression is a constant even though the PHI node
00940           // is not a constant!
00941           LatticeVal Result;
00942           for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) {
00943             LatticeVal &In1 = getValueState(PN1->getIncomingValue(i));
00944             BasicBlock *InBlock = PN1->getIncomingBlock(i);
00945             LatticeVal &In2 =
00946               getValueState(PN2->getIncomingValueForBlock(InBlock));
00947 
00948             if (In1.isOverdefined() || In2.isOverdefined()) {
00949               Result.markOverdefined();
00950               break;  // Cannot fold this operation over the PHI nodes!
00951             } else if (In1.isConstant() && In2.isConstant()) {
00952               Constant *V = ConstantExpr::getCompare(I.getPredicate(), 
00953                                                      In1.getConstant(), 
00954                                                      In2.getConstant());
00955               if (Result.isUndefined())
00956                 Result.markConstant(V);
00957               else if (Result.isConstant() && Result.getConstant() != V) {
00958                 Result.markOverdefined();
00959                 break;
00960               }
00961             }
00962           }
00963 
00964           // If we found a constant value here, then we know the instruction is
00965           // constant despite the fact that the PHI nodes are overdefined.
00966           if (Result.isConstant()) {
00967             markConstant(IV, &I, Result.getConstant());
00968             // Remember that this instruction is virtually using the PHI node
00969             // operands.
00970             UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I));
00971             UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I));
00972             return;
00973           } else if (Result.isUndefined()) {
00974             return;
00975           }
00976 
00977           // Okay, this really is overdefined now.  Since we might have
00978           // speculatively thought that this was not overdefined before, and
00979           // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs,
00980           // make sure to clean out any entries that we put there, for
00981           // efficiency.
00982           std::multimap<PHINode*, Instruction*>::iterator It, E;
00983           tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1);
00984           while (It != E) {
00985             if (It->second == &I) {
00986               UsersOfOverdefinedPHIs.erase(It++);
00987             } else
00988               ++It;
00989           }
00990           tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2);
00991           while (It != E) {
00992             if (It->second == &I) {
00993               UsersOfOverdefinedPHIs.erase(It++);
00994             } else
00995               ++It;
00996           }
00997         }
00998 
00999     markOverdefined(IV, &I);
01000   } else if (V1State.isConstant() && V2State.isConstant()) {
01001     markConstant(IV, &I, ConstantExpr::getCompare(I.getPredicate(), 
01002                                                   V1State.getConstant(), 
01003                                                   V2State.getConstant()));
01004   }
01005 }
01006 
01007 void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) {
01008   // FIXME : SCCP does not handle vectors properly.
01009   markOverdefined(&I);
01010   return;
01011 
01012 #if 0
01013   LatticeVal &ValState = getValueState(I.getOperand(0));
01014   LatticeVal &IdxState = getValueState(I.getOperand(1));
01015 
01016   if (ValState.isOverdefined() || IdxState.isOverdefined())
01017     markOverdefined(&I);
01018   else if(ValState.isConstant() && IdxState.isConstant())
01019     markConstant(&I, ConstantExpr::getExtractElement(ValState.getConstant(),
01020                                                      IdxState.getConstant()));
01021 #endif
01022 }
01023 
01024 void SCCPSolver::visitInsertElementInst(InsertElementInst &I) {
01025   // FIXME : SCCP does not handle vectors properly.
01026   markOverdefined(&I);
01027   return;
01028 #if 0
01029   LatticeVal &ValState = getValueState(I.getOperand(0));
01030   LatticeVal &EltState = getValueState(I.getOperand(1));
01031   LatticeVal &IdxState = getValueState(I.getOperand(2));
01032 
01033   if (ValState.isOverdefined() || EltState.isOverdefined() ||
01034       IdxState.isOverdefined())
01035     markOverdefined(&I);
01036   else if(ValState.isConstant() && EltState.isConstant() &&
01037           IdxState.isConstant())
01038     markConstant(&I, ConstantExpr::getInsertElement(ValState.getConstant(),
01039                                                     EltState.getConstant(),
01040                                                     IdxState.getConstant()));
01041   else if (ValState.isUndefined() && EltState.isConstant() &&
01042            IdxState.isConstant()) 
01043     markConstant(&I,ConstantExpr::getInsertElement(UndefValue::get(I.getType()),
01044                                                    EltState.getConstant(),
01045                                                    IdxState.getConstant()));
01046 #endif
01047 }
01048 
01049 void SCCPSolver::visitShuffleVectorInst(ShuffleVectorInst &I) {
01050   // FIXME : SCCP does not handle vectors properly.
01051   markOverdefined(&I);
01052   return;
01053 #if 0
01054   LatticeVal &V1State   = getValueState(I.getOperand(0));
01055   LatticeVal &V2State   = getValueState(I.getOperand(1));
01056   LatticeVal &MaskState = getValueState(I.getOperand(2));
01057 
01058   if (MaskState.isUndefined() ||
01059       (V1State.isUndefined() && V2State.isUndefined()))
01060     return;  // Undefined output if mask or both inputs undefined.
01061   
01062   if (V1State.isOverdefined() || V2State.isOverdefined() ||
01063       MaskState.isOverdefined()) {
01064     markOverdefined(&I);
01065   } else {
01066     // A mix of constant/undef inputs.
01067     Constant *V1 = V1State.isConstant() ? 
01068         V1State.getConstant() : UndefValue::get(I.getType());
01069     Constant *V2 = V2State.isConstant() ? 
01070         V2State.getConstant() : UndefValue::get(I.getType());
01071     Constant *Mask = MaskState.isConstant() ? 
01072       MaskState.getConstant() : UndefValue::get(I.getOperand(2)->getType());
01073     markConstant(&I, ConstantExpr::getShuffleVector(V1, V2, Mask));
01074   }
01075 #endif
01076 }
01077 
01078 // Handle getelementptr instructions... if all operands are constants then we
01079 // can turn this into a getelementptr ConstantExpr.
01080 //
01081 void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) {
01082   LatticeVal &IV = ValueState[&I];
01083   if (IV.isOverdefined()) return;
01084 
01085   SmallVector<Constant*, 8> Operands;
01086   Operands.reserve(I.getNumOperands());
01087 
01088   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
01089     LatticeVal &State = getValueState(I.getOperand(i));
01090     if (State.isUndefined())
01091       return;  // Operands are not resolved yet...
01092     else if (State.isOverdefined()) {
01093       markOverdefined(IV, &I);
01094       return;
01095     }
01096     assert(State.isConstant() && "Unknown state!");
01097     Operands.push_back(State.getConstant());
01098   }
01099 
01100   Constant *Ptr = Operands[0];
01101   Operands.erase(Operands.begin());  // Erase the pointer from idx list...
01102 
01103   markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, &Operands[0],
01104                                                       Operands.size()));
01105 }
01106 
01107 void SCCPSolver::visitStoreInst(Instruction &SI) {
01108   if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1)))
01109     return;
01110   GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1));
01111   DenseMap<GlobalVariable*, LatticeVal>::iterator I = TrackedGlobals.find(GV);
01112   if (I == TrackedGlobals.end() || I->second.isOverdefined()) return;
01113 
01114   // Get the value we are storing into the global.
01115   LatticeVal &PtrVal = getValueState(SI.getOperand(0));
01116 
01117   mergeInValue(I->second, GV, PtrVal);
01118   if (I->second.isOverdefined())
01119     TrackedGlobals.erase(I);      // No need to keep tracking this!
01120 }
01121 
01122 
01123 // Handle load instructions.  If the operand is a constant pointer to a constant
01124 // global, we can replace the load with the loaded constant value!
01125 void SCCPSolver::visitLoadInst(LoadInst &I) {
01126   LatticeVal &IV = ValueState[&I];
01127   if (IV.isOverdefined()) return;
01128 
01129   LatticeVal &PtrVal = getValueState(I.getOperand(0));
01130   if (PtrVal.isUndefined()) return;   // The pointer is not resolved yet!
01131   if (PtrVal.isConstant() && !I.isVolatile()) {
01132     Value *Ptr = PtrVal.getConstant();
01133     // TODO: Consider a target hook for valid address spaces for this xform.
01134     if (isa<ConstantPointerNull>(Ptr) && 
01135         cast<PointerType>(Ptr->getType())->getAddressSpace() == 0) {
01136       // load null -> null
01137       markConstant(IV, &I, Constant::getNullValue(I.getType()));
01138       return;
01139     }
01140 
01141     // Transform load (constant global) into the value loaded.
01142     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
01143       if (GV->isConstant()) {
01144         if (GV->hasDefinitiveInitializer()) {
01145           markConstant(IV, &I, GV->getInitializer());
01146           return;
01147         }
01148       } else if (!TrackedGlobals.empty()) {
01149         // If we are tracking this global, merge in the known value for it.
01150         DenseMap<GlobalVariable*, LatticeVal>::iterator It =
01151           TrackedGlobals.find(GV);
01152         if (It != TrackedGlobals.end()) {
01153           mergeInValue(IV, &I, It->second);
01154           return;
01155         }
01156       }
01157     }
01158 
01159     // Transform load (constantexpr_GEP global, 0, ...) into the value loaded.
01160     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
01161       if (CE->getOpcode() == Instruction::GetElementPtr)
01162     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
01163       if (GV->isConstant() && GV->hasDefinitiveInitializer())
01164         if (Constant *V =
01165              ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE,
01166                                                     *Context)) {
01167           markConstant(IV, &I, V);
01168           return;
01169         }
01170   }
01171 
01172   // Otherwise we cannot say for certain what value this load will produce.
01173   // Bail out.
01174   markOverdefined(IV, &I);
01175 }
01176 
01177 void SCCPSolver::visitCallSite(CallSite CS) {
01178   Function *F = CS.getCalledFunction();
01179   Instruction *I = CS.getInstruction();
01180   
01181   // The common case is that we aren't tracking the callee, either because we
01182   // are not doing interprocedural analysis or the callee is indirect, or is
01183   // external.  Handle these cases first.
01184   if (F == 0 || !F->hasLocalLinkage()) {
01185 CallOverdefined:
01186     // Void return and not tracking callee, just bail.
01187     if (I->getType() == Type::getVoidTy(I->getContext())) return;
01188     
01189     // Otherwise, if we have a single return value case, and if the function is
01190     // a declaration, maybe we can constant fold it.
01191     if (!isa<StructType>(I->getType()) && F && F->isDeclaration() && 
01192         canConstantFoldCallTo(F)) {
01193       
01194       SmallVector<Constant*, 8> Operands;
01195       for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
01196            AI != E; ++AI) {
01197         LatticeVal &State = getValueState(*AI);
01198         if (State.isUndefined())
01199           return;  // Operands are not resolved yet.
01200         else if (State.isOverdefined()) {
01201           markOverdefined(I);
01202           return;
01203         }
01204         assert(State.isConstant() && "Unknown state!");
01205         Operands.push_back(State.getConstant());
01206       }
01207      
01208       // If we can constant fold this, mark the result of the call as a
01209       // constant.
01210       if (Constant *C = ConstantFoldCall(F, Operands.data(), Operands.size())) {
01211         markConstant(I, C);
01212         return;
01213       }
01214     }
01215 
01216     // Otherwise, we don't know anything about this call, mark it overdefined.
01217     markOverdefined(I);
01218     return;
01219   }
01220 
01221   // If this is a single/zero retval case, see if we're tracking the function.
01222   DenseMap<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F);
01223   if (TFRVI != TrackedRetVals.end()) {
01224     // If so, propagate the return value of the callee into this call result.
01225     mergeInValue(I, TFRVI->second);
01226   } else if (isa<StructType>(I->getType())) {
01227     // Check to see if we're tracking this callee, if not, handle it in the
01228     // common path above.
01229     DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator
01230     TMRVI = TrackedMultipleRetVals.find(std::make_pair(F, 0));
01231     if (TMRVI == TrackedMultipleRetVals.end())
01232       goto CallOverdefined;
01233     
01234     // If we are tracking this callee, propagate the return values of the call
01235     // into this call site.  We do this by walking all the uses. Single-index
01236     // ExtractValueInst uses can be tracked; anything more complicated is
01237     // currently handled conservatively.
01238     for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
01239          UI != E; ++UI) {
01240       if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(*UI)) {
01241         if (EVI->getNumIndices() == 1) {
01242           mergeInValue(EVI, 
01243                   TrackedMultipleRetVals[std::make_pair(F, *EVI->idx_begin())]);
01244           continue;
01245         }
01246       }
01247       // The aggregate value is used in a way not handled here. Assume nothing.
01248       markOverdefined(*UI);
01249     }
01250   } else {
01251     // Otherwise we're not tracking this callee, so handle it in the
01252     // common path above.
01253     goto CallOverdefined;
01254   }
01255    
01256   // Finally, if this is the first call to the function hit, mark its entry
01257   // block executable.
01258   if (!BBExecutable.count(F->begin()))
01259     MarkBlockExecutable(F->begin());
01260   
01261   // Propagate information from this call site into the callee.
01262   CallSite::arg_iterator CAI = CS.arg_begin();
01263   for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
01264        AI != E; ++AI, ++CAI) {
01265     LatticeVal &IV = ValueState[AI];
01266     if (AI->hasByValAttr() && isa<PointerType>(AI->getType())) {
01267       IV.markOverdefined();
01268       continue;
01269     }
01270     if (!IV.isOverdefined())
01271       mergeInValue(IV, AI, getValueState(*CAI));
01272   }
01273 }
01274 
01275 
01276 void SCCPSolver::Solve() {
01277   // Process the work lists until they are empty!
01278   while (!BBWorkList.empty() || !InstWorkList.empty() ||
01279          !OverdefinedInstWorkList.empty()) {
01280     // Process the instruction work list...
01281     while (!OverdefinedInstWorkList.empty()) {
01282       Value *I = OverdefinedInstWorkList.back();
01283       OverdefinedInstWorkList.pop_back();
01284 
01285       DEBUG(errs() << "\nPopped off OI-WL: " << *I << '\n');
01286 
01287       // "I" got into the work list because it either made the transition from
01288       // bottom to constant
01289       //
01290       // Anything on this worklist that is overdefined need not be visited
01291       // since all of its users will have already been marked as overdefined
01292       // Update all of the users of this instruction's value...
01293       //
01294       for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
01295            UI != E; ++UI)
01296         OperandChangedState(*UI);
01297     }
01298     // Process the instruction work list...
01299     while (!InstWorkList.empty()) {
01300       Value *I = InstWorkList.back();
01301       InstWorkList.pop_back();
01302 
01303       DEBUG(errs() << "\nPopped off I-WL: " << *I << '\n');
01304 
01305       // "I" got into the work list because it either made the transition from
01306       // bottom to constant
01307       //
01308       // Anything on this worklist that is overdefined need not be visited
01309       // since all of its users will have already been marked as overdefined.
01310       // Update all of the users of this instruction's value...
01311       //
01312       if (!getValueState(I).isOverdefined())
01313         for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
01314              UI != E; ++UI)
01315           OperandChangedState(*UI);
01316     }
01317 
01318     // Process the basic block work list...
01319     while (!BBWorkList.empty()) {
01320       BasicBlock *BB = BBWorkList.back();
01321       BBWorkList.pop_back();
01322 
01323       DEBUG(errs() << "\nPopped off BBWL: " << *BB << '\n');
01324 
01325       // Notify all instructions in this basic block that they are newly
01326       // executable.
01327       visit(BB);
01328     }
01329   }
01330 }
01331 
01332 /// ResolvedUndefsIn - While solving the dataflow for a function, we assume
01333 /// that branches on undef values cannot reach any of their successors.
01334 /// However, this is not a safe assumption.  After we solve dataflow, this
01335 /// method should be use to handle this.  If this returns true, the solver
01336 /// should be rerun.
01337 ///
01338 /// This method handles this by finding an unresolved branch and marking it one
01339 /// of the edges from the block as being feasible, even though the condition
01340 /// doesn't say it would otherwise be.  This allows SCCP to find the rest of the
01341 /// CFG and only slightly pessimizes the analysis results (by marking one,
01342 /// potentially infeasible, edge feasible).  This cannot usefully modify the
01343 /// constraints on the condition of the branch, as that would impact other users
01344 /// of the value.
01345 ///
01346 /// This scan also checks for values that use undefs, whose results are actually
01347 /// defined.  For example, 'zext i8 undef to i32' should produce all zeros
01348 /// conservatively, as "(zext i8 X -> i32) & 0xFF00" must always return zero,
01349 /// even if X isn't defined.
01350 bool SCCPSolver::ResolvedUndefsIn(Function &F) {
01351   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
01352     if (!BBExecutable.count(BB))
01353       continue;
01354     
01355     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
01356       // Look for instructions which produce undef values.
01357       if (I->getType() == Type::getVoidTy(F.getContext())) continue;
01358       
01359       LatticeVal &LV = getValueState(I);
01360       if (!LV.isUndefined()) continue;
01361 
01362       // Get the lattice values of the first two operands for use below.
01363       LatticeVal &Op0LV = getValueState(I->getOperand(0));
01364       LatticeVal Op1LV;
01365       if (I->getNumOperands() == 2) {
01366         // If this is a two-operand instruction, and if both operands are
01367         // undefs, the result stays undef.
01368         Op1LV = getValueState(I->getOperand(1));
01369         if (Op0LV.isUndefined() && Op1LV.isUndefined())
01370           continue;
01371       }
01372       
01373       // If this is an instructions whose result is defined even if the input is
01374       // not fully defined, propagate the information.
01375       const Type *ITy = I->getType();
01376       switch (I->getOpcode()) {
01377       default: break;          // Leave the instruction as an undef.
01378       case Instruction::ZExt:
01379         // After a zero extend, we know the top part is zero.  SExt doesn't have
01380         // to be handled here, because we don't know whether the top part is 1's
01381         // or 0's.
01382         assert(Op0LV.isUndefined());
01383         markForcedConstant(LV, I, Constant::getNullValue(ITy));
01384         return true;
01385       case Instruction::Mul:
01386       case Instruction::And:
01387         // undef * X -> 0.   X could be zero.
01388         // undef & X -> 0.   X could be zero.
01389         markForcedConstant(LV, I, Constant::getNullValue(ITy));
01390         return true;
01391 
01392       case Instruction::Or:
01393         // undef | X -> -1.   X could be -1.
01394         if (const VectorType *PTy = dyn_cast<VectorType>(ITy))
01395           markForcedConstant(LV, I,
01396                              Constant::getAllOnesValue(PTy));
01397         else          
01398           markForcedConstant(LV, I, Constant::getAllOnesValue(ITy));
01399         return true;
01400 
01401       case Instruction::SDiv:
01402       case Instruction::UDiv:
01403       case Instruction::SRem:
01404       case Instruction::URem:
01405         // X / undef -> undef.  No change.
01406         // X % undef -> undef.  No change.
01407         if (Op1LV.isUndefined()) break;
01408         
01409         // undef / X -> 0.   X could be maxint.
01410         // undef % X -> 0.   X could be 1.
01411         markForcedConstant(LV, I, Constant::getNullValue(ITy));
01412         return true;
01413         
01414       case Instruction::AShr:
01415         // undef >>s X -> undef.  No change.
01416         if (Op0LV.isUndefined()) break;
01417         
01418         // X >>s undef -> X.  X could be 0, X could have the high-bit known set.
01419         if (Op0LV.isConstant())
01420           markForcedConstant(LV, I, Op0LV.getConstant());
01421         else
01422           markOverdefined(LV, I);
01423         return true;
01424       case Instruction::LShr:
01425       case Instruction::Shl:
01426         // undef >> X -> undef.  No change.
01427         // undef << X -> undef.  No change.
01428         if (Op0LV.isUndefined()) break;
01429         
01430         // X >> undef -> 0.  X could be 0.
01431         // X << undef -> 0.  X could be 0.
01432         markForcedConstant(LV, I, Constant::getNullValue(ITy));
01433         return true;
01434       case Instruction::Select:
01435         // undef ? X : Y  -> X or Y.  There could be commonality between X/Y.
01436         if (Op0LV.isUndefined()) {
01437           if (!Op1LV.isConstant())  // Pick the constant one if there is any.
01438             Op1LV = getValueState(I->getOperand(2));
01439         } else if (Op1LV.isUndefined()) {
01440           // c ? undef : undef -> undef.  No change.
01441           Op1LV = getValueState(I->getOperand(2));
01442           if (Op1LV.isUndefined())
01443             break;
01444           // Otherwise, c ? undef : x -> x.
01445         } else {
01446           // Leave Op1LV as Operand(1)'s LatticeValue.
01447         }
01448         
01449         if (Op1LV.isConstant())
01450           markForcedConstant(LV, I, Op1LV.getConstant());
01451         else
01452           markOverdefined(LV, I);
01453         return true;
01454       case Instruction::Call:
01455         // If a call has an undef result, it is because it is constant foldable
01456         // but one of the inputs was undef.  Just force the result to
01457         // overdefined.
01458         markOverdefined(LV, I);
01459         return true;
01460       }
01461     }
01462   
01463     TerminatorInst *TI = BB->getTerminator();
01464     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
01465       if (!BI->isConditional()) continue;
01466       if (!getValueState(BI->getCondition()).isUndefined())
01467         continue;
01468     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
01469       if (SI->getNumSuccessors()<2)   // no cases
01470         continue;
01471       if (!getValueState(SI->getCondition()).isUndefined())
01472         continue;
01473     } else {
01474       continue;
01475     }
01476     
01477     // If the edge to the second successor isn't thought to be feasible yet,
01478     // mark it so now.  We pick the second one so that this goes to some
01479     // enumerated value in a switch instead of going to the default destination.
01480     if (KnownFeasibleEdges.count(Edge(BB, TI->getSuccessor(1))))
01481       continue;
01482     
01483     // Otherwise, it isn't already thought to be feasible.  Mark it as such now
01484     // and return.  This will make other blocks reachable, which will allow new
01485     // values to be discovered and existing ones to be moved in the lattice.
01486     markEdgeExecutable(BB, TI->getSuccessor(1));
01487     
01488     // This must be a conditional branch of switch on undef.  At this point,
01489     // force the old terminator to branch to the first successor.  This is
01490     // required because we are now influencing the dataflow of the function with
01491     // the assumption that this edge is taken.  If we leave the branch condition
01492     // as undef, then further analysis could think the undef went another way
01493     // leading to an inconsistent set of conclusions.
01494     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
01495       BI->setCondition(ConstantInt::getFalse(*Context));
01496     } else {
01497       SwitchInst *SI = cast<SwitchInst>(TI);
01498       SI->setCondition(SI->getCaseValue(1));
01499     }
01500     
01501     return true;
01502   }
01503 
01504   return false;
01505 }
01506 
01507 
01508 namespace {
01509   //===--------------------------------------------------------------------===//
01510   //
01511   /// SCCP Class - This class uses the SCCPSolver to implement a per-function
01512   /// Sparse Conditional Constant Propagator.
01513   ///
01514   struct VISIBILITY_HIDDEN SCCP : public FunctionPass {
01515     static char ID; // Pass identification, replacement for typeid
01516     SCCP() : FunctionPass(&ID) {}
01517 
01518     // runOnFunction - Run the Sparse Conditional Constant Propagation
01519     // algorithm, and return true if the function was modified.
01520     //
01521     bool runOnFunction(Function &F);
01522 
01523     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
01524       AU.setPreservesCFG();
01525     }
01526   };
01527 } // end anonymous namespace
01528 
01529 char SCCP::ID = 0;
01530 static RegisterPass<SCCP>
01531 X("sccp", "Sparse Conditional Constant Propagation");
01532 
01533 // createSCCPPass - This is the public interface to this file...
01534 FunctionPass *llvm::createSCCPPass() {
01535   return new SCCP();
01536 }
01537 
01538 
01539 // runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm,
01540 // and return true if the function was modified.
01541 //
01542 bool SCCP::runOnFunction(Function &F) {
01543   DEBUG(errs() << "SCCP on function '" << F.getName() << "'\n");
01544   SCCPSolver Solver;
01545   Solver.setContext(&F.getContext());
01546 
01547   // Mark the first block of the function as being executable.
01548   Solver.MarkBlockExecutable(F.begin());
01549 
01550   // Mark all arguments to the function as being overdefined.
01551   for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;++AI)
01552     Solver.markOverdefined(AI);
01553 
01554   // Solve for constants.
01555   bool ResolvedUndefs = true;
01556   while (ResolvedUndefs) {
01557     Solver.Solve();
01558     DEBUG(errs() << "RESOLVING UNDEFs\n");
01559     ResolvedUndefs = Solver.ResolvedUndefsIn(F);
01560   }
01561 
01562   bool MadeChanges = false;
01563 
01564   // If we decided that there are basic blocks that are dead in this function,
01565   // delete their contents now.  Note that we cannot actually delete the blocks,
01566   // as we cannot modify the CFG of the function.
01567   //
01568   SmallVector<Instruction*, 512> Insts;
01569   std::map<Value*, LatticeVal> &Values = Solver.getValueMapping();
01570 
01571   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
01572     if (!Solver.isBlockExecutable(BB)) {
01573       DEBUG(errs() << "  BasicBlock Dead:" << *BB);
01574       ++NumDeadBlocks;
01575 
01576       // Delete the instructions backwards, as it has a reduced likelihood of
01577       // having to update as many def-use and use-def chains.
01578       for (BasicBlock::iterator I = BB->begin(), E = BB->getTerminator();
01579            I != E; ++I)
01580         Insts.push_back(I);
01581       while (!Insts.empty()) {
01582         Instruction *I = Insts.back();
01583         Insts.pop_back();
01584         if (!I->use_empty())
01585           I->replaceAllUsesWith(UndefValue::get(I->getType()));
01586         BB->getInstList().erase(I);
01587         MadeChanges = true;
01588         ++NumInstRemoved;
01589       }
01590     } else {
01591       // Iterate over all of the instructions in a function, replacing them with
01592       // constants if we have found them to be of constant values.
01593       //
01594       for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
01595         Instruction *Inst = BI++;
01596         if (Inst->getType() == Type::getVoidTy(F.getContext()) ||
01597             isa<TerminatorInst>(Inst))
01598           continue;
01599         
01600         LatticeVal &IV = Values[Inst];
01601         if (!IV.isConstant() && !IV.isUndefined())
01602           continue;
01603         
01604         Constant *Const = IV.isConstant()
01605           ? IV.getConstant() : UndefValue::get(Inst->getType());
01606         DEBUG(errs() << "  Constant: " << *Const << " = " << *Inst);
01607 
01608         // Replaces all of the uses of a variable with uses of the constant.
01609         Inst->replaceAllUsesWith(Const);
01610         
01611         // Delete the instruction.
01612         Inst->eraseFromParent();
01613         
01614         // Hey, we just changed something!
01615         MadeChanges = true;
01616         ++NumInstRemoved;
01617       }
01618     }
01619 
01620   return MadeChanges;
01621 }
01622 
01623 namespace {
01624   //===--------------------------------------------------------------------===//
01625   //
01626   /// IPSCCP Class - This class implements interprocedural Sparse Conditional
01627   /// Constant Propagation.
01628   ///
01629   struct VISIBILITY_HIDDEN IPSCCP : public ModulePass {
01630     static char ID;
01631     IPSCCP() : ModulePass(&ID) {}
01632     bool runOnModule(Module &M);
01633   };
01634 } // end anonymous namespace
01635 
01636 char IPSCCP::ID = 0;
01637 static RegisterPass<IPSCCP>
01638 Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation");
01639 
01640 // createIPSCCPPass - This is the public interface to this file...
01641 ModulePass *llvm::createIPSCCPPass() {
01642   return new IPSCCP();
01643 }
01644 
01645 
01646 static bool AddressIsTaken(GlobalValue *GV) {
01647   // Delete any dead constantexpr klingons.
01648   GV->removeDeadConstantUsers();
01649 
01650   for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end();
01651        UI != E; ++UI)
01652     if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
01653       if (SI->getOperand(0) == GV || SI->isVolatile())
01654         return true;  // Storing addr of GV.
01655     } else if (isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) {
01656       // Make sure we are calling the function, not passing the address.
01657       CallSite CS = CallSite::get(cast<Instruction>(*UI));
01658       if (CS.hasArgument(GV))
01659         return true;
01660     } else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
01661       if (LI->isVolatile())
01662         return true;
01663     } else {
01664       return true;
01665     }
01666   return false;
01667 }
01668 
01669 bool IPSCCP::runOnModule(Module &M) {
01670   LLVMContext *Context = &M.getContext();
01671   
01672   SCCPSolver Solver;
01673   Solver.setContext(Context);
01674 
01675   // Loop over all functions, marking arguments to those with their addresses
01676   // taken or that are external as overdefined.
01677   //
01678   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
01679     if (!F->hasLocalLinkage() || AddressIsTaken(F)) {
01680       if (!F->isDeclaration())
01681         Solver.MarkBlockExecutable(F->begin());
01682       for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
01683            AI != E; ++AI)
01684         Solver.markOverdefined(AI);
01685     } else {
01686       Solver.AddTrackedFunction(F);
01687     }
01688 
01689   // Loop over global variables.  We inform the solver about any internal global
01690   // variables that do not have their 'addresses taken'.  If they don't have
01691   // their addresses taken, we can propagate constants through them.
01692   for (Module::global_iterator G = M.global_begin(), E = M.global_end();
01693        G != E; ++G)
01694     if (!G->isConstant() && G->hasLocalLinkage() && !AddressIsTaken(G))
01695       Solver.TrackValueOfGlobalVariable(G);
01696 
01697   // Solve for constants.
01698   bool ResolvedUndefs = true;
01699   while (ResolvedUndefs) {
01700     Solver.Solve();
01701 
01702     DEBUG(errs() << "RESOLVING UNDEFS\n");
01703     ResolvedUndefs = false;
01704     for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
01705       ResolvedUndefs |= Solver.ResolvedUndefsIn(*F);
01706   }
01707 
01708   bool MadeChanges = false;
01709 
01710   // Iterate over all of the instructions in the module, replacing them with
01711   // constants if we have found them to be of constant values.
01712   //
01713   SmallVector<Instruction*, 512> Insts;
01714   SmallVector<BasicBlock*, 512> BlocksToErase;
01715   std::map<Value*, LatticeVal> &Values = Solver.getValueMapping();
01716 
01717   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
01718     for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
01719          AI != E; ++AI)
01720       if (!AI->use_empty()) {
01721         LatticeVal &IV = Values[AI];
01722         if (IV.isConstant() || IV.isUndefined()) {
01723           Constant *CST = IV.isConstant() ?
01724             IV.getConstant() : UndefValue::get(AI->getType());
01725           DEBUG(errs() << "***  Arg " << *AI << " = " << *CST <<"\n");
01726 
01727           // Replaces all of the uses of a variable with uses of the
01728           // constant.
01729           AI->replaceAllUsesWith(CST);
01730           ++IPNumArgsElimed;
01731         }
01732       }
01733 
01734     for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
01735       if (!Solver.isBlockExecutable(BB)) {
01736         DEBUG(errs() << "  BasicBlock Dead:" << *BB);
01737         ++IPNumDeadBlocks;
01738 
01739         // Delete the instructions backwards, as it has a reduced likelihood of
01740         // having to update as many def-use and use-def chains.
01741         TerminatorInst *TI = BB->getTerminator();
01742         for (BasicBlock::iterator I = BB->begin(), E = TI; I != E; ++I)
01743           Insts.push_back(I);
01744 
01745         while (!Insts.empty()) {
01746           Instruction *I = Insts.back();
01747           Insts.pop_back();
01748           if (!I->use_empty())
01749             I->replaceAllUsesWith(UndefValue::get(I->getType()));
01750           BB->getInstList().erase(I);
01751           MadeChanges = true;
01752           ++IPNumInstRemoved;
01753         }
01754 
01755         for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
01756           BasicBlock *Succ = TI->getSuccessor(i);
01757           if (!Succ->empty() && isa<PHINode>(Succ->begin()))
01758             TI->getSuccessor(i)->removePredecessor(BB);
01759         }
01760         if (!TI->use_empty())
01761           TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
01762         BB->getInstList().erase(TI);
01763 
01764         if (&*BB != &F->front())
01765           BlocksToErase.push_back(BB);
01766         else
01767           new UnreachableInst(M.getContext(), BB);
01768 
01769       } else {
01770         for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
01771           Instruction *Inst = BI++;
01772           if (Inst->getType() == Type::getVoidTy(M.getContext()))
01773             continue;
01774           
01775           LatticeVal &IV = Values[Inst];
01776           if (!IV.isConstant() && !IV.isUndefined())
01777             continue;
01778           
01779           Constant *Const = IV.isConstant()
01780             ? IV.getConstant() : UndefValue::get(Inst->getType());
01781           DEBUG(errs() << "  Constant: " << *Const << " = " << *Inst);
01782 
01783           // Replaces all of the uses of a variable with uses of the
01784           // constant.
01785           Inst->replaceAllUsesWith(Const);
01786           
01787           // Delete the instruction.
01788           if (!isa<CallInst>(Inst) && !isa<TerminatorInst>(Inst))
01789             Inst->eraseFromParent();
01790 
01791           // Hey, we just changed something!
01792           MadeChanges = true;
01793           ++IPNumInstRemoved;
01794         }
01795       }
01796 
01797     // Now that all instructions in the function are constant folded, erase dead
01798     // blocks, because we can now use ConstantFoldTerminator to get rid of
01799     // in-edges.
01800     for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) {
01801       // If there are any PHI nodes in this successor, drop entries for BB now.
01802       BasicBlock *DeadBB = BlocksToErase[i];
01803       while (!DeadBB->use_empty()) {
01804         Instruction *I = cast<Instruction>(DeadBB->use_back());
01805         bool Folded = ConstantFoldTerminator(I->getParent());
01806         if (!Folded) {
01807           // The constant folder may not have been able to fold the terminator
01808           // if this is a branch or switch on undef.  Fold it manually as a
01809           // branch to the first successor.
01810 #ifndef NDEBUG
01811           if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
01812             assert(BI->isConditional() && isa<UndefValue>(BI->getCondition()) &&
01813                    "Branch should be foldable!");
01814           } else if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
01815             assert(isa<UndefValue>(SI->getCondition()) && "Switch should fold");
01816           } else {
01817             llvm_unreachable("Didn't fold away reference to block!");
01818           }
01819 #endif
01820           
01821           // Make this an uncond branch to the first successor.
01822           TerminatorInst *TI = I->getParent()->getTerminator();
01823           BranchInst::Create(TI->getSuccessor(0), TI);
01824           
01825           // Remove entries in successor phi nodes to remove edges.
01826           for (unsigned i = 1, e = TI->getNumSuccessors(); i != e; ++i)
01827             TI->getSuccessor(i)->removePredecessor(TI->getParent());
01828           
01829           // Remove the old terminator.
01830           TI->eraseFromParent();
01831         }
01832       }
01833 
01834       // Finally, delete the basic block.
01835       F->getBasicBlockList().erase(DeadBB);
01836     }
01837     BlocksToErase.clear();
01838   }
01839 
01840   // If we inferred constant or undef return values for a function, we replaced
01841   // all call uses with the inferred value.  This means we don't need to bother
01842   // actually returning anything from the function.  Replace all return
01843   // instructions with return undef.
01844   // TODO: Process multiple value ret instructions also.
01845   const DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals();
01846   for (DenseMap<Function*, LatticeVal>::const_iterator I = RV.begin(),
01847          E = RV.end(); I != E; ++I)
01848     if (!I->second.isOverdefined() &&
01849         I->first->getReturnType() != Type::getVoidTy(M.getContext())) {
01850       Function *F = I->first;
01851       for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
01852         if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
01853           if (!isa<UndefValue>(RI->getOperand(0)))
01854             RI->setOperand(0, UndefValue::get(F->getReturnType()));
01855     }
01856 
01857   // If we infered constant or undef values for globals variables, we can delete
01858   // the global and any stores that remain to it.
01859   const DenseMap<GlobalVariable*, LatticeVal> &TG = Solver.getTrackedGlobals();
01860   for (DenseMap<GlobalVariable*, LatticeVal>::const_iterator I = TG.begin(),
01861          E = TG.end(); I != E; ++I) {
01862     GlobalVariable *GV = I->first;
01863     assert(!I->second.isOverdefined() &&
01864            "Overdefined values should have been taken out of the map!");
01865     DEBUG(errs() << "Found that GV '" << GV->getName() << "' is constant!\n");
01866     while (!GV->use_empty()) {
01867       StoreInst *SI = cast<StoreInst>(GV->use_back());
01868       SI->eraseFromParent();
01869     }
01870     M.getGlobalList().erase(GV);
01871     ++IPNumGlobalConst;
01872   }
01873 
01874   return MadeChanges;
01875 }