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

[Maxim Kuvyrkov]

On 6/22/10 12:18 AM, Jeff Law wrote:
> On 06/21/10 13:28, Steven Bosscher wrote:
>>
>> I experimented with a patch similar to Maxim's already 2.5 years ago
>> (and offered to work on it for CS, but there was no interest in this
>> work at the time :-/) See these three Bugzilla comments:
>>
>> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33828#c2
> Right. This is precisely the problem with using immediate dominators.
> This doesn't argue that Maxim's approach is wrong or bad for compile
> time performance or anything like that. It merely raises the same issue.

I agree with Steven that the search is better be constrained, possibly, 
with a large enough constant.  I've added a new parameter and a 
dominance.c function to return dominated blocks up to depth N in the 
dominator tree (with N==1 being immediate dominators and N==0 being all 
dominators).

Does this sound OK?

...
>> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33828#c13
>>
>> Note especially the pessimization in comment #13 of PR33828.
>> Therefore I maintain my objection to this patch.
> Clearly you don't want to hoist any higher than the lowest common
> dominator. Otherwise you unreasonably lengthen lifetimes. Maxim will
> need to address this problem as well.

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.

I will post second version of the patch in a couple of days.

Thank you,

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