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

    <tr>
        <th>Summary</th>
        <td>
            Assertion failure in SCEV - "Your comparator is not a valid strict-weak ordering"
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:SCEV,
            hardening
      </td>
    </tr>

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

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

<pre>
    While debugging another issue, we found this assertion failure arising from this `stable_sort` invocation: https://github.com/llvm/llvm-project/blame/main/llvm/lib/Analysis/ScalarEvolution.cpp#L795, which is using this comparator: https://github.com/llvm/llvm-project/blame/main/llvm/lib/Analysis/ScalarEvolution.cpp#L781.

This only happens when clang is compiled with the corresponding libc++ hardening enabled (`-D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG`).

A reduced test case:
```
$ cat reduced.ll
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define ptr @_f1(ptr %this, ptr %__first) {
entry:
  %call = call i64 @_f2(ptr %this, ptr %__first)
 %call3 = call ptr @_f3(ptr %this, i64 %call)
  ret ptr null
}

define void @_f4(ptr %__from_s, ptr %__to) {
entry:
  %0 = load ptr, ptr %__from_s, align 8
  %sub.ptr.lhs.cast = ptrtoint ptr %0 to i64
 %sub.ptr.rhs.cast = ptrtoint ptr %__to to i64
  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
  %add.ptr = getelementptr i8, ptr %__from_s, i64 %sub.ptr.sub
  br label %for.cond

for.cond: ; preds = %for.cond, %entry
  %__i.0 = phi ptr [ %add.ptr, %entry ], [ %incdec.ptr, %for.cond ]
  store volatile ptr %__i.0, ptr null, align 8
  %incdec.ptr = getelementptr i8, ptr %__i.0, i64 1
  br label %for.cond
}

define ptr @_f3(ptr %this, i64 %__n) {
entry:
  %0 = load ptr, ptr %this, align 8
  %call3 = load volatile i64, ptr null, align 8
  %add.ptr = getelementptr i8, ptr %0, i64 %call3
  %add.ptr16 = getelementptr i8, ptr %add.ptr, i64 %__n
  call void @_f4(ptr %add.ptr, ptr %add.ptr16)
  ret ptr null
}

define i64 @_f2(ptr %__first, ptr %__last) {
entry:
  %call = call i64 @_f5(ptr %__first, ptr %__last)
  ret i64 %call
}

define i64 @_f5(ptr %__first, ptr %__last) {
entry:
 %sub.ptr.lhs.cast = ptrtoint ptr %__last to i64
  %sub.ptr.rhs.cast = ptrtoint ptr %__first to i64
  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
  ret i64 %sub.ptr.sub
}
$ ./clang-bad -O1 -c reduced.ll -o -
libcxx/include/__debug_utils/strict_weak_ordering_check.h:59: assertion __comp(*(__first + __a), *(__first + __b)) failed: Your comparator is not a valid strict-weak ordering
...
```
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJzEVl2v26gW_TXkBdnCYDvOQx6ck5PeSr1tdXtnRvNkYSAxLQEL8Pn49yOwk_h8NlNpNFKUGHuvxdqb7Z1FnZMHLcQaFBuAsaP6u3kEGINiu6CD74xdUyUe9t2iNfxx_UcnlYBctMPhIPUBUm18JyyUzg0C4Bt4L-DeDJpD30kHqXPCemk03FOpBisgtdIF4N6a4xgDSuQ8bZVonLEelAhKfWcYDTBAath53ztAaoB3AO8O0ndDmzJzBHin1N3pJ-mt-S6YB3jXKnoUAO-OVOpZkGwB3tWaqkcnHcC7b4wqam_vjBrCVinre4DJp-WqiHl0knVQOjhEuVEpM8eeWuqN_Td0VVkKUA1Q_f-gxWj1CDva90I7eN8JDZmi-gAnmVIJDu-l76DvBGTGWuF6o3nIRcmWAbwBeAM7arnQ4abQ4Qg4BLgCJUq2zaePm5uvX5v_1P_b3n7--PlD898v21tA3njQbG83v30AJQJ4NcmsoRV8YIJDL5yHjDoRqoXqEDV-UA1wDhn1p9BUKYBqT-1BeMipp4o-msFDQLYQYCySIyC1SHq8RIDUBMevsMyeLsNVmcevRJ4vMlwBUme4SvYVmq50vFWe4GWefAthGF90eCt7JU4aHqqyKfNk0D-0udeJknp4SA56GCEA1VzspRaw9xaCHDX7DOAqLnARuig017Rsmr20zgO8gmC5AagW2tvHsUgwBDCqVNw3XsgyHxnxFYyBYmIgF4qzKPKSItKPiAkPrfARood4LmC5fZLinZF8pMsvdE0TXu3mqSpv3k4SRXnKUB7inyZzZqJKHjSsThg3tGnvbao6lzLqxgbpvfVGan_CI-hNyGoqxQlj38MEqTPYHOeGNkLC71Sr5zKC0ld2OjFRztO4D9nCg_BCiaPQPtyR1Rt5P9vIDW0kay1UtBUqPNsbmzKj-Xg05xWpISAb2FvB3dS7l9BR53gSk7imkel4FH0nRynFZqZ6joGg2Mb1GCE144LNgk77xLjA77yxoV8U9eH_45yoTNEp8dhjL0_6wv3zsk1soWbZu2V61sdXvBVNo3-hg08kz3K6vJQRcy5LaLr3q3FlB6Fn7zN5hs_KnzHMDn1WgcAS58irb_4M8_ROVl45UF6bcOeRNjtoRX9hahZXcZ5lzsfhO0qvY31F6bVTbOR4Yyb9ZJZFPf_MOJuV6OlwmiqFc5gCvIumJGkph8mXDCZs9kcPEwMTgOpgRx4eAN5JzdTAg0Nqmugwm8FLFSyR81Yy39wL-qMxlgsr9aFhnWA_0g6QuliFaXfxmk0TLFBwMrgGuDrVIRiepqHhkGNiL5-18dkqmlURR-ifZrAz3xfslTYeUnhHleRwFJYEYfAkDKA6TdO5z1nwNeErsqILsc6WeVYWGVpVi27NKMkzjquM78UyI-2qQAUpin3bkhIzThZyjREuEMkQJkWVLdN9lbPlqhD5iixbgQXIkThSqdLgJlNjD4voxNcZQWVVLeL0c5O3j4aT1N9ubn8PZgXfAIzPBnCy_HYdTWs7HBzIkZLOuwu1l16Jdf3C00sNAylMgj_6lYphvBisWv9tRx1zDQ0ypXu3xn8FAAD__2Oq6kA">