How to handle divide-by-zero exception?

Project Infrastructure LLVM Dev List Archives
#1

Currently it states in the language manual that the results of division by zero are undefined. However, I'm curious as to how you would normally handle either divide by zero or other "hardware" exceptions (null pointer dereference and so on) and turn them into LLVM exceptions.

It seems to me that you would need some way to set up the unwind labels beforehand, just like you do for the invoke instruction. For the specific case of divide by zero, I can imagine an optional unwind label parameter for the divide instruction, however that won't work too well for other kinds of exceptions since any load or store instruction could potentially produce them.

I would think that you would want some means to declare a trap handler (possibly via an intrinsic) that says "execute this function if a hardware exception occurs". The trap handler would be responsible for doing the appropriate unwind instruction or other cleanup. You could either define some standard constants representing different exception types, or have a different trap handler function for each known type (illegal address, divide by zero, etc.) This assumes of course that the lowered form of 'unwind' will be able to thread its way through a stack frame that was interrupted in the middle of an operation. If the trap occurred inside non-LLVM-generated code, for example, I imagine it might be difficult to get the frame address of the innermost enclosing LLVM-generated stack frame.

-- Talin

#2

Talin wrote:

Currently it states in the language manual that the results of division by zero are undefined. However, I'm curious as to how you would normally handle either divide by zero or other "hardware" exceptions (null pointer dereference and so on) and turn them into LLVM exceptions.

Ultimately, what we'd like to do is attach a bit to each instruction which specifies whether it may trap. If something happens (like an invalid pointer dereference or divide by zero), it would have to become an LLVM 'exception' if the bit is true, or else execute undefined behaviour. The goal being to allow language frontends that want to trap (like Java) to set the bit, and others (like C) can clear it on all instructions and never pay any performance penalty.

http://nondot.org/sabre/LLVMNotes/ExceptionHandlingChanges.txt

It seems to me that you would need some way to set up the unwind labels beforehand, just like you do for the invoke instruction. For the specific case of divide by zero, I can imagine an optional unwind label parameter for the divide instruction, however that won't work too well for other kinds of exceptions since any load or store instruction could potentially produce them.

The major problem is how you define "dominance" once you've modified the concept of a basic block to allow edges coming out the middle instead of the bottom. We've had an extensive thread on this in the past where the consensus was:

  * given a block A with an 'unwinds to' label to B:
   - A is a predecessor to B (B is a successor of A)
   - for the dominator tree, A and B are treated as if they shared the same predecessor.
  * we permit 'unwinds to' on the entry block, even though this means that there is no singular dominator root to the function. The domtree calculations already support this, though it means that you can't just add an AllocaInst to the entry block and the load/store it in any arbitrary block in the problem (if it were only reachable from the 'unwinds to' edge of the entry block).

There already exists a branch where this work is in progress, named "llvm-non-call-eh". I haven't been able to give it as much attention as it deserves, and would appreciate any help working on it.

Nick Lewycky

#3

Talin wrote:

Currently it states in the language manual that the results of division
by zero are undefined. However, I'm curious as to how you would normally
handle either divide by zero or other "hardware" exceptions (null
pointer dereference and so on) and turn them into LLVM exceptions.

Ultimately, what we'd like to do is attach a bit to each instruction
which specifies whether it may trap. If something happens (like an
invalid pointer dereference or divide by zero), it would have to become
an LLVM 'exception' if the bit is true, or else execute undefined
behaviour. The goal being to allow language frontends that want to trap
(like Java) to set the bit, and others (like C) can clear it on all
instructions and never pay any performance penalty.

http://nondot.org/sabre/LLVMNotes/ExceptionHandlingChanges.txt

It seems to me that you would need some way to set up the unwind labels
beforehand, just like you do for the invoke instruction. For the
specific case of divide by zero, I can imagine an optional unwind label
parameter for the divide instruction, however that won't work too well
for other kinds of exceptions since any load or store instruction could
potentially produce them.

The major problem is how you define "dominance" once you've modified the
concept of a basic block to allow edges coming out the middle instead of
the bottom. We've had an extensive thread on this in the past where the
consensus was:

