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. 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
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
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:
-----------------------
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;
}
foo$n(parameter-list)
{
leading-statements.
PushTheExceptionHandler(foo$x);
try-statements
PopTheExceptionHandler();
final-statements;
tail-statements;
}
foo$x(ExceptionInformation info)
{
// here the stack-pointer and frame-base-pointer
// should be the same as at the beginning of the
// try-block. Local variables from 'foo$n' are
// at the same offsets.
if (isExeception0) {
catch-0-statements;
}
.
else if (isExecptionN) {
catch-n-statements;
}
else {
unwind-to-next-handler();
}
final-statements;
tail-statements;
}
-------------------------
The rough idea is:
1) Make lists of the global & local variables modified in
'try-statements'
and accessed
in 'foo$x', per catch-?-statements. Those that are access in
'final-statements' and
'tail-statements' are added to a separate list.
2) Add memory-stores for each modified global & local variable in
'leading-statements',
which is also accessed in 'foo$x'
3) The local variables from the previous two points need slots in the
stack-frame of
foo$n, so that foo$x can access them if executed.
4) Flag all potentially excepting instructions (PEI). Note that a given
instruction
might match more that one catch block.
5) For each possible exception that an instruction may throw, trace backward
and find
the first occurrence of any value updated that is in either that
'catch-?-statements'
list or the list of the final-parts. This instruction should be marked
with an
additional 'serializing' flag, which indicates that it needs to be
stored
to memory
prior to the PEI in question and cannot be moved past it.
Then optimize the two methods as if they were otherwise independent.
Various optimizations would obviously be able to 'unflag' an op previous
marked PEI and the serialize flags would need adjustment.
The back-end compiler pass could attempt to 'merge' the two functions.
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.
On May 9, 2008, at 10:04 PM, Nick Lewycky 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. 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