[LLVMdev] How to handle divide-by-zero exception?

[Nick Lewycky]

Dan Gohman wrote:
> On May 8, 2008, at 9:35 PM, Nick Lewycky 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. :)

> 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