Support sext instruction in SCEV delinearization algorithm (new revision)

[alexsusu]

Summary

This patch incorporates also the one from https://reviews.llvm.org/D35478 in order to make it work well for SCEVDivision, when having SExt expressions.
Before the patch, SCEVDivision::divide() was not working due to casts (SExt, etc). This was manifesting for example when used in the delinearization algorithm of Polly, implemented in ScopDetection.cpp (note that ScalarEvolution.cpp seems to have a delinearize() method also which is an appendix), which needs to perform SCEV division.

Delinearization does (see paper Grosser et al, "On recovering Multi-dimensional Arrays in Polly", IMPACT 2015, Section 4 - http://impact.gforge.inria.fr/impact2015/papers/impact2015-grosser.pdf ):
    - sum of product expansion
    - after a simple removal process, products are sorted by the number of factors
    - check that the smaller terms in the sorted array divide the larger ones
    - symbolically divide the original offset expression by the size of the individual array dimensions starting from the innermost dimension .
Note that I did not check to see if the sum of product expansion gives in certain corner cases errors due to ScalarEvolution.

However, even the initial patch (from  https://reviews.llvm.org/D35478) had "bugs" - it was not working because it was not treating the Nominator.
Therefore, we are now treating it for cast expressions. Note that SCEVDivision is a SCEVVisitor - see http://llvm.org/doxygen/ScalarEvolutionExpressions_8h_source.html#l00445: we see that we only need to treat it for Trunc, ZExt, SExt - methods visitTruncateExpr(), visitZeroExtendExpr(), visitSignExtendExpr(). Note that in this patch we only address the SExt.
We also had to adapt numberOfTerms() to treat for cast expressions.

[efriedma]

Please post patches with full context (http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface)

Missing unit-tests.

Please put the rename into a separate patch; it makes the functional changes more difficult to review.

I don't think you can "ignore" all these operations like this; I mean, I can see ignoring sign-extension because it's signed division, but zero-extension or truncation actually changes the result. (4294967300/4294967298 is very different from 4/2.)

[Meinersbur]

Thanks Alex for the patch. I just see it now. As Eli is mentioning already, could you separate the patch into separate differentials?

• One for renaming nominator/denominator to dividend/divisor. It will be discussed/decided on independently.
• One for allowing sext in delinerization (this differential, please add at least one unit-test)
• Another for zext, trunc expressions, these probably need some discussion about their correctness.

Thanks.

[alexsusu]

Adding very simple unit tests on which normally Polly fails to detect the right SCoP due to the sext (and trunc, as well) in both dividend and divisor used in the third step of the delinearization algorithm (it seems the SCEV expressions sext(N * N), sext(N), etc are created by the 1st step of the delinearization algorithm extracting the terms from the sum of products from the array index i * N * N + j * N + k) presented in Section 4.1 of the paper Grosser et al, "On recovering Multi-dimensional Arrays in Polly", IMPACT 2015 - http://impact.gforge.inria.fr/impact2015/papers/impact2015-grosser.pdf ). Because of this Polly complains of non-affine expression for array indexing.
To make Polly work, we need to apply the patch I already committed (I will put another patch ASAP).
Please note my patch is not incremental w.r.t. patch from https://reviews.llvm.org/D35478 - you need to apply ONLY my patch.

As requested by Michael (Meinersbur) I add the .ll unit tests (and also the .c files used to generate the .ll files, just in case).

test_sext.ll5 KBDownload

test_sext.c1 KBDownload

[Meinersbur]

This is a commit to LLVM, not Polly. The unit test should be in LLVM as well. There are already tests in test\Analysis\Delinearization. You can model a new one after one that already exists.

[alexsusu]

Note that in this patch we only address the SExt, as suggested by Michael (Meinersbur).

[Meinersbur]

Could you re-upload the patch with the LLVM source directory as patch root (so it patches include/llvm/Analysis/ScalarEvolution.h instead of ./ScalarEvolution.h).

Could you format your changes using clang-format?

We also need a test-case.

[alexsusu]

Added correct path to the ScalarEvolution.cpp file (lib/Analysis/ScalarEvolution.cpp).
Again, my patch incorporates also the one from https://reviews.llvm.org/D35478 - in order to make it work well for SCEVDivision, when having SExt expressions. My own changes are basically only the ones handling SCEVSignExtendExpr.

[lebedev.ri]

Please always upload all patches with the full context.
Also, the tests need to be added as well, with the code changes, into the repo.

[alexsusu]

Adding as Roman said the patch for ScalarEvolution.cpp and also the associated test test/Analysis/Delinearization/test_sext.ll .

[lebedev.ri]

test/Analysis/Delinearization/test_sext.ll

41

I'm guessing this is the expected result that you want to check?
It needs to be actually checked..

Look at other files in that directory, e.g. test/Analysis/Delinearization/constant_functions_multi_dim.ll
You are missing ; RUN: opt -delinearize -analyze < %s | FileCheck %s as the first line, and the actual check line.
And check if llvm/utils/update_test_checks.py can help generate the actual check lines.

[alexsusu]

Adding, as Roman suggested, in the header of the test_sext.ll file a line describing the RUN command and a CHECK line.

[Meinersbur]

lib/Analysis/ScalarEvolution.cpp

945–955

This patch is for handling sext only, correct? In this case, are these two cases needed?

1083

This change looks unnecessary/unrelated to this patch.

1089

This change looks unnecessary/unrelated to this patch.

1111–1113

This change looks unnecessary/unrelated to this patch.

test/Analysis/Delinearization/test_sext.ll

5

Is this a line to be checked? Then the line must start with CHECK: instead of AddRec:

[alexsusu]

Addressed Michael Kruse's comment on the patch - changed the test .ll file.

[Meinersbur]

I could not apply the patch: test/Analysis/Delinearization/test_sext.ll is marked to modify an existing file which does not exist. Did you add the file using git add -N and created the diff against that?

[Meinersbur]

I applied this patch. However, your test-case fails.

lib/Analysis/ScalarEvolution.cpp

943

Please document what this function is supposed to do.

945–960

These seem to just ignore casts of the denominator. If SCEVDivision implements a signed division, then this should be ok for sext. If it implements unsigned division, it should be ok for zext. However, it is never semantically correct for both at the same time nor for trunc.

969

SCEV only has SCEVUDivExpr, i.e. cannot represent signed division. Therefore signed division seems the wrong interpretation here.

SCEVDivision::divide might actually do a signed division, unfortunately I cannot find any documentation supporting this.

test/Analysis/Delinearization/test_sext.ll

11

This check fails for me. I get the output:

Base offset: %a
ArrayDecl[UnknownSize][%N][%N] with elements of 16 bytes.

Maybe you want to check the ArrayRef line as well.

[alexsusu]

Made a better patch following comments from Michael Kruse.
Most importantly I added comments that I consider SCEVDivision::divide() to be signed division.

[dmgreen]

Hello. I just have some test Nits.

lib/Analysis/ScalarEvolution.cpp

10720

Don't need the brackets, like the if below

test/Analysis/Delinearization/test_sext.ll

2

This line doesn't seem to be true and can be removed I think

3

It's probably best to not run -O3 here, as it could change the output as llvm evolves. You can run -O3 on the input now and use that generated IR for this test, then just needing -delinearize -analyze.

62

source_filename and ModuleID can be removed

66

This Function Attrs comment and the #0 on the function can be removed

[alexsusu]

Did corrections, following Dave Green's comments.

[greened]

lib/Analysis/ScalarEvolution.cpp

992

We don't want this part of the comment in the final patch.

994

Instead of talking about why the code is here instead of somewhere else, it's probably better to talk about what the code is doing. What expectations are being verified?

[alexsusu]

Addressed small review issue of greened (David Greene) on comment in method: void visitAddRecExpr(const SCEVAddRecExpr *Numerator) .

[lebedev.ri]

Not really sure why this patch got stuck, do you not want it to progress?
The comments in code read *really* weird, and inline comments aren't being addressed.

[Meinersbur]

In D40369#2699027, @lebedev.ri wrote:

Not really sure why this patch got stuck, do you not want it to progress?
The comments in code read *really* weird, and inline comments aren't being addressed.

Yeas, I would like to see this implemented, but I don't have confidence that this review is going forward. It has always been the first item on my Phabricator dashboard a I wanted to clean it up.

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

lib/Analysis/ScalarEvolution.cpp

static void divide(ScalarEvolution &SE, const SCEV *Numerator,
     *Quotient = D.Quotient;
     *Remainder = D.Remainder;
   }
 
   // Except in the trivial case described above, we do not know how to divide
   // Expr by Denominator for the following functions with empty implementation.
   void visitTruncateExpr(const SCEVTruncateExpr *Numerator) {}
   void visitZeroExtendExpr(const SCEVZeroExtendExpr *Numerator) {}
-  void visitSignExtendExpr(const SCEVSignExtendExpr *Numerator) {}
   void visitUDivExpr(const SCEVUDivExpr *Numerator) {}
   void visitSMaxExpr(const SCEVSMaxExpr *Numerator) {}
   void visitUMaxExpr(const SCEVUMaxExpr *Numerator) {}
   void visitUnknown(const SCEVUnknown *Numerator) {}
   void visitCouldNotCompute(const SCEVCouldNotCompute *Numerator) {}
 
   void visitConstant(const SCEVConstant *Numerator) {
     if (const SCEVConstant *D = dyn_cast<SCEVConstant>(Denominator)) {
if (const SCEVConstant *D = dyn_cast<SCEVConstant>(Denominator)) {
       APInt RemainderVal(NumeratorVal.getBitWidth(), 0);
       APInt::sdivrem(NumeratorVal, DenominatorVal, QuotientVal, RemainderVal);
       Quotient = SE.getConstant(QuotientVal);
       Remainder = SE.getConstant(RemainderVal);
       return;
     }
   }
 
+  void treatCastDenominator(const SCEVCastExpr *CENumerator, const SCEV **Q,
+                        const SCEV **R) {
+    if (const SCEVTruncateExpr *TruncDenominator =
+                                      dyn_cast<SCEVTruncateExpr>(Denominator)) {
+      divide(SE, CENumerator->getOperand(), TruncDenominator->getOperand(), Q,
+             R);
+    }
+    else
+    if (const SCEVZeroExtendExpr *ZExtDenominator =
+                                  dyn_cast<SCEVZeroExtendExpr>(Denominator)) {
+      divide(SE, CENumerator->getOperand(), ZExtDenominator->getOperand(), Q, R);
+    }
+    else
+    if (const SCEVSignExtendExpr *SExtDenominator =
+                                      dyn_cast<SCEVSignExtendExpr>(Denominator)) {
+      // Dropping SExt in Dividend and Divisor
+      divide(SE, CENumerator->getOperand(), SExtDenominator->getOperand(), Q, R);
+    }
+    else
+      divide(SE, CENumerator->getOperand(), Denominator, Q, R);
+  }
+
+  void visitSignExtendExpr(const SCEVSignExtendExpr *Numerator) {
+    const SCEV *Q, *R;
+    treatCastDenominator(Numerator, &Q, &R);
+
+    // Note that the division operation here is signed.
+    //  And SExt does not change the value of the divisor nor of the dividend.
+    //  So we can take out the SExt from both the divisor and the dividend
+    // And, we sign extend the Quotient and Remainder because
+    //  the resulting type of the Quotient and Remainder should be the type of
+    //      the Dividend,
+    //  since we assume that the Divisor can be in the most extreme case
+    //   +1 or -1 and Dividend already is a signed integer type since it is
+    //   the result of a sext operation.
+    //  If we don't SExt, the Quotient and Remainder will have the type of
+    //  the Dividend (and Divisor).
+
+    Quotient = SE.getSignExtendExpr(Q, Numerator->getType());
+    Remainder = SE.getSignExtendExpr(R, Numerator->getType());
+  }
+
   void visitAddRecExpr(const SCEVAddRecExpr *Numerator) {
     const SCEV *StartQ, *StartR, *StepQ, *StepR;
     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())
-      return cannotDivide(Numerator);
+
+    // This is from Manuel Selva's patch (https://reviews.llvm.org/D35478).
+    //  We have to put this code here instead of the conditionals with
+    //    cannotDivide() in order to work with sext expressions.
+    assert(Numerator->getStart()->getType() == StartQ->getType() &&
+           StartQ->getType() == StartR->getType() &&
+           "Expected matching types");
+    assert(Numerator->getStepRecurrence(SE)->getType() == StepQ->getType() &&
+           StepQ->getType() == StepR->getType() &&
+           "Expected matching types");
+
     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();
+    Type *Ty = Numerator->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())
         return cannotDivide(Numerator);
 
+      assert(Ty == Q->getType() && Ty == R->getType() &&
+             "Expected matching types");
+
       Qs.push_back(Q);
       Rs.push_back(R);
     }
 
     if (Qs.size() == 1) {
       Quotient = Qs[0];
       Remainder = Rs[0];
       return;
void visitMulExpr(const SCEVMulExpr *Numerator) {
     }
 
     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();
+        cast<SCEVConstant>(SE.getZero(Denominator->getType()))->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();
+          cast<SCEVConstant>(SE.getOne(Denominator->getType()))->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);
     // This SCEV does not seem to simplify: fail the division here.
     if (sizeOfSCEV(Diff) > sizeOfSCEV(Numerator))
       return cannotDivide(Numerator);
     divide(SE, Diff, Denominator, &Q, &R);
     if (R != Zero)
       return cannotDivide(Numerator);
     Quotient = Q;
   }
 
 private:
   SCEVDivision(ScalarEvolution &S, const SCEV *Numerator,
                const SCEV *Denominator)
       : SE(S), Denominator(Denominator) {
-    Zero = SE.getZero(Denominator->getType());
-    One = SE.getOne(Denominator->getType());
+    Zero = SE.getZero(Numerator->getType());
+    One = SE.getOne(Numerator->getType());
 
     // 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.
static inline bool containsParameters(SmallVectorImpl<const SCEV *> &Terms) {
   for (const SCEV *T : Terms)
     if (SCEVExprContains(T, isa<SCEVUnknown, const SCEV *>))
       return true;
   return false;
 }
 
 // Return the number of product terms in S.
 static inline int numberOfTerms(const SCEV *S) {
+  if (const SCEVSignExtendExpr *SExtS = dyn_cast<SCEVSignExtendExpr>(S)) {
+    return numberOfTerms(SExtS->getOperand());
+  }
+
   if (const SCEVMulExpr *Expr = dyn_cast<SCEVMulExpr>(S))
     return Expr->getNumOperands();
   return 1;
 }
 
 static const SCEV *removeConstantFactors(ScalarEvolution &SE, const SCEV *T) {
   if (isa<SCEVConstant>(T))
     return nullptr;

test/Analysis/Delinearization/test_sext.ll

+; The below LLVM program is obtained by
+;    running: clang -O3 -mllvm -disable-llvm-optzns -emit-llvm -S test_trunc.c
+;
+; /* For a 64-bit CPU system sext is generated from i32 to i64 for the 64-bit target.
+;    I presume it will not generate sext on a 32-bit CPU target
+;       - if you want to make it generate sext use short instead of int.
+;    This implies also that if I use scalars of type long (i64) instead of int,
+;       delinearization will work also without the sext patch.
+;
+; The delinearization algorithm uses the sext patch because it performs:
+;     - division of sext_i32_to_i64(N * N) by sext_i32_to_i64(N), which generates
+;          quotient sext_i32_to_i64(N) and sext_i32_to_i64(0) remainder.
+;     - the dividend and the divisor are created by the third step of the delinearization
+;       algorithm (it seems the SCEV expressions sext(N * N), sext(N), etc
+;       are created by the 1st step of the delinearization algorithm extracting the
+;       terms from the sum of products from the array index i * N*N + j * N + k)
+;       presented in Section 4.1 of the paper
+;       Grosser et al, "On recovering Multi-dimensional Arrays in Polly", IMPACT 2015
+;       - http://impact.gforge.inria.fr/impact2015/papers/impact2015-grosser.pdf )
+; */
+;
+;
+; void Test(int *a, int N) {
+;     int i, j, k;
+;
+;     /* We note here we initialize a linearized version of the a array.
+;        Note: there is no need for the ScalarEvolution patch if just using a
+;         loop nest with only i and j vars and the a vector is accessed as a
+;         2D array.
+;     */
+;     for (i = 0; i < N; i++) {
+;         for (j = 0; j < N; j++) {
+;             for (k = 0; k < N; k++) {
+;                 a[i * N*N + j * N + k] = i + j;
+;             }
+;         }
+;     }
+; }
+
+
+; SCEV/AddRec: {(4 * (sext i32 {{0,+,(%N * %N)}<%for.body3.lr.ph.split.us.us>,+,%N}<%for.body3.us.us> to i64)),+,4}<nsw><%for.body6.us.us>
+
+; ModuleID = 'test_sext.c'
+source_filename = "test_sext.c"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define void @Test(i32* %a, i32 %N) #0 !dbg !7 {
+entry:
+  %a.addr = alloca i32*, align 8
+  %N.addr = alloca i32, align 4
+  %i = alloca i32, align 4
+  %j = alloca i32, align 4
+  %k = alloca i32, align 4
+  store i32* %a, i32** %a.addr, align 8
+  store i32 %N, i32* %N.addr, align 4
+  %0 = bitcast i32* %i to i8*
+  %1 = bitcast i32* %j to i8*
+  %2 = bitcast i32* %k to i8*
+  store i32 0, i32* %i, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc14, %entry
+  %3 = load i32, i32* %i, align 4
+  %4 = load i32, i32* %N.addr, align 4
+  %cmp = icmp slt i32 %3, %4
+  br i1 %cmp, label %for.body, label %for.end16
+
+for.body:                                         ; preds = %for.cond
+  store i32 0, i32* %j, align 4
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc11, %for.body
+  %5 = load i32, i32* %j, align 4
+  %6 = load i32, i32* %N.addr, align 4
+  %cmp2 = icmp slt i32 %5, %6
+  br i1 %cmp2, label %for.body3, label %for.end13
+
+for.body3:                                        ; preds = %for.cond1
+  store i32 0, i32* %k, align 4
+  br label %for.cond4
+
+for.cond4:                                        ; preds = %for.inc, %for.body3
+  %7 = load i32, i32* %k, align 4
+  %8 = load i32, i32* %N.addr, align 4
+  %cmp5 = icmp slt i32 %7, %8
+  br i1 %cmp5, label %for.body6, label %for.end
+
+for.body6:                                        ; preds = %for.cond4
+  %9 = load i32, i32* %i, align 4
+  %10 = load i32, i32* %j, align 4
+  %add = add nsw i32 %9, %10
+  %11 = load i32*, i32** %a.addr, align 8
+  %12 = load i32, i32* %i, align 4
+  %13 = load i32, i32* %N.addr, align 4
+  %mul = mul nsw i32 %12, %13
+  %14 = load i32, i32* %N.addr, align 4
+  %mul7 = mul nsw i32 %mul, %14
+  %15 = load i32, i32* %j, align 4
+  %16 = load i32, i32* %N.addr, align 4
+  %mul8 = mul nsw i32 %15, %16
+  %add9 = add nsw i32 %mul7, %mul8
+  %17 = load i32, i32* %k, align 4
+  %add10 = add nsw i32 %add9, %17
+  %idxprom = sext i32 %add10 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %11, i64 %idxprom
+  store i32 %add, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body6
+  %18 = load i32, i32* %k, align 4
+  %inc = add nsw i32 %18, 1
+  store i32 %inc, i32* %k, align 4
+  br label %for.cond4
+
+for.end:                                          ; preds = %for.cond4
+  br label %for.inc11
+
+for.inc11:                                        ; preds = %for.end
+  %19 = load i32, i32* %j, align 4
+  %inc12 = add nsw i32 %19, 1
+  store i32 %inc12, i32* %j, align 4
+  br label %for.cond1
+
+for.end13:                                        ; preds = %for.cond1
+  br label %for.inc14
+
+for.inc14:                                        ; preds = %for.end13
+  %20 = load i32, i32* %i, align 4
+  %inc15 = add nsw i32 %20, 1
+  store i32 %inc15, i32* %i, align 4
+  br label %for.cond
+
+for.end16:                                        ; preds = %for.cond
+  %21 = bitcast i32* %k to i8*
+  %22 = bitcast i32* %j to i8*
+  %23 = bitcast i32* %i to i8*
+  ret void
+}