Null check folding.
authorEugene Rozenfeld <erozen@microsoft.com>
Fri, 5 Aug 2016 20:14:58 +0000 (13:14 -0700)
committerEugene Rozenfeld <erozen@microsoft.com>
Fri, 5 Aug 2016 22:43:16 +0000 (15:43 -0700)
commit47eec64cdd246244a7dee1e7edd054e9e579be02
tree0b5c923a8fbff21ce515395beda2ddba50ca2bfc
parent693fff99049bc7d63459b2c444237ca532036b47
Null check folding.

1. Added a null check folding optimization to early prop. The optimization tries to fold
GT_NULLCHECK(y) nodes  into GT_IND(x) nodes where x=y+const
in the same block (where const is sufficiently small). The algorithm uses SSA use-def info
to go from x to its def and then tries to match the pattern x = COMMA(NULLCHECK(y), ADD(y, const))).
If such a pattern is found, the algorithm checks the trees and statements that are between the use
and the def in execution order to see if they have unsafe side effects: calls, exception sources, and
assignments (all assignment if we are in a try and assignments to global memory if we are not).
If there are no nodes with unsafe side effects, the null check is removed.

2. Made several improvements to null check elimination in assertion propagation.
..* Added a new kind for op1: O1K_VALUE_NUMBER
..* Non-null assertions can now be made about arbitrary value numbers, not just locals
..* Fixed code that was trying to find a ref given a byref: the code now handles an arbitrary number of
    offsets and checks whether the total offsetof is small enough.
..* Added similar code that tries to find a ref VN given a byref VN

This addresses part of the suboptimal code generated for #1226: null check is no longer emitted.

Correctness: ran full desktop and CoreCLR testing.

Throughput: no measurable throughput impact (verified by running internal CQNgenTP several times).

Code size in CoreCLR:

Framework assemblies:

Total bytes of diff: -805 (-0.01 % of base)
    diff is an improvement.
Total byte diff includes 0 bytes from reconciling methods
        Base had    0 unique methods,        0 unique bytes
        Diff had    0 unique methods,        0 unique bytes
Top file improvements by size (bytes):
        -352 : System.Private.CoreLib.dasm (-0.01 % of base)
        -306 : Microsoft.CodeAnalysis.CSharp.dasm (-0.01 % of base)
         -58 : Microsoft.CodeAnalysis.dasm (-0.01 % of base)
         -48 : System.Numerics.Vectors.dasm (-0.08 % of base)
         -14 : System.Xml.XmlDocument.dasm (-0.01 % of base)
7 total files with size differences.
Top method improvements by size (bytes):
         -30 : System.Numerics.Vectors.dasm - System.Numerics.Matrix4x4:ToString():ref:this
         -30 : System.Private.CoreLib.dasm - System.DateTimeParse:ParseByFormat(byref,byref,byref,ref,byref):bool
         -24 : Microsoft.CodeAnalysis.CSharp.dasm - <GetMethodsToEmit>d__68:MoveNext():bool:this
         -18 : System.Private.CoreLib.dasm - System.DateTimeParse:Lex(int,byref,byref,byref,byref,byref,int):bool
         -18 : System.Private.CoreLib.dasm - System.DateTimeParse:ProcessDateTimeSuffix(byref,byref,byref):bool
243 total methods with size differences.

JIT Code quality benchmarks in CoreCLR:

Total bytes of diff: -29 (-0.01 % of base)
    diff is an improvement.
Total byte diff includes 0 bytes from reconciling methods
        Base had    0 unique methods,        0 unique bytes
        Diff had    0 unique methods,        0 unique bytes
Top file improvements by size (bytes):
         -25 : Bytemark\Bytemark\Bytemark.dasm (-0.03 % of base)
          -4 : BenchmarksGame\pidigits\pi-digits\pi-digits.dasm (-0.21 % of base)
2 total files with size differences.
Top method improvements by size (bytes):
          -9 : Bytemark\Bytemark\Bytemark.dasm - AssignJagged:second_assignments(ref,ref)
          -6 : Bytemark\Bytemark\Bytemark.dasm - EMFloat:MultiplyInternalFPF(byref,byref,byref)
          -4 : Bytemark\Bytemark\Bytemark.dasm - EMFloat:AddSubInternalFPF(ubyte,byref,byref,byref)
          -2 : Bytemark\Bytemark\Bytemark.dasm - EMFloat:denormalize(byref,int)
          -2 : Bytemark\Bytemark\Bytemark.dasm - EMFloat:DivideInternalFPF(byref,byref,byref)
8 total methods with size differences.

In internal SPMI:

3915 methods with diffs, almost everything -- code size improvements
13,715 bytes code size reduction overall 0.51% on affected methods

CQ_Perf: 85 methods with diffs, 84 code size improvements, no regressions
Benchmarks with code size diffs:
Roslyn 59
TrueTypeBench 19
mono-pi-digits 2
mono-chameneos-redux 2
ByteMark\assign_jagged 1
Json_Serialize 1
SharpChess 1
BenchI\mulmtx 1

Internal CQPerf didn't report any runtime wins for these benchmarks.
src/jit/assertionprop.cpp
src/jit/block.h
src/jit/compiler.h
src/jit/earlyprop.cpp
src/jit/morph.cpp