<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">