[LLVMdev] should InstCombine preserve @llvm.assume?

[Hal Finkel]

----- Original Message -----
> From: "Jingyue Wu" <jingyue at google.com>
> To: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>
> Cc: "David Majnemer" <david.majnemer at gmail.com>, "Hal Finkel" <hfinkel at 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 (
> 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.

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

> 
> 
> Thoughts?
> 
> 
> Thanks,
> Jingyue

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory