[llvm-dev] Managed Languages BOF @ Dev Meeting

[Sanjoy Das via llvm-dev]

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