[llvm-dev] RFC: Comprehensive Static Instrumentation

[Xinliang David Li via llvm-dev]

On Mon, Jun 20, 2016 at 4:27 PM, Evgenii Stepanov <eugenis at google.com>
wrote:

> I like this non-LTO use model a lot. In my opinion, it does not
> conflict with the LTO model - the only difference is when the
> implementation of CSI hooks is injected into the build - compile time
> vs link time. I don't see any problem with injecting it both at
> compile and link time - this would take care of CSI hooks in third
> party libraries.
>
> I also don't understand the need of the export list. As I see it, the
> IR library of the tool is loaded at compilation time, internalized and
> merged with the IR for the module being compiled. If any CSI hooks
> remain undefined at this point, they are replaced with empty
> functions.


Yes, the IR library itself 'serves' as the export list in this case. Export
list is needed when IR library is not even used.

David




> The IR tool library should not have any global state, of
> course - it is an equivalent of the C++ header file. Exactly the same
> happens at LTO link time, in case the link brought in new CSI hooks
> unresolved at compilation time.
>
> ThinLTO uses a different build model - it's not compile+link, but
> compile+merge+compile+link or something like that AFAIK. This requires
> build system changes, and I imagine the extra work would not be worth
> the benefits for many smaller projects. I'd love if CSI worked without
> any kind of LTO with reasonable performance (btw, do you have the
> numbers for the slowdown with an empty tool without LTO?).
>
> On Mon, Jun 20, 2016 at 4:00 PM, TB Schardl via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> > Hey David,
> >
> > Thank you for your feedback.  I'm trying to understand the model you
> > sketched in order to compare it to CSI's current approach, but the
> details
> > of your proposal are still fuzzy to me.  In particular, although the
> model
> > you described would avoid using LTO to elide unused hooks, it seems more
> > complicated for both tool writers and tool users to use.  Please clarify
> > your model and shed some light on the questions below.
> >
> > 1) What does the "CSI dev tool" you describe look like?  In particular,
> how
> > does the tool writer produce and maintain an export list of non-stub hook
> > definitions for her tool?  Maintaining an export list manually would
> seem to
> > be an error-prone hassle.  One could imagine generating the export list
> > automatically with a custom compile-time pass that the tool-writer runs,
> but
> > maintaining consistency between a tool and its export list remains a
> concern
> > for both the tool writer and the tool user.
> >
> > 2) To clarify, in your scheme, the tool writer produces an export list as
> > well as an object/bitcode for the tool.  The tool user compiles the
> > program-under-test using the export list, and then incorporates the tool
> > object/bitcode at link time.  Is this what you have in mind?
> >
> > 3) Do I understand correctly that your model only gets rid of the need
> for
> > LTO to elide unused instrumentation hooks?  In particular, are other
> > optimizations on the instrumentation still contingent on LTO (or
> ThinLTO)?
> > One nice feature of the current design is that tool writers can use
> > properties passed to hooks to elide instrumentation conditionally based
> on
> > common static analysis.  It looks like optimizations based on properties
> are
> > still possible in the model you propose, but as with the current design,
> > they would still rely on LTO or ThinLTO.
> >
> > 4) In your model, if the tool user wants to analyze his program with
> several
> > different tools, then he must recompile his program from source once for
> > each tool.  Is this correct?  The argument in this thread seems to be
> that
> > recompiling the program from source is no worse than using LTO because
> LTO
> > incurs high overhead.  (From the results I've found online
> > http://llvm.org/devmtg/2015-04/slides/ThinLTO_EuroLLVM2015.pdf, however,
> > ThinLTO seems to be much lower overhead than LTO.  Are these results
> still
> > accurate?)
> >
> > 5) What happens when the program-under-test is built from multiple source
> > files?  It seems that all source files must be compiled using the same
> > export list, which is a burden on the tool user.  Although this
> complexity
> > could be managed by the program's build system, managing this complexity
> > through the build system or by some other means still seems like a
> burden on
> > the tool user.
> >
> > 6) What happens when the program-under-test uses third-party libraries?
> If
> > the tool user does not have access to the sources of those libraries,
> then I
> > don't see how they can properly elide hooks using an export list.  At
> best,
> > it would seem that the library writer would distribute a object/bitcode
> for
> > the library with all hooks in place already, which is exactly what
> happens
> > with CSI's the existing design.
> >
> > Thanks again for your feedback.
> >
> > Cheers,
> > TB
> >
> > On Sun, Jun 19, 2016 at 6:45 PM, Xinliang David Li <xinliangli at gmail.com
> >
> > wrote:
> >>
> >> It is great that CSI does not depend on lto for correctness, but I think
> >> it should remove the dependency completely. Being able to work with lto
> >> should be something that is supported, but lto is not required.
> >>
> >> Such a design will greatly increase CSI usability not only for tool
> >> users(app developers), but also for CSI tool developers.
> >>
> >> My understanding is that it is not far to get there. Here is the CSI use
> >> model I am thinking:
> >>
> >> 1) a CSI dev tool can be provided to tool developers to produce a) hook
> >> library in native object format b) hook lib in bitcode format c) export
> list
> >> of non stub hook defs
> >>
> >> 2) the compiler implementation of CSI lowering will check the export
> list
> >> and decide whether to lower a hook call to noop or not
> >>
> >> 3) in thinlto mode, the bitcode can be readin for inlining. This works
> for
> >> lto too
> >>
> >> 4) compiler driver can hide all the above from the users
> >>
> >>
> >> In short, making it work in default mode makes it easier to deploy and
> can
> >> get you a long way
> >>
> >> Thanks,
> >>
> >> David
> >>
> >>
> >> On Sunday, June 19, 2016, TB Schardl <neboat at mit.edu> wrote:
> >>>
> >>> Hey Peter and David,
> >>>
> >>> Thank you for your comments.
> >>>
> >>> As mentioned elsewhere, the current design of CSI does not rely on LTO
> >>> for correctness.  The tool-instrumented executable will run correctly
> even
> >>> if the linker performs no optimization.  In particular, unused
> >>> instrumentation hooks are implemented by default as nop functions,
> which
> >>> just return immediately.  CSI is a system that can use LTO to improve
> tool
> >>> performance; it does not require LTO to function.
> >>>
> >>> One of our considerations when developing CSI version 1 was design
> >>> simplicity.  As such, CSI version 1 essentially consists of three
> >>> components:
> >>> 1) A compile-time pass that the tool user runs to insert
> instrumentation
> >>> hooks.
> >>> 2) A null-tool library that provides default nop implementations for
> each
> >>> instrumentation hook.  When a tool writer implements a tool using the
> CSI
> >>> API, the tool writer's implemented hooks override the corresponding
> default
> >>> implementations.
> >>> 3) A runtime library that implements certain powerful features of CSI,
> >>> including contiguous sets of ID's for hooks.
> >>>
> >>> We've been thinking about how CSI might work with -mlink-bitcode-file.
> >>> From our admittedly limited understanding of that feature, it seems
> that a
> >>> design that uses -mlink-bitcode-file would still require something
> like the
> >>> first and third components of the existing design.  Additional
> complexity
> >>> might be needed to get CSI to work with -mlink-bitcode-file, but these
> two
> >>> components seem to be core to CSI, regardless of whether
> -mlink-bitcode-file
> >>> is used.  (Eliminating the null-tool library amounts to eliminating a
> pretty
> >>> simple 39-line C file, which at first blush doesn't look like a big
> win in
> >>> design complexity).
> >>>
> >>> CSI focuses on making it easy for tool writers to create many
> >>> dynamic-analysis tools.  CSI can leverage standard compiler
> optimizations to
> >>> improve tool performance, if the tool user employs mechanisms such as
> LTO or
> >>> thinLTO, but LTO itself is not mandatory.  It might be worthwhile to
> explore
> >>> other approaches with different trade-offs, such as
> -mlink-bitcode-file, but
> >>> the existing design doesn't preclude these approaches down the road,
> and
> >>> they will be able to share the same infrastructure.  Unless the other
> >>> approaches are dramatically simpler, the existing design seems like a
> good
> >>> place to start.
> >>>
> >>> Cheers,
> >>> TB
> >>>
> >>> On Fri, Jun 17, 2016 at 4:25 PM, Peter Collingbourne via llvm-dev
> >>> <llvm-dev at lists.llvm.org> wrote:
> >>>>
> >>>>
> >>>>
> >>>> On Thu, Jun 16, 2016 at 10:16 PM, Xinliang David Li via llvm-dev
> >>>> <llvm-dev at lists.llvm.org> wrote:
> >>>>>
> >>>>>
> >>>>>
> >>>>> On Thu, Jun 16, 2016 at 3:27 PM, Mehdi Amini via llvm-dev
> >>>>> <llvm-dev at lists.llvm.org> wrote:
> >>>>>>
> >>>>>> Hi TB,
> >>>>>>
> >>>>>> Thanks for you answer.
> >>>>>>
> >>>>>> On Jun 16, 2016, at 2:50 PM, TB Schardl <neboat at mit.edu> wrote:
> >>>>>>
> >>>>>> 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.)
> >>>>>>
> >>>>>>
> >>>>>> Ok this is roughly what I had in mind.
> >>>>>>
> >>>>>> I still believe it is not great to rely on LTO, and better, it is
> not
> >>>>>> needed to achieve this result.
> >>>>>>
> >>>>>> For instance, I don't see why the "library" that defines the subset
> of
> >>>>>> instrumentation hooks used by this tool can't be fed during a
> regular
> >>>>>> compile, and the useless hook be eliminated at this point.
> >>>>>> Implementation detail, but in practice, instead of feeding the
> library
> >>>>>> itself, the "framework" that allows to generate the library for the
> tool
> >>>>>> writer can output a "configuration file" along side the library,
> and this
> >>>>>> configuration file is what is fed to the compiler and tells the
> >>>>>> instrumentation pass which of the hooks to generate. It sounds more
> >>>>>> efficient to me, and remove the dependency on LTO.
> >>>>>> I imagine there is a possible drawback that I'm missing right now...
> >>>>>
> >>>>>
> >>>>>
> >>>>> I agree that the tool does not need to depend on full LTO. What is
> >>>>> needed is essentially an option or configuration such that the
> compiler can
> >>>>> find the bit code file(s) for the hooks during compilation time. It
> is
> >>>>> pretty much similar to how math function inlining can be done ...
> >>>>
> >>>>
> >>>> I agree, and I would strongly prefer that the design worked like this
> >>>> rather than relying on LTO.
> >>>>
> >>>> The flag for loading bitcode already exists, and is called
> >>>> -mlink-bitcode-file. Projects such as libclc already use it, I
> believe.
> >>>>
> >>>> What might be useful is if CSI improved the infrastructure around
> >>>> -mlink-bitcode-file to make it more convenient to produce compatible
> bitcode
> >>>> files. libclc for example relies on a post-processing pass to change
> symbol
> >>>> linkage, and I think that can be avoided by changing symbol linkages
> as they
> >>>> are imported from the bitcode file.
> >>>>
> >>>> Peter
> >>>>
> >>>>> David
> >>>>>
> >>>>>
> >>>>>
> >>>>>>
> >>>>>>
> >>>>>>
> >>>>>>
> >>>>>> 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).
> >>>>>>
> >>>>>>
> >>>>>> I expect this to be reproducible on most non-trivial C/C++ programs.
> >>>>>> But taking clang as an example, just running `ninja clang` on OS X a
> >>>>>> not-so-recent 12-cores machine takes 970s with LTO and 252s without
> (and I
> >>>>>> believe this is without debug info...).
> >>>>>> Running just `ninja` to build all of llvm/clang here would take *a
> >>>>>> lot* longer with LTO, and not so much without.
> >>>>>>
> >>>>>> The LTO builds without assert
> >>>>>>
> >>>>>> Best,
> >>>>>>
> >>>>>> --
> >>>>>> Mehdi
> >>>>>>
> >>>>>>
> >>>>>>
> >>>>>>
> >>>>>>
> >>>>>> 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
> >>>>>>
> >>>>>>
> >>>>>>
> >>>>>> _______________________________________________
> >>>>>> 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
> >>>>>
> >>>>
> >>>>
> >>>>
> >>>> --
> >>>> --
> >>>> Peter
> >>>>
> >>>> _______________________________________________
> >>>> 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
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160620/e3dcd1d9/attachment.html>