public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
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


      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).