This is the mail archive of the
mailing list for the GCC project.
- From: Jeff Law <law at redhat dot com>
- To: Maxim Kuvyrkov <maxim at codesourcery dot com>
- Cc: Steven Bosscher <stevenb dot gcc at gmail dot com>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Thu, 01 Jul 2010 10:36:04 -0600
- Subject: Re: 0005-Search-all-dominated-blocks-for-expressions-to-hoist.patch
- References: <4C18F225.firstname.lastname@example.org> <4C18F491.email@example.com> <AANLkTinT0L8VRpB_Y_sQfoQ4x_tC3CZl5csz6IWJezb2@mail.gmail.com> <4C1FB369.firstname.lastname@example.org> <AANLkTimJKmvB19PiVdPDNh2g6VX9fryFGh4vR_rrm_J3@mail.gmail.com> <4C1FC91D.email@example.com> <4C20AB99.firstname.lastname@example.org> <4C225BA4.email@example.com> <4C237F81.firstname.lastname@example.org> <4C2B8911.email@example.com> <4C2B9B4D.firstname.lastname@example.org>
On 06/30/10 13:30, Maxim Kuvyrkov wrote:
While this specific case may be reasonably safe, in general we really
want to avoid bi-directional dataflow solvers as it's often hard to
prove termination, it's hard to evaluate their compile-time performance,
they're typically more difficult to understand for anyone reading the
code, and (personal opinion here) often they're a symptom of not solving
the right problem.
It looks like you've got a bi-directional dataflow problem to clean up
VBEout, in general we really want to avoid bi-directional problems. Is
there some reason you're not using a lowest common ancestor algorithm
A dataflow problem seems simpler for this case. The problem uses
bi-directional links to compute a set of expressions that will be
subtracted from VBEout on each iteration, it never adds new
expressions to destination sets. I, therefore, claim that the fact
that this particular problem uses bi-directional links does not really
have any significant negative impact.
Interesting. While working on implementing cleanup of VBEout sets I
oscillated several times between bottom-up dominator tree walk and
iterative walk. At some point I got myself convinced that dominator
walk would do just as fine the job as iterative walk. Then I come up
with the above case which needs more than a single walk to get to the
right solution. Now you pointed out that the above case is invalid,
which makes me think that a dominator walk would suffice after all.A little bit. But it's still unclear why we're not using lowest common
ancestor here. It seems that tells us precisely where we want to hoist
to avoid unnecessary movements. Or is this to prevent hoisting into an
LCA, then hoisting the expression again on a later pass further up the
Still, the iterative solution looks better to me as it makes it
crystal clear that only expressions that definitely won't be hoisted
to BB will be removed from BB's VBEout.
Does this make sense?
The other issues that I think are still unanswered:
1. Why precisely to do we need transpout for hoisting. We should
only be hoisting a very busy expression into a block which dominates the
original evaluations. We don't insert on edges, so we don't have to
worry about splitting abnormals. The only thing I can think of is
perhaps the hoisting might require new edges in the destination block in
the expression potentially traps?!?
2. Assuming there's a good reason for #1, for correctness we should
drop transpout and instead use the same method as PRE.