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

    <tr>
        <th>Summary</th>
        <td>
            [SLPVectorizer] compareCmp is not strict weak ordering 
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </td>
    </tr>

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

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

<pre>
    After submitting https://reviews.llvm.org/D150264, we found that vectorizeCmpInsts, the `compareCmp<false>` is not strict weak ordering. For example, there is no condition for IsDeleted(CI1) and LEPreds/GEPreds are looking in different directions which might violate transitivity of equivalence. As well as `if (I1->getParent() != I2->getParent())` condition as for a, b, c we might have `!comp(a, b), !comp(b, a), !comp(b, c), !comp(c, b)` but `comp(a, b)` as getParent for them might return true.

This function is complicated and I could not figure out the right fix

```diff
template <bool IsCompatibility>
static bool compareCmp(Value *V, Value *V2, TargetLibraryInfo &TLI,
 function_ref<bool(Instruction *)> IsDeleted) {
  auto *CI1 = cast<CmpInst>(V);
  auto *CI2 = cast<CmpInst>(V2);
  if (IsDeleted(CI2) || !isValidElementType(CI2->getType()))
    return false;
+ if (IsDeleted(CI1) || !isValidElementType(CI1->getType()))
+   return true;
  if (CI1->getOperand(0)->getType()->getTypeID() <
 CI2->getOperand(0)->getType()->getTypeID())
    return !IsCompatibility;
  if (CI1->getOperand(0)->getType()->getTypeID() >
 CI2->getOperand(0)->getType()->getTypeID())
    return false;
 CmpInst::Predicate Pred1 = CI1->getPredicate();
  CmpInst::Predicate Pred2 = CI2->getPredicate();
  CmpInst::Predicate SwapPred1 = CmpInst::getSwappedPredicate(Pred1);
  CmpInst::Predicate SwapPred2 = CmpInst::getSwappedPredicate(Pred2);
  CmpInst::Predicate BasePred1 = std::min(Pred1, SwapPred1);
  CmpInst::Predicate BasePred2 = std::min(Pred2, SwapPred2);
  if (BasePred1 < BasePred2)
    return !IsCompatibility;
  if (BasePred1 > BasePred2)
    return false;
 // Compare operands.
+ // Likely a violation here as well
  bool LEPreds = Pred1 <= Pred2;
  bool GEPreds = Pred1 >= Pred2;
  for (int I = 0, E = CI1->getNumOperands(); I < E; ++I) {
    auto *Op1 = CI1->getOperand(LEPreds ? I : E - I - 1);
    auto *Op2 = CI2->getOperand(GEPreds ? I : E - I - 1);
    if (Op1->getValueID() < Op2->getValueID())
      return !IsCompatibility;
    if (Op1->getValueID() > Op2->getValueID())
      return false;
    if (auto *I1 = dyn_cast<Instruction>(Op1))
      if (auto *I2 = dyn_cast<Instruction>(Op2)) {
        if (I1->getParent() != I2->getParent())
-          return false;
+          return I1->getParent() < I2->getParent();
        InstructionsState S = getSameOpcode({I1, I2}, TLI);
        if (S.getOpcode())
 continue;
+       // Likely a violation here as well
        return false;
      }
  }
  return IsCompatibility;
}
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy0V11v6jgT_jXmZlSUTEoaLriAAEeRqrdHatXbIyeZgN_ma22HHvbXr-wkJFDa01a7CEFij5_58DMzNldK7EqiBZut2Gw94Y3eV3KR8jLn8sWdxFV6XCwzTRJUExdCa1HuYK91rZi3ZLhluJV0EPSqpnl-KKaV3DHcrt2Zg_4twxBeCbKqKVPQe67hQImupPibwqKOSqWVEdF7AuY7SVXUXJoZ5oUZzxUxb8N8B4SCstKgtBSJhlfiL1DJlKQod1PYVhLoNy_qnDosSe0KSKoyFVpUJWSVhEitKSdNKcMgjFyGc-BlCvebn5JSxXD7o30CLgnyqnoxnooSUpFlJKnUkApJicFT8LoXyR4KsdtrOIgq55pAS14qocVB6CNUGdBfjTjwnMqEprBU8Ep5DlwZV0UGDIPIvWHeZkf6Jzf4DANjFEOXeWuI8Mqk-frOyDGurG_cuB6bn8QEvLVrzw82rgxdE1qGQS82N__DsF3Irw8nb4aTE4jvQNzofuvO8H3HmHay3hqp91R0pknSjSxBy4amzFkzZ9n-Pu2FgqwpbZTNLhrgXCRcU2p3K4KkavLU8iETu0YSVI22DJIWORO_x4DGffs1u9gOaSpqu1_MC-OqyiFSoWGeFrHIhT4a0llBpbkWCViZETcxeOZ5Q8Bw-Wz8Hd7QvD5xuSN9L2LJ5TEqswoY-k_3EcOwhT3590tS1tlgyFAqLZvWcYZLE0RvMybtHNjdqoMA3mgDvAwjFwxbEq4088Iuq4wLGDxbjCtL8P0leL6m4-lZ5mBrSsjuLCuEeua5SDc5FVTqp2NNrVTH3m6g4y7Oe2ToOdAleqeS4eqqUvdTSt0PlRpsGFPvjaMDwkNNkpdGt8Nw_gZ2NBCt-7z1-g0evP86zLUQMXTfcPTftXzzH1l-vrlw4tqSeUtTbG1mg3lqaTy4cZrtwAeHPwDBDgS_C_L4yuuRNWOhHWkzW1M6RrXCX4LGr0Djp6BXXNFgtdJpK1CIcrAwHHz7Eia-h4ljzKtlY2xWOAB-k-FjtM3HaBesa08pELYlHKqW2Wo6VIVO4l68UH4E3nV0U4ntaYK3vbvXYxtCd2yw0Tk52b_gyHor_eOK9OaatOmTDANRaoistGPCvLlIjv81RZef6sRsKx_CxjwyXDFcRRc9Y2gBD_Vlug3pPji2tZBL2MANRHADF8QZw10m3gD34_Nw7T4_1L1NtrGOyys81Hht7owDn-PUn7VtvqbtgnMnBX2Muj6dHstfXeMdNfy2-T7U7lv4CxT8BAq2KOdbP2B979RpgW7g9Hm3e19KvKPOC9_R5V0YPXJQPWpbSW0MTNHkBT3USZXa-n63imydi5Ddre1JzBy63gK2UXicWpr2i8dxT6pSi7K55tbXCsUfCAJgDO1eR4994N4h70nydLadpAsvnXtzPqGF6we-M3MQg8l-wXGexBkmmee6aZrFd7NkPkviGGNEj5JkIhbooOf4ju-67p0TTAM_c4I4CFwH3WyexezWoYKL_HS5mwilGlr4nnvrTnIeU676u6NcGKGbuNkpduvkQunhTjjRQuf2lvl4__O5vwRKNluPjtYfXfRg0sh8cX7x3Am9b-JpUhUMt0ZT93dTy-r_lGiGW2utudxZg_8JAAD__yrkVpg">