| Issue |
172591
|
| Summary |
[InstCombine] N^2 time complexity for chains of selects produced by unrolling
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
AlexMaclean
|
```
define i1 @foo() {
%c1 = load volatile i1, ptr undef
%s1 = select i1 %c1, i1 true, i1 false
%c2 = load volatile i1, ptr undef
%s2 = select i1 %c2, i1 true, i1 %s1
%c3 = load volatile i1, ptr undef
%s3 = select i1 %c3, i1 true, i1 %s2
%c4 = load volatile i1, ptr undef
%s4 = select i1 %c4, i1 true, i1 %s3
%c5 = load volatile i1, ptr undef
%s5 = select i1 %c5, i1 true, i1 %s4
ret i1 %s5
}
```
The following code is highly simplified but similar patterns can occur in unrolled loops. In this case, InstCombine will reassociate the selects, essentially inverting the order. This happens by pushing each select all the way inwards through each previous select, starting with the first and ending with the last (which is pushed through all the other selects). This has O(n^2) time complexity and can be quite noticeable for large unrolled loops.
It seems like we should be able to do better, such as by deferring the reassociation to the end and the doing a complete reordering, but I'm not sure what fits within the design of InstCombine.
Here is the relevant snippet in IC:
```
// select(C0, a, select(C1, a, b)) -> select(C0|C1, a, b)
if (FalseSI->getTrueValue() == TrueVal && FalseSI->hasOneUse()) {
Value *Or = Builder.CreateLogicalOr(CondVal, FalseSI->getCondition());
replaceOperand(SI, 0, Or);
replaceOperand(SI, 2, FalseSI->getFalseValue());
return &SI;
}
```
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
