Enhance loop rotation with existence of profile data in MachineBlockPlacement pass.

[congh]

Summary

Currently, in MachineBlockPlacement pass the loop is rotated to let the best exit to be the last BB in the loop chain, to maximize the fall-through from the loop to outside. With profile data, we can determine the cost in terms of missed fall through opportunities when rotating a loop chain and select the best rotation. Basically, there are three kinds of cost to consider for each rotation:

1. The possibly missed fall through edge (if it exists) from BB out of the loop to the loop header.
2. The possibly missed fall through edges (if they exist) from the loop exits to BB out of the loop.
3. The missed fall through edge (if it exists) from the last BB to the first BB in the loop chain.

Therefore, the cost for a given rotation is the sum of costs listed above. We select the best rotation with the smallest cost. This is only for PGO mode when we have more precise edge frequencies.

[chandlerc]

Will try to get to this patch soon, but if you haven't yet, you should
start working on some reduced test cases similar to the existing ones to
use in conjunction with this mode.

[congh]

I have added a test case for this patch, which checks whether the loop will be rotated if there is profile data for the function so that the hot back edge will become fall-through.

[congh]

Bug fix for checking if a function has profile data (from using hasMetadata() to getEntryCount()).

[congh]

Update the patch to consider the cost of unconditional jump from outside of the loop to the loop header.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

250

Why changing this interface at all? There does not seem to be necessary.

761

ExistingBB is already computed in the caller, there is no need for the interface change here ..

797

Though equivalent, but it might be more readable if it computes 'benefit/savings' in terms of the fall through opportunities instead of the cost. For instance, in the following three items, 1 and 2 are really savings that come with the rotation, and 3 is the saving that will be lost with the candidate layout (including the original layout before the rotation).

818

Why is this loop outside of the following loop? I expect each new candidate loop header to have a chance to check the fall through opportunity and related saving/cost.

821

If the previous chain does not end up connecting with this new top block in the current loop chain, then the benefit of the fall through won't be materializable, for instance when the Pred has more than 1 successors and the other successor is also a chain lead.

828

I think the adjustment should be done the other way:

when num of successors > 1, the cost will be adjust to the minimal freq of the Pred's outgoing edge -- that is where the unconditional jump will be inserted (assuming the fall through path is the hottest one)

846

See the previous comment. Even when Iter is not the current Head, it may still have fall through opportunity.

855

Do you also want to check if the Succ block has more than one incoming edges. If it has more than one incoming edges, need to make sure 'Succ' block's other predecessor is not a tail of another chain that can be connnected with 'Succ'.

870

This needs more explanation.

939

I suggest adding another intern option to guard this.

if (UseProfileBasedCostAnalysis && F.getFunction()->getEntryCount()) ...

941

the check does not seem necessary. If LoopTop == header, ExitingBB will be null.

[congh]

lib/CodeGen/MachineBlockPlacement.cpp

250

This is only an internal "interface". The reason why I moved the computation of ExitingBB to inside of this function is because ExitingBB is only needed by rotateLoop and it doesn't make sense to compute it outside of this function. This makes the logic more compact and clear: it is rotateLoop but not buildLoopChains who needs ExitingBB.

250

I just checked this part again, and I found I was wrong: the exiting BB is calculated before building the loop chain. This should be guaranteed as when finding best exit BB it is assumed that BBs haven't been merged to the loop chain. I will update the patch by rolling this part back.

761

Please see my comment above.

797

Agree. I will update the comment.

818

Here we only consider natural loops, which have only one entry (loop header). As there is only one loop header, we only need to compute the fall-through once. We only check this benefit if the loop top is the loop header.

821

That is right. But at this point we haven't started to build chains outside of this loop. It is difficult to tell if Pred will or will not be connected to the loop header. This is just a heuristic-like optimization. We could not guarantee global optimal result.

828

Consider a two-way branch from Pred with frequencies x and y, and x is the frequency from Pred to the loop header. When x > y, and the edge is not fall-thru, then the number of jumps is x + y + y, and branch cost is x + y; if it is a fall-thru, the number of jumps is x + y, and the branch cost is y. If we take the weight of branch cost and jump instruction to be the same, then we can save x+y by making that edge fall-thru.

If x < y, the edge from Pred to the loop header won't be fall-thru and we save nothing.

So the conclusion is: if num of successors > 1 and the edge from Pred to the loop header is the most frequent one, then making this edge fall-thru can save us the freq of Pred. If that edge is not the most frequent one, we could save nothing. If num of successors == 1, we can save 2x freq of Pred.

846

The fall-thru from Pred to another successor that is not the header? Then loop rotation won't affect that fall-thru.

855

The function findBestLoopExit() doesn't consider this possibility. If we check this, should we go ahead and check if the source of the more frequent incoming edge has a more frequent outgoing edge... I am afraid this may make things too complicated.

939

OK.

941

This is because I changed the position of findBestLoopExit(). As I will resume its position, I will also update this part.

[congh]

The updated patch according to David's comments.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

818

Ok -- a comment there about that will be useful.

821

Is it worthwhile considering doing loop rotation after all chains have been formed?

828

case 1: num_successors (Pred) == 2, and x > y

if Pred->Header edge is not the fall through, assuming the other edge will become a fall through edge , then the costs will be:

1. number of jumps executed: (x+y), cost of jump is C1
2. number of taken branches: x, cost of branch taken is C2:

Total cost: C1* (x+y) + C2* x

if Pred->Header edge is the fall through,

1. number of jumps executed: (x+y)
2. number of taken branches: y

Total cost: C1 * (x+y) + C2 * y

so the saving (of keeping the Pred->header fall through) is C2 * (x - y)

case 2: number of successors (Pred) == 2, x < y

The saving of keeping Pred->header to be fall through is still C2 * (x - y ), but negative.

case 3: number of successors (Pred) == 1

Keeping the fall through, the total cost is 0, while not keeping the fall through the cost is (C1+C2)*x

Conclusion
a) when number of successors > 1, the real cost of not doing the fall through should be adjusted to C2 * (x-y)
b) when the number of successors == 1, your estimate is correct, assuming C1 == C2
c) better introduce a cost parameter for type1 and type2

846

This is explained by you -- only natural loop is considered.

855

you need keep an eye on it and consider not doing loop rotation on the fly and chain merging on the fly. The decision of rotation and how chains are merged/connected need to be made together.

941

Another question is: if the current layout algorithm finds a different 'best' loop top than the header, than the profile driven/cost based rotation will be suppressed, which is not desirable.

[davidxl]

Cong, the proposed cost analysis can not handle diamond shaped or loops with more complicated control flow. To handle those cases, I think you need to generalize it by computing the complete branch costs for all rotation candidates and select the one with the least cost. The entry and exit connection cost computation remains the same. To compute taken branch cost, there are only 4 cases to consider: tail BB with 1 successor, tail BB multiple successors, non-tail BB with 1 successor, non-tail BB with multiple successors.

B0
do {
B1
if (..) {

B2

} else {

B3

}
B4
} while (..);
B5;

If the original layout keeps the topo order:
B0 B1 B2 B3 B4 B5

The cost analysis should discover the optimal rotation to be
B0 B3 B4 B1 B2 B5

[congh]

lib/CodeGen/MachineBlockPlacement.cpp

818

OK. Thanks!

821

If all chains are already formed, loop rotation may not be done as BBs outside of the loop are already merged into chains. For example, BBs just after loops' exits may not be chain tops. I thinks LLVM's bottom-up method makes sense here.

828

Note that here we focus on loop rotation. In the case of x > y, the other edge with frequency y won't become a fall through edge. If the header is not the chain top, then Pred will chose another loop BB other than the header or the other successor outside of the loop as its successor in the layout. That is why the number of jumps executed is x + y + y (in this case there both of its CFG successors are not fall-thru so there are two jumps).

Following this analysis (as in my last post), we could see that we can save (C1 + C2) * y by making the header as the top of the loop chain.

855

In LLVM' current bottom-up algorithm, those two processes are separated by design. Even we delay the loop rotation until forming chains outside of it, if it has several exits, the situation is still complicated (single-entry single-exit loops are much easier to handle as they can be reduced to one CFG node). The loop rotation algorithm is based on the heuristic that the loop exit at the chain bottom are much likely to have a fall-thru edge to the outside.

870

Done.

941

Actually, if we use the profile based loop rotation algorithm, we could discard the current method to find the best loop top and exit. This is because our algorithm already considers them.

[congh]

In D10717#196064, @davidxl wrote:

Cong, the proposed cost analysis can not handle diamond shaped or loops with more complicated control flow. To handle those cases, I think you need to generalize it by computing the complete branch costs for all rotation candidates and select the one with the least cost. The entry and exit connection cost computation remains the same. To compute taken branch cost, there are only 4 cases to consider: tail BB with 1 successor, tail BB multiple successors, non-tail BB with 1 successor, non-tail BB with multiple successors.

B0
do {
B1
if (..) {

B2

} else {

B3

}
B4
} while (..);
B5;

If the original layout keeps the topo order:
B0 B1 B2 B3 B4 B5

The cost analysis should discover the optimal rotation to be
B0 B3 B4 B1 B2 B5

As we know, the current LLVM's algorithm always form a chain with all BBs in a loop, which is a drawback. I will propose another patch that changes this behavior. In the new algorithm, the loop chain formation may stop as long as an exit is reached, and only this loop chain will be rotated. This is similar to GCC's strategy. In the above example, once B1->B3->B4 is formed, the loop chain build is complete. Then B1 is the best candidate to be the chain bottom as there is an fall-thru edge from B1 to B2.

[congh]

Add one more test case with a diamond structure in the loop.

[congh]

Update the patch with the new cost analysis of the tail to head in the loop chain.

[congh]

Update the patch by adding two opt parameters that define the cost of misfetch and jump instruction, and use them when rotating loops.

[congh]

Added one more test case with a nested loop.

Chandler, could you please take a look at this patch and see if it is ready to commit?

[chandlerc]

Sorry for delays getting to this patch.

lib/CodeGen/MachineBlockPlacement.cpp

84–86

This seems confusing to me. We use profile data to guide many parts of block placement. This flag doesn't guard most of them. Could you select a more accurate name?

