[VectorCombine][X86] Poor handling of compare-select patterns with AVX2 spoofing on AVX1 targets

[RKSimon]

https://godbolt.org/z/Waonx44Mj

For AVX1 only targets we often encounter 'fake-AVX2' code for integer math like:

#if !defined(__AVX2__)
#define _mm256_cmpgt_epi32( a, b ) \
 _mm256_setr_m128i( \
	_mm_cmpgt_epi32( _mm256_extractf128_si256( (a), 0 ), _mm256_extractf128_si256( (b), 0 ) ), \
	_mm_cmpgt_epi32( _mm256_extractf128_si256( (a), 1 ), _mm256_extractf128_si256( (b), 1 ) ) )

#define _mm256_blendv_epi8( a, b, c ) \
 _mm256_setr_m128i( \
	_mm_blendv_epi8( _mm256_extractf128_si256( (a), 0 ), _mm256_extractf128_si256( (b), 0 ), _mm256_extractf128_si256( (c), 0 ) ), \
	_mm_blendv_epi8( _mm256_extractf128_si256( (a), 1 ), _mm256_extractf128_si256( (b), 1 ), _mm256_extractf128_si256( (c), 1 ) ) )
#endif

__m256i cmpsel_epi8(__m256i x, __m256i y, __m256i a, __m256i b) {
    __m256i cmp = _mm256_cmpgt_epi32(x,y);
    return _mm256_blendv_epi8(a,b,cmp);
}

This is really poorly optimized, mainly due to all the bitcasts to/from the __m128i (<2 x i64>) types.

In particular we see this pattern a lot:

  %3 = bitcast <4 x i32> %sext.i to <2 x i64>
  %4 = bitcast <4 x i32> %sext.i21 to <2 x i64>
  %shuffle.i.i = shufflevector <2 x i64> %3, <2 x i64> %4, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
  %7 = bitcast <4 x i64> %shuffle.i.i to <8 x i32>

We should be able to get VectorCombine to fold this to a <8 x i32> shufflevector instead, in fact VectorCombine::foldBitcastShuf might handle this if we extend it to binary shuffles, with improved cost handling.

We also see :

  %2 = icmp sgt <8 x i32> %0, %1
  %cmp.i = shufflevector <8 x i1> %2, <8 x i1> poison, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
  %sext.i = sext <4 x i1> %cmp.i to <4 x i32>
  %3 = bitcast <4 x i32> %sext.i to <2 x i64>
  %cmp.i20 = shufflevector <8 x i1> %2, <8 x i1> poison, <4 x i32> <i32 4, i32 5, i32 6, i32 7>
  %sext.i21 = sext <4 x i1> %cmp.i20 to <4 x i32>
  %4 = bitcast <4 x i32> %sext.i21 to <2 x i64>

We've managed to combine to a single <8 x i32> icmp , but failed to rejoin the compare result sign extensions. We should be able to handle this in VectorCombine if we handle concatenation of casts (based off what we do in VectorCombine::foldShuffleOfBinops)

• Extend VectorCombine::foldBitcastShuf to handle length changing shuffles
• Extend VectorCombine::foldBitcastShuf to handle binary shuffles
• Add a VectorCombine::foldShuffleOfCasts similar to VectorCombine::foldShuffleOfBinops

[llvmbot]

@llvm/issue-subscribers-backend-x86

https://godbolt.org/z/Waonx44Mj

For AVX1 only targets we often encounter 'fake-AVX2' code for integer math like:

#if !defined(__AVX2__)
#define _mm256_cmpgt_epi32( a, b ) \
 _mm256_setr_m128i( \
	_mm_cmpgt_epi32( _mm256_extractf128_si256( (a), 0 ), _mm256_extractf128_si256( (b), 0 ) ), \
	_mm_cmpgt_epi32( _mm256_extractf128_si256( (a), 1 ), _mm256_extractf128_si256( (b), 1 ) ) )

#define _mm256_blendv_epi8( a, b, c ) \
 _mm256_setr_m128i( \
	_mm_blendv_epi8( _mm256_extractf128_si256( (a), 0 ), _mm256_extractf128_si256( (b), 0 ), _mm256_extractf128_si256( (c), 0 ) ), \
	_mm_blendv_epi8( _mm256_extractf128_si256( (a), 1 ), _mm256_extractf128_si256( (b), 1 ), _mm256_extractf128_si256( (c), 1 ) ) )
#endif

__m256i cmpsel_epi8(__m256i x, __m256i y, __m256i a, __m256i b) {
    __m256i cmp = _mm256_cmpgt_epi32(x,y);
    return _mm256_blendv_epi8(a,b,cmp);
}

This is really poorly optimized, mainly due to all the bitcasts to/from the __m128i (<2 x i64>) types.

