This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Consistently Handle Expressions That Cannot Be Divided
ClosedPublic

Authored by mssimpso on Aug 3 2015, 9:24 AM.

Details

Summary

This patch addresses the issue of SCEV division asserting on some input
expressions (e.g., non-affine expressions) and quietly giving up on others.
When giving up, we set the quotient to be equal to zero and the remainder to be
equal to the numerator. With this patch, we always quietly give up when we
cannot perform the division.

This patch also adds a test case for DependenceAnalysis that previously caused
an assertion.

Diff Detail

Event Timeline

mssimpso updated this revision to Diff 31243.Aug 3 2015, 9:24 AM
mssimpso retitled this revision from to [DependenceAnalysis] Ensure All Recurrences are Affine.
mssimpso updated this object.
mssimpso added reviewers: sebpop, grosser.
mssimpso added a subscriber: llvm-commits.
jingyue resigned from this revision.Aug 11 2015, 8:50 PM
jingyue removed a reviewer: jingyue.

I don't see any obvious problem, but I don't have enough expertise on DependenceAnalysis to LGTM it unfortunately.

lib/Analysis/DependenceAnalysis.cpp
3244

Nit: the comment is incorrect. This function only checks if all recurrences are affine instead of ensuring that.

It would be helpful if the test case attached had the source loop as a comment, similar to the other test cases for DependenceAnalysis.

Also, I have a related change http://reviews.llvm.org/D11771 that actually fixes the way delinearizer is called (its currently called incorrectly). If useful to you, please have a look, and possibly review.

mssimpso updated this revision to Diff 32726.Aug 20 2015, 1:15 PM
mssimpso added a subscriber: jingyue.

@jingyue:

Thanks for the correction. I've updated the comment.

@vaivaswatha:

Thanks for pointing me to D11771. I was curious to know if your change would
prevent the attached test case from aborting, but it did not. This test case is
reduced from a benchmark in spec2006, and we just need to check that it doesn't
abort. I'm not sure it would be very meaningful to translate it back into the
source language. Other DependenceAnalysis tests (e.g., Constraints.ll,
Invariant.ll) seem to do the same.

mssimpso marked an inline comment as done.Aug 20 2015, 1:17 PM
mssimpso added a subscriber: mcrosier.

Hi Matthew,

Would it be possible to make allAddRecsAffine a non-static function? We are running into the same problem with delinearization in polly, and need to do the same check from there.

Thanks,
Sanjin

Sanjin,

What do you think about adding an isAffineRecursive() along side isAffine() in SCEVAddRecExpr? Would that work for you? But doesn't Polly's SCEVValidator already walk the entire expression to check this?

mssimpso updated this revision to Diff 33223.Aug 26 2015, 10:58 AM

Moved functionality to SCEVAddRecExpr per @ssijaric's request

mcrosier added inline comments.Aug 26 2015, 12:02 PM
test/Analysis/DependenceAnalysis/AffineSCEVAddRecExpr.ll
5

Is it valuable to comments this is a reduced test case from spec? Perhaps we could just say:

"We check that this reduced test case does not abort."

This suggestion doesn't require a revised patch, if accepted. Just make the change before committing the patch.

Sanjin,

What do you think about adding an isAffineRecursive() along side isAffine() in SCEVAddRecExpr? Would that work for you? But doesn't Polly's SCEVValidator already walk the entire expression to check this?

Thanks, Matthew. That will work.

Polly didn't call SCEVValidator via isAffineExpr where the error occurs - it seems to rely on SCEVAddRecExpr::computeAccessFunctions to bail out if the expression is not affine. SCEVAddRecExpr::computeAccessFunctions has the following check at the start:

