Skip to content

Missed optimization: fold ceil(x/16) == 0 to x == 0 #143636

Closed
@Cancelll

Description

@Cancelll
define i1 @src(i32 %arg0) {
  %1 = add i32 %arg0, 1
  %2 = lshr i32 %1, 4
  %3 = and i32 %1, 15
  %4 = icmp ne i32 %3, 0
  %5 = zext i1 %4 to i32
  %6 = add nuw nsw i32 %2, %5
  %7 = icmp eq i32 %6, 0
  ret i1 %7
}

define i1 @tgt(i32 %arg0) {
  %5 = icmp eq i32 %arg0, -1
  ret i1 %5
}

(x >> 4) + ((x & 0xF) ≠ 0) is equivalent to ceil(x/16).
ceil(x/16) equals to 0 only when x is 0.

Alive2: https://alive2.llvm.org/ce/z/E85DRW
godbolt: https://godbolt.org/z/Y5frz97Mh

The pattern is found in projects including wasmi, coreutils, ruff. An example:
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/013f9638352b38eb8f26daddafeeb0d87fc6510b/bench/coreutils-rs/optimized/50z74lntrf1cjp27.ll#L1210-L1216

Metadata

Metadata

Assignees

Labels

llvm:analysisIncludes value tracking, cost tables and constant foldingllvm:instcombineCovers the InstCombine, InstSimplify and AggressiveInstCombine passesmissed-optimization

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions