[SCEV] Consider delinearization pattern with extension with identity factor

[chrisj]

Summary

The delinearization algorithm did not consider terms which had an extension without a multiply factor, i.e. a identify factor. We lose cases where size is char type where there will no multiply factor.

[mssimpso]

test/Analysis/Delinearization/terms_with_identify_factor.ll

1

Hi Chris,

I think you need "REQUIRES: asserts" if you're checking the output of -debug.

[grosser]

Hi Chris,

this patch is clearly correct (in terms of it does not mis-compiling anything) and also beneficial. To be a little bit more sure we do not accidentally regress on test cases that have an sext further outside, I would probably match for the expression sext(SCEVUnknown), specifically. This seems to be the precise pattern we are looking for.

I also tested your patch on 3D arrays/loops and due to SCEV hoisting these checks out the simple matching your propose does not work. It might be interesting to look into handling sext expressions for 3D arrays as well.

Best,
Tobias

[Eugene.Zelenko]

Looks like patch was not committed.

[chrisj]

Apologies, forget this one. I will update the test with mathew's comment.

[chrisj]

Updated the test command and added "REQUIRES: asserts"

[grosser]

Hi Chris,

I am fine with this patch, but as written in my previous review I would prefer for it to match for the precise pattern sext<SCEVUnknown>, rather than just sext<*> to make it very clear for which pattern we match. If this change is OK for you and still catches the cases you are interested in, just post an updated patch and I will commit it.

[grosser]

This LGTM. Can you commit this by yourself?

[grosser]

OK. I committed this change for you!

lib/Analysis/ScalarEvolution.cpp

 // Collect all SCEVUnknown and SCEVMulExpr expressions.
 struct SCEVCollectTerms {
   SmallVectorImpl<const SCEV *> &Terms;
 
   SCEVCollectTerms(SmallVectorImpl<const SCEV *> &T)
       : Terms(T) {}
 
   bool follow(const SCEV *S) {
-    if (isa<SCEVUnknown>(S) || isa<SCEVMulExpr>(S)) {
+    if (isa<SCEVUnknown>(S) || isa<SCEVMulExpr>(S) ||
+      isa<SCEVSignExtendExpr>(S)) {
       if (!containsUndefs(S))
         Terms.push_back(S);
 
       // Stop recursion: once we collected a term, do not walk its operands.
       return false;
     }
 
     // Keep looking.

test/Analysis/Delinearization/terms_with_identify_factor.ll

+; RUN: opt < %s -analyze -delinearize -debug 2>&1 | FileCheck %s
+; void foo (int m, int n, char *A) {
+;    for (int i=0; i < m; i++)
+;      for(int j=0; j< n; j++)
+;        A[i*n+j] += 1;
+;}
+
+; ModuleID = 'delin.cpp'
+;target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+;target triple = "aarch64--linux-gnu"
+
+; CHECK-LABEL: Delinearization on function foo
+; CHECK: Inst:  %4 = load i8, i8* %arrayidx.us, align 1
+; AddRec: {{0,+,(sext i32 %n to i64)}<%for.body3.lr.ph.us>,+,1}<nw><%for.body3.us>
+; CHECK: Subscripts
+; CHECK-NEXT: {0,+,1}<nuw><nsw><%for.body3.lr.ph.us>
+; CHECK-NEXT: {0,+,1}<nuw><nsw><%for.body3.us>
+; CHECK: succeeded to delinearize
+
+define void @foo(i32 %m, i32 %n, i8* nocapture %A) #0 {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  %cmp15 = icmp sgt i32 %m, 0
+  %cmp213 = icmp sgt i32 %n, 0
+  %or.cond = and i1 %cmp15, %cmp213
+  br i1 %or.cond, label %for.cond1.preheader.lr.ph.split.us, label %for.end8
+
+for.cond1.preheader.lr.ph.split.us:               ; preds = %entry.split
+  %0 = add i32 %n, -1
+  %1 = sext i32 %n to i64
+  %2 = add i32 %m, -1
+  br label %for.body3.lr.ph.us
+
+for.body3.us:                                     ; preds = %for.body3.us, %for.body3.lr.ph.us
+  %indvars.iv = phi i64 [ 0, %for.body3.lr.ph.us ], [ %indvars.iv.next, %for.body3.us ]
+  %3 = add nsw i64 %indvars.iv, %5
+  %arrayidx.us = getelementptr inbounds i8, i8* %A, i64 %3
+  %4 = load i8, i8* %arrayidx.us, align 1
+  %add4.us = add i8 %4, 1
+  store i8 %add4.us, i8* %arrayidx.us, align 1
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %0
+  br i1 %exitcond, label %for.cond1.for.inc6_crit_edge.us, label %for.body3.us
+
+for.body3.lr.ph.us:                               ; preds = %for.cond1.for.inc6_crit_edge.us, %for.cond1.preheader.lr.ph.split.us
+  %indvars.iv19 = phi i64 [ %indvars.iv.next20, %for.cond1.for.inc6_crit_edge.us ], [ 0, %for.cond1.preheader.lr.ph.split.us ]
+  %5 = mul nsw i64 %indvars.iv19, %1
+  br label %for.body3.us
+
+for.cond1.for.inc6_crit_edge.us:                  ; preds = %for.body3.us
+  %indvars.iv.next20 = add nuw nsw i64 %indvars.iv19, 1
+  %lftr.wideiv22 = trunc i64 %indvars.iv19 to i32
+  %exitcond23 = icmp eq i32 %lftr.wideiv22, %2
+  br i1 %exitcond23, label %for.end8.loopexit, label %for.body3.lr.ph.us
+
+for.end8.loopexit:                                ; preds = %for.cond1.for.inc6_crit_edge.us
+  br label %for.end8
+
+for.end8:                                         ; preds = %for.end8.loopexit, %entry.split
+  ret void
+}
+