This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by congh on Jun 24 2015, 4:18 PM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

congh updated this revision to Diff 28417.Jun 24 2015, 4:18 PM
congh retitled this revision from to Enhance loop rotation with existence of profile data in MachineBlockPlacement pass..
congh updated this object.
congh edited the test plan for this revision. (Show Details)
congh added a reviewer: chandlerc.
congh added a subscriber: Unknown Object (MLST).
chandlerc edited edge metadata.Jun 24 2015, 5:47 PM

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 updated this revision to Diff 28435.Jun 24 2015, 7:25 PM
congh edited edge metadata.

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 updated this revision to Diff 28476.Jun 25 2015, 10:39 AM

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

congh updated this revision to Diff 28490.Jun 25 2015, 12:09 PM

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

davidxl added inline comments.
lib/CodeGen/MachineBlockPlacement.cpp
250 ↗(On Diff #28490)

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

761 ↗(On Diff #28490)

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

797 ↗(On Diff #28490)

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 ↗(On Diff #28490)

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 ↗(On Diff #28490)

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 ↗(On Diff #28490)

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 ↗(On Diff #28490)

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

855 ↗(On Diff #28490)

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 ↗(On Diff #28490)

This needs more explanation.

939 ↗(On Diff #28490)

I suggest adding another intern option to guard this.

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

941 ↗(On Diff #28490)

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

congh added inline comments.Jun 26 2015, 4:08 PM
lib/CodeGen/MachineBlockPlacement.cpp
250 ↗(On Diff #28490)

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 ↗(On Diff #28490)

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 ↗(On Diff #28490)

Please see my comment above.

797 ↗(On Diff #28490)

Agree. I will update the comment.

818 ↗(On Diff #28490)

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 ↗(On Diff #28490)

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 ↗(On Diff #28490)

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 ↗(On Diff #28490)

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

855 ↗(On Diff #28490)

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 ↗(On Diff #28490)

OK.

941 ↗(On Diff #28490)

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

congh updated this revision to Diff 28610.Jun 26 2015, 4:17 PM

The updated patch according to David's comments.

davidxl added inline comments.Jun 26 2015, 5:11 PM
lib/CodeGen/MachineBlockPlacement.cpp
818 ↗(On Diff #28490)

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

821 ↗(On Diff #28490)

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

828 ↗(On Diff #28490)

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 ↗(On Diff #28490)

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

855 ↗(On Diff #28490)

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 ↗(On Diff #28490)

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.

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 added inline comments.Jun 29 2015, 10:53 AM
lib/CodeGen/MachineBlockPlacement.cpp
818 ↗(On Diff #28490)

OK. Thanks!

821 ↗(On Diff #28490)

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 ↗(On Diff #28490)

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 ↗(On Diff #28490)

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 ↗(On Diff #28490)

Done.

941 ↗(On Diff #28490)

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.

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 updated this revision to Diff 28735.Jun 29 2015, 5:33 PM

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

congh updated this revision to Diff 28743.Jun 29 2015, 7:43 PM

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

congh updated this revision to Diff 28815.Jun 30 2015, 2:29 PM
congh added a comment.Jun 30 2015, 2:29 PM

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

congh updated this revision to Diff 29482.Jul 10 2015, 1:15 PM

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 requested changes to this revision.Jul 24 2015, 11:21 AM
chandlerc edited edge metadata.

Sorry for delays getting to this patch.

lib/CodeGen/MachineBlockPlacement.cpp
84–86 ↗(On Diff #29482)

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 ↗(On Diff #29482)

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 ↗(On Diff #29482)

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 ↗(On Diff #29482)

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 ↗(On Diff #29482)

"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 ↗(On Diff #29482)

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 ↗(On Diff #29482)

Why is a conditional jump's benefit not considered?

854–856 ↗(On Diff #29482)

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 ↗(On Diff #29482)

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

877–879 ↗(On Diff #29482)

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

This revision now requires changes to proceed.Jul 24 2015, 11:21 AM
davidxl added inline comments.Jul 24 2015, 1:46 PM
lib/CodeGen/MachineBlockPlacement.cpp
84–86 ↗(On Diff #29482)

yes -- something like

'precise-rotation-cost' would be clearer.

congh marked 9 inline comments as done.Jul 24 2015, 3:43 PM
congh added inline comments.
lib/CodeGen/MachineBlockPlacement.cpp
84–86 ↗(On Diff #29482)

I have chosen the name suggested by David.

89–92 ↗(On Diff #29482)

I have updated the description following your suggestion.

94–96 ↗(On Diff #29482)

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 ↗(On Diff #29482)

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

815–826 ↗(On Diff #29482)

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

831 ↗(On Diff #29482)

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

846–849 ↗(On Diff #29482)

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 ↗(On Diff #29482)

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

868 ↗(On Diff #29482)

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 ↗(On Diff #29482)

Yes, this is more efficient. Done.

congh updated this revision to Diff 30619.Jul 24 2015, 3:45 PM
congh edited edge metadata.
congh marked 7 inline comments as done.

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

chandlerc added inline comments.Jul 24 2015, 7:21 PM
lib/CodeGen/MachineBlockPlacement.cpp
816–827 ↗(On Diff #30619)

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.

834–838 ↗(On Diff #30619)

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.

902 ↗(On Diff #30619)

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.

912–916 ↗(On Diff #30619)

What if one of the successors is outside the loop?

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

846–849 ↗(On Diff #29482)

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.

davidxl added inline comments.Jul 24 2015, 9:03 PM
lib/CodeGen/MachineBlockPlacement.cpp
816–827 ↗(On Diff #30619)

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.

834–838 ↗(On Diff #30619)

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)

847–850 ↗(On Diff #30619)

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.

902 ↗(On Diff #30619)

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

912–916 ↗(On Diff #30619)

this should not matter.

915 ↗(On Diff #30619)

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 added inline comments.Jul 26 2015, 11:24 PM
lib/CodeGen/MachineBlockPlacement.cpp
816–827 ↗(On Diff #30619)

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.

834–838 ↗(On Diff #30619)

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.

834–838 ↗(On Diff #30619)

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.

847–850 ↗(On Diff #30619)

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.

902 ↗(On Diff #30619)

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.

912–916 ↗(On Diff #30619)

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

915 ↗(On Diff #30619)

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 added inline comments.Jul 27 2015, 12:53 AM
lib/CodeGen/MachineBlockPlacement.cpp
834–838 ↗(On Diff #30619)

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.

915 ↗(On Diff #30619)

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

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

rotation cost is: x * MisFetchCost + x*JumpInstCost

Combine 1) and 2),

congh added inline comments.Jul 27 2015, 1:48 PM
lib/CodeGen/MachineBlockPlacement.cpp
834–838 ↗(On Diff #30619)

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.

915 ↗(On Diff #30619)

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 added inline comments.Jul 27 2015, 2:06 PM
lib/CodeGen/MachineBlockPlacement.cpp
834–838 ↗(On Diff #30619)

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 updated this revision to Diff 30773.Jul 27 2015, 7:18 PM
congh edited edge metadata.

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

Improve the inefficient code that computes branch probabilities.

congh added a comment.Aug 3 2015, 10:45 AM

Ping on this patch?

congh updated this revision to Diff 31424.Aug 5 2015, 5:38 PM

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

PTAL.

djasper edited edge metadata.Oct 7 2015, 8:25 AM

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 ↗(On Diff #31424)

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 ↗(On Diff #31424)

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

congh added a comment.Oct 12 2015, 1:00 PM

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

lib/CodeGen/MachineBlockPlacement.cpp
93 ↗(On Diff #31424)

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 ↗(On Diff #31424)

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 updated this revision to Diff 37153.Oct 12 2015, 1:01 PM
congh edited edge metadata.

Update the patch according to Daniel's comment.

davidxl added inline comments.Oct 19 2015, 2:26 PM
lib/CodeGen/MachineBlockPlacement.cpp
92 ↗(On Diff #37153)

Fix typo: probabilistic.

99 ↗(On Diff #37153)

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

842 ↗(On Diff #37153)

Why not just multiply with Scale?

855 ↗(On Diff #37153)

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

893 ↗(On Diff #37153)

Fix indentation.

922 ↗(On Diff #37153)

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

925 ↗(On Diff #37153)

chair --> chain

938 ↗(On Diff #37153)

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

congh marked 3 inline comments as done.Oct 19 2015, 3:15 PM
congh added inline comments.
lib/CodeGen/MachineBlockPlacement.cpp
99 ↗(On Diff #37153)

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

842 ↗(On Diff #37153)

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.

855 ↗(On Diff #37153)

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

893 ↗(On Diff #37153)

This is the result from running clang-format.

922 ↗(On Diff #37153)

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.

938 ↗(On Diff #37153)

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 updated this revision to Diff 37803.Oct 19 2015, 3:17 PM
congh marked an inline comment as done.

Update the patch according to David's comment.

davidxl added inline comments.Oct 19 2015, 3:33 PM
lib/CodeGen/MachineBlockPlacement.cpp
920 ↗(On Diff #37803)

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 added inline comments.Oct 19 2015, 3:45 PM
lib/CodeGen/MachineBlockPlacement.cpp
920 ↗(On Diff #37803)

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

congh updated this revision to Diff 37807.Oct 19 2015, 3:46 PM

Update the patch by fixing a comment.

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
  1. 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).
congh updated this object.Oct 19 2015, 4:17 PM
This revision was automatically updated to reflect the committed changes.