89–92

It might be useful to clarify that this cost models the probabalistic risk of an *instruction* misfetch due to a jump relative to falling through?

94–96

We have lots of existing measures of the cost of an instruction already. It would probably help to clarify this is a weight specifically designed to fit with the scale of the misfetch cost above? Not really sure how important it is to be able to tune these two costs independently.

269–271

My assumption is that the flag is expected to go away at some point. As such, I wouldn't embed a predicate here. I would sink this into the code that actually needs to test these properties to make decisions.

815–826

"we could determine" -> "we can determine"

Also, I find the mixture of "benefit" and "cost" confusing in this comment. I would try to use more clear terms here.

831

Please don't use floating point to compute these kinds of things.

We would like LLVM to not depend no the vagaries of the FPU and would like to avoid any possible numerical instability manifesting as non-deterministic compiles.

Instead, you should compute things using the BlockFrequency and BranchProbability abstract units which do the fixed-point math for you.

846–849

Why is a conditional jump's benefit not considered?

854–856

There is no comment explaining the actual algorithm at this point. Please add one. Especially with a loop structure this complex (three iterators??) it would help to give the reader some context for how this loop is supposed to operate.

868

This seems to be a *cost* rather than a benefit?

877–879

You should compute the max edge probability, and factor in the frequency outside of the loop.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

84–86

yes -- something like

'precise-rotation-cost' would be clearer.

[congh]

lib/CodeGen/MachineBlockPlacement.cpp

84–86

I have chosen the name suggested by David.

89–92

I have updated the description following your suggestion.

94–96

OK. I have updated the description.

We actually only need one ratio between those two costs. But I think it would be more clear to give two costs separately in case we need other costs in the future (like mispredicate?).

269–271

OK. Now this is only called once and it is OK to "inline" this function there.

815–826

You are right. I have updated the comment by clearly stating which item is a benefit and which one is a cost.

831

Thanks for explaining the background! I have used a pair of BlockFrequency to express benefit and cost respectively.

846–849

