Support sext and trunc instructions in SCEV delinearization algorithm

[ManuelSelva]

Summary

This patch is a very first attempt to support sext and trunc instructions in SCEV delinearization algorithm.
The patch includes:

• modifications of the algorithm trying to divide an SCEV by another SCEV in order to support sext and trunc instructions.
• a test case for this new feature

[grosser]

Add Sebastian as reviewer.

[grosser]

Hi Manuel,

most changes are simple. I added a couple of style comments. I probably only get to this on the weekend, but the main thing we need to check is under which conditions ignoring sext/zext is legal. I am afraid, this is only OK with non-trivial checks -- or if ew can get nsw information from the IR.

Out of interest. Why does your IR has the mix of 32 and 64 values in the first place? And why do you have overflow-checked intrinsics?

lib/Analysis/ScalarEvolution.cpp

873

Indentation.

878

Indentation.

925

Alignment?

940

Can this assert ever be reached? It seems you bail out right before the position at which the assert is inserted.

[ManuelSelva]

Hi Tobias,

Thank you for looking at that. To first answer your questions "out of interest", this IR is generated by JavaScriptCore, a JavaScript virtual machine performing JIT compilation. The virtual machine is using NaN-boxing, i.e., uses the unused values (all representing NaN) of 64 bits floating point representation to represent JavaScript objects. In this representation, 32 bits integers are represented by 64 bits values all starting with the FFFF 0000 32 bits pattern. As a consequence, to get the integer value from a 64 bits value, the virtual machine generates LLVM code that truncates the value to a 32 bits integer.

Then, when performing arithmetic operations on these 32 bits integers, we need to ensure that they do not overflow, because if it's the case, we can't represent them anymore with the NaN-boxing trick and so we need to do *something* to represent them properly. This "something" is not present in the test case I provided in order to make it as minimal as possible.

If you are curious on this NaN-boxing thing and more generally on JavaScript implementations, you can have a look at the following links:

• https://manuelselva.github.io/docs/presentations/2017-06-21-Manuel-Selva-js-polyhedral-journees-compil.pdf (see in the backup slides, slides I made for a recent presentation)
• https://wingolog.org/archives/2011/05/18/value-representation-in-javascript-implementations)

I'll now look into the details of this patch, to ensure its correctness as you said.

Best,
Manu

[alexsusu]

In D35478#814250, @ManuelSelva wrote:

Hi Tobias,

Thank you for looking at that. To first answer your questions "out of interest", this IR is generated by JavaScriptCore, a JavaScript virtual machine performing JIT compilation. The virtual machine is using NaN-boxing, i.e., uses the unused values (all representing NaN) of 64 bits floating point representation to represent JavaScript objects. In this representation, 32 bits integers are represented by 64 bits values all starting with the FFFF 0000 32 bits pattern. As a consequence, to get the integer value from a 64 bits value, the virtual machine generates LLVM code that truncates the value to a 32 bits integer.

Then, when performing arithmetic operations on these 32 bits integers, we need to ensure that they do not overflow, because if it's the case, we can't represent them anymore with the NaN-boxing trick and so we need to do *something* to represent them properly. This "something" is not present in the test case I provided in order to make it as minimal as possible.

If you are curious on this NaN-boxing thing and more generally on JavaScript implementations, you can have a look at the following links:

• https://manuelselva.github.io/docs/presentations/2017-06-21-Manuel-Selva-js-polyhedral-journees-compil.pdf (see in the backup slides, slides I made for a recent presentation)
• https://wingolog.org/archives/2011/05/18/value-representation-in-javascript-implementations)

I'll now look into the details of this patch, to ensure its correctness as you said.

Best,
Manu

Hello.
  I applied the patch that was provided in this review to my LLVM build.
  I would like to draw attention to a bug of the deliniarization procedure that is related to type casts (from i32 to i64), and is probably related to the problems that were supposed to be addressed by the patch in this review.
  I attach a C file that reproduces this bug - the delinearization procedure fails due to sext from i32 to i64, and Polly finds Non affine access functions, which he shouldn't. Note that in the same C file I also provide on line 3 a commented signature of the Test function which can be uncommented, for which delinearization works OK and all access functions are affine.
  I will try to look deeper in the problem with delinearization. Please let me know if you can help with this problem.

Best regards,
  Alex

MultiDim.c1 KBDownload

[alexsusu]

Hello.

I applied the patch that was provided in this review to my LLVM build.
I would like to draw attention to a bug of the deliniarization procedure that is related to type casts (from i32 to i64), and is probably related to the problems that were supposed to be addressed by the patch in this review.
I attach a C file that reproduces this bug - the delinearization procedure fails due to sext from i32 to i64, and Polly finds Non affine access functions, which he shouldn't. Note that in the same C file I also provide on line 3 a commented signature of the Test function which can be uncommented, for which delinearization works OK and all access functions are affine.
I will try to look deeper in the problem with delinearization. Please let me know if you can help with this problem.

Best regards,

Alex

MultiDim.c1 KBDownload

lib/Analysis/ScalarEvolution.cpp

 
   // 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 visitTruncateExpr(const SCEVTruncateExpr *Numerator) {
