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.

5 files changed, 238 insertions, 10 deletions

diff --git a/src/jit/valuenum.cpp b/src/jit/valuenum.cpp
index fb3202f164..b2b14ed581 100644
--- a/src/jit/valuenum.cpp
+++ b/src/jit/valuenum.cpp
@@ -1135,13 +1135,30 @@ ValueNum ValueNumStore::VNForFunc(var_types typ, VNFunc func, ValueNum arg0VN, V
     }
 }
 
+//------------------------------------------------------------------------------
+// VNForMapStore : Evaluate VNF_MapStore with the given arguments.
+//
+//
+// Arguments:
+//    typ  -    Value type
+//    arg0VN  - Map value number
+//    arg1VN  - Index value number
+//    arg2VN  - New value for map[index]
+//
+// Return Value:
+//    Value number for the result of the evaluation.
+
 ValueNum ValueNumStore::VNForMapStore(var_types typ, ValueNum arg0VN, ValueNum arg1VN, ValueNum arg2VN)
 {
     ValueNum result = VNForFunc(typ, VNF_MapStore, arg0VN, arg1VN, arg2VN);
 #ifdef DEBUG
     if (m_pComp->verbose)
     {
-        printf("    VNForMapStore(" STR_VN "%x, " STR_VN "%x, " STR_VN "%x):%s returns ", arg0VN, arg1VN, arg2VN, varTypeName(typ));
+        printf("    VNForMapStore(" STR_VN "%x, " STR_VN "%x, " STR_VN "%x):%s returns ",
+               arg0VN,
+               arg1VN,
+               arg2VN,
+               varTypeName(typ));
         m_pComp->vnPrint(result, 1);
         printf("\n");
     }
@@ -1149,10 +1166,30 @@ ValueNum ValueNumStore::VNForMapStore(var_types typ, ValueNum arg0VN, ValueNum a
     return result;
 }
 
+//------------------------------------------------------------------------------
+// VNForMapSelect : Evaluate VNF_MapSelect with the given arguments.
+//
+//
+// Arguments:
+//    vnk  -    Value number kind
+//    typ  -    Value type
+//    arg0VN  - Map value number
+//    arg1VN  - Index value number
+//
+// Return Value:
+//    Value number for the result of the evaluation.
+//
+// Notes:
+//    This requires a "ValueNumKind" because it will attempt, given "select(phi(m1, ..., mk), ind)", to evaluate
+//    "select(m1, ind)", ..., "select(mk, ind)" to see if they agree.  It needs to know which kind of value number
+//    (liberal/conservative) to read from the SSA def referenced in the phi argument.
+
+
 ValueNum ValueNumStore::VNForMapSelect(ValueNumKind vnk, var_types typ, ValueNum arg0VN, ValueNum arg1VN)
 {
     unsigned budget = m_mapSelectBudget;
-    ValueNum result = VNForMapSelectWork(vnk, typ, arg0VN, arg1VN, &budget);
+    bool usedRecursiveVN = false;
+    ValueNum result = VNForMapSelectWork(vnk, typ, arg0VN, arg1VN, &budget, &usedRecursiveVN);
 #ifdef DEBUG
     if (m_pComp->verbose)
     {
@@ -1164,7 +1201,33 @@ ValueNum ValueNumStore::VNForMapSelect(ValueNumKind vnk, var_types typ, ValueNum
     return result;
 }
 
-ValueNum ValueNumStore::VNForMapSelectWork(ValueNumKind vnk, var_types typ, ValueNum arg0VN, ValueNum arg1VN, unsigned* pBudget)
+//------------------------------------------------------------------------------
+// VNForMapSelectWork : A method that does the work for VNForMapSelect and may call itself recursively.
+//
+//
+// Arguments:
+//    vnk  -             Value number kind
+//    typ  -             Value type
+//    arg0VN  -          Zeroth argument
+//    arg1VN  -          First argument
+//    pBudget -          Remaining budget for the outer evaluation
+//    pUsedRecursiveVN - Out-parameter that is set to true iff RecursiveVN was returned from this method
+//                       or from a method called during one of recursive invocations.
+//
+// Return Value:
+//    Value number for the result of the evaluation.
+//
+// Notes:
+//    This requires a "ValueNumKind" because it will attempt, given "select(phi(m1, ..., mk), ind)", to evaluate
+//    "select(m1, ind)", ..., "select(mk, ind)" to see if they agree.  It needs to know which kind of value number
+//    (liberal/conservative) to read from the SSA def referenced in the phi argument.
+
+ValueNum ValueNumStore::VNForMapSelectWork(ValueNumKind vnk,
+                                           var_types typ,
+                                           ValueNum arg0VN,
+                                           ValueNum arg1VN,
+                                           unsigned* pBudget,
+                                           bool* pUsedRecursiveVN)
 {
     // This label allows us to directly implement a tail call by setting up the arguments, and doing a goto to here.
 TailCall:
@@ -1172,6 +1235,8 @@ TailCall:
     assert(arg0VN == VNNormVal(arg0VN));  // Arguments carry no exceptions.
     assert(arg1VN == VNNormVal(arg1VN));  // Arguments carry no exceptions.
 
+    *pUsedRecursiveVN = false;
+
 #ifdef DEBUG
     // Provide a mechanism for writing tests that ensure we don't call this ridiculously often.
     m_numMapSels++;
@@ -1204,6 +1269,7 @@ TailCall:
         // If it's recursive, stop the recursion.
         if (SelectIsBeingEvaluatedRecursively(arg0VN, arg1VN))
         {
+            *pUsedRecursiveVN = true;
             return RecursiveVN;
         }
         
@@ -1240,7 +1306,8 @@ TailCall:
 #endif
                     // This is the equivalent of the recursive tail call:
                     // return VNForMapSelect(vnk, typ, funcApp.m_args[0], arg1VN);
-                    arg0VN = funcApp.m_args[0];  // Make sure we capture any exceptions from the "i" and "v" of the store...
+                    // Make sure we capture any exceptions from the "i" and "v" of the store...
+                    arg0VN = funcApp.m_args[0];
                     goto TailCall;
                 }
             }
@@ -1284,7 +1351,12 @@ TailCall:
                     {
                         bool allSame = true;
                         ValueNum argRest = phiFuncApp.m_args[1];
-                        ValueNum sameSelResult = VNForMapSelectWork(vnk, typ, phiArgVN, arg1VN, pBudget);
+                        ValueNum sameSelResult = VNForMapSelectWork(vnk,
+                                                                    typ,
+                                                                    phiArgVN,
+                                                                    arg1VN,
+                                                                    pBudget,
+                                                                    pUsedRecursiveVN);
                         while (allSame && argRest != ValueNumStore::NoVN)
                         {
                             ValueNum cur = argRest;
@@ -1314,7 +1386,14 @@ TailCall:
                             }
                             else
                             {
-                                ValueNum curResult = VNForMapSelectWork(vnk, typ, phiArgVN, arg1VN, pBudget);
+                                bool usedRecursiveVN = false;
+                                ValueNum curResult = VNForMapSelectWork(vnk,
+                                                                        typ,
+                                                                        phiArgVN,
+                                                                        arg1VN,
+                                                                        pBudget,
+                                                                        &usedRecursiveVN);
+                                *pUsedRecursiveVN |= usedRecursiveVN;
                                 if (sameSelResult == ValueNumStore::RecursiveVN)
                                     sameSelResult = curResult;
                                 if (curResult != ValueNumStore::RecursiveVN && curResult != sameSelResult)
@@ -1328,7 +1407,13 @@ TailCall:
                             m_fixedPointMapSels.Pop();
 
                             // To avoid exponential searches, we make sure that this result is memo-ized.
-                            GetVNFunc2Map()->Set(fstruct, sameSelResult);
+                            // The result is always valid for memoization if we didn't rely on RecursiveVN to get it.
+                            // If RecursiveVN was used, we are processing a loop and we can't memo-ize this intermediate
+                            // result if, e.g., this block is in a multi-entry loop.
+                            if (!*pUsedRecursiveVN)
+                            {
+                                GetVNFunc2Map()->Set(fstruct, sameSelResult);
+                            }
 
                             return sameSelResult;
                         }
@@ -4208,8 +4293,11 @@ void Compiler::fgValueNumberBlock(BasicBlock* blk, bool newVNsForPhis)
 #ifdef DEBUG
                 ValueNum oldPhiAppVN = phiAppVN;
 #endif
-                phiAppVN = vnStore->VNForFunc(TYP_REF, VNF_Phi, vnStore->VNForIntCon(phiArgs->GetSsaNum()), phiAppVN);
-                JITDUMP("  Building phi application: $%x = phi(%d, $%x).\n", phiAppVN, phiArgs->GetSsaNum(), oldPhiAppVN);
+                unsigned phiArgSSANum = phiArgs->GetSsaNum();
+                ValueNum phiArgSSANumVN = vnStore->VNForIntCon(phiArgSSANum);
+                JITDUMP("  Building phi application: $%x = SSA# %d.\n", phiArgSSANumVN, phiArgSSANum);
+                phiAppVN = vnStore->VNForFunc(TYP_REF, VNF_Phi, phiArgSSANumVN, phiAppVN);
+                JITDUMP("  Building phi application: $%x = phi($%x, $%x).\n", phiAppVN, phiArgSSANumVN, oldPhiAppVN);
                 phiArgs = phiArgs->m_nextArg;
             }
             if (allSame)
diff --git a/src/jit/valuenum.h b/src/jit/valuenum.h
index 6b32332351..21047438ef 100644
--- a/src/jit/valuenum.h
+++ b/src/jit/valuenum.h
@@ -397,7 +397,13 @@ public:
     // (liberal/conservative) to read from the SSA def referenced in the phi argument.
     ValueNum VNForMapSelect(ValueNumKind vnk, var_types typ, ValueNum op1VN, ValueNum op2VN);
 
-    ValueNum VNForMapSelectWork(ValueNumKind vnk, var_types typ, ValueNum op1VN, ValueNum op2VN, unsigned* pBudget);
+    // A method that does the work for VNForMapSelect and may call itself recursively.
+    ValueNum VNForMapSelectWork(ValueNumKind vnk,
+                                var_types typ,
+                                ValueNum op1VN,
+                                ValueNum op2VN,
+                                unsigned* pBudget,
+                                bool* pUsedRecursiveVN);
 
     // A specialized version of VNForFunc that is used for VNF_MapStore and provides some logging when verbose is set
     ValueNum VNForMapStore(var_types typ, ValueNum arg0VN, ValueNum arg1VN, ValueNum arg2VN);
diff --git a/tests/src/JIT/Regression/JitBlue/devdiv_174983/app.config b/tests/src/JIT/Regression/JitBlue/devdiv_174983/app.config
new file mode 100644
index 0000000000..6f7bbd9d2b
--- /dev/null
+++ b/tests/src/JIT/Regression/JitBlue/devdiv_174983/app.config
@@ -0,0 +1,27 @@
+<?xml version="1.0" encoding="utf-8"?>
+<configuration>
+  <runtime>
+    <assemblyBinding xmlns="urn:schemas-microsoft-com:asm.v1">
+      <dependentAssembly>
+        <assemblyIdentity name="System.Runtime" publicKeyToken="b03f5f7f11d50a3a" culture="neutral" />
+        <bindingRedirect oldVersion="0.0.0.0-4.0.20.0" newVersion="4.0.20.0" />
+      </dependentAssembly>
+      <dependentAssembly>
+        <assemblyIdentity name="System.Text.Encoding" publicKeyToken="b03f5f7f11d50a3a" culture="neutral" />
+        <bindingRedirect oldVersion="0.0.0.0-4.0.10.0" newVersion="4.0.10.0" />
+      </dependentAssembly>
+      <dependentAssembly>
+        <assemblyIdentity name="System.Threading.Tasks" publicKeyToken="b03f5f7f11d50a3a" culture="neutral" />
+        <bindingRedirect oldVersion="0.0.0.0-4.0.10.0" newVersion="4.0.10.0" />
+      </dependentAssembly>
+      <dependentAssembly>
+        <assemblyIdentity name="System.IO" publicKeyToken="b03f5f7f11d50a3a" culture="neutral" />
+        <bindingRedirect oldVersion="0.0.0.0-4.0.10.0" newVersion="4.0.10.0" />
+      </dependentAssembly>
+      <dependentAssembly>
+        <assemblyIdentity name="System.Reflection" publicKeyToken="b03f5f7f11d50a3a" culture="neutral" />
+        <bindingRedirect oldVersion="0.0.0.0-4.0.10.0" newVersion="4.0.10.0" />
+      </dependentAssembly>
+    </assemblyBinding>
+  </runtime>
+</configuration>
diff --git a/tests/src/JIT/Regression/JitBlue/devdiv_174983/devdiv_174983.cs b/tests/src/JIT/Regression/JitBlue/devdiv_174983/devdiv_174983.cs
new file mode 100644
index 0000000000..4097029ada
--- /dev/null
+++ b/tests/src/JIT/Regression/JitBlue/devdiv_174983/devdiv_174983.cs
@@ -0,0 +1,57 @@
+// Copyright (c) Microsoft. All rights reserved.
+// Licensed under the MIT license. See LICENSE file in the project root for full license information.
+//
+
+using System;
+
+public class Test
+{
+    public int i;
+    public int j;
+
+    public static int l;
+
+    public static int Main()
+    {
+        Test test = new Test();
+        test.i = 3;
+        test.j = 5;
+        Test.l = 1;
+        if (test.Foo() == 8)
+        {
+            Console.WriteLine("PASS!");
+            return 100;
+        }
+        else
+        {
+            Console.WriteLine("FAIL!");
+            return 101;
+        }
+    }
+
+    // This tests a multi-entry loop where we have to evaluate recursive phi's
+    // for heap state in value numbering.
+    public int Foo()
+    {        
+        if (l != 17)
+        {
+            goto L2;
+        }
+
+        i = 0;
+
+L1:
+        if (l == 1)
+        {
+            // In the bug the compiler incorrectly concluded that i is always 0 here.
+            return i + j;
+        }       
+
+L2:
+        if (l == 12)
+        {
+            return i;
+        }
+        goto L1;
+    }
+}
diff --git a/tests/src/JIT/Regression/JitBlue/devdiv_174983/devdiv_174983.csproj b/tests/src/JIT/Regression/JitBlue/devdiv_174983/devdiv_174983.csproj
new file mode 100644
index 0000000000..d80962697d
--- /dev/null
+++ b/tests/src/JIT/Regression/JitBlue/devdiv_174983/devdiv_174983.csproj
@@ -0,0 +1,50 @@
+<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="12.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.props))\dir.props" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <AssemblyName>$(MSBuildProjectName)</AssemblyName>
+    <SchemaVersion>2.0</SchemaVersion>
+    <ProjectGuid>{95DFC527-4DC1-495E-97D7-E94EE1F7140D}</ProjectGuid>
+    <OutputType>Exe</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <FileAlignment>512</FileAlignment>
+    <ProjectTypeGuids>{786C830F-07A1-408B-BD7F-6EE04809D6DB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}</ProjectTypeGuids>
+    <ReferencePath>$(ProgramFiles)\Common Files\microsoft shared\VSTT\11.0\UITestExtensionPackages</ReferencePath>
+    <SolutionDir Condition="$(SolutionDir) == '' Or $(SolutionDir) == '*Undefined*'">..\..\</SolutionDir>
+
+    <NuGetPackageImportStamp>7a9bfb7d</NuGetPackageImportStamp>
+  </PropertyGroup>
+  <!-- Default configurations to help VS understand the configurations -->
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+  </PropertyGroup>
+  <ItemGroup>
+    <CodeAnalysisDependentAssemblyPaths Condition=" '$(VS100COMNTOOLS)' != '' " Include="$(VS100COMNTOOLS)..\IDE\PrivateAssemblies">
+      <Visible>False</Visible>
+    </CodeAnalysisDependentAssemblyPaths>
+  </ItemGroup>
+  <PropertyGroup>
+    <DebugType>None</DebugType>
+    <Optimize>True</Optimize>
+  </PropertyGroup>
+  <ItemGroup>
+    <Compile Include="devdiv_174983.cs" />
+  </ItemGroup>
+  <ItemGroup>
+    <None Include="$(JitPackagesConfigFileDirectory)threading+thread\project.json" />
+    <None Include="app.config" />
+  </ItemGroup>
+  <ItemGroup>
+    <Service Include="{82A7F48D-3B50-4B1E-B82E-3ADA8210C358}" />
+  </ItemGroup>
+  <PropertyGroup>
+    <ProjectJson>$(JitPackagesConfigFileDirectory)threading+thread\project.json</ProjectJson>
+    <ProjectLockJson>$(JitPackagesConfigFileDirectory)threading+thread\project.lock.json</ProjectLockJson>
+  </PropertyGroup>
+  <Import Project="$([MSBuild]::GetDirectoryNameOfFileAbove($(MSBuildThisFileDirectory), dir.targets))\dir.targets" />
+  <PropertyGroup Condition=" '$(MsBuildProjectDirOverride)' != '' ">
+  </PropertyGroup> 
+</Project>