1 /* Switch Conversion converts variable initializations based on switch
2 statements to initializations from a static array.
3 Copyright (C) 2006, 2008 Free Software Foundation, Inc.
4 Contributed by Martin Jambor <jamborm@suse.cz>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 3, or (at your option) any
13 GCC is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 Switch initialization conversion
26 The following pass changes simple initializations of scalars in a switch
27 statement into initializations from a static array. Obviously, the values must
28 be constant and known at compile time and a default branch must be
29 provided. For example, the following code:
52 a_5 = PHI <a_1, a_2, a_3, a_4>
53 b_5 = PHI <b_1, b_2, b_3, b_4>
58 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
59 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
62 if (((unsigned) argc) - 1 < 11)
64 a_6 = CSWTCH02[argc - 1];
65 b_6 = CSWTCH01[argc - 1];
75 There are further constraints. Specifically, the range of values across all
76 case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
77 eight) times the number of the actual switch branches. */
81 #include "coretypes.h"
89 #include "basic-block.h"
90 #include "tree-flow.h"
91 #include "tree-flow-inline.h"
92 #include "tree-ssa-operands.h"
95 #include "tree-pass.h"
96 #include "diagnostic.h"
97 #include "tree-dump.h"
100 /* The main structure of the pass. */
101 struct switch_conv_info
103 /* The expression used to decide the switch branch. (It is subsequently used
104 as the index to the created array.) */
107 /* The following integer constants store the minimum value covered by the
111 /* The difference between the above two numbers, i.e. The size of the array
112 that would have to be created by the transformation. */
115 /* Basic block that contains the actual SWITCH_EXPR. */
116 basic_block switch_bb;
118 /* All branches of the switch statement must have a single successor stored in
119 the following variable. */
120 basic_block final_bb;
122 /* Number of phi nodes in the final bb (that we'll be replacing). */
125 /* Array of default values, in the same order as phi nodes. */
126 tree *default_values;
128 /* Constructors of new static arrays. */
129 VEC (constructor_elt, gc) **constructors;
131 /* Array of ssa names that are initialized with a value from a new static
133 tree *target_inbound_names;
135 /* Array of ssa names that are initialized with the default value if the
136 switch expression is out of range. */
137 tree *target_outbound_names;
139 /* The probability of the default edge in the replaced switch. */
142 /* The count of the default edge in the replaced switch. */
143 gcov_type default_count;
145 /* Combined count of all other (non-default) edges in the replaced switch. */
146 gcov_type other_count;
148 /* The first load statement that loads a temporary from a new static array.
152 /* The last load statement that loads a temporary from a new static array. */
155 /* String reason why the case wasn't a good candidate that is written to the
156 dump file, if there is one. */
160 /* Global pass info. */
161 static struct switch_conv_info info;
164 /* Checks whether the range given by individual case statements of the SWTCH
165 switch statement isn't too big and whether the number of branches actually
166 satisfies the size of the new array. */
169 check_range (tree swtch)
171 tree min_case, max_case;
172 tree cases = SWITCH_LABELS (swtch);
173 unsigned int branch_num = TREE_VEC_LENGTH (cases);
176 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
177 is a default label which is the last in the vector. */
179 min_case = TREE_VEC_ELT (cases, 0);
180 info.range_min = CASE_LOW (min_case);
182 gcc_assert (branch_num > 1);
183 gcc_assert (CASE_LOW (TREE_VEC_ELT (cases, branch_num - 1)) == NULL_TREE);
184 max_case = TREE_VEC_ELT (cases, branch_num - 2);
185 if (CASE_HIGH (max_case) != NULL_TREE)
186 range_max = CASE_HIGH (max_case);
188 range_max = CASE_LOW (max_case);
190 gcc_assert (info.range_min);
191 gcc_assert (range_max);
193 info.range_size = int_const_binop (MINUS_EXPR, range_max, info.range_min, 0);
195 gcc_assert (info.range_size);
196 if (!host_integerp (info.range_size, 1))
198 info.reason = "index range way too large or otherwise unusable.\n";
202 if ((unsigned HOST_WIDE_INT) tree_low_cst (info.range_size, 1)
203 > ((unsigned) branch_num * SWITCH_CONVERSION_BRANCH_RATIO))
205 info.reason = "the maximum range-branch ratio exceeded.\n";
212 /* Checks the given CS switch case whether it is suitable for conversion
213 (whether all but the default basic blocks are empty and so on). If it is,
214 adds the case to the branch list along with values for the defined variables
215 and returns true. Otherwise returns false. */
218 check_process_case (tree cs)
221 basic_block label_bb, following_bb;
224 ldecl = CASE_LABEL (cs);
225 label_bb = label_to_block (ldecl);
227 e = find_edge (info.switch_bb, label_bb);
230 if (CASE_LOW (cs) == NULL_TREE)
232 /* Default branch. */
233 info.default_prob = e->probability;
234 info.default_count = e->count;
237 info.other_count += e->count;
241 info.reason = " Bad case - cs BB label is NULL\n";
245 if (!single_pred_p (label_bb))
247 if (info.final_bb && info.final_bb != label_bb)
249 info.reason = " Bad case - a non-final BB has two predecessors\n";
250 return false; /* sth complex going on in this branch */
253 following_bb = label_bb;
257 if (!empty_block_p (label_bb))
259 info.reason = " Bad case - a non-final BB not empty\n";
263 e = single_succ_edge (label_bb);
264 following_bb = single_succ (label_bb);
268 info.final_bb = following_bb;
269 else if (info.final_bb != following_bb)
271 info.reason = " Bad case - different final BB\n";
272 return false; /* the only successor is not common for all the branches */
278 /* This function checks whether all required values in phi nodes in final_bb
279 are constants. Required values are those that correspond to a basic block
280 which is a part of the examined switch statement. It returns true if the
281 phi nodes are OK, otherwise false. */
284 check_final_bb (void)
289 for (phi = phi_nodes (info.final_bb); phi; phi = PHI_CHAIN (phi))
295 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
297 basic_block bb = PHI_ARG_EDGE (phi, i)->src;
299 if ((bb == info.switch_bb
300 || (single_pred_p (bb) && single_pred (bb) == info.switch_bb))
301 && !is_gimple_min_invariant (PHI_ARG_ELT (phi, i).def))
303 info.reason = " Non-invariant value from a case\n";
304 return false; /* non invariant argument */
312 /* The following function allocates default_values, target_{in,out}_names and
313 constructors arrays. The last one is also populated with pointers to
314 vectors that will become constructors of new arrays. */
317 create_temp_arrays (void)
321 info.default_values = (tree *) xcalloc (info.phi_count, sizeof (tree));
322 info.constructors = (VEC (constructor_elt, gc) **) xcalloc (info.phi_count,
324 info.target_inbound_names = (tree *) xcalloc (info.phi_count, sizeof (tree));
325 info.target_outbound_names = (tree *) xcalloc (info.phi_count,
328 for (i = 0; i < info.phi_count; i++)
330 info.constructors[i] = VEC_alloc (constructor_elt, gc,
331 tree_low_cst (info.range_size, 1) + 1);
335 /* Free the arrays created by create_temp_arrays(). The vectors that are
336 created by that function are not freed here, however, because they have
337 already become constructors and must be preserved. */
340 free_temp_arrays (void)
342 free (info.constructors);
343 free (info.default_values);
344 free (info.target_inbound_names);
345 free (info.target_outbound_names);
348 /* Populate the array of default values in the order of phi nodes.
349 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */
352 gather_default_values (tree default_case)
355 basic_block bb = label_to_block (CASE_LABEL (default_case));
359 gcc_assert (CASE_LOW (default_case) == NULL_TREE);
361 if (bb == info.final_bb)
362 e = find_edge (info.switch_bb, bb);
364 e = single_succ_edge (bb);
366 for (phi = phi_nodes (info.final_bb), i = 0; phi; phi = PHI_CHAIN (phi), i++)
368 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
370 info.default_values[i] = val;
374 /* The following function populates the vectors in the constructors array with
375 future contents of the static arrays. The vectors are populated in the
376 order of phi nodes. SWTCH is the switch statement being converted. */
379 build_constructors (tree swtch)
382 tree cases = SWITCH_LABELS (swtch);
383 tree pos = info.range_min;
385 for (i = 0; i < TREE_VEC_LENGTH (cases) - 1; i++)
387 tree cs = TREE_VEC_ELT (cases, i);
388 basic_block bb = label_to_block (CASE_LABEL (cs));
393 if (bb == info.final_bb)
394 e = find_edge (info.switch_bb, bb);
396 e = single_succ_edge (bb);
399 while (tree_int_cst_lt (pos, CASE_LOW (cs)))
402 for (k = 0; k < info.phi_count; k++)
404 constructor_elt *elt;
406 elt = VEC_quick_push (constructor_elt,
407 info.constructors[k], NULL);
408 elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min, 0);
409 elt->value = info.default_values[k];
412 pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
414 gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
418 high = CASE_HIGH (cs);
420 high = CASE_LOW (cs);
421 for (phi = phi_nodes (info.final_bb); phi; phi = PHI_CHAIN (phi))
423 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
426 while (!tree_int_cst_lt (high, pos))
428 constructor_elt *elt;
430 elt = VEC_quick_push (constructor_elt,
431 info.constructors[j], NULL);
432 elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min, 0);
435 pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
442 /* Create an appropriate array type and declaration and assemble a static array
443 variable. Also create a load statement that initializes the variable in
444 question with a value from the static array. SWTCH is the switch statement
445 being converted, NUM is the index to arrays of constructors, default values
446 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
447 of the index of the new array, PHI is the phi node of the final BB that
448 corresponds to the value that will be loaded from the created array. TIDX
449 is a temporary variable holding the index for loads from the new array. */
452 build_one_array (tree swtch, int num, tree arr_index_type, tree phi, tree tidx)
460 block_stmt_iterator bsi;
462 gcc_assert (info.default_values[num]);
463 value_type = TREE_TYPE (info.default_values[num]);
464 array_type = build_array_type (value_type, arr_index_type);
466 ctor = build_constructor (array_type, info.constructors[num]);
467 TREE_CONSTANT (ctor) = true;
469 decl = build_decl (VAR_DECL, NULL_TREE, array_type);
470 TREE_STATIC (decl) = 1;
471 DECL_INITIAL (decl) = ctor;
473 DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
474 DECL_ARTIFICIAL (decl) = 1;
475 TREE_CONSTANT (decl) = 1;
476 add_referenced_var (decl);
477 assemble_variable (decl, 0, 0, 0);
478 mark_sym_for_renaming (decl);
480 name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL_TREE);
481 info.target_inbound_names[num] = name;
483 fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
485 load = build2 (GIMPLE_MODIFY_STMT, void_type_node, name, fetch);
486 SSA_NAME_DEF_STMT (name) = load;
488 bsi = bsi_for_stmt (swtch);
489 bsi_insert_before (&bsi, load, BSI_SAME_STMT);
490 mark_symbols_for_renaming (load);
492 info.arr_ref_last = load;
497 /* Builds and initializes static arrays initialized with values gathered from
498 the SWTCH switch statement. Also creates statements that load values from
502 build_arrays (tree swtch)
506 block_stmt_iterator bsi;
507 tree phi = phi_nodes (info.final_bb);
510 arr_index_type = build_index_type (info.range_size);
511 tidx = make_rename_temp (arr_index_type, "csti");
512 sub = build2 (MINUS_EXPR, TREE_TYPE (info.index_expr), info.index_expr,
513 fold_convert (TREE_TYPE (info.index_expr), info.range_min));
514 sub = build2 (GIMPLE_MODIFY_STMT, void_type_node, tidx, sub);
516 bsi = bsi_for_stmt (swtch);
517 bsi_insert_before (&bsi, sub, BSI_SAME_STMT);
518 mark_symbols_for_renaming (sub);
519 info.arr_ref_first = sub;
521 for (phi = phi_nodes (info.final_bb), i = 0; phi; phi = PHI_CHAIN (phi), i++)
522 build_one_array (swtch, i, arr_index_type, phi, tidx);
527 /* Generates and appropriately inserts loads of default values at the position
528 given by BSI. Returns the last inserted statement. */
531 gen_def_assigns (block_stmt_iterator *bsi)
534 tree assign = NULL_TREE;
536 for (i = 0; i < info.phi_count; i++)
538 tree name = make_ssa_name (SSA_NAME_VAR (info.target_inbound_names[i]),
541 info.target_outbound_names[i] = name;
542 assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, name,
543 info.default_values[i]);
544 SSA_NAME_DEF_STMT (name) = assign;
545 bsi_insert_before (bsi, assign, BSI_SAME_STMT);
546 find_new_referenced_vars (&assign);
547 mark_symbols_for_renaming (assign);
552 /* Deletes the unused bbs and edges that now contain the switch statement and
553 its empty branch bbs. BBD is the now dead BB containing the original switch
554 statement, FINAL is the last BB of the converted switch statement (in terms
558 prune_bbs (basic_block bbd, basic_block final)
563 for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
569 delete_basic_block (bb);
571 delete_basic_block (bbd);
574 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
575 from the basic block loading values from an array and E2F from the basic
576 block loading default values. BBF is the last switch basic block (see the
577 bbf description in the comment below). */
580 fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
585 for (phi = phi_nodes (bbf), i = 0; phi; phi = PHI_CHAIN (phi), i++)
587 add_phi_arg (phi, info.target_inbound_names[i], e1f);
588 add_phi_arg (phi, info.target_outbound_names[i], e2f);
593 /* Creates a check whether the switch expression value actually falls into the
594 range given by all the cases. If it does not, the temporaries are loaded
595 with default values instead. SWTCH is the switch statement being converted.
597 bb0 is the bb with the switch statement, however, we'll end it with a
600 bb1 is the bb to be used when the range check went ok. It is derived from
603 bb2 is the bb taken when the expression evaluated outside of the range
604 covered by the created arrays. It is populated by loads of default
607 bbF is a fall through for both bb1 and bb2 and contains exactly what
608 originally followed the switch statement.
610 bbD contains the switch statement (in the end). It is unreachable but we
611 still need to strip off its edges.
615 gen_inbound_check (tree swtch)
617 tree label_decl1 = create_artificial_label ();
618 tree label_decl2 = create_artificial_label ();
619 tree label_decl3 = create_artificial_label ();
620 tree label1, label2, label3;
622 tree utype = unsigned_type_for (TREE_TYPE (info.index_expr));
624 tree cast, cast_assign;
625 tree ulb, minus, minus_assign;
631 block_stmt_iterator bsi;
632 basic_block bb0, bb1, bb2, bbf, bbd;
633 edge e01, e02, e21, e1d, e1f, e2f;
635 gcc_assert (info.default_values);
636 bb0 = bb_for_stmt (swtch);
638 /* (end of) block 0 */
639 bsi = bsi_for_stmt (info.arr_ref_first);
640 tmp_u = make_rename_temp (utype, "csui");
642 cast = build1 (NOP_EXPR, utype, info.index_expr);
643 cast_assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, tmp_u, cast);
644 find_new_referenced_vars (&cast_assign);
645 bsi_insert_before (&bsi, cast_assign, BSI_SAME_STMT);
646 mark_symbols_for_renaming (cast_assign);
648 ulb = fold_convert (utype, info.range_min);
649 minus = build2 (MINUS_EXPR, utype, tmp_u, ulb);
650 minus_assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, tmp_u, minus);
651 find_new_referenced_vars (&minus_assign);
652 bsi_insert_before (&bsi, minus_assign, BSI_SAME_STMT);
653 mark_symbols_for_renaming (minus_assign);
655 bound = fold_convert (utype, info.range_size);
657 if_expr = build3 (COND_EXPR, void_type_node,
658 build2 (LE_EXPR, boolean_type_node, tmp_u, bound),
659 NULL_TREE, NULL_TREE);
661 find_new_referenced_vars (&if_expr);
662 bsi_insert_before (&bsi, if_expr, BSI_SAME_STMT);
663 mark_symbols_for_renaming (if_expr);
666 bsi = bsi_for_stmt (info.arr_ref_first);
667 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
668 bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
669 last_assign = gen_def_assigns (&bsi);
672 bsi = bsi_for_stmt (info.arr_ref_first);
673 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
674 bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
677 bsi = bsi_start (info.final_bb);
678 label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
679 bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
682 e02 = split_block (bb0, if_expr);
685 e21 = split_block (bb2, last_assign);
689 e1d = split_block (bb1, info.arr_ref_last);
693 /* flags and profiles of the edge for in-range values */
694 e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
695 e01->probability = REG_BR_PROB_BASE - info.default_prob;
696 e01->count = info.other_count;
698 /* flags and profiles of the edge taking care of out-of-range values */
699 e02->flags &= ~EDGE_FALLTHRU;
700 e02->flags |= EDGE_FALSE_VALUE;
701 e02->probability = info.default_prob;
702 e02->count = info.default_count;
706 e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
707 e1f->probability = REG_BR_PROB_BASE;
708 e1f->count = info.other_count;
710 e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
711 e2f->probability = REG_BR_PROB_BASE;
712 e2f->count = info.default_count;
714 /* frequencies of the new BBs */
715 bb1->frequency = EDGE_FREQUENCY (e01);
716 bb2->frequency = EDGE_FREQUENCY (e02);
717 bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
719 prune_bbs (bbd, info.final_bb); /* to keep calc_dfs_tree() in dominance.c
722 fix_phi_nodes (e1f, e2f, bbf);
724 free_dominance_info (CDI_DOMINATORS);
725 free_dominance_info (CDI_POST_DOMINATORS);
728 /* The following function is invoked on every switch statement (the current one
729 is given in SWTCH) and runs the individual phases of switch conversion on it
730 one after another until one fails or the conversion is completed. */
733 process_switch (tree swtch)
739 /* Operand 2 is either NULL_TREE or a vector of cases (stmt.c). */
740 if (TREE_OPERAND (swtch, 2) == NULL_TREE)
742 info.reason = "swtch has no labels\n";
746 /* Comment from stmt.c:
747 The switch body is lowered in gimplify.c, we should never have switches
748 with a non-NULL SWITCH_BODY here. */
749 gcc_assert (!SWITCH_BODY (swtch));
751 cases = SWITCH_LABELS (swtch);
752 info.final_bb = NULL;
753 info.switch_bb = bb_for_stmt (swtch);
754 info.index_expr = SWITCH_COND (swtch);
755 index_type = TREE_TYPE (info.index_expr);
756 info.arr_ref_first = NULL_TREE;
757 info.arr_ref_last = NULL_TREE;
758 info.default_prob = 0;
759 info.default_count = 0;
760 info.other_count = 0;
762 /* An ERROR_MARK occurs for various reasons including invalid data type.
763 (comment from stmt.c) */
764 if (index_type == error_mark_node)
766 info.reason = "index error.\n";
770 /* Check the case label values are within reasonable range: */
771 if (!check_range (swtch))
774 /* For all the cases, see whether they are empty, the assignments they
775 represent constant and so on... */
776 for (i = 0; i < TREE_VEC_LENGTH (cases); i++)
778 tree part_case = TREE_VEC_ELT (cases, i);
779 if (!check_process_case (part_case))
782 fprintf (dump_file, "Processing of case %i failed\n", i);
787 if (!check_final_bb ())
790 /* At this point all checks have passed and we can proceed with the
793 create_temp_arrays ();
794 gather_default_values (TREE_VEC_ELT (cases, TREE_VEC_LENGTH (cases) - 1));
795 build_constructors (swtch);
797 build_arrays (swtch); /* Build the static arrays and assignments. */
798 gen_inbound_check (swtch); /* Build the bounds check. */
805 /* The main function of the pass scans statements for switches and invokes
806 process_switch on them. */
815 tree stmt = last_stmt (bb);
816 if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
818 expanded_location loc = expand_location (EXPR_LOCATION (stmt));
822 fprintf (dump_file, "beginning to process the following "
823 "SWITCH statement (%s:%d) : ------- \n",
825 print_generic_stmt (dump_file, stmt, 2);
826 fprintf (dump_file, "\n");
830 if (process_switch (stmt))
834 fprintf (dump_file, "Switch converted\n");
835 fprintf (dump_file, "--------------------------------\n");
842 gcc_assert (info.reason);
843 fprintf (dump_file, "Bailing out - ");
844 fprintf (dump_file, info.reason);
845 fprintf (dump_file, "--------------------------------\n");
857 switchconv_gate (void)
859 return flag_tree_switch_conversion != 0;
862 struct gimple_opt_pass pass_convert_switch =
866 "switchconv", /* name */
867 switchconv_gate, /* gate */
868 do_switchconv, /* execute */
871 0, /* static_pass_number */
872 TV_TREE_SWITCH_CONVERSION, /* tv_id */
873 PROP_cfg | PROP_ssa, /* properties_required */
874 0, /* properties_provided */
875 0, /* properties_destroyed */
876 0, /* todo_flags_start */
877 TODO_update_ssa | TODO_dump_func
878 | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */