Re: [PATCH V4] Optimize '(X - N * M) / N' to 'X / N - M' if valid

[Jiufu Guo <guojiufu@linux.ibm.com>]

Hi Andrew, Aldy and Richard,

Thanks a lot for all your very helpful comments!

Andrew MacLeod <amacleod@redhat.com> writes:

> On 7/14/23 09:37, Richard Biener wrote:
>> On Fri, 14 Jul 2023, Aldy Hernandez wrote:
>>
>>> I don't know what you're trying to accomplish here, as I haven't been
>>> following the PR, but adding all these helper functions to the ranger header
>>> file seems wrong, especially since there's only one use of them. I see you're
>>> tweaking the irange API, adding helper functions to range-op (which is only
>>> for code dealing with implementing range operators for tree codes), etc etc.
>>>
>>> If you need these helper functions, I suggest you put them closer to their
>>> uses (i.e. wherever the match.pd support machinery goes).
>> Note I suggested the opposite beacuse I thought these kind of helpers
>> are closer to value-range support than to match.pd.
>
>
> probably vr-values.{cc.h} and  the simply_using_ranges paradigm would
> be the most sensible place to put these kinds of auxiliary routines?

Thanks! Richard also mentioned this as an example of using VR APIs.
I did not use vr-values.h/cc just because it seems vr-values are not
used/included in match.pd directly yet.

>
>
>>
>> But I take away from your answer that there's nothing close in the
>> value-range machinery that answers the question whether A op B may
>> overflow?
>
> we dont track it in ranges themselves.   During calculation of a range
> we obviously know, but propagating that generally when we rarely care
> doesn't seem worthwhile.  The very first generation of irange 6 years
> ago had an overflow_p() flag, but it was removed as not being worth
> keeping.     easier to simply ask the question when it matters

Right, agree!

>
> As the routines show, it pretty easy to figure out when the need arises so I think that should suffice.  At least for now,
>
> Should we decide we would like it in general, it wouldnt be hard to
> add to irange.  wi_fold() cuurently returns null, it could easily
> return a bool indicating if an overflow happened, and wi_fold_in_parts
> and fold_range would simply OR the results all together of the
> compoent wi_fold() calls.  It would require updating/audfiting  a
> number of range-op entries and adding an overflowed_p()  query to
> irange.

I also tried to add a 'm_ovf' field to irange and record the
overflow info during 'wi_fold' in range-op(e.g. plus/minus/mult).
But, as you said, overflow info is not widely used (it seems that 
match.pd covers most of the cases which are using overflow info).
It may not be worth adding a field to every instance of VR, and 
additional cost may not be profitable to maintain it during VR
assign/union_/intersect.
I've attached a patch for this idea, just for reference.

Currently, what I'm trying to do is find a better place to add
APIs to check the overflow info for match.pd.

vr-range.h/cc would be one choice :)
I noticed Aldy mentioned 'may_overflow_p' in a comment of PR100499,
where this API was trying to add? This may be another choice.

Thanks a gain for your great comments!

BR,
Jeff (Jiufu Guo)

>
> Andrew

gcc/ChangeLog:

	* range-op.cc (value_range_with_overflow): Call set_overflow.
	(operator_mult::wi_fold): Call set_overflow.
	* value-query.h (get_range): New function.
	* value-range-storage.cc (irange_storage::set_irange): Set
	ovf info.
	(irange_storage::get_irange): Call set_overflow.
	* value-range-storage.h (irange_storage): Add m_ovf field.
	* value-range.cc (irange::nonnegative_p): New function.
	(irange::nonpositive_p): New function.
	(irange::operator=): Maintain ovf info.
	(irange::union_): Maintain ovf info.
	(irange::intersect): Maintain ovf info.
	* value-range.h (irange::irange): Initialize m_ovf.

---
 gcc/range-op.cc            | 17 +++++++++++++----
 gcc/value-query.h          | 10 ++++++++++
 gcc/value-range-storage.cc |  2 ++
 gcc/value-range-storage.h  |  1 +
 gcc/value-range.cc         | 29 ++++++++++++++++++++++++++---
 gcc/value-range.h          |  6 ++++++
 6 files changed, 58 insertions(+), 7 deletions(-)

diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 3ab2c665901..02971e8a16a 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -433,6 +433,10 @@ value_range_with_overflow (irange &r, tree type,
   const unsigned int prec = TYPE_PRECISION (type);
   const bool overflow_wraps = TYPE_OVERFLOW_WRAPS (type);
 
+  bool ovf = !TYPE_OVERFLOW_UNDEFINED (type)
+	     && (min_ovf != wi::OVF_NONE || max_ovf != wi::OVF_NONE);
+  r.set_overflow (ovf ? wi::OVF_UNKNOWN : wi::OVF_NONE);
+
   // For one bit precision if max != min, then the range covers all
   // values.
   if (prec == 1 && wi::ne_p (wmax, wmin))
@@ -2050,10 +2054,15 @@ operator_mult::wi_fold (irange &r, tree type,
 
   // Sort the 4 products so that min is in prod0 and max is in
   // prod3.
-  widest2_int prod0 = min0 * min1;
-  widest2_int prod1 = min0 * max1;
-  widest2_int prod2 = max0 * min1;
-  widest2_int prod3 = max0 * max1;
+  wi::overflow_type ovf1, ovf2, ovf3, ovf4;
+  widest2_int prod0 = wi::mul (min0, min1, sign, &ovf1);
+  widest2_int prod1 = wi::mul (min0, max1, sign, &ovf2);
+  widest2_int prod2 = wi::mul (max0, min1, sign, &ovf3);
+  widest2_int prod3 = wi::mul (max0, max1, sign, &ovf4);
+  bool ovf = !TYPE_OVERFLOW_UNDEFINED (type)
+	     && (ovf1 != wi::OVF_NONE || ovf2 != wi::OVF_NONE
+		 || ovf3 != wi::OVF_NONE || ovf3 != wi::OVF_NONE);
+  r.set_overflow (ovf ? wi::OVF_UNKNOWN : wi::OVF_NONE);
 
   // min0min1 > max0max1
   if (prod0 > prod3)
diff --git a/gcc/value-query.h b/gcc/value-query.h
index d10c3eac1e2..cf488c7ea9b 100644
--- a/gcc/value-query.h
+++ b/gcc/value-query.h
@@ -137,6 +137,16 @@ get_range_query (const struct function *fun)
   return (fun && fun->x_range_query) ? fun->x_range_query : &global_ranges;
 }
 
+/* Return true if there is range for "X" expression at "S" statement,
+   and the range is not varying and not undefined.   */
+
+inline bool
+get_range (vrange &r, tree x, gimple *s = NULL)
+{
+  return get_range_query (cfun)->range_of_expr (r, x, s) && !r.varying_p ()
+	 && !r.undefined_p ();
+}
+
 // Query the global range of NAME in function F.  Default to cfun.
 extern void gimple_range_global (vrange &v, tree name,
 				 struct function *f = cfun);
diff --git a/gcc/value-range-storage.cc b/gcc/value-range-storage.cc
index 2f82739680c..93bbae3c465 100644
--- a/gcc/value-range-storage.cc
+++ b/gcc/value-range-storage.cc
@@ -277,6 +277,7 @@ void
 irange_storage::set_irange (const irange &r)
 {
   gcc_checking_assert (fits_p (r));
+  m_ovf = r.m_ovf;
 
   if (r.undefined_p ())
     {
@@ -325,6 +326,7 @@ read_wide_int (wide_int &w,
 void
 irange_storage::get_irange (irange &r, tree type) const
 {
+  r.set_overflow (m_ovf);
   if (m_kind == VR_UNDEFINED)
     {
       r.set_undefined ();
diff --git a/gcc/value-range-storage.h b/gcc/value-range-storage.h
index 99fb815cdc2..62a17d73e9f 100644
--- a/gcc/value-range-storage.h
+++ b/gcc/value-range-storage.h
@@ -90,6 +90,7 @@ private:
   unsigned char m_num_ranges;
 
   enum value_range_kind m_kind : 3;
+  wi::overflow_type m_ovf;
 
   // The length of this is m_num_ranges * 2 + 1 to accomodate the nonzero bits.
   HOST_WIDE_INT m_val[1];
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 707b1f15fd4..58aed715658 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -287,6 +287,18 @@ add_vrange (const vrange &v, inchash::hash &hstate,
 
 } //namespace inchash
 
+bool
+irange::nonnegative_p () const
+{
+  return wi::ge_p (lower_bound (), 0, TYPE_SIGN (type ()));
+}
+
+bool
+irange::nonpositive_p () const
+{
+  return wi::le_p (upper_bound (), 0, TYPE_SIGN (type ()));
+}
+
 bool
 irange::supports_type_p (const_tree type) const
 {
@@ -916,6 +928,7 @@ irange::operator= (const irange &src)
   m_type = src.m_type;
   m_kind = src.m_kind;
   m_nonzero_mask = src.m_nonzero_mask;
+  m_ovf = src.m_ovf;
   if (m_max_ranges == 1)
     normalize_kind ();
   if (flag_checking)
@@ -1244,7 +1257,15 @@ irange::union_ (const vrange &v)
     }
 
   if (varying_p ())
-    return false;
+    {
+      if (m_ovf == r.m_ovf || m_ovf == wi::OVF_UNKNOWN)
+	return false;
+      m_ovf = wi::OVF_UNKNOWN;
+      return true;
+    }
+
+  if (m_ovf != r.m_ovf)
+    m_ovf = wi::OVF_UNKNOWN;
 
   if (r.varying_p ())
     {
@@ -1417,14 +1438,16 @@ irange::intersect (const vrange &v)
       set_undefined ();
       return true;
     }
-  if (r.varying_p ())
-    return false;
+
   if (varying_p ())
     {
       operator= (r);
       return true;
     }
 
+  if (r.varying_p ())
+    return false;
+
   if (r.num_pairs () == 1)
     {
       bool res = intersect (r.lower_bound (), r.upper_bound ());
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 2b4ebabe7c8..ae35f6fbcf7 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -145,6 +145,10 @@ public:
   virtual bool singleton_p (tree *result = NULL) const override;
   bool singleton_p (wide_int &) const;
   bool contains_p (const wide_int &) const;
+  bool nonnegative_p () const;
+  bool nonpositive_p () const;
+  bool no_overflow () const { return m_ovf == wi::OVF_NONE; }
+  void set_overflow (wi::overflow_type ovf) { m_ovf = ovf;}
 
   // In-place operators.
   virtual bool union_ (const vrange &) override;
@@ -197,6 +201,7 @@ private:
   unsigned char m_max_ranges;
   tree m_type;
   wide_int m_nonzero_mask;
+  wi::overflow_type m_ovf;
 protected:
   wide_int *m_base;
 };
@@ -839,6 +844,7 @@ irange::irange (wide_int *base, unsigned nranges, bool resizable)
     m_max_ranges (nranges)
 {
   m_base = base;
+  m_ovf = wi::OVF_UNKNOWN;
   set_undefined ();
 }
 
-- 
2.39.3