I have a new plan for handling 'unwinds to' in the control flow graph and dominance. Just as a quick recap the problem I encountered is how to deal instructions in a block being used as operands in the unwind dest. Such as this: bb1: unwinds to %cleanup call void @foo() ; might throw, might not %x = add i32 %y, %z call void @foo() ; might throw, might not ret void cleanup: call void @use(i32 %x) The problem is that %x might not have been executed before we enter %cleanup. I won't reiterate what my previous plan was. The problem with it was that a lot of optimizations use the dominance tree to decide where it's safe to insert new instructions and it always assumes that if A dom B then an instruction in A is always accessible in B. Here's the new plan. Please poke holes in it. A. redefine the CFG a bit. i. pred_iterator stays the same. ii. succ_iterator only iterates over successors iii. outedge_iterator iterates over successors and the unwind dest There's still some code which refers to outedges by TerminatorInst + unsigned. I can't think of any reason not to replace all of them with outedge_iterator. B. redefine the dominator tree by modifying the GraphTraits i. A dom B means that all instructions in A are guaranteed to execute before any instructions in B. ii. the domtree may have multiple roots. Multiple roots occurs when the entry block 'unwinds to' another block. Domtree getRoot() should just return the root represented by the Function entry block, and if anyone needs it would could provide getAllRoots(). We would also need to add an "isReachable" method to domtree and replace all users who currently test for reachability by checking whether the block is dominated by the root. Before I start investing time implementing these changes, does anyone foresee any problems that I missed? Nick
Sorry -- Small change. Nick Lewycky wrote:> A. redefine the CFG a bit. > i. pred_iterator stays the same.pred_iterator becomes an inverse of outedge_iterator. That is, edges that lead to the execution of this block, regardless of whether it's an unwind-edge or not. Nick
Note that changing the definition of pred_iterator may have consequences for post-dom tree construction. You may need to split pred_iterator as you are splitting succ_iterator. --Owen On Mar 28, 2008, at 1:20 AM, Nick Lewycky wrote:> Sorry -- Small change. > > Nick Lewycky wrote: >> A. redefine the CFG a bit. >> i. pred_iterator stays the same. > > pred_iterator becomes an inverse of outedge_iterator. That is, edges > that lead to the execution of this block, regardless of whether it's > an > unwind-edge or not. > > Nick > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-------------- next part -------------- A non-text attachment was scrubbed... Name: smime.p7s Type: application/pkcs7-signature Size: 2555 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080328/b58515d5/attachment.bin>
Hi Nick,> Just as a quick recap the problem I encountered is how to deal > instructions in a block being used as operands in the unwind dest. Such > as this: > > bb1: unwinds to %cleanup > call void @foo() ; might throw, might not > %x = add i32 %y, %z > call void @foo() ; might throw, might not > ret void > cleanup: > call void @use(i32 %x) > > The problem is that %x might not have been executed before we enter > %cleanup.how about just declaring this illegal? i.e. require the first call to be in a different basic block to the second, making it possible to use a phi node in %cleanup. Ciao, Duncan.
Hi Nick, On Mar 28, 2008, at 02:15, Nick Lewycky wrote:> Before I start investing time implementing these changes, does > anyone foresee any problems that I missed?Stepping back from the nuts and bolts for a moment, could you precisely define what constitutes a predecessor in this model? What blocks would a phi node in %catch require for a case like this? define i8 @f(i1 %b) { entry: b label %try try: unwinds to %catch b i1 %b, label %then, label %else then: unwinds to %catch ret void else: unwinds to %catch ret void catch: ; What are my predecessors? ret void }> B. redefine the dominator tree by modifying the GraphTraits > i. A dom B means that all instructions in A are guaranteed to > execute before any instructions in B. > ii. the domtree may have multiple roots. > > Multiple roots occurs when the entry block 'unwinds to' another block.It seems highly problematical that static allocas might not dominate their uses. The entry block is already special in that it cannot be used as a branch target. Why not also forbid 'unwinds to' on the entry block? — Gordon -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080328/d701b75a/attachment.html>
On Mar 27, 2008, at 11:15 PM, Nick Lewycky wrote:> I have a new plan for handling 'unwinds to' in the control flow graph > and dominance. > > Just as a quick recap the problem I encountered is how to deal > instructions in a block being used as operands in the unwind dest. > Such > as this: > > bb1: unwinds to %cleanup > call void @foo() ; might throw, might not > %x = add i32 %y, %z > call void @foo() ; might throw, might not > ret void > cleanup: > call void @use(i32 %x) > > The problem is that %x might not have been executed before we enter > %cleanup.This means bb1 has multiple exit points, which defeats the "single entry, single exit" idea. Did I miss anything here ? - Devang
Duncan Sands wrote:> Hi Nick, > >> Just as a quick recap the problem I encountered is how to deal >> instructions in a block being used as operands in the unwind dest. Such >> as this: >> >> bb1: unwinds to %cleanup >> call void @foo() ; might throw, might not >> %x = add i32 %y, %z >> call void @foo() ; might throw, might not >> ret void >> cleanup: >> call void @use(i32 %x) >> >> The problem is that %x might not have been executed before we enter >> %cleanup. > > how about just declaring this illegal? i.e. require the first call > to be in a different basic block to the second, making it possible > to use a phi node in %cleanup.Because it's extremely difficult for an optimization pass to maintain that guarantee, it's expensive to scan through the instruction list sequentially, and it leads to additional basic blocks. I agree that the snippet should be illegal, but I don't think this is the way to do it. Nick
Gordon Henriksen wrote:> What blocks would a phi node in %catch require for a case like this? > > define i8 @f(i1 %b) { > > entry: > > b label %try > > try: unwinds to %catch > > b i1 %b, label %then, label %else > > then: unwinds to %catch > > ret void > > else: unwinds to %catch > > ret void > > catch: ; What are my predecessors? > > ret void > > }'catch' has 3 preds, %try, %then and %else.> >> B. redefine the dominator tree by modifying the GraphTraits >> i. A dom B means that all instructions in A are guaranteed to >> execute before any instructions in B. >> ii. the domtree may have multiple roots. >> >> Multiple roots occurs when the entry block 'unwinds to' another block. > > It seems highly problematical that static allocas might not dominate > their uses.I'm not sure what you mean by that. It would be invalid to "alloca" in a BB then use the pointer in the unwind dest. You can't escape that. The entry block is already special in that it cannot be used> as a branch target. Why not also forbid 'unwinds to' on the entry block?Yes, we could also do that. I'm all for hearing arguments for and opposed. Nick
Hi Devang,> > Just as a quick recap the problem I encountered is how to deal > > instructions in a block being used as operands in the unwind dest. > > Such > > as this: > > > > bb1: unwinds to %cleanup > > call void @foo() ; might throw, might not > > %x = add i32 %y, %z > > call void @foo() ; might throw, might not > > ret void > > cleanup: > > call void @use(i32 %x) > > > > The problem is that %x might not have been executed before we enter > > %cleanup. > > This means bb1 has multiple exit points, which defeats the "single > entry, single exit" idea. Did I miss anything here ?you are correct, this fundamental property of basic blocks is being discarded. Very nasty! This is why I argued against this approach in favour of the mini-basic-blocks approach, in which you have lots of basic blocks which under the hood share common info to reduce memory usage. However Chris convinced me that in fact not that many places really use that there is a single exit, and that only a wimpy quiche eater would shrink at the idea of auditing all of LLVM! :) Ciao, Duncan.