Is maxstack really necessary?

[masonwheeler]

One of the trickier parts of creating IL metadata is figuring out the correct value for maxstack for a method, especially now that refemit is no longer available to do it for you if you want to be able to save the result. According to the CIL standard , III.1.7.4, maxstack must be provided and it must not be smaller than the actual maximum IL execution stack size of a method. The rationale given is:

By analyzing the CIL stream for any method, it is easy to determine how many items will be pushed on the CIL Evaluation stack. However, specifying that maximum number ahead of time helps a CIL-to-native-code compiler (especially a simple one that does only a single pass through the CIL stream) in allocating internal data structures that model the stack and/or
verification algorithm.

I'm sure that made sense in 2012, but a lot has changed since then. With every new .NET release, we're treated to blog posts explaining the advances that have been made both in the libraries and in the JIT compilers to improve performance. A conservative estimate of the maxstack value can be easily calculated by a single-pass analysis of an IL opcode stream (have a look at how refemit does it), so it seems a bit redundant for a highly sophisticated modern JIT to require as input information that it could trivially compute for itself.

While actually removing this from the metadata would be infeasible due to backwards compatibility, it seems reasonable to make it something optional that the JIT ignores, either unconditionally or if told to (perhaps if you specify a value of -1?) so as to ease the burden on compiler developers.

Any thoughts on this?

[dotnet-issue-labeler]

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

[CyrusNajmabadi]

THis seems reasonable to me. Though i imagine another suitable approach would be to have a helper that can compute this at compile time and just embed the appropriate stack depth so that the jit doesn't have to do this work. That would potentially be a best-of-both worlds approach (IMO at least) whereby the burden is eased on the metadata-emitter, and the cost is not paid at runtime by the JIT.

@jkotas any thoughts here?

[masonwheeler]

Though i imagine another suitable approach would be to have a helper that can compute this at compile time and just embed the appropriate stack depth so that the jit doesn't have to do this work.

If this were to happen in System.Reflection.Metadata.Ecma355, (the natural place to put such a helper in the Runtime libraries,) the ideal place to include such code would be under the hood of InstructionEncoder, essentially the same way as it's done in refemit. This could be accomplished without any source-breaking API changes by having InstructionEncoder compute this value as a running total, which was accessible as a new property int MaxStack {get;}. Document that its value should only be considered valid after you have finished encoding the entire method body, and you're good to go.

Putting it someplace external would violate DRY and significantly increase complexity by requiring consumers of the API to track the history of the opcodes they encode externally. It could conceivably be placed in a helper class somewhere to help people working on other metadata systems, but realistically speaking the benefit of doing so would be minimal because such an analyzer needs to work on some representation of IL opcodes and streams, and other metadata systems are unlikely to use the one provided by SRM. (Though perhaps there would be benefit in a helper class for analysis purposes when using SRM to read/edit an assembly. Either way, it should still be invoked under the hood of InstructionEncoder.)

[jkotas]

The highly sophisticated modern JITs are not the only components that consume IL. For example, there are number of interpreters out there. Some of them take advantage of maxstack to preallocate its internal data structures. Also, JIT inliner uses maxstack as one of the early outs to reject inlining candidates that are likely too complex.

You can use some sort of conversative estimate for maxstack. Number of components out there do that, with the caveat that it may behave poorly in some situations.

Adding a helper to System.Reflection.Metadata to compute maxstack for you sounds good to me. I would make it compute precise value so that the behavior is well defined, and we do not have to have a discussion about the trade-offs involved in computing the conservative estimate.

[ghost]

Tagging subscribers to this area: @dotnet/area-system-reflection-metadata
See info in area-owners.md if you want to be subscribed.

Issue Details

---

One of the trickier parts of creating IL metadata is figuring out the correct value for maxstack for a method, especially now that refemit is no longer available to do it for you if you want to be able to save the result. According to the CIL standard , III.1.7.4, maxstack must be provided and it must not be smaller than the actual maximum IL execution stack size of a method. The rationale given is:

By analyzing the CIL stream for any method, it is easy to determine how many items will be pushed on the CIL Evaluation stack. However, specifying that maximum number ahead of time helps a CIL-to-native-code compiler (especially a simple one that does only a single pass through the CIL stream) in allocating internal data structures that model the stack and/or
verification algorithm.

I'm sure that made sense in 2012, but a lot has changed since then. With every new .NET release, we're treated to blog posts explaining the advances that have been made both in the libraries and in the JIT compilers to improve performance. A conservative estimate of the maxstack value can be easily calculated by a single-pass analysis of an IL opcode stream (have a look at how refemit does it), so it seems a bit redundant for a highly sophisticated modern JIT to require as input information that it could trivially compute for itself.

While actually removing this from the metadata would be infeasible due to backwards compatibility, it seems reasonable to make it something optional that the JIT ignores, either unconditionally or if told to (perhaps if you specify a value of -1?) so as to ease the burden on compiler developers.

Any thoughts on this?

Author:	masonwheeler
Assignees:	-
Labels:	area-System.Reflection.Metadata, untriaged
Milestone:	-

[masonwheeler]

I would make it compute precise value so that the behavior is well defined, and we do not have to have a discussion about the trade-offs involved in computing the conservative estimate.

