This is an archive of the discontinued LLVM Phabricator instance.

Loop rotation
Needs RevisionPublic

Authored by hiraditya on Jul 21 2016, 8:40 AM.

Details

Summary

This patch implements Loop Rotation Pass:

  1. Canonicalize loop latch to have only one successor.
  2. Clone all the BBs which are exiting the loop (There is a cost function to prevent code size increase)
  3. Adjust phi of cloned BBs
  4. Add phi to the new loop header
  5. Update DOM

With this patch all the basic blocks which are exiting the loop can be copied during rotation. This is helpful for passes like gvn/licm which can now remove loop invariant code
because some computations (which might not dominate all the basic blocks of loop) can now be PRE'd as they are available outside of the loop (due to loop rotation).

Several test cases have been added to exercise loop rotation for different loop bodies.

Relevant test case to demonstrate loop rotation can help gvn.
llvm/test/Transforms/LoopVectorize/vect.omp.persistence.ll

This patch depends on https://reviews.llvm.org/D22558, which is used to clone SEME.

Worked in collaboration with Sebastian Pop

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

Essentially, if the header and latch both are exiting, the loop will not rotate (as per your suggestion).

Can you please explain why we need to rotate those loops? Then we can figure out heuristics that we can use here.

We need to rotate loops because of two reasons:

  1. To make the loop in a canonical form.
  2. To expose redundancies by cloning the basic blocks which are exiting out of the loop.
    • If we add the check that (when a loop latch is exiting then don't rotate the loop), then the computations like load in all the basic blocks which are exiting the loop, except header cannot PRE'd.
    • Even if a loop is in canonical form, we may still want to rotate it to expose redundancies.

The vectorizer already tags loops with metadata, so I assumed having it here should have been okay.

The vectorizer is a different beast. When we vectorize a loop, we usually don't want other passes to touch it afterwards at all. That's why we use metadata, we kind of say "this loop is as good as we can get, leave it alone".

In case of loop-rotation it's not the case - we are not sure that the loop is in the best position even in terms of rotation after one iteration of loop-rotate. Using metadata to avoid further rotation seems like an attempt to paper over a real problem, i.e. finding the best candidate for the bottom check for the loop versus trying to get lucky with that.

When I suggested to rotate only loops that have not-exiting latch, that was my attempt to create a heuristics to find that 'best candidate' for the bottom check. Your testing shows that it's not good enough, so my question is what cases this heuristics misses. Probably we just need to take into account some additional characteristics of the loop and it'll work just fine.

Michael

I think putting a set of heuristics is not going to help because that way redundancies cannot be exposed in loops which appear to the loop rotation as rotated.
I can just remove/disable those test cases for now and may be improve on those test cases later.

We need to rotate loops because of two reasons:

  • To make the loop in a canonical form.
  • To expose redundancies by cloning the basic blocks which are exiting out of the loop.

These are two completely separate goal and we should make a clear distinction between them. I think loop-rotate should be primarily used to achieve to canonicalize loops, and my impression of this patch was that it'll just help us to handle more loops, which is great.

If you also intend to use loop-rotate as an actual optimization (to achieve the second goal), I'd suggest adding a separate mode, maybe even separate pass, for it, which will reuse the same infrastructure, but will be driven by completely different factors. It'll probably be also scheduled in some other place in the pipeline.

Also, speaking about the tests:

LLVM :: Transforms/GVNHoist/pr29031.ll
LLVM :: Transforms/LoopRotate/loop-rotate-before-latch.ll
LLVM :: Transforms/LoopRotate/multiple-exits.ll
LLVM :: Transforms/LoopRotate/pr7447.ll

Why do these fail? From the first glance it looks like they don't require rotating loops with exiting latch. Also, in the original code we explicitly had

if (L->isLoopExiting(OrigLatch))
  return false;

How could we possible rotate the loops before? Could you please investigate it in more details?

Thanks,
Michael

FWIW I agree with @mzolotukhin and I'm not a fan of using a metadata to achieve this: I rather have a principled way of deciding what to do / reach idempotent state just by looking at the code.

hiraditya updated this revision to Diff 75434.Oct 21 2016, 8:18 AM

Addressed Michael's comments about removing the metadata support and identifying already rotated loops.

  • Do not rotate the loop if the latch is already exiting.
  • Do not add any metadata specifying the loop has been rotated.
hiraditya updated this revision to Diff 76239.Oct 28 2016, 1:05 PM

Addressed the issue when a loop may have two back edges.

bjope added a subscriber: bjope.Oct 31 2016, 9:46 AM
bjope added inline comments.
llvm/test/Transforms/LoopRotate/phi-duplicate.ll
31

The sole purpose with this test case seems to be to verify PR5837, and to make sure that there is only one phi (no duplicates created). Now you have introduced new CHECK statements to verify that we do get multple phi nodes.

If we still think that this test case is important and that that we only want want phi for this code, then I guess it still should verify that there is only one phi.
If the world has changed and we now think that multiple phi nodes are wonderful, then I either expect that the test case is obsolete and can be removed. Or there should be a pretty good informative explanation why the test case has mutated in this way (no longer verifying the same thing as it initially was intended do verify).

hiraditya added inline comments.Nov 7 2016, 8:34 AM
llvm/test/Transforms/LoopRotate/phi-duplicate.ll
31

Thanks for pointing this out. The current loop-rotation calls SSAUpdater::RewriteUse to remove multiple PHIs. The new loop rotation is simpler and does not use SSAUpdater. For this test case calling

./bin/opt -loop-rotate -simplifycfg -S < ../llvm/test/Transforms/LoopRotate/phi-duplicate.ll

would remove multiple phis (simplifycfg is called later in the pass pipeline at -O2 and -O3 anyways). I can edit the test case by adding -simplifycfg or modify the comment as well whichever you prefer.

bjope added inline comments.Nov 9 2016, 1:05 AM
llvm/test/Transforms/LoopRotate/phi-duplicate.ll
31

I have no personal preference here. I just happened to notice that the test case no longer mapped to the description/history of the test case (such as this comment, the reference to PR5837 earlier in this file, etc).

If there is no purpose with the test case (except showing the history of how loop-rotate has evovled), then maybe it should be removed? (with that said - I have no idea if it is custom to remove test cases in llvm)

Simplest solution is probably to just add some comments describing what the original purpose with the test case was, and why it has been changed into testing something else.

Hi,

Sorry for the long delay, I'm now trying to catch up with the reviews after the conference. Please find some comments below.

Thanks,
Michael

llvm/lib/Transforms/Scalar/LoopRotation.cpp
544

Could we also check that LoopSimplify is also preserved?

llvm/test/Analysis/GlobalsModRef/memset-escape.ll
9–22

Can you please explain why this test was changed?

llvm/test/Transforms/LoopRotate/alloca.ll
8–11

Do we really need this change?

llvm/test/Transforms/LoopRotate/dbgvalue.ll
8–11

Why was this test changed?

llvm/test/Transforms/LoopRotate/indirectbr-1.ll
2

Can we merge all tests with the same command lines to a single file?

llvm/test/Transforms/LoopRotate/loop-rotate-before-latch.ll
7–8

Please add a comment about what we check in this test.

llvm/test/Transforms/LoopRotate/loop-rotate.ll
2–10

Why can't we run them together?

16

Better to use @bar0 to avoid potential undesired matches somewhere else in the output.

llvm/test/Transforms/LoopRotate/multiple-exits.ll
78–81

Can we check the expected IR in more details? Currently, from the CHECK lines it's hard to tell what we expect (and it's hard to assess the change proposed in this patch). Comments also might help.

