Missed optimization between range parameter metadata and assumes

[scottmcm]

Now that range parameter metadata exists (🎉) I'm trying to remove some of our assumes that rustc outputs which should no longer be necessary (rust-lang/rust#135610).

That works for almost all of our tests in https://github.com/rust-lang/rust/blob/master/tests/codegen/transmute-optimized.rs , but one.

We end up, after optimizations, still getting

define noundef range(i8 1, 4) i8 @ordering_transmute_onetwothree(i8 noundef returned range(i8 -1, 2) %x) unnamed_addr #2 {
start:
  %0 = icmp ne i8 %x, 0
  tail call void @llvm.assume(i1 %0)
  %1 = icmp ult i8 %x, 4
  tail call void @llvm.assume(i1 %1)
  ret i8 %x
}

That input range is [-1, 2) and those assumes are a range [1, 4), so it ought to simplify to just ret i8 1, but it doesn't.

Alive2 proof that it would be legal: https://alive2.llvm.org/ce/z/GucQsJ -- and legal even without the range on the return value.

Maybe this is somehow related to the x uge 1 being turned into x ne 0, and thus it not noticing there's a range? Or maybe it's something about the wrap-around?

SEO: rust transmute range bounds

---

As an aside, I'd love to emit these as range assume operand bundles instead of icmps, but AFAICT those don't exist yet, so I'm stuck with the icmps for now 🙁

[dtcxzyw]

I cannot reproduce this issue: https://godbolt.org/z/aeh996njM It should be simplified by CVP/SCCP.

BTW, if the range is known in the frontend, you can convert it into the canonical form (X + offset) upred C instead of two comparisons. For example, you should emit assume(x - 1 u< 3) for [1, 4). See also ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS, APInt &Offset).

[scottmcm]

I cannot reproduce this issue

On nightly there's a another assume for the input that's a duplicate of the range metadata, which is how that passes.

Adding -C no-prepopulate-passes to your link I get https://godbolt.org/z/K5c55dP5q

define noundef range(i8 1, 4) i8 @ordering_transmute_onetwothree(i8 noundef range(i8 -1, 2) %x) unnamed_addr {
start:
  %x.dbg.spill = alloca [1 x i8], align 1
  store i8 %x, ptr %x.dbg.spill, align 1
  %0 = icmp uge i8 %x, -1
  %1 = icmp ule i8 %x, 1
  %2 = or i1 %0, %1
  call void @llvm.assume(i1 %2)
  %3 = icmp uge i8 %x, 1
  call void @llvm.assume(i1 %3)
  %4 = icmp ule i8 %x, 3
  call void @llvm.assume(i1 %4)
  ret i8 %x
}

Where it's that first of the three assumes that enables the optimization, even though that assume should be a complete duplicate of the range(i8 -1, 2).

And sorry for not providing a repro link earlier, but here's one with opt trunk: https://llvm.godbolt.org/z/c4jascGah

For example, you should emit assume(x - 1 u< 3) for [1, 4).

Oh, if that's better I'll absolutely do that. Thanks!

[dtcxzyw]

I am trying to avoid breaking assume((icmp X, C1) && (icmp X, C2)) into two assumptions in InstCombine.

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

Lines 3164 to 3183 in 7253c6f

	// Canonicalize assume(a && b) -> assume(a); assume(b);
	// Note: New assumption intrinsics created here are registered by
	// the InstCombineIRInserter object.
	FunctionType *AssumeIntrinsicTy = II->getFunctionType();
	Value *AssumeIntrinsic = II->getCalledOperand();
	Value *A, *B;
	if (match(IIOperand, m_LogicalAnd(m_Value(A), m_Value(B)))) {
	Builder.CreateCall(AssumeIntrinsicTy, AssumeIntrinsic, A, OpBundles,
	II->getName());
	Builder.CreateCall(AssumeIntrinsicTy, AssumeIntrinsic, B, II->getName());
	return eraseInstFromFunction(*II);
	}
	// assume(!(a || b)) -> assume(!a); assume(!b);
	if (match(IIOperand, m_Not(m_LogicalOr(m_Value(A), m_Value(B))))) {
	Builder.CreateCall(AssumeIntrinsicTy, AssumeIntrinsic,
	Builder.CreateNot(A), OpBundles, II->getName());
	Builder.CreateCall(AssumeIntrinsicTy, AssumeIntrinsic,
	Builder.CreateNot(B), II->getName());
	return eraseInstFromFunction(*II);
	}

[scottmcm]

Update: I locally changed how rustc emits those assumes, and it fixed the test! 🎉

Now I get

define noundef range(i8 1, 4) i8 @ordering_transmute_onetwothree(i8 noundef range(i8 -1, 2) %x) unnamed_addr #2 {
start:
  %0 = add nsw i8 %x, -1
  %1 = icmp ult i8 %0, 3
  tail call void @llvm.assume(i1 %1)
  ret i8 1
}

And the compiler need to do less work to emit these in the first place, so beautiful.

Thank you, @dtcxzyw! I appreciate your help ❤

Up to you if you want to keep this open or close it as "frontend doing it wrong".

[dtcxzyw]

I am trying to avoid breaking assume((icmp X, C1) && (icmp X, C2)) into two assumptions in InstCombine.

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

Lines 3164 to 3183 in 7253c6f

// Canonicalize assume(a && b) -> assume(a); assume(b);
// Note: New assumption intrinsics created here are registered by
// the InstCombineIRInserter object.
FunctionType *AssumeIntrinsicTy = II->getFunctionType();
Value *AssumeIntrinsic = II->getCalledOperand();
Value *A, *B;
if (match(IIOperand, m_LogicalAnd(m_Value(A), m_Value(B)))) {
Builder.CreateCall(AssumeIntrinsicTy, AssumeIntrinsic, A, OpBundles,
II->getName());
Builder.CreateCall(AssumeIntrinsicTy, AssumeIntrinsic, B, II->getName());
return eraseInstFromFunction(*II);
}
// assume(!(a || b)) -> assume(!a); assume(!b);
if (match(IIOperand, m_Not(m_LogicalOr(m_Value(A), m_Value(B))))) {
Builder.CreateCall(AssumeIntrinsicTy, AssumeIntrinsic,
Builder.CreateNot(A), OpBundles, II->getName());
Builder.CreateCall(AssumeIntrinsicTy, AssumeIntrinsic,
Builder.CreateNot(B), II->getName());
return eraseInstFromFunction(*II);
}

Confirmed that it doesn't help :(