* given a block A with an 'unwinds to' label to B:
  - A is a predecessor to B (B is a successor of A)
  - for the dominator tree, A and B are treated as if they shared the
same predecessor.
* we permit 'unwinds to' on the entry block, even though this means
that there is no singular dominator root to the function. The domtree
calculations already support this, though it means that you can't just
add an AllocaInst to the entry block and the load/store it in any
arbitrary block in the problem (if it were only reachable from the
'unwinds to' edge of the entry block).

I had attempted to read the relevant email threads and
perhaps I missed where the consensus was reached. Please
correct me if I missed some of the discussion.

Having a dom tree with multiple roots, where blocks may
not be dominated by the entry block is pretty scary. Having
"predecessor" mean different things in the context of the CFG
versus the context of the dom tree is very scary.

Say we have this CFG:

   A
   >
   B X
   >
   C

and B "unwinds to" X. Instead of having X be a successor to B,
how about making X a successor to A (and A a predecessor of X)?
A would need a special new kind of terminator instruction which
looks something like a conditional branch with B and X as
destinations, though it would always branch to B when executed.

Then, X would have to begin with a special instruction, maybe
an intrinsic call, which would be a magic place-holder in X for
all the side-effects that could potentially be produced by
(interrupted) execution of B.

I think this would preserve all the usual CFG and SSA
assumptions, and would produce the same dom tree that you're
proposing, but without the need for bending the definition
of "predecessor".

Would this be an acceptable approach? Or has this been
discussed already?

Dan

#4

Dan Gohman wrote:

Talin wrote:

Currently it states in the language manual that the results of division
by zero are undefined. However, I'm curious as to how you would normally
handle either divide by zero or other "hardware" exceptions (null
pointer dereference and so on) and turn them into LLVM exceptions.

Ultimately, what we'd like to do is attach a bit to each instruction
which specifies whether it may trap. If something happens (like an
invalid pointer dereference or divide by zero), it would have to become
an LLVM 'exception' if the bit is true, or else execute undefined
behaviour. The goal being to allow language frontends that want to trap
(like Java) to set the bit, and others (like C) can clear it on all
instructions and never pay any performance penalty.

http://nondot.org/sabre/LLVMNotes/ExceptionHandlingChanges.txt

It seems to me that you would need some way to set up the unwind labels
beforehand, just like you do for the invoke instruction. For the
specific case of divide by zero, I can imagine an optional unwind label
parameter for the divide instruction, however that won't work too well
for other kinds of exceptions since any load or store instruction could
potentially produce them.

The major problem is how you define "dominance" once you've modified the
concept of a basic block to allow edges coming out the middle instead of
the bottom. We've had an extensive thread on this in the past where the
consensus was:

* given a block A with an 'unwinds to' label to B:
  - A is a predecessor to B (B is a successor of A)
  - for the dominator tree, A and B are treated as if they shared the
same predecessor.
* we permit 'unwinds to' on the entry block, even though this means
that there is no singular dominator root to the function. The domtree
calculations already support this, though it means that you can't just
add an AllocaInst to the entry block and the load/store it in any
arbitrary block in the problem (if it were only reachable from the
'unwinds to' edge of the entry block).

I had attempted to read the relevant email threads and
perhaps I missed where the consensus was reached. Please
correct me if I missed some of the discussion.

My idea of "consensus" is when people stopped disagreeing, not that we actually agreed on anything. :slight_smile:

Having a dom tree with multiple roots, where blocks may
not be dominated by the entry block is pretty scary.

The dom tree code already supports it, because it already happens to postdominator trees. There are some clients that will need to be changed, but I think it's pretty minimal.

  Having

"predecessor" mean different things in the context of the CFG
versus the context of the dom tree is very scary.

Say we have this CFG:

   A
   >
   B X
   >
   C

and B "unwinds to" X. Instead of having X be a successor to B,
how about making X a successor to A (and A a predecessor of X)?
A would need a special new kind of terminator instruction which
looks something like a conditional branch with B and X as
destinations, though it would always branch to B when executed.

Sure. We could even call it "invoke".

