Okay, so we're switching topics a bit away from MPI to something at least a little bit
different, link time call graph analysis.
All right, thank you. So, yeah, we're going to talk about user-guided program instrumentation
approach and especially a link time call graph analysis extension to that project, which
kind of makes it more usable. So, to give some background on this work, I'm involved in
a project called XRFoam that deals with the Open Foam Computational Fluid Dynamics Toolbox.
And that's a very complex code, quite large. And the goal here is to improve the performance
of Open Foam for HPC systems, especially for the exascale error. And one of the things
we do is, yeah, develop empirical performance models. And for that, we have sort of developed
like workflow, how we do that. We start with several measurements where we get an initial
overview and identify hotspots. Then, based on these hotspots, do an analysis of the critical
kernels. And finally, we can do the empirical modeling in order to find scalability bugs
and predict performance when scaling out. And so, especially for the focus measurements
and the modeling, you need quite accurate and reliable methods to be sure that the data
you collect is right and you have the right level of detail. And what we use for that
is code instrumentation. And just to give the background, I want to give an example.
For example, in GCC and Clang, you have the F instrument functions flag, which does a
very basic instrumentation. But if you activate that flag, you insert these, or the compiler
inserts these function enter and exit probes, which are then a runtime interface with a
profiling tool which records runtime. Or, yeah, more involved metrics, maybe performance
counters, stuff like that. And the big problem with this instrumentation approach, especially
compared to other mechanisms like sampling, is that it can increase the run times by orders
of magnitude if you're not careful, if you just instrument every function. So, you have
to have some kind of selection mechanism in place to prevent that. And sort of the method
that's most commonly used is to use profile-based filtering, either manual, where you look at
the profile that is generated by the instrumented measurement, and then determine, like, which
functions, maybe, for example, very small or called very often and don't do much work,
so that can be filtered out. And there are also tools like Scope, which can help in generating
these filters. However, this is only, like, on a purely profile base and there's no, yeah,
no calling contacts involved in the decision. So, there are some other call graph-based
approaches where you have a static call graph that is then used to make the selection.
I want to highlight, too, there's Pira, which does automatic iterative refinement. So, we
start with a static selection based on the statically collected call graph, and then
iteratively compile a program with instrumentation, execute it, measure it, and then look at
the profile in order to determine what to filter out. And then the tool we're working
on is the copy tool, which is short for compile-assisted performance instrumentation, and that one
is more focused on allowing the user to specify what he wants to measure, so he can say, okay,
I'm interested in MPI communications, so that is what I want to measure.
So, here's a very high-level overview of how copy works. So, you have your source code,
and that is put into the static analysis in order to generate the call graph. And then
at the same time, the user specifies the measurement objective in front of a selection spec. We
have a simple DSL for that. And this together is then fed into the copy tool in order to
generate the instrumentation configuration, which is hopefully low overhead.
And, yeah, so let's consider an example for that. So, we might have the following scenario.
So, I want to record all call paths that contain MPI communication. Additionally, I want to
measure functions that contain loops with at least 10 floating point operations, and
I don't care about system headers or inline functions. And this is how this looks as a
copy spec. I won't get into the details of the syntax, but you can combine different
selection modules where you start with the set of all functions and then sort of here
select inline functions or system header functions. And then you can combine them to, in the
end, produce one set that you want to instrument. And for this particular example, this reduces
the number of instrument functions by 74 percent for our form test case.
So, the call graph is sort of the base data structure that we use for all the analysis
and for the selection. And this is currently generated based on the source level by a tool
called MetaCG. And this can be a bit cumbersome for very complex applications, such as Open
Foom, because you, yeah, you need sort of a separate source code analysis step, and
that can be difficult to set up, especially if there's like shared library dependencies
stuff like that. So, it can be tricky. And so, we looked into how we can maybe generate
the call graph at different stages. And so, this is what Tim is going to talk about, how
we can generate the call graph at different program stages. And then we introduced the
caged compiler plugin, where we, yeah, evaluate how this can be done at link time.
So, well, thank you. So, we were interested in the whole program call graphs. This is
because CAPI, the tool that does our instrumentation, needs to be aware of every function inside
our call graph, which means that we are, that it's necessary to have a whole program view.
And the tools that were used like MetaCG were able to create a call graph, and they
have the distinct advantage of being able to annotate metadata to this call graph. This
is where the name MetaCG came from. And this means that we not only can answer structural
questions like we want to instrument every function that eventually call paths down
to some MPI call, but we can also answer instrument based on metadata. For example, the loop depth
specification or floating point operations. And yes, there were multiple possible ways
to generate a call graph. One of them is source code. One of them is the intermediate representation
that is basically part of every compiler, especially the LLVM compile pipeline, and
machine code at the very last. So, the basic idea is, well, we have the source code. Let's
do call graph generation on the source code, which is relatively easy. MetaCG is doing
it on a source code basis. But this means as you feed every single source code file
into MetaCG, this means that your view of the program is limited to one translation unit
at a time. So, you then need to merge those part call graphs of every translation unit
together to generate this overview of the whole program that you need. The information
you then gather from your profiling maps very cleanly back to your source code, because
once you find a function, well, it's named the same way in your source code. But on the
other hand, what you write in your source code is not necessarily what's actually executed
on the machine, right? Because there might be code transformation, constant propagation,
dead code elimination, inlining. And this is actually something we want to be aware
of if we are doing instrumentation, not that we want to instrument a function that doesn't
exist anymore. Also, this merging of the translation units means that the user is involved. The
user currently has to specify when he uses MetaCG which source code translation units
belong to one target. And then manually has to tell MetaCG these functions are all to
be merged. Please generate the call graph for that. And the user might not perfectly emulate
the linker behavior. So, there are different resolution types that a linker might choose
if there are samely named structs or classes. And, depending on how you are implementing
your merging process, you might have slight differences between your call graph that you
generated and that's what the linker will eventually do. So, the other extreme would
be, well, let's do it on the compiled machine code then. Reverse engineering tools like
radar or Ghidra are able to generate call graphs and binary data just fine. And those
have the very distinct advantages that this is actually what is run on the machine. There
are no code transformation left. You have the advantage of being able to see machine
code optimization passes if they are influencing the generated call graph. But, on the other
hand, a lot of information, the metadata that we also would like to be able to instrument
based upon are lost as soon as we go down to machine code. Inlining already happened,
so there is no function annotated with please inline anymore. Also, pointer type information,
as we heard in the talk earlier, gets lost as soon as we go down to machine type. And
constness is also something that is more to be inferred than actually stated once we
go down to machine code. And so, we decided the best of both worlds is probably the LLVMIR
because it's a heavily annotated representation. It is close enough to what will run on the
machine that we have the ability to observe the code transformation. We are able to give
more specific estimates on what the actual cost of a function might be because we have
more clear way of tracking, for example, instruction counts, floating ops, and integer ops. On
the other hand, it's also close enough to what the user actually wrote because we're
not down on the machine code yet. And we can figure out the inlining stuff, the constness,
the virtual functions. We can get type information in the IR. And if we do it at link time, we
are not even limited to the translation unit by translation unit scope that source code
based approaches are. So, if you have your pretty default compile pipeline, you have
your source code, which builds a translation unit, gets fed into the compiler, which outputs
intermediate representation, and then the optimizer runs there and multiple source code
translation unit optimized IR modules are fed into the linker. And we can do our call
graph analysis inside the linker, solve our translation unit problem, and are able to
have all our information ready. So, to do this, we developed the cage plugin. Cage stands
for call graph embedding LLVM plugin. And it basically generates a call graph using
some of LLVM tools, does some annotation, virtual function call analysis, and this can
run as part of the optimizer in the pipeline, but it can also run as part of the LLVM linker.
Also as a plugin, for which we use a slightly modified version of the LLVM linker, but
the basic logic of running plugins in the LLVM linker was there. So, then we do a V
table analysis, our metadata annotation, because it's all available to us. And then
we embed the result into the binary, which enables dynamic augmentation. And I will come
to that one later. So, at link time, we're doing static analysis basically. And as I
already mentioned, we split our information in basically two types. One of them is structural
information like call hierarchies, call paths, call depth, the number of children, how deep
we are in our path. And you also have virtual function calls, which are mostly structural,
because once you have virtual and polymorphic calls, you have like a set of functions that
are probably being called by that pointer. And so, we can narrow down the possibilities
of which functions are called, but we cannot actually statically figure out this function
is getting called. So, it's slightly metadata based, but it's also mostly structural. On
the metadata information side, we have instruction composition, so we can determine what is the
relation between arithmetic operations and memory operations, for example, or we can
generate local and global loop depth estimates. And then we have inlining information, which
is metadata, because inlining is not like a must do for a compiler, just because you
have specified inlining for a function doesn't mean that the compiler will actually inline
the function. So, it's partly structural information and partly metadata, so you see
there's no clear like line between those, they blur at some points, but we can represent
all those in the metadata annotated call graph. And if you remember, we were able to do dynamic
augmentation. Well, what is dynamic augmentation? If you remember, each object contains the
call graph that we generated, which means that the call graphs can be aggregated at runtime
if a shared library is loaded, because even if you are at link time, even if you can see
all the statically linked objects, all the translation units that belong to your target,
your binary might load a shared library, which then, well, you're unaware of. So, the idea
is, as soon as the main executable is loaded, it passes its embedded call graph on startup
to a runtime collecting library. And then, the main executable can load whatever shared
object it wants. And if this shared object also contains a call graph, then this runtime
collector gets passed this call graph on the first load of the shared object and can aggregate
it like merging. So, we're basically back to the translation unit by translation unit
based approach, but now we're doing shared library on binary and executable based merging.
And then, we attach all this data together to one really big whole program call graph,
now including shared objects. And then, we can export this, for example, and pass it
back to Karpi for some further refinement of the instrumentation.
Go ahead. All right. Thanks. So, to put it all together, for Karpi, we have the call
graph analysis approach, Tim just explained. So, for each object file, we have the call
graph analysis and then the embedding. And then, on the runtime side, we can sort of
merge the main executable call graph with the shared libraries as they are loaded. And
we defer the instrumentation using a dynamic instrumentation approach in order to sort
of apply that selection dynamically. And, yeah, that's how it works. So, to summarize,
we are developing the Karpi tool for instrumentation selection based on call graph analysis. And
we have explored this cage plugin for generating this call graph information at link time,
which allows whole program visibility and this dynamic documentation. And together
with Karpi, we can, yeah, use the embedded call graph to run the selection at runtime
and thereby improving Karpi to make the compilation process and the analysis process more streamlined.
And this is sort of an active development. So, at this point, we don't have a very detailed
evaluation about performance and stuff like that. So, there's some concerns, for example,
when you go to very big programs and do LTO, there might be performance problems. So, there
might be more work to make it viable in that regard. But, yeah, it works well in a prototype
fashion. Yeah. Thank you.
Any questions?
Perhaps I was a bit distracted. So, I have two questions. If you can comment on Lambda
functions, OMP sections, or OMP sections of the code, not specific constructs, and instruction
cache. If you can comment how those are handled, those three aspects, let's say.
So when it comes to OpenMP, we don't at the moment have any specific OpenMP profiling
interface that we target. So, this might be something that is probably useful in the future.
But for now, we just do the basic functions mutation and select on that. Yeah. Then the
other point was, sorry, could you repeat?
So, do you want to comment on that?
So, lambdas and caches, so caching, no, there is no logic to handle caching in any way.
And regarding lambdas and OpenMP, it's, if you're talking about profiling, you've got
your answer right there. But if you're talking about generating call graphs in which lambdas
and OpenMP runtime calls are available, then the call graph will actually figure out that
there are OpenMP runtime calls, and will correctly, if I remember correctly, will figure out that
this function calls back to the OpenMP runtime, because once you are in IR, the runtimes actually
carved out, all the pragmas were removed from the actual source code. So, we are aware
of OpenMP, but we are not using that information currently for any profiling. But you could
do metadata-based copy selection with it. So, every call path that eventually leads
to an OpenMP runtime call would be a valid instrumentation using copy.
Just that the question of the instruction cache is whether, this is my ignorance, but
if you are reintroducing a lot of new instructions here in the code, or in the code that is being
read, I was thinking whether too much data ends up, maybe I didn't understand well.
So, this is more of a performance-related question, right? Okay, so, yes, of course,
you introduce a new instruction whenever a shared library is loaded, because we then
add instructions that pass the call graph back to our runtime collecting facility, and
we also introduce instructions because we are using a profiling approach, which are function
calls. So, yes, we are impeding the instruction fetching, instruction caching flow, which
is also why profiling has rather high overhead compared to sampling approaches, for example.
But as Sebastian told, we have not really extensively profiled our application, quite
ironic, so we are not aware how much the benefit or the impact actually would be.
So in your slide, you say you have a fork of LLD. The obvious question is, what's stopping
you from upstreaming this? So, yes, we have a fork of LLD that just basically
exposes the flag load new pass manager plugin, and you pass the plugin, and it does the rest.
What's currently holding us back from upstreaming is it's not very well developed, it was coupled
together in half a week or something, and there already is an open merge request on
fabricator that implements this exact functionality for, if I remember correctly, LLDM9, which
was abandoned for a year until it was totally abandoned and closed, and so we didn't actually
figure out how to make this more interesting. Don't take that as a signal. People just move
jobs or whatever, so try it again and bash people, and I can help you with that as well,
find the right people to get this, because it seems like a simple and obvious thing to
have. It isn't actually that hard. Apparently, there wasn't much interest in the community
back in 2020? Yes, that's too long ago. We will polish it a little much, and then hopefully
get this one upstream. Thanks. Any other questions? No. Okay. Thank you very much.
Thank you very much, Sebastian.