JIT: implement forward substitution

[gafter]

This is moved from dotnet/roslyn#6542

Commenting out the first two lines of this for loop and uncommenting the third results in a 42% speedup:

int count = 0;
for (uint i = 0; i < 1000000000; ++i) {
    var isMultipleOf16 = i % 16 == 0;
    count += isMultipleOf16 ? 1 : 0;
    //count += i % 16 == 0 ? 1 : 0;
}

Behind the timing is vastly different assembly code: 13 vs. 7 instructions in the loop. The platform is Windows 7 running .NET 4.0 x64. Code optimization is enabled, and the test app was run outside VS2010.

Repro project
StackOverflow question on this topic

/cc @breyed

Note that this issue has also been demonstrated in VS2015.

category:cq
theme:forward-substitution
skill-level:expert
cost:extra-large

[mikedn]

The title is a bit misleading as the local variable is actually eliminated, there's no memory load/store anywhere in the generated code.

Related to #4207 as the problem is really the ceq/brtrue sequence and not local variable elimination. Also related to #4399 as both versions generate a less than ideal bool to 0/1 conversion. Also related to #4353 because both versions generate 2 useless instructions for i % 16.

The mod to and conversion has a problem that I haven't seen reported before - it generates a and, test sequence instead of a single test.

/cc @cmckinsey

[cmckinsey]

Thanks for the report Neil. In general I'd like the JIT to be less sensitive to minor code-shape/structure issues such as whether or not a single-def/single-use named variable is used rather than embedded in the consuming tree. While users can work-around this in limited fashion, in the presence of inlining this becomes impossible. This transformation proves crucial in other MS compilers that have extensive tree-optimization capability to create bigger trees.

@mikedn Thanks for the analysis. While there are other things going on here (like missed setcc transformation even in the original version), the largest issue is lack of forward-substitution. We should ideally change the name of this issue to reflect missing forward-substitution transformation. However feel free to open an issue for the and/test->test combining.

Thanks.

[mikedn]

@cmckinsey

However feel free to open an issue for the and/test->test combining.

No need, if the div/mod PR is merged this particular issue is solved because the and/test -> test transform is done in LowerCmp.

[papaslavik]

@cmckinsey

This transformation proves crucial in other MS compilers that have extensive tree-optimization capability to create bigger trees.

Are there any plans for contributing such a feature to coreclr?

[GSPP]

Are there any plans to move to an SSA-based internal representation? LLVM has that and I believe GCC as well. The Hotspot JIT has it, too. V8 does this, too. AFAIK this is the most modern and flexible way to represent code inside of a compiler. All these issues that are caused by specific tree shapes should go away.

[SunnyWar]

@GSPP Latest MS Visual C++ compiler has SSA back end also: [https://blogs.msdn.microsoft.com/vcblog/2016/05/04/new-code-optimizer/] The link provides some examples of code the JIT handles pretty poorly.

[GSPP]

So the old VC compiler was tree based (because it was not SSA based). Some .NET JITs are based on the VC codebase according to public information. I don't recall which ones. Maybe RyuJIT inherited this undesirable tree-based structure.

[mikedn]

@GSPP @SunnyWar Guys, seriously, you can be sure that the JIT team knows what SSA is and many other things. RyuJIT uses SSA (which doesn't exclude being tree based) and VC++ has been using SSA for a long time (and I doubt that it's tree based). This kind of posts do not contribute anything to this issue or any other issues.

[GSPP]

@mikedn maybe you're right.

[BruceForstall]

@AndyAyersMS Can we close this and just keep #6973?

[AndyAyersMS]

This one has more cross-links, so if we close it, maybe we should enumerate the related issues in the survivor?

[BruceForstall]

This one has more cross-links, so if we close it, maybe we should enumerate the related issues in the survivor?

I generally assume that someone addressing such a big work item will look at the linked items, even if closed.