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

[Maxim Kuvyrkov]

On 6/22/10 4:24 PM, Maxim Kuvyrkov wrote:
> 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).

The attached patch adds max-hoist-depth parameter to control depth of 
descend in dominator tree.  The default value of 30 should be enough for 
most practical purposes.

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

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.

VBEout for the testcase in PR33828 is now just as expected:

hoisting vbeinout computation: 2 passes
vbeout(2): n_bits = 5, set = {1 3 }
vbeout(3): n_bits = 5, set = {1 3 }
vbeout(4): n_bits = 5, set = {1 3 }
vbeout(5): n_bits = 5, set = {0 1 2 3 }
vbeout(6): n_bits = 5, set = {}
hoisting vbeout cleanup pass
vbeout(2): n_bits = 5, set = {}
vbeout(3): n_bits = 5, set = {}
vbeout(4): n_bits = 5, set = {1 3 }
vbeout(5): n_bits = 5, set = {}
vbeout(6): n_bits = 5, set = {}

With cleaned up vbeout the pass hoists occurences from bb5 and bb6 to 
bb4 instead of [unnecessarily far] to bb2:

PRE/HOIST: end of bb 4, insn 47, copying expression 1 to reg 146

Cleaning up vbeout also makes for less mechanic work to be done in 
hoist_code speeding up the pass.

Any comments?  OK to check in?

-- 
Maxim Kuvyrkov
CodeSourcery
maxim@codesourcery.com
(650) 331-3385 x724
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: 0005-Also-search-non-immediately-dominated-blocks-for-exp.ChangeLog
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20100623/dfd0f79f/attachment.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: 0005-Also-search-non-immediately-dominated-blocks-for-exp.patch
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20100623/dfd0f79f/attachment-0001.ksh>