llvm/test/Transforms/LoopRotate/nosimplifylatch.ll
6–8

Why do we need this change?

llvm/test/Transforms/LoopRotate/phi-duplicate.ll
31

If these phi-nodes are unnecessary, I think we should not create them in the first place. Loop-rotate is usually one of the first passes among loop passes and other loop passes will deal with what loop-rotate produces. Simplifycfg will only be run afterwards.

How hard will it be to clean the phis up in loop-rotate?

llvm/test/Transforms/LoopRotate/pr7447.ll
5–6

Can we instead check the actual CFG and not rely on the debug/stats output?

llvm/test/Transforms/LoopRotate/preserve-loop-simplify.ll
19–25

Why did this test change? Shouldn't we be producing the same results on such cases?

llvm/test/Transforms/LoopRotate/simplifylatch.ll
47

Does rotated loop has a preheader now? If not, we're breaking LoopSimplify form, which is not good.

llvm/test/Transforms/LoopVectorize/vect.omp.persistence.ll
7–12

This test actually should probably be rewritten.

It tries to check that

  1. loop-rotate doesn't drop metadata,
  2. no pass in -O2 pipeline before the vectorizer drops metadata.

The first check should be a separate test for loop-rotate, so I suggest adding it explicitly now (or in a separate commit). Then, one function from this test can be removed, and comments updates.

