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

On Jun 13, 2011, at 12:29 AM, John McCall wrote:
> 
> On Jun 12, 2011, at 11:24 PM, Bill Wendling wrote:
> 
>> On Jun 12, 2011, at 4:40 PM, John McCall wrote:
>> 
>>> On Jun 12, 2011, at 2:14 PM, Cameron Zwarich wrote:
>>> 
>>>> On Jun 12, 2011, at 1:25 AM, Duncan Sands wrote:
>>>> 
>>>>> Hi Sohail,
>>>>> 
>>>>>> Is LLVM expressive enough to represent asynchronous
exceptions?
>>>>> 
>>>>> not currently.  The first step in this direction is to get
rid of the invoke
>>>>> instruction and attach exception handling information to
basic blocks.  See
>>>>>
http://nondot.org/sabre/LLVMNotes/ExceptionHandlingChanges.txt
>>>>> for a discussion.
>>>> 
>>>> Is this really a good idea? Why have a control flow graph if it
doesn't actually capture control flow? There are lots of compilers for
languages with more pervasive exceptions that represent them explicitly, e.g.
the Hotspot server compiler for Java or several ML compilers (where integer
overflow throws an exception).
>>> 
>>> You and Bill seem to be responding to a different question, namely
"Is LLVM expressive enough to represent synchronous exceptions from
non-call instructions?"  This really has nothing to do with Sohail's
question.  Duncan is quite correct:  the only reasonable representation for
asynchronous exceptions is to attach EH information to basic blocks.
>>> 
>> Placing the EH information on the basic block has the same implications
for the CFG for both questions.
> 
> Let me make an analogy.  We live in Germany.  Sohail wants to drive to
Spain.  Duncan told him to go through France.  You and Cameron are saying that
the traffic in France is awful, and some friends who went to Italy didn't go
through France.  I am trying to point out that Italy is not Spain, even though
they are both on the Mediterranean, and that you have to drive through France to
get to Spain.
> 
> There is really no alternative to putting EH edges on basic blocks if
you're going to support preemptive asynchronous exceptions — some random
multiply that gets hoisted out of a loop has to change exception handlers just
in case that's where the PC lands during a signal.  There isn't much
point in complaining that doing so muddies the CFG, which is really just an
inherent fact of handling asynchronous exceptions.  That is not true for
synchronous exceptions;  you don't have to abandon the "internally
throwing instructions are terminators" design at all, you just have to
allow more things to be terminators.
> 
> John.
No. Duncan suggested that he could hitch a ride with us through France. The
problem is, we're not driving to Spain at all and there doesn't appear
to be any place to transfer.

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.

-Andy

On Jun 13, 2011, at 2:23 PM, Andrew Trick wrote:
>> There is really no alternative to putting EH edges on basic blocks if
you're going to support preemptive asynchronous exceptions — some random
multiply that gets hoisted out of a loop has to change exception handlers just
in case that's where the PC lands during a signal.  There isn't much
point in complaining that doing so muddies the CFG, which is really just an
inherent fact of handling asynchronous exceptions. That is not true for
synchronous exceptions;  you don't have to abandon the "internally
throwing instructions are terminators" design at all, you just have to
allow more things to be terminators.
>> 
>> John.
> 
> No. Duncan suggested that he could hitch a ride with us through France. The
problem is, we're not driving to Spain at all and there doesn't appear
to be any place to transfer.
> 
> 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.
While a european vacation sounds nice, I don't think that support for asynch
exceptions is desirable in LLVM.  Synchronous exceptions like divide by zero or
null pointer derefs are another thing entirely though.

-Chris

