Branch data Line data Source code
1 : : /* Expands front end tree to back end RTL for GCC
2 : : Copyright (C) 1987-2024 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 : 156835 : simple_case_node (tree low, tree high, tree code_label):
74 : 156835 : 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 : 2567724 : label_rtx (tree label)
93 : : {
94 : 2567724 : gcc_assert (TREE_CODE (label) == LABEL_DECL);
95 : :
96 : 2567724 : if (!DECL_RTL_SET_P (label))
97 : : {
98 : 624056 : rtx_code_label *r = gen_label_rtx ();
99 : 624056 : SET_DECL_RTL (label, r);
100 : 624056 : if (FORCED_LABEL (label) || DECL_NONLOCAL (label))
101 : 14124 : LABEL_PRESERVE_P (r) = 1;
102 : : }
103 : :
104 : 2567724 : 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 : 0 : force_label_rtx (tree label)
111 : : {
112 : 0 : rtx_insn *ref = label_rtx (label);
113 : 0 : tree function = decl_function_context (label);
114 : :
115 : 0 : gcc_assert (function);
116 : :
117 : 0 : vec_safe_push (forced_labels, ref);
118 : 0 : 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 : 824227 : jump_target_rtx (tree label)
125 : : {
126 : 824227 : return as_a <rtx_code_label *> (label_rtx (label));
127 : : }
128 : :
129 : : /* Add an unconditional jump to LABEL as the next sequential instruction. */
130 : :
131 : : void
132 : 2906727 : emit_jump (rtx label)
133 : : {
134 : 2906727 : do_pending_stack_adjust ();
135 : 2906727 : emit_jump_insn (targetm.gen_jump (label));
136 : 2906727 : emit_barrier ();
137 : 2906727 : }
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 : 624056 : expand_label (tree label)
154 : : {
155 : 624056 : rtx_code_label *label_r = jump_target_rtx (label);
156 : :
157 : 624056 : do_pending_stack_adjust ();
158 : 624056 : emit_label (label_r);
159 : 624056 : if (DECL_NAME (label))
160 : 80701 : LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label));
161 : :
162 : 624056 : if (DECL_NONLOCAL (label))
163 : : {
164 : 501 : expand_builtin_setjmp_receiver (NULL);
165 : 501 : nonlocal_goto_handler_labels
166 : 501 : = gen_rtx_INSN_LIST (VOIDmode, label_r,
167 : 501 : nonlocal_goto_handler_labels);
168 : : }
169 : :
170 : 624056 : if (FORCED_LABEL (label))
171 : 13623 : vec_safe_push<rtx_insn *> (forced_labels, label_r);
172 : :
173 : 1247611 : if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
174 : 14124 : maybe_set_first_label_num (label_r);
175 : 624056 : }
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 : 42347461 : 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 : 42347461 : const char *constraint = *constraint_p;
196 : 42347461 : const char *p;
197 : :
198 : : /* Assume the constraint doesn't allow the use of either a register
199 : : or memory. */
200 : 42347461 : *allows_mem = false;
201 : 42347461 : *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 : 42347461 : p = strchr (constraint, '=');
208 : 42347461 : if (!p)
209 : 18334 : p = strchr (constraint, '+');
210 : :
211 : : /* If the string doesn't contain an `=', issue an error
212 : : message. */
213 : 18334 : if (!p)
214 : : {
215 : 14 : error ("output operand constraint lacks %<=%>");
216 : 14 : return false;
217 : : }
218 : :
219 : : /* If the constraint begins with `+', then the operand is both read
220 : : from and written to. */
221 : 42347447 : *is_inout = (*p == '+');
222 : :
223 : : /* Canonicalize the output constraint so that it begins with `='. */
224 : 42347447 : if (p != constraint || *is_inout)
225 : : {
226 : 18320 : char *buf;
227 : 18320 : size_t c_len = strlen (constraint);
228 : :
229 : 18320 : if (p != constraint)
230 : 0 : warning (0, "output constraint %qc for operand %d "
231 : : "is not at the beginning",
232 : 0 : *p, operand_num);
233 : :
234 : : /* Make a copy of the constraint. */
235 : 18320 : buf = XALLOCAVEC (char, c_len + 1);
236 : 18320 : strcpy (buf, constraint);
237 : : /* Swap the first character and the `=' or `+'. */
238 : 18320 : buf[p - constraint] = buf[0];
239 : : /* Make sure the first character is an `='. (Until we do this,
240 : : it might be a `+'.) */
241 : 18320 : buf[0] = '=';
242 : : /* Replace the constraint with the canonicalized string. */
243 : 18320 : *constraint_p = ggc_alloc_string (buf, c_len);
244 : 18320 : constraint = *constraint_p;
245 : : }
246 : :
247 : : /* Loop through the constraint string. */
248 : 85507270 : for (p = constraint + 1; *p; )
249 : : {
250 : 43159823 : switch (*p)
251 : : {
252 : 0 : case '+':
253 : 0 : case '=':
254 : 0 : error ("operand constraint contains incorrectly positioned "
255 : : "%<+%> or %<=%>");
256 : 0 : return false;
257 : :
258 : 0 : case '%':
259 : 0 : if (operand_num + 1 == ninputs + noutputs)
260 : : {
261 : 0 : error ("%<%%%> constraint used with last operand");
262 : 0 : 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 : 0 : case '0': case '1': case '2': case '3': case '4':
275 : 0 : case '5': case '6': case '7': case '8': case '9':
276 : 0 : case '[':
277 : 0 : error ("matching constraint not valid in output operand");
278 : 0 : return false;
279 : :
280 : 0 : 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 : 0 : *allows_mem = true;
285 : 0 : break;
286 : :
287 : 1936169 : case 'g': case 'X':
288 : 1936169 : *allows_reg = true;
289 : 1936169 : *allows_mem = true;
290 : 1936169 : break;
291 : :
292 : 40605204 : default:
293 : 40605204 : if (!ISALPHA (*p))
294 : : break;
295 : 40586050 : enum constraint_num cn = lookup_constraint (p);
296 : 40586050 : if (reg_class_for_constraint (cn) != NO_REGS
297 : 40586050 : || insn_extra_address_constraint (cn))
298 : 38528506 : *allows_reg = true;
299 : : else if (insn_extra_memory_constraint (cn))
300 : 2049665 : *allows_mem = true;
301 : : else
302 : : insn_extra_constraint_allows_reg_mem (cn, allows_reg, allows_mem);
303 : : break;
304 : : }
305 : :
306 : 86334054 : for (size_t len = CONSTRAINT_LEN (*p, p); len; len--, p++)
307 : 43174678 : if (*p == '\0')
308 : : break;
309 : : }
310 : :
311 : : return true;
312 : : }
313 : :
314 : : /* Similar, but for input constraints. */
315 : :
316 : : bool
317 : 24510109 : 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 : 24510109 : const char *constraint = *constraint_p;
323 : 24510109 : const char *orig_constraint = constraint;
324 : 24510109 : size_t c_len = strlen (constraint);
325 : 24510109 : size_t j;
326 : 24510109 : bool saw_match = false;
327 : :
328 : : /* Assume the constraint doesn't allow the use of either
329 : : a register or memory. */
330 : 24510109 : *allows_mem = false;
331 : 24510109 : *allows_reg = false;
332 : :
333 : : /* Make sure constraint has neither `=', `+', nor '&'. */
334 : :
335 : 65615226 : for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
336 : 41105119 : switch (constraint[j])
337 : : {
338 : 468613 : case '+': case '=': case '&':
339 : 468613 : if (constraint == orig_constraint)
340 : : {
341 : 0 : error ("input operand constraint contains %qc", constraint[j]);
342 : 0 : return false;
343 : : }
344 : : break;
345 : :
346 : 378853 : case '%':
347 : 378853 : if (constraint == orig_constraint
348 : 378853 : && input_num + 1 == ninputs - ninout)
349 : : {
350 : 0 : error ("%<%%%> constraint used with last operand");
351 : 0 : 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 : 14960872 : case '0': case '1': case '2': case '3': case '4':
370 : 14960872 : case '5': case '6': case '7': case '8': case '9':
371 : 14960872 : {
372 : 14960872 : char *end;
373 : 14960872 : unsigned long match;
374 : :
375 : 14960872 : saw_match = true;
376 : :
377 : 14960872 : match = strtoul (constraint + j, &end, 10);
378 : 14960872 : if (match >= (unsigned long) noutputs)
379 : : {
380 : 0 : error ("matching constraint references invalid operand number");
381 : 0 : 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 : 14960872 : if (*end == '\0'
387 : 14896813 : && (j == 0 || (j == 1 && constraint[0] == '%')))
388 : : {
389 : 14885306 : constraint = constraints[match];
390 : 14885306 : *constraint_p = constraint;
391 : 14885306 : c_len = strlen (constraint);
392 : 14885306 : 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 : 14885306 : break;
398 : : }
399 : : else
400 : 75566 : j = end - constraint;
401 : : /* Anticipate increment at end of loop. */
402 : 75566 : j--;
403 : : }
404 : : /* Fall through. */
405 : :
406 : 2914383 : case 'g': case 'X':
407 : 2914383 : *allows_reg = true;
408 : 2914383 : *allows_mem = true;
409 : 2914383 : break;
410 : :
411 : 21877494 : default:
412 : 21877494 : if (! ISALPHA (constraint[j]))
413 : : {
414 : 2 : error ("invalid punctuation %qc in constraint", constraint[j]);
415 : 2 : return false;
416 : : }
417 : 21877492 : enum constraint_num cn = lookup_constraint (constraint + j);
418 : 21877492 : if (reg_class_for_constraint (cn) != NO_REGS
419 : 21877492 : || insn_extra_address_constraint (cn))
420 : 18975908 : *allows_reg = true;
421 : : else if (insn_extra_memory_constraint (cn)
422 : : || insn_extra_special_memory_constraint (cn)
423 : : || insn_extra_relaxed_memory_constraint (cn))
424 : 2664010 : *allows_mem = true;
425 : : else
426 : : insn_extra_constraint_allows_reg_mem (cn, allows_reg, allows_mem);
427 : : break;
428 : : }
429 : :
430 : 24510107 : if (saw_match && !*allows_reg)
431 : 0 : 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 : 171095 : decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED,
441 : : void *data)
442 : : {
443 : 171095 : tree decl = *declp;
444 : 171095 : const HARD_REG_SET *const regs = (const HARD_REG_SET *) data;
445 : :
446 : 171095 : if (VAR_P (decl))
447 : : {
448 : 21489 : if (DECL_HARD_REGISTER (decl)
449 : 1823 : && REG_P (DECL_RTL (decl))
450 : 23312 : && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
451 : : {
452 : 1823 : rtx reg = DECL_RTL (decl);
453 : :
454 : 1823 : if (overlaps_hard_reg_set_p (*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 : 171095 : 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 : 151562 : tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs)
468 : : {
469 : 151562 : 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 : 226402 : check_unique_operand_names (tree outputs, tree inputs, tree labels)
480 : : {
481 : 226402 : tree i, j, i_name = NULL_TREE;
482 : :
483 : 581686 : for (i = outputs; i ; i = TREE_CHAIN (i))
484 : : {
485 : 355284 : i_name = TREE_PURPOSE (TREE_PURPOSE (i));
486 : 355284 : if (! i_name)
487 : 354867 : continue;
488 : :
489 : 2337 : for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
490 : 1920 : if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
491 : 0 : goto failure;
492 : : }
493 : :
494 : 595570 : for (i = inputs; i ; i = TREE_CHAIN (i))
495 : : {
496 : 369174 : i_name = TREE_PURPOSE (TREE_PURPOSE (i));
497 : 369174 : if (! i_name)
498 : 369025 : continue;
499 : :
500 : 373 : for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
501 : 224 : if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
502 : 0 : goto failure;
503 : 462 : for (j = outputs; j ; j = TREE_CHAIN (j))
504 : 319 : if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
505 : 6 : goto failure;
506 : : }
507 : :
508 : 227175 : for (i = labels; i ; i = TREE_CHAIN (i))
509 : : {
510 : 789 : i_name = TREE_PURPOSE (i);
511 : 789 : if (! i_name)
512 : 0 : continue;
513 : :
514 : 2131 : for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
515 : 1347 : if (simple_cst_equal (i_name, TREE_PURPOSE (j)))
516 : 5 : goto failure;
517 : 1118 : for (j = inputs; j ; j = TREE_CHAIN (j))
518 : 339 : if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
519 : 5 : goto failure;
520 : : }
521 : :
522 : : return true;
523 : :
524 : 16 : failure:
525 : 16 : error ("duplicate %<asm%> operand name %qs", TREE_STRING_POINTER (i_name));
526 : 16 : 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 : 226402 : resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels)
536 : : {
537 : 226402 : char *buffer;
538 : 226402 : char *p;
539 : 226402 : const char *c;
540 : 226402 : tree t;
541 : :
542 : 226402 : 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 : 821978 : for (t = inputs; t ; t = TREE_CHAIN (t))
547 : : {
548 : 369174 : c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
549 : 369174 : if (strchr (c, '[') != NULL)
550 : : {
551 : 181 : p = buffer = xstrdup (c);
552 : 543 : while ((p = strchr (p, '[')) != NULL)
553 : 181 : p = resolve_operand_name_1 (p, outputs, inputs, NULL);
554 : 181 : TREE_VALUE (TREE_PURPOSE (t))
555 : 181 : = build_string (strlen (buffer), buffer);
556 : 181 : free (buffer);
557 : : }
558 : : }
559 : :
560 : : /* Now check for any needed substitutions in the template. */
561 : 226402 : c = TREE_STRING_POINTER (string);
562 : 276217 : while ((c = strchr (c, '%')) != NULL)
563 : : {
564 : 49978 : if (c[1] == '[')
565 : : break;
566 : 49910 : else if (ISALPHA (c[1]) && c[2] == '[')
567 : : break;
568 : : else
569 : : {
570 : 49815 : c += 1 + (c[1] == '%');
571 : 49815 : continue;
572 : : }
573 : : }
574 : :
575 : 226402 : 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 : 163 : buffer = xstrdup (TREE_STRING_POINTER (string));
582 : 163 : p = buffer + (c - TREE_STRING_POINTER (string));
583 : :
584 : 490 : while ((p = strchr (p, '%')) != NULL)
585 : : {
586 : 327 : if (p[1] == '[')
587 : 141 : p += 1;
588 : 186 : else if (ISALPHA (p[1]) && p[2] == '[')
589 : 147 : p += 2;
590 : : else
591 : : {
592 : 39 : p += 1 + (p[1] == '%');
593 : 39 : continue;
594 : : }
595 : :
596 : 288 : p = resolve_operand_name_1 (p, outputs, inputs, labels);
597 : : }
598 : :
599 : 163 : string = build_string (strlen (buffer), buffer);
600 : 163 : free (buffer);
601 : : }
602 : :
603 : 226402 : 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 : 469 : resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels)
613 : : {
614 : 469 : char *q;
615 : 469 : int op, op_inout;
616 : 469 : tree t;
617 : :
618 : : /* Collect the operand name. */
619 : 469 : q = strchr (++p, ']');
620 : 469 : if (!q)
621 : : {
622 : 0 : error ("missing close brace for named operand");
623 : 0 : return strchr (p, '\0');
624 : : }
625 : 469 : *q = '\0';
626 : :
627 : : /* Resolve the name to a number. */
628 : 1751 : for (op_inout = op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
629 : : {
630 : 1524 : tree name = TREE_PURPOSE (TREE_PURPOSE (t));
631 : 2793 : if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
632 : 242 : goto found;
633 : 1282 : tree constraint = TREE_VALUE (TREE_PURPOSE (t));
634 : 2564 : if (constraint && strchr (TREE_STRING_POINTER (constraint), '+') != NULL)
635 : 64 : op_inout++;
636 : : }
637 : 406 : for (t = inputs; t ; t = TREE_CHAIN (t), op++)
638 : : {
639 : 302 : tree name = TREE_PURPOSE (TREE_PURPOSE (t));
640 : 493 : if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
641 : 123 : goto found;
642 : : }
643 : 104 : op += op_inout;
644 : 113 : for (t = labels; t ; t = TREE_CHAIN (t), op++)
645 : : {
646 : 110 : tree name = TREE_PURPOSE (t);
647 : 220 : if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
648 : 101 : goto found;
649 : : }
650 : :
651 : 3 : error ("undefined named operand %qs", identifier_to_locale (p));
652 : 3 : op = 0;
653 : :
654 : 469 : 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 : 469 : sprintf (--p, "%d", op);
659 : 469 : p = strchr (p, '\0');
660 : :
661 : : /* Verify the no extra buffer space assumption. */
662 : 469 : gcc_assert (p <= q);
663 : :
664 : : /* Shift the rest of the buffer down to fill the gap. */
665 : 469 : memmove (p, q + 1, strlen (q + 1) + 1);
666 : :
667 : 469 : 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 : 378 : expand_naked_return (void)
676 : : {
677 : 378 : rtx_code_label *end_label;
678 : :
679 : 378 : clear_pending_stack_adjust ();
680 : 378 : do_pending_stack_adjust ();
681 : :
682 : 378 : end_label = naked_return_label;
683 : 378 : if (end_label == 0)
684 : 378 : end_label = naked_return_label = gen_label_rtx ();
685 : :
686 : 378 : emit_jump (end_label);
687 : 378 : }
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 : 0 : do_jump_if_equal (machine_mode mode, rtx op0, rtx op1, rtx_code_label *label,
693 : : int unsignedp, profile_probability prob)
694 : : {
695 : 0 : do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
696 : : NULL_RTX, NULL, label, prob);
697 : 0 : }
698 : :
699 : : /* Return the sum of probabilities of outgoing edges of basic block BB. */
700 : :
701 : : static profile_probability
702 : 16372 : get_outgoing_edge_probs (basic_block bb)
703 : : {
704 : 16372 : edge e;
705 : 16372 : edge_iterator ei;
706 : 16372 : profile_probability prob_sum = profile_probability::never ();
707 : 16372 : if (!bb)
708 : 0 : return profile_probability::never ();
709 : 154016 : FOR_EACH_EDGE (e, ei, bb->succs)
710 : 137644 : prob_sum += e->probability;
711 : 16372 : 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 : 29676 : conditional_probability (profile_probability target_prob,
723 : : profile_probability base_prob)
724 : : {
725 : 29676 : 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 : 16372 : 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 : 16372 : int i, ncases;
749 : 16372 : auto_vec<rtx> labelvec;
750 : 16372 : rtx_insn *fallback_label = label_rtx (case_list[0].m_code_label);
751 : 16372 : rtx_code_label *table_label = gen_label_rtx ();
752 : 16372 : bool has_gaps = false;
753 : 16372 : profile_probability default_prob = default_edge ? default_edge->probability
754 : 16372 : : profile_probability::never ();
755 : 16372 : profile_probability base = get_outgoing_edge_probs (stmt_bb);
756 : 16372 : bool try_with_tablejump = false;
757 : :
758 : 16372 : profile_probability new_default_prob = conditional_probability (default_prob,
759 : : base);
760 : :
761 : 16372 : 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 : 16372 : if (optimize_insn_for_speed_p ()
769 : 16146 : && compare_tree_int (minval, 0) > 0
770 : 28951 : && compare_tree_int (minval, 3) < 0)
771 : : {
772 : 1421 : minval = build_int_cst (index_type, 0);
773 : 1421 : range = maxval;
774 : 1421 : 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 : 16372 : ncases = tree_to_shwi (range) + 1;
782 : 16372 : labelvec.safe_grow_cleared (ncases);
783 : :
784 : 346414 : for (unsigned j = 0; j < case_list.length (); j++)
785 : : {
786 : 156835 : 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 : 156835 : HOST_WIDE_INT i_low
791 : 156835 : = tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
792 : 156835 : n->m_low, minval));
793 : 156835 : HOST_WIDE_INT i_high
794 : 156835 : = tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
795 : 156835 : n->m_high, minval));
796 : 156835 : HOST_WIDE_INT i;
797 : :
798 : 340404 : for (i = i_low; i <= i_high; i ++)
799 : 550707 : labelvec[i]
800 : 183569 : = 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 : 16372 : rtx gap_label = (default_label) ? default_label : fallback_label;
809 : :
810 : 378240 : for (i = 0; i < ncases; i++)
811 : 361868 : if (labelvec[i] == 0)
812 : : {
813 : 178299 : has_gaps = true;
814 : 178299 : labelvec[i] = gen_rtx_LABEL_REF (Pmode, gap_label);
815 : : }
816 : :
817 : 16372 : 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 : 13304 : new_default_prob = conditional_probability (default_prob / 2, base);
825 : 13304 : default_prob /= 2;
826 : 13304 : base -= default_prob;
827 : : }
828 : : else
829 : : {
830 : 3068 : base -= default_prob;
831 : 3068 : default_prob = profile_probability::never ();
832 : : }
833 : :
834 : 16372 : if (default_edge)
835 : 14949 : 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 : 16372 : if (base > profile_probability::never ())
841 : : {
842 : 16372 : edge e;
843 : 16372 : edge_iterator ei;
844 : 154016 : FOR_EACH_EDGE (e, ei, stmt_bb->succs)
845 : 137644 : e->probability /= base;
846 : : }
847 : :
848 : 16372 : if (try_with_tablejump)
849 : : {
850 : 16372 : bool ok = try_tablejump (index_type, index_expr, minval, range,
851 : : table_label, default_label, new_default_prob);
852 : 16372 : gcc_assert (ok);
853 : : }
854 : : /* Output the table. */
855 : 16372 : emit_label (table_label);
856 : :
857 : 16372 : if (CASE_VECTOR_PC_RELATIVE
858 : 16372 : || (flag_pic && targetm.asm_out.generate_pic_addr_diff_vec ()))
859 : 3225 : 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 : 31131 : 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 : 16372 : emit_barrier ();
870 : 16372 : }
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 : 16372 : expand_case (gswitch *stmt)
880 : : {
881 : 16372 : tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
882 : 16372 : rtx_code_label *default_label;
883 : 16372 : unsigned int count;
884 : 16372 : int i;
885 : 16372 : int ncases = gimple_switch_num_labels (stmt);
886 : 16372 : tree index_expr = gimple_switch_index (stmt);
887 : 16372 : tree index_type = TREE_TYPE (index_expr);
888 : 16372 : tree elt;
889 : 16372 : basic_block bb = gimple_bb (stmt);
890 : 16372 : gimple *def_stmt;
891 : :
892 : 16372 : 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 : 16372 : if (index_type == error_mark_node)
897 : 0 : return;
898 : :
899 : : /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
900 : : expressions being INTEGER_CST. */
901 : 16372 : 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 : 16372 : gcc_assert (ncases > 1);
906 : :
907 : 16372 : do_pending_stack_adjust ();
908 : :
909 : : /* Find the default case target label. */
910 : 16372 : tree default_lab = CASE_LABEL (gimple_switch_default_label (stmt));
911 : 16372 : default_label = jump_target_rtx (default_lab);
912 : 16372 : basic_block default_bb = label_to_block (cfun, default_lab);
913 : 16372 : edge default_edge = find_edge (bb, default_bb);
914 : :
915 : : /* Get upper and lower bounds of case values. */
916 : 16372 : elt = gimple_switch_label (stmt, 1);
917 : 16372 : minval = fold_convert (index_type, CASE_LOW (elt));
918 : 16372 : elt = gimple_switch_label (stmt, ncases - 1);
919 : 16372 : if (CASE_HIGH (elt))
920 : 142 : maxval = fold_convert (index_type, CASE_HIGH (elt));
921 : : else
922 : 16230 : 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 : 16372 : if (TYPE_PRECISION (index_type) > BITS_PER_WORD
929 : 6 : && TREE_CODE (index_expr) == SSA_NAME
930 : 6 : && (def_stmt = SSA_NAME_DEF_STMT (index_expr))
931 : 6 : && is_gimple_assign (def_stmt)
932 : 16375 : && gimple_assign_rhs_code (def_stmt) == NOP_EXPR)
933 : : {
934 : 0 : tree inner_index_expr = gimple_assign_rhs1 (def_stmt);
935 : 0 : tree inner_index_type = TREE_TYPE (inner_index_expr);
936 : :
937 : 0 : if (INTEGRAL_TYPE_P (inner_index_type)
938 : 0 : && TYPE_PRECISION (inner_index_type) <= BITS_PER_WORD
939 : 0 : && int_fits_type_p (minval, inner_index_type)
940 : 0 : && int_fits_type_p (maxval, inner_index_type))
941 : : {
942 : 0 : index_expr = inner_index_expr;
943 : 0 : index_type = inner_index_type;
944 : 0 : minval = fold_convert (index_type, minval);
945 : 0 : maxval = fold_convert (index_type, maxval);
946 : : }
947 : : }
948 : :
949 : : /* Compute span of values. */
950 : 16372 : 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 : 16372 : count = 0;
955 : :
956 : 173207 : for (i = ncases - 1; i >= 1; --i)
957 : : {
958 : 156835 : elt = gimple_switch_label (stmt, i);
959 : 156835 : tree low = CASE_LOW (elt);
960 : 156835 : gcc_assert (low);
961 : 156835 : tree high = CASE_HIGH (elt);
962 : 156835 : gcc_assert (! high || tree_int_cst_lt (low, high));
963 : 156835 : tree lab = CASE_LABEL (elt);
964 : :
965 : : /* Count the elements.
966 : : A range counts double, since it requires two compares. */
967 : 156835 : count++;
968 : 156835 : if (high)
969 : 21620 : 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 : 156835 : low = fold_convert (index_type, low);
977 : 156835 : if (TREE_OVERFLOW (low))
978 : 0 : low = wide_int_to_tree (index_type, wi::to_wide (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 : 156835 : if (! high)
984 : 135215 : high = low;
985 : 156835 : high = fold_convert (index_type, high);
986 : 156835 : if (TREE_OVERFLOW (high))
987 : 0 : high = wide_int_to_tree (index_type, wi::to_wide (high));
988 : :
989 : 156835 : case_list.safe_push (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 : 16372 : gcc_assert (count > 0);
997 : :
998 : 16372 : 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 : 16372 : if (EDGE_COUNT (default_edge->dest->succs) == 0
1005 : 18488 : && gimple_seq_unreachable_p (bb_seq (default_edge->dest)))
1006 : : {
1007 : 1423 : default_label = NULL;
1008 : 1423 : remove_edge (default_edge);
1009 : 1423 : default_edge = NULL;
1010 : : }
1011 : :
1012 : 16372 : emit_case_dispatch_table (index_expr, index_type,
1013 : : case_list, default_label, default_edge,
1014 : : minval, maxval, range, bb);
1015 : :
1016 : 16372 : reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
1017 : :
1018 : 16372 : free_temp_slots ();
1019 : 16372 : }
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 : 0 : expand_sjlj_dispatch_table (rtx dispatch_index,
1036 : : vec<tree> dispatch_table)
1037 : : {
1038 : 0 : tree index_type = integer_type_node;
1039 : 0 : machine_mode index_mode = TYPE_MODE (index_type);
1040 : :
1041 : 0 : int ncases = dispatch_table.length ();
1042 : :
1043 : 0 : do_pending_stack_adjust ();
1044 : 0 : 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 : 0 : if (dispatch_table.length () <= 5
1052 : 0 : || (!targetm.have_casesi () && !targetm.have_tablejump ())
1053 : 0 : || !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 : 0 : rtx index = copy_to_mode_reg (index_mode, dispatch_index);
1070 : 0 : rtx zero = CONST0_RTX (index_mode);
1071 : 0 : for (int i = 0; i < ncases; i++)
1072 : : {
1073 : 0 : tree elt = dispatch_table[i];
1074 : 0 : rtx_code_label *lab = jump_target_rtx (CASE_LABEL (elt));
1075 : 0 : do_jump_if_equal (index_mode, index, zero, lab, 0,
1076 : : profile_probability::uninitialized ());
1077 : 0 : 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 : 0 : auto_vec<simple_case_node> case_list;
1086 : 0 : tree index_expr = make_tree (index_type, dispatch_index);
1087 : 0 : tree minval = build_int_cst (index_type, 0);
1088 : 0 : tree maxval = CASE_LOW (dispatch_table.last ());
1089 : 0 : tree range = maxval;
1090 : 0 : rtx_code_label *default_label = gen_label_rtx ();
1091 : :
1092 : 0 : for (int i = ncases - 1; i >= 0; --i)
1093 : : {
1094 : 0 : tree elt = dispatch_table[i];
1095 : 0 : tree high = CASE_HIGH (elt);
1096 : 0 : if (high == NULL_TREE)
1097 : 0 : high = CASE_LOW (elt);
1098 : 0 : case_list.safe_push (simple_case_node (CASE_LOW (elt), high,
1099 : 0 : CASE_LABEL (elt)));
1100 : : }
1101 : :
1102 : 0 : emit_case_dispatch_table (index_expr, index_type,
1103 : : case_list, default_label, NULL,
1104 : : minval, maxval, range,
1105 : 0 : BLOCK_FOR_INSN (before_case));
1106 : 0 : emit_label (default_label);
1107 : 0 : }
1108 : :
1109 : : /* Dispatching something not handled? Trap! */
1110 : 0 : expand_builtin_trap ();
1111 : :
1112 : 0 : reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
1113 : :
1114 : 0 : free_temp_slots ();
1115 : 0 : }
1116 : :
1117 : :
|