JIT: Strength reduction only done with native sized int

[BoyBaykiller]

Only when the iteration variable is a native sized int does it do strength reduction.

// https://godbolt.org/z/hdTeGEeE1
int TestNint(int* data, int count)
{
    int sum = 0;
    for (nint i = 0; i < count; i++)
    {
        sum += data[i];
    }

    return sum;
}

int TestInt(int* data, int count)
{
    int sum = 0;
    for (int i = 0; i < count; i++)
    {
        sum += data[i];
    }

    return sum;
}

G_M63938_IG04:  ;; offset=0x000E
       add      eax, dword ptr [rsi]
       add      rsi, 4
       dec      rcx
       jne      SHORT G_M63938_IG04

vs

G_M29388_IG03:  ;; offset=0x000C
       movsxd   rdi, ecx
       add      eax, dword ptr [rsi+4*rdi]
       inc      ecx
       cmp      ecx, edx
       jl       SHORT G_M29388_IG03

[dotnet-policy-service]

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

[jakobbotsch]

I suspect we bail here:

runtime/src/coreclr/jit/scev.cpp

Lines 1679 to 1748 in b54c5d5

	//------------------------------------------------------------------------
	// AddRecMayOverflow:
	// Check if an add recurrence may overflow inside the containing loop.
	//
	// Parameters:
	// addRec - The add recurrence
	// signedBound - Whether to check using signed (true) or unsigned (false) bounds.
	// assumptions - Assumptions about the containing loop.
	//
	// Returns:
	// True if the add recurrence may overflow and wrap around. False if we were
	// able to prove that it cannot.
	//
	// Remarks:
	// May return true conservatively.
	//
	bool ScalarEvolutionContext::AddRecMayOverflow(ScevAddRec* addRec,
	bool signedBound,
	const SimplificationAssumptions& assumptions)
	{
	if (assumptions.NumBackEdgeTakenBound == 0)
	{
	return true;
	}
	if (!addRec->TypeIs(TYP_INT))
	{
	return true;
	}
	// In general we are interested in proving that the add recurrence does not
	// cross the minimum or maximum bounds during the iteration of the loop:
	//
	// For signed bounds (sext): sext(a + b) != sext(a) + sext(b) if a + b crosses -2^31 or 2^31 - 1.
	// For unsigned bounds (zext): zext(a + b) != zext(a) + zext(b) if a + b crosses 0 or 2^32 - 1.
	//
	// We need to verify this condition for all i < bound where a = start, b =
	// step + i.
	//
	// For now, we only handle the super duper simple case of unsigned bounds
	// with addRec = <L, 0, 1> and a TYP_INT bound.
	//
	if (signedBound)
	{
	return true;
	}
	int64_t startCns;
	if (addRec->Start->GetConstantValue(m_comp, &startCns) && (startCns != 0))
	{
	return true;
	}
	int64_t stepCns;
	if (!addRec->Step->GetConstantValue(m_comp, &stepCns) || (stepCns != 1))
	{
	return true;
	}
	for (unsigned i = 0; i < assumptions.NumBackEdgeTakenBound; i++)
	{
	Scev* bound = assumptions.BackEdgeTakenBound[i];
	if (bound->TypeIs(TYP_INT))
	{
	return false;
	}
	}
	return true;
	}

This function does not support sign extensions and it was never added because we only see zero extensions for the managed patterns. Also proving the necessary condition is not as easy as proving it for zero extensions.

[tannergooding]

In this case we should be able to check and take advantage of the "never negative" metadata we track, right? Or is this happening before we have that info available?

[jakobbotsch]

In this case we should be able to check and take advantage of the "never negative" metadata we track, right? Or is this happening before we have that info available?

