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

411

Could we also check that LoopSimplify is also preserved?

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

9–22

Can you please explain why this test was changed?

llvm/test/Transforms/LoopRotate/alloca.ll

8–11

Do we really need this change?

llvm/test/Transforms/LoopRotate/dbgvalue.ll

8–11

Why was this test changed?

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

2

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

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

6–7 ↗

(On Diff #76239)

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

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

1–9 ↗

(On Diff #76239)

Why can't we run them together?

15 ↗

(On Diff #76239)

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

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

78–81

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

llvm/test/Transforms/LoopRotate/nosimplifylatch.ll

6–8

Why do we need this change?

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

31

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

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

llvm/test/Transforms/LoopRotate/pr7447.ll

5–6

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

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

19–25

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

llvm/test/Transforms/LoopRotate/simplifylatch.ll

47

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

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

7–12

This test actually should probably be rewritten.

It tries to check that

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

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

[hiraditya]

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

I can remove the change.

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

19–25

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

llvm/test/Transforms/LoopRotate/simplifylatch.ll

47

Yes the rotated loop has a preheader.

[hiraditya]

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 ↗

(On Diff #73486)

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.

157

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.

178

Why is this called 'TODO'?

196

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?

204

This line seems too long.

206

s/Ins/Inst/

313

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

321

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.

325

Why is this under DEBUG?

410

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

432–433

Yes, please rename it.

442

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

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

1–2

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

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

llvm/test/Transforms/LoopRotate/dbgvalue.ll

8–11

The question is still relevant.

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

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

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

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

llvm/test/Transforms/LoopRotate/nosimplifylatch.ll

6–8

The question is still relevant.

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

36–45

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

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

19–25

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

llvm/test/Transforms/LoopRotate/simplifylatch.ll

48–60

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

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

7–12

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

[hiraditya]

Addressed Michael's comments.

llvm/lib/Transforms/Scalar/LoopRotation.cpp

313

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.

321

I'll remove this.

325

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

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

19–25

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

llvm/test/Transforms/LoopRotate/simplifylatch.ll

48–60

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

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

7–12

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

[mzolotukhin]

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 ↗

(On Diff #82375)

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

151

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.

179

Why is it called 'TODO'?

200–201

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?

226

Missing dot before Returns.

442

Please rename the function per the previous discussion.

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

1–2

Still relevant.

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

36–45

It can be CHECK-NEXT I guess.

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

19–25

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

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

7–12

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

[hiraditya]

llvm/lib/IR/Metadata.cpp

1109–1112 ↗

(On Diff #82375)

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

151

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

179

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

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

1–2

The test fails if I remove simplifycfg.

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

19–25

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

[hiraditya]

Addressed Michael's comments.

[mzolotukhin]

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

7

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

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

210 ↗

(On Diff #83981)

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

179

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

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

1–2

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

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

3–4

Please remove this.

9

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

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

1–2 ↗

(On Diff #83981)

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

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

22

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

[hiraditya]

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

1–2

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

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

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

7

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

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

9

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

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

22

Will do

[hiraditya]

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

210 ↗

(On Diff #83981)

I have minimized other tests as well.

llvm/test/Transforms/LoopRotate/nosimplifylatch.ll

6–8

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.

101–103

This function seems to be unused.

122–123

Formatting is slightly off here.

149–152

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

157

Why do we need this check?

189–190

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

208

Why is UserInst guaranteed to be a PHINode?

225–226

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.

226–227

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

250

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

260–261

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

306–311

You have the same typedef inside LoopRotate.

307–310

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

386

Can we avoid quadratic complexity here?

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

73 ↗

(On Diff #87288)

This function doesn't have any indirect branches.

149–153 ↗

(On Diff #87288)

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

208

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

225–226

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.

226–227

I've updated the comment.

260–261

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.

386

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

73 ↗

(On Diff #87288)

I'll update the comment.

149–153 ↗

(On Diff #87288)

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

386

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

149–153 ↗

(On Diff #87288)

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.

11 ↗

(On Diff #90501)

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

[hiraditya]

Removed unreachable from testcases.
Replaced fp* with i64*

llvm/lib/Transforms/Scalar/LoopRotation.cpp

386

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

149–153 ↗

(On Diff #87288)

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 ↗

(On Diff #73486)

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 ↗

(On Diff #91422)

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

llvm/lib/Transforms/Scalar/LoopRotation.cpp

61–63

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

151

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

208

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/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.
+// This file implements Loop Rotation Pass:
+// 1. Canonicalize loop latch to have only one successor.
+// 2. Clone all the BBs which are exiting the loop.
+// 3. Adjust phi of cloned BBs
+// 4. Add phi to the new loop header
+// 5. Update DOM
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/LoopRotation.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/LoopPassManager.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/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"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-rotate"
 
-static cl::opt<unsigned> DefaultRotationThreshold(
+static cl::opt<unsigned> RotationMaxHeaderSize(
     "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<int> MaxLoopsRotated(
+    "max-loops-rotated", cl::init(-1), cl::Hidden,
+    cl::desc("The maximum loops to be rotated (-1 means no limit)"));
+
+static int LoopsRotated = 0;
+
 STATISTIC(NumRotated, "Number of loops rotated");
 
-namespace {
+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 (BasicBlock::iterator I = PhiBB->begin(),
+       E = PhiBB->end(); I != E; ++I) {
+    PHINode *PN = dyn_cast<PHINode>(I);
+    if (!PN)
+      break;
+    PN->removeIncomingValue(PN->getBasicBlockIndex(From));
+  }
+}
+
 /// A simple loop rotation transformation.
 class LoopRotate {
   const unsigned MaxHeaderSize;
   LoopInfo *LI;
   const TargetTransformInfo *TTI;
   AssumptionCache *AC;
   DominatorTree *DT;
   ScalarEvolution *SE;
-
+  Loop *L;
 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);
+             DominatorTree *DT, ScalarEvolution *SE, Loop *L)
+      : MaxHeaderSize(MaxHeaderSize), 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();
 
-/// 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;
+  void addPhis(SmallVectorImpl<BasicBlock *> &Blocks, ValueToValueMapTy &VMap,
+               const Twine &NameSuffix, BasicBlock *NewHeader,
+               BasicBlock *NewPreheader, BasicBlock *NewLatch);
 
-    Value *OrigPreHeaderVal = ValueMap.lookup(OrigHeaderVal);
+  bool isProfitableToRotate();
 
-    // 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;
+  bool isLegalToRotate();
 
-      // Increment the iterator before removing the use from the list.
-      ++UI;
+  void adjustNewHeaderPhis(ValueToValueMapTy &VMap, BasicBlock *NewH,
+                           BasicBlock *NewPH);
 
-      // 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;
-
-        // Users in the OrigPreHeader need to use the value to which the
-        // original definitions are mapped.
-        if (UserBB == OrigPreheader) {
-          U = OrigPreHeaderVal;
-          continue;
-        }
-      }
+  BasicBlock *collectSEMEBlocks(BasicBlock *OrigH, BasicBlock *OrigLatch,
+                                SmallVectorImpl<BasicBlock *> &Blocks,
+                                SmallPtrSetImpl<BasicBlock *> &Exits);
 
-      // Anything else can be handled by SSAUpdater.
-      SSA.RewriteUse(U);
-    }
-
-    // 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;
+  void addPhisToNewHeader(SmallVectorImpl<BasicBlock *> &Blocks,
+                          BasicBlock *NewHeader, BasicBlock *NewPreheader,
+                          BasicBlock *NewLatch, ValueToValueMapTy &VMap);
 
-          // The original users in the OrigHeader are already using the original
-          // definitions.
-          BasicBlock *UserBB = UserInst->getParent();
-          if (UserBB == OrigHeader)
-            continue;
-
-          // 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));
-        }
-      }
-    }
-  }
-}
+};
 
-/// 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) {
+bool LoopRotate::isLegalToRotate() {
   // 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;
 
-  BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator());
-  if (!BI || BI->isUnconditional())
+  const BasicBlock *OrigH = L->getHeader();
+  // The header may have invoke instruction to BBs within the loop.
+  const BranchInst *BI = dyn_cast<const BranchInst>(OrigH->getTerminator());
+  if (!BI || !BI->isConditional())
     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 (!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 (!isSEME(OrigH, LoopLatch, DT))
     return false;
 
+  return true;
+}
+
+// FIXME: count the number of instructions in Blocks and discard when reaching
+// upper bound.
+bool LoopRotate::isProfitableToRotate() {
+  const BasicBlock *OrigHeader = L->getHeader();
+
   // 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);
 
-    CodeMetrics Metrics;
-    Metrics.analyzeBasicBlock(OrigHeader, *TTI, EphValues);
-    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)
-      return false;
-  }
+
+
 
-  // Now, this loop is suitable for rotation.
-  BasicBlock *OrigPreheader = L->getLoopPreheader();
+  unsigned LoopSize = MaxHeaderSize;
+  for(const BasicBlock* BB : L->getBlocks()) {
+    unsigned BBSize = 0;
+    std::for_each(BB->begin(), BB->end(), [&BBSize, this](const Instruction &I){
+      BBSize += TTI->getUserCost(&I);
+    });
 
-  // If the loop could not be converted to canonical form, it must have an
-  // indirectbr in it, just give up.
-  if (!OrigPreheader)
+    if (LoopSize + BBSize >= RotationMaxSize)
       return false;
+    LoopSize += BBSize;
+  }
 
-  // Anything ScalarEvolution may know about this loop or the PHI nodes
-  // in its header will soon be invalidated.
-  if (SE)
-    SE->forgetLoop(L);
+  return true;
+}
 
-  DEBUG(dbgs() << "LoopRotation: rotating "; L->dump());
+// Add phis to the new header and adjust the phi nodes from the OrigHeader.
+void LoopRotate::addPhisToNewHeader(SmallVectorImpl<BasicBlock *> &Blocks,
+                                    BasicBlock *NewHeader, BasicBlock *NewPreheader,
+                                    BasicBlock *NewLatch, ValueToValueMapTy &VMap) {
+  // Add to NewHeader phi nodes for all copied variables which are used.
+  for (BasicBlock *BB : Blocks) {
+    for (Instruction &Inst : *BB) {
+      // Skip Ins with no use e.g., branches.
+      if (Inst.use_begin() == Inst.use_end())
+        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);
+      for (auto UI = Inst.use_begin(), E = Inst.use_end(); UI != E;) {
+        Use &U = *UI++;
+        Instruction *UserInst = cast<Instruction>(U.getUser());
+
+        // Nothing to rename when the use is dominated by the definition.
+        if (DT->dominates(&Inst, UserInst))
+          continue;
+
+        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 = PHINode::Create(Inst.getType(), 2, "phi.nh",
+                                      &*NewHeader->begin());
+        PN->addIncoming(&Inst, NewLatch);
+        PN->addIncoming(cast<Instruction>(VMap[&Inst]), NewPreheader);
 
-    // 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;
-      }
-    } else {
-      ValueMap[Inst] = C;
+        // When Inst does not dominate U, it is going to use the updated
+        // definition coming from PN.
+        U.set(PN);
       }
-    if (C) {
-      // Otherwise, stick the new instruction into the new block!
-      C->setName(Inst->getName());
-      C->insertBefore(LoopEntryBranch);
-    }
-  }
-
-  // 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) {
+  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);
+BasicBlock *
+LoopRotate::collectSEMEBlocks(BasicBlock *OrigH, BasicBlock *OrigLatch,
+                              SmallVectorImpl<BasicBlock *> &Blocks,
+                              SmallPtrSetImpl<BasicBlock *> &Exits) {
+  BasicBlock *NewH = nullptr;
+  for (auto I = df_begin(OrigH), E = df_end(OrigH); I != E;) {
+    if (!L->contains(*I)) {
+      I.skipChildren();
+      continue;
+    }
 
-  DEBUG(dbgs() << "LoopRotation: into "; L->dump());
+    // Copy until any BB where the branch does not exit loop, or the loop-latch.
+    if (OrigLatch == *I || !L->isLoopExiting(*I)
+        || !isa<BranchInst>((*I)->getTerminator())) {
+      // This will become the new header.
+      NewH = *I;
+      I.skipChildren();
+    } else {
+      Blocks.push_back(*I);
 
-  ++NumRotated;
-  return true;
+      BranchInst *BI = cast<BranchInst>((*I)->getTerminator());
+      for (unsigned B = 0, E = BI->getNumSuccessors(); B < E; ++B) {
+        BasicBlock *Succ = BI->getSuccessor(B);
+        if (!L->contains(Succ))
+          Exits.insert(Succ);
+      }
+      ++I;
+    }
+  }
+  return NewH;
 }
 
-/// 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;
+/// Rotate loop L.
+/// TODO: arrange newly inserted bbs.
+void LoopRotate::rotateLoop() {
+  BasicBlock *OrigH = L->getHeader();
+  BasicBlock *OrigLatch = L->getLoopLatch();
+  BasicBlock *OrigPH = L->getLoopPreheader();
 
-  for (BasicBlock::iterator I = Begin; I != End; ++I) {
+  DEBUG(dbgs() << "LoopRotation: rotating "; L->dump());
 
-    if (!isSafeToSpeculativelyExecute(&*I))
-      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, OrigLatch, Blocks, Exits);
+  assert(NewH);
+
+  ValueToValueMapTy VMap;
+  copySEME(Blocks, Exits, VMap, ".lr", DT, LI);
+
+  // Redirect original preheader to the entry of SEME.
+  BranchInst *PBI = dyn_cast<BranchInst>(OrigPH->getTerminator());
+  assert(PBI && (1 == PBI->getNumSuccessors()));
+
+  BasicBlock *CopyOrigH = cast<BasicBlock>(VMap[OrigH]);
+  PBI->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;
+    }
+  assert(BeforeLoop && "No entry point to the loop from New Header.");
 
-    if (isa<DbgInfoIntrinsic>(I))
+  BasicBlock *NewPH = BasicBlock::Create(NewH->getContext(),
+                                         NewH->getName() + ".lr.ph",
+                                         NewH->getParent(), BeforeLoop);
+  Loop *OuterLoop = LI->getLoopFor(OrigPH);
+  if (OuterLoop)
+    OuterLoop->addBasicBlockToLoop(NewPH, *LI);
+
+  // Move NewH physically to the beginning of the loop.
+  Function *F = BeforeLoop->getParent();
+  F->getBasicBlockList().splice(OrigH->getIterator(), F->getBasicBlockList(),
+                                  NewH);
+  // 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());
+
+  for (BasicBlock *BB : Blocks) {
+    typedef DomTreeNodeBase<BasicBlock> DTNode;
+    DTNode *IDom = DT->getNode(BB);
+    std::vector<DTNode*>::iterator I = IDom->begin();
+    for (; I != IDom->end();) {
+      BasicBlock *ExitBB = (*I)->getBlock();
+      if (L->contains(ExitBB)) {
+        ++I;
         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
-    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;
-        }
       }
 
-      if (seenIncrement)
-        return false;
-      seenIncrement = true;
-      break;
+      BasicBlock *StaleIDom = DT->getNode(ExitBB)->getIDom()->getBlock();
+      //assert (BB == StaleIDom);
+      BasicBlock *NewBB = cast<BasicBlock>(VMap[BB]);
+      // VERIFY: NewIDom will be 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 = IDom->begin();
+      } else
+        ++I;
     }
-    case Instruction::Trunc:
-    case Instruction::ZExt:
-    case Instruction::SExt:
-      // ignore type conversions
-      break;
-    }
-  }
-  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");
+
+  addPhisToNewHeader(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);
+
+  LI->verify();
+  DT->verifyDomTree();
+  assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
+  DEBUG(verifyFunction(*F));
+  DEBUG(dbgs() << "\nLoopRotation: rotated "; L->dumpVerbose());
 
-  BranchInst *Jmp = dyn_cast<BranchInst>(Latch->getTerminator());
-  if (!Jmp || !Jmp->isUnconditional())
-    return false;
+  assert (isSEME(L->getHeader(), NewLatch, DT));
+  assert (isSEME(CopyOrigH, NewPH, DT));
 
-  BasicBlock *LastExit = Latch->getSinglePredecessor();
-  if (!LastExit || !L->isLoopExiting(LastExit))
-    return false;
+  ++NumRotated;
+}
 
-  BranchInst *BI = dyn_cast<BranchInst>(LastExit->getTerminator());
-  if (!BI)
+/// Rotate \c L, and return true if any modification was made.
+bool LoopRotate::processLoop() {
+  if (!isLegalToRotate())
     return false;
 
-  if (!shouldSpeculateInstrs(Latch->begin(), Jmp->getIterator(), L))
+  if (!isProfitableToRotate())
     return false;
 
-  DEBUG(dbgs() << "Folding loop latch " << Latch->getName() << " into "
-               << LastExit->getName() << "\n");
-
-  // 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;
+  if (MaxLoopsRotated != -1) {
+    if (LoopsRotated >= MaxLoopsRotated)
+      return false;
+    ++LoopsRotated;
   }
 
-/// Rotate \c L, and return true if any modification was made.
-bool LoopRotate::processLoop(Loop *L) {
   // Save the loop metadata.
   MDNode *LoopMD = L->getLoopID();
 
-  // 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);
+  // Make sure the latch has only one successor.
+  BasicBlock *LoopLatch = L->getLoopLatch();
+  if (!LoopLatch->getSingleSuccessor()) {
+    DEBUG(dbgs() << "\nSplitting the edge of Loop:"; L->dumpVerbose(););
+    LoopLatch = SplitEdge(LoopLatch, L->getHeader(), DT, LI);
+  }
+
+  assert(LoopLatch->getSingleSuccessor());
 
-  bool MadeChange = rotateLoop(L, SimplifiedLatch);
-  assert((!MadeChange || L->isLoopExiting(L->getLoopLatch())) &&
+  // Anything ScalarEvolution may know about this loop or the PHI nodes
+  // in its header will soon be invalidated.
+  if (SE)
+    SE->forgetLoop(L);
+
+  rotateLoop();
+  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)
     L->setLoopID(LoopMD);
 
-  return MadeChange;
+  return true;
 }
 
 LoopRotatePass::LoopRotatePass() {}
 
 PreservedAnalyses LoopRotatePass::run(Loop &L, AnalysisManager<Loop> &AM) {
   auto &FAM = AM.getResult<FunctionAnalysisManagerLoopProxy>(L).getManager();
   Function *F = L.getHeader()->getParent();
 
   auto *LI = FAM.getCachedResult<LoopAnalysis>(*F);
   const auto *TTI = FAM.getCachedResult<TargetIRAnalysis>(*F);
   auto *AC = FAM.getCachedResult<AssumptionAnalysis>(*F);
   assert((LI && TTI && AC) && "Analyses for loop rotation not available");
 
   // Optional analyses.
   auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(*F);
   auto *SE = FAM.getCachedResult<ScalarEvolutionAnalysis>(*F);
-  LoopRotate LR(DefaultRotationThreshold, LI, TTI, AC, DT, SE);
+  LoopRotate LR(RotationMaxHeaderSize, LI, TTI, AC, DT, 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) {
     initializeLoopRotateLegacyPassPass(*PassRegistry::getPassRegistry());
     if (SpecifiedMaxHeaderSize == -1)
-      MaxHeaderSize = DefaultRotationThreshold;
+      MaxHeaderSize = RotationMaxHeaderSize;
     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(MaxHeaderSize, 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);
 }

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.preheader
+; 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
+; RUN: opt < %s -basicaa -globalopt -instcombine -loop-rotate -licm -simplifycfg -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

llvm/test/Transforms/LoopRotate/alloca.ll

 ; RUN: opt < %s -loop-rotate -S | FileCheck %s
 
 ; Test alloca in -loop-rotate.
 
 ; We expect a different value for %ptr each iteration (according to the
 ; definition of alloca). I.e. each @use must be paired with an alloca.
 
-; CHECK: call void @use(i8* %
-; CHECK: %ptr = alloca i8
+; CHECK: alloca i8
+; CHECK: call void @use
+; CHECK: alloca i8
 
 @e = global i16 10
 
 declare void @use(i8*)
 
 define void @test() {
 entry:
   %end = load i16, i16* @e
   br label %loop

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/indirectbr-1.ll

+; RUN: opt -S < %s -loop-rotate -verify-dom-info -verify-loop-info | FileCheck %s
+; ModuleID = 'ind.c'
+source_filename = "ind.c"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+; Check that the loop-latch with indirect branch is not rotated.
+; CHECK-NOT: {{.*}}.lr
+; CHECK-NOT: {{.*}}.lr.ph
+
+@f.x = internal global [3 x i8*] [i8* blockaddress(@f, %F), i8* blockaddress(@f, %G), i8* blockaddress(@f, %H)], align 16
+
+; Function Attrs: nounwind uwtable
+define i32 @f(i32 %i, i32 %j, i32 %k) #0 {
+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 @z(...) #1
+
+declare i32 @g(...) #1
+
+declare i32 @h(...) #1
+
+attributes #0 = { nounwind uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 3.9.0 "}

llvm/test/Transforms/LoopRotate/loop-rotate-0.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 the loop is rotated.
+
+; CHECK: for.cond.lr:                                      ; preds = %entry
+; CHECK: %first.0.lr = phi i32 [ 1, %entry ]
+; CHECK: if.end.lr:                                        ; preds = %for.cond.lr
+; CHECK: if.end75.lr:                                      ; preds = %if.end.lr
+; CHECK: if.end94.lr.ph:                                   ; preds = %if.end75.lr
+
+define i32 @a2i_ASN1_ENUMERATED() {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %if.end94, %entry
+  %first.0 = phi i32 [ 1, %entry ], [ 0, %if.end94 ]
+  br i1 undef, label %err_sl, label %if.end
+
+if.end:                                           ; preds = %for.cond
+  br i1 undef, label %err_sl, label %if.end75
+
+if.end75:                                         ; preds = %if.end
+  br i1 undef, label %if.end94, label %if.then93
+
+if.then93:                                        ; preds = %if.end75
+  ret i32 0
+
+if.end94:                                         ; preds = %if.end75
+  %call179 = tail call i32 @gets()
+  br label %for.cond
+
+err_sl:                                           ; preds = %if.end, %for.cond
+  unreachable
+}
+
+declare i32 @gets()

llvm/test/Transforms/LoopRotate/loop-rotate-1.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 the loop is rotated.
+; CHECK: while.cond.lr:                                    ; preds = %entry
+; CHECK: while.body.lr.ph:                                 ; preds = %while.cond.lr
+
+%fp = type { i64 }
+
+declare void @foo(%fp* %this, %fp* %that)
+
+define void @bar(%fp* %__begin1, %fp* %__end1, %fp** %__end2) {
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %while.body, %entry
+  %__end1.addr.0 = phi %fp* [ %__end1, %entry ], [ %incdec.ptr, %while.body ]
+  %cmp = icmp eq %fp* %__end1.addr.0, %__begin1
+  br i1 %cmp, label %while.end, label %while.body
+
+while.body:                                       ; preds = %while.cond
+  %0 = load %fp*, %fp** %__end2, align 8
+  %add.ptr = getelementptr inbounds %fp, %fp* %0, i64 -1
+  %incdec.ptr = getelementptr inbounds %fp, %fp* %__end1.addr.0, i64 -1
+  tail call void @foo(%fp* %add.ptr, %fp* %incdec.ptr)
+  %1 = load %fp*, %fp** %__end2, align 8
+  %incdec.ptr2 = getelementptr inbounds %fp, %fp* %1, i64 -1
+  store %fp* %incdec.ptr2, %fp** %__end2, align 8
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  ret void
+}

llvm/test/Transforms/LoopRotate/loop-rotate-10.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 the loop is rotated.
+; CHECK-LABEL: bar
+; CHECK: for.cond.lr:                                      ; preds = %entry
+; CHECK: if.end.lr:                                        ; preds = %for.cond.lr
+; CHECK: if.end75.lr:                                      ; preds = %if.end.lr
+; CHECK: if.end94.lr:                                      ; preds = %if.end75.lr
+; CHECK: if.then178.lr.ph:                                 ; preds = %if.end94.lr
+
+declare i32 @foo()
+define i32 @bar() {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %if.then178, %entry
+  %first.0 = phi i32 [ 1, %entry ], [ 0, %if.then178 ]
+  br i1 undef, label %err_sl, label %if.end
+
+if.end:                                           ; preds = %for.cond
+  br i1 undef, label %err_sl, label %if.end75
+
+if.end75:                                         ; preds = %if.end
+  br i1 undef, label %if.end94, label %if.then93
+
+if.then93:                                        ; preds = %if.end75
+  unreachable
+
+if.end94:                                         ; preds = %if.end75
+  br i1 undef, label %if.then178, label %for.end182
+
+if.then178:                                       ; preds = %if.end94
+  %call179 = tail call i32 @foo()
+  br label %for.cond
+
+for.end182:                                       ; preds = %if.end94
+  ret i32 1
+
+err_sl:                                           ; preds = %if.end, %for.cond
+  unreachable
+}

llvm/test/Transforms/LoopRotate/loop-rotate-2.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 the loop is rotated.
+; CHECK-LABEL: bar
+; CHECK: bb4.lr:                                           ; preds = %bb
+; CHECK: bb6.lr.ph:                                        ; preds = %bb4.lr
+; CHECK: bb6:                                              ; preds = %bb6.lr.ph, %bb4
+; CHECK: bb4:                                              ; preds = %bb6
+; CHECK: bb12:                                             ; preds = %bb4.lr, %bb4
+
+%0 = type { i64, i64, i8* }
+%1 = type { i8 }
+
+declare void @foo(%0*, %0*)
+
+define linkonce_odr void @bar(%1* %arg, %0* %arg1, %0* %arg2, %0** %arg3) {
+bb:
+  br label %bb4
+
+bb4:                                              ; preds = %bb6, %bb
+  %tmp = phi %0* [ %arg2, %bb ], [ %tmp9, %bb6 ]
+  %tmp5 = icmp eq %0* %tmp, %arg1
+  br i1 %tmp5, label %bb12, label %bb6
+
+bb6:                                              ; preds = %bb4
+  %tmp7 = load %0*, %0** %arg3, align 8
+  %tmp8 = getelementptr inbounds %0, %0* %tmp7, i64 -1
+  %tmp9 = getelementptr inbounds %0, %0* %tmp, i64 -1
+  tail call void @foo(%0* %tmp8, %0* nonnull dereferenceable(24) %tmp9)
+  %tmp10 = load %0*, %0** %arg3, align 8
+  %tmp11 = getelementptr inbounds %0, %0* %tmp10, i64 -1
+  store %0* %tmp11, %0** %arg3, align 8
+  br label %bb4
+
+bb12:                                             ; preds = %bb4
+  ret void
+}

llvm/test/Transforms/LoopRotate/loop-rotate-3.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 the loop is rotated.
+; CHECK: do.body.i10.lr:                                   ; preds = %if.else.i3
+; CHECK: do.cond.i19.lr.ph:                                ; preds = %do.body.i10.lr
+
+define void @foo() {
+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
+}

llvm/test/Transforms/LoopRotate/loop-rotate-4.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 the loop is rotated.
+; CHECK-LABEL: foo
+; CHECK: while.cond.lr:                                    ; preds = %entry
+; CHECK: if.end6.lr:                                       ; preds = %while.cond.lr
+; CHECK: if.else.lr:                                       ; preds = %if.end6.lr
+; CHECK: if.end2.i.lr:                                     ; preds = %if.else.lr
+; CHECK: if.end37.lr:                                      ; preds = %if.end2.i.lr
+; CHECK: if.else96.lr:                                     ; preds = %if.end37.lr
+; CHECK: if.else106.lr.ph:                                 ; preds = %if.else96.lr
+
+define i32 @foo() {
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %if.then467, %entry
+  br i1 undef, label %if.then, label %if.end6
+
+if.then:                                          ; preds = %while.cond
+  unreachable
+
+if.end6:                                          ; preds = %while.cond
+  %conv7 = ashr exact i64 undef, 32
+  br i1 undef, label %if.else, label %if.then19
+
+if.then19:                                        ; preds = %if.end6
+  unreachable
+
+if.else:                                          ; preds = %if.end6
+  br i1 undef, label %thr, label %if.end2.i
+
+if.end2.i:                                        ; preds = %if.else
+  br i1 undef, label %thr, label %if.end37
+
+thr:                      ; preds = %if.end2.i, %if.else
+  unreachable
+
+if.end37:                                         ; preds = %if.end2.i
+  br i1 undef, label %if.else96, label %if.then40
+
+if.then40:                                        ; preds = %if.end37
+  unreachable
+
+if.else96:                                        ; preds = %if.end37
+  br i1 undef, label %if.else106, label %if.then99
+
+if.then99:                                        ; preds = %if.else96
+  unreachable
+
+if.else106:                                       ; preds = %if.else96
+  switch i32 undef, label %if.else427 [
+    i32 26, label %if.then130
+    i32 24, label %if.then130
+    i32 23, label %if.then130
+    i32 22, label %if.then130
+    i32 20, label %if.then130
+    i32 19, label %if.then130
+    i32 18, label %if.then130
+    i32 12, label %if.then130
+    i32 6, label %if.then149
+    i32 1, label %if.then172
+    i32 30, label %if.then467
+    i32 4, label %if.then193
+    i32 2, label %if.then310
+    i32 10, label %if.then369
+  ]
+
+if.then130:                                       ; preds = %if.else106, %if.else106, %if.else106, %if.else106, %if.else106, %if.else106, %if.else106, %if.else106
+  br i1 undef, label %land.lhs.true138, label %if.then467
+
+land.lhs.true138:                                 ; preds = %if.then130
+  unreachable
+
+if.then149:                                       ; preds = %if.else106
+  %add151 = add nsw i64 undef, %conv7
+  unreachable
+
+if.then172:                                       ; preds = %if.else106
+  unreachable
+
+if.then193:                                       ; preds = %if.else106
+  unreachable
+
+if.then310:                                       ; preds = %if.else106
+  unreachable
+
+if.then369:                                       ; preds = %if.else106
+  unreachable
+
+if.else427:                                       ; preds = %if.else106
+  unreachable
+
+if.then467:                                       ; preds = %if.then130, %if.else106
+  br label %while.cond
+}

llvm/test/Transforms/LoopRotate/loop-rotate-5.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 the loop is rotated.
+; CHECK-LABEL: foo
+; CHECK: bb3.lr:                                           ; preds = %bb
+; CHECK: bb5.lr:                                           ; preds = %bb3.lr
+; CHECK: bb8.lr.ph:                                        ; preds = %bb5.lr
+
+define void @foo(i8* %arg, i8* %arg1, i64 %arg2) {
+bb:
+  %tmp = and i32 undef, 7
+  br label %bb3
+
+bb3:                                              ; preds = %bb8, %bb
+  %tmp4 = phi i32 [ 0, %bb8 ], [ %tmp, %bb ]
+  br i1 undef, label %bb9, label %bb5
+
+bb5:                                              ; preds = %bb3
+  %tmp6 = sub nsw i32 8, %tmp4
+  br i1 undef, label %bb7, label %bb8
+
+bb7:                                              ; preds = %bb5
+  unreachable
+
+bb8:                                              ; preds = %bb5
+  store i32 undef, i32* undef, align 8
+  br label %bb3
+
+bb9:                                              ; preds = %bb3
+  ret void
+}

llvm/test/Transforms/LoopRotate/loop-rotate-6.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 the loop is rotated.
+; CHECK-LABEL: bar
+; 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 @foo(i8*, i32)
+
+define i32 @bar(i8* %arg, i32 %arg1, i8* %arg2, i32 %arg3) {
+bb:
+  switch i32 %arg3, label %bb5 [
+    i32 0, label %bb23
+    i32 -1, label %bb4
+  ]
+
+bb4:                                              ; preds = %bb
+  unreachable
+
+bb5:                                              ; preds = %bb
+  br i1 undef, label %bb6, label %bb7
+
+bb6:                                              ; preds = %bb5
+  br i1 undef, label %bb8, label %bb9
+
+bb7:                                              ; preds = %bb5
+  unreachable
+
+bb8:                                              ; preds = %bb6
+  unreachable
+
+bb9:                                              ; preds = %bb6
+  br i1 undef, label %bb22, label %bb10
+
+bb10:                                             ; preds = %bb9
+  switch i32 undef, label %bb11 [
+    i32 46, label %bb19
+    i32 32, label %bb19
+  ]
+
+bb11:                                             ; preds = %bb10
+  unreachable
+
+bb12:                                             ; preds = %bb19
+  switch i8 undef, label %bb13 [
+    i8 32, label %bb21
+    i8 46, label %bb21
+  ]
+
+bb13:                                             ; preds = %bb12
+  br i1 undef, label %bb14, label %bb15
+
+bb14:                                             ; preds = %bb13
+  unreachable
+
+bb15:                                             ; preds = %bb13
+  br i1 undef, label %bb17, label %bb16
+
+bb16:                                             ; preds = %bb15
+  %tmp = call i32 @foo(i8* %tmp20, i32 10)
+  unreachable
+
+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
+  unreachable
+
+bb22:                                             ; preds = %bb9
+  unreachable
+
+bb23:                                             ; preds = %bb
+  ret i32 0
+}

llvm/test/Transforms/LoopRotate/loop-rotate-7.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 the loop is rotated.
+; CHECK-LABEL: bar
+; CHECK: for.cond65.preheader:                             ; preds = %entry
+; CHECK: for.cond65.lr:                                    ; preds = %for.cond65.preheader
+; CHECK: for.body68.lr.ph:                                 ; preds = %for.cond65.lr
+
+define i32 @bar() {
+entry:
+  br i1 undef, label %return, label %for.cond65
+
+for.cond65:                                       ; preds = %entry, %for.body68
+  %n.0.pn = phi i8* [ %n.1, %for.body68 ], [ undef, %entry ]
+  %n.1 = getelementptr inbounds i8, i8* %n.0.pn, i64 -1
+  br i1 undef, label %for.body68, label %return
+
+for.body68:                                       ; preds = %for.cond65
+  %xor71 = xor i8 undef, -1
+  br label %for.cond65
+
+return:                                           ; preds = %for.cond65, %entry
+  ret i32 undef
+}

llvm/test/Transforms/LoopRotate/loop-rotate-8.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"
+
+declare i8* @foo()
+
+; Check that the loop is rotated.
+; CHECK-LABEL: bar
+; CHECK: for.cond.preheader:                               ; preds = %if.end
+; 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
+
+define void @bar() #1 {
+entry:
+  br i1 undef, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  unreachable
+
+if.end:                                           ; preds = %entry
+  br i1 undef, label %return, label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %if.end
+  br i1 undef, label %for.body, label %return
+
+for.body:                                         ; preds = %for.cond
+  %call15 = call i8* @foo()
+  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 %for.body.i, label %for.inc
+
+for.body.i:                                       ; preds = %for.cond.i
+  unreachable
+
+crl:                    ; preds = %if.then.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
+}

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

+; RUN: opt -S < %s -loop-rotate -verify-dom-info -verify-loop-info | FileCheck %s
+; ModuleID = 'bugpoint-reduced-instructions.bc'
+source_filename = "bugpoint-output-cebc3aa.bc"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Check that the loop is rotated.
+; CHECK-LABEL: bar
+; CHECK: while.cond.preheader:                             ; preds = %if.end92
+; CHECK: while.cond.lr:                                    ; preds = %while.cond.preheader
+; CHECK: if.end107.lr.ph:                                  ; preds = %while.cond.lr
+
+; Function Attrs: nounwind uwtable
+define i32 @bar() {
+entry:
+  br i1 undef, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  ret i32 -1
+
+if.end:                                           ; preds = %entry
+  br i1 undef, label %if.then39, label %if.end48
+
+if.then39:                                        ; preds = %if.end
+  unreachable
+
+if.end48:                                         ; preds = %if.end
+  br i1 undef, label %if.else61, label %if.then59
+
+if.then59:                                        ; preds = %if.end48
+  unreachable
+
+if.else61:                                        ; preds = %if.end48
+  br i1 undef, label %if.then91, label %if.end92
+
+if.then91:                                        ; preds = %if.else61
+  unreachable
+
+if.end92:                                         ; preds = %if.else61
+  br i1 undef, label %if.then96, label %while.cond
+
+if.then96:                                        ; preds = %if.end92
+  unreachable
+
+while.cond:                                       ; preds = %if.end107, %if.end92
+  %len.3 = phi i64 [ %add109, %if.end107 ], [ 0, %if.end92 ]
+  br i1 undef, label %if.then106, label %if.end107
+
+if.then106:                                       ; preds = %while.cond
+  unreachable
+
+if.end107:                                        ; preds = %while.cond
+  %add109 = add i64 undef, %len.3
+  %sub111 = sub i64 undef, undef
+  br label %while.cond
+}

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

+; RUN: opt -S -loop-rotate < %s -verify-loop-info -verify-dom-info | FileCheck %s
+; ModuleID = 'bugpoint-reduced-simplified.bc'
+source_filename = "bugpoint-output-fdebd3b.bc"
+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"
+
+; Function Attrs: nounwind readonly
+define void @test1() #0 {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond1, %entry
+  %sum.0 = phi i32 [ 0, %entry ], [ %sum.1, %for.cond1 ]
+  br i1 undef, label %for.cond1, label %return
+
+for.cond1:                                        ; preds = %land.rhs, %for.cond
+  %sum.1 = phi i32 [ 0, %land.rhs ], [ %sum.0, %for.cond ]
+  br i1 undef, label %land.rhs, label %for.cond
+
+land.rhs:                                         ; preds = %for.cond1
+  br i1 undef, label %return, label %for.cond1
+
+return:                                           ; preds = %land.rhs, %for.cond
+  %retval.0 = phi i32 [ 1000, %land.rhs ], [ %sum.0, %for.cond ]
+  ret void
+}
+
+attributes #0 = { nounwind readonly }
+
+; check that loop with multiple exit is rotated and has a preheader.
+; CHECK-LABEL: test1
+; CHECK: entry:
+; CHECK: br label %for.cond.lr
+; CHECK: for.cond.loopexit:
+; CHECK:   br label %for.cond
+; CHECK: for.cond.lr:
+; CHECK:   br i1 false, label %for.cond1.preheader.lr.ph, label %return.loopexit1
+; CHECK: for.cond1.preheader.lr.ph:
+; CHECK:   br label %for.cond1.preheader
+; CHECK: for.cond1.preheader:

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 two loops rotated.
+; CHECK-LABEL: @test1
+
+; Check that the outer loop is rotated.
+; CHECK: for.cond.lr:
+; CHECK: for.cond1.preheader.lr.ph:
+
+; Check that the inner loop is rotated.
+; CHECK: for.cond1.lr:
+; CHECK: land.rhs.lr:
+; CHECK: land.rhs.for.cond1_crit_edge.lr.ph:
+
 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
   %add = add i32 %0, %sum.1
   %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
 }
 
 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 ]

 return.loopexit:                                  ; preds = %for.cond
   br label %return
 
 return:                                           ; preds = %return.loopexit, %a
   ret void
 
 ; 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: %inc = add i32 %phi.nh, 1
+; CHECK: %cmp = icmp eq i32 %i.0, %x
+; CHECK: br i1 %cmp, label %return.loopexit, label %for.body
 }
 
 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: %incdec.ptr.i = getelementptr
+;CHECK: 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:  %phi.nh3 = phi i64
+; CHECK:  %phi.nh2 = phi i64
+; CHECK:  %phi.nh1 = phi i64
+; CHECK:  %phi.nh = phi i64
+; 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/pr7447.ll

+; REQUIRES: asserts
+; RUN: opt < %s -loop-rotate -stats 2>&1 | FileCheck %s
+
+; PR7447: there should be two loops rotated.
+; CHECK: 2 loop-rotate
+
+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
+
+for.cond1:                                        ; preds = %for.cond, %land.rhs
+  %sum.1 = phi i32 [ %add, %land.rhs ], [ %sum.0, %for.cond ]
+  %i.1 = phi i32 [ %inc, %land.rhs ], [ 0, %for.cond ]
+  %cmp2 = icmp ult i32 %i.1, 100
+  br i1 %cmp2, label %land.rhs, label %for.cond
+
+land.rhs:                                         ; preds = %for.cond1
+  %conv = zext i32 %i.1 to i64
+  %arrayidx = getelementptr inbounds [100 x i32], [100 x i32]* %a, i64 0, i64 %conv
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add i32 %0, %sum.1
+  %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
+}

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

 ; 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-NEXT: br i1 {{[^,]*}}, label %return, label %inner.body
 
 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
 
 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: [[OUTER_LATCH_LOOPEXIT]]:
 ; 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 that loop with multiple exits is rotated.
 ; CHECK-LABEL: @f(
-; CHECK-NOT: bb:
+; 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]
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
+;CHECK-LABEL: @foo(
+;CHECK: for.body.lr:
+;CHECK: %arrayidx.lr = getelementptr inbounds i8, i8* %CurPtr, i64 %idxprom.lr
+;CHECK: %0 = load i8, i8* %arrayidx.lr, align 1
+;CHECK: %conv.lr = sext i8 %0 to i32
+;CHECK: %arrayidx1.lr = getelementptr inbounds i8, i8* %CurPtr, i64 0
+;CHECK: %1 = load i8, i8* %arrayidx1.lr, align 1
+;CHECK: %conv2.lr = sext i8 %1 to i32
+;CHECK: for.body:
+;CHECK: %arrayidx = getelementptr inbounds i8, i8* %CurPtr, i64 %idxprom
+;CHECK: %2 = load i8, i8* %arrayidx, align 1
+;CHECK: %conv = sext i8 %2 to i32
+;CHECK: %3 = load i8, i8* %arrayidx1, align 1
+;CHECK: %conv2 = sext i8 %3 to i32
+;CHECK: br i1 %cmp3, label %return, label %for.inc
 
 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

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
+; checking the stats for the function @nonrotated
+; CHECK: 2 gvn{{.*}}Number of equalities propagated
+; With the new loop rotation both the loops should be rotated.
+; CHECK: 2 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"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; 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];