From fda3475fa704e854d22922b4ac280aa8064bca35 Mon Sep 17 00:00:00 2001 From: Eugene Rozenfeld Date: Thu, 21 Jan 2016 17:54:10 -0800 Subject: [PATCH] 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 | 106 +++++++++++++++++++-- src/jit/valuenum.h | 8 +- .../Regression/JitBlue/devdiv_174983/app.config | 27 ++++++ .../JitBlue/devdiv_174983/devdiv_174983.cs | 57 +++++++++++ .../JitBlue/devdiv_174983/devdiv_174983.csproj | 50 ++++++++++ 5 files changed, 238 insertions(+), 10 deletions(-) create mode 100644 tests/src/JIT/Regression/JitBlue/devdiv_174983/app.config create mode 100644 tests/src/JIT/Regression/JitBlue/devdiv_174983/devdiv_174983.cs create mode 100644 tests/src/JIT/Regression/JitBlue/devdiv_174983/devdiv_174983.csproj diff --git a/src/jit/valuenum.cpp b/src/jit/valuenum.cpp index fb3202f..b2b14ed 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 6b32332..2104743 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 0000000..6f7bbd9 --- /dev/null +++ b/tests/src/JIT/Regression/JitBlue/devdiv_174983/app.config @@ -0,0 +1,27 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + 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 0000000..4097029 --- /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 0000000..d809626 --- /dev/null +++ b/tests/src/JIT/Regression/JitBlue/devdiv_174983/devdiv_174983.csproj @@ -0,0 +1,50 @@ + + + + + Debug + AnyCPU + $(MSBuildProjectName) + 2.0 + {95DFC527-4DC1-495E-97D7-E94EE1F7140D} + Exe + Properties + 512 + {786C830F-07A1-408B-BD7F-6EE04809D6DB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC} + $(ProgramFiles)\Common Files\microsoft shared\VSTT\11.0\UITestExtensionPackages + ..\..\ + + 7a9bfb7d + + + + + + + + + False + + + + None + True + + + + + + + + + + + + + $(JitPackagesConfigFileDirectory)threading+thread\project.json + $(JitPackagesConfigFileDirectory)threading+thread\project.lock.json + + + + + -- 2.7.4