On 03/24/2017 05:54 AM, Richard Biener wrote:
On Fri, Mar 24, 2017 at 10:39 AM, Segher Boessenkool
<seg...@kernel.crashing.org> wrote:
On Fri, Mar 24, 2017 at 09:13:59AM +0100, Richard Biener wrote:
https://gcc.gnu.org/ml/gcc-patches/2017-02/msg01485.html
?
What about it? That suggestion would make fwprop do *less* useful work,
while in principle the problem is that it *already* does not enough!
Ok, not knowing a lot about fwprop I take your word for it (but GIMPLE level
forwprop works that way and certainly you can't substitute a def into a use
that is before the def).
When fwprop has done a propagation it makes fresh new uses for all the
sources of the resulting insn, which it adds at the end of the table.
It doesn't reuse the original uses.
Yes, that's what I suspected.
If fwprop actually tried all propagations (and never tried substituting
X with X, which it currently does), there would be no problem.
To me it looked like fwprop tries to iterate over all propagations but
it iterates over a changing data structure which is why it "oscillates".
But I didn't actually verify that theory (in fact, I just very much disliked
Berns patch give its compile-time cost).
We have, in order, in one bb:
B = A|Z
A = B
D = A
where each of those is the only set of its dest. Now the first thing
tried is propagating the first into the second. This fails. Then,
Z is found to be zero, so we get
B = A
A = B
D = A
If the first was now propagated into the second again, all is fine
(all three vars are set to A). But this is not tried again. The
second is propagated into the third, giving
B = A
A = B
D = B
and then the first is propagated into the third, and we repeat
forever.
This patch is a workaround; it makes no difference on pretty much any
code, except this single testcase (which has undefined behaviour,
uninitialised variables).
Yeah, your fix looks similar to the other hack I suggested.
I have implemented the "retry things" as well fwiw, but a) it is too
big and invasive for stage 4, and b) it kind of sucks, needs more
work, even more invasive. The workaround is cheap and solves the
immediate problem.
Agreed, still iterating over the DF uses in the first place looks like
the bug (given this "all uses" data structure changes during propagation!).
I'd have done
for (BBs in RPO order)
for (insn in BB)
repeat:
for (use in insn)
if (propagate_into (use))
goto repeat;
I wonder why it wasn't implemented like this in the first place.
ISTM that with the exception of loops that it ought to give the same
final result. For loops, I wouldn't expect opportunities along
backedges to be all that common.
It also seems to me that we ought to be able to verify if the different
order changes things.
Just to be clear, I can live with either approach. I would even be
option to Segher's as a stopgap and yours for gcc-8.
jeff
