From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 83276 invoked by alias); 25 Dec 2015 11:42:00 -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 83263 invoked by uid 89); 25 Dec 2015 11:41:59 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=0.1 required=5.0 tests=AWL,BAYES_20,KAM_LAZY_DOMAIN_SECURITY,RP_MATCHES_RCVD,SPF_HELO_PASS autolearn=no version=3.3.2 spammy=$15, Yura, y.gribov@samsung.com, H*F:D*samsung.com 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, 25 Dec 2015 11:41:57 +0000 Received: from eucpsbgm1.samsung.com (unknown [203.254.199.244]) by mailout2.w1.samsung.com (Oracle Communications Messaging Server 7.0.5.31.0 64bit (built May 5 2014)) with ESMTP id <0NZW003VEWHSNY30@mailout2.w1.samsung.com> for gcc-patches@gcc.gnu.org; Fri, 25 Dec 2015 11:41:52 +0000 (GMT) Received: from eusync3.samsung.com ( [203.254.199.213]) by eucpsbgm1.samsung.com (EUCPMTA) with SMTP id 9B.D9.16778.08B2D765; Fri, 25 Dec 2015 11:41:52 +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 <0NZW000UBWHRGY10@eusync3.samsung.com>; Fri, 25 Dec 2015 11:41:52 +0000 (GMT) Subject: Re: [PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp To: Yuri Gribov References: <5672787D.6040105@samsung.com> <56727A5A.1070200@samsung.com> <5672AB99.6090209@samsung.com> <56746A70.7080802@samsung.com> Cc: Richard Biener , GCC Patches , Cong Hou From: Yury Gribov Message-id: <567D2B9F.9@samsung.com> Date: Fri, 25 Dec 2015 11:42: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/msg02141.txt.bz2 On 12/19/2015 01:30 AM, Yuri Gribov wrote: > On Fri, Dec 18, 2015 at 11:20 PM, Yury Gribov wrote: >> 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. > > Richard, > > I was doing my original testing on an older GCC (actually 4.9) and it > seems that this particular issue does not reproduce on current trunk. > But from what I can see the problem is still in the code which I'll > now try to explain. > > Here's the problem that was detected by the tool: > > (gdb) p dr_group_sort_cmp($dr1,$dr2) > $1 = -1 > (gdb) p dr_group_sort_cmp($dr2,$dr3) > $2 = -1 > (gdb) p dr_group_sort_cmp($dr1,$dr3) > $3 = 1 > > In other words, dr1 < dr2 and dr2 < dr3 but dr1 > dr3 (which is a > violation of transitivity axiom and will generally drive qsort mad). > Let's see why that happens. > > Comparison starts at base addresses which are > > (gdb) cal debug_generic_expr($ba1) > b_7(D) + (sizetype) i_69 * 4 > (gdb) cal debug_generic_expr($ba2) > a_12(D) + (sizetype) ((long unsigned int) i_69 * 4) > (gdb) cal debug_generic_expr($ba3) > b_7(D) + (sizetype) ((long unsigned int) i_69 * 4) > > Now here are results for operand_equals_p: > > (gdb) cal operand_equal_p($ba1,$ba2,0) > $1 = 0 > (gdb) cal operand_equal_p($ba2,$ba3,0) > $3 = 0 > > This means that to compare dr1 vs. dr2 and dr2 vs. dr3 we use compare_tree: > > (gdb) cal compare_tree($ba1,$ba2) > $4 = -1 > (gdb) cal compare_tree($ba2,$ba3) > $5 = -1 > > For dr1 vs. dr3 situation is more interesting. We continue with other checks > in dr_group_sort_cmp. Everything is equal: > > (gdb) p dr_equal_offsets_p(*$dr1,*$dr3) > $7 = true > (gdb) p $dr1.is_read > $9 = false > (gdb) p $dr3.is_read > $11 = false > (gdb) cal operand_equal_p($dr1.ref.typed.type.type_common.size_unit,$dr3.ref.typed.type.type_common.size_unit,0) > $15 = 1 > (gdb) cal operand_equal_p($dr1.innermost.step,$dr3.innermost.step,0) > $16 = 1 > > Until the very end where we compare initial values: > > (gdb) cal tree_int_cst_compare($dr1.innermost.init,$dr3.innermost.init,0) > $18 = 1 > > I think the core reason is probably that pattern that's used here i.e. > if(P(x,y)) > return cmp1(x,y); > return cmp2(x,y); > will in general not be a valid total ordering even if cmp1 or cmp2 are. > (In our case P = operand_equals_p, cmp1 = compare_tree, cmp2 = > tree_int_cst_compare). > > FTR I compiled the attached repro with 4.9.3 like this: > $ ./cc1plus -quiet -O2 -ftree-vectorize repro.i Richard, What's your call on this? Do you want a GCC6-relevant repro? /Yura