From 377afcd5beb350a1b7cd07b0a868a766345073e0 Mon Sep 17 00:00:00 2001 From: Martin Liska Date: Mon, 27 Aug 2018 14:18:24 +0200 Subject: [PATCH] Fix probability for bit-tests. 2018-08-27 Martin Liska * tree-switch-conversion.c (bit_test_cluster::find_bit_tests): Add new argument to bit_test_cluster constructor. (bit_test_cluster::emit): Set bits really number of values handlel by a test. (bit_test_cluster::hoist_edge_and_branch_if_true): Add probability argument. * tree-switch-conversion.h (struct bit_test_cluster): Add m_handles_entire_switch. 2018-08-27 Martin Liska * gcc.dg/tree-ssa/switch-2.c: New test. From-SVN: r263878 --- gcc/ChangeLog | 11 ++++++ gcc/testsuite/ChangeLog | 4 +++ gcc/testsuite/gcc.dg/tree-ssa/switch-2.c | 25 +++++++++++++ gcc/tree-switch-conversion.c | 46 +++++++++++++++++------- gcc/tree-switch-conversion.h | 12 +++++-- 5 files changed, 82 insertions(+), 16 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-2.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b39f12fe037..698f677aa7e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2018-08-27 Martin Liska + + * tree-switch-conversion.c (bit_test_cluster::find_bit_tests): + Add new argument to bit_test_cluster constructor. + (bit_test_cluster::emit): Set bits really number of values + handlel by a test. + (bit_test_cluster::hoist_edge_and_branch_if_true): Add + probability argument. + * tree-switch-conversion.h (struct bit_test_cluster): + Add m_handles_entire_switch. + 2018-08-27 Martin Liska PR tree-optimization/86702 diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index ef5da5aae78..f20f43a5df8 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2018-08-27 Martin Liska + + * gcc.dg/tree-ssa/switch-2.c: New test. + 2018-08-27 Richard Biener * g++.dg/torture/20180705-1.C: New testcase. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-2.c b/gcc/testsuite/gcc.dg/tree-ssa/switch-2.c new file mode 100644 index 00000000000..710825dc257 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/switch-2.c @@ -0,0 +1,25 @@ +/* { dg-do compile { target { { x86_64-*-* aarch64-*-* ia64-*-* powerpc64-*-* } && lp64 } } } */ +/* { dg-options "-O2 -fdump-tree-switchlower1" } */ + +int global; + +int foo (int x) +{ + switch (x) { + case 0: + case 10: + return 1; + case 20: + case 30: + case 62: + return 2; + case 1000: + case 1010: + case 1025 ... 1030: + return 1; + default: + return 0; + } +} + +/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: BT:0-62 BT:1000-1030" "switchlower1" } } */ diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index 00a463b1dde..47acb0c8ae8 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -1279,12 +1279,16 @@ bit_test_cluster::find_bit_tests (vec &clusters) return clusters.copy (); /* Find and build the clusters. */ - for (int end = l;;) + for (unsigned end = l;;) { int start = min[end].m_start; if (is_beneficial (clusters, start, end - 1)) - output.safe_push (new bit_test_cluster (clusters, start, end - 1)); + { + bool entire = start == 0 && end == clusters.length (); + output.safe_push (new bit_test_cluster (clusters, start, end - 1, + entire)); + } else for (int i = end - 1; i >= start; i--) output.safe_push (clusters[i]); @@ -1434,6 +1438,7 @@ 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 counts, and other information we need to build the branch tests. */ @@ -1452,11 +1457,11 @@ bit_test_cluster::emit (tree index_expr, tree index_type, test[k].mask = wi::zero (prec); test[k].target_bb = n->m_case_bb; test[k].label = n->m_case_label_expr; - test[k].bits = 1; + test[k].bits = 0; count++; } - else - test[k].bits++; + + test[k].bits += n->get_range (n->get_low (), n->get_high ()); lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval)); if (n->get_high () == NULL_TREE) @@ -1513,14 +1518,20 @@ bit_test_cluster::emit (tree index_expr, tree index_type, /*simple=*/true, NULL_TREE, /*before=*/true, GSI_SAME_STMT); - /* if (idx > range) goto default */ - range = force_gimple_operand_gsi (&gsi, + if (m_handles_entire_switch) + { + /* if (idx > range) goto default */ + range + = force_gimple_operand_gsi (&gsi, fold_convert (unsigned_index_type, range), /*simple=*/true, NULL_TREE, /*before=*/true, GSI_SAME_STMT); - tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range); - basic_block new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb); - gsi = gsi_last_bb (new_bb); + tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range); + basic_block new_bb + = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb, + profile_probability::unlikely ()); + gsi = gsi_last_bb (new_bb); + } /* csui = (1 << (word_mode) idx) */ csui = make_ssa_name (word_type_node); @@ -1533,17 +1544,23 @@ bit_test_cluster::emit (tree index_expr, tree index_type, gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT); update_stmt (shift_stmt); + profile_probability prob = profile_probability::always (); + /* for each unique set of cases: if (const & csui) goto target */ for (k = 0; k < count; k++) { + prob = profile_probability::always ().apply_scale (test[k].bits, + bt_range); + 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 = 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); - new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_bb); + basic_block new_bb + = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_bb, prob); gsi = gsi_last_bb (new_bb); } @@ -1551,7 +1568,8 @@ bit_test_cluster::emit (tree index_expr, tree index_type, gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0); /* If nothing matched, go to the default label. */ - make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU); + edge e = make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU); + e->probability = profile_probability::always (); } /* Split the basic block at the statement pointed to by GSIP, and insert @@ -1571,7 +1589,8 @@ bit_test_cluster::emit (tree index_expr, tree index_type, basic_block bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, - tree cond, basic_block case_bb) + tree cond, basic_block case_bb, + profile_probability prob) { tree tmp; gcond *cond_stmt; @@ -1579,6 +1598,7 @@ bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, basic_block new_bb, split_bb = gsi_bb (*gsip); edge e_true = make_edge (split_bb, case_bb, EDGE_TRUE_VALUE); + e_true->probability = prob; gcc_assert (e_true->src == split_bb); tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL, diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h index af2f47a07e6..726d54ad912 100644 --- a/gcc/tree-switch-conversion.h +++ b/gcc/tree-switch-conversion.h @@ -329,8 +329,10 @@ This transformation was contributed by Roger Sayle, see this e-mail: struct bit_test_cluster: public group_cluster { /* Constructor. */ - bit_test_cluster (vec &clusters, unsigned start, unsigned end) - :group_cluster (clusters, start, end) + bit_test_cluster (vec &clusters, unsigned start, unsigned end, + bool handles_entire_switch) + :group_cluster (clusters, start, end), + m_handles_entire_switch (handles_entire_switch) {} cluster_type @@ -396,7 +398,11 @@ struct bit_test_cluster: public group_cluster Returns the newly created basic block. */ static basic_block hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, tree cond, - basic_block case_bb); + basic_block case_bb, + profile_probability prob); + + /* True when the jump table handles an entire switch statement. */ + bool m_handles_entire_switch; /* Maximum number of different basic blocks that can be handled by a bit test. */ -- 2.30.2