There's nothing like that here since there are no arrays/spans, just raw pointers.
While it may look obvious that i is never negative, consider the fact that it wouldn't necessarily be the case for any of the 3 following loops:

    for (int i = -10; i < count; i++)
    {
        sum += data[i];
    }

    for (int i = 0; i <= count; i++)
    {
        sum += data[i];
    }

    for (int i = 0; i < count; i += 2)
    {
        sum += data[i];
    }

So somehow to prove that you need to consider all of i = 0, i < count and i++ simultaneously.

That is not to say that we cannot prove it -- in fact we prove a similar fact here:

runtime/src/coreclr/jit/inductionvariableopts.cpp

Lines 2359 to 2411 in 32a02c7

	// Now see if we have a bound that guarantees that we iterate fewer times
	// than the array/string's length.
	ValueNum arrLengthVN = m_comp->vnStore->VNForFunc(TYP_INT, VNF_ARR_LENGTH, addRecStartBase.GetLiberal());
	for (int i = 0; i < m_backEdgeBounds.Height(); i++)
	{
	Scev* bound = m_backEdgeBounds.Bottom(i);
	if (!bound->TypeIs(TYP_INT))
	{
	// Currently cannot handle bounds that aren't 32 bit.
	continue;
	}
	// In some cases VN is powerful enough to evaluate bound <
	// ARR_LENGTH(vn) directly.
	ValueNumPair boundVN = m_scevContext.MaterializeVN(bound);
	if (boundVN.GetLiberal() != ValueNumStore::NoVN)
	{
	ValueNum relop = m_comp->vnStore->VNForFunc(TYP_INT, VNF_LT_UN, boundVN.GetLiberal(), arrLengthVN);
	if (m_scevContext.EvaluateRelop(relop) == RelopEvaluationResult::True)
	{
	return true;
	}
	}
	// In common cases VN cannot prove the above, so try a little bit
	// harder. In this case we know the bound doesn't overflow
	// (conceptually the bound is an arbitrary precision integer and a
	// negative bound does not make sense).
	int64_t boundOffset;
	Scev* boundBase = bound->PeelAdditions(&boundOffset);
	boundOffset = static_cast<int32_t>(boundOffset);
	if (boundOffset >= 0)
	{
	// If we take the backedge >= the array length times, then we would
	// advance the addrec past the end.
	continue;
	}
	// Now try to prove that boundBase <= ARR_LENGTH(vn). Commonly
	// boundBase == ARR_LENGTH(vn) exactly, but it may also have a
	// dominating subsuming compare before the loop due to loop cloning.
	ValueNumPair boundBaseVN = m_scevContext.MaterializeVN(boundBase);
	if (boundBaseVN.GetLiberal() != ValueNumStore::NoVN)
	{
	ValueNum relop = m_comp->vnStore->VNForFunc(TYP_INT, VNF_LE, boundBaseVN.GetLiberal(), arrLengthVN);
	if (m_scevContext.EvaluateRelop(relop) == RelopEvaluationResult::True)
	{
	return true;
	}
	}
	}

[tannergooding]

There's nothing like that here since there are no arrays/spans, just raw pointers.

Hmmmm... We're definitely getting that information at some point. Note the difference between these two: https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AXEBDAzgWwB8ABAJgEYBYAKGIGYACAVwDtdsAzGBshgYQYBvGg1EMAliwwMAKjFwYAcpIwAKFQCoGAE2wZsaCVIaRWGAJQixw6mLtHpuJvgYBeBgAYA3FfsNf9hzQDKosKhJunl4RADwmEGbR4gDUyZa2fkIBmQxOLsnupsYA9AwoPhl+AL402WLEAOy5zhV2NdQB4XIKAJJS6lJauvqG4UUWATY54XmR3nWiCwxBUCHh4nNJDHHjSanpOVM5YrMF8WYMpeVL7UuNzfitYu1VQA===

    int TestNint(int* data, int count)
    {
        int sum = 0;
        
        for (nint i = 0; i < count; i++)
        {
            sum += count / 4;
        }

        return sum;
    }

    int TestInt(int* data, int count)
    {
        int sum = 0;
        
        for (int i = 0; i < count; i++)
        {
            sum += count / 4;
        }

        return sum;
    }

