Delete dependent struct promotion/Improve CQ.

[sandreenko]

The dependent struct promotion was initially added as a workaround for illegal independent struct promotion cases that we found too late. The main reason for that was that we ran fgMarkAddressExposedLocals after fgPromoteStructs, so when we understood that a lclVar has addrTaken fields etc. it was too late to cancel the promotion.

After fgMarkAddressExposedLocals was cleaned and rewritten by @mikedn it became possible to move fgMarkAddressExposedLocals phase before fgPromoteStructs. It will allow us to remove dependent struct promotion and buggy code that deals with it (for example in fgMorphStructField). This will give us a better TP (because we get rid of many tracked variables that we do not fully utilize) and cleaner code.

Also, it is possible to improve our CQ by the way. I want to make the change that deletes dependent struct diff-free; in order to do that, I am planning to teach our JIT to work equally with dependent promoted and not-promoted fields.

If right now you disable dependent struct promotion you will see some diffs in System.Private.CoreLib, both improvements and regressions:

diff is an improvement. 
-10 : System.Private.CoreLib.dasm (0.00% of base)
31 total methods with size differences (27 improved, 4 regressed), 26200 unchanged.

The regressed methods are doing CSE or asserting propagation for dependent struct fields better.

The main improvement case is where we replace small LCL_FIELD with LCL_VAR for arguments and then do lvNormalizeOnLoad replacing LCL_VAR bool with CAST int<-bool<-int (LCL_VAR int); on x64 we generate 2 instruction when we promote such field:

       mov      eax, dword ptr [rbp-44H]
       movsx    rax, ax

when we do not do struct promotion for this struct we keep this field access as LCL_FIELD and generate only one instruction:

       movsx    rax, word  ptr [rbp-44H]

Does somebody remember case when we need to do this replacement?
https://github.com/dotnet/coreclr/blob/0aab97266ea6620a17a20804c7aebfcdbd37a5b0/src/jit/morph.cpp#L6017-L6027

I did not hit any asserts when I removed it but got some regressions (as well as expected improvements) because OptimizeConstCompare was not able to optimize EQ bool lcl_var, int const as it is able to optimize EQ cast int<-bool<-int (LCL_VAR int), int const. that can be easily fixed.

So my plan is to fix CQ/code size regression caused by dependent struct promotion step by step, then start to teach assertion propagation and CSE not to rely on lvPromote flag. As bonus it will allow us to do the same optimizations for struct fields that we can't promote now, for example if there are more than 4 fields in the struct but one is used often or in a loop.

Bonus: another case where we do a kind of dependent struct promotion is fgRetypeImplicitByRefArgs:

                // If the promotion is dependent, the promoted temp would just be committed
                // to memory anyway, so we'll rewrite its appearances to be indirections
                // through the pointer parameter, the same as we'd do for this
                // parameter if it weren't promoted at all (otherwise the initialization
                // of the new temp would just be a needless memcpy at method entry).
                bool undoPromotion = (lvaGetPromotionType(newVarDsc) == PROMOTION_TYPE_DEPENDENT) ||
                                     (varDsc->lvRefCnt(RCS_EARLY) <= varDsc->lvFieldCnt);

The right analysis for x64 should make decision for each field separately and for code size purposes should compare fieldDsc->lvRefCnt(RCS_EARLY) >= 2. Or at least varDsc->lvFieldCnt * 5 + varDsc->lvRefCnt(RCS_EARLY) < 4 * varDsc->lvRefCnt(RCS_EARLY) => varDsc->lvFieldCnt * 5 < 3 * varDsc->lvRefCnt(RCS_EARLY) that means that it is profitable to spend 5 instruction in the scratch block to copy each fields and then access them with 1 instruction instead of 4. However, if you change it now it will cause few regressions because CSE will work worse.

P.s. I was not able to do the description short and sweet, but hope it is readable.

category:cq
theme:structs
skill-level:expert
cost:extra-large
impact:large

[sandreenko]

PTAL @dotnet/jit-contrib

[mikedn]

I was not able to do the description short and sweet, but hope it is readable.

It's readable but it will take a while to digest all this 😄

For now a quick comment:

The main improvement case is where we replace small LCL_FIELD with LCL_VAR for arguments and then do lvNormalizeOnLoad replacing LCL_VAR bool with CAST int<-bool<-int (LCL_VAR int); on x64 we generate 2 instruction when we promote such field:

My cast operand containment PR should take care of this case. It's supposed to make the LCL_VAR reg optional. If it's in memory then codegen will combine the load and the cast into a single movzx/movsx.

[mikedn]

The main reason for that was that we ran fgMarkAddressExposedLocals after fgPromoteStructs, so when we understood that a lclVar has addrTaken fields etc. it was too late to cancel the promotion.

Are you sure that's the main reason? It's not clear to me why it was done like this to begin with. Hopefully there isn't some weird gotcha that we're yet to discover.

