[llvm-dev] RFC: Comprehensive Static Instrumentation

[TB Schardl via llvm-dev]

Hey Mehdi,

Thank you for your comments.  I've CC'd the CSI mailing list with your
comments and put my responses inline.  Please let me know any other
questions you have.

Cheers,
TB

On Thu, Jun 16, 2016 at 3:48 PM, Mehdi Amini <mehdi.amini at apple.com> wrote:

>
> On Jun 16, 2016, at 9:01 AM, TB Schardl via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> Hey LLVM-dev,
>
> We propose to build the CSI framework to provide a comprehensive suite of
> compiler-inserted instrumentation hooks that dynamic-analysis tools can use
> to observe and investigate program runtime behavior.  Traditionally, tools
> based on compiler instrumentation would each separately modify the compiler
> to insert their own instrumentation.  In contrast, CSI inserts a standard
> collection of instrumentation hooks into the program-under-test.  Each
> CSI-tool is implemented as a library that defines relevant hooks, and the
> remaining hooks are "nulled" out and elided during link-time optimization
> (LTO), resulting in instrumented runtimes on par with custom
> instrumentation.  CSI allows many compiler-based tools to be written as
> simple libraries without modifying the compiler, greatly lowering the bar
> for
> developing dynamic-analysis tools.
>
> ================
> Motivation
> ================
>
> Key to understanding and improving the behavior of any system is
> visibility -- the ability to know what is going on inside the system.
> Various dynamic-analysis tools, such as race detectors, memory checkers,
> cache simulators, call-graph generators, code-coverage analyzers, and
> performance profilers, rely on compiler instrumentation to gain visibility
> into the program behaviors during execution.  With this approach, the tool
> writer modifies the compiler to insert instrumentation code into the
> program-under-test so that it can execute behind the scene while the
> program-under-test runs.  This approach, however, means that the
> development of new tools requires compiler work, which many potential tool
> writers are ill equipped to do, and thus raises the bar for building new
> and innovative tools.
>
> The goal of the CSI framework is to provide comprehensive static
> instrumentation through the compiler, in order to simplify the task of
> building efficient and effective platform-independent tools.  The CSI
> framework allows the tool writer to easily develop analysis tools that
> require
> compiler instrumentation without needing to understand the compiler
> internals or modifying the compiler, which greatly lowers the bar for
> developing dynamic-analysis tools.
>
> ================
> Approach
> ================
>
> The CSI framework inserts instrumentation hooks at salient locations
> throughout the compiled code of a program-under-test, such as function
> entry and exit points, basic-block entry and exit points, before and after
> each memory operation, etc.  Tool writers can instrument a
> program-under-test simply by first writing a library that defines the
> semantics of relevant hooks
> and then statically linking their compiled library with the
> program-under-test.
>
> At first glance, this brute-force method of inserting hooks at every
> salient location in the program-under-test seems to be replete with
> overheads.  CSI overcomes these overheads through the use of
> link-time-optimization (LTO), which is now readily available in most major
> compilers, including GCC and LLVM.  Using LTO, instrumentation hooks that
> are not used by a particular tool can be elided, allowing the overheads of
> these hooks to be avoided when the
>
>
> I don't understand this flow: the front-end emits all the possible
> instrumentation but the useless calls to the runtime will be removed during
> the link?
> It means that the final binary is specialized for a given tool right? What
> is the advantage of generating this useless instrumentation in the first
> place then? I'm missing a piece here...
>

