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

[Andrew MacLeod <amacleod@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 3218 bytes --]


On 7/17/23 09:45, Jiufu Guo wrote:
>
>>> 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.
>> Ah, yeah - the folding APIs would be a good fit I guess.  I was
>> also looking to have the "new" helpers to be somewhat consistent
>> with the ranger API.
>>
>> So if we had a fold_range overload with either an output argument
>> or a flag that makes it return false on possible overflow that
>> would work I guess?  Since we have a virtual class setup we
>> might be able to provide a default failing method and implement
>> workers for plus and mult (as needed for this patch) as the need
>> arises?
> Thanks for your comments!
> Here is a concern.  The patterns in match.pd may be supported by
> 'vrp' passes. At that time, the range info would be computed (via
> the value-range machinery) and cached for each SSA_NAME. In the
> patterns, when range_of_expr is called for a capture, the range
> info is retrieved from the cache, and no need to fold_range again.
> This means the overflow info may also need to be cached together
> with other range info.  There may be additional memory and time
> cost.
>

I've been thinking about this a little bit, and how to make the info 
available in a useful way.

I wonder if maybe we just add another entry point  to range-ops that 
looks a bit like fold_range ..

   Attached is an (untested) patch which ads overflow_free_p(op1, op2, 
relation)  to rangeops.   It defaults to returning false.  If you want 
to implement it for say plus,  you'd add to operator_plus in 
range-ops.cc  something like

operator_plus::overflow_free_p (irange&op1, irange& op2, relation_kind)
{
    // stuff you do in plus_without_overflow
}

I added relation_kind as  param, but you can ignore it.  maybe it wont 
ever help, but it seems like if we know there is a relation between op1 
and op2 we might be able to someday determine something else?     if 
not, remove it.

Then all you need to do too access it is to go thru range-op_handler.. 
so for instance:

range_op_handler (PLUS_EXPR).overflow_free_p (op1, op2)

It'll work for all types an all tree codes. the dispatch machinery will 
return false unless both op1 and op2 are integral ranges, and then it 
will invoke the appropriate handler, defaulting to returning FALSE.

I also am not a fan of the get_range  routine.  It would be better to 
generally just call range_of_expr, get the results, then handle 
undefined in the new overflow_free_p() routine and return false.  
varying should not need anything special since it will trigger the 
overflow when you do the calculation.

The auxillary routines could go in vr-values.h/cc.  They seem like 
things that simplify_using_ranges could utilize, and when we get to 
integrating simplify_using_ranges better,  what you are doing may end up 
there anyway

Does that work?

Andrew

[-- Attachment #2: ofp.diff --]
[-- Type: text/x-patch, Size: 1895 bytes --]

diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index d1c735ee6aa..f2a863db286 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -366,6 +366,24 @@ range_op_handler::op1_op2_relation (const vrange &lhs) const
     }
 }
 
+bool
+range_op_handler::overflow_free_p (const vrange &lh,
+				   const vrange &rh,
+				   relation_trio rel) const
+{
+  gcc_checking_assert (m_operator);
+  switch (dispatch_kind (lh, lh, rh))
+    {
+      case RO_III:
+	return m_operator->overflow_free_p(as_a <irange> (lh),
+					   as_a <irange> (rh),
+					   rel);
+      default:
+	return false;
+    }
+}
+
+
 
 // Convert irange bitmasks into a VALUE MASK pair suitable for calling CCP.
 
@@ -688,6 +706,13 @@ range_operator::op1_op2_relation_effect (irange &lhs_range ATTRIBUTE_UNUSED,
   return false;
 }
 
+bool
+range_operator::overflow_free_p (const irange &, const irange &,
+				 relation_trio) const
+{
+  return false;
+}
+
 // Apply any known bitmask updates based on this operator.
 
 void
diff --git a/gcc/range-op.h b/gcc/range-op.h
index af94c2756a7..db3b03f28a5 100644
--- a/gcc/range-op.h
+++ b/gcc/range-op.h
@@ -147,6 +147,9 @@ public:
 
   virtual relation_kind op1_op2_relation (const irange &lhs) const;
   virtual relation_kind op1_op2_relation (const frange &lhs) const;
+
+  virtual bool overflow_free_p (const irange &lh, const irange &rh,
+				relation_trio = TRIO_VARYING) const;
 protected:
   // Perform an integral operation between 2 sub-ranges and return it.
   virtual void wi_fold (irange &r, tree type,
@@ -214,6 +217,8 @@ public:
 				  const vrange &op2,
 				  relation_kind = VREL_VARYING) const;
   relation_kind op1_op2_relation (const vrange &lhs) const;
+  bool overflow_free_p (const vrange &lh, const vrange &rh,
+			relation_trio = TRIO_VARYING) const;
 protected:
   unsigned dispatch_kind (const vrange &lhs, const vrange &op1,
 			  const vrange& op2) const;