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? I think Jakub and at least someone else was
concerned about that possibility.
Assuming overflow isn't a problem, this is OK.
jeff