On Jun 13, 2011, at 2:23 PM, Andrew Trick wrote:
> On Jun 13, 2011, at 12:29 AM, John McCall wrote:
>> 
>> On Jun 12, 2011, at 11:24 PM, Bill Wendling wrote:
>> 
>>> On Jun 12, 2011, at 4:40 PM, John McCall wrote:
>>> 
>>>> On Jun 12, 2011, at 2:14 PM, Cameron Zwarich wrote:
>>>> 
>>>>> On Jun 12, 2011, at 1:25 AM, Duncan Sands wrote:
>>>>> 
>>>>>> Hi Sohail,
>>>>>> 
>>>>>>> Is LLVM expressive enough to represent asynchronous
exceptions?
>>>>>> 
>>>>>> not currently.  The first step in this direction is to
get rid of the invoke
>>>>>> instruction and attach exception handling information
to basic blocks.  See
>>>>>>
http://nondot.org/sabre/LLVMNotes/ExceptionHandlingChanges.txt
>>>>>> for a discussion.
>>>>> 
>>>>> Is this really a good idea? Why have a control flow graph
if it doesn't actually capture control flow? There are lots of compilers for
languages with more pervasive exceptions that represent them explicitly, e.g.
the Hotspot server compiler for Java or several ML compilers (where integer
overflow throws an exception).
>>>> 
>>>> You and Bill seem to be responding to a different question,
namely "Is LLVM expressive enough to represent synchronous exceptions from
non-call instructions?"  This really has nothing to do with Sohail's
question.  Duncan is quite correct:  the only reasonable representation for
asynchronous exceptions is to attach EH information to basic blocks.
>>>> 
>>> Placing the EH information on the basic block has the same
implications for the CFG for both questions.
>> 
>> Let me make an analogy.  We live in Germany.  Sohail wants to drive to
Spain.  Duncan told him to go through France.  You and Cameron are saying that
the traffic in France is awful, and some friends who went to Italy didn't go
through France.  I am trying to point out that Italy is not Spain, even though
they are both on the Mediterranean, and that you have to drive through France to
get to Spain.
>> 
>> There is really no alternative to putting EH edges on basic blocks if
you're going to support preemptive asynchronous exceptions — some random
multiply that gets hoisted out of a loop has to change exception handlers just
in case that's where the PC lands during a signal.  There isn't much
point in complaining that doing so muddies the CFG, which is really just an
inherent fact of handling asynchronous exceptions.  That is not true for
synchronous exceptions;  you don't have to abandon the "internally
throwing instructions are terminators" design at all, you just have to
allow more things to be terminators.
> 
> No. Duncan suggested that he could hitch a ride with us through France. The
problem is, we're not driving to Spain at all and there doesn't appear
to be any place to transfer.
We have not yet reached a consensus to not go to Spain.  I would be fine with
that outcome, though.
> 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".  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.

John.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110613/5e949218/attachment.html>

On Jun 13, 2011, at 2:52 PM, Chris Lattner wrote:
> Synchronous exceptions like divide by zero or null pointer derefs are
another thing entirely though.
When runtimes support this, do they preserve all registers or just the
non-volatile registers, like a normal unwinder? How is information about the
exception passed to the landing pad?

/jakob

On Mon, Jun 13, 2011 at 2:56 PM, John McCall <rjmccall at apple.com>
wrote:
> On Jun 13, 2011, at 2:23 PM, Andrew Trick wrote:
>
> On Jun 13, 2011, at 12:29 AM, John McCall wrote:
>
> On Jun 12, 2011, at 11:24 PM, Bill Wendling wrote:
>
> On Jun 12, 2011, at 4:40 PM, John McCall wrote:
>
> On Jun 12, 2011, at 2:14 PM, Cameron Zwarich wrote:
>
> On Jun 12, 2011, at 1:25 AM, Duncan Sands wrote:
>
> Hi Sohail,
>
> Is LLVM expressive enough to represent asynchronous exceptions?
>
> not currently.  The first step in this direction is to get rid of the
invoke
>
> instruction and attach exception handling information to basic blocks.  See
>
> http://nondot.org/sabre/LLVMNotes/ExceptionHandlingChanges.txt
>
> for a discussion.
>
> Is this really a good idea? Why have a control flow graph if it doesn't
> actually capture control flow? There are lots of compilers for languages
> with more pervasive exceptions that represent them explicitly, e.g. the
> Hotspot server compiler for Java or several ML compilers (where integer
> overflow throws an exception).
>
> You and Bill seem to be responding to a different question, namely "Is
LLVM
> expressive enough to represent synchronous exceptions from non-call
> instructions?"  This really has nothing to do with Sohail's
question.
>  Duncan is quite correct:  the only reasonable representation for
> asynchronous exceptions is to attach EH information to basic blocks.
>
> Placing the EH information on the basic block has the same implications for
> the CFG for both questions.
>
> Let me make an analogy.  We live in Germany.  Sohail wants to drive to
> Spain.  Duncan told him to go through France.  You and Cameron are saying
> that the traffic in France is awful, and some friends who went to Italy
> didn't go through France.  I am trying to point out that Italy is not
Spain,
> even though they are both on the Mediterranean, and that you have to drive
> through France to get to Spain.
>
> There is really no alternative to putting EH edges on basic blocks if
you're
> going to support preemptive asynchronous exceptions — some random multiply
> that gets hoisted out of a loop has to change exception handlers just in
> case that's where the PC lands during a signal.  There isn't much
point in
> complaining that doing so muddies the CFG, which is really just an inherent
> fact of handling asynchronous exceptions.  That is not true for synchronous
> exceptions;  you don't have to abandon the "internally throwing
instructions
> are terminators" design at all, you just have to allow more things to
be
> terminators.
>
> No. Duncan suggested that he could hitch a ride with us through France. The
> problem is, we're not driving to Spain at all and there doesn't
appear to be
> any place to transfer.
>
> We have not yet reached a consensus to not go to Spain.  I would be fine
> with that outcome, though.
>
> 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".  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.
> John.
The thing I've never really quite understood with this whole
discussion of attaching an unwind edge to blocks is how this works
with SSA form... how do you write a PHI node that has multiple values
on a given edge?

