Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- FunctionSpecialization.h - Function Specialization -----------------===//

//

// 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

//

//===----------------------------------------------------------------------===//

//

// This specialises functions with constant parameters. Constant parameters

// like function pointers and constant globals are propagated to the callee by

// specializing the function. The main benefit of this pass at the moment is

// that indirect calls are transformed into direct calls, which provides inline

// opportunities that the inliner would not have been able to achieve. That's

// why function specialisation is run before the inliner in the optimisation

// pipeline; that is by design. Otherwise, we would only benefit from constant

// passing, which is a valid use-case too, but hasn't been explored much in

// terms of performance uplifts, cost-model and compile-time impact.

//

// Current limitations:

// - It does not yet handle integer ranges. We do support "literal constants",

//   but that's off by default under an option.

// - The cost-model could be further looked into (it mainly focuses on inlining

//   benefits),

//

// Ideas:

// - With a function specialization attribute for arguments, we could have

//   a direct way to steer function specialization, avoiding the cost-model,

//   and thus control compile-times / code-size.

//

// Todos:

// - Specializing recursive functions relies on running the transformation a

//   number of times, which is controlled by option

//   `func-specialization-max-iters`. Thus, increasing this value and the

//   number of iterations, will linearly increase the number of times recursive

//   functions get specialized, see also the discussion in

//   https://reviews.llvm.org/D106426 for details. Perhaps there is a

//   compile-time friendlier way to control/limit the number of specialisations

//   for recursive functions.

// - Don't transform the function if function specialization does not trigger;

//   the SCCPSolver may make IR changes.

//

// References:

// - 2021 LLVM Dev Mtg “Introducing function specialisation, and can we enable

//   it by default?”, https://www.youtube.com/watch?v=zJiCjeXgV5Q

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H

#define LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H

#include "llvm/Analysis/CodeMetrics.h"

#include "llvm/Analysis/InlineCost.h"

#include "llvm/Analysis/LoopInfo.h"

#include "llvm/Analysis/TargetTransformInfo.h"

#include "llvm/Transforms/Scalar/SCCP.h"

#include "llvm/Transforms/Utils/Cloning.h"

#include "llvm/Transforms/Utils/SCCPSolver.h"

#include "llvm/Transforms/Utils/SizeOpts.h"

using namespace llvm;

namespace llvm {

// Specialization signature, used to uniquely designate a specialization within

// a function.

struct SpecSig {

  // Hashing support, used to distinguish between ordinary, empty, or tombstone

  // keys.

  unsigned Key = 0;

  SmallVector<ArgInfo, 4> Args;

  bool operator==(const SpecSig &Other) const {

    if (Key != Other.Key || Args.size() != Other.Args.size())

      return false;

    for (size_t I = 0; I < Args.size(); ++I)

      if (Args[I] != Other.Args[I])

        return false;

    return true;

  }

  friend hash_code hash_value(const SpecSig &S) {

    return hash_combine(hash_value(S.Key),

                        hash_combine_range(S.Args.begin(), S.Args.end()));

  }

};

// Specialization instance.

struct Spec {

  // Original function.

  Function *F;

  // Cloned function, a specialized version of the original one.

  Function *Clone = nullptr;

  // Specialization signature.

  SpecSig Sig;

  // Profitability of the specialization.

  InstructionCost Gain;

  // List of call sites, matching this specialization.

  SmallVector<CallBase *> CallSites;

  Spec(Function *F, const SpecSig &S, InstructionCost G)

      : F(F), Sig(S), Gain(G) {}

  Spec(Function *F, const SpecSig &&S, InstructionCost G)

      : F(F), Sig(S), Gain(G) {}

};

// Map of potential specializations for each function. The FunctionSpecializer

// keeps the discovered specialisation opportunities for the module in a single

// vector, where the specialisations of each function form a contiguous range.

// This map's value is the beginning and the end of that range.

using SpecMap = DenseMap<Function *, std::pair<unsigned, unsigned>>;

class FunctionSpecializer {

