Page MenuHomePhabricator

[LoopUnroll] Don't try to unroll non-rotated loops
ClosedPublic

Authored by davide on Apr 19 2017, 5:19 PM.

Details

Summary

LoopUnroll doesn't seem to be in a state to handle this, and we end discovering later, when we end up with a broken dominator :(
(see https://bugs.llvm.org/show_bug.cgi?id=28103#c3)

Fixes PR28103.

Diff Detail

Repository
rL LLVM

Event Timeline

davide created this revision.Apr 19 2017, 5:19 PM
davide added inline comments.
lib/Transforms/Utils/LoopUnroll.cpp
338–348 ↗(On Diff #95861)

A similar check is done in LSR. Once we agree this is sufficient to handle these cases, maybe we can move the logic to a common file (LoopInfo.h maybe?)

mzolotukhin added inline comments.Apr 19 2017, 5:27 PM
lib/Transforms/Utils/LoopUnroll.cpp
324–329 ↗(On Diff #95861)

This check can probably be removed then.

test/Transforms/LoopUnroll/not-rotated.ll
4 ↗(On Diff #95861)

Could you please add a comment explaining what we're testing here?

12 ↗(On Diff #95861)

I'd prefer replacing i1 true with something like i1 %a, where %a is a function argument. That would make the test more stable against compiler getting smarter and optimizing these branches away in future.

davide updated this revision to Diff 95876.Apr 19 2017, 7:58 PM

Address Michael's comments.

efriedma added inline comments.
lib/Transforms/Utils/LoopUnroll.cpp
332 ↗(On Diff #95876)

It might be simpler to explicitly check the two successors; one should be the header, and the other outside the loop.

You also can't delete the check that BI is non-null and conditional; we specifically assume that later on.

davide added inline comments.Apr 20 2017, 12:55 PM
lib/Transforms/Utils/LoopUnroll.cpp
332 ↗(On Diff #95876)

Thanks for the comments, I'll change that as I also believe it's simpler.
No tests are failing if I remove that check, which is slightly concerning.
I'll try to craft a test where this fails.

zzheng added a subscriber: zzheng.Apr 20 2017, 1:54 PM
Gerolf added a subscriber: Gerolf.Apr 20 2017, 3:27 PM

I don't know if this patch makes the situation better or worse. It seems to touch on the tip of an iceberg. The underlying problem is: What can or should happen when a loop is irreducible? It the answer is "don't unroll", then this is the fix your actually looking for. Obviously this loop is irreducible since it has a retreat edge from sink to body2, but body2 does not dominate sink. I'm also curious if this loop is in the source code already or if some pass in the compiler actually generated. FWIW, unless the compiler has a problem irreducible loops should be rare. And when the user writes an irreducible loop, I think it is OK when compiler optimizations turn conservative.

-Gerolf

lib/Transforms/Utils/LoopUnroll.cpp
328 ↗(On Diff #95876)

There must be a helper routine to answer the question whether a loop is rotated or not. Otherwise each pass may end up having its own definition. I'm also wondering how one decides whether or not a loop is rotated when the loop is irreducible.

The underlying problem is: What can or should happen when a loop is irreducible?

There is no "underlying problem" here. An LLVM "Loop*" always refers to a natural loop; unrolling a Loop is always a well-defined operation (unless we're dealing with something weird like indirectbr). See LoopInfo.h. Our current implementation of loop unrolling only knows how to unroll loops with exactly one latch which is a conditional branch that exits the loop, but that isn't fundamental to the algorithm. We could unroll loops with a more complicated latch, or multiple latches; it's just a matter of teaching the algorithm how to fix up the latches correctly.

I don't know if this patch makes the situation better or worse. It seems to touch on the tip of an iceberg. The underlying problem is: What can or should happen when a loop is irreducible? It the answer is "don't unroll", then this is the fix your actually looking for. Obviously this loop is irreducible since it has a retreat edge from sink to body2, but body2 does not dominate sink. I'm also curious if this loop is in the source code already or if some pass in the compiler actually generated. FWIW, unless the compiler has a problem irreducible loops should be rare. And when the user writes an irreducible loop, I think it is OK when compiler optimizations turn conservative.

-Gerolf

Unless I'm reading the test in the PR incorrectly (which I might) the input contains already the loop (and it's not generated by the compiler).
Please note that the testcase I hit internally and the PR reported upstream are both generated by a fuzzer, and looking at them they don't seem to resemble any kind of real code.
That said, I cannot make a call, but I'm under the impression that loops like this are infrequent enough that bailing out is not necessarily unreasonable. I consider not crashing (or ending up with a corrupt dominator) more important in this case, and in this sense, this patch is an improvement compared to what we have today. If we want to improve the algorithm later to handle more sophisticated latches/multiple latches, we might as well do later (and quite frankly, I wouldn't really go that route until we hit a case where this matters).
What do you think?

mzolotukhin accepted this revision.Apr 20 2017, 5:19 PM

Thanks for addressing my previous remarks! The change looks good to me (modulo Eli's remark regarding the check).

I consider not crashing (or ending up with a corrupt dominator) more important in this case, and in this sense, this patch is an improvement compared to what we have today. If we want to improve the algorithm later to handle more sophisticated latches/multiple latches, we might as well do later (and quite frankly, I wouldn't really go that route until we hit a case where this matters).

Your reasoning makes perfect sense to me.

Michael

lib/Transforms/Utils/LoopUnroll.cpp
332 ↗(On Diff #95876)

I agree that an explicit check would be simpler and easier to understand here.

This revision is now accepted and ready to land.Apr 20 2017, 5:19 PM
davide updated this revision to Diff 96426.Apr 24 2017, 10:41 AM
davide added a reviewer: efriedma.

Updated the check as per Eli's suggestion. PTAL.

efriedma accepted this revision.Apr 24 2017, 12:02 PM

LGTM.

lib/Transforms/Utils/LoopUnroll.cpp
337 ↗(On Diff #96426)

Extra newline.

This revision was automatically updated to reflect the committed changes.