| Issue |
79321
|
| Summary |
SLPVectorizer's PHICompare doesn't provide a strict weak ordering
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
dwblaikie
|
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;
```
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