  /// The IPSCCP Solver.

  SCCPSolver &Solver;

  Module &M;

  /// Analysis manager, needed to invalidate analyses.

  FunctionAnalysisManager *FAM;

  /// Analyses used to help determine if a function should be specialized.

  std::function<const TargetLibraryInfo &(Function &)> GetTLI;

  std::function<TargetTransformInfo &(Function &)> GetTTI;

  std::function<AssumptionCache &(Function &)> GetAC;

  // The number of functions specialised, used for collecting statistics and

  // also in the cost model.

  unsigned NbFunctionsSpecialized = 0;

  SmallPtrSet<Function *, 32> SpecializedFuncs;

  SmallPtrSet<Function *, 32> FullySpecialized;

  DenseMap<Function *, CodeMetrics> FunctionMetrics;

public:

  FunctionSpecializer(

      SCCPSolver &Solver, Module &M, FunctionAnalysisManager *FAM,

      std::function<const TargetLibraryInfo &(Function &)> GetTLI,

      std::function<TargetTransformInfo &(Function &)> GetTTI,

      std::function<AssumptionCache &(Function &)> GetAC)

      : Solver(Solver), M(M), FAM(FAM), GetTLI(GetTLI), GetTTI(GetTTI),

        GetAC(GetAC) {}

  ~FunctionSpecializer() {

    // Eliminate dead code.

    removeDeadFunctions();

    cleanUpSSA();

  }

  bool isClonedFunction(Function *F) { return SpecializedFuncs.count(F); }

  bool run();

private:

  Constant *getPromotableAlloca(AllocaInst *Alloca, CallInst *Call);

  /// A constant stack value is an AllocaInst that has a single constant

  /// value stored to it. Return this constant if such an alloca stack value

  /// is a function argument.

  Constant *getConstantStackValue(CallInst *Call, Value *Val);

  /// Iterate over the argument tracked functions see if there

  /// are any new constant values for the call instruction via

  /// stack variables.

  void promoteConstantStackValues();

  /// Clean up fully specialized functions.

  void removeDeadFunctions();

  /// Remove any ssa_copy intrinsics that may have been introduced.

  void cleanUpSSA();

  // Compute the code metrics for function \p F.

  CodeMetrics &analyzeFunction(Function *F);

  /// @brief  Find potential specialization opportunities.

  /// @param F Function to specialize

  /// @param Cost Cost of specializing a function. Final gain is this cost

  /// minus benefit

  /// @param AllSpecs A vector to add potential specializations to.

  /// @param SM  A map for a function's specialisation range

  /// @return True, if any potential specializations were found

  bool findSpecializations(Function *F, InstructionCost Cost,

                           SmallVectorImpl<Spec> &AllSpecs, SpecMap &SM);

  bool isCandidateFunction(Function *F);

  /// @brief Create a specialization of \p F and prime the SCCPSolver

  /// @param F Function to specialize

  /// @param S Which specialization to create

  /// @return The new, cloned function

  Function *createSpecialization(Function *F, const SpecSig &S);

  /// Compute and return the cost of specializing function \p F.

  InstructionCost getSpecializationCost(Function *F);

  /// Compute a bonus for replacing argument \p A with constant \p C.

  InstructionCost getSpecializationBonus(Argument *A, Constant *C,

                                         const LoopInfo &LI);

  /// Determine if it is possible to specialise the function for constant values

  /// of the formal parameter \p A.

  bool isArgumentInteresting(Argument *A);

  /// Check if the value \p V  (an actual argument) is a constant or can only

  /// have a constant value. Return that constant.

  Constant *getCandidateConstant(Value *V);

  /// @brief Find and update calls to \p F, which match a specialization

  /// @param F Orginal function

  /// @param Begin Start of a range of possibly matching specialisations

  /// @param End End of a range (exclusive) of possibly matching specialisations

  void updateCallSites(Function *F, const Spec *Begin, const Spec *End);

};

} // namespace llvm

#endif // LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H