[PR103437,committed] IRA: Process multiplication overflow in priority calculation for allocno assignments

  The following patch fixes

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103437

The patch was successfully bootstrapped and tested on x86-64. There is 
no test as the bug occurs on GCC built with sanitizing for an existing 
go test.
  

On Thu, Dec 02, 2021 at 08:53:31AM -0500, Vladimir Makarov via Gcc-patches wrote:
> The following patch fixes
> 
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103437
> 
> The patch was successfully bootstrapped and tested on x86-64. There is no
> test as the bug occurs on GCC built with sanitizing for an existing go test.

> commit c6cf5ac1522c54b2ced98fc687e973a9ff17ba1e
> Author: Vladimir N. Makarov <vmakarov@redhat.com>
> Date:   Thu Dec 2 08:29:45 2021 -0500
> 
>     [PR103437] Process multiplication overflow in priority calculation for allocno assignments
>     
>     We process overflows in cost calculations but for huge functions
>     priority calculation can overflow as priority can be bigger the cost
>     used for it.  The patch fixes the problem.
>     
>     gcc/ChangeLog:
>     
>             PR rtl-optimization/103437
>             * ira-color.c (setup_allocno_priorities): Process multiplication
>             overflow.
> 
> diff --git a/gcc/ira-color.c b/gcc/ira-color.c
> index 3d01c60800c..1f80cbea0e2 100644
> --- a/gcc/ira-color.c
> +++ b/gcc/ira-color.c
> @@ -2796,7 +2796,7 @@ static int *allocno_priorities;
>  static void
>  setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
>  {
> -  int i, length, nrefs, priority, max_priority, mult;
> +  int i, length, nrefs, priority, max_priority, mult, diff;
>    ira_allocno_t a;
>  
>    max_priority = 0;
> @@ -2807,11 +2807,14 @@ setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
>        ira_assert (nrefs >= 0);
>        mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
>        ira_assert (mult >= 0);
> -      allocno_priorities[ALLOCNO_NUM (a)]
> -	= priority
> -	= (mult
> -	   * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a))
> -	   * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
> +      mult *= ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
> +      diff = ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
> +      /* Multiplication can overflow for very large functions.
> +	 Check the overflow and constrain the result if necessary: */
> +      if (__builtin_smul_overflow (mult, diff, &priority)

I'm afraid we can't use __builtin_smul_overflow, not all system compilers
will have that.
But, as it is done in int and we kind of rely on int being 32-bit on host
and rely on long long being 64-bit, I think you can do something like:
      long long priorityll = (long long) mult * diff;
      priority = priorityll;
      if (priorityll != priority
...

> +	  || priority <= -INT_MAX)
> +	priority = diff >= 0 ? INT_MAX : -INT_MAX;
> +      allocno_priorities[ALLOCNO_NUM (a)] = priority;
>        if (priority < 0)
>  	priority = -priority;
>        if (max_priority < priority)

	Jakub
  

On 2021-12-02 09:00, Jakub Jelinek wrote:
> On Thu, Dec 02, 2021 at 08:53:31AM -0500, Vladimir Makarov via Gcc-patches wrote:
>> The following patch fixes
>>
>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103437
>>
>> The patch was successfully bootstrapped and tested on x86-64. There is no
>> test as the bug occurs on GCC built with sanitizing for an existing go test.
> I'm afraid we can't use __builtin_smul_overflow, not all system compilers
> will have that.
> But, as it is done in int and we kind of rely on int being 32-bit on host
> and rely on long long being 64-bit, I think you can do something like:
>        long long priorityll = (long long) mult * diff;
>        priority = priorityll;
>        if (priorityll != priority
> ...
>
>
My 1st version of the patch was based on long long but the standard does 
not guarantee that int size is smaller than long long size.  Although it 
is true for all targets supported by GCC.

Another solution would be to switching to int32_t instead of int for 
costs but it will require a lot of changes in RA code.

I see your point for usage system compiler different from GCC and LLVM.  
I guess I could change it to

#if __GNUC__ >= 5

current code

#else

long long code

#endif


What do you think?
  

On Thu, Dec 02, 2021 at 09:23:20AM -0500, Vladimir Makarov wrote:
> 
> On 2021-12-02 09:00, Jakub Jelinek wrote:
> > On Thu, Dec 02, 2021 at 08:53:31AM -0500, Vladimir Makarov via Gcc-patches wrote:
> > > The following patch fixes
> > > 
> > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103437
> > > 
> > > The patch was successfully bootstrapped and tested on x86-64. There is no
> > > test as the bug occurs on GCC built with sanitizing for an existing go test.
> > I'm afraid we can't use __builtin_smul_overflow, not all system compilers
> > will have that.
> > But, as it is done in int and we kind of rely on int being 32-bit on host
> > and rely on long long being 64-bit, I think you can do something like:
> >        long long priorityll = (long long) mult * diff;
> >        priority = priorityll;
> >        if (priorityll != priority
> > ...
> > 
> > 
> My 1st version of the patch was based on long long but the standard does not
> guarantee that int size is smaller than long long size.  Although it is true
> for all targets supported by GCC.
> 
> Another solution would be to switching to int32_t instead of int for costs
> but it will require a lot of changes in RA code.
> 
> I see your point for usage system compiler different from GCC and LLVM.  I
> guess I could change it to
> 
> #if __GNUC__ >= 5

#ifdef __has_builtin
# if __has_builtin(__builtin_smul_overflow)
would be the best check.
And you can just gcc_assert (sizeof (long long) >= 2 * sizeof (int));
in the fallback code ;)

	Jakub
  

On 2021-12-02 09:29, Jakub Jelinek wrote:
> On Thu, Dec 02, 2021 at 09:23:20AM -0500, Vladimir Makarov wrote:
>> On 2021-12-02 09:00, Jakub Jelinek wrote:
>>> On Thu, Dec 02, 2021 at 08:53:31AM -0500, Vladimir Makarov via Gcc-patches wrote:
>>>> The following patch fixes
>>>>
>>>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103437
>>>>
>>>> The patch was successfully bootstrapped and tested on x86-64. There is no
>>>> test as the bug occurs on GCC built with sanitizing for an existing go test.
>>> I'm afraid we can't use __builtin_smul_overflow, not all system compilers
>>> will have that.
>>> But, as it is done in int and we kind of rely on int being 32-bit on host
>>> and rely on long long being 64-bit, I think you can do something like:
>>>         long long priorityll = (long long) mult * diff;
>>>         priority = priorityll;
>>>         if (priorityll != priority
>>> ...
>>>
>>>
>> My 1st version of the patch was based on long long but the standard does not
>> guarantee that int size is smaller than long long size.  Although it is true
>> for all targets supported by GCC.
>>
>> Another solution would be to switching to int32_t instead of int for costs
>> but it will require a lot of changes in RA code.
>>
>> I see your point for usage system compiler different from GCC and LLVM.  I
>> guess I could change it to
>>
>> #if __GNUC__ >= 5
> #ifdef __has_builtin
> # if __has_builtin(__builtin_smul_overflow)
> would be the best check.
> And you can just gcc_assert (sizeof (long long) >= 2 * sizeof (int));
> in the fallback code ;)

I used static_assert in my 1st patch version.  I think it is better than 
gcc_assert..

I'll commit patch fix today.  Thank you for your feedback, Jakub.
  

On Thu, Dec 2, 2021 at 3:38 PM Vladimir Makarov via Gcc-patches <
gcc-patches@gcc.gnu.org> wrote:

>
> On 2021-12-02 09:29, Jakub Jelinek wrote:
> > On Thu, Dec 02, 2021 at 09:23:20AM -0500, Vladimir Makarov wrote:
> >> On 2021-12-02 09:00, Jakub Jelinek wrote:
> >>> On Thu, Dec 02, 2021 at 08:53:31AM -0500, Vladimir Makarov via
> Gcc-patches wrote:
> >>>> The following patch fixes
> >>>>
> >>>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103437
> >>>>
> >>>> The patch was successfully bootstrapped and tested on x86-64. There
> is no
> >>>> test as the bug occurs on GCC built with sanitizing for an existing
> go test.
> >>> I'm afraid we can't use __builtin_smul_overflow, not all system
> compilers
> >>> will have that.
> >>> But, as it is done in int and we kind of rely on int being 32-bit on
> host
> >>> and rely on long long being 64-bit, I think you can do something like:
> >>>         long long priorityll = (long long) mult * diff;
> >>>         priority = priorityll;
> >>>         if (priorityll != priority
> >>> ...
> >>>
> >>>
> >> My 1st version of the patch was based on long long but the standard
> does not
> >> guarantee that int size is smaller than long long size.  Although it is
> true
> >> for all targets supported by GCC.
> >>
> >> Another solution would be to switching to int32_t instead of int for
> costs
> >> but it will require a lot of changes in RA code.
> >>
> >> I see your point for usage system compiler different from GCC and
> LLVM.  I
> >> guess I could change it to
> >>
> >> #if __GNUC__ >= 5
> > #ifdef __has_builtin
> > # if __has_builtin(__builtin_smul_overflow)
> > would be the best check.
> > And you can just gcc_assert (sizeof (long long) >= 2 * sizeof (int));
> > in the fallback code ;)
>
> I used static_assert in my 1st patch version.  I think it is better than
> gcc_assert..
>
> I'll commit patch fix today.  Thank you for your feedback, Jakub.
>
>
Thanks, I confirm I am seeing build failures with gcc-4.8.5 ;-)

Christophe
  

On 2021-12-02 10:52, Christophe Lyon wrote:
>
>
> On Thu, Dec 2, 2021 at 3:38 PM Vladimir Makarov via Gcc-patches 
> <gcc-patches@gcc.gnu.org> wrote:
>
>
>     On 2021-12-02 09:29, Jakub Jelinek wrote:
>     > On Thu, Dec 02, 2021 at 09:23:20AM -0500, Vladimir Makarov wrote:
>     >> On 2021-12-02 09:00, Jakub Jelinek wrote:
>     >>> On Thu, Dec 02, 2021 at 08:53:31AM -0500, Vladimir Makarov via
>     Gcc-patches wrote:
>     >>>> The following patch fixes
>     >>>>
>     >>>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103437
>     >>>>
>     >>>> The patch was successfully bootstrapped and tested on x86-64.
>     There is no
>     >>>> test as the bug occurs on GCC built with sanitizing for an
>     existing go test.
>     >>> I'm afraid we can't use __builtin_smul_overflow, not all
>     system compilers
>     >>> will have that.
>     >>> But, as it is done in int and we kind of rely on int being
>     32-bit on host
>     >>> and rely on long long being 64-bit, I think you can do
>     something like:
>     >>>         long long priorityll = (long long) mult * diff;
>     >>>         priority = priorityll;
>     >>>         if (priorityll != priority
>     >>> ...
>     >>>
>     >>>
>     >> My 1st version of the patch was based on long long but the
>     standard does not
>     >> guarantee that int size is smaller than long long size. 
>     Although it is true
>     >> for all targets supported by GCC.
>     >>
>     >> Another solution would be to switching to int32_t instead of
>     int for costs
>     >> but it will require a lot of changes in RA code.
>     >>
>     >> I see your point for usage system compiler different from GCC
>     and LLVM.  I
>     >> guess I could change it to
>     >>
>     >> #if __GNUC__ >= 5
>     > #ifdef __has_builtin
>     > # if __has_builtin(__builtin_smul_overflow)
>     > would be the best check.
>     > And you can just gcc_assert (sizeof (long long) >= 2 * sizeof
>     (int));
>     > in the fallback code ;)
>
>     I used static_assert in my 1st patch version.  I think it is
>     better than
>     gcc_assert..
>
>     I'll commit patch fix today.  Thank you for your feedback, Jakub.
>
>
> Thanks, I confirm I am seeing build failures with gcc-4.8.5 ;-)
>
I've committed the following patch with the backup code.  Sorry for 
inconvenience.
  

