From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 9796 invoked by alias); 18 Dec 2015 19:50:29 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 9787 invoked by uid 89); 18 Dec 2015 19:50:29 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.9 required=5.0 tests=AWL,BAYES_00,KAM_LAZY_DOMAIN_SECURITY,SPF_HELO_PASS,T_RP_MATCHES_RCVD autolearn=no version=3.3.2 spammy=Submitted, H*r:May, Hx-languages-length:1499, HContent-transfer-encoding:7bit X-HELO: mailout4.w1.samsung.com Received: from mailout4.w1.samsung.com (HELO mailout4.w1.samsung.com) (210.118.77.14) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Fri, 18 Dec 2015 19:50:27 +0000 Received: from eucpsbgm1.samsung.com (unknown [203.254.199.244]) by mailout4.w1.samsung.com (Oracle Communications Messaging Server 7.0.5.31.0 64bit (built May 5 2014)) with ESMTP id <0NZK003DVKFZN700@mailout4.w1.samsung.com> for gcc-patches@gcc.gnu.org; Fri, 18 Dec 2015 19:50:23 +0000 (GMT) Received: from eusync3.samsung.com ( [203.254.199.213]) by eucpsbgm1.samsung.com (EUCPMTA) with SMTP id 6F.17.16778.F7364765; Fri, 18 Dec 2015 19:50:23 +0000 (GMT) Received: from [106.109.9.145] by eusync3.samsung.com (Oracle Communications Messaging Server 7.0.5.31.0 64bit (built May 5 2014)) with ESMTPA id <0NZK00CMXKFYKD80@eusync3.samsung.com>; Fri, 18 Dec 2015 19:50:23 +0000 (GMT) Subject: Re: [PATCH 3/5] "Fix" intransitive comparison in reload_pseudo_compare_func To: Vladimir Makarov , GCC Patches References: <5672787D.6040105@samsung.com> <567279C9.4080707@samsung.com> <56730EA6.5020508@redhat.com> From: Yury Gribov Message-id: <56746393.8030504@samsung.com> Date: Fri, 18 Dec 2015 19:50:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.4.0 MIME-version: 1.0 In-reply-to: <56730EA6.5020508@redhat.com> Content-type: text/plain; charset=utf-8; format=flowed Content-transfer-encoding: 7bit X-IsSubscribed: yes X-SW-Source: 2015-12/txt/msg01918.txt.bz2 On 12/17/2015 10:36 PM, Vladimir Makarov wrote: > On 12/17/2015 04:00 AM, Yury Gribov wrote: >> This patch fixes intransitive comparison in >> reload_pseudo_compare_func. Imagine the following >> situation: >> 1) bitmap_bit_p is unset for A and B but set for C >> 2) A < B (due to early ira_reg_class_max_nregs comparison) >> 3) B < C (due to following regno_assign_info comparison) >> >> It may then easily happen that A > C (due to regno_assign_info >> comparison) which violates the transitiveness requirement of total >> ordering. >> >> Unfortunately I'm not sure how to properly fix this so Cc-ing Vladimir >> for help. >> > Yury, thanks for reporting this. Yes that could be a problem but I > can not approve this patch as it might result in *significant* > performance degradation. I remember the code. What you propose is the > original patch (PR57878) and it was exactly modified to the current > version because of the negative performance impact. The current code is > safe although it might result into infinite cycling for some sort > algorithms but not for used qsort. > > I'll think how to fix it better. Probably I will need two comparison > functions for different assignment iterations. The solution will need > benchmarking as the code is critical for LRA performance. Could you > fill a bug report in order not to forget the issue. Thanks! Submitted https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68988