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.