diff options
| author | Marc Glisse <marc.glisse@inria.fr> | 2020-08-10 12:50:42 +0200 |
|---|---|---|
| committer | Marc Glisse <marc.glisse@inria.fr> | 2020-08-10 12:53:01 +0200 |
| commit | 287522613d661b4c5ba8403b051eb470c1674cba (patch) | |
| tree | f9c3ea8dfe1d1a8e89a20f898746d93f96a9de4d /gcc/match.pd | |
| parent | 9939be5758b52ed2fe1a7e56b94ce6d0f4d81580 (diff) | |
| download | gcc-287522613d661b4c5ba8403b051eb470c1674cba.zip gcc-287522613d661b4c5ba8403b051eb470c1674cba.tar.gz gcc-287522613d661b4c5ba8403b051eb470c1674cba.tar.bz2 | |
Simplify X * C1 == C2 with wrapping overflow
Odd numbers are invertible in Z / 2^n Z, so X * C1 == C2 can be rewritten
as X == C2 * inv(C1) when overflow wraps.
mod_inv should probably be updated to better match the other wide_int
functions, but that's a separate issue.
2020-08-10 Marc Glisse <marc.glisse@inria.fr>
PR tree-optimization/95433
* match.pd (X * C1 == C2): Handle wrapping overflow.
* expr.c (maybe_optimize_mod_cmp): Qualify call to mod_inv.
(mod_inv): Move...
* wide-int.cc (mod_inv): ... here.
* wide-int.h (mod_inv): Declare it.
* gcc.dg/tree-ssa/pr95433-2.c: New file.
Diffstat (limited to 'gcc/match.pd')
| -rw-r--r-- | gcc/match.pd | 19 |
1 files changed, 17 insertions, 2 deletions
diff --git a/gcc/match.pd b/gcc/match.pd index 7e5c5a6..c3b8816 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -3828,7 +3828,9 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (cmp @0 @2)))))) /* For integral types with undefined overflow fold - x * C1 == C2 into x == C2 / C1 or false. */ + x * C1 == C2 into x == C2 / C1 or false. + If overflow wraps and C1 is odd, simplify to x == C2 / C1 in the ring + Z / 2^n Z. */ (for cmp (eq ne) (simplify (cmp (mult @0 INTEGER_CST@1) INTEGER_CST@2) @@ -3839,7 +3841,20 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (if (wi::multiple_of_p (wi::to_widest (@2), wi::to_widest (@1), TYPE_SIGN (TREE_TYPE (@0)), ")) (cmp @0 { wide_int_to_tree (TREE_TYPE (@0), quot); }) - { constant_boolean_node (cmp == NE_EXPR, type); }))))) + { constant_boolean_node (cmp == NE_EXPR, type); })) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) + && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)) + && (wi::bit_and (wi::to_wide (@1), 1) == 1)) + (cmp @0 + { + tree itype = TREE_TYPE (@0); + int p = TYPE_PRECISION (itype); + wide_int m = wi::one (p + 1) << p; + wide_int a = wide_int::from (wi::to_wide (@1), p + 1, UNSIGNED); + wide_int i = wide_int::from (wi::mod_inv (a, m), + p, TYPE_SIGN (itype)); + wide_int_to_tree (itype, wi::mul (i, wi::to_wide (@2))); + }))))) /* Simplify comparison of something with itself. For IEEE floating-point, we can only do some of these simplifications. */ |