<div dir="ltr">Hey John,<div><br></div><div>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.</div><div><br></div><div>Cheers,</div><div>TB</div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jun 16, 2016 at 3:51 PM, John Criswell <span dir="ltr"><<a href="mailto:jtcriswel@gmail.com" target="_blank">jtcriswel@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>Dear TB,<br>
<br>
Comments inline below.<span class=""><br>
<br>
On 6/16/16 11:01 AM, TB Schardl via llvm-dev wrote:<br>
</span></div><span class="">
<blockquote type="cite">
<div dir="ltr"><span>
<p><span>Hey LLVM-dev,</span></p>
<p dir="ltr"><span><br>
</span></p>
<p dir="ltr"><span>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</span></p>
<p dir="ltr"><span>developing dynamic-analysis tools.</span></p>
</span></div>
</blockquote>
<br></span>
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.</div></blockquote><div><br></div><div>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.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000"><span class=""><br>
<br>
<blockquote type="cite">
<div dir="ltr"><span><br>
<p dir="ltr"><span>================</span></p>
<p dir="ltr"><span>Motivation</span></p>
<p dir="ltr"><span>================</span></p>
<br>
<p dir="ltr"><span>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.</span></p>
</span></div>
</blockquote>
<span></span><br>
<br>
<br>
<span></span>
<blockquote type="cite">
<div dir="ltr"><span>
<p dir="ltr"><span>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</span></p>
<p dir="ltr"><span>compiler instrumentation without needing to
understand the compiler internals or modifying the
compiler, which greatly lowers the bar for developing
dynamic-analysis tools.</span></p>
<br>
<p dir="ltr"><span>================</span></p>
<p dir="ltr"><span>Approach</span></p>
<p dir="ltr"><span>================</span></p>
<br>
<p dir="ltr"><span>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</span></p>
<p dir="ltr"><span>and then statically linking their compiled
library with the program-under-test.</span></p>
<br>
<p dir="ltr"><span>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</span></p>
<p dir="ltr"><span>instrumented program-under-test is run. </span></p>
</span></div>
</blockquote>
<br></span>
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.</div></blockquote><div><br></div><div>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.</div><div><br></div><div>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:</div><div><br></div><div><font face="monospace, monospace">__csi_before_load(const csi_id_t load_id, const void *addr,</font></div><div><font face="monospace, monospace"> const int32_t num_bytes, const uint64_t prop) {</font></div><div><font face="monospace, monospace"> if (prop & CSI_PROP_LOAD_READ_BEFORE_WRITE_IN_BB)</font></div><div><font face="monospace, monospace"> return;</font></div><div><font face="monospace, monospace"> process_load(addr, num_bytes);</font></div><div><font face="monospace, monospace">}</font></div><div><br></div><div>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.</div><div><br></div><div>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. </div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000"><span class=""><br>
<br>
<br>
<blockquote type="cite">
<div dir="ltr"><span>
<p dir="ltr"><span>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.</span></p>
</span></div>
</blockquote>
<br></span>
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.</div></blockquote><div><br></div><div>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.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000"><span class=""><br>
<br>
<br>
<blockquote type="cite">
<div dir="ltr"><span>
<br>
<p dir="ltr"><span>================</span></p>
<p dir="ltr"><span>CSI version 1</span></p>
<p dir="ltr"><span>================</span></p>
<br>
<p dir="ltr"><span>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. <br>
</span></p>
</span></div>
</blockquote>
<br></span>
Don't forget that atomic instructions (e.g., compare-and-swap) and
some of the intrinsics (e.g., llvm.memcpy()) also access memory.</div></blockquote><div><br></div><div>Addressing these instructions is on our radar for future versions of CSI.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000"><span class=""><br>
<br>
<blockquote type="cite">
<div dir="ltr"><span>
<p dir="ltr"><span> 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.</span></p>
<br>
<p dir="ltr"><span>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.</span></p>
<br>
<p dir="ltr"><span>================</span></p>
<p dir="ltr"><span>Future plan</span></p>
<p dir="ltr"><span>================</span></p>
<br>
<p dir="ltr"><span>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.</span></p>
</span></div>
</blockquote>
<br></span>
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).</div></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000">
<br>
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.<br></div></blockquote><div><br></div><div>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.</div><div><br></div><div>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.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000">
<br>
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.<br>
<br>
Food for thought,<br>
<br>
John Criswell<span class=""><br>
<br>
<blockquote type="cite">
<div dir="ltr"><span>
<div><span><br>
</span></div>
</span></div>
<br>
<fieldset></fieldset>
<br>
<pre>_______________________________________________
LLVM Developers mailing list
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
<p><br>
</p>
</span><span class=""><font color="#888888"><pre cols="72">--
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
<a href="http://www.cs.rochester.edu/u/criswell" target="_blank">http://www.cs.rochester.edu/u/criswell</a></pre>
</font></span></div>
</blockquote></div><br></div></div>