[JIT] Assertion Prop Issues and Ideas

AndyAyersMS commented 2 years ago

Tracking issue for work and ideas about Assertion Prop.

Recent work

Not a complete list -- will fill this out over time.

Existing open issues

Not a complete list -- will fill this out over time. Also need to go back through these to see how many are no longer relevant.

Ideas

Local Assertion Prop

Extend local prop to work cross-block. If a block's successor has no other predecessors, the successor can inherit the assertion state. This extends local prop to work across join-free regions.

we would want to process blocks in morph in reverse postorder
we would need to save/restore assertion states if a block has multiple successors

I worked up a simple-minded prototype of this that just handles the case where the predecessor is BBJ_NONE and successor is join free. It revealed some annoying interaction with VN and CSE, in particular, if we have code like:

;; BB01
  = *this
...
;; BB02 (linear flow from BB01
  (big tree, say runtime lookup, with *this)
...
;; BBxx (not linear flow from BB02)
  (big tree, say runtime lookup, with *this, nominal CSE of the tree in BB02)

Then locally propping a non-null this into BB02 breaks CSE, because the two big trees now have different exception sets (this may in fact happen already if the first tree is in BB01).

Some possible remedies:

In general, VN doesn't deal with conditionally generated facts, though one can sometimes play games by introducing artificial definitions before building SSA (or after, if you can update SSA). For instance, in BB01 we could introduce a synthetic non-null def of this below the intial indir, then all CSE uses would see the "non null this" VN. This idea of fake defs is powerful and could possibly be leveraged for many other things. But it might be too costly for us.
Run AP before CSE and allow CSE to filter out overly broad exception sets when supported by assertions. I'm not really sure why we run CSE before AP anyways.
Don't let local prop clear exception bits, just use the null/non-null prop assertions to impact control flow.

Enhance Assertion Kill/Gen Logic

Currently in local prop, we kill assertions for unaliased locals. This includes killing promoted local asserts when a parent struct is assigned to, and killing parent struct asserts when a promoted field is assigned to. However, this is pessimistic in the common case where a field is assigned a value it already has, eg redundant zeroing of fields:

struct S {... int f; ...}

S s = new S();   // generates s == ZERROBJ
s.f = 0;         // kills s == ZEROBJ

In general, we don't do "gen" for promoted structs and their fields with the same thoroughness that we do "kill" so there is an asymmetry here. Arguably a ZEROOBJ on a promoted struct should inspire zero assertions for all its fields. But we may be better off not generating these quasi-redundant assertions and instead teach the lookup logic to understand parent/child relationships.

I have a prototype for this but will wait for #74384 to finalize first.

Flow dependent prop for address-taken locals

In many cases we may be able to prove that address-takenness is not applicable to a span of local defs and uses, eg the last "use" is the one that causes exposure (say a struct passed by ref).

category:planning theme:assertion-prop skill-level:expert cost:medium impact:medium

dotnet-issue-labeler[bot] commented 2 years ago

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

AndyAyersMS commented 2 years ago

FYI @dotnet/jit-contrib. Probably lots to add here...

ghost commented 2 years ago

Tagging subscribers to this area: @JulieLeeMSFT, @jakobbotsch See info in area-owners.md if you want to be subscribed.

Issue Details

Tracking issue for work and ideas about Assertion Prop. ### Recent work Not a complete list -- will fill this out over time. * https://github.com/dotnet/runtime/pull/74384 * https://github.com/dotnet/runtime/pull/72700 * https://github.com/dotnet/runtime/pull/73142 * https://github.com/dotnet/runtime/pull/70378 ### Existing open issues Not a complete list -- will fill this out over time. Also need to go back through these to see how many are no longer relevant. * https://github.com/dotnet/runtime/issues/32248 * https://github.com/dotnet/runtime/issues/12098 * https://github.com/dotnet/runtime/issues/10592 * https://github.com/dotnet/runtime/issues/10591 * https://github.com/dotnet/runtime/issues/9057 * https://github.com/dotnet/runtime/issues/7552 * https://github.com/dotnet/runtime/issues/7551 * https://github.com/dotnet/runtime/issues/6395 * https://github.com/dotnet/runtime/issues/4659 ### Ideas #### Local Assertion Prop Extend local prop to work cross-block. If a block's successor has no other predecessors, the successor can inherit the assertion state. This extends local prop to work across join-free regions. * we would want to process blocks in morph in reverse postorder * we would need to save/restore assertion states if a block has multiple successors I worked up a simple-minded prototype of this that just handles the case where the predecessor is BBJ_NONE and successor is join free. It revealed some annoying interaction with VN and CSE, in particular, if we have code like: ``` ;; BB01 = *this ... ;; BB02 (linear flow from BB01 (big tree, say runtime lookup, with *this) ... ;; BBxx (not linear flow from BB02) (big tree, say runtime lookup, with *this, nominal CSE of the tree in BB02) ``` Then locally propping a non-null `this` into `BB02` breaks CSE, because the two big trees now have different exception sets (this may in fact happen already if the first tree is in BB01). Some possible remedies: * In general, VN doesn't deal with conditionally generated facts, though one can sometimes play games by introducing artificial definitions before building SSA (or after, if you can update SSA). For instance, in BB01 we could introduce a synthetic non-null def of this below the intial indir, then all CSE uses would see the "non null `this`" VN. This idea of fake defs is powerful and could possibly be leveraged for many other things. But it might be too costly for us. * Run AP before CSE and allow CSE to filter out overly broad exception sets when supported by assertions. I'm not really sure why we run CSE before AP anyways. * Don't let local prop clear exception bits, just use the null/non-null prop assertions to impact control flow. #### Enhance Assertion Kill/Gen Logic Currently in local prop, we kill assertions for unaliased locals. This includes killing promoted local asserts when a parent struct is assigned to, and killing parent struct asserts when a promoted field is assigned to. However, this is pessimistic in the common case where a field is assigned a value it already has, eg redundant zeroing of fields: ``` struct S {... int f; ...} S s = new S(); // generates s == ZERROBJ s.f = 0; // kills s == ZEROBJ ``` In general, we don't do "gen" for promoted structs and their fields with the same thoroughness that we do "kill" so there is an asymmetry here. Arguably a ZEROOBJ on a promoted struct should inspire zero assertions for all its fields. But we may be better off not generating these quasi-redundant assertions and instead teach the lookup logic to understand parent/child relationships. I have a prototype for this but will wait for #74384 to finalize first. #### Flow dependent prop for address-taken locals In many cases we may be able to prove that address-takenness is not applicable to a span of local defs and uses, eg the last "use" is the one that causes exposure (say a struct passed by `ref`).

Author:	AndyAyersMS
Assignees:	-
Labels:	`area-CodeGen-coreclr`, `untriaged`
Milestone:	-

SingleAccretion commented 2 years ago

I'm not really sure why we run CSE before AP anyways.

The primary benefit of running assertion propagation after CSE is the ability to take advantage of the refined conservative VNs.

AndyAyersMS commented 2 years ago

I'm not really sure why we run CSE before AP anyways.

The primary benefit of running assertion propagation after CSE is the ability to take advantage of the refined conservative VNs.

Ah. you'd think I would have remembered https://github.com/dotnet/runtime/issues/45658. At any rate we don't actually have to do the CSE up front, just know that it is possible. For instance, we could recognize CSE candidates but defer optimizing and then see which CSEs AP benefits from before we figure out which ones we should (or now, have to) do.

We already have GTF_MAKE_CSE for the interaction of hoisting and CSE -- though somewhat oddly we don't look for this in our CSE profitability analysis. Seems like we should at least keep track of cases where hosting thinks we should CSE but CSE disagrees.

dotnet / runtime