Signed division performed even when values are provably non-negative

[stephentoub]

Repro:

static int Result(int i)
{
    if (i < 4) return 0;
    return i / 4;
}

This results in:

; Method Program:<<Main>$>g__Result|0_0(int):int (FullOpts)
G_M000_IG01:                ;; offset=0x0000

G_M000_IG02:                ;; offset=0x0000
       cmp      ecx, 4
       jge      SHORT G_M000_IG05

G_M000_IG03:                ;; offset=0x0005
       xor      eax, eax

G_M000_IG04:                ;; offset=0x0007
       ret      

G_M000_IG05:                ;; offset=0x0008
       mov      eax, ecx
       sar      eax, 31
       and      eax, 3
       add      eax, ecx
       sar      eax, 2

G_M000_IG06:                ;; offset=0x0015
       ret      
; Total bytes of code: 22

but as the JIT can prove that the i used in i / 4 isn't negative, so presumably it should be able to emit the code as if:

static int Result(int i)
{
    if (i < 4) return 0;
    return (int)((uint)i / 4);
}

were instead used? And it results in:

; Method Program:<<Main>$>g__Result|0_0(int):int (FullOpts)
G_M000_IG01:                ;; offset=0x0000

G_M000_IG02:                ;; offset=0x0000
       cmp      ecx, 4
       jge      SHORT G_M000_IG05

G_M000_IG03:                ;; offset=0x0005
       xor      eax, eax

G_M000_IG04:                ;; offset=0x0007
       ret      

G_M000_IG05:                ;; offset=0x0008
       mov      eax, ecx
       shr      eax, 2

G_M000_IG06:                ;; offset=0x000D
       ret      
; Total bytes of code: 14

[ghost]

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

Issue Details

---

Repro:

static int Result(int i)
{
    if (i < 4) return 0;
    return i / 4;
}

This results in:

; Method Program:<<Main>$>g__Result|0_0(int):int (FullOpts)
G_M000_IG01:                ;; offset=0x0000

G_M000_IG02:                ;; offset=0x0000
       cmp      ecx, 4
       jge      SHORT G_M000_IG05

G_M000_IG03:                ;; offset=0x0005
       xor      eax, eax

G_M000_IG04:                ;; offset=0x0007
       ret      

G_M000_IG05:                ;; offset=0x0008
       mov      eax, ecx
       sar      eax, 31
       and      eax, 3
       add      eax, ecx
       sar      eax, 2

G_M000_IG06:                ;; offset=0x0015
       ret      
; Total bytes of code: 22

but as the JIT can prove that the i used in i / 4 isn't negative, so presumably it should be able to emit the code as if:

static int Result(int i)
{
    if (i < 4) return 0;
    return (int)((uint)i / 4);
}

were instead used? And it results in:

; Method Program:<<Main>$>g__Result|0_0(int):int (FullOpts)
G_M000_IG01:                ;; offset=0x0000

G_M000_IG02:                ;; offset=0x0000
       cmp      ecx, 4
       jge      SHORT G_M000_IG05

G_M000_IG03:                ;; offset=0x0005
       xor      eax, eax

G_M000_IG04:                ;; offset=0x0007
       ret      

G_M000_IG05:                ;; offset=0x0008
       mov      eax, ecx
       shr      eax, 2

G_M000_IG06:                ;; offset=0x000D
       ret      
; Total bytes of code: 14

Author:	stephentoub
Assignees:	-
Labels:	area-CodeGen-coreclr
Milestone:	-

[yemtron]

As just an observer here, it seems JIT can prove the sign of i at runtime but still would need to be evaluated unless you're being explicit such as the the (uint) casting you are doing. Perhaps JIT could optimize using branch prediction in some way at i < 4, but I believe still at some point JIT would have to evaluate the sign of an int type.

[MichalPetryka]

but as the JIT can prove that the i used in i / 4 isn't negative

It's already supposed to:

runtime/src/coreclr/jit/morph.cpp

Lines 8510 to 8517 in f2e4ddf

	// Convert DIV to UDIV if both op1 and op2 are known to be never negative
	if (!gtIsActiveCSE_Candidate(tree) && varTypeIsIntegral(tree) && op1->IsNeverNegative(this) &&
	op2->IsNeverNegative(this))
	{
	assert(tree->OperIs(GT_DIV));
	tree->ChangeOper(GT_UDIV, GenTree::PRESERVE_VN);
	return fgMorphSmpOp(tree, mac);
	}

[AndyAyersMS]

op->IsNeverNegative() is currently not flow-sensitive, so it doesn't reflect the fact that something was learned by branching that happened before the divide. Value numbering has the same limitation... we'd need to catch this in assertion prop.

[EgorBo]

While #94347 fixes your example, we might still have a few cases where we won't optimize, e.g. when JIT expands X mod CNS too early or currently we won't do this for long because needed assertions exist only for int32 atm (they were added for bound checks) - I'll try to improve it