ScalarEvolutionExpander step scaling bug

[loladiro]

Summary

the expandAddRecExprLiterally function incorrectly transforms: [Start + Step * X] into Step * [Start + X] instead of the correct transform of [Step * X] + Start

this caused https://github.com/JuliaLang/julia/issues/14704#issuecomment-174126219 due to what appeared to be sufficiently complicated loop interactions (.ll code that reproduces the issue in llc available upon request)

[loladiro]

Do you have an IR test case?

[vtjnash]

i don't know how to reduce the test case, but in the attached IR, the "loop-reduce" pass does an invalid transform for the computation of %57 from %25 from %"#s13.0"

14704.ll7 KBDownload

[loladiro]

@sanjoy is probably the person who should review this.

[sanjoy]

Can you please upload a diff with full context: http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface ?

[vtjnash]

full context diff

[sanjoy]

Overall LGTM, but this should have a test case. It is best to have an
IR test case, but I understand that it is difficult to get LSR to do
exactly what you want in a robust way. Do you mind looking into
writing a C++ test case (i.e. create a SCEV expression using C++, and
assert that it expands to what it should expand to)? You could add it
to unittests/Analysis/ScalarEvolutionTest.cpp.

lib/Analysis/ScalarEvolutionExpander.cpp

1280

Very minor, but be more explicit about otherwise above (since I got confused on the first reading), and say something like "And if PostLoopOffset is not nullptr then ..."

[loladiro]

I had bugpoint reduce the testcase to only those instructions needed to trigger this case. Is there a good way to extract the SCEV expression to put into the unittest?

; ModuleID = 'bugpoint-reduced-simplified.bc'
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-darwin15.0.0"

define void @julia_partition_lp_24079() #0 {
top:
  br i1 undef, label %L4, label %L.preheader

L.preheader:                                      ; preds = %top
  br label %L

L:                                                ; preds = %L3, %L.preheader
  br i1 undef, label %idxend, label %oob

L1:                                               ; preds = %L1.preheader, %L2
  %"#s13.0" = phi i64 [ %1, %L2 ], [ 1, %L1.preheader ]
  %0 = add i64 %"#s13.0", -1
  br i1 undef, label %idxend.8, label %oob.7

L2:                                               ; preds = %idxend.8
  %1 = add i64 %"#s13.0", 1
  br i1 undef, label %L3, label %L1

L3:                                               ; preds = %idxend.10, %idxend, %L2
  br i1 undef, label %L4, label %L

L4:                                               ; preds = %L3, %top
  ret void

oob:                                              ; preds = %L
  unreachable

idxend:                                           ; preds = %L
  br i1 undef, label %L3, label %L1.preheader

L1.preheader:                                     ; preds = %idxend
  br label %L1

if6:                                              ; preds = %idxend.8
  %2 = load i64, i64* undef, align 8
  br i1 undef, label %ib, label %oob.9

oob.7:                                            ; preds = %L1
  unreachable

idxend.8:                                         ; preds = %L1
  br i1 undef, label %if6, label %L2

ib:                                               ; preds = %if6
  %3 = mul i64 %2, %0
  %4 = add i64 undef, %3
  %5 = icmp ult i64 %4, undef
  br i1 %5, label %idxend.10, label %oob.9

oob.9:                                            ; preds = %ib, %if6
  unreachable

idxend.10:                                        ; preds = %ib
  br label %L3
}

attributes #0 = { "no-frame-pointer-elim"="true" }

!llvm.module.flags = !{!0}

!0 = !{i32 1, !"Debug Info Version", i32 3}

[sanjoy]

In D16505#346027, @loladiro wrote:

I had bugpoint reduce the testcase to only those instructions needed to trigger this case. Is there a good way to extract the SCEV expression to put into the unittest?

Given that this test case triggers the bad expansion using LSR, I'd
say just having this run through opt -loop-reduce and
FileCheck-ing for the right IR expression is enough (and perhaps
CHECK-NOT:-ing the wrong IR expression). I initially suggested
writing a unittest in case it was difficult to extract a small
self-contained IR reproducer, but that does not seem to be the case.

[sanjoy]

