Consider adding a cache of well known tokens to the JIT

[tannergooding]

Today, the JIT uses a set of heuristics to determine whether or not a method is profitable to inline. However, due to tokens being unique per module and due to the cost associated with resolving tokens the JIT (when inlining) can't easily see when certain code patterns will result in constants or otherwise dead code elimination. This can hinder the ability for the JIT to correctly inline methods with things like Isa.IsSupported, if (typeof(T) == typeof(...)) checks, or even string.Length.

As such, I propose we create a cache (effectively a Dictionary<TokenId, MethodInfo> or similar, per module) of well known methods (i.e. certain NamedIntrinsics) so the inliner can correctly determine if the inlining is profitable.

This table could be built up during Tier 0 and would be available during Tier 1 so that the inliner can correctly see when a call is constant and do the appropriate dead code elimination and size adjustments.

[tannergooding]

CC. @AndyAyersMS, @EgorBo

I had brought this idea up a couple times on Discord and decided to log a formal issue. I think it will largely handle the issue around the most critical scenarios in a mostly pay for play manner

[tannergooding]

On a meta point, there has also been previous discussion around concepts like "jit hints" and this would allow such work to be prototyped since the helper method would be well-known during importation.

[EgorBo]

Example of such an heuristic: EgorBo@3810c21
The idea is to increase the benefit multiplier if we feed get_Length with a string literal:

Inline candidate has const arg that feeds string.Length (+ const test).  Multiplier increased to XX.

It was originally rejected due to "resolvetoken" call but can be re-considered once we implement that cache of tokens ^.

[AndyAyersMS]

It would be better, I suspect, to implement a cache like this on the runtime side of the jit interface, as the runtime is more aware of various complications (collectible assemblies and such), has means for managing caches that might need periodic trimming or cleaning, and is able to use locks and other synchronization mechanisms that wouldn't be appropriate in the jit.

If that's the case, then what we're talking about seems like a "lightweight" version of resolveToken that has limited resolution abilities, and keeps a cache with

• positive mappings (perhaps returning a limited set of kinds/properties instead of handles) for the tokens that map to the "well known" objects of interest
• negative mappings for other tokens (things that are not of particular interest)

Given the above, it would be interesting to sketch what the jit interface API might look like.

Note if the aim of this is to improve inlining, we'll often be unable to make strong immediate inferences with the information we get back. Suppose during the IL scan this new API lets the jit know a particular call returns true. Connecting that with potential "savings" from being able to partially import the method is not easy as we don't know how the return value influences future computation and don't understand the control flow even if we can tell that value influences a branch.

So instead what we'd need to do is simply note that the IL contains "known return value" calls that we suspect are conveying valuable bits of information, and then use those notes to boost the viability of the method as an inline candidate. Then we'd revisit the method at the next stage of the inlinee evaluation pipeline, where we'd import the method for real and build IR and optimize based on that and verify that good things indeed happened (or more likely, just assume based on the hints that good things would happen).

[tannergooding]

@AndyAyersMS, that makes sense to me.

I believe the most important information for the purpose of inlining is NamedIntrinsicId. There is a lot we could theoretically do with CORINFO_RESOLVED_TOKEN or CORINFO_CALL_INFO, but I think most of the immediately interesting optimizations are limited to the named intrinsics we have in the JIT. This also keeps the maximum size of such caches restricted and fairly small and gives us a good place to "register" a token, as we can simply do it as part of lookupNamedIntrinsic for those we are interested in.

I think, therefore, that the surface area for the JIT/EE interface might be relatively simplistic such as:

void RegisterWellKnownToken(const CORINFO_RESOLVED_TOKEN* pResolvedToken, NamedIntrinsicId intrinsicId);
bool TryResolveWellKnownToken(mdToken token, CORINFO_RESOLVED_TOKEN* pResolvedToken, NamedIntrinsicId* intrinsicId);

