llvm dev - May 2021 - llvm.assume after CodeGenPrepare

With recent changes in BasicAA (mostly by Nikita Popov I believe) llvm.assumes
can now guide in the AA decision making. Which is of course great.

For example for C input (or IR equivalent) as follows it can make a huge
difference if the variable 'x' is known to be non-zero when AA is
queried during scheduling

__builtin_assume(x != 0);
for (int i = 0; i < 64; i += 4) {
  v[(i + 0) * x] = v[(i + 0) * x] >> 2;
  v[(i + 1) * x] = v[(i + 1) * x] >> 2;
  v[(i + 2) * x] = v[(i + 2) * x] >> 2;
  v[(i + 3) * x] = v[(i + 3) * x] >> 2;
}

Unfortunately it appears that the CodeGenPrepare pass removes llvm.assume so
that they never reach the code generator. Currently commit 91c9dee3fb6d89ab3
(and before that commit 6d20937c29a1a1d67) eliminate assumptions in
CodeGenPrepare for reasons that appear to be optimization (avoiding blocks that
would be empty if it was not for the llvm.assume and its predecessors).

It seems these two efforts are quite contradictory. Is there any deeper thinking
behind this? I for one would be in favor of not eliminating assumes.

-Markus
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210525/050b1757/attachment.html>

On Tue, May 25, 2021 at 12:11 PM Markus Lavin <markus.lavin at
ericsson.com> wrote:
> With recent changes in BasicAA (mostly by Nikita Popov I believe)
llvm.assumes can now guide in the AA decision making. Which is of course great.
>
>
>
> For example for C input (or IR equivalent) as follows it can make a huge
difference if the variable ‘x’ is known to be non-zero when AA is queried during
scheduling
>
>
>
> __builtin_assume(x != 0);
>
> for (int i = 0; i < 64; i += 4) {
>
>   v[(i + 0) * x] = v[(i + 0) * x] >> 2;
>
>   v[(i + 1) * x] = v[(i + 1) * x] >> 2;
>
>   v[(i + 2) * x] = v[(i + 2) * x] >> 2;
>
>   v[(i + 3) * x] = v[(i + 3) * x] >> 2;
>
> }
>
>
>
> Unfortunately it appears that the CodeGenPrepare pass removes llvm.assume
so that they never reach the code generator. Currently commit 91c9dee3fb6d89ab3
(and before that commit 6d20937c29a1a1d67) eliminate assumptions in
CodeGenPrepare for reasons that appear to be optimization (avoiding blocks that
would be empty if it was not for the llvm.assume and its predecessors).
>
>
>
> It seems these two efforts are quite contradictory. Is there any deeper
thinking behind this? I for one would be in favor of not eliminating assumes.
Well, I'm fairly new to LLVM and don't really have much of a clue
about this. I just wanted to make a small improvement on top of the
existing work from 6d20937c29a1a1d67 without thinking all that much
about the overall design; and since codegenprepare was already
stripping it, I thought it would be safe to assume that no later pass
would use this information.


I was writing some code like this:

    assert(ptr != nullptr || !ret); // no-op in release builds
    __builtin_assume(ptr != nullptr || !ret);

Then I figured that it would look nicer and might (?) be nicer on the
optimizer to instead make it look like this:

    if (ptr == nullptr) {
        assert(!ret); // no-op in release builds
        __builtin_assume(!ret);
    }

but when I tried that, the result was that because the llvm.assume
only got stripped in a later part of the codegenprepare pass, the
branch condition was never eliminated (see
https://chromium-review.googlesource.com/c/chromium/src/+/2727400/2/base/memory/checked_ptr.h#120).
That seemed wrong to me; and since I saw that it was already stripped
later on in codegenprepare, I thought it'd be a good idea to do it a
bit earlier to allow removing the branch entirely.


I guess if you wanted to keep llvm.assume information around without
creating empty blocks, you'd have to instead let the codegenprepare
pass figure out whether blocks are empty except for llvm.assume and
its speculatable dependencies, and if so, either discard the whole
block or rewrite "if (COND1) __builtin_assume(COND2)" to something
like "__builtin_assume(!COND1 || COND2)"?

I think there's two interacting pieces here:

  * I don't believe we have a way to represent an assume at the MI
    layer.  If we let them flow through codegen, we'd need to add such a
    thing.
  * The tradeoffs between information preservation and lowering may be
    different at different points in the pipeline.  Johannes frames this
    as a canonicalization problem.  That sounds reasonable, but it's
    also reasonable that we may need to give up on preserving assumes at
    some point.  (As a silly example, we probably don't want them at
    MC.)  Where exactly that point is unclear, and is mostly a matter of
    practical engineering tradeoffs.

If you felt like exploring alternate lowering points, that would seem 
entirely reasonable.  It might not work out, or it might require a bunch 
of work to make happen, but the basic idea seems entirely worth exploring.

Philip

On 5/25/21 3:11 AM, Markus Lavin via llvm-dev wrote:
>
> With recent changes in BasicAA (mostly by Nikita Popov I believe) 
> llvm.assumes can now guide in the AA decision making. Which is of 
> course great.
>
> For example for C input (or IR equivalent) as follows it can make a 
> huge difference if the variable ‘x’ is known to be non-zero when AA is 
> queried during scheduling
>
> __builtin_assume(x != 0);
>
> for (int i = 0; i < 64; i += 4) {
>
>   v[(i + 0) * x] = v[(i + 0) * x] >> 2;
>
>   v[(i + 1) * x] = v[(i + 1) * x] >> 2;
>
>   v[(i + 2) * x] = v[(i + 2) * x] >> 2;
>
> v[(i + 3) * x] = v[(i + 3) * x] >> 2;
>
> }
>
> Unfortunately it appears that the CodeGenPrepare pass removes 
> llvm.assume so that they never reach the code generator. Currently 
> commit 91c9dee3fb6d89ab3 (and before that commit 6d20937c29a1a1d67) 
> eliminate assumptions in CodeGenPrepare for reasons that appear to be 
> optimization (avoiding blocks that would be empty if it was not for 
> the llvm.assume and its predecessors).
>
> It seems these two efforts are quite contradictory. Is there any 
> deeper thinking behind this? I for one would be in favor of not 
> eliminating assumes.
>
> -Markus
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210525/dc241bb1/attachment.html>