You mean when Pred->succ_size() > 1? In that case we assume Pred will have the other successor as the layout successor, which is very likely to happen, and then we will save nothing (there are some cases that we can guess at this point that Pred won't have the other successor as fall-through. We could do this optimization here but I think it makes the analysis too complicated).

854–856

OK. I have added a comment explains what this loop does. The TailIter is also described just below this statement.

868

This is a benefit because then we have a fallthrough from a block outside of the loop to the loop header. I think my comment here is incorrect and sorry about it (it is corrected now).

877–879

Yes, this is more efficient. Done.

[congh]

Chandler, I have updated the patch according to your comments. PTAL. Thanks!

[chandlerc]

lib/CodeGen/MachineBlockPlacement.cpp

815–826

I think it would be clearer to talk *only* in terms of cost. Below, when computing it, you can add and subtract costs to find the minimum.

Consider wording along the lines of:

There are three costs we want to minimize stemming from a jump rather than a fall through edge:

1. Entering the loop,
2. Exiting the loop, and
3. Continuing to loop by returning to the header.

Does that make sense? If not, then maybe I'm misunderstanding what you're trying to say more fundamentally.

833–837

As above, I think it would be useful to have just cost, and to use the natural addition and subtraction to find the minimum cost rotation.

Also, "hopefully there is no overflow" seems a bad sign. We should *definitely* have no overflow, and I think it makes sense to add asserts and such to enforce that.

846–849

I'm curious what data makes you confident that the other successor will end up the layout successor?

It seems strange to me to assume that because there are more than one successors of the non-loop-predecessor of the header, the loop header won't be the layout-successor. Naively, I would expect a common pattern of:

E --
|   |
|   v
|   LH <-
|   |    |
|   v    |
|   L2 --
|   |
v   |
X <-

Where LH is the loop header, and E is the entering block and X is the exit block. With this, it is perfectly conceivable that LH would be the layout successor of E.

901

Tragically, this loop is still quadratic in complexity.

getEdgeProbability is really inefficient when queried in this way. You can find other code in this file to compute the best successor probability without hitting this quadratic behavior. We should really figure out an API for this in BPI but for now, I would suggest extracting a helper and using it here.

911–915

What if one of the successors is outside the loop?

(Also, please add a test case covering this?)

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

815–826

More precisely, the objective is to find a rotation with minimal overall cost or equivalently maximal the overall benefit. The cost/benefit function has 3 components.

833–837

Cong is actually computing the overall benefit and maximize it.

Cong, It is equivalent to compute cost only -- simply change it to LoopExternalConnectionCost. For rotation with positive benefit in current patch, the connection cost will be 0, while for rotation with no benefit, the connection cost will be the branch freq to the head (or branch out freq)

846–849

I believe I raised similar question before (see comment and replies at line 818). I think the problem is that we can not be very sure if this loop's header will or will not be the layout successor of E due to the loop based layout ordering constraint (In fact in your example, unless the branch is highly biased towards LH, it is likely X will be the layout successor of E).

That is why I proposed at some point that loop rotation be done when base layout is done for the function -- however that may require too big a change.

It might worth considering obvious beneficial conditional jump here.

901

yes -- can consider computing TailBB's sum weight outside the loop.

911–915

this should not matter.

914

I don't think this formula is correct. The correct formula is

(x-x')*MisfetchCost + y*JumpInstrCost

Where x' is the frequency of the edge from the tail node to the block which is not its layout successor (before the rotation).

[congh]

lib/CodeGen/MachineBlockPlacement.cpp

815–826

Yes. This makes more sense. But from the implementation aspect, BlockFrequency doesn't provide subtract operation. This is why I use both benefit and cost. I could scale down all frequencies so that I can use signed 64bit integer to calculate the cost or benefit.

833–837

The arithmetic operation defined in BlockFrequency already considers overflow, but it may return the saturated result, which may not be what we want. I may have to use the similar way that is used in getSumForBlock() to prevent potential overflow.

833–837

David, I am not clear how LoopExternalConnectionCost is working: do we only need this cost, or do we have other cost/benefit? I ask this because there may exist more than one rotation that is beneficial.

846–849

Without knowing the layout outside of the loop, we do not know if the loop header will or will not be the layout-successor of its predecessor outside of the loop. However, this is the case when we do loop rotation (unless we change the design as suggested by David). But if a loop has many iterations, the benefit of the loop header's fall-through would be trivial comparing to the cost from the loop chain's tail to its head (similar assumption for the exit fall-through). If not, the fall-through to the loop header is very important to the overall cost and we'd better hope that the fall-through will be there in the final layout. That is why I think that we should always take this fall-through into consideration.

901

Yes, thanks for pointing it out. I will calculate the sum of weight outside of the loop to avoid redundant calculations.

I will consider to design an API in BPI to help us here.

911–915

That would be an exit and the exit fall-through is also considered here. I will add a test case about it (maybe a loop with several exits with different frequencies).

914

We don't have to compare each rotation with the current layout before rotation. We just calculate its own cost. Your formula is equivalent to the current one: you subtract x' * MisfetchCost from every rotation (so the layout before rotation is x' - x' = 0 here).

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

833–837

For each loop rotation, the entry-connection cost will be the sum of frequencies (multiplied by misfetch cost) of all incoming edges that are not 'fall through' edges. Similarly, the exit-connection cost can be computed.

914

What is needed is the cost introduced due to the rotation, however my version of the cost function is indeed incorrect. We can actually prove it is the following:

(x*MisFetchCost + min(x,y)*JumpInstCost)*TailNodeFreq

Note that this is slightly different from yours -- x is not the larger of the probabilities, but the original fall through probability. The second term is the same.

Suppose before the rotation, the layout is
... BB1,... TailBB, BB2

where TailBB is ended with 'jcc BB1'. The fall through (not taken) prob is x, and taken probability is y.

After rotation, the layout is
BB2, ... BB1, .. TailBB.

There are two cases:

1. x > y. The jump instructions added to TailBB will be jcc' BB2 followed by direct jump: jmp BB1

Rotation cost will be: x*MisFetchCost + y*MisFetchCost + y *JumpInstCost - y*MisFetchCost = x*MisFetchCost + y * JumpInstCost

2. x < y, The jump instructions added will be jcc BB1 + jmp BB2

rotation cost is: x * MisFetchCost + x*JumpInstCost

Combine 1) and 2),

[congh]

lib/CodeGen/MachineBlockPlacement.cpp

833–837

I just understand how to define LoopExternalConnectionCost: a loop rotation with the chain head that is not the loop header will have this cost, which actually is equal to the benefit I am now using. But I don't agree with your latest definition of it: we only need to consider the frequency of the potential fall-through edge from the header's predecessor to the header.

914

Yes, your analysis is correct. Originally I assume x >= y as I assume when BB2 is chosen to be the layout-successor of TailBB during loop chain build, it has larger edge frequency than other edges. However, I found this assumption may not hold (considering critical edge cases). I will update the code following your analysis. Thanks a lot!

[congh]

lib/CodeGen/MachineBlockPlacement.cpp

833–837

Also, I found it difficult to calculate the exit-connection cost: there may exist several exits in the loop, and at first we don't know how much cost should be given to each rotation. Even we find the largest exit frequency from another loop, we could not avoid subtract operation on costs (represented by BlockFrequency without this operation defined) when a rotation has a tail block with an exit edge that is less frequent.

I am now afraid that in order to unify cost and benefit we may pay more here.

[congh]

Measure the loop rotation only in cost instead of cost+benefit.

Improve the inefficient code that computes branch probabilities.

[congh]

Ping on this patch?

[congh]

Update the patch by skipping getting best loop top and exit when profile data is available.

PTAL.

[congh]

Ping?

[djasper]

Just a minor comment about the wording of the options. Otherwise, I don't think I'll add much to the reviews by both Chandler and David.

lib/CodeGen/MachineBlockPlacement.cpp

93

In what way is the cost "relative"?

In my understanding, this can either mean that it is a difference or a ratio. In either case "unsigned" would be a weird data type.

99

Same as above, what do you actually mean by "relative"?

[congh]

Thanks for reviewing those patches, Daniel! (Sorry for the delayed reply as I just came back from vacation).