hiraditya updated this revision to Diff 78905.Nov 22 2016, 11:33 AM

Preserve loop-simplify form.
Do not generate redundant phis.

hiraditya added inline comments.Nov 22 2016, 11:35 AM
llvm/test/Analysis/GlobalsModRef/memset-escape.ll
9–22

The loop rotation causes the loop to be unrolled completely as a result the call to @abort is eliminated.

Quoted Text

llvm/test/Transforms/LoopRotate/alloca.ll
8–11

I can remove the change.

llvm/test/Transforms/LoopRotate/preserve-loop-simplify.ll
19–25

Thanks for pointing this out. I have added code to restore the loop-simplify form.

llvm/test/Transforms/LoopRotate/simplifylatch.ll
47

Yes the rotated loop has a preheader.

hiraditya updated this revision to Diff 78907.Nov 22 2016, 11:41 AM

Rebase against master.

hiraditya updated this revision to Diff 80303.Dec 5 2016, 11:49 AM

Removed multiple calls to opt in llvm/test/Transforms/LoopRotate/loop-rotate.ll

mzolotukhin requested changes to this revision.Dec 14 2016, 3:18 PM
mzolotukhin edited edge metadata.

Hi,

Sorry for the delay, please find some comments inline.

Many of them are about the tests - I still feel uneasy about bugpoint generated tests. It's hard to tell what they're checking and it would be almost impossible to say if they are relevant or not after a couple of changes in the code. Can you correlate the place in the code with every test (e.g. if we comment out check A, then test A starts to fail)? If so, I'm pretty sure that you can reduce corresponding tests even more (in fact, it's often better to actually write them from scratch and use the bugpoint-generated programs just as a hint of what properties the test should have). If you can not, then I think there is no value in such tests. I also think that some of the tests are actually identical. I'm might sound picky here, but if we don't write good tests now, we'll end up with not-so-good tests in future.

Thanks,
Michael

llvm/include/llvm/Analysis/LoopInfo.h
444

This still needs to be documented. It might be unclear what instruction we return here.

llvm/lib/Transforms/Scalar/LoopRotation.cpp
12

Don't we clone other blocks too? Exiting blocks might be a boundary for the region we clone, but this region can contain non-exiting blocks too. Is it correct?

Also, I think this comment does not need to cover implementation details at all. If we want to make it more verbose, then we should rather describe what loop rotation means, what loops are affected, and what properties we guarantee after the transformation for rotated loops.

202

I think this check is not needed now. What we want to look at is the loop edge (and we do it just before this check) - loop rotation should make it exiting. But even if you want to keep this check, the comment needs to be updated as it was written for the limitations of the old implementation.

246

Why is this called 'TODO'?

261

if getNumOperands != 2, then we'll break from this loop and then create a phi-node with 2 predecessors, which will be invalid.

Can we assert that it equals 2?

269

This line seems too long.

284

s/Ins/Inst/

465

Wouldn't it be better to check if the loop has indirect branches and bail out before we begin doing anything?

473

We're doing something to arrange new blocks below. Please either say what specifically is missing or remove this TODO in case it's actually done.

477

Why is this under DEBUG?

543

Nitpick: please verify DT first (since LI uses it).

566–567

Yes, please rename it.

601

s/see (collectSEMEBlocks)/(see collectSEMEBlocks)/

llvm/test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll
1–2

This test is no longer relevant, it doesn't fail if the change it went in with is reverted.

Could you please remove it (in a separate commit) altogether?

llvm/test/Transforms/LoopRotate/dbgvalue.ll
8–11

The question is still relevant.

llvm/test/Transforms/LoopRotate/loop-rotate-before-latch.ll
2

Why do we need -stats here? We never check them.
Why do we run -loop-rotate twice?