We would then flow the resolved token down into impImportCall and impIntrinsic. This would be passed into lookupNamedIntrinsic where interesting named intrinsics can use RegisterWellKnownToken to place themselves into the cache. To start with, this would be cases such as Isa.IsSupported for hardware intrinsics, Type.op_Equality for generic checks, and string.Length for constant strings. The importer, when it encounters a call would attempt to use TryResolveWellKnownToken. The call can be skipped if optimizations are not enabled and should quickly return if the token is not in the cache. If there was a named intrinsic in the cache, the inliner can then use the returned intrinsicId to improve its own heuristics.

Say, for example, that there is a if (typeof(...) == typeof(...)) check. If we are in a generic context and T is constrained to struct then there is a very high likelihood that this represents a constant check and the inline multiplier can be increased. Ideally the inliner can also adjust itself if it sees many of these Type.op_Equality calls.

Similar heuristics can happen for Isa.IsSupported calls as the lookupNamedIntrinsic will have converted them to NI_IsSupported_True or NI_IsSupported_False letting us know if they are "constant true" or "constant false" and therefore allowing the inline multipler to be increased.

Having the cache store and return the CORINFO_RESOLVED_TOKEN allows future expansion if appropriate.

[jkotas]

void RegisterWellKnownToken(const CORINFO_RESOLVED_TOKEN* pResolvedToken, NamedIntrinsicId intrinsicId);

Should the first argument be just CORINFO_METHOD_HANDLE ?

[jkotas]

We may want to look at this as bag of cached key/value pairs attached to CORINFO_METHOD_HANDLE:

bool GetCachedData(CORINFO_METHOD_HANDLE method, intptr_t key, intptr_t* pValue);
void SetCachedData(CORINFO_METHOD_HANDLE method, intptr_t key, intptr_t value);

The JIT can define as many keys as it needs and the JIT owns interpretation of the value for given key, e.g. it can be the intrinsic IDs or cached observations about inlinees. The VM side would be free to flush the cache at will, e.g. when it becomes too big or when unloading occurs.

[AndyAyersMS]

Should the first argument be just CORINFO_METHOD_HANDLE ?

There are merits to both token-based lookup and handle based cache lookup.

Tanner's proposal is aimed at providing a cheap form of token resolution for use by the very early stages of inline candidate evaluation, where we're just scanning the IL stream, so that we can recognize some calls as being of special interest (like the Isa.IsSupported calls that will always resolve to a constant) and encourage the inliner to take a deeper look.

A more general handle keyed cache could be use to amortize costs of more detailed later stages of analysis, eg how much of an inlinee actually ends up getting imported, given that some of the calls it makes resolve to known constants at jit time.

Longer term, it also could be used by an AOT jit querying into interprocedural analysis data, where the shape of the data will likely be dictated by an earlier analysis performed by the jit.

[tannergooding]

Should the first argument be just CORINFO_METHOD_HANDLE ?

It certainly could be and that would be more extensible overall. That being said, I was hoping to attack a more specific issue first and something which I think may be better suited to be an independent API from a "you can cache any data you want" feature.

Namely, metadata tokens are unique per module and are somewhat "expensive" to resolve so we don't want to do so when doing an "is it profitable to inline this" check. This is often fine because most calls aren't "interesting" and won't have significant impact on inlining.
However, we also have a number of well-known methods which are more often than not a NamedIntrinsic and so we could maintain a small limited cache of these well-known tokens per module to assist in known problematic inlining scenarios used in perf critical/sensitive code.

If tracked on the VM side, this would effectively require a lazily allocated dictionary/map of metadata tokens to resolved token and NamedIntrinsic identifier. For a module that does not use any of these "well-known" intrinsics, there would be no additional allocations/overhead and for a module that does use them, it would be limited by the number of intrinsics we want to recognize. The most interesting ones being those that play into constant folding such as Isa.IsSupported, Type.op_Equality, string.Length, IsReferenceOrContainsReferences, and a couple others. You could imagine a similar "trivial" cache for well-known types such as string and the other primitive types (int32, char, potentially Vector4, etc).

Unlike a general-purpose "cache any information you want API", this API is known to be small and bounded and so there wouldn't need to be a huge concern around flushing it, since the overhead will never be more than a handful of entries per module and most modules will likely be empty or only contain a couple entries.

