third_party/llvm-16.0/llvm/lib/Analysis/InlineOrder.cpp - SwiftShader - Git at Google

 //===- InlineOrder.cpp - Inlining order abstraction -*- C++ ---*-----------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//

 #include "llvm/Analysis/InlineOrder.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InlineAdvisor.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Support/CommandLine.h"

 using namespace llvm;

 #define DEBUG_TYPE "inline-order"

 enum class InlinePriorityMode : int { Size, Cost, CostBenefit, ML };

 static cl::opt<InlinePriorityMode> UseInlinePriority(
     "inline-priority-mode", cl::init(InlinePriorityMode::Size), cl::Hidden,
     cl::desc("Choose the priority mode to use in module inline"),
     cl::values(clEnumValN(InlinePriorityMode::Size, "size",
                           "Use callee size priority."),
                clEnumValN(InlinePriorityMode::Cost, "cost",
                           "Use inline cost priority."),
                clEnumValN(InlinePriorityMode::CostBenefit, "cost-benefit",
                           "Use cost-benefit ratio."),
                clEnumValN(InlinePriorityMode::ML, "ml",
                           "Use ML.")));

 static cl::opt<int> ModuleInlinerTopPriorityThreshold(
     "moudle-inliner-top-priority-threshold", cl::Hidden, cl::init(0),
     cl::desc("The cost threshold for call sites that get inlined without the "
              "cost-benefit analysis"));

 namespace {

 llvm::InlineCost getInlineCostWrapper(CallBase &CB,
                                       FunctionAnalysisManager &FAM,
                                       const InlineParams &Params) {
   Function &Caller = *CB.getCaller();
   ProfileSummaryInfo *PSI =
       FAM.getResult<ModuleAnalysisManagerFunctionProxy>(Caller)
           .getCachedResult<ProfileSummaryAnalysis>(
               *CB.getParent()->getParent()->getParent());

   auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(Caller);
   auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
     return FAM.getResult<AssumptionAnalysis>(F);
   };
   auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
     return FAM.getResult<BlockFrequencyAnalysis>(F);
   };
   auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
     return FAM.getResult<TargetLibraryAnalysis>(F);
   };

   Function &Callee = *CB.getCalledFunction();
   auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
   bool RemarksEnabled =
       Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled(
           DEBUG_TYPE);
   return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI,
                        GetBFI, PSI, RemarksEnabled ? &ORE : nullptr);
 }

 class SizePriority {
 public:
   SizePriority() = default;
   SizePriority(const CallBase *CB, FunctionAnalysisManager &,
                const InlineParams &) {
     Function *Callee = CB->getCalledFunction();
     Size = Callee->getInstructionCount();
   }

   static bool isMoreDesirable(const SizePriority &P1, const SizePriority &P2) {
     return P1.Size < P2.Size;
   }

 private:
   unsigned Size = UINT_MAX;
 };

 class CostPriority {
 public:
   CostPriority() = default;
   CostPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
                const InlineParams &Params) {
     auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params);
     if (IC.isVariable())
       Cost = IC.getCost();
     else
       Cost = IC.isNever() ? INT_MAX : INT_MIN;
   }

   static bool isMoreDesirable(const CostPriority &P1, const CostPriority &P2) {
     return P1.Cost < P2.Cost;
   }

 private:
   int Cost = INT_MAX;
 };

 class CostBenefitPriority {
 public:
   CostBenefitPriority() = default;
   CostBenefitPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
                       const InlineParams &Params) {
     auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params);
     Cost = IC.getCost();
     StaticBonusApplied = IC.getStaticBonusApplied();
     CostBenefit = IC.getCostBenefit();
   }

   static bool isMoreDesirable(const CostBenefitPriority &P1,
                               const CostBenefitPriority &P2) {
     // We prioritize call sites in the dictionary order of the following
     // priorities:
     //
     // 1. Those call sites that are expected to reduce the caller size when
     //    inlined.  Within them, we prioritize those call sites with bigger
     //    reduction.
     //
     // 2. Those call sites that have gone through the cost-benefit analysis.
     //    Currently, they are limited to hot call sites.  Within them, we
     //    prioritize those call sites with higher benefit-to-cost ratios.
     //
     // 3. Remaining call sites are prioritized according to their costs.

     // We add back StaticBonusApplied to determine whether we expect the caller
     // to shrink (even if we don't delete the callee).
     bool P1ReducesCallerSize =
         P1.Cost + P1.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
     bool P2ReducesCallerSize =
         P2.Cost + P2.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
     if (P1ReducesCallerSize || P2ReducesCallerSize) {
       // If one reduces the caller size while the other doesn't, then return
       // true iff P1 reduces the caller size.
       if (P1ReducesCallerSize != P2ReducesCallerSize)
         return P1ReducesCallerSize;

       // If they both reduce the caller size, pick the one with the smaller
       // cost.
       return P1.Cost < P2.Cost;
     }

     bool P1HasCB = P1.CostBenefit.has_value();
     bool P2HasCB = P2.CostBenefit.has_value();
     if (P1HasCB || P2HasCB) {
       // If one has undergone the cost-benefit analysis while the other hasn't,
       // then return true iff P1 has.
       if (P1HasCB != P2HasCB)
         return P1HasCB;

       // If they have undergone the cost-benefit analysis, then pick the one
       // with a higher benefit-to-cost ratio.
       APInt LHS = P1.CostBenefit->getBenefit() * P2.CostBenefit->getCost();
       APInt RHS = P2.CostBenefit->getBenefit() * P1.CostBenefit->getCost();
       return LHS.ugt(RHS);
     }

     // Remaining call sites are ordered according to their costs.
     return P1.Cost < P2.Cost;
   }

 private:
   int Cost = INT_MAX;
   int StaticBonusApplied = 0;
   std::optional<CostBenefitPair> CostBenefit;
 };

 class MLPriority {
 public:
   MLPriority() = default;
   MLPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
              const InlineParams &Params) {
     auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params);
     if (IC.isVariable())
       Cost = IC.getCost();
     else
       Cost = IC.isNever() ? INT_MAX : INT_MIN;
   }

   static bool isMoreDesirable(const MLPriority &P1, const MLPriority &P2) {
     return P1.Cost < P2.Cost;
   }

 private:
   int Cost = INT_MAX;
 };

 template <typename PriorityT>
 class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
   using T = std::pair<CallBase *, int>;

   bool hasLowerPriority(const CallBase *L, const CallBase *R) const {
     const auto I1 = Priorities.find(L);
     const auto I2 = Priorities.find(R);
     assert(I1 != Priorities.end() && I2 != Priorities.end());
     return PriorityT::isMoreDesirable(I2->second, I1->second);
   }

   bool updateAndCheckDecreased(const CallBase *CB) {
     auto It = Priorities.find(CB);
     const auto OldPriority = It->second;
     It->second = PriorityT(CB, FAM, Params);
     const auto NewPriority = It->second;
     return PriorityT::isMoreDesirable(OldPriority, NewPriority);
   }

   // A call site could become less desirable for inlining because of the size
   // growth from prior inlining into the callee. This method is used to lazily
   // update the desirability of a call site if it's decreasing. It is only
   // called on pop() or front(), not every time the desirability changes. When
   // the desirability of the front call site decreases, an updated one would be
   // pushed right back into the heap. For simplicity, those cases where
   // the desirability of a call site increases are ignored here.
   void adjust() {
     while (updateAndCheckDecreased(Heap.front())) {
       std::pop_heap(Heap.begin(), Heap.end(), isLess);
       std::push_heap(Heap.begin(), Heap.end(), isLess);
     }
   }

 public:
   PriorityInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params)
       : FAM(FAM), Params(Params) {
     isLess = [&](const CallBase *L, const CallBase *R) {
       return hasLowerPriority(L, R);
     };
   }

   size_t size() override { return Heap.size(); }

   void push(const T &Elt) override {
     CallBase *CB = Elt.first;
     const int InlineHistoryID = Elt.second;

     Heap.push_back(CB);
     Priorities[CB] = PriorityT(CB, FAM, Params);
     std::push_heap(Heap.begin(), Heap.end(), isLess);
     InlineHistoryMap[CB] = InlineHistoryID;
   }

   T pop() override {
     assert(size() > 0);
     adjust();

     CallBase *CB = Heap.front();
     T Result = std::make_pair(CB, InlineHistoryMap[CB]);
     InlineHistoryMap.erase(CB);
     std::pop_heap(Heap.begin(), Heap.end(), isLess);
     Heap.pop_back();
     return Result;
   }

   void erase_if(function_ref<bool(T)> Pred) override {
     auto PredWrapper = [=](CallBase *CB) -> bool {
       return Pred(std::make_pair(CB, 0));
     };
     llvm::erase_if(Heap, PredWrapper);
     std::make_heap(Heap.begin(), Heap.end(), isLess);
   }

 private:
   SmallVector<CallBase *, 16> Heap;
   std::function<bool(const CallBase *L, const CallBase *R)> isLess;
   DenseMap<CallBase *, int> InlineHistoryMap;
   DenseMap<const CallBase *, PriorityT> Priorities;
   FunctionAnalysisManager &FAM;
   const InlineParams &Params;
 };

 } // namespace

 std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
 llvm::getInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params) {
   switch (UseInlinePriority) {
   case InlinePriorityMode::Size:
     LLVM_DEBUG(dbgs() << "    Current used priority: Size priority ---- \n");
     return std::make_unique<PriorityInlineOrder<SizePriority>>(FAM, Params);

   case InlinePriorityMode::Cost:
     LLVM_DEBUG(dbgs() << "    Current used priority: Cost priority ---- \n");
     return std::make_unique<PriorityInlineOrder<CostPriority>>(FAM, Params);

   case InlinePriorityMode::CostBenefit:
     LLVM_DEBUG(
         dbgs() << "    Current used priority: cost-benefit priority ---- \n");
     return std::make_unique<PriorityInlineOrder<CostBenefitPriority>>(FAM, Params);
   case InlinePriorityMode::ML:
     LLVM_DEBUG(
         dbgs() << "    Current used priority: ML priority ---- \n");
     return std::make_unique<PriorityInlineOrder<MLPriority>>(FAM, Params);
   }
   return nullptr;
 }
	//===- InlineOrder.cpp - Inlining order abstraction -- C++ --------------===//
	//
	// 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
	//
	//===----------------------------------------------------------------------===//

	#include "llvm/Analysis/InlineOrder.h"
	#include "llvm/Analysis/AssumptionCache.h"
	#include "llvm/Analysis/BlockFrequencyInfo.h"
	#include "llvm/Analysis/GlobalsModRef.h"
	#include "llvm/Analysis/InlineAdvisor.h"
	#include "llvm/Analysis/InlineCost.h"
	#include "llvm/Analysis/OptimizationRemarkEmitter.h"
	#include "llvm/Analysis/ProfileSummaryInfo.h"
	#include "llvm/Analysis/TargetLibraryInfo.h"
	#include "llvm/Analysis/TargetTransformInfo.h"
	#include "llvm/Support/CommandLine.h"

	using namespace llvm;

	#define DEBUG_TYPE "inline-order"

	enum class InlinePriorityMode : int { Size, Cost, CostBenefit, ML };

	static cl::opt<InlinePriorityMode> UseInlinePriority(
	"inline-priority-mode", cl::init(InlinePriorityMode::Size), cl::Hidden,
	cl::desc("Choose the priority mode to use in module inline"),
	cl::values(clEnumValN(InlinePriorityMode::Size, "size",
	"Use callee size priority."),
	clEnumValN(InlinePriorityMode::Cost, "cost",
	"Use inline cost priority."),
	clEnumValN(InlinePriorityMode::CostBenefit, "cost-benefit",
	"Use cost-benefit ratio."),
	clEnumValN(InlinePriorityMode::ML, "ml",
	"Use ML.")));

	static cl::opt<int> ModuleInlinerTopPriorityThreshold(
	"moudle-inliner-top-priority-threshold", cl::Hidden, cl::init(0),
	cl::desc("The cost threshold for call sites that get inlined without the "
	"cost-benefit analysis"));

	namespace {

	llvm::InlineCost getInlineCostWrapper(CallBase &CB,
	FunctionAnalysisManager &FAM,
	const InlineParams &Params) {
	Function &Caller = *CB.getCaller();
	ProfileSummaryInfo *PSI =
	FAM.getResult<ModuleAnalysisManagerFunctionProxy>(Caller)
	.getCachedResult<ProfileSummaryAnalysis>(
	*CB.getParent()->getParent()->getParent());

	auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(Caller);
	auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
	return FAM.getResult<AssumptionAnalysis>(F);
	};
	auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
	return FAM.getResult<BlockFrequencyAnalysis>(F);
	};
	auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
	return FAM.getResult<TargetLibraryAnalysis>(F);
	};

	Function &Callee = *CB.getCalledFunction();
	auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
	bool RemarksEnabled =
	Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled(
	DEBUG_TYPE);
	return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI,
	GetBFI, PSI, RemarksEnabled ? &ORE : nullptr);
	}

	class SizePriority {
	public:
	SizePriority() = default;
	SizePriority(const CallBase *CB, FunctionAnalysisManager &,
	const InlineParams &) {
	Function *Callee = CB->getCalledFunction();
	Size = Callee->getInstructionCount();
	}

	static bool isMoreDesirable(const SizePriority &P1, const SizePriority &P2) {
	return P1.Size < P2.Size;
	}

	private:
	unsigned Size = UINT_MAX;
	};

	class CostPriority {
	public:
	CostPriority() = default;
	CostPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
	const InlineParams &Params) {
	auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params);
	if (IC.isVariable())
	Cost = IC.getCost();
	else
	Cost = IC.isNever() ? INT_MAX : INT_MIN;
	}

	static bool isMoreDesirable(const CostPriority &P1, const CostPriority &P2) {
	return P1.Cost < P2.Cost;
	}

	private:
	int Cost = INT_MAX;
	};

	class CostBenefitPriority {
	public:
	CostBenefitPriority() = default;
	CostBenefitPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
	const InlineParams &Params) {
	auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params);
	Cost = IC.getCost();
	StaticBonusApplied = IC.getStaticBonusApplied();
	CostBenefit = IC.getCostBenefit();
	}

	static bool isMoreDesirable(const CostBenefitPriority &P1,
	const CostBenefitPriority &P2) {
	// We prioritize call sites in the dictionary order of the following
	// priorities:
	//
	// 1. Those call sites that are expected to reduce the caller size when
	// inlined. Within them, we prioritize those call sites with bigger
	// reduction.
	//
	// 2. Those call sites that have gone through the cost-benefit analysis.
	// Currently, they are limited to hot call sites. Within them, we
	// prioritize those call sites with higher benefit-to-cost ratios.
	//
	// 3. Remaining call sites are prioritized according to their costs.

	// We add back StaticBonusApplied to determine whether we expect the caller
	// to shrink (even if we don't delete the callee).
	bool P1ReducesCallerSize =
	P1.Cost + P1.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
	bool P2ReducesCallerSize =
	P2.Cost + P2.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
	if (P1ReducesCallerSize \|\| P2ReducesCallerSize) {
	// If one reduces the caller size while the other doesn't, then return
	// true iff P1 reduces the caller size.
	if (P1ReducesCallerSize != P2ReducesCallerSize)
	return P1ReducesCallerSize;

	// If they both reduce the caller size, pick the one with the smaller
	// cost.
	return P1.Cost < P2.Cost;
	}

	bool P1HasCB = P1.CostBenefit.has_value();
	bool P2HasCB = P2.CostBenefit.has_value();
	if (P1HasCB \|\| P2HasCB) {
	// If one has undergone the cost-benefit analysis while the other hasn't,
	// then return true iff P1 has.
	if (P1HasCB != P2HasCB)
	return P1HasCB;

	// If they have undergone the cost-benefit analysis, then pick the one
	// with a higher benefit-to-cost ratio.
	APInt LHS = P1.CostBenefit->getBenefit() * P2.CostBenefit->getCost();
	APInt RHS = P2.CostBenefit->getBenefit() * P1.CostBenefit->getCost();
	return LHS.ugt(RHS);
	}

	// Remaining call sites are ordered according to their costs.
	return P1.Cost < P2.Cost;
	}

	private:
	int Cost = INT_MAX;
	int StaticBonusApplied = 0;
	std::optional<CostBenefitPair> CostBenefit;
	};

	class MLPriority {
	public:
	MLPriority() = default;
	MLPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
	const InlineParams &Params) {
	auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params);
	if (IC.isVariable())
	Cost = IC.getCost();
	else
	Cost = IC.isNever() ? INT_MAX : INT_MIN;
	}

	static bool isMoreDesirable(const MLPriority &P1, const MLPriority &P2) {
	return P1.Cost < P2.Cost;
	}

	private:
	int Cost = INT_MAX;
	};

	template <typename PriorityT>
	class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
	using T = std::pair<CallBase *, int>;

	bool hasLowerPriority(const CallBase L, const CallBase R) const {
	const auto I1 = Priorities.find(L);
	const auto I2 = Priorities.find(R);
	assert(I1 != Priorities.end() && I2 != Priorities.end());
	return PriorityT::isMoreDesirable(I2->second, I1->second);
	}

	bool updateAndCheckDecreased(const CallBase *CB) {
	auto It = Priorities.find(CB);
	const auto OldPriority = It->second;
	It->second = PriorityT(CB, FAM, Params);
	const auto NewPriority = It->second;
	return PriorityT::isMoreDesirable(OldPriority, NewPriority);
	}

	// A call site could become less desirable for inlining because of the size
	// growth from prior inlining into the callee. This method is used to lazily
	// update the desirability of a call site if it's decreasing. It is only
	// called on pop() or front(), not every time the desirability changes. When
	// the desirability of the front call site decreases, an updated one would be
	// pushed right back into the heap. For simplicity, those cases where
	// the desirability of a call site increases are ignored here.
	void adjust() {
	while (updateAndCheckDecreased(Heap.front())) {
	std::pop_heap(Heap.begin(), Heap.end(), isLess);
	std::push_heap(Heap.begin(), Heap.end(), isLess);
	}
	}

	public:
	PriorityInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params)
	: FAM(FAM), Params(Params) {
	isLess = [&](const CallBase L, const CallBase R) {
	return hasLowerPriority(L, R);
	};
	}

	size_t size() override { return Heap.size(); }

	void push(const T &Elt) override {
	CallBase *CB = Elt.first;
	const int InlineHistoryID = Elt.second;

	Heap.push_back(CB);
	Priorities[CB] = PriorityT(CB, FAM, Params);
	std::push_heap(Heap.begin(), Heap.end(), isLess);
	InlineHistoryMap[CB] = InlineHistoryID;
	}

	T pop() override {
	assert(size() > 0);
	adjust();

	CallBase *CB = Heap.front();
	T Result = std::make_pair(CB, InlineHistoryMap[CB]);
	InlineHistoryMap.erase(CB);
	std::pop_heap(Heap.begin(), Heap.end(), isLess);
	Heap.pop_back();
	return Result;
	}

	void erase_if(function_ref<bool(T)> Pred) override {
	auto PredWrapper = [=](CallBase *CB) -> bool {
	return Pred(std::make_pair(CB, 0));
	};
	llvm::erase_if(Heap, PredWrapper);
	std::make_heap(Heap.begin(), Heap.end(), isLess);
	}

	private:
	SmallVector<CallBase *, 16> Heap;
	std::function<bool(const CallBase L, const CallBase R)> isLess;
	DenseMap<CallBase *, int> InlineHistoryMap;
	DenseMap<const CallBase *, PriorityT> Priorities;
	FunctionAnalysisManager &FAM;
	const InlineParams &Params;
	};

	} // namespace

	std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
	llvm::getInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params) {
	switch (UseInlinePriority) {
	case InlinePriorityMode::Size:
	LLVM_DEBUG(dbgs() << " Current used priority: Size priority ---- \n");
	return std::make_unique<PriorityInlineOrder<SizePriority>>(FAM, Params);

	case InlinePriorityMode::Cost:
	LLVM_DEBUG(dbgs() << " Current used priority: Cost priority ---- \n");
	return std::make_unique<PriorityInlineOrder<CostPriority>>(FAM, Params);

	case InlinePriorityMode::CostBenefit:
	LLVM_DEBUG(
	dbgs() << " Current used priority: cost-benefit priority ---- \n");
	return std::make_unique<PriorityInlineOrder<CostBenefitPriority>>(FAM, Params);
	case InlinePriorityMode::ML:
	LLVM_DEBUG(
	dbgs() << " Current used priority: ML priority ---- \n");
	return std::make_unique<PriorityInlineOrder<MLPriority>>(FAM, Params);
	}
	return nullptr;
	}