llvm dev - Jun 2016 - RFC: Comprehensive Static Instrumentation

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

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, 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160616/f83e55e1/attachment.html>

CC'ing the mailing list for the CSI project.

On Thu, Jun 16, 2016 at 12:01 PM, TB Schardl <neboat at mit.edu> 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
>
> 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, 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.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160616/22de2d66/attachment.html>

I am very glad this project reached the state where we can start the public
code review. Please shoot the patches for review when ready.

--kcc

On Thu, Jun 16, 2016 at 12:14 PM, TB Schardl via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> CC'ing the mailing list for the CSI project.
>
> On Thu, Jun 16, 2016 at 12:01 PM, TB Schardl <neboat at mit.edu>
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
>>
>> 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, 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/7603fa0e/attachment.html>

> 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...

> 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.


-- 
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/007b1c1c/attachment.html>

Dear TB,

Comments inline below.

On 6/16/16 11:01 AM, TB Schardl via llvm-dev 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.
>
Can you clarify the scope of tools that you want to develop?  Are these 
profiling tools, security enforcement tools, debugging tools, etc?  The 
type of tools you want to build will dictate whether such a framework 
makes sense.
>
> ===============>
> 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
>
> instrumented program-under-test is run.
>
The algorithms for optimizing away run-time hooks is not necessarily 
uniform.  For example, if a tool instruments loads and stores to collect 
the set of memory locations accessed by a program, then optimizing away 
a redundant check on a store is okay.  If the instrumentation is meant 
to enforce memory safety, then redundant checks can only be optimized 
away if there is no intervening call to free() between the two checks 
(which may require inter-procedural analysis to determine).  In such a 
case, you either need to be very pessimistic about the optimizations 
that you use, or you will get incorrect optimizations for certain 
classes of dynamic analyses.

> 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, 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.
>
Is your intention to have a compiler flag that enables insertions of 
hooks, or are you planning on having a pass always add the hooks and 
having libLTO always remove them?  I assume the former, but you should 
probably clarify.

>
> ===============>
> 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.
>
Don't forget that atomic instructions (e.g., compare-and-swap) and some 
of the intrinsics (e.g., llvm.memcpy()) also access memory.
> 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.
>
As an aside, I'm not sure that I buy the idea that tool developers 
should be oblivious to the compiler internals.  If a tool developer 
doesn't understand what the compiler is doing, then she/he may not 
understand the results of the output.  For example, LLVM load/stores do 
not include stack spill slots, memory accesses incurred by calling 
conventions, etc.  Depending on where the instrumentation passes are 
placed in the pass pipeline, instrumentation calls can be moved or 
removed (perhaps in undesirable ways for some dynamic analysis 
applications).

I would also argue that a key design feature of LLVM is to make writing 
such passes simple, and I think LLVM accomplishes this.  If one 
understands how to build an efficient dynamic analysis, one can probably 
handle writing the compiler passes.

Overall, I think having common instrumentation infrastructure is a good 
thing.  However, I'm not sure how common it can be across different 
applications of instrumentation.  As an example, most memory safety 
solutions have the same instrumentation and optimization needs (and 
constraints on optimization) regardless of how they implement the checks 
on loads and stores.  However, it's less clear to me that a race 
detector and a memory safety compiler can safely use the same 
optimizations.  You may find yourself implementing a common 
infrastructure with each tool implementing specialized optimizations to 
make each type of dynamic analysis really fast.

Food for thought,

John Criswell
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160616/6f79aa3a/attachment-0001.html>

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>

Hey John,

Thanks for your comments.  I've CC'd the CSI mailing list with your
comments and responded inline.  Please let me know if you have further
questions.

Cheers,
TB

On Thu, Jun 16, 2016 at 3:51 PM, John Criswell <jtcriswel at gmail.com>
wrote:
> Dear TB,
>
> Comments inline below.
>
> On 6/16/16 11:01 AM, TB Schardl via llvm-dev 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.
>
>
> Can you clarify the scope of tools that you want to develop?  Are these
> profiling tools, security enforcement tools, debugging tools, etc?  The
> type of tools you want to build will dictate whether such a framework makes
> sense.
>
For the first version of CSI, we've looked at tools including memory
checkers, race detectors, performance profilers, call-graph generators,
cache analyzers, and code-coverage analyzers.  Our experience working with
and developing such tools has shown us that these tools benefit from
instrumentation at the IR level, which is where we have currently targeted
CSI.  One benefit of targeting the IR is that CSI tools are thus
source-language and machine-architecture independent.  For future versions
of CSI, we are interested in including instrumentation in the front end and
back end.

