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

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. Namely, you are no longer representing the actual
control flow of the program.

-bw

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.

On Jun 13, 2011, at 12:29 AM, John McCall wrote:
> 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.
Before we go through the horrible traffic in France, we should make sure that
Spain is actually there.

It is one thing to define an IR that can handle async exceptions, but it has to
be translated to machine code without phi nodes and atomic 512-bit stores.

It seems impractical to me to generate code that can correctly handle an async
exception after every (machine) instruction. Has anyone done this before?

Do they allow functions to use anything other than atomic, volatile variables?

Even that won't work:

  void *volatile p = 0;
  try {
    p = malloc(7);
  }
  finally {
    free(p);
  }

The try block would look something like:

  call _malloc
  movq %rax, p(%rpb)

If you take an exception between those two instructions, you are leaking memory.

/jakob

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.
> 
I realize that Italy isn't Spain, though I do want to see the Sistine Chapel
before I die (but since that would involve getting on a plane, it poses a bit of
a problem). Like Cameron, I'm referring to Chris's original proposal.

-bw

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