This is the mail archive of the
mailing list for the GCC project.
Re: [PATCH][RFC] Fix PR56113 more
- From: Richard Biener <rguenther at suse dot de>
- To: Jakub Jelinek <jakub at redhat dot com>
- Cc: gcc-patches at gcc dot gnu dot org, Steven Bosscher <steven at gcc dot gnu dot org>
- Date: Mon, 18 Mar 2013 09:46:57 +0100 (CET)
- Subject: Re: [PATCH][RFC] Fix PR56113 more
- References: <alpine.LNX.email@example.com> <20130201094922.GK4385@tucnak.redhat.com> <alpine.LNX.firstname.lastname@example.org> <alpine.LNX.email@example.com>
On Fri, 8 Feb 2013, Richard Biener wrote:
> On Fri, 1 Feb 2013, Richard Biener wrote:
> > On Fri, 1 Feb 2013, Jakub Jelinek wrote:
> > > On Fri, Feb 01, 2013 at 10:00:00AM +0100, Richard Biener wrote:
> > > >
> > > > This reduces compile-time of the testcase in PR56113 (with n = 40000)
> > > > from 575s to 353s. It does so by reducing the quadratic algorithm
> > > > to impose an order on visiting dominator sons during a domwalk.
> > > >
> > > > Steven raises the issue that there exist domwalk users that modify
> > > > the CFG during the walk and thus the new scheme does not work
> > > > (at least optimally, as the current quadratic scheme does). As
> > > > we are using a fixed-size sbitmap to track visited blocks existing
> > > > domwalks cannot add new blocks to the CFG so the worst thing that
> > > > can happen is that the order of dominator sons is no longer
> > > > optimal (I suppose with the "right" CFG manipulations even the
> > > > domwalk itself does not work - so I'd be hesitant to try to support
> > > > such domwalk users) - back to the state before any ordering
> > > > was imposed on the dom children visits (see rev 159100).
> > >
> > > I think it would be desirable to first analyze the failures Steven saw, if
> > > any. As you said, asan doesn't use domwalk, so it is a mystery to me.
> > Yeah. Now, fortunately domwalk.h is only directly included and thus
> > the set of optimizers using it are
> > compare-elim.c:#include "domwalk.h"
> > domwalk.c:#include "domwalk.h"
> > fwprop.c:#include "domwalk.h"
> > gimple-ssa-strength-reduction.c:#include "domwalk.h"
> > graphite-sese-to-poly.c:#include "domwalk.h"
> > tree-into-ssa.c:#include "domwalk.h"
> > tree-ssa-dom.c:#include "domwalk.h"
> > tree-ssa-dse.c:#include "domwalk.h"
> > tree-ssa-loop-im.c:#include "domwalk.h"
> > tree-ssa-math-opts.c: If we did this using domwalk.c, an efficient
> > implementation would have
> > tree-ssa-phiopt.c:#include "domwalk.h"
> > tree-ssa-pre.c:#include "domwalk.h"
> > tree-ssa-pre.c:/* Local state for the eliminate domwalk. */
> > tree-ssa-pre.c: eliminate domwalk. */
> > tree-ssa-pre.c:/* At the current point of the eliminate domwalk make OP
> > available. */
> > tree-ssa-pre.c:/* Perform elimination for the basic-block B during the
> > domwalk. */
> > tree-ssa-strlen.c:#include "domwalk.h"
> > tree-ssa-uncprop.c:#include "domwalk.h"
> > I don't see any target specific ones that do not have coverage
> > with x86_64 multilib testing (maybe compare-elim.c? though that
> > doesn't really require a domwalk as it is only using the
> > before_dom_children hook). That said, arbitrary CFG manipulations
> > during domwalk certainly will not preserve "domwalk" properties
> > of a domwalk.
> > Steven - can you reproduce your failures (and on which target?)
> I'm not sure what to do about this old compile-time regression.
> Apart from this known issue in domwalk.c GCC 4.8 scalability (at -O1)
> looks quite good. I can certainly push it back to 4.9 if you think
> it's too risky to fix now.
I have committed this to trunk now, r196769.
2013-03-18 Richard Biener <firstname.lastname@example.org>
* domwalk.c (bb_postorder): New global static.
(cmp_bb_postorder): New function.
(walk_dominator_tree): Replace scheme imposing an order for
visiting dominator sons by one sorting them at the time they
are pushed on the stack.