2014-10-24 Christophe Lyon <christophe.lyon@linaro.org>
[official-gcc.git] / gcc / stmt.c
blob96a4c627ad16745d9c7bfddac9638d6337fbbef2
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 "hashtab.h"
39 #include "hash-set.h"
40 #include "vec.h"
41 #include "machmode.h"
42 #include "input.h"
43 #include "function.h"
44 #include "insn-config.h"
45 #include "expr.h"
46 #include "libfuncs.h"
47 #include "recog.h"
48 #include "diagnostic-core.h"
49 #include "output.h"
50 #include "langhooks.h"
51 #include "predict.h"
52 #include "optabs.h"
53 #include "target.h"
54 #include "basic-block.h"
55 #include "tree-ssa-alias.h"
56 #include "internal-fn.h"
57 #include "gimple-expr.h"
58 #include "is-a.h"
59 #include "gimple.h"
60 #include "regs.h"
61 #include "alloc-pool.h"
62 #include "pretty-print.h"
63 #include "params.h"
64 #include "dumpfile.h"
65 #include "builtins.h"
68 /* Functions and data structures for expanding case statements. */
70 /* Case label structure, used to hold info on labels within case
71 statements. We handle "range" labels; for a single-value label
72 as in C, the high and low limits are the same.
74 We start with a vector of case nodes sorted in ascending order, and
75 the default label as the last element in the vector. Before expanding
76 to RTL, we transform this vector into a list linked via the RIGHT
77 fields in the case_node struct. Nodes with higher case values are
78 later in the list.
80 Switch statements can be output in three forms. A branch table is
81 used if there are more than a few labels and the labels are dense
82 within the range between the smallest and largest case value. If a
83 branch table is used, no further manipulations are done with the case
84 node chain.
86 The alternative to the use of a branch table is to generate a series
87 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
88 and PARENT fields to hold a binary tree. Initially the tree is
89 totally unbalanced, with everything on the right. We balance the tree
90 with nodes on the left having lower case values than the parent
91 and nodes on the right having higher values. We then output the tree
92 in order.
94 For very small, suitable switch statements, we can generate a series
95 of simple bit test and branches instead. */
97 struct case_node
99 struct case_node *left; /* Left son in binary tree */
100 struct case_node *right; /* Right son in binary tree; also node chain */
101 struct case_node *parent; /* Parent of node in binary tree */
102 tree low; /* Lowest index value for this label */
103 tree high; /* Highest index value for this label */
104 tree code_label; /* Label to jump to when node matches */
105 int prob; /* Probability of taking this case. */
106 /* Probability of reaching subtree rooted at this node */
107 int subtree_prob;
110 typedef struct case_node case_node;
111 typedef struct case_node *case_node_ptr;
113 extern basic_block label_to_block_fn (struct function *, tree);
115 static bool check_unique_operand_names (tree, tree, tree);
116 static char *resolve_operand_name_1 (char *, tree, tree, tree);
117 static void balance_case_nodes (case_node_ptr *, case_node_ptr);
118 static int node_has_low_bound (case_node_ptr, tree);
119 static int node_has_high_bound (case_node_ptr, tree);
120 static int node_is_bounded (case_node_ptr, tree);
121 static void emit_case_nodes (rtx, case_node_ptr, rtx, int, tree);
123 /* Return the rtx-label that corresponds to a LABEL_DECL,
124 creating it if necessary. */
127 label_rtx (tree label)
129 gcc_assert (TREE_CODE (label) == LABEL_DECL);
131 if (!DECL_RTL_SET_P (label))
133 rtx_code_label *r = gen_label_rtx ();
134 SET_DECL_RTL (label, r);
135 if (FORCED_LABEL (label) || DECL_NONLOCAL (label))
136 LABEL_PRESERVE_P (r) = 1;
139 return DECL_RTL (label);
142 /* As above, but also put it on the forced-reference list of the
143 function that contains it. */
145 force_label_rtx (tree label)
147 rtx_insn *ref = as_a <rtx_insn *> (label_rtx (label));
148 tree function = decl_function_context (label);
150 gcc_assert (function);
152 forced_labels = gen_rtx_INSN_LIST (VOIDmode, ref, forced_labels);
153 return ref;
156 /* Add an unconditional jump to LABEL as the next sequential instruction. */
158 void
159 emit_jump (rtx label)
161 do_pending_stack_adjust ();
162 emit_jump_insn (gen_jump (label));
163 emit_barrier ();
166 /* Handle goto statements and the labels that they can go to. */
168 /* Specify the location in the RTL code of a label LABEL,
169 which is a LABEL_DECL tree node.
171 This is used for the kind of label that the user can jump to with a
172 goto statement, and for alternatives of a switch or case statement.
173 RTL labels generated for loops and conditionals don't go through here;
174 they are generated directly at the RTL level, by other functions below.
176 Note that this has nothing to do with defining label *names*.
177 Languages vary in how they do that and what that even means. */
179 void
180 expand_label (tree label)
182 rtx_insn *label_r = as_a <rtx_insn *> (label_rtx (label));
184 do_pending_stack_adjust ();
185 emit_label (label_r);
186 if (DECL_NAME (label))
187 LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label));
189 if (DECL_NONLOCAL (label))
191 expand_builtin_setjmp_receiver (NULL);
192 nonlocal_goto_handler_labels
193 = gen_rtx_INSN_LIST (VOIDmode, label_r,
194 nonlocal_goto_handler_labels);
197 if (FORCED_LABEL (label))
198 forced_labels = gen_rtx_INSN_LIST (VOIDmode, label_r, forced_labels);
200 if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
201 maybe_set_first_label_num (label_r);
204 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
205 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
206 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
207 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
208 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
209 constraint allows the use of a register operand. And, *IS_INOUT
210 will be true if the operand is read-write, i.e., if it is used as
211 an input as well as an output. If *CONSTRAINT_P is not in
212 canonical form, it will be made canonical. (Note that `+' will be
213 replaced with `=' as part of this process.)
215 Returns TRUE if all went well; FALSE if an error occurred. */
217 bool
218 parse_output_constraint (const char **constraint_p, int operand_num,
219 int ninputs, int noutputs, bool *allows_mem,
220 bool *allows_reg, bool *is_inout)
222 const char *constraint = *constraint_p;
223 const char *p;
225 /* Assume the constraint doesn't allow the use of either a register
226 or memory. */
227 *allows_mem = false;
228 *allows_reg = false;
230 /* Allow the `=' or `+' to not be at the beginning of the string,
231 since it wasn't explicitly documented that way, and there is a
232 large body of code that puts it last. Swap the character to
233 the front, so as not to uglify any place else. */
234 p = strchr (constraint, '=');
235 if (!p)
236 p = strchr (constraint, '+');
238 /* If the string doesn't contain an `=', issue an error
239 message. */
240 if (!p)
242 error ("output operand constraint lacks %<=%>");
243 return false;
246 /* If the constraint begins with `+', then the operand is both read
247 from and written to. */
248 *is_inout = (*p == '+');
250 /* Canonicalize the output constraint so that it begins with `='. */
251 if (p != constraint || *is_inout)
253 char *buf;
254 size_t c_len = strlen (constraint);
256 if (p != constraint)
257 warning (0, "output constraint %qc for operand %d "
258 "is not at the beginning",
259 *p, operand_num);
261 /* Make a copy of the constraint. */
262 buf = XALLOCAVEC (char, c_len + 1);
263 strcpy (buf, constraint);
264 /* Swap the first character and the `=' or `+'. */
265 buf[p - constraint] = buf[0];
266 /* Make sure the first character is an `='. (Until we do this,
267 it might be a `+'.) */
268 buf[0] = '=';
269 /* Replace the constraint with the canonicalized string. */
270 *constraint_p = ggc_alloc_string (buf, c_len);
271 constraint = *constraint_p;
274 /* Loop through the constraint string. */
275 for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p))
276 switch (*p)
278 case '+':
279 case '=':
280 error ("operand constraint contains incorrectly positioned "
281 "%<+%> or %<=%>");
282 return false;
284 case '%':
285 if (operand_num + 1 == ninputs + noutputs)
287 error ("%<%%%> constraint used with last operand");
288 return false;
290 break;
292 case '?': case '!': case '*': case '&': case '#':
293 case 'E': case 'F': case 'G': case 'H':
294 case 's': case 'i': case 'n':
295 case 'I': case 'J': case 'K': case 'L': case 'M':
296 case 'N': case 'O': case 'P': case ',':
297 break;
299 case '0': case '1': case '2': case '3': case '4':
300 case '5': case '6': case '7': case '8': case '9':
301 case '[':
302 error ("matching constraint not valid in output operand");
303 return false;
305 case '<': case '>':
306 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
307 excepting those that expand_call created. So match memory
308 and hope. */
309 *allows_mem = true;
310 break;
312 case 'g': case 'X':
313 *allows_reg = true;
314 *allows_mem = true;
315 break;
317 default:
318 if (!ISALPHA (*p))
319 break;
320 enum constraint_num cn = lookup_constraint (p);
321 if (reg_class_for_constraint (cn) != NO_REGS
322 || insn_extra_address_constraint (cn))
323 *allows_reg = true;
324 else if (insn_extra_memory_constraint (cn))
325 *allows_mem = true;
326 else
328 /* Otherwise we can't assume anything about the nature of
329 the constraint except that it isn't purely registers.
330 Treat it like "g" and hope for the best. */
331 *allows_reg = true;
332 *allows_mem = true;
334 break;
337 return true;
340 /* Similar, but for input constraints. */
342 bool
343 parse_input_constraint (const char **constraint_p, int input_num,
344 int ninputs, int noutputs, int ninout,
345 const char * const * constraints,
346 bool *allows_mem, bool *allows_reg)
348 const char *constraint = *constraint_p;
349 const char *orig_constraint = constraint;
350 size_t c_len = strlen (constraint);
351 size_t j;
352 bool saw_match = false;
354 /* Assume the constraint doesn't allow the use of either
355 a register or memory. */
356 *allows_mem = false;
357 *allows_reg = false;
359 /* Make sure constraint has neither `=', `+', nor '&'. */
361 for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
362 switch (constraint[j])
364 case '+': case '=': case '&':
365 if (constraint == orig_constraint)
367 error ("input operand constraint contains %qc", constraint[j]);
368 return false;
370 break;
372 case '%':
373 if (constraint == orig_constraint
374 && input_num + 1 == ninputs - ninout)
376 error ("%<%%%> constraint used with last operand");
377 return false;
379 break;
381 case '<': case '>':
382 case '?': case '!': case '*': case '#':
383 case 'E': case 'F': case 'G': case 'H':
384 case 's': case 'i': case 'n':
385 case 'I': case 'J': case 'K': case 'L': case 'M':
386 case 'N': case 'O': case 'P': case ',':
387 break;
389 /* Whether or not a numeric constraint allows a register is
390 decided by the matching constraint, and so there is no need
391 to do anything special with them. We must handle them in
392 the default case, so that we don't unnecessarily force
393 operands to memory. */
394 case '0': case '1': case '2': case '3': case '4':
395 case '5': case '6': case '7': case '8': case '9':
397 char *end;
398 unsigned long match;
400 saw_match = true;
402 match = strtoul (constraint + j, &end, 10);
403 if (match >= (unsigned long) noutputs)
405 error ("matching constraint references invalid operand number");
406 return false;
409 /* Try and find the real constraint for this dup. Only do this
410 if the matching constraint is the only alternative. */
411 if (*end == '\0'
412 && (j == 0 || (j == 1 && constraint[0] == '%')))
414 constraint = constraints[match];
415 *constraint_p = constraint;
416 c_len = strlen (constraint);
417 j = 0;
418 /* ??? At the end of the loop, we will skip the first part of
419 the matched constraint. This assumes not only that the
420 other constraint is an output constraint, but also that
421 the '=' or '+' come first. */
422 break;
424 else
425 j = end - constraint;
426 /* Anticipate increment at end of loop. */
427 j--;
429 /* Fall through. */
431 case 'g': case 'X':
432 *allows_reg = true;
433 *allows_mem = true;
434 break;
436 default:
437 if (! ISALPHA (constraint[j]))
439 error ("invalid punctuation %qc in constraint", constraint[j]);
440 return false;
442 enum constraint_num cn = lookup_constraint (constraint + j);
443 if (reg_class_for_constraint (cn) != NO_REGS
444 || insn_extra_address_constraint (cn))
445 *allows_reg = true;
446 else if (insn_extra_memory_constraint (cn))
447 *allows_mem = true;
448 else
450 /* Otherwise we can't assume anything about the nature of
451 the constraint except that it isn't purely registers.
452 Treat it like "g" and hope for the best. */
453 *allows_reg = true;
454 *allows_mem = true;
456 break;
459 if (saw_match && !*allows_reg)
460 warning (0, "matching constraint does not allow a register");
462 return true;
465 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
466 can be an asm-declared register. Called via walk_tree. */
468 static tree
469 decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED,
470 void *data)
472 tree decl = *declp;
473 const HARD_REG_SET *const regs = (const HARD_REG_SET *) data;
475 if (TREE_CODE (decl) == VAR_DECL)
477 if (DECL_HARD_REGISTER (decl)
478 && REG_P (DECL_RTL (decl))
479 && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
481 rtx reg = DECL_RTL (decl);
483 if (overlaps_hard_reg_set_p (*regs, GET_MODE (reg), REGNO (reg)))
484 return decl;
486 walk_subtrees = 0;
488 else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL)
489 walk_subtrees = 0;
490 return NULL_TREE;
493 /* If there is an overlap between *REGS and DECL, return the first overlap
494 found. */
495 tree
496 tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs)
498 return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL);
502 /* A subroutine of expand_asm_operands. Check that all operand names
503 are unique. Return true if so. We rely on the fact that these names
504 are identifiers, and so have been canonicalized by get_identifier,
505 so all we need are pointer comparisons. */
507 static bool
508 check_unique_operand_names (tree outputs, tree inputs, tree labels)
510 tree i, j, i_name = NULL_TREE;
512 for (i = outputs; i ; i = TREE_CHAIN (i))
514 i_name = TREE_PURPOSE (TREE_PURPOSE (i));
515 if (! i_name)
516 continue;
518 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
519 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
520 goto failure;
523 for (i = inputs; i ; i = TREE_CHAIN (i))
525 i_name = TREE_PURPOSE (TREE_PURPOSE (i));
526 if (! i_name)
527 continue;
529 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
530 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
531 goto failure;
532 for (j = outputs; j ; j = TREE_CHAIN (j))
533 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
534 goto failure;
537 for (i = labels; i ; i = TREE_CHAIN (i))
539 i_name = TREE_PURPOSE (i);
540 if (! i_name)
541 continue;
543 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
544 if (simple_cst_equal (i_name, TREE_PURPOSE (j)))
545 goto failure;
546 for (j = inputs; j ; j = TREE_CHAIN (j))
547 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
548 goto failure;
551 return true;
553 failure:
554 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name));
555 return false;
558 /* A subroutine of expand_asm_operands. Resolve the names of the operands
559 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
560 STRING and in the constraints to those numbers. */
562 tree
563 resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels)
565 char *buffer;
566 char *p;
567 const char *c;
568 tree t;
570 check_unique_operand_names (outputs, inputs, labels);
572 /* Substitute [<name>] in input constraint strings. There should be no
573 named operands in output constraints. */
574 for (t = inputs; t ; t = TREE_CHAIN (t))
576 c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
577 if (strchr (c, '[') != NULL)
579 p = buffer = xstrdup (c);
580 while ((p = strchr (p, '[')) != NULL)
581 p = resolve_operand_name_1 (p, outputs, inputs, NULL);
582 TREE_VALUE (TREE_PURPOSE (t))
583 = build_string (strlen (buffer), buffer);
584 free (buffer);
588 /* Now check for any needed substitutions in the template. */
589 c = TREE_STRING_POINTER (string);
590 while ((c = strchr (c, '%')) != NULL)
592 if (c[1] == '[')
593 break;
594 else if (ISALPHA (c[1]) && c[2] == '[')
595 break;
596 else
598 c += 1 + (c[1] == '%');
599 continue;
603 if (c)
605 /* OK, we need to make a copy so we can perform the substitutions.
606 Assume that we will not need extra space--we get to remove '['
607 and ']', which means we cannot have a problem until we have more
608 than 999 operands. */
609 buffer = xstrdup (TREE_STRING_POINTER (string));
610 p = buffer + (c - TREE_STRING_POINTER (string));
612 while ((p = strchr (p, '%')) != NULL)
614 if (p[1] == '[')
615 p += 1;
616 else if (ISALPHA (p[1]) && p[2] == '[')
617 p += 2;
618 else
620 p += 1 + (p[1] == '%');
621 continue;
624 p = resolve_operand_name_1 (p, outputs, inputs, labels);
627 string = build_string (strlen (buffer), buffer);
628 free (buffer);
631 return string;
634 /* A subroutine of resolve_operand_names. P points to the '[' for a
635 potential named operand of the form [<name>]. In place, replace
636 the name and brackets with a number. Return a pointer to the
637 balance of the string after substitution. */
639 static char *
640 resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels)
642 char *q;
643 int op;
644 tree t;
646 /* Collect the operand name. */
647 q = strchr (++p, ']');
648 if (!q)
650 error ("missing close brace for named operand");
651 return strchr (p, '\0');
653 *q = '\0';
655 /* Resolve the name to a number. */
656 for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
658 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
659 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
660 goto found;
662 for (t = inputs; t ; t = TREE_CHAIN (t), op++)
664 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
665 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
666 goto found;
668 for (t = labels; t ; t = TREE_CHAIN (t), op++)
670 tree name = TREE_PURPOSE (t);
671 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
672 goto found;
675 error ("undefined named operand %qs", identifier_to_locale (p));
676 op = 0;
678 found:
679 /* Replace the name with the number. Unfortunately, not all libraries
680 get the return value of sprintf correct, so search for the end of the
681 generated string by hand. */
682 sprintf (--p, "%d", op);
683 p = strchr (p, '\0');
685 /* Verify the no extra buffer space assumption. */
686 gcc_assert (p <= q);
688 /* Shift the rest of the buffer down to fill the gap. */
689 memmove (p, q + 1, strlen (q + 1) + 1);
691 return p;
695 /* Generate RTL to return directly from the current function.
696 (That is, we bypass any return value.) */
698 void
699 expand_naked_return (void)
701 rtx end_label;
703 clear_pending_stack_adjust ();
704 do_pending_stack_adjust ();
706 end_label = naked_return_label;
707 if (end_label == 0)
708 end_label = naked_return_label = gen_label_rtx ();
710 emit_jump (end_label);
713 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
714 is the probability of jumping to LABEL. */
715 static void
716 do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label,
717 int unsignedp, int prob)
719 gcc_assert (prob <= REG_BR_PROB_BASE);
720 do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
721 NULL_RTX, NULL_RTX, label, prob);
724 /* Do the insertion of a case label into case_list. The labels are
725 fed to us in descending order from the sorted vector of case labels used
726 in the tree part of the middle end. So the list we construct is
727 sorted in ascending order.
729 LABEL is the case label to be inserted. LOW and HIGH are the bounds
730 against which the index is compared to jump to LABEL and PROB is the
731 estimated probability LABEL is reached from the switch statement. */
733 static struct case_node *
734 add_case_node (struct case_node *head, tree low, tree high,
735 tree label, int prob, alloc_pool case_node_pool)
737 struct case_node *r;
739 gcc_checking_assert (low);
740 gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high)));
742 /* Add this label to the chain. */
743 r = (struct case_node *) pool_alloc (case_node_pool);
744 r->low = low;
745 r->high = high;
746 r->code_label = label;
747 r->parent = r->left = NULL;
748 r->prob = prob;
749 r->subtree_prob = prob;
750 r->right = head;
751 return r;
754 /* Dump ROOT, a list or tree of case nodes, to file. */
756 static void
757 dump_case_nodes (FILE *f, struct case_node *root,
758 int indent_step, int indent_level)
760 if (root == 0)
761 return;
762 indent_level++;
764 dump_case_nodes (f, root->left, indent_step, indent_level);
766 fputs (";; ", f);
767 fprintf (f, "%*s", indent_step * indent_level, "");
768 print_dec (root->low, f, TYPE_SIGN (TREE_TYPE (root->low)));
769 if (!tree_int_cst_equal (root->low, root->high))
771 fprintf (f, " ... ");
772 print_dec (root->high, f, TYPE_SIGN (TREE_TYPE (root->high)));
774 fputs ("\n", f);
776 dump_case_nodes (f, root->right, indent_step, indent_level);
779 #ifndef HAVE_casesi
780 #define HAVE_casesi 0
781 #endif
783 #ifndef HAVE_tablejump
784 #define HAVE_tablejump 0
785 #endif
787 /* Return the smallest number of different values for which it is best to use a
788 jump-table instead of a tree of conditional branches. */
790 static unsigned int
791 case_values_threshold (void)
793 unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
795 if (threshold == 0)
796 threshold = targetm.case_values_threshold ();
798 return threshold;
801 /* Return true if a switch should be expanded as a decision tree.
802 RANGE is the difference between highest and lowest case.
803 UNIQ is number of unique case node targets, not counting the default case.
804 COUNT is the number of comparisons needed, not counting the default case. */
806 static bool
807 expand_switch_as_decision_tree_p (tree range,
808 unsigned int uniq ATTRIBUTE_UNUSED,
809 unsigned int count)
811 int max_ratio;
813 /* If neither casesi or tablejump is available, or flag_jump_tables
814 over-ruled us, we really have no choice. */
815 if (!HAVE_casesi && !HAVE_tablejump)
816 return true;
817 if (!flag_jump_tables)
818 return true;
819 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
820 if (flag_pic)
821 return true;
822 #endif
824 /* If the switch is relatively small such that the cost of one
825 indirect jump on the target are higher than the cost of a
826 decision tree, go with the decision tree.
828 If range of values is much bigger than number of values,
829 or if it is too large to represent in a HOST_WIDE_INT,
830 make a sequence of conditional branches instead of a dispatch.
832 The definition of "much bigger" depends on whether we are
833 optimizing for size or for speed. If the former, the maximum
834 ratio range/count = 3, because this was found to be the optimal
835 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
836 10 is much older, and was probably selected after an extensive
837 benchmarking investigation on numerous platforms. Or maybe it
838 just made sense to someone at some point in the history of GCC,
839 who knows... */
840 max_ratio = optimize_insn_for_size_p () ? 3 : 10;
841 if (count < case_values_threshold ()
842 || ! tree_fits_uhwi_p (range)
843 || compare_tree_int (range, max_ratio * count) > 0)
844 return true;
846 return false;
849 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
850 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
851 DEFAULT_PROB is the estimated probability that it jumps to
852 DEFAULT_LABEL.
854 We generate a binary decision tree to select the appropriate target
855 code. This is done as follows:
857 If the index is a short or char that we do not have
858 an insn to handle comparisons directly, convert it to
859 a full integer now, rather than letting each comparison
860 generate the conversion.
862 Load the index into a register.
864 The list of cases is rearranged into a binary tree,
865 nearly optimal assuming equal probability for each case.
867 The tree is transformed into RTL, eliminating redundant
868 test conditions at the same time.
870 If program flow could reach the end of the decision tree
871 an unconditional jump to the default code is emitted.
873 The above process is unaware of the CFG. The caller has to fix up
874 the CFG itself. This is done in cfgexpand.c. */
876 static void
877 emit_case_decision_tree (tree index_expr, tree index_type,
878 struct case_node *case_list, rtx default_label,
879 int default_prob)
881 rtx index = expand_normal (index_expr);
883 if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
884 && ! have_insn_for (COMPARE, GET_MODE (index)))
886 int unsignedp = TYPE_UNSIGNED (index_type);
887 enum machine_mode wider_mode;
888 for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
889 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
890 if (have_insn_for (COMPARE, wider_mode))
892 index = convert_to_mode (wider_mode, index, unsignedp);
893 break;
897 do_pending_stack_adjust ();
899 if (MEM_P (index))
901 index = copy_to_reg (index);
902 if (TREE_CODE (index_expr) == SSA_NAME)
903 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr), index);
906 balance_case_nodes (&case_list, NULL);
908 if (dump_file && (dump_flags & TDF_DETAILS))
910 int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
911 fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
912 dump_case_nodes (dump_file, case_list, indent_step, 0);
915 emit_case_nodes (index, case_list, default_label, default_prob, index_type);
916 if (default_label)
917 emit_jump (default_label);
920 /* Return the sum of probabilities of outgoing edges of basic block BB. */
922 static int
923 get_outgoing_edge_probs (basic_block bb)
925 edge e;
926 edge_iterator ei;
927 int prob_sum = 0;
928 if (!bb)
929 return 0;
930 FOR_EACH_EDGE (e, ei, bb->succs)
931 prob_sum += e->probability;
932 return prob_sum;
935 /* Computes the conditional probability of jumping to a target if the branch
936 instruction is executed.
937 TARGET_PROB is the estimated probability of jumping to a target relative
938 to some basic block BB.
939 BASE_PROB is the probability of reaching the branch instruction relative
940 to the same basic block BB. */
942 static inline int
943 conditional_probability (int target_prob, int base_prob)
945 if (base_prob > 0)
947 gcc_assert (target_prob >= 0);
948 gcc_assert (target_prob <= base_prob);
949 return GCOV_COMPUTE_SCALE (target_prob, base_prob);
951 return -1;
954 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
955 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
956 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
957 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
959 First, a jump insn is emitted. First we try "casesi". If that
960 fails, try "tablejump". A target *must* have one of them (or both).
962 Then, a table with the target labels is emitted.
964 The process is unaware of the CFG. The caller has to fix up
965 the CFG itself. This is done in cfgexpand.c. */
967 static void
968 emit_case_dispatch_table (tree index_expr, tree index_type,
969 struct case_node *case_list, rtx default_label,
970 tree minval, tree maxval, tree range,
971 basic_block stmt_bb)
973 int i, ncases;
974 struct case_node *n;
975 rtx *labelvec;
976 rtx fallback_label = label_rtx (case_list->code_label);
977 rtx_code_label *table_label = gen_label_rtx ();
978 bool has_gaps = false;
979 edge default_edge = stmt_bb ? EDGE_SUCC (stmt_bb, 0) : NULL;
980 int default_prob = default_edge ? default_edge->probability : 0;
981 int base = get_outgoing_edge_probs (stmt_bb);
982 bool try_with_tablejump = false;
984 int new_default_prob = conditional_probability (default_prob,
985 base);
987 if (! try_casesi (index_type, index_expr, minval, range,
988 table_label, default_label, fallback_label,
989 new_default_prob))
991 /* Index jumptables from zero for suitable values of minval to avoid
992 a subtraction. For the rationale see:
993 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
994 if (optimize_insn_for_speed_p ()
995 && compare_tree_int (minval, 0) > 0
996 && compare_tree_int (minval, 3) < 0)
998 minval = build_int_cst (index_type, 0);
999 range = maxval;
1000 has_gaps = true;
1002 try_with_tablejump = true;
1005 /* Get table of labels to jump to, in order of case index. */
1007 ncases = tree_to_shwi (range) + 1;
1008 labelvec = XALLOCAVEC (rtx, ncases);
1009 memset (labelvec, 0, ncases * sizeof (rtx));
1011 for (n = case_list; n; n = n->right)
1013 /* Compute the low and high bounds relative to the minimum
1014 value since that should fit in a HOST_WIDE_INT while the
1015 actual values may not. */
1016 HOST_WIDE_INT i_low
1017 = tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
1018 n->low, minval));
1019 HOST_WIDE_INT i_high
1020 = tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
1021 n->high, minval));
1022 HOST_WIDE_INT i;
1024 for (i = i_low; i <= i_high; i ++)
1025 labelvec[i]
1026 = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
1029 /* Fill in the gaps with the default. We may have gaps at
1030 the beginning if we tried to avoid the minval subtraction,
1031 so substitute some label even if the default label was
1032 deemed unreachable. */
1033 if (!default_label)
1034 default_label = fallback_label;
1035 for (i = 0; i < ncases; i++)
1036 if (labelvec[i] == 0)
1038 has_gaps = true;
1039 labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
1042 if (has_gaps)
1044 /* There is at least one entry in the jump table that jumps
1045 to default label. The default label can either be reached
1046 through the indirect jump or the direct conditional jump
1047 before that. Split the probability of reaching the
1048 default label among these two jumps. */
1049 new_default_prob = conditional_probability (default_prob/2,
1050 base);
1051 default_prob /= 2;
1052 base -= default_prob;
1054 else
1056 base -= default_prob;
1057 default_prob = 0;
1060 if (default_edge)
1061 default_edge->probability = default_prob;
1063 /* We have altered the probability of the default edge. So the probabilities
1064 of all other edges need to be adjusted so that it sums up to
1065 REG_BR_PROB_BASE. */
1066 if (base)
1068 edge e;
1069 edge_iterator ei;
1070 FOR_EACH_EDGE (e, ei, stmt_bb->succs)
1071 e->probability = GCOV_COMPUTE_SCALE (e->probability, base);
1074 if (try_with_tablejump)
1076 bool ok = try_tablejump (index_type, index_expr, minval, range,
1077 table_label, default_label, new_default_prob);
1078 gcc_assert (ok);
1080 /* Output the table. */
1081 emit_label (table_label);
1083 if (CASE_VECTOR_PC_RELATIVE || flag_pic)
1084 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
1085 gen_rtx_LABEL_REF (Pmode,
1086 table_label),
1087 gen_rtvec_v (ncases, labelvec),
1088 const0_rtx, const0_rtx));
1089 else
1090 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
1091 gen_rtvec_v (ncases, labelvec)));
1093 /* Record no drop-through after the table. */
1094 emit_barrier ();
1097 /* Reset the aux field of all outgoing edges of basic block BB. */
1099 static inline void
1100 reset_out_edges_aux (basic_block bb)
1102 edge e;
1103 edge_iterator ei;
1104 FOR_EACH_EDGE (e, ei, bb->succs)
1105 e->aux = (void *)0;
1108 /* Compute the number of case labels that correspond to each outgoing edge of
1109 STMT. Record this information in the aux field of the edge. */
1111 static inline void
1112 compute_cases_per_edge (gimple stmt)
1114 basic_block bb = gimple_bb (stmt);
1115 reset_out_edges_aux (bb);
1116 int ncases = gimple_switch_num_labels (stmt);
1117 for (int i = ncases - 1; i >= 1; --i)
1119 tree elt = gimple_switch_label (stmt, i);
1120 tree lab = CASE_LABEL (elt);
1121 basic_block case_bb = label_to_block_fn (cfun, lab);
1122 edge case_edge = find_edge (bb, case_bb);
1123 case_edge->aux = (void *)((intptr_t)(case_edge->aux) + 1);
1127 /* Terminate a case (Pascal/Ada) or switch (C) statement
1128 in which ORIG_INDEX is the expression to be tested.
1129 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
1130 type as given in the source before any compiler conversions.
1131 Generate the code to test it and jump to the right place. */
1133 void
1134 expand_case (gimple stmt)
1136 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
1137 rtx default_label = NULL_RTX;
1138 unsigned int count, uniq;
1139 int i;
1140 int ncases = gimple_switch_num_labels (stmt);
1141 tree index_expr = gimple_switch_index (stmt);
1142 tree index_type = TREE_TYPE (index_expr);
1143 tree elt;
1144 basic_block bb = gimple_bb (stmt);
1146 /* A list of case labels; it is first built as a list and it may then
1147 be rearranged into a nearly balanced binary tree. */
1148 struct case_node *case_list = 0;
1150 /* A pool for case nodes. */
1151 alloc_pool case_node_pool;
1153 /* An ERROR_MARK occurs for various reasons including invalid data type.
1154 ??? Can this still happen, with GIMPLE and all? */
1155 if (index_type == error_mark_node)
1156 return;
1158 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
1159 expressions being INTEGER_CST. */
1160 gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
1162 case_node_pool = create_alloc_pool ("struct case_node pool",
1163 sizeof (struct case_node),
1164 100);
1166 do_pending_stack_adjust ();
1168 /* Find the default case target label. */
1169 default_label = label_rtx (CASE_LABEL (gimple_switch_default_label (stmt)));
1170 edge default_edge = EDGE_SUCC (bb, 0);
1171 int default_prob = default_edge->probability;
1173 /* Get upper and lower bounds of case values. */
1174 elt = gimple_switch_label (stmt, 1);
1175 minval = fold_convert (index_type, CASE_LOW (elt));
1176 elt = gimple_switch_label (stmt, ncases - 1);
1177 if (CASE_HIGH (elt))
1178 maxval = fold_convert (index_type, CASE_HIGH (elt));
1179 else
1180 maxval = fold_convert (index_type, CASE_LOW (elt));
1182 /* Compute span of values. */
1183 range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
1185 /* Listify the labels queue and gather some numbers to decide
1186 how to expand this switch(). */
1187 uniq = 0;
1188 count = 0;
1189 hash_set<tree> seen_labels;
1190 compute_cases_per_edge (stmt);
1192 for (i = ncases - 1; i >= 1; --i)
1194 elt = gimple_switch_label (stmt, i);
1195 tree low = CASE_LOW (elt);
1196 gcc_assert (low);
1197 tree high = CASE_HIGH (elt);
1198 gcc_assert (! high || tree_int_cst_lt (low, high));
1199 tree lab = CASE_LABEL (elt);
1201 /* Count the elements.
1202 A range counts double, since it requires two compares. */
1203 count++;
1204 if (high)
1205 count++;
1207 /* If we have not seen this label yet, then increase the
1208 number of unique case node targets seen. */
1209 if (!seen_labels.add (lab))
1210 uniq++;
1212 /* The bounds on the case range, LOW and HIGH, have to be converted
1213 to case's index type TYPE. Note that the original type of the
1214 case index in the source code is usually "lost" during
1215 gimplification due to type promotion, but the case labels retain the
1216 original type. Make sure to drop overflow flags. */
1217 low = fold_convert (index_type, low);
1218 if (TREE_OVERFLOW (low))
1219 low = wide_int_to_tree (index_type, low);
1221 /* The canonical from of a case label in GIMPLE is that a simple case
1222 has an empty CASE_HIGH. For the casesi and tablejump expanders,
1223 the back ends want simple cases to have high == low. */
1224 if (! high)
1225 high = low;
1226 high = fold_convert (index_type, high);
1227 if (TREE_OVERFLOW (high))
1228 high = wide_int_to_tree (index_type, high);
1230 basic_block case_bb = label_to_block_fn (cfun, lab);
1231 edge case_edge = find_edge (bb, case_bb);
1232 case_list = add_case_node (
1233 case_list, low, high, lab,
1234 case_edge->probability / (intptr_t)(case_edge->aux),
1235 case_node_pool);
1237 reset_out_edges_aux (bb);
1239 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
1240 destination, such as one with a default case only.
1241 It also removes cases that are out of range for the switch
1242 type, so we should never get a zero here. */
1243 gcc_assert (count > 0);
1245 rtx_insn *before_case = get_last_insn ();
1247 /* Decide how to expand this switch.
1248 The two options at this point are a dispatch table (casesi or
1249 tablejump) or a decision tree. */
1251 if (expand_switch_as_decision_tree_p (range, uniq, count))
1252 emit_case_decision_tree (index_expr, index_type,
1253 case_list, default_label,
1254 default_prob);
1255 else
1256 emit_case_dispatch_table (index_expr, index_type,
1257 case_list, default_label,
1258 minval, maxval, range, bb);
1260 reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
1262 free_temp_slots ();
1263 free_alloc_pool (case_node_pool);
1266 /* Expand the dispatch to a short decrement chain if there are few cases
1267 to dispatch to. Likewise if neither casesi nor tablejump is available,
1268 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
1269 tablejump. The index mode is always the mode of integer_type_node.
1270 Trap if no case matches the index.
1272 DISPATCH_INDEX is the index expression to switch on. It should be a
1273 memory or register operand.
1275 DISPATCH_TABLE is a set of case labels. The set should be sorted in
1276 ascending order, be contiguous, starting with value 0, and contain only
1277 single-valued case labels. */
1279 void
1280 expand_sjlj_dispatch_table (rtx dispatch_index,
1281 vec<tree> dispatch_table)
1283 tree index_type = integer_type_node;
1284 enum machine_mode index_mode = TYPE_MODE (index_type);
1286 int ncases = dispatch_table.length ();
1288 do_pending_stack_adjust ();
1289 rtx_insn *before_case = get_last_insn ();
1291 /* Expand as a decrement-chain if there are 5 or fewer dispatch
1292 labels. This covers more than 98% of the cases in libjava,
1293 and seems to be a reasonable compromise between the "old way"
1294 of expanding as a decision tree or dispatch table vs. the "new
1295 way" with decrement chain or dispatch table. */
1296 if (dispatch_table.length () <= 5
1297 || (!HAVE_casesi && !HAVE_tablejump)
1298 || !flag_jump_tables)
1300 /* Expand the dispatch as a decrement chain:
1302 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1306 if (index == 0) do_0; else index--;
1307 if (index == 0) do_1; else index--;
1309 if (index == 0) do_N; else index--;
1311 This is more efficient than a dispatch table on most machines.
1312 The last "index--" is redundant but the code is trivially dead
1313 and will be cleaned up by later passes. */
1314 rtx index = copy_to_mode_reg (index_mode, dispatch_index);
1315 rtx zero = CONST0_RTX (index_mode);
1316 for (int i = 0; i < ncases; i++)
1318 tree elt = dispatch_table[i];
1319 rtx lab = label_rtx (CASE_LABEL (elt));
1320 do_jump_if_equal (index_mode, index, zero, lab, 0, -1);
1321 force_expand_binop (index_mode, sub_optab,
1322 index, CONST1_RTX (index_mode),
1323 index, 0, OPTAB_DIRECT);
1326 else
1328 /* Similar to expand_case, but much simpler. */
1329 struct case_node *case_list = 0;
1330 alloc_pool case_node_pool = create_alloc_pool ("struct sjlj_case pool",
1331 sizeof (struct case_node),
1332 ncases);
1333 tree index_expr = make_tree (index_type, dispatch_index);
1334 tree minval = build_int_cst (index_type, 0);
1335 tree maxval = CASE_LOW (dispatch_table.last ());
1336 tree range = maxval;
1337 rtx_code_label *default_label = gen_label_rtx ();
1339 for (int i = ncases - 1; i >= 0; --i)
1341 tree elt = dispatch_table[i];
1342 tree low = CASE_LOW (elt);
1343 tree lab = CASE_LABEL (elt);
1344 case_list = add_case_node (case_list, low, low, lab, 0, case_node_pool);
1347 emit_case_dispatch_table (index_expr, index_type,
1348 case_list, default_label,
1349 minval, maxval, range,
1350 BLOCK_FOR_INSN (before_case));
1351 emit_label (default_label);
1352 free_alloc_pool (case_node_pool);
1355 /* Dispatching something not handled? Trap! */
1356 expand_builtin_trap ();
1358 reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
1360 free_temp_slots ();
1364 /* Take an ordered list of case nodes
1365 and transform them into a near optimal binary tree,
1366 on the assumption that any target code selection value is as
1367 likely as any other.
1369 The transformation is performed by splitting the ordered
1370 list into two equal sections plus a pivot. The parts are
1371 then attached to the pivot as left and right branches. Each
1372 branch is then transformed recursively. */
1374 static void
1375 balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
1377 case_node_ptr np;
1379 np = *head;
1380 if (np)
1382 int i = 0;
1383 int ranges = 0;
1384 case_node_ptr *npp;
1385 case_node_ptr left;
1387 /* Count the number of entries on branch. Also count the ranges. */
1389 while (np)
1391 if (!tree_int_cst_equal (np->low, np->high))
1392 ranges++;
1394 i++;
1395 np = np->right;
1398 if (i > 2)
1400 /* Split this list if it is long enough for that to help. */
1401 npp = head;
1402 left = *npp;
1404 /* If there are just three nodes, split at the middle one. */
1405 if (i == 3)
1406 npp = &(*npp)->right;
1407 else
1409 /* Find the place in the list that bisects the list's total cost,
1410 where ranges count as 2.
1411 Here I gets half the total cost. */
1412 i = (i + ranges + 1) / 2;
1413 while (1)
1415 /* Skip nodes while their cost does not reach that amount. */
1416 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
1417 i--;
1418 i--;
1419 if (i <= 0)
1420 break;
1421 npp = &(*npp)->right;
1424 *head = np = *npp;
1425 *npp = 0;
1426 np->parent = parent;
1427 np->left = left;
1429 /* Optimize each of the two split parts. */
1430 balance_case_nodes (&np->left, np);
1431 balance_case_nodes (&np->right, np);
1432 np->subtree_prob = np->prob;
1433 np->subtree_prob += np->left->subtree_prob;
1434 np->subtree_prob += np->right->subtree_prob;
1436 else
1438 /* Else leave this branch as one level,
1439 but fill in `parent' fields. */
1440 np = *head;
1441 np->parent = parent;
1442 np->subtree_prob = np->prob;
1443 for (; np->right; np = np->right)
1445 np->right->parent = np;
1446 (*head)->subtree_prob += np->right->subtree_prob;
1452 /* Search the parent sections of the case node tree
1453 to see if a test for the lower bound of NODE would be redundant.
1454 INDEX_TYPE is the type of the index expression.
1456 The instructions to generate the case decision tree are
1457 output in the same order as nodes are processed so it is
1458 known that if a parent node checks the range of the current
1459 node minus one that the current node is bounded at its lower
1460 span. Thus the test would be redundant. */
1462 static int
1463 node_has_low_bound (case_node_ptr node, tree index_type)
1465 tree low_minus_one;
1466 case_node_ptr pnode;
1468 /* If the lower bound of this node is the lowest value in the index type,
1469 we need not test it. */
1471 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
1472 return 1;
1474 /* If this node has a left branch, the value at the left must be less
1475 than that at this node, so it cannot be bounded at the bottom and
1476 we need not bother testing any further. */
1478 if (node->left)
1479 return 0;
1481 low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low),
1482 node->low,
1483 build_int_cst (TREE_TYPE (node->low), 1));
1485 /* If the subtraction above overflowed, we can't verify anything.
1486 Otherwise, look for a parent that tests our value - 1. */
1488 if (! tree_int_cst_lt (low_minus_one, node->low))
1489 return 0;
1491 for (pnode = node->parent; pnode; pnode = pnode->parent)
1492 if (tree_int_cst_equal (low_minus_one, pnode->high))
1493 return 1;
1495 return 0;
1498 /* Search the parent sections of the case node tree
1499 to see if a test for the upper bound of NODE would be redundant.
1500 INDEX_TYPE is the type of the index expression.
1502 The instructions to generate the case decision tree are
1503 output in the same order as nodes are processed so it is
1504 known that if a parent node checks the range of the current
1505 node plus one that the current node is bounded at its upper
1506 span. Thus the test would be redundant. */
1508 static int
1509 node_has_high_bound (case_node_ptr node, tree index_type)
1511 tree high_plus_one;
1512 case_node_ptr pnode;
1514 /* If there is no upper bound, obviously no test is needed. */
1516 if (TYPE_MAX_VALUE (index_type) == NULL)
1517 return 1;
1519 /* If the upper bound of this node is the highest value in the type
1520 of the index expression, we need not test against it. */
1522 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
1523 return 1;
1525 /* If this node has a right branch, the value at the right must be greater
1526 than that at this node, so it cannot be bounded at the top and
1527 we need not bother testing any further. */
1529 if (node->right)
1530 return 0;
1532 high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high),
1533 node->high,
1534 build_int_cst (TREE_TYPE (node->high), 1));
1536 /* If the addition above overflowed, we can't verify anything.
1537 Otherwise, look for a parent that tests our value + 1. */
1539 if (! tree_int_cst_lt (node->high, high_plus_one))
1540 return 0;
1542 for (pnode = node->parent; pnode; pnode = pnode->parent)
1543 if (tree_int_cst_equal (high_plus_one, pnode->low))
1544 return 1;
1546 return 0;
1549 /* Search the parent sections of the
1550 case node tree to see if both tests for the upper and lower
1551 bounds of NODE would be redundant. */
1553 static int
1554 node_is_bounded (case_node_ptr node, tree index_type)
1556 return (node_has_low_bound (node, index_type)
1557 && node_has_high_bound (node, index_type));
1561 /* Emit step-by-step code to select a case for the value of INDEX.
1562 The thus generated decision tree follows the form of the
1563 case-node binary tree NODE, whose nodes represent test conditions.
1564 INDEX_TYPE is the type of the index of the switch.
1566 Care is taken to prune redundant tests from the decision tree
1567 by detecting any boundary conditions already checked by
1568 emitted rtx. (See node_has_high_bound, node_has_low_bound
1569 and node_is_bounded, above.)
1571 Where the test conditions can be shown to be redundant we emit
1572 an unconditional jump to the target code. As a further
1573 optimization, the subordinates of a tree node are examined to
1574 check for bounded nodes. In this case conditional and/or
1575 unconditional jumps as a result of the boundary check for the
1576 current node are arranged to target the subordinates associated
1577 code for out of bound conditions on the current node.
1579 We can assume that when control reaches the code generated here,
1580 the index value has already been compared with the parents
1581 of this node, and determined to be on the same side of each parent
1582 as this node is. Thus, if this node tests for the value 51,
1583 and a parent tested for 52, we don't need to consider
1584 the possibility of a value greater than 51. If another parent
1585 tests for the value 50, then this node need not test anything. */
1587 static void
1588 emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
1589 int default_prob, tree index_type)
1591 /* If INDEX has an unsigned type, we must make unsigned branches. */
1592 int unsignedp = TYPE_UNSIGNED (index_type);
1593 int probability;
1594 int prob = node->prob, subtree_prob = node->subtree_prob;
1595 enum machine_mode mode = GET_MODE (index);
1596 enum machine_mode imode = TYPE_MODE (index_type);
1598 /* Handle indices detected as constant during RTL expansion. */
1599 if (mode == VOIDmode)
1600 mode = imode;
1602 /* See if our parents have already tested everything for us.
1603 If they have, emit an unconditional jump for this node. */
1604 if (node_is_bounded (node, index_type))
1605 emit_jump (label_rtx (node->code_label));
1607 else if (tree_int_cst_equal (node->low, node->high))
1609 probability = conditional_probability (prob, subtree_prob + default_prob);
1610 /* Node is single valued. First see if the index expression matches
1611 this node and then check our children, if any. */
1612 do_jump_if_equal (mode, index,
1613 convert_modes (mode, imode,
1614 expand_normal (node->low),
1615 unsignedp),
1616 label_rtx (node->code_label), unsignedp, probability);
1617 /* Since this case is taken at this point, reduce its weight from
1618 subtree_weight. */
1619 subtree_prob -= prob;
1620 if (node->right != 0 && node->left != 0)
1622 /* This node has children on both sides.
1623 Dispatch to one side or the other
1624 by comparing the index value with this node's value.
1625 If one subtree is bounded, check that one first,
1626 so we can avoid real branches in the tree. */
1628 if (node_is_bounded (node->right, index_type))
1630 probability = conditional_probability (
1631 node->right->prob,
1632 subtree_prob + default_prob);
1633 emit_cmp_and_jump_insns (index,
1634 convert_modes
1635 (mode, imode,
1636 expand_normal (node->high),
1637 unsignedp),
1638 GT, NULL_RTX, mode, unsignedp,
1639 label_rtx (node->right->code_label),
1640 probability);
1641 emit_case_nodes (index, node->left, default_label, default_prob,
1642 index_type);
1645 else if (node_is_bounded (node->left, index_type))
1647 probability = conditional_probability (
1648 node->left->prob,
1649 subtree_prob + default_prob);
1650 emit_cmp_and_jump_insns (index,
1651 convert_modes
1652 (mode, imode,
1653 expand_normal (node->high),
1654 unsignedp),
1655 LT, NULL_RTX, mode, unsignedp,
1656 label_rtx (node->left->code_label),
1657 probability);
1658 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1661 /* If both children are single-valued cases with no
1662 children, finish up all the work. This way, we can save
1663 one ordered comparison. */
1664 else if (tree_int_cst_equal (node->right->low, node->right->high)
1665 && node->right->left == 0
1666 && node->right->right == 0
1667 && tree_int_cst_equal (node->left->low, node->left->high)
1668 && node->left->left == 0
1669 && node->left->right == 0)
1671 /* Neither node is bounded. First distinguish the two sides;
1672 then emit the code for one side at a time. */
1674 /* See if the value matches what the right hand side
1675 wants. */
1676 probability = conditional_probability (
1677 node->right->prob,
1678 subtree_prob + default_prob);
1679 do_jump_if_equal (mode, index,
1680 convert_modes (mode, imode,
1681 expand_normal (node->right->low),
1682 unsignedp),
1683 label_rtx (node->right->code_label),
1684 unsignedp, probability);
1686 /* See if the value matches what the left hand side
1687 wants. */
1688 probability = conditional_probability (
1689 node->left->prob,
1690 subtree_prob + default_prob);
1691 do_jump_if_equal (mode, index,
1692 convert_modes (mode, imode,
1693 expand_normal (node->left->low),
1694 unsignedp),
1695 label_rtx (node->left->code_label),
1696 unsignedp, probability);
1699 else
1701 /* Neither node is bounded. First distinguish the two sides;
1702 then emit the code for one side at a time. */
1704 tree test_label
1705 = build_decl (curr_insn_location (),
1706 LABEL_DECL, NULL_TREE, NULL_TREE);
1708 /* The default label could be reached either through the right
1709 subtree or the left subtree. Divide the probability
1710 equally. */
1711 probability = conditional_probability (
1712 node->right->subtree_prob + default_prob/2,
1713 subtree_prob + default_prob);
1714 /* See if the value is on the right. */
1715 emit_cmp_and_jump_insns (index,
1716 convert_modes
1717 (mode, imode,
1718 expand_normal (node->high),
1719 unsignedp),
1720 GT, NULL_RTX, mode, unsignedp,
1721 label_rtx (test_label),
1722 probability);
1723 default_prob /= 2;
1725 /* Value must be on the left.
1726 Handle the left-hand subtree. */
1727 emit_case_nodes (index, node->left, default_label, default_prob, index_type);
1728 /* If left-hand subtree does nothing,
1729 go to default. */
1730 if (default_label)
1731 emit_jump (default_label);
1733 /* Code branches here for the right-hand subtree. */
1734 expand_label (test_label);
1735 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1739 else if (node->right != 0 && node->left == 0)
1741 /* Here we have a right child but no left so we issue a conditional
1742 branch to default and process the right child.
1744 Omit the conditional branch to default if the right child
1745 does not have any children and is single valued; it would
1746 cost too much space to save so little time. */
1748 if (node->right->right || node->right->left
1749 || !tree_int_cst_equal (node->right->low, node->right->high))
1751 if (!node_has_low_bound (node, index_type))
1753 probability = conditional_probability (
1754 default_prob/2,
1755 subtree_prob + default_prob);
1756 emit_cmp_and_jump_insns (index,
1757 convert_modes
1758 (mode, imode,
1759 expand_normal (node->high),
1760 unsignedp),
1761 LT, NULL_RTX, mode, unsignedp,
1762 default_label,
1763 probability);
1764 default_prob /= 2;
1767 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1769 else
1771 probability = conditional_probability (
1772 node->right->subtree_prob,
1773 subtree_prob + default_prob);
1774 /* We cannot process node->right normally
1775 since we haven't ruled out the numbers less than
1776 this node's value. So handle node->right explicitly. */
1777 do_jump_if_equal (mode, index,
1778 convert_modes
1779 (mode, imode,
1780 expand_normal (node->right->low),
1781 unsignedp),
1782 label_rtx (node->right->code_label), unsignedp, probability);
1786 else if (node->right == 0 && node->left != 0)
1788 /* Just one subtree, on the left. */
1789 if (node->left->left || node->left->right
1790 || !tree_int_cst_equal (node->left->low, node->left->high))
1792 if (!node_has_high_bound (node, index_type))
1794 probability = conditional_probability (
1795 default_prob/2,
1796 subtree_prob + default_prob);
1797 emit_cmp_and_jump_insns (index,
1798 convert_modes
1799 (mode, imode,
1800 expand_normal (node->high),
1801 unsignedp),
1802 GT, NULL_RTX, mode, unsignedp,
1803 default_label,
1804 probability);
1805 default_prob /= 2;
1808 emit_case_nodes (index, node->left, default_label,
1809 default_prob, index_type);
1811 else
1813 probability = conditional_probability (
1814 node->left->subtree_prob,
1815 subtree_prob + default_prob);
1816 /* We cannot process node->left normally
1817 since we haven't ruled out the numbers less than
1818 this node's value. So handle node->left explicitly. */
1819 do_jump_if_equal (mode, index,
1820 convert_modes
1821 (mode, imode,
1822 expand_normal (node->left->low),
1823 unsignedp),
1824 label_rtx (node->left->code_label), unsignedp, probability);
1828 else
1830 /* Node is a range. These cases are very similar to those for a single
1831 value, except that we do not start by testing whether this node
1832 is the one to branch to. */
1834 if (node->right != 0 && node->left != 0)
1836 /* Node has subtrees on both sides.
1837 If the right-hand subtree is bounded,
1838 test for it first, since we can go straight there.
1839 Otherwise, we need to make a branch in the control structure,
1840 then handle the two subtrees. */
1841 tree test_label = 0;
1843 if (node_is_bounded (node->right, index_type))
1845 /* Right hand node is fully bounded so we can eliminate any
1846 testing and branch directly to the target code. */
1847 probability = conditional_probability (
1848 node->right->subtree_prob,
1849 subtree_prob + default_prob);
1850 emit_cmp_and_jump_insns (index,
1851 convert_modes
1852 (mode, imode,
1853 expand_normal (node->high),
1854 unsignedp),
1855 GT, NULL_RTX, mode, unsignedp,
1856 label_rtx (node->right->code_label),
1857 probability);
1859 else
1861 /* Right hand node requires testing.
1862 Branch to a label where we will handle it later. */
1864 test_label = build_decl (curr_insn_location (),
1865 LABEL_DECL, NULL_TREE, NULL_TREE);
1866 probability = conditional_probability (
1867 node->right->subtree_prob + default_prob/2,
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 (test_label),
1876 probability);
1877 default_prob /= 2;
1880 /* Value belongs to this node or to the left-hand subtree. */
1882 probability = conditional_probability (
1883 prob,
1884 subtree_prob + default_prob);
1885 emit_cmp_and_jump_insns (index,
1886 convert_modes
1887 (mode, imode,
1888 expand_normal (node->low),
1889 unsignedp),
1890 GE, NULL_RTX, mode, unsignedp,
1891 label_rtx (node->code_label),
1892 probability);
1894 /* Handle the left-hand subtree. */
1895 emit_case_nodes (index, node->left, default_label, default_prob, index_type);
1897 /* If right node had to be handled later, do that now. */
1899 if (test_label)
1901 /* If the left-hand subtree fell through,
1902 don't let it fall into the right-hand subtree. */
1903 if (default_label)
1904 emit_jump (default_label);
1906 expand_label (test_label);
1907 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1911 else if (node->right != 0 && node->left == 0)
1913 /* Deal with values to the left of this node,
1914 if they are possible. */
1915 if (!node_has_low_bound (node, index_type))
1917 probability = conditional_probability (
1918 default_prob/2,
1919 subtree_prob + default_prob);
1920 emit_cmp_and_jump_insns (index,
1921 convert_modes
1922 (mode, imode,
1923 expand_normal (node->low),
1924 unsignedp),
1925 LT, NULL_RTX, mode, unsignedp,
1926 default_label,
1927 probability);
1928 default_prob /= 2;
1931 /* Value belongs to this node or to the right-hand subtree. */
1933 probability = conditional_probability (
1934 prob,
1935 subtree_prob + default_prob);
1936 emit_cmp_and_jump_insns (index,
1937 convert_modes
1938 (mode, imode,
1939 expand_normal (node->high),
1940 unsignedp),
1941 LE, NULL_RTX, mode, unsignedp,
1942 label_rtx (node->code_label),
1943 probability);
1945 emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1948 else if (node->right == 0 && node->left != 0)
1950 /* Deal with values to the right of this node,
1951 if they are possible. */
1952 if (!node_has_high_bound (node, index_type))
1954 probability = conditional_probability (
1955 default_prob/2,
1956 subtree_prob + default_prob);
1957 emit_cmp_and_jump_insns (index,
1958 convert_modes
1959 (mode, imode,
1960 expand_normal (node->high),
1961 unsignedp),
1962 GT, NULL_RTX, mode, unsignedp,
1963 default_label,
1964 probability);
1965 default_prob /= 2;
1968 /* Value belongs to this node or to the left-hand subtree. */
1970 probability = conditional_probability (
1971 prob,
1972 subtree_prob + default_prob);
1973 emit_cmp_and_jump_insns (index,
1974 convert_modes
1975 (mode, imode,
1976 expand_normal (node->low),
1977 unsignedp),
1978 GE, NULL_RTX, mode, unsignedp,
1979 label_rtx (node->code_label),
1980 probability);
1982 emit_case_nodes (index, node->left, default_label, default_prob, index_type);
1985 else
1987 /* Node has no children so we check low and high bounds to remove
1988 redundant tests. Only one of the bounds can exist,
1989 since otherwise this node is bounded--a case tested already. */
1990 int high_bound = node_has_high_bound (node, index_type);
1991 int low_bound = node_has_low_bound (node, index_type);
1993 if (!high_bound && low_bound)
1995 probability = conditional_probability (
1996 default_prob,
1997 subtree_prob + default_prob);
1998 emit_cmp_and_jump_insns (index,
1999 convert_modes
2000 (mode, imode,
2001 expand_normal (node->high),
2002 unsignedp),
2003 GT, NULL_RTX, mode, unsignedp,
2004 default_label,
2005 probability);
2008 else if (!low_bound && high_bound)
2010 probability = conditional_probability (
2011 default_prob,
2012 subtree_prob + default_prob);
2013 emit_cmp_and_jump_insns (index,
2014 convert_modes
2015 (mode, imode,
2016 expand_normal (node->low),
2017 unsignedp),
2018 LT, NULL_RTX, mode, unsignedp,
2019 default_label,
2020 probability);
2022 else if (!low_bound && !high_bound)
2024 /* Widen LOW and HIGH to the same width as INDEX. */
2025 tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
2026 tree low = build1 (CONVERT_EXPR, type, node->low);
2027 tree high = build1 (CONVERT_EXPR, type, node->high);
2028 rtx low_rtx, new_index, new_bound;
2030 /* Instead of doing two branches, emit one unsigned branch for
2031 (index-low) > (high-low). */
2032 low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL);
2033 new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
2034 NULL_RTX, unsignedp,
2035 OPTAB_WIDEN);
2036 new_bound = expand_expr (fold_build2 (MINUS_EXPR, type,
2037 high, low),
2038 NULL_RTX, mode, EXPAND_NORMAL);
2040 probability = conditional_probability (
2041 default_prob,
2042 subtree_prob + default_prob);
2043 emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
2044 mode, 1, default_label, probability);
2047 emit_jump (label_rtx (node->code_label));