[PATCH] rtl-optimization/110587 - speedup find_hard_regno_for_1

[PATCH] rtl-optimization/110587 - speedup find_hard_regno_for_1

[Richard Biener]

The following applies a micro-optimization to find_hard_regno_for_1,
re-ordering the check so we can easily jump-thread by using an else.
This reduces the time spent in this function by 15% for the testcase
in the PR.

Bootstrap & regtest running on x86_64-unknown-linux-gnu, OK if that
passes?

Thanks,
Richard.

	PR rtl-optimization/110587
	* lra-assigns.cc (find_hard_regno_for_1): Re-order checks.
---
 gcc/lra-assigns.cc | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/gcc/lra-assigns.cc b/gcc/lra-assigns.cc
index b8582dcafff..d2ebcfd5056 100644
--- a/gcc/lra-assigns.cc
+++ b/gcc/lra-assigns.cc
@@ -522,14 +522,15 @@ find_hard_regno_for_1 (int regno, int *cost, int try_only_hard_regno,
 	       r2 != NULL;
 	       r2 = r2->start_next)
 	    {
-	      if (r2->regno >= lra_constraint_new_regno_start
+	      if (live_pseudos_reg_renumber[r2->regno] < 0
+		  && r2->regno >= lra_constraint_new_regno_start
 		  && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
-		  && live_pseudos_reg_renumber[r2->regno] < 0
 		  && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
 		sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
 				   r2->regno);
-	      if (live_pseudos_reg_renumber[r2->regno] >= 0
-		  && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
+	      else if (live_pseudos_reg_renumber[r2->regno] >= 0
+		       && rclass_intersect_p
+			    [regno_allocno_class_array[r2->regno]])
 		sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
 	    }
 	}
-- 
2.35.3

Re: [PATCH] rtl-optimization/110587 - speedup find_hard_regno_for_1

[Jeff Law]

On 8/8/23 10:49, Vladimir Makarov wrote:
> 
> On 8/7/23 09:18, Richard Biener wrote:
>> On Wed, 2 Aug 2023, Richard Biener wrote:
>>
>>> On Mon, 31 Jul 2023, Jeff Law wrote:
>>>
>>>>
>>>> On 7/31/23 04:54, Richard Biener via Gcc-patches wrote:
>>>>> On Tue, 25 Jul 2023, Richard Biener wrote:
>>>>>
>>>>>> The following applies a micro-optimization to find_hard_regno_for_1,
>>>>>> re-ordering the check so we can easily jump-thread by using an else.
>>>>>> This reduces the time spent in this function by 15% for the testcase
>>>>>> in the PR.
>>>>>>
>>>>>> Bootstrap & regtest running on x86_64-unknown-linux-gnu, OK if that
>>>>>> passes?
>>>>> Ping.
>>>>>
>>>>>> Thanks,
>>>>>> Richard.
>>>>>>
>>>>>>   PR rtl-optimization/110587
>>>>>>   * lra-assigns.cc (find_hard_regno_for_1): Re-order checks.
>>>>>> ---
>>>>>>    gcc/lra-assigns.cc | 9 +++++----
>>>>>>    1 file changed, 5 insertions(+), 4 deletions(-)
>>>>>>
>>>>>> diff --git a/gcc/lra-assigns.cc b/gcc/lra-assigns.cc
>>>>>> index b8582dcafff..d2ebcfd5056 100644
>>>>>> --- a/gcc/lra-assigns.cc
>>>>>> +++ b/gcc/lra-assigns.cc
>>>>>> @@ -522,14 +522,15 @@ find_hard_regno_for_1 (int regno, int *cost, 
>>>>>> int
>>>>>> @@ try_only_hard_regno,
>>>>>>            r2 != NULL;
>>>>>>            r2 = r2->start_next)
>>>>>>            {
>>>>>> -          if (r2->regno >= lra_constraint_new_regno_start
>>>>>> +          if (live_pseudos_reg_renumber[r2->regno] < 0
>>>>>> +          && r2->regno >= lra_constraint_new_regno_start
>>>>>>        && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
>>>>>> -          && live_pseudos_reg_renumber[r2->regno] < 0
>>>>>>        && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
>>>>>>      sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
>>>>>>                       r2->regno);
>>>>>> -          if (live_pseudos_reg_renumber[r2->regno] >= 0
>>>>>> -          && 
>>>>>> rclass_intersect_p[regno_allocno_class_array[r2->regno]])
>>>>>> +          else if (live_pseudos_reg_renumber[r2->regno] >= 0
>>>>>> +               && rclass_intersect_p
>>>>>> +                [regno_allocno_class_array[r2->regno]])
>>>>>>      sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
>>>> My biggest concern here would be r2->regno < 0  in the new code 
>>>> which could
>>>> cause an OOB array reference in the first condition of the test.
>>>>
>>>> Isn't that the point if the original ordering?  Test that r2->regno is
>>>> reasonable before using it as an array index?
>>> Note the original code is
>>>
>>>                if (r2->regno >= lra_constraint_new_regno_start
>>> ...
>>>           if (live_pseudos_reg_renumber[r2->regno] >= 0
>>> ...
>>>
>>> so we are going to access live_pseudos_reg_renumber[r2->regno]
>>> independent on the r2->regno >= lra_constraint_new_regno_start check,
>>> so I don't think that's the point of the original ordering.  Note
>>> I preserved the ordering with respect to other array accesses,
>>> the speedup seen is because we now have the
>>>
>>>
>>>     if (live_pseudos_reg_renumber[r2->regno] < 0
>>>         ...
>>>     else if (live_pseudos_reg_renumber[r2->regno] >= 0
>>>              ...
>>>
>>> structure directly exposed which helps the compiler.
>>>
>>> I think the check on r2->regno is to decide whether to alter
>>> conflict_reload_and_inheritance_pseudos or
>>> live_range_hard_reg_pseudos (so it's also somewhat natural to check
>>> that first).
>> So - OK?
>>
> Richard, sorry, I overlooked this thread.
> 
> Yes, it is OK to commit.  In general Jeff has a reasonable concern but 
> in this case r2->regno is always >= 0 and I can not imagine reasons that 
> we will change algorithm in the future in such way when it is not true.
Thanks for confirming it's a non-issue.  No objection from me.

jeff

Re: [PATCH] rtl-optimization/110587 - speedup find_hard_regno_for_1

[Vladimir Makarov]

On 8/7/23 09:18, Richard Biener wrote:
> On Wed, 2 Aug 2023, Richard Biener wrote:
>
>> On Mon, 31 Jul 2023, Jeff Law wrote:
>>
>>>
>>> On 7/31/23 04:54, Richard Biener via Gcc-patches wrote:
>>>> On Tue, 25 Jul 2023, Richard Biener wrote:
>>>>
>>>>> The following applies a micro-optimization to find_hard_regno_for_1,
>>>>> re-ordering the check so we can easily jump-thread by using an else.
>>>>> This reduces the time spent in this function by 15% for the testcase
>>>>> in the PR.
>>>>>
>>>>> Bootstrap & regtest running on x86_64-unknown-linux-gnu, OK if that
>>>>> passes?
>>>> Ping.
>>>>
>>>>> Thanks,
>>>>> Richard.
>>>>>
>>>>>   PR rtl-optimization/110587
>>>>>   * lra-assigns.cc (find_hard_regno_for_1): Re-order checks.
>>>>> ---
>>>>>    gcc/lra-assigns.cc | 9 +++++----
>>>>>    1 file changed, 5 insertions(+), 4 deletions(-)
>>>>>
>>>>> diff --git a/gcc/lra-assigns.cc b/gcc/lra-assigns.cc
>>>>> index b8582dcafff..d2ebcfd5056 100644
>>>>> --- a/gcc/lra-assigns.cc
>>>>> +++ b/gcc/lra-assigns.cc
>>>>> @@ -522,14 +522,15 @@ find_hard_regno_for_1 (int regno, int *cost, int
>>>>> @@ try_only_hard_regno,
>>>>>            r2 != NULL;
>>>>>            r2 = r2->start_next)
>>>>>    	    {
>>>>> -	      if (r2->regno >= lra_constraint_new_regno_start
>>>>> +	      if (live_pseudos_reg_renumber[r2->regno] < 0
>>>>> +		  && r2->regno >= lra_constraint_new_regno_start
>>>>>        && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
>>>>> -		  && live_pseudos_reg_renumber[r2->regno] < 0
>>>>>        && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
>>>>>      sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
>>>>>    				   r2->regno);
>>>>> -	      if (live_pseudos_reg_renumber[r2->regno] >= 0
>>>>> -		  && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
>>>>> +	      else if (live_pseudos_reg_renumber[r2->regno] >= 0
>>>>> +		       && rclass_intersect_p
>>>>> +			    [regno_allocno_class_array[r2->regno]])
>>>>>      sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
>>> My biggest concern here would be r2->regno < 0  in the new code which could
>>> cause an OOB array reference in the first condition of the test.
>>>
>>> Isn't that the point if the original ordering?  Test that r2->regno is
>>> reasonable before using it as an array index?
>> Note the original code is
>>
>>                if (r2->regno >= lra_constraint_new_regno_start
>> ...
>> 	      if (live_pseudos_reg_renumber[r2->regno] >= 0
>> ...
>>
>> so we are going to access live_pseudos_reg_renumber[r2->regno]
>> independent on the r2->regno >= lra_constraint_new_regno_start check,
>> so I don't think that's the point of the original ordering.  Note
>> I preserved the ordering with respect to other array accesses,
>> the speedup seen is because we now have the
>>
>>
>>     if (live_pseudos_reg_renumber[r2->regno] < 0
>>         ...
>>     else if (live_pseudos_reg_renumber[r2->regno] >= 0
>>              ...
>>
>> structure directly exposed which helps the compiler.
>>
>> I think the check on r2->regno is to decide whether to alter
>> conflict_reload_and_inheritance_pseudos or
>> live_range_hard_reg_pseudos (so it's also somewhat natural to check
>> that first).
> So - OK?
>
Richard, sorry, I overlooked this thread.

Yes, it is OK to commit.  In general Jeff has a reasonable concern but 
in this case r2->regno is always >= 0 and I can not imagine reasons that 
we will change algorithm in the future in such way when it is not true.

Re: [PATCH] rtl-optimization/110587 - speedup find_hard_regno_for_1

[Richard Biener]

On Wed, 2 Aug 2023, Richard Biener wrote:

> On Mon, 31 Jul 2023, Jeff Law wrote:
> 
> > 
> > 
> > On 7/31/23 04:54, Richard Biener via Gcc-patches wrote:
> > > On Tue, 25 Jul 2023, Richard Biener wrote:
> > > 
> > >> The following applies a micro-optimization to find_hard_regno_for_1,
> > >> re-ordering the check so we can easily jump-thread by using an else.
> > >> This reduces the time spent in this function by 15% for the testcase
> > >> in the PR.
> > >>
> > >> Bootstrap & regtest running on x86_64-unknown-linux-gnu, OK if that
> > >> passes?
> > > 
> > > Ping.
> > > 
> > >> Thanks,
> > >> Richard.
> > >>
> > >>  PR rtl-optimization/110587
> > >>  * lra-assigns.cc (find_hard_regno_for_1): Re-order checks.
> > >> ---
> > >>   gcc/lra-assigns.cc | 9 +++++----
> > >>   1 file changed, 5 insertions(+), 4 deletions(-)
> > >>
> > >> diff --git a/gcc/lra-assigns.cc b/gcc/lra-assigns.cc
> > >> index b8582dcafff..d2ebcfd5056 100644
> > >> --- a/gcc/lra-assigns.cc
> > >> +++ b/gcc/lra-assigns.cc
> > >> @@ -522,14 +522,15 @@ find_hard_regno_for_1 (int regno, int *cost, int
> > >> @@ try_only_hard_regno,
> > >>           r2 != NULL;
> > >>           r2 = r2->start_next)
> > >>   	    {
> > >> -	      if (r2->regno >= lra_constraint_new_regno_start
> > >> +	      if (live_pseudos_reg_renumber[r2->regno] < 0
> > >> +		  && r2->regno >= lra_constraint_new_regno_start
> > >>       && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
> > >> -		  && live_pseudos_reg_renumber[r2->regno] < 0
> > >>       && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
> > >>     sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
> > >>   				   r2->regno);
> > >> -	      if (live_pseudos_reg_renumber[r2->regno] >= 0
> > >> -		  && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
> > >> +	      else if (live_pseudos_reg_renumber[r2->regno] >= 0
> > >> +		       && rclass_intersect_p
> > >> +			    [regno_allocno_class_array[r2->regno]])
> > >>     sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
> > My biggest concern here would be r2->regno < 0  in the new code which could
> > cause an OOB array reference in the first condition of the test.
> > 
> > Isn't that the point if the original ordering?  Test that r2->regno is
> > reasonable before using it as an array index?
> 
> Note the original code is
> 
>               if (r2->regno >= lra_constraint_new_regno_start
> ...
> 	      if (live_pseudos_reg_renumber[r2->regno] >= 0
> ...
> 
> so we are going to access live_pseudos_reg_renumber[r2->regno]
> independent on the r2->regno >= lra_constraint_new_regno_start check,
> so I don't think that's the point of the original ordering.  Note
> I preserved the ordering with respect to other array accesses,
> the speedup seen is because we now have the
> 
> 
>    if (live_pseudos_reg_renumber[r2->regno] < 0
>        ...
>    else if (live_pseudos_reg_renumber[r2->regno] >= 0
>             ...
> 
> structure directly exposed which helps the compiler.
> 
> I think the check on r2->regno is to decide whether to alter
> conflict_reload_and_inheritance_pseudos or
> live_range_hard_reg_pseudos (so it's also somewhat natural to check
> that first).

So - OK?

Thanks,
Richard.

Re: [PATCH] rtl-optimization/110587 - speedup find_hard_regno_for_1

[Richard Biener]

On Mon, 31 Jul 2023, Jeff Law wrote:

> 
> 
> On 7/31/23 04:54, Richard Biener via Gcc-patches wrote:
> > On Tue, 25 Jul 2023, Richard Biener wrote:
> > 
> >> The following applies a micro-optimization to find_hard_regno_for_1,
> >> re-ordering the check so we can easily jump-thread by using an else.
> >> This reduces the time spent in this function by 15% for the testcase
> >> in the PR.
> >>
> >> Bootstrap & regtest running on x86_64-unknown-linux-gnu, OK if that
> >> passes?
> > 
> > Ping.
> > 
> >> Thanks,
> >> Richard.
> >>
> >>  PR rtl-optimization/110587
> >>  * lra-assigns.cc (find_hard_regno_for_1): Re-order checks.
> >> ---
> >>   gcc/lra-assigns.cc | 9 +++++----
> >>   1 file changed, 5 insertions(+), 4 deletions(-)
> >>
> >> diff --git a/gcc/lra-assigns.cc b/gcc/lra-assigns.cc
> >> index b8582dcafff..d2ebcfd5056 100644
> >> --- a/gcc/lra-assigns.cc
> >> +++ b/gcc/lra-assigns.cc
> >> @@ -522,14 +522,15 @@ find_hard_regno_for_1 (int regno, int *cost, int
> >> @@ try_only_hard_regno,
> >>           r2 != NULL;
> >>           r2 = r2->start_next)
> >>   	    {
> >> -	      if (r2->regno >= lra_constraint_new_regno_start
> >> +	      if (live_pseudos_reg_renumber[r2->regno] < 0
> >> +		  && r2->regno >= lra_constraint_new_regno_start
> >>       && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
> >> -		  && live_pseudos_reg_renumber[r2->regno] < 0
> >>       && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
> >>     sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
> >>   				   r2->regno);
> >> -	      if (live_pseudos_reg_renumber[r2->regno] >= 0
> >> -		  && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
> >> +	      else if (live_pseudos_reg_renumber[r2->regno] >= 0
> >> +		       && rclass_intersect_p
> >> +			    [regno_allocno_class_array[r2->regno]])
> >>     sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
> My biggest concern here would be r2->regno < 0  in the new code which could
> cause an OOB array reference in the first condition of the test.
> 
> Isn't that the point if the original ordering?  Test that r2->regno is
> reasonable before using it as an array index?

Note the original code is

              if (r2->regno >= lra_constraint_new_regno_start
...
	      if (live_pseudos_reg_renumber[r2->regno] >= 0
...

so we are going to access live_pseudos_reg_renumber[r2->regno]
independent on the r2->regno >= lra_constraint_new_regno_start check,
so I don't think that's the point of the original ordering.  Note
I preserved the ordering with respect to other array accesses,
the speedup seen is because we now have the


   if (live_pseudos_reg_renumber[r2->regno] < 0
       ...
   else if (live_pseudos_reg_renumber[r2->regno] >= 0
            ...

structure directly exposed which helps the compiler.

I think the check on r2->regno is to decide whether to alter
conflict_reload_and_inheritance_pseudos or
live_range_hard_reg_pseudos (so it's also somewhat natural to check
that first).

Thanks,
Richard.

Re: [PATCH] rtl-optimization/110587 - speedup find_hard_regno_for_1

[Jeff Law]

On 7/31/23 04:54, Richard Biener via Gcc-patches wrote:
> On Tue, 25 Jul 2023, Richard Biener wrote:
> 
>> The following applies a micro-optimization to find_hard_regno_for_1,
>> re-ordering the check so we can easily jump-thread by using an else.
>> This reduces the time spent in this function by 15% for the testcase
>> in the PR.
>>
>> Bootstrap & regtest running on x86_64-unknown-linux-gnu, OK if that
>> passes?
> 
> Ping.
> 
>> Thanks,
>> Richard.
>>
>> 	PR rtl-optimization/110587
>> 	* lra-assigns.cc (find_hard_regno_for_1): Re-order checks.
>> ---
>>   gcc/lra-assigns.cc | 9 +++++----
>>   1 file changed, 5 insertions(+), 4 deletions(-)
>>
>> diff --git a/gcc/lra-assigns.cc b/gcc/lra-assigns.cc
>> index b8582dcafff..d2ebcfd5056 100644
>> --- a/gcc/lra-assigns.cc
>> +++ b/gcc/lra-assigns.cc
>> @@ -522,14 +522,15 @@ find_hard_regno_for_1 (int regno, int *cost, int try_only_hard_regno,
>>   	       r2 != NULL;
>>   	       r2 = r2->start_next)
>>   	    {
>> -	      if (r2->regno >= lra_constraint_new_regno_start
>> +	      if (live_pseudos_reg_renumber[r2->regno] < 0
>> +		  && r2->regno >= lra_constraint_new_regno_start
>>   		  && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
>> -		  && live_pseudos_reg_renumber[r2->regno] < 0
>>   		  && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
>>   		sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
>>   				   r2->regno);
>> -	      if (live_pseudos_reg_renumber[r2->regno] >= 0
>> -		  && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
>> +	      else if (live_pseudos_reg_renumber[r2->regno] >= 0
>> +		       && rclass_intersect_p
>> +			    [regno_allocno_class_array[r2->regno]])
>>   		sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
My biggest concern here would be r2->regno < 0  in the new code which 
could cause an OOB array reference in the first condition of the test.

Isn't that the point if the original ordering?  Test that r2->regno is 
reasonable before using it as an array index?

jeff

Re: [PATCH] rtl-optimization/110587 - speedup find_hard_regno_for_1

[Richard Biener]

On Tue, 25 Jul 2023, Richard Biener wrote:

> The following applies a micro-optimization to find_hard_regno_for_1,
> re-ordering the check so we can easily jump-thread by using an else.
> This reduces the time spent in this function by 15% for the testcase
> in the PR.
> 
> Bootstrap & regtest running on x86_64-unknown-linux-gnu, OK if that
> passes?

Ping.

> Thanks,
> Richard.
> 
> 	PR rtl-optimization/110587
> 	* lra-assigns.cc (find_hard_regno_for_1): Re-order checks.
> ---
>  gcc/lra-assigns.cc | 9 +++++----
>  1 file changed, 5 insertions(+), 4 deletions(-)
> 
> diff --git a/gcc/lra-assigns.cc b/gcc/lra-assigns.cc
> index b8582dcafff..d2ebcfd5056 100644
> --- a/gcc/lra-assigns.cc
> +++ b/gcc/lra-assigns.cc
> @@ -522,14 +522,15 @@ find_hard_regno_for_1 (int regno, int *cost, int try_only_hard_regno,
>  	       r2 != NULL;
>  	       r2 = r2->start_next)
>  	    {
> -	      if (r2->regno >= lra_constraint_new_regno_start
> +	      if (live_pseudos_reg_renumber[r2->regno] < 0
> +		  && r2->regno >= lra_constraint_new_regno_start
>  		  && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
> -		  && live_pseudos_reg_renumber[r2->regno] < 0
>  		  && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
>  		sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
>  				   r2->regno);
> -	      if (live_pseudos_reg_renumber[r2->regno] >= 0
> -		  && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
> +	      else if (live_pseudos_reg_renumber[r2->regno] >= 0
> +		       && rclass_intersect_p
> +			    [regno_allocno_class_array[r2->regno]])
>  		sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
>  	    }
>  	}
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)