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; > > > -- Richard Biener <rguent...@suse.de> SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)