+ bbf = m_final_bb;
+
+ e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
+ e1f->probability = profile_probability::always ();
+
+ if (m_default_case_nonstandard)
+ e2f = NULL;
+ else
+ {
+ e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
+ e2f->probability = profile_probability::always ();
+ }
+
+ /* frequencies of the new BBs */
+ bb1->count = e01->count ();
+ bb2->count = e02->count ();
+ if (!m_default_case_nonstandard)
+ bbf->count = e1f->count () + e2f->count ();
+
+ /* Tidy blocks that have become unreachable. */
+ prune_bbs (bbd, m_final_bb,
+ m_default_case_nonstandard ? m_default_bb : NULL);
+
+ /* Fixup the PHI nodes in bbF. */
+ fix_phi_nodes (e1f, e2f, bbf);
+
+ /* Fix the dominator tree, if it is available. */
+ if (dom_info_available_p (CDI_DOMINATORS))
+ {
+ vec<basic_block> bbs_to_fix_dom;
+
+ set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
+ if (!m_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 (3 + (bb2 != bbf));
+ bbs_to_fix_dom.quick_push (bb0);
+ bbs_to_fix_dom.quick_push (bb1);
+ 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);
+ bbs_to_fix_dom.release ();
+ }
+}
+
+/* The following function is invoked on every switch statement (the current
+ one is given in SWTCH) and runs the individual phases of switch
+ conversion on it one after another until one fails or the conversion
+ is completed. On success, NULL is in m_reason, otherwise points
+ to a string with the reason why the conversion failed. */
+
+void
+switch_conversion::expand (gswitch *swtch)
+{
+ /* Group case labels so that we get the right results from the heuristics
+ that decide on the code generation approach for this switch. */
+ m_cfg_altered |= group_case_labels_stmt (swtch);
+
+ /* If this switch is now a degenerate case with only a default label,
+ there is nothing left for us to do. */
+ if (gimple_switch_num_labels (swtch) < 2)
+ {
+ m_reason = "switch is a degenerate case";
+ return;
+ }
+
+ collect (swtch);
+
+ /* No error markers should reach here (they should be filtered out
+ during gimplification). */
+ gcc_checking_assert (TREE_TYPE (m_index_expr) != error_mark_node);
+
+ /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
+ gcc_checking_assert (!TREE_CONSTANT (m_index_expr));
+
+ /* Prefer bit test if possible. */
+ if (tree_fits_uhwi_p (m_range_size)
+ && bit_test_cluster::can_be_handled (tree_to_uhwi (m_range_size), m_uniq)
+ && bit_test_cluster::is_beneficial (m_count, m_uniq))
+ {
+ m_reason = "expanding as bit test is preferable";
+ return;
+ }
+
+ if (m_uniq <= 2)
+ {
+ /* This will be expanded as a decision tree . */
+ m_reason = "expanding as jumps is preferable";
+ return;
+ }
+
+ /* If there is no common successor, we cannot do the transformation. */
+ if (!m_final_bb)
+ {
+ m_reason = "no common successor to all case label target blocks found";
+ return;
+ }
+
+ /* Check the case label values are within reasonable range: */
+ if (!check_range ())
+ {
+ gcc_assert (m_reason);
+ return;
+ }
+
+ /* For all the cases, see whether they are empty, the assignments they
+ represent constant and so on... */
+ if (!check_all_empty_except_final ())
+ {
+ gcc_assert (m_reason);
+ return;
+ }
+ if (!check_final_bb ())
+ {
+ gcc_assert (m_reason);
+ return;
+ }
+
+ /* At this point all checks have passed and we can proceed with the
+ transformation. */
+
+ create_temp_arrays ();
+ gather_default_values (m_default_case_nonstandard
+ ? gimple_switch_label (swtch, 1)
+ : gimple_switch_default_label (swtch));
+ build_constructors ();
+
+ build_arrays (); /* Build the static arrays and assignments. */
+ gen_inbound_check (); /* Build the bounds check. */
+
+ m_cfg_altered = true;
+}
+
+/* Destructor. */
+
+switch_conversion::~switch_conversion ()
+{
+ XDELETEVEC (m_constructors);
+ XDELETEVEC (m_default_values);
+}
+
+/* Constructor. */
+
+group_cluster::group_cluster (vec<cluster *> &clusters,
+ unsigned start, unsigned end)
+{
+ gcc_checking_assert (end - start + 1 >= 1);
+ m_prob = profile_probability::never ();
+ m_cases.create (end - start + 1);
+ for (unsigned i = start; i <= end; i++)
+ {
+ m_cases.quick_push (static_cast<simple_cluster *> (clusters[i]));
+ m_prob += clusters[i]->m_prob;
+ }
+ m_subtree_prob = m_prob;
+}
+
+/* Destructor. */
+
+group_cluster::~group_cluster ()
+{
+ for (unsigned i = 0; i < m_cases.length (); i++)
+ delete m_cases[i];
+
+ m_cases.release ();
+}
+
+/* Dump content of a cluster. */
+
+void
+group_cluster::dump (FILE *f, bool details)
+{
+ unsigned total_values = 0;
+ for (unsigned i = 0; i < m_cases.length (); i++)
+ total_values += m_cases[i]->get_range (m_cases[i]->get_low (),
+ m_cases[i]->get_high ());
+
+ unsigned comparison_count = 0;
+ for (unsigned i = 0; i < m_cases.length (); i++)
+ {
+ simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
+ comparison_count += sc->m_range_p ? 2 : 1;
+ }
+
+ unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ());
+ fprintf (f, "%s", get_type () == JUMP_TABLE ? "JT" : "BT");
+
+ if (details)
+ fprintf (f, "(values:%d comparisons:%d range:" HOST_WIDE_INT_PRINT_DEC
+ " density: %.2f%%)", total_values, comparison_count, range,
+ 100.0f * comparison_count / range);
+
+ fprintf (f, ":");
+ PRINT_CASE (f, get_low ());
+ fprintf (f, "-");
+ PRINT_CASE (f, get_high ());
+ fprintf (f, " ");
+}
+
+/* Emit GIMPLE code to handle the cluster. */
+
+void
+jump_table_cluster::emit (tree index_expr, tree,
+ tree default_label_expr, basic_block default_bb)
+{
+ unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ());
+ unsigned HOST_WIDE_INT nondefault_range = 0;
+
+ /* For jump table we just emit a new gswitch statement that will
+ be latter lowered to jump table. */
+ auto_vec <tree> labels;
+ labels.create (m_cases.length ());
+
+ make_edge (m_case_bb, default_bb, 0);
+ for (unsigned i = 0; i < m_cases.length (); i++)
+ {
+ labels.quick_push (unshare_expr (m_cases[i]->m_case_label_expr));
+ make_edge (m_case_bb, m_cases[i]->m_case_bb, 0);
+ }
+
+ gswitch *s = gimple_build_switch (index_expr,
+ unshare_expr (default_label_expr), labels);
+ gimple_stmt_iterator gsi = gsi_start_bb (m_case_bb);
+ gsi_insert_after (&gsi, s, GSI_NEW_STMT);
+
+ /* Set up even probabilities for all cases. */
+ for (unsigned i = 0; i < m_cases.length (); i++)
+ {
+ simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
+ edge case_edge = find_edge (m_case_bb, sc->m_case_bb);
+ unsigned HOST_WIDE_INT case_range
+ = sc->get_range (sc->get_low (), sc->get_high ());
+ nondefault_range += case_range;
+
+ /* case_edge->aux is number of values in a jump-table that are covered
+ by the case_edge. */
+ case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + case_range);
+ }
+
+ edge default_edge = gimple_switch_default_edge (cfun, s);
+ default_edge->probability = profile_probability::never ();
+
+ for (unsigned i = 0; i < m_cases.length (); i++)
+ {
+ simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
+ edge case_edge = find_edge (m_case_bb, sc->m_case_bb);
+ case_edge->probability
+ = profile_probability::always ().apply_scale ((intptr_t)case_edge->aux,
+ range);
+ }
+
+ /* Number of non-default values is probability of default edge. */
+ default_edge->probability
+ += profile_probability::always ().apply_scale (nondefault_range,
+ range).invert ();
+
+ switch_decision_tree::reset_out_edges_aux (s);
+}
+
+/* Find jump tables of given CLUSTERS, where all members of the vector
+ are of type simple_cluster. New clusters are returned. */
+
+vec<cluster *>
+jump_table_cluster::find_jump_tables (vec<cluster *> &clusters)
+{
+ if (!is_enabled ())
+ return clusters.copy ();
+
+ unsigned l = clusters.length ();
+ auto_vec<min_cluster_item> min;
+ min.reserve (l + 1);
+
+ min.quick_push (min_cluster_item (0, 0, 0));
+
+ for (unsigned i = 1; i <= l; i++)
+ {
+ /* Set minimal # of clusters with i-th item to infinite. */
+ min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
+
+ for (unsigned j = 0; j < i; j++)
+ {
+ unsigned HOST_WIDE_INT s = min[j].m_non_jt_cases;
+ if (i - j < case_values_threshold ())
+ s += i - j;
+
+ /* Prefer clusters with smaller number of numbers covered. */
+ if ((min[j].m_count + 1 < min[i].m_count
+ || (min[j].m_count + 1 == min[i].m_count
+ && s < min[i].m_non_jt_cases))
+ && can_be_handled (clusters, j, i - 1))
+ min[i] = min_cluster_item (min[j].m_count + 1, j, s);
+ }
+
+ gcc_checking_assert (min[i].m_count != INT_MAX);
+ }
+
+ /* No result. */
+ if (min[l].m_count == l)
+ return clusters.copy ();