/* Switch Conversion converts variable initializations based on switch
statements to initializations from a static array.
- Copyright (C) 2006, 2008 Free Software Foundation, Inc.
+ Copyright (C) 2006, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
Contributed by Martin Jambor <jamborm@suse.cz>
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include <signal.h>
-
#include "line-map.h"
#include "params.h"
#include "flags.h"
#include "output.h"
#include "input.h"
#include "tree-pass.h"
-#include "diagnostic.h"
+#include "gimple-pretty-print.h"
#include "tree-dump.h"
#include "timevar.h"
+#include "langhooks.h"
/* The main structure of the pass. */
struct switch_conv_info
/* String reason why the case wasn't a good candidate that is written to the
dump file, if there is one. */
const char *reason;
+
+ /* Parameters for expand_switch_using_bit_tests. Should be computed
+ the same way as in expand_case. */
+ unsigned int bit_test_uniq;
+ unsigned int bit_test_count;
+ basic_block bit_test_bb[2];
};
/* Global pass info. */
tree range_max;
/* The gimplifier has already sorted the cases by CASE_LOW and ensured there
- is a default label which is the last in the vector. */
+ is a default label which is the first in the vector. */
min_case = gimple_switch_label (swtch, 1);
info.range_min = CASE_LOW (min_case);
gcc_assert (info.range_min);
gcc_assert (range_max);
- info.range_size = int_const_binop (MINUS_EXPR, range_max, info.range_min, 0);
+ info.range_size = int_const_binop (MINUS_EXPR, range_max, info.range_min);
gcc_assert (info.range_size);
if (!host_integerp (info.range_size, 1))
info.default_count = e->count;
}
else
- info.other_count += e->count;
+ {
+ int i;
+ info.other_count += e->count;
+ for (i = 0; i < 2; i++)
+ if (info.bit_test_bb[i] == label_bb)
+ break;
+ else if (info.bit_test_bb[i] == NULL)
+ {
+ info.bit_test_bb[i] = label_bb;
+ info.bit_test_uniq++;
+ break;
+ }
+ if (i == 2)
+ info.bit_test_uniq = 3;
+ if (CASE_HIGH (cs) != NULL_TREE
+ && ! tree_int_cst_equal (CASE_LOW (cs), CASE_HIGH (cs)))
+ info.bit_test_count += 2;
+ else
+ info.bit_test_count++;
+ }
if (!label_bb)
{
{
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))
- && !is_gimple_ip_invariant (gimple_phi_arg_def (phi, i)))
+ if (bb == info.switch_bb
+ || (single_pred_p (bb) && single_pred (bb) == info.switch_bb))
{
- info.reason = " Non-invariant value from a case\n";
- return false; /* Non-invariant argument. */
+ tree reloc, val;
+
+ val = gimple_phi_arg_def (phi, i);
+ if (!is_gimple_ip_invariant (val))
+ {
+ info.reason = " Non-invariant value from a case\n";
+ 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)
+ info.reason
+ = " Value from a case would need runtime relocations\n";
+ else
+ info.reason
+ = " Value from a case is not a valid initializer\n";
+ return false;
+ }
}
}
}
{
int i;
- info.default_values = (tree *) xcalloc (info.phi_count, sizeof (tree));
- info.constructors = (VEC (constructor_elt, gc) **) xcalloc (info.phi_count,
- sizeof (tree));
- info.target_inbound_names = (tree *) xcalloc (info.phi_count, sizeof (tree));
- info.target_outbound_names = (tree *) xcalloc (info.phi_count,
- sizeof (tree));
-
+ info.default_values = XCNEWVEC (tree, info.phi_count * 3);
+ info.constructors = XCNEWVEC (VEC (constructor_elt, gc) *, info.phi_count);
+ info.target_inbound_names = info.default_values + info.phi_count;
+ info.target_outbound_names = info.target_inbound_names + info.phi_count;
for (i = 0; i < info.phi_count; i++)
info.constructors[i]
= VEC_alloc (constructor_elt, gc, tree_low_cst (info.range_size, 1) + 1);
static void
free_temp_arrays (void)
{
- free (info.constructors);
- free (info.default_values);
- free (info.target_inbound_names);
- free (info.target_outbound_names);
+ XDELETEVEC (info.constructors);
+ XDELETEVEC (info.default_values);
}
/* Populate the array of default values in the order of phi nodes.
elt = VEC_quick_push (constructor_elt,
info.constructors[k], NULL);
elt->index = int_const_binop (MINUS_EXPR, pos,
- info.range_min, 0);
+ info.range_min);
elt->value = info.default_values[k];
}
- pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
+ pos = int_const_binop (PLUS_EXPR, pos, integer_one_node);
}
gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
{
gimple phi = gsi_stmt (gsi);
tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ tree low = CASE_LOW (cs);
pos = CASE_LOW (cs);
- while (!tree_int_cst_lt (high, pos))
+ do
{
constructor_elt *elt;
elt = VEC_quick_push (constructor_elt,
info.constructors[j], NULL);
- elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min, 0);
+ elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min);
elt->value = val;
- pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
- }
+ pos = int_const_binop (PLUS_EXPR, pos, integer_one_node);
+ } while (!tree_int_cst_lt (high, pos)
+ && tree_int_cst_lt (low, pos));
j++;
}
}
}
+/* If all values in the constructor vector are the same, return the value.
+ Otherwise return NULL_TREE. Not supposed to be called for empty
+ vectors. */
+
+static tree
+constructor_contains_same_values_p (VEC (constructor_elt, gc) *vec)
+{
+ unsigned int i;
+ tree prev = NULL_TREE;
+ constructor_elt *elt;
+
+ FOR_EACH_VEC_ELT (constructor_elt, vec, i, elt)
+ {
+ if (!prev)
+ prev = elt->value;
+ else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
+ return NULL_TREE;
+ }
+ return prev;
+}
+
+/* Return type which should be used for array elements, either TYPE,
+ or for integral type some smaller integral type that can still hold
+ all the constants. */
+
+static tree
+array_value_type (gimple swtch, tree type, int num)
+{
+ unsigned int i, len = VEC_length (constructor_elt, info.constructors[num]);
+ constructor_elt *elt;
+ enum machine_mode mode;
+ int sign = 0;
+ tree smaller_type;
+
+ if (!INTEGRAL_TYPE_P (type))
+ return type;
+
+ mode = GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type)));
+ if (GET_MODE_SIZE (TYPE_MODE (type)) <= GET_MODE_SIZE (mode))
+ return type;
+
+ if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32))
+ return type;
+
+ FOR_EACH_VEC_ELT (constructor_elt, info.constructors[num], i, elt)
+ {
+ double_int cst;
+
+ if (TREE_CODE (elt->value) != INTEGER_CST)
+ return type;
+
+ cst = TREE_INT_CST (elt->value);
+ while (1)
+ {
+ unsigned int prec = GET_MODE_BITSIZE (mode);
+ if (prec > HOST_BITS_PER_WIDE_INT)
+ return type;
+
+ if (sign >= 0
+ && double_int_equal_p (cst, double_int_zext (cst, prec)))
+ {
+ if (sign == 0
+ && double_int_equal_p (cst, double_int_sext (cst, prec)))
+ break;
+ sign = 1;
+ break;
+ }
+ if (sign <= 0
+ && double_int_equal_p (cst, double_int_sext (cst, prec)))
+ {
+ sign = -1;
+ break;
+ }
+
+ if (sign == 1)
+ sign = 0;
+
+ mode = GET_MODE_WIDER_MODE (mode);
+ if (mode == VOIDmode
+ || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (TYPE_MODE (type)))
+ return type;
+ }
+ }
+
+ if (sign == 0)
+ sign = TYPE_UNSIGNED (type) ? 1 : -1;
+ smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
+ if (GET_MODE_SIZE (TYPE_MODE (type))
+ <= GET_MODE_SIZE (TYPE_MODE (smaller_type)))
+ return type;
+
+ return smaller_type;
+}
+
/* Create an appropriate array type and declaration and assemble a static array
variable. Also create a load statement that initializes the variable in
question with a value from the static array. SWTCH is the switch statement
and target SSA names for this particular array. ARR_INDEX_TYPE is the type
of the index of the new array, PHI is the phi node of the final BB that
corresponds to the value that will be loaded from the created array. TIDX
- is a temporary variable holding the index for loads from the new array. */
+ is an ssa name of a temporary variable holding the index for loads from the
+ new array. */
static void
build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi,
tree tidx)
{
- tree array_type, ctor, decl, value_type, name, fetch;
+ tree name, cst;
gimple load;
- gimple_stmt_iterator gsi;
+ gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
+ location_t loc = gimple_location (swtch);
gcc_assert (info.default_values[num]);
- value_type = TREE_TYPE (info.default_values[num]);
- array_type = build_array_type (value_type, arr_index_type);
- ctor = build_constructor (array_type, info.constructors[num]);
- TREE_CONSTANT (ctor) = true;
+ name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL);
+ info.target_inbound_names[num] = name;
- decl = build_decl (VAR_DECL, NULL_TREE, array_type);
- TREE_STATIC (decl) = 1;
- DECL_INITIAL (decl) = ctor;
+ cst = constructor_contains_same_values_p (info.constructors[num]);
+ if (cst)
+ load = gimple_build_assign (name, cst);
+ else
+ {
+ tree array_type, ctor, decl, value_type, fetch, default_type;
- DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
- DECL_ARTIFICIAL (decl) = 1;
- TREE_CONSTANT (decl) = 1;
- add_referenced_var (decl);
- varpool_mark_needed_node (varpool_node (decl));
- varpool_finalize_decl (decl);
- mark_sym_for_renaming (decl);
+ default_type = TREE_TYPE (info.default_values[num]);
+ value_type = array_value_type (swtch, default_type, num);
+ array_type = build_array_type (value_type, arr_index_type);
+ if (default_type != value_type)
+ {
+ unsigned int i;
+ constructor_elt *elt;
- name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL);
- info.target_inbound_names[num] = name;
+ FOR_EACH_VEC_ELT (constructor_elt, info.constructors[num], i, elt)
+ elt->value = fold_convert (value_type, elt->value);
+ }
+ ctor = build_constructor (array_type, info.constructors[num]);
+ TREE_CONSTANT (ctor) = true;
+ TREE_STATIC (ctor) = true;
+
+ decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
+ TREE_STATIC (decl) = 1;
+ DECL_INITIAL (decl) = ctor;
+
+ DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
+ DECL_ARTIFICIAL (decl) = 1;
+ TREE_CONSTANT (decl) = 1;
+ TREE_READONLY (decl) = 1;
+ add_referenced_var (decl);
+ varpool_mark_needed_node (varpool_node (decl));
+ varpool_finalize_decl (decl);
+
+ fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
+ NULL_TREE);
+ if (default_type != value_type)
+ {
+ fetch = fold_convert (default_type, fetch);
+ fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
+ true, GSI_SAME_STMT);
+ }
+ load = gimple_build_assign (name, fetch);
+ }
- fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
- NULL_TREE);
- load = gimple_build_assign (name, fetch);
SSA_NAME_DEF_STMT (name) = load;
-
- gsi = gsi_for_stmt (swtch);
gsi_insert_before (&gsi, load, GSI_SAME_STMT);
- mark_symbols_for_renaming (load);
-
+ update_stmt (load);
info.arr_ref_last = load;
}
build_arrays (gimple swtch)
{
tree arr_index_type;
- tree tidx, sub;
+ tree tidx, sub, tmp, utype;
gimple stmt;
gimple_stmt_iterator gsi;
int i;
+ location_t loc = gimple_location (swtch);
gsi = gsi_for_stmt (swtch);
+ /* Make sure we do not generate arithmetics in a subrange. */
+ utype = TREE_TYPE (info.index_expr);
+ if (TREE_TYPE (utype))
+ utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
+ else
+ utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
+
arr_index_type = build_index_type (info.range_size);
- tidx = make_rename_temp (arr_index_type, "csti");
- sub = fold_build2 (MINUS_EXPR, TREE_TYPE (info.index_expr), info.index_expr,
- fold_convert (TREE_TYPE (info.index_expr),
- info.range_min));
- sub = force_gimple_operand_gsi (&gsi, fold_convert (arr_index_type, sub),
+ tmp = create_tmp_var (utype, "csui");
+ add_referenced_var (tmp);
+ tidx = make_ssa_name (tmp, NULL);
+ sub = fold_build2_loc (loc, MINUS_EXPR, utype,
+ fold_convert_loc (loc, utype, info.index_expr),
+ fold_convert_loc (loc, utype, info.range_min));
+ sub = force_gimple_operand_gsi (&gsi, sub,
false, NULL, true, GSI_SAME_STMT);
stmt = gimple_build_assign (tidx, sub);
+ SSA_NAME_DEF_STMT (tidx) = stmt;
gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
- mark_symbols_for_renaming (stmt);
+ update_stmt (stmt);
info.arr_ref_first = stmt;
for (gsi = gsi_start_phis (info.final_bb), i = 0;
assign = gimple_build_assign (name, info.default_values[i]);
SSA_NAME_DEF_STMT (name) = assign;
gsi_insert_before (gsi, assign, GSI_SAME_STMT);
- find_new_referenced_vars (assign);
- mark_symbols_for_renaming (assign);
+ update_stmt (assign);
}
return assign;
}
!gsi_end_p (gsi); gsi_next (&gsi), i++)
{
gimple phi = gsi_stmt (gsi);
- add_phi_arg (phi, info.target_inbound_names[i], e1f);
- add_phi_arg (phi, info.target_outbound_names[i], e2f);
+ add_phi_arg (phi, info.target_inbound_names[i], e1f, UNKNOWN_LOCATION);
+ add_phi_arg (phi, info.target_outbound_names[i], e2f, UNKNOWN_LOCATION);
}
}
static void
gen_inbound_check (gimple swtch)
{
- tree label_decl1 = create_artificial_label ();
- tree label_decl2 = create_artificial_label ();
- tree label_decl3 = create_artificial_label ();
+ tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
+ tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
+ tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
gimple label1, label2, label3;
-
- tree utype;
- tree tmp_u;
- tree cast;
- gimple cast_assign, minus_assign;
- tree ulb, minus;
+ tree utype, tidx;
tree bound;
gimple cond_stmt;
gimple_stmt_iterator gsi;
basic_block bb0, bb1, bb2, bbf, bbd;
edge e01, e02, e21, e1d, e1f, e2f;
+ location_t loc = gimple_location (swtch);
gcc_assert (info.default_values);
bb0 = gimple_bb (swtch);
- /* Make sure we do not generate arithmetics in a subrange. */
- if (TREE_TYPE (TREE_TYPE (info.index_expr)))
- utype = unsigned_type_for (TREE_TYPE (TREE_TYPE (info.index_expr)));
- else
- utype = unsigned_type_for (TREE_TYPE (info.index_expr));
+ tidx = gimple_assign_lhs (info.arr_ref_first);
+ utype = TREE_TYPE (tidx);
/* (end of) block 0 */
gsi = gsi_for_stmt (info.arr_ref_first);
- tmp_u = make_rename_temp (utype, "csui");
-
- cast = fold_convert (utype, info.index_expr);
- cast_assign = gimple_build_assign (tmp_u, cast);
- find_new_referenced_vars (cast_assign);
- gsi_insert_before (&gsi, cast_assign, GSI_SAME_STMT);
- mark_symbols_for_renaming (cast_assign);
-
- ulb = fold_convert (utype, info.range_min);
- minus = fold_build2 (MINUS_EXPR, utype, tmp_u, ulb);
- minus = force_gimple_operand_gsi (&gsi, minus, false, NULL, true,
- GSI_SAME_STMT);
- minus_assign = gimple_build_assign (tmp_u, minus);
- find_new_referenced_vars (minus_assign);
- gsi_insert_before (&gsi, minus_assign, GSI_SAME_STMT);
- mark_symbols_for_renaming (minus_assign);
-
- bound = fold_convert (utype, info.range_size);
+ gsi_next (&gsi);
- cond_stmt = gimple_build_cond (LE_EXPR, tmp_u, bound, NULL_TREE, NULL_TREE);
-
- find_new_referenced_vars (cond_stmt);
+ bound = fold_convert_loc (loc, utype, info.range_size);
+ cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
- mark_symbols_for_renaming (cond_stmt);
+ update_stmt (cond_stmt);
/* block 2 */
- gsi = gsi_for_stmt (info.arr_ref_first);
label2 = gimple_build_label (label_decl2);
gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
last_assign = gen_def_assigns (&gsi);
/* block 1 */
- gsi = gsi_for_stmt (info.arr_ref_first);
label1 = gimple_build_label (label_decl1);
gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
info.default_prob = 0;
info.default_count = 0;
info.other_count = 0;
+ info.bit_test_uniq = 0;
+ info.bit_test_count = 0;
+ info.bit_test_bb[0] = NULL;
+ info.bit_test_bb[1] = NULL;
/* An ERROR_MARK occurs for various reasons including invalid data type.
(comment from stmt.c) */
return false;
}
+ if (info.bit_test_uniq <= 2)
+ {
+ rtl_profile_for_bb (gimple_bb (swtch));
+ if (expand_switch_using_bit_tests_p (gimple_switch_index (swtch),
+ info.range_size, info.bit_test_uniq,
+ info.bit_test_count))
+ {
+ info.reason = " Expanding as bit test is preferable\n";
+ return false;
+ }
+ }
+
if (!check_final_bb ())
return false;
"SWITCH statement (%s:%d) : ------- \n",
loc.file, loc.line);
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
- fprintf (dump_file, "\n");
+ putc ('\n', dump_file);
}
info.reason = NULL;
{
if (dump_file)
{
- fprintf (dump_file, "Switch converted\n");
- fprintf (dump_file, "--------------------------------\n");
+ fputs ("Switch converted\n", dump_file);
+ fputs ("--------------------------------\n", dump_file);
}
}
else
if (dump_file)
{
gcc_assert (info.reason);
- fprintf (dump_file, "Bailing out - ");
- fprintf (dump_file, info.reason);
- fprintf (dump_file, "--------------------------------\n");
+ fputs ("Bailing out - ", dump_file);
+ fputs (info.reason, dump_file);
+ fputs ("--------------------------------\n", dump_file);
}
}
}
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_update_ssa | TODO_dump_func
+ TODO_update_ssa
| TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
}
};
OSDN Git Service
