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

On Thu, Jan 21, 2016 at 2:52 PM, Jonas Wagner <jonas.wagner at epfl.ch>
wrote:
> Hello,
>
> 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.
>
> How did you measure this? If it was measured by removing the checks before
> optimization happens, then what you may have been measuring is not the
> execution overhead of the branches (which is what would be eliminated by
> nop’ing them out) but the effect on the optimizer.
>
> Interesting. Indeed this was measured by removing some checks and then
> re-optimizing the program.
>
> I’m aware of some impact checks may have on optimization. For example,
> I’ve seen cases where much less inlining happens because functions with
> checks are larger. Do you know other concrete examples? This is definitely
> something I’ll have to be careful about. Philip Reames confirms this, too.
>
Off the top of my head:

- CFG is more complex
- regalloc is harder (although in theory it needn't do a worse job since
the branches are marked as unlikely; but not sure about in practice)
- the branch splits a BB which otherwise would have stayed together,
restricting e.g. the scheduler (which is BB-at-a-time last I heard)

-- Sean Silva

> On the other hand, we’ve also found that the benefit from removing a check
> is roughly proportional to the number of cycles spent executing that
> check’s instructions. Our model of this is not very precise, but it shows
> that the cost of executing the check’s instructions matters.
>
> I'll try to measure this, and will come back when I have data.
>
> Best,
> Jonas
> ​
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160121/8537e8c6/attachment.html>

----- Original Message -----
> From: "Sean Silva via llvm-dev" <llvm-dev at
lists.llvm.org>
> To: "Jonas Wagner" <jonas.wagner at epfl.ch>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Thursday, January 21, 2016 6:53:18 PM
> Subject: Re: [llvm-dev] Adding support for self-modifying branches to
> LLVM?
> On Thu, Jan 21, 2016 at 2:52 PM, Jonas Wagner < jonas.wagner at epfl.ch
> > wrote:
> > Hello,
> 
> > > > There is some data on this, e.g, in “High System-Code
Security
> > > > with
> > > > Low Overhead” . 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.
> > > 
> > 
> 
> > > How did you measure this? If it was measured by removing the
> > > checks
> > > before optimization happens, then what you may have been
> > > measuring
> > > is not the execution overhead of the branches (which is what
> > > would
> > > be eliminated by nop’ing them out) but the effect on the
> > > optimizer.
> > 
> 
> > Interesting. Indeed this was measured by removing some checks and
> > then re-optimizing the program.
> 
> > I’m aware of some impact checks may have on optimization. For
> > example, I’ve seen cases where much less inlining happens because
> > functions with checks are larger. Do you know other concrete
> > examples? This is definitely something I’ll have to be careful
> > about. Philip Reames confirms this, too.
> 
> Off the top of my head:
> - CFG is more complex
> - regalloc is harder (although in theory it needn't do a worse job
> since the branches are marked as unlikely; but not sure about in
> practice)
> - the branch splits a BB which otherwise would have stayed together,
> restricting e.g. the scheduler (which is BB-at-a-time last I heard)
Yes, the scheduling is per-BB (it is also interrupted by function calls). :( 

-Hal 
> -- Sean Silva
> > On the other hand, we’ve also found that the benefit from removing
> > a
> > check is roughly proportional to the number of cycles spent
> > executing that check’s instructions. Our model of this is not very
> > precise, but it shows that the cost of executing the check’s
> > instructions matters.
> 
> > I'll try to measure this, and will come back when I have data.
> 
> > Best,
> 
> > Jonas
> 
> > 
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160121/122aedbe/attachment.html>

On Thu, Jan 21, 2016 at 5:31 PM, Hal Finkel <hfinkel at anl.gov> wrote:
>
>
> ------------------------------
>
> *From: *"Sean Silva via llvm-dev" <llvm-dev at
lists.llvm.org>
> *To: *"Jonas Wagner" <jonas.wagner at epfl.ch>
> *Cc: *"llvm-dev" <llvm-dev at lists.llvm.org>
> *Sent: *Thursday, January 21, 2016 6:53:18 PM
> *Subject: *Re: [llvm-dev] Adding support for self-modifying branches to
> LLVM?
>
>
>
> On Thu, Jan 21, 2016 at 2:52 PM, Jonas Wagner <jonas.wagner at
epfl.ch>
> wrote:
>
>> Hello,
>>
>> 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.
>>
>> How did you measure this? If it was measured by removing the checks
>> before optimization happens, then what you may have been measuring is
not
>> the execution overhead of the branches (which is what would be
eliminated
>> by nop’ing them out) but the effect on the optimizer.
>>
>> Interesting. Indeed this was measured by removing some checks and then
>> re-optimizing the program.
>>
>> I’m aware of some impact checks may have on optimization. For example,
>> I’ve seen cases where much less inlining happens because functions with
>> checks are larger. Do you know other concrete examples? This is
definitely
>> something I’ll have to be careful about. Philip Reames confirms this,
too.
>>
> Off the top of my head:
>
> - CFG is more complex
> - regalloc is harder (although in theory it needn't do a worse job
since
> the branches are marked as unlikely; but not sure about in practice)
> - the branch splits a BB which otherwise would have stayed together,
> restricting e.g. the scheduler (which is BB-at-a-time last I heard)
>
>
> Yes, the scheduling is per-BB (it is also interrupted by function calls).
> :(
>
:(

-- Sean Silva

>
>
>  -Hal
>
> -- Sean Silva
>
>
>> On the other hand, we’ve also found that the benefit from removing a
>> check is roughly proportional to the number of cycles spent executing
that
>> check’s instructions. Our model of this is not very precise, but it
shows
>> that the cost of executing the check’s instructions matters.
>>
>> I'll try to measure this, and will come back when I have data.
>>
>> Best,
>> Jonas
>> ​
>>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160121/534fa973/attachment.html>