Pointer semantics in GIMPLE

[Krister Walfridsson]

On Thu, 20 Mar 2025, Richard Biener wrote:

>> Pointer arithmetic -- POINTER_DIFF_EXPR
>> ---------------------------------------
>> Subtracting a pointer q from a pointer p is done using POINTER_DIFF_EXPR.
>>   * It is UB if the difference does not fit in a signed integer with the
>>     same precision as the pointers.
>
> Yep.
>
>> This implies that an object's size must be less than half the address
>> space; otherwise, POINTER_DIFF_EXPR cannot be used to compute sizes in C.
>> But there may be additional restrictions. For example, compiling the
>> function:
>>
>>    void foo(int *p, int *q, int n)
>>    {
>>      for (int i = 0; i < n; i++)
>>        p[i] = q[i] + 1;
>>    }
>>
>> causes the vectorized code to perform overlap checks like:
>>
>>    _7 = q_11(D) + 4;
>>    _25 = p_12(D) - _7;
>>    _26 = (sizetype) _25;
>>    _27 = _26 > 8;
>>    _28 = _27;
>>    if (_28 != 0)
>>      goto <bb 11>;
>>    else
>>      goto <bb 12>;
>>
>> which takes the difference between two pointers that may point to
>> different objects. This suggests that all objects must fit within half the
>> address space.
>
> Interesting detail.  But yes, the above is either incorrect code (I didn't
> double-check) or this condition must hold.  For 64bit virtual address-space
> it likely holds in practice.  For 32bit virtual address-space it might not.
>
>> Question: What are the restrictions on valid address ranges and object
>> sizes?
>
> The restriction on object size is documented, as well as that objects
> may not cross/include 'NULL'.  Can you open a bugreport for the
> vectorizer overlap test issue above?  I think we want to track this and
> at least document the restriction (we could possibly add a target hook
> that can tell whether such a simplified check is OK).

PR119399


>> Issues
>> ------
>> The semantics I've described above result in many reports of
>> miscompilations that I haven't reported yet.
>>
>> As mentioned earlier, the vectorizer can use POINTER_PLUS_EXPR to generate
>> pointers that extend up to a vector length past the object (and similarly,
>> up to one vector length before the object in a backwards loop). This is
>> invalid if the object is too close to address 0 or 0xffffffffffffffff.
>>
>> And this out of bounds distance can be made arbitrarily large, as can be
>> seen by compiling the following function below for x86_64 with -O3:
>>
>> void foo(int *p, uint64_t s, int64_t n)
>> {
>>    for (int64_t i = 0; i < n; i++)
>>      {
>>        int *q = p + i * s;
>>        for (int j = 0; j < 4; j++)
>>         *q++ = j;
>>      }
>> }
>>
>> Here, the vectorized code add s * 4 to the pointer ivtmp_8 at the end of
>> each iteration:
>>
>>    <bb 5> :
>>    bnd.8_38 = (unsigned long) n_10(D);
>>    _21 = s_11(D) * 4;
>>
>>    <bb 3> :
>>    # ivtmp_8 = PHI <ivtmp_7(6), p_12(D)(5)>
>>    # ivtmp_26 = PHI <ivtmp_20(6), 0(5)>
>>    MEM <vector(4) int> [(int *)ivtmp_8] = { 0, 1, 2, 3 };
>>    ivtmp_7 = ivtmp_8 + _21;
>>    ivtmp_20 = ivtmp_26 + 1;
>>    if (ivtmp_20 < bnd.8_38)
>>      goto <bb 6>;
>>    else
>>      goto <bb 7>;
>>
>>    <bb 6> :
>>    goto <bb 3>;
>>
>> This means calling foo with a sufficiently large s can guarantee wrapping
>> or evaluating to 0, even though the original IR before optimization did
>> not wrap or evaluating to 0. For example, when calling foo as:
>>
>>    foo(p, -((uintptr_t)p / 4), 1);
>>
>> I guess this is essentially the same issue as PR113590, and could be fixed
>> by moving all induction variable updates to the latch.
>
> Yes.
>
> But if that
>> happens, the motivating examples for needing to handle invalid pointer
>> values would no longer occur. Would that mean smtgcc should adopt a more
>> restrictive semantics for pointer values?
>
> In principle yes, but PR113590 blocks this I guess.  Could smtgcc consider
> a SSA def to be happening only at the latest possible point, that is,
> "virtually"
> sink it to the latch?  (I realize when you have two dependent defs that can
> be moved together only such "virtual" sinking could be somewhat complicated)

I think it feels a bit strange (and brittle) to define the semantics by 
virtually sinking everything as much as possible. But isn't this sinking 
just another way of saying that the operation is UB only if the value is 
used? That is, we can solve this essentially the same way LLVM does with 
its deferred UB.

The idea is that POINTER_DIFF_EXPR, PLUS_EXPR, etc. are defined for all 
inputs, but the result is a poison value when it doesn't fit in the return 
type. Any use of a poison value is UB.

This is trivial to implement in smtgcc and would solve PR113590.

    /Krister