llvm dev - Oct 2015 - Managed Languages BOF @ Dev Meeting

On 18 Oct 2015, at 23:08, Sanjoy Das <sanjoy at playingwithpointers.com>
wrote:
> 
> Supporting only basic block level granularity for "try ranges"
may not
> be sufficient for Java -- if a basic block has more than one null check
> in it then throwing the NullPtrException for the first null check (if
> it fails) is semantically different from throwing the NullPtrException
> for the second null check (the constructed exceptions will have
> different stack traces attached to them, for instance [1]).  
[ Footnote inlined ]
> [1]: there is a "hot exception" optimization that some JVMs can
do
>  that may allow us to get around this
> 
(http://jawspeak.com/2010/05/26/hotspot-caused-exceptions-to-lose-their-stack-traces-in-production-and-the-fix/),
>  but that's an _optimization_ that Java programmers should be able to
>  turn off.
There are some quite exciting security vulnerabilities associated with this
optimisation (it turns out that running a few instructions after a
security-critical check has failed is not always a good thing to do) so I agree
that it’s a good idea to avoid depending on it.

> So we'd
> have to do repeat the null checks in the unwind block, like
> 
>  superblock:  # unwinds to unwind_block
>    null_check(ptr_a)
>    do_something
>    null_check(ptr_b)
>    do_something_again
> 
>  unwind_block:
>    ;; either ptr_a is null or ptr_b is null
>    if (ptr_a == null)
>      throw_nullptrexception(bci = 42)
>    else ;; if (ptr_b == null)
>      throw_nullptrexception(bci = 43)
> 
> So the code explosion problem still exists (in unwind_block), and
> we've duplicated a bunch of code.
Does it?  I guess it depends on how you are implementing the exceptions.  I was
expecting that the non-call exceptions would be implemented on top of signals
(or something SEH-like on Windows), so the trap handler would have some generic
code to identify the faulting instruction, map this back to something useful,
and then throw the exception.  You wouldn’t be throwing the null pointer
exception from the unwind target, that would be generated in the signal handler
and the unwind target would only have to do the normal unwinding.

In a JIT environment, the unwind targets could probably also be lazily emitted,
so in your initial IR you’d just have a single patchpoint for the unwind target.
My knowledge of common Java idioms is slightly rusty, but my impression was
that, while lots of Java code abuses exceptions for non-exceptional behaviour,
this is quite rare for null-pointer exceptions.  Is there much (any?) real-world
code where the handling of null pointer exceptions is performance critical?
> Having said that, I'd love to take a look at the proposal that was
> made -- will it be easy for you to dig up a link?
It was this mailing list, but your ability to search it is probably as good as
mine.  My brain, unfortunately, does not contain a well indexed cross-reference
of the archive.  I believe that the general consensus was that something like
this would be good to have, but not sufficiently important to anyone with time
to spend actively hacking on stuff to do.  Given that people are now seriously
using LLVM for languages that are not so C-like, this might be different...

David

David Chisnall wrote:
 >> So we'd
 >> have to do repeat the null checks in the unwind block, like
 >>
 >>   superblock:  # unwinds to unwind_block
 >>     null_check(ptr_a)
 >>     do_something
 >>     null_check(ptr_b)
 >>     do_something_again
 >>
 >>   unwind_block:
 >>     ;; either ptr_a is null or ptr_b is null
 >>     if (ptr_a == null)
 >>       throw_nullptrexception(bci = 42)
 >>     else ;; if (ptr_b == null)
 >>       throw_nullptrexception(bci = 43)
 >>
 >> So the code explosion problem still exists (in unwind_block), and
 >> we've duplicated a bunch of code.
 >

 > Does it?  I guess it depends on how you are implementing the
 > exceptions.  I was expecting that the non-call exceptions would be
 > implemented on top of signals (or something SEH-like on Windows), so
 > the trap handler would have some generic code to identify the faulting
 > instruction, map this back to something useful, and then throw the
 > exception.  You wouldn’t be throwing the null pointer exception from
 > the unwind target, that would be generated in the signal handler and
 > the unwind target would only have to do the normal unwinding.

I see what you mean.  You'd keep some bookkeeping information on each
"faulting_load" instruction that specifies how the exception being
thrown has to be constructed.  So my example would look something like
this:

    superblock:  # unwinds to unwind_block
      faulting_load(ptr_a)  # exception_construction_args = (42)
      do_something
      faulting_load(ptr_b)  # exception_construction_args = (43)
      do_something_again

Did I understand the scheme correctly?

The interesting bit (I'm sure you've thought of this, I'm still
trying
to verify that I've understood the scheme correctly) here is that the
faulting_load instruction will not have the same reordering semantics
as a normal load.  You cannot reorder two `faulting_load` instructions
as that would change which NPE you get. E.g. if you were supposed to
get an NPE on bci 42, when loading ptr_a, in the above example, the
optimizer cannot change that to getting an NPE on bci 43, when loading
ptr_b. It therefore cannot re-order faulting_load(ptr_a) and
faulting_load(ptr_b) even though they're control equivalent, and even if
aliasing permits.

 > In a JIT environment, the unwind targets could probably also be
 > lazily emitted, so in your initial IR you’d just have a single
 > patchpoint for the unwind target.  My knowledge of common Java idioms
 > is slightly rusty, but my impression was that, while lots of Java code
 > abuses exceptions for non-exceptional behaviour, this is quite rare
 > for null-pointer exceptions.

Yes, that is accurate.  In fact, LLVM has an implementation of
page-fault based null check elimination [1] that we've been using for
a while.  However, this is not done by a new "faulting_load"
instruction; but is done by late matching "test Reg, Reg; jz throw"
and trying to "fold" the null check into a "nearby memory
operation".

There are two reasons why we chose this late matching approach:

  1. Keeping the control flow explicit lets most of the optimizer elide
     redundant null checks (without us teaching it about another new
     thing).

  2. It helps making the optimization profile guided and optional -- if
     you don't do anything then you still have an explicit null check
     (the "conservative" case, in this scenario) to fall back on, and
     not an implicit null check.

     Since taking a page fault is so much more expensive than a fully
     predicted explicit null check branch, getting this wrong even in a
     handful of cases can cause a net regression (because an occasional
     "catch NullPointerException" can heavily skew the scales).  So we
     have to rely on recompilation to avoid having a failing implicit
     null check in an application's steady state.  As soon as we detect
     that an implicit null check has failed, we kick off a recompile of
     the same method with information that tells LLVM that that
     specific null check must not be made implicit this time.

The problem with this scheme is that it does not address the basic
block explosion issue that started this discussion.

 > Is there much (any?) real-world code
 > where the handling of null pointer exceptions is performance critical?

I'd expect "evolution" to have taken care of most such code. :)

 > Given that people are now seriously using LLVM for
 > languages that are not so C-like, this might be different...

See [1]. :)

-- Sanjoy

[1]: http://llvm.org/docs/FaultMaps.html

On 19 Oct 2015, at 10:27, Sanjoy Das <sanjoy at playingwithpointers.com>
wrote:
> 
> 
> David Chisnall wrote:
> >> So we'd
> >> have to do repeat the null checks in the unwind block, like
> >>
> >>   superblock:  # unwinds to unwind_block
> >>     null_check(ptr_a)
> >>     do_something
> >>     null_check(ptr_b)
> >>     do_something_again
> >>
> >>   unwind_block:
> >>     ;; either ptr_a is null or ptr_b is null
> >>     if (ptr_a == null)
> >>       throw_nullptrexception(bci = 42)
> >>     else ;; if (ptr_b == null)
> >>       throw_nullptrexception(bci = 43)
> >>
> >> So the code explosion problem still exists (in unwind_block), and
> >> we've duplicated a bunch of code.
> >
> 
> > Does it?  I guess it depends on how you are implementing the
> > exceptions.  I was expecting that the non-call exceptions would be
> > implemented on top of signals (or something SEH-like on Windows), so
> > the trap handler would have some generic code to identify the faulting
> > instruction, map this back to something useful, and then throw the
> > exception.  You wouldn’t be throwing the null pointer exception from
> > the unwind target, that would be generated in the signal handler and
> > the unwind target would only have to do the normal unwinding.
> 
> I see what you mean.  You'd keep some bookkeeping information on each
> "faulting_load" instruction that specifies how the exception
being
> thrown has to be constructed.  So my example would look something like
> this:
> 
>   superblock:  # unwinds to unwind_block
>     faulting_load(ptr_a)  # exception_construction_args = (42)
>     do_something
>     faulting_load(ptr_b)  # exception_construction_args = (43)
>     do_something_again
> 
> Did I understand the scheme correctly?
Yes, in much the same way that we already emit data into the LSDA.  Whatever
catches the trap (signal handler, SEH handler) would receive the PC of the
faulting load, look up the relevant information, and then prepare the exception
object.
> The interesting bit (I'm sure you've thought of this, I'm still
trying
> to verify that I've understood the scheme correctly) here is that the
> faulting_load instruction will not have the same reordering semantics
> as a normal load.  You cannot reorder two `faulting_load` instructions
> as that would change which NPE you get. E.g. if you were supposed to
> get an NPE on bci 42, when loading ptr_a, in the above example, the
> optimizer cannot change that to getting an NPE on bci 43, when loading
> ptr_b. It therefore cannot re-order faulting_load(ptr_a) and
> faulting_load(ptr_b) even though they're control equivalent, and even
if
> aliasing permits.
Yes, that would probably be the trickiest part of this.  Note that this is also
somewhat language dependent.  If the source language does not define ordering of
memory operations, then reordering them would be fine.  I’m definitely not
sufficiently familiar with the Java spec to say exactly when this would or
wouldn’t be permitted - I think Java is a lot stricter than C/C++ with respect
to evaluation order.  We’d probably need some metadata on each basic block,
along with the unwind target, to specify what the requirements are. 
Alternatively, we could use the atomic load and store instructions with a new
ordering that would guarantee ordering within a single thread but not actually
guarantee atomicity.
> > In a JIT environment, the unwind targets could probably also be
> > lazily emitted, so in your initial IR you’d just have a single
> > patchpoint for the unwind target.  My knowledge of common Java idioms
> > is slightly rusty, but my impression was that, while lots of Java code
> > abuses exceptions for non-exceptional behaviour, this is quite rare
> > for null-pointer exceptions.
> 
> Yes, that is accurate.  In fact, LLVM has an implementation of
> page-fault based null check elimination [1] that we've been using for
> a while.  However, this is not done by a new "faulting_load"
> instruction; but is done by late matching "test Reg, Reg; jz
throw"
> and trying to "fold" the null check into a "nearby memory
operation".
> 
> There are two reasons why we chose this late matching approach:
> 
> 1. Keeping the control flow explicit lets most of the optimizer elide
>    redundant null checks (without us teaching it about another new
>    thing).
> 
> 2. It helps making the optimization profile guided and optional -- if
>    you don't do anything then you still have an explicit null check
>    (the "conservative" case, in this scenario) to fall back on,
and
>    not an implicit null check.
> 
>    Since taking a page fault is so much more expensive than a fully
>    predicted explicit null check branch, getting this wrong even in a
>    handful of cases can cause a net regression (because an occasional
>    "catch NullPointerException" can heavily skew the scales).  So
we
>    have to rely on recompilation to avoid having a failing implicit
>    null check in an application's steady state.  As soon as we detect
>    that an implicit null check has failed, we kick off a recompile of
>    the same method with information that tells LLVM that that
>    specific null check must not be made implicit this time.
> 
> The problem with this scheme is that it does not address the basic
> block explosion issue that started this discussion.
I can definitely see the attraction of keeping flow control explicit.  Note that
moving the unwind target to the basic block also simplifies flow control for
explicit (call) exceptions though - it’s not limited to non-call exceptions.  If
you have a language like Java with large try blocks, containing a number of
calls, all with the same jump target, then the IR will be a lot simpler for
cases where the catch block doesn’t touch any variables modified in the try
block (you’d still need to split the try block into basic blocks where it does).

The recompilation case would be similar in both cases, only this time you’d be
replacing an implicit null check with an explicit one, rather than removing some
metadata.

David

Am 19.10.2015 um 10:56 schrieb David Chisnall via llvm-dev:
> My knowledge of common Java idioms
> is slightly rusty, but my impression was that, while lots of Java
> code abuses exceptions for non-exceptional behaviour, this is quite
> rare for null-pointer exceptions.
Actually such abuse is heavily frowned upon. They use it only where 
unavoidable - i.e. when calling into the JDK's implementations of file 
I/O and JDBC.
They certainly don't expect the exceptional path to be fast; I have yet 
to see code where the hot path goes through a catch clause.

 > Is there much (any?) real-world
> code where the handling of null pointer exceptions is performance
> critical?
I doubt that NPEs are really used for that purpose. The catch block 
would never be sure that the NPE doesn't originate from a true null 
pointer dereference somewhere in the code.
If I must imagine a Java programmer who uses exceptions for control 
flow, they'd likely use some exception that they think cannot happen. If 
they are mildly compentent, they'll define their own exception class 
just to be on the safe side.

Of cousre, there are shoddy programmers who do that kind of thing, and 
worse. I don't think LLVM needs to worry about the speed of that kind of 
code though :-)