llvm dev - Jan 2016 - Adding support for self-modifying branches to LLVM?

Thanks for the information. This has been very useful!

Patch points indeed *almost* do what I need. I will try to build a similar
solution.

Self-modifying code for truly zero-overhead (when not
enabled)
> instrumentation is a real thing (look at e.g. DTrace pid provider) but
> unless the number of instrumentation point is very large (100's of
> thousands? millions?) or not known beforehand (both are true for DTrace),
> the cost of a branch will be negligible.
>
In the use case that I have in mind, there are indeed a large number of
instrumentation points. To give a concrete example of what I'd like to
achieve, consider Clang's -fsanitize flag. These sanitizers add thousands
of little independent bits of code to the program, e.g., memory access
checks. Code that is very useful but also slows the program down. I'd like
to transform this code into zero-overhead instrumentation that I can enable
selectively.

AFAIK, the cost of a well-predicted, not-taken branch is the same as a
nop
> on every x86 made in the last many years.
>
I'm still not 100% sure whether the `nop <-> br` conversion is the
best
approach. I've considered some alternatives:
- Branches where the condition is a flag in memory. My early experiments
were too slow :(
- Conditional branches along with some other way to control the flags
register. I'm afraid of the side effects this might have.

For now, transforming an `llvm.experimental.patchpoint` into an
unconditional branch looks most promising. I just need to figure out how to
trick LLVM into laying out basic blocks the right way (and not eliminating
those that are unreachable due to not-yet-transformed branches).

Cheers,
Jonas
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160120/3e55ff9b/attachment.html>

On Wed, Jan 20, 2016 at 1:49 PM, Jonas Wagner <jonas.wagner at epfl.ch>
wrote:
> Thanks for the information. This has been very useful!
>
> Patch points indeed *almost* do what I need. I will try to build a similar
> solution.
>
> Self-modifying code for truly zero-overhead (when not enabled)
>> instrumentation is a real thing (look at e.g. DTrace pid provider) but
>> unless the number of instrumentation point is very large (100's of
>> thousands? millions?) or not known beforehand (both are true for
DTrace),
>> the cost of a branch will be negligible.
>>
>
> In the use case that I have in mind, there are indeed a large number of
> instrumentation points. To give a concrete example of what I'd like to
> achieve, consider Clang's -fsanitize flag. These sanitizers add
thousands
> of little independent bits of code to the program, e.g., memory access
> checks. Code that is very useful but also slows the program down. I'd
like
> to transform this code into zero-overhead instrumentation that I can enable
> selectively.
>
Your initial idea (compile with branches, then convert to nops) won't truly
be zero-overhead because that still requires having the instrumentation
present in the IR, which inhibits optimization. Actually, for UBSan I think
this is the primary mechanism by which it "slows code down".

Also, for sanitizers that use shadow, they really "want"
instrumentation to
be enabled "everywhere". E.g. for ASan if one part of the code is not
instrumented, it will fail to detect a bug that it otherwise would have
found (false negative). For MSan it is even worse because if any part of
the code is not instrumented, it will give a false positive.
For example, just compiling a single function with ASan/MSan
instrumentation isn't particularly useful, since that function probably
uses memory from another part of the program and without having that other
code instrumented the checks aren't particularly useful.

>
> AFAIK, the cost of a well-predicted, not-taken branch is the same as a nop
>> on every x86 made in the last many years.
>>
>
> I'm still not 100% sure whether the `nop <-> br` conversion is
the best
> approach. I've considered some alternatives:
> - Branches where the condition is a flag in memory. My early experiments
> were too slow :(
> - Conditional branches along with some other way to control the flags
> register. I'm afraid of the side effects this might have.
>
> For now, transforming an `llvm.experimental.patchpoint` into an
> unconditional branch looks most promising. I just need to figure out how to
> trick LLVM into laying out basic blocks the right way (and not eliminating
> those that are unreachable due to not-yet-transformed branches).
>
Using patchpoint et al. seems like a much better fit for your use case (as
I've understood it).

-- Sean Silva

>
> Cheers,
> Jonas
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160120/c9cf5dc4/attachment.html>

Hi,

Your initial idea (compile with branches, then convert to nops) won't
truly
> be zero-overhead because that still requires having the instrumentation
> present in the IR, which inhibits optimization. Actually, for UBSan I think
> this is the primary mechanism by which it "slows code down".
>
This is very interesting! Do you know of any studies that measure this kind
of effect?

Also, for sanitizers that use shadow, they really "want"
instrumentation to
> be enabled "everywhere".
>
There is some data on this, e.g, in "High System-Code Security with Low
Overhead" <http://dslab.epfl.ch/proj/asap/#publications>. In this
work we
found that, for ASan as well as other instrumentation tools, most overhead
comes from the checks. Especially for CPU-intensive applications, the cost
of maintaining shadow memory is small.

I'm happy to discuss this further. Also, if there are more suggestions on
how to best implement this, let me know!

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