1 | /* Expands front end tree to back end RTL for GCC |
2 | Copyright (C) 1987-2023 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.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 | |
70 | class simple_case_node |
71 | { |
72 | public: |
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 | |
85 | static bool check_unique_operand_names (tree, tree, tree); |
86 | static 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 | |
91 | rtx_insn * |
92 | label_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. */ |
109 | rtx_insn * |
110 | force_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). */ |
123 | rtx_code_label * |
124 | jump_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 | |
131 | void |
132 | emit_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 | |
152 | void |
153 | expand_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 | |
190 | bool |
191 | parse_output_constraint (const char **constraint_p, int operand_num, |
192 | int ninputs, int noutputs, bool *allows_mem, |
193 | bool *allows_reg, bool *is_inout) |
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 | |
316 | bool |
317 | parse_input_constraint (const char **constraint_p, int input_num, |
318 | int ninputs, int noutputs, int ninout, |
319 | const char * const * constraints, |
320 | bool *allows_mem, bool *allows_reg) |
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 | |
439 | static tree |
440 | decl_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. */ |
466 | tree |
467 | tree_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 | |
478 | static bool |
479 | check_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 | |
534 | tree |
535 | resolve_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 | |
611 | static char * |
612 | resolve_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 | |
674 | void |
675 | expand_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. */ |
691 | static void |
692 | do_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 | |
701 | static profile_probability |
702 | get_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 | |
721 | static inline profile_probability |
722 | conditional_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 | |
741 | static void |
742 | emit_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 | |
878 | void |
879 | expand_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 | |
1034 | void |
1035 | expand_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 | |