void SCEVAddRecExpr::computeAccessFunctions(

  ScalarEvolution &SE, SmallVectorImpl<const SCEV *> &Subscripts,
  SmallVectorImpl<const SCEV *> &Sizes) const {

// Early exit in case this SCEV is not an affine multivariate function.
if (Sizes.empty() || !this->isAffine())
  return;

....
...

Would it be valid to change !this->isAffine() to !this->isAffineRecursive() ?

Would it be valid to change !this->isAffine() to !this->isAffineRecursive() ?

Assuming the patch is accepted, yes I believe that would work.

mcrosier removed a subscriber: mcrosier.Aug 26 2015, 2:55 PM
sanjoy edited edge metadata.Aug 27 2015, 12:23 AM

I have two general questions, only tangentially related to this review (because I'm not familiar with this piece of code):

  • What is the difference between DependenceAnalysis::tryDelinearize and ScalarEvolution::delinearize?
  • It looks like SCEVDivision bails out on things other than non-affine add recs (e.g. on SCEVUnknowns). Why are those okay? IOW, is the failing assert too strong? This is assuming that the only problem with a nested non-affine add rec is that the SCEVDivision aborts, are there other problems too?
include/llvm/Analysis/ScalarEvolutionExpressions.h
320 ↗(On Diff #33223)

Nit: SCEVAddRecExprs

lib/Analysis/DependenceAnalysis.cpp
3303

Why not move this check to ScalarEvolution::computeAccessFunctions?

Sanjoy,

Thanks very much for joining the review and providing feedback. I very much appreciate it!

What is the difference between DependenceAnalysis::tryDelinearize and ScalarEvolution::delinearize?

As far as I know, there shouldn't be a difference here regarding the actual computation. In fact, before the most recent rewrite that split the computation into 3 phases, tryDelinearize called delinearize directly. Perhaps @sebpop can provide more insight. Otherwise, I will look into restoring that feature to avoid duplication.

It looks like SCEVDivision bails out on things other than non-affine add recs (e.g. on SCEVUnknowns). Why are those okay? IOW, is the failing assert too strong?

If you're asking why the divide function gives up on some cases (appropriately setting the quotient to be zero and the remainder to be the original dividend) and instead asserts on the non-affine add rec case, I think that's a valid point. Does it make sense to quietly give up here instead of asserting?

This is assuming that the only problem with a nested non-affine add rec is that the SCEVDivision aborts, are there other problems too?

None that I'm aware of specifically, although see @ssijaric's comment above regarding a similar issue in Polly. The add rec does indeed need to be affine to divide. If it is not, getSetRecurrence() will construct a new add rec, and so on, and we may never be able to traverse the entire expression. It also seems that having an easy way to recursively check whether an add rec is affine would be useful. Any more thoughts you might have on bailing vs. asserting would be helpful. Thanks, again.

include/llvm/Analysis/ScalarEvolutionExpressions.h
320 ↗(On Diff #33223)

Nice catch! Thank you.

lib/Analysis/DependenceAnalysis.cpp
3303

I agree. computeAccessFunctions already checks that the expression is an affine add rec. We would only need to change the check to the recursive version.

test/Analysis/DependenceAnalysis/AffineSCEVAddRecExpr.ll
5

I agree. Thanks, Chad.

What is the difference between DependenceAnalysis::tryDelinearize and ScalarEvolution::delinearize?

As far as I know, there shouldn't be a difference here regarding the actual computation. In fact, before the most recent rewrite that split the computation into 3 phases, tryDelinearize called delinearize directly. Perhaps @sebpop can provide more insight. Otherwise, I will look into restoring that feature to avoid duplication.

It looks like calling ScalarEvolution::delinearize is not the same as what is happening here. findArrayDimensions() here is being called with the Terms from both Src and Dst. This is probably not the same as calling it separately (which is what would happen if ScalarEvolution::delinearize is called).

If you're asking why the divide function gives up on some cases (appropriately setting the quotient to be zero and the remainder to be the original dividend) and instead asserts on the non-affine add rec case, I think that's a valid point. Does it make sense to quietly give up here instead of asserting?

As someone who does not know the details of DependenceAnalysis, I'd say yes. That makes the behavior consistent between non-affine add recurrences and other SCEV expressions that cannot be divided.

mssimpso updated this revision to Diff 34271.Sep 8 2015, 3:12 PM
mssimpso edited edge metadata.

Updating revision to address comments.

@sanjoy, I've updated this revision so that we consistently handle expressions
that we cannot divide. We will now give up on the non-affine case instead of
asserting. Because we give up quietly, there's no longer a need to change the
callers of the division. Thanks for the suggestion.

mssimpso retitled this revision from [DependenceAnalysis] Ensure All Recurrences are Affine to [SCEV] Consistently Handle Expressions That Cannot Be Divided.Sep 8 2015, 3:16 PM
mssimpso updated this object.
sanjoy accepted this revision.Sep 9 2015, 5:17 PM
sanjoy edited edge metadata.

lgtm

This revision is now accepted and ready to land.Sep 9 2015, 5:17 PM
This revision was automatically updated to reflect the committed changes.