#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "tree.h"
#include "tm_p.h"
#include "flags.h"
#include "except.h"
#include "function.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 "output.h"
#include "ggc.h"
#include "langhooks.h"
#include "predict.h"
#include "optabs.h"
#include "target.h"
#include "regs.h"
struct case_node GTY(())
{
struct case_node *left;
struct case_node *right;
struct case_node *parent;
tree low;
tree high;
tree code_label;
};
typedef struct case_node case_node;
typedef struct case_node *case_node_ptr;
static short cost_table_[129];
static int use_cost_table;
static int cost_table_initialized;
#define COST_TABLE(I) cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)]
static int n_occurrences (int, const char *);
static bool decl_conflicts_with_clobbers_p (tree, const 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 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 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);
rtx
label_rtx (tree label)
{
gcc_assert (TREE_CODE (label) == LABEL_DECL);
if (!DECL_RTL_SET_P (label))
{
rtx r = gen_label_rtx ();
SET_DECL_RTL (label, r);
if (FORCED_LABEL (label) || DECL_NONLOCAL (label))
LABEL_PRESERVE_P (r) = 1;
}
return DECL_RTL (label);
}
rtx
force_label_rtx (tree label)
{
rtx ref = label_rtx (label);
tree function = decl_function_context (label);
struct function *p;
gcc_assert (function);
if (function != current_function_decl)
p = find_function_data (function);
else
p = cfun;
p->expr->x_forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref,
p->expr->x_forced_labels);
return ref;
}
void
emit_jump (rtx label)
{
do_pending_stack_adjust ();
emit_jump_insn (gen_jump (label));
emit_barrier ();
}
void
expand_computed_goto (tree exp)
{
rtx x = expand_expr (exp, NULL_RTX, VOIDmode, 0);
x = convert_memory_address (Pmode, x);
do_pending_stack_adjust ();
emit_indirect_jump (x);
}
void
expand_label (tree label)
{
rtx label_r = label_rtx (label);
do_pending_stack_adjust ();
emit_label (label_r);
if (DECL_NAME (label))
LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label));
if (DECL_NONLOCAL (label))
{
expand_nl_goto_receiver ();
nonlocal_goto_handler_labels
= gen_rtx_EXPR_LIST (VOIDmode, label_r,
nonlocal_goto_handler_labels);
}
if (FORCED_LABEL (label))
forced_labels = gen_rtx_EXPR_LIST (VOIDmode, label_r, forced_labels);
if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
maybe_set_first_label_num (label_r);
}
void
expand_goto (tree label)
{
#ifdef ENABLE_CHECKING
tree context = decl_function_context (label);
gcc_assert (!context || context == current_function_decl);
#endif
emit_jump (label_rtx (label));
}
static int
n_occurrences (int c, const char *s)
{
int n = 0;
while (*s)
n += (*s++ == c);
return n;
}
static void
expand_asm (tree string, int vol)
{
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)));
MEM_VOLATILE_P (body) = vol;
emit_insn (body);
}
bool
parse_output_constraint (const char **constraint_p, int operand_num,
int ninputs, int noutputs, bool *allows_mem,
bool *allows_reg, bool *is_inout)
{
const char *constraint = *constraint_p;
const char *p;
*allows_mem = false;
*allows_reg = false;
p = strchr (constraint, '=');
if (!p)
p = strchr (constraint, '+');
if (!p)
{
error ("output operand constraint lacks %<=%>");
return false;
}
*is_inout = (*p == '+');
if (p != constraint || *is_inout)
{
char *buf;
size_t c_len = strlen (constraint);
if (p != constraint)
warning ("output constraint %qc for operand %d "
"is not at the beginning",
*p, operand_num);
buf = alloca (c_len + 1);
strcpy (buf, constraint);
buf[p - constraint] = buf[0];
buf[0] = '=';
*constraint_p = ggc_alloc_string (buf, c_len);
constraint = *constraint_p;
}
for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p))
switch (*p)
{
case '+':
case '=':
error ("operand constraint contains incorrectly positioned "
"%<+%> or %<=%>");
return false;
case '%':
if (operand_num + 1 == ninputs + noutputs)
{
error ("%<%%%> constraint used with last operand");
return false;
}
break;
case 'V': case 'm': case 'o':
*allows_mem = true;
break;
case '?': case '!': case '*': case '&': case '#':
case 'E': case 'F': case 'G': case 'H':
case 's': case 'i': case 'n':
case 'I': case 'J': case 'K': case 'L': case 'M':
case 'N': case 'O': case 'P': case ',':
break;
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
case '[':
error ("matching constraint not valid in output operand");
return false;
case '<': case '>':
*allows_mem = true;
break;
case 'g': case 'X':
*allows_reg = true;
*allows_mem = true;
break;
case 'p': case 'r':
*allows_reg = true;
break;
default:
if (!ISALPHA (*p))
break;
if (REG_CLASS_FROM_CONSTRAINT (*p, p) != NO_REGS)
*allows_reg = true;
#ifdef EXTRA_CONSTRAINT_STR
else if (EXTRA_ADDRESS_CONSTRAINT (*p, p))
*allows_reg = true;
else if (EXTRA_MEMORY_CONSTRAINT (*p, p))
*allows_mem = true;
else
{
*allows_reg = true;
*allows_mem = true;
}
#endif
break;
}
return true;
}
bool
parse_input_constraint (const char **constraint_p, int input_num,
int ninputs, int noutputs, int ninout,
const char * const * constraints,
bool *allows_mem, bool *allows_reg)
{
const char *constraint = *constraint_p;
const char *orig_constraint = constraint;
size_t c_len = strlen (constraint);
size_t j;
bool saw_match = false;
*allows_mem = false;
*allows_reg = false;
for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
switch (constraint[j])
{
case '+': case '=': case '&':
if (constraint == orig_constraint)
{
error ("input operand constraint contains %qc", constraint[j]);
return false;
}
break;
case '%':
if (constraint == orig_constraint
&& input_num + 1 == ninputs - ninout)
{
error ("%<%%%> constraint used with last operand");
return false;
}
break;
case 'V': case 'm': case 'o':
*allows_mem = true;
break;
case '<': case '>':
case '?': case '!': case '*': case '#':
case 'E': case 'F': case 'G': case 'H':
case 's': case 'i': case 'n':
case 'I': case 'J': case 'K': case 'L': case 'M':
case 'N': case 'O': case 'P': case ',':
break;
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
{
char *end;
unsigned long match;
saw_match = true;
match = strtoul (constraint + j, &end, 10);
if (match >= (unsigned long) noutputs)
{
error ("matching constraint references invalid operand number");
return false;
}
if (*end == '\0'
&& (j == 0 || (j == 1 && constraint[0] == '%')))
{
constraint = constraints[match];
*constraint_p = constraint;
c_len = strlen (constraint);
j = 0;
break;
}
else
j = end - constraint;
j--;
}
case 'p': case 'r':
*allows_reg = true;
break;
case 'g': case 'X':
*allows_reg = true;
*allows_mem = true;
break;
default:
if (! ISALPHA (constraint[j]))
{
error ("invalid punctuation %qc in constraint", constraint[j]);
return false;
}
if (REG_CLASS_FROM_CONSTRAINT (constraint[j], constraint + j)
!= NO_REGS)
*allows_reg = true;
#ifdef EXTRA_CONSTRAINT_STR
else if (EXTRA_ADDRESS_CONSTRAINT (constraint[j], constraint + j))
*allows_reg = true;
else if (EXTRA_MEMORY_CONSTRAINT (constraint[j], constraint + j))
*allows_mem = true;
else
{
*allows_reg = true;
*allows_mem = true;
}
#endif
break;
}
if (saw_match && !*allows_reg)
warning ("matching constraint does not allow a register");
return true;
}
static bool
decl_conflicts_with_clobbers_p (tree decl, const HARD_REG_SET clobbered_regs)
{
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)
{
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)));
DECL_REGISTER (decl) = 0;
return true;
}
}
return false;
}
static void
expand_asm_operands (tree string, tree outputs, tree inputs,
tree clobbers, int vol, tree uses, location_t locus)
{
rtvec argvec, constraintvec;
rtx body;
int ninputs = list_length (inputs);
int noutputs = list_length (outputs);
int ninout;
int nuses = 0;
int nclobbers;
HARD_REG_SET clobbered_regs;
int clobber_conflict_found = 0;
tree tail;
tree t;
int i;
rtx *output_rtx = alloca (noutputs * sizeof (rtx));
int *inout_opnum = alloca (noutputs * sizeof (int));
rtx *real_output_rtx = alloca (noutputs * sizeof (rtx));
enum machine_mode *inout_mode
= alloca (noutputs * sizeof (enum machine_mode));
const char **constraints
= alloca ((noutputs + ninputs) * sizeof (const char *));
int old_generating_concat_p = generating_concat_p;
if (noutputs == 0)
vol = 1;
if (! check_operand_nalternatives (outputs, inputs))
return;
string = resolve_asm_operand_names (string, outputs, inputs);
i = 0;
for (t = outputs; t ; t = TREE_CHAIN (t), i++)
constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
for (t = inputs; t ; t = TREE_CHAIN (t), i++)
constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
clobbers = targetm.md_asm_clobbers (clobbers);
nclobbers = 0;
CLEAR_HARD_REG_SET (clobbered_regs);
for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
{
const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
i = decode_reg_name (regname);
if (i >= 0 || i == -4)
++nclobbers;
else if (i == -2)
error ("unknown register name %qs in %<asm%>", regname);
if (i >= 0)
{
if (uses == NULL && flag_pic
#ifdef REAL_PIC_OFFSET_TABLE_REGNUM
&& i == REAL_PIC_OFFSET_TABLE_REGNUM
#else
&& i == (int)PIC_OFFSET_TABLE_REGNUM
#endif
)
{
error ("PIC register %qs clobbered in %<asm%>", regname);
return;
}
SET_HARD_REG_BIT (clobbered_regs, i);
}
}
ninout = 0;
for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
{
tree val = TREE_VALUE (tail);
tree type = TREE_TYPE (val);
const char *constraint;
bool is_inout;
bool allows_reg;
bool allows_mem;
if (type == error_mark_node)
return;
constraint = constraints[i];
if (!parse_output_constraint (&constraint, i, ninputs, noutputs,
&allows_mem, &allows_reg, &is_inout))
return;
if (! allows_reg
&& (allows_mem
|| is_inout
|| (DECL_P (val)
&& REG_P (DECL_RTL (val))
&& GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))))
lang_hooks.mark_addressable (val);
if (is_inout)
ninout++;
}
ninputs += ninout;
if (ninputs + noutputs > MAX_RECOG_OPERANDS)
{
error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS);
return;
}
for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail))
{
bool allows_reg, allows_mem;
const char *constraint;
if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node)
return;
constraint = constraints[i + noutputs];
if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
constraints, &allows_mem, &allows_reg))
return;
if (! allows_reg && allows_mem)
lang_hooks.mark_addressable (TREE_VALUE (tail));
}
ninout = 0;
for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
{
tree val = TREE_VALUE (tail);
tree type = TREE_TYPE (val);
bool is_inout;
bool allows_reg;
bool allows_mem;
rtx op;
bool ok;
ok = parse_output_constraint (&constraints[i], i, ninputs,
noutputs, &allows_mem, &allows_reg,
&is_inout);
gcc_assert (ok);
generating_concat_p = 0;
real_output_rtx[i] = NULL_RTX;
if ((TREE_CODE (val) == INDIRECT_REF
&& allows_mem)
|| (DECL_P (val)
&& (allows_mem || REG_P (DECL_RTL (val)))
&& ! (REG_P (DECL_RTL (val))
&& GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))
|| ! allows_reg
|| is_inout)
{
op = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE);
if (MEM_P (op))
op = validize_mem (op);
if (! allows_reg && !MEM_P (op))
error ("output number %d not directly addressable", i);
if ((! allows_mem && MEM_P (op))
|| GET_CODE (op) == CONCAT)
{
real_output_rtx[i] = op;
op = gen_reg_rtx (GET_MODE (op));
if (is_inout)
emit_move_insn (op, real_output_rtx[i]);
}
}
else
{
op = assign_temp (type, 0, 0, 1);
op = validize_mem (op);
TREE_VALUE (tail) = make_tree (type, op);
}
output_rtx[i] = op;
generating_concat_p = old_generating_concat_p;
if (is_inout)
{
inout_mode[ninout] = TYPE_MODE (type);
inout_opnum[ninout++] = i;
}
if (decl_conflicts_with_clobbers_p (val, clobbered_regs))
clobber_conflict_found = 1;
}
argvec = rtvec_alloc (ninputs);
constraintvec = rtvec_alloc (ninputs);
body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode
: GET_MODE (output_rtx[0])),
ggc_strdup (TREE_STRING_POINTER (string)),
empty_string, 0, argvec, constraintvec,
locus);
MEM_VOLATILE_P (body) = vol;
for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i)
{
bool allows_reg, allows_mem;
const char *constraint;
tree val, type;
rtx op;
bool ok;
constraint = constraints[i + noutputs];
ok = parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
constraints, &allows_mem, &allows_reg);
gcc_assert (ok);
generating_concat_p = 0;
val = TREE_VALUE (tail);
type = TREE_TYPE (val);
op = expand_expr (val, NULL_RTX, VOIDmode,
(allows_mem && !allows_reg
? EXPAND_MEMORY : EXPAND_NORMAL));
if (GET_CODE (op) == CONCAT)
op = force_reg (GET_MODE (op), op);
else if (MEM_P (op))
op = validize_mem (op);
if (asm_operand_ok (op, constraint) <= 0)
{
if (allows_reg)
op = force_reg (TYPE_MODE (type), op);
else if (!allows_mem)
warning ("asm operand %d probably doesn%'t match constraints",
i + noutputs);
else if (MEM_P (op))
{
}
else
{
warning ("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;
}
}
}
generating_concat_p = old_generating_concat_p;
ASM_OPERANDS_INPUT (body, i) = op;
if (i == 0 && !TREE_CHAIN (tail)
&& strcmp (TREE_STRING_POINTER (string), "%0:") == 0
&& GET_CODE (op) == SYMBOL_REF)
{
SYMBOL_REF_FLAGS (op) |= SYMBOL_FLAG_LOCAL;
SYMBOL_REF_FLAGS (op) &= ~SYMBOL_FLAG_EXTERNAL;
}
ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i)
= gen_rtx_ASM_INPUT (TYPE_MODE (type),
ggc_strdup (constraints[i + noutputs]));
if (decl_conflicts_with_clobbers_p (val, clobbered_regs))
clobber_conflict_found = 1;
}
generating_concat_p = 0;
for (i = 0; i < ninout; i++)
{
int j = inout_opnum[i];
char buffer[16];
ASM_OPERANDS_INPUT (body, ninputs - ninout + i)
= output_rtx[j];
sprintf (buffer, "%d", j);
ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i)
= gen_rtx_ASM_INPUT (inout_mode[i], ggc_strdup (buffer));
}
for (tail = uses; tail; tail = TREE_CHAIN (tail))
nuses++;
generating_concat_p = old_generating_concat_p;
if (noutputs == 1 && nclobbers == 0 && nuses == 0)
{
ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = ggc_strdup (constraints[0]);
emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body));
}
else if (noutputs == 0 && nclobbers == 0 && nuses == 0)
{
emit_insn (body);
}
else
{
rtx obody = body;
int num = noutputs;
if (num == 0)
num = 1;
body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers + nuses));
for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
{
XVECEXP (body, 0, i)
= gen_rtx_SET (VOIDmode,
output_rtx[i],
gen_rtx_ASM_OPERANDS
(GET_MODE (output_rtx[i]),
ggc_strdup (TREE_STRING_POINTER (string)),
ggc_strdup (constraints[i]),
i, argvec, constraintvec, locus));
MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol;
}
if (i == 0)
XVECEXP (body, 0, i++) = obody;
for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
{
const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
int j = decode_reg_name (regname);
rtx clobbered_reg;
if (j < 0)
{
if (j == -3)
continue;
if (j == -4)
{
XVECEXP (body, 0, i++)
= gen_rtx_CLOBBER (VOIDmode,
gen_rtx_MEM
(BLKmode,
gen_rtx_SCRATCH (VOIDmode)));
continue;
}
continue;
}
clobbered_reg = gen_rtx_REG (QImode, j);
if (!clobber_conflict_found)
{
int opno;
for (opno = 0; opno < noutputs; opno++)
if (reg_overlap_mentioned_p (clobbered_reg, output_rtx[opno]))
internal_error ("asm clobber conflict with output operand");
for (opno = 0; opno < ninputs - ninout; opno++)
if (reg_overlap_mentioned_p (clobbered_reg,
ASM_OPERANDS_INPUT (obody, opno)))
internal_error ("asm clobber conflict with input operand");
}
XVECEXP (body, 0, i++)
= gen_rtx_CLOBBER (VOIDmode, clobbered_reg);
}
for (tail = uses; tail; tail = TREE_CHAIN (tail))
{
int regno;
rtx rtx_reg;
const char *use_regname = TREE_STRING_POINTER (TREE_VALUE (tail));
regno = decode_reg_name (use_regname);
rtx_reg = gen_rtx_REG (QImode, regno);
XVECEXP (body, 0, i++) = gen_rtx_USE (VOIDmode, rtx_reg);
}
emit_insn (body);
}
for (i = 0; i < noutputs; ++i)
if (real_output_rtx[i])
emit_move_insn (real_output_rtx[i], output_rtx[i]);
free_temp_slots ();
}
void
expand_asm_expr (tree exp)
{
int noutputs, i;
tree outputs, tail;
tree *o;
if (ASM_INPUT_P (exp))
{
expand_asm (ASM_STRING (exp), ASM_VOLATILE_P (exp));
return;
}
outputs = ASM_OUTPUTS (exp);
noutputs = list_length (outputs);
o = (tree *) alloca (noutputs * sizeof (tree));
for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
o[i] = TREE_VALUE (tail);
expand_asm_operands (ASM_STRING (exp), outputs, ASM_INPUTS (exp),
ASM_CLOBBERS (exp), ASM_VOLATILE_P (exp),
ASM_USES (exp),
input_location);
for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
{
if (o[i] != TREE_VALUE (tail))
{
expand_assignment (o[i], TREE_VALUE (tail));
free_temp_slots ();
TREE_VALUE (tail) = o[i];
}
}
}
static bool
check_operand_nalternatives (tree outputs, tree inputs)
{
if (outputs || inputs)
{
tree tmp = TREE_PURPOSE (outputs ? outputs : inputs);
int nalternatives
= n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp)));
tree next = inputs;
if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES)
{
error ("too many alternatives in %<asm%>");
return false;
}
tmp = outputs;
while (tmp)
{
const char *constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp)));
if (n_occurrences (',', constraint) != nalternatives)
{
error ("operand constraints for %<asm%> differ "
"in number of alternatives");
return false;
}
if (TREE_CHAIN (tmp))
tmp = TREE_CHAIN (tmp);
else
tmp = next, next = 0;
}
}
return true;
}
static bool
check_unique_operand_names (tree outputs, tree inputs)
{
tree i, j;
for (i = outputs; i ; i = TREE_CHAIN (i))
{
tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
if (! i_name)
continue;
for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
goto failure;
}
for (i = inputs; i ; i = TREE_CHAIN (i))
{
tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
if (! i_name)
continue;
for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
goto failure;
for (j = outputs; j ; j = TREE_CHAIN (j))
if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
goto failure;
}
return true;
failure:
error ("duplicate asm operand name %qs",
TREE_STRING_POINTER (TREE_PURPOSE (TREE_PURPOSE (i))));
return false;
}
tree
resolve_asm_operand_names (tree string, tree outputs, tree inputs)
{
char *buffer;
char *p;
const char *c;
tree t;
check_unique_operand_names (outputs, inputs);
for (t = inputs; t ; t = TREE_CHAIN (t))
{
c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
if (strchr (c, '[') != NULL)
{
p = buffer = xstrdup (c);
while ((p = strchr (p, '[')) != NULL)
p = resolve_operand_name_1 (p, outputs, inputs);
TREE_VALUE (TREE_PURPOSE (t))
= build_string (strlen (buffer), buffer);
free (buffer);
}
}
c = TREE_STRING_POINTER (string);
while ((c = strchr (c, '%')) != NULL)
{
if (c[1] == '[')
break;
else if (ISALPHA (c[1]) && c[2] == '[')
break;
else
{
c += 1;
continue;
}
}
if (c)
{
buffer = xstrdup (TREE_STRING_POINTER (string));
p = buffer + (c - TREE_STRING_POINTER (string));
while ((p = strchr (p, '%')) != NULL)
{
if (p[1] == '[')
p += 1;
else if (ISALPHA (p[1]) && p[2] == '[')
p += 2;
else
{
p += 1;
continue;
}
p = resolve_operand_name_1 (p, outputs, inputs);
}
string = build_string (strlen (buffer), buffer);
free (buffer);
}
return string;
}
static char *
resolve_operand_name_1 (char *p, tree outputs, tree inputs)
{
char *q;
int op;
tree t;
size_t len;
q = strchr (p, ']');
if (!q)
{
error ("missing close brace for named operand");
return strchr (p, '\0');
}
len = q - p - 1;
for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
{
tree name = TREE_PURPOSE (TREE_PURPOSE (t));
if (name)
{
const char *c = TREE_STRING_POINTER (name);
if (strncmp (c, p + 1, len) == 0 && c[len] == '\0')
goto found;
}
}
for (t = inputs; t ; t = TREE_CHAIN (t), op++)
{
tree name = TREE_PURPOSE (TREE_PURPOSE (t));
if (name)
{
const char *c = TREE_STRING_POINTER (name);
if (strncmp (c, p + 1, len) == 0 && c[len] == '\0')
goto found;
}
}
*q = '\0';
error ("undefined named operand %qs", p + 1);
op = 0;
found:
sprintf (p, "%d", op);
p = strchr (p, '\0');
gcc_assert (p <= q);
memmove (p, q + 1, strlen (q + 1) + 1);
return p;
}
void
expand_expr_stmt (tree exp)
{
rtx value;
tree type;
value = expand_expr (exp, const0_rtx, VOIDmode, 0);
type = TREE_TYPE (exp);
if (value && MEM_P (value) && TREE_THIS_VOLATILE (exp))
{
if (TYPE_MODE (type) == VOIDmode)
;
else if (TYPE_MODE (type) != BLKmode)
value = copy_to_reg (value);
else
{
rtx lab = gen_label_rtx ();
emit_cmp_and_jump_insns (value, value, EQ,
expand_expr (TYPE_SIZE (type),
NULL_RTX, VOIDmode, 0),
BLKmode, 0, lab);
emit_label (lab);
}
}
free_temp_slots ();
}
int
warn_if_unused_value (tree exp, location_t locus)
{
restart:
if (TREE_USED (exp))
return 0;
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:
return 0;
case BIND_EXPR:
exp = BIND_EXPR_BODY (exp);
goto restart;
case SAVE_EXPR:
exp = TREE_OPERAND (exp, 0);
goto restart;
case TRUTH_ORIF_EXPR:
case TRUTH_ANDIF_EXPR:
exp = TREE_OPERAND (exp, 1);
goto restart;
case COMPOUND_EXPR:
if (TREE_NO_WARNING (exp))
return 0;
if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus))
return 1;
if (TREE_CONSTANT (TREE_OPERAND (exp, 1)))
return 0;
exp = TREE_OPERAND (exp, 1);
goto restart;
case NOP_EXPR:
case CONVERT_EXPR:
case NON_LVALUE_EXPR:
if (TREE_NO_WARNING (exp))
return 0;
{
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;
case INDIRECT_REF:
if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE)
{
exp = TREE_OPERAND (exp, 0);
goto restart;
}
default:
if ((DECL_P (exp) || REFERENCE_CLASS_P (exp))
&& TREE_THIS_VOLATILE (exp))
return 0;
if (EXPRESSION_CLASS_P (exp) && TREE_CODE_LENGTH (TREE_CODE (exp)) == 0)
return 0;
maybe_warn:
if (TREE_SIDE_EFFECTS (exp))
return 0;
warning ("%Hvalue computed is not used", &locus);
return 1;
}
}
void
expand_null_return (void)
{
clobber_return_register ();
expand_null_return_1 ();
}
void
expand_naked_return (void)
{
rtx end_label;
clear_pending_stack_adjust ();
do_pending_stack_adjust ();
end_label = naked_return_label;
if (end_label == 0)
end_label = naked_return_label = gen_label_rtx ();
emit_jump (end_label);
}
static void
expand_value_return (rtx val)
{
rtx return_reg = DECL_RTL (DECL_RESULT (current_function_decl));
if (return_reg != val)
{
tree type = TREE_TYPE (DECL_RESULT (current_function_decl));
if (targetm.calls.promote_function_return (TREE_TYPE (current_function_decl)))
{
int unsignedp = TYPE_UNSIGNED (type);
enum machine_mode old_mode
= DECL_MODE (DECL_RESULT (current_function_decl));
enum machine_mode mode
= promote_mode (type, old_mode, &unsignedp, 1);
if (mode != old_mode)
val = convert_modes (mode, old_mode, val, unsignedp);
}
if (GET_CODE (return_reg) == PARALLEL)
emit_group_load (return_reg, val, type, int_size_in_bytes (type));
else
emit_move_insn (return_reg, val);
}
expand_null_return_1 ();
}
static void
expand_null_return_1 (void)
{
clear_pending_stack_adjust ();
do_pending_stack_adjust ();
emit_jump (return_label);
}
void
expand_return (tree retval)
{
rtx result_rtl;
rtx val = 0;
tree retval_rhs;
if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE)
{
expand_expr (retval, NULL_RTX, VOIDmode, 0);
expand_null_return ();
return;
}
if (retval == error_mark_node)
{
expand_null_return ();
return;
}
else if ((TREE_CODE (retval) == MODIFY_EXPR
|| TREE_CODE (retval) == INIT_EXPR)
&& TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL)
retval_rhs = TREE_OPERAND (retval, 1);
else
retval_rhs = retval;
result_rtl = DECL_RTL (DECL_RESULT (current_function_decl));
if (TREE_CODE (retval_rhs) == RESULT_DECL)
expand_value_return (result_rtl);
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 = 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);
enum machine_mode tmpmode, result_reg_mode;
if (bytes == 0)
{
expand_null_return ();
return;
}
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));
for (bitpos = 0, xbitpos = padding_correction;
bitpos < bytes * BITS_PER_UNIT;
bitpos += bitsize, xbitpos += bitsize)
{
if (xbitpos % BITS_PER_WORD == 0
|| xbitpos == padding_correction)
{
dst = gen_reg_rtx (word_mode);
result_pseudos[xbitpos / BITS_PER_WORD] = dst;
emit_move_insn (dst, CONST0_RTX (GET_MODE (dst)));
}
if (bitpos % BITS_PER_WORD == 0)
src = operand_subword_force (result_val,
bitpos / BITS_PER_WORD,
BLKmode);
store_bit_field (dst, bitsize, xbitpos % BITS_PER_WORD, word_mode,
extract_bit_field (src, bitsize,
bitpos % BITS_PER_WORD, 1,
NULL_RTX, word_mode, word_mode));
}
tmpmode = GET_MODE (result_rtl);
if (tmpmode == BLKmode)
{
for (tmpmode = GET_CLASS_NARROWEST_MODE (MODE_INT);
tmpmode != VOIDmode;
tmpmode = GET_MODE_WIDER_MODE (tmpmode))
if (GET_MODE_SIZE (tmpmode) >= bytes)
break;
gcc_assert (tmpmode != VOIDmode);
PUT_MODE (result_rtl, tmpmode);
}
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);
}
else if (retval_rhs != 0
&& !VOID_TYPE_P (TREE_TYPE (retval_rhs))
&& (REG_P (result_rtl)
|| (GET_CODE (result_rtl) == PARALLEL)))
{
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 = expand_expr (retval_rhs, val, GET_MODE (val), 0);
val = force_not_mem (val);
expand_value_return (val);
}
else
{
expand_expr (retval, const0_rtx, VOIDmode, 0);
expand_value_return (result_rtl);
}
}
int
is_body_block (tree stmt)
{
if (lang_hooks.no_body_blocks)
return 0;
if (TREE_CODE (stmt) == BLOCK)
{
tree parent = BLOCK_SUPERCONTEXT (stmt);
if (parent && TREE_CODE (parent) == BLOCK)
{
tree grandparent = BLOCK_SUPERCONTEXT (parent);
if (grandparent && TREE_CODE (grandparent) == FUNCTION_DECL)
return 1;
}
}
return 0;
}
static void
expand_nl_goto_receiver (void)
{
emit_insn (gen_rtx_USE (VOIDmode, hard_frame_pointer_rtx));
emit_insn (gen_rtx_CLOBBER (VOIDmode, static_chain_rtx));
#ifdef HAVE_nonlocal_goto
if (! HAVE_nonlocal_goto)
#endif
emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx);
#if ARG_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
if (fixed_regs[ARG_POINTER_REGNUM])
{
#ifdef ELIMINABLE_REGS
static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS;
size_t i;
for (i = 0; i < ARRAY_SIZE (elim_regs); i++)
if (elim_regs[i].from == ARG_POINTER_REGNUM
&& elim_regs[i].to == HARD_FRAME_POINTER_REGNUM)
break;
if (i == ARRAY_SIZE (elim_regs))
#endif
{
emit_move_insn (virtual_incoming_args_rtx,
copy_to_reg (get_arg_pointer_save_area (cfun)));
}
}
#endif
#ifdef HAVE_nonlocal_goto_receiver
if (HAVE_nonlocal_goto_receiver)
emit_insn (gen_nonlocal_goto_receiver ());
#endif
emit_insn (gen_rtx_ASM_INPUT (VOIDmode, ""));
}
void
expand_decl (tree decl)
{
tree type;
type = TREE_TYPE (decl);
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;
}
if (TREE_CODE (decl) != VAR_DECL)
return;
if (TREE_STATIC (decl) || DECL_EXTERNAL (decl))
return;
if (type == error_mark_node)
SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx));
else if (DECL_SIZE (decl) == 0)
{
rtx x;
if (DECL_INITIAL (decl) == 0)
x = gen_rtx_MEM (BLKmode, const0_rtx);
else
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))
{
int unsignedp = TYPE_UNSIGNED (type);
enum machine_mode reg_mode
= promote_mode (type, DECL_MODE (decl), &unsignedp, 0);
SET_DECL_RTL (decl, gen_reg_rtx (reg_mode));
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 if (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST
&& ! (flag_stack_check && ! STACK_CHECK_BUILTIN
&& 0 < compare_tree_int (DECL_SIZE_UNIT (decl),
STACK_CHECK_MAX_VAR_SIZE)))
{
rtx oldaddr = 0;
rtx addr;
rtx x;
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);
}
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);
}
}
else
{
rtx address, size, x;
do_pending_stack_adjust ();
size = expand_expr (DECL_SIZE_UNIT (decl), NULL_RTX, VOIDmode, 0);
free_temp_slots ();
address = allocate_dynamic_stack_space (size, NULL_RTX,
TYPE_ALIGN (TREE_TYPE (decl)));
x = gen_rtx_MEM (DECL_MODE (decl), address);
set_mem_attributes (x, decl, 1);
SET_DECL_RTL (decl, x);
#ifdef STACK_BOUNDARY
DECL_ALIGN (decl) = STACK_BOUNDARY;
#else
DECL_ALIGN (decl) = BIGGEST_ALIGNMENT;
#endif
DECL_USER_ALIGN (decl) = 0;
}
}
rtx
expand_stack_save (void)
{
rtx ret = NULL_RTX;
do_pending_stack_adjust ();
emit_stack_save (SAVE_BLOCK, &ret, NULL_RTX);
return ret;
}
void
expand_stack_restore (tree var)
{
rtx sa = DECL_RTL (var);
emit_stack_restore (SAVE_BLOCK, sa, NULL_RTX);
}
void
expand_anon_union_decl (tree decl, tree cleanup ATTRIBUTE_UNUSED,
tree decl_elts)
{
rtx x;
tree t;
for (t = decl_elts; t; t = TREE_CHAIN (t))
if (TREE_ADDRESSABLE (TREE_VALUE (t)))
{
TREE_ADDRESSABLE (decl) = 1;
break;
}
expand_decl (decl);
x = DECL_RTL (decl);
for (t = decl_elts; t; t = TREE_CHAIN (t))
{
tree decl_elt = TREE_VALUE (t);
enum machine_mode mode = TYPE_MODE (TREE_TYPE (decl_elt));
rtx decl_rtl;
if (TREE_USED (decl_elt))
TREE_USED (decl) = 1;
DECL_ALIGN (decl_elt) = DECL_ALIGN (decl);
DECL_USER_ALIGN (decl_elt) = DECL_USER_ALIGN (decl);
if (mode == BLKmode && DECL_MODE (decl) != BLKmode)
DECL_MODE (decl_elt) = mode
= mode_for_size_tree (DECL_SIZE (decl_elt), MODE_INT, 1);
if (mode == GET_MODE (x))
decl_rtl = x;
else if (MEM_P (x))
decl_rtl = adjust_address_nv (x, mode, 0);
else
{
gcc_assert (REG_P (x));
decl_rtl = gen_lowpart_SUBREG (mode, x);
}
SET_DECL_RTL (decl_elt, decl_rtl);
}
}
static struct case_node *
add_case_node (struct case_node *head, tree type, tree low, tree high,
tree label)
{
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);
if (!high || tree_int_cst_equal (low, high))
{
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 ((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 (TREE_CODE (min_value) == INTEGER_CST
&& tree_int_cst_compare (low, min_value) < 0)
low = min_value;
low = fold_convert (type, low);
if (TREE_CODE (max_value) == INTEGER_CST
&& tree_int_cst_compare (high, max_value) > 0)
high = max_value;
high = fold_convert (type, high);
}
r = ggc_alloc (sizeof (struct case_node));
r->low = low;
r->high = high;
r->code_label = label;
r->parent = r->left = NULL;
r->right = head;
return r;
}
#define MAX_CASE_BIT_TESTS 3
#ifndef CASE_USE_BIT_TESTS
#define CASE_USE_BIT_TESTS (ashl_optab->handlers[word_mode].insn_code \
!= CODE_FOR_nothing)
#endif
struct case_bit_test
{
HOST_WIDE_INT hi;
HOST_WIDE_INT lo;
rtx label;
int bits;
};
static
bool lshift_cheap_p (void)
{
static bool init = false;
static bool cheap = true;
if (!init)
{
rtx reg = gen_rtx_REG (word_mode, 10000);
int cost = rtx_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg), SET);
cheap = cost < COSTS_N_INSNS (3);
init = true;
}
return cheap;
}
static int
case_bit_test_cmp (const void *p1, const void *p2)
{
const struct case_bit_test *d1 = p1;
const struct case_bit_test *d2 = p2;
return d2->bits - d1->bits;
}
static void
emit_case_bit_tests (tree index_type, tree index_expr, tree minval,
tree range, case_node_ptr nodes, 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;
count = 0;
for (n = nodes; n; n = n->right)
{
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;
}
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_expr (index_expr, NULL_RTX, VOIDmode, 0);
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);
index = convert_to_mode (word_mode, index, 0);
index = expand_binop (word_mode, ashl_optab, const1_rtx,
index, NULL_RTX, 1, OPTAB_WIDEN);
for (i = 0; i < count; i++)
{
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);
}
emit_jump (default_label);
}
#ifndef HAVE_casesi
#define HAVE_casesi 0
#endif
#ifndef HAVE_tablejump
#define HAVE_tablejump 0
#endif
void
expand_case (tree exp)
{
tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
rtx default_label = 0;
struct case_node *n;
unsigned int count, uniq;
rtx index;
rtx table_label;
int ncases;
rtx *labelvec;
int i, fail;
rtx before_case, end, lab;
tree vec = SWITCH_LABELS (exp);
tree orig_type = TREE_TYPE (exp);
tree index_expr = SWITCH_COND (exp);
tree index_type = TREE_TYPE (index_expr);
int unsignedp = TYPE_UNSIGNED (index_type);
rtx start;
struct case_node *case_list = 0;
tree default_label_decl;
gcc_assert (!SWITCH_BODY (exp));
gcc_assert (SWITCH_LABELS (exp));
do_pending_stack_adjust ();
if (index_type != error_mark_node)
{
tree elt;
bitmap label_bitmap;
gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
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);
for (i = TREE_VEC_LENGTH (vec) - 1; --i >= 0; )
{
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));
}
start = get_last_insn ();
if (! NOTE_P (start))
{
emit_note (NOTE_INSN_DELETED);
start = get_last_insn ();
}
default_label = label_rtx (default_label_decl);
before_case = get_last_insn ();
uniq = 0;
count = 0;
label_bitmap = BITMAP_ALLOC (NULL);
for (n = case_list; n; n = n->right)
{
if (count++ == 0)
{
minval = n->low;
maxval = n->high;
}
else
{
if (INT_CST_LT (n->low, minval))
minval = n->low;
if (INT_CST_LT (maxval, n->high))
maxval = n->high;
}
if (! tree_int_cst_equal (n->low, n->high))
count++;
lab = label_rtx (n->code_label);
if (!bitmap_bit_p (label_bitmap, CODE_LABEL_NUMBER (lab)))
{
bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab));
uniq++;
}
}
BITMAP_FREE (label_bitmap);
if (count == 0)
{
emit_jump (default_label);
return;
}
range = fold (build2 (MINUS_EXPR, index_type, maxval, minval));
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 (compare_tree_int (minval, 0) > 0
&& compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
{
minval = integer_zero_node;
range = maxval;
}
emit_case_bit_tests (index_type, index_expr, minval, range,
case_list, default_label);
}
else if (count < case_values_threshold ()
|| compare_tree_int (range,
(optimize_size ? 3 : 10) * count) > 0
|| compare_tree_int (range, 0) < 0
#if !defined(ASM_OUTPUT_ADDR_DIFF_ELT) && (!defined(TARGET_ARM) || !defined(ASM_OUTPUT_ADDR_DIFF_VEC))
|| flag_pic
#endif
|| TREE_CONSTANT (index_expr)
|| (!HAVE_casesi && !HAVE_tablejump))
{
index = expand_expr (index_expr, NULL_RTX, VOIDmode, 0);
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 ();
if (MEM_P (index))
index = copy_to_reg (index);
use_cost_table
= (TREE_CODE (orig_type) != ENUMERAL_TYPE
&& estimate_case_costs (case_list));
balance_case_nodes (&case_list, NULL);
#ifdef TARGET_ARM
{
struct case_node *n;
int unsignedp = TYPE_UNSIGNED (index_type);
if (TYPE_MODE (index_type) == DImode)
{
for (n = case_list; n; n = n->right)
{
if (TREE_INT_CST_HIGH (n->low) != 0
|| (n->high && TREE_INT_CST_HIGH (n->high) != 0))
goto failed;
}
emit_cmp_and_jump_insns (gen_rtx_SUBREG (SImode, index,
subreg_highpart_offset (SImode, DImode)),
const0_rtx, NE, NULL_RTX, SImode, unsignedp, default_label);
if (unsignedp)
index_type = unsigned_intSI_type_node;
else
index_type = intSI_type_node;
index = convert_to_mode (SImode, index, unsignedp);
failed:;
}
}
#endif
emit_case_nodes (index, case_list, default_label, index_type);
emit_jump (default_label);
}
else
{
table_label = gen_label_rtx ();
if (! try_casesi (index_type, index_expr, minval, range,
table_label, default_label))
{
bool ok;
index_type = integer_type_node;
if (! optimize_size
&& compare_tree_int (minval, 0) > 0
&& compare_tree_int (minval, 3) < 0)
{
minval = integer_zero_node;
range = maxval;
}
ok = try_tablejump (index_type, index_expr, minval, range,
table_label, default_label);
gcc_assert (ok);
}
ncases = tree_low_cst (range, 0) + 1;
#ifdef TARGET_ARM
if (TARGET_THUMB)
ncases++;
#endif
labelvec = alloca (ncases * sizeof (rtx));
memset (labelvec, 0, ncases * sizeof (rtx));
for (n = case_list; n; n = n->right)
{
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));
}
for (i = 0; i < ncases; i++)
if (labelvec[i] == 0)
labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
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)));
emit_barrier ();
}
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 ();
}
static void
do_jump_if_equal (rtx op1, rtx op2, 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);
}
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 (! cost_table_initialized)
{
cost_table_initialized = 1;
for (i = 0; i < 128; i++)
{
if (ISALNUM (i))
COST_TABLE (i) = 16;
else if (ISPUNCT (i))
COST_TABLE (i) = 8;
else if (ISCNTRL (i))
COST_TABLE (i) = -1;
}
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;
}
for (n = node; n; n = n->right)
{
if ((INT_CST_LT (n->low, min_ascii)) || 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;
}
return 1;
}
static void
balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
{
case_node_ptr np;
np = *head;
if (np)
{
int cost = 0;
int i = 0;
int ranges = 0;
case_node_ptr *npp;
case_node_ptr left;
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));
i++;
np = np->right;
}
if (i > 2)
{
npp = head;
left = *npp;
if (use_cost_table)
{
int n_moved = 0;
i = (cost + 1) / 2;
while (1)
{
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)
{
np = *head;
np->parent = parent;
balance_case_nodes (&np->left, np);
for (; np->right; np = np->right)
np->right->parent = np;
return;
}
}
else if (i == 3)
npp = &(*npp)->right;
else
{
i = (i + ranges + 1) / 2;
while (1)
{
if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
i--;
i--;
if (i <= 0)
break;
npp = &(*npp)->right;
}
}
*head = np = *npp;
*npp = 0;
np->parent = parent;
np->left = left;
balance_case_nodes (&np->left, np);
balance_case_nodes (&np->right, np);
}
else
{
np = *head;
np->parent = parent;
for (; np->right; np = np->right)
np->right->parent = np;
}
}
}
static int
node_has_low_bound (case_node_ptr node, tree index_type)
{
tree low_minus_one;
case_node_ptr pnode;
if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
return 1;
if (node->left)
return 0;
low_minus_one = fold (build2 (MINUS_EXPR, TREE_TYPE (node->low),
node->low, integer_one_node));
if (! tree_int_cst_lt (low_minus_one, node->low))
return 0;
for (pnode = node->parent; pnode; pnode = pnode->parent)
if (tree_int_cst_equal (low_minus_one, pnode->high))
return 1;
return 0;
}
static int
node_has_high_bound (case_node_ptr node, tree index_type)
{
tree high_plus_one;
case_node_ptr pnode;
if (TYPE_MAX_VALUE (index_type) == NULL)
return 1;
if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
return 1;
if (node->right)
return 0;
high_plus_one = fold (build2 (PLUS_EXPR, TREE_TYPE (node->high),
node->high, integer_one_node));
if (! tree_int_cst_lt (node->high, high_plus_one))
return 0;
for (pnode = node->parent; pnode; pnode = pnode->parent)
if (tree_int_cst_equal (high_plus_one, pnode->low))
return 1;
return 0;
}
static int
node_is_bounded (case_node_ptr node, tree index_type)
{
return (node_has_low_bound (node, index_type)
&& node_has_high_bound (node, index_type));
}
static void
emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
tree index_type)
{
int unsignedp = TYPE_UNSIGNED (index_type);
enum machine_mode mode = GET_MODE (index);
enum machine_mode imode = TYPE_MODE (index_type);
if (mode == VOIDmode)
mode = imode;
if (node_is_bounded (node, index_type))
emit_jump (label_rtx (node->code_label));
else if (tree_int_cst_equal (node->low, node->high))
{
do_jump_if_equal (index,
convert_modes (mode, imode,
expand_expr (node->low, NULL_RTX,
VOIDmode, 0),
unsignedp),
label_rtx (node->code_label), unsignedp);
if (node->right != 0 && node->left != 0)
{
if (node_is_bounded (node->right, index_type))
{
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
expand_expr (node->high, NULL_RTX,
VOIDmode, 0),
unsignedp),
GT, NULL_RTX, mode, unsignedp,
label_rtx (node->right->code_label));
emit_case_nodes (index, node->left, default_label, index_type);
}
else if (node_is_bounded (node->left, index_type))
{
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
expand_expr (node->high, NULL_RTX,
VOIDmode, 0),
unsignedp),
LT, NULL_RTX, mode, unsignedp,
label_rtx (node->left->code_label));
emit_case_nodes (index, node->right, default_label, index_type);
}
else if (tree_int_cst_equal (node->right->low, node->right->high)
&& node->right->left == 0
&& node->right->right == 0
&& tree_int_cst_equal (node->left->low, node->left->high)
&& node->left->left == 0
&& node->left->right == 0)
{
do_jump_if_equal (index,
convert_modes (mode, imode,
expand_expr (node->right->low,
NULL_RTX,
VOIDmode, 0),
unsignedp),
label_rtx (node->right->code_label),
unsignedp);
do_jump_if_equal (index,
convert_modes (mode, imode,
expand_expr (node->left->low,
NULL_RTX,
VOIDmode, 0),
unsignedp),
label_rtx (node->left->code_label),
unsignedp);
}
else
{
tree test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
expand_expr (node->high, NULL_RTX,
VOIDmode, 0),
unsignedp),
GT, NULL_RTX, mode, unsignedp,
label_rtx (test_label));
emit_case_nodes (index, node->left, default_label, index_type);
emit_jump (default_label);
expand_label (test_label);
emit_case_nodes (index, node->right, default_label, index_type);
}
}
else if (node->right != 0 && node->left == 0)
{
if (node->right->right || node->right->left
|| !tree_int_cst_equal (node->right->low, node->right->high))
{
if (!node_has_low_bound (node, index_type))
{
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
expand_expr (node->high, NULL_RTX,
VOIDmode, 0),
unsignedp),
LT, NULL_RTX, mode, unsignedp,
default_label);
}
emit_case_nodes (index, node->right, default_label, index_type);
}
else
do_jump_if_equal (index,
convert_modes
(mode, imode,
expand_expr (node->right->low, NULL_RTX,
VOIDmode, 0),
unsignedp),
label_rtx (node->right->code_label), unsignedp);
}
else if (node->right == 0 && node->left != 0)
{
if (node->left->left || node->left->right
|| !tree_int_cst_equal (node->left->low, node->left->high))
{
if (!node_has_high_bound (node, index_type))
{
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
expand_expr (node->high, NULL_RTX,
VOIDmode, 0),
unsignedp),
GT, NULL_RTX, mode, unsignedp,
default_label);
}
emit_case_nodes (index, node->left, default_label, index_type);
}
else
do_jump_if_equal (index,
convert_modes
(mode, imode,
expand_expr (node->left->low, NULL_RTX,
VOIDmode, 0),
unsignedp),
label_rtx (node->left->code_label), unsignedp);
}
}
else
{
if (node->right != 0 && node->left != 0)
{
tree test_label = 0;
if (node_is_bounded (node->right, index_type))
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
expand_expr (node->high, NULL_RTX,
VOIDmode, 0),
unsignedp),
GT, NULL_RTX, mode, unsignedp,
label_rtx (node->right->code_label));
else
{
test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
expand_expr (node->high, NULL_RTX,
VOIDmode, 0),
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),
unsignedp),
GE, NULL_RTX, mode, unsignedp,
label_rtx (node->code_label));
emit_case_nodes (index, node->left, default_label, index_type);
if (test_label)
{
emit_jump (default_label);
expand_label (test_label);
emit_case_nodes (index, node->right, default_label, index_type);
}
}
else if (node->right != 0 && node->left == 0)
{
if (!node_has_low_bound (node, index_type))
{
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
expand_expr (node->low, NULL_RTX,
VOIDmode, 0),
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),
unsignedp),
LE, NULL_RTX, mode, unsignedp,
label_rtx (node->code_label));
emit_case_nodes (index, node->right, default_label, index_type);
}
else if (node->right == 0 && node->left != 0)
{
if (!node_has_high_bound (node, index_type))
{
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
expand_expr (node->high, NULL_RTX,
VOIDmode, 0),
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),
unsignedp),
GE, NULL_RTX, mode, unsignedp,
label_rtx (node->code_label));
emit_case_nodes (index, node->left, default_label, index_type);
}
else
{
int high_bound = node_has_high_bound (node, index_type);
int low_bound = node_has_low_bound (node, index_type);
if (!high_bound && low_bound)
{
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
expand_expr (node->high, NULL_RTX,
VOIDmode, 0),
unsignedp),
GT, NULL_RTX, mode, unsignedp,
default_label);
}
else if (!low_bound && high_bound)
{
emit_cmp_and_jump_insns (index,
convert_modes
(mode, imode,
expand_expr (node->low, NULL_RTX,
VOIDmode, 0),
unsignedp),
LT, NULL_RTX, mode, unsignedp,
default_label);
}
else if (!low_bound && !high_bound)
{
tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
tree low = build1 (CONVERT_EXPR, type, node->low);
tree high = build1 (CONVERT_EXPR, type, node->high);
rtx low_rtx, new_index, new_bound;
low_rtx = expand_expr (low, NULL_RTX, mode, 0);
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);
emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
mode, 1, default_label);
}
emit_jump (label_rtx (node->code_label));
}
}
}