/* 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)
{
return false;
}
- e = single_succ_edge (label_bb);
+ if (!single_succ_p (label_bb))
+ {
+ info.reason
+ = " Bad case - a non-final BB without a single successor\n";
+ return false;
+ }
following_bb = single_succ (label_bb);
}
{
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)));
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++;
static tree
constructor_contains_same_values_p (VEC (constructor_elt, gc) *vec)
{
- int i, len = VEC_length (constructor_elt, vec);
+ unsigned int i;
tree prev = NULL_TREE;
+ constructor_elt *elt;
- for (i = 0; i < len; i++)
+ FOR_EACH_VEC_ELT (constructor_elt, vec, i, elt)
{
- constructor_elt *elt = VEC_index (constructor_elt, vec, i);
-
if (!prev)
prev = elt->value;
else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
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
load = gimple_build_assign (name, cst);
else
{
- tree array_type, ctor, decl, value_type, fetch;
+ tree array_type, ctor, decl, value_type, fetch, default_type;
- value_type = TREE_TYPE (info.default_values[num]);
+ 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;
+
+ 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_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);
}
build_arrays (gimple swtch)
{
tree arr_index_type;
- tree tidx, sub, tmp;
+ tree tidx, sub, tmp, utype;
gimple stmt;
gimple_stmt_iterator gsi;
int i;
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);
- tmp = create_tmp_var (TREE_TYPE (info.index_expr), "csti");
+ tmp = create_tmp_var (utype, "csui");
add_referenced_var (tmp);
tidx = make_ssa_name (tmp, NULL);
- sub = fold_build2_loc (loc, MINUS_EXPR,
- TREE_TYPE (info.index_expr), info.index_expr,
- fold_convert_loc (loc, TREE_TYPE (info.index_expr),
- info.range_min));
+ 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);
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_1, tmp_u_2, tmp_u_var;
- tree cast;
- gimple cast_assign, minus_assign;
- tree ulb, minus;
+ tree utype, tidx;
tree bound;
gimple cond_stmt;
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_var = create_tmp_var (utype, "csui");
- add_referenced_var (tmp_u_var);
- tmp_u_1 = make_ssa_name (tmp_u_var, NULL);
-
- cast = fold_convert_loc (loc, utype, info.index_expr);
- cast_assign = gimple_build_assign (tmp_u_1, cast);
- SSA_NAME_DEF_STMT (tmp_u_1) = cast_assign;
- gsi_insert_before (&gsi, cast_assign, GSI_SAME_STMT);
- update_stmt (cast_assign);
-
- ulb = fold_convert_loc (loc, utype, info.range_min);
- minus = fold_build2_loc (loc, MINUS_EXPR, utype, tmp_u_1, ulb);
- minus = force_gimple_operand_gsi (&gsi, minus, false, NULL, true,
- GSI_SAME_STMT);
- tmp_u_2 = make_ssa_name (tmp_u_var, NULL);
- minus_assign = gimple_build_assign (tmp_u_2, minus);
- SSA_NAME_DEF_STMT (tmp_u_2) = minus_assign;
- gsi_insert_before (&gsi, minus_assign, GSI_SAME_STMT);
- update_stmt (minus_assign);
+ gsi_next (&gsi);
bound = fold_convert_loc (loc, utype, info.range_size);
- cond_stmt = gimple_build_cond (LE_EXPR, tmp_u_2, bound, NULL_TREE, NULL_TREE);
+ cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
gsi_insert_before (&gsi, cond_stmt, GSI_SAME_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;
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
