Reassociate pass serializes vector comparison results

[RKSimon]

https://godbolt.org/z/Kh7667Yxo

Pulled out of Issue #63946

While the scalar code for an accumulative or chain of comparison results stays as a binary tree:

define i1 @scalar(i32 %a, i32 %b0, i32 %b1, i32 %b2, i32 %b3, i32 %b4, i32 %b5, i32 %b6, i32 %b7) local_unnamed_addr {
entry:
  %cmp0 = icmp eq i32 %b0, %a
  %cmp1 = icmp eq i32 %b1, %a
  %cmp2 = icmp eq i32 %b2, %a
  %cmp3 = icmp eq i32 %b3, %a
  %cmp4 = icmp eq i32 %b4, %a
  %cmp5 = icmp eq i32 %b5, %a
  %cmp6 = icmp eq i32 %b6, %a
  %cmp7 = icmp eq i32 %b7, %a
  %or01 = or i1 %cmp0, %cmp1
  %or23 = or i1 %cmp2, %cmp3
  %or45 = or i1 %cmp4, %cmp5
  %or67 = or i1 %cmp6, %cmp7
  %or0123 = or i1 %or01, %or23
  %or4567 = or i1 %or45, %or67
  %or01234567 = or i1 %or0123, %or4567
  ret i1 %or01234567
}

The vector code equivalent gets linearised, resulting in a much deeper serial chain, affecting IPC and making it more likely we will hit value tracking recursion depth limits:

define <8 x i1> @vector(<8 x i32> %a, <8 x i32> %b0, <8 x i32> %b1, <8 x i32> %b2, <8 x i32> %b3, <8 x i32> %b4, <8 x i32> %b5, <8 x i32> %b6, <8 x i32> %b7) local_unnamed_addr {
entry:
  %cmp0 = icmp eq <8 x i32> %b0, %a
  %cmp1 = icmp eq <8 x i32> %b1, %a
  %cmp2 = icmp eq <8 x i32> %b2, %a
  %cmp3 = icmp eq <8 x i32> %b3, %a
  %cmp4 = icmp eq <8 x i32> %b4, %a
  %cmp5 = icmp eq <8 x i32> %b5, %a
  %cmp6 = icmp eq <8 x i32> %b6, %a
  %cmp7 = icmp eq <8 x i32> %b7, %a
  %or01 = or <8 x i1> %cmp0, %cmp1
  %or23 = or <8 x i1> %cmp2, %cmp3
  %or45 = or <8 x i1> %cmp4, %cmp5
  %or67 = or <8 x i1> %cmp6, %cmp7
  %or0123 = or <8 x i1> %or01, %or23
  %or4567 = or <8 x i1> %or45, %or67
  %or01234567 = or <8 x i1> %or0123, %or4567
  ret <8 x i1> %or01234567
}

->

define <8 x i1> @vector(<8 x i32> %a, <8 x i32> %b0, <8 x i32> %b1, <8 x i32> %b2, <8 x i32> %b3, <8 x i32> %b4, <8 x i32> %b5, <8 x i32> %b6, <8 x i32> %b7) local_unnamed_addr {
  %cmp0 = icmp eq <8 x i32> %b0, %a
  %cmp1 = icmp eq <8 x i32> %b1, %a
  %cmp2 = icmp eq <8 x i32> %b2, %a
  %cmp3 = icmp eq <8 x i32> %b3, %a
  %cmp4 = icmp eq <8 x i32> %b4, %a
  %cmp5 = icmp eq <8 x i32> %b5, %a
  %cmp6 = icmp eq <8 x i32> %b6, %a
  %cmp7 = icmp eq <8 x i32> %b7, %a
  %or67 = or <8 x i1> %cmp1, %cmp0
  %or45 = or <8 x i1> %or67, %cmp2
  %or4567 = or <8 x i1> %or45, %cmp3
  %or23 = or <8 x i1> %or4567, %cmp4
  %or01 = or <8 x i1> %or23, %cmp5
  %or0123 = or <8 x i1> %or01, %cmp6
  %or01234567 = or <8 x i1> %or0123, %cmp7
  ret <8 x i1> %or01234567
}

[RKSimon]

The magic code is:

llvm-project/llvm/lib/Transforms/Scalar/Reassociate.cpp

Line 2271 in 8406f80

if (I->getType()->isIntegerTy(1))

Could this be as simple as changing to isIntOrIntVectorTy(1)?

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. In the comments of the issue, request for it to be assigned to you.
2. Fix the issue locally.
3. Run the test suite locally. Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests.
4. Create a Git commit.
5. Run git clang-format HEAD~1 to format your changes.
6. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation.

If you have any further questions about this issue, don't hesitate to ask via a comment in the thread below.

[llvmbot]

@llvm/issue-subscribers-good-first-issue

Author: Simon Pilgrim (RKSimon)

https://godbolt.org/z/Kh7667Yxo

Pulled out of Issue #63946

While the scalar code for an accumulative or chain of comparison results stays as a binary tree:

