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"
99 #include "langhooks.h"
101 /* The main structure of the pass. */
102 struct switch_conv_info
104 /* The expression used to decide the switch branch. (It is subsequently used
105 as the index to the created array.) */
108 /* The following integer constants store the minimum value covered by the
112 /* The difference between the above two numbers, i.e. The size of the array
113 that would have to be created by the transformation. */
116 /* Basic block that contains the actual SWITCH_EXPR. */
117 basic_block switch_bb;
119 /* All branches of the switch statement must have a single successor stored in
120 the following variable. */
121 basic_block final_bb;
123 /* Number of phi nodes in the final bb (that we'll be replacing). */
126 /* Array of default values, in the same order as phi nodes. */
127 tree *default_values;
129 /* Constructors of new static arrays. */
130 VEC (constructor_elt, gc) **constructors;
132 /* Array of ssa names that are initialized with a value from a new static
134 tree *target_inbound_names;
136 /* Array of ssa names that are initialized with the default value if the
137 switch expression is out of range. */
138 tree *target_outbound_names;
140 /* The probability of the default edge in the replaced switch. */
143 /* The count of the default edge in the replaced switch. */
144 gcov_type default_count;
146 /* Combined count of all other (non-default) edges in the replaced switch. */
147 gcov_type other_count;
149 /* The first load statement that loads a temporary from a new static array.
151 gimple arr_ref_first;
153 /* The last load statement that loads a temporary from a new static array. */
156 /* String reason why the case wasn't a good candidate that is written to the
157 dump file, if there is one. */
161 /* Global pass info. */
162 static struct switch_conv_info info;
165 /* Checks whether the range given by individual case statements of the SWTCH
166 switch statement isn't too big and whether the number of branches actually
167 satisfies the size of the new array. */
170 check_range (gimple swtch)
172 tree min_case, max_case;
173 unsigned int branch_num = gimple_switch_num_labels (swtch);
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 = gimple_switch_label (swtch, 1);
180 info.range_min = CASE_LOW (min_case);
182 gcc_assert (branch_num > 1);
183 gcc_assert (CASE_LOW (gimple_switch_label (swtch, 0)) == NULL_TREE);
184 max_case = gimple_switch_label (swtch, branch_num - 1);
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)
286 gimple_stmt_iterator gsi;
289 for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
291 gimple phi = gsi_stmt (gsi);
296 for (i = 0; i < gimple_phi_num_args (phi); i++)
298 basic_block bb = gimple_phi_arg_edge (phi, i)->src;
300 if (bb == info.switch_bb
301 || (single_pred_p (bb) && single_pred (bb) == info.switch_bb))
305 val = gimple_phi_arg_def (phi, i);
306 if (!is_gimple_ip_invariant (val))
308 info.reason = " Non-invariant value from a case\n";
309 return false; /* Non-invariant argument. */
311 reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
312 if ((flag_pic && reloc != null_pointer_node)
313 || (!flag_pic && reloc == NULL_TREE))
317 = " Value from a case would need runtime relocations\n";
320 = " Value from a case is not a valid initializer\n";
330 /* The following function allocates default_values, target_{in,out}_names and
331 constructors arrays. The last one is also populated with pointers to
332 vectors that will become constructors of new arrays. */
335 create_temp_arrays (void)
339 info.default_values = (tree *) xcalloc (info.phi_count, sizeof (tree));
340 info.constructors = (VEC (constructor_elt, gc) **) xcalloc (info.phi_count,
342 info.target_inbound_names = (tree *) xcalloc (info.phi_count, sizeof (tree));
343 info.target_outbound_names = (tree *) xcalloc (info.phi_count,
346 for (i = 0; i < info.phi_count; i++)
348 = VEC_alloc (constructor_elt, gc, tree_low_cst (info.range_size, 1) + 1);
351 /* Free the arrays created by create_temp_arrays(). The vectors that are
352 created by that function are not freed here, however, because they have
353 already become constructors and must be preserved. */
356 free_temp_arrays (void)
358 free (info.constructors);
359 free (info.default_values);
360 free (info.target_inbound_names);
361 free (info.target_outbound_names);
364 /* Populate the array of default values in the order of phi nodes.
365 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */
368 gather_default_values (tree default_case)
370 gimple_stmt_iterator gsi;
371 basic_block bb = label_to_block (CASE_LABEL (default_case));
375 gcc_assert (CASE_LOW (default_case) == NULL_TREE);
377 if (bb == info.final_bb)
378 e = find_edge (info.switch_bb, bb);
380 e = single_succ_edge (bb);
382 for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
384 gimple phi = gsi_stmt (gsi);
385 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
387 info.default_values[i++] = val;
391 /* The following function populates the vectors in the constructors array with
392 future contents of the static arrays. The vectors are populated in the
393 order of phi nodes. SWTCH is the switch statement being converted. */
396 build_constructors (gimple swtch)
398 unsigned i, branch_num = gimple_switch_num_labels (swtch);
399 tree pos = info.range_min;
401 for (i = 1; i < branch_num; i++)
403 tree cs = gimple_switch_label (swtch, i);
404 basic_block bb = label_to_block (CASE_LABEL (cs));
407 gimple_stmt_iterator gsi;
410 if (bb == info.final_bb)
411 e = find_edge (info.switch_bb, bb);
413 e = single_succ_edge (bb);
416 while (tree_int_cst_lt (pos, CASE_LOW (cs)))
419 for (k = 0; k < info.phi_count; k++)
421 constructor_elt *elt;
423 elt = VEC_quick_push (constructor_elt,
424 info.constructors[k], NULL);
425 elt->index = int_const_binop (MINUS_EXPR, pos,
427 elt->value = info.default_values[k];
430 pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
432 gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
436 high = CASE_HIGH (cs);
438 high = CASE_LOW (cs);
439 for (gsi = gsi_start_phis (info.final_bb);
440 !gsi_end_p (gsi); gsi_next (&gsi))
442 gimple phi = gsi_stmt (gsi);
443 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
444 tree low = CASE_LOW (cs);
449 constructor_elt *elt;
451 elt = VEC_quick_push (constructor_elt,
452 info.constructors[j], NULL);
453 elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min, 0);
456 pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
457 } while (!tree_int_cst_lt (high, pos) && tree_int_cst_lt (low, pos));
463 /* Create an appropriate array type and declaration and assemble a static array
464 variable. Also create a load statement that initializes the variable in
465 question with a value from the static array. SWTCH is the switch statement
466 being converted, NUM is the index to arrays of constructors, default values
467 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
468 of the index of the new array, PHI is the phi node of the final BB that
469 corresponds to the value that will be loaded from the created array. TIDX
470 is a temporary variable holding the index for loads from the new array. */
473 build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi,
476 tree array_type, ctor, decl, value_type, name, fetch;
478 gimple_stmt_iterator gsi;
480 gcc_assert (info.default_values[num]);
481 value_type = TREE_TYPE (info.default_values[num]);
482 array_type = build_array_type (value_type, arr_index_type);
484 ctor = build_constructor (array_type, info.constructors[num]);
485 TREE_CONSTANT (ctor) = true;
487 decl = build_decl (VAR_DECL, NULL_TREE, array_type);
488 TREE_STATIC (decl) = 1;
489 DECL_INITIAL (decl) = ctor;
491 DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
492 DECL_ARTIFICIAL (decl) = 1;
493 TREE_CONSTANT (decl) = 1;
494 add_referenced_var (decl);
495 varpool_mark_needed_node (varpool_node (decl));
496 varpool_finalize_decl (decl);
497 mark_sym_for_renaming (decl);
499 name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL);
500 info.target_inbound_names[num] = name;
502 fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
504 load = gimple_build_assign (name, fetch);
505 SSA_NAME_DEF_STMT (name) = load;
507 gsi = gsi_for_stmt (swtch);
508 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
509 mark_symbols_for_renaming (load);
511 info.arr_ref_last = load;
514 /* Builds and initializes static arrays initialized with values gathered from
515 the SWTCH switch statement. Also creates statements that load values from
519 build_arrays (gimple swtch)
522 tree tidx, sub, utype;
524 gimple_stmt_iterator gsi;
527 gsi = gsi_for_stmt (swtch);
529 arr_index_type = build_index_type (info.range_size);
531 /* Make sure we do not generate arithmetics in a subrange. */
532 if (TREE_TYPE (TREE_TYPE (info.index_expr)))
533 utype = lang_hooks.types.type_for_mode
534 (TYPE_MODE (TREE_TYPE (TREE_TYPE (info.index_expr))), 1);
536 utype = lang_hooks.types.type_for_mode
537 (TYPE_MODE (TREE_TYPE (info.index_expr)), 1);
539 tidx = make_rename_temp (utype, "csui");
540 sub = fold_build2 (MINUS_EXPR, utype,
541 fold_convert (utype, info.index_expr),
542 fold_convert (utype, info.range_min));
543 sub = force_gimple_operand_gsi (&gsi, sub, false, NULL, true, GSI_SAME_STMT);
544 stmt = gimple_build_assign (tidx, sub);
546 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
547 mark_symbols_for_renaming (stmt);
548 info.arr_ref_first = stmt;
550 for (gsi = gsi_start_phis (info.final_bb), i = 0;
551 !gsi_end_p (gsi); gsi_next (&gsi), i++)
552 build_one_array (swtch, i, arr_index_type, gsi_stmt (gsi), tidx);
555 /* Generates and appropriately inserts loads of default values at the position
556 given by BSI. Returns the last inserted statement. */
559 gen_def_assigns (gimple_stmt_iterator *gsi)
562 gimple assign = NULL;
564 for (i = 0; i < info.phi_count; i++)
567 = make_ssa_name (SSA_NAME_VAR (info.target_inbound_names[i]), NULL);
569 info.target_outbound_names[i] = name;
570 assign = gimple_build_assign (name, info.default_values[i]);
571 SSA_NAME_DEF_STMT (name) = assign;
572 gsi_insert_before (gsi, assign, GSI_SAME_STMT);
573 find_new_referenced_vars (assign);
574 mark_symbols_for_renaming (assign);
579 /* Deletes the unused bbs and edges that now contain the switch statement and
580 its empty branch bbs. BBD is the now dead BB containing the original switch
581 statement, FINAL is the last BB of the converted switch statement (in terms
585 prune_bbs (basic_block bbd, basic_block final)
590 for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
596 delete_basic_block (bb);
598 delete_basic_block (bbd);
601 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
602 from the basic block loading values from an array and E2F from the basic
603 block loading default values. BBF is the last switch basic block (see the
604 bbf description in the comment below). */
607 fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
609 gimple_stmt_iterator gsi;
612 for (gsi = gsi_start_phis (bbf), i = 0;
613 !gsi_end_p (gsi); gsi_next (&gsi), i++)
615 gimple phi = gsi_stmt (gsi);
616 add_phi_arg (phi, info.target_inbound_names[i], e1f);
617 add_phi_arg (phi, info.target_outbound_names[i], e2f);
622 /* Creates a check whether the switch expression value actually falls into the
623 range given by all the cases. If it does not, the temporaries are loaded
624 with default values instead. SWTCH is the switch statement being converted.
626 bb0 is the bb with the switch statement, however, we'll end it with a
629 bb1 is the bb to be used when the range check went ok. It is derived from
632 bb2 is the bb taken when the expression evaluated outside of the range
633 covered by the created arrays. It is populated by loads of default
636 bbF is a fall through for both bb1 and bb2 and contains exactly what
637 originally followed the switch statement.
639 bbD contains the switch statement (in the end). It is unreachable but we
640 still need to strip off its edges.
644 gen_inbound_check (gimple swtch)
646 tree label_decl1 = create_artificial_label ();
647 tree label_decl2 = create_artificial_label ();
648 tree label_decl3 = create_artificial_label ();
649 gimple label1, label2, label3;
658 gimple_stmt_iterator gsi;
659 basic_block bb0, bb1, bb2, bbf, bbd;
660 edge e01, e02, e21, e1d, e1f, e2f;
662 gcc_assert (info.default_values);
663 bb0 = gimple_bb (swtch);
665 tidx = gimple_assign_lhs (info.arr_ref_first);
666 utype = TREE_TYPE (tidx);
668 /* (end of) block 0 */
669 gsi = gsi_for_stmt (info.arr_ref_first);
672 bound = fold_convert (utype, info.range_size);
674 cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
676 find_new_referenced_vars (cond_stmt);
677 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
678 mark_symbols_for_renaming (cond_stmt);
681 label2 = gimple_build_label (label_decl2);
682 gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
683 last_assign = gen_def_assigns (&gsi);
686 label1 = gimple_build_label (label_decl1);
687 gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
690 gsi = gsi_start_bb (info.final_bb);
691 label3 = gimple_build_label (label_decl3);
692 gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
695 e02 = split_block (bb0, cond_stmt);
698 e21 = split_block (bb2, last_assign);
702 e1d = split_block (bb1, info.arr_ref_last);
706 /* flags and profiles of the edge for in-range values */
707 e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
708 e01->probability = REG_BR_PROB_BASE - info.default_prob;
709 e01->count = info.other_count;
711 /* flags and profiles of the edge taking care of out-of-range values */
712 e02->flags &= ~EDGE_FALLTHRU;
713 e02->flags |= EDGE_FALSE_VALUE;
714 e02->probability = info.default_prob;
715 e02->count = info.default_count;
719 e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
720 e1f->probability = REG_BR_PROB_BASE;
721 e1f->count = info.other_count;
723 e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
724 e2f->probability = REG_BR_PROB_BASE;
725 e2f->count = info.default_count;
727 /* frequencies of the new BBs */
728 bb1->frequency = EDGE_FREQUENCY (e01);
729 bb2->frequency = EDGE_FREQUENCY (e02);
730 bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
732 prune_bbs (bbd, info.final_bb); /* To keep calc_dfs_tree() in dominance.c
735 fix_phi_nodes (e1f, e2f, bbf);
737 free_dominance_info (CDI_DOMINATORS);
738 free_dominance_info (CDI_POST_DOMINATORS);
741 /* The following function is invoked on every switch statement (the current one
742 is given in SWTCH) and runs the individual phases of switch conversion on it
743 one after another until one fails or the conversion is completed. */
746 process_switch (gimple swtch)
748 unsigned int i, branch_num = gimple_switch_num_labels (swtch);
751 /* Operand 2 is either NULL_TREE or a vector of cases (stmt.c). */
754 info.reason = "switch has no labels\n";
758 info.final_bb = NULL;
759 info.switch_bb = gimple_bb (swtch);
760 info.index_expr = gimple_switch_index (swtch);
761 index_type = TREE_TYPE (info.index_expr);
762 info.arr_ref_first = NULL;
763 info.arr_ref_last = NULL;
764 info.default_prob = 0;
765 info.default_count = 0;
766 info.other_count = 0;
768 /* An ERROR_MARK occurs for various reasons including invalid data type.
769 (comment from stmt.c) */
770 if (index_type == error_mark_node)
772 info.reason = "index error.\n";
776 /* Check the case label values are within reasonable range: */
777 if (!check_range (swtch))
780 /* For all the cases, see whether they are empty, the assignments they
781 represent constant and so on... */
782 for (i = 0; i < branch_num; i++)
783 if (!check_process_case (gimple_switch_label (swtch, i)))
786 fprintf (dump_file, "Processing of case %i failed\n", i);
790 if (!check_final_bb ())
793 /* At this point all checks have passed and we can proceed with the
796 create_temp_arrays ();
797 gather_default_values (gimple_switch_label (swtch, 0));
798 build_constructors (swtch);
800 build_arrays (swtch); /* Build the static arrays and assignments. */
801 gen_inbound_check (swtch); /* Build the bounds check. */
808 /* The main function of the pass scans statements for switches and invokes
809 process_switch on them. */
818 gimple stmt = last_stmt (bb);
819 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
823 expanded_location loc = expand_location (gimple_location (stmt));
825 fprintf (dump_file, "beginning to process the following "
826 "SWITCH statement (%s:%d) : ------- \n",
828 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
829 fprintf (dump_file, "\n");
833 if (process_switch (stmt))
837 fprintf (dump_file, "Switch converted\n");
838 fprintf (dump_file, "--------------------------------\n");
845 gcc_assert (info.reason);
846 fprintf (dump_file, "Bailing out - ");
847 fprintf (dump_file, info.reason);
848 fprintf (dump_file, "--------------------------------\n");
860 switchconv_gate (void)
862 return flag_tree_switch_conversion != 0;
865 struct gimple_opt_pass pass_convert_switch =
869 "switchconv", /* name */
870 switchconv_gate, /* gate */
871 do_switchconv, /* execute */
874 0, /* static_pass_number */
875 TV_TREE_SWITCH_CONVERSION, /* tv_id */
876 PROP_cfg | PROP_ssa, /* properties_required */
877 0, /* properties_provided */
878 0, /* properties_destroyed */
879 0, /* todo_flags_start */
880 TODO_update_ssa | TODO_dump_func
881 | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */