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

[Jeff Law <law at redhat dot com>]

On 06/24/10 09:53, Maxim Kuvyrkov wrote:
> On 6/23/10 11:08 PM, Maxim Kuvyrkov wrote:
> ...
> > > This can be addressed with a walk over the dominator tree after we
> > > compute VBEout. Start with the root and descend in the tree keeping a
> > > bitset of expressions that should be alive up the tree. If current node
> > >
> > > 1. has a single successor,
> > > 2. has i'th expression set in VBEout,
> > > 3. the successor has i'th expression set in VBEout,
> > > 4. current node doesn't generate i'th expression,
> > > 5. i'th expression is not marked in the bitset as required up the tree,
> > >
> > > than we can hoist i'th expression in the successor with the same result
> > > as in the current node and not unnecessarily extend live ranges. There
> > > maybe a couple more details to the above, but the problem should be
> > > easily fixable.
> >
> > This is implemented as cleanup_code_hoist_vbeout() function. The
> > solution it produces is OK from correctness point of view (it removes
> > bits from VBEout), but, please, *check my reasoning* to make sure it
> > doesn't remove from VBEout expressions it shouldn't.
>
> There is a flaw in the implementation I posted yesterday.  VBEout sets 
> have to be cleaned up considering data both downward and upward the 
> dominator tree; see new example and comments in 
> compute_code_hoist_vbeinout.
>
> This updated patch corrects the cleaning routine and adds several 
> comments to annotate its actions.
>
> Does this look OK?


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?

In your comments you have the following CFG:



+  /* We cannot cleanup VBEout in a single traversal.  There has to be both
+     upward and downward links when computing VBEout of current block to
+     avoid removing bits that shouldn't be removed.  E.g., consider
+     the following dominator tree; '*' marks blocks which compute same
+     expression, the expression can be freely moved; the expected result
+     is that we move computations of '*' from (3) and (6) to (2).
+
+       2
+      / \
+     3*  4
+        / \
+       5   6*
+
+     Doing a depth-first search over this tree without and upward link
+     will remove the expression from VBEout[4] (there's no point of 
hoisting
+     the expression to (4) if it's not computed in both (5) and (6).
+     When cleaning up VBEout[2] we won't see the expression as needed 
in (4),
+     so we will remove it from VBEout[2] leaving it to (3) to calculate
+     it's own copy of '*'.

The first paragraph of your comment implies that we'd want to hoist the 
expression from 3 & 6 into 2.  However, that's not a valid 
transformation as the path 2, 4, 5 does not evaluate the expression in 
the original CFG.  VBEout for block 4 should be false since the 
expression is not evaluated in block #5.

Jeff