| Message ID | 851d1590-6ef5-45f2-5bc0-77de42671254@vnet.ibm.com |
|---|---|
| State | New |
| Headers | show |
On Tue, 9 May 2017, Peter Bergner wrote: > Here is the updated patch to use gimple_seq_unreachable_p() which scans the > sequence backwards so it bails out earlier in the common case (ie, no call > to __builtin_unreachable). As discussed in the previous thread, we remove > case statement labels from the jump table that lead to unreachable blocks, > which leads to fewer compare/branches in the decision tree case and > possibly a smaller jump table in the jump table case. Unreachable default > case statements are only handled here when generating a jump table, since > the current code for decision trees seems to prefer the status quo. We can > revisit this later if someone finds a test case that would benefit from > handling it for decision trees too. > > This passes bootstrap and regtesting on powerpc64le-linux and x86_64-linux > with no regressions. Ok for trunk now? Ok. Thanks, Richard. > Peter > > gcc/ > * tree-cfg.c (gimple_seq_unreachable_p): New function. > (assert_unreachable_fallthru_edge_p): Use it. > (group_case_labels_stmt): Likewise. > * tree-cfg.h: Prototype it. > * stmt.c: Include cfghooks.h and tree-cfg.h. > (emit_case_dispatch_table) <gap_label>: New local variable. > Use it to fill dispatch table gaps. > Test for default_label before updating probabilities. > (expand_case) <default_label>: Remove unneeded initialization. > Test for unreachable default case statement and remove its edge. > Set default_label accordingly. > * tree-ssa-ccp.c (optimize_unreachable): Update comment. > > gcc/testsuite/ > * gcc.target/powerpc/pr51513.c: New test. > * gcc.dg/predict-13.c: Replace __builtin_unreachable() with > __builtin_abort(). > * gcc.dg/predict-14.c: Likewise. > > Index: gcc/tree-cfg.c > =================================================================== > --- gcc/tree-cfg.c (revision 247291) > +++ gcc/tree-cfg.c (working copy) > @@ -452,6 +452,31 @@ computed_goto_p (gimple *t) > && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL); > } > > +/* Returns true if the sequence of statements STMTS only contains > + a call to __builtin_unreachable (). */ > + > +bool > +gimple_seq_unreachable_p (gimple_seq stmts) > +{ > + if (stmts == NULL) > + return false; > + > + gimple_stmt_iterator gsi = gsi_last (stmts); > + > + if (!gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_UNREACHABLE)) > + return false; > + > + for (gsi_prev (&gsi); !gsi_end_p (gsi); gsi_prev (&gsi)) > + { > + gimple *stmt = gsi_stmt (gsi); > + if (gimple_code (stmt) != GIMPLE_LABEL > + && !is_gimple_debug (stmt) > + && !gimple_clobber_p (stmt)) > + return false; > + } > + return true; > +} > + > /* Returns true for edge E where e->src ends with a GIMPLE_COND and > the other edge points to a bb with just __builtin_unreachable (). > I.e. return true for C->M edge in: > @@ -476,22 +501,7 @@ assert_unreachable_fallthru_edge_p (edge > if (other_bb == e->dest) > other_bb = EDGE_SUCC (pred_bb, 1)->dest; > if (EDGE_COUNT (other_bb->succs) == 0) > - { > - gimple_stmt_iterator gsi = gsi_after_labels (other_bb); > - gimple *stmt; > - > - if (gsi_end_p (gsi)) > - return false; > - stmt = gsi_stmt (gsi); > - while (is_gimple_debug (stmt) || gimple_clobber_p (stmt)) > - { > - gsi_next (&gsi); > - if (gsi_end_p (gsi)) > - return false; > - stmt = gsi_stmt (gsi); > - } > - return gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE); > - } > + return gimple_seq_unreachable_p (bb_seq (other_bb)); > } > return false; > } > @@ -1668,9 +1678,11 @@ group_case_labels_stmt (gswitch *stmt) > gcc_assert (base_case); > base_bb = label_to_block (CASE_LABEL (base_case)); > > - /* Discard cases that have the same destination as the > - default case. */ > - if (base_bb == default_bb) > + /* Discard cases that have the same destination as the default case > + or if their destination block is unreachable. */ > + if (base_bb == default_bb > + || (EDGE_COUNT (base_bb->succs) == 0 > + && gimple_seq_unreachable_p (bb_seq (base_bb)))) > { > gimple_switch_set_label (stmt, i, NULL_TREE); > i++; > Index: gcc/tree-cfg.h > =================================================================== > --- gcc/tree-cfg.h (revision 247291) > +++ gcc/tree-cfg.h (working copy) > @@ -56,6 +56,7 @@ extern bool is_ctrl_stmt (gimple *); > extern bool is_ctrl_altering_stmt (gimple *); > extern bool simple_goto_p (gimple *); > extern bool stmt_ends_bb_p (gimple *); > +extern bool gimple_seq_unreachable_p (gimple_seq); > extern bool assert_unreachable_fallthru_edge_p (edge); > extern void delete_tree_cfg_annotations (function *); > extern gphi *get_virtual_phi (basic_block); > Index: gcc/stmt.c > =================================================================== > --- gcc/stmt.c (revision 247291) > +++ gcc/stmt.c (working copy) > @@ -30,6 +30,7 @@ along with GCC; see the file COPYING3. > #include "rtl.h" > #include "tree.h" > #include "gimple.h" > +#include "cfghooks.h" > #include "predict.h" > #include "alloc-pool.h" > #include "memmodel.h" > @@ -49,6 +50,7 @@ along with GCC; see the file COPYING3. > #include "expr.h" > #include "langhooks.h" > #include "cfganal.h" > +#include "tree-cfg.h" > #include "params.h" > #include "dumpfile.h" > #include "builtins.h" > @@ -1007,20 +1009,21 @@ emit_case_dispatch_table (tree index_exp > = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label)); > } > > - /* Fill in the gaps with the default. We may have gaps at > - the beginning if we tried to avoid the minval subtraction, > - so substitute some label even if the default label was > - deemed unreachable. */ > - if (!default_label) > - default_label = fallback_label; > + /* The dispatch table may contain gaps, including at the beginning of > + the table if we tried to avoid the minval subtraction. We fill the > + dispatch table slots associated with the gaps with the default case label. > + However, in the event the default case is unreachable, we then use > + any label from one of the case statements. */ > + rtx gap_label = (default_label) ? default_label : fallback_label; > + > for (i = 0; i < ncases; i++) > if (labelvec[i] == 0) > { > - has_gaps = true; > - labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label); > + has_gaps = true; > + labelvec[i] = gen_rtx_LABEL_REF (Pmode, gap_label); > } > > - if (has_gaps) > + if (has_gaps && default_label) > { > /* There is at least one entry in the jump table that jumps > to default label. The default label can either be reached > @@ -1115,7 +1118,7 @@ void > expand_case (gswitch *stmt) > { > tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE; > - rtx_code_label *default_label = NULL; > + rtx_code_label *default_label; > unsigned int count, uniq; > int i; > int ncases = gimple_switch_num_labels (stmt); > @@ -1232,9 +1235,21 @@ expand_case (gswitch *stmt) > case_list, default_label, > default_prob); > else > - emit_case_dispatch_table (index_expr, index_type, > - case_list, default_label, > - minval, maxval, range, bb); > + { > + /* If the default case is unreachable, then set default_label to NULL > + so that we omit the range check when generating the dispatch table. > + We also remove the edge to the unreachable default case. The block > + itself will be automatically removed later. */ > + if (EDGE_COUNT (default_edge->dest->succs) == 0 > + && gimple_seq_unreachable_p (bb_seq (default_edge->dest))) > + { > + default_label = NULL; > + remove_edge (default_edge); > + } > + emit_case_dispatch_table (index_expr, index_type, > + case_list, default_label, > + minval, maxval, range, bb); > + } > > reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case); > > Index: gcc/tree-ssa-ccp.c > =================================================================== > --- gcc/tree-ssa-ccp.c (revision 247291) > +++ gcc/tree-ssa-ccp.c (working copy) > @@ -2715,7 +2715,8 @@ optimize_unreachable (gimple_stmt_iterat > } > else > { > - /* Todo: handle other cases, f.i. switch statement. */ > + /* Todo: handle other cases. Note that unreachable switch case > + statements have already been removed. */ > continue; > } > > Index: gcc/testsuite/gcc.target/powerpc/pr51513.c > =================================================================== > --- gcc/testsuite/gcc.target/powerpc/pr51513.c (nonexistent) > +++ gcc/testsuite/gcc.target/powerpc/pr51513.c (working copy) > @@ -0,0 +1,25 @@ > +/* { dg-do compile { target { powerpc*-*-linux* } } } */ > +/* { dg-options "-O2 -fjump-tables --param case-values-threshold=1" } */ > +/* Verify we created a jump table. */ > +/* { dg-final { scan-assembler-times "mtctr " 1 } } */ > +/* { dg-final { scan-assembler-times "bctr" 1 } } */ > +/* Verify we eliminated the range check. */ > +/* { dg-final { scan-assembler-not "cmpldi" } } */ > +/* { dg-final { scan-assembler-not "cmplwi" } } */ > + > +long > +bug (long cond, long v0, long v1, long v2) > +{ > + switch (cond) > + { > + case 0: > + return v0; > + case 1: > + return v1; > + case 2: > + return v2; > + default: > + __builtin_unreachable (); > + } > + __builtin_abort (); > +} > Index: gcc/testsuite/gcc.dg/predict-13.c > =================================================================== > --- gcc/testsuite/gcc.dg/predict-13.c (revision 247291) > +++ gcc/testsuite/gcc.dg/predict-13.c (working copy) > @@ -10,9 +10,9 @@ int main(int argc, char **argv) > case 2: > return 2; > case 3: > - __builtin_unreachable(); > + __builtin_abort(); > case 4: > - __builtin_unreachable(); > + __builtin_abort(); > default: > return 5; > } > Index: gcc/testsuite/gcc.dg/predict-14.c > =================================================================== > --- gcc/testsuite/gcc.dg/predict-14.c (revision 247291) > +++ gcc/testsuite/gcc.dg/predict-14.c (working copy) > @@ -6,11 +6,11 @@ int main(int argc, char **argv) > switch (argc) > { > case 1: > - __builtin_unreachable(); > + __builtin_abort(); > case 4: > - __builtin_unreachable(); > + __builtin_abort(); > default: > - __builtin_unreachable(); > + __builtin_abort(); > } > > return 10; > >
On Tue, May 9, 2017 at 7:54 PM, Peter Bergner <bergner@vnet.ibm.com> wrote: > Here is the updated patch to use gimple_seq_unreachable_p() which scans the > sequence backwards so it bails out earlier in the common case (ie, no call > to __builtin_unreachable). As discussed in the previous thread, we remove > case statement labels from the jump table that lead to unreachable blocks, > which leads to fewer compare/branches in the decision tree case and > possibly a smaller jump table in the jump table case. Unreachable default > case statements are only handled here when generating a jump table, since > the current code for decision trees seems to prefer the status quo. We can > revisit this later if someone finds a test case that would benefit from > handling it for decision trees too. > > This passes bootstrap and regtesting on powerpc64le-linux and x86_64-linux > with no regressions. Ok for trunk now? > > Peter > > gcc/ > * tree-cfg.c (gimple_seq_unreachable_p): New function. > (assert_unreachable_fallthru_edge_p): Use it. > (group_case_labels_stmt): Likewise. > * tree-cfg.h: Prototype it. > * stmt.c: Include cfghooks.h and tree-cfg.h. > (emit_case_dispatch_table) <gap_label>: New local variable. > Use it to fill dispatch table gaps. > Test for default_label before updating probabilities. > (expand_case) <default_label>: Remove unneeded initialization. > Test for unreachable default case statement and remove its edge. > Set default_label accordingly. > * tree-ssa-ccp.c (optimize_unreachable): Update comment. > > gcc/testsuite/ > * gcc.target/powerpc/pr51513.c: New test. > * gcc.dg/predict-13.c: Replace __builtin_unreachable() with > __builtin_abort(). > * gcc.dg/predict-14.c: Likewise. > This caused: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80714 H.J.
On 5/11/17 3:49 PM, H.J. Lu wrote: > This caused: > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80714 This is already being tracked in https://gcc.gnu.org/PR80707 Peter
Index: gcc/tree-cfg.c =================================================================== --- gcc/tree-cfg.c (revision 247291) +++ gcc/tree-cfg.c (working copy) @@ -452,6 +452,31 @@ computed_goto_p (gimple *t) && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL); } +/* Returns true if the sequence of statements STMTS only contains + a call to __builtin_unreachable (). */ + +bool +gimple_seq_unreachable_p (gimple_seq stmts) +{ + if (stmts == NULL) + return false; + + gimple_stmt_iterator gsi = gsi_last (stmts); + + if (!gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_UNREACHABLE)) + return false; + + for (gsi_prev (&gsi); !gsi_end_p (gsi); gsi_prev (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + if (gimple_code (stmt) != GIMPLE_LABEL + && !is_gimple_debug (stmt) + && !gimple_clobber_p (stmt)) + return false; + } + return true; +} + /* Returns true for edge E where e->src ends with a GIMPLE_COND and the other edge points to a bb with just __builtin_unreachable (). I.e. return true for C->M edge in: @@ -476,22 +501,7 @@ assert_unreachable_fallthru_edge_p (edge if (other_bb == e->dest) other_bb = EDGE_SUCC (pred_bb, 1)->dest; if (EDGE_COUNT (other_bb->succs) == 0) - { - gimple_stmt_iterator gsi = gsi_after_labels (other_bb); - gimple *stmt; - - if (gsi_end_p (gsi)) - return false; - stmt = gsi_stmt (gsi); - while (is_gimple_debug (stmt) || gimple_clobber_p (stmt)) - { - gsi_next (&gsi); - if (gsi_end_p (gsi)) - return false; - stmt = gsi_stmt (gsi); - } - return gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE); - } + return gimple_seq_unreachable_p (bb_seq (other_bb)); } return false; } @@ -1668,9 +1678,11 @@ group_case_labels_stmt (gswitch *stmt) gcc_assert (base_case); base_bb = label_to_block (CASE_LABEL (base_case)); - /* Discard cases that have the same destination as the - default case. */ - if (base_bb == default_bb) + /* Discard cases that have the same destination as the default case + or if their destination block is unreachable. */ + if (base_bb == default_bb + || (EDGE_COUNT (base_bb->succs) == 0 + && gimple_seq_unreachable_p (bb_seq (base_bb)))) { gimple_switch_set_label (stmt, i, NULL_TREE); i++; Index: gcc/tree-cfg.h =================================================================== --- gcc/tree-cfg.h (revision 247291) +++ gcc/tree-cfg.h (working copy) @@ -56,6 +56,7 @@ extern bool is_ctrl_stmt (gimple *); extern bool is_ctrl_altering_stmt (gimple *); extern bool simple_goto_p (gimple *); extern bool stmt_ends_bb_p (gimple *); +extern bool gimple_seq_unreachable_p (gimple_seq); extern bool assert_unreachable_fallthru_edge_p (edge); extern void delete_tree_cfg_annotations (function *); extern gphi *get_virtual_phi (basic_block); Index: gcc/stmt.c =================================================================== --- gcc/stmt.c (revision 247291) +++ gcc/stmt.c (working copy) @@ -30,6 +30,7 @@ along with GCC; see the file COPYING3. #include "rtl.h" #include "tree.h" #include "gimple.h" +#include "cfghooks.h" #include "predict.h" #include "alloc-pool.h" #include "memmodel.h" @@ -49,6 +50,7 @@ along with GCC; see the file COPYING3. #include "expr.h" #include "langhooks.h" #include "cfganal.h" +#include "tree-cfg.h" #include "params.h" #include "dumpfile.h" #include "builtins.h" @@ -1007,20 +1009,21 @@ emit_case_dispatch_table (tree index_exp = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label)); } - /* Fill in the gaps with the default. We may have gaps at - the beginning if we tried to avoid the minval subtraction, - so substitute some label even if the default label was - deemed unreachable. */ - if (!default_label) - default_label = fallback_label; + /* The dispatch table may contain gaps, including at the beginning of + the table if we tried to avoid the minval subtraction. We fill the + dispatch table slots associated with the gaps with the default case label. + However, in the event the default case is unreachable, we then use + any label from one of the case statements. */ + rtx gap_label = (default_label) ? default_label : fallback_label; + for (i = 0; i < ncases; i++) if (labelvec[i] == 0) { - has_gaps = true; - labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label); + has_gaps = true; + labelvec[i] = gen_rtx_LABEL_REF (Pmode, gap_label); } - if (has_gaps) + if (has_gaps && default_label) { /* There is at least one entry in the jump table that jumps to default label. The default label can either be reached @@ -1115,7 +1118,7 @@ void expand_case (gswitch *stmt) { tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE; - rtx_code_label *default_label = NULL; + rtx_code_label *default_label; unsigned int count, uniq; int i; int ncases = gimple_switch_num_labels (stmt); @@ -1232,9 +1235,21 @@ expand_case (gswitch *stmt) case_list, default_label, default_prob); else - emit_case_dispatch_table (index_expr, index_type, - case_list, default_label, - minval, maxval, range, bb); + { + /* If the default case is unreachable, then set default_label to NULL + so that we omit the range check when generating the dispatch table. + We also remove the edge to the unreachable default case. The block + itself will be automatically removed later. */ + if (EDGE_COUNT (default_edge->dest->succs) == 0 + && gimple_seq_unreachable_p (bb_seq (default_edge->dest))) + { + default_label = NULL; + remove_edge (default_edge); + } + emit_case_dispatch_table (index_expr, index_type, + case_list, default_label, + minval, maxval, range, bb); + } reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case); Index: gcc/tree-ssa-ccp.c =================================================================== --- gcc/tree-ssa-ccp.c (revision 247291) +++ gcc/tree-ssa-ccp.c (working copy) @@ -2715,7 +2715,8 @@ optimize_unreachable (gimple_stmt_iterat } else { - /* Todo: handle other cases, f.i. switch statement. */ + /* Todo: handle other cases. Note that unreachable switch case + statements have already been removed. */ continue; } Index: gcc/testsuite/gcc.target/powerpc/pr51513.c =================================================================== --- gcc/testsuite/gcc.target/powerpc/pr51513.c (nonexistent) +++ gcc/testsuite/gcc.target/powerpc/pr51513.c (working copy) @@ -0,0 +1,25 @@ +/* { dg-do compile { target { powerpc*-*-linux* } } } */ +/* { dg-options "-O2 -fjump-tables --param case-values-threshold=1" } */ +/* Verify we created a jump table. */ +/* { dg-final { scan-assembler-times "mtctr " 1 } } */ +/* { dg-final { scan-assembler-times "bctr" 1 } } */ +/* Verify we eliminated the range check. */ +/* { dg-final { scan-assembler-not "cmpldi" } } */ +/* { dg-final { scan-assembler-not "cmplwi" } } */ + +long +bug (long cond, long v0, long v1, long v2) +{ + switch (cond) + { + case 0: + return v0; + case 1: + return v1; + case 2: + return v2; + default: + __builtin_unreachable (); + } + __builtin_abort (); +} Index: gcc/testsuite/gcc.dg/predict-13.c =================================================================== --- gcc/testsuite/gcc.dg/predict-13.c (revision 247291) +++ gcc/testsuite/gcc.dg/predict-13.c (working copy) @@ -10,9 +10,9 @@ int main(int argc, char **argv) case 2: return 2; case 3: - __builtin_unreachable(); + __builtin_abort(); case 4: - __builtin_unreachable(); + __builtin_abort(); default: return 5; } Index: gcc/testsuite/gcc.dg/predict-14.c =================================================================== --- gcc/testsuite/gcc.dg/predict-14.c (revision 247291) +++ gcc/testsuite/gcc.dg/predict-14.c (working copy) @@ -6,11 +6,11 @@ int main(int argc, char **argv) switch (argc) { case 1: - __builtin_unreachable(); + __builtin_abort(); case 4: - __builtin_unreachable(); + __builtin_abort(); default: - __builtin_unreachable(); + __builtin_abort(); } return 10;