lib/CodeGen/MachineBlockPlacement.cpp

93

Here we assume that fall-through will have zero cost comparing to 1 for non-fall-through. As this is not a "relative" cost, I have updated this description to:

Cost that models the probabilistic risk of an instruction misfetch due to a jump comparing to falling through, whose cost is zero.

99

This is a relative cost: if the cost of a misfetch is 1, then we assume the cost of a jump instruction is also 1 (we can adjust those two options to change their ratio if necessary).

[congh]

Update the patch according to Daniel's comment.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

92

Fix typo: probabilistic.

99

From the way this parameter is used below, it does not look like a relative cost, but more absolute cost.

840

Why not just multiply with Scale?

853

Why is the result called 'Freq' -- it should really be the cost.

891

Fix indentation.

920

Fix the comment. It is not 'we still get an additional ..', but 'we may still get an additional jmp if the exit bb does not have its target as the layout successor'.

923

chair --> chain

936

does this not consider the case when a direct jump is not needed?

[congh]

lib/CodeGen/MachineBlockPlacement.cpp

99

OK. I will remove the word "relative" here.

840

There is no operator * defined between a BlockFrequency and an integer. Also, this / operator is defined to be saturating. I will add a comment for explanation.

853

I think it is due to some historic reason. Fixed.

891

This is the result from running clang-format.

920

Note that we are sure that the two BBs involved here were layout together before, and the second one is a successor of the first one. So we are sure that there will be an additional jump.

936

This should not happen. For this rotation, the TailBB is the tail and its layout successor must be a BB that is outside of the loop chain.

[congh]

Update the patch according to David's comment.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

920

The situation is

TailBB->currentChainHead
TailBB->OtherSucessor

After rotation, TailBB->OtherSuccessor may be a fall through, so there is no need for a jump for that case. If OtherSuccessor is inside the chain, then a jmp is definitely needed.

[congh]

lib/CodeGen/MachineBlockPlacement.cpp

920

OK. This makes sense. As we don't know the layout successor of the loop chain, we only need to update this comment.

[congh]

Update the patch by fixing a comment.

[davidxl]

This version LGTM as it is not enabled by default yet. There are a couple of followups to do:

1. collect extensively performance data (including PMU perf data), and possibly tune the parameters (for selected targets)
2. turn it on by default when tuning is done

3. think about how to better handle loop rotation cost analysis with the right ordering --- current way (from inside out) is less than ideal, as the compiler has to guess how header/exit blocks are connected with blocks in the enclosing chain (it has not been laid out yet).

lib/CodeGen/MachineBlockPlacement.cpp

static cl::opt<bool> OutlineOptionalBranches(
     cl::init(false), cl::Hidden);
 
 static cl::opt<unsigned> OutlineOptionalThreshold(
     "outline-optional-threshold",
     cl::desc("Don't outline optional branches that are a single block with an "
              "instruction count below this threshold"),
     cl::init(4), cl::Hidden);
 
