ext-tsp basic block layout

[spupyrev]

Summary

A new basic block ordering improving existing MachineBlockPlacement.

The algorithm tries to find a layout of nodes (basic blocks) of a given CFG
optimizing jump locality and thus processor I-cache utilization. This is
achieved via increasing the number of fall-through jumps and co-locating
frequently executed nodes together. The name follows the underlying
optimization problem, Extended-TSP, which is a generalization of classical
(maximum) Traveling Salesmen Problem.

The algorithm is a greedy heuristic that works with chains (ordered lists)
of basic blocks. Initially all chains are isolated basic blocks. On every
iteration, we pick a pair of chains whose merging yields the biggest increase
in the ExtTSP value, which models how i-cache "friendly" a specific chain is.
A pair of chains giving the maximum gain is merged into a new chain. The
procedure stops when there is only one chain left, or when merging does not
increase ExtTSP. In the latter case, the remaining chains are sorted by
density in decreasing order.

An important aspect is the way two chains are merged. Unlike earlier
algorithms (e.g., based on the approach of Pettis-Hansen), two
chains, X and Y, are first split into three, X1, X2, and Y. Then we
consider all possible ways of gluing the three chains (e.g., X1YX2, X1X2Y,
X2X1Y, X2YX1, YX1X2, YX2X1) and choose the one producing the largest score.
This improves the quality of the final result (the search space is larger)
while keeping the implementation sufficiently fast.

Perf impact:
The perf improvement over the existing MachineBlockPlacement is in the range
of 0.5%-1.5% for medium-sized binaries (e.g, clang/gcc), depending on the PGO
mode (tested with various options of LLVM_BUILD_INSTRUMENTED and AutoFDO,
CSSPGO).
For large-scale fully-optimized binaries running in production, we measure 0.2%-0.8%
speedup (with AutoFDO/CSSPGO but excluding post-link optimizers).
For smaller (not front-end bound) binaries, we do not expect regressions; for SPEC17:

• 508.namd_r: 8.96+/-3.89 (win)
• 602.gcc: -0.93+/-0.47 (regression)
• 623.xalancbmk: 2.12+/-0.84 (win)
• 625.x264: 1.41+/-0.7 (win)
• other binaries are flat.

Performance of the alg:
We haven't seen a change of the build time for large binaries.

[tschuett]

Would it help to add remarks in a later diff to get some insights into the algorithm?
https://llvm.org/docs/Remarks.html

[davidxl]

llvm/lib/CodeGen/MachineBlockPlacement.cpp

3408

Ok, we can keep ext-tsp as an cleanup pass.

llvm/test/CodeGen/X86/code_placement_ext_tsp.ll

304

This might be a bug in existing layout. By design, with profile data, in order to take b2 as the layout successor, the incoming edge weight needs > 2*10 = 20.

llvm/test/CodeGen/X86/code_placement_ext_tsp_large.ll

10

Add a cfg with ascii art.

12

Explain a little the expected output.

30

Add brief explanation of expected output.

[hoy]

llvm/lib/CodeGen/MachineBlockPlacement.cpp

3571

The object is created but not used anywhere. Is that expected?

llvm/lib/Transforms/Utils/CodeLayout.cpp

111

nit: please use enum class and add comment for each enum value.

906

This is an assert-only loop. Put it under #ifndef NDEBUG ?

[rahmanl]

llvm/lib/Transforms/Utils/CodeLayout.cpp

138

I think we would never merge 0-score chains. If there is any additional benefit (code size) it can be incorporated into the score. But I am OK with this.

635

You can use something like the following function:

