This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: 0005-Search-all-dominated-blocks-for-expressions-to-hoist.patch

On 07/02/10 10:08, Maxim Kuvyrkov wrote:

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 ;)
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?

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 recurse/iterate?

Or is this problem some kind of implementation detail that I've missed?

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 hoist_expr_reaches_here_p.

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.
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.

I don't think there is. Anyway, we will find out once I or someone else implement removal of transpout.

Jeff, do you remember why transpout sets were introduced in the first place?
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.

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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]