[PR103437,committed] IRA: Process multiplication overflow in priority calculation for allocno assignments
Message ID | 116e765c-ea89-47f4-600f-af115dd561c3@redhat.com |
---|---|
State | Committed |
Headers |
Return-Path: <gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org> X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 1D00E385BF81 for <patchwork@sourceware.org>; Thu, 2 Dec 2021 13:54:08 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 1D00E385BF81 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1638453248; bh=21zPi8Jq4MvSD6k/Gr3ZthGROV5uXpQ1th+Xjt5+dFI=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=queZs5NAPj6KIrEmhLp6YkLaptWE6EtH+4GrwPd2VnkVLRq4z0GnyMC0XJqWscacA V0JwehmEDuzN8FyJx51nn18QHaozAoTixS+fWuKwonQlHt2YnShXgUZSAKZzQYe/5t PdzflRq8ohSqiCgyY0oA3a0r7mRDrpMVVYgU5DNE= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id EEC87385840F for <gcc-patches@gcc.gnu.org>; Thu, 2 Dec 2021 13:53:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EEC87385840F Received: from mail-qk1-f199.google.com (mail-qk1-f199.google.com [209.85.222.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-381-Rt16YsFtNn-a7-AdHtebBQ-1; Thu, 02 Dec 2021 08:53:34 -0500 X-MC-Unique: Rt16YsFtNn-a7-AdHtebBQ-1 Received: by mail-qk1-f199.google.com with SMTP id br9-20020a05620a460900b0046ad784c791so37646902qkb.4 for <gcc-patches@gcc.gnu.org>; Thu, 02 Dec 2021 05:53:34 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent :content-language:to:from:subject; bh=FRKE2oZna5Onm4eG9sGjULLX8Y/B3tr3uyqQA1eWtNI=; b=1aSGODcNHJLOB2Rnk4fRosFg63ju0MazsE4pm50S2q69rYA7tpffBxzOPupHeA6YNu YXmf/TgyQhaZcJLm6ZQQpqiH55nSCrUNetsOeVOBpRRQRl2tDglAKfkE4wqKdqyMdYcP LkadNp6M065wyzGfAx1xCROJXbhsbVCGPmYNCZipLuxIA4kcCmXug6w+AtrwPxqZfYnO 9pDfzrRNvfFuN4pe8P7U2WvgkIGLn9jvGDPeuISiT5B5t6lsBPkCEGHDNOcmK/B2TJHm J1guqZVmoMjiTX+5XzDtzsdzouK8RyAFASBO8/WRinSEFYMsXRB8Az1x6fquRsLsaLvD FiVw== X-Gm-Message-State: AOAM532rFrjcJjWYK2VkeLhJDGe6JchJy6Tz9BV+gRrjdM01n79VPF0z 58WiD7B1MzHI7o6WCDFqajxrrnWP/n4U2VzoZpySSM3maHKWS21gA0tK/kWrvBAhxNcdGOwqPEX zs6yPFh0hjrCs+5izEiGBVjCKO/EPSVkLqNR8bEYt17wwBiuXJRNnQBYNhGFsoKHaatoNuQ== X-Received: by 2002:ad4:5bee:: with SMTP id k14mr12573700qvc.106.1638453213812; Thu, 02 Dec 2021 05:53:33 -0800 (PST) X-Google-Smtp-Source: ABdhPJxdZZ+pUZlpQN0YopW/w3AeSG7ioQykqe4gcCLP5Iw4U1XFShjseC12ITTaTXQQTiACxf31fg== X-Received: by 2002:ad4:5bee:: with SMTP id k14mr12573679qvc.106.1638453213557; Thu, 02 Dec 2021 05:53:33 -0800 (PST) Received: from [192.168.1.113] ([69.165.238.126]) by smtp.gmail.com with ESMTPSA id i7sm1569325qkn.0.2021.12.02.05.53.32 for <gcc-patches@gcc.gnu.org> (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 02 Dec 2021 05:53:32 -0800 (PST) Message-ID: <116e765c-ea89-47f4-600f-af115dd561c3@redhat.com> Date: Thu, 2 Dec 2021 08:53:31 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.1.0 To: "gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org> Subject: [PR103437] [committed] IRA: Process multiplication overflow in priority calculation for allocno assignments X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/mixed; boundary="------------PpUq0n8T5zGStgdroSHcmKOH" Content-Language: en-US X-Spam-Status: No, score=-13.2 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list <gcc-patches.gcc.gnu.org> List-Unsubscribe: <https://gcc.gnu.org/mailman/options/gcc-patches>, <mailto:gcc-patches-request@gcc.gnu.org?subject=unsubscribe> List-Archive: <https://gcc.gnu.org/pipermail/gcc-patches/> List-Post: <mailto:gcc-patches@gcc.gnu.org> List-Help: <mailto:gcc-patches-request@gcc.gnu.org?subject=help> List-Subscribe: <https://gcc.gnu.org/mailman/listinfo/gcc-patches>, <mailto:gcc-patches-request@gcc.gnu.org?subject=subscribe> From: Vladimir Makarov via Gcc-patches <gcc-patches@gcc.gnu.org> Reply-To: Vladimir Makarov <vmakarov@redhat.com> Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" <gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org> |
Series |
[PR103437,committed] IRA: Process multiplication overflow in priority calculation for allocno assignments
|
|
Commit Message
Vladimir Makarov
Dec. 2, 2021, 1:53 p.m. UTC
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.
Comments
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.
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) + || 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)