1/* Expands front end tree to back end RTL for GCC
2 Copyright (C) 1987-2023 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
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.cc.
22 The functions whose names start with `expand_' are called by the
23 expander to generate RTL instructions for various kinds of constructs. */
24
25#include "config.h"
26#include "system.h"
27#include "coretypes.h"
28#include "backend.h"
29#include "target.h"
30#include "rtl.h"
31#include "tree.h"
32#include "gimple.h"
33#include "cfghooks.h"
34#include "predict.h"
35#include "memmodel.h"
36#include "tm_p.h"
37#include "optabs.h"
38#include "regs.h"
39#include "emit-rtl.h"
40#include "pretty-print.h"
41#include "diagnostic-core.h"
42
43#include "fold-const.h"
44#include "varasm.h"
45#include "stor-layout.h"
46#include "dojump.h"
47#include "explow.h"
48#include "stmt.h"
49#include "expr.h"
50#include "langhooks.h"
51#include "cfganal.h"
52#include "tree-cfg.h"
53#include "dumpfile.h"
54#include "builtins.h"
55
56
57/* Functions and data structures for expanding case statements. */
58
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.
62
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.
65
66 Switch statements are expanded in jump table form.
67
68*/
69
70class simple_case_node
71{
72public:
73 simple_case_node (tree low, tree high, tree code_label):
74 m_low (low), m_high (high), m_code_label (code_label)
75 {}
76
77 /* Lowest index value for this label. */
78 tree m_low;
79 /* Highest index value for this label. */
80 tree m_high;
81 /* Label to jump to when node matches. */
82 tree m_code_label;
83};
84
85static bool check_unique_operand_names (tree, tree, tree);
86static char *resolve_operand_name_1 (char *, tree, tree, tree);
87
88/* Return the rtx-label that corresponds to a LABEL_DECL,
89 creating it if necessary. */
90
91rtx_insn *
92label_rtx (tree label)
93{
94 gcc_assert (TREE_CODE (label) == LABEL_DECL);
95
96 if (!DECL_RTL_SET_P (label))
97 {
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;
102 }
103
104 return as_a <rtx_insn *> (DECL_RTL (label));
105}
106
107/* As above, but also put it on the forced-reference list of the
108 function that contains it. */
109rtx_insn *
110force_label_rtx (tree label)
111{
112 rtx_insn *ref = label_rtx (label);
113 tree function = decl_function_context (label);
114
115 gcc_assert (function);
116
117 vec_safe_push (forced_labels, obj: ref);
118 return ref;
119}
120
121/* As label_rtx, but ensures (in check build), that returned value is
122 an existing label (i.e. rtx with code CODE_LABEL). */
123rtx_code_label *
124jump_target_rtx (tree label)
125{
126 return as_a <rtx_code_label *> (p: label_rtx (label));
127}
128
129/* Add an unconditional jump to LABEL as the next sequential instruction. */
130
131void
132emit_jump (rtx label)
133{
134 do_pending_stack_adjust ();
135 emit_jump_insn (targetm.gen_jump (label));
136 emit_barrier ();
137}
138
139/* Handle goto statements and the labels that they can go to. */
140
141/* Specify the location in the RTL code of a label LABEL,
142 which is a LABEL_DECL tree node.
143
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.
148
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. */
151
152void
153expand_label (tree label)
154{
155 rtx_code_label *label_r = jump_target_rtx (label);
156
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));
161
162 if (DECL_NONLOCAL (label))
163 {
164 expand_builtin_setjmp_receiver (NULL);
165 nonlocal_goto_handler_labels
166 = gen_rtx_INSN_LIST (VOIDmode, label_r,
167 nonlocal_goto_handler_labels);
168 }
169
170 if (FORCED_LABEL (label))
171 vec_safe_push<rtx_insn *> (forced_labels, obj: label_r);
172
173 if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
174 maybe_set_first_label_num (label_r);
175}
176
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.)
187
188 Returns TRUE if all went well; FALSE if an error occurred. */
189
190bool
191parse_output_constraint (const char **constraint_p, int operand_num,
192 int ninputs, int noutputs, bool *allows_mem,
193 bool *allows_reg, bool *is_inout)
194{
195 const char *constraint = *constraint_p;
196 const char *p;
197
198 /* Assume the constraint doesn't allow the use of either a register
199 or memory. */
200 *allows_mem = false;
201 *allows_reg = false;
202
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 (s: constraint, c: '=');
208 if (!p)
209 p = strchr (s: constraint, c: '+');
210
211 /* If the string doesn't contain an `=', issue an error
212 message. */
213 if (!p)
214 {
215 error ("output operand constraint lacks %<=%>");
216 return false;
217 }
218
219 /* If the constraint begins with `+', then the operand is both read
220 from and written to. */
221 *is_inout = (*p == '+');
222
223 /* Canonicalize the output constraint so that it begins with `='. */
224 if (p != constraint || *is_inout)
225 {
226 char *buf;
227 size_t c_len = strlen (s: constraint);
228
229 if (p != constraint)
230 warning (0, "output constraint %qc for operand %d "
231 "is not at the beginning",
232 *p, operand_num);
233
234 /* Make a copy of the constraint. */
235 buf = XALLOCAVEC (char, c_len + 1);
236 strcpy (dest: buf, src: 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 `+'.) */
241 buf[0] = '=';
242 /* Replace the constraint with the canonicalized string. */
243 *constraint_p = ggc_alloc_string (contents: buf, length: c_len);
244 constraint = *constraint_p;
245 }
246
247 /* Loop through the constraint string. */
248 for (p = constraint + 1; *p; )
249 {
250 switch (*p)
251 {
252 case '+':
253 case '=':
254 error ("operand constraint contains incorrectly positioned "
255 "%<+%> or %<=%>");
256 return false;
257
258 case '%':
259 if (operand_num + 1 == ninputs + noutputs)
260 {
261 error ("%<%%%> constraint used with last operand");
262 return false;
263 }
264 break;
265
266 case '?': case '!': case '*': case '&': case '#':
267 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 ',':
272 break;
273
274 case '0': case '1': case '2': case '3': case '4':
275 case '5': case '6': case '7': case '8': case '9':
276 case '[':
277 error ("matching constraint not valid in output operand");
278 return false;
279
280 case '<': case '>':
281 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
282 excepting those that expand_call created. So match memory
283 and hope. */
284 *allows_mem = true;
285 break;
286
287 case 'g': case 'X':
288 *allows_reg = true;
289 *allows_mem = true;
290 break;
291
292 default:
293 if (!ISALPHA (*p))
294 break;
295 enum constraint_num cn = lookup_constraint (p);
296 if (reg_class_for_constraint (c: cn) != NO_REGS
297 || insn_extra_address_constraint (c: cn))
298 *allows_reg = true;
299 else if (insn_extra_memory_constraint (c: cn))
300 *allows_mem = true;
301 else
302 insn_extra_constraint_allows_reg_mem (c: cn, allows_reg, allows_mem);
303 break;
304 }
305
306 for (size_t len = CONSTRAINT_LEN (*p, p); len; len--, p++)
307 if (*p == '\0')
308 break;
309 }
310
311 return true;
312}
313
314/* Similar, but for input constraints. */
315
316bool
317parse_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)
321{
322 const char *constraint = *constraint_p;
323 const char *orig_constraint = constraint;
324 size_t c_len = strlen (s: constraint);
325 size_t j;
326 bool saw_match = false;
327
328 /* Assume the constraint doesn't allow the use of either
329 a register or memory. */
330 *allows_mem = false;
331 *allows_reg = false;
332
333 /* Make sure constraint has neither `=', `+', nor '&'. */
334
335 for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
336 switch (constraint[j])
337 {
338 case '+': case '=': case '&':
339 if (constraint == orig_constraint)
340 {
341 error ("input operand constraint contains %qc", constraint[j]);
342 return false;
343 }
344 break;
345
346 case '%':
347 if (constraint == orig_constraint
348 && input_num + 1 == ninputs - ninout)
349 {
350 error ("%<%%%> constraint used with last operand");
351 return false;
352 }
353 break;
354
355 case '<': case '>':
356 case '?': case '!': case '*': case '#':
357 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 ',':
362 break;
363
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':
371 {
372 char *end;
373 unsigned long match;
374
375 saw_match = true;
376
377 match = strtoul (nptr: constraint + j, endptr: &end, base: 10);
378 if (match >= (unsigned long) noutputs)
379 {
380 error ("matching constraint references invalid operand number");
381 return false;
382 }
383
384 /* Try and find the real constraint for this dup. Only do this
385 if the matching constraint is the only alternative. */
386 if (*end == '\0'
387 && (j == 0 || (j == 1 && constraint[0] == '%')))
388 {
389 constraint = constraints[match];
390 *constraint_p = constraint;
391 c_len = strlen (s: constraint);
392 j = 0;
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. */
397 break;
398 }
399 else
400 j = end - constraint;
401 /* Anticipate increment at end of loop. */
402 j--;
403 }
404 /* Fall through. */
405
406 case 'g': case 'X':
407 *allows_reg = true;
408 *allows_mem = true;
409 break;
410
411 default:
412 if (! ISALPHA (constraint[j]))
413 {
414 error ("invalid punctuation %qc in constraint", constraint[j]);
415 return false;
416 }
417 enum constraint_num cn = lookup_constraint (p: constraint + j);
418 if (reg_class_for_constraint (c: cn) != NO_REGS
419 || insn_extra_address_constraint (c: cn))
420 *allows_reg = true;
421 else if (insn_extra_memory_constraint (c: cn)
422 || insn_extra_special_memory_constraint (c: cn)
423 || insn_extra_relaxed_memory_constraint (cn))
424 *allows_mem = true;
425 else
426 insn_extra_constraint_allows_reg_mem (c: cn, allows_reg, allows_mem);
427 break;
428 }
429
430 if (saw_match && !*allows_reg)
431 warning (0, "matching constraint does not allow a register");
432
433 return true;
434}
435
436/* Return DECL iff there's an overlap between *REGS and DECL, where DECL
437 can be an asm-declared register. Called via walk_tree. */
438
439static tree
440decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED,
441 void *data)
442{
443 tree decl = *declp;
444 const HARD_REG_SET *const regs = (const HARD_REG_SET *) data;
445
446 if (VAR_P (decl))
447 {
448 if (DECL_HARD_REGISTER (decl)
449 && REG_P (DECL_RTL (decl))
450 && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
451 {
452 rtx reg = DECL_RTL (decl);
453
454 if (overlaps_hard_reg_set_p (regs: *regs, GET_MODE (reg), REGNO (reg)))
455 return decl;
456 }
457 walk_subtrees = 0;
458 }
459 else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL)
460 walk_subtrees = 0;
461 return NULL_TREE;
462}
463
464/* If there is an overlap between *REGS and DECL, return the first overlap
465 found. */
466tree
467tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs)
468{
469 return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL);
470}
471
472
473/* A subroutine of expand_asm_operands. Check that all operand names
474 are unique. Return true if so. We rely on the fact that these names
475 are identifiers, and so have been canonicalized by get_identifier,
476 so all we need are pointer comparisons. */
477
478static bool
479check_unique_operand_names (tree outputs, tree inputs, tree labels)
480{
481 tree i, j, i_name = NULL_TREE;
482
483 for (i = outputs; i ; i = TREE_CHAIN (i))
484 {
485 i_name = TREE_PURPOSE (TREE_PURPOSE (i));
486 if (! i_name)
487 continue;
488
489 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
490 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
491 goto failure;
492 }
493
494 for (i = inputs; i ; i = TREE_CHAIN (i))
495 {
496 i_name = TREE_PURPOSE (TREE_PURPOSE (i));
497 if (! i_name)
498 continue;
499
500 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
501 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
502 goto failure;
503 for (j = outputs; j ; j = TREE_CHAIN (j))
504 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
505 goto failure;
506 }
507
508 for (i = labels; i ; i = TREE_CHAIN (i))
509 {
510 i_name = TREE_PURPOSE (i);
511 if (! i_name)
512 continue;
513
514 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
515 if (simple_cst_equal (i_name, TREE_PURPOSE (j)))
516 goto failure;
517 for (j = inputs; j ; j = TREE_CHAIN (j))
518 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
519 goto failure;
520 }
521
522 return true;
523
524 failure:
525 error ("duplicate %<asm%> operand name %qs", TREE_STRING_POINTER (i_name));
526 return false;
527}
528
529/* Resolve the names of the operands in *POUTPUTS and *PINPUTS to numbers,
530 and replace the name expansions in STRING and in the constraints to
531 those numbers. This is generally done in the front end while creating
532 the ASM_EXPR generic tree that eventually becomes the GIMPLE_ASM. */
533
534tree
535resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels)
536{
537 char *buffer;
538 char *p;
539 const char *c;
540 tree t;
541
542 check_unique_operand_names (outputs, inputs, labels);
543
544 /* Substitute [<name>] in input constraint strings. There should be no
545 named operands in output constraints. */
546 for (t = inputs; t ; t = TREE_CHAIN (t))
547 {
548 c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
549 if (strchr (s: c, c: '[') != NULL)
550 {
551 p = buffer = xstrdup (c);
552 while ((p = strchr (s: p, c: '[')) != NULL)
553 p = resolve_operand_name_1 (p, outputs, inputs, NULL);
554 TREE_VALUE (TREE_PURPOSE (t))
555 = build_string (strlen (s: buffer), buffer);
556 free (ptr: buffer);
557 }
558 }
559
560 /* Now check for any needed substitutions in the template. */
561 c = TREE_STRING_POINTER (string);
562 while ((c = strchr (s: c, c: '%')) != NULL)
563 {
564 if (c[1] == '[')
565 break;
566 else if (ISALPHA (c[1]) && c[2] == '[')
567 break;
568 else
569 {
570 c += 1 + (c[1] == '%');
571 continue;
572 }
573 }
574
575 if (c)
576 {
577 /* OK, we need to make a copy so we can perform the substitutions.
578 Assume that we will not need extra space--we get to remove '['
579 and ']', which means we cannot have a problem until we have more
580 than 999 operands. */
581 buffer = xstrdup (TREE_STRING_POINTER (string));
582 p = buffer + (c - TREE_STRING_POINTER (string));
583
584 while ((p = strchr (s: p, c: '%')) != NULL)
585 {
586 if (p[1] == '[')
587 p += 1;
588 else if (ISALPHA (p[1]) && p[2] == '[')
589 p += 2;
590 else
591 {
592 p += 1 + (p[1] == '%');
593 continue;
594 }
595
596 p = resolve_operand_name_1 (p, outputs, inputs, labels);
597 }
598
599 string = build_string (strlen (s: buffer), buffer);
600 free (ptr: buffer);
601 }
602
603 return string;
604}
605
606/* A subroutine of resolve_operand_names. P points to the '[' for a
607 potential named operand of the form [<name>]. In place, replace
608 the name and brackets with a number. Return a pointer to the
609 balance of the string after substitution. */
610
611static char *
612resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels)
613{
614 char *q;
615 int op, op_inout;
616 tree t;
617
618 /* Collect the operand name. */
619 q = strchr (s: ++p, c: ']');
620 if (!q)
621 {
622 error ("missing close brace for named operand");
623 return strchr (s: p, c: '\0');
624 }
625 *q = '\0';
626
627 /* Resolve the name to a number. */
628 for (op_inout = op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
629 {
630 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
631 if (name && strcmp (TREE_STRING_POINTER (name), s2: p) == 0)
632 goto found;
633 tree constraint = TREE_VALUE (TREE_PURPOSE (t));
634 if (constraint && strchr (TREE_STRING_POINTER (constraint), c: '+') != NULL)
635 op_inout++;
636 }
637 for (t = inputs; t ; t = TREE_CHAIN (t), op++)
638 {
639 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
640 if (name && strcmp (TREE_STRING_POINTER (name), s2: p) == 0)
641 goto found;
642 }
643 op += op_inout;
644 for (t = labels; t ; t = TREE_CHAIN (t), op++)
645 {
646 tree name = TREE_PURPOSE (t);
647 if (name && strcmp (TREE_STRING_POINTER (name), s2: p) == 0)
648 goto found;
649 }
650
651 error ("undefined named operand %qs", identifier_to_locale (p));
652 op = 0;
653
654 found:
655 /* Replace the name with the number. Unfortunately, not all libraries
656 get the return value of sprintf correct, so search for the end of the
657 generated string by hand. */
658 sprintf (s: --p, format: "%d", op);
659 p = strchr (s: p, c: '\0');
660
661 /* Verify the no extra buffer space assumption. */
662 gcc_assert (p <= q);
663
664 /* Shift the rest of the buffer down to fill the gap. */
665 memmove (dest: p, src: q + 1, n: strlen (s: q + 1) + 1);
666
667 return p;
668}
669
670
671/* Generate RTL to return directly from the current function.
672 (That is, we bypass any return value.) */
673
674void
675expand_naked_return (void)
676{
677 rtx_code_label *end_label;
678
679 clear_pending_stack_adjust ();
680 do_pending_stack_adjust ();
681
682 end_label = naked_return_label;
683 if (end_label == 0)
684 end_label = naked_return_label = gen_label_rtx ();
685
686 emit_jump (label: end_label);
687}
688
689/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
690 is the probability of jumping to LABEL. */
691static void
692do_jump_if_equal (machine_mode mode, rtx op0, rtx op1, rtx_code_label *label,
693 int unsignedp, profile_probability prob)
694{
695 do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
696 NULL_RTX, NULL, label, prob);
697}
698
699/* Return the sum of probabilities of outgoing edges of basic block BB. */
700
701static profile_probability
702get_outgoing_edge_probs (basic_block bb)
703{
704 edge e;
705 edge_iterator ei;
706 profile_probability prob_sum = profile_probability::never ();
707 if (!bb)
708 return profile_probability::never ();
709 FOR_EACH_EDGE (e, ei, bb->succs)
710 prob_sum += e->probability;
711 return prob_sum;
712}
713
714/* Computes the conditional probability of jumping to a target if the branch
715 instruction is executed.
716 TARGET_PROB is the estimated probability of jumping to a target relative
717 to some basic block BB.
718 BASE_PROB is the probability of reaching the branch instruction relative
719 to the same basic block BB. */
720
721static inline profile_probability
722conditional_probability (profile_probability target_prob,
723 profile_probability base_prob)
724{
725 return target_prob / base_prob;
726}
727
728/* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
729 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
730 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
731 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
732
733 First, a jump insn is emitted. First we try "casesi". If that
734 fails, try "tablejump". A target *must* have one of them (or both).
735
736 Then, a table with the target labels is emitted.
737
738 The process is unaware of the CFG. The caller has to fix up
739 the CFG itself. This is done in cfgexpand.cc. */
740
741static void
742emit_case_dispatch_table (tree index_expr, tree index_type,
743 auto_vec<simple_case_node> &case_list,
744 rtx default_label,
745 edge default_edge, tree minval, tree maxval,
746 tree range, basic_block stmt_bb)
747{
748 int i, ncases;
749 auto_vec<rtx> labelvec;
750 rtx_insn *fallback_label = label_rtx (label: case_list[0].m_code_label);
751 rtx_code_label *table_label = gen_label_rtx ();
752 bool has_gaps = false;
753 profile_probability default_prob = default_edge ? default_edge->probability
754 : profile_probability::never ();
755 profile_probability base = get_outgoing_edge_probs (bb: stmt_bb);
756 bool try_with_tablejump = false;
757
758 profile_probability new_default_prob = conditional_probability (target_prob: default_prob,
759 base_prob: base);
760
761 if (! try_casesi (index_type, index_expr, minval, range,
762 table_label, default_label, fallback_label,
763 new_default_prob))
764 {
765 /* Index jumptables from zero for suitable values of minval to avoid
766 a subtraction. For the rationale see:
767 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
768 if (optimize_insn_for_speed_p ()
769 && compare_tree_int (minval, 0) > 0
770 && compare_tree_int (minval, 3) < 0)
771 {
772 minval = build_int_cst (index_type, 0);
773 range = maxval;
774 has_gaps = true;
775 }
776 try_with_tablejump = true;
777 }
778
779 /* Get table of labels to jump to, in order of case index. */
780
781 ncases = tree_to_shwi (range) + 1;
782 labelvec.safe_grow_cleared (len: ncases);
783
784 for (unsigned j = 0; j < case_list.length (); j++)
785 {
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. */
790 HOST_WIDE_INT i_low
791 = tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
792 n->m_low, minval));
793 HOST_WIDE_INT i_high
794 = tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
795 n->m_high, minval));
796 HOST_WIDE_INT i;
797
798 for (i = i_low; i <= i_high; i ++)
799 labelvec[i]
800 = gen_rtx_LABEL_REF (Pmode, label_rtx (n->m_code_label));
801 }
802
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;
809
810 for (i = 0; i < ncases; i++)
811 if (labelvec[i] == 0)
812 {
813 has_gaps = true;
814 labelvec[i] = gen_rtx_LABEL_REF (Pmode, gap_label);
815 }
816
817 if (has_gaps && default_label)
818 {
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. */
824 new_default_prob = conditional_probability (target_prob: default_prob / 2, base_prob: base);
825 default_prob /= 2;
826 base -= default_prob;
827 }
828 else
829 {
830 base -= default_prob;
831 default_prob = profile_probability::never ();
832 }
833
834 if (default_edge)
835 default_edge->probability = default_prob;
836
837 /* We have altered the probability of the default edge. So the probabilities
838 of all other edges need to be adjusted so that it sums up to
839 REG_BR_PROB_BASE. */
840 if (base > profile_probability::never ())
841 {
842 edge e;
843 edge_iterator ei;
844 FOR_EACH_EDGE (e, ei, stmt_bb->succs)
845 e->probability /= base;
846 }
847
848 if (try_with_tablejump)
849 {
850 bool ok = try_tablejump (index_type, index_expr, minval, range,
851 table_label, default_label, new_default_prob);
852 gcc_assert (ok);
853 }
854 /* Output the table. */
855 emit_label (table_label);
856
857 if (CASE_VECTOR_PC_RELATIVE
858 || (flag_pic && targetm.asm_out.generate_pic_addr_diff_vec ()))
859 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
860 gen_rtx_LABEL_REF (Pmode,
861 table_label),
862 gen_rtvec_v (ncases, labelvec.address ()),
863 const0_rtx, const0_rtx));
864 else
865 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
866 gen_rtvec_v (ncases, labelvec.address ())));
867
868 /* Record no drop-through after the table. */
869 emit_barrier ();
870}
871
872/* Terminate a case Ada or switch (C) statement
873 in which ORIG_INDEX is the expression to be tested.
874 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
875 type as given in the source before any compiler conversions.
876 Generate the code to test it and jump to the right place. */
877
878void
879expand_case (gswitch *stmt)
880{
881 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
882 rtx_code_label *default_label;
883 unsigned int count;
884 int i;
885 int ncases = gimple_switch_num_labels (gs: stmt);
886 tree index_expr = gimple_switch_index (gs: stmt);
887 tree index_type = TREE_TYPE (index_expr);
888 tree elt;
889 basic_block bb = gimple_bb (g: stmt);
890 gimple *def_stmt;
891
892 auto_vec<simple_case_node> case_list;
893
894 /* An ERROR_MARK occurs for various reasons including invalid data type.
895 ??? Can this still happen, with GIMPLE and all? */
896 if (index_type == error_mark_node)
897 return;
898
899 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
900 expressions being INTEGER_CST. */
901 gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
902
903 /* Optimization of switch statements with only one label has already
904 occurred, so we should never see them at this point. */
905 gcc_assert (ncases > 1);
906
907 do_pending_stack_adjust ();
908
909 /* Find the default case target label. */
910 tree default_lab = CASE_LABEL (gimple_switch_default_label (stmt));
911 default_label = jump_target_rtx (label: default_lab);
912 basic_block default_bb = label_to_block (cfun, default_lab);
913 edge default_edge = find_edge (bb, default_bb);
914
915 /* Get upper and lower bounds of case values. */
916 elt = gimple_switch_label (gs: stmt, index: 1);
917 minval = fold_convert (index_type, CASE_LOW (elt));
918 elt = gimple_switch_label (gs: stmt, index: ncases - 1);
919 if (CASE_HIGH (elt))
920 maxval = fold_convert (index_type, CASE_HIGH (elt));
921 else
922 maxval = fold_convert (index_type, CASE_LOW (elt));
923
924 /* Try to narrow the index type if it's larger than a word.
925 That is mainly for -O0 where an equivalent optimization
926 done by forward propagation is not run and is aimed at
927 avoiding a call to a comparison routine of libgcc. */
928 if (TYPE_PRECISION (index_type) > BITS_PER_WORD
929 && TREE_CODE (index_expr) == SSA_NAME
930 && (def_stmt = SSA_NAME_DEF_STMT (index_expr))
931 && is_gimple_assign (gs: def_stmt)
932 && gimple_assign_rhs_code (gs: def_stmt) == NOP_EXPR)
933 {
934 tree inner_index_expr = gimple_assign_rhs1 (gs: def_stmt);
935 tree inner_index_type = TREE_TYPE (inner_index_expr);
936
937 if (INTEGRAL_TYPE_P (inner_index_type)
938 && TYPE_PRECISION (inner_index_type) <= BITS_PER_WORD
939 && int_fits_type_p (minval, inner_index_type)
940 && int_fits_type_p (maxval, inner_index_type))
941 {
942 index_expr = inner_index_expr;
943 index_type = inner_index_type;
944 minval = fold_convert (index_type, minval);
945 maxval = fold_convert (index_type, maxval);
946 }
947 }
948
949 /* Compute span of values. */
950 range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
951
952 /* Listify the labels queue and gather some numbers to decide
953 how to expand this switch(). */
954 count = 0;
955
956 for (i = ncases - 1; i >= 1; --i)
957 {
958 elt = gimple_switch_label (gs: stmt, index: i);
959 tree low = CASE_LOW (elt);
960 gcc_assert (low);
961 tree high = CASE_HIGH (elt);
962 gcc_assert (! high || tree_int_cst_lt (low, high));
963 tree lab = CASE_LABEL (elt);
964
965 /* Count the elements.
966 A range counts double, since it requires two compares. */
967 count++;
968 if (high)
969 count++;
970
971 /* The bounds on the case range, LOW and HIGH, have to be converted
972 to case's index type TYPE. Note that the original type of the
973 case index in the source code is usually "lost" during
974 gimplification due to type promotion, but the case labels retain the
975 original type. Make sure to drop overflow flags. */
976 low = fold_convert (index_type, low);
977 if (TREE_OVERFLOW (low))
978 low = wide_int_to_tree (type: index_type, cst: wi::to_wide (t: low));
979
980 /* The canonical from of a case label in GIMPLE is that a simple case
981 has an empty CASE_HIGH. For the casesi and tablejump expanders,
982 the back ends want simple cases to have high == low. */
983 if (! high)
984 high = low;
985 high = fold_convert (index_type, high);
986 if (TREE_OVERFLOW (high))
987 high = wide_int_to_tree (type: index_type, cst: wi::to_wide (t: high));
988
989 case_list.safe_push (obj: simple_case_node (low, high, lab));
990 }
991
992 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
993 destination, such as one with a default case only.
994 It also removes cases that are out of range for the switch
995 type, so we should never get a zero here. */
996 gcc_assert (count > 0);
997
998 rtx_insn *before_case = get_last_insn ();
999
1000 /* If the default case is unreachable, then set default_label to NULL
1001 so that we omit the range check when generating the dispatch table.
1002 We also remove the edge to the unreachable default case. The block
1003 itself will be automatically removed later. */
1004 if (EDGE_COUNT (default_edge->dest->succs) == 0
1005 && gimple_seq_unreachable_p (bb_seq (bb: default_edge->dest)))
1006 {
1007 default_label = NULL;
1008 remove_edge (default_edge);
1009 default_edge = NULL;
1010 }
1011
1012 emit_case_dispatch_table (index_expr, index_type,
1013 case_list, default_label, default_edge,
1014 minval, maxval, range, stmt_bb: bb);
1015
1016 reorder_insns (NEXT_INSN (insn: before_case), get_last_insn (), before_case);
1017
1018 free_temp_slots ();
1019}
1020
1021/* Expand the dispatch to a short decrement chain if there are few cases
1022 to dispatch to. Likewise if neither casesi nor tablejump is available,
1023 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
1024 tablejump. The index mode is always the mode of integer_type_node.
1025 Trap if no case matches the index.
1026
1027 DISPATCH_INDEX is the index expression to switch on. It should be a
1028 memory or register operand.
1029
1030 DISPATCH_TABLE is a set of case labels. The set should be sorted in
1031 ascending order, be contiguous, starting with value 0, and contain only
1032 single-valued case labels. */
1033
1034void
1035expand_sjlj_dispatch_table (rtx dispatch_index,
1036 vec<tree> dispatch_table)
1037{
1038 tree index_type = integer_type_node;
1039 machine_mode index_mode = TYPE_MODE (index_type);
1040
1041 int ncases = dispatch_table.length ();
1042
1043 do_pending_stack_adjust ();
1044 rtx_insn *before_case = get_last_insn ();
1045
1046 /* Expand as a decrement-chain if there are 5 or fewer dispatch
1047 labels. This covers more than 98% of the cases in libjava,
1048 and seems to be a reasonable compromise between the "old way"
1049 of expanding as a decision tree or dispatch table vs. the "new
1050 way" with decrement chain or dispatch table. */
1051 if (dispatch_table.length () <= 5
1052 || (!targetm.have_casesi () && !targetm.have_tablejump ())
1053 || !flag_jump_tables)
1054 {
1055 /* Expand the dispatch as a decrement chain:
1056
1057 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1058
1059 ==>
1060
1061 if (index == 0) do_0; else index--;
1062 if (index == 0) do_1; else index--;
1063 ...
1064 if (index == 0) do_N; else index--;
1065
1066 This is more efficient than a dispatch table on most machines.
1067 The last "index--" is redundant but the code is trivially dead
1068 and will be cleaned up by later passes. */
1069 rtx index = copy_to_mode_reg (index_mode, dispatch_index);
1070 rtx zero = CONST0_RTX (index_mode);
1071 for (int i = 0; i < ncases; i++)
1072 {
1073 tree elt = dispatch_table[i];
1074 rtx_code_label *lab = jump_target_rtx (CASE_LABEL (elt));
1075 do_jump_if_equal (mode: index_mode, op0: index, op1: zero, label: lab, unsignedp: 0,
1076 prob: profile_probability::uninitialized ());
1077 force_expand_binop (index_mode, sub_optab,
1078 index, CONST1_RTX (index_mode),
1079 index, 0, OPTAB_DIRECT);
1080 }
1081 }
1082 else
1083 {
1084 /* Similar to expand_case, but much simpler. */
1085 auto_vec<simple_case_node> case_list;
1086 tree index_expr = make_tree (index_type, dispatch_index);
1087 tree minval = build_int_cst (index_type, 0);
1088 tree maxval = CASE_LOW (dispatch_table.last ());
1089 tree range = maxval;
1090 rtx_code_label *default_label = gen_label_rtx ();
1091
1092 for (int i = ncases - 1; i >= 0; --i)
1093 {
1094 tree elt = dispatch_table[i];
1095 tree high = CASE_HIGH (elt);
1096 if (high == NULL_TREE)
1097 high = CASE_LOW (elt);
1098 case_list.safe_push (obj: simple_case_node (CASE_LOW (elt), high,
1099 CASE_LABEL (elt)));
1100 }
1101
1102 emit_case_dispatch_table (index_expr, index_type,
1103 case_list, default_label, NULL,
1104 minval, maxval, range,
1105 stmt_bb: BLOCK_FOR_INSN (insn: before_case));
1106 emit_label (default_label);
1107 }
1108
1109 /* Dispatching something not handled? Trap! */
1110 expand_builtin_trap ();
1111
1112 reorder_insns (NEXT_INSN (insn: before_case), get_last_insn (), before_case);
1113
1114 free_temp_slots ();
1115}
1116
1117
1118

source code of gcc/stmt.cc