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
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
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. */
29 #include "coretypes.h"
33 #include "hard-reg-set.h"
39 #include "insn-config.h"
44 #include "diagnostic-core.h"
47 #include "langhooks.h"
53 #include "alloc-pool.h"
54 #include "pretty-print.h"
57 #include "tree-flow.h"
60 /* Functions and data structures for expanding case statements. */
62 /* Case label structure, used to hold info on labels within case
63 statements. We handle "range" labels; for a single-value label
64 as in C, the high and low limits are the same.
66 We start with a vector of case nodes sorted in ascending order, and
67 the default label as the last element in the vector. Before expanding
68 to RTL, we transform this vector into a list linked via the RIGHT
69 fields in the case_node struct. Nodes with higher case values are
72 Switch statements can be output in three forms. A branch table is
73 used if there are more than a few labels and the labels are dense
74 within the range between the smallest and largest case value. If a
75 branch table is used, no further manipulations are done with the case
78 The alternative to the use of a branch table is to generate a series
79 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
80 and PARENT fields to hold a binary tree. Initially the tree is
81 totally unbalanced, with everything on the right. We balance the tree
82 with nodes on the left having lower case values than the parent
83 and nodes on the right having higher values. We then output the tree
86 For very small, suitable switch statements, we can generate a series
87 of simple bit test and branches instead. */
91 struct case_node
*left
; /* Left son in binary tree */
92 struct case_node
*right
; /* Right son in binary tree; also node chain */
93 struct case_node
*parent
; /* Parent of node in binary tree */
94 tree low
; /* Lowest index value for this label */
95 tree high
; /* Highest index value for this label */
96 tree code_label
; /* Label to jump to when node matches */
97 gcov_type subtree_count
, count
; /* Execution counts */
100 typedef struct case_node case_node
;
101 typedef struct case_node
*case_node_ptr
;
103 /* These are used by estimate_case_costs and balance_case_nodes. */
105 /* This must be a signed type, and non-ANSI compilers lack signed char. */
106 static short cost_table_
[129];
107 static int use_cost_table
;
108 static int cost_table_initialized
;
110 /* Special care is needed because we allow -1, but TREE_INT_CST_LOW
112 #define COST_TABLE(I) cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)]
114 static int n_occurrences (int, const char *);
115 static bool tree_conflicts_with_clobbers_p (tree
, HARD_REG_SET
*);
116 static void expand_nl_goto_receiver (void);
117 static bool check_operand_nalternatives (tree
, tree
);
118 static bool check_unique_operand_names (tree
, tree
, tree
);
119 static char *resolve_operand_name_1 (char *, tree
, tree
, tree
);
120 static void expand_null_return_1 (void);
121 static void expand_value_return (rtx
);
122 static int estimate_case_costs (case_node_ptr
);
123 static bool lshift_cheap_p (void);
124 static int case_bit_test_cmp (const void *, const void *);
125 static void emit_case_bit_tests (tree
, tree
, tree
, tree
, case_node_ptr
, rtx
);
126 static void balance_case_nodes (case_node_ptr
*, case_node_ptr
);
127 static int node_has_low_bound (case_node_ptr
, tree
);
128 static int node_has_high_bound (case_node_ptr
, tree
);
129 static int node_is_bounded (case_node_ptr
, tree
);
130 static void emit_case_nodes (rtx
, case_node_ptr
, rtx
, int, tree
);
131 static struct case_node
*add_case_node (struct case_node
*, tree
,
132 tree
, tree
, tree
, gcov_type
,
136 /* Return the rtx-label that corresponds to a LABEL_DECL,
137 creating it if necessary. */
140 label_rtx (tree label
)
142 gcc_assert (TREE_CODE (label
) == LABEL_DECL
);
144 if (!DECL_RTL_SET_P (label
))
146 rtx r
= gen_label_rtx ();
147 SET_DECL_RTL (label
, r
);
148 if (FORCED_LABEL (label
) || DECL_NONLOCAL (label
))
149 LABEL_PRESERVE_P (r
) = 1;
152 return DECL_RTL (label
);
155 /* As above, but also put it on the forced-reference list of the
156 function that contains it. */
158 force_label_rtx (tree label
)
160 rtx ref
= label_rtx (label
);
161 tree function
= decl_function_context (label
);
163 gcc_assert (function
);
165 forced_labels
= gen_rtx_EXPR_LIST (VOIDmode
, ref
, forced_labels
);
169 /* Add an unconditional jump to LABEL as the next sequential instruction. */
172 emit_jump (rtx label
)
174 do_pending_stack_adjust ();
175 emit_jump_insn (gen_jump (label
));
179 /* Emit code to jump to the address
180 specified by the pointer expression EXP. */
183 expand_computed_goto (tree exp
)
185 rtx x
= expand_normal (exp
);
187 x
= convert_memory_address (Pmode
, x
);
189 do_pending_stack_adjust ();
190 emit_indirect_jump (x
);
193 /* Handle goto statements and the labels that they can go to. */
195 /* Specify the location in the RTL code of a label LABEL,
196 which is a LABEL_DECL tree node.
198 This is used for the kind of label that the user can jump to with a
199 goto statement, and for alternatives of a switch or case statement.
200 RTL labels generated for loops and conditionals don't go through here;
201 they are generated directly at the RTL level, by other functions below.
203 Note that this has nothing to do with defining label *names*.
204 Languages vary in how they do that and what that even means. */
207 expand_label (tree label
)
209 rtx label_r
= label_rtx (label
);
211 do_pending_stack_adjust ();
212 emit_label (label_r
);
213 if (DECL_NAME (label
))
214 LABEL_NAME (DECL_RTL (label
)) = IDENTIFIER_POINTER (DECL_NAME (label
));
216 if (DECL_NONLOCAL (label
))
218 expand_nl_goto_receiver ();
219 nonlocal_goto_handler_labels
220 = gen_rtx_EXPR_LIST (VOIDmode
, label_r
,
221 nonlocal_goto_handler_labels
);
224 if (FORCED_LABEL (label
))
225 forced_labels
= gen_rtx_EXPR_LIST (VOIDmode
, label_r
, forced_labels
);
227 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
228 maybe_set_first_label_num (label_r
);
231 /* Generate RTL code for a `goto' statement with target label LABEL.
232 LABEL should be a LABEL_DECL tree node that was or will later be
233 defined with `expand_label'. */
236 expand_goto (tree label
)
238 #ifdef ENABLE_CHECKING
239 /* Check for a nonlocal goto to a containing function. Should have
240 gotten translated to __builtin_nonlocal_goto. */
241 tree context
= decl_function_context (label
);
242 gcc_assert (!context
|| context
== current_function_decl
);
245 emit_jump (label_rtx (label
));
248 /* Return the number of times character C occurs in string S. */
250 n_occurrences (int c
, const char *s
)
258 /* Generate RTL for an asm statement (explicit assembler code).
259 STRING is a STRING_CST node containing the assembler code text,
260 or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the
261 insn is volatile; don't optimize it. */
264 expand_asm_loc (tree string
, int vol
, location_t locus
)
268 if (TREE_CODE (string
) == ADDR_EXPR
)
269 string
= TREE_OPERAND (string
, 0);
271 body
= gen_rtx_ASM_INPUT_loc (VOIDmode
,
272 ggc_strdup (TREE_STRING_POINTER (string
)),
275 MEM_VOLATILE_P (body
) = vol
;
280 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
281 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
282 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
283 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
284 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
285 constraint allows the use of a register operand. And, *IS_INOUT
286 will be true if the operand is read-write, i.e., if it is used as
287 an input as well as an output. If *CONSTRAINT_P is not in
288 canonical form, it will be made canonical. (Note that `+' will be
289 replaced with `=' as part of this process.)
291 Returns TRUE if all went well; FALSE if an error occurred. */
294 parse_output_constraint (const char **constraint_p
, int operand_num
,
295 int ninputs
, int noutputs
, bool *allows_mem
,
296 bool *allows_reg
, bool *is_inout
)
298 const char *constraint
= *constraint_p
;
301 /* Assume the constraint doesn't allow the use of either a register
306 /* Allow the `=' or `+' to not be at the beginning of the string,
307 since it wasn't explicitly documented that way, and there is a
308 large body of code that puts it last. Swap the character to
309 the front, so as not to uglify any place else. */
310 p
= strchr (constraint
, '=');
312 p
= strchr (constraint
, '+');
314 /* If the string doesn't contain an `=', issue an error
318 error ("output operand constraint lacks %<=%>");
322 /* If the constraint begins with `+', then the operand is both read
323 from and written to. */
324 *is_inout
= (*p
== '+');
326 /* Canonicalize the output constraint so that it begins with `='. */
327 if (p
!= constraint
|| *is_inout
)
330 size_t c_len
= strlen (constraint
);
333 warning (0, "output constraint %qc for operand %d "
334 "is not at the beginning",
337 /* Make a copy of the constraint. */
338 buf
= XALLOCAVEC (char, c_len
+ 1);
339 strcpy (buf
, constraint
);
340 /* Swap the first character and the `=' or `+'. */
341 buf
[p
- constraint
] = buf
[0];
342 /* Make sure the first character is an `='. (Until we do this,
343 it might be a `+'.) */
345 /* Replace the constraint with the canonicalized string. */
346 *constraint_p
= ggc_alloc_string (buf
, c_len
);
347 constraint
= *constraint_p
;
350 /* Loop through the constraint string. */
351 for (p
= constraint
+ 1; *p
; p
+= CONSTRAINT_LEN (*p
, p
))
356 error ("operand constraint contains incorrectly positioned "
361 if (operand_num
+ 1 == ninputs
+ noutputs
)
363 error ("%<%%%> constraint used with last operand");
368 case 'V': case TARGET_MEM_CONSTRAINT
: case 'o':
372 case '?': case '!': case '*': case '&': case '#':
373 case 'E': case 'F': case 'G': case 'H':
374 case 's': case 'i': case 'n':
375 case 'I': case 'J': case 'K': case 'L': case 'M':
376 case 'N': case 'O': case 'P': case ',':
379 case '0': case '1': case '2': case '3': case '4':
380 case '5': case '6': case '7': case '8': case '9':
382 error ("matching constraint not valid in output operand");
386 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
387 excepting those that expand_call created. So match memory
404 if (REG_CLASS_FROM_CONSTRAINT (*p
, p
) != NO_REGS
)
406 #ifdef EXTRA_CONSTRAINT_STR
407 else if (EXTRA_ADDRESS_CONSTRAINT (*p
, p
))
409 else if (EXTRA_MEMORY_CONSTRAINT (*p
, p
))
413 /* Otherwise we can't assume anything about the nature of
414 the constraint except that it isn't purely registers.
415 Treat it like "g" and hope for the best. */
426 /* Similar, but for input constraints. */
429 parse_input_constraint (const char **constraint_p
, int input_num
,
430 int ninputs
, int noutputs
, int ninout
,
431 const char * const * constraints
,
432 bool *allows_mem
, bool *allows_reg
)
434 const char *constraint
= *constraint_p
;
435 const char *orig_constraint
= constraint
;
436 size_t c_len
= strlen (constraint
);
438 bool saw_match
= false;
440 /* Assume the constraint doesn't allow the use of either
441 a register or memory. */
445 /* Make sure constraint has neither `=', `+', nor '&'. */
447 for (j
= 0; j
< c_len
; j
+= CONSTRAINT_LEN (constraint
[j
], constraint
+j
))
448 switch (constraint
[j
])
450 case '+': case '=': case '&':
451 if (constraint
== orig_constraint
)
453 error ("input operand constraint contains %qc", constraint
[j
]);
459 if (constraint
== orig_constraint
460 && input_num
+ 1 == ninputs
- ninout
)
462 error ("%<%%%> constraint used with last operand");
467 case 'V': case TARGET_MEM_CONSTRAINT
: case 'o':
472 case '?': case '!': case '*': case '#':
473 case 'E': case 'F': case 'G': case 'H':
474 case 's': case 'i': case 'n':
475 case 'I': case 'J': case 'K': case 'L': case 'M':
476 case 'N': case 'O': case 'P': case ',':
479 /* Whether or not a numeric constraint allows a register is
480 decided by the matching constraint, and so there is no need
481 to do anything special with them. We must handle them in
482 the default case, so that we don't unnecessarily force
483 operands to memory. */
484 case '0': case '1': case '2': case '3': case '4':
485 case '5': case '6': case '7': case '8': case '9':
492 match
= strtoul (constraint
+ j
, &end
, 10);
493 if (match
>= (unsigned long) noutputs
)
495 error ("matching constraint references invalid operand number");
499 /* Try and find the real constraint for this dup. Only do this
500 if the matching constraint is the only alternative. */
502 && (j
== 0 || (j
== 1 && constraint
[0] == '%')))
504 constraint
= constraints
[match
];
505 *constraint_p
= constraint
;
506 c_len
= strlen (constraint
);
508 /* ??? At the end of the loop, we will skip the first part of
509 the matched constraint. This assumes not only that the
510 other constraint is an output constraint, but also that
511 the '=' or '+' come first. */
515 j
= end
- constraint
;
516 /* Anticipate increment at end of loop. */
531 if (! ISALPHA (constraint
[j
]))
533 error ("invalid punctuation %qc in constraint", constraint
[j
]);
536 if (REG_CLASS_FROM_CONSTRAINT (constraint
[j
], constraint
+ j
)
539 #ifdef EXTRA_CONSTRAINT_STR
540 else if (EXTRA_ADDRESS_CONSTRAINT (constraint
[j
], constraint
+ j
))
542 else if (EXTRA_MEMORY_CONSTRAINT (constraint
[j
], constraint
+ j
))
546 /* Otherwise we can't assume anything about the nature of
547 the constraint except that it isn't purely registers.
548 Treat it like "g" and hope for the best. */
556 if (saw_match
&& !*allows_reg
)
557 warning (0, "matching constraint does not allow a register");
562 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
563 can be an asm-declared register. Called via walk_tree. */
566 decl_overlaps_hard_reg_set_p (tree
*declp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
570 const HARD_REG_SET
*const regs
= (const HARD_REG_SET
*) data
;
572 if (TREE_CODE (decl
) == VAR_DECL
)
574 if (DECL_HARD_REGISTER (decl
)
575 && REG_P (DECL_RTL (decl
))
576 && REGNO (DECL_RTL (decl
)) < FIRST_PSEUDO_REGISTER
)
578 rtx reg
= DECL_RTL (decl
);
580 if (overlaps_hard_reg_set_p (*regs
, GET_MODE (reg
), REGNO (reg
)))
585 else if (TYPE_P (decl
) || TREE_CODE (decl
) == PARM_DECL
)
590 /* If there is an overlap between *REGS and DECL, return the first overlap
593 tree_overlaps_hard_reg_set (tree decl
, HARD_REG_SET
*regs
)
595 return walk_tree (&decl
, decl_overlaps_hard_reg_set_p
, regs
, NULL
);
598 /* Check for overlap between registers marked in CLOBBERED_REGS and
599 anything inappropriate in T. Emit error and return the register
600 variable definition for error, NULL_TREE for ok. */
603 tree_conflicts_with_clobbers_p (tree t
, HARD_REG_SET
*clobbered_regs
)
605 /* Conflicts between asm-declared register variables and the clobber
606 list are not allowed. */
607 tree overlap
= tree_overlaps_hard_reg_set (t
, clobbered_regs
);
611 error ("asm-specifier for variable %qE conflicts with asm clobber list",
612 DECL_NAME (overlap
));
614 /* Reset registerness to stop multiple errors emitted for a single
616 DECL_REGISTER (overlap
) = 0;
623 /* Generate RTL for an asm statement with arguments.
624 STRING is the instruction template.
625 OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs.
626 Each output or input has an expression in the TREE_VALUE and
627 a tree list in TREE_PURPOSE which in turn contains a constraint
628 name in TREE_VALUE (or NULL_TREE) and a constraint string
630 CLOBBERS is a list of STRING_CST nodes each naming a hard register
631 that is clobbered by this insn.
633 Not all kinds of lvalue that may appear in OUTPUTS can be stored directly.
634 Some elements of OUTPUTS may be replaced with trees representing temporary
635 values. The caller should copy those temporary values to the originally
638 VOL nonzero means the insn is volatile; don't optimize it. */
641 expand_asm_operands (tree string
, tree outputs
, tree inputs
,
642 tree clobbers
, tree labels
, int vol
, location_t locus
)
644 rtvec argvec
, constraintvec
, labelvec
;
646 int ninputs
= list_length (inputs
);
647 int noutputs
= list_length (outputs
);
648 int nlabels
= list_length (labels
);
651 HARD_REG_SET clobbered_regs
;
652 int clobber_conflict_found
= 0;
656 /* Vector of RTX's of evaluated output operands. */
657 rtx
*output_rtx
= XALLOCAVEC (rtx
, noutputs
);
658 int *inout_opnum
= XALLOCAVEC (int, noutputs
);
659 rtx
*real_output_rtx
= XALLOCAVEC (rtx
, noutputs
);
660 enum machine_mode
*inout_mode
= XALLOCAVEC (enum machine_mode
, noutputs
);
661 const char **constraints
= XALLOCAVEC (const char *, noutputs
+ ninputs
);
662 int old_generating_concat_p
= generating_concat_p
;
664 /* An ASM with no outputs needs to be treated as volatile, for now. */
668 if (! check_operand_nalternatives (outputs
, inputs
))
671 string
= resolve_asm_operand_names (string
, outputs
, inputs
, labels
);
673 /* Collect constraints. */
675 for (t
= outputs
; t
; t
= TREE_CHAIN (t
), i
++)
676 constraints
[i
] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
677 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), i
++)
678 constraints
[i
] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
680 /* Sometimes we wish to automatically clobber registers across an asm.
681 Case in point is when the i386 backend moved from cc0 to a hard reg --
682 maintaining source-level compatibility means automatically clobbering
683 the flags register. */
684 clobbers
= targetm
.md_asm_clobbers (outputs
, inputs
, clobbers
);
686 /* Count the number of meaningful clobbered registers, ignoring what
687 we would ignore later. */
689 CLEAR_HARD_REG_SET (clobbered_regs
);
690 for (tail
= clobbers
; tail
; tail
= TREE_CHAIN (tail
))
695 if (TREE_VALUE (tail
) == error_mark_node
)
697 regname
= TREE_STRING_POINTER (TREE_VALUE (tail
));
699 i
= decode_reg_name_and_count (regname
, &nregs
);
703 error ("unknown register name %qs in %<asm%>", regname
);
705 /* Mark clobbered registers. */
710 for (reg
= i
; reg
< i
+ nregs
; reg
++)
714 /* Clobbering the PIC register is an error. */
715 if (reg
== (int) PIC_OFFSET_TABLE_REGNUM
)
717 error ("PIC register clobbered by %qs in %<asm%>", regname
);
721 SET_HARD_REG_BIT (clobbered_regs
, reg
);
726 /* First pass over inputs and outputs checks validity and sets
727 mark_addressable if needed. */
730 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
732 tree val
= TREE_VALUE (tail
);
733 tree type
= TREE_TYPE (val
);
734 const char *constraint
;
739 /* If there's an erroneous arg, emit no insn. */
740 if (type
== error_mark_node
)
743 /* Try to parse the output constraint. If that fails, there's
744 no point in going further. */
745 constraint
= constraints
[i
];
746 if (!parse_output_constraint (&constraint
, i
, ninputs
, noutputs
,
747 &allows_mem
, &allows_reg
, &is_inout
))
754 && REG_P (DECL_RTL (val
))
755 && GET_MODE (DECL_RTL (val
)) != TYPE_MODE (type
))))
756 mark_addressable (val
);
763 if (ninputs
+ noutputs
> MAX_RECOG_OPERANDS
)
765 error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS
);
769 for (i
= 0, tail
= inputs
; tail
; i
++, tail
= TREE_CHAIN (tail
))
771 bool allows_reg
, allows_mem
;
772 const char *constraint
;
774 /* If there's an erroneous arg, emit no insn, because the ASM_INPUT
775 would get VOIDmode and that could cause a crash in reload. */
776 if (TREE_TYPE (TREE_VALUE (tail
)) == error_mark_node
)
779 constraint
= constraints
[i
+ noutputs
];
780 if (! parse_input_constraint (&constraint
, i
, ninputs
, noutputs
, ninout
,
781 constraints
, &allows_mem
, &allows_reg
))
784 if (! allows_reg
&& allows_mem
)
785 mark_addressable (TREE_VALUE (tail
));
788 /* Second pass evaluates arguments. */
790 /* Make sure stack is consistent for asm goto. */
792 do_pending_stack_adjust ();
795 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
797 tree val
= TREE_VALUE (tail
);
798 tree type
= TREE_TYPE (val
);
805 ok
= parse_output_constraint (&constraints
[i
], i
, ninputs
,
806 noutputs
, &allows_mem
, &allows_reg
,
810 /* If an output operand is not a decl or indirect ref and our constraint
811 allows a register, make a temporary to act as an intermediate.
812 Make the asm insn write into that, then our caller will copy it to
813 the real output operand. Likewise for promoted variables. */
815 generating_concat_p
= 0;
817 real_output_rtx
[i
] = NULL_RTX
;
818 if ((TREE_CODE (val
) == INDIRECT_REF
821 && (allows_mem
|| REG_P (DECL_RTL (val
)))
822 && ! (REG_P (DECL_RTL (val
))
823 && GET_MODE (DECL_RTL (val
)) != TYPE_MODE (type
)))
827 op
= expand_expr (val
, NULL_RTX
, VOIDmode
, EXPAND_WRITE
);
829 op
= validize_mem (op
);
831 if (! allows_reg
&& !MEM_P (op
))
832 error ("output number %d not directly addressable", i
);
833 if ((! allows_mem
&& MEM_P (op
))
834 || GET_CODE (op
) == CONCAT
)
836 real_output_rtx
[i
] = op
;
837 op
= gen_reg_rtx (GET_MODE (op
));
839 emit_move_insn (op
, real_output_rtx
[i
]);
844 op
= assign_temp (type
, 0, 0, 1);
845 op
= validize_mem (op
);
846 if (!MEM_P (op
) && TREE_CODE (TREE_VALUE (tail
)) == SSA_NAME
)
847 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (TREE_VALUE (tail
)), op
);
848 TREE_VALUE (tail
) = make_tree (type
, op
);
852 generating_concat_p
= old_generating_concat_p
;
856 inout_mode
[ninout
] = TYPE_MODE (type
);
857 inout_opnum
[ninout
++] = i
;
860 if (tree_conflicts_with_clobbers_p (val
, &clobbered_regs
))
861 clobber_conflict_found
= 1;
864 /* Make vectors for the expression-rtx, constraint strings,
865 and named operands. */
867 argvec
= rtvec_alloc (ninputs
);
868 constraintvec
= rtvec_alloc (ninputs
);
869 labelvec
= rtvec_alloc (nlabels
);
871 body
= gen_rtx_ASM_OPERANDS ((noutputs
== 0 ? VOIDmode
872 : GET_MODE (output_rtx
[0])),
873 ggc_strdup (TREE_STRING_POINTER (string
)),
874 empty_string
, 0, argvec
, constraintvec
,
877 MEM_VOLATILE_P (body
) = vol
;
879 /* Eval the inputs and put them into ARGVEC.
880 Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */
882 for (i
= 0, tail
= inputs
; tail
; tail
= TREE_CHAIN (tail
), ++i
)
884 bool allows_reg
, allows_mem
;
885 const char *constraint
;
890 constraint
= constraints
[i
+ noutputs
];
891 ok
= parse_input_constraint (&constraint
, i
, ninputs
, noutputs
, ninout
,
892 constraints
, &allows_mem
, &allows_reg
);
895 generating_concat_p
= 0;
897 val
= TREE_VALUE (tail
);
898 type
= TREE_TYPE (val
);
899 /* EXPAND_INITIALIZER will not generate code for valid initializer
900 constants, but will still generate code for other types of operand.
901 This is the behavior we want for constant constraints. */
902 op
= expand_expr (val
, NULL_RTX
, VOIDmode
,
903 allows_reg
? EXPAND_NORMAL
904 : allows_mem
? EXPAND_MEMORY
905 : EXPAND_INITIALIZER
);
907 /* Never pass a CONCAT to an ASM. */
908 if (GET_CODE (op
) == CONCAT
)
909 op
= force_reg (GET_MODE (op
), op
);
911 op
= validize_mem (op
);
913 if (asm_operand_ok (op
, constraint
, NULL
) <= 0)
915 if (allows_reg
&& TYPE_MODE (type
) != BLKmode
)
916 op
= force_reg (TYPE_MODE (type
), op
);
917 else if (!allows_mem
)
918 warning (0, "asm operand %d probably doesn%'t match constraints",
922 /* We won't recognize either volatile memory or memory
923 with a queued address as available a memory_operand
924 at this point. Ignore it: clearly this *is* a memory. */
928 warning (0, "use of memory input without lvalue in "
929 "asm operand %d is deprecated", i
+ noutputs
);
933 rtx mem
= force_const_mem (TYPE_MODE (type
), op
);
935 op
= validize_mem (mem
);
937 op
= force_reg (TYPE_MODE (type
), op
);
940 || GET_CODE (op
) == SUBREG
941 || GET_CODE (op
) == CONCAT
)
943 tree qual_type
= build_qualified_type (type
,
946 rtx memloc
= assign_temp (qual_type
, 1, 1, 1);
947 memloc
= validize_mem (memloc
);
948 emit_move_insn (memloc
, op
);
954 generating_concat_p
= old_generating_concat_p
;
955 ASM_OPERANDS_INPUT (body
, i
) = op
;
957 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body
, i
)
958 = gen_rtx_ASM_INPUT (TYPE_MODE (type
),
959 ggc_strdup (constraints
[i
+ noutputs
]));
961 if (tree_conflicts_with_clobbers_p (val
, &clobbered_regs
))
962 clobber_conflict_found
= 1;
965 /* Protect all the operands from the queue now that they have all been
968 generating_concat_p
= 0;
970 /* For in-out operands, copy output rtx to input rtx. */
971 for (i
= 0; i
< ninout
; i
++)
973 int j
= inout_opnum
[i
];
976 ASM_OPERANDS_INPUT (body
, ninputs
- ninout
+ i
)
979 sprintf (buffer
, "%d", j
);
980 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body
, ninputs
- ninout
+ i
)
981 = gen_rtx_ASM_INPUT (inout_mode
[i
], ggc_strdup (buffer
));
984 /* Copy labels to the vector. */
985 for (i
= 0, tail
= labels
; i
< nlabels
; ++i
, tail
= TREE_CHAIN (tail
))
986 ASM_OPERANDS_LABEL (body
, i
)
987 = gen_rtx_LABEL_REF (Pmode
, label_rtx (TREE_VALUE (tail
)));
989 generating_concat_p
= old_generating_concat_p
;
991 /* Now, for each output, construct an rtx
992 (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER
993 ARGVEC CONSTRAINTS OPNAMES))
994 If there is more than one, put them inside a PARALLEL. */
996 if (nlabels
> 0 && nclobbers
== 0)
998 gcc_assert (noutputs
== 0);
999 emit_jump_insn (body
);
1001 else if (noutputs
== 0 && nclobbers
== 0)
1003 /* No output operands: put in a raw ASM_OPERANDS rtx. */
1006 else if (noutputs
== 1 && nclobbers
== 0)
1008 ASM_OPERANDS_OUTPUT_CONSTRAINT (body
) = ggc_strdup (constraints
[0]);
1009 emit_insn (gen_rtx_SET (VOIDmode
, output_rtx
[0], body
));
1019 body
= gen_rtx_PARALLEL (VOIDmode
, rtvec_alloc (num
+ nclobbers
));
1021 /* For each output operand, store a SET. */
1022 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
1024 XVECEXP (body
, 0, i
)
1025 = gen_rtx_SET (VOIDmode
,
1027 gen_rtx_ASM_OPERANDS
1028 (GET_MODE (output_rtx
[i
]),
1029 ggc_strdup (TREE_STRING_POINTER (string
)),
1030 ggc_strdup (constraints
[i
]),
1031 i
, argvec
, constraintvec
, labelvec
, locus
));
1033 MEM_VOLATILE_P (SET_SRC (XVECEXP (body
, 0, i
))) = vol
;
1036 /* If there are no outputs (but there are some clobbers)
1037 store the bare ASM_OPERANDS into the PARALLEL. */
1040 XVECEXP (body
, 0, i
++) = obody
;
1042 /* Store (clobber REG) for each clobbered register specified. */
1044 for (tail
= clobbers
; tail
; tail
= TREE_CHAIN (tail
))
1046 const char *regname
= TREE_STRING_POINTER (TREE_VALUE (tail
));
1048 int j
= decode_reg_name_and_count (regname
, &nregs
);
1053 if (j
== -3) /* `cc', which is not a register */
1056 if (j
== -4) /* `memory', don't cache memory across asm */
1058 XVECEXP (body
, 0, i
++)
1059 = gen_rtx_CLOBBER (VOIDmode
,
1062 gen_rtx_SCRATCH (VOIDmode
)));
1066 /* Ignore unknown register, error already signaled. */
1070 for (reg
= j
; reg
< j
+ nregs
; reg
++)
1072 /* Use QImode since that's guaranteed to clobber just
1074 clobbered_reg
= gen_rtx_REG (QImode
, reg
);
1076 /* Do sanity check for overlap between clobbers and
1077 respectively input and outputs that hasn't been
1078 handled. Such overlap should have been detected and
1080 if (!clobber_conflict_found
)
1084 /* We test the old body (obody) contents to avoid
1085 tripping over the under-construction body. */
1086 for (opno
= 0; opno
< noutputs
; opno
++)
1087 if (reg_overlap_mentioned_p (clobbered_reg
,
1090 ("asm clobber conflict with output operand");
1092 for (opno
= 0; opno
< ninputs
- ninout
; opno
++)
1093 if (reg_overlap_mentioned_p (clobbered_reg
,
1094 ASM_OPERANDS_INPUT (obody
,
1097 ("asm clobber conflict with input operand");
1100 XVECEXP (body
, 0, i
++)
1101 = gen_rtx_CLOBBER (VOIDmode
, clobbered_reg
);
1106 emit_jump_insn (body
);
1111 /* For any outputs that needed reloading into registers, spill them
1112 back to where they belong. */
1113 for (i
= 0; i
< noutputs
; ++i
)
1114 if (real_output_rtx
[i
])
1115 emit_move_insn (real_output_rtx
[i
], output_rtx
[i
]);
1117 crtl
->has_asm_statement
= 1;
1118 coverage_has_asm_stmt ();
1123 expand_asm_stmt (gimple stmt
)
1126 tree outputs
, tail
, t
;
1130 tree str
, out
, in
, cl
, labels
;
1131 location_t locus
= gimple_location (stmt
);
1133 /* Meh... convert the gimple asm operands into real tree lists.
1134 Eventually we should make all routines work on the vectors instead
1135 of relying on TREE_CHAIN. */
1137 n
= gimple_asm_noutputs (stmt
);
1140 t
= out
= gimple_asm_output_op (stmt
, 0);
1141 for (i
= 1; i
< n
; i
++)
1142 t
= TREE_CHAIN (t
) = gimple_asm_output_op (stmt
, i
);
1146 n
= gimple_asm_ninputs (stmt
);
1149 t
= in
= gimple_asm_input_op (stmt
, 0);
1150 for (i
= 1; i
< n
; i
++)
1151 t
= TREE_CHAIN (t
) = gimple_asm_input_op (stmt
, i
);
1155 n
= gimple_asm_nclobbers (stmt
);
1158 t
= cl
= gimple_asm_clobber_op (stmt
, 0);
1159 for (i
= 1; i
< n
; i
++)
1160 t
= TREE_CHAIN (t
) = gimple_asm_clobber_op (stmt
, i
);
1164 n
= gimple_asm_nlabels (stmt
);
1167 t
= labels
= gimple_asm_label_op (stmt
, 0);
1168 for (i
= 1; i
< n
; i
++)
1169 t
= TREE_CHAIN (t
) = gimple_asm_label_op (stmt
, i
);
1172 s
= gimple_asm_string (stmt
);
1173 str
= build_string (strlen (s
), s
);
1175 if (gimple_asm_input_p (stmt
))
1177 expand_asm_loc (str
, gimple_asm_volatile_p (stmt
), locus
);
1182 noutputs
= gimple_asm_noutputs (stmt
);
1183 /* o[I] is the place that output number I should be written. */
1184 o
= (tree
*) alloca (noutputs
* sizeof (tree
));
1186 /* Record the contents of OUTPUTS before it is modified. */
1187 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
1188 o
[i
] = TREE_VALUE (tail
);
1190 /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of
1191 OUTPUTS some trees for where the values were actually stored. */
1192 expand_asm_operands (str
, outputs
, in
, cl
, labels
,
1193 gimple_asm_volatile_p (stmt
), locus
);
1195 /* Copy all the intermediate outputs into the specified outputs. */
1196 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
1198 if (o
[i
] != TREE_VALUE (tail
))
1200 expand_assignment (o
[i
], TREE_VALUE (tail
), false);
1203 /* Restore the original value so that it's correct the next
1204 time we expand this function. */
1205 TREE_VALUE (tail
) = o
[i
];
1210 /* A subroutine of expand_asm_operands. Check that all operands have
1211 the same number of alternatives. Return true if so. */
1214 check_operand_nalternatives (tree outputs
, tree inputs
)
1216 if (outputs
|| inputs
)
1218 tree tmp
= TREE_PURPOSE (outputs
? outputs
: inputs
);
1220 = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp
)));
1223 if (nalternatives
+ 1 > MAX_RECOG_ALTERNATIVES
)
1225 error ("too many alternatives in %<asm%>");
1232 const char *constraint
1233 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp
)));
1235 if (n_occurrences (',', constraint
) != nalternatives
)
1237 error ("operand constraints for %<asm%> differ "
1238 "in number of alternatives");
1242 if (TREE_CHAIN (tmp
))
1243 tmp
= TREE_CHAIN (tmp
);
1245 tmp
= next
, next
= 0;
1252 /* A subroutine of expand_asm_operands. Check that all operand names
1253 are unique. Return true if so. We rely on the fact that these names
1254 are identifiers, and so have been canonicalized by get_identifier,
1255 so all we need are pointer comparisons. */
1258 check_unique_operand_names (tree outputs
, tree inputs
, tree labels
)
1260 tree i
, j
, i_name
= NULL_TREE
;
1262 for (i
= outputs
; i
; i
= TREE_CHAIN (i
))
1264 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
1268 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
1269 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
1273 for (i
= inputs
; i
; i
= TREE_CHAIN (i
))
1275 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
1279 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
1280 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
1282 for (j
= outputs
; j
; j
= TREE_CHAIN (j
))
1283 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
1287 for (i
= labels
; i
; i
= TREE_CHAIN (i
))
1289 i_name
= TREE_PURPOSE (i
);
1293 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
1294 if (simple_cst_equal (i_name
, TREE_PURPOSE (j
)))
1296 for (j
= inputs
; j
; j
= TREE_CHAIN (j
))
1297 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
1304 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name
));
1308 /* A subroutine of expand_asm_operands. Resolve the names of the operands
1309 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
1310 STRING and in the constraints to those numbers. */
1313 resolve_asm_operand_names (tree string
, tree outputs
, tree inputs
, tree labels
)
1320 check_unique_operand_names (outputs
, inputs
, labels
);
1322 /* Substitute [<name>] in input constraint strings. There should be no
1323 named operands in output constraints. */
1324 for (t
= inputs
; t
; t
= TREE_CHAIN (t
))
1326 c
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
1327 if (strchr (c
, '[') != NULL
)
1329 p
= buffer
= xstrdup (c
);
1330 while ((p
= strchr (p
, '[')) != NULL
)
1331 p
= resolve_operand_name_1 (p
, outputs
, inputs
, NULL
);
1332 TREE_VALUE (TREE_PURPOSE (t
))
1333 = build_string (strlen (buffer
), buffer
);
1338 /* Now check for any needed substitutions in the template. */
1339 c
= TREE_STRING_POINTER (string
);
1340 while ((c
= strchr (c
, '%')) != NULL
)
1344 else if (ISALPHA (c
[1]) && c
[2] == '[')
1348 c
+= 1 + (c
[1] == '%');
1355 /* OK, we need to make a copy so we can perform the substitutions.
1356 Assume that we will not need extra space--we get to remove '['
1357 and ']', which means we cannot have a problem until we have more
1358 than 999 operands. */
1359 buffer
= xstrdup (TREE_STRING_POINTER (string
));
1360 p
= buffer
+ (c
- TREE_STRING_POINTER (string
));
1362 while ((p
= strchr (p
, '%')) != NULL
)
1366 else if (ISALPHA (p
[1]) && p
[2] == '[')
1370 p
+= 1 + (p
[1] == '%');
1374 p
= resolve_operand_name_1 (p
, outputs
, inputs
, labels
);
1377 string
= build_string (strlen (buffer
), buffer
);
1384 /* A subroutine of resolve_operand_names. P points to the '[' for a
1385 potential named operand of the form [<name>]. In place, replace
1386 the name and brackets with a number. Return a pointer to the
1387 balance of the string after substitution. */
1390 resolve_operand_name_1 (char *p
, tree outputs
, tree inputs
, tree labels
)
1396 /* Collect the operand name. */
1397 q
= strchr (++p
, ']');
1400 error ("missing close brace for named operand");
1401 return strchr (p
, '\0');
1405 /* Resolve the name to a number. */
1406 for (op
= 0, t
= outputs
; t
; t
= TREE_CHAIN (t
), op
++)
1408 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
1409 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
1412 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), op
++)
1414 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
1415 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
1418 for (t
= labels
; t
; t
= TREE_CHAIN (t
), op
++)
1420 tree name
= TREE_PURPOSE (t
);
1421 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
1425 error ("undefined named operand %qs", identifier_to_locale (p
));
1429 /* Replace the name with the number. Unfortunately, not all libraries
1430 get the return value of sprintf correct, so search for the end of the
1431 generated string by hand. */
1432 sprintf (--p
, "%d", op
);
1433 p
= strchr (p
, '\0');
1435 /* Verify the no extra buffer space assumption. */
1436 gcc_assert (p
<= q
);
1438 /* Shift the rest of the buffer down to fill the gap. */
1439 memmove (p
, q
+ 1, strlen (q
+ 1) + 1);
1444 /* Generate RTL to evaluate the expression EXP. */
1447 expand_expr_stmt (tree exp
)
1452 value
= expand_expr (exp
, const0_rtx
, VOIDmode
, EXPAND_NORMAL
);
1453 type
= TREE_TYPE (exp
);
1455 /* If all we do is reference a volatile value in memory,
1456 copy it to a register to be sure it is actually touched. */
1457 if (value
&& MEM_P (value
) && TREE_THIS_VOLATILE (exp
))
1459 if (TYPE_MODE (type
) == VOIDmode
)
1461 else if (TYPE_MODE (type
) != BLKmode
)
1462 value
= copy_to_reg (value
);
1465 rtx lab
= gen_label_rtx ();
1467 /* Compare the value with itself to reference it. */
1468 emit_cmp_and_jump_insns (value
, value
, EQ
,
1469 expand_normal (TYPE_SIZE (type
)),
1475 /* Free any temporaries used to evaluate this expression. */
1479 /* Warn if EXP contains any computations whose results are not used.
1480 Return 1 if a warning is printed; 0 otherwise. LOCUS is the
1481 (potential) location of the expression. */
1484 warn_if_unused_value (const_tree exp
, location_t locus
)
1487 if (TREE_USED (exp
) || TREE_NO_WARNING (exp
))
1490 /* Don't warn about void constructs. This includes casting to void,
1491 void function calls, and statement expressions with a final cast
1493 if (VOID_TYPE_P (TREE_TYPE (exp
)))
1496 if (EXPR_HAS_LOCATION (exp
))
1497 locus
= EXPR_LOCATION (exp
);
1499 switch (TREE_CODE (exp
))
1501 case PREINCREMENT_EXPR
:
1502 case POSTINCREMENT_EXPR
:
1503 case PREDECREMENT_EXPR
:
1504 case POSTDECREMENT_EXPR
:
1509 case TRY_CATCH_EXPR
:
1510 case WITH_CLEANUP_EXPR
:
1516 /* For a binding, warn if no side effect within it. */
1517 exp
= BIND_EXPR_BODY (exp
);
1521 case NON_LVALUE_EXPR
:
1522 exp
= TREE_OPERAND (exp
, 0);
1525 case TRUTH_ORIF_EXPR
:
1526 case TRUTH_ANDIF_EXPR
:
1527 /* In && or ||, warn if 2nd operand has no side effect. */
1528 exp
= TREE_OPERAND (exp
, 1);
1532 if (warn_if_unused_value (TREE_OPERAND (exp
, 0), locus
))
1534 /* Let people do `(foo (), 0)' without a warning. */
1535 if (TREE_CONSTANT (TREE_OPERAND (exp
, 1)))
1537 exp
= TREE_OPERAND (exp
, 1);
1541 /* If this is an expression with side effects, don't warn; this
1542 case commonly appears in macro expansions. */
1543 if (TREE_SIDE_EFFECTS (exp
))
1548 /* Don't warn about automatic dereferencing of references, since
1549 the user cannot control it. */
1550 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp
, 0))) == REFERENCE_TYPE
)
1552 exp
= TREE_OPERAND (exp
, 0);
1558 /* Referencing a volatile value is a side effect, so don't warn. */
1559 if ((DECL_P (exp
) || REFERENCE_CLASS_P (exp
))
1560 && TREE_THIS_VOLATILE (exp
))
1563 /* If this is an expression which has no operands, there is no value
1564 to be unused. There are no such language-independent codes,
1565 but front ends may define such. */
1566 if (EXPRESSION_CLASS_P (exp
) && TREE_OPERAND_LENGTH (exp
) == 0)
1570 warning_at (locus
, OPT_Wunused_value
, "value computed is not used");
1576 /* Generate RTL to return from the current function, with no value.
1577 (That is, we do not do anything about returning any value.) */
1580 expand_null_return (void)
1582 /* If this function was declared to return a value, but we
1583 didn't, clobber the return registers so that they are not
1584 propagated live to the rest of the function. */
1585 clobber_return_register ();
1587 expand_null_return_1 ();
1590 /* Generate RTL to return directly from the current function.
1591 (That is, we bypass any return value.) */
1594 expand_naked_return (void)
1598 clear_pending_stack_adjust ();
1599 do_pending_stack_adjust ();
1601 end_label
= naked_return_label
;
1603 end_label
= naked_return_label
= gen_label_rtx ();
1605 emit_jump (end_label
);
1608 /* Generate RTL to return from the current function, with value VAL. */
1611 expand_value_return (rtx val
)
1613 /* Copy the value to the return location unless it's already there. */
1615 tree decl
= DECL_RESULT (current_function_decl
);
1616 rtx return_reg
= DECL_RTL (decl
);
1617 if (return_reg
!= val
)
1619 tree funtype
= TREE_TYPE (current_function_decl
);
1620 tree type
= TREE_TYPE (decl
);
1621 int unsignedp
= TYPE_UNSIGNED (type
);
1622 enum machine_mode old_mode
= DECL_MODE (decl
);
1623 enum machine_mode mode
;
1624 if (DECL_BY_REFERENCE (decl
))
1625 mode
= promote_function_mode (type
, old_mode
, &unsignedp
, funtype
, 2);
1627 mode
= promote_function_mode (type
, old_mode
, &unsignedp
, funtype
, 1);
1629 if (mode
!= old_mode
)
1630 val
= convert_modes (mode
, old_mode
, val
, unsignedp
);
1632 if (GET_CODE (return_reg
) == PARALLEL
)
1633 emit_group_load (return_reg
, val
, type
, int_size_in_bytes (type
));
1635 emit_move_insn (return_reg
, val
);
1638 expand_null_return_1 ();
1641 /* Output a return with no value. */
1644 expand_null_return_1 (void)
1646 clear_pending_stack_adjust ();
1647 do_pending_stack_adjust ();
1648 emit_jump (return_label
);
1651 /* Generate RTL to evaluate the expression RETVAL and return it
1652 from the current function. */
1655 expand_return (tree retval
)
1661 /* If function wants no value, give it none. */
1662 if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl
))) == VOID_TYPE
)
1664 expand_normal (retval
);
1665 expand_null_return ();
1669 if (retval
== error_mark_node
)
1671 /* Treat this like a return of no value from a function that
1673 expand_null_return ();
1676 else if ((TREE_CODE (retval
) == MODIFY_EXPR
1677 || TREE_CODE (retval
) == INIT_EXPR
)
1678 && TREE_CODE (TREE_OPERAND (retval
, 0)) == RESULT_DECL
)
1679 retval_rhs
= TREE_OPERAND (retval
, 1);
1681 retval_rhs
= retval
;
1683 result_rtl
= DECL_RTL (DECL_RESULT (current_function_decl
));
1685 /* If we are returning the RESULT_DECL, then the value has already
1686 been stored into it, so we don't have to do anything special. */
1687 if (TREE_CODE (retval_rhs
) == RESULT_DECL
)
1688 expand_value_return (result_rtl
);
1690 /* If the result is an aggregate that is being returned in one (or more)
1691 registers, load the registers here. The compiler currently can't handle
1692 copying a BLKmode value into registers. We could put this code in a
1693 more general area (for use by everyone instead of just function
1694 call/return), but until this feature is generally usable it is kept here
1695 (and in expand_call). */
1697 else if (retval_rhs
!= 0
1698 && TYPE_MODE (TREE_TYPE (retval_rhs
)) == BLKmode
1699 && REG_P (result_rtl
))
1702 unsigned HOST_WIDE_INT bitpos
, xbitpos
;
1703 unsigned HOST_WIDE_INT padding_correction
= 0;
1704 unsigned HOST_WIDE_INT bytes
1705 = int_size_in_bytes (TREE_TYPE (retval_rhs
));
1706 int n_regs
= (bytes
+ UNITS_PER_WORD
- 1) / UNITS_PER_WORD
;
1707 unsigned int bitsize
1708 = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs
)), BITS_PER_WORD
);
1709 rtx
*result_pseudos
= XALLOCAVEC (rtx
, n_regs
);
1710 rtx result_reg
, src
= NULL_RTX
, dst
= NULL_RTX
;
1711 rtx result_val
= expand_normal (retval_rhs
);
1712 enum machine_mode tmpmode
, result_reg_mode
;
1716 expand_null_return ();
1720 /* If the structure doesn't take up a whole number of words, see
1721 whether the register value should be padded on the left or on
1722 the right. Set PADDING_CORRECTION to the number of padding
1723 bits needed on the left side.
1725 In most ABIs, the structure will be returned at the least end of
1726 the register, which translates to right padding on little-endian
1727 targets and left padding on big-endian targets. The opposite
1728 holds if the structure is returned at the most significant
1729 end of the register. */
1730 if (bytes
% UNITS_PER_WORD
!= 0
1731 && (targetm
.calls
.return_in_msb (TREE_TYPE (retval_rhs
))
1733 : BYTES_BIG_ENDIAN
))
1734 padding_correction
= (BITS_PER_WORD
- ((bytes
% UNITS_PER_WORD
)
1737 /* Copy the structure BITSIZE bits at a time. */
1738 for (bitpos
= 0, xbitpos
= padding_correction
;
1739 bitpos
< bytes
* BITS_PER_UNIT
;
1740 bitpos
+= bitsize
, xbitpos
+= bitsize
)
1742 /* We need a new destination pseudo each time xbitpos is
1743 on a word boundary and when xbitpos == padding_correction
1744 (the first time through). */
1745 if (xbitpos
% BITS_PER_WORD
== 0
1746 || xbitpos
== padding_correction
)
1748 /* Generate an appropriate register. */
1749 dst
= gen_reg_rtx (word_mode
);
1750 result_pseudos
[xbitpos
/ BITS_PER_WORD
] = dst
;
1752 /* Clear the destination before we move anything into it. */
1753 emit_move_insn (dst
, CONST0_RTX (GET_MODE (dst
)));
1756 /* We need a new source operand each time bitpos is on a word
1758 if (bitpos
% BITS_PER_WORD
== 0)
1759 src
= operand_subword_force (result_val
,
1760 bitpos
/ BITS_PER_WORD
,
1763 /* Use bitpos for the source extraction (left justified) and
1764 xbitpos for the destination store (right justified). */
1765 store_bit_field (dst
, bitsize
, xbitpos
% BITS_PER_WORD
, word_mode
,
1766 extract_bit_field (src
, bitsize
,
1767 bitpos
% BITS_PER_WORD
, 1, false,
1768 NULL_RTX
, word_mode
, word_mode
));
1771 tmpmode
= GET_MODE (result_rtl
);
1772 if (tmpmode
== BLKmode
)
1774 /* Find the smallest integer mode large enough to hold the
1775 entire structure and use that mode instead of BLKmode
1776 on the USE insn for the return register. */
1777 for (tmpmode
= GET_CLASS_NARROWEST_MODE (MODE_INT
);
1778 tmpmode
!= VOIDmode
;
1779 tmpmode
= GET_MODE_WIDER_MODE (tmpmode
))
1780 /* Have we found a large enough mode? */
1781 if (GET_MODE_SIZE (tmpmode
) >= bytes
)
1784 /* A suitable mode should have been found. */
1785 gcc_assert (tmpmode
!= VOIDmode
);
1787 PUT_MODE (result_rtl
, tmpmode
);
1790 if (GET_MODE_SIZE (tmpmode
) < GET_MODE_SIZE (word_mode
))
1791 result_reg_mode
= word_mode
;
1793 result_reg_mode
= tmpmode
;
1794 result_reg
= gen_reg_rtx (result_reg_mode
);
1796 for (i
= 0; i
< n_regs
; i
++)
1797 emit_move_insn (operand_subword (result_reg
, i
, 0, result_reg_mode
),
1800 if (tmpmode
!= result_reg_mode
)
1801 result_reg
= gen_lowpart (tmpmode
, result_reg
);
1803 expand_value_return (result_reg
);
1805 else if (retval_rhs
!= 0
1806 && !VOID_TYPE_P (TREE_TYPE (retval_rhs
))
1807 && (REG_P (result_rtl
)
1808 || (GET_CODE (result_rtl
) == PARALLEL
)))
1810 /* Calculate the return value into a temporary (usually a pseudo
1812 tree ot
= TREE_TYPE (DECL_RESULT (current_function_decl
));
1813 tree nt
= build_qualified_type (ot
, TYPE_QUALS (ot
) | TYPE_QUAL_CONST
);
1815 val
= assign_temp (nt
, 0, 0, 1);
1816 val
= expand_expr (retval_rhs
, val
, GET_MODE (val
), EXPAND_NORMAL
);
1817 val
= force_not_mem (val
);
1818 /* Return the calculated value. */
1819 expand_value_return (val
);
1823 /* No hard reg used; calculate value into hard return reg. */
1824 expand_expr (retval
, const0_rtx
, VOIDmode
, EXPAND_NORMAL
);
1825 expand_value_return (result_rtl
);
1829 /* Emit code to restore vital registers at the beginning of a nonlocal goto
1832 expand_nl_goto_receiver (void)
1836 /* Clobber the FP when we get here, so we have to make sure it's
1837 marked as used by this function. */
1838 emit_use (hard_frame_pointer_rtx
);
1840 /* Mark the static chain as clobbered here so life information
1841 doesn't get messed up for it. */
1842 chain
= targetm
.calls
.static_chain (current_function_decl
, true);
1843 if (chain
&& REG_P (chain
))
1844 emit_clobber (chain
);
1846 #ifdef HAVE_nonlocal_goto
1847 if (! HAVE_nonlocal_goto
)
1849 /* First adjust our frame pointer to its actual value. It was
1850 previously set to the start of the virtual area corresponding to
1851 the stacked variables when we branched here and now needs to be
1852 adjusted to the actual hardware fp value.
1854 Assignments are to virtual registers are converted by
1855 instantiate_virtual_regs into the corresponding assignment
1856 to the underlying register (fp in this case) that makes
1857 the original assignment true.
1858 So the following insn will actually be
1859 decrementing fp by STARTING_FRAME_OFFSET. */
1860 emit_move_insn (virtual_stack_vars_rtx
, hard_frame_pointer_rtx
);
1862 #if !HARD_FRAME_POINTER_IS_ARG_POINTER
1863 if (fixed_regs
[ARG_POINTER_REGNUM
])
1865 #ifdef ELIMINABLE_REGS
1866 /* If the argument pointer can be eliminated in favor of the
1867 frame pointer, we don't need to restore it. We assume here
1868 that if such an elimination is present, it can always be used.
1869 This is the case on all known machines; if we don't make this
1870 assumption, we do unnecessary saving on many machines. */
1871 static const struct elims
{const int from
, to
;} elim_regs
[] = ELIMINABLE_REGS
;
1874 for (i
= 0; i
< ARRAY_SIZE (elim_regs
); i
++)
1875 if (elim_regs
[i
].from
== ARG_POINTER_REGNUM
1876 && elim_regs
[i
].to
== HARD_FRAME_POINTER_REGNUM
)
1879 if (i
== ARRAY_SIZE (elim_regs
))
1882 /* Now restore our arg pointer from the address at which it
1883 was saved in our stack frame. */
1884 emit_move_insn (crtl
->args
.internal_arg_pointer
,
1885 copy_to_reg (get_arg_pointer_save_area ()));
1890 #ifdef HAVE_nonlocal_goto_receiver
1891 if (HAVE_nonlocal_goto_receiver
)
1892 emit_insn (gen_nonlocal_goto_receiver ());
1895 /* We must not allow the code we just generated to be reordered by
1896 scheduling. Specifically, the update of the frame pointer must
1897 happen immediately, not later. */
1898 emit_insn (gen_blockage ());
1901 /* Generate RTL for the automatic variable declaration DECL.
1902 (Other kinds of declarations are simply ignored if seen here.) */
1905 expand_decl (tree decl
)
1909 type
= TREE_TYPE (decl
);
1911 /* For a CONST_DECL, set mode, alignment, and sizes from those of the
1912 type in case this node is used in a reference. */
1913 if (TREE_CODE (decl
) == CONST_DECL
)
1915 DECL_MODE (decl
) = TYPE_MODE (type
);
1916 DECL_ALIGN (decl
) = TYPE_ALIGN (type
);
1917 DECL_SIZE (decl
) = TYPE_SIZE (type
);
1918 DECL_SIZE_UNIT (decl
) = TYPE_SIZE_UNIT (type
);
1922 /* Otherwise, only automatic variables need any expansion done. Static and
1923 external variables, and external functions, will be handled by
1924 `assemble_variable' (called from finish_decl). TYPE_DECL requires
1925 nothing. PARM_DECLs are handled in `assign_parms'. */
1926 if (TREE_CODE (decl
) != VAR_DECL
)
1929 if (TREE_STATIC (decl
) || DECL_EXTERNAL (decl
))
1932 /* Create the RTL representation for the variable. */
1934 if (type
== error_mark_node
)
1935 SET_DECL_RTL (decl
, gen_rtx_MEM (BLKmode
, const0_rtx
));
1937 else if (DECL_SIZE (decl
) == 0)
1939 /* Variable with incomplete type. */
1941 if (DECL_INITIAL (decl
) == 0)
1942 /* Error message was already done; now avoid a crash. */
1943 x
= gen_rtx_MEM (BLKmode
, const0_rtx
);
1945 /* An initializer is going to decide the size of this array.
1946 Until we know the size, represent its address with a reg. */
1947 x
= gen_rtx_MEM (BLKmode
, gen_reg_rtx (Pmode
));
1949 set_mem_attributes (x
, decl
, 1);
1950 SET_DECL_RTL (decl
, x
);
1952 else if (use_register_for_decl (decl
))
1954 /* Automatic variable that can go in a register. */
1955 enum machine_mode reg_mode
= promote_decl_mode (decl
, NULL
);
1957 SET_DECL_RTL (decl
, gen_reg_rtx (reg_mode
));
1959 /* Note if the object is a user variable. */
1960 if (!DECL_ARTIFICIAL (decl
))
1961 mark_user_reg (DECL_RTL (decl
));
1963 if (POINTER_TYPE_P (type
))
1964 mark_reg_pointer (DECL_RTL (decl
),
1965 TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl
))));
1974 /* Variable-sized decls are dealt with in the gimplifier. */
1975 gcc_assert (TREE_CODE (DECL_SIZE_UNIT (decl
)) == INTEGER_CST
);
1977 /* If we previously made RTL for this decl, it must be an array
1978 whose size was determined by the initializer.
1979 The old address was a register; set that register now
1980 to the proper address. */
1981 if (DECL_RTL_SET_P (decl
))
1983 gcc_assert (MEM_P (DECL_RTL (decl
)));
1984 gcc_assert (REG_P (XEXP (DECL_RTL (decl
), 0)));
1985 oldaddr
= XEXP (DECL_RTL (decl
), 0);
1988 /* Set alignment we actually gave this decl. */
1989 DECL_ALIGN (decl
) = (DECL_MODE (decl
) == BLKmode
? BIGGEST_ALIGNMENT
1990 : GET_MODE_BITSIZE (DECL_MODE (decl
)));
1991 DECL_USER_ALIGN (decl
) = 0;
1993 x
= assign_temp (decl
, 1, 1, 1);
1994 set_mem_attributes (x
, decl
, 1);
1995 SET_DECL_RTL (decl
, x
);
1999 addr
= force_operand (XEXP (DECL_RTL (decl
), 0), oldaddr
);
2000 if (addr
!= oldaddr
)
2001 emit_move_insn (oldaddr
, addr
);
2006 /* Emit code to save the current value of stack. */
2008 expand_stack_save (void)
2012 do_pending_stack_adjust ();
2013 emit_stack_save (SAVE_BLOCK
, &ret
);
2017 /* Emit code to restore the current value of stack. */
2019 expand_stack_restore (tree var
)
2021 rtx sa
= expand_normal (var
);
2023 sa
= convert_memory_address (Pmode
, sa
);
2024 emit_stack_restore (SAVE_BLOCK
, sa
);
2027 /* Do the insertion of a case label into case_list. The labels are
2028 fed to us in descending order from the sorted vector of case labels used
2029 in the tree part of the middle end. So the list we construct is
2030 sorted in ascending order. The bounds on the case range, LOW and HIGH,
2031 are converted to case's index type TYPE. */
2033 static struct case_node
*
2034 add_case_node (struct case_node
*head
, tree type
, tree low
, tree high
,
2035 tree label
, gcov_type count
, alloc_pool case_node_pool
)
2037 tree min_value
, max_value
;
2038 struct case_node
*r
;
2040 gcc_assert (TREE_CODE (low
) == INTEGER_CST
);
2041 gcc_assert (!high
|| TREE_CODE (high
) == INTEGER_CST
);
2043 min_value
= TYPE_MIN_VALUE (type
);
2044 max_value
= TYPE_MAX_VALUE (type
);
2046 /* If there's no HIGH value, then this is not a case range; it's
2047 just a simple case label. But that's just a degenerate case
2049 If the bounds are equal, turn this into the one-value case. */
2050 if (!high
|| tree_int_cst_equal (low
, high
))
2052 /* If the simple case value is unreachable, ignore it. */
2053 if ((TREE_CODE (min_value
) == INTEGER_CST
2054 && tree_int_cst_compare (low
, min_value
) < 0)
2055 || (TREE_CODE (max_value
) == INTEGER_CST
2056 && tree_int_cst_compare (low
, max_value
) > 0))
2058 low
= fold_convert (type
, low
);
2063 /* If the entire case range is unreachable, ignore it. */
2064 if ((TREE_CODE (min_value
) == INTEGER_CST
2065 && tree_int_cst_compare (high
, min_value
) < 0)
2066 || (TREE_CODE (max_value
) == INTEGER_CST
2067 && tree_int_cst_compare (low
, max_value
) > 0))
2070 /* If the lower bound is less than the index type's minimum
2071 value, truncate the range bounds. */
2072 if (TREE_CODE (min_value
) == INTEGER_CST
2073 && tree_int_cst_compare (low
, min_value
) < 0)
2075 low
= fold_convert (type
, low
);
2077 /* If the upper bound is greater than the index type's maximum
2078 value, truncate the range bounds. */
2079 if (TREE_CODE (max_value
) == INTEGER_CST
2080 && tree_int_cst_compare (high
, max_value
) > 0)
2082 high
= fold_convert (type
, high
);
2086 /* Add this label to the chain. Make sure to drop overflow flags. */
2087 r
= (struct case_node
*) pool_alloc (case_node_pool
);
2088 r
->low
= build_int_cst_wide (TREE_TYPE (low
), TREE_INT_CST_LOW (low
),
2089 TREE_INT_CST_HIGH (low
));
2090 r
->high
= build_int_cst_wide (TREE_TYPE (high
), TREE_INT_CST_LOW (high
),
2091 TREE_INT_CST_HIGH (high
));
2092 r
->code_label
= label
;
2093 r
->parent
= r
->left
= NULL
;
2095 r
->subtree_count
= 0;
2100 /* Maximum number of case bit tests. */
2101 #define MAX_CASE_BIT_TESTS 3
2103 /* By default, enable case bit tests on targets with ashlsi3. */
2104 #ifndef CASE_USE_BIT_TESTS
2105 #define CASE_USE_BIT_TESTS (optab_handler (ashl_optab, word_mode) \
2106 != CODE_FOR_nothing)
2110 /* A case_bit_test represents a set of case nodes that may be
2111 selected from using a bit-wise comparison. HI and LO hold
2112 the integer to be tested against, LABEL contains the label
2113 to jump to upon success and BITS counts the number of case
2114 nodes handled by this test, typically the number of bits
2117 struct case_bit_test
2125 /* Determine whether "1 << x" is relatively cheap in word_mode. */
2128 bool lshift_cheap_p (void)
2130 static bool init
[2] = {false, false};
2131 static bool cheap
[2] = {true, true};
2133 bool speed_p
= optimize_insn_for_speed_p ();
2137 rtx reg
= gen_rtx_REG (word_mode
, 10000);
2138 int cost
= rtx_cost (gen_rtx_ASHIFT (word_mode
, const1_rtx
, reg
), SET
,
2140 cheap
[speed_p
] = cost
< COSTS_N_INSNS (3);
2141 init
[speed_p
] = true;
2144 return cheap
[speed_p
];
2147 /* Comparison function for qsort to order bit tests by decreasing
2148 number of case nodes, i.e. the node with the most cases gets
2152 case_bit_test_cmp (const void *p1
, const void *p2
)
2154 const struct case_bit_test
*const d1
= (const struct case_bit_test
*) p1
;
2155 const struct case_bit_test
*const d2
= (const struct case_bit_test
*) p2
;
2157 if (d2
->bits
!= d1
->bits
)
2158 return d2
->bits
- d1
->bits
;
2160 /* Stabilize the sort. */
2161 return CODE_LABEL_NUMBER (d2
->label
) - CODE_LABEL_NUMBER (d1
->label
);
2164 /* Expand a switch statement by a short sequence of bit-wise
2165 comparisons. "switch(x)" is effectively converted into
2166 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
2169 INDEX_EXPR is the value being switched on, which is of
2170 type INDEX_TYPE. MINVAL is the lowest case value of in
2171 the case nodes, of INDEX_TYPE type, and RANGE is highest
2172 value minus MINVAL, also of type INDEX_TYPE. NODES is
2173 the set of case nodes, and DEFAULT_LABEL is the label to
2174 branch to should none of the cases match.
2176 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
2180 emit_case_bit_tests (tree index_type
, tree index_expr
, tree minval
,
2181 tree range
, case_node_ptr nodes
, rtx default_label
)
2183 struct case_bit_test test
[MAX_CASE_BIT_TESTS
];
2184 enum machine_mode mode
;
2185 rtx expr
, index
, label
;
2186 unsigned int i
,j
,lo
,hi
;
2187 struct case_node
*n
;
2191 for (n
= nodes
; n
; n
= n
->right
)
2193 label
= label_rtx (n
->code_label
);
2194 for (i
= 0; i
< count
; i
++)
2195 if (label
== test
[i
].label
)
2200 gcc_assert (count
< MAX_CASE_BIT_TESTS
);
2203 test
[i
].label
= label
;
2210 lo
= tree_low_cst (fold_build2 (MINUS_EXPR
, index_type
,
2211 n
->low
, minval
), 1);
2212 hi
= tree_low_cst (fold_build2 (MINUS_EXPR
, index_type
,
2213 n
->high
, minval
), 1);
2214 for (j
= lo
; j
<= hi
; j
++)
2215 if (j
>= HOST_BITS_PER_WIDE_INT
)
2216 test
[i
].hi
|= (HOST_WIDE_INT
) 1 << (j
- HOST_BITS_PER_INT
);
2218 test
[i
].lo
|= (HOST_WIDE_INT
) 1 << j
;
2221 qsort (test
, count
, sizeof(*test
), case_bit_test_cmp
);
2223 index_expr
= fold_build2 (MINUS_EXPR
, index_type
,
2224 fold_convert (index_type
, index_expr
),
2225 fold_convert (index_type
, minval
));
2226 index
= expand_normal (index_expr
);
2227 do_pending_stack_adjust ();
2229 mode
= TYPE_MODE (index_type
);
2230 expr
= expand_normal (range
);
2232 emit_cmp_and_jump_insns (index
, expr
, GTU
, NULL_RTX
, mode
, 1,
2235 index
= convert_to_mode (word_mode
, index
, 0);
2236 index
= expand_binop (word_mode
, ashl_optab
, const1_rtx
,
2237 index
, NULL_RTX
, 1, OPTAB_WIDEN
);
2239 for (i
= 0; i
< count
; i
++)
2241 expr
= immed_double_const (test
[i
].lo
, test
[i
].hi
, word_mode
);
2242 expr
= expand_binop (word_mode
, and_optab
, index
, expr
,
2243 NULL_RTX
, 1, OPTAB_WIDEN
);
2244 emit_cmp_and_jump_insns (expr
, const0_rtx
, NE
, NULL_RTX
,
2245 word_mode
, 1, test
[i
].label
);
2249 emit_jump (default_label
);
2253 #define HAVE_casesi 0
2256 #ifndef HAVE_tablejump
2257 #define HAVE_tablejump 0
2260 /* Return true if a switch should be expanded as a bit test.
2261 INDEX_EXPR is the index expression, RANGE is the difference between
2262 highest and lowest case, UNIQ is number of unique case node targets
2263 not counting the default case and COUNT is the number of comparisons
2264 needed, not counting the default case. */
2266 expand_switch_using_bit_tests_p (tree index_expr
, tree range
,
2267 unsigned int uniq
, unsigned int count
)
2269 return (CASE_USE_BIT_TESTS
2270 && ! TREE_CONSTANT (index_expr
)
2271 && compare_tree_int (range
, GET_MODE_BITSIZE (word_mode
)) < 0
2272 && compare_tree_int (range
, 0) > 0
2273 && lshift_cheap_p ()
2274 && ((uniq
== 1 && count
>= 3)
2275 || (uniq
== 2 && count
>= 5)
2276 || (uniq
== 3 && count
>= 6)));
2279 #define case_probability(x, y) ((y) ? ((x) * REG_BR_PROB_BASE / (y)) : -1)
2281 /* Terminate a case (Pascal/Ada) or switch (C) statement
2282 in which ORIG_INDEX is the expression to be tested.
2283 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
2284 type as given in the source before any compiler conversions.
2285 Generate the code to test it and jump to the right place. */
2288 expand_case (gimple stmt
)
2290 tree minval
= NULL_TREE
, maxval
= NULL_TREE
, range
= NULL_TREE
;
2291 rtx default_label
= 0;
2292 struct case_node
*n
;
2293 unsigned int count
, uniq
;
2299 rtx before_case
, end
, lab
;
2301 tree index_expr
= gimple_switch_index (stmt
);
2302 tree index_type
= TREE_TYPE (index_expr
);
2303 int unsignedp
= TYPE_UNSIGNED (index_type
);
2304 basic_block bb
= gimple_bb (stmt
);
2306 /* The insn after which the case dispatch should finally
2307 be emitted. Zero for a dummy. */
2310 /* A list of case labels; it is first built as a list and it may then
2311 be rearranged into a nearly balanced binary tree. */
2312 struct case_node
*case_list
= 0;
2314 /* Label to jump to if no case matches. */
2315 tree default_label_decl
= NULL_TREE
;
2317 gcov_type default_count
= 0;
2319 alloc_pool case_node_pool
= create_alloc_pool ("struct case_node pool",
2320 sizeof (struct case_node
),
2323 do_pending_stack_adjust ();
2325 /* An ERROR_MARK occurs for various reasons including invalid data type. */
2326 if (index_type
!= error_mark_node
)
2329 bitmap label_bitmap
;
2330 edge case_edge
= NULL
, default_edge
= NULL
;
2332 bool has_gaps
= false;
2334 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
2335 expressions being INTEGER_CST. */
2336 gcc_assert (TREE_CODE (index_expr
) != INTEGER_CST
);
2338 /* The default case, if ever taken, is the first element. */
2339 elt
= gimple_switch_label (stmt
, 0);
2340 if (!CASE_LOW (elt
) && !CASE_HIGH (elt
))
2342 default_label_decl
= CASE_LABEL (elt
);
2343 case_edge
= EDGE_SUCC(bb
, 0);
2344 default_edge
= case_edge
;
2345 default_count
= case_edge
->count
;
2349 for (i
= gimple_switch_num_labels (stmt
) - 1; i
>= stopi
; --i
)
2352 basic_block case_bb
;
2354 elt
= gimple_switch_label (stmt
, i
);
2356 low
= CASE_LOW (elt
);
2358 high
= CASE_HIGH (elt
);
2360 /* Discard empty ranges. */
2361 if (high
&& tree_int_cst_lt (high
, low
))
2363 case_bb
= label_to_block (CASE_LABEL(elt
));
2364 case_edge
= find_edge (bb
, case_bb
);
2365 case_list
= add_case_node (case_list
, index_type
, low
, high
,
2366 CASE_LABEL (elt
), case_edge
->count
,
2371 before_case
= start
= get_last_insn ();
2372 if (default_label_decl
)
2373 default_label
= label_rtx (default_label_decl
);
2375 /* Get upper and lower bounds of case values. */
2379 label_bitmap
= BITMAP_ALLOC (NULL
);
2380 for (n
= case_list
; n
; n
= n
->right
)
2382 /* Count the elements and track the largest and smallest
2383 of them (treating them as signed even if they are not). */
2391 tree min_minus_one
= fold_build2 (MINUS_EXPR
, index_type
,
2393 build_int_cst (index_type
, 1));
2394 /* case_list is sorted in increasing order. If the minval - 1 of
2395 this node is greater than the previous maxval, then there is a
2396 gap. If jump table expansion is used, this gap will be filled
2397 with the default label. */
2398 if (tree_int_cst_lt (maxval
, min_minus_one
))
2400 if (tree_int_cst_lt (n
->low
, minval
))
2402 if (tree_int_cst_lt (maxval
, n
->high
))
2405 /* A range counts double, since it requires two compares. */
2406 if (! tree_int_cst_equal (n
->low
, n
->high
))
2409 /* If we have not seen this label yet, then increase the
2410 number of unique case node targets seen. */
2411 lab
= label_rtx (n
->code_label
);
2412 if (bitmap_set_bit (label_bitmap
, CODE_LABEL_NUMBER (lab
)))
2416 BITMAP_FREE (label_bitmap
);
2418 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
2419 destination, such as one with a default case only. However,
2420 it doesn't remove cases that are out of range for the switch
2421 type, so we may still get a zero here. */
2425 emit_jump (default_label
);
2426 free_alloc_pool (case_node_pool
);
2430 /* Compute span of values. */
2431 range
= fold_build2 (MINUS_EXPR
, index_type
, maxval
, minval
);
2433 /* Try implementing this switch statement by a short sequence of
2434 bit-wise comparisons. However, we let the binary-tree case
2435 below handle constant index expressions. */
2436 if (expand_switch_using_bit_tests_p (index_expr
, range
, uniq
, count
))
2438 /* Optimize the case where all the case values fit in a
2439 word without having to subtract MINVAL. In this case,
2440 we can optimize away the subtraction. */
2441 if (compare_tree_int (minval
, 0) > 0
2442 && compare_tree_int (maxval
, GET_MODE_BITSIZE (word_mode
)) < 0)
2444 minval
= build_int_cst (index_type
, 0);
2447 emit_case_bit_tests (index_type
, index_expr
, minval
, range
,
2448 case_list
, default_label
);
2451 /* If range of values is much bigger than number of values,
2452 make a sequence of conditional branches instead of a dispatch.
2453 If the switch-index is a constant, do it this way
2454 because we can optimize it. */
2456 else if (count
< targetm
.case_values_threshold ()
2457 || compare_tree_int (range
,
2458 (optimize_insn_for_size_p () ? 3 : 10) * count
) > 0
2459 /* RANGE may be signed, and really large ranges will show up
2460 as negative numbers. */
2461 || compare_tree_int (range
, 0) < 0
2462 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
2465 || !flag_jump_tables
2466 || TREE_CONSTANT (index_expr
)
2467 /* If neither casesi or tablejump is available, we can
2468 only go this way. */
2469 || (!HAVE_casesi
&& !HAVE_tablejump
))
2471 index
= expand_normal (index_expr
);
2473 /* If the index is a short or char that we do not have
2474 an insn to handle comparisons directly, convert it to
2475 a full integer now, rather than letting each comparison
2476 generate the conversion. */
2478 if (GET_MODE_CLASS (GET_MODE (index
)) == MODE_INT
2479 && ! have_insn_for (COMPARE
, GET_MODE (index
)))
2481 enum machine_mode wider_mode
;
2482 for (wider_mode
= GET_MODE (index
); wider_mode
!= VOIDmode
;
2483 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
2484 if (have_insn_for (COMPARE
, wider_mode
))
2486 index
= convert_to_mode (wider_mode
, index
, unsignedp
);
2491 do_pending_stack_adjust ();
2494 index
= copy_to_reg (index
);
2496 /* We generate a binary decision tree to select the
2497 appropriate target code. This is done as follows:
2499 The list of cases is rearranged into a binary tree,
2500 nearly optimal assuming equal probability for each case.
2502 The tree is transformed into RTL, eliminating
2503 redundant test conditions at the same time.
2505 If program flow could reach the end of the
2506 decision tree an unconditional jump to the
2507 default code is emitted. */
2509 use_cost_table
= estimate_case_costs (case_list
);
2510 balance_case_nodes (&case_list
, NULL
);
2511 emit_case_nodes (index
, case_list
, default_label
, default_count
,
2514 emit_jump (default_label
);
2518 rtx fallback_label
= label_rtx (case_list
->code_label
);
2521 gcov_type count
= bb
->count
;
2522 table_label
= gen_label_rtx ();
2523 if (! try_casesi (index_type
, index_expr
, minval
, range
,
2524 table_label
, default_label
, fallback_label
))
2527 int default_probability
;
2529 /* Index jumptables from zero for suitable values of
2530 minval to avoid a subtraction. */
2531 if (optimize_insn_for_speed_p ()
2532 && compare_tree_int (minval
, 0) > 0
2533 && compare_tree_int (minval
, 3) < 0)
2535 minval
= build_int_cst (index_type
, 0);
2541 /* There is at least one entry in the jump table that jumps
2542 to default label. The default label can either be reached
2543 through the indirect jump or the direct conditional jump
2544 before that. Split the probability of reaching the
2545 default label among these two jumps. */
2546 default_probability
= case_probability (default_count
/2,
2549 count
-= default_count
;
2553 default_probability
= case_probability (default_count
,
2555 count
-= default_count
;
2559 ok
= try_tablejump (index_type
, index_expr
, minval
, range
,
2560 table_label
, default_label
,
2561 default_probability
);
2566 default_edge
->count
= default_count
;
2568 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2569 e
->probability
= e
->count
* REG_BR_PROB_BASE
/ count
;
2572 /* Get table of labels to jump to, in order of case index. */
2574 ncases
= tree_low_cst (range
, 0) + 1;
2575 labelvec
= XALLOCAVEC (rtx
, ncases
);
2576 memset (labelvec
, 0, ncases
* sizeof (rtx
));
2578 for (n
= case_list
; n
; n
= n
->right
)
2580 /* Compute the low and high bounds relative to the minimum
2581 value since that should fit in a HOST_WIDE_INT while the
2582 actual values may not. */
2584 = tree_low_cst (fold_build2 (MINUS_EXPR
, index_type
,
2585 n
->low
, minval
), 1);
2586 HOST_WIDE_INT i_high
2587 = tree_low_cst (fold_build2 (MINUS_EXPR
, index_type
,
2588 n
->high
, minval
), 1);
2591 for (i
= i_low
; i
<= i_high
; i
++)
2593 = gen_rtx_LABEL_REF (Pmode
, label_rtx (n
->code_label
));
2596 /* Fill in the gaps with the default. We may have gaps at
2597 the beginning if we tried to avoid the minval subtraction,
2598 so substitute some label even if the default label was
2599 deemed unreachable. */
2601 default_label
= fallback_label
;
2602 for (i
= 0; i
< ncases
; i
++)
2603 if (labelvec
[i
] == 0)
2604 labelvec
[i
] = gen_rtx_LABEL_REF (Pmode
, default_label
);
2606 /* Output the table. */
2607 emit_label (table_label
);
2609 if (CASE_VECTOR_PC_RELATIVE
|| flag_pic
)
2610 emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE
,
2611 gen_rtx_LABEL_REF (Pmode
, table_label
),
2612 gen_rtvec_v (ncases
, labelvec
),
2613 const0_rtx
, const0_rtx
));
2615 emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE
,
2616 gen_rtvec_v (ncases
, labelvec
)));
2618 /* Record no drop-through after the table. */
2622 before_case
= NEXT_INSN (before_case
);
2623 end
= get_last_insn ();
2624 reorder_insns (before_case
, end
, start
);
2628 free_alloc_pool (case_node_pool
);
2631 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */
2634 do_jump_if_equal (enum machine_mode mode
, rtx op0
, rtx op1
, rtx label
,
2635 int unsignedp
, int prob
)
2637 do_compare_rtx_and_jump (op0
, op1
, EQ
, unsignedp
, mode
,
2638 NULL_RTX
, NULL_RTX
, label
, prob
);
2641 /* Not all case values are encountered equally. This function
2642 uses a heuristic to weight case labels, in cases where that
2643 looks like a reasonable thing to do.
2645 Right now, all we try to guess is text, and we establish the
2648 chars above space: 16
2657 If we find any cases in the switch that are not either -1 or in the range
2658 of valid ASCII characters, or are control characters other than those
2659 commonly used with "\", don't treat this switch scanning text.
2661 Return 1 if these nodes are suitable for cost estimation, otherwise
2665 estimate_case_costs (case_node_ptr node
)
2667 tree min_ascii
= integer_minus_one_node
;
2668 tree max_ascii
= build_int_cst (TREE_TYPE (node
->high
), 127);
2672 /* If we haven't already made the cost table, make it now. Note that the
2673 lower bound of the table is -1, not zero. */
2675 if (! cost_table_initialized
)
2677 cost_table_initialized
= 1;
2679 for (i
= 0; i
< 128; i
++)
2682 COST_TABLE (i
) = 16;
2683 else if (ISPUNCT (i
))
2685 else if (ISCNTRL (i
))
2686 COST_TABLE (i
) = -1;
2689 COST_TABLE (' ') = 8;
2690 COST_TABLE ('\t') = 4;
2691 COST_TABLE ('\0') = 4;
2692 COST_TABLE ('\n') = 2;
2693 COST_TABLE ('\f') = 1;
2694 COST_TABLE ('\v') = 1;
2695 COST_TABLE ('\b') = 1;
2698 /* See if all the case expressions look like text. It is text if the
2699 constant is >= -1 and the highest constant is <= 127. Do all comparisons
2700 as signed arithmetic since we don't want to ever access cost_table with a
2701 value less than -1. Also check that none of the constants in a range
2702 are strange control characters. */
2704 for (n
= node
; n
; n
= n
->right
)
2706 if (tree_int_cst_lt (n
->low
, min_ascii
)
2707 || tree_int_cst_lt (max_ascii
, n
->high
))
2710 for (i
= (HOST_WIDE_INT
) TREE_INT_CST_LOW (n
->low
);
2711 i
<= (HOST_WIDE_INT
) TREE_INT_CST_LOW (n
->high
); i
++)
2712 if (COST_TABLE (i
) < 0)
2716 /* All interesting values are within the range of interesting
2717 ASCII characters. */
2721 /* Take an ordered list of case nodes
2722 and transform them into a near optimal binary tree,
2723 on the assumption that any target code selection value is as
2724 likely as any other.
2726 The transformation is performed by splitting the ordered
2727 list into two equal sections plus a pivot. The parts are
2728 then attached to the pivot as left and right branches. Each
2729 branch is then transformed recursively. */
2732 balance_case_nodes (case_node_ptr
*head
, case_node_ptr parent
)
2742 gcov_type count
= 0;
2746 /* Count the number of entries on branch. Also count the ranges. */
2750 if (!tree_int_cst_equal (np
->low
, np
->high
))
2754 cost
+= COST_TABLE (TREE_INT_CST_LOW (np
->high
));
2758 cost
+= COST_TABLE (TREE_INT_CST_LOW (np
->low
));
2766 /* Split this list if it is long enough for that to help. */
2771 /* Find the place in the list that bisects the list's total cost,
2772 Here I gets half the total cost. */
2777 /* Skip nodes while their cost does not reach that amount. */
2778 if (!tree_int_cst_equal ((*npp
)->low
, (*npp
)->high
))
2779 i
-= COST_TABLE (TREE_INT_CST_LOW ((*npp
)->high
));
2780 i
-= COST_TABLE (TREE_INT_CST_LOW ((*npp
)->low
));
2783 npp
= &(*npp
)->right
;
2788 /* Leave this branch lopsided, but optimize left-hand
2789 side and fill in `parent' fields for right-hand side. */
2791 np
->parent
= parent
;
2792 np
->subtree_count
= count
;
2793 balance_case_nodes (&np
->left
, np
);
2795 np
->subtree_count
+= np
->left
->subtree_count
;
2797 for (; np
->right
; np
= np
->right
) {
2798 np
->right
->parent
= np
;
2799 (*head
)->subtree_count
+= np
->right
->count
;
2804 /* If there are just three nodes, split at the middle one. */
2806 npp
= &(*npp
)->right
;
2809 /* Find the place in the list that bisects the list's total cost,
2810 where ranges count as 2.
2811 Here I gets half the total cost. */
2812 i
= (i
+ ranges
+ 1) / 2;
2815 /* Skip nodes while their cost does not reach that amount. */
2816 if (!tree_int_cst_equal ((*npp
)->low
, (*npp
)->high
))
2821 npp
= &(*npp
)->right
;
2826 np
->parent
= parent
;
2829 /* Optimize each of the two split parts. */
2830 balance_case_nodes (&np
->left
, np
);
2831 balance_case_nodes (&np
->right
, np
);
2832 np
->subtree_count
= np
->count
;
2834 np
->subtree_count
+= np
->left
->subtree_count
;
2836 np
->subtree_count
+= np
->right
->subtree_count
;
2840 /* Else leave this branch as one level,
2841 but fill in `parent' fields. */
2843 np
->parent
= parent
;
2844 np
->subtree_count
= np
->count
;
2845 for (; np
->right
; np
= np
->right
) {
2846 np
->right
->parent
= np
;
2847 (*head
)->subtree_count
+= np
->right
->subtree_count
;
2853 /* Search the parent sections of the case node tree
2854 to see if a test for the lower bound of NODE would be redundant.
2855 INDEX_TYPE is the type of the index expression.
2857 The instructions to generate the case decision tree are
2858 output in the same order as nodes are processed so it is
2859 known that if a parent node checks the range of the current
2860 node minus one that the current node is bounded at its lower
2861 span. Thus the test would be redundant. */
2864 node_has_low_bound (case_node_ptr node
, tree index_type
)
2867 case_node_ptr pnode
;
2869 /* If the lower bound of this node is the lowest value in the index type,
2870 we need not test it. */
2872 if (tree_int_cst_equal (node
->low
, TYPE_MIN_VALUE (index_type
)))
2875 /* If this node has a left branch, the value at the left must be less
2876 than that at this node, so it cannot be bounded at the bottom and
2877 we need not bother testing any further. */
2882 low_minus_one
= fold_build2 (MINUS_EXPR
, TREE_TYPE (node
->low
),
2884 build_int_cst (TREE_TYPE (node
->low
), 1));
2886 /* If the subtraction above overflowed, we can't verify anything.
2887 Otherwise, look for a parent that tests our value - 1. */
2889 if (! tree_int_cst_lt (low_minus_one
, node
->low
))
2892 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
2893 if (tree_int_cst_equal (low_minus_one
, pnode
->high
))
2899 /* Search the parent sections of the case node tree
2900 to see if a test for the upper bound of NODE would be redundant.
2901 INDEX_TYPE is the type of the index expression.
2903 The instructions to generate the case decision tree are
2904 output in the same order as nodes are processed so it is
2905 known that if a parent node checks the range of the current
2906 node plus one that the current node is bounded at its upper
2907 span. Thus the test would be redundant. */
2910 node_has_high_bound (case_node_ptr node
, tree index_type
)
2913 case_node_ptr pnode
;
2915 /* If there is no upper bound, obviously no test is needed. */
2917 if (TYPE_MAX_VALUE (index_type
) == NULL
)
2920 /* If the upper bound of this node is the highest value in the type
2921 of the index expression, we need not test against it. */
2923 if (tree_int_cst_equal (node
->high
, TYPE_MAX_VALUE (index_type
)))
2926 /* If this node has a right branch, the value at the right must be greater
2927 than that at this node, so it cannot be bounded at the top and
2928 we need not bother testing any further. */
2933 high_plus_one
= fold_build2 (PLUS_EXPR
, TREE_TYPE (node
->high
),
2935 build_int_cst (TREE_TYPE (node
->high
), 1));
2937 /* If the addition above overflowed, we can't verify anything.
2938 Otherwise, look for a parent that tests our value + 1. */
2940 if (! tree_int_cst_lt (node
->high
, high_plus_one
))
2943 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
2944 if (tree_int_cst_equal (high_plus_one
, pnode
->low
))
2950 /* Search the parent sections of the
2951 case node tree to see if both tests for the upper and lower
2952 bounds of NODE would be redundant. */
2955 node_is_bounded (case_node_ptr node
, tree index_type
)
2957 return (node_has_low_bound (node
, index_type
)
2958 && node_has_high_bound (node
, index_type
));
2962 /* Attach a REG_BR_PROB note to the last created RTX instruction if
2963 PROBABILITY is not -1. */
2966 add_prob_note_to_last_insn(int probability
)
2968 if (probability
!= -1)
2970 rtx jump_insn
= get_last_insn();
2971 add_reg_note (jump_insn
, REG_BR_PROB
, GEN_INT (probability
));
2975 /* Emit step-by-step code to select a case for the value of INDEX.
2976 The thus generated decision tree follows the form of the
2977 case-node binary tree NODE, whose nodes represent test conditions.
2978 INDEX_TYPE is the type of the index of the switch.
2980 Care is taken to prune redundant tests from the decision tree
2981 by detecting any boundary conditions already checked by
2982 emitted rtx. (See node_has_high_bound, node_has_low_bound
2983 and node_is_bounded, above.)
2985 Where the test conditions can be shown to be redundant we emit
2986 an unconditional jump to the target code. As a further
2987 optimization, the subordinates of a tree node are examined to
2988 check for bounded nodes. In this case conditional and/or
2989 unconditional jumps as a result of the boundary check for the
2990 current node are arranged to target the subordinates associated
2991 code for out of bound conditions on the current node.
2993 We can assume that when control reaches the code generated here,
2994 the index value has already been compared with the parents
2995 of this node, and determined to be on the same side of each parent
2996 as this node is. Thus, if this node tests for the value 51,
2997 and a parent tested for 52, we don't need to consider
2998 the possibility of a value greater than 51. If another parent
2999 tests for the value 50, then this node need not test anything. */
3002 emit_case_nodes (rtx index
, case_node_ptr node
, rtx default_label
,
3003 int default_count
, tree index_type
)
3005 /* If INDEX has an unsigned type, we must make unsigned branches. */
3006 int unsignedp
= TYPE_UNSIGNED (index_type
);
3008 gcov_type count
= node
->count
, subtree_count
= node
->subtree_count
;
3009 enum machine_mode mode
= GET_MODE (index
);
3010 enum machine_mode imode
= TYPE_MODE (index_type
);
3012 /* Handle indices detected as constant during RTL expansion. */
3013 if (mode
== VOIDmode
)
3016 /* See if our parents have already tested everything for us.
3017 If they have, emit an unconditional jump for this node. */
3018 if (node_is_bounded (node
, index_type
))
3019 emit_jump (label_rtx (node
->code_label
));
3021 else if (tree_int_cst_equal (node
->low
, node
->high
))
3023 probability
= case_probability (count
, subtree_count
+ default_count
);
3024 /* Node is single valued. First see if the index expression matches
3025 this node and then check our children, if any. */
3026 do_jump_if_equal (mode
, index
,
3027 convert_modes (mode
, imode
,
3028 expand_normal (node
->low
),
3030 label_rtx (node
->code_label
), unsignedp
, probability
);
3031 /* Since this case is taken at this point, reduce its weight from
3033 subtree_count
-= count
;
3034 if (node
->right
!= 0 && node
->left
!= 0)
3036 /* This node has children on both sides.
3037 Dispatch to one side or the other
3038 by comparing the index value with this node's value.
3039 If one subtree is bounded, check that one first,
3040 so we can avoid real branches in the tree. */
3042 if (node_is_bounded (node
->right
, index_type
))
3044 emit_cmp_and_jump_insns (index
,
3047 expand_normal (node
->high
),
3049 GT
, NULL_RTX
, mode
, unsignedp
,
3050 label_rtx (node
->right
->code_label
));
3051 probability
= case_probability (node
->right
->count
,
3052 subtree_count
+ default_count
);
3053 add_prob_note_to_last_insn (probability
);
3054 emit_case_nodes (index
, node
->left
, default_label
, default_count
,
3058 else if (node_is_bounded (node
->left
, index_type
))
3060 emit_cmp_and_jump_insns (index
,
3063 expand_normal (node
->high
),
3065 LT
, NULL_RTX
, mode
, unsignedp
,
3066 label_rtx (node
->left
->code_label
));
3067 probability
= case_probability (node
->left
->count
,
3068 subtree_count
+ default_count
);
3069 add_prob_note_to_last_insn (probability
);
3070 emit_case_nodes (index
, node
->right
, default_label
, default_count
, index_type
);
3073 /* If both children are single-valued cases with no
3074 children, finish up all the work. This way, we can save
3075 one ordered comparison. */
3076 else if (tree_int_cst_equal (node
->right
->low
, node
->right
->high
)
3077 && node
->right
->left
== 0
3078 && node
->right
->right
== 0
3079 && tree_int_cst_equal (node
->left
->low
, node
->left
->high
)
3080 && node
->left
->left
== 0
3081 && node
->left
->right
== 0)
3083 /* Neither node is bounded. First distinguish the two sides;
3084 then emit the code for one side at a time. */
3086 /* See if the value matches what the right hand side
3088 probability
= case_probability (node
->right
->count
,
3089 subtree_count
+ default_count
);
3090 do_jump_if_equal (mode
, index
,
3091 convert_modes (mode
, imode
,
3092 expand_normal (node
->right
->low
),
3094 label_rtx (node
->right
->code_label
),
3095 unsignedp
, probability
);
3097 /* See if the value matches what the left hand side
3099 probability
= case_probability (node
->left
->count
,
3100 subtree_count
+ default_count
);
3101 do_jump_if_equal (mode
, index
,
3102 convert_modes (mode
, imode
,
3103 expand_normal (node
->left
->low
),
3105 label_rtx (node
->left
->code_label
),
3106 unsignedp
, probability
);
3111 /* Neither node is bounded. First distinguish the two sides;
3112 then emit the code for one side at a time. */
3115 = build_decl (CURR_INSN_LOCATION
,
3116 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
3118 /* See if the value is on the right. */
3119 emit_cmp_and_jump_insns (index
,
3122 expand_normal (node
->high
),
3124 GT
, NULL_RTX
, mode
, unsignedp
,
3125 label_rtx (test_label
));
3126 /* The default label could be reached either through the right
3127 subtree or the left subtree. Divide the probability
3129 probability
= case_probability (
3130 node
->right
->subtree_count
+ default_count
/2,
3131 subtree_count
+ default_count
);
3133 add_prob_note_to_last_insn (probability
);
3135 /* Value must be on the left.
3136 Handle the left-hand subtree. */
3137 emit_case_nodes (index
, node
->left
, default_label
, default_count
, index_type
);
3138 /* If left-hand subtree does nothing,
3141 emit_jump (default_label
);
3143 /* Code branches here for the right-hand subtree. */
3144 expand_label (test_label
);
3145 emit_case_nodes (index
, node
->right
, default_label
, default_count
, index_type
);
3149 else if (node
->right
!= 0 && node
->left
== 0)
3151 /* Here we have a right child but no left so we issue a conditional
3152 branch to default and process the right child.
3154 Omit the conditional branch to default if the right child
3155 does not have any children and is single valued; it would
3156 cost too much space to save so little time. */
3158 if (node
->right
->right
|| node
->right
->left
3159 || !tree_int_cst_equal (node
->right
->low
, node
->right
->high
))
3161 if (!node_has_low_bound (node
, index_type
))
3163 emit_cmp_and_jump_insns (index
,
3166 expand_normal (node
->high
),
3168 LT
, NULL_RTX
, mode
, unsignedp
,
3170 probability
= case_probability (default_count
/2,
3171 subtree_count
+ default_count
);
3173 add_prob_note_to_last_insn (probability
);
3176 emit_case_nodes (index
, node
->right
, default_label
, default_count
, index_type
);
3180 probability
= case_probability (node
->right
->subtree_count
,
3181 subtree_count
+ default_count
);
3182 /* We cannot process node->right normally
3183 since we haven't ruled out the numbers less than
3184 this node's value. So handle node->right explicitly. */
3185 do_jump_if_equal (mode
, index
,
3188 expand_normal (node
->right
->low
),
3190 label_rtx (node
->right
->code_label
), unsignedp
, probability
);
3194 else if (node
->right
== 0 && node
->left
!= 0)
3196 /* Just one subtree, on the left. */
3197 if (node
->left
->left
|| node
->left
->right
3198 || !tree_int_cst_equal (node
->left
->low
, node
->left
->high
))
3200 if (!node_has_high_bound (node
, index_type
))
3202 emit_cmp_and_jump_insns (index
,
3205 expand_normal (node
->high
),
3207 GT
, NULL_RTX
, mode
, unsignedp
,
3209 probability
= case_probability (
3210 default_count
/2, subtree_count
+ default_count
);
3212 add_prob_note_to_last_insn (probability
);
3215 emit_case_nodes (index
, node
->left
, default_label
,
3216 default_count
, index_type
);
3220 probability
= case_probability (node
->left
->subtree_count
,
3221 subtree_count
+ default_count
);
3222 /* We cannot process node->left normally
3223 since we haven't ruled out the numbers less than
3224 this node's value. So handle node->left explicitly. */
3225 do_jump_if_equal (mode
, index
,
3228 expand_normal (node
->left
->low
),
3230 label_rtx (node
->left
->code_label
), unsignedp
, probability
);
3236 /* Node is a range. These cases are very similar to those for a single
3237 value, except that we do not start by testing whether this node
3238 is the one to branch to. */
3240 if (node
->right
!= 0 && node
->left
!= 0)
3242 /* Node has subtrees on both sides.
3243 If the right-hand subtree is bounded,
3244 test for it first, since we can go straight there.
3245 Otherwise, we need to make a branch in the control structure,
3246 then handle the two subtrees. */
3247 tree test_label
= 0;
3249 if (node_is_bounded (node
->right
, index_type
))
3251 /* Right hand node is fully bounded so we can eliminate any
3252 testing and branch directly to the target code. */
3253 emit_cmp_and_jump_insns (index
,
3256 expand_normal (node
->high
),
3258 GT
, NULL_RTX
, mode
, unsignedp
,
3259 label_rtx (node
->right
->code_label
));
3260 probability
= case_probability (node
->right
->subtree_count
,
3261 subtree_count
+ default_count
);
3262 add_prob_note_to_last_insn (probability
);
3266 /* Right hand node requires testing.
3267 Branch to a label where we will handle it later. */
3269 test_label
= build_decl (CURR_INSN_LOCATION
,
3270 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
3271 emit_cmp_and_jump_insns (index
,
3274 expand_normal (node
->high
),
3276 GT
, NULL_RTX
, mode
, unsignedp
,
3277 label_rtx (test_label
));
3278 probability
= case_probability (node
->right
->subtree_count
+ default_count
/2,
3279 subtree_count
+ default_count
);
3281 add_prob_note_to_last_insn (probability
);
3284 /* Value belongs to this node or to the left-hand subtree. */
3286 emit_cmp_and_jump_insns (index
,
3289 expand_normal (node
->low
),
3291 GE
, NULL_RTX
, mode
, unsignedp
,
3292 label_rtx (node
->code_label
));
3293 probability
= case_probability (count
, subtree_count
+ default_count
);
3294 add_prob_note_to_last_insn (probability
);
3296 /* Handle the left-hand subtree. */
3297 emit_case_nodes (index
, node
->left
, default_label
, default_count
, index_type
);
3299 /* If right node had to be handled later, do that now. */
3303 /* If the left-hand subtree fell through,
3304 don't let it fall into the right-hand subtree. */
3306 emit_jump (default_label
);
3308 expand_label (test_label
);
3309 emit_case_nodes (index
, node
->right
, default_label
, default_count
, index_type
);
3313 else if (node
->right
!= 0 && node
->left
== 0)
3315 /* Deal with values to the left of this node,
3316 if they are possible. */
3317 if (!node_has_low_bound (node
, index_type
))
3319 emit_cmp_and_jump_insns (index
,
3322 expand_normal (node
->low
),
3324 LT
, NULL_RTX
, mode
, unsignedp
,
3326 probability
= case_probability (default_count
/2,
3327 subtree_count
+ default_count
);
3329 add_prob_note_to_last_insn (probability
);
3332 /* Value belongs to this node or to the right-hand subtree. */
3334 emit_cmp_and_jump_insns (index
,
3337 expand_normal (node
->high
),
3339 LE
, NULL_RTX
, mode
, unsignedp
,
3340 label_rtx (node
->code_label
));
3341 probability
= case_probability (count
, subtree_count
+ default_count
);
3342 add_prob_note_to_last_insn (probability
);
3344 emit_case_nodes (index
, node
->right
, default_label
, default_count
, index_type
);
3347 else if (node
->right
== 0 && node
->left
!= 0)
3349 /* Deal with values to the right of this node,
3350 if they are possible. */
3351 if (!node_has_high_bound (node
, index_type
))
3353 emit_cmp_and_jump_insns (index
,
3356 expand_normal (node
->high
),
3358 GT
, NULL_RTX
, mode
, unsignedp
,
3360 probability
= case_probability (default_count
/2,
3361 subtree_count
+ default_count
);
3363 add_prob_note_to_last_insn (probability
);
3366 /* Value belongs to this node or to the left-hand subtree. */
3368 emit_cmp_and_jump_insns (index
,
3371 expand_normal (node
->low
),
3373 GE
, NULL_RTX
, mode
, unsignedp
,
3374 label_rtx (node
->code_label
));
3375 probability
= case_probability (count
, subtree_count
+ default_count
);
3376 add_prob_note_to_last_insn (probability
);
3378 emit_case_nodes (index
, node
->left
, default_label
, default_count
, index_type
);
3383 /* Node has no children so we check low and high bounds to remove
3384 redundant tests. Only one of the bounds can exist,
3385 since otherwise this node is bounded--a case tested already. */
3386 int high_bound
= node_has_high_bound (node
, index_type
);
3387 int low_bound
= node_has_low_bound (node
, index_type
);
3389 if (!high_bound
&& low_bound
)
3391 emit_cmp_and_jump_insns (index
,
3394 expand_normal (node
->high
),
3396 GT
, NULL_RTX
, mode
, unsignedp
,
3398 probability
= case_probability (default_count
,
3399 subtree_count
+ default_count
);
3400 add_prob_note_to_last_insn (probability
);
3403 else if (!low_bound
&& high_bound
)
3405 emit_cmp_and_jump_insns (index
,
3408 expand_normal (node
->low
),
3410 LT
, NULL_RTX
, mode
, unsignedp
,
3412 probability
= case_probability (default_count
,
3413 subtree_count
+ default_count
);
3414 add_prob_note_to_last_insn (probability
);
3416 else if (!low_bound
&& !high_bound
)
3418 /* Widen LOW and HIGH to the same width as INDEX. */
3419 tree type
= lang_hooks
.types
.type_for_mode (mode
, unsignedp
);
3420 tree low
= build1 (CONVERT_EXPR
, type
, node
->low
);
3421 tree high
= build1 (CONVERT_EXPR
, type
, node
->high
);
3422 rtx low_rtx
, new_index
, new_bound
;
3424 /* Instead of doing two branches, emit one unsigned branch for
3425 (index-low) > (high-low). */
3426 low_rtx
= expand_expr (low
, NULL_RTX
, mode
, EXPAND_NORMAL
);
3427 new_index
= expand_simple_binop (mode
, MINUS
, index
, low_rtx
,
3428 NULL_RTX
, unsignedp
,
3430 new_bound
= expand_expr (fold_build2 (MINUS_EXPR
, type
,
3432 NULL_RTX
, mode
, EXPAND_NORMAL
);
3434 emit_cmp_and_jump_insns (new_index
, new_bound
, GT
, NULL_RTX
,
3435 mode
, 1, default_label
);
3436 probability
= case_probability (default_count
,
3437 subtree_count
+ default_count
);
3438 add_prob_note_to_last_insn (probability
);
3441 emit_jump (label_rtx (node
->code_label
));