-Eli

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

Hi Andrew,
> No. Duncan suggested that he could hitch a ride with us through France. The
problem is, we're not driving to Spain at all and there doesn't appear
to be any place to transfer.
>
> 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.
when Chris first came up with his proposal for attaching exception handling info
to basic blocks, I argued that it would be better to keep explicit control flow
by having lots of basic blocks.  This has costs.  First off, you get a lot of
control flow edges, which can cause some optimizers to take a long time.  This
could hopefully be dealt with by having such algorithms ignore/spend less time
on exception handling cfg edges.  Secondly, you use up more memory by allocating
a lot of basic blocks.  This could be mitigated by internally using
"lightweight
basic blocks" to represent all the little basic blocks that would have all
been
part of one big basic block if you weren't allowing trapping instructions. 
But
in the end I either became convinced that Chris was right or just gave up - I no
longer recall which :)

Ciao, Duncan.

Hi Chris,
> While a european vacation sounds nice, I don't think that support for
asynch exceptions is desirable in LLVM.  Synchronous exceptions like divide by
zero or null pointer derefs are another thing entirely though.
as I mentioned in a reply to another email in this thread, Ada does make use of
asynchronous exceptions.  However support for this does not have to be great: if
such an exception occurs then you are already fairly far into "nasal
demon"
territory as far as the Ada language is concerned, and I'm pretty sure that
as
far as Ada is concerned the optimizers can ignore this possibility.  The GCC Ada
front-end does not rely on traps for catching division by zero and such: it
inserts explicit checks (presumably because it is too hard to preserve correct
semantics otherwise, or perhaps GCC's trap support doesn't work
reliably).

Ciao, Duncan.

On Jun 14, 2011, at 1:07 AM, Duncan Sands wrote:
> Hi Andrew,
> 
>> No. Duncan suggested that he could hitch a ride with us through France.
The problem is, we're not driving to Spain at all and there doesn't
appear to be any place to transfer.
>> 
>> 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.
> 
> when Chris first came up with his proposal for attaching exception handling
info
> to basic blocks, I argued that it would be better to keep explicit control
flow
> by having lots of basic blocks.  This has costs.  First off, you get a lot
of
> control flow edges, which can cause some optimizers to take a long time. 
This
> could hopefully be dealt with by having such algorithms ignore/spend less
time
> on exception handling cfg edges.  Secondly, you use up more memory by
allocating
> a lot of basic blocks.  This could be mitigated by internally using
"lightweight
> basic blocks" to represent all the little basic blocks that would have
all been
> part of one big basic block if you weren't allowing trapping
instructions.
Compilation time issues in CodeGen are usually caused by large basic blocks or
"deep" CFGs. Passes are quadratic in both of these dimensions. The
number of edges in the CFG is irrelevant for a given CFG depth. In other words,
exception edges do not fundamentally increase the complexity of the CFG. I think
this will hold true for the mid-level optimizer too.

If we need to optimize the memory footprint of the IR, there is plenty of room
for improvement. To be concerned about this, I would need to see data on the
footprint of CFG edges relative to total memory.

If any optimizations are currently inhibited by adding exception edges, I think
it's an artificial limitation. Fixing the limitation will improve
optimization independent of exception handling. For example, a loop optimization
that only handles single-exit loops is simply incomplete regardless of whether
we support exceptions.

