There is no register-to-register copy instructions in LLVM. I've found a
bug
in mem2reg (LLVM 2.3 but it doesn't appear to be fixed in trunk either) and
a
copy instruction seems to be the easiest way to fix it.
Consider this code coming into the RenamePass phase of mem2reg.
"*" in the phi means we haven't added that incoming value yet.
// x.0 = ...
// y.0 = ...
//
// do
// x = phi(x.0, *)
// y = phi(y.0, *)
// [...]
// store x -> y
// store expr -> x
// end do
//
// We are updating both phis to add a value from a back edge
// When we saw the first store we set IncomingVals[y] to x.
// When we see the second store we need to create a
// temporary t = x before the second store and set
// IncomingVals[y] to t. Otherwise y's phi will pick up the
// new value of x (expr) rather than the old, proper one.
This bug triggers on a code we have here. I've been unable to successfully
bugpoint it as bugpoint croaks with a bad_alloc exception. We're in the
midst
of upgrading to 2.4 so I will re-try bugpoint then. The above pseudocode
represents the situation adequately.
How do I go about creating the copy t = x? I don't want to use an add with
a
zero constant because it may not be optimized in all circustations (floating
point, for example).
In this particular example another solution would be to reorder the phis but I
don't think that will work in the general case.
-Dave
On Tuesday 27 January 2009 16:54, 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.Actually, that wouldn't work at all. Never mind. :) -Dave
On Tue, Jan 27, 2009 at 2:54 PM, David Greene <dag at cray.com> wrote:> How do I go about creating the copy t = x? I don't want to use an add with a > zero constant because it may not be optimized in all circustations (floating > point, for example).You can use a no-op bitcast for scalars, but there isn't any reliable way to do it for all first-class values. 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. 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)> 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. -Eli
I dont know if this helps but this sort of an issue apparently crops up during the un-SSA phase, if copy propagation is done on SSA'ed code. The exact problem is mentioned in (the Lost Copy problem) "Practical Improvements to the Construction and Destruction of Static Single Assignment Form". Since there is no explicit assignment (copy) instruction in LLVM, I dont know if this is a problem here. regards, Prakash On Tue, Jan 27, 2009 at 7:28 PM, Eli Friedman <eli.friedman at gmail.com>wrote:> On Tue, Jan 27, 2009 at 2:54 PM, David Greene <dag at cray.com> wrote: > > How do I go about creating the copy t = x? I don't want to use an add > with a > > zero constant because it may not be optimized in all circustations > (floating > > point, for example). > > You can use a no-op bitcast for scalars, but there isn't any reliable > way to do it for all first-class values. 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. > > 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) > > > 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. > > -Eli > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090128/6e65f4d0/attachment.html>
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