1 /* Expands front end tree to back end RTL for GCC
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
3 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
4 2010, 2011, 2012 Free Software Foundation, Inc.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
21
22 /* This file handles the generation of rtl code from tree structure
23 above the level of expressions, using subroutines in exp*.c and emit-rtl.c.
24 The functions whose names start with `expand_' are called by the
25 expander to generate RTL instructions for various kinds of constructs. */
26
27 #include "config.h"
28 #include "system.h"
29 #include "coretypes.h"
30 #include "tm.h"
31
32 #include "rtl.h"
33 #include "hard-reg-set.h"
34 #include "tree.h"
35 #include "tm_p.h"
36 #include "flags.h"
37 #include "except.h"
38 #include "function.h"
39 #include "insn-config.h"
40 #include "expr.h"
41 #include "libfuncs.h"
42 #include "recog.h"
43 #include "machmode.h"
44 #include "diagnostic-core.h"
45 #include "output.h"
46 #include "ggc.h"
47 #include "langhooks.h"
48 #include "predict.h"
49 #include "optabs.h"
50 #include "target.h"
51 #include "gimple.h"
52 #include "regs.h"
53 #include "alloc-pool.h"
54 #include "pretty-print.h"
55 #include "bitmap.h"
56 #include "params.h"
57
58
59 /* Functions and data structures for expanding case statements. */
60
61 /* Case label structure, used to hold info on labels within case
62 statements. We handle "range" labels; for a single-value label
63 as in C, the high and low limits are the same.
64
65 We start with a vector of case nodes sorted in ascending order, and
66 the default label as the last element in the vector. Before expanding
67 to RTL, we transform this vector into a list linked via the RIGHT
68 fields in the case_node struct. Nodes with higher case values are
69 later in the list.
70
71 Switch statements can be output in three forms. A branch table is
72 used if there are more than a few labels and the labels are dense
73 within the range between the smallest and largest case value. If a
74 branch table is used, no further manipulations are done with the case
75 node chain.
76
77 The alternative to the use of a branch table is to generate a series
78 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
79 and PARENT fields to hold a binary tree. Initially the tree is
80 totally unbalanced, with everything on the right. We balance the tree
81 with nodes on the left having lower case values than the parent
82 and nodes on the right having higher values. We then output the tree
83 in order.
84
85 For very small, suitable switch statements, we can generate a series
86 of simple bit test and branches instead. */
87
88 struct case_node
89 {
90 struct case_node *left; /* Left son in binary tree */
91 struct case_node *right; /* Right son in binary tree; also node chain */
92 struct case_node *parent; /* Parent of node in binary tree */
93 tree low; /* Lowest index value for this label */
94 tree high; /* Highest index value for this label */
95 tree code_label; /* Label to jump to when node matches */
96 };
97
98 typedef struct case_node case_node;
99 typedef struct case_node *case_node_ptr;
100
101 /* These are used by estimate_case_costs and balance_case_nodes. */
102
103 /* This must be a signed type, and non-ANSI compilers lack signed char. */
104 static short cost_table_[129];
105 static int use_cost_table;
106 static int cost_table_initialized;
107
108 /* Special care is needed because we allow -1, but TREE_INT_CST_LOW
109 is unsigned. */
110 #define COST_TABLE(I) cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)]
111
112 static int n_occurrences (int, const char *);
113 static bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *);
114 static void expand_nl_goto_receiver (void);
115 static bool check_operand_nalternatives (tree, tree);
116 static bool check_unique_operand_names (tree, tree, tree);
117 static char *resolve_operand_name_1 (char *, tree, tree, tree);
118 static void expand_null_return_1 (void);
119 static void expand_value_return (rtx);
120 static int estimate_case_costs (case_node_ptr);
121 static bool lshift_cheap_p (void);
122 static int case_bit_test_cmp (const void *, const void *);
123 static void emit_case_bit_tests (tree, tree, tree, tree, case_node_ptr, rtx);
124 static void balance_case_nodes (case_node_ptr *, case_node_ptr);
125 static int node_has_low_bound (case_node_ptr, tree);
126 static int node_has_high_bound (case_node_ptr, tree);
127 static int node_is_bounded (case_node_ptr, tree);
128 static void emit_case_nodes (rtx, case_node_ptr, rtx, tree);
129 static struct case_node *add_case_node (struct case_node *, tree,
130 tree, tree, tree, alloc_pool);
131
132
133 /* Return the rtx-label that corresponds to a LABEL_DECL,
134 creating it if necessary. */
135
136 rtx
label_rtx(tree label)137 label_rtx (tree label)
138 {
139 gcc_assert (TREE_CODE (label) == LABEL_DECL);
140
141 if (!DECL_RTL_SET_P (label))
142 {
143 rtx r = gen_label_rtx ();
144 SET_DECL_RTL (label, r);
145 if (FORCED_LABEL (label) || DECL_NONLOCAL (label))
146 LABEL_PRESERVE_P (r) = 1;
147 }
148
149 return DECL_RTL (label);
150 }
151
152 /* As above, but also put it on the forced-reference list of the
153 function that contains it. */
154 rtx
force_label_rtx(tree label)155 force_label_rtx (tree label)
156 {
157 rtx ref = label_rtx (label);
158 tree function = decl_function_context (label);
159
160 gcc_assert (function);
161
162 forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref, forced_labels);
163 return ref;
164 }
165
166 /* Add an unconditional jump to LABEL as the next sequential instruction. */
167
168 void
emit_jump(rtx label)169 emit_jump (rtx label)
170 {
171 do_pending_stack_adjust ();
172 emit_jump_insn (gen_jump (label));
173 emit_barrier ();
174 }
175
176 /* Emit code to jump to the address
177 specified by the pointer expression EXP. */
178
179 void
expand_computed_goto(tree exp)180 expand_computed_goto (tree exp)
181 {
182 rtx x = expand_normal (exp);
183
184 x = convert_memory_address (Pmode, x);
185
186 do_pending_stack_adjust ();
187 emit_indirect_jump (x);
188 }
189
190 /* Handle goto statements and the labels that they can go to. */
191
192 /* Specify the location in the RTL code of a label LABEL,
193 which is a LABEL_DECL tree node.
194
195 This is used for the kind of label that the user can jump to with a
196 goto statement, and for alternatives of a switch or case statement.
197 RTL labels generated for loops and conditionals don't go through here;
198 they are generated directly at the RTL level, by other functions below.
199
200 Note that this has nothing to do with defining label *names*.
201 Languages vary in how they do that and what that even means. */
202
203 void
expand_label(tree label)204 expand_label (tree label)
205 {
206 rtx label_r = label_rtx (label);
207
208 do_pending_stack_adjust ();
209 emit_label (label_r);
210 if (DECL_NAME (label))
211 LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label));
212
213 if (DECL_NONLOCAL (label))
214 {
215 expand_nl_goto_receiver ();
216 nonlocal_goto_handler_labels
217 = gen_rtx_EXPR_LIST (VOIDmode, label_r,
218 nonlocal_goto_handler_labels);
219 }
220
221 if (FORCED_LABEL (label))
222 forced_labels = gen_rtx_EXPR_LIST (VOIDmode, label_r, forced_labels);
223
224 if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
225 maybe_set_first_label_num (label_r);
226 }
227
228 /* Generate RTL code for a `goto' statement with target label LABEL.
229 LABEL should be a LABEL_DECL tree node that was or will later be
230 defined with `expand_label'. */
231
232 void
expand_goto(tree label)233 expand_goto (tree label)
234 {
235 #ifdef ENABLE_CHECKING
236 /* Check for a nonlocal goto to a containing function. Should have
237 gotten translated to __builtin_nonlocal_goto. */
238 tree context = decl_function_context (label);
239 gcc_assert (!context || context == current_function_decl);
240 #endif
241
242 emit_jump (label_rtx (label));
243 }
244
245 /* Return the number of times character C occurs in string S. */
246 static int
n_occurrences(int c,const char * s)247 n_occurrences (int c, const char *s)
248 {
249 int n = 0;
250 while (*s)
251 n += (*s++ == c);
252 return n;
253 }
254
255 /* Generate RTL for an asm statement (explicit assembler code).
256 STRING is a STRING_CST node containing the assembler code text,
257 or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the
258 insn is volatile; don't optimize it. */
259
260 static void
expand_asm_loc(tree string,int vol,location_t locus)261 expand_asm_loc (tree string, int vol, location_t locus)
262 {
263 rtx body;
264
265 if (TREE_CODE (string) == ADDR_EXPR)
266 string = TREE_OPERAND (string, 0);
267
268 body = gen_rtx_ASM_INPUT_loc (VOIDmode,
269 ggc_strdup (TREE_STRING_POINTER (string)),
270 locus);
271
272 MEM_VOLATILE_P (body) = vol;
273
274 emit_insn (body);
275 }
276
277 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
278 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
279 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
280 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
281 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
282 constraint allows the use of a register operand. And, *IS_INOUT
283 will be true if the operand is read-write, i.e., if it is used as
284 an input as well as an output. If *CONSTRAINT_P is not in
285 canonical form, it will be made canonical. (Note that `+' will be
286 replaced with `=' as part of this process.)
287
288 Returns TRUE if all went well; FALSE if an error occurred. */
289
290 bool
parse_output_constraint(const char ** constraint_p,int operand_num,int ninputs,int noutputs,bool * allows_mem,bool * allows_reg,bool * is_inout)291 parse_output_constraint (const char **constraint_p, int operand_num,
292 int ninputs, int noutputs, bool *allows_mem,
293 bool *allows_reg, bool *is_inout)
294 {
295 const char *constraint = *constraint_p;
296 const char *p;
297
298 /* Assume the constraint doesn't allow the use of either a register
299 or memory. */
300 *allows_mem = false;
301 *allows_reg = false;
302
303 /* Allow the `=' or `+' to not be at the beginning of the string,
304 since it wasn't explicitly documented that way, and there is a
305 large body of code that puts it last. Swap the character to
306 the front, so as not to uglify any place else. */
307 p = strchr (constraint, '=');
308 if (!p)
309 p = strchr (constraint, '+');
310
311 /* If the string doesn't contain an `=', issue an error
312 message. */
313 if (!p)
314 {
315 error ("output operand constraint lacks %<=%>");
316 return false;
317 }
318
319 /* If the constraint begins with `+', then the operand is both read
320 from and written to. */
321 *is_inout = (*p == '+');
322
323 /* Canonicalize the output constraint so that it begins with `='. */
324 if (p != constraint || *is_inout)
325 {
326 char *buf;
327 size_t c_len = strlen (constraint);
328
329 if (p != constraint)
330 warning (0, "output constraint %qc for operand %d "
331 "is not at the beginning",
332 *p, operand_num);
333
334 /* Make a copy of the constraint. */
335 buf = XALLOCAVEC (char, c_len + 1);
336 strcpy (buf, constraint);
337 /* Swap the first character and the `=' or `+'. */
338 buf[p - constraint] = buf[0];
339 /* Make sure the first character is an `='. (Until we do this,
340 it might be a `+'.) */
341 buf[0] = '=';
342 /* Replace the constraint with the canonicalized string. */
343 *constraint_p = ggc_alloc_string (buf, c_len);
344 constraint = *constraint_p;
345 }
346
347 /* Loop through the constraint string. */
348 for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p))
349 switch (*p)
350 {
351 case '+':
352 case '=':
353 error ("operand constraint contains incorrectly positioned "
354 "%<+%> or %<=%>");
355 return false;
356
357 case '%':
358 if (operand_num + 1 == ninputs + noutputs)
359 {
360 error ("%<%%%> constraint used with last operand");
361 return false;
362 }
363 break;
364
365 case 'V': case TARGET_MEM_CONSTRAINT: case 'o':
366 *allows_mem = true;
367 break;
368
369 case '?': case '!': case '*': case '&': case '#':
370 case 'E': case 'F': case 'G': case 'H':
371 case 's': case 'i': case 'n':
372 case 'I': case 'J': case 'K': case 'L': case 'M':
373 case 'N': case 'O': case 'P': case ',':
374 break;
375
376 case '0': case '1': case '2': case '3': case '4':
377 case '5': case '6': case '7': case '8': case '9':
378 case '[':
379 error ("matching constraint not valid in output operand");
380 return false;
381
382 case '<': case '>':
383 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
384 excepting those that expand_call created. So match memory
385 and hope. */
386 *allows_mem = true;
387 break;
388
389 case 'g': case 'X':
390 *allows_reg = true;
391 *allows_mem = true;
392 break;
393
394 case 'p': case 'r':
395 *allows_reg = true;
396 break;
397
398 default:
399 if (!ISALPHA (*p))
400 break;
401 if (REG_CLASS_FROM_CONSTRAINT (*p, p) != NO_REGS)
402 *allows_reg = true;
403 #ifdef EXTRA_CONSTRAINT_STR
404 else if (EXTRA_ADDRESS_CONSTRAINT (*p, p))
405 *allows_reg = true;
406 else if (EXTRA_MEMORY_CONSTRAINT (*p, p))
407 *allows_mem = true;
408 else
409 {
410 /* Otherwise we can't assume anything about the nature of
411 the constraint except that it isn't purely registers.
412 Treat it like "g" and hope for the best. */
413 *allows_reg = true;
414 *allows_mem = true;
415 }
416 #endif
417 break;
418 }
419
420 return true;
421 }
422
423 /* Similar, but for input constraints. */
424
425 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)426 parse_input_constraint (const char **constraint_p, int input_num,
427 int ninputs, int noutputs, int ninout,
428 const char * const * constraints,
429 bool *allows_mem, bool *allows_reg)
430 {
431 const char *constraint = *constraint_p;
432 const char *orig_constraint = constraint;
433 size_t c_len = strlen (constraint);
434 size_t j;
435 bool saw_match = false;
436
437 /* Assume the constraint doesn't allow the use of either
438 a register or memory. */
439 *allows_mem = false;
440 *allows_reg = false;
441
442 /* Make sure constraint has neither `=', `+', nor '&'. */
443
444 for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
445 switch (constraint[j])
446 {
447 case '+': case '=': case '&':
448 if (constraint == orig_constraint)
449 {
450 error ("input operand constraint contains %qc", constraint[j]);
451 return false;
452 }
453 break;
454
455 case '%':
456 if (constraint == orig_constraint
457 && input_num + 1 == ninputs - ninout)
458 {
459 error ("%<%%%> constraint used with last operand");
460 return false;
461 }
462 break;
463
464 case 'V': case TARGET_MEM_CONSTRAINT: case 'o':
465 *allows_mem = true;
466 break;
467
468 case '<': case '>':
469 case '?': case '!': case '*': case '#':
470 case 'E': case 'F': case 'G': case 'H':
471 case 's': case 'i': case 'n':
472 case 'I': case 'J': case 'K': case 'L': case 'M':
473 case 'N': case 'O': case 'P': case ',':
474 break;
475
476 /* Whether or not a numeric constraint allows a register is
477 decided by the matching constraint, and so there is no need
478 to do anything special with them. We must handle them in
479 the default case, so that we don't unnecessarily force
480 operands to memory. */
481 case '0': case '1': case '2': case '3': case '4':
482 case '5': case '6': case '7': case '8': case '9':
483 {
484 char *end;
485 unsigned long match;
486
487 saw_match = true;
488
489 match = strtoul (constraint + j, &end, 10);
490 if (match >= (unsigned long) noutputs)
491 {
492 error ("matching constraint references invalid operand number");
493 return false;
494 }
495
496 /* Try and find the real constraint for this dup. Only do this
497 if the matching constraint is the only alternative. */
498 if (*end == '\0'
499 && (j == 0 || (j == 1 && constraint[0] == '%')))
500 {
501 constraint = constraints[match];
502 *constraint_p = constraint;
503 c_len = strlen (constraint);
504 j = 0;
505 /* ??? At the end of the loop, we will skip the first part of
506 the matched constraint. This assumes not only that the
507 other constraint is an output constraint, but also that
508 the '=' or '+' come first. */
509 break;
510 }
511 else
512 j = end - constraint;
513 /* Anticipate increment at end of loop. */
514 j--;
515 }
516 /* Fall through. */
517
518 case 'p': case 'r':
519 *allows_reg = true;
520 break;
521
522 case 'g': case 'X':
523 *allows_reg = true;
524 *allows_mem = true;
525 break;
526
527 default:
528 if (! ISALPHA (constraint[j]))
529 {
530 error ("invalid punctuation %qc in constraint", constraint[j]);
531 return false;
532 }
533 if (REG_CLASS_FROM_CONSTRAINT (constraint[j], constraint + j)
534 != NO_REGS)
535 *allows_reg = true;
536 #ifdef EXTRA_CONSTRAINT_STR
537 else if (EXTRA_ADDRESS_CONSTRAINT (constraint[j], constraint + j))
538 *allows_reg = true;
539 else if (EXTRA_MEMORY_CONSTRAINT (constraint[j], constraint + j))
540 *allows_mem = true;
541 else
542 {
543 /* Otherwise we can't assume anything about the nature of
544 the constraint except that it isn't purely registers.
545 Treat it like "g" and hope for the best. */
546 *allows_reg = true;
547 *allows_mem = true;
548 }
549 #endif
550 break;
551 }
552
553 if (saw_match && !*allows_reg)
554 warning (0, "matching constraint does not allow a register");
555
556 return true;
557 }
558
559 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
560 can be an asm-declared register. Called via walk_tree. */
561
562 static tree
decl_overlaps_hard_reg_set_p(tree * declp,int * walk_subtrees ATTRIBUTE_UNUSED,void * data)563 decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED,
564 void *data)
565 {
566 tree decl = *declp;
567 const HARD_REG_SET *const regs = (const HARD_REG_SET *) data;
568
569 if (TREE_CODE (decl) == VAR_DECL)
570 {
571 if (DECL_HARD_REGISTER (decl)
572 && REG_P (DECL_RTL (decl))
573 && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
574 {
575 rtx reg = DECL_RTL (decl);
576
577 if (overlaps_hard_reg_set_p (*regs, GET_MODE (reg), REGNO (reg)))
578 return decl;
579 }
580 walk_subtrees = 0;
581 }
582 else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL)
583 walk_subtrees = 0;
584 return NULL_TREE;
585 }
586
587 /* If there is an overlap between *REGS and DECL, return the first overlap
588 found. */
589 tree
tree_overlaps_hard_reg_set(tree decl,HARD_REG_SET * regs)590 tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs)
591 {
592 return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL);
593 }
594
595 /* Check for overlap between registers marked in CLOBBERED_REGS and
596 anything inappropriate in T. Emit error and return the register
597 variable definition for error, NULL_TREE for ok. */
598
599 static bool
tree_conflicts_with_clobbers_p(tree t,HARD_REG_SET * clobbered_regs)600 tree_conflicts_with_clobbers_p (tree t, HARD_REG_SET *clobbered_regs)
601 {
602 /* Conflicts between asm-declared register variables and the clobber
603 list are not allowed. */
604 tree overlap = tree_overlaps_hard_reg_set (t, clobbered_regs);
605
606 if (overlap)
607 {
608 error ("asm-specifier for variable %qE conflicts with asm clobber list",
609 DECL_NAME (overlap));
610
611 /* Reset registerness to stop multiple errors emitted for a single
612 variable. */
613 DECL_REGISTER (overlap) = 0;
614 return true;
615 }
616
617 return false;
618 }
619
620 /* Generate RTL for an asm statement with arguments.
621 STRING is the instruction template.
622 OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs.
623 Each output or input has an expression in the TREE_VALUE and
624 a tree list in TREE_PURPOSE which in turn contains a constraint
625 name in TREE_VALUE (or NULL_TREE) and a constraint string
626 in TREE_PURPOSE.
627 CLOBBERS is a list of STRING_CST nodes each naming a hard register
628 that is clobbered by this insn.
629
630 Not all kinds of lvalue that may appear in OUTPUTS can be stored directly.
631 Some elements of OUTPUTS may be replaced with trees representing temporary
632 values. The caller should copy those temporary values to the originally
633 specified lvalues.
634
635 VOL nonzero means the insn is volatile; don't optimize it. */
636
637 static void
expand_asm_operands(tree string,tree outputs,tree inputs,tree clobbers,tree labels,int vol,location_t locus)638 expand_asm_operands (tree string, tree outputs, tree inputs,
639 tree clobbers, tree labels, int vol, location_t locus)
640 {
641 rtvec argvec, constraintvec, labelvec;
642 rtx body;
643 int ninputs = list_length (inputs);
644 int noutputs = list_length (outputs);
645 int nlabels = list_length (labels);
646 int ninout;
647 int nclobbers;
648 HARD_REG_SET clobbered_regs;
649 int clobber_conflict_found = 0;
650 tree tail;
651 tree t;
652 int i;
653 /* Vector of RTX's of evaluated output operands. */
654 rtx *output_rtx = XALLOCAVEC (rtx, noutputs);
655 int *inout_opnum = XALLOCAVEC (int, noutputs);
656 rtx *real_output_rtx = XALLOCAVEC (rtx, noutputs);
657 enum machine_mode *inout_mode = XALLOCAVEC (enum machine_mode, noutputs);
658 const char **constraints = XALLOCAVEC (const char *, noutputs + ninputs);
659 int old_generating_concat_p = generating_concat_p;
660
661 /* An ASM with no outputs needs to be treated as volatile, for now. */
662 if (noutputs == 0)
663 vol = 1;
664
665 if (! check_operand_nalternatives (outputs, inputs))
666 return;
667
668 string = resolve_asm_operand_names (string, outputs, inputs, labels);
669
670 /* Collect constraints. */
671 i = 0;
672 for (t = outputs; t ; t = TREE_CHAIN (t), i++)
673 constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
674 for (t = inputs; t ; t = TREE_CHAIN (t), i++)
675 constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
676
677 /* Sometimes we wish to automatically clobber registers across an asm.
678 Case in point is when the i386 backend moved from cc0 to a hard reg --
679 maintaining source-level compatibility means automatically clobbering
680 the flags register. */
681 clobbers = targetm.md_asm_clobbers (outputs, inputs, clobbers);
682
683 /* Count the number of meaningful clobbered registers, ignoring what
684 we would ignore later. */
685 nclobbers = 0;
686 CLEAR_HARD_REG_SET (clobbered_regs);
687 for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
688 {
689 const char *regname;
690 int nregs;
691
692 if (TREE_VALUE (tail) == error_mark_node)
693 return;
694 regname = TREE_STRING_POINTER (TREE_VALUE (tail));
695
696 i = decode_reg_name_and_count (regname, &nregs);
697 if (i == -4)
698 ++nclobbers;
699 else if (i == -2)
700 error ("unknown register name %qs in %<asm%>", regname);
701
702 /* Mark clobbered registers. */
703 if (i >= 0)
704 {
705 int reg;
706
707 for (reg = i; reg < i + nregs; reg++)
708 {
709 ++nclobbers;
710
711 /* Clobbering the PIC register is an error. */
712 if (reg == (int) PIC_OFFSET_TABLE_REGNUM)
713 {
714 error ("PIC register clobbered by %qs in %<asm%>", regname);
715 return;
716 }
717
718 SET_HARD_REG_BIT (clobbered_regs, reg);
719 }
720 }
721 }
722
723 /* First pass over inputs and outputs checks validity and sets
724 mark_addressable if needed. */
725
726 ninout = 0;
727 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
728 {
729 tree val = TREE_VALUE (tail);
730 tree type = TREE_TYPE (val);
731 const char *constraint;
732 bool is_inout;
733 bool allows_reg;
734 bool allows_mem;
735
736 /* If there's an erroneous arg, emit no insn. */
737 if (type == error_mark_node)
738 return;
739
740 /* Try to parse the output constraint. If that fails, there's
741 no point in going further. */
742 constraint = constraints[i];
743 if (!parse_output_constraint (&constraint, i, ninputs, noutputs,
744 &allows_mem, &allows_reg, &is_inout))
745 return;
746
747 if (! allows_reg
748 && (allows_mem
749 || is_inout
750 || (DECL_P (val)
751 && REG_P (DECL_RTL (val))
752 && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))))
753 mark_addressable (val);
754
755 if (is_inout)
756 ninout++;
757 }
758
759 ninputs += ninout;
760 if (ninputs + noutputs > MAX_RECOG_OPERANDS)
761 {
762 error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS);
763 return;
764 }
765
766 for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail))
767 {
768 bool allows_reg, allows_mem;
769 const char *constraint;
770
771 /* If there's an erroneous arg, emit no insn, because the ASM_INPUT
772 would get VOIDmode and that could cause a crash in reload. */
773 if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node)
774 return;
775
776 constraint = constraints[i + noutputs];
777 if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
778 constraints, &allows_mem, &allows_reg))
779 return;
780
781 if (! allows_reg && allows_mem)
782 mark_addressable (TREE_VALUE (tail));
783 }
784
785 /* Second pass evaluates arguments. */
786
787 /* Make sure stack is consistent for asm goto. */
788 if (nlabels > 0)
789 do_pending_stack_adjust ();
790
791 ninout = 0;
792 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
793 {
794 tree val = TREE_VALUE (tail);
795 tree type = TREE_TYPE (val);
796 bool is_inout;
797 bool allows_reg;
798 bool allows_mem;
799 rtx op;
800 bool ok;
801
802 ok = parse_output_constraint (&constraints[i], i, ninputs,
803 noutputs, &allows_mem, &allows_reg,
804 &is_inout);
805 gcc_assert (ok);
806
807 /* If an output operand is not a decl or indirect ref and our constraint
808 allows a register, make a temporary to act as an intermediate.
809 Make the asm insn write into that, then our caller will copy it to
810 the real output operand. Likewise for promoted variables. */
811
812 generating_concat_p = 0;
813
814 real_output_rtx[i] = NULL_RTX;
815 if ((TREE_CODE (val) == INDIRECT_REF
816 && allows_mem)
817 || (DECL_P (val)
818 && (allows_mem || REG_P (DECL_RTL (val)))
819 && ! (REG_P (DECL_RTL (val))
820 && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))
821 || ! allows_reg
822 || is_inout)
823 {
824 op = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE);
825 if (MEM_P (op))
826 op = validize_mem (op);
827
828 if (! allows_reg && !MEM_P (op))
829 error ("output number %d not directly addressable", i);
830 if ((! allows_mem && MEM_P (op))
831 || GET_CODE (op) == CONCAT)
832 {
833 real_output_rtx[i] = op;
834 op = gen_reg_rtx (GET_MODE (op));
835 if (is_inout)
836 emit_move_insn (op, real_output_rtx[i]);
837 }
838 }
839 else
840 {
841 op = assign_temp (type, 0, 0, 1);
842 op = validize_mem (op);
843 if (!MEM_P (op) && TREE_CODE (TREE_VALUE (tail)) == SSA_NAME)
844 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (TREE_VALUE (tail)), op);
845 TREE_VALUE (tail) = make_tree (type, op);
846 }
847 output_rtx[i] = op;
848
849 generating_concat_p = old_generating_concat_p;
850
851 if (is_inout)
852 {
853 inout_mode[ninout] = TYPE_MODE (type);
854 inout_opnum[ninout++] = i;
855 }
856
857 if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
858 clobber_conflict_found = 1;
859 }
860
861 /* Make vectors for the expression-rtx, constraint strings,
862 and named operands. */
863
864 argvec = rtvec_alloc (ninputs);
865 constraintvec = rtvec_alloc (ninputs);
866 labelvec = rtvec_alloc (nlabels);
867
868 body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode
869 : GET_MODE (output_rtx[0])),
870 ggc_strdup (TREE_STRING_POINTER (string)),
871 empty_string, 0, argvec, constraintvec,
872 labelvec, locus);
873
874 MEM_VOLATILE_P (body) = vol;
875
876 /* Eval the inputs and put them into ARGVEC.
877 Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */
878
879 for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i)
880 {
881 bool allows_reg, allows_mem;
882 const char *constraint;
883 tree val, type;
884 rtx op;
885 bool ok;
886
887 constraint = constraints[i + noutputs];
888 ok = parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
889 constraints, &allows_mem, &allows_reg);
890 gcc_assert (ok);
891
892 generating_concat_p = 0;
893
894 val = TREE_VALUE (tail);
895 type = TREE_TYPE (val);
896 /* EXPAND_INITIALIZER will not generate code for valid initializer
897 constants, but will still generate code for other types of operand.
898 This is the behavior we want for constant constraints. */
899 op = expand_expr (val, NULL_RTX, VOIDmode,
900 allows_reg ? EXPAND_NORMAL
901 : allows_mem ? EXPAND_MEMORY
902 : EXPAND_INITIALIZER);
903
904 /* Never pass a CONCAT to an ASM. */
905 if (GET_CODE (op) == CONCAT)
906 op = force_reg (GET_MODE (op), op);
907 else if (MEM_P (op))
908 op = validize_mem (op);
909
910 if (asm_operand_ok (op, constraint, NULL) <= 0)
911 {
912 if (allows_reg && TYPE_MODE (type) != BLKmode)
913 op = force_reg (TYPE_MODE (type), op);
914 else if (!allows_mem)
915 warning (0, "asm operand %d probably doesn%'t match constraints",
916 i + noutputs);
917 else if (MEM_P (op))
918 {
919 /* We won't recognize either volatile memory or memory
920 with a queued address as available a memory_operand
921 at this point. Ignore it: clearly this *is* a memory. */
922 }
923 else
924 {
925 warning (0, "use of memory input without lvalue in "
926 "asm operand %d is deprecated", i + noutputs);
927
928 if (CONSTANT_P (op))
929 {
930 rtx mem = force_const_mem (TYPE_MODE (type), op);
931 if (mem)
932 op = validize_mem (mem);
933 else
934 op = force_reg (TYPE_MODE (type), op);
935 }
936 if (REG_P (op)
937 || GET_CODE (op) == SUBREG
938 || GET_CODE (op) == CONCAT)
939 {
940 tree qual_type = build_qualified_type (type,
941 (TYPE_QUALS (type)
942 | TYPE_QUAL_CONST));
943 rtx memloc = assign_temp (qual_type, 1, 1, 1);
944 memloc = validize_mem (memloc);
945 emit_move_insn (memloc, op);
946 op = memloc;
947 }
948 }
949 }
950
951 generating_concat_p = old_generating_concat_p;
952 ASM_OPERANDS_INPUT (body, i) = op;
953
954 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i)
955 = gen_rtx_ASM_INPUT (TYPE_MODE (type),
956 ggc_strdup (constraints[i + noutputs]));
957
958 if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
959 clobber_conflict_found = 1;
960 }
961
962 /* Protect all the operands from the queue now that they have all been
963 evaluated. */
964
965 generating_concat_p = 0;
966
967 /* For in-out operands, copy output rtx to input rtx. */
968 for (i = 0; i < ninout; i++)
969 {
970 int j = inout_opnum[i];
971 char buffer[16];
972
973 ASM_OPERANDS_INPUT (body, ninputs - ninout + i)
974 = output_rtx[j];
975
976 sprintf (buffer, "%d", j);
977 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i)
978 = gen_rtx_ASM_INPUT (inout_mode[i], ggc_strdup (buffer));
979 }
980
981 /* Copy labels to the vector. */
982 for (i = 0, tail = labels; i < nlabels; ++i, tail = TREE_CHAIN (tail))
983 ASM_OPERANDS_LABEL (body, i)
984 = gen_rtx_LABEL_REF (Pmode, label_rtx (TREE_VALUE (tail)));
985
986 generating_concat_p = old_generating_concat_p;
987
988 /* Now, for each output, construct an rtx
989 (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER
990 ARGVEC CONSTRAINTS OPNAMES))
991 If there is more than one, put them inside a PARALLEL. */
992
993 if (nlabels > 0 && nclobbers == 0)
994 {
995 gcc_assert (noutputs == 0);
996 emit_jump_insn (body);
997 }
998 else if (noutputs == 0 && nclobbers == 0)
999 {
1000 /* No output operands: put in a raw ASM_OPERANDS rtx. */
1001 emit_insn (body);
1002 }
1003 else if (noutputs == 1 && nclobbers == 0)
1004 {
1005 ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = ggc_strdup (constraints[0]);
1006 emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body));
1007 }
1008 else
1009 {
1010 rtx obody = body;
1011 int num = noutputs;
1012
1013 if (num == 0)
1014 num = 1;
1015
1016 body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers));
1017
1018 /* For each output operand, store a SET. */
1019 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1020 {
1021 XVECEXP (body, 0, i)
1022 = gen_rtx_SET (VOIDmode,
1023 output_rtx[i],
1024 gen_rtx_ASM_OPERANDS
1025 (GET_MODE (output_rtx[i]),
1026 ggc_strdup (TREE_STRING_POINTER (string)),
1027 ggc_strdup (constraints[i]),
1028 i, argvec, constraintvec, labelvec, locus));
1029
1030 MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol;
1031 }
1032
1033 /* If there are no outputs (but there are some clobbers)
1034 store the bare ASM_OPERANDS into the PARALLEL. */
1035
1036 if (i == 0)
1037 XVECEXP (body, 0, i++) = obody;
1038
1039 /* Store (clobber REG) for each clobbered register specified. */
1040
1041 for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
1042 {
1043 const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
1044 int reg, nregs;
1045 int j = decode_reg_name_and_count (regname, &nregs);
1046 rtx clobbered_reg;
1047
1048 if (j < 0)
1049 {
1050 if (j == -3) /* `cc', which is not a register */
1051 continue;
1052
1053 if (j == -4) /* `memory', don't cache memory across asm */
1054 {
1055 XVECEXP (body, 0, i++)
1056 = gen_rtx_CLOBBER (VOIDmode,
1057 gen_rtx_MEM
1058 (BLKmode,
1059 gen_rtx_SCRATCH (VOIDmode)));
1060 continue;
1061 }
1062
1063 /* Ignore unknown register, error already signaled. */
1064 continue;
1065 }
1066
1067 for (reg = j; reg < j + nregs; reg++)
1068 {
1069 /* Use QImode since that's guaranteed to clobber just
1070 * one reg. */
1071 clobbered_reg = gen_rtx_REG (QImode, reg);
1072
1073 /* Do sanity check for overlap between clobbers and
1074 respectively input and outputs that hasn't been
1075 handled. Such overlap should have been detected and
1076 reported above. */
1077 if (!clobber_conflict_found)
1078 {
1079 int opno;
1080
1081 /* We test the old body (obody) contents to avoid
1082 tripping over the under-construction body. */
1083 for (opno = 0; opno < noutputs; opno++)
1084 if (reg_overlap_mentioned_p (clobbered_reg,
1085 output_rtx[opno]))
1086 internal_error
1087 ("asm clobber conflict with output operand");
1088
1089 for (opno = 0; opno < ninputs - ninout; opno++)
1090 if (reg_overlap_mentioned_p (clobbered_reg,
1091 ASM_OPERANDS_INPUT (obody,
1092 opno)))
1093 internal_error
1094 ("asm clobber conflict with input operand");
1095 }
1096
1097 XVECEXP (body, 0, i++)
1098 = gen_rtx_CLOBBER (VOIDmode, clobbered_reg);
1099 }
1100 }
1101
1102 if (nlabels > 0)
1103 emit_jump_insn (body);
1104 else
1105 emit_insn (body);
1106 }
1107
1108 /* For any outputs that needed reloading into registers, spill them
1109 back to where they belong. */
1110 for (i = 0; i < noutputs; ++i)
1111 if (real_output_rtx[i])
1112 emit_move_insn (real_output_rtx[i], output_rtx[i]);
1113
1114 crtl->has_asm_statement = 1;
1115 free_temp_slots ();
1116 }
1117
1118 void
expand_asm_stmt(gimple stmt)1119 expand_asm_stmt (gimple stmt)
1120 {
1121 int noutputs;
1122 tree outputs, tail, t;
1123 tree *o;
1124 size_t i, n;
1125 const char *s;
1126 tree str, out, in, cl, labels;
1127 location_t locus = gimple_location (stmt);
1128
1129 /* Meh... convert the gimple asm operands into real tree lists.
1130 Eventually we should make all routines work on the vectors instead
1131 of relying on TREE_CHAIN. */
1132 out = NULL_TREE;
1133 n = gimple_asm_noutputs (stmt);
1134 if (n > 0)
1135 {
1136 t = out = gimple_asm_output_op (stmt, 0);
1137 for (i = 1; i < n; i++)
1138 t = TREE_CHAIN (t) = gimple_asm_output_op (stmt, i);
1139 }
1140
1141 in = NULL_TREE;
1142 n = gimple_asm_ninputs (stmt);
1143 if (n > 0)
1144 {
1145 t = in = gimple_asm_input_op (stmt, 0);
1146 for (i = 1; i < n; i++)
1147 t = TREE_CHAIN (t) = gimple_asm_input_op (stmt, i);
1148 }
1149
1150 cl = NULL_TREE;
1151 n = gimple_asm_nclobbers (stmt);
1152 if (n > 0)
1153 {
1154 t = cl = gimple_asm_clobber_op (stmt, 0);
1155 for (i = 1; i < n; i++)
1156 t = TREE_CHAIN (t) = gimple_asm_clobber_op (stmt, i);
1157 }
1158
1159 labels = NULL_TREE;
1160 n = gimple_asm_nlabels (stmt);
1161 if (n > 0)
1162 {
1163 t = labels = gimple_asm_label_op (stmt, 0);
1164 for (i = 1; i < n; i++)
1165 t = TREE_CHAIN (t) = gimple_asm_label_op (stmt, i);
1166 }
1167
1168 s = gimple_asm_string (stmt);
1169 str = build_string (strlen (s), s);
1170
1171 if (gimple_asm_input_p (stmt))
1172 {
1173 expand_asm_loc (str, gimple_asm_volatile_p (stmt), locus);
1174 return;
1175 }
1176
1177 outputs = out;
1178 noutputs = gimple_asm_noutputs (stmt);
1179 /* o[I] is the place that output number I should be written. */
1180 o = (tree *) alloca (noutputs * sizeof (tree));
1181
1182 /* Record the contents of OUTPUTS before it is modified. */
1183 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1184 o[i] = TREE_VALUE (tail);
1185
1186 /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of
1187 OUTPUTS some trees for where the values were actually stored. */
1188 expand_asm_operands (str, outputs, in, cl, labels,
1189 gimple_asm_volatile_p (stmt), locus);
1190
1191 /* Copy all the intermediate outputs into the specified outputs. */
1192 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1193 {
1194 if (o[i] != TREE_VALUE (tail))
1195 {
1196 expand_assignment (o[i], TREE_VALUE (tail), false);
1197 free_temp_slots ();
1198
1199 /* Restore the original value so that it's correct the next
1200 time we expand this function. */
1201 TREE_VALUE (tail) = o[i];
1202 }
1203 }
1204 }
1205
1206 /* A subroutine of expand_asm_operands. Check that all operands have
1207 the same number of alternatives. Return true if so. */
1208
1209 static bool
check_operand_nalternatives(tree outputs,tree inputs)1210 check_operand_nalternatives (tree outputs, tree inputs)
1211 {
1212 if (outputs || inputs)
1213 {
1214 tree tmp = TREE_PURPOSE (outputs ? outputs : inputs);
1215 int nalternatives
1216 = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp)));
1217 tree next = inputs;
1218
1219 if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES)
1220 {
1221 error ("too many alternatives in %<asm%>");
1222 return false;
1223 }
1224
1225 tmp = outputs;
1226 while (tmp)
1227 {
1228 const char *constraint
1229 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp)));
1230
1231 if (n_occurrences (',', constraint) != nalternatives)
1232 {
1233 error ("operand constraints for %<asm%> differ "
1234 "in number of alternatives");
1235 return false;
1236 }
1237
1238 if (TREE_CHAIN (tmp))
1239 tmp = TREE_CHAIN (tmp);
1240 else
1241 tmp = next, next = 0;
1242 }
1243 }
1244
1245 return true;
1246 }
1247
1248 /* A subroutine of expand_asm_operands. Check that all operand names
1249 are unique. Return true if so. We rely on the fact that these names
1250 are identifiers, and so have been canonicalized by get_identifier,
1251 so all we need are pointer comparisons. */
1252
1253 static bool
check_unique_operand_names(tree outputs,tree inputs,tree labels)1254 check_unique_operand_names (tree outputs, tree inputs, tree labels)
1255 {
1256 tree i, j, i_name = NULL_TREE;
1257
1258 for (i = outputs; i ; i = TREE_CHAIN (i))
1259 {
1260 i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1261 if (! i_name)
1262 continue;
1263
1264 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1265 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1266 goto failure;
1267 }
1268
1269 for (i = inputs; i ; i = TREE_CHAIN (i))
1270 {
1271 i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1272 if (! i_name)
1273 continue;
1274
1275 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1276 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1277 goto failure;
1278 for (j = outputs; j ; j = TREE_CHAIN (j))
1279 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1280 goto failure;
1281 }
1282
1283 for (i = labels; i ; i = TREE_CHAIN (i))
1284 {
1285 i_name = TREE_PURPOSE (i);
1286 if (! i_name)
1287 continue;
1288
1289 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1290 if (simple_cst_equal (i_name, TREE_PURPOSE (j)))
1291 goto failure;
1292 for (j = inputs; j ; j = TREE_CHAIN (j))
1293 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1294 goto failure;
1295 }
1296
1297 return true;
1298
1299 failure:
1300 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name));
1301 return false;
1302 }
1303
1304 /* A subroutine of expand_asm_operands. Resolve the names of the operands
1305 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
1306 STRING and in the constraints to those numbers. */
1307
1308 tree
resolve_asm_operand_names(tree string,tree outputs,tree inputs,tree labels)1309 resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels)
1310 {
1311 char *buffer;
1312 char *p;
1313 const char *c;
1314 tree t;
1315
1316 check_unique_operand_names (outputs, inputs, labels);
1317
1318 /* Substitute [<name>] in input constraint strings. There should be no
1319 named operands in output constraints. */
1320 for (t = inputs; t ; t = TREE_CHAIN (t))
1321 {
1322 c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
1323 if (strchr (c, '[') != NULL)
1324 {
1325 p = buffer = xstrdup (c);
1326 while ((p = strchr (p, '[')) != NULL)
1327 p = resolve_operand_name_1 (p, outputs, inputs, NULL);
1328 TREE_VALUE (TREE_PURPOSE (t))
1329 = build_string (strlen (buffer), buffer);
1330 free (buffer);
1331 }
1332 }
1333
1334 /* Now check for any needed substitutions in the template. */
1335 c = TREE_STRING_POINTER (string);
1336 while ((c = strchr (c, '%')) != NULL)
1337 {
1338 if (c[1] == '[')
1339 break;
1340 else if (ISALPHA (c[1]) && c[2] == '[')
1341 break;
1342 else
1343 {
1344 c += 1 + (c[1] == '%');
1345 continue;
1346 }
1347 }
1348
1349 if (c)
1350 {
1351 /* OK, we need to make a copy so we can perform the substitutions.
1352 Assume that we will not need extra space--we get to remove '['
1353 and ']', which means we cannot have a problem until we have more
1354 than 999 operands. */
1355 buffer = xstrdup (TREE_STRING_POINTER (string));
1356 p = buffer + (c - TREE_STRING_POINTER (string));
1357
1358 while ((p = strchr (p, '%')) != NULL)
1359 {
1360 if (p[1] == '[')
1361 p += 1;
1362 else if (ISALPHA (p[1]) && p[2] == '[')
1363 p += 2;
1364 else
1365 {
1366 p += 1 + (p[1] == '%');
1367 continue;
1368 }
1369
1370 p = resolve_operand_name_1 (p, outputs, inputs, labels);
1371 }
1372
1373 string = build_string (strlen (buffer), buffer);
1374 free (buffer);
1375 }
1376
1377 return string;
1378 }
1379
1380 /* A subroutine of resolve_operand_names. P points to the '[' for a
1381 potential named operand of the form [<name>]. In place, replace
1382 the name and brackets with a number. Return a pointer to the
1383 balance of the string after substitution. */
1384
1385 static char *
resolve_operand_name_1(char * p,tree outputs,tree inputs,tree labels)1386 resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels)
1387 {
1388 char *q;
1389 int op;
1390 tree t;
1391
1392 /* Collect the operand name. */
1393 q = strchr (++p, ']');
1394 if (!q)
1395 {
1396 error ("missing close brace for named operand");
1397 return strchr (p, '\0');
1398 }
1399 *q = '\0';
1400
1401 /* Resolve the name to a number. */
1402 for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
1403 {
1404 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1405 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1406 goto found;
1407 }
1408 for (t = inputs; t ; t = TREE_CHAIN (t), op++)
1409 {
1410 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1411 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1412 goto found;
1413 }
1414 for (t = labels; t ; t = TREE_CHAIN (t), op++)
1415 {
1416 tree name = TREE_PURPOSE (t);
1417 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1418 goto found;
1419 }
1420
1421 error ("undefined named operand %qs", identifier_to_locale (p));
1422 op = 0;
1423
1424 found:
1425 /* Replace the name with the number. Unfortunately, not all libraries
1426 get the return value of sprintf correct, so search for the end of the
1427 generated string by hand. */
1428 sprintf (--p, "%d", op);
1429 p = strchr (p, '\0');
1430
1431 /* Verify the no extra buffer space assumption. */
1432 gcc_assert (p <= q);
1433
1434 /* Shift the rest of the buffer down to fill the gap. */
1435 memmove (p, q + 1, strlen (q + 1) + 1);
1436
1437 return p;
1438 }
1439
1440 /* Generate RTL to evaluate the expression EXP. */
1441
1442 void
expand_expr_stmt(tree exp)1443 expand_expr_stmt (tree exp)
1444 {
1445 rtx value;
1446 tree type;
1447
1448 value = expand_expr (exp, const0_rtx, VOIDmode, EXPAND_NORMAL);
1449 type = TREE_TYPE (exp);
1450
1451 /* If all we do is reference a volatile value in memory,
1452 copy it to a register to be sure it is actually touched. */
1453 if (value && MEM_P (value) && TREE_THIS_VOLATILE (exp))
1454 {
1455 if (TYPE_MODE (type) == VOIDmode)
1456 ;
1457 else if (TYPE_MODE (type) != BLKmode)
1458 copy_to_reg (value);
1459 else
1460 {
1461 rtx lab = gen_label_rtx ();
1462
1463 /* Compare the value with itself to reference it. */
1464 emit_cmp_and_jump_insns (value, value, EQ,
1465 expand_normal (TYPE_SIZE (type)),
1466 BLKmode, 0, lab);
1467 emit_label (lab);
1468 }
1469 }
1470
1471 /* Free any temporaries used to evaluate this expression. */
1472 free_temp_slots ();
1473 }
1474
1475 /* Warn if EXP contains any computations whose results are not used.
1476 Return 1 if a warning is printed; 0 otherwise. LOCUS is the
1477 (potential) location of the expression. */
1478
1479 int
warn_if_unused_value(const_tree exp,location_t locus)1480 warn_if_unused_value (const_tree exp, location_t locus)
1481 {
1482 restart:
1483 if (TREE_USED (exp) || TREE_NO_WARNING (exp))
1484 return 0;
1485
1486 /* Don't warn about void constructs. This includes casting to void,
1487 void function calls, and statement expressions with a final cast
1488 to void. */
1489 if (VOID_TYPE_P (TREE_TYPE (exp)))
1490 return 0;
1491
1492 if (EXPR_HAS_LOCATION (exp))
1493 locus = EXPR_LOCATION (exp);
1494
1495 switch (TREE_CODE (exp))
1496 {
1497 case PREINCREMENT_EXPR:
1498 case POSTINCREMENT_EXPR:
1499 case PREDECREMENT_EXPR:
1500 case POSTDECREMENT_EXPR:
1501 case MODIFY_EXPR:
1502 case INIT_EXPR:
1503 case TARGET_EXPR:
1504 case CALL_EXPR:
1505 case TRY_CATCH_EXPR:
1506 case WITH_CLEANUP_EXPR:
1507 case EXIT_EXPR:
1508 case VA_ARG_EXPR:
1509 return 0;
1510
1511 case BIND_EXPR:
1512 /* For a binding, warn if no side effect within it. */
1513 exp = BIND_EXPR_BODY (exp);
1514 goto restart;
1515
1516 case SAVE_EXPR:
1517 case NON_LVALUE_EXPR:
1518 exp = TREE_OPERAND (exp, 0);
1519 goto restart;
1520
1521 case TRUTH_ORIF_EXPR:
1522 case TRUTH_ANDIF_EXPR:
1523 /* In && or ||, warn if 2nd operand has no side effect. */
1524 exp = TREE_OPERAND (exp, 1);
1525 goto restart;
1526
1527 case COMPOUND_EXPR:
1528 if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus))
1529 return 1;
1530 /* Let people do `(foo (), 0)' without a warning. */
1531 if (TREE_CONSTANT (TREE_OPERAND (exp, 1)))
1532 return 0;
1533 exp = TREE_OPERAND (exp, 1);
1534 goto restart;
1535
1536 case COND_EXPR:
1537 /* If this is an expression with side effects, don't warn; this
1538 case commonly appears in macro expansions. */
1539 if (TREE_SIDE_EFFECTS (exp))
1540 return 0;
1541 goto warn;
1542
1543 case INDIRECT_REF:
1544 /* Don't warn about automatic dereferencing of references, since
1545 the user cannot control it. */
1546 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE)
1547 {
1548 exp = TREE_OPERAND (exp, 0);
1549 goto restart;
1550 }
1551 /* Fall through. */
1552
1553 default:
1554 /* Referencing a volatile value is a side effect, so don't warn. */
1555 if ((DECL_P (exp) || REFERENCE_CLASS_P (exp))
1556 && TREE_THIS_VOLATILE (exp))
1557 return 0;
1558
1559 /* If this is an expression which has no operands, there is no value
1560 to be unused. There are no such language-independent codes,
1561 but front ends may define such. */
1562 if (EXPRESSION_CLASS_P (exp) && TREE_OPERAND_LENGTH (exp) == 0)
1563 return 0;
1564
1565 warn:
1566 warning_at (locus, OPT_Wunused_value, "value computed is not used");
1567 return 1;
1568 }
1569 }
1570
1571
1572 /* Generate RTL to return from the current function, with no value.
1573 (That is, we do not do anything about returning any value.) */
1574
1575 void
expand_null_return(void)1576 expand_null_return (void)
1577 {
1578 /* If this function was declared to return a value, but we
1579 didn't, clobber the return registers so that they are not
1580 propagated live to the rest of the function. */
1581 clobber_return_register ();
1582
1583 expand_null_return_1 ();
1584 }
1585
1586 /* Generate RTL to return directly from the current function.
1587 (That is, we bypass any return value.) */
1588
1589 void
expand_naked_return(void)1590 expand_naked_return (void)
1591 {
1592 rtx end_label;
1593
1594 clear_pending_stack_adjust ();
1595 do_pending_stack_adjust ();
1596
1597 end_label = naked_return_label;
1598 if (end_label == 0)
1599 end_label = naked_return_label = gen_label_rtx ();
1600
1601 emit_jump (end_label);
1602 }
1603
1604 /* Generate RTL to return from the current function, with value VAL. */
1605
1606 static void
expand_value_return(rtx val)1607 expand_value_return (rtx val)
1608 {
1609 /* Copy the value to the return location unless it's already there. */
1610
1611 tree decl = DECL_RESULT (current_function_decl);
1612 rtx return_reg = DECL_RTL (decl);
1613 if (return_reg != val)
1614 {
1615 tree funtype = TREE_TYPE (current_function_decl);
1616 tree type = TREE_TYPE (decl);
1617 int unsignedp = TYPE_UNSIGNED (type);
1618 enum machine_mode old_mode = DECL_MODE (decl);
1619 enum machine_mode mode;
1620 if (DECL_BY_REFERENCE (decl))
1621 mode = promote_function_mode (type, old_mode, &unsignedp, funtype, 2);
1622 else
1623 mode = promote_function_mode (type, old_mode, &unsignedp, funtype, 1);
1624
1625 if (mode != old_mode)
1626 val = convert_modes (mode, old_mode, val, unsignedp);
1627
1628 if (GET_CODE (return_reg) == PARALLEL)
1629 emit_group_load (return_reg, val, type, int_size_in_bytes (type));
1630 else
1631 emit_move_insn (return_reg, val);
1632 }
1633
1634 expand_null_return_1 ();
1635 }
1636
1637 /* Output a return with no value. */
1638
1639 static void
expand_null_return_1(void)1640 expand_null_return_1 (void)
1641 {
1642 clear_pending_stack_adjust ();
1643 do_pending_stack_adjust ();
1644 emit_jump (return_label);
1645 }
1646
1647 /* Generate RTL to evaluate the expression RETVAL and return it
1648 from the current function. */
1649
1650 void
expand_return(tree retval)1651 expand_return (tree retval)
1652 {
1653 rtx result_rtl;
1654 rtx val = 0;
1655 tree retval_rhs;
1656
1657 /* If function wants no value, give it none. */
1658 if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE)
1659 {
1660 expand_normal (retval);
1661 expand_null_return ();
1662 return;
1663 }
1664
1665 if (retval == error_mark_node)
1666 {
1667 /* Treat this like a return of no value from a function that
1668 returns a value. */
1669 expand_null_return ();
1670 return;
1671 }
1672 else if ((TREE_CODE (retval) == MODIFY_EXPR
1673 || TREE_CODE (retval) == INIT_EXPR)
1674 && TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL)
1675 retval_rhs = TREE_OPERAND (retval, 1);
1676 else
1677 retval_rhs = retval;
1678
1679 result_rtl = DECL_RTL (DECL_RESULT (current_function_decl));
1680
1681 /* If we are returning the RESULT_DECL, then the value has already
1682 been stored into it, so we don't have to do anything special. */
1683 if (TREE_CODE (retval_rhs) == RESULT_DECL)
1684 expand_value_return (result_rtl);
1685
1686 /* If the result is an aggregate that is being returned in one (or more)
1687 registers, load the registers here. */
1688
1689 else if (retval_rhs != 0
1690 && TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode
1691 && REG_P (result_rtl))
1692 {
1693 val = copy_blkmode_to_reg (GET_MODE (result_rtl), retval_rhs);
1694 if (val)
1695 {
1696 /* Use the mode of the result value on the return register. */
1697 PUT_MODE (result_rtl, GET_MODE (val));
1698 expand_value_return (val);
1699 }
1700 else
1701 expand_null_return ();
1702 }
1703 else if (retval_rhs != 0
1704 && !VOID_TYPE_P (TREE_TYPE (retval_rhs))
1705 && (REG_P (result_rtl)
1706 || (GET_CODE (result_rtl) == PARALLEL)))
1707 {
1708 /* Calculate the return value into a temporary (usually a pseudo
1709 reg). */
1710 tree ot = TREE_TYPE (DECL_RESULT (current_function_decl));
1711 tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST);
1712
1713 val = assign_temp (nt, 0, 0, 1);
1714 val = expand_expr (retval_rhs, val, GET_MODE (val), EXPAND_NORMAL);
1715 val = force_not_mem (val);
1716 /* Return the calculated value. */
1717 expand_value_return (val);
1718 }
1719 else
1720 {
1721 /* No hard reg used; calculate value into hard return reg. */
1722 expand_expr (retval, const0_rtx, VOIDmode, EXPAND_NORMAL);
1723 expand_value_return (result_rtl);
1724 }
1725 }
1726
1727 /* Emit code to restore vital registers at the beginning of a nonlocal goto
1728 handler. */
1729 static void
expand_nl_goto_receiver(void)1730 expand_nl_goto_receiver (void)
1731 {
1732 rtx chain;
1733
1734 /* Clobber the FP when we get here, so we have to make sure it's
1735 marked as used by this function. */
1736 emit_use (hard_frame_pointer_rtx);
1737
1738 /* Mark the static chain as clobbered here so life information
1739 doesn't get messed up for it. */
1740 chain = targetm.calls.static_chain (current_function_decl, true);
1741 if (chain && REG_P (chain))
1742 emit_clobber (chain);
1743
1744 #ifdef HAVE_nonlocal_goto
1745 if (! HAVE_nonlocal_goto)
1746 #endif
1747 /* First adjust our frame pointer to its actual value. It was
1748 previously set to the start of the virtual area corresponding to
1749 the stacked variables when we branched here and now needs to be
1750 adjusted to the actual hardware fp value.
1751
1752 Assignments are to virtual registers are converted by
1753 instantiate_virtual_regs into the corresponding assignment
1754 to the underlying register (fp in this case) that makes
1755 the original assignment true.
1756 So the following insn will actually be
1757 decrementing fp by STARTING_FRAME_OFFSET. */
1758 emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx);
1759
1760 #if !HARD_FRAME_POINTER_IS_ARG_POINTER
1761 if (fixed_regs[ARG_POINTER_REGNUM])
1762 {
1763 #ifdef ELIMINABLE_REGS
1764 /* If the argument pointer can be eliminated in favor of the
1765 frame pointer, we don't need to restore it. We assume here
1766 that if such an elimination is present, it can always be used.
1767 This is the case on all known machines; if we don't make this
1768 assumption, we do unnecessary saving on many machines. */
1769 static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS;
1770 size_t i;
1771
1772 for (i = 0; i < ARRAY_SIZE (elim_regs); i++)
1773 if (elim_regs[i].from == ARG_POINTER_REGNUM
1774 && elim_regs[i].to == HARD_FRAME_POINTER_REGNUM)
1775 break;
1776
1777 if (i == ARRAY_SIZE (elim_regs))
1778 #endif
1779 {
1780 /* Now restore our arg pointer from the address at which it
1781 was saved in our stack frame. */
1782 emit_move_insn (crtl->args.internal_arg_pointer,
1783 copy_to_reg (get_arg_pointer_save_area ()));
1784 }
1785 }
1786 #endif
1787
1788 #ifdef HAVE_nonlocal_goto_receiver
1789 if (HAVE_nonlocal_goto_receiver)
1790 emit_insn (gen_nonlocal_goto_receiver ());
1791 #endif
1792
1793 /* We must not allow the code we just generated to be reordered by
1794 scheduling. Specifically, the update of the frame pointer must
1795 happen immediately, not later. */
1796 emit_insn (gen_blockage ());
1797 }
1798
1799 /* Generate RTL for the automatic variable declaration DECL.
1800 (Other kinds of declarations are simply ignored if seen here.) */
1801
1802 void
expand_decl(tree decl)1803 expand_decl (tree decl)
1804 {
1805 tree type;
1806
1807 type = TREE_TYPE (decl);
1808
1809 /* For a CONST_DECL, set mode, alignment, and sizes from those of the
1810 type in case this node is used in a reference. */
1811 if (TREE_CODE (decl) == CONST_DECL)
1812 {
1813 DECL_MODE (decl) = TYPE_MODE (type);
1814 DECL_ALIGN (decl) = TYPE_ALIGN (type);
1815 DECL_SIZE (decl) = TYPE_SIZE (type);
1816 DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type);
1817 return;
1818 }
1819
1820 /* Otherwise, only automatic variables need any expansion done. Static and
1821 external variables, and external functions, will be handled by
1822 `assemble_variable' (called from finish_decl). TYPE_DECL requires
1823 nothing. PARM_DECLs are handled in `assign_parms'. */
1824 if (TREE_CODE (decl) != VAR_DECL)
1825 return;
1826
1827 if (TREE_STATIC (decl) || DECL_EXTERNAL (decl))
1828 return;
1829
1830 /* Create the RTL representation for the variable. */
1831
1832 if (type == error_mark_node)
1833 SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx));
1834
1835 else if (DECL_SIZE (decl) == 0)
1836 {
1837 /* Variable with incomplete type. */
1838 rtx x;
1839 if (DECL_INITIAL (decl) == 0)
1840 /* Error message was already done; now avoid a crash. */
1841 x = gen_rtx_MEM (BLKmode, const0_rtx);
1842 else
1843 /* An initializer is going to decide the size of this array.
1844 Until we know the size, represent its address with a reg. */
1845 x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode));
1846
1847 set_mem_attributes (x, decl, 1);
1848 SET_DECL_RTL (decl, x);
1849 }
1850 else if (use_register_for_decl (decl))
1851 {
1852 /* Automatic variable that can go in a register. */
1853 enum machine_mode reg_mode = promote_decl_mode (decl, NULL);
1854
1855 SET_DECL_RTL (decl, gen_reg_rtx (reg_mode));
1856
1857 /* Note if the object is a user variable. */
1858 if (!DECL_ARTIFICIAL (decl))
1859 mark_user_reg (DECL_RTL (decl));
1860
1861 if (POINTER_TYPE_P (type))
1862 mark_reg_pointer (DECL_RTL (decl),
1863 TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl))));
1864 }
1865
1866 else
1867 {
1868 rtx oldaddr = 0;
1869 rtx addr;
1870 rtx x;
1871
1872 /* Variable-sized decls are dealt with in the gimplifier. */
1873 gcc_assert (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST);
1874
1875 /* If we previously made RTL for this decl, it must be an array
1876 whose size was determined by the initializer.
1877 The old address was a register; set that register now
1878 to the proper address. */
1879 if (DECL_RTL_SET_P (decl))
1880 {
1881 gcc_assert (MEM_P (DECL_RTL (decl)));
1882 gcc_assert (REG_P (XEXP (DECL_RTL (decl), 0)));
1883 oldaddr = XEXP (DECL_RTL (decl), 0);
1884 }
1885
1886 /* Set alignment we actually gave this decl. */
1887 DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT
1888 : GET_MODE_BITSIZE (DECL_MODE (decl)));
1889 DECL_USER_ALIGN (decl) = 0;
1890
1891 x = assign_temp (decl, 1, 1, 1);
1892 set_mem_attributes (x, decl, 1);
1893 SET_DECL_RTL (decl, x);
1894
1895 if (oldaddr)
1896 {
1897 addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr);
1898 if (addr != oldaddr)
1899 emit_move_insn (oldaddr, addr);
1900 }
1901 }
1902 }
1903
1904 /* Emit code to save the current value of stack. */
1905 rtx
expand_stack_save(void)1906 expand_stack_save (void)
1907 {
1908 rtx ret = NULL_RTX;
1909
1910 do_pending_stack_adjust ();
1911 emit_stack_save (SAVE_BLOCK, &ret);
1912 return ret;
1913 }
1914
1915 /* Emit code to restore the current value of stack. */
1916 void
expand_stack_restore(tree var)1917 expand_stack_restore (tree var)
1918 {
1919 rtx prev, sa = expand_normal (var);
1920
1921 sa = convert_memory_address (Pmode, sa);
1922
1923 prev = get_last_insn ();
1924 emit_stack_restore (SAVE_BLOCK, sa);
1925 fixup_args_size_notes (prev, get_last_insn (), 0);
1926 }
1927
1928 /* Do the insertion of a case label into case_list. The labels are
1929 fed to us in descending order from the sorted vector of case labels used
1930 in the tree part of the middle end. So the list we construct is
1931 sorted in ascending order. The bounds on the case range, LOW and HIGH,
1932 are converted to case's index type TYPE. */
1933
1934 static struct case_node *
add_case_node(struct case_node * head,tree type,tree low,tree high,tree label,alloc_pool case_node_pool)1935 add_case_node (struct case_node *head, tree type, tree low, tree high,
1936 tree label, alloc_pool case_node_pool)
1937 {
1938 tree min_value, max_value;
1939 struct case_node *r;
1940
1941 gcc_assert (TREE_CODE (low) == INTEGER_CST);
1942 gcc_assert (!high || TREE_CODE (high) == INTEGER_CST);
1943
1944 min_value = TYPE_MIN_VALUE (type);
1945 max_value = TYPE_MAX_VALUE (type);
1946
1947 /* If there's no HIGH value, then this is not a case range; it's
1948 just a simple case label. But that's just a degenerate case
1949 range.
1950 If the bounds are equal, turn this into the one-value case. */
1951 if (!high || tree_int_cst_equal (low, high))
1952 {
1953 /* If the simple case value is unreachable, ignore it. */
1954 if ((TREE_CODE (min_value) == INTEGER_CST
1955 && tree_int_cst_compare (low, min_value) < 0)
1956 || (TREE_CODE (max_value) == INTEGER_CST
1957 && tree_int_cst_compare (low, max_value) > 0))
1958 return head;
1959 low = fold_convert (type, low);
1960 high = low;
1961 }
1962 else
1963 {
1964 /* If the entire case range is unreachable, ignore it. */
1965 if ((TREE_CODE (min_value) == INTEGER_CST
1966 && tree_int_cst_compare (high, min_value) < 0)
1967 || (TREE_CODE (max_value) == INTEGER_CST
1968 && tree_int_cst_compare (low, max_value) > 0))
1969 return head;
1970
1971 /* If the lower bound is less than the index type's minimum
1972 value, truncate the range bounds. */
1973 if (TREE_CODE (min_value) == INTEGER_CST
1974 && tree_int_cst_compare (low, min_value) < 0)
1975 low = min_value;
1976 low = fold_convert (type, low);
1977
1978 /* If the upper bound is greater than the index type's maximum
1979 value, truncate the range bounds. */
1980 if (TREE_CODE (max_value) == INTEGER_CST
1981 && tree_int_cst_compare (high, max_value) > 0)
1982 high = max_value;
1983 high = fold_convert (type, high);
1984 }
1985
1986
1987 /* Add this label to the chain. Make sure to drop overflow flags. */
1988 r = (struct case_node *) pool_alloc (case_node_pool);
1989 r->low = build_int_cst_wide (TREE_TYPE (low), TREE_INT_CST_LOW (low),
1990 TREE_INT_CST_HIGH (low));
1991 r->high = build_int_cst_wide (TREE_TYPE (high), TREE_INT_CST_LOW (high),
1992 TREE_INT_CST_HIGH (high));
1993 r->code_label = label;
1994 r->parent = r->left = NULL;
1995 r->right = head;
1996 return r;
1997 }
1998
1999 /* Maximum number of case bit tests. */
2000 #define MAX_CASE_BIT_TESTS 3
2001
2002 /* By default, enable case bit tests on targets with ashlsi3. */
2003 #ifndef CASE_USE_BIT_TESTS
2004 #define CASE_USE_BIT_TESTS (optab_handler (ashl_optab, word_mode) \
2005 != CODE_FOR_nothing)
2006 #endif
2007
2008
2009 /* A case_bit_test represents a set of case nodes that may be
2010 selected from using a bit-wise comparison. HI and LO hold
2011 the integer to be tested against, LABEL contains the label
2012 to jump to upon success and BITS counts the number of case
2013 nodes handled by this test, typically the number of bits
2014 set in HI:LO. */
2015
2016 struct case_bit_test
2017 {
2018 HOST_WIDE_INT hi;
2019 HOST_WIDE_INT lo;
2020 rtx label;
2021 int bits;
2022 };
2023
2024 /* Determine whether "1 << x" is relatively cheap in word_mode. */
2025
2026 static
lshift_cheap_p(void)2027 bool lshift_cheap_p (void)
2028 {
2029 static bool init[2] = {false, false};
2030 static bool cheap[2] = {true, true};
2031
2032 bool speed_p = optimize_insn_for_speed_p ();
2033
2034 if (!init[speed_p])
2035 {
2036 rtx reg = gen_rtx_REG (word_mode, 10000);
2037 int cost = set_src_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg),
2038 speed_p);
2039 cheap[speed_p] = cost < COSTS_N_INSNS (3);
2040 init[speed_p] = true;
2041 }
2042
2043 return cheap[speed_p];
2044 }
2045
2046 /* Comparison function for qsort to order bit tests by decreasing
2047 number of case nodes, i.e. the node with the most cases gets
2048 tested first. */
2049
2050 static int
case_bit_test_cmp(const void * p1,const void * p2)2051 case_bit_test_cmp (const void *p1, const void *p2)
2052 {
2053 const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
2054 const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
2055
2056 if (d2->bits != d1->bits)
2057 return d2->bits - d1->bits;
2058
2059 /* Stabilize the sort. */
2060 return CODE_LABEL_NUMBER (d2->label) - CODE_LABEL_NUMBER (d1->label);
2061 }
2062
2063 /* Expand a switch statement by a short sequence of bit-wise
2064 comparisons. "switch(x)" is effectively converted into
2065 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
2066 integer constants.
2067
2068 INDEX_EXPR is the value being switched on, which is of
2069 type INDEX_TYPE. MINVAL is the lowest case value of in
2070 the case nodes, of INDEX_TYPE type, and RANGE is highest
2071 value minus MINVAL, also of type INDEX_TYPE. NODES is
2072 the set of case nodes, and DEFAULT_LABEL is the label to
2073 branch to should none of the cases match.
2074
2075 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
2076 node targets. */
2077
2078 static void
emit_case_bit_tests(tree index_type,tree index_expr,tree minval,tree range,case_node_ptr nodes,rtx default_label)2079 emit_case_bit_tests (tree index_type, tree index_expr, tree minval,
2080 tree range, case_node_ptr nodes, rtx default_label)
2081 {
2082 struct case_bit_test test[MAX_CASE_BIT_TESTS];
2083 enum machine_mode mode;
2084 rtx expr, index, label;
2085 unsigned int i,j,lo,hi;
2086 struct case_node *n;
2087 unsigned int count;
2088
2089 count = 0;
2090 for (n = nodes; n; n = n->right)
2091 {
2092 label = label_rtx (n->code_label);
2093 for (i = 0; i < count; i++)
2094 if (label == test[i].label)
2095 break;
2096
2097 if (i == count)
2098 {
2099 gcc_assert (count < MAX_CASE_BIT_TESTS);
2100 test[i].hi = 0;
2101 test[i].lo = 0;
2102 test[i].label = label;
2103 test[i].bits = 1;
2104 count++;
2105 }
2106 else
2107 test[i].bits++;
2108
2109 lo = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2110 n->low, minval), 1);
2111 hi = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2112 n->high, minval), 1);
2113 for (j = lo; j <= hi; j++)
2114 if (j >= HOST_BITS_PER_WIDE_INT)
2115 test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT);
2116 else
2117 test[i].lo |= (HOST_WIDE_INT) 1 << j;
2118 }
2119
2120 qsort (test, count, sizeof(*test), case_bit_test_cmp);
2121
2122 index_expr = fold_build2 (MINUS_EXPR, index_type,
2123 fold_convert (index_type, index_expr),
2124 fold_convert (index_type, minval));
2125 index = expand_normal (index_expr);
2126 do_pending_stack_adjust ();
2127
2128 mode = TYPE_MODE (index_type);
2129 expr = expand_normal (range);
2130 if (default_label)
2131 emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
2132 default_label);
2133
2134 index = convert_to_mode (word_mode, index, 0);
2135 index = expand_binop (word_mode, ashl_optab, const1_rtx,
2136 index, NULL_RTX, 1, OPTAB_WIDEN);
2137
2138 for (i = 0; i < count; i++)
2139 {
2140 expr = immed_double_const (test[i].lo, test[i].hi, word_mode);
2141 expr = expand_binop (word_mode, and_optab, index, expr,
2142 NULL_RTX, 1, OPTAB_WIDEN);
2143 emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX,
2144 word_mode, 1, test[i].label);
2145 }
2146
2147 if (default_label)
2148 emit_jump (default_label);
2149 }
2150
2151 #ifndef HAVE_casesi
2152 #define HAVE_casesi 0
2153 #endif
2154
2155 #ifndef HAVE_tablejump
2156 #define HAVE_tablejump 0
2157 #endif
2158
2159 /* Return true if a switch should be expanded as a bit test.
2160 INDEX_EXPR is the index expression, RANGE is the difference between
2161 highest and lowest case, UNIQ is number of unique case node targets
2162 not counting the default case and COUNT is the number of comparisons
2163 needed, not counting the default case. */
2164 bool
expand_switch_using_bit_tests_p(tree index_expr,tree range,unsigned int uniq,unsigned int count)2165 expand_switch_using_bit_tests_p (tree index_expr, tree range,
2166 unsigned int uniq, unsigned int count)
2167 {
2168 return (CASE_USE_BIT_TESTS
2169 && ! TREE_CONSTANT (index_expr)
2170 && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
2171 && compare_tree_int (range, 0) > 0
2172 && lshift_cheap_p ()
2173 && ((uniq == 1 && count >= 3)
2174 || (uniq == 2 && count >= 5)
2175 || (uniq == 3 && count >= 6)));
2176 }
2177
2178 /* Return the smallest number of different values for which it is best to use a
2179 jump-table instead of a tree of conditional branches. */
2180
2181 static unsigned int
case_values_threshold(void)2182 case_values_threshold (void)
2183 {
2184 unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
2185
2186 if (threshold == 0)
2187 threshold = targetm.case_values_threshold ();
2188
2189 return threshold;
2190 }
2191
2192 /* Terminate a case (Pascal/Ada) or switch (C) statement
2193 in which ORIG_INDEX is the expression to be tested.
2194 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
2195 type as given in the source before any compiler conversions.
2196 Generate the code to test it and jump to the right place. */
2197
2198 void
expand_case(gimple stmt)2199 expand_case (gimple stmt)
2200 {
2201 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
2202 rtx default_label = 0;
2203 struct case_node *n;
2204 unsigned int count, uniq;
2205 rtx index;
2206 rtx table_label;
2207 int ncases;
2208 rtx *labelvec;
2209 int i;
2210 rtx before_case, end, lab;
2211
2212 tree index_expr = gimple_switch_index (stmt);
2213 tree index_type = TREE_TYPE (index_expr);
2214 int unsignedp = TYPE_UNSIGNED (index_type);
2215
2216 /* The insn after which the case dispatch should finally
2217 be emitted. Zero for a dummy. */
2218 rtx start;
2219
2220 /* A list of case labels; it is first built as a list and it may then
2221 be rearranged into a nearly balanced binary tree. */
2222 struct case_node *case_list = 0;
2223
2224 /* Label to jump to if no case matches. */
2225 tree default_label_decl = NULL_TREE;
2226
2227 alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
2228 sizeof (struct case_node),
2229 100);
2230
2231 do_pending_stack_adjust ();
2232
2233 /* An ERROR_MARK occurs for various reasons including invalid data type. */
2234 if (index_type != error_mark_node)
2235 {
2236 tree elt;
2237 bitmap label_bitmap;
2238 int stopi = 0;
2239
2240 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
2241 expressions being INTEGER_CST. */
2242 gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
2243
2244 /* The default case, if ever taken, is the first element. */
2245 elt = gimple_switch_label (stmt, 0);
2246 if (!CASE_LOW (elt) && !CASE_HIGH (elt))
2247 {
2248 default_label_decl = CASE_LABEL (elt);
2249 stopi = 1;
2250 }
2251
2252 for (i = gimple_switch_num_labels (stmt) - 1; i >= stopi; --i)
2253 {
2254 tree low, high;
2255 elt = gimple_switch_label (stmt, i);
2256
2257 low = CASE_LOW (elt);
2258 gcc_assert (low);
2259 high = CASE_HIGH (elt);
2260
2261 /* Discard empty ranges. */
2262 if (high && tree_int_cst_lt (high, low))
2263 continue;
2264
2265 case_list = add_case_node (case_list, index_type, low, high,
2266 CASE_LABEL (elt), case_node_pool);
2267 }
2268
2269
2270 before_case = start = get_last_insn ();
2271 if (default_label_decl)
2272 default_label = label_rtx (default_label_decl);
2273
2274 /* Get upper and lower bounds of case values. */
2275
2276 uniq = 0;
2277 count = 0;
2278 label_bitmap = BITMAP_ALLOC (NULL);
2279 for (n = case_list; n; n = n->right)
2280 {
2281 /* Count the elements and track the largest and smallest
2282 of them (treating them as signed even if they are not). */
2283 if (count++ == 0)
2284 {
2285 minval = n->low;
2286 maxval = n->high;
2287 }
2288 else
2289 {
2290 if (tree_int_cst_lt (n->low, minval))
2291 minval = n->low;
2292 if (tree_int_cst_lt (maxval, n->high))
2293 maxval = n->high;
2294 }
2295 /* A range counts double, since it requires two compares. */
2296 if (! tree_int_cst_equal (n->low, n->high))
2297 count++;
2298
2299 /* If we have not seen this label yet, then increase the
2300 number of unique case node targets seen. */
2301 lab = label_rtx (n->code_label);
2302 if (bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab)))
2303 uniq++;
2304 }
2305
2306 BITMAP_FREE (label_bitmap);
2307
2308 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
2309 destination, such as one with a default case only. However,
2310 it doesn't remove cases that are out of range for the switch
2311 type, so we may still get a zero here. */
2312 if (count == 0)
2313 {
2314 if (default_label)
2315 emit_jump (default_label);
2316 free_alloc_pool (case_node_pool);
2317 return;
2318 }
2319
2320 /* Compute span of values. */
2321 range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
2322
2323 /* Try implementing this switch statement by a short sequence of
2324 bit-wise comparisons. However, we let the binary-tree case
2325 below handle constant index expressions. */
2326 if (expand_switch_using_bit_tests_p (index_expr, range, uniq, count))
2327 {
2328 /* Optimize the case where all the case values fit in a
2329 word without having to subtract MINVAL. In this case,
2330 we can optimize away the subtraction. */
2331 if (compare_tree_int (minval, 0) > 0
2332 && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
2333 {
2334 minval = build_int_cst (index_type, 0);
2335 range = maxval;
2336 }
2337 emit_case_bit_tests (index_type, index_expr, minval, range,
2338 case_list, default_label);
2339 }
2340
2341 /* If range of values is much bigger than number of values,
2342 make a sequence of conditional branches instead of a dispatch.
2343 If the switch-index is a constant, do it this way
2344 because we can optimize it. */
2345
2346 else if (count < case_values_threshold ()
2347 || compare_tree_int (range,
2348 (optimize_insn_for_size_p () ? 3 : 10) * count) > 0
2349 /* RANGE may be signed, and really large ranges will show up
2350 as negative numbers. */
2351 || compare_tree_int (range, 0) < 0
2352 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
2353 || flag_pic
2354 #endif
2355 || !flag_jump_tables
2356 || TREE_CONSTANT (index_expr)
2357 /* If neither casesi or tablejump is available, we can
2358 only go this way. */
2359 || (!HAVE_casesi && !HAVE_tablejump))
2360 {
2361 index = expand_normal (index_expr);
2362
2363 /* If the index is a short or char that we do not have
2364 an insn to handle comparisons directly, convert it to
2365 a full integer now, rather than letting each comparison
2366 generate the conversion. */
2367
2368 if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
2369 && ! have_insn_for (COMPARE, GET_MODE (index)))
2370 {
2371 enum machine_mode wider_mode;
2372 for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
2373 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2374 if (have_insn_for (COMPARE, wider_mode))
2375 {
2376 index = convert_to_mode (wider_mode, index, unsignedp);
2377 break;
2378 }
2379 }
2380
2381 do_pending_stack_adjust ();
2382
2383 if (MEM_P (index))
2384 index = copy_to_reg (index);
2385
2386 /* We generate a binary decision tree to select the
2387 appropriate target code. This is done as follows:
2388
2389 The list of cases is rearranged into a binary tree,
2390 nearly optimal assuming equal probability for each case.
2391
2392 The tree is transformed into RTL, eliminating
2393 redundant test conditions at the same time.
2394
2395 If program flow could reach the end of the
2396 decision tree an unconditional jump to the
2397 default code is emitted. */
2398
2399 use_cost_table = estimate_case_costs (case_list);
2400 balance_case_nodes (&case_list, NULL);
2401 emit_case_nodes (index, case_list, default_label, index_type);
2402 if (default_label)
2403 emit_jump (default_label);
2404 }
2405 else
2406 {
2407 rtx fallback_label = label_rtx (case_list->code_label);
2408 table_label = gen_label_rtx ();
2409 if (! try_casesi (index_type, index_expr, minval, range,
2410 table_label, default_label, fallback_label))
2411 {
2412 bool ok;
2413
2414 /* Index jumptables from zero for suitable values of
2415 minval to avoid a subtraction. */
2416 if (optimize_insn_for_speed_p ()
2417 && compare_tree_int (minval, 0) > 0
2418 && compare_tree_int (minval, 3) < 0)
2419 {
2420 minval = build_int_cst (index_type, 0);
2421 range = maxval;
2422 }
2423
2424 ok = try_tablejump (index_type, index_expr, minval, range,
2425 table_label, default_label);
2426 gcc_assert (ok);
2427 }
2428
2429 /* Get table of labels to jump to, in order of case index. */
2430
2431 ncases = tree_low_cst (range, 0) + 1;
2432 labelvec = XALLOCAVEC (rtx, ncases);
2433 memset (labelvec, 0, ncases * sizeof (rtx));
2434
2435 for (n = case_list; n; n = n->right)
2436 {
2437 /* Compute the low and high bounds relative to the minimum
2438 value since that should fit in a HOST_WIDE_INT while the
2439 actual values may not. */
2440 HOST_WIDE_INT i_low
2441 = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2442 n->low, minval), 1);
2443 HOST_WIDE_INT i_high
2444 = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2445 n->high, minval), 1);
2446 HOST_WIDE_INT i;
2447
2448 for (i = i_low; i <= i_high; i ++)
2449 labelvec[i]
2450 = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
2451 }
2452
2453 /* Fill in the gaps with the default. We may have gaps at
2454 the beginning if we tried to avoid the minval subtraction,
2455 so substitute some label even if the default label was
2456 deemed unreachable. */
2457 if (!default_label)
2458 default_label = fallback_label;
2459 for (i = 0; i < ncases; i++)
2460 if (labelvec[i] == 0)
2461 labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
2462
2463 /* Output the table. */
2464 emit_label (table_label);
2465
2466 if (CASE_VECTOR_PC_RELATIVE || flag_pic)
2467 emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
2468 gen_rtx_LABEL_REF (Pmode, table_label),
2469 gen_rtvec_v (ncases, labelvec),
2470 const0_rtx, const0_rtx));
2471 else
2472 emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
2473 gen_rtvec_v (ncases, labelvec)));
2474
2475 /* Record no drop-through after the table. */
2476 emit_barrier ();
2477 }
2478
2479 before_case = NEXT_INSN (before_case);
2480 end = get_last_insn ();
2481 reorder_insns (before_case, end, start);
2482 }
2483
2484 free_temp_slots ();
2485 free_alloc_pool (case_node_pool);
2486 }
2487
2488 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */
2489
2490 static void
do_jump_if_equal(enum machine_mode mode,rtx op0,rtx op1,rtx label,int unsignedp)2491 do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label,
2492 int unsignedp)
2493 {
2494 do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
2495 NULL_RTX, NULL_RTX, label, -1);
2496 }
2497
2498 /* Not all case values are encountered equally. This function
2499 uses a heuristic to weight case labels, in cases where that
2500 looks like a reasonable thing to do.
2501
2502 Right now, all we try to guess is text, and we establish the
2503 following weights:
2504
2505 chars above space: 16
2506 digits: 16
2507 default: 12
2508 space, punct: 8
2509 tab: 4
2510 newline: 2
2511 other "\" chars: 1
2512 remaining chars: 0
2513
2514 If we find any cases in the switch that are not either -1 or in the range
2515 of valid ASCII characters, or are control characters other than those
2516 commonly used with "\", don't treat this switch scanning text.
2517
2518 Return 1 if these nodes are suitable for cost estimation, otherwise
2519 return 0. */
2520
2521 static int
estimate_case_costs(case_node_ptr node)2522 estimate_case_costs (case_node_ptr node)
2523 {
2524 tree min_ascii = integer_minus_one_node;
2525 tree max_ascii = build_int_cst (TREE_TYPE (node->high), 127);
2526 case_node_ptr n;
2527 int i;
2528
2529 /* If we haven't already made the cost table, make it now. Note that the
2530 lower bound of the table is -1, not zero. */
2531
2532 if (! cost_table_initialized)
2533 {
2534 cost_table_initialized = 1;
2535
2536 for (i = 0; i < 128; i++)
2537 {
2538 if (ISALNUM (i))
2539 COST_TABLE (i) = 16;
2540 else if (ISPUNCT (i))
2541 COST_TABLE (i) = 8;
2542 else if (ISCNTRL (i))
2543 COST_TABLE (i) = -1;
2544 }
2545
2546 COST_TABLE (' ') = 8;
2547 COST_TABLE ('\t') = 4;
2548 COST_TABLE ('\0') = 4;
2549 COST_TABLE ('\n') = 2;
2550 COST_TABLE ('\f') = 1;
2551 COST_TABLE ('\v') = 1;
2552 COST_TABLE ('\b') = 1;
2553 }
2554
2555 /* See if all the case expressions look like text. It is text if the
2556 constant is >= -1 and the highest constant is <= 127. Do all comparisons
2557 as signed arithmetic since we don't want to ever access cost_table with a
2558 value less than -1. Also check that none of the constants in a range
2559 are strange control characters. */
2560
2561 for (n = node; n; n = n->right)
2562 {
2563 if (tree_int_cst_lt (n->low, min_ascii)
2564 || tree_int_cst_lt (max_ascii, n->high))
2565 return 0;
2566
2567 for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low);
2568 i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++)
2569 if (COST_TABLE (i) < 0)
2570 return 0;
2571 }
2572
2573 /* All interesting values are within the range of interesting
2574 ASCII characters. */
2575 return 1;
2576 }
2577
2578 /* Take an ordered list of case nodes
2579 and transform them into a near optimal binary tree,
2580 on the assumption that any target code selection value is as
2581 likely as any other.
2582
2583 The transformation is performed by splitting the ordered
2584 list into two equal sections plus a pivot. The parts are
2585 then attached to the pivot as left and right branches. Each
2586 branch is then transformed recursively. */
2587
2588 static void
balance_case_nodes(case_node_ptr * head,case_node_ptr parent)2589 balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
2590 {
2591 case_node_ptr np;
2592
2593 np = *head;
2594 if (np)
2595 {
2596 int cost = 0;
2597 int i = 0;
2598 int ranges = 0;
2599 case_node_ptr *npp;
2600 case_node_ptr left;
2601
2602 /* Count the number of entries on branch. Also count the ranges. */
2603
2604 while (np)
2605 {
2606 if (!tree_int_cst_equal (np->low, np->high))
2607 {
2608 ranges++;
2609 if (use_cost_table)
2610 cost += COST_TABLE (TREE_INT_CST_LOW (np->high));
2611 }
2612
2613 if (use_cost_table)
2614 cost += COST_TABLE (TREE_INT_CST_LOW (np->low));
2615
2616 i++;
2617 np = np->right;
2618 }
2619
2620 if (i > 2)
2621 {
2622 /* Split this list if it is long enough for that to help. */
2623 npp = head;
2624 left = *npp;
2625 if (use_cost_table)
2626 {
2627 /* Find the place in the list that bisects the list's total cost,
2628 Here I gets half the total cost. */
2629 int n_moved = 0;
2630 i = (cost + 1) / 2;
2631 while (1)
2632 {
2633 /* Skip nodes while their cost does not reach that amount. */
2634 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
2635 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high));
2636 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low));
2637 if (i <= 0)
2638 break;
2639 npp = &(*npp)->right;
2640 n_moved += 1;
2641 }
2642 if (n_moved == 0)
2643 {
2644 /* Leave this branch lopsided, but optimize left-hand
2645 side and fill in `parent' fields for right-hand side. */
2646 np = *head;
2647 np->parent = parent;
2648 balance_case_nodes (&np->left, np);
2649 for (; np->right; np = np->right)
2650 np->right->parent = np;
2651 return;
2652 }
2653 }
2654 /* If there are just three nodes, split at the middle one. */
2655 else if (i == 3)
2656 npp = &(*npp)->right;
2657 else
2658 {
2659 /* Find the place in the list that bisects the list's total cost,
2660 where ranges count as 2.
2661 Here I gets half the total cost. */
2662 i = (i + ranges + 1) / 2;
2663 while (1)
2664 {
2665 /* Skip nodes while their cost does not reach that amount. */
2666 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
2667 i--;
2668 i--;
2669 if (i <= 0)
2670 break;
2671 npp = &(*npp)->right;
2672 }
2673 }
2674 *head = np = *npp;
2675 *npp = 0;
2676 np->parent = parent;
2677 np->left = left;
2678
2679 /* Optimize each of the two split parts. */
2680 balance_case_nodes (&np->left, np);
2681 balance_case_nodes (&np->right, np);
2682 }
2683 else
2684 {
2685 /* Else leave this branch as one level,
2686 but fill in `parent' fields. */
2687 np = *head;
2688 np->parent = parent;
2689 for (; np->right; np = np->right)
2690 np->right->parent = np;
2691 }
2692 }
2693 }
2694
2695 /* Search the parent sections of the case node tree
2696 to see if a test for the lower bound of NODE would be redundant.
2697 INDEX_TYPE is the type of the index expression.
2698
2699 The instructions to generate the case decision tree are
2700 output in the same order as nodes are processed so it is
2701 known that if a parent node checks the range of the current
2702 node minus one that the current node is bounded at its lower
2703 span. Thus the test would be redundant. */
2704
2705 static int
node_has_low_bound(case_node_ptr node,tree index_type)2706 node_has_low_bound (case_node_ptr node, tree index_type)
2707 {
2708 tree low_minus_one;
2709 case_node_ptr pnode;
2710
2711 /* If the lower bound of this node is the lowest value in the index type,
2712 we need not test it. */
2713
2714 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
2715 return 1;
2716
2717 /* If this node has a left branch, the value at the left must be less
2718 than that at this node, so it cannot be bounded at the bottom and
2719 we need not bother testing any further. */
2720
2721 if (node->left)
2722 return 0;
2723
2724 low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low),
2725 node->low,
2726 build_int_cst (TREE_TYPE (node->low), 1));
2727
2728 /* If the subtraction above overflowed, we can't verify anything.
2729 Otherwise, look for a parent that tests our value - 1. */
2730
2731 if (! tree_int_cst_lt (low_minus_one, node->low))
2732 return 0;
2733
2734 for (pnode = node->parent; pnode; pnode = pnode->parent)
2735 if (tree_int_cst_equal (low_minus_one, pnode->high))
2736 return 1;
2737
2738 return 0;
2739 }
2740
2741 /* Search the parent sections of the case node tree
2742 to see if a test for the upper bound of NODE would be redundant.
2743 INDEX_TYPE is the type of the index expression.
2744
2745 The instructions to generate the case decision tree are
2746 output in the same order as nodes are processed so it is
2747 known that if a parent node checks the range of the current
2748 node plus one that the current node is bounded at its upper
2749 span. Thus the test would be redundant. */
2750
2751 static int
node_has_high_bound(case_node_ptr node,tree index_type)2752 node_has_high_bound (case_node_ptr node, tree index_type)
2753 {
2754 tree high_plus_one;
2755 case_node_ptr pnode;
2756
2757 /* If there is no upper bound, obviously no test is needed. */
2758
2759 if (TYPE_MAX_VALUE (index_type) == NULL)
2760 return 1;
2761
2762 /* If the upper bound of this node is the highest value in the type
2763 of the index expression, we need not test against it. */
2764
2765 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
2766 return 1;
2767
2768 /* If this node has a right branch, the value at the right must be greater
2769 than that at this node, so it cannot be bounded at the top and
2770 we need not bother testing any further. */
2771
2772 if (node->right)
2773 return 0;
2774
2775 high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high),
2776 node->high,
2777 build_int_cst (TREE_TYPE (node->high), 1));
2778
2779 /* If the addition above overflowed, we can't verify anything.
2780 Otherwise, look for a parent that tests our value + 1. */
2781
2782 if (! tree_int_cst_lt (node->high, high_plus_one))
2783 return 0;
2784
2785 for (pnode = node->parent; pnode; pnode = pnode->parent)
2786 if (tree_int_cst_equal (high_plus_one, pnode->low))
2787 return 1;
2788
2789 return 0;
2790 }
2791
2792 /* Search the parent sections of the
2793 case node tree to see if both tests for the upper and lower
2794 bounds of NODE would be redundant. */
2795
2796 static int
node_is_bounded(case_node_ptr node,tree index_type)2797 node_is_bounded (case_node_ptr node, tree index_type)
2798 {
2799 return (node_has_low_bound (node, index_type)
2800 && node_has_high_bound (node, index_type));
2801 }
2802
2803 /* Emit step-by-step code to select a case for the value of INDEX.
2804 The thus generated decision tree follows the form of the
2805 case-node binary tree NODE, whose nodes represent test conditions.
2806 INDEX_TYPE is the type of the index of the switch.
2807
2808 Care is taken to prune redundant tests from the decision tree
2809 by detecting any boundary conditions already checked by
2810 emitted rtx. (See node_has_high_bound, node_has_low_bound
2811 and node_is_bounded, above.)
2812
2813 Where the test conditions can be shown to be redundant we emit
2814 an unconditional jump to the target code. As a further
2815 optimization, the subordinates of a tree node are examined to
2816 check for bounded nodes. In this case conditional and/or
2817 unconditional jumps as a result of the boundary check for the
2818 current node are arranged to target the subordinates associated
2819 code for out of bound conditions on the current node.
2820
2821 We can assume that when control reaches the code generated here,
2822 the index value has already been compared with the parents
2823 of this node, and determined to be on the same side of each parent
2824 as this node is. Thus, if this node tests for the value 51,
2825 and a parent tested for 52, we don't need to consider
2826 the possibility of a value greater than 51. If another parent
2827 tests for the value 50, then this node need not test anything. */
2828
2829 static void
emit_case_nodes(rtx index,case_node_ptr node,rtx default_label,tree index_type)2830 emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
2831 tree index_type)
2832 {
2833 /* If INDEX has an unsigned type, we must make unsigned branches. */
2834 int unsignedp = TYPE_UNSIGNED (index_type);
2835 enum machine_mode mode = GET_MODE (index);
2836 enum machine_mode imode = TYPE_MODE (index_type);
2837
2838 /* Handle indices detected as constant during RTL expansion. */
2839 if (mode == VOIDmode)
2840 mode = imode;
2841
2842 /* See if our parents have already tested everything for us.
2843 If they have, emit an unconditional jump for this node. */
2844 if (node_is_bounded (node, index_type))
2845 emit_jump (label_rtx (node->code_label));
2846
2847 else if (tree_int_cst_equal (node->low, node->high))
2848 {
2849 /* Node is single valued. First see if the index expression matches
2850 this node and then check our children, if any. */
2851
2852 do_jump_if_equal (mode, index,
2853 convert_modes (mode, imode,
2854 expand_normal (node->low),
2855 unsignedp),
2856 label_rtx (node->code_label), unsignedp);
2857
2858 if (node->right != 0 && node->left != 0)
2859 {
2860 /* This node has children on both sides.
2861 Dispatch to one side or the other
2862 by comparing the index value with this node's value.
2863 If one subtree is bounded, check that one first,
2864 so we can avoid real branches in the tree. */
2865
2866 if (node_is_bounded (node->right, index_type))
2867 {
2868 emit_cmp_and_jump_insns (index,
2869 convert_modes
2870 (mode, imode,
2871 expand_normal (node->high),
2872 unsignedp),
2873 GT, NULL_RTX, mode, unsignedp,
2874 label_rtx (node->right->code_label));
2875 emit_case_nodes (index, node->left, default_label, index_type);
2876 }
2877
2878 else if (node_is_bounded (node->left, index_type))
2879 {
2880 emit_cmp_and_jump_insns (index,
2881 convert_modes
2882 (mode, imode,
2883 expand_normal (node->high),
2884 unsignedp),
2885 LT, NULL_RTX, mode, unsignedp,
2886 label_rtx (node->left->code_label));
2887 emit_case_nodes (index, node->right, default_label, index_type);
2888 }
2889
2890 /* If both children are single-valued cases with no
2891 children, finish up all the work. This way, we can save
2892 one ordered comparison. */
2893 else if (tree_int_cst_equal (node->right->low, node->right->high)
2894 && node->right->left == 0
2895 && node->right->right == 0
2896 && tree_int_cst_equal (node->left->low, node->left->high)
2897 && node->left->left == 0
2898 && node->left->right == 0)
2899 {
2900 /* Neither node is bounded. First distinguish the two sides;
2901 then emit the code for one side at a time. */
2902
2903 /* See if the value matches what the right hand side
2904 wants. */
2905 do_jump_if_equal (mode, index,
2906 convert_modes (mode, imode,
2907 expand_normal (node->right->low),
2908 unsignedp),
2909 label_rtx (node->right->code_label),
2910 unsignedp);
2911
2912 /* See if the value matches what the left hand side
2913 wants. */
2914 do_jump_if_equal (mode, index,
2915 convert_modes (mode, imode,
2916 expand_normal (node->left->low),
2917 unsignedp),
2918 label_rtx (node->left->code_label),
2919 unsignedp);
2920 }
2921
2922 else
2923 {
2924 /* Neither node is bounded. First distinguish the two sides;
2925 then emit the code for one side at a time. */
2926
2927 tree test_label
2928 = build_decl (CURR_INSN_LOCATION,
2929 LABEL_DECL, NULL_TREE, NULL_TREE);
2930
2931 /* See if the value is on the right. */
2932 emit_cmp_and_jump_insns (index,
2933 convert_modes
2934 (mode, imode,
2935 expand_normal (node->high),
2936 unsignedp),
2937 GT, NULL_RTX, mode, unsignedp,
2938 label_rtx (test_label));
2939
2940 /* Value must be on the left.
2941 Handle the left-hand subtree. */
2942 emit_case_nodes (index, node->left, default_label, index_type);
2943 /* If left-hand subtree does nothing,
2944 go to default. */
2945 if (default_label)
2946 emit_jump (default_label);
2947
2948 /* Code branches here for the right-hand subtree. */
2949 expand_label (test_label);
2950 emit_case_nodes (index, node->right, default_label, index_type);
2951 }
2952 }
2953
2954 else if (node->right != 0 && node->left == 0)
2955 {
2956 /* Here we have a right child but no left so we issue a conditional
2957 branch to default and process the right child.
2958
2959 Omit the conditional branch to default if the right child
2960 does not have any children and is single valued; it would
2961 cost too much space to save so little time. */
2962
2963 if (node->right->right || node->right->left
2964 || !tree_int_cst_equal (node->right->low, node->right->high))
2965 {
2966 if (!node_has_low_bound (node, index_type))
2967 {
2968 emit_cmp_and_jump_insns (index,
2969 convert_modes
2970 (mode, imode,
2971 expand_normal (node->high),
2972 unsignedp),
2973 LT, NULL_RTX, mode, unsignedp,
2974 default_label);
2975 }
2976
2977 emit_case_nodes (index, node->right, default_label, index_type);
2978 }
2979 else
2980 /* We cannot process node->right normally
2981 since we haven't ruled out the numbers less than
2982 this node's value. So handle node->right explicitly. */
2983 do_jump_if_equal (mode, index,
2984 convert_modes
2985 (mode, imode,
2986 expand_normal (node->right->low),
2987 unsignedp),
2988 label_rtx (node->right->code_label), unsignedp);
2989 }
2990
2991 else if (node->right == 0 && node->left != 0)
2992 {
2993 /* Just one subtree, on the left. */
2994 if (node->left->left || node->left->right
2995 || !tree_int_cst_equal (node->left->low, node->left->high))
2996 {
2997 if (!node_has_high_bound (node, index_type))
2998 {
2999 emit_cmp_and_jump_insns (index,
3000 convert_modes
3001 (mode, imode,
3002 expand_normal (node->high),
3003 unsignedp),
3004 GT, NULL_RTX, mode, unsignedp,
3005 default_label);
3006 }
3007
3008 emit_case_nodes (index, node->left, default_label, index_type);
3009 }
3010 else
3011 /* We cannot process node->left normally
3012 since we haven't ruled out the numbers less than
3013 this node's value. So handle node->left explicitly. */
3014 do_jump_if_equal (mode, index,
3015 convert_modes
3016 (mode, imode,
3017 expand_normal (node->left->low),
3018 unsignedp),
3019 label_rtx (node->left->code_label), unsignedp);
3020 }
3021 }
3022 else
3023 {
3024 /* Node is a range. These cases are very similar to those for a single
3025 value, except that we do not start by testing whether this node
3026 is the one to branch to. */
3027
3028 if (node->right != 0 && node->left != 0)
3029 {
3030 /* Node has subtrees on both sides.
3031 If the right-hand subtree is bounded,
3032 test for it first, since we can go straight there.
3033 Otherwise, we need to make a branch in the control structure,
3034 then handle the two subtrees. */
3035 tree test_label = 0;
3036
3037 if (node_is_bounded (node->right, index_type))
3038 /* Right hand node is fully bounded so we can eliminate any
3039 testing and branch directly to the target code. */
3040 emit_cmp_and_jump_insns (index,
3041 convert_modes
3042 (mode, imode,
3043 expand_normal (node->high),
3044 unsignedp),
3045 GT, NULL_RTX, mode, unsignedp,
3046 label_rtx (node->right->code_label));
3047 else
3048 {
3049 /* Right hand node requires testing.
3050 Branch to a label where we will handle it later. */
3051
3052 test_label = build_decl (CURR_INSN_LOCATION,
3053 LABEL_DECL, NULL_TREE, NULL_TREE);
3054 emit_cmp_and_jump_insns (index,
3055 convert_modes
3056 (mode, imode,
3057 expand_normal (node->high),
3058 unsignedp),
3059 GT, NULL_RTX, mode, unsignedp,
3060 label_rtx (test_label));
3061 }
3062
3063 /* Value belongs to this node or to the left-hand subtree. */
3064
3065 emit_cmp_and_jump_insns (index,
3066 convert_modes
3067 (mode, imode,
3068 expand_normal (node->low),
3069 unsignedp),
3070 GE, NULL_RTX, mode, unsignedp,
3071 label_rtx (node->code_label));
3072
3073 /* Handle the left-hand subtree. */
3074 emit_case_nodes (index, node->left, default_label, index_type);
3075
3076 /* If right node had to be handled later, do that now. */
3077
3078 if (test_label)
3079 {
3080 /* If the left-hand subtree fell through,
3081 don't let it fall into the right-hand subtree. */
3082 if (default_label)
3083 emit_jump (default_label);
3084
3085 expand_label (test_label);
3086 emit_case_nodes (index, node->right, default_label, index_type);
3087 }
3088 }
3089
3090 else if (node->right != 0 && node->left == 0)
3091 {
3092 /* Deal with values to the left of this node,
3093 if they are possible. */
3094 if (!node_has_low_bound (node, index_type))
3095 {
3096 emit_cmp_and_jump_insns (index,
3097 convert_modes
3098 (mode, imode,
3099 expand_normal (node->low),
3100 unsignedp),
3101 LT, NULL_RTX, mode, unsignedp,
3102 default_label);
3103 }
3104
3105 /* Value belongs to this node or to the right-hand subtree. */
3106
3107 emit_cmp_and_jump_insns (index,
3108 convert_modes
3109 (mode, imode,
3110 expand_normal (node->high),
3111 unsignedp),
3112 LE, NULL_RTX, mode, unsignedp,
3113 label_rtx (node->code_label));
3114
3115 emit_case_nodes (index, node->right, default_label, index_type);
3116 }
3117
3118 else if (node->right == 0 && node->left != 0)
3119 {
3120 /* Deal with values to the right of this node,
3121 if they are possible. */
3122 if (!node_has_high_bound (node, index_type))
3123 {
3124 emit_cmp_and_jump_insns (index,
3125 convert_modes
3126 (mode, imode,
3127 expand_normal (node->high),
3128 unsignedp),
3129 GT, NULL_RTX, mode, unsignedp,
3130 default_label);
3131 }
3132
3133 /* Value belongs to this node or to the left-hand subtree. */
3134
3135 emit_cmp_and_jump_insns (index,
3136 convert_modes
3137 (mode, imode,
3138 expand_normal (node->low),
3139 unsignedp),
3140 GE, NULL_RTX, mode, unsignedp,
3141 label_rtx (node->code_label));
3142
3143 emit_case_nodes (index, node->left, default_label, index_type);
3144 }
3145
3146 else
3147 {
3148 /* Node has no children so we check low and high bounds to remove
3149 redundant tests. Only one of the bounds can exist,
3150 since otherwise this node is bounded--a case tested already. */
3151 int high_bound = node_has_high_bound (node, index_type);
3152 int low_bound = node_has_low_bound (node, index_type);
3153
3154 if (!high_bound && low_bound)
3155 {
3156 emit_cmp_and_jump_insns (index,
3157 convert_modes
3158 (mode, imode,
3159 expand_normal (node->high),
3160 unsignedp),
3161 GT, NULL_RTX, mode, unsignedp,
3162 default_label);
3163 }
3164
3165 else if (!low_bound && high_bound)
3166 {
3167 emit_cmp_and_jump_insns (index,
3168 convert_modes
3169 (mode, imode,
3170 expand_normal (node->low),
3171 unsignedp),
3172 LT, NULL_RTX, mode, unsignedp,
3173 default_label);
3174 }
3175 else if (!low_bound && !high_bound)
3176 {
3177 /* Widen LOW and HIGH to the same width as INDEX. */
3178 tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
3179 tree low = build1 (CONVERT_EXPR, type, node->low);
3180 tree high = build1 (CONVERT_EXPR, type, node->high);
3181 rtx low_rtx, new_index, new_bound;
3182
3183 /* Instead of doing two branches, emit one unsigned branch for
3184 (index-low) > (high-low). */
3185 low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL);
3186 new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
3187 NULL_RTX, unsignedp,
3188 OPTAB_WIDEN);
3189 new_bound = expand_expr (fold_build2 (MINUS_EXPR, type,
3190 high, low),
3191 NULL_RTX, mode, EXPAND_NORMAL);
3192
3193 emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
3194 mode, 1, default_label);
3195 }
3196
3197 emit_jump (label_rtx (node->code_label));
3198 }
3199 }
3200 }
3201