# Division Optimization in match and simplify

Marc Glisse marc.glisse@inria.fr
Wed Nov 4 12:46:00 GMT 2015

```On Wed, 4 Nov 2015, Richard Biener wrote:

>> I don't really remember what the tests !TYPE_UNSIGNED (type) and
>> tree_int_cst_sgn are for in the other pattern, but since you are only moving
>> the transformation...
>
> +/* Optimize (X & (-A)) / A where A is a power of 2, to X >> log2(A) */
> +(for div (exact_div trunc_div)
> + (simplify
> +  (div (bit_and @0 INTEGER_CST@1) INTEGER_CST@2)
> +  (if (!TYPE_UNSIGNED (type) && integer_pow2p (@2)
> +       && tree_int_cst_sgn (@2) > 0
> +       && wi::add (@2, @1) == 0)
> +   (rshift @0 { build_int_cst (integer_type_node, wi::exact_log2 (@2)); }))))
>
> the TYPE_UNSIGNED test is because right shift of negative values is undefined,

tree.def: "Shift means logical shift if done on an unsigned type, arithmetic shift if done on a signed type."
To me, this implies that right shift of negative values is well-defined
inside gcc.
Also, the test allows *only signed types*, not unsigned.

> so is a shift with a negative value.  I believe we can safely handle
> conversions here
> just like fold-const.c does with
>
> (div (convert? (bit_and @0 INTEGER_CST@1) INTEGER_CST@2)
> (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))
>  ...
>
> With that the pattern looks ok to me.

As long as it comes with (convert @0) in the result... I think the
fold-const.c pattern is lucky that (int)(x&-4u) gets folded to
(int)x&-4, or it might ICE for ((int)(x&-4u))/4.

--
Marc Glisse

```