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

[Matteo Favaro via llvm-dev]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200619/fd551583/attachment.html>