On Nov 28, 2010, at 2:20 AM, Bill Wendling wrote:> On Nov 27, 2010, at 4:57 PM, John McCall wrote: > >> On Nov 25, 2010, at 3:03 AM, Duncan Sands wrote: >>> I'm pointing out that if the invoke instruction >>> is removed and catch information is attached to entire basic blocks, then if no >>> care is taken then it is perfectly possible to use %x before it is defined as >>> explained in my previous email, blowing up the entire LLVM system. Clearly the >>> solution is to not allow this by not allowing values defined in a basic block >>> to be used in a handler for that block; >> >> If we take this route — and I think we should, although I'd like to see region >> chaining in first — I see two reasonable solutions. The first is what you've >> said, that effectively there's an edge from the beginning of the block; the >> second is a slight twist, that the edge leaves from the end of the phis. I >> think the latter will greatly simplify every transformation which ever inserts >> a phi, and in particular mem2reg. Since phis can't throw, it should be >> equivalent anyway. > > Wouldn't this route make otherwise value programs invalid? For instance: > > entry: > %x = alloca i32 > br label try > > try: unwinds to %landing.pad > %x1 = add i32 37, 927 > call @foo() > br label %normal.edge > > landing.pad: landingpad > ; Code that prints the value of %x1 > > We expect the value printed to be 964, but if we don't allow %x1 to be accessible then we get garbage or an assert...What do you mean by "otherwise valid"? Just that we can prove that %x1 has been computed by the time a throw can occur? We really want SSA well-formedness to be a simple structural condition; having to examine instruction-specific semantics to compute dominance would make it absurdly expensive to compute and keep valid. For example, if any instruction were valid to reference up to the first throwing instruction, then re-ordering the loads in the following code would break SSA: bb: unwinds to %lp %x1 = throwing load i32* %v1 %x2 = throwing load i32* %v2 ... lp: call void @print_int(i32 %x1) Put another way, this would change SSA well-formedness from a local problem to a global one. Of course, this will be a very challenging change regardless of dominance criteria because of the imprecision of edges. For example, we would not be able to mem2reg %v in the following example without splitting %bb: define void @foo() entry: %v = alloca i32 br label %bb bb: unwinds to %lp store i32 0, i32* %v call void @bar() store i32 1, i32* %v call void @bar() ret void lp: %x = load i32* %v ... That's inherent in the design, unfortunately. John.
On Nov 28, 2010, at 2:59 AM, John McCall wrote:> On Nov 28, 2010, at 2:20 AM, Bill Wendling wrote: > >> On Nov 27, 2010, at 4:57 PM, John McCall wrote: >> >>> On Nov 25, 2010, at 3:03 AM, Duncan Sands wrote: >>>> I'm pointing out that if the invoke instruction >>>> is removed and catch information is attached to entire basic blocks, then if no >>>> care is taken then it is perfectly possible to use %x before it is defined as >>>> explained in my previous email, blowing up the entire LLVM system. Clearly the >>>> solution is to not allow this by not allowing values defined in a basic block >>>> to be used in a handler for that block; >>> >>> If we take this route — and I think we should, although I'd like to see region >>> chaining in first — I see two reasonable solutions. The first is what you've >>> said, that effectively there's an edge from the beginning of the block; the >>> second is a slight twist, that the edge leaves from the end of the phis. I >>> think the latter will greatly simplify every transformation which ever inserts >>> a phi, and in particular mem2reg. Since phis can't throw, it should be >>> equivalent anyway. >> >> Wouldn't this route make otherwise value programs invalid? For instance: >> >> entry: >> %x = alloca i32 >> br label try >> >> try: unwinds to %landing.pad >> %x1 = add i32 37, 927 >> call @foo() >> br label %normal.edge >> >> landing.pad: landingpad >> ; Code that prints the value of %x1 >> >> We expect the value printed to be 964, but if we don't allow %x1 to be accessible then we get garbage or an assert... > > What do you mean by "otherwise valid"??? Uh...in the current EH implementation, if foo() throws, then %x1 would have 964 as the value, even in "landing.pad". And the value could be printed out with no problems. In other words, this is completely valid code with proper semantics: #include <iostream> extern void foo(); int main() { int x = 0; try { x = 37 + 927; foo(); } catch (...) { std::cout << x << '\n'; } } Any solution that violates this isn't a solution. -bw> Just that we can prove that %x1 has been computed by the time a throw can occur? We really want SSA well-formedness to be a simple structural condition; having to examine instruction-specific semantics to compute dominance would make it absurdly expensive to compute and keep valid. For example, if any instruction were valid to reference up to the first throwing instruction, then re-ordering the loads in the following code would break SSA: > > bb: unwinds to %lp > %x1 = throwing load i32* %v1 > %x2 = throwing load i32* %v2 > ... > lp: > call void @print_int(i32 %x1) > > Put another way, this would change SSA well-formedness from a local problem to a global one. > > Of course, this will be a very challenging change regardless of dominance criteria because of the imprecision of edges. For example, we would not be able to mem2reg %v in the following example without splitting %bb: > > define void @foo() > entry: > %v = alloca i32 > br label %bb > bb: unwinds to %lp > store i32 0, i32* %v > call void @bar() > store i32 1, i32* %v > call void @bar() > ret void > lp: > %x = load i32* %v > ... > > That's inherent in the design, unfortunately. > > John.
On Nov 28, 2010, at 1:57 PM, Bill Wendling wrote:> On Nov 28, 2010, at 2:59 AM, John McCall wrote: > >> On Nov 28, 2010, at 2:20 AM, Bill Wendling wrote: >> >>> On Nov 27, 2010, at 4:57 PM, John McCall wrote: >>> >>>> On Nov 25, 2010, at 3:03 AM, Duncan Sands wrote: >>>>> I'm pointing out that if the invoke instruction >>>>> is removed and catch information is attached to entire basic blocks, then if no >>>>> care is taken then it is perfectly possible to use %x before it is defined as >>>>> explained in my previous email, blowing up the entire LLVM system. Clearly the >>>>> solution is to not allow this by not allowing values defined in a basic block >>>>> to be used in a handler for that block; >>>> >>>> If we take this route — and I think we should, although I'd like to see region >>>> chaining in first — I see two reasonable solutions. The first is what you've >>>> said, that effectively there's an edge from the beginning of the block; the >>>> second is a slight twist, that the edge leaves from the end of the phis. I >>>> think the latter will greatly simplify every transformation which ever inserts >>>> a phi, and in particular mem2reg. Since phis can't throw, it should be >>>> equivalent anyway. >>> >>> Wouldn't this route make otherwise value programs invalid? For instance: >>> >>> entry: >>> %x = alloca i32 >>> br label try >>> >>> try: unwinds to %landing.pad >>> %x1 = add i32 37, 927 >>> call @foo() >>> br label %normal.edge >>> >>> landing.pad: landingpad >>> ; Code that prints the value of %x1 >>> >>> We expect the value printed to be 964, but if we don't allow %x1 to be accessible then we get garbage or an assert... >> >> What do you mean by "otherwise valid"? > > ?? Uh...in the current EH implementation, if foo() throws, then %x1 would have 964 as the value, even in "landing.pad". And the value could be printed out with no problems. In other words, this is completely valid code with proper semantics: > > #include <iostream> > extern void foo(); > int main() { > int x = 0; > try { > x = 37 + 927; > foo(); > } catch (...) { > std::cout << x << '\n'; > } > } > > Any solution that violates this isn't a solution.These well-formedness constraints on IR are not constraints on actual user code, they're constraints on frontends and transforms. Frontends have to translate actual user code into well-formed IR, and transforms have to preserve well-formedness. In your example, a C++ frontend is going to generate this code with %x as an alloca, like so: (I've taken the liberty of changing "x = 37 + 927;" to "extern int count; x = count;". This makes the operation non-constant but still non-throwing. I don't think it substantively changes the example other than to remove a potential source of confusion, but if you disagree, the same argument works with the original example) entry: %x = alloca i32 store i32 0, i32* x br label %try try: unwinds to %lp %count = load i32* @count store i32 %count, i32* x call void @foo() br label %return lp: dispatch [ catchall i8* null, label %catch ] catch: # I've removed the begin/end catch calls for simplicity, if you think they're relevant I can elaborate %t = load i32* %x call void @operator<<(%"std::ostream"* @std::cout, i32 %t) br label %return return: ret i32 0 This is well-formed SSA; the alloca instruction %x is in the entry block and thus dominates both the store in %try and the load in %catch. mem2reg wants to eliminate %x and replace the load in %catch with a fixed value. This involves looking at the value stored in %x at all predecessor points, which is a challenge because one of those predecessors is an arbitrary point within the block %try, and %x actually has two values over that extent. So mem2reg would have to split %try and make a phi in %lp, like so: try1: unwinds to %lp %count = load i32* @count br label %try2 try2: unwinds to %lp call void foo() br label %return lp: %t = phi i32 [ i32 0, label %try1 ], [ i32 %count, label %try2 ] #etc. That's a lot of added complexity for mem2reg (and other transformations that use it as a subroutine), but it's pretty much inherent in any design where edges don't always come from terminators. Now, in this specific case, mem2reg could say "hey, %count can't throw, I don't need the phi at all". But it would still need to split %lp to make the IR well-formed; it's just that %lp1 wouldn't have an "unwinds" clause. And in the general case, it needs a phi. John.
On Sun, Nov 28, 2010 at 13:57, Bill Wendling <wendling at apple.com> wrote:> In other words, this is completely valid code with proper semantics: > > #include <iostream> > extern void foo(); > int main() { > int x = 0; > try { > x = 37 + 927; > foo(); > } catch (...) { > std::cout << x << '\n'; > } > } > > Any solution that violates this isn't a solution. >The obvious direct translation of that is still fine: entry: %x = alloca store %x, 0 br try try: unwind catch %t = add 37, 927 store %x, %t call foo br after catch: %y = load %x ... print %y ... br after Since the result of the store isn't used in the catch block (only the side effect). It would be up to mem2reg to split the try block when removing the alloca, the same as it's currently up to mem2reg to add the phi node in the after block.