[Bug tree-optimization/15524] [4.0 Regression] jump threading on trees is slow with switch statements with large # of cases

["law at redhat dot com" <gcc-bugzilla at gcc dot gnu dot org>]

------- Additional Comments From law at redhat dot com  2005-04-12 16:55 -------
Subject: Re:  [4.0 Regression] jump threading
	on trees is slow with switch statements with large # of cases

On Fri, 2005-04-08 at 21:49 +0000, dnovillo at gcc dot gnu dot org
wrote:
> ------- Additional Comments From dnovillo at gcc dot gnu dot org  2005-04-08 21:49 -------
> (In reply to comment #18)
> 
> > Ugh.  The copy we inserted turned out to be totally useless for determining
> > that the condition at the end of BB5 is always false.  Argggh.
> > 
> > To make this scheme work we'd have to do copy insertions anytime the
> > COND_EXPR_COND or SWITCH_EXPR changed.  Worse yet, we'd need to call
> > rewrite_ssa_into_ssa to keep things in SSA form.  Double Ugh.
> > 
> It's a matter of scheduling the passes mostly.  The reason you're having a hard
> time here is mostly because some of the scalar cleanups haven't run.  Suppose
> that we do this after FRE and copy propagation.  We end up with:
As we discussed on the phone, it can be seen in that way.  For VRP you
have the nice property that it's self-contained.  ie, the other
optimizers have already run, you insert your ASSERT_EXPRs, then run the
VPR algorithm, then destroy the ASSERT_EXPRs.

That mental model doesn't work right now with the way DOM & the jump
threader because they are too tightly intertwined.

As I mentioned on the phone, what I want to do long term is have the
jump threader which maintains its temporary equivalences and queries
the value handles created by PRE/FRE or whatever.

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.  The uses of the PHI result are put onto a
worklist of statements which need their value handles updated and
which may now be redundant.  If the state is proven redundant, then
we have a new copy to propagate and the uses of the LHS of the
statement are put on the worklist.

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.

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.

Jeff



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15524