The problem is that you end up with a CFG that looks like this:

      A
     / \
    B X

which doesn't represent what could happen at all. Any pass should be able to reasonably look at that CFG and say that instructions from B and X are exclusive. The reality is that instructions in X will occur after some of the instructions in B are executed.

It also has a slightly worse problem which is that the unwind destination for a block depends on which predecessor it came in from. Not nice at all.

Then, X would have to begin with a special instruction, maybe
an intrinsic call, which would be a magic place-holder in X for
all the side-effects that could potentially be produced by
(interrupted) execution of B.

I think this would preserve all the usual CFG and SSA
assumptions, and would produce the same dom tree that you're
proposing, but without the need for bending the definition
of "predecessor".

Would this be an acceptable approach? Or has this been
discussed already?

It would work, in the same sense that the other proposal would work. The trick is in trying to find a balance such that the resulting system is most intuitive and straightforward to implement. I don't think this is it.

Nick

#5

DISCLAIMER: I am SSA, LLVM and compiler ignorant, so take the following for
what it is worth.

What about logically breaking a (complex) SEH method into two logical
methods, as per this pseudo-code as an example:

#6

Hi,

What about logically breaking a (complex) SEH method into two logical
methods, as per this pseudo-code as an example:

-----------------------

foo(parameter-list)
{
  leading-statements;

  try {
    try-statements;
  }
  catch(Execption0 ex0) {
    catch-0-statements;
  }
  .
  catch(ExceptionN exN) {
    catch-n-statements;
  }
  finally {
    final-statemements
  }

  tail-statements;
}

LLVM is completely "flat" - it has no local blocks at all.
So a big part of exception handling is flattening this kind
of code when outputting LLVM IR (which seems to be more or
less what you are suggesting). This is done by llvm-g++ for
example. Try compiling some C++ code with try-catch-finally
blocks with llvm-g++ with -S -emit-llvm -o - to see what I
mean. Inevitably flattening occurs before LLVM even sees
the code, since there is no direct way of representing nested
blocks in LLVM.

Ciao,

Duncan.

#7

