Index: llvm/lib/Transforms/IPO/FunctionSpecialization.cpp =================================================================== --- llvm/lib/Transforms/IPO/FunctionSpecialization.cpp +++ llvm/lib/Transforms/IPO/FunctionSpecialization.cpp @@ -92,6 +92,23 @@ cl::desc("Enable specialization of functions that take a literal constant " "as an argument.")); +// Bookkeeping struct to pass data from the analysis and profitability phase +// to the actual transform helper functions. +struct ArgInfo { + Function *Fn; // The function to perform specialisaiton on. + Argument *Arg; // The Formal argument being analysed. + Constant *Const; // A corresponding actual constant argument. + InstructionCost Gain; // Profitability: Gain = Bonus - Cost. + + // Flag if this will be a partial specialization, in which case we will need + // to keep the original function around in addition to the added + // specializations. + bool Partial = false; + + ArgInfo(Function *F, Argument *A, Constant *C, InstructionCost G) + : Fn(F), Arg(A), Const(C), Gain(G) {}; +}; + // Helper to check if \p LV is either a constant or a constant // range with a single element. This should cover exactly the same cases as the // old ValueLatticeElement::isConstant() and is intended to be used in the @@ -256,16 +273,26 @@ bool specializeFunctions(SmallVectorImpl &FuncDecls, SmallVectorImpl &CurrentSpecializations) { - - // Attempt to specialize the argument-tracked functions. bool Changed = false; for (auto *F : FuncDecls) { - if (specializeFunction(F, CurrentSpecializations)) { + if (!isCandidateFunction(F, CurrentSpecializations)) + continue; + + auto Cost = getSpecializationCost(F); + if (!Cost.isValid()) { + LLVM_DEBUG(dbgs() << "FnSpecialization: Invalid specialisation cost.\n"); + continue; + } + + auto ConstArgs = calculateGains(F, Cost); + if (ConstArgs.empty()) { + LLVM_DEBUG(dbgs() << "FnSpecialization: no possible constants found\n"); + continue; + } + + for (auto &CA : ConstArgs) { + specializeFunction(CA, CurrentSpecializations); Changed = true; - LLVM_DEBUG(dbgs() << "FnSpecialization: Can specialize this func.\n"); - } else { - LLVM_DEBUG( - dbgs() << "FnSpecialization: Cannot specialize this func.\n"); } } @@ -333,15 +360,80 @@ return Clone; } - /// 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 and - /// false otherwise. - bool specializeFunction(Function *F, - SmallVectorImpl &Specializations) { + /// This function decides whether it's worthwhile to specialize function \p F + /// based on the known constant values its arguments can take on, i.e. it + /// calculates a gain and returns a list of actual arguments that are deemed + /// profitable to specialize. 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. + SmallVector calculateGains(Function *F, InstructionCost Cost) { + SmallVector Worklist; + // 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 &FormalArg : F->args()) { + LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing arg: " + << FormalArg.getName() << "\n"); + // 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). + bool IsPartial = true; + SmallVector ActualConstArg; + if (!isArgumentInteresting(&FormalArg, ActualConstArg, IsPartial)) { + LLVM_DEBUG(dbgs() << "FnSpecialization: Argument is not interesting\n"); + continue; + } + + for (auto *ActualArg : ActualConstArg) { + InstructionCost Gain = + getSpecializationBonus(&FormalArg, ActualArg) - Cost; + if (ForceFunctionSpecialization || Gain > 0) + Worklist.push_back({F, &FormalArg, ActualArg, Gain}); + } + + if (Worklist.empty()) + continue; + // Sort the candidates in descending order. + std::sort(Worklist.begin(), Worklist.end(), [] (ArgInfo L, ArgInfo R) { + return L.Gain > R.Gain; } ); + + // Truncate the worklist to 'MaxConstantsThreshold' candidates if + // necessary. + if (Worklist.size() > MaxConstantsThreshold) { + LLVM_DEBUG(dbgs() << "FnSpecialization: number of constants exceed " + << "the maximum number of constants threshold.\n" + << "Truncating worklist to " << MaxConstantsThreshold + << " candidates.\n"); + Worklist.erase(Worklist.begin() + MaxConstantsThreshold, + Worklist.end()); + } + + if (IsPartial || ActualConstArg.size() != Worklist.size()) + for (auto &ActualArg : Worklist) + ActualArg.Partial = true; + + LLVM_DEBUG( + dbgs() << "Sorted list of candidates by gain:\n"; + for (auto &C : Worklist) { + dbgs() << "- Function = " << C.Fn->getName() << ", "; + dbgs() << "FormalArg = " << C.Arg->getName() << ", "; + dbgs() << "ActualArg = " << C.Const->getName() << ", "; + dbgs() << "Gain = " << C.Gain << "\n"; + } + ); + + // FIXME: Only one argument per function. + return Worklist; + } + return Worklist; + } + + bool isCandidateFunction(Function *F, + SmallVectorImpl &Specializations) { // Do not specialize the cloned function again. if (SpecializedFuncs.contains(F)) return false; @@ -362,84 +454,33 @@ LLVM_DEBUG(dbgs() << "FnSpecialization: Try function: " << F->getName() << "\n"); + return true; + } - // 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. - auto FnSpecCost = getSpecializationCost(F); - if (!FnSpecCost.isValid()) { - LLVM_DEBUG(dbgs() << "FnSpecialization: Invalid specialisation cost.\n"); - return false; - } - - LLVM_DEBUG(dbgs() << "FnSpecialization: func specialisation cost: "; - FnSpecCost.print(dbgs()); dbgs() << "\n"); - - // 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()) { - LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing arg: " << A.getName() - << "\n"); - // 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, FnSpecCost, IsPartial)) { - LLVM_DEBUG(dbgs() << "FnSpecialization: Argument is not interesting\n"); - continue; - } + void specializeFunction(ArgInfo &AI, + SmallVectorImpl &Specializations) { + Function *Clone = cloneCandidateFunction(AI.Fn); + Argument *ClonedArg = Clone->arg_begin() + AI.Arg->getArgNo(); - assert(!Constants.empty() && "No constants on which to specialize"); - LLVM_DEBUG(dbgs() << "FnSpecialization: Argument is interesting!\n" - << "FnSpecialization: Specializing '" << F->getName() - << "' on argument: " << A << "\n" - << "FnSpecialization: Constants are:\n\n"; - for (unsigned I = 0; I < Constants.size(); ++I) dbgs() - << *Constants[I] << "\n"; - dbgs() << "FnSpecialization: End of constants\n\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); - NbFunctionsSpecialized++; - } + // Rewrite calls to the function so that they call the clone instead. + rewriteCallSites(AI.Fn, Clone, *ClonedArg, AI.Const); - // If the function has been completely specialized, the original function - // is no longer needed. Mark it unreachable. - if (!IsPartial) - Solver.markFunctionUnreachable(F); + // 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(AI.Fn, ClonedArg, AI.Const); - // FIXME: Only one argument per function. - return true; - } + // Mark all the specialized functions + Specializations.push_back(Clone); + NbFunctionsSpecialized++; - return false; + // If the function has been completely specialized, the original function + // is no longer needed. Mark it unreachable. + if (!AI.Partial) + Solver.markFunctionUnreachable(AI.Fn); } - /// Compute the cost of specializing function \p F. + /// Compute and return the cost of specializing function \p F. InstructionCost getSpecializationCost(Function *F) { // Compute the code metrics for the function. SmallPtrSet EphValues; @@ -578,9 +619,7 @@ /// /// \returns true if the function should be specialized on the given /// argument. - bool isArgumentInteresting(Argument *A, - SmallVectorImpl &Constants, - const InstructionCost &FnSpecCost, + bool isArgumentInteresting(Argument *A, SmallVectorImpl &Constants, bool &IsPartial) { // For now, don't attempt to specialize functions based on the values of // composite types. @@ -608,42 +647,8 @@ // // TODO 2: this currently does not support constants, i.e. integer ranges. // - SmallVector PossibleConstants; - bool AllConstant = getPossibleConstants(A, PossibleConstants); - if (PossibleConstants.empty()) { - LLVM_DEBUG(dbgs() << "FnSpecialization: no possible constants found\n"); - return false; - } - if (PossibleConstants.size() > MaxConstantsThreshold) { - LLVM_DEBUG(dbgs() << "FnSpecialization: number of constants found exceed " - << "the maximum number of constants threshold.\n"); - return false; - } - - for (auto *C : PossibleConstants) { - LLVM_DEBUG(dbgs() << "FnSpecialization: Constant: " << *C << "\n"); - if (ForceFunctionSpecialization) { - LLVM_DEBUG(dbgs() << "FnSpecialization: Forced!\n"); - Constants.push_back(C); - continue; - } - if (getSpecializationBonus(A, C) > FnSpecCost) { - LLVM_DEBUG(dbgs() << "FnSpecialization: profitable!\n"); - Constants.push_back(C); - } else { - LLVM_DEBUG(dbgs() << "FnSpecialization: not profitable\n"); - } - } - - // 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(); - + IsPartial = !getPossibleConstants(A, Constants); + LLVM_DEBUG(dbgs() << "FnSpecialization: interesting arg: " << *A << "\n"); return true; } Index: llvm/test/Transforms/FunctionSpecialization/function-specialization4.ll =================================================================== --- llvm/test/Transforms/FunctionSpecialization/function-specialization4.ll +++ llvm/test/Transforms/FunctionSpecialization/function-specialization4.ll @@ -38,7 +38,7 @@ ret i32 %add1 } -; CONST1-NOT: define internal i32 @foo.1(i32 %x, i32* %b, i32* %c) +; CONST1: define internal i32 @foo.1(i32 %x, i32* %b, i32* %c) ; CONST1-NOT: define internal i32 @foo.2(i32 %x, i32* %b, i32* %c) ; CHECK: define internal i32 @foo.1(i32 %x, i32* %b, i32* %c) {