Normalize a SCEV Expression


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)

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?

Stefanos Baziotis

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.


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).


Στις Παρ, 31 Ιουλ 2020 στις 12:36 μ.μ., ο/η Florian Hahn <> έγραψε:

Right, I guess in your example, the flags on the add depend on the exact bound of the loop, which is omitted.


Στις Παρ, 31 Ιουλ 2020 στις 2:44 μ.μ., ο/η Florian Hahn <> έγραψε: