[SCEV] Consistently Handle Expressions That Cannot Be Divided

[mssimpso]

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.

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

[vaivaswatha]

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]

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

[ssijaric]

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

[mssimpso]

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]

Moved functionality to SCEVAddRecExpr per @ssijaric's request

[mcrosier]

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.

[ssijaric]

In D11725#233066, @mssimpso wrote:

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() ?

[mssimpso]

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

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

[sanjoy]

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?

[mssimpso]

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.

[vaivaswatha]

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

[sanjoy]

In D11725#234430, @mssimpso wrote:

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]

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.

[sanjoy]

lgtm

lib/Analysis/DependenceAnalysis.cpp

if (!isKnownPredicate(CmpInst::ICMP_SGE,
       // if Y may be < X
       NewDirection |= Dependence::DVEntry::GT;
     Level.Direction &= NewDirection;
   }
   else
     llvm_unreachable("constraint has unexpected kind");
 }
 
+/// Check that all recurrences in an expression are affine.
+static bool allAddRecsAffine(const SCEVAddRecExpr *S) {
+
+  // Local struct for the SCEVTraversal. Traverse the expression until a
+  // SCEVAddRecExpr is found that is not affine.
+  struct AllAddRecsAffine {
+    bool IsAffine;
+    AllAddRecsAffine() : IsAffine(true) {}
+    bool follow(const SCEV *S) {
+      if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(S))
+        IsAffine = AddRec->isAffine();
+      return true;
+    }
+    bool isDone() { return !IsAffine; }
+  };
+
+  AllAddRecsAffine Check;
+  SCEVTraversal<AllAddRecsAffine> ST(Check);
+  ST.visitAll(S);
+  return Check.IsAffine;
+}
+
 /// Check if we can delinearize the subscripts. If the SCEVs representing the
 /// source and destination array references are recurrences on a nested loop,
 /// this function flattens the nested recurrences into separate recurrences
 /// for each loop level.
 bool DependenceAnalysis::tryDelinearize(Instruction *Src,
                                         Instruction *Dst,
                                         SmallVectorImpl<Subscript> &Pair)
 {
bool DependenceAnalysis::tryDelinearize(Instruction *Src,
   if (ElementSize != SE->getElementSize(Dst))
     return false;
 
   const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase);
   const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase);
 
   const SCEVAddRecExpr *SrcAR = dyn_cast<SCEVAddRecExpr>(SrcSCEV);
   const SCEVAddRecExpr *DstAR = dyn_cast<SCEVAddRecExpr>(DstSCEV);
-  if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine())
+  if (!SrcAR || !DstAR || !allAddRecsAffine(SrcAR) || !allAddRecsAffine(DstAR))
     return false;
 
   // First step: collect parametric terms in both array references.
   SmallVector<const SCEV *, 4> Terms;
   SE->collectParametricTerms(SrcAR, Terms);
   SE->collectParametricTerms(DstAR, Terms);
 
   // Second step: find subscript sizes.

test/Analysis/DependenceAnalysis/AffineSCEVAddRecExpr.ll

+; REQUIRES: asserts
+; RUN: opt < %s -analyze -basicaa -da-delinearize -da
+;
+; This is a reduced test case from a benchmark in spec2006. We check that this
+; code does not abort.
+;
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n8:16:32-S64"
+target triple = "thumbv7--linux-gnueabi"
+
+define void @f(i32** %a, i32 %n) align 2 {
+for.preheader:
+  %t.0 = ashr exact i32 %n, 3
+  br label %for.body.1
+
+for.body.1:
+  %i.1 = phi i32 [ %t.5, %for.inc ], [ 0, %for.preheader ]
+  %i.2 = phi i32 [ %i.5, %for.inc ], [ %t.0, %for.preheader ]
+  br i1 undef, label %for.inc, label %for.body.2
+
+for.body.2:
+  %i.3 = phi i32 [ %t.1, %for.body.2 ], [ %i.1, %for.body.1 ]
+  %t.1 = add i32 %i.3, 1
+  %t.2 = load i32*, i32** %a, align 4
+  %t.3 = getelementptr inbounds i32, i32* %t.2, i32 %i.3
+  %t.4 = load i32, i32* %t.3, align 4
+  br i1 undef, label %for.inc, label %for.body.2
+
+for.inc:
+  %i.4 = phi i32 [ %i.2, %for.body.1 ], [ %i.2, %for.body.2 ]
+  %t.5 = add i32 %i.1, %i.4
+  %i.5 = add i32 %i.2, -1
+  br i1 undef, label %for.exit, label %for.body.1
+
+for.exit:
+  ret void
+}