Page MenuHomePhabricator

[ARM] Loop Strength Reduction crashes when targeting ARM or Thumb.
ClosedPublic

Authored by labrinea on Nov 1 2016, 6:48 AM.

Details

Summary

Scalar Evolution asserts when not all the operands of an Add Recurrence Expression are loop invariants. Loop Strength Reduction should only create affine Add Recurrences, so that both the start and the step of the expression are loop invariants.

A corresponding bug has been raised here: https://llvm.org/bugs/show_bug.cgi?id=30325

Diff Detail

Event Timeline

labrinea updated this revision to Diff 76547.Nov 1 2016, 6:48 AM
labrinea retitled this revision from to [ARM] Loop Strength Reduction crashes when targeting ARM or Thumb if the LLVM-IR is not in LCSSA form..
labrinea updated this object.
efriedma requested changes to this revision.Nov 1 2016, 10:06 AM
efriedma added a reviewer: efriedma.
efriedma added a subscriber: efriedma.
efriedma added inline comments.
lib/Transforms/Scalar/LoopStrengthReduce.cpp
329

"SE.isLoopInvariant(AR->getStepRecurrence(SE), AR->getLoop())" is always true; if you try to build an AddRec with non-invariant operands, you'll hit the assertion you pointed out.

582

It would be more clear to check "SE.isLoopInvariant(RHS, AR->getLoop())".

3208

Again, useless check.

This revision now requires changes to proceed.Nov 1 2016, 10:06 AM

The test I have added is a reproducer that triggers the assertion in the absence of these checks. What would be a proper fix if these checks are useless?

Err, hang on, I must be missing something... ignore me for the moment; taking another look.

efriedma added inline comments.Nov 1 2016, 10:27 AM
lib/Transforms/Scalar/LoopStrengthReduce.cpp
329

Ah, right, my previous comment was wrong. "AR->isAffine()" would be a more clear way to write this check. (A non-affine AddRec always has a step which is not invariant, and an affine AddRec always has a step which is invariant.)

582

(Ignore my previous comment here.)

3208

(Ignore my previous comment here.)

labrinea updated this revision to Diff 76600.Nov 1 2016, 11:04 AM
labrinea edited edge metadata.

An Affine AddRec always has a Step which is invariant. This is the right thing to check instead of the Step itself.

labrinea updated this revision to Diff 76603.Nov 1 2016, 11:07 AM
labrinea edited edge metadata.

Accidentally uploaded a diff with too few context. Uploaded again.

efriedma added inline comments.Nov 1 2016, 11:19 AM
lib/Transforms/Scalar/LoopStrengthReduce.cpp
581

Please move this check into the earlier if statement.

3206

Please move this check earlier (maybe the same place as the "AR->getStart()->isZero()" check).

test/Transforms/LoopStrengthReduce/ARM/addrec-is-loop-invariant.ll
4

This issue has nothing to do with LCSSA, as far as I can tell.

labrinea added inline comments.Nov 2 2016, 1:59 AM
lib/Transforms/Scalar/LoopStrengthReduce.cpp
571

Like this:

-    if (IgnoreSignificantBits || isAddRecSExtable(AR, SE)) {
+    if ((IgnoreSignificantBits || isAddRecSExtable(AR, SE)) && AR->isAffine()) {

?

3195

Something like:

-    if (AR->getStart()->isZero())
+    if (AR->getStart()->isZero() || !AR->isAffine())

?

test/Transforms/LoopStrengthReduce/ARM/addrec-is-loop-invariant.ll
18

Here, %c.0 is used outside of loop0, where it is defined. Adding a PHI node for it prevents the issue. That's why I am mentioning the LCSSA form.

efriedma added inline comments.Nov 2 2016, 10:13 AM
lib/Transforms/Scalar/LoopStrengthReduce.cpp
571

Yes.

3195

Yes.

test/Transforms/LoopStrengthReduce/ARM/addrec-is-loop-invariant.ll
18

Oh, LCSSA hides the issue because SCEV doesn't look through LCSSA PHI nodes. That doesn't really mean the lack of LCSSA is causing the problem, though... you could probably trigger this with IR in LCSSA form by messing with the loop nest (for example, make loop1 a subloop of loop0).

labrinea updated this revision to Diff 76829.Nov 3 2016, 3:35 AM
labrinea retitled this revision from [ARM] Loop Strength Reduction crashes when targeting ARM or Thumb if the LLVM-IR is not in LCSSA form. to [ARM] Loop Strength Reduction crashes when targeting ARM or Thumb..
labrinea updated this object.
efriedma accepted this revision.Nov 8 2016, 11:11 AM
efriedma edited edge metadata.

LGTM. (I'm not exactly an LSR expert, but this change is simple enough that I feel comfortable approving it anyway.)

This revision is now accepted and ready to land.Nov 8 2016, 11:11 AM
This revision was automatically updated to reflect the committed changes.