[LLVMdev] Is LLVM expressive enough to represent asynchronous exceptions?

[Andrew Trick]

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