/* 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 Free Software Foundation, Inc.
+ 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
+ Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
/* This file handles the generation of rtl code from tree structure
above the level of expressions, using subroutines in exp*.c and emit-rtl.c.
#include "tm.h"
#include "rtl.h"
+#include "hard-reg-set.h"
#include "tree.h"
#include "tm_p.h"
#include "flags.h"
#include "insn-config.h"
#include "expr.h"
#include "libfuncs.h"
-#include "hard-reg-set.h"
#include "recog.h"
#include "machmode.h"
#include "toplev.h"
#include "optabs.h"
#include "target.h"
#include "regs.h"
+#include "alloc-pool.h"
\f
/* Functions and data structures for expanding case statements. */
For very small, suitable switch statements, we can generate a series
of simple bit test and branches instead. */
-struct case_node GTY(())
+struct case_node
{
struct case_node *left; /* Left son in binary tree */
struct case_node *right; /* Right son in binary tree; also node chain */
#define COST_TABLE(I) cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)]
\f
static int n_occurrences (int, const char *);
-static bool decl_conflicts_with_clobbers_p (tree, const HARD_REG_SET);
+static bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *);
static void expand_nl_goto_receiver (void);
static bool check_operand_nalternatives (tree, tree);
static bool check_unique_operand_names (tree, tree);
static char *resolve_operand_name_1 (char *, tree, tree);
static void expand_null_return_1 (void);
-static rtx shift_return_value (rtx);
static void expand_value_return (rtx);
-static void do_jump_if_equal (rtx, rtx, rtx, int);
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 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);
+ tree, tree, tree, alloc_pool);
\f
/* Return the rtx-label that corresponds to a LABEL_DECL,
else
p = cfun;
- p->expr->x_forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref,
- p->expr->x_forced_labels);
+ forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref, forced_labels);
return ref;
}
void
expand_computed_goto (tree exp)
{
- rtx x = expand_expr (exp, NULL_RTX, VOIDmode, 0);
+ rtx x = expand_normal (exp);
x = convert_memory_address (Pmode, x);
or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the
insn is volatile; don't optimize it. */
-void
-expand_asm (tree string, int vol)
+static void
+expand_asm_loc (tree string, int vol, location_t locus)
{
rtx body;
if (TREE_CODE (string) == ADDR_EXPR)
string = TREE_OPERAND (string, 0);
- body = gen_rtx_ASM_INPUT (VOIDmode,
- ggc_strdup (TREE_STRING_POINTER (string)));
+ body = gen_rtx_ASM_INPUT_loc (VOIDmode,
+ ggc_strdup (TREE_STRING_POINTER (string)),
+ locus);
MEM_VOLATILE_P (body) = vol;
*is_inout = (*p == '+');
/* Canonicalize the output constraint so that it begins with `='. */
- if (p != constraint || is_inout)
+ if (p != constraint || *is_inout)
{
char *buf;
size_t c_len = strlen (constraint);
if (p != constraint)
- warning ("output constraint %qc for operand %d "
+ warning (0, "output constraint %qc for operand %d "
"is not at the beginning",
*p, operand_num);
}
break;
- case 'V': case 'm': case 'o':
+ case 'V': case TARGET_MEM_CONSTRAINT: case 'o':
*allows_mem = true;
break;
}
break;
- case 'V': case 'm': case 'o':
+ case 'V': case TARGET_MEM_CONSTRAINT: case 'o':
*allows_mem = true;
break;
}
if (saw_match && !*allows_reg)
- warning ("matching constraint does not allow a register");
+ warning (0, "matching constraint does not allow a register");
return true;
}
+/* Return DECL iff there's an overlap between *REGS and DECL, where DECL
+ can be an asm-declared register. Called via walk_tree. */
+
+static tree
+decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED,
+ void *data)
+{
+ tree decl = *declp;
+ const HARD_REG_SET *regs = data;
+
+ if (TREE_CODE (decl) == VAR_DECL)
+ {
+ if (DECL_HARD_REGISTER (decl)
+ && REG_P (DECL_RTL (decl))
+ && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
+ {
+ rtx reg = DECL_RTL (decl);
+
+ if (overlaps_hard_reg_set_p (*regs, GET_MODE (reg), REGNO (reg)))
+ return decl;
+ }
+ walk_subtrees = 0;
+ }
+ else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL)
+ walk_subtrees = 0;
+ return NULL_TREE;
+}
+
+/* If there is an overlap between *REGS and DECL, return the first overlap
+ found. */
+tree
+tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs)
+{
+ return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL);
+}
+
/* Check for overlap between registers marked in CLOBBERED_REGS and
- anything inappropriate in DECL. Emit error and return TRUE for error,
- FALSE for ok. */
+ anything inappropriate in T. Emit error and return the register
+ variable definition for error, NULL_TREE for ok. */
static bool
-decl_conflicts_with_clobbers_p (tree decl, const HARD_REG_SET clobbered_regs)
+tree_conflicts_with_clobbers_p (tree t, HARD_REG_SET *clobbered_regs)
{
/* Conflicts between asm-declared register variables and the clobber
list are not allowed. */
- if ((TREE_CODE (decl) == VAR_DECL || TREE_CODE (decl) == PARM_DECL)
- && DECL_REGISTER (decl)
- && REG_P (DECL_RTL (decl))
- && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
+ tree overlap = tree_overlaps_hard_reg_set (t, clobbered_regs);
+
+ if (overlap)
{
- rtx reg = DECL_RTL (decl);
- unsigned int regno;
-
- for (regno = REGNO (reg);
- regno < (REGNO (reg)
- + hard_regno_nregs[REGNO (reg)][GET_MODE (reg)]);
- regno++)
- if (TEST_HARD_REG_BIT (clobbered_regs, regno))
- {
- error ("asm-specifier for variable %qs conflicts with "
- "asm clobber list",
- IDENTIFIER_POINTER (DECL_NAME (decl)));
-
- /* Reset registerness to stop multiple errors emitted for a
- single variable. */
- DECL_REGISTER (decl) = 0;
- return true;
- }
+ error ("asm-specifier for variable %qs conflicts with asm clobber list",
+ IDENTIFIER_POINTER (DECL_NAME (overlap)));
+
+ /* Reset registerness to stop multiple errors emitted for a single
+ variable. */
+ DECL_REGISTER (overlap) = 0;
+ return true;
}
+
return false;
}
STRING is the instruction template.
OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs.
Each output or input has an expression in the TREE_VALUE and
- and a tree list in TREE_PURPOSE which in turn contains a constraint
+ a tree list in TREE_PURPOSE which in turn contains a constraint
name in TREE_VALUE (or NULL_TREE) and a constraint string
in TREE_PURPOSE.
CLOBBERS is a list of STRING_CST nodes each naming a hard register
VOL nonzero means the insn is volatile; don't optimize it. */
-void
+static void
expand_asm_operands (tree string, tree outputs, tree inputs,
tree clobbers, int vol, location_t locus)
{
Case in point is when the i386 backend moved from cc0 to a hard reg --
maintaining source-level compatibility means automatically clobbering
the flags register. */
- clobbers = targetm.md_asm_clobbers (clobbers);
+ clobbers = targetm.md_asm_clobbers (outputs, inputs, clobbers);
/* Count the number of meaningful clobbered registers, ignoring what
we would ignore later. */
CLEAR_HARD_REG_SET (clobbered_regs);
for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
{
- const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
+ const char *regname;
+
+ if (TREE_VALUE (tail) == error_mark_node)
+ return;
+ regname = TREE_STRING_POINTER (TREE_VALUE (tail));
i = decode_reg_name (regname);
if (i >= 0 || i == -4)
inout_opnum[ninout++] = i;
}
- if (decl_conflicts_with_clobbers_p (val, clobbered_regs))
+ if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
clobber_conflict_found = 1;
}
val = TREE_VALUE (tail);
type = TREE_TYPE (val);
+ /* EXPAND_INITIALIZER will not generate code for valid initializer
+ constants, but will still generate code for other types of operand.
+ This is the behavior we want for constant constraints. */
op = expand_expr (val, NULL_RTX, VOIDmode,
- (allows_mem && !allows_reg
- ? EXPAND_MEMORY : EXPAND_NORMAL));
+ allows_reg ? EXPAND_NORMAL
+ : allows_mem ? EXPAND_MEMORY
+ : EXPAND_INITIALIZER);
/* Never pass a CONCAT to an ASM. */
if (GET_CODE (op) == CONCAT)
if (asm_operand_ok (op, constraint) <= 0)
{
- if (allows_reg)
+ if (allows_reg && TYPE_MODE (type) != BLKmode)
op = force_reg (TYPE_MODE (type), op);
else if (!allows_mem)
- warning ("asm operand %d probably doesn%'t match constraints",
+ warning (0, "asm operand %d probably doesn%'t match constraints",
i + noutputs);
else if (MEM_P (op))
{
}
else
{
- warning ("use of memory input without lvalue in "
+ warning (0, "use of memory input without lvalue in "
"asm operand %d is deprecated", i + noutputs);
if (CONSTANT_P (op))
= gen_rtx_ASM_INPUT (TYPE_MODE (type),
ggc_strdup (constraints[i + noutputs]));
- if (decl_conflicts_with_clobbers_p (val, clobbered_regs))
+ if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
clobber_conflict_found = 1;
}
if (real_output_rtx[i])
emit_move_insn (real_output_rtx[i], output_rtx[i]);
+ crtl->has_asm_statement = 1;
free_temp_slots ();
}
if (ASM_INPUT_P (exp))
{
- expand_asm (ASM_STRING (exp), ASM_VOLATILE_P (exp));
+ expand_asm_loc (ASM_STRING (exp), ASM_VOLATILE_P (exp), input_location);
return;
}
{
if (o[i] != TREE_VALUE (tail))
{
- expand_assignment (o[i], TREE_VALUE (tail));
+ expand_assignment (o[i], TREE_VALUE (tail), false);
free_temp_slots ();
/* Restore the original value so that it's correct the next
rtx value;
tree type;
- value = expand_expr (exp, const0_rtx, VOIDmode, 0);
+ value = expand_expr (exp, const0_rtx, VOIDmode, EXPAND_NORMAL);
+ if (GIMPLE_TUPLE_P (exp))
+ type = void_type_node;
+ else
type = TREE_TYPE (exp);
/* If all we do is reference a volatile value in memory,
/* Compare the value with itself to reference it. */
emit_cmp_and_jump_insns (value, value, EQ,
- expand_expr (TYPE_SIZE (type),
- NULL_RTX, VOIDmode, 0),
+ expand_normal (TYPE_SIZE (type)),
BLKmode, 0, lab);
emit_label (lab);
}
(potential) location of the expression. */
int
-warn_if_unused_value (tree exp, location_t locus)
+warn_if_unused_value (const_tree exp, location_t locus)
{
restart:
- if (TREE_USED (exp))
+ if (TREE_USED (exp) || TREE_NO_WARNING (exp))
return 0;
/* Don't warn about void constructs. This includes casting to void,
case PREDECREMENT_EXPR:
case POSTDECREMENT_EXPR:
case MODIFY_EXPR:
+ case GIMPLE_MODIFY_STMT:
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:
goto restart;
case COMPOUND_EXPR:
- if (TREE_NO_WARNING (exp))
- return 0;
if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus))
return 1;
/* Let people do `(foo (), 0)' without a warning. */
exp = TREE_OPERAND (exp, 1);
goto restart;
- case NOP_EXPR:
- case CONVERT_EXPR:
- case NON_LVALUE_EXPR:
- /* Don't warn about conversions not explicit in the user's program. */
- if (TREE_NO_WARNING (exp))
+ 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;
- /* Assignment to a cast usually results in a cast of a modify.
- Don't complain about that. There can be an arbitrary number of
- casts before the modify, so we must loop until we find the first
- non-cast expression and then test to see if that is a modify. */
- {
- tree tem = TREE_OPERAND (exp, 0);
-
- while (TREE_CODE (tem) == CONVERT_EXPR || TREE_CODE (tem) == NOP_EXPR)
- tem = TREE_OPERAND (tem, 0);
-
- if (TREE_CODE (tem) == MODIFY_EXPR || TREE_CODE (tem) == INIT_EXPR
- || TREE_CODE (tem) == CALL_EXPR)
- return 0;
- }
- goto maybe_warn;
+ goto warn;
case INDIRECT_REF:
/* Don't warn about automatic dereferencing of references, since
/* 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_CODE_LENGTH (TREE_CODE (exp)) == 0)
- return 0;
-
- maybe_warn:
- /* If this is an expression with side effects, don't warn. */
- if (TREE_SIDE_EFFECTS (exp))
+ if (EXPRESSION_CLASS_P (exp) && TREE_OPERAND_LENGTH (exp) == 0)
return 0;
- warning ("%Hvalue computed is not used", &locus);
+ warn:
+ warning (OPT_Wunused_value, "%Hvalue computed is not used", &locus);
return 1;
}
}
emit_jump (end_label);
}
-/* If the current function returns values in the most significant part
- of a register, shift return value VAL appropriately. The mode of
- the function's return type is known not to be BLKmode. */
-
-static rtx
-shift_return_value (rtx val)
-{
- tree type;
-
- type = TREE_TYPE (DECL_RESULT (current_function_decl));
- if (targetm.calls.return_in_msb (type))
- {
- rtx target;
- HOST_WIDE_INT shift;
-
- target = DECL_RTL (DECL_RESULT (current_function_decl));
- shift = (GET_MODE_BITSIZE (GET_MODE (target))
- - BITS_PER_UNIT * int_size_in_bytes (type));
- if (shift > 0)
- val = expand_shift (LSHIFT_EXPR, GET_MODE (target),
- gen_lowpart (GET_MODE (target), val),
- build_int_cst (NULL_TREE, shift), target, 1);
- }
- return val;
-}
-
-
/* Generate RTL to return from the current function, with value VAL. */
static void
static void
expand_null_return_1 (void)
{
- rtx end_label;
-
clear_pending_stack_adjust ();
do_pending_stack_adjust ();
-
- end_label = return_label;
- if (end_label == 0)
- end_label = return_label = gen_label_rtx ();
- emit_jump (end_label);
+ emit_jump (return_label);
}
\f
/* Generate RTL to evaluate the expression RETVAL and return it
/* If function wants no value, give it none. */
if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE)
{
- expand_expr (retval, NULL_RTX, VOIDmode, 0);
+ expand_normal (retval);
expand_null_return ();
return;
}
expand_null_return ();
return;
}
- else if ((TREE_CODE (retval) == MODIFY_EXPR
+ else if ((TREE_CODE (retval) == GIMPLE_MODIFY_STMT
|| TREE_CODE (retval) == INIT_EXPR)
- && TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL)
- retval_rhs = TREE_OPERAND (retval, 1);
+ && TREE_CODE (GENERIC_TREE_OPERAND (retval, 0)) == RESULT_DECL)
+ retval_rhs = GENERIC_TREE_OPERAND (retval, 1);
else
retval_rhs = retval;
(and in expand_call). */
else if (retval_rhs != 0
- && TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode
+ && TYPE_MODE (GENERIC_TREE_TYPE (retval_rhs)) == BLKmode
&& REG_P (result_rtl))
{
int i;
= MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)), BITS_PER_WORD);
rtx *result_pseudos = alloca (sizeof (rtx) * n_regs);
rtx result_reg, src = NULL_RTX, dst = NULL_RTX;
- rtx result_val = expand_expr (retval_rhs, NULL_RTX, VOIDmode, 0);
+ rtx result_val = expand_normal (retval_rhs);
enum machine_mode tmpmode, result_reg_mode;
if (bytes == 0)
tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST);
val = assign_temp (nt, 0, 0, 1);
- val = expand_expr (retval_rhs, val, GET_MODE (val), 0);
+ val = expand_expr (retval_rhs, val, GET_MODE (val), EXPAND_NORMAL);
val = force_not_mem (val);
/* Return the calculated value. */
- expand_value_return (shift_return_value (val));
+ expand_value_return (val);
}
else
{
/* No hard reg used; calculate value into hard return reg. */
- expand_expr (retval, const0_rtx, VOIDmode, 0);
+ expand_expr (retval, const0_rtx, VOIDmode, EXPAND_NORMAL);
expand_value_return (result_rtl);
}
}
*that* node in turn will point to the relevant FUNCTION_DECL node. */
int
-is_body_block (tree stmt)
+is_body_block (const_tree stmt)
{
if (lang_hooks.no_body_blocks)
return 0;
{
/* Clobber the FP when we get here, so we have to make sure it's
marked as used by this function. */
- emit_insn (gen_rtx_USE (VOIDmode, hard_frame_pointer_rtx));
+ emit_use (hard_frame_pointer_rtx);
/* Mark the static chain as clobbered here so life information
doesn't get messed up for it. */
- emit_insn (gen_rtx_CLOBBER (VOIDmode, static_chain_rtx));
+ emit_clobber (static_chain_rtx);
#ifdef HAVE_nonlocal_goto
if (! HAVE_nonlocal_goto)
/* Now restore our arg pointer from the address at which it
was saved in our stack frame. */
emit_move_insn (virtual_incoming_args_rtx,
- copy_to_reg (get_arg_pointer_save_area (cfun)));
+ copy_to_reg (get_arg_pointer_save_area ()));
}
}
#endif
emit_insn (gen_nonlocal_goto_receiver ());
#endif
- /* @@@ This is a kludge. Not all machine descriptions define a blockage
- insn, but we must not allow the code we just generated to be reordered
- by scheduling. Specifically, the update of the frame pointer must
- happen immediately, not later. So emit an ASM_INPUT to act as blockage
- insn. */
- emit_insn (gen_rtx_ASM_INPUT (VOIDmode, ""));
+ /* We must not allow the code we just generated to be reordered by
+ scheduling. Specifically, the update of the frame pointer must
+ happen immediately, not later. */
+ emit_insn (gen_blockage ());
}
\f
/* Generate RTL for the automatic variable declaration DECL.
/* Note if the object is a user variable. */
if (!DECL_ARTIFICIAL (decl))
- {
mark_user_reg (DECL_RTL (decl));
- /* Trust user variables which have a pointer type to really
- be pointers. Do not trust compiler generated temporaries
- as our type system is totally busted as it relates to
- pointer arithmetic which translates into lots of compiler
- generated objects with pointer types, but which are not really
- pointers. */
- if (POINTER_TYPE_P (type))
- mark_reg_pointer (DECL_RTL (decl),
- TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl))));
- }
+ if (POINTER_TYPE_P (type))
+ mark_reg_pointer (DECL_RTL (decl),
+ TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl))));
}
else if (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST
/* Compute the variable's size, in bytes. This will expand any
needed SAVE_EXPRs for the first time. */
- size = expand_expr (DECL_SIZE_UNIT (decl), NULL_RTX, VOIDmode, 0);
+ size = expand_normal (DECL_SIZE_UNIT (decl));
free_temp_slots ();
/* Allocate space on the stack for the variable. Note that
void
expand_stack_restore (tree var)
{
- rtx sa = DECL_RTL (var);
+ rtx sa = expand_normal (var);
+ sa = convert_memory_address (Pmode, sa);
emit_stack_restore (SAVE_BLOCK, sa, NULL_RTX);
}
\f
static struct case_node *
add_case_node (struct case_node *head, tree type, tree low, tree high,
- tree label)
+ tree label, alloc_pool case_node_pool)
{
tree min_value, max_value;
struct case_node *r;
}
- /* Add this label to the chain. */
- r = ggc_alloc (sizeof (struct case_node));
- r->low = low;
- r->high = high;
+ /* Add this label to the chain. Make sure to drop overflow flags. */
+ 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->code_label = label;
r->parent = r->left = NULL;
r->right = head;
/* By default, enable case bit tests on targets with ashlsi3. */
#ifndef CASE_USE_BIT_TESTS
-#define CASE_USE_BIT_TESTS (ashl_optab->handlers[word_mode].insn_code \
+#define CASE_USE_BIT_TESTS (optab_handler (ashl_optab, word_mode)->insn_code \
!= CODE_FOR_nothing)
#endif
const struct case_bit_test *d1 = p1;
const struct case_bit_test *d2 = p2;
- return d2->bits - d1->bits;
+ if (d2->bits != d1->bits)
+ return d2->bits - d1->bits;
+
+ /* Stabilize the sort. */
+ return CODE_LABEL_NUMBER (d2->label) - CODE_LABEL_NUMBER (d1->label);
}
/* Expand a switch statement by a short sequence of bit-wise
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);
+ 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);
qsort (test, count, sizeof(*test), case_bit_test_cmp);
- index_expr = fold (build2 (MINUS_EXPR, index_type,
- convert (index_type, index_expr),
- convert (index_type, minval)));
- index = expand_expr (index_expr, NULL_RTX, VOIDmode, 0);
+ 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_expr (range, NULL_RTX, VOIDmode, 0);
- emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
- default_label);
+ expr = expand_normal (range);
+ if (default_label)
+ emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
+ default_label);
index = convert_to_mode (word_mode, index, 0);
index = expand_binop (word_mode, ashl_optab, const1_rtx,
word_mode, 1, test[i].label);
}
- emit_jump (default_label);
+ if (default_label)
+ emit_jump (default_label);
}
#ifndef HAVE_casesi
#define HAVE_tablejump 0
#endif
-/* Terminate a case (Pascal) or switch (C) statement
+/* Terminate a case (Pascal/Ada) or switch (C) statement
in which ORIG_INDEX is the expression to be tested.
If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
type as given in the source before any compiler conversions.
{
tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
rtx default_label = 0;
- struct case_node *n, *m;
+ struct case_node *n;
unsigned int count, uniq;
rtx index;
rtx table_label;
int ncases;
rtx *labelvec;
- int i, fail;
+ int i;
rtx before_case, end, lab;
tree vec = SWITCH_LABELS (exp);
struct case_node *case_list = 0;
/* Label to jump to if no case matches. */
- tree default_label_decl;
+ tree default_label_decl = NULL_TREE;
+
+ alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
+ sizeof (struct case_node),
+ 100);
/* The switch body is lowered in gimplify.c, we should never have
switches with a non-NULL SWITCH_BODY here. */
if (index_type != error_mark_node)
{
tree elt;
+ bitmap label_bitmap;
+ int vl = TREE_VEC_LENGTH (vec);
- /* The default case is at the end of TREE_VEC. */
- elt = TREE_VEC_ELT (vec, TREE_VEC_LENGTH (vec) - 1);
- gcc_assert (!CASE_HIGH (elt));
- gcc_assert (!CASE_LOW (elt));
- default_label_decl = CASE_LABEL (elt);
+ /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
+ expressions being INTEGER_CST. */
+ gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
- for (i = TREE_VEC_LENGTH (vec) - 1; --i >= 0; )
+ /* The default case, if ever taken, is at the end of TREE_VEC. */
+ elt = TREE_VEC_ELT (vec, vl - 1);
+ if (!CASE_LOW (elt) && !CASE_HIGH (elt))
{
- elt = TREE_VEC_ELT (vec, i);
- gcc_assert (CASE_LOW (elt));
- case_list = add_case_node (case_list, index_type,
- CASE_LOW (elt), CASE_HIGH (elt),
- CASE_LABEL (elt));
+ default_label_decl = CASE_LABEL (elt);
+ --vl;
}
-
- /* Make sure start points to something that won't need any
- transformation before the end of this function. */
- start = get_last_insn ();
- if (! NOTE_P (start))
+ for (i = vl - 1; i >= 0; --i)
{
- emit_note (NOTE_INSN_DELETED);
- start = get_last_insn ();
+ tree low, high;
+ elt = TREE_VEC_ELT (vec, 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);
}
- default_label = label_rtx (default_label_decl);
- before_case = get_last_insn ();
+ 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
}
else
{
- if (INT_CST_LT (n->low, minval))
+ if (tree_int_cst_lt (n->low, minval))
minval = n->low;
- if (INT_CST_LT (maxval, n->high))
+ 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++;
- /* Count the number of unique case node targets. */
- uniq++;
+ /* If we have not seen this label yet, then increase the
+ number of unique case node targets seen. */
lab = label_rtx (n->code_label);
- for (m = case_list; m != n; m = m->right)
- if (label_rtx (m->code_label) == lab)
- {
- uniq--;
- break;
- }
+ if (!bitmap_bit_p (label_bitmap, CODE_LABEL_NUMBER (lab)))
+ {
+ bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab));
+ uniq++;
+ }
}
- /* Compute span of values. */
- if (count != 0)
- range = fold (build2 (MINUS_EXPR, index_type, maxval, minval));
+ 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)
{
- expand_expr (index_expr, const0_rtx, VOIDmode, 0);
- emit_jump (default_label);
+ 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. */
- else if (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)))
+ if (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)))
{
/* Optimize the case where all the case values fit in a
word without having to subtract MINVAL. In this case,
if (compare_tree_int (minval, 0) > 0
&& compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
{
- minval = integer_zero_node;
+ minval = build_int_cst (index_type, 0);
range = maxval;
}
emit_case_bit_tests (index_type, index_expr, minval, range,
#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_expr (index_expr, NULL_RTX, VOIDmode, 0);
+ 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
if (MEM_P (index))
index = copy_to_reg (index);
- if (GET_CODE (index) == CONST_INT
- || TREE_CODE (index_expr) == INTEGER_CST)
- {
- /* Make a tree node with the proper constant value
- if we don't already have one. */
- if (TREE_CODE (index_expr) != INTEGER_CST)
- {
- index_expr
- = build_int_cst_wide (NULL_TREE, INTVAL (index),
- unsignedp || INTVAL (index) >= 0
- ? 0 : -1);
- index_expr = convert (index_type, index_expr);
- }
- /* For constant index expressions we need only
- issue an unconditional branch to the appropriate
- target code. The job of removing any unreachable
- code is left to the optimization phase if the
- "-O" option is specified. */
- for (n = case_list; n; n = n->right)
- if (! tree_int_cst_lt (index_expr, n->low)
- && ! tree_int_cst_lt (n->high, index_expr))
- break;
-
- if (n)
- emit_jump (label_rtx (n->code_label));
- else
- emit_jump (default_label);
- }
- else
- {
- /* If the index expression is not constant we generate
- a binary decision tree to select the appropriate
- target code. This is done as follows:
-
- The list of cases is rearranged into a binary tree,
- nearly optimal assuming equal probability for each case.
-
- The tree is transformed into RTL, eliminating
- redundant test conditions at the same time.
-
- If program flow could reach the end of the
- decision tree an unconditional jump to the
- default code is emitted. */
-
- use_cost_table
- = (TREE_CODE (orig_type) != ENUMERAL_TYPE
- && estimate_case_costs (case_list));
- balance_case_nodes (&case_list, NULL);
- emit_case_nodes (index, case_list, default_label, index_type);
- emit_jump (default_label);
- }
+ /* We generate a binary decision tree to select the
+ appropriate target code. This is done as follows:
+
+ The list of cases is rearranged into a binary tree,
+ nearly optimal assuming equal probability for each case.
+
+ The tree is transformed into RTL, eliminating
+ redundant test conditions at the same time.
+
+ If program flow could reach the end of the
+ decision tree an unconditional jump to the
+ default code is emitted. */
+
+ use_cost_table
+ = (TREE_CODE (orig_type) != ENUMERAL_TYPE
+ && 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))
+ table_label, default_label, fallback_label))
{
bool ok;
- index_type = integer_type_node;
/* Index jumptables from zero for suitable values of
minval to avoid a subtraction. */
&& compare_tree_int (minval, 0) > 0
&& compare_tree_int (minval, 3) < 0)
{
- minval = integer_zero_node;
+ minval = build_int_cst (index_type, 0);
range = maxval;
}
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);
+ = 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);
+ = 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 ++)
= gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
}
- /* Fill in the gaps with the default. */
+ /* 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);
emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
gen_rtvec_v (ncases, labelvec)));
- /* If the case insn drops through the table,
- after the table we must jump to the default-label.
- Otherwise record no drop-through after the table. */
-#ifdef CASE_DROPS_THROUGH
- emit_jump (default_label);
-#else
+ /* Record no drop-through after the table. */
emit_barrier ();
-#endif
}
before_case = NEXT_INSN (before_case);
end = get_last_insn ();
- fail = squeeze_notes (&before_case, &end);
- gcc_assert (!fail);
reorder_insns (before_case, end, start);
}
free_temp_slots ();
+ free_alloc_pool (case_node_pool);
}
-/* Generate code to jump to LABEL if OP1 and OP2 are equal. */
+/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */
static void
-do_jump_if_equal (rtx op1, rtx op2, rtx label, int unsignedp)
+do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label,
+ int unsignedp)
{
- if (GET_CODE (op1) == CONST_INT && GET_CODE (op2) == CONST_INT)
- {
- if (op1 == op2)
- emit_jump (label);
- }
- else
- emit_cmp_and_jump_insns (op1, op2, EQ, NULL_RTX,
- (GET_MODE (op1) == VOIDmode
- ? GET_MODE (op2) : GET_MODE (op1)),
- unsignedp, label);
+ do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
+ NULL_RTX, NULL_RTX, label);
}
\f
/* Not all case values are encountered equally. This function
estimate_case_costs (case_node_ptr node)
{
tree min_ascii = integer_minus_one_node;
- tree max_ascii = convert (TREE_TYPE (node->high),
- build_int_cst (NULL_TREE, 127));
+ tree max_ascii = build_int_cst (TREE_TYPE (node->high), 127);
case_node_ptr n;
int i;
for (n = node; n; n = n->right)
{
- if ((INT_CST_LT (n->low, min_ascii)) || INT_CST_LT (max_ascii, n->high))
+ 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);
if (node->left)
return 0;
- low_minus_one = fold (build2 (MINUS_EXPR, TREE_TYPE (node->low),
- node->low, integer_one_node));
+ low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low),
+ node->low,
+ build_int_cst (TREE_TYPE (node->low), 1));
/* If the subtraction above overflowed, we can't verify anything.
Otherwise, look for a parent that tests our value - 1. */
if (node->right)
return 0;
- high_plus_one = fold (build2 (PLUS_EXPR, TREE_TYPE (node->high),
- node->high, integer_one_node));
+ high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high),
+ node->high,
+ build_int_cst (TREE_TYPE (node->high), 1));
/* If the addition above overflowed, we can't verify anything.
Otherwise, look for a parent that tests our value + 1. */
enum machine_mode mode = GET_MODE (index);
enum machine_mode imode = TYPE_MODE (index_type);
+ /* Handle indices detected as constant during RTL expansion. */
+ if (mode == VOIDmode)
+ mode = imode;
+
/* See if our parents have already tested everything for us.
If they have, emit an unconditional jump for this node. */
if (node_is_bounded (node, index_type))
/* Node is single valued. First see if the index expression matches
this node and then check our children, if any. */
- do_jump_if_equal (index,
+ do_jump_if_equal (mode, index,
convert_modes (mode, imode,
- expand_expr (node->low, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->low),
unsignedp),
label_rtx (node->code_label), unsignedp);
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
- expand_expr (node->high, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->high),
unsignedp),
GT, NULL_RTX, mode, unsignedp,
label_rtx (node->right->code_label));
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
- expand_expr (node->high, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->high),
unsignedp),
LT, NULL_RTX, mode, unsignedp,
label_rtx (node->left->code_label));
/* See if the value matches what the right hand side
wants. */
- do_jump_if_equal (index,
+ do_jump_if_equal (mode, index,
convert_modes (mode, imode,
- expand_expr (node->right->low,
- NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->right->low),
unsignedp),
label_rtx (node->right->code_label),
unsignedp);
/* See if the value matches what the left hand side
wants. */
- do_jump_if_equal (index,
+ do_jump_if_equal (mode, index,
convert_modes (mode, imode,
- expand_expr (node->left->low,
- NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->left->low),
unsignedp),
label_rtx (node->left->code_label),
unsignedp);
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
- expand_expr (node->high, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->high),
unsignedp),
GT, NULL_RTX, mode, unsignedp,
label_rtx (test_label));
emit_case_nodes (index, node->left, default_label, index_type);
/* If left-hand subtree does nothing,
go to default. */
- emit_jump (default_label);
+ if (default_label)
+ emit_jump (default_label);
/* Code branches here for the right-hand subtree. */
expand_label (test_label);
else if (node->right != 0 && node->left == 0)
{
- /* Here we have a right child but no left so we issue conditional
+ /* Here we have a right child but no left so we issue a conditional
branch to default and process the right child.
- Omit the conditional branch to default if we it avoid only one
- right child; it costs too much space to save so little time. */
+ Omit the conditional branch to default if the right child
+ does not have any children and is single valued; it would
+ cost too much space to save so little time. */
if (node->right->right || node->right->left
|| !tree_int_cst_equal (node->right->low, node->right->high))
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
- expand_expr (node->high, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->high),
unsignedp),
LT, NULL_RTX, mode, unsignedp,
default_label);
/* We cannot process node->right normally
since we haven't ruled out the numbers less than
this node's value. So handle node->right explicitly. */
- do_jump_if_equal (index,
+ do_jump_if_equal (mode, index,
convert_modes
(mode, imode,
- expand_expr (node->right->low, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->right->low),
unsignedp),
label_rtx (node->right->code_label), unsignedp);
}
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
- expand_expr (node->high, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->high),
unsignedp),
GT, NULL_RTX, mode, unsignedp,
default_label);
/* We cannot process node->left normally
since we haven't ruled out the numbers less than
this node's value. So handle node->left explicitly. */
- do_jump_if_equal (index,
+ do_jump_if_equal (mode, index,
convert_modes
(mode, imode,
- expand_expr (node->left->low, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->left->low),
unsignedp),
label_rtx (node->left->code_label), unsignedp);
}
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
- expand_expr (node->high, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->high),
unsignedp),
GT, NULL_RTX, mode, unsignedp,
label_rtx (node->right->code_label));
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
- expand_expr (node->high, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->high),
unsignedp),
GT, NULL_RTX, mode, unsignedp,
label_rtx (test_label));
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
- expand_expr (node->low, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->low),
unsignedp),
GE, NULL_RTX, mode, unsignedp,
label_rtx (node->code_label));
{
/* If the left-hand subtree fell through,
don't let it fall into the right-hand subtree. */
- emit_jump (default_label);
+ if (default_label)
+ emit_jump (default_label);
expand_label (test_label);
emit_case_nodes (index, node->right, default_label, index_type);
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
- expand_expr (node->low, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->low),
unsignedp),
LT, NULL_RTX, mode, unsignedp,
default_label);
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
- expand_expr (node->high, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->high),
unsignedp),
LE, NULL_RTX, mode, unsignedp,
label_rtx (node->code_label));
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
- expand_expr (node->high, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->high),
unsignedp),
GT, NULL_RTX, mode, unsignedp,
default_label);
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
- expand_expr (node->low, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->low),
unsignedp),
GE, NULL_RTX, mode, unsignedp,
label_rtx (node->code_label));
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
- expand_expr (node->high, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->high),
unsignedp),
GT, NULL_RTX, mode, unsignedp,
default_label);
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
- expand_expr (node->low, NULL_RTX,
- VOIDmode, 0),
+ expand_normal (node->low),
unsignedp),
LT, NULL_RTX, mode, unsignedp,
default_label);
/* Instead of doing two branches, emit one unsigned branch for
(index-low) > (high-low). */
- low_rtx = expand_expr (low, NULL_RTX, mode, 0);
+ low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL);
new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
NULL_RTX, unsignedp,
OPTAB_WIDEN);
- new_bound = expand_expr (fold (build2 (MINUS_EXPR, type,
- high, low)),
- NULL_RTX, mode, 0);
+ new_bound = expand_expr (fold_build2 (MINUS_EXPR, type,
+ high, low),
+ NULL_RTX, mode, EXPAND_NORMAL);
emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
mode, 1, default_label);
OSDN Git Service
