From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id 8D5E13858C30 for ; Wed, 1 Mar 2023 10:12:05 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 8D5E13858C30 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 8C5F41FE16; Wed, 1 Mar 2023 10:12:04 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1677665524; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=4Yox9dTX5fXXEcbjag8o2Ax85r+T10tiuKPJzSL7gGM=; b=n2UDfhjpX+5orYy5eNeEDhCV5H5fiuIarEPe6T9WcTRuclkYej1bJG112stwZ7x72QSh2u f+Q9rghekGiF6NQsvcOEr9DyPwImV6TLzLwOEbTtswBbBbv8b0p1A7yWKdSbd92HZRXrCw VezoxbglcotRGmnDEFUsWTU7x9e7RLc= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1677665524; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=4Yox9dTX5fXXEcbjag8o2Ax85r+T10tiuKPJzSL7gGM=; b=sWzz5k+WZYgV9vRXQxoOhr7YGQGf2EaH3oVoCsn5LE1JErV0IWCq9UWoPggimbTit1LkX+ XwS9/lhHSOsOpeBQ== Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id 7F4532C141; Wed, 1 Mar 2023 10:12:04 +0000 (UTC) Date: Wed, 1 Mar 2023 10:12:04 +0000 (UTC) From: Richard Biener To: Aldy Hernandez cc: gcc-patches@gcc.gnu.org, Andrew MacLeod Subject: Re: [PATCH] Fixup possible VR_ANTI_RANGE value_range issues In-Reply-To: Message-ID: References: <09219.123022708581201997@us-mta-652.us.mimecast.lan> <98102d74-cb30-0190-af66-86800e0721e4@redhat.com> User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Spam-Status: No, score=-5.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Wed, 1 Mar 2023, Aldy Hernandez wrote: > > > On 2/28/23 10:41, Richard Biener wrote: > > On Mon, 27 Feb 2023, Aldy Hernandez wrote: > > > >> > >> > >> On 2/27/23 14:58, Richard Biener wrote: > >>> After fixing PR107561 the following avoids looking at VR_ANTI_RANGE > >>> ranges where it doesn't seem obvious the code does the correct > >>> thing here (lower_bound and upper_bound do not work as expected). > >> > >> I do realize there's some confusion here, and some of it is my fault. This > >> has > >> become obvious in my upcoming work removing all of legacy. > >> > >> What's going on is that ultimately min/max are broken with (non-legacy) > >> iranges. Or at the very least inconsistent between legacy and non-legacy. > >> These are left over from the legacy world, and have been marked DEPRECATED > >> for > >> a few releases, but the middle end warnings continued to use them and even > >> added new uses after they were obsoleted. > >> > >> min/max have different meanings depending on kind(), which is also > >> deprecated, > >> btw. They are the underlying min/max fields from the legacy > >> implementation, > >> and thus somewhat leak the implementation details. Unfortunately, they are > >> being called from non-legacy code which is ignoring the kind() field. > >> > >> In retrospect I should've converted everything away from min/max/kind years > >> ago, or at the very least converted min/max to work with non-legacy more > >> consistently. > >> > >> For the record: > >> > >> enum value_range_kind kind () const; // DEPRECATED > >> tree min () const; // DEPRECATED > >> tree max () const; // DEPRECATED > >> bool symbolic_p () const; // DEPRECATED > >> bool constant_p () const; // DEPRECATED > >> void normalize_symbolics (); // DEPRECATED > >> void normalize_addresses (); // DEPRECATED > >> bool may_contain_p (tree) const; // DEPRECATED > >> bool legacy_verbose_union_ (const class irange *); // DEPRECATED > >> bool legacy_verbose_intersect (const irange *); // DEPRECATED > >> > >> In my local branch I tried converting all the middle-end legacy API uses to > >> the new API, but a bunch of tests started failing, and lots more false > >> positives started showing up in correct code. I suspect that's part of the > >> reason legacy continued to be used in these passes :-/. As you point out > >> in > >> the PR, the tests seem designed to test the current (at times broken) > >> implementation. > >> > >> That being said, the 5 fixes in your patch are not wrong to begin with, > >> because all uses guard lower_bound() and upper_bound() which work > >> correctly. > >> They return the lowest and uppermost possible bound for the range (ignoring > >> the underlying implementation). So, the lower bound of a signed non-zero > >> is > >> -INF because ~[0,0] is really [-INF,-1][1,+INF]. In the min/max legacy > >> code, > >> min() of signed non-zero (~[0,0]) is 0. The new implementation has no > >> concept > >> of anti-ranges, and we don't leak any of that out. > >> > >> Any uses of min/max without looking at kind() are definitely broken. OTOH > >> uses > >> of lower/upper_bound are fine and should work with both legacy and > >> non-legacy. > >> > >> Unrelated, but one place where I haven't been able to convince myself that > >> the > >> use is correct is bounds_of_var_in_loop: > >> > >>> /* Check if init + nit * step overflows. Though we checked > >>> scev {init, step}_loop doesn't wrap, it is not enough > >>> because the loop may exit immediately. Overflow could > >>> happen in the plus expression in this case. */ > >>> if ((dir == EV_DIR_DECREASES > >>> && compare_values (maxvr.min (), initvr.min ()) != -1) > >>> || (dir == EV_DIR_GROWS > >>> && compare_values (maxvr.max (), initvr.max ()) != 1)) > >> > >> Ughh...this is all slated to go away, and I have patches removing all of > >> legacy and the old API. > >> > >> Does this help? Do you still think lower and upper bound are not working > >> as > >> expected? > > > > lower_bound/upper_bound work as expected, > > tree_lower_bound/tree_upper_bound do not. I've checked and all uses > > I "fixed" use lower_bound/upper_boud. > > > > tree_lower_bound & friends are 'protected', but in the above light the > > comment > > > > // potential promotion to public? > > > > looks dangerous (I was considering using them ...). > > First of all, my apologies for the time you've spent on this. This needed > cleaning up a few releases ago, but with legacy in place, it kept getting > pushed further away. This is my first order of business once stage1 opens. > That being said, thank you for spot checking this. > > It looks like tree_lower_bound was just syntactic sugar for m_base[pair * 2]. > The comment is likely wrong. It should've stayed protected, or nuked in favor > of accessing m_base directly to avoid confusion. > > > > > I'm dropping the patch, it's probably time to work on getting rid of > > 'value_range' uses (aka legacy_mode_p ()) and/or replace raw accesses > > to the min/max for that mode with m_base accesses? At least > > that there's tree_{upper,lower}_bound for pair != 0 suggests this > > function is used with differing semantics internally which is a > > My local tree has a few dozen patches removing legacy and converting the trees > to wide_int. In my work, legacy_mode_p, min, max, kind, tree_lower_bound, etc > are all gone. I can make the branch public if you like. > > > source of confusion (to me at least). tree_{lower,upper}_bound > > should be able to assert it's not a legacy mode range and > > min/max should be able to assert that it is. > > Agreed. One possible problem *may be* vr-values.cc which still uses min() and > max() throughout can be called on legacy as well as non-legacy. > > This unfortunately means that since kind/min/max will return different results > for legacy/non-legacy (kind() never returns VR_ANTI_RANGE for non-legacy), > simplify_using_ranges can theoretically give different results depending on > how it's called. In practice, only DOM/VRP call simplify_using_ranges and > always with non-legacy. However, simplify_using_ranges uses get_value_range() > internally which uses legacy. Sorry, I just realized this now while auditing > the code. > > I honestly have no idea if this matters in practice, and since this has been > this way for a few releases, I'm afraid of touching it so late in the cycle. > But I'm happy to help if you think it must be fixed in this release. > > Hmmmm, it looks like there are just a few non-legacy uses in vr-values.cc > (int_range<2> and int_range_max), and never in code paths checking > min/max/kind. So your suggestions about the asserts may be all we need, > dunno. > > > > > Btw, legacy_upper_bound looks wrong: > > > > if (m_kind == VR_ANTI_RANGE) > > { > > tree typ = type (), t; > > if (pair == 1 || vrp_val_is_min (min ())) > > t = vrp_val_max (typ); > > else > > t = wide_int_to_tree (typ, wi::to_wide (min ()) - 1); > > > > not sure what the pair == 1 case is about, but the upper bound > > of an anti-range is only special when max() is vrp_val_is_max, > > aka ~[low, +INF] where it then is low - 1, but the above checks > > for ~[-INF, high] and returns +INF in that case. That's correct > > unless high == +INF at least, but the else case is wrong for > > all high != +INF? > > An anti-range is really two pairs. So, ~[6,9] is really: > > [-MIN, 5][10, MAX] > > Pair 0 is [-MIN, 5] and pair 1 is [10, MAX]. This means that the upper bound > for the pair==1 case is just MAX. > > > > > I think it should be > > > > if (pair == 1 || !vrp_val_is_max (max ())) > > t = vrp_val_max (typ); > > else > > t = wide_int_to_tree (typ, wi::to_wide (min ()) - 1); > > > > no? > > I think both of us are wrong. The original vrp_val_is_min(min()) call will > always return false. And your !vrp_val_is_max(max()) is always true. This is > because irange::set() will normalize anti-ranges into a VR_RANGE when > possible, in order to avoid multiple representations for the same range: > > else if (is_min) > { > tree one = build_int_cst (TREE_TYPE (max), 1); > min = int_const_binop (PLUS_EXPR, max, one); > max = vrp_val_max (TREE_TYPE (max)); > kind = VR_RANGE; > } > else if (is_max) > { > tree one = build_int_cst (TREE_TYPE (min), 1); > max = int_const_binop (MINUS_EXPR, min, one); > min = vrp_val_min (TREE_TYPE (min)); > kind = VR_RANGE; > } > > So ~[-MIN,5] is represented as [6,MAX] and ~[5,+MAX] as [-MIN,4]. > > Ughhh... so it looks like legacy_upper_bound is correct, but the > vrp_val_is_min() check is useless. > > Am I missing something? Well, you are missing that VR_ANTI_RANGE only has a single pair in m_base[], so it's _not_ represented as [-MIN, 5][10, MAX]. So you say that for VR_ANTI_RANGE we should never ask for legacy_upper_bound (0) but always legaacy_upper_bound (1)? Btw, I didn't see in ::verify where we verify proper normalization so after some range ops it might be in non normalized form. That said - as this is all going away tampering with it looks less useful than ripping it out ... Anyway, see the series I posted which I ended up with in understanding the code. Appearantly I misunderstood the intent of the current state, mainly because of lack of documentation I guess :/ I do wonder if s/value_range/int_range<2>/ throughout most code is the correct thing to do and what the actual hurdles are in the end. Richard.