/* Expands front end tree to back end RTL for GNU C-Compiler
- Copyright (C) 1987, 88, 89, 92, 93, 94, 1995 Free Software Foundation, Inc.
+ Copyright (C) 1987, 88, 89, 92-5, 1996 Free Software Foundation, Inc.
This file is part of GNU CC.
You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING. If not, write to
-the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA. */
/* This file handles the generation of rtl code from tree structure
extern rtx return_label;
-/* List (chain of EXPR_LISTs) of pseudo-regs of SAVE_EXPRs.
- So we can mark them all live at the end of the function, if nonopt. */
-extern rtx save_expr_regs;
-
/* Offset to end of allocated area of stack frame.
If stack grows down, this is the address of the last stack slot allocated.
If stack grows up, this is the address for the next slot. */
statements. We handle "range" labels; for a single-value label
as in C, the high and low limits are the same.
- A chain of case nodes is initially maintained via the RIGHT fields
- in the nodes. Nodes with higher case values are later in the list.
+ An AVL tree of case nodes is initially created, and later transformed
+ to a list linked via the RIGHT fields in the nodes. Nodes with
+ higher case values are later in the list.
Switch statements can be output in one of two forms. A branch table
is used if there are more than a few labels and the labels are dense
tree low; /* Lowest index value for this label */
tree high; /* Highest index value for this label */
tree code_label; /* Label to jump to when node matches */
+ int balance;
};
typedef struct case_node case_node;
A label is needed for skipping over this block. It is only
used when generating bytecodes. */
rtx skip_label;
- /* A list of case labels, kept in ascending order by value
- as the list is built.
- During expand_end_case, this list may be rearranged into a
- nearly balanced binary tree. */
+ /* A list of case labels; it is first built as an AVL tree.
+ During expand_end_case, this is converted to a list, and may be
+ rearranged into a nearly balanced binary tree. */
struct case_node *case_list;
/* Label to jump to if no case matches. */
tree default_label;
static int node_is_bounded PROTO((case_node_ptr, tree));
static void emit_jump_if_reachable PROTO((rtx));
static void emit_case_nodes PROTO((rtx, case_node_ptr, rtx, tree));
-
-int bc_expand_exit_loop_if_false ();
-void bc_expand_start_cond ();
-void bc_expand_end_cond ();
-void bc_expand_start_else ();
-void bc_expand_end_bindings ();
-void bc_expand_start_case ();
-void bc_check_for_full_enumeration_handling ();
-void bc_expand_end_case ();
-void bc_expand_decl ();
+static int add_case_node PROTO((tree, tree, tree, tree *));
+static struct case_node *case_tree2list PROTO((case_node *, case_node *));
extern rtx bc_allocate_local ();
extern rtx bc_allocate_variable_array ();
last_insn = get_last_insn ();
if (!optimize
&& (GET_CODE (last_insn) == CODE_LABEL
- || prev_real_insn (last_insn) == 0))
+ || (GET_CODE (last_insn) == NOTE
+ && prev_real_insn (last_insn) == 0)))
emit_insn (gen_nop ());
}
}
&& (after_label == 0
|| INSN_UID (first_insn) < INSN_UID (after_label))
&& INSN_UID (first_insn) > INSN_UID (f->before_jump)
- && ! DECL_REGISTER (f->target))
+ && ! DECL_ERROR_ISSUED (f->target))
{
error_with_decl (f->target,
"label `%s' used before containing binding contour");
/* Prevent multiple errors for one label. */
- DECL_REGISTER (f->target) = 1;
+ DECL_ERROR_ISSUED (f->target) = 1;
}
/* We will expand the cleanups into a sequence of their own and
f->before_jump
= emit_insns_after (cleanup_insns, f->before_jump);
- TREE_VALUE (lists) = 0;
+ f->cleanup_list_list = TREE_CHAIN (lists);
}
if (stack_level)
tree type = TREE_TYPE (val);
tree val1;
int j;
- int found_equal;
+ int found_equal = 0;
+ int allows_reg = 0;
/* If there's an erroneous arg, emit no insn. */
if (TREE_TYPE (val) == error_mark_node)
return;
- /* Make sure constraint has `=' and does not have `+'. */
+ /* Make sure constraint has `=' and does not have `+'. Also, see
+ if it allows any register. Be liberal on the latter test, since
+ the worst that happens if we get it wrong is we issue an error
+ message. */
- found_equal = 0;
- for (j = 0; j < TREE_STRING_LENGTH (TREE_PURPOSE (tail)); j++)
- {
- if (TREE_STRING_POINTER (TREE_PURPOSE (tail))[j] == '+')
- {
- error ("output operand constraint contains `+'");
- return;
- }
- if (TREE_STRING_POINTER (TREE_PURPOSE (tail))[j] == '=')
+ for (j = 0; j < TREE_STRING_LENGTH (TREE_PURPOSE (tail)) - 1; j++)
+ switch (TREE_STRING_POINTER (TREE_PURPOSE (tail))[j])
+ {
+ case '+':
+ error ("output operand constraint contains `+'");
+ return;
+
+ case '=':
found_equal = 1;
- }
+ break;
+
+ case '?': case '!': case '*': case '%': case '&':
+ case 'V': case 'm': case 'o': case '<': case '>':
+ case 'E': case 'F': case 'G': case 'H': case 'X':
+ case 's': case 'i': case 'n':
+ case 'I': case 'J': case 'K': case 'L': case 'M':
+ case 'N': case 'O': case 'P': case ',':
+#ifdef EXTRA_CONSTRAINT
+ case 'Q': case 'R': case 'S': case 'T': case 'U':
+#endif
+ break;
+
+ case 'p': case 'g': case 'r':
+ /* Whether or not a numeric constraint allows a register is
+ decided by the matching constraint, and so there is no need
+ to do anything special with them. We must handle them in
+ the default case, so that we don't unnecessarily force
+ operands to memory. */
+ case '0': case '1': case '2': case '3': case '4':
+ default:
+ allows_reg = 1;
+ break;
+ }
+
if (! found_equal)
{
error ("output operand constraint lacks `='");
return;
}
- /* If an output operand is not a decl or indirect ref,
- make a temporary to act as an intermediate. Make the asm insn
- write into that, then our caller will copy it to the real output
- operand. Likewise for promoted variables. */
+ /* If an output operand is not a decl or indirect ref and our constraint
+ allows a register, make a temporary to act as an intermediate.
+ Make the asm insn write into that, then our caller will copy it to
+ the real output operand. Likewise for promoted variables. */
if (TREE_CODE (val) == INDIRECT_REF
|| (TREE_CODE_CLASS (TREE_CODE (val)) == 'd'
&& ! (GET_CODE (DECL_RTL (val)) == REG
- && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))))
- output_rtx[i] = expand_expr (TREE_VALUE (tail), NULL_RTX, VOIDmode, 0);
- else
+ && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))
+ || ! allows_reg)
{
- if (TYPE_MODE (type) == BLKmode)
- {
- output_rtx[i] = assign_stack_temp (BLKmode,
- int_size_in_bytes (type), 0);
- MEM_IN_STRUCT_P (output_rtx[i]) = AGGREGATE_TYPE_P (type);
- }
- else
- output_rtx[i] = gen_reg_rtx (TYPE_MODE (type));
+ if (! allows_reg)
+ mark_addressable (TREE_VALUE (tail));
+ output_rtx[i]
+ = expand_expr (TREE_VALUE (tail), NULL_RTX, VOIDmode, 0);
+
+ if (! allows_reg && GET_CODE (output_rtx[i]) != MEM)
+ error ("output number %d not directly addressable", i);
+ }
+ else
+ {
+ output_rtx[i] = assign_temp (type, 0, 0, 0);
TREE_VALUE (tail) = make_tree (type, output_rtx[i]);
}
}
for (tail = inputs; tail; tail = TREE_CHAIN (tail))
{
int j;
+ int allows_reg = 0;
/* If there's an erroneous arg, emit no insn,
because the ASM_INPUT would get VOIDmode
/* Make sure constraint has neither `=' nor `+'. */
- for (j = 0; j < TREE_STRING_LENGTH (TREE_PURPOSE (tail)); j++)
- if (TREE_STRING_POINTER (TREE_PURPOSE (tail))[j] == '='
- || TREE_STRING_POINTER (TREE_PURPOSE (tail))[j] == '+')
+ for (j = 0; j < TREE_STRING_LENGTH (TREE_PURPOSE (tail)) - 1; j++)
+ switch (TREE_STRING_POINTER (TREE_PURPOSE (tail))[j])
{
+ case '+': case '=':
error ("input operand constraint contains `%c'",
TREE_STRING_POINTER (TREE_PURPOSE (tail))[j]);
return;
+
+ case '?': case '!': case '*': case '%': case '&':
+ case 'V': case 'm': case 'o': case '<': case '>':
+ case 'E': case 'F': case 'G': case 'H': case 'X':
+ case 's': case 'i': case 'n':
+ case 'I': case 'J': case 'K': case 'L': case 'M':
+ case 'N': case 'O': case 'P': case ',':
+#ifdef EXTRA_CONSTRAINT
+ case 'Q': case 'R': case 'S': case 'T': case 'U':
+#endif
+ break;
+
+ case 'p': case 'g': case 'r':
+ /* Whether or not a numeric constraint allows a register is
+ decided by the matching constraint, and so there is no need
+ to do anything special with them. We must handle them in
+ the default case, so that we don't unnecessarily force
+ operands to memory. */
+ case '0': case '1': case '2': case '3': case '4':
+ default:
+ allows_reg = 1;
+ break;
}
+ if (! allows_reg)
+ mark_addressable (TREE_VALUE (tail));
+
XVECEXP (body, 3, i) /* argvec */
= expand_expr (TREE_VALUE (tail), NULL_RTX, VOIDmode, 0);
if (CONSTANT_P (XVECEXP (body, 3, i))
&& ! general_operand (XVECEXP (body, 3, i),
TYPE_MODE (TREE_TYPE (TREE_VALUE (tail)))))
- XVECEXP (body, 3, i)
- = force_reg (TYPE_MODE (TREE_TYPE (TREE_VALUE (tail))),
- XVECEXP (body, 3, i));
+ {
+ if (allows_reg)
+ XVECEXP (body, 3, i)
+ = force_reg (TYPE_MODE (TREE_TYPE (TREE_VALUE (tail))),
+ XVECEXP (body, 3, i));
+ else
+ XVECEXP (body, 3, i)
+ = force_const_mem (TYPE_MODE (TREE_TYPE (TREE_VALUE (tail))),
+ XVECEXP (body, 3, i));
+ }
+
+ if (! allows_reg
+ && (GET_CODE (XVECEXP (body, 3, i)) == REG
+ || GET_CODE (XVECEXP (body, 3, i)) == SUBREG
+ || GET_CODE (XVECEXP (body, 3, i)) == CONCAT))
+ {
+ tree type = TREE_TYPE (TREE_VALUE (tail));
+ rtx memloc = assign_temp (type, 1, 1, 1);
+
+ emit_move_insn (memloc, XVECEXP (body, 3, i));
+ XVECEXP (body, 3, i) = memloc;
+ }
+
XVECEXP (body, 4, i) /* constraints */
= gen_rtx (ASM_INPUT, TYPE_MODE (TREE_TYPE (TREE_VALUE (tail))),
TREE_STRING_POINTER (TREE_PURPOSE (tail)));
momentary = suspend_momentary ();
t = make_node (RTL_EXPR);
resume_momentary (momentary);
+ do_pending_stack_adjust ();
start_sequence_for_rtl_expr (t);
NO_DEFER_POP;
expr_stmts_for_value++;
&& TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode
&& GET_CODE (DECL_RTL (DECL_RESULT (current_function_decl))) == REG)
{
- int i;
+ int i, bitpos, xbitpos;
int big_endian_correction = 0;
int bytes = int_size_in_bytes (TREE_TYPE (retval_rhs));
int n_regs = (bytes + UNITS_PER_WORD - 1) / UNITS_PER_WORD;
+ int bitsize = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)),BITS_PER_WORD);
rtx *result_pseudos = (rtx *) alloca (sizeof (rtx) * n_regs);
- rtx result_reg;
+ rtx result_reg, src, dst;
rtx result_val = expand_expr (retval_rhs, NULL_RTX, VOIDmode, 0);
enum machine_mode tmpmode, result_reg_mode;
- /* Structures smaller than a word are aligned to the least significant
- byte (to the right). On a BYTES_BIG_ENDIAN machine, this means we
- must skip the empty high order bytes when calculating the bit
- offset. */
- if (BYTES_BIG_ENDIAN && bytes < UNITS_PER_WORD)
- big_endian_correction = (BITS_PER_WORD - (bytes * BITS_PER_UNIT));
-
- for (i = 0; i < n_regs; i++)
+ /* Structures whose size is not a multiple of a word are aligned
+ to the least significant byte (to the right). On a BYTES_BIG_ENDIAN
+ machine, this means we must skip the empty high order bytes when
+ calculating the bit offset. */
+ if (BYTES_BIG_ENDIAN && bytes % UNITS_PER_WORD)
+ big_endian_correction = (BITS_PER_WORD - ((bytes % UNITS_PER_WORD)
+ * BITS_PER_UNIT));
+
+ /* Copy the structure BITSIZE bits at a time. */
+ for (bitpos = 0, xbitpos = big_endian_correction;
+ bitpos < bytes * BITS_PER_UNIT;
+ bitpos += bitsize, xbitpos += bitsize)
{
- rtx reg = gen_reg_rtx (word_mode);
- rtx word = operand_subword_force (result_val, i, BLKmode);
- int bitsize = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)),BITS_PER_WORD);
- int bitpos;
-
- result_pseudos[i] = reg;
-
- /* Clobber REG and move each partword into it. Ensure we don't
- go past the end of the structure. Note that the loop below
- works because we've already verified that padding and
- endianness are compatible. */
- emit_insn (gen_rtx (CLOBBER, VOIDmode, reg));
-
- for (bitpos = 0;
- bitpos < BITS_PER_WORD && bytes > 0;
- bitpos += bitsize, bytes -= bitsize / BITS_PER_UNIT)
+ /* We need a new destination pseudo each time xbitpos is
+ on a word boundary and when xbitpos == big_endian_correction
+ (the first time through). */
+ if (xbitpos % BITS_PER_WORD == 0
+ || xbitpos == big_endian_correction)
{
- int xbitpos = bitpos + big_endian_correction;
-
- store_bit_field (reg, bitsize, xbitpos, word_mode,
- extract_bit_field (word, bitsize, bitpos, 1,
- NULL_RTX, word_mode,
- word_mode,
- bitsize / BITS_PER_UNIT,
- BITS_PER_WORD),
- bitsize / BITS_PER_UNIT, BITS_PER_WORD);
+ /* Generate an appropriate register. */
+ dst = gen_reg_rtx (word_mode);
+ result_pseudos[xbitpos / BITS_PER_WORD] = dst;
+
+ /* Clobber the destination before we move anything into it. */
+ emit_insn (gen_rtx (CLOBBER, VOIDmode, dst));
}
+
+ /* We need a new source operand each time bitpos is on a word
+ boundary. */
+ if (bitpos % BITS_PER_WORD == 0)
+ src = operand_subword_force (result_val,
+ bitpos / BITS_PER_WORD,
+ BLKmode);
+
+ /* Use bitpos for the source extraction (left justified) and
+ xbitpos for the destination store (right justified). */
+ store_bit_field (dst, bitsize, xbitpos % BITS_PER_WORD, word_mode,
+ extract_bit_field (src, bitsize,
+ bitpos % BITS_PER_WORD, 1,
+ NULL_RTX, word_mode,
+ word_mode,
+ bitsize / BITS_PER_UNIT,
+ BITS_PER_WORD),
+ bitsize / BITS_PER_UNIT, BITS_PER_WORD);
}
/* Find the smallest integer mode large enough to hold the
for (a = actuals, f = formals, i = 0; a && f; a = TREE_CHAIN (a), f = TREE_CHAIN (f), i++)
{
- if (TREE_TYPE (TREE_VALUE (a)) != TREE_TYPE (f))
+ if (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_VALUE (a)))
+ != TYPE_MAIN_VARIANT (TREE_TYPE (f)))
return 0;
if (GET_CODE (DECL_RTL (f)) != REG || DECL_MODE (f) == BLKmode)
return 0;
}
\f
/* Generate RTL for the automatic variable declaration DECL.
- (Other kinds of declarations are simply ignored if seen here.)
- CLEANUP is an expression to be executed at exit from this binding contour;
- for example, in C++, it might call the destructor for this variable.
-
- If CLEANUP contains any SAVE_EXPRs, then you must preevaluate them
- either before or after calling `expand_decl' but before compiling
- any subsequent expressions. This is because CLEANUP may be expanded
- more than once, on different branches of execution.
- For the same reason, CLEANUP may not contain a CALL_EXPR
- except as its topmost node--else `preexpand_calls' would get confused.
-
- If CLEANUP is nonzero and DECL is zero, we record a cleanup
- that is not associated with any particular variable.
-
- There is no special support here for C++ constructors.
- They should be handled by the proper code in DECL_INITIAL. */
+ (Other kinds of declarations are simply ignored if seen here.) */
void
expand_decl (decl)
{
DECL_RTL (decl) = gen_reg_rtx (reg_mode);
if (TREE_CODE (type) == POINTER_TYPE)
- mark_reg_pointer (DECL_RTL (decl));
+ mark_reg_pointer (DECL_RTL (decl),
+ (TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl)))
+ / BITS_PER_UNIT));
REG_USERVAR_P (DECL_RTL (decl)) = 1;
}
}
NULL_RTX, VOIDmode, 0);
free_temp_slots ();
- /* Allocate space on the stack for the variable. */
+ /* Allocate space on the stack for the variable. Note that
+ DECL_ALIGN says how the variable is to be aligned and we
+ cannot use it to conclude anything about the alignment of
+ the size. */
address = allocate_dynamic_stack_space (size, NULL_RTX,
- DECL_ALIGN (decl));
+ TYPE_ALIGN (TREE_TYPE (decl)));
/* Reference the variable indirect through that rtx. */
DECL_RTL (decl) = gen_rtx (MEM, DECL_MODE (decl), address);
/* CLEANUP is an expression to be executed at exit from this binding contour;
for example, in C++, it might call the destructor for this variable.
- If CLEANUP contains any SAVE_EXPRs, then you must preevaluate them
- either before or after calling `expand_decl' but before compiling
- any subsequent expressions. This is because CLEANUP may be expanded
- more than once, on different branches of execution.
- For the same reason, CLEANUP may not contain a CALL_EXPR
- except as its topmost node--else `preexpand_calls' would get confused.
+ We wrap CLEANUP in an UNSAVE_EXPR node, so that we can expand the
+ CLEANUP multiple times, and have the correct semantics. This
+ happens in exception handling, and for non-local gotos.
If CLEANUP is nonzero and DECL is zero, we record a cleanup
that is not associated with any particular variable. */
if (cleanup != 0)
{
+ cleanup = unsave_expr (cleanup);
+
thisblock->data.block.cleanups
= temp_tree_cons (decl, cleanup, thisblock->data.block.cleanups);
/* If this block has a cleanup, it belongs in stack_block_stack. */
struct nesting *thisblock = block_stack;
rtx x;
- expand_decl (decl, cleanup);
+ expand_decl (decl);
+ expand_decl_cleanup (decl, cleanup);
x = DECL_RTL (decl);
while (decl_elts)
case_stack->data.case_stmt.default_label = label;
}
else
- {
- /* Find the elt in the chain before which to insert the new value,
- to keep the chain sorted in increasing order.
- But report an error if this element is a duplicate. */
- for (l = &case_stack->data.case_stmt.case_list;
- /* Keep going past elements distinctly less than VALUE. */
- *l != 0 && tree_int_cst_lt ((*l)->high, value);
- l = &(*l)->right)
- ;
- if (*l)
- {
- /* Element we will insert before must be distinctly greater;
- overlap means error. */
- if (! tree_int_cst_lt (value, (*l)->low))
- {
- *duplicate = (*l)->code_label;
- return 2;
- }
- }
-
- /* Add this label to the chain, and succeed.
- Copy VALUE so it is on temporary rather than momentary
- obstack and will thus survive till the end of the case statement. */
- n = (struct case_node *) oballoc (sizeof (struct case_node));
- n->left = 0;
- n->right = *l;
- n->high = n->low = copy_node (value);
- n->code_label = label;
- *l = n;
- }
+ return add_case_node (value, value, label, duplicate);
expand_label (label);
return 0;
if (tree_int_cst_lt (value2, value1))
return 4;
- /* If the bounds are equal, turn this into the one-value case. */
- if (tree_int_cst_equal (value1, value2))
- return pushcase (value1, converter, label, duplicate);
-
- /* Find the elt in the chain before which to insert the new value,
- to keep the chain sorted in increasing order.
- But report an error if this element is a duplicate. */
- for (l = &case_stack->data.case_stmt.case_list;
- /* Keep going past elements distinctly less than this range. */
- *l != 0 && tree_int_cst_lt ((*l)->high, value1);
- l = &(*l)->right)
- ;
- if (*l)
+ return add_case_node (value1, value2, label, duplicate);
+}
+
+/* Do the actual insertion of a case label for pushcase and pushcase_range
+ into case_stack->data.case_stmt.case_list. Use an AVL tree to avoid
+ slowdown for large switch statements. */
+
+static int
+add_case_node (low, high, label, duplicate)
+ tree low, high;
+ tree label;
+ tree *duplicate;
+{
+ struct case_node *p, **q, *r;
+
+ q = &case_stack->data.case_stmt.case_list;
+ p = *q;
+
+ while (r = *q)
{
- /* Element we will insert before must be distinctly greater;
- overlap means error. */
- if (! tree_int_cst_lt (value2, (*l)->low))
+ p = r;
+
+ /* Keep going past elements distinctly greater than HIGH. */
+ if (tree_int_cst_lt (high, p->low))
+ q = &p->left;
+
+ /* or distinctly less than LOW. */
+ else if (tree_int_cst_lt (p->high, low))
+ q = &p->right;
+
+ else
{
- *duplicate = (*l)->code_label;
+ /* We have an overlap; this is an error. */
+ *duplicate = p->code_label;
return 2;
}
}
/* Add this label to the chain, and succeed.
- Copy VALUE1, VALUE2 so they are on temporary rather than momentary
+ Copy LOW, HIGH so they are on temporary rather than momentary
obstack and will thus survive till the end of the case statement. */
- n = (struct case_node *) oballoc (sizeof (struct case_node));
- n->left = 0;
- n->right = *l;
- n->low = copy_node (value1);
- n->high = copy_node (value2);
- n->code_label = label;
- *l = n;
+ r = (struct case_node *) oballoc (sizeof (struct case_node));
+ r->low = copy_node (low);
+
+ /* If the bounds are equal, turn this into the one-value case. */
+
+ if (tree_int_cst_equal (low, high))
+ r->high = r->low;
+ else
+ {
+ r->high = copy_node (high);
+ case_stack->data.case_stmt.num_ranges++;
+ }
+ r->code_label = label;
expand_label (label);
- case_stack->data.case_stmt.num_ranges++;
+ *q = r;
+ r->parent = p;
+ r->left = 0;
+ r->right = 0;
+ r->balance = 0;
+
+ while (p)
+ {
+ struct case_node *s;
+
+ if (r == p->left)
+ {
+ int b;
+
+ if (! (b = p->balance))
+ /* Growth propagation from left side. */
+ p->balance = -1;
+ else if (b < 0)
+ {
+ if (r->balance < 0)
+ {
+ /* R-Rotation */
+ if (p->left = s = r->right)
+ s->parent = p;
+
+ r->right = p;
+ p->balance = 0;
+ r->balance = 0;
+ s = p->parent;
+ p->parent = r;
+
+ if (r->parent = s)
+ {
+ if (s->left == p)
+ s->left = r;
+ else
+ s->right = r;
+ }
+ else
+ case_stack->data.case_stmt.case_list = r;
+ }
+ else
+ /* r->balance == +1 */
+ {
+ /* LR-Rotation */
+
+ int b2;
+ struct case_node *t = r->right;
+
+ if (p->left = s = t->right)
+ s->parent = p;
+
+ t->right = p;
+ if (r->right = s = t->left)
+ s->parent = r;
+
+ t->left = r;
+ b = t->balance;
+ b2 = b < 0;
+ p->balance = b2;
+ b2 = -b2 - b;
+ r->balance = b2;
+ t->balance = 0;
+ s = p->parent;
+ p->parent = t;
+ r->parent = t;
+
+ if (t->parent = s)
+ {
+ if (s->left == p)
+ s->left = t;
+ else
+ s->right = t;
+ }
+ else
+ case_stack->data.case_stmt.case_list = t;
+ }
+ break;
+ }
+
+ else
+ {
+ /* p->balance == +1; growth of left side balances the node. */
+ p->balance = 0;
+ break;
+ }
+ }
+ else
+ /* r == p->right */
+ {
+ int b;
+
+ if (! (b = p->balance))
+ /* Growth propagation from right side. */
+ p->balance++;
+ else if (b > 0)
+ {
+ if (r->balance > 0)
+ {
+ /* L-Rotation */
+
+ if (p->right = s = r->left)
+ s->parent = p;
+
+ r->left = p;
+ p->balance = 0;
+ r->balance = 0;
+ s = p->parent;
+ p->parent = r;
+ if (r->parent = s)
+ {
+ if (s->left == p)
+ s->left = r;
+ else
+ s->right = r;
+ }
+
+ else
+ case_stack->data.case_stmt.case_list = r;
+ }
+
+ else
+ /* r->balance == -1 */
+ {
+ /* RL-Rotation */
+ int b2;
+ struct case_node *t = r->left;
+
+ if (p->right = s = t->left)
+ s->parent = p;
+
+ t->left = p;
+
+ if (r->left = s = t->right)
+ s->parent = r;
+
+ t->right = r;
+ b = t->balance;
+ b2 = b < 0;
+ r->balance = b2;
+ b2 = -b2 - b;
+ p->balance = b2;
+ t->balance = 0;
+ s = p->parent;
+ p->parent = t;
+ r->parent = t;
+
+ if (t->parent = s)
+ {
+ if (s->left == p)
+ s->left = t;
+ else
+ s->right = t;
+ }
+
+ else
+ case_stack->data.case_stmt.case_list = t;
+ }
+ break;
+ }
+ else
+ {
+ /* p->balance == -1; growth of right side balances the node. */
+ p->balance = 0;
+ break;
+ }
+ }
+
+ r = p;
+ p = p->parent;
+ }
return 0;
}
-
/* Accumulate one case or default label; VALUE is the value of the
case, or nil for a default label. If not currently inside a case,
return 1 and do nothing. If VALUE is a duplicate or overlaps, return
if (case_label != thiscase->data.case_stmt.case_list
&& ! tree_int_cst_lt (case_label->high, value)
- || case_label->left && ! tree_int_cst_lt (value, case_label->left->low))
+ || (case_label->left && ! tree_int_cst_lt (value, case_label->left->low)))
return 2;
new_label = (struct case_node *) oballoc (sizeof (struct case_node));
tree next_node_to_try = NULL_TREE;
long next_node_offset = 0;
- register struct case_node *n;
+ register struct case_node *n, *root = case_stack->data.case_stmt.case_list;
tree val = make_node (INTEGER_CST);
TREE_TYPE (val) = type;
- for (n = case_stack->data.case_stmt.case_list; n;
- n = n->right)
+ if (! root)
+ ; /* Do nothing */
+ else if (sparseness == 2)
{
- TREE_INT_CST_LOW (val) = TREE_INT_CST_LOW (n->low);
- TREE_INT_CST_HIGH (val) = TREE_INT_CST_HIGH (n->low);
- while ( ! tree_int_cst_lt (n->high, val))
+ tree t;
+ HOST_WIDE_INT xlo;
+
+ /* This less efficient loop is only needed to handle
+ duplicate case values (multiple enum constants
+ with the same value). */
+ TREE_TYPE (val) = TREE_TYPE (root->low);
+ for (t = TYPE_VALUES (type), xlo = 0; t != NULL_TREE;
+ t = TREE_CHAIN (t), xlo++)
{
- /* Calculate (into xlo) the "offset" of the integer (val).
- The element with lowest value has offset 0, the next smallest
- element has offset 1, etc. */
-
- HOST_WIDE_INT xlo, xhi;
- tree t;
- if (sparseness == 2)
+ TREE_INT_CST_LOW (val) = TREE_INT_CST_LOW (TREE_VALUE (t));
+ TREE_INT_CST_HIGH (val) = TREE_INT_CST_HIGH (TREE_VALUE (t));
+ n = root;
+ do
{
- /* This less efficient loop is only needed to handle
- duplicate case values (multiple enum constants
- with the same value). */
- for (t = TYPE_VALUES (type), xlo = 0; t != NULL_TREE;
- t = TREE_CHAIN (t), xlo++)
+ /* Keep going past elements distinctly greater than VAL. */
+ if (tree_int_cst_lt (val, n->low))
+ n = n->left;
+
+ /* or distinctly less than VAL. */
+ else if (tree_int_cst_lt (n->high, val))
+ n = n->right;
+
+ else
{
- if (tree_int_cst_equal (val, TREE_VALUE (t)))
- BITARRAY_SET (cases_seen, xlo);
+ /* We have found a matching range. */
+ BITARRAY_SET (cases_seen, xlo);
+ break;
}
}
- else
+ while (n);
+ }
+ }
+ else
+ {
+ if (root->left)
+ case_stack->data.case_stmt.case_list = root = case_tree2list (root, 0);
+ for (n = root; n; n = n->right)
+ {
+ TREE_INT_CST_LOW (val) = TREE_INT_CST_LOW (n->low);
+ TREE_INT_CST_HIGH (val) = TREE_INT_CST_HIGH (n->low);
+ while ( ! tree_int_cst_lt (n->high, val))
{
+ /* Calculate (into xlo) the "offset" of the integer (val).
+ The element with lowest value has offset 0, the next smallest
+ element has offset 1, etc. */
+
+ HOST_WIDE_INT xlo, xhi;
+ tree t;
if (sparseness && TYPE_VALUES (type) != NULL_TREE)
{
/* The TYPE_VALUES will be in increasing order, so
xlo++;
t = TREE_CHAIN (t);
if (t == next_node_to_try)
- break;
+ {
+ xlo = -1;
+ break;
+ }
}
}
else
if (xhi == 0 && xlo >= 0 && xlo < count)
BITARRAY_SET (cases_seen, xlo);
+ add_double (TREE_INT_CST_LOW (val), TREE_INT_CST_HIGH (val),
+ 1, 0,
+ &TREE_INT_CST_LOW (val), &TREE_INT_CST_HIGH (val));
}
- add_double (TREE_INT_CST_LOW (val), TREE_INT_CST_HIGH (val),
- 1, 0,
- &TREE_INT_CST_LOW (val), &TREE_INT_CST_HIGH (val));
}
}
}
/* The time complexity of this code is normally O(N), where
N being the number of members in the enumerated type.
However, if type is a ENUMERAL_TYPE whose values do not
- increase monotonically, quadratic time may be needed. */
+ increase monotonically, O(N*log(N)) time may be needed. */
mark_seen_cases (type, cases_seen, size, sparseness);
occur since C and C++ don't enforce type-checking of
assignments to enumeration variables. */
+ if (case_stack->data.case_stmt.case_list
+ && case_stack->data.case_stmt.case_list->left)
+ case_stack->data.case_stmt.case_list
+ = case_tree2list (case_stack->data.case_stmt.case_list, 0);
if (warn_switch)
for (n = case_stack->data.case_stmt.case_list; n; n = n->right)
{
before_case = get_last_insn ();
+ if (thiscase->data.case_stmt.case_list
+ && thiscase->data.case_stmt.case_list->left)
+ thiscase->data.case_stmt.case_list
+ = case_tree2list(thiscase->data.case_stmt.case_list, 0);
+
/* Simplify the case-list before we count it. */
group_case_nodes (thiscase->data.case_stmt.case_list);
|| count < CASE_VALUES_THRESHOLD
|| ((unsigned HOST_WIDE_INT) (TREE_INT_CST_LOW (range))
> 10 * count)
+#ifndef ASM_OUTPUT_ADDR_DIFF_ELT
+ || flag_pic
+#endif
|| TREE_CODE (index_expr) == INTEGER_CST
/* These will reduce to a constant. */
|| (TREE_CODE (index_expr) == CALL_EXPR
free_temp_slots ();
}
+/* Convert the tree NODE into a list linked by the right field, with the left
+ field zeroed. RIGHT is used for recursion; it is a list to be placed
+ rightmost in the resulting list. */
+
+static struct case_node *
+case_tree2list (node, right)
+ struct case_node *node, *right;
+{
+ struct case_node *left;
+
+ if (node->right)
+ right = case_tree2list (node->right, right);
+
+ node->right = right;
+ if (left = node->left)
+ {
+ node->left = 0;
+ return case_tree2list (left, node);
+ }
+
+ return node;
+}
/* Terminate a case statement. EXPR is the original index
expression. */
{
tree block = DECL_INITIAL (current_function_decl);
- /* There first block is for the function body, and does not have
- corresponding block notes. Don't include it in the block vector. */
- block = BLOCK_SUBBLOCKS (block);
-
block_vector = identify_blocks (block, get_insns ());
}
OSDN Git Service