+  const SCEV *Q, *R;
+  divide(SE, Numerator->getOperand(), Denominator, &Q, &R);
+  Quotient = SE.getTruncateExpr(Q, Numerator->getType());
+  Remainder = SE.getTruncateExpr(R, Numerator->getType());
+  }
+
+  void visitSignExtendExpr(const SCEVSignExtendExpr *Numerator) {
+  const SCEV *Q, *R;
+    divide(SE, Numerator->getOperand(), Denominator, &Q, &R);
+    Quotient = SE.getSignExtendExpr(Q, Numerator->getType());
+    Remainder = SE.getSignExtendExpr(R, Numerator->getType());
+  }
+
+
   void visitConstant(const SCEVConstant *Numerator) {
     if (const SCEVConstant *D = dyn_cast<SCEVConstant>(Denominator)) {
       APInt NumeratorVal = Numerator->getAPInt();

       APInt::sdivrem(NumeratorVal, DenominatorVal, QuotientVal, RemainderVal);
       Quotient = SE.getConstant(QuotientVal);
       Remainder = SE.getConstant(RemainderVal);
+      Quotient = SE.getTruncateOrNoop(Quotient, Numerator->getType());
+      Remainder = SE.getTruncateOrNoop(Remainder, Numerator->getType());
       return;
     }
   }

       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);
-    Quotient = SE.getAddRecExpr(StartQ, StepQ, Numerator->getLoop(),
-                                Numerator->getNoWrapFlags());
-    Remainder = SE.getAddRecExpr(StartR, StepR, Numerator->getLoop(),
-                                 Numerator->getNoWrapFlags());
+    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;

       // 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);

     // 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;

   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

test/Analysis/Delinearization/constant_sext_trunc.ll

+; RUN: opt -delinearize -analyze < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; CHECK:      Inst:  store i64 -281474976710602, i64* %19
+; CHECK-NEXT: In Loop with Header: Block #6
+; CHECK-NEXT: AccessFunction: (8 * (sext i32 {{[{][{]}}0,+,(trunc i64 %4 to i32)}<%"Block #3">,+,1}<%"Block #6"> to i64))
+; CHECK-NEXT: Base offset: %18
+; CHECK-NEXT: ArrayDecl[UnknownSize][%4] with elements of 8 bytes.
+; CHECK-NEXT: ArrayRef[(sext i32 {0,+,1}<%"Block #3"> to i64)][{0,+,1}<nuw><nsw><%"Block #6">]
+
+; CHECK:      Inst:  store i64 -281474976710602, i64* %19
+; CHECK-NEXT: In Loop with Header: Block #3
+; CHECK-NEXT: AccessFunction: (8 * (sext i32 {(-1 + (trunc i64 %4 to i32)),+,(trunc i64 %4 to i32)}<%"Block #3"> to i64))
+; CHECK-NEXT: Base offset: %18
+; CHECK-NEXT: ArrayDecl[UnknownSize][%4] with elements of 8 bytes.
+; CHECK-NEXT: ArrayRef[(sext i32 {1,+,1}<%"Block #3"> to i64)][-1]
+
+define i64 @jsBody_test() #0 {
+Prologue:
+  %0 = call i8* @llvm.frameaddress(i32 0)
+  %1 = ptrtoint i8* %0 to i64
+  %2 = add i64 %1, 56
+  %3 = inttoptr i64 %2 to i64*
+  %4 = load i64, i64* %3
+  %5 = add i64 %1, 48
+  %6 = inttoptr i64 %5 to i64*
+  %7 = load i64, i64* %6
+  %8 = trunc i64 %4 to i32
+  %9 = icmp slt i32 0, %8
+  %10 = add i64 %7, 8
+  %11 = inttoptr i64 %10 to i64*
+  %12 = load i64, i64* %11
+  %13 = add i64 %12, 0
+  br label %"Block #3"
+
+"Block #1":                                       ; preds = %"Block #9"
+  br label %"Block #3"
+
+"Block #3":                                       ; preds = %"Block #1", %Prologue
+  %.01 = phi i32 [ 0, %Prologue ], [ %22, %"Block #1" ]
+  br i1 %9, label %"Block #4", label %"Block #9"
+
+"Block #4":                                       ; preds = %"Block #3"
+  %14 = call { i32, i1 } @llvm.smul.with.overflow.i32(i32 %8, i32 %.01)
+  %15 = extractvalue { i32, i1 } %14, 0
+  br label %"Block #6"
+
+"Block #5":                                       ; preds = %"Block #6"
+  br label %"Block #6"
+
+"Block #6":                                       ; preds = %"Block #5", %"Block #4"
+  %.0 = phi i32 [ 0, %"Block #4" ], [ %20, %"Block #5" ]
+  %16 = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %15, i32 %.0)
+  %17 = extractvalue { i32, i1 } %16, 0
+  %18 = inttoptr i64 %13 to [10000000 x i64]*
+  %19 = getelementptr [10000000 x i64], [10000000 x i64]* %18, i32 0, i32 %17
+  store i64 -281474976710602, i64* %19
+  %20 = add i32 %.0, 1
+  %21 = icmp slt i32 %20, %8
+  br i1 %21, label %"Block #5", label %"Block #9"
+
+"Block #9":                                       ; preds = %"Block #6", %"Block #3"
+  %22 = add i32 %.01, 1
+  %23 = icmp slt i32 %22, 1000
+  br i1 %23, label %"Block #1", label %"Block #10"
+
+"Block #10":                                      ; preds = %"Block #9"
+  ret i64 10
+}
+
+; Function Attrs: nounwind readnone
+declare i8* @llvm.frameaddress(i32) #1
+
+; Function Attrs: nounwind readnone speculatable
+declare { i32, i1 } @llvm.smul.with.overflow.i32(i32, i32) #2
+
+; Function Attrs: nounwind readnone speculatable
+declare { i32, i1 } @llvm.sadd.with.overflow.i32(i32, i32) #2
+
+attributes #0 = { "target-features"="-avx" }
+attributes #1 = { nounwind readnone }
+attributes #2 = { nounwind readnone speculatable }