------- Additional Comments From law at redhat dot com 2005-04-13 17:11 -------
Subject: Re: [4.0 Regression] jump threading
on trees is slow with switch statements with large # of cases
On Wed, 2005-04-13 at 13:04 +0000, dnovillo at redhat dot com wrote:
> ------- Additional Comments From dnovillo at redhat dot com 2005-04-13 13:03
> -------
> Subject: Re: [4.0 Regression] jump threading on trees is slow with switch
> statements with large # of cases
>
> On Tue, Apr 12, 2005 at 04:55:20PM -0000, law at redhat dot com wrote:
>
> > That mental model doesn't work right now with the way DOM & the
> > jump threader because they are too tightly intertwined.
> >
> The link that you have still not shown me is why doesn't this
> mental model work for the jump threader. That's why I said that
> I need to run the threader myself and see why it needs all these
> additional crutches.
That the model we wont to go to -- but it's certainly not where we
are today. Why? Because the jump threader exposes more optimization
opportunities for DOM (including constant and copy propagations) and
DOM exposes more opportunities for the threader. They are inherently
tied together with their current structure.
>
> If the code has been cleaned up of redundancies, copies
> propagated, names have known values and ranges are set, then I
> don't see why we would need all the extra baggage.
Because threading exposes new opportunities to perform constant
and copy propagation and redundancy elimination.
>
> > The iteration step we see today would turn into a worklist.
> > ie, after we thread jumps, we walk through the IL for PHIs
> > which represent a copy that can be propagated.
> >
> Ah, here's something specific I don't follow. Why would you have
> these PHIs anymore? If all the arguments were ultimately
> equivalent, then the various propagators are bound to have
> removed them. If not, that sounds like a bug in them.
They are exposed as a result of jump threading. For example we might
have something like:
BB 3:
x3 = PHI (x2 (0), x1 (1), x1 (2));
[ ... ]
if (cond) goto X, else goto Y
If jump threading manages to determine where the conditional will go
when BB3 is reached via BB0, then we'll be able to remove the PHI
argument associated with the edge from BB0 to BB3. That in turn exposes
a copy propagation opportunity (x3 = x1).
Or when we thread a jump we might expose a new redundancy because the
dominator graph changed. Whenever we expose a redundancy we also expose
a copy propagation opportunity.
>
> > What's nice about this is the bulk of DOM as we know it today
> > disappears along with the expensive iteration in the case when
> > jumps are threaded. We just need the right APIs for copy
> > propagation and value handles.
> >
> Again, why? The propagators are supposed to have done this
> already. They are all supposed to work in conditional regions.
You really don't seem to understand what the threader does and how its
actions can expose new optimization opportunities. I might suggest you
look very closely at what happens for a test like 20030714-2.c which is
derived from real code. As we thread jumps, we expose new redundancy
elimination opportunities, which in turn expose new copy propagation
opportunities.
> > We could still potentially use ASSERT_EXPRs to encode
> > information about edge equivalences, though we probably would
> > still want the ASSERT_EXPR to appear as statement rather than
> > the RHS of a MODIFY_EXPR.
> >
> Odd, the nice thing about assertions being on the RHS is that you
> pin their result to a specific SSA name that you then get to use
> at every place naturally dominated by the assertion.
>
> If you could give me a concrete test case that I could sink my
> teeth in, that'd be great.
Go back the PR I've referenced twice.
jeff
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15524
