From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x629.google.com (mail-ej1-x629.google.com [IPv6:2a00:1450:4864:20::629]) by sourceware.org (Postfix) with ESMTPS id 6298F3858D1E for ; Sat, 1 Oct 2022 07:48:06 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 6298F3858D1E Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-ej1-x629.google.com with SMTP id dv25so13161599ejb.12 for ; Sat, 01 Oct 2022 00:48:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:subject:cc:to:from:date:from:to:cc:subject:date; bh=T+qDjQmgL6cNQvd/cH5EzM2jpF7uaYFb8UbwNoLzp4I=; b=U8Wm5P77JR6QRGPH0k5VqCDiwz26pDTQeJCXkNg4fUAxs0XCWXXtLSVVGygcHNWKYH 98XOwd2VXJWUsAbqExalEfz5h8zgTZhM4Xc7KVJqye0zOeil720WIr1Eakkcypf/g7Po rUVxDi5grOESjCaaxOQKQPjXtrvVBR5YE561IkX/mQIsA7Lo2O9h+g2xbH0JJ+DLlyiI h5T0vPQqiKsjBf6cScv++HiDpJ7tpJ6X5Cw1M9bOPl5NwGWsurnxFGJ95IvpOxYgsH7N p+vd1Wg7ffbit8IPCGpk7VEEwE6MLo34A93joW97tPKfCBJg2IamJk6YOoBLpuOTDa/Z yL/g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:subject:cc:to:from:date:x-gm-message-state:from:to:cc :subject:date; bh=T+qDjQmgL6cNQvd/cH5EzM2jpF7uaYFb8UbwNoLzp4I=; b=AfkOzcf7a3qmVZWu1mp6wyc/JHXpY/4hg4lmQxpjw/6Hd8aHO40XGmGTOiFPfAMXjw BRcw4Q4hLFIzw7dXiVhXXWipEg8Wowj6MQiTZZjTAULm6cp0adkrRYTJZr4EkyoWP/Hn m3qW6+2WfdeO62JB/RdDfxGmrfJx5UL0WZhs7dFMh0E7bzszW1VIIu9uvSvZptPaSmgQ w37wi0DCIH1B1IB4ss9q3wVr1FW/+caJfjt/cXGNhocOTzmEOHHGJch8w9GWSdZqEh0S O6kbQsVHFKIz5ypPsLueVvCsfQTJkDfWFTC02YIlelFjMjXZkPNBK6dOIyLOXVL3sqH4 mDWQ== X-Gm-Message-State: ACrzQf2zwdDJnM94+BGZDbBw+xNWhTjC48+/UrrRToq5tIj8pHq2OeRR CTLfd7qYmwpHDZM29Fh6Cmk= X-Google-Smtp-Source: AMsMyM699rNaX033BRf47Gbq70qgGvzLC/qEPptM0AUepebzSt5ydtLQ98FCQPdsxAXmigPEnvBlhw== X-Received: by 2002:a17:906:9753:b0:787:8e6a:103c with SMTP id o19-20020a170906975300b007878e6a103cmr8955400ejy.337.1664610484925; Sat, 01 Oct 2022 00:48:04 -0700 (PDT) Received: from nbbrfq ([2001:871:227:1d92:3b3f:9f87:ac65:9ebc]) by smtp.gmail.com with ESMTPSA id 18-20020a170906211200b0077a8fa8ba55sm2299234ejt.210.2022.10.01.00.48.04 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 01 Oct 2022 00:48:04 -0700 (PDT) Date: Sat, 1 Oct 2022 09:47:52 +0200 From: Bernhard Reutner-Fischer To: Andrew MacLeod via Gcc-patches Cc: rep.dot.nop@gmail.com, Andrew MacLeod Subject: Re: [PATCH] Process unsigned overflow relations for plus and minus in range-ops. Message-ID: <20221001094752.5fbb4079@nbbrfq> In-Reply-To: <9b234c9a-5020-c97c-c379-877c4c018293@redhat.com> References: <9b234c9a-5020-c97c-c379-877c4c018293@redhat.com> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-10.3 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,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 List-Id: On Thu, 29 Sep 2022 18:38:10 -0400 Andrew MacLeod via Gcc-patches wrote: > 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. Capital A in A return value > + > +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. s/relatoin/relation/ Excess space before the last sentense, or should this go to a new line? > + > +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 You could remove ATTRIBUTE_UNUSED above for rel like you did for the other operators. > { > - 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/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); } surplus braces. This could be __attribute__((__pure__)) but that's certainly found by predict even without the annotation? Probably it makes no difference because it's inlined anyway. thanks, > void print_relation (FILE *f, relation_kind rel); > > class relation_oracle