instcombine generating incorrect range metadata for a ctpop

[regehr]

instcombine takes this code:

define i32 @f(i32 %0) {
  %2 = lshr i32 2048, %0
  %3 = call i32 @llvm.ctpop.i32(i32 %2)
  %4 = freeze i32 %3
  ret i32 %4
}

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i32 @llvm.ctpop.i32(i32) #0

and turns it into:

define i32 @f(i32 %0) {
  %2 = lshr i32 2048, %0
  %.fr = freeze i32 %2
  %3 = call i32 @llvm.ctpop.i32(i32 %.fr), !range !0
  ret i32 %3
}

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i32 @llvm.ctpop.i32(i32) #0

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

!0 = !{i32 0, i32 13}

but the inferred 0..13 range is too tight. to see this, consider that (in the original code) %2 can easily be poison, this happens when %0 is uge 32. then, ctpop(poison) gives poison, and freezing it results in an arbitrary 32-bit value.

cc @nunoplopes

[nunoplopes]

Another example:

define i32 @f(i32 %n22) {
  %n23 = call i32 @llvm.ctlz.i32(i32 %n22, i1 true)
  %n30 = call i32 @llvm.ctpop.i32(i32 %n23)
  %n31 = freeze i32 %n30
  ret i32 %n31
}

declare i32 @llvm.ctlz.i32(i32, i1 immarg)
declare i32 @llvm.ctpop.i32(i32)

[nikic]

Would be solved by specifying !range as poison rather than IUB. But that would also preclude converting !range to assume (I think we don't do this in a default configuration right now, but we do do this for !nonnull and we should have consistent semantics).

[nikic]

Though I guess that just means that frontends should also be emitting !noundef when emitting !range or !nonnull.

[nunoplopes]

Would be solved by specifying !range as poison rather than IUB. But that would also preclude converting !range to assume (I think we don't do this in a default configuration right now, but we do do this for !nonnull and we should have consistent semantics).

The bug here is that the range is wrong. Since the freeze is hoisted past ctpop, you would get poison anyway. So changing the semantics of !range doesn't fix this particular bug.
Not to say that we can't/shouldn't be changing the semantics of !range.

[nikic]

@nunoplopes There are two transforms involved here (I believe): One that annotates ctpop with !range, and the other that pushes freeze through a !canCreateUndefOrPoison op. With our current !range semantics, the first transform is incorrect (because bits are only known up to poison, so this converts poison into IUB), while the second one is correct (because !range does not introduce poison, it causes IUB instead). With altered !range semantics, the first transform becomes correct, and the second one needs to be fixed (because now canCreateUndefOrPoison needs to return true for !range).

So I do think that changing !range semantics would be the first step towards resolving this issue (short of just not annotating with !range at all).

[nunoplopes]

You're right. The !range is not tight enough if anything not the other way around. The range should be [0,1].

!range was introduced to annotate loads of enums. For that use case, UB was fine, since loads are already complicated.
Then we started annotating function calls & intrinsics. For function calls, UB is also fine. It's only for intrinsics that it may cause trouble, since we open the box.
It sounds fine to me to change the semantics. And it's indeed more consistent with what we have these days.

[nikic]

LangRef: https://reviews.llvm.org/D141386

Assuming this goes in I'll work on the optimization changes afterwards.

[nikic]

Should not be closed yet, that was on the first step.