From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 79757 invoked by alias); 8 Jan 2016 08:23:16 -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 79733 invoked by uid 89); 8 Jan 2016 08:23:15 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.3 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_LOW,RP_MATCHES_RCVD,SPF_PASS autolearn=ham version=3.3.2 spammy=mad, hashval_t, violation, yuri X-HELO: mx2.suse.de Received: from mx2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Fri, 08 Jan 2016 08:23:13 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 3A672ABBB; Fri, 8 Jan 2016 08:23:09 +0000 (UTC) Date: Fri, 08 Jan 2016 08:23:00 -0000 From: Richard Biener To: Yuri Gribov cc: Yury Gribov , GCC Patches , Cong Hou Subject: Re: [PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp In-Reply-To: Message-ID: References: <5672787D.6040105@samsung.com> <56727A5A.1070200@samsung.com> <5672AB99.6090209@samsung.com> <56746A70.7080802@samsung.com> User-Agent: Alpine 2.11 (LSU 23 2013-08-11) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-SW-Source: 2016-01/txt/msg00381.txt.bz2 On Sat, 19 Dec 2015, 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). Yeah, I agree with that. But I don't agree with your simple fix. Can you please file a bugreport about this issue so we can track it and work on it for GCC 7? I believe that compare_tree needs to handle the equality case "properly". Thanks, Richard.