Division Optimization in match and simplify

[Marc Glisse]

+/* Optimize (X & (-A)) / A where A is a power of 2, to X >> log2(A) */
+(for div (exact_div trunc_div)

Actually, it probably works for all integer divisions (floor_div, etc) 
since it is exact and thus does not depend on the rounding.

(sorry for giving the comments small piece by small piece, I write them as 
I think of them...)

+ (simplify
+  (div (convert? (bit_and @0 INTEGER_CST@1)) INTEGER_CST@2)
+  (if (integer_pow2p (@2)
+       && tree_int_cst_sign_bit (@2) == 0

I think the previous test tree_int_cst_sgn > 0 was better: for unsigned, 
it is ok if that bit is set, it is only for signed that we want to avoid 
-1/-1 which gives 1 (while a shift by 31 would give -1, except that 
wi::exact_log2 might return -1 so we would end up with a negative shift).

(actually, we could generate (unsigned)x>>31 in that case, but let's 
forget it for now)

+       && wi::add (@2, @1) == 0
+       && tree_nop_conversion_p (type, TREE_TYPE (@0)))
+   (rshift (convert @0) { build_int_cst (integer_type_node, wi::exact_log2 (@2)); }))))

(does this fit in 80 cols?)

Note that if we port the following to match.pd from wherever it currently 
is, the 'convert?' becomes much less useful on this transformation

(simplify
  (convert (bit_and:s @0 INTEGER_CST@1))
  (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))
   (bit_and (convert @0) (convert @1))))

-- 
Marc Glisse