[llvm-dev] [RFC][llvm-mca] Adding binary support to llvm-mca.

Matt Davis via llvm-dev
2018-12-03T22:38:40Z

Hi Andrea,

On Mon, Dec 03, 2018 at 01:21:33PM +0000, Andrea Di Biagio
wrote:
> So, I have been thinking a bit more about this whole design.
>
> The more I think about your suggested design, the more I am convinced that
> we should do something more to support ranges in binary object files too.
> My understanding is that the reason why we don't support object files
in
> general, is because of the presence of relocations. That is because a
> region start marker is effectively symbol relative, and the symbol (a
> function) would be relocated in the final executable.
> You mentioned to me that resolving even a 'simple' symbol-relative
> relocation is not trivial, beause it requires specific knowledge about the
> binary format, and the target (i.e. how relocations are encoded is target
> specific). I am surprised that there is not a utility library for resolving
> relocations.. but I am not familiar with that part of the compiler. I was
> hoping that there was a target specific interface to use in this case...

There might be a better way of resolving the relocs, but from what I saw
looking at llvm-objdump and other related tools, it seems that resolving
the relocated symbol is a target specific effort.  I also spent sometime
sniffing around ExecutionEngine/RuntimeDyld/RuntimeDyld.cpp which also
performs the reloc resolution.  I should clarify that I too am not an
expert in llvm's utilities for performing symbol/reloc resolution, and
perhaps someone in the community can point me in the right direction.  I
can clearly see the reloc data in the object file via tools like
objdump; however, accessing the relocs via
llvm::object::ObjectFile::relocations() did not produce address values
that we could use (values of zero).

I was hoping that, for a first pass at this patch, supporting just
executables would be okay.  That keeps this initial patch set simple,
and hopefully will encourage others to take a peek at it, since it's
less daunting than what it might otherwise be.  Of course, there is the
concern that this initial patch will lock us into a design that will be
more complicated to unravel later.

> An alternative approach would require that you define your own
> "symbol-relative" reference. After all, ranges are just a
sequences of
> instructions in a function. If a function symbol is described by the symbol
> table, then you should be able to obtain its offset in the .text section.
> So, you could potentially encode your own symbol+offset. However, the
> linker would not be able to understand your "custom relocation",
and
> information about regions in the final elf would be basically broken.
> So,that would not be a solution...
>
> I don't know honestly what is the best approach to use in this case.
> As a compromise, it would not be a bad idea to add the ability to specify
> ranges from command line. What do you think?
> Still, from a user point of view, the idea that we don't support object
> files in general sounds like a big limitation.

I agree, only supporting executables is a limitation.  However, I'd
like to land the base support now and add in the additional
features/support after this large patch set lands.  But I can see
where landing the whole thing entirely also makes sense.

> About the new experimental intrinsics: those would definitely work well for
> the simple case where instructions are from the same basic block.
> However, some/most of the constraints that you plan to add will have to
> change if in future we decide to allow ranges that potentially cross
> multiple basic blocks. How will the rules/constraints on those new
> intrinsics change? I just want to make sure that the suggested design is
> future-proof.

Since the llvm/clang parts of the code are just responsible for
collecting where a range starts/ends, I hope that we can remove some
of the baked-in constraints that are specified in IR/Verifier.cpp.
As you pointed out earlier in this thread, we might want to
introduce a dominance check if/when we lift the one-basic-block
restriction.

-Matt

