should InstCombine preserve @llvm.assume?

Hi,

I have some WIP that leverages @llvm.assume in some optimization passes other than InstCombine. However, it doesn’t work yet because InstCombine removes @llvm.assume calls that are useful for later optimizations. For example, given

define i32 @foo(i32 %a, i32 %b) {
%sum = add i32 %a, %b
%1 = icmp sge i32 %sum, 0
call void @llvm.assume(i1 %1)
ret i32 %sum
}

“opt -instcombine” emits

define i32 @foo(i32 %a, i32 %b) {
%sum = add i32 %a, %b
ret i32 %sum
}

removing the @llvm.assume call so later optimizations won’t know sum is non-negative any more. (Note that the opt I use here is with http://reviews.llvm.org/D10283 patched. This patch fixes a bug in ValueTracking).

The reasons that InstCombine removes this assume call are:

  1. SimplifyICmpInst proves %1 is true based on the assume call.
  2. then, InstCombine (http://llvm.org/docs/doxygen/html/InstCombineCompares_8cpp_source.html#l02649) replaces all uses of %1 with true including the use in the assume call.
  3. Somewhere later, llvm.assume(true) is considered trivially dead and thus removed from the IR.

Step 2 looks particularly problematic to me. Removing @llvm.assume essentially throws away the base of the proof so we won’t be able to make the same proof any more.

How can we fix this issue? One heavy-handed approach is, instead of RAUW the icmp, we only replace the uses that are not by @llvm.assume. But I have two concerns.

  1. what if the icmp is not directly used by an @llvm.assume? e.g., if we proved a >= 0 and that condition is used in assume(a >= 0 || b >= 0), should we keep (a >= 0) in case later passes use them? If yes, we would probably have to recursively traverse def-use chains. If no, some assumption is again lost after instcombine.

  2. what if the kept assumes are not leveraged later at all? These assumes bump up values’ refcounts and could potentially hurt optimizations. This looks like a problem for adding @llvm.assume in general. Maybe users should be aware of these trade-offs when adding __builtin_assumes in their source code.

Thoughts?

Thanks,
Jingyue

From: "Jingyue Wu" <jingyue@google.com>
To: "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>
Cc: "David Majnemer" <david.majnemer@gmail.com>, "Hal Finkel" <hfinkel@anl.gov>
Sent: Wednesday, June 10, 2015 1:56:54 AM
Subject: should InstCombine preserve @llvm.assume?

Hi,

I have some WIP that leverages @llvm.assume in some optimization
passes other than InstCombine. However, it doesn't work yet because
InstCombine removes @llvm.assume calls that are useful for later
optimizations. For example, given

define i32 @foo(i32 %a, i32 %b) {
%sum = add i32 %a, %b
%1 = icmp sge i32 %sum, 0
call void @llvm.assume(i1 %1)
ret i32 %sum
}

"opt -instcombine" emits

define i32 @foo(i32 %a, i32 %b) {
%sum = add i32 %a, %b
ret i32 %sum
}

removing the @llvm.assume call so later optimizations won't know sum
is non-negative any more. (Note that the opt I use here is with
http://reviews.llvm.org/D10283 patched. This patch fixes a bug in
ValueTracking).

The reasons that InstCombine removes this assume call are:
1) SimplifyICmpInst proves %1 is true based on the assume call.
2) then, InstCombine (
LLVM: lib/Transforms/InstCombine/InstCombineCompares.cpp Source File
) replaces all uses of %1 with true including the use in the assume
call.
3) Somewhere later, llvm.assume(true) is considered trivially dead
and thus removed from the IR.

This is a bug; my guess is that the context instruction is not being set correctly in this case. The @llvm.assume should never be used to simplify instructions that are used only by the @llvm.assume. If the context instruction is set correctly, the logic in isValidAssumeForContext should prevent this.

Feel free to file a bug with this IR and I'll look at it.

Step 2 looks particularly problematic to me. Removing @llvm.assume
essentially throws away the base of the proof so we won't be able to
make the same proof any more.

How can we fix this issue? One heavy-handed approach is, instead of
RAUW the icmp, we only replace the uses that are not by
@llvm.assume. But I have two concerns.

1) what if the icmp is not directly used by an @llvm.assume? e.g., if
we proved a >= 0 and that condition is used in assume(a >= 0 || b >=
0), should we keep (a >= 0) in case later passes use them? If yes,
we would probably have to recursively traverse def-use chains. If
no, some assumption is again lost after instcombine.

2) what if the kept assumes are not leveraged later at all? These
assumes bump up values' refcounts and could potentially hurt
optimizations. This looks like a problem for adding @llvm.assume in
general. Maybe users should be aware of these trade-offs when adding
__builtin_assumes in their source code.

Yes, this is the established tradeoff. The LangRef contains a warning about this explicitly:

"Note that the optimizer might limit the transformations performed on values used by the llvm.assume intrinsic in order to preserve the instructions only used to form the intrinsic’s input argument. This might prove undesirable if the extra information provided by the llvm.assume intrinsic does not cause sufficient overall improvement in code quality. For this reason, llvm.assume should not be used to document basic mathematical invariants that the optimizer can otherwise deduce or facts that are of little use to the optimizer."

-Hal

Thanks! Filed as https://llvm.org/bugs/show_bug.cgi?id=23809.