Which produces:

C.TestNint(Int32*, Int32)
    L0000: xor eax, eax
    L0002: movsxd rcx, r8d
    L0005: test rcx, rcx
    L0008: jle short L0020
    L000a: mov edx, r8d
    L000d: sar edx, 0x1f
    L0010: and edx, 3
    L0013: add edx, r8d
    L0016: sar edx, 2
    L0019: add eax, edx
    L001b: dec rcx
    L001e: jne short L0019
    L0020: ret

C.TestInt(Int32*, Int32)
    L0000: xor eax, eax
    L0002: test r8d, r8d
    L0005: jle short L0014
    L0007: mov ecx, r8d
    L000a: shr ecx, 2
    L000d: add eax, ecx
    L000f: dec r8d
    L0012: jne short L000d
    L0014: ret

You can note that the former (likely due to the combination of casts and other scenarios) no longer tracks is never negative (for count) and so it emits a signed division sequence (sar, and, add, sar), while the latter is able to track is never negative and instead emits an unsigned division sequence (shr).

So either we're getting that information "past" where the loop analysis could take advantage of it; or instead we're just not checking the relevant metadata we already track for VN, assertion prop, and other areas.

Doing pre-conditions like if (count < 0) { return 0; } are also enough to force such an assertion to be tracked for the TestNint case.

[jakobbotsch]

There's nothing like that here since there are no arrays/spans, just raw pointers.

Hmmmm... We're definitely getting that information at some point. Note the difference between these two: https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AXEBDAzgWwB8ABAJgEYBYAKGIGYACAVwDtdsAzGBshgYQYBvGg1EMAliwwMAKjFwYAcpIwAKFQCoGAE2wZsaCVIaRWGAJQixw6mLtHpuJvgYBeBgAYA3FfsNf9hzQDKosKhJunl4RADwmEGbR4gDUyZa2fkIBmQxOLsnupsYA9AwoPhl+AL402WLEAOy5zhV2NdQB4XIKAJJS6lJauvqG4UUWATY54XmR3nWiCwxBUCHh4nNJDHHjSanpOVM5YrMF8WYMpeVL7UuNzfitYu1VQA===

int TestNint(int* data, int count)
{
    int sum = 0;
    
    for (nint i = 0; i < count; i++)
    {
        sum += count / 4;
    }

    return sum;
}

int TestInt(int* data, int count)
{
    int sum = 0;
    
    for (int i = 0; i < count; i++)
    {
        sum += count / 4;
    }

    return sum;
}

Which produces:

C.TestNint(Int32*, Int32)
L0000: xor eax, eax
L0002: movsxd rcx, r8d
L0005: test rcx, rcx
L0008: jle short L0020
L000a: mov edx, r8d
L000d: sar edx, 0x1f
L0010: and edx, 3
L0013: add edx, r8d
L0016: sar edx, 2
L0019: add eax, edx
L001b: dec rcx
L001e: jne short L0019
L0020: ret

C.TestInt(Int32*, Int32)
L0000: xor eax, eax
L0002: test r8d, r8d
L0005: jle short L0014
L0007: mov ecx, r8d
L000a: shr ecx, 2
L000d: add eax, ecx
L000f: dec r8d
L0012: jne short L000d
L0014: ret

You can note that the former (likely due to the combination of casts and other scenarios) no longer tracks is never negative (for count) and so it emits a signed division sequence (sar, and, add, sar), while the latter is able to track is never negative and instead emits an unsigned division sequence (shr).

So either we're getting that information "past" where the loop analysis could take advantage of it; or instead we're just not checking the relevant metadata we already track for VN, assertion prop, and other areas.

