llvm dev - Jun 2015 - [LLVMdev] 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150609/33d30f0e/attachment.html>

----- 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

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

On Wed, Jun 10, 2015 at 5:32 AM, Hal Finkel <hfinkel at anl.gov> wrote:
> ----- 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150610/af76a9fe/attachment.html>