Full support for exception sets in value numbering. by briansull · Pull Request #20129 · dotnet/coreclr

briansull · 2018-09-25T20:28:06Z

New method that add exception sets:
fgValueNumberAddExceptionSet

vnAddExceptionSetForIndirection
vnAddExceptionSetForDivision
vnAddExceptionSetForOverflow
vnAddExceptionSetForCkFinite

Refactoring work added methods:
VNEvalShouldFold - method to decide if constant folding should be performed
EvalUsingMathIdentity - Uses math identities to simplify value number exoressions
Renamed fgValueNumberHelperMethVNFunc to fgValueNumberJitHelperMethodVNFunc

Added standard method header comments for all five overloads of VNForFunc

4creators · 2018-09-25T20:50:01Z

src/jit/valuenum.cpp

-    if (GetVNFunc0Map()->Lookup(func, &res))
+    // Have we already assigned a ValueNum for 'func' ?
+    //
+    if (GetVNFunc0Map()->Lookup(func, &resultVN))


Perhaps it could more easy to read if if condition would be negated and fused with else statement.

4creators · 2018-09-25T20:52:27Z

src/jit/valuenum.cpp

-#endif
-
+//----------------------------------------------------------------------------------------
+//  VNForFunc-2      - Returns the ValueNum associated with 'func'('arg0VN','arg1VN')


From docs perspective VNForFunc-2 could be misleading since it could indicate function name. In reality func name is VNForFunc but is defined as different overload what cen be immediately seen from list of args

I think that what I have done with the number suffix -1 -2 -3 is fine here.
As a function name can never contain a "-" symbol.

@briansull
I am raising this problem bcs I have started working on automatic generation of docs for native code using doxygen. First attempts look promising. Current documentation format is not supported by doxygen and good quality docs generation would require applying transforms which most probably could be implemented either by using clang-doxygen build or by sophisticated regex. Having to recognize invalid function name and match it with signature in code could be an additional problem preventing docs generation.

How does doxygen differenentiate between function overloads with the same name?

doxygen uses either its own fully functional C++ parser or even better integrates with Clang and relies on Clang parser for C/C++ code understanding.

Function overloads are displayed in a similar way as C# overloads are displayed in C# docs.

That is the full prototype with all of the types for all arguments, right?

Write(String, Object, Object, Object, Object)
Write(String, Object, Object, Object)

4creators · 2018-09-25T20:57:08Z

src/jit/valuenum.cpp

+        {
+            // We can fold the expression, but we don't want to fold
+            // when the expression will always throw an exception
+            shouldFold = VNEvalShouldFold(typ, func, arg0VN, arg1VN);


I have analyzed similar problem while writing folding check in importer and it seems that there are 2 possible scenarios with 2 possible decisions:

Expression tree is much bigger in comparison to tree with exception -> decision: it is better to fold.

Expression tree is comparable or smaller than exception tree -> decision: do not fold.

Actually the reason that VNEvalShouldFold returns false is that the folding of some expressions would turn them into an unconditional throw. When the expression unconditionally throws it does not produce a useful "normal" value number and using a dummy value such a zero causes problems because we think that we can use that zero in the CSE phase.

It is simpler to detect such cases and not try to fold them in value numbering.
So we do not fold (5 / 0) or (MIN_INT / -1)

Got it. Thanks for explanation

4creators · 2018-09-25T21:00:30Z

src/jit/valuenum.cpp

-                        }
-                        break;
+//----------------------------------------------------------------------------------------
+//  VNForFunc-3      - Returns the ValueNum associated with 'func'('arg0VN','arg1VN','arg2VN')


The same docs problem as above: function name has not changed.

I think that what I have done with the number suffix -1 -2 -3 is fine here.
As a function name can never contain a "-" symbol.

src/jit/valuenum.cpp

mikedn · 2018-09-26T05:12:32Z

src/jit/compiler.h

-    VNFunc fgValueNumberHelperMethVNFunc(CorInfoHelpFunc helpFunc);
+    // Requires that "helpFunc" is one of the pure Jit Helper methods.
+    // Returns the corresponding VNFunc to use for value numbering
+    VNFunc fgValueNumberJitHelperMethodVNFunc(CorInfoHelpFunc helpFunc);


Consistency with existing code can be a good thing but maybe it's time to stop using fg for everything. All these new functions should have a vn prefix.

Yeah, I know, I can do that in an upcoming changeset

OK I will change the names of these methods to start with vnAddExceptionSet