llvm/test/Transforms/LoopRotate/multiple-exits.ll
6–18

Why do we need to move it?
The second function has CHECK-lines after its body, so we are inconsistent now.

Also, we have pr7447.ll test. Can we merge these files maybe?

llvm/test/Transforms/LoopRotate/nosimplifylatch.ll
6–8

The question is still relevant.

llvm/test/Transforms/LoopRotate/phi-duplicate.ll
36–45

Can we add CHECK-NOT to make sure that no other phis are present?

llvm/test/Transforms/LoopRotate/preserve-loop-simplify.ll
19–25

Can't we cancel the changes to the test then?

llvm/test/Transforms/LoopRotate/simplifylatch.ll
48–60

If we really want to check the entire contents of the loop, then we should use CHECK-NEXT. However, I'm not a fan of it - we should only check what matters.

llvm/test/Transforms/LoopVectorize/vect.omp.persistence.ll
7–12

The test in the current form is hard to maintain, and with every change we risk that it becomes irrelevant. Could you please address it?

This revision now requires changes to proceed.Dec 14 2016, 3:18 PM
hiraditya updated this revision to Diff 82375.Dec 22 2016, 3:21 PM
hiraditya edited edge metadata.
hiraditya marked 8 inline comments as done.

Addressed Michael's comments.

llvm/lib/Transforms/Scalar/LoopRotation.cpp
465

This pass is able to rotate the loop when there are indirect branches inside it, so that would help expose redundancies in more cases. If there is a failing case or there is a regression please let me know.

473

I'll remove this.

477

This variable is only used for verification and as such not needed in release mode.

llvm/test/Transforms/LoopRotate/preserve-loop-simplify.ll
19–25

The names of copied basic blocks are not the same, and the order also changes because of extra basic blocks, so we need the changes here.

llvm/test/Transforms/LoopRotate/simplifylatch.ll
48–60

Thanks for the suggestion. I removed the test because it wasn't checking anything special.

llvm/test/Transforms/LoopVectorize/vect.omp.persistence.ll
7–12

I can clone this test in test/Transforms/LoopRotate directory and add the loop rotation related checks, if that is more reasonable.

mzolotukhin requested changes to this revision.Dec 28 2016, 1:44 PM
mzolotukhin edited edge metadata.

Hi,

Please find some remarks inline. Also, some remarks from previous reviews haven't been addressed yet.

Thanks,
Michael

llvm/lib/IR/Metadata.cpp
1109–1112

Can we remove this function and use SmallVector::append instead?

llvm/lib/Transforms/Scalar/LoopRotation.cpp
18–21

Nitpicks: 1) sentences should end with a dot. 2) I'd prefer to have some bullets in this list (I mean formatting), like:

- property1
- property2
196

Maybe I forgot something, but why exactly do we still need this check? I thought that one of the main benefits of this patch was to remove this limitation.

247

Why is it called 'TODO'?

265–266

Is it possible at all? I think in this loop we expect phi nodes to be of a some specific form, i.e. having 2 operands: NewLatch and NewPreheader. Shouldn't we just assert this instead of continue the loop?

332

Missing dot before Returns.

576

Please rename the function per the previous discussion.

llvm/test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll
1–2

Still relevant.

llvm/test/Transforms/LoopRotate/phi-duplicate.ll
36–45

It can be CHECK-NEXT I guess.

llvm/test/Transforms/LoopRotate/preserve-loop-simplify.ll
19–25

Could you please show what was the original behavior in this test and what do we do now? I'd like to make sure we are not rendering this test useless.

llvm/test/Transforms/LoopVectorize/vect.omp.persistence.ll
7–12

Yes, we should do something like this. Please do this in a separate patch.

This revision now requires changes to proceed.Dec 28 2016, 1:44 PM
hiraditya marked an inline comment as done.Jan 11 2017, 8:22 AM
hiraditya added inline comments.
llvm/lib/IR/Metadata.cpp
1109–1112

We can but then there should be a way to get the Attachments from MDAttachmentMap. Currently there is none.

llvm/lib/Transforms/Scalar/LoopRotation.cpp
196

If the loop-header has invoke instruction, or some other TerminatorInst, I'm not sure how to deal with them.

247

