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

    <tr>
        <th>Summary</th>
        <td>
            SLPVectorizer's PHICompare doesn't provide a strict weak ordering
        </td>
    </tr>

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

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

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

<pre>
    https://github.com/llvm/llvm-project/blame/fc364e26845ce5529caf9f88abcc5a5531d1f59f/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp#L4138

Discovered via an internal bug where we don't have a good reproduction for this yet, but eyeballing the comparator it appears it could be buggy so I figured I'd start with this bug.

The issue was flagged by libc++ comparator checking 

There are several places in the comparator where it tests "if either element is missing this property, then they are not-less-than (ie: they are equal)" but assuming all states are valid/there's no external restrictions on the state of these objects, that definition can lead to an invalid/non-strict-weak comparator. 

Take the first case of this in the comparator: `!hasOneUse` - if either `Value` has more than one use, they are considered not-less-than.

But if you had `A`, `B`, and `C` - where `B` `!hasOneUse`, but `A` and `C` `hasOneUse` - then you end up with a situation where `A /< B` and `B /< C`, but `A < C`, potentially.

The issue comes up several times in this function - pretty much all the `return false` (including the trailing one, which catches both the dyn_cast check pairs, so counts for two instances of the problem) have this issue - so 7 instances by the looks of it.

The correct way to do these checks would be to choose an ordering for these cases - in the `hasOneUse` example, for instance - all the `!hasOneUse` might be the earlier elements, so it'd look like changing this code:

```
if (!V1->hasOneUse() || !V2->hasOneUse())
  return false;
```
To this:
```
if (!V1->hasOneUse() < !V2->hasOneUse())
  return true;
if (!V1->hasOneUse() > !V2->hasOneUse())
  return false;
...
```

I don't think it can be done in fewer steps - I think it requires at least two comparisons per pair like this. (that could be wrapped up in some utility to make it easier, like:
```
std::optional<bool> ThreeWayBoolCompare(bool A, bool B) {
 if (A < B)
    return true;
  if (B < A)
    return false;
 return std::nullopt;
}
...
if (std::optional<bool> Comp = ThreeWayBoolCompare(!V1->hasOneUse(), !V2->hasOneUse()))
  return *Comp;
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJycVl2P6jgS_TXmpQQCh4_mgQegB21LI-1Ie_fu46riVIi3HTtjV5phf_2qHGigb_es7kgtOont-jh16rgwJXv0RBu12KnF8wh7bkLcVKfSoX21NCpDdd40zF1SxVbpg9KHo-WmLycmtEofnHu7_ht3MfyHDCt9KB22pPShNsVyTnr5NF8YWiz02mC9rp-esDRmgYtFMatm9WJd3xmypdKHbxF9qkNsk9KH72Q4RPtfMfiPX397f40T03VKF7_OZ8WTmj6r6Xb4fbbJhDeKVMGbRUAP1jNFjw7K_ginhiLBiaAKXukVQ4NvBAjHECqI1MVQ9YZt8FCHCNzYBGdipfdQ9gx0phKds_4I3BCY0HYYkUMEy4BdRxiTPJrQuwpKEpfHM6QAL1DbYy9RvSi9qiAxRoaT5WZwUvbHyX0a3xoCm1JPcMIEtcPjkSooz-BsaZTeKb27d28aMq8S1gcbkQAjQaI3iuigc2gogfUfwx9gsQxMiRMorW0NZLmhCOSoJc9gE7Q2pSF5m6CLoaPIZwGHG8o2z9mdDzx2lNKYG_Sg9JMlVWxv6_R7j07ptdI6w4op9a3YRecEGaaU972hs5XSBwmDlF4l8AHoj0s5IyWONhcrQRhSyoch1PKSCEIpnExDhMhQUW29zeU16MERVsBhIMnVmQ9-PBgenwhf71CaPKKLr5R91jYmBoPp4th-ArCkr5ZTpWcNpr97-mcitZzCGG4wq-X0O7o-f28wQRui2EcPwRP0iS44DxCa4JOtMs0f0H4g0a5ncXAOPTRYiYdtDmIvj7vLI_q8sh_iGYhwWf4k5GsnXGw9nFbL6YfsMi3EPfkK-m7gO0Ky3GOuwru7LYi-FHvY3VndXT_uP3iG-49dYPJs0bnzFy1kQktJ_F_7gG17bQOboO790PJj6CIxn6HtTZPJKFVUy2kk7qOHGt2QmVDaG9dXVyXgiDbLQvC5TqfGmgYMsmkoQRlymxNUZ_9vg8IW6Vfo0MZMzhREMjynQXVOAaxPjF6adSCzdFvpqFV6PUjWwLOc3ljOr-6OlOd8xIXwms9b_gEYE2Ikw3DCs3RAFS4dkwNLcLoKGAcwTQiJpElCrChKloM25v2YKAmP_RWrBwrQH9h2LkMiZ64hwvge3Y9d0dpjw9l5Q0AYnb2p0BUuy1lGJUVw9lUCR3981yYTKpGc-6zF0fCXX20tVVR69n02VsUvtwDk4xrUaq9We5B1_cm6_GUzAA_cKHafOvsWcli3iH4uluJnAuHY3-L4v5Z_-cspTiaTT5MZfl_eL1hurH_NlyJ6KWolcmY91HSiCImpE_683PZF-r23Ua4AFoVOnBti0FKbROw7irl3hsoLshNJM0v8-9V7inIhZ9mxHlJoCXq2znImfCvqbRkIk6UopBJbXxUocSVLxTZ0IhToVLEvQ3CC37cmEv0Lz7sQ3D4HKQDKKmyzZsnTbuDUBToYyjLI2O4O6M-LCJf9u7x_-9n-x9Jcv76H7XvnQsc3eq6ePxRx8PBneUpuoIrnLxL-imP5tvkTiv3AMqW3YvXHVhpVm6JaF2sc0Wa2mi5ns2Kh9ajZLFczfFrp5XQxf1qXWK_WC6qmq6qamsUccT6yGz3V8-lMz2dLvdB6staLNeFqZsx8uZw9rdR8Si1aN5FBdBLicZSVdbNaF3o2cliSS3lK1trTaZBdpbUMzXGTx9-yPyY1nzqbON2ssGVHm4e5NY8xv_3t5YIcVIHS0ChdDG-2kmF0GD8gjx9XzR310f38LJ4jlTk6Z_K_AAAA__8j78Dv">