From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 101240 invoked by alias); 18 Dec 2015 20:19:46 -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 101228 invoked by uid 89); 18 Dec 2015 20:19:46 -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=H*r:May, Hx-languages-length:2241, HContent-type:windows-1252, HContent-transfer-encoding:7bit X-HELO: mailout2.w1.samsung.com Received: from mailout2.w1.samsung.com (HELO mailout2.w1.samsung.com) (210.118.77.12) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Fri, 18 Dec 2015 20:19:44 +0000 Received: from eucpsbgm2.samsung.com (unknown [203.254.199.245]) by mailout2.w1.samsung.com (Oracle Communications Messaging Server 7.0.5.31.0 64bit (built May 5 2014)) with ESMTP id <0NZK00AM4LSSQ000@mailout2.w1.samsung.com> for gcc-patches@gcc.gnu.org; Fri, 18 Dec 2015 20:19:40 +0000 (GMT) Received: from eusync2.samsung.com ( [203.254.199.212]) by eucpsbgm2.samsung.com (EUCPMTA) with SMTP id 4E.FB.21385.B5A64765; Fri, 18 Dec 2015 20:19:39 +0000 (GMT) Received: from [106.109.9.145] by eusync2.samsung.com (Oracle Communications Messaging Server 7.0.5.31.0 64bit (built May 5 2014)) with ESMTPA id <0NZK00HPELSR4JA0@eusync2.samsung.com>; Fri, 18 Dec 2015 20:19:39 +0000 (GMT) Subject: Re: [PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp To: Richard Biener References: <5672787D.6040105@samsung.com> <56727A5A.1070200@samsung.com> <5672AB99.6090209@samsung.com> Cc: GCC Patches , Cong Hou , Yuri Gribov From: Yury Gribov Message-id: <56746A70.7080802@samsung.com> Date: Fri, 18 Dec 2015 20:19: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: Content-type: text/plain; charset=windows-1252; format=flowed Content-transfer-encoding: 7bit X-IsSubscribed: yes X-SW-Source: 2015-12/txt/msg01926.txt.bz2 On 12/17/2015 03:51 PM, Richard Biener wrote: > On Thu, 17 Dec 2015, Yury Gribov wrote: > >> On 12/17/2015 02:57 PM, Richard Biener wrote: >>> On Thu, 17 Dec 2015, Yury Gribov wrote: >>> >>>> That's an interesting one. The original comparison function assumes that >>>> operand_equal_p(a,b) is true iff compare_tree(a, b) == 0. >>>> Unfortunately that's not true (functions are written by different >>>> authors). >>>> >>>> This causes subtle violation of transitiveness. >>>> >>>> I believe removing operand_equal_p should preserve the intended semantics >>>> (same approach taken in another comparison function in this file - >>>> comp_dr_with_seg_len_pair). >>>> >>>> Cc-ing Cong Hou and Richard who are the authours. >>> >>> I don't think the patch is good. compare_tree really doesn't expect >>> equal elements (and it returning zero is bad or a bug). >> >> Hm but that's how it's used in other comparator in this file >> (comp_dr_with_seg_len_pair). > > But for sure > > switch (code) > { > /* For const values, we can just use hash values for comparisons. */ > case INTEGER_CST: > case REAL_CST: > case FIXED_CST: > case STRING_CST: > case COMPLEX_CST: > case VECTOR_CST: > { > hashval_t h1 = iterative_hash_expr (t1, 0); > hashval_t h2 = iterative_hash_expr (t2, 0); > if (h1 != h2) > return h1 < h2 ? -1 : 1; > break; > } > > doesn't detect un-equality correctly (it assumes the hash is > collision-free). > > Also note that operator== of dr_with_seg_len again also uses > operand_equal_p (plus compare_tree). > > IMHO compare_tree should be cleaned up with respect to what > trees we expect here (no REAL_CSTs for example) and properly > do comparisons. > >>> But it's also >>> "lazy" in that it will return 0 when it hopes a further disambiguation >>> inside dr_group_sort_cmp on a different field will eventually lead to >>> a non-zero compare_tree. >>> >>> So eventually if compare_tree returns zero we have to fall back to the >>> final disambiguator using gimple_uid. >>> >>> That said, I'd like to see the testcase where you observe an >>> intransitive comparison. >> >> Let me dig my debugging logs (I'll send detailed repro tomorrow). Added home address.