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
On Jan 28, 2009, at 9:50 AM, David Greene wrote:> 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? >The "normal" answer would be that they execute atomically only at the IR level. Part of the out-of-SSA translation that happens in the backend is to insert sufficient copies to to hide the non-atomic nature of the execution.>> 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 > > Again, 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.I have no idea if the Verifier actually accepts this, but it is semantically valid because of the conditional execution involved in the phi. The value of x will never be read before it has been def'd. --Owen
On Jan 28, 2009, at 9:50 AM, David Greene wrote:>> 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?PHIs can't depend on each other.> Again, how can simultaenous execution of statements with a > dependence have any > meaning?There is no such thing.> For practical reasons, as Owen says, LLVM does not treat phis as > executing simultaneously.He's wrong. -Chris
On Wednesday 28 January 2009 12:07, Owen Anderson wrote:> On Jan 28, 2009, at 9:50 AM, David Greene wrote: > > 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? > > The "normal" answer would be that they execute atomically only at the > IR level. Part of the out-of-SSA translation that happens in the > backend is to insert sufficient copies to to hide the non-atomic > nature of the execution. > > >> 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 > > > > Again, 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. > > I have no idea if the Verifier actually accepts this, but it is > semantically valid because of the conditional execution involved in > the phi. The value of x will never be read before it has been def'd.So if this is true then it seems that you wouldn't need the extra phi anyway, since y = phi(y.0, x) would be semantically valid. Ok, so I can understand how the SSA construction can be considered valid. All right, I'll have to go and see if out-of-SSA does the right thing with this. -Dave
On Wednesday 28 January 2009 12:30, Chris Lattner wrote:> > For practical reasons, as Owen says, LLVM does not treat phis as > > executing simultaneously. > > He's wrong.Are we absolutely sure about this? There are a lot of algorithms that walk basic blocks. -Dave
On Wednesday 28 January 2009 12:30, Chris Lattner wrote:> On Jan 28, 2009, at 9:50 AM, David Greene wrote: > >> 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? > > PHIs can't depend on each other.So just to be clear, this means that all phi uses are considered to execute before any phi derfs? -Dave