llvm dev - Jun 2011 - [LLVMdev] Is LLVM expressive enough to represent asynchronous exceptions?

On Jun 13, 2011, at 2:56 PM, John McCall wrote:
>> The point is, you're not going to be able to leverage most of a
CFG-based optimizing compiler if don't use the CFG to express control flow.
> 
> I don't understand the argument that "the CFG" has to be
defined by "certain uses by terminator instructions".
I'm not familiar with that argument. It's an implementation detail of
LLVM IR that unfortunately makes people fear using blocks to solve control flow
problems. We do need some way to connect control and data flow. Some values
determine control flow and other values are explicitly live-in or live-out on
CFG edges.
>  Unwind edges are inherently a different kind of edge because they proceed
from within the execution of an instruction.  Making the edge explicit on each
possibly-throwing instruction makes it easier to demonstrate that transforms
don't change exception behavior, in part by making it very awkward to write
any transforms on "invoking" instructions at all.  We don't care
right now because all throwing instructions are calls and therefore generally
optimization barriers, modulo inlining / partial inlining / specialization.  But
that's not true of loads and FP operations.
The CFG is well defined as a simple graph of blocks with optional terminator.
The point is, CFG analysis can completely traverse and reason about control flow
without knowledge of the operations within a block or even recognizing the
terminator. Terminators are simply things that need to be at the end of a block.
If you can't recognize it, don't remove it.

Optimizing across an exceptional control edge is not awkward at all because
dominance properties hold within an extended basic block. Most current LLVM
transforms can be easily adapted to operate on an EBB. You mainly need a
slightly smarter local instruction iterator. The same cannot be said about
teaching passes, and the people who write them, to understand implicit control
flow edges "within" blocks. I think that's similar in difficulty
to representing the entire function as a single instruction list with labels.
Sure, a control flow graph "exists" in your mind, but reasoning about
the correctness of a CFG analysis/transform is no longer simple.

-Andy

On Jun 13, 2011, at 3:43 PM, Andrew Trick wrote:
> Optimizing across an exceptional control edge is not awkward at all because
dominance properties hold within an extended basic block. Most current LLVM
transforms can be easily adapted to operate on an EBB. You mainly need a
slightly smarter local instruction iterator. The same cannot be said about
teaching passes, and the people who write them, to understand implicit control
flow edges "within" blocks.
...what on earth are you imagining is being proposed here?  Basic blocks remain
single-entry, and for the purposes of dominance they're single-exit in
exactly the same way that LLVM's current basic blocks are single-exit: 
there are at most two exit points, whose location does not depend on the
instructions in the "body" of the block.  Dominance is not
fundamentally changed.  In particular, the most important property by far —
transitivity of dominance through non-phis — still holds.

And yes, working with invoke instructions is annoying, in part because of the
possibility that the normal edge is critical, which is an invented problem
forced on us by the terminator representation.

John.

On Jun 13, 2011, at 4:33 PM, John McCall wrote:
> On Jun 13, 2011, at 3:43 PM, Andrew Trick wrote:
>> Optimizing across an exceptional control edge is not awkward at all
because dominance properties hold within an extended basic block. Most current
LLVM transforms can be easily adapted to operate on an EBB. You mainly need a
slightly smarter local instruction iterator. The same cannot be said about
teaching passes, and the people who write them, to understand implicit control
flow edges "within" blocks.
> 
> ...what on earth are you imagining is being proposed here?  Basic blocks
remain single-entry, and for the purposes of dominance they're single-exit
in exactly the same way that LLVM's current basic blocks are single-exit: 
there are at most two exit points, whose location does not depend on the
instructions in the "body" of the block.  Dominance is not
fundamentally changed.  In particular, the most important property by far —
transitivity of dominance through non-phis — still holds.
> 
> And yes, working with invoke instructions is annoying, in part because of
the possibility that the normal edge is critical, which is an invented problem
forced on us by the terminator representation.
I understand all of your arguments yet reach the opposite conclusion. In neither
solution does the dominance property supposed to change. It's just hard to
maintain correctly when trapping instructions don't terminate. Yes, handling
critical CFG edges is annoying--so don't do it.

Whatever needs to be done to handle explicit "trapping" control flow
already needs to be done to successfully optimize regular control flow. No
change in representation needed.

-Andy