From: Bernhard Reutner-Fischer <rep.dot.nop@gmail.com>
To: Andrew MacLeod via Gcc-patches <gcc-patches@gcc.gnu.org>
Cc: rep.dot.nop@gmail.com, Andrew MacLeod <amacleod@redhat.com>
Subject: Re: [PATCH] Process unsigned overflow relations for plus and minus in range-ops.
Date: Sat, 1 Oct 2022 09:47:52 +0200 [thread overview]
Message-ID: <20221001094752.5fbb4079@nbbrfq> (raw)
In-Reply-To: <9b234c9a-5020-c97c-c379-877c4c018293@redhat.com>
On Thu, 29 Sep 2022 18:38:10 -0400
Andrew MacLeod via Gcc-patches <gcc-patches@gcc.gnu.org> 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
prev parent reply other threads:[~2022-10-01 7:48 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-09-29 22:38 Andrew MacLeod
2022-10-01 7:47 ` Bernhard Reutner-Fischer [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20221001094752.5fbb4079@nbbrfq \
--to=rep.dot.nop@gmail.com \
--cc=amacleod@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).