comparison gcc/stmt.c @ 16:04ced10e8804

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