Daily bump.
[official-gcc.git] / gcc / stmt.c
blobaacb1840dec0735803130429c38f0dc14172d388
1 /* Expands front end tree to back end RTL for GCC
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
3 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file handles the generation of rtl code from tree structure
23 above the level of expressions, using subroutines in exp*.c and emit-rtl.c.
24 The functions whose names start with `expand_' are called by the
25 expander to generate RTL instructions for various kinds of constructs. */
27 #include "config.h"
28 #include "system.h"
29 #include "coretypes.h"
30 #include "tm.h"
32 #include "rtl.h"
33 #include "hard-reg-set.h"
34 #include "tree.h"
35 #include "tm_p.h"
36 #include "flags.h"
37 #include "except.h"
38 #include "function.h"
39 #include "insn-config.h"
40 #include "expr.h"
41 #include "libfuncs.h"
42 #include "recog.h"
43 #include "machmode.h"
44 #include "toplev.h"
45 #include "output.h"
46 #include "ggc.h"
47 #include "langhooks.h"
48 #include "predict.h"
49 #include "optabs.h"
50 #include "target.h"
51 #include "regs.h"
52 #include "alloc-pool.h"
54 /* Functions and data structures for expanding case statements. */
56 /* Case label structure, used to hold info on labels within case
57 statements. We handle "range" labels; for a single-value label
58 as in C, the high and low limits are the same.
60 We start with a vector of case nodes sorted in ascending order, and
61 the default label as the last element in the vector. Before expanding
62 to RTL, we transform this vector into a list linked via the RIGHT
63 fields in the case_node struct. Nodes with higher case values are
64 later in the list.
66 Switch statements can be output in three forms. A branch table is
67 used if there are more than a few labels and the labels are dense
68 within the range between the smallest and largest case value. If a
69 branch table is used, no further manipulations are done with the case
70 node chain.
72 The alternative to the use of a branch table is to generate a series
73 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
74 and PARENT fields to hold a binary tree. Initially the tree is
75 totally unbalanced, with everything on the right. We balance the tree
76 with nodes on the left having lower case values than the parent
77 and nodes on the right having higher values. We then output the tree
78 in order.
80 For very small, suitable switch statements, we can generate a series
81 of simple bit test and branches instead. */
83 struct case_node
85 struct case_node *left; /* Left son in binary tree */
86 struct case_node *right; /* Right son in binary tree; also node chain */
87 struct case_node *parent; /* Parent of node in binary tree */
88 tree low; /* Lowest index value for this label */
89 tree high; /* Highest index value for this label */
90 tree code_label; /* Label to jump to when node matches */
93 typedef struct case_node case_node;
94 typedef struct case_node *case_node_ptr;
96 /* These are used by estimate_case_costs and balance_case_nodes. */
98 /* This must be a signed type, and non-ANSI compilers lack signed char. */
99 static short cost_table_[129];
100 static int use_cost_table;
101 static int cost_table_initialized;
103 /* Special care is needed because we allow -1, but TREE_INT_CST_LOW
104 is unsigned. */
105 #define COST_TABLE(I) cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)]
107 static int n_occurrences (int, const char *);
108 static bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *);
109 static void expand_nl_goto_receiver (void);
110 static bool check_operand_nalternatives (tree, tree);
111 static bool check_unique_operand_names (tree, tree);
112 static char *resolve_operand_name_1 (char *, tree, tree);
113 static void expand_null_return_1 (void);
114 static void expand_value_return (rtx);
115 static int estimate_case_costs (case_node_ptr);
116 static bool lshift_cheap_p (void);
117 static int case_bit_test_cmp (const void *, const void *);
118 static void emit_case_bit_tests (tree, tree, tree, tree, case_node_ptr, rtx);
119 static void balance_case_nodes (case_node_ptr *, case_node_ptr);
120 static int node_has_low_bound (case_node_ptr, tree);
121 static int node_has_high_bound (case_node_ptr, tree);
122 static int node_is_bounded (case_node_ptr, tree);
123 static void emit_case_nodes (rtx, case_node_ptr, rtx, tree);
124 static struct case_node *add_case_node (struct case_node *, tree,
125 tree, tree, tree, alloc_pool);
128 /* Return the rtx-label that corresponds to a LABEL_DECL,
129 creating it if necessary. */
132 label_rtx (tree label)
134 gcc_assert (TREE_CODE (label) == LABEL_DECL);
136 if (!DECL_RTL_SET_P (label))
138 rtx r = gen_label_rtx ();
139 SET_DECL_RTL (label, r);
140 if (FORCED_LABEL (label) || DECL_NONLOCAL (label))
141 LABEL_PRESERVE_P (r) = 1;
144 return DECL_RTL (label);
147 /* As above, but also put it on the forced-reference list of the
148 function that contains it. */
150 force_label_rtx (tree label)
152 rtx ref = label_rtx (label);
153 tree function = decl_function_context (label);
154 struct function *p;
156 gcc_assert (function);
158 if (function != current_function_decl)
159 p = find_function_data (function);
160 else
161 p = cfun;
163 p->expr->x_forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref,
164 p->expr->x_forced_labels);
165 return ref;
168 /* Add an unconditional jump to LABEL as the next sequential instruction. */
170 void
171 emit_jump (rtx label)
173 do_pending_stack_adjust ();
174 emit_jump_insn (gen_jump (label));
175 emit_barrier ();
178 /* Emit code to jump to the address
179 specified by the pointer expression EXP. */
181 void
182 expand_computed_goto (tree exp)
184 rtx x = expand_normal (exp);
186 x = convert_memory_address (Pmode, x);
188 do_pending_stack_adjust ();
189 emit_indirect_jump (x);
192 /* Handle goto statements and the labels that they can go to. */
194 /* Specify the location in the RTL code of a label LABEL,
195 which is a LABEL_DECL tree node.
197 This is used for the kind of label that the user can jump to with a
198 goto statement, and for alternatives of a switch or case statement.
199 RTL labels generated for loops and conditionals don't go through here;
200 they are generated directly at the RTL level, by other functions below.
202 Note that this has nothing to do with defining label *names*.
203 Languages vary in how they do that and what that even means. */
205 void
206 expand_label (tree label)
208 rtx label_r = label_rtx (label);
210 do_pending_stack_adjust ();
211 emit_label (label_r);
212 if (DECL_NAME (label))
213 LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label));
215 if (DECL_NONLOCAL (label))
217 expand_nl_goto_receiver ();
218 nonlocal_goto_handler_labels
219 = gen_rtx_EXPR_LIST (VOIDmode, label_r,
220 nonlocal_goto_handler_labels);
223 if (FORCED_LABEL (label))
224 forced_labels = gen_rtx_EXPR_LIST (VOIDmode, label_r, forced_labels);
226 if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
227 maybe_set_first_label_num (label_r);
230 /* Generate RTL code for a `goto' statement with target label LABEL.
231 LABEL should be a LABEL_DECL tree node that was or will later be
232 defined with `expand_label'. */
234 void
235 expand_goto (tree label)
237 #ifdef ENABLE_CHECKING
238 /* Check for a nonlocal goto to a containing function. Should have
239 gotten translated to __builtin_nonlocal_goto. */
240 tree context = decl_function_context (label);
241 gcc_assert (!context || context == current_function_decl);
242 #endif
244 emit_jump (label_rtx (label));
247 /* Return the number of times character C occurs in string S. */
248 static int
249 n_occurrences (int c, const char *s)
251 int n = 0;
252 while (*s)
253 n += (*s++ == c);
254 return n;
257 /* Generate RTL for an asm statement (explicit assembler code).
258 STRING is a STRING_CST node containing the assembler code text,
259 or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the
260 insn is volatile; don't optimize it. */
262 static void
263 expand_asm_loc (tree string, int vol, location_t locus)
265 rtx body;
267 if (TREE_CODE (string) == ADDR_EXPR)
268 string = TREE_OPERAND (string, 0);
270 body = gen_rtx_ASM_INPUT_loc (VOIDmode,
271 ggc_strdup (TREE_STRING_POINTER (string)),
272 locus);
274 MEM_VOLATILE_P (body) = vol;
276 emit_insn (body);
279 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
280 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
281 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
282 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
283 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
284 constraint allows the use of a register operand. And, *IS_INOUT
285 will be true if the operand is read-write, i.e., if it is used as
286 an input as well as an output. If *CONSTRAINT_P is not in
287 canonical form, it will be made canonical. (Note that `+' will be
288 replaced with `=' as part of this process.)
290 Returns TRUE if all went well; FALSE if an error occurred. */
292 bool
293 parse_output_constraint (const char **constraint_p, int operand_num,
294 int ninputs, int noutputs, bool *allows_mem,
295 bool *allows_reg, bool *is_inout)
297 const char *constraint = *constraint_p;
298 const char *p;
300 /* Assume the constraint doesn't allow the use of either a register
301 or memory. */
302 *allows_mem = false;
303 *allows_reg = false;
305 /* Allow the `=' or `+' to not be at the beginning of the string,
306 since it wasn't explicitly documented that way, and there is a
307 large body of code that puts it last. Swap the character to
308 the front, so as not to uglify any place else. */
309 p = strchr (constraint, '=');
310 if (!p)
311 p = strchr (constraint, '+');
313 /* If the string doesn't contain an `=', issue an error
314 message. */
315 if (!p)
317 error ("output operand constraint lacks %<=%>");
318 return false;
321 /* If the constraint begins with `+', then the operand is both read
322 from and written to. */
323 *is_inout = (*p == '+');
325 /* Canonicalize the output constraint so that it begins with `='. */
326 if (p != constraint || *is_inout)
328 char *buf;
329 size_t c_len = strlen (constraint);
331 if (p != constraint)
332 warning (0, "output constraint %qc for operand %d "
333 "is not at the beginning",
334 *p, operand_num);
336 /* Make a copy of the constraint. */
337 buf = alloca (c_len + 1);
338 strcpy (buf, constraint);
339 /* Swap the first character and the `=' or `+'. */
340 buf[p - constraint] = buf[0];
341 /* Make sure the first character is an `='. (Until we do this,
342 it might be a `+'.) */
343 buf[0] = '=';
344 /* Replace the constraint with the canonicalized string. */
345 *constraint_p = ggc_alloc_string (buf, c_len);
346 constraint = *constraint_p;
349 /* Loop through the constraint string. */
350 for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p))
351 switch (*p)
353 case '+':
354 case '=':
355 error ("operand constraint contains incorrectly positioned "
356 "%<+%> or %<=%>");
357 return false;
359 case '%':
360 if (operand_num + 1 == ninputs + noutputs)
362 error ("%<%%%> constraint used with last operand");
363 return false;
365 break;
367 case 'V': case 'm': case 'o':
368 *allows_mem = true;
369 break;
371 case '?': case '!': case '*': case '&': case '#':
372 case 'E': case 'F': case 'G': case 'H':
373 case 's': case 'i': case 'n':
374 case 'I': case 'J': case 'K': case 'L': case 'M':
375 case 'N': case 'O': case 'P': case ',':
376 break;
378 case '0': case '1': case '2': case '3': case '4':
379 case '5': case '6': case '7': case '8': case '9':
380 case '[':
381 error ("matching constraint not valid in output operand");
382 return false;
384 case '<': case '>':
385 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
386 excepting those that expand_call created. So match memory
387 and hope. */
388 *allows_mem = true;
389 break;
391 case 'g': case 'X':
392 *allows_reg = true;
393 *allows_mem = true;
394 break;
396 case 'p': case 'r':
397 *allows_reg = true;
398 break;
400 default:
401 if (!ISALPHA (*p))
402 break;
403 if (REG_CLASS_FROM_CONSTRAINT (*p, p) != NO_REGS)
404 *allows_reg = true;
405 #ifdef EXTRA_CONSTRAINT_STR
406 else if (EXTRA_ADDRESS_CONSTRAINT (*p, p))
407 *allows_reg = true;
408 else if (EXTRA_MEMORY_CONSTRAINT (*p, p))
409 *allows_mem = true;
410 else
412 /* Otherwise we can't assume anything about the nature of
413 the constraint except that it isn't purely registers.
414 Treat it like "g" and hope for the best. */
415 *allows_reg = true;
416 *allows_mem = true;
418 #endif
419 break;
422 return true;
425 /* Similar, but for input constraints. */
427 bool
428 parse_input_constraint (const char **constraint_p, int input_num,
429 int ninputs, int noutputs, int ninout,
430 const char * const * constraints,
431 bool *allows_mem, bool *allows_reg)
433 const char *constraint = *constraint_p;
434 const char *orig_constraint = constraint;
435 size_t c_len = strlen (constraint);
436 size_t j;
437 bool saw_match = false;
439 /* Assume the constraint doesn't allow the use of either
440 a register or memory. */
441 *allows_mem = false;
442 *allows_reg = false;
444 /* Make sure constraint has neither `=', `+', nor '&'. */
446 for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
447 switch (constraint[j])
449 case '+': case '=': case '&':
450 if (constraint == orig_constraint)
452 error ("input operand constraint contains %qc", constraint[j]);
453 return false;
455 break;
457 case '%':
458 if (constraint == orig_constraint
459 && input_num + 1 == ninputs - ninout)
461 error ("%<%%%> constraint used with last operand");
462 return false;
464 break;
466 case 'V': case 'm': case 'o':
467 *allows_mem = true;
468 break;
470 case '<': case '>':
471 case '?': case '!': case '*': case '#':
472 case 'E': case 'F': case 'G': case 'H':
473 case 's': case 'i': case 'n':
474 case 'I': case 'J': case 'K': case 'L': case 'M':
475 case 'N': case 'O': case 'P': case ',':
476 break;
478 /* Whether or not a numeric constraint allows a register is
479 decided by the matching constraint, and so there is no need
480 to do anything special with them. We must handle them in
481 the default case, so that we don't unnecessarily force
482 operands to memory. */
483 case '0': case '1': case '2': case '3': case '4':
484 case '5': case '6': case '7': case '8': case '9':
486 char *end;
487 unsigned long match;
489 saw_match = true;
491 match = strtoul (constraint + j, &end, 10);
492 if (match >= (unsigned long) noutputs)
494 error ("matching constraint references invalid operand number");
495 return false;
498 /* Try and find the real constraint for this dup. Only do this
499 if the matching constraint is the only alternative. */
500 if (*end == '\0'
501 && (j == 0 || (j == 1 && constraint[0] == '%')))
503 constraint = constraints[match];
504 *constraint_p = constraint;
505 c_len = strlen (constraint);
506 j = 0;
507 /* ??? At the end of the loop, we will skip the first part of
508 the matched constraint. This assumes not only that the
509 other constraint is an output constraint, but also that
510 the '=' or '+' come first. */
511 break;
513 else
514 j = end - constraint;
515 /* Anticipate increment at end of loop. */
516 j--;
518 /* Fall through. */
520 case 'p': case 'r':
521 *allows_reg = true;
522 break;
524 case 'g': case 'X':
525 *allows_reg = true;
526 *allows_mem = true;
527 break;
529 default:
530 if (! ISALPHA (constraint[j]))
532 error ("invalid punctuation %qc in constraint", constraint[j]);
533 return false;
535 if (REG_CLASS_FROM_CONSTRAINT (constraint[j], constraint + j)
536 != NO_REGS)
537 *allows_reg = true;
538 #ifdef EXTRA_CONSTRAINT_STR
539 else if (EXTRA_ADDRESS_CONSTRAINT (constraint[j], constraint + j))
540 *allows_reg = true;
541 else if (EXTRA_MEMORY_CONSTRAINT (constraint[j], constraint + j))
542 *allows_mem = true;
543 else
545 /* Otherwise we can't assume anything about the nature of
546 the constraint except that it isn't purely registers.
547 Treat it like "g" and hope for the best. */
548 *allows_reg = true;
549 *allows_mem = true;
551 #endif
552 break;
555 if (saw_match && !*allows_reg)
556 warning (0, "matching constraint does not allow a register");
558 return true;
561 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
562 can be an asm-declared register. Called via walk_tree. */
564 static tree
565 decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED,
566 void *data)
568 tree decl = *declp;
569 const HARD_REG_SET *regs = data;
571 if (TREE_CODE (decl) == VAR_DECL)
573 if (DECL_HARD_REGISTER (decl)
574 && REG_P (DECL_RTL (decl))
575 && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
577 rtx reg = DECL_RTL (decl);
579 if (overlaps_hard_reg_set_p (*regs, GET_MODE (reg), REGNO (reg)))
580 return decl;
582 walk_subtrees = 0;
584 else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL)
585 walk_subtrees = 0;
586 return NULL_TREE;
589 /* If there is an overlap between *REGS and DECL, return the first overlap
590 found. */
591 tree
592 tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs)
594 return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL);
597 /* Check for overlap between registers marked in CLOBBERED_REGS and
598 anything inappropriate in T. Emit error and return the register
599 variable definition for error, NULL_TREE for ok. */
601 static bool
602 tree_conflicts_with_clobbers_p (tree t, HARD_REG_SET *clobbered_regs)
604 /* Conflicts between asm-declared register variables and the clobber
605 list are not allowed. */
606 tree overlap = tree_overlaps_hard_reg_set (t, clobbered_regs);
608 if (overlap)
610 error ("asm-specifier for variable %qs conflicts with asm clobber list",
611 IDENTIFIER_POINTER (DECL_NAME (overlap)));
613 /* Reset registerness to stop multiple errors emitted for a single
614 variable. */
615 DECL_REGISTER (overlap) = 0;
616 return true;
619 return false;
622 /* Generate RTL for an asm statement with arguments.
623 STRING is the instruction template.
624 OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs.
625 Each output or input has an expression in the TREE_VALUE and
626 and a tree list in TREE_PURPOSE which in turn contains a constraint
627 name in TREE_VALUE (or NULL_TREE) and a constraint string
628 in TREE_PURPOSE.
629 CLOBBERS is a list of STRING_CST nodes each naming a hard register
630 that is clobbered by this insn.
632 Not all kinds of lvalue that may appear in OUTPUTS can be stored directly.
633 Some elements of OUTPUTS may be replaced with trees representing temporary
634 values. The caller should copy those temporary values to the originally
635 specified lvalues.
637 VOL nonzero means the insn is volatile; don't optimize it. */
639 static void
640 expand_asm_operands (tree string, tree outputs, tree inputs,
641 tree clobbers, int vol, location_t locus)
643 rtvec argvec, constraintvec;
644 rtx body;
645 int ninputs = list_length (inputs);
646 int noutputs = list_length (outputs);
647 int ninout;
648 int nclobbers;
649 HARD_REG_SET clobbered_regs;
650 int clobber_conflict_found = 0;
651 tree tail;
652 tree t;
653 int i;
654 /* Vector of RTX's of evaluated output operands. */
655 rtx *output_rtx = alloca (noutputs * sizeof (rtx));
656 int *inout_opnum = alloca (noutputs * sizeof (int));
657 rtx *real_output_rtx = alloca (noutputs * sizeof (rtx));
658 enum machine_mode *inout_mode
659 = alloca (noutputs * sizeof (enum machine_mode));
660 const char **constraints
661 = alloca ((noutputs + ninputs) * sizeof (const char *));
662 int old_generating_concat_p = generating_concat_p;
664 /* An ASM with no outputs needs to be treated as volatile, for now. */
665 if (noutputs == 0)
666 vol = 1;
668 if (! check_operand_nalternatives (outputs, inputs))
669 return;
671 string = resolve_asm_operand_names (string, outputs, inputs);
673 /* Collect constraints. */
674 i = 0;
675 for (t = outputs; t ; t = TREE_CHAIN (t), i++)
676 constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
677 for (t = inputs; t ; t = TREE_CHAIN (t), i++)
678 constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
680 /* Sometimes we wish to automatically clobber registers across an asm.
681 Case in point is when the i386 backend moved from cc0 to a hard reg --
682 maintaining source-level compatibility means automatically clobbering
683 the flags register. */
684 clobbers = targetm.md_asm_clobbers (outputs, inputs, clobbers);
686 /* Count the number of meaningful clobbered registers, ignoring what
687 we would ignore later. */
688 nclobbers = 0;
689 CLEAR_HARD_REG_SET (clobbered_regs);
690 for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
692 const char *regname;
694 if (TREE_VALUE (tail) == error_mark_node)
695 return;
696 regname = TREE_STRING_POINTER (TREE_VALUE (tail));
698 i = decode_reg_name (regname);
699 if (i >= 0 || i == -4)
700 ++nclobbers;
701 else if (i == -2)
702 error ("unknown register name %qs in %<asm%>", regname);
704 /* Mark clobbered registers. */
705 if (i >= 0)
707 /* Clobbering the PIC register is an error. */
708 if (i == (int) PIC_OFFSET_TABLE_REGNUM)
710 error ("PIC register %qs clobbered in %<asm%>", regname);
711 return;
714 SET_HARD_REG_BIT (clobbered_regs, i);
718 /* First pass over inputs and outputs checks validity and sets
719 mark_addressable if needed. */
721 ninout = 0;
722 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
724 tree val = TREE_VALUE (tail);
725 tree type = TREE_TYPE (val);
726 const char *constraint;
727 bool is_inout;
728 bool allows_reg;
729 bool allows_mem;
731 /* If there's an erroneous arg, emit no insn. */
732 if (type == error_mark_node)
733 return;
735 /* Try to parse the output constraint. If that fails, there's
736 no point in going further. */
737 constraint = constraints[i];
738 if (!parse_output_constraint (&constraint, i, ninputs, noutputs,
739 &allows_mem, &allows_reg, &is_inout))
740 return;
742 if (! allows_reg
743 && (allows_mem
744 || is_inout
745 || (DECL_P (val)
746 && REG_P (DECL_RTL (val))
747 && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))))
748 lang_hooks.mark_addressable (val);
750 if (is_inout)
751 ninout++;
754 ninputs += ninout;
755 if (ninputs + noutputs > MAX_RECOG_OPERANDS)
757 error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS);
758 return;
761 for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail))
763 bool allows_reg, allows_mem;
764 const char *constraint;
766 /* If there's an erroneous arg, emit no insn, because the ASM_INPUT
767 would get VOIDmode and that could cause a crash in reload. */
768 if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node)
769 return;
771 constraint = constraints[i + noutputs];
772 if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
773 constraints, &allows_mem, &allows_reg))
774 return;
776 if (! allows_reg && allows_mem)
777 lang_hooks.mark_addressable (TREE_VALUE (tail));
780 /* Second pass evaluates arguments. */
782 ninout = 0;
783 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
785 tree val = TREE_VALUE (tail);
786 tree type = TREE_TYPE (val);
787 bool is_inout;
788 bool allows_reg;
789 bool allows_mem;
790 rtx op;
791 bool ok;
793 ok = parse_output_constraint (&constraints[i], i, ninputs,
794 noutputs, &allows_mem, &allows_reg,
795 &is_inout);
796 gcc_assert (ok);
798 /* If an output operand is not a decl or indirect ref and our constraint
799 allows a register, make a temporary to act as an intermediate.
800 Make the asm insn write into that, then our caller will copy it to
801 the real output operand. Likewise for promoted variables. */
803 generating_concat_p = 0;
805 real_output_rtx[i] = NULL_RTX;
806 if ((TREE_CODE (val) == INDIRECT_REF
807 && allows_mem)
808 || (DECL_P (val)
809 && (allows_mem || REG_P (DECL_RTL (val)))
810 && ! (REG_P (DECL_RTL (val))
811 && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))
812 || ! allows_reg
813 || is_inout)
815 op = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE);
816 if (MEM_P (op))
817 op = validize_mem (op);
819 if (! allows_reg && !MEM_P (op))
820 error ("output number %d not directly addressable", i);
821 if ((! allows_mem && MEM_P (op))
822 || GET_CODE (op) == CONCAT)
824 real_output_rtx[i] = op;
825 op = gen_reg_rtx (GET_MODE (op));
826 if (is_inout)
827 emit_move_insn (op, real_output_rtx[i]);
830 else
832 op = assign_temp (type, 0, 0, 1);
833 op = validize_mem (op);
834 TREE_VALUE (tail) = make_tree (type, op);
836 output_rtx[i] = op;
838 generating_concat_p = old_generating_concat_p;
840 if (is_inout)
842 inout_mode[ninout] = TYPE_MODE (type);
843 inout_opnum[ninout++] = i;
846 if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
847 clobber_conflict_found = 1;
850 /* Make vectors for the expression-rtx, constraint strings,
851 and named operands. */
853 argvec = rtvec_alloc (ninputs);
854 constraintvec = rtvec_alloc (ninputs);
856 body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode
857 : GET_MODE (output_rtx[0])),
858 ggc_strdup (TREE_STRING_POINTER (string)),
859 empty_string, 0, argvec, constraintvec,
860 locus);
862 MEM_VOLATILE_P (body) = vol;
864 /* Eval the inputs and put them into ARGVEC.
865 Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */
867 for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i)
869 bool allows_reg, allows_mem;
870 const char *constraint;
871 tree val, type;
872 rtx op;
873 bool ok;
875 constraint = constraints[i + noutputs];
876 ok = parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
877 constraints, &allows_mem, &allows_reg);
878 gcc_assert (ok);
880 generating_concat_p = 0;
882 val = TREE_VALUE (tail);
883 type = TREE_TYPE (val);
884 /* EXPAND_INITIALIZER will not generate code for valid initializer
885 constants, but will still generate code for other types of operand.
886 This is the behavior we want for constant constraints. */
887 op = expand_expr (val, NULL_RTX, VOIDmode,
888 allows_reg ? EXPAND_NORMAL
889 : allows_mem ? EXPAND_MEMORY
890 : EXPAND_INITIALIZER);
892 /* Never pass a CONCAT to an ASM. */
893 if (GET_CODE (op) == CONCAT)
894 op = force_reg (GET_MODE (op), op);
895 else if (MEM_P (op))
896 op = validize_mem (op);
898 if (asm_operand_ok (op, constraint) <= 0)
900 if (allows_reg && TYPE_MODE (type) != BLKmode)
901 op = force_reg (TYPE_MODE (type), op);
902 else if (!allows_mem)
903 warning (0, "asm operand %d probably doesn%'t match constraints",
904 i + noutputs);
905 else if (MEM_P (op))
907 /* We won't recognize either volatile memory or memory
908 with a queued address as available a memory_operand
909 at this point. Ignore it: clearly this *is* a memory. */
911 else
913 warning (0, "use of memory input without lvalue in "
914 "asm operand %d is deprecated", i + noutputs);
916 if (CONSTANT_P (op))
918 rtx mem = force_const_mem (TYPE_MODE (type), op);
919 if (mem)
920 op = validize_mem (mem);
921 else
922 op = force_reg (TYPE_MODE (type), op);
924 if (REG_P (op)
925 || GET_CODE (op) == SUBREG
926 || GET_CODE (op) == CONCAT)
928 tree qual_type = build_qualified_type (type,
929 (TYPE_QUALS (type)
930 | TYPE_QUAL_CONST));
931 rtx memloc = assign_temp (qual_type, 1, 1, 1);
932 memloc = validize_mem (memloc);
933 emit_move_insn (memloc, op);
934 op = memloc;
939 generating_concat_p = old_generating_concat_p;
940 ASM_OPERANDS_INPUT (body, i) = op;
942 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i)
943 = gen_rtx_ASM_INPUT (TYPE_MODE (type),
944 ggc_strdup (constraints[i + noutputs]));
946 if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
947 clobber_conflict_found = 1;
950 /* Protect all the operands from the queue now that they have all been
951 evaluated. */
953 generating_concat_p = 0;
955 /* For in-out operands, copy output rtx to input rtx. */
956 for (i = 0; i < ninout; i++)
958 int j = inout_opnum[i];
959 char buffer[16];
961 ASM_OPERANDS_INPUT (body, ninputs - ninout + i)
962 = output_rtx[j];
964 sprintf (buffer, "%d", j);
965 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i)
966 = gen_rtx_ASM_INPUT (inout_mode[i], ggc_strdup (buffer));
969 generating_concat_p = old_generating_concat_p;
971 /* Now, for each output, construct an rtx
972 (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER
973 ARGVEC CONSTRAINTS OPNAMES))
974 If there is more than one, put them inside a PARALLEL. */
976 if (noutputs == 1 && nclobbers == 0)
978 ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = ggc_strdup (constraints[0]);
979 emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body));
982 else if (noutputs == 0 && nclobbers == 0)
984 /* No output operands: put in a raw ASM_OPERANDS rtx. */
985 emit_insn (body);
988 else
990 rtx obody = body;
991 int num = noutputs;
993 if (num == 0)
994 num = 1;
996 body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers));
998 /* For each output operand, store a SET. */
999 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1001 XVECEXP (body, 0, i)
1002 = gen_rtx_SET (VOIDmode,
1003 output_rtx[i],
1004 gen_rtx_ASM_OPERANDS
1005 (GET_MODE (output_rtx[i]),
1006 ggc_strdup (TREE_STRING_POINTER (string)),
1007 ggc_strdup (constraints[i]),
1008 i, argvec, constraintvec, locus));
1010 MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol;
1013 /* If there are no outputs (but there are some clobbers)
1014 store the bare ASM_OPERANDS into the PARALLEL. */
1016 if (i == 0)
1017 XVECEXP (body, 0, i++) = obody;
1019 /* Store (clobber REG) for each clobbered register specified. */
1021 for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
1023 const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
1024 int j = decode_reg_name (regname);
1025 rtx clobbered_reg;
1027 if (j < 0)
1029 if (j == -3) /* `cc', which is not a register */
1030 continue;
1032 if (j == -4) /* `memory', don't cache memory across asm */
1034 XVECEXP (body, 0, i++)
1035 = gen_rtx_CLOBBER (VOIDmode,
1036 gen_rtx_MEM
1037 (BLKmode,
1038 gen_rtx_SCRATCH (VOIDmode)));
1039 continue;
1042 /* Ignore unknown register, error already signaled. */
1043 continue;
1046 /* Use QImode since that's guaranteed to clobber just one reg. */
1047 clobbered_reg = gen_rtx_REG (QImode, j);
1049 /* Do sanity check for overlap between clobbers and respectively
1050 input and outputs that hasn't been handled. Such overlap
1051 should have been detected and reported above. */
1052 if (!clobber_conflict_found)
1054 int opno;
1056 /* We test the old body (obody) contents to avoid tripping
1057 over the under-construction body. */
1058 for (opno = 0; opno < noutputs; opno++)
1059 if (reg_overlap_mentioned_p (clobbered_reg, output_rtx[opno]))
1060 internal_error ("asm clobber conflict with output operand");
1062 for (opno = 0; opno < ninputs - ninout; opno++)
1063 if (reg_overlap_mentioned_p (clobbered_reg,
1064 ASM_OPERANDS_INPUT (obody, opno)))
1065 internal_error ("asm clobber conflict with input operand");
1068 XVECEXP (body, 0, i++)
1069 = gen_rtx_CLOBBER (VOIDmode, clobbered_reg);
1072 emit_insn (body);
1075 /* For any outputs that needed reloading into registers, spill them
1076 back to where they belong. */
1077 for (i = 0; i < noutputs; ++i)
1078 if (real_output_rtx[i])
1079 emit_move_insn (real_output_rtx[i], output_rtx[i]);
1081 cfun->has_asm_statement = 1;
1082 free_temp_slots ();
1085 void
1086 expand_asm_expr (tree exp)
1088 int noutputs, i;
1089 tree outputs, tail;
1090 tree *o;
1092 if (ASM_INPUT_P (exp))
1094 expand_asm_loc (ASM_STRING (exp), ASM_VOLATILE_P (exp), input_location);
1095 return;
1098 outputs = ASM_OUTPUTS (exp);
1099 noutputs = list_length (outputs);
1100 /* o[I] is the place that output number I should be written. */
1101 o = (tree *) alloca (noutputs * sizeof (tree));
1103 /* Record the contents of OUTPUTS before it is modified. */
1104 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1105 o[i] = TREE_VALUE (tail);
1107 /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of
1108 OUTPUTS some trees for where the values were actually stored. */
1109 expand_asm_operands (ASM_STRING (exp), outputs, ASM_INPUTS (exp),
1110 ASM_CLOBBERS (exp), ASM_VOLATILE_P (exp),
1111 input_location);
1113 /* Copy all the intermediate outputs into the specified outputs. */
1114 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1116 if (o[i] != TREE_VALUE (tail))
1118 expand_assignment (o[i], TREE_VALUE (tail), false);
1119 free_temp_slots ();
1121 /* Restore the original value so that it's correct the next
1122 time we expand this function. */
1123 TREE_VALUE (tail) = o[i];
1128 /* A subroutine of expand_asm_operands. Check that all operands have
1129 the same number of alternatives. Return true if so. */
1131 static bool
1132 check_operand_nalternatives (tree outputs, tree inputs)
1134 if (outputs || inputs)
1136 tree tmp = TREE_PURPOSE (outputs ? outputs : inputs);
1137 int nalternatives
1138 = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp)));
1139 tree next = inputs;
1141 if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES)
1143 error ("too many alternatives in %<asm%>");
1144 return false;
1147 tmp = outputs;
1148 while (tmp)
1150 const char *constraint
1151 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp)));
1153 if (n_occurrences (',', constraint) != nalternatives)
1155 error ("operand constraints for %<asm%> differ "
1156 "in number of alternatives");
1157 return false;
1160 if (TREE_CHAIN (tmp))
1161 tmp = TREE_CHAIN (tmp);
1162 else
1163 tmp = next, next = 0;
1167 return true;
1170 /* A subroutine of expand_asm_operands. Check that all operand names
1171 are unique. Return true if so. We rely on the fact that these names
1172 are identifiers, and so have been canonicalized by get_identifier,
1173 so all we need are pointer comparisons. */
1175 static bool
1176 check_unique_operand_names (tree outputs, tree inputs)
1178 tree i, j;
1180 for (i = outputs; i ; i = TREE_CHAIN (i))
1182 tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1183 if (! i_name)
1184 continue;
1186 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1187 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1188 goto failure;
1191 for (i = inputs; i ; i = TREE_CHAIN (i))
1193 tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1194 if (! i_name)
1195 continue;
1197 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1198 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1199 goto failure;
1200 for (j = outputs; j ; j = TREE_CHAIN (j))
1201 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1202 goto failure;
1205 return true;
1207 failure:
1208 error ("duplicate asm operand name %qs",
1209 TREE_STRING_POINTER (TREE_PURPOSE (TREE_PURPOSE (i))));
1210 return false;
1213 /* A subroutine of expand_asm_operands. Resolve the names of the operands
1214 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
1215 STRING and in the constraints to those numbers. */
1217 tree
1218 resolve_asm_operand_names (tree string, tree outputs, tree inputs)
1220 char *buffer;
1221 char *p;
1222 const char *c;
1223 tree t;
1225 check_unique_operand_names (outputs, inputs);
1227 /* Substitute [<name>] in input constraint strings. There should be no
1228 named operands in output constraints. */
1229 for (t = inputs; t ; t = TREE_CHAIN (t))
1231 c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
1232 if (strchr (c, '[') != NULL)
1234 p = buffer = xstrdup (c);
1235 while ((p = strchr (p, '[')) != NULL)
1236 p = resolve_operand_name_1 (p, outputs, inputs);
1237 TREE_VALUE (TREE_PURPOSE (t))
1238 = build_string (strlen (buffer), buffer);
1239 free (buffer);
1243 /* Now check for any needed substitutions in the template. */
1244 c = TREE_STRING_POINTER (string);
1245 while ((c = strchr (c, '%')) != NULL)
1247 if (c[1] == '[')
1248 break;
1249 else if (ISALPHA (c[1]) && c[2] == '[')
1250 break;
1251 else
1253 c += 1;
1254 continue;
1258 if (c)
1260 /* OK, we need to make a copy so we can perform the substitutions.
1261 Assume that we will not need extra space--we get to remove '['
1262 and ']', which means we cannot have a problem until we have more
1263 than 999 operands. */
1264 buffer = xstrdup (TREE_STRING_POINTER (string));
1265 p = buffer + (c - TREE_STRING_POINTER (string));
1267 while ((p = strchr (p, '%')) != NULL)
1269 if (p[1] == '[')
1270 p += 1;
1271 else if (ISALPHA (p[1]) && p[2] == '[')
1272 p += 2;
1273 else
1275 p += 1;
1276 continue;
1279 p = resolve_operand_name_1 (p, outputs, inputs);
1282 string = build_string (strlen (buffer), buffer);
1283 free (buffer);
1286 return string;
1289 /* A subroutine of resolve_operand_names. P points to the '[' for a
1290 potential named operand of the form [<name>]. In place, replace
1291 the name and brackets with a number. Return a pointer to the
1292 balance of the string after substitution. */
1294 static char *
1295 resolve_operand_name_1 (char *p, tree outputs, tree inputs)
1297 char *q;
1298 int op;
1299 tree t;
1300 size_t len;
1302 /* Collect the operand name. */
1303 q = strchr (p, ']');
1304 if (!q)
1306 error ("missing close brace for named operand");
1307 return strchr (p, '\0');
1309 len = q - p - 1;
1311 /* Resolve the name to a number. */
1312 for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
1314 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1315 if (name)
1317 const char *c = TREE_STRING_POINTER (name);
1318 if (strncmp (c, p + 1, len) == 0 && c[len] == '\0')
1319 goto found;
1322 for (t = inputs; t ; t = TREE_CHAIN (t), op++)
1324 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1325 if (name)
1327 const char *c = TREE_STRING_POINTER (name);
1328 if (strncmp (c, p + 1, len) == 0 && c[len] == '\0')
1329 goto found;
1333 *q = '\0';
1334 error ("undefined named operand %qs", p + 1);
1335 op = 0;
1336 found:
1338 /* Replace the name with the number. Unfortunately, not all libraries
1339 get the return value of sprintf correct, so search for the end of the
1340 generated string by hand. */
1341 sprintf (p, "%d", op);
1342 p = strchr (p, '\0');
1344 /* Verify the no extra buffer space assumption. */
1345 gcc_assert (p <= q);
1347 /* Shift the rest of the buffer down to fill the gap. */
1348 memmove (p, q + 1, strlen (q + 1) + 1);
1350 return p;
1353 /* Generate RTL to evaluate the expression EXP. */
1355 void
1356 expand_expr_stmt (tree exp)
1358 rtx value;
1359 tree type;
1361 value = expand_expr (exp, const0_rtx, VOIDmode, EXPAND_NORMAL);
1362 if (GIMPLE_TUPLE_P (exp))
1363 type = void_type_node;
1364 else
1365 type = TREE_TYPE (exp);
1367 /* If all we do is reference a volatile value in memory,
1368 copy it to a register to be sure it is actually touched. */
1369 if (value && MEM_P (value) && TREE_THIS_VOLATILE (exp))
1371 if (TYPE_MODE (type) == VOIDmode)
1373 else if (TYPE_MODE (type) != BLKmode)
1374 value = copy_to_reg (value);
1375 else
1377 rtx lab = gen_label_rtx ();
1379 /* Compare the value with itself to reference it. */
1380 emit_cmp_and_jump_insns (value, value, EQ,
1381 expand_normal (TYPE_SIZE (type)),
1382 BLKmode, 0, lab);
1383 emit_label (lab);
1387 /* Free any temporaries used to evaluate this expression. */
1388 free_temp_slots ();
1391 /* Warn if EXP contains any computations whose results are not used.
1392 Return 1 if a warning is printed; 0 otherwise. LOCUS is the
1393 (potential) location of the expression. */
1396 warn_if_unused_value (const_tree exp, location_t locus)
1398 restart:
1399 if (TREE_USED (exp) || TREE_NO_WARNING (exp))
1400 return 0;
1402 /* Don't warn about void constructs. This includes casting to void,
1403 void function calls, and statement expressions with a final cast
1404 to void. */
1405 if (VOID_TYPE_P (TREE_TYPE (exp)))
1406 return 0;
1408 if (EXPR_HAS_LOCATION (exp))
1409 locus = EXPR_LOCATION (exp);
1411 switch (TREE_CODE (exp))
1413 case PREINCREMENT_EXPR:
1414 case POSTINCREMENT_EXPR:
1415 case PREDECREMENT_EXPR:
1416 case POSTDECREMENT_EXPR:
1417 case MODIFY_EXPR:
1418 case GIMPLE_MODIFY_STMT:
1419 case INIT_EXPR:
1420 case TARGET_EXPR:
1421 case CALL_EXPR:
1422 case TRY_CATCH_EXPR:
1423 case WITH_CLEANUP_EXPR:
1424 case EXIT_EXPR:
1425 case VA_ARG_EXPR:
1426 return 0;
1428 case BIND_EXPR:
1429 /* For a binding, warn if no side effect within it. */
1430 exp = BIND_EXPR_BODY (exp);
1431 goto restart;
1433 case SAVE_EXPR:
1434 exp = TREE_OPERAND (exp, 0);
1435 goto restart;
1437 case TRUTH_ORIF_EXPR:
1438 case TRUTH_ANDIF_EXPR:
1439 /* In && or ||, warn if 2nd operand has no side effect. */
1440 exp = TREE_OPERAND (exp, 1);
1441 goto restart;
1443 case COMPOUND_EXPR:
1444 if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus))
1445 return 1;
1446 /* Let people do `(foo (), 0)' without a warning. */
1447 if (TREE_CONSTANT (TREE_OPERAND (exp, 1)))
1448 return 0;
1449 exp = TREE_OPERAND (exp, 1);
1450 goto restart;
1452 case COND_EXPR:
1453 /* If this is an expression with side effects, don't warn; this
1454 case commonly appears in macro expansions. */
1455 if (TREE_SIDE_EFFECTS (exp))
1456 return 0;
1457 goto warn;
1459 case INDIRECT_REF:
1460 /* Don't warn about automatic dereferencing of references, since
1461 the user cannot control it. */
1462 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE)
1464 exp = TREE_OPERAND (exp, 0);
1465 goto restart;
1467 /* Fall through. */
1469 default:
1470 /* Referencing a volatile value is a side effect, so don't warn. */
1471 if ((DECL_P (exp) || REFERENCE_CLASS_P (exp))
1472 && TREE_THIS_VOLATILE (exp))
1473 return 0;
1475 /* If this is an expression which has no operands, there is no value
1476 to be unused. There are no such language-independent codes,
1477 but front ends may define such. */
1478 if (EXPRESSION_CLASS_P (exp) && TREE_OPERAND_LENGTH (exp) == 0)
1479 return 0;
1481 warn:
1482 warning (OPT_Wunused_value, "%Hvalue computed is not used", &locus);
1483 return 1;
1488 /* Generate RTL to return from the current function, with no value.
1489 (That is, we do not do anything about returning any value.) */
1491 void
1492 expand_null_return (void)
1494 /* If this function was declared to return a value, but we
1495 didn't, clobber the return registers so that they are not
1496 propagated live to the rest of the function. */
1497 clobber_return_register ();
1499 expand_null_return_1 ();
1502 /* Generate RTL to return directly from the current function.
1503 (That is, we bypass any return value.) */
1505 void
1506 expand_naked_return (void)
1508 rtx end_label;
1510 clear_pending_stack_adjust ();
1511 do_pending_stack_adjust ();
1513 end_label = naked_return_label;
1514 if (end_label == 0)
1515 end_label = naked_return_label = gen_label_rtx ();
1517 emit_jump (end_label);
1520 /* Generate RTL to return from the current function, with value VAL. */
1522 static void
1523 expand_value_return (rtx val)
1525 /* Copy the value to the return location
1526 unless it's already there. */
1528 rtx return_reg = DECL_RTL (DECL_RESULT (current_function_decl));
1529 if (return_reg != val)
1531 tree type = TREE_TYPE (DECL_RESULT (current_function_decl));
1532 if (targetm.calls.promote_function_return (TREE_TYPE (current_function_decl)))
1534 int unsignedp = TYPE_UNSIGNED (type);
1535 enum machine_mode old_mode
1536 = DECL_MODE (DECL_RESULT (current_function_decl));
1537 enum machine_mode mode
1538 = promote_mode (type, old_mode, &unsignedp, 1);
1540 if (mode != old_mode)
1541 val = convert_modes (mode, old_mode, val, unsignedp);
1543 if (GET_CODE (return_reg) == PARALLEL)
1544 emit_group_load (return_reg, val, type, int_size_in_bytes (type));
1545 else
1546 emit_move_insn (return_reg, val);
1549 expand_null_return_1 ();
1552 /* Output a return with no value. */
1554 static void
1555 expand_null_return_1 (void)
1557 clear_pending_stack_adjust ();
1558 do_pending_stack_adjust ();
1559 emit_jump (return_label);
1562 /* Generate RTL to evaluate the expression RETVAL and return it
1563 from the current function. */
1565 void
1566 expand_return (tree retval)
1568 rtx result_rtl;
1569 rtx val = 0;
1570 tree retval_rhs;
1572 /* If function wants no value, give it none. */
1573 if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE)
1575 expand_normal (retval);
1576 expand_null_return ();
1577 return;
1580 if (retval == error_mark_node)
1582 /* Treat this like a return of no value from a function that
1583 returns a value. */
1584 expand_null_return ();
1585 return;
1587 else if ((TREE_CODE (retval) == GIMPLE_MODIFY_STMT
1588 || TREE_CODE (retval) == INIT_EXPR)
1589 && TREE_CODE (GENERIC_TREE_OPERAND (retval, 0)) == RESULT_DECL)
1590 retval_rhs = GENERIC_TREE_OPERAND (retval, 1);
1591 else
1592 retval_rhs = retval;
1594 result_rtl = DECL_RTL (DECL_RESULT (current_function_decl));
1596 /* If we are returning the RESULT_DECL, then the value has already
1597 been stored into it, so we don't have to do anything special. */
1598 if (TREE_CODE (retval_rhs) == RESULT_DECL)
1599 expand_value_return (result_rtl);
1601 /* If the result is an aggregate that is being returned in one (or more)
1602 registers, load the registers here. The compiler currently can't handle
1603 copying a BLKmode value into registers. We could put this code in a
1604 more general area (for use by everyone instead of just function
1605 call/return), but until this feature is generally usable it is kept here
1606 (and in expand_call). */
1608 else if (retval_rhs != 0
1609 && TYPE_MODE (GENERIC_TREE_TYPE (retval_rhs)) == BLKmode
1610 && REG_P (result_rtl))
1612 int i;
1613 unsigned HOST_WIDE_INT bitpos, xbitpos;
1614 unsigned HOST_WIDE_INT padding_correction = 0;
1615 unsigned HOST_WIDE_INT bytes
1616 = int_size_in_bytes (TREE_TYPE (retval_rhs));
1617 int n_regs = (bytes + UNITS_PER_WORD - 1) / UNITS_PER_WORD;
1618 unsigned int bitsize
1619 = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)), BITS_PER_WORD);
1620 rtx *result_pseudos = alloca (sizeof (rtx) * n_regs);
1621 rtx result_reg, src = NULL_RTX, dst = NULL_RTX;
1622 rtx result_val = expand_normal (retval_rhs);
1623 enum machine_mode tmpmode, result_reg_mode;
1625 if (bytes == 0)
1627 expand_null_return ();
1628 return;
1631 /* If the structure doesn't take up a whole number of words, see
1632 whether the register value should be padded on the left or on
1633 the right. Set PADDING_CORRECTION to the number of padding
1634 bits needed on the left side.
1636 In most ABIs, the structure will be returned at the least end of
1637 the register, which translates to right padding on little-endian
1638 targets and left padding on big-endian targets. The opposite
1639 holds if the structure is returned at the most significant
1640 end of the register. */
1641 if (bytes % UNITS_PER_WORD != 0
1642 && (targetm.calls.return_in_msb (TREE_TYPE (retval_rhs))
1643 ? !BYTES_BIG_ENDIAN
1644 : BYTES_BIG_ENDIAN))
1645 padding_correction = (BITS_PER_WORD - ((bytes % UNITS_PER_WORD)
1646 * BITS_PER_UNIT));
1648 /* Copy the structure BITSIZE bits at a time. */
1649 for (bitpos = 0, xbitpos = padding_correction;
1650 bitpos < bytes * BITS_PER_UNIT;
1651 bitpos += bitsize, xbitpos += bitsize)
1653 /* We need a new destination pseudo each time xbitpos is
1654 on a word boundary and when xbitpos == padding_correction
1655 (the first time through). */
1656 if (xbitpos % BITS_PER_WORD == 0
1657 || xbitpos == padding_correction)
1659 /* Generate an appropriate register. */
1660 dst = gen_reg_rtx (word_mode);
1661 result_pseudos[xbitpos / BITS_PER_WORD] = dst;
1663 /* Clear the destination before we move anything into it. */
1664 emit_move_insn (dst, CONST0_RTX (GET_MODE (dst)));
1667 /* We need a new source operand each time bitpos is on a word
1668 boundary. */
1669 if (bitpos % BITS_PER_WORD == 0)
1670 src = operand_subword_force (result_val,
1671 bitpos / BITS_PER_WORD,
1672 BLKmode);
1674 /* Use bitpos for the source extraction (left justified) and
1675 xbitpos for the destination store (right justified). */
1676 store_bit_field (dst, bitsize, xbitpos % BITS_PER_WORD, word_mode,
1677 extract_bit_field (src, bitsize,
1678 bitpos % BITS_PER_WORD, 1,
1679 NULL_RTX, word_mode, word_mode));
1682 tmpmode = GET_MODE (result_rtl);
1683 if (tmpmode == BLKmode)
1685 /* Find the smallest integer mode large enough to hold the
1686 entire structure and use that mode instead of BLKmode
1687 on the USE insn for the return register. */
1688 for (tmpmode = GET_CLASS_NARROWEST_MODE (MODE_INT);
1689 tmpmode != VOIDmode;
1690 tmpmode = GET_MODE_WIDER_MODE (tmpmode))
1691 /* Have we found a large enough mode? */
1692 if (GET_MODE_SIZE (tmpmode) >= bytes)
1693 break;
1695 /* A suitable mode should have been found. */
1696 gcc_assert (tmpmode != VOIDmode);
1698 PUT_MODE (result_rtl, tmpmode);
1701 if (GET_MODE_SIZE (tmpmode) < GET_MODE_SIZE (word_mode))
1702 result_reg_mode = word_mode;
1703 else
1704 result_reg_mode = tmpmode;
1705 result_reg = gen_reg_rtx (result_reg_mode);
1707 for (i = 0; i < n_regs; i++)
1708 emit_move_insn (operand_subword (result_reg, i, 0, result_reg_mode),
1709 result_pseudos[i]);
1711 if (tmpmode != result_reg_mode)
1712 result_reg = gen_lowpart (tmpmode, result_reg);
1714 expand_value_return (result_reg);
1716 else if (retval_rhs != 0
1717 && !VOID_TYPE_P (TREE_TYPE (retval_rhs))
1718 && (REG_P (result_rtl)
1719 || (GET_CODE (result_rtl) == PARALLEL)))
1721 /* Calculate the return value into a temporary (usually a pseudo
1722 reg). */
1723 tree ot = TREE_TYPE (DECL_RESULT (current_function_decl));
1724 tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST);
1726 val = assign_temp (nt, 0, 0, 1);
1727 val = expand_expr (retval_rhs, val, GET_MODE (val), EXPAND_NORMAL);
1728 val = force_not_mem (val);
1729 /* Return the calculated value. */
1730 expand_value_return (val);
1732 else
1734 /* No hard reg used; calculate value into hard return reg. */
1735 expand_expr (retval, const0_rtx, VOIDmode, EXPAND_NORMAL);
1736 expand_value_return (result_rtl);
1740 /* Given a pointer to a BLOCK node return nonzero if (and only if) the node
1741 in question represents the outermost pair of curly braces (i.e. the "body
1742 block") of a function or method.
1744 For any BLOCK node representing a "body block" of a function or method, the
1745 BLOCK_SUPERCONTEXT of the node will point to another BLOCK node which
1746 represents the outermost (function) scope for the function or method (i.e.
1747 the one which includes the formal parameters). The BLOCK_SUPERCONTEXT of
1748 *that* node in turn will point to the relevant FUNCTION_DECL node. */
1751 is_body_block (const_tree stmt)
1753 if (lang_hooks.no_body_blocks)
1754 return 0;
1756 if (TREE_CODE (stmt) == BLOCK)
1758 tree parent = BLOCK_SUPERCONTEXT (stmt);
1760 if (parent && TREE_CODE (parent) == BLOCK)
1762 tree grandparent = BLOCK_SUPERCONTEXT (parent);
1764 if (grandparent && TREE_CODE (grandparent) == FUNCTION_DECL)
1765 return 1;
1769 return 0;
1772 /* Emit code to restore vital registers at the beginning of a nonlocal goto
1773 handler. */
1774 static void
1775 expand_nl_goto_receiver (void)
1777 /* Clobber the FP when we get here, so we have to make sure it's
1778 marked as used by this function. */
1779 emit_insn (gen_rtx_USE (VOIDmode, hard_frame_pointer_rtx));
1781 /* Mark the static chain as clobbered here so life information
1782 doesn't get messed up for it. */
1783 emit_insn (gen_rtx_CLOBBER (VOIDmode, static_chain_rtx));
1785 #ifdef HAVE_nonlocal_goto
1786 if (! HAVE_nonlocal_goto)
1787 #endif
1788 /* First adjust our frame pointer to its actual value. It was
1789 previously set to the start of the virtual area corresponding to
1790 the stacked variables when we branched here and now needs to be
1791 adjusted to the actual hardware fp value.
1793 Assignments are to virtual registers are converted by
1794 instantiate_virtual_regs into the corresponding assignment
1795 to the underlying register (fp in this case) that makes
1796 the original assignment true.
1797 So the following insn will actually be
1798 decrementing fp by STARTING_FRAME_OFFSET. */
1799 emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx);
1801 #if ARG_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
1802 if (fixed_regs[ARG_POINTER_REGNUM])
1804 #ifdef ELIMINABLE_REGS
1805 /* If the argument pointer can be eliminated in favor of the
1806 frame pointer, we don't need to restore it. We assume here
1807 that if such an elimination is present, it can always be used.
1808 This is the case on all known machines; if we don't make this
1809 assumption, we do unnecessary saving on many machines. */
1810 static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS;
1811 size_t i;
1813 for (i = 0; i < ARRAY_SIZE (elim_regs); i++)
1814 if (elim_regs[i].from == ARG_POINTER_REGNUM
1815 && elim_regs[i].to == HARD_FRAME_POINTER_REGNUM)
1816 break;
1818 if (i == ARRAY_SIZE (elim_regs))
1819 #endif
1821 /* Now restore our arg pointer from the address at which it
1822 was saved in our stack frame. */
1823 emit_move_insn (virtual_incoming_args_rtx,
1824 copy_to_reg (get_arg_pointer_save_area (cfun)));
1827 #endif
1829 #ifdef HAVE_nonlocal_goto_receiver
1830 if (HAVE_nonlocal_goto_receiver)
1831 emit_insn (gen_nonlocal_goto_receiver ());
1832 #endif
1834 /* We must not allow the code we just generated to be reordered by
1835 scheduling. Specifically, the update of the frame pointer must
1836 happen immediately, not later. */
1837 emit_insn (gen_blockage ());
1840 /* Generate RTL for the automatic variable declaration DECL.
1841 (Other kinds of declarations are simply ignored if seen here.) */
1843 void
1844 expand_decl (tree decl)
1846 tree type;
1848 type = TREE_TYPE (decl);
1850 /* For a CONST_DECL, set mode, alignment, and sizes from those of the
1851 type in case this node is used in a reference. */
1852 if (TREE_CODE (decl) == CONST_DECL)
1854 DECL_MODE (decl) = TYPE_MODE (type);
1855 DECL_ALIGN (decl) = TYPE_ALIGN (type);
1856 DECL_SIZE (decl) = TYPE_SIZE (type);
1857 DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type);
1858 return;
1861 /* Otherwise, only automatic variables need any expansion done. Static and
1862 external variables, and external functions, will be handled by
1863 `assemble_variable' (called from finish_decl). TYPE_DECL requires
1864 nothing. PARM_DECLs are handled in `assign_parms'. */
1865 if (TREE_CODE (decl) != VAR_DECL)
1866 return;
1868 if (TREE_STATIC (decl) || DECL_EXTERNAL (decl))
1869 return;
1871 /* Create the RTL representation for the variable. */
1873 if (type == error_mark_node)
1874 SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx));
1876 else if (DECL_SIZE (decl) == 0)
1877 /* Variable with incomplete type. */
1879 rtx x;
1880 if (DECL_INITIAL (decl) == 0)
1881 /* Error message was already done; now avoid a crash. */
1882 x = gen_rtx_MEM (BLKmode, const0_rtx);
1883 else
1884 /* An initializer is going to decide the size of this array.
1885 Until we know the size, represent its address with a reg. */
1886 x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode));
1888 set_mem_attributes (x, decl, 1);
1889 SET_DECL_RTL (decl, x);
1891 else if (use_register_for_decl (decl))
1893 /* Automatic variable that can go in a register. */
1894 int unsignedp = TYPE_UNSIGNED (type);
1895 enum machine_mode reg_mode
1896 = promote_mode (type, DECL_MODE (decl), &unsignedp, 0);
1898 SET_DECL_RTL (decl, gen_reg_rtx (reg_mode));
1900 /* Note if the object is a user variable. */
1901 if (!DECL_ARTIFICIAL (decl))
1902 mark_user_reg (DECL_RTL (decl));
1904 if (POINTER_TYPE_P (type))
1905 mark_reg_pointer (DECL_RTL (decl),
1906 TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl))));
1909 else if (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST
1910 && ! (flag_stack_check && ! STACK_CHECK_BUILTIN
1911 && 0 < compare_tree_int (DECL_SIZE_UNIT (decl),
1912 STACK_CHECK_MAX_VAR_SIZE)))
1914 /* Variable of fixed size that goes on the stack. */
1915 rtx oldaddr = 0;
1916 rtx addr;
1917 rtx x;
1919 /* If we previously made RTL for this decl, it must be an array
1920 whose size was determined by the initializer.
1921 The old address was a register; set that register now
1922 to the proper address. */
1923 if (DECL_RTL_SET_P (decl))
1925 gcc_assert (MEM_P (DECL_RTL (decl)));
1926 gcc_assert (REG_P (XEXP (DECL_RTL (decl), 0)));
1927 oldaddr = XEXP (DECL_RTL (decl), 0);
1930 /* Set alignment we actually gave this decl. */
1931 DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT
1932 : GET_MODE_BITSIZE (DECL_MODE (decl)));
1933 DECL_USER_ALIGN (decl) = 0;
1935 x = assign_temp (decl, 1, 1, 1);
1936 set_mem_attributes (x, decl, 1);
1937 SET_DECL_RTL (decl, x);
1939 if (oldaddr)
1941 addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr);
1942 if (addr != oldaddr)
1943 emit_move_insn (oldaddr, addr);
1946 else
1947 /* Dynamic-size object: must push space on the stack. */
1949 rtx address, size, x;
1951 /* Record the stack pointer on entry to block, if have
1952 not already done so. */
1953 do_pending_stack_adjust ();
1955 /* Compute the variable's size, in bytes. This will expand any
1956 needed SAVE_EXPRs for the first time. */
1957 size = expand_normal (DECL_SIZE_UNIT (decl));
1958 free_temp_slots ();
1960 /* Allocate space on the stack for the variable. Note that
1961 DECL_ALIGN says how the variable is to be aligned and we
1962 cannot use it to conclude anything about the alignment of
1963 the size. */
1964 address = allocate_dynamic_stack_space (size, NULL_RTX,
1965 TYPE_ALIGN (TREE_TYPE (decl)));
1967 /* Reference the variable indirect through that rtx. */
1968 x = gen_rtx_MEM (DECL_MODE (decl), address);
1969 set_mem_attributes (x, decl, 1);
1970 SET_DECL_RTL (decl, x);
1973 /* Indicate the alignment we actually gave this variable. */
1974 #ifdef STACK_BOUNDARY
1975 DECL_ALIGN (decl) = STACK_BOUNDARY;
1976 #else
1977 DECL_ALIGN (decl) = BIGGEST_ALIGNMENT;
1978 #endif
1979 DECL_USER_ALIGN (decl) = 0;
1983 /* Emit code to save the current value of stack. */
1985 expand_stack_save (void)
1987 rtx ret = NULL_RTX;
1989 do_pending_stack_adjust ();
1990 emit_stack_save (SAVE_BLOCK, &ret, NULL_RTX);
1991 return ret;
1994 /* Emit code to restore the current value of stack. */
1995 void
1996 expand_stack_restore (tree var)
1998 rtx sa = expand_normal (var);
2000 emit_stack_restore (SAVE_BLOCK, sa, NULL_RTX);
2003 /* DECL is an anonymous union. CLEANUP is a cleanup for DECL.
2004 DECL_ELTS is the list of elements that belong to DECL's type.
2005 In each, the TREE_VALUE is a VAR_DECL, and the TREE_PURPOSE a cleanup. */
2007 void
2008 expand_anon_union_decl (tree decl, tree cleanup ATTRIBUTE_UNUSED,
2009 tree decl_elts)
2011 rtx x;
2012 tree t;
2014 /* If any of the elements are addressable, so is the entire union. */
2015 for (t = decl_elts; t; t = TREE_CHAIN (t))
2016 if (TREE_ADDRESSABLE (TREE_VALUE (t)))
2018 TREE_ADDRESSABLE (decl) = 1;
2019 break;
2022 expand_decl (decl);
2023 x = DECL_RTL (decl);
2025 /* Go through the elements, assigning RTL to each. */
2026 for (t = decl_elts; t; t = TREE_CHAIN (t))
2028 tree decl_elt = TREE_VALUE (t);
2029 enum machine_mode mode = TYPE_MODE (TREE_TYPE (decl_elt));
2030 rtx decl_rtl;
2032 /* If any of the elements are addressable, so is the entire
2033 union. */
2034 if (TREE_USED (decl_elt))
2035 TREE_USED (decl) = 1;
2037 /* Propagate the union's alignment to the elements. */
2038 DECL_ALIGN (decl_elt) = DECL_ALIGN (decl);
2039 DECL_USER_ALIGN (decl_elt) = DECL_USER_ALIGN (decl);
2041 /* If the element has BLKmode and the union doesn't, the union is
2042 aligned such that the element doesn't need to have BLKmode, so
2043 change the element's mode to the appropriate one for its size. */
2044 if (mode == BLKmode && DECL_MODE (decl) != BLKmode)
2045 DECL_MODE (decl_elt) = mode
2046 = mode_for_size_tree (DECL_SIZE (decl_elt), MODE_INT, 1);
2048 if (mode == GET_MODE (x))
2049 decl_rtl = x;
2050 else if (MEM_P (x))
2051 /* (SUBREG (MEM ...)) at RTL generation time is invalid, so we
2052 instead create a new MEM rtx with the proper mode. */
2053 decl_rtl = adjust_address_nv (x, mode, 0);
2054 else
2056 gcc_assert (REG_P (x));
2057 decl_rtl = gen_lowpart_SUBREG (mode, x);
2059 SET_DECL_RTL (decl_elt, decl_rtl);
2063 /* Do the insertion of a case label into case_list. The labels are
2064 fed to us in descending order from the sorted vector of case labels used
2065 in the tree part of the middle end. So the list we construct is
2066 sorted in ascending order. The bounds on the case range, LOW and HIGH,
2067 are converted to case's index type TYPE. */
2069 static struct case_node *
2070 add_case_node (struct case_node *head, tree type, tree low, tree high,
2071 tree label, alloc_pool case_node_pool)
2073 tree min_value, max_value;
2074 struct case_node *r;
2076 gcc_assert (TREE_CODE (low) == INTEGER_CST);
2077 gcc_assert (!high || TREE_CODE (high) == INTEGER_CST);
2079 min_value = TYPE_MIN_VALUE (type);
2080 max_value = TYPE_MAX_VALUE (type);
2082 /* If there's no HIGH value, then this is not a case range; it's
2083 just a simple case label. But that's just a degenerate case
2084 range.
2085 If the bounds are equal, turn this into the one-value case. */
2086 if (!high || tree_int_cst_equal (low, high))
2088 /* If the simple case value is unreachable, ignore it. */
2089 if ((TREE_CODE (min_value) == INTEGER_CST
2090 && tree_int_cst_compare (low, min_value) < 0)
2091 || (TREE_CODE (max_value) == INTEGER_CST
2092 && tree_int_cst_compare (low, max_value) > 0))
2093 return head;
2094 low = fold_convert (type, low);
2095 high = low;
2097 else
2099 /* If the entire case range is unreachable, ignore it. */
2100 if ((TREE_CODE (min_value) == INTEGER_CST
2101 && tree_int_cst_compare (high, min_value) < 0)
2102 || (TREE_CODE (max_value) == INTEGER_CST
2103 && tree_int_cst_compare (low, max_value) > 0))
2104 return head;
2106 /* If the lower bound is less than the index type's minimum
2107 value, truncate the range bounds. */
2108 if (TREE_CODE (min_value) == INTEGER_CST
2109 && tree_int_cst_compare (low, min_value) < 0)
2110 low = min_value;
2111 low = fold_convert (type, low);
2113 /* If the upper bound is greater than the index type's maximum
2114 value, truncate the range bounds. */
2115 if (TREE_CODE (max_value) == INTEGER_CST
2116 && tree_int_cst_compare (high, max_value) > 0)
2117 high = max_value;
2118 high = fold_convert (type, high);
2122 /* Add this label to the chain. Make sure to drop overflow flags. */
2123 r = (struct case_node *) pool_alloc (case_node_pool);
2124 r->low = build_int_cst_wide (TREE_TYPE (low), TREE_INT_CST_LOW (low),
2125 TREE_INT_CST_HIGH (low));
2126 r->high = build_int_cst_wide (TREE_TYPE (high), TREE_INT_CST_LOW (high),
2127 TREE_INT_CST_HIGH (high));
2128 r->code_label = label;
2129 r->parent = r->left = NULL;
2130 r->right = head;
2131 return r;
2134 /* Maximum number of case bit tests. */
2135 #define MAX_CASE_BIT_TESTS 3
2137 /* By default, enable case bit tests on targets with ashlsi3. */
2138 #ifndef CASE_USE_BIT_TESTS
2139 #define CASE_USE_BIT_TESTS (optab_handler (ashl_optab, word_mode)->insn_code \
2140 != CODE_FOR_nothing)
2141 #endif
2144 /* A case_bit_test represents a set of case nodes that may be
2145 selected from using a bit-wise comparison. HI and LO hold
2146 the integer to be tested against, LABEL contains the label
2147 to jump to upon success and BITS counts the number of case
2148 nodes handled by this test, typically the number of bits
2149 set in HI:LO. */
2151 struct case_bit_test
2153 HOST_WIDE_INT hi;
2154 HOST_WIDE_INT lo;
2155 rtx label;
2156 int bits;
2159 /* Determine whether "1 << x" is relatively cheap in word_mode. */
2161 static
2162 bool lshift_cheap_p (void)
2164 static bool init = false;
2165 static bool cheap = true;
2167 if (!init)
2169 rtx reg = gen_rtx_REG (word_mode, 10000);
2170 int cost = rtx_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg), SET);
2171 cheap = cost < COSTS_N_INSNS (3);
2172 init = true;
2175 return cheap;
2178 /* Comparison function for qsort to order bit tests by decreasing
2179 number of case nodes, i.e. the node with the most cases gets
2180 tested first. */
2182 static int
2183 case_bit_test_cmp (const void *p1, const void *p2)
2185 const struct case_bit_test *d1 = p1;
2186 const struct case_bit_test *d2 = p2;
2188 if (d2->bits != d1->bits)
2189 return d2->bits - d1->bits;
2191 /* Stabilize the sort. */
2192 return CODE_LABEL_NUMBER (d2->label) - CODE_LABEL_NUMBER (d1->label);
2195 /* Expand a switch statement by a short sequence of bit-wise
2196 comparisons. "switch(x)" is effectively converted into
2197 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
2198 integer constants.
2200 INDEX_EXPR is the value being switched on, which is of
2201 type INDEX_TYPE. MINVAL is the lowest case value of in
2202 the case nodes, of INDEX_TYPE type, and RANGE is highest
2203 value minus MINVAL, also of type INDEX_TYPE. NODES is
2204 the set of case nodes, and DEFAULT_LABEL is the label to
2205 branch to should none of the cases match.
2207 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
2208 node targets. */
2210 static void
2211 emit_case_bit_tests (tree index_type, tree index_expr, tree minval,
2212 tree range, case_node_ptr nodes, rtx default_label)
2214 struct case_bit_test test[MAX_CASE_BIT_TESTS];
2215 enum machine_mode mode;
2216 rtx expr, index, label;
2217 unsigned int i,j,lo,hi;
2218 struct case_node *n;
2219 unsigned int count;
2221 count = 0;
2222 for (n = nodes; n; n = n->right)
2224 label = label_rtx (n->code_label);
2225 for (i = 0; i < count; i++)
2226 if (label == test[i].label)
2227 break;
2229 if (i == count)
2231 gcc_assert (count < MAX_CASE_BIT_TESTS);
2232 test[i].hi = 0;
2233 test[i].lo = 0;
2234 test[i].label = label;
2235 test[i].bits = 1;
2236 count++;
2238 else
2239 test[i].bits++;
2241 lo = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2242 n->low, minval), 1);
2243 hi = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2244 n->high, minval), 1);
2245 for (j = lo; j <= hi; j++)
2246 if (j >= HOST_BITS_PER_WIDE_INT)
2247 test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT);
2248 else
2249 test[i].lo |= (HOST_WIDE_INT) 1 << j;
2252 qsort (test, count, sizeof(*test), case_bit_test_cmp);
2254 index_expr = fold_build2 (MINUS_EXPR, index_type,
2255 fold_convert (index_type, index_expr),
2256 fold_convert (index_type, minval));
2257 index = expand_normal (index_expr);
2258 do_pending_stack_adjust ();
2260 mode = TYPE_MODE (index_type);
2261 expr = expand_normal (range);
2262 emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
2263 default_label);
2265 index = convert_to_mode (word_mode, index, 0);
2266 index = expand_binop (word_mode, ashl_optab, const1_rtx,
2267 index, NULL_RTX, 1, OPTAB_WIDEN);
2269 for (i = 0; i < count; i++)
2271 expr = immed_double_const (test[i].lo, test[i].hi, word_mode);
2272 expr = expand_binop (word_mode, and_optab, index, expr,
2273 NULL_RTX, 1, OPTAB_WIDEN);
2274 emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX,
2275 word_mode, 1, test[i].label);
2278 emit_jump (default_label);
2281 #ifndef HAVE_casesi
2282 #define HAVE_casesi 0
2283 #endif
2285 #ifndef HAVE_tablejump
2286 #define HAVE_tablejump 0
2287 #endif
2289 /* Terminate a case (Pascal/Ada) or switch (C) statement
2290 in which ORIG_INDEX is the expression to be tested.
2291 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
2292 type as given in the source before any compiler conversions.
2293 Generate the code to test it and jump to the right place. */
2295 void
2296 expand_case (tree exp)
2298 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
2299 rtx default_label = 0;
2300 struct case_node *n;
2301 unsigned int count, uniq;
2302 rtx index;
2303 rtx table_label;
2304 int ncases;
2305 rtx *labelvec;
2306 int i;
2307 rtx before_case, end, lab;
2309 tree vec = SWITCH_LABELS (exp);
2310 tree orig_type = TREE_TYPE (exp);
2311 tree index_expr = SWITCH_COND (exp);
2312 tree index_type = TREE_TYPE (index_expr);
2313 int unsignedp = TYPE_UNSIGNED (index_type);
2315 /* The insn after which the case dispatch should finally
2316 be emitted. Zero for a dummy. */
2317 rtx start;
2319 /* A list of case labels; it is first built as a list and it may then
2320 be rearranged into a nearly balanced binary tree. */
2321 struct case_node *case_list = 0;
2323 /* Label to jump to if no case matches. */
2324 tree default_label_decl;
2326 alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
2327 sizeof (struct case_node),
2328 100);
2330 /* The switch body is lowered in gimplify.c, we should never have
2331 switches with a non-NULL SWITCH_BODY here. */
2332 gcc_assert (!SWITCH_BODY (exp));
2333 gcc_assert (SWITCH_LABELS (exp));
2335 do_pending_stack_adjust ();
2337 /* An ERROR_MARK occurs for various reasons including invalid data type. */
2338 if (index_type != error_mark_node)
2340 tree elt;
2341 bitmap label_bitmap;
2343 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
2344 expressions being INTEGER_CST. */
2345 gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
2347 /* The default case is at the end of TREE_VEC. */
2348 elt = TREE_VEC_ELT (vec, TREE_VEC_LENGTH (vec) - 1);
2349 gcc_assert (!CASE_HIGH (elt));
2350 gcc_assert (!CASE_LOW (elt));
2351 default_label_decl = CASE_LABEL (elt);
2353 for (i = TREE_VEC_LENGTH (vec) - 1; --i >= 0; )
2355 tree low, high;
2356 elt = TREE_VEC_ELT (vec, i);
2358 low = CASE_LOW (elt);
2359 gcc_assert (low);
2360 high = CASE_HIGH (elt);
2362 /* Discard empty ranges. */
2363 if (high && tree_int_cst_lt (high, low))
2364 continue;
2366 case_list = add_case_node (case_list, index_type, low, high,
2367 CASE_LABEL (elt), case_node_pool);
2371 before_case = start = get_last_insn ();
2372 default_label = label_rtx (default_label_decl);
2374 /* Get upper and lower bounds of case values. */
2376 uniq = 0;
2377 count = 0;
2378 label_bitmap = BITMAP_ALLOC (NULL);
2379 for (n = case_list; n; n = n->right)
2381 /* Count the elements and track the largest and smallest
2382 of them (treating them as signed even if they are not). */
2383 if (count++ == 0)
2385 minval = n->low;
2386 maxval = n->high;
2388 else
2390 if (tree_int_cst_lt (n->low, minval))
2391 minval = n->low;
2392 if (tree_int_cst_lt (maxval, n->high))
2393 maxval = n->high;
2395 /* A range counts double, since it requires two compares. */
2396 if (! tree_int_cst_equal (n->low, n->high))
2397 count++;
2399 /* If we have not seen this label yet, then increase the
2400 number of unique case node targets seen. */
2401 lab = label_rtx (n->code_label);
2402 if (!bitmap_bit_p (label_bitmap, CODE_LABEL_NUMBER (lab)))
2404 bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab));
2405 uniq++;
2409 BITMAP_FREE (label_bitmap);
2411 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
2412 destination, such as one with a default case only. However,
2413 it doesn't remove cases that are out of range for the switch
2414 type, so we may still get a zero here. */
2415 if (count == 0)
2417 emit_jump (default_label);
2418 free_alloc_pool (case_node_pool);
2419 return;
2422 /* Compute span of values. */
2423 range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
2425 /* Try implementing this switch statement by a short sequence of
2426 bit-wise comparisons. However, we let the binary-tree case
2427 below handle constant index expressions. */
2428 if (CASE_USE_BIT_TESTS
2429 && ! TREE_CONSTANT (index_expr)
2430 && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
2431 && compare_tree_int (range, 0) > 0
2432 && lshift_cheap_p ()
2433 && ((uniq == 1 && count >= 3)
2434 || (uniq == 2 && count >= 5)
2435 || (uniq == 3 && count >= 6)))
2437 /* Optimize the case where all the case values fit in a
2438 word without having to subtract MINVAL. In this case,
2439 we can optimize away the subtraction. */
2440 if (compare_tree_int (minval, 0) > 0
2441 && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
2443 minval = build_int_cst (index_type, 0);
2444 range = maxval;
2446 emit_case_bit_tests (index_type, index_expr, minval, range,
2447 case_list, default_label);
2450 /* If range of values is much bigger than number of values,
2451 make a sequence of conditional branches instead of a dispatch.
2452 If the switch-index is a constant, do it this way
2453 because we can optimize it. */
2455 else if (count < case_values_threshold ()
2456 || compare_tree_int (range,
2457 (optimize_size ? 3 : 10) * count) > 0
2458 /* RANGE may be signed, and really large ranges will show up
2459 as negative numbers. */
2460 || compare_tree_int (range, 0) < 0
2461 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
2462 || flag_pic
2463 #endif
2464 || !flag_jump_tables
2465 || TREE_CONSTANT (index_expr)
2466 /* If neither casesi or tablejump is available, we can
2467 only go this way. */
2468 || (!HAVE_casesi && !HAVE_tablejump))
2470 index = expand_normal (index_expr);
2472 /* If the index is a short or char that we do not have
2473 an insn to handle comparisons directly, convert it to
2474 a full integer now, rather than letting each comparison
2475 generate the conversion. */
2477 if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
2478 && ! have_insn_for (COMPARE, GET_MODE (index)))
2480 enum machine_mode wider_mode;
2481 for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
2482 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2483 if (have_insn_for (COMPARE, wider_mode))
2485 index = convert_to_mode (wider_mode, index, unsignedp);
2486 break;
2490 do_pending_stack_adjust ();
2492 if (MEM_P (index))
2493 index = copy_to_reg (index);
2495 /* We generate a binary decision tree to select the
2496 appropriate target code. This is done as follows:
2498 The list of cases is rearranged into a binary tree,
2499 nearly optimal assuming equal probability for each case.
2501 The tree is transformed into RTL, eliminating
2502 redundant test conditions at the same time.
2504 If program flow could reach the end of the
2505 decision tree an unconditional jump to the
2506 default code is emitted. */
2508 use_cost_table
2509 = (TREE_CODE (orig_type) != ENUMERAL_TYPE
2510 && estimate_case_costs (case_list));
2511 balance_case_nodes (&case_list, NULL);
2512 emit_case_nodes (index, case_list, default_label, index_type);
2513 emit_jump (default_label);
2515 else
2517 table_label = gen_label_rtx ();
2518 if (! try_casesi (index_type, index_expr, minval, range,
2519 table_label, default_label))
2521 bool ok;
2523 /* Index jumptables from zero for suitable values of
2524 minval to avoid a subtraction. */
2525 if (! optimize_size
2526 && compare_tree_int (minval, 0) > 0
2527 && compare_tree_int (minval, 3) < 0)
2529 minval = build_int_cst (index_type, 0);
2530 range = maxval;
2533 ok = try_tablejump (index_type, index_expr, minval, range,
2534 table_label, default_label);
2535 gcc_assert (ok);
2538 /* Get table of labels to jump to, in order of case index. */
2540 ncases = tree_low_cst (range, 0) + 1;
2541 labelvec = alloca (ncases * sizeof (rtx));
2542 memset (labelvec, 0, ncases * sizeof (rtx));
2544 for (n = case_list; n; n = n->right)
2546 /* Compute the low and high bounds relative to the minimum
2547 value since that should fit in a HOST_WIDE_INT while the
2548 actual values may not. */
2549 HOST_WIDE_INT i_low
2550 = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2551 n->low, minval), 1);
2552 HOST_WIDE_INT i_high
2553 = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2554 n->high, minval), 1);
2555 HOST_WIDE_INT i;
2557 for (i = i_low; i <= i_high; i ++)
2558 labelvec[i]
2559 = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
2562 /* Fill in the gaps with the default. */
2563 for (i = 0; i < ncases; i++)
2564 if (labelvec[i] == 0)
2565 labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
2567 /* Output the table. */
2568 emit_label (table_label);
2570 if (CASE_VECTOR_PC_RELATIVE || flag_pic)
2571 emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
2572 gen_rtx_LABEL_REF (Pmode, table_label),
2573 gen_rtvec_v (ncases, labelvec),
2574 const0_rtx, const0_rtx));
2575 else
2576 emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
2577 gen_rtvec_v (ncases, labelvec)));
2579 /* Record no drop-through after the table. */
2580 emit_barrier ();
2583 before_case = NEXT_INSN (before_case);
2584 end = get_last_insn ();
2585 reorder_insns (before_case, end, start);
2588 free_temp_slots ();
2589 free_alloc_pool (case_node_pool);
2592 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */
2594 static void
2595 do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label,
2596 int unsignedp)
2598 do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
2599 NULL_RTX, NULL_RTX, label);
2602 /* Not all case values are encountered equally. This function
2603 uses a heuristic to weight case labels, in cases where that
2604 looks like a reasonable thing to do.
2606 Right now, all we try to guess is text, and we establish the
2607 following weights:
2609 chars above space: 16
2610 digits: 16
2611 default: 12
2612 space, punct: 8
2613 tab: 4
2614 newline: 2
2615 other "\" chars: 1
2616 remaining chars: 0
2618 If we find any cases in the switch that are not either -1 or in the range
2619 of valid ASCII characters, or are control characters other than those
2620 commonly used with "\", don't treat this switch scanning text.
2622 Return 1 if these nodes are suitable for cost estimation, otherwise
2623 return 0. */
2625 static int
2626 estimate_case_costs (case_node_ptr node)
2628 tree min_ascii = integer_minus_one_node;
2629 tree max_ascii = build_int_cst (TREE_TYPE (node->high), 127);
2630 case_node_ptr n;
2631 int i;
2633 /* If we haven't already made the cost table, make it now. Note that the
2634 lower bound of the table is -1, not zero. */
2636 if (! cost_table_initialized)
2638 cost_table_initialized = 1;
2640 for (i = 0; i < 128; i++)
2642 if (ISALNUM (i))
2643 COST_TABLE (i) = 16;
2644 else if (ISPUNCT (i))
2645 COST_TABLE (i) = 8;
2646 else if (ISCNTRL (i))
2647 COST_TABLE (i) = -1;
2650 COST_TABLE (' ') = 8;
2651 COST_TABLE ('\t') = 4;
2652 COST_TABLE ('\0') = 4;
2653 COST_TABLE ('\n') = 2;
2654 COST_TABLE ('\f') = 1;
2655 COST_TABLE ('\v') = 1;
2656 COST_TABLE ('\b') = 1;
2659 /* See if all the case expressions look like text. It is text if the
2660 constant is >= -1 and the highest constant is <= 127. Do all comparisons
2661 as signed arithmetic since we don't want to ever access cost_table with a
2662 value less than -1. Also check that none of the constants in a range
2663 are strange control characters. */
2665 for (n = node; n; n = n->right)
2667 if (tree_int_cst_lt (n->low, min_ascii)
2668 || tree_int_cst_lt (max_ascii, n->high))
2669 return 0;
2671 for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low);
2672 i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++)
2673 if (COST_TABLE (i) < 0)
2674 return 0;
2677 /* All interesting values are within the range of interesting
2678 ASCII characters. */
2679 return 1;
2682 /* Take an ordered list of case nodes
2683 and transform them into a near optimal binary tree,
2684 on the assumption that any target code selection value is as
2685 likely as any other.
2687 The transformation is performed by splitting the ordered
2688 list into two equal sections plus a pivot. The parts are
2689 then attached to the pivot as left and right branches. Each
2690 branch is then transformed recursively. */
2692 static void
2693 balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
2695 case_node_ptr np;
2697 np = *head;
2698 if (np)
2700 int cost = 0;
2701 int i = 0;
2702 int ranges = 0;
2703 case_node_ptr *npp;
2704 case_node_ptr left;
2706 /* Count the number of entries on branch. Also count the ranges. */
2708 while (np)
2710 if (!tree_int_cst_equal (np->low, np->high))
2712 ranges++;
2713 if (use_cost_table)
2714 cost += COST_TABLE (TREE_INT_CST_LOW (np->high));
2717 if (use_cost_table)
2718 cost += COST_TABLE (TREE_INT_CST_LOW (np->low));
2720 i++;
2721 np = np->right;
2724 if (i > 2)
2726 /* Split this list if it is long enough for that to help. */
2727 npp = head;
2728 left = *npp;
2729 if (use_cost_table)
2731 /* Find the place in the list that bisects the list's total cost,
2732 Here I gets half the total cost. */
2733 int n_moved = 0;
2734 i = (cost + 1) / 2;
2735 while (1)
2737 /* Skip nodes while their cost does not reach that amount. */
2738 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
2739 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high));
2740 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low));
2741 if (i <= 0)
2742 break;
2743 npp = &(*npp)->right;
2744 n_moved += 1;
2746 if (n_moved == 0)
2748 /* Leave this branch lopsided, but optimize left-hand
2749 side and fill in `parent' fields for right-hand side. */
2750 np = *head;
2751 np->parent = parent;
2752 balance_case_nodes (&np->left, np);
2753 for (; np->right; np = np->right)
2754 np->right->parent = np;
2755 return;
2758 /* If there are just three nodes, split at the middle one. */
2759 else if (i == 3)
2760 npp = &(*npp)->right;
2761 else
2763 /* Find the place in the list that bisects the list's total cost,
2764 where ranges count as 2.
2765 Here I gets half the total cost. */
2766 i = (i + ranges + 1) / 2;
2767 while (1)
2769 /* Skip nodes while their cost does not reach that amount. */
2770 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
2771 i--;
2772 i--;
2773 if (i <= 0)
2774 break;
2775 npp = &(*npp)->right;
2778 *head = np = *npp;
2779 *npp = 0;
2780 np->parent = parent;
2781 np->left = left;
2783 /* Optimize each of the two split parts. */
2784 balance_case_nodes (&np->left, np);
2785 balance_case_nodes (&np->right, np);
2787 else
2789 /* Else leave this branch as one level,
2790 but fill in `parent' fields. */
2791 np = *head;
2792 np->parent = parent;
2793 for (; np->right; np = np->right)
2794 np->right->parent = np;
2799 /* Search the parent sections of the case node tree
2800 to see if a test for the lower bound of NODE would be redundant.
2801 INDEX_TYPE is the type of the index expression.
2803 The instructions to generate the case decision tree are
2804 output in the same order as nodes are processed so it is
2805 known that if a parent node checks the range of the current
2806 node minus one that the current node is bounded at its lower
2807 span. Thus the test would be redundant. */
2809 static int
2810 node_has_low_bound (case_node_ptr node, tree index_type)
2812 tree low_minus_one;
2813 case_node_ptr pnode;
2815 /* If the lower bound of this node is the lowest value in the index type,
2816 we need not test it. */
2818 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
2819 return 1;
2821 /* If this node has a left branch, the value at the left must be less
2822 than that at this node, so it cannot be bounded at the bottom and
2823 we need not bother testing any further. */
2825 if (node->left)
2826 return 0;
2828 low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low),
2829 node->low,
2830 build_int_cst (TREE_TYPE (node->low), 1));
2832 /* If the subtraction above overflowed, we can't verify anything.
2833 Otherwise, look for a parent that tests our value - 1. */
2835 if (! tree_int_cst_lt (low_minus_one, node->low))
2836 return 0;
2838 for (pnode = node->parent; pnode; pnode = pnode->parent)
2839 if (tree_int_cst_equal (low_minus_one, pnode->high))
2840 return 1;
2842 return 0;
2845 /* Search the parent sections of the case node tree
2846 to see if a test for the upper bound of NODE would be redundant.
2847 INDEX_TYPE is the type of the index expression.
2849 The instructions to generate the case decision tree are
2850 output in the same order as nodes are processed so it is
2851 known that if a parent node checks the range of the current
2852 node plus one that the current node is bounded at its upper
2853 span. Thus the test would be redundant. */
2855 static int
2856 node_has_high_bound (case_node_ptr node, tree index_type)
2858 tree high_plus_one;
2859 case_node_ptr pnode;
2861 /* If there is no upper bound, obviously no test is needed. */
2863 if (TYPE_MAX_VALUE (index_type) == NULL)
2864 return 1;
2866 /* If the upper bound of this node is the highest value in the type
2867 of the index expression, we need not test against it. */
2869 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
2870 return 1;
2872 /* If this node has a right branch, the value at the right must be greater
2873 than that at this node, so it cannot be bounded at the top and
2874 we need not bother testing any further. */
2876 if (node->right)
2877 return 0;
2879 high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high),
2880 node->high,
2881 build_int_cst (TREE_TYPE (node->high), 1));
2883 /* If the addition above overflowed, we can't verify anything.
2884 Otherwise, look for a parent that tests our value + 1. */
2886 if (! tree_int_cst_lt (node->high, high_plus_one))
2887 return 0;
2889 for (pnode = node->parent; pnode; pnode = pnode->parent)
2890 if (tree_int_cst_equal (high_plus_one, pnode->low))
2891 return 1;
2893 return 0;
2896 /* Search the parent sections of the
2897 case node tree to see if both tests for the upper and lower
2898 bounds of NODE would be redundant. */
2900 static int
2901 node_is_bounded (case_node_ptr node, tree index_type)
2903 return (node_has_low_bound (node, index_type)
2904 && node_has_high_bound (node, index_type));
2907 /* Emit step-by-step code to select a case for the value of INDEX.
2908 The thus generated decision tree follows the form of the
2909 case-node binary tree NODE, whose nodes represent test conditions.
2910 INDEX_TYPE is the type of the index of the switch.
2912 Care is taken to prune redundant tests from the decision tree
2913 by detecting any boundary conditions already checked by
2914 emitted rtx. (See node_has_high_bound, node_has_low_bound
2915 and node_is_bounded, above.)
2917 Where the test conditions can be shown to be redundant we emit
2918 an unconditional jump to the target code. As a further
2919 optimization, the subordinates of a tree node are examined to
2920 check for bounded nodes. In this case conditional and/or
2921 unconditional jumps as a result of the boundary check for the
2922 current node are arranged to target the subordinates associated
2923 code for out of bound conditions on the current node.
2925 We can assume that when control reaches the code generated here,
2926 the index value has already been compared with the parents
2927 of this node, and determined to be on the same side of each parent
2928 as this node is. Thus, if this node tests for the value 51,
2929 and a parent tested for 52, we don't need to consider
2930 the possibility of a value greater than 51. If another parent
2931 tests for the value 50, then this node need not test anything. */
2933 static void
2934 emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
2935 tree index_type)
2937 /* If INDEX has an unsigned type, we must make unsigned branches. */
2938 int unsignedp = TYPE_UNSIGNED (index_type);
2939 enum machine_mode mode = GET_MODE (index);
2940 enum machine_mode imode = TYPE_MODE (index_type);
2942 /* Handle indices detected as constant during RTL expansion. */
2943 if (mode == VOIDmode)
2944 mode = imode;
2946 /* See if our parents have already tested everything for us.
2947 If they have, emit an unconditional jump for this node. */
2948 if (node_is_bounded (node, index_type))
2949 emit_jump (label_rtx (node->code_label));
2951 else if (tree_int_cst_equal (node->low, node->high))
2953 /* Node is single valued. First see if the index expression matches
2954 this node and then check our children, if any. */
2956 do_jump_if_equal (mode, index,
2957 convert_modes (mode, imode,
2958 expand_normal (node->low),
2959 unsignedp),
2960 label_rtx (node->code_label), unsignedp);
2962 if (node->right != 0 && node->left != 0)
2964 /* This node has children on both sides.
2965 Dispatch to one side or the other
2966 by comparing the index value with this node's value.
2967 If one subtree is bounded, check that one first,
2968 so we can avoid real branches in the tree. */
2970 if (node_is_bounded (node->right, index_type))
2972 emit_cmp_and_jump_insns (index,
2973 convert_modes
2974 (mode, imode,
2975 expand_normal (node->high),
2976 unsignedp),
2977 GT, NULL_RTX, mode, unsignedp,
2978 label_rtx (node->right->code_label));
2979 emit_case_nodes (index, node->left, default_label, index_type);
2982 else if (node_is_bounded (node->left, index_type))
2984 emit_cmp_and_jump_insns (index,
2985 convert_modes
2986 (mode, imode,
2987 expand_normal (node->high),
2988 unsignedp),
2989 LT, NULL_RTX, mode, unsignedp,
2990 label_rtx (node->left->code_label));
2991 emit_case_nodes (index, node->right, default_label, index_type);
2994 /* If both children are single-valued cases with no
2995 children, finish up all the work. This way, we can save
2996 one ordered comparison. */
2997 else if (tree_int_cst_equal (node->right->low, node->right->high)
2998 && node->right->left == 0
2999 && node->right->right == 0
3000 && tree_int_cst_equal (node->left->low, node->left->high)
3001 && node->left->left == 0
3002 && node->left->right == 0)
3004 /* Neither node is bounded. First distinguish the two sides;
3005 then emit the code for one side at a time. */
3007 /* See if the value matches what the right hand side
3008 wants. */
3009 do_jump_if_equal (mode, index,
3010 convert_modes (mode, imode,
3011 expand_normal (node->right->low),
3012 unsignedp),
3013 label_rtx (node->right->code_label),
3014 unsignedp);
3016 /* See if the value matches what the left hand side
3017 wants. */
3018 do_jump_if_equal (mode, index,
3019 convert_modes (mode, imode,
3020 expand_normal (node->left->low),
3021 unsignedp),
3022 label_rtx (node->left->code_label),
3023 unsignedp);
3026 else
3028 /* Neither node is bounded. First distinguish the two sides;
3029 then emit the code for one side at a time. */
3031 tree test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
3033 /* See if the value is on the right. */
3034 emit_cmp_and_jump_insns (index,
3035 convert_modes
3036 (mode, imode,
3037 expand_normal (node->high),
3038 unsignedp),
3039 GT, NULL_RTX, mode, unsignedp,
3040 label_rtx (test_label));
3042 /* Value must be on the left.
3043 Handle the left-hand subtree. */
3044 emit_case_nodes (index, node->left, default_label, index_type);
3045 /* If left-hand subtree does nothing,
3046 go to default. */
3047 emit_jump (default_label);
3049 /* Code branches here for the right-hand subtree. */
3050 expand_label (test_label);
3051 emit_case_nodes (index, node->right, default_label, index_type);
3055 else if (node->right != 0 && node->left == 0)
3057 /* Here we have a right child but no left so we issue a conditional
3058 branch to default and process the right child.
3060 Omit the conditional branch to default if the right child
3061 does not have any children and is single valued; it would
3062 cost too much space to save so little time. */
3064 if (node->right->right || node->right->left
3065 || !tree_int_cst_equal (node->right->low, node->right->high))
3067 if (!node_has_low_bound (node, index_type))
3069 emit_cmp_and_jump_insns (index,
3070 convert_modes
3071 (mode, imode,
3072 expand_normal (node->high),
3073 unsignedp),
3074 LT, NULL_RTX, mode, unsignedp,
3075 default_label);
3078 emit_case_nodes (index, node->right, default_label, index_type);
3080 else
3081 /* We cannot process node->right normally
3082 since we haven't ruled out the numbers less than
3083 this node's value. So handle node->right explicitly. */
3084 do_jump_if_equal (mode, index,
3085 convert_modes
3086 (mode, imode,
3087 expand_normal (node->right->low),
3088 unsignedp),
3089 label_rtx (node->right->code_label), unsignedp);
3092 else if (node->right == 0 && node->left != 0)
3094 /* Just one subtree, on the left. */
3095 if (node->left->left || node->left->right
3096 || !tree_int_cst_equal (node->left->low, node->left->high))
3098 if (!node_has_high_bound (node, index_type))
3100 emit_cmp_and_jump_insns (index,
3101 convert_modes
3102 (mode, imode,
3103 expand_normal (node->high),
3104 unsignedp),
3105 GT, NULL_RTX, mode, unsignedp,
3106 default_label);
3109 emit_case_nodes (index, node->left, default_label, index_type);
3111 else
3112 /* We cannot process node->left normally
3113 since we haven't ruled out the numbers less than
3114 this node's value. So handle node->left explicitly. */
3115 do_jump_if_equal (mode, index,
3116 convert_modes
3117 (mode, imode,
3118 expand_normal (node->left->low),
3119 unsignedp),
3120 label_rtx (node->left->code_label), unsignedp);
3123 else
3125 /* Node is a range. These cases are very similar to those for a single
3126 value, except that we do not start by testing whether this node
3127 is the one to branch to. */
3129 if (node->right != 0 && node->left != 0)
3131 /* Node has subtrees on both sides.
3132 If the right-hand subtree is bounded,
3133 test for it first, since we can go straight there.
3134 Otherwise, we need to make a branch in the control structure,
3135 then handle the two subtrees. */
3136 tree test_label = 0;
3138 if (node_is_bounded (node->right, index_type))
3139 /* Right hand node is fully bounded so we can eliminate any
3140 testing and branch directly to the target code. */
3141 emit_cmp_and_jump_insns (index,
3142 convert_modes
3143 (mode, imode,
3144 expand_normal (node->high),
3145 unsignedp),
3146 GT, NULL_RTX, mode, unsignedp,
3147 label_rtx (node->right->code_label));
3148 else
3150 /* Right hand node requires testing.
3151 Branch to a label where we will handle it later. */
3153 test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
3154 emit_cmp_and_jump_insns (index,
3155 convert_modes
3156 (mode, imode,
3157 expand_normal (node->high),
3158 unsignedp),
3159 GT, NULL_RTX, mode, unsignedp,
3160 label_rtx (test_label));
3163 /* Value belongs to this node or to the left-hand subtree. */
3165 emit_cmp_and_jump_insns (index,
3166 convert_modes
3167 (mode, imode,
3168 expand_normal (node->low),
3169 unsignedp),
3170 GE, NULL_RTX, mode, unsignedp,
3171 label_rtx (node->code_label));
3173 /* Handle the left-hand subtree. */
3174 emit_case_nodes (index, node->left, default_label, index_type);
3176 /* If right node had to be handled later, do that now. */
3178 if (test_label)
3180 /* If the left-hand subtree fell through,
3181 don't let it fall into the right-hand subtree. */
3182 emit_jump (default_label);
3184 expand_label (test_label);
3185 emit_case_nodes (index, node->right, default_label, index_type);
3189 else if (node->right != 0 && node->left == 0)
3191 /* Deal with values to the left of this node,
3192 if they are possible. */
3193 if (!node_has_low_bound (node, index_type))
3195 emit_cmp_and_jump_insns (index,
3196 convert_modes
3197 (mode, imode,
3198 expand_normal (node->low),
3199 unsignedp),
3200 LT, NULL_RTX, mode, unsignedp,
3201 default_label);
3204 /* Value belongs to this node or to the right-hand subtree. */
3206 emit_cmp_and_jump_insns (index,
3207 convert_modes
3208 (mode, imode,
3209 expand_normal (node->high),
3210 unsignedp),
3211 LE, NULL_RTX, mode, unsignedp,
3212 label_rtx (node->code_label));
3214 emit_case_nodes (index, node->right, default_label, index_type);
3217 else if (node->right == 0 && node->left != 0)
3219 /* Deal with values to the right of this node,
3220 if they are possible. */
3221 if (!node_has_high_bound (node, index_type))
3223 emit_cmp_and_jump_insns (index,
3224 convert_modes
3225 (mode, imode,
3226 expand_normal (node->high),
3227 unsignedp),
3228 GT, NULL_RTX, mode, unsignedp,
3229 default_label);
3232 /* Value belongs to this node or to the left-hand subtree. */
3234 emit_cmp_and_jump_insns (index,
3235 convert_modes
3236 (mode, imode,
3237 expand_normal (node->low),
3238 unsignedp),
3239 GE, NULL_RTX, mode, unsignedp,
3240 label_rtx (node->code_label));
3242 emit_case_nodes (index, node->left, default_label, index_type);
3245 else
3247 /* Node has no children so we check low and high bounds to remove
3248 redundant tests. Only one of the bounds can exist,
3249 since otherwise this node is bounded--a case tested already. */
3250 int high_bound = node_has_high_bound (node, index_type);
3251 int low_bound = node_has_low_bound (node, index_type);
3253 if (!high_bound && low_bound)
3255 emit_cmp_and_jump_insns (index,
3256 convert_modes
3257 (mode, imode,
3258 expand_normal (node->high),
3259 unsignedp),
3260 GT, NULL_RTX, mode, unsignedp,
3261 default_label);
3264 else if (!low_bound && high_bound)
3266 emit_cmp_and_jump_insns (index,
3267 convert_modes
3268 (mode, imode,
3269 expand_normal (node->low),
3270 unsignedp),
3271 LT, NULL_RTX, mode, unsignedp,
3272 default_label);
3274 else if (!low_bound && !high_bound)
3276 /* Widen LOW and HIGH to the same width as INDEX. */
3277 tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
3278 tree low = build1 (CONVERT_EXPR, type, node->low);
3279 tree high = build1 (CONVERT_EXPR, type, node->high);
3280 rtx low_rtx, new_index, new_bound;
3282 /* Instead of doing two branches, emit one unsigned branch for
3283 (index-low) > (high-low). */
3284 low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL);
3285 new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
3286 NULL_RTX, unsignedp,
3287 OPTAB_WIDEN);
3288 new_bound = expand_expr (fold_build2 (MINUS_EXPR, type,
3289 high, low),
3290 NULL_RTX, mode, EXPAND_NORMAL);
3292 emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
3293 mode, 1, default_label);
3296 emit_jump (label_rtx (node->code_label));