+static cl::opt<bool> UseProfileBasedCostAnalysis(
+    "use-profile-based-cost-analysis",
+    cl::desc("Use profile data to guide machine block placement."),
+    cl::init(false), cl::Hidden);
+
+static cl::opt<unsigned> MisfetchCost(
+    "misfetch-cost",
+    cl::desc("The cost of misfetch due to conditional/unconditional jumps."),
+    cl::init(1), cl::Hidden);
+
+static cl::opt<unsigned>
+    JumpInstCost("jump-inst-cost", cl::desc("The cost of jump instructions."),
+                 cl::init(1), cl::Hidden);
+
 namespace {
 class BlockChain;
 /// \brief Type for our function-wide basic block -> block chain mapping.
 typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType;
 }
 
 namespace {
 /// \brief A chain of blocks which will be laid out contiguously.
 ///
 /// This is the datastructure representing a chain of consecutive blocks that
class MachineBlockPlacement : public MachineFunctionPass {
   void markChainSuccessors(BlockChain &Chain, MachineBasicBlock *LoopHeaderBB,
                            SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
                            const BlockFilterSet *BlockFilter = nullptr);
   MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB,
                                          BlockChain &Chain,
                                          const BlockFilterSet *BlockFilter);
   MachineBasicBlock *
   selectBestCandidateBlock(BlockChain &Chain,
                            SmallVectorImpl<MachineBasicBlock *> &WorkList,
                            const BlockFilterSet *BlockFilter);
   MachineBasicBlock *
   getFirstUnplacedBlock(MachineFunction &F, const BlockChain &PlacedChain,
                         MachineFunction::iterator &PrevUnplacedBlockIt,
                         const BlockFilterSet *BlockFilter);
   void buildChain(MachineBasicBlock *BB, BlockChain &Chain,
                   SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
                   const BlockFilterSet *BlockFilter = nullptr);
   MachineBasicBlock *findBestLoopTop(MachineLoop &L,
                                      const BlockFilterSet &LoopBlockSet);
   MachineBasicBlock *findBestLoopExit(MachineFunction &F, MachineLoop &L,
                                       const BlockFilterSet &LoopBlockSet);
   void buildLoopChains(MachineFunction &F, MachineLoop &L);
   void rotateLoop(BlockChain &LoopChain, MachineBasicBlock *ExitingBB,
                   const BlockFilterSet &LoopBlockSet);
+  void rotateLoopWithProfile(BlockChain &LoopChain, MachineLoop &L,
+                             const BlockFilterSet &LoopBlockSet);
   void buildCFGChains(MachineFunction &F);
+  bool useProfileData(MachineFunction &F) {
+    return UseProfileBasedCostAnalysis && F.getFunction()->getEntryCount();
+  }
 
 public:
   static char ID; // Pass identification, replacement for typeid
   MachineBlockPlacement() : MachineFunctionPass(ID) {
     initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnMachineFunction(MachineFunction &F) override;
MachineBlockPlacement::findBestLoopExit(MachineFunction &F, MachineLoop &L,
   // Without a candidate exiting block or with only a single block in the
   // loop, just use the loop header to layout the loop.
   if (!ExitingBB || L.getNumBlocks() == 1)
     return nullptr;
 
   // Also, if we have exit blocks which lead to outer loops but didn't select
   // one of them as the exiting block we are rotating toward, disable loop
   // rotation altogether.
   if (!BlocksExitingToOuterLoop.empty() &&
       !BlocksExitingToOuterLoop.count(ExitingBB))
     return nullptr;
 
   DEBUG(dbgs() << "  Best exiting block: " << getBlockName(ExitingBB) << "\n");
   return ExitingBB;
 }
 
 /// \brief Attempt to rotate an exiting block to the bottom of the loop.
for (MachineBasicBlock *Pred : Top->predecessors()) {
     }
   }
 
   // If the header has viable fallthrough, check whether the current loop
   // bottom is a viable exiting block. If so, bail out as rotating will
   // introduce an unnecessary branch.
   if (ViableTopFallthrough) {
     MachineBasicBlock *Bottom = *std::prev(LoopChain.end());
     for (MachineBasicBlock *Succ : Bottom->successors()) {
       BlockChain *SuccChain = BlockToChain[Succ];
       if (!LoopBlockSet.count(Succ) &&
           (!SuccChain || Succ == *SuccChain->begin()))
         return;
     }
   }
 
   BlockChain::iterator ExitIt =
       std::find(LoopChain.begin(), LoopChain.end(), ExitingBB);
   if (ExitIt == LoopChain.end())
     return;
 
   std::rotate(LoopChain.begin(), std::next(ExitIt), LoopChain.end());
 }
 
