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

On Oct 16, 2015, at 1:27 PM, Joe Ranieri via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> I'm planning on attending. You've mentioned some of these, but
> specific topics of interest for me include:
> - Dealing with the explosion of basic blocks that come up with
> languages where almost every function call, implicit and explicit, can
> raise exceptions.
I saw this come up in a recent discussion about LLILC.  One simple way to do
this is to introduce a new intrinsic, like “llvm.nullcheck(x)” which
symbolically represents the null check and bail out in one instruction - instead
of the fully elaborated basic block representation (which slows everything down
by increasing the height of the CFG).  These null checks can be optimized away
through standard techniques, and any remaining ones expanded out to LLVM IR
before codegen, or as part of lowering to MachineInstrs.

-Chris

Chris Lattner via llvm-dev wrote:
 > I saw this come up in a recent discussion about LLILC.  One simple
 > way to do this is to introduce a new intrinsic, like
 > “llvm.nullcheck(x)” which symbolically represents the null check and
 > bail out in one instruction - instead of the fully elaborated basic
 > block representation (which slows everything down by increasing the
 > height of the CFG).

Is this compile time slowdown just a generic effect of the fact that a
lot of things in LLVM have O(f(# BBs)) complexity?  Or are there
specific things (like domtree construction) that suffer due to lots of
basic blocks?

 > These null checks can be optimized away through
 > standard techniques, and any remaining ones expanded out to LLVM IR
 > before codegen, or as part of lowering to MachineInstrs.

That won't be free, since keeping the control flow explicit does give
us better optimization in cases where we can sink work into the cold
throwing path, like these:

  *ptr = 42
  if (a == null) { throw(); unreachable; }
  *ptr = 43

==>

  if (a == null) {  *ptr = 42; throw(); unreachable; }
  *ptr = 43

And

  val = *ptr;
  if (a == null) { throw(some_arg = val); unreachable; }

==>

  if (a == null) { val = *ptr; throw(some_arg = val); unreachable; }

 >
 > -Chris
 > _______________________________________________
 > LLVM Developers mailing list
 > llvm-dev at lists.llvm.org
 > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

> On Oct 18, 2015, at 3:20 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> 
> 
> Chris Lattner via llvm-dev wrote:
> > I saw this come up in a recent discussion about LLILC.  One simple
> > way to do this is to introduce a new intrinsic, like
> > “llvm.nullcheck(x)” which symbolically represents the null check and
> > bail out in one instruction - instead of the fully elaborated basic
> > block representation (which slows everything down by increasing the
> > height of the CFG).
> 
> Is this compile time slowdown just a generic effect of the fact that a
> lot of things in LLVM have O(f(# BBs)) complexity?  
Yes.
> Or are there
> specific things (like domtree construction) that suffer due to lots of
> basic blocks?
Yes.  :-)

Some things work in time proportional to the depth of the CFG, and each null
check adds a level.
> 
> > These null checks can be optimized away through
> > standard techniques, and any remaining ones expanded out to LLVM IR
> > before codegen, or as part of lowering to MachineInstrs.
> 
> That won't be free, since keeping the control flow explicit does give
> us better optimization in cases where we can sink work into the cold
> throwing path, like these:
I don’t claim it to be optimal.  That said, we do sinking at the machine level
as well, so we will catch at least some of these cases.

-Chris