>
>
>
> ===============>
> 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
>
> instrumented program-under-test is run.
>
>
> The algorithms for optimizing away run-time hooks is not necessarily
> uniform.  For example, if a tool instruments loads and stores to collect
> the set of memory locations accessed by a program, then optimizing away a
> redundant check on a store is okay.  If the instrumentation is meant to
> enforce memory safety, then redundant checks can only be optimized away if
> there is no intervening call to free() between the two checks (which may
> require inter-procedural analysis to determine).  In such a case, you
> either need to be very pessimistic about the optimizations that you use, or
> you will get incorrect optimizations for certain classes of dynamic
> analyses.
>
The safety of performing certain optimizations on an instrumented program
depends on the tool, as you describe, and exists regardless of whether the
tool is implemented with CSI or custom compiler instrumentation.  For
example, if the compiler implements a conditional in the source code with a
conditional move instruction, then a code-coverage tool will struggle to
determine whether both branches of the conditional were executed in a given
run of the program.  By leveraging LTO as it currently exists in LLVM, CSI
makes standard compiler analyses and optimizations available to tool
writers to optimize their tools.  As with any tool writer that uses
compiler instrumentation, tool writers that use CSI must determine what
optimizations tool users can safely perform on instrumented programs.

For some tool-specific optimizations, tool-writers can leverage the
properties passed to instrumentation hooks, which store the results of
commonly used compiler analysis.  For example, although a tool might simply
instrument every load or store, the same tool might benefit from ignoring
certain loads or stores.  If the property bit is available in CSI, that
tool could enjoy this optimization by implementing a load hook like this:

__csi_before_load(const csi_id_t load_id, const void *addr,
                  const int32_t num_bytes, const uint64_t prop) {
  if (prop & CSI_PROP_LOAD_READ_BEFORE_WRITE_IN_BB)
    return;
  process_load(addr, num_bytes);
}

Because prop is a compile-time constant, LTO is capable of inlining this
instrumentation and constant-folding prop to elide the instrumentation when
the condition is true.  This optimization is not available to tool writers
if the bit is not set in the property, of course.  Our plan is to add
information to these properties gradually based on general demand.

CSI does not provide as much flexibility as a custom LLVM pass, which can
perform arbitrary compiler analysis and optimization.  CSI trades off this
flexibility to dramatically simplify the task of writing many dynamic
analysis tools.  This is the 90-10 tradeoff that we opt into, and we feel
that making life easy for many would-be tool writers is worth the effort,
even if we can't quite cover everyone's needs.  Moreover, we see value
in
CSI as a framework for prototyping tools; once a tool writer has written a
correct tool, for instance, then she can decide whether the tool needs more
performance and can take on writing a custom LLVM pass.

>
>
> 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, 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.
>
>
> Is your intention to have a compiler flag that enables insertions of
> hooks, or are you planning on having a pass always add the hooks and having
> libLTO always remove them?  I assume the former, but you should probably
> clarify.
>
With CSI's current design, we've added a single compiler flag that
inserts
all of these hooks.  Although CSI can leverage LTO to remove unused
instrumentation, we don't rely on LTO for correctness.

>
>
>
>
> ===============>
> 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.
>
>
> Don't forget that atomic instructions (e.g., compare-and-swap) and some
of
> the intrinsics (e.g., llvm.memcpy()) also access memory.
>
Addressing these instructions is on our radar for future versions of CSI.

