[COMMITTED] [range-ops] Add tree code to range_operator.

[COMMITTED] [range-ops] Add tree code to range_operator.

[Aldy Hernandez]

This patch adds a tree code to range_operator in order to known which
tree code to pass into bit-CCP.

Up to now range-ops has been free of tree details, with the exception
of the div entries which use a tree code to differentiate between
them.  This is still the goal going forward, but this is a stop-gap
until we can merge the CCP and range-op bit handling in the next
release.

No change in performance.

gcc/ChangeLog:

	* range-op.cc: (range_op_table::set): Set m_code.
	(integral_table::integral_table): Handle shared entries.
	(pointer_table::pointer_table): Same.
	* range-op.h (class range_operator): Add m_code.
---
 gcc/range-op.cc | 37 +++++++++++++++++++++++--------------
 gcc/range-op.h  |  5 +++++
 2 files changed, 28 insertions(+), 14 deletions(-)

diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 8ff5d5b4c78..1fbebd85620 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -2523,7 +2523,7 @@ private:
 			const irange &outer) const;
   void fold_pair (irange &r, unsigned index, const irange &inner,
 			   const irange &outer) const;
-} op_convert;
+};
 
 // Add a partial equivalence between the LHS and op1 for casts.
 
@@ -3877,7 +3877,7 @@ public:
 					   const irange &op1,
 					   const irange &op2,
 					   relation_kind rel) const;
-} op_identity;
+};
 
 // Determine if there is a relationship between LHS and OP1.
 
@@ -3922,7 +3922,7 @@ public:
 			   const irange &op1,
 			   const irange &op2,
 			   relation_trio rel = TRIO_VARYING) const;
