Daily bump.
[official-gcc.git] / gcc / stmt.c
blob7d4cbb0cb4c4fccee6b7f29cb4d5d7d0c7e9c8f7
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, 2008, 2009,
4 2010 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 "diagnostic-core.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 "gimple.h"
52 #include "regs.h"
53 #include "alloc-pool.h"
54 #include "pretty-print.h"
55 #include "bitmap.h"
58 /* Functions and data structures for expanding case statements. */
60 /* Case label structure, used to hold info on labels within case
61 statements. We handle "range" labels; for a single-value label
62 as in C, the high and low limits are the same.
64 We start with a vector of case nodes sorted in ascending order, and
65 the default label as the last element in the vector. Before expanding
66 to RTL, we transform this vector into a list linked via the RIGHT
67 fields in the case_node struct. Nodes with higher case values are
68 later in the list.
70 Switch statements can be output in three forms. A branch table is
71 used if there are more than a few labels and the labels are dense
72 within the range between the smallest and largest case value. If a
73 branch table is used, no further manipulations are done with the case
74 node chain.
76 The alternative to the use of a branch table is to generate a series
77 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
78 and PARENT fields to hold a binary tree. Initially the tree is
79 totally unbalanced, with everything on the right. We balance the tree
80 with nodes on the left having lower case values than the parent
81 and nodes on the right having higher values. We then output the tree
82 in order.
84 For very small, suitable switch statements, we can generate a series
85 of simple bit test and branches instead. */
87 struct case_node
89 struct case_node *left; /* Left son in binary tree */
90 struct case_node *right; /* Right son in binary tree; also node chain */
91 struct case_node *parent; /* Parent of node in binary tree */
92 tree low; /* Lowest index value for this label */
93 tree high; /* Highest index value for this label */
94 tree code_label; /* Label to jump to when node matches */
97 typedef struct case_node case_node;
98 typedef struct case_node *case_node_ptr;
100 /* These are used by estimate_case_costs and balance_case_nodes. */
102 /* This must be a signed type, and non-ANSI compilers lack signed char. */
103 static short cost_table_[129];
104 static int use_cost_table;
105 static int cost_table_initialized;
107 /* Special care is needed because we allow -1, but TREE_INT_CST_LOW
108 is unsigned. */
109 #define COST_TABLE(I) cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)]
111 static int n_occurrences (int, const char *);
112 static bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *);
113 static void expand_nl_goto_receiver (void);
114 static bool check_operand_nalternatives (tree, tree);
115 static bool check_unique_operand_names (tree, tree, tree);
116 static char *resolve_operand_name_1 (char *, tree, tree, tree);
117 static void expand_null_return_1 (void);
118 static void expand_value_return (rtx);
119 static int estimate_case_costs (case_node_ptr);
120 static bool lshift_cheap_p (void);
121 static int case_bit_test_cmp (const void *, const void *);
122 static void emit_case_bit_tests (tree, tree, tree, tree, case_node_ptr, rtx);
123 static void balance_case_nodes (case_node_ptr *, case_node_ptr);
124 static int node_has_low_bound (case_node_ptr, tree);
125 static int node_has_high_bound (case_node_ptr, tree);
126 static int node_is_bounded (case_node_ptr, tree);
127 static void emit_case_nodes (rtx, case_node_ptr, rtx, tree);
128 static struct case_node *add_case_node (struct case_node *, tree,
129 tree, tree, tree, alloc_pool);
132 /* Return the rtx-label that corresponds to a LABEL_DECL,
133 creating it if necessary. */
136 label_rtx (tree label)
138 gcc_assert (TREE_CODE (label) == LABEL_DECL);
140 if (!DECL_RTL_SET_P (label))
142 rtx r = gen_label_rtx ();
143 SET_DECL_RTL (label, r);
144 if (FORCED_LABEL (label) || DECL_NONLOCAL (label))
145 LABEL_PRESERVE_P (r) = 1;
148 return DECL_RTL (label);
151 /* As above, but also put it on the forced-reference list of the
152 function that contains it. */
154 force_label_rtx (tree label)
156 rtx ref = label_rtx (label);
157 tree function = decl_function_context (label);
159 gcc_assert (function);
161 forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref, forced_labels);
162 return ref;
165 /* Add an unconditional jump to LABEL as the next sequential instruction. */
167 void
168 emit_jump (rtx label)
170 do_pending_stack_adjust ();
171 emit_jump_insn (gen_jump (label));
172 emit_barrier ();
175 /* Emit code to jump to the address
176 specified by the pointer expression EXP. */
178 void
179 expand_computed_goto (tree exp)
181 rtx x = expand_normal (exp);
183 x = convert_memory_address (Pmode, x);
185 do_pending_stack_adjust ();
186 emit_indirect_jump (x);
189 /* Handle goto statements and the labels that they can go to. */
191 /* Specify the location in the RTL code of a label LABEL,
192 which is a LABEL_DECL tree node.
194 This is used for the kind of label that the user can jump to with a
195 goto statement, and for alternatives of a switch or case statement.
196 RTL labels generated for loops and conditionals don't go through here;
197 they are generated directly at the RTL level, by other functions below.
199 Note that this has nothing to do with defining label *names*.
200 Languages vary in how they do that and what that even means. */
202 void
203 expand_label (tree label)
205 rtx label_r = label_rtx (label);
207 do_pending_stack_adjust ();
208 emit_label (label_r);
209 if (DECL_NAME (label))
210 LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label));
212 if (DECL_NONLOCAL (label))
214 expand_nl_goto_receiver ();
215 nonlocal_goto_handler_labels
216 = gen_rtx_EXPR_LIST (VOIDmode, label_r,
217 nonlocal_goto_handler_labels);
220 if (FORCED_LABEL (label))
221 forced_labels = gen_rtx_EXPR_LIST (VOIDmode, label_r, forced_labels);
223 if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
224 maybe_set_first_label_num (label_r);
227 /* Generate RTL code for a `goto' statement with target label LABEL.
228 LABEL should be a LABEL_DECL tree node that was or will later be
229 defined with `expand_label'. */
231 void
232 expand_goto (tree label)
234 #ifdef ENABLE_CHECKING
235 /* Check for a nonlocal goto to a containing function. Should have
236 gotten translated to __builtin_nonlocal_goto. */
237 tree context = decl_function_context (label);
238 gcc_assert (!context || context == current_function_decl);
239 #endif
241 emit_jump (label_rtx (label));
244 /* Return the number of times character C occurs in string S. */
245 static int
246 n_occurrences (int c, const char *s)
248 int n = 0;
249 while (*s)
250 n += (*s++ == c);
251 return n;
254 /* Generate RTL for an asm statement (explicit assembler code).
255 STRING is a STRING_CST node containing the assembler code text,
256 or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the
257 insn is volatile; don't optimize it. */
259 static void
260 expand_asm_loc (tree string, int vol, location_t locus)
262 rtx body;
264 if (TREE_CODE (string) == ADDR_EXPR)
265 string = TREE_OPERAND (string, 0);
267 body = gen_rtx_ASM_INPUT_loc (VOIDmode,
268 ggc_strdup (TREE_STRING_POINTER (string)),
269 locus);
271 MEM_VOLATILE_P (body) = vol;
273 emit_insn (body);
276 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
277 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
278 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
279 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
280 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
281 constraint allows the use of a register operand. And, *IS_INOUT
282 will be true if the operand is read-write, i.e., if it is used as
283 an input as well as an output. If *CONSTRAINT_P is not in
284 canonical form, it will be made canonical. (Note that `+' will be
285 replaced with `=' as part of this process.)
287 Returns TRUE if all went well; FALSE if an error occurred. */
289 bool
290 parse_output_constraint (const char **constraint_p, int operand_num,
291 int ninputs, int noutputs, bool *allows_mem,
292 bool *allows_reg, bool *is_inout)
294 const char *constraint = *constraint_p;
295 const char *p;
297 /* Assume the constraint doesn't allow the use of either a register
298 or memory. */
299 *allows_mem = false;
300 *allows_reg = false;
302 /* Allow the `=' or `+' to not be at the beginning of the string,
303 since it wasn't explicitly documented that way, and there is a
304 large body of code that puts it last. Swap the character to
305 the front, so as not to uglify any place else. */
306 p = strchr (constraint, '=');
307 if (!p)
308 p = strchr (constraint, '+');
310 /* If the string doesn't contain an `=', issue an error
311 message. */
312 if (!p)
314 error ("output operand constraint lacks %<=%>");
315 return false;
318 /* If the constraint begins with `+', then the operand is both read
319 from and written to. */
320 *is_inout = (*p == '+');
322 /* Canonicalize the output constraint so that it begins with `='. */
323 if (p != constraint || *is_inout)
325 char *buf;
326 size_t c_len = strlen (constraint);
328 if (p != constraint)
329 warning (0, "output constraint %qc for operand %d "
330 "is not at the beginning",
331 *p, operand_num);
333 /* Make a copy of the constraint. */
334 buf = XALLOCAVEC (char, c_len + 1);
335 strcpy (buf, constraint);
336 /* Swap the first character and the `=' or `+'. */
337 buf[p - constraint] = buf[0];
338 /* Make sure the first character is an `='. (Until we do this,
339 it might be a `+'.) */
340 buf[0] = '=';
341 /* Replace the constraint with the canonicalized string. */
342 *constraint_p = ggc_alloc_string (buf, c_len);
343 constraint = *constraint_p;
346 /* Loop through the constraint string. */
347 for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p))
348 switch (*p)
350 case '+':
351 case '=':
352 error ("operand constraint contains incorrectly positioned "
353 "%<+%> or %<=%>");
354 return false;
356 case '%':
357 if (operand_num + 1 == ninputs + noutputs)
359 error ("%<%%%> constraint used with last operand");
360 return false;
362 break;
364 case 'V': case TARGET_MEM_CONSTRAINT: case 'o':
365 *allows_mem = true;
366 break;
368 case '?': case '!': case '*': case '&': case '#':
369 case 'E': case 'F': case 'G': case 'H':
370 case 's': case 'i': case 'n':
371 case 'I': case 'J': case 'K': case 'L': case 'M':
372 case 'N': case 'O': case 'P': case ',':
373 break;
375 case '0': case '1': case '2': case '3': case '4':
376 case '5': case '6': case '7': case '8': case '9':
377 case '[':
378 error ("matching constraint not valid in output operand");
379 return false;
381 case '<': case '>':
382 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
383 excepting those that expand_call created. So match memory
384 and hope. */
385 *allows_mem = true;
386 break;
388 case 'g': case 'X':
389 *allows_reg = true;
390 *allows_mem = true;
391 break;
393 case 'p': case 'r':
394 *allows_reg = true;
395 break;
397 default:
398 if (!ISALPHA (*p))
399 break;
400 if (REG_CLASS_FROM_CONSTRAINT (*p, p) != NO_REGS)
401 *allows_reg = true;
402 #ifdef EXTRA_CONSTRAINT_STR
403 else if (EXTRA_ADDRESS_CONSTRAINT (*p, p))
404 *allows_reg = true;
405 else if (EXTRA_MEMORY_CONSTRAINT (*p, p))
406 *allows_mem = true;
407 else
409 /* Otherwise we can't assume anything about the nature of
410 the constraint except that it isn't purely registers.
411 Treat it like "g" and hope for the best. */
412 *allows_reg = true;
413 *allows_mem = true;
415 #endif
416 break;
419 return true;
422 /* Similar, but for input constraints. */
424 bool
425 parse_input_constraint (const char **constraint_p, int input_num,
426 int ninputs, int noutputs, int ninout,
427 const char * const * constraints,
428 bool *allows_mem, bool *allows_reg)
430 const char *constraint = *constraint_p;
431 const char *orig_constraint = constraint;
432 size_t c_len = strlen (constraint);
433 size_t j;
434 bool saw_match = false;
436 /* Assume the constraint doesn't allow the use of either
437 a register or memory. */
438 *allows_mem = false;
439 *allows_reg = false;
441 /* Make sure constraint has neither `=', `+', nor '&'. */
443 for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
444 switch (constraint[j])
446 case '+': case '=': case '&':
447 if (constraint == orig_constraint)
449 error ("input operand constraint contains %qc", constraint[j]);
450 return false;
452 break;
454 case '%':
455 if (constraint == orig_constraint
456 && input_num + 1 == ninputs - ninout)
458 error ("%<%%%> constraint used with last operand");
459 return false;
461 break;
463 case 'V': case TARGET_MEM_CONSTRAINT: case 'o':
464 *allows_mem = true;
465 break;
467 case '<': case '>':
468 case '?': case '!': case '*': case '#':
469 case 'E': case 'F': case 'G': case 'H':
470 case 's': case 'i': case 'n':
471 case 'I': case 'J': case 'K': case 'L': case 'M':
472 case 'N': case 'O': case 'P': case ',':
473 break;
475 /* Whether or not a numeric constraint allows a register is
476 decided by the matching constraint, and so there is no need
477 to do anything special with them. We must handle them in
478 the default case, so that we don't unnecessarily force
479 operands to memory. */
480 case '0': case '1': case '2': case '3': case '4':
481 case '5': case '6': case '7': case '8': case '9':
483 char *end;
484 unsigned long match;
486 saw_match = true;
488 match = strtoul (constraint + j, &end, 10);
489 if (match >= (unsigned long) noutputs)
491 error ("matching constraint references invalid operand number");
492 return false;
495 /* Try and find the real constraint for this dup. Only do this
496 if the matching constraint is the only alternative. */
497 if (*end == '\0'
498 && (j == 0 || (j == 1 && constraint[0] == '%')))
500 constraint = constraints[match];
501 *constraint_p = constraint;
502 c_len = strlen (constraint);
503 j = 0;
504 /* ??? At the end of the loop, we will skip the first part of
505 the matched constraint. This assumes not only that the
506 other constraint is an output constraint, but also that
507 the '=' or '+' come first. */
508 break;
510 else
511 j = end - constraint;
512 /* Anticipate increment at end of loop. */
513 j--;
515 /* Fall through. */
517 case 'p': case 'r':
518 *allows_reg = true;
519 break;
521 case 'g': case 'X':
522 *allows_reg = true;
523 *allows_mem = true;
524 break;
526 default:
527 if (! ISALPHA (constraint[j]))
529 error ("invalid punctuation %qc in constraint", constraint[j]);
530 return false;
532 if (REG_CLASS_FROM_CONSTRAINT (constraint[j], constraint + j)
533 != NO_REGS)
534 *allows_reg = true;
535 #ifdef EXTRA_CONSTRAINT_STR
536 else if (EXTRA_ADDRESS_CONSTRAINT (constraint[j], constraint + j))
537 *allows_reg = true;
538 else if (EXTRA_MEMORY_CONSTRAINT (constraint[j], constraint + j))
539 *allows_mem = true;
540 else
542 /* Otherwise we can't assume anything about the nature of
543 the constraint except that it isn't purely registers.
544 Treat it like "g" and hope for the best. */
545 *allows_reg = true;
546 *allows_mem = true;
548 #endif
549 break;
552 if (saw_match && !*allows_reg)
553 warning (0, "matching constraint does not allow a register");
555 return true;
558 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
559 can be an asm-declared register. Called via walk_tree. */
561 static tree
562 decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED,
563 void *data)
565 tree decl = *declp;
566 const HARD_REG_SET *const regs = (const HARD_REG_SET *) data;
568 if (TREE_CODE (decl) == VAR_DECL)
570 if (DECL_HARD_REGISTER (decl)
571 && REG_P (DECL_RTL (decl))
572 && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
574 rtx reg = DECL_RTL (decl);
576 if (overlaps_hard_reg_set_p (*regs, GET_MODE (reg), REGNO (reg)))
577 return decl;
579 walk_subtrees = 0;
581 else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL)
582 walk_subtrees = 0;
583 return NULL_TREE;
586 /* If there is an overlap between *REGS and DECL, return the first overlap
587 found. */
588 tree
589 tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs)
591 return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL);
594 /* Check for overlap between registers marked in CLOBBERED_REGS and
595 anything inappropriate in T. Emit error and return the register
596 variable definition for error, NULL_TREE for ok. */
598 static bool
599 tree_conflicts_with_clobbers_p (tree t, HARD_REG_SET *clobbered_regs)
601 /* Conflicts between asm-declared register variables and the clobber
602 list are not allowed. */
603 tree overlap = tree_overlaps_hard_reg_set (t, clobbered_regs);
605 if (overlap)
607 error ("asm-specifier for variable %qE conflicts with asm clobber list",
608 DECL_NAME (overlap));
610 /* Reset registerness to stop multiple errors emitted for a single
611 variable. */
612 DECL_REGISTER (overlap) = 0;
613 return true;
616 return false;
619 /* Generate RTL for an asm statement with arguments.
620 STRING is the instruction template.
621 OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs.
622 Each output or input has an expression in the TREE_VALUE and
623 a tree list in TREE_PURPOSE which in turn contains a constraint
624 name in TREE_VALUE (or NULL_TREE) and a constraint string
625 in TREE_PURPOSE.
626 CLOBBERS is a list of STRING_CST nodes each naming a hard register
627 that is clobbered by this insn.
629 Not all kinds of lvalue that may appear in OUTPUTS can be stored directly.
630 Some elements of OUTPUTS may be replaced with trees representing temporary
631 values. The caller should copy those temporary values to the originally
632 specified lvalues.
634 VOL nonzero means the insn is volatile; don't optimize it. */
636 static void
637 expand_asm_operands (tree string, tree outputs, tree inputs,
638 tree clobbers, tree labels, int vol, location_t locus)
640 rtvec argvec, constraintvec, labelvec;
641 rtx body;
642 int ninputs = list_length (inputs);
643 int noutputs = list_length (outputs);
644 int nlabels = list_length (labels);
645 int ninout;
646 int nclobbers;
647 HARD_REG_SET clobbered_regs;
648 int clobber_conflict_found = 0;
649 tree tail;
650 tree t;
651 int i;
652 /* Vector of RTX's of evaluated output operands. */
653 rtx *output_rtx = XALLOCAVEC (rtx, noutputs);
654 int *inout_opnum = XALLOCAVEC (int, noutputs);
655 rtx *real_output_rtx = XALLOCAVEC (rtx, noutputs);
656 enum machine_mode *inout_mode = XALLOCAVEC (enum machine_mode, noutputs);
657 const char **constraints = XALLOCAVEC (const char *, noutputs + ninputs);
658 int old_generating_concat_p = generating_concat_p;
660 /* An ASM with no outputs needs to be treated as volatile, for now. */
661 if (noutputs == 0)
662 vol = 1;
664 if (! check_operand_nalternatives (outputs, inputs))
665 return;
667 string = resolve_asm_operand_names (string, outputs, inputs, labels);
669 /* Collect constraints. */
670 i = 0;
671 for (t = outputs; t ; t = TREE_CHAIN (t), i++)
672 constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
673 for (t = inputs; t ; t = TREE_CHAIN (t), i++)
674 constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
676 /* Sometimes we wish to automatically clobber registers across an asm.
677 Case in point is when the i386 backend moved from cc0 to a hard reg --
678 maintaining source-level compatibility means automatically clobbering
679 the flags register. */
680 clobbers = targetm.md_asm_clobbers (outputs, inputs, clobbers);
682 /* Count the number of meaningful clobbered registers, ignoring what
683 we would ignore later. */
684 nclobbers = 0;
685 CLEAR_HARD_REG_SET (clobbered_regs);
686 for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
688 const char *regname;
689 int nregs;
691 if (TREE_VALUE (tail) == error_mark_node)
692 return;
693 regname = TREE_STRING_POINTER (TREE_VALUE (tail));
695 i = decode_reg_name_and_count (regname, &nregs);
696 if (i == -4)
697 ++nclobbers;
698 else if (i == -2)
699 error ("unknown register name %qs in %<asm%>", regname);
701 /* Mark clobbered registers. */
702 if (i >= 0)
704 int reg;
706 for (reg = i; reg < i + nregs; reg++)
708 ++nclobbers;
710 /* Clobbering the PIC register is an error. */
711 if (reg == (int) PIC_OFFSET_TABLE_REGNUM)
713 error ("PIC register clobbered by %qs in %<asm%>", regname);
714 return;
717 SET_HARD_REG_BIT (clobbered_regs, reg);
722 /* First pass over inputs and outputs checks validity and sets
723 mark_addressable if needed. */
725 ninout = 0;
726 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
728 tree val = TREE_VALUE (tail);
729 tree type = TREE_TYPE (val);
730 const char *constraint;
731 bool is_inout;
732 bool allows_reg;
733 bool allows_mem;
735 /* If there's an erroneous arg, emit no insn. */
736 if (type == error_mark_node)
737 return;
739 /* Try to parse the output constraint. If that fails, there's
740 no point in going further. */
741 constraint = constraints[i];
742 if (!parse_output_constraint (&constraint, i, ninputs, noutputs,
743 &allows_mem, &allows_reg, &is_inout))
744 return;
746 if (! allows_reg
747 && (allows_mem
748 || is_inout
749 || (DECL_P (val)
750 && REG_P (DECL_RTL (val))
751 && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))))
752 mark_addressable (val);
754 if (is_inout)
755 ninout++;
758 ninputs += ninout;
759 if (ninputs + noutputs > MAX_RECOG_OPERANDS)
761 error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS);
762 return;
765 for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail))
767 bool allows_reg, allows_mem;
768 const char *constraint;
770 /* If there's an erroneous arg, emit no insn, because the ASM_INPUT
771 would get VOIDmode and that could cause a crash in reload. */
772 if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node)
773 return;
775 constraint = constraints[i + noutputs];
776 if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
777 constraints, &allows_mem, &allows_reg))
778 return;
780 if (! allows_reg && allows_mem)
781 mark_addressable (TREE_VALUE (tail));
784 /* Second pass evaluates arguments. */
786 /* Make sure stack is consistent for asm goto. */
787 if (nlabels > 0)
788 do_pending_stack_adjust ();
790 ninout = 0;
791 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
793 tree val = TREE_VALUE (tail);
794 tree type = TREE_TYPE (val);
795 bool is_inout;
796 bool allows_reg;
797 bool allows_mem;
798 rtx op;
799 bool ok;
801 ok = parse_output_constraint (&constraints[i], i, ninputs,
802 noutputs, &allows_mem, &allows_reg,
803 &is_inout);
804 gcc_assert (ok);
806 /* If an output operand is not a decl or indirect ref and our constraint
807 allows a register, make a temporary to act as an intermediate.
808 Make the asm insn write into that, then our caller will copy it to
809 the real output operand. Likewise for promoted variables. */
811 generating_concat_p = 0;
813 real_output_rtx[i] = NULL_RTX;
814 if ((TREE_CODE (val) == INDIRECT_REF
815 && allows_mem)
816 || (DECL_P (val)
817 && (allows_mem || REG_P (DECL_RTL (val)))
818 && ! (REG_P (DECL_RTL (val))
819 && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))
820 || ! allows_reg
821 || is_inout)
823 op = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE);
824 if (MEM_P (op))
825 op = validize_mem (op);
827 if (! allows_reg && !MEM_P (op))
828 error ("output number %d not directly addressable", i);
829 if ((! allows_mem && MEM_P (op))
830 || GET_CODE (op) == CONCAT)
832 real_output_rtx[i] = op;
833 op = gen_reg_rtx (GET_MODE (op));
834 if (is_inout)
835 emit_move_insn (op, real_output_rtx[i]);
838 else
840 op = assign_temp (type, 0, 0, 1);
841 op = validize_mem (op);
842 if (!MEM_P (op) && TREE_CODE (TREE_VALUE (tail)) == SSA_NAME)
843 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (TREE_VALUE (tail)), op);
844 TREE_VALUE (tail) = make_tree (type, op);
846 output_rtx[i] = op;
848 generating_concat_p = old_generating_concat_p;
850 if (is_inout)
852 inout_mode[ninout] = TYPE_MODE (type);
853 inout_opnum[ninout++] = i;
856 if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
857 clobber_conflict_found = 1;
860 /* Make vectors for the expression-rtx, constraint strings,
861 and named operands. */
863 argvec = rtvec_alloc (ninputs);
864 constraintvec = rtvec_alloc (ninputs);
865 labelvec = rtvec_alloc (nlabels);
867 body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode
868 : GET_MODE (output_rtx[0])),
869 ggc_strdup (TREE_STRING_POINTER (string)),
870 empty_string, 0, argvec, constraintvec,
871 labelvec, locus);
873 MEM_VOLATILE_P (body) = vol;
875 /* Eval the inputs and put them into ARGVEC.
876 Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */
878 for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i)
880 bool allows_reg, allows_mem;
881 const char *constraint;
882 tree val, type;
883 rtx op;
884 bool ok;
886 constraint = constraints[i + noutputs];
887 ok = parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
888 constraints, &allows_mem, &allows_reg);
889 gcc_assert (ok);
891 generating_concat_p = 0;
893 val = TREE_VALUE (tail);
894 type = TREE_TYPE (val);
895 /* EXPAND_INITIALIZER will not generate code for valid initializer
896 constants, but will still generate code for other types of operand.
897 This is the behavior we want for constant constraints. */
898 op = expand_expr (val, NULL_RTX, VOIDmode,
899 allows_reg ? EXPAND_NORMAL
900 : allows_mem ? EXPAND_MEMORY
901 : EXPAND_INITIALIZER);
903 /* Never pass a CONCAT to an ASM. */
904 if (GET_CODE (op) == CONCAT)
905 op = force_reg (GET_MODE (op), op);
906 else if (MEM_P (op))
907 op = validize_mem (op);
909 if (asm_operand_ok (op, constraint, NULL) <= 0)
911 if (allows_reg && TYPE_MODE (type) != BLKmode)
912 op = force_reg (TYPE_MODE (type), op);
913 else if (!allows_mem)
914 warning (0, "asm operand %d probably doesn%'t match constraints",
915 i + noutputs);
916 else if (MEM_P (op))
918 /* We won't recognize either volatile memory or memory
919 with a queued address as available a memory_operand
920 at this point. Ignore it: clearly this *is* a memory. */
922 else
924 warning (0, "use of memory input without lvalue in "
925 "asm operand %d is deprecated", i + noutputs);
927 if (CONSTANT_P (op))
929 rtx mem = force_const_mem (TYPE_MODE (type), op);
930 if (mem)
931 op = validize_mem (mem);
932 else
933 op = force_reg (TYPE_MODE (type), op);
935 if (REG_P (op)
936 || GET_CODE (op) == SUBREG
937 || GET_CODE (op) == CONCAT)
939 tree qual_type = build_qualified_type (type,
940 (TYPE_QUALS (type)
941 | TYPE_QUAL_CONST));
942 rtx memloc = assign_temp (qual_type, 1, 1, 1);
943 memloc = validize_mem (memloc);
944 emit_move_insn (memloc, op);
945 op = memloc;
950 generating_concat_p = old_generating_concat_p;
951 ASM_OPERANDS_INPUT (body, i) = op;
953 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i)
954 = gen_rtx_ASM_INPUT (TYPE_MODE (type),
955 ggc_strdup (constraints[i + noutputs]));
957 if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
958 clobber_conflict_found = 1;
961 /* Protect all the operands from the queue now that they have all been
962 evaluated. */
964 generating_concat_p = 0;
966 /* For in-out operands, copy output rtx to input rtx. */
967 for (i = 0; i < ninout; i++)
969 int j = inout_opnum[i];
970 char buffer[16];
972 ASM_OPERANDS_INPUT (body, ninputs - ninout + i)
973 = output_rtx[j];
975 sprintf (buffer, "%d", j);
976 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i)
977 = gen_rtx_ASM_INPUT (inout_mode[i], ggc_strdup (buffer));
980 /* Copy labels to the vector. */
981 for (i = 0, tail = labels; i < nlabels; ++i, tail = TREE_CHAIN (tail))
982 ASM_OPERANDS_LABEL (body, i)
983 = gen_rtx_LABEL_REF (Pmode, label_rtx (TREE_VALUE (tail)));
985 generating_concat_p = old_generating_concat_p;
987 /* Now, for each output, construct an rtx
988 (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER
989 ARGVEC CONSTRAINTS OPNAMES))
990 If there is more than one, put them inside a PARALLEL. */
992 if (nlabels > 0 && nclobbers == 0)
994 gcc_assert (noutputs == 0);
995 emit_jump_insn (body);
997 else if (noutputs == 0 && nclobbers == 0)
999 /* No output operands: put in a raw ASM_OPERANDS rtx. */
1000 emit_insn (body);
1002 else if (noutputs == 1 && nclobbers == 0)
1004 ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = ggc_strdup (constraints[0]);
1005 emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body));
1007 else
1009 rtx obody = body;
1010 int num = noutputs;
1012 if (num == 0)
1013 num = 1;
1015 body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers));
1017 /* For each output operand, store a SET. */
1018 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1020 XVECEXP (body, 0, i)
1021 = gen_rtx_SET (VOIDmode,
1022 output_rtx[i],
1023 gen_rtx_ASM_OPERANDS
1024 (GET_MODE (output_rtx[i]),
1025 ggc_strdup (TREE_STRING_POINTER (string)),
1026 ggc_strdup (constraints[i]),
1027 i, argvec, constraintvec, labelvec, locus));
1029 MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol;
1032 /* If there are no outputs (but there are some clobbers)
1033 store the bare ASM_OPERANDS into the PARALLEL. */
1035 if (i == 0)
1036 XVECEXP (body, 0, i++) = obody;
1038 /* Store (clobber REG) for each clobbered register specified. */
1040 for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
1042 const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
1043 int reg, nregs;
1044 int j = decode_reg_name_and_count (regname, &nregs);
1045 rtx clobbered_reg;
1047 if (j < 0)
1049 if (j == -3) /* `cc', which is not a register */
1050 continue;
1052 if (j == -4) /* `memory', don't cache memory across asm */
1054 XVECEXP (body, 0, i++)
1055 = gen_rtx_CLOBBER (VOIDmode,
1056 gen_rtx_MEM
1057 (BLKmode,
1058 gen_rtx_SCRATCH (VOIDmode)));
1059 continue;
1062 /* Ignore unknown register, error already signaled. */
1063 continue;
1066 for (reg = j; reg < j + nregs; reg++)
1068 /* Use QImode since that's guaranteed to clobber just
1069 * one reg. */
1070 clobbered_reg = gen_rtx_REG (QImode, reg);
1072 /* Do sanity check for overlap between clobbers and
1073 respectively input and outputs that hasn't been
1074 handled. Such overlap should have been detected and
1075 reported above. */
1076 if (!clobber_conflict_found)
1078 int opno;
1080 /* We test the old body (obody) contents to avoid
1081 tripping over the under-construction body. */
1082 for (opno = 0; opno < noutputs; opno++)
1083 if (reg_overlap_mentioned_p (clobbered_reg,
1084 output_rtx[opno]))
1085 internal_error
1086 ("asm clobber conflict with output operand");
1088 for (opno = 0; opno < ninputs - ninout; opno++)
1089 if (reg_overlap_mentioned_p (clobbered_reg,
1090 ASM_OPERANDS_INPUT (obody,
1091 opno)))
1092 internal_error
1093 ("asm clobber conflict with input operand");
1096 XVECEXP (body, 0, i++)
1097 = gen_rtx_CLOBBER (VOIDmode, clobbered_reg);
1101 if (nlabels > 0)
1102 emit_jump_insn (body);
1103 else
1104 emit_insn (body);
1107 /* For any outputs that needed reloading into registers, spill them
1108 back to where they belong. */
1109 for (i = 0; i < noutputs; ++i)
1110 if (real_output_rtx[i])
1111 emit_move_insn (real_output_rtx[i], output_rtx[i]);
1113 crtl->has_asm_statement = 1;
1114 free_temp_slots ();
1117 void
1118 expand_asm_stmt (gimple stmt)
1120 int noutputs;
1121 tree outputs, tail, t;
1122 tree *o;
1123 size_t i, n;
1124 const char *s;
1125 tree str, out, in, cl, labels;
1126 location_t locus = gimple_location (stmt);
1128 /* Meh... convert the gimple asm operands into real tree lists.
1129 Eventually we should make all routines work on the vectors instead
1130 of relying on TREE_CHAIN. */
1131 out = NULL_TREE;
1132 n = gimple_asm_noutputs (stmt);
1133 if (n > 0)
1135 t = out = gimple_asm_output_op (stmt, 0);
1136 for (i = 1; i < n; i++)
1137 t = TREE_CHAIN (t) = gimple_asm_output_op (stmt, i);
1140 in = NULL_TREE;
1141 n = gimple_asm_ninputs (stmt);
1142 if (n > 0)
1144 t = in = gimple_asm_input_op (stmt, 0);
1145 for (i = 1; i < n; i++)
1146 t = TREE_CHAIN (t) = gimple_asm_input_op (stmt, i);
1149 cl = NULL_TREE;
1150 n = gimple_asm_nclobbers (stmt);
1151 if (n > 0)
1153 t = cl = gimple_asm_clobber_op (stmt, 0);
1154 for (i = 1; i < n; i++)
1155 t = TREE_CHAIN (t) = gimple_asm_clobber_op (stmt, i);
1158 labels = NULL_TREE;
1159 n = gimple_asm_nlabels (stmt);
1160 if (n > 0)
1162 t = labels = gimple_asm_label_op (stmt, 0);
1163 for (i = 1; i < n; i++)
1164 t = TREE_CHAIN (t) = gimple_asm_label_op (stmt, i);
1167 s = gimple_asm_string (stmt);
1168 str = build_string (strlen (s), s);
1170 if (gimple_asm_input_p (stmt))
1172 expand_asm_loc (str, gimple_asm_volatile_p (stmt), locus);
1173 return;
1176 outputs = out;
1177 noutputs = gimple_asm_noutputs (stmt);
1178 /* o[I] is the place that output number I should be written. */
1179 o = (tree *) alloca (noutputs * sizeof (tree));
1181 /* Record the contents of OUTPUTS before it is modified. */
1182 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1183 o[i] = TREE_VALUE (tail);
1185 /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of
1186 OUTPUTS some trees for where the values were actually stored. */
1187 expand_asm_operands (str, outputs, in, cl, labels,
1188 gimple_asm_volatile_p (stmt), locus);
1190 /* Copy all the intermediate outputs into the specified outputs. */
1191 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1193 if (o[i] != TREE_VALUE (tail))
1195 expand_assignment (o[i], TREE_VALUE (tail), false);
1196 free_temp_slots ();
1198 /* Restore the original value so that it's correct the next
1199 time we expand this function. */
1200 TREE_VALUE (tail) = o[i];
1205 /* A subroutine of expand_asm_operands. Check that all operands have
1206 the same number of alternatives. Return true if so. */
1208 static bool
1209 check_operand_nalternatives (tree outputs, tree inputs)
1211 if (outputs || inputs)
1213 tree tmp = TREE_PURPOSE (outputs ? outputs : inputs);
1214 int nalternatives
1215 = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp)));
1216 tree next = inputs;
1218 if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES)
1220 error ("too many alternatives in %<asm%>");
1221 return false;
1224 tmp = outputs;
1225 while (tmp)
1227 const char *constraint
1228 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp)));
1230 if (n_occurrences (',', constraint) != nalternatives)
1232 error ("operand constraints for %<asm%> differ "
1233 "in number of alternatives");
1234 return false;
1237 if (TREE_CHAIN (tmp))
1238 tmp = TREE_CHAIN (tmp);
1239 else
1240 tmp = next, next = 0;
1244 return true;
1247 /* A subroutine of expand_asm_operands. Check that all operand names
1248 are unique. Return true if so. We rely on the fact that these names
1249 are identifiers, and so have been canonicalized by get_identifier,
1250 so all we need are pointer comparisons. */
1252 static bool
1253 check_unique_operand_names (tree outputs, tree inputs, tree labels)
1255 tree i, j;
1257 for (i = outputs; i ; i = TREE_CHAIN (i))
1259 tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1260 if (! i_name)
1261 continue;
1263 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1264 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1265 goto failure;
1268 for (i = inputs; i ; i = TREE_CHAIN (i))
1270 tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1271 if (! i_name)
1272 continue;
1274 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1275 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1276 goto failure;
1277 for (j = outputs; j ; j = TREE_CHAIN (j))
1278 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1279 goto failure;
1282 for (i = labels; i ; i = TREE_CHAIN (i))
1284 tree i_name = TREE_PURPOSE (i);
1285 if (! i_name)
1286 continue;
1288 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1289 if (simple_cst_equal (i_name, TREE_PURPOSE (j)))
1290 goto failure;
1291 for (j = inputs; j ; j = TREE_CHAIN (j))
1292 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1293 goto failure;
1296 return true;
1298 failure:
1299 error ("duplicate asm operand name %qs",
1300 TREE_STRING_POINTER (TREE_PURPOSE (TREE_PURPOSE (i))));
1301 return false;
1304 /* A subroutine of expand_asm_operands. Resolve the names of the operands
1305 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
1306 STRING and in the constraints to those numbers. */
1308 tree
1309 resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels)
1311 char *buffer;
1312 char *p;
1313 const char *c;
1314 tree t;
1316 check_unique_operand_names (outputs, inputs, labels);
1318 /* Substitute [<name>] in input constraint strings. There should be no
1319 named operands in output constraints. */
1320 for (t = inputs; t ; t = TREE_CHAIN (t))
1322 c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
1323 if (strchr (c, '[') != NULL)
1325 p = buffer = xstrdup (c);
1326 while ((p = strchr (p, '[')) != NULL)
1327 p = resolve_operand_name_1 (p, outputs, inputs, NULL);
1328 TREE_VALUE (TREE_PURPOSE (t))
1329 = build_string (strlen (buffer), buffer);
1330 free (buffer);
1334 /* Now check for any needed substitutions in the template. */
1335 c = TREE_STRING_POINTER (string);
1336 while ((c = strchr (c, '%')) != NULL)
1338 if (c[1] == '[')
1339 break;
1340 else if (ISALPHA (c[1]) && c[2] == '[')
1341 break;
1342 else
1344 c += 1 + (c[1] == '%');
1345 continue;
1349 if (c)
1351 /* OK, we need to make a copy so we can perform the substitutions.
1352 Assume that we will not need extra space--we get to remove '['
1353 and ']', which means we cannot have a problem until we have more
1354 than 999 operands. */
1355 buffer = xstrdup (TREE_STRING_POINTER (string));
1356 p = buffer + (c - TREE_STRING_POINTER (string));
1358 while ((p = strchr (p, '%')) != NULL)
1360 if (p[1] == '[')
1361 p += 1;
1362 else if (ISALPHA (p[1]) && p[2] == '[')
1363 p += 2;
1364 else
1366 p += 1 + (p[1] == '%');
1367 continue;
1370 p = resolve_operand_name_1 (p, outputs, inputs, labels);
1373 string = build_string (strlen (buffer), buffer);
1374 free (buffer);
1377 return string;
1380 /* A subroutine of resolve_operand_names. P points to the '[' for a
1381 potential named operand of the form [<name>]. In place, replace
1382 the name and brackets with a number. Return a pointer to the
1383 balance of the string after substitution. */
1385 static char *
1386 resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels)
1388 char *q;
1389 int op;
1390 tree t;
1392 /* Collect the operand name. */
1393 q = strchr (++p, ']');
1394 if (!q)
1396 error ("missing close brace for named operand");
1397 return strchr (p, '\0');
1399 *q = '\0';
1401 /* Resolve the name to a number. */
1402 for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
1404 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1405 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1406 goto found;
1408 for (t = inputs; t ; t = TREE_CHAIN (t), op++)
1410 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1411 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1412 goto found;
1414 for (t = labels; t ; t = TREE_CHAIN (t), op++)
1416 tree name = TREE_PURPOSE (t);
1417 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1418 goto found;
1421 error ("undefined named operand %qs", identifier_to_locale (p));
1422 op = 0;
1424 found:
1425 /* Replace the name with the number. Unfortunately, not all libraries
1426 get the return value of sprintf correct, so search for the end of the
1427 generated string by hand. */
1428 sprintf (--p, "%d", op);
1429 p = strchr (p, '\0');
1431 /* Verify the no extra buffer space assumption. */
1432 gcc_assert (p <= q);
1434 /* Shift the rest of the buffer down to fill the gap. */
1435 memmove (p, q + 1, strlen (q + 1) + 1);
1437 return p;
1440 /* Generate RTL to evaluate the expression EXP. */
1442 void
1443 expand_expr_stmt (tree exp)
1445 rtx value;
1446 tree type;
1448 value = expand_expr (exp, const0_rtx, VOIDmode, EXPAND_NORMAL);
1449 type = TREE_TYPE (exp);
1451 /* If all we do is reference a volatile value in memory,
1452 copy it to a register to be sure it is actually touched. */
1453 if (value && MEM_P (value) && TREE_THIS_VOLATILE (exp))
1455 if (TYPE_MODE (type) == VOIDmode)
1457 else if (TYPE_MODE (type) != BLKmode)
1458 value = copy_to_reg (value);
1459 else
1461 rtx lab = gen_label_rtx ();
1463 /* Compare the value with itself to reference it. */
1464 emit_cmp_and_jump_insns (value, value, EQ,
1465 expand_normal (TYPE_SIZE (type)),
1466 BLKmode, 0, lab);
1467 emit_label (lab);
1471 /* Free any temporaries used to evaluate this expression. */
1472 free_temp_slots ();
1475 /* Warn if EXP contains any computations whose results are not used.
1476 Return 1 if a warning is printed; 0 otherwise. LOCUS is the
1477 (potential) location of the expression. */
1480 warn_if_unused_value (const_tree exp, location_t locus)
1482 restart:
1483 if (TREE_USED (exp) || TREE_NO_WARNING (exp))
1484 return 0;
1486 /* Don't warn about void constructs. This includes casting to void,
1487 void function calls, and statement expressions with a final cast
1488 to void. */
1489 if (VOID_TYPE_P (TREE_TYPE (exp)))
1490 return 0;
1492 if (EXPR_HAS_LOCATION (exp))
1493 locus = EXPR_LOCATION (exp);
1495 switch (TREE_CODE (exp))
1497 case PREINCREMENT_EXPR:
1498 case POSTINCREMENT_EXPR:
1499 case PREDECREMENT_EXPR:
1500 case POSTDECREMENT_EXPR:
1501 case MODIFY_EXPR:
1502 case INIT_EXPR:
1503 case TARGET_EXPR:
1504 case CALL_EXPR:
1505 case TRY_CATCH_EXPR:
1506 case WITH_CLEANUP_EXPR:
1507 case EXIT_EXPR:
1508 case VA_ARG_EXPR:
1509 return 0;
1511 case BIND_EXPR:
1512 /* For a binding, warn if no side effect within it. */
1513 exp = BIND_EXPR_BODY (exp);
1514 goto restart;
1516 case SAVE_EXPR:
1517 case NON_LVALUE_EXPR:
1518 exp = TREE_OPERAND (exp, 0);
1519 goto restart;
1521 case TRUTH_ORIF_EXPR:
1522 case TRUTH_ANDIF_EXPR:
1523 /* In && or ||, warn if 2nd operand has no side effect. */
1524 exp = TREE_OPERAND (exp, 1);
1525 goto restart;
1527 case COMPOUND_EXPR:
1528 if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus))
1529 return 1;
1530 /* Let people do `(foo (), 0)' without a warning. */
1531 if (TREE_CONSTANT (TREE_OPERAND (exp, 1)))
1532 return 0;
1533 exp = TREE_OPERAND (exp, 1);
1534 goto restart;
1536 case COND_EXPR:
1537 /* If this is an expression with side effects, don't warn; this
1538 case commonly appears in macro expansions. */
1539 if (TREE_SIDE_EFFECTS (exp))
1540 return 0;
1541 goto warn;
1543 case INDIRECT_REF:
1544 /* Don't warn about automatic dereferencing of references, since
1545 the user cannot control it. */
1546 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE)
1548 exp = TREE_OPERAND (exp, 0);
1549 goto restart;
1551 /* Fall through. */
1553 default:
1554 /* Referencing a volatile value is a side effect, so don't warn. */
1555 if ((DECL_P (exp) || REFERENCE_CLASS_P (exp))
1556 && TREE_THIS_VOLATILE (exp))
1557 return 0;
1559 /* If this is an expression which has no operands, there is no value
1560 to be unused. There are no such language-independent codes,
1561 but front ends may define such. */
1562 if (EXPRESSION_CLASS_P (exp) && TREE_OPERAND_LENGTH (exp) == 0)
1563 return 0;
1565 warn:
1566 warning_at (locus, OPT_Wunused_value, "value computed is not used");
1567 return 1;
1572 /* Generate RTL to return from the current function, with no value.
1573 (That is, we do not do anything about returning any value.) */
1575 void
1576 expand_null_return (void)
1578 /* If this function was declared to return a value, but we
1579 didn't, clobber the return registers so that they are not
1580 propagated live to the rest of the function. */
1581 clobber_return_register ();
1583 expand_null_return_1 ();
1586 /* Generate RTL to return directly from the current function.
1587 (That is, we bypass any return value.) */
1589 void
1590 expand_naked_return (void)
1592 rtx end_label;
1594 clear_pending_stack_adjust ();
1595 do_pending_stack_adjust ();
1597 end_label = naked_return_label;
1598 if (end_label == 0)
1599 end_label = naked_return_label = gen_label_rtx ();
1601 emit_jump (end_label);
1604 /* Generate RTL to return from the current function, with value VAL. */
1606 static void
1607 expand_value_return (rtx val)
1609 /* Copy the value to the return location unless it's already there. */
1611 tree decl = DECL_RESULT (current_function_decl);
1612 rtx return_reg = DECL_RTL (decl);
1613 if (return_reg != val)
1615 tree funtype = TREE_TYPE (current_function_decl);
1616 tree type = TREE_TYPE (decl);
1617 int unsignedp = TYPE_UNSIGNED (type);
1618 enum machine_mode old_mode = DECL_MODE (decl);
1619 enum machine_mode mode;
1620 if (DECL_BY_REFERENCE (decl))
1621 mode = promote_function_mode (type, old_mode, &unsignedp, funtype, 2);
1622 else
1623 mode = promote_function_mode (type, old_mode, &unsignedp, funtype, 1);
1625 if (mode != old_mode)
1626 val = convert_modes (mode, old_mode, val, unsignedp);
1628 if (GET_CODE (return_reg) == PARALLEL)
1629 emit_group_load (return_reg, val, type, int_size_in_bytes (type));
1630 else
1631 emit_move_insn (return_reg, val);
1634 expand_null_return_1 ();
1637 /* Output a return with no value. */
1639 static void
1640 expand_null_return_1 (void)
1642 clear_pending_stack_adjust ();
1643 do_pending_stack_adjust ();
1644 emit_jump (return_label);
1647 /* Generate RTL to evaluate the expression RETVAL and return it
1648 from the current function. */
1650 void
1651 expand_return (tree retval)
1653 rtx result_rtl;
1654 rtx val = 0;
1655 tree retval_rhs;
1657 /* If function wants no value, give it none. */
1658 if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE)
1660 expand_normal (retval);
1661 expand_null_return ();
1662 return;
1665 if (retval == error_mark_node)
1667 /* Treat this like a return of no value from a function that
1668 returns a value. */
1669 expand_null_return ();
1670 return;
1672 else if ((TREE_CODE (retval) == MODIFY_EXPR
1673 || TREE_CODE (retval) == INIT_EXPR)
1674 && TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL)
1675 retval_rhs = TREE_OPERAND (retval, 1);
1676 else
1677 retval_rhs = retval;
1679 result_rtl = DECL_RTL (DECL_RESULT (current_function_decl));
1681 /* If we are returning the RESULT_DECL, then the value has already
1682 been stored into it, so we don't have to do anything special. */
1683 if (TREE_CODE (retval_rhs) == RESULT_DECL)
1684 expand_value_return (result_rtl);
1686 /* If the result is an aggregate that is being returned in one (or more)
1687 registers, load the registers here. The compiler currently can't handle
1688 copying a BLKmode value into registers. We could put this code in a
1689 more general area (for use by everyone instead of just function
1690 call/return), but until this feature is generally usable it is kept here
1691 (and in expand_call). */
1693 else if (retval_rhs != 0
1694 && TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode
1695 && REG_P (result_rtl))
1697 int i;
1698 unsigned HOST_WIDE_INT bitpos, xbitpos;
1699 unsigned HOST_WIDE_INT padding_correction = 0;
1700 unsigned HOST_WIDE_INT bytes
1701 = int_size_in_bytes (TREE_TYPE (retval_rhs));
1702 int n_regs = (bytes + UNITS_PER_WORD - 1) / UNITS_PER_WORD;
1703 unsigned int bitsize
1704 = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)), BITS_PER_WORD);
1705 rtx *result_pseudos = XALLOCAVEC (rtx, n_regs);
1706 rtx result_reg, src = NULL_RTX, dst = NULL_RTX;
1707 rtx result_val = expand_normal (retval_rhs);
1708 enum machine_mode tmpmode, result_reg_mode;
1710 if (bytes == 0)
1712 expand_null_return ();
1713 return;
1716 /* If the structure doesn't take up a whole number of words, see
1717 whether the register value should be padded on the left or on
1718 the right. Set PADDING_CORRECTION to the number of padding
1719 bits needed on the left side.
1721 In most ABIs, the structure will be returned at the least end of
1722 the register, which translates to right padding on little-endian
1723 targets and left padding on big-endian targets. The opposite
1724 holds if the structure is returned at the most significant
1725 end of the register. */
1726 if (bytes % UNITS_PER_WORD != 0
1727 && (targetm.calls.return_in_msb (TREE_TYPE (retval_rhs))
1728 ? !BYTES_BIG_ENDIAN
1729 : BYTES_BIG_ENDIAN))
1730 padding_correction = (BITS_PER_WORD - ((bytes % UNITS_PER_WORD)
1731 * BITS_PER_UNIT));
1733 /* Copy the structure BITSIZE bits at a time. */
1734 for (bitpos = 0, xbitpos = padding_correction;
1735 bitpos < bytes * BITS_PER_UNIT;
1736 bitpos += bitsize, xbitpos += bitsize)
1738 /* We need a new destination pseudo each time xbitpos is
1739 on a word boundary and when xbitpos == padding_correction
1740 (the first time through). */
1741 if (xbitpos % BITS_PER_WORD == 0
1742 || xbitpos == padding_correction)
1744 /* Generate an appropriate register. */
1745 dst = gen_reg_rtx (word_mode);
1746 result_pseudos[xbitpos / BITS_PER_WORD] = dst;
1748 /* Clear the destination before we move anything into it. */
1749 emit_move_insn (dst, CONST0_RTX (GET_MODE (dst)));
1752 /* We need a new source operand each time bitpos is on a word
1753 boundary. */
1754 if (bitpos % BITS_PER_WORD == 0)
1755 src = operand_subword_force (result_val,
1756 bitpos / BITS_PER_WORD,
1757 BLKmode);
1759 /* Use bitpos for the source extraction (left justified) and
1760 xbitpos for the destination store (right justified). */
1761 store_bit_field (dst, bitsize, xbitpos % BITS_PER_WORD, word_mode,
1762 extract_bit_field (src, bitsize,
1763 bitpos % BITS_PER_WORD, 1, false,
1764 NULL_RTX, word_mode, word_mode));
1767 tmpmode = GET_MODE (result_rtl);
1768 if (tmpmode == BLKmode)
1770 /* Find the smallest integer mode large enough to hold the
1771 entire structure and use that mode instead of BLKmode
1772 on the USE insn for the return register. */
1773 for (tmpmode = GET_CLASS_NARROWEST_MODE (MODE_INT);
1774 tmpmode != VOIDmode;
1775 tmpmode = GET_MODE_WIDER_MODE (tmpmode))
1776 /* Have we found a large enough mode? */
1777 if (GET_MODE_SIZE (tmpmode) >= bytes)
1778 break;
1780 /* A suitable mode should have been found. */
1781 gcc_assert (tmpmode != VOIDmode);
1783 PUT_MODE (result_rtl, tmpmode);
1786 if (GET_MODE_SIZE (tmpmode) < GET_MODE_SIZE (word_mode))
1787 result_reg_mode = word_mode;
1788 else
1789 result_reg_mode = tmpmode;
1790 result_reg = gen_reg_rtx (result_reg_mode);
1792 for (i = 0; i < n_regs; i++)
1793 emit_move_insn (operand_subword (result_reg, i, 0, result_reg_mode),
1794 result_pseudos[i]);
1796 if (tmpmode != result_reg_mode)
1797 result_reg = gen_lowpart (tmpmode, result_reg);
1799 expand_value_return (result_reg);
1801 else if (retval_rhs != 0
1802 && !VOID_TYPE_P (TREE_TYPE (retval_rhs))
1803 && (REG_P (result_rtl)
1804 || (GET_CODE (result_rtl) == PARALLEL)))
1806 /* Calculate the return value into a temporary (usually a pseudo
1807 reg). */
1808 tree ot = TREE_TYPE (DECL_RESULT (current_function_decl));
1809 tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST);
1811 val = assign_temp (nt, 0, 0, 1);
1812 val = expand_expr (retval_rhs, val, GET_MODE (val), EXPAND_NORMAL);
1813 val = force_not_mem (val);
1814 /* Return the calculated value. */
1815 expand_value_return (val);
1817 else
1819 /* No hard reg used; calculate value into hard return reg. */
1820 expand_expr (retval, const0_rtx, VOIDmode, EXPAND_NORMAL);
1821 expand_value_return (result_rtl);
1825 /* Emit code to restore vital registers at the beginning of a nonlocal goto
1826 handler. */
1827 static void
1828 expand_nl_goto_receiver (void)
1830 rtx chain;
1832 /* Clobber the FP when we get here, so we have to make sure it's
1833 marked as used by this function. */
1834 emit_use (hard_frame_pointer_rtx);
1836 /* Mark the static chain as clobbered here so life information
1837 doesn't get messed up for it. */
1838 chain = targetm.calls.static_chain (current_function_decl, true);
1839 if (chain && REG_P (chain))
1840 emit_clobber (chain);
1842 #ifdef HAVE_nonlocal_goto
1843 if (! HAVE_nonlocal_goto)
1844 #endif
1845 /* First adjust our frame pointer to its actual value. It was
1846 previously set to the start of the virtual area corresponding to
1847 the stacked variables when we branched here and now needs to be
1848 adjusted to the actual hardware fp value.
1850 Assignments are to virtual registers are converted by
1851 instantiate_virtual_regs into the corresponding assignment
1852 to the underlying register (fp in this case) that makes
1853 the original assignment true.
1854 So the following insn will actually be
1855 decrementing fp by STARTING_FRAME_OFFSET. */
1856 emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx);
1858 #if !HARD_FRAME_POINTER_IS_ARG_POINTER
1859 if (fixed_regs[ARG_POINTER_REGNUM])
1861 #ifdef ELIMINABLE_REGS
1862 /* If the argument pointer can be eliminated in favor of the
1863 frame pointer, we don't need to restore it. We assume here
1864 that if such an elimination is present, it can always be used.
1865 This is the case on all known machines; if we don't make this
1866 assumption, we do unnecessary saving on many machines. */
1867 static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS;
1868 size_t i;
1870 for (i = 0; i < ARRAY_SIZE (elim_regs); i++)
1871 if (elim_regs[i].from == ARG_POINTER_REGNUM
1872 && elim_regs[i].to == HARD_FRAME_POINTER_REGNUM)
1873 break;
1875 if (i == ARRAY_SIZE (elim_regs))
1876 #endif
1878 /* Now restore our arg pointer from the address at which it
1879 was saved in our stack frame. */
1880 emit_move_insn (crtl->args.internal_arg_pointer,
1881 copy_to_reg (get_arg_pointer_save_area ()));
1884 #endif
1886 #ifdef HAVE_nonlocal_goto_receiver
1887 if (HAVE_nonlocal_goto_receiver)
1888 emit_insn (gen_nonlocal_goto_receiver ());
1889 #endif
1891 /* We must not allow the code we just generated to be reordered by
1892 scheduling. Specifically, the update of the frame pointer must
1893 happen immediately, not later. */
1894 emit_insn (gen_blockage ());
1897 /* Generate RTL for the automatic variable declaration DECL.
1898 (Other kinds of declarations are simply ignored if seen here.) */
1900 void
1901 expand_decl (tree decl)
1903 tree type;
1905 type = TREE_TYPE (decl);
1907 /* For a CONST_DECL, set mode, alignment, and sizes from those of the
1908 type in case this node is used in a reference. */
1909 if (TREE_CODE (decl) == CONST_DECL)
1911 DECL_MODE (decl) = TYPE_MODE (type);
1912 DECL_ALIGN (decl) = TYPE_ALIGN (type);
1913 DECL_SIZE (decl) = TYPE_SIZE (type);
1914 DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type);
1915 return;
1918 /* Otherwise, only automatic variables need any expansion done. Static and
1919 external variables, and external functions, will be handled by
1920 `assemble_variable' (called from finish_decl). TYPE_DECL requires
1921 nothing. PARM_DECLs are handled in `assign_parms'. */
1922 if (TREE_CODE (decl) != VAR_DECL)
1923 return;
1925 if (TREE_STATIC (decl) || DECL_EXTERNAL (decl))
1926 return;
1928 /* Create the RTL representation for the variable. */
1930 if (type == error_mark_node)
1931 SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx));
1933 else if (DECL_SIZE (decl) == 0)
1935 /* Variable with incomplete type. */
1936 rtx x;
1937 if (DECL_INITIAL (decl) == 0)
1938 /* Error message was already done; now avoid a crash. */
1939 x = gen_rtx_MEM (BLKmode, const0_rtx);
1940 else
1941 /* An initializer is going to decide the size of this array.
1942 Until we know the size, represent its address with a reg. */
1943 x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode));
1945 set_mem_attributes (x, decl, 1);
1946 SET_DECL_RTL (decl, x);
1948 else if (use_register_for_decl (decl))
1950 /* Automatic variable that can go in a register. */
1951 enum machine_mode reg_mode = promote_decl_mode (decl, NULL);
1953 SET_DECL_RTL (decl, gen_reg_rtx (reg_mode));
1955 /* Note if the object is a user variable. */
1956 if (!DECL_ARTIFICIAL (decl))
1957 mark_user_reg (DECL_RTL (decl));
1959 if (POINTER_TYPE_P (type))
1960 mark_reg_pointer (DECL_RTL (decl),
1961 TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl))));
1964 else
1966 rtx oldaddr = 0;
1967 rtx addr;
1968 rtx x;
1970 /* Variable-sized decls are dealt with in the gimplifier. */
1971 gcc_assert (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST);
1973 /* If we previously made RTL for this decl, it must be an array
1974 whose size was determined by the initializer.
1975 The old address was a register; set that register now
1976 to the proper address. */
1977 if (DECL_RTL_SET_P (decl))
1979 gcc_assert (MEM_P (DECL_RTL (decl)));
1980 gcc_assert (REG_P (XEXP (DECL_RTL (decl), 0)));
1981 oldaddr = XEXP (DECL_RTL (decl), 0);
1984 /* Set alignment we actually gave this decl. */
1985 DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT
1986 : GET_MODE_BITSIZE (DECL_MODE (decl)));
1987 DECL_USER_ALIGN (decl) = 0;
1989 x = assign_temp (decl, 1, 1, 1);
1990 set_mem_attributes (x, decl, 1);
1991 SET_DECL_RTL (decl, x);
1993 if (oldaddr)
1995 addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr);
1996 if (addr != oldaddr)
1997 emit_move_insn (oldaddr, addr);
2002 /* Emit code to save the current value of stack. */
2004 expand_stack_save (void)
2006 rtx ret = NULL_RTX;
2008 do_pending_stack_adjust ();
2009 emit_stack_save (SAVE_BLOCK, &ret, NULL_RTX);
2010 return ret;
2013 /* Emit code to restore the current value of stack. */
2014 void
2015 expand_stack_restore (tree var)
2017 rtx sa = expand_normal (var);
2019 sa = convert_memory_address (Pmode, sa);
2020 emit_stack_restore (SAVE_BLOCK, sa, NULL_RTX);
2023 /* Do the insertion of a case label into case_list. The labels are
2024 fed to us in descending order from the sorted vector of case labels used
2025 in the tree part of the middle end. So the list we construct is
2026 sorted in ascending order. The bounds on the case range, LOW and HIGH,
2027 are converted to case's index type TYPE. */
2029 static struct case_node *
2030 add_case_node (struct case_node *head, tree type, tree low, tree high,
2031 tree label, alloc_pool case_node_pool)
2033 tree min_value, max_value;
2034 struct case_node *r;
2036 gcc_assert (TREE_CODE (low) == INTEGER_CST);
2037 gcc_assert (!high || TREE_CODE (high) == INTEGER_CST);
2039 min_value = TYPE_MIN_VALUE (type);
2040 max_value = TYPE_MAX_VALUE (type);
2042 /* If there's no HIGH value, then this is not a case range; it's
2043 just a simple case label. But that's just a degenerate case
2044 range.
2045 If the bounds are equal, turn this into the one-value case. */
2046 if (!high || tree_int_cst_equal (low, high))
2048 /* If the simple case value is unreachable, ignore it. */
2049 if ((TREE_CODE (min_value) == INTEGER_CST
2050 && tree_int_cst_compare (low, min_value) < 0)
2051 || (TREE_CODE (max_value) == INTEGER_CST
2052 && tree_int_cst_compare (low, max_value) > 0))
2053 return head;
2054 low = fold_convert (type, low);
2055 high = low;
2057 else
2059 /* If the entire case range is unreachable, ignore it. */
2060 if ((TREE_CODE (min_value) == INTEGER_CST
2061 && tree_int_cst_compare (high, min_value) < 0)
2062 || (TREE_CODE (max_value) == INTEGER_CST
2063 && tree_int_cst_compare (low, max_value) > 0))
2064 return head;
2066 /* If the lower bound is less than the index type's minimum
2067 value, truncate the range bounds. */
2068 if (TREE_CODE (min_value) == INTEGER_CST
2069 && tree_int_cst_compare (low, min_value) < 0)
2070 low = min_value;
2071 low = fold_convert (type, low);
2073 /* If the upper bound is greater than the index type's maximum
2074 value, truncate the range bounds. */
2075 if (TREE_CODE (max_value) == INTEGER_CST
2076 && tree_int_cst_compare (high, max_value) > 0)
2077 high = max_value;
2078 high = fold_convert (type, high);
2082 /* Add this label to the chain. Make sure to drop overflow flags. */
2083 r = (struct case_node *) pool_alloc (case_node_pool);
2084 r->low = build_int_cst_wide (TREE_TYPE (low), TREE_INT_CST_LOW (low),
2085 TREE_INT_CST_HIGH (low));
2086 r->high = build_int_cst_wide (TREE_TYPE (high), TREE_INT_CST_LOW (high),
2087 TREE_INT_CST_HIGH (high));
2088 r->code_label = label;
2089 r->parent = r->left = NULL;
2090 r->right = head;
2091 return r;
2094 /* Maximum number of case bit tests. */
2095 #define MAX_CASE_BIT_TESTS 3
2097 /* By default, enable case bit tests on targets with ashlsi3. */
2098 #ifndef CASE_USE_BIT_TESTS
2099 #define CASE_USE_BIT_TESTS (optab_handler (ashl_optab, word_mode) \
2100 != CODE_FOR_nothing)
2101 #endif
2104 /* A case_bit_test represents a set of case nodes that may be
2105 selected from using a bit-wise comparison. HI and LO hold
2106 the integer to be tested against, LABEL contains the label
2107 to jump to upon success and BITS counts the number of case
2108 nodes handled by this test, typically the number of bits
2109 set in HI:LO. */
2111 struct case_bit_test
2113 HOST_WIDE_INT hi;
2114 HOST_WIDE_INT lo;
2115 rtx label;
2116 int bits;
2119 /* Determine whether "1 << x" is relatively cheap in word_mode. */
2121 static
2122 bool lshift_cheap_p (void)
2124 static bool init[2] = {false, false};
2125 static bool cheap[2] = {true, true};
2127 bool speed_p = optimize_insn_for_speed_p ();
2129 if (!init[speed_p])
2131 rtx reg = gen_rtx_REG (word_mode, 10000);
2132 int cost = rtx_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg), SET,
2133 speed_p);
2134 cheap[speed_p] = cost < COSTS_N_INSNS (3);
2135 init[speed_p] = true;
2138 return cheap[speed_p];
2141 /* Comparison function for qsort to order bit tests by decreasing
2142 number of case nodes, i.e. the node with the most cases gets
2143 tested first. */
2145 static int
2146 case_bit_test_cmp (const void *p1, const void *p2)
2148 const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
2149 const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
2151 if (d2->bits != d1->bits)
2152 return d2->bits - d1->bits;
2154 /* Stabilize the sort. */
2155 return CODE_LABEL_NUMBER (d2->label) - CODE_LABEL_NUMBER (d1->label);
2158 /* Expand a switch statement by a short sequence of bit-wise
2159 comparisons. "switch(x)" is effectively converted into
2160 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
2161 integer constants.
2163 INDEX_EXPR is the value being switched on, which is of
2164 type INDEX_TYPE. MINVAL is the lowest case value of in
2165 the case nodes, of INDEX_TYPE type, and RANGE is highest
2166 value minus MINVAL, also of type INDEX_TYPE. NODES is
2167 the set of case nodes, and DEFAULT_LABEL is the label to
2168 branch to should none of the cases match.
2170 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
2171 node targets. */
2173 static void
2174 emit_case_bit_tests (tree index_type, tree index_expr, tree minval,
2175 tree range, case_node_ptr nodes, rtx default_label)
2177 struct case_bit_test test[MAX_CASE_BIT_TESTS];
2178 enum machine_mode mode;
2179 rtx expr, index, label;
2180 unsigned int i,j,lo,hi;
2181 struct case_node *n;
2182 unsigned int count;
2184 count = 0;
2185 for (n = nodes; n; n = n->right)
2187 label = label_rtx (n->code_label);
2188 for (i = 0; i < count; i++)
2189 if (label == test[i].label)
2190 break;
2192 if (i == count)
2194 gcc_assert (count < MAX_CASE_BIT_TESTS);
2195 test[i].hi = 0;
2196 test[i].lo = 0;
2197 test[i].label = label;
2198 test[i].bits = 1;
2199 count++;
2201 else
2202 test[i].bits++;
2204 lo = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2205 n->low, minval), 1);
2206 hi = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2207 n->high, minval), 1);
2208 for (j = lo; j <= hi; j++)
2209 if (j >= HOST_BITS_PER_WIDE_INT)
2210 test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT);
2211 else
2212 test[i].lo |= (HOST_WIDE_INT) 1 << j;
2215 qsort (test, count, sizeof(*test), case_bit_test_cmp);
2217 index_expr = fold_build2 (MINUS_EXPR, index_type,
2218 fold_convert (index_type, index_expr),
2219 fold_convert (index_type, minval));
2220 index = expand_normal (index_expr);
2221 do_pending_stack_adjust ();
2223 mode = TYPE_MODE (index_type);
2224 expr = expand_normal (range);
2225 if (default_label)
2226 emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
2227 default_label);
2229 index = convert_to_mode (word_mode, index, 0);
2230 index = expand_binop (word_mode, ashl_optab, const1_rtx,
2231 index, NULL_RTX, 1, OPTAB_WIDEN);
2233 for (i = 0; i < count; i++)
2235 expr = immed_double_const (test[i].lo, test[i].hi, word_mode);
2236 expr = expand_binop (word_mode, and_optab, index, expr,
2237 NULL_RTX, 1, OPTAB_WIDEN);
2238 emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX,
2239 word_mode, 1, test[i].label);
2242 if (default_label)
2243 emit_jump (default_label);
2246 #ifndef HAVE_casesi
2247 #define HAVE_casesi 0
2248 #endif
2250 #ifndef HAVE_tablejump
2251 #define HAVE_tablejump 0
2252 #endif
2254 /* Return true if a switch should be expanded as a bit test.
2255 INDEX_EXPR is the index expression, RANGE is the difference between
2256 highest and lowest case, UNIQ is number of unique case node targets
2257 not counting the default case and COUNT is the number of comparisons
2258 needed, not counting the default case. */
2259 bool
2260 expand_switch_using_bit_tests_p (tree index_expr, tree range,
2261 unsigned int uniq, unsigned int count)
2263 return (CASE_USE_BIT_TESTS
2264 && ! TREE_CONSTANT (index_expr)
2265 && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
2266 && compare_tree_int (range, 0) > 0
2267 && lshift_cheap_p ()
2268 && ((uniq == 1 && count >= 3)
2269 || (uniq == 2 && count >= 5)
2270 || (uniq == 3 && count >= 6)));
2273 /* Terminate a case (Pascal/Ada) or switch (C) statement
2274 in which ORIG_INDEX is the expression to be tested.
2275 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
2276 type as given in the source before any compiler conversions.
2277 Generate the code to test it and jump to the right place. */
2279 void
2280 expand_case (gimple stmt)
2282 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
2283 rtx default_label = 0;
2284 struct case_node *n;
2285 unsigned int count, uniq;
2286 rtx index;
2287 rtx table_label;
2288 int ncases;
2289 rtx *labelvec;
2290 int i;
2291 rtx before_case, end, lab;
2293 tree index_expr = gimple_switch_index (stmt);
2294 tree index_type = TREE_TYPE (index_expr);
2295 int unsignedp = TYPE_UNSIGNED (index_type);
2297 /* The insn after which the case dispatch should finally
2298 be emitted. Zero for a dummy. */
2299 rtx start;
2301 /* A list of case labels; it is first built as a list and it may then
2302 be rearranged into a nearly balanced binary tree. */
2303 struct case_node *case_list = 0;
2305 /* Label to jump to if no case matches. */
2306 tree default_label_decl = NULL_TREE;
2308 alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
2309 sizeof (struct case_node),
2310 100);
2312 do_pending_stack_adjust ();
2314 /* An ERROR_MARK occurs for various reasons including invalid data type. */
2315 if (index_type != error_mark_node)
2317 tree elt;
2318 bitmap label_bitmap;
2319 int stopi = 0;
2321 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
2322 expressions being INTEGER_CST. */
2323 gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
2325 /* The default case, if ever taken, is the first element. */
2326 elt = gimple_switch_label (stmt, 0);
2327 if (!CASE_LOW (elt) && !CASE_HIGH (elt))
2329 default_label_decl = CASE_LABEL (elt);
2330 stopi = 1;
2333 for (i = gimple_switch_num_labels (stmt) - 1; i >= stopi; --i)
2335 tree low, high;
2336 elt = gimple_switch_label (stmt, i);
2338 low = CASE_LOW (elt);
2339 gcc_assert (low);
2340 high = CASE_HIGH (elt);
2342 /* Discard empty ranges. */
2343 if (high && tree_int_cst_lt (high, low))
2344 continue;
2346 case_list = add_case_node (case_list, index_type, low, high,
2347 CASE_LABEL (elt), case_node_pool);
2351 before_case = start = get_last_insn ();
2352 if (default_label_decl)
2353 default_label = label_rtx (default_label_decl);
2355 /* Get upper and lower bounds of case values. */
2357 uniq = 0;
2358 count = 0;
2359 label_bitmap = BITMAP_ALLOC (NULL);
2360 for (n = case_list; n; n = n->right)
2362 /* Count the elements and track the largest and smallest
2363 of them (treating them as signed even if they are not). */
2364 if (count++ == 0)
2366 minval = n->low;
2367 maxval = n->high;
2369 else
2371 if (tree_int_cst_lt (n->low, minval))
2372 minval = n->low;
2373 if (tree_int_cst_lt (maxval, n->high))
2374 maxval = n->high;
2376 /* A range counts double, since it requires two compares. */
2377 if (! tree_int_cst_equal (n->low, n->high))
2378 count++;
2380 /* If we have not seen this label yet, then increase the
2381 number of unique case node targets seen. */
2382 lab = label_rtx (n->code_label);
2383 if (bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab)))
2384 uniq++;
2387 BITMAP_FREE (label_bitmap);
2389 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
2390 destination, such as one with a default case only. However,
2391 it doesn't remove cases that are out of range for the switch
2392 type, so we may still get a zero here. */
2393 if (count == 0)
2395 if (default_label)
2396 emit_jump (default_label);
2397 free_alloc_pool (case_node_pool);
2398 return;
2401 /* Compute span of values. */
2402 range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
2404 /* Try implementing this switch statement by a short sequence of
2405 bit-wise comparisons. However, we let the binary-tree case
2406 below handle constant index expressions. */
2407 if (expand_switch_using_bit_tests_p (index_expr, range, uniq, count))
2409 /* Optimize the case where all the case values fit in a
2410 word without having to subtract MINVAL. In this case,
2411 we can optimize away the subtraction. */
2412 if (compare_tree_int (minval, 0) > 0
2413 && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
2415 minval = build_int_cst (index_type, 0);
2416 range = maxval;
2418 emit_case_bit_tests (index_type, index_expr, minval, range,
2419 case_list, default_label);
2422 /* If range of values is much bigger than number of values,
2423 make a sequence of conditional branches instead of a dispatch.
2424 If the switch-index is a constant, do it this way
2425 because we can optimize it. */
2427 else if (count < targetm.case_values_threshold ()
2428 || compare_tree_int (range,
2429 (optimize_insn_for_size_p () ? 3 : 10) * count) > 0
2430 /* RANGE may be signed, and really large ranges will show up
2431 as negative numbers. */
2432 || compare_tree_int (range, 0) < 0
2433 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
2434 || flag_pic
2435 #endif
2436 || !flag_jump_tables
2437 || TREE_CONSTANT (index_expr)
2438 /* If neither casesi or tablejump is available, we can
2439 only go this way. */
2440 || (!HAVE_casesi && !HAVE_tablejump))
2442 index = expand_normal (index_expr);
2444 /* If the index is a short or char that we do not have
2445 an insn to handle comparisons directly, convert it to
2446 a full integer now, rather than letting each comparison
2447 generate the conversion. */
2449 if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
2450 && ! have_insn_for (COMPARE, GET_MODE (index)))
2452 enum machine_mode wider_mode;
2453 for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
2454 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2455 if (have_insn_for (COMPARE, wider_mode))
2457 index = convert_to_mode (wider_mode, index, unsignedp);
2458 break;
2462 do_pending_stack_adjust ();
2464 if (MEM_P (index))
2465 index = copy_to_reg (index);
2467 /* We generate a binary decision tree to select the
2468 appropriate target code. This is done as follows:
2470 The list of cases is rearranged into a binary tree,
2471 nearly optimal assuming equal probability for each case.
2473 The tree is transformed into RTL, eliminating
2474 redundant test conditions at the same time.
2476 If program flow could reach the end of the
2477 decision tree an unconditional jump to the
2478 default code is emitted. */
2480 use_cost_table = estimate_case_costs (case_list);
2481 balance_case_nodes (&case_list, NULL);
2482 emit_case_nodes (index, case_list, default_label, index_type);
2483 if (default_label)
2484 emit_jump (default_label);
2486 else
2488 rtx fallback_label = label_rtx (case_list->code_label);
2489 table_label = gen_label_rtx ();
2490 if (! try_casesi (index_type, index_expr, minval, range,
2491 table_label, default_label, fallback_label))
2493 bool ok;
2495 /* Index jumptables from zero for suitable values of
2496 minval to avoid a subtraction. */
2497 if (optimize_insn_for_speed_p ()
2498 && compare_tree_int (minval, 0) > 0
2499 && compare_tree_int (minval, 3) < 0)
2501 minval = build_int_cst (index_type, 0);
2502 range = maxval;
2505 ok = try_tablejump (index_type, index_expr, minval, range,
2506 table_label, default_label);
2507 gcc_assert (ok);
2510 /* Get table of labels to jump to, in order of case index. */
2512 ncases = tree_low_cst (range, 0) + 1;
2513 labelvec = XALLOCAVEC (rtx, ncases);
2514 memset (labelvec, 0, ncases * sizeof (rtx));
2516 for (n = case_list; n; n = n->right)
2518 /* Compute the low and high bounds relative to the minimum
2519 value since that should fit in a HOST_WIDE_INT while the
2520 actual values may not. */
2521 HOST_WIDE_INT i_low
2522 = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2523 n->low, minval), 1);
2524 HOST_WIDE_INT i_high
2525 = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2526 n->high, minval), 1);
2527 HOST_WIDE_INT i;
2529 for (i = i_low; i <= i_high; i ++)
2530 labelvec[i]
2531 = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
2534 /* Fill in the gaps with the default. We may have gaps at
2535 the beginning if we tried to avoid the minval subtraction,
2536 so substitute some label even if the default label was
2537 deemed unreachable. */
2538 if (!default_label)
2539 default_label = fallback_label;
2540 for (i = 0; i < ncases; i++)
2541 if (labelvec[i] == 0)
2542 labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
2544 /* Output the table. */
2545 emit_label (table_label);
2547 if (CASE_VECTOR_PC_RELATIVE || flag_pic)
2548 emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
2549 gen_rtx_LABEL_REF (Pmode, table_label),
2550 gen_rtvec_v (ncases, labelvec),
2551 const0_rtx, const0_rtx));
2552 else
2553 emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
2554 gen_rtvec_v (ncases, labelvec)));
2556 /* Record no drop-through after the table. */
2557 emit_barrier ();
2560 before_case = NEXT_INSN (before_case);
2561 end = get_last_insn ();
2562 reorder_insns (before_case, end, start);
2565 free_temp_slots ();
2566 free_alloc_pool (case_node_pool);
2569 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */
2571 static void
2572 do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label,
2573 int unsignedp)
2575 do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
2576 NULL_RTX, NULL_RTX, label, -1);
2579 /* Not all case values are encountered equally. This function
2580 uses a heuristic to weight case labels, in cases where that
2581 looks like a reasonable thing to do.
2583 Right now, all we try to guess is text, and we establish the
2584 following weights:
2586 chars above space: 16
2587 digits: 16
2588 default: 12
2589 space, punct: 8
2590 tab: 4
2591 newline: 2
2592 other "\" chars: 1
2593 remaining chars: 0
2595 If we find any cases in the switch that are not either -1 or in the range
2596 of valid ASCII characters, or are control characters other than those
2597 commonly used with "\", don't treat this switch scanning text.
2599 Return 1 if these nodes are suitable for cost estimation, otherwise
2600 return 0. */
2602 static int
2603 estimate_case_costs (case_node_ptr node)
2605 tree min_ascii = integer_minus_one_node;
2606 tree max_ascii = build_int_cst (TREE_TYPE (node->high), 127);
2607 case_node_ptr n;
2608 int i;
2610 /* If we haven't already made the cost table, make it now. Note that the
2611 lower bound of the table is -1, not zero. */
2613 if (! cost_table_initialized)
2615 cost_table_initialized = 1;
2617 for (i = 0; i < 128; i++)
2619 if (ISALNUM (i))
2620 COST_TABLE (i) = 16;
2621 else if (ISPUNCT (i))
2622 COST_TABLE (i) = 8;
2623 else if (ISCNTRL (i))
2624 COST_TABLE (i) = -1;
2627 COST_TABLE (' ') = 8;
2628 COST_TABLE ('\t') = 4;
2629 COST_TABLE ('\0') = 4;
2630 COST_TABLE ('\n') = 2;
2631 COST_TABLE ('\f') = 1;
2632 COST_TABLE ('\v') = 1;
2633 COST_TABLE ('\b') = 1;
2636 /* See if all the case expressions look like text. It is text if the
2637 constant is >= -1 and the highest constant is <= 127. Do all comparisons
2638 as signed arithmetic since we don't want to ever access cost_table with a
2639 value less than -1. Also check that none of the constants in a range
2640 are strange control characters. */
2642 for (n = node; n; n = n->right)
2644 if (tree_int_cst_lt (n->low, min_ascii)
2645 || tree_int_cst_lt (max_ascii, n->high))
2646 return 0;
2648 for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low);
2649 i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++)
2650 if (COST_TABLE (i) < 0)
2651 return 0;
2654 /* All interesting values are within the range of interesting
2655 ASCII characters. */
2656 return 1;
2659 /* Take an ordered list of case nodes
2660 and transform them into a near optimal binary tree,
2661 on the assumption that any target code selection value is as
2662 likely as any other.
2664 The transformation is performed by splitting the ordered
2665 list into two equal sections plus a pivot. The parts are
2666 then attached to the pivot as left and right branches. Each
2667 branch is then transformed recursively. */
2669 static void
2670 balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
2672 case_node_ptr np;
2674 np = *head;
2675 if (np)
2677 int cost = 0;
2678 int i = 0;
2679 int ranges = 0;
2680 case_node_ptr *npp;
2681 case_node_ptr left;
2683 /* Count the number of entries on branch. Also count the ranges. */
2685 while (np)
2687 if (!tree_int_cst_equal (np->low, np->high))
2689 ranges++;
2690 if (use_cost_table)
2691 cost += COST_TABLE (TREE_INT_CST_LOW (np->high));
2694 if (use_cost_table)
2695 cost += COST_TABLE (TREE_INT_CST_LOW (np->low));
2697 i++;
2698 np = np->right;
2701 if (i > 2)
2703 /* Split this list if it is long enough for that to help. */
2704 npp = head;
2705 left = *npp;
2706 if (use_cost_table)
2708 /* Find the place in the list that bisects the list's total cost,
2709 Here I gets half the total cost. */
2710 int n_moved = 0;
2711 i = (cost + 1) / 2;
2712 while (1)
2714 /* Skip nodes while their cost does not reach that amount. */
2715 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
2716 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high));
2717 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low));
2718 if (i <= 0)
2719 break;
2720 npp = &(*npp)->right;
2721 n_moved += 1;
2723 if (n_moved == 0)
2725 /* Leave this branch lopsided, but optimize left-hand
2726 side and fill in `parent' fields for right-hand side. */
2727 np = *head;
2728 np->parent = parent;
2729 balance_case_nodes (&np->left, np);
2730 for (; np->right; np = np->right)
2731 np->right->parent = np;
2732 return;
2735 /* If there are just three nodes, split at the middle one. */
2736 else if (i == 3)
2737 npp = &(*npp)->right;
2738 else
2740 /* Find the place in the list that bisects the list's total cost,
2741 where ranges count as 2.
2742 Here I gets half the total cost. */
2743 i = (i + ranges + 1) / 2;
2744 while (1)
2746 /* Skip nodes while their cost does not reach that amount. */
2747 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
2748 i--;
2749 i--;
2750 if (i <= 0)
2751 break;
2752 npp = &(*npp)->right;
2755 *head = np = *npp;
2756 *npp = 0;
2757 np->parent = parent;
2758 np->left = left;
2760 /* Optimize each of the two split parts. */
2761 balance_case_nodes (&np->left, np);
2762 balance_case_nodes (&np->right, np);
2764 else
2766 /* Else leave this branch as one level,
2767 but fill in `parent' fields. */
2768 np = *head;
2769 np->parent = parent;
2770 for (; np->right; np = np->right)
2771 np->right->parent = np;
2776 /* Search the parent sections of the case node tree
2777 to see if a test for the lower bound of NODE would be redundant.
2778 INDEX_TYPE is the type of the index expression.
2780 The instructions to generate the case decision tree are
2781 output in the same order as nodes are processed so it is
2782 known that if a parent node checks the range of the current
2783 node minus one that the current node is bounded at its lower
2784 span. Thus the test would be redundant. */
2786 static int
2787 node_has_low_bound (case_node_ptr node, tree index_type)
2789 tree low_minus_one;
2790 case_node_ptr pnode;
2792 /* If the lower bound of this node is the lowest value in the index type,
2793 we need not test it. */
2795 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
2796 return 1;
2798 /* If this node has a left branch, the value at the left must be less
2799 than that at this node, so it cannot be bounded at the bottom and
2800 we need not bother testing any further. */
2802 if (node->left)
2803 return 0;
2805 low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low),
2806 node->low,
2807 build_int_cst (TREE_TYPE (node->low), 1));
2809 /* If the subtraction above overflowed, we can't verify anything.
2810 Otherwise, look for a parent that tests our value - 1. */
2812 if (! tree_int_cst_lt (low_minus_one, node->low))
2813 return 0;
2815 for (pnode = node->parent; pnode; pnode = pnode->parent)
2816 if (tree_int_cst_equal (low_minus_one, pnode->high))
2817 return 1;
2819 return 0;
2822 /* Search the parent sections of the case node tree
2823 to see if a test for the upper bound of NODE would be redundant.
2824 INDEX_TYPE is the type of the index expression.
2826 The instructions to generate the case decision tree are
2827 output in the same order as nodes are processed so it is
2828 known that if a parent node checks the range of the current
2829 node plus one that the current node is bounded at its upper
2830 span. Thus the test would be redundant. */
2832 static int
2833 node_has_high_bound (case_node_ptr node, tree index_type)
2835 tree high_plus_one;
2836 case_node_ptr pnode;
2838 /* If there is no upper bound, obviously no test is needed. */
2840 if (TYPE_MAX_VALUE (index_type) == NULL)
2841 return 1;
2843 /* If the upper bound of this node is the highest value in the type
2844 of the index expression, we need not test against it. */
2846 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
2847 return 1;
2849 /* If this node has a right branch, the value at the right must be greater
2850 than that at this node, so it cannot be bounded at the top and
2851 we need not bother testing any further. */
2853 if (node->right)
2854 return 0;
2856 high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high),
2857 node->high,
2858 build_int_cst (TREE_TYPE (node->high), 1));
2860 /* If the addition above overflowed, we can't verify anything.
2861 Otherwise, look for a parent that tests our value + 1. */
2863 if (! tree_int_cst_lt (node->high, high_plus_one))
2864 return 0;
2866 for (pnode = node->parent; pnode; pnode = pnode->parent)
2867 if (tree_int_cst_equal (high_plus_one, pnode->low))
2868 return 1;
2870 return 0;
2873 /* Search the parent sections of the
2874 case node tree to see if both tests for the upper and lower
2875 bounds of NODE would be redundant. */
2877 static int
2878 node_is_bounded (case_node_ptr node, tree index_type)
2880 return (node_has_low_bound (node, index_type)
2881 && node_has_high_bound (node, index_type));
2884 /* Emit step-by-step code to select a case for the value of INDEX.
2885 The thus generated decision tree follows the form of the
2886 case-node binary tree NODE, whose nodes represent test conditions.
2887 INDEX_TYPE is the type of the index of the switch.
2889 Care is taken to prune redundant tests from the decision tree
2890 by detecting any boundary conditions already checked by
2891 emitted rtx. (See node_has_high_bound, node_has_low_bound
2892 and node_is_bounded, above.)
2894 Where the test conditions can be shown to be redundant we emit
2895 an unconditional jump to the target code. As a further
2896 optimization, the subordinates of a tree node are examined to
2897 check for bounded nodes. In this case conditional and/or
2898 unconditional jumps as a result of the boundary check for the
2899 current node are arranged to target the subordinates associated
2900 code for out of bound conditions on the current node.
2902 We can assume that when control reaches the code generated here,
2903 the index value has already been compared with the parents
2904 of this node, and determined to be on the same side of each parent
2905 as this node is. Thus, if this node tests for the value 51,
2906 and a parent tested for 52, we don't need to consider
2907 the possibility of a value greater than 51. If another parent
2908 tests for the value 50, then this node need not test anything. */
2910 static void
2911 emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
2912 tree index_type)
2914 /* If INDEX has an unsigned type, we must make unsigned branches. */
2915 int unsignedp = TYPE_UNSIGNED (index_type);
2916 enum machine_mode mode = GET_MODE (index);
2917 enum machine_mode imode = TYPE_MODE (index_type);
2919 /* Handle indices detected as constant during RTL expansion. */
2920 if (mode == VOIDmode)
2921 mode = imode;
2923 /* See if our parents have already tested everything for us.
2924 If they have, emit an unconditional jump for this node. */
2925 if (node_is_bounded (node, index_type))
2926 emit_jump (label_rtx (node->code_label));
2928 else if (tree_int_cst_equal (node->low, node->high))
2930 /* Node is single valued. First see if the index expression matches
2931 this node and then check our children, if any. */
2933 do_jump_if_equal (mode, index,
2934 convert_modes (mode, imode,
2935 expand_normal (node->low),
2936 unsignedp),
2937 label_rtx (node->code_label), unsignedp);
2939 if (node->right != 0 && node->left != 0)
2941 /* This node has children on both sides.
2942 Dispatch to one side or the other
2943 by comparing the index value with this node's value.
2944 If one subtree is bounded, check that one first,
2945 so we can avoid real branches in the tree. */
2947 if (node_is_bounded (node->right, index_type))
2949 emit_cmp_and_jump_insns (index,
2950 convert_modes
2951 (mode, imode,
2952 expand_normal (node->high),
2953 unsignedp),
2954 GT, NULL_RTX, mode, unsignedp,
2955 label_rtx (node->right->code_label));
2956 emit_case_nodes (index, node->left, default_label, index_type);
2959 else if (node_is_bounded (node->left, index_type))
2961 emit_cmp_and_jump_insns (index,
2962 convert_modes
2963 (mode, imode,
2964 expand_normal (node->high),
2965 unsignedp),
2966 LT, NULL_RTX, mode, unsignedp,
2967 label_rtx (node->left->code_label));
2968 emit_case_nodes (index, node->right, default_label, index_type);
2971 /* If both children are single-valued cases with no
2972 children, finish up all the work. This way, we can save
2973 one ordered comparison. */
2974 else if (tree_int_cst_equal (node->right->low, node->right->high)
2975 && node->right->left == 0
2976 && node->right->right == 0
2977 && tree_int_cst_equal (node->left->low, node->left->high)
2978 && node->left->left == 0
2979 && node->left->right == 0)
2981 /* Neither node is bounded. First distinguish the two sides;
2982 then emit the code for one side at a time. */
2984 /* See if the value matches what the right hand side
2985 wants. */
2986 do_jump_if_equal (mode, index,
2987 convert_modes (mode, imode,
2988 expand_normal (node->right->low),
2989 unsignedp),
2990 label_rtx (node->right->code_label),
2991 unsignedp);
2993 /* See if the value matches what the left hand side
2994 wants. */
2995 do_jump_if_equal (mode, index,
2996 convert_modes (mode, imode,
2997 expand_normal (node->left->low),
2998 unsignedp),
2999 label_rtx (node->left->code_label),
3000 unsignedp);
3003 else
3005 /* Neither node is bounded. First distinguish the two sides;
3006 then emit the code for one side at a time. */
3008 tree test_label
3009 = build_decl (CURR_INSN_LOCATION,
3010 LABEL_DECL, NULL_TREE, NULL_TREE);
3012 /* See if the value is on the right. */
3013 emit_cmp_and_jump_insns (index,
3014 convert_modes
3015 (mode, imode,
3016 expand_normal (node->high),
3017 unsignedp),
3018 GT, NULL_RTX, mode, unsignedp,
3019 label_rtx (test_label));
3021 /* Value must be on the left.
3022 Handle the left-hand subtree. */
3023 emit_case_nodes (index, node->left, default_label, index_type);
3024 /* If left-hand subtree does nothing,
3025 go to default. */
3026 if (default_label)
3027 emit_jump (default_label);
3029 /* Code branches here for the right-hand subtree. */
3030 expand_label (test_label);
3031 emit_case_nodes (index, node->right, default_label, index_type);
3035 else if (node->right != 0 && node->left == 0)
3037 /* Here we have a right child but no left so we issue a conditional
3038 branch to default and process the right child.
3040 Omit the conditional branch to default if the right child
3041 does not have any children and is single valued; it would
3042 cost too much space to save so little time. */
3044 if (node->right->right || node->right->left
3045 || !tree_int_cst_equal (node->right->low, node->right->high))
3047 if (!node_has_low_bound (node, index_type))
3049 emit_cmp_and_jump_insns (index,
3050 convert_modes
3051 (mode, imode,
3052 expand_normal (node->high),
3053 unsignedp),
3054 LT, NULL_RTX, mode, unsignedp,
3055 default_label);
3058 emit_case_nodes (index, node->right, default_label, index_type);
3060 else
3061 /* We cannot process node->right normally
3062 since we haven't ruled out the numbers less than
3063 this node's value. So handle node->right explicitly. */
3064 do_jump_if_equal (mode, index,
3065 convert_modes
3066 (mode, imode,
3067 expand_normal (node->right->low),
3068 unsignedp),
3069 label_rtx (node->right->code_label), unsignedp);
3072 else if (node->right == 0 && node->left != 0)
3074 /* Just one subtree, on the left. */
3075 if (node->left->left || node->left->right
3076 || !tree_int_cst_equal (node->left->low, node->left->high))
3078 if (!node_has_high_bound (node, index_type))
3080 emit_cmp_and_jump_insns (index,
3081 convert_modes
3082 (mode, imode,
3083 expand_normal (node->high),
3084 unsignedp),
3085 GT, NULL_RTX, mode, unsignedp,
3086 default_label);
3089 emit_case_nodes (index, node->left, default_label, index_type);
3091 else
3092 /* We cannot process node->left normally
3093 since we haven't ruled out the numbers less than
3094 this node's value. So handle node->left explicitly. */
3095 do_jump_if_equal (mode, index,
3096 convert_modes
3097 (mode, imode,
3098 expand_normal (node->left->low),
3099 unsignedp),
3100 label_rtx (node->left->code_label), unsignedp);
3103 else
3105 /* Node is a range. These cases are very similar to those for a single
3106 value, except that we do not start by testing whether this node
3107 is the one to branch to. */
3109 if (node->right != 0 && node->left != 0)
3111 /* Node has subtrees on both sides.
3112 If the right-hand subtree is bounded,
3113 test for it first, since we can go straight there.
3114 Otherwise, we need to make a branch in the control structure,
3115 then handle the two subtrees. */
3116 tree test_label = 0;
3118 if (node_is_bounded (node->right, index_type))
3119 /* Right hand node is fully bounded so we can eliminate any
3120 testing and branch directly to the target code. */
3121 emit_cmp_and_jump_insns (index,
3122 convert_modes
3123 (mode, imode,
3124 expand_normal (node->high),
3125 unsignedp),
3126 GT, NULL_RTX, mode, unsignedp,
3127 label_rtx (node->right->code_label));
3128 else
3130 /* Right hand node requires testing.
3131 Branch to a label where we will handle it later. */
3133 test_label = build_decl (CURR_INSN_LOCATION,
3134 LABEL_DECL, NULL_TREE, NULL_TREE);
3135 emit_cmp_and_jump_insns (index,
3136 convert_modes
3137 (mode, imode,
3138 expand_normal (node->high),
3139 unsignedp),
3140 GT, NULL_RTX, mode, unsignedp,
3141 label_rtx (test_label));
3144 /* Value belongs to this node or to the left-hand subtree. */
3146 emit_cmp_and_jump_insns (index,
3147 convert_modes
3148 (mode, imode,
3149 expand_normal (node->low),
3150 unsignedp),
3151 GE, NULL_RTX, mode, unsignedp,
3152 label_rtx (node->code_label));
3154 /* Handle the left-hand subtree. */
3155 emit_case_nodes (index, node->left, default_label, index_type);
3157 /* If right node had to be handled later, do that now. */
3159 if (test_label)
3161 /* If the left-hand subtree fell through,
3162 don't let it fall into the right-hand subtree. */
3163 if (default_label)
3164 emit_jump (default_label);
3166 expand_label (test_label);
3167 emit_case_nodes (index, node->right, default_label, index_type);
3171 else if (node->right != 0 && node->left == 0)
3173 /* Deal with values to the left of this node,
3174 if they are possible. */
3175 if (!node_has_low_bound (node, index_type))
3177 emit_cmp_and_jump_insns (index,
3178 convert_modes
3179 (mode, imode,
3180 expand_normal (node->low),
3181 unsignedp),
3182 LT, NULL_RTX, mode, unsignedp,
3183 default_label);
3186 /* Value belongs to this node or to the right-hand subtree. */
3188 emit_cmp_and_jump_insns (index,
3189 convert_modes
3190 (mode, imode,
3191 expand_normal (node->high),
3192 unsignedp),
3193 LE, NULL_RTX, mode, unsignedp,
3194 label_rtx (node->code_label));
3196 emit_case_nodes (index, node->right, default_label, index_type);
3199 else if (node->right == 0 && node->left != 0)
3201 /* Deal with values to the right of this node,
3202 if they are possible. */
3203 if (!node_has_high_bound (node, index_type))
3205 emit_cmp_and_jump_insns (index,
3206 convert_modes
3207 (mode, imode,
3208 expand_normal (node->high),
3209 unsignedp),
3210 GT, NULL_RTX, mode, unsignedp,
3211 default_label);
3214 /* Value belongs to this node or to the left-hand subtree. */
3216 emit_cmp_and_jump_insns (index,
3217 convert_modes
3218 (mode, imode,
3219 expand_normal (node->low),
3220 unsignedp),
3221 GE, NULL_RTX, mode, unsignedp,
3222 label_rtx (node->code_label));
3224 emit_case_nodes (index, node->left, default_label, index_type);
3227 else
3229 /* Node has no children so we check low and high bounds to remove
3230 redundant tests. Only one of the bounds can exist,
3231 since otherwise this node is bounded--a case tested already. */
3232 int high_bound = node_has_high_bound (node, index_type);
3233 int low_bound = node_has_low_bound (node, index_type);
3235 if (!high_bound && low_bound)
3237 emit_cmp_and_jump_insns (index,
3238 convert_modes
3239 (mode, imode,
3240 expand_normal (node->high),
3241 unsignedp),
3242 GT, NULL_RTX, mode, unsignedp,
3243 default_label);
3246 else if (!low_bound && high_bound)
3248 emit_cmp_and_jump_insns (index,
3249 convert_modes
3250 (mode, imode,
3251 expand_normal (node->low),
3252 unsignedp),
3253 LT, NULL_RTX, mode, unsignedp,
3254 default_label);
3256 else if (!low_bound && !high_bound)
3258 /* Widen LOW and HIGH to the same width as INDEX. */
3259 tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
3260 tree low = build1 (CONVERT_EXPR, type, node->low);
3261 tree high = build1 (CONVERT_EXPR, type, node->high);
3262 rtx low_rtx, new_index, new_bound;
3264 /* Instead of doing two branches, emit one unsigned branch for
3265 (index-low) > (high-low). */
3266 low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL);
3267 new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
3268 NULL_RTX, unsignedp,
3269 OPTAB_WIDEN);
3270 new_bound = expand_expr (fold_build2 (MINUS_EXPR, type,
3271 high, low),
3272 NULL_RTX, mode, EXPAND_NORMAL);
3274 emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
3275 mode, 1, default_label);
3278 emit_jump (label_rtx (node->code_label));