[llvm-dev] RFC: separating guards and implicit control flow

[Philip Reames via llvm-dev]

All,

TLDR: guards currently require reasoning about implicit control flow.  
LLVM struggles with implicit control flow within a basic block.  We 
should redesign guards to admit this rather than trying to boil the ocean.

As you may be aware, LLVM currently has experimental support for a 
construct called a "guard".  A guard is like a branch to a potential 
deoptimzation point, except that the guard is allowed to "spuriously" 
deoptimize even if the condition doesn't require it. This critical 
flexibility allows an earlier guard to be "widened" (i.e. made to fail 
more often) if doing so allows the elimination of a later guard or 
otherwise is useful to prune possible code paths.  At this point, the 
basic notion of a guard is fairly well proven with both critical 
transformations (LoopPredication, GurardWidening) available upstream, 
and multiple downstream speculative optimizations built on top.

As we've explored the design, we've stumbled on a implementation 
challenge.  Today, guards are modeled as call, not invokes.  As it turns 
out, LLVM is not terribly good at dealing with potential implicit exits 
within a basic block.  At this point, thanks to a fuzzer and a lot of 
work, we've worked through most of the correctness bugs with this 
representation, but the optimization problem remains.  Many of our 
optimization passes (e.g. SCEV, LICM, GVN to a degree, etc..) just give 
up when they encounter a potentially throwing call within a basic 
block.  Unfortunately, this limitation turns out to be a fairly 
fundamental one as efficient algorithms for such cases require being 
able to answer ordering questions about instructions which our current 
linked list implementation of a basic block makes prohibitively slow. 
(I'm skipping most of the details here; if you're curious ask and I'll 
expand.)

My proposal is to seriously evaluate whether we should stop trying to 
fix LLVM's problems with implicit control flow, and instead, model 
guards as explicit control flow since that's what all of our algorithms 
are tuned for.  That is, I'm going to continue to investigate efficient 
handling for implicit control in parallel, but I'd like to change the 
intrinsics just enough to allow experimentation with an alternate 
explicit control flow based form at the same time.

Doing so requires a small change to the LangRef - we currently state 
guards can't be invoked.  The most basic implementation patch is quite 
contained, but once we allow the form, we'll need to update many of the 
algorithms we've taught about implicit guards to consider a guard as a 
possible terminator.  This doesn't look had or ugly from the couple I've 
prototyped so far.

The advantage of this is that enumerating terminators within a CFG is a 
well understood and fast operation over LLVM IR.  This proposal does 
have the downside of loosing some optimizations that are block local or 
specific to single (explicit) exit loops, but I've come to believe 
that's a worthwhile tradeoff.  Also, teaching the optimizer to better 
optimize multiple exit loops is generally useful to a much large 
audience and useful for JITted languages, in particular, since not all 
of our control flow is represented by guards anyways.

Philip

p.s. It's worth noting that assumes have basically the same problem.  If 
this approach works, we may want to consider changing the representation 
of assumes as well.