+/// \brief Attempt to rotate a loop based on profile data to reduce branch cost.
+///
+/// With profile data, we could determine the benefit in terms of fall through
+/// opportunities when rotating a loop chain and select the best rotation.
+/// Basically, there are three kinds of benefit costs to consider for each
+/// rotation:
+///    1. The fall through edge (if it exists) from BB out of the loop to the
+///    loop header.
+///    2. The fall through edge (if it exists) from the loop exit to BB out of
+///    the loop.
+///    3. The fall through edge (if it exists) from the last BB to the first BB
+///    in the loop chain.
+///  Therefore, the benefit for a given rotation is 1 + 2 - 3. We select the
+///  best rotation with the largest benefit.
+void MachineBlockPlacement::rotateLoopWithProfile(
+    BlockChain &LoopChain, MachineLoop &L, const BlockFilterSet &LoopBlockSet) {
+  auto HeaderBB = L.getHeader();
+  auto HeaderIter = std::find(LoopChain.begin(), LoopChain.end(), HeaderBB);
+  double BestRotationBenefit = -std::numeric_limits<double>::max();
+  auto RotationPos = LoopChain.end();
+
+  // Compute the benefit of the fall-through edge to the loop header. As we only
+  // consider natural loops with single header, this computation can be done
+  // only once.
+  double HeaderFallThruBenefit = 0;
+  for (auto *Pred : HeaderBB->predecessors()) {
+    BlockChain *PredChain = BlockToChain[Pred];
+    if (!LoopBlockSet.count(Pred) &&
+        (!PredChain || Pred == *std::prev(PredChain->end()))) {
+      double EdgeFreq = static_cast<double>(
+          (MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, HeaderBB))
+              .getFrequency());
+      double FallThruBenefit = EdgeFreq * MisfetchCost;
+      // If the predecessor has only an unconditional jump to the header, we
+      // need to consider the cost of this jump.
+      if (Pred->succ_size() == 1)
+        FallThruBenefit += EdgeFreq * JumpInstCost;
+      HeaderFallThruBenefit = std::max(HeaderFallThruBenefit, FallThruBenefit);
+    }
+  }
+
+  for (auto Iter = LoopChain.begin(), TailIter = std::prev(LoopChain.end()),
+            EndIter = LoopChain.end();
+       Iter != EndIter; Iter++, TailIter++) {
+    if (TailIter == LoopChain.end())
+      TailIter = LoopChain.begin();
+
+    auto TailBB = *TailIter;
+
+    // Calculate the cost by putting this BB to the top:
+    double Benefit = 0;
+
+    // If the current BB is not the loop header, we need to take into account
+    // the fall through edge from outside of the loop to the header.
+    if (Iter == HeaderIter)
+      Benefit += HeaderFallThruBenefit;
+
+    // The benefit of the fall through edge with the largest frequency from the
+    // tail BB to outside.
+    BlockFrequency ExitFallThruFreq(0);
+    for (auto *Succ : TailBB->successors()) {
+      BlockChain *SuccChain = BlockToChain[Succ];
+      if (!LoopBlockSet.count(Succ) &&
+          (!SuccChain || Succ == *SuccChain->begin())) {
+        auto EdgeFreq =
+            MBFI->getBlockFreq(TailBB) * MBPI->getEdgeProbability(TailBB, Succ);
+        ExitFallThruFreq = std::max(ExitFallThruFreq, EdgeFreq);
+      }
+    }
+    Benefit +=
+        static_cast<double>(ExitFallThruFreq.getFrequency()) * MisfetchCost;
+
+    // The cost of breaking the once fall-through edge from the tail to the top
+    // of the loop chain. Here we need to consider two cases:
+    //   1. If the tail node has only one successor, then we will get an
+    //   additional jmp instruction. So the cost here is (MisfetchCost +
+    //   JumpInstCost) * tail node frequency.
+    //   2. If the tail node has two successors, then we still get an additional
+    //   jmp instruction. Note that the more frequent executed jmp instruction
+    //   will be put ahead of the other one. Assume the frequency of those two
+    //   branches are x and y (x >= y), then the cost will be (x * MisfetechCost
+    //   + y * JumpInstCost) * tail node frequency.
+    //   3. If the tail node has more than two successors (this rarely happens),
+    //   we won't consider any additional cost.
+    if (TailBB->isSuccessor(*Iter)) {
+      auto TailBBFreq = MBFI->getBlockFreq(TailBB);
+      if (TailBB->succ_size() == 1)
+        Benefit -= static_cast<double>(TailBBFreq.getFrequency()) *
+                   (MisfetchCost + JumpInstCost);
+      else if (TailBB->succ_size() == 2) {
+        double Freq1 = static_cast<double>(
+            (TailBBFreq *
+             MBPI->getEdgeProbability(TailBB, *(TailBB->succ_begin())))
+                .getFrequency());
+        double Freq2 = static_cast<double>(
+            (TailBBFreq *
+             MBPI->getEdgeProbability(TailBB, *(TailBB->succ_rbegin())))
+                .getFrequency());
+        if (Freq1 < Freq2)
+          std::swap(Freq1, Freq2);
+        Benefit -= Freq1 * MisfetchCost + Freq2 * JumpInstCost;
+      }
+    }
+
+    DEBUG(dbgs() << "The benefit of loop rotation by making "
+                 << getBlockNum(*Iter) << " to the top: " << Benefit << "\n");
+
+    if (Benefit > BestRotationBenefit) {
+      BestRotationBenefit = Benefit;
+      RotationPos = Iter;
+    }
+  }
+
+  if (RotationPos != LoopChain.end()) {
+    DEBUG(dbgs() << "Rotate loop by making " << getBlockNum(*RotationPos)
+                 << " to the top\n");
+    std::rotate(LoopChain.begin(), RotationPos, LoopChain.end());
+  }
+}
+
 /// \brief Forms basic block chains from the natural loop structures.
 ///
 /// These chains are designed to preserve the existing *structure* of the code
 /// as much as possible. We can then stitch the chains together in a way which
 /// both preserves the topological structure and minimizes taken conditional
 /// branches.
 void MachineBlockPlacement::buildLoopChains(MachineFunction &F,
                                             MachineLoop &L) {
   // First recurse through any nested loops, building chains for those inner
   // loops.
   for (MachineLoop *InnerLoop : L)
     buildLoopChains(F, *InnerLoop);
 
   SmallVector<MachineBasicBlock *, 16> BlockWorkList;
   BlockFilterSet LoopBlockSet(L.block_begin(), L.block_end());
 
   // First check to see if there is an obviously preferable top block for the
for (MachineBasicBlock *ChainBB : Chain) {
       }
     }
 
     if (Chain.LoopPredecessors == 0)
       BlockWorkList.push_back(*Chain.begin());
   }
 
   buildChain(LoopTop, LoopChain, BlockWorkList, &LoopBlockSet);
