Loop elimination in presence of invariant expression

[kunalspathak]

Below example is taken from Microbenchmarks

public void ObjrefValueTypeObj()
{
  for (int i = 0; i < InnerIterationCount200000; i++)
    orvt = (FooORVT)o;
}

Here the only expression is an invariant inside the loop and can bring it outside and eliminate the loop. Instead we generate this on x64:

G_M64166_IG03:
       48BA08581DBA14020000 mov      rdx, 0x214BA1D5808
       488B32               mov      rsi, gword ptr [rdx]
       48BA60D79AC3F77F0000 mov      rdx, 0x7FF7C39AD760
       483916               cmp      qword ptr [rsi], rdx
       7412                 je       SHORT G_M64166_IG05
						;; bbWeight=4    PerfScore 22.00
G_M64166_IG04:
       488BD6               mov      rdx, rsi
       48B960D79AC3F77F0000 mov      rcx, 0x7FF7C39AD760
       E870B392FF           call     CORINFO_HELP_UNBOX
						;; bbWeight=1    PerfScore 1.50
G_M64166_IG05:
       48B8E0571DBA14020000 mov      rax, 0x214BA1D57E0
       488B38               mov      rdi, gword ptr [rax]
       4883C708             add      rdi, 8
       4883C608             add      rsi, 8
       E886370A5F           call     CORINFO_HELP_ASSIGN_BYREF
       E881370A5F           call     CORINFO_HELP_ASSIGN_BYREF
       FFC3                 inc      ebx
       3B1D5133DAFF         cmp      ebx, dword ptr [reloc classVar[0xc39ac8f8]]
       7CA9                 jl       SHORT G_M64166_IG03

[GrabYourPitchforks]

The InnerIterationCount200000 field is a read+write static field. There's a comment in the microbenchmarks source that the field should not be marked read-only, but I don't know why it's important for those tests. Whatever. :)

Anyway, I imagine that the JIT could compute the ref once outside the loop, but I think it would still need to dereference it every iteration as part of the loop condition. The reason for this is that the loop itself makes a method call to the unbox helper, and I think most compilers pessimistically assume that such methods could have side effects. One potential side effect could be mutating the stored static value.

[adamsitnik]

There's a comment in the microbenchmarks source that the field should not be marked read-only, but I don't know why it's important for those tests.

I added the comment when I was porting all benchmarks from xunit-performance to BenchmarkDotNet and I was told to not change any of the logic of the ported benchmarks. I think that as of today we should most probably just rewrite these benchmarks without using any loops but validating that they are not optimized by a JIT to a const.

In this case, the benchmark could be just:

public object ObjrefValueTypeObj() => orvt = (FooORVT)o;

[kunalspathak]

I think most compilers pessimistically assume that such methods could have side effects. One potential side effect could be mutating the stored static value.

I think that is a valid assumption if there are calls to user code. But in this case, it is calling the JIT helper and perhaps it will be known beforehand that we are not updating the stored static value.

[GrabYourPitchforks]

The castclass instruction can end up calling user code. Take exception filters as an example:

public static class Program {
    private static int _loopCount = 10000;
    
    public static void Main() {
        try {
            DoIt(42); // not a string!
        } catch when (ResetStatic())
        {
        }
    }
    
    private static bool ResetStatic()
    {
        _loopCount = 20000;
        return false;
    }
    
    private static void DoIt(object o)
    {
        Console.WriteLine($"Start of DoIt: _loopCount = {_loopCount}"); // prints 10000
        try
        {
            for (int i = 0; i < _loopCount; i++)
            {
                string s = (string)o;
            }
        } finally
        {
            Console.WriteLine($"End of DoIt: _loopCount = {_loopCount}"); // prints 20000
        }
    }
}

[kunalspathak]

Interesting. Thanks for sharing the example.

[AndyAyersMS]

@kunalspathak which part do you think is invariant ?

We generally assume statics can be changed by other threads so the static read of o and anything derived from it are not loop invariant., and likewise for InnerIterationCount200000. So the helper call properties aren't the primary blockers for loop optimization.

Stores to statics can be observed by other threads so can't be sunk out of the loop. So the only hoistable computations in this loop are the constants and the fetching of orvt's address.

This all changes for readonly statics since they can't be safely modified after their corresponding class constructors have completed.

If we marked o as readonly static then the jit would likely eliminate the type test and call to unbox (at least once the class init had run); if we marked InnerIterationCount200000 as readonly the jit would propagate the constant value into the loop exit test.

[kunalspathak]

which part do you think is invariant ?

To begin with, my impression was that none of the loop index variable's value participate in the expression inside for-loop, the entire expression orvt = (FooORVT)o; could have been hoisted outside and hence no loop is needed. Of course, this is after we ensure that accessing InnerIterationCount200000 doesn't change the static value. In this case, it is returning the primitive value (and not executing any code such as getter), so it should be ok to assume that change its value won't have any impact on value of o that we are trying to assign. But I get that other threads can change o and hence the end effect with and without hoisting it out of the loop will differ.

If we marked o as readonly static then the jit would likely eliminate the type test and call to unbox (at least once the class init had run);

I don't see this happening currently.
public readonly static Object o = (Object)new FooORVT();

if we marked InnerIterationCount200000 as readonly the jit would propagate the constant value into the loop exit test.

I don't see this happening as well.
public readonly static int InnerIterationCount200000 = 200000;

Edit: It is in the loop exit test, but basically i didn't see any difference after adding readonly for both those variables.

[kunalspathak]

Another minor thing I noticed for ARM64 is when we are about to call CORINFO_HELP_UNBOX we re-populate x0 with same value.

G_M65201_IG03:
        D2859C01          movz    x1, #0x2ce0
        F2A20001          movk    x1, #0x1000 LSL #16
        F2C02981          movk    x1, #332 LSL #32
        F9400034          ldr     x20, [x1]
        F9400281          ldr     x1, [x20]
        D2987200          movz    x0, #0xc390
        F2A6D420          movk    x0, #0x36a1 LSL #16
        F2CFFFA0          movk    x0, #0x7ffd LSL #32
        EB00003F          cmp     x1, x0
        540000C0          beq     G_M65201_IG05
						;; bbWeight=4    PerfScore 42.00
G_M65201_IG04:
        AA1403E1          mov     x1, x20
        D2987200          movz    x0, #0xc390
        F2A6D420          movk    x0, #0x36a1 LSL #16
        F2CFFFA0          movk    x0, #0x7ffd LSL #32
        97FF5CC1          bl      CORINFO_HELP_UNBOX
						;; bbWeight=1    PerfScore 3.00

[AndyAyersMS]

To see the impact of readonly statics you typically need to either look at tier1 code, restructure the code so it forces cctors to run before you jit the method you're looking at, or if you're using PMI for diffs, try passing --cctors (works sometimes) to get class constructors run early.

[kunalspathak]

To see the impact of readonly statics you typically need to either look at tier1 code, restructure the code so it forces cctors to run before you jit the method you're looking at, or if you're using PMI for diffs, try passing --cctors (works sometimes) to get class constructors run early.

Now I see it. Thanks!

[AndyAyersMS]

@kunalspathak I think everything here is working as expected (modulo hoisting of large constants). If you agree, please close. Otherwise let's pin down where you think we are missing out.