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: 1565 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4ac7:0:0:0:0:0 with SMTP id y7csp207140wrs; Thu, 29 Sep 2022 15:42:36 -0700 (PDT) X-Google-Smtp-Source: AMsMyM6ZlfCnZQkSv9rqqKgLU22358dC377Pb4MCX/dKFs8ZC/gfpLVc7SLbQeVIxK6vzr1lGo8i X-Received: by 2002:a05:6402:414d:b0:451:73f0:e113 with SMTP id x13-20020a056402414d00b0045173f0e113mr5402709eda.207.1664491356509; Thu, 29 Sep 2022 15:42:36 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1664491356; cv=none; d=google.com; s=arc-20160816; b=NeZWiCbPAIW4LbtQfT3zmTVaYj/s9eAH7ocsrJKd/X0FnZ6IVywhMxniDD9aj2FBJs xmjAYgCz+SrzTNThnwGFx9NLFerVUvnnQ4YViJIMZ5YsYp3Lp3qqplcOpAolX6QmsggU ln+6VUTNTbczMYuKzXndiXviO5iT1NzBsTrzPtckCVYiSQTAu8he4UA05UuKPMgH5CRU XTw2VGurEO2qrwei2jzJ7AuAvZlDb1n3vi8THjn8I3O6mG+TYr2G5sbfkPt6A7TjUXMA HoTGApBb01PV4Vcf+g+L6hBa40v0iqRws1c25mYbJ+DPgnME+7WF38jSt5wh5Iu+K+Fg Utvg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:content-language :subject:to:user-agent:mime-version:date:message-id:dmarc-filter :delivered-to:dkim-signature:dkim-filter; bh=1n4H1UBzRKQlnhFbVV1rY8Qp2dKGh+w3kR6h3PpogJ4=; b=PPAOZS6pM1YnoeKTAY3oCDT6fx92K5Tg8cSkUreVn6BozpEsJ7WCKFVawGTHfRcUUu yk0HdKxK6f8F9fPEkOF3hbDXSXtAUgboHzRAcBInxY+Czle3hcwovQa5ThYmFZAaq2RI 6OoheQRMgEr5h/18S/gW0DhNAi64uagIabUjRZyClsAVdIdCxj/lPaba946G2JA4EEEe S63vQnrsaivVI9yr/IsczOlcejSqHfGuBBSJplxe4X6I4gE0uZZ6evkJPrSegskdqUM9 WV8pq5LK+zPvDwPMFeA/LTQsSOYjFl7L6gSU/x/d59JnYaSdaxFNhuFaxKTeSdn9t9lk gNHA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=FukeKyK1; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id v29-20020a50955d000000b00451c4c5f019si636999eda.324.2022.09.29.15.42.36 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Sep 2022 15:42:36 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=FukeKyK1; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 804B738207F7 for ; Thu, 29 Sep 2022 22:39:40 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 804B738207F7 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1664491180; bh=1n4H1UBzRKQlnhFbVV1rY8Qp2dKGh+w3kR6h3PpogJ4=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=FukeKyK1Ts4bR/Buw8EI0Wad2856JYSM4h0maHAKbIQ73avIbmPC7hxndsxlrx3cO cTnuQ+M1PN40ZswRFRxQflFKM84l7ezYYUZw3nmB5TrcHqABZOqotkRjt7ICJehDD8 qVwSE4Ic2jxhO0OhaedfMGaryTvsHPeSZGkPLB0E= 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-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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1745345688292114531?= X-GMAIL-MSGID: =?utf-8?q?1745345688292114531?= 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