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 <mli...@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 <mli...@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
>
