From patchwork Thu Sep 29 22:38:10 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1684647 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=G0756ljU; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4MdpFL3DHSz1yqc for ; Fri, 30 Sep 2022 08:39:17 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 73324384BC2D for ; Thu, 29 Sep 2022 22:39:15 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 73324384BC2D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1664491155; bh=1n4H1UBzRKQlnhFbVV1rY8Qp2dKGh+w3kR6h3PpogJ4=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=G0756ljUaXdqkjvIdMHvyT9HM3akWnv196VfQuw5LjE7nCIZmYqvvunz2nBAgZrF7 9t+F7Q5RGeUl3ljWKhHxfSm3sHV6TiQahPkATtdi8RGi45sXl/b59aLb4C5KW6BILK 4LIzXAXyvSF3AbBN8BJIWzztOKC5OU9e2NqRPYkQ= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id E2485384BC2C for ; Thu, 29 Sep 2022 22:38:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E2485384BC2C Received: from mail-qv1-f71.google.com (mail-qv1-f71.google.com [209.85.219.71]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-30-_5_uq70cM-yyGW5OWJU8WA-1; Thu, 29 Sep 2022 18:38:14 -0400 X-MC-Unique: _5_uq70cM-yyGW5OWJU8WA-1 Received: by mail-qv1-f71.google.com with SMTP id c6-20020a0ce7c6000000b004abe95fbed8so1864052qvo.11 for ; Thu, 29 Sep 2022 15:38:14 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date; bh=kH+mtPyt44UI/0aBOPNcI/GuBsi+ip81Dku5vHrfJe8=; b=654A6T2F7quiLXShDISya6ZTYTHlvsGKR0joWsz1fpQBdK3YO4uwBvuajRvPXsq8SL 5pzxAfbdfuE2ZpxX09Nm8zyCT6Fvq+ln1vKLSFsUrmhKWVszDoFVyCEstvyC6kl1IGEP 0HOaP+JP8RVFPwInlT3CaWq7YGg94ACTJxydJ4w31EF4a4XZikXe7HfhRtg0Vt8InRA5 Gcyxmgj4RoVjR5FZacG2Edj6H/iIVFlPHXtDuD0M6vZFfyzXxTkUHCQRbd5GcDi2ROov 7lCYJjx8tjHIeKCpTxDFcr/eANFwE1jigHCKLBraGRbauCs7emttnS0/KFV5l7Zngzd9 Ad3A== X-Gm-Message-State: ACrzQf2NjrAUZBuFHLq7BoUR15xtOUH2oSSKq2DJrG8+4Rcn9/7iaLTp lSBjmulpBSO5Yrz/PbYEjvjF7p8fyaoXNmPndr+/8BUgeer8FWS6z5VttgTSCEI6SUTYux/h5at 9W38b8Mn6q03x7AisqlxnPZeSMs8qfi35TjShKbKEwXZb3qybBWziLryT9Q8vvBMgSGMK+w== X-Received: by 2002:ac8:7dc6:0:b0:35c:c9b1:9f98 with SMTP id c6-20020ac87dc6000000b0035cc9b19f98mr4554464qte.170.1664491093110; Thu, 29 Sep 2022 15:38:13 -0700 (PDT) X-Google-Smtp-Source: AMsMyM4RnDXnSO8jgIA2eT+TyZGSRCs011GnomEK7QQVPAkh2yk1RZu3HNjB0ZV4NMZwyJSdskQblQ== X-Received: by 2002:ac8:7dc6:0:b0:35c:c9b1:9f98 with SMTP id c6-20020ac87dc6000000b0035cc9b19f98mr4554449qte.170.1664491092805; Thu, 29 Sep 2022 15:38:12 -0700 (PDT) Received: from ?IPV6:2607:fea8:a263:f600::3dbe? ([2607:fea8:a263:f600::3dbe]) by smtp.gmail.com with ESMTPSA id q34-20020a05620a2a6200b006b8d1914504sm702757qkp.22.2022.09.29.15.38.11 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 29 Sep 2022 15:38:11 -0700 (PDT) Message-ID: <9b234c9a-5020-c97c-c379-877c4c018293@redhat.com> Date: Thu, 29 Sep 2022 18:38:10 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.1 To: gcc-patches Subject: [PATCH] Process unsigned overflow relations for plus and minus in range-ops. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.0 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_NONE, 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 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-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" If a relation is available, calculate overflow and normal ranges. Then apply as appropriate. This patch implements operator_plus::op1/op2_range and operator_minus::op1_range to utilize any relation passed into properly reflect the range. If the relation between the LHS and the operand being calculated is one of <,<=,>,>=, then determine what the overflow and normal ranges are for this type, and reflect those in the operand being calculated. With this patch, we can move the testcase for PR 79095 to an evrp test instead of vrp1, so we resolve it much earlier.  This testcase tests various overflow conditions to ensure we can detect and propagate overflow conditions.  ie, it has a series of tests similar to: unsigned f1 (unsigned a, unsigned b) {   b = a + 1;   if (b < a)     {       arf (a, b);       return 42;     }   baz (a, b);   return b; } It tests that 'baz' remains a call using symbolic names, and that 'arf' can be folded to constant arguments. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From f02cb8601792be310e8760b082e0c3213129639a Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 23 Aug 2022 10:17:02 -0400 Subject: [PATCH 6/6] Process unsigned overflow relations for plus and minus is range-ops. If a relation is available, calculate overflow and normal ranges. Then apply as appropriate. gcc/ * range-op.cc (plus_minus_ranges): New. (adjust_op1_for_overflow): New. (operator_plus::op1_range): Use new adjustment. (operator_plus::op2_range): Ditto. (operator_minus::op1_range): Ditto. * value-relation.h (relation_lt_le_gt_ge_p): New. gcc/testsuite/ * gcc.dg/tree-ssa/pr79095.c: Test evrp pass rather than vrp1. --- gcc/range-op.cc | 121 +++++++++++++++++++++++- gcc/testsuite/gcc.dg/tree-ssa/pr79095.c | 6 +- gcc/value-relation.h | 2 + 3 files changed, 121 insertions(+), 8 deletions(-) diff --git a/gcc/range-op.cc b/gcc/range-op.cc index 9bb04c361d0..830c64bd6b9 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -1305,22 +1305,123 @@ operator_plus::wi_fold (irange &r, tree type, value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub); } +// Given addition or subtraction, determine the possible NORMAL ranges and +// OVERFLOW ranges given an OFFSET range. ADD_P is true for addition. +// Return the relation that exists between the LHS and OP1 in order for the +// NORMAL range to apply. +// a return value of VREL_VARYING means no ranges were applicable. + +static relation_kind +plus_minus_ranges (irange &r_ov, irange &r_normal, const irange &offset, + bool add_p) +{ + relation_kind kind = VREL_VARYING; + // For now, only deal with constant adds. This could be extended to ranges + // when someone is so motivated. + if (!offset.singleton_p () || offset.zero_p ()) + return kind; + + // Always work with a positive offset. ie a+ -2 -> a-2 and a- -2 > a+2 + wide_int off = offset.lower_bound (); + if (wi::neg_p (off, SIGNED)) + { + add_p = !add_p; + off = wi::neg (off); + } + + wi::overflow_type ov; + tree type = offset.type (); + unsigned prec = TYPE_PRECISION (type); + wide_int ub; + wide_int lb; + // calculate the normal range and relation for the operation. + if (add_p) + { + // [ 0 , INF - OFF] + lb = wi::zero (prec); + ub = wi::sub (wi::to_wide (vrp_val_max (type)), off, UNSIGNED, &ov); + kind = VREL_GT; + } + else + { + // [ OFF, INF ] + lb = off; + ub = wi::to_wide (vrp_val_max (type)); + kind = VREL_LT; + } + int_range<2> normal_range (type, lb, ub); + int_range<2> ov_range (type, lb, ub, VR_ANTI_RANGE); + + r_ov = ov_range; + r_normal = normal_range; + return kind; +} + +// Once op1 has been calculated by operator_plus or operator_minus, check +// to see if the relation passed causes any part of the calculation to +// be not possible. ie +// a_2 = b_3 + 1 with a_2 < b_3 can refine the range of b_3 to [INF, INF] +// and that further refines a_2 to [0, 0]. +// R is the value of op1, OP2 is the offset being added/subtracted, REL is the +// relation between LHS relatoin OP1 and ADD_P is true for PLUS, false for +// MINUS. IF any adjustment can be made, R will reflect it. + +static void +adjust_op1_for_overflow (irange &r, const irange &op2, relation_kind rel, + bool add_p) +{ + tree type = r.type (); + // Check for unsigned overflow and calculate the overflow part. + signop s = TYPE_SIGN (type); + if (!TYPE_OVERFLOW_WRAPS (type) || s == SIGNED) + return; + + // Only work with <, <=, >, >= relations. + if (!relation_lt_le_gt_ge_p (rel)) + return; + + // Get the ranges for this offset. + int_range_max normal, overflow; + relation_kind k = plus_minus_ranges (overflow, normal, op2, add_p); + + // VREL_VARYING means there are no adjustments. + if (k == VREL_VARYING) + return; + + // If the relations match use the normal range, otherwise use overflow range. + if (relation_intersect (k, rel) == k) + r.intersect (normal); + else + r.intersect (overflow); + return; +} + bool operator_plus::op1_range (irange &r, tree type, const irange &lhs, const irange &op2, - relation_kind rel ATTRIBUTE_UNUSED) const + relation_kind rel) const { - return range_op_handler (MINUS_EXPR, type).fold_range (r, type, lhs, op2); + if (lhs.undefined_p ()) + return false; + // Start with the default operation. + range_op_handler minus (MINUS_EXPR, type); + if (!minus) + return false; + bool res = minus.fold_range (r, type, lhs, op2); + // Check for a relation refinement. + if (res) + adjust_op1_for_overflow (r, op2, rel, true /* PLUS_EXPR */); + return res; } bool operator_plus::op2_range (irange &r, tree type, const irange &lhs, const irange &op1, - relation_kind rel ATTRIBUTE_UNUSED) const + relation_kind rel) const { - return range_op_handler (MINUS_EXPR, type).fold_range (r, type, lhs, op1); + return op1_range (r, type, lhs, op1, rel); } @@ -1472,7 +1573,17 @@ operator_minus::op1_range (irange &r, tree type, const irange &op2, relation_kind rel ATTRIBUTE_UNUSED) const { - return range_op_handler (PLUS_EXPR, type).fold_range (r, type, lhs, op2); + if (lhs.undefined_p ()) + return false; + // Start with the default operation. + range_op_handler minus (PLUS_EXPR, type); + if (!minus) + return false; + bool res = minus.fold_range (r, type, lhs, op2); + if (res) + adjust_op1_for_overflow (r, op2, rel, false /* PLUS_EXPR */); + return res; + } bool diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr79095.c b/gcc/testsuite/gcc.dg/tree-ssa/pr79095.c index f635fcafe4f..b1751877756 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr79095.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr79095.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fno-ipa-icf -fdump-tree-vrp1" } */ +/* { dg-options "-O2 -fno-ipa-icf -fdump-tree-evrp" } */ extern void arf (unsigned x, unsigned y); extern void baz (unsigned x, unsigned y); @@ -429,8 +429,8 @@ f4nro (unsigned a, unsigned b) } /* All calls to baz should still reference a & b as arguments. */ -/* { dg-final { scan-tree-dump-times "baz \\(a_\[0-9\]+\\(D\\), b_\[0-9\]+\\)" 32 "vrp1"} } */ +/* { dg-final { scan-tree-dump-times "baz \\(a_\[0-9\]+\\(D\\), b_\[0-9\]+\\)" 32 "evrp"} } */ /* All calls to arf should have constant arguments. */ -/* { dg-final { scan-tree-dump-times "arf \\(\[0-9\]+, \[0-9\]+\\)" 32 "vrp1"} } */ +/* { dg-final { scan-tree-dump-times "arf \\(\[0-9\]+, \[0-9\]+\\)" 32 "evrp"} } */ diff --git a/gcc/value-relation.h b/gcc/value-relation.h index f3b18ac62ef..e1347ea8ad8 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -78,6 +78,8 @@ relation_kind relation_union (relation_kind r1, relation_kind r2); relation_kind relation_intersect (relation_kind r1, relation_kind r2); relation_kind relation_negate (relation_kind r); relation_kind relation_swap (relation_kind r); +inline bool relation_lt_le_gt_ge_p (relation_kind r) + { return (r >= VREL_LT && r <= VREL_GE); } void print_relation (FILE *f, relation_kind rel); class relation_oracle -- 2.37.3