diff --git a/llvm/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h --- a/llvm/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -166,6 +166,7 @@ void initializeForwardControlFlowIntegrityPass(PassRegistry&); void initializeFuncletLayoutPass(PassRegistry&); void initializeFunctionImportLegacyPassPass(PassRegistry&); +void initializeFunctionSpecializationPass(PassRegistry &); void initializeGCMachineCodeAnalysisPass(PassRegistry&); void initializeGCModuleInfoPass(PassRegistry&); void initializeGCOVProfilerLegacyPassPass(PassRegistry&); diff --git a/llvm/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h --- a/llvm/include/llvm/LinkAllPasses.h +++ b/include/llvm/LinkAllPasses.h @@ -230,6 +230,7 @@ (void) llvm::createInjectTLIMappingsLegacyPass(); (void) llvm::createUnifyLoopExitsPass(); (void) llvm::createFixIrreduciblePass(); + (void)llvm::createFunctionSpecializationPass(); (void)new llvm::IntervalPartition(); (void)new llvm::ScalarEvolutionWrapperPass(); diff --git a/llvm/include/llvm/Transforms/IPO.h b/include/llvm/Transforms/IPO.h --- a/llvm/include/llvm/Transforms/IPO.h +++ b/include/llvm/Transforms/IPO.h @@ -169,6 +169,11 @@ /// ModulePass *createIPSCCPPass(); +//===----------------------------------------------------------------------===// +/// createFunctionSpecializationPass - This pass propagates constants from call +/// sites to the specialized version of the callee function. +ModulePass *createFunctionSpecializationPass(); + //===----------------------------------------------------------------------===// // /// createLoopExtractorPass - This pass extracts all natural loops from the diff --git a/llvm/include/llvm/Transforms/Scalar/SCCP.h b/include/llvm/Transforms/Scalar/SCCP.h --- a/llvm/include/llvm/Transforms/Scalar/SCCP.h +++ b/include/llvm/Transforms/Scalar/SCCP.h @@ -20,15 +20,386 @@ #ifndef LLVM_TRANSFORMS_SCALAR_SCCP_H #define LLVM_TRANSFORMS_SCALAR_SCCP_H +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/DomTreeUpdater.h" #include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/Analysis/ValueLattice.h" +#include "llvm/Analysis/ValueLatticeUtils.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Function.h" +#include "llvm/IR/InstVisitor.h" #include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" #include "llvm/Transforms/Utils/PredicateInfo.h" namespace llvm { +/// Helper struct for bundling up the analysis results per function for IPSCCP. +struct AnalysisResultsForFn { + std::unique_ptr PredInfo; + DominatorTree *DT; + PostDominatorTree *PDT; +}; + +//===----------------------------------------------------------------------===// +// +/// SCCPSolver - This class is a general purpose solver for Sparse Conditional +/// Constant Propagation. +/// +class SCCPSolver : public InstVisitor { + const DataLayout &DL; + std::function GetTLI; + 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, ValueLatticeElement> 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 + /// overdefined, it's entry is simply removed from this map. + DenseMap TrackedGlobals; + + /// 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. + MapVector TrackedRetVals; + + /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions + /// that return multiple values. + MapVector, ValueLatticeElement> + TrackedMultipleRetVals; + + /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is + /// represented here for efficient lookup. + SmallPtrSet MRVFunctionsTracked; + + /// MustTailFunctions - Each function here is a callee of non-removable + /// musttail call site. + SmallPtrSet MustTailCallees; + + /// TrackingIncomingArguments - This is the set of functions for whose + /// arguments we make optimistic assumptions about and try to prove as + /// constants. + SmallPtrSet TrackingIncomingArguments; + + /// The reason for two worklists is that overdefined is the lowest state + /// on the lattice, and moving things to overdefined as fast as possible + /// makes SCCP converge much faster. + /// + /// By having a separate worklist, we accomplish this because everything + /// possibly overdefined will become overdefined at the soonest possible + /// point. + SmallVector OverdefinedInstWorkList; + SmallVector InstWorkList; + + // The BasicBlock work list + SmallVector BBWorkList; + + /// KnownFeasibleEdges - Entries in this set are edges which have already had + /// PHI nodes retriggered. + using Edge = std::pair; + DenseSet KnownFeasibleEdges; + + DenseMap AnalysisResults; + DenseMap> AdditionalUsers; + + LLVMContext &Ctx; + +public: + void addAnalysis(Function &F, AnalysisResultsForFn A); + + const PredicateBase *getPredicateInfoFor(Instruction *I); + + DomTreeUpdater getDTU(Function &F); + + SCCPSolver(const DataLayout &DL, + std::function GetTLI, + LLVMContext &Ctx); + + /// 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); + + /// Mark all of the blocks in function \p F non-executable. Clients can used + /// this method to erase a function from the module (e.g., if it has been + /// completely specialized and is no longer needed). + void markFunctionUnreachable(Function *F) { + for (auto &BB : *F) + BBExecutable.erase(&BB); + } + + /// TrackValueOfGlobalVariable - Clients can use this method to + /// inform the SCCPSolver that it should track loads and stores to the + /// specified global variable if it can. This is only legal to call if + /// performing Interprocedural SCCP. + void TrackValueOfGlobalVariable(GlobalVariable *GV); + + /// AddTrackedFunction - If the SCCP solver is supposed to track calls into + /// and out of the specified function (which cannot have its address taken), + /// this method must be called. + void AddTrackedFunction(Function *F); + + /// AddMustTailCallee - If the SCCP solver finds that this function is called + /// from non-removable musttail call site. + void AddMustTailCallee(Function *F) { MustTailCallees.insert(F); } + + /// Returns true if the given function is called from non-removable musttail + /// call site. + bool isMustTailCallee(Function *F) { return MustTailCallees.count(F); } + + void AddArgumentTrackedFunction(Function *F) { + TrackingIncomingArguments.insert(F); + } + + /// Returns true if the given function is in the solver's set of + /// argument-tracked functions. + bool isArgumentTrackedFunction(Function *F) { + return TrackingIncomingArguments.count(F); + } + + /// Return a reference to the set of argument tracked functions. + SmallPtrSetImpl &getArgumentTrackedFunctions() { + return TrackingIncomingArguments; + } + + /// Mark argument \p A constant with value \p C in a new function + /// specialization. The argument's parent function is a specialization of the + /// original function \p F. All other arguments of the specialization inherit + /// the lattice state of their corresponding values in the original function. + void markArgInFuncSpecialization(Function *F, Argument *A, Constant *C) { + assert(F->arg_size() == A->getParent()->arg_size() && + "Functions should have the same number of arguments"); + + // Mark the argument constant in the new function. + markConstant(A, C); + + // For the remaining arguments in the new function, copy the lattice state + // over from the old function. + for (auto I = F->arg_begin(), J = A->getParent()->arg_begin(), + E = F->arg_end(); + I != E; ++I, ++J) + if (J != A && ValueState.count(I)) { + ValueState[J] = ValueState[I]; + pushToWorkList(ValueState[J], J); + } + } + + /// Solve - Solve for constants and executable blocks. + void Solve(); + + /// ResolvedUndefsIn - While solving the dataflow for a function, we assume + /// that branches on undef values cannot reach any of their successors. + /// However, this is not a safe assumption. After we solve dataflow, this + /// method should be use to handle this. If this returns true, the solver + /// should be rerun. + bool ResolvedUndefsIn(Function &F); + + bool isBlockExecutable(BasicBlock *BB) const { + return BBExecutable.count(BB); + } + + // isEdgeFeasible - Return true if the control flow edge from the 'From' basic + // block to the 'To' basic block is currently feasible. + bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const; + + std::vector getStructLatticeValueFor(Value *V) const; + + void removeLatticeValueFor(Value *V) { ValueState.erase(V); } + + const ValueLatticeElement &getLatticeValueFor(Value *V) const; + + /// getTrackedRetVals - Get the inferred return value map. + const MapVector &getTrackedRetVals() { + return TrackedRetVals; + } + + /// getTrackedGlobals - Get and return the set of inferred initializers for + /// global variables. + const DenseMap &getTrackedGlobals() { + return TrackedGlobals; + } + + /// getMRVFunctionsTracked - Get the set of functions which return multiple + /// values tracked by the pass. + const SmallPtrSet getMRVFunctionsTracked() { + return MRVFunctionsTracked; + } + + /// getMustTailCallees - Get the set of functions which are called + /// from non-removable musttail call sites. + const SmallPtrSet getMustTailCallees() { + return MustTailCallees; + } + + /// markOverdefined - Mark the specified value overdefined. This + /// works with both scalars and structs. + void markOverdefined(Value *V); + + // isStructLatticeConstant - Return true if all the lattice values + // corresponding to elements of the structure are constants, + // false otherwise. + bool isStructLatticeConstant(Function *F, StructType *STy); + + /// Helper to return a Constant if \p LV is either a constant or a constant + /// range with a single element. + Constant *getConstant(const ValueLatticeElement &LV) const; + +private: + ConstantInt *getConstantInt(const ValueLatticeElement &IV) const { + return dyn_cast_or_null(getConstant(IV)); + } + + // pushToWorkList - Helper for markConstant/markOverdefined + void pushToWorkList(ValueLatticeElement &IV, Value *V) { + if (IV.isOverdefined()) + return OverdefinedInstWorkList.push_back(V); + InstWorkList.push_back(V); + } + + // Helper to push \p V to the worklist, after updating it to \p IV. Also + // prints a debug message with the updated value. + void pushToWorkListMsg(ValueLatticeElement &IV, Value *V); + + // markConstant - Make a value be marked as "constant". If the value + // is not already a constant, add it to the instruction work list so that + // the users of the instruction are updated later. + bool markConstant(ValueLatticeElement &IV, Value *V, Constant *C, + bool MayIncludeUndef = false); + + bool markConstant(Value *V, Constant *C) { + assert(!V->getType()->isStructTy() && "structs should use mergeInValue"); + return markConstant(ValueState[V], V, C); + } + + // 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. + bool markOverdefined(ValueLatticeElement &IV, Value *V); + + /// Merge \p MergeWithV into \p IV and push \p V to the worklist, if \p IV + /// changes. + bool mergeInValue(ValueLatticeElement &IV, Value *V, + ValueLatticeElement MergeWithV, + ValueLatticeElement::MergeOptions Opts = { + /*MayIncludeUndef=*/false, /*CheckWiden=*/false}); + + bool mergeInValue(Value *V, ValueLatticeElement MergeWithV, + ValueLatticeElement::MergeOptions Opts = { + /*MayIncludeUndef=*/false, /*CheckWiden=*/false}); + + /// getValueState - Return the ValueLatticeElement object that corresponds to + /// the value. This function handles the case when the value hasn't been seen + /// yet by properly seeding constants etc. + ValueLatticeElement &getValueState(Value *V); + + /// getStructValueState - Return the ValueLatticeElement 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. + ValueLatticeElement &getStructValueState(Value *V, unsigned i); + + /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB + /// work list if it is not already executable. + bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest); + + // getFeasibleSuccessors - Return a vector of booleans to indicate which + // successors are reachable from a given terminator instruction. + void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl &Succs); + + // OperandChangedState - This method is invoked on all of the users of an + // instruction that was just changed state somehow. Based on this + // information, we need to update the specified user of this instruction. + void OperandChangedState(Instruction *I) { + if (BBExecutable.count(I->getParent())) // Inst is executable? + visit(*I); + } + + // Add U as additional user of V. + void addAdditionalUser(Value *V, User *U) { + auto Iter = AdditionalUsers.insert({V, {}}); + Iter.first->second.insert(U); + } + + // Mark I's users as changed, including AdditionalUsers. + void markUsersAsChanged(Value *I); + void handleCallOverdefined(CallBase &CB); + void handleCallResult(CallBase &CB); + void handleCallArguments(CallBase &CB); + +private: + friend class InstVisitor; + + // visit implementations - Something changed in this instruction. Either an + // operand made a transition, or the instruction is newly executable. Change + // the value type of I to reflect these changes if appropriate. + void visitPHINode(PHINode &I); + + // Terminators + + void visitReturnInst(ReturnInst &I); + void visitTerminator(Instruction &TI); + + void visitCastInst(CastInst &I); + void visitSelectInst(SelectInst &I); + void visitUnaryOperator(Instruction &I); + void visitBinaryOperator(Instruction &I); + void visitCmpInst(CmpInst &I); + void visitExtractValueInst(ExtractValueInst &EVI); + void visitInsertValueInst(InsertValueInst &IVI); + + void visitCatchSwitchInst(CatchSwitchInst &CPI) { + markOverdefined(&CPI); + visitTerminator(CPI); + } + + // Instructions that cannot be folded away. + + void visitStoreInst(StoreInst &I); + void visitLoadInst(LoadInst &I); + void visitGetElementPtrInst(GetElementPtrInst &I); + + void visitCallInst(CallInst &I) { visitCallBase(I); } + + void visitInvokeInst(InvokeInst &II) { + visitCallBase(II); + visitTerminator(II); + } + + void visitCallBrInst(CallBrInst &CBI) { + visitCallBase(CBI); + visitTerminator(CBI); + } + + void visitCallBase(CallBase &CB); + void visitResumeInst(ResumeInst &I) { /*returns void*/ + } + void visitUnreachableInst(UnreachableInst &I) { /*returns void*/ + } + void visitFenceInst(FenceInst &I) { /*returns void*/ + } + + void visitInstruction(Instruction &I); +}; + +bool tryToReplaceWithConstant(llvm::SCCPSolver &Solver, Value *V); +bool simplifyInstsInBlock(SCCPSolver &Solver, BasicBlock &BB, + SmallPtrSetImpl &InsertedValues, + Statistic &InstRemovedStat, + Statistic &InstReplacedStat); class PostDominatorTree; @@ -38,12 +409,6 @@ PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; -/// Helper struct for bundling up the analysis results per function for IPSCCP. -struct AnalysisResultsForFn { - std::unique_ptr PredInfo; - DominatorTree *DT; - PostDominatorTree *PDT; -}; bool runIPSCCP(Module &M, const DataLayout &DL, std::function GetTLI, diff --git a/llvm/lib/Transforms/IPO/CMakeLists.txt b/lib/Transforms/IPO/CMakeLists.txt --- a/llvm/lib/Transforms/IPO/CMakeLists.txt +++ b/lib/Transforms/IPO/CMakeLists.txt @@ -15,6 +15,7 @@ ForceFunctionAttrs.cpp FunctionAttrs.cpp FunctionImport.cpp + FunctionSpecialization.cpp GlobalDCE.cpp GlobalOpt.cpp GlobalSplit.cpp diff --git a/lib/Transforms/IPO/FunctionSpecialization.cpp b/lib/Transforms/IPO/FunctionSpecialization.cpp new file mode 100644 --- /dev/null +++ b/lib/Transforms/IPO/FunctionSpecialization.cpp @@ -0,0 +1,632 @@ +//===- FunctionSpecialization.cpp - Specialize Functions using SCCP ------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Propagate Constant arguments by specializing the Functions. +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/BlockFrequencyInfo.h" +#include "llvm/Analysis/CodeMetrics.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/ProfileSummaryInfo.h" +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/IPO.h" +#include "llvm/Transforms/Scalar/SCCP.h" +#include "llvm/Transforms/Utils/Cloning.h" +#include "llvm/Transforms/Utils/SizeOpts.h" +#include + +using namespace llvm; + +#define DEBUG_TYPE "function-specialize" + +STATISTIC(NumFuncSpecialized, "Number of Functions Specialized"); +STATISTIC(NumInstRemoved, "Number of instructions removed"); +STATISTIC(NumInstReplaced, + "Number of instructions replaced with (simpler) instruction"); + +namespace { + +/// FunctionSpecializer is responsible for specializing functions based on the +/// values of their incoming arguments. +/// +/// After an initial IPSCCP data-flow is solved, we may find that a formal +/// argument of a function can take on a particular constant value in some +/// calling contexts, but not all. If this is the case, we can create a new +/// version of the function in which the argument is replaced by the constant +/// value and recompute the data-flow. This allows constant propagation across +/// function boundaries when an argument can take on more than one value. +/// +/// Specialization is controlled by a goal-oriented heuristic that seeks to +/// predict if replacing an argument with a constant value would result in any +/// significant optimization opportunities. The heuristic is currently limited +/// to revealing inlining opportunities via indirect call promotion. Inline +/// cost is used to weigh the expected benefit of specialization against the +/// cost of doing so. +class FunctionSpecializer { + + /// The IPSCCP Solver. + SCCPSolver &Solver; + + /// Analyses used to help determine if a function should be specialized. + std::function GetAC; + std::function GetTTI; + std::function GetTLI; + + /// Maps to save specialization costs and bonuses so we don't recompute them + /// unnecessarily. + DenseMap SpecializationCosts; + DenseMap, unsigned> SpecializationBonuses; + + /// A mapping from specialized functions to their corresponding functions + /// from the original module. + DenseMap OriginalFunctions; + + // Holds the newly created functions. We maintain a separate list of these + // functions to avoid iterator invalidation. + SmallVector Specializations; + +public: + FunctionSpecializer(SCCPSolver &Solver, + std::function GetAC, + std::function GetTTI, + std::function GetTLI) + : Solver(Solver), GetAC(GetAC), GetTTI(GetTTI), GetTLI(GetTLI) {} + + SmallVectorImpl &getSpecializations() { return Specializations; } + + /// Attempt to specialize functions in the module to enable constant + /// propagation across function boundaries. + /// + /// \returns true if at least one function is specialized. + bool specializeFunctions() { + + // Clear the previously specialized function list. + Specializations.clear(); + + // Attempt to specialize the argument-tracked functions. + bool Changed = false; + for (auto *F : Solver.getArgumentTrackedFunctions()) { + // If the function is not in the OriginalFunctions map, initialize it + // with an identity relationship. + if (!OriginalFunctions.count(F)) + OriginalFunctions[F] = F; + + Changed |= specializeFunction(F, Specializations); + } + + for (auto *F : Specializations) { + // Initialize the state of the newly created functions, marking them + // argument-tracked and executable. + if (F->hasExactDefinition() && !F->hasFnAttribute(Attribute::Naked)) + Solver.AddTrackedFunction(F); + Solver.AddArgumentTrackedFunction(F); + Solver.MarkBlockExecutable(&F->front()); + + // Replace the function arguments for the specialized functions. + for (Argument &Arg : F->args()) { + if (!Arg.use_empty() && tryToReplaceWithConstant(Solver, &Arg)) { + LLVM_DEBUG(dbgs() + << "\nFunctionSpecialize: Replaced constant argument"); + } + } + } + return Changed; + } + +private: + /// Clone the function \p F and remove the ssa_copy intrinsics added by + /// the SCCPSolver in the cloned version. + Function *cloneCandidateFunction(Function *F) { + ValueToValueMapTy EmptyMap; + Function *Clone = CloneFunction(F, EmptyMap); + // The ssa_copy intrinsics are added to the original function by + // the SCCP utility. Remove them for the cloned version. + // TODO: Move to SCCP.cpp + for (BasicBlock &BB : *Clone) { + for (auto BI = BB.begin(), E = BB.end(); BI != E;) { + auto *Inst = &*BI++; + if (auto *II = dyn_cast(Inst)) { + if (II->getIntrinsicID() == Intrinsic::ssa_copy) { + Value *Op = II->getOperand(0); + Inst->replaceAllUsesWith(Op); + Inst->eraseFromParent(); + } + } + } + } + return Clone; + } + + /// Attempt to specialize function \p F. + /// + /// This function decides whether to specialize function \p F based on the + /// known constant values its arguments can take on. Specialization is + /// performed on the first interesting argument. Specializations based on + /// additional arguments will be evaluated on following iterations of the + /// main IPSCCP solve loop. + /// + /// \returns true if the function is specialized. + bool specializeFunction(Function *F, + SmallVectorImpl &Specializations) { + + // If we're optimizing the function for size, we shouldn't specialize it. + if (F->hasOptSize() || + llvm::shouldOptimizeForSize(F, nullptr, nullptr, PGSOQueryType::IRPass)) + return false; + + // Exit if the function is not executable. There's no point in specializing + // a dead function. + if (!Solver.isBlockExecutable(&F->getEntryBlock())) + return false; + + // Determine if we should specialize the function based on the values the + // argument can take on. If specialization is not profitable, we continue + // on to the next argument. + for (Argument &A : F->args()) { + + // True if this will be a partial specialization. We will need to keep + // the original function around in addition to the added specializations. + bool IsPartial = true; + + // Determine if this argument is interesting. If we know the argument can + // take on any constant values, they are collected in Constants. If the + // argument can only ever equal a constant value in Constants, the + // function will be completely specialized, and the IsPartial flag will + // be set to false by isArgumentInteresting (that function only adds + // values to the Constants list that are deemed profitable). + SmallVector Constants; + if (!isArgumentInteresting(&A, Constants, IsPartial)) + continue; + + assert(!Constants.empty() && "No constants on which to specialize"); + LLVM_DEBUG(dbgs() << "Specializing function " << F->getName() << " on " + << A << ": (" << *Constants[0]; + for (unsigned I = 1; I < Constants.size(); ++I) dbgs() + << ", " << *Constants[I]; + dbgs() << ")\n"); + + // Create a version of the function in which the argument is marked + // constant with the given value. + for (auto *C : Constants) { + + // Clone the function. We leave the ValueToValueMap empty to allow + // IPSCCP to propagate the constant arguments. + Function *Clone = cloneCandidateFunction(F); + Argument *ClonedArg = Clone->arg_begin() + A.getArgNo(); + + // Rewrite calls to the function so that they call the clone instead. + rewriteCallSites(F, Clone, *ClonedArg, C); + + // Initialize the lattice state of the arguments of the function clone, + // marking the argument on which we specialized the function constant + // with the given value. + Solver.markArgInFuncSpecialization(F, ClonedArg, C); + + // Mark all the specialized functions + Specializations.push_back(Clone); + NumFuncSpecialized++; + + // Set the parent function of the clone. + OriginalFunctions[Clone] = OriginalFunctions[F]; + } + + // If the function has been completely specialized, the original function + // is no longer needed. Mark it unreachable. + if (!IsPartial) + Solver.markFunctionUnreachable(F); + + return true; + } + + return false; + } + + /// Compute the cost of specializing function \p F. + unsigned getSpecializationCost(Function *F) { + // TODO: Yet to implement + return 1; + } + + /// Compute a bonus for replacing argument \p A with constant \p C. + unsigned getSpecializationBonus(Argument *A, Constant *C) { + // TODO: Yet to implement + return 2; + } + + /// Determine if we should specialize a function based on the incoming values + /// of the given argument. + /// + /// This function implements the goal-directed heuristic. It determines if + /// specializing the function based on the incoming values of argument \p A + /// would result in any significant optimization opportunities. If + /// optimization opportunities exist, the constant values of \p A on which to + /// specialize the function are collected in \p Constants. If the values in + /// \p Constants represent the complete set of values that \p A can take on, + /// the function will be completely specialized, and the \p IsPartial flag is + /// set to false. + /// + /// \returns true if the function should be specialized on the given + /// argument. + bool isArgumentInteresting(Argument *A, + SmallVectorImpl &Constants, + bool &IsPartial) { + Function *F = A->getParent(); + + // For now, don't attempt to specialize functions based on the values of + // struct types. + if (A->getType()->isStructTy()) + return false; + + // If the argument isn't overdefined, there's nothing to do. It should + // already be constant. + if (!Solver.getLatticeValueFor(A).isOverdefined()) + return false; + + // Collect the constant values that the argument can take on. If the + // argument can't take on any constant values, we aren't going to + // specialize the function. While it's possible to specialize the function + // based on non-constant arguments, there's likely not much benefit to + // constant propagation in doing so. + SmallPtrSet PossibleConstants; + bool AllConstant = getPossibleConstants(A, PossibleConstants); + if (PossibleConstants.empty()) + return false; + + // Determine if it would be profitable to create a specialization of the + // function where the argument takes on the given constant value. If so, + // add the constant to Constants. + for (auto *C : PossibleConstants) { + if (getSpecializationBonus(A, C) > getSpecializationCost(F)) + Constants.push_back(C); + } + + // None of the constant values the argument can take on were deemed good + // candidates on which to specialize the function. + if (Constants.empty()) + return false; + + // This will be a partial specialization if some of the constants were + // rejected due to their profitability. + IsPartial = !AllConstant || PossibleConstants.size() != Constants.size(); + + return true; + } + + /// Collect in \p Constants all the constant values that argument \p A can + /// take on. + /// + /// \returns true if all of the values the argument can take on are constant + /// (e.g., the argument's parent function cannot be called with an + /// overdefined value). + bool getPossibleConstants(Argument *A, + SmallPtrSetImpl &Constants) { + Function *F = A->getParent(); + bool AllConstant = true; + + // Iterate over all the call sites of the argument's parent function. + for (User *U : F->users()) { + if (!isa(U) && !isa(U)) + continue; + auto &CS = *cast(U); + + // If the parent of the call site will never be executed, we don't need + // to worry about the passed value. + if (!Solver.isBlockExecutable(CS.getParent())) + continue; + + // Get the lattice value for the value the call site passes to the + // argument. If this value is not constant, move on to the next call + // site. Additionally, set the AllConstant flag to false. + if (CS.getArgOperand(A->getArgNo()) != A && + !Solver.getLatticeValueFor(CS.getArgOperand(A->getArgNo())) + .isConstant()) { + AllConstant = false; + continue; + } + + // Add the constant to the set. + if (auto *C = dyn_cast(CS.getArgOperand(A->getArgNo()))) + Constants.insert(C); + } + + // If the argument can only take on constant values, AllConstant will be + // true. + return AllConstant; + } + + /// Rewrite calls to function \p F to call function \p Clone instead. + /// + /// This function modifies calls to function \p F whose argument at index \p + /// ArgNo is equal to constant \p C. The calls are rewritten to call function + /// \p Clone instead. + void rewriteCallSites(Function *F, Function *Clone, Argument &Arg, + Constant *C) { + unsigned ArgNo = Arg.getArgNo(); + SmallVector CallSitesToRewrite; + for (auto *U : F->users()) { + if (!isa(U) && !isa(U)) + continue; + auto &CS = *cast(U); + if (!CS.getCalledFunction() || CS.getCalledFunction() != F) + continue; + CallSitesToRewrite.push_back(&CS); + } + for (auto *CS : CallSitesToRewrite) { + + if ((CS->getFunction() == Clone && CS->getArgOperand(ArgNo) == &Arg) || + CS->getArgOperand(ArgNo) == C) { + CS->setCalledFunction(Clone); + } + } + } +}; + +/// Function to clean up the left over intrinsics from SCCP util. +// TODO: Move to SCCP.cpp +static void cleanup(Module &M) { + for (Function &F : M) { + for (BasicBlock &BB : F) { + for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) { + Instruction *Inst = &*BI++; + if (auto *II = dyn_cast(Inst)) { + if (II->getIntrinsicID() == Intrinsic::ssa_copy) { + Value *Op = II->getOperand(0); + Inst->replaceAllUsesWith(Op); + Inst->eraseFromParent(); + } + } + } + } + } +} + +/// This function, +/// 1. Returns \p Val if it is constant +/// 2. Checks if \p Val is AllocaInst and returns single constant value stored +/// to it. +static Constant *getConstantValue(CallInst *Call, Value *Val, + SCCPSolver &Solver) { + if (!Val) + return nullptr; + Val = Val->stripPointerCasts(); + if (auto *ConstVal = dyn_cast(Val)) { + return ConstVal; + } + auto *Alloca = dyn_cast(Val); + if (!Alloca) + return nullptr; + + if (!Alloca->getAllocatedType()->isIntegerTy()) { + return nullptr; + } + + // Check if alloca is promotable.. + // NOTE: isAllocaPromotable() would fail because of usage in the call. + Value *StoreValue = nullptr; + for (auto *User : Alloca->users()) { + if (User == Call) + continue; + if (auto *Bitcast = dyn_cast(User)) { + if (Bitcast->hasOneUse() && *Bitcast->user_begin() == Call) + continue; + return nullptr; + } + + if (auto *Store = dyn_cast(User)) { + // This is a duplicate store, bail out. + if (StoreValue || Store->isVolatile()) { + return nullptr; + } + StoreValue = Store->getValueOperand(); + continue; + } + // Return null, if there is any other unknown usage. + return nullptr; + } + + return dyn_cast_or_null(StoreValue); +} + +// This function does the following tansformation: +// Before: +// define internal void @someFunc(i32* arg1) { +// %temp = alloca i32, align 4 +// store i32 2 i32* %temp, align 4 +// call void @otherFunc(i32* nonnull %temp) +// ret void +// } +// +// define internal void @otherFunc(i32* nocapture readonly %arg) +// +// +// After: +// @funciton.specialize.arg = internal constant i32 ; Global constant +// define internal void @someFunc(i32* arg1) { +// call void @otherFunc(i32* nonnull @funciton.specialize.arg) +// ret void +// } +// +// define internal void @otherFunc(i32* nocapture readonly %arg) +// FIXME: Is there a better way to do this transformation? +static void tryToReplaceConstantArgOperand(Module &M, SCCPSolver &Solver) { + + // Iterate over the argument tracked functions see if there + // are any new constant values for the call instruction via + // stack variables. + for (auto *F : Solver.getArgumentTrackedFunctions()) { + // TODO: Generalize for any read only arguments. + if (F->arg_size() != 1 || !(*F->arg_begin()).onlyReadsMemory()) { + continue; + } + + for (auto *User : F->users()) { + auto *Call = dyn_cast(User); + if (!Call) + break; + auto *ArgOperand = Call->getArgOperand(0); + auto *ConstVal = getConstantValue(Call, ArgOperand, Solver); + if (!ConstVal) + return; + + auto *GV = new GlobalVariable(M, ConstVal->getType(), true, + GlobalValue::InternalLinkage, ConstVal, + "funciton.specialize.arg"); + Call->setArgOperand(0, GV); + + // Add the changed CallInst to Solver Worklist + Solver.visitCall(*Call); + } + } +} + +// TODO: Move to new pass manager +struct FunctionSpecialization : public ModulePass { + static char ID; // Pass identification, replacement for typeid + FunctionSpecialization() : ModulePass(ID) {} + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + } + + virtual bool runOnModule(Module &M) override { + if (skipModule(M)) + return false; + + const DataLayout &DL = M.getDataLayout(); + auto GetTLI = [this](Function &F) -> TargetLibraryInfo & { + return this->getAnalysis().getTLI(F); + }; + auto GetTTI = [this](Function &F) -> TargetTransformInfo & { + return this->getAnalysis().getTTI(F); + }; + auto GetAC = [this](Function &F) -> AssumptionCache & { + return this->getAnalysis().getAssumptionCache(F); + }; + + auto GetAnalysis = [this](Function &F) -> AnalysisResultsForFn { + DominatorTree &DT = + this->getAnalysis(F).getDomTree(); + return { + std::make_unique( + F, DT, + this->getAnalysis().getAssumptionCache( + F)), + nullptr, // We cannot preserve the DT or PDT with the legacy pass + nullptr}; // manager, so set them to nullptr. + }; + + SCCPSolver Solver(DL, GetTLI, M.getContext()); + FunctionSpecializer FS(Solver, GetAC, GetTTI, GetTLI); + bool Changed = false; + + // Loop over all functions, marking arguments to those with their addresses + // taken or that are external as overdefined. + for (Function &F : M) { + if (F.isDeclaration()) + continue; + + Solver.addAnalysis(F, GetAnalysis(F)); + + // Determine if we can track the function's arguments. If so, add the + // function to the solver's set of argument-tracked functions. + if (canTrackArgumentsInterprocedurally(&F)) { + Solver.AddArgumentTrackedFunction(&F); + continue; + } + + // Assume the function is called. + Solver.MarkBlockExecutable(&F.front()); + + // Assume nothing about the incoming arguments. + for (Argument &AI : F.args()) + Solver.markOverdefined(&AI); + } + + // Solve for constants. + auto RunSCCPSolver = [&](auto &WorkList) { + bool ResolvedUndefs = true; + Solver.Solve(); + while (ResolvedUndefs) { + LLVM_DEBUG(dbgs() << "FunctionSpecialize: RESOLVING UNDEFS\n"); + ResolvedUndefs = false; + for (Function *F : WorkList) { + if (Solver.ResolvedUndefsIn(*F)) + ResolvedUndefs = true; + } + if (ResolvedUndefs) + Solver.Solve(); + } + }; + + // Initially resolve the constants in all the argument tracked functions. + RunSCCPSolver(Solver.getArgumentTrackedFunctions()); + + // Iterate if there are more specializations. + while (FS.specializeFunctions()) { + Changed = true; + + // Run solver for the specialized functions only. + RunSCCPSolver(FS.getSpecializations()); + + // Simplify instructions in the specialized functions. + // TODO: Can be refactored in SCCP.cpp and use it here. + SmallPtrSet InsertedValues; + for (auto *F : FS.getSpecializations()) { + for (BasicBlock &BB : *F) { + if (!Solver.isBlockExecutable(&BB)) { + continue; + } + simplifyInstsInBlock(Solver, BB, InsertedValues, NumInstRemoved, + NumInstReplaced); + for (auto *Val : InsertedValues) + Solver.markOverdefined(Val); + } + } + + // Replace some unresolved constant arguments + tryToReplaceConstantArgOperand(M, Solver); + } + + // Clean up the IR by removing ssa_copy intrinsics. + cleanup(M); + + return Changed; + } +}; +} // namespace + +char FunctionSpecialization::ID = 0; + +INITIALIZE_PASS_BEGIN( + FunctionSpecialization, "function-specialize", + "Propagate constant arguments by specializing the function", false, false) + +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_END(FunctionSpecialization, "function-specialize", + "Propagate constant arguments by specializing the function", + false, false) + +ModulePass *llvm::createFunctionSpecializationPass() { + return new FunctionSpecialization(); +} diff --git a/llvm/lib/Transforms/IPO/IPO.cpp b/lib/Transforms/IPO/IPO.cpp --- a/llvm/lib/Transforms/IPO/IPO.cpp +++ b/lib/Transforms/IPO/IPO.cpp @@ -32,6 +32,7 @@ initializeDAEPass(Registry); initializeDAHPass(Registry); initializeForceFunctionAttrsLegacyPassPass(Registry); + initializeFunctionSpecializationPass(Registry); initializeGlobalDCELegacyPassPass(Registry); initializeGlobalOptLegacyPassPass(Registry); initializeGlobalSplitPass(Registry); diff --git a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp b/lib/Transforms/IPO/PassManagerBuilder.cpp --- a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp +++ b/lib/Transforms/IPO/PassManagerBuilder.cpp @@ -952,6 +952,9 @@ PM.add( createPGOIndirectCallPromotionLegacyPass(true, !PGOSampleUse.empty())); + // Propage constant function arguments by specializing the functions. + PM.add(createFunctionSpecializationPass()); + // Propagate constants at call sites into the functions they call. This // opens opportunities for globalopt (and inlining) by substituting function // pointers passed as arguments to direct uses of functions. diff --git a/llvm/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp --- a/llvm/lib/Transforms/Scalar/SCCP.cpp +++ b/lib/Transforms/Scalar/SCCP.cpp @@ -17,24 +17,11 @@ //===----------------------------------------------------------------------===// #include "llvm/Transforms/Scalar/SCCP.h" -#include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/MapVector.h" -#include "llvm/ADT/PointerIntPair.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/SetVector.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/ConstantFolding.h" -#include "llvm/Analysis/DomTreeUpdater.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/TargetLibraryInfo.h" -#include "llvm/Analysis/ValueLattice.h" -#include "llvm/Analysis/ValueLatticeUtils.h" -#include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" @@ -107,510 +94,239 @@ bool isOverdefined(const ValueLatticeElement &LV) { return !LV.isUnknownOrUndef() && !isConstant(LV); } +} // namespace -//===----------------------------------------------------------------------===// -// -/// SCCPSolver - This class is a general purpose solver for Sparse Conditional -/// Constant Propagation. -/// -class SCCPSolver : public InstVisitor { - const DataLayout &DL; - std::function GetTLI; - 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, ValueLatticeElement> 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 - /// overdefined, it's entry is simply removed from this map. - DenseMap TrackedGlobals; - - /// 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. - MapVector TrackedRetVals; - - /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions - /// that return multiple values. - MapVector, ValueLatticeElement> - TrackedMultipleRetVals; - - /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is - /// represented here for efficient lookup. - SmallPtrSet MRVFunctionsTracked; - - /// MustTailFunctions - Each function here is a callee of non-removable - /// musttail call site. - SmallPtrSet MustTailCallees; - - /// TrackingIncomingArguments - This is the set of functions for whose - /// arguments we make optimistic assumptions about and try to prove as - /// constants. - SmallPtrSet TrackingIncomingArguments; - - /// The reason for two worklists is that overdefined is the lowest state - /// on the lattice, and moving things to overdefined as fast as possible - /// makes SCCP converge much faster. - /// - /// By having a separate worklist, we accomplish this because everything - /// possibly overdefined will become overdefined at the soonest possible - /// point. - SmallVector OverdefinedInstWorkList; - SmallVector InstWorkList; - - // The BasicBlock work list - SmallVector BBWorkList; - - /// KnownFeasibleEdges - Entries in this set are edges which have already had - /// PHI nodes retriggered. - using Edge = std::pair; - DenseSet KnownFeasibleEdges; - - DenseMap AnalysisResults; - DenseMap> AdditionalUsers; - - LLVMContext &Ctx; - -public: - void addAnalysis(Function &F, AnalysisResultsForFn A) { - AnalysisResults.insert({&F, std::move(A)}); - } - - const PredicateBase *getPredicateInfoFor(Instruction *I) { - auto A = AnalysisResults.find(I->getParent()->getParent()); - if (A == AnalysisResults.end()) - return nullptr; - return A->second.PredInfo->getPredicateInfoFor(I); - } - - DomTreeUpdater getDTU(Function &F) { - auto A = AnalysisResults.find(&F); - assert(A != AnalysisResults.end() && "Need analysis results for function."); - return {A->second.DT, A->second.PDT, DomTreeUpdater::UpdateStrategy::Lazy}; - } - - SCCPSolver(const DataLayout &DL, - std::function GetTLI, - LLVMContext &Ctx) - : DL(DL), GetTLI(std::move(GetTLI)), Ctx(Ctx) {} - - /// 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).second) - return false; - LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n'); - BBWorkList.push_back(BB); // Add the block to the work list! - return true; - } - - /// TrackValueOfGlobalVariable - Clients can use this method to - /// inform the SCCPSolver that it should track loads and stores to the - /// specified global variable if it can. This is only legal to call if - /// performing Interprocedural SCCP. - void TrackValueOfGlobalVariable(GlobalVariable *GV) { - // We only track the contents of scalar globals. - if (GV->getValueType()->isSingleValueType()) { - ValueLatticeElement &IV = TrackedGlobals[GV]; - if (!isa(GV->getInitializer())) - IV.markConstant(GV->getInitializer()); - } - } - - /// AddTrackedFunction - If the SCCP solver is supposed to track calls into - /// and out of the specified function (which cannot have its address taken), - /// this method must be called. - void AddTrackedFunction(Function *F) { - // Add an entry, F -> undef. - if (auto *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), ValueLatticeElement())); - } else if (!F->getReturnType()->isVoidTy()) - TrackedRetVals.insert(std::make_pair(F, ValueLatticeElement())); - } - - /// AddMustTailCallee - If the SCCP solver finds that this function is called - /// from non-removable musttail call site. - void AddMustTailCallee(Function *F) { - MustTailCallees.insert(F); - } - - /// Returns true if the given function is called from non-removable musttail - /// call site. - bool isMustTailCallee(Function *F) { - return MustTailCallees.count(F); - } - - void AddArgumentTrackedFunction(Function *F) { - TrackingIncomingArguments.insert(F); - } - - /// Returns true if the given function is in the solver's set of - /// argument-tracked functions. - bool isArgumentTrackedFunction(Function *F) { - return TrackingIncomingArguments.count(F); - } - - /// Solve - Solve for constants and executable blocks. - void Solve(); - - /// ResolvedUndefsIn - While solving the dataflow for a function, we assume - /// that branches on undef values cannot reach any of their successors. - /// However, this is not a safe assumption. After we solve dataflow, this - /// method should be use to handle this. If this returns true, the solver - /// should be rerun. - bool ResolvedUndefsIn(Function &F); - - bool isBlockExecutable(BasicBlock *BB) const { - return BBExecutable.count(BB); - } - - // isEdgeFeasible - Return true if the control flow edge from the 'From' basic - // block to the 'To' basic block is currently feasible. - bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const; - - std::vector getStructLatticeValueFor(Value *V) const { - std::vector StructValues; - auto *STy = dyn_cast(V->getType()); - assert(STy && "getStructLatticeValueFor() can be called only on structs"); - for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { - auto I = StructValueState.find(std::make_pair(V, i)); - assert(I != StructValueState.end() && "Value not in valuemap!"); - StructValues.push_back(I->second); - } - return StructValues; - } +void SCCPSolver::addAnalysis(Function &F, AnalysisResultsForFn A) { + AnalysisResults.insert({&F, std::move(A)}); +} - void removeLatticeValueFor(Value *V) { ValueState.erase(V); } +const PredicateBase *SCCPSolver::getPredicateInfoFor(Instruction *I) { + auto A = AnalysisResults.find(I->getParent()->getParent()); + if (A == AnalysisResults.end()) + return nullptr; + return A->second.PredInfo->getPredicateInfoFor(I); +} - const ValueLatticeElement &getLatticeValueFor(Value *V) const { - assert(!V->getType()->isStructTy() && - "Should use getStructLatticeValueFor"); - DenseMap::const_iterator I = - ValueState.find(V); - assert(I != ValueState.end() && - "V not found in ValueState nor Paramstate map!"); - return I->second; - } +DomTreeUpdater SCCPSolver::getDTU(Function &F) { + auto A = AnalysisResults.find(&F); + assert(A != AnalysisResults.end() && "Need analysis results for function."); + return {A->second.DT, A->second.PDT, DomTreeUpdater::UpdateStrategy::Lazy}; +} - /// getTrackedRetVals - Get the inferred return value map. - const MapVector &getTrackedRetVals() { - return TrackedRetVals; - } +SCCPSolver::SCCPSolver( + const DataLayout &DL, + std::function GetTLI, + LLVMContext &Ctx) + : DL(DL), GetTLI(std::move(GetTLI)), Ctx(Ctx) {} - /// getTrackedGlobals - Get and return the set of inferred initializers for - /// global variables. - const DenseMap &getTrackedGlobals() { - return TrackedGlobals; - } +bool SCCPSolver::MarkBlockExecutable(BasicBlock *BB) { + if (!BBExecutable.insert(BB).second) + return false; + LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n'); + BBWorkList.push_back(BB); // Add the block to the work list! + return true; +} - /// getMRVFunctionsTracked - Get the set of functions which return multiple - /// values tracked by the pass. - const SmallPtrSet getMRVFunctionsTracked() { - return MRVFunctionsTracked; +void SCCPSolver::TrackValueOfGlobalVariable(GlobalVariable *GV) { + // We only track the contents of scalar globals. + if (GV->getValueType()->isSingleValueType()) { + ValueLatticeElement &IV = TrackedGlobals[GV]; + if (!isa(GV->getInitializer())) + IV.markConstant(GV->getInitializer()); } +} - /// getMustTailCallees - Get the set of functions which are called - /// from non-removable musttail call sites. - const SmallPtrSet getMustTailCallees() { - return MustTailCallees; - } +void SCCPSolver::AddTrackedFunction(Function *F) { + // Add an entry, F -> undef. + if (auto *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), ValueLatticeElement())); + } else if (!F->getReturnType()->isVoidTy()) + TrackedRetVals.insert(std::make_pair(F, ValueLatticeElement())); +} - /// markOverdefined - Mark the specified value overdefined. This - /// works with both scalars and structs. - void markOverdefined(Value *V) { - if (auto *STy = dyn_cast(V->getType())) - for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) - markOverdefined(getStructValueState(V, i), V); - else - markOverdefined(ValueState[V], V); +std::vector +SCCPSolver::getStructLatticeValueFor(Value *V) const { + std::vector StructValues; + auto *STy = dyn_cast(V->getType()); + assert(STy && "getStructLatticeValueFor() can be called only on structs"); + for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { + auto I = StructValueState.find(std::make_pair(V, i)); + assert(I != StructValueState.end() && "Value not in valuemap!"); + StructValues.push_back(I->second); } + return StructValues; +} - // isStructLatticeConstant - Return true if all the lattice values - // corresponding to elements of the structure are constants, - // false otherwise. - bool isStructLatticeConstant(Function *F, StructType *STy) { - for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { - const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i)); - assert(It != TrackedMultipleRetVals.end()); - ValueLatticeElement LV = It->second; - if (!isConstant(LV)) - return false; - } - return true; - } +const ValueLatticeElement &SCCPSolver::getLatticeValueFor(Value *V) const { + assert(!V->getType()->isStructTy() && "Should use getStructLatticeValueFor"); + DenseMap::const_iterator I = ValueState.find(V); + assert(I != ValueState.end() && + "V not found in ValueState nor Paramstate map!"); + return I->second; +} - /// Helper to return a Constant if \p LV is either a constant or a constant - /// range with a single element. - Constant *getConstant(const ValueLatticeElement &LV) const { - if (LV.isConstant()) - return LV.getConstant(); +void SCCPSolver::markOverdefined(Value *V) { + if (auto *STy = dyn_cast(V->getType())) + for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) + markOverdefined(getStructValueState(V, i), V); + else + markOverdefined(ValueState[V], V); +} - if (LV.isConstantRange()) { - auto &CR = LV.getConstantRange(); - if (CR.getSingleElement()) - return ConstantInt::get(Ctx, *CR.getSingleElement()); - } - return nullptr; +bool SCCPSolver::isStructLatticeConstant(Function *F, StructType *STy) { + for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { + const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i)); + assert(It != TrackedMultipleRetVals.end()); + ValueLatticeElement LV = It->second; + if (!isConstant(LV)) + return false; } + return true; +} -private: - ConstantInt *getConstantInt(const ValueLatticeElement &IV) const { - return dyn_cast_or_null(getConstant(IV)); - } +Constant *SCCPSolver::getConstant(const ValueLatticeElement &LV) const { + if (LV.isConstant()) + return LV.getConstant(); - // pushToWorkList - Helper for markConstant/markOverdefined - void pushToWorkList(ValueLatticeElement &IV, Value *V) { - if (IV.isOverdefined()) - return OverdefinedInstWorkList.push_back(V); - InstWorkList.push_back(V); + if (LV.isConstantRange()) { + auto &CR = LV.getConstantRange(); + if (CR.getSingleElement()) + return ConstantInt::get(Ctx, *CR.getSingleElement()); } + return nullptr; +} - // Helper to push \p V to the worklist, after updating it to \p IV. Also - // prints a debug message with the updated value. - void pushToWorkListMsg(ValueLatticeElement &IV, Value *V) { - LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n'); - pushToWorkList(IV, V); - } +void SCCPSolver::pushToWorkListMsg(ValueLatticeElement &IV, Value *V) { + LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n'); + pushToWorkList(IV, V); +} +bool SCCPSolver::markConstant(ValueLatticeElement &IV, Value *V, Constant *C, + bool MayIncludeUndef) { + if (!IV.markConstant(C, MayIncludeUndef)) + return false; + LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n'); + pushToWorkList(IV, V); + return true; +} - // markConstant - Make a value be marked as "constant". If the value - // is not already a constant, add it to the instruction work list so that - // the users of the instruction are updated later. - bool markConstant(ValueLatticeElement &IV, Value *V, Constant *C, - bool MayIncludeUndef = false) { - if (!IV.markConstant(C, MayIncludeUndef)) - return false; - LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n'); - pushToWorkList(IV, V); - return true; - } +bool SCCPSolver::markOverdefined(ValueLatticeElement &IV, Value *V) { + if (!IV.markOverdefined()) + return false; - bool markConstant(Value *V, Constant *C) { - assert(!V->getType()->isStructTy() && "structs should use mergeInValue"); - return markConstant(ValueState[V], V, C); - } + LLVM_DEBUG(dbgs() << "markOverdefined: "; + if (auto *F = dyn_cast(V)) dbgs() + << "Function '" << F->getName() << "'\n"; + else dbgs() << *V << '\n'); + // Only instructions go on the work list + pushToWorkList(IV, V); + return true; +} - // 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. - bool markOverdefined(ValueLatticeElement &IV, Value *V) { - if (!IV.markOverdefined()) return false; - - LLVM_DEBUG(dbgs() << "markOverdefined: "; - if (auto *F = dyn_cast(V)) dbgs() - << "Function '" << F->getName() << "'\n"; - else dbgs() << *V << '\n'); - // Only instructions go on the work list +bool SCCPSolver::mergeInValue(ValueLatticeElement &IV, Value *V, + ValueLatticeElement MergeWithV, + ValueLatticeElement::MergeOptions Opts) { + if (IV.mergeIn(MergeWithV, Opts)) { pushToWorkList(IV, V); + LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : " + << IV << "\n"); return true; } + return false; +} - /// Merge \p MergeWithV into \p IV and push \p V to the worklist, if \p IV - /// changes. - bool mergeInValue(ValueLatticeElement &IV, Value *V, - ValueLatticeElement MergeWithV, - ValueLatticeElement::MergeOptions Opts = { - /*MayIncludeUndef=*/false, /*CheckWiden=*/false}) { - if (IV.mergeIn(MergeWithV, Opts)) { - pushToWorkList(IV, V); - LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : " - << IV << "\n"); - return true; - } - return false; - } - - bool mergeInValue(Value *V, ValueLatticeElement MergeWithV, - ValueLatticeElement::MergeOptions Opts = { - /*MayIncludeUndef=*/false, /*CheckWiden=*/false}) { - assert(!V->getType()->isStructTy() && - "non-structs should use markConstant"); - return mergeInValue(ValueState[V], V, MergeWithV, Opts); - } - - /// getValueState - Return the ValueLatticeElement object that corresponds to - /// the value. This function handles the case when the value hasn't been seen - /// yet by properly seeding constants etc. - ValueLatticeElement &getValueState(Value *V) { - assert(!V->getType()->isStructTy() && "Should use getStructValueState"); +bool SCCPSolver::mergeInValue(Value *V, ValueLatticeElement MergeWithV, + ValueLatticeElement::MergeOptions Opts) { + assert(!V->getType()->isStructTy() && "non-structs should use markConstant"); + return mergeInValue(ValueState[V], V, MergeWithV, Opts); +} - auto I = ValueState.insert(std::make_pair(V, ValueLatticeElement())); - ValueLatticeElement &LV = I.first->second; +ValueLatticeElement &SCCPSolver::getValueState(Value *V) { + assert(!V->getType()->isStructTy() && "Should use getStructValueState"); - if (!I.second) - return LV; // Common case, already in the map. + auto I = ValueState.insert(std::make_pair(V, ValueLatticeElement())); + ValueLatticeElement &LV = I.first->second; - if (auto *C = dyn_cast(V)) - LV.markConstant(C); // Constants are constant + if (!I.second) + return LV; // Common case, already in the map. - // All others are unknown by default. - return LV; - } + if (auto *C = dyn_cast(V)) + LV.markConstant(C); // Constants are constant - /// getStructValueState - Return the ValueLatticeElement 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. - ValueLatticeElement &getStructValueState(Value *V, unsigned i) { - assert(V->getType()->isStructTy() && "Should use getValueState"); - assert(i < cast(V->getType())->getNumElements() && - "Invalid element #"); + // All others are unknown by default. + return LV; +} - auto I = StructValueState.insert( - std::make_pair(std::make_pair(V, i), ValueLatticeElement())); - ValueLatticeElement &LV = I.first->second; +ValueLatticeElement &SCCPSolver::getStructValueState(Value *V, unsigned i) { + assert(V->getType()->isStructTy() && "Should use getValueState"); + assert(i < cast(V->getType())->getNumElements() && + "Invalid element #"); - if (!I.second) - return LV; // Common case, already in the map. + auto I = StructValueState.insert( + std::make_pair(std::make_pair(V, i), ValueLatticeElement())); + ValueLatticeElement &LV = I.first->second; - if (auto *C = dyn_cast(V)) { - Constant *Elt = C->getAggregateElement(i); + if (!I.second) + return LV; // Common case, already in the map. - if (!Elt) - LV.markOverdefined(); // Unknown sort of constant. - else if (isa(Elt)) - ; // Undef values remain unknown. - else - LV.markConstant(Elt); // Constants are constant. - } + if (auto *C = dyn_cast(V)) { + Constant *Elt = C->getAggregateElement(i); - // All others are underdefined by default. - return LV; + if (!Elt) + LV.markOverdefined(); // Unknown sort of constant. + else if (isa(Elt)) + ; // Undef values remain unknown. + else + LV.markConstant(Elt); // Constants are constant. } - /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB - /// work list if it is not already executable. - bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { - if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) - return false; // This edge is already known to be executable! - - if (!MarkBlockExecutable(Dest)) { - // If the destination is already executable, we just made an *edge* - // feasible that wasn't before. Revisit the PHI nodes in the block - // because they have potentially new operands. - LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() - << " -> " << Dest->getName() << '\n'); - - for (PHINode &PN : Dest->phis()) - visitPHINode(PN); - } - return true; - } + // All others are underdefined by default. + return LV; +} - // getFeasibleSuccessors - Return a vector of booleans to indicate which - // successors are reachable from a given terminator instruction. - void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl &Succs); +bool SCCPSolver::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { + if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) + return false; // This edge is already known to be executable! - // OperandChangedState - This method is invoked on all of the users of an - // instruction that was just changed state somehow. Based on this - // information, we need to update the specified user of this instruction. - void OperandChangedState(Instruction *I) { - if (BBExecutable.count(I->getParent())) // Inst is executable? - visit(*I); - } + if (!MarkBlockExecutable(Dest)) { + // If the destination is already executable, we just made an *edge* + // feasible that wasn't before. Revisit the PHI nodes in the block + // because they have potentially new operands. + LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() + << " -> " << Dest->getName() << '\n'); - // Add U as additional user of V. - void addAdditionalUser(Value *V, User *U) { - auto Iter = AdditionalUsers.insert({V, {}}); - Iter.first->second.insert(U); + for (PHINode &PN : Dest->phis()) + visitPHINode(PN); } + return true; +} // Mark I's users as changed, including AdditionalUsers. - void markUsersAsChanged(Value *I) { - // Functions include their arguments in the use-list. Changed function - // values mean that the result of the function changed. We only need to - // update the call sites with the new function result and do not have to - // propagate the call arguments. - if (isa(I)) { - for (User *U : I->users()) { - if (auto *CB = dyn_cast(U)) - handleCallResult(*CB); - } - } else { - for (User *U : I->users()) - if (auto *UI = dyn_cast(U)) - OperandChangedState(UI); +void SCCPSolver::markUsersAsChanged(Value *I) { + // Functions include their arguments in the use-list. Changed function + // values mean that the result of the function changed. We only need to + // update the call sites with the new function result and do not have to + // propagate the call arguments. + if (isa(I)) { + for (User *U : I->users()) { + if (auto *CB = dyn_cast(U)) + handleCallResult(*CB); } - - auto Iter = AdditionalUsers.find(I); - if (Iter != AdditionalUsers.end()) { - for (User *U : Iter->second) - if (auto *UI = dyn_cast(U)) - OperandChangedState(UI); - } - } - void handleCallOverdefined(CallBase &CB); - void handleCallResult(CallBase &CB); - void handleCallArguments(CallBase &CB); - -private: - friend class InstVisitor; - - // visit implementations - Something changed in this instruction. Either an - // operand made a transition, or the instruction is newly executable. Change - // the value type of I to reflect these changes if appropriate. - void visitPHINode(PHINode &I); - - // Terminators - - void visitReturnInst(ReturnInst &I); - void visitTerminator(Instruction &TI); - - void visitCastInst(CastInst &I); - void visitSelectInst(SelectInst &I); - void visitUnaryOperator(Instruction &I); - void visitBinaryOperator(Instruction &I); - void visitCmpInst(CmpInst &I); - void visitExtractValueInst(ExtractValueInst &EVI); - void visitInsertValueInst(InsertValueInst &IVI); - - void visitCatchSwitchInst(CatchSwitchInst &CPI) { - markOverdefined(&CPI); - visitTerminator(CPI); - } - - // Instructions that cannot be folded away. - - void visitStoreInst (StoreInst &I); - void visitLoadInst (LoadInst &I); - void visitGetElementPtrInst(GetElementPtrInst &I); - - void visitCallInst (CallInst &I) { - visitCallBase(I); - } - - void visitInvokeInst (InvokeInst &II) { - visitCallBase(II); - visitTerminator(II); - } - - void visitCallBrInst (CallBrInst &CBI) { - visitCallBase(CBI); - visitTerminator(CBI); + } else { + for (User *U : I->users()) + if (auto *UI = dyn_cast(U)) + OperandChangedState(UI); } - void visitCallBase (CallBase &CB); - void visitResumeInst (ResumeInst &I) { /*returns void*/ } - void visitUnreachableInst(UnreachableInst &I) { /*returns void*/ } - void visitFenceInst (FenceInst &I) { /*returns void*/ } - - void visitInstruction(Instruction &I) { - // All the instructions we don't do any special handling for just - // go to overdefined. - LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n'); - markOverdefined(&I); + auto Iter = AdditionalUsers.find(I); + if (Iter != AdditionalUsers.end()) { + for (User *U : Iter->second) + if (auto *UI = dyn_cast(U)) + OperandChangedState(UI); } -}; - -} // end anonymous namespace +} // getFeasibleSuccessors - Return a vector of booleans to indicate which // successors are reachable from a given terminator instruction. @@ -1198,6 +914,13 @@ handleCallArguments(CB); } +void SCCPSolver::visitInstruction(Instruction &I) { + // All the instructions we don't do any special handling for just + // go to overdefined. + LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n'); + markOverdefined(&I); +} + void SCCPSolver::handleCallOverdefined(CallBase &CB) { Function *F = CB.getCalledFunction(); @@ -1624,7 +1347,7 @@ return MadeChange; } -static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) { +bool llvm::tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) { Constant *Const = nullptr; if (V->getType()->isStructTy()) { std::vector IVs = Solver.getStructLatticeValueFor(V); @@ -1672,17 +1395,19 @@ return true; } -static bool simplifyInstsInBlock(SCCPSolver &Solver, BasicBlock &BB, - SmallPtrSetImpl &InsertedValues, - Statistic &InstRemovedStat, - Statistic &InstReplacedStat) { +bool llvm::simplifyInstsInBlock(SCCPSolver &Solver, BasicBlock &BB, + SmallPtrSetImpl &InsertedValues, + Statistic &InstRemovedStat, + Statistic &InstReplacedStat) { bool MadeChanges = false; for (Instruction &Inst : make_early_inc_range(BB)) { if (Inst.getType()->isVoidTy()) continue; if (tryToReplaceWithConstant(Solver, &Inst)) { - if (Inst.isSafeToRemove()) + if (Inst.isSafeToRemove()) { + Solver.removeLatticeValueFor(&Inst); Inst.eraseFromParent(); + } // Hey, we just changed something! MadeChanges = true; ++InstRemovedStat; diff --git a/test/Transforms/FunctionSpecialize/function-specialize-recursive.ll b/test/Transforms/FunctionSpecialize/function-specialize-recursive.ll new file mode 100644 --- /dev/null +++ b/test/Transforms/FunctionSpecialize/function-specialize-recursive.ll @@ -0,0 +1,43 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -function-specialize -inline -instcombine -S < %s | FileCheck %s +target triple = "aarch64-unknown-linux-gnu" + +@Global = internal constant i32 1, align 4 + +; Function Attrs: nofree nounwind uwtable +define internal void @recursiveFunc(i32* nocapture readonly %arg) { + %temp = alloca i32, align 4 + %arg.load = load i32, i32* %arg, align 4 + %arg.cmp = icmp slt i32 %arg.load, 9 + br i1 %arg.cmp, label %block6, label %ret.block + +block6: + call void @print_val(i32 %arg.load) + %arg.add = add nsw i32 %arg.load, 1 + store i32 %arg.add, i32* %temp, align 4 + call void @recursiveFunc(i32* nonnull %temp) + br label %ret.block + +ret.block: + ret void +} + +; Function Attrs: nofree nounwind +declare dso_local void @print_val(i32) + +; Function Attrs: nofree nounwind uwtable +define i32 @main() { +; CHECK-LABEL: @main( +; CHECK-NEXT: call void @print_val(i32 1) +; CHECK-NEXT: call void @print_val(i32 2) +; CHECK-NEXT: call void @print_val(i32 3) +; CHECK-NEXT: call void @print_val(i32 4) +; CHECK-NEXT: call void @print_val(i32 5) +; CHECK-NEXT: call void @print_val(i32 6) +; CHECK-NEXT: call void @print_val(i32 7) +; CHECK-NEXT: call void @print_val(i32 8) +; CHECK-NEXT: ret i32 0 +; + call void @recursiveFunc(i32* nonnull @Global) + ret i32 0 +} diff --git a/test/Transforms/FunctionSpecialize/function-specialize.ll b/test/Transforms/FunctionSpecialize/function-specialize.ll new file mode 100644 --- /dev/null +++ b/test/Transforms/FunctionSpecialize/function-specialize.ll @@ -0,0 +1,52 @@ +; RUN: opt -function-specialize -deadargelim -inline -S < %s | FileCheck %s + +target triple = "aarch64-unknown-linux-gnueabi" + +; CHECK-LABEL: @main(i64 %x, i1 %flag) { +; CHECK: entry: +; CHECK-NEXT: br i1 %flag, label %plus, label %minus +; CHECK: plus: +; CHECK-NEXT: [[TMP0:%.+]] = add i64 %x, 1 +; CHECH-NEXT: br label %merge +; CHECK: minus: +; CHECK-NEXT: [[TMP1:%.+]] = sub i64 %x, 1 +; CHECK-NEXT: br label %merge +; CHECK: merge: +; CHECK-NEXT: [[TMP2:%.+]] = phi i64 [ [[TMP0]], %plus ], [ [[TMP1]], %minus ] +; CHECK-NEXT: ret i64 [[TMP2]] +; CHECK-NEXT: } +; +define i64 @main(i64 %x, i1 %flag) { +entry: + br i1 %flag, label %plus, label %minus + +plus: + %tmp0 = call i64 @compute(i64 %x, i64 (i64)* @plus) + br label %merge + +minus: + %tmp1 = call i64 @compute(i64 %x, i64 (i64)* @minus) + br label %merge + +merge: + %tmp2 = phi i64 [ %tmp0, %plus ], [ %tmp1, %minus] + ret i64 %tmp2 +} + +define internal i64 @compute(i64 %x, i64 (i64)* %binop) { +entry: + %tmp0 = call i64 %binop(i64 %x) + ret i64 %tmp0 +} + +define internal i64 @plus(i64 %x) { +entry: + %tmp0 = add i64 %x, 1 + ret i64 %tmp0 +} + +define internal i64 @minus(i64 %x) { +entry: + %tmp0 = sub i64 %x, 1 + ret i64 %tmp0 +} diff --git a/test/Transforms/FunctionSpecialize/function-specialize2.ll b/test/Transforms/FunctionSpecialize/function-specialize2.ll new file mode 100644 --- /dev/null +++ b/test/Transforms/FunctionSpecialize/function-specialize2.ll @@ -0,0 +1,88 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --include-generated-funcs +; RUN: opt -function-specialize -deadargelim -S < %s | FileCheck %s + +target triple = "aarch64-unknown-linux-gnu" + +; Function Attrs: nounwind uwtable +define internal i32 @func(i32* %0, i32 %1, void (i32*)* nocapture %2) { + %4 = alloca i32, align 4 + store i32 %1, i32* %4, align 4 + %5 = load i32, i32* %4, align 4 + %6 = icmp slt i32 %5, 1 + br i1 %6, label %14, label %7 + +7: ; preds = %3 + %8 = load i32, i32* %4, align 4 + %9 = sext i32 %8 to i64 + %10 = getelementptr inbounds i32, i32* %0, i64 %9 + call void %2(i32* %10) + %11 = load i32, i32* %4, align 4 + %12 = add nsw i32 %11, -1 + %13 = call i32 @func(i32* %0, i32 %12, void (i32*)* %2) + br label %14 + +14: ; preds = %3, %7 + ret i32 0 +} + +; Function Attrs: nofree norecurse nounwind uwtable +define internal void @increment(i32* nocapture %0) { + %2 = load i32, i32* %0, align 4 + %3 = add nsw i32 %2, 1 + store i32 %3, i32* %0, align 4 + ret void +} + +; Function Attrs: nofree norecurse nounwind uwtable +define internal void @decrement(i32* nocapture %0) { + %2 = load i32, i32* %0, align 4 + %3 = add nsw i32 %2, -1 + store i32 %3, i32* %0, align 4 + ret void +} + +; Function Attrs: nounwind uwtable +define i32 @main(i32* %0, i32 %1) { +; CHECK: [[TMP3:%.*]] = call i32 @func.2(i32* [[TMP0:%.*]], i32 [[TMP1:%.*]]) + %3 = call i32 @func(i32* %0, i32 %1, void (i32*)* nonnull @increment) +; CHECK: [[TMP4:%.*]] = call i32 @func.1(i32* [[TMP0]], i32 [[TMP3]]) + %4 = call i32 @func(i32* %0, i32 %3, void (i32*)* nonnull @decrement) + ret i32 %4 +} + +; CHECK: @func.1( +; CHECK: [[TMP3:%.*]] = alloca i32, align 4 +; CHECK: store i32 [[TMP1:%.*]], i32* [[TMP3]], align 4 +; CHECK: [[TMP4:%.*]] = load i32, i32* [[TMP3]], align 4 +; CHECK: [[TMP5:%.*]] = icmp slt i32 [[TMP4]], 1 +; CHECK: br i1 [[TMP5]], label [[TMP13:%.*]], label [[TMP6:%.*]] +; CHECK: 6: +; CHECK: [[TMP7:%.*]] = load i32, i32* [[TMP3]], align 4 +; CHECK: [[TMP8:%.*]] = sext i32 [[TMP7]] to i64 +; CHECK: [[TMP9:%.*]] = getelementptr inbounds i32, i32* [[TMP0:%.*]], i64 [[TMP8]] +; CHECK: call void @decrement(i32* [[TMP9]]) +; CHECK: [[TMP10:%.*]] = load i32, i32* [[TMP3]], align 4 +; CHECK: [[TMP11:%.*]] = add nsw i32 [[TMP10]], -1 +; CHECK: [[TMP12:%.*]] = call i32 @func.1(i32* [[TMP0]], i32 [[TMP11]]) +; CHECK: br label [[TMP13]] +; CHECK: 13: +; CHECK: ret i32 0 +; +; +; CHECK: @func.2( +; CHECK: [[TMP3:%.*]] = alloca i32, align 4 +; CHECK: store i32 [[TMP1:%.*]], i32* [[TMP3]], align 4 +; CHECK: [[TMP4:%.*]] = load i32, i32* [[TMP3]], align 4 +; CHECK: [[TMP5:%.*]] = icmp slt i32 [[TMP4]], 1 +; CHECK: br i1 [[TMP5]], label [[TMP13:%.*]], label [[TMP6:%.*]] +; CHECK: 6: +; CHECK: [[TMP7:%.*]] = load i32, i32* [[TMP3]], align 4 +; CHECK: [[TMP8:%.*]] = sext i32 [[TMP7]] to i64 +; CHECK: [[TMP9:%.*]] = getelementptr inbounds i32, i32* [[TMP0:%.*]], i64 [[TMP8]] +; CHECK: call void @increment(i32* [[TMP9]]) +; CHECK: [[TMP10:%.*]] = load i32, i32* [[TMP3]], align 4 +; CHECK: [[TMP11:%.*]] = add nsw i32 [[TMP10]], -1 +; CHECK: [[TMP12:%.*]] = call i32 @func.2(i32* [[TMP0]], i32 [[TMP11]]) +; CHECK: br label [[TMP13]] +; CHECK: ret i32 0 +;