LLVM fails to remove bounds check on loops over pointers

[AngelicosPhosphoros]

I expected that LLVM would remove bounds check on this code:

#include <cstddef>

void do_checks(const int* begin, const size_t len){
    size_t idx = 0;
    const auto end = begin + len;
    for (const int* it = begin; it!=end; ++it, ++idx){
        if (idx < len){
            // Do something useful
        }
        else
        {
            throw 5;
        }
    }
}

But it doesn't:

@_ZTIi = external dso_local constant i8*

define dso_local void @_Z9do_checksPKim(i32* readnone %0, i64 %1) local_unnamed_addr #0 !dbg !15 {
  call void @llvm.dbg.value(metadata i32* %0, metadata !27, metadata !DIExpression()), !dbg !34
  call void @llvm.dbg.value(metadata i64 %1, metadata !28, metadata !DIExpression()), !dbg !34
  call void @llvm.dbg.value(metadata i64 0, metadata !29, metadata !DIExpression()), !dbg !34
  call void @llvm.dbg.value(metadata !DIArgList(i32* %0, i64 %1), metadata !30, metadata !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_constu, 4, DW_OP_mul, DW_OP_plus, DW_OP_stack_value)), !dbg !34
  call void @llvm.dbg.value(metadata i32* %0, metadata !32, metadata !DIExpression()), !dbg !35
  call void @llvm.dbg.value(metadata i64 0, metadata !29, metadata !DIExpression()), !dbg !34
  %3 = icmp eq i64 %1, 0, !dbg !36
  br i1 %3, label %4, label %5, !dbg !38

4:                                                ; preds = %5, %2
  ret void, !dbg !39

5:                                                ; preds = %2
  %6 = shl nsw i64 %1, 2, !dbg !38
  %7 = add i64 %6, -4, !dbg !38
  %8 = lshr exact i64 %7, 2, !dbg !38
  %9 = icmp ult i64 %8, %1, !dbg !38
  call void @llvm.dbg.value(metadata i32* undef, metadata !32, metadata !DIExpression()), !dbg !35
  call void @llvm.dbg.value(metadata i64 undef, metadata !29, metadata !DIExpression()), !dbg !34
  br i1 %9, label %4, label %10, !dbg !40

10:                                               ; preds = %5
  %11 = tail call i8* @__cxa_allocate_exception(i64 4) #2, !dbg !42
  %12 = bitcast i8* %11 to i32*, !dbg !42
  store i32 5, i32* %12, align 16, !dbg !42, !tbaa !45
  tail call void @__cxa_throw(i8* %11, i8* bitcast (i8** @_ZTIi to i8*), i8* null) #3, !dbg !42
  unreachable, !dbg !42
}

declare dso_local i8* @__cxa_allocate_exception(i64) local_unnamed_addr

declare dso_local void @__cxa_throw(i8*, i8*, i8*) local_unnamed_addr

declare void @llvm.dbg.value(metadata, metadata, metadata) #1

attributes #0 = { mustprogress uwtable "frame-pointer"="none" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { nofree nosync nounwind readnone speculatable willreturn }
attributes #2 = { nounwind }
attributes #3 = { noreturn }

godbolt link

It affects real-world code like this:

size_t idx = 0;
for (auto& ref : v){
    v.at(idx);
    ++idx;
}

or in Rust

for (i, v) in arr.enumerate(){
    let prev_chunk = &arr[..i];
}

[rotateright]

Looks like we are missing 2 transforms in IR (instcombine):

1. Convert opposing shifts around an add to shift+mask
2. Fold a compare of an add+and with a low-bit mask to a "X != 0"

[rotateright]

Reopened - this auto-closed based on the commit message, but didn't auto-reopen when the patch was reverted.

[AngelicosPhosphoros]

@rotateright Hi, thanks for your fix!
Your patch fixed i < v.size() but sirprisingly it still fails to remove i <= v.size()
godbolt

Should I reopen this issue or file new one?

[rotateright]

Please file another bug (and link back to this one for context). It's not clear to me at first glance what we need to do to fix it.

[AngelicosPhosphoros]

OK, thanks.