<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/64881>64881</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Missed constraint elimination opportunity in nested loop
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          cynecx
      </td>
    </tr>
</table>

<pre>
    ```cpp
[[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;
        }
 }
}
```

The bounds check `idx < len` inside the inner loop could've been eliminated but isn't right now. 

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

<details>
<summary>Reduced llvm ir</summary>

```llvm
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()
```

</details>
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyEVkGP6jYQ_jXmMtpVMklIOHBYlsc7VJWq6l16dOKBuGtsajvL0l9f2QkkAfreagW2Zzzf52_GY7hz8qCJ1qzYsGK74J1vjV03F03N16I24rJmy6T_b04nlmxZ8hZ9N9pY8p3VrNiyYgufRgrgtbGeYcVwxbLN4N1_YiZoLzXB2w-GlRRfDFcgDLByA3IP_Rqw7BvLtqBIB3OwzUMCK7fArY3f51YqYlglwTbFivykVlLTwM557mUDUnuGb8BDwOvYWobv0OkohOihJ_OBKSuH4wDAz_iOTuHvmR5hnZXbcdLL2J8KNxHwpt3Vr_-MGh-N_qDLLw5wx4XhjuEOpHZkvTQanLEelPwgkJ4sD2uj994EJtUoAYQzpkH-MHyPECEXuGG4kXO0-80fcbMM_mH4DZIwfHn5eCrYhOzgDQyXDJdx2iM_2fAWMzooMWSwB8DNlft835iBUePb4FrxU-1_tAS16bRw0LTUfABbJn0F9IjLJMgrBYFvCaTWZEEZc4LGdEowLD8JaiINpORRau5JQN15kE4zLD1YeWg9aHN-hSls6_3JseytF-VgRG2UfzX2wHD3L8Pdb3nT0B-UhqNWTZ-RoCA0iuvD7WL8KowQf1XUfv-ehjBKfR5B2hjGnPz97creBXkulQvFf11y3fHI7YVl3_4k0TWhDvsoLHtnuBvNs1BXoYNvvzQ0iVjpLE9uxX7ygU8xpFgu8zB7KHWGRdrXW3M8QXfwM893SK9FUFuQaXSPFcNrUmGGsxl9ST-li0HAG1AWgU6t7DGKDcRYDIsEQtcJ42ITMfLBkGbRMnK4QeVTnHzECbbiASigDyHxHutKopxCMSyWE13UTZdi8FakIdxL30oH0gFXZ35x4G1HD5ItZyKVs1nf8CZnKednqSKLA3lSdCTtQ1qlHu6VzKL-T1Nd3IKMwVYxmDJc3G2twpgredCQTyojif5cCNDuHLbEILO6cN5YuprS5KcxJ0zSdB56Iu5LOvXDMQv0z9Wvz1nyWJvzckyz2XTGIs3mOqf5SKg7T0lls_MG1-Ipp3ysjEdixeM9mV-jCbVoHclZ8vF2T136qhl9QneBhit16wPTh7R36rQl3rS8VvT0rRTUKG7p_yM87fJ9txr720KsM7HKVnxB63S5wmVRJQUu2nWe5EXWFGWypyJvsqoW6apJVyJZ1SKpERdyjQlmSYUpYl5m-Frti3yf7nlW5gUSR5YndORSvYbmF1rxQjrX0XqZV1W6iFq6-LMMUdMZopEhhl9pdh32vNTdwbE8UdJ5N0bx0ita_y6dIwGN0c5bLrW_vTvh-Tenk7G-09JfQGrQ5MJzFJ6rRWfV-u61kL7t6tfGHBnuYqfuv15O1vxNjWe4i-Qcw10k_18AAAD__-wvxNE">