Page MenuHomePhabricator

ScalarEvolutionExpander step scaling bug
ClosedPublic

Authored by loladiro on Jan 23 2016, 1:13 AM.

Details

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)

Diff Detail

Repository
rL LLVM

Event Timeline

vtjnash updated this revision to Diff 45788.Jan 23 2016, 1:13 AM
vtjnash retitled this revision from to ScalarEvolutionExpander step scaling bug.
vtjnash updated this object.
vtjnash set the repository for this revision to rL LLVM.
vtjnash added a subscriber: loladiro.

Do you have an IR test case?

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"

@sanjoy is probably the person who should review this.

vtjnash updated this revision to Diff 46831.Feb 3 2016, 1:40 PM
vtjnash edited edge metadata.
vtjnash removed rL LLVM as the repository for this revision.

full context diff

loladiro set the repository for this revision to rL LLVM.Feb 3 2016, 1:41 PM
sanjoy added a comment.Feb 3 2016, 9:11 PM

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 ↗(On Diff #46831)

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 ..."

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 added a comment.Feb 7 2016, 2:13 PM

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 requested changes to this revision.Feb 15 2016, 4:29 PM
sanjoy edited edge metadata.

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.

This revision now requires changes to proceed.Feb 15 2016, 4:29 PM
vtjnash updated this revision to Diff 59258.Jun 1 2016, 11:37 AM
vtjnash edited edge metadata.

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.

sanjoy requested changes to this revision.Jun 9 2016, 12:38 PM
sanjoy edited edge metadata.
sanjoy added inline comments.
lib/Analysis/ScalarEvolutionExpander.cpp
1274 ↗(On Diff #59258)

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 ↗(On Diff #59258)

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.

This revision now requires changes to proceed.Jun 9 2016, 12:38 PM
vtjnash added inline comments.Jun 28 2016, 9:40 AM
lib/Analysis/ScalarEvolutionExpander.cpp
1274 ↗(On Diff #59258)

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

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 commandeered this revision.Jul 12 2016, 2:29 PM
loladiro added a reviewer: vtjnash.

Actually, let me just put the patch up myself.

loladiro updated this revision to Diff 63729.Jul 12 2016, 2:29 PM
loladiro edited edge metadata.

Updates as suggested by @sanjoy.

sanjoy accepted this revision.Jul 12 2016, 2:59 PM
sanjoy edited edge metadata.

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

This revision is now accepted and ready to land.Jul 12 2016, 2:59 PM
This revision was automatically updated to reflect the committed changes.