Page MenuHomePhabricator

[llvm-mca][RFC] Adding binary support to llvm-mca.
Needs ReviewPublic

Authored by mattd on Nov 15 2018, 2:40 PM.

Details

Summary

Introduction

Currently llvm-mca only accepts assembly code as input. We would like to
extend llvm-mca to support object files, allowing users to analyze the
performance of binaries. The proposed changes optionally introduce an object
file section, but this can be stripped-out if desired.

For the llvm-mca binary support feature to be useful, a user needs to tell
llvm-mca which portions of their code they would like analyzed. Currently,
this is accomplished via assembly comments. However, assembly comments are not
preserved in object files, and this has encouraged this RFC. For the proposed
binary support, we need to introduce changes to clang and llvm to allow the
user's object code to be recognized by llvm-mca:

  1. We need a way for a user to identify a region/block of code they want analyzed by llvm-mca.
  1. We need the information defining the user's region of code to be maintained in the object file so that llvm-mca can analyze the desired region(s) from the binary object file.

We define a "code region" as a subset of a user's program that is to be
analyzed via llvm-mca. The sequence of instructions to be analyzed is
represented as a pair: <start, end> where the 'start' marks the beginning of
the user's source code and 'end' terminates the sequence. The instructions
between 'start' and 'end' form the region that can be analyzed by llvm-mca at a
later time.

Example

Before we go into the details of this proposed change, let's first look at a
simple example:

// example.c -- Analyze a dot-product expression.
double test(double x, double y) {

double result = 0.0;
__mca_code_region_start(42);
result += x * y;
__mca_code_region_end();
return result;

}

In the example above, we have identified a code region, in this case a single
dot-product expression. For the sake of brevity and simplicity, we've chosen
a very simple example, but in reality a more complicated example could use
multiple expressions. We have also denoted this region as number 42. That
identifier is only for the user, and simplifies reading an llvm-mca analysis
report later.

When this code is compiled, the region markers (the mca_code_region markers)
are transformed into assembly labels. While the markers are presented as
function calls, in reality they are no-ops.

test:
pushq %rbp
movq %rsp, %rbp
movsd %xmm0, -8(%rbp)
movsd %xmm1, -16(%rbp)
.Lmca_code_region_start_0: # LLVM-MCA-START ID: 42
xorps %xmm0, %xmm0
movsd %xmm0, -24(%rbp)
movsd -8(%rbp), %xmm0
mulsd -16(%rbp), %xmm0
addsd -24(%rbp), %xmm0
movsd %xmm0, -24(%rbp)
.Lmca_code_region_end_0: # LLVM-MCA-END ID: 42
movsd -24(%rbp), %xmm0
popq %rbp
retq
.section .mca_code_regions,"",@progbits
.quad 42
.quad .Lmca_code_region_start_0
.quad .Lmca_code_region_end_0-.Lmca_code_region_start_0

The assembly has been trimmed to show the portions relevant to this RFC.
Notice the labels enclose the user's defined region, and that they preserve the
user's arbitrary region identifier, the ever-so-important region 42.

In the object file section .mca_code_regions, we have noted the user's region
identifier (.quad 42), start address, and region size. A more complicated
example can have multiple regions defined within a single .mca_code_regions
section. This section can be read by llvm-mca, allowing llvm-mca to take
object files as input instead of assembly source.

Details

We need a way for a user to identify a region/block of code they want analyzed
by llvm-mca. We solve this problem by introducing two intrinsics that a user can
specify, for identifying regions of code for analysis.

The two intrinsics are: llvm.mca.code.regions.start and
llvm.mca.code.regions.end. A user can identify a code region by inserting the
mca_code_region_start and mca_code_region_end markers. These are simply
clang builtins and are transformed into the aforementioned intrinsics during
compilation. The code between the intrinsics are what we call "code regions"
and are to be easily identifiable by llvm-mca; any code between a start/end
pair can be analyzed by llvm-mca at a later time. A user can define multiple
non-overlapping code regions within their program.

The llvm.mca.code.region.start intrinsic takes an integer constant as its only
argument. This argument is implemented as a metadata i32, and is only used
when generating llvm-mca reports. This value allows a user to more easily
identify a specific code region. llvm.mca.code.region.end takes no arguments.
Since we disallow nesting of regions, the first 'end' intrinsic lexically
following a 'start' intrinsic represents the end of that code region.

Now that we have a solution for identifying regions for analysis, we now need a
way for preserving that information to be read at a later time. To accomplish
this we propose adding a new section (.mca_code_regions) to the object file
generated by llvm. During code generation, the start/end intrinsics described
above will be transformed into start/end labels in assembly. When llvm
generates the object file from the user's code, these start/end labels form a
pair of values identifying the start of the user's code region, and size. The
size represents the number of bytes between the start and end address of the
labels. Note that the labels are emitted during assembly printing. We hope
that these labels have no influence on code generation or basic-block
placement. However, the target assembler strategy for handling labels is
outside of our control.

This proposed change affects the size of a binary, but only if the user calls
the start/end builtins mentioned above. The additional size of the
.mca_code_regions section, which we imagine to be very small (to the order of a
few bytes), can trivially be stripped by tools like 'strip' or 'objcopy'.

