| Message ID | 20170429163055.GR1809@tucnak |
|---|---|
| State | New |
| Headers | show |
On Sat, 29 Apr 2017, Jakub Jelinek wrote: > On Wed, Feb 15, 2017 at 12:51:30PM +0100, 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. > > If the tree-vrp.c change makes it in, is this patch ok for trunk too now > that we are in stage1? Bootstrapped/regtested on x86_64-linux and > i686-linux on top of the tree-vrp.c change (without the tree-vrp.c change > vrp40.c regresses). Ok. Thanks, Richard. > 2017-04-29 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 Tue, May 02, 2017 at 01:16:05PM +0200, Richard Biener wrote: > On Sat, 29 Apr 2017, Jakub Jelinek wrote: > > > On Wed, Feb 15, 2017 at 12:51:30PM +0100, 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. > > > > If the tree-vrp.c change makes it in, is this patch ok for trunk too now > > that we are in stage1? Bootstrapped/regtested on x86_64-linux and > > i686-linux on top of the tree-vrp.c change (without the tree-vrp.c change > > vrp40.c regresses). > > Ok. So with XFAILing vrp40.c for now until the constant load opt is resolved? Jakub
On Tue, 2 May 2017, Jakub Jelinek wrote: > On Tue, May 02, 2017 at 01:16:05PM +0200, Richard Biener wrote: > > On Sat, 29 Apr 2017, Jakub Jelinek wrote: > > > > > On Wed, Feb 15, 2017 at 12:51:30PM +0100, 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. > > > > > > If the tree-vrp.c change makes it in, is this patch ok for trunk too now > > > that we are in stage1? Bootstrapped/regtested on x86_64-linux and > > > i686-linux on top of the tree-vrp.c change (without the tree-vrp.c change > > > vrp40.c regresses). > > > > Ok. > > So with XFAILing vrp40.c for now until the constant load opt is resolved? Yes. Maybe instead add vrp40-2.c XFAILed and leave vrp40.c with switchconv disabled? Richard.
--- 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" } } */