/* Expands front end tree to back end RTL for GCC
Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
- 2010 Free Software Foundation, Inc.
+ 2010, 2011, 2012 Free Software Foundation, Inc.
This file is part of GCC.
#include "regs.h"
#include "alloc-pool.h"
#include "pretty-print.h"
-#include "bitmap.h"
+#include "pointer-set.h"
#include "params.h"
+#include "dumpfile.h"
\f
/* Functions and data structures for expanding case statements. */
typedef struct case_node case_node;
typedef struct case_node *case_node_ptr;
-/* These are used by estimate_case_costs and balance_case_nodes. */
-
-/* This must be a signed type, and non-ANSI compilers lack signed char. */
-static short cost_table_[129];
-static int use_cost_table;
-static int cost_table_initialized;
-
-/* Special care is needed because we allow -1, but TREE_INT_CST_LOW
- is unsigned. */
-#define COST_TABLE(I) cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)]
\f
static int n_occurrences (int, const char *);
static bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *);
static char *resolve_operand_name_1 (char *, tree, tree, tree);
static void expand_null_return_1 (void);
static void expand_value_return (rtx);
-static int estimate_case_costs (case_node_ptr);
-static bool lshift_cheap_p (void);
-static int case_bit_test_cmp (const void *, const void *);
-static void emit_case_bit_tests (tree, tree, tree, tree, case_node_ptr, rtx);
static void balance_case_nodes (case_node_ptr *, case_node_ptr);
static int node_has_low_bound (case_node_ptr, tree);
static int node_has_high_bound (case_node_ptr, tree);
static int node_is_bounded (case_node_ptr, tree);
static void emit_case_nodes (rtx, case_node_ptr, rtx, tree);
-static struct case_node *add_case_node (struct case_node *, tree,
- tree, tree, tree, alloc_pool);
-
\f
/* Return the rtx-label that corresponds to a LABEL_DECL,
creating it if necessary. */
}
else
{
- op = assign_temp (type, 0, 0, 1);
+ op = assign_temp (type, 0, 1);
op = validize_mem (op);
if (!MEM_P (op) && TREE_CODE (TREE_VALUE (tail)) == SSA_NAME)
set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (TREE_VALUE (tail)), op);
at this point. Ignore it: clearly this *is* a memory. */
}
else
- {
- warning (0, "use of memory input without lvalue in "
- "asm operand %d is deprecated", i + noutputs);
-
- if (CONSTANT_P (op))
- {
- rtx mem = force_const_mem (TYPE_MODE (type), op);
- if (mem)
- op = validize_mem (mem);
- else
- op = force_reg (TYPE_MODE (type), op);
- }
- if (REG_P (op)
- || GET_CODE (op) == SUBREG
- || GET_CODE (op) == CONCAT)
- {
- tree qual_type = build_qualified_type (type,
- (TYPE_QUALS (type)
- | TYPE_QUAL_CONST));
- rtx memloc = assign_temp (qual_type, 1, 1, 1);
- memloc = validize_mem (memloc);
- emit_move_insn (memloc, op);
- op = memloc;
- }
- }
+ gcc_unreachable ();
}
generating_concat_p = old_generating_concat_p;
static bool
check_unique_operand_names (tree outputs, tree inputs, tree labels)
{
- tree i, j;
+ tree i, j, i_name = NULL_TREE;
for (i = outputs; i ; i = TREE_CHAIN (i))
{
- tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
+ i_name = TREE_PURPOSE (TREE_PURPOSE (i));
if (! i_name)
continue;
for (i = inputs; i ; i = TREE_CHAIN (i))
{
- tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
+ i_name = TREE_PURPOSE (TREE_PURPOSE (i));
if (! i_name)
continue;
for (i = labels; i ; i = TREE_CHAIN (i))
{
- tree i_name = TREE_PURPOSE (i);
+ i_name = TREE_PURPOSE (i);
if (! i_name)
continue;
return true;
failure:
- error ("duplicate asm operand name %qs",
- TREE_STRING_POINTER (TREE_PURPOSE (TREE_PURPOSE (i))));
+ error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name));
return false;
}
return p;
}
-\f
-/* Generate RTL to evaluate the expression EXP. */
-
-void
-expand_expr_stmt (tree exp)
-{
- rtx value;
- tree type;
-
- value = expand_expr (exp, const0_rtx, VOIDmode, EXPAND_NORMAL);
- type = TREE_TYPE (exp);
-
- /* If all we do is reference a volatile value in memory,
- copy it to a register to be sure it is actually touched. */
- if (value && MEM_P (value) && TREE_THIS_VOLATILE (exp))
- {
- if (TYPE_MODE (type) == VOIDmode)
- ;
- else if (TYPE_MODE (type) != BLKmode)
- copy_to_reg (value);
- else
- {
- rtx lab = gen_label_rtx ();
-
- /* Compare the value with itself to reference it. */
- emit_cmp_and_jump_insns (value, value, EQ,
- expand_normal (TYPE_SIZE (type)),
- BLKmode, 0, lab);
- emit_label (lab);
- }
- }
-
- /* Free any temporaries used to evaluate this expression. */
- free_temp_slots ();
-}
-
-/* Warn if EXP contains any computations whose results are not used.
- Return 1 if a warning is printed; 0 otherwise. LOCUS is the
- (potential) location of the expression. */
-
-int
-warn_if_unused_value (const_tree exp, location_t locus)
-{
- restart:
- if (TREE_USED (exp) || TREE_NO_WARNING (exp))
- return 0;
-
- /* Don't warn about void constructs. This includes casting to void,
- void function calls, and statement expressions with a final cast
- to void. */
- if (VOID_TYPE_P (TREE_TYPE (exp)))
- return 0;
-
- if (EXPR_HAS_LOCATION (exp))
- locus = EXPR_LOCATION (exp);
-
- switch (TREE_CODE (exp))
- {
- case PREINCREMENT_EXPR:
- case POSTINCREMENT_EXPR:
- case PREDECREMENT_EXPR:
- case POSTDECREMENT_EXPR:
- case MODIFY_EXPR:
- case INIT_EXPR:
- case TARGET_EXPR:
- case CALL_EXPR:
- case TRY_CATCH_EXPR:
- case WITH_CLEANUP_EXPR:
- case EXIT_EXPR:
- case VA_ARG_EXPR:
- return 0;
-
- case BIND_EXPR:
- /* For a binding, warn if no side effect within it. */
- exp = BIND_EXPR_BODY (exp);
- goto restart;
-
- case SAVE_EXPR:
- case NON_LVALUE_EXPR:
- exp = TREE_OPERAND (exp, 0);
- goto restart;
-
- case TRUTH_ORIF_EXPR:
- case TRUTH_ANDIF_EXPR:
- /* In && or ||, warn if 2nd operand has no side effect. */
- exp = TREE_OPERAND (exp, 1);
- goto restart;
-
- case COMPOUND_EXPR:
- if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus))
- return 1;
- /* Let people do `(foo (), 0)' without a warning. */
- if (TREE_CONSTANT (TREE_OPERAND (exp, 1)))
- return 0;
- exp = TREE_OPERAND (exp, 1);
- goto restart;
-
- case COND_EXPR:
- /* If this is an expression with side effects, don't warn; this
- case commonly appears in macro expansions. */
- if (TREE_SIDE_EFFECTS (exp))
- return 0;
- goto warn;
-
- case INDIRECT_REF:
- /* Don't warn about automatic dereferencing of references, since
- the user cannot control it. */
- if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE)
- {
- exp = TREE_OPERAND (exp, 0);
- goto restart;
- }
- /* Fall through. */
-
- default:
- /* Referencing a volatile value is a side effect, so don't warn. */
- if ((DECL_P (exp) || REFERENCE_CLASS_P (exp))
- && TREE_THIS_VOLATILE (exp))
- return 0;
-
- /* If this is an expression which has no operands, there is no value
- to be unused. There are no such language-independent codes,
- but front ends may define such. */
- if (EXPRESSION_CLASS_P (exp) && TREE_OPERAND_LENGTH (exp) == 0)
- return 0;
-
- warn:
- warning_at (locus, OPT_Wunused_value, "value computed is not used");
- return 1;
- }
-}
-
\f
/* Generate RTL to return from the current function, with no value.
(That is, we do not do anything about returning any value.) */
expand_value_return (result_rtl);
/* If the result is an aggregate that is being returned in one (or more)
- registers, load the registers here. The compiler currently can't handle
- copying a BLKmode value into registers. We could put this code in a
- more general area (for use by everyone instead of just function
- call/return), but until this feature is generally usable it is kept here
- (and in expand_call). */
+ registers, load the registers here. */
else if (retval_rhs != 0
&& TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode
&& REG_P (result_rtl))
{
- int i;
- unsigned HOST_WIDE_INT bitpos, xbitpos;
- unsigned HOST_WIDE_INT padding_correction = 0;
- unsigned HOST_WIDE_INT bytes
- = int_size_in_bytes (TREE_TYPE (retval_rhs));
- int n_regs = (bytes + UNITS_PER_WORD - 1) / UNITS_PER_WORD;
- unsigned int bitsize
- = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)), BITS_PER_WORD);
- rtx *result_pseudos = XALLOCAVEC (rtx, n_regs);
- rtx result_reg, src = NULL_RTX, dst = NULL_RTX;
- rtx result_val = expand_normal (retval_rhs);
- enum machine_mode tmpmode, result_reg_mode;
-
- if (bytes == 0)
- {
- expand_null_return ();
- return;
- }
-
- /* If the structure doesn't take up a whole number of words, see
- whether the register value should be padded on the left or on
- the right. Set PADDING_CORRECTION to the number of padding
- bits needed on the left side.
-
- In most ABIs, the structure will be returned at the least end of
- the register, which translates to right padding on little-endian
- targets and left padding on big-endian targets. The opposite
- holds if the structure is returned at the most significant
- end of the register. */
- if (bytes % UNITS_PER_WORD != 0
- && (targetm.calls.return_in_msb (TREE_TYPE (retval_rhs))
- ? !BYTES_BIG_ENDIAN
- : BYTES_BIG_ENDIAN))
- padding_correction = (BITS_PER_WORD - ((bytes % UNITS_PER_WORD)
- * BITS_PER_UNIT));
-
- /* Copy the structure BITSIZE bits at a time. */
- for (bitpos = 0, xbitpos = padding_correction;
- bitpos < bytes * BITS_PER_UNIT;
- bitpos += bitsize, xbitpos += bitsize)
- {
- /* We need a new destination pseudo each time xbitpos is
- on a word boundary and when xbitpos == padding_correction
- (the first time through). */
- if (xbitpos % BITS_PER_WORD == 0
- || xbitpos == padding_correction)
- {
- /* Generate an appropriate register. */
- dst = gen_reg_rtx (word_mode);
- result_pseudos[xbitpos / BITS_PER_WORD] = dst;
-
- /* Clear the destination before we move anything into it. */
- emit_move_insn (dst, CONST0_RTX (GET_MODE (dst)));
- }
-
- /* We need a new source operand each time bitpos is on a word
- boundary. */
- if (bitpos % BITS_PER_WORD == 0)
- src = operand_subword_force (result_val,
- bitpos / BITS_PER_WORD,
- BLKmode);
-
- /* Use bitpos for the source extraction (left justified) and
- xbitpos for the destination store (right justified). */
- store_bit_field (dst, bitsize, xbitpos % BITS_PER_WORD,
- 0, 0, word_mode,
- extract_bit_field (src, bitsize,
- bitpos % BITS_PER_WORD, 1, false,
- NULL_RTX, word_mode, word_mode));
- }
-
- tmpmode = GET_MODE (result_rtl);
- if (tmpmode == BLKmode)
+ val = copy_blkmode_to_reg (GET_MODE (result_rtl), retval_rhs);
+ if (val)
{
- /* Find the smallest integer mode large enough to hold the
- entire structure and use that mode instead of BLKmode
- on the USE insn for the return register. */
- for (tmpmode = GET_CLASS_NARROWEST_MODE (MODE_INT);
- tmpmode != VOIDmode;
- tmpmode = GET_MODE_WIDER_MODE (tmpmode))
- /* Have we found a large enough mode? */
- if (GET_MODE_SIZE (tmpmode) >= bytes)
- break;
-
- /* A suitable mode should have been found. */
- gcc_assert (tmpmode != VOIDmode);
-
- PUT_MODE (result_rtl, tmpmode);
+ /* Use the mode of the result value on the return register. */
+ PUT_MODE (result_rtl, GET_MODE (val));
+ expand_value_return (val);
}
-
- if (GET_MODE_SIZE (tmpmode) < GET_MODE_SIZE (word_mode))
- result_reg_mode = word_mode;
else
- result_reg_mode = tmpmode;
- result_reg = gen_reg_rtx (result_reg_mode);
-
- for (i = 0; i < n_regs; i++)
- emit_move_insn (operand_subword (result_reg, i, 0, result_reg_mode),
- result_pseudos[i]);
-
- if (tmpmode != result_reg_mode)
- result_reg = gen_lowpart (tmpmode, result_reg);
-
- expand_value_return (result_reg);
+ expand_null_return ();
}
else if (retval_rhs != 0
&& !VOID_TYPE_P (TREE_TYPE (retval_rhs))
tree ot = TREE_TYPE (DECL_RESULT (current_function_decl));
tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST);
- val = assign_temp (nt, 0, 0, 1);
+ val = assign_temp (nt, 0, 1);
val = expand_expr (retval_rhs, val, GET_MODE (val), EXPAND_NORMAL);
val = force_not_mem (val);
/* Return the calculated value. */
emit_insn (gen_blockage ());
}
\f
-/* Generate RTL for the automatic variable declaration DECL.
- (Other kinds of declarations are simply ignored if seen here.) */
-
-void
-expand_decl (tree decl)
-{
- tree type;
-
- type = TREE_TYPE (decl);
-
- /* For a CONST_DECL, set mode, alignment, and sizes from those of the
- type in case this node is used in a reference. */
- if (TREE_CODE (decl) == CONST_DECL)
- {
- DECL_MODE (decl) = TYPE_MODE (type);
- DECL_ALIGN (decl) = TYPE_ALIGN (type);
- DECL_SIZE (decl) = TYPE_SIZE (type);
- DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type);
- return;
- }
-
- /* Otherwise, only automatic variables need any expansion done. Static and
- external variables, and external functions, will be handled by
- `assemble_variable' (called from finish_decl). TYPE_DECL requires
- nothing. PARM_DECLs are handled in `assign_parms'. */
- if (TREE_CODE (decl) != VAR_DECL)
- return;
-
- if (TREE_STATIC (decl) || DECL_EXTERNAL (decl))
- return;
-
- /* Create the RTL representation for the variable. */
-
- if (type == error_mark_node)
- SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx));
-
- else if (DECL_SIZE (decl) == 0)
- {
- /* Variable with incomplete type. */
- rtx x;
- if (DECL_INITIAL (decl) == 0)
- /* Error message was already done; now avoid a crash. */
- x = gen_rtx_MEM (BLKmode, const0_rtx);
- else
- /* An initializer is going to decide the size of this array.
- Until we know the size, represent its address with a reg. */
- x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode));
-
- set_mem_attributes (x, decl, 1);
- SET_DECL_RTL (decl, x);
- }
- else if (use_register_for_decl (decl))
- {
- /* Automatic variable that can go in a register. */
- enum machine_mode reg_mode = promote_decl_mode (decl, NULL);
-
- SET_DECL_RTL (decl, gen_reg_rtx (reg_mode));
-
- /* Note if the object is a user variable. */
- if (!DECL_ARTIFICIAL (decl))
- mark_user_reg (DECL_RTL (decl));
-
- if (POINTER_TYPE_P (type))
- mark_reg_pointer (DECL_RTL (decl),
- TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl))));
- }
-
- else
- {
- rtx oldaddr = 0;
- rtx addr;
- rtx x;
-
- /* Variable-sized decls are dealt with in the gimplifier. */
- gcc_assert (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST);
-
- /* If we previously made RTL for this decl, it must be an array
- whose size was determined by the initializer.
- The old address was a register; set that register now
- to the proper address. */
- if (DECL_RTL_SET_P (decl))
- {
- gcc_assert (MEM_P (DECL_RTL (decl)));
- gcc_assert (REG_P (XEXP (DECL_RTL (decl), 0)));
- oldaddr = XEXP (DECL_RTL (decl), 0);
- }
-
- /* Set alignment we actually gave this decl. */
- DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT
- : GET_MODE_BITSIZE (DECL_MODE (decl)));
- DECL_USER_ALIGN (decl) = 0;
-
- x = assign_temp (decl, 1, 1, 1);
- set_mem_attributes (x, decl, 1);
- SET_DECL_RTL (decl, x);
-
- if (oldaddr)
- {
- addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr);
- if (addr != oldaddr)
- emit_move_insn (oldaddr, addr);
- }
- }
-}
-\f
/* Emit code to save the current value of stack. */
rtx
expand_stack_save (void)
void
expand_stack_restore (tree var)
{
- rtx sa = expand_normal (var);
+ rtx prev, sa = expand_normal (var);
sa = convert_memory_address (Pmode, sa);
+
+ prev = get_last_insn ();
emit_stack_restore (SAVE_BLOCK, sa);
+ fixup_args_size_notes (prev, get_last_insn (), 0);
+}
+
+/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */
+static void
+do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label,
+ int unsignedp)
+{
+ do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
+ NULL_RTX, NULL_RTX, label, -1);
}
\f
/* Do the insertion of a case label into case_list. The labels are
fed to us in descending order from the sorted vector of case labels used
in the tree part of the middle end. So the list we construct is
- sorted in ascending order. The bounds on the case range, LOW and HIGH,
- are converted to case's index type TYPE. */
+ sorted in ascending order. */
static struct case_node *
-add_case_node (struct case_node *head, tree type, tree low, tree high,
+add_case_node (struct case_node *head, tree low, tree high,
tree label, alloc_pool case_node_pool)
{
- tree min_value, max_value;
struct case_node *r;
- gcc_assert (TREE_CODE (low) == INTEGER_CST);
- gcc_assert (!high || TREE_CODE (high) == INTEGER_CST);
-
- min_value = TYPE_MIN_VALUE (type);
- max_value = TYPE_MAX_VALUE (type);
+ gcc_checking_assert (low);
+ gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high)));
- /* If there's no HIGH value, then this is not a case range; it's
- just a simple case label. But that's just a degenerate case
- range.
- If the bounds are equal, turn this into the one-value case. */
- if (!high || tree_int_cst_equal (low, high))
- {
- /* If the simple case value is unreachable, ignore it. */
- if ((TREE_CODE (min_value) == INTEGER_CST
- && tree_int_cst_compare (low, min_value) < 0)
- || (TREE_CODE (max_value) == INTEGER_CST
- && tree_int_cst_compare (low, max_value) > 0))
- return head;
- low = fold_convert (type, low);
- high = low;
- }
- else
- {
- /* If the entire case range is unreachable, ignore it. */
- if ((TREE_CODE (min_value) == INTEGER_CST
- && tree_int_cst_compare (high, min_value) < 0)
- || (TREE_CODE (max_value) == INTEGER_CST
- && tree_int_cst_compare (low, max_value) > 0))
- return head;
-
- /* If the lower bound is less than the index type's minimum
- value, truncate the range bounds. */
- if (TREE_CODE (min_value) == INTEGER_CST
- && tree_int_cst_compare (low, min_value) < 0)
- low = min_value;
- low = fold_convert (type, low);
-
- /* If the upper bound is greater than the index type's maximum
- value, truncate the range bounds. */
- if (TREE_CODE (max_value) == INTEGER_CST
- && tree_int_cst_compare (high, max_value) > 0)
- high = max_value;
- high = fold_convert (type, high);
- }
-
-
- /* Add this label to the chain. Make sure to drop overflow flags. */
+ /* Add this label to the chain. */
r = (struct case_node *) pool_alloc (case_node_pool);
- r->low = build_int_cst_wide (TREE_TYPE (low), TREE_INT_CST_LOW (low),
- TREE_INT_CST_HIGH (low));
- r->high = build_int_cst_wide (TREE_TYPE (high), TREE_INT_CST_LOW (high),
- TREE_INT_CST_HIGH (high));
+ r->low = low;
+ r->high = high;
r->code_label = label;
r->parent = r->left = NULL;
r->right = head;
return r;
}
\f
-/* Maximum number of case bit tests. */
-#define MAX_CASE_BIT_TESTS 3
+/* Dump ROOT, a list or tree of case nodes, to file. */
+
+static void
+dump_case_nodes (FILE *f, struct case_node *root,
+ int indent_step, int indent_level)
+{
+ HOST_WIDE_INT low, high;
+
+ if (root == 0)
+ return;
+ indent_level++;
-/* By default, enable case bit tests on targets with ashlsi3. */
-#ifndef CASE_USE_BIT_TESTS
-#define CASE_USE_BIT_TESTS (optab_handler (ashl_optab, word_mode) \
- != CODE_FOR_nothing)
+ dump_case_nodes (f, root->left, indent_step, indent_level);
+
+ low = tree_low_cst (root->low, 0);
+ high = tree_low_cst (root->high, 0);
+
+ fputs (";; ", f);
+ if (high == low)
+ fprintf(f, "%*s" HOST_WIDE_INT_PRINT_DEC,
+ indent_step * indent_level, "", low);
+ else
+ fprintf(f, "%*s" HOST_WIDE_INT_PRINT_DEC " ... " HOST_WIDE_INT_PRINT_DEC,
+ indent_step * indent_level, "", low, high);
+ fputs ("\n", f);
+
+ dump_case_nodes (f, root->right, indent_step, indent_level);
+}
+\f
+#ifndef HAVE_casesi
+#define HAVE_casesi 0
#endif
+#ifndef HAVE_tablejump
+#define HAVE_tablejump 0
+#endif
-/* A case_bit_test represents a set of case nodes that may be
- selected from using a bit-wise comparison. HI and LO hold
- the integer to be tested against, LABEL contains the label
- to jump to upon success and BITS counts the number of case
- nodes handled by this test, typically the number of bits
- set in HI:LO. */
+/* Return the smallest number of different values for which it is best to use a
+ jump-table instead of a tree of conditional branches. */
-struct case_bit_test
+static unsigned int
+case_values_threshold (void)
{
- HOST_WIDE_INT hi;
- HOST_WIDE_INT lo;
- rtx label;
- int bits;
-};
+ unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
-/* Determine whether "1 << x" is relatively cheap in word_mode. */
+ if (threshold == 0)
+ threshold = targetm.case_values_threshold ();
-static
-bool lshift_cheap_p (void)
-{
- static bool init[2] = {false, false};
- static bool cheap[2] = {true, true};
+ return threshold;
+}
- bool speed_p = optimize_insn_for_speed_p ();
+/* Return true if a switch should be expanded as a decision tree.
+ RANGE is the difference between highest and lowest case.
+ UNIQ is number of unique case node targets, not counting the default case.
+ COUNT is the number of comparisons needed, not counting the default case. */
- if (!init[speed_p])
- {
- rtx reg = gen_rtx_REG (word_mode, 10000);
- int cost = rtx_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg), SET,
- speed_p);
- cheap[speed_p] = cost < COSTS_N_INSNS (3);
- init[speed_p] = true;
- }
+static bool
+expand_switch_as_decision_tree_p (tree range,
+ unsigned int uniq ATTRIBUTE_UNUSED,
+ unsigned int count)
+{
+ int max_ratio;
+
+ /* If neither casesi or tablejump is available, or flag_jump_tables
+ over-ruled us, we really have no choice. */
+ if (!HAVE_casesi && !HAVE_tablejump)
+ return true;
+ if (!flag_jump_tables)
+ return true;
+
+ /* If the switch is relatively small such that the cost of one
+ indirect jump on the target are higher than the cost of a
+ decision tree, go with the decision tree.
+
+ If range of values is much bigger than number of values,
+ or if it is too large to represent in a HOST_WIDE_INT,
+ make a sequence of conditional branches instead of a dispatch.
+
+ The definition of "much bigger" depends on whether we are
+ optimizing for size or for speed. If the former, the maximum
+ ratio range/count = 3, because this was found to be the optimal
+ ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
+ 10 is much older, and was probably selected after an extensive
+ benchmarking investigation on numerous platforms. Or maybe it
+ just made sense to someone at some point in the history of GCC,
+ who knows... */
+ max_ratio = optimize_insn_for_size_p () ? 3 : 10;
+ if (count < case_values_threshold ()
+ || ! host_integerp (range, /*pos=*/1)
+ || compare_tree_int (range, max_ratio * count) > 0)
+ return true;
- return cheap[speed_p];
+ return false;
}
-/* Comparison function for qsort to order bit tests by decreasing
- number of case nodes, i.e. the node with the most cases gets
- tested first. */
+/* Generate a decision tree, switching on INDEX_EXPR and jumping to
+ one of the labels in CASE_LIST or to the DEFAULT_LABEL.
+
+ We generate a binary decision tree to select the appropriate target
+ code. This is done as follows:
-static int
-case_bit_test_cmp (const void *p1, const void *p2)
-{
- const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
- const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
+ If the index is a short or char that we do not have
+ an insn to handle comparisons directly, convert it to
+ a full integer now, rather than letting each comparison
+ generate the conversion.
- if (d2->bits != d1->bits)
- return d2->bits - d1->bits;
+ Load the index into a register.
- /* Stabilize the sort. */
- return CODE_LABEL_NUMBER (d2->label) - CODE_LABEL_NUMBER (d1->label);
-}
+ The list of cases is rearranged into a binary tree,
+ nearly optimal assuming equal probability for each case.
-/* Expand a switch statement by a short sequence of bit-wise
- comparisons. "switch(x)" is effectively converted into
- "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
- integer constants.
+ The tree is transformed into RTL, eliminating redundant
+ test conditions at the same time.
- INDEX_EXPR is the value being switched on, which is of
- type INDEX_TYPE. MINVAL is the lowest case value of in
- the case nodes, of INDEX_TYPE type, and RANGE is highest
- value minus MINVAL, also of type INDEX_TYPE. NODES is
- the set of case nodes, and DEFAULT_LABEL is the label to
- branch to should none of the cases match.
+ If program flow could reach the end of the decision tree
+ an unconditional jump to the default code is emitted.
- There *MUST* be MAX_CASE_BIT_TESTS or less unique case
- node targets. */
+ The above process is unaware of the CFG. The caller has to fix up
+ the CFG itself. This is done in cfgexpand.c. */
static void
-emit_case_bit_tests (tree index_type, tree index_expr, tree minval,
- tree range, case_node_ptr nodes, rtx default_label)
+emit_case_decision_tree (tree index_expr, tree index_type,
+ struct case_node *case_list, rtx default_label)
{
- struct case_bit_test test[MAX_CASE_BIT_TESTS];
- enum machine_mode mode;
- rtx expr, index, label;
- unsigned int i,j,lo,hi;
- struct case_node *n;
- unsigned int count;
+ rtx index = expand_normal (index_expr);
- count = 0;
- for (n = nodes; n; n = n->right)
+ if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
+ && ! have_insn_for (COMPARE, GET_MODE (index)))
{
- label = label_rtx (n->code_label);
- for (i = 0; i < count; i++)
- if (label == test[i].label)
- break;
-
- if (i == count)
- {
- gcc_assert (count < MAX_CASE_BIT_TESTS);
- test[i].hi = 0;
- test[i].lo = 0;
- test[i].label = label;
- test[i].bits = 1;
- count++;
- }
- else
- test[i].bits++;
-
- lo = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
- n->low, minval), 1);
- hi = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
- n->high, minval), 1);
- for (j = lo; j <= hi; j++)
- if (j >= HOST_BITS_PER_WIDE_INT)
- test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT);
- else
- test[i].lo |= (HOST_WIDE_INT) 1 << j;
+ int unsignedp = TYPE_UNSIGNED (index_type);
+ enum machine_mode wider_mode;
+ for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
+ wider_mode = GET_MODE_WIDER_MODE (wider_mode))
+ if (have_insn_for (COMPARE, wider_mode))
+ {
+ index = convert_to_mode (wider_mode, index, unsignedp);
+ break;
+ }
}
- qsort (test, count, sizeof(*test), case_bit_test_cmp);
-
- index_expr = fold_build2 (MINUS_EXPR, index_type,
- fold_convert (index_type, index_expr),
- fold_convert (index_type, minval));
- index = expand_normal (index_expr);
do_pending_stack_adjust ();
- mode = TYPE_MODE (index_type);
- expr = expand_normal (range);
- if (default_label)
- emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
- default_label);
+ if (MEM_P (index))
+ {
+ index = copy_to_reg (index);
+ if (TREE_CODE (index_expr) == SSA_NAME)
+ set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr), index);
+ }
- index = convert_to_mode (word_mode, index, 0);
- index = expand_binop (word_mode, ashl_optab, const1_rtx,
- index, NULL_RTX, 1, OPTAB_WIDEN);
+ balance_case_nodes (&case_list, NULL);
- for (i = 0; i < count; i++)
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- expr = immed_double_const (test[i].lo, test[i].hi, word_mode);
- expr = expand_binop (word_mode, and_optab, index, expr,
- NULL_RTX, 1, OPTAB_WIDEN);
- emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX,
- word_mode, 1, test[i].label);
+ int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
+ fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
+ dump_case_nodes (dump_file, case_list, indent_step, 0);
}
+ emit_case_nodes (index, case_list, default_label, index_type);
if (default_label)
emit_jump (default_label);
}
-#ifndef HAVE_casesi
-#define HAVE_casesi 0
-#endif
+/* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
+ one of the labels in CASE_LIST or to the DEFAULT_LABEL.
+ MINVAL, MAXVAL, and RANGE are the extrema and range of the case
+ labels in CASE_LIST.
-#ifndef HAVE_tablejump
-#define HAVE_tablejump 0
-#endif
+ First, a jump insn is emitted. First we try "casesi". If that
+ fails, try "tablejump". A target *must* have one of them (or both).
-/* Return true if a switch should be expanded as a bit test.
- INDEX_EXPR is the index expression, RANGE is the difference between
- highest and lowest case, UNIQ is number of unique case node targets
- not counting the default case and COUNT is the number of comparisons
- needed, not counting the default case. */
-bool
-expand_switch_using_bit_tests_p (tree index_expr, tree range,
- unsigned int uniq, unsigned int count)
-{
- return (CASE_USE_BIT_TESTS
- && ! TREE_CONSTANT (index_expr)
- && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
- && compare_tree_int (range, 0) > 0
- && lshift_cheap_p ()
- && ((uniq == 1 && count >= 3)
- || (uniq == 2 && count >= 5)
- || (uniq == 3 && count >= 6)));
-}
+ Then, a table with the target labels is emitted.
-/* Return the smallest number of different values for which it is best to use a
- jump-table instead of a tree of conditional branches. */
+ The process is unaware of the CFG. The caller has to fix up
+ the CFG itself. This is done in cfgexpand.c. */
-static unsigned int
-case_values_threshold (void)
+static void
+emit_case_dispatch_table (tree index_expr, tree index_type,
+ struct case_node *case_list, rtx default_label,
+ tree minval, tree maxval, tree range)
{
- unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
+ int i, ncases;
+ struct case_node *n;
+ rtx *labelvec;
+ rtx fallback_label = label_rtx (case_list->code_label);
+ rtx table_label = gen_label_rtx ();
- if (threshold == 0)
- threshold = targetm.case_values_threshold ();
+ if (! try_casesi (index_type, index_expr, minval, range,
+ table_label, default_label, fallback_label))
+ {
+ bool ok;
- return threshold;
+ /* Index jumptables from zero for suitable values of minval to avoid
+ a subtraction. For the rationale see:
+ "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
+ if (optimize_insn_for_speed_p ()
+ && compare_tree_int (minval, 0) > 0
+ && compare_tree_int (minval, 3) < 0)
+ {
+ minval = build_int_cst (index_type, 0);
+ range = maxval;
+ }
+
+ ok = try_tablejump (index_type, index_expr, minval, range,
+ table_label, default_label);
+ gcc_assert (ok);
+ }
+
+ /* Get table of labels to jump to, in order of case index. */
+
+ ncases = tree_low_cst (range, 0) + 1;
+ labelvec = XALLOCAVEC (rtx, ncases);
+ memset (labelvec, 0, ncases * sizeof (rtx));
+
+ for (n = case_list; n; n = n->right)
+ {
+ /* Compute the low and high bounds relative to the minimum
+ value since that should fit in a HOST_WIDE_INT while the
+ actual values may not. */
+ HOST_WIDE_INT i_low
+ = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
+ n->low, minval), 1);
+ HOST_WIDE_INT i_high
+ = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
+ n->high, minval), 1);
+ HOST_WIDE_INT i;
+
+ for (i = i_low; i <= i_high; i ++)
+ labelvec[i]
+ = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
+ }
+
+ /* Fill in the gaps with the default. We may have gaps at
+ the beginning if we tried to avoid the minval subtraction,
+ so substitute some label even if the default label was
+ deemed unreachable. */
+ if (!default_label)
+ default_label = fallback_label;
+ for (i = 0; i < ncases; i++)
+ if (labelvec[i] == 0)
+ labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
+
+ /* Output the table. */
+ emit_label (table_label);
+
+ if (CASE_VECTOR_PC_RELATIVE || flag_pic)
+ emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
+ gen_rtx_LABEL_REF (Pmode, table_label),
+ gen_rtvec_v (ncases, labelvec),
+ const0_rtx, const0_rtx));
+ else
+ emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
+ gen_rtvec_v (ncases, labelvec)));
+
+ /* Record no drop-through after the table. */
+ emit_barrier ();
}
/* Terminate a case (Pascal/Ada) or switch (C) statement
expand_case (gimple stmt)
{
tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
- rtx default_label = 0;
- struct case_node *n;
+ rtx default_label = NULL_RTX;
unsigned int count, uniq;
- rtx index;
- rtx table_label;
- int ncases;
- rtx *labelvec;
int i;
- rtx before_case, end, lab;
-
+ int ncases = gimple_switch_num_labels (stmt);
tree index_expr = gimple_switch_index (stmt);
tree index_type = TREE_TYPE (index_expr);
- int unsignedp = TYPE_UNSIGNED (index_type);
-
- /* The insn after which the case dispatch should finally
- be emitted. Zero for a dummy. */
- rtx start;
+ tree elt;
/* A list of case labels; it is first built as a list and it may then
be rearranged into a nearly balanced binary tree. */
struct case_node *case_list = 0;
- /* Label to jump to if no case matches. */
- tree default_label_decl = NULL_TREE;
-
- alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
- sizeof (struct case_node),
- 100);
-
- do_pending_stack_adjust ();
-
- /* An ERROR_MARK occurs for various reasons including invalid data type. */
- if (index_type != error_mark_node)
- {
- tree elt;
- bitmap label_bitmap;
- int stopi = 0;
-
- /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
- expressions being INTEGER_CST. */
- gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
-
- /* The default case, if ever taken, is the first element. */
- elt = gimple_switch_label (stmt, 0);
- if (!CASE_LOW (elt) && !CASE_HIGH (elt))
- {
- default_label_decl = CASE_LABEL (elt);
- stopi = 1;
- }
-
- for (i = gimple_switch_num_labels (stmt) - 1; i >= stopi; --i)
- {
- tree low, high;
- elt = gimple_switch_label (stmt, i);
-
- low = CASE_LOW (elt);
- gcc_assert (low);
- high = CASE_HIGH (elt);
-
- /* Discard empty ranges. */
- if (high && tree_int_cst_lt (high, low))
- continue;
-
- case_list = add_case_node (case_list, index_type, low, high,
- CASE_LABEL (elt), case_node_pool);
- }
-
-
- before_case = start = get_last_insn ();
- if (default_label_decl)
- default_label = label_rtx (default_label_decl);
-
- /* Get upper and lower bounds of case values. */
-
- uniq = 0;
- count = 0;
- label_bitmap = BITMAP_ALLOC (NULL);
- for (n = case_list; n; n = n->right)
- {
- /* Count the elements and track the largest and smallest
- of them (treating them as signed even if they are not). */
- if (count++ == 0)
- {
- minval = n->low;
- maxval = n->high;
- }
- else
- {
- if (tree_int_cst_lt (n->low, minval))
- minval = n->low;
- if (tree_int_cst_lt (maxval, n->high))
- maxval = n->high;
- }
- /* A range counts double, since it requires two compares. */
- if (! tree_int_cst_equal (n->low, n->high))
- count++;
-
- /* If we have not seen this label yet, then increase the
- number of unique case node targets seen. */
- lab = label_rtx (n->code_label);
- if (bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab)))
- uniq++;
- }
-
- BITMAP_FREE (label_bitmap);
-
- /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
- destination, such as one with a default case only. However,
- it doesn't remove cases that are out of range for the switch
- type, so we may still get a zero here. */
- if (count == 0)
- {
- if (default_label)
- emit_jump (default_label);
- free_alloc_pool (case_node_pool);
- return;
- }
-
- /* Compute span of values. */
- range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
-
- /* Try implementing this switch statement by a short sequence of
- bit-wise comparisons. However, we let the binary-tree case
- below handle constant index expressions. */
- if (expand_switch_using_bit_tests_p (index_expr, range, uniq, count))
- {
- /* Optimize the case where all the case values fit in a
- word without having to subtract MINVAL. In this case,
- we can optimize away the subtraction. */
- if (compare_tree_int (minval, 0) > 0
- && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
- {
- minval = build_int_cst (index_type, 0);
- range = maxval;
- }
- emit_case_bit_tests (index_type, index_expr, minval, range,
- case_list, default_label);
- }
-
- /* If range of values is much bigger than number of values,
- make a sequence of conditional branches instead of a dispatch.
- If the switch-index is a constant, do it this way
- because we can optimize it. */
-
- else if (count < case_values_threshold ()
- || compare_tree_int (range,
- (optimize_insn_for_size_p () ? 3 : 10) * count) > 0
- /* RANGE may be signed, and really large ranges will show up
- as negative numbers. */
- || compare_tree_int (range, 0) < 0
-#ifndef ASM_OUTPUT_ADDR_DIFF_ELT
- || flag_pic
-#endif
- || !flag_jump_tables
- || TREE_CONSTANT (index_expr)
- /* If neither casesi or tablejump is available, we can
- only go this way. */
- || (!HAVE_casesi && !HAVE_tablejump))
- {
- index = expand_normal (index_expr);
-
- /* If the index is a short or char that we do not have
- an insn to handle comparisons directly, convert it to
- a full integer now, rather than letting each comparison
- generate the conversion. */
-
- if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
- && ! have_insn_for (COMPARE, GET_MODE (index)))
- {
- enum machine_mode wider_mode;
- for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
- wider_mode = GET_MODE_WIDER_MODE (wider_mode))
- if (have_insn_for (COMPARE, wider_mode))
- {
- index = convert_to_mode (wider_mode, index, unsignedp);
- break;
- }
- }
-
- do_pending_stack_adjust ();
+ /* A pool for case nodes. */
+ alloc_pool case_node_pool;
- if (MEM_P (index))
- index = copy_to_reg (index);
-
- /* We generate a binary decision tree to select the
- appropriate target code. This is done as follows:
+ /* An ERROR_MARK occurs for various reasons including invalid data type.
+ ??? Can this still happen, with GIMPLE and all? */
+ if (index_type == error_mark_node)
+ return;
- The list of cases is rearranged into a binary tree,
- nearly optimal assuming equal probability for each case.
+ /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
+ expressions being INTEGER_CST. */
+ gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
+
+ case_node_pool = create_alloc_pool ("struct case_node pool",
+ sizeof (struct case_node),
+ 100);
- The tree is transformed into RTL, eliminating
- redundant test conditions at the same time.
+ do_pending_stack_adjust ();
- If program flow could reach the end of the
- decision tree an unconditional jump to the
- default code is emitted. */
+ /* Find the default case target label. */
+ default_label = label_rtx (CASE_LABEL (gimple_switch_default_label (stmt)));
- use_cost_table = estimate_case_costs (case_list);
- balance_case_nodes (&case_list, NULL);
- emit_case_nodes (index, case_list, default_label, index_type);
- if (default_label)
- emit_jump (default_label);
- }
- else
- {
- rtx fallback_label = label_rtx (case_list->code_label);
- table_label = gen_label_rtx ();
- if (! try_casesi (index_type, index_expr, minval, range,
- table_label, default_label, fallback_label))
- {
- bool ok;
+ /* Get upper and lower bounds of case values. */
+ elt = gimple_switch_label (stmt, 1);
+ minval = fold_convert (index_type, CASE_LOW (elt));
+ elt = gimple_switch_label (stmt, ncases - 1);
+ if (CASE_HIGH (elt))
+ maxval = fold_convert (index_type, CASE_HIGH (elt));
+ else
+ maxval = fold_convert (index_type, CASE_LOW (elt));
- /* Index jumptables from zero for suitable values of
- minval to avoid a subtraction. */
- if (optimize_insn_for_speed_p ()
- && compare_tree_int (minval, 0) > 0
- && compare_tree_int (minval, 3) < 0)
- {
- minval = build_int_cst (index_type, 0);
- range = maxval;
- }
+ /* Compute span of values. */
+ range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
- ok = try_tablejump (index_type, index_expr, minval, range,
- table_label, default_label);
- gcc_assert (ok);
- }
+ /* Listify the labels queue and gather some numbers to decide
+ how to expand this switch(). */
+ uniq = 0;
+ count = 0;
+ struct pointer_set_t *seen_labels = pointer_set_create ();
+ for (i = gimple_switch_num_labels (stmt) - 1; i >= 1; --i)
+ {
+ elt = gimple_switch_label (stmt, i);
+ tree low = CASE_LOW (elt);
+ gcc_assert (low);
+ tree high = CASE_HIGH (elt);
+ gcc_assert (! high || tree_int_cst_lt (low, high));
+ tree lab = CASE_LABEL (elt);
+
+ /* Count the elements.
+ A range counts double, since it requires two compares. */
+ count++;
+ if (high)
+ count++;
+
+ /* If we have not seen this label yet, then increase the
+ number of unique case node targets seen. */
+ if (!pointer_set_insert (seen_labels, lab))
+ uniq++;
+
+ /* The bounds on the case range, LOW and HIGH, have to be converted
+ to case's index type TYPE. Note that the original type of the
+ case index in the source code is usually "lost" during
+ gimplification due to type promotion, but the case labels retain the
+ original type. Make sure to drop overflow flags. */
+ low = fold_convert (index_type, low);
+ if (TREE_OVERFLOW (low))
+ low = build_int_cst_wide (index_type,
+ TREE_INT_CST_LOW (low),
+ TREE_INT_CST_HIGH (low));
+
+ /* The canonical from of a case label in GIMPLE is that a simple case
+ has an empty CASE_HIGH. For the casesi and tablejump expanders,
+ the back ends want simple cases to have high == low. */
+ if (! high)
+ high = low;
+ high = fold_convert (index_type, high);
+ if (TREE_OVERFLOW (high))
+ high = build_int_cst_wide (index_type,
+ TREE_INT_CST_LOW (high),
+ TREE_INT_CST_HIGH (high));
+
+ case_list = add_case_node (case_list, low, high, lab,
+ case_node_pool);
+ }
+ pointer_set_destroy (seen_labels);
- /* Get table of labels to jump to, in order of case index. */
+ /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
+ destination, such as one with a default case only.
+ It also removes cases that are out of range for the switch
+ type, so we should never get a zero here. */
+ gcc_assert (count > 0);
- ncases = tree_low_cst (range, 0) + 1;
- labelvec = XALLOCAVEC (rtx, ncases);
- memset (labelvec, 0, ncases * sizeof (rtx));
+ rtx before_case = get_last_insn ();
- for (n = case_list; n; n = n->right)
- {
- /* Compute the low and high bounds relative to the minimum
- value since that should fit in a HOST_WIDE_INT while the
- actual values may not. */
- HOST_WIDE_INT i_low
- = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
- n->low, minval), 1);
- HOST_WIDE_INT i_high
- = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
- n->high, minval), 1);
- HOST_WIDE_INT i;
-
- for (i = i_low; i <= i_high; i ++)
- labelvec[i]
- = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
- }
+ /* Decide how to expand this switch.
+ The two options at this point are a dispatch table (casesi or
+ tablejump) or a decision tree. */
- /* Fill in the gaps with the default. We may have gaps at
- the beginning if we tried to avoid the minval subtraction,
- so substitute some label even if the default label was
- deemed unreachable. */
- if (!default_label)
- default_label = fallback_label;
- for (i = 0; i < ncases; i++)
- if (labelvec[i] == 0)
- labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
-
- /* Output the table. */
- emit_label (table_label);
-
- if (CASE_VECTOR_PC_RELATIVE || flag_pic)
- emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
- gen_rtx_LABEL_REF (Pmode, table_label),
- gen_rtvec_v (ncases, labelvec),
- const0_rtx, const0_rtx));
- else
- emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
- gen_rtvec_v (ncases, labelvec)));
+ if (expand_switch_as_decision_tree_p (range, uniq, count))
+ emit_case_decision_tree (index_expr, index_type,
+ case_list, default_label);
+ else
+ emit_case_dispatch_table (index_expr, index_type,
+ case_list, default_label,
+ minval, maxval, range);
- /* Record no drop-through after the table. */
- emit_barrier ();
- }
-
- before_case = NEXT_INSN (before_case);
- end = get_last_insn ();
- reorder_insns (before_case, end, start);
- }
+ reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
free_temp_slots ();
free_alloc_pool (case_node_pool);
}
-/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */
+/* Expand the dispatch to a short decrement chain if there are few cases
+ to dispatch to. Likewise if neither casesi nor tablejump is available,
+ or if flag_jump_tables is set. Otherwise, expand as a casesi or a
+ tablejump. The index mode is always the mode of integer_type_node.
+ Trap if no case matches the index.
-static void
-do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label,
- int unsignedp)
-{
- do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
- NULL_RTX, NULL_RTX, label, -1);
-}
-\f
-/* Not all case values are encountered equally. This function
- uses a heuristic to weight case labels, in cases where that
- looks like a reasonable thing to do.
+ DISPATCH_INDEX is the index expression to switch on. It should be a
+ memory or register operand.
+
+ DISPATCH_TABLE is a set of case labels. The set should be sorted in
+ ascending order, be contiguous, starting with value 0, and contain only
+ single-valued case labels. */
- Right now, all we try to guess is text, and we establish the
- following weights:
+void
+expand_sjlj_dispatch_table (rtx dispatch_index,
+ VEC(tree,heap) *dispatch_table)
+{
+ tree index_type = integer_type_node;
+ enum machine_mode index_mode = TYPE_MODE (index_type);
- chars above space: 16
- digits: 16
- default: 12
- space, punct: 8
- tab: 4
- newline: 2
- other "\" chars: 1
- remaining chars: 0
+ int ncases = VEC_length (tree, dispatch_table);
- If we find any cases in the switch that are not either -1 or in the range
- of valid ASCII characters, or are control characters other than those
- commonly used with "\", don't treat this switch scanning text.
+ do_pending_stack_adjust ();
+ rtx before_case = get_last_insn ();
+
+ /* Expand as a decrement-chain if there are 5 or fewer dispatch
+ labels. This covers more than 98% of the cases in libjava,
+ and seems to be a reasonable compromise between the "old way"
+ of expanding as a decision tree or dispatch table vs. the "new
+ way" with decrement chain or dispatch table. */
+ if (VEC_length (tree, dispatch_table) <= 5
+ || (!HAVE_casesi && !HAVE_tablejump)
+ || !flag_jump_tables)
+ {
+ /* Expand the dispatch as a decrement chain:
- Return 1 if these nodes are suitable for cost estimation, otherwise
- return 0. */
+ "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
-static int
-estimate_case_costs (case_node_ptr node)
-{
- tree min_ascii = integer_minus_one_node;
- tree max_ascii = build_int_cst (TREE_TYPE (node->high), 127);
- case_node_ptr n;
- int i;
+ ==>
- /* If we haven't already made the cost table, make it now. Note that the
- lower bound of the table is -1, not zero. */
+ if (index == 0) do_0; else index--;
+ if (index == 0) do_1; else index--;
+ ...
+ if (index == 0) do_N; else index--;
- if (! cost_table_initialized)
+ This is more efficient than a dispatch table on most machines.
+ The last "index--" is redundant but the code is trivially dead
+ and will be cleaned up by later passes. */
+ rtx index = copy_to_mode_reg (index_mode, dispatch_index);
+ rtx zero = CONST0_RTX (index_mode);
+ for (int i = 0; i < ncases; i++)
+ {
+ tree elt = VEC_index (tree, dispatch_table, i);
+ rtx lab = label_rtx (CASE_LABEL (elt));
+ do_jump_if_equal (index_mode, index, zero, lab, 0);
+ force_expand_binop (index_mode, sub_optab,
+ index, CONST1_RTX (index_mode),
+ index, 0, OPTAB_DIRECT);
+ }
+ }
+ else
{
- cost_table_initialized = 1;
-
- for (i = 0; i < 128; i++)
+ /* Similar to expand_case, but much simpler. */
+ struct case_node *case_list = 0;
+ alloc_pool case_node_pool = create_alloc_pool ("struct sjlj_case pool",
+ sizeof (struct case_node),
+ ncases);
+ tree index_expr = make_tree (index_type, dispatch_index);
+ tree minval = build_int_cst (index_type, 0);
+ tree maxval = CASE_LOW (VEC_last (tree, dispatch_table));
+ tree range = maxval;
+ rtx default_label = gen_label_rtx ();
+
+ for (int i = ncases - 1; i > 0; --i)
{
- if (ISALNUM (i))
- COST_TABLE (i) = 16;
- else if (ISPUNCT (i))
- COST_TABLE (i) = 8;
- else if (ISCNTRL (i))
- COST_TABLE (i) = -1;
+ tree elt = VEC_index (tree, dispatch_table, i);
+ tree low = CASE_LOW (elt);
+ tree lab = CASE_LABEL (elt);
+ case_list = add_case_node (case_list, low, low, lab, case_node_pool);
}
- COST_TABLE (' ') = 8;
- COST_TABLE ('\t') = 4;
- COST_TABLE ('\0') = 4;
- COST_TABLE ('\n') = 2;
- COST_TABLE ('\f') = 1;
- COST_TABLE ('\v') = 1;
- COST_TABLE ('\b') = 1;
+ emit_case_dispatch_table (index_expr, index_type,
+ case_list, default_label,
+ minval, maxval, range);
+ emit_label (default_label);
+ free_alloc_pool (case_node_pool);
}
- /* See if all the case expressions look like text. It is text if the
- constant is >= -1 and the highest constant is <= 127. Do all comparisons
- as signed arithmetic since we don't want to ever access cost_table with a
- value less than -1. Also check that none of the constants in a range
- are strange control characters. */
+ /* Dispatching something not handled? Trap! */
+ expand_builtin_trap ();
- for (n = node; n; n = n->right)
- {
- if (tree_int_cst_lt (n->low, min_ascii)
- || tree_int_cst_lt (max_ascii, n->high))
- return 0;
-
- for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low);
- i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++)
- if (COST_TABLE (i) < 0)
- return 0;
- }
+ reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
- /* All interesting values are within the range of interesting
- ASCII characters. */
- return 1;
+ free_temp_slots ();
}
+\f
/* Take an ordered list of case nodes
and transform them into a near optimal binary tree,
on the assumption that any target code selection value is as
np = *head;
if (np)
{
- int cost = 0;
int i = 0;
int ranges = 0;
case_node_ptr *npp;
while (np)
{
if (!tree_int_cst_equal (np->low, np->high))
- {
- ranges++;
- if (use_cost_table)
- cost += COST_TABLE (TREE_INT_CST_LOW (np->high));
- }
-
- if (use_cost_table)
- cost += COST_TABLE (TREE_INT_CST_LOW (np->low));
+ ranges++;
i++;
np = np->right;
/* Split this list if it is long enough for that to help. */
npp = head;
left = *npp;
- if (use_cost_table)
- {
- /* Find the place in the list that bisects the list's total cost,
- Here I gets half the total cost. */
- int n_moved = 0;
- i = (cost + 1) / 2;
- while (1)
- {
- /* Skip nodes while their cost does not reach that amount. */
- if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
- i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high));
- i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low));
- if (i <= 0)
- break;
- npp = &(*npp)->right;
- n_moved += 1;
- }
- if (n_moved == 0)
- {
- /* Leave this branch lopsided, but optimize left-hand
- side and fill in `parent' fields for right-hand side. */
- np = *head;
- np->parent = parent;
- balance_case_nodes (&np->left, np);
- for (; np->right; np = np->right)
- np->right->parent = np;
- return;
- }
- }
+
/* If there are just three nodes, split at the middle one. */
- else if (i == 3)
+ if (i == 3)
npp = &(*npp)->right;
else
{
projects / gcc.git / blobdiff