X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FSCCP.cpp;h=8d0b86606a8a3d42ef11c0f0943a8d5deb378dbc;hb=c10fa6c801e48771b5eade50afc2fe6abaf08227;hp=4701d2f740564217f3f7a29686d1ff8765fdd892;hpb=f006b183e2d2bebcf6968d1dd7350397c95b0325;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp index 4701d2f7405..8d0b86606a8 100644 --- a/lib/Transforms/Scalar/SCCP.cpp +++ b/lib/Transforms/Scalar/SCCP.cpp @@ -15,10 +15,6 @@ // * Proves values to be constant, and replaces them with constants // * Proves conditional branches to be unconditional // -// Notice that: -// * This pass has a habit of making definitions be dead. It is a good idea -// to to run a DCE pass sometime after running this pass. -// //===----------------------------------------------------------------------===// #define DEBUG_TYPE "sccp" @@ -27,12 +23,11 @@ #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" #include "llvm/Instructions.h" -#include "llvm/LLVMContext.h" #include "llvm/Pass.h" #include "llvm/Analysis/ConstantFolding.h" -#include "llvm/Analysis/MemoryBuiltins.h" -#include "llvm/Analysis/ValueTracking.h" #include "llvm/Transforms/Utils/Local.h" +#include "llvm/Target/TargetData.h" +#include "llvm/Target/TargetLibraryInfo.h" #include "llvm/Support/CallSite.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" @@ -40,19 +35,17 @@ #include "llvm/Support/raw_ostream.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" -#include "llvm/ADT/STLExtras.h" #include -#include using namespace llvm; STATISTIC(NumInstRemoved, "Number of instructions removed"); STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable"); STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP"); -STATISTIC(IPNumDeadBlocks , "Number of basic blocks unreachable by IPSCCP"); STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP"); STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP"); @@ -61,10 +54,10 @@ namespace { /// an LLVM value may occupy. It is a simple class with value semantics. /// class LatticeVal { - enum { + enum LatticeValueTy { /// undefined - This LLVM Value has no known value yet. undefined, - + /// constant - This LLVM Value has a specific constant value. constant, @@ -73,67 +66,86 @@ class LatticeVal { /// with another (different) constant, it goes to overdefined, instead of /// asserting. forcedconstant, - + /// overdefined - This instruction is not known to be constant, and we know /// it has a value. overdefined - } LatticeValue; // The current lattice position - - Constant *ConstantVal; // If Constant value, the current value + }; + + /// Val: This stores the current lattice value along with the Constant* for + /// the constant if this is a 'constant' or 'forcedconstant' value. + PointerIntPair Val; + + LatticeValueTy getLatticeValue() const { + return Val.getInt(); + } + public: - inline LatticeVal() : LatticeValue(undefined), ConstantVal(0) {} - - // markOverdefined - Return true if this is a new status to be in... - inline bool markOverdefined() { - if (LatticeValue != overdefined) { - LatticeValue = overdefined; - return true; - } - return false; + LatticeVal() : Val(0, undefined) {} + + bool isUndefined() const { return getLatticeValue() == undefined; } + bool isConstant() const { + return getLatticeValue() == constant || getLatticeValue() == forcedconstant; } + bool isOverdefined() const { return getLatticeValue() == overdefined; } - // markConstant - Return true if this is a new status for us. - inline bool markConstant(Constant *V) { - if (LatticeValue != constant) { - if (LatticeValue == undefined) { - LatticeValue = constant; - assert(V && "Marking constant with NULL"); - ConstantVal = V; - } else { - assert(LatticeValue == forcedconstant && - "Cannot move from overdefined to constant!"); - // Stay at forcedconstant if the constant is the same. - if (V == ConstantVal) return false; - - // Otherwise, we go to overdefined. Assumptions made based on the - // forced value are possibly wrong. Assuming this is another constant - // could expose a contradiction. - LatticeValue = overdefined; - } - return true; + Constant *getConstant() const { + assert(isConstant() && "Cannot get the constant of a non-constant!"); + return Val.getPointer(); + } + + /// markOverdefined - Return true if this is a change in status. + bool markOverdefined() { + if (isOverdefined()) + return false; + + Val.setInt(overdefined); + return true; + } + + /// markConstant - Return true if this is a change in status. + bool markConstant(Constant *V) { + if (getLatticeValue() == constant) { // Constant but not forcedconstant. + assert(getConstant() == V && "Marking constant with different value"); + return false; + } + + if (isUndefined()) { + Val.setInt(constant); + assert(V && "Marking constant with NULL"); + Val.setPointer(V); } else { - assert(ConstantVal == V && "Marking constant with different value"); + assert(getLatticeValue() == forcedconstant && + "Cannot move from overdefined to constant!"); + // Stay at forcedconstant if the constant is the same. + if (V == getConstant()) return false; + + // Otherwise, we go to overdefined. Assumptions made based on the + // forced value are possibly wrong. Assuming this is another constant + // could expose a contradiction. + Val.setInt(overdefined); } - return false; + return true; } - inline void markForcedConstant(Constant *V) { - assert(LatticeValue == undefined && "Can't force a defined value!"); - LatticeValue = forcedconstant; - ConstantVal = V; - } - - inline bool isUndefined() const { return LatticeValue == undefined; } - inline bool isConstant() const { - return LatticeValue == constant || LatticeValue == forcedconstant; + /// getConstantInt - If this is a constant with a ConstantInt value, return it + /// otherwise return null. + ConstantInt *getConstantInt() const { + if (isConstant()) + return dyn_cast(getConstant()); + return 0; } - inline bool isOverdefined() const { return LatticeValue == overdefined; } - inline Constant *getConstant() const { - assert(isConstant() && "Cannot get the constant of a non-constant!"); - return ConstantVal; + void markForcedConstant(Constant *V) { + assert(isUndefined() && "Can't force a defined value!"); + Val.setInt(forcedconstant); + Val.setPointer(V); } }; +} // end anonymous namespace. + + +namespace { //===----------------------------------------------------------------------===// // @@ -141,9 +153,15 @@ public: /// Constant Propagation. /// class SCCPSolver : public InstVisitor { - LLVMContext *Context; - DenseSet BBExecutable;// The basic blocks that are executable - std::map ValueState; // The state each value is in. + const TargetData *TD; + const TargetLibraryInfo *TLI; + SmallPtrSet BBExecutable; // The BBs that are executable. + DenseMap ValueState; // The state each value is in. + + /// StructValueState - This maintains ValueState for values that have + /// StructType, for example for formal arguments, calls, insertelement, etc. + /// + DenseMap, LatticeVal> StructValueState; /// GlobalValue - If we are tracking any values for the contents of a global /// variable, we keep a mapping from the constant accessor to the element of @@ -160,35 +178,45 @@ class SCCPSolver : public InstVisitor { /// that return multiple values. DenseMap, LatticeVal> TrackedMultipleRetVals; - // The reason for two worklists is that overdefined is the lowest state - // on the lattice, and moving things to overdefined as fast as possible - // makes SCCP converge much faster. - // By having a separate worklist, we accomplish this because everything - // possibly overdefined will become overdefined at the soonest possible - // point. + /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is + /// represented here for efficient lookup. + SmallPtrSet MRVFunctionsTracked; + + /// TrackingIncomingArguments - This is the set of functions for whose + /// arguments we make optimistic assumptions about and try to prove as + /// constants. + SmallPtrSet TrackingIncomingArguments; + + /// The reason for two worklists is that overdefined is the lowest state + /// on the lattice, and moving things to overdefined as fast as possible + /// makes SCCP converge much faster. + /// + /// By having a separate worklist, we accomplish this because everything + /// possibly overdefined will become overdefined at the soonest possible + /// point. SmallVector OverdefinedInstWorkList; SmallVector InstWorkList; SmallVector BBWorkList; // The BasicBlock work list - /// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not - /// overdefined, despite the fact that the PHI node is overdefined. - std::multimap UsersOfOverdefinedPHIs; - /// KnownFeasibleEdges - Entries in this set are edges which have already had /// PHI nodes retriggered. typedef std::pair Edge; DenseSet KnownFeasibleEdges; public: - void setContext(LLVMContext *C) { Context = C; } + SCCPSolver(const TargetData *td, const TargetLibraryInfo *tli) + : TD(td), TLI(tli) {} /// MarkBlockExecutable - This method can be used by clients to mark all of /// the blocks that are known to be intrinsically live in the processed unit. - void MarkBlockExecutable(BasicBlock *BB) { - DEBUG(errs() << "Marking Block Executable: " << BB->getName() << "\n"); - BBExecutable.insert(BB); // Basic block is executable! + /// + /// This returns true if the block was not considered live before. + bool MarkBlockExecutable(BasicBlock *BB) { + if (!BBExecutable.insert(BB)) return false; + DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n"); BBWorkList.push_back(BB); // Add the block to the work list! + return true; } /// TrackValueOfGlobalVariable - Clients can use this method to @@ -196,8 +224,8 @@ public: /// specified global variable if it can. This is only legal to call if /// performing Interprocedural SCCP. void TrackValueOfGlobalVariable(GlobalVariable *GV) { - const Type *ElTy = GV->getType()->getElementType(); - if (ElTy->isFirstClassType()) { + // We only track the contents of scalar globals. + if (GV->getType()->getElementType()->isSingleValueType()) { LatticeVal &IV = TrackedGlobals[GV]; if (!isa(GV->getInitializer())) IV.markConstant(GV->getInitializer()); @@ -208,9 +236,9 @@ public: /// and out of the specified function (which cannot have its address taken), /// this method must be called. void AddTrackedFunction(Function *F) { - assert(F->hasLocalLinkage() && "Can only track internal functions!"); // Add an entry, F -> undef. - if (const StructType *STy = dyn_cast(F->getReturnType())) { + if (StructType *STy = dyn_cast(F->getReturnType())) { + MRVFunctionsTracked.insert(F); for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) TrackedMultipleRetVals.insert(std::make_pair(std::make_pair(F, i), LatticeVal())); @@ -218,6 +246,10 @@ public: TrackedRetVals.insert(std::make_pair(F, LatticeVal())); } + void AddArgumentTrackedFunction(Function *F) { + TrackingIncomingArguments.insert(F); + } + /// Solve - Solve for constants and executable blocks. /// void Solve(); @@ -233,12 +265,19 @@ public: return BBExecutable.count(BB); } - /// getValueMapping - Once we have solved for constants, return the mapping of - /// LLVM values to LatticeVals. - std::map &getValueMapping() { - return ValueState; + LatticeVal getLatticeValueFor(Value *V) const { + DenseMap::const_iterator I = ValueState.find(V); + assert(I != ValueState.end() && "V is not in valuemap!"); + return I->second; } + /*LatticeVal getStructLatticeValueFor(Value *V, unsigned i) const { + DenseMap, LatticeVal>::const_iterator I = + StructValueState.find(std::make_pair(V, i)); + assert(I != StructValueState.end() && "V is not in valuemap!"); + return I->second; + }*/ + /// getTrackedRetVals - Get the inferred return value map. /// const DenseMap &getTrackedRetVals() { @@ -251,48 +290,68 @@ public: return TrackedGlobals; } - inline void markOverdefined(Value *V) { + void markOverdefined(Value *V) { + assert(!V->getType()->isStructTy() && "Should use other method"); markOverdefined(ValueState[V], V); } + /// markAnythingOverdefined - Mark the specified value overdefined. This + /// works with both scalars and structs. + void markAnythingOverdefined(Value *V) { + if (StructType *STy = dyn_cast(V->getType())) + for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) + markOverdefined(getStructValueState(V, i), V); + else + markOverdefined(V); + } + private: // markConstant - Make a value be marked as "constant". If the value // is not already a constant, add it to the instruction work list so that // the users of the instruction are updated later. // - inline void markConstant(LatticeVal &IV, Value *V, Constant *C) { - if (IV.markConstant(C)) { - DEBUG(errs() << "markConstant: " << *C << ": " << *V << '\n'); + void markConstant(LatticeVal &IV, Value *V, Constant *C) { + if (!IV.markConstant(C)) return; + DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n'); + if (IV.isOverdefined()) + OverdefinedInstWorkList.push_back(V); + else InstWorkList.push_back(V); - } - } - - inline void markForcedConstant(LatticeVal &IV, Value *V, Constant *C) { - IV.markForcedConstant(C); - DEBUG(errs() << "markForcedConstant: " << *C << ": " << *V << '\n'); - InstWorkList.push_back(V); } - - inline void markConstant(Value *V, Constant *C) { + + void markConstant(Value *V, Constant *C) { + assert(!V->getType()->isStructTy() && "Should use other method"); markConstant(ValueState[V], V, C); } + void markForcedConstant(Value *V, Constant *C) { + assert(!V->getType()->isStructTy() && "Should use other method"); + LatticeVal &IV = ValueState[V]; + IV.markForcedConstant(C); + DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n'); + if (IV.isOverdefined()) + OverdefinedInstWorkList.push_back(V); + else + InstWorkList.push_back(V); + } + + // markOverdefined - Make a value be marked as "overdefined". If the // value is not already overdefined, add it to the overdefined instruction // work list so that the users of the instruction are updated later. - inline void markOverdefined(LatticeVal &IV, Value *V) { - if (IV.markOverdefined()) { - DEBUG(errs() << "markOverdefined: "; - if (Function *F = dyn_cast(V)) - errs() << "Function '" << F->getName() << "'\n"; - else - errs() << *V << '\n'); - // Only instructions go on the work list - OverdefinedInstWorkList.push_back(V); - } + void markOverdefined(LatticeVal &IV, Value *V) { + if (!IV.markOverdefined()) return; + + DEBUG(dbgs() << "markOverdefined: "; + if (Function *F = dyn_cast(V)) + dbgs() << "Function '" << F->getName() << "'\n"; + else + dbgs() << *V << '\n'); + // Only instructions go on the work list + OverdefinedInstWorkList.push_back(V); } - inline void mergeInValue(LatticeVal &IV, Value *V, LatticeVal &MergeWithV) { + void mergeInValue(LatticeVal &IV, Value *V, LatticeVal MergeWithV) { if (IV.isOverdefined() || MergeWithV.isUndefined()) return; // Noop. if (MergeWithV.isOverdefined()) @@ -302,54 +361,85 @@ private: else if (IV.getConstant() != MergeWithV.getConstant()) markOverdefined(IV, V); } - - inline void mergeInValue(Value *V, LatticeVal &MergeWithV) { - return mergeInValue(ValueState[V], V, MergeWithV); + + void mergeInValue(Value *V, LatticeVal MergeWithV) { + assert(!V->getType()->isStructTy() && "Should use other method"); + mergeInValue(ValueState[V], V, MergeWithV); } - // getValueState - Return the LatticeVal object that corresponds to the value. - // This function is necessary because not all values should start out in the - // underdefined state... Argument's should be overdefined, and - // constants should be marked as constants. If a value is not known to be an - // Instruction object, then use this accessor to get its value from the map. - // - inline LatticeVal &getValueState(Value *V) { - std::map::iterator I = ValueState.find(V); - if (I != ValueState.end()) return I->second; // Common case, in the map + /// getValueState - Return the LatticeVal object that corresponds to the + /// value. This function handles the case when the value hasn't been seen yet + /// by properly seeding constants etc. + LatticeVal &getValueState(Value *V) { + assert(!V->getType()->isStructTy() && "Should use getStructValueState"); + + std::pair::iterator, bool> I = + ValueState.insert(std::make_pair(V, LatticeVal())); + LatticeVal &LV = I.first->second; + + if (!I.second) + return LV; // Common case, already in the map. if (Constant *C = dyn_cast(V)) { - if (isa(V)) { - // Nothing to do, remain undefined. - } else { - LatticeVal &LV = ValueState[C]; + // Undef values remain undefined. + if (!isa(V)) LV.markConstant(C); // Constants are constant - return LV; - } } - // All others are underdefined by default... - return ValueState[V]; + + // All others are underdefined by default. + return LV; } - // markEdgeExecutable - Mark a basic block as executable, adding it to the BB - // work list if it is not already executable... - // + /// getStructValueState - Return the LatticeVal object that corresponds to the + /// value/field pair. This function handles the case when the value hasn't + /// been seen yet by properly seeding constants etc. + LatticeVal &getStructValueState(Value *V, unsigned i) { + assert(V->getType()->isStructTy() && "Should use getValueState"); + assert(i < cast(V->getType())->getNumElements() && + "Invalid element #"); + + std::pair, LatticeVal>::iterator, + bool> I = StructValueState.insert( + std::make_pair(std::make_pair(V, i), LatticeVal())); + LatticeVal &LV = I.first->second; + + if (!I.second) + return LV; // Common case, already in the map. + + if (Constant *C = dyn_cast(V)) { + Constant *Elt = C->getAggregateElement(i); + + if (Elt == 0) + LV.markOverdefined(); // Unknown sort of constant. + else if (isa(Elt)) + ; // Undef values remain undefined. + else + LV.markConstant(Elt); // Constants are constant. + } + + // All others are underdefined by default. + return LV; + } + + + /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB + /// work list if it is not already executable. void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) return; // This edge is already known to be executable! - if (BBExecutable.count(Dest)) { - DEBUG(errs() << "Marking Edge Executable: " << Source->getName() - << " -> " << Dest->getName() << "\n"); - - // The destination is already executable, but we just made an edge + if (!MarkBlockExecutable(Dest)) { + // If the destination is already executable, we just made an *edge* // feasible that wasn't before. Revisit the PHI nodes in the block // because they have potentially new operands. - for (BasicBlock::iterator I = Dest->begin(); isa(I); ++I) - visitPHINode(*cast(I)); + DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() + << " -> " << Dest->getName() << "\n"); - } else { - MarkBlockExecutable(Dest); + PHINode *PN; + for (BasicBlock::iterator I = Dest->begin(); + (PN = dyn_cast(I)); ++I) + visitPHINode(*PN); } } @@ -359,28 +449,25 @@ private: void getFeasibleSuccessors(TerminatorInst &TI, SmallVector &Succs); // isEdgeFeasible - Return true if the control flow edge from the 'From' basic - // block to the 'To' basic block is currently feasible... + // block to the 'To' basic block is currently feasible. // bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); // OperandChangedState - This method is invoked on all of the users of an - // instruction that was just changed state somehow.... Based on this + // instruction that was just changed state somehow. Based on this // information, we need to update the specified user of this instruction. // - void OperandChangedState(User *U) { - // Only instructions use other variable values! - Instruction &I = cast(*U); - if (BBExecutable.count(I.getParent())) // Inst is executable? - visit(I); + void OperandChangedState(Instruction *I) { + if (BBExecutable.count(I->getParent())) // Inst is executable? + visit(*I); } private: friend class InstVisitor; - // visit implementations - Something changed in this instruction... Either an + // visit implementations - Something changed in this instruction. Either an // operand made a transition, or the instruction is newly executable. Change // the value type of I to reflect these changes if appropriate. - // void visitPHINode(PHINode &I); // Terminators @@ -396,31 +483,33 @@ private: void visitShuffleVectorInst(ShuffleVectorInst &I); void visitExtractValueInst(ExtractValueInst &EVI); void visitInsertValueInst(InsertValueInst &IVI); + void visitLandingPadInst(LandingPadInst &I) { markAnythingOverdefined(&I); } - // Instructions that cannot be folded away... - void visitStoreInst (Instruction &I); + // Instructions that cannot be folded away. + void visitStoreInst (StoreInst &I); void visitLoadInst (LoadInst &I); void visitGetElementPtrInst(GetElementPtrInst &I); void visitCallInst (CallInst &I) { - if (isFreeCall(&I)) - return; - visitCallSite(CallSite::get(&I)); + visitCallSite(&I); } void visitInvokeInst (InvokeInst &II) { - visitCallSite(CallSite::get(&II)); + visitCallSite(&II); visitTerminatorInst(II); } void visitCallSite (CallSite CS); + void visitResumeInst (TerminatorInst &I) { /*returns void*/ } void visitUnwindInst (TerminatorInst &I) { /*returns void*/ } void visitUnreachableInst(TerminatorInst &I) { /*returns void*/ } + void visitFenceInst (FenceInst &I) { /*returns void*/ } + void visitAtomicCmpXchgInst (AtomicCmpXchgInst &I) { markOverdefined(&I); } + void visitAtomicRMWInst (AtomicRMWInst &I) { markOverdefined(&I); } void visitAllocaInst (Instruction &I) { markOverdefined(&I); } - void visitVANextInst (Instruction &I) { markOverdefined(&I); } - void visitVAArgInst (Instruction &I) { markOverdefined(&I); } + void visitVAArgInst (Instruction &I) { markAnythingOverdefined(&I); } void visitInstruction(Instruction &I) { - // If a new instruction is added to LLVM that we don't handle... - errs() << "SCCP: Don't know how to handle: " << I; - markOverdefined(&I); // Just in case + // If a new instruction is added to LLVM that we don't handle. + dbgs() << "SCCP: Don't know how to handle: " << I; + markAnythingOverdefined(&I); // Just in case } }; @@ -436,37 +525,65 @@ void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, if (BranchInst *BI = dyn_cast(&TI)) { if (BI->isUnconditional()) { Succs[0] = true; - } else { - LatticeVal &BCValue = getValueState(BI->getCondition()); - if (BCValue.isOverdefined() || - (BCValue.isConstant() && !isa(BCValue.getConstant()))) { - // Overdefined condition variables, and branches on unfoldable constant - // conditions, mean the branch could go either way. + return; + } + + LatticeVal BCValue = getValueState(BI->getCondition()); + ConstantInt *CI = BCValue.getConstantInt(); + if (CI == 0) { + // Overdefined condition variables, and branches on unfoldable constant + // conditions, mean the branch could go either way. + if (!BCValue.isUndefined()) Succs[0] = Succs[1] = true; - } else if (BCValue.isConstant()) { - // Constant condition variables mean the branch can only go a single way - Succs[BCValue.getConstant() == ConstantInt::getFalse(*Context)] = true; - } + return; } - } else if (isa(&TI)) { + + // Constant condition variables mean the branch can only go a single way. + Succs[CI->isZero()] = true; + return; + } + + if (isa(TI)) { // Invoke instructions successors are always executable. Succs[0] = Succs[1] = true; - } else if (SwitchInst *SI = dyn_cast(&TI)) { - LatticeVal &SCValue = getValueState(SI->getCondition()); - if (SCValue.isOverdefined() || // Overdefined condition? - (SCValue.isConstant() && !isa(SCValue.getConstant()))) { + return; + } + + if (SwitchInst *SI = dyn_cast(&TI)) { + if (!SI->getNumCases()) { + Succs[0] = true; + return; + } + LatticeVal SCValue = getValueState(SI->getCondition()); + ConstantInt *CI = SCValue.getConstantInt(); + + if (CI == 0) { // Overdefined or undefined condition? // All destinations are executable! - Succs.assign(TI.getNumSuccessors(), true); - } else if (SCValue.isConstant()) - Succs[SI->findCaseValue(cast(SCValue.getConstant()))] = true; - } else { - llvm_unreachable("SCCP: Don't know how to handle this terminator!"); + if (!SCValue.isUndefined()) + Succs.assign(TI.getNumSuccessors(), true); + return; + } + + Succs[SI->findCaseValue(CI).getSuccessorIndex()] = true; + return; } + + // TODO: This could be improved if the operand is a [cast of a] BlockAddress. + if (isa(&TI)) { + // Just mark all destinations executable! + Succs.assign(TI.getNumSuccessors(), true); + return; + } + +#ifndef NDEBUG + dbgs() << "Unknown terminator instruction: " << TI << '\n'; +#endif + llvm_unreachable("SCCP: Don't know how to handle this terminator!"); } // isEdgeFeasible - Return true if the control flow edge from the 'From' basic -// block to the 'To' basic block is currently feasible... +// block to the 'To' basic block is currently feasible. // bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { assert(BBExecutable.count(To) && "Dest should always be alive!"); @@ -474,58 +591,53 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { // Make sure the source basic block is executable!! if (!BBExecutable.count(From)) return false; - // Check to make sure this edge itself is actually feasible now... + // Check to make sure this edge itself is actually feasible now. TerminatorInst *TI = From->getTerminator(); if (BranchInst *BI = dyn_cast(TI)) { if (BI->isUnconditional()) return true; - else { - LatticeVal &BCValue = getValueState(BI->getCondition()); - if (BCValue.isOverdefined()) { - // Overdefined condition variables mean the branch could go either way. - return true; - } else if (BCValue.isConstant()) { - // Not branching on an evaluatable constant? - if (!isa(BCValue.getConstant())) return true; - // Constant condition variables mean the branch can only go a single way - return BI->getSuccessor(BCValue.getConstant() == - ConstantInt::getFalse(*Context)) == To; - } - return false; - } - } else if (isa(TI)) { - // Invoke instructions successors are always executable. + LatticeVal BCValue = getValueState(BI->getCondition()); + + // Overdefined condition variables mean the branch could go either way, + // undef conditions mean that neither edge is feasible yet. + ConstantInt *CI = BCValue.getConstantInt(); + if (CI == 0) + return !BCValue.isUndefined(); + + // Constant condition variables mean the branch can only go a single way. + return BI->getSuccessor(CI->isZero()) == To; + } + + // Invoke instructions successors are always executable. + if (isa(TI)) return true; - } else if (SwitchInst *SI = dyn_cast(TI)) { - LatticeVal &SCValue = getValueState(SI->getCondition()); - if (SCValue.isOverdefined()) { // Overdefined condition? - // All destinations are executable! + + if (SwitchInst *SI = dyn_cast(TI)) { + if (SI->getNumCases() < 1) return true; - } else if (SCValue.isConstant()) { - Constant *CPV = SCValue.getConstant(); - if (!isa(CPV)) - return true; // not a foldable constant? - - // Make sure to skip the "default value" which isn't a value - for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) - if (SI->getSuccessorValue(i) == CPV) // Found the taken branch... - return SI->getSuccessor(i) == To; - - // Constant value not equal to any of the branches... must execute - // default branch then... - return SI->getDefaultDest() == To; - } - return false; - } else { + + LatticeVal SCValue = getValueState(SI->getCondition()); + ConstantInt *CI = SCValue.getConstantInt(); + + if (CI == 0) + return !SCValue.isUndefined(); + + return SI->findCaseValue(CI).getCaseSuccessor() == To; + } + + // Just mark all destinations executable! + // TODO: This could be improved if the operand is a [cast of a] BlockAddress. + if (isa(TI)) + return true; + #ifndef NDEBUG - errs() << "Unknown terminator instruction: " << *TI << '\n'; + dbgs() << "Unknown terminator instruction: " << *TI << '\n'; #endif - llvm_unreachable(0); - } + llvm_unreachable(0); } -// visit Implementations - Something changed in this instruction... Either an +// visit Implementations - Something changed in this instruction, either an // operand made a transition, or the instruction is newly executable. Change // the value type of I to reflect these changes if appropriate. This method // makes sure to do the following actions: @@ -544,30 +656,18 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { // successors executable. // void SCCPSolver::visitPHINode(PHINode &PN) { - LatticeVal &PNIV = getValueState(&PN); - if (PNIV.isOverdefined()) { - // There may be instructions using this PHI node that are not overdefined - // themselves. If so, make sure that they know that the PHI node operand - // changed. - std::multimap::iterator I, E; - tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN); - if (I != E) { - SmallVector Users; - for (; I != E; ++I) Users.push_back(I->second); - while (!Users.empty()) { - visit(Users.back()); - Users.pop_back(); - } - } + // If this PN returns a struct, just mark the result overdefined. + // TODO: We could do a lot better than this if code actually uses this. + if (PN.getType()->isStructTy()) + return markAnythingOverdefined(&PN); + + if (getValueState(&PN).isOverdefined()) return; // Quick exit - } // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant, // and slow us down a lot. Just mark them overdefined. - if (PN.getNumIncomingValues() > 64) { - markOverdefined(PNIV, &PN); - return; - } + if (PN.getNumIncomingValues() > 64) + return markOverdefined(&PN); // Look at all of the executable operands of the PHI node. If any of them // are overdefined, the PHI becomes overdefined as well. If they are all @@ -577,32 +677,28 @@ void SCCPSolver::visitPHINode(PHINode &PN) { // Constant *OperandVal = 0; for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { - LatticeVal &IV = getValueState(PN.getIncomingValue(i)); + LatticeVal IV = getValueState(PN.getIncomingValue(i)); if (IV.isUndefined()) continue; // Doesn't influence PHI node. - if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) { - if (IV.isOverdefined()) { // PHI node becomes overdefined! - markOverdefined(&PN); - return; - } + if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) + continue; - if (OperandVal == 0) { // Grab the first value... - OperandVal = IV.getConstant(); - } else { // Another value is being merged in! - // There is already a reachable operand. If we conflict with it, - // then the PHI node becomes overdefined. If we agree with it, we - // can continue on. - - // Check to see if there are two different constants merging... - if (IV.getConstant() != OperandVal) { - // Yes there is. This means the PHI node is not constant. - // You must be overdefined poor PHI. - // - markOverdefined(&PN); // The PHI node now becomes overdefined - return; // I'm done analyzing you - } - } + if (IV.isOverdefined()) // PHI node becomes overdefined! + return markOverdefined(&PN); + + if (OperandVal == 0) { // Grab the first value. + OperandVal = IV.getConstant(); + continue; } + + // There is already a reachable operand. If we conflict with it, + // then the PHI node becomes overdefined. If we agree with it, we + // can continue on. + + // Check to see if there are two different constants merging, if so, the PHI + // node is overdefined. + if (IV.getConstant() != OperandVal) + return markOverdefined(&PN); } // If we exited the loop, this means that the PHI node only has constant @@ -614,44 +710,33 @@ void SCCPSolver::visitPHINode(PHINode &PN) { markConstant(&PN, OperandVal); // Acquire operand value } + + + void SCCPSolver::visitReturnInst(ReturnInst &I) { - if (I.getNumOperands() == 0) return; // Ret void + if (I.getNumOperands() == 0) return; // ret void Function *F = I.getParent()->getParent(); - // If we are tracking the return value of this function, merge it in. - if (!F->hasLocalLinkage()) - return; + Value *ResultOp = I.getOperand(0); - if (!TrackedRetVals.empty() && I.getNumOperands() == 1) { + // If we are tracking the return value of this function, merge it in. + if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) { DenseMap::iterator TFRVI = TrackedRetVals.find(F); - if (TFRVI != TrackedRetVals.end() && - !TFRVI->second.isOverdefined()) { - LatticeVal &IV = getValueState(I.getOperand(0)); - mergeInValue(TFRVI->second, F, IV); + if (TFRVI != TrackedRetVals.end()) { + mergeInValue(TFRVI->second, F, getValueState(ResultOp)); return; } } - + // Handle functions that return multiple values. - if (!TrackedMultipleRetVals.empty() && I.getNumOperands() > 1) { - for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { - DenseMap, LatticeVal>::iterator - It = TrackedMultipleRetVals.find(std::make_pair(F, i)); - if (It == TrackedMultipleRetVals.end()) break; - mergeInValue(It->second, F, getValueState(I.getOperand(i))); - } - } else if (!TrackedMultipleRetVals.empty() && - I.getNumOperands() == 1 && - isa(I.getOperand(0)->getType())) { - for (unsigned i = 0, e = I.getOperand(0)->getType()->getNumContainedTypes(); - i != e; ++i) { - DenseMap, LatticeVal>::iterator - It = TrackedMultipleRetVals.find(std::make_pair(F, i)); - if (It == TrackedMultipleRetVals.end()) break; - if (Value *Val = FindInsertedValue(I.getOperand(0), i, I.getContext())) - mergeInValue(It->second, F, getValueState(Val)); - } + if (!TrackedMultipleRetVals.empty()) { + if (StructType *STy = dyn_cast(ResultOp->getType())) + if (MRVFunctionsTracked.count(F)) + for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) + mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F, + getStructValueState(ResultOp, i)); + } } @@ -661,356 +746,191 @@ void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) { BasicBlock *BB = TI.getParent(); - // Mark all feasible successors executable... + // Mark all feasible successors executable. for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i) if (SuccFeasible[i]) markEdgeExecutable(BB, TI.getSuccessor(i)); } void SCCPSolver::visitCastInst(CastInst &I) { - Value *V = I.getOperand(0); - LatticeVal &VState = getValueState(V); - if (VState.isOverdefined()) // Inherit overdefinedness of operand + LatticeVal OpSt = getValueState(I.getOperand(0)); + if (OpSt.isOverdefined()) // Inherit overdefinedness of operand markOverdefined(&I); - else if (VState.isConstant()) // Propagate constant value - markConstant(&I, ConstantExpr::getCast(I.getOpcode(), - VState.getConstant(), I.getType())); + else if (OpSt.isConstant()) // Propagate constant value + markConstant(&I, ConstantExpr::getCast(I.getOpcode(), + OpSt.getConstant(), I.getType())); } -void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { - Value *Aggr = EVI.getAggregateOperand(); - // If the operand to the extractvalue is an undef, the result is undef. - if (isa(Aggr)) - return; - - // Currently only handle single-index extractvalues. - if (EVI.getNumIndices() != 1) { - markOverdefined(&EVI); - return; - } - - Function *F = 0; - if (CallInst *CI = dyn_cast(Aggr)) - F = CI->getCalledFunction(); - else if (InvokeInst *II = dyn_cast(Aggr)) - F = II->getCalledFunction(); - - // TODO: If IPSCCP resolves the callee of this function, we could propagate a - // result back! - if (F == 0 || TrackedMultipleRetVals.empty()) { - markOverdefined(&EVI); - return; - } - - // See if we are tracking the result of the callee. If not tracking this - // function (for example, it is a declaration) just move to overdefined. - if (!TrackedMultipleRetVals.count(std::make_pair(F, *EVI.idx_begin()))) { - markOverdefined(&EVI); - return; +void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { + // If this returns a struct, mark all elements over defined, we don't track + // structs in structs. + if (EVI.getType()->isStructTy()) + return markAnythingOverdefined(&EVI); + + // If this is extracting from more than one level of struct, we don't know. + if (EVI.getNumIndices() != 1) + return markOverdefined(&EVI); + + Value *AggVal = EVI.getAggregateOperand(); + if (AggVal->getType()->isStructTy()) { + unsigned i = *EVI.idx_begin(); + LatticeVal EltVal = getStructValueState(AggVal, i); + mergeInValue(getValueState(&EVI), &EVI, EltVal); + } else { + // Otherwise, must be extracting from an array. + return markOverdefined(&EVI); } - - // Otherwise, the value will be merged in here as a result of CallSite - // handling. } void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) { - Value *Aggr = IVI.getAggregateOperand(); - Value *Val = IVI.getInsertedValueOperand(); + StructType *STy = dyn_cast(IVI.getType()); + if (STy == 0) + return markOverdefined(&IVI); - // If the operands to the insertvalue are undef, the result is undef. - if (isa(Aggr) && isa(Val)) - return; - - // Currently only handle single-index insertvalues. - if (IVI.getNumIndices() != 1) { - markOverdefined(&IVI); - return; - } + // If this has more than one index, we can't handle it, drive all results to + // undef. + if (IVI.getNumIndices() != 1) + return markAnythingOverdefined(&IVI); - // Currently only handle insertvalue instructions that are in a single-use - // chain that builds up a return value. - for (const InsertValueInst *TmpIVI = &IVI; ; ) { - if (!TmpIVI->hasOneUse()) { - markOverdefined(&IVI); - return; + Value *Aggr = IVI.getAggregateOperand(); + unsigned Idx = *IVI.idx_begin(); + + // Compute the result based on what we're inserting. + for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { + // This passes through all values that aren't the inserted element. + if (i != Idx) { + LatticeVal EltVal = getStructValueState(Aggr, i); + mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal); + continue; } - const Value *V = *TmpIVI->use_begin(); - if (isa(V)) - break; - TmpIVI = dyn_cast(V); - if (!TmpIVI) { - markOverdefined(&IVI); - return; + + Value *Val = IVI.getInsertedValueOperand(); + if (Val->getType()->isStructTy()) + // We don't track structs in structs. + markOverdefined(getStructValueState(&IVI, i), &IVI); + else { + LatticeVal InVal = getValueState(Val); + mergeInValue(getStructValueState(&IVI, i), &IVI, InVal); } } - - // See if we are tracking the result of the callee. - Function *F = IVI.getParent()->getParent(); - DenseMap, LatticeVal>::iterator - It = TrackedMultipleRetVals.find(std::make_pair(F, *IVI.idx_begin())); - - // Merge in the inserted member value. - if (It != TrackedMultipleRetVals.end()) - mergeInValue(It->second, F, getValueState(Val)); - - // Mark the aggregate result of the IVI overdefined; any tracking that we do - // will be done on the individual member values. - markOverdefined(&IVI); } void SCCPSolver::visitSelectInst(SelectInst &I) { - LatticeVal &CondValue = getValueState(I.getCondition()); + // If this select returns a struct, just mark the result overdefined. + // TODO: We could do a lot better than this if code actually uses this. + if (I.getType()->isStructTy()) + return markAnythingOverdefined(&I); + + LatticeVal CondValue = getValueState(I.getCondition()); if (CondValue.isUndefined()) return; - if (CondValue.isConstant()) { - if (ConstantInt *CondCB = dyn_cast(CondValue.getConstant())){ - mergeInValue(&I, getValueState(CondCB->getZExtValue() ? I.getTrueValue() - : I.getFalseValue())); - return; - } + + if (ConstantInt *CondCB = CondValue.getConstantInt()) { + Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue(); + mergeInValue(&I, getValueState(OpVal)); + return; } - + // Otherwise, the condition is overdefined or a constant we can't evaluate. // See if we can produce something better than overdefined based on the T/F // value. - LatticeVal &TVal = getValueState(I.getTrueValue()); - LatticeVal &FVal = getValueState(I.getFalseValue()); - - // select ?, C, C -> C. - if (TVal.isConstant() && FVal.isConstant() && - TVal.getConstant() == FVal.getConstant()) { - markConstant(&I, FVal.getConstant()); - return; - } + LatticeVal TVal = getValueState(I.getTrueValue()); + LatticeVal FVal = getValueState(I.getFalseValue()); - if (TVal.isUndefined()) { // select ?, undef, X -> X. - mergeInValue(&I, FVal); - } else if (FVal.isUndefined()) { // select ?, X, undef -> X. - mergeInValue(&I, TVal); - } else { - markOverdefined(&I); - } + // select ?, C, C -> C. + if (TVal.isConstant() && FVal.isConstant() && + TVal.getConstant() == FVal.getConstant()) + return markConstant(&I, FVal.getConstant()); + + if (TVal.isUndefined()) // select ?, undef, X -> X. + return mergeInValue(&I, FVal); + if (FVal.isUndefined()) // select ?, X, undef -> X. + return mergeInValue(&I, TVal); + markOverdefined(&I); } -// Handle BinaryOperators and Shift Instructions... +// Handle Binary Operators. void SCCPSolver::visitBinaryOperator(Instruction &I) { + LatticeVal V1State = getValueState(I.getOperand(0)); + LatticeVal V2State = getValueState(I.getOperand(1)); + LatticeVal &IV = ValueState[&I]; if (IV.isOverdefined()) return; - LatticeVal &V1State = getValueState(I.getOperand(0)); - LatticeVal &V2State = getValueState(I.getOperand(1)); - - if (V1State.isOverdefined() || V2State.isOverdefined()) { - // If this is an AND or OR with 0 or -1, it doesn't matter that the other - // operand is overdefined. - if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Or) { - LatticeVal *NonOverdefVal = 0; - if (!V1State.isOverdefined()) { - NonOverdefVal = &V1State; - } else if (!V2State.isOverdefined()) { - NonOverdefVal = &V2State; + if (V1State.isConstant() && V2State.isConstant()) + return markConstant(IV, &I, + ConstantExpr::get(I.getOpcode(), V1State.getConstant(), + V2State.getConstant())); + + // If something is undef, wait for it to resolve. + if (!V1State.isOverdefined() && !V2State.isOverdefined()) + return; + + // Otherwise, one of our operands is overdefined. Try to produce something + // better than overdefined with some tricks. + + // If this is an AND or OR with 0 or -1, it doesn't matter that the other + // operand is overdefined. + if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Or) { + LatticeVal *NonOverdefVal = 0; + if (!V1State.isOverdefined()) + NonOverdefVal = &V1State; + else if (!V2State.isOverdefined()) + NonOverdefVal = &V2State; + + if (NonOverdefVal) { + if (NonOverdefVal->isUndefined()) { + // Could annihilate value. + if (I.getOpcode() == Instruction::And) + markConstant(IV, &I, Constant::getNullValue(I.getType())); + else if (VectorType *PT = dyn_cast(I.getType())) + markConstant(IV, &I, Constant::getAllOnesValue(PT)); + else + markConstant(IV, &I, + Constant::getAllOnesValue(I.getType())); + return; } - if (NonOverdefVal) { - if (NonOverdefVal->isUndefined()) { - // Could annihilate value. - if (I.getOpcode() == Instruction::And) - markConstant(IV, &I, Constant::getNullValue(I.getType())); - else if (const VectorType *PT = dyn_cast(I.getType())) - markConstant(IV, &I, Constant::getAllOnesValue(PT)); - else - markConstant(IV, &I, - Constant::getAllOnesValue(I.getType())); - return; - } else { - if (I.getOpcode() == Instruction::And) { - if (NonOverdefVal->getConstant()->isNullValue()) { - markConstant(IV, &I, NonOverdefVal->getConstant()); - return; // X and 0 = 0 - } - } else { - if (ConstantInt *CI = - dyn_cast(NonOverdefVal->getConstant())) - if (CI->isAllOnesValue()) { - markConstant(IV, &I, NonOverdefVal->getConstant()); - return; // X or -1 = -1 - } - } - } + if (I.getOpcode() == Instruction::And) { + // X and 0 = 0 + if (NonOverdefVal->getConstant()->isNullValue()) + return markConstant(IV, &I, NonOverdefVal->getConstant()); + } else { + if (ConstantInt *CI = NonOverdefVal->getConstantInt()) + if (CI->isAllOnesValue()) // X or -1 = -1 + return markConstant(IV, &I, NonOverdefVal->getConstant()); } } + } - // If both operands are PHI nodes, it is possible that this instruction has - // a constant value, despite the fact that the PHI node doesn't. Check for - // this condition now. - if (PHINode *PN1 = dyn_cast(I.getOperand(0))) - if (PHINode *PN2 = dyn_cast(I.getOperand(1))) - if (PN1->getParent() == PN2->getParent()) { - // Since the two PHI nodes are in the same basic block, they must have - // entries for the same predecessors. Walk the predecessor list, and - // if all of the incoming values are constants, and the result of - // evaluating this expression with all incoming value pairs is the - // same, then this expression is a constant even though the PHI node - // is not a constant! - LatticeVal Result; - for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) { - LatticeVal &In1 = getValueState(PN1->getIncomingValue(i)); - BasicBlock *InBlock = PN1->getIncomingBlock(i); - LatticeVal &In2 = - getValueState(PN2->getIncomingValueForBlock(InBlock)); - - if (In1.isOverdefined() || In2.isOverdefined()) { - Result.markOverdefined(); - break; // Cannot fold this operation over the PHI nodes! - } else if (In1.isConstant() && In2.isConstant()) { - Constant *V = - ConstantExpr::get(I.getOpcode(), In1.getConstant(), - In2.getConstant()); - if (Result.isUndefined()) - Result.markConstant(V); - else if (Result.isConstant() && Result.getConstant() != V) { - Result.markOverdefined(); - break; - } - } - } - - // If we found a constant value here, then we know the instruction is - // constant despite the fact that the PHI nodes are overdefined. - if (Result.isConstant()) { - markConstant(IV, &I, Result.getConstant()); - // Remember that this instruction is virtually using the PHI node - // operands. - UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I)); - UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I)); - return; - } else if (Result.isUndefined()) { - return; - } - - // Okay, this really is overdefined now. Since we might have - // speculatively thought that this was not overdefined before, and - // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs, - // make sure to clean out any entries that we put there, for - // efficiency. - std::multimap::iterator It, E; - tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1); - while (It != E) { - if (It->second == &I) { - UsersOfOverdefinedPHIs.erase(It++); - } else - ++It; - } - tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2); - while (It != E) { - if (It->second == &I) { - UsersOfOverdefinedPHIs.erase(It++); - } else - ++It; - } - } - - markOverdefined(IV, &I); - } else if (V1State.isConstant() && V2State.isConstant()) { - markConstant(IV, &I, - ConstantExpr::get(I.getOpcode(), V1State.getConstant(), - V2State.getConstant())); - } + markOverdefined(&I); } -// Handle ICmpInst instruction... +// Handle ICmpInst instruction. void SCCPSolver::visitCmpInst(CmpInst &I) { + LatticeVal V1State = getValueState(I.getOperand(0)); + LatticeVal V2State = getValueState(I.getOperand(1)); + LatticeVal &IV = ValueState[&I]; if (IV.isOverdefined()) return; - LatticeVal &V1State = getValueState(I.getOperand(0)); - LatticeVal &V2State = getValueState(I.getOperand(1)); - - if (V1State.isOverdefined() || V2State.isOverdefined()) { - // If both operands are PHI nodes, it is possible that this instruction has - // a constant value, despite the fact that the PHI node doesn't. Check for - // this condition now. - if (PHINode *PN1 = dyn_cast(I.getOperand(0))) - if (PHINode *PN2 = dyn_cast(I.getOperand(1))) - if (PN1->getParent() == PN2->getParent()) { - // Since the two PHI nodes are in the same basic block, they must have - // entries for the same predecessors. Walk the predecessor list, and - // if all of the incoming values are constants, and the result of - // evaluating this expression with all incoming value pairs is the - // same, then this expression is a constant even though the PHI node - // is not a constant! - LatticeVal Result; - for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) { - LatticeVal &In1 = getValueState(PN1->getIncomingValue(i)); - BasicBlock *InBlock = PN1->getIncomingBlock(i); - LatticeVal &In2 = - getValueState(PN2->getIncomingValueForBlock(InBlock)); - - if (In1.isOverdefined() || In2.isOverdefined()) { - Result.markOverdefined(); - break; // Cannot fold this operation over the PHI nodes! - } else if (In1.isConstant() && In2.isConstant()) { - Constant *V = ConstantExpr::getCompare(I.getPredicate(), - In1.getConstant(), - In2.getConstant()); - if (Result.isUndefined()) - Result.markConstant(V); - else if (Result.isConstant() && Result.getConstant() != V) { - Result.markOverdefined(); - break; - } - } - } - - // If we found a constant value here, then we know the instruction is - // constant despite the fact that the PHI nodes are overdefined. - if (Result.isConstant()) { - markConstant(IV, &I, Result.getConstant()); - // Remember that this instruction is virtually using the PHI node - // operands. - UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I)); - UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I)); - return; - } else if (Result.isUndefined()) { - return; - } + if (V1State.isConstant() && V2State.isConstant()) + return markConstant(IV, &I, ConstantExpr::getCompare(I.getPredicate(), + V1State.getConstant(), + V2State.getConstant())); - // Okay, this really is overdefined now. Since we might have - // speculatively thought that this was not overdefined before, and - // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs, - // make sure to clean out any entries that we put there, for - // efficiency. - std::multimap::iterator It, E; - tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1); - while (It != E) { - if (It->second == &I) { - UsersOfOverdefinedPHIs.erase(It++); - } else - ++It; - } - tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2); - while (It != E) { - if (It->second == &I) { - UsersOfOverdefinedPHIs.erase(It++); - } else - ++It; - } - } + // If operands are still undefined, wait for it to resolve. + if (!V1State.isOverdefined() && !V2State.isOverdefined()) + return; - markOverdefined(IV, &I); - } else if (V1State.isConstant() && V2State.isConstant()) { - markConstant(IV, &I, ConstantExpr::getCompare(I.getPredicate(), - V1State.getConstant(), - V2State.getConstant())); - } + markOverdefined(&I); } void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) { - // FIXME : SCCP does not handle vectors properly. - markOverdefined(&I); - return; + // TODO : SCCP does not handle vectors properly. + return markOverdefined(&I); #if 0 LatticeVal &ValState = getValueState(I.getOperand(0)); @@ -1025,9 +945,8 @@ void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) { } void SCCPSolver::visitInsertElementInst(InsertElementInst &I) { - // FIXME : SCCP does not handle vectors properly. - markOverdefined(&I); - return; + // TODO : SCCP does not handle vectors properly. + return markOverdefined(&I); #if 0 LatticeVal &ValState = getValueState(I.getOperand(0)); LatticeVal &EltState = getValueState(I.getOperand(1)); @@ -1042,7 +961,7 @@ void SCCPSolver::visitInsertElementInst(InsertElementInst &I) { EltState.getConstant(), IdxState.getConstant())); else if (ValState.isUndefined() && EltState.isConstant() && - IdxState.isConstant()) + IdxState.isConstant()) markConstant(&I,ConstantExpr::getInsertElement(UndefValue::get(I.getType()), EltState.getConstant(), IdxState.getConstant())); @@ -1050,9 +969,8 @@ void SCCPSolver::visitInsertElementInst(InsertElementInst &I) { } void SCCPSolver::visitShuffleVectorInst(ShuffleVectorInst &I) { - // FIXME : SCCP does not handle vectors properly. - markOverdefined(&I); - return; + // TODO : SCCP does not handle vectors properly. + return markOverdefined(&I); #if 0 LatticeVal &V1State = getValueState(I.getOperand(0)); LatticeVal &V2State = getValueState(I.getOperand(1)); @@ -1061,63 +979,63 @@ void SCCPSolver::visitShuffleVectorInst(ShuffleVectorInst &I) { if (MaskState.isUndefined() || (V1State.isUndefined() && V2State.isUndefined())) return; // Undefined output if mask or both inputs undefined. - + if (V1State.isOverdefined() || V2State.isOverdefined() || MaskState.isOverdefined()) { markOverdefined(&I); } else { // A mix of constant/undef inputs. - Constant *V1 = V1State.isConstant() ? + Constant *V1 = V1State.isConstant() ? V1State.getConstant() : UndefValue::get(I.getType()); - Constant *V2 = V2State.isConstant() ? + Constant *V2 = V2State.isConstant() ? V2State.getConstant() : UndefValue::get(I.getType()); - Constant *Mask = MaskState.isConstant() ? + Constant *Mask = MaskState.isConstant() ? MaskState.getConstant() : UndefValue::get(I.getOperand(2)->getType()); markConstant(&I, ConstantExpr::getShuffleVector(V1, V2, Mask)); } #endif } -// Handle getelementptr instructions... if all operands are constants then we +// Handle getelementptr instructions. If all operands are constants then we // can turn this into a getelementptr ConstantExpr. // void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { - LatticeVal &IV = ValueState[&I]; - if (IV.isOverdefined()) return; + if (ValueState[&I].isOverdefined()) return; SmallVector Operands; Operands.reserve(I.getNumOperands()); for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { - LatticeVal &State = getValueState(I.getOperand(i)); + LatticeVal State = getValueState(I.getOperand(i)); if (State.isUndefined()) - return; // Operands are not resolved yet... - else if (State.isOverdefined()) { - markOverdefined(IV, &I); - return; - } + return; // Operands are not resolved yet. + + if (State.isOverdefined()) + return markOverdefined(&I); + assert(State.isConstant() && "Unknown state!"); Operands.push_back(State.getConstant()); } Constant *Ptr = Operands[0]; - Operands.erase(Operands.begin()); // Erase the pointer from idx list... - - markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, &Operands[0], - Operands.size())); + ArrayRef Indices(Operands.begin() + 1, Operands.end()); + markConstant(&I, ConstantExpr::getGetElementPtr(Ptr, Indices)); } -void SCCPSolver::visitStoreInst(Instruction &SI) { +void SCCPSolver::visitStoreInst(StoreInst &SI) { + // If this store is of a struct, ignore it. + if (SI.getOperand(0)->getType()->isStructTy()) + return; + if (TrackedGlobals.empty() || !isa(SI.getOperand(1))) return; + GlobalVariable *GV = cast(SI.getOperand(1)); DenseMap::iterator I = TrackedGlobals.find(GV); if (I == TrackedGlobals.end() || I->second.isOverdefined()) return; - // Get the value we are storing into the global. - LatticeVal &PtrVal = getValueState(SI.getOperand(0)); - - mergeInValue(I->second, GV, PtrVal); + // Get the value we are storing into the global, then merge it. + mergeInValue(I->second, GV, getValueState(SI.getOperand(0))); if (I->second.isOverdefined()) TrackedGlobals.erase(I); // No need to keep tracking this! } @@ -1126,50 +1044,42 @@ void SCCPSolver::visitStoreInst(Instruction &SI) { // Handle load instructions. If the operand is a constant pointer to a constant // global, we can replace the load with the loaded constant value! void SCCPSolver::visitLoadInst(LoadInst &I) { + // If this load is of a struct, just mark the result overdefined. + if (I.getType()->isStructTy()) + return markAnythingOverdefined(&I); + + LatticeVal PtrVal = getValueState(I.getOperand(0)); + if (PtrVal.isUndefined()) return; // The pointer is not resolved yet! + LatticeVal &IV = ValueState[&I]; if (IV.isOverdefined()) return; - LatticeVal &PtrVal = getValueState(I.getOperand(0)); - if (PtrVal.isUndefined()) return; // The pointer is not resolved yet! - if (PtrVal.isConstant() && !I.isVolatile()) { - Value *Ptr = PtrVal.getConstant(); - // TODO: Consider a target hook for valid address spaces for this xform. - if (isa(Ptr) && I.getPointerAddressSpace() == 0) { - // load null -> null - markConstant(IV, &I, Constant::getNullValue(I.getType())); - return; - } + if (!PtrVal.isConstant() || I.isVolatile()) + return markOverdefined(IV, &I); - // Transform load (constant global) into the value loaded. - if (GlobalVariable *GV = dyn_cast(Ptr)) { - if (GV->isConstant()) { - if (GV->hasDefinitiveInitializer()) { - markConstant(IV, &I, GV->getInitializer()); - return; - } - } else if (!TrackedGlobals.empty()) { - // If we are tracking this global, merge in the known value for it. - DenseMap::iterator It = - TrackedGlobals.find(GV); - if (It != TrackedGlobals.end()) { - mergeInValue(IV, &I, It->second); - return; - } + Constant *Ptr = PtrVal.getConstant(); + + // load null -> null + if (isa(Ptr) && I.getPointerAddressSpace() == 0) + return markConstant(IV, &I, Constant::getNullValue(I.getType())); + + // Transform load (constant global) into the value loaded. + if (GlobalVariable *GV = dyn_cast(Ptr)) { + if (!TrackedGlobals.empty()) { + // If we are tracking this global, merge in the known value for it. + DenseMap::iterator It = + TrackedGlobals.find(GV); + if (It != TrackedGlobals.end()) { + mergeInValue(IV, &I, It->second); + return; } } - - // Transform load (constantexpr_GEP global, 0, ...) into the value loaded. - if (ConstantExpr *CE = dyn_cast(Ptr)) - if (CE->getOpcode() == Instruction::GetElementPtr) - if (GlobalVariable *GV = dyn_cast(CE->getOperand(0))) - if (GV->isConstant() && GV->hasDefinitiveInitializer()) - if (Constant *V = - ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE)) { - markConstant(IV, &I, V); - return; - } } + // Transform load from a constant into a constant if possible. + if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, TD)) + return markConstant(IV, &I, C); + // Otherwise we cannot say for certain what value this load will produce. // Bail out. markOverdefined(IV, &I); @@ -1178,101 +1088,88 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { void SCCPSolver::visitCallSite(CallSite CS) { Function *F = CS.getCalledFunction(); Instruction *I = CS.getInstruction(); - + // The common case is that we aren't tracking the callee, either because we // are not doing interprocedural analysis or the callee is indirect, or is // external. Handle these cases first. - if (F == 0 || !F->hasLocalLinkage()) { + if (F == 0 || F->isDeclaration()) { CallOverdefined: // Void return and not tracking callee, just bail. if (I->getType()->isVoidTy()) return; - + // Otherwise, if we have a single return value case, and if the function is // a declaration, maybe we can constant fold it. - if (!isa(I->getType()) && F && F->isDeclaration() && + if (F && F->isDeclaration() && !I->getType()->isStructTy() && canConstantFoldCallTo(F)) { - + SmallVector Operands; for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); AI != E; ++AI) { - LatticeVal &State = getValueState(*AI); + LatticeVal State = getValueState(*AI); + if (State.isUndefined()) return; // Operands are not resolved yet. - else if (State.isOverdefined()) { - markOverdefined(I); - return; - } + if (State.isOverdefined()) + return markOverdefined(I); assert(State.isConstant() && "Unknown state!"); Operands.push_back(State.getConstant()); } - + // If we can constant fold this, mark the result of the call as a // constant. - if (Constant *C = ConstantFoldCall(F, Operands.data(), Operands.size())) { - markConstant(I, C); - return; - } + if (Constant *C = ConstantFoldCall(F, Operands, TLI)) + return markConstant(I, C); } // Otherwise, we don't know anything about this call, mark it overdefined. - markOverdefined(I); - return; + return markAnythingOverdefined(I); } - // If this is a single/zero retval case, see if we're tracking the function. - DenseMap::iterator TFRVI = TrackedRetVals.find(F); - if (TFRVI != TrackedRetVals.end()) { - // If so, propagate the return value of the callee into this call result. - mergeInValue(I, TFRVI->second); - } else if (isa(I->getType())) { - // Check to see if we're tracking this callee, if not, handle it in the - // common path above. - DenseMap, LatticeVal>::iterator - TMRVI = TrackedMultipleRetVals.find(std::make_pair(F, 0)); - if (TMRVI == TrackedMultipleRetVals.end()) - goto CallOverdefined; - - // Need to mark as overdefined, otherwise it stays undefined which - // creates extractvalue undef, - markOverdefined(I); - // If we are tracking this callee, propagate the return values of the call - // into this call site. We do this by walking all the uses. Single-index - // ExtractValueInst uses can be tracked; anything more complicated is - // currently handled conservatively. - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); - UI != E; ++UI) { - if (ExtractValueInst *EVI = dyn_cast(*UI)) { - if (EVI->getNumIndices() == 1) { - mergeInValue(EVI, - TrackedMultipleRetVals[std::make_pair(F, *EVI->idx_begin())]); - continue; + // If this is a local function that doesn't have its address taken, mark its + // entry block executable and merge in the actual arguments to the call into + // the formal arguments of the function. + if (!TrackingIncomingArguments.empty() && TrackingIncomingArguments.count(F)){ + MarkBlockExecutable(F->begin()); + + // Propagate information from this call site into the callee. + CallSite::arg_iterator CAI = CS.arg_begin(); + for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); + AI != E; ++AI, ++CAI) { + // If this argument is byval, and if the function is not readonly, there + // will be an implicit copy formed of the input aggregate. + if (AI->hasByValAttr() && !F->onlyReadsMemory()) { + markOverdefined(AI); + continue; + } + + if (StructType *STy = dyn_cast(AI->getType())) { + for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { + LatticeVal CallArg = getStructValueState(*CAI, i); + mergeInValue(getStructValueState(AI, i), AI, CallArg); } + } else { + mergeInValue(AI, getValueState(*CAI)); } - // The aggregate value is used in a way not handled here. Assume nothing. - markOverdefined(*UI); } - } else { - // Otherwise we're not tracking this callee, so handle it in the - // common path above. - goto CallOverdefined; } - - // Finally, if this is the first call to the function hit, mark its entry - // block executable. - if (!BBExecutable.count(F->begin())) - MarkBlockExecutable(F->begin()); - - // Propagate information from this call site into the callee. - CallSite::arg_iterator CAI = CS.arg_begin(); - for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); - AI != E; ++AI, ++CAI) { - LatticeVal &IV = ValueState[AI]; - if (AI->hasByValAttr() && !F->onlyReadsMemory()) { - IV.markOverdefined(); - continue; - } - if (!IV.isOverdefined()) - mergeInValue(IV, AI, getValueState(*CAI)); + + // If this is a single/zero retval case, see if we're tracking the function. + if (StructType *STy = dyn_cast(F->getReturnType())) { + if (!MRVFunctionsTracked.count(F)) + goto CallOverdefined; // Not tracking this callee. + + // If we are tracking this callee, propagate the result of the function + // into this call site. + for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) + mergeInValue(getStructValueState(I, i), I, + TrackedMultipleRetVals[std::make_pair(F, i)]); + } else { + DenseMap::iterator TFRVI = TrackedRetVals.find(F); + if (TFRVI == TrackedRetVals.end()) + goto CallOverdefined; // Not tracking this callee. + + // If so, propagate the return value of the callee into this call result. + mergeInValue(I, TFRVI->second); } } @@ -1280,50 +1177,52 @@ void SCCPSolver::Solve() { // Process the work lists until they are empty! while (!BBWorkList.empty() || !InstWorkList.empty() || !OverdefinedInstWorkList.empty()) { - // Process the instruction work list... + // Process the overdefined instruction's work list first, which drives other + // things to overdefined more quickly. while (!OverdefinedInstWorkList.empty()) { - Value *I = OverdefinedInstWorkList.back(); - OverdefinedInstWorkList.pop_back(); + Value *I = OverdefinedInstWorkList.pop_back_val(); - DEBUG(errs() << "\nPopped off OI-WL: " << *I << '\n'); + DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n'); // "I" got into the work list because it either made the transition from // bottom to constant // // Anything on this worklist that is overdefined need not be visited // since all of its users will have already been marked as overdefined - // Update all of the users of this instruction's value... + // Update all of the users of this instruction's value. // for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI) - OperandChangedState(*UI); + if (Instruction *I = dyn_cast(*UI)) + OperandChangedState(I); } - // Process the instruction work list... + + // Process the instruction work list. while (!InstWorkList.empty()) { - Value *I = InstWorkList.back(); - InstWorkList.pop_back(); + Value *I = InstWorkList.pop_back_val(); - DEBUG(errs() << "\nPopped off I-WL: " << *I << '\n'); + DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n'); - // "I" got into the work list because it either made the transition from - // bottom to constant + // "I" got into the work list because it made the transition from undef to + // constant. // // Anything on this worklist that is overdefined need not be visited // since all of its users will have already been marked as overdefined. - // Update all of the users of this instruction's value... + // Update all of the users of this instruction's value. // - if (!getValueState(I).isOverdefined()) + if (I->getType()->isStructTy() || !getValueState(I).isOverdefined()) for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI) - OperandChangedState(*UI); + if (Instruction *I = dyn_cast(*UI)) + OperandChangedState(I); } - // Process the basic block work list... + // Process the basic block work list. while (!BBWorkList.empty()) { BasicBlock *BB = BBWorkList.back(); BBWorkList.pop_back(); - DEBUG(errs() << "\nPopped off BBWL: " << *BB << '\n'); + DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n'); // Notify all instructions in this basic block that they are newly // executable. @@ -1354,53 +1253,121 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { if (!BBExecutable.count(BB)) continue; - + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { // Look for instructions which produce undef values. if (I->getType()->isVoidTy()) continue; - + + if (StructType *STy = dyn_cast(I->getType())) { + // Only a few things that can be structs matter for undef. + + // Tracked calls must never be marked overdefined in ResolvedUndefsIn. + if (CallSite CS = CallSite(I)) + if (Function *F = CS.getCalledFunction()) + if (MRVFunctionsTracked.count(F)) + continue; + + // extractvalue and insertvalue don't need to be marked; they are + // tracked as precisely as their operands. + if (isa(I) || isa(I)) + continue; + + // Send the results of everything else to overdefined. We could be + // more precise than this but it isn't worth bothering. + for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { + LatticeVal &LV = getStructValueState(I, i); + if (LV.isUndefined()) + markOverdefined(LV, I); + } + continue; + } + LatticeVal &LV = getValueState(I); if (!LV.isUndefined()) continue; - // Get the lattice values of the first two operands for use below. - LatticeVal &Op0LV = getValueState(I->getOperand(0)); + // extractvalue is safe; check here because the argument is a struct. + if (isa(I)) + continue; + + // Compute the operand LatticeVals, for convenience below. + // Anything taking a struct is conservatively assumed to require + // overdefined markings. + if (I->getOperand(0)->getType()->isStructTy()) { + markOverdefined(I); + return true; + } + LatticeVal Op0LV = getValueState(I->getOperand(0)); LatticeVal Op1LV; if (I->getNumOperands() == 2) { - // If this is a two-operand instruction, and if both operands are - // undefs, the result stays undef. + if (I->getOperand(1)->getType()->isStructTy()) { + markOverdefined(I); + return true; + } + Op1LV = getValueState(I->getOperand(1)); - if (Op0LV.isUndefined() && Op1LV.isUndefined()) - continue; } - // If this is an instructions whose result is defined even if the input is // not fully defined, propagate the information. - const Type *ITy = I->getType(); + Type *ITy = I->getType(); switch (I->getOpcode()) { - default: break; // Leave the instruction as an undef. + case Instruction::Add: + case Instruction::Sub: + case Instruction::Trunc: + case Instruction::FPTrunc: + case Instruction::BitCast: + break; // Any undef -> undef + case Instruction::FSub: + case Instruction::FAdd: + case Instruction::FMul: + case Instruction::FDiv: + case Instruction::FRem: + // Floating-point binary operation: be conservative. + if (Op0LV.isUndefined() && Op1LV.isUndefined()) + markForcedConstant(I, Constant::getNullValue(ITy)); + else + markOverdefined(I); + return true; case Instruction::ZExt: - // After a zero extend, we know the top part is zero. SExt doesn't have - // to be handled here, because we don't know whether the top part is 1's - // or 0's. - assert(Op0LV.isUndefined()); - markForcedConstant(LV, I, Constant::getNullValue(ITy)); + case Instruction::SExt: + case Instruction::FPToUI: + case Instruction::FPToSI: + case Instruction::FPExt: + case Instruction::PtrToInt: + case Instruction::IntToPtr: + case Instruction::SIToFP: + case Instruction::UIToFP: + // undef -> 0; some outputs are impossible + markForcedConstant(I, Constant::getNullValue(ITy)); return true; case Instruction::Mul: case Instruction::And: + // Both operands undef -> undef + if (Op0LV.isUndefined() && Op1LV.isUndefined()) + break; // undef * X -> 0. X could be zero. // undef & X -> 0. X could be zero. - markForcedConstant(LV, I, Constant::getNullValue(ITy)); + markForcedConstant(I, Constant::getNullValue(ITy)); return true; case Instruction::Or: + // Both operands undef -> undef + if (Op0LV.isUndefined() && Op1LV.isUndefined()) + break; // undef | X -> -1. X could be -1. - if (const VectorType *PTy = dyn_cast(ITy)) - markForcedConstant(LV, I, - Constant::getAllOnesValue(PTy)); - else - markForcedConstant(LV, I, Constant::getAllOnesValue(ITy)); + markForcedConstant(I, Constant::getAllOnesValue(ITy)); return true; + case Instruction::Xor: + // undef ^ undef -> 0; strictly speaking, this is not strictly + // necessary, but we try to be nice to people who expect this + // behavior in simple cases + if (Op0LV.isUndefined() && Op1LV.isUndefined()) { + markForcedConstant(I, Constant::getNullValue(ITy)); + return true; + } + // undef ^ X -> undef + break; + case Instruction::SDiv: case Instruction::UDiv: case Instruction::SRem: @@ -1408,33 +1375,31 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { // X / undef -> undef. No change. // X % undef -> undef. No change. if (Op1LV.isUndefined()) break; - + // undef / X -> 0. X could be maxint. // undef % X -> 0. X could be 1. - markForcedConstant(LV, I, Constant::getNullValue(ITy)); + markForcedConstant(I, Constant::getNullValue(ITy)); return true; - + case Instruction::AShr: - // undef >>s X -> undef. No change. - if (Op0LV.isUndefined()) break; - - // X >>s undef -> X. X could be 0, X could have the high-bit known set. - if (Op0LV.isConstant()) - markForcedConstant(LV, I, Op0LV.getConstant()); - else - markOverdefined(LV, I); + // X >>a undef -> undef. + if (Op1LV.isUndefined()) break; + + // undef >>a X -> all ones + markForcedConstant(I, Constant::getAllOnesValue(ITy)); return true; case Instruction::LShr: case Instruction::Shl: - // undef >> X -> undef. No change. - // undef << X -> undef. No change. - if (Op0LV.isUndefined()) break; - - // X >> undef -> 0. X could be 0. - // X << undef -> 0. X could be 0. - markForcedConstant(LV, I, Constant::getNullValue(ITy)); + // X << undef -> undef. + // X >> undef -> undef. + if (Op1LV.isUndefined()) break; + + // undef << X -> 0 + // undef >> X -> 0 + markForcedConstant(I, Constant::getNullValue(ITy)); return true; case Instruction::Select: + Op1LV = getValueState(I->getOperand(1)); // undef ? X : Y -> X or Y. There could be commonality between X/Y. if (Op0LV.isUndefined()) { if (!Op1LV.isConstant()) // Pick the constant one if there is any. @@ -1448,60 +1413,89 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { } else { // Leave Op1LV as Operand(1)'s LatticeValue. } - + if (Op1LV.isConstant()) - markForcedConstant(LV, I, Op1LV.getConstant()); + markForcedConstant(I, Op1LV.getConstant()); else - markOverdefined(LV, I); + markOverdefined(I); + return true; + case Instruction::Load: + // A load here means one of two things: a load of undef from a global, + // a load from an unknown pointer. Either way, having it return undef + // is okay. + break; + case Instruction::ICmp: + // X == undef -> undef. Other comparisons get more complicated. + if (cast(I)->isEquality()) + break; + markOverdefined(I); return true; case Instruction::Call: - // If a call has an undef result, it is because it is constant foldable - // but one of the inputs was undef. Just force the result to + case Instruction::Invoke: { + // There are two reasons a call can have an undef result + // 1. It could be tracked. + // 2. It could be constant-foldable. + // Because of the way we solve return values, tracked calls must + // never be marked overdefined in ResolvedUndefsIn. + if (Function *F = CallSite(I).getCalledFunction()) + if (TrackedRetVals.count(F)) + break; + + // If the call is constant-foldable, we mark it overdefined because + // we do not know what return values are valid. + markOverdefined(I); + return true; + } + default: + // If we don't know what should happen here, conservatively mark it // overdefined. - markOverdefined(LV, I); + markOverdefined(I); return true; } } - + + // Check to see if we have a branch or switch on an undefined value. If so + // we force the branch to go one way or the other to make the successor + // values live. It doesn't really matter which way we force it. TerminatorInst *TI = BB->getTerminator(); if (BranchInst *BI = dyn_cast(TI)) { if (!BI->isConditional()) continue; if (!getValueState(BI->getCondition()).isUndefined()) continue; - } else if (SwitchInst *SI = dyn_cast(TI)) { - if (SI->getNumSuccessors()<2) // no cases + + // If the input to SCCP is actually branch on undef, fix the undef to + // false. + if (isa(BI->getCondition())) { + BI->setCondition(ConstantInt::getFalse(BI->getContext())); + markEdgeExecutable(BB, TI->getSuccessor(1)); + return true; + } + + // Otherwise, it is a branch on a symbolic value which is currently + // considered to be undef. Handle this by forcing the input value to the + // branch to false. + markForcedConstant(BI->getCondition(), + ConstantInt::getFalse(TI->getContext())); + return true; + } + + if (SwitchInst *SI = dyn_cast(TI)) { + if (!SI->getNumCases()) continue; if (!getValueState(SI->getCondition()).isUndefined()) continue; - } else { - continue; - } - - // If the edge to the second successor isn't thought to be feasible yet, - // mark it so now. We pick the second one so that this goes to some - // enumerated value in a switch instead of going to the default destination. - if (KnownFeasibleEdges.count(Edge(BB, TI->getSuccessor(1)))) - continue; - - // Otherwise, it isn't already thought to be feasible. Mark it as such now - // and return. This will make other blocks reachable, which will allow new - // values to be discovered and existing ones to be moved in the lattice. - markEdgeExecutable(BB, TI->getSuccessor(1)); - - // This must be a conditional branch of switch on undef. At this point, - // force the old terminator to branch to the first successor. This is - // required because we are now influencing the dataflow of the function with - // the assumption that this edge is taken. If we leave the branch condition - // as undef, then further analysis could think the undef went another way - // leading to an inconsistent set of conclusions. - if (BranchInst *BI = dyn_cast(TI)) { - BI->setCondition(ConstantInt::getFalse(*Context)); - } else { - SwitchInst *SI = cast(TI); - SI->setCondition(SI->getCaseValue(1)); + + // If the input to SCCP is actually switch on undef, fix the undef to + // the first constant. + if (isa(SI->getCondition())) { + SI->setCondition(SI->caseBegin().getCaseValue()); + markEdgeExecutable(BB, SI->caseBegin().getCaseSuccessor()); + return true; + } + + markForcedConstant(SI->getCondition(), SI->caseBegin().getCaseValue()); + return true; } - - return true; } return false; @@ -1515,50 +1509,77 @@ namespace { /// Sparse Conditional Constant Propagator. /// struct SCCP : public FunctionPass { + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + } static char ID; // Pass identification, replacement for typeid - SCCP() : FunctionPass(&ID) {} + SCCP() : FunctionPass(ID) { + initializeSCCPPass(*PassRegistry::getPassRegistry()); + } // runOnFunction - Run the Sparse Conditional Constant Propagation // algorithm, and return true if the function was modified. // bool runOnFunction(Function &F); - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesCFG(); - } }; } // end anonymous namespace char SCCP::ID = 0; -static RegisterPass -X("sccp", "Sparse Conditional Constant Propagation"); +INITIALIZE_PASS(SCCP, "sccp", + "Sparse Conditional Constant Propagation", false, false) -// createSCCPPass - This is the public interface to this file... +// createSCCPPass - This is the public interface to this file. FunctionPass *llvm::createSCCPPass() { return new SCCP(); } +static void DeleteInstructionInBlock(BasicBlock *BB) { + DEBUG(dbgs() << " BasicBlock Dead:" << *BB); + ++NumDeadBlocks; + + // Check to see if there are non-terminating instructions to delete. + if (isa(BB->begin())) + return; + + // Delete the instructions backwards, as it has a reduced likelihood of having + // to update as many def-use and use-def chains. + Instruction *EndInst = BB->getTerminator(); // Last not to be deleted. + while (EndInst != BB->begin()) { + // Delete the next to last instruction. + BasicBlock::iterator I = EndInst; + Instruction *Inst = --I; + if (!Inst->use_empty()) + Inst->replaceAllUsesWith(UndefValue::get(Inst->getType())); + if (isa(Inst)) { + EndInst = Inst; + continue; + } + BB->getInstList().erase(Inst); + ++NumInstRemoved; + } +} // runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm, // and return true if the function was modified. // bool SCCP::runOnFunction(Function &F) { - DEBUG(errs() << "SCCP on function '" << F.getName() << "'\n"); - SCCPSolver Solver; - Solver.setContext(&F.getContext()); + DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n"); + const TargetData *TD = getAnalysisIfAvailable(); + const TargetLibraryInfo *TLI = &getAnalysis(); + SCCPSolver Solver(TD, TLI); // Mark the first block of the function as being executable. Solver.MarkBlockExecutable(F.begin()); // Mark all arguments to the function as being overdefined. for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;++AI) - Solver.markOverdefined(AI); + Solver.markAnythingOverdefined(AI); // Solve for constants. bool ResolvedUndefs = true; while (ResolvedUndefs) { Solver.Solve(); - DEBUG(errs() << "RESOLVING UNDEFs\n"); + DEBUG(dbgs() << "RESOLVING UNDEFs\n"); ResolvedUndefs = Solver.ResolvedUndefsIn(F); } @@ -1567,57 +1588,45 @@ bool SCCP::runOnFunction(Function &F) { // If we decided that there are basic blocks that are dead in this function, // delete their contents now. Note that we cannot actually delete the blocks, // as we cannot modify the CFG of the function. - // - SmallVector Insts; - std::map &Values = Solver.getValueMapping(); - for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) + for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { if (!Solver.isBlockExecutable(BB)) { - DEBUG(errs() << " BasicBlock Dead:" << *BB); - ++NumDeadBlocks; - - // Delete the instructions backwards, as it has a reduced likelihood of - // having to update as many def-use and use-def chains. - for (BasicBlock::iterator I = BB->begin(), E = BB->getTerminator(); - I != E; ++I) - Insts.push_back(I); - while (!Insts.empty()) { - Instruction *I = Insts.back(); - Insts.pop_back(); - if (!I->use_empty()) - I->replaceAllUsesWith(UndefValue::get(I->getType())); - BB->getInstList().erase(I); - MadeChanges = true; - ++NumInstRemoved; - } - } else { - // Iterate over all of the instructions in a function, replacing them with - // constants if we have found them to be of constant values. - // - for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { - Instruction *Inst = BI++; - if (Inst->getType()->isVoidTy() || isa(Inst)) - continue; - - LatticeVal &IV = Values[Inst]; - if (!IV.isConstant() && !IV.isUndefined()) - continue; - - Constant *Const = IV.isConstant() - ? IV.getConstant() : UndefValue::get(Inst->getType()); - DEBUG(errs() << " Constant: " << *Const << " = " << *Inst); + DeleteInstructionInBlock(BB); + MadeChanges = true; + continue; + } - // Replaces all of the uses of a variable with uses of the constant. - Inst->replaceAllUsesWith(Const); - - // Delete the instruction. - Inst->eraseFromParent(); - - // Hey, we just changed something! - MadeChanges = true; - ++NumInstRemoved; - } + // Iterate over all of the instructions in a function, replacing them with + // constants if we have found them to be of constant values. + // + for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { + Instruction *Inst = BI++; + if (Inst->getType()->isVoidTy() || isa(Inst)) + continue; + + // TODO: Reconstruct structs from their elements. + if (Inst->getType()->isStructTy()) + continue; + + LatticeVal IV = Solver.getLatticeValueFor(Inst); + if (IV.isOverdefined()) + continue; + + Constant *Const = IV.isConstant() + ? IV.getConstant() : UndefValue::get(Inst->getType()); + DEBUG(dbgs() << " Constant: " << *Const << " = " << *Inst); + + // Replaces all of the uses of a variable with uses of the constant. + Inst->replaceAllUsesWith(Const); + + // Delete the instruction. + Inst->eraseFromParent(); + + // Hey, we just changed something! + MadeChanges = true; + ++NumInstRemoved; } + } return MadeChanges; } @@ -1629,65 +1638,105 @@ namespace { /// Constant Propagation. /// struct IPSCCP : public ModulePass { + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + } static char ID; - IPSCCP() : ModulePass(&ID) {} + IPSCCP() : ModulePass(ID) { + initializeIPSCCPPass(*PassRegistry::getPassRegistry()); + } bool runOnModule(Module &M); }; } // end anonymous namespace char IPSCCP::ID = 0; -static RegisterPass -Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation"); - -// createIPSCCPPass - This is the public interface to this file... +INITIALIZE_PASS_BEGIN(IPSCCP, "ipsccp", + "Interprocedural Sparse Conditional Constant Propagation", + false, false) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) +INITIALIZE_PASS_END(IPSCCP, "ipsccp", + "Interprocedural Sparse Conditional Constant Propagation", + false, false) + +// createIPSCCPPass - This is the public interface to this file. ModulePass *llvm::createIPSCCPPass() { return new IPSCCP(); } -static bool AddressIsTaken(GlobalValue *GV) { +static bool AddressIsTaken(const GlobalValue *GV) { // Delete any dead constantexpr klingons. GV->removeDeadConstantUsers(); - for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); - UI != E; ++UI) - if (StoreInst *SI = dyn_cast(*UI)) { + for (Value::const_use_iterator UI = GV->use_begin(), E = GV->use_end(); + UI != E; ++UI) { + const User *U = *UI; + if (const StoreInst *SI = dyn_cast(U)) { if (SI->getOperand(0) == GV || SI->isVolatile()) return true; // Storing addr of GV. - } else if (isa(*UI) || isa(*UI)) { + } else if (isa(U) || isa(U)) { // Make sure we are calling the function, not passing the address. - CallSite CS = CallSite::get(cast(*UI)); - if (CS.hasArgument(GV)) + ImmutableCallSite CS(cast(U)); + if (!CS.isCallee(UI)) return true; - } else if (LoadInst *LI = dyn_cast(*UI)) { + } else if (const LoadInst *LI = dyn_cast(U)) { if (LI->isVolatile()) return true; + } else if (isa(U)) { + // blockaddress doesn't take the address of the function, it takes addr + // of label. } else { return true; } + } return false; } bool IPSCCP::runOnModule(Module &M) { - LLVMContext *Context = &M.getContext(); - - SCCPSolver Solver; - Solver.setContext(Context); + const TargetData *TD = getAnalysisIfAvailable(); + const TargetLibraryInfo *TLI = &getAnalysis(); + SCCPSolver Solver(TD, TLI); + + // AddressTakenFunctions - This set keeps track of the address-taken functions + // that are in the input. As IPSCCP runs through and simplifies code, + // functions that were address taken can end up losing their + // address-taken-ness. Because of this, we keep track of their addresses from + // the first pass so we can use them for the later simplification pass. + SmallPtrSet AddressTakenFunctions; // Loop over all functions, marking arguments to those with their addresses // taken or that are external as overdefined. // - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) - if (!F->hasLocalLinkage() || AddressIsTaken(F)) { - if (!F->isDeclaration()) - Solver.MarkBlockExecutable(F->begin()); - for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); - AI != E; ++AI) - Solver.markOverdefined(AI); - } else { + for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { + if (F->isDeclaration()) + continue; + + // If this is a strong or ODR definition of this function, then we can + // propagate information about its result into callsites of it. + if (!F->mayBeOverridden()) Solver.AddTrackedFunction(F); + + // If this function only has direct calls that we can see, we can track its + // arguments and return value aggressively, and can assume it is not called + // unless we see evidence to the contrary. + if (F->hasLocalLinkage()) { + if (AddressIsTaken(F)) + AddressTakenFunctions.insert(F); + else { + Solver.AddArgumentTrackedFunction(F); + continue; + } } + // Assume the function is called. + Solver.MarkBlockExecutable(F->begin()); + + // Assume nothing about the incoming arguments. + for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); + AI != E; ++AI) + Solver.markAnythingOverdefined(AI); + } + // Loop over global variables. We inform the solver about any internal global // variables that do not have their 'addresses taken'. If they don't have // their addresses taken, we can propagate constants through them. @@ -1701,7 +1750,7 @@ bool IPSCCP::runOnModule(Module &M) { while (ResolvedUndefs) { Solver.Solve(); - DEBUG(errs() << "RESOLVING UNDEFS\n"); + DEBUG(dbgs() << "RESOLVING UNDEFS\n"); ResolvedUndefs = false; for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) ResolvedUndefs |= Solver.ResolvedUndefsIn(*F); @@ -1712,48 +1761,37 @@ bool IPSCCP::runOnModule(Module &M) { // Iterate over all of the instructions in the module, replacing them with // constants if we have found them to be of constant values. // - SmallVector Insts; SmallVector BlocksToErase; - std::map &Values = Solver.getValueMapping(); for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); - AI != E; ++AI) - if (!AI->use_empty()) { - LatticeVal &IV = Values[AI]; - if (IV.isConstant() || IV.isUndefined()) { - Constant *CST = IV.isConstant() ? - IV.getConstant() : UndefValue::get(AI->getType()); - DEBUG(errs() << "*** Arg " << *AI << " = " << *CST <<"\n"); - - // Replaces all of the uses of a variable with uses of the - // constant. - AI->replaceAllUsesWith(CST); - ++IPNumArgsElimed; - } + if (Solver.isBlockExecutable(F->begin())) { + for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); + AI != E; ++AI) { + if (AI->use_empty() || AI->getType()->isStructTy()) continue; + + // TODO: Could use getStructLatticeValueFor to find out if the entire + // result is a constant and replace it entirely if so. + + LatticeVal IV = Solver.getLatticeValueFor(AI); + if (IV.isOverdefined()) continue; + + Constant *CST = IV.isConstant() ? + IV.getConstant() : UndefValue::get(AI->getType()); + DEBUG(dbgs() << "*** Arg " << *AI << " = " << *CST <<"\n"); + + // Replaces all of the uses of a variable with uses of the + // constant. + AI->replaceAllUsesWith(CST); + ++IPNumArgsElimed; } + } - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { if (!Solver.isBlockExecutable(BB)) { - DEBUG(errs() << " BasicBlock Dead:" << *BB); - ++IPNumDeadBlocks; + DeleteInstructionInBlock(BB); + MadeChanges = true; - // Delete the instructions backwards, as it has a reduced likelihood of - // having to update as many def-use and use-def chains. TerminatorInst *TI = BB->getTerminator(); - for (BasicBlock::iterator I = BB->begin(), E = TI; I != E; ++I) - Insts.push_back(I); - - while (!Insts.empty()) { - Instruction *I = Insts.back(); - Insts.pop_back(); - if (!I->use_empty()) - I->replaceAllUsesWith(UndefValue::get(I->getType())); - BB->getInstList().erase(I); - MadeChanges = true; - ++IPNumInstRemoved; - } - for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { BasicBlock *Succ = TI->getSuccessor(i); if (!Succ->empty() && isa(Succ->begin())) @@ -1761,40 +1799,44 @@ bool IPSCCP::runOnModule(Module &M) { } if (!TI->use_empty()) TI->replaceAllUsesWith(UndefValue::get(TI->getType())); - BB->getInstList().erase(TI); + TI->eraseFromParent(); if (&*BB != &F->front()) BlocksToErase.push_back(BB); else new UnreachableInst(M.getContext(), BB); + continue; + } - } else { - for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { - Instruction *Inst = BI++; - if (Inst->getType()->isVoidTy()) - continue; - - LatticeVal &IV = Values[Inst]; - if (!IV.isConstant() && !IV.isUndefined()) - continue; - - Constant *Const = IV.isConstant() - ? IV.getConstant() : UndefValue::get(Inst->getType()); - DEBUG(errs() << " Constant: " << *Const << " = " << *Inst); - - // Replaces all of the uses of a variable with uses of the - // constant. - Inst->replaceAllUsesWith(Const); - - // Delete the instruction. - if (!isa(Inst) && !isa(Inst)) - Inst->eraseFromParent(); - - // Hey, we just changed something! - MadeChanges = true; - ++IPNumInstRemoved; - } + for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { + Instruction *Inst = BI++; + if (Inst->getType()->isVoidTy() || Inst->getType()->isStructTy()) + continue; + + // TODO: Could use getStructLatticeValueFor to find out if the entire + // result is a constant and replace it entirely if so. + + LatticeVal IV = Solver.getLatticeValueFor(Inst); + if (IV.isOverdefined()) + continue; + + Constant *Const = IV.isConstant() + ? IV.getConstant() : UndefValue::get(Inst->getType()); + DEBUG(dbgs() << " Constant: " << *Const << " = " << *Inst); + + // Replaces all of the uses of a variable with uses of the + // constant. + Inst->replaceAllUsesWith(Const); + + // Delete the instruction. + if (!isa(Inst) && !isa(Inst)) + Inst->eraseFromParent(); + + // Hey, we just changed something! + MadeChanges = true; + ++IPNumInstRemoved; } + } // Now that all instructions in the function are constant folded, erase dead // blocks, because we can now use ConstantFoldTerminator to get rid of @@ -1802,8 +1844,16 @@ bool IPSCCP::runOnModule(Module &M) { for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) { // If there are any PHI nodes in this successor, drop entries for BB now. BasicBlock *DeadBB = BlocksToErase[i]; - while (!DeadBB->use_empty()) { - Instruction *I = cast(DeadBB->use_back()); + for (Value::use_iterator UI = DeadBB->use_begin(), UE = DeadBB->use_end(); + UI != UE; ) { + // Grab the user and then increment the iterator early, as the user + // will be deleted. Step past all adjacent uses from the same user. + Instruction *I = dyn_cast(*UI); + do { ++UI; } while (UI != UE && *UI == I); + + // Ignore blockaddress users; BasicBlock's dtor will handle them. + if (!I) continue; + bool Folded = ConstantFoldTerminator(I->getParent()); if (!Folded) { // The constant folder may not have been able to fold the terminator @@ -1819,15 +1869,15 @@ bool IPSCCP::runOnModule(Module &M) { llvm_unreachable("Didn't fold away reference to block!"); } #endif - + // Make this an uncond branch to the first successor. TerminatorInst *TI = I->getParent()->getTerminator(); BranchInst::Create(TI->getSuccessor(0), TI); - + // Remove entries in successor phi nodes to remove edges. for (unsigned i = 1, e = TI->getNumSuccessors(); i != e; ++i) TI->getSuccessor(i)->removePredecessor(TI->getParent()); - + // Remove the old terminator. TI->eraseFromParent(); } @@ -1843,20 +1893,39 @@ bool IPSCCP::runOnModule(Module &M) { // all call uses with the inferred value. This means we don't need to bother // actually returning anything from the function. Replace all return // instructions with return undef. + // + // Do this in two stages: first identify the functions we should process, then + // actually zap their returns. This is important because we can only do this + // if the address of the function isn't taken. In cases where a return is the + // last use of a function, the order of processing functions would affect + // whether other functions are optimizable. + SmallVector ReturnsToZap; + // TODO: Process multiple value ret instructions also. const DenseMap &RV = Solver.getTrackedRetVals(); for (DenseMap::const_iterator I = RV.begin(), - E = RV.end(); I != E; ++I) - if (!I->second.isOverdefined() && - !I->first->getReturnType()->isVoidTy()) { - Function *F = I->first; - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) - if (ReturnInst *RI = dyn_cast(BB->getTerminator())) - if (!isa(RI->getOperand(0))) - RI->setOperand(0, UndefValue::get(F->getReturnType())); - } + E = RV.end(); I != E; ++I) { + Function *F = I->first; + if (I->second.isOverdefined() || F->getReturnType()->isVoidTy()) + continue; + + // We can only do this if we know that nothing else can call the function. + if (!F->hasLocalLinkage() || AddressTakenFunctions.count(F)) + continue; + + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) + if (ReturnInst *RI = dyn_cast(BB->getTerminator())) + if (!isa(RI->getOperand(0))) + ReturnsToZap.push_back(RI); + } + + // Zap all returns which we've identified as zap to change. + for (unsigned i = 0, e = ReturnsToZap.size(); i != e; ++i) { + Function *F = ReturnsToZap[i]->getParent()->getParent(); + ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType())); + } - // If we infered constant or undef values for globals variables, we can delete + // If we inferred constant or undef values for globals variables, we can delete // the global and any stores that remain to it. const DenseMap &TG = Solver.getTrackedGlobals(); for (DenseMap::const_iterator I = TG.begin(), @@ -1864,7 +1933,7 @@ bool IPSCCP::runOnModule(Module &M) { GlobalVariable *GV = I->first; assert(!I->second.isOverdefined() && "Overdefined values should have been taken out of the map!"); - DEBUG(errs() << "Found that GV '" << GV->getName() << "' is constant!\n"); + DEBUG(dbgs() << "Found that GV '" << GV->getName() << "' is constant!\n"); while (!GV->use_empty()) { StoreInst *SI = cast(GV->use_back()); SI->eraseFromParent();