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

[Maxim Kuvyrkov <maxim@codesourcery.com>]

On 6/23/10 11:20 PM, Paolo Bonzini wrote:
> On 06/23/2010 09:08 PM, Maxim Kuvyrkov wrote:
>> 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.
>
> 30 seems like "infinite" for most practical cases.

Exactly.  The purpose of the parameter is to avoid quadratic behavior on 
weird CFGs.  For normal graphs code hoisting should traverse the whole 
structure.

The problem of excessive code hoisting that arises when looking for 
expressions in the whole dominator subtree [instead of just immediately 
dominated blocks] will be addressed in another patch I'm about to post. 
  The the GCSE-complex-constants thread.

Thanks,

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