Gordon Henriksen wrote:> On 2008-03-29, at 00:57, Nick Lewycky wrote: > >> 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. > > Would it be more natural to claim %entry and %try as the predecessors? > This is similar to how a high level language disallows variable > declarations from a try block to be visible from the catch.In LLVM the rule is that an instruction must be dominated by its operands. Predecessors and successors don't enter into it, except to define the dominance tree.> object x; > try { x = null; } > catch { use(x); } // error, x is uninitialized >Yes, I know. I'm planning to accomplish this by defining pred/succ sensibly such that we get a domtree where the equivalent LLVM code would be invalid.> Also, consider a phi node: > > phi i32 [%x, %bb1] ; %x defined in %bb1. > > Depending on what type of predecessor %bb1 is, some of the models > you've mentioned declare this phi node illegal.Oh. Now that's a very good point. bb1: unwinds to %cleanup %x = add i32 @foo, @bar ret i32 %x cleanup: %y = phi i32 [%x, bb1] If %cleanup has %bb1 as a predecessor then the above is legal. (PHI nodes being the only Instruction that works on pred/succ and not dominators.) And you're right, the fix for that it to make the predecessor be bb1's preds (if it has any). This is nastier than I was expecting... Nick
Hi Gordon, I've been thinking about this problem a bit. Nick Lewycky wrote:> Gordon Henriksen wrote: >> Also, consider a phi node: >> >> phi i32 [%x, %bb1] ; %x defined in %bb1. >> >> Depending on what type of predecessor %bb1 is, some of the models >> you've mentioned declare this phi node illegal. > > Oh. Now that's a very good point. > > bb1: unwinds to %cleanup > %x = add i32 @foo, @bar > ret i32 %x > cleanup: > %y = phi i32 [%x, bb1] > > If %cleanup has %bb1 as a predecessor then the above is legal. (PHI > nodes being the only Instruction that works on pred/succ and not > dominators.)We already have this issue with invoke. Consider: bb1: %x = invoke i32 @f() to label %normal unwind label %unwind normal: phi i32 [%x, %bb1] ret i32 %x unwind: phi i32 [%x, %bb1] ; illegal ret i32 %x The PHI in %unwind must mention %bb1, but may not refer to %x. In the code sample I pasted before (bb1: unwinds to %cleanup) it would mean that the PHI node in %cleanup must reference %bb1 but may not contain any instructions inside of %bb1. Yes this rule will require fixing up some optimizations, but I'm prepared to do that. This only applies to PHI nodes so it'll be fast to check for. The usual dominance test will take care of the case where %unwind branches out to other blocks that try to use %x. Any other issues I should keep in mind? Nick
> In LLVM the rule is that an instruction must be dominated by its > operands....> We already have this issue with invoke. Consider: > > bb1: > %x = invoke i32 @f() to label %normal unwind label %unwind > normal: > phi i32 [%x, %bb1] > ret i32 %x > unwind: > phi i32 [%x, %bb1] ; illegal > ret i32 %x > > The PHI in %unwind must mention %bb1, but may not refer to %x.In some sense this PHI is not dominated by its operands. There is an edge to %unwind coming out of the invoke, but it is coming out of the RHS, i.e. before the assignment to %x. If I wrote the invoke as: invoke i32 @f() <= this may branch to %unwind place the result in %x then it is clear that the phi is dominated by the call part of the invoke but not the result copying part. Likewise for something like bb1: unwinds to %cleanup %x = udiv i32 @foo, @bar <= The udiv is always executed before %cleanup, but not the assignment to %x ret i32 %x cleanup: %y = phi i32 [%x, bb1] So maybe it is helpful to think of instructions as corresponding to a LHS and a RHS node in the cfg, with an edge from RHS to LHS, and with exceptional edges coming out of the RHS node. Ciao, Duncan.
On Thu, 3 Apr 2008, Duncan Sands wrote:>> bb1: >> %x = invoke i32 @f() to label %normal unwind label %unwind >> normal: >> phi i32 [%x, %bb1] >> ret i32 %x >> unwind: >> phi i32 [%x, %bb1] ; illegal >> ret i32 %x >> >> The PHI in %unwind must mention %bb1, but may not refer to %x. > > In some sense this PHI is not dominated by its operands. There > is an edge to %unwind coming out of the invoke, but it is coming > out of the RHS, i.e. before the assignment to %x. If I wrote > the invoke as:On IRC, I suggested that Nicholas consider making the unwind block not be dominated by *any* instruction in the unwinding block. This gets us out of weird partial dominance cases and makes the CFG checks simpler. For example, this would be illegal: foo: unwinds to bar: %a = add ... call ... ... bar: use %a Because foo doesn't dominate bar at all. In practice, unwind blocks (at least in C++) almost never refer to computation in the unwinding block, so I think that this is just fine in pratice. For cases where a reference does exist, it is sufficient to split the block: foo: %a = add .. br foo2 foo2: unwinds to bar call ... bar: use %a This means that simplifycfg would need to know that it can't merge foo/foo2, etc. I think this would significantly simplify the dominance issues with this approach. Maybe even the quiche eaters will be able to handle it! ;-) What do you think? -Chris -- http://nondot.org/sabre/ http://llvm.org/