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