[jkotas]

There are merits to both token-based lookup and handle based cache lookup.

The expensive part of CORINFO_RESOLVED_TOKEN is dealing with the context, creating method instantiations, etc. The context-free token->HANDLE lookup is cheap if the token has been resolved already. It is basically just an lookup in an array using RID part of the token. We can streamline and aggresively inline this path to make it very fast if necessary.

If you would like to have a raw API that just can attach information for token, the API should explicitly take just CORINFO_MODULE_HANDLE and mdToken instead of the whole CORINFO_RESOLVED_TOKEN to make it clear that it does not take the context into account.

NamedIntrinsic and so we could maintain a small limited cache of these well-known tokens per module

If you do not find the token in cache, how are you going to tell whether you have not seen this token yet vs. you have seen the token and it is not a well-known method?

[tannergooding]

If you do not find the token in cache, how are you going to tell whether you have not seen this token yet vs. you have seen the token and it is not a well-known method?

The intent was that lookupNamedIntrinsic would pass in the CORINFO_RESOLVED_TOKEN and the intrinsic ID. The CORINFO_RESOLVED_TOKEN provides the Module, mdToken, and token kind and so the token/intrinsic ID would be added to the cache in the Module type. This would therefore not involve caching every token, but only a limited subset of intrinsic IDs that are explicitly "registered" to the cache when resolved..

In tier 0, it is likely there would likely be no entries in this cache and such entries wouldn't be used due to lack of inlining or other optimizations happening. However, methods that are rejitted to tier 1 would have had these self-same tokens already cached (from the tier 0 pass) if they were intrinsic IDs.

The inliner has to do a basic pass over the opcodes in a method it is determining inline profitability for and so it has the current Module, mdToken, and token kind. It can therefore construct the "input" CORINFO_RESOLVED_TOKEN and pass that into the cache. If an entry in the cache exists, it would return the cached RESOLVED_TOKEN and NamedIntrinsic and the inliner can do further heuristics as appropriate. If an entry does not exist in the cache, it would return NI_Illegal and the inliner would assume this is not a well known token and would continue as it does today. In the common "success" case, this will be NI_IsSupported_True, NI_IsSupported_False, or potentially the intrinsic ID for string.Length or Type.op_Equality.

The input does not strictly need to be a CORINFO_RESOLVED_TOKEN, this was simply a suggestion given that this contains roughly the information that is used to get eeCallInfo and ultimately the NamedIntrinsic in the normal importer scenario (where CEE_CALL is decoded).

[jkotas]

The intent was that lookupNamedIntrinsic would pass in the CORINFO_RESOLVED_TOKEN and the intrinsic ID. The CORINFO_RESOLVED_TOKEN provides the Module, mdToken, and token kind and so the token/intrinsic ID would be added to the cache in the Module type. This would therefore not involve caching every token, but only a limited subset of intrinsic IDs that are explicitly "registered" to the cache when resolved..

I am sorry but I do not see how this can work. I think you are saying that you can get from Module, mdToken to NamedIntrinsic id using a small cache and without doing expensive operation like resolving the token to HANDLE. Could you please walk through step-by-stepn on how it is going to work?

BTW: We have done experiments on catching resolveToken results in the past, but we were not able to come up with something that is a clear improvement. The problem is that resolveToken has a very long tail of tokens that are resolved just once or a few times that ends up killing the cache benefits.

[tannergooding]

Could you please walk through step-by-stepn on how it is going to work?

My understanding is that metadata tokens are effectively unique 32-bit unsigned integers per "module" (it is scoped to a specific "metadata binary"). This means that in the context of a single Module, the 4-byte token that follows CALL is unique to the module and any two methods in that module that have call 0x######## will be calling the same method. During normal importation this token is resolved by using the it as a lookup in the relevant metadata tables. For call this token will represent a methodref, methoddef, or methodspec entry.

This means that once something in the module has already resolved a call token to a well known NamedIntrinsic, you should effectively be able to use the same token ID in the same module to quickly get the same NamedIntrinsic without having to do the more in depth resolution. In pseudo-code, you would effectively have:

