llvm / llvm/llvm-project

[InstCombine] N^2 time complexity for chains of selects produced by unrolling

Open
#172,591 3 comments 0 reactions 1 assignee Claimed by @nikic View on GitHub
llvm:instcombine slow-compile
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

```
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: https://github.com/llvm/llvm-project/blob/dea9ec84a40a41d871f2e69d2ddb98d4071afa1d/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp#L4534-L4540

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.