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