-} op_unknown;
+};
 
 bool
 operator_unknown::fold_range (irange &r, tree type,
@@ -4245,7 +4245,7 @@ public:
   virtual void wi_fold (irange & r, tree type,
 			const wide_int &lh_lb, const wide_int &lh_ub,
 			const wide_int &rh_lb, const wide_int &rh_ub) const;
-} op_ptr_min_max;
+};
 
 void
 pointer_min_max_operator::wi_fold (irange &r, tree type,
@@ -4372,8 +4372,17 @@ range_op_table::set (enum tree_code code, range_operator &op)
 {
   gcc_checking_assert (m_range_tree[code] == NULL);
   m_range_tree[code] = &op;
+  gcc_checking_assert (op.m_code == ERROR_MARK || op.m_code == code);
+  op.m_code = code;
 }
 
+// Shared operators that require separate instantiations because they
+// do not share a common tree code.
+static operator_cast op_nop, op_convert;
+static operator_identity op_ssa, op_paren, op_obj_type;
+static operator_unknown op_realpart, op_imagpart;
+static pointer_min_max_operator op_ptr_min, op_ptr_max;
+
 // Instantiate a range op table for integral operations.
 
 class integral_table : public range_op_table
@@ -4402,7 +4411,7 @@ integral_table::integral_table ()
   set (EXACT_DIV_EXPR, op_exact_div);
   set (LSHIFT_EXPR, op_lshift);
   set (RSHIFT_EXPR, op_rshift);
-  set (NOP_EXPR, op_convert);
+  set (NOP_EXPR, op_nop);
   set (CONVERT_EXPR, op_convert);
   set (TRUTH_AND_EXPR, op_logical_and);
   set (BIT_AND_EXPR, op_bitwise_and);
@@ -4413,11 +4422,11 @@ integral_table::integral_table ()
   set (TRUTH_NOT_EXPR, op_logical_not);
   set (BIT_NOT_EXPR, op_bitwise_not);
   set (INTEGER_CST, op_integer_cst);
-  set (SSA_NAME, op_identity);
-  set (PAREN_EXPR, op_identity);
-  set (OBJ_TYPE_REF, op_identity);
-  set (IMAGPART_EXPR, op_unknown);
-  set (REALPART_EXPR, op_unknown);
+  set (SSA_NAME, op_ssa);
+  set (PAREN_EXPR, op_paren);
+  set (OBJ_TYPE_REF, op_obj_type);
+  set (IMAGPART_EXPR, op_imagpart);
+  set (REALPART_EXPR, op_realpart);
   set (POINTER_DIFF_EXPR, op_pointer_diff);
   set (ABS_EXPR, op_abs);
   set (ABSU_EXPR, op_absu);
@@ -4437,8 +4446,8 @@ pointer_table::pointer_table ()
 {
   set (BIT_AND_EXPR, op_pointer_and);
   set (BIT_IOR_EXPR, op_pointer_or);
-  set (MIN_EXPR, op_ptr_min_max);
-  set (MAX_EXPR, op_ptr_min_max);
+  set (MIN_EXPR, op_ptr_min);
+  set (MAX_EXPR, op_ptr_max);
   set (POINTER_PLUS_EXPR, op_pointer_plus);
 
   set (EQ_EXPR, op_equal);
@@ -4447,10 +4456,10 @@ pointer_table::pointer_table ()
   set (LE_EXPR, op_le);
   set (GT_EXPR, op_gt);
   set (GE_EXPR, op_ge);
-  set (SSA_NAME, op_identity);
+  set (SSA_NAME, op_ssa);
   set (INTEGER_CST, op_integer_cst);
   set (ADDR_EXPR, op_addr);
-  set (NOP_EXPR, op_convert);
+  set (NOP_EXPR, op_nop);
   set (CONVERT_EXPR, op_convert);
 
   set (BIT_NOT_EXPR, op_bitwise_not);
diff --git a/gcc/range-op.h b/gcc/range-op.h
index 442a6e1d299..c999b456f62 100644
--- a/gcc/range-op.h
+++ b/gcc/range-op.h
@@ -48,7 +48,9 @@ along with GCC; see the file COPYING3.  If not see
 
 class range_operator
 {
+  friend class range_op_table;
 public:
+  range_operator () : m_code (ERROR_MARK) { }
   // Perform an operation between 2 ranges and return it.
   virtual bool fold_range (irange &r, tree type,
 			   const irange &lh,
@@ -106,6 +108,9 @@ protected:
 			 const wide_int &lh_ub,
 			 const wide_int &rh_lb,
 			 const wide_int &rh_ub) const;
+
+  // Tree code of the range operator or ERROR_MARK if unknown.
+  tree_code m_code;
 };
 
 // Like range_operator above, but for floating point operators.
-- 
2.38.1

[COMMITTED] [range-ops] Use existing tree code for *DIV_EXPR entries.

[Aldy Hernandez]

There is no need for a special tree code in the *DIV_EXPR entries, as
the parent class has one.

gcc/ChangeLog:

	* range-op.cc (class operator_div): Remove tree code.
	(operator_div::wi_op_overflows): Handle EXACT_DIV_EXPR as
	TRUNC_DIV_EXPR.
---
 gcc/range-op.cc | 21 ++++++---------------
 1 file changed, 6 insertions(+), 15 deletions(-)

diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 1fbebd85620..00a736e983d 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -1971,7 +1971,6 @@ operator_mult::wi_fold (irange &r, tree type,
 class operator_div : public cross_product_operator
 {
 public:
-  operator_div (enum tree_code c)  { code = c; }
   virtual void wi_fold (irange &r, tree type,
 		        const wide_int &lh_lb,
 		        const wide_int &lh_ub,
@@ -1983,8 +1982,6 @@ public:
   virtual bool fold_range (irange &r, tree type,
 			   const irange &lh, const irange &rh,
 			   relation_trio trio) const final override;
-private:
-  enum tree_code code;
 };
 
 bool
@@ -1995,7 +1992,7 @@ operator_div::fold_range (irange &r, tree type,
   if (!cross_product_operator::fold_range (r, type, lh, rh, trio))
     return false;
 
-  update_known_bitmask (r, code, lh, rh);
+  update_known_bitmask (r, m_code, lh, rh);
   return true;
 }
 
@@ -2009,13 +2006,9 @@ operator_div::wi_op_overflows (wide_int &res, tree type,
   wi::overflow_type overflow = wi::OVF_NONE;
   signop sign = TYPE_SIGN (type);
 
-  switch (code)
+  switch (m_code)
     {
     case EXACT_DIV_EXPR:
-      // EXACT_DIV_EXPR is implemented as TRUNC_DIV_EXPR in
-      // operator_exact_divide.  No need to handle it here.
-      gcc_unreachable ();
-      break;
     case TRUNC_DIV_EXPR:
       res = wi::div_trunc (w0, w1, sign, &overflow);
       break;
@@ -2091,17 +2084,11 @@ operator_div::wi_fold (irange &r, tree type,
   gcc_checking_assert (!r.undefined_p ());
 }
 
-operator_div op_trunc_div (TRUNC_DIV_EXPR);
-operator_div op_floor_div (FLOOR_DIV_EXPR);
-operator_div op_round_div (ROUND_DIV_EXPR);
-operator_div op_ceil_div (CEIL_DIV_EXPR);
-
 
 class operator_exact_divide : public operator_div
 {
   using range_operator::op1_range;
 public:
-  operator_exact_divide () : operator_div (TRUNC_DIV_EXPR) { }
   virtual bool op1_range (irange &r, tree type,
 			  const irange &lhs,
 			  const irange &op2,
@@ -4382,6 +4369,10 @@ static operator_cast op_nop, op_convert;
 static operator_identity op_ssa, op_paren, op_obj_type;
 static operator_unknown op_realpart, op_imagpart;
 static pointer_min_max_operator op_ptr_min, op_ptr_max;
+static operator_div op_trunc_div;
+static operator_div op_floor_div;
+static operator_div op_round_div;
+static operator_div op_ceil_div;
 
 // Instantiate a range op table for integral operations.
 
-- 
2.38.1

[COMMITTED] [range-ops] Update known bitmasks using CCP for all operators.

[Aldy Hernandez]

Use bit-CCP to calculate bitmasks for all integer operators, instead
of the half-assed job we were doing with just a handful of operators.

This sets us up nicely for tracking known-one bitmasks in the next
release, as all we'll have to do is just store them in the irange.

All in all, this series of patches incur a 1.9% penalty to VRP, with
no measurable difference in overall compile time.  The reason is
three-fold:

(a) There's double dispatch going on.  First, the dispatch for the
range-ops virtuals, and now the switch in bit_value_binop.

(b) The maybe nonzero mask is stored as a tree and there is an endless
back and forth with wide-ints.  This will be a non-issue next release,
when we convert irange to wide-ints.

(c) New functionality has a cost.  We were handling 2 cases (plus
casts).  Now we handle 20.

I can play around with moving the bit_value_binop cases into inlined
methods in the different range-op entries, and see if that improves
anything, but I doubt (a) buys us that much.  Certainly something that
can be done in stage3 if it's measurable in any significant way.

p.s It would be nice in the future to teach the op[12]_range methods about
the masks.

gcc/ChangeLog:

	* range-op.cc (range_operator::fold_range): Call
	update_known_bitmask.
	(operator_bitwise_and::fold_range): Avoid setting nonzero bits
	when range is undefined.
---
 gcc/range-op.cc | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 00a736e983d..9eec46441a3 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -245,6 +245,7 @@ range_operator::fold_range (irange &r, tree type,
       wi_fold_in_parts (r, type, lh.lower_bound (), lh.upper_bound (),
 			rh.lower_bound (), rh.upper_bound ());
       op1_op2_relation_effect (r, type, lh, rh, rel);
+      update_known_bitmask (r, m_code, lh, rh);
       return true;
     }
 
@@ -262,10 +263,12 @@ range_operator::fold_range (irange &r, tree type,
 	if (r.varying_p ())
 	  {
 	    op1_op2_relation_effect (r, type, lh, rh, rel);
+	    update_known_bitmask (r, m_code, lh, rh);
 	    return true;
 	  }
       }
   op1_op2_relation_effect (r, type, lh, rh, rel);
+  update_known_bitmask (r, m_code, lh, rh);
   return true;
 }
 
@@ -2873,7 +2876,7 @@ operator_bitwise_and::fold_range (irange &r, tree type,
 {
   if (range_operator::fold_range (r, type, lh, rh))
     {
-      if (!lh.undefined_p () && !rh.undefined_p ())
+      if (!r.undefined_p () && !lh.undefined_p () && !rh.undefined_p ())
 	r.set_nonzero_bits (wi::bit_and (lh.get_nonzero_bits (),
 					 rh.get_nonzero_bits ()));
       return true;
-- 
2.38.1

[COMMITTED] [range-ops] Avoid unnecessary intersection in update_known_bitmask.

[Aldy Hernandez]

All the work for keeping the maybe nonzero masks up to date is being
done by the bit-CCP code now.  Any bitmask inherent in the range that
range-ops may have calculated has no extra information, so the
intersection is unnecessary.

gcc/ChangeLog:

	* range-op.cc (update_known_bitmask): Avoid unnecessary intersection.
---
 gcc/range-op.cc | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 9eec46441a3..0b01cf48fdf 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -89,10 +89,7 @@ update_known_bitmask (irange &r, tree_code code,
   bit_value_binop (code, sign, prec, &value, &mask,
 		   lh_sign, lh_prec, lh_value, lh_mask,
 		   rh_sign, rh_prec, rh_value, rh_mask);
-
-  int_range<2> tmp (type);
-  tmp.set_nonzero_bits (value | mask);
-  r.intersect (tmp);
+  r.set_nonzero_bits (value | mask);
 }
 
 // Return the upper limit for a type.
-- 
2.38.1

[COMMITTED] [range-ops] Remove specialized fold_range methods for various operators.

[Aldy Hernandez]

Remove some specialized fold_range methods that were merely setting
maybe nonzero masks, as these are now subsumed by the generic version.

gcc/ChangeLog:

	* range-op.cc (operator_mult::fold_range): Remove.
	(operator_div::fold_range): Remove.
	(operator_bitwise_and): Remove.
---
 gcc/range-op.cc | 52 -------------------------------------------------
 1 file changed, 52 deletions(-)

diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 0b01cf48fdf..6fa3b151596 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -1790,13 +1790,9 @@ cross_product_operator::wi_cross_product (irange &r, tree type,
 
 class operator_mult : public cross_product_operator
 {
-  using range_operator::fold_range;
   using range_operator::op1_range;
   using range_operator::op2_range;
 public:
-  virtual bool fold_range (irange &r, tree type,
-			   const irange &lh, const irange &rh,
-			   relation_trio = TRIO_VARYING) const final override;
   virtual void wi_fold (irange &r, tree type,
 		        const wide_int &lh_lb,
 		        const wide_int &lh_ub,
@@ -1815,18 +1811,6 @@ public:
 			  relation_trio) const final override;
 } op_mult;
 
-bool
-operator_mult::fold_range (irange &r, tree type,
-			   const irange &lh, const irange &rh,
-			   relation_trio trio) const
-{
-  if (!cross_product_operator::fold_range (r, type, lh, rh, trio))
-    return false;
-
-  update_known_bitmask (r, MULT_EXPR, lh, rh);
-  return true;
-}
-
 bool
 operator_mult::op1_range (irange &r, tree type,
 			  const irange &lhs, const irange &op2,
@@ -1979,23 +1963,8 @@ public:
   virtual bool wi_op_overflows (wide_int &res, tree type,
 				const wide_int &, const wide_int &)
     const final override;
-  virtual bool fold_range (irange &r, tree type,
-			   const irange &lh, const irange &rh,
-			   relation_trio trio) const final override;
 };
 
-bool
-operator_div::fold_range (irange &r, tree type,
-			  const irange &lh, const irange &rh,
-			  relation_trio trio) const
-{
-  if (!cross_product_operator::fold_range (r, type, lh, rh, trio))
-    return false;
-
-  update_known_bitmask (r, m_code, lh, rh);
-  return true;
-}
-
 bool
 operator_div::wi_op_overflows (wide_int &res, tree type,
 			       const wide_int &w0, const wide_int &w1) const
@@ -2834,14 +2803,9 @@ operator_logical_and::op2_range (irange &r, tree type,
 
 class operator_bitwise_and : public range_operator
 {
-  using range_operator::fold_range;
   using range_operator::op1_range;
   using range_operator::op2_range;
 public:
-  virtual bool fold_range (irange &r, tree type,
-			   const irange &lh,
-			   const irange &rh,
-			   relation_trio rel = TRIO_VARYING) const;
   virtual bool op1_range (irange &r, tree type,
 			  const irange &lhs,
 			  const irange &op2,
@@ -2865,22 +2829,6 @@ private:
 				const irange &op2) const;
 } op_bitwise_and;
 
-bool
-operator_bitwise_and::fold_range (irange &r, tree type,
-				  const irange &lh,
-				  const irange &rh,
-				  relation_trio) const
-{
-  if (range_operator::fold_range (r, type, lh, rh))
-    {
-      if (!r.undefined_p () && !lh.undefined_p () && !rh.undefined_p ())
-	r.set_nonzero_bits (wi::bit_and (lh.get_nonzero_bits (),
-					 rh.get_nonzero_bits ()));
-      return true;
-    }
-  return false;
-}
-
 
 // Optimize BIT_AND_EXPR, BIT_IOR_EXPR and BIT_XOR_EXPR of signed types
 // by considering the number of leading redundant sign bit copies.
-- 
2.38.1