On Thu, Dec 02, 2021 at 11:03:46AM -0500, Vladimir Makarov wrote:
> --- a/gcc/ira-color.c
> +++ b/gcc/ira-color.c
> @@ -2797,6 +2797,7 @@ static void
>  setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
>  {
>    int i, length, nrefs, priority, max_priority, mult, diff;
> +  bool overflow_backup_p = true;
>    ira_allocno_t a;
>  
>    max_priority = 0;
> @@ -2811,9 +2812,25 @@ setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
>        diff = ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
>        /* Multiplication can overflow for very large functions.
>  	 Check the overflow and constrain the result if necessary: */
> +#ifdef __has_builtin
> +#if __has_builtin(__builtin_smul_overflow)
> +      overflow_backup_p = false;
>        if (__builtin_smul_overflow (mult, diff, &priority)
>  	  || priority <= -INT_MAX)
>  	priority = diff >= 0 ? INT_MAX : -INT_MAX;
> +#endif
> +#endif
> +      if (overflow_backup_p)
> +	{
> +	  static_assert
> +	    (sizeof (long long) >= 2 * sizeof (int),
> +	     "overflow code does not work for such int and long long sizes");
> +	  long long priorityll = (long long) mult * diff;
> +	  if (priorityll < -INT_MAX || priorityll > INT_MAX)
> +	    priority = diff >= 0 ? INT_MAX : -INT_MAX;
> +	  else
> +	    priority = priorityll;
> +	}

This will require that long long is at least twice as large as int
everywhere, I thought you wanted to do that only when
__builtin_smul_overflow isn't available.
That would be
#ifdef __has_builtin
#if __has_builtin(__builtin_smul_overflow)
#define HAS_SMUL_OVERFLOW
#endif
#endif
#ifdef HAS_SMUL_OVERFLOW
      if (__builtin_smul_overflow (mult, diff, &priority)
	  || priority <= -INT_MAX)
	priority = diff >= 0 ? INT_MAX : -INT_MAX;
#else
      static_assert (sizeof (long long) >= 2 * sizeof (int),
		     "overflow code does not work for int wider"
		     "than half of long long");
      long long priorityll = (long long) mult * diff;
      if (priorityll < -INT_MAX || priorityll > INT_MAX)
	priority = diff >= 0 ? INT_MAX : -INT_MAX;
      else
	priority = priorityll;
#endif
Why priority <= -INT_MAX in the first case though,
shouldn't that be < -INT_MAX ?

	Jakub
  

On 2021-12-02 11:13, Jakub Jelinek wrote:
> On Thu, Dec 02, 2021 at 11:03:46AM -0500, Vladimir Makarov wrote:
>> --- a/gcc/ira-color.c
>> +++ b/gcc/ira-color.c
>> @@ -2797,6 +2797,7 @@ static void
>>   setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
>>   {
>>     int i, length, nrefs, priority, max_priority, mult, diff;
>> +  bool overflow_backup_p = true;
>>     ira_allocno_t a;
>>   
>>     max_priority = 0;
>> @@ -2811,9 +2812,25 @@ setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
>>         diff = ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
>>         /* Multiplication can overflow for very large functions.
>>   	 Check the overflow and constrain the result if necessary: */
>> +#ifdef __has_builtin
>> +#if __has_builtin(__builtin_smul_overflow)
>> +      overflow_backup_p = false;
>>         if (__builtin_smul_overflow (mult, diff, &priority)
>>   	  || priority <= -INT_MAX)
>>   	priority = diff >= 0 ? INT_MAX : -INT_MAX;
>> +#endif
>> +#endif
>> +      if (overflow_backup_p)
>> +	{
>> +	  static_assert
>> +	    (sizeof (long long) >= 2 * sizeof (int),
>> +	     "overflow code does not work for such int and long long sizes");
>> +	  long long priorityll = (long long) mult * diff;
>> +	  if (priorityll < -INT_MAX || priorityll > INT_MAX)
>> +	    priority = diff >= 0 ? INT_MAX : -INT_MAX;
>> +	  else
>> +	    priority = priorityll;
>> +	}
So simple problem and so many details :)
> This will require that long long is at least twice as large as int
> everywhere, I thought you wanted to do that only when
> __builtin_smul_overflow isn't available.

That is not critical as GCC and probably all others C++ compiler support 
only targets with this assertion.  I guess it is better to find this 
problem earlier on targets (if any) where it is not true *independently* 
on used compiler.

So it is difficult for me to know what is better.  Probably for 
GCC/Clang oriented world, your variant is better as it permits to 
compile the code by GCC even on targets where the assertion is false.

> That would be
> #ifdef __has_builtin
> #if __has_builtin(__builtin_smul_overflow)
> #define HAS_SMUL_OVERFLOW
> #endif
> #endif
> #ifdef HAS_SMUL_OVERFLOW
>        if (__builtin_smul_overflow (mult, diff, &priority)
> 	  || priority <= -INT_MAX)
> 	priority = diff >= 0 ? INT_MAX : -INT_MAX;
> #else
>        static_assert (sizeof (long long) >= 2 * sizeof (int),
> 		     "overflow code does not work for int wider"
> 		     "than half of long long");
>        long long priorityll = (long long) mult * diff;
>        if (priorityll < -INT_MAX || priorityll > INT_MAX)
> 	priority = diff >= 0 ? INT_MAX : -INT_MAX;
>        else
> 	priority = priorityll;
> #endif
> Why priority <= -INT_MAX in the first case though,
> shouldn't that be < -INT_MAX ?

My thought was to avoid 'always false' warning for non two's compliment 
binary representation targets.  As I remember C++17 started to require 
only two-compliment integers.  If we require to use only c++17 and 
upper, then probably it is better to fix it.

In any case, I feel these details are not my area of expertise. If you 
believe I should do these changes, please confirm that you want these 
changes and I'll definitely do this.  Thank you, Jakub.
  

On 2021-12-02 12:06, Vladimir Makarov wrote:
>
> On 2021-12-02 11:13, Jakub Jelinek wrote:
>> On Thu, Dec 02, 2021 at 11:03:46AM -0500, Vladimir Makarov wrote:
>>> --- a/gcc/ira-color.c
>>> +++ b/gcc/ira-color.c
>>> @@ -2797,6 +2797,7 @@ static void
>>>   setup_allocno_priorities (ira_allocno_t *consideration_allocnos, 
>>> int n)
>>>   {
>>>     int i, length, nrefs, priority, max_priority, mult, diff;
>>> +  bool overflow_backup_p = true;
>>>     ira_allocno_t a;
>>>       max_priority = 0;
>>> @@ -2811,9 +2812,25 @@ setup_allocno_priorities (ira_allocno_t 
>>> *consideration_allocnos, int n)
>>>         diff = ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
>>>         /* Multiplication can overflow for very large functions.
>>>        Check the overflow and constrain the result if necessary: */
>>> +#ifdef __has_builtin
>>> +#if __has_builtin(__builtin_smul_overflow)
>>> +      overflow_backup_p = false;
>>>         if (__builtin_smul_overflow (mult, diff, &priority)
>>>         || priority <= -INT_MAX)
>>>       priority = diff >= 0 ? INT_MAX : -INT_MAX;
>>> +#endif
>>> +#endif
>>> +      if (overflow_backup_p)
>>> +    {
>>> +      static_assert
>>> +        (sizeof (long long) >= 2 * sizeof (int),
>>> +         "overflow code does not work for such int and long long 
>>> sizes");
>>> +      long long priorityll = (long long) mult * diff;
>>> +      if (priorityll < -INT_MAX || priorityll > INT_MAX)
>>> +        priority = diff >= 0 ? INT_MAX : -INT_MAX;
>>> +      else
>>> +        priority = priorityll;
>>> +    }
> So simple problem and so many details :)
>> This will require that long long is at least twice as large as int
>> everywhere, I thought you wanted to do that only when
>> __builtin_smul_overflow isn't available.
>
> That is not critical as GCC and probably all others C++ compiler 
> support only targets with this assertion.  I guess it is better to 
> find this problem earlier on targets (if any) where it is not true 
> *independently* on used compiler.
>
> So it is difficult for me to know what is better.  Probably for 
> GCC/Clang oriented world, your variant is better as it permits to 
> compile the code by GCC even on targets where the assertion is false.
>
>
After some more considerations, I think you are right and the backup 
code should be conditional.  Because otherwise, there is no sense to use 
code with __builtin_smul_overflow.  I'll do the changes.
  

On 2021-12-02 12:21, Vladimir Makarov via Gcc-patches wrote:
>
> On 2021-12-02 12:06, Vladimir Makarov wrote:
>>
>>
>> So simple problem and so many details :)
>>> This will require that long long is at least twice as large as int
>>> everywhere, I thought you wanted to do that only when
>>> __builtin_smul_overflow isn't available.
>>
>> That is not critical as GCC and probably all others C++ compiler 
>> support only targets with this assertion.  I guess it is better to 
>> find this problem earlier on targets (if any) where it is not true 
>> *independently* on used compiler.
>>
>> So it is difficult for me to know what is better.  Probably for 
>> GCC/Clang oriented world, your variant is better as it permits to 
>> compile the code by GCC even on targets where the assertion is false.
>>
>>
> After some more considerations, I think you are right and the backup 
> code should be conditional.  Because otherwise, there is no sense to 
> use code with __builtin_smul_overflow.  I'll do the changes.
>
>
Here is one more patch I've committed.  Jakub, thank your for the 
discussion and your patience.