Message ID | 20170214200445.GY1849@tucnak |
---|---|
State | New |
Headers | show |
On February 14, 2017 9:04:45 PM GMT+01:00, Jakub Jelinek <jakub@redhat.com> wrote: >Hi! > >The following patch is an attempt to fix a regression where we no >longer >switch convert one switch because earlier optimizations turn it into >unsupported shape. Is that because of early threading? >The patch contains two important changes (that can perhaps be split off >separately): >1) handle virtual PHIs; while because we require all the switch bbs > to be empty, all the edges from the switch to final_bb should have the > same virtual op SSA_NAME, if the final_bb is reachable through other > edges from other code, it might have virtual PHI and switchconv would > unnecessarily give up >2) if the switch cases form contiguous range, there is no need to >require > anything about the default case, it can be abort, or arbitrary code > that can or might not fall through into final_bb, or it can e.g. be > empty bb and just the values from default bb might not be appropriate > constants; we emit an if (val is in range) vals = CSWTCH[...]; else > anyway and the else can be anything; we still have to require standard > default case if the range is non-contiguous, because then the default > is used also for some values in the tables. > >Bootstrapped/regtested on x86_64-linux and i686-linux. It causes a >single >regression, vrp40.c, which looks like this: >int f(int a) { >switch (a & 1) { case 0: case 1: return 3; case 2: return 5; case 3: >return 7; >case 4: return 11; case 5: return 13; case 6: return 17; case 7: return >19; } >} >and expects to be optimized into return 3 by vrp1. As switchconv is >earlier >than that, vrp1 sees: > _1 = a_3(D) & 1; > _4 = (unsigned int) _1; > _5 = CSWTCH.1[_4]; > return _5; >and doesn't optimize it. If the testcase had say case 7: replaced with >default:, it wouldn't pass already before. That looks odd... If the patch is ok, what >should >we do with vrp40.c? Change it in some way (e.g. return variable in one >case) so that switchconv doesn't trigger, or add an optimization in vrp >if we see a load from constant array with known initializer and the >range >is small enough and contains the same value for all those values, >replace >it with the value? Possibly, but for GCC 8. can we teach EVRP about this? It runs before switch conversion. Richard. It would help also with say: >const int a[] = { 7, 8, 9, 1, 1, 1, 1, 2, 3, 4, 5, 6 }; >int foo (int x) >{ > if (x <= 2 || x >= 7) return 3; > return a[x]; >} >turn it into >int foo (int x) >{ > if (x <= 2 || x >= 7) return 3; > return 1; >} > >2017-02-14 Jakub Jelinek <jakub@redhat.com> > > PR tree-optimization/79472 > * tree-switch-conversion.c (struct switch_conv_info): Add > contiguous_range and default_case_nonstandard fields. > (collect_switch_conv_info): Compute contiguous_range and > default_case_nonstandard fields, don't clear final_bb if > contiguous_range and only the default case doesn't have the required > structure. > (check_all_empty_except_final): Set default_case_nonstandard instead > of failing if contiguous_range and the default case doesn't have empty > block. > (check_final_bb): Add SWTCH argument, don't fail if contiguous_range > and only the default case doesn't have the required constants. Skip > virtual phis. > (gather_default_values): Skip virtual phis. Allow non-NULL CASE_LOW > if default_case_nonstandard. > (build_constructors): Build constant 1 just once. Assert that default > values aren't inserted in between cases if contiguous_range. Skip > virtual phis. > (build_arrays): Skip virtual phis. > (prune_bbs): Add DEFAULT_BB argument, don't remove that bb. > (fix_phi_nodes): Don't add e2f phi arg if default_case_nonstandard. > Handle virtual phis. > (gen_inbound_check): Handle default_case_nonstandard case. > (process_switch): Adjust check_final_bb caller. Call > gather_default_values with the first non-default case instead of > default case if default_case_nonstandard. > > * gcc.dg/tree-ssa/cswtch-3.c: New test. > * gcc.dg/tree-ssa/cswtch-4.c: New test. > * gcc.dg/tree-ssa/cswtch-5.c: New test. > >--- gcc/tree-switch-conversion.c.jj 2017-02-14 14:54:08.020975500 +0100 >+++ gcc/tree-switch-conversion.c 2017-02-14 17:09:01.162826954 +0100 >@@ -592,6 +592,14 @@ struct switch_conv_info > dump file, if there is one. */ > const char *reason; > >+ /* True if default case is not used for any value between range_min >and >+ range_max inclusive. */ >+ bool contiguous_range; >+ >+ /* True if default case does not have the required shape for other >case >+ labels. */ >+ bool default_case_nonstandard; >+ > /* Parameters for expand_switch_using_bit_tests. Should be computed > the same way as in expand_case. */ > unsigned int uniq; >@@ -606,8 +614,9 @@ collect_switch_conv_info (gswitch *swtch > unsigned int branch_num = gimple_switch_num_labels (swtch); > tree min_case, max_case; > unsigned int count, i; >- edge e, e_default; >+ edge e, e_default, e_first; > edge_iterator ei; >+ basic_block first; > > memset (info, 0, sizeof (*info)); > >@@ -616,8 +625,8 @@ collect_switch_conv_info (gswitch *swtch > Collect the bits we can deduce from the CFG. */ > info->index_expr = gimple_switch_index (swtch); > info->switch_bb = gimple_bb (swtch); >- info->default_bb = >- label_to_block (CASE_LABEL (gimple_switch_default_label (swtch))); >+ info->default_bb >+ = label_to_block (CASE_LABEL (gimple_switch_default_label >(swtch))); > e_default = find_edge (info->switch_bb, info->default_bb); > info->default_prob = e_default->probability; > info->default_count = e_default->count; >@@ -625,17 +634,54 @@ collect_switch_conv_info (gswitch *swtch > if (e != e_default) > info->other_count += e->count; > >+ /* Get upper and lower bounds of case values, and the covered range. > */ >+ min_case = gimple_switch_label (swtch, 1); >+ max_case = gimple_switch_label (swtch, branch_num - 1); >+ >+ info->range_min = CASE_LOW (min_case); >+ if (CASE_HIGH (max_case) != NULL_TREE) >+ info->range_max = CASE_HIGH (max_case); >+ else >+ info->range_max = CASE_LOW (max_case); >+ >+ info->contiguous_range = true; >+ tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : >info->range_min; >+ for (i = 2; i < branch_num; i++) >+ { >+ tree elt = gimple_switch_label (swtch, i); >+ wide_int w = last; >+ if (w + 1 != CASE_LOW (elt)) >+ { >+ info->contiguous_range = false; >+ break; >+ } >+ last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt); >+ } >+ >+ if (info->contiguous_range) >+ { >+ first = label_to_block (CASE_LABEL (gimple_switch_label (swtch, >1))); >+ e_first = find_edge (info->switch_bb, first); >+ } >+ else >+ { >+ first = info->default_bb; >+ e_first = e_default; >+ } >+ > /* See if there is one common successor block for all branch > targets. If it exists, record it in FINAL_BB. >- Start with the destination of the default case as guess >- or its destination in case it is a forwarder block. */ >- if (! single_pred_p (e_default->dest)) >- info->final_bb = e_default->dest; >- else if (single_succ_p (e_default->dest) >- && ! single_pred_p (single_succ (e_default->dest))) >- info->final_bb = single_succ (e_default->dest); >+ Start with the destination of the first non-default case >+ if the range is contiguous and default case otherwise as >+ guess or its destination in case it is a forwarder block. */ >+ if (! single_pred_p (e_first->dest)) >+ info->final_bb = e_first->dest; >+ else if (single_succ_p (e_first->dest) >+ && ! single_pred_p (single_succ (e_first->dest))) >+ info->final_bb = single_succ (e_first->dest); > /* Require that all switch destinations are either that common >- FINAL_BB or a forwarder to it. */ >+ FINAL_BB or a forwarder to it, except for the default >+ case if contiguous range. */ > if (info->final_bb) > FOR_EACH_EDGE (e, ei, info->switch_bb->succs) > { >@@ -647,22 +693,18 @@ collect_switch_conv_info (gswitch *swtch > && single_succ (e->dest) == info->final_bb) > continue; > >+ if (e == e_default && info->contiguous_range) >+ { >+ info->default_case_nonstandard = true; >+ continue; >+ } >+ > info->final_bb = NULL; > break; > } > >- /* Get upper and lower bounds of case values, and the covered range. > */ >- min_case = gimple_switch_label (swtch, 1); >- max_case = gimple_switch_label (swtch, branch_num - 1); >- >- info->range_min = CASE_LOW (min_case); >- if (CASE_HIGH (max_case) != NULL_TREE) >- info->range_max = CASE_HIGH (max_case); >- else >- info->range_max = CASE_LOW (max_case); >- >- info->range_size = >- int_const_binop (MINUS_EXPR, info->range_max, info->range_min); >+ info->range_size >+ = int_const_binop (MINUS_EXPR, info->range_max, info->range_min); > >/* Get a count of the number of case labels. Single-valued case labels > simply count as one, but a case range counts double, since it may >@@ -713,7 +755,7 @@ check_range (struct switch_conv_info *in > static bool > check_all_empty_except_final (struct switch_conv_info *info) > { >- edge e; >+ edge e, e_default = find_edge (info->switch_bb, info->default_bb); > edge_iterator ei; > > FOR_EACH_EDGE (e, ei, info->switch_bb->succs) >@@ -723,6 +765,12 @@ check_all_empty_except_final (struct swi > > if (!empty_block_p (e->dest)) > { >+ if (info->contiguous_range && e == e_default) >+ { >+ info->default_case_nonstandard = true; >+ continue; >+ } >+ > info->reason = "bad case - a non-final BB not empty"; > return false; > } >@@ -737,7 +785,7 @@ check_all_empty_except_final (struct swi > phi nodes are OK, otherwise false. */ > > static bool >-check_final_bb (struct switch_conv_info *info) >+check_final_bb (gswitch *swtch, struct switch_conv_info *info) > { > gphi_iterator gsi; > >@@ -747,6 +795,9 @@ check_final_bb (struct switch_conv_info > gphi *phi = gsi.phi (); > unsigned int i; > >+ if (virtual_operand_p (gimple_phi_result (phi))) >+ continue; >+ > info->phi_count++; > > for (i = 0; i < gimple_phi_num_args (phi); i++) >@@ -754,27 +805,55 @@ check_final_bb (struct switch_conv_info > basic_block bb = gimple_phi_arg_edge (phi, i)->src; > > if (bb == info->switch_bb >- || (single_pred_p (bb) && single_pred (bb) == info->switch_bb)) >+ || (single_pred_p (bb) >+ && single_pred (bb) == info->switch_bb >+ && (!info->default_case_nonstandard >+ || empty_block_p (bb)))) > { > tree reloc, val; >+ const char *reason = NULL; > > val = gimple_phi_arg_def (phi, i); > if (!is_gimple_ip_invariant (val)) >+ reason = "non-invariant value from a case"; >+ else > { >- info->reason = "non-invariant value from a case"; >- return false; /* Non-invariant argument. */ >+ reloc = initializer_constant_valid_p (val, TREE_TYPE (val)); >+ if ((flag_pic && reloc != null_pointer_node) >+ || (!flag_pic && reloc == NULL_TREE)) >+ { >+ if (reloc) >+ reason >+ = "value from a case would need runtime relocations"; >+ else >+ reason >+ = "value from a case is not a valid initializer"; >+ } > } >- reloc = initializer_constant_valid_p (val, TREE_TYPE (val)); >- if ((flag_pic && reloc != null_pointer_node) >- || (!flag_pic && reloc == NULL_TREE)) >+ if (reason) > { >- if (reloc) >- info->reason >- = "value from a case would need runtime relocations"; >- else >- info->reason >- = "value from a case is not a valid initializer"; >- return false; >+ /* For contiguous range, we can allow non-constant >+ or one that needs relocation, as long as it is >+ only reachable from the default case. */ >+ if (bb == info->switch_bb) >+ bb = info->final_bb; >+ if (!info->contiguous_range || bb != info->default_bb) >+ { >+ info->reason = reason; >+ return false; >+ } >+ >+ unsigned int branch_num = gimple_switch_num_labels (swtch); >+ for (unsigned int i = 1; i < branch_num; i++) >+ { >+ tree lab = CASE_LABEL (gimple_switch_label (swtch, i)); >+ if (label_to_block (lab) == bb) >+ { >+ info->reason = reason; >+ return false; >+ } >+ } >+ info->default_case_nonstandard = true; > } > } > } >@@ -815,7 +894,9 @@ free_temp_arrays (struct switch_conv_inf > } > > /* Populate the array of default values in the order of phi nodes. >- DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. >*/ >+ DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch >+ if the range is non-contiguous or the default case has standard >+ structure, otherwise it is the first non-default case instead. */ > > static void >gather_default_values (tree default_case, struct switch_conv_info >*info) >@@ -825,7 +906,8 @@ gather_default_values (tree default_case > edge e; > int i = 0; > >- gcc_assert (CASE_LOW (default_case) == NULL_TREE); >+ gcc_assert (CASE_LOW (default_case) == NULL_TREE >+ || info->default_case_nonstandard); > > if (bb == info->final_bb) > e = find_edge (info->switch_bb, bb); >@@ -835,6 +917,8 @@ gather_default_values (tree default_case >for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next >(&gsi)) > { > gphi *phi = gsi.phi (); >+ if (virtual_operand_p (gimple_phi_result (phi))) >+ continue; > tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); > gcc_assert (val); > info->default_values[i++] = val; >@@ -850,6 +934,7 @@ build_constructors (gswitch *swtch, stru > { > unsigned i, branch_num = gimple_switch_num_labels (swtch); > tree pos = info->range_min; >+ tree pos_one = build_int_cst (TREE_TYPE (pos), 1); > > for (i = 1; i < branch_num; i++) > { >@@ -869,6 +954,7 @@ build_constructors (gswitch *swtch, stru > while (tree_int_cst_lt (pos, CASE_LOW (cs))) > { > int k; >+ gcc_assert (!info->contiguous_range); > for (k = 0; k < info->phi_count; k++) > { > constructor_elt elt; >@@ -879,8 +965,7 @@ build_constructors (gswitch *swtch, stru > info->constructors[k]->quick_push (elt); > } > >- pos = int_const_binop (PLUS_EXPR, pos, >- build_int_cst (TREE_TYPE (pos), 1)); >+ pos = int_const_binop (PLUS_EXPR, pos, pos_one); > } > gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs))); > >@@ -893,6 +978,8 @@ build_constructors (gswitch *swtch, stru > !gsi_end_p (gsi); gsi_next (&gsi)) > { > gphi *phi = gsi.phi (); >+ if (virtual_operand_p (gimple_phi_result (phi))) >+ continue; > tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); > tree low = CASE_LOW (cs); > pos = CASE_LOW (cs); >@@ -905,8 +992,7 @@ build_constructors (gswitch *swtch, stru > elt.value = unshare_expr_without_location (val); > info->constructors[j]->quick_push (elt); > >- pos = int_const_binop (PLUS_EXPR, pos, >- build_int_cst (TREE_TYPE (pos), 1)); >+ pos = int_const_binop (PLUS_EXPR, pos, pos_one); > } while (!tree_int_cst_lt (high, pos) > && tree_int_cst_lt (low, pos)); > j++; >@@ -1118,8 +1204,12 @@ build_arrays (gswitch *swtch, struct swi > info->arr_ref_first = stmt; > > for (gpi = gsi_start_phis (info->final_bb), i = 0; >- !gsi_end_p (gpi); gsi_next (&gpi), i++) >- build_one_array (swtch, i, arr_index_type, gpi.phi (), tidx, >info); >+ !gsi_end_p (gpi); gsi_next (&gpi)) >+ { >+ gphi *phi = gpi.phi (); >+ if (!virtual_operand_p (gimple_phi_result (phi))) >+ build_one_array (swtch, i++, arr_index_type, phi, tidx, info); >+ } > } > >/* Generates and appropriately inserts loads of default values at the >position >@@ -1148,7 +1238,7 @@ gen_def_assigns (gimple_stmt_iterator *g > of succession). */ > > static void >-prune_bbs (basic_block bbd, basic_block final) >+prune_bbs (basic_block bbd, basic_block final, basic_block default_bb) > { > edge_iterator ei; > edge e; >@@ -1158,7 +1248,7 @@ prune_bbs (basic_block bbd, basic_block > basic_block bb; > bb = e->dest; > remove_edge (e); >- if (bb != final) >+ if (bb != final && bb != default_bb) > delete_basic_block (bb); > } > delete_basic_block (bbd); >@@ -1177,11 +1267,20 @@ fix_phi_nodes (edge e1f, edge e2f, basic > int i; > > for (gsi = gsi_start_phis (bbf), i = 0; >- !gsi_end_p (gsi); gsi_next (&gsi), i++) >+ !gsi_end_p (gsi); gsi_next (&gsi)) > { > gphi *phi = gsi.phi (); >- add_phi_arg (phi, info->target_inbound_names[i], e1f, >UNKNOWN_LOCATION); >- add_phi_arg (phi, info->target_outbound_names[i], e2f, >UNKNOWN_LOCATION); >+ tree inbound, outbound; >+ if (virtual_operand_p (gimple_phi_result (phi))) >+ inbound = outbound = gimple_vop (cfun); >+ else >+ { >+ inbound = info->target_inbound_names[i]; >+ outbound = info->target_outbound_names[i++]; >+ } >+ add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION); >+ if (!info->default_case_nonstandard) >+ add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION); > } > } > >@@ -1218,10 +1317,10 @@ gen_inbound_check (gswitch *swtch, struc > > gcond *cond_stmt; > >- gassign *last_assign; >+ gassign *last_assign = NULL; > gimple_stmt_iterator gsi; > basic_block bb0, bb1, bb2, bbf, bbd; >- edge e01, e02, e21, e1d, e1f, e2f; >+ edge e01 = NULL, e02, e21, e1d, e1f, e2f; > location_t loc = gimple_location (swtch); > > gcc_assert (info->default_values); >@@ -1241,9 +1340,12 @@ gen_inbound_check (gswitch *swtch, struc > update_stmt (cond_stmt); > > /* block 2 */ >- label2 = gimple_build_label (label_decl2); >- gsi_insert_before (&gsi, label2, GSI_SAME_STMT); >- last_assign = gen_def_assigns (&gsi, info); >+ if (!info->default_case_nonstandard) >+ { >+ label2 = gimple_build_label (label_decl2); >+ gsi_insert_before (&gsi, label2, GSI_SAME_STMT); >+ last_assign = gen_def_assigns (&gsi, info); >+ } > > /* block 1 */ > label1 = gimple_build_label (label_decl1); >@@ -1258,16 +1360,40 @@ gen_inbound_check (gswitch *swtch, struc > e02 = split_block (bb0, cond_stmt); > bb2 = e02->dest; > >- e21 = split_block (bb2, last_assign); >- bb1 = e21->dest; >- remove_edge (e21); >+ if (info->default_case_nonstandard) >+ { >+ bb1 = bb2; >+ bb2 = info->default_bb; >+ e01 = e02; >+ e01->flags = EDGE_TRUE_VALUE; >+ e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE); >+ edge e_default = find_edge (bb1, bb2); >+ for (gphi_iterator gsi = gsi_start_phis (bb2); >+ !gsi_end_p (gsi); gsi_next (&gsi)) >+ { >+ gphi *phi = gsi.phi (); >+ tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_default); >+ add_phi_arg (phi, arg, e02, >+ gimple_phi_arg_location_from_edge (phi, e_default)); >+ } >+ /* Partially fix the dominator tree, if it is available. */ >+ if (dom_info_available_p (CDI_DOMINATORS)) >+ redirect_immediate_dominators (CDI_DOMINATORS, bb1, bb0); >+ } >+ else >+ { >+ e21 = split_block (bb2, last_assign); >+ bb1 = e21->dest; >+ remove_edge (e21); >+ } > > e1d = split_block (bb1, info->arr_ref_last); > bbd = e1d->dest; > remove_edge (e1d); > > /* flags and profiles of the edge for in-range values */ >- e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE); >+ if (!info->default_case_nonstandard) >+ e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE); > e01->probability = REG_BR_PROB_BASE - info->default_prob; > e01->count = info->other_count; > >@@ -1283,17 +1409,24 @@ gen_inbound_check (gswitch *swtch, struc > e1f->probability = REG_BR_PROB_BASE; > e1f->count = info->other_count; > >- e2f = make_edge (bb2, bbf, EDGE_FALLTHRU); >- e2f->probability = REG_BR_PROB_BASE; >- e2f->count = info->default_count; >+ if (info->default_case_nonstandard) >+ e2f = NULL; >+ else >+ { >+ e2f = make_edge (bb2, bbf, EDGE_FALLTHRU); >+ e2f->probability = REG_BR_PROB_BASE; >+ e2f->count = info->default_count; >+ } > > /* frequencies of the new BBs */ > bb1->frequency = EDGE_FREQUENCY (e01); > bb2->frequency = EDGE_FREQUENCY (e02); >- bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f); >+ if (!info->default_case_nonstandard) >+ bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f); > > /* Tidy blocks that have become unreachable. */ >- prune_bbs (bbd, info->final_bb); >+ prune_bbs (bbd, info->final_bb, >+ info->default_case_nonstandard ? info->default_bb : NULL); > > /* Fixup the PHI nodes in bbF. */ > fix_phi_nodes (e1f, e2f, bbf, info); >@@ -1304,15 +1437,17 @@ gen_inbound_check (gswitch *swtch, struc > vec<basic_block> bbs_to_fix_dom; > > set_immediate_dominator (CDI_DOMINATORS, bb1, bb0); >- set_immediate_dominator (CDI_DOMINATORS, bb2, bb0); >+ if (!info->default_case_nonstandard) >+ set_immediate_dominator (CDI_DOMINATORS, bb2, bb0); > if (! get_immediate_dominator (CDI_DOMINATORS, bbf)) > /* If bbD was the immediate dominator ... */ > set_immediate_dominator (CDI_DOMINATORS, bbf, bb0); > >- bbs_to_fix_dom.create (4); >+ bbs_to_fix_dom.create (3 + (bb2 != bbf)); > bbs_to_fix_dom.quick_push (bb0); > bbs_to_fix_dom.quick_push (bb1); >- bbs_to_fix_dom.quick_push (bb2); >+ if (bb2 != bbf) >+ bbs_to_fix_dom.quick_push (bb2); > bbs_to_fix_dom.quick_push (bbf); > > iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true); >@@ -1387,7 +1522,7 @@ process_switch (gswitch *swtch) > gcc_assert (info.reason); > return info.reason; > } >- if (!check_final_bb (&info)) >+ if (!check_final_bb (swtch, &info)) > { > gcc_assert (info.reason); > return info.reason; >@@ -1397,7 +1532,9 @@ process_switch (gswitch *swtch) > transformation. */ > > create_temp_arrays (&info); >- gather_default_values (gimple_switch_default_label (swtch), &info); >+ gather_default_values (info.default_case_nonstandard >+ ? gimple_switch_label (swtch, 1) >+ : gimple_switch_default_label (swtch), &info); > build_constructors (swtch, &info); > >build_arrays (swtch, &info); /* Build the static arrays and >assignments. */ >--- gcc/testsuite/gcc.dg/tree-ssa/cswtch-3.c.jj 2017-02-14 >15:46:55.002417399 +0100 >+++ gcc/testsuite/gcc.dg/tree-ssa/cswtch-3.c 2017-02-14 >15:46:55.002417399 +0100 >@@ -0,0 +1,330 @@ >+/* PR tree-optimization/79472 */ >+/* { dg-options "-O2 -fdump-tree-switchconv" } */ >+/* { dg-do run } */ >+ >+int *expected; >+ >+void >+foo (int x, int y) >+{ >+ if (x != expected[0] || y != expected[1]) >+ __builtin_abort (); >+ expected += 2; >+} >+ >+__attribute__((noinline, noclone)) void >+f1 (int v, int w) >+{ >+ int i, j; >+ if (w) >+ { >+ i = 129; >+ j = i - 1; >+ goto lab; >+ } >+ switch (v) >+ { >+ case 170: >+ j = 7; >+ i = 27; >+ break; >+ case 171: >+ i = 8; >+ j = 122; >+ break; >+ case 172: >+ i = 21; >+ j = -19; >+ break; >+ case 173: >+ i = 18; >+ j = 17; >+ break; >+ case 174: >+ i = 139; >+ j = -5; >+ break; >+ case 175: >+ i = 14; >+ j = -26; >+ break; >+ case 176: >+ j = 5; >+ i = -14; >+ break; >+ case 177: >+ j = 8; >+ i = 12; >+ break; >+ default: >+ __builtin_abort (); >+ } >+ >+ lab: >+ foo (i, j); >+} >+ >+__attribute__((noinline, noclone)) void >+f2 (int v) >+{ >+ int i, j; >+ switch (v) >+ { >+ case 170: >+ j = 7; >+ i = 27; >+ break; >+ case 171: >+ i = 8; >+ j = 122; >+ break; >+ case 172: >+ i = 21; >+ j = -19; >+ break; >+ case 173: >+ i = 18; >+ j = 17; >+ break; >+ case 174: >+ i = 139; >+ j = -5; >+ break; >+ case 175: >+ i = 14; >+ j = -26; >+ break; >+ case 176: >+ j = 5; >+ i = -14; >+ break; >+ case 177: >+ j = 8; >+ i = 12; >+ break; >+ default: >+ foo (5, 12); >+ foo (17, 19); >+ i = 8; >+ j = 19; >+ break; >+ } >+ >+ foo (i, j); >+} >+ >+__attribute__((noinline, noclone)) void >+f3 (int v) >+{ >+ int i; >+ switch (v) >+ { >+ default: >+ i = v; >+ goto lab; >+ case 170: >+ i = 27; >+ break; >+ case 171: >+ i = 8; >+ break; >+ case 172: >+ i = 21; >+ break; >+ case 173: >+ i = 18; >+ break; >+ case 174: >+ i = 139; >+ break; >+ case 175: >+ i = 14; >+ break; >+ case 176: >+ i = -14; >+ break; >+ case 177: >+ i = 12; >+ break; >+ } >+ >+ lab: >+ foo (i, -5); >+} >+ >+__attribute__((noinline, noclone)) void >+f4 (int v, int w) >+{ >+ int i, j, k = 5; >+ if (w) >+ { >+ foo (0, 0); >+ k = 26; >+ goto do_default; >+ } >+ switch (v) >+ { >+ case 170: >+ j = 7; >+ i = 27; >+ break; >+ case 171: >+ i = 8; >+ j = 122; >+ break; >+ case 172: >+ i = 21; >+ j = -19; >+ break; >+ case 173: >+ i = 18; >+ j = 17; >+ break; >+ case 174: >+ i = 139; >+ j = -5; >+ break; >+ case 175: >+ i = 14; >+ j = -26; >+ break; >+ case 176: >+ j = 5; >+ i = -14; >+ break; >+ case 177: >+ j = 8; >+ i = 12; >+ break; >+ default: >+ do_default: >+ foo (5, 12); >+ foo (17, 19); >+ i = 8; >+ j = 19; >+ break; >+ } >+ >+ foo (i, j + k); >+} >+ >+void >+f5 (int v, int w) >+{ >+ int i; >+ if (w) >+ { >+ foo (23, 0); >+ i = 129; >+ } >+ else >+ switch (v) >+ { >+ case 170: >+ i = 27; >+ break; >+ case 171: >+ i = 8; >+ break; >+ case 172: >+ i = 21; >+ break; >+ case 173: >+ i = 18; >+ break; >+ case 174: >+ i = 139; >+ break; >+ case 175: >+ i = 14; >+ break; >+ case 176: >+ i = -14; >+ break; >+ case 177: >+ i = 12; >+ break; >+ default: >+ i = 80; >+ break; >+ } >+ >+ lab: >+ foo (i, 0); >+} >+ >+int >+main () >+{ >+ int *e; >+#define T(call, cnt, ...) \ >+ expected = e = (int []) __VA_ARGS__; \ >+ call; \ >+ if (expected != e + cnt) \ >+ __builtin_abort () >+ T (f1 (171, 1), 2, { 129, 128 }); >+ T (f1 (140, 1), 2, { 129, 128 }); >+ T (f1 (170, 0), 2, { 27, 7 }); >+ T (f1 (171, 0), 2, { 8, 122 }); >+ T (f1 (172, 0), 2, { 21, -19 }); >+ T (f1 (173, 0), 2, { 18, 17 }); >+ T (f1 (174, 0), 2, { 139, -5 }); >+ T (f1 (175, 0), 2, { 14, -26 }); >+ T (f1 (176, 0), 2, { -14, 5 }); >+ T (f1 (177, 0), 2, { 12, 8 }); >+ T (f2 (-31), 6, { 5, 12, 17, 19, 8, 19 }); >+ T (f2 (169), 6, { 5, 12, 17, 19, 8, 19 }); >+ T (f2 (170), 2, { 27, 7 }); >+ T (f2 (171), 2, { 8, 122 }); >+ T (f2 (172), 2, { 21, -19 }); >+ T (f2 (173), 2, { 18, 17 }); >+ T (f2 (174), 2, { 139, -5 }); >+ T (f2 (175), 2, { 14, -26 }); >+ T (f2 (176), 2, { -14, 5 }); >+ T (f2 (177), 2, { 12, 8 }); >+ T (f2 (178), 6, { 5, 12, 17, 19, 8, 19 }); >+ T (f2 (231), 6, { 5, 12, 17, 19, 8, 19 }); >+ T (f3 (-31), 2, { -31, -5 }); >+ T (f3 (169), 2, { 169, -5 }); >+ T (f3 (170), 2, { 27, -5 }); >+ T (f3 (171), 2, { 8, -5 }); >+ T (f3 (172), 2, { 21, -5 }); >+ T (f3 (173), 2, { 18, -5 }); >+ T (f3 (174), 2, { 139, -5 }); >+ T (f3 (175), 2, { 14, -5 }); >+ T (f3 (176), 2, { -14, -5 }); >+ T (f3 (177), 2, { 12, -5 }); >+ T (f3 (178), 2, { 178, -5 }); >+ T (f3 (231), 2, { 231, -5 }); >+ T (f4 (171, 1), 8, { 0, 0, 5, 12, 17, 19, 8, 45 }); >+ T (f4 (140, 1), 8, { 0, 0, 5, 12, 17, 19, 8, 45 }); >+ T (f4 (-31, 0), 6, { 5, 12, 17, 19, 8, 24 }); >+ T (f4 (169, 0), 6, { 5, 12, 17, 19, 8, 24 }); >+ T (f4 (170, 0), 2, { 27, 12 }); >+ T (f4 (171, 0), 2, { 8, 127 }); >+ T (f4 (172, 0), 2, { 21, -14 }); >+ T (f4 (173, 0), 2, { 18, 22 }); >+ T (f4 (174, 0), 2, { 139, 0 }); >+ T (f4 (175, 0), 2, { 14, -21 }); >+ T (f4 (176, 0), 2, { -14, 10 }); >+ T (f4 (177, 0), 2, { 12, 13 }); >+ T (f4 (178, 0), 6, { 5, 12, 17, 19, 8, 24 }); >+ T (f4 (231, 0), 6, { 5, 12, 17, 19, 8, 24 }); >+ T (f5 (171, 1), 4, { 23, 0, 129, 0 }); >+ T (f5 (140, 1), 4, { 23, 0, 129, 0 }); >+ T (f5 (-31, 0), 2, { 80, 0 }); >+ T (f5 (169, 0), 2, { 80, 0 }); >+ T (f5 (170, 0), 2, { 27, 0 }); >+ T (f5 (171, 0), 2, { 8, 0 }); >+ T (f5 (172, 0), 2, { 21, 0 }); >+ T (f5 (173, 0), 2, { 18, 0 }); >+ T (f5 (174, 0), 2, { 139, 0 }); >+ T (f5 (175, 0), 2, { 14, 0 }); >+ T (f5 (176, 0), 2, { -14, 0 }); >+ T (f5 (177, 0), 2, { 12, 0 }); >+ T (f5 (178, 0), 2, { 80, 0 }); >+ T (f5 (231, 0), 2, { 80, 0 }); >+} >+ >+/* { dg-final { scan-tree-dump-times "Switch converted" 5 "switchconv" >} } */ >+/* { dg-final { scan-tree-dump-times "= CSWTCH" 8 "switchconv" } } */ >--- gcc/testsuite/gcc.dg/tree-ssa/cswtch-4.c.jj 2017-02-14 >15:46:55.003417386 +0100 >+++ gcc/testsuite/gcc.dg/tree-ssa/cswtch-4.c 2017-02-14 >15:46:55.003417386 +0100 >@@ -0,0 +1,57 @@ >+/* PR tree-optimization/79472 */ >+/* { dg-options "-O2 -fdump-tree-switchconv" } */ >+/* { dg-do compile } */ >+ >+void >+frobulate (unsigned int v) >+{ >+ const char *s; >+ >+ switch (v) >+ { >+ case 0: >+ s = "foo"; >+ break; >+ case 1: >+ s = "bar"; >+ break; >+ case 2: >+ s = "spam"; >+ break; >+ default: >+ __builtin_abort (); >+ break; >+ } >+ >+ __builtin_printf ("%s\n", s); >+} >+ >+void >+frobulate_for_gcc (unsigned int v) >+{ >+ const char *s; >+ >+ switch (v) >+ { >+ case 0: >+ s = "foo"; >+ break; >+ case 1: >+ s = "bar"; >+ break; >+ case 2: >+ s = "spam"; >+ break; >+ default: >+ s = (const char *) 0; >+ break; >+ } >+ >+ if (!s) >+ __builtin_abort (); >+ >+ __builtin_printf ("%s\n", s); >+} >+ >+/* { dg-final { scan-tree-dump-times "Switch converted" 2 "switchconv" >} } */ >+/* { dg-final { scan-tree-dump-times "= CSWTCH" 2 "switchconv" } } */ >--- gcc/testsuite/gcc.dg/tree-ssa/cswtch-5.c.jj 2017-02-14 >17:11:40.802710606 +0100 >+++ gcc/testsuite/gcc.dg/tree-ssa/cswtch-5.c 2017-02-14 >17:13:59.424872889 +0100 >@@ -0,0 +1,66 @@ >+/* PR tree-optimization/79472 */ >+/* { dg-options "-O2 -fdump-tree-switchconv" } */ >+/* { dg-do compile } */ >+ >+void >+foo (unsigned int v) >+{ >+ const char *s; >+ >+ switch (v) >+ { >+ case 0: >+ s = "foo"; >+ break; >+ case 1: >+ s = "bar"; >+ break; >+ case 2: >+ s = "spam"; >+ break; >+ default: >+ for (int i = 0; i < v; i++) >+ __builtin_printf ("baz\n"); >+ return; >+ } >+ >+ __builtin_printf ("%s\n", s); >+} >+ >+int >+bar (unsigned int v, int w) >+{ >+ const char *s; >+ >+ switch (v) >+ { >+ case 0: >+ s = "foo"; >+ break; >+ case 1: >+ s = "bar"; >+ break; >+ case 2: >+ s = "spam"; >+ break; >+ default: >+ __builtin_printf ("baz\n"); >+ if (v > 25) >+ __builtin_printf ("bl1\n"); >+ else >+ __builtin_printf ("bl2\n"); >+ goto lab; >+ } >+ >+ __builtin_printf ("%s\n", s); >+ if (w > 25) >+ __builtin_printf ("cl1\n"); >+ else >+ __builtin_printf ("cl2\n"); >+ lab: >+ __builtin_printf ("dl\n"); >+ return v + w; >+} >+ >+/* { dg-final { scan-tree-dump-times "Switch converted" 2 "switchconv" >} } */ >+/* { dg-final { scan-tree-dump-times "= CSWTCH" 2 "switchconv" } } */ > > Jakub
On Wed, Feb 15, 2017 at 08:06:16AM +0100, Richard Biener wrote: > On February 14, 2017 9:04:45 PM GMT+01:00, Jakub Jelinek <jakub@redhat.com> wrote: > >Hi! > > > >The following patch is an attempt to fix a regression where we no > >longer > >switch convert one switch because earlier optimizations turn it into > >unsupported shape. > > Is that because of early threading? Yes. > >and expects to be optimized into return 3 by vrp1. As switchconv is > >earlier > >than that, vrp1 sees: > > _1 = a_3(D) & 1; > > _4 = (unsigned int) _1; > > _5 = CSWTCH.1[_4]; > > return _5; > >and doesn't optimize it. If the testcase had say case 7: replaced with > >default:, it wouldn't pass already before. > > That looks odd... Just a pass ordering issue. > If the patch is ok, what > >should > >we do with vrp40.c? Change it in some way (e.g. return variable in one > >case) so that switchconv doesn't trigger, or add an optimization in vrp > >if we see a load from constant array with known initializer and the > >range > >is small enough and contains the same value for all those values, > >replace > >it with the value? > > Possibly, but for GCC 8. To both this switchconv patch and the potential improvement for loading from const arrays (can create an enhancement PR for that), or just the latter? > can we teach EVRP about this? It runs before switch conversion. I guess so. It is a matter of calling simplify_switch_using_ranges and then doing some cleanup (you wrote that optimization) - to_update_switch_stmts handling. Jakub
On 15/02/17 08:17, Jakub Jelinek wrote: > On Wed, Feb 15, 2017 at 08:06:16AM +0100, Richard Biener wrote: >> On February 14, 2017 9:04:45 PM GMT+01:00, Jakub Jelinek <jakub@redhat.com> wrote: >>> Hi! >>> >>> The following patch is an attempt to fix a regression where we no >>> longer >>> switch convert one switch because earlier optimizations turn it into >>> unsupported shape. >> >> Is that because of early threading? > > Yes. > >>> and expects to be optimized into return 3 by vrp1. As switchconv is >>> earlier >>> than that, vrp1 sees: >>> _1 = a_3(D) & 1; >>> _4 = (unsigned int) _1; >>> _5 = CSWTCH.1[_4]; >>> return _5; >>> and doesn't optimize it. If the testcase had say case 7: replaced with >>> default:, it wouldn't pass already before. >> >> That looks odd... > > Just a pass ordering issue. > >> If the patch is ok, what >>> should >>> we do with vrp40.c? Change it in some way (e.g. return variable in one >>> case) so that switchconv doesn't trigger, or add an optimization in vrp >>> if we see a load from constant array with known initializer and the >>> range >>> is small enough and contains the same value for all those values, >>> replace >>> it with the value? >> >> Possibly, but for GCC 8. > > To both this switchconv patch and the potential improvement for loading > from const arrays (can create an enhancement PR for that), or just the > latter? Both I think - the patch is pretty big. Maybe we can instead make early threading not mess this up? >> can we teach EVRP about this? It runs before switch conversion. > > I guess so. It is a matter of calling simplify_switch_using_ranges > and then doing some cleanup (you wrote that optimization) > - to_update_switch_stmts handling. Sounds like a good thing to do (for GCC 8 as well). Thanks, Richard. > > Jakub >
On Wed, Feb 15, 2017 at 12:46:44PM +0100, Richard Biener wrote: > >> Possibly, but for GCC 8. > > > > To both this switchconv patch and the potential improvement for loading > > from const arrays (can create an enhancement PR for that), or just the > > latter? > > Both I think - the patch is pretty big. Ok, I'll queue the patch for GCC8 then. > Maybe we can instead make early > threading not mess this up? Maybe, but not planning to do that myself, my knowledge about jump threading is too limited. > >> can we teach EVRP about this? It runs before switch conversion. > > > > I guess so. It is a matter of calling simplify_switch_using_ranges > > and then doing some cleanup (you wrote that optimization) > > - to_update_switch_stmts handling. > > Sounds like a good thing to do (for GCC 8 as well). Ok, will file enhancement PRs. Jakub
On 02/15/2017 04:51 AM, Jakub Jelinek wrote: > On Wed, Feb 15, 2017 at 12:46:44PM +0100, Richard Biener wrote: >>>> Possibly, but for GCC 8. >>> >>> To both this switchconv patch and the potential improvement for loading >>> from const arrays (can create an enhancement PR for that), or just the >>> latter? >> >> Both I think - the patch is pretty big. > > Ok, I'll queue the patch for GCC8 then. > >> Maybe we can instead make early >> threading not mess this up? > > Maybe, but not planning to do that myself, my knowledge about jump threading > is too limited. The problem is at the point where we thread all we see is this: # s_1 = PHI <"foo"(2), "bar"(3), "spam"(4), 0B(5)> <L7>: if (s_1 == 0B) goto <bb 7>; else goto <bb 8>; Nothing more is needed for jump threading to do its job. This doesn't look any different to the threader than any other simple jump threading opportunity. I guess we could look to see if the PHI is the join point for a switch, but that seems rather hacky. jeff
--- gcc/tree-switch-conversion.c.jj 2017-02-14 14:54:08.020975500 +0100 +++ gcc/tree-switch-conversion.c 2017-02-14 17:09:01.162826954 +0100 @@ -592,6 +592,14 @@ struct switch_conv_info dump file, if there is one. */ const char *reason; + /* True if default case is not used for any value between range_min and + range_max inclusive. */ + bool contiguous_range; + + /* True if default case does not have the required shape for other case + labels. */ + bool default_case_nonstandard; + /* Parameters for expand_switch_using_bit_tests. Should be computed the same way as in expand_case. */ unsigned int uniq; @@ -606,8 +614,9 @@ collect_switch_conv_info (gswitch *swtch unsigned int branch_num = gimple_switch_num_labels (swtch); tree min_case, max_case; unsigned int count, i; - edge e, e_default; + edge e, e_default, e_first; edge_iterator ei; + basic_block first; memset (info, 0, sizeof (*info)); @@ -616,8 +625,8 @@ collect_switch_conv_info (gswitch *swtch Collect the bits we can deduce from the CFG. */ info->index_expr = gimple_switch_index (swtch); info->switch_bb = gimple_bb (swtch); - info->default_bb = - label_to_block (CASE_LABEL (gimple_switch_default_label (swtch))); + info->default_bb + = label_to_block (CASE_LABEL (gimple_switch_default_label (swtch))); e_default = find_edge (info->switch_bb, info->default_bb); info->default_prob = e_default->probability; info->default_count = e_default->count; @@ -625,17 +634,54 @@ collect_switch_conv_info (gswitch *swtch if (e != e_default) info->other_count += e->count; + /* Get upper and lower bounds of case values, and the covered range. */ + min_case = gimple_switch_label (swtch, 1); + max_case = gimple_switch_label (swtch, branch_num - 1); + + info->range_min = CASE_LOW (min_case); + if (CASE_HIGH (max_case) != NULL_TREE) + info->range_max = CASE_HIGH (max_case); + else + info->range_max = CASE_LOW (max_case); + + info->contiguous_range = true; + tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : info->range_min; + for (i = 2; i < branch_num; i++) + { + tree elt = gimple_switch_label (swtch, i); + wide_int w = last; + if (w + 1 != CASE_LOW (elt)) + { + info->contiguous_range = false; + break; + } + last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt); + } + + if (info->contiguous_range) + { + first = label_to_block (CASE_LABEL (gimple_switch_label (swtch, 1))); + e_first = find_edge (info->switch_bb, first); + } + else + { + first = info->default_bb; + e_first = e_default; + } + /* See if there is one common successor block for all branch targets. If it exists, record it in FINAL_BB. - Start with the destination of the default case as guess - or its destination in case it is a forwarder block. */ - if (! single_pred_p (e_default->dest)) - info->final_bb = e_default->dest; - else if (single_succ_p (e_default->dest) - && ! single_pred_p (single_succ (e_default->dest))) - info->final_bb = single_succ (e_default->dest); + Start with the destination of the first non-default case + if the range is contiguous and default case otherwise as + guess or its destination in case it is a forwarder block. */ + if (! single_pred_p (e_first->dest)) + info->final_bb = e_first->dest; + else if (single_succ_p (e_first->dest) + && ! single_pred_p (single_succ (e_first->dest))) + info->final_bb = single_succ (e_first->dest); /* Require that all switch destinations are either that common - FINAL_BB or a forwarder to it. */ + FINAL_BB or a forwarder to it, except for the default + case if contiguous range. */ if (info->final_bb) FOR_EACH_EDGE (e, ei, info->switch_bb->succs) { @@ -647,22 +693,18 @@ collect_switch_conv_info (gswitch *swtch && single_succ (e->dest) == info->final_bb) continue; + if (e == e_default && info->contiguous_range) + { + info->default_case_nonstandard = true; + continue; + } + info->final_bb = NULL; break; } - /* Get upper and lower bounds of case values, and the covered range. */ - min_case = gimple_switch_label (swtch, 1); - max_case = gimple_switch_label (swtch, branch_num - 1); - - info->range_min = CASE_LOW (min_case); - if (CASE_HIGH (max_case) != NULL_TREE) - info->range_max = CASE_HIGH (max_case); - else - info->range_max = CASE_LOW (max_case); - - info->range_size = - int_const_binop (MINUS_EXPR, info->range_max, info->range_min); + info->range_size + = int_const_binop (MINUS_EXPR, info->range_max, info->range_min); /* Get a count of the number of case labels. Single-valued case labels simply count as one, but a case range counts double, since it may @@ -713,7 +755,7 @@ check_range (struct switch_conv_info *in static bool check_all_empty_except_final (struct switch_conv_info *info) { - edge e; + edge e, e_default = find_edge (info->switch_bb, info->default_bb); edge_iterator ei; FOR_EACH_EDGE (e, ei, info->switch_bb->succs) @@ -723,6 +765,12 @@ check_all_empty_except_final (struct swi if (!empty_block_p (e->dest)) { + if (info->contiguous_range && e == e_default) + { + info->default_case_nonstandard = true; + continue; + } + info->reason = "bad case - a non-final BB not empty"; return false; } @@ -737,7 +785,7 @@ check_all_empty_except_final (struct swi phi nodes are OK, otherwise false. */ static bool -check_final_bb (struct switch_conv_info *info) +check_final_bb (gswitch *swtch, struct switch_conv_info *info) { gphi_iterator gsi; @@ -747,6 +795,9 @@ check_final_bb (struct switch_conv_info gphi *phi = gsi.phi (); unsigned int i; + if (virtual_operand_p (gimple_phi_result (phi))) + continue; + info->phi_count++; for (i = 0; i < gimple_phi_num_args (phi); i++) @@ -754,27 +805,55 @@ check_final_bb (struct switch_conv_info basic_block bb = gimple_phi_arg_edge (phi, i)->src; if (bb == info->switch_bb - || (single_pred_p (bb) && single_pred (bb) == info->switch_bb)) + || (single_pred_p (bb) + && single_pred (bb) == info->switch_bb + && (!info->default_case_nonstandard + || empty_block_p (bb)))) { tree reloc, val; + const char *reason = NULL; val = gimple_phi_arg_def (phi, i); if (!is_gimple_ip_invariant (val)) + reason = "non-invariant value from a case"; + else { - info->reason = "non-invariant value from a case"; - return false; /* Non-invariant argument. */ + reloc = initializer_constant_valid_p (val, TREE_TYPE (val)); + if ((flag_pic && reloc != null_pointer_node) + || (!flag_pic && reloc == NULL_TREE)) + { + if (reloc) + reason + = "value from a case would need runtime relocations"; + else + reason + = "value from a case is not a valid initializer"; + } } - reloc = initializer_constant_valid_p (val, TREE_TYPE (val)); - if ((flag_pic && reloc != null_pointer_node) - || (!flag_pic && reloc == NULL_TREE)) + if (reason) { - if (reloc) - info->reason - = "value from a case would need runtime relocations"; - else - info->reason - = "value from a case is not a valid initializer"; - return false; + /* For contiguous range, we can allow non-constant + or one that needs relocation, as long as it is + only reachable from the default case. */ + if (bb == info->switch_bb) + bb = info->final_bb; + if (!info->contiguous_range || bb != info->default_bb) + { + info->reason = reason; + return false; + } + + unsigned int branch_num = gimple_switch_num_labels (swtch); + for (unsigned int i = 1; i < branch_num; i++) + { + tree lab = CASE_LABEL (gimple_switch_label (swtch, i)); + if (label_to_block (lab) == bb) + { + info->reason = reason; + return false; + } + } + info->default_case_nonstandard = true; } } } @@ -815,7 +894,9 @@ free_temp_arrays (struct switch_conv_inf } /* Populate the array of default values in the order of phi nodes. - DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */ + DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch + if the range is non-contiguous or the default case has standard + structure, otherwise it is the first non-default case instead. */ static void gather_default_values (tree default_case, struct switch_conv_info *info) @@ -825,7 +906,8 @@ gather_default_values (tree default_case edge e; int i = 0; - gcc_assert (CASE_LOW (default_case) == NULL_TREE); + gcc_assert (CASE_LOW (default_case) == NULL_TREE + || info->default_case_nonstandard); if (bb == info->final_bb) e = find_edge (info->switch_bb, bb); @@ -835,6 +917,8 @@ gather_default_values (tree default_case for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) { gphi *phi = gsi.phi (); + if (virtual_operand_p (gimple_phi_result (phi))) + continue; tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); gcc_assert (val); info->default_values[i++] = val; @@ -850,6 +934,7 @@ build_constructors (gswitch *swtch, stru { unsigned i, branch_num = gimple_switch_num_labels (swtch); tree pos = info->range_min; + tree pos_one = build_int_cst (TREE_TYPE (pos), 1); for (i = 1; i < branch_num; i++) { @@ -869,6 +954,7 @@ build_constructors (gswitch *swtch, stru while (tree_int_cst_lt (pos, CASE_LOW (cs))) { int k; + gcc_assert (!info->contiguous_range); for (k = 0; k < info->phi_count; k++) { constructor_elt elt; @@ -879,8 +965,7 @@ build_constructors (gswitch *swtch, stru info->constructors[k]->quick_push (elt); } - pos = int_const_binop (PLUS_EXPR, pos, - build_int_cst (TREE_TYPE (pos), 1)); + pos = int_const_binop (PLUS_EXPR, pos, pos_one); } gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs))); @@ -893,6 +978,8 @@ build_constructors (gswitch *swtch, stru !gsi_end_p (gsi); gsi_next (&gsi)) { gphi *phi = gsi.phi (); + if (virtual_operand_p (gimple_phi_result (phi))) + continue; tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); tree low = CASE_LOW (cs); pos = CASE_LOW (cs); @@ -905,8 +992,7 @@ build_constructors (gswitch *swtch, stru elt.value = unshare_expr_without_location (val); info->constructors[j]->quick_push (elt); - pos = int_const_binop (PLUS_EXPR, pos, - build_int_cst (TREE_TYPE (pos), 1)); + pos = int_const_binop (PLUS_EXPR, pos, pos_one); } while (!tree_int_cst_lt (high, pos) && tree_int_cst_lt (low, pos)); j++; @@ -1118,8 +1204,12 @@ build_arrays (gswitch *swtch, struct swi info->arr_ref_first = stmt; for (gpi = gsi_start_phis (info->final_bb), i = 0; - !gsi_end_p (gpi); gsi_next (&gpi), i++) - build_one_array (swtch, i, arr_index_type, gpi.phi (), tidx, info); + !gsi_end_p (gpi); gsi_next (&gpi)) + { + gphi *phi = gpi.phi (); + if (!virtual_operand_p (gimple_phi_result (phi))) + build_one_array (swtch, i++, arr_index_type, phi, tidx, info); + } } /* Generates and appropriately inserts loads of default values at the position @@ -1148,7 +1238,7 @@ gen_def_assigns (gimple_stmt_iterator *g of succession). */ static void -prune_bbs (basic_block bbd, basic_block final) +prune_bbs (basic_block bbd, basic_block final, basic_block default_bb) { edge_iterator ei; edge e; @@ -1158,7 +1248,7 @@ prune_bbs (basic_block bbd, basic_block basic_block bb; bb = e->dest; remove_edge (e); - if (bb != final) + if (bb != final && bb != default_bb) delete_basic_block (bb); } delete_basic_block (bbd); @@ -1177,11 +1267,20 @@ fix_phi_nodes (edge e1f, edge e2f, basic int i; for (gsi = gsi_start_phis (bbf), i = 0; - !gsi_end_p (gsi); gsi_next (&gsi), i++) + !gsi_end_p (gsi); gsi_next (&gsi)) { gphi *phi = gsi.phi (); - add_phi_arg (phi, info->target_inbound_names[i], e1f, UNKNOWN_LOCATION); - add_phi_arg (phi, info->target_outbound_names[i], e2f, UNKNOWN_LOCATION); + tree inbound, outbound; + if (virtual_operand_p (gimple_phi_result (phi))) + inbound = outbound = gimple_vop (cfun); + else + { + inbound = info->target_inbound_names[i]; + outbound = info->target_outbound_names[i++]; + } + add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION); + if (!info->default_case_nonstandard) + add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION); } } @@ -1218,10 +1317,10 @@ gen_inbound_check (gswitch *swtch, struc gcond *cond_stmt; - gassign *last_assign; + gassign *last_assign = NULL; gimple_stmt_iterator gsi; basic_block bb0, bb1, bb2, bbf, bbd; - edge e01, e02, e21, e1d, e1f, e2f; + edge e01 = NULL, e02, e21, e1d, e1f, e2f; location_t loc = gimple_location (swtch); gcc_assert (info->default_values); @@ -1241,9 +1340,12 @@ gen_inbound_check (gswitch *swtch, struc update_stmt (cond_stmt); /* block 2 */ - label2 = gimple_build_label (label_decl2); - gsi_insert_before (&gsi, label2, GSI_SAME_STMT); - last_assign = gen_def_assigns (&gsi, info); + if (!info->default_case_nonstandard) + { + label2 = gimple_build_label (label_decl2); + gsi_insert_before (&gsi, label2, GSI_SAME_STMT); + last_assign = gen_def_assigns (&gsi, info); + } /* block 1 */ label1 = gimple_build_label (label_decl1); @@ -1258,16 +1360,40 @@ gen_inbound_check (gswitch *swtch, struc e02 = split_block (bb0, cond_stmt); bb2 = e02->dest; - e21 = split_block (bb2, last_assign); - bb1 = e21->dest; - remove_edge (e21); + if (info->default_case_nonstandard) + { + bb1 = bb2; + bb2 = info->default_bb; + e01 = e02; + e01->flags = EDGE_TRUE_VALUE; + e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE); + edge e_default = find_edge (bb1, bb2); + for (gphi_iterator gsi = gsi_start_phis (bb2); + !gsi_end_p (gsi); gsi_next (&gsi)) + { + gphi *phi = gsi.phi (); + tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_default); + add_phi_arg (phi, arg, e02, + gimple_phi_arg_location_from_edge (phi, e_default)); + } + /* Partially fix the dominator tree, if it is available. */ + if (dom_info_available_p (CDI_DOMINATORS)) + redirect_immediate_dominators (CDI_DOMINATORS, bb1, bb0); + } + else + { + e21 = split_block (bb2, last_assign); + bb1 = e21->dest; + remove_edge (e21); + } e1d = split_block (bb1, info->arr_ref_last); bbd = e1d->dest; remove_edge (e1d); /* flags and profiles of the edge for in-range values */ - e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE); + if (!info->default_case_nonstandard) + e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE); e01->probability = REG_BR_PROB_BASE - info->default_prob; e01->count = info->other_count; @@ -1283,17 +1409,24 @@ gen_inbound_check (gswitch *swtch, struc e1f->probability = REG_BR_PROB_BASE; e1f->count = info->other_count; - e2f = make_edge (bb2, bbf, EDGE_FALLTHRU); - e2f->probability = REG_BR_PROB_BASE; - e2f->count = info->default_count; + if (info->default_case_nonstandard) + e2f = NULL; + else + { + e2f = make_edge (bb2, bbf, EDGE_FALLTHRU); + e2f->probability = REG_BR_PROB_BASE; + e2f->count = info->default_count; + } /* frequencies of the new BBs */ bb1->frequency = EDGE_FREQUENCY (e01); bb2->frequency = EDGE_FREQUENCY (e02); - bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f); + if (!info->default_case_nonstandard) + bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f); /* Tidy blocks that have become unreachable. */ - prune_bbs (bbd, info->final_bb); + prune_bbs (bbd, info->final_bb, + info->default_case_nonstandard ? info->default_bb : NULL); /* Fixup the PHI nodes in bbF. */ fix_phi_nodes (e1f, e2f, bbf, info); @@ -1304,15 +1437,17 @@ gen_inbound_check (gswitch *swtch, struc vec<basic_block> bbs_to_fix_dom; set_immediate_dominator (CDI_DOMINATORS, bb1, bb0); - set_immediate_dominator (CDI_DOMINATORS, bb2, bb0); + if (!info->default_case_nonstandard) + set_immediate_dominator (CDI_DOMINATORS, bb2, bb0); if (! get_immediate_dominator (CDI_DOMINATORS, bbf)) /* If bbD was the immediate dominator ... */ set_immediate_dominator (CDI_DOMINATORS, bbf, bb0); - bbs_to_fix_dom.create (4); + bbs_to_fix_dom.create (3 + (bb2 != bbf)); bbs_to_fix_dom.quick_push (bb0); bbs_to_fix_dom.quick_push (bb1); - bbs_to_fix_dom.quick_push (bb2); + if (bb2 != bbf) + bbs_to_fix_dom.quick_push (bb2); bbs_to_fix_dom.quick_push (bbf); iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true); @@ -1387,7 +1522,7 @@ process_switch (gswitch *swtch) gcc_assert (info.reason); return info.reason; } - if (!check_final_bb (&info)) + if (!check_final_bb (swtch, &info)) { gcc_assert (info.reason); return info.reason; @@ -1397,7 +1532,9 @@ process_switch (gswitch *swtch) transformation. */ create_temp_arrays (&info); - gather_default_values (gimple_switch_default_label (swtch), &info); + gather_default_values (info.default_case_nonstandard + ? gimple_switch_label (swtch, 1) + : gimple_switch_default_label (swtch), &info); build_constructors (swtch, &info); build_arrays (swtch, &info); /* Build the static arrays and assignments. */ --- gcc/testsuite/gcc.dg/tree-ssa/cswtch-3.c.jj 2017-02-14 15:46:55.002417399 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/cswtch-3.c 2017-02-14 15:46:55.002417399 +0100 @@ -0,0 +1,330 @@ +/* PR tree-optimization/79472 */ +/* { dg-options "-O2 -fdump-tree-switchconv" } */ +/* { dg-do run } */ + +int *expected; + +void +foo (int x, int y) +{ + if (x != expected[0] || y != expected[1]) + __builtin_abort (); + expected += 2; +} + +__attribute__((noinline, noclone)) void +f1 (int v, int w) +{ + int i, j; + if (w) + { + i = 129; + j = i - 1; + goto lab; + } + switch (v) + { + case 170: + j = 7; + i = 27; + break; + case 171: + i = 8; + j = 122; + break; + case 172: + i = 21; + j = -19; + break; + case 173: + i = 18; + j = 17; + break; + case 174: + i = 139; + j = -5; + break; + case 175: + i = 14; + j = -26; + break; + case 176: + j = 5; + i = -14; + break; + case 177: + j = 8; + i = 12; + break; + default: + __builtin_abort (); + } + + lab: + foo (i, j); +} + +__attribute__((noinline, noclone)) void +f2 (int v) +{ + int i, j; + switch (v) + { + case 170: + j = 7; + i = 27; + break; + case 171: + i = 8; + j = 122; + break; + case 172: + i = 21; + j = -19; + break; + case 173: + i = 18; + j = 17; + break; + case 174: + i = 139; + j = -5; + break; + case 175: + i = 14; + j = -26; + break; + case 176: + j = 5; + i = -14; + break; + case 177: + j = 8; + i = 12; + break; + default: + foo (5, 12); + foo (17, 19); + i = 8; + j = 19; + break; + } + + foo (i, j); +} + +__attribute__((noinline, noclone)) void +f3 (int v) +{ + int i; + switch (v) + { + default: + i = v; + goto lab; + case 170: + i = 27; + break; + case 171: + i = 8; + break; + case 172: + i = 21; + break; + case 173: + i = 18; + break; + case 174: + i = 139; + break; + case 175: + i = 14; + break; + case 176: + i = -14; + break; + case 177: + i = 12; + break; + } + + lab: + foo (i, -5); +} + +__attribute__((noinline, noclone)) void +f4 (int v, int w) +{ + int i, j, k = 5; + if (w) + { + foo (0, 0); + k = 26; + goto do_default; + } + switch (v) + { + case 170: + j = 7; + i = 27; + break; + case 171: + i = 8; + j = 122; + break; + case 172: + i = 21; + j = -19; + break; + case 173: + i = 18; + j = 17; + break; + case 174: + i = 139; + j = -5; + break; + case 175: + i = 14; + j = -26; + break; + case 176: + j = 5; + i = -14; + break; + case 177: + j = 8; + i = 12; + break; + default: + do_default: + foo (5, 12); + foo (17, 19); + i = 8; + j = 19; + break; + } + + foo (i, j + k); +} + +void +f5 (int v, int w) +{ + int i; + if (w) + { + foo (23, 0); + i = 129; + } + else + switch (v) + { + case 170: + i = 27; + break; + case 171: + i = 8; + break; + case 172: + i = 21; + break; + case 173: + i = 18; + break; + case 174: + i = 139; + break; + case 175: + i = 14; + break; + case 176: + i = -14; + break; + case 177: + i = 12; + break; + default: + i = 80; + break; + } + + lab: + foo (i, 0); +} + +int +main () +{ + int *e; +#define T(call, cnt, ...) \ + expected = e = (int []) __VA_ARGS__; \ + call; \ + if (expected != e + cnt) \ + __builtin_abort () + T (f1 (171, 1), 2, { 129, 128 }); + T (f1 (140, 1), 2, { 129, 128 }); + T (f1 (170, 0), 2, { 27, 7 }); + T (f1 (171, 0), 2, { 8, 122 }); + T (f1 (172, 0), 2, { 21, -19 }); + T (f1 (173, 0), 2, { 18, 17 }); + T (f1 (174, 0), 2, { 139, -5 }); + T (f1 (175, 0), 2, { 14, -26 }); + T (f1 (176, 0), 2, { -14, 5 }); + T (f1 (177, 0), 2, { 12, 8 }); + T (f2 (-31), 6, { 5, 12, 17, 19, 8, 19 }); + T (f2 (169), 6, { 5, 12, 17, 19, 8, 19 }); + T (f2 (170), 2, { 27, 7 }); + T (f2 (171), 2, { 8, 122 }); + T (f2 (172), 2, { 21, -19 }); + T (f2 (173), 2, { 18, 17 }); + T (f2 (174), 2, { 139, -5 }); + T (f2 (175), 2, { 14, -26 }); + T (f2 (176), 2, { -14, 5 }); + T (f2 (177), 2, { 12, 8 }); + T (f2 (178), 6, { 5, 12, 17, 19, 8, 19 }); + T (f2 (231), 6, { 5, 12, 17, 19, 8, 19 }); + T (f3 (-31), 2, { -31, -5 }); + T (f3 (169), 2, { 169, -5 }); + T (f3 (170), 2, { 27, -5 }); + T (f3 (171), 2, { 8, -5 }); + T (f3 (172), 2, { 21, -5 }); + T (f3 (173), 2, { 18, -5 }); + T (f3 (174), 2, { 139, -5 }); + T (f3 (175), 2, { 14, -5 }); + T (f3 (176), 2, { -14, -5 }); + T (f3 (177), 2, { 12, -5 }); + T (f3 (178), 2, { 178, -5 }); + T (f3 (231), 2, { 231, -5 }); + T (f4 (171, 1), 8, { 0, 0, 5, 12, 17, 19, 8, 45 }); + T (f4 (140, 1), 8, { 0, 0, 5, 12, 17, 19, 8, 45 }); + T (f4 (-31, 0), 6, { 5, 12, 17, 19, 8, 24 }); + T (f4 (169, 0), 6, { 5, 12, 17, 19, 8, 24 }); + T (f4 (170, 0), 2, { 27, 12 }); + T (f4 (171, 0), 2, { 8, 127 }); + T (f4 (172, 0), 2, { 21, -14 }); + T (f4 (173, 0), 2, { 18, 22 }); + T (f4 (174, 0), 2, { 139, 0 }); + T (f4 (175, 0), 2, { 14, -21 }); + T (f4 (176, 0), 2, { -14, 10 }); + T (f4 (177, 0), 2, { 12, 13 }); + T (f4 (178, 0), 6, { 5, 12, 17, 19, 8, 24 }); + T (f4 (231, 0), 6, { 5, 12, 17, 19, 8, 24 }); + T (f5 (171, 1), 4, { 23, 0, 129, 0 }); + T (f5 (140, 1), 4, { 23, 0, 129, 0 }); + T (f5 (-31, 0), 2, { 80, 0 }); + T (f5 (169, 0), 2, { 80, 0 }); + T (f5 (170, 0), 2, { 27, 0 }); + T (f5 (171, 0), 2, { 8, 0 }); + T (f5 (172, 0), 2, { 21, 0 }); + T (f5 (173, 0), 2, { 18, 0 }); + T (f5 (174, 0), 2, { 139, 0 }); + T (f5 (175, 0), 2, { 14, 0 }); + T (f5 (176, 0), 2, { -14, 0 }); + T (f5 (177, 0), 2, { 12, 0 }); + T (f5 (178, 0), 2, { 80, 0 }); + T (f5 (231, 0), 2, { 80, 0 }); +} + +/* { dg-final { scan-tree-dump-times "Switch converted" 5 "switchconv" } } */ +/* { dg-final { scan-tree-dump-times "= CSWTCH" 8 "switchconv" } } */ --- gcc/testsuite/gcc.dg/tree-ssa/cswtch-4.c.jj 2017-02-14 15:46:55.003417386 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/cswtch-4.c 2017-02-14 15:46:55.003417386 +0100 @@ -0,0 +1,57 @@ +/* PR tree-optimization/79472 */ +/* { dg-options "-O2 -fdump-tree-switchconv" } */ +/* { dg-do compile } */ + +void +frobulate (unsigned int v) +{ + const char *s; + + switch (v) + { + case 0: + s = "foo"; + break; + case 1: + s = "bar"; + break; + case 2: + s = "spam"; + break; + default: + __builtin_abort (); + break; + } + + __builtin_printf ("%s\n", s); +} + +void +frobulate_for_gcc (unsigned int v) +{ + const char *s; + + switch (v) + { + case 0: + s = "foo"; + break; + case 1: + s = "bar"; + break; + case 2: + s = "spam"; + break; + default: + s = (const char *) 0; + break; + } + + if (!s) + __builtin_abort (); + + __builtin_printf ("%s\n", s); +} + +/* { dg-final { scan-tree-dump-times "Switch converted" 2 "switchconv" } } */ +/* { dg-final { scan-tree-dump-times "= CSWTCH" 2 "switchconv" } } */ --- gcc/testsuite/gcc.dg/tree-ssa/cswtch-5.c.jj 2017-02-14 17:11:40.802710606 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/cswtch-5.c 2017-02-14 17:13:59.424872889 +0100 @@ -0,0 +1,66 @@ +/* PR tree-optimization/79472 */ +/* { dg-options "-O2 -fdump-tree-switchconv" } */ +/* { dg-do compile } */ + +void +foo (unsigned int v) +{ + const char *s; + + switch (v) + { + case 0: + s = "foo"; + break; + case 1: + s = "bar"; + break; + case 2: + s = "spam"; + break; + default: + for (int i = 0; i < v; i++) + __builtin_printf ("baz\n"); + return; + } + + __builtin_printf ("%s\n", s); +} + +int +bar (unsigned int v, int w) +{ + const char *s; + + switch (v) + { + case 0: + s = "foo"; + break; + case 1: + s = "bar"; + break; + case 2: + s = "spam"; + break; + default: + __builtin_printf ("baz\n"); + if (v > 25) + __builtin_printf ("bl1\n"); + else + __builtin_printf ("bl2\n"); + goto lab; + } + + __builtin_printf ("%s\n", s); + if (w > 25) + __builtin_printf ("cl1\n"); + else + __builtin_printf ("cl2\n"); + lab: + __builtin_printf ("dl\n"); + return v + w; +} + +/* { dg-final { scan-tree-dump-times "Switch converted" 2 "switchconv" } } */ +/* { dg-final { scan-tree-dump-times "= CSWTCH" 2 "switchconv" } } */