diff --git a/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp b/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp --- a/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp +++ b/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp @@ -92,6 +92,25 @@ cl::desc("Enable specialization of functions that take a literal constant " "as an argument.")); +namespace { +// 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 specialisation 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){}; +}; +} // Anonymous namespace + // 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 +275,27 @@ bool specializeFunctions(SmallVectorImpl &FuncDecls, SmallVectorImpl &CurrentSpecializations) { - - // Attempt to specialize the argument-tracked functions. bool Changed = false; for (auto *F : FuncDecls) { - if (specializeFunction(F, CurrentSpecializations)) { - Changed = true; - LLVM_DEBUG(dbgs() << "FnSpecialization: Can specialize this func.\n"); - } else { + if (!isCandidateFunction(F, CurrentSpecializations)) + continue; + + auto Cost = getSpecializationCost(F); + if (!Cost.isValid()) { LLVM_DEBUG( - dbgs() << "FnSpecialization: Cannot specialize this func.\n"); + 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; } } @@ -333,15 +363,79 @@ 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 = + ForceFunctionSpecialization + ? 1 + : getSpecializationBonus(&FormalArg, ActualArg) - Cost; + + if (Gain <= 0) + continue; + Worklist.push_back({F, &FormalArg, ActualArg, Gain}); + } + + if (Worklist.empty()) + continue; + + // Sort the candidates in descending order. + llvm::sort(Worklist, + [](ArgInfo &L, ArgInfo &R) { return L.Gain > R.Gain; }); + + // TODO: truncate the worklist to 'MaxConstantsThreshold' candidates if + // necessary. + if (Worklist.size() > MaxConstantsThreshold) { + Worklist.clear(); + continue; + } + + if (IsPartial || Worklist.size() < ActualConstArg.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. + break; + } + return Worklist; + } + bool isCandidateFunction(Function *F, + SmallVectorImpl &Specializations) { // Do not specialize the cloned function again. if (SpecializedFuncs.contains(F)) return false; @@ -362,84 +456,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->getArg(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; @@ -580,7 +623,6 @@ /// argument. bool isArgumentInteresting(Argument *A, SmallVectorImpl &Constants, - const InstructionCost &FnSpecCost, bool &IsPartial) { // For now, don't attempt to specialize functions based on the values of // composite types. @@ -608,42 +650,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; } @@ -681,7 +689,7 @@ // For now, constant expressions are fine but only if they are function // calls. - if (auto *CE = dyn_cast(V)) + if (auto *CE = dyn_cast(V)) if (!isa(CE->getOperand(0))) return false;