Record expr location for opqaue value numbers
authorJoseph Tremoulet <jotrem@microsoft.com>
Sat, 13 Aug 2016 18:17:09 +0000 (14:17 -0400)
committerJoseph Tremoulet <jotrem@microsoft.com>
Tue, 16 Aug 2016 14:38:26 +0000 (10:38 -0400)
commitfbb1a28a9bb92ed2a22c3c7f5cbfcc6e4fbe104f
treecb7c4dc257fe588d263e2161e87999170c01e946
parent0b4cb32910b989b2e93885a1b02f6ba1446bb005
Record expr location for opqaue value numbers

When value numbering sees an expression that is too complex, runs out of
compile-time budget for deep field/phi sequences, etc., it assigns
`VNForExpr()` for the expression whose value number is being computed.
This produces a new, unique, opaque value number that will compare as
equal to itself but not to any other value number.

This change updates value numbering to record the location of the
expression whose value such a value numbers is created to stand in for.
While attaching location information to value numbers in general must be
done with care regarding subtleties of correlating value numbers for
expressions in different locations that compute the same value, those
subtleties are not relevant in the case of these unique/opaque value
numbers, whose point is to stand in for the value of one particular
expression and whose value may be propagated by copies but will never be
computed by other redundant expressions.

Loop-invariant code hoisting is updated to take these locations into
account when determining loop-invariance; the opaque value number is
loop-invariant if the expression whose value it represents is outside the
loop.

The `VNForExpr()` method is updated to take a `BasicBlock*` to identify
the location, but the backing store only records the block's loop number,
since the loop-invariance check is the only consumer of this information
and doing so allows a more compact representation (in particular, we avoid
allocating `m_defs` backing storage for these value numbers, since they are
used for the "give up and be conservative" cases).

The `BasicBlock*` passed to `VNForExpr()` can be `nullptr` to still have
the prior semantics of a fully opaque value number that can't be proved
loop-invariant; this is used for a handful of cases where the budgeting
results are memoized and so expressions at different locations could end
up sharing opaque value numbers, as well as a few cases where the
`VNForExpr()` call is covering a rare corner case in a utility for which
the corresponding `BasicBlock` may not be handy.

Fixes dotnet/coreclr#6303.

Commit migrated from https://github.com/dotnet/coreclr/commit/91de2cec1e2156a2fb418c6dfa1716b4ad59ad30
src/coreclr/src/jit/block.h
src/coreclr/src/jit/gentree.cpp
src/coreclr/src/jit/morph.cpp
src/coreclr/src/jit/optimizer.cpp
src/coreclr/src/jit/valuenum.cpp
src/coreclr/src/jit/valuenum.h