Loop invariant is not deduced in C++-iterator-style loop over pointers

[davidben]

In the following loop, the compiler should be able to optimize out the assert.

struct SpanAsPointers {
    int *begin, *end;
};

int sum_span_as_pointers(SpanAsPointers s) {
    int *begin = s.begin;
    int *end = s.end;
    __builtin_assume(begin <= end);

    int sum = 0;
    int *iter = begin;
    while (iter != end) {
        assert(iter < end);
        sum += *iter;
        iter++;
    }
    return sum;
}

See this link for a runnable example, and a longer discussion on why the invariant is true: https://godbolt.org/z/ad5P4d5M5

Also in that link is something interesting: Clang does figure out the invariant when we use integers instead of pointers! It just doesn't apply the same analysis to pointers for some reason.

This is the missing compiler piece needed to solve #101370.

(CC @ldionne @var-const @danakj)

[fhahn]

I think what's missing here is the information that both begin and end are multiples of the pointer step size in the loop (4 in this case due to using int*).

Without that information, I think we currently have to assume that incrementing iter may not exactly reach end. If char* is used instead the check gets removed: https://godbolt.org/z/43rK885zK

For this particular case, one way to add this information would be to add align 4 to the arguments, but that might not work in all cases. Then all that remains is to update https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp#L1010 to make use of alignment info.

[davidben]

Oh good point. I hadn't thought of that dependency. Although it is UB in C to create unaligned pointers, so I think that is a fair assumption for the compiler to make. Otherwise things like pointer subtraction kinda go haywire.

[nikic]

Clang assumes that references are aligned, but not raw pointers. You can do a git grep "reinterpret_cast.*-1" on the LLVM codebase to get an idea of why that is :)

[fhahn]

Ah yes. If I read https://en.cppreference.com/w/cpp/language/reinterpret_cast correctly, I guess those casts would violate 5), but has too much widespread use to be too aggressive here. This also pessimizes other parts of libc++, e.g. not being able to compute trip counts for things like std::find. There an attribute might help.

[danakj]

Could perhaps clang assume pointers are aligned when it encounters arithmetic with them?

[davidben]

You can do a git grep "reinterpret_cast.*-1" on the LLVM codebase to get an idea of why that is :)

FWIW, it's not that many of them. A SentinelPointer<TargetRegisterClass>() that internally aligns things is probably more readable than reinterpret_cast<TargetRegisterClass *>(-1). I do see some reinterpret_cast<void*>(-1) instances which might complicate things... do you all ever expect one pointer type's sentinel to compare against another one's?

Alternatively, we could use reinterpret_cast<T*>(alignof(std::max_align_t)). Gross but would be compatible across types.

Could perhaps clang assume pointers are aligned when it encounters arithmetic with them?

That's doubly supported by the standard. Not only must pointers always be aligned, but if you ever write ptr + n, it is UB unless ptr points to some object that has room for n, and a valid object must be aligned. Likewise, if you ever write ptr1 - ptr2, ptr1 and ptr2 must point within the same array, which further implies they're compatibly aligned. (If they weren't compatibly aligned, you can't even divide by sizeof(T) without chopping bits off. If you believe pointer subtraction chop bits off, you can't even transform begin + (end - begin) to end.)

In the context of #101370, the analogs to __builtin_assume(begin <= end) can probably be rewritten as __builtin_assume(end - begin >= 0). That naturally establishes the "must be in the same buffer" precondition.

For completeness, there is another thorny corner of pointers and alignment, which is taking the address of fields in a packed structs. There's a warning for it (though it's incomplete; see #97091), but if the compiler ever lowers references to pointers without tagging their (lack of) alignment, that might do weird things.

[davidben]

Oh the alignment discussion is interesting though. It means I can at least try to fix #101370 for vector<uint8_t>. And then hopefully once Clang has a story for deducing the alignment precondition, it will either translate to vector<int> or be easily adaptable. I'll see if I can get that to work.

[fhahn]

One option would be to use std::asume_aligned<>() on the iterators to add an assumption about the alignment (should be safe for start/end of vectors. It will need a few improvements in LLVM to better make use of the info, but should be doable

[fhahn]

Created #108961 to create assumptions for begin/end pointers of std::vector

[danakj]

Will there be separate versions of that PR for std::array and std::basic_string, etc? In Chromium, I think I will just do this inside the CheckedContiguousIterator (our version of __bounded_iter) when storing the member pointers. Could libc++ do the same or is there a reason why it's done this way?

[davidben]

@danakj I don't think the others needed those assumptions, at least for basic ranged-for loops. vector is tricky because the bounded iterator's end does not match the end that the programmer checks against. (vector storing pointers instead of one pointer and sizes might also impact things. I'm not sure.)

[davidben]

I guess the issue in this bug is about pointers, because the compiler can't see that end >= start. But the more complex std::vector issue was because of the end and cap thing, and this was somewhat related? Though I'm playing around with vector for the char case now and that optimization impediment may be a bit more complex.

[danakj]

It would be good to check as well basic_string<char16_t> or char32_t, as they also have end vs cap?

[davidben]

No, it's just vector whose iterators were bounded by end. basic_string did not promise iterator stability when you append up to the capacity, so we went with the tighter bound. basic_string also does not store a triple of pointers.

Though I'm playing around with vector for the char case now and that optimization impediment may be a bit more complex

Figured that out. Will upload a PR shortly. It is indeed the alignment issue discussed here and then needing to relate the pointers together from the other bug.

[davidben]

Actually, the alignment thing seems to have some connection to #108600, playing around with it. (Though I haven't fully figured out what's up there.) So maybe it'll be useful generally? Not sure.

There is a slight risk doing it generally in that the compiler is apparently bad at discarding unnecessary assumes. But hopefully ordering assumptions are safe?

[davidben]

@fhahn Actually, is alignment enough? Let's suppose sizeof(T) is 8 and alignof(T) is 4. Then it's totally possible that iter skips over end:

struct T { int x, y; };

T arr[8];
T *iter = arr;
// Very, very, very sketchy but it is still aligned!
// As long as we don't actually use `end`, it's OK, I think.
T *end = (T*)(&arr[4].y);
// Our initial precondition still holds:
assert(iter <= end);
// I believe you're allowed to check `iter != end`
// without problems.
while (iter != end) {
  // Sadly the compiler cannot infer this because it's not true!
  assert(iter < end);
  ++iter;
}

To solve this, I think the programmer needs to write something that tells the compiler that iter and end both point within the same array. (void)(end - iter) should be fine. So I guess this means that __bounded_iter should compute and throw away these subtractions?

What if, instead of alignment annotations, we taught Clang to reason about pointer arithmetic preconditions like this?

[davidben]

Interestingly, Clang does actually already assume that, when you write end - iter, that end and iter are compatibly spaced, otherwise this could not be optimized:
https://godbolt.org/z/7W1qGb1r5

Looks like this comes from the sdiv exact in the LLVM IR output. But I suspect this isn't carried all the way into other assumptions about the pointers. It also looks like LLVM loses the precondition that end and start point within the same buffer, because it drops to ptrtoint before emitting pointer subtraction. (I assume this and provenance woes are why the optimized LLVM IR still has arithmetic.)