>
>
> 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.
>
>
> As an aside, I'm not sure that I buy the idea that tool developers
should
> be oblivious to the compiler internals.  If a tool developer doesn't
> understand what the compiler is doing, then she/he may not understand the
> results of the output.  For example, LLVM load/stores do not include stack
> spill slots, memory accesses incurred by calling conventions, etc.
> Depending on where the instrumentation passes are placed in the pass
> pipeline, instrumentation calls can be moved or removed (perhaps in
> undesirable ways for some dynamic analysis applications).
>
> I would also argue that a key design feature of LLVM is to make writing
> such passes simple, and I think LLVM accomplishes this.  If one understands
> how to build an efficient dynamic analysis, one can probably handle writing
> the compiler passes.
>
I personally think there's still a significant difference between
understanding what a compiler does conceptually (e.g., "What is a basic
block?") and being able to manipulate the codebase of a mainstream compiler
(e.g., "How does LLVM represent basic blocks, and how do I add instructions
to them?").  Although LLVM is certainly easier to work with than other
compiler codebases, CSI makes writing dynamic analysis tools even easier,
equivalent to writing a C library.  We've encountered several researchers
interested in writing dynamic analysis tools who are daunted by the task of
learning LLVM.

A common instrumentation infrastructure such as CSI has other benefits as
well.  Providing a single compiler hook to provide instrumentation for many
different tools reducers clutter in the compiler's codebase.  Furthermore,
tool-writers have an easier time distributing their tool if they don't have
to worry about getting users to use their custom compiler or to get their
changes upstreamed.

>
> Overall, I think having common instrumentation infrastructure is a good
> thing.  However, I'm not sure how common it can be across different
> applications of instrumentation.  As an example, most memory safety
> solutions have the same instrumentation and optimization needs (and
> constraints on optimization) regardless of how they implement the checks on
> loads and stores.  However, it's less clear to me that a race detector
and
> a memory safety compiler can safely use the same optimizations.  You may
> find yourself implementing a common infrastructure with each tool
> implementing specialized optimizations to make each type of dynamic
> analysis really fast.
>
> Food for thought,
>
> John Criswell
>
>
>
>
> _______________________________________________
> LLVM Developers mailing listllvm-dev at
lists.llvm.orghttp://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
> --
> John Criswell
> Assistant Professor
> Department of Computer Science, University of
Rochesterhttp://www.cs.rochester.edu/u/criswell
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160616/b61a1031/attachment.html>

On 6/16/2016 2:48 PM, Mehdi Amini via llvm-dev wrote:
>
>> On Jun 16, 2016, at 9:01 AM, TB Schardl via llvm-dev 
>> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>>
>> 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...
>
Suppose I want to build a production build, and one build for each of 
ASAN, MSAN, UBSAN, and TSAN.

With the current approach, I need to compile my source five different 
times, and link five different times.

With the CSI approach (assuming it was the backing technology behind the 
sanitizers), I need to compile twice (once for production, once for 
instrumentation), then LTO-link five times.  I can reuse my .o files 
across the sanitizer types.

It's possible that the math doesn't really work out in practice if the 
cost of the LTO-link dwarfs the compile times.

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160617/dc484003/attachment.html>

>
>
> I would also argue that a key design feature of LLVM is to make writing
> such passes simple, and I think LLVM accomplishes this.  If one understands
> how to build an efficient dynamic analysis, one can probably handle writing
> the compiler passes.
> John Criswell
>
I disagree here.
LLVM *is* the simplest-to-use compiler infrastructure I've used,
but not having to deal with a compiler guts for prototyping ideas is still
an order of magnitude simpler.
For most of the CSI use cases the users will not even need to understand
anything about compilers (except for the concept of basic blocks).

And we should not expect CSI to be as fast and as specializable as a custom
pass.
CSI's power is in the ability to attract more people to do quick-and-easy
experiments.

--kcc
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160617/46fcf669/attachment.html>

I think the CSI framework, or something like it, could be helpful for some
work I'm trying to do regarding dynamic memory analysis: given a C/C++
program in which certain l-value expressions are marked as
"interesting",
invoke my analysis callback every time that memory is written.

Of the options I've looked at for implementing this, it sounds like CSI
might be my best bet.  (Factors include license terms, performance of the
instrumented app, and how much time it would take me to create such a tool.)

- Christian


On Thu, Jun 16, 2016 at 12:01 PM, 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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160620/529d84d6/attachment.html>

Hi Christian,

While not yet merged into LLVM trunk, the CSI implementation is
available for download from our public GitHub organization. You're
welcome to download CSI and start trying it out now.

To clone CSI, execute these commands:

   git clone --recursive git at github.com:csi-llvm/llvm.git
   cd llvm/csi
   ./build.sh

This will clone and build the modified version of LLVM trunk that
contains the modifications to implement CSI.

In the 'llvm/csi' directory, you'll see several example tools in the
'toolkit' directory, and a sample program and Makefile in the
'example' directory to illustrate how a CSI-instrumented executable is
created.

We've so far only tested on Ubuntu 14.04 x64_64. Please let us know of
any feedback you may have!

Tyler

On Mon Jun 20 06:02:26 PDT 2016, Christian Convey via llvm-dev
<llvm-dev at lists.llvm.org> wrote:

 > I think the CSI framework, or something like it, could be helpful for 
some
 > work I'm trying to do regarding dynamic memory analysis: given a C/C++
 > program in which certain l-value expressions are marked as
"interesting",
 > invoke my analysis callback every time that memory is written.
 >
 > Of the options I've looked at for implementing this, it sounds like
CSI
 > might be my best bet.  (Factors include license terms, performance of the
 > instrumented app, and how much time it would take me to create such a 
tool.)
 >
 > - Christian