Daily bump.
[official-gcc.git] / gcc / stmt.c
blob6d4eed9613beb8353e535d7905fcbf8186249fe1
1 /* Expands front end tree to back end RTL for GCC
2 Copyright (C) 1987-2014 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 "tree.h"
33 #include "varasm.h"
34 #include "stor-layout.h"
35 #include "tm_p.h"
36 #include "flags.h"
37 #include "except.h"
38 #include "function.h"
39 #include "insn-config.h"
40 #include "expr.h"
41 #include "libfuncs.h"
42 #include "recog.h"
43 #include "machmode.h"
44 #include "diagnostic-core.h"
45 #include "output.h"
46 #include "langhooks.h"
47 #include "predict.h"
48 #include "optabs.h"
49 #include "target.h"
50 #include "hash-set.h"
51 #include "basic-block.h"
52 #include "tree-ssa-alias.h"
53 #include "internal-fn.h"
54 #include "gimple-expr.h"
55 #include "is-a.h"
56 #include "gimple.h"
57 #include "regs.h"
58 #include "alloc-pool.h"
59 #include "pretty-print.h"
60 #include "params.h"
61 #include "dumpfile.h"
62 #include "builtins.h"
65 /* Functions and data structures for expanding case statements. */
67 /* Case label structure, used to hold info on labels within case
68 statements. We handle "range" labels; for a single-value label
69 as in C, the high and low limits are the same.
71 We start with a vector of case nodes sorted in ascending order, and
72 the default label as the last element in the vector. Before expanding
73 to RTL, we transform this vector into a list linked via the RIGHT
74 fields in the case_node struct. Nodes with higher case values are
75 later in the list.
77 Switch statements can be output in three forms. A branch table is
78 used if there are more than a few labels and the labels are dense
79 within the range between the smallest and largest case value. If a
80 branch table is used, no further manipulations are done with the case
81 node chain.
83 The alternative to the use of a branch table is to generate a series
84 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
85 and PARENT fields to hold a binary tree. Initially the tree is
86 totally unbalanced, with everything on the right. We balance the tree
87 with nodes on the left having lower case values than the parent
88 and nodes on the right having higher values. We then output the tree
89 in order.
91 For very small, suitable switch statements, we can generate a series
92 of simple bit test and branches instead. */
94 struct case_node
96 struct case_node *left; /* Left son in binary tree */
97 struct case_node *right; /* Right son in binary tree; also node chain */
98 struct case_node *parent; /* Parent of node in binary tree */
99 tree low; /* Lowest index value for this label */
100 tree high; /* Highest index value for this label */
101 tree code_label; /* Label to jump to when node matches */
102 int prob; /* Probability of taking this case. */
103 /* Probability of reaching subtree rooted at this node */
104 int subtree_prob;
107 typedef struct case_node case_node;
108 typedef struct case_node *case_node_ptr;
110 extern basic_block label_to_block_fn (struct function *, tree);
112 static bool check_unique_operand_names (tree, tree, tree);
113 static char *resolve_operand_name_1 (char *, tree, tree, tree);
114 static void balance_case_nodes (case_node_ptr *, case_node_ptr);
115 static int node_has_low_bound (case_node_ptr, tree);
116 static int node_has_high_bound (case_node_ptr, tree);
117 static int node_is_bounded (case_node_ptr, tree);
118 static void emit_case_nodes (rtx, case_node_ptr, rtx, int, tree);
120 /* Return the rtx-label that corresponds to a LABEL_DECL,
121 creating it if necessary. */
124 label_rtx (tree label)
126 gcc_assert (TREE_CODE (label) == LABEL_DECL);
128 if (!DECL_RTL_SET_P (label))
130 rtx_code_label *r = gen_label_rtx ();
131 SET_DECL_RTL (label, r);
132 if (FORCED_LABEL (label) || DECL_NONLOCAL (label))
133 LABEL_PRESERVE_P (r) = 1;
136 return DECL_RTL (label);
139 /* As above, but also put it on the forced-reference list of the
140 function that contains it. */
142 force_label_rtx (tree label)
144 rtx_insn *ref = as_a <rtx_insn *> (label_rtx (label));
145 tree function = decl_function_context (label);
147 gcc_assert (function);
149 forced_labels = gen_rtx_INSN_LIST (VOIDmode, ref, forced_labels);
150 return ref;
153 /* Add an unconditional jump to LABEL as the next sequential instruction. */
155 void
156 emit_jump (rtx label)
158 do_pending_stack_adjust ();
159 emit_jump_insn (gen_jump (label));
160 emit_barrier ();
163 /* Handle goto statements and the labels that they can go to. */
165 /* Specify the location in the RTL code of a label LABEL,
166 which is a LABEL_DECL tree node.
168 This is used for the kind of label that the user can jump to with a
169 goto statement, and for alternatives of a switch or case statement.
170 RTL labels generated for loops and conditionals don't go through here;
171 they are generated directly at the RTL level, by other functions below.
173 Note that this has nothing to do with defining label *names*.
174 Languages vary in how they do that and what that even means. */
176 void
177 expand_label (tree label)
179 rtx_insn *label_r = as_a <rtx_insn *> (label_rtx (label));
181 do_pending_stack_adjust ();
182 emit_label (label_r);
183 if (DECL_NAME (label))
184 LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label));
186 if (DECL_NONLOCAL (label))
188 expand_builtin_setjmp_receiver (NULL);
189 nonlocal_goto_handler_labels
190 = gen_rtx_INSN_LIST (VOIDmode, label_r,
191 nonlocal_goto_handler_labels);
194 if (FORCED_LABEL (label))
195 forced_labels = gen_rtx_INSN_LIST (VOIDmode, label_r, forced_labels);
197 if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
198 maybe_set_first_label_num (label_r);
201 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
202 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
203 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
204 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
205 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
206 constraint allows the use of a register operand. And, *IS_INOUT
207 will be true if the operand is read-write, i.e., if it is used as
208 an input as well as an output. If *CONSTRAINT_P is not in
209 canonical form, it will be made canonical. (Note that `+' will be
210 replaced with `=' as part of this process.)
212 Returns TRUE if all went well; FALSE if an error occurred. */
214 bool
215 parse_output_constraint (const char **constraint_p, int operand_num,
216 int ninputs, int noutputs, bool *allows_mem,
217 bool *allows_reg, bool *is_inout)
219 const char *constraint = *constraint_p;
220 const char *p;
222 /* Assume the constraint doesn't allow the use of either a register
223 or memory. */
224 *allows_mem = false;
225 *allows_reg = false;
227 /* Allow the `=' or `+' to not be at the beginning of the string,
228 since it wasn't explicitly documented that way, and there is a
229 large body of code that puts it last. Swap the character to
230 the front, so as not to uglify any place else. */
231 p = strchr (constraint, '=');
232 if (!p)
233 p = strchr (constraint, '+');
235 /* If the string doesn't contain an `=', issue an error
236 message. */
237 if (!p)
239 error ("output operand constraint lacks %<=%>");
240 return false;
243 /* If the constraint begins with `+', then the operand is both read
244 from and written to. */
245 *is_inout = (*p == '+');
247 /* Canonicalize the output constraint so that it begins with `='. */
248 if (p != constraint || *is_inout)
250 char *buf;
251 size_t c_len = strlen (constraint);
253 if (p != constraint)
254 warning (0, "output constraint %qc for operand %d "
255 "is not at the beginning",
256 *p, operand_num);
258 /* Make a copy of the constraint. */
259 buf = XALLOCAVEC (char, c_len + 1);
260 strcpy (buf, constraint);
261 /* Swap the first character and the `=' or `+'. */
262 buf[p - constraint] = buf[0];
263 /* Make sure the first character is an `='. (Until we do this,
264 it might be a `+'.) */
265 buf[0] = '=';
266 /* Replace the constraint with the canonicalized string. */
267 *constraint_p = ggc_alloc_string (buf, c_len);
268 constraint = *constraint_p;
271 /* Loop through the constraint string. */
272 for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p))
273 switch (*p)
275 case '+':
276 case '=':
277 error ("operand constraint contains incorrectly positioned "
278 "%<+%> or %<=%>");
279 return false;
281 case '%':
282 if (operand_num + 1 == ninputs + noutputs)
284 error ("%<%%%> constraint used with last operand");
285 return false;
287 break;
289 case '?': case '!': case '*': case '&': case '#':
290 case 'E': case 'F': case 'G': case 'H':
291 case 's': case 'i': case 'n':
292 case 'I': case 'J': case 'K': case 'L': case 'M':
293 case 'N': case 'O': case 'P': case ',':
294 break;
296 case '0': case '1': case '2': case '3': case '4':
297 case '5': case '6': case '7': case '8': case '9':
298 case '[':
299 error ("matching constraint not valid in output operand");
300 return false;
302 case '<': case '>':
303 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
304 excepting those that expand_call created. So match memory
305 and hope. */
306 *allows_mem = true;
307 break;
309 case 'g': case 'X':
310 *allows_reg = true;
311 *allows_mem = true;
312 break;
314 default:
315 if (!ISALPHA (*p))
316 break;
317 enum constraint_num cn = lookup_constraint (p);
318 if (reg_class_for_constraint (cn) != NO_REGS
319 || insn_extra_address_constraint (cn))
320 *allows_reg = true;
321 else if (insn_extra_memory_constraint (cn))
322 *allows_mem = true;
323 else
325 /* Otherwise we can't assume anything about the nature of
326 the constraint except that it isn't purely registers.
327 Treat it like "g" and hope for the best. */
328 *allows_reg = true;
329 *allows_mem = true;
331 break;
334 return true;
337 /* Similar, but for input constraints. */
339 bool
340 parse_input_constraint (const char **constraint_p, int input_num,
341 int ninputs, int noutputs, int ninout,
342 const char * const * constraints,
343 bool *allows_mem, bool *allows_reg)
345 const char *constraint = *constraint_p;
346 const char *orig_constraint = constraint;
347 size_t c_len = strlen (constraint);
348 size_t j;
349 bool saw_match = false;
351 /* Assume the constraint doesn't allow the use of either
352 a register or memory. */
353 *allows_mem = false;
354 *allows_reg = false;
356 /* Make sure constraint has neither `=', `+', nor '&'. */
358 for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
359 switch (constraint[j])
361 case '+': case '=': case '&':
362 if (constraint == orig_constraint)
364 error ("input operand constraint contains %qc", constraint[j]);
365 return false;
367 break;
369 case '%':
370 if (constraint == orig_constraint
371 && input_num + 1 == ninputs - ninout)
373 error ("%<%%%> constraint used with last operand");
374 return false;
376 break;
378 case '<': case '>':
379 case '?': case '!': case '*': case '#':
380 case 'E': case 'F': case 'G': case 'H':
381 case 's': case 'i': case 'n':
382 case 'I': case 'J': case 'K': case 'L': case 'M':
383 case 'N': case 'O': case 'P': case ',':
384 break;
386 /* Whether or not a numeric constraint allows a register is
387 decided by the matching constraint, and so there is no need
388 to do anything special with them. We must handle them in
389 the default case, so that we don't unnecessarily force
390 operands to memory. */
391 case '0': case '1': case '2': case '3': case '4':
392 case '5': case '6': case '7': case '8': case '9':
394 char *end;
395 unsigned long match;
397 saw_match = true;
399 match = strtoul (constraint + j, &end, 10);
400 if (match >= (unsigned long) noutputs)
402 error ("matching constraint references invalid operand number");
403 return false;
406 /* Try and find the real constraint for this dup. Only do this
407 if the matching constraint is the only alternative. */
408 if (*end == '\0'
409 && (j == 0 || (j == 1 && constraint[0] == '%')))
411 constraint = constraints[match];
412 *constraint_p = constraint;
413 c_len = strlen (constraint);
414 j = 0;
415 /* ??? At the end of the loop, we will skip the first part of
416 the matched constraint. This assumes not only that the
417 other constraint is an output constraint, but also that
418 the '=' or '+' come first. */
419 break;
421 else
422 j = end - constraint;
423 /* Anticipate increment at end of loop. */
424 j--;
426 /* Fall through. */
428 case 'g': case 'X':
429 *allows_reg = true;
430 *allows_mem = true;
431 break;
433 default:
434 if (! ISALPHA (constraint[j]))
436 error ("invalid punctuation %qc in constraint", constraint[j]);
437 return false;
439 enum constraint_num cn = lookup_constraint (constraint + j);
440 if (reg_class_for_constraint (cn) != NO_REGS
441 || insn_extra_address_constraint (cn))
442 *allows_reg = true;
443 else if (insn_extra_memory_constraint (cn))
444 *allows_mem = true;
445 else
447 /* Otherwise we can't assume anything about the nature of
448 the constraint except that it isn't purely registers.
449 Treat it like "g" and hope for the best. */
450 *allows_reg = true;
451 *allows_mem = true;
453 break;
456 if (saw_match && !*allows_reg)
457 warning (0, "matching constraint does not allow a register");
459 return true;
462 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
463 can be an asm-declared register. Called via walk_tree. */
465 static tree
466 decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED,
467 void *data)
469 tree decl = *declp;
470 const HARD_REG_SET *const regs = (const HARD_REG_SET *) data;
472 if (TREE_CODE (decl) == VAR_DECL)
474 if (DECL_HARD_REGISTER (decl)
475 && REG_P (DECL_RTL (decl))
476 && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
478 rtx reg = DECL_RTL (decl);
480 if (overlaps_hard_reg_set_p (*regs, GET_MODE (reg), REGNO (reg)))
481 return decl;
483 walk_subtrees = 0;
485 else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL)
486 walk_subtrees = 0;
487 return NULL_TREE;
490 /* If there is an overlap between *REGS and DECL, return the first overlap
491 found. */
492 tree
493 tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs)
495 return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL);
499 /* A subroutine of expand_asm_operands. Check that all operand names
500 are unique. Return true if so. We rely on the fact that these names
501 are identifiers, and so have been canonicalized by get_identifier,
502 so all we need are pointer comparisons. */
504 static bool
505 check_unique_operand_names (tree outputs, tree inputs, tree labels)
507 tree i, j, i_name = NULL_TREE;
509 for (i = outputs; i ; i = TREE_CHAIN (i))
511 i_name = TREE_PURPOSE (TREE_PURPOSE (i));
512 if (! i_name)
513 continue;
515 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
516 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
517 goto failure;
520 for (i = inputs; i ; i = TREE_CHAIN (i))
522 i_name = TREE_PURPOSE (TREE_PURPOSE (i));
523 if (! i_name)
524 continue;
526 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
527 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
528 goto failure;
529 for (j = outputs; j ; j = TREE_CHAIN (j))
530 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
531 goto failure;
534 for (i = labels; i ; i = TREE_CHAIN (i))
536 i_name = TREE_PURPOSE (i);
537 if (! i_name)
538 continue;
540 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
541 if (simple_cst_equal (i_name, TREE_PURPOSE (j)))
542 goto failure;
543 for (j = inputs; j ; j = TREE_CHAIN (j))
544 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
545 goto failure;
548 return true;
550 failure:
551 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name));
552 return false;
555 /* A subroutine of expand_asm_operands. Resolve the names of the operands
556 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
557 STRING and in the constraints to those numbers. */
559 tree
560 resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels)
562 char *buffer;
563 char *p;
564 const char *c;
565 tree t;
567 check_unique_operand_names (outputs, inputs, labels);
569 /* Substitute [<name>] in input constraint strings. There should be no
570 named operands in output constraints. */
571 for (t = inputs; t ; t = TREE_CHAIN (t))
573 c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
574 if (strchr (c, '[') != NULL)
576 p = buffer = xstrdup (c);
577 while ((p = strchr (p, '[')) != NULL)
578 p = resolve_operand_name_1 (p, outputs, inputs, NULL);
579 TREE_VALUE (TREE_PURPOSE (t))
580 = build_string (strlen (buffer), buffer);
581 free (buffer);
585 /* Now check for any needed substitutions in the template. */
586 c = TREE_STRING_POINTER (string);
587 while ((c = strchr (c, '%')) != NULL)
589 if (c[1] == '[')
590 break;
591 else if (ISALPHA (c[1]) && c[2] == '[')
592 break;
593 else
595 c += 1 + (c[1] == '%');
596 continue;
600 if (c)
602 /* OK, we need to make a copy so we can perform the substitutions.
603 Assume that we will not need extra space--we get to remove '['
604 and ']', which means we cannot have a problem until we have more
605 than 999 operands. */
606 buffer = xstrdup (TREE_STRING_POINTER (string));
607 p = buffer + (c - TREE_STRING_POINTER (string));
609 while ((p = strchr (p, '%')) != NULL)
611 if (p[1] == '[')
612 p += 1;
613 else if (ISALPHA (p[1]) && p[2] == '[')
614 p += 2;
615 else
617 p += 1 + (p[1] == '%');
618 continue;
621 p = resolve_operand_name_1 (p, outputs, inputs, labels);
624 string = build_string (strlen (buffer), buffer);
625 free (buffer);
628 return string;
631 /* A subroutine of resolve_operand_names. P points to the '[' for a
632 potential named operand of the form [<name>]. In place, replace
633 the name and brackets with a number. Return a pointer to the
634 balance of the string after substitution. */
636 static char *
637 resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels)
639 char *q;
640 int op;
641 tree t;
643 /* Collect the operand name. */
644 q = strchr (++p, ']');
645 if (!q)
647 error ("missing close brace for named operand");
648 return strchr (p, '\0');
650 *q = '\0';
652 /* Resolve the name to a number. */
653 for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
655 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
656 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
657 goto found;
659 for (t = inputs; t ; t = TREE_CHAIN (t), op++)
661 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
662 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
663 goto found;
665 for (t = labels; t ; t = TREE_CHAIN (t), op++)
667 tree name = TREE_PURPOSE (t);
668 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
669 goto found;
672 error ("undefined named operand %qs", identifier_to_locale (p));
673 op = 0;
675 found:
676 /* Replace the name with the number. Unfortunately, not all libraries
677 get the return value of sprintf correct, so search for the end of the
678 generated string by hand. */
679 sprintf (--p, "%d", op);
680 p = strchr (p, '\0');
682 /* Verify the no extra buffer space assumption. */
683 gcc_assert (p <= q);
685 /* Shift the rest of the buffer down to fill the gap. */
686 memmove (p, q + 1, strlen (q + 1) + 1);
688 return p;
692 /* Generate RTL to return directly from the current function.
693 (That is, we bypass any return value.) */
695 void
696 expand_naked_return (void)
698 rtx end_label;
700 clear_pending_stack_adjust ();
701 do_pending_stack_adjust ();
703 end_label = naked_return_label;
704 if (end_label == 0)
705 end_label = naked_return_label = gen_label_rtx ();
707 emit_jump (end_label);
710 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
711 is the probability of jumping to LABEL. */
712 static void
713 do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label,
714 int unsignedp, int prob)
716 gcc_assert (prob <= REG_BR_PROB_BASE);
717 do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
718 NULL_RTX, NULL_RTX, label, prob);
721 /* Do the insertion of a case label into case_list. The labels are
722 fed to us in descending order from the sorted vector of case labels used
723 in the tree part of the middle end. So the list we construct is
724 sorted in ascending order.
726 LABEL is the case label to be inserted. LOW and HIGH are the bounds
727 against which the index is compared to jump to LABEL and PROB is the
728 estimated probability LABEL is reached from the switch statement. */
730 static struct case_node *
731 add_case_node (struct case_node *head, tree low, tree high,
732 tree label, int prob, alloc_pool case_node_pool)
734 struct case_node *r;
736 gcc_checking_assert (low);
737 gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high)));
739 /* Add this label to the chain. */
740 r = (struct case_node *) pool_alloc (case_node_pool);
741 r->low = low;
742 r->high = high;
743 r->code_label = label;
744 r->parent = r->left = NULL;
745 r->prob = prob;
746 r->subtree_prob = prob;
747 r->right = head;
748 return r;
751 /* Dump ROOT, a list or tree of case nodes, to file. */
753 static void
754 dump_case_nodes (FILE *f, struct case_node *root,
755 int indent_step, int indent_level)
757 if (root == 0)
758 return;
759 indent_level++;
761 dump_case_nodes (f, root->left, indent_step, indent_level);
763 fputs (";; ", f);
764 fprintf (f, "%*s", indent_step * indent_level, "");
765 print_dec (root->low, f, TYPE_SIGN (TREE_TYPE (root->low)));
766 if (!tree_int_cst_equal (root->low, root->high))
768 fprintf (f, " ... ");
769 print_dec (root->high, f, TYPE_SIGN (TREE_TYPE (root->high)));
771 fputs ("\n", f);
773 dump_case_nodes (f, root->right, indent_step, indent_level);
776 #ifndef HAVE_casesi
777 #define HAVE_casesi 0
778 #endif
780 #ifndef HAVE_tablejump
781 #define HAVE_tablejump 0
782 #endif
784 /* Return the smallest number of different values for which it is best to use a
785 jump-table instead of a tree of conditional branches. */
787 static unsigned int
788 case_values_threshold (void)
790 unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
792 if (threshold == 0)
793 threshold = targetm.case_values_threshold ();
795 return threshold;
798 /* Return true if a switch should be expanded as a decision tree.
799 RANGE is the difference between highest and lowest case.
800 UNIQ is number of unique case node targets, not counting the default case.
801 COUNT is the number of comparisons needed, not counting the default case. */
803 static bool
804 expand_switch_as_decision_tree_p (tree range,
805 unsigned int uniq ATTRIBUTE_UNUSED,
806 unsigned int count)
808 int max_ratio;
810 /* If neither casesi or tablejump is available, or flag_jump_tables
811 over-ruled us, we really have no choice. */
812 if (!HAVE_casesi && !HAVE_tablejump)
813 return true;
814 if (!flag_jump_tables)
815 return true;
816 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
817 if (flag_pic)
818 return true;
819 #endif
821 /* If the switch is relatively small such that the cost of one
822 indirect jump on the target are higher than the cost of a
823 decision tree, go with the decision tree.
825 If range of values is much bigger than number of values,
826 or if it is too large to represent in a HOST_WIDE_INT,
827 make a sequence of conditional branches instead of a dispatch.
829 The definition of "much bigger" depends on whether we are
830 optimizing for size or for speed. If the former, the maximum
831 ratio range/count = 3, because this was found to be the optimal
832 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
833 10 is much older, and was probably selected after an extensive
834 benchmarking investigation on numerous platforms. Or maybe it
835 just made sense to someone at some point in the history of GCC,
836 who knows... */
837 max_ratio = optimize_insn_for_size_p () ? 3 : 10;
838 if (count < case_values_threshold ()
839 || ! tree_fits_uhwi_p (range)
840 || compare_tree_int (range, max_ratio * count) > 0)
841 return true;
843 return false;
846 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
847 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
848 DEFAULT_PROB is the estimated probability that it jumps to
849 DEFAULT_LABEL.
851 We generate a binary decision tree to select the appropriate target
852 code. This is done as follows:
854 If the index is a short or char that we do not have
855 an insn to handle comparisons directly, convert it to
856 a full integer now, rather than letting each comparison
857 generate the conversion.
859 Load the index into a register.
861 The list of cases is rearranged into a binary tree,
862 nearly optimal assuming equal probability for each case.
864 The tree is transformed into RTL, eliminating redundant
865 test conditions at the same time.
867 If program flow could reach the end of the decision tree
868 an unconditional jump to the default code is emitted.
870 The above process is unaware of the CFG. The caller has to fix up
871 the CFG itself. This is done in cfgexpand.c. */
873 static void
874 emit_case_decision_tree (tree index_expr, tree index_type,
875 struct case_node *case_list, rtx default_label,
876 int default_prob)
878 rtx index = expand_normal (index_expr);
880 if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
881 && ! have_insn_for (COMPARE, GET_MODE (index)))
883 int unsignedp = TYPE_UNSIGNED (index_type);
884 enum machine_mode wider_mode;
885 for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
886 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
887 if (have_insn_for (COMPARE, wider_mode))
889 index = convert_to_mode (wider_mode, index, unsignedp);
890 break;
894 do_pending_stack_adjust ();
896 if (MEM_P (index))
898 index = copy_to_reg (index);
899 if (TREE_CODE (index_expr) == SSA_NAME)
900 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr), index);
903 balance_case_nodes (&case_list, NULL);
905 if (dump_file && (dump_flags & TDF_DETAILS))
907 int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
908 fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
909 dump_case_nodes (dump_file, case_list, indent_step, 0);
912 emit_case_nodes (index, case_list, default_label, default_prob, index_type);
913 if (default_label)
914 emit_jump (default_label);
917 /* Return the sum of probabilities of outgoing edges of basic block BB. */
919 static int
920 get_outgoing_edge_probs (basic_block bb)
922 edge e;
923 edge_iterator ei;
924 int prob_sum = 0;
925 if (!bb)
926 return 0;
927 FOR_EACH_EDGE (e, ei, bb->succs)
928 prob_sum += e->probability;
929 return prob_sum;
932 /* Computes the conditional probability of jumping to a target if the branch
933 instruction is executed.
934 TARGET_PROB is the estimated probability of jumping to a target relative
935 to some basic block BB.
936 BASE_PROB is the probability of reaching the branch instruction relative
937 to the same basic block BB. */
939 static inline int
940 conditional_probability (int target_prob, int base_prob)
942 if (base_prob > 0)
944 gcc_assert (target_prob >= 0);
945 gcc_assert (target_prob <= base_prob);
946 return GCOV_COMPUTE_SCALE (target_prob, base_prob);
948 return -1;
951 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
952 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
953 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
954 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
956 First, a jump insn is emitted. First we try "casesi". If that
957 fails, try "tablejump". A target *must* have one of them (or both).
959 Then, a table with the target labels is emitted.
961 The process is unaware of the CFG. The caller has to fix up
962 the CFG itself. This is done in cfgexpand.c. */
964 static void
965 emit_case_dispatch_table (tree index_expr, tree index_type,
966 struct case_node *case_list, rtx default_label,
967 tree minval, tree maxval, tree range,
968 basic_block stmt_bb)
970 int i, ncases;
971 struct case_node *n;
972 rtx *labelvec;
973 rtx fallback_label = label_rtx (case_list->code_label);
974 rtx_code_label *table_label = gen_label_rtx ();
975 bool has_gaps = false;
976 edge default_edge = stmt_bb ? EDGE_SUCC (stmt_bb, 0) : NULL;
977 int default_prob = default_edge ? default_edge->probability : 0;
978 int base = get_outgoing_edge_probs (stmt_bb);
979 bool try_with_tablejump = false;
981 int new_default_prob = conditional_probability (default_prob,
982 base);
984 if (! try_casesi (index_type, index_expr, minval, range,
985 table_label, default_label, fallback_label,
986 new_default_prob))
988 /* Index jumptables from zero for suitable values of minval to avoid
989 a subtraction. For the rationale see:
990 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
991 if (optimize_insn_for_speed_p ()
992 && compare_tree_int (minval, 0) > 0
993 && compare_tree_int (minval, 3) < 0)
995 minval = build_int_cst (index_type, 0);
996 range = maxval;
997 has_gaps = true;
999 try_with_tablejump = true;
1002 /* Get table of labels to jump to, in order of case index. */
1004 ncases = tree_to_shwi (range) + 1;
1005 labelvec = XALLOCAVEC (rtx, ncases);
1006 memset (labelvec, 0, ncases * sizeof (rtx));
1008 for (n = case_list; n; n = n->right)
1010 /* Compute the low and high bounds relative to the minimum
1011 value since that should fit in a HOST_WIDE_INT while the
1012 actual values may not. */
1013 HOST_WIDE_INT i_low
1014 = tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
1015 n->low, minval));
1016 HOST_WIDE_INT i_high
1017 = tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
1018 n->high, minval));
1019 HOST_WIDE_INT i;
1021 for (i = i_low; i <= i_high; i ++)
1022 labelvec[i]
1023 = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
1026 /* Fill in the gaps with the default. We may have gaps at
1027 the beginning if we tried to avoid the minval subtraction,
1028 so substitute some label even if the default label was
1029 deemed unreachable. */
1030 if (!default_label)
1031 default_label = fallback_label;
1032 for (i = 0; i < ncases; i++)
1033 if (labelvec[i] == 0)
1035 has_gaps = true;
1036 labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
1039 if (has_gaps)
1041 /* There is at least one entry in the jump table that jumps
1042 to default label. The default label can either be reached
1043 through the indirect jump or the direct conditional jump
1044 before that. Split the probability of reaching the
1045 default label among these two jumps. */
1046 new_default_prob = conditional_probability (default_prob/2,
1047 base);
1048 default_prob /= 2;
1049 base -= default_prob;
1051 else
1053 base -= default_prob;
1054 default_prob = 0;
1057 if (default_edge)
1058 default_edge->probability = default_prob;
1060 /* We have altered the probability of the default edge. So the probabilities
1061 of all other edges need to be adjusted so that it sums up to
1062 REG_BR_PROB_BASE. */
1063 if (base)
1065 edge e;
1066 edge_iterator ei;
1067 FOR_EACH_EDGE (e, ei, stmt_bb->succs)
1068 e->probability = GCOV_COMPUTE_SCALE (e->probability, base);
1071 if (try_with_tablejump)
1073 bool ok = try_tablejump (index_type, index_expr, minval, range,
1074 table_label, default_label, new_default_prob);
1075 gcc_assert (ok);
1077 /* Output the table. */
1078 emit_label (table_label);
1080 if (CASE_VECTOR_PC_RELATIVE || flag_pic)
1081 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
1082 gen_rtx_LABEL_REF (Pmode,
1083 table_label),
1084 gen_rtvec_v (ncases, labelvec),
1085 const0_rtx, const0_rtx));
1086 else
1087 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
1088 gen_rtvec_v (ncases, labelvec)));
1090 /* Record no drop-through after the table. */
1091 emit_barrier ();
1094 /* Reset the aux field of all outgoing edges of basic block BB. */
1096 static inline void
1097 reset_out_edges_aux (basic_block bb)
1099 edge e;
1100 edge_iterator ei;
1101 FOR_EACH_EDGE (e, ei, bb->succs)
1102 e->aux = (void *)0;
1105 /* Compute the number of case labels that correspond to each outgoing edge of
1106 STMT. Record this information in the aux field of the edge. */
1108 static inline void
1109 compute_cases_per_edge (gimple stmt)
1111 basic_block bb = gimple_bb (stmt);
1112 reset_out_edges_aux (bb);
1113 int ncases = gimple_switch_num_labels (stmt);
1114 for (int i = ncases - 1; i >= 1; --i)
1116 tree elt = gimple_switch_label (stmt, i);
1117 tree lab = CASE_LABEL (elt);
1118 basic_block case_bb = label_to_block_fn (cfun, lab);
1119 edge case_edge = find_edge (bb, case_bb);
1120 case_edge->aux = (void *)((intptr_t)(case_edge->aux) + 1);
1124 /* Terminate a case (Pascal/Ada) or switch (C) statement
1125 in which ORIG_INDEX is the expression to be tested.
1126 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
1127 type as given in the source before any compiler conversions.
1128 Generate the code to test it and jump to the right place. */
1130 void
1131 expand_case (gimple stmt)
1133 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
1134 rtx default_label = NULL_RTX;
1135 unsigned int count, uniq;
1136 int i;
1137 int ncases = gimple_switch_num_labels (stmt);
1138 tree index_expr = gimple_switch_index (stmt);
1139 tree index_type = TREE_TYPE (index_expr);
1140 tree elt;
1141 basic_block bb = gimple_bb (stmt);
1143 /* A list of case labels; it is first built as a list and it may then
1144 be rearranged into a nearly balanced binary tree. */
1145 struct case_node *case_list = 0;
1147 /* A pool for case nodes. */
1148 alloc_pool case_node_pool;
1150 /* An ERROR_MARK occurs for various reasons including invalid data type.
1151 ??? Can this still happen, with GIMPLE and all? */
1152 if (index_type == error_mark_node)
1153 return;
1155 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
1156 expressions being INTEGER_CST. */
1157 gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
1159 case_node_pool = create_alloc_pool ("struct case_node pool",
1160 sizeof (struct case_node),
1161 100);
1163 do_pending_stack_adjust ();
1165 /* Find the default case target label. */
1166 default_label = label_rtx (CASE_LABEL (gimple_switch_default_label (stmt)));
1167 edge default_edge = EDGE_SUCC (bb, 0);
1168 int default_prob = default_edge->probability;
1170 /* Get upper and lower bounds of case values. */
1171 elt = gimple_switch_label (stmt, 1);
1172 minval = fold_convert (index_type, CASE_LOW (elt));
1173 elt = gimple_switch_label (stmt, ncases - 1);
1174 if (CASE_HIGH (elt))
1175 maxval = fold_convert (index_type, CASE_HIGH (elt));
1176 else
1177 maxval = fold_convert (index_type, CASE_LOW (elt));
1179 /* Compute span of values. */
1180 range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
1182 /* Listify the labels queue and gather some numbers to decide
1183 how to expand this switch(). */
1184 uniq = 0;
1185 count = 0;
1186 hash_set<tree> seen_labels;
1187 compute_cases_per_edge (stmt);
1189 for (i = ncases - 1; i >= 1; --i)
1191 elt = gimple_switch_label (stmt, i);
1192 tree low = CASE_LOW (elt);
1193 gcc_assert (low);
1194 tree high = CASE_HIGH (elt);
1195 gcc_assert (! high || tree_int_cst_lt (low, high));
1196 tree lab = CASE_LABEL (elt);
1198 /* Count the elements.
1199 A range counts double, since it requires two compares. */
1200 count++;
1201 if (high)
1202 count++;
1204 /* If we have not seen this label yet, then increase the
1205 number of unique case node targets seen. */
1206 if (!seen_labels.add (lab))
1207 uniq++;
1209 /* The bounds on the case range, LOW and HIGH, have to be converted
1210 to case's index type TYPE. Note that the original type of the
1211 case index in the source code is usually "lost" during
1212 gimplification due to type promotion, but the case labels retain the
1213 original type. Make sure to drop overflow flags. */
1214 low = fold_convert (index_type, low);
1215 if (TREE_OVERFLOW (low))
1216 low = wide_int_to_tree (index_type, low);
1218 /* The canonical from of a case label in GIMPLE is that a simple case
1219 has an empty CASE_HIGH. For the casesi and tablejump expanders,
1220 the back ends want simple cases to have high == low. */
1221 if (! high)
1222 high = low;
1223 high = fold_convert (index_type, high);
1224 if (TREE_OVERFLOW (high))
1225 high = wide_int_to_tree (index_type, high);
1227 basic_block case_bb = label_to_block_fn (cfun, lab);
1228 edge case_edge = find_edge (bb, case_bb);
1229 case_list = add_case_node (
1230 case_list, low, high, lab,
1231 case_edge->probability / (intptr_t)(case_edge->aux),
1232 case_node_pool);
1234 reset_out_edges_aux (bb);
1236 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
1237 destination, such as one with a default case only.
1238 It also removes cases that are out of range for the switch
1239 type, so we should never get a zero here. */
1240 gcc_assert (count > 0);
1242 rtx_insn *before_case = get_last_insn ();
1244 /* Decide how to expand this switch.
1245 The two options at this point are a dispatch table (casesi or
1246 tablejump) or a decision tree. */
1248 if (expand_switch_as_decision_tree_p (range, uniq, count))
1249 emit_case_decision_tree (index_expr, index_type,
1250 case_list, default_label,
1251 default_prob);
1252 else
1253 emit_case_dispatch_table (index_expr, index_type,
1254 case_list, default_label,
1255 minval, maxval, range, bb);
1257 reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
1259 free_temp_slots ();
1260 free_alloc_pool (case_node_pool);
1263 /* Expand the dispatch to a short decrement chain if there are few cases
1264 to dispatch to. Likewise if neither casesi nor tablejump is available,
1265 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
1266 tablejump. The index mode is always the mode of integer_type_node.
1267 Trap if no case matches the index.
1269 DISPATCH_INDEX is the index expression to switch on. It should be a
1270 memory or register operand.
1272 DISPATCH_TABLE is a set of case labels. The set should be sorted in
1273 ascending order, be contiguous, starting with value 0, and contain only
1274 single-valued case labels. */
1276 void
1277 expand_sjlj_dispatch_table (rtx dispatch_index,
1278 vec<tree> dispatch_table)
1280 tree index_type = integer_type_node;
1281 enum machine_mode index_mode = TYPE_MODE (index_type);
1283 int ncases = dispatch_table.length ();
1285 do_pending_stack_adjust ();
1286 rtx_insn *before_case = get_last_insn ();
1288 /* Expand as a decrement-chain if there are 5 or fewer dispatch
1289 labels. This covers more than 98% of the cases in libjava,
1290 and seems to be a reasonable compromise between the "old way"
1291 of expanding as a decision tree or dispatch table vs. the "new
1292 way" with decrement chain or dispatch table. */
1293 if (dispatch_table.length () <= 5
1294 || (!HAVE_casesi && !HAVE_tablejump)
1295 || !flag_jump_tables)
1297 /* Expand the dispatch as a decrement chain:
1299 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1303 if (index == 0) do_0; else index--;
1304 if (index == 0) do_1; else index--;
1306 if (index == 0) do_N; else index--;
1308 This is more efficient than a dispatch table on most machines.
1309 The last "index--" is redundant but the code is trivially dead
1310 and will be cleaned up by later passes. */
1311 rtx index = copy_to_mode_reg (index_mode, dispatch_index);
1312 rtx zero = CONST0_RTX (index_mode);
1313 for (int i = 0; i < ncases; i++)
1315 tree elt = dispatch_table[i];
1316 rtx lab = label_rtx (CASE_LABEL (elt));
1317 do_jump_if_equal (index_mode, index, zero, lab, 0, -1);
1318 force_expand_binop (index_mode, sub_optab,
1319 index, CONST1_RTX (index_mode),
1320 index, 0, OPTAB_DIRECT);
1323 else
1325 /* Similar to expand_case, but much simpler. */
1326 struct case_node *case_list = 0;
1327 alloc_pool case_node_pool = create_alloc_pool ("struct sjlj_case pool",
1328 sizeof (struct case_node),
1329 ncases);
1330 tree index_expr = make_tree (index_type, dispatch_index);
1331 tree minval = build_int_cst (index_type, 0);
1332 tree maxval = CASE_LOW (dispatch_table.last ());
1333 tree range = maxval;
1334 rtx_code_label *default_label = gen_label_rtx ();
1336 for (int i = ncases - 1; i >= 0; --i)
1338 tree elt = dispatch_table[i];
1339 tree low = CASE_LOW (elt);
1340 tree lab = CASE_LABEL (elt);
1341 case_list = add_case_node (case_list, low, low, lab, 0, case_node_pool);
1344 emit_case_dispatch_table (index_expr, index_type,
1345 case_list, default_label,
1346 minval, maxval, range,
1347 BLOCK_FOR_INSN (before_case));
1348 emit_label (default_label);
1349 free_alloc_pool (case_node_pool);
1352 /* Dispatching something not handled? Trap! */
1353 expand_builtin_trap ();
1355 reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
1357 free_temp_slots ();
1361 /* Take an ordered list of case nodes
1362 and transform them into a near optimal binary tree,
1363 on the assumption that any target code selection value is as
1364 likely as any other.
1366 The transformation is performed by splitting the ordered
1367 list into two equal sections plus a pivot. The parts are
1368 then attached to the pivot as left and right branches. Each
1369 branch is then transformed recursively. */
1371 static void
1372 balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
1374 case_node_ptr np;
1376 np = *head;
1377 if (np)
1379 int i = 0;
1380 int ranges = 0;
1381 case_node_ptr *npp;
1382 case_node_ptr left;
1384 /* Count the number of entries on branch. Also count the ranges. */
1386 while (np)
1388 if (!tree_int_cst_equal (np->low, np->high))
1389 ranges++;
1391 i++;
1392 np = np->right;
1395 if (i > 2)
1397 /* Split this list if it is long enough for that to help. */
1398 npp = head;
1399 left = *npp;
1401 /* If there are just three nodes, split at the middle one. */
1402 if (i == 3)
1403 npp = &(*npp)->right;
1404 else
1406 /* Find the place in the list that bisects the list's total cost,
1407 where ranges count as 2.
1408 Here I gets half the total cost. */
1409 i = (i + ranges + 1) / 2;
1410 while (1)
1412 /* Skip nodes while their cost does not reach that amount. */
1413 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
1414 i--;
1415 i--;
1416 if (i <= 0)
1417 break;
1418 npp = &(*npp)->right;
1421 *head = np = *npp;
1422 *npp = 0;
1423 np->parent = parent;
1424 np->left = left;
1426 /* Optimize each of the two split parts. */
1427 balance_case_nodes (&np->left, np);
1428 balance_case_nodes (&np->right, np);
1429 np->subtree_prob = np->prob;
1430 np->subtree_prob += np->left->subtree_prob;
1431 np->subtree_prob += np->right->subtree_prob;
1433 else
1435 /* Else leave this branch as one level,
1436 but fill in `parent' fields. */
1437 np = *head;
1438 np->parent = parent;
1439 np->subtree_prob = np->prob;
1440 for (; np->right; np = np->right)
1442 np->right->parent = np;
1443 (*head)->subtree_prob += np->right->subtree_prob;
1449 /* Search the parent sections of the case node tree
1450 to see if a test for the lower bound of NODE would be redundant.
1451 INDEX_TYPE is the type of the index expression.
1453 The instructions to generate the case decision tree are
1454 output in the same order as nodes are processed so it is
1455 known that if a parent node checks the range of the current
1456 node minus one that the current node is bounded at its lower
1457 span. Thus the test would be redundant. */
1459 static int
1460 node_has_low_bound (case_node_ptr node, tree index_type)
1462 tree low_minus_one;
1463 case_node_ptr pnode;
1465 /* If the lower bound of this node is the lowest value in the index type,
1466 we need not test it. */
1468 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
1469 return 1;
1471 /* If this node has a left branch, the value at the left must be less
1472 than that at this node, so it cannot be bounded at the bottom and
1473 we need not bother testing any further. */
1475 if (node->left)
1476 return 0;
1478 low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low),
1479 node->low,
1480 build_int_cst (TREE_TYPE (node->low), 1));
1482 /* If the subtraction above overflowed, we can't verify anything.
1483 Otherwise, look for a parent that tests our value - 1. */
1485 if (! tree_int_cst_lt (low_minus_one, node->low))
1486 return 0;
1488 for (pnode = node->parent; pnode; pnode = pnode->parent)
1489 if (tree_int_cst_equal (low_minus_one, pnode->high))
1490 return 1;
1492 return 0;
1495 /* Search the parent sections of the case node tree
1496 to see if a test for the upper bound of NODE would be redundant.
1497 INDEX_TYPE is the type of the index expression.
1499 The instructions to generate the case decision tree are
1500 output in the same order as nodes are processed so it is
1501 known that if a parent node checks the range of the current
1502 node plus one that the current node is bounded at its upper
1503 span. Thus the test would be redundant. */
1505 static int
1506 node_has_high_bound (case_node_ptr node, tree index_type)
1508 tree high_plus_one;
1509 case_node_ptr pnode;
1511 /* If there is no upper bound, obviously no test is needed. */
1513 if (TYPE_MAX_VALUE (index_type) == NULL)
1514 return 1;
1516 /* If the upper bound of this node is the highest value in the type
1517 of the index expression, we need not test against it. */
1519 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
1520 return 1;
1522 /* If this node has a right branch, the value at the right must be greater
1523 than that at this node, so it cannot be bounded at the top and
1524 we need not bother testing any further. */
1526 if (node->right)
1527 return 0;
1529 high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high),
1530 node->high,
1531 build_int_cst (TREE_TYPE (node->high), 1));
1533 /* If the addition above overflowed, we can't verify anything.
1534 Otherwise, look for a parent that tests our value + 1. */
1536 if (! tree_int_cst_lt (node->high, high_plus_one))
1537 return 0;
1539 for (pnode = node->parent; pnode; pnode = pnode->parent)
1540 if (tree_int_cst_equal (high_plus_one, pnode->low))
1541 return 1;
1543 return 0;
1546 /* Search the parent sections of the
1547 case node tree to see if both tests for the upper and lower
1548 bounds of NODE would be redundant. */
1550 static int
1551 node_is_bounded (case_node_ptr node, tree index_type)
1553 return (node_has_low_bound (node, index_type)
1554 && node_has_high_bound (node, index_type));
1558 /* Emit step-by-step code to select a case for the value of INDEX.
1559 The thus generated decision tree follows the form of the
1560 case-node binary tree NODE, whose nodes represent test conditions.
1561 INDEX_TYPE is the type of the index of the switch.
1563 Care is taken to prune redundant tests from the decision tree
1564 by detecting any boundary conditions already checked by
1565 emitted rtx. (See node_has_high_bound, node_has_low_bound
1566 and node_is_bounded, above.)
1568 Where the test conditions can be shown to be redundant we emit
1569 an unconditional jump to the target code. As a further
1570 optimization, the subordinates of a tree node are examined to
1571 check for bounded nodes. In this case conditional and/or
1572 unconditional jumps as a result of the boundary check for the
1573 current node are arranged to target the subordinates associated
1574 code for out of bound conditions on the current node.
1576 We can assume that when control reaches the code generated here,
1577 the index value has already been compared with the parents
1578 of this node, and determined to be on the same side of each parent
1579 as this node is. Thus, if this node tests for the value 51,
1580 and a parent tested for 52, we don't need to consider
1581 the possibility of a value greater than 51. If another parent
1582 tests for the value 50, then this node need not test anything. */
1584 static void
1585 emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
1586 int default_prob, tree index_type)
1588 /* If INDEX has an unsigned type, we must make unsigned branches. */
1589 int unsignedp = TYPE_UNSIGNED (index_type);
1590 int probability;
1591 int prob = node->prob, subtree_prob = node->subtree_prob;
1592 enum machine_mode mode = GET_MODE (index);
1593 enum machine_mode imode = TYPE_MODE (index_type);
1595 /* Handle indices detected as constant during RTL expansion. */
1596 if (mode == VOIDmode)
1597 mode = imode;
1599 /* See if our parents have already tested everything for us.
1600 If they have, emit an unconditional jump for this node. */
1601 if (node_is_bounded (node, index_type))
1602 emit_jump (label_rtx (node->code_label));
1604 else if (tree_int_cst_equal (node->low, node->high))
1606 probability = conditional_probability (prob, subtree_prob + default_prob);
1607 /* Node is single valued. First see if the index expression matches
1608 this node and then check our children, if any. */
1609 do_jump_if_equal (mode, index,
1610 convert_modes (mode, imode,
1611 expand_normal (node->low),
1612 unsignedp),
1613 label_rtx (node->code_label), unsignedp, probability);
1614 /* Since this case is taken at this point, reduce its weight from
1615 subtree_weight. */
1616 subtree_prob -= prob;
1617 if (node->right != 0 && node->left != 0)
1619 /* This node has children on both sides.
1620 Dispatch to one side or the other
1621 by comparing the index value with this node's value.
1622 If one subtree is bounded, check that one first,
1623 so we can avoid real branches in the tree. */
1625 if (node_is_bounded (node->right, index_type))
1627 probability = conditional_probability (
1628 node->right->prob,
1629 subtree_prob + default_prob);
1630 emit_cmp_and_jump_insns (index,
1631 convert_modes
1632 (mode, imode,
1633 expand_normal (node->high),
1634 unsignedp),
1635 GT, NULL_RTX, mode, unsignedp,
1636 label_rtx (node->right->code_label),
1637 probability);
1638 emit_case_nodes (index, node->left, default_label, default_prob,
1639 index_type);
1642 else if (node_is_bounded (node->left, index_type))
1644 probability = conditional_probability (
1645 node->left->prob,
1646 subtree_prob + default_prob);
1647 emit_cmp_and_jump_insns (index,
1648 convert_modes
1649 (mode, imode,
1650 expand_normal (node->high),
1651 unsignedp),
1652 LT, NULL_RTX, mode, unsignedp,
1653 label_rtx (node->left->code_label),
1654 probability);
1655 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1658 /* If both children are single-valued cases with no
1659 children, finish up all the work. This way, we can save
1660 one ordered comparison. */
1661 else if (tree_int_cst_equal (node->right->low, node->right->high)
1662 && node->right->left == 0
1663 && node->right->right == 0
1664 && tree_int_cst_equal (node->left->low, node->left->high)
1665 && node->left->left == 0
1666 && node->left->right == 0)
1668 /* Neither node is bounded. First distinguish the two sides;
1669 then emit the code for one side at a time. */
1671 /* See if the value matches what the right hand side
1672 wants. */
1673 probability = conditional_probability (
1674 node->right->prob,
1675 subtree_prob + default_prob);
1676 do_jump_if_equal (mode, index,
1677 convert_modes (mode, imode,
1678 expand_normal (node->right->low),
1679 unsignedp),
1680 label_rtx (node->right->code_label),
1681 unsignedp, probability);
1683 /* See if the value matches what the left hand side
1684 wants. */
1685 probability = conditional_probability (
1686 node->left->prob,
1687 subtree_prob + default_prob);
1688 do_jump_if_equal (mode, index,
1689 convert_modes (mode, imode,
1690 expand_normal (node->left->low),
1691 unsignedp),
1692 label_rtx (node->left->code_label),
1693 unsignedp, probability);
1696 else
1698 /* Neither node is bounded. First distinguish the two sides;
1699 then emit the code for one side at a time. */
1701 tree test_label
1702 = build_decl (curr_insn_location (),
1703 LABEL_DECL, NULL_TREE, NULL_TREE);
1705 /* The default label could be reached either through the right
1706 subtree or the left subtree. Divide the probability
1707 equally. */
1708 probability = conditional_probability (
1709 node->right->subtree_prob + default_prob/2,
1710 subtree_prob + default_prob);
1711 /* See if the value is on the right. */
1712 emit_cmp_and_jump_insns (index,
1713 convert_modes
1714 (mode, imode,
1715 expand_normal (node->high),
1716 unsignedp),
1717 GT, NULL_RTX, mode, unsignedp,
1718 label_rtx (test_label),
1719 probability);
1720 default_prob /= 2;
1722 /* Value must be on the left.
1723 Handle the left-hand subtree. */
1724 emit_case_nodes (index, node->left, default_label, default_prob, index_type);
1725 /* If left-hand subtree does nothing,
1726 go to default. */
1727 if (default_label)
1728 emit_jump (default_label);
1730 /* Code branches here for the right-hand subtree. */
1731 expand_label (test_label);
1732 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1736 else if (node->right != 0 && node->left == 0)
1738 /* Here we have a right child but no left so we issue a conditional
1739 branch to default and process the right child.
1741 Omit the conditional branch to default if the right child
1742 does not have any children and is single valued; it would
1743 cost too much space to save so little time. */
1745 if (node->right->right || node->right->left
1746 || !tree_int_cst_equal (node->right->low, node->right->high))
1748 if (!node_has_low_bound (node, index_type))
1750 probability = conditional_probability (
1751 default_prob/2,
1752 subtree_prob + default_prob);
1753 emit_cmp_and_jump_insns (index,
1754 convert_modes
1755 (mode, imode,
1756 expand_normal (node->high),
1757 unsignedp),
1758 LT, NULL_RTX, mode, unsignedp,
1759 default_label,
1760 probability);
1761 default_prob /= 2;
1764 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1766 else
1768 probability = conditional_probability (
1769 node->right->subtree_prob,
1770 subtree_prob + default_prob);
1771 /* We cannot process node->right normally
1772 since we haven't ruled out the numbers less than
1773 this node's value. So handle node->right explicitly. */
1774 do_jump_if_equal (mode, index,
1775 convert_modes
1776 (mode, imode,
1777 expand_normal (node->right->low),
1778 unsignedp),
1779 label_rtx (node->right->code_label), unsignedp, probability);
1783 else if (node->right == 0 && node->left != 0)
1785 /* Just one subtree, on the left. */
1786 if (node->left->left || node->left->right
1787 || !tree_int_cst_equal (node->left->low, node->left->high))
1789 if (!node_has_high_bound (node, index_type))
1791 probability = conditional_probability (
1792 default_prob/2,
1793 subtree_prob + default_prob);
1794 emit_cmp_and_jump_insns (index,
1795 convert_modes
1796 (mode, imode,
1797 expand_normal (node->high),
1798 unsignedp),
1799 GT, NULL_RTX, mode, unsignedp,
1800 default_label,
1801 probability);
1802 default_prob /= 2;
1805 emit_case_nodes (index, node->left, default_label,
1806 default_prob, index_type);
1808 else
1810 probability = conditional_probability (
1811 node->left->subtree_prob,
1812 subtree_prob + default_prob);
1813 /* We cannot process node->left normally
1814 since we haven't ruled out the numbers less than
1815 this node's value. So handle node->left explicitly. */
1816 do_jump_if_equal (mode, index,
1817 convert_modes
1818 (mode, imode,
1819 expand_normal (node->left->low),
1820 unsignedp),
1821 label_rtx (node->left->code_label), unsignedp, probability);
1825 else
1827 /* Node is a range. These cases are very similar to those for a single
1828 value, except that we do not start by testing whether this node
1829 is the one to branch to. */
1831 if (node->right != 0 && node->left != 0)
1833 /* Node has subtrees on both sides.
1834 If the right-hand subtree is bounded,
1835 test for it first, since we can go straight there.
1836 Otherwise, we need to make a branch in the control structure,
1837 then handle the two subtrees. */
1838 tree test_label = 0;
1840 if (node_is_bounded (node->right, index_type))
1842 /* Right hand node is fully bounded so we can eliminate any
1843 testing and branch directly to the target code. */
1844 probability = conditional_probability (
1845 node->right->subtree_prob,
1846 subtree_prob + default_prob);
1847 emit_cmp_and_jump_insns (index,
1848 convert_modes
1849 (mode, imode,
1850 expand_normal (node->high),
1851 unsignedp),
1852 GT, NULL_RTX, mode, unsignedp,
1853 label_rtx (node->right->code_label),
1854 probability);
1856 else
1858 /* Right hand node requires testing.
1859 Branch to a label where we will handle it later. */
1861 test_label = build_decl (curr_insn_location (),
1862 LABEL_DECL, NULL_TREE, NULL_TREE);
1863 probability = conditional_probability (
1864 node->right->subtree_prob + default_prob/2,
1865 subtree_prob + default_prob);
1866 emit_cmp_and_jump_insns (index,
1867 convert_modes
1868 (mode, imode,
1869 expand_normal (node->high),
1870 unsignedp),
1871 GT, NULL_RTX, mode, unsignedp,
1872 label_rtx (test_label),
1873 probability);
1874 default_prob /= 2;
1877 /* Value belongs to this node or to the left-hand subtree. */
1879 probability = conditional_probability (
1880 prob,
1881 subtree_prob + default_prob);
1882 emit_cmp_and_jump_insns (index,
1883 convert_modes
1884 (mode, imode,
1885 expand_normal (node->low),
1886 unsignedp),
1887 GE, NULL_RTX, mode, unsignedp,
1888 label_rtx (node->code_label),
1889 probability);
1891 /* Handle the left-hand subtree. */
1892 emit_case_nodes (index, node->left, default_label, default_prob, index_type);
1894 /* If right node had to be handled later, do that now. */
1896 if (test_label)
1898 /* If the left-hand subtree fell through,
1899 don't let it fall into the right-hand subtree. */
1900 if (default_label)
1901 emit_jump (default_label);
1903 expand_label (test_label);
1904 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1908 else if (node->right != 0 && node->left == 0)
1910 /* Deal with values to the left of this node,
1911 if they are possible. */
1912 if (!node_has_low_bound (node, index_type))
1914 probability = conditional_probability (
1915 default_prob/2,
1916 subtree_prob + default_prob);
1917 emit_cmp_and_jump_insns (index,
1918 convert_modes
1919 (mode, imode,
1920 expand_normal (node->low),
1921 unsignedp),
1922 LT, NULL_RTX, mode, unsignedp,
1923 default_label,
1924 probability);
1925 default_prob /= 2;
1928 /* Value belongs to this node or to the right-hand subtree. */
1930 probability = conditional_probability (
1931 prob,
1932 subtree_prob + default_prob);
1933 emit_cmp_and_jump_insns (index,
1934 convert_modes
1935 (mode, imode,
1936 expand_normal (node->high),
1937 unsignedp),
1938 LE, NULL_RTX, mode, unsignedp,
1939 label_rtx (node->code_label),
1940 probability);
1942 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1945 else if (node->right == 0 && node->left != 0)
1947 /* Deal with values to the right of this node,
1948 if they are possible. */
1949 if (!node_has_high_bound (node, index_type))
1951 probability = conditional_probability (
1952 default_prob/2,
1953 subtree_prob + default_prob);
1954 emit_cmp_and_jump_insns (index,
1955 convert_modes
1956 (mode, imode,
1957 expand_normal (node->high),
1958 unsignedp),
1959 GT, NULL_RTX, mode, unsignedp,
1960 default_label,
1961 probability);
1962 default_prob /= 2;
1965 /* Value belongs to this node or to the left-hand subtree. */
1967 probability = conditional_probability (
1968 prob,
1969 subtree_prob + default_prob);
1970 emit_cmp_and_jump_insns (index,
1971 convert_modes
1972 (mode, imode,
1973 expand_normal (node->low),
1974 unsignedp),
1975 GE, NULL_RTX, mode, unsignedp,
1976 label_rtx (node->code_label),
1977 probability);
1979 emit_case_nodes (index, node->left, default_label, default_prob, index_type);
1982 else
1984 /* Node has no children so we check low and high bounds to remove
1985 redundant tests. Only one of the bounds can exist,
1986 since otherwise this node is bounded--a case tested already. */
1987 int high_bound = node_has_high_bound (node, index_type);
1988 int low_bound = node_has_low_bound (node, index_type);
1990 if (!high_bound && low_bound)
1992 probability = conditional_probability (
1993 default_prob,
1994 subtree_prob + default_prob);
1995 emit_cmp_and_jump_insns (index,
1996 convert_modes
1997 (mode, imode,
1998 expand_normal (node->high),
1999 unsignedp),
2000 GT, NULL_RTX, mode, unsignedp,
2001 default_label,
2002 probability);
2005 else if (!low_bound && high_bound)
2007 probability = conditional_probability (
2008 default_prob,
2009 subtree_prob + default_prob);
2010 emit_cmp_and_jump_insns (index,
2011 convert_modes
2012 (mode, imode,
2013 expand_normal (node->low),
2014 unsignedp),
2015 LT, NULL_RTX, mode, unsignedp,
2016 default_label,
2017 probability);
2019 else if (!low_bound && !high_bound)
2021 /* Widen LOW and HIGH to the same width as INDEX. */
2022 tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
2023 tree low = build1 (CONVERT_EXPR, type, node->low);
2024 tree high = build1 (CONVERT_EXPR, type, node->high);
2025 rtx low_rtx, new_index, new_bound;
2027 /* Instead of doing two branches, emit one unsigned branch for
2028 (index-low) > (high-low). */
2029 low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL);
2030 new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
2031 NULL_RTX, unsignedp,
2032 OPTAB_WIDEN);
2033 new_bound = expand_expr (fold_build2 (MINUS_EXPR, type,
2034 high, low),
2035 NULL_RTX, mode, EXPAND_NORMAL);
2037 probability = conditional_probability (
2038 default_prob,
2039 subtree_prob + default_prob);
2040 emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
2041 mode, 1, default_label, probability);
2044 emit_jump (label_rtx (node->code_label));