From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 125508 invoked by alias); 4 Sep 2018 14:25:54 -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 125493 invoked by uid 89); 4 Sep 2018 14:25:53 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-25.8 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.2 spammy= X-HELO: mail-wr1-f46.google.com Received: from mail-wr1-f46.google.com (HELO mail-wr1-f46.google.com) (209.85.221.46) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 04 Sep 2018 14:25:51 +0000 Received: by mail-wr1-f46.google.com with SMTP id w11-v6so4201345wrc.5 for ; Tue, 04 Sep 2018 07:25:50 -0700 (PDT) Return-Path: Received: from abulafia.quesejoda.com (247.red-79-147-188.dynamicip.rima-tde.net. [79.147.188.247]) by smtp.gmail.com with ESMTPSA id 60-v6sm23558265wre.82.2018.09.04.07.25.47 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 04 Sep 2018 07:25:47 -0700 (PDT) Subject: Re: VRP: abstract out wide int CONVERT_EXPR_P code To: Richard Biener Cc: GCC Patches References: <30744ab3-510b-fc67-ad59-906fd54c50cf@redhat.com> From: Aldy Hernandez Message-ID: <8ef6498d-b299-a64c-80d4-8d245b304e54@redhat.com> Date: Tue, 04 Sep 2018 14:25:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 In-Reply-To: Content-Type: multipart/mixed; boundary="------------C169220B28CC7096ADC7D4C6" X-IsSubscribed: yes X-SW-Source: 2018-09/txt/msg00194.txt.bz2 This is a multi-part message in MIME format. --------------C169220B28CC7096ADC7D4C6 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Content-length: 7533 On 09/04/2018 10:20 AM, Richard Biener wrote: > On Tue, Sep 4, 2018 at 4:12 PM Aldy Hernandez wrote: >> >> >> >> On 09/04/2018 08:49 AM, Richard Biener wrote: >>> On Tue, Sep 4, 2018 at 2:41 PM Aldy Hernandez wrote: >>>> >>>> >>>> >>>> On 09/04/2018 07:58 AM, Richard Biener wrote: >>>>> On Mon, Sep 3, 2018 at 1:32 PM Aldy Hernandez wrote: >>>>>> >>>>>> >>>>>> >>>>>> On 08/28/2018 05:27 AM, Richard Biener wrote: >>>>>>> On Mon, Aug 27, 2018 at 2:24 PM Aldy Hernandez wrote: >>>>>>>> >>>>>>>> Howdy! >>>>>>>> >>>>>>>> Phew, I think this is the last abstraction. This handles the unary >>>>>>>> CONVERT_EXPR_P code. >>>>>>>> >>>>>>>> It's the usual story-- normalize the symbolics to [-MIN,+MAX] and handle >>>>>>>> everything generically. >>>>>>>> >>>>>>>> Normalizing the symbolics brought about some nice surprises. We now >>>>>>>> handle a few things we were punting on before, which I've documented in >>>>>>>> the patch, but can remove if so desired. I wrote them mainly for myself: >>>>>>>> >>>>>>>> /* NOTES: Previously we were returning VARYING for all symbolics, but >>>>>>>> we can do better by treating them as [-MIN, +MAX]. For >>>>>>>> example, converting [SYM, SYM] from INT to LONG UNSIGNED, >>>>>>>> we can return: ~[0x8000000, 0xffffffff7fffffff]. >>>>>>>> >>>>>>>> We were also failing to convert ~[0,0] from char* to unsigned, >>>>>>>> instead choosing to return VR_VARYING. Now we return ~[0,0]. */ >>>>>>>> >>>>>>>> Tested on x86-64 by the usual bootstrap and regtest gymnastics, >>>>>>>> including --enable-languages=all, because my past sins are still >>>>>>>> haunting me. >>>>>>>> >>>>>>>> OK? >>>>>>> >>>>>>> The new wide_int_range_convert_tree looks odd given it returns >>>>>>> tree's. I'd have expected an API that does the conversion resulting >>>>>>> in a wide_int range and the VRP code adapting to that by converting >>>>>>> the result to trees. >>>>>> >>>>>> Rewritten as suggested. >>>>>> >>>>>> A few notes. >>>>>> >>>>>> First. I am not using widest_int as was done previously. We were >>>>>> passing 0/false to the overflow args in force_fit_type so the call was >>>>>> just degrading into wide_int_to_tree() anyhow. Am I missing some >>>>>> subtlety here, and must we use widest_int and then force_fit_type on the >>>>>> caller? >>>>> >>>>> The issue is that the wide-ints get "converted", so it's indeed subtle. >>>> >>>> This seems like it should be documented-- at the very least in >>>> wide_int_range_convert. >>> >>> I don't think you need it there. >>> >>>> What do you mean "converted"? I'd like to understand this better before >>>> I write out the comment :). Do we lose precision by keeping it in a >>>> wide_int as opposed to a widest_int? >>> >>> As you're using wide_int::from that "changes" precision now. >> >> Ah, so it's wide_int_to_tree that wants to see the widest precision. I see. > > I honestly don't remember exactly but I suppose precision mismatched somehow. > > Your code was OK with not using widest_ints. > >>> >>>> Also, can we have the caller to wide_int_range_convert() use >>>> wide_int_to_tree directly instead of passing through force_fit_type? >>> >>> I think so. >>> >>>> It >>>> seems force_fit_type with overflowable=0 and overflowed=false is just a >>>> call to wide_int_to_tree anyhow. >>>> >>>>> >>>>> + || wi::rshift (wi::sub (vr0_max, vr0_min), >>>>> + wi::uhwi (outer_prec, inner_prec), >>>>> + inner_sign) == 0) >>>>> >>>>> this was previously allowed only for VR_RANGEs - now it's also for >>>>> VR_ANTI_RANGE. >>>>> That looks incorrect. Testcase welcome ;) >>>> >>>> See change to extract_range_into_wide_ints. VR_ANTI_RANGEs of constants >>>> will remain as is, whereas VR_ANTI_RANGEs of symbols will degrade into >>>> [-MIN,+MAX] and be handled generically. >>>> >>>> Also, see comment: >>>> >>>> + /* We normalize everything to a VR_RANGE, but for constant >>>> + anti-ranges we must handle them by leaving the final result >>>> + as an anti range. This allows us to convert things like >>>> + ~[0,5] seamlessly. */ >>> >>> Yes, but for truncation of ~[0, 5] from say int to short it's not correct >>> to make the result ~[0, 5], is it? At least the original code dropped >>> that to VARYING. For the same reason truncating [3, 765] from >>> short to unsigned char isn't [3, 253]. But maybe I'm missing something. >> >> Correct, but in that case we will realize that in wide_int_range_convert >> and refuse to do the conversion: >> >> /* If the conversion is not truncating we can convert the min and >> max values and canonicalize the resulting range. Otherwise we >> can do the conversion if the size of the range is less than what >> the precision of the target type can represent. */ >> if (outer_prec >= inner_prec >> || wi::rshift (wi::sub (vr0_max, vr0_min), >> wi::uhwi (outer_prec, inner_prec), >> inner_sign) == 0) > > so you say the check is also sufficient for all anti-ranges? I see the > current VRP code does canonicalization to ranges before running into > the CONVERT_EXPR_CODE case. > >>> >>>>> >>>>> + return (!wi::eq_p (min, wi::min_value (outer_prec, outer_sign)) >>>>> + || !wi::eq_p (max, wi::max_value (outer_prec, outer_sign))); >>>>> >>>>> so you return false for VARYING? Why? I'd simply return true and >>>>> return VARYING in the new type in the path you return false. >>>> >>>> Since symbols and VR_VARYING and other things get turned into a >>>> [-MIN,+MAX] by extract_range_into_wide_ints, it's a lot easier to handle >>>> things generically and return varying when the range spans the entire >>>> domain. It also keeps with the rest of the wide_int_range_* functions >>>> that return false when we know it's going to be VR_VARYING. >>> >>> Ah, OK, didn't know they did that. Not sure if that's convenient though >>> given VR_VARYING has no representation in the wide-int-range "range" >>> so callers chaining ops would need to do sth like >>> >>> if (!wide_int_range_* (...., &out_min, &out_max)) >>> { >>> out_min = wide_int::min (prec); >>> out_max = wide_int::max (prec); >>> } >>> if (!wide_int_range_* (out_min, out_max, ....)) >>> ... >>> >>> to not lose cases where VARYING inputs produce non-VARYING results? >> >> Well in the ssa-range branch we treat [-MIN,+MAX] as varying. We call >> it range_for_type(). > > Sure. But out_min/max is uninitialized when the functions return false? > >> Also, the above if(!wide_int_range*) chaining is not necessary in the >> ssa-range work. See op_wi() in range-op.c. We just return false and >> the caller loop takes care of things. > > I see. I'm still trying to view the wide-int-range.{cc,h} stuff as a generally > useful API rather than just factored out "stuff" to be used by VRP and > range-op.c ... > > Anyhow, let's go with your original patch. I assume you mean with my original patch but using widest_int instead of wide_int, because of the subtlety mentioned? If so, that's the patch I just attached (and am doing so again for the record). Please let me know and I will commit. > > I hope I can spend some time going over wide-int-range.{cc,h} and sanitizing > its interface (yeah, didn't forget the class thing ... maybe tomorrow > before I leave ;)) Thanks. I appreciate your comments. Aldy --------------C169220B28CC7096ADC7D4C6 Content-Type: text/x-patch; name="curr.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="curr.patch" Content-length: 6809 gcc/ * wide-int-range.cc (wide_int_range_convert): New. * wide-int-range.h (wide_int_range_convert): New. * tree-vrp.c (extract_range_from_unary_expr): Abstract wide int code into wide_int_range_convert. (extract_range_into_wide_ints): Do not munge anti range constants into the entire domain. Just return the range back. diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index d29a2c9b507..2a3797e7f24 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -995,7 +995,7 @@ ranges_from_anti_range (const value_range *ar, /* Extract the components of a value range into a pair of wide ints in [WMIN, WMAX]. - If the value range is anything but a VR_RANGE of constants, the + If the value range is anything but a VR_*RANGE of constants, the resulting wide ints are set to [-MIN, +MAX] for the type. */ static void inline @@ -1003,7 +1003,10 @@ extract_range_into_wide_ints (const value_range *vr, signop sign, unsigned prec, wide_int &wmin, wide_int &wmax) { - if (range_int_cst_p (vr)) + if ((vr->type == VR_RANGE + || vr->type == VR_ANTI_RANGE) + && TREE_CODE (vr->min) == INTEGER_CST + && TREE_CODE (vr->max) == INTEGER_CST) { wmin = wi::to_wide (vr->min); wmax = wi::to_wide (vr->max); @@ -1850,44 +1853,42 @@ extract_range_from_unary_expr (value_range *vr, return; } - /* If VR0 is varying and we increase the type precision, assume - a full range for the following transformation. */ - if (vr0.type == VR_VARYING - && INTEGRAL_TYPE_P (inner_type) - && TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type)) - { - vr0.type = VR_RANGE; - vr0.min = TYPE_MIN_VALUE (inner_type); - vr0.max = TYPE_MAX_VALUE (inner_type); - } - - /* If VR0 is a constant range or anti-range and the conversion is - not truncating we can convert the min and max values and - canonicalize the resulting range. Otherwise we can do the - conversion if the size of the range is less than what the - precision of the target type can represent and the range is - not an anti-range. */ - if ((vr0.type == VR_RANGE - || vr0.type == VR_ANTI_RANGE) + /* We normalize everything to a VR_RANGE, but for constant + anti-ranges we must handle them by leaving the final result + as an anti range. This allows us to convert things like + ~[0,5] seamlessly. */ + value_range_type vr_type = VR_RANGE; + if (vr0.type == VR_ANTI_RANGE && TREE_CODE (vr0.min) == INTEGER_CST - && TREE_CODE (vr0.max) == INTEGER_CST - && (TYPE_PRECISION (outer_type) >= TYPE_PRECISION (inner_type) - || (vr0.type == VR_RANGE - && integer_zerop (int_const_binop (RSHIFT_EXPR, - int_const_binop (MINUS_EXPR, vr0.max, vr0.min), - size_int (TYPE_PRECISION (outer_type))))))) + && TREE_CODE (vr0.max) == INTEGER_CST) + vr_type = VR_ANTI_RANGE; + + /* NOTES: Previously we were returning VARYING for all symbolics, but + we can do better by treating them as [-MIN, +MAX]. For + example, converting [SYM, SYM] from INT to LONG UNSIGNED, + we can return: ~[0x8000000, 0xffffffff7fffffff]. + + We were also failing to convert ~[0,0] from char* to unsigned, + instead choosing to return VR_VARYING. Now we return ~[0,0]. */ + wide_int vr0_min, vr0_max; + widest_int wmin, wmax; + signop inner_sign = TYPE_SIGN (inner_type); + signop outer_sign = TYPE_SIGN (outer_type); + unsigned inner_prec = TYPE_PRECISION (inner_type); + unsigned outer_prec = TYPE_PRECISION (outer_type); + extract_range_into_wide_ints (&vr0, inner_sign, inner_prec, + vr0_min, vr0_max); + if (wide_int_range_convert (wmin, wmax, + inner_sign, inner_prec, + outer_sign, outer_prec, + vr0_min, vr0_max)) { - tree new_min, new_max; - new_min = force_fit_type (outer_type, wi::to_widest (vr0.min), - 0, false); - new_max = force_fit_type (outer_type, wi::to_widest (vr0.max), - 0, false); - set_and_canonicalize_value_range (vr, vr0.type, - new_min, new_max, NULL); - return; + tree min = wide_int_to_tree (outer_type, wmin); + tree max = wide_int_to_tree (outer_type, wmax); + set_and_canonicalize_value_range (vr, vr_type, min, max, NULL); } - - set_value_range_to_varying (vr); + else + set_value_range_to_varying (vr); return; } else if (code == ABS_EXPR) diff --git a/gcc/wide-int-range.cc b/gcc/wide-int-range.cc index 04d391b33d5..aa25b88b982 100644 --- a/gcc/wide-int-range.cc +++ b/gcc/wide-int-range.cc @@ -735,6 +735,42 @@ wide_int_range_abs (wide_int &min, wide_int &max, return true; } +/* Convert range in [VR0_MIN, VR0_MAX] with INNER_SIGN and INNER_PREC, + to a widest_int range in [MIN, MAX] with OUTER_SIGN and OUTER_PREC. + + Return TRUE if we were able to successfully calculate the new range. + + Caller is responsible for canonicalizing the resulting range. */ + +bool +wide_int_range_convert (widest_int &min, widest_int &max, + signop inner_sign, + unsigned inner_prec, + signop outer_sign, + unsigned outer_prec, + const wide_int &vr0_min, + const wide_int &vr0_max) +{ + /* If the conversion is not truncating we can convert the min and + max values and canonicalize the resulting range. Otherwise we + can do the conversion if the size of the range is less than what + the precision of the target type can represent. */ + if (outer_prec >= inner_prec + || wi::rshift (wi::sub (vr0_max, vr0_min), + wi::uhwi (outer_prec, inner_prec), + inner_sign) == 0) + { + min = widest_int::from (vr0_min, inner_sign); + max = widest_int::from (vr0_max, inner_sign); + widest_int min_value + = widest_int::from (wi::min_value (outer_prec, outer_sign), outer_sign); + widest_int max_value + = widest_int::from (wi::max_value (outer_prec, outer_sign), outer_sign); + return !wi::eq_p (min, min_value) || !wi::eq_p (max, max_value); + } + return false; +} + /* Calculate a division operation on two ranges and store the result in [WMIN, WMAX] U [EXTRA_MIN, EXTRA_MAX]. diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h index eaf47bca449..d0efd5ca694 100644 --- a/gcc/wide-int-range.h +++ b/gcc/wide-int-range.h @@ -109,6 +109,13 @@ extern bool wide_int_range_abs (wide_int &min, wide_int &max, const wide_int &vr0_min, const wide_int &vr0_max, bool overflow_undefined); +extern bool wide_int_range_convert (widest_int &min, widest_int &max, + signop inner_sign, + unsigned inner_prec, + signop outer_sign, + unsigned outer_prec, + const wide_int &vr0_min, + const wide_int &vr0_max); extern bool wide_int_range_div (wide_int &wmin, wide_int &wmax, enum tree_code code, signop sign, unsigned prec, --------------C169220B28CC7096ADC7D4C6--