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: Wed, 07 Jul 2010 10:40:57 -0600
- Subject: Re: 0005-Search-all-dominated-blocks-for-expressions-to-hoist.patch
- References: <4C18F225.email@example.com> <4C18F491.firstname.lastname@example.org> <AANLkTinT0L8VRpB_Y_sQfoQ4x_tC3CZl5csz6IWJezb2@mail.gmail.com> <4C1FB369.email@example.com> <AANLkTimJKmvB19PiVdPDNh2g6VX9fryFGh4vR_rrm_J3@mail.gmail.com> <4C1FC91D.firstname.lastname@example.org> <4C20AB99.email@example.com> <4C225BA4.firstname.lastname@example.org> <4C237F81.email@example.com> <4C2B8911.firstname.lastname@example.org> <4C2B9B4D.email@example.com> <4C2CC3F4.firstname.lastname@example.org> <4C2E0F06.email@example.com>
On 07/02/10 10:08, Maxim Kuvyrkov wrote:
Isn't it fairly simple? If we have an expression we want to hoist from
some set of blocks; isn't the destination the LCA within the dominator
tree of those blocks?
It appears we were thinking about different approaches to using LCA to
solve this problem, the algorithm I thought you were suggesting
would've been bulky and slow.
Now I see that the problem can be solved reasonably fast with LCA too.
I don't yet have all the details figured out, so if you have a clear
picture of the algorithm in mind, please don't hold it to yourself ;)
I realize that LCA is usually formulated as the LCA between two blocks,
but isn't it relatively easy to compute the LCA for pairs and
Or is this problem some kind of implementation detail that I've missed?
If you want to keep the changes separate (and there's certainly value in
doing that), the way to go is fix the correctness issue first, then the
improvement of the optimization. Particularly when we're still
iterating on the implementation of the optimization.
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?!?
I can't give a definitive answer to if and why hoisting needs
transpout. It seems to me transpout can be safely removed if we just
avoid propagating data across complex edges in compute_vbeinout and
That said, I would not check in such a clean up in the same patch as
improving code hoisting to look into non-immediately-dominated blocks.
Let's keep bugs these two changes can introduce separate.
I don't think there is. Anyway, we will find out once I or someone
else implement removal of transpout.I don't. It was in the first external version of hoisting I posted and
the first development version I checked into Cygnus's internal tree.
Jeff, do you remember why transpout sets were introduced in the first
Since there's no edge insertions with hoisting, the only potential
problem I can see is when the hoisted expression itself can trigger
traversal of an abnormal edge and the block we want to put the
expression does not have an edge to the handler. In that case we'd need
to add edges in the cfg and I don't see any compensation code in gcse.c
to deal with that case.
Assuming that's the situation we need to avoid then we really need to
switch the pre-like code since it detects expressions which can cause
traversal of the abnormal edge much better. It's a fairly simple patch
since it just prunes some expressions from the local tables before
running the dataflow solver.