Implementation Status

We currently have the proposed changes implemented at the url posted below.
This initial patch only targets ELF object files, and does not handle
relocatable addresses. Since the start of a code region is represented as an
assembly label, and referenced in the .mca_code_regions section, that address
is relocatable. That value can be represented as section-relative relocatable
symbol (.text + addend), but we are not handling that case yet. Instead, the
proposed changes only handle linked/executable object files.

The change is presented as a monolithic patch; however, when the time comes
it will be split into three patches:

  1. The introduction of the builtins to clang.
  2. The llvm portion (the added intrinsics).
  3. The llvm-mca portion.

This RFC was proposed to the wider llvm community here:
https://lists.llvm.org/pipermail/llvm-dev/2018-November/127784.html

Diff Detail

Event Timeline

mattd created this revision.Nov 15 2018, 2:40 PM
mattd edited the summary of this revision. (Show Details)Nov 21 2018, 8:49 AM
mattd updated this revision to Diff 175358.Nov 26 2018, 3:47 PM
  • Rebased this patch.
  • Added an additional IRVerifier check to generate a compiler error if a llvm-mca code region belongs to more than one basic-block (this was discussed in the llvm-dev mailing list thread).
mattd added inline comments.Nov 27 2018, 8:37 AM
test/CodeGen/builtins-mca.c
2

I'll fix the file mode when I generate the patch set for these changes.

mattd added a comment.Dec 5 2018, 5:08 PM

Ping

Just pinging this patch and RFC to see if anyone else, aside from Andrea, has any feedback. The discussion on the RFC is here:
https://lists.llvm.org/pipermail/llvm-dev/2018-December/128218.html

mattd updated this revision to Diff 178585.Dec 17 2018, 8:22 PM
  • Following some discussion of the RFC on the mailing list, this patch makes a few improvements:
  • Object files and executables are supported. This is accomplished by scanning the symbol table for mca_code_region_start and mca_code_region_end symbols.
  • This solution does not rely on target specific relocations.
  • Regions cannot be nested, so a start of region label/symbol must be followed by an end (this has always been the case).
  • Symbol names are encoded with the user's defined region number." That number is just for cosmetic purposes and is only helpful for the user, llvm-mca can make use of that number to annotate its analysis reports.
mattd added a comment.Dec 17 2018, 8:24 PM
  • Following some discussion of the RFC on the mailing list, this patch makes a few improvements:
  • Object files and executables are supported. This is accomplished by scanning the symbol table for mca_code_region_start and mca_code_region_end symbols.
  • This solution does not rely on target specific relocations.
  • Regions cannot be nested, so a start of region label/symbol must be followed by an end (this has always been the case).
  • Symbol names are encoded with the user's defined region number." That number is just for cosmetic purposes and is only helpful for the user, llvm-mca can make use of that number to annotate its analysis reports.

I forgot to mention, this also removes the need for the .mca_code_regions object file section. All of the parsing and code-region identification is performed via symbol table.

mattd updated this revision to Diff 179383.Dec 21 2018, 4:10 PM
  • Corrected some comments and removed unnecessary code, as a result of the last two patches.
  • Rebased
mattd updated this revision to Diff 179904.Jan 2 2019, 11:39 AM
  • Removed the check in IR/Verifier that rejected programs if llvm-mca code regions span multiple blocks.

In short, we let llvm-mca handle multiple blocks as it always has. To be fair here, llvm-mca doesn't handle branch instructions, but a user can currently place LLVM-MCA assembly comments such that the instructions cross multiple blocks.

mattd updated this revision to Diff 179909.Jan 2 2019, 11:59 AM
  • Renamed the assembly comment that gets added to assembly files when using the llvm.mca.code.region.start intrinsic.
mattd updated this revision to Diff 180335.Jan 4 2019, 3:53 PM
  • Update the symbol name parsing for the llvm-mca region markers.

This update allows llvm-mca to sort code regions based on both the start address of the region and the compiler-generated sequence number.
The sequence number is useful when sorting regions that might begin/end at the same address. This can be helpful in cases where a region begins immediately after the previous one ends.

mattd marked an inline comment as done.Jan 4 2019, 3:58 PM
mattd added inline comments.
include/llvm/Target/Target.td
1192

I've set hasSideEffects to true, so that DeadMachineInstructionElim does not remove the llvm-mca code markers under optimization. However, it's certainly possible that optimizations will move code outside of the region.

Should the test/CodeGen/X86/*.ll tests be put in test/CodeGen/Generic/*.ll instead?

mattd updated this revision to Diff 180509.Jan 7 2019, 9:07 AM
  • Rebased against master
  • Moved most of the added llvm-mca CodeGen/X86 tests to CodeGen/Generic.
mattd updated this revision to Diff 180762.Jan 8 2019, 4:08 PM

Update the SelectionDAG handling of the mca_code_region_start and mca_code_region_end intrinsics.

The previous version of this patch just emitted the machine instructions when building the SelectionDAG. Now we are generating SDNodes which seems to give a better representation of the code blocks during inlining/optimization.