From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qv1-xf41.google.com (mail-qv1-xf41.google.com [IPv6:2607:f8b0:4864:20::f41]) by sourceware.org (Postfix) with ESMTPS id 63A553857C41 for ; Thu, 6 Aug 2020 19:31:00 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 63A553857C41 Received: by mail-qv1-xf41.google.com with SMTP id x7so6725490qvi.5 for ; Thu, 06 Aug 2020 12:31:00 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=t+LF5zIa1pO6JKyYZCMP3klwgztjPD4HpbqTyJhox7Q=; b=hi5MItzFcOQzUbYhpw5Zu3XpIW2/MH61OANzVk26EIS6vYpLyDiZrAVQgE7xu43rDh QQC+Tb/y7u0nj5Do+ZK5jhNikvHkPae4/k0+7+CX/x+dBVFXTl8AALpJDsbwD+WarLun eYSv8pE0E5jLs9JhuIEwXO97ox8iE9RrZAvHvJH1+FbPvUKYGwWYoIIwYQsmSSEVhSVh WEsAXm/KWLcv48+xRai0a20VfqiduNMNR4/Bx5Vwe8HavKxAQ90MZ6pMmgc28BwWEXop w+hHHb+S4BD6mJ6upbpl72k9J2JkSjpGmmUujZ/8YuWP0a5b0a4ucvyl0EnjE64i7S/1 dAfA== X-Gm-Message-State: AOAM533NuRnA0SJrVr8fx17soNrRdqD5D1GNWeUEgyUCJ9rEIrVrn9rl DHxQZY8HUsetMpbw3GFiCYtCs2IO X-Google-Smtp-Source: ABdhPJyIn4xVaQ+Y114LcjyTC/ATZaited9Em7P2zcdww3L+hEGhi9p3vzJHe3uFGM9MOzX3OUC0Dg== X-Received: by 2002:ad4:560f:: with SMTP id ca15mr5663828qvb.144.1596742259748; Thu, 06 Aug 2020 12:30:59 -0700 (PDT) Received: from [192.168.0.41] (184-96-226-5.hlrn.qwest.net. [184.96.226.5]) by smtp.gmail.com with ESMTPSA id o21sm4747734qkk.94.2020.08.06.12.30.58 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 06 Aug 2020 12:30:59 -0700 (PDT) Subject: Re: [PATCH] Rewrite get_size_range for irange API. To: Aldy Hernandez , gcc-patches@gcc.gnu.org Cc: msebor@redhat.com References: <20200806145350.864962-1-aldyh@redhat.com> From: Martin Sebor Message-ID: <790f18b6-c75f-e91b-3ea5-087a38f67b54@gmail.com> Date: Thu, 6 Aug 2020 13:30:58 -0600 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1 MIME-Version: 1.0 In-Reply-To: <20200806145350.864962-1-aldyh@redhat.com> Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-10.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 06 Aug 2020 19:31:02 -0000 On 8/6/20 8:53 AM, Aldy Hernandez via Gcc-patches wrote: > [Martin, does this sound reasonable to you?] It mostly makes sense to me except one part: > > The following patch converts get_size_range to the irange API, thus > removing the use of VR_ANTI_RANGE. > > This was a bit tricky because of the gymnastics we do in get_size_range > to ignore negatives and all that. I didn't convert the function for > multi-ranges. The code still returns a pair of trees indicating the > massaged range. But I do believe the code is cleaner and smaller. > > I'm not sure the current code (or my adaptation) gets all cases, but > the goal was to keep to the existing functionality, nothing more. > > OK? > > gcc/ChangeLog: > > * calls.c (range_remove_non_positives): New. > (set_bounds_from_range): New. > (get_size_range): Rewrite for irange API. > * tree-affine.c (expr_to_aff_combination): Call determine_value_range > with a range. > * tree-vrp.c (determine_value_range_1): Rename to... > (determine_value_range): ...this. > * tree-vrp.h (determine_value_range): Adjust prototype. > --- > gcc/calls.c | 139 ++++++++++++++++++---------------------------- > gcc/tree-affine.c | 5 +- > gcc/tree-vrp.c | 44 ++++++--------- > gcc/tree-vrp.h | 2 +- > 4 files changed, 73 insertions(+), 117 deletions(-) > > diff --git a/gcc/calls.c b/gcc/calls.c > index 44401e6350d..4aeeb36a2be 100644 > --- a/gcc/calls.c > +++ b/gcc/calls.c > @@ -57,6 +57,7 @@ along with GCC; see the file COPYING3. If not see > #include "attribs.h" > #include "builtins.h" > #include "gimple-fold.h" > +#include "range.h" > > /* Like PREFERRED_STACK_BOUNDARY but in units of bytes, not bits. */ > #define STACK_BYTES (PREFERRED_STACK_BOUNDARY / BITS_PER_UNIT) > @@ -1237,6 +1238,31 @@ alloc_max_size (void) > return alloc_object_size_limit; > } > > +// Remove non-positive numbers from a range. ALLOW_ZERO is TRUE if 0 > +// is considered positive. > + > +static void > +range_remove_non_positives (irange *vr, bool allow_zero) > +{ > + tree floor, type = vr->type (); > + if (allow_zero) > + floor = build_zero_cst (type); > + else > + floor = build_one_cst (type); > + value_range positives (floor, TYPE_MAX_VALUE (type)); > + vr->intersect (positives); > +} > + > +// Set the extreme bounds of range VR into range[]. > + > +static bool > +set_bounds_from_range (const irange *vr, tree range[2]) > +{ > + range[0] = wide_int_to_tree (vr->type (), vr->lower_bound ()); > + range[1] = wide_int_to_tree (vr->type (), vr->upper_bound ()); > + return true; > +} > + > /* Return true when EXP's range can be determined and set RANGE[] to it > after adjusting it if necessary to make EXP a represents a valid size > of object, or a valid size argument to an allocation function declared > @@ -1250,9 +1276,11 @@ alloc_max_size (void) > bool > get_size_range (tree exp, tree range[2], bool allow_zero /* = false */) > { > - if (!exp) > - return false; > - > + if (!exp || !INTEGRAL_TYPE_P (TREE_TYPE (exp))) > + { > + range[0] = range[1] = NULL_TREE; > + return false; > + } > if (tree_fits_uhwi_p (exp)) > { > /* EXP is a constant. */ > @@ -1261,91 +1289,30 @@ get_size_range (tree exp, tree range[2], bool allow_zero /* = false */) > } > > tree exptype = TREE_TYPE (exp); > - bool integral = INTEGRAL_TYPE_P (exptype); > - > - wide_int min, max; > - enum value_range_kind range_type; > - > - if (integral) > - range_type = determine_value_range (exp, &min, &max); > - else > - range_type = VR_VARYING; > - > - if (range_type == VR_VARYING) > + value_range vr; > + determine_value_range (&vr, exp); > + if (vr.num_pairs () == 1) > + return set_bounds_from_range (&vr, range); > + > + widest_irange positives (vr); > + range_remove_non_positives (&positives, allow_zero); > + > + // If all numbers are negative, let the caller sort it out. > + if (positives.undefined_p ()) > + return set_bounds_from_range (&vr, range); > + > + // Remove the unknown parts of a multi-range. > + // This will transform [5,10][20,MAX] into [5,10]. Is this comment correct? Wouldn't this result in returning smaller sizes than the actual value allows? If so, I'd expect that to cause false positives (and in that case, if none of our tests fail we need to add some that would). By my reading of the code below it seems to return the upper range (i.e., [20, MAX]) but I'm not fully acquainted with the new ranger APIs yet. Thanks Martin > + int pairs = positives.num_pairs (); > + if (pairs > 1 > + && positives.upper_bound () == wi::to_wide (TYPE_MAX_VALUE (exptype))) > { > - if (integral) > - { > - /* Use the full range of the type of the expression when > - no value range information is available. */ > - range[0] = TYPE_MIN_VALUE (exptype); > - range[1] = TYPE_MAX_VALUE (exptype); > - return true; > - } > - > - range[0] = NULL_TREE; > - range[1] = NULL_TREE; > - return false; > + value_range last_range (exptype, > + positives.lower_bound (pairs - 1), > + positives.upper_bound (pairs - 1), VR_ANTI_RANGE); > + positives.intersect (last_range); > } > - > - unsigned expprec = TYPE_PRECISION (exptype); > - > - bool signed_p = !TYPE_UNSIGNED (exptype); > - > - if (range_type == VR_ANTI_RANGE) > - { > - if (signed_p) > - { > - if (wi::les_p (max, 0)) > - { > - /* EXP is not in a strictly negative range. That means > - it must be in some (not necessarily strictly) positive > - range which includes zero. Since in signed to unsigned > - conversions negative values end up converted to large > - positive values, and otherwise they are not valid sizes, > - the resulting range is in both cases [0, TYPE_MAX]. */ > - min = wi::zero (expprec); > - max = wi::to_wide (TYPE_MAX_VALUE (exptype)); > - } > - else if (wi::les_p (min - 1, 0)) > - { > - /* EXP is not in a negative-positive range. That means EXP > - is either negative, or greater than max. Since negative > - sizes are invalid make the range [MAX + 1, TYPE_MAX]. */ > - min = max + 1; > - max = wi::to_wide (TYPE_MAX_VALUE (exptype)); > - } > - else > - { > - max = min - 1; > - min = wi::zero (expprec); > - } > - } > - else if (wi::eq_p (0, min - 1)) > - { > - /* EXP is unsigned and not in the range [1, MAX]. That means > - it's either zero or greater than MAX. Even though 0 would > - normally be detected by -Walloc-zero, unless ALLOW_ZERO > - is true, set the range to [MAX, TYPE_MAX] so that when MAX > - is greater than the limit the whole range is diagnosed. */ > - if (allow_zero) > - min = max = wi::zero (expprec); > - else > - { > - min = max + 1; > - max = wi::to_wide (TYPE_MAX_VALUE (exptype)); > - } > - } > - else > - { > - max = min - 1; > - min = wi::zero (expprec); > - } > - } > - > - range[0] = wide_int_to_tree (exptype, min); > - range[1] = wide_int_to_tree (exptype, max); > - > - return true; > + return set_bounds_from_range (&positives, range); > } > > /* Diagnose a call EXP to function FN decorated with attribute alloc_size > diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c > index 5620e6bf28f..2a1b1872e27 100644 > --- a/gcc/tree-affine.c > +++ b/gcc/tree-affine.c > @@ -340,7 +340,7 @@ expr_to_aff_combination (aff_tree *comb, tree_code code, tree type, > op1 = fold_convert (otype, op1); > return expr_to_aff_combination (comb, icode, otype, op0, op1); > } > - wide_int minv, maxv; > + value_range vr; > /* If inner type has wrapping overflow behavior, fold conversion > for below case: > (T1)(X *+- CST) -> (T1)X *+- (T1)CST > @@ -348,10 +348,11 @@ expr_to_aff_combination (aff_tree *comb, tree_code code, tree type, > if (TYPE_UNSIGNED (itype) > && TYPE_OVERFLOW_WRAPS (itype) > && TREE_CODE (op1) == INTEGER_CST > - && determine_value_range (op0, &minv, &maxv) == VR_RANGE) > + && determine_value_range (&vr, op0)) > { > wi::overflow_type overflow = wi::OVF_NONE; > signop sign = UNSIGNED; > + wide_int minv = vr.lower_bound (), maxv = vr.upper_bound (); > if (icode == PLUS_EXPR) > wi::add (maxv, wi::to_wide (op1), sign, &overflow); > else if (icode == MULT_EXPR) > diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c > index de84c1d505d..2078cd246c6 100644 > --- a/gcc/tree-vrp.c > +++ b/gcc/tree-vrp.c > @@ -4565,25 +4565,30 @@ make_pass_vrp (gcc::context *ctxt) > } > > > -/* Worker for determine_value_range. */ > +/* Compute a value-range for EXPR and set it in *VR. Return TRUE if range > + found was neither varying nor undefined. */ > > -static void > -determine_value_range_1 (value_range *vr, tree expr) > +bool > +determine_value_range (irange *vr, tree expr) > { > if (BINARY_CLASS_P (expr)) > { > - value_range vr0, vr1; > - determine_value_range_1 (&vr0, TREE_OPERAND (expr, 0)); > - determine_value_range_1 (&vr1, TREE_OPERAND (expr, 1)); > - range_fold_binary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr), > + value_range res, vr0, vr1; > + determine_value_range (&vr0, TREE_OPERAND (expr, 0)); > + determine_value_range (&vr1, TREE_OPERAND (expr, 1)); > + range_fold_binary_expr (&res, TREE_CODE (expr), TREE_TYPE (expr), > &vr0, &vr1); > + res.normalize_symbolics (); > + *vr = res; > } > else if (UNARY_CLASS_P (expr)) > { > - value_range vr0; > - determine_value_range_1 (&vr0, TREE_OPERAND (expr, 0)); > - range_fold_unary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr), > + value_range res, vr0; > + determine_value_range (&vr0, TREE_OPERAND (expr, 0)); > + range_fold_unary_expr (&res, TREE_CODE (expr), TREE_TYPE (expr), > &vr0, TREE_TYPE (TREE_OPERAND (expr, 0))); > + res.normalize_symbolics (); > + *vr = res; > } > else if (TREE_CODE (expr) == INTEGER_CST) > vr->set (expr); > @@ -4602,22 +4607,5 @@ determine_value_range_1 (value_range *vr, tree expr) > else > vr->set_varying (TREE_TYPE (expr)); > } > -} > - > -/* Compute a value-range for EXPR and set it in *MIN and *MAX. Return > - the determined range type. */ > - > -value_range_kind > -determine_value_range (tree expr, wide_int *min, wide_int *max) > -{ > - value_range vr; > - determine_value_range_1 (&vr, expr); > - if (vr.constant_p ()) > - { > - *min = wi::to_wide (vr.min ()); > - *max = wi::to_wide (vr.max ()); > - return vr.kind (); > - } > - > - return VR_VARYING; > + return !vr->varying_p () && !vr->undefined_p (); > } > diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h > index 371e58aa0ea..54c88c93d48 100644 > --- a/gcc/tree-vrp.h > +++ b/gcc/tree-vrp.h > @@ -61,7 +61,7 @@ extern bool find_case_label_index (gswitch *, size_t, tree, size_t *); > extern bool overflow_comparison_p (tree_code, tree, tree, bool, tree *); > extern tree get_single_symbol (tree, bool *, tree *); > extern void maybe_set_nonzero_bits (edge, tree); > -extern value_range_kind determine_value_range (tree, wide_int *, wide_int *); > +extern bool determine_value_range (irange *vr, tree); > extern wide_int masked_increment (const wide_int &val_in, const wide_int &mask, > const wide_int &sgnbit, unsigned int prec); > >