Fix a bug in JIT value numbering.
authorEugene Rozenfeld <erozen@microsoft.com>
Fri, 22 Jan 2016 01:54:10 +0000 (17:54 -0800)
committerEugene Rozenfeld <erozen@microsoft.com>
Fri, 22 Jan 2016 23:38:51 +0000 (15:38 -0800)
commitfda3475fa704e854d22922b4ac280aa8064bca35
treee27c5944b7a144d38605278a531e7ba468a218f6
parentbdd9b58273d2275f50215a493d23e277ef729ad9
Fix a bug in JIT value numbering.

This is a fix for a silent bad codegen bug in value numbering.
The value numbering algorithm tries to check whether heap PHI arguments
evaluate to the same value for the given query. In doing so, it may encounter
PHIs that recursively depend on each other (this corresponds to cycles in
control flow graph). A special value RecursiveVN is returned in such cases.
The algorithm uses the following rule:
if some PHI arguments evaluate to RecursiveVN but all others evaluate to the
same value that's not RecursiveVN, then that value can be used as the result.
Furthermore, in order to avoid exponential searches in case of many PHI's the
results of all PHI evaluations are memoized.

The bug was that if RecursiveVN was used to get the result, it can't always
be memoized. In particular, if the loop causing recursive PHIs is a multi-entry
loop, intermediate PHI results shouldn't be memoized. The fix is conservative in
that it always disables memoization if RecursiveVN was involved. Note that we
also have another mechanism (budget) to mitigate expensive PHI evaluations.

There were no diffs in SuperPMI and no measurable throughput impact.

I added a test with a simplified repro.
The original bug had code with yield return.

I also fixed some formatting and added several function headers.
src/jit/valuenum.cpp
src/jit/valuenum.h
tests/src/JIT/Regression/JitBlue/devdiv_174983/app.config [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/devdiv_174983/devdiv_174983.cs [new file with mode: 0644]
tests/src/JIT/Regression/JitBlue/devdiv_174983/devdiv_174983.csproj [new file with mode: 0644]