Daily bump.
[official-gcc.git] / gcc / stmt.c
blob6c62a129601ccb65d5f7cb289c197d5e653003d8
1 /* Expands front end tree to back end RTL for GCC
2 Copyright (C) 1987-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file handles the generation of rtl code from tree structure
21 above the level of expressions, using subroutines in exp*.c and emit-rtl.c.
22 The functions whose names start with `expand_' are called by the
23 expander to generate RTL instructions for various kinds of constructs. */
25 #include "config.h"
26 #include "system.h"
27 #include "coretypes.h"
28 #include "tm.h"
30 #include "rtl.h"
31 #include "hard-reg-set.h"
32 #include "hash-set.h"
33 #include "machmode.h"
34 #include "vec.h"
35 #include "double-int.h"
36 #include "input.h"
37 #include "alias.h"
38 #include "symtab.h"
39 #include "wide-int.h"
40 #include "inchash.h"
41 #include "tree.h"
42 #include "fold-const.h"
43 #include "varasm.h"
44 #include "stor-layout.h"
45 #include "tm_p.h"
46 #include "flags.h"
47 #include "except.h"
48 #include "function.h"
49 #include "insn-config.h"
50 #include "hashtab.h"
51 #include "statistics.h"
52 #include "real.h"
53 #include "fixed-value.h"
54 #include "expmed.h"
55 #include "dojump.h"
56 #include "explow.h"
57 #include "calls.h"
58 #include "emit-rtl.h"
59 #include "stmt.h"
60 #include "expr.h"
61 #include "libfuncs.h"
62 #include "recog.h"
63 #include "diagnostic-core.h"
64 #include "output.h"
65 #include "langhooks.h"
66 #include "predict.h"
67 #include "insn-codes.h"
68 #include "optabs.h"
69 #include "target.h"
70 #include "cfganal.h"
71 #include "basic-block.h"
72 #include "tree-ssa-alias.h"
73 #include "internal-fn.h"
74 #include "gimple-expr.h"
75 #include "is-a.h"
76 #include "gimple.h"
77 #include "regs.h"
78 #include "alloc-pool.h"
79 #include "pretty-print.h"
80 #include "params.h"
81 #include "dumpfile.h"
82 #include "builtins.h"
85 /* Functions and data structures for expanding case statements. */
87 /* Case label structure, used to hold info on labels within case
88 statements. We handle "range" labels; for a single-value label
89 as in C, the high and low limits are the same.
91 We start with a vector of case nodes sorted in ascending order, and
92 the default label as the last element in the vector. Before expanding
93 to RTL, we transform this vector into a list linked via the RIGHT
94 fields in the case_node struct. Nodes with higher case values are
95 later in the list.
97 Switch statements can be output in three forms. A branch table is
98 used if there are more than a few labels and the labels are dense
99 within the range between the smallest and largest case value. If a
100 branch table is used, no further manipulations are done with the case
101 node chain.
103 The alternative to the use of a branch table is to generate a series
104 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
105 and PARENT fields to hold a binary tree. Initially the tree is
106 totally unbalanced, with everything on the right. We balance the tree
107 with nodes on the left having lower case values than the parent
108 and nodes on the right having higher values. We then output the tree
109 in order.
111 For very small, suitable switch statements, we can generate a series
112 of simple bit test and branches instead. */
114 struct case_node
116 struct case_node *left; /* Left son in binary tree */
117 struct case_node *right; /* Right son in binary tree; also node chain */
118 struct case_node *parent; /* Parent of node in binary tree */
119 tree low; /* Lowest index value for this label */
120 tree high; /* Highest index value for this label */
121 tree code_label; /* Label to jump to when node matches */
122 int prob; /* Probability of taking this case. */
123 /* Probability of reaching subtree rooted at this node */
124 int subtree_prob;
127 typedef struct case_node case_node;
128 typedef struct case_node *case_node_ptr;
130 extern basic_block label_to_block_fn (struct function *, tree);
132 static bool check_unique_operand_names (tree, tree, tree);
133 static char *resolve_operand_name_1 (char *, tree, tree, tree);
134 static void balance_case_nodes (case_node_ptr *, case_node_ptr);
135 static int node_has_low_bound (case_node_ptr, tree);
136 static int node_has_high_bound (case_node_ptr, tree);
137 static int node_is_bounded (case_node_ptr, tree);
138 static void emit_case_nodes (rtx, case_node_ptr, rtx, int, tree);
140 /* Return the rtx-label that corresponds to a LABEL_DECL,
141 creating it if necessary. */
144 label_rtx (tree label)
146 gcc_assert (TREE_CODE (label) == LABEL_DECL);
148 if (!DECL_RTL_SET_P (label))
150 rtx_code_label *r = gen_label_rtx ();
151 SET_DECL_RTL (label, r);
152 if (FORCED_LABEL (label) || DECL_NONLOCAL (label))
153 LABEL_PRESERVE_P (r) = 1;
156 return DECL_RTL (label);
159 /* As above, but also put it on the forced-reference list of the
160 function that contains it. */
162 force_label_rtx (tree label)
164 rtx_insn *ref = as_a <rtx_insn *> (label_rtx (label));
165 tree function = decl_function_context (label);
167 gcc_assert (function);
169 forced_labels = gen_rtx_INSN_LIST (VOIDmode, ref, forced_labels);
170 return ref;
173 /* Add an unconditional jump to LABEL as the next sequential instruction. */
175 void
176 emit_jump (rtx label)
178 do_pending_stack_adjust ();
179 emit_jump_insn (gen_jump (label));
180 emit_barrier ();
183 /* Handle goto statements and the labels that they can go to. */
185 /* Specify the location in the RTL code of a label LABEL,
186 which is a LABEL_DECL tree node.
188 This is used for the kind of label that the user can jump to with a
189 goto statement, and for alternatives of a switch or case statement.
190 RTL labels generated for loops and conditionals don't go through here;
191 they are generated directly at the RTL level, by other functions below.
193 Note that this has nothing to do with defining label *names*.
194 Languages vary in how they do that and what that even means. */
196 void
197 expand_label (tree label)
199 rtx_insn *label_r = as_a <rtx_insn *> (label_rtx (label));
201 do_pending_stack_adjust ();
202 emit_label (label_r);
203 if (DECL_NAME (label))
204 LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label));
206 if (DECL_NONLOCAL (label))
208 expand_builtin_setjmp_receiver (NULL);
209 nonlocal_goto_handler_labels
210 = gen_rtx_INSN_LIST (VOIDmode, label_r,
211 nonlocal_goto_handler_labels);
214 if (FORCED_LABEL (label))
215 forced_labels = gen_rtx_INSN_LIST (VOIDmode, label_r, forced_labels);
217 if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
218 maybe_set_first_label_num (label_r);
221 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
222 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
223 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
224 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
225 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
226 constraint allows the use of a register operand. And, *IS_INOUT
227 will be true if the operand is read-write, i.e., if it is used as
228 an input as well as an output. If *CONSTRAINT_P is not in
229 canonical form, it will be made canonical. (Note that `+' will be
230 replaced with `=' as part of this process.)
232 Returns TRUE if all went well; FALSE if an error occurred. */
234 bool
235 parse_output_constraint (const char **constraint_p, int operand_num,
236 int ninputs, int noutputs, bool *allows_mem,
237 bool *allows_reg, bool *is_inout)
239 const char *constraint = *constraint_p;
240 const char *p;
242 /* Assume the constraint doesn't allow the use of either a register
243 or memory. */
244 *allows_mem = false;
245 *allows_reg = false;
247 /* Allow the `=' or `+' to not be at the beginning of the string,
248 since it wasn't explicitly documented that way, and there is a
249 large body of code that puts it last. Swap the character to
250 the front, so as not to uglify any place else. */
251 p = strchr (constraint, '=');
252 if (!p)
253 p = strchr (constraint, '+');
255 /* If the string doesn't contain an `=', issue an error
256 message. */
257 if (!p)
259 error ("output operand constraint lacks %<=%>");
260 return false;
263 /* If the constraint begins with `+', then the operand is both read
264 from and written to. */
265 *is_inout = (*p == '+');
267 /* Canonicalize the output constraint so that it begins with `='. */
268 if (p != constraint || *is_inout)
270 char *buf;
271 size_t c_len = strlen (constraint);
273 if (p != constraint)
274 warning (0, "output constraint %qc for operand %d "
275 "is not at the beginning",
276 *p, operand_num);
278 /* Make a copy of the constraint. */
279 buf = XALLOCAVEC (char, c_len + 1);
280 strcpy (buf, constraint);
281 /* Swap the first character and the `=' or `+'. */
282 buf[p - constraint] = buf[0];
283 /* Make sure the first character is an `='. (Until we do this,
284 it might be a `+'.) */
285 buf[0] = '=';
286 /* Replace the constraint with the canonicalized string. */
287 *constraint_p = ggc_alloc_string (buf, c_len);
288 constraint = *constraint_p;
291 /* Loop through the constraint string. */
292 for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p))
293 switch (*p)
295 case '+':
296 case '=':
297 error ("operand constraint contains incorrectly positioned "
298 "%<+%> or %<=%>");
299 return false;
301 case '%':
302 if (operand_num + 1 == ninputs + noutputs)
304 error ("%<%%%> constraint used with last operand");
305 return false;
307 break;
309 case '?': case '!': case '*': case '&': case '#':
310 case '$': case '^':
311 case 'E': case 'F': case 'G': case 'H':
312 case 's': case 'i': case 'n':
313 case 'I': case 'J': case 'K': case 'L': case 'M':
314 case 'N': case 'O': case 'P': case ',':
315 break;
317 case '0': case '1': case '2': case '3': case '4':
318 case '5': case '6': case '7': case '8': case '9':
319 case '[':
320 error ("matching constraint not valid in output operand");
321 return false;
323 case '<': case '>':
324 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
325 excepting those that expand_call created. So match memory
326 and hope. */
327 *allows_mem = true;
328 break;
330 case 'g': case 'X':
331 *allows_reg = true;
332 *allows_mem = true;
333 break;
335 default:
336 if (!ISALPHA (*p))
337 break;
338 enum constraint_num cn = lookup_constraint (p);
339 if (reg_class_for_constraint (cn) != NO_REGS
340 || insn_extra_address_constraint (cn))
341 *allows_reg = true;
342 else if (insn_extra_memory_constraint (cn))
343 *allows_mem = true;
344 else
345 insn_extra_constraint_allows_reg_mem (cn, allows_reg, allows_mem);
346 break;
349 return true;
352 /* Similar, but for input constraints. */
354 bool
355 parse_input_constraint (const char **constraint_p, int input_num,
356 int ninputs, int noutputs, int ninout,
357 const char * const * constraints,
358 bool *allows_mem, bool *allows_reg)
360 const char *constraint = *constraint_p;
361 const char *orig_constraint = constraint;
362 size_t c_len = strlen (constraint);
363 size_t j;
364 bool saw_match = false;
366 /* Assume the constraint doesn't allow the use of either
367 a register or memory. */
368 *allows_mem = false;
369 *allows_reg = false;
371 /* Make sure constraint has neither `=', `+', nor '&'. */
373 for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
374 switch (constraint[j])
376 case '+': case '=': case '&':
377 if (constraint == orig_constraint)
379 error ("input operand constraint contains %qc", constraint[j]);
380 return false;
382 break;
384 case '%':
385 if (constraint == orig_constraint
386 && input_num + 1 == ninputs - ninout)
388 error ("%<%%%> constraint used with last operand");
389 return false;
391 break;
393 case '<': case '>':
394 case '?': case '!': case '*': case '#':
395 case '$': case '^':
396 case 'E': case 'F': case 'G': case 'H':
397 case 's': case 'i': case 'n':
398 case 'I': case 'J': case 'K': case 'L': case 'M':
399 case 'N': case 'O': case 'P': case ',':
400 break;
402 /* Whether or not a numeric constraint allows a register is
403 decided by the matching constraint, and so there is no need
404 to do anything special with them. We must handle them in
405 the default case, so that we don't unnecessarily force
406 operands to memory. */
407 case '0': case '1': case '2': case '3': case '4':
408 case '5': case '6': case '7': case '8': case '9':
410 char *end;
411 unsigned long match;
413 saw_match = true;
415 match = strtoul (constraint + j, &end, 10);
416 if (match >= (unsigned long) noutputs)
418 error ("matching constraint references invalid operand number");
419 return false;
422 /* Try and find the real constraint for this dup. Only do this
423 if the matching constraint is the only alternative. */
424 if (*end == '\0'
425 && (j == 0 || (j == 1 && constraint[0] == '%')))
427 constraint = constraints[match];
428 *constraint_p = constraint;
429 c_len = strlen (constraint);
430 j = 0;
431 /* ??? At the end of the loop, we will skip the first part of
432 the matched constraint. This assumes not only that the
433 other constraint is an output constraint, but also that
434 the '=' or '+' come first. */
435 break;
437 else
438 j = end - constraint;
439 /* Anticipate increment at end of loop. */
440 j--;
442 /* Fall through. */
444 case 'g': case 'X':
445 *allows_reg = true;
446 *allows_mem = true;
447 break;
449 default:
450 if (! ISALPHA (constraint[j]))
452 error ("invalid punctuation %qc in constraint", constraint[j]);
453 return false;
455 enum constraint_num cn = lookup_constraint (constraint + j);
456 if (reg_class_for_constraint (cn) != NO_REGS
457 || insn_extra_address_constraint (cn))
458 *allows_reg = true;
459 else if (insn_extra_memory_constraint (cn))
460 *allows_mem = true;
461 else
462 insn_extra_constraint_allows_reg_mem (cn, allows_reg, allows_mem);
463 break;
466 if (saw_match && !*allows_reg)
467 warning (0, "matching constraint does not allow a register");
469 return true;
472 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
473 can be an asm-declared register. Called via walk_tree. */
475 static tree
476 decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED,
477 void *data)
479 tree decl = *declp;
480 const HARD_REG_SET *const regs = (const HARD_REG_SET *) data;
482 if (TREE_CODE (decl) == VAR_DECL)
484 if (DECL_HARD_REGISTER (decl)
485 && REG_P (DECL_RTL (decl))
486 && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
488 rtx reg = DECL_RTL (decl);
490 if (overlaps_hard_reg_set_p (*regs, GET_MODE (reg), REGNO (reg)))
491 return decl;
493 walk_subtrees = 0;
495 else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL)
496 walk_subtrees = 0;
497 return NULL_TREE;
500 /* If there is an overlap between *REGS and DECL, return the first overlap
501 found. */
502 tree
503 tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs)
505 return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL);
509 /* A subroutine of expand_asm_operands. Check that all operand names
510 are unique. Return true if so. We rely on the fact that these names
511 are identifiers, and so have been canonicalized by get_identifier,
512 so all we need are pointer comparisons. */
514 static bool
515 check_unique_operand_names (tree outputs, tree inputs, tree labels)
517 tree i, j, i_name = NULL_TREE;
519 for (i = outputs; i ; i = TREE_CHAIN (i))
521 i_name = TREE_PURPOSE (TREE_PURPOSE (i));
522 if (! i_name)
523 continue;
525 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
526 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
527 goto failure;
530 for (i = inputs; i ; i = TREE_CHAIN (i))
532 i_name = TREE_PURPOSE (TREE_PURPOSE (i));
533 if (! i_name)
534 continue;
536 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
537 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
538 goto failure;
539 for (j = outputs; j ; j = TREE_CHAIN (j))
540 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
541 goto failure;
544 for (i = labels; i ; i = TREE_CHAIN (i))
546 i_name = TREE_PURPOSE (i);
547 if (! i_name)
548 continue;
550 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
551 if (simple_cst_equal (i_name, TREE_PURPOSE (j)))
552 goto failure;
553 for (j = inputs; j ; j = TREE_CHAIN (j))
554 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
555 goto failure;
558 return true;
560 failure:
561 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name));
562 return false;
565 /* A subroutine of expand_asm_operands. Resolve the names of the operands
566 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
567 STRING and in the constraints to those numbers. */
569 tree
570 resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels)
572 char *buffer;
573 char *p;
574 const char *c;
575 tree t;
577 check_unique_operand_names (outputs, inputs, labels);
579 /* Substitute [<name>] in input constraint strings. There should be no
580 named operands in output constraints. */
581 for (t = inputs; t ; t = TREE_CHAIN (t))
583 c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
584 if (strchr (c, '[') != NULL)
586 p = buffer = xstrdup (c);
587 while ((p = strchr (p, '[')) != NULL)
588 p = resolve_operand_name_1 (p, outputs, inputs, NULL);
589 TREE_VALUE (TREE_PURPOSE (t))
590 = build_string (strlen (buffer), buffer);
591 free (buffer);
595 /* Now check for any needed substitutions in the template. */
596 c = TREE_STRING_POINTER (string);
597 while ((c = strchr (c, '%')) != NULL)
599 if (c[1] == '[')
600 break;
601 else if (ISALPHA (c[1]) && c[2] == '[')
602 break;
603 else
605 c += 1 + (c[1] == '%');
606 continue;
610 if (c)
612 /* OK, we need to make a copy so we can perform the substitutions.
613 Assume that we will not need extra space--we get to remove '['
614 and ']', which means we cannot have a problem until we have more
615 than 999 operands. */
616 buffer = xstrdup (TREE_STRING_POINTER (string));
617 p = buffer + (c - TREE_STRING_POINTER (string));
619 while ((p = strchr (p, '%')) != NULL)
621 if (p[1] == '[')
622 p += 1;
623 else if (ISALPHA (p[1]) && p[2] == '[')
624 p += 2;
625 else
627 p += 1 + (p[1] == '%');
628 continue;
631 p = resolve_operand_name_1 (p, outputs, inputs, labels);
634 string = build_string (strlen (buffer), buffer);
635 free (buffer);
638 return string;
641 /* A subroutine of resolve_operand_names. P points to the '[' for a
642 potential named operand of the form [<name>]. In place, replace
643 the name and brackets with a number. Return a pointer to the
644 balance of the string after substitution. */
646 static char *
647 resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels)
649 char *q;
650 int op;
651 tree t;
653 /* Collect the operand name. */
654 q = strchr (++p, ']');
655 if (!q)
657 error ("missing close brace for named operand");
658 return strchr (p, '\0');
660 *q = '\0';
662 /* Resolve the name to a number. */
663 for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
665 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
666 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
667 goto found;
669 for (t = inputs; t ; t = TREE_CHAIN (t), op++)
671 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
672 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
673 goto found;
675 for (t = labels; t ; t = TREE_CHAIN (t), op++)
677 tree name = TREE_PURPOSE (t);
678 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
679 goto found;
682 error ("undefined named operand %qs", identifier_to_locale (p));
683 op = 0;
685 found:
686 /* Replace the name with the number. Unfortunately, not all libraries
687 get the return value of sprintf correct, so search for the end of the
688 generated string by hand. */
689 sprintf (--p, "%d", op);
690 p = strchr (p, '\0');
692 /* Verify the no extra buffer space assumption. */
693 gcc_assert (p <= q);
695 /* Shift the rest of the buffer down to fill the gap. */
696 memmove (p, q + 1, strlen (q + 1) + 1);
698 return p;
702 /* Generate RTL to return directly from the current function.
703 (That is, we bypass any return value.) */
705 void
706 expand_naked_return (void)
708 rtx end_label;
710 clear_pending_stack_adjust ();
711 do_pending_stack_adjust ();
713 end_label = naked_return_label;
714 if (end_label == 0)
715 end_label = naked_return_label = gen_label_rtx ();
717 emit_jump (end_label);
720 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
721 is the probability of jumping to LABEL. */
722 static void
723 do_jump_if_equal (machine_mode mode, rtx op0, rtx op1, rtx label,
724 int unsignedp, int prob)
726 gcc_assert (prob <= REG_BR_PROB_BASE);
727 do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
728 NULL_RTX, NULL_RTX, label, prob);
731 /* Do the insertion of a case label into case_list. The labels are
732 fed to us in descending order from the sorted vector of case labels used
733 in the tree part of the middle end. So the list we construct is
734 sorted in ascending order.
736 LABEL is the case label to be inserted. LOW and HIGH are the bounds
737 against which the index is compared to jump to LABEL and PROB is the
738 estimated probability LABEL is reached from the switch statement. */
740 static struct case_node *
741 add_case_node (struct case_node *head, tree low, tree high,
742 tree label, int prob, alloc_pool case_node_pool)
744 struct case_node *r;
746 gcc_checking_assert (low);
747 gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high)));
749 /* Add this label to the chain. */
750 r = (struct case_node *) pool_alloc (case_node_pool);
751 r->low = low;
752 r->high = high;
753 r->code_label = label;
754 r->parent = r->left = NULL;
755 r->prob = prob;
756 r->subtree_prob = prob;
757 r->right = head;
758 return r;
761 /* Dump ROOT, a list or tree of case nodes, to file. */
763 static void
764 dump_case_nodes (FILE *f, struct case_node *root,
765 int indent_step, int indent_level)
767 if (root == 0)
768 return;
769 indent_level++;
771 dump_case_nodes (f, root->left, indent_step, indent_level);
773 fputs (";; ", f);
774 fprintf (f, "%*s", indent_step * indent_level, "");
775 print_dec (root->low, f, TYPE_SIGN (TREE_TYPE (root->low)));
776 if (!tree_int_cst_equal (root->low, root->high))
778 fprintf (f, " ... ");
779 print_dec (root->high, f, TYPE_SIGN (TREE_TYPE (root->high)));
781 fputs ("\n", f);
783 dump_case_nodes (f, root->right, indent_step, indent_level);
786 #ifndef HAVE_casesi
787 #define HAVE_casesi 0
788 #endif
790 #ifndef HAVE_tablejump
791 #define HAVE_tablejump 0
792 #endif
794 /* Return the smallest number of different values for which it is best to use a
795 jump-table instead of a tree of conditional branches. */
797 static unsigned int
798 case_values_threshold (void)
800 unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
802 if (threshold == 0)
803 threshold = targetm.case_values_threshold ();
805 return threshold;
808 /* Return true if a switch should be expanded as a decision tree.
809 RANGE is the difference between highest and lowest case.
810 UNIQ is number of unique case node targets, not counting the default case.
811 COUNT is the number of comparisons needed, not counting the default case. */
813 static bool
814 expand_switch_as_decision_tree_p (tree range,
815 unsigned int uniq ATTRIBUTE_UNUSED,
816 unsigned int count)
818 int max_ratio;
820 /* If neither casesi or tablejump is available, or flag_jump_tables
821 over-ruled us, we really have no choice. */
822 if (!HAVE_casesi && !HAVE_tablejump)
823 return true;
824 if (!flag_jump_tables)
825 return true;
826 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
827 if (flag_pic)
828 return true;
829 #endif
831 /* If the switch is relatively small such that the cost of one
832 indirect jump on the target are higher than the cost of a
833 decision tree, go with the decision tree.
835 If range of values is much bigger than number of values,
836 or if it is too large to represent in a HOST_WIDE_INT,
837 make a sequence of conditional branches instead of a dispatch.
839 The definition of "much bigger" depends on whether we are
840 optimizing for size or for speed. If the former, the maximum
841 ratio range/count = 3, because this was found to be the optimal
842 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
843 10 is much older, and was probably selected after an extensive
844 benchmarking investigation on numerous platforms. Or maybe it
845 just made sense to someone at some point in the history of GCC,
846 who knows... */
847 max_ratio = optimize_insn_for_size_p () ? 3 : 10;
848 if (count < case_values_threshold ()
849 || ! tree_fits_uhwi_p (range)
850 || compare_tree_int (range, max_ratio * count) > 0)
851 return true;
853 return false;
856 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
857 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
858 DEFAULT_PROB is the estimated probability that it jumps to
859 DEFAULT_LABEL.
861 We generate a binary decision tree to select the appropriate target
862 code. This is done as follows:
864 If the index is a short or char that we do not have
865 an insn to handle comparisons directly, convert it to
866 a full integer now, rather than letting each comparison
867 generate the conversion.
869 Load the index into a register.
871 The list of cases is rearranged into a binary tree,
872 nearly optimal assuming equal probability for each case.
874 The tree is transformed into RTL, eliminating redundant
875 test conditions at the same time.
877 If program flow could reach the end of the decision tree
878 an unconditional jump to the default code is emitted.
880 The above process is unaware of the CFG. The caller has to fix up
881 the CFG itself. This is done in cfgexpand.c. */
883 static void
884 emit_case_decision_tree (tree index_expr, tree index_type,
885 struct case_node *case_list, rtx default_label,
886 int default_prob)
888 rtx index = expand_normal (index_expr);
890 if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
891 && ! have_insn_for (COMPARE, GET_MODE (index)))
893 int unsignedp = TYPE_UNSIGNED (index_type);
894 machine_mode wider_mode;
895 for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
896 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
897 if (have_insn_for (COMPARE, wider_mode))
899 index = convert_to_mode (wider_mode, index, unsignedp);
900 break;
904 do_pending_stack_adjust ();
906 if (MEM_P (index))
908 index = copy_to_reg (index);
909 if (TREE_CODE (index_expr) == SSA_NAME)
910 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr), index);
913 balance_case_nodes (&case_list, NULL);
915 if (dump_file && (dump_flags & TDF_DETAILS))
917 int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
918 fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
919 dump_case_nodes (dump_file, case_list, indent_step, 0);
922 emit_case_nodes (index, case_list, default_label, default_prob, index_type);
923 if (default_label)
924 emit_jump (default_label);
927 /* Return the sum of probabilities of outgoing edges of basic block BB. */
929 static int
930 get_outgoing_edge_probs (basic_block bb)
932 edge e;
933 edge_iterator ei;
934 int prob_sum = 0;
935 if (!bb)
936 return 0;
937 FOR_EACH_EDGE (e, ei, bb->succs)
938 prob_sum += e->probability;
939 return prob_sum;
942 /* Computes the conditional probability of jumping to a target if the branch
943 instruction is executed.
944 TARGET_PROB is the estimated probability of jumping to a target relative
945 to some basic block BB.
946 BASE_PROB is the probability of reaching the branch instruction relative
947 to the same basic block BB. */
949 static inline int
950 conditional_probability (int target_prob, int base_prob)
952 if (base_prob > 0)
954 gcc_assert (target_prob >= 0);
955 gcc_assert (target_prob <= base_prob);
956 return GCOV_COMPUTE_SCALE (target_prob, base_prob);
958 return -1;
961 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
962 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
963 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
964 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
966 First, a jump insn is emitted. First we try "casesi". If that
967 fails, try "tablejump". A target *must* have one of them (or both).
969 Then, a table with the target labels is emitted.
971 The process is unaware of the CFG. The caller has to fix up
972 the CFG itself. This is done in cfgexpand.c. */
974 static void
975 emit_case_dispatch_table (tree index_expr, tree index_type,
976 struct case_node *case_list, rtx default_label,
977 tree minval, tree maxval, tree range,
978 basic_block stmt_bb)
980 int i, ncases;
981 struct case_node *n;
982 rtx *labelvec;
983 rtx fallback_label = label_rtx (case_list->code_label);
984 rtx_code_label *table_label = gen_label_rtx ();
985 bool has_gaps = false;
986 edge default_edge = stmt_bb ? EDGE_SUCC (stmt_bb, 0) : NULL;
987 int default_prob = default_edge ? default_edge->probability : 0;
988 int base = get_outgoing_edge_probs (stmt_bb);
989 bool try_with_tablejump = false;
991 int new_default_prob = conditional_probability (default_prob,
992 base);
994 if (! try_casesi (index_type, index_expr, minval, range,
995 table_label, default_label, fallback_label,
996 new_default_prob))
998 /* Index jumptables from zero for suitable values of minval to avoid
999 a subtraction. For the rationale see:
1000 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
1001 if (optimize_insn_for_speed_p ()
1002 && compare_tree_int (minval, 0) > 0
1003 && compare_tree_int (minval, 3) < 0)
1005 minval = build_int_cst (index_type, 0);
1006 range = maxval;
1007 has_gaps = true;
1009 try_with_tablejump = true;
1012 /* Get table of labels to jump to, in order of case index. */
1014 ncases = tree_to_shwi (range) + 1;
1015 labelvec = XALLOCAVEC (rtx, ncases);
1016 memset (labelvec, 0, ncases * sizeof (rtx));
1018 for (n = case_list; n; n = n->right)
1020 /* Compute the low and high bounds relative to the minimum
1021 value since that should fit in a HOST_WIDE_INT while the
1022 actual values may not. */
1023 HOST_WIDE_INT i_low
1024 = tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
1025 n->low, minval));
1026 HOST_WIDE_INT i_high
1027 = tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
1028 n->high, minval));
1029 HOST_WIDE_INT i;
1031 for (i = i_low; i <= i_high; i ++)
1032 labelvec[i]
1033 = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
1036 /* Fill in the gaps with the default. We may have gaps at
1037 the beginning if we tried to avoid the minval subtraction,
1038 so substitute some label even if the default label was
1039 deemed unreachable. */
1040 if (!default_label)
1041 default_label = fallback_label;
1042 for (i = 0; i < ncases; i++)
1043 if (labelvec[i] == 0)
1045 has_gaps = true;
1046 labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
1049 if (has_gaps)
1051 /* There is at least one entry in the jump table that jumps
1052 to default label. The default label can either be reached
1053 through the indirect jump or the direct conditional jump
1054 before that. Split the probability of reaching the
1055 default label among these two jumps. */
1056 new_default_prob = conditional_probability (default_prob/2,
1057 base);
1058 default_prob /= 2;
1059 base -= default_prob;
1061 else
1063 base -= default_prob;
1064 default_prob = 0;
1067 if (default_edge)
1068 default_edge->probability = default_prob;
1070 /* We have altered the probability of the default edge. So the probabilities
1071 of all other edges need to be adjusted so that it sums up to
1072 REG_BR_PROB_BASE. */
1073 if (base)
1075 edge e;
1076 edge_iterator ei;
1077 FOR_EACH_EDGE (e, ei, stmt_bb->succs)
1078 e->probability = GCOV_COMPUTE_SCALE (e->probability, base);
1081 if (try_with_tablejump)
1083 bool ok = try_tablejump (index_type, index_expr, minval, range,
1084 table_label, default_label, new_default_prob);
1085 gcc_assert (ok);
1087 /* Output the table. */
1088 emit_label (table_label);
1090 if (CASE_VECTOR_PC_RELATIVE || flag_pic)
1091 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
1092 gen_rtx_LABEL_REF (Pmode,
1093 table_label),
1094 gen_rtvec_v (ncases, labelvec),
1095 const0_rtx, const0_rtx));
1096 else
1097 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
1098 gen_rtvec_v (ncases, labelvec)));
1100 /* Record no drop-through after the table. */
1101 emit_barrier ();
1104 /* Reset the aux field of all outgoing edges of basic block BB. */
1106 static inline void
1107 reset_out_edges_aux (basic_block bb)
1109 edge e;
1110 edge_iterator ei;
1111 FOR_EACH_EDGE (e, ei, bb->succs)
1112 e->aux = (void *)0;
1115 /* Compute the number of case labels that correspond to each outgoing edge of
1116 STMT. Record this information in the aux field of the edge. */
1118 static inline void
1119 compute_cases_per_edge (gswitch *stmt)
1121 basic_block bb = gimple_bb (stmt);
1122 reset_out_edges_aux (bb);
1123 int ncases = gimple_switch_num_labels (stmt);
1124 for (int i = ncases - 1; i >= 1; --i)
1126 tree elt = gimple_switch_label (stmt, i);
1127 tree lab = CASE_LABEL (elt);
1128 basic_block case_bb = label_to_block_fn (cfun, lab);
1129 edge case_edge = find_edge (bb, case_bb);
1130 case_edge->aux = (void *)((intptr_t)(case_edge->aux) + 1);
1134 /* Terminate a case (Pascal/Ada) or switch (C) statement
1135 in which ORIG_INDEX is the expression to be tested.
1136 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
1137 type as given in the source before any compiler conversions.
1138 Generate the code to test it and jump to the right place. */
1140 void
1141 expand_case (gswitch *stmt)
1143 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
1144 rtx default_label = NULL_RTX;
1145 unsigned int count, uniq;
1146 int i;
1147 int ncases = gimple_switch_num_labels (stmt);
1148 tree index_expr = gimple_switch_index (stmt);
1149 tree index_type = TREE_TYPE (index_expr);
1150 tree elt;
1151 basic_block bb = gimple_bb (stmt);
1153 /* A list of case labels; it is first built as a list and it may then
1154 be rearranged into a nearly balanced binary tree. */
1155 struct case_node *case_list = 0;
1157 /* A pool for case nodes. */
1158 alloc_pool case_node_pool;
1160 /* An ERROR_MARK occurs for various reasons including invalid data type.
1161 ??? Can this still happen, with GIMPLE and all? */
1162 if (index_type == error_mark_node)
1163 return;
1165 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
1166 expressions being INTEGER_CST. */
1167 gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
1169 case_node_pool = create_alloc_pool ("struct case_node pool",
1170 sizeof (struct case_node),
1171 100);
1173 do_pending_stack_adjust ();
1175 /* Find the default case target label. */
1176 default_label = label_rtx (CASE_LABEL (gimple_switch_default_label (stmt)));
1177 edge default_edge = EDGE_SUCC (bb, 0);
1178 int default_prob = default_edge->probability;
1180 /* Get upper and lower bounds of case values. */
1181 elt = gimple_switch_label (stmt, 1);
1182 minval = fold_convert (index_type, CASE_LOW (elt));
1183 elt = gimple_switch_label (stmt, ncases - 1);
1184 if (CASE_HIGH (elt))
1185 maxval = fold_convert (index_type, CASE_HIGH (elt));
1186 else
1187 maxval = fold_convert (index_type, CASE_LOW (elt));
1189 /* Compute span of values. */
1190 range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
1192 /* Listify the labels queue and gather some numbers to decide
1193 how to expand this switch(). */
1194 uniq = 0;
1195 count = 0;
1196 hash_set<tree> seen_labels;
1197 compute_cases_per_edge (stmt);
1199 for (i = ncases - 1; i >= 1; --i)
1201 elt = gimple_switch_label (stmt, i);
1202 tree low = CASE_LOW (elt);
1203 gcc_assert (low);
1204 tree high = CASE_HIGH (elt);
1205 gcc_assert (! high || tree_int_cst_lt (low, high));
1206 tree lab = CASE_LABEL (elt);
1208 /* Count the elements.
1209 A range counts double, since it requires two compares. */
1210 count++;
1211 if (high)
1212 count++;
1214 /* If we have not seen this label yet, then increase the
1215 number of unique case node targets seen. */
1216 if (!seen_labels.add (lab))
1217 uniq++;
1219 /* The bounds on the case range, LOW and HIGH, have to be converted
1220 to case's index type TYPE. Note that the original type of the
1221 case index in the source code is usually "lost" during
1222 gimplification due to type promotion, but the case labels retain the
1223 original type. Make sure to drop overflow flags. */
1224 low = fold_convert (index_type, low);
1225 if (TREE_OVERFLOW (low))
1226 low = wide_int_to_tree (index_type, low);
1228 /* The canonical from of a case label in GIMPLE is that a simple case
1229 has an empty CASE_HIGH. For the casesi and tablejump expanders,
1230 the back ends want simple cases to have high == low. */
1231 if (! high)
1232 high = low;
1233 high = fold_convert (index_type, high);
1234 if (TREE_OVERFLOW (high))
1235 high = wide_int_to_tree (index_type, high);
1237 basic_block case_bb = label_to_block_fn (cfun, lab);
1238 edge case_edge = find_edge (bb, case_bb);
1239 case_list = add_case_node (
1240 case_list, low, high, lab,
1241 case_edge->probability / (intptr_t)(case_edge->aux),
1242 case_node_pool);
1244 reset_out_edges_aux (bb);
1246 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
1247 destination, such as one with a default case only.
1248 It also removes cases that are out of range for the switch
1249 type, so we should never get a zero here. */
1250 gcc_assert (count > 0);
1252 rtx_insn *before_case = get_last_insn ();
1254 /* Decide how to expand this switch.
1255 The two options at this point are a dispatch table (casesi or
1256 tablejump) or a decision tree. */
1258 if (expand_switch_as_decision_tree_p (range, uniq, count))
1259 emit_case_decision_tree (index_expr, index_type,
1260 case_list, default_label,
1261 default_prob);
1262 else
1263 emit_case_dispatch_table (index_expr, index_type,
1264 case_list, default_label,
1265 minval, maxval, range, bb);
1267 reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
1269 free_temp_slots ();
1270 free_alloc_pool (case_node_pool);
1273 /* Expand the dispatch to a short decrement chain if there are few cases
1274 to dispatch to. Likewise if neither casesi nor tablejump is available,
1275 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
1276 tablejump. The index mode is always the mode of integer_type_node.
1277 Trap if no case matches the index.
1279 DISPATCH_INDEX is the index expression to switch on. It should be a
1280 memory or register operand.
1282 DISPATCH_TABLE is a set of case labels. The set should be sorted in
1283 ascending order, be contiguous, starting with value 0, and contain only
1284 single-valued case labels. */
1286 void
1287 expand_sjlj_dispatch_table (rtx dispatch_index,
1288 vec<tree> dispatch_table)
1290 tree index_type = integer_type_node;
1291 machine_mode index_mode = TYPE_MODE (index_type);
1293 int ncases = dispatch_table.length ();
1295 do_pending_stack_adjust ();
1296 rtx_insn *before_case = get_last_insn ();
1298 /* Expand as a decrement-chain if there are 5 or fewer dispatch
1299 labels. This covers more than 98% of the cases in libjava,
1300 and seems to be a reasonable compromise between the "old way"
1301 of expanding as a decision tree or dispatch table vs. the "new
1302 way" with decrement chain or dispatch table. */
1303 if (dispatch_table.length () <= 5
1304 || (!HAVE_casesi && !HAVE_tablejump)
1305 || !flag_jump_tables)
1307 /* Expand the dispatch as a decrement chain:
1309 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1313 if (index == 0) do_0; else index--;
1314 if (index == 0) do_1; else index--;
1316 if (index == 0) do_N; else index--;
1318 This is more efficient than a dispatch table on most machines.
1319 The last "index--" is redundant but the code is trivially dead
1320 and will be cleaned up by later passes. */
1321 rtx index = copy_to_mode_reg (index_mode, dispatch_index);
1322 rtx zero = CONST0_RTX (index_mode);
1323 for (int i = 0; i < ncases; i++)
1325 tree elt = dispatch_table[i];
1326 rtx lab = label_rtx (CASE_LABEL (elt));
1327 do_jump_if_equal (index_mode, index, zero, lab, 0, -1);
1328 force_expand_binop (index_mode, sub_optab,
1329 index, CONST1_RTX (index_mode),
1330 index, 0, OPTAB_DIRECT);
1333 else
1335 /* Similar to expand_case, but much simpler. */
1336 struct case_node *case_list = 0;
1337 alloc_pool case_node_pool = create_alloc_pool ("struct sjlj_case pool",
1338 sizeof (struct case_node),
1339 ncases);
1340 tree index_expr = make_tree (index_type, dispatch_index);
1341 tree minval = build_int_cst (index_type, 0);
1342 tree maxval = CASE_LOW (dispatch_table.last ());
1343 tree range = maxval;
1344 rtx_code_label *default_label = gen_label_rtx ();
1346 for (int i = ncases - 1; i >= 0; --i)
1348 tree elt = dispatch_table[i];
1349 tree low = CASE_LOW (elt);
1350 tree lab = CASE_LABEL (elt);
1351 case_list = add_case_node (case_list, low, low, lab, 0, case_node_pool);
1354 emit_case_dispatch_table (index_expr, index_type,
1355 case_list, default_label,
1356 minval, maxval, range,
1357 BLOCK_FOR_INSN (before_case));
1358 emit_label (default_label);
1359 free_alloc_pool (case_node_pool);
1362 /* Dispatching something not handled? Trap! */
1363 expand_builtin_trap ();
1365 reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
1367 free_temp_slots ();
1371 /* Take an ordered list of case nodes
1372 and transform them into a near optimal binary tree,
1373 on the assumption that any target code selection value is as
1374 likely as any other.
1376 The transformation is performed by splitting the ordered
1377 list into two equal sections plus a pivot. The parts are
1378 then attached to the pivot as left and right branches. Each
1379 branch is then transformed recursively. */
1381 static void
1382 balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
1384 case_node_ptr np;
1386 np = *head;
1387 if (np)
1389 int i = 0;
1390 int ranges = 0;
1391 case_node_ptr *npp;
1392 case_node_ptr left;
1394 /* Count the number of entries on branch. Also count the ranges. */
1396 while (np)
1398 if (!tree_int_cst_equal (np->low, np->high))
1399 ranges++;
1401 i++;
1402 np = np->right;
1405 if (i > 2)
1407 /* Split this list if it is long enough for that to help. */
1408 npp = head;
1409 left = *npp;
1411 /* If there are just three nodes, split at the middle one. */
1412 if (i == 3)
1413 npp = &(*npp)->right;
1414 else
1416 /* Find the place in the list that bisects the list's total cost,
1417 where ranges count as 2.
1418 Here I gets half the total cost. */
1419 i = (i + ranges + 1) / 2;
1420 while (1)
1422 /* Skip nodes while their cost does not reach that amount. */
1423 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
1424 i--;
1425 i--;
1426 if (i <= 0)
1427 break;
1428 npp = &(*npp)->right;
1431 *head = np = *npp;
1432 *npp = 0;
1433 np->parent = parent;
1434 np->left = left;
1436 /* Optimize each of the two split parts. */
1437 balance_case_nodes (&np->left, np);
1438 balance_case_nodes (&np->right, np);
1439 np->subtree_prob = np->prob;
1440 np->subtree_prob += np->left->subtree_prob;
1441 np->subtree_prob += np->right->subtree_prob;
1443 else
1445 /* Else leave this branch as one level,
1446 but fill in `parent' fields. */
1447 np = *head;
1448 np->parent = parent;
1449 np->subtree_prob = np->prob;
1450 for (; np->right; np = np->right)
1452 np->right->parent = np;
1453 (*head)->subtree_prob += np->right->subtree_prob;
1459 /* Search the parent sections of the case node tree
1460 to see if a test for the lower bound of NODE would be redundant.
1461 INDEX_TYPE is the type of the index expression.
1463 The instructions to generate the case decision tree are
1464 output in the same order as nodes are processed so it is
1465 known that if a parent node checks the range of the current
1466 node minus one that the current node is bounded at its lower
1467 span. Thus the test would be redundant. */
1469 static int
1470 node_has_low_bound (case_node_ptr node, tree index_type)
1472 tree low_minus_one;
1473 case_node_ptr pnode;
1475 /* If the lower bound of this node is the lowest value in the index type,
1476 we need not test it. */
1478 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
1479 return 1;
1481 /* If this node has a left branch, the value at the left must be less
1482 than that at this node, so it cannot be bounded at the bottom and
1483 we need not bother testing any further. */
1485 if (node->left)
1486 return 0;
1488 low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low),
1489 node->low,
1490 build_int_cst (TREE_TYPE (node->low), 1));
1492 /* If the subtraction above overflowed, we can't verify anything.
1493 Otherwise, look for a parent that tests our value - 1. */
1495 if (! tree_int_cst_lt (low_minus_one, node->low))
1496 return 0;
1498 for (pnode = node->parent; pnode; pnode = pnode->parent)
1499 if (tree_int_cst_equal (low_minus_one, pnode->high))
1500 return 1;
1502 return 0;
1505 /* Search the parent sections of the case node tree
1506 to see if a test for the upper bound of NODE would be redundant.
1507 INDEX_TYPE is the type of the index expression.
1509 The instructions to generate the case decision tree are
1510 output in the same order as nodes are processed so it is
1511 known that if a parent node checks the range of the current
1512 node plus one that the current node is bounded at its upper
1513 span. Thus the test would be redundant. */
1515 static int
1516 node_has_high_bound (case_node_ptr node, tree index_type)
1518 tree high_plus_one;
1519 case_node_ptr pnode;
1521 /* If there is no upper bound, obviously no test is needed. */
1523 if (TYPE_MAX_VALUE (index_type) == NULL)
1524 return 1;
1526 /* If the upper bound of this node is the highest value in the type
1527 of the index expression, we need not test against it. */
1529 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
1530 return 1;
1532 /* If this node has a right branch, the value at the right must be greater
1533 than that at this node, so it cannot be bounded at the top and
1534 we need not bother testing any further. */
1536 if (node->right)
1537 return 0;
1539 high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high),
1540 node->high,
1541 build_int_cst (TREE_TYPE (node->high), 1));
1543 /* If the addition above overflowed, we can't verify anything.
1544 Otherwise, look for a parent that tests our value + 1. */
1546 if (! tree_int_cst_lt (node->high, high_plus_one))
1547 return 0;
1549 for (pnode = node->parent; pnode; pnode = pnode->parent)
1550 if (tree_int_cst_equal (high_plus_one, pnode->low))
1551 return 1;
1553 return 0;
1556 /* Search the parent sections of the
1557 case node tree to see if both tests for the upper and lower
1558 bounds of NODE would be redundant. */
1560 static int
1561 node_is_bounded (case_node_ptr node, tree index_type)
1563 return (node_has_low_bound (node, index_type)
1564 && node_has_high_bound (node, index_type));
1568 /* Emit step-by-step code to select a case for the value of INDEX.
1569 The thus generated decision tree follows the form of the
1570 case-node binary tree NODE, whose nodes represent test conditions.
1571 INDEX_TYPE is the type of the index of the switch.
1573 Care is taken to prune redundant tests from the decision tree
1574 by detecting any boundary conditions already checked by
1575 emitted rtx. (See node_has_high_bound, node_has_low_bound
1576 and node_is_bounded, above.)
1578 Where the test conditions can be shown to be redundant we emit
1579 an unconditional jump to the target code. As a further
1580 optimization, the subordinates of a tree node are examined to
1581 check for bounded nodes. In this case conditional and/or
1582 unconditional jumps as a result of the boundary check for the
1583 current node are arranged to target the subordinates associated
1584 code for out of bound conditions on the current node.
1586 We can assume that when control reaches the code generated here,
1587 the index value has already been compared with the parents
1588 of this node, and determined to be on the same side of each parent
1589 as this node is. Thus, if this node tests for the value 51,
1590 and a parent tested for 52, we don't need to consider
1591 the possibility of a value greater than 51. If another parent
1592 tests for the value 50, then this node need not test anything. */
1594 static void
1595 emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
1596 int default_prob, tree index_type)
1598 /* If INDEX has an unsigned type, we must make unsigned branches. */
1599 int unsignedp = TYPE_UNSIGNED (index_type);
1600 int probability;
1601 int prob = node->prob, subtree_prob = node->subtree_prob;
1602 machine_mode mode = GET_MODE (index);
1603 machine_mode imode = TYPE_MODE (index_type);
1605 /* Handle indices detected as constant during RTL expansion. */
1606 if (mode == VOIDmode)
1607 mode = imode;
1609 /* See if our parents have already tested everything for us.
1610 If they have, emit an unconditional jump for this node. */
1611 if (node_is_bounded (node, index_type))
1612 emit_jump (label_rtx (node->code_label));
1614 else if (tree_int_cst_equal (node->low, node->high))
1616 probability = conditional_probability (prob, subtree_prob + default_prob);
1617 /* Node is single valued. First see if the index expression matches
1618 this node and then check our children, if any. */
1619 do_jump_if_equal (mode, index,
1620 convert_modes (mode, imode,
1621 expand_normal (node->low),
1622 unsignedp),
1623 label_rtx (node->code_label), unsignedp, probability);
1624 /* Since this case is taken at this point, reduce its weight from
1625 subtree_weight. */
1626 subtree_prob -= prob;
1627 if (node->right != 0 && node->left != 0)
1629 /* This node has children on both sides.
1630 Dispatch to one side or the other
1631 by comparing the index value with this node's value.
1632 If one subtree is bounded, check that one first,
1633 so we can avoid real branches in the tree. */
1635 if (node_is_bounded (node->right, index_type))
1637 probability = conditional_probability (
1638 node->right->prob,
1639 subtree_prob + default_prob);
1640 emit_cmp_and_jump_insns (index,
1641 convert_modes
1642 (mode, imode,
1643 expand_normal (node->high),
1644 unsignedp),
1645 GT, NULL_RTX, mode, unsignedp,
1646 label_rtx (node->right->code_label),
1647 probability);
1648 emit_case_nodes (index, node->left, default_label, default_prob,
1649 index_type);
1652 else if (node_is_bounded (node->left, index_type))
1654 probability = conditional_probability (
1655 node->left->prob,
1656 subtree_prob + default_prob);
1657 emit_cmp_and_jump_insns (index,
1658 convert_modes
1659 (mode, imode,
1660 expand_normal (node->high),
1661 unsignedp),
1662 LT, NULL_RTX, mode, unsignedp,
1663 label_rtx (node->left->code_label),
1664 probability);
1665 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1668 /* If both children are single-valued cases with no
1669 children, finish up all the work. This way, we can save
1670 one ordered comparison. */
1671 else if (tree_int_cst_equal (node->right->low, node->right->high)
1672 && node->right->left == 0
1673 && node->right->right == 0
1674 && tree_int_cst_equal (node->left->low, node->left->high)
1675 && node->left->left == 0
1676 && node->left->right == 0)
1678 /* Neither node is bounded. First distinguish the two sides;
1679 then emit the code for one side at a time. */
1681 /* See if the value matches what the right hand side
1682 wants. */
1683 probability = conditional_probability (
1684 node->right->prob,
1685 subtree_prob + default_prob);
1686 do_jump_if_equal (mode, index,
1687 convert_modes (mode, imode,
1688 expand_normal (node->right->low),
1689 unsignedp),
1690 label_rtx (node->right->code_label),
1691 unsignedp, probability);
1693 /* See if the value matches what the left hand side
1694 wants. */
1695 probability = conditional_probability (
1696 node->left->prob,
1697 subtree_prob + default_prob);
1698 do_jump_if_equal (mode, index,
1699 convert_modes (mode, imode,
1700 expand_normal (node->left->low),
1701 unsignedp),
1702 label_rtx (node->left->code_label),
1703 unsignedp, probability);
1706 else
1708 /* Neither node is bounded. First distinguish the two sides;
1709 then emit the code for one side at a time. */
1711 tree test_label
1712 = build_decl (curr_insn_location (),
1713 LABEL_DECL, NULL_TREE, void_type_node);
1715 /* The default label could be reached either through the right
1716 subtree or the left subtree. Divide the probability
1717 equally. */
1718 probability = conditional_probability (
1719 node->right->subtree_prob + default_prob/2,
1720 subtree_prob + default_prob);
1721 /* See if the value is on the right. */
1722 emit_cmp_and_jump_insns (index,
1723 convert_modes
1724 (mode, imode,
1725 expand_normal (node->high),
1726 unsignedp),
1727 GT, NULL_RTX, mode, unsignedp,
1728 label_rtx (test_label),
1729 probability);
1730 default_prob /= 2;
1732 /* Value must be on the left.
1733 Handle the left-hand subtree. */
1734 emit_case_nodes (index, node->left, default_label, default_prob, index_type);
1735 /* If left-hand subtree does nothing,
1736 go to default. */
1737 if (default_label)
1738 emit_jump (default_label);
1740 /* Code branches here for the right-hand subtree. */
1741 expand_label (test_label);
1742 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1746 else if (node->right != 0 && node->left == 0)
1748 /* Here we have a right child but no left so we issue a conditional
1749 branch to default and process the right child.
1751 Omit the conditional branch to default if the right child
1752 does not have any children and is single valued; it would
1753 cost too much space to save so little time. */
1755 if (node->right->right || node->right->left
1756 || !tree_int_cst_equal (node->right->low, node->right->high))
1758 if (!node_has_low_bound (node, index_type))
1760 probability = conditional_probability (
1761 default_prob/2,
1762 subtree_prob + default_prob);
1763 emit_cmp_and_jump_insns (index,
1764 convert_modes
1765 (mode, imode,
1766 expand_normal (node->high),
1767 unsignedp),
1768 LT, NULL_RTX, mode, unsignedp,
1769 default_label,
1770 probability);
1771 default_prob /= 2;
1774 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1776 else
1778 probability = conditional_probability (
1779 node->right->subtree_prob,
1780 subtree_prob + default_prob);
1781 /* We cannot process node->right normally
1782 since we haven't ruled out the numbers less than
1783 this node's value. So handle node->right explicitly. */
1784 do_jump_if_equal (mode, index,
1785 convert_modes
1786 (mode, imode,
1787 expand_normal (node->right->low),
1788 unsignedp),
1789 label_rtx (node->right->code_label), unsignedp, probability);
1793 else if (node->right == 0 && node->left != 0)
1795 /* Just one subtree, on the left. */
1796 if (node->left->left || node->left->right
1797 || !tree_int_cst_equal (node->left->low, node->left->high))
1799 if (!node_has_high_bound (node, index_type))
1801 probability = conditional_probability (
1802 default_prob/2,
1803 subtree_prob + default_prob);
1804 emit_cmp_and_jump_insns (index,
1805 convert_modes
1806 (mode, imode,
1807 expand_normal (node->high),
1808 unsignedp),
1809 GT, NULL_RTX, mode, unsignedp,
1810 default_label,
1811 probability);
1812 default_prob /= 2;
1815 emit_case_nodes (index, node->left, default_label,
1816 default_prob, index_type);
1818 else
1820 probability = conditional_probability (
1821 node->left->subtree_prob,
1822 subtree_prob + default_prob);
1823 /* We cannot process node->left normally
1824 since we haven't ruled out the numbers less than
1825 this node's value. So handle node->left explicitly. */
1826 do_jump_if_equal (mode, index,
1827 convert_modes
1828 (mode, imode,
1829 expand_normal (node->left->low),
1830 unsignedp),
1831 label_rtx (node->left->code_label), unsignedp, probability);
1835 else
1837 /* Node is a range. These cases are very similar to those for a single
1838 value, except that we do not start by testing whether this node
1839 is the one to branch to. */
1841 if (node->right != 0 && node->left != 0)
1843 /* Node has subtrees on both sides.
1844 If the right-hand subtree is bounded,
1845 test for it first, since we can go straight there.
1846 Otherwise, we need to make a branch in the control structure,
1847 then handle the two subtrees. */
1848 tree test_label = 0;
1850 if (node_is_bounded (node->right, index_type))
1852 /* Right hand node is fully bounded so we can eliminate any
1853 testing and branch directly to the target code. */
1854 probability = conditional_probability (
1855 node->right->subtree_prob,
1856 subtree_prob + default_prob);
1857 emit_cmp_and_jump_insns (index,
1858 convert_modes
1859 (mode, imode,
1860 expand_normal (node->high),
1861 unsignedp),
1862 GT, NULL_RTX, mode, unsignedp,
1863 label_rtx (node->right->code_label),
1864 probability);
1866 else
1868 /* Right hand node requires testing.
1869 Branch to a label where we will handle it later. */
1871 test_label = build_decl (curr_insn_location (),
1872 LABEL_DECL, NULL_TREE, void_type_node);
1873 probability = conditional_probability (
1874 node->right->subtree_prob + default_prob/2,
1875 subtree_prob + default_prob);
1876 emit_cmp_and_jump_insns (index,
1877 convert_modes
1878 (mode, imode,
1879 expand_normal (node->high),
1880 unsignedp),
1881 GT, NULL_RTX, mode, unsignedp,
1882 label_rtx (test_label),
1883 probability);
1884 default_prob /= 2;
1887 /* Value belongs to this node or to the left-hand subtree. */
1889 probability = conditional_probability (
1890 prob,
1891 subtree_prob + default_prob);
1892 emit_cmp_and_jump_insns (index,
1893 convert_modes
1894 (mode, imode,
1895 expand_normal (node->low),
1896 unsignedp),
1897 GE, NULL_RTX, mode, unsignedp,
1898 label_rtx (node->code_label),
1899 probability);
1901 /* Handle the left-hand subtree. */
1902 emit_case_nodes (index, node->left, default_label, default_prob, index_type);
1904 /* If right node had to be handled later, do that now. */
1906 if (test_label)
1908 /* If the left-hand subtree fell through,
1909 don't let it fall into the right-hand subtree. */
1910 if (default_label)
1911 emit_jump (default_label);
1913 expand_label (test_label);
1914 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1918 else if (node->right != 0 && node->left == 0)
1920 /* Deal with values to the left of this node,
1921 if they are possible. */
1922 if (!node_has_low_bound (node, index_type))
1924 probability = conditional_probability (
1925 default_prob/2,
1926 subtree_prob + default_prob);
1927 emit_cmp_and_jump_insns (index,
1928 convert_modes
1929 (mode, imode,
1930 expand_normal (node->low),
1931 unsignedp),
1932 LT, NULL_RTX, mode, unsignedp,
1933 default_label,
1934 probability);
1935 default_prob /= 2;
1938 /* Value belongs to this node or to the right-hand subtree. */
1940 probability = conditional_probability (
1941 prob,
1942 subtree_prob + default_prob);
1943 emit_cmp_and_jump_insns (index,
1944 convert_modes
1945 (mode, imode,
1946 expand_normal (node->high),
1947 unsignedp),
1948 LE, NULL_RTX, mode, unsignedp,
1949 label_rtx (node->code_label),
1950 probability);
1952 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1955 else if (node->right == 0 && node->left != 0)
1957 /* Deal with values to the right of this node,
1958 if they are possible. */
1959 if (!node_has_high_bound (node, index_type))
1961 probability = conditional_probability (
1962 default_prob/2,
1963 subtree_prob + default_prob);
1964 emit_cmp_and_jump_insns (index,
1965 convert_modes
1966 (mode, imode,
1967 expand_normal (node->high),
1968 unsignedp),
1969 GT, NULL_RTX, mode, unsignedp,
1970 default_label,
1971 probability);
1972 default_prob /= 2;
1975 /* Value belongs to this node or to the left-hand subtree. */
1977 probability = conditional_probability (
1978 prob,
1979 subtree_prob + default_prob);
1980 emit_cmp_and_jump_insns (index,
1981 convert_modes
1982 (mode, imode,
1983 expand_normal (node->low),
1984 unsignedp),
1985 GE, NULL_RTX, mode, unsignedp,
1986 label_rtx (node->code_label),
1987 probability);
1989 emit_case_nodes (index, node->left, default_label, default_prob, index_type);
1992 else
1994 /* Node has no children so we check low and high bounds to remove
1995 redundant tests. Only one of the bounds can exist,
1996 since otherwise this node is bounded--a case tested already. */
1997 int high_bound = node_has_high_bound (node, index_type);
1998 int low_bound = node_has_low_bound (node, index_type);
2000 if (!high_bound && low_bound)
2002 probability = conditional_probability (
2003 default_prob,
2004 subtree_prob + default_prob);
2005 emit_cmp_and_jump_insns (index,
2006 convert_modes
2007 (mode, imode,
2008 expand_normal (node->high),
2009 unsignedp),
2010 GT, NULL_RTX, mode, unsignedp,
2011 default_label,
2012 probability);
2015 else if (!low_bound && high_bound)
2017 probability = conditional_probability (
2018 default_prob,
2019 subtree_prob + default_prob);
2020 emit_cmp_and_jump_insns (index,
2021 convert_modes
2022 (mode, imode,
2023 expand_normal (node->low),
2024 unsignedp),
2025 LT, NULL_RTX, mode, unsignedp,
2026 default_label,
2027 probability);
2029 else if (!low_bound && !high_bound)
2031 /* Widen LOW and HIGH to the same width as INDEX. */
2032 tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
2033 tree low = build1 (CONVERT_EXPR, type, node->low);
2034 tree high = build1 (CONVERT_EXPR, type, node->high);
2035 rtx low_rtx, new_index, new_bound;
2037 /* Instead of doing two branches, emit one unsigned branch for
2038 (index-low) > (high-low). */
2039 low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL);
2040 new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
2041 NULL_RTX, unsignedp,
2042 OPTAB_WIDEN);
2043 new_bound = expand_expr (fold_build2 (MINUS_EXPR, type,
2044 high, low),
2045 NULL_RTX, mode, EXPAND_NORMAL);
2047 probability = conditional_probability (
2048 default_prob,
2049 subtree_prob + default_prob);
2050 emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
2051 mode, 1, default_label, probability);
2054 emit_jump (label_rtx (node->code_label));