Codegen: Tail-duplicate during placement.

[iteratee]

Summary

The tail duplication pass uses an assumed layout when making duplication
decisions. This is fine, but passes up duplication opportunities that
may arise when blocks are outlined. This change allows duplication after
layout decisions. Because we want the updated CFG to affect subsequent
placement decisions, duplication must occur during placement.

In order to achieve this goal, TailDuplicationPass is split into a
utility class, TailDuplicator, and the pass itself. The pass delegates
nearly everything to the TailDuplicator object, except for looping over
the blocks in a function. This allows the same code to be used for tail
duplication in both places.

This change, in concert with outlining optional branches, allows
triangle shaped code to perform much better, esepecially when the
taken/untaken branches are correlated, as it creates a second spine when
the tests are small enough.

[iteratee]

Add a test and a fix for duplicating blocks that have un-analyzable fallthrough.
Note that the test doesn't currently fail, but D20505 will fail without the fix.

[iteratee]

Are there any other concerns with this patch other than performance and size numbers from Quentin?

[iteratee]

This comment was removed by iteratee.

[qcolombet]

Hi Kyle,

The performance results pretty look good so far! (Up to 4% improvement on some SPEC!)
Go ahead with the commit, we will adjust if things turn out to be bad for other workload, but I do not think it will happen.

The only actionable regression on your end is SingleSource/Benchmarks/Misc/ReedSolomon, which regressed by ~4% on x86_64 -O3. Other than that, this is a net win or the regression are within the noise!

Cheers,
-Quentin

[iteratee]

Modified to work with tail-merging during layout.
Had to make tail-merging during layout less agressive so that it wouldn't undo tail-duplication.

[iteratee]

clean up some spurious debugging.

[echristo]

Couple of inline comments. I think some of the overall design can be separated out and be made a bit simpler - especially as relates to ForcedLayoutPred etc, but we can worry about that as a cleanup that'll happen next.

Thanks!

-eric

lib/CodeGen/BranchFolding.cpp

641 ↗

