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