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 06/30/10 13:30, Maxim Kuvyrkov wrote:

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 here?

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

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.

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?
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 dominator tree?

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.



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