search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
28.97k stars 11.94k forks source link

LLVM fails to optimize out an arithmetic right shift of an I64 by 63 followed by a fshl of an I64 by 1 #102875

Open johnplatts opened 2 months ago

johnplatts commented 2 months ago

LLVM fails to optimize out the @llvm.fshl.i64(i64 %shifted_hi, i64 %1, i64 1) below (as all of the bits of %shifted_hi are known to be equal to the MSB of %1 in the code below):

define { i64, i64 } @src(i64 %0, i64 %1) local_unnamed_addr #0 {
  %shifted_hi = ashr i64 %1, 63
  ; shifted_hi = ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
  ; %1 =         sxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
  %shifted_lo = tail call i64 @llvm.fshl.i64(i64 %shifted_hi, i64 %1, i64 1)
  ; %shifted_lo = ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
  %result0 = insertvalue { i64, i64 } poison, i64 %shifted_lo, 0
  %result1 = insertvalue { i64, i64 } %result0, i64 %shifted_hi, 1
  ret { i64, i64 } %result1
}

define { i64, i64 } @tgt(i64 %0, i64 %1) local_unnamed_addr #0 {
  %shr_result = ashr i64 %1, 63
  ; shifted_hi = ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
  ; %1 =         sxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
  %result0 = insertvalue { i64, i64 } poison, i64 %shr_result, 0
  %result1 = insertvalue { i64, i64 } %result0, i64 %shr_result, 1
  ret { i64, i64 } %result1
}

attributes #0 = { mustprogress nofree norecurse nosync nounwind willreturn memory(none) uwtable }
attributes #1 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }

The above snippet run through alive-tv and opt can be found at https://alive2.llvm.org/ce/z/dew45A.

%shifted_lo = tail call i64 @llvm.fshl.i64(i64 %shifted_hi, i64 %1, i64 1) above can be optimized down to %shifted_hi in the case where %shifted_hi is equal to the result of ashr i64 %1, 63 as all of the bits of %shifted_hi are equal to the MSB of %1.

nikic commented 2 months ago

Interesting case! Would you mind sharing where you encountered this pattern?

johnplatts commented 2 months ago

Interesting case! Would you mind sharing where you encountered this pattern?

I was writing a portable C++ function to perform an arithmetic right-shift of a 128-bit signed integer on targets that do not support the __int128_t/__uint128_t types.