[clang] pointer subtraction should use ptrtoaddr rather than ptrtoint

[bababuck]

Not sure this is an issue or not, but seems incorrect from what I was able to gather.

From the C-specification,

Pointer subtraction works by subtracting p1’s numeric value from p3’s, and dividing by target object size. The two pointer arguments should point into the same array.

My understanding is that pointer subtraction should return the number of elements between the two pointers. From this, it follows that the provenance of the pointer should not be considered, and thus a ptrtoaddr instruction should be used.

However, clang currently lowers pointer subtraction using ptrtoint.

#include <stdint.h>
#include <stddef.h>

ptrdiff_t foot(int8_t *a, int8_t *b) {
  return a - b;
}

./bin/clang -O2 -S -emit-llvm -o ptr.ll ptr.c

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none)
define dso_local noundef i64 @foot(ptr noundef %a, ptr noundef %b) local_unnamed_addr #0 {
entry:
  %sub.ptr.lhs.cast = ptrtoint ptr %a to i64
  %sub.ptr.rhs.cast = ptrtoint ptr %b to i64
  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
  ret i64 %sub.ptr.sub
}  

[llvmbot]

@llvm/issue-subscribers-clang-codegen

Author: Ryan Buchner (bababuck)

Not sure this is an issue or not, but seems incorrect from what I was able to gather.

From the C-specification,

Pointer subtraction works by subtracting p1’s numeric value from p3’s, and dividing by target object size. The two pointer arguments should point into the same array.

My understanding is that pointer subtraction should return the number of elements between the two pointers. From this, it follows that the provenance of the pointer should not be considered, and thus a ptrtoaddr instruction should be used.

However, clang currently lowers pointer subtraction using ptrtoint.

#include <stdint.h>
#include <stddef.h>

ptrdiff_t foot(int8_t *a, int8_t *b) {
  return a - b;
}

./bin/clang -O2 -S -emit-llvm -o ptr.ll ptr.c

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none)
define dso_local noundef i64 @<!-- -->foot(ptr noundef %a, ptr noundef %b) local_unnamed_addr #<!-- -->0 {
entry:
  %sub.ptr.lhs.cast = ptrtoint ptr %a to i64
  %sub.ptr.rhs.cast = ptrtoint ptr %b to i64
  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
  ret i64 %sub.ptr.sub
}  

[keinflue]

I can't find the quote in any of the important C standard drafts. Draft N3220 adjacent to C23 says in §6.5.7:

When two pointers are subtracted, both shall point to elements of the same array object, or one past
the last element of the array object; the result is the difference of the subscripts of the two array
elements.

[keinflue]

I think the quote is from https://www.gnu.org/software/c-intro-and-ref/manual/html_node/Pointer-Arithmetic.html (?).

As you quoted, this continues with

The two pointer arguments should point into the same array.

which really isn't a "should" but a "must".

[bababuck]

Thanks for the response, and for the proper sources (you were correct about my source). Are two pointers from the same array guaranteed to have the same provenance? If so then the use of either ptrtoint or ptrtoaddr should be equivalent in this case, though to me ptrtoaddr makes more sense semantically.

[keinflue]

I am still learning how provenance is implemented in LLVM so I might be completely wrong here, but I tested the following test case:

int* f(int* x, int* y)
{
    long i = y - x;
    long xi = (long)x;
    return (int*)(xi + i*sizeof(int));
}

from this opt produces

define dso_local noundef ptr @f(ptr noundef readnone captures(none) %x, ptr noundef readnone returned captures(ret: address, provenance) %y) local_unnamed_addr #0 {
entry:
  ret ptr %y
}
attributes #0 = { mustprogress nofree norecurse nosync nounwind willreturn memory(none) }

If I change ptrtoint for the pointer subtraction to ptrtoaddr, then I get instead

define dso_local noundef ptr @f(ptr noundef %x, ptr noundef captures(address) %y) local_unnamed_addr #0 {
entry:
  %sub.ptr.lhs.cast = ptrtoaddr ptr %y to i64
  %sub.ptr.rhs.cast = ptrtoaddr ptr %x to i64
  %0 = ptrtoint ptr %x to i64
  %sub.ptr.sub = sub i64 %0, %sub.ptr.rhs.cast
  %add = add i64 %sub.ptr.sub, %sub.ptr.lhs.cast
  %1 = inttoptr i64 %add to ptr
  ret ptr %1
}
attributes #0 = { mustprogress nofree norecurse nosync nounwind willreturn memory(none) }

This looks worse to me. The first optimization seems valid, because x and y must have same provenance for being pointers into the same array as required by y - x. Therefore the pointer returned by the function must have the same provenance as well, meaning that it must return y exactly. That is my understanding at least.

[bababuck]

Was able to dig into it some more, and in the second case the optimization isn't made (EarlyCSEPAss) the cast instruction (long)x is still treated as a ptrtoint, so in the following, the %sub.ptr.rhs.cast = ptrtoaddr ptr %x to i64 ...%sub.ptr.rhs.cast = ptrtoaddr ptr %x to i64...%add = add i64 %0, %sub.ptr.sub sequence cannot be folded via the add(sub(X, Y), Y) -> X idiom.

define dso_local ptr @f(ptr noundef %x, ptr noundef %y) #0 {
entry:
  %sub.ptr.lhs.cast = ptrtoaddr ptr %y to i64
  %sub.ptr.rhs.cast = ptrtoaddr ptr %x to i64
  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
  %sub.ptr.div = sdiv exact i64 %sub.ptr.sub, 4
  %0 = ptrtoint ptr %x to i64
  %add = add i64 %0, %sub.ptr.sub
  %1 = inttoptr i64 %add to ptr
  ret ptr %1
}

I don't have anything to draw from this, just wanted to understand the behavior you mentioned.