class Module
{
    private Dictionary<uint, NamedIntrinsic> _cachedIntrinsics;

    public static void RegisterWellKnownIntrinsic(uint token, NamedIntrinsic intrinsic) {
        if (_cachedIntrinsics is null) {
            _cachedIntrinsics = new Dictionary<uint, NamedIntrinsic>();
        }
        _cachedIntrinsics[token] = intrinsic;
    }

    public static bool TryGetWellKnownIntrinsic(uint token, out NamedIntrinsic intrinsic)
    {
        intrinsic = NI_Illegal;
        return (_cachedIntrinsic is not null) && _cachedIntrinsic.TryGetValue(token, out intrinsic);
    }
}

So, during tier 0 when an "interesting" named intrinsic is found, lookupNamedIntrinsic would call a JIT/EE interface method and say "for this module, register this token ID to be this named intrinsic", this is simple a map<mdToken, NamedIntrinsic> in the VM Module type (or similar).

During tier 1 when inlining is happening, the inliner would use a sibling JIT/EE interface method to say "is this token ID in this module a well known named intrinsic", that method effectively returns true with the corresponding NamedIntrinsic or false with NI_Illegal.

[jkotas]

This means that once something in the module has already resolved a call token to a well known NamedIntrinsic, you should effectively be able to use the same token ID in the same module to quickly get the same NamedIntrinsic without having to do the more in depth resolution.

Right, once something in the module resolves the token, it is also possible to get raw CORINFO_METHOD_HANDLE very efficiently using existing runtime caches. (As I have said, it is just a simple array indexing.)

So, during tier 0 when an "interesting" named intrinsic is found, lookupNamedIntrinsic would call a JIT/EE interface method and say "for this module, register this token ID to be this named intrinsic",

I do not think we would want to be spending time doing this during tier 0.

use a sibling JIT/EE interface method to say "is this token ID in this module a well known named intrinsic", that method effectively returns true with the corresponding NamedIntrinsic or false with NI_Illegal.

It is not guaranteed that the cache for given token has been populated. The token can be on path that has not been executed yet; or the cache could have been flushed in the meantime. So this check would be returning false negatives. I do not think we would be ok with unpredictable performance that this would introduce.

[tannergooding]

Right, once something in the module resolves the token, it is also possible to get raw CORINFO_METHOD_HANDLE very efficiently using existing runtime caches. (As I have said, it is just a simple array indexing.)

I wasn't aware we had this. I think the downside is that it requires an additional resolution on the handle to get the corresponding NamedIntrinsic so you know if there is anything interesting that can be done. This could be limited to just methods marked Intrinsic which might make it more "pay for play".

I do not think we would want to be spending time doing this during tier 0.

We are already resolving these tokens in tier 0, particularly for HWIntrinsics as it is a strict requirement for them to be handled by the JIT. There are some that aren't resolved, but I think those are likely less interesting.

The token can be on path that has not been executed yet; or the cache could have been flushed in the meantime.

My hope is that that populating the cache is largely handled by tiered jitting. Unless a user is utilizing this code in a method marked AggressiveOptimization it shouldn't be a concern.
I would likewise hope that this is a cache that would not need to be flushed. Even if we consider every IsSupported ISA, you are looking at ~50 entries in a module tops. Most modules won't be using hardware intrinsics and so they won't have any entries and won't need flushing. For those that are using hardware intrinsics, they are likely limited to a small subset of the overall number we expose.

For modules that are using generic specialization (e.g. typeof(T) == typeof(...)) or constant strings (string.Length) there may be a couple more entries that are worth caching, but the vast majority of the checks don't play into constant folding and so aren't interesting.

I do not think we would be ok with unpredictable performance that this would introduce.

The same is true for any cache like setup we have that allows that cache to be flushed. I think it comes down to us saying saying we do or don't care that there are cases with Isa.IsSupported or typeof(T) == typeof(...) that can't be inlined today because they don't reach bump the inlining profability margin enough. In order to bump it, we will have to resolve these tokens one way or another.

My proposal is to do this in a limited scenario that allows us to keep small, pay for play caches of well known tokens.