auto ComputeMergeGainWithOffsetAndTypes([&](int Offset, std::vector<MergeTypeTy> &merge_types) {
  if (Offset == 0 || Offset == PredChain.size())
    return;
  auto BB = ChainPred->blocks()[Offset - 1];
   // Skip the splitting if it breaks FT successors
   if (BB->ForcedSucc != nullptr)
     continue;
   for (auto &MergeType: merge_types) {
      Gain.updateIfLessThan(computeMergeGain(ChainPred, ChainSucc, Jumps, Offset, MergeType));
   }
}

684

Great. Please add a comment to explain why this splitting is not exercised.

llvm/test/CodeGen/X86/code_placement_ext_tsp.ll

5

This is missing the ascii cfg.

306

Please use the same names as in the CFG so this can be easily mapped. And please do this across all tests.

llvm/test/CodeGen/X86/code_placement_ext_tsp_large.ll

2

I am not an expert on this, but I feel like this is not needed. Does it make a difference?

[spupyrev]

addressing comments:

• adjusted tests;
• enum class;
• minor refactorings as suggested.

llvm/lib/CodeGen/MachineBlockPlacement.cpp

3571

What object do you refer to?

llvm/test/CodeGen/X86/code_placement_ext_tsp.ll

304

This tests uses two different modes of ext-tsp, with and without "chain splitting" -- something that Rahman suggested. The "old" layout in MachineBlockPlacement isn't applied here.

llvm/test/CodeGen/X86/code_placement_ext_tsp_large.ll

10

The purpose of the test is to verify that chain splitting code is executed and that it is beneficial for the layout, that is, the optimized score is increased. I added the explanations.

Since the graph is large and randomly generated, the ascii representation is not very readable. In fact, it is not providing any insights, so let's skip it?

[davidxl]

llvm/lib/Transforms/Utils/CodeLayout.cpp

86

The paper documents 6 types of branches and their weight K_{s,t}. Should these be parametized here?

98

The tsp score does not seem to be contiguous here. When Dist == 0, it should have the same score as the fall through case, but this produces 0.1* Count.

640

It is confusing to have both this method and calcExtTSPScore methods.

927

From the initialization, Order[Idx] == Idx, so is this map needed?

936

typo 'Increasing'

938

why is the count not used?

940

This function computes the 'fallthrough' maximizing TSP score, not the extTSP in the original paper. Where is the h function and the K coeffcients?

948

Can the reserve be combined with the vector declaration, or the intention is to avoid initialization?

llvm/test/CodeGen/X86/code_placement_ext_tsp_large.ll

10

ok. I was expecting to look into the test case and reason that improved score corresponds to improved layout. Looks like this is just a test to show increased score. Can this be done instead with any other tests (the score should be increased monotonically) ?

[spupyrev]

David's comments (except for the large test)

llvm/lib/Transforms/Utils/CodeLayout.cpp

98

Agree, that's something me and my colleagues have been thinking about lately.

The current function is tuned for the maximum performance of the resulting binary. It is not guaranteed/enforced that the function is contiguous. That said, i'd be super happy to see and review improvements of the objective in the future. There is likely a room for optimizations here

927

This function is also called when Order != Identity

940

oops. Refactored function to compute correct result

[spupyrev]

changed "large" test into a human-readable one, added ascii for the CFG

[davidxl]

llvm/lib/Transforms/Utils/CodeLayout.cpp

98

I guessed that with ForwardWeight == 0.1, a bias can be introduced against laying out larger successor as the fall through block, but it is not the case. Using different forward weight seems to produce the same decision for a simple diamond cfg case -- in order to for one successor to be a fallthrough, the branch probability needs to > 50%.

I wonder what role this weight plays in practice (performance)?

927

Probably provide another wrapper to compute the mapping and pass it in. The map can use the vector type, so for the case when Order == Identity, Order can be used for both.

[spupyrev]

llvm/lib/Transforms/Utils/CodeLayout.cpp

98

I am not sure I understand the question, could you clarify?

The weights affect the resulting layout, which in turn may impact perf. However, changing the weights from 0.1 to say 0.2 likely won't make a difference, except for some corner cases.
IIRC, in my tests 3 years ago it was important to keep ForwardWeight<FallthroughWeight=1.0. Intuitively this makes sense, though the exact values may need to be re-tuned. (This is a separate and time-consuming project)

[davidxl]

llvm/lib/Transforms/Utils/CodeLayout.cpp

98

You answer touched upon what I was asking. To clarify the question: are there performance data to show why 0.1 (instead of other values) is used. ExtTSP score can be considered as a locality score, and the forwardWeight is an attempt to model the cost of taken branch instruction. I wonder if there is a better way to model this in the objective function. No need to address it in this patch though.

[davidxl]

llvm/lib/CodeGen/MachineBlockPlacement.cpp

3457

It is better to use vector type as the index space is dense?

3459

vector type?

3472

Why not computing the actual byte size of the block?

3478

Is multi-graph assumed, why?

3492

Can the following (computing NewBlockOrder) be folded into applyExtTspLayout? The NewOrder is not used anywhere else, so no need to be exposed.

3529

Is NewIndex the same as BlockIndex computed in applyExtTsp? Why recomputing?

[spupyrev]

• changed DenseMap => std::vector
• git rid of multi-edges

llvm/lib/CodeGen/MachineBlockPlacement.cpp

3472

That would be great! Do you mind pointing to the right way of implementing this? I was not able to find anything meaningless in MachineBasicBlock

3492

I am not fully understanding the suggestion.

The goal is here is to make applyExtTspLayout work with any type of nodes, not just MachineBasicBlock (potentially we want to apply it for function sorting). I tried creating a generic implementation with templates (and thus "hiding" NewOrder) but it turned out to be much messier than what it is now.

3529

No, this is a new index after reordering.

[davidxl]

llvm/lib/CodeGen/MachineBlockPlacement.cpp

3472

This is target dependent unfortunately -- an abstract interface can be added in MCCodeEmitter. The implementation should be similar to encodeInstruction.

This is beyond the scope of the patch, so perhaps add a TODO in the comment.

[spupyrev]

adding a note on computing block sizes exactly

[davidxl]

LGTM, please also wait for other reviewers lgtm.

[spupyrev]

adding 'mtriple' back to test options, as MachineBlockPlacement isn't deterministic between different platforms (so tests fail on Windows)

[rahmanl]

LGTM as well.

[hoy]

lgtm except for some nits. Thanks.

llvm/lib/CodeGen/MachineBlockPlacement.cpp

3571

nvm, the object pointed by FunctionChain is used in FunctionChain->merge.

llvm/lib/Transforms/Utils/CodeLayout.cpp

61

nit: the distance in use isn't really in bytes? It is number of MR instructions?

274

nit: we usually use uint64_t for id type explicitly.

898

nit: no need to use #ifndef NDEBUG

[spupyrev]

changed type of Chain.Id to uint64

llvm/lib/Transforms/Utils/CodeLayout.cpp

61

As discussed in https://reviews.llvm.org/D113424/new/#inline-1097352, we use block sizes in bytes, approximating it by num_mir_instr * 4.

Equivalently, we could similarly use the number of instructions in both places (by scaling the constants down by 4) but I don't really see a difference

[thakis]

Looks like this broke CodeGen/X86/code_placement_ext_tsp.ll on arm macs:

http://45.33.8.238/macm1/23133/step_11.txt

Please take a look, and revert for now if it takes a while to fix.

[thakis]

Also here https://lab.llvm.org/buildbot/#/builders/186/builds/2803 which should've sent email long ago. Reverting...

[spupyrev]

making the tests deterministic

[MaskRay]

llvm/lib/Transforms/Utils/CodeLayout.cpp

716

This should be Jump->Target. See https://github.com/llvm/llvm-project/pull/66592