From ffd961fc053419bc1eb37792c18ec98e7c3bc364 Mon Sep 17 00:00:00 2001 From: Eric Botcazou Date: Tue, 8 Dec 2020 08:57:46 +0100 Subject: [PATCH] PR tree-optimization/96344 The very recent addition of the if_to_switch pass has partially disabled the optimization added back in June to optimize_range_tests_to_bit_test, as witnessed by the 3 new failures in the gnat.dg testsuite. It turns out that both tree-ssa-reassoc.c and tree-switch-conversion.c can turn things into bit tests so the optimization is added to bit_test_cluster::emit too. The patch also contains a secondary optimization, whereby the full bit-test sequence is sent to the folder before being gimplified in case there is only one test, so that the optimal sequence (bt + jc on x86) can be emitted like with optimize_range_tests_to_bit_test. gcc/ChangeLog: PR tree-optimization/96344 * tree-switch-conversion.c (bit_test_cluster::emit): Compute the range only if an entry test is necessary. Merge the entry test in the bit test when possible. Use PREC local variable consistently. When there is only one test, do a single gimplification at the end. --- gcc/tree-switch-conversion.c | 60 +++++++++++++++++++++++++++--------- 1 file changed, 46 insertions(+), 14 deletions(-) diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index a87a2a3cd15..989bd7710d1 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -1511,7 +1511,6 @@ bit_test_cluster::emit (tree index_expr, tree index_type, tree minval = get_low (); tree maxval = get_high (); - tree range = int_const_binop (MINUS_EXPR, maxval, minval); unsigned HOST_WIDE_INT bt_range = get_range (minval, maxval); /* Go through all case labels, and collect the case labels, profile @@ -1550,11 +1549,38 @@ bit_test_cluster::emit (tree index_expr, tree index_type, qsort (test, count, sizeof (*test), case_bit_test::cmp); + /* If every possible relative value of the index expression is a valid shift + amount, then we can merge the entry test in the bit test. */ + wide_int min, max; + bool entry_test_needed; + if (TREE_CODE (index_expr) == SSA_NAME + && get_range_info (index_expr, &min, &max) == VR_RANGE + && wi::leu_p (max - min, prec - 1)) + { + wide_int iminval = wi::to_wide (minval); + tree minval_type = TREE_TYPE (minval); + if (wi::lt_p (min, iminval, TYPE_SIGN (minval_type))) + { + minval = wide_int_to_tree (minval_type, min); + for (i = 0; i < count; i++) + test[i].mask = wi::lshift (test[i].mask, iminval - min); + } + else if (wi::gt_p (min, iminval, TYPE_SIGN (minval_type))) + { + minval = wide_int_to_tree (minval_type, min); + for (i = 0; i < count; i++) + test[i].mask = wi::lrshift (test[i].mask, min - iminval); + } + maxval = wide_int_to_tree (minval_type, max); + entry_test_needed = false; + } + else + entry_test_needed = true; + /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of the minval subtractions, but it might make the mask constants more expensive. So, compare the costs. */ - if (compare_tree_int (minval, 0) > 0 - && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0) + if (compare_tree_int (minval, 0) > 0 && compare_tree_int (maxval, prec) < 0) { int cost_diff; HOST_WIDE_INT m = tree_to_uhwi (minval); @@ -1577,7 +1603,6 @@ bit_test_cluster::emit (tree index_expr, tree index_type, for (i = 0; i < count; i++) test[i].mask = wi::lshift (test[i].mask, m); minval = build_zero_cst (TREE_TYPE (minval)); - range = maxval; } } @@ -1593,8 +1618,9 @@ bit_test_cluster::emit (tree index_expr, tree index_type, /*simple=*/true, NULL_TREE, /*before=*/true, GSI_SAME_STMT); - if (m_handles_entire_switch) + if (m_handles_entire_switch && entry_test_needed) { + tree range = int_const_binop (MINUS_EXPR, maxval, minval); /* if (idx > range) goto default */ range = force_gimple_operand_gsi (&gsi, @@ -1608,16 +1634,22 @@ bit_test_cluster::emit (tree index_expr, tree index_type, gsi = gsi_last_bb (new_bb); } - /* csui = (1 << (word_mode) idx) */ - csui = make_ssa_name (word_type_node); tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one, fold_convert (word_type_node, idx)); - tmp = force_gimple_operand_gsi (&gsi, tmp, - /*simple=*/false, NULL_TREE, - /*before=*/true, GSI_SAME_STMT); - shift_stmt = gimple_build_assign (csui, tmp); - gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT); - update_stmt (shift_stmt); + + /* csui = (1 << (word_mode) idx) */ + if (count > 1) + { + csui = make_ssa_name (word_type_node); + tmp = force_gimple_operand_gsi (&gsi, tmp, + /*simple=*/false, NULL_TREE, + /*before=*/true, GSI_SAME_STMT); + shift_stmt = gimple_build_assign (csui, tmp); + gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT); + update_stmt (shift_stmt); + } + else + csui = tmp; profile_probability prob = profile_probability::always (); @@ -1630,10 +1662,10 @@ bit_test_cluster::emit (tree index_expr, tree index_type, bt_range -= test[k].bits; tmp = wide_int_to_tree (word_type_node, test[k].mask); tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp); + tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero); tmp = force_gimple_operand_gsi (&gsi, tmp, /*simple=*/true, NULL_TREE, /*before=*/true, GSI_SAME_STMT); - tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero); basic_block new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_bb, prob); gsi = gsi_last_bb (new_bb); -- 2.30.2