Because, even if the loop's size is greater than RotationMaxSize, what we can do is peel fewer basic blocks than needed to completely rotate the loop. That way, at least, some redundancies will be exposed.

llvm/test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll
1–2

The test fails if I remove simplifycfg.

llvm/test/Transforms/LoopRotate/preserve-loop-simplify.ll
19–25

Originally, only the basic block inner.body was cloned outside the loop which became the new loop header. In the new implementation inner.header and inner.body both are cloned outside the loop such that inner.latch becomes the new loop header.

hiraditya updated this revision to Diff 83981.Jan 11 2017, 8:24 AM
hiraditya edited edge metadata.

Addressed Michael's comments.

mzolotukhin added inline comments.Jan 11 2017, 4:09 PM
llvm/test/Transforms/LoopRotate/indirectbr-1.ll
7

We have a test checking this in loop-rotate.ll (@foo3). How are they different? Can we combine them (and place in one file)?

llvm/test/Transforms/LoopRotate/loop-rotate.ll
211

Will the following routine test the same?

define i32 @bar5() {

entry:
  br label %loop.header

loop.header:
  %a = phi i32 [ %b, %latch ], [ 0, %entry ]
  switch i8 undef, label %loop.body [
    i8 0, label %unreach
    i8 1, label %unreach
  ]

loop.body:
  br i1 undef, label %latch, label %return

latch:
  %b = phi i32 [ %a, %loop.body ]
  br label %loop.header

unreach:
  unreachable

return:
  ret i32 0
}

If it's sufficient, can you minimize other test in the similar manner? It should be much easier to understand what's going on, and hopefully they'll be much less fragile.

mzolotukhin added inline comments.Jan 11 2017, 4:09 PM
llvm/lib/Transforms/Scalar/LoopRotation.cpp
247

I see, then I guess it should be expressed clearer in the comment. Currently it's not obvious what is there that needs to be done.

llvm/test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll
1–2

It doesn't test what it was supposed to test. We either need to make sure it's useful, or remove it. I tried to revert the change the test was commited with and the test still passed, which means it no longer checks what it checked before. If you remove -simplifycfg it starts to fail, sure (I assume because there is for.body in the output) - but can you explain why there shouldn't be for.body? Can you explain what this test does? Juggling flags just to make it passes doesn't help us and only slows down everyone (mostly you, as you have to deal with it:) ).

llvm/test/Transforms/LoopRotate/multiple-exits-merge-phi.ll
3–4

Please remove this.

9

How is it different from the test in multiple-exits.ll? What phis are merged (the name of the test hints that they should be)?