mikedn · 2018-09-26T05:14:05Z

src/jit/valuenumfuncs.h

-ValueNumFuncDef(ArithmeticExc, 2, false, false, false)      // E.g., for signed its, MinInt / -1.
-ValueNumFuncDef(OverflowExc, 1, false, false, false)        // Integer overflow check. Args: 0: expression value,  throws when it overflows
+ValueNumFuncDef(ArithmeticExc, 2, false, false, false)      // Arithmetic exception check, ckfinite and integer division overflow, Args: 0: expression value,
+ValueNumFuncDef(OverflowExc, 1, false, false, false)        // Integer overflow check. used for chjecked add,sub and mul Args: 0: expression value,  throws when it overflows


for checked add

mikedn · 2018-09-26T05:18:27Z

src/jit/valuenum.cpp

+    ValueNum resultVN = NoVN;
+
+    // We may create one of these in the switch below.
+    ValueNum ZeroVN;


These should be moved inside the switch

mikedn · 2018-09-26T05:19:14Z

src/jit/valuenum.cpp

+    if (typ == TYP_BYREF) // We don't want/need to optimize a zero byref
    {
-        return res;
+        return NoVN;


Return resultVN for consistency?

mikedn · 2018-09-26T05:21:22Z

src/jit/valuenum.cpp

+                ZeroVN = VNZeroForType(typ);
+                if (arg1VN == ZeroVN)
+                {
+                    resultVN = arg0VN;


0 shifted by anything gives 0

OK I will add

mikedn · 2018-09-26T05:26:48Z

src/jit/valuenum.cpp

+                // This identity does not apply for floating point (when x == -0.0)
+                // (x + 0) == (0 + x) => x
+                ZeroVN = VNZeroForType(typ);
+                if (VNIsEqual(arg0VN, ZeroVN))


Maybe it would be clearer to just wrap the whole thing in an if (!varTypeIsFloating(typ)) instead of relying on VNIsEqual.

I will rework this area to be clearer

mikedn · 2018-09-26T05:28:09Z

src/jit/valuenum.cpp

+            // First we'll record the exeception set for the rhs and
+            // later we will union in the exeception set for the lhs
+            //
+            ValueNum vnExcSet = ValueNumStore::VNForEmptyExcSet();


Wouldn't be better to change VNUnpackExc to always initialize pvnx rather than doing this all other the place?

I will think about that

Opened #20185

mikedn · 2018-09-26T05:30:10Z

src/jit/valuenum.cpp

+                if (vnStore->IsVNConstant(funcCAttr.m_args[1]) &&
+                    varTypeIsIntegral(vnStore->TypeOfVN(funcCAttr.m_args[1])))
+                {
+                    offset += vnStore->CoercedConstantValue<ssize_t>(funcCAttr.m_args[1]);


Hmm, I don't understand this. Looks like the total offset is extracted from both liberal and conservative VNs?

I will double check

I redid this area and fixed it. Thanks

mikedn · 2018-09-26T05:31:29Z

src/jit/valuenum.cpp

+
+    if (typ == TYP_INT)
+    {
+        INT32 kVal;


Move inside ifs below. There are more cases below.

mikedn · 2018-09-26T05:33:22Z

src/jit/valuenum.cpp

+    ValueNumPair vnpTreeExc    = ValueNumStore::VNPForEmptyExcSet();
+    ValueNumPair vnpDivZeroExc = ValueNumStore::VNPForEmptyExcSet();
+    ValueNumPair vnpArithmExc  = ValueNumStore::VNPForEmptyExcSet();
+    ValueNumPair newExcSet;


Move it below, where it is initialized.

mikedn · 2018-09-26T05:33:35Z

src/jit/valuenum.cpp

+    //
+    ValueNumPair vnpTreeNorm;
+    ValueNumPair vnpTreeExc = ValueNumStore::VNPForEmptyExcSet();
+    ValueNumPair newExcSet;


Move to initialization

mikedn · 2018-09-26T05:33:44Z

src/jit/valuenum.cpp

+    //
+    ValueNumPair vnpTreeNorm;
+    ValueNumPair vnpTreeExc = ValueNumStore::VNPForEmptyExcSet();
+    ValueNumPair newExcSet;


Move to initialization

mikedn · 2018-09-26T05:35:13Z

src/jit/valuenum.cpp

+            case GT_ARR_LENGTH: // Implicit null check.
+            case GT_IND:        // Implicit null check.
+            case GT_NULLCHECK:  // Explicit null check.
+                fgValueNumberAddExceptionSetForIndirection(tree);


About other indir-like nodes (atomic ops, HW intrinsics)?

Also, there's a GTF_IND_NONFAULTING flags, should that be tested here?

If those nodes return true for OperMayThrow then they must be added here. (otherwise we assert in Debug)
If they don't, then it is a nop to add code to handle them here.

OperMayThrow checks for the GTF_IND_NONFAULTING flag, so we don't need to handle it here.

If those nodes return true for OperMayThrow then they must be added here

GT_HWIntrinsic can return true if it's a load/store. I don't see atomic ops in OperMayThrow but they probably should be there too.

briansull · 2018-09-28T17:50:43Z

@dotnet/jit-contrib PTAL
@AndyAyersMS PTAL

I have investigated the diffs and they are very few and are a very small.
They are caused when a CSE def has no NullPtrExc and the CSE use has a NullPtrExc.

briansull · 2018-09-28T17:57:35Z

Fixes #8648 and #10111

AndyAyersMS · 2018-09-28T21:01:30Z

src/jit/optcse.cpp

                {
-                    unsigned int cseBit = genCSEnum2bit(tree->gtCSEnum);
-                    CSEdsc*      desc   = optCSEfindDsc(tree->gtCSEnum);
+                    unsigned     CSEnum = GET_CSE_INDEX(tree->gtCSEnum);


Seems like somewhere in here (or perhaps in the method header) you should outline the general approach: the intention is to determine for each candidate if the intersection of all the exceptions provided by the defs is a superset of the union of the exceptions expected by the (qualified) uses.

The algorithm uncovers the defs and uses gradually and so incrementally building up both the intersection def set and the union use set.

It would be good to make sure we have (or can point at) test cases that show the various cases of this code getting covered.

I am still thinking about it but wonder if there is some implicit priority in choosing uses that should be thought about more carefully. Suppose we first find a def with exceptions 1, 2, 3 and then a use with exceptions 1, 2, 3, and then a def with exceptions 2, 3 and then a use with exceptions 2, 3. By the current algorithm we would not do any CSE here. But we could still CSE the 2,3 use.

So I wonder if instead we should not disqualify any uses until we've seen them all, and then pick the subset of uses that is compatible with what the definitions can provide.

Typically expressions with the same Normal ValueNum generate exactly the same exception sets. There are two way that we can get different exception sets with the same Normal value number.

We used an arithmetic identiity:
e.g.: (p.a + q.b) * 0 -- The normal value for the expression is set to zero because of the multiply by zero.
e.g. (p.a - p.a ) -- The normal value for the expression is set to zero because of the subtraction of the same value.

We stored an expression into a LclVar or into Memory and used it later in a CSE:
e.g. t = p.a; e1=(t + q.b); e2=(p.a+q.b) -- e1 has one NullPtrExc and e2 has two.
e.g. m.a = p.a; e1=(m.a + q.b); e2=(p.a + q.b) -- e1 and e2 have different exception sets.

The bug cases were due to case 1.
The small code regressions are due to case 2.

I believe that case 2 can be fixed by adding exception sets to the ValueNum that we use to track the Global Heap. After each operation we would update the Global Heap with any new NullPtrExc or other exception sets. Then the CSE uses could also rely upon exception sets tracked by the Global Heap.

Added large comment addressing this to the method header

Thanks for the comment -- my main concern was not how this can happen (though it is nice to now have specifics here), but how often it can happen.

As long as it's "rare" that different CSE defs have different exception sets then it doesn't matter much whether you disqualify uses eagerly or wait until you've seen them all, as it is unlikely you'll ever hit the case I describe where you miss CSEing some use because you saw some other more constraining use first.

But maybe it's worth mentioning that the approach you take here may not find the "maximal" set of CSEs in some rare cases.

AndyAyersMS · 2018-09-28T21:03:05Z

src/jit/optcse.cpp

+                            if (theConservNormVN != desc->defConservNormVN)
+                            {
+                                // This candidate has defs with differing conservative normal VNs, mark it with NoVN
+                                desc->defConservNormVN = ValueNumStore::NoVN; // record the marker for differing VNs


This could also set NO_CSE and then continue, right?

No, This is existing code that is there for rangecheck elimation. (I believe)

I renamed the existing field to `defConservNormVN' and maintained its existing behavior.

Here is the old existing field definition in compiler.h
ValueNum defConservativeVN; // if all def occurrences share the same conservative value

Might be useful to mention how this can happen and why even if so, the candidate is still a viable CSE.

AndyAyersMS · 2018-09-28T21:09:59Z

src/jit/optcse.cpp

+                                //
+                                if (desc->defExcSetCurrent !=
+                                    theLiberalExcSet) // no update is needed when these are the same VN
+                                {


I think the code reads better if you don't use these end of line comments.

Also it would be nice to try and bubble all the fail/continue cases upwards so that we don't get so deeply nested, eg structure the code as the loop-equivalent of early return style, eg:

if (something disqualifying 1) { continue; } if (something disqualifying 2) { continue; } // success !

Not sure exactly you want here. As far as I can tell this isn't a straight forward change.

For now maybe just move the comments.

I think there may be simpler/cleaner ways to express the code too, but I'm ok leaving it as is for now.

AndyAyersMS

Haven't looked at the valuenum.cpp changes yet in much detail.

briansull · 2018-09-28T22:24:29Z

src/jit/optcse.cpp

                    // use to fetch the same value with no reload, so we can safely propagate that
                    // conservative VN to this use.  This can help range check elimination later on.
-                    cse->gtVNPair.SetConservative(defConservativeVN);
+                    cse->gtVNPair.SetConservative(theConservativeVN);


This is the existing code that depends upon theConservativeVN getting set to NoVN when there are differing conservative values.

I see now. Thanks.

New method that add exception sets: fgValueNumberAddExceptionSet - fgValueNumberAddExceptionSetForIndirection - fgValueNumberAddExceptionSetForDivision - fgValueNumberAddExceptionSetForOverflow - fgValueNumberAddExceptionSetForCkFinite Refactoring work added methods: VNEvalShouldFold - method to decide if constant folding should be performed EvalUsingMathIdentity - Uses math identities to simplify value number exoressions Renamed fgValueNumberHelperMethVNFunc to fgValueNumberJitHelperMethodVNFunc Removed the suffixes from the method headers comments

briansull · 2018-10-05T22:56:40Z

@AndyAyersMS PTAL
@dotnet/jit-contrib PTAL

AndyAyersMS

Looked at valuenum.cpp now too.

briansull · 2018-10-05T23:37:26Z

@dotnet-bot retest Windows_NT x64 Release CoreFX Tests

briansull · 2018-10-10T18:07:21Z

Fixes #8648

4creators reviewed Sep 25, 2018

View reviewed changes

src/jit/valuenum.cpp Outdated Show resolved Hide resolved

4creators reviewed Sep 25, 2018

View reviewed changes

src/jit/valuenum.cpp Show resolved Hide resolved

mikedn reviewed Sep 26, 2018

View reviewed changes

src/jit/valuenum.cpp Outdated

if (typ == TYP_INT)

{

INT32 kVal;

Copy link

mikedn Sep 26, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Move inside ifs below. There are more cases below.

mikedn reviewed Sep 26, 2018

View reviewed changes

briansull force-pushed the vn-add-exception-sets branch from 5a8d9f3 to 1fc0560 Compare September 28, 2018 18:35

AndyAyersMS reviewed Sep 28, 2018

View reviewed changes

briansull commented Sep 28, 2018

View reviewed changes

briansull force-pushed the vn-add-exception-sets branch from 1fc0560 to 3e5b2a9 Compare October 1, 2018 23:03

briansull added 2 commits October 5, 2018 15:08

Added method header comments in optcse describing the algorithm

a552cfe

briansull force-pushed the vn-add-exception-sets branch from 3e5b2a9 to a552cfe Compare October 5, 2018 22:40

AndyAyersMS reviewed Oct 5, 2018

View reviewed changes

briansull merged commit 22a9229 into dotnet:master Oct 9, 2018

briansull mentioned this pull request Oct 10, 2018

[WIP] Support for tracking Exception Sets with ValueNumbers #19284

Closed

briansull mentioned this pull request Oct 10, 2018

Enable the tests associated with the fixed issue 8648 #20347

Merged

Conversation

briansull commented Sep 25, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mikedn Sep 26, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

briansull Sep 27, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

briansull commented Sep 25, 2018 •

edited

Loading

mikedn Sep 26, 2018 •

edited

Loading

briansull Sep 27, 2018 •

edited

Loading

briansull Sep 27, 2018 •

edited

Loading

briansull commented Sep 28, 2018 •

edited

Loading

briansull commented Sep 28, 2018 •

edited

Loading

briansull Sep 28, 2018 •

edited

Loading