Here's the idea.  When a tool user, who has a program they want to
instrument, compiles their program source into an object/bitcode, he can
turn on the CSI compile-time pass to insert instrumentation hooks (function
calls to instrumentation routines) throughout the IR of the program.
Separately, a tool writer implements a particular tool by writing a library
that defines the subset of instrumentation hooks she cares about.  At link
time, the object/bitcode of the program source is linked with the object
file/bitcode of the tool, resulting in a tool-instrumented executable.
When LTO is used at link time, unused instrumentation is elided, and
additional optimizations can run on the instrumented program.  (I'm happy
to send you a nice picture that we have of this flow, if the mailing list
doesn't mind.)

The final binary is specialized to a given tool.  One advantage of CSI,
however, is that a single set of instrumentation covers the needs of a wide
variety of tools, since different tools provide different implementations
of the same hooks.  The specialization of a binary to a given tool happens
at link time.


>
> instrumented program-under-test is run.  Furthermore, LTO can optimize a
> tool's instrumentation within a program using traditional compiler
> optimizations.  Our initial study indicates that the use of LTO does not
> unduly slow down the build time
>
>
> This is a false claim: LTO has a very large overhead, and especially is
> not parallel, so the more core you have the more the difference will be. We
> frequently observes builds that are 3 times slower. Moreover, LTO is not
> incremental friendly and during debug (which is very relevant with
> sanitizer) rebuilding involves waiting for the full link to occur again.
>
>
Can you please point us towards some projects where LTO incurs a 3x
slowdown?  We're interested in the overhead of LTO on build times, and
although we've found LTO to incur more overhead on parallel build times
than serial build times, as you mentioned, the overheads we've measured on
serial or parallel builds have been less than 40% (which we saw when
building the Apache HTTP server).

We've also designed CSI such that it does not depend on LTO for
correctness; the program and tool will work correctly with ordinary ld.  Of
course, the downside of not using LTO is that instrumentation is not
optimized, and in particular, unused instrumentation will incur overhead.


>
> --
> Mehdi
>
> , and the LTO can indeed optimize away unused hooks.  One of our
> experiments with Apache HTTP server shows that, compiling with CSI and
> linking with the "null" CSI-tool (which consists solely of empty hooks)
> slows down the build time of the Apache HTTP server by less than 40%, and
> the resulting tool-instrumented executable is as fast as the original
> uninstrumented code.
>
>
> ================
> CSI version 1
> ================
>
> The initial version of CSI supports a basic set of hooks that covers the
> following categories of program objects: functions, function exits
> (specifically, returns), basic blocks, call sites, loads, and stores.  We
> prioritized instrumenting these IR objects based on the need of seven
> example CSI tools, including a race detector, a cache-reuse analyzer, and a
> code-coverage analyzer.  We plan to evolve the CSI API over time to be more
> comprehensive, and we have designed the CSI API to be extensible, allowing
> new instrumentation to be added as needs grow.  We chose to initially
> implement a minimal "core" set of hooks, because we felt it was best to add
> new instrumentation on an as-needed basis in order to keep the interface
> simple.
>
> There are three salient features about the design of CSI.  First, CSI
> assigns each instrumented program object a unique integer identifier within
> one of the (currently) six program-object categories.  Within each
> category, the ID's are consecutively numbered from 0 up to the number of
> such objects minus 1.  The contiguous assignment of the ID's allows the
> tool writer to easily keep track of IR objects in the program and iterate
> through all objects in a category (whether the object is encountered during
> execution or not).  Second, CSI provides a platform-independent means to
> relate a given program object to locations in the source code.
> Specifically, CSI provides "front-end-data (FED)" tables, which provide
> file name and source lines for each program object given the object's ID.
> Third, each CSI hook takes in as a parameter a "property": a 64-bit
> unsigned integer that CSI uses to export the results of compiler analyses
> and other information known at compile time.  The use of properties allow
> the tool to rely on compiler analyses to optimize instrumentation and
> decrease overhead.  In particular, since the value of a property is known
> at compile time, LTO can constant-fold the conditional test around a
> property to elide unnecessary instrumentation.
>
> ================
> Future plan
> ================
>
> We plan to expand CSI in future versions by instrumenting additional
> program objects, such as atomic instructions, floating-point instructions,
> and exceptions.  We are also planning to provide additional static
> information to tool writers, both through information encoded in the
> properties passed to hooks and by other means.  In particular, we are also
> looking at mechanisms to present tool writers with more complex static
> information, such as how different program objects relate to each other,
> e.g., which basic blocks belong to a given function.
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160616/312c260b/attachment.html>