Skip to content

Support the % N -> & (N - 1) transformation for runtime power-of-two values #58996

Closed
@scottmcm

Description

@scottmcm

I tried sending this to opt

define i16 @src(i16 %x, i16 %y) {
start:
  %0 = tail call i16 @llvm.ctpop.i16(i16 %y)
  %_3 = icmp eq i16 %0, 1
  tail call void @llvm.assume(i1 %_3)
  %_7 = icmp eq i16 %y, 0
  %1 = urem i16 %x, %y
  ret i16 %1
}

expecting it to optimize to something like this

define i16 @tgt(i16 %x, i16 %y) {
start:
  %0 = sub nuw i16 %y, 1
  %1 = and i16 %x, %0
  ret i16 %1
}

but it didn't -- it left the div in the generated assembly.

Alive2 proof that this would be fine: https://alive2.llvm.org/ce/z/irgU2q


If there's a better way to communicate this, then please let me know! Assuming ctpop seemed like the best way, though, since x & (x - 1) == 0 gets normalized down to ctpop <= 1, and thus I assumed that it was the preferred way to tell LLVM the value is a power-of-two.

Metadata

Metadata

Assignees

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions