Loop rotation

[hiraditya]

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

[hiraditya]

In D22630#574886, @mzolotukhin wrote:

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.

[mzolotukhin]

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

[mehdi_amini]

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]

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]

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

[bjope]

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]

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]

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.

[mzolotukhin]

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

606

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–10 ↗

(On Diff #76239)

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

1 ↗

(On Diff #76239)

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

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

6–7 ↗

(On Diff #76239)

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

76–83

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–9

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

4–5 ↗

(On Diff #76239)

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

llvm/test/Transforms/LoopRotate/preserve-loop-simplify.ll

22–28

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

llvm/test/Transforms/LoopRotate/simplifylatch.ll

45

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–10

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]

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

[hiraditya]

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–10 ↗

(On Diff #76239)

I can remove the change.

llvm/test/Transforms/LoopRotate/preserve-loop-simplify.ll

22–28

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

llvm/test/Transforms/LoopRotate/simplifylatch.ll

45

Yes the rotated loop has a preheader.

[hiraditya]

Rebase against master.

[hiraditya]

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

[hiraditya]

Ping

[mzolotukhin]

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.

193–195

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.

239

Why is this called 'TODO'?

256

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?

264

This line seems too long.

290

s/Ins/Inst/

515

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

523

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.

527

Why is this under DEBUG?

605

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

628–629

Yes, please rename it.

654

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

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

0

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

1 ↗

(On Diff #80303)

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–7

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–9

The question is still relevant.

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

36–43

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

llvm/test/Transforms/LoopRotate/preserve-loop-simplify.ll

22–28

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

llvm/test/Transforms/LoopRotate/simplifylatch.ll

46–58

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–10

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?

[hiraditya]

Addressed Michael's comments.

llvm/lib/Transforms/Scalar/LoopRotation.cpp

515

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.

523

I'll remove this.

527

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

llvm/test/Transforms/LoopRotate/preserve-loop-simplify.ll

22–28

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

46–58

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

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

7–10

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

[mzolotukhin]

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

192

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.

240

Why is it called 'TODO'?

260–261

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?

356

Missing dot before Returns.

638

Please rename the function per the previous discussion.

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

0

Still relevant.

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

36–43

It can be CHECK-NEXT I guess.

llvm/test/Transforms/LoopRotate/preserve-loop-simplify.ll

22–28

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–10

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

[hiraditya]

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

192

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

240

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

0

The test fails if I remove simplifycfg.

llvm/test/Transforms/LoopRotate/preserve-loop-simplify.ll

22–28

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]

Addressed Michael's comments.

[mzolotukhin]

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

6 ↗

(On Diff #83981)

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]

llvm/lib/Transforms/Scalar/LoopRotation.cpp

240

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

0

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

2–3 ↗

(On Diff #83981)

Please remove this.

8 ↗

(On Diff #83981)

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

2–3

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

19

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

[hiraditya]

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

0

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

6 ↗

(On Diff #83981)

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

8 ↗

(On Diff #83981)

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

19

Will do

[hiraditya]

Addressed Michael's comments.

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

[hiraditya]

Rebase

[hiraditya]

ping

[mzolotukhin]

Please address my previous remarks regarding the tests.

[hiraditya]

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–9

After for-in there is a phi now

[hiraditya]

ping

[mzolotukhin]

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.

108–110

This function seems to be unused.

151–153

Formatting is slightly off here.

182–185

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

193–195

Why do we need this check?

249–272

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

317

Why is UserInst guaranteed to be a PHINode?

356–357

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

375–399

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.

424

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

462–463

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

504–513

You have the same typedef inside LoopRotate.

505–508

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

584

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?

[hiraditya]

In D22630#689237, @mzolotukhin wrote:

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

317

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

356–357

I've updated the comment.

375–399

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.

462–463

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.

584

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]

Addressed comments from Michael.

[mzolotukhin]

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

584

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.

[hiraditya]

Removed unreachable from testcases.
Replaced fp* with i64*

llvm/lib/Transforms/Scalar/LoopRotation.cpp

584

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.

[hiraditya]

Ping

[hiraditya]

Ping

[hiraditya]

Ping

[hiraditya]

Ping

[hiraditya]

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

[xbolva00]

Ping

@hfinkel

[brzycki]

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

78–80

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

192

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

317

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

[hiraditya]

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

[fhahn]

In D22630#1939540, @hiraditya wrote:

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.

[Meinersbur]

Could you do the following?

1. Rebase to the current master. The diff does not apply.

2. Make the title more concrete. This is not the initial implementation of loop rotation

3. Describe in the summary what the changes are compared to the current LoopRotation pass.

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

[lebedev.ri]

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

llvm/include/llvm/Analysis/LoopInfo.h

   bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const;
 
   /// Return true if the Loop is in the form that the LoopSimplify form
   /// transforms loops to, which is sometimes called normal form.
   bool isLoopSimplifyForm() const;
 
   /// Return true if the loop body is safe to clone in practice.
   bool isSafeToClone() const;
 
   /// Returns true if the loop is annotated parallel.
   ///
   /// A parallel loop can be assumed to not contain any dependencies between
   /// iterations by the compiler. That is, any loop-carried dependency checking
   /// can be skipped completely when parallelizing the loop on the target
   /// machine. Thus, if the parallel loop information originates from the
   /// programmer, e.g. via the OpenMP parallel for pragma, it is the
   /// programmer's responsibility to ensure there are no loop-carried
   /// dependencies. The final execution order of the instructions across
   /// iterations is not guaranteed, thus, the end result might or might not
   /// implement actual concurrent execution of instructions across multiple
   /// iterations.
   bool isAnnotatedParallel() const;
 
+  /// Return the llvm.loop loop id metadata node for this loop and the
+  /// instruction which contains the metadata. If there is no such instruction
+  /// having a loop metadata then return a pair of nullptrs.
+  std::pair<MDNode *, Instruction *> getLoopIDWithInstr() const;
+
   /// Return the llvm.loop loop id metadata node for this loop if it is present.
   ///
   /// If this loop contains the same llvm.loop metadata on each branch to the
   /// header then the node is returned. If any latch instruction does not
   /// contain llvm.loop or or if multiple latches contain different nodes then
   /// 0 is returned.
-  MDNode *getLoopID() const;
+  MDNode *getLoopID() const { return getLoopIDWithInstr().first; }
+
   /// Set the llvm.loop loop id metadata for this loop.
   ///
   /// The LoopID metadata node will be added to each terminator instruction in
   /// the loop that branches to the loop header.
   ///
   /// The LoopID metadata node should have one or more operands and the first
   /// operand should be the node itself.
   void setLoopID(MDNode *LoopID) const;

llvm/include/llvm/IR/Instruction.h

   /// This does the same thing as getAllMetadata, except that it filters out the
   /// debug location.
   void getAllMetadataOtherThanDebugLoc(
       SmallVectorImpl<std::pair<unsigned, MDNode *>> &MDs) const {
     if (hasMetadataOtherThanDebugLoc())
       getAllMetadataOtherThanDebugLocImpl(MDs);
   }
 
+  /// Get all the metadata IDs attached to this Instruction except the ones
+  /// associated with debug location. The Vector \p MDIDs is not cleared.
+  void getAllNonDebugMetadataIDs(SmallVectorImpl<unsigned> &MDIDs) const;
+
   /// Fills the AAMDNodes structure with AA metadata from this instruction.
   /// When Merge is true, the existing AA metadata is merged with that from this
   /// instruction providing the most-general result.
   void getAAMetadata(AAMDNodes &N, bool Merge = false) const;
 
   /// Set the metadata of the specified kind to the specified node. This updates
   /// or replaces metadata if already present, or removes it if Node is null.
   void setMetadata(unsigned KindID, MDNode *Node);

llvm/include/llvm/Transforms/Scalar.h

 // LoopReroll - This pass is a simple loop rerolling pass.
 //
 Pass *createLoopRerollPass();
 
 //===----------------------------------------------------------------------===//
 //
 // LoopRotate - This pass is a simple loop rotating pass.
 //
-Pass *createLoopRotatePass(int MaxHeaderSize = -1);
+Pass *createLoopRotatePass();
 
 //===----------------------------------------------------------------------===//
 //
 // LoopIdiom - This pass recognizes and replaces idioms in loops.
 //
 Pass *createLoopIdiomPass();
 
 //===----------------------------------------------------------------------===//

llvm/lib/Analysis/LoopInfo.cpp

     for (Instruction &I : *BB)
       if (auto CS = CallSite(&I))
         if (CS.cannotDuplicate())
           return false;
   }
   return true;
 }
 
-MDNode *Loop::getLoopID() const {
+std::pair<MDNode *, Instruction *> Loop::getLoopIDWithInstr() const {
   MDNode *LoopID = nullptr;
+  Instruction *I = nullptr;
   if (BasicBlock *Latch = getLoopLatch()) {
-    LoopID = Latch->getTerminator()->getMetadata(LLVMContext::MD_loop);
+    I = Latch->getTerminator();
+    LoopID = I->getMetadata(LLVMContext::MD_loop);
   } else {
     // Go through each predecessor of the loop header and check the
     // terminator for the metadata.
     for (BasicBlock *BB : predecessors(getHeader())) {
       if (!this->contains(BB))
         continue;
 
       TerminatorInst *TI = BB->getTerminator();
       if (MDNode *MD = TI->getMetadata(LLVMContext::MD_loop)) {
-        if (!LoopID)
+        if (!LoopID) {
           LoopID = MD;
-        else if (MD != LoopID) // Multiple MD_loop found => corrupt metadata.
-          return nullptr;
+          I = TI;
+        } else // Multiple MD_loop found.
+          return { nullptr, nullptr };
       }
     }
   }
   if (!LoopID || LoopID->getNumOperands() == 0 ||
       LoopID->getOperand(0) != LoopID)
-    return nullptr;
-  return LoopID;
+    return { nullptr, nullptr };
+  return { LoopID, I };
 }
 
 void Loop::setLoopID(MDNode *LoopID) const {
   assert(LoopID && "Loop ID should not be null");
   assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand");
   assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself");
 
   if (BasicBlock *Latch = getLoopLatch()) {

llvm/lib/IR/LLVMContextImpl.h

   }
   unsigned getHashValue() const {
     return hash_combine(MIType, Line, File, Elements);
   }
 };
 
 /// \brief DenseMapInfo for MDNode subclasses.
 template <class NodeTy> struct MDNodeInfo {
   typedef MDNodeKeyImpl<NodeTy> KeyTy;
   typedef MDNodeSubsetEqualImpl<NodeTy> SubsetEqualTy;
   static inline NodeTy *getEmptyKey() {
     return DenseMapInfo<NodeTy *>::getEmptyKey();
   }
   static inline NodeTy *getTombstoneKey() {
     return DenseMapInfo<NodeTy *>::getTombstoneKey();
   }
   static unsigned getHashValue(const KeyTy &Key) { return Key.getHashValue(); }

   void erase(unsigned ID);
 
   /// \brief Copy out all the attachments.
   ///
   /// Copies all the current attachments into \c Result, sorting by attachment
   /// ID.  This function does \em not clear \c Result.
   void getAll(SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const;
 
+  /// \brief Appends the IDs of all current attachments into \c Result.
+  void getAllIDs(SmallVectorImpl<unsigned> &Result) const;
+
   /// \brief Erase matching attachments.
   ///
   /// Erases all attachments matching the \c shouldRemove predicate.
   template <class PredTy> void remove_if(PredTy shouldRemove) {
     Attachments.erase(llvm::remove_if(Attachments, shouldRemove),
                       Attachments.end());
   }
 };

llvm/lib/IR/Metadata.cpp

 }
 
 void MDAttachmentMap::erase(unsigned ID) {
   if (empty())
     return;
 
   // Common case is one/last value.
   if (Attachments.back().first == ID) {
     Attachments.pop_back();
     return;
   }
 
   for (auto I = Attachments.begin(), E = std::prev(Attachments.end()); I != E;
        ++I)
     if (I->first == ID) {
       *I = std::move(Attachments.back());
       Attachments.pop_back();
       return;
     }
 }

     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
   Result.append(Attachments.begin(), Attachments.end());
 
   // Sort the resulting array so it is stable.
   if (Result.size() > 1)
     array_pod_sort(Result.begin(), Result.end());
 }
 
+void MDAttachmentMap::getAllIDs(SmallVectorImpl<unsigned> &Result) const {
+  for (auto &A : Attachments)
+    Result.push_back(A.first);
+}
+
 void MDGlobalAttachmentMap::insert(unsigned ID, MDNode &MD) {
   Attachments.push_back({ID, TrackingMDNodeRef(&MD)});
 }
 
 void MDGlobalAttachmentMap::get(unsigned ID,
                                 SmallVectorImpl<MDNode *> &Result) {
   for (auto A : Attachments)
     if (A.MDKind == ID)

   assert(hasMetadataHashEntry() &&
          getContext().pImpl->InstructionMetadata.count(this) &&
          "Shouldn't have called this");
   const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second;
   assert(!Info.empty() && "Shouldn't have called this");
   Info.getAll(Result);
 }
 
+void
+Instruction::getAllNonDebugMetadataIDs(SmallVectorImpl<unsigned> &MDIDs) const {
+  if (!hasMetadataOtherThanDebugLoc())
+    return;
+  const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second;
+  assert(!Info.empty() && "Shouldn't have called this");
+  Info.getAllIDs(MDIDs);
+}
+
 bool Instruction::extractProfMetadata(uint64_t &TrueVal,
                                       uint64_t &FalseVal) const {
   assert(
       (getOpcode() == Instruction::Br || getOpcode() == Instruction::Select) &&
       "Looking for branch weights on something besides branch or select");
 
   auto *ProfileData = getMetadata(LLVMContext::MD_prof);
   if (!ProfileData || ProfileData->getNumOperands() != 3)

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

   MPM.add(createSpeculativeExecutionIfHasBranchDivergencePass());
   MPM.add(createJumpThreadingPass());         // Thread jumps.
   MPM.add(createCorrelatedValuePropagationPass()); // Propagate conditionals
   MPM.add(createCFGSimplificationPass());     // Merge & remove BBs
   // Combine silly seq's
   addInstructionCombiningPass(MPM);
   if (SizeLevel == 0 && !DisableLibCallsShrinkWrap)
     MPM.add(createLibCallsShrinkWrapPass());
   addExtensionsToPM(EP_Peephole, MPM);
 
   MPM.add(createTailCallEliminationPass()); // Eliminate tail calls
   MPM.add(createCFGSimplificationPass());     // Merge & remove BBs
   MPM.add(createReassociatePass());           // Reassociate expressions
-  // Rotate Loop - disable header duplication at -Oz
-  MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1));
+
+  // Rotate Loop - disable loop rotation at -Oz
+  if (SizeLevel != 2)
+    MPM.add(createLoopRotatePass());
   MPM.add(createLICMPass());                  // Hoist loop invariants
   MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3));
   MPM.add(createCFGSimplificationPass());
   addInstructionCombiningPass(MPM);
   MPM.add(createIndVarSimplifyPass());        // Canonicalize indvars
   MPM.add(createLoopIdiomPass());             // Recognize idioms like memset.
   addExtensionsToPM(EP_LateLoopOptimizations, MPM);
   MPM.add(createLoopDeletionPass());          // Delete dead loops

 
   MPM.add(createFloat2IntPass());
 
   addExtensionsToPM(EP_VectorizerStart, MPM);
 
   // Re-rotate loops in all our loop nests. These may have fallout out of
   // rotated form due to GVN or other transformations, and the vectorizer relies
   // on the rotated form. Disable header duplication at -Oz.
-  MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1));
+  if (SizeLevel != 2)
+    MPM.add(createLoopRotatePass());
 
   // Distribute loops to allow partial vectorization.  I.e. isolate dependences
   // into separate loop that would otherwise inhibit vectorization.  This is
   // currently only performed for loops marked with the metadata
   // llvm.loop.distribute=true or when -enable-loop-distribute is specified.
   MPM.add(createLoopDistributePass());
 
   MPM.add(createLoopVectorizePass(DisableUnrollLoops, LoopVectorize));

llvm/lib/Transforms/Scalar/LoopRotation.cpp

 //===- LoopRotation.cpp - Loop Rotation Pass ------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements Loop Rotation Pass.
+// All the basic blocks which are between the loop-header and the basic blocks
+// exiting the loop are 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 will be available outside of the loop (due to loop rotation).
 //
+// Only the loops satisfying following properties are rotated:
+// - The loop is an SEME (Single Entry Multiple Exit) region.
+// - The loop has a header and its terminator conditionally exits the loop.
+// - The loop has a latch and its terminator does not exit the loop.
+// - The loop has preheader.
+//
+// Post conditions:
+// The dominator tree is updated during loop rotation.
+// A loop already in loop-simplified form remains in loop-simplified form.
+// LoopInfo is preserved.
+// The rotated loop and the cloned region are SEME regions.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/LoopRotation.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/Verifier.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
+
+#include<tuple>
+
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-rotate"
 
-static cl::opt<unsigned> DefaultRotationThreshold(
-    "rotation-max-header-size", cl::init(16), cl::Hidden,
-    cl::desc("The default maximum header size for automatic loop rotation"));
+static cl::opt<unsigned> RotationMaxSize(
+    "rotation-max-size", cl::init(100), cl::Hidden,
+    cl::desc("The default maximum loop size for automatic loop rotation"));
+
+static cl::opt<unsigned> MaxExits("lr-max-exits", cl::init(10), cl::Hidden,
+                                  cl::desc("The maximum exits to be cloned"));
 
 STATISTIC(NumRotated, "Number of loops rotated");
 
-namespace {
+// Insert \p NewBB in between \p PredBefore and \p Succ, and redirect edges
+// accordingly. PredBefore -> NewBB -> Succ. Also move NewBB before Succ.
+static void insertBetween(BasicBlock *NewBB, BasicBlock *PredBefore,
+                          BasicBlock *Succ) {
+  BranchInst *NewBI = BranchInst::Create(Succ, NewBB);
+  NewBI->setDebugLoc(PredBefore->getTerminator()->getDebugLoc());
+
+  BranchInst *BLI = dyn_cast<BranchInst>(PredBefore->getTerminator());
+  for (unsigned I = 0, E = BLI->getNumSuccessors(); I < E; ++I)
+    if (BLI->getSuccessor(I) == Succ) {
+      BLI->setSuccessor(I, NewBB);
+      break;
+    }
+  // Move NewBB physically from the end of the block list.
+  Function *F = Succ->getParent();
+  F->getBasicBlockList().splice(Succ->getIterator(), F->getBasicBlockList(),
+                                NewBB);
+}
+
+// Remove the arguments of all phi nodes in PhiBB coming from block From.
+static void discardIncomingValues(BasicBlock *PhiBB, BasicBlock *From) {
+  for (Instruction &I : *PhiBB) {
+    PHINode *PN = dyn_cast<PHINode>(&I);
+    if (!PN)
+      break;
+    PN->removeIncomingValue(PN->getBasicBlockIndex(From));
+  }
+}
+
+/// Returns true of the region formed by [Entry, Exit] is a
+/// single-entry-multiple-exit (SEME) region. All the traces from \p Entry
+/// which leads to the \p Exit are analyzed.
+static bool isSingleEntryMultipleExit(const BasicBlock *Entry,
+                                      const BasicBlock *Exit,
+                                      DominatorTree *DT) {
+  if (!DT->dominates(Entry, Exit))
+    return false;
+
+  for (auto I = idf_begin(Exit), E = idf_end(Exit); I != E;) {
+    if (*I == Entry) {
+      I.skipChildren();
+      continue;
+    }
+
+    if (!DT->dominates(Entry, *I))
+      return false;
+
+    ++I;
+  }
+  return true;
+}
+
 /// A simple loop rotation transformation.
 class LoopRotate {
-  const unsigned MaxHeaderSize;
   LoopInfo *LI;
   const TargetTransformInfo *TTI;
   AssumptionCache *AC;
   DominatorTree *DT;
   ScalarEvolution *SE;
+  Loop *L;
+  typedef SmallVectorImpl<BasicBlock *> SmallVecBB;
+  typedef SmallPtrSetImpl<BasicBlock *> SmallPtrSetBB;
 
 public:
-  LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI,
-             const TargetTransformInfo *TTI, AssumptionCache *AC,
-             DominatorTree *DT, ScalarEvolution *SE)
-      : MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE) {
-  }
-  bool processLoop(Loop *L);
+  LoopRotate(LoopInfo *LI, const TargetTransformInfo *TTI, AssumptionCache *AC,
+             DominatorTree *DT, ScalarEvolution *SE, Loop *L)
+      : LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE), L(L) {}
+  bool processLoop();
 
 private:
-  bool rotateLoop(Loop *L, bool SimplifiedLatch);
-  bool simplifyLoopLatch(Loop *L);
-};
-} // end anonymous namespace
+  void rotateLoop(BasicBlock *NewH, const SmallVecBB &Blocks,
+                  const SmallPtrSetBB &Exits) const;
 
-/// RewriteUsesOfClonedInstructions - We just cloned the instructions from the
-/// old header into the preheader.  If there were uses of the values produced by
-/// these instruction that were outside of the loop, we have to insert PHI nodes
-/// to merge the two values.  Do this now.
-static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader,
-                                            BasicBlock *OrigPreheader,
-                                            ValueToValueMapTy &ValueMap) {
-  // Remove PHI node entries that are no longer live.
-  BasicBlock::iterator I, E = OrigHeader->end();
-  for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I)
-    PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader));
-
-  // Now fix up users of the instructions in OrigHeader, inserting PHI nodes
-  // as necessary.
-  SSAUpdater SSA;
-  for (I = OrigHeader->begin(); I != E; ++I) {
-    Value *OrigHeaderVal = &*I;
-
-    // If there are no uses of the value (e.g. because it returns void), there
-    // is nothing to rewrite.
-    if (OrigHeaderVal->use_empty())
-      continue;
-
-    Value *OrigPreHeaderVal = ValueMap.lookup(OrigHeaderVal);
-
-    // The value now exits in two versions: the initial value in the preheader
-    // and the loop "next" value in the original header.
-    SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName());
-    SSA.AddAvailableValue(OrigHeader, OrigHeaderVal);
-    SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal);
-
-    // Visit each use of the OrigHeader instruction.
-    for (Value::use_iterator UI = OrigHeaderVal->use_begin(),
-                             UE = OrigHeaderVal->use_end();
-         UI != UE;) {
-      // Grab the use before incrementing the iterator.
-      Use &U = *UI;
-
-      // Increment the iterator before removing the use from the list.
-      ++UI;
+  bool preserveLoopSimplifyForm(const SmallPtrSetBB &Exits) const;
 
-      // SSAUpdater can't handle a non-PHI use in the same block as an
-      // earlier def. We can easily handle those cases manually.
-      Instruction *UserInst = cast<Instruction>(U.getUser());
-      if (!isa<PHINode>(UserInst)) {
-        BasicBlock *UserBB = UserInst->getParent();
-
-        // The original users in the OrigHeader are already using the
-        // original definitions.
-        if (UserBB == OrigHeader)
-          continue;
+  bool isLoopSizeWithinLimits(const SmallVecBB &Blocks,
+                              const SmallPtrSetBB &Exits) const;
 
-        // Users in the OrigPreHeader need to use the value to which the
-        // original definitions are mapped.
-        if (UserBB == OrigPreheader) {
-          U = OrigPreHeaderVal;
-          continue;
-        }
-      }
+  bool isLegalToRotate() const;
 
-      // Anything else can be handled by SSAUpdater.
-      SSA.RewriteUse(U);
-    }
+  void adjustNewHeaderPhis(ValueToValueMapTy &VMap, BasicBlock *NewH,
+                           BasicBlock *NewPH) const;
 
-    // Replace MetadataAsValue(ValueAsMetadata(OrigHeaderVal)) uses in debug
-    // intrinsics.
-    LLVMContext &C = OrigHeader->getContext();
-    if (auto *VAM = ValueAsMetadata::getIfExists(OrigHeaderVal)) {
-      if (auto *MAV = MetadataAsValue::getIfExists(C, VAM)) {
-        for (auto UI = MAV->use_begin(), E = MAV->use_end(); UI != E;) {
-          // Grab the use before incrementing the iterator. Otherwise, altering
-          // the Use will invalidate the iterator.
-          Use &U = *UI++;
-          DbgInfoIntrinsic *UserInst = dyn_cast<DbgInfoIntrinsic>(U.getUser());
-          if (!UserInst)
-            continue;
+  BasicBlock *collectSEMEBlocks(BasicBlock *OrigH, BasicBlock *OrigLatch,
+                                SmallVecBB &Blocks, SmallPtrSetBB &Exits) const;
 
-          // The original users in the OrigHeader are already using the original
-          // definitions.
-          BasicBlock *UserBB = UserInst->getParent();
-          if (UserBB == OrigHeader)
-            continue;
+  PHINode *getOrCreatePHI(Instruction *Inst, BasicBlock *NewHeader,
+                          BasicBlock *NewPreheader, BasicBlock *NewLatch,
+                          ValueToValueMapTy &VMap) const;
 
-          // Users in the OrigPreHeader need to use the value to which the
-          // original definitions are mapped and anything else can be handled by
-          // the SSAUpdater. To avoid adding PHINodes, check if the value is
-          // available in UserBB, if not substitute undef.
-          Value *NewVal;
-          if (UserBB == OrigPreheader)
-            NewVal = OrigPreHeaderVal;
-          else if (SSA.HasValueForBlock(UserBB))
-            NewVal = SSA.GetValueInMiddleOfBlock(UserBB);
-          else
-            NewVal = UndefValue::get(OrigHeaderVal->getType());
-          U = MetadataAsValue::get(C, ValueAsMetadata::get(NewVal));
-        }
-      }
-    }
-  }
-}
+  void addNewPhisToNewHeader(const SmallVecBB &Blocks, BasicBlock *NewHeader,
+                             BasicBlock *NewPreheader, BasicBlock *NewLatch,
+                             ValueToValueMapTy &VMap) const;
+};
 
-/// Rotate loop LP. Return true if the loop is rotated.
-///
-/// \param SimplifiedLatch is true if the latch was just folded into the final
-/// loop exit. In this case we may want to rotate even though the new latch is
-/// now an exiting branch. This rotation would have happened had the latch not
-/// been simplified. However, if SimplifiedLatch is false, then we avoid
-/// rotating loops in which the latch exits to avoid excessive or endless
-/// rotation. LoopRotate should be repeatable and converge to a canonical
-/// form. This property is satisfied because simplifying the loop latch can only
-/// happen once across multiple invocations of the LoopRotate pass.
-bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
+// Check if there is something preventing loop from being rotated.
+bool LoopRotate::isLegalToRotate() const {
   // If the loop has only one block then there is not much to rotate.
   if (L->getBlocks().size() == 1)
     return false;
 
-  BasicBlock *OrigHeader = L->getHeader();
-  BasicBlock *OrigLatch = L->getLoopLatch();
+  const BasicBlock *LoopLatch = L->getLoopLatch();
+  if (!LoopLatch || isa<IndirectBrInst>(LoopLatch->getTerminator()))
+    return false;
+
+  const BasicBlock *OrigH = L->getHeader();
+  // The header should have a conditional branch to within the loop for rotation
+  // to happen. In cases where the header does not conditionally branch to
+  // within the loop e.g., header with an invoke instruction rotation will fail.
+  const BranchInst *BI = dyn_cast<const BranchInst>(OrigH->getTerminator());
+  if (!BI || !BI->isConditional())
+    return false;
 
-  BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator());
-  if (!BI || BI->isUnconditional())
+  // If the loop latch is exiting then, probably, this loop is already rotated.
+  if (L->isLoopExiting(LoopLatch))
     return false;
 
-  // If the loop header is not one of the loop exiting blocks then
-  // either this loop is already rotated or it is not
-  // suitable for loop rotation transformations.
-  if (!L->isLoopExiting(OrigHeader))
+  // If the loop header is not one of the loop exiting blocks then it might
+  // have been rotated already.
+  if (!L->isLoopExiting(OrigH))
     return false;
 
-  // If the loop latch already contains a branch that leaves the loop then the
-  // loop is already rotated.
-  if (!OrigLatch)
+  // If the loop could not be converted to canonical form, it must have an
+  // indirectbr in it, just give up.
+  if (!L->getLoopPreheader())
     return false;
 
-  // Rotate if either the loop latch does *not* exit the loop, or if the loop
-  // latch was just simplified.
-  if (L->isLoopExiting(OrigLatch) && !SimplifiedLatch)
+  if (!isSingleEntryMultipleExit(OrigH, LoopLatch, DT))
     return false;
 
+  return true;
+}
+
+// Check if the size of rotated loop will be within limits.
+bool LoopRotate::isLoopSizeWithinLimits(const SmallVecBB &Blocks,
+                                        const SmallPtrSetBB &Exits) const {
   // Check size of original header and reject loop if it is very big or we can't
   // duplicate blocks inside it.
-  {
-    SmallPtrSet<const Value *, 32> EphValues;
-    CodeMetrics::collectEphemeralValues(L, AC, EphValues);
-
+  if (Exits.size() > MaxExits)
+    return false;
+  unsigned LoopSize = 0;
+  for (const BasicBlock *BB : Blocks) {
     CodeMetrics Metrics;
-    Metrics.analyzeBasicBlock(OrigHeader, *TTI, EphValues);
+    Metrics.analyzeBasicBlock(BB, *TTI, EphValues);
+    // TODO: Modify this because there might be blocks with indirectbr, invoke
+    // in the loop but we can cut the cloning part at that point and that will
+    // be the last exit BB.
     if (Metrics.notDuplicatable) {
       DEBUG(dbgs() << "LoopRotation: NOT rotating - contains non-duplicatable"
                    << " instructions: ";
             L->dump());
       return false;
     }
+
     if (Metrics.convergent) {
       DEBUG(dbgs() << "LoopRotation: NOT rotating - contains convergent "
                       "instructions: ";
             L->dump());
       return false;
     }
-    if (Metrics.NumInsts > MaxHeaderSize)
+
+    LoopSize += Metrics.NumInsts;
+    // TODO: 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.
+    if (LoopSize >= RotationMaxSize)
       return false;
   }
+  return true;
+}
 
-  // Now, this loop is suitable for rotation.
-  BasicBlock *OrigPreheader = L->getLoopPreheader();
-
-  // If the loop could not be converted to canonical form, it must have an
-  // indirectbr in it, just give up.
-  if (!OrigPreheader)
-    return false;
+// Return a PHI for incoming values from NewPreHeader and NewLatch. If such a
+// PHI already exsits then return that otherwise create one. NewHeader has two
+// predecessors NewPreHeader and NewLatch. Inst is the original instruction
+// for which the PHI is to be created, its value is coming from NewLatch
+// and its cloned value VMap[Inst] is coming from NewPreheader.
+PHINode *LoopRotate::getOrCreatePHI(Instruction *Inst, BasicBlock *NewHeader,
+                                    BasicBlock *NewPreheader,
+                                    BasicBlock *NewLatch,
+                                    ValueToValueMapTy &VMap) const {
+    // Look within existing PHIs having same incoming values.
+    for (Instruction &I: *NewHeader) {
+        PHINode *PN = dyn_cast<PHINode>(&I);
+        if (!PN)
+          break;
+        assert(PN->getNumOperands() == 2);
+        int NLVal = PN->getBasicBlockIndex(NewLatch);
+        assert(NLVal >= 0);
+        int NPHVal = PN->getBasicBlockIndex(NewPreheader);
+        assert(NPHVal >= 0);
+        if (PN->getIncomingValue(NLVal) == Inst &&
+            PN->getIncomingValue(NPHVal) == VMap[Inst])
+          return PN;
+    }
+
+    PHINode *PN = PHINode::Create(Inst->getType(), 2, "phi.nh",
+                                  &*NewHeader->begin());
+    PN->addIncoming(Inst, NewLatch);
+    PN->addIncoming(cast<Instruction>(VMap[Inst]), NewPreheader);
+
+    return PN;
+}
+
+// Add phis to the new header and adjust the phi nodes from the OrigHeader.
+void LoopRotate::addNewPhisToNewHeader(const SmallVecBB &Blocks,
+                                       BasicBlock *NewHeader,
+                                       BasicBlock *NewPreheader,
+                                       BasicBlock *NewLatch,
+                                       ValueToValueMapTy &VMap) const {
+  // Add to NewHeader, phi nodes for all copied variables which are used.
+  for (BasicBlock *BB : Blocks) {
+    for (Instruction &Inst : *BB) {
+      // Skip Inst with no use e.g., branches.
+      if (Inst.use_begin() == Inst.use_end())
+        continue;
 
-  // Anything ScalarEvolution may know about this loop or the PHI nodes
-  // in its header will soon be invalidated.
-  if (SE)
-    SE->forgetLoop(L);
+      for (auto UI = Inst.use_begin(), E = Inst.use_end(); UI != E;) {
+        Use &U = *UI++;
+        Instruction *UserInst = cast<Instruction>(U.getUser());
 
-  DEBUG(dbgs() << "LoopRotation: rotating "; L->dump());
+        // Nothing to rename when the use is dominated by the definition.
+        if (DT->dominates(&Inst, UserInst))
+          continue;
 
-  // Find new Loop header. NewHeader is a Header's one and only successor
-  // that is inside loop.  Header's other successor is outside the
-  // loop.  Otherwise loop is not suitable for rotation.
-  BasicBlock *Exit = BI->getSuccessor(0);
-  BasicBlock *NewHeader = BI->getSuccessor(1);
-  if (L->contains(Exit))
-    std::swap(Exit, NewHeader);
-  assert(NewHeader && "Unable to determine new loop header");
-  assert(L->contains(NewHeader) && !L->contains(Exit) &&
-         "Unable to determine loop header and exit blocks");
-
-  // This code assumes that the new header has exactly one predecessor.
-  // Remove any single-entry PHI nodes in it.
-  assert(NewHeader->getSinglePredecessor() &&
-         "New header doesn't have one pred!");
-  FoldSingleEntryPHINodes(NewHeader);
-
-  // Begin by walking OrigHeader and populating ValueMap with an entry for
-  // each Instruction.
-  BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end();
-  ValueToValueMapTy ValueMap;
-
-  // For PHI nodes, the value available in OldPreHeader is just the
-  // incoming value from OldPreHeader.
-  for (; PHINode *PN = dyn_cast<PHINode>(I); ++I)
-    ValueMap[PN] = PN->getIncomingValueForBlock(OrigPreheader);
-
-  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
-
-  // For the rest of the instructions, either hoist to the OrigPreheader if
-  // possible or create a clone in the OldPreHeader if not.
-  TerminatorInst *LoopEntryBranch = OrigPreheader->getTerminator();
-  while (I != E) {
-    Instruction *Inst = &*I++;
-
-    // If the instruction's operands are invariant and it doesn't read or write
-    // memory, then it is safe to hoist.  Doing this doesn't change the order of
-    // execution in the preheader, but does prevent the instruction from
-    // executing in each iteration of the loop.  This means it is safe to hoist
-    // something that might trap, but isn't safe to hoist something that reads
-    // memory (without proving that the loop doesn't write).
-    if (L->hasLoopInvariantOperands(Inst) && !Inst->mayReadFromMemory() &&
-        !Inst->mayWriteToMemory() && !isa<TerminatorInst>(Inst) &&
-        !isa<DbgInfoIntrinsic>(Inst) && !isa<AllocaInst>(Inst)) {
-      Inst->moveBefore(LoopEntryBranch);
+        if (!L->contains(UserInst->getParent())) {
+          // Handle uses in the loop-closed-phi.
+          PHINode *ClosePhi = cast<PHINode>(UserInst);
+          BasicBlock *Pred = ClosePhi->getIncomingBlock(U.getOperandNo());
+
+          // Do not rename a loop close phi node if its predecessor in the loop
+          // is dominated by Inst.
+          if (L->contains(Pred) && DT->dominates(BB, Pred))
             continue;
         }
 
-    // Otherwise, create a duplicate of the instruction.
-    Instruction *C = Inst->clone();
+        PHINode* PN = getOrCreatePHI(&Inst, NewHeader, NewPreheader, NewLatch, VMap);
 
-    // Eagerly remap the operands of the instruction.
-    RemapInstruction(C, ValueMap,
-                     RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
-
-    // With the operands remapped, see if the instruction constant folds or is
-    // otherwise simplifyable.  This commonly occurs because the entry from PHI
-    // nodes allows icmps and other instructions to fold.
-    // FIXME: Provide TLI, DT, AC to SimplifyInstruction.
-    Value *V = SimplifyInstruction(C, DL);
-    if (V && LI->replacementPreservesLCSSAForm(C, V)) {
-      // If so, then delete the temporary instruction and stick the folded value
-      // in the map.
-      ValueMap[Inst] = V;
-      if (!C->mayHaveSideEffects()) {
-        delete C;
-        C = nullptr;
+        // When Inst does not dominate U, it is going to use the updated
+        // definition coming from PN.
+        U.set(PN);
       }
-    } else {
-      ValueMap[Inst] = C;
     }
-    if (C) {
-      // Otherwise, stick the new instruction into the new block!
-      C->setName(Inst->getName());
-      C->insertBefore(LoopEntryBranch);
-
-      if (auto *II = dyn_cast<IntrinsicInst>(C))
-        if (II->getIntrinsicID() == Intrinsic::assume)
-          AC->registerAssumption(II);
-    }
-  }
-
-  // Along with all the other instructions, we just cloned OrigHeader's
-  // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's
-  // successors by duplicating their incoming values for OrigHeader.
-  TerminatorInst *TI = OrigHeader->getTerminator();
-  for (BasicBlock *SuccBB : TI->successors())
-    for (BasicBlock::iterator BI = SuccBB->begin();
-         PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
-      PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreheader);
-
-  // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove
-  // OrigPreHeader's old terminator (the original branch into the loop), and
-  // remove the corresponding incoming values from the PHI nodes in OrigHeader.
-  LoopEntryBranch->eraseFromParent();
-
-  // If there were any uses of instructions in the duplicated block outside the
-  // loop, update them, inserting PHI nodes as required
-  RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap);
-
-  // NewHeader is now the header of the loop.
-  L->moveToHeader(NewHeader);
-  assert(L->getHeader() == NewHeader && "Latch block is our new header");
-
-  // At this point, we've finished our major CFG changes.  As part of cloning
-  // the loop into the preheader we've simplified instructions and the
-  // duplicated conditional branch may now be branching on a constant.  If it is
-  // branching on a constant and if that constant means that we enter the loop,
-  // then we fold away the cond branch to an uncond branch.  This simplifies the
-  // loop in cases important for nested loops, and it also means we don't have
-  // to split as many edges.
-  BranchInst *PHBI = cast<BranchInst>(OrigPreheader->getTerminator());
-  assert(PHBI->isConditional() && "Should be clone of BI condbr!");
-  if (!isa<ConstantInt>(PHBI->getCondition()) ||
-      PHBI->getSuccessor(cast<ConstantInt>(PHBI->getCondition())->isZero()) !=
-          NewHeader) {
-    // The conditional branch can't be folded, handle the general case.
-    // Update DominatorTree to reflect the CFG change we just made.  Then split
-    // edges as necessary to preserve LoopSimplify form.
-    if (DT) {
-      // Everything that was dominated by the old loop header is now dominated
-      // by the original loop preheader. Conceptually the header was merged
-      // into the preheader, even though we reuse the actual block as a new
-      // loop latch.
-      DomTreeNode *OrigHeaderNode = DT->getNode(OrigHeader);
-      SmallVector<DomTreeNode *, 8> HeaderChildren(OrigHeaderNode->begin(),
-                                                   OrigHeaderNode->end());
-      DomTreeNode *OrigPreheaderNode = DT->getNode(OrigPreheader);
-      for (unsigned I = 0, E = HeaderChildren.size(); I != E; ++I)
-        DT->changeImmediateDominator(HeaderChildren[I], OrigPreheaderNode);
-
-      assert(DT->getNode(Exit)->getIDom() == OrigPreheaderNode);
-      assert(DT->getNode(NewHeader)->getIDom() == OrigPreheaderNode);
-
-      // Update OrigHeader to be dominated by the new header block.
-      DT->changeImmediateDominator(OrigHeader, OrigLatch);
-    }
-
-    // Right now OrigPreHeader has two successors, NewHeader and ExitBlock, and
-    // thus is not a preheader anymore.
-    // Split the edge to form a real preheader.
-    BasicBlock *NewPH = SplitCriticalEdge(
-        OrigPreheader, NewHeader,
-        CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA());
-    NewPH->setName(NewHeader->getName() + ".lr.ph");
-
-    // Preserve canonical loop form, which means that 'Exit' should have only
-    // one predecessor. Note that Exit could be an exit block for multiple
-    // nested loops, causing both of the edges to now be critical and need to
-    // be split.
-    SmallVector<BasicBlock *, 4> ExitPreds(pred_begin(Exit), pred_end(Exit));
-    bool SplitLatchEdge = false;
-    for (BasicBlock *ExitPred : ExitPreds) {
-      // We only need to split loop exit edges.
-      Loop *PredLoop = LI->getLoopFor(ExitPred);
-      if (!PredLoop || PredLoop->contains(Exit))
-        continue;
-      if (isa<IndirectBrInst>(ExitPred->getTerminator()))
-        continue;
-      SplitLatchEdge |= L->getLoopLatch() == ExitPred;
-      BasicBlock *ExitSplit = SplitCriticalEdge(
-          ExitPred, Exit,
-          CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA());
-      ExitSplit->moveBefore(Exit);
-    }
-    assert(SplitLatchEdge &&
-           "Despite splitting all preds, failed to split latch exit?");
-  } else {
-    // We can fold the conditional branch in the preheader, this makes things
-    // simpler. The first step is to remove the extra edge to the Exit block.
-    Exit->removePredecessor(OrigPreheader, true /*preserve LCSSA*/);
-    BranchInst *NewBI = BranchInst::Create(NewHeader, PHBI);
-    NewBI->setDebugLoc(PHBI->getDebugLoc());
-    PHBI->eraseFromParent();
-
-    // With our CFG finalized, update DomTree if it is available.
-    if (DT) {
-      // Update OrigHeader to be dominated by the new header block.
-      DT->changeImmediateDominator(NewHeader, OrigPreheader);
-      DT->changeImmediateDominator(OrigHeader, OrigLatch);
-
-      // Brute force incremental dominator tree update. Call
-      // findNearestCommonDominator on all CFG predecessors of each child of the
-      // original header.
-      DomTreeNode *OrigHeaderNode = DT->getNode(OrigHeader);
-      SmallVector<DomTreeNode *, 8> HeaderChildren(OrigHeaderNode->begin(),
-                                                   OrigHeaderNode->end());
-      bool Changed;
-      do {
-        Changed = false;
-        for (unsigned I = 0, E = HeaderChildren.size(); I != E; ++I) {
-          DomTreeNode *Node = HeaderChildren[I];
-          BasicBlock *BB = Node->getBlock();
-
-          pred_iterator PI = pred_begin(BB);
-          BasicBlock *NearestDom = *PI;
-          for (pred_iterator PE = pred_end(BB); PI != PE; ++PI)
-            NearestDom = DT->findNearestCommonDominator(NearestDom, *PI);
-
-          // Remember if this changes the DomTree.
-          if (Node->getIDom()->getBlock() != NearestDom) {
-            DT->changeImmediateDominator(BB, NearestDom);
-            Changed = true;
-          }
-        }
 
-        // If the dominator changed, this may have an effect on other
-        // predecessors, continue until we reach a fixpoint.
-      } while (Changed);
-    }
-  }
+// Add incoming values to the (already present) PHIs of NewH.
+void LoopRotate::adjustNewHeaderPhis(ValueToValueMapTy &VMap, BasicBlock *NewH,
+                                     BasicBlock *NewPH) const {
+  for (Instruction &Inst : *NewH) {
+    PHINode *PN = dyn_cast<PHINode>(&Inst);
+    if (!PN)
+      break;
+    assert((PN->getNumOperands() == 1) && "NewH had multiple predecessors.");
+    Value *Op = PN->getIncomingValue(0);
+    if (Value *RenamedVal = VMap[Op])
+      PN->addIncoming(RenamedVal, NewPH);
+    else // When no mapping is available (e.g., in case of a constant).
+      PN->addIncoming(Op, NewPH);
 
-  assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation");
-  assert(L->getLoopLatch() && "Invalid loop latch after loop rotation");
-
-  // Now that the CFG and DomTree are in a consistent state again, try to merge
-  // the OrigHeader block into OrigLatch.  This will succeed if they are
-  // connected by an unconditional branch.  This is just a cleanup so the
-  // emitted code isn't too gross in this common case.
-  MergeBlockIntoPredecessor(OrigHeader, DT, LI);
-
-  DEBUG(dbgs() << "LoopRotation: into "; L->dump());
-
-  ++NumRotated;
-  return true;
+// OrigH and OrigLatch represent an SEME region.  Collect all BasicBlocks
+// (bounded by \p OrigH and \p OrigLatch), which are exiting the loop in
+// \p Blocks and collect all the exits from the region in \p Exits. Returns the
+// first basic block which will not be cloned.
+BasicBlock *LoopRotate::collectSEMEBlocks(BasicBlock *OrigH,
+                                          BasicBlock *OrigLatch,
+                                          SmallVecBB &Blocks,
+                                          SmallPtrSetBB &Exits) const {
+  BasicBlock *NewH = nullptr;
+  for (auto BB = df_begin(OrigH), E = df_end(OrigH); BB != E;) {
+    if (!L->contains(*BB)) {
+      BB.skipChildren();
+      continue;
     }
 
-/// Determine whether the instructions in this range may be safely and cheaply
-/// speculated. This is not an important enough situation to develop complex
-/// heuristics. We handle a single arithmetic instruction along with any type
-/// conversions.
-static bool shouldSpeculateInstrs(BasicBlock::iterator Begin,
-                                  BasicBlock::iterator End, Loop *L) {
-  bool seenIncrement = false;
-  bool MultiExitLoop = false;
-
-  if (!L->getExitingBlock())
-    MultiExitLoop = true;
+    // Copy until any BB where the branch does not exit loop, or the loop-latch.
+    if (OrigLatch == *BB || !L->isLoopExiting(*BB) ||
+        !isa<BranchInst>((*BB)->getTerminator())) {
+      // This will become the new header.
+      NewH = *BB;
+      BB.skipChildren();
+    } else {
+      Blocks.push_back(*BB);
 
-  for (BasicBlock::iterator I = Begin; I != End; ++I) {
+      BranchInst *BI = cast<BranchInst>((*BB)->getTerminator());
+      for (unsigned B = 0, E = BI->getNumSuccessors(); B < E; ++B) {
+        BasicBlock *Succ = BI->getSuccessor(B);
+        if (!L->contains(Succ))
+          Exits.insert(Succ);
+      }
+      ++BB;
+    }
+  }
+  return NewH;
+}
 
-    if (!isSafeToSpeculativelyExecute(&*I))
-      return false;
+// Helper function for copySEME. Adjusts the PHIs of all the \p Exits bounding
+// an SEME. \p VMap contains mapping of original BB vs copied BB.
+static void adjustExitingPhis(ValueToValueMapTy &VMap,
+                              const SmallPtrSetImpl<BasicBlock *> &Exits) {
+  for (BasicBlock *BB : Exits) {
+    for (Instruction &Inst : *BB) {
+      PHINode *PN = dyn_cast<PHINode>(&Inst);
+      if (!PN)
+        break;
+      bool EdgeFromOrigBB = false;
+      for (unsigned i = 0, e = PN->getNumOperands(); i != e; ++i) {
+        Value *CopyB = VMap[PN->getIncomingBlock(i)];
+        if (!CopyB) // Skip args coming from outside the SEME.
+          continue;
+        BasicBlock *CopyBB = cast<BasicBlock>(CopyB);
+        EdgeFromOrigBB = true;
+        Value *Op = PN->getIncomingValue(i);
+        if (Value *RenamedVal = VMap[Op])
+          PN->addIncoming(RenamedVal, CopyBB);
+        else
+          // When no mapping is available it may be a constant,
+          // a function argument, or a global, add as it is.
+          PN->addIncoming(Op, CopyBB);
+      }
+      assert(EdgeFromOrigBB && "Illegal exit from SEME.");
+    }
+  }
+}
 
-    if (isa<DbgInfoIntrinsic>(I))
+/// Clones the basic blocks (\p Blocks) of an SEME bounded by \p Exits.
+/// Blocks[0] is the entry basic block of the SEME.
+/// The mapping between original BBs and correponding copied BBs are
+/// populated in \p VMap. During copy the DOM and LI of CFG are updated.
+/// \returns The entry point of the copied SEME. \p NameSuffix is used to suffix
+/// name of the copied BBs. The copied SEME is also an SEME.
+static BasicBlock* copyBlocks(const SmallVectorImpl<BasicBlock *> &Blocks,
+                              const SmallPtrSetImpl<BasicBlock *> &Exits,
+                              ValueToValueMapTy &VMap,
+                              const Twine &NameSuffix,
+                              DominatorTree *DT, LoopInfo *LI) {
+  // Step1: Clone the basic blocks and populate VMap.
+  BasicBlock *OrigH = Blocks[0];
+
+  Function *F = OrigH->getParent();
+  SmallVector<BasicBlock *, 4> NewBlocks;
+  for (BasicBlock *BB : Blocks) {
+    assert(!isa<IndirectBrInst>(BB->getTerminator()) &&
+           "Cannot clone SEME with indirect branches.");
+
+    BasicBlock *NewBB = CloneBasicBlock(BB, VMap, NameSuffix, F);
+    // Move them physically from the end of the block list.
+    F->getBasicBlockList().splice(OrigH->getIterator(), F->getBasicBlockList(),
+                                  NewBB);
+    Loop *BBLoop = LI->getLoopFor(BB);
+    Loop *BBParentLoop = BBLoop->getParentLoop();
+    if (BBParentLoop)
+      BBParentLoop->addBasicBlockToLoop(NewBB, *LI);
+    VMap[BB] = NewBB;
+    NewBlocks.push_back(NewBB);
+  }
+
+  // Step2: Remap the names in copied BBs.
+  remapInstructionsInBlocks(NewBlocks, VMap);
+
+  // Step3: Redirect the edges.
+  for (BasicBlock *BB : Blocks) {
+    BasicBlock *NewBB = cast<BasicBlock>(VMap[BB]);
+    BranchInst *BI = dyn_cast<BranchInst>(NewBB->getTerminator());
+    if (!BI)
       continue;
 
-    switch (I->getOpcode()) {
-    default:
-      return false;
-    case Instruction::GetElementPtr:
-      // GEPs are cheap if all indices are constant.
-      if (!cast<GEPOperator>(I)->hasAllConstantIndices())
-        return false;
-      // fall-thru to increment case
-      LLVM_FALLTHROUGH;
-    case Instruction::Add:
-    case Instruction::Sub:
-    case Instruction::And:
-    case Instruction::Or:
-    case Instruction::Xor:
-    case Instruction::Shl:
-    case Instruction::LShr:
-    case Instruction::AShr: {
-      Value *IVOpnd =
-          !isa<Constant>(I->getOperand(0))
-              ? I->getOperand(0)
-              : !isa<Constant>(I->getOperand(1)) ? I->getOperand(1) : nullptr;
-      if (!IVOpnd)
-        return false;
-
-      // If increment operand is used outside of the loop, this speculation
-      // could cause extra live range interference.
-      if (MultiExitLoop) {
-        for (User *UseI : IVOpnd->users()) {
-          auto *UserInst = cast<Instruction>(UseI);
-          if (!L->contains(UserInst))
-            return false;
+    for (unsigned I = 0, E = BI->getNumSuccessors(); I < E; ++I)
+      if (auto *NewSucc = cast_or_null<BasicBlock>(VMap[BI->getSuccessor(I)]))
+        BI->setSuccessor(I, NewSucc);
+  }
+
+  // Step4: Update the DOM of copied SEME. Except for the entry block its tree
+  // structure is the same as of original SEME so the dominators also follow the
+  // same structural property. If the IDom of original BB is not in SEME that
+  // means it is the entry block, in that case the new IDom of the new BB must
+  // be its single predecessor because we are dealing with an SEME region.
+  BasicBlock *EntryNewSEME = nullptr;
+  if (auto *DomT = DT->getNode(Blocks[0])->getIDom()) {
+    // Entry to SEME has a dominator, update the copied entry.
+    BasicBlock *Dom = DomT->getBlock();
+    assert(!VMap[Dom]); // Dom does not belong to SEME => entry block.
+    BasicBlock *NewBB = cast<BasicBlock>(VMap[Blocks[0]]);
+    EntryNewSEME = NewBB;
+    DT->addNewBlock(NewBB, Dom);
+    DT->changeImmediateDominator(NewBB, Dom);
+  }
+
+  for (auto BBI = std::next(Blocks.begin()); BBI != Blocks.end(); ++BBI) {
+    BasicBlock *NewBB = cast<BasicBlock>(VMap[*BBI]);
+    BasicBlock *Dom = DT->getNode(*BBI)->getIDom()->getBlock();
+    BasicBlock *NewDom = cast<BasicBlock>(VMap[Dom]);
+    DT->addNewBlock(NewBB, NewDom);
+    DT->changeImmediateDominator(NewBB, NewDom);
+  }
+
+  // Step5: Adjust PHI nodes for edges exiting the SEME.
+  adjustExitingPhis(VMap, Exits);
+  return EntryNewSEME;
+}
+
+bool LoopRotate::preserveLoopSimplifyForm(const SmallPtrSetBB &Exits) const {
+    bool HasIndirectBr = false;
+    // Split the edge from exiting BB to exit BB if not in loop-simplify form.
+    // We do not guarantee loop-simplify form to be preserved if the original
+    // loop has indirect exiting branches.
+    for (BasicBlock *BB: Exits) {
+      if (!BB->getSinglePredecessor()) {
+        // Splitting edges on the fly causes predecessor list to be corrupted
+        // so collect all the predecessors of BB to be split.
+        SmallVector<BasicBlock *, 2> EdgesToBeSplit;
+        for (BasicBlock *Pred : predecessors(BB))
+          if (L->contains(Pred)) {
+            if (isa<IndirectBrInst>(Pred->getTerminator()))
+              HasIndirectBr = true;
+            else
+              EdgesToBeSplit.push_back(Pred);
           }
-      }
+        for (BasicBlock *Pred: EdgesToBeSplit)
+          SplitEdge(Pred, BB, DT, LI); // Split Pred->BB
+      }
+    }
+  return HasIndirectBr;
 
-      if (seenIncrement)
-        return false;
-      seenIncrement = true;
+/// Rotate loop L.
+/// Rotate the SEME (\p Blocks) bounded by \p Exits.
+/// Blocks[0] is the entry basic block of the SEME.
+void LoopRotate::rotateLoop(BasicBlock *NewH, const SmallVecBB &Blocks,
+                            const SmallPtrSetBB &Exits) const {
+  bool LoopSimplifyForm = false;
+  DEBUG(LoopSimplifyForm = L->isLoopSimplifyForm());
+  BasicBlock *OrigH = L->getHeader();
+  BasicBlock *OrigLatch = L->getLoopLatch();
+  BasicBlock *OrigPH = L->getLoopPreheader();
+
+  DEBUG(dbgs() << "LoopRotation: rotating "; L->dump());
+
+  /// The mapping between original BBs in Blocks and correponding copied BBs are
+  /// populated in VMap.
+  ValueToValueMapTy VMap;
+  copyBlocks(Blocks, Exits, VMap, ".lr", DT, LI);
+
+  // Redirect original preheader to the entry of copied SEME.
+  BranchInst *OrigPHBI = dyn_cast<BranchInst>(OrigPH->getTerminator());
+  assert(OrigPHBI && (1 == OrigPHBI->getNumSuccessors()) &&
+         "Preheader does not have single successor.");
+
+  BasicBlock *CopyOrigH = cast<BasicBlock>(VMap[OrigH]);
+  OrigPHBI->setSuccessor(0, CopyOrigH);
+  DT->changeImmediateDominator(CopyOrigH, OrigPH);
+  L->moveToHeader(NewH);
+
+  BasicBlock *BeforeLoop = nullptr;
+  for (BasicBlock *BB : predecessors(NewH))
+    if (!L->contains(BB)) {
+      BeforeLoop = BB;
       break;
     }
-    case Instruction::Trunc:
-    case Instruction::ZExt:
-    case Instruction::SExt:
-      // ignore type conversions
-      break;
+  assert(BeforeLoop && "No entry point to the loop from New Header.");
+
+  Function *F = BeforeLoop->getParent();
+  // Move NewH physically to the beginning of the loop.
+  F->getBasicBlockList().splice(OrigH->getIterator(), F->getBasicBlockList(),
+                                NewH);
+
+  // SplitEdge does not work properly with single-entry PHIs.
+  BasicBlock *NewPH = BasicBlock::Create(
+      NewH->getContext(), NewH->getName() + ".lr.ph", F, BeforeLoop);
+
+  Loop *OuterLoop = LI->getLoopFor(OrigPH);
+  if (OuterLoop)
+    OuterLoop->addBasicBlockToLoop(NewPH, *LI);
+
+  // BeforeLoop --> NewPH --> NewH.
+  insertBetween(NewPH, BeforeLoop, NewH);
+
+  DT->addNewBlock(NewPH, BeforeLoop);
+  DT->changeImmediateDominator(NewPH, BeforeLoop);
+  DT->changeImmediateDominator(NewH, NewPH);
+
+  // Also, the original entry lost its immediate dominator so its dominator
+  // should be adjusted. We use SEME property => idom (OrigH) = its single pred.
+  DT->changeImmediateDominator(OrigH, OrigH->getSinglePredecessor());
+
+  // Adjust the dominators of original SEME.
+  for (BasicBlock *BB : Blocks) {
+    typedef DomTreeNodeBase<BasicBlock> DTNode;
+    // Get the subtree of BB in the dominator tree.
+    DTNode *DTBB = (*DT)[BB];
+    std::vector<DTNode *>::const_iterator I = DTBB->begin();
+    while (I != DTBB->end()) {
+      BasicBlock *ExitBB = (*I)->getBlock();
+      if (L->contains(ExitBB)) {
+        ++I;
+        continue;
       }
+      BasicBlock *StaleIDom = DT->getNode(ExitBB)->getIDom()->getBlock();
+      BasicBlock *NewBB = cast<BasicBlock>(VMap[BB]);
+      // NewIDom is correct because this part of CFG is up-to-date.
+      BasicBlock *NewIDom = DT->findNearestCommonDominator(StaleIDom, NewBB);
+      NewIDom = DT->findNearestCommonDominator(NewIDom, BB);
+      if (NewIDom != StaleIDom) {
+        DT->changeImmediateDominator(ExitBB, NewIDom);
+        DEBUG(dbgs() << "\nChanging IDom of " << *ExitBB << "to" << *NewIDom);
+        I = DTBB->begin();
+      } else
+        ++I;
     }
-  return true;
   }
 
-/// Fold the loop tail into the loop exit by speculating the loop tail
-/// instructions. Typically, this is a single post-increment. In the case of a
-/// simple 2-block loop, hoisting the increment can be much better than
-/// duplicating the entire loop header. In the case of loops with early exits,
-/// rotation will not work anyway, but simplifyLoopLatch will put the loop in
-/// canonical form so downstream passes can handle it.
-///
-/// I don't believe this invalidates SCEV.
-bool LoopRotate::simplifyLoopLatch(Loop *L) {
-  BasicBlock *Latch = L->getLoopLatch();
-  if (!Latch || Latch->hasAddressTaken())
-    return false;
+  adjustNewHeaderPhis(VMap, NewH, NewPH);
+
+  BasicBlock *NewLatch = L->getLoopLatch();
+  assert(L->getLoopPreheader() && "Invalid loop preheader after rotation");
+  assert(NewLatch && "Invalid loop latch after rotation");
+
+  addNewPhisToNewHeader(Blocks, NewH, NewPH, NewLatch, VMap);
+
+  // Discard incoming values in the CopyOrigHeader, which are coming from
+  // OrigLatch since it has only one predecessor.
+  discardIncomingValues(CopyOrigH, OrigLatch);
+  discardIncomingValues(OrigH, OrigPH);
+  const bool HasIndirectBr = preserveLoopSimplifyForm(Exits);
+
+  DEBUG(DT->verifyDomTree());
+  DEBUG(LI->verify(*DT));
+
+  // If the loop was not in loop-simplify form then after the loop
+  // rotation, it is still not going to be in that form.
+  if (!HasIndirectBr && LoopSimplifyForm)
+    assert(L->isLoopSimplifyForm() && "Loop simplify form not preserved.");
+  assert(L->isRecursivelyLCSSAForm(*DT, *LI) && "Loop is not in LCSSA form.");
+
+  DEBUG(dbgs() << "\nLoopRotation: rotated "; L->dumpVerbose());
+
+  assert(isSingleEntryMultipleExit(L->getHeader(), NewLatch, DT) &&
+         "Rotated loop not an SEME");
+  assert(isSingleEntryMultipleExit(CopyOrigH, NewPH, DT) &&
+         "Copied SEME not an SEME");
 
-  BranchInst *Jmp = dyn_cast<BranchInst>(Latch->getTerminator());
-  if (!Jmp || !Jmp->isUnconditional())
-    return false;
+  ++NumRotated;
+}
 
-  BasicBlock *LastExit = Latch->getSinglePredecessor();
-  if (!LastExit || !L->isLoopExiting(LastExit))
+/// Rotate \c L, and return true if any modification was made.
+bool LoopRotate::processLoop() {
+  if (!isLegalToRotate())
     return false;
 
-  BranchInst *BI = dyn_cast<BranchInst>(LastExit->getTerminator());
-  if (!BI)
-    return false;
+  BasicBlock *OrigH = L->getHeader();
+  BasicBlock *LoopLatch = L->getLoopLatch();
 
-  if (!shouldSpeculateInstrs(Latch->begin(), Jmp->getIterator(), L))
-    return false;
+  // Basic blocks to be copied.
+  SmallVector<BasicBlock *, 4> Blocks;
+  SmallPtrSet<BasicBlock *, 4> Exits;
+  // Collect all nodes of the loop from header to latch.
+  BasicBlock *NewH = collectSEMEBlocks(OrigH, LoopLatch, Blocks, Exits);
+  assert(NewH && "Invalid SEME region.");
 
-  DEBUG(dbgs() << "Folding loop latch " << Latch->getName() << " into "
-               << LastExit->getName() << "\n");
+  if (!isLoopSizeWithinLimits(Blocks, Exits))
+    return false;
 
-  // Hoist the instructions from Latch into LastExit.
-  LastExit->getInstList().splice(BI->getIterator(), Latch->getInstList(),
-                                 Latch->begin(), Jmp->getIterator());
-
-  unsigned FallThruPath = BI->getSuccessor(0) == Latch ? 0 : 1;
-  BasicBlock *Header = Jmp->getSuccessor(0);
-  assert(Header == L->getHeader() && "expected a backward branch");
-
-  // Remove Latch from the CFG so that LastExit becomes the new Latch.
-  BI->setSuccessor(FallThruPath, Header);
-  Latch->replaceSuccessorsPhiUsesWith(LastExit);
-  Jmp->eraseFromParent();
-
-  // Nuke the Latch block.
-  assert(Latch->empty() && "unable to evacuate Latch");
-  LI->removeBlock(Latch);
-  if (DT)
-    DT->eraseNode(Latch);
-  Latch->eraseFromParent();
-  return true;
+  // Save the loop metadata.
+  MDNode *LoopMD = nullptr;
+  Instruction *TI = nullptr;
+  std::tie(LoopMD, TI) = L->getLoopIDWithInstr();
+
+  // Make sure the latch has only one successor.
+  if (!LoopLatch->getSingleSuccessor()) {
+    // Since LoopLatch was skipped while collecting SEME blocks, exits out of
+    // the loop-latch is collected here.
+    BranchInst *BLI = dyn_cast<BranchInst>(LoopLatch->getTerminator());
+    if (!BLI)
+      return false;
+    // If the NewH is the loop-latch => Exits does not include the exiting block
+    // from loop-latch (see collectSEMEBlocks).
+    if (NewH == LoopLatch)
+      for (unsigned I = 0, E = BLI->getNumSuccessors(); I < E; ++I) {
+        BasicBlock *Succ = BLI->getSuccessor(I);
+        if (Succ != OrigH && !L->contains(Succ))
+          Exits.insert(Succ);
+      }
+
+    // The old loop-latch will become the parent of new loop-latch.
+    DEBUG(dbgs() << "\nSplitting the edge of Loop:"; L->dumpVerbose(););
+    BasicBlock *NewLoopLatch = SplitEdge(LoopLatch, OrigH, DT, LI);
+
+    // If the NewH is the loop-latch => NewH would change as the loop-latch has
+    // changed after splitting. Also, we need to add the (old) loop-latch to the
+    // blocks because it was skipped (all the blocks before NewH are copied to
+    // new SEME).
+    if (NewH == LoopLatch) {
+      NewH = NewLoopLatch;
+      Blocks.push_back(LoopLatch);
+    }
+    LoopLatch = NewLoopLatch;
   }
 
-/// Rotate \c L, and return true if any modification was made.
-bool LoopRotate::processLoop(Loop *L) {
-  // Save the loop metadata.
-  MDNode *LoopMD = L->getLoopID();
+  assert(LoopLatch->getSingleSuccessor() && "Invalid SEME region.");
 
-  // Simplify the loop latch before attempting to rotate the header
-  // upward. Rotation may not be needed if the loop tail can be folded into the
-  // loop exit.
-  bool SimplifiedLatch = simplifyLoopLatch(L);
+  // Anything ScalarEvolution may know about this loop or the PHI nodes in its
+  // header will soon be invalidated.
+  if (SE)
+    SE->forgetLoop(L);
 
-  bool MadeChange = rotateLoop(L, SimplifiedLatch);
-  assert((!MadeChange || L->isLoopExiting(L->getLoopLatch())) &&
+  rotateLoop(NewH, Blocks, Exits);
+  assert(L->isLoopExiting(L->getLoopLatch()) &&
          "Loop latch should be exiting after loop-rotate.");
 
-  // Restore the loop metadata.
-  // NB! We presume LoopRotation DOESN'T ADD its own metadata.
-  if ((MadeChange || SimplifiedLatch) && LoopMD)
+  if (LoopMD) {
+    // Drop loop metadata from the old loop header.
+    SmallVector<unsigned, 2> MDs;
+    TI->getAllNonDebugMetadataIDs(MDs);
+    MDs.erase(llvm::remove_if(MDs, [](unsigned ID) {
+          return ID == LLVMContext::MD_loop; }), MDs.end());
+
+    TI->dropUnknownNonDebugMetadata(MDs);
+
+    // Restore the loop metadata to the new loop header.
     L->setLoopID(LoopMD);
+  }
 
-  return MadeChange;
+  return true;
 }
 
 LoopRotatePass::LoopRotatePass(bool EnableHeaderDuplication)
     : EnableHeaderDuplication(EnableHeaderDuplication) {}
 
 PreservedAnalyses LoopRotatePass::run(Loop &L, LoopAnalysisManager &AM,
                                       LoopStandardAnalysisResults &AR,
                                       LPMUpdater &) {
-  int Threshold = EnableHeaderDuplication ? DefaultRotationThreshold : 0;
-  LoopRotate LR(Threshold, &AR.LI, &AR.TTI, &AR.AC, &AR.DT, &AR.SE);
+  LoopRotate LR(&AR.LI, &AR.TTI, &AR.AC, &AR.DT, &AR.SE, &L);
 
-  bool Changed = LR.processLoop(&L);
+  bool Changed = LR.processLoop();
   if (!Changed)
     return PreservedAnalyses::all();
 
   return getLoopPassPreservedAnalyses();
 }
 
 namespace {
 
 class LoopRotateLegacyPass : public LoopPass {
-  unsigned MaxHeaderSize;
-
 public:
   static char ID; // Pass ID, replacement for typeid
-  LoopRotateLegacyPass(int SpecifiedMaxHeaderSize = -1) : LoopPass(ID) {
+  LoopRotateLegacyPass() : LoopPass(ID) {
     initializeLoopRotateLegacyPassPass(*PassRegistry::getPassRegistry());
-    if (SpecifiedMaxHeaderSize == -1)
-      MaxHeaderSize = DefaultRotationThreshold;
-    else
-      MaxHeaderSize = unsigned(SpecifiedMaxHeaderSize);
   }
 
   // LCSSA form makes instruction renaming easier.
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
+    AU.addRequired<DominatorTreeWrapperPass>();
     getLoopAnalysisUsage(AU);
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     if (skipLoop(L))
       return false;
     Function &F = *L->getHeader()->getParent();
 
     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     const auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
     auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
     auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
     auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
     auto *SE = SEWP ? &SEWP->getSE() : nullptr;
-    LoopRotate LR(MaxHeaderSize, LI, TTI, AC, DT, SE);
-    return LR.processLoop(L);
+    LoopRotate LR(LI, TTI, AC, DT, SE, L);
+    return LR.processLoop();
   }
 };
 }
 
 char LoopRotateLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_END(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops", false,
                     false)
 
-Pass *llvm::createLoopRotatePass(int MaxHeaderSize) {
-  return new LoopRotateLegacyPass(MaxHeaderSize);
-}
+Pass *llvm::createLoopRotatePass() { return new LoopRotateLegacyPass(); }

llvm/test/Analysis/GlobalsModRef/memset-escape.ll

 ; RUN: opt < %s -O1 -S -enable-non-lto-gmr=true | FileCheck %s
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.10.0"
 
 @a = internal global [3 x i32] zeroinitializer, align 4
 @b = common global i32 0, align 4
 
-; The important thing we're checking for here is the reload of (some element of)
-; @a after the memset.
-
-; CHECK-LABEL: @main
-; CHECK: call void @llvm.memset.p0i8.i64{{.*}} @a
-; CHECK: store i32 3
-; CHECK: load i32, i32* getelementptr {{.*}} @a
-; CHECK: icmp eq i32
-; CHECK: br i1
+; Check that load and the call to abort is redundant.
+; CHECK:   store i32 1, i32* getelementptr inbounds ([3 x i32], [3 x i32]* @a, i64 0, i64 2), align 4
+; CHECK:   store i32 0, i32* @b, align 4
+; CHECK:   br label %for.body
+
+; CHECK: for.body:                                         ; preds = %for.body.lr.ph
+; CHECK:   store i32 0, i32* getelementptr inbounds ([3 x i32], [3 x i32]* @a, i64 0, i64 0), align 4
+; CHECK:   store i32 0, i32* getelementptr inbounds ([3 x i32], [3 x i32]* @a, i64 0, i64 1), align 4
+; CHECK:   store i32 0, i32* getelementptr inbounds ([3 x i32], [3 x i32]* @a, i64 0, i64 2), align 4
+; CHECK:   store i32 3, i32* @b, align 4
+; CHECK:   br i1 true, label %if.end, label %if.then
+; CHECK-NOT: load
+; CHECK-NOT: call void @abort()
 
 define i32 @main() {
 entry:
   %retval = alloca i32, align 4
   %c = alloca [1 x i32], align 4
   store i32 0, i32* %retval, align 4
   %0 = bitcast [1 x i32]* %c to i8*
   call void @llvm.memset.p0i8.i64(i8* %0, i8 0, i64 4, i32 4, i1 false)
   store i32 1, i32* getelementptr inbounds ([3 x i32], [3 x i32]* @a, i64 0, i64 2), align 4

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

-; RUN: opt < %s -basicaa -globalopt -instcombine -loop-rotate -licm -instcombine -indvars -loop-deletion -constmerge -S | FileCheck %s
-; PR11882: ComputeLoadConstantCompareExitLimit crash.
-;
-; for.body is deleted leaving a loop-invariant load.
-; CHECK-NOT: for.body
-target datalayout = "e-p:64:64:64-n32:64"
-
-@func_21_l_773 = external global i32, align 4
-@g_814 = external global i32, align 4
-@g_244 = internal global [1 x [0 x i32]] zeroinitializer, align 4
-
-define void @func_21() nounwind uwtable ssp {
-entry:
-  br label %lbl_818
-
-lbl_818:                                          ; preds = %for.end, %entry
-  call void (...) @func_27()
-  store i32 0, i32* @g_814, align 4
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.body, %lbl_818
-  %0 = load i32, i32* @g_814, align 4
-  %cmp = icmp sle i32 %0, 0
-  br i1 %cmp, label %for.body, label %for.end
-
-for.body:                                         ; preds = %for.cond
-  %idxprom = sext i32 %0 to i64
-  %arrayidx = getelementptr inbounds [0 x i32], [0 x i32]* getelementptr inbounds ([1 x [0 x i32]], [1 x [0 x i32]]* @g_244, i32 0, i64 0), i32 0, i64 %idxprom
-  %1 = load i32, i32* %arrayidx, align 1
-  store i32 %1, i32* @func_21_l_773, align 4
-  store i32 1, i32* @g_814, align 4
-  br label %for.cond
-
-for.end:                                          ; preds = %for.cond
-  %2 = load i32, i32* @func_21_l_773, align 4
-  %tobool = icmp ne i32 %2, 0
-  br i1 %tobool, label %lbl_818, label %if.end
-
-if.end:                                           ; preds = %for.end
-  ret void
-}
-
-declare void @func_27(...)

llvm/test/Transforms/LoopRotate/basic.ll

entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.body, %entry
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %cmp = icmp slt i32 %i.0, 100
   %arrayidx = getelementptr inbounds [20 x i32], [20 x i32]* %array, i64 0, i64 0
   br i1 %cmp, label %for.body, label %for.end
 
-; CHECK: for.body:
+; CHECK: for.cond.lr:
 ; CHECK-NEXT: phi i32 [ 0
-; CHECK-NEXT: store i32 0
+; CHECK: for.body:
+; CHECK: store i32 0
 
 for.body:                                         ; preds = %for.cond
   store i32 0, i32* %arrayidx, align 16
   %inc = add nsw i32 %i.0, 1
   br label %for.cond
 
 for.end:                                          ; preds = %for.cond
   %arrayidx.lcssa = phi i32* [ %arrayidx, %for.cond ]

llvm/test/Transforms/LoopRotate/dbgvalue.ll

 ; RUN: opt -S -loop-rotate < %s | FileCheck %s
 
 declare void @llvm.dbg.declare(metadata, metadata, metadata) nounwind readnone
 declare void @llvm.dbg.value(metadata, i64, metadata, metadata) nounwind readnone
 
 define i32 @tak(i32 %x, i32 %y, i32 %z) nounwind ssp !dbg !0 {
 ; CHECK-LABEL: define i32 @tak(
-; CHECK: entry
-; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 %x
-; CHECK: tail call void @llvm.dbg.value(metadata i32 %call
+; CHECK: tailrecurse.lr
+; CHECK: call void @llvm.dbg.value(metadata i32 %x
+; CHECK: tail call void @llvm.dbg.value(metadata i32 %y
 
 entry:
   br label %tailrecurse
 
 tailrecurse:                                      ; preds = %if.then, %entry
   %x.tr = phi i32 [ %x, %entry ], [ %call, %if.then ]
   %y.tr = phi i32 [ %y, %entry ], [ %call9, %if.then ]
   %z.tr = phi i32 [ %z, %entry ], [ %call14, %if.then ]
   tail call void @llvm.dbg.value(metadata i32 %x.tr, i64 0, metadata !6, metadata !DIExpression()), !dbg !7

 return:                                           ; preds = %if.end
   ret i32 %z.tr, !dbg !17
 }
 
 define i32 @tak2(i32 %x, i32 %y, i32 %z) nounwind ssp !dbg !0 {
 ; CHECK-LABEL: define i32 @tak2(
 ; CHECK: entry
 ; CHECK: tail call void @llvm.dbg.value(metadata i32 %x.tr
-; CHECK: tail call void @llvm.dbg.value(metadata i32 undef
+; CHECK: tail call void @llvm.dbg.value(metadata i32 %y.tr
 
 entry:
   br label %tailrecurse
 
 tailrecurse:                                      ; preds = %if.then, %entry
   %x.tr = phi i32 [ %x, %entry ], [ %call, %if.then ]
   %y.tr = phi i32 [ %y, %entry ], [ %call9, %if.then ]
   %z.tr = phi i32 [ %z, %entry ], [ %call14, %if.then ]

 
 @channelColumns = external global i64
 @horzPlane = external global i8*, align 8
 
 define void @FindFreeHorzSeg(i64 %startCol, i64 %row, i64* %rowStart) {
 ; Ensure that the loop increment basic block is rotated into the tail of the
 ; body, even though it contains a debug intrinsic call.
 ; CHECK-LABEL: define void @FindFreeHorzSeg(
+; CHECK: for.inc:
+; CHECK: phi i64 [ %{{[^,]*}}, %{{[^,]*}} ]
 ; CHECK: %dec = add
 ; CHECK-NEXT: tail call void @llvm.dbg.value
+; CHECK-NEXT: br label %for.cond
 ; CHECK: %cmp = icmp
 ; CHECK: br i1 %cmp
-; CHECK: phi i64 [ %{{[^,]*}}, %{{[^,]*}} ]
-; CHECK-NEXT: br label %for.end
 
 
 entry:
   br label %for.cond
 
 for.cond:
   %i.0 = phi i64 [ %startCol, %entry ], [ %dec, %for.inc ]
   %cmp = icmp eq i64 %i.0, 0

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

+; RUN: opt -S < %s -loop-rotate -verify-dom-info -verify-loop-info | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Check that a basic while loop is rotated.
+; CHECK-LABEL: @bar0
+; CHECK: while.cond.lr:                                    ; preds = %entry
+; CHECK: while.body.lr.ph:                                 ; preds = %while.cond.lr
+
+declare void @foo0(i64* %this, i64* %that)
+
+define void @bar0(i64* %__begin1, i64* %__end1, i64** %__end2) {
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %while.body, %entry
+  %__end1.addr.0 = phi i64* [ %__end1, %entry ], [ %incdec.ptr, %while.body ]
+  %cmp = icmp eq i64* %__end1.addr.0, %__begin1
+  br i1 %cmp, label %while.end, label %while.body
+
+while.body:                                       ; preds = %while.cond
+  %incdec.ptr = load i64*, i64** %__end2, align 8
+  tail call void @foo0(i64* %__begin1, i64* %incdec.ptr)
+  store i64* %incdec.ptr, i64** %__end2, align 8
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  ret void
+}
+
+; Check that the loop is rotated and multiple phis are updated.
+; CHECK-LABEL: @foo2
+; CHECK: do.body.i10.lr:                                   ; preds = %if.else.i3
+; CHECK: do.cond.i19.lr.ph:                                ; preds = %do.body.i10.lr
+
+define void @foo2() {
+entry:
+  br i1 undef, label %for.body, label %for.end
+
+for.body:                                         ; preds = %entry
+  br i1 undef, label %inverse.exit21, label %if.else.i3
+
+if.else.i3:                                       ; preds = %for.body
+  br label %do.body.i10
+
+do.body.i10:                                      ; preds = %do.cond.i19, %if.else.i3
+  %b1.0.i4 = phi i64 [ 0, %if.else.i3 ], [ %b2.0.i7, %do.cond.i19 ]
+  %b2.0.i7 = phi i64 [ 1, %if.else.i3 ], [ %sub8.i18, %do.cond.i19 ]
+  br i1 undef, label %do.cond.thread.i15, label %do.cond.i19
+
+do.cond.thread.i15:                               ; preds = %do.body.i10
+  br label %inverse.exit21
+
+do.cond.i19:                                      ; preds = %do.body.i10
+  %mul.i17 = mul nsw i64 undef, %b2.0.i7
+  %sub8.i18 = sub nsw i64 %b1.0.i4, %mul.i17
+  br label %do.body.i10
+
+inverse.exit21:                                   ; preds = %do.cond.thread.i15, %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %inverse.exit21, %entry
+  ret void
+}
+
+; Check that the loop with switch block within loop is rotated and the critical edge is first split.
+; CHECK-LABEL: @foo3
+; CHECK: entry:
+; CHECK: br i1 %cmp1, label %while.cond.preheader, label %while.exit
+; CHECK: while.cond.lr:                                    ; preds = %while.cond.preheader
+; CHECK: %conv7.lr = ashr exact i64 undef, 32
+; CHECK: br i1 %cmp, label %if.else106.lr.ph, label %while.exit.loopexit
+; CHECK: if.else106.lr.ph:                                 ; preds = %while.cond.lr
+; CHECK: if.else106:                                       ; preds = %if.else106.lr.ph, %while.cond
+; CHECK: switch i32 %val, label %if.else106.while.exit.loopexit_crit_edge [
+; CHECK: if.else106.while.exit.loopexit_crit_edge:         ; preds = %if.else106
+; CHECK: while.cond:                                       ; preds = %if.then467
+; CHECK: %conv7 = ashr exact i64 undef, 32
+; CHECK: br i1 %cmp, label %if.else106, label %while.cond.while.exit.loopexit_crit_edge
+; CHECK: while.cond.while.exit.loopexit_crit_edge:         ; preds = %while.cond
+; CHECK: if.then130:                                       ; preds = %if.else106
+; CHECK: if.then467:                                       ; preds = %if.then130, %if.else106
+; CHECK: while.exit.loopexit:                              ; preds = %if.else106.while.exit.loopexit_crit_edge, %while.cond.while.exit.loopexit_crit_edge, %while.cond.lr
+; CHECK: while.exit:                                       ; preds = %while.exit.loopexit, %entry
+
+define i32 @foo3(i1 %cmp, i1 %cmp1, i32 %val) {
+entry:
+  br i1 %cmp1, label %while.cond, label %while.exit
+
+while.cond:
+  %conv7 = ashr exact i64 undef, 32
+  br i1 %cmp, label %if.else106, label %while.exit
+
+if.else106:
+  switch i32 %val, label %while.exit [
+    i32 12, label %if.then130
+    i32 30, label %if.then467
+  ]
+
+if.then130:
+  br label %if.then467
+
+if.then467:
+  br label %while.cond
+
+while.exit:
+  ret i32 0
+}
+
+; Check that the loop with pre-header and loop-body having a switch block is rotated.
+; CHECK-LABEL: @bar5
+; CHECK: bb19.preheader:                                   ; preds = %bb10, %bb10
+; CHECK: bb19.lr:                                          ; preds = %bb19.preheader
+; CHECK: bb12.lr.ph:                                       ; preds = %bb19.lr
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare i32 @foo5(i8*, i32)
+
+define i32 @bar5(i8* %arg, i32 %arg1, i8* %arg2, i32 %arg3) {
+bb10:
+  switch i32 %arg3, label %bb11 [
+    i32 46, label %bb19
+    i32 32, label %bb19
+  ]
+
+bb11:                                             ; preds = %bb10
+  ret i32 -1
+
+bb12:                                             ; preds = %bb19
+  switch i8 undef, label %bb13 [
+    i8 32, label %bb21
+    i8 46, label %bb21
+  ]
+
+bb13:                                             ; preds = %bb12
+  br label %bb15
+
+bb15:                                             ; preds = %bb13
+  br i1 undef, label %bb17, label %bb16
+
+bb16:                                             ; preds = %bb15
+  %tmp = call i32 @foo5(i8* %tmp20, i32 10)
+  ret i32 0
+
+bb17:                                             ; preds = %bb15
+  %tmp18 = phi i8* [ %tmp20, %bb15 ]
+  br label %bb19
+
+bb19:                                             ; preds = %bb17, %bb10, %bb10
+  %tmp20 = phi i8* [ %tmp18, %bb17 ], [ null, %bb10 ], [ null, %bb10 ]
+  br i1 undef, label %bb21, label %bb12
+
+bb21:                                             ; preds = %bb19, %bb12, %bb12
+  ret i32 0
+}
+
+declare i8* @foo7()
+
+; Check that the loop with multiple exits and a if-block branching within the loop is rotated.
+; CHECK-LABEL: @bar7
+; CHECK: entry:
+; CHECK: for.cond.preheader:                               ; preds = %entry
+; CHECK: br label %for.cond.lr
+; CHECK: for.cond.lr:                                      ; preds = %for.cond.preheader
+; CHECK: for.body.lr:                                      ; preds = %for.cond.lr
+; CHECK: if.end20.lr.ph:                                   ; preds = %for.body.lr
+; CHECK: if.end20:                                         ; preds = %if.end20.lr.ph, %for.body
+; CHECK: %phi.nh = phi i8* [ %call15, %for.body ], [ %call15.lr, %if.end20.lr.ph ]
+; CHECK: for.cond:                                         ; preds = %for.inc
+; CHECK: br i1 false, label %for.body, label %for.cond.return.loopexit_crit_edge
+; CHECK: for.cond.return.loopexit_crit_edge:               ; preds = %for.cond
+; CHECK: for.body:                                         ; preds = %for.cond
+; CHECK: br i1 false, label %if.end20, label %for.body.return.loopexit_crit_edge
+; CHECK: for.body.return.loopexit_crit_edge:               ; preds = %for.body
+; CHECK: if.then23:                                        ; preds = %crl, %if.then.i
+; CHECK: %call15.lcssa = phi i8* [ %phi.nh, %crl ], [ %phi.nh, %if.then.i ]
+
+define void @bar7(i1 %cmp1) {
+entry:
+  br i1 %cmp1, label %return, label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  br i1 undef, label %for.body, label %return
+
+for.body:                                         ; preds = %for.cond
+  %call15 = call i8* @foo7()
+  br i1 undef, label %if.end20, label %return
+
+if.end20:                                         ; preds = %for.body
+  %issuer.i = getelementptr inbounds i8, i8* %call15, i64 24
+  br i1 undef, label %if.then.i, label %for.cond.i
+
+if.then.i:                                        ; preds = %if.end20
+  br i1 undef, label %if.then23, label %crl
+
+for.cond.i:                                       ; preds = %if.end20
+  br i1 undef, label %crl, label %for.inc
+
+crl:                                              ; preds = %if.then.i, %for.cond.i
+  br i1 undef, label %if.then23, label %for.inc
+
+if.then23:                                        ; preds = %crl, %if.then.i
+  %reason = getelementptr inbounds i8, i8* %call15, i64 32
+  br label %return
+
+for.inc:                                          ; preds = %crl, %for.cond.i
+  br label %for.cond
+
+return:                                           ; preds = %if.then23, %for.body, %for.cond, %if.end
+  ret void
+}
+
+; Check that the loop-latch with indirect branch is not rotated.
+; CHECK-LABEL: @foo8
+; CHECK-NOT: {{.*}}.lr
+; CHECK-NOT: {{.*}}.lr.ph
+
+@f.x = internal global [3 x i8*] [i8* blockaddress(@foo8, %F), i8* blockaddress(@foo8, %G), i8* blockaddress(@foo8, %H)], align 16
+
+; Function Attrs: nounwind uwtable
+define i32 @foo8(i32 %i, i32 %j, i32 %k) {
+entry:
+  %retval = alloca i32, align 4
+  %i.addr = alloca i32, align 4
+  %j.addr = alloca i32, align 4
+  %k.addr = alloca i32, align 4
+  store i32 %i, i32* %i.addr, align 4
+  store i32 %j, i32* %j.addr, align 4
+  store i32 %k, i32* %k.addr, align 4
+  br label %F
+
+F:                                                ; preds = %entry, %indirectgoto
+  %0 = load i32, i32* %i.addr, align 4
+  %1 = load i32, i32* %j.addr, align 4
+  %cmp = icmp sgt i32 %0, %1
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %F
+  br label %G
+
+if.else:                                          ; preds = %F
+  %2 = load i32, i32* %i.addr, align 4
+  %3 = load i32, i32* %k.addr, align 4
+  %cmp1 = icmp sgt i32 %2, %3
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:                                         ; preds = %if.else
+  br label %H
+
+if.end:                                           ; preds = %if.else
+  br label %if.end3
+
+if.end3:                                          ; preds = %if.end
+  %call = call i32 (...) @z()
+  %idxprom = sext i32 %call to i64
+  %arrayidx = getelementptr inbounds [3 x i8*], [3 x i8*]* @f.x, i64 0, i64 %idxprom
+  %4 = load i8*, i8** %arrayidx, align 8
+  br label %indirectgoto
+
+G:                                                ; preds = %if.then, %indirectgoto
+  %call4 = call i32 (...) @g()
+  store i32 %call4, i32* %retval, align 4
+  br label %return
+
+H:                                                ; preds = %if.then2, %indirectgoto
+  %call5 = call i32 (...) @h()
+  store i32 %call5, i32* %retval, align 4
+  br label %return
+
+return:                                           ; preds = %H, %G
+  %5 = load i32, i32* %retval, align 4
+  ret i32 %5
+
+indirectgoto:                                     ; preds = %if.end3
+  %indirect.goto.dest = phi i8* [ %4, %if.end3 ]
+  indirectbr i8* %indirect.goto.dest, [label %F, label %G, label %H]
+}
+
+declare i32 @g(...)
+declare i32 @h(...)
+declare i32 @z(...)

llvm/test/Transforms/LoopRotate/multiple-exits.ll

 ; RUN: opt -S -loop-rotate < %s -verify-loop-info -verify-dom-info | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.8.0"
 
-; PR7447
+; PR7447: there should be one loop rotated, for.cond is rotated.
 define i32 @test1([100 x i32]* nocapture %a) nounwind readonly {
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.cond1, %entry
   %sum.0 = phi i32 [ 0, %entry ], [ %sum.1, %for.cond1 ]
   %i.0 = phi i1 [ true, %entry ], [ false, %for.cond1 ]
   br i1 %i.0, label %for.cond1, label %return
 
land.rhs:                                         ; preds = %for.cond1
   %cmp4 = icmp ugt i32 %add, 1000
   %inc = add i32 %i.1, 1
   br i1 %cmp4, label %return, label %for.cond1
 
 return:                                           ; preds = %for.cond, %land.rhs
   %retval.0 = phi i32 [ 1000, %land.rhs ], [ %sum.0, %for.cond ]
   ret i32 %retval.0
 
-; CHECK-LABEL: @test1(
-; CHECK: for.cond1.preheader:
-; CHECK: %sum.04 = phi i32 [ 0, %entry ], [ %sum.1.lcssa, %for.cond.loopexit ]
-; CHECK: br label %for.cond1
-
-; CHECK: for.cond1:
-; CHECK: %sum.1 = phi i32 [ %add, %land.rhs ], [ %sum.04, %for.cond1.preheader ]
-; CHECK: %i.1 = phi i32 [ %inc, %land.rhs ], [ 0, %for.cond1.preheader ]
-; CHECK: %cmp2 = icmp ult i32 %i.1, 100
-; CHECK: br i1 %cmp2, label %land.rhs, label %for.cond.loopexit
+; CHECK-LABEL: @test1
+; Check that the outer loop is rotated.
+; CHECK: for.cond.lr:
+; CHECK: for.cond1.preheader.lr.ph:
+; CHECK: for.cond1:                                        ; preds = %for.cond1.preheader, %land.rhs
+; CHECK:  %sum.1 = phi i32 [ %add, %land.rhs ], [ %phi.nh, %for.cond1.preheader ]
+; CHECK:  %i.1 = phi i32 [ %inc, %land.rhs ], [ 0, %for.cond1.preheader ]
 }
 
 define void @test2(i32 %x) nounwind {
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %if.end, %entry
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %if.end ]
a:                                                ; preds = %for.body
   br label %return
 
 return.loopexit:                                  ; preds = %for.cond
   br label %return
 
 return:                                           ; preds = %return.loopexit, %a
   ret void
 
+; Both for.cond and for.body are cloned outside of the loop and if.end is the new loop header.
 ; CHECK-LABEL: @test2(
 ; CHECK: if.end:
-; CHECK: %inc = add i32 %i.02, 1
-; CHECK: %cmp = icmp eq i32 %inc, %x
-; CHECK: br i1 %cmp, label %for.cond.return.loopexit_crit_edge, label %for.body
+; CHECK-NEXT: phi
+; CHECK: %inc = add i32 %phi.nh, 1
+; CHECK: for.cond:
+; CHECK-NEXT: phi
+; CHECK-NEXT: %cmp = icmp eq i32 %i.0, %x
+; CHECK-NEXT: br i1 %cmp, label %for.cond.return.loopexit_crit_edge, label %for.body
+; CHECK: for.cond.return.loopexit_crit_edge:
 }
 
 declare i32 @foo(i32)
 
 declare i32 @bar(i32)
 
 @_ZTIi = external constant i8*
 
 ; Verify dominators.

llvm/test/Transforms/LoopRotate/nosimplifylatch.ll

 ; RUN: opt -S < %s -loop-rotate -licm -verify-dom-info -verify-loop-info | FileCheck %s
 target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
 target triple = "arm64-apple-ios8.0.0"
 
 ;CHECK: for.inc:
-;CHECK-NEXT: %incdec.ptr.i = getelementptr 
+;CHECK-NEXT: phi
+;CHECK-NEXT: %incdec.ptr.i = getelementptr
+;CHECK-NEXT: br
 
 ; Function Attrs: alwaysinline inlinehint nounwind readonly ssp
 define linkonce_odr hidden i64 @_ZNSt3__14findINS_11__wrap_iterIPiEEiEET_S4_S4_RKT0_(i64 %__first.coerce, i64 %__last.coerce, i32* nocapture readonly dereferenceable(4) %__value_) {
 entry:
   %coerce.val.ip = inttoptr i64 %__first.coerce to i32*
   %coerce.val.ip2 = inttoptr i64 %__last.coerce to i32*
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry

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

for.body:                                         ; preds = %for.cond
   store double %add, double* %arrayidx10
   %inc = add nsw i64 %j.0, 1                      ; <i64> [#uses=1]
   br label %for.cond
 
 for.end:                                          ; preds = %for.cond
   ret void
 }
 
 ; Should only end up with one phi.
 ; CHECK-LABEL:      define void @test(
 ; CHECK-NEXT: entry:
-; CHECK-NEXT:   br label %for.body
+; CHECK-NEXT:   br label %for.cond.lr
 ; CHECK:      for.body:
-; CHECK-NEXT:   %j.01 = phi i64
-; CHECK-NOT:  br
-; CHECK:   br i1 %cmp, label %for.body, label %for.end
-; CHECK:      for.end:
-; CHECK-NEXT:        ret void
+; CHECK-NEXT:  %phi.nh = phi i64
+; CHECK-NOT: = phi
+; CHECK:  %inc = add nsw i64 %phi.nh, 1
+; CHECK:   br label %for.cond
+; CHECK: for.cond:
+; CHECK:   br i1 %cmp
+; CHECK: for.end:
+; CHECK-NEXT:  ret void

llvm/test/Transforms/LoopRotate/preserve-loop-simplify.ll

 ; RUN: opt -S -loop-rotate < %s -verify-loop-info | FileCheck %s
 ;
 ; Verify that LoopRotate preserves LoopSimplify form even in very peculiar loop
 ; structures. We manually validate the CFG with FileCheck because currently we
 ; can't cause a failure when LoopSimplify fails to be preserved.
 
+; Check that inner.header and inner.body both are cloned outside the loop
+; such that inner.latch becomes the new loop header.
+
 define void @PR18643() {
 ; CHECK-LABEL: @PR18643(
 entry:
   br label %outer.header
 ; CHECK: br label %outer.header
 
 outer.header:
 ; CHECK: outer.header:
   br i1 undef, label %inner.header, label %outer.body
 ; CHECK-NEXT: br i1 {{[^,]*}}, label %[[INNER_PREROTATE_PREHEADER:[^,]*]], label %outer.body
 
 ; CHECK: [[INNER_PREROTATE_PREHEADER]]:
-; CHECK-NEXT: br i1 {{[^,]*}}, label %[[INNER_PREROTATE_PREHEADER_SPLIT_RETURN:[^,]*]], label %[[INNER_ROTATED_PREHEADER:[^,]*]]
+; CHECK: br label %inner.header.lr
+
+; CHECK: inner.header.lr:
+; CHECK: br i1 true, label %return, label %inner.body.lr
+
+; CHECK: inner.body.lr:
+; CHECK-NEXT: br i1 {{[^,]*}}, label %[[OUTER_LATCH_LOOPEXIT:[^,]*]], label %[[INNER_ROTATED_PREHEADER:[^,]*]]
 
 ; CHECK: [[INNER_ROTATED_PREHEADER]]:
-; CHECK-NEXT: br label %inner.body
+; CHECK-NEXT: br label %inner.latch
 
 inner.header:
 ; Now the latch!
 ; CHECK: inner.header:
   br i1 undef, label %return, label %inner.body
 ; CHECK-NEXT: br i1 {{[^,]*}}, label %[[INNER_SPLIT_RETURN:[^,]*]], label %inner.body
 
+; CHECK: [[INNER_SPLIT_RETURN]]:
+; CHECK: br label %return
+
 inner.body:
 ; Now the header!
 ; CHECK: inner.body:
   br i1 undef, label %outer.latch, label %inner.latch
-; CHECK-NEXT: br i1 {{[^,]*}}, label %[[INNER_SPLIT_OUTER_LATCH:[^,]*]], label %inner.header
+; CHECK-NEXT: br i1 {{[^,]*}}, label %[[OUTER_LATCH_LOOPEXIT:[^,]*]], label %inner.latch
+
+; CHECK: [[OUTER_LATCH_LOOPEXIT]]:
+; CHECK-NEXT: br label %outer.latch.loopexit
 
 inner.latch:
 ; Dead!
   br label %inner.header
 
 outer.body:
 ; CHECK: outer.body:
   br label %outer.latch
 ; CHECK-NEXT: br label %outer.latch
 
-; L2 -> L1 exit edge needs a simplified exit block.
-; CHECK: [[INNER_SPLIT_OUTER_LATCH]]:
-; CHECK-NEXT: br label %outer.latch
 
 outer.latch:
 ; CHECK: outer.latch:
   br label %outer.header
 ; CHECK-NEXT: br label %outer.header
 
-; L1 -> L0 exit edge need sa simplified exit block.
-; CHECK: [[INNER_PREROTATE_PREHEADER_SPLIT_RETURN]]:
-; CHECK-NEXT: br label %return
-
-; L2 -> L0 exit edge needs a simplified exit block.
-; CHECK: [[INNER_SPLIT_RETURN]]:
-; CHECK-NEXT: br label %return
-
 return:
 ; CHECK: return:
   unreachable
 }

llvm/test/Transforms/LoopRotate/simplifylatch.ll

 ; RUN: opt -S < %s -loop-rotate -licm -verify-dom-info -verify-loop-info | FileCheck %s
 ; PR2624 unroll multiple exits
 
 @mode_table = global [4 x i32] zeroinitializer    ; <[4 x i32]*> [#uses=1]
 
-; CHECK-LABEL: @f(
-; CHECK-NOT: bb:
+; Check that loop with multiple exits is rotated.
+; CHECK-LABEL: @f
+; CHECK: bb.lr:
+; CHECK: bb2.lr:
+; CHECK: bb4.lr.ph:
+; CHECK: bb:
+
 define i8 @f() {
 entry:
   tail call i32 @fegetround( )    ; <i32>:0 [#uses=1]
   br label %bb
 
 bb:   ; preds = %bb4, %entry
   %mode.0 = phi i8 [ 0, %entry ], [ %indvar.next, %bb4 ]    ; <i8> [#uses=4]
   zext i8 %mode.0 to i32    ; <i32>:1 [#uses=1]
bb4:    ; preds = %bb2
   br label %bb
 
 bb5:    ; preds = %bb2
   tail call void @raise_exception( ) noreturn
   unreachable
 }
 
 declare i32 @fegetround()
-
 declare void @raise_exception() noreturn
 
-;CHECK: for.body.lr.ph:
-;CHECK-NEXT:  %arrayidx1 = getelementptr inbounds i8, i8* %CurPtr, i64 0
-;CHECK-NEXT:  %0 = load i8, i8* %arrayidx1, align 1
-;CHECK-NEXT:  %conv2 = sext i8 %0 to i32
-;CHECK-NEXT:  br label %for.body
-
-define i32 @foo(i8* %CurPtr, i32 %a) #0 {
-entry:
-  br label %for.cond
-
-for.cond:           ; preds = %for.inc, %entry
-  %i.0 = phi i32 [ 1, %entry ], [ %inc, %for.inc ]
-  %cmp = icmp ne i32 %i.0, %a
-  br i1 %cmp, label %for.body, label %return
-
-for.body:           ; preds = %for.cond
-  %idxprom = zext i32 %i.0 to i64
-  %arrayidx = getelementptr inbounds i8, i8* %CurPtr, i64 %idxprom
-  %0 = load i8, i8* %arrayidx, align 1
-  %conv = sext i8 %0 to i32
-  %arrayidx1 = getelementptr inbounds i8, i8* %CurPtr, i64 0
-  %1 = load i8, i8* %arrayidx1, align 1
-  %conv2 = sext i8 %1 to i32
-  %cmp3 = icmp ne i32 %conv, %conv2
-  br i1 %cmp3, label %return, label %for.inc
-
-for.inc:            ; preds = %for.body
-  %inc = add i32 %i.0, 1
-  br label %for.cond
-
-return:             ; preds = %for.cond, %for.body
-  %retval.0 = phi i32 [ 0, %for.body ], [ 1, %for.cond ]
-  ret i32 %retval.0
-}
-
-attributes #0 = { nounwind uwtable }

llvm/test/Transforms/LoopRotate/vect.omp.persistence.ll

+; RUN: opt < %s -loop-rotate -S | FileCheck -check-prefix=CHECK1 %s
+; REQUIRES: asserts
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+
+; The loop rotate should not remove the metadata.
+; See http://reviews.llvm.org/D3348 for details.
+
+;
+; Test #1
+;
+; Ensure that "llvm.loop.vectorize.enable" metadata was not lost after loop-rotate.
+; In past LoopRotate was clearing that metadata.
+;
+; The source C code is:
+; void rotated(float *a, int size)
+; {
+;   int t = 0;
+;   #pragma omp simd
+;   for (int i = 0; i < size; ++i) {
+;     a[i] = a[i-5] * a[i+2];
+;     ++t;
+;   }
+;}
+
+; CHECK1: @rotated1
+; CHECK1: for.header.lr:
+; CHECK1: for.body.lr.ph:
+; CHECK1: for.header:
+; CHECK1: br i1 %cmp2, label %for.header.for.end.loopexit_crit_edge, label %for.body, !llvm.loop !0
+; CHECK1: for.header.for.end.loopexit_crit_edge:
+
+define void @rotated1(float* nocapture %a, i64 %size) {
+entry:
+  %cmp1 = icmp sgt i64 %size, 0
+  br i1 %cmp1, label %for.header, label %for.end
+
+for.header:
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
+  %cmp2 = icmp sgt i64 %indvars.iv, %size
+  br i1 %cmp2, label %for.end, label %for.body
+
+for.body:
+
+  %0 = add nsw i64 %indvars.iv, -5
+  %arrayidx = getelementptr inbounds float, float* %a, i64 %0
+  %1 = load float, float* %arrayidx, align 4, !llvm.mem.parallel_loop_access !1
+  %2 = add nsw i64 %indvars.iv, 2
+  %arrayidx2 = getelementptr inbounds float, float* %a, i64 %2
+  %3 = load float, float* %arrayidx2, align 4, !llvm.mem.parallel_loop_access !1
+  %mul = fmul float %1, %3
+  %arrayidx4 = getelementptr inbounds float, float* %a, i64 %indvars.iv
+  store float %mul, float* %arrayidx4, align 4, !llvm.mem.parallel_loop_access !1
+
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.header, !llvm.loop !1
+
+for.end:
+  ret void
+}
+
+!1 = !{!1, !2}
+!2 = !{!"llvm.loop.vectorize.enable", i1 true}
+
+; CHECK1: @rotated2
+; CHECK1: loop_cond.lr:
+; CHECK1: loop_inc.lr.ph:
+; CHECK1: loop_inc:
+; CHECK1: loop_cond:
+; CHECK1: br i1 %cmp, label %loop_cond.return_crit_edge, label %loop_inc, !llvm.loop !2
+; CHECK1: loop_cond.return_crit_edge:
+
+;
+; Test #2
+;
+; Ensure that "llvm.loop.vectorize.enable" metadata was not lost due to loop rotation
+; (see http://reviews.llvm.org/D3348#comment-4).
+;
+define i32 @rotated2(i32 %a) {
+entry:
+  br label %loop_cond
+loop_cond:
+  %indx = phi i32 [ 1, %entry ], [ %inc, %loop_inc ]
+  %cmp = icmp ne i32 %indx, %a
+  br i1 %cmp, label %return, label %loop_inc
+loop_inc:
+  %inc = add i32 %indx, 1
+  br label %loop_cond, !llvm.loop !3
+return:
+  ret i32 0
+}
+
+!3 = !{!3, !4}
+!4 = !{!"llvm.loop.vectorize.enable", i1 true}
+
+; CHECK1: !0 = distinct !{!0, !1}
+; CHECK1: !1 = !{!"llvm.loop.vectorize.enable", i1 true}
+; CHECK1: !2 = distinct !{!2, !1}

llvm/test/Transforms/LoopSimplify/ashr-crash.ll

 
 ; Check that the def-use chain that leads to the bad SCEV is still
 ; there.
 ;
 ; CHECK-LABEL: @foo
 ; CHECK-LABEL: entry:
 ; CHECK-LABEL: for.cond1.preheader:
 ; CHECK-LABEL: for.body3:
-; CHECK: %cmp4.le.le
-; CHECK: %conv.le.le = zext i1 %cmp4.le.le to i32
-; CHECK: %xor.le.le = xor i32 %conv6.le.le, 1
+; CHECK: %cmp4
+; CHECK: %conv = zext i1 %cmp4 to i32
+; CHECK: %xor = xor i32 %conv6, 1
 define void @foo() {
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc7, %entry
   %storemerge = phi i32 [ 0, %entry ], [ %inc8, %for.inc7 ]
   %f.0 = phi i32 [ undef, %entry ], [ %f.1, %for.inc7 ]
   store i32 %storemerge, i32* @d, align 4

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

 ; RUN: opt < %s -O2 -force-vector-interleave=2 -force-vector-width=4 -debug-only=loop-vectorize -stats -S 2>&1 | FileCheck %s
 ; REQUIRES: asserts
 
 ; Loop from "rotated"
 ; CHECK: LV: Loop hints: force=enabled
-; Loop from "nonrotated"
-; CHECK: LV: Loop hints: force=enabled
 ; No more loops in the module
 ; CHECK-NOT: LV: Loop hints: force=
 ; In total only 1 loop should be rotated.
 ; CHECK: 1 loop-rotate
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 ; See http://reviews.llvm.org/D3348 for details.
 
 ;
 ; Test #1
 ;
 ; Ensure that "llvm.loop.vectorize.enable" metadata was not lost prior to LoopVectorize pass.
 ; In past LoopRotate was clearing that metadata.
 ;
 ; The source C code is:
 ; void rotated(float *a, int size)
 ; {
 ;   int t = 0;
 ;   #pragma omp simd
 ;   for (int i = 0; i < size; ++i) {
 ;     a[i] = a[i-5] * a[i+2];

 
 for.end:
   ret void
 }
 
 !1 = !{!1, !2}
 !2 = !{!"llvm.loop.vectorize.enable", i1 true}
 
-;
-; Test #2
-;
-; Ensure that "llvm.loop.vectorize.enable" metadata was not lost even
-; if loop was not rotated (see http://reviews.llvm.org/D3348#comment-4).
-;
-define i32 @nonrotated(i32 %a) {
-entry:
-  br label %loop_cond
-loop_cond:
-  %indx = phi i32 [ 1, %entry ], [ %inc, %loop_inc ]
-  %cmp = icmp ne i32 %indx, %a
-  br i1 %cmp, label %return, label %loop_inc
-loop_inc:
-  %inc = add i32 %indx, 1
-  br label %loop_cond, !llvm.loop !3
-return:
-  ret i32 0
-}
-
-!3 = !{!3, !4}
-!4 = !{!"llvm.loop.vectorize.enable", i1 true}