Re: [PATCH] Switch conversion: support any ax + b transformation (PR tree-optimization/84436).

[Martin Liška <mliska at suse dot cz>]

On 10/17/18 12:39 AM, Jeff Law wrote:
> On 10/11/18 6:56 AM, Martin Liška wrote:
>> Hi.
>>
>> As seen in the PR, switch conversion can do better when we return equal numbers
>> based on index value. I implemented more than that, more precisely I support all linear
>> transformation based on index value. It's the same what clang is capable of.
>>
>> Patch survives testing on x86_64-linux-gnu. I added various tests that should
>> benefit of the transformation.
>>
>> Thanks,
>> Martin
>>
>> gcc/ChangeLog:
>>
>> 2018-10-11  Martin Liska  <mliska@suse.cz>
>>
>> 	PR tree-optimization/84436
>> 	* tree-switch-conversion.c (switch_conversion::contains_same_values_p):
>> 	Remove.
>> 	(switch_conversion::contains_linear_function_p): New.
>> 	(switch_conversion::build_one_array): Support linear
>> 	transformation on input.
>> 	* tree-switch-conversion.h (struct switch_conversion): Add
>> 	contains_linear_function_p declaration.
>>
>> gcc/testsuite/ChangeLog:
>>
>> 2018-10-11  Martin Liska  <mliska@suse.cz>
>>
>> 	PR tree-optimization/84436
>> 	* gcc.dg/tree-ssa/pr84436-1.c: New test.
>> 	* gcc.dg/tree-ssa/pr84436-2.c: New test.
>> 	* gcc.dg/tree-ssa/pr84436-3.c: New test.
>> 	* gcc.dg/tree-ssa/pr84436-4.c: New test.
>> 	* gcc.dg/tree-ssa/pr84436-5.c: New test.
>> ---
>>
>>
>>
>> diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
>> index 64169a6cd3d..8f34ab45cb9 100644
>> --- a/gcc/tree-switch-conversion.c
>> +++ b/gcc/tree-switch-conversion.c
>> @@ -439,25 +439,63 @@ switch_conversion::build_constructors ()
>>      }
>>  }
>>  
>> -/* If all values in the constructor vector are the same, return the value.
>> -   Otherwise return NULL_TREE.  Not supposed to be called for empty
>> -   vectors.  */
>> +/* If all values in the constructor vector are products of a linear function
>> +   a * x + b, then return true.  When true, COEFF_A and COEFF_B and
>> +   coefficients of the linear function.  Note that equal values are special
>> +   case of a linear function with a and b equal to zero.  */
>>  
>> -tree
>> -switch_conversion::contains_same_values_p (vec<constructor_elt, va_gc> *vec)
>> +bool
>> +switch_conversion::contains_linear_function_p (vec<constructor_elt, va_gc> *vec,
>> +					       wide_int *coeff_a,
>> +					       wide_int *coeff_b)
>>  {
>>    unsigned int i;
>> -  tree prev = NULL_TREE;
>>    constructor_elt *elt;
>>  
>> +  gcc_assert (vec->length () >= 2);
>> +
>> +  /* Let's try to find any linear function a.x + y that can apply to
>> +     given values. 'a' can be calculated as follows:
>> +
>> +     a = (y2 - y1) / (x2 - x1) where x2 - x1 = 1 (consecutive case indices)
>> +     a = y2 - y1
>> +
>> +     and
>> +
>> +     b = y2 - a * x2
>> +
>> +  */
>> +
>> +  tree elt0 = (*vec)[0].value;
>> +  tree elt1 = (*vec)[1].value;
>> +
>> +  if (TREE_CODE (elt0) != INTEGER_CST || TREE_CODE (elt1) != INTEGER_CST)
>> +    return false;
>> +
>> +  wide_int range_min = wi::to_wide (fold_convert (TREE_TYPE (elt0),
>> +						  m_range_min));
>> +  wide_int y1 = wi::to_wide (elt0);
>> +  wide_int y2 = wi::to_wide (elt1);
>> +  wide_int a = y2 - y1;
>> +  wide_int b = y2 - a * (range_min + 1);
>> +
>> +  /* Verify that all values fulfill the linear function.  */
>>    FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
>>      {
>> -      if (!prev)
>> -	prev = elt->value;
>> -      else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
>> -	return NULL_TREE;
>> +      if (TREE_CODE (elt->value) != INTEGER_CST)
>> +	return false;
>> +
>> +      wide_int value = wi::to_wide (elt->value);
>> +      if (a * range_min + b != value)
>> +	return false;
> ISTM that if we overflow the ax + b, then we're not going to be equal to
> value here, right?

No, I want to support overflowing values as seen in gcc/testsuite/gcc.dg/tree-ssa/pr84436-4.c.
I provided some explanation in email I've just sent.

Martin

 I think Jakub and at least someone else was
> concerned about that possibility.
> 
> Assuming overflow isn't a problem, this is OK.
> 
> jeff
>