| Message ID | fa1e4d42-1a87-9ca1-5e99-6d6b8d13be06@vnet.ibm.com |
|---|---|
| State | New |
| Headers | show |
On Wed, Apr 26, 2017 at 10:39:12PM -0500, Peter Bergner wrote: > +/* Returns true if the basic block BB has no successors and only contains > + a call to __builtin_unreachable (). */ so return EDGE_COUNT (bb->succs) == 0 && (gsi = gsi_last_nondebug_bb (bb)) && !gsi_end_p (gsi) && gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_UNREACHABLE); or at least if (EDGE_COUNT (bb->succs) != 0) return false; /* there is also a first_non_label_stmt() in tree-cfg.c ?! */ gsi = gsi_start_nondebug_after_labels_bb (bb); if (gsi_end_p (gsi)) return false; while (gimple_clobber_p (gsi_stmt (gsi))) { gsi_next (&gsi); if (gsi_end_p (gsi)) return false; } return gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE); which i should better phrase as gsi = gsi_start_nondebug_after_labels_bb (bb); while (!gsi_end_p (gsi) { gimple *stmt = gsi_stmt (gsi); if (gimple_clobber_p (stmt)) gsi_next (&gsi); else return gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE); } return false; No comment on the patch itself. cheers, > + > +bool > +gimple_unreachable_bb_p (basic_block bb) > +{ > + gimple_stmt_iterator gsi; > + gimple_seq stmts = bb_seq (bb); > + gimple *stmt; > + > + if (EDGE_COUNT (bb->succs) != 0) > + return false; > + > + gsi = gsi_start (stmts); > + while (!gsi_end_p (gsi) && gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL) > + gsi_next (&gsi); > + > + 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); > +} > + > /* 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: > @@ -475,23 +506,7 @@ assert_unreachable_fallthru_edge_p (edge > basic_block other_bb = EDGE_SUCC (pred_bb, 0)->dest; > 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_unreachable_bb_p (other_bb); > } > return false; > } > @@ -1668,9 +1683,10 @@ 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 > + || gimple_unreachable_bb_p (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_unreachable_bb_p (basic_block); > 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,20 @@ 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 (gimple_unreachable_bb_p (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 4/27/17 6:57 AM, Bernhard Reutner-Fischer wrote: > On Wed, Apr 26, 2017 at 10:39:12PM -0500, Peter Bergner wrote: >> +/* Returns true if the basic block BB has no successors and only contains >> + a call to __builtin_unreachable (). */ > > so > return EDGE_COUNT (bb->succs) == 0 > && (gsi = gsi_last_nondebug_bb (bb)) > && !gsi_end_p (gsi) > && gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_UNREACHABLE); [snip] > which i should better phrase as > gsi = gsi_start_nondebug_after_labels_bb (bb); > while (!gsi_end_p (gsi) > { > gimple *stmt = gsi_stmt (gsi); > if (gimple_clobber_p (stmt)) > gsi_next (&gsi); > else > return gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE); > } > return false; I didn't try to rewrite the code too much, I basically just outlined the code as is. However, one change I did have to make, was to not use routines like gsi_after_labels(), etc., since those do not work during expansion to RTL, due to bb->flags == BB_RTL. Those off limits routines include gsi_start_nondebug_after_labels_bb(), since it calls gsi_after_labels(). Peter
On Wed, 26 Apr 2017, Peter Bergner wrote: > On 4/20/17 8:26 AM, Peter Bergner wrote: > > On 4/20/17 2:37 AM, Richard Biener wrote: > >> Ok, so I think we should ensure that we remove the regular cases > >> with unreachable destination, like in > >> > >> switch (i) > >> { > >> case 0: > >> __builtin_unreachable (); > >> default:; > >> } > >> > >> and handle default with __builtin_unreachable () from switch > >> expansion by omitting the range check for the jump table > >> indexing (and choose a non-default case label for gaps). > > > > Ok, I'll modify optimize_unreachable() to remove the unreachable > > case statements, and leave the unreachable default case statement > > for switch expansion so we can eliminate the range check. Thanks. > > Ok, I lied. :-) It ended up being a fair amount of code to remove > the unreachable case statements within optimize_unreachable(). > Instead, I hooked into group_case_labels_stmt() which is much > simpler! That code eliminates all case statements that have the > same destination as the default case statement. With the patch, > we also eliminate case statements that are unreachable, thus > treating them like default cases. This has the added benefit of > being able to reduce the size of the dispatch table, if those cases > were at the end of the dispatch table entries. > > One difference from the last patch is that I am no longer setting > default_label to NULL when we emit a decision tree. I noticed that > the decision tree code seemed to generate slightly better code for > some of my unit tests if I left it alone. This simplified the > patch somewhat by removing the changes to emit_case_nodes(). > > This passed bootstrap and regtesting on powerpc64le-linux and > x86_64-linux. Is this ok for trunk now? If so, I can hold off > committing it until GCC 7 has been released if that helps. Can you do the gimple_unreachable_bb_p check earlier in expand_case so it covers the emit_case_decision_tree path as well (and verify that works, of course)? So basically right at /* Find the default case target label. */ default_label = jump_target_rtx (CASE_LABEL (gimple_switch_default_label (stmt))); edge default_edge = EDGE_SUCC (bb, 0); int default_prob = default_edge->probability; handle this case. As for Bernhards concern I share this -- please intead make the interface take either a gimple_seq or a gimple_stmt_iterator instead of a basic-block. That makes it more obvious you can't use things like gsi_after_labels. Also I think it's more natural to work backwards as the last stmt in the sequence _has_ to be __builtin_unreachable () and thus checking that first is the cheapest thing to do given that in most cases it will not be __builtin_unreachable () (but a noreturn call or an inifinite loop). Thus, name it gimple_seq_unreachable_p. Thanks, Richard. > Peter > > > gcc/ > * tree-cfg.c (gimple_unreachable_bb_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. > * gcc/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,37 @@ computed_goto_p (gimple *t) > && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL); > } > > +/* Returns true if the basic block BB has no successors and only contains > + a call to __builtin_unreachable (). */ > + > +bool > +gimple_unreachable_bb_p (basic_block bb) > +{ > + gimple_stmt_iterator gsi; > + gimple_seq stmts = bb_seq (bb); > + gimple *stmt; > + > + if (EDGE_COUNT (bb->succs) != 0) > + return false; > + > + gsi = gsi_start (stmts); > + while (!gsi_end_p (gsi) && gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL) > + gsi_next (&gsi); > + > + 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); > +} > + > /* 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: > @@ -475,23 +506,7 @@ assert_unreachable_fallthru_edge_p (edge > basic_block other_bb = EDGE_SUCC (pred_bb, 0)->dest; > 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_unreachable_bb_p (other_bb); > } > return false; > } > @@ -1668,9 +1683,10 @@ 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 > + || gimple_unreachable_bb_p (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_unreachable_bb_p (basic_block); > 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,20 @@ 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 (gimple_unreachable_bb_p (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 05/03/2017 08:32 AM, Richard Biener wrote: > As for Bernhards concern I share this -- please intead make the > interface take either a gimple_seq or a gimple_stmt_iterator > instead of a basic-block. That makes it more obvious you > can't use things like gsi_after_labels. Also I think it's more > natural to work backwards as the last stmt in the sequence > _has_ to be __builtin_unreachable () and thus checking that first > is the cheapest thing to do given that in most cases it will > not be __builtin_unreachable () (but a noreturn call or an > inifinite loop). > > Thus, name it gimple_seq_unreachable_p. So you mean something like the following? /* Returns true if the sequence of statements STMTS only contains a call to __builtin_unreachable (). */ bool gimple_seq_unreachable_p (gimple_seq stmts) { 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; } > On Wed, 26 Apr 2017, Peter Bergner wrote: >> One difference from the last patch is that I am no longer setting >> default_label to NULL when we emit a decision tree. I noticed that >> the decision tree code seemed to generate slightly better code for >> some of my unit tests if I left it alone. This simplified the >> patch somewhat by removing the changes to emit_case_nodes(). [snip] > > Can you do the gimple_unreachable_bb_p check earlier in > expand_case so it covers the emit_case_decision_tree path as well > (and verify that works, of course)? So basically right at > > /* Find the default case target label. */ > default_label = jump_target_rtx > (CASE_LABEL (gimple_switch_default_label (stmt))); > edge default_edge = EDGE_SUCC (bb, 0); > int default_prob = default_edge->probability; > > handle this case. That is what the previous patch did, but as I mention above, we generate slightly better code for some test cases (other tests seemed to generate the same code) if we don't attempt to handle the decision tree case. I'll note that the current unpatched compiler already knows how to remove unreachable case statement blocks when we expand to a decision tree. I can add that code back if you think that it will have a positive benefit for some test case I haven't tried yet. Peter
On May 8, 2017 6:41:01 PM GMT+02:00, Peter Bergner <bergner@vnet.ibm.com> wrote: >On 05/03/2017 08:32 AM, Richard Biener wrote: > > As for Bernhards concern I share this -- please intead make the > > interface take either a gimple_seq or a gimple_stmt_iterator > > instead of a basic-block. That makes it more obvious you > > can't use things like gsi_after_labels. Also I think it's more > > natural to work backwards as the last stmt in the sequence > > _has_ to be __builtin_unreachable () and thus checking that first > > is the cheapest thing to do given that in most cases it will > > not be __builtin_unreachable () (but a noreturn call or an > > inifinite loop). > > > > Thus, name it gimple_seq_unreachable_p. > >So you mean something like the following? Yes. > >/* Returns true if the sequence of statements STMTS only contains > a call to __builtin_unreachable (). */ > >bool >gimple_seq_unreachable_p (gimple_seq stmts) >{ > 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; >} > > > > > On Wed, 26 Apr 2017, Peter Bergner wrote: > >> One difference from the last patch is that I am no longer setting > >> default_label to NULL when we emit a decision tree. I noticed that > >> the decision tree code seemed to generate slightly better code for > >> some of my unit tests if I left it alone. This simplified the > >> patch somewhat by removing the changes to emit_case_nodes(). >[snip] > > > > Can you do the gimple_unreachable_bb_p check earlier in > > expand_case so it covers the emit_case_decision_tree path as well > > (and verify that works, of course)? So basically right at > > > > /* Find the default case target label. */ > > default_label = jump_target_rtx > > (CASE_LABEL (gimple_switch_default_label (stmt))); > > edge default_edge = EDGE_SUCC (bb, 0); > > int default_prob = default_edge->probability; > > > > handle this case. > >That is what the previous patch did, but as I mention above, >we generate slightly better code for some test cases (other >tests seemed to generate the same code) if we don't attempt >to handle the decision tree case. I'll note that the current >unpatched compiler already knows how to remove unreachable >case statement blocks when we expand to a decision tree. > >I can add that code back if you think that it will have a >positive benefit for some test case I haven't tried yet. > >Peter
On 05/08/2017 12:44 PM, Richard Biener wrote: >>> On Wed, 26 Apr 2017, Peter Bergner wrote: >>>> One difference from the last patch is that I am no longer setting >>>> default_label to NULL when we emit a decision tree. I noticed that >>>> the decision tree code seemed to generate slightly better code for >>>> some of my unit tests if I left it alone. This simplified the >>>> patch somewhat by removing the changes to emit_case_nodes(). >> [snip] >>> Can you do the gimple_unreachable_bb_p check earlier in >>> expand_case so it covers the emit_case_decision_tree path as well >>> (and verify that works, of course)? So basically right at >>> >>> /* Find the default case target label. */ >>> default_label = jump_target_rtx >>> (CASE_LABEL (gimple_switch_default_label (stmt))); >>> edge default_edge = EDGE_SUCC (bb, 0); >>> int default_prob = default_edge->probability; >>> >>> handle this case. >> That is what the previous patch did, but as I mention above, >> we generate slightly better code for some test cases (other >> tests seemed to generate the same code) if we don't attempt >> to handle the decision tree case. I'll note that the current >> unpatched compiler already knows how to remove unreachable >> case statement blocks when we expand to a decision tree. >> >> I can add that code back if you think that it will have a >> positive benefit for some test case I haven't tried yet. Any comment on the above? Peter
On 05/08/2017 01:20 PM, Peter Bergner wrote: > That is what the previous patch did, but as I mention above, > we generate slightly better code for some test cases (other > tests seemed to generate the same code) if we don't attempt > to handle the decision tree case. I'll note that the current > unpatched compiler already knows how to remove unreachable > case statement blocks when we expand to a decision tree. I should be more careful with my description here. The patch does affect both unreachable case statements for both decision trees as well as jump tables, and that leads to improved code for both decision trees as well as jump tables. What I meant to say above, is that the current handling of unreachable default case statements in the unpatched compiler seems to lead to slightly better code for some test cases than attempting to handle default_label == NULL in the decision tree code. It was for that reason, I placed the code in expand_case() only in the jump table path. The fact it made the patch smaller was a bonus, since I didn't need to protect emit_case_nodes() from a NULL default_label. As I said, if you think it will help some test case I haven't tried yet, I can add that support back. Peter
On Mon, 8 May 2017, Peter Bergner wrote: > On 05/08/2017 01:20 PM, Peter Bergner wrote: > > That is what the previous patch did, but as I mention above, > > we generate slightly better code for some test cases (other > > tests seemed to generate the same code) if we don't attempt > > to handle the decision tree case. I'll note that the current > > unpatched compiler already knows how to remove unreachable > > case statement blocks when we expand to a decision tree. > > I should be more careful with my description here. The patch does > affect both unreachable case statements for both decision trees as > well as jump tables, and that leads to improved code for both > decision trees as well as jump tables. > > What I meant to say above, is that the current handling of unreachable > default case statements in the unpatched compiler seems to lead to > slightly better code for some test cases than attempting to handle > default_label == NULL in the decision tree code. It was for that > reason, I placed the code in expand_case() only in the jump table > path. The fact it made the patch smaller was a bonus, since I didn't > need to protect emit_case_nodes() from a NULL default_label. Ah, ok. > As I said, if you think it will help some test case I haven't tried yet, > I can add that support back. Well, let's to that incremental then, if at all. Thanks, Richard.
Index: gcc/tree-cfg.c =================================================================== --- gcc/tree-cfg.c (revision 247291) +++ gcc/tree-cfg.c (working copy) @@ -452,6 +452,37 @@ computed_goto_p (gimple *t) && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL); } +/* Returns true if the basic block BB has no successors and only contains + a call to __builtin_unreachable (). */ + +bool +gimple_unreachable_bb_p (basic_block bb) +{ + gimple_stmt_iterator gsi; + gimple_seq stmts = bb_seq (bb); + gimple *stmt; + + if (EDGE_COUNT (bb->succs) != 0) + return false; + + gsi = gsi_start (stmts); + while (!gsi_end_p (gsi) && gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL) + gsi_next (&gsi); + + 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); +} + /* 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: @@ -475,23 +506,7 @@ assert_unreachable_fallthru_edge_p (edge basic_block other_bb = EDGE_SUCC (pred_bb, 0)->dest; 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_unreachable_bb_p (other_bb); } return false; } @@ -1668,9 +1683,10 @@ 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 + || gimple_unreachable_bb_p (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_unreachable_bb_p (basic_block); 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,20 @@ 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 (gimple_unreachable_bb_p (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;