it became possible to move fgMarkAddressExposedLocals phase before fgPromoteStructs

I the first look this seemed like an unfortunate move but I suppose we can still make it work. I was hoping that sooner or later we will move morphing expressions such as IND(ADDR(LCL_VAR)) from morph to LocalAddressVisitor, that would have included replacing fields with promoted variables. If we reorder these 2 phases it means LocalAddressVisitor will generate LCL_FLD nodes for expressions such as FIELD(ADDR(LCL_VAR)) and later, after struct promotion, another traversal (morph most likely) will change LCL_FLD node into LCL_VAR nodes for promoted vars. Seems workable.

Does somebody remember case when we need to do this replacement?

Normalize on load is a bit of a pain in the back and seemingly a source of bugs (I think I've seen at least 2). It's not clear to me if it's truly needed in all cases when it is used. It may be needed for small int arguments passed in registers, where an actual load doesn't occur and I'm not sure if there's any guarantee that the caller extended the small int value to int. It doesn't seem necessary for address exposed small int variables, simply keeping the small int type of the LCL_VAR node should work.

There are some RA complications with LCL_VAR nodes having small int type when the variable itself is actually TYP_INT but that's another story.

then start to teach assertion propagation and CSE not to rely on lvPromote flag

How do those depend on lvPromoted? I don't remember seeing uses of this flag in the CSE/AssertionProp code.

The right analysis for x64 should make decision for each field separately and for code size purposes should compare fieldDsc->lvRefCnt(RCS_EARLY) >= 2 …

That does sound like a plan but I wonder how do you deal with the fact that you want to do promotion after LocalAddressVisitor yet count fields separately in LocalAddressVisitor. In general, implicit by ref args seem to be a bit of a problem because you first need to count the number of uses during a full traversal of the method and then actually morph them somehow in another full traversal.

[sandreenko]

The main reason for that was that we ran fgMarkAddressExposedLocals after fgPromoteStructs, so when we understood that a lclVar has addrTaken fields etc. it was too late to cancel the promotion.

Are you sure that's the main reason? It's not clear to me why it was done like this to begin with. Hopefully there isn't some weird gotcha that we're yet to discover.

It was the historical reason as I was told and LocalAddressVisitor::EscapeAddress sets most lvDoNotEnregister for lvPromote lclVars nowdays. We can extract a separate flag for PROMOTION_TYPE_DEPENDENT to make it clearer (like dotnet/coreclr#19223).

Does somebody remember case when we need to do this replacement?

Normalize on load is a bit of a pain in the back and seemingly a source of bugs (I think I've seen at least 2). It's not clear to me if it's truly needed in all cases when it is used. It may be needed for small int arguments passed in registers, where an actual load doesn't occur and I'm not sure if there's any guarantee that the caller extended the small int value to int. It doesn't seem necessary for address exposed small int variables, simply keeping the small int type of the LCL_VAR node should work.
There are some RA complications with LCL_VAR nodes having small int type when the variable itself is actually TYP_INT but that's another story.

Hm, we will need to find a test that shows why we need it.

then start to teach assertion propagation and CSE not to rely on lvPromote flag

How do those depend on lvPromoted? I don't remember seeing uses of this flag in the CSE/AssertionProp code.

It was not designed for this purpose, it is more like side-effect:

1. There is a size limit for trees that we try to optimize and the cost function prefer LCL_VAR over LCL_FIELD->ADDR->LCL_VAR, I will update this comment when I find where it is located.
2. Dependent promoted fields are tracked variables that are in SSA and it is what CSE and AssertionProp use.

[sandreenko]

The right analysis for x64 should make decision for each field separately and for code size purposes should compare fieldDsc->lvRefCnt(RCS_EARLY) >= 2 …

That does sound like a plan but I wonder how do you deal with the fact that you want to do promotion after LocalAddressVisitor yet count fields separately in LocalAddressVisitor. In general, implicit by ref args seem to be a bit of a problem because you first need to count the number of uses during a full traversal of the method and then actually morph them somehow in another full traversal.

Right now fgRetypeImplicitByRefArgs is executed when all counters are calculated, so we can use them. If we want to optimize it and do not do promotion in the first place (rather than undo and leave wasted lclVars for fields) we will be able to do that if we swap fgMarkAddressExposedLocals and fgPromoteStructs. In the ideal case fgPromoteStructs should be the only place that make decisions about fields promotions.

[mikedn]

Dependent promoted fields are tracked variables that are in SSA and it is what CSE and AssertionProp use.

Hmm, not quite. The usual reason why we end up with dependent promotion is due to lvDoNotEnregister being set. lvaSetVarAddrExposed sets it but it also sets lvAddrExposed which will "hide" these variables from SSA and all SSA-based optimizations.

Of course, it's possible for lvDoNotEnregister to be set without lvAddrExposed being also set. In the case of struct the most common reason for that is likely DNER_LocalField. This is also something we may want to review in the future, but it's a different story.

As far as LocalAddressVisitor is concerned, dependent promoted structs are address exposed and thus they are not optimization candidates. So it does seem that it makes a lot of sense to swap LocalAddressVisitor and struct promotion phases to avoid unnecessary promotion. I'm not sure I'd even bother with small diffs like

diff is an improvement. 
-10 : System.Private.CoreLib.dasm (0.00% of base)
31 total methods with size differences (27 improved, 4 regressed), 26200 unchanged.

if they're well understood.

[mikedn]

Normalize on load is a bit of a pain in the back and seemingly a source of bugs (I think I've seen at least 2).

Bugs related to normalize on load:

• RyuJIT spills 16 bit value but reloads as 32 bits in ARM32/x86 in release #10660 (basically you have to be careful when doing copy propagation not to substitute a normal lclvar with a "normalize on load" lclvar)
• RyuJIT: Mishandling of subrange assertion for rewritten call parameter #10925 (bad use of subrange assertions to drive "normalize on load" cast insertion?)
• RyuJIT: Missing zeroing of upper bits for small struct used in Volatile.Read #10941 (partially, we really shouldn't morph volatile indirs but doing it for local variables wouldn't normally cause problems, if it weren't for normalize on load)

It would be nice to get rid of that but it doesn't seem that easy.

[sandreenko]

Bugs related to normalize on load:
#10660 (basically you have to be careful when doing copy propagation not to substitute a normal lclvar with a "normalize on load" lclvar)
#10925 (bad use of subrange assertions to drive "normalize on load" cast insertion?)
#10941 (partially, we really shouldn't morph volatile indirs but doing it for local variables wouldn't normally cause problems, if it weren't for normalize on load)
It would be nice to get rid of that but it doesn't seem that easy.

Thanks for organizing this!

[briansull]

I merged mikedn full fix for #10660 - Normalize on Load

Fix normalize on load handling in assertion propagation dotnet/coreclr#21184

[mikedn]

After digging a bit more I discovered than in addition to bugs caused by load normalization there is also a strange interaction between load normalization and dependent promotion.

If a small int struct field is dependent promoted then the its stack location's size is exactly the size of the small int type, not 4 bytes like other small int lclvars. And such promoted struct fields are "normalize on load" so the lclvar node's type gets changed to TYP_INT. This results in 4 bytes being loaded from a 1 or 2 byte stack location.

       668955F8             mov      word  ptr [rbp-08H], dx ; V01.a
       8D5002               lea      edx, [rax+2]
       480FBFD2             movsx    rdx, dx
       668955FA             mov      word  ptr [rbp-06H], dx ; V01.b
       83C003               add      eax, 3
       480FBFC0             movsx    rax, ax
       668945FC             mov      word  ptr [rbp-04H], ax ; V01.c
       8B45F8               mov      eax, dword ptr [rbp-08H] ; reads both V01.a and V01.b
       480FBFC0             movsx    rax, ax
       8945F4               mov      dword ptr [rbp-0CH], eax

It works fine because the cast inserted by normalization clears the upper bits but it's kind of strange to see the JIT generating code that reads more bytes than needed. On an architecture that requires proper data alignment this would fail because the stack location may be only 1/2 byte aligned and the load size is 4 byte.

So one more reason to get rid of dependent promotion (and load normalization if possible).

[mikedn]

Going back to "normalize on load" and the need for the replacement: load normalization is used for method parameters, address exposed variables and promoted struct fields. Obviously, as far as this issue is concerned we only care about the last case - promoted struct fields. And here we have two cases:

• dependent promoted struct fields - these are supposed to disappear if this change is done so we don't need to be concerned with this case.
• independent promoted struct fields - this is what we care about and where things get interesting. If you have a small int promoted struct field why would you need "load normalization"? The lclvar associated with such a field should be a normal lclvar. That is, it should be normalize on store, not normalize on load. And if we do this then it's likely that we won't get regressions such as

       mov      eax, dword ptr [rbp-44H]
       movsx    rax, ax

Instead, it's possible that we'll actually get some improvements, because "normalize on store" tends to be better than "normalize on load" CQ wise.

[mikedn]

because "normalize on store" tends to be better than "normalize on load" CQ wise.

For example:

struct range { public byte begin, end; }

static int Test()
{
    range r = new range { begin = 1, end = 42 };
    int s = 0;
    for (; r.begin < r.end; r.begin = (byte)(r.begin + 1))
        s += r.begin;
    return s;
}

One may expect that this generates the exact same assembly as similar code that uses 2 byte local variables instead of the range struct. Yet the generated code is different (larger) in the struct case, exactly because promoted struct fields are normalize on load instead of normalize on store.

[AndyAyersMS]

Lots of good discussion here for follow-up, but likely post 3.0.