llvm dev - Jul 2020 - Normalize a SCEV Expression

Hi,

I have a SCEV like this: {16,+,8}. Say that this came from a loop like:
int64_t *p;
for (int64_t i = 0; i < ...; ++i)
  p[i+2]...

And assuming that I'm on a 64-bit machine. What I would like to do is
normalize it
like that, basically this: {2,+,1} i.e. map it to the index.

Now, I tried to get the underlying element size of the pointer, then
getUDivExpr(OriginalSCEV, ElementSize); But I don't get the desired SCEV
back. Instead I'm getting:
{16,+,8} \u 8, i.e. just adding udiv in the original expression.

Why is this not simplified?

Thanks,
Stefanos Baziotis
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200730/ffc5f897/attachment.html>

> On Jul 30, 2020, at 21:03, Stefanos Baziotis via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi,
> 
> I have a SCEV like this: {16,+,8}. Say that this came from a loop like:
> int64_t *p;
> for (int64_t i = 0; i < ...; ++i)
>   p[i+2]...
> 
> And assuming that I'm on a 64-bit machine. What I would like to do is
normalize it
> like that, basically this: {2,+,1} i.e. map it to the index.
> 
> Now, I tried to get the underlying element size of the pointer, then
getUDivExpr(OriginalSCEV, ElementSize); But I don't get the desired SCEV
back. Instead I'm getting:
> {16,+,8} \u 8, i.e. just adding udiv in the original expression.
> 

I guess the problem here is that the AddRec is missing overflow flags, which
means the expression may overflow and if that happens, the folded expression may
not be equivalent to the original one in all cases.

If the AddRec has the overflow flags set, it looks something like
`{16,+,8}<nuw><nsw><%loop>`. I’d check if the original IR had
nuw/nsw flags on add instruction for the AddRec. The way those flags are managed
in SCEV are sometimes a bit surprising, because the expressions are not tied to
a specific location and the flags need to be valid for the whole scope the
expression can be evaluated in.

Cheers,
Florian

Indeed you're right, thanks! I need a nuw (which I have to invent, with a
run-time check, since it doesn't exist in the original but anyway).

Best,
Stefanos

Στις Παρ, 31 Ιουλ 2020 στις 12:36 μ.μ., ο/η Florian Hahn <
florian_hahn at apple.com> έγραψε:
>
>
> > On Jul 30, 2020, at 21:03, Stefanos Baziotis via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
> >
> > Hi,
> >
> > I have a SCEV like this: {16,+,8}. Say that this came from a loop
like:
> > int64_t *p;
> > for (int64_t i = 0; i < ...; ++i)
> >   p[i+2]...
> >
> > And assuming that I'm on a 64-bit machine. What I would like to do
is
> normalize it
> > like that, basically this: {2,+,1} i.e. map it to the index.
> >
> > Now, I tried to get the underlying element size of the pointer, then
> getUDivExpr(OriginalSCEV, ElementSize); But I don't get the desired
SCEV
> back. Instead I'm getting:
> > {16,+,8} \u 8, i.e. just adding udiv in the original expression.
> >
>
>
> I guess the problem here is that the AddRec is missing overflow flags,
> which means the expression may overflow and if that happens, the folded
> expression may not be equivalent to the original one in all cases.
>
> If the AddRec has the overflow flags set, it looks something like
> `{16,+,8}<nuw><nsw><%loop>`. I’d check if the original IR
had nuw/nsw flags
> on add instruction for the AddRec. The way those flags are managed in SCEV
> are sometimes a bit surprising, because the expressions are not tied to a
> specific location and the flags need to be valid for the whole scope the
> expression can be evaluated in.
>
> Cheers,
> Florian
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200731/89f38386/attachment.html>