Bounds checks not eliminated when compared to Min

[stephentoub]

Repro:

internal class Program
{
    private static void Main(string[] args) { }

    private static int Get1(int i, int size, int[] items)
    {
        if ((uint)i < (uint)size && (uint)i < (uint)items.Length)
        {
            return items[i];
        }

        return -1;
    }

    private static int Get2(int i, int size, int[] items)
    {
        if ((uint)i < Math.Min((uint)size, (uint)items.Length))
        {
            return items[i];
        }

        return -1;
    }

    private static int Get3(int i, int size, int[] items)
    {
        if ((uint)i < ((uint)size < (uint)items.Length ? (uint)size : (uint)items.Length))
        {
            return items[i];
        }

        return -1;
    }
}

Get1 eliminates the bounds check, but incurs both comparisons against size and items.Length, resulting in two cmp/ja pairs:

; Method Program:Get1(int,int,int[]):int (FullOpts)
G_M000_IG01:                ;; offset=0x0000

G_M000_IG02:                ;; offset=0x0000
       cmp      ecx, edx
       jae      SHORT G_M000_IG04

G_M000_IG03:                ;; offset=0x0004
       mov      eax, dword ptr [r8+0x08]
       cmp      eax, ecx
       ja       SHORT G_M000_IG06

G_M000_IG04:                ;; offset=0x000C
       mov      eax, -1

G_M000_IG05:                ;; offset=0x0011
       ret      

G_M000_IG06:                ;; offset=0x0012
       mov      eax, ecx
       mov      eax, dword ptr [r8+4*rax+0x10]

G_M000_IG07:                ;; offset=0x0019
       ret      
; Total bytes of code: 26

Get2 and Get3 both combine the size/items.Length checks via a cmov, but incur a bounds check, resulting in a cmov/cmp/jb and cmp/jae:

; Method Program:Get3(int,int,int[]):int (FullOpts)
G_M000_IG01:                ;; offset=0x0000
       sub      rsp, 40

G_M000_IG02:                ;; offset=0x0004
       mov      r10d, dword ptr [r8+0x08]
       cmp      r10d, edx
       cmovbe   edx, r10d
       cmp      ecx, edx
       jb       SHORT G_M000_IG05

G_M000_IG03:                ;; offset=0x0013
       mov      eax, -1

G_M000_IG04:                ;; offset=0x0018
       add      rsp, 40
       ret      

G_M000_IG05:                ;; offset=0x001D
       cmp      ecx, r10d
       jae      SHORT G_M000_IG07
       mov      eax, ecx
       mov      eax, dword ptr [r8+4*rax+0x10]

G_M000_IG06:                ;; offset=0x0029
       add      rsp, 40
       ret      

G_M000_IG07:                ;; offset=0x002E
       call     CORINFO_HELP_RNGCHKFAIL
       int3     
; Total bytes of code: 52

Seems if the JIT could recognize that the bounds check could be eliminated, then Get2/Get3 could eliminate the extra cmp/jae.

[dotnet-policy-service]

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

[EgorBo]

So far doesn't look trivial, but should be doable

On an unrelated note:

for patterns like

if ((uint)i < (uint)size && (uint)i < (uint)items.Length)

we can only legally convert it to cmov if items.Length's dereference comes first, otherwise it is not legal

[stephentoub]

we can only legally convert it to cmov if items.Length's dereference comes first, otherwise it is not legal

Out of curiosity, why is that? If it's because items could be null and thus it could trigger an exception, what are the side effects of the first comparison that would be visible otherwise?

[EgorBo]

we can only legally convert it to cmov if items.Length's dereference comes first, otherwise it is not legal

Out of curiosity, why is that? If it's because items could be null and thus it could trigger an exception, what are the side effects of the first comparison that would be visible otherwise?

Yep, basically x < y && x < z(side-effect) the side-effect should not be evaluated if x >= y. While cmov implies that all side effects are evaluated up-front.

Hence it is better to put the side effect first if you want branchless. Same in C++: https://godbolt.org/z/r3rnqTvz6

[stephentoub]

What is the side effect to be concerned about with if ((uint)i < (uint)size && (uint)i < (uint)items.Length) ? Even if items were null and thus resulted in an exception, the rest of the expression doesn't have any visible side effects.

Also, though, while it'd nice to convert such an expression, I think the first step would just be eliminating the bounds check when it's instead explicitly written as if ((uint)i < Math.Min((uint)size, (uint)items.Length)) or the like.

[EgorBo]

What is the side effect to be concerned about with if ((uint)i < (uint)size && (uint)i < (uint)items.Length) ? Even if items were null and thus resulted in an exception, the rest of the expression doesn't have any visible side effects.

I probably mis-understand you, but if i is >size, then we just give up and not evaluate items.Length, hence, no exception? (if we don't convert it to branchless).

Btw, if you just save the length to a local, then your first example converts into branchless:

    private static int Get1(int i, int size, int[] items)
    {
        int len = items.Length;
        if ((uint)i < (uint)size && (uint)i < (uint)len)
        {
            return items[i];
        }
        return -1;
    }

; Assembly listing for method Program:Get1(int,int,int[]):int (FullOpts)
            stp     fp, lr, [sp, #-0x10]!
            mov     fp, sp
            ldr     w3, [x2, #0x08]
            cmp     w0, w1
            ccmp    w0, w3, c, lo
            blo     G_M56046_IG04
            movn    w0, #0
            ldp     fp, lr, [sp], #0x10
            ret     lr
G_M56046_IG04:
            add     x1, x2, #16
            ldr     w0, [x1, w0, UXTW #2]
            ldp     fp, lr, [sp], #0x10
            ret     lr
; Total bytes of code 52

Only on arm64, though (we intentionally give on x64 there)

[stephentoub]

then we just give up and not evaluate items.Length, hence, no exception?

Ah, sure, in my head I was thinking of the Math.Min version.

Only on arm64, though (we intentionally give on x64 there)

How come?

[EgorBo]

How come?

The logic accounts for each architecture’s conditional‐instruction support: ARM64 provides many conditional operations, while x64 relies only on CMOV (which can’t handle complex patterns efficiently). Fortunately, this logic automatically switches to use APX when available—though, to my knowledge, no x64 CPU on the market today actually supports APX.

runtime/src/coreclr/jit/optimizebools.cpp

Lines 1654 to 1668 in c048ff0

	#elif defined(TARGET_AMD64)
	// todo-xarch-apx: when we have proper CPUID (hardware) support, we can switch the below from an OR
	// condition to an AND, for now, `JitConfig.JitEnableApxIfConv` will drive whether the optimization
	// trigger or not
	// else if ((compOpportunisticallyDependsOn(InstructionSet_APX) || JitConfig.JitEnableApxIfConv()) &&
	// optBoolsDsc.optOptimizeCompareChainCondBlock())
	else if (JitConfig.EnableApxConditionalChaining() && !optSwitchDetectAndConvert(b1, true) &&
	optBoolsDsc.optOptimizeCompareChainCondBlock())
	{
	// The optimization will have merged b1 and b2. Retry the loop so that
	// b1 and b2->bbNext can be tested.
	change = true;
	retry = true;
	numCond++;
	}

[stephentoub]

But we use cmov in M2 and M3. Are we being overly cautious, is M2/M3 less efficient in x64, or am I missing the connection?