X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FSCCP.cpp;h=f0b5d7702e37f13d7ba60f435fbdd3d16321e68f;hb=ca74940fee04662a61cee290a1b04ef2f2b52c09;hp=4ead2757b47bf06ffd9d767d9ec464c57fb5abc1;hpb=794fd75c67a2cdc128d67342c6d88a504d186896;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp index 4ead2757b47..f0b5d7702e3 100644 --- a/lib/Transforms/Scalar/SCCP.cpp +++ b/lib/Transforms/Scalar/SCCP.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -27,25 +27,31 @@ #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/MallocHelper.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Support/CallSite.h" -#include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/InstVisitor.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/SmallSet.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 ofinstructions removed by IPSCCP"); +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"); @@ -54,7 +60,7 @@ namespace { /// LatticeVal class - This class represents the different lattice values that /// an LLVM value may occupy. It is a simple class with value semantics. /// -class VISIBILITY_HIDDEN LatticeVal { +class LatticeVal { enum { /// undefined - This LLVM Value has no known value yet. undefined, @@ -129,16 +135,14 @@ public: } }; -} // end anonymous namespace - - //===----------------------------------------------------------------------===// // /// SCCPSolver - This class is a general purpose solver for Sparse Conditional /// Constant Propagation. /// class SCCPSolver : public InstVisitor { - SmallSet BBExecutable;// The basic blocks that are executable + LLVMContext *Context; + DenseSet BBExecutable;// The basic blocks that are executable std::map ValueState; // The state each value is in. /// GlobalValue - If we are tracking any values for the contents of a global @@ -147,10 +151,14 @@ class SCCPSolver : public InstVisitor { /// overdefined, it's entry is simply removed from this map. DenseMap TrackedGlobals; - /// TrackedFunctionRetVals - If we are tracking arguments into and the return + /// TrackedRetVals - If we are tracking arguments into and the return /// value out of a function, it will have an entry in this map, indicating /// what the known return value for the function is. - DenseMap TrackedFunctionRetVals; + DenseMap TrackedRetVals; + + /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions + /// 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 @@ -158,11 +166,11 @@ class SCCPSolver : public InstVisitor { // By having a separate worklist, we accomplish this because everything // possibly overdefined will become overdefined at the soonest possible // point. - std::vector OverdefinedInstWorkList; - std::vector InstWorkList; + SmallVector OverdefinedInstWorkList; + SmallVector InstWorkList; - std::vector BBWorkList; // The BasicBlock work list + 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. @@ -170,14 +178,15 @@ class SCCPSolver : public InstVisitor { /// KnownFeasibleEdges - Entries in this set are edges which have already had /// PHI nodes retriggered. - typedef std::pair Edge; - std::set KnownFeasibleEdges; + typedef std::pair Edge; + DenseSet KnownFeasibleEdges; public: + void setContext(LLVMContext *C) { Context = C; } /// 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) { - DOUT << "Marking Block Executable: " << BB->getName() << "\n"; + DEBUG(errs() << "Marking Block Executable: " << BB->getName() << "\n"); BBExecutable.insert(BB); // Basic block is executable! BBWorkList.push_back(BB); // Add the block to the work list! } @@ -199,9 +208,14 @@ public: /// and out of the specified function (which cannot have its address taken), /// this method must be called. void AddTrackedFunction(Function *F) { - assert(F->hasInternalLinkage() && "Can only track internal functions!"); + assert(F->hasLocalLinkage() && "Can only track internal functions!"); // Add an entry, F -> undef. - TrackedFunctionRetVals[F]; + if (const StructType *STy = dyn_cast(F->getReturnType())) { + for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) + TrackedMultipleRetVals.insert(std::make_pair(std::make_pair(F, i), + LatticeVal())); + } else + TrackedRetVals.insert(std::make_pair(F, LatticeVal())); } /// Solve - Solve for constants and executable blocks. @@ -215,10 +229,8 @@ public: /// should be rerun. bool ResolvedUndefsIn(Function &F); - /// getExecutableBlocks - Once we have solved for constants, return the set of - /// blocks that is known to be executable. - SmallSet &getExecutableBlocks() { - return BBExecutable; + bool isBlockExecutable(BasicBlock *BB) const { + return BBExecutable.count(BB); } /// getValueMapping - Once we have solved for constants, return the mapping of @@ -227,10 +239,10 @@ public: return ValueState; } - /// getTrackedFunctionRetVals - Get the inferred return value map. + /// getTrackedRetVals - Get the inferred return value map. /// - const DenseMap &getTrackedFunctionRetVals() { - return TrackedFunctionRetVals; + const DenseMap &getTrackedRetVals() { + return TrackedRetVals; } /// getTrackedGlobals - Get and return the set of inferred initializers for @@ -250,14 +262,14 @@ private: // inline void markConstant(LatticeVal &IV, Value *V, Constant *C) { if (IV.markConstant(C)) { - DOUT << "markConstant: " << *C << ": " << *V; + DEBUG(errs() << "markConstant: " << *C << ": " << *V << '\n'); InstWorkList.push_back(V); } } inline void markForcedConstant(LatticeVal &IV, Value *V, Constant *C) { IV.markForcedConstant(C); - DOUT << "markForcedConstant: " << *C << ": " << *V; + DEBUG(errs() << "markForcedConstant: " << *C << ": " << *V << '\n'); InstWorkList.push_back(V); } @@ -268,14 +280,13 @@ private: // 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(DOUT << "markOverdefined: "; + DEBUG(errs() << "markOverdefined: "; if (Function *F = dyn_cast(V)) - DOUT << "Function '" << F->getName() << "'\n"; + errs() << "Function '" << F->getName() << "'\n"; else - DOUT << *V); + errs() << *V << '\n'); // Only instructions go on the work list OverdefinedInstWorkList.push_back(V); } @@ -328,8 +339,8 @@ private: return; // This edge is already known to be executable! if (BBExecutable.count(Dest)) { - DOUT << "Marking Edge Executable: " << Source->getName() - << " -> " << Dest->getName() << "\n"; + DEBUG(errs() << "Marking Edge Executable: " << Source->getName() + << " -> " << Dest->getName() << "\n"); // The destination is already executable, but we just made an edge // feasible that wasn't before. Revisit the PHI nodes in the block @@ -383,12 +394,19 @@ private: void visitExtractElementInst(ExtractElementInst &I); void visitInsertElementInst(InsertElementInst &I); void visitShuffleVectorInst(ShuffleVectorInst &I); + void visitExtractValueInst(ExtractValueInst &EVI); + void visitInsertValueInst(InsertValueInst &IVI); // Instructions that cannot be folded away... void visitStoreInst (Instruction &I); void visitLoadInst (LoadInst &I); void visitGetElementPtrInst(GetElementPtrInst &I); - void visitCallInst (CallInst &I) { visitCallSite(CallSite::get(&I)); } + void visitCallInst (CallInst &I) { + if (isMalloc(&I)) + markOverdefined(&I); + else + visitCallSite(CallSite::get(&I)); + } void visitInvokeInst (InvokeInst &II) { visitCallSite(CallSite::get(&II)); visitTerminatorInst(II); @@ -403,11 +421,14 @@ private: void visitInstruction(Instruction &I) { // If a new instruction is added to LLVM that we don't handle... - cerr << "SCCP: Don't know how to handle: " << I; + errs() << "SCCP: Don't know how to handle: " << I; markOverdefined(&I); // Just in case } }; +} // end anonymous namespace + + // getFeasibleSuccessors - Return a vector of booleans to indicate which // successors are reachable from a given terminator instruction. // @@ -426,7 +447,7 @@ void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, 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()] = true; + Succs[BCValue.getConstant() == ConstantInt::getFalse(*Context)] = true; } } } else if (isa(&TI)) { @@ -438,22 +459,10 @@ void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, (SCValue.isConstant() && !isa(SCValue.getConstant()))) { // All destinations are executable! Succs.assign(TI.getNumSuccessors(), true); - } else if (SCValue.isConstant()) { - Constant *CPV = SCValue.getConstant(); - // 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 right branch... - Succs[i] = true; - return; - } - } - - // Constant value not equal to any of the branches... must execute - // default branch then... - Succs[0] = true; - } + } else if (SCValue.isConstant()) + Succs[SI->findCaseValue(cast(SCValue.getConstant()))] = true; } else { - assert(0 && "SCCP: Don't know how to handle this terminator!"); + llvm_unreachable("SCCP: Don't know how to handle this terminator!"); } } @@ -483,7 +492,7 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { // Constant condition variables mean the branch can only go a single way return BI->getSuccessor(BCValue.getConstant() == - ConstantInt::getFalse()) == To; + ConstantInt::getFalse(*Context)) == To; } return false; } @@ -511,8 +520,10 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { } return false; } else { - cerr << "Unknown terminator instruction: " << *TI; - abort(); +#ifndef NDEBUG + errs() << "Unknown terminator instruction: " << *TI << '\n'; +#endif + llvm_unreachable(0); } } @@ -573,7 +584,7 @@ void SCCPSolver::visitPHINode(PHINode &PN) { if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) { if (IV.isOverdefined()) { // PHI node becomes overdefined! - markOverdefined(PNIV, &PN); + markOverdefined(&PN); return; } @@ -589,7 +600,7 @@ void SCCPSolver::visitPHINode(PHINode &PN) { // Yes there is. This means the PHI node is not constant. // You must be overdefined poor PHI. // - markOverdefined(PNIV, &PN); // The PHI node now becomes overdefined + markOverdefined(&PN); // The PHI node now becomes overdefined return; // I'm done analyzing you } } @@ -602,26 +613,50 @@ void SCCPSolver::visitPHINode(PHINode &PN) { // this is the case, the PHI remains undefined. // if (OperandVal) - markConstant(PNIV, &PN, OperandVal); // Acquire operand value + markConstant(&PN, OperandVal); // Acquire operand value } void SCCPSolver::visitReturnInst(ReturnInst &I) { if (I.getNumOperands() == 0) return; // Ret void - // If we are tracking the return value of this function, merge it in. Function *F = I.getParent()->getParent(); - if (F->hasInternalLinkage() && !TrackedFunctionRetVals.empty()) { + // If we are tracking the return value of this function, merge it in. + if (!F->hasLocalLinkage()) + return; + + if (!TrackedRetVals.empty() && I.getNumOperands() == 1) { DenseMap::iterator TFRVI = - TrackedFunctionRetVals.find(F); - if (TFRVI != TrackedFunctionRetVals.end() && + TrackedRetVals.find(F); + if (TFRVI != TrackedRetVals.end() && !TFRVI->second.isOverdefined()) { LatticeVal &IV = getValueState(I.getOperand(0)); mergeInValue(TFRVI->second, F, IV); + 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)); } } } - void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) { SmallVector SuccFeasible; getFeasibleSuccessors(TI, SuccFeasible); @@ -644,6 +679,88 @@ void SCCPSolver::visitCastInst(CastInst &I) { VState.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; + } + + // 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; + + // Currently only handle single-index insertvalues. + if (IVI.getNumIndices() != 1) { + markOverdefined(&IVI); + return; + } + + // 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; + } + const Value *V = *TmpIVI->use_begin(); + if (isa(V)) + break; + TmpIVI = dyn_cast(V); + if (!TmpIVI) { + markOverdefined(&IVI); + return; + } + } + + // 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 (CondValue.isUndefined()) @@ -703,9 +820,10 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { if (I.getOpcode() == Instruction::And) markConstant(IV, &I, Constant::getNullValue(I.getType())); else if (const VectorType *PT = dyn_cast(I.getType())) - markConstant(IV, &I, ConstantVector::getAllOnesValue(PT)); + markConstant(IV, &I, Constant::getAllOnesValue(PT)); else - markConstant(IV, &I, ConstantInt::getAllOnesValue(I.getType())); + markConstant(IV, &I, + Constant::getAllOnesValue(I.getType())); return; } else { if (I.getOpcode() == Instruction::And) { @@ -749,7 +867,8 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { 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(), + Constant *V = + ConstantExpr::get(I.getOpcode(), In1.getConstant(), In2.getConstant()); if (Result.isUndefined()) Result.markConstant(V); @@ -797,7 +916,8 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { markOverdefined(IV, &I); } else if (V1State.isConstant() && V2State.isConstant()) { - markConstant(IV, &I, ConstantExpr::get(I.getOpcode(), V1State.getConstant(), + markConstant(IV, &I, + ConstantExpr::get(I.getOpcode(), V1State.getConstant(), V2State.getConstant())); } } @@ -1015,7 +1135,8 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { if (PtrVal.isUndefined()) return; // The pointer is not resolved yet! if (PtrVal.isConstant() && !I.isVolatile()) { Value *Ptr = PtrVal.getConstant(); - if (isa(Ptr)) { + // 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; @@ -1024,7 +1145,7 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { // Transform load (constant global) into the value loaded. if (GlobalVariable *GV = dyn_cast(Ptr)) { if (GV->isConstant()) { - if (!GV->isDeclaration()) { + if (GV->hasDefinitiveInitializer()) { markConstant(IV, &I, GV->getInitializer()); return; } @@ -1043,9 +1164,10 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { if (ConstantExpr *CE = dyn_cast(Ptr)) if (CE->getOpcode() == Instruction::GetElementPtr) if (GlobalVariable *GV = dyn_cast(CE->getOperand(0))) - if (GV->isConstant() && !GV->isDeclaration()) + if (GV->isConstant() && GV->hasDefinitiveInitializer()) if (Constant *V = - ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE)) { + ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE, + *Context)) { markConstant(IV, &I, V); return; } @@ -1058,64 +1180,96 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { void SCCPSolver::visitCallSite(CallSite CS) { Function *F = CS.getCalledFunction(); - - // If we are tracking this function, we must make sure to bind arguments as - // appropriate. - DenseMap::iterator TFRVI =TrackedFunctionRetVals.end(); - if (F && F->hasInternalLinkage()) - TFRVI = TrackedFunctionRetVals.find(F); - - if (TFRVI != TrackedFunctionRetVals.end()) { - // If this is the first call to the function hit, mark its entry block - // executable. - if (!BBExecutable.count(F->begin())) - MarkBlockExecutable(F->begin()); - - 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 (!IV.isOverdefined()) - mergeInValue(IV, AI, getValueState(*CAI)); - } - } Instruction *I = CS.getInstruction(); - if (I->getType() == Type::VoidTy) return; - - LatticeVal &IV = ValueState[I]; - if (IV.isOverdefined()) return; - - // Propagate the return value of the function to the value of the instruction. - if (TFRVI != TrackedFunctionRetVals.end()) { - mergeInValue(IV, I, TFRVI->second); - return; - } + + // 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()) { +CallOverdefined: + // Void return and not tracking callee, just bail. + if (I->getType() == Type::getVoidTy(I->getContext())) 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() && + 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. + else if (State.isOverdefined()) { + markOverdefined(I); + return; + } + 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 (F == 0 || !F->isDeclaration() || !canConstantFoldCallTo(F)) { - markOverdefined(IV, I); + // Otherwise, we don't know anything about this call, mark it overdefined. + markOverdefined(I); return; } - SmallVector Operands; - Operands.reserve(I->getNumOperands()-1); - - 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... - else if (State.isOverdefined()) { - markOverdefined(IV, I); - return; + // 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; + + // 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; + } + } + // The aggregate value is used in a way not handled here. Assume nothing. + markOverdefined(*UI); } - assert(State.isConstant() && "Unknown state!"); - Operands.push_back(State.getConstant()); + } 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 (!IV.isOverdefined()) + mergeInValue(IV, AI, getValueState(*CAI)); } - - if (Constant *C = ConstantFoldCall(F, &Operands[0], Operands.size())) - markConstant(IV, I, C); - else - markOverdefined(IV, I); } @@ -1128,7 +1282,7 @@ void SCCPSolver::Solve() { Value *I = OverdefinedInstWorkList.back(); OverdefinedInstWorkList.pop_back(); - DOUT << "\nPopped off OI-WL: " << *I; + DEBUG(errs() << "\nPopped off OI-WL: " << *I << '\n'); // "I" got into the work list because it either made the transition from // bottom to constant @@ -1146,7 +1300,7 @@ void SCCPSolver::Solve() { Value *I = InstWorkList.back(); InstWorkList.pop_back(); - DOUT << "\nPopped off I-WL: " << *I; + DEBUG(errs() << "\nPopped off I-WL: " << *I << '\n'); // "I" got into the work list because it either made the transition from // bottom to constant @@ -1166,7 +1320,7 @@ void SCCPSolver::Solve() { BasicBlock *BB = BBWorkList.back(); BBWorkList.pop_back(); - DOUT << "\nPopped off BBWL: " << *BB; + DEBUG(errs() << "\nPopped off BBWL: " << *BB << '\n'); // Notify all instructions in this basic block that they are newly // executable. @@ -1200,7 +1354,7 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { // Look for instructions which produce undef values. - if (I->getType() == Type::VoidTy) continue; + if (I->getType() == Type::getVoidTy(F.getContext())) continue; LatticeVal &LV = getValueState(I); if (!LV.isUndefined()) continue; @@ -1238,9 +1392,10 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { case Instruction::Or: // undef | X -> -1. X could be -1. if (const VectorType *PTy = dyn_cast(ITy)) - markForcedConstant(LV, I, ConstantVector::getAllOnesValue(PTy)); + markForcedConstant(LV, I, + Constant::getAllOnesValue(PTy)); else - markForcedConstant(LV, I, ConstantInt::getAllOnesValue(ITy)); + markForcedConstant(LV, I, Constant::getAllOnesValue(ITy)); return true; case Instruction::SDiv: @@ -1296,6 +1451,12 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { else markOverdefined(LV, 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 + // overdefined. + markOverdefined(LV, I); + return true; } } @@ -1305,21 +1466,38 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { if (!getValueState(BI->getCondition()).isUndefined()) continue; } else if (SwitchInst *SI = dyn_cast(TI)) { + if (SI->getNumSuccessors()<2) // no cases + continue; if (!getValueState(SI->getCondition()).isUndefined()) continue; } else { continue; } - // If the edge to the first successor isn't thought to be feasible yet, mark - // it so now. - if (KnownFeasibleEdges.count(Edge(BB, TI->getSuccessor(0)))) + // 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(0)); + 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)); + } + return true; } @@ -1333,9 +1511,9 @@ namespace { /// SCCP Class - This class uses the SCCPSolver to implement a per-function /// Sparse Conditional Constant Propagator. /// - struct VISIBILITY_HIDDEN SCCP : public FunctionPass { - static const int ID; // Pass identifcation, replacement for typeid - SCCP() : FunctionPass((intptr_t)&ID) {} + struct SCCP : public FunctionPass { + static char ID; // Pass identification, replacement for typeid + SCCP() : FunctionPass(&ID) {} // runOnFunction - Run the Sparse Conditional Constant Propagation // algorithm, and return true if the function was modified. @@ -1346,11 +1524,11 @@ namespace { AU.setPreservesCFG(); } }; - - const int SCCP::ID = 0; - RegisterPass X("sccp", "Sparse Conditional Constant Propagation"); } // end anonymous namespace +char SCCP::ID = 0; +static RegisterPass +X("sccp", "Sparse Conditional Constant Propagation"); // createSCCPPass - This is the public interface to this file... FunctionPass *llvm::createSCCPPass() { @@ -1362,8 +1540,9 @@ FunctionPass *llvm::createSCCPPass() { // and return true if the function was modified. // bool SCCP::runOnFunction(Function &F) { - DOUT << "SCCP on function '" << F.getName() << "'\n"; + DEBUG(errs() << "SCCP on function '" << F.getName() << "'\n"); SCCPSolver Solver; + Solver.setContext(&F.getContext()); // Mark the first block of the function as being executable. Solver.MarkBlockExecutable(F.begin()); @@ -1376,7 +1555,7 @@ bool SCCP::runOnFunction(Function &F) { bool ResolvedUndefs = true; while (ResolvedUndefs) { Solver.Solve(); - DOUT << "RESOLVING UNDEFs\n"; + DEBUG(errs() << "RESOLVING UNDEFs\n"); ResolvedUndefs = Solver.ResolvedUndefsIn(F); } @@ -1386,13 +1565,12 @@ bool SCCP::runOnFunction(Function &F) { // delete their contents now. Note that we cannot actually delete the blocks, // as we cannot modify the CFG of the function. // - SmallSet &ExecutableBBs = Solver.getExecutableBlocks(); - SmallVector Insts; + SmallVector Insts; std::map &Values = Solver.getValueMapping(); for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) - if (!ExecutableBBs.count(BB)) { - DOUT << " BasicBlock Dead:" << *BB; + if (!Solver.isBlockExecutable(BB)) { + DEBUG(errs() << " BasicBlock Dead:" << *BB); ++NumDeadBlocks; // Delete the instructions backwards, as it has a reduced likelihood of @@ -1415,25 +1593,27 @@ bool SCCP::runOnFunction(Function &F) { // for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { Instruction *Inst = BI++; - if (Inst->getType() != Type::VoidTy) { - LatticeVal &IV = Values[Inst]; - if (IV.isConstant() || IV.isUndefined() && - !isa(Inst)) { - Constant *Const = IV.isConstant() - ? IV.getConstant() : UndefValue::get(Inst->getType()); - DOUT << " Constant: " << *Const << " = " << *Inst; - - // Replaces all of the uses of a variable with uses of the constant. - Inst->replaceAllUsesWith(Const); - - // Delete the instruction. - BB->getInstList().erase(Inst); + if (Inst->getType() == Type::getVoidTy(F.getContext()) || + 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); - // Hey, we just changed something! - MadeChanges = true; - ++NumInstRemoved; - } - } + // 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; } } @@ -1446,17 +1626,17 @@ namespace { /// IPSCCP Class - This class implements interprocedural Sparse Conditional /// Constant Propagation. /// - struct VISIBILITY_HIDDEN IPSCCP : public ModulePass { - static const int ID; - IPSCCP() : ModulePass((intptr_t)&ID) {} + struct IPSCCP : public ModulePass { + static char ID; + IPSCCP() : ModulePass(&ID) {} bool runOnModule(Module &M); }; - - const int IPSCCP::ID = 0; - RegisterPass - Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation"); } // 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... ModulePass *llvm::createIPSCCPPass() { return new IPSCCP(); @@ -1475,10 +1655,8 @@ static bool AddressIsTaken(GlobalValue *GV) { } else if (isa(*UI) || isa(*UI)) { // Make sure we are calling the function, not passing the address. CallSite CS = CallSite::get(cast(*UI)); - for (CallSite::arg_iterator AI = CS.arg_begin(), - E = CS.arg_end(); AI != E; ++AI) - if (*AI == GV) - return true; + if (CS.hasArgument(GV)) + return true; } else if (LoadInst *LI = dyn_cast(*UI)) { if (LI->isVolatile()) return true; @@ -1489,13 +1667,16 @@ static bool AddressIsTaken(GlobalValue *GV) { } bool IPSCCP::runOnModule(Module &M) { + LLVMContext *Context = &M.getContext(); + SCCPSolver Solver; + Solver.setContext(Context); // 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->hasInternalLinkage() || AddressIsTaken(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(); @@ -1510,7 +1691,7 @@ bool IPSCCP::runOnModule(Module &M) { // their addresses taken, we can propagate constants through them. for (Module::global_iterator G = M.global_begin(), E = M.global_end(); G != E; ++G) - if (!G->isConstant() && G->hasInternalLinkage() && !AddressIsTaken(G)) + if (!G->isConstant() && G->hasLocalLinkage() && !AddressIsTaken(G)) Solver.TrackValueOfGlobalVariable(G); // Solve for constants. @@ -1518,7 +1699,7 @@ bool IPSCCP::runOnModule(Module &M) { while (ResolvedUndefs) { Solver.Solve(); - DOUT << "RESOLVING UNDEFS\n"; + DEBUG(errs() << "RESOLVING UNDEFS\n"); ResolvedUndefs = false; for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) ResolvedUndefs |= Solver.ResolvedUndefsIn(*F); @@ -1529,9 +1710,8 @@ 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. // - SmallSet &ExecutableBBs = Solver.getExecutableBlocks(); - SmallVector Insts; - SmallVector BlocksToErase; + SmallVector Insts; + SmallVector BlocksToErase; std::map &Values = Solver.getValueMapping(); for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { @@ -1542,7 +1722,7 @@ bool IPSCCP::runOnModule(Module &M) { if (IV.isConstant() || IV.isUndefined()) { Constant *CST = IV.isConstant() ? IV.getConstant() : UndefValue::get(AI->getType()); - DOUT << "*** Arg " << *AI << " = " << *CST <<"\n"; + DEBUG(errs() << "*** Arg " << *AI << " = " << *CST <<"\n"); // Replaces all of the uses of a variable with uses of the // constant. @@ -1552,8 +1732,8 @@ bool IPSCCP::runOnModule(Module &M) { } for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) - if (!ExecutableBBs.count(BB)) { - DOUT << " BasicBlock Dead:" << *BB; + if (!Solver.isBlockExecutable(BB)) { + DEBUG(errs() << " BasicBlock Dead:" << *BB); ++IPNumDeadBlocks; // Delete the instructions backwards, as it has a reduced likelihood of @@ -1574,7 +1754,7 @@ bool IPSCCP::runOnModule(Module &M) { for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { BasicBlock *Succ = TI->getSuccessor(i); - if (Succ->begin() != Succ->end() && isa(Succ->begin())) + if (!Succ->empty() && isa(Succ->begin())) TI->getSuccessor(i)->removePredecessor(BB); } if (!TI->use_empty()) @@ -1584,32 +1764,33 @@ bool IPSCCP::runOnModule(Module &M) { if (&*BB != &F->front()) BlocksToErase.push_back(BB); else - new UnreachableInst(BB); + new UnreachableInst(M.getContext(), BB); } else { for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { Instruction *Inst = BI++; - if (Inst->getType() != Type::VoidTy) { - LatticeVal &IV = Values[Inst]; - if (IV.isConstant() || IV.isUndefined() && - !isa(Inst)) { - Constant *Const = IV.isConstant() - ? IV.getConstant() : UndefValue::get(Inst->getType()); - DOUT << " 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)) - BB->getInstList().erase(Inst); - - // Hey, we just changed something! - MadeChanges = true; - ++IPNumInstRemoved; - } - } + if (Inst->getType() == Type::getVoidTy(M.getContext())) + 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; } } @@ -1626,18 +1807,20 @@ bool IPSCCP::runOnModule(Module &M) { // The constant folder may not have been able to fold the terminator // if this is a branch or switch on undef. Fold it manually as a // branch to the first successor. +#ifndef NDEBUG if (BranchInst *BI = dyn_cast(I)) { assert(BI->isConditional() && isa(BI->getCondition()) && "Branch should be foldable!"); } else if (SwitchInst *SI = dyn_cast(I)) { assert(isa(SI->getCondition()) && "Switch should fold"); } else { - assert(0 && "Didn't fold away reference to block!"); + llvm_unreachable("Didn't fold away reference to block!"); } +#endif // Make this an uncond branch to the first successor. TerminatorInst *TI = I->getParent()->getTerminator(); - new BranchInst(TI->getSuccessor(0), TI); + 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) @@ -1658,11 +1841,12 @@ 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. - const DenseMap &RV =Solver.getTrackedFunctionRetVals(); + // 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() != Type::VoidTy) { + I->first->getReturnType() != Type::getVoidTy(M.getContext())) { Function *F = I->first; for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) if (ReturnInst *RI = dyn_cast(BB->getTerminator())) @@ -1678,7 +1862,7 @@ bool IPSCCP::runOnModule(Module &M) { GlobalVariable *GV = I->first; assert(!I->second.isOverdefined() && "Overdefined values should have been taken out of the map!"); - DOUT << "Found that GV '" << GV->getName()<< "' is constant!\n"; + DEBUG(errs() << "Found that GV '" << GV->getName() << "' is constant!\n"); while (!GV->use_empty()) { StoreInst *SI = cast(GV->use_back()); SI->eraseFromParent();