X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FSCCP.cpp;h=8d0b86606a8a3d42ef11c0f0943a8d5deb378dbc;hb=c10fa6c801e48771b5eade50afc2fe6abaf08227;hp=2ee4bbc95b17f54f54928ef4d63b625b2f63871b;hpb=c175e5de2dbb04e835b13f0554a7ba2f25ba4fc3;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp index 2ee4bbc95b1..8d0b86606a8 100644 --- a/lib/Transforms/Scalar/SCCP.cpp +++ b/lib/Transforms/Scalar/SCCP.cpp @@ -25,9 +25,9 @@ #include "llvm/Instructions.h" #include "llvm/Pass.h" #include "llvm/Analysis/ConstantFolding.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" @@ -39,9 +39,7 @@ #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"); @@ -59,7 +57,7 @@ class LatticeVal { enum LatticeValueTy { /// undefined - This LLVM Value has no known value yet. undefined, - + /// constant - This LLVM Value has a specific constant value. constant, @@ -68,7 +66,7 @@ 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 @@ -77,30 +75,30 @@ class LatticeVal { /// 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: LatticeVal() : Val(0, undefined) {} - + bool isUndefined() const { return getLatticeValue() == undefined; } bool isConstant() const { return getLatticeValue() == constant || getLatticeValue() == forcedconstant; } bool isOverdefined() const { return getLatticeValue() == overdefined; } - + 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; } @@ -111,17 +109,17 @@ public: 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(getLatticeValue() == forcedconstant && + 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. @@ -137,7 +135,7 @@ public: return dyn_cast(getConstant()); return 0; } - + void markForcedConstant(Constant *V) { assert(isUndefined() && "Can't force a defined value!"); Val.setInt(forcedconstant); @@ -156,9 +154,15 @@ namespace { /// class SCCPSolver : public InstVisitor { const TargetData *TD; - SmallPtrSet BBExecutable;// The BBs that are executable. + 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 /// the global, to the currently known value. If the value becomes @@ -174,6 +178,15 @@ class SCCPSolver : public InstVisitor { /// that return multiple values. DenseMap, LatticeVal> TrackedMultipleRetVals; + /// 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. @@ -187,16 +200,13 @@ class SCCPSolver : public InstVisitor { 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: - SCCPSolver(const TargetData *td) : TD(td) {} + 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. @@ -204,7 +214,7 @@ public: /// This returns true if the block was not considered live before. bool MarkBlockExecutable(BasicBlock *BB) { if (!BBExecutable.insert(BB)) return false; - DEBUG(errs() << "Marking Block Executable: " << BB->getName() << "\n"); + DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n"); BBWorkList.push_back(BB); // Add the block to the work list! return true; } @@ -214,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()); @@ -227,7 +237,8 @@ public: /// this method must be called. void AddTrackedFunction(Function *F) { // 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())); @@ -235,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(); @@ -256,6 +271,13 @@ public: 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() { @@ -269,9 +291,20 @@ public: } 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 @@ -279,32 +312,41 @@ private: // void markConstant(LatticeVal &IV, Value *V, Constant *C) { if (!IV.markConstant(C)) return; - DEBUG(errs() << "markConstant: " << *C << ": " << *V << '\n'); - InstWorkList.push_back(V); + DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n'); + if (IV.isOverdefined()) + OverdefinedInstWorkList.push_back(V); + else + InstWorkList.push_back(V); } - + 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) { - ValueState[V].markForcedConstant(C); - DEBUG(errs() << "markForcedConstant: " << *C << ": " << *V << '\n'); - InstWorkList.push_back(V); + 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. void markOverdefined(LatticeVal &IV, Value *V) { if (!IV.markOverdefined()) return; - - DEBUG(errs() << "markOverdefined: "; + + DEBUG(dbgs() << "markOverdefined: "; if (Function *F = dyn_cast(V)) - errs() << "Function '" << F->getName() << "'\n"; + dbgs() << "Function '" << F->getName() << "'\n"; else - errs() << *V << '\n'); + dbgs() << *V << '\n'); // Only instructions go on the work list OverdefinedInstWorkList.push_back(V); } @@ -319,8 +361,9 @@ private: else if (IV.getConstant() != MergeWithV.getConstant()) markOverdefined(IV, V); } - + void mergeInValue(Value *V, LatticeVal MergeWithV) { + assert(!V->getType()->isStructTy() && "Should use other method"); mergeInValue(ValueState[V], V, MergeWithV); } @@ -329,21 +372,57 @@ private: /// value. This function handles the case when the value hasn't been seen yet /// by properly seeding constants etc. LatticeVal &getValueState(Value *V) { - DenseMap::iterator I = ValueState.find(V); - if (I != ValueState.end()) return I->second; // Common case, in the map + assert(!V->getType()->isStructTy() && "Should use getStructValueState"); - LatticeVal &LV = ValueState[V]; + 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)) { // Undef values remain undefined. if (!isa(V)) LV.markConstant(C); // Constants are constant } - + + // All others are underdefined by default. + return LV; + } + + /// 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) { @@ -354,7 +433,7 @@ private: // 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. - DEBUG(errs() << "Marking Edge Executable: " << Source->getName() + DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() << " -> " << Dest->getName() << "\n"); PHINode *PN; @@ -382,20 +461,6 @@ private: if (BBExecutable.count(I->getParent())) // Inst is executable? visit(*I); } - - /// RemoveFromOverdefinedPHIs - If I has any entries in the - /// UsersOfOverdefinedPHIs map for PN, remove them now. - void RemoveFromOverdefinedPHIs(Instruction *I, PHINode *PN) { - if (UsersOfOverdefinedPHIs.empty()) return; - std::multimap::iterator It, E; - tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN); - while (It != E) { - if (It->second == I) - UsersOfOverdefinedPHIs.erase(It++); - else - ++It; - } - } private: friend class InstVisitor; @@ -418,29 +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 (StoreInst &I); void visitLoadInst (LoadInst &I); void visitGetElementPtrInst(GetElementPtrInst &I); void visitCallInst (CallInst &I) { - 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 + dbgs() << "SCCP: Don't know how to handle: " << I; + markAnythingOverdefined(&I); // Just in case } }; @@ -458,7 +527,7 @@ void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, Succs[0] = true; return; } - + LatticeVal BCValue = getValueState(BI->getCondition()); ConstantInt *CI = BCValue.getConstantInt(); if (CI == 0) { @@ -468,42 +537,46 @@ void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, Succs[0] = Succs[1] = true; return; } - + // 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; 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! if (!SCValue.isUndefined()) Succs.assign(TI.getNumSuccessors(), true); return; } - - Succs[SI->findCaseValue(CI)] = true; + + 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 - errs() << "Unknown terminator instruction: " << TI << '\n'; + dbgs() << "Unknown terminator instruction: " << TI << '\n'; #endif llvm_unreachable("SCCP: Don't know how to handle this terminator!"); } @@ -523,7 +596,7 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { if (BranchInst *BI = dyn_cast(TI)) { if (BI->isUnconditional()) return true; - + LatticeVal BCValue = getValueState(BI->getCondition()); // Overdefined condition variables mean the branch could go either way, @@ -531,39 +604,35 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { 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; - + if (SwitchInst *SI = dyn_cast(TI)) { + if (SI->getNumCases() < 1) + return true; + LatticeVal SCValue = getValueState(SI->getCondition()); ConstantInt *CI = SCValue.getConstantInt(); - + if (CI == 0) return !SCValue.isUndefined(); - // 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) == CI) // Found the taken branch. - return SI->getSuccessor(i) == To; - - // If the constant value is not equal to any of the branches, we must - // execute default branch. - return SI->getDefaultDest() == To; + 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)) + if (isa(TI)) return true; - + #ifndef NDEBUG - errs() << "Unknown terminator instruction: " << *TI << '\n'; + dbgs() << "Unknown terminator instruction: " << *TI << '\n'; #endif llvm_unreachable(0); } @@ -587,22 +656,13 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { // successors executable. // void SCCPSolver::visitPHINode(PHINode &PN) { - if (getValueState(&PN).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) - return; - - SmallVector Users; - for (; I != E; ++I) - Users.push_back(I->second); - while (!Users.empty()) - visit(Users.pop_back_val()); + // 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. @@ -622,7 +682,7 @@ void SCCPSolver::visitPHINode(PHINode &PN) { if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) continue; - + if (IV.isOverdefined()) // PHI node becomes overdefined! return markOverdefined(&PN); @@ -630,11 +690,11 @@ void SCCPSolver::visitPHINode(PHINode &PN) { 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) @@ -657,28 +717,26 @@ void SCCPSolver::visitReturnInst(ReturnInst &I) { if (I.getNumOperands() == 0) return; // ret void Function *F = I.getParent()->getParent(); - + Value *ResultOp = I.getOperand(0); + // If we are tracking the return value of this function, merge it in. - if (!TrackedRetVals.empty()) { + if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) { DenseMap::iterator TFRVI = TrackedRetVals.find(F); if (TFRVI != TrackedRetVals.end()) { - mergeInValue(TFRVI->second, F, getValueState(I.getOperand(0))); + mergeInValue(TFRVI->second, F, getValueState(ResultOp)); return; } } - + // Handle functions that return multiple values. - if (!TrackedMultipleRetVals.empty() && - 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)); + } } @@ -699,100 +757,89 @@ void SCCPSolver::visitCastInst(CastInst &I) { if (OpSt.isOverdefined()) // Inherit overdefinedness of operand markOverdefined(&I); else if (OpSt.isConstant()) // Propagate constant value - markConstant(&I, ConstantExpr::getCast(I.getOpcode(), + 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; +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); - // Currently only handle single-index extractvalues. + // If this is extracting from more than one level of struct, we don't know. if (EVI.getNumIndices() != 1) return markOverdefined(&EVI); - - 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()) - return markOverdefined(&EVI); - - // 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()))) + + 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(); - - // If the operands to the insertvalue are undef, the result is undef. - if (isa(Aggr) && isa(Val)) - return; + StructType *STy = dyn_cast(IVI.getType()); + if (STy == 0) + return markOverdefined(&IVI); - // Currently only handle single-index insertvalues. + // If this has more than one index, we can't handle it, drive all results to + // undef. if (IVI.getNumIndices() != 1) - return markOverdefined(&IVI); + 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()) - return markOverdefined(&IVI); - - const Value *V = *TmpIVI->use_begin(); - if (isa(V)) - break; - TmpIVI = dyn_cast(V); - if (!TmpIVI) - return markOverdefined(&IVI); + 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; + } + + 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) { + // 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 (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() && + if (TVal.isConstant() && FVal.isConstant() && TVal.getConstant() == FVal.getConstant()) return markConstant(&I, FVal.getConstant()); @@ -807,7 +854,7 @@ void SCCPSolver::visitSelectInst(SelectInst &I) { 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; @@ -815,14 +862,14 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { 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) { @@ -837,14 +884,14 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { // Could annihilate value. if (I.getOpcode() == Instruction::And) markConstant(IV, &I, Constant::getNullValue(I.getType())); - else if (const VectorType *PT = dyn_cast(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 (I.getOpcode() == Instruction::And) { // X and 0 = 0 if (NonOverdefVal->getConstant()->isNullValue()) @@ -858,64 +905,6 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { } - // 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! - } - - 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; - } - - 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. - RemoveFromOverdefinedPHIs(&I, PN1); - RemoveFromOverdefinedPHIs(&I, PN2); - } - markOverdefined(&I); } @@ -928,81 +917,19 @@ void SCCPSolver::visitCmpInst(CmpInst &I) { if (IV.isOverdefined()) return; if (V1State.isConstant() && V2State.isConstant()) - return markConstant(IV, &I, ConstantExpr::getCompare(I.getPredicate(), - V1State.getConstant(), + return markConstant(IV, &I, ConstantExpr::getCompare(I.getPredicate(), + V1State.getConstant(), V2State.getConstant())); - + // If operands are still undefined, wait for it to resolve. if (!V1State.isOverdefined() && !V2State.isOverdefined()) return; - - // If something is overdefined, use some tricks to avoid ending up and over - // defined if we can. - - // 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! - } - - 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(&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; - } - - 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. - RemoveFromOverdefinedPHIs(&I, PN1); - RemoveFromOverdefinedPHIs(&I, PN2); - } markOverdefined(&I); } void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) { - // FIXME : SCCP does not handle vectors properly. + // TODO : SCCP does not handle vectors properly. return markOverdefined(&I); #if 0 @@ -1018,7 +945,7 @@ void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) { } void SCCPSolver::visitInsertElementInst(InsertElementInst &I) { - // FIXME : SCCP does not handle vectors properly. + // TODO : SCCP does not handle vectors properly. return markOverdefined(&I); #if 0 LatticeVal &ValState = getValueState(I.getOperand(0)); @@ -1034,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())); @@ -1042,7 +969,7 @@ void SCCPSolver::visitInsertElementInst(InsertElementInst &I) { } void SCCPSolver::visitShuffleVectorInst(ShuffleVectorInst &I) { - // FIXME : SCCP does not handle vectors properly. + // TODO : SCCP does not handle vectors properly. return markOverdefined(&I); #if 0 LatticeVal &V1State = getValueState(I.getOperand(0)); @@ -1052,17 +979,17 @@ 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)); } @@ -1082,7 +1009,7 @@ void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { LatticeVal State = getValueState(I.getOperand(i)); if (State.isUndefined()) return; // Operands are not resolved yet. - + if (State.isOverdefined()) return markOverdefined(&I); @@ -1091,14 +1018,18 @@ void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { } Constant *Ptr = Operands[0]; - markConstant(&I, ConstantExpr::getGetElementPtr(Ptr, &Operands[0]+1, - Operands.size()-1)); + ArrayRef Indices(Operands.begin() + 1, Operands.end()); + markConstant(&I, ConstantExpr::getGetElementPtr(Ptr, Indices)); } 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; @@ -1113,21 +1044,25 @@ void SCCPSolver::visitStoreInst(StoreInst &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; if (!PtrVal.isConstant() || I.isVolatile()) return markOverdefined(IV, &I); - + 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()) { @@ -1153,7 +1088,7 @@ 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. @@ -1161,17 +1096,17 @@ void SCCPSolver::visitCallSite(CallSite CS) { 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 (F && F->isDeclaration() && !isa(I->getType()) && + 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); - + if (State.isUndefined()) return; // Operands are not resolved yet. if (State.isOverdefined()) @@ -1179,72 +1114,62 @@ CallOverdefined: 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())) + if (Constant *C = ConstantFoldCall(F, Operands, TLI)) return markConstant(I, C); } // Otherwise, we don't know anything about this call, mark it overdefined. - return markOverdefined(I); + 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. - 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; - } - - mergeInValue(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); } } @@ -1257,7 +1182,7 @@ void SCCPSolver::Solve() { while (!OverdefinedInstWorkList.empty()) { 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 @@ -1271,12 +1196,12 @@ void SCCPSolver::Solve() { if (Instruction *I = dyn_cast(*UI)) OperandChangedState(I); } - + // Process the instruction work list. while (!InstWorkList.empty()) { 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 made the transition from undef to // constant. @@ -1285,7 +1210,7 @@ void SCCPSolver::Solve() { // since all of its users will have already been marked as overdefined. // 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) if (Instruction *I = dyn_cast(*UI)) @@ -1297,7 +1222,7 @@ void SCCPSolver::Solve() { 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. @@ -1328,48 +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. + // 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. + 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(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. 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: @@ -1377,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(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(I, Op0LV.getConstant()); - else - markOverdefined(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. + // 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. @@ -1417,60 +1413,89 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { } else { // Leave Op1LV as Operand(1)'s LatticeValue. } - + if (Op1LV.isConstant()) markForcedConstant(I, Op1LV.getConstant()); else 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(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(BI->getContext())); - } 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; @@ -1484,23 +1509,24 @@ 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. FunctionPass *llvm::createSCCPPass() { @@ -1508,17 +1534,27 @@ FunctionPass *llvm::createSCCPPass() { } static void DeleteInstructionInBlock(BasicBlock *BB) { - DEBUG(errs() << " BasicBlock Dead:" << *BB); + DEBUG(dbgs() << " 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. - while (!isa(BB->begin())) { - Instruction *I = --BasicBlock::iterator(BB->getTerminator()); - - if (!I->use_empty()) - I->replaceAllUsesWith(UndefValue::get(I->getType())); - BB->getInstList().erase(I); + + // 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; } } @@ -1527,21 +1563,23 @@ static void DeleteInstructionInBlock(BasicBlock *BB) { // and return true if the function was modified. // bool SCCP::runOnFunction(Function &F) { - DEBUG(errs() << "SCCP on function '" << F.getName() << "'\n"); - SCCPSolver Solver(getAnalysisIfAvailable()); + 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); } @@ -1557,7 +1595,7 @@ bool SCCP::runOnFunction(Function &F) { MadeChanges = true; continue; } - + // Iterate over all of the instructions in a function, replacing them with // constants if we have found them to be of constant values. // @@ -1565,21 +1603,25 @@ bool SCCP::runOnFunction(Function &F) { 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(errs() << " Constant: " << *Const << " = " << *Inst); + 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; @@ -1596,15 +1638,25 @@ 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"); +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() { @@ -1612,33 +1664,45 @@ ModulePass *llvm::createIPSCCPPass() { } -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. - if (UI.getOperandNo() != 0) + 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(*UI)) { + } 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) { - SCCPSolver Solver(getAnalysisIfAvailable()); + 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. @@ -1646,26 +1710,31 @@ bool IPSCCP::runOnModule(Module &M) { 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() && - !isa(F->getReturnType())) + 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() && !AddressIsTaken(F)) - continue; + 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.markOverdefined(AI); + Solver.markAnythingOverdefined(AI); } // Loop over global variables. We inform the solver about any internal global @@ -1681,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); @@ -1698,15 +1767,18 @@ bool IPSCCP::runOnModule(Module &M) { if (Solver.isBlockExecutable(F->begin())) { for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; ++AI) { - if (AI->use_empty()) continue; - + 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(errs() << "*** Arg " << *AI << " = " << *CST <<"\n"); - + DEBUG(dbgs() << "*** Arg " << *AI << " = " << *CST <<"\n"); + // Replaces all of the uses of a variable with uses of the // constant. AI->replaceAllUsesWith(CST); @@ -1735,24 +1807,27 @@ bool IPSCCP::runOnModule(Module &M) { new UnreachableInst(M.getContext(), BB); continue; } - + for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { Instruction *Inst = BI++; - if (Inst->getType()->isVoidTy()) + 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(errs() << " Constant: " << *Const << " = " << *Inst); + 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(); @@ -1769,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 @@ -1786,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(); } @@ -1810,6 +1893,14 @@ 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(), @@ -1817,18 +1908,24 @@ bool IPSCCP::runOnModule(Module &M) { 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() || AddressIsTaken(F)) + 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))) - RI->setOperand(0, UndefValue::get(F->getReturnType())); + 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(), @@ -1836,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();