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