[llvm-dev] LLVM-IR store-load propagation

Fri Jun 19 10:05:17 PDT 2020

Thanks Johannes and Roman for pointing me to those patch proposals (D80991,
D68934). They seem to approach the problem as a way more generic solution
and I'll surely keep an eye on them to see if they'll be merged. From a
quick glance it looks like that after running that analysis pass one would
be able to know the potential values associated with a variable at a
specific point in the code, which would mean the pass I described would be
possible "for free", right? If that's the case I think that more or less
I'm using the llvm::KnownBits in a weakest form to spot the unknown bits in
the index (an integer) and generate the possible values.

The idea of promoting the 'alloca' to be a vector also sounds really
interesting, my only fear is that doing that unconditionally would result
in a non-optimizable representation that would hinder some custom passes
that I have in my pipeline. That's mainly the reason why in the dummy pass
I described in the first email I check if there's at least a chance
(specifically a 'store' to one of the known indexes) for the code to be
optimized. I would gladly read the discussion where the "alloca promotion"
solution has been pointed out if it's available on the mailing list, how
can I find it?

Cheers,
Matteo

Il giorno ven 19 giu 2020 alle ore 10:33 Roman Lebedev <lebedev.ri at gmail.com>
ha scritto:

> On Fri, Jun 19, 2020 at 5:08 AM Johannes Doerfert
> <johannesdoerfert at gmail.com> wrote:
> >
> > Hi Matteo,
> >
> >
> > I think Roman (CC'ed) had a similar problem recently.
> Similar, yes.
>
> > IIRC, the solution that was discussed was to enable memory promotion of
> the alloca into a vector.
> I'm working on that :)
> But i'm not sure if we will be okay doing that unconditionally,
> is spilling going to be able to undo all that?
>
> > Once that happen the existing instcombine logic might already create
> your select.
> >
> > If the above turns out to be not sufficient for a more complex case, you
> might want to
> > consider building something on top of https://reviews.llvm.org/D80991,
> or maybe Shinji (CC'ed)
> > might even ;)
> >
> > Cheers,
> >   Johannes
> Roman
>
> > On 6/18/20 7:28 PM, Matteo Favaro via llvm-dev wrote:
> >
> > Hello everyone,
> >
> > This week I was looking into the following example (
> > https://godbolt.org/z/uhgQcq) where two constants are written to a local
> > array and an input argument, masked and shifted, is used to select
> between
> > them. The possible values for the CC variable are 0 and 1, so I'm
> expecting
> > that at the maximum level of optimizations the two constants are actually
> > propagated, resulting in the return value being a 'select' controlled by
> CC
> > and returning either one or the other.
> >
> > Although, I quickly realized that the implementation in the function
> 'src'
> > was not going to be optimized any further, resulting in the generation of
> > two 'store' instructions and one 'load' instruction, apparently hindering
> > the constant propagation pass.
> >
> > I then decided to explicitly access the local buffer with constant
> indexes
> > and see if LLVM would have been able to identify that CC could have been
> > either 0 or 1 (effectively avoiding the 'default' case of the switch and
> > therefore the '0xdeadc0de' constant). As a result the function 'tgt' is
> > optimized in the way I would expect it to be.
> >
> > This also seemed to be a good exercise for Alive2, so I fed it with the
> > unoptimized 'src' and the optimized 'tgt' functions to prove their
> > equivalence, obtaining the result 'Transformation seems to be correct'.
> As
> > a counter-proof I tampered with the logic or modified the constants,
> > obtaining a valid proof of why the transformation wasn't correct
> > (effectively showing that the original 'src' and 'tgt' functions may
> > actually be semantically equivalent).
> >
> > To replicate the Alive2 result at https://alive2.llvm.org, the following
> > input can be used:
> >
> > define i64 @_Z3srcm(i64 %Flags) {
> > entry:
> >   %Memory = alloca [2 x i64], align 16
> >   %and = lshr i64 %Flags, 6
> >   %shr = and i64 %and, 1
> >   %0 = bitcast [2 x i64]* %Memory to i8*
> >   %arrayidx = getelementptr inbounds [2 x i64], [2 x i64]* %Memory, i64
> 0,
> > i64 0
> >   store i64 5369966919, i64* %arrayidx, align 16
> >   %arrayidx1 = getelementptr inbounds [2 x i64], [2 x i64]* %Memory, i64
> 0,
> > i64 1
> >   store i64 5369966790, i64* %arrayidx1, align 8
> >   %arrayidx2 = getelementptr inbounds [2 x i64], [2 x i64]* %Memory, i64
> 0,
> > i64 %shr
> >   %1 = load i64, i64* %arrayidx2, align 8
> >   ret i64 %1
> > }
> >
> > define i64 @_Z3tgtm(i64 %Flags) {
> > entry:
> >   %0 = and i64 %Flags, 64
> >   %trunc = icmp eq i64 %0, 0
> >   %. = select i1 %trunc, i64 5369966919, i64 5369966790
> >   ret i64 %.
> > }
> >
> > At this point I decided to replicate the 'tgt' function logic and coded a
> > quick LLVM pass that:
> >
> >    1. uses the known/unknown computed bits information to identify a
> >    non-volatile 'load' instruction that uses an index proved to have
> only two
> >    possible values;
> >    2.  check if there's at least one 'store' to the accessed buffer using
> >    one of the two indexes;
> >    3. converts the single 'load' instruction into two 'load' instructions
> >    using the concrete indexes;
> >    4. generates a 'select' instruction that returns one of the two loaded
> >    values, using as condition a check on the index.
> >
> > The pass seems to be working fine, but I'm left wondering if LLVM is
> > purposefully avoiding such an optimization, and if so what is the reason
> to
> > do so (e.g. hard to prove that the optimization is actually going to
> > improve the quality of the code, the logic I'm using is completely off
> the
> > rails).
> >
> > Assuming the logic it's correct and this could be seen as a new custom
> > optimization pass, what would be the suggested way to implement it in a
> > solid and generic fashion?
> >
> > Thanks for any insight,
> > Matteo
> >
> >
> > _______________________________________________
> > 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/20200619/d059b3b7/attachment.html>