See Java and Ada in gcc for an example of how this is done. Essentially, you install a trap handler on the OS for the traps your interested in and have them create an exception. The inline code is `normal', no special funniness to it, other than exception tables and unwind tables that explain what to do. This scheme can even be made to work for asynchronous events as well.

#8

LLVM is completely "flat" - it has no local blocks at all.
So a big part of exception handling is flattening this kind
of code when outputting LLVM IR (which seems to be more or
less what you are suggesting). This is done by llvm-g++ for example.
Try compiling some C++ code with try-catch-finally blocks with llvm-g++

with -S

-emit-llvm -o - to see what I mean. Inevitably flattening occurs before

LLVM

even sees the code, since there is no direct way of representing nested

blocks in LLVM.

I was pretty much only thinking about hardware exceptions and traps which
can be
implictly triggered via a (normally) non-termintating instruction.

#9

Dan Gohman wrote:

Having a dom tree with multiple roots, where blocks may
not be dominated by the entry block is pretty scary.

The dom tree code already supports it, because it already happens to
postdominator trees. There are some clients that will need to be
changed, but I think it's pretty minimal.

Please reconsider prohibiting the entry block from having an
"unwinds to". Beyond dom tree clients, there's also the widely
useful idiom of allocas in the entry block that this would
break.

I just hunted through the archives and confirmed my memory
of seeing this concern raised but never addressed. If I
missed a reason why entry needs to have "unwinds to", please
point it out again.

Also, in that case, please also explain what will happen here:

entry: unwinds to %handler
   call void @foo()
   br label %exit
handler:
   br label %exit
exit:
   ret void

Where does %exit stand in dom tree land?

Having

"predecessor" mean different things in the context of the CFG
versus the context of the dom tree is very scary.

Say we have this CFG:

  A
  >
  B X
  >
  C

and B "unwinds to" X. Instead of having X be a successor to B,
how about making X a successor to A (and A a predecessor of X)?
A would need a special new kind of terminator instruction which
looks something like a conditional branch with B and X as
destinations, though it would always branch to B when executed.

Sure. We could even call it "invoke".

The problem is that you end up with a CFG that looks like this:

     A
    / \
   B X

which doesn't represent what could happen at all. Any pass should be
able to reasonably look at that CFG and say that instructions from B and
X are exclusive. The reality is that instructions in X will occur after
some of the instructions in B are executed.

I maintain that it does represent what happens, with a little
abstraction :-). Control will flow to B in the case that B doesn't
end up interrupted by an exception, and to X in the case that
it does. It's not a coincidence that this is the CFG that results
from reverse-engineering a CFG from the dom tree that you're
proposing to use.

Unfortunately, after thinking this through a little more I
found a problem with the magic side-effects intrinsic. As a
call it can easily appear to have lots of side-effects, but it
won't easily be able to appear to access alloca or malloc
memory in the function that doesn't escape.

There were some other minor issues with my proposal which I
believe can be reasonably fixed, but this issue with the
side-effects intrinsic is a fundamental problem :-/.

Dan

#10

Dan Gohman wrote:

Dan Gohman wrote:

Having a dom tree with multiple roots, where blocks may
not be dominated by the entry block is pretty scary.

The dom tree code already supports it, because it already happens to
postdominator trees. There are some clients that will need to be
changed, but I think it's pretty minimal.

Please reconsider prohibiting the entry block from having an
"unwinds to". Beyond dom tree clients, there's also the widely
useful idiom of allocas in the entry block that this would
break.

*shrug* I'm not married to the idea. It just hasn't hit me that it's necessary.

Put another way, if I actually encounter passes doing things like inserting alloca's in the first block and this is harder to fix than disallowing 'unwinds to' on the entry BB would be, I'll disallow 'unwinds to' on the entry BB.

I just hunted through the archives and confirmed my memory
of seeing this concern raised but never addressed. If I
missed a reason why entry needs to have "unwinds to", please
point it out again.

Also, in that case, please also explain what will happen here:

entry: unwinds to %handler
   call void @foo()
   br label %exit
handler:
   br label %exit
exit:
   ret void

Where does %exit stand in dom tree land?

Yup, it's exactly where you think:

   > > >
entry handler exit

Having

"predecessor" mean different things in the context of the CFG
versus the context of the dom tree is very scary.

Say we have this CFG:

  A
  >
  B X
  >
  C

and B "unwinds to" X. Instead of having X be a successor to B,
how about making X a successor to A (and A a predecessor of X)?
A would need a special new kind of terminator instruction which
looks something like a conditional branch with B and X as
destinations, though it would always branch to B when executed.

Sure. We could even call it "invoke".

The problem is that you end up with a CFG that looks like this:

     A
    / \
   B X

which doesn't represent what could happen at all. Any pass should be
able to reasonably look at that CFG and say that instructions from B and
X are exclusive. The reality is that instructions in X will occur after
some of the instructions in B are executed.

I maintain that it does represent what happens, with a little
abstraction :-). Control will flow to B in the case that B doesn't
end up interrupted by an exception, and to X in the case that
it does. It's not a coincidence that this is the CFG that results
from reverse-engineering a CFG from the dom tree that you're
proposing to use.

That drops the fact that some instructions from B may execute before X.

In practise, what users want out of the domtree is to know the nearest block they can put an instruction that is guaranteed to be executed before entering this/these other blocks. That's how I justify my change to the domtree -- it doesn't really apply to the CFG though.

Unfortunately, after thinking this through a little more I
found a problem with the magic side-effects intrinsic. As a
call it can easily appear to have lots of side-effects, but it
won't easily be able to appear to access alloca or malloc
memory in the function that doesn't escape.

There were some other minor issues with my proposal which I
believe can be reasonably fixed, but this issue with the
side-effects intrinsic is a fundamental problem :-/.

Right. Calling an intrinsic that might have arbitrary side-effects (modify arbitrary memory) would also break mem2reg in all cases.

The simpler method of avoiding an intrinsic and just having a "br label %foo, onunwind %unwind" instruction is still up for grabs, but I still think it's bad for reasons up 2 frames in this thread.

Nick