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?) Thanks, Richard.