+
+  // Check if we have profile data for this function. If yes, we rotate this
+  // loop by heavily using the profile data for better layout.
+  if (useProfileData(F))
+    rotateLoopWithProfile(LoopChain, L, LoopBlockSet);
+  else
     rotateLoop(LoopChain, ExitingBB, LoopBlockSet);
 
   DEBUG({
     // Crash at the end so we get all of the debugging output first.
     bool BadLoop = false;
     if (LoopChain.LoopPredecessors) {
       BadLoop = true;
       dbgs() << "Loop chain contains a block without its preds placed!\n"
              << "  Loop header:  " << getBlockName(*L.block_begin()) << "\n"

test/CodeGen/X86/code_placement_loop_rotation.ll

+; RUN: llc -mcpu=corei7 -mtriple=x86_64-linux < %s | FileCheck %s -check-prefix=CHECK
+; RUN: llc -mcpu=corei7 -mtriple=x86_64-linux -use-profile-based-cost-analysis < %s | FileCheck %s -check-prefix=CHECK-PROFILE
+
+define void @foo() {
+; Test that not all edges in the loop chain are fall through without profile
+; data.
+;
+; CHECK-LABEL: foo:
+; CHECK: callq e
+; CHECK: callq f
+; CHECK: callq g
+; CHECK: callq h
+
+entry:
+  br label %header
+
+header:
+  call void @e()
+  %call = call zeroext i1 @a()
+  br i1 %call, label %if.then, label %if.else, !prof !2
+
+if.then:
+  call void @f()
+  br label %if.end
+
+if.else:
+  call void @g()
+  br label %if.end
+
+if.end:
+  call void @h()
+  %call2 = call zeroext i1 @a()
+  br i1 %call2, label %header, label %end
+
+end:
+  ret void
+}
+
+define void @bar() !prof !1 {
+; Test that all edges in the loop chain are fall through with profile data.
+;
+; CHECK-PROFILE-LABEL: bar:
+; CHECK-PROFILE: callq g
+; CHECK-PROFILE: callq h
+; CHECK-PROFILE: callq e
+; CHECK-PROFILE: callq f
+
+entry:
+  br label %header
+
+header:
+  call void @e()
+  %call = call zeroext i1 @a()
+  br i1 %call, label %if.then, label %if.else, !prof !2
+
+if.then:
+  call void @f()
+  br label %if.end
+
+if.else:
+  call void @g()
+  br label %if.end
+
+if.end:
+  call void @h()
+  %call2 = call zeroext i1 @a()
+  br i1 %call2, label %header, label %end
+
+end:
+  ret void
+}
+
+declare zeroext i1 @a()
+declare void @e()
+declare void @f()
+declare void @g()
+declare void @h()
+
+!1 = !{!"function_entry_count", i64 1}
+!2 = !{!"branch_weights", i32 16, i32 16}

test/CodeGen/X86/code_placement_loop_rotation2.ll

+; RUN: llc -mcpu=corei7 -mtriple=x86_64-linux < %s | FileCheck %s -check-prefix=CHECK
+; RUN: llc -mcpu=corei7 -mtriple=x86_64-linux -use-profile-based-cost-analysis < %s | FileCheck %s -check-prefix=CHECK-PROFILE
+
+define void @foo() {
+; Test a nested loop case when profile data is not available.
+;
+; CHECK-LABEL: foo:
+; CHECK: callq b
+; CHECK: callq c
+; CHECK: callq d
+; CHECK: callq e
+; CHECK: callq f
+; CHECK: callq g
+; CHECK: callq h
+
+entry:
+  br label %header
+
+header:
+  call void @b()
+  %call = call zeroext i1 @a()
+  br i1 %call, label %if.then, label %if.else, !prof !2
+
+if.then:
+  br label %header2
+
+header2:
+  call void @c()
+  %call1 = call zeroext i1 @a()
+  br i1 %call1, label %if.then2, label %if.else2, !prof !2
+
+if.then2:
+  call void @d()
+  br label %if.end2
+
+if.else2:
+  call void @e()
+  br label %if.end2
+
+if.end2:
+  call void @f()
+  %call2 = call zeroext i1 @a()
+  br i1 %call2, label %header2, label %if.end
+
+if.else:
+  call void @g()
+  br label %if.end
+
+if.end:
+  call void @h()
+  %call3 = call zeroext i1 @a()
+  br i1 %call3, label %header, label %end
+
+end:
+  ret void
+}
+
+define void @bar() !prof !1 {
+; Test a nested loop case when profile data is available.
+;
+; CHECK-PROFILE-LABEL: bar:
+; CHECK-PROFILE: callq e
+; CHECK-PROFILE: callq f
+; CHECK-PROFILE: callq c
+; CHECK-PROFILE: callq d
+; CHECK-PROFILE: callq h
+; CHECK-PROFILE: callq b
+; CHECK-PROFILE: callq g
+
+entry:
+  br label %header
+
+header:
+  call void @b()
+  %call = call zeroext i1 @a()
+  br i1 %call, label %if.then, label %if.else, !prof !2
+
+if.then:
+  br label %header2
+
+header2:
+  call void @c()
+  %call1 = call zeroext i1 @a()
+  br i1 %call1, label %if.then2, label %if.else2, !prof !2
+
+if.then2:
+  call void @d()
+  br label %if.end2
+
+if.else2:
+  call void @e()
+  br label %if.end2
+
+if.end2:
+  call void @f()
+  %call2 = call zeroext i1 @a()
+  br i1 %call2, label %header2, label %if.end
+
+if.else:
+  call void @g()
+  br label %if.end
+
+if.end:
+  call void @h()
+  %call3 = call zeroext i1 @a()
+  br i1 %call3, label %header, label %end
+
+end:
+  ret void
+}
+
+declare zeroext i1 @a()
+declare void @b()
+declare void @c()
+declare void @d()
+declare void @e()
+declare void @f()
+declare void @g()
+declare void @h()
+
+!1 = !{!"function_entry_count", i64 1}
+!2 = !{!"branch_weights", i32 16, i32 16}