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

(On Diff #31243)

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

4 ↗

(On Diff #33223)

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

3281 ↗

(On Diff #33223)

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

3281 ↗

(On Diff #33223)

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

4 ↗

(On Diff #33223)

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

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

if (const SCEVConstant *D = dyn_cast<SCEVConstant>(Denominator)) {
       Quotient = SE.getConstant(QuotientVal);
       Remainder = SE.getConstant(RemainderVal);
       return;
     }
   }
 
   void visitAddRecExpr(const SCEVAddRecExpr *Numerator) {
     const SCEV *StartQ, *StartR, *StepQ, *StepR;
-    assert(Numerator->isAffine() && "Numerator should be affine");
+    if (!Numerator->isAffine())
+      return cannotDivide(Numerator);
     divide(SE, Numerator->getStart(), Denominator, &StartQ, &StartR);
     divide(SE, Numerator->getStepRecurrence(SE), Denominator, &StepQ, &StepR);
     // Bail out if the types do not match.
     Type *Ty = Denominator->getType();
     if (Ty != StartQ->getType() || Ty != StartR->getType() ||
-        Ty != StepQ->getType() || Ty != StepR->getType()) {
-      Quotient = Zero;
-      Remainder = Numerator;
-      return;
-    }
+        Ty != StepQ->getType() || Ty != StepR->getType())
+      return cannotDivide(Numerator);
     Quotient = SE.getAddRecExpr(StartQ, StepQ, Numerator->getLoop(),
                                 Numerator->getNoWrapFlags());
     Remainder = SE.getAddRecExpr(StartR, StepR, Numerator->getLoop(),
                                  Numerator->getNoWrapFlags());
   }
 
   void visitAddExpr(const SCEVAddExpr *Numerator) {
     SmallVector<const SCEV *, 2> Qs, Rs;
     Type *Ty = Denominator->getType();
 
     for (const SCEV *Op : Numerator->operands()) {
       const SCEV *Q, *R;
       divide(SE, Op, Denominator, &Q, &R);
 
       // Bail out if types do not match.
-      if (Ty != Q->getType() || Ty != R->getType()) {
-        Quotient = Zero;
-        Remainder = Numerator;
-        return;
-      }
+      if (Ty != Q->getType() || Ty != R->getType())
+        return cannotDivide(Numerator);
 
       Qs.push_back(Q);
       Rs.push_back(R);
     }
 
     if (Qs.size() == 1) {
       Quotient = Qs[0];
       Remainder = Rs[0];
       return;
     }
 
     Quotient = SE.getAddExpr(Qs);
     Remainder = SE.getAddExpr(Rs);
   }
 
   void visitMulExpr(const SCEVMulExpr *Numerator) {
     SmallVector<const SCEV *, 2> Qs;
     Type *Ty = Denominator->getType();
 
     bool FoundDenominatorTerm = false;
     for (const SCEV *Op : Numerator->operands()) {
       // Bail out if types do not match.
-      if (Ty != Op->getType()) {
-        Quotient = Zero;
-        Remainder = Numerator;
-        return;
-      }
+      if (Ty != Op->getType())
+        return cannotDivide(Numerator);
 
       if (FoundDenominatorTerm) {
         Qs.push_back(Op);
         continue;
       }
 
       // Check whether Denominator divides one of the product operands.
       const SCEV *Q, *R;
       divide(SE, Op, Denominator, &Q, &R);
       if (!R->isZero()) {
         Qs.push_back(Op);
         continue;
       }
 
       // Bail out if types do not match.
-      if (Ty != Q->getType()) {
-        Quotient = Zero;
-        Remainder = Numerator;
-        return;
-      }
+      if (Ty != Q->getType())
+        return cannotDivide(Numerator);
 
       FoundDenominatorTerm = true;
       Qs.push_back(Q);
     }
 
     if (FoundDenominatorTerm) {
       Remainder = Zero;
       if (Qs.size() == 1)
         Quotient = Qs[0];
       else
         Quotient = SE.getMulExpr(Qs);
       return;
     }
 
-    if (!isa<SCEVUnknown>(Denominator)) {
-      Quotient = Zero;
-      Remainder = Numerator;
-      return;
-    }
+    if (!isa<SCEVUnknown>(Denominator))
+      return cannotDivide(Numerator);
 
     // The Remainder is obtained by replacing Denominator by 0 in Numerator.
     ValueToValueMap RewriteMap;
     RewriteMap[cast<SCEVUnknown>(Denominator)->getValue()] =
         cast<SCEVConstant>(Zero)->getValue();
     Remainder = SCEVParameterRewriter::rewrite(Numerator, SE, RewriteMap, true);
 
     if (Remainder->isZero()) {
       // The Quotient is obtained by replacing Denominator by 1 in Numerator.
       RewriteMap[cast<SCEVUnknown>(Denominator)->getValue()] =
           cast<SCEVConstant>(One)->getValue();
       Quotient =
           SCEVParameterRewriter::rewrite(Numerator, SE, RewriteMap, true);
       return;
     }
 
     // Quotient is (Numerator - Remainder) divided by Denominator.
     const SCEV *Q, *R;
     const SCEV *Diff = SE.getMinusSCEV(Numerator, Remainder);
-    if (sizeOfSCEV(Diff) > sizeOfSCEV(Numerator)) {
-      // This SCEV does not seem to simplify: fail the division here.
-      Quotient = Zero;
-      Remainder = Numerator;
-      return;
-    }
+    if (sizeOfSCEV(Diff) > sizeOfSCEV(Numerator))
+      return cannotDivide(Numerator);
     divide(SE, Diff, Denominator, &Q, &R);
-    assert(R == Zero &&
-           "(Numerator - Remainder) should evenly divide Denominator");
+    if (R != Zero)
+      return cannotDivide(Numerator);
     Quotient = Q;
   }
 
 private:
   SCEVDivision(ScalarEvolution &S, const SCEV *Numerator,
                const SCEV *Denominator)
       : SE(S), Denominator(Denominator) {
     Zero = SE.getConstant(Denominator->getType(), 0);
     One = SE.getConstant(Denominator->getType(), 1);
 
-    // By default, we don't know how to divide Expr by Denominator.
-    // Providing the default here simplifies the rest of the code.
+    // We generally do not know how to divide Expr by Denominator. We
+    // initialize the division to a "cannot divide" state to simplify the rest
+    // of the code.
+    cannotDivide(Numerator);
+  }
+
+  // Convenience function for giving up on the division. We set the quotient to
+  // be equal to zero and the remainder to be equal to the numerator.
+  void cannotDivide(const SCEV *Numerator) {
     Quotient = Zero;
     Remainder = Numerator;
   }
 
   ScalarEvolution &SE;
   const SCEV *Denominator, *Quotient, *Remainder, *Zero, *One;
 };
 

llvm/trunk/test/Analysis/DependenceAnalysis/NonAffineExpr.ll

+; RUN: opt < %s -analyze -basicaa -da-delinearize -da
+;
+; CHECK: da analyze - consistent input [S S]!
+; CHECK: da analyze - confused!
+; CHECK: da analyze - input [* *]!
+;
+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
+}