>
> -Andrea
>
> On Tue, Nov 27, 2018 at 5:08 PM Andrea Di Biagio <andrea.dibiagio at
gmail.com>
> wrote:
>
> > Thanks for clarifying it Matt.
> >
> > In general, I quite like your suggested design.
> >
> > My only concern is about the semantic of the two new intrinsics. You
> > design doesn't allow mca ranges to span through multiple basic
blocks. That
> > constraint is acceptable for now, since llvm-mca doesn't know how
to deal
> > with control flow.
> > However, I am a bit concerned about what might happen in future if we
> > decide to let users specify code regions that span through multiple
basic
> > blocks. Basically, I don't particularly like the idea of changing
the
> > semantic of already existing intrinsic. A design that already accounts
for
> > that particular scenario/future work would be ideal. That being said,
> > marking those new intrinsics as 'experimental' may be a good
compromise (at
> > least for now).
> >
> > So, I am quite happy overall with the direction of this RFC.
> > However, I am interesting to hear from other developers about your
> > suggested design.
> >
> > > 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.
> >
> > This may be okay for now. However, it would be nice to remove that
> > constraint in future and add support to generic object files.
> >
> > -Andrea
> >
> > On Thu, Nov 22, 2018 at 7:21 PM <Matthew.Davis at sony.com>
wrote:
> >
> >> I want to clarify a few restrictions of llvm-mca code regions that
this
> >> RFC proposes:
> >>
> >> 1) All llvm-mca code regions must start with an
> >> llvm.mca.code.region.start intrinsic and end with
> >> an llvm.mca.code.region.end intrinsic.  This rule is enforced at
the IR
> >> level in the IR verifier.
> >>
> >> 2) llvm-mca code regions cannot nest.  This restriction implies
that an
> >> llvm.mca.code.region.start
> >> must have a llvm.mca.code.region.end intrinsic without any other
llvm.mca
> >> start intrinsics
> >> between the two. The current implementation in the patch enforces
this
> >> restriction at the
> >> IR level via the IR Verifier.
> >>
> >> 3) An llvm-mca code region cannot span multiple basic blocks.
llvm-mca
> >> does not follow
> >> branches (yet).  Instead, a branch instruction is treated by
llvm-mca
> >> like any other instruction.
> >> The current patch associated with this RFC does not enforce this
> >> restriction.  I plan on updating
> >> the patch to enforce that a code region can only belong to a
single basic
> >> block.  This is a simple
> >> check, ensuring that both the llvm.mca.code.region.start and
accompanying
> >> end intrinsics live
> >> in the same basic block. I imagine adding this check at the IR
level when
> >> we also verify points 1 and 2
> >> above.  That will keep the code-region verification logic isolated
to the
> >> IR verifier.  The start/end
> >> intrinsics should not have any uses, so I'm not sure that they
would be
> >> moved/sunk on behalf
> >> of any other instruction.  In other words, I do not imagine that a
start
> >> and end would be split
> >> apart due to later MI optimizations.  If I discover that such a
case
> >> occurs, then I might add the
> >> basic-block check prior to emitting the code region data to the
object
> >> file.    Once  llvm-mca  is
> >> updated to handle branches, then we can remove this constraint.
> >>
> >> -Matt
> >>
> >> > -----Original Message-----
> >> > From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On
Behalf Of Matt
> >> Davis via llvm-
> >> > dev
> >> > Sent: Wednesday, November 21, 2018 8:47 AM
> >> > To: Andrea Di Biagio <andrea.dibiagio at gmail.com>
> >> > Cc: llvm-dev <llvm-dev at lists.llvm.org>; Di Biagio,
Andrea
> >> > <Andrea.Dibiagio at sony.com>; cfe-dev at
lists.llvm.org
> >> > Subject: Re: [llvm-dev] [RFC][llvm-mca] Adding binary support
to
> >> llvm-mca.
> >> >
> >> > Hi Andrea,
> >> >
> >> > Thanks for your input.
> >> >
> >> > On Wed, Nov 21, 2018 at 12:43:52PM +0000, Andrea Di Biagio
wrote:
> >> > [... snip ...]
> >> > > About the suggested design:
> >> > > I like the idea of being able to identify code regions
using a numeric
> >> > > identifier.
> >> > > However, what happens if a code region spans through
multiple basic
> >> blocks?
> >> >
> >> > The current patch does not take into consideration cases
where the
> >> > region start and end intrinsics are placed in different basic
blocks.
> >> > Such would be the case if a region is defined to span
multiple blocks.
> >> > This would be similar to the current case where a user places
a
> >> > #LLVM-MCA-BEGIN assembly comment in one block and an
#LLVM-MCA-END in
> >> > another.  However, as you point out below, if the user does
this in the
> >> > source code via intrinsics (just what this patch is
proposing), then
> >> > there is a chance that optimizations might change the layout
of the
> >> > instructions and confuse the ordering of the MCA intrinsics.
> >> >
> >> > Since MCA does not follow branches (MCA just treats a branch
as it would
> >> > a non-branching instruction), it seems that a user should be
aware that
> >> > defining MCA code regions that span multiple blocks might
result in an
> >> > unexpected analysis.  While we do not discourage this, it
seems like
> >> > such a case will probably not produce an expected result for
the user.
> >> > We could introduce a warning, or automatically divide the
regions so
> >> > that a single region can only contain a single block.
> >> >
> >> > > My understanding is that code regions are not allowed to
overlap. So,
> >> it
> >> > > makes sense if ` __mca_code_region_end()` doesn't
take an ID as input.
> >> > > However, what if ` __mca_code_region_end()` ends in a
different basic
> >> block?
> >> > >
> >> > > `__mca_code_region_start()` has to always dominate `
> >> > > __mca_code_region_end()`. This is trivial to verify when
both calls
> >> are in
> >> > > a same basic block; however, we need to make sure that
the
> >> relationship is
> >> > > still the same when the `end()` call is in a different
basic block.
> >> > > That would not be enough. I think we should also verify
that `
> >> > > __mca_code_region_end()` always post-dominates the call
to
> >> > > `__mca_code_region_start()`.
> >> >
> >> > In any case this patch should probably check dominance of the
> >> > intrinsics, even though MCA does not follow branches and MCA
does not
> >> > not explicitly forbid a region from containing multiple
blocks.
> >> >
> >> > >
> >> > > My question is: what happens with basic block
reordering? We don't
> >> know the
> >> > > layout of basic blocks until we reach code emission. How
does it work
> >> for
> >> > > regions that span through multiple basic blocks?. I
think your RFC
> >> should
> >> > > clarify this aspect.
> >> > >
> >> > > As a side note: at the moment, llvm-mca doesn't know
how to deal with
> >> > > branches. So, for simplicity we could force code regions
to only
> >> contain
> >> > > instructions from a single basic block.
> >> > >
> >> > > However, In future we may want to teach llvm-mca how to
analyze
> >> branchy
> >> > > code too. For example, we could introduce a simple
control-flow
> >> analysis in
> >> > > llvm-mca, and use an external "branch trace"
information (for
> >> example, a
> >> > > perf trace generated by an external tool) to decorate
branches with
> >> with
> >> > > branch probabilities (similarly to what we currently do
in LLVM with
> >> PGO).
> >> > > We could then use that knowledge to model branch
prediction and
> >> simulate
> >> > > what happens in the presence of multiple branches.
> >> > >
> >> > > So, the idea of having regions that potentially span
multiple basic
> >> blocks
> >> > > is not bad in general. However, I think you should
better clarify
> >> what are
> >> > > the constraints (at least, you should answer to my
questions from
> >> before).
> >> >
> >> > I agree! Thanks for pointing that out.
> >> >
> >> > > If we decide to use those new intrinsics, then those
should be
> >> experimental
> >> > > (at least to start).
> >> >
> >> > Agreed.
> >> >
> >> > -Matt
> >> >
> >> > > On Thu, Nov 15, 2018 at 11:07 PM via llvm-dev <
> >> llvm-dev at lists.llvm.org>
> >> > > wrote:
> >> > >
> >> > > > 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
(which involve both
> >> > > > clang and llvm) 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:
> >> > > >
> >> > > > * We need a way for a user to identify a
region/block of code they
> >> want
> >> > > >    analyzed by llvm-mca.
> >> > > > * 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
> >> > > >    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,"", at
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.
> >> > > >
> >> > > > For purposes of review and to communicate the idea,
the change is
> >> > > > presented as a monolithic patch here:
> >> > > >
> >> > > > https://reviews.llvm.org/D54603
> >> > > >
> >> > > > The change is presented as a monolithic patch;
however, if accepted
> >> > > > the patch will be split into three smaller patches:
> >> > > > 1. The introduction of the builtins to clang.
> >> > > > 2. The llvm portion (the added intrinsics).
> >> > > > 3. The llvm-mca portion.
> >> > > >
> >> > > > Thanks!
> >> > > >
> >> > > > -Matt
> >> > > > _______________________________________________
> >> > > > LLVM Developers mailing list
> >> > > > llvm-dev at lists.llvm.org
> >> > > >
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >> > > >
> >> > _______________________________________________
> >> > LLVM Developers mailing list
> >> > llvm-dev at lists.llvm.org
> >> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >>
> >