From a593f585711872802b39e735e86ad3585bb5b6ee Mon Sep 17 00:00:00 2001 From: Andy Ayers Date: Tue, 10 Nov 2020 19:45:06 -0800 Subject: [PATCH] JIT: preliminary version of profile-based inline policy (#44427) Add a new inline policy that can be used when a method has profile data. It uses the call site frequency to boost profitability. Size and per-call benefit are currently using the estimates done by the model policy. Not on by default. Set COMPlus_JitInlinePolicyProfile=1 to enable. Add testing to weekly experimental runs. --- .../common/templates/runtimes/run-test-job.yml | 1 + src/coreclr/src/jit/importer.cpp | 19 ++ src/coreclr/src/jit/inline.cpp | 3 +- src/coreclr/src/jit/inline.def | 4 +- src/coreclr/src/jit/inline.h | 9 +- src/coreclr/src/jit/inlinepolicy.cpp | 264 ++++++++++++++++++++- src/coreclr/src/jit/inlinepolicy.h | 31 +++ src/coreclr/src/jit/jitconfigvalues.h | 2 + src/tests/Common/testenvironment.proj | 2 + 9 files changed, 329 insertions(+), 6 deletions(-) diff --git a/eng/pipelines/common/templates/runtimes/run-test-job.yml b/eng/pipelines/common/templates/runtimes/run-test-job.yml index e469612..c3d4481 100644 --- a/eng/pipelines/common/templates/runtimes/run-test-job.yml +++ b/eng/pipelines/common/templates/runtimes/run-test-job.yml @@ -471,6 +471,7 @@ jobs: - jitehwritethru - jitobjectstackallocation - jitpgo + - jitpgo_inline ${{ if in(parameters.testGroup, 'ilasm') }}: scenarios: - ilasmroundtrip diff --git a/src/coreclr/src/jit/importer.cpp b/src/coreclr/src/jit/importer.cpp index 1ef8630..5d57941 100644 --- a/src/coreclr/src/jit/importer.cpp +++ b/src/coreclr/src/jit/importer.cpp @@ -18894,6 +18894,25 @@ void Compiler::impMakeDiscretionaryInlineObservations(InlineInfo* pInlineInfo, I inlineResult->NoteInt(InlineObservation::CALLSITE_FREQUENCY, static_cast(frequency)); inlineResult->NoteInt(InlineObservation::CALLSITE_WEIGHT, static_cast(weight)); + + // If the call site has profile data, report the relative frequency of the site. + // + if ((pInlineInfo != nullptr) && pInlineInfo->iciBlock->hasProfileWeight()) + { + double callSiteWeight = (double)pInlineInfo->iciBlock->bbWeight; + double entryWeight = (double)impInlineRoot()->fgFirstBB->bbWeight; + + assert(callSiteWeight >= 0); + assert(entryWeight >= 0); + + if (entryWeight != 0) + { + inlineResult->NoteBool(InlineObservation::CALLSITE_HAS_PROFILE, true); + + double frequency = callSiteWeight / entryWeight; + inlineResult->NoteDouble(InlineObservation::CALLSITE_PROFILE_FREQUENCY, frequency); + } + } } /***************************************************************************** diff --git a/src/coreclr/src/jit/inline.cpp b/src/coreclr/src/jit/inline.cpp index 050214e..a2eee7d 100644 --- a/src/coreclr/src/jit/inline.cpp +++ b/src/coreclr/src/jit/inline.cpp @@ -390,7 +390,8 @@ void InlineContext::Dump(unsigned indent) if (m_Parent == nullptr) { // Root method - printf("Inlines into %08X %s\n", calleeToken, calleeName); + InlinePolicy* policy = InlinePolicy::GetPolicy(compiler, true); + printf("Inlines into %08X [via %s] %s\n", calleeToken, policy->GetName(), calleeName); } else { diff --git a/src/coreclr/src/jit/inline.def b/src/coreclr/src/jit/inline.def index 6391802..3c3ef46 100644 --- a/src/coreclr/src/jit/inline.def +++ b/src/coreclr/src/jit/inline.def @@ -165,14 +165,16 @@ INLINE_OBSERVATION(RARE_GC_STRUCT, bool, "rarely called, has gc str INLINE_OBSERVATION(CONSTANT_ARG_FEEDS_TEST, bool, "constant argument feeds test", INFORMATION, CALLSITE) INLINE_OBSERVATION(DEPTH, int, "depth", INFORMATION, CALLSITE) INLINE_OBSERVATION(FREQUENCY, int, "rough call site frequency", INFORMATION, CALLSITE) +INLINE_OBSERVATION(HAS_PROFILE, bool, "profile data is available", INFORMATION, CALLSITE) INLINE_OBSERVATION(IN_LOOP, bool, "call site is in a loop", INFORMATION, CALLSITE) INLINE_OBSERVATION(IN_TRY_REGION, bool, "call site is in a try region", INFORMATION, CALLSITE) INLINE_OBSERVATION(IS_PROFITABLE_INLINE, bool, "profitable inline", INFORMATION, CALLSITE) INLINE_OBSERVATION(IS_SAME_THIS, bool, "same this as root caller", INFORMATION, CALLSITE) INLINE_OBSERVATION(IS_SIZE_DECREASING_INLINE, bool, "size decreasing inline", INFORMATION, CALLSITE) INLINE_OBSERVATION(LOG_REPLAY_ACCEPT, bool, "accepted by log replay", INFORMATION, CALLSITE) +INLINE_OBSERVATION(PROFILE_FREQUENCY, double, "frequency from profile data", INFORMATION, CALLSITE) INLINE_OBSERVATION(RANDOM_ACCEPT, bool, "random accept", INFORMATION, CALLSITE) -INLINE_OBSERVATION(WEIGHT, int, "call site frequency", INFORMATION, CALLSITE) +INLINE_OBSERVATION(WEIGHT, int, "frequency from block weight", INFORMATION, CALLSITE) // ------ Final Sentinel ------- diff --git a/src/coreclr/src/jit/inline.h b/src/coreclr/src/jit/inline.h index b2c414d..4918e6c 100644 --- a/src/coreclr/src/jit/inline.h +++ b/src/coreclr/src/jit/inline.h @@ -225,7 +225,8 @@ public: virtual void NoteSuccess() = 0; virtual void NoteBool(InlineObservation obs, bool value) = 0; virtual void NoteFatal(InlineObservation obs) = 0; - virtual void NoteInt(InlineObservation obs, int value) = 0; + virtual void NoteInt(InlineObservation obs, int value) = 0; + virtual void NoteDouble(InlineObservation obs, double value) = 0; // Optional observations. Most policies ignore these. virtual void NoteContext(InlineContext* context) @@ -396,6 +397,12 @@ public: m_Policy->NoteInt(obs, value); } + // Make an observation with a double value + void NoteDouble(InlineObservation obs, double value) + { + m_Policy->NoteDouble(obs, value); + } + #if defined(DEBUG) || defined(INLINE_DATA) // Record observation from an earlier failure. diff --git a/src/coreclr/src/jit/inlinepolicy.cpp b/src/coreclr/src/jit/inlinepolicy.cpp index 487fbe6..090283d 100644 --- a/src/coreclr/src/jit/inlinepolicy.cpp +++ b/src/coreclr/src/jit/inlinepolicy.cpp @@ -84,6 +84,16 @@ InlinePolicy* InlinePolicy::GetPolicy(Compiler* compiler, bool isPrejitRoot) return new (compiler, CMK_Inlining) ModelPolicy(compiler, isPrejitRoot); } + // Optionally install the ProfilePolicy, if the method has profile data. + // + bool enableProfilePolicy = JitConfig.JitInlinePolicyProfile() != 0; + bool hasProfileData = compiler->fgIsUsingProfileWeights(); + + if (enableProfilePolicy && hasProfileData) + { + return new (compiler, CMK_Inlining) ProfilePolicy(compiler, isPrejitRoot); + } + // Use the default policy by default return new (compiler, CMK_Inlining) DefaultPolicy(compiler, isPrejitRoot); } @@ -636,6 +646,20 @@ void DefaultPolicy::NoteInt(InlineObservation obs, int value) } //------------------------------------------------------------------------ +// NoteDouble: handle an observed double value +// +// Arguments: +// obs - the current obsevation +// value - the value being observed + +void DefaultPolicy::NoteDouble(InlineObservation obs, double value) +{ + // By default, ignore this observation. + // + assert(obs == InlineObservation::CALLSITE_PROFILE_FREQUENCY); +} + +//------------------------------------------------------------------------ // DetermineMultiplier: determine benefit multiplier for this inline // // Notes: uses the accumulated set of observations to compute a @@ -1149,6 +1173,7 @@ void RandomPolicy::DetermineProfitability(CORINFO_METHOD_INFO* methodInfo) // clang-format off DiscretionaryPolicy::DiscretionaryPolicy(Compiler* compiler, bool isPrejitRoot) : DefaultPolicy(compiler, isPrejitRoot) + , m_ProfileFrequency(0.0) , m_BlockCount(0) , m_Maxstack(0) , m_ArgCount(0) @@ -1189,6 +1214,7 @@ DiscretionaryPolicy::DiscretionaryPolicy(Compiler* compiler, bool isPrejitRoot) , m_CallSiteWeight(0) , m_ModelCodeSizeEstimate(0) , m_PerCallInstructionEstimate(0) + , m_HasProfile(false) , m_IsClassCtor(false) , m_IsSameThis(false) , m_CallerHasNewArray(false) @@ -1235,6 +1261,10 @@ void DiscretionaryPolicy::NoteBool(InlineObservation obs, bool value) // hotness for all candidates. So ignore. break; + case InlineObservation::CALLSITE_HAS_PROFILE: + m_HasProfile = value; + break; + default: DefaultPolicy::NoteBool(obs, value); break; @@ -1303,6 +1333,22 @@ void DiscretionaryPolicy::NoteInt(InlineObservation obs, int value) } //------------------------------------------------------------------------ +// NoteDouble: handle an observed double value +// +// Arguments: +// obs - the current obsevation +// value - the value being observed + +void DiscretionaryPolicy::NoteDouble(InlineObservation obs, double value) +{ + assert(obs == InlineObservation::CALLSITE_PROFILE_FREQUENCY); + assert(value >= 0.0); + assert(m_ProfileFrequency == 0.0); + + m_ProfileFrequency = value; +} + +//------------------------------------------------------------------------ // ComputeOpcodeBin: simple histogramming of opcodes based on presumably // similar codegen impact. // @@ -1571,10 +1617,17 @@ void DiscretionaryPolicy::ComputeOpcodeBin(OPCODE opcode) bool DiscretionaryPolicy::PropagateNeverToRuntime() const { // Propagate most failures, but don't propagate when the inline - // was viable but unprofitable. - bool propagate = (m_Observation != InlineObservation::CALLEE_NOT_PROFITABLE_INLINE); + // was viable but unprofitable, or does not return.. + // + switch (m_Observation) + { + case InlineObservation::CALLEE_NOT_PROFITABLE_INLINE: + case InlineObservation::CALLEE_DOES_NOT_RETURN: + return false; - return propagate; + default: + return true; + } } //------------------------------------------------------------------------ @@ -2187,6 +2240,211 @@ void ModelPolicy::DetermineProfitability(CORINFO_METHOD_INFO* methodInfo) } } +//------------------------------------------------------------------------/ +// ProfilePolicy: construct a new ProfilePolicy +// +// Arguments: +// compiler -- compiler instance doing the inlining (root compiler) +// isPrejitRoot -- true if this compiler is prejitting the root method + +ProfilePolicy::ProfilePolicy(Compiler* compiler, bool isPrejitRoot) : DiscretionaryPolicy(compiler, isPrejitRoot) +{ + // Empty +} + +//------------------------------------------------------------------------ +// NoteInt: handle an observed integer value +// +// Arguments: +// obs - the current obsevation +// value - the value being observed +// +// Notes: +// The ILSize threshold used here should be large enough that +// it does not generally influence inlining decisions -- it only +// helps to make them faster. +// +// The value used below is just a guess and needs refinement. + +void ProfilePolicy::NoteInt(InlineObservation obs, int value) +{ + // Let underlying policy do its thing. + DiscretionaryPolicy::NoteInt(obs, value); + + // Fail fast for inlinees that are too large to ever inline. + // + if (!m_IsForceInline && (obs == InlineObservation::CALLEE_IL_CODE_SIZE) && (value >= 1000)) + { + // Callee too big, not a candidate + SetNever(InlineObservation::CALLEE_TOO_MUCH_IL); + return; + } + + // Safeguard against overly deep inlines + if (obs == InlineObservation::CALLSITE_DEPTH) + { + unsigned depthLimit = m_RootCompiler->m_inlineStrategy->GetMaxInlineDepth(); + + if (m_CallsiteDepth > depthLimit) + { + SetFailure(InlineObservation::CALLSITE_IS_TOO_DEEP); + return; + } + } + + // This observation happens after we determine profitability + // so we need to special case it here. + // + if (obs == InlineObservation::CALLEE_NUMBER_OF_BASIC_BLOCKS) + { + // Fail if this is a throw helper. + // + assert(m_IsForceInlineKnown); + assert(m_IsNoReturnKnown); + assert(value > 0); + + if (!m_IsForceInline && m_IsNoReturn && (value == 1)) + { + SetNever(InlineObservation::CALLEE_DOES_NOT_RETURN); + return; + } + + // If we're mimicing the default policy because there's no PGO + // data for this call, also fail if thereare too many basic blocks. + // + if (!m_HasProfile && !m_IsForceInline && (value > MAX_BASIC_BLOCKS)) + { + SetNever(InlineObservation::CALLEE_TOO_MANY_BASIC_BLOCKS); + return; + } + } +} + +//------------------------------------------------------------------------ +// DetermineProfitability: determine if this inline is profitable +// +// Arguments: +// methodInfo -- method info for the callee +// +// Notes: +// There are currently two parameters that are ad-hoc: the +// "global importance" weight and the size/speed threshold. Ideally this +// policy would have just one tunable parameter, the threshold, +// which describes how willing we are to trade size for speed. + +void ProfilePolicy::DetermineProfitability(CORINFO_METHOD_INFO* methodInfo) +{ + // We expect to have profile data, otherwise we should not + // have used this policy. + // + if (!m_HasProfile) + { + // Todo: investigate these cases more carefully. + // + SetFailure(InlineObservation::CALLSITE_NOT_PROFITABLE_INLINE); + return; + } + + // Do some homework + MethodInfoObservations(methodInfo); + EstimateCodeSize(); + EstimatePerformanceImpact(); + + // Preliminary inline model. + // + // If code size is estimated to increase, look at + // the profitability model for guidance. + // + // If code size will decrease, just inline. + // + if (m_ModelCodeSizeEstimate <= 0) + { + // Inline will likely decrease code size + JITLOG_THIS(m_RootCompiler, (LL_INFO100000, "Inline profitable, will decrease code size by %g bytes\n", + (double)-m_ModelCodeSizeEstimate / SIZE_SCALE)); + + if (m_IsPrejitRoot) + { + SetCandidate(InlineObservation::CALLEE_IS_SIZE_DECREASING_INLINE); + } + else + { + SetCandidate(InlineObservation::CALLSITE_IS_SIZE_DECREASING_INLINE); + } + + return; + } + + JITDUMP("Have profile data for call site...\n"); + + // This is a (projected) size increasing inline, and we have profile + // data available at the call site. + // + // We estimate that this inline will increase code size. Only + // inline if the performance win is sufficiently large to + // justify bigger code. + + // First compute the number of instruction executions saved + // via inlining per call to the callee per byte of code size + // impact. + // + // The per call instruction estimate is negative if the inline + // will reduce instruction count. Flip the sign here to make + // positive be better and negative worse. + double perCallBenefit = -((double)m_PerCallInstructionEstimate / (double)m_ModelCodeSizeEstimate); + + // Multiply by the call frequency to scale the benefit by + // the local importance. + // + double localBenefit = perCallBenefit * m_ProfileFrequency; + + // Account for "global importance" + // + double globalImportance = 1.0; + double benefit = globalImportance * localBenefit; + + // Compare this to the threshold, and inline if greater. + // + // The threshold is interpretable as a speed/size tradeoff, + // roughly the number benefit units needed for one extra byte of code. + // to spend to get one unit of benefit. + // + // Default is 65/245 = 0.25 + // + double threshold = JitConfig.JitInlinePolicyProfileThreshold() / 256.0; + bool shouldInline = (benefit > threshold); + + JITLOG_THIS(m_RootCompiler, + (LL_INFO100000, "Inline %s profitable: benefit=%g (perCall=%g, local=%g, global=%g, size=%g)\n", + shouldInline ? "is" : "is not", benefit, perCallBenefit, localBenefit, globalImportance, + (double)m_PerCallInstructionEstimate / SIZE_SCALE, (double)m_ModelCodeSizeEstimate / SIZE_SCALE)); + + if (!shouldInline) + { + // Fail the inline + if (m_IsPrejitRoot) + { + SetNever(InlineObservation::CALLEE_NOT_PROFITABLE_INLINE); + } + else + { + SetFailure(InlineObservation::CALLSITE_NOT_PROFITABLE_INLINE); + } + } + else + { + // Update candidacy + if (m_IsPrejitRoot) + { + SetCandidate(InlineObservation::CALLEE_IS_PROFITABLE_INLINE); + } + else + { + SetCandidate(InlineObservation::CALLSITE_IS_PROFITABLE_INLINE); + } + } +} + #if defined(DEBUG) || defined(INLINE_DATA) //------------------------------------------------------------------------/ diff --git a/src/coreclr/src/jit/inlinepolicy.h b/src/coreclr/src/jit/inlinepolicy.h index 7bd6557..3e0d344 100644 --- a/src/coreclr/src/jit/inlinepolicy.h +++ b/src/coreclr/src/jit/inlinepolicy.h @@ -12,6 +12,7 @@ // DefaultPolicy - default inliner policy // DiscretionaryPolicy - default variant with uniform size policy // ModelPolicy - policy based on statistical modelling +// ProfilePolicy - policy based on statistical modelling and profile feedback // // These experimental policies are available only in // DEBUG or release+INLINE_DATA builds of the jit. @@ -116,6 +117,7 @@ public: void NoteSuccess() override; void NoteBool(InlineObservation obs, bool value) override; void NoteInt(InlineObservation obs, int value) override; + void NoteDouble(InlineObservation obs, double value) override; // Policy determinations void DetermineProfitability(CORINFO_METHOD_INFO* methodInfo) override; @@ -193,6 +195,7 @@ public: // Policy observations void NoteBool(InlineObservation obs, bool value) override; void NoteInt(InlineObservation obs, int value) override; + void NoteDouble(InlineObservation obs, double value) override; // Policy policies bool PropagateNeverToRuntime() const override; @@ -227,6 +230,7 @@ protected: MAX_ARGS = 6 }; + double m_ProfileFrequency; unsigned m_BlockCount; unsigned m_Maxstack; unsigned m_ArgCount; @@ -267,6 +271,7 @@ protected: unsigned m_CallSiteWeight; int m_ModelCodeSizeEstimate; int m_PerCallInstructionEstimate; + bool m_HasProfile; bool m_IsClassCtor; bool m_IsSameThis; bool m_CallerHasNewArray; @@ -306,6 +311,32 @@ public: #endif // defined(DEBUG) || defined(INLINE_DATA) }; +// ProfilePolicy is an experimental policy that uses the results +// of data modelling and profile feedback to make estimates. + +class ProfilePolicy : public DiscretionaryPolicy +{ +public: + // Construct a ProfilePolicy + ProfilePolicy(Compiler* compiler, bool isPrejitRoot); + + // Policy observations + void NoteInt(InlineObservation obs, int value) override; + + // Policy determinations + void DetermineProfitability(CORINFO_METHOD_INFO* methodInfo) override; + +#if defined(DEBUG) || defined(INLINE_DATA) + + // Miscellaneous + const char* GetName() const override + { + return "ProfilePolicy"; + } + +#endif // defined(DEBUG) || defined(INLINE_DATA) +}; + #if defined(DEBUG) || defined(INLINE_DATA) // RandomPolicy implements a policy that inlines at random. diff --git a/src/coreclr/src/jit/jitconfigvalues.h b/src/coreclr/src/jit/jitconfigvalues.h index 5d77d6a..5cec145 100644 --- a/src/coreclr/src/jit/jitconfigvalues.h +++ b/src/coreclr/src/jit/jitconfigvalues.h @@ -402,6 +402,8 @@ CONFIG_STRING(JitInlineReplayFile, W("JitInlineReplayFile")) #endif // defined(DEBUG) || defined(INLINE_DATA) CONFIG_INTEGER(JitInlinePolicyModel, W("JitInlinePolicyModel"), 0) +CONFIG_INTEGER(JitInlinePolicyProfile, W("JitInlinePolicyProfile"), 0) +CONFIG_INTEGER(JitInlinePolicyProfileThreshold, W("JitInlinePolicyProfileThreshold"), 40) CONFIG_INTEGER(JitObjectStackAllocation, W("JitObjectStackAllocation"), 0) CONFIG_INTEGER(JitEECallTimingInfo, W("JitEECallTimingInfo"), 0) diff --git a/src/tests/Common/testenvironment.proj b/src/tests/Common/testenvironment.proj index f10f076..98ca7ab 100644 --- a/src/tests/Common/testenvironment.proj +++ b/src/tests/Common/testenvironment.proj @@ -54,6 +54,7 @@ COMPlus_JitEnableGuardedDevirtualization; COMPlus_EnableEHWriteThru; COMPlus_JitObjectStackAllocation; + COMPlus_JitInlinePolicyProfile; RunningIlasmRoundTrip @@ -145,6 +146,7 @@ + -- 2.7.4