X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FSCCP.cpp;h=bc068f78c5765300e688684ad4e3554cb8a1ab0e;hb=aa1c57e324a08e5859b1efbf3e63bf6339613724;hp=5ce82b96245d5a50f2c77268181b4a8a95e2377d;hpb=3d3abe0852d5f499bed7ab014519dd582a0a795d;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp index 5ce82b96245..bc068f78c57 100644 --- a/lib/Transforms/Scalar/SCCP.cpp +++ b/lib/Transforms/Scalar/SCCP.cpp @@ -17,31 +17,32 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "sccp" #include "llvm/Transforms/Scalar.h" -#include "llvm/Transforms/IPO.h" -#include "llvm/Constants.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Instructions.h" -#include "llvm/Pass.h" -#include "llvm/Analysis/ConstantFolding.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" -#include "llvm/Support/InstVisitor.h" -#include "llvm/Support/raw_ostream.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/InstVisitor.h" +#include "llvm/IR/Instructions.h" +#include "llvm/Pass.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/IPO.h" +#include "llvm/Transforms/Utils/Local.h" #include using namespace llvm; +#define DEBUG_TYPE "sccp" + STATISTIC(NumInstRemoved, "Number of instructions removed"); STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable"); @@ -81,7 +82,7 @@ class LatticeVal { } public: - LatticeVal() : Val(0, undefined) {} + LatticeVal() : Val(nullptr, undefined) {} bool isUndefined() const { return getLatticeValue() == undefined; } bool isConstant() const { @@ -133,7 +134,7 @@ public: ConstantInt *getConstantInt() const { if (isConstant()) return dyn_cast(getConstant()); - return 0; + return nullptr; } void markForcedConstant(Constant *V) { @@ -153,7 +154,7 @@ namespace { /// Constant Propagation. /// class SCCPSolver : public InstVisitor { - const TargetData *TD; + const DataLayout &DL; const TargetLibraryInfo *TLI; SmallPtrSet BBExecutable; // The BBs that are executable. DenseMap ValueState; // The state each value is in. @@ -205,16 +206,17 @@ class SCCPSolver : public InstVisitor { typedef std::pair Edge; DenseSet KnownFeasibleEdges; public: - SCCPSolver(const TargetData *td, const TargetLibraryInfo *tli) - : TD(td), TLI(tli) {} + SCCPSolver(const DataLayout &DL, const TargetLibraryInfo *tli) + : DL(DL), 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. /// /// This returns true if the block was not considered live before. bool MarkBlockExecutable(BasicBlock *BB) { - if (!BBExecutable.insert(BB)) return false; - DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n"); + if (!BBExecutable.insert(BB).second) + return false; + DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n'); BBWorkList.push_back(BB); // Add the block to the work list! return true; } @@ -271,13 +273,6 @@ 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() { @@ -409,8 +404,8 @@ private: if (Constant *C = dyn_cast(V)) { Constant *Elt = C->getAggregateElement(i); - - if (Elt == 0) + + if (!Elt) LV.markOverdefined(); // Unknown sort of constant. else if (isa(Elt)) ; // Undef values remain undefined. @@ -434,7 +429,7 @@ private: // feasible that wasn't before. Revisit the PHI nodes in the block // because they have potentially new operands. DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() - << " -> " << Dest->getName() << "\n"); + << " -> " << Dest->getName() << '\n'); PHINode *PN; for (BasicBlock::iterator I = Dest->begin(); @@ -446,7 +441,7 @@ private: // getFeasibleSuccessors - Return a vector of booleans to indicate which // successors are reachable from a given terminator instruction. // - void getFeasibleSuccessors(TerminatorInst &TI, SmallVector &Succs); + void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl &Succs); // isEdgeFeasible - Return true if the control flow edge from the 'From' basic // block to the 'To' basic block is currently feasible. @@ -498,17 +493,18 @@ private: } 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 visitAtomicCmpXchgInst(AtomicCmpXchgInst &I) { + markAnythingOverdefined(&I); + } void visitAtomicRMWInst (AtomicRMWInst &I) { markOverdefined(&I); } void visitAllocaInst (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. - dbgs() << "SCCP: Don't know how to handle: " << I; + dbgs() << "SCCP: Don't know how to handle: " << I << '\n'; markAnythingOverdefined(&I); // Just in case } }; @@ -520,7 +516,7 @@ private: // successors are reachable from a given terminator instruction. // void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, - SmallVector &Succs) { + SmallVectorImpl &Succs) { Succs.resize(TI.getNumSuccessors()); if (BranchInst *BI = dyn_cast(&TI)) { if (BI->isUnconditional()) { @@ -530,7 +526,7 @@ void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, LatticeVal BCValue = getValueState(BI->getCondition()); ConstantInt *CI = BCValue.getConstantInt(); - if (CI == 0) { + if (!CI) { // Overdefined condition variables, and branches on unfoldable constant // conditions, mean the branch could go either way. if (!BCValue.isUndefined()) @@ -557,7 +553,7 @@ void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, LatticeVal SCValue = getValueState(SI->getCondition()); ConstantInt *CI = SCValue.getConstantInt(); - if (CI == 0) { // Overdefined or undefined condition? + if (!CI) { // Overdefined or undefined condition? // All destinations are executable! if (!SCValue.isUndefined()) Succs.assign(TI.getNumSuccessors(), true); @@ -602,7 +598,7 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { // Overdefined condition variables mean the branch could go either way, // undef conditions mean that neither edge is feasible yet. ConstantInt *CI = BCValue.getConstantInt(); - if (CI == 0) + if (!CI) return !BCValue.isUndefined(); // Constant condition variables mean the branch can only go a single way. @@ -620,7 +616,7 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { LatticeVal SCValue = getValueState(SI->getCondition()); ConstantInt *CI = SCValue.getConstantInt(); - if (CI == 0) + if (!CI) return !SCValue.isUndefined(); return SI->findCaseValue(CI).getCaseSuccessor() == To; @@ -634,7 +630,7 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { #ifndef NDEBUG dbgs() << "Unknown terminator instruction: " << *TI << '\n'; #endif - llvm_unreachable(0); + llvm_unreachable(nullptr); } // visit Implementations - Something changed in this instruction, either an @@ -675,7 +671,7 @@ void SCCPSolver::visitPHINode(PHINode &PN) { // constant. If they are constant and don't agree, the PHI is overdefined. // If there are no executable operands, the PHI remains undefined. // - Constant *OperandVal = 0; + Constant *OperandVal = nullptr; for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { LatticeVal IV = getValueState(PN.getIncomingValue(i)); if (IV.isUndefined()) continue; // Doesn't influence PHI node. @@ -686,7 +682,7 @@ void SCCPSolver::visitPHINode(PHINode &PN) { if (IV.isOverdefined()) // PHI node becomes overdefined! return markOverdefined(&PN); - if (OperandVal == 0) { // Grab the first value. + if (!OperandVal) { // Grab the first value. OperandVal = IV.getConstant(); continue; } @@ -710,9 +706,6 @@ void SCCPSolver::visitPHINode(PHINode &PN) { markConstant(&PN, OperandVal); // Acquire operand value } - - - void SCCPSolver::visitReturnInst(ReturnInst &I) { if (I.getNumOperands() == 0) return; // ret void @@ -785,7 +778,7 @@ void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) { StructType *STy = dyn_cast(IVI.getType()); - if (STy == 0) + if (!STy) return markOverdefined(&IVI); // If this has more than one index, we can't handle it, drive all results to @@ -873,7 +866,7 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { // If this is an AND or OR with 0 or -1, it doesn't matter that the other // operand is overdefined. if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Or) { - LatticeVal *NonOverdefVal = 0; + LatticeVal *NonOverdefVal = nullptr; if (!V1State.isOverdefined()) NonOverdefVal = &V1State; else if (!V2State.isOverdefined()) @@ -1018,8 +1011,9 @@ void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { } Constant *Ptr = Operands[0]; - ArrayRef Indices(Operands.begin() + 1, Operands.end()); - markConstant(&I, ConstantExpr::getGetElementPtr(Ptr, Indices)); + auto Indices = makeArrayRef(Operands.begin() + 1, Operands.end()); + markConstant(&I, ConstantExpr::getGetElementPtr(I.getSourceElementType(), Ptr, + Indices)); } void SCCPSolver::visitStoreInst(StoreInst &SI) { @@ -1077,7 +1071,7 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { } // Transform load from a constant into a constant if possible. - if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, TD)) + if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, DL)) return markConstant(IV, &I, C); // Otherwise we cannot say for certain what value this load will produce. @@ -1092,7 +1086,7 @@ void SCCPSolver::visitCallSite(CallSite CS) { // 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->isDeclaration()) { + if (!F || F->isDeclaration()) { CallOverdefined: // Void return and not tracking callee, just bail. if (I->getType()->isVoidTy()) return; @@ -1115,6 +1109,9 @@ CallOverdefined: Operands.push_back(State.getConstant()); } + if (getValueState(I).isOverdefined()) + return; + // If we can constant fold this, mark the result of the call as a // constant. if (Constant *C = ConstantFoldCall(F, Operands, TLI)) @@ -1185,16 +1182,15 @@ void SCCPSolver::Solve() { DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n'); // "I" got into the work list because it either made the transition from - // bottom to constant + // bottom to constant, or to overdefined. // // Anything on this worklist that is overdefined need not be visited // since all of its users will have already been marked as overdefined // Update all of the users of this instruction's value. // - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); - UI != E; ++UI) - if (Instruction *I = dyn_cast(*UI)) - OperandChangedState(I); + for (User *U : I->users()) + if (Instruction *UI = dyn_cast(U)) + OperandChangedState(UI); } // Process the instruction work list. @@ -1211,10 +1207,9 @@ void SCCPSolver::Solve() { // Update all of the users of this instruction's value. // 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)) - OperandChangedState(I); + for (User *U : I->users()) + if (Instruction *UI = dyn_cast(U)) + OperandChangedState(UI); } // Process the basic block work list. @@ -1509,8 +1504,8 @@ namespace { /// Sparse Conditional Constant Propagator. /// struct SCCP : public FunctionPass { - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); } static char ID; // Pass identification, replacement for typeid SCCP() : FunctionPass(ID) { @@ -1520,7 +1515,7 @@ namespace { // runOnFunction - Run the Sparse Conditional Constant Propagation // algorithm, and return true if the function was modified. // - bool runOnFunction(Function &F); + bool runOnFunction(Function &F) override; }; } // end anonymous namespace @@ -1563,10 +1558,14 @@ static void DeleteInstructionInBlock(BasicBlock *BB) { // and return true if the function was modified. // bool SCCP::runOnFunction(Function &F) { + if (skipOptnoneFunction(F)) + return false; + DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n"); - const TargetData *TD = getAnalysisIfAvailable(); - const TargetLibraryInfo *TLI = &getAnalysis(); - SCCPSolver Solver(TD, TLI); + const DataLayout &DL = F.getParent()->getDataLayout(); + const TargetLibraryInfo *TLI = + &getAnalysis().getTLI(); + SCCPSolver Solver(DL, TLI); // Mark the first block of the function as being executable. Solver.MarkBlockExecutable(F.begin()); @@ -1614,7 +1613,7 @@ bool SCCP::runOnFunction(Function &F) { Constant *Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(Inst->getType()); - DEBUG(dbgs() << " Constant: " << *Const << " = " << *Inst); + DEBUG(dbgs() << " Constant: " << *Const << " = " << *Inst << '\n'); // Replaces all of the uses of a variable with uses of the constant. Inst->replaceAllUsesWith(Const); @@ -1638,14 +1637,14 @@ namespace { /// Constant Propagation. /// struct IPSCCP : public ModulePass { - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); } static char ID; IPSCCP() : ModulePass(ID) { initializeIPSCCPPass(*PassRegistry::getPassRegistry()); } - bool runOnModule(Module &M); + bool runOnModule(Module &M) override; }; } // end anonymous namespace @@ -1653,7 +1652,7 @@ char IPSCCP::ID = 0; INITIALIZE_PASS_BEGIN(IPSCCP, "ipsccp", "Interprocedural Sparse Conditional Constant Propagation", false, false) -INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_END(IPSCCP, "ipsccp", "Interprocedural Sparse Conditional Constant Propagation", false, false) @@ -1668,21 +1667,20 @@ static bool AddressIsTaken(const GlobalValue *GV) { // Delete any dead constantexpr klingons. GV->removeDeadConstantUsers(); - 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)) { + for (const Use &U : GV->uses()) { + const User *UR = U.getUser(); + if (const StoreInst *SI = dyn_cast(UR)) { if (SI->getOperand(0) == GV || SI->isVolatile()) return true; // Storing addr of GV. - } else if (isa(U) || isa(U)) { + } else if (isa(UR) || isa(UR)) { // Make sure we are calling the function, not passing the address. - ImmutableCallSite CS(cast(U)); - if (!CS.isCallee(UI)) + ImmutableCallSite CS(cast(UR)); + if (!CS.isCallee(&U)) return true; - } else if (const LoadInst *LI = dyn_cast(U)) { + } else if (const LoadInst *LI = dyn_cast(UR)) { if (LI->isVolatile()) return true; - } else if (isa(U)) { + } else if (isa(UR)) { // blockaddress doesn't take the address of the function, it takes addr // of label. } else { @@ -1693,9 +1691,10 @@ static bool AddressIsTaken(const GlobalValue *GV) { } bool IPSCCP::runOnModule(Module &M) { - const TargetData *TD = getAnalysisIfAvailable(); - const TargetLibraryInfo *TLI = &getAnalysis(); - SCCPSolver Solver(TD, TLI); + const DataLayout &DL = M.getDataLayout(); + const TargetLibraryInfo *TLI = + &getAnalysis().getTLI(); + SCCPSolver Solver(DL, TLI); // AddressTakenFunctions - This set keeps track of the address-taken functions // that are in the input. As IPSCCP runs through and simplifies code, @@ -1822,7 +1821,7 @@ bool IPSCCP::runOnModule(Module &M) { Constant *Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(Inst->getType()); - DEBUG(dbgs() << " Constant: " << *Const << " = " << *Inst); + DEBUG(dbgs() << " Constant: " << *Const << " = " << *Inst << '\n'); // Replaces all of the uses of a variable with uses of the // constant. @@ -1844,8 +1843,9 @@ 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]; - for (Value::use_iterator UI = DeadBB->use_begin(), UE = DeadBB->use_end(); - UI != UE; ) { + for (Value::user_iterator UI = DeadBB->user_begin(), + UE = DeadBB->user_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); @@ -1925,8 +1925,8 @@ bool IPSCCP::runOnModule(Module &M) { ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType())); } - // If we inferred constant or undef values for globals variables, we can delete - // the global and any stores that remain to it. + // 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(), E = TG.end(); I != E; ++I) { @@ -1935,7 +1935,7 @@ bool IPSCCP::runOnModule(Module &M) { "Overdefined values should have been taken out of the map!"); DEBUG(dbgs() << "Found that GV '" << GV->getName() << "' is constant!\n"); while (!GV->use_empty()) { - StoreInst *SI = cast(GV->use_back()); + StoreInst *SI = cast(GV->user_back()); SI->eraseFromParent(); } M.getGlobalList().erase(GV);