On 08/24/11 13:12, Richard Sandiford wrote:
> Sorry, I'm find this a bit tough to review.  Could you provide some
> overview comments somewhere to say what the new algorithm is?
> The comment at the head of regrename.c still describes the current
> bb-local algorithm.

New patch below, with extra comments.  Let me know if more are needed.

> One thing though:
> 
> Bernd Schmidt <bernds@codesourcery.com> writes:
>> @@ -215,8 +306,9 @@ merge_overlapping_regs (HARD_REG_SET *ps
>>    IOR_HARD_REG_SET (*pset, head->hard_conflicts);
>>    EXECUTE_IF_SET_IN_BITMAP (&head->conflicts, 0, i, bi)
>>      {
>> -      du_head_p other = VEC_index (du_head_p, id_to_chain, i);
>> +      du_head_p other = chain_from_id (i);
>>        unsigned j = other->nregs;
>> +      gcc_assert (other != head);
>>        while (j-- > 0)
>>  	SET_HARD_REG_BIT (*pset, other->regno + j);
>>      }
> 
> Is this effectively cubic in the number of chains?  There are O(chains)
> calls to merge_overlapping_regs, O(chains) nodes in the conflicts bitmap,
> and chain_from_id chases O(chains) merges.

I've made chain_from_id store its final result in the original chain, so
it'll take O(chains) only once per chain.

Bootstrapped and tested on i686-linux (with rr enabled at O2). I've also
redone performance tests with a popular embedded benchmark on C6X; some
fluctuations around +/-5%, and 20% improvement on one benchmark.


Bernd