Doing pre-conditions like if (count < 0) { return 0; } are also enough to force such an assertion to be tracked for the TestNint case.

It is not hard to know that count is non-negative. We get that directly from the zero-trip test created by loop inversion, and count is invariant.

To do strength reduction we need to prove that i is non-negative and that sign extending it is equivalent to a 64-bit strength reduced computation. That's harder.

[tannergooding]

Could you elaborate a bit?

If it's non-negative, then there is no "sign-extension"; rather it is definitively a zero-extension. Given that, it should be "trivial" to for us to know that count must be a positive non-zero value within the loop and that decrementing is feasible because it meets all the same requirements as the array iteration scenario.

That is, given [0, int.MaxValue), we know that any operation that doesn't overflow will produce a bitwise identical result. We are incrementing by one, so we cannot overflow past MaxValue if starting from 0; so therefore inversing the operation so that we start from count and decrementing by one also cannot overflow past 0. -- And this holds for any upperBound <= (int.MaxValue - incrementAmount) scenario to a lowerBound >= (0 + decrementAmount) scenario, or vice-versa

[jakobbotsch]

Again, this is not about count, it is about i and more specifically about the add recurrence of the sign extension of i. Strength reducing the address computed by the indexing of that sign extension requires proving that we compute the same address if we do everything as 64 bit computations. That requires simultaneously deriving facts about the starting value, monotonicity, and assertions of the bounds.
That's possible but not implemented because we do not see the pattern for array and span loops.

[jakobbotsch]

That is, given [0, int.MaxValue), we know that any operation that doesn't overflow will produce a bitwise identical result. We are incrementing by one, so we cannot overflow past MaxValue if starting from 0; so therefore inversing the operation so that we start from count and decrementing by one also cannot overflow past 0. -- And this holds for any upperBound <= (int.MaxValue - incrementAmount) scenario to a lowerBound >= (0 + decrementAmount) scenario, or vice-versa

And yes, it looks somewhat like this, except done by symbolic reasoning and combining the various facts given by different sources. That's what StaysWithinManagedObject I linked above is doing for a slightly different case.

[tannergooding]

I guess I'm still not following.

There's no sign extension for i either. It's lower bound is 0 and the upper bound (exclusive) is count which is known non-negative, so therefore i must also be non-negative and fits into the same bucket (with the same upper/lowerBound and increment/decrement logic and conditions).

I definitely get why many cases might be complex. However, this scenario does light up for array/span and so I would expect this one in particular to be trivial given the same invariants we infer from array/span limits also exist here for count and therefore no index accessed would ever differ for the pointer or byref arithmetic case.

Basically anything we're doing with arrays/spans we should be able to apply the same to unmanaged pointers (or even byref arithmetic) given the same overall logic. That is, arrays/spans are mostly limited by needing to ensure the bounds checking is maintained. Pointers and byrefs don't have the same because they are unsafe and don't do such checks. So it should be even simpler as there is no "StaysWithinObject" to check, we only care about the other invariants around arithmetic staying the same (which given our existing VN info around is never negative and ranges, should be feasible, particularly as we already use that for some array/span cases).

In other words, given we already do this for array/span, I'd expect that we can easily piggy back off that same logic for pointers and we're just artificially limiting ourselves due to only checking for Array/Span. I'd expect array/span case to just be some extra checks on top of the pointer case, since its the same stuff just with a bounds checking side effect involved

[jakobbotsch]

There are no specific checks for array/spans. The strength reduction is general and works on arbitrary SCEV expressions that includes a symbolic representation for the add recurrences that can vary through loops (like i).

What is different is that the IR produced for indexing arrays and spans use zero extensions, not sign extensions. They can use zero extensions because they happen after bounds checks that already guaranteed that the index is non-negative.

Proving that a zero extended 32-bit add recurrence is equivalent to a 64-bit add recurrence is simpler than the sign extended version. Since it's the case we see for array/span indexing, it was the case we targeted.