commit 65e4c9ed1bcfd3259f639052ceabf144b67ac646 Author: Bin Cheng Date: Thu May 20 15:26:07 2021 +0800 Make function multiple_of_p aware of wrap behavior. The function was designed mostly for use if TOP doesn't wrap, this patch relaxed the restriction by introducing new parameter NO_WRAP. It also changes two callers accordingly. gcc: PR tree-optimization/100499 * fold-const.c (multiple_of_p): New parameter. Check may wrap behavior. * fold-const.h (multiple_of_p): New parameter. * stor-layout.c (handle_warn_if_not_align): Pass new argument indicating no wrap would happen. * tree-ssa-loop-niter.c (number_of_iterations_ne): Adjust checking on multiple_of_p by handling properly. gcc/testsuite: PR tree-optimization/100499 * gcc.c-torture/execute/pr100499.c: New test. diff --git a/gcc/fold-const.c b/gcc/fold-const.c index 5a41524702b..41ba07014ed 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -13967,10 +13967,15 @@ fold_build_call_array_initializer_loc (location_t loc, tree type, tree fn, SAVE_EXPR (I) * SAVE_EXPR (J) (where the same SAVE_EXPR (J) is used in the original and the - transformed version). */ + transformed version). + + Before introducing NO_WRAP, this function didn't check if TOP could wrap + because of overflow or not, and it was mostly for use in case that TOP + doesn't overflow/wrap. Now it only assumes TOP doesn't overflow/wrap if + NO_WRAP is true. */ int -multiple_of_p (tree type, const_tree top, const_tree bottom) +multiple_of_p (tree type, const_tree top, const_tree bottom, bool no_wrap) { gimple *stmt; tree t1, op1, op2; @@ -13988,10 +13993,15 @@ multiple_of_p (tree type, const_tree top, const_tree bottom) a multiple of BOTTOM then TOP is a multiple of BOTTOM. */ if (!integer_pow2p (bottom)) return 0; - return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom) - || multiple_of_p (type, TREE_OPERAND (top, 0), bottom)); + return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom, no_wrap) + || multiple_of_p (type, TREE_OPERAND (top, 0), bottom, no_wrap)); case MULT_EXPR: + if (!no_wrap && TYPE_OVERFLOW_WRAPS (type) + /* Overflow/wrap doesn't matter if the 2nd operand is power of 2. */ + && !integer_pow2p (TREE_OPERAND (top, 1))) + return false; + if (TREE_CODE (bottom) == INTEGER_CST) { op1 = TREE_OPERAND (top, 0); @@ -14000,7 +14010,7 @@ multiple_of_p (tree type, const_tree top, const_tree bottom) std::swap (op1, op2); if (TREE_CODE (op2) == INTEGER_CST) { - if (multiple_of_p (type, op2, bottom)) + if (multiple_of_p (type, op2, bottom, no_wrap)) return 1; /* Handle multiple_of_p ((x * 2 + 2) * 4, 8). */ if (multiple_of_p (type, bottom, op2)) @@ -14010,33 +14020,28 @@ multiple_of_p (tree type, const_tree top, const_tree bottom) if (wi::fits_to_tree_p (w, TREE_TYPE (bottom))) { op2 = wide_int_to_tree (TREE_TYPE (bottom), w); - return multiple_of_p (type, op1, op2); + return multiple_of_p (type, op1, op2, no_wrap); } } - return multiple_of_p (type, op1, bottom); + return multiple_of_p (type, op1, bottom, no_wrap); } } - return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom) - || multiple_of_p (type, TREE_OPERAND (top, 0), bottom)); + return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom, no_wrap) + || multiple_of_p (type, TREE_OPERAND (top, 0), bottom, no_wrap)); case MINUS_EXPR: - /* It is impossible to prove if op0 - op1 is multiple of bottom + case PLUS_EXPR: + if (!no_wrap && TYPE_OVERFLOW_WRAPS (type) + /* Overflow/wrap doesn't matter if the 2nd operand is power of 2. */ + && !integer_pow2p (TREE_OPERAND (top, 1))) + return false; + + /* It is impossible to prove if op0 -/+ op1 is multiple of bottom precisely, so be conservative here checking if both op0 and op1 are multiple of bottom. Note we check the second operand first since it's usually simpler. */ - return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom) - && multiple_of_p (type, TREE_OPERAND (top, 0), bottom)); - - case PLUS_EXPR: - /* The same as MINUS_EXPR, but handle cases like op0 + 0xfffffffd - as op0 - 3 if the expression has unsigned type. For example, - (X / 3) + 0xfffffffd is multiple of 3, but 0xfffffffd is not. */ - op1 = TREE_OPERAND (top, 1); - if (TYPE_UNSIGNED (type) - && TREE_CODE (op1) == INTEGER_CST && tree_int_cst_sign_bit (op1)) - op1 = fold_build1 (NEGATE_EXPR, type, op1); - return (multiple_of_p (type, op1, bottom) - && multiple_of_p (type, TREE_OPERAND (top, 0), bottom)); + return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom, no_wrap) + && multiple_of_p (type, TREE_OPERAND (top, 0), bottom, no_wrap)); case LSHIFT_EXPR: if (TREE_CODE (TREE_OPERAND (top, 1)) == INTEGER_CST) @@ -14050,7 +14055,7 @@ multiple_of_p (tree type, const_tree top, const_tree bottom) const_binop (LSHIFT_EXPR, size_one_node, op1))) != 0 && !TREE_OVERFLOW (t1)) - return multiple_of_p (type, t1, bottom); + return multiple_of_p (type, t1, bottom, no_wrap); } return 0; @@ -14064,11 +14069,11 @@ multiple_of_p (tree type, const_tree top, const_tree bottom) /* fall through */ case SAVE_EXPR: - return multiple_of_p (type, TREE_OPERAND (top, 0), bottom); + return multiple_of_p (type, TREE_OPERAND (top, 0), bottom, no_wrap); case COND_EXPR: - return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom) - && multiple_of_p (type, TREE_OPERAND (top, 2), bottom)); + return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom, no_wrap) + && multiple_of_p (type, TREE_OPERAND (top, 2), bottom, no_wrap)); case INTEGER_CST: if (TREE_CODE (bottom) != INTEGER_CST diff --git a/gcc/fold-const.h b/gcc/fold-const.h index 2a74287c131..1e0937b75fe 100644 --- a/gcc/fold-const.h +++ b/gcc/fold-const.h @@ -94,7 +94,7 @@ extern void fold_overflow_warning (const char*, enum warn_strict_overflow_code); extern enum tree_code fold_div_compare (enum tree_code, tree, tree, tree *, tree *, bool *); extern bool operand_equal_p (const_tree, const_tree, unsigned int flags = 0); -extern int multiple_of_p (tree, const_tree, const_tree); +extern int multiple_of_p (tree, const_tree, const_tree, bool = false); #define omit_one_operand(T1,T2,T3)\ omit_one_operand_loc (UNKNOWN_LOCATION, T1, T2, T3) extern tree omit_one_operand_loc (location_t, tree, tree, tree); diff --git a/gcc/stor-layout.c b/gcc/stor-layout.c index 94b8b21c7a8..50fccc71984 100644 --- a/gcc/stor-layout.c +++ b/gcc/stor-layout.c @@ -1184,7 +1184,8 @@ handle_warn_if_not_align (tree field, unsigned int record_align) record_align, context, warn_if_not_align); tree off = byte_position (field); - if (!multiple_of_p (TREE_TYPE (off), off, size_int (warn_if_not_align))) + if (!multiple_of_p (TREE_TYPE (off), off, size_int (warn_if_not_align), + /* bool no_wrap = */true)) { if (TREE_CODE (off) == INTEGER_CST) warning (opt_w, "%q+D offset %E in %qT isn%'t aligned to %u", diff --git a/gcc/testsuite/gcc.c-torture/execute/pr100499.c b/gcc/testsuite/gcc.c-torture/execute/pr100499.c new file mode 100644 index 00000000000..555c9d3dd92 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr100499.c @@ -0,0 +1,32 @@ +/* { dg-options "-O1 -fpeel-loops -ftree-loop-vectorize" } */ + +#include +typedef unsigned short uint16_t; +typedef signed int int32_t; +static uint16_t g_2823 = 0xEC75L; +static uint16_t g_116 = 0xBC07L; + +static uint16_t +(safe_mul_func_uint16_t_u_u)(uint16_t ui1, uint16_t ui2 ) +{ + + return ((unsigned int)ui1) * ((unsigned int)ui2); +} + +int main (int argc, char* argv[]) +{ + uint16_t l_2815 = 65535UL; + uint16_t *l_2821 = &g_116; + uint16_t *l_2822 = &g_2823; + + assert (g_2823 == 60533); +lbl_2826: + l_2815 &= 0x9DEF1EAEL; + if (+(safe_mul_func_uint16_t_u_u(((*l_2821) = l_2815), (--(*l_2822))))) + { + goto lbl_2826; + } + assert (g_2823 == 32768); + + return 0; +} diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 3817ec423e7..325bd978609 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -1024,17 +1024,19 @@ number_of_iterations_ne (class loop *loop, tree type, affine_iv *iv, new_base = base - step > FINAL ; step < 0 && base - step doesn't overflow - 2') |FINAL - new_base| is an exact multiple of step. - - Please refer to PR34114 as an example of loop-ch's impact, also refer - to PR72817 as an example why condition 2') is necessary. + Please refer to PR34114 as an example of loop-ch's impact. Note, for NE_EXPR, base equals to FINAL is a special case, in - which the loop exits immediately, and the iv does not overflow. */ + which the loop exits immediately, and the iv does not overflow. + + Also note, we prove condition 2) by checking base and final seperately + along with condition 1) or 1'). */ if (!niter->control.no_overflow - && (integer_onep (s) || multiple_of_p (type, c, s))) + && (integer_onep (s) + || (multiple_of_p (type, fold_convert (niter_type, iv->base), s) + && multiple_of_p (type, fold_convert (niter_type, final), s)))) { - tree t, cond, new_c, relaxed_cond = boolean_false_node; + tree t, cond, relaxed_cond = boolean_false_node; if (tree_int_cst_sign_bit (iv->step)) { @@ -1048,12 +1050,8 @@ number_of_iterations_ne (class loop *loop, tree type, affine_iv *iv, if (integer_nonzerop (t)) { t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step); - new_c = fold_build2 (MINUS_EXPR, niter_type, - fold_convert (niter_type, t), - fold_convert (niter_type, final)); - if (multiple_of_p (type, new_c, s)) - relaxed_cond = fold_build2 (GT_EXPR, boolean_type_node, - t, final); + relaxed_cond = fold_build2 (GT_EXPR, boolean_type_node, t, + final); } } } @@ -1069,12 +1067,8 @@ number_of_iterations_ne (class loop *loop, tree type, affine_iv *iv, if (integer_nonzerop (t)) { t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step); - new_c = fold_build2 (MINUS_EXPR, niter_type, - fold_convert (niter_type, final), - fold_convert (niter_type, t)); - if (multiple_of_p (type, new_c, s)) - relaxed_cond = fold_build2 (LT_EXPR, boolean_type_node, - t, final); + relaxed_cond = fold_build2 (LT_EXPR, boolean_type_node, t, + final); } } } @@ -1084,19 +1078,11 @@ number_of_iterations_ne (class loop *loop, tree type, affine_iv *iv, t = simplify_using_initial_conditions (loop, relaxed_cond); if (t && integer_onep (t)) - niter->control.no_overflow = true; - } - - /* First the trivial cases -- when the step is 1. */ - if (integer_onep (s)) - { - niter->niter = c; - return true; - } - if (niter->control.no_overflow && multiple_of_p (type, c, s)) - { - niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, c, s); - return true; + { + niter->control.no_overflow = true; + niter->niter = fold_build2 (EXACT_DIV_EXPR, niter_type, c, s); + return true; + } } /* Let nsd (step, size of mode) = d. If d does not divide c, the loop