[llvm-dev] Are SCEV normal form?

[Alexandre Isoard via llvm-dev]

Hi Sanjoy,

On Fri, Aug 11, 2017 at 7:37 PM, Sanjoy Das <sanjoy at google.com> wrote:

> Hi Alexandre,
>
> Right now there is no phase where we simplify or canonicalize SCEV
> expressions after their creation -- the shape of a SCEV expression is
> expected to be canonical when you create it.  For this reason the
> right place to do the simplification you suggest is during the
> creation of the SCEV expression itself (createSCEV).
>

I guess I will have to add a new case in getAddExpr. (which is already
huge!)


> If there is a general strategy here that isn't too complex, I'd
> suggest going with that; otherwise detecting some simple patterns that
> you care about is fine too.
>

The idea is to simplify:

    zext(trunc(%a))+shl(lshr(%a))

Into `%a`.

The problem is that sometime trunc has been sunk into %a, and shl/lshr are
encoded as UDiv/Mul.
This is a little bit difficult to match the general case. Also, this can be
generalized in splitting %a into three, or more parts.


> As far as your initial question is concerned (which I am sorry for not
> replying too -- it looks like it slipped through the cracks somehow):
> if there isn't a universal good reason to pick one over the other, I
> think we should just pick one as the normal form as per our
> convenience and teach downstream users to how to effectively use it.
>

Here there is a good reason to pick the zext-trunc version as the
range/known-bits analysis are exact.
While the subtraction make those over-estimated.
I am wondering if I should not generate a zext-trunc-sub-mul-div when it is
not a power-of-two to bound the result of the subtraction...


> For instance, if we choose the zext-trunc version as the canonical
> form then we should teach the 2D array GEP generation logic (not sure
> if there is such a thing in LLVM today?) that is equivalent to the
> udiv-mul form, perhaps by helpers on ScalarEvolution itself.
>

If I fold the add expression the GEP should end up all right by itself.


> Thanks!
> -- Sanjoy


Best regard.

-- 
*Alexandre Isoard*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170815/5b97a83b/attachment.html>