[jkotas]

his could be limited to just methods marked Intrinsic which might make it more "pay for play".

To find out whether the method is an Intrinsic, you have to get its CORINFO_METHOD_HANDLE first. The intrinsic bit is cached on CORINFO_METHOD_HANDLE.

I do not think we would be ok with unpredictable performance that this would introduce.

The same is true for any cache like setup we have that allows that cache to be flushed

I disagree. A real cache that handles cache misses properly would be fully determistic.

[AndyAyersMS]

Seems like we could experiment here easily enough.

We can have the inlinee IL scan resolve all call tokens when we're at Tier1, and see how much JIT throughput that costs us. The hypothesis here is that these resolutions will be quick as all the necessary loading and instantiation will have happened earlier, so the additional costs won't be that high.

A fair number of methods bypass Tier0 today, so it may be something more nuanced is needed...

[tannergooding]

To find out whether the method is an Intrinsic, you have to get its CORINFO_METHOD_HANDLE first. The intrinsic bit is cached on CORINFO_METHOD_HANDLE.

Right, just the first time. After you have resolved that once for a module, then simply the token is needed to map back to a NamedIntrinsic.

I disagree. A real cache that handles cache misses properly would be fully determistic.

My understanding is that we couldn't use proper cache here. The issue being that token resolution can be expensive and we don't want to be doing that, even with a cache, for every token when determining inlining profitability for a given method.
This is why we don't do it today and why changes like @EgorBo's change for caching string.Length were rejected previously to my understanding: EgorBo@3810c21.
As I understood it, we likewise don't want to be doing it because the majority of methods are not interesting to the inliner, there are very few methods that can actually be impactful here and those that are will be NamedIntrinsic.

So I think I'm not connecting something here and so I'm failing to see how some "real cache" that handles cache misses by fully resolving a token will save cost here.
Is getting just the CORINFO_METHOD_HANDLE somehow cheaper than a full impResolveToken, even for a token that had never been resolved before?
As in, we can get just the CORINFO_METHOD_HANDLE and do something like check "is this a JIT intrinsic" and then do a lookupIntrinsicId from there to make this more pay for play?

[jkotas]

Is getting just the CORINFO_METHOD_HANDLE somehow cheaper than a full impResolveToken, even for a token that had never been resolved before?

Right, resolving the token for the first time is expensive.

The solutions you have in mind seem to have non-predictable characteristics. We would see number of cases where the inlining behavior depends on what methods were JITed before and which tokens happened to be left in the cache as side-effect. I do not consider such solution to be a viable option.

[tannergooding]

Right, resolving the token for the first time is expensive.
The solutions you have in mind seem to have non-predictable characteristics. We would see number of cases where the inlining behavior depends on what methods were JITed before and which tokens happened to be left in the cache as side-effect. I do not consider such solution to be a viable option.

Right, I was just trying to propose something to workaround needing to resolve the tokens in the inline profitability phase, because I have been told and seen many times that doing this in the inliner was effectively a non-starter due to how it impacts JIT throughput.

If we believe we can do this without it negatively impacting throughput or that the negative impact is justified for Tier 1 methods, then that is all the better and would also allow broader heuristics to occur (user defined properties that simply return a static readonly field could also be correctly handled as an example).

However, as Andy mentioned there are a fair number of methods that bypass Tier0 today. It would be nice if these could also be handled, either by ensuring we do the same resolutions under AggressiveOptimization or by treating AggressiveOptimization more like a Tier 0.5, where it is better than Tier 0 but where additional optimizations could still be had by rejitting again after the normal 30 invocations (which would cover cases like improved inlining and static constructor calls).

[tannergooding]

I did a very minimal prototype here: https://github.com/tannergooding/runtime/tree/resolve-tokens-inline. This prototype effectively just updates fgFindJumpTargets to resolve call tokens for CEE_CONSTRAINED, CEE_CALL, and CEE_CALLVIRT if makeInlineObservations && isTier1.

