Re: [PATCH (3/7)] Widening multiply-and-accumulate pattern matching

[Richard Guenther <richard.guenther@gmail.com>]

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

On Thu, Jul 7, 2011 at 2:28 PM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Thu, Jul 7, 2011 at 1:43 PM, Andrew Stubbs <andrew.stubbs@gmail.com> wrote:
>> On 07/07/11 11:26, Andrew Stubbs wrote:
>>>
>>> On 07/07/11 10:58, Richard Guenther wrote:
>>>>
>>>> I think you should assume that series of widenings,
>>>> (int)(short)char_variable
>>>> are already combined.  Thus I believe you only need to consider a single
>>>> conversion in valid_types_for_madd_p.
>>>
>>> Hmm, I'm not so sure. I'll look into it a bit further.
>>
>> OK, here's a test case that gives multiple conversions:
>>
>>  long long
>>  foo (long long a, signed char b, signed char c)
>>  {
>>    int bc = b * c;
>>    return a + (short)bc;
>>  }
>>
>> The dump right before the widen_mult pass gives:
>>
>>  foo (long long int a, signed char b, signed char c)
>>  {
>>    int bc;
>>    long long int D.2018;
>>    short int D.2017;
>>    long long int D.2016;
>>    int D.2015;
>>    int D.2014;
>>
>>  <bb 2>:
>>    D.2014_2 = (int) b_1(D);
>>    D.2015_4 = (int) c_3(D);
>>    bc_5 = D.2014_2 * D.2015_4;
>>    D.2017_6 = (short int) bc_5;
>
> Ok, so you have a truncation that is a no-op value-wise.  I would
> argue that this truncation should be removed independent on
> whether we have a widening multiply instruction or not.
>
> The technically most capable place to remove non-value-changing
> truncations (and combine them with a successive conversion)
> would be value-range propagation.  Which already knows:
>
> Value ranges after VRP:
>
> b_1(D): VARYING
> D.2698_2: [-128, 127]
> c_3(D): VARYING
> D.2699_4: [-128, 127]
> bc_5: [-16256, 16384]
> D.2701_6: [-16256, 16384]
> D.2702_7: [-16256, 16384]
> a_8(D): VARYING
> D.2700_9: VARYING
>
> thus truncating bc_5 to short does not change the value.
>
> The simplification could be made when looking at the
> statement
>
>>    D.2018_7 = (long long int) D.2017_6;
>
> in vrp_fold_stmt, based on the fact that this conversion
> converts from a value-preserving intermediate conversion.
> Thus the transform would replace the D.2017_6 operand
> with bc_5.
>
> So yes, the case appears - but it shouldn't ;)
>
> I'll cook up a quick patch for VRP.

Like the attached.  I'll finish and properly test it.

Richard.

[-- Attachment #2: p --]
[-- Type: application/octet-stream, Size: 10194 bytes --]

Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c	(revision 175962)
+++ gcc/tree-vrp.c	(working copy)
@@ -161,10 +161,10 @@ static VEC (switch_update, heap) *to_upd
 static inline tree
 vrp_val_max (const_tree type)
 {
-  if (!INTEGRAL_TYPE_P (type))
-    return NULL_TREE;
+  if (INTEGRAL_TYPE_P (type))
+    return upper_bound_in_type (CONST_CAST_TREE (type), CONST_CAST_TREE (type));
 
-  return TYPE_MAX_VALUE (type);
+  return NULL_TREE;
 }
 
 /* Return the minimum value for TYPE.  */
@@ -172,10 +172,10 @@ vrp_val_max (const_tree type)
 static inline tree
 vrp_val_min (const_tree type)
 {
-  if (!INTEGRAL_TYPE_P (type))
-    return NULL_TREE;
+  if (INTEGRAL_TYPE_P (type))
+    return lower_bound_in_type (CONST_CAST_TREE (type), CONST_CAST_TREE (type));
 
-  return TYPE_MIN_VALUE (type);
+  return NULL_TREE;
 }
 
 /* Return whether VAL is equal to the maximum value of its type.  This
@@ -565,7 +565,7 @@ set_value_range_to_nonnegative (value_ra
   set_value_range (vr, VR_RANGE, zero,
 		   (overflow_infinity
 		    ? positive_overflow_infinity (type)
-		    : TYPE_MAX_VALUE (type)),
+		    : vrp_val_max (type)),
 		   vr->equiv);
 }
 
@@ -1627,7 +1627,7 @@ extract_range_from_assert (value_range_t
     }
   else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
     {
-      min = TYPE_MIN_VALUE (type);
+      min = vrp_val_min (type);
 
       if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
 	max = limit;
@@ -1662,7 +1662,7 @@ extract_range_from_assert (value_range_t
     }
   else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
     {
-      max = TYPE_MAX_VALUE (type);
+      max = vrp_val_max (type);
 
       if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
 	min = limit;
@@ -2079,11 +2079,11 @@ vrp_int_const_binop (enum tree_code code
 	  || code == ROUND_DIV_EXPR)
 	return (needs_overflow_infinity (TREE_TYPE (res))
 		? positive_overflow_infinity (TREE_TYPE (res))
-		: TYPE_MAX_VALUE (TREE_TYPE (res)));
+		: vrp_val_max (TREE_TYPE (res)));
       else
 	return (needs_overflow_infinity (TREE_TYPE (res))
 		? negative_overflow_infinity (TREE_TYPE (res))
-		: TYPE_MIN_VALUE (TREE_TYPE (res)));
+		: vrp_val_min (TREE_TYPE (res)));
     }
 
   return res;
@@ -2888,8 +2888,8 @@ extract_range_from_unary_expr (value_ran
 	  && TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type))
 	{
 	  vr0.type = VR_RANGE;
-	  vr0.min = TYPE_MIN_VALUE (inner_type);
-	  vr0.max = TYPE_MAX_VALUE (inner_type);
+	  vr0.min = vrp_val_min (inner_type);
+	  vr0.max = vrp_val_max (inner_type);
 	}
 
       /* If VR0 is a constant range or anti-range and the conversion is
@@ -2974,7 +2974,7 @@ extract_range_from_unary_expr (value_ran
 	    }
 	}
       else
-	min = TYPE_MIN_VALUE (type);
+	min = vrp_val_min (type);
 
       if (is_positive_overflow_infinity (vr0.min))
 	max = negative_overflow_infinity (type);
@@ -2993,7 +2993,7 @@ extract_range_from_unary_expr (value_ran
 	    }
 	}
       else
-	max = TYPE_MIN_VALUE (type);
+	max = vrp_val_min (type);
     }
   else if (code == NEGATE_EXPR
 	   && TYPE_UNSIGNED (type))
@@ -3035,7 +3035,7 @@ extract_range_from_unary_expr (value_ran
       else if (!vrp_val_is_min (vr0.min))
 	min = fold_unary_to_constant (code, type, vr0.min);
       else if (!needs_overflow_infinity (type))
-	min = TYPE_MAX_VALUE (type);
+	min = vrp_val_max (type);
       else if (supports_overflow_infinity (type))
 	min = positive_overflow_infinity (type);
       else
@@ -3049,7 +3049,7 @@ extract_range_from_unary_expr (value_ran
       else if (!vrp_val_is_min (vr0.max))
 	max = fold_unary_to_constant (code, type, vr0.max);
       else if (!needs_overflow_infinity (type))
-	max = TYPE_MAX_VALUE (type);
+	max = vrp_val_max (type);
       else if (supports_overflow_infinity (type)
 	       /* We shouldn't generate [+INF, +INF] as set_value_range
 		  doesn't like this and ICEs.  */
@@ -3079,7 +3079,7 @@ extract_range_from_unary_expr (value_ran
 	         TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE.  */
 	      if (TYPE_OVERFLOW_WRAPS (type))
 		{
-		  tree type_min_value = TYPE_MIN_VALUE (type);
+		  tree type_min_value = vrp_val_min (type);
 
 		  min = (vr0.min != type_min_value
 			 ? int_const_binop (PLUS_EXPR, type_min_value,
@@ -3091,7 +3091,7 @@ extract_range_from_unary_expr (value_ran
 		  if (overflow_infinity_range_p (&vr0))
 		    min = negative_overflow_infinity (type);
 		  else
-		    min = TYPE_MIN_VALUE (type);
+		    min = vrp_val_min (type);
 		}
 	    }
 	  else
@@ -3112,7 +3112,7 @@ extract_range_from_unary_expr (value_ran
 		    }
 		}
 	      else
-		max = TYPE_MAX_VALUE (type);
+		max = vrp_val_max (type);
 	    }
 	}
 
@@ -3396,11 +3396,11 @@ adjust_range_with_scev (value_range_t *v
   if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
     tmin = lower_bound_in_type (type, type);
   else
-    tmin = TYPE_MIN_VALUE (type);
+    tmin = vrp_val_min (type);
   if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
     tmax = upper_bound_in_type (type, type);
   else
-    tmax = TYPE_MAX_VALUE (type);
+    tmax = vrp_val_max (type);
 
   /* Try to use estimated number of iterations for the loop to constrain the
      final value in the evolution.  */
@@ -4318,8 +4318,8 @@ extract_code_and_val_from_cond_with_ops
   if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
       && INTEGRAL_TYPE_P (TREE_TYPE (val)))
     {
-      tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
-      tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
+      tree min = vrp_val_min (TREE_TYPE (val));
+      tree max = vrp_val_max (TREE_TYPE (val));
 
       if (comp_code == GT_EXPR
 	  && (!max
@@ -6685,7 +6685,7 @@ vrp_visit_phi_node (gimple phi)
 	{
 	  if (!needs_overflow_infinity (TREE_TYPE (vr_result.min))
 	      || !vrp_var_may_overflow (lhs, phi))
-	    vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
+	    vr_result.min = vrp_val_min (TREE_TYPE (vr_result.min));
 	  else if (supports_overflow_infinity (TREE_TYPE (vr_result.min)))
 	    vr_result.min =
 		negative_overflow_infinity (TREE_TYPE (vr_result.min));
@@ -6697,7 +6697,7 @@ vrp_visit_phi_node (gimple phi)
 	{
 	  if (!needs_overflow_infinity (TREE_TYPE (vr_result.max))
 	      || !vrp_var_may_overflow (lhs, phi))
-	    vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
+	    vr_result.max = vrp_val_max (TREE_TYPE (vr_result.max));
 	  else if (supports_overflow_infinity (TREE_TYPE (vr_result.max)))
 	    vr_result.max =
 		positive_overflow_infinity (TREE_TYPE (vr_result.max));
@@ -7119,7 +7119,7 @@ test_for_singularity (enum tree_code con
     {
       /* This should not be negative infinity; there is no overflow
 	 here.  */
-      min = TYPE_MIN_VALUE (TREE_TYPE (op0));
+      min = vrp_val_min (TREE_TYPE (op0));
 
       max = op1;
       if (cond_code == LT_EXPR && !is_overflow_infinity (max))
@@ -7134,7 +7134,7 @@ test_for_singularity (enum tree_code con
     {
       /* This should not be positive infinity; there is no overflow
 	 here.  */
-      max = TYPE_MAX_VALUE (TREE_TYPE (op0));
+      max = vrp_val_max (TREE_TYPE (op0));
 
       min = op1;
       if (cond_code == GT_EXPR && !is_overflow_infinity (min))
@@ -7342,6 +7342,33 @@ simplify_switch_using_ranges (gimple stm
   return false;
 }
 
+/* Simplify an integral conversion from an SSA name in STMT.  */
+
+static bool
+simplify_conversion_using_ranges (gimple stmt)
+{
+  tree rhs1 = gimple_assign_rhs1 (stmt);
+  tree type = TREE_TYPE (gimple_assign_lhs (stmt));
+  gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
+  value_range_t *vr;
+
+  if (!is_gimple_assign (def_stmt)
+      || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
+    return false;
+  rhs1 = gimple_assign_rhs1 (def_stmt);
+  if (TREE_CODE (rhs1) != SSA_NAME)
+    return false;
+  vr = get_value_range (rhs1);
+  if (vr->type != VR_RANGE)
+    return false;
+  if (!int_fits_type_p (vr->min, type)
+      || !int_fits_type_p (vr->max, type))
+    return false;
+  gimple_assign_set_rhs1 (stmt, rhs1);
+  update_stmt (stmt);
+  return true;
+}
+
 /* Simplify STMT using ranges if possible.  */
 
 static bool
@@ -7351,6 +7378,7 @@ simplify_stmt_using_ranges (gimple_stmt_
   if (is_gimple_assign (stmt))
     {
       enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
+      tree rhs1 = gimple_assign_rhs1 (stmt);
 
       switch (rhs_code)
 	{
@@ -7364,7 +7392,7 @@ simplify_stmt_using_ranges (gimple_stmt_
 	     or identity if the RHS is zero or one, and the LHS are known
 	     to be boolean values.  Transform all TRUTH_*_EXPR into
              BIT_*_EXPR if both arguments are known to be boolean values.  */
-	  if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))
+	  if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
 	    return simplify_truth_ops_using_ranges (gsi, stmt);
 	  break;
 
@@ -7373,15 +7401,15 @@ simplify_stmt_using_ranges (gimple_stmt_
 	 than zero and the second operand is an exact power of two.  */
 	case TRUNC_DIV_EXPR:
 	case TRUNC_MOD_EXPR:
-	  if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))
+	  if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
 	      && integer_pow2p (gimple_assign_rhs2 (stmt)))
 	    return simplify_div_or_mod_using_ranges (stmt);
 	  break;
 
       /* Transform ABS (X) into X or -X as appropriate.  */
 	case ABS_EXPR:
-	  if (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
-	      && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))
+	  if (TREE_CODE (rhs1) == SSA_NAME
+	      && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
 	    return simplify_abs_using_ranges (stmt);
 	  break;
 
@@ -7390,10 +7418,16 @@ simplify_stmt_using_ranges (gimple_stmt_
 	  /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR
 	     if all the bits being cleared are already cleared or
 	     all the bits being set are already set.  */
-	  if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))
+	  if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
 	    return simplify_bit_ops_using_ranges (gsi, stmt);
 	  break;
 
+	CASE_CONVERT:
+	  if (TREE_CODE (rhs1) == SSA_NAME
+	      && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
+	    return simplify_conversion_using_ranges (stmt);
+	  break;
+
 	default:
 	  break;
 	}