[llvm-dev] Normalize a SCEV Expression

[Florian Hahn via llvm-dev]

> 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