This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [tcb] Incremental SSA updates
Hello,
> >-- it includes the local dominance patch
> > (http://gcc.gnu.org/ml/gcc-patches/2004-10/msg01633.html). This is
> > used to avoid going over all statements in basic blocks in
> > update_ssa_form_locally. Rationale is that the primary use of
> > update_ssa_form is incremental updating of ssa form; in this case
> > usually only very few statements are involved, and scaning
> > long basic blocks to find a few interesting statements might get
> > expensive.
> >
> > This patch requires changes to bsi_insert_before and
> > bsi_insert_after that in turn make us more picky about
> > what these functions can do -- on several places we call
> > bsi_insert_after (stmts, BSI_NEW_STMT), where stmts is in fact a list of
> > statements; BSI_NEW_STMT placement does not make much sense in this
> > case, and now we abort for it. Thus several changes outside of
> > tree-cfg. To make it more clear which changes are due to this patch,
> > changelog for it is separate (the first chunk).
> >
> Hmm, why do you need this? The IL scan is certainly very cheap and we
> only scan a subset of the graph. Have you noticed any speedups with
> this more complex approach?
I did not try to measure. But if the patch is really used in an
incremental fashion, scanning long basic blocks most definitely is not
cheap.
> >-- description of internals and usage of tree-update-ssa.c can be found
> > at the beginning of the file. The interface is somewhat similar to
> > the one your patch had, except that it enables you to have more than one
> > new definition for each ssa name, and also allows you to specify the
> > set of uses you want to rewrite. The algorithm used is the same
> > as tree-into-ssa uses, except that it is more careful in order to
> > touch only the area where the rewritten values are live (so that it
> > can be used in incremental fashion).
> >
> Yeah, this is exactly what update_ssa does.
No it is not; update_ssa features for example
rewrite_blocks (start_bb, REWRITE_UPDATE);
which will walk everything that's dominated by start_bb,
not just the relevant part of the dominance tree.
> It only updates the exact
> sub-graph used by the new and old names. There may be a many-to-one
> mapping between new names and old names. I'm not sure why you need the
> ability to only rewrite a subset of the uses. Where is it used?
It is supposed to be used for example during updates of loop closed ssa
form, where you know that only some of the uses are affected.
> >-- there are several pieces of code affected by the lack of the immediate
> > uses patch (marked with TBRWIUA comment). For now we cope without
> > this patch by finding the uses of the rewritten ssa name by scanning
> > the whole program (in gather_uses_to_update_op). This of course
> > makes it inefficient to use the patch for incremental ssa form
> > updates for now, unless you provide the set of uses explicitly
> > yourself.
> >
> Hmm, OK. My approach doesn't need a whole program scan and needs no
> immediate uses, we only scan the exact subgraph.
Your approach scans whole subgraph dominated by start_bb, which
may be significantly more than necessary area. In the use in vrp,
it will usually be almost whole program.
Zdenek