In particular we see this pattern a lot:

  %3 = bitcast <4 x i32> %sext.i to <2 x i64>
  %4 = bitcast <4 x i32> %sext.i21 to <2 x i64>
  %shuffle.i.i = shufflevector <2 x i64> %3, <2 x i64> %4, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
  %7 = bitcast <4 x i64> %shuffle.i.i to <8 x i32>

We should be able to get VectorCombine to fold this to a <8 x i32> shufflevector instead, in fact VectorCombine::foldBitcastShuf might handle this if we extend it to binary shuffles, with improved cost handling.

We also see :

  %2 = icmp sgt <8 x i32> %0, %1
  %cmp.i = shufflevector <8 x i1> %2, <8 x i1> poison, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
  %sext.i = sext <4 x i1> %cmp.i to <4 x i32>
  %3 = bitcast <4 x i32> %sext.i to <2 x i64>
  %cmp.i20 = shufflevector <8 x i1> %2, <8 x i1> poison, <4 x i32> <i32 4, i32 5, i32 6, i32 7>
  %sext.i21 = sext <4 x i1> %cmp.i20 to <4 x i32>
  %4 = bitcast <4 x i32> %sext.i21 to <2 x i64>

We've managed to combine to a single <8 x i32> icmp , but failed to rejoin the compare result sign extensions. We should be able to handle this in VectorCombine if we handle concatenation of casts (based off what we do in VectorCombine::foldShuffleOfBinops)

[nico]

This broke check-clang: http://45.33.8.238/linux/120114/step_7.txt

Please take a look and revert for now if it takes a while to fix.

[RKSimon]

Should be fixed by 32a9c09

[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/Waonx44Mj

For AVX1 only targets we often encounter 'fake-AVX2' code for integer math like:

#if !defined(__AVX2__)
#define _mm256_cmpgt_epi32( a, b ) \
 _mm256_setr_m128i( \
	_mm_cmpgt_epi32( _mm256_extractf128_si256( (a), 0 ), _mm256_extractf128_si256( (b), 0 ) ), \
	_mm_cmpgt_epi32( _mm256_extractf128_si256( (a), 1 ), _mm256_extractf128_si256( (b), 1 ) ) )

#define _mm256_blendv_epi8( a, b, c ) \
 _mm256_setr_m128i( \
	_mm_blendv_epi8( _mm256_extractf128_si256( (a), 0 ), _mm256_extractf128_si256( (b), 0 ), _mm256_extractf128_si256( (c), 0 ) ), \
	_mm_blendv_epi8( _mm256_extractf128_si256( (a), 1 ), _mm256_extractf128_si256( (b), 1 ), _mm256_extractf128_si256( (c), 1 ) ) )
#endif

__m256i cmpsel_epi8(__m256i x, __m256i y, __m256i a, __m256i b) {
    __m256i cmp = _mm256_cmpgt_epi32(x,y);
    return _mm256_blendv_epi8(a,b,cmp);
}

This is really poorly optimized, mainly due to all the bitcasts to/from the __m128i (<2 x i64>) types.

In particular we see this pattern a lot:

  %3 = bitcast <4 x i32> %sext.i to <2 x i64>
  %4 = bitcast <4 x i32> %sext.i21 to <2 x i64>
  %shuffle.i.i = shufflevector <2 x i64> %3, <2 x i64> %4, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
  %7 = bitcast <4 x i64> %shuffle.i.i to <8 x i32>

We should be able to get VectorCombine to fold this to a <8 x i32> shufflevector instead, in fact VectorCombine::foldBitcastShuf might handle this if we extend it to binary shuffles, with improved cost handling.

We also see :

  %2 = icmp sgt <8 x i32> %0, %1
  %cmp.i = shufflevector <8 x i1> %2, <8 x i1> poison, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
  %sext.i = sext <4 x i1> %cmp.i to <4 x i32>
  %3 = bitcast <4 x i32> %sext.i to <2 x i64>
  %cmp.i20 = shufflevector <8 x i1> %2, <8 x i1> poison, <4 x i32> <i32 4, i32 5, i32 6, i32 7>
  %sext.i21 = sext <4 x i1> %cmp.i20 to <4 x i32>
  %4 = bitcast <4 x i32> %sext.i21 to <2 x i64>

We've managed to combine to a single <8 x i32> icmp , but failed to rejoin the compare result sign extensions. We should be able to handle this in VectorCombine if we handle concatenation of casts (based off what we do in VectorCombine::foldShuffleOfBinops)

[SahilPatidar]

@RKSimon I'm interested in taking on this task, if it's still available.

[RKSimon]

I've been investigating this myself and its a much bigger task than I initially thought as the shuffle costs for length changing shuffles are so poor - I need to split this further to show the yak shaving involved