This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Make getPostIncExpr guaranteed to return AddRec
ClosedPublic

Authored by mkazantsev on Feb 6 2018, 3:32 AM.

Details

Summary

The current implementation of getPostIncExpr invokes getAddExpr for two recurrencies
and expects that it always returns it a recurrency. But this is not guaranteed to happen if we
have reached max recursion depth or refused to make SCEV simplification for other reasons.

This patch changes its implementation so that now it always returns SCEVAddRec without
relying on getAddExpr.

Diff Detail

Event Timeline

mkazantsev created this revision.Feb 6 2018, 3:32 AM
sanjoy requested changes to this revision.Feb 6 2018, 1:11 PM
sanjoy added inline comments.
lib/Analysis/ScalarEvolution.cpp
10221

This is unnecessary -- the step for {A,+,B,+,C} will always be {B,+,C} so we should be able to use Ops.push_back(SE.getAddExpr(getOperand(i), getOperand(i+1))); in the loop below.

10223

Also state why we can't guarantee it (SCEV does not simplify to fixed point etc.).

10224

I didn't quite understand what you meant by "last op of this is non zero".

This revision now requires changes to proceed.Feb 6 2018, 1:11 PM
mkazantsev added inline comments.Feb 6 2018, 8:51 PM
lib/Analysis/ScalarEvolution.cpp
10224

When we create an AddRecurrency, if we found out that the last stey was zero we pop it out. For example, if we add {1,+,1} and {2,+,-1}, we have {1+2,+,1-1} where the last element is zero, so it will be removed. It means that whatever the last operand in this is, it is NOT a constant zero (otherwise it would have been removed earlier). The fact that the returned value has the same value as its last element guarantees as that the returned value is an AddRec.

mkazantsev updated this revision to Diff 133146.Feb 6 2018, 9:40 PM
mkazantsev marked 3 inline comments as done.
sanjoy accepted this revision.Feb 9 2018, 4:54 PM

lgtm

lib/Analysis/ScalarEvolution.cpp
10232

"We know that the last operand is not a constant zero" -> might be nice to assert this.

This revision is now accepted and ready to land.Feb 9 2018, 4:54 PM
mkazantsev added inline comments.Feb 11 2018, 8:07 PM
lib/Analysis/ScalarEvolution.cpp
10232

Will do.

This revision was automatically updated to reflect the committed changes.