Missed constraint elimination opportunity in nested loop

[cynecx]

[[noreturn]] void abort();

#define AT(idx) do { if (idx >= len) { abort(); } arr } while(0)

[[inline]] static int* at(int* arr, unsigned len, unsigned idx) {
    if (idx >= len) {
        abort();
    }
    return arr + idx;
}

void monkey(int* arr, unsigned len) {
    // insertion sort like iteration
    for (unsigned i = 1; i < len; ++i) {
        for (unsigned k = i; k > 0; --k) {
            // k > 0 && k < len
            *at(arr, len, k) += 1;
        }
    }
}

Output

monkey(int*, unsigned int):                           # @monkey(int*, unsigned int)
        cmp     esi, 2
        jb      .LBB0_6
        mov     eax, esi
        mov     ecx, 1
.LBB0_2:                                # =>This Loop Header: Depth=1
        mov     rdx, rcx
.LBB0_3:                                #   Parent Loop BB0_2 Depth=1
        cmp     rdx, rax
        jae     .LBB0_7
        inc     dword ptr [rdi + 4*rdx]
        dec     rdx
        jne     .LBB0_3
        inc     rcx
        cmp     rcx, rax
        jne     .LBB0_2
.LBB0_6:
        ret
.LBB0_7:
        push    rax
        call    abort()@PLT

The bounds check idx < len inside the inner loop could've been eliminated but still remains.

https://godbolt.org/z/K4ccePe19 (c++ / clang)
https://godbolt.org/z/ddY8ehGG1 (llvm ir / opt)

Reduced llvm ir

define void @monkey(ptr %arr, i64 %len) {
  %1 = icmp ugt i64 %len, 1
  br i1 %1, label %2, label %exit

2:
  %3 = phi i64 [ 1, %0 ], [ %14, %13 ]
  br label %4

4:
  %5 = phi i64 [ %3, %2 ], [ %11, %7 ]
  %6 = icmp ult i64 %5, %len ; this is always true
  br i1 %6, label %7, label %abort

7:
  %8 = getelementptr inbounds i32, ptr %arr, i64 %5
  
  %9 = load i32, ptr %8, align 4
  %10 = add nsw i32 %9, 1
  store i32 %10, ptr %8, align 4

  %11 = add nsw i64 %5, -1
  %12 = icmp eq i64 %11, 0
  br i1 %12, label %13, label %4

13:
  %14 = add nuw nsw i64 %3, 1
  %15 = icmp eq i64 %14, %len
  br i1 %15, label %exit, label %2

exit:
  ret void

abort:
  tail call void @abort()
  unreachable
}

declare void @abort()

[fhahn]

Thanks for the example! I think this can be handled by an extension to the induction handling discussed here (https://reviews.llvm.org/D152730>.). Put up a patch: https://reviews.llvm.org/D158777