JIT: Fix value type box optimization (#13016)
authorAndy Ayers <andya@microsoft.com>
Mon, 31 Jul 2017 20:01:01 +0000 (13:01 -0700)
committerGitHub <noreply@github.com>
Mon, 31 Jul 2017 20:01:01 +0000 (13:01 -0700)
commit9c844a9f2a1a40fca1766ccc3a3c5e146743cb13
treed57dfb129ba010627de610f5bdf5cc549f356760
parent6b38dca32dee8321dafab8be92366d17da2b8bec
JIT: Fix value type box optimization (#13016)

Boxing a value type produces a non-null result. If the result of the box is
only used to feed a compare against null, the jit tries to optimize the box
away entirely since the result of the comparison is known. Such idiomatic
expressions arise fairly often in generics instantiated over value types.

In the current implementation the box expands into two parts. The first is
an upstream statement to allocate a boxed object and assign a reference to
the boxed object to a local var known as the "box temp". The second is an
expression tree whose value is the box temp that also contains an an
encapsulated copy from the value being boxed to the payload section of the
boxed object. The box node also contains a pointer back to the first
statement (more on this later).

In the examples being discussed here this second tree is a child of a compare
node whose other child is a null pointer. When the optimization fires, the
upstream allocation statement is located via the pointer in the box node and
removed, and the entire compare is replaced with a constant 0 or 1 as
appropriate. Unfortunately the encapsulated copy in the box subtree may
include side effects that should be preserved, and so this transformation is
unsafe.

Note that the copy subtree as a whole will always contain side effects, since
the copy is storing values into the heap, and that copy now will not happen.
But the side effects that happen when producing the value to box must remain.

In the initial example from #12949 the side effects in question were
introduced by the jit's optimizer to capure a CSE definition. #13016 gives
several other examples where the side effects are present in the initial user
code. For instance the value being boxed might come from an array, in which
case the encapsulated copy in the box expression tree would contain the array
null check and bounds check. So removing the entire tree can alter behavior.

This fix attempts to carefully preserve the important side effects by
reworking how a box is imported. The copy is now moved out from under the box
into a second upstream statement. The box itself is then just a trivial
side-effect-free reference to the box temp. To ensure proper ordering of side
effects the jit spills the evaluation stack before appending the copy
statement.

When the optimization fires the jit removes the upstream heap allocation
as before, as well as the now-trivial compare tree. It analyzes the source
side of the upstream copy. If it is side effect free, the copy is removed
entirely. If not, the jit modifies the copy into a minimal load of the
boxed value, and this load should reproduce the necessary side effects.

The optimization is only performed when the tree shape of the copy matches
expected patterns.

There are some expected cases where the tree won't match, for instance if the
optimization is invoked while the jit is inlining. Because this optimization
runs at several points the jit can catch these cases once inlining completes.
There is one case that is not handled that could be -- if the assignment part
of the copy is itself a subtree of a comma. This doesn't happen often.

The optimization is now also extended to handle the case where the comparision
operation is `cgt.un`. This doesn't catch any new cases but causes the
optimization to happen earlier, typically during importation, which should
reduce jit time slightly.

Generally the split of the box into two upstream statements reduces code size,
especially when the box expression is incorporated into a larger tree -- for
example a call. However in some cases where the value being boxed comes from
an array, preserving the array bounds check now causes loop cloning to kick
in and increase code size. Hence the overall size impact on the jit-diff set is
essentially zero.

Added a number of new test cases showing the variety of situations that must
be handled and the need to spill before appending the copy statement.

Fixes #12949.
19 files changed:
src/jit/gentree.cpp
src/jit/gentree.h
src/jit/importer.cpp
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_1.cs [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_1.csproj [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_2.cs [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_2.csproj [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_3.cs [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_3.csproj [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_4.cs [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_4.csproj [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_5.cs [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_5.csproj [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_6.cs [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_6.csproj [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_7.cs [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_7.csproj [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_8.cs [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/GitHub_12949/GitHub_12949_8.csproj [new file with mode: 0644]