Getting this out of my queue for now. The only thing that's needed is a test case, and the bugpoint reduced test-case run through opt -loop-reduce and FileCheck ed for correct IR should be more than enough.

[vtjnash]

I couldn't get Keno's testcase to work for me (it shows the patch, but not the bug), so I re-extracted it with bugpoint and simplified it a bit more by hand.

[vtjnash]

bump

[sanjoy]

lib/Analysis/ScalarEvolutionExpander.cpp

1274

I know I LGTM'ed this before, but would making this condition !Start->isZero() be better? Then in the body you could do

assert(!PostLoopOffset && "<reason>");
PostLoopOffset = Start;
Start = getConstant(0);

1275

Grammar nit: please use full sentences, start with upper case, end with periods etc. Also wrap the comments to 80 chars please.

Same with the commit message.

[vtjnash]

lib/Analysis/ScalarEvolutionExpander.cpp

1274

That sounds feasible, and probably better than letting constant folding eliminate it later, although either way this fixes the bug.

[loladiro]

Bump! @vtjnash does @sanjoy's proposed patch work look ok to you? Can you update the patch? I'd like to make sure this doesn't get passed over for 3.9.

[loladiro]

Actually, let me just put the patch up myself.

[loladiro]

Updates as suggested by @sanjoy.

[sanjoy]

lgtm, but please clean up the commit message punctuation before checkin.

lib/Analysis/ScalarEvolutionExpander.cpp

   if (!SE.dominates(Step, L->getHeader())) {
     PostLoopScale = Step;
     Step = SE.getConstant(Normalized->getType(), 1);
+    if (!Start->isZero()) {
+        // The normalization below assumes that Start is constant zero, so if
+        // it isn't re-associate Start to PostLoopOffset.
+        assert(!PostLoopOffset && "Start not-null but PostLoopOffset set?");
+        PostLoopOffset = Start;
+        Start = SE.getConstant(Normalized->getType(), 0);
+    }
     Normalized =
       cast<SCEVAddRecExpr>(SE.getAddRecExpr(
                              Start, Step, Normalized->getLoop(),

test/Analysis/ScalarEvolution/incorrect-offset-scaling.ll

+; RUN: opt -S -loop-reduce < %s | FileCheck %s
+
+target triple = "x86_64-unknown-unknown"
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @incorrect_offset_scaling(i64, i64*) {
+top:
+  br label %L
+
+L:                                                ; preds = %idxend.10, %idxend, %L2, %top
+  br i1 undef, label %L, label %L1
+
+L1:                                               ; preds = %L1.preheader, %L2
+  %r13 = phi i64 [ %r1, %L2 ], [ 1, %L ]
+; CHECK:  %lsr.iv = phi i64 [ 0, %L{{[^ ]+}} ], [ %lsr.iv.next, %L2 ]
+; CHECK-NOT:  %lsr.iv = phi i64 [ -1, %L{{[^ ]+}} ], [ %lsr.iv.next, %L2 ]
+; CHECK:  br
+  %r0 = add i64 %r13, -1
+  br label %idxend.8
+
+L2:                                               ; preds = %idxend.8
+  %r1 = add i64 %r13, 1
+  br i1 undef, label %L, label %L1
+
+if6:                                              ; preds = %idxend.8
+  %r2 = add i64 %0, -1
+  %r3 = load i64, i64* %1, align 8
+; CHECK-NOT:  %r2
+; CHECK:  %r3 = load i64
+  br label %ib
+
+idxend.8:                                         ; preds = %L1
+  br i1 undef, label %if6, label %L2
+
+ib:                                               ; preds = %if6
+  %r4 = mul i64 %r3, %r0
+  %r5 = add i64 %r2, %r4
+  %r6 = icmp ult i64 %r5, undef
+; CHECK  %2 = mul i64 %lsr.iv, %r3
+; CHECK  %3 = add i64 %1, -1
+; CHECK  %4 = add i64 %0, %r3
+; CHECK  %r6
+  %r7 = getelementptr i64, i64* undef, i64 %r5
+  store i64 1, i64* %r7, align 8
+; CHECK  %5 = mul i64 %lsr.iv, %r3
+; CHECK  %6 = add i64 %5, -1
+  br label %L
+}