That would be nice if it can be done, particularly if it can be done efficiently. Does a general-case algorithm exist for computing the precise max stack requirement from an IL stream? I haven't looked deeply into this, but it intuitively feels like beating the conservative estimate provided by the refemit running-total algorithm is something that could be done in specific cases by a human observer, but not something that would be easy to do algorithmically for all cases.

[jkotas]

I believe that the algorithm to compute precise max stack can be linear with the size of IL stream. So the efficiency is just about the constant multiplier.

Note that System.Reflection.Metadata.Ecma335.InstructionEncoder is not used by Roslyn. Roslyn has its own encoder that fits better with how Roslyn generates code. The Roslyn emitter computes maxstack for free. I expect that most compilers will be like Roslyn and stay away from InstructionEncoder.

If we were to add the helper for InstructionEncoder to compute maxstack it would be useful to have concrete library that it can be validated on and measured on.

[masonwheeler]

If I might ask, what's the purpose of creating an API for compiler writers that you expect compiler writers will never actually use, and would in fact prefer to go to all the effort of rolling their own despite the fact that a prebuilt solution exists?

[jkotas]

This API would be for people who use InstructionEncoder today, e.g. people writing simple compilers that do not run into usability and efficiency problems of InstructionEncoder.

I agree with you that it is debatable to be adding APIs that only work well for trivial cases. The same can be said about InstructionEncoder. I do not know why we have added InstructionEncoder when Roslyn does not use it.

[ericstj]

I do not know why we have added InstructionEncoder when Roslyn does not use it.

Perhaps it did at one point? dotnet/corefx#5354
@tmat

[masonwheeler]

@jkotas So InstructionEncoder has usability and efficiency problems, to such a degree that a prominent team member essentially states flat-out "this API sucks, don't use it for serious work."

A metadata writer library needs an IL emitter. So as long as we're throwing ideas around, how would you fix it? Changes to the implementation? A new class and deprecate the old one? Move Roslyn's much better IL emitter into SRM.Ecma335?

[masonwheeler]

@ericstj I'm sorry, perhaps what did what at some point?

[ericstj]

I updated my comment. Perhaps Roslyn was using InstructionEncoder when @tmat originally added it.

[MichalStrehovsky]

InstructionEncoder fundamentally cannot compute the stack height because it doesn't know how many things to push/pop for calls/newobj and similar. It knows a call is getting generated, but the token is just a meaningless number. It's by design - S.R.Metadata builders don't interpret tokens because that runs into problems with recursion quickly (might need to know about a token that hasn't been emitted yet).

The expectation is that a S.R.Metadata user has a type system thing running next to S.R.Metadata that can answer these questions. An API addition to compute MaxStack in InstructionEncoder would need to bridge this gap somehow.

[masonwheeler]

@MichalStrehovsky You're right, that does tend to complicate things. Personally I'd prefer to resolve this with a system that requires all tokens to be declared, and their basic shape defined, before they can be used, but does not require a token's underlying data to be complete before it can be declared. But that's essentially the exact opposite of how SRM works.

So my idea won't work without some kind of callback setup for the calculation code to query the library consumer's "type system thing" for information, and that could balloon into a big, ugly mess of complexity very quickly.

Do you have any preferred alternatives for how to implement something like this?

[jkotas]

A metadata writer library needs an IL emitter.

I think that code emitters in serious compilers typically up being highly opinionated APIs to make them fit well with the rest of the compiler. It is hard to create a great non-opinionated code emitter API in isolation. Both System.Reflection.Emit.ILGenerator and System.Reflection.Metadata.Ecma335.InstructionEncoder have similar efficiency and usability issues for serious work. It does not mean that they are worthless. They are still useful if one just needs to emit something simple and not building a serious compiler.

If somebody came with .NET compiler construction framework (something like LLVM for .NET), it would make sense to have IL code emitter as part of it that fits well with the rest of the framework. I can believe that the code emitter like that would work well for serious work and nobody using that framework would think twice about using it.

[masonwheeler]

Well, I've never looked too closely at its efficiency, but honestly I don't see much in the way of usability problems with System.Reflection.Emit.ILGenerator. It's certainly significantly easier to work with than SRM! (Although admittedly some of that has to do with the larger architectural and abstraction-level differences between refemit and SRM.)

[MichalStrehovsky]

So my idea won't work without some kind of callback setup for the calculation code to query the library consumer's "type system thing" for information, and that could balloon into a big, ugly mess of complexity very quickly.

S.R.Metadata tends to do these callbacks through generics so this would probably be something along the lines of InstructionEncoder<TCallback> where TCallback : IStackInfoProvider, where IStackInfoProvider would provide a stack delta given a token. But this might be hard to do in a "streaming" fashion because of EH regions (that affect stack height, but get defined outside of InstructionEncoder).

If you're looking for inspiration on how to do this as a post pass in a precise fashion, this might be useful:

runtime/src/coreclr/tools/Common/TypeSystem/IL/ILStackHelper.cs

Line 25 in 57bfe47

public static int ComputeMaxStack(this MethodIL methodIL)

[tmat]

I think you could pass a delegate Func<EntityHandle, int> getMethodCallStackEffect as an optional parameter to AddMethodBody. The current impl already does a pass over the IL stream to fix up branches. Calculating maxstack could be included as well. The ControlFlowBuilder used there has all the exception regions as well.

[steveharter]

Closing as answered.