I then profiled (using AMD uProf) benchmarks.run.windows.x64.checked.mch under SPMI using the baseline and my prototype with --sequential -build_type Release. The resulting flamegraphs look roughly like the following (baseline image given, there is no visible difference when comparing to the prototype image):

In the scheme of things, MyICJI::resolveToken takes ~0.04% of the retired instructions in either scenario, even when disabling tiering and compiling everything straight to tier 1 (this includes token resolution for normal block importation) and fgFindJumpTargets takes ~0.63% of the retired instructions. There is an increase in samples and retired branch instructions between the baseline and prototype, but not enough to move the actual percentage markers as other phases like Morph and LinearScan take far more time.

I think the most "costly" aspect of resolving tokens for improving inlining heuristics is likely going to be downstream effects if it causes something to inline that wouldn't have been inlined without the change.

[tannergooding]

Andy pointed out on Discord I'll need to not run SPMI like originally suggested but a live benchmark instead.

Will report those results when done.

[tannergooding]

After discussing with @AndyAyersMS something that would work correctly (since SPMI caches tokens), I ended up testing csc compiling a simple HelloWorld program (csc.dll Program.cs /r:System.Runtime.dll /r:System.Console.dll /r:System.Private.Corelib.dll) with COMPlus_ReadyToRun=0 and COMPlus_TieredCompilation=0

This results in the following flame graph:

Most of the time is still spent in the backend, but the numbers are actually more measurable for the impact now:

• Compiler::fgFindJumpTarget goes from 0.48% to 0.63% of instructions retired (28.5m to 39.25m)
• CEEInfo::resolveToken goes from 0.32% to 0.34% of instructions retired (19m to 21m)
• CEEInfo::getCallInfo goes from 0.36% to 0.32% of instructions retired (21.25m to 19.75m)

[AndyAyersMS]

So the data seems to agree that with TC enabled there is minimal extra cost to trying to resolve inlinee tokens early during Tier1, as most tokens we run across at Tier1 have already been resolved and re-resolving is fairly cheap.

Still remains to be seen how to best realize a benefit from this extra information.

I suspect recognizing the constant valued methods will give a small improvement but more will be needed. I don't think it is feasible to build a flow graph model during the IL scan, so I'd still tempted to just add enough observational hints to encourage the jit to proceed with inlining and then possibly implement a backout scheme if it turns out the cost of these inlinees that we expect to simplify is too high.

While it's tempting to say that any use of HW intrinsics merits much more aggressive inlining, we still have to have some kinds of limits in place.

[tannergooding]

While it's tempting to say that any use of HW intrinsics merits much more aggressive inlining, we still have to have some kinds of limits in place.

Definitely. I think the "simplest" heuristics are likely based on some basic counts such as:

• How many calls are intrinsic (Named or Otherwise)
• How many calls are hwintrinsic and therefore are not calls at all, but are effectively "simple ops"
• How many calls are CSE or constant folding candidates (such as Math calls)
• How many calls are "constants" like Isa.IsSupported
• How many calls are potential constants, like string.Length or Type.op_Equality checks

There are definitely cases where a user could write checks in a fashion to make us think its a profitable method with many dead code paths when it actually isn't, but I expect those will be rare, especially in methods marked AggressiveInlining.

• The latter is a particular concern, because there are cases like Vector<T>.op_Divide which are marked AggressiveInlining today, but which have just enough typeof(T) == typeof(...) checks that the JIT gives up 😄

[tannergooding]

@AndyAyersMS, do you think a PR with the minimal prototype I gave would be appropriate?

That would allow iterative changes like the one @EgorBo tried with string.Length in EgorBo@3810c21.
As well as additional prototyping or considerations in the area.

It could be placed behind a DOTNET_* (COMPlus_*) switch if there was any remaining concern.

[AndyAyersMS]

@AndyAyersMS, do you think a PR with the minimal prototype I gave would be appropriate?

Yes.

[tannergooding]

#50675 is merged. This allows us to resolve tokens for tier1 and prejit inline observations.

This provides minimal improved support for IsSupported checks and should unblock changes like EgorBo/runtime-1@3810c21 as well as recognizing things like Type.op_Equality or other checks for improved heuristics.