This isn't the first time I've heard the small block fallacy. I'll
try to give a quick data point. I suppressed basic block merging and hacked
SimplifyCFG to split blocks at all call sites. Then I looked at the impact on
403.gcc and lencod at -O3. This is all I had time for.

It looks like the aggressive block splitting did have a small impact on compile
time. Up to 10% for some passes. Much of the overhead is in isel, which
doesn't make sense to me. We should get a speedup, but we may be suffering
from extra DAG bloat for the copy nodes at block boundaries.

The regalloc slowdown is also counterintuitive to me. But the way GreedyRA works
today, I think the small blocks force it into a more exhaustive search for split
points. This could be managed.

I didn't notice a significant score change in either case, though that's
not really what I was interested in.

** lencod trunk (unmodified)

Program | GCCAS  Bytecode LLC compile LLC-BETA compile JIT codegen | GCC CBE LLC
LLC-BETA JIT | GCC/CBE GCC/LLC GCC/LLC-BETA LLC/LLC-BETA
lencod  | 6.9222 2335248  8.6951      *                *           | *   *   
7.2000 *        *   | n/a     n/a     n/a          n/a

  opt Total Execution Time: 6.9222 seconds (6.9200 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  ---
Name ---
   1.0654 ( 16.0%)   0.0024 (  0.9%)   1.0678 ( 15.4%)   1.0678 ( 15.4%)  Global
Value Numbering
   0.5236 (  7.9%)   0.0041 (  1.6%)   0.5277 (  7.6%)   0.5271 (  7.6%) 
Induction Variable Simplification
   0.5145 (  7.7%)   0.0020 (  0.8%)   0.5165 (  7.5%)   0.5166 (  7.5%) 
Combine redundant instructions

  llc Total Execution Time: 8.6951 seconds (8.6967 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  ---
Name ---
   2.7376 ( 33.2%)   0.2429 ( 55.4%)   2.9804 ( 34.3%)   2.9815 ( 34.3%)  X86
DAG->DAG Instruction Selection
   1.8160 ( 22.0%)   0.0093 (  2.1%)   1.8252 ( 21.0%)   1.8250 ( 21.0%)  Loop
Strength Reduction
   0.8806 ( 10.7%)   0.0653 ( 14.9%)   0.9459 ( 10.9%)   0.9461 ( 10.9%)  Greedy
Register Allocator

  1219 branchfolding    - Number of block tails merged
  1687 branchfolding    - Number of branches optimized
  1847 branchfolding    - Number of dead blocks removed

** lencod split blocks at calls

Program | GCCAS  Bytecode LLC compile LLC-BETA compile JIT codegen | GCC CBE LLC
LLC-BETA JIT | GCC/CBE GCC/LLC GCC/LLC-BETA LLC/LLC-BETA
lencod  | 7.3408 2392336  9.1578      *                *           | *   *   
7.2500 *        *   | n/a     n/a     n/a          n/a

  Total Execution Time: 7.3408 seconds (7.3399 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  ---
Name ---
   1.0714 ( 15.1%)   0.0044 (  1.7%)   1.0757 ( 14.7%)   1.0760 ( 14.7%)  Global
Value Numbering
   0.5184 (  7.3%)   0.0050 (  1.9%)   0.5233 (  7.1%)   0.5229 (  7.1%) 
Induction Variable Simplification
   0.5201 (  7.3%)   0.0027 (  1.0%)   0.5228 (  7.1%)   0.5226 (  7.1%) 
Combine redundant instructions

  Total Execution Time: 9.1578 seconds (9.4429 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  ---
Name ---
   2.9271 ( 33.8%)   0.3016 ( 60.6%)   3.2287 ( 35.3%)   3.2297 ( 34.2%)  X86
DAG->DAG Instruction Selection
   1.8756 ( 21.7%)   0.0101 (  2.0%)   1.8857 ( 20.6%)   1.8859 ( 20.0%)  Loop
Strength Reduction
   0.9343 ( 10.8%)   0.0651 ( 13.1%)   0.9993 ( 10.9%)   0.9996 ( 10.6%)  Greedy
Register Allocator

  1260 branchfolding    - Number of block tails merged
  1677 branchfolding    - Number of branches optimized
  5732 branchfolding    - Number of dead blocks removed

-Andy

-------------- next part --------------
A non-text attachment was scrubbed...
Name: splitblocks.diff
Type: application/octet-stream
Size: 1823 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110614/d9eb6b11/attachment.obj>