define i1 @<!-- -->scalar(i32 %a, i32 %b0, i32 %b1, i32 %b2, i32 %b3, i32 %b4, i32 %b5, i32 %b6, i32 %b7) local_unnamed_addr {
entry:
  %cmp0 = icmp eq i32 %b0, %a
  %cmp1 = icmp eq i32 %b1, %a
  %cmp2 = icmp eq i32 %b2, %a
  %cmp3 = icmp eq i32 %b3, %a
  %cmp4 = icmp eq i32 %b4, %a
  %cmp5 = icmp eq i32 %b5, %a
  %cmp6 = icmp eq i32 %b6, %a
  %cmp7 = icmp eq i32 %b7, %a
  %or01 = or i1 %cmp0, %cmp1
  %or23 = or i1 %cmp2, %cmp3
  %or45 = or i1 %cmp4, %cmp5
  %or67 = or i1 %cmp6, %cmp7
  %or0123 = or i1 %or01, %or23
  %or4567 = or i1 %or45, %or67
  %or01234567 = or i1 %or0123, %or4567
  ret i1 %or01234567
}

The vector code equivalent gets linearised, resulting in a much deeper serial chain, affecting IPC and making it more likely we will hit value tracking recursion depth limits:

define &lt;8 x i1&gt; @<!-- -->vector(&lt;8 x i32&gt; %a, &lt;8 x i32&gt; %b0, &lt;8 x i32&gt; %b1, &lt;8 x i32&gt; %b2, &lt;8 x i32&gt; %b3, &lt;8 x i32&gt; %b4, &lt;8 x i32&gt; %b5, &lt;8 x i32&gt; %b6, &lt;8 x i32&gt; %b7) local_unnamed_addr {
entry:
  %cmp0 = icmp eq &lt;8 x i32&gt; %b0, %a
  %cmp1 = icmp eq &lt;8 x i32&gt; %b1, %a
  %cmp2 = icmp eq &lt;8 x i32&gt; %b2, %a
  %cmp3 = icmp eq &lt;8 x i32&gt; %b3, %a
  %cmp4 = icmp eq &lt;8 x i32&gt; %b4, %a
  %cmp5 = icmp eq &lt;8 x i32&gt; %b5, %a
  %cmp6 = icmp eq &lt;8 x i32&gt; %b6, %a
  %cmp7 = icmp eq &lt;8 x i32&gt; %b7, %a
  %or01 = or &lt;8 x i1&gt; %cmp0, %cmp1
  %or23 = or &lt;8 x i1&gt; %cmp2, %cmp3
  %or45 = or &lt;8 x i1&gt; %cmp4, %cmp5
  %or67 = or &lt;8 x i1&gt; %cmp6, %cmp7
  %or0123 = or &lt;8 x i1&gt; %or01, %or23
  %or4567 = or &lt;8 x i1&gt; %or45, %or67
  %or01234567 = or &lt;8 x i1&gt; %or0123, %or4567
  ret &lt;8 x i1&gt; %or01234567
}

->

define &lt;8 x i1&gt; @<!-- -->vector(&lt;8 x i32&gt; %a, &lt;8 x i32&gt; %b0, &lt;8 x i32&gt; %b1, &lt;8 x i32&gt; %b2, &lt;8 x i32&gt; %b3, &lt;8 x i32&gt; %b4, &lt;8 x i32&gt; %b5, &lt;8 x i32&gt; %b6, &lt;8 x i32&gt; %b7) local_unnamed_addr {
  %cmp0 = icmp eq &lt;8 x i32&gt; %b0, %a
  %cmp1 = icmp eq &lt;8 x i32&gt; %b1, %a
  %cmp2 = icmp eq &lt;8 x i32&gt; %b2, %a
  %cmp3 = icmp eq &lt;8 x i32&gt; %b3, %a
  %cmp4 = icmp eq &lt;8 x i32&gt; %b4, %a
  %cmp5 = icmp eq &lt;8 x i32&gt; %b5, %a
  %cmp6 = icmp eq &lt;8 x i32&gt; %b6, %a
  %cmp7 = icmp eq &lt;8 x i32&gt; %b7, %a
  %or67 = or &lt;8 x i1&gt; %cmp1, %cmp0
  %or45 = or &lt;8 x i1&gt; %or67, %cmp2
  %or4567 = or &lt;8 x i1&gt; %or45, %cmp3
  %or23 = or &lt;8 x i1&gt; %or4567, %cmp4
  %or01 = or &lt;8 x i1&gt; %or23, %cmp5
  %or0123 = or &lt;8 x i1&gt; %or01, %cmp6
  %or01234567 = or &lt;8 x i1&gt; %or0123, %cmp7
  ret &lt;8 x i1&gt; %or01234567
}

[RKSimon]

@dtcxzyw A small warning - there looks to be no test coverage for this - so this ticket might end up being rather lengthy - adding useful scalar AND vector test coverage, performance testing, .....

[SahilPatidar]

@RKSimon Is this task still available? I'd be happy to work on it if it is.

[RKSimon]

• Add test coverage for reassociation of scalar/vector boolean types
• Disable vector boolean reassociation to match scalar boolean types
• Run test suite before/after tests for the effect of disabling scalar and vector boolean reassociation (although scalar most likely is the only one to show a diff)

[SahilPatidar]

@RKSimon Sorry for the delay. I noticed a difference in vector behavior with -passes=reassociate. When I perform the same operation as in the example you provided

[SahilPatidar]

@RKSimon

[RKSimon]

@SahilPatidar Were you able to create some suitable tests ?

[SahilPatidar]

I tried some tests similar to the ones you mentioned, but with some modifications.