Proposal: IL optimization step

[benaadams]

The jit can only apply so many optimizations as it is time constrained at runtime.

AOT/NGen which has more time ends up with asm but loses some optimizations the jit can do at runtime as it needs to be conservative as to cpu architecture; static readonly to consts etc

The compile to il compilers (C#/VB.NET/etc); which aren't as time constrained but have a lot of optimizations considered out of scope.

Do we need a 3rd compiler between roslyn and jit that optimizes the il as part of the regular compile or a "publish" compile?

This could be a collaboration between the jit and roslyn teams?

I'm sure there are lots of low hanging fruit between the two; that the jit would like to do but are too expensive.

There is also the whole program optimization or linker + tree shaking which is also a component in this picture. (e.g. Mono/Xamarin linker). Likely also partial linking (e.g. nugets/non-platform runtime libs)

From #15644 (comment)

/cc @migueldeicaza @gafter @jkotas @AndyAyersMS

[HaloFour]

Does something like rewriting LINQ as loops fit into a process like this?

[alrz]

Speaking of optimziations,

int square(int num) {
  int a = 0;
  for (int x = 0; x < num; x+=2) {
    if (x % 2) {
      a += x;
    }
  }
  return a;
}

gcc changes the above function to return zero. 😄

[iam3yal]

And when we're at it! maybe constexpr can be taken into account! when and if it will ever get implemented. 😄

I don't know but maybe this is the right phase for handling constexpr just a thought.

[fanoI]

I think IL rewrite and constexpr are two separate things.

[iam3yal]

@fanoI They are two different things but what lead me to write this is really this part:

a "publish" compile?

Maybe during debug compilation the compiler won't evaluate functions as constexpr to reduce compilation time and then when you do publish or release it evaluate it at compile-time.

Just because they are two different things doesn't mean it's not the right phase to handle it.

[AndyAyersMS]

Part of the challenge in building an IL-IL optimizer is that in general the scope of optimizations is limited to a method or perhaps a single assembly. One can do some cool things at this scope but quite often the code one would like to optimize is scattered across many methods and many assemblies.

To broaden the scope, you can gather all the relevant assemblies together sometime well before execution and optimize them all together. But by doing this you inevitably build in strong dependence on the exact versions of the assemblies involved, and so the resulting set of optimized IL assemblies must now be deployed and versioned and serviced together. For some app models this is a natural fit; for others it is not.

Engineering challenges abound. @mikedn touched on some of them over in #15644, but there are many more. Just to touch on a few:

• The optimizer may not have enough context to build a coherent call graph, which can severely limit interprocedural fact propagation.
• For a given method the optimizer typically can't know all callers. To take advantage of caller-specific information the optimizer must clone or inline the callee. This in turn can cause significant code growth. Linking or tree-shaking can counteract this but typically needs some extra information to help limit the viral impact of reflection and/or interop.
• Determining which generic instantiations will be required at runtime is generally intractable
• The number of possible generic instantiations can be huge (in fact, unbounded). The optimizer must be designed to carefully balance between the added precision that comes from knowing instantiated types and the need to describe them all concisely.
• Instantiated generics cannot be described directly in IL, so if the optimizer instantiates generics to further optimize them then there needs to be some extra mechanism in the output IL to represent them, and downstream components must be updated to recognize them.
• The optimizer must anticipate the generic sharing strategy (if any) employed by the runtime, and or implement its own sharing. Shared generic instantiation(s) also cannot be described directly by IL.
• Runtime features like generic virtual methods, covariance and contravariance, reflection, reflection emit, and assembly loading complicate and limit the applicability of many interprocedural analyses.
• It's not always clear what "optimal" IL looks like. One must anticipate the capabilities and limitations of the downstream code generator.

I'm not saying that building an IL-IL optimizer is a bad idea, mind you -- but building one that is broadly applicable is a major undertaking.

[iam3yal]

@AndyAyersMS

To broaden the scope, you can gather all the relevant assemblies together sometime well before execution and optimize them all together. But by doing this you inevitably build in strong dependence on the exact versions of the assemblies involved, and so the resulting set of optimized IL assemblies must now be deployed and versioned and serviced together. For some app models this is a natural fit; for others it is not.

In C++ we face the exact same problem, don't we? static linking vs dynamic linking? there's trade-offs and yet many people choose to have static linking for their applications.

All this can be part of a compiler flag, I guess it needs to be an opt-in feature.

[mikedn]

In C++ we face the exact same problem, don't we? static linking vs dynamic linking? there's trade-offs and yet many people choose to have static linking for their applications.

What problem? C++ has headers and many C++ libraries are header only, starting with the C++ standard library (with a few exceptions). Besides, many used static linking for convenience, not for performance reasons. And static linking is certainly not the norm, for example you can find many games where the code is spread across many dlls.

All this can be part of a compiler flag, I guess it needs to be an opt-in feature.

Such a feature is being worked on. It's called corert.

[iam3yal]

@mikedn

What problem? C++ has headers and many C++ libraries are header only, starting with the C++ standard library (with a few exceptions). Besides, many used static linking for convenience, not for performance reasons. And static linking is certainly not the norm, for example you can find many games where the code is spread across many dlls.

I think you missed my point... my point being is people that do choose static linking face the following problems which he mentions in his post:

1. strong dependence on the exact versions of the assemblies involved

2. deployed and versioned and serviced together

It certainly isn't the norm for games but for many other applications static linking is fairly common.

I wasn't speaking about performance at all and it wasn't my intention to imply that the analogy has anything to do with the discussed feature itself but merely to point out that in the C++ world some people would accept these trade-offs and if people do that out of convenience then they would surely do it if it can increase performance especially in the .NET world so they might pay the price for bundling everything together but they will get optimized code which might worth it for them.

Such a feature is being worked on. It's called corert.

As far as I understand CoreRT is mostly designed for AOT scenarios and the emitted code isn't really IL, this isn't part of Roslyn and there's no compiler flag so how is it related? or as you said being worked on? maybe I'm missing something.

[mikedn]

I think you missed my point...

but merely to point out that in the C++ world some people would accept these trade-offs and if people do that out of convenience

Could be. It's somewhat unavoidable when apples and oranges comparisons are used. The C++ world is rather different from the .NET world and attempts to make decisions in one world based on what happens in the other may very well result in failure.

then they would surely do it if it can increase performance especially in the .NET world so they might pay the price for bundling everything together but they will get optimized code which might worth it for them

Why do you think that bundling everything together would increase performance?

Do you even know that you have all the code after bundling? No, there's always Assembly.Load & friends.

Can you transform a virtual call into a direct call because you can see that no class has overridden the called method? No, you can't because someone may create a class at runtime and override that method.

Can you look at all the List<T> code, conclude that count <= array.Length is always true and eliminate a range check? No, you can't because someone might use reflection to set the count field and break the invariant.

As far as I understand CoreRT is mostly designed for AOT scenarios and the emitted code isn't really IL, this isn't part of Roslyn and there's no compiler flag so how is it related? or as you said being worked on? maybe I'm missing something.

Well, do you want better compiler optimizations? Are you willing to merge all the code into a single binary and give up runtime code loading? Are you willing to give up runtime code generation? Are you willing to give up full reflection functionality? Then it sounds to me that CoreRT is exactly what you're looking for.

Do want it to emit IL? Why would you want that? I thought you wanted performance. Do you want it to be part of Roslyn as a compiler flag? Again, I thought you wanted performance.

The problem with this proposal is that it is extremely nebulous. Most people just want better performance and don't care how they get it. Some propose that we might get better performance by doing certain things but nobody knows exactly what and how much performance we can get by doing that.

And then we have the Roslyn team who had to cut a lot of stuff from C# 7 to deliver it. And the JIT team who too has a lot of work to do. And the CoreRT teams who for whatever reasons moves rather slowly. And the proposition is to embark into this new nebulous project that overlaps existing projects and delivers unknowns. Hmm...

[iam3yal]

@mikedn

Could be. It's somewhat unavoidable when apples and oranges comparisons are used. The C++ world is rather different from the .NET world and attempts to make decisions in one world based on what happens in the other may very well result in failure.

Okay, first of all I didn't just compare two worlds I made an analogy between two worlds and I merely pointed out that people choose one thing over the other regardless to the trade-offs in one world so they might do the same in a different world where the impact might be greater...

Why do you think that bundling everything together would increase performance?

I never said it will increase performance! I said that if it can increase performance then people will use it just for this fact alone and will accept the trade-offs he pointed out in his post.

I'm not an expert on the subject so I'm not going to pretend like my words are made of steel but based on what @AndyAyersMS wrote it seems like bundling assembly can eliminate some challenges.

By everything I only refer to the assemblies you own not 3rd-party ones.

Do you even know that you have all the code after bundling? No, there's always Assembly.Load & friends.

No, I don't know.

Well, do you want better compiler optimizations? Are you willing to merge all the code into a single binary and give up runtime code loading? Are you willing to give up runtime code generation? Are you willing to give up full reflection functionality?

ATM I don't know what would be the trade-offs, there's no proposal about it or design work that delve into limitations, so how did you decide what would be the limitations for such a feature?

Then it sounds to me that CoreRT is exactly what you're looking for.

Maybe... but I don't think so.

Do want it to emit IL? Why would you want that? I thought you wanted performance. Do you want it to be part of Roslyn as a compiler flag? Again, I thought you wanted performance.

Just because I want to optimize existing IL for performance to reduce run-time overheads it means that now I want to compile it to native code?

The problem with this proposal is that it is extremely nebulous. Most people just want better performance and don't care how they get it. Some propose that we might get better performance by doing certain things but nobody knows exactly what and how much performance we can get by doing that.

I agree but how would you get to something without discussing it first? don't you think we need to have an open discussion about it? and what we really want to get out of it?

This isn't really a proposal, this is the reason it was marked as Discussion.

And then we have the Roslyn team who had to cut a lot of stuff from C# 7 to deliver it. And the JIT team who too has a lot of work to do. And the CoreRT teams who for whatever reasons moves rather slowly. And the proposition is to embark into this new nebulous project that overlaps existing projects and delivers unknowns. Hmm...

You're right but I don't think it's our job as a community to get into their schedule, we can still discuss things and make proposals without stepping into their shoes, when and if these things will see the light of day, that's a different story so to that I'd say patience is a virtue.