llvm/test/Transforms/LoopRotate/vect.omp.persistence.ll
1–2 ↗(On Diff #83981)

We don't need to run the entire pipeline to check that loop-rotate doesn't drop metadata. Please keep only the loop-rotate part here (but please make sure we actually check the metadata - that's what this test was about).

llvm/test/Transforms/LoopVectorize/vect.omp.persistence.ll
22

Please update the comments, as the test has nothing to do with loop-rotate now. I'd recommend committing it separately.

hiraditya marked 3 inline comments as done.Jan 13 2017, 8:48 AM
hiraditya added inline comments.
llvm/test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll
1–2

The for.body gets deleted because, once the loop is rotated everything in the loop becomes redundant/invariant. Previously, loop-rotate used to call simplifycfg, which I removed. So, I added the -simplifycfg in this test to make sure that the behavior is preserved.

I agree, it does not seem to test what it is supposed to. I can just remove this test (maybe in a separate patch together with changes related to vect.omp.persistence.ll)

llvm/test/Transforms/LoopRotate/indirectbr-1.ll
7

This test checks that loop-latch having indirect branch is not rotated. This is different from all the tests in loop-rotate.ll. I'll merge this in loop-rotate.ll.

llvm/test/Transforms/LoopRotate/multiple-exits-merge-phi.ll
9

It seems both are same. merge-phi is the phi in return statement, I was just trying to distinguish this from loop-header phi. I'll remove this test as this is redundant.

llvm/test/Transforms/LoopVectorize/vect.omp.persistence.ll
22

Will do

hiraditya updated this revision to Diff 84315.Jan 13 2017, 8:49 AM
hiraditya edited edge metadata.

Addressed Michael's comments.

Removed redundant tests
Merged indirectbr-1.ll into loop-rotate.ll

Please address my previous remarks regarding the tests.

hiraditya updated this revision to Diff 87288.Feb 6 2017, 1:07 PM

Fixed other test cases as per the review.

llvm/test/Transforms/LoopRotate/loop-rotate.ll
211

I have minimized other tests as well.

llvm/test/Transforms/LoopRotate/nosimplifylatch.ll
6–8

After for-in there is a phi now

mzolotukhin requested changes to this revision.Feb 28 2017, 7:00 PM

Hi,

Please find some comments inline. Also, please reinspect the tests - in many of them the comments don't correspond to test bodies, they are not minimal, and some tests duplicate others.

Thanks,
Michael

llvm/lib/Transforms/Scalar/LoopRotation.cpp
19

Why do we need this requirement?

24

Please end sentences with dots.

101–103

This function seems to be unused.

167–169

Formatting is slightly off here.

194–197

I don't understand how this comment corresponds to the code.

202

Why do we need this check?

254–266

Please add a comment about what this function is doing and what it expects.

293

Why is UserInst guaranteed to be a PHINode?

332–333

I find it a bit confusing that you're saying about blocks being copied while the function in fact just populates the list.

351–374

I think this check is the reason you kept that OrigH->isExiting() check. I think that what we rather should do here is to copy all blocks up to an exiting block that we're going to make a new latch. Does it make sense?

In other words, I'd like the following case to be rotated:
Entry -> {A}
A -> {B}
B -> {Exit, C}
C -> {A}

I see that current implementation is generic enough to handle such cases, and the only reasons why it won't do it is that (IMHO unnecessary) limitations.

399

...a constant, a function argument, or a global.

437–438

Why don't we need to update LI if there is no parent loop?

463

You have the same typedef inside LoopRotate.

464–467

If it's not used anywhere, please remove it.

530

Can we avoid quadratic complexity here?

llvm/test/Transforms/LoopRotate/loop-rotate.ll
74

This function doesn't have any indirect branches.

150–154

Why do we need two switches in this test?

This revision now requires changes to proceed.Feb 28 2017, 7:00 PM
hiraditya marked 7 inline comments as done.Mar 3 2017, 9:43 AM

Hi,

Please find some comments inline. Also, please reinspect the tests - in many of them the comments don't correspond to test bodies, they are not minimal, and some tests duplicate others.

Thanks,
Michael

Thank you for the detailed review. I did not try to remove so much from tests from file other than loop-rotate.ll because they were there from the past.
For loop-rotate.ll I think the tests are a combination of multiple scenarios, and it will be good to have them.

llvm/lib/Transforms/Scalar/LoopRotation.cpp
293

Because Inst does not dominate UserInst it must be the loop-closed-phi as the loop is in loop-closed-ssa form.

332–333

I've updated the comment.

351–374

We can certainly do that. From other reviewers (including you) there were comments in the past that the loop-rotation should have a way to reach idempotence. If we keep rotating when the header is not exiting, there will be no way to stabilize loop rotation.

437–438

For the current loop under rotation, there are no new basic blocks added. Only when the loop-header is changed around line 539 L->moveToHeader is called.

530

Actually this while loop is bounded by the number of exiting basicblocks from the loop which were cloned.

llvm/test/Transforms/LoopRotate/loop-rotate.ll
74

I'll update the comment.

150–154

This switch statement is a loop preheader as it is branching to the loop header. So I think, it would exercise if the dominators are updated properly.

hiraditya updated this revision to Diff 90501.Mar 3 2017, 9:45 AM
hiraditya edited edge metadata.

Addressed comments from Michael.

mzolotukhin requested changes to this revision.Mar 9 2017, 3:04 PM

Please fix the tests as requested.

We need to cover multiple scenarios by a minimal set of tests. There is no need in combining scenarios unless it triggers some corner case (in which case we should explicitly state which corner case we're testing). For instance, using a custom type %fp is completely irrelevant from what loop-rotation is doing, so it should be removed from the test. Many tests contain unreachable blocks (I realize you get them from bugpoint) - what's the purpose of keeping them in the test? Why can't we remove them? And so forth...

Michael

llvm/lib/Transforms/Scalar/LoopRotation.cpp
530

Can you elaborate? I don't see any exits from the loop, but I see how we start from the beginning.

llvm/test/Transforms/LoopRotate/loop-rotate.ll
12

Why can't we use i64 instead of %fp?

150–154

Loop simplify splits the edge to the loop anyway. Thus, this test, if checking anything, checks only loop simplify. For testing loop-rotation the first switch is absolutely unnecessary.

This revision now requires changes to proceed.Mar 9 2017, 3:04 PM
hiraditya updated this revision to Diff 91422.Mar 10 2017, 2:51 PM
hiraditya edited edge metadata.

Removed unreachable from testcases.
Replaced fp* with i64*

llvm/lib/Transforms/Scalar/LoopRotation.cpp
530

This part of code executes only for the basic blocks which are not in the loop, i.e., exit basic blocks. For the exit basic blocks dominator tree may not be up to date and hence is being updated here. Once the exit basic blocks have their dominators up-to-date, and since their sub-trees are already up-to-date => NewIDom == StaleIDom (line:581) for all successors of exit basic blocks.

llvm/test/Transforms/LoopRotate/loop-rotate.ll
150–154

There is no loop-simplify in the new loop rotation.

This revision now requires changes to proceed.Apr 24 2017, 8:40 AM
bjope removed a subscriber: bjope.May 10 2017, 12:11 AM

@mzolotukhin Please let me know if you have any further comments.

Gentle ping and a few comments. There are a few proprietary benchmarks that perform better with this pass and I'd like to see this (hopefully) moving towards a commit.

llvm/lib/Analysis/LoopInfo.cpp
225

What does getLoopID() return today in the event of multiple latches? @hiraditya maybe it makes sense, for now at least, to return { nullptr, nullptr }; when size of GetLoopLatches() > 1?

llvm/lib/IR/Metadata.cpp
1311

I'd prefer a message more like "No Instruction Metadata found".

llvm/lib/Transforms/Scalar/LoopRotation.cpp
71–73

The bug is marked as fixed by a duplicate. Could you please remove and verify it is working?

FYI: https://bugs.llvm.org/show_bug.cgi?id=28104

196

It'd be helpful to have a comment mentioning that you're not handling the unconventional exits like invoke.

293

This also would be good to have as a comment. And possibly an assert() that validates the claim.

bjope added a subscriber: bjope.Oct 25 2018, 3:48 AM
fhahn added a subscriber: fhahn.Mar 21 2020, 1:47 PM
hiraditya added a comment.EditedMar 24 2020, 10:12 AM

An interesting case to explore: https://bugs.llvm.org/show_bug.cgi?id=27360

LLVM does not peel/unroll loops with multiple exits. With this loop rotation this should be possible.

TODO: Seems like this loop rotation can help here: https://reviews.llvm.org/D44823

An interesting case to explore: https://bugs.llvm.org/show_bug.cgi?id=27360
LLVM does not peel/unroll loops with multiple exits. With this loop rotation this should be possible.

LLVM supports unrolling multi-exit loops with runtime trip counts as in the bug, but it requires an option by default (-unroll-runtime -unroll-runtime-multi-exit). The example in PR27360 actually gets unrolled on master, due to the pragma forcing unrolling. Without the pragma, unrolling does not happen, but that is due to a TODO in the runtime loopunroller code.

Could you do the following?

  1. Rebase to the current master. The diff does not apply.
  1. Make the title more concrete. This is not the initial implementation of loop rotation
  1. Describe in the summary what the changes are compared to the current LoopRotation pass.
  1. Clarify the summary "Canonicalize loop latch to have only one successor." An already-rotated loop will have two successors: the header and the loop exit. Does this mean it will split the backedge just to have a latch with just the backedge as successor? Will the empty block be removed again?
llvm/lib/Transforms/Scalar/LoopRotation.cpp
18

This is true for all LoopInfo-detected loops.

Herald added a project: Restricted Project. · View Herald TranscriptJul 19 2020, 4:20 AM
sanjoy resigned from this revision.Jan 29 2022, 5:26 PM
lebedev.ri resigned from this revision.Jan 12 2023, 4:57 PM

This review may be stuck/dead, consider abandoning if no longer relevant.
Removing myself as reviewer in attempt to clean dashboard.

Herald added a project: Restricted Project. · View Herald TranscriptJan 12 2023, 4:57 PM