Ranged-for loop with _LIBCPP_ABI_BOUNDED_ITERATORS does not optimize runtime checks

[davidben]

When enabling bounded iterators, it seems Clang cannot optimize them out of a ranged-for loop. Here's a simple function that just sums over a span with a ranged-for loop, sum1, as well as a corresponding hand-written iterator loop, sum2.
https://godbolt.org/z/WqsPKdEoa

The left output, without _LIBCPP_ABI_BOUNDED_ITERATORS has no runtime checks, and Clang is even able to vectorize the loop. The right output, with _LIBCPP_ABI_BOUNDED_ITERATORS contains runtime checks with, in turn, impede the optimization.

Cause

I teased apart what __bounded_iter was doing. This is the assertion in question:

  // Return whether the given iterator is in the bounds of this __bounded_iter.
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool __in_bounds(_Iterator const& __iter) const {
    return __iter >= __begin_ && __iter < __end_;
  }

I've extracted that into a minimal sum3 function (same godbolt link), and that seems to reveal the problem. While Clang can prove that iter >= begin, it can't prove that iter < end. I suspect this is because iterator loops look like iter != end, not iter < end. In order to prove that iter < end, it must also know that begin <= end. Otherwise it's possible that iter was ahead of end to start with.

Indeed, if I add that assertion to the top, in sum4 (same godbolt again), Clang pays for a different undesirable runtime check outside the loop, but then figures it out! So fixing #78784 may have further benefits, if the analysis is extended further.

Alternative fix

Another way Clang could have figured it out is if we used iter != end instead of iter < end for the safety assertion. That's actually what Chromium's checked iterator does. However, libc++ cannot do this because it doesn't check operator+, etc., only operator*. It is possible for __current_ to overflow well past __end_ before we do the check.

I think libc++ should bounds-check operator+ too. First, once __current_ has advanced past __end_, we may have already hit undefined behavior because pointer arithmetic is locked to the allocation. So the check in operator* may be too late anyway. Second, #78771 describes a place where libc++'s memmove specialization breaks its own hardening checks! Since memmove specialization is pretty valuable, I think it's best to fix #78771 by bounds-checking operator+ and making sure the specialization takes triggers it early enough.

Now, once operator+ is bounds-checked, __bounded_iter can rely on __begin_ <= __current_ <= __end_. That means the safety check need only be __current_ != __end_, which should be more easily optimized out.

(CC @danakj)

[davidben]

Incidentally, __bounded_iter actually checks begin <= end in its constructor:

  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 explicit __bounded_iter(
      _Iterator __current, _Iterator __begin, _Iterator __end)
      : __current_(__current), __begin_(__begin), __end_(__end) {
    _LIBCPP_ASSERT_INTERNAL(__begin <= __end, "__bounded_iter(current, begin, end): [begin, end) is not a valid range");
  }

I suspect this was originally done in support of this optimization. Presumably, when libc++ first added bounded iterators, someone tested that it was optimizable in ranged-for loops. However, since that test, libc++ has started categorizing its asserts, and this one was excluded from hardened mode, breaking the optimization! It only runs in debug mode.

Indeed, if I switch from hardened mode to debug mode, the check is optimized out. But we, instead, pay for a different pointless check that the span's size is non-negative, #78784.
https://godbolt.org/z/Kv5qdPs6b

I think, in principle, excluding that check is correct. This assertion is about whether the container is in good shape, not whether the caller has used iterators correctly. The container can maintain its invariants more efficiently without the iterator double-checking. But libc++ currently relies on this double-check to mask a different problem. :-)

[ldionne]

CC @var-const @fhahn

[fhahn]

This issue here is that this gets lowered to something like the code below. Note %add.ptr.i = getelementptr inbounds i32, ptr %s.coerce0, i64 %s.coerce1. getelementptr indices are interpreted as signed offsets, so if the number of elements in the span is signed negative in 64 bit, then the offset actually gets subtracted instead of added.

With an assumption that the number of elements is signed positive, LLVM will be able to remove the checks: https://llvm.godbolt.org/z/5G74nzbTx

Would it be possible to add such an assumption on the number of elements?

declare void @llvm.assume(i1)

define dso_local noundef i32 @_Z4sum1NSt3__14spanIKiLm18446744073709551615EEE(ptr %s.coerce0, i64 %s.coerce1) local_unnamed_addr #0 personality ptr null {
entry:
  %add.ptr.i = getelementptr inbounds i32, ptr %s.coerce0, i64 %s.coerce1
  br label %for.cond

for.cond:                                         ; preds = %_ZNKSt3__114__bounded_iterIPKivEdeB8se180000Ev.exit, %entry
  %__begin1.sroa.0.0 = phi ptr [ %s.coerce0, %entry ], [ %incdec.ptr.i, %_ZNKSt3__114__bounded_iterIPKivEdeB8se180000Ev.exit ]
  %sum.0 = phi i32 [ 0, %entry ], [ %add, %_ZNKSt3__114__bounded_iterIPKivEdeB8se180000Ev.exit ]
  %cmp.i.not = icmp eq ptr %__begin1.sroa.0.0, %add.ptr.i
  br i1 %cmp.i.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:                                 ; preds = %for.cond
  ret i32 %sum.0

for.body:                                         ; preds = %for.cond
  %cmp.not.i.i = icmp uge ptr %__begin1.sroa.0.0, %s.coerce0
  %cmp2.i.i = icmp ult ptr %__begin1.sroa.0.0, %add.ptr.i
  %0 = and i1 %cmp.not.i.i, %cmp2.i.i
  br i1 %0, label %_ZNKSt3__114__bounded_iterIPKivEdeB8se180000Ev.exit, label %cond.false.i

cond.false.i:                                     ; preds = %for.body
  tail call void @llvm.trap()
  unreachable

_ZNKSt3__114__bounded_iterIPKivEdeB8se180000Ev.exit: ; preds = %for.body
  %1 = load i32, ptr %__begin1.sroa.0.0, align 4
  %add = add nsw i32 %1, %sum.0
  %incdec.ptr.i = getelementptr inbounds i32, ptr %__begin1.sroa.0.0, i64 1
  br label %for.cond
}