[JIT] Assertion Prop Issues and Ideas

[AndyAyersMS]

Tracking issue for work and ideas about Assertion Prop.

Recent work

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

• JIT: extend copy prop to local fields #74384
• Hash the AssertionDsc struct for faster lookup #72700
• Skip assertion list look ups where unnecessary #73142
• JIT: Do not propagate some constants #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.

• optAssertionProp_Ind should eliminate GTF_EXCEPT better. #32248
• JIT: morph late canonicalization of assign foils local assertion prop #12098
• JIT: look at cost impact of assertion dup detection #10592
• JIT: possibly revisit how we set assertion prop table size #10591
• JIT: type assertion prop doesn't know declared types for args or locals #9057
• JIT: Assertion prop does unnecessary bitvector copying #7552
• JIT: Assertion prop should generate fewer array-bound complement assertions #7551
• [RyuJIT] Further cleanup and hardening of assertion prop #6395
• JIT - slow generated code on Release for iterating simple array of struct #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).

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

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]

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

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.

• JIT: extend copy prop to local fields #74384
• Hash the AssertionDsc struct for faster lookup #72700
• Skip assertion list look ups where unnecessary #73142
• JIT: Do not propagate some constants #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.

• optAssertionProp_Ind should eliminate GTF_EXCEPT better. #32248
• JIT: morph late canonicalization of assign foils local assertion prop #12098
• JIT: look at cost impact of assertion dup detection #10592
• JIT: possibly revisit how we set assertion prop table size #10591
• JIT: type assertion prop doesn't know declared types for args or locals #9057
• JIT: Assertion prop does unnecessary bitvector copying #7552
• JIT: Assertion prop should generate fewer array-bound complement assertions #7551
• [RyuJIT] Further cleanup and hardening of assertion prop #6395
• JIT - slow generated code on Release for iterating simple array of struct #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]

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]

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 #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.