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

[Maxim Kuvyrkov]

On 6/30/10 10:12 PM, Jeff Law wrote:
> 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?

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.

Is there any reason bi-directional dataflow problems should be avoided 
at all cost?

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

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?

Thanks,

-- 
Maxim Kuvyrkov
CodeSourcery
maxim@codesourcery.com
(650) 331-3385 x724