(On Diff #62154)

Can you elaborate here? Perhaps with a FIXME or a TODO.

lib/CodeGen/MachineBlockPlacement.cpp

1696 ↗

(On Diff #62154)

The MachineFunction has an MMI so you don't need this argument. :)

[davidxl]

test/CodeGen/PowerPC/tail-dup-analyzable-fallthrough.ll

5 ↗

(On Diff #62154)

Please simplify this test case and document what is the expected layout with tailDup. The test as it stands now is hard to read.

test/CodeGen/PowerPC/tail-dup-layout.ll

2 ↗

(On Diff #62154)

Same here : simplify the test case and document the expected output with description.

[iteratee]

Added comments to tests to try and make them more readable

[iteratee]

Added comment explaining why tail-merging can't use the unconditional branch heuristic when it is run during layout.

[iteratee]

lib/CodeGen/BranchFolding.cpp

641 ↗

(On Diff #62517)

I don't think that there is a way to fix it. The heuristic overcounts fractional tails where one block would end up with a jump, but another would not. It's probably fine to use it early, but during layout we have to be stricter about the thresholds.

test/CodeGen/PowerPC/tail-dup-analyzable-fallthrough.ll

5 ↗

(On Diff #62154)

This test was reduced from an actual regression that I introduced and then fixed.

I've added comments to explain what went wrong.

test/CodeGen/PowerPC/tail-dup-layout.ll

2 ↗

(On Diff #62154)

I don't see that this test is that complex at all, except for the optional bodies. Unfortunately, they have to a certain size or they won't get outlined. I've added an easier to read expectation of layout, and a description of what the CHECK lines are looking for.

[iteratee]

Fixed the last 2 tests.
One was minor,
For the WebAssembly test, I just disabled tail-duplication during placement, as previously instructed.

[davidxl]

test/CodeGen/PowerPC/tail-dup-analyzable-fallthrough.ll

6 ↗

(On Diff #62531)

Kyle, thanks.

I think it is better get a minimal reproducible and use that as test case. for instance, I am not sure if the struct HashBucket etc and some other things are relevant here -- they are all distractions. I have pointed to an example of the minimalist test case.

test/CodeGen/PowerPC/tail-dup-layout.ll

3 ↗

(On Diff #62531)

The test case should be as simple as possible and remove all irrelevant pieces.

Regarding the size limit, you can use "outline-optional-threshold", option to specify a lower limit so that you can reduce the size of the optional body.

52 ↗

(On Diff #62531)

An example of a simple clean test case:

CodeGen/X86/code_placement_outline_optional_branches.ll

[iteratee]

Simplify test cases.

[iteratee]

Please take a look at the tests again.

test/CodeGen/PowerPC/tail-dup-analyzable-fallthrough.ll

7 ↗

(On Diff #62551)

I simplified the code quite a bit. The essence of what was happening was a linked-list walk was getting miscompiled, so I shrunk it to that.

test/CodeGen/PowerPC/tail-dup-layout.ll

4 ↗

(On Diff #62551)

OK, I made it look more like the other test that you pointed too, with repeated calls for bodies.

[davidxl]

Very nice. I like the patch a lot! I will go though it one more time shortly.

thanks,

David

[davidxl]

lib/CodeGen/BranchFolding.cpp

595 ↗

(On Diff #62551)

Since you are here, please document arguments to this method: MBB1, MBB2, PredBB, SuccBB, AfterPlacement.

624 ↗

(On Diff #62551)

Expand the comment a little more: TailMerging invoked after block placement. Do not undo ...

648 ↗

(On Diff #62551)

Is there a better way to identify Pred BBs which are tailduplicated into during block placement? Looks to me we should avoid undoing any taildups done in layout stage.

lib/CodeGen/TailDuplicator.cpp

512 ↗

(On Diff #62551)

Document new parameters. While you are here, document IsSimple as well.

741 ↗

(On Diff #62551)

Same here -- document parameter.

847 ↗

(On Diff #62551)

Are there other places in taildup where blocks may get removed? It seems to me that tailDupllicator needs to have member to remember it is in 'layout' state, and the block deletor code should check that flag instead.

[iteratee]

Added comments, simplified flags to tail-duplicator

lib/CodeGen/BranchFolding.cpp

648 ↗

(On Diff #62551)

While we could pass a set of blocks around, the thresholds don't overlap by default. e.g. We tail-duplicate blocks of 2 instructions or fewer, and tail-merge blocks of 3 instructions or more. The problem is with fractional overlap. e.g. a block of 2 instructions was duplicated and in one of the resulting block an additional branch had to be added.

Would you prefer that I create a set of blocks and pass them into the branch optimizer? It would make it faster to skip those blocks altogether.

lib/CodeGen/TailDuplicator.cpp

512 ↗

(On Diff #62551)

New parameter removed.

847 ↗

(On Diff #62551)

No, nowhere else that blocks may get removed, and ultimately I want to not have different modes.

I decided that for duplication during layout, it doesn't make sense to try to delete the block. I've updated the code accordingly, and will fix D20505 to match.

[davidxl]

lib/CodeGen/BranchFolding.cpp

656 ↗

(On Diff #62995)

Depending on the threshold difference can be fragile.

How about changing AfterPlacement into a callback/lambda function using function_ref<..>. It tells tailMerge if a block should be skipped.

[iteratee]

Took a more principled stand on when to tail merge and when not to, so that tail-duplicating and tail merging now don't overlap.

[davidxl]

lib/CodeGen/BranchFolding.cpp

608 ↗

(On Diff #63585)

I think it is cleaner to check at the beginning if anyone of MBB1 or MBB2 need to be skipped (either be the taildupped block or a block tail-dupped into), and return false if so. The set of skipped blocks can be passed into the BF by block placement.

629 ↗

(On Diff #63585)

Is this change related?

lib/CodeGen/TailDuplicator.cpp

519 ↗

(On Diff #63585)

Expand the comments a little more.

835 ↗

(On Diff #63585)

nit: block placement does not expect any blocks to be deleted.

[iteratee]

lib/CodeGen/BranchFolding.cpp

633 ↗

(On Diff #63585)

I changed this heuristic to avoid undoing valuable duplication. In fact, some of the cases where it doesn't merge are cases where we wanted to tail duplicate, but couldn't. See Hexagon/rdf-copy.ll

I'll split the changes here out into a separate patch.

656 ↗

(On Diff #63585)

Discussed this with chandlerc. He thinks that passing around the list of blocks that were tail-duplicated too tightly couples the passes, and that we should strive to have non-overlap. He suggested that a list of blocks that were duplicated might be a good debug measure to make sure they aren't being re-merged.

Overall I agree with him, and I made a change so there shouldn't be any overlap.
Do you want to see the set as a debugging measure?

[iteratee]

I'll handle the 2 comment changes you asked for before I upload a new patch, but please take a look at the comments I added. I wrote them before I saw your comments, because I was thinking through some cases.

lib/CodeGen/BranchFolding.cpp

608 ↗

(On Diff #63585)

See below for the discussion about this, but I don't think passing in the set of blocks is the right choice.

629 ↗

(On Diff #63585)

Yes, but I plan to split it out into a separate patch.

[davidxl]

lib/CodeGen/BranchFolding.cpp

656 ↗

(On Diff #63585)

I don't agree. Without making it explicit, the the pass coupling does not disappear -- it is still there but in a more implicit but hard to maintain way.

For instance, can we guarantee this still work when TailMerger and TailDuplicator uses non-default size thresholds?

[chandlerc]

lib/CodeGen/BranchFolding.cpp

656 ↗

(On Diff #63585)

My thought was specifically that we should enforce an invariant that these are defined in a non-overlapping way, *and* check it in asserts builds precisely so that things like non-default size thresholds work in a sane way.

As long as there is the potential for overlap, we have the problem (IMO) that the innards of tail dup or tail merge can do things that user programs cannot. I would much prefer that we have a set of rules that are sufficiently precise and enforced that one pass doesn't have to have a back-channel to communicate to the other pass.

But I do agree that it is important that this is actually a guaranteed property and one we check that we don't violate.

[iteratee]

Use single explicit threshold between tail-dup and tail-merge during layout.
Tail-duplicate indirect branches with a larger threshold during layout (Mirrors pre reg-alloc behavior).

[iteratee]

Fix WebAssembly cfg stackify test.
Broke because we don't tail-duplicate loop latches early any more.

[iteratee]

Fixed additional tests.
Early tail-duplication now respects loops.
Explicit threshold for merging/duplication during layout.

[iteratee]

Factored out explicit threshold code.

[iteratee]

lib/CodeGen/BranchFolding.cpp

674 ↗

(On Diff #67644)

This should all be resolved now. See D23383 and D23390 for the explicit threshold. The changes to make merging not overlap during layout have already gone in.

lib/CodeGen/TailDuplicator.cpp

876 ↗

(On Diff #67644)

This is resolved by allowing the deletion to occur.

[iteratee]

Updated tests. No other changes.

[iteratee]

Quentin, can you re-run the benchmark suite? This patch has changed a fair bit since you last ran them.
If you could do D20505 as well, which depends on this, that would be awesome.

Thanks,
Kyle.

[davidxl]

include/llvm/CodeGen/TailDuplicator.h

58 ↗

(On Diff #68634)

Document the new parameters and behavior (zero default etc)

lib/CodeGen/BranchFolding.cpp

699 ↗

(On Diff #68634)

CurMPIter = HighestMPIter;

Maybe a separate cleanup patch

707 ↗

(On Diff #68634)

MBB1 can be computed in common path

709 ↗

(On Diff #68634)

On what platforms? Is there a better way to query it?

713 ↗

(On Diff #68634)

where does 21 magic number come from? Why not just define a special value to signal merging is disabled/skipped for such blocks?

lib/CodeGen/MachineBlockPlacement.cpp

139 ↗

(On Diff #68634)

This name is very confusing. Just name it as TailDupThresholdInLayout. Perhaps document that this is also used to 'force' the tail merge at the high threshold to avoid it undoing tailDup decisions.

1009 ↗

(On Diff #68634)

This makes the primary loop body too large. Outline it into its own method.

lib/CodeGen/TailDuplicator.cpp

545 ↗

(On Diff #68634)

Irrelevant change?

572 ↗

(On Diff #68634)

Irrelevant change?

575 ↗

(On Diff #68634)

Is this change needed (handled by previous taildup invocation)?

[iteratee]

Fixes from review.

[iteratee]

I have some questions, but most of the suggestions are done.

lib/CodeGen/BranchFolding.cpp

709 ↗

(On Diff #68634)

I believe ARM marks the actual return as an indirect branch.
I don't see a better way. Indirect tail-calls will likely get caught here as well.
Since what we're looking for is jump tables within the function, checking the successor size seems reasonable.
Would you like me to re-write the comment so that it seems more intentional?

713 ↗

(On Diff #68634)

It's one more than 20, from tail-duplication of the same pattern. I'm open to other suggestions as to how to make these two cooperate.

lib/CodeGen/TailDuplicator.cpp

545 ↗

(On Diff #68634)

No. With tail-duplication occurring only once, we had to duplicate those blocks when we got the chance. Now with layout-duplication we can wait and duplicate them later.

572 ↗

(On Diff #68634)

No. Because this check is only necessary if you want to expand these blocks later in layout mode.
This change is required by the previous one above, because otherwise it breaks a test.

575 ↗

(On Diff #68634)

Yes, there are tests where the loop-latch is a switch. I presume it occurs in the real world as well.

[iteratee]

lib/CodeGen/TailDuplicator.cpp

545 ↗

(On Diff #68942)

This was related to a performance regression I found. I can probably pull this out into a separate patch that gets committed at the same time. Would that be better?

[davidxl]

lib/CodeGen/TailDuplicator.cpp

545 ↗

(On Diff #68942)

Yes this should be in a different patch with different review (and test cases etc).

[iteratee]

Changes missed from previous upload

[davidxl]

lib/CodeGen/BranchFolding.cpp

709 ↗

(On Diff #68942)

How abut Block1.back().isIndirectBranch() && !Block1.back().isReturn() ?

713 ↗

(On Diff #68942)

I think this value should be passed in either via constructor or a separate API:

setMergeThresholdForBBwithIndirectBr(...).

In tailDup, the value 20 should also be controlled by an option.

lib/CodeGen/MachineBlockPlacement.cpp

1015 ↗

(On Diff #68942)

Why can't this part be folded into maybeTailDuplicateBlock? If not, the big chunk of code between if (Removed) { ..} belongs to its own method.

lib/CodeGen/TailDuplicator.cpp

572 ↗

(On Diff #68942)

I don't get it. This one looks like a heuristic change to not give block with return instruction (as indirect branch) a larger threshold for duplication, which is independent of this patch.

[iteratee]

lib/CodeGen/TailDuplicator.cpp

572 ↗

(On Diff #68942)

I'll split these out, but they're all intertwined.

1. Don't duplicate latches/pre-headers early.
2. There are now tests that fail, so duplicate switches during layout.
3. Because the indirect branch test is now post Reg-Alloc, it has to handle the actual return instructions.

[davidxl]

lib/CodeGen/TailDuplicator.cpp

572 ↗

(On Diff #69036)

thx for the expalnation. Getting Part-1 right is the key here.

[iteratee]

Removed changes as requested. They'll show up in another patch shortly.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

1023 ↗

(On Diff #69058)

BB = *std::prev(Chain.end())

1834 ↗

(On Diff #69058)

early return if not removed to reduce code nesting level

1835 ↗

(On Diff #69058)

remove 'into'

1840 ↗

(On Diff #69058)

std::prev

1844 ↗

(On Diff #69058)

This does not look right the place to update. The successors of DupBB may also get more unscheduled predecessors. The update should be done in one place where the total number of Preds (BB is dupped into) is known.

1849 ↗

(On Diff #69058)

Can you give more explanation on the iterative tailDup?

1885 ↗

(On Diff #69058)

Should an early return be done here?
if (!IsSimple && BB->succ_size() == 1) return false;
if (!TailDup.shouldTailDuplicate(...) return false;

1890 ↗

(On Diff #69058)

should also skip if Pred is in the same chain as BB (e.g, when BB is a loop head of another loop, and Pred is that loop's latch)

1893 ↗

(On Diff #69058)

Need to count the number of other Pred that BB can tail duplicate into.

If that number is zero, should return false.

1905 ↗

(On Diff #69058)

To early to do the update. Wait until the tailDup actually happens. Actually, do we really need to update? When tailDup happens, Pred will become NewSucc's new predecessor, and Pred is still not scheduled.

1910 ↗

(On Diff #69058)

Early return false when '!CanDupToChain'

1934 ↗

(On Diff #69058)

It is cleaner to use RemoveList.erase(remove_if(...)..) pattern

Also bypass if RemBB's unscheduled pred number is not zero.

[iteratee]

Simplifications from review.

[iteratee]

Applied some suggestions, answered others.

lib/CodeGen/MachineBlockPlacement.cpp

1840 ↗

(On Diff #69058)

Can't. I need to actually update the iterator so that I can check to see if there is an additional block in the chain.

1844 ↗

(On Diff #69058)

You're correct, It only needs to be done once because only one block is actually going from unscheduled to scheduled: BB.
That makes the function simpler overall and easier to understand.

1890 ↗

(On Diff #69058)

No, even if they're in the same chain, blocks that end up with both as predecessors still have an additional predecessor.

I think you're thinking of the check that I do below of NewChain vs PredChain.

1893 ↗

(On Diff #69058)

No. because although we don't have predecessors to worry about (Loop filter), there may be unfiltered predecessors that we can duplicate into, and now is the only time to do so.

1905 ↗

(On Diff #69058)

We can't do it any later. BB may disappear after tail duplication.

I could make tail duplication return a vector of blocks that were duplicated into, and save the successor list before duplication.
That may be easier to follow, but wouldn't be any more correct.

Yes, we need to update. For each duplication the successors now have an additional unscheduled predecessor

1910 ↗

(On Diff #69058)

That would be incorrect. There are plenty of cases where we can't duplicate into the layout predecessor where we still want to perform tail duplication.

[iteratee]

Remove unused variable.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

1893 ↗

(On Diff #69176)

It is not correct to do. BB and Pred are in the same nested loop that already been laid out. You can not duplicate BB into Pred here.

LPred

|
|

BB <-----

|               \
..                 \
Pred              |
 \__________|

1905 ↗

(On Diff #69176)

I think a list of Preds that BB can be duplicated into need to be passed in.

The reason doing update here is not bullet proof is that if later if there are other heuristic to decide not to tailDup, then the early update will be wrong. It needs to be tied to the actual transformation

1910 ↗

(On Diff #69176)

There are two problems here

1. many Pred (other than LPred) has been skipped as illegal candidates, but tailDupiicator does not know about will happily do tailDup -- as the tailDuplicator does not know about the new constraints from MBP
2. if the total number of candidate predecessors that BB can tailDuped into is fewer than 2, there is no point do the tail duplication

[iteratee]

lib/CodeGen/MachineBlockPlacement.cpp

1893 ↗

(On Diff #69176)

I don't see why not. There's not a correctness issue, and if BB was the loop top of the inner loop, it was never considered to be duplicated. Now is the chance that we have to do it.

1905 ↗

(On Diff #69176)

The goal of this loop is not to find constraints.

I agree it would be cleaner to get the list out of tail-duplication. I'll do that.

1910 ↗

(On Diff #69176)

I think you misunderstand the point of this loop. The point is not to find "legal candidates", but to find the candidates for which duplicating will require update.

Because of that, we don't have an accurate count, and don't want one. We'll gladly let tailDuplicator do its job.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

1849 ↗

(On Diff #69176)

This one needs a test case to cover.

1910 ↗

(On Diff #69176)

Ok.

Do you see the possibility that some Pred simply can not be selected as dup target bb (for legality or performance reasons)? Overall, the code should be organizied in the way that the list of BBs that MBP thinks it can/should be tailDup should match the actual transformations.

[iteratee]

lib/CodeGen/MachineBlockPlacement.cpp

1910 ↗

(On Diff #69176)

I can see that we might want to limit the set of predecessors duplicate to. A good case would be to filter out predecessors that are too cold.

The performance results have been reasonable so far without that change, and It would certainly make this more complicated.
For now, I think it would be best to simply go with the cleaner version of getting a list of blocks back from tailDuplicateAndUpdate.

This will make it easy to add filters later, and to add them inside of tailDuplicator as well without worrying about breaking this loop.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

1910 ↗

(On Diff #69176)

I am fine with unfiltered solution for now -- but the code structure should make future tuning easy to do :)

[iteratee]

Update unscheduled predecessors after tail duplication.

[iteratee]

Changes missed in previous patch. Get list of duplicated predecessors from TailDuplicator and use that list to update unscheduled predecessors.

[iteratee]

Remove extra debugging.

[iteratee]

lib/CodeGen/BranchFolding.cpp

709 ↗

(On Diff #68942)

I checked. There are platforms where the "return" instruction does not return true for isReturn after epilog lowering.
Mips, Hexagon, Thumb.

I think I'll re-write the comment so that it sounds less like a workaround.

[iteratee]

Add test case for repeated tail-duplication.

[davidxl]

test/CodeGen/X86/tail-dup-repeat.ll

7 ↗

(On Diff #69762)

Can this function's declaration be simplified? If the parameters are not necessary, remove them

11 ↗

(On Diff #69762)

Clean up the parameters (shorten names etc)). Remove unnecessary attribute

15 ↗

(On Diff #69762)

Please also clean up variable names and label names.

For label names, make them more meaningful. For instance, if a block is duplicated, the label for the block can be 'dup:'. For iterative tail dup, also name them in sequence numbers dup1, dup2 etc. Others can be cleaned up suchas header, loopexit etc.

Some simple comments in the test case (where tail dup happens) is also helpful.

[iteratee]

Found new, shorter test case for repeated tail duplication.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

1862 ↗

(On Diff #71247)

Is this comment correct? The TailBB may be dup'ed in to Lpred, but still not removed as there are some other predecessors it can not be dup'ed into ?

1951 ↗

(On Diff #71247)

Should DuplicatedToLPred == CanDupToChain?

[iteratee]

Simplified computation of whether a block was duplicated to the layout pred.

lib/CodeGen/MachineBlockPlacement.cpp

1862 ↗

(On Diff #71247)

It is currently correct.
The tail duplication code only copies the block into the layout predecessor if it can be copied into all other predecessors as well.

1951 ↗

(On Diff #71247)

Even better, since we now return the list of predecessors that received a copy of BB, we should check to see if LPred is in that list. Basically free since we loop over the list anyway.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

1013 ↗

(On Diff #71274)

The update of BB should be wrapped into 'repeatedlyTailDuplicateBlock'.

1826 ↗

(On Diff #71274)

Missing coma. ".. it was removed, markChainSuccessors .."

1836 ↗

(On Diff #71274)

Add a comment here that Chain End is updated when DupBB is removed by the removal call back.

There also seem to be a bug here: if TailDup happens, but DupBB is not removed, the loop will check the same BB again. Should it just break the loop when removed is not true?

1863 ↗

(On Diff #71274)

It is cleaner to make this interface return bool (either Removed or DuplicatedToLPred)

[iteratee]

Added comments.

Made changes from review:
Chain end is now updated in repeatedlyTailDuplicateBlock
MaybeTailDuplicate now returns Removed instead of using out parameter.

[iteratee]

Please take a look. I cleaned up the issues you pointed out and added comments.

lib/CodeGen/MachineBlockPlacement.cpp

1826 ↗

(On Diff #71274)

I split the sentence into 2 and then added a comma. It's easier to read now.

1836 ↗

(On Diff #71274)

I added some comments.

Currently, duplication to layout predecessor only occurs if the block is removed. I added a comment about that as well.

[davidxl]

lgtm.

This is large change so it bounds to run into some corner case issues. Please test thoroughly and watch for any fallouts.

lib/CodeGen/MachineBlockPlacement.cpp

1848 ↗

(On Diff #73330)

Add an assert that Removed is true when DuplicatedToLPred is true

llvm/trunk/include/llvm/CodeGen/TailDuplicator.h

 // This file defines the TailDuplicator class. Used by the
 // TailDuplication pass, and MachineBlockPlacement.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_TAILDUPLICATOR_H
 #define LLVM_CODEGEN_TAILDUPLICATOR_H
 
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/MachineSSAUpdater.h"
 #include "llvm/CodeGen/RegisterScavenging.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 
 namespace llvm {
 
 extern cl::opt<unsigned> TailDupIndirectBranchSize;
 
 /// Utility class to perform tail duplication.
 class TailDuplicator {
   const TargetInstrInfo *TII;
   const TargetRegisterInfo *TRI;
   const MachineBranchProbabilityInfo *MBPI;
   const MachineModuleInfo *MMI;
   MachineRegisterInfo *MRI;
   MachineFunction *MF;
   bool PreRegAlloc;
+  bool LayoutMode;
   unsigned TailDupSize;
 
   // A list of virtual registers for which to update SSA form.
   SmallVector<unsigned, 16> SSAUpdateVRs;
 
   // For each virtual register in SSAUpdateVals keep a list of source virtual
   // registers.
   typedef std::vector<std::pair<MachineBasicBlock *, unsigned>> AvailableValsTy;
 
   DenseMap<unsigned, AvailableValsTy> SSAUpdateVals;
 
 public:
   /// Prepare to run on a specific machine function.
-  /// @param TailDupSize - Maxmimum size of blocks to tail-duplicate.
+  /// @param MF - Function that will be processed
+  /// @param MBPI - Branch Probability Info. Used to propagate correct
+  ///     probabilities when modifying the CFG.
+  /// @param LayoutMode - When true, don't use the existing layout to make
+  ///     decisions.
+  /// @param TailDupSize - Maxmimum size of blocks to tail-duplicate. Zero
+  ///     default implies using the command line value TailDupSize.
   void initMF(MachineFunction &MF,
               const MachineBranchProbabilityInfo *MBPI,
-              unsigned TailDupSize = 0);
+              bool LayoutMode, unsigned TailDupSize = 0);
   bool tailDuplicateBlocks();
   static bool isSimpleBB(MachineBasicBlock *TailBB);
   bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB);
   /// Returns true if TailBB can successfully be duplicated into PredBB
   bool canTailDuplicate(MachineBasicBlock *TailBB, MachineBasicBlock *PredBB);
   /// Tail duplicate a single basic block into its predecessors, and then clean
   /// up.
   /// If \p DuplicatePreds is not null, it will be updated to contain the list
   /// of predecessors that received a copy of \p MBB.
+  /// If \p RemovalCallback is non-null. It will be called before MBB is
+  /// deleted.
   bool tailDuplicateAndUpdate(
       bool IsSimple, MachineBasicBlock *MBB,
-      SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds = nullptr);
+      MachineBasicBlock *ForcedLayoutPred,
+      SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds = nullptr,
+      llvm::function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
 
 private:
   typedef TargetInstrInfo::RegSubRegPair RegSubRegPair;
 
   void addSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,
                          MachineBasicBlock *BB);
   void processPHI(MachineInstr *MI, MachineBasicBlock *TailBB,
                   MachineBasicBlock *PredBB,
                   DenseMap<unsigned, RegSubRegPair> &LocalVRMap,
                   SmallVectorImpl<std::pair<unsigned, RegSubRegPair>> &Copies,
                   const DenseSet<unsigned> &UsedByPhi, bool Remove);
   void duplicateInstruction(MachineInstr *MI, MachineBasicBlock *TailBB,
                             MachineBasicBlock *PredBB,
                             DenseMap<unsigned, RegSubRegPair> &LocalVRMap,
                             const DenseSet<unsigned> &UsedByPhi);
   void updateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
                             SmallVectorImpl<MachineBasicBlock *> &TDBBs,
                             SmallSetVector<MachineBasicBlock *, 8> &Succs);
   bool canCompletelyDuplicateBB(MachineBasicBlock &BB);
   bool duplicateSimpleBB(MachineBasicBlock *TailBB,
                          SmallVectorImpl<MachineBasicBlock *> &TDBBs,
                          const DenseSet<unsigned> &RegsUsedByPhi,
                          SmallVectorImpl<MachineInstr *> &Copies);
-  bool tailDuplicate(bool IsSimple, MachineBasicBlock *TailBB,
+  bool tailDuplicate(bool IsSimple,
+                     MachineBasicBlock *TailBB,
+                     MachineBasicBlock *ForcedLayoutPred,
                      SmallVectorImpl<MachineBasicBlock *> &TDBBs,
                      SmallVectorImpl<MachineInstr *> &Copies);
   void appendCopies(MachineBasicBlock *MBB,
                  SmallVectorImpl<std::pair<unsigned,RegSubRegPair>> &CopyInfos,
                  SmallVectorImpl<MachineInstr *> &Copies);
 
-  void removeDeadBlock(MachineBasicBlock *MBB);
+  void removeDeadBlock(
+      MachineBasicBlock *MBB,
+      llvm::function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
 };
 
 } // End llvm namespace
 
 #endif

llvm/trunk/lib/CodeGen/MachineBlockPlacement.cpp

 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/TailDuplicator.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetLowering.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include <algorithm>
static cl::opt<unsigned> MisfetchCost(
     cl::desc("Cost that models the probabilistic risk of an instruction "
              "misfetch due to a jump comparing to falling through, whose cost "
              "is zero."),
     cl::init(1), cl::Hidden);
 
 static cl::opt<unsigned> JumpInstCost("jump-inst-cost",
                                       cl::desc("Cost of jump instructions."),
                                       cl::init(1), cl::Hidden);
+static cl::opt<bool>
+TailDupPlacement("tail-dup-placement",
+              cl::desc("Perform tail duplication during placement. "
+                       "Creates more fallthrough opportunites in "
+                       "outline branches."),
+              cl::init(true), cl::Hidden);
 
 static cl::opt<bool>
 BranchFoldPlacement("branch-fold-placement",
               cl::desc("Perform branch folding during placement. "
                        "Reduces code size."),
               cl::init(true), cl::Hidden);
 
+// Heuristic for tail duplication.
+static cl::opt<unsigned> TailDuplicatePlacementThreshold(
+    "tail-dup-placement-threshold",
+    cl::desc("Instruction cutoff for tail duplication during layout. "
+             "Tail merging during layout is forced to have a threshold "
+             "that won't conflict."), cl::init(2),
+    cl::Hidden);
+
 extern cl::opt<unsigned> StaticLikelyProb;
 extern cl::opt<unsigned> ProfileLikelyProb;
 
 namespace {
 class BlockChain;
 /// \brief Type for our function-wide basic block -> block chain mapping.
 typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType;
 }
public:
   typedef SmallVectorImpl<MachineBasicBlock *>::iterator iterator;
 
   /// \brief Beginning of blocks within the chain.
   iterator begin() { return Blocks.begin(); }
 
   /// \brief End of blocks within the chain.
   iterator end() { return Blocks.end(); }
 
+  bool remove(MachineBasicBlock* BB) {
+    for(iterator i = begin(); i != end(); ++i) {
+      if (*i == BB) {
+        Blocks.erase(i);
+        return true;
+      }
+    }
+    return false;
+  }
+
   /// \brief Merge a block chain into this one.
   ///
   /// This routine merges a block chain into this one. It takes care of forming
   /// a contiguous sequence of basic blocks, updating the edge list, and
   /// updating the block -> chain mapping. It does not free or tear down the
   /// old chain, but the old chain's block list is no longer valid.
   void merge(MachineBasicBlock *BB, BlockChain *Chain) {
     assert(BB);
class MachineBlockPlacement : public MachineFunctionPass {
   const TargetInstrInfo *TII;
 
   /// \brief A handle to the target's lowering info.
   const TargetLoweringBase *TLI;
 
   /// \brief A handle to the post dominator tree.
   MachineDominatorTree *MDT;
 
+  /// \brief Duplicator used to duplicate tails during placement.
+  ///
+  /// Placement decisions can open up new tail duplication opportunities, but
+  /// since tail duplication affects placement decisions of later blocks, it
+  /// must be done inline.
+  TailDuplicator TailDup;
+
   /// \brief A set of blocks that are unavoidably execute, i.e. they dominate
   /// all terminators of the MachineFunction.
   SmallPtrSet<MachineBasicBlock *, 4> UnavoidableBlocks;
 
   /// \brief Allocator and owner of BlockChain structures.
   ///
   /// We build BlockChains lazily while processing the loop structure of
   /// a function. To reduce malloc traffic, we allocate them using this
   /// slab-like allocator, and destroy them after the pass completes. An
   /// important guarantee is that this allocator produces stable pointers to
   /// the chains.
   SpecificBumpPtrAllocator<BlockChain> ChainAllocator;
 
   /// \brief Function wide BasicBlock to BlockChain mapping.
   ///
   /// This mapping allows efficiently moving from any given basic block to the
   /// BlockChain it participates in, if any. We use it to, among other things,
   /// allow implicitly defining edges between chains as the existing edges
   /// between basic blocks.
   DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain;
 
+  /// Decrease the UnscheduledPredecessors count for all blocks in chain, and
+  /// if the count goes to 0, add them to the appropriate work list.
   void markChainSuccessors(BlockChain &Chain, MachineBasicBlock *LoopHeaderBB,
                            const BlockFilterSet *BlockFilter = nullptr);
+
+  /// Decrease the UnscheduledPredecessors count for a single block, and
+  /// if the count goes to 0, add them to the appropriate work list.
+  void markBlockSuccessors(
+      BlockChain &Chain, MachineBasicBlock *BB, MachineBasicBlock *LoopHeaderBB,
+      const BlockFilterSet *BlockFilter = nullptr);
+
+
   BranchProbability
   collectViableSuccessors(MachineBasicBlock *BB, BlockChain &Chain,
                           const BlockFilterSet *BlockFilter,
                           SmallVector<MachineBasicBlock *, 4> &Successors);
   bool shouldPredBlockBeOutlined(MachineBasicBlock *BB, MachineBasicBlock *Succ,
                                  BlockChain &Chain,
                                  const BlockFilterSet *BlockFilter,
                                  BranchProbability SuccProb,
                                  BranchProbability HotProb);
+  bool repeatedlyTailDuplicateBlock(
+      MachineBasicBlock *BB, MachineBasicBlock *&LPred,
+      MachineBasicBlock *LoopHeaderBB,
+      BlockChain &Chain, BlockFilterSet *BlockFilter,
+      MachineFunction::iterator &PrevUnplacedBlockIt);
+  bool maybeTailDuplicateBlock(MachineBasicBlock *BB, MachineBasicBlock *LPred,
+                               const BlockChain &Chain,
+                               BlockFilterSet *BlockFilter,
+                               MachineFunction::iterator &PrevUnplacedBlockIt,
+                               bool &DuplicatedToPred);
   bool
   hasBetterLayoutPredecessor(MachineBasicBlock *BB, MachineBasicBlock *Succ,
                              BlockChain &SuccChain, BranchProbability SuccProb,
                              BranchProbability RealSuccProb, BlockChain &Chain,
                              const BlockFilterSet *BlockFilter);
   MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB,
                                          BlockChain &Chain,
                                          const BlockFilterSet *BlockFilter);
class MachineBlockPlacement : public MachineFunctionPass {
   ///
   /// If the optional parameter BlockFilter is provided, only MBB
   /// present in the set will be added to the worklist. If nullptr
   /// is provided, no filtering occurs.
   void fillWorkLists(MachineBasicBlock *MBB,
                      SmallPtrSetImpl<BlockChain *> &UpdatedPreds,
                      const BlockFilterSet *BlockFilter);
   void buildChain(MachineBasicBlock *BB, BlockChain &Chain,
-                  const BlockFilterSet *BlockFilter = nullptr);
+                  BlockFilterSet *BlockFilter = nullptr);
   MachineBasicBlock *findBestLoopTop(MachineLoop &L,
                                      const BlockFilterSet &LoopBlockSet);
   MachineBasicBlock *findBestLoopExit(MachineLoop &L,
                                       const BlockFilterSet &LoopBlockSet);
   BlockFilterSet collectLoopBlockSet(MachineLoop &L);
   void buildLoopChains(MachineLoop &L);
   void rotateLoop(BlockChain &LoopChain, MachineBasicBlock *ExitingBB,
                   const BlockFilterSet &LoopBlockSet);

 }
 #endif
 
 /// \brief Mark a chain's successors as having one fewer preds.
 ///
 /// When a chain is being merged into the "placed" chain, this routine will
 /// quickly walk the successors of each block in the chain and mark them as
 /// having one fewer active predecessor. It also adds any successors of this
-/// chain which reach the zero-predecessor state to the worklist passed in.
+/// chain which reach the zero-predecessor state to the appropriate worklist.
 void MachineBlockPlacement::markChainSuccessors(
     BlockChain &Chain, MachineBasicBlock *LoopHeaderBB,
     const BlockFilterSet *BlockFilter) {
   // Walk all the blocks in this chain, marking their successors as having
   // a predecessor placed.
   for (MachineBasicBlock *MBB : Chain) {
-    // Add any successors for which this is the only un-placed in-loop
-    // predecessor to the worklist as a viable candidate for CFG-neutral
-    // placement. No subsequent placement of this block will violate the CFG
-    // shape, so we get to use heuristics to choose a favorable placement.
-    for (MachineBasicBlock *Succ : MBB->successors()) {
-      if (BlockFilter && !BlockFilter->count(Succ))
-        continue;
-      BlockChain &SuccChain = *BlockToChain[Succ];
-      // Disregard edges within a fixed chain, or edges to the loop header.
-      if (&Chain == &SuccChain || Succ == LoopHeaderBB)
-        continue;
+    markBlockSuccessors(Chain, MBB, LoopHeaderBB, BlockFilter);
+  }
+}
+
+/// \brief Mark a single block's successors as having one fewer preds.
+///
+/// Under normal circumstances, this is only called by markChainSuccessors,
+/// but if a block that was to be placed is completely tail-duplicated away,
+/// and was duplicated into the chain end, we need to redo markBlockSuccessors
+/// for just that block.
+void MachineBlockPlacement::markBlockSuccessors(
+    BlockChain &Chain, MachineBasicBlock *MBB, MachineBasicBlock *LoopHeaderBB,
+    const BlockFilterSet *BlockFilter) {
 
-      // This is a cross-chain edge that is within the loop, so decrement the
-      // loop predecessor count of the destination chain.
-      if (SuccChain.UnscheduledPredecessors == 0 ||
-          --SuccChain.UnscheduledPredecessors > 0)
-        continue;
 
-      auto *MBB = *SuccChain.begin();
-      if (MBB->isEHPad())
-        EHPadWorkList.push_back(MBB);
-      else
-        BlockWorkList.push_back(MBB);
-    }
+    auto *NewBB = *SuccChain.begin();
+    if (NewBB->isEHPad())
+      EHPadWorkList.push_back(NewBB);
+      BlockWorkList.push_back(NewBB);
   }
 }
 
 /// This helper function collects the set of successors of block
 /// \p BB that are allowed to be its layout successors, and return
 /// the total branch probability of edges from \p BB to those
 /// blocks.
 BranchProbability MachineBlockPlacement::collectViableSuccessors(
void MachineBlockPlacement::fillWorkLists(
   if (MBB->isEHPad())
     EHPadWorkList.push_back(MBB);
   else
     BlockWorkList.push_back(MBB);
 }
 
 void MachineBlockPlacement::buildChain(
     MachineBasicBlock *BB, BlockChain &Chain,
-    const BlockFilterSet *BlockFilter) {
+    BlockFilterSet *BlockFilter) {
   assert(BB && "BB must not be null.\n");
   assert(BlockToChain[BB] == &Chain && "BlockToChainMap mis-match.\n");
   MachineFunction::iterator PrevUnplacedBlockIt = F->begin();
 
   MachineBasicBlock *LoopHeaderBB = BB;
   markChainSuccessors(Chain, LoopHeaderBB, BlockFilter);
   BB = *std::prev(Chain.end());
   for (;;) {
if (!BestSucc) {
       BestSucc = getFirstUnplacedBlock(Chain, PrevUnplacedBlockIt, BlockFilter);
       if (!BestSucc)
         break;
 
       DEBUG(dbgs() << "Unnatural loop CFG detected, forcibly merging the "
                       "layout successor until the CFG reduces\n");
     }
 
+    // Placement may have changed tail duplication opportunities.
+    // Check for that now.
+    if (TailDupPlacement && BestSucc) {
+      // If the chosen successor was duplicated into all its predecessors,
+      // don't bother laying it out, just go round the loop again with BB as
+      // the chain end.
+      if (repeatedlyTailDuplicateBlock(BestSucc, BB, LoopHeaderBB, Chain,
+                                       BlockFilter, PrevUnplacedBlockIt))
+        continue;
+    }
+
     // Place this block, updating the datastructures to reflect its placement.
     BlockChain &SuccChain = *BlockToChain[BestSucc];
     // Zero out UnscheduledPredecessors for the successor we're about to merge in case
     // we selected a successor that didn't fit naturally into the CFG.
     SuccChain.UnscheduledPredecessors = 0;
     DEBUG(dbgs() << "Merging from " << getBlockName(BB) << " to "
                  << getBlockName(BestSucc) << "\n");
     markChainSuccessors(SuccChain, LoopHeaderBB, BlockFilter);
for (MachineBasicBlock *ChainBB : FunctionChain) {
     BranchProbability LayoutProb =
         MBPI->getEdgeProbability(LayoutPred, ChainBB);
     BlockFrequency LayoutEdgeFreq = MBFI->getBlockFreq(LayoutPred) * LayoutProb;
     if (LayoutEdgeFreq <= (Freq * ColdProb))
       ChainBB->setAlignment(Align);
   }
 }
 
+/// Tail duplicate \p BB into (some) predecessors if profitable, repeating if
+/// it was duplicated into its chain predecessor and removed.
+/// \p BB    - Basic block that may be duplicated.
+///
+/// \p LPred - Chosen layout predecessor of \p BB.
+///            Updated to be the chain end if LPred is removed.
+/// \p Chain - Chain to which \p LPred belongs, and \p BB will belong.
+/// \p BlockFilter - Set of blocks that belong to the loop being laid out.
+///                  Used to identify which blocks to update predecessor
+///                  counts.
+/// \p PrevUnplacedBlockIt - Iterator pointing to the last block that was
+///                          chosen in the given order due to unnatural CFG
+///                          only needed if \p BB is removed and
+///                          \p PrevUnplacedBlockIt pointed to \p BB.
+/// @return true if \p BB was removed.
+bool MachineBlockPlacement::repeatedlyTailDuplicateBlock(
+    MachineBasicBlock *BB, MachineBasicBlock *&LPred,
+    MachineBasicBlock *LoopHeaderBB,
+    BlockChain &Chain, BlockFilterSet *BlockFilter,
+    MachineFunction::iterator &PrevUnplacedBlockIt) {
+  bool Removed, DuplicatedToLPred;
+  bool DuplicatedToOriginalLPred;
+  Removed = maybeTailDuplicateBlock(BB, LPred, Chain, BlockFilter,
+                                    PrevUnplacedBlockIt,
+                                    DuplicatedToLPred);
+  if (!Removed)
+    return false;
+  DuplicatedToOriginalLPred = DuplicatedToLPred;
+  // Iteratively try to duplicate again. It can happen that a block that is
+  // duplicated into is still small enough to be duplicated again.
+  // No need to call markBlockSuccessors in this case, as the blocks being
+  // duplicated from here on are already scheduled.
+  // Note that DuplicatedToLPred always implies Removed.
+  while (DuplicatedToLPred) {
+    assert (Removed && "Block must have been removed to be duplicated into its "
+            "layout predecessor.");
+    MachineBasicBlock *DupBB, *DupPred;
+    // The removal callback causes Chain.end() to be updated when a block is
+    // removed. On the first pass through the loop, the chain end should be the
+    // same as it was on function entry. On subsequent passes, because we are
+    // duplicating the block at the end of the chain, if it is removed the
+    // chain will have shrunk by one block.
+    BlockChain::iterator ChainEnd = Chain.end();
+    DupBB = *(--ChainEnd);
+    // Now try to duplicate again.
+    if (ChainEnd == Chain.begin())
+      break;
+    DupPred = *std::prev(ChainEnd);
+    Removed = maybeTailDuplicateBlock(DupBB, DupPred, Chain, BlockFilter,
+                                      PrevUnplacedBlockIt,
+                                      DuplicatedToLPred);
+  }
+  // If BB was duplicated into LPred, it is now scheduled. But because it was
+  // removed, markChainSuccessors won't be called for its chain. Instead we
+  // call markBlockSuccessors for LPred to achieve the same effect. This must go
+  // at the end because repeating the tail duplication can increase the number
+  // of unscheduled predecessors.
+  if (DuplicatedToOriginalLPred)
+    markBlockSuccessors(Chain, LPred, LoopHeaderBB, BlockFilter);
+
+  LPred = *std::prev(Chain.end());
+  return true;
+}
+
+/// Tail duplicate \p BB into (some) predecessors if profitable.
+/// \p BB    - Basic block that may be duplicated
+/// \p LPred - Chosen layout predecessor of \p BB
+/// \p Chain - Chain to which \p LPred belongs, and \p BB will belong.
+/// \p BlockFilter - Set of blocks that belong to the loop being laid out.
+///                  Used to identify which blocks to update predecessor
+///                  counts.
+/// \p PrevUnplacedBlockIt - Iterator pointing to the last block that was
+///                          chosen in the given order due to unnatural CFG
+///                          only needed if \p BB is removed and
+///                          \p PrevUnplacedBlockIt pointed to \p BB.
+/// \p DuplicatedToLPred - True if the block was duplicated into LPred. Will
+///                        only be true if the block was removed.
+/// \return  - True if the block was duplicated into all preds and removed.
+bool MachineBlockPlacement::maybeTailDuplicateBlock(
+    MachineBasicBlock *BB, MachineBasicBlock *LPred,
+    const BlockChain &Chain, BlockFilterSet *BlockFilter,
+    MachineFunction::iterator &PrevUnplacedBlockIt,
+    bool &DuplicatedToLPred) {
+
+  DuplicatedToLPred = false;
+  DEBUG(dbgs() << "Redoing tail duplication for Succ#"
+        << BB->getNumber() << "\n");
+  bool IsSimple = TailDup.isSimpleBB(BB);
+  // Blocks with single successors don't create additional fallthrough
+  // opportunities. Don't duplicate them. TODO: When conditional exits are
+  // analyzable, allow them to be duplicated.
+  if (!IsSimple && BB->succ_size() == 1)
+    return false;
+  if (!TailDup.shouldTailDuplicate(IsSimple, *BB))
+    return false;
+  // This has to be a callback because none of it can be done after
+  // BB is deleted.
+  bool Removed = false;
+  auto RemovalCallback =
+      [&](MachineBasicBlock *RemBB) {
+        // Signal to outer function
+        Removed = true;
+
+        // Conservative default.
+        bool InWorkList = true;
+        // Remove from the Chain and Chain Map
+        if (BlockToChain.count(RemBB)) {
+          BlockChain *Chain = BlockToChain[RemBB];
+          InWorkList = Chain->UnscheduledPredecessors == 0;
+          Chain->remove(RemBB);
+          BlockToChain.erase(RemBB);
+        }
+
+        // Handle the unplaced block iterator
+        if (&(*PrevUnplacedBlockIt) == RemBB) {
+          PrevUnplacedBlockIt++;
+        }
+
+        // Handle the Work Lists
+        if (InWorkList) {
+          SmallVectorImpl<MachineBasicBlock *> &RemoveList = BlockWorkList;
+          if (RemBB->isEHPad())
+            RemoveList = EHPadWorkList;
+          RemoveList.erase(
+              remove_if(RemoveList,
+                        [RemBB](MachineBasicBlock *BB) {return BB == RemBB;}),
+              RemoveList.end());
+        }
+
+        // Handle the filter set
+        if (BlockFilter) {
+          BlockFilter->erase(RemBB);
+        }
+
+        // Remove the block from loop info.
+        MLI->removeBlock(RemBB);
+
+        // TailDuplicator handles removing it from loops.
+        DEBUG(dbgs() << "TailDuplicator deleted block: "
+              << getBlockName(RemBB) << "\n");
+      };
+  auto RemovalCallbackRef =
+      llvm::function_ref<void(MachineBasicBlock*)>(RemovalCallback);
+
+  SmallVector<MachineBasicBlock *, 8> DuplicatedPreds;
+  TailDup.tailDuplicateAndUpdate(IsSimple, BB, LPred,
+                                 &DuplicatedPreds, &RemovalCallbackRef);
+
+  // Update UnscheduledPredecessors to reflect tail-duplication.
+  DuplicatedToLPred = false;
+  for (MachineBasicBlock *Pred : DuplicatedPreds) {
+    // We're only looking for unscheduled predecessors that match the filter.
+    BlockChain* PredChain = BlockToChain[Pred];
+    if (Pred == LPred)
+      DuplicatedToLPred = true;
+    if (Pred == LPred || (BlockFilter && !BlockFilter->count(Pred))
+        || PredChain == &Chain)
+      continue;
+    for (MachineBasicBlock *NewSucc : Pred->successors()) {
+      if (BlockFilter && !BlockFilter->count(NewSucc))
+        continue;
+      BlockChain *NewChain = BlockToChain[NewSucc];
+      if (NewChain != &Chain && NewChain != PredChain)
+        NewChain->UnscheduledPredecessors++;
+    }
+  }
+  return Removed;
+}
+
 bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(*MF.getFunction()))
     return false;
 
   // Check for single-block functions and skip them.
   if (std::next(MF.begin()) == MF.end())
     return false;
 
   F = &MF;
   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
   MBFI = llvm::make_unique<BranchFolder::MBFIWrapper>(
       getAnalysis<MachineBlockFrequencyInfo>());
   MLI = &getAnalysis<MachineLoopInfo>();
   TII = MF.getSubtarget().getInstrInfo();
   TLI = MF.getSubtarget().getTargetLowering();
   MDT = &getAnalysis<MachineDominatorTree>();
+  if (TailDupPlacement) {
+    unsigned TailDupSize = TailDuplicatePlacementThreshold;
+    if (MF.getFunction()->optForSize())
+      TailDupSize = 1;
+    TailDup.initMF(MF, MBPI, /* LayoutMode */ true, TailDupSize);
+  }
+
   assert(BlockToChain.empty());
 
   buildCFGChains();
 
   // Changing the layout can create new tail merging opportunities.
   TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
   // TailMerge can create jump into if branches that make CFG irreducible for
   // HW that requires structured CFG.
   bool EnableTailMerge = !MF.getTarget().requiresStructuredCFG() &&
                          PassConfig->getEnableTailMerge() &&
                          BranchFoldPlacement;
   // No tail merging opportunities if the block number is less than four.
   if (MF.size() > 3 && EnableTailMerge) {
-    // Default to the standard tail-merge-size option.
-    unsigned TailMergeSize = 0;
+    unsigned TailMergeSize = TailDuplicatePlacementThreshold + 1;
     BranchFolder BF(/*EnableTailMerge=*/true, /*CommonHoist=*/false, *MBFI,
                     *MBPI, TailMergeSize);
 
     if (BF.OptimizeFunction(MF, TII, MF.getSubtarget().getRegisterInfo(),
                             getAnalysisIfAvailable<MachineModuleInfo>(), MLI,
                             /*AfterBlockPlacement=*/true)) {
       // Redo the layout if tail merging creates/removes/moves blocks.
       BlockToChain.clear();
+      // Must redo the dominator tree if blocks were changed.
+      MDT->runOnMachineFunction(MF);
       ChainAllocator.DestroyAll();
       buildCFGChains();
     }
   }
 
   optimizeBranches();
   alignBlocks();
 

llvm/trunk/lib/CodeGen/TailDuplication.cpp

INITIALIZE_PASS(TailDuplicatePass, "tailduplication", "Tail Duplication", false,
                 false)
 
 bool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(*MF.getFunction()))
     return false;
 
   auto MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
 
-  Duplicator.initMF(MF, MBPI);
+  Duplicator.initMF(MF, MBPI, /* LayoutMode */ false);
 
   bool MadeChange = false;
   while (Duplicator.tailDuplicateBlocks())
     MadeChange = true;
 
   return MadeChange;
 }
 
 void TailDuplicatePass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<MachineBranchProbabilityInfo>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }

llvm/trunk/lib/CodeGen/TailDuplicator.cpp

 #include "llvm/CodeGen/TailDuplicator.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
TailDupVerify("tail-dup-verify",
                   cl::desc("Verify sanity of PHI instructions during taildup"),
                   cl::init(false), cl::Hidden);
 
 static cl::opt<unsigned> TailDupLimit("tail-dup-limit", cl::init(~0U),
                                       cl::Hidden);
 
 void TailDuplicator::initMF(MachineFunction &MFin,
                             const MachineBranchProbabilityInfo *MBPIin,
-                            unsigned TailDupSizeIn) {
+                            bool LayoutModeIn, unsigned TailDupSizeIn) {
   MF = &MFin;
   TII = MF->getSubtarget().getInstrInfo();
   TRI = MF->getSubtarget().getRegisterInfo();
   MRI = &MF->getRegInfo();
   MMI = &MF->getMMI();
   MBPI = MBPIin;
   TailDupSize = TailDupSizeIn;
 
   assert(MBPI != nullptr && "Machine Branch Probability Info required");
 
+  LayoutMode = LayoutModeIn;
   PreRegAlloc = MRI->isSSA();
 }
 
 static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) {
   for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) {
     MachineBasicBlock *MBB = &*I;
     SmallSetVector<MachineBasicBlock *, 8> Preds(MBB->pred_begin(),
                                                  MBB->pred_end());
while (MI != MBB->end()) {
       ++MI;
     }
   }
 }
 
 /// Tail duplicate the block and cleanup.
 /// \p IsSimple - return value of isSimpleBB
 /// \p MBB - block to be duplicated
+/// \p ForcedLayoutPred - If non-null, treat this block as the layout
+///     predecessor, instead of using the ordering in MF
 /// \p DuplicatedPreds - if non-null, \p DuplicatedPreds will contain a list of
 ///     all Preds that received a copy of \p MBB.
+/// \p RemovalCallback - if non-null, called just before MBB is deleted.
 bool TailDuplicator::tailDuplicateAndUpdate(
     bool IsSimple, MachineBasicBlock *MBB,
-    SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds) {
+    MachineBasicBlock *ForcedLayoutPred,
+    SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds,
+    llvm::function_ref<void(MachineBasicBlock *)> *RemovalCallback) {
   // Save the successors list.
   SmallSetVector<MachineBasicBlock *, 8> Succs(MBB->succ_begin(),
                                                MBB->succ_end());
 
   SmallVector<MachineBasicBlock *, 8> TDBBs;
   SmallVector<MachineInstr *, 16> Copies;
-  if (!tailDuplicate(IsSimple, MBB, TDBBs, Copies))
+  if (!tailDuplicate(IsSimple, MBB, ForcedLayoutPred, TDBBs, Copies))
     return false;
 
   ++NumTails;
 
   SmallVector<MachineInstr *, 8> NewPHIs;
   MachineSSAUpdater SSAUpdate(*MF, &NewPHIs);
 
   // TailBB's immediate successors are now successors of those predecessors
   // which duplicated TailBB. Add the predecessors as sources to the PHI
   // instructions.
   bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken();
   if (PreRegAlloc)
     updateSuccessorsPHIs(MBB, isDead, TDBBs, Succs);
 
   // If it is dead, remove it.
   if (isDead) {
     NumTailDupRemoved += MBB->size();
-    removeDeadBlock(MBB);
+    removeDeadBlock(MBB, RemovalCallback);
     ++NumDeadBlocks;
   }
 
   // Update SSA form.
   if (!SSAUpdateVRs.empty()) {
     for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) {
       unsigned VReg = SSAUpdateVRs[i];
       SSAUpdate.Initialize(VReg);
for (MachineFunction::iterator I = ++MF->begin(), E = MF->end(); I != E;) {
     if (NumTails == TailDupLimit)
       break;
 
     bool IsSimple = isSimpleBB(MBB);
 
     if (!shouldTailDuplicate(IsSimple, *MBB))
       continue;
 
-    MadeChange |= tailDuplicateAndUpdate(IsSimple, MBB);
+    MadeChange |= tailDuplicateAndUpdate(IsSimple, MBB, nullptr);
   }
 
   if (PreRegAlloc && TailDupVerify)
     VerifyPHIs(*MF, false);
 
   return MadeChange;
 }
 
for (MachineInstr &MI : *SuccBB) {
       }
     }
   }
 }
 
 /// Determine if it is profitable to duplicate this block.
 bool TailDuplicator::shouldTailDuplicate(bool IsSimple,
                                          MachineBasicBlock &TailBB) {
-  // Only duplicate blocks that end with unconditional branches.
-  if (TailBB.canFallThrough())
+  // When doing tail-duplication during layout, the block ordering is in flux,
+  // so canFallThrough returns a result based on incorrect information and
+  // should just be ignored.
+  if (!LayoutMode && TailBB.canFallThrough())
     return false;
 
   // Don't try to tail-duplicate single-block loops.
   if (TailBB.isSuccessor(&TailBB))
     return false;
 
   // Set the limit on the cost to duplicate. When optimizing for size,
   // duplicate only one, because one branch instruction can be eliminated to
for (MachineBasicBlock *PredBB : Preds) {
 
     TDBBs.push_back(PredBB);
   }
   return Changed;
 }
 
 bool TailDuplicator::canTailDuplicate(MachineBasicBlock *TailBB,
                                       MachineBasicBlock *PredBB) {
-  // EH edges are ignored by AnalyzeBranch.
+  // EH edges are ignored by analyzeBranch.
   if (PredBB->succ_size() > 1)
     return false;
 
   MachineBasicBlock *PredTBB, *PredFBB;
   SmallVector<MachineOperand, 4> PredCond;
   if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true))
     return false;
   if (!PredCond.empty())
     return false;
   return true;
 }
 
 /// If it is profitable, duplicate TailBB's contents in each
 /// of its predecessors.
+/// \p IsSimple result of isSimpleBB
+/// \p TailBB   Block to be duplicated.
+/// \p ForcedLayoutPred  When non-null, use this block as the layout predecessor
+///                      instead of the previous block in MF's order.
+/// \p TDBBs             A vector to keep track of all blocks tail-duplicated
+///                      into.
+/// \p Copies            A vector of copy instructions inserted. Used later to
+///                      walk all the inserted copies and remove redundant ones.
 bool TailDuplicator::tailDuplicate(bool IsSimple, MachineBasicBlock *TailBB,
+                                   MachineBasicBlock *ForcedLayoutPred,
                                    SmallVectorImpl<MachineBasicBlock *> &TDBBs,
                                    SmallVectorImpl<MachineInstr *> &Copies) {
   DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n');
 
   DenseSet<unsigned> UsedByPhi;
   getRegsUsedByPHIs(*TailBB, &UsedByPhi);
 
   if (IsSimple)
     return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies);
 
   // Iterate through all the unique predecessors and tail-duplicate this
   // block into them, if possible. Copying the list ahead of time also
   // avoids trouble with the predecessor list reallocating.
   bool Changed = false;
   SmallSetVector<MachineBasicBlock *, 8> Preds(TailBB->pred_begin(),
                                                TailBB->pred_end());
   for (MachineBasicBlock *PredBB : Preds) {
     assert(TailBB != PredBB &&
            "Single-block loop should have been rejected earlier!");
 
     if (!canTailDuplicate(TailBB, PredBB))
       continue;
 
     // Don't duplicate into a fall-through predecessor (at least for now).
-    if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough())
+    bool IsLayoutSuccessor = false;
+    if (ForcedLayoutPred)
+      IsLayoutSuccessor = (ForcedLayoutPred == PredBB);
+    else if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough())
+      IsLayoutSuccessor = true;
+    if (IsLayoutSuccessor)
       continue;
 
     DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
                  << "From Succ: " << *TailBB);
 
     TDBBs.push_back(PredBB);
 
     // Remove PredBB's unconditional branch.
for (MachineBasicBlock *PredBB : Preds) {
 
     Changed = true;
     ++NumTailDups;
   }
 
   // If TailBB was duplicated into all its predecessors except for the prior
   // block, which falls through unconditionally, move the contents of this
   // block into the prior block.
-  MachineBasicBlock *PrevBB = &*std::prev(TailBB->getIterator());
+  MachineBasicBlock *PrevBB = ForcedLayoutPred;
+  if (!PrevBB)
+    PrevBB = &*std::prev(TailBB->getIterator());
   MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
   SmallVector<MachineOperand, 4> PriorCond;
   // This has to check PrevBB->succ_size() because EH edges are ignored by
-  // AnalyzeBranch.
+  // analyzeBranch.
   if (PrevBB->succ_size() == 1 &&
       // Layout preds are not always CFG preds. Check.
       *PrevBB->succ_begin() == TailBB &&
       !TII->analyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true) &&
-      PriorCond.empty() && !PriorTBB && TailBB->pred_size() == 1 &&
+      PriorCond.empty() &&
+      (!PriorTBB || PriorTBB == TailBB) &&
+      TailBB->pred_size() == 1 &&
       !TailBB->hasAddressTaken()) {
     DEBUG(dbgs() << "\nMerging into block: " << *PrevBB
                  << "From MBB: " << *TailBB);
     if (PreRegAlloc) {
       DenseMap<unsigned, RegSubRegPair> LocalVRMap;
       SmallVector<std::pair<unsigned, RegSubRegPair>, 4> CopyInfos;
       MachineBasicBlock::iterator I = TailBB->begin();
       // Process PHI instructions first.
if (PreRegAlloc) {
         // uses with PHI source register or the new registers.
         MachineInstr *MI = &*I++;
         assert(!MI->isBundle() && "Not expecting bundles before regalloc!");
         duplicateInstruction(MI, TailBB, PrevBB, LocalVRMap, UsedByPhi);
         MI->eraseFromParent();
       }
       appendCopies(PrevBB, CopyInfos, Copies);
     } else {
+      TII->removeBranch(*PrevBB);
       // No PHIs to worry about, just splice the instructions over.
       PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end());
     }
     PrevBB->removeSuccessor(PrevBB->succ_begin());
     assert(PrevBB->succ_empty());
     PrevBB->transferSuccessors(TailBB);
     TDBBs.push_back(PrevBB);
     Changed = true;
for (auto &CI : CopyInfos) {
     auto C = BuildMI(*MBB, Loc, DebugLoc(), CopyD, CI.first)
                 .addReg(CI.second.Reg, 0, CI.second.SubReg);
     Copies.push_back(C);
   }
 }
 
 /// Remove the specified dead machine basic block from the function, updating
 /// the CFG.
-void TailDuplicator::removeDeadBlock(MachineBasicBlock *MBB) {
+void TailDuplicator::removeDeadBlock(
+    MachineBasicBlock *MBB,
+    llvm::function_ref<void(MachineBasicBlock *)> *RemovalCallback) {
   assert(MBB->pred_empty() && "MBB must be dead!");
   DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
 
+  if (RemovalCallback)
+    (*RemovalCallback)(MBB);
+
   // Remove all successors.
   while (!MBB->succ_empty())
     MBB->removeSuccessor(MBB->succ_end() - 1);
 
   // Remove the block.
   MBB->eraseFromParent();
 }
 
 } // End llvm namespace

llvm/trunk/test/CodeGen/AArch64/arm64-extload-knownzero.ll

 ; RUN: llc < %s -mtriple=arm64-eabi | FileCheck %s
 ; rdar://12771555
 
 define void @foo(i16* %ptr, i32 %a) nounwind {
 entry:
 ; CHECK-LABEL: foo:
   %tmp1 = icmp ult i32 %a, 100
   br i1 %tmp1, label %bb1, label %bb2
 bb1:
 ; CHECK: %bb1
 ; CHECK: ldrh [[REG:w[0-9]+]]
   %tmp2 = load i16, i16* %ptr, align 2
   br label %bb2
 bb2:
-; CHECK: %bb2
 ; CHECK-NOT: and {{w[0-9]+}}, [[REG]], #0xffff
 ; CHECK: cmp [[REG]], #23
   %tmp3 = phi i16 [ 0, %entry ], [ %tmp2, %bb1 ]
   %cmp = icmp ult i16 %tmp3, 24
   br i1 %cmp, label %bb3, label %exit
 bb3:
   call void @bar() nounwind
   br label %exit
 exit:
   ret void
 }
 
 declare void @bar ()

llvm/trunk/test/CodeGen/AArch64/machine_cse.ll

-; RUN: llc < %s -mtriple=aarch64-linux-gnuabi -O2 | FileCheck %s
+; RUN: llc < %s -mtriple=aarch64-linux-gnuabi -O2 -tail-dup-placement=0 | FileCheck %s
+; -tail-dup-placement causes tail duplication during layout. This breaks the
+; assumptions of the test case as written (specifically, it creates an
+; additional cmp instruction, creating a false positive), so we pass
+; -tail-dup-placement=0 to restore the original behavior
 
 ; marked as external to prevent possible optimizations
 @a = external global i32
 @b = external global i32
 @c = external global i32
 @d = external global i32
 @e = external global i32
 

llvm/trunk/test/CodeGen/AArch64/tail-dup-repeat-worklist.ll

+; RUN: llc -O3 -o - -verify-machineinstrs %s | FileCheck %s
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64-unknown-linux-gnu"
+
+%struct.s1 = type { %struct.s3*, %struct.s1* }
+%struct.s2 = type opaque
+%struct.s3 = type { i32 }
+
+; Function Attrs: nounwind
+define internal fastcc i32 @repeated_dup_worklist(%struct.s1** %pp1, %struct.s2* %p2, i32 %state, i1 %i1_1, i32 %i32_1) unnamed_addr #0 {
+entry:
+  br label %while.cond.outer
+
+; The loop gets laid out:
+; %while.cond.outer
+; %(null)
+; %(null)
+; %dup2
+; and then %dup1 gets chosen as the next block.
+; when dup2 is duplicated into dup1, %worklist could erroneously be placed on
+; the worklist, because all of its current predecessors are now scheduled.
+; However, after dup2 is tail-duplicated, %worklist can't be on the worklist
+; because it now has unscheduled predecessors.q
+; CHECK-LABEL: repeated_dup_worklist
+; CHECK: // %entry
+; CHECK: // %while.cond.outer
+; first %(null) block
+; CHECK: // in Loop:
+; CHECK: ldr
+; CHECK-NEXT: tbnz
+; second %(null) block
+; CHECK: // in Loop:
+; CHECK: // %dup2
+; CHECK: // %worklist
+; CHECK: // %if.then96.i
+while.cond.outer:                                 ; preds = %dup1, %entry
+  %progress.0.ph = phi i32 [ 0, %entry ], [ %progress.1, %dup1 ]
+  %inc77 = add nsw i32 %progress.0.ph, 1
+  %cmp = icmp slt i32 %progress.0.ph, %i32_1
+  br i1 %cmp, label %dup2, label %dup1
+
+dup2:                       ; preds = %if.then96.i, %worklist, %while.cond.outer
+  %progress.1.ph = phi i32 [ 0, %while.cond.outer ], [ %progress.1, %if.then96.i ], [ %progress.1, %worklist ]
+  %.pr = load %struct.s1*, %struct.s1** %pp1, align 8
+  br label %dup1
+
+dup1:                                       ; preds = %dup2, %while.cond.outer
+  %0 = phi %struct.s1* [ %.pr, %dup2 ], [ undef, %while.cond.outer ]
+  %progress.1 = phi i32 [ %progress.1.ph, %dup2 ], [ %inc77, %while.cond.outer ]
+  br i1 %i1_1, label %while.cond.outer, label %worklist
+
+worklist:                                       ; preds = %dup1
+  %snode94 = getelementptr inbounds %struct.s1, %struct.s1* %0, i64 0, i32 0
+  %1 = load %struct.s3*, %struct.s3** %snode94, align 8
+  %2 = getelementptr inbounds %struct.s3, %struct.s3* %1, i32 0, i32 0
+  %3 = load i32, i32* %2, align 4
+  %tobool95.i = icmp eq i32 %3, 0
+  br i1 %tobool95.i, label %if.then96.i, label %dup2
+
+if.then96.i:                                      ; preds = %worklist
+  call fastcc void @free_s3(%struct.s2* %p2, %struct.s3* %1) #1
+  br label %dup2
+}
+
+; Function Attrs: nounwind
+declare fastcc void @free_s3(%struct.s2*, %struct.s3*) unnamed_addr #0
+
+attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="cortex-a57" "target-features"="+crc,+crypto,+neon" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { nounwind }

llvm/trunk/test/CodeGen/ARM/2011-03-23-PeepholeBug.ll

 bb1:                                              ; preds = %bb
 ; CHECK: bb1
 ; CHECK: subs [[REG:r[0-9]+]], #1
   %tmp = tail call i32 @puts() nounwind
   %indvar.next = add i32 %indvar, 1
   br label %bb2
 
 bb2:                                              ; preds = %bb1, %entry
-; CHECK: bb2
 ; CHECK: cmp [[REG]], #0
 ; CHECK: ble
   %indvar = phi i32 [ %indvar.next, %bb1 ], [ 0, %entry ]
   %tries.0 = sub i32 2147483647, %indvar
   %tmp1 = icmp sgt i32 %tries.0, 0
   br i1 %tmp1, label %bb, label %bb3
 
 bb3:                                              ; preds = %bb2, %bb
   ret i32 0
 }
 
 declare i32 @rand()
 
 declare i32 @puts() nounwind

llvm/trunk/test/CodeGen/PowerPC/branch-opt.ll

-; RUN: llc -verify-machineinstrs < %s -march=ppc32 | \
-; RUN:   grep "b LBB.*" | count 4
+; RUN: llc -verify-machineinstrs < %s -march=ppc32 | FileCheck %s
 
 target datalayout = "E-p:32:32"
 target triple = "powerpc-apple-darwin8.7.0"
 
+;CHECK-LABEL: foo:
+; There are 4 inner loops (%bb, %bb12, %bb25, %bb38) that all exit to %cond_next48
+; The last (whichever it is) should have a fallthrough exit, and the other three
+; need an unconditional branch. No other block should have an unconditional
+; branch to cond_next48
+; One of the blocks ends up with a loop exit block that gets a tail-duplicated copy
+; of %cond_next48, so there should only be two unconditional branches.
+
+;CHECK: b LBB0_13
+;CHECK: b LBB0_13
+;CHECK-NOT: b LBB0_13
+;CHECK: LBB0_13: ; %cond_next48
+
 define void @foo(i32 %W, i32 %X, i32 %Y, i32 %Z) {
 entry:
   %tmp1 = and i32 %W, 1   ; <i32> [#uses=1]
   %tmp1.upgrd.1 = icmp eq i32 %tmp1, 0    ; <i1> [#uses=1]
   br i1 %tmp1.upgrd.1, label %cond_false, label %bb5
 bb:   ; preds = %bb5, %bb
   %indvar77 = phi i32 [ %indvar.next78, %bb ], [ 0, %bb5 ]    ; <i32> [#uses=1]
   %tmp2 = tail call i32 (...) @bar( )    ; <i32> [#uses=0]

llvm/trunk/test/CodeGen/PowerPC/sjlj.ll

 ; CHECK-DAG: stxvd2x
 
 ; CHECK-DAG: addis [[REG:[0-9]+]], 2, env_sigill@toc@ha
 ; CHECK-DAG: std 31, env_sigill@toc@l([[REG]])
 ; CHECK-DAG: addi [[REGA:[0-9]+]], [[REG]], env_sigill@toc@l
 ; CHECK-DAG: std [[REGA]], [[OFF:[0-9]+]](31)                  # 8-byte Folded Spill
 ; CHECK-DAG: std 1, 16([[REGA]])
 ; CHECK-DAG: std 2, 24([[REGA]])
-; CHECK: bcl 20, 31, .LBB1_5
+; CHECK: bcl 20, 31, .LBB1_3
 ; CHECK: li 3, 1
-; CHECK: #EH_SjLj_Setup .LBB1_5
+; CHECK: #EH_SjLj_Setup .LBB1_3
 ; CHECK: b .LBB1_1
 
-; CHECK: .LBB1_4:
+; CHECK: .LBB1_3:
+; CHECK: mflr [[REGL:[0-9]+]]
+; CHECK: ld [[REG2:[0-9]+]], [[OFF]](31)                   # 8-byte Folded Reload
+; CHECK: std [[REGL]], 8([[REG2]])
+; CHECK: li 3, 0
+
+; CHECK: .LBB1_5:
 
 ; CHECK: lfd
 ; CHECK: lxvd2x
 ; CHECK: ld
 ; CHECK: blr
 
-; CHECK: .LBB1_5:
-; CHECK: mflr [[REGL:[0-9]+]]
-; CHECK: ld [[REG2:[0-9]+]], [[OFF]](31)                   # 8-byte Folded Reload
-; CHECK: std [[REGL]], 8([[REG2]])
-; CHECK: li 3, 0
-
 ; CHECK-NOAV: @main
 ; CHECK-NOAV-NOT: stxvd2x
 ; CHECK-NOAV: bcl
 ; CHECK-NOAV: mflr
 ; CHECK-NOAV: bl foo
 ; CHECK-NOAV-NOT: lxvd2x
 ; CHECK-NOAV: blr
 }

llvm/trunk/test/CodeGen/PowerPC/tail-dup-layout.ll

+; RUN: llc -outline-optional-branches -O2 < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-n32:64"
+target triple = "powerpc64le-grtev4-linux-gnu"
+
+; Intended layout:
+; The outlining flag produces the layout
+; test1
+; test2
+; test3
+; test4
+; exit
+; optional1
+; optional2
+; optional3
+; optional4
+; Tail duplication puts test n+1 at the end of optional n
+; so optional1 includes a copy of test2 at the end, and branches
+; to test3 (at the top) or falls through to optional 2.
+; The CHECK statements check for the whole string of tests and exit block,
+; and then check that the correct test has been duplicated into the end of
+; the optional blocks and that the optional blocks are in the correct order.
+;CHECK-LABEL: f:
+; test1 may have been merged with entry
+;CHECK: mr [[TAGREG:[0-9]+]], 3
+;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 1
+;CHECK-NEXT: bc 12, 1, [[OPT1LABEL:[._0-9A-Za-z]+]]
+;CHECK-NEXT: [[TEST2LABEL:[._0-9A-Za-z]+]]: # %test2
+;CHECK-NEXT: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 30, 30
+;CHECK-NEXT: bne 0, [[OPT2LABEL:[._0-9A-Za-z]+]]
+;CHECK-NEXT: [[TEST3LABEL:[._0-9A-Za-z]+]]: # %test3
+;CHECK-NEXT: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 29, 29
+;CHECK-NEXT: bne 0, .[[OPT3LABEL:[._0-9A-Za-z]+]]
+;CHECK-NEXT: [[TEST4LABEL:[._0-9A-Za-z]+]]: # %test4
+;CHECK-NEXT: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 28, 28
+;CHECK-NEXT: bne 0, .[[OPT4LABEL:[._0-9A-Za-z]+]]
+;CHECK-NEXT: [[EXITLABEL:[._0-9A-Za-z]+]]: # %exit
+;CHECK: blr
+;CHECK-NEXT: [[OPT1LABEL]]
+;CHECK: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 30, 30
+;CHECK-NEXT: beq 0, [[TEST3LABEL]]
+;CHECK-NEXT: [[OPT2LABEL]]
+;CHECK: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 29, 29
+;CHECK-NEXT: beq 0, [[TEST4LABEL]]
+;CHECK-NEXT: [[OPT3LABEL]]
+;CHECK: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 28, 28
+;CHECK-NEXT: beq 0, [[EXITLABEL]]
+;CHECK-NEXT: [[OPT4LABEL]]
+;CHECK: b [[EXITLABEL]]
+
+define void @f(i32 %tag) {
+entry:
+  br label %test1
+test1:
+  %tagbit1 = and i32 %tag, 1
+  %tagbit1eq0 = icmp eq i32 %tagbit1, 0
+  br i1 %tagbit1eq0, label %test2, label %optional1
+optional1:
+  call void @a()
+  call void @a()
+  call void @a()
+  call void @a()
+  br label %test2
+test2:
+  %tagbit2 = and i32 %tag, 2
+  %tagbit2eq0 = icmp eq i32 %tagbit2, 0
+  br i1 %tagbit2eq0, label %test3, label %optional2
+optional2:
+  call void @b()
+  call void @b()
+  call void @b()
+  call void @b()
+  br label %test3
+test3:
+  %tagbit3 = and i32 %tag, 4
+  %tagbit3eq0 = icmp eq i32 %tagbit3, 0
+  br i1 %tagbit3eq0, label %test4, label %optional3
+optional3:
+  call void @c()
+  call void @c()
+  call void @c()
+  call void @c()
+  br label %test4
+test4:
+  %tagbit4 = and i32 %tag, 8
+  %tagbit4eq0 = icmp eq i32 %tagbit4, 0
+  br i1 %tagbit4eq0, label %exit, label %optional4
+optional4:
+  call void @d()
+  call void @d()
+  call void @d()
+  call void @d()
+  br label %exit
+exit:
+  ret void
+}
+
+declare void @a()
+declare void @b()
+declare void @c()
+declare void @d()

llvm/trunk/test/CodeGen/WebAssembly/cfg-stackify.ll

 ; RUN: llc < %s -asm-verbose=false -disable-wasm-fallthrough-return-opt -disable-block-placement -verify-machineinstrs -fast-isel=false | FileCheck %s
-; RUN: llc < %s -asm-verbose=false -disable-wasm-fallthrough-return-opt -verify-machineinstrs -fast-isel=false | FileCheck -check-prefix=OPT %s
+; RUN: llc < %s -asm-verbose=false -disable-wasm-fallthrough-return-opt -tail-dup-placement=0 -verify-machineinstrs -fast-isel=false | FileCheck -check-prefix=OPT %s
 
 ; Test the CFG stackifier pass.
 
 ; Explicitly disable fast-isel, since it gets implicitly enabled in the
 ; optnone test.
 
 target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown"

llvm/trunk/test/CodeGen/WebAssembly/mem-intrinsics.ll

-; RUN: llc < %s -asm-verbose=false -disable-wasm-fallthrough-return-opt | FileCheck %s
+; RUN: llc < %s -asm-verbose=false -disable-wasm-fallthrough-return-opt -tail-dup-placement=0| FileCheck %s
 
 ; Test memcpy, memmove, and memset intrinsics.
 
 target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
 declare void @llvm.memcpy.p0i8.p0i8.i32(i8* nocapture, i8* nocapture readonly, i32, i32, i1)
 declare void @llvm.memmove.p0i8.p0i8.i32(i8* nocapture, i8* nocapture readonly, i32, i32, i1)

llvm/trunk/test/CodeGen/X86/block-placement.ll

body4:
   %next = add i32 %iv, 1
   %exitcond = icmp eq i32 %next, %i
   br i1 %exitcond, label %exit, label %body1
 
 exit:
   ret i32 %sum
 }
 
+; Tail duplication during layout can entirely remove body0 by duplicating it
+; into the entry block and into body1. This is a good thing but it isn't what
+; this test is looking for. So to make the blocks longer so they don't get
+; duplicated, we add some calls to dummy.
+declare void @dummy()
+
 define i32 @test_loop_rotate(i32 %i, i32* %a) {
 ; Check that we rotate conditional exits from the loop to the bottom of the
 ; loop, eliminating unconditional branches to the top.
 ; CHECK-LABEL: test_loop_rotate:
 ; CHECK: %entry
 ; CHECK: %body1
 ; CHECK: %body0
 ; CHECK: %exit
 
 entry:
   br label %body0
 
 body0:
   %iv = phi i32 [ 0, %entry ], [ %next, %body1 ]
   %base = phi i32 [ 0, %entry ], [ %sum, %body1 ]
   %next = add i32 %iv, 1
   %exitcond = icmp eq i32 %next, %i
+  call void @dummy()
+  call void @dummy()
   br i1 %exitcond, label %exit, label %body1
 
 body1:
   %arrayidx = getelementptr inbounds i32, i32* %a, i32 %iv
   %0 = load i32, i32* %arrayidx
   %sum = add nsw i32 %0, %base
   %bailcond1 = icmp eq i32 %sum, 42
   br label %body0

 ;    strange layouts that are siginificantly less efficient, often times maing
 ;    it discontiguous.
 ;
 ; CHECK: @benchmark_heapsort
 ; CHECK: %entry
 ; First rotated loop top.
 ; CHECK: .p2align
 ; CHECK: %while.end
-; CHECK: %for.cond
+; %for.cond gets completely tail-duplicated away.
 ; CHECK: %if.then
 ; CHECK: %if.else
 ; CHECK: %if.end10
 ; Second rotated loop top
 ; CHECK: .p2align
 ; CHECK: %if.then24
 ; CHECK: %while.cond.outer
 ; Third rotated loop top

llvm/trunk/test/CodeGen/X86/cmov-into-branch.ll

 ; Either one should become a branch rather than conditional move.
 ; TODO: But likely true vs. likely false should affect basic block placement?
 define i32 @weighted_select3(i32 %a, i32 %b) {
 ; CHECK-LABEL: weighted_select3:
 ; CHECK:       # BB#0:
 ; CHECK-NEXT:    testl %edi, %edi
 ; CHECK-NEXT:    je [[LABEL_BB6:.*]]
 ; CHECK:         movl %edi, %eax
+; CHECK-NEXT:    retq
 ; CHECK:         [[LABEL_BB6]]
 ; CHECK-NEXT:    movl %esi, %edi
-; CHECK-NEXT:    jmp
+; CHECK-NEXT:    movl %edi, %eax
+; CHECK-NEXT:    retq
 ;
   %cmp = icmp ne i32 %a, 0
   %sel = select i1 %cmp, i32 %a, i32 %b, !prof !2
   ret i32 %sel
 }
 
 ; Weightlessness is no reason to die.
 define i32 @unweighted_select(i32 %a, i32 %b) {

llvm/trunk/test/CodeGen/X86/fma-intrinsics-phi-213-to-231.ll

 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+avx2,+fma | FileCheck %s
 
 ; CHECK-LABEL: fmaddsubpd_loop_128:
 ; CHECK:   vfmaddsub231pd %xmm1, %xmm0, %xmm2
-; CHECK:   vmovaps %xmm2, %xmm0
+; CHECK:   vmovapd %xmm2, %xmm0
 ; CHECK-NEXT: retq
 define <2 x double> @fmaddsubpd_loop_128(i32 %iter, <2 x double> %a, <2 x double> %b, <2 x double> %c) {
 entry:
   br label %for.cond
 
 for.cond:
   %c.addr.0 = phi <2 x double> [ %c, %entry ], [ %0, %for.inc ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
for.inc:
   br label %for.cond
 
 for.end:
   ret <2 x double> %c.addr.0
 }
 
 ; CHECK-LABEL: fmsubaddpd_loop_128:
 ; CHECK:   vfmsubadd231pd %xmm1, %xmm0, %xmm2
-; CHECK:   vmovaps %xmm2, %xmm0
+; CHECK:   vmovapd %xmm2, %xmm0
 ; CHECK-NEXT: retq
 define <2 x double> @fmsubaddpd_loop_128(i32 %iter, <2 x double> %a, <2 x double> %b, <2 x double> %c) {
 entry:
   br label %for.cond
 
 for.cond:
   %c.addr.0 = phi <2 x double> [ %c, %entry ], [ %0, %for.inc ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
for.inc:
   br label %for.cond
 
 for.end:
   ret <2 x double> %c.addr.0
 }
 
 ; CHECK-LABEL: fmaddpd_loop_128:
 ; CHECK:   vfmadd231pd %xmm1, %xmm0, %xmm2
-; CHECK:   vmovaps %xmm2, %xmm0
+; CHECK:   vmovapd %xmm2, %xmm0
 ; CHECK-NEXT: retq
 define <2 x double> @fmaddpd_loop_128(i32 %iter, <2 x double> %a, <2 x double> %b, <2 x double> %c) {
 entry:
   br label %for.cond
 
 for.cond:
   %c.addr.0 = phi <2 x double> [ %c, %entry ], [ %0, %for.inc ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
for.inc:
   br label %for.cond
 
 for.end:
   ret <2 x double> %c.addr.0
 }
 
 ; CHECK-LABEL: fmsubpd_loop_128:
 ; CHECK:   vfmsub231pd %xmm1, %xmm0, %xmm2
-; CHECK:   vmovaps %xmm2, %xmm0
+; CHECK:   vmovapd %xmm2, %xmm0
 ; CHECK-NEXT: retq
 define <2 x double> @fmsubpd_loop_128(i32 %iter, <2 x double> %a, <2 x double> %b, <2 x double> %c) {
 entry:
   br label %for.cond
 
 for.cond:
   %c.addr.0 = phi <2 x double> [ %c, %entry ], [ %0, %for.inc ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
for.inc:
   br label %for.cond
 
 for.end:
   ret <2 x double> %c.addr.0
 }
 
 ; CHECK-LABEL: fnmaddpd_loop_128:
 ; CHECK:   vfnmadd231pd %xmm1, %xmm0, %xmm2
-; CHECK:   vmovaps %xmm2, %xmm0
+; CHECK:   vmovapd %xmm2, %xmm0
 ; CHECK-NEXT: retq
 define <2 x double> @fnmaddpd_loop_128(i32 %iter, <2 x double> %a, <2 x double> %b, <2 x double> %c) {
 entry:
   br label %for.cond
 
 for.cond:
   %c.addr.0 = phi <2 x double> [ %c, %entry ], [ %0, %for.inc ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
for.inc:
   br label %for.cond
 
 for.end:
   ret <2 x double> %c.addr.0
 }
 
 ; CHECK-LABEL: fnmsubpd_loop_128:
 ; CHECK:   vfnmsub231pd %xmm1, %xmm0, %xmm2
-; CHECK:   vmovaps %xmm2, %xmm0
+; CHECK:   vmovapd %xmm2, %xmm0
 ; CHECK-NEXT: retq
 define <2 x double> @fnmsubpd_loop_128(i32 %iter, <2 x double> %a, <2 x double> %b, <2 x double> %c) {
 entry:
   br label %for.cond
 
 for.cond:
   %c.addr.0 = phi <2 x double> [ %c, %entry ], [ %0, %for.inc ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]

 declare <4 x float> @llvm.x86.fma.vfmsubadd.ps(<4 x float>, <4 x float>, <4 x float>)
 declare <4 x float> @llvm.x86.fma.vfmadd.ps(<4 x float>, <4 x float>, <4 x float>)
 declare <4 x float> @llvm.x86.fma.vfmsub.ps(<4 x float>, <4 x float>, <4 x float>)
 declare <4 x float> @llvm.x86.fma.vfnmadd.ps(<4 x float>, <4 x float>, <4 x float>)
 declare <4 x float> @llvm.x86.fma.vfnmsub.ps(<4 x float>, <4 x float>, <4 x float>)
 
 ; CHECK-LABEL: fmaddsubpd_loop_256:
 ; CHECK:   vfmaddsub231pd %ymm1, %ymm0, %ymm2
-; CHECK:   vmovaps %ymm2, %ymm0
+; CHECK:   vmovapd %ymm2, %ymm0
 ; CHECK-NEXT: retq
 define <4 x double> @fmaddsubpd_loop_256(i32 %iter, <4 x double> %a, <4 x double> %b, <4 x double> %c) {
 entry:
   br label %for.cond
 
 for.cond:
   %c.addr.0 = phi <4 x double> [ %c, %entry ], [ %0, %for.inc ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
for.inc:
   br label %for.cond
 
 for.end:
   ret <4 x double> %c.addr.0
 }
 
 ; CHECK-LABEL: fmsubaddpd_loop_256:
 ; CHECK:   vfmsubadd231pd %ymm1, %ymm0, %ymm2
-; CHECK:   vmovaps %ymm2, %ymm0
+; CHECK:   vmovapd %ymm2, %ymm0
 ; CHECK-NEXT: retq
 define <4 x double> @fmsubaddpd_loop_256(i32 %iter, <4 x double> %a, <4 x double> %b, <4 x double> %c) {
 entry:
   br label %for.cond
 
 for.cond:
   %c.addr.0 = phi <4 x double> [ %c, %entry ], [ %0, %for.inc ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
for.inc:
   br label %for.cond
 
 for.end:
   ret <4 x double> %c.addr.0
 }
 
 ; CHECK-LABEL: fmaddpd_loop_256:
 ; CHECK:   vfmadd231pd %ymm1, %ymm0, %ymm2
-; CHECK:   vmovaps %ymm2, %ymm0
+; CHECK:   vmovapd %ymm2, %ymm0
 ; CHECK-NEXT: retq
 define <4 x double> @fmaddpd_loop_256(i32 %iter, <4 x double> %a, <4 x double> %b, <4 x double> %c) {
 entry:
   br label %for.cond
 
 for.cond:
   %c.addr.0 = phi <4 x double> [ %c, %entry ], [ %0, %for.inc ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
for.inc:
   br label %for.cond
 
 for.end:
   ret <4 x double> %c.addr.0
 }
 
 ; CHECK-LABEL: fmsubpd_loop_256:
 ; CHECK:   vfmsub231pd %ymm1, %ymm0, %ymm2
-; CHECK:   vmovaps %ymm2, %ymm0
+; CHECK:   vmovapd %ymm2, %ymm0
 ; CHECK-NEXT: retq
 define <4 x double> @fmsubpd_loop_256(i32 %iter, <4 x double> %a, <4 x double> %b, <4 x double> %c) {
 entry:
   br label %for.cond
 
 for.cond:
   %c.addr.0 = phi <4 x double> [ %c, %entry ], [ %0, %for.inc ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
for.inc:
   br label %for.cond
 
 for.end:
   ret <4 x double> %c.addr.0
 }
 
 ; CHECK-LABEL: fnmaddpd_loop_256:
 ; CHECK:   vfnmadd231pd %ymm1, %ymm0, %ymm2
-; CHECK:   vmovaps %ymm2, %ymm0
+; CHECK:   vmovapd %ymm2, %ymm0
 ; CHECK-NEXT: retq
 define <4 x double> @fnmaddpd_loop_256(i32 %iter, <4 x double> %a, <4 x double> %b, <4 x double> %c) {
 entry:
   br label %for.cond
 
 for.cond:
   %c.addr.0 = phi <4 x double> [ %c, %entry ], [ %0, %for.inc ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
for.inc:
   br label %for.cond
 
 for.end:
   ret <4 x double> %c.addr.0
 }
 
 ; CHECK-LABEL: fnmsubpd_loop_256:
 ; CHECK:   vfnmsub231pd %ymm1, %ymm0, %ymm2
-; CHECK:   vmovaps %ymm2, %ymm0
+; CHECK:   vmovapd %ymm2, %ymm0
 ; CHECK-NEXT: retq
 define <4 x double> @fnmsubpd_loop_256(i32 %iter, <4 x double> %a, <4 x double> %b, <4 x double> %c) {
 entry:
   br label %for.cond
 
 for.cond:
   %c.addr.0 = phi <4 x double> [ %c, %entry ], [ %0, %for.inc ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]

llvm/trunk/test/CodeGen/X86/fp-une-cmp.ll

 define double @profile_metadata(double %x, double %y) {
 ; CHECK-LABEL: profile_metadata:
 ; CHECK:       # BB#0: # %entry
 ; CHECK-NEXT:    mulsd %xmm1, %xmm0
 ; CHECK-NEXT:    xorpd %xmm1, %xmm1
 ; CHECK-NEXT:    ucomisd %xmm1, %xmm0
 ; CHECK-NEXT:    jne .LBB1_1
 ; CHECK-NEXT:    jp .LBB1_1
-; CHECK-NEXT:  .LBB1_2: # %bb2
+; CHECK-NEXT:  # %bb2
 ; CHECK-NEXT:    retq
 ; CHECK-NEXT:  .LBB1_1: # %bb1
 ; CHECK-NEXT:    addsd {{.*}}(%rip), %xmm0
-; CHECK-NEXT:    jmp .LBB1_2
+; CHECK-NEXT:    retq
 
 entry:
   %mul = fmul double %x, %y
   %cmp = fcmp une double %mul, 0.000000e+00
   br i1 %cmp, label %bb1, label %bb2, !prof !1
 
 bb1:
   %add = fadd double %mul, -1.000000e+00

llvm/trunk/test/CodeGen/X86/pr11202.ll

l1:                                               ; preds = %l2, %entry
   %a = zext i1 false to i32
   br label %l2
 
 l2:                                               ; preds = %l1
   %b = zext i1 false to i32
   br label %l1
 }
 
-; CHECK: .Ltmp0:                                 # Address of block that was removed by CodeGen
+; It is correct for either l1 or l2 to be removed.
+; If l2 is removed, the message should be "Address of block that was removed by CodeGen"
+; If l1 is removed, it should be "Block address taken."
+; CHECK: .Ltmp0:                                 # {{Address of block that was removed by CodeGen|Block address taken}}
 ; CHECK: .quad  .Ltmp0

llvm/trunk/test/CodeGen/X86/ragreedy-bug.ll

 ; RUN: llc < %s -mtriple=x86_64-apple-macosx -regalloc=greedy | FileCheck %s
 
 ; This testing case is reduced from 197.parser prune_match function.
 ; We make sure register copies are not generated on isupper.exit blocks.
 
-; CHECK: isupper.exit
+; isupper.exit and isupper.exit223 get tail-duplicated into all their
+; predecessors.
+; CHECK: cond.true.i.i
 ; CHECK-NEXT: in Loop
+; Mem-move
+; CHECK-NEXT: movl
+; CHECK-NEXT: andl
 ; CHECK-NEXT: testl
 ; CHECK-NEXT: jne
-; CHECK: isupper.exit
+; CHECK: cond.true.i.i217
 ; CHECK-NEXT: in Loop
+; Mem-move
+; CHECK-NEXT: movl
+; CHECK-NEXT: andl
 ; CHECK-NEXT: testl
 ; CHECK-NEXT: je
+; CHECK: cond.false.i.i
 ; CHECK: maskrune
+; CHECK-NEXT: movzbl
+; CHECK-NEXT: movzbl
+; CHECK-NEXT: testl
+; CHECK-NEXT: je
+; CHECK: cond.false.i.i219
 ; CHECK: maskrune
+; CHECK-NEXT: movzbl
+; CHECK-NEXT: movzbl
+; CHECK-NEXT: testl
+; CHECK-NEXT: jne
 
 %struct.List_o_links_struct = type { i32, i32, i32, %struct.List_o_links_struct* }
 %struct.Connector_struct = type { i16, i16, i8, i8, %struct.Connector_struct*, i8* }
 %struct._RuneLocale = type { [8 x i8], [32 x i8], i32 (i8*, i64, i8**)*, i32 (i32, i8*, i64, i8**)*, i32, [256 x i32], [256 x i32], [256 x i32], %struct._RuneRange, %struct._RuneRange, %struct._RuneRange, i8*, i32, i32, %struct._RuneCharClass* }
 %struct._RuneRange = type { i32, %struct._RuneEntry* }
 %struct._RuneEntry = type { i32, i32, i32, i32* }
 %struct._RuneCharClass = type { [14 x i8], i32 }
 %struct.Exp_struct = type { i8, i8, i8, i8, %union.anon }

llvm/trunk/test/CodeGen/X86/sse1.ll

 define <4 x float> @vselect(<4 x float>*%p, <4 x i32> %q) {
 ; X32-LABEL: vselect:
 ; X32:       # BB#0: # %entry
 ; X32-NEXT:    cmpl $0, {{[0-9]+}}(%esp)
 ; X32-NEXT:    xorps %xmm0, %xmm0
 ; X32-NEXT:    je .LBB1_1
 ; X32-NEXT:  # BB#2: # %entry
 ; X32-NEXT:    xorps %xmm1, %xmm1
-; X32-NEXT:    jmp .LBB1_3
+; X32-NEXT:    cmpl $0, {{[0-9]+}}(%esp)
+; X32-NEXT:    jne .LBB1_5
+; X32-NEXT:    jmp .LBB1_4
 ; X32-NEXT:  .LBB1_1:
 ; X32-NEXT:    movss {{.*#+}} xmm1 = mem[0],zero,zero,zero
-; X32-NEXT:  .LBB1_3: # %entry
 ; X32-NEXT:    cmpl $0, {{[0-9]+}}(%esp)
 ; X32-NEXT:    je .LBB1_4
-; X32-NEXT:  # BB#5: # %entry
+; X32-NEXT:  .LBB1_5: # %entry
 ; X32-NEXT:    xorps %xmm2, %xmm2
-; X32-NEXT:    jmp .LBB1_6
+; X32-NEXT:    cmpl $0, {{[0-9]+}}(%esp)
+; X32-NEXT:    jne .LBB1_8
+; X32-NEXT:    jmp .LBB1_7
 ; X32-NEXT:  .LBB1_4:
 ; X32-NEXT:    movss {{.*#+}} xmm2 = mem[0],zero,zero,zero
-; X32-NEXT:  .LBB1_6: # %entry
 ; X32-NEXT:    cmpl $0, {{[0-9]+}}(%esp)
 ; X32-NEXT:    je .LBB1_7
-; X32-NEXT:  # BB#8: # %entry
+; X32-NEXT:  .LBB1_8: # %entry
 ; X32-NEXT:    xorps %xmm3, %xmm3
 ; X32-NEXT:    jmp .LBB1_9
 ; X32-NEXT:  .LBB1_7:
 ; X32-NEXT:    movss {{.*#+}} xmm3 = mem[0],zero,zero,zero
 ; X32-NEXT:  .LBB1_9: # %entry
 ; X32-NEXT:    cmpl $0, {{[0-9]+}}(%esp)
 ; X32-NEXT:    unpcklps {{.*#+}} xmm2 = xmm2[0],xmm3[0],xmm2[1],xmm3[1]
 ; X32-NEXT:    jne .LBB1_11
 ; X32-NEXT:  # BB#10:
 ; X32-NEXT:    movss {{.*#+}} xmm0 = mem[0],zero,zero,zero
 ; X32-NEXT:  .LBB1_11: # %entry
 ; X32-NEXT:    unpcklps {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1]
 ; X32-NEXT:    unpcklps {{.*#+}} xmm0 = xmm0[0],xmm2[0],xmm0[1],xmm2[1]
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: vselect:
 ; X64:       # BB#0: # %entry
 ; X64-NEXT:    testl %ecx, %ecx
 ; X64-NEXT:    xorps %xmm0, %xmm0
 ; X64-NEXT:    je .LBB1_1
 ; X64-NEXT:  # BB#2: # %entry
 ; X64-NEXT:    xorps %xmm1, %xmm1
-; X64-NEXT:    jmp .LBB1_3
+; X64-NEXT:    testl %edx, %edx
+; X64-NEXT:    jne .LBB1_5
+; X64-NEXT:    jmp .LBB1_4
 ; X64-NEXT:  .LBB1_1:
 ; X64-NEXT:    movss {{.*#+}} xmm1 = mem[0],zero,zero,zero
-; X64-NEXT:  .LBB1_3: # %entry
 ; X64-NEXT:    testl %edx, %edx
 ; X64-NEXT:    je .LBB1_4
-; X64-NEXT:  # BB#5: # %entry
+; X64-NEXT:  .LBB1_5: # %entry
 ; X64-NEXT:    xorps %xmm2, %xmm2
-; X64-NEXT:    jmp .LBB1_6
+; X64-NEXT:    testl %r8d, %r8d
+; X64-NEXT:    jne .LBB1_8
+; X64-NEXT:    jmp .LBB1_7
 ; X64-NEXT:  .LBB1_4:
 ; X64-NEXT:    movss {{.*#+}} xmm2 = mem[0],zero,zero,zero
-; X64-NEXT:  .LBB1_6: # %entry
 ; X64-NEXT:    testl %r8d, %r8d
 ; X64-NEXT:    je .LBB1_7
-; X64-NEXT:  # BB#8: # %entry
+; X64-NEXT:  .LBB1_8: # %entry
 ; X64-NEXT:    xorps %xmm3, %xmm3
 ; X64-NEXT:    jmp .LBB1_9
 ; X64-NEXT:  .LBB1_7:
 ; X64-NEXT:    movss {{.*#+}} xmm3 = mem[0],zero,zero,zero
 ; X64-NEXT:  .LBB1_9: # %entry
 ; X64-NEXT:    testl %esi, %esi
 ; X64-NEXT:    unpcklps {{.*#+}} xmm2 = xmm2[0],xmm3[0],xmm2[1],xmm3[1]
 ; X64-NEXT:    jne .LBB1_11

llvm/trunk/test/CodeGen/X86/tail-dup-repeat.ll

+; RUN: llc -O2 -tail-dup-placement-threshold=4 -o - %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: uwtable
+; When tail-duplicating during placement, we work backward from blocks with
+; multiple successors. In this case, the block dup1 gets duplicated into dup2
+; and if.then64, and then the block dup2 gets duplicated into land.lhs.true
+; and if.end70
+; CHECK-LABEL: repeated_tail_dup:
+define void @repeated_tail_dup(i1 %a1, i1 %a2, i32* %a4, i32* %a5, i8* %a6) #0 align 2 {
+entry:
+  br label %for.cond
+
+; CHECK: {{^}}.[[HEADER:LBB0_[1-9]]]: # %for.cond
+for.cond:                                         ; preds = %dup1, %entry
+  br i1 %a1, label %land.lhs.true, label %if.end56
+
+land.lhs.true:                                    ; preds = %for.cond
+  store i32 10, i32* %a4, align 8
+  br label %dup2
+
+if.end56:                                         ; preds = %for.cond
+  br i1 %a2, label %if.then64, label %if.end70
+
+if.then64:                                        ; preds = %if.end56
+  store i8 1, i8* %a6, align 1
+  br label %dup1
+
+; CHECK:      # %if.end70
+; CHECK-NEXT: # in Loop:
+; CHECK-NEXT: movl $12, (%rdx)
+; CHECK-NEXT: movl $2, (%rcx)
+; CHECK-NEXT: testl %eax, %eax
+; CHECK-NEXT: je .[[HEADER]]
+if.end70:                                         ; preds = %if.end56
+  store i32 12, i32* %a4, align 8
+  br label %dup2
+
+dup2:                                             ; preds = %if.end70, %land.lhs.true
+  store i32 2, i32* %a5, align 4
+  br label %dup1
+
+dup1:                                             ; preds = %dup2, %if.then64
+  %val = load i32, i32* %a4, align 8
+  %switch = icmp ult i32 undef, 1
+  br i1 %switch, label %for.cond, label %for.end
+
+for.end:                                          ; preds = %dup1
+  ret void
+}
+
+attributes #0 = { uwtable }

llvm/trunk/test/CodeGen/X86/update-terminator.mir

 # RUN: llc -march=x86-64 -verify-machineinstrs -run-pass block-placement -o - %s | FileCheck %s
 # Check the conditional jump in bb.1 is changed to unconditional after block placement swaps bb.2 and bb.3.
 
 --- |
   @a = external global i16
   @b = external global i32
 
+  declare void @dummy1()
+  declare void @dummy2()
+  declare void @dummy3()
+
   ; Function Attrs: nounwind
   define void @f2() {
     br i1 undef, label %bb1, label %bb3
 
   bb1:
+    call void @dummy1()
+    call void @dummy1()
+    call void @dummy1()
     br i1 undef, label %bb2, label %bb2
 
   bb2:
+    call void @dummy2()
+    call void @dummy2()
+    call void @dummy2()
     br label %bb4
 
   bb3:
+    call void @dummy3()
+    call void @dummy3()
+    call void @dummy3()
     br label %bb2
 
   bb4:
     ret void
   }
 
 
 ...
 ---
 # CHECK-LABEL: name: f2
 # CHECK: bb.1:
 # CHECK: JMP_1 %bb.2
 # CHECK: bb.3:
 # CHECK: bb.2:
 name:            f2
 body:             |
   bb.0 (%ir-block.0):
     successors: %bb.1(50), %bb.3(50)
 
     JNE_1 %bb.1, implicit %eflags
     JMP_1 %bb.3
   bb.1:
     successors: %bb.2(100)
 
+    CALL64pcrel32 @dummy1, csr_64, implicit %rsp, implicit-def %rsp
+    CALL64pcrel32 @dummy1, csr_64, implicit %rsp, implicit-def %rsp
+    CALL64pcrel32 @dummy1, csr_64, implicit %rsp, implicit-def %rsp
     JNE_1 %bb.2, implicit %eflags
 
   bb.2:
     successors: %bb.4(100)
 
+    CALL64pcrel32 @dummy2, csr_64, implicit %rsp, implicit-def %rsp
+    CALL64pcrel32 @dummy2, csr_64, implicit %rsp, implicit-def %rsp
+    CALL64pcrel32 @dummy2, csr_64, implicit %rsp, implicit-def %rsp
     JMP_1 %bb.4
 
   bb.3:
     successors: %bb.2(100)
+    CALL64pcrel32 @dummy3, csr_64, implicit %rsp, implicit-def %rsp
+    CALL64pcrel32 @dummy3, csr_64, implicit %rsp, implicit-def %rsp
+    CALL64pcrel32 @dummy3, csr_64, implicit %rsp, implicit-def %rsp
     JMP_1 %bb.2
 
   bb.4:
     RETQ
 
 ...