1 /* Expands front end tree to back end RTL for GCC
2 Copyright (C) 1987-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file handles the generation of rtl code from tree structure
21 above the level of expressions, using subroutines in exp*.c and emit-rtl.c.
22 The functions whose names start with `expand_' are called by the
23 expander to generate RTL instructions for various kinds of constructs. */
27 #include "coretypes.h"
40 #include "pretty-print.h"
41 #include "diagnostic-core.h"
43 #include "fold-const.h"
45 #include "stor-layout.h"
50 #include "langhooks.h"
57 /* Functions and data structures for expanding case statements. */
59 /* Case label structure, used to hold info on labels within case
60 statements. We handle "range" labels; for a single-value label
61 as in C, the high and low limits are the same.
63 We start with a vector of case nodes sorted in ascending order, and
64 the default label as the last element in the vector.
66 Switch statements are expanded in jump table form.
70 class simple_case_node
73 simple_case_node (tree low
, tree high
, tree code_label
):
74 m_low (low
), m_high (high
), m_code_label (code_label
)
77 /* Lowest index value for this label. */
79 /* Highest index value for this label. */
81 /* Label to jump to when node matches. */
85 static bool check_unique_operand_names (tree
, tree
, tree
);
86 static char *resolve_operand_name_1 (char *, tree
, tree
, tree
);
88 /* Return the rtx-label that corresponds to a LABEL_DECL,
89 creating it if necessary. */
92 label_rtx (tree label
)
94 gcc_assert (TREE_CODE (label
) == LABEL_DECL
);
96 if (!DECL_RTL_SET_P (label
))
98 rtx_code_label
*r
= gen_label_rtx ();
99 SET_DECL_RTL (label
, r
);
100 if (FORCED_LABEL (label
) || DECL_NONLOCAL (label
))
101 LABEL_PRESERVE_P (r
) = 1;
104 return as_a
<rtx_insn
*> (DECL_RTL (label
));
107 /* As above, but also put it on the forced-reference list of the
108 function that contains it. */
110 force_label_rtx (tree label
)
112 rtx_insn
*ref
= label_rtx (label
);
113 tree function
= decl_function_context (label
);
115 gcc_assert (function
);
117 vec_safe_push (forced_labels
, ref
);
121 /* As label_rtx, but ensures (in check build), that returned value is
122 an existing label (i.e. rtx with code CODE_LABEL). */
124 jump_target_rtx (tree label
)
126 return as_a
<rtx_code_label
*> (label_rtx (label
));
129 /* Add an unconditional jump to LABEL as the next sequential instruction. */
132 emit_jump (rtx label
)
134 do_pending_stack_adjust ();
135 emit_jump_insn (targetm
.gen_jump (label
));
139 /* Handle goto statements and the labels that they can go to. */
141 /* Specify the location in the RTL code of a label LABEL,
142 which is a LABEL_DECL tree node.
144 This is used for the kind of label that the user can jump to with a
145 goto statement, and for alternatives of a switch or case statement.
146 RTL labels generated for loops and conditionals don't go through here;
147 they are generated directly at the RTL level, by other functions below.
149 Note that this has nothing to do with defining label *names*.
150 Languages vary in how they do that and what that even means. */
153 expand_label (tree label
)
155 rtx_code_label
*label_r
= jump_target_rtx (label
);
157 do_pending_stack_adjust ();
158 emit_label (label_r
);
159 if (DECL_NAME (label
))
160 LABEL_NAME (DECL_RTL (label
)) = IDENTIFIER_POINTER (DECL_NAME (label
));
162 if (DECL_NONLOCAL (label
))
164 expand_builtin_setjmp_receiver (NULL
);
165 nonlocal_goto_handler_labels
166 = gen_rtx_INSN_LIST (VOIDmode
, label_r
,
167 nonlocal_goto_handler_labels
);
170 if (FORCED_LABEL (label
))
171 vec_safe_push
<rtx_insn
*> (forced_labels
, label_r
);
173 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
174 maybe_set_first_label_num (label_r
);
177 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
178 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
179 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
180 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
181 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
182 constraint allows the use of a register operand. And, *IS_INOUT
183 will be true if the operand is read-write, i.e., if it is used as
184 an input as well as an output. If *CONSTRAINT_P is not in
185 canonical form, it will be made canonical. (Note that `+' will be
186 replaced with `=' as part of this process.)
188 Returns TRUE if all went well; FALSE if an error occurred. */
191 parse_output_constraint (const char **constraint_p
, int operand_num
,
192 int ninputs
, int noutputs
, bool *allows_mem
,
193 bool *allows_reg
, bool *is_inout
)
195 const char *constraint
= *constraint_p
;
198 /* Assume the constraint doesn't allow the use of either a register
203 /* Allow the `=' or `+' to not be at the beginning of the string,
204 since it wasn't explicitly documented that way, and there is a
205 large body of code that puts it last. Swap the character to
206 the front, so as not to uglify any place else. */
207 p
= strchr (constraint
, '=');
209 p
= strchr (constraint
, '+');
211 /* If the string doesn't contain an `=', issue an error
215 error ("output operand constraint lacks %<=%>");
219 /* If the constraint begins with `+', then the operand is both read
220 from and written to. */
221 *is_inout
= (*p
== '+');
223 /* Canonicalize the output constraint so that it begins with `='. */
224 if (p
!= constraint
|| *is_inout
)
227 size_t c_len
= strlen (constraint
);
230 warning (0, "output constraint %qc for operand %d "
231 "is not at the beginning",
234 /* Make a copy of the constraint. */
235 buf
= XALLOCAVEC (char, c_len
+ 1);
236 strcpy (buf
, constraint
);
237 /* Swap the first character and the `=' or `+'. */
238 buf
[p
- constraint
] = buf
[0];
239 /* Make sure the first character is an `='. (Until we do this,
240 it might be a `+'.) */
242 /* Replace the constraint with the canonicalized string. */
243 *constraint_p
= ggc_alloc_string (buf
, c_len
);
244 constraint
= *constraint_p
;
247 /* Loop through the constraint string. */
248 for (p
= constraint
+ 1; *p
; )
254 error ("operand constraint contains incorrectly positioned "
259 if (operand_num
+ 1 == ninputs
+ noutputs
)
261 error ("%<%%%> constraint used with last operand");
266 case '?': case '!': case '*': case '&': case '#':
268 case 'E': case 'F': case 'G': case 'H':
269 case 's': case 'i': case 'n':
270 case 'I': case 'J': case 'K': case 'L': case 'M':
271 case 'N': case 'O': case 'P': case ',':
274 case '0': case '1': case '2': case '3': case '4':
275 case '5': case '6': case '7': case '8': case '9':
277 error ("matching constraint not valid in output operand");
281 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
282 excepting those that expand_call created. So match memory
295 enum constraint_num cn
= lookup_constraint (p
);
296 if (reg_class_for_constraint (cn
) != NO_REGS
297 || insn_extra_address_constraint (cn
))
299 else if (insn_extra_memory_constraint (cn
))
302 insn_extra_constraint_allows_reg_mem (cn
, allows_reg
, allows_mem
);
306 for (size_t len
= CONSTRAINT_LEN (*p
, p
); len
; len
--, p
++)
314 /* Similar, but for input constraints. */
317 parse_input_constraint (const char **constraint_p
, int input_num
,
318 int ninputs
, int noutputs
, int ninout
,
319 const char * const * constraints
,
320 bool *allows_mem
, bool *allows_reg
)
322 const char *constraint
= *constraint_p
;
323 const char *orig_constraint
= constraint
;
324 size_t c_len
= strlen (constraint
);
326 bool saw_match
= false;
328 /* Assume the constraint doesn't allow the use of either
329 a register or memory. */
333 /* Make sure constraint has neither `=', `+', nor '&'. */
335 for (j
= 0; j
< c_len
; j
+= CONSTRAINT_LEN (constraint
[j
], constraint
+j
))
336 switch (constraint
[j
])
338 case '+': case '=': case '&':
339 if (constraint
== orig_constraint
)
341 error ("input operand constraint contains %qc", constraint
[j
]);
347 if (constraint
== orig_constraint
348 && input_num
+ 1 == ninputs
- ninout
)
350 error ("%<%%%> constraint used with last operand");
356 case '?': case '!': case '*': case '#':
358 case 'E': case 'F': case 'G': case 'H':
359 case 's': case 'i': case 'n':
360 case 'I': case 'J': case 'K': case 'L': case 'M':
361 case 'N': case 'O': case 'P': case ',':
364 /* Whether or not a numeric constraint allows a register is
365 decided by the matching constraint, and so there is no need
366 to do anything special with them. We must handle them in
367 the default case, so that we don't unnecessarily force
368 operands to memory. */
369 case '0': case '1': case '2': case '3': case '4':
370 case '5': case '6': case '7': case '8': case '9':
377 match
= strtoul (constraint
+ j
, &end
, 10);
378 if (match
>= (unsigned long) noutputs
)
380 error ("matching constraint references invalid operand number");
384 /* Try and find the real constraint for this dup. Only do this
385 if the matching constraint is the only alternative. */
387 && (j
== 0 || (j
== 1 && constraint
[0] == '%')))
389 constraint
= constraints
[match
];
390 *constraint_p
= constraint
;
391 c_len
= strlen (constraint
);
393 /* ??? At the end of the loop, we will skip the first part of
394 the matched constraint. This assumes not only that the
395 other constraint is an output constraint, but also that
396 the '=' or '+' come first. */
400 j
= end
- constraint
;
401 /* Anticipate increment at end of loop. */
412 if (! ISALPHA (constraint
[j
]))
414 error ("invalid punctuation %qc in constraint", constraint
[j
]);
417 enum constraint_num cn
= lookup_constraint (constraint
+ j
);
418 if (reg_class_for_constraint (cn
) != NO_REGS
419 || insn_extra_address_constraint (cn
))
421 else if (insn_extra_memory_constraint (cn
)
422 || insn_extra_special_memory_constraint (cn
))
425 insn_extra_constraint_allows_reg_mem (cn
, allows_reg
, allows_mem
);
429 if (saw_match
&& !*allows_reg
)
430 warning (0, "matching constraint does not allow a register");
435 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
436 can be an asm-declared register. Called via walk_tree. */
439 decl_overlaps_hard_reg_set_p (tree
*declp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
443 const HARD_REG_SET
*const regs
= (const HARD_REG_SET
*) data
;
447 if (DECL_HARD_REGISTER (decl
)
448 && REG_P (DECL_RTL (decl
))
449 && REGNO (DECL_RTL (decl
)) < FIRST_PSEUDO_REGISTER
)
451 rtx reg
= DECL_RTL (decl
);
453 if (overlaps_hard_reg_set_p (*regs
, GET_MODE (reg
), REGNO (reg
)))
458 else if (TYPE_P (decl
) || TREE_CODE (decl
) == PARM_DECL
)
463 /* If there is an overlap between *REGS and DECL, return the first overlap
466 tree_overlaps_hard_reg_set (tree decl
, HARD_REG_SET
*regs
)
468 return walk_tree (&decl
, decl_overlaps_hard_reg_set_p
, regs
, NULL
);
472 /* A subroutine of expand_asm_operands. Check that all operand names
473 are unique. Return true if so. We rely on the fact that these names
474 are identifiers, and so have been canonicalized by get_identifier,
475 so all we need are pointer comparisons. */
478 check_unique_operand_names (tree outputs
, tree inputs
, tree labels
)
480 tree i
, j
, i_name
= NULL_TREE
;
482 for (i
= outputs
; i
; i
= TREE_CHAIN (i
))
484 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
488 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
489 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
493 for (i
= inputs
; i
; i
= TREE_CHAIN (i
))
495 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
499 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
500 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
502 for (j
= outputs
; j
; j
= TREE_CHAIN (j
))
503 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
507 for (i
= labels
; i
; i
= TREE_CHAIN (i
))
509 i_name
= TREE_PURPOSE (i
);
513 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
514 if (simple_cst_equal (i_name
, TREE_PURPOSE (j
)))
516 for (j
= inputs
; j
; j
= TREE_CHAIN (j
))
517 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
524 error ("duplicate %<asm%> operand name %qs", TREE_STRING_POINTER (i_name
));
528 /* Resolve the names of the operands in *POUTPUTS and *PINPUTS to numbers,
529 and replace the name expansions in STRING and in the constraints to
530 those numbers. This is generally done in the front end while creating
531 the ASM_EXPR generic tree that eventually becomes the GIMPLE_ASM. */
534 resolve_asm_operand_names (tree string
, tree outputs
, tree inputs
, tree labels
)
541 check_unique_operand_names (outputs
, inputs
, labels
);
543 /* Substitute [<name>] in input constraint strings. There should be no
544 named operands in output constraints. */
545 for (t
= inputs
; t
; t
= TREE_CHAIN (t
))
547 c
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
548 if (strchr (c
, '[') != NULL
)
550 p
= buffer
= xstrdup (c
);
551 while ((p
= strchr (p
, '[')) != NULL
)
552 p
= resolve_operand_name_1 (p
, outputs
, inputs
, NULL
);
553 TREE_VALUE (TREE_PURPOSE (t
))
554 = build_string (strlen (buffer
), buffer
);
559 /* Now check for any needed substitutions in the template. */
560 c
= TREE_STRING_POINTER (string
);
561 while ((c
= strchr (c
, '%')) != NULL
)
565 else if (ISALPHA (c
[1]) && c
[2] == '[')
569 c
+= 1 + (c
[1] == '%');
576 /* OK, we need to make a copy so we can perform the substitutions.
577 Assume that we will not need extra space--we get to remove '['
578 and ']', which means we cannot have a problem until we have more
579 than 999 operands. */
580 buffer
= xstrdup (TREE_STRING_POINTER (string
));
581 p
= buffer
+ (c
- TREE_STRING_POINTER (string
));
583 while ((p
= strchr (p
, '%')) != NULL
)
587 else if (ISALPHA (p
[1]) && p
[2] == '[')
591 p
+= 1 + (p
[1] == '%');
595 p
= resolve_operand_name_1 (p
, outputs
, inputs
, labels
);
598 string
= build_string (strlen (buffer
), buffer
);
605 /* A subroutine of resolve_operand_names. P points to the '[' for a
606 potential named operand of the form [<name>]. In place, replace
607 the name and brackets with a number. Return a pointer to the
608 balance of the string after substitution. */
611 resolve_operand_name_1 (char *p
, tree outputs
, tree inputs
, tree labels
)
617 /* Collect the operand name. */
618 q
= strchr (++p
, ']');
621 error ("missing close brace for named operand");
622 return strchr (p
, '\0');
626 /* Resolve the name to a number. */
627 for (op_inout
= op
= 0, t
= outputs
; t
; t
= TREE_CHAIN (t
), op
++)
629 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
630 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
632 tree constraint
= TREE_VALUE (TREE_PURPOSE (t
));
633 if (constraint
&& strchr (TREE_STRING_POINTER (constraint
), '+') != NULL
)
636 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), op
++)
638 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
639 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
643 for (t
= labels
; t
; t
= TREE_CHAIN (t
), op
++)
645 tree name
= TREE_PURPOSE (t
);
646 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
650 error ("undefined named operand %qs", identifier_to_locale (p
));
654 /* Replace the name with the number. Unfortunately, not all libraries
655 get the return value of sprintf correct, so search for the end of the
656 generated string by hand. */
657 sprintf (--p
, "%d", op
);
658 p
= strchr (p
, '\0');
660 /* Verify the no extra buffer space assumption. */
663 /* Shift the rest of the buffer down to fill the gap. */
664 memmove (p
, q
+ 1, strlen (q
+ 1) + 1);
670 /* Generate RTL to return directly from the current function.
671 (That is, we bypass any return value.) */
674 expand_naked_return (void)
676 rtx_code_label
*end_label
;
678 clear_pending_stack_adjust ();
679 do_pending_stack_adjust ();
681 end_label
= naked_return_label
;
683 end_label
= naked_return_label
= gen_label_rtx ();
685 emit_jump (end_label
);
688 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
689 is the probability of jumping to LABEL. */
691 do_jump_if_equal (machine_mode mode
, rtx op0
, rtx op1
, rtx_code_label
*label
,
692 int unsignedp
, profile_probability prob
)
694 do_compare_rtx_and_jump (op0
, op1
, EQ
, unsignedp
, mode
,
695 NULL_RTX
, NULL
, label
, prob
);
698 /* Return the sum of probabilities of outgoing edges of basic block BB. */
700 static profile_probability
701 get_outgoing_edge_probs (basic_block bb
)
705 profile_probability prob_sum
= profile_probability::never ();
707 return profile_probability::never ();
708 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
709 prob_sum
+= e
->probability
;
713 /* Computes the conditional probability of jumping to a target if the branch
714 instruction is executed.
715 TARGET_PROB is the estimated probability of jumping to a target relative
716 to some basic block BB.
717 BASE_PROB is the probability of reaching the branch instruction relative
718 to the same basic block BB. */
720 static inline profile_probability
721 conditional_probability (profile_probability target_prob
,
722 profile_probability base_prob
)
724 return target_prob
/ base_prob
;
727 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
728 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
729 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
730 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
732 First, a jump insn is emitted. First we try "casesi". If that
733 fails, try "tablejump". A target *must* have one of them (or both).
735 Then, a table with the target labels is emitted.
737 The process is unaware of the CFG. The caller has to fix up
738 the CFG itself. This is done in cfgexpand.c. */
741 emit_case_dispatch_table (tree index_expr
, tree index_type
,
742 auto_vec
<simple_case_node
> &case_list
,
744 edge default_edge
, tree minval
, tree maxval
,
745 tree range
, basic_block stmt_bb
)
749 rtx_insn
*fallback_label
= label_rtx (case_list
[0].m_code_label
);
750 rtx_code_label
*table_label
= gen_label_rtx ();
751 bool has_gaps
= false;
752 profile_probability default_prob
= default_edge
? default_edge
->probability
753 : profile_probability::never ();
754 profile_probability base
= get_outgoing_edge_probs (stmt_bb
);
755 bool try_with_tablejump
= false;
757 profile_probability new_default_prob
= conditional_probability (default_prob
,
760 if (! try_casesi (index_type
, index_expr
, minval
, range
,
761 table_label
, default_label
, fallback_label
,
764 /* Index jumptables from zero for suitable values of minval to avoid
765 a subtraction. For the rationale see:
766 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
767 if (optimize_insn_for_speed_p ()
768 && compare_tree_int (minval
, 0) > 0
769 && compare_tree_int (minval
, 3) < 0)
771 minval
= build_int_cst (index_type
, 0);
775 try_with_tablejump
= true;
778 /* Get table of labels to jump to, in order of case index. */
780 ncases
= tree_to_shwi (range
) + 1;
781 labelvec
= XALLOCAVEC (rtx
, ncases
);
782 memset (labelvec
, 0, ncases
* sizeof (rtx
));
784 for (unsigned j
= 0; j
< case_list
.length (); j
++)
786 simple_case_node
*n
= &case_list
[j
];
787 /* Compute the low and high bounds relative to the minimum
788 value since that should fit in a HOST_WIDE_INT while the
789 actual values may not. */
791 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
794 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
798 for (i
= i_low
; i
<= i_high
; i
++)
800 = gen_rtx_LABEL_REF (Pmode
, label_rtx (n
->m_code_label
));
803 /* The dispatch table may contain gaps, including at the beginning of
804 the table if we tried to avoid the minval subtraction. We fill the
805 dispatch table slots associated with the gaps with the default case label.
806 However, in the event the default case is unreachable, we then use
807 any label from one of the case statements. */
808 rtx gap_label
= (default_label
) ? default_label
: fallback_label
;
810 for (i
= 0; i
< ncases
; i
++)
811 if (labelvec
[i
] == 0)
814 labelvec
[i
] = gen_rtx_LABEL_REF (Pmode
, gap_label
);
817 if (has_gaps
&& default_label
)
819 /* There is at least one entry in the jump table that jumps
820 to default label. The default label can either be reached
821 through the indirect jump or the direct conditional jump
822 before that. Split the probability of reaching the
823 default label among these two jumps. */
825 = conditional_probability (default_prob
.apply_scale (1, 2), base
);
826 default_prob
= default_prob
.apply_scale (1, 2);
827 base
-= default_prob
;
831 base
-= default_prob
;
832 default_prob
= profile_probability::never ();
836 default_edge
->probability
= default_prob
;
838 /* We have altered the probability of the default edge. So the probabilities
839 of all other edges need to be adjusted so that it sums up to
841 if (base
> profile_probability::never ())
845 FOR_EACH_EDGE (e
, ei
, stmt_bb
->succs
)
846 e
->probability
/= base
;
849 if (try_with_tablejump
)
851 bool ok
= try_tablejump (index_type
, index_expr
, minval
, range
,
852 table_label
, default_label
, new_default_prob
);
855 /* Output the table. */
856 emit_label (table_label
);
858 if (CASE_VECTOR_PC_RELATIVE
859 || (flag_pic
&& targetm
.asm_out
.generate_pic_addr_diff_vec ()))
860 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE
,
861 gen_rtx_LABEL_REF (Pmode
,
863 gen_rtvec_v (ncases
, labelvec
),
864 const0_rtx
, const0_rtx
));
866 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE
,
867 gen_rtvec_v (ncases
, labelvec
)));
869 /* Record no drop-through after the table. */
873 /* Terminate a case Ada or switch (C) statement
874 in which ORIG_INDEX is the expression to be tested.
875 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
876 type as given in the source before any compiler conversions.
877 Generate the code to test it and jump to the right place. */
880 expand_case (gswitch
*stmt
)
882 tree minval
= NULL_TREE
, maxval
= NULL_TREE
, range
= NULL_TREE
;
883 rtx_code_label
*default_label
;
886 int ncases
= gimple_switch_num_labels (stmt
);
887 tree index_expr
= gimple_switch_index (stmt
);
888 tree index_type
= TREE_TYPE (index_expr
);
890 basic_block bb
= gimple_bb (stmt
);
893 auto_vec
<simple_case_node
> case_list
;
895 /* An ERROR_MARK occurs for various reasons including invalid data type.
896 ??? Can this still happen, with GIMPLE and all? */
897 if (index_type
== error_mark_node
)
900 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
901 expressions being INTEGER_CST. */
902 gcc_assert (TREE_CODE (index_expr
) != INTEGER_CST
);
904 /* Optimization of switch statements with only one label has already
905 occurred, so we should never see them at this point. */
906 gcc_assert (ncases
> 1);
908 do_pending_stack_adjust ();
910 /* Find the default case target label. */
911 tree default_lab
= CASE_LABEL (gimple_switch_default_label (stmt
));
912 default_label
= jump_target_rtx (default_lab
);
913 basic_block default_bb
= label_to_block (cfun
, default_lab
);
914 edge default_edge
= find_edge (bb
, default_bb
);
916 /* Get upper and lower bounds of case values. */
917 elt
= gimple_switch_label (stmt
, 1);
918 minval
= fold_convert (index_type
, CASE_LOW (elt
));
919 elt
= gimple_switch_label (stmt
, ncases
- 1);
921 maxval
= fold_convert (index_type
, CASE_HIGH (elt
));
923 maxval
= fold_convert (index_type
, CASE_LOW (elt
));
925 /* Try to narrow the index type if it's larger than a word.
926 That is mainly for -O0 where an equivalent optimization
927 done by forward propagation is not run and is aimed at
928 avoiding a call to a comparison routine of libgcc. */
929 if (TYPE_PRECISION (index_type
) > BITS_PER_WORD
930 && TREE_CODE (index_expr
) == SSA_NAME
931 && (def_stmt
= SSA_NAME_DEF_STMT (index_expr
))
932 && is_gimple_assign (def_stmt
)
933 && gimple_assign_rhs_code (def_stmt
) == NOP_EXPR
)
935 tree inner_index_expr
= gimple_assign_rhs1 (def_stmt
);
936 tree inner_index_type
= TREE_TYPE (inner_index_expr
);
938 if (INTEGRAL_TYPE_P (inner_index_type
)
939 && TYPE_PRECISION (inner_index_type
) <= BITS_PER_WORD
940 && int_fits_type_p (minval
, inner_index_type
)
941 && int_fits_type_p (maxval
, inner_index_type
))
943 index_expr
= inner_index_expr
;
944 index_type
= inner_index_type
;
945 minval
= fold_convert (index_type
, minval
);
946 maxval
= fold_convert (index_type
, maxval
);
950 /* Compute span of values. */
951 range
= fold_build2 (MINUS_EXPR
, index_type
, maxval
, minval
);
953 /* Listify the labels queue and gather some numbers to decide
954 how to expand this switch(). */
957 for (i
= ncases
- 1; i
>= 1; --i
)
959 elt
= gimple_switch_label (stmt
, i
);
960 tree low
= CASE_LOW (elt
);
962 tree high
= CASE_HIGH (elt
);
963 gcc_assert (! high
|| tree_int_cst_lt (low
, high
));
964 tree lab
= CASE_LABEL (elt
);
966 /* Count the elements.
967 A range counts double, since it requires two compares. */
972 /* The bounds on the case range, LOW and HIGH, have to be converted
973 to case's index type TYPE. Note that the original type of the
974 case index in the source code is usually "lost" during
975 gimplification due to type promotion, but the case labels retain the
976 original type. Make sure to drop overflow flags. */
977 low
= fold_convert (index_type
, low
);
978 if (TREE_OVERFLOW (low
))
979 low
= wide_int_to_tree (index_type
, wi::to_wide (low
));
981 /* The canonical from of a case label in GIMPLE is that a simple case
982 has an empty CASE_HIGH. For the casesi and tablejump expanders,
983 the back ends want simple cases to have high == low. */
986 high
= fold_convert (index_type
, high
);
987 if (TREE_OVERFLOW (high
))
988 high
= wide_int_to_tree (index_type
, wi::to_wide (high
));
990 case_list
.safe_push (simple_case_node (low
, high
, lab
));
993 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
994 destination, such as one with a default case only.
995 It also removes cases that are out of range for the switch
996 type, so we should never get a zero here. */
997 gcc_assert (count
> 0);
999 rtx_insn
*before_case
= get_last_insn ();
1001 /* If the default case is unreachable, then set default_label to NULL
1002 so that we omit the range check when generating the dispatch table.
1003 We also remove the edge to the unreachable default case. The block
1004 itself will be automatically removed later. */
1005 if (EDGE_COUNT (default_edge
->dest
->succs
) == 0
1006 && gimple_seq_unreachable_p (bb_seq (default_edge
->dest
)))
1008 default_label
= NULL
;
1009 remove_edge (default_edge
);
1010 default_edge
= NULL
;
1013 emit_case_dispatch_table (index_expr
, index_type
,
1014 case_list
, default_label
, default_edge
,
1015 minval
, maxval
, range
, bb
);
1017 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1022 /* Expand the dispatch to a short decrement chain if there are few cases
1023 to dispatch to. Likewise if neither casesi nor tablejump is available,
1024 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
1025 tablejump. The index mode is always the mode of integer_type_node.
1026 Trap if no case matches the index.
1028 DISPATCH_INDEX is the index expression to switch on. It should be a
1029 memory or register operand.
1031 DISPATCH_TABLE is a set of case labels. The set should be sorted in
1032 ascending order, be contiguous, starting with value 0, and contain only
1033 single-valued case labels. */
1036 expand_sjlj_dispatch_table (rtx dispatch_index
,
1037 vec
<tree
> dispatch_table
)
1039 tree index_type
= integer_type_node
;
1040 machine_mode index_mode
= TYPE_MODE (index_type
);
1042 int ncases
= dispatch_table
.length ();
1044 do_pending_stack_adjust ();
1045 rtx_insn
*before_case
= get_last_insn ();
1047 /* Expand as a decrement-chain if there are 5 or fewer dispatch
1048 labels. This covers more than 98% of the cases in libjava,
1049 and seems to be a reasonable compromise between the "old way"
1050 of expanding as a decision tree or dispatch table vs. the "new
1051 way" with decrement chain or dispatch table. */
1052 if (dispatch_table
.length () <= 5
1053 || (!targetm
.have_casesi () && !targetm
.have_tablejump ())
1054 || !flag_jump_tables
)
1056 /* Expand the dispatch as a decrement chain:
1058 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1062 if (index == 0) do_0; else index--;
1063 if (index == 0) do_1; else index--;
1065 if (index == 0) do_N; else index--;
1067 This is more efficient than a dispatch table on most machines.
1068 The last "index--" is redundant but the code is trivially dead
1069 and will be cleaned up by later passes. */
1070 rtx index
= copy_to_mode_reg (index_mode
, dispatch_index
);
1071 rtx zero
= CONST0_RTX (index_mode
);
1072 for (int i
= 0; i
< ncases
; i
++)
1074 tree elt
= dispatch_table
[i
];
1075 rtx_code_label
*lab
= jump_target_rtx (CASE_LABEL (elt
));
1076 do_jump_if_equal (index_mode
, index
, zero
, lab
, 0,
1077 profile_probability::uninitialized ());
1078 force_expand_binop (index_mode
, sub_optab
,
1079 index
, CONST1_RTX (index_mode
),
1080 index
, 0, OPTAB_DIRECT
);
1085 /* Similar to expand_case, but much simpler. */
1086 auto_vec
<simple_case_node
> case_list
;
1087 tree index_expr
= make_tree (index_type
, dispatch_index
);
1088 tree minval
= build_int_cst (index_type
, 0);
1089 tree maxval
= CASE_LOW (dispatch_table
.last ());
1090 tree range
= maxval
;
1091 rtx_code_label
*default_label
= gen_label_rtx ();
1093 for (int i
= ncases
- 1; i
>= 0; --i
)
1095 tree elt
= dispatch_table
[i
];
1096 tree high
= CASE_HIGH (elt
);
1097 if (high
== NULL_TREE
)
1098 high
= CASE_LOW (elt
);
1099 case_list
.safe_push (simple_case_node (CASE_LOW (elt
), high
,
1103 emit_case_dispatch_table (index_expr
, index_type
,
1104 case_list
, default_label
, NULL
,
1105 minval
, maxval
, range
,
1106 BLOCK_FOR_INSN (before_case
));
1107 emit_label (default_label
);
1110 /* Dispatching something not handled? Trap! */
1111 expand_builtin_trap ();
1113 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);