Daily bump.
[official-gcc.git] / gcc / stmt.c
blob45dc45fd049aed27d63ba8d47a00dd2858afafb3
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
346 /* Otherwise we can't assume anything about the nature of
347 the constraint except that it isn't purely registers.
348 Treat it like "g" and hope for the best. */
349 *allows_reg = true;
350 *allows_mem = true;
352 break;
355 return true;
358 /* Similar, but for input constraints. */
360 bool
361 parse_input_constraint (const char **constraint_p, int input_num,
362 int ninputs, int noutputs, int ninout,
363 const char * const * constraints,
364 bool *allows_mem, bool *allows_reg)
366 const char *constraint = *constraint_p;
367 const char *orig_constraint = constraint;
368 size_t c_len = strlen (constraint);
369 size_t j;
370 bool saw_match = false;
372 /* Assume the constraint doesn't allow the use of either
373 a register or memory. */
374 *allows_mem = false;
375 *allows_reg = false;
377 /* Make sure constraint has neither `=', `+', nor '&'. */
379 for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
380 switch (constraint[j])
382 case '+': case '=': case '&':
383 if (constraint == orig_constraint)
385 error ("input operand constraint contains %qc", constraint[j]);
386 return false;
388 break;
390 case '%':
391 if (constraint == orig_constraint
392 && input_num + 1 == ninputs - ninout)
394 error ("%<%%%> constraint used with last operand");
395 return false;
397 break;
399 case '<': case '>':
400 case '?': case '!': case '*': case '#':
401 case '$': case '^':
402 case 'E': case 'F': case 'G': case 'H':
403 case 's': case 'i': case 'n':
404 case 'I': case 'J': case 'K': case 'L': case 'M':
405 case 'N': case 'O': case 'P': case ',':
406 break;
408 /* Whether or not a numeric constraint allows a register is
409 decided by the matching constraint, and so there is no need
410 to do anything special with them. We must handle them in
411 the default case, so that we don't unnecessarily force
412 operands to memory. */
413 case '0': case '1': case '2': case '3': case '4':
414 case '5': case '6': case '7': case '8': case '9':
416 char *end;
417 unsigned long match;
419 saw_match = true;
421 match = strtoul (constraint + j, &end, 10);
422 if (match >= (unsigned long) noutputs)
424 error ("matching constraint references invalid operand number");
425 return false;
428 /* Try and find the real constraint for this dup. Only do this
429 if the matching constraint is the only alternative. */
430 if (*end == '\0'
431 && (j == 0 || (j == 1 && constraint[0] == '%')))
433 constraint = constraints[match];
434 *constraint_p = constraint;
435 c_len = strlen (constraint);
436 j = 0;
437 /* ??? At the end of the loop, we will skip the first part of
438 the matched constraint. This assumes not only that the
439 other constraint is an output constraint, but also that
440 the '=' or '+' come first. */
441 break;
443 else
444 j = end - constraint;
445 /* Anticipate increment at end of loop. */
446 j--;
448 /* Fall through. */
450 case 'g': case 'X':
451 *allows_reg = true;
452 *allows_mem = true;
453 break;
455 default:
456 if (! ISALPHA (constraint[j]))
458 error ("invalid punctuation %qc in constraint", constraint[j]);
459 return false;
461 enum constraint_num cn = lookup_constraint (constraint + j);
462 if (reg_class_for_constraint (cn) != NO_REGS
463 || insn_extra_address_constraint (cn))
464 *allows_reg = true;
465 else if (insn_extra_memory_constraint (cn))
466 *allows_mem = true;
467 else
469 /* Otherwise we can't assume anything about the nature of
470 the constraint except that it isn't purely registers.
471 Treat it like "g" and hope for the best. */
472 *allows_reg = true;
473 *allows_mem = true;
475 break;
478 if (saw_match && !*allows_reg)
479 warning (0, "matching constraint does not allow a register");
481 return true;
484 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
485 can be an asm-declared register. Called via walk_tree. */
487 static tree
488 decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED,
489 void *data)
491 tree decl = *declp;
492 const HARD_REG_SET *const regs = (const HARD_REG_SET *) data;
494 if (TREE_CODE (decl) == VAR_DECL)
496 if (DECL_HARD_REGISTER (decl)
497 && REG_P (DECL_RTL (decl))
498 && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
500 rtx reg = DECL_RTL (decl);
502 if (overlaps_hard_reg_set_p (*regs, GET_MODE (reg), REGNO (reg)))
503 return decl;
505 walk_subtrees = 0;
507 else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL)
508 walk_subtrees = 0;
509 return NULL_TREE;
512 /* If there is an overlap between *REGS and DECL, return the first overlap
513 found. */
514 tree
515 tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs)
517 return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL);
521 /* A subroutine of expand_asm_operands. Check that all operand names
522 are unique. Return true if so. We rely on the fact that these names
523 are identifiers, and so have been canonicalized by get_identifier,
524 so all we need are pointer comparisons. */
526 static bool
527 check_unique_operand_names (tree outputs, tree inputs, tree labels)
529 tree i, j, i_name = NULL_TREE;
531 for (i = outputs; i ; i = TREE_CHAIN (i))
533 i_name = TREE_PURPOSE (TREE_PURPOSE (i));
534 if (! i_name)
535 continue;
537 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
538 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
539 goto failure;
542 for (i = inputs; i ; i = TREE_CHAIN (i))
544 i_name = TREE_PURPOSE (TREE_PURPOSE (i));
545 if (! i_name)
546 continue;
548 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
549 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
550 goto failure;
551 for (j = outputs; j ; j = TREE_CHAIN (j))
552 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
553 goto failure;
556 for (i = labels; i ; i = TREE_CHAIN (i))
558 i_name = TREE_PURPOSE (i);
559 if (! i_name)
560 continue;
562 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
563 if (simple_cst_equal (i_name, TREE_PURPOSE (j)))
564 goto failure;
565 for (j = inputs; j ; j = TREE_CHAIN (j))
566 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
567 goto failure;
570 return true;
572 failure:
573 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name));
574 return false;
577 /* A subroutine of expand_asm_operands. Resolve the names of the operands
578 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
579 STRING and in the constraints to those numbers. */
581 tree
582 resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels)
584 char *buffer;
585 char *p;
586 const char *c;
587 tree t;
589 check_unique_operand_names (outputs, inputs, labels);
591 /* Substitute [<name>] in input constraint strings. There should be no
592 named operands in output constraints. */
593 for (t = inputs; t ; t = TREE_CHAIN (t))
595 c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
596 if (strchr (c, '[') != NULL)
598 p = buffer = xstrdup (c);
599 while ((p = strchr (p, '[')) != NULL)
600 p = resolve_operand_name_1 (p, outputs, inputs, NULL);
601 TREE_VALUE (TREE_PURPOSE (t))
602 = build_string (strlen (buffer), buffer);
603 free (buffer);
607 /* Now check for any needed substitutions in the template. */
608 c = TREE_STRING_POINTER (string);
609 while ((c = strchr (c, '%')) != NULL)
611 if (c[1] == '[')
612 break;
613 else if (ISALPHA (c[1]) && c[2] == '[')
614 break;
615 else
617 c += 1 + (c[1] == '%');
618 continue;
622 if (c)
624 /* OK, we need to make a copy so we can perform the substitutions.
625 Assume that we will not need extra space--we get to remove '['
626 and ']', which means we cannot have a problem until we have more
627 than 999 operands. */
628 buffer = xstrdup (TREE_STRING_POINTER (string));
629 p = buffer + (c - TREE_STRING_POINTER (string));
631 while ((p = strchr (p, '%')) != NULL)
633 if (p[1] == '[')
634 p += 1;
635 else if (ISALPHA (p[1]) && p[2] == '[')
636 p += 2;
637 else
639 p += 1 + (p[1] == '%');
640 continue;
643 p = resolve_operand_name_1 (p, outputs, inputs, labels);
646 string = build_string (strlen (buffer), buffer);
647 free (buffer);
650 return string;
653 /* A subroutine of resolve_operand_names. P points to the '[' for a
654 potential named operand of the form [<name>]. In place, replace
655 the name and brackets with a number. Return a pointer to the
656 balance of the string after substitution. */
658 static char *
659 resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels)
661 char *q;
662 int op;
663 tree t;
665 /* Collect the operand name. */
666 q = strchr (++p, ']');
667 if (!q)
669 error ("missing close brace for named operand");
670 return strchr (p, '\0');
672 *q = '\0';
674 /* Resolve the name to a number. */
675 for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
677 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
678 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
679 goto found;
681 for (t = inputs; t ; t = TREE_CHAIN (t), op++)
683 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
684 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
685 goto found;
687 for (t = labels; t ; t = TREE_CHAIN (t), op++)
689 tree name = TREE_PURPOSE (t);
690 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
691 goto found;
694 error ("undefined named operand %qs", identifier_to_locale (p));
695 op = 0;
697 found:
698 /* Replace the name with the number. Unfortunately, not all libraries
699 get the return value of sprintf correct, so search for the end of the
700 generated string by hand. */
701 sprintf (--p, "%d", op);
702 p = strchr (p, '\0');
704 /* Verify the no extra buffer space assumption. */
705 gcc_assert (p <= q);
707 /* Shift the rest of the buffer down to fill the gap. */
708 memmove (p, q + 1, strlen (q + 1) + 1);
710 return p;
714 /* Generate RTL to return directly from the current function.
715 (That is, we bypass any return value.) */
717 void
718 expand_naked_return (void)
720 rtx end_label;
722 clear_pending_stack_adjust ();
723 do_pending_stack_adjust ();
725 end_label = naked_return_label;
726 if (end_label == 0)
727 end_label = naked_return_label = gen_label_rtx ();
729 emit_jump (end_label);
732 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
733 is the probability of jumping to LABEL. */
734 static void
735 do_jump_if_equal (machine_mode mode, rtx op0, rtx op1, rtx label,
736 int unsignedp, int prob)
738 gcc_assert (prob <= REG_BR_PROB_BASE);
739 do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
740 NULL_RTX, NULL_RTX, label, prob);
743 /* Do the insertion of a case label into case_list. The labels are
744 fed to us in descending order from the sorted vector of case labels used
745 in the tree part of the middle end. So the list we construct is
746 sorted in ascending order.
748 LABEL is the case label to be inserted. LOW and HIGH are the bounds
749 against which the index is compared to jump to LABEL and PROB is the
750 estimated probability LABEL is reached from the switch statement. */
752 static struct case_node *
753 add_case_node (struct case_node *head, tree low, tree high,
754 tree label, int prob, alloc_pool case_node_pool)
756 struct case_node *r;
758 gcc_checking_assert (low);
759 gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high)));
761 /* Add this label to the chain. */
762 r = (struct case_node *) pool_alloc (case_node_pool);
763 r->low = low;
764 r->high = high;
765 r->code_label = label;
766 r->parent = r->left = NULL;
767 r->prob = prob;
768 r->subtree_prob = prob;
769 r->right = head;
770 return r;
773 /* Dump ROOT, a list or tree of case nodes, to file. */
775 static void
776 dump_case_nodes (FILE *f, struct case_node *root,
777 int indent_step, int indent_level)
779 if (root == 0)
780 return;
781 indent_level++;
783 dump_case_nodes (f, root->left, indent_step, indent_level);
785 fputs (";; ", f);
786 fprintf (f, "%*s", indent_step * indent_level, "");
787 print_dec (root->low, f, TYPE_SIGN (TREE_TYPE (root->low)));
788 if (!tree_int_cst_equal (root->low, root->high))
790 fprintf (f, " ... ");
791 print_dec (root->high, f, TYPE_SIGN (TREE_TYPE (root->high)));
793 fputs ("\n", f);
795 dump_case_nodes (f, root->right, indent_step, indent_level);
798 #ifndef HAVE_casesi
799 #define HAVE_casesi 0
800 #endif
802 #ifndef HAVE_tablejump
803 #define HAVE_tablejump 0
804 #endif
806 /* Return the smallest number of different values for which it is best to use a
807 jump-table instead of a tree of conditional branches. */
809 static unsigned int
810 case_values_threshold (void)
812 unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
814 if (threshold == 0)
815 threshold = targetm.case_values_threshold ();
817 return threshold;
820 /* Return true if a switch should be expanded as a decision tree.
821 RANGE is the difference between highest and lowest case.
822 UNIQ is number of unique case node targets, not counting the default case.
823 COUNT is the number of comparisons needed, not counting the default case. */
825 static bool
826 expand_switch_as_decision_tree_p (tree range,
827 unsigned int uniq ATTRIBUTE_UNUSED,
828 unsigned int count)
830 int max_ratio;
832 /* If neither casesi or tablejump is available, or flag_jump_tables
833 over-ruled us, we really have no choice. */
834 if (!HAVE_casesi && !HAVE_tablejump)
835 return true;
836 if (!flag_jump_tables)
837 return true;
838 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
839 if (flag_pic)
840 return true;
841 #endif
843 /* If the switch is relatively small such that the cost of one
844 indirect jump on the target are higher than the cost of a
845 decision tree, go with the decision tree.
847 If range of values is much bigger than number of values,
848 or if it is too large to represent in a HOST_WIDE_INT,
849 make a sequence of conditional branches instead of a dispatch.
851 The definition of "much bigger" depends on whether we are
852 optimizing for size or for speed. If the former, the maximum
853 ratio range/count = 3, because this was found to be the optimal
854 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
855 10 is much older, and was probably selected after an extensive
856 benchmarking investigation on numerous platforms. Or maybe it
857 just made sense to someone at some point in the history of GCC,
858 who knows... */
859 max_ratio = optimize_insn_for_size_p () ? 3 : 10;
860 if (count < case_values_threshold ()
861 || ! tree_fits_uhwi_p (range)
862 || compare_tree_int (range, max_ratio * count) > 0)
863 return true;
865 return false;
868 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
869 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
870 DEFAULT_PROB is the estimated probability that it jumps to
871 DEFAULT_LABEL.
873 We generate a binary decision tree to select the appropriate target
874 code. This is done as follows:
876 If the index is a short or char that we do not have
877 an insn to handle comparisons directly, convert it to
878 a full integer now, rather than letting each comparison
879 generate the conversion.
881 Load the index into a register.
883 The list of cases is rearranged into a binary tree,
884 nearly optimal assuming equal probability for each case.
886 The tree is transformed into RTL, eliminating redundant
887 test conditions at the same time.
889 If program flow could reach the end of the decision tree
890 an unconditional jump to the default code is emitted.
892 The above process is unaware of the CFG. The caller has to fix up
893 the CFG itself. This is done in cfgexpand.c. */
895 static void
896 emit_case_decision_tree (tree index_expr, tree index_type,
897 struct case_node *case_list, rtx default_label,
898 int default_prob)
900 rtx index = expand_normal (index_expr);
902 if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
903 && ! have_insn_for (COMPARE, GET_MODE (index)))
905 int unsignedp = TYPE_UNSIGNED (index_type);
906 machine_mode wider_mode;
907 for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
908 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
909 if (have_insn_for (COMPARE, wider_mode))
911 index = convert_to_mode (wider_mode, index, unsignedp);
912 break;
916 do_pending_stack_adjust ();
918 if (MEM_P (index))
920 index = copy_to_reg (index);
921 if (TREE_CODE (index_expr) == SSA_NAME)
922 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr), index);
925 balance_case_nodes (&case_list, NULL);
927 if (dump_file && (dump_flags & TDF_DETAILS))
929 int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
930 fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
931 dump_case_nodes (dump_file, case_list, indent_step, 0);
934 emit_case_nodes (index, case_list, default_label, default_prob, index_type);
935 if (default_label)
936 emit_jump (default_label);
939 /* Return the sum of probabilities of outgoing edges of basic block BB. */
941 static int
942 get_outgoing_edge_probs (basic_block bb)
944 edge e;
945 edge_iterator ei;
946 int prob_sum = 0;
947 if (!bb)
948 return 0;
949 FOR_EACH_EDGE (e, ei, bb->succs)
950 prob_sum += e->probability;
951 return prob_sum;
954 /* Computes the conditional probability of jumping to a target if the branch
955 instruction is executed.
956 TARGET_PROB is the estimated probability of jumping to a target relative
957 to some basic block BB.
958 BASE_PROB is the probability of reaching the branch instruction relative
959 to the same basic block BB. */
961 static inline int
962 conditional_probability (int target_prob, int base_prob)
964 if (base_prob > 0)
966 gcc_assert (target_prob >= 0);
967 gcc_assert (target_prob <= base_prob);
968 return GCOV_COMPUTE_SCALE (target_prob, base_prob);
970 return -1;
973 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
974 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
975 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
976 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
978 First, a jump insn is emitted. First we try "casesi". If that
979 fails, try "tablejump". A target *must* have one of them (or both).
981 Then, a table with the target labels is emitted.
983 The process is unaware of the CFG. The caller has to fix up
984 the CFG itself. This is done in cfgexpand.c. */
986 static void
987 emit_case_dispatch_table (tree index_expr, tree index_type,
988 struct case_node *case_list, rtx default_label,
989 tree minval, tree maxval, tree range,
990 basic_block stmt_bb)
992 int i, ncases;
993 struct case_node *n;
994 rtx *labelvec;
995 rtx fallback_label = label_rtx (case_list->code_label);
996 rtx_code_label *table_label = gen_label_rtx ();
997 bool has_gaps = false;
998 edge default_edge = stmt_bb ? EDGE_SUCC (stmt_bb, 0) : NULL;
999 int default_prob = default_edge ? default_edge->probability : 0;
1000 int base = get_outgoing_edge_probs (stmt_bb);
1001 bool try_with_tablejump = false;
1003 int new_default_prob = conditional_probability (default_prob,
1004 base);
1006 if (! try_casesi (index_type, index_expr, minval, range,
1007 table_label, default_label, fallback_label,
1008 new_default_prob))
1010 /* Index jumptables from zero for suitable values of minval to avoid
1011 a subtraction. For the rationale see:
1012 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
1013 if (optimize_insn_for_speed_p ()
1014 && compare_tree_int (minval, 0) > 0
1015 && compare_tree_int (minval, 3) < 0)
1017 minval = build_int_cst (index_type, 0);
1018 range = maxval;
1019 has_gaps = true;
1021 try_with_tablejump = true;
1024 /* Get table of labels to jump to, in order of case index. */
1026 ncases = tree_to_shwi (range) + 1;
1027 labelvec = XALLOCAVEC (rtx, ncases);
1028 memset (labelvec, 0, ncases * sizeof (rtx));
1030 for (n = case_list; n; n = n->right)
1032 /* Compute the low and high bounds relative to the minimum
1033 value since that should fit in a HOST_WIDE_INT while the
1034 actual values may not. */
1035 HOST_WIDE_INT i_low
1036 = tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
1037 n->low, minval));
1038 HOST_WIDE_INT i_high
1039 = tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
1040 n->high, minval));
1041 HOST_WIDE_INT i;
1043 for (i = i_low; i <= i_high; i ++)
1044 labelvec[i]
1045 = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
1048 /* Fill in the gaps with the default. We may have gaps at
1049 the beginning if we tried to avoid the minval subtraction,
1050 so substitute some label even if the default label was
1051 deemed unreachable. */
1052 if (!default_label)
1053 default_label = fallback_label;
1054 for (i = 0; i < ncases; i++)
1055 if (labelvec[i] == 0)
1057 has_gaps = true;
1058 labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
1061 if (has_gaps)
1063 /* There is at least one entry in the jump table that jumps
1064 to default label. The default label can either be reached
1065 through the indirect jump or the direct conditional jump
1066 before that. Split the probability of reaching the
1067 default label among these two jumps. */
1068 new_default_prob = conditional_probability (default_prob/2,
1069 base);
1070 default_prob /= 2;
1071 base -= default_prob;
1073 else
1075 base -= default_prob;
1076 default_prob = 0;
1079 if (default_edge)
1080 default_edge->probability = default_prob;
1082 /* We have altered the probability of the default edge. So the probabilities
1083 of all other edges need to be adjusted so that it sums up to
1084 REG_BR_PROB_BASE. */
1085 if (base)
1087 edge e;
1088 edge_iterator ei;
1089 FOR_EACH_EDGE (e, ei, stmt_bb->succs)
1090 e->probability = GCOV_COMPUTE_SCALE (e->probability, base);
1093 if (try_with_tablejump)
1095 bool ok = try_tablejump (index_type, index_expr, minval, range,
1096 table_label, default_label, new_default_prob);
1097 gcc_assert (ok);
1099 /* Output the table. */
1100 emit_label (table_label);
1102 if (CASE_VECTOR_PC_RELATIVE || flag_pic)
1103 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
1104 gen_rtx_LABEL_REF (Pmode,
1105 table_label),
1106 gen_rtvec_v (ncases, labelvec),
1107 const0_rtx, const0_rtx));
1108 else
1109 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
1110 gen_rtvec_v (ncases, labelvec)));
1112 /* Record no drop-through after the table. */
1113 emit_barrier ();
1116 /* Reset the aux field of all outgoing edges of basic block BB. */
1118 static inline void
1119 reset_out_edges_aux (basic_block bb)
1121 edge e;
1122 edge_iterator ei;
1123 FOR_EACH_EDGE (e, ei, bb->succs)
1124 e->aux = (void *)0;
1127 /* Compute the number of case labels that correspond to each outgoing edge of
1128 STMT. Record this information in the aux field of the edge. */
1130 static inline void
1131 compute_cases_per_edge (gswitch *stmt)
1133 basic_block bb = gimple_bb (stmt);
1134 reset_out_edges_aux (bb);
1135 int ncases = gimple_switch_num_labels (stmt);
1136 for (int i = ncases - 1; i >= 1; --i)
1138 tree elt = gimple_switch_label (stmt, i);
1139 tree lab = CASE_LABEL (elt);
1140 basic_block case_bb = label_to_block_fn (cfun, lab);
1141 edge case_edge = find_edge (bb, case_bb);
1142 case_edge->aux = (void *)((intptr_t)(case_edge->aux) + 1);
1146 /* Terminate a case (Pascal/Ada) or switch (C) statement
1147 in which ORIG_INDEX is the expression to be tested.
1148 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
1149 type as given in the source before any compiler conversions.
1150 Generate the code to test it and jump to the right place. */
1152 void
1153 expand_case (gswitch *stmt)
1155 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
1156 rtx default_label = NULL_RTX;
1157 unsigned int count, uniq;
1158 int i;
1159 int ncases = gimple_switch_num_labels (stmt);
1160 tree index_expr = gimple_switch_index (stmt);
1161 tree index_type = TREE_TYPE (index_expr);
1162 tree elt;
1163 basic_block bb = gimple_bb (stmt);
1165 /* A list of case labels; it is first built as a list and it may then
1166 be rearranged into a nearly balanced binary tree. */
1167 struct case_node *case_list = 0;
1169 /* A pool for case nodes. */
1170 alloc_pool case_node_pool;
1172 /* An ERROR_MARK occurs for various reasons including invalid data type.
1173 ??? Can this still happen, with GIMPLE and all? */
1174 if (index_type == error_mark_node)
1175 return;
1177 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
1178 expressions being INTEGER_CST. */
1179 gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
1181 case_node_pool = create_alloc_pool ("struct case_node pool",
1182 sizeof (struct case_node),
1183 100);
1185 do_pending_stack_adjust ();
1187 /* Find the default case target label. */
1188 default_label = label_rtx (CASE_LABEL (gimple_switch_default_label (stmt)));
1189 edge default_edge = EDGE_SUCC (bb, 0);
1190 int default_prob = default_edge->probability;
1192 /* Get upper and lower bounds of case values. */
1193 elt = gimple_switch_label (stmt, 1);
1194 minval = fold_convert (index_type, CASE_LOW (elt));
1195 elt = gimple_switch_label (stmt, ncases - 1);
1196 if (CASE_HIGH (elt))
1197 maxval = fold_convert (index_type, CASE_HIGH (elt));
1198 else
1199 maxval = fold_convert (index_type, CASE_LOW (elt));
1201 /* Compute span of values. */
1202 range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
1204 /* Listify the labels queue and gather some numbers to decide
1205 how to expand this switch(). */
1206 uniq = 0;
1207 count = 0;
1208 hash_set<tree> seen_labels;
1209 compute_cases_per_edge (stmt);
1211 for (i = ncases - 1; i >= 1; --i)
1213 elt = gimple_switch_label (stmt, i);
1214 tree low = CASE_LOW (elt);
1215 gcc_assert (low);
1216 tree high = CASE_HIGH (elt);
1217 gcc_assert (! high || tree_int_cst_lt (low, high));
1218 tree lab = CASE_LABEL (elt);
1220 /* Count the elements.
1221 A range counts double, since it requires two compares. */
1222 count++;
1223 if (high)
1224 count++;
1226 /* If we have not seen this label yet, then increase the
1227 number of unique case node targets seen. */
1228 if (!seen_labels.add (lab))
1229 uniq++;
1231 /* The bounds on the case range, LOW and HIGH, have to be converted
1232 to case's index type TYPE. Note that the original type of the
1233 case index in the source code is usually "lost" during
1234 gimplification due to type promotion, but the case labels retain the
1235 original type. Make sure to drop overflow flags. */
1236 low = fold_convert (index_type, low);
1237 if (TREE_OVERFLOW (low))
1238 low = wide_int_to_tree (index_type, low);
1240 /* The canonical from of a case label in GIMPLE is that a simple case
1241 has an empty CASE_HIGH. For the casesi and tablejump expanders,
1242 the back ends want simple cases to have high == low. */
1243 if (! high)
1244 high = low;
1245 high = fold_convert (index_type, high);
1246 if (TREE_OVERFLOW (high))
1247 high = wide_int_to_tree (index_type, high);
1249 basic_block case_bb = label_to_block_fn (cfun, lab);
1250 edge case_edge = find_edge (bb, case_bb);
1251 case_list = add_case_node (
1252 case_list, low, high, lab,
1253 case_edge->probability / (intptr_t)(case_edge->aux),
1254 case_node_pool);
1256 reset_out_edges_aux (bb);
1258 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
1259 destination, such as one with a default case only.
1260 It also removes cases that are out of range for the switch
1261 type, so we should never get a zero here. */
1262 gcc_assert (count > 0);
1264 rtx_insn *before_case = get_last_insn ();
1266 /* Decide how to expand this switch.
1267 The two options at this point are a dispatch table (casesi or
1268 tablejump) or a decision tree. */
1270 if (expand_switch_as_decision_tree_p (range, uniq, count))
1271 emit_case_decision_tree (index_expr, index_type,
1272 case_list, default_label,
1273 default_prob);
1274 else
1275 emit_case_dispatch_table (index_expr, index_type,
1276 case_list, default_label,
1277 minval, maxval, range, bb);
1279 reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
1281 free_temp_slots ();
1282 free_alloc_pool (case_node_pool);
1285 /* Expand the dispatch to a short decrement chain if there are few cases
1286 to dispatch to. Likewise if neither casesi nor tablejump is available,
1287 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
1288 tablejump. The index mode is always the mode of integer_type_node.
1289 Trap if no case matches the index.
1291 DISPATCH_INDEX is the index expression to switch on. It should be a
1292 memory or register operand.
1294 DISPATCH_TABLE is a set of case labels. The set should be sorted in
1295 ascending order, be contiguous, starting with value 0, and contain only
1296 single-valued case labels. */
1298 void
1299 expand_sjlj_dispatch_table (rtx dispatch_index,
1300 vec<tree> dispatch_table)
1302 tree index_type = integer_type_node;
1303 machine_mode index_mode = TYPE_MODE (index_type);
1305 int ncases = dispatch_table.length ();
1307 do_pending_stack_adjust ();
1308 rtx_insn *before_case = get_last_insn ();
1310 /* Expand as a decrement-chain if there are 5 or fewer dispatch
1311 labels. This covers more than 98% of the cases in libjava,
1312 and seems to be a reasonable compromise between the "old way"
1313 of expanding as a decision tree or dispatch table vs. the "new
1314 way" with decrement chain or dispatch table. */
1315 if (dispatch_table.length () <= 5
1316 || (!HAVE_casesi && !HAVE_tablejump)
1317 || !flag_jump_tables)
1319 /* Expand the dispatch as a decrement chain:
1321 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1325 if (index == 0) do_0; else index--;
1326 if (index == 0) do_1; else index--;
1328 if (index == 0) do_N; else index--;
1330 This is more efficient than a dispatch table on most machines.
1331 The last "index--" is redundant but the code is trivially dead
1332 and will be cleaned up by later passes. */
1333 rtx index = copy_to_mode_reg (index_mode, dispatch_index);
1334 rtx zero = CONST0_RTX (index_mode);
1335 for (int i = 0; i < ncases; i++)
1337 tree elt = dispatch_table[i];
1338 rtx lab = label_rtx (CASE_LABEL (elt));
1339 do_jump_if_equal (index_mode, index, zero, lab, 0, -1);
1340 force_expand_binop (index_mode, sub_optab,
1341 index, CONST1_RTX (index_mode),
1342 index, 0, OPTAB_DIRECT);
1345 else
1347 /* Similar to expand_case, but much simpler. */
1348 struct case_node *case_list = 0;
1349 alloc_pool case_node_pool = create_alloc_pool ("struct sjlj_case pool",
1350 sizeof (struct case_node),
1351 ncases);
1352 tree index_expr = make_tree (index_type, dispatch_index);
1353 tree minval = build_int_cst (index_type, 0);
1354 tree maxval = CASE_LOW (dispatch_table.last ());
1355 tree range = maxval;
1356 rtx_code_label *default_label = gen_label_rtx ();
1358 for (int i = ncases - 1; i >= 0; --i)
1360 tree elt = dispatch_table[i];
1361 tree low = CASE_LOW (elt);
1362 tree lab = CASE_LABEL (elt);
1363 case_list = add_case_node (case_list, low, low, lab, 0, case_node_pool);
1366 emit_case_dispatch_table (index_expr, index_type,
1367 case_list, default_label,
1368 minval, maxval, range,
1369 BLOCK_FOR_INSN (before_case));
1370 emit_label (default_label);
1371 free_alloc_pool (case_node_pool);
1374 /* Dispatching something not handled? Trap! */
1375 expand_builtin_trap ();
1377 reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
1379 free_temp_slots ();
1383 /* Take an ordered list of case nodes
1384 and transform them into a near optimal binary tree,
1385 on the assumption that any target code selection value is as
1386 likely as any other.
1388 The transformation is performed by splitting the ordered
1389 list into two equal sections plus a pivot. The parts are
1390 then attached to the pivot as left and right branches. Each
1391 branch is then transformed recursively. */
1393 static void
1394 balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
1396 case_node_ptr np;
1398 np = *head;
1399 if (np)
1401 int i = 0;
1402 int ranges = 0;
1403 case_node_ptr *npp;
1404 case_node_ptr left;
1406 /* Count the number of entries on branch. Also count the ranges. */
1408 while (np)
1410 if (!tree_int_cst_equal (np->low, np->high))
1411 ranges++;
1413 i++;
1414 np = np->right;
1417 if (i > 2)
1419 /* Split this list if it is long enough for that to help. */
1420 npp = head;
1421 left = *npp;
1423 /* If there are just three nodes, split at the middle one. */
1424 if (i == 3)
1425 npp = &(*npp)->right;
1426 else
1428 /* Find the place in the list that bisects the list's total cost,
1429 where ranges count as 2.
1430 Here I gets half the total cost. */
1431 i = (i + ranges + 1) / 2;
1432 while (1)
1434 /* Skip nodes while their cost does not reach that amount. */
1435 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
1436 i--;
1437 i--;
1438 if (i <= 0)
1439 break;
1440 npp = &(*npp)->right;
1443 *head = np = *npp;
1444 *npp = 0;
1445 np->parent = parent;
1446 np->left = left;
1448 /* Optimize each of the two split parts. */
1449 balance_case_nodes (&np->left, np);
1450 balance_case_nodes (&np->right, np);
1451 np->subtree_prob = np->prob;
1452 np->subtree_prob += np->left->subtree_prob;
1453 np->subtree_prob += np->right->subtree_prob;
1455 else
1457 /* Else leave this branch as one level,
1458 but fill in `parent' fields. */
1459 np = *head;
1460 np->parent = parent;
1461 np->subtree_prob = np->prob;
1462 for (; np->right; np = np->right)
1464 np->right->parent = np;
1465 (*head)->subtree_prob += np->right->subtree_prob;
1471 /* Search the parent sections of the case node tree
1472 to see if a test for the lower bound of NODE would be redundant.
1473 INDEX_TYPE is the type of the index expression.
1475 The instructions to generate the case decision tree are
1476 output in the same order as nodes are processed so it is
1477 known that if a parent node checks the range of the current
1478 node minus one that the current node is bounded at its lower
1479 span. Thus the test would be redundant. */
1481 static int
1482 node_has_low_bound (case_node_ptr node, tree index_type)
1484 tree low_minus_one;
1485 case_node_ptr pnode;
1487 /* If the lower bound of this node is the lowest value in the index type,
1488 we need not test it. */
1490 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
1491 return 1;
1493 /* If this node has a left branch, the value at the left must be less
1494 than that at this node, so it cannot be bounded at the bottom and
1495 we need not bother testing any further. */
1497 if (node->left)
1498 return 0;
1500 low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low),
1501 node->low,
1502 build_int_cst (TREE_TYPE (node->low), 1));
1504 /* If the subtraction above overflowed, we can't verify anything.
1505 Otherwise, look for a parent that tests our value - 1. */
1507 if (! tree_int_cst_lt (low_minus_one, node->low))
1508 return 0;
1510 for (pnode = node->parent; pnode; pnode = pnode->parent)
1511 if (tree_int_cst_equal (low_minus_one, pnode->high))
1512 return 1;
1514 return 0;
1517 /* Search the parent sections of the case node tree
1518 to see if a test for the upper bound of NODE would be redundant.
1519 INDEX_TYPE is the type of the index expression.
1521 The instructions to generate the case decision tree are
1522 output in the same order as nodes are processed so it is
1523 known that if a parent node checks the range of the current
1524 node plus one that the current node is bounded at its upper
1525 span. Thus the test would be redundant. */
1527 static int
1528 node_has_high_bound (case_node_ptr node, tree index_type)
1530 tree high_plus_one;
1531 case_node_ptr pnode;
1533 /* If there is no upper bound, obviously no test is needed. */
1535 if (TYPE_MAX_VALUE (index_type) == NULL)
1536 return 1;
1538 /* If the upper bound of this node is the highest value in the type
1539 of the index expression, we need not test against it. */
1541 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
1542 return 1;
1544 /* If this node has a right branch, the value at the right must be greater
1545 than that at this node, so it cannot be bounded at the top and
1546 we need not bother testing any further. */
1548 if (node->right)
1549 return 0;
1551 high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high),
1552 node->high,
1553 build_int_cst (TREE_TYPE (node->high), 1));
1555 /* If the addition above overflowed, we can't verify anything.
1556 Otherwise, look for a parent that tests our value + 1. */
1558 if (! tree_int_cst_lt (node->high, high_plus_one))
1559 return 0;
1561 for (pnode = node->parent; pnode; pnode = pnode->parent)
1562 if (tree_int_cst_equal (high_plus_one, pnode->low))
1563 return 1;
1565 return 0;
1568 /* Search the parent sections of the
1569 case node tree to see if both tests for the upper and lower
1570 bounds of NODE would be redundant. */
1572 static int
1573 node_is_bounded (case_node_ptr node, tree index_type)
1575 return (node_has_low_bound (node, index_type)
1576 && node_has_high_bound (node, index_type));
1580 /* Emit step-by-step code to select a case for the value of INDEX.
1581 The thus generated decision tree follows the form of the
1582 case-node binary tree NODE, whose nodes represent test conditions.
1583 INDEX_TYPE is the type of the index of the switch.
1585 Care is taken to prune redundant tests from the decision tree
1586 by detecting any boundary conditions already checked by
1587 emitted rtx. (See node_has_high_bound, node_has_low_bound
1588 and node_is_bounded, above.)
1590 Where the test conditions can be shown to be redundant we emit
1591 an unconditional jump to the target code. As a further
1592 optimization, the subordinates of a tree node are examined to
1593 check for bounded nodes. In this case conditional and/or
1594 unconditional jumps as a result of the boundary check for the
1595 current node are arranged to target the subordinates associated
1596 code for out of bound conditions on the current node.
1598 We can assume that when control reaches the code generated here,
1599 the index value has already been compared with the parents
1600 of this node, and determined to be on the same side of each parent
1601 as this node is. Thus, if this node tests for the value 51,
1602 and a parent tested for 52, we don't need to consider
1603 the possibility of a value greater than 51. If another parent
1604 tests for the value 50, then this node need not test anything. */
1606 static void
1607 emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
1608 int default_prob, tree index_type)
1610 /* If INDEX has an unsigned type, we must make unsigned branches. */
1611 int unsignedp = TYPE_UNSIGNED (index_type);
1612 int probability;
1613 int prob = node->prob, subtree_prob = node->subtree_prob;
1614 machine_mode mode = GET_MODE (index);
1615 machine_mode imode = TYPE_MODE (index_type);
1617 /* Handle indices detected as constant during RTL expansion. */
1618 if (mode == VOIDmode)
1619 mode = imode;
1621 /* See if our parents have already tested everything for us.
1622 If they have, emit an unconditional jump for this node. */
1623 if (node_is_bounded (node, index_type))
1624 emit_jump (label_rtx (node->code_label));
1626 else if (tree_int_cst_equal (node->low, node->high))
1628 probability = conditional_probability (prob, subtree_prob + default_prob);
1629 /* Node is single valued. First see if the index expression matches
1630 this node and then check our children, if any. */
1631 do_jump_if_equal (mode, index,
1632 convert_modes (mode, imode,
1633 expand_normal (node->low),
1634 unsignedp),
1635 label_rtx (node->code_label), unsignedp, probability);
1636 /* Since this case is taken at this point, reduce its weight from
1637 subtree_weight. */
1638 subtree_prob -= prob;
1639 if (node->right != 0 && node->left != 0)
1641 /* This node has children on both sides.
1642 Dispatch to one side or the other
1643 by comparing the index value with this node's value.
1644 If one subtree is bounded, check that one first,
1645 so we can avoid real branches in the tree. */
1647 if (node_is_bounded (node->right, index_type))
1649 probability = conditional_probability (
1650 node->right->prob,
1651 subtree_prob + default_prob);
1652 emit_cmp_and_jump_insns (index,
1653 convert_modes
1654 (mode, imode,
1655 expand_normal (node->high),
1656 unsignedp),
1657 GT, NULL_RTX, mode, unsignedp,
1658 label_rtx (node->right->code_label),
1659 probability);
1660 emit_case_nodes (index, node->left, default_label, default_prob,
1661 index_type);
1664 else if (node_is_bounded (node->left, index_type))
1666 probability = conditional_probability (
1667 node->left->prob,
1668 subtree_prob + default_prob);
1669 emit_cmp_and_jump_insns (index,
1670 convert_modes
1671 (mode, imode,
1672 expand_normal (node->high),
1673 unsignedp),
1674 LT, NULL_RTX, mode, unsignedp,
1675 label_rtx (node->left->code_label),
1676 probability);
1677 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1680 /* If both children are single-valued cases with no
1681 children, finish up all the work. This way, we can save
1682 one ordered comparison. */
1683 else if (tree_int_cst_equal (node->right->low, node->right->high)
1684 && node->right->left == 0
1685 && node->right->right == 0
1686 && tree_int_cst_equal (node->left->low, node->left->high)
1687 && node->left->left == 0
1688 && node->left->right == 0)
1690 /* Neither node is bounded. First distinguish the two sides;
1691 then emit the code for one side at a time. */
1693 /* See if the value matches what the right hand side
1694 wants. */
1695 probability = conditional_probability (
1696 node->right->prob,
1697 subtree_prob + default_prob);
1698 do_jump_if_equal (mode, index,
1699 convert_modes (mode, imode,
1700 expand_normal (node->right->low),
1701 unsignedp),
1702 label_rtx (node->right->code_label),
1703 unsignedp, probability);
1705 /* See if the value matches what the left hand side
1706 wants. */
1707 probability = conditional_probability (
1708 node->left->prob,
1709 subtree_prob + default_prob);
1710 do_jump_if_equal (mode, index,
1711 convert_modes (mode, imode,
1712 expand_normal (node->left->low),
1713 unsignedp),
1714 label_rtx (node->left->code_label),
1715 unsignedp, probability);
1718 else
1720 /* Neither node is bounded. First distinguish the two sides;
1721 then emit the code for one side at a time. */
1723 tree test_label
1724 = build_decl (curr_insn_location (),
1725 LABEL_DECL, NULL_TREE, void_type_node);
1727 /* The default label could be reached either through the right
1728 subtree or the left subtree. Divide the probability
1729 equally. */
1730 probability = conditional_probability (
1731 node->right->subtree_prob + default_prob/2,
1732 subtree_prob + default_prob);
1733 /* See if the value is on the right. */
1734 emit_cmp_and_jump_insns (index,
1735 convert_modes
1736 (mode, imode,
1737 expand_normal (node->high),
1738 unsignedp),
1739 GT, NULL_RTX, mode, unsignedp,
1740 label_rtx (test_label),
1741 probability);
1742 default_prob /= 2;
1744 /* Value must be on the left.
1745 Handle the left-hand subtree. */
1746 emit_case_nodes (index, node->left, default_label, default_prob, index_type);
1747 /* If left-hand subtree does nothing,
1748 go to default. */
1749 if (default_label)
1750 emit_jump (default_label);
1752 /* Code branches here for the right-hand subtree. */
1753 expand_label (test_label);
1754 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1758 else if (node->right != 0 && node->left == 0)
1760 /* Here we have a right child but no left so we issue a conditional
1761 branch to default and process the right child.
1763 Omit the conditional branch to default if the right child
1764 does not have any children and is single valued; it would
1765 cost too much space to save so little time. */
1767 if (node->right->right || node->right->left
1768 || !tree_int_cst_equal (node->right->low, node->right->high))
1770 if (!node_has_low_bound (node, index_type))
1772 probability = conditional_probability (
1773 default_prob/2,
1774 subtree_prob + default_prob);
1775 emit_cmp_and_jump_insns (index,
1776 convert_modes
1777 (mode, imode,
1778 expand_normal (node->high),
1779 unsignedp),
1780 LT, NULL_RTX, mode, unsignedp,
1781 default_label,
1782 probability);
1783 default_prob /= 2;
1786 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1788 else
1790 probability = conditional_probability (
1791 node->right->subtree_prob,
1792 subtree_prob + default_prob);
1793 /* We cannot process node->right normally
1794 since we haven't ruled out the numbers less than
1795 this node's value. So handle node->right explicitly. */
1796 do_jump_if_equal (mode, index,
1797 convert_modes
1798 (mode, imode,
1799 expand_normal (node->right->low),
1800 unsignedp),
1801 label_rtx (node->right->code_label), unsignedp, probability);
1805 else if (node->right == 0 && node->left != 0)
1807 /* Just one subtree, on the left. */
1808 if (node->left->left || node->left->right
1809 || !tree_int_cst_equal (node->left->low, node->left->high))
1811 if (!node_has_high_bound (node, index_type))
1813 probability = conditional_probability (
1814 default_prob/2,
1815 subtree_prob + default_prob);
1816 emit_cmp_and_jump_insns (index,
1817 convert_modes
1818 (mode, imode,
1819 expand_normal (node->high),
1820 unsignedp),
1821 GT, NULL_RTX, mode, unsignedp,
1822 default_label,
1823 probability);
1824 default_prob /= 2;
1827 emit_case_nodes (index, node->left, default_label,
1828 default_prob, index_type);
1830 else
1832 probability = conditional_probability (
1833 node->left->subtree_prob,
1834 subtree_prob + default_prob);
1835 /* We cannot process node->left normally
1836 since we haven't ruled out the numbers less than
1837 this node's value. So handle node->left explicitly. */
1838 do_jump_if_equal (mode, index,
1839 convert_modes
1840 (mode, imode,
1841 expand_normal (node->left->low),
1842 unsignedp),
1843 label_rtx (node->left->code_label), unsignedp, probability);
1847 else
1849 /* Node is a range. These cases are very similar to those for a single
1850 value, except that we do not start by testing whether this node
1851 is the one to branch to. */
1853 if (node->right != 0 && node->left != 0)
1855 /* Node has subtrees on both sides.
1856 If the right-hand subtree is bounded,
1857 test for it first, since we can go straight there.
1858 Otherwise, we need to make a branch in the control structure,
1859 then handle the two subtrees. */
1860 tree test_label = 0;
1862 if (node_is_bounded (node->right, index_type))
1864 /* Right hand node is fully bounded so we can eliminate any
1865 testing and branch directly to the target code. */
1866 probability = conditional_probability (
1867 node->right->subtree_prob,
1868 subtree_prob + default_prob);
1869 emit_cmp_and_jump_insns (index,
1870 convert_modes
1871 (mode, imode,
1872 expand_normal (node->high),
1873 unsignedp),
1874 GT, NULL_RTX, mode, unsignedp,
1875 label_rtx (node->right->code_label),
1876 probability);
1878 else
1880 /* Right hand node requires testing.
1881 Branch to a label where we will handle it later. */
1883 test_label = build_decl (curr_insn_location (),
1884 LABEL_DECL, NULL_TREE, void_type_node);
1885 probability = conditional_probability (
1886 node->right->subtree_prob + default_prob/2,
1887 subtree_prob + default_prob);
1888 emit_cmp_and_jump_insns (index,
1889 convert_modes
1890 (mode, imode,
1891 expand_normal (node->high),
1892 unsignedp),
1893 GT, NULL_RTX, mode, unsignedp,
1894 label_rtx (test_label),
1895 probability);
1896 default_prob /= 2;
1899 /* Value belongs to this node or to the left-hand subtree. */
1901 probability = conditional_probability (
1902 prob,
1903 subtree_prob + default_prob);
1904 emit_cmp_and_jump_insns (index,
1905 convert_modes
1906 (mode, imode,
1907 expand_normal (node->low),
1908 unsignedp),
1909 GE, NULL_RTX, mode, unsignedp,
1910 label_rtx (node->code_label),
1911 probability);
1913 /* Handle the left-hand subtree. */
1914 emit_case_nodes (index, node->left, default_label, default_prob, index_type);
1916 /* If right node had to be handled later, do that now. */
1918 if (test_label)
1920 /* If the left-hand subtree fell through,
1921 don't let it fall into the right-hand subtree. */
1922 if (default_label)
1923 emit_jump (default_label);
1925 expand_label (test_label);
1926 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1930 else if (node->right != 0 && node->left == 0)
1932 /* Deal with values to the left of this node,
1933 if they are possible. */
1934 if (!node_has_low_bound (node, index_type))
1936 probability = conditional_probability (
1937 default_prob/2,
1938 subtree_prob + default_prob);
1939 emit_cmp_and_jump_insns (index,
1940 convert_modes
1941 (mode, imode,
1942 expand_normal (node->low),
1943 unsignedp),
1944 LT, NULL_RTX, mode, unsignedp,
1945 default_label,
1946 probability);
1947 default_prob /= 2;
1950 /* Value belongs to this node or to the right-hand subtree. */
1952 probability = conditional_probability (
1953 prob,
1954 subtree_prob + default_prob);
1955 emit_cmp_and_jump_insns (index,
1956 convert_modes
1957 (mode, imode,
1958 expand_normal (node->high),
1959 unsignedp),
1960 LE, NULL_RTX, mode, unsignedp,
1961 label_rtx (node->code_label),
1962 probability);
1964 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1967 else if (node->right == 0 && node->left != 0)
1969 /* Deal with values to the right of this node,
1970 if they are possible. */
1971 if (!node_has_high_bound (node, index_type))
1973 probability = conditional_probability (
1974 default_prob/2,
1975 subtree_prob + default_prob);
1976 emit_cmp_and_jump_insns (index,
1977 convert_modes
1978 (mode, imode,
1979 expand_normal (node->high),
1980 unsignedp),
1981 GT, NULL_RTX, mode, unsignedp,
1982 default_label,
1983 probability);
1984 default_prob /= 2;
1987 /* Value belongs to this node or to the left-hand subtree. */
1989 probability = conditional_probability (
1990 prob,
1991 subtree_prob + default_prob);
1992 emit_cmp_and_jump_insns (index,
1993 convert_modes
1994 (mode, imode,
1995 expand_normal (node->low),
1996 unsignedp),
1997 GE, NULL_RTX, mode, unsignedp,
1998 label_rtx (node->code_label),
1999 probability);
2001 emit_case_nodes (index, node->left, default_label, default_prob, index_type);
2004 else
2006 /* Node has no children so we check low and high bounds to remove
2007 redundant tests. Only one of the bounds can exist,
2008 since otherwise this node is bounded--a case tested already. */
2009 int high_bound = node_has_high_bound (node, index_type);
2010 int low_bound = node_has_low_bound (node, index_type);
2012 if (!high_bound && low_bound)
2014 probability = conditional_probability (
2015 default_prob,
2016 subtree_prob + default_prob);
2017 emit_cmp_and_jump_insns (index,
2018 convert_modes
2019 (mode, imode,
2020 expand_normal (node->high),
2021 unsignedp),
2022 GT, NULL_RTX, mode, unsignedp,
2023 default_label,
2024 probability);
2027 else if (!low_bound && high_bound)
2029 probability = conditional_probability (
2030 default_prob,
2031 subtree_prob + default_prob);
2032 emit_cmp_and_jump_insns (index,
2033 convert_modes
2034 (mode, imode,
2035 expand_normal (node->low),
2036 unsignedp),
2037 LT, NULL_RTX, mode, unsignedp,
2038 default_label,
2039 probability);
2041 else if (!low_bound && !high_bound)
2043 /* Widen LOW and HIGH to the same width as INDEX. */
2044 tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
2045 tree low = build1 (CONVERT_EXPR, type, node->low);
2046 tree high = build1 (CONVERT_EXPR, type, node->high);
2047 rtx low_rtx, new_index, new_bound;
2049 /* Instead of doing two branches, emit one unsigned branch for
2050 (index-low) > (high-low). */
2051 low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL);
2052 new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
2053 NULL_RTX, unsignedp,
2054 OPTAB_WIDEN);
2055 new_bound = expand_expr (fold_build2 (MINUS_EXPR, type,
2056 high, low),
2057 NULL_RTX, mode, EXPAND_NORMAL);
2059 probability = conditional_probability (
2060 default_prob,
2061 subtree_prob + default_prob);
2062 emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
2063 mode, 1, default_label, probability);
2066 emit_jump (label_rtx (node->code_label));