On Tuesday 27 January 2009 18:28, Eli Friedman wrote:> You can use a no-op bitcast for scalars, but there isn't any reliable > way to do it for all first-class values.Guh.> That said, I don't quite follow the issue. This is SSA, so the only way a > value can change is if you change the code.This isn't (yet) SSA. This is mem2reg turning things into SSA.> I'm not really following what the issue is in this testcase, though, > so I could be missing something. The way you're describing it, > mem2reg appears to be working as intended; the correct completion is > in fact as follows: > // x = phi(x.0, expr) > // y = phi(y.0, x)Yes, that's what mem2reg ends up with.> > In this particular example another solution would be to reorder the phis > > but I don't think that will work in the general case. > > PHI nodes don't have an ordering, at least conceptually; they're not > real instructions.They don't have an ordering? So what does your above code mean? I would have expected it to mean that y is either the value of y.0 or the value from the phi immediate preceeding it. Is that not correct? If my understanding is correct then the code is wrong. The original code looks something like this: x = 0 y = 0 do [...use x and y...] y = x x = expr end do So y should get the previous value of x, not the value updated at the end of the loop body. If there truly is no ordering then perhaps Prakash is correct and this is an out-of-SSA problem. I'd appreciate your opinion on this. I read the Briggs SPE paper a long time ago. Time to dust it off. -Dave
On Jan 28, 2009, at 9:06 AM, David Greene wrote:>>> In this particular example another solution would be to reorder >>> the phis >>> but I don't think that will work in the general case. >> >> PHI nodes don't have an ordering, at least conceptually; they're not >> real instructions. > > They don't have an ordering? So what does your above code mean? I > would have > expected it to mean that y is either the value of y.0 or the value > from the > phi immediate preceeding it. Is that not correct? > > If my understanding is correct then the code is wrong. The original > code > looks something like this: > > x = 0 > y = 0 > do > [...use x and y...] > y = x > x = expr > end do > > So y should get the previous value of x, not the value updated at > the end of > the loop body. > > If there truly is no ordering then perhaps Prakash is correct and > this is an > out-of-SSA problem. I'd appreciate your opinion on this. I read > the Briggs > SPE paper a long time ago. Time to dust it off.Eli is correct in that, in theory, PHI nodes in SSA form are unordered, i.e. all PHIs in a given basic block are evaluated simultaneously. In that case, the correct code would be: x.0 = 0 y.0 = 0 do x = phi(x.0, x.1) y = phi(y.0, x) x.1 = ... ... end do LLVM does not implement this simultaneous evaluation for practical reasons. Most situations can be resolved by reordering the PHI nodes, though the swap copy still remains: x.0 = 0 y.0 = 0 do x = phi(x.0, y) y = phi(y.0, x) // NOT CORRECT WITH ORDERED PHIS! ... end do In this case, you can resolve it by inserting an extra PHI node: x.0 = 0 y.0 = 0 do foo = phi(undef, x) x = phi(x.0, y) y = phi(y.0, foo) // CORRECT WITH ORDERED PHIS! ... end do --Owen
On Jan 28, 2009, at 9:06 AM, David Greene wrote:> On Tuesday 27 January 2009 18:28, Eli Friedman wrote: > >> You can use a no-op bitcast for scalars, but there isn't any reliable >> way to do it for all first-class values. > > Guh. > >> That said, I don't quite follow the issue. This is SSA, so the >> only way a >> value can change is if you change the code. > > This isn't (yet) SSA. This is mem2reg turning things into SSA. > >> I'm not really following what the issue is in this testcase, though, >> so I could be missing something. The way you're describing it, >> mem2reg appears to be working as intended; the correct completion is >> in fact as follows: >> // x = phi(x.0, expr) >> // y = phi(y.0, x) > > Yes, that's what mem2reg ends up with.Why is this a problem? All phis execute "atomically". What problem are you seeing in practice? -Chris
On Jan 28, 2009, at 9:32 AM, Chris Lattner wrote:> Why is this a problem? All phis execute "atomically". What problem > are you seeing in practice? > > -ChrisI'm pretty sure we don't actually implement atomic execution of phis. I recall having the same basic issue a long time ago, and being informed of this. --Owen
On Wednesday 28 January 2009 11:32, Chris Lattner wrote:> On Jan 28, 2009, at 9:06 AM, David Greene wrote: > > On Tuesday 27 January 2009 18:28, Eli Friedman wrote: > >> You can use a no-op bitcast for scalars, but there isn't any reliable > >> way to do it for all first-class values. > > > > Guh. > > > >> That said, I don't quite follow the issue. This is SSA, so the > >> only way a > >> value can change is if you change the code. > > > > This isn't (yet) SSA. This is mem2reg turning things into SSA. > > > >> I'm not really following what the issue is in this testcase, though, > >> so I could be missing something. The way you're describing it, > >> mem2reg appears to be working as intended; the correct completion is > >> in fact as follows: > >> // x = phi(x.0, expr) > >> // y = phi(y.0, x) > > > > Yes, that's what mem2reg ends up with. > > Why is this a problem? All phis execute "atomically". What problem > are you seeing in practice?I'm getting incorrect answers. How can a set of phis with a dependence execute simultaenously? There is only one definition of x and it has to happen before the use of x in the phi defining y, doesn't it? Owen says:> In this case, you can resolve it by inserting an extra PHI node:> x.0 = 0 > y.0 = 0 > do > foo = phi(undef, x) > x = phi(x.0, y) > y = phi(y.0, foo) // CORRECT WITH ORDERED PHIS! > ... > end doAgain, how can simultaenous execution of statements with a dependence have any meaning? For practical reasons, as Owen says, LLVM does not treat phis as executing simultaneously. So in this case wouldn't there be a use-before-def error on x? I should think Verifier would choke on this code. -Dave