[InstCombine] Generate better code for std::bit_ceil
authorKazu Hirata <kazu@google.com>
Fri, 24 Mar 2023 02:26:43 +0000 (19:26 -0700)
committerKazu Hirata <kazu@google.com>
Fri, 24 Mar 2023 02:26:43 +0000 (19:26 -0700)
commit231fa27435105e980b113754c112980ebeb8927d
tree26b69612ef97e495d0b0c514edd4af569c9c41a8
parent5f48b861f8ce2d2355347d3b3b8826f7bfd23dd6
[InstCombine] Generate better code for std::bit_ceil

Without this patch, std::bit_ceil<uint32_t> is compiled as:

  %dec = add i32 %x, -1
  %lz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)
  %sub = sub i32 32, %lz
  %res = shl i32 1, %sub
  %ugt = icmp ugt i32 %x, 1
  %sel = select i1 %ugt, i32 %res, i32 1

With this patch, we generate:

  %dec = add i32 %x, -1
  %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)
  %sub = sub nsw i32 0, %ctlz
  %and = and i32 %1, 31
  %sel = shl nuw i32 1, %and
  ret i32 %sel

https://alive2.llvm.org/ce/z/pwezvF

This patch recognizes the specific pattern from std::bit_ceil in
libc++ and libstdc++ and drops the conditional move.  In addition to
the LLVM IR generated for std::bit_ceil(X), this patch recognizes
variants like:

  std::bit_ceil(X - 1)
  std::bit_ceil(X + 1)
  std::bit_ceil(X + 2)
  std::bit_ceil(-X)
  std::bit_ceil(~X)

This patch fixes:

https://github.com/llvm/llvm-project/issues/60802

Differential Revision: https://reviews.llvm.org/D145299
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
llvm/test/Transforms/InstCombine/bit_ceil.ll