From patchwork Fri Oct 4 12:59:36 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 1171825 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-510247-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="kvoSRN96"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 46l92L2srNz9s4Y for ; Fri, 4 Oct 2019 22:59:51 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to:cc :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=e3iVL0NtX084mEDlQVkg+uLoT3ZXn5h835SKDUwdDqFomd3Tyb G49N0yl5NFMfVwFHDM3q5DAQOOiqnhnhuxgWlNxQskd4ZcNaJZnyp3xYIWU5lHuA Livrvhj+4CTv8r5NtH/6JZsJcOSwZcCknCAmrbVgjz51JGxWC5vyIroRM= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to:cc :from:subject:message-id:date:mime-version:content-type; s= default; bh=MBG/TOX6CsDe+ESY5EnTztwv4rY=; b=kvoSRN96NEnzzTwGBhCZ 3PwqlINCZ0dfDbPwtSWNAN3psrp1bDkiWS0iJ5EHMw7FvpDpmssXMiwk7CYyL3hd UI2WRXcssdLrgJztBkrTHWSttKfkxJ/uC+WN+wwdlD16DumQ+DSqL2QadKz2cQRS /HECGDWq/dNN3y95s9ehync= Received: (qmail 60895 invoked by alias); 4 Oct 2019 12:59:43 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 60887 invoked by uid 89); 4 Oct 2019 12:59:43 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-24.4 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, SPF_HELO_PASS autolearn=ham version=3.3.1 spammy=VR_RANGE, !type_unsigned, !TYPE_UNSIGNED, vr_range X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 04 Oct 2019 12:59:41 +0000 Received: from mail-wm1-f69.google.com (mail-wm1-f69.google.com [209.85.128.69]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 63BF959451 for ; Fri, 4 Oct 2019 12:59:40 +0000 (UTC) Received: by mail-wm1-f69.google.com with SMTP id f63so1580007wma.7 for ; Fri, 04 Oct 2019 05:59:40 -0700 (PDT) Received: from abulafia.quesejoda.com (136.red-2-139-5.dynamicip.rima-tde.net. [2.139.5.136]) by smtp.gmail.com with ESMTPSA id t13sm16017969wra.70.2019.10.04.05.59.37 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 04 Oct 2019 05:59:37 -0700 (PDT) To: Jeff Law Cc: gcc-patches , Andrew MacLeod From: Aldy Hernandez Subject: [patch] canonicalize unsigned [1,MAX] ranges into ~[0,0] Message-ID: Date: Fri, 4 Oct 2019 08:59:36 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.7.0 MIME-Version: 1.0 X-IsSubscribed: yes When I did the value_range canonicalization work, I noticed that an unsigned [1,MAX] and an ~[0,0] could be two different representations for the same thing. I didn't address the problem then because callers to ranges_from_anti_range() would go into an infinite loop trying to extract ~[0,0] into [1,MAX] and []. We had a lot of callers to ranges_from_anti_range, and it smelled like a rat's nest, so I bailed. Now that we have one main caller (from the symbolic PLUS/MINUS handling), it's a lot easier to contain. Well, singleton_p also calls it, but it's already handling nonzero specially, so it wouldn't be affected. With some upcoming cleanups I'm about to post, the fact that [1,MAX] and ~[0,0] are equal_p(), but not nonzero_p(), matters. Plus, it's just good form to have one representation, giving us the ability to pick at nonzero_p ranges with ease. The code in extract_range_from_plus_minus_expr() continues to be a mess (as it has always been), but at least it's contained, and with this patch, it's slightly smaller. Note, I'm avoiding adding a comment header for functions with highly descriptive obvious names. OK? Aldy commit 1c333730deeb4ddadc46ad6d12d5344f92c0352c Author: Aldy Hernandez Date: Fri Oct 4 08:51:25 2019 +0200 Canonicalize UNSIGNED [1,MAX] into ~[0,0]. Adapt PLUS/MINUS symbolic handling, so it doesn't call ranges_from_anti_range with a VR_ANTI_RANGE containing one sub-range. diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 6e4f145af46..3934b41fdf9 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,18 @@ +2019-10-04 Aldy Hernandez + + * tree-vrp.c (value_range_base::singleton_p): Use num_pairs + instead of calling vrp_val_is_*. + (value_range_base::set): Canonicalize unsigned [1,MAX] into + non-zero. + (range_has_numeric_bounds_p): New. + (range_int_cst_p): Use range_has_numeric_bounds_p. + (ranges_from_anti_range): Assert that we won't recurse + indefinitely. + (extract_extremes_from_range): New. + (extract_range_from_plus_minus_expr): Adapt so we don't call + ranges_from_anti_range with an anti-range containing only one + sub-range. + 2019-10-04 Aldy Hernandez (value_range_from_overflowed_bounds): Rename from diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index a2ab4a21925..97dd2b7a734 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -379,10 +379,7 @@ value_range_base::singleton_p (tree *result) const } return false; } - - /* An anti-range that includes an extreme, is just a range with - one sub-range. Use the one sub-range. */ - if (vrp_val_is_min (m_min, true) || vrp_val_is_max (m_max, true)) + if (num_pairs () == 1) { value_range_base vr0, vr1; ranges_from_anti_range (this, &vr0, &vr1, true); @@ -843,6 +840,17 @@ value_range_base::set (enum value_range_kind kind, tree min, tree max) return; } + /* Unsigned [1, MAX] is canonicalized as ~[0, 0]. */ + if (kind == VR_RANGE && TYPE_UNSIGNED (type) + && prec > 1 + && wi::eq_p (wi::to_wide (min), wi::one (prec)) + && wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign))) + { + m_kind = VR_ANTI_RANGE; + m_min = m_max = build_int_cst (type, 0); + return; + } + /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky to make sure VRP iteration terminates, otherwise we can get into oscillations. */ @@ -913,15 +921,21 @@ vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2) && bitmap_equal_p (b1, b2))); } +static bool +range_has_numeric_bounds_p (const value_range_base *vr) +{ + return (vr->min () + && TREE_CODE (vr->min ()) == INTEGER_CST + && TREE_CODE (vr->max ()) == INTEGER_CST); +} + /* Return true if max and min of VR are INTEGER_CST. It's not necessary a singleton. */ bool range_int_cst_p (const value_range_base *vr) { - return (vr->kind () == VR_RANGE - && TREE_CODE (vr->min ()) == INTEGER_CST - && TREE_CODE (vr->max ()) == INTEGER_CST); + return (vr->kind () == VR_RANGE && range_has_numeric_bounds_p (vr)); } /* Return true if VR is a INTEGER_CST singleton. */ @@ -1327,6 +1341,10 @@ ranges_from_anti_range (const value_range_base *ar, value_range_base *vr0, value_range_base *vr1, bool handle_pointers) { + /* An unsigned ~[0,0] cannot be split into [1,MAX] because it gets + normalized back into ~[0,0]. Avoid infinite loop. */ + gcc_checking_assert (!ar->nonzero_p () || !TYPE_UNSIGNED (ar->type ())); + tree type = ar->type (); vr0->set_undefined (); @@ -1582,6 +1600,22 @@ extract_range_from_pointer_plus_expr (value_range_base *vr, vr->set_varying (expr_type); } +static void +extract_extremes_from_range (const value_range_base *vr, tree *min, tree *max) +{ + if (range_has_numeric_bounds_p (vr)) + { + *min = wide_int_to_tree (vr->type (), vr->lower_bound ()); + *max = wide_int_to_tree (vr->type (), vr->upper_bound ()); + } + else + { + gcc_checking_assert (vr->kind () != VR_ANTI_RANGE); + *min = vr->min (); + *max = vr->max (); + } +} + /* Extract range information from a PLUS/MINUS_EXPR and store the result in *VR. */ @@ -1597,9 +1631,18 @@ extract_range_from_plus_minus_expr (value_range_base *vr, value_range_base vr0 = *vr0_, vr1 = *vr1_; value_range_base vrtem0, vrtem1; + /* We can't do anything with symbolic anti ranges. */ + if ((vr0.kind () == VR_ANTI_RANGE && !range_has_numeric_bounds_p (&vr0)) + || (vr1.kind () == VR_ANTI_RANGE && !range_has_numeric_bounds_p (&vr1))) + { + vr->set_varying (expr_type); + return; + } + /* Now canonicalize anti-ranges to ranges when they are not symbolic and express ~[] op X as ([]' op X) U ([]'' op X). */ if (vr0.kind () == VR_ANTI_RANGE + && vr0.num_pairs () == 2 && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1)) { extract_range_from_plus_minus_expr (vr, code, expr_type, &vrtem0, vr1_); @@ -1614,6 +1657,7 @@ extract_range_from_plus_minus_expr (value_range_base *vr, } /* Likewise for X op ~[]. */ if (vr1.kind () == VR_ANTI_RANGE + && vr1.num_pairs () == 2 && ranges_from_anti_range (&vr1, &vrtem0, &vrtem1)) { extract_range_from_plus_minus_expr (vr, code, expr_type, vr0_, &vrtem0); @@ -1628,26 +1672,10 @@ extract_range_from_plus_minus_expr (value_range_base *vr, } value_range_kind kind; - value_range_kind vr0_kind = vr0.kind (), vr1_kind = vr1.kind (); - tree vr0_min = vr0.min (), vr0_max = vr0.max (); - tree vr1_min = vr1.min (), vr1_max = vr1.max (); tree min = NULL, max = NULL; - - /* This will normalize things such that calculating - [0,0] - VR_VARYING is not dropped to varying, but is - calculated as [MIN+1, MAX]. */ - if (vr0.varying_p ()) - { - vr0_kind = VR_RANGE; - vr0_min = vrp_val_min (expr_type); - vr0_max = vrp_val_max (expr_type); - } - if (vr1.varying_p ()) - { - vr1_kind = VR_RANGE; - vr1_min = vrp_val_min (expr_type); - vr1_max = vrp_val_max (expr_type); - } + tree vr0_min, vr0_max, vr1_min, vr1_max; + extract_extremes_from_range (&vr0, &vr0_min, &vr0_max); + extract_extremes_from_range (&vr1, &vr1_min, &vr1_max); const bool minus_p = (code == MINUS_EXPR); tree min_op0 = vr0_min; @@ -1666,10 +1694,9 @@ extract_range_from_plus_minus_expr (value_range_base *vr, single-symbolic ranges, try to compute the precise resulting range, but only if we know that this resulting range will also be constant or single-symbolic. */ - if (vr0_kind == VR_RANGE && vr1_kind == VR_RANGE - && (TREE_CODE (min_op0) == INTEGER_CST - || (sym_min_op0 - = get_single_symbol (min_op0, &neg_min_op0, &min_op0))) + if ((TREE_CODE (min_op0) == INTEGER_CST + || (sym_min_op0 + = get_single_symbol (min_op0, &neg_min_op0, &min_op0))) && (TREE_CODE (min_op1) == INTEGER_CST || (sym_min_op1 = get_single_symbol (min_op1, &neg_min_op1, &min_op1))) @@ -1724,18 +1751,6 @@ extract_range_from_plus_minus_expr (value_range_base *vr, } else { - /* For other cases, for example if we have a PLUS_EXPR with two - VR_ANTI_RANGEs, drop to VR_VARYING. It would take more effort - to compute a precise range for such a case. - ??? General even mixed range kind operations can be expressed - by for example transforming ~[3, 5] + [1, 2] to range-only - operations and a union primitive: - [-INF, 2] + [1, 2] U [5, +INF] + [1, 2] - [-INF+1, 4] U [6, +INF(OVF)] - though usually the union is not exactly representable with - a single range or anti-range as the above is - [-INF+1, +INF(OVF)] intersected with ~[5, 5] - but one could use a scheme similar to equivalences for this. */ vr->set_varying (expr_type); return; }