1 /* Expands front end tree to back end RTL for GCC 2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 3 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 4 2010 Free Software Foundation, Inc. 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free 10 Software Foundation; either version 3, or (at your option) any later 11 version. 12 13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16 for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 /* This file handles the generation of rtl code from tree structure 23 above the level of expressions, using subroutines in exp*.c and emit-rtl.c. 24 The functions whose names start with `expand_' are called by the 25 expander to generate RTL instructions for various kinds of constructs. */ 26 27 #include "config.h" 28 #include "system.h" 29 #include "coretypes.h" 30 #include "tm.h" 31 32 #include "rtl.h" 33 #include "hard-reg-set.h" 34 #include "tree.h" 35 #include "tm_p.h" 36 #include "flags.h" 37 #include "except.h" 38 #include "function.h" 39 #include "insn-config.h" 40 #include "expr.h" 41 #include "libfuncs.h" 42 #include "recog.h" 43 #include "machmode.h" 44 #include "toplev.h" 45 #include "output.h" 46 #include "ggc.h" 47 #include "langhooks.h" 48 #include "predict.h" 49 #include "optabs.h" 50 #include "target.h" 51 #include "gimple.h" 52 #include "regs.h" 53 #include "alloc-pool.h" 54 #include "pretty-print.h" 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 }; 94 95 typedef struct case_node case_node; 96 typedef struct case_node *case_node_ptr; 97 98 /* These are used by estimate_case_costs and balance_case_nodes. */ 99 100 /* This must be a signed type, and non-ANSI compilers lack signed char. */ 101 static short cost_table_[129]; 102 static int use_cost_table; 103 static int cost_table_initialized; 104 105 /* Special care is needed because we allow -1, but TREE_INT_CST_LOW 106 is unsigned. */ 107 #define COST_TABLE(I) cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)] 108 109 static int n_occurrences (int, const char *); 110 static bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *); 111 static void expand_nl_goto_receiver (void); 112 static bool check_operand_nalternatives (tree, tree); 113 static bool check_unique_operand_names (tree, tree, tree); 114 static char *resolve_operand_name_1 (char *, tree, tree, tree); 115 static void expand_null_return_1 (void); 116 static void expand_value_return (rtx); 117 static int estimate_case_costs (case_node_ptr); 118 static bool lshift_cheap_p (void); 119 static int case_bit_test_cmp (const void *, const void *); 120 static void emit_case_bit_tests (tree, tree, tree, tree, case_node_ptr, rtx); 121 static void balance_case_nodes (case_node_ptr *, case_node_ptr); 122 static int node_has_low_bound (case_node_ptr, tree); 123 static int node_has_high_bound (case_node_ptr, tree); 124 static int node_is_bounded (case_node_ptr, tree); 125 static void emit_case_nodes (rtx, case_node_ptr, rtx, tree); 126 static struct case_node *add_case_node (struct case_node *, tree, 127 tree, tree, tree, alloc_pool); 128 129 130 /* Return the rtx-label that corresponds to a LABEL_DECL, 131 creating it if necessary. */ 132 133 rtx 134 label_rtx (tree label) 135 { 136 gcc_assert (TREE_CODE (label) == LABEL_DECL); 137 138 if (!DECL_RTL_SET_P (label)) 139 { 140 rtx r = gen_label_rtx (); 141 SET_DECL_RTL (label, r); 142 if (FORCED_LABEL (label) || DECL_NONLOCAL (label)) 143 LABEL_PRESERVE_P (r) = 1; 144 } 145 146 return DECL_RTL (label); 147 } 148 149 /* As above, but also put it on the forced-reference list of the 150 function that contains it. */ 151 rtx 152 force_label_rtx (tree label) 153 { 154 rtx ref = label_rtx (label); 155 tree function = decl_function_context (label); 156 157 gcc_assert (function); 158 159 forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref, forced_labels); 160 return ref; 161 } 162 163 /* Add an unconditional jump to LABEL as the next sequential instruction. */ 164 165 void 166 emit_jump (rtx label) 167 { 168 do_pending_stack_adjust (); 169 emit_jump_insn (gen_jump (label)); 170 emit_barrier (); 171 } 172 173 /* Emit code to jump to the address 174 specified by the pointer expression EXP. */ 175 176 void 177 expand_computed_goto (tree exp) 178 { 179 rtx x = expand_normal (exp); 180 181 x = convert_memory_address (Pmode, x); 182 183 do_pending_stack_adjust (); 184 emit_indirect_jump (x); 185 } 186 187 /* Handle goto statements and the labels that they can go to. */ 188 189 /* Specify the location in the RTL code of a label LABEL, 190 which is a LABEL_DECL tree node. 191 192 This is used for the kind of label that the user can jump to with a 193 goto statement, and for alternatives of a switch or case statement. 194 RTL labels generated for loops and conditionals don't go through here; 195 they are generated directly at the RTL level, by other functions below. 196 197 Note that this has nothing to do with defining label *names*. 198 Languages vary in how they do that and what that even means. */ 199 200 void 201 expand_label (tree label) 202 { 203 rtx label_r = label_rtx (label); 204 205 do_pending_stack_adjust (); 206 emit_label (label_r); 207 if (DECL_NAME (label)) 208 LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label)); 209 210 if (DECL_NONLOCAL (label)) 211 { 212 expand_nl_goto_receiver (); 213 nonlocal_goto_handler_labels 214 = gen_rtx_EXPR_LIST (VOIDmode, label_r, 215 nonlocal_goto_handler_labels); 216 } 217 218 if (FORCED_LABEL (label)) 219 forced_labels = gen_rtx_EXPR_LIST (VOIDmode, label_r, forced_labels); 220 221 if (DECL_NONLOCAL (label) || FORCED_LABEL (label)) 222 maybe_set_first_label_num (label_r); 223 } 224 225 /* Generate RTL code for a `goto' statement with target label LABEL. 226 LABEL should be a LABEL_DECL tree node that was or will later be 227 defined with `expand_label'. */ 228 229 void 230 expand_goto (tree label) 231 { 232 #ifdef ENABLE_CHECKING 233 /* Check for a nonlocal goto to a containing function. Should have 234 gotten translated to __builtin_nonlocal_goto. */ 235 tree context = decl_function_context (label); 236 gcc_assert (!context || context == current_function_decl); 237 #endif 238 239 emit_jump (label_rtx (label)); 240 } 241 242 /* Return the number of times character C occurs in string S. */ 243 static int 244 n_occurrences (int c, const char *s) 245 { 246 int n = 0; 247 while (*s) 248 n += (*s++ == c); 249 return n; 250 } 251 252 /* Generate RTL for an asm statement (explicit assembler code). 253 STRING is a STRING_CST node containing the assembler code text, 254 or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the 255 insn is volatile; don't optimize it. */ 256 257 static void 258 expand_asm_loc (tree string, int vol, location_t locus) 259 { 260 rtx body; 261 262 if (TREE_CODE (string) == ADDR_EXPR) 263 string = TREE_OPERAND (string, 0); 264 265 body = gen_rtx_ASM_INPUT_loc (VOIDmode, 266 ggc_strdup (TREE_STRING_POINTER (string)), 267 locus); 268 269 MEM_VOLATILE_P (body) = vol; 270 271 emit_insn (body); 272 } 273 274 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the 275 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS 276 inputs and NOUTPUTS outputs to this extended-asm. Upon return, 277 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a 278 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the 279 constraint allows the use of a register operand. And, *IS_INOUT 280 will be true if the operand is read-write, i.e., if it is used as 281 an input as well as an output. If *CONSTRAINT_P is not in 282 canonical form, it will be made canonical. (Note that `+' will be 283 replaced with `=' as part of this process.) 284 285 Returns TRUE if all went well; FALSE if an error occurred. */ 286 287 bool 288 parse_output_constraint (const char **constraint_p, int operand_num, 289 int ninputs, int noutputs, bool *allows_mem, 290 bool *allows_reg, bool *is_inout) 291 { 292 const char *constraint = *constraint_p; 293 const char *p; 294 295 /* Assume the constraint doesn't allow the use of either a register 296 or memory. */ 297 *allows_mem = false; 298 *allows_reg = false; 299 300 /* Allow the `=' or `+' to not be at the beginning of the string, 301 since it wasn't explicitly documented that way, and there is a 302 large body of code that puts it last. Swap the character to 303 the front, so as not to uglify any place else. */ 304 p = strchr (constraint, '='); 305 if (!p) 306 p = strchr (constraint, '+'); 307 308 /* If the string doesn't contain an `=', issue an error 309 message. */ 310 if (!p) 311 { 312 error ("output operand constraint lacks %<=%>"); 313 return false; 314 } 315 316 /* If the constraint begins with `+', then the operand is both read 317 from and written to. */ 318 *is_inout = (*p == '+'); 319 320 /* Canonicalize the output constraint so that it begins with `='. */ 321 if (p != constraint || *is_inout) 322 { 323 char *buf; 324 size_t c_len = strlen (constraint); 325 326 if (p != constraint) 327 warning (0, "output constraint %qc for operand %d " 328 "is not at the beginning", 329 *p, operand_num); 330 331 /* Make a copy of the constraint. */ 332 buf = XALLOCAVEC (char, c_len + 1); 333 strcpy (buf, constraint); 334 /* Swap the first character and the `=' or `+'. */ 335 buf[p - constraint] = buf[0]; 336 /* Make sure the first character is an `='. (Until we do this, 337 it might be a `+'.) */ 338 buf[0] = '='; 339 /* Replace the constraint with the canonicalized string. */ 340 *constraint_p = ggc_alloc_string (buf, c_len); 341 constraint = *constraint_p; 342 } 343 344 /* Loop through the constraint string. */ 345 for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p)) 346 switch (*p) 347 { 348 case '+': 349 case '=': 350 error ("operand constraint contains incorrectly positioned " 351 "%<+%> or %<=%>"); 352 return false; 353 354 case '%': 355 if (operand_num + 1 == ninputs + noutputs) 356 { 357 error ("%<%%%> constraint used with last operand"); 358 return false; 359 } 360 break; 361 362 case 'V': case TARGET_MEM_CONSTRAINT: case 'o': 363 *allows_mem = true; 364 break; 365 366 case '?': case '!': case '*': case '&': case '#': 367 case 'E': case 'F': case 'G': case 'H': 368 case 's': case 'i': case 'n': 369 case 'I': case 'J': case 'K': case 'L': case 'M': 370 case 'N': case 'O': case 'P': case ',': 371 break; 372 373 case '0': case '1': case '2': case '3': case '4': 374 case '5': case '6': case '7': case '8': case '9': 375 case '[': 376 error ("matching constraint not valid in output operand"); 377 return false; 378 379 case '<': case '>': 380 /* ??? Before flow, auto inc/dec insns are not supposed to exist, 381 excepting those that expand_call created. So match memory 382 and hope. */ 383 *allows_mem = true; 384 break; 385 386 case 'g': case 'X': 387 *allows_reg = true; 388 *allows_mem = true; 389 break; 390 391 case 'p': case 'r': 392 *allows_reg = true; 393 break; 394 395 default: 396 if (!ISALPHA (*p)) 397 break; 398 if (REG_CLASS_FROM_CONSTRAINT (*p, p) != NO_REGS) 399 *allows_reg = true; 400 #ifdef EXTRA_CONSTRAINT_STR 401 else if (EXTRA_ADDRESS_CONSTRAINT (*p, p)) 402 *allows_reg = true; 403 else if (EXTRA_MEMORY_CONSTRAINT (*p, p)) 404 *allows_mem = true; 405 else 406 { 407 /* Otherwise we can't assume anything about the nature of 408 the constraint except that it isn't purely registers. 409 Treat it like "g" and hope for the best. */ 410 *allows_reg = true; 411 *allows_mem = true; 412 } 413 #endif 414 break; 415 } 416 417 return true; 418 } 419 420 /* Similar, but for input constraints. */ 421 422 bool 423 parse_input_constraint (const char **constraint_p, int input_num, 424 int ninputs, int noutputs, int ninout, 425 const char * const * constraints, 426 bool *allows_mem, bool *allows_reg) 427 { 428 const char *constraint = *constraint_p; 429 const char *orig_constraint = constraint; 430 size_t c_len = strlen (constraint); 431 size_t j; 432 bool saw_match = false; 433 434 /* Assume the constraint doesn't allow the use of either 435 a register or memory. */ 436 *allows_mem = false; 437 *allows_reg = false; 438 439 /* Make sure constraint has neither `=', `+', nor '&'. */ 440 441 for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j)) 442 switch (constraint[j]) 443 { 444 case '+': case '=': case '&': 445 if (constraint == orig_constraint) 446 { 447 error ("input operand constraint contains %qc", constraint[j]); 448 return false; 449 } 450 break; 451 452 case '%': 453 if (constraint == orig_constraint 454 && input_num + 1 == ninputs - ninout) 455 { 456 error ("%<%%%> constraint used with last operand"); 457 return false; 458 } 459 break; 460 461 case 'V': case TARGET_MEM_CONSTRAINT: case 'o': 462 *allows_mem = true; 463 break; 464 465 case '<': case '>': 466 case '?': case '!': case '*': case '#': 467 case 'E': case 'F': case 'G': case 'H': 468 case 's': case 'i': case 'n': 469 case 'I': case 'J': case 'K': case 'L': case 'M': 470 case 'N': case 'O': case 'P': case ',': 471 break; 472 473 /* Whether or not a numeric constraint allows a register is 474 decided by the matching constraint, and so there is no need 475 to do anything special with them. We must handle them in 476 the default case, so that we don't unnecessarily force 477 operands to memory. */ 478 case '0': case '1': case '2': case '3': case '4': 479 case '5': case '6': case '7': case '8': case '9': 480 { 481 char *end; 482 unsigned long match; 483 484 saw_match = true; 485 486 match = strtoul (constraint + j, &end, 10); 487 if (match >= (unsigned long) noutputs) 488 { 489 error ("matching constraint references invalid operand number"); 490 return false; 491 } 492 493 /* Try and find the real constraint for this dup. Only do this 494 if the matching constraint is the only alternative. */ 495 if (*end == '\0' 496 && (j == 0 || (j == 1 && constraint[0] == '%'))) 497 { 498 constraint = constraints[match]; 499 *constraint_p = constraint; 500 c_len = strlen (constraint); 501 j = 0; 502 /* ??? At the end of the loop, we will skip the first part of 503 the matched constraint. This assumes not only that the 504 other constraint is an output constraint, but also that 505 the '=' or '+' come first. */ 506 break; 507 } 508 else 509 j = end - constraint; 510 /* Anticipate increment at end of loop. */ 511 j--; 512 } 513 /* Fall through. */ 514 515 case 'p': case 'r': 516 *allows_reg = true; 517 break; 518 519 case 'g': case 'X': 520 *allows_reg = true; 521 *allows_mem = true; 522 break; 523 524 default: 525 if (! ISALPHA (constraint[j])) 526 { 527 error ("invalid punctuation %qc in constraint", constraint[j]); 528 return false; 529 } 530 if (REG_CLASS_FROM_CONSTRAINT (constraint[j], constraint + j) 531 != NO_REGS) 532 *allows_reg = true; 533 #ifdef EXTRA_CONSTRAINT_STR 534 else if (EXTRA_ADDRESS_CONSTRAINT (constraint[j], constraint + j)) 535 *allows_reg = true; 536 else if (EXTRA_MEMORY_CONSTRAINT (constraint[j], constraint + j)) 537 *allows_mem = true; 538 else 539 { 540 /* Otherwise we can't assume anything about the nature of 541 the constraint except that it isn't purely registers. 542 Treat it like "g" and hope for the best. */ 543 *allows_reg = true; 544 *allows_mem = true; 545 } 546 #endif 547 break; 548 } 549 550 if (saw_match && !*allows_reg) 551 warning (0, "matching constraint does not allow a register"); 552 553 return true; 554 } 555 556 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL 557 can be an asm-declared register. Called via walk_tree. */ 558 559 static tree 560 decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED, 561 void *data) 562 { 563 tree decl = *declp; 564 const HARD_REG_SET *const regs = (const HARD_REG_SET *) data; 565 566 if (TREE_CODE (decl) == VAR_DECL) 567 { 568 if (DECL_HARD_REGISTER (decl) 569 && REG_P (DECL_RTL (decl)) 570 && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER) 571 { 572 rtx reg = DECL_RTL (decl); 573 574 if (overlaps_hard_reg_set_p (*regs, GET_MODE (reg), REGNO (reg))) 575 return decl; 576 } 577 walk_subtrees = 0; 578 } 579 else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL) 580 walk_subtrees = 0; 581 return NULL_TREE; 582 } 583 584 /* If there is an overlap between *REGS and DECL, return the first overlap 585 found. */ 586 tree 587 tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs) 588 { 589 return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL); 590 } 591 592 /* Check for overlap between registers marked in CLOBBERED_REGS and 593 anything inappropriate in T. Emit error and return the register 594 variable definition for error, NULL_TREE for ok. */ 595 596 static bool 597 tree_conflicts_with_clobbers_p (tree t, HARD_REG_SET *clobbered_regs) 598 { 599 /* Conflicts between asm-declared register variables and the clobber 600 list are not allowed. */ 601 tree overlap = tree_overlaps_hard_reg_set (t, clobbered_regs); 602 603 if (overlap) 604 { 605 error ("asm-specifier for variable %qE conflicts with asm clobber list", 606 DECL_NAME (overlap)); 607 608 /* Reset registerness to stop multiple errors emitted for a single 609 variable. */ 610 DECL_REGISTER (overlap) = 0; 611 return true; 612 } 613 614 return false; 615 } 616 617 /* Generate RTL for an asm statement with arguments. 618 STRING is the instruction template. 619 OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs. 620 Each output or input has an expression in the TREE_VALUE and 621 a tree list in TREE_PURPOSE which in turn contains a constraint 622 name in TREE_VALUE (or NULL_TREE) and a constraint string 623 in TREE_PURPOSE. 624 CLOBBERS is a list of STRING_CST nodes each naming a hard register 625 that is clobbered by this insn. 626 627 Not all kinds of lvalue that may appear in OUTPUTS can be stored directly. 628 Some elements of OUTPUTS may be replaced with trees representing temporary 629 values. The caller should copy those temporary values to the originally 630 specified lvalues. 631 632 VOL nonzero means the insn is volatile; don't optimize it. */ 633 634 static void 635 expand_asm_operands (tree string, tree outputs, tree inputs, 636 tree clobbers, tree labels, int vol, location_t locus) 637 { 638 rtvec argvec, constraintvec, labelvec; 639 rtx body; 640 int ninputs = list_length (inputs); 641 int noutputs = list_length (outputs); 642 int nlabels = list_length (labels); 643 int ninout; 644 int nclobbers; 645 HARD_REG_SET clobbered_regs; 646 int clobber_conflict_found = 0; 647 tree tail; 648 tree t; 649 int i; 650 /* Vector of RTX's of evaluated output operands. */ 651 rtx *output_rtx = XALLOCAVEC (rtx, noutputs); 652 int *inout_opnum = XALLOCAVEC (int, noutputs); 653 rtx *real_output_rtx = XALLOCAVEC (rtx, noutputs); 654 enum machine_mode *inout_mode = XALLOCAVEC (enum machine_mode, noutputs); 655 const char **constraints = XALLOCAVEC (const char *, noutputs + ninputs); 656 int old_generating_concat_p = generating_concat_p; 657 658 /* An ASM with no outputs needs to be treated as volatile, for now. */ 659 if (noutputs == 0) 660 vol = 1; 661 662 if (! check_operand_nalternatives (outputs, inputs)) 663 return; 664 665 string = resolve_asm_operand_names (string, outputs, inputs, labels); 666 667 /* Collect constraints. */ 668 i = 0; 669 for (t = outputs; t ; t = TREE_CHAIN (t), i++) 670 constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t))); 671 for (t = inputs; t ; t = TREE_CHAIN (t), i++) 672 constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t))); 673 674 /* Sometimes we wish to automatically clobber registers across an asm. 675 Case in point is when the i386 backend moved from cc0 to a hard reg -- 676 maintaining source-level compatibility means automatically clobbering 677 the flags register. */ 678 clobbers = targetm.md_asm_clobbers (outputs, inputs, clobbers); 679 680 /* Count the number of meaningful clobbered registers, ignoring what 681 we would ignore later. */ 682 nclobbers = 0; 683 CLEAR_HARD_REG_SET (clobbered_regs); 684 for (tail = clobbers; tail; tail = TREE_CHAIN (tail)) 685 { 686 const char *regname; 687 688 if (TREE_VALUE (tail) == error_mark_node) 689 return; 690 regname = TREE_STRING_POINTER (TREE_VALUE (tail)); 691 692 i = decode_reg_name (regname); 693 if (i >= 0 || i == -4) 694 ++nclobbers; 695 else if (i == -2) 696 error ("unknown register name %qs in %<asm%>", regname); 697 698 /* Mark clobbered registers. */ 699 if (i >= 0) 700 { 701 /* Clobbering the PIC register is an error. */ 702 if (i == (int) PIC_OFFSET_TABLE_REGNUM) 703 { 704 error ("PIC register %qs clobbered in %<asm%>", regname); 705 return; 706 } 707 708 SET_HARD_REG_BIT (clobbered_regs, i); 709 } 710 } 711 712 /* First pass over inputs and outputs checks validity and sets 713 mark_addressable if needed. */ 714 715 ninout = 0; 716 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 717 { 718 tree val = TREE_VALUE (tail); 719 tree type = TREE_TYPE (val); 720 const char *constraint; 721 bool is_inout; 722 bool allows_reg; 723 bool allows_mem; 724 725 /* If there's an erroneous arg, emit no insn. */ 726 if (type == error_mark_node) 727 return; 728 729 /* Try to parse the output constraint. If that fails, there's 730 no point in going further. */ 731 constraint = constraints[i]; 732 if (!parse_output_constraint (&constraint, i, ninputs, noutputs, 733 &allows_mem, &allows_reg, &is_inout)) 734 return; 735 736 if (! allows_reg 737 && (allows_mem 738 || is_inout 739 || (DECL_P (val) 740 && REG_P (DECL_RTL (val)) 741 && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))) 742 mark_addressable (val); 743 744 if (is_inout) 745 ninout++; 746 } 747 748 ninputs += ninout; 749 if (ninputs + noutputs > MAX_RECOG_OPERANDS) 750 { 751 error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS); 752 return; 753 } 754 755 for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail)) 756 { 757 bool allows_reg, allows_mem; 758 const char *constraint; 759 760 /* If there's an erroneous arg, emit no insn, because the ASM_INPUT 761 would get VOIDmode and that could cause a crash in reload. */ 762 if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node) 763 return; 764 765 constraint = constraints[i + noutputs]; 766 if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout, 767 constraints, &allows_mem, &allows_reg)) 768 return; 769 770 if (! allows_reg && allows_mem) 771 mark_addressable (TREE_VALUE (tail)); 772 } 773 774 /* Second pass evaluates arguments. */ 775 776 /* Make sure stack is consistent for asm goto. */ 777 if (nlabels > 0) 778 do_pending_stack_adjust (); 779 780 ninout = 0; 781 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 782 { 783 tree val = TREE_VALUE (tail); 784 tree type = TREE_TYPE (val); 785 bool is_inout; 786 bool allows_reg; 787 bool allows_mem; 788 rtx op; 789 bool ok; 790 791 ok = parse_output_constraint (&constraints[i], i, ninputs, 792 noutputs, &allows_mem, &allows_reg, 793 &is_inout); 794 gcc_assert (ok); 795 796 /* If an output operand is not a decl or indirect ref and our constraint 797 allows a register, make a temporary to act as an intermediate. 798 Make the asm insn write into that, then our caller will copy it to 799 the real output operand. Likewise for promoted variables. */ 800 801 generating_concat_p = 0; 802 803 real_output_rtx[i] = NULL_RTX; 804 if ((TREE_CODE (val) == INDIRECT_REF 805 && allows_mem) 806 || (DECL_P (val) 807 && (allows_mem || REG_P (DECL_RTL (val))) 808 && ! (REG_P (DECL_RTL (val)) 809 && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))) 810 || ! allows_reg 811 || is_inout) 812 { 813 op = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE); 814 if (MEM_P (op)) 815 op = validize_mem (op); 816 817 if (! allows_reg && !MEM_P (op)) 818 error ("output number %d not directly addressable", i); 819 if ((! allows_mem && MEM_P (op)) 820 || GET_CODE (op) == CONCAT) 821 { 822 real_output_rtx[i] = op; 823 op = gen_reg_rtx (GET_MODE (op)); 824 if (is_inout) 825 emit_move_insn (op, real_output_rtx[i]); 826 } 827 } 828 else 829 { 830 op = assign_temp (type, 0, 0, 1); 831 op = validize_mem (op); 832 if (!MEM_P (op) && TREE_CODE (TREE_VALUE (tail)) == SSA_NAME) 833 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (TREE_VALUE (tail)), op); 834 TREE_VALUE (tail) = make_tree (type, op); 835 } 836 output_rtx[i] = op; 837 838 generating_concat_p = old_generating_concat_p; 839 840 if (is_inout) 841 { 842 inout_mode[ninout] = TYPE_MODE (type); 843 inout_opnum[ninout++] = i; 844 } 845 846 if (tree_conflicts_with_clobbers_p (val, &clobbered_regs)) 847 clobber_conflict_found = 1; 848 } 849 850 /* Make vectors for the expression-rtx, constraint strings, 851 and named operands. */ 852 853 argvec = rtvec_alloc (ninputs); 854 constraintvec = rtvec_alloc (ninputs); 855 labelvec = rtvec_alloc (nlabels); 856 857 body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode 858 : GET_MODE (output_rtx[0])), 859 ggc_strdup (TREE_STRING_POINTER (string)), 860 empty_string, 0, argvec, constraintvec, 861 labelvec, locus); 862 863 MEM_VOLATILE_P (body) = vol; 864 865 /* Eval the inputs and put them into ARGVEC. 866 Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */ 867 868 for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i) 869 { 870 bool allows_reg, allows_mem; 871 const char *constraint; 872 tree val, type; 873 rtx op; 874 bool ok; 875 876 constraint = constraints[i + noutputs]; 877 ok = parse_input_constraint (&constraint, i, ninputs, noutputs, ninout, 878 constraints, &allows_mem, &allows_reg); 879 gcc_assert (ok); 880 881 generating_concat_p = 0; 882 883 val = TREE_VALUE (tail); 884 type = TREE_TYPE (val); 885 /* EXPAND_INITIALIZER will not generate code for valid initializer 886 constants, but will still generate code for other types of operand. 887 This is the behavior we want for constant constraints. */ 888 op = expand_expr (val, NULL_RTX, VOIDmode, 889 allows_reg ? EXPAND_NORMAL 890 : allows_mem ? EXPAND_MEMORY 891 : EXPAND_INITIALIZER); 892 893 /* Never pass a CONCAT to an ASM. */ 894 if (GET_CODE (op) == CONCAT) 895 op = force_reg (GET_MODE (op), op); 896 else if (MEM_P (op)) 897 op = validize_mem (op); 898 899 if (asm_operand_ok (op, constraint, NULL) <= 0) 900 { 901 if (allows_reg && TYPE_MODE (type) != BLKmode) 902 op = force_reg (TYPE_MODE (type), op); 903 else if (!allows_mem) 904 warning (0, "asm operand %d probably doesn%'t match constraints", 905 i + noutputs); 906 else if (MEM_P (op)) 907 { 908 /* We won't recognize either volatile memory or memory 909 with a queued address as available a memory_operand 910 at this point. Ignore it: clearly this *is* a memory. */ 911 } 912 else 913 { 914 warning (0, "use of memory input without lvalue in " 915 "asm operand %d is deprecated", i + noutputs); 916 917 if (CONSTANT_P (op)) 918 { 919 rtx mem = force_const_mem (TYPE_MODE (type), op); 920 if (mem) 921 op = validize_mem (mem); 922 else 923 op = force_reg (TYPE_MODE (type), op); 924 } 925 if (REG_P (op) 926 || GET_CODE (op) == SUBREG 927 || GET_CODE (op) == CONCAT) 928 { 929 tree qual_type = build_qualified_type (type, 930 (TYPE_QUALS (type) 931 | TYPE_QUAL_CONST)); 932 rtx memloc = assign_temp (qual_type, 1, 1, 1); 933 memloc = validize_mem (memloc); 934 emit_move_insn (memloc, op); 935 op = memloc; 936 } 937 } 938 } 939 940 generating_concat_p = old_generating_concat_p; 941 ASM_OPERANDS_INPUT (body, i) = op; 942 943 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i) 944 = gen_rtx_ASM_INPUT (TYPE_MODE (type), 945 ggc_strdup (constraints[i + noutputs])); 946 947 if (tree_conflicts_with_clobbers_p (val, &clobbered_regs)) 948 clobber_conflict_found = 1; 949 } 950 951 /* Protect all the operands from the queue now that they have all been 952 evaluated. */ 953 954 generating_concat_p = 0; 955 956 /* For in-out operands, copy output rtx to input rtx. */ 957 for (i = 0; i < ninout; i++) 958 { 959 int j = inout_opnum[i]; 960 char buffer[16]; 961 962 ASM_OPERANDS_INPUT (body, ninputs - ninout + i) 963 = output_rtx[j]; 964 965 sprintf (buffer, "%d", j); 966 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i) 967 = gen_rtx_ASM_INPUT (inout_mode[i], ggc_strdup (buffer)); 968 } 969 970 /* Copy labels to the vector. */ 971 for (i = 0, tail = labels; i < nlabels; ++i, tail = TREE_CHAIN (tail)) 972 ASM_OPERANDS_LABEL (body, i) 973 = gen_rtx_LABEL_REF (Pmode, label_rtx (TREE_VALUE (tail))); 974 975 generating_concat_p = old_generating_concat_p; 976 977 /* Now, for each output, construct an rtx 978 (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER 979 ARGVEC CONSTRAINTS OPNAMES)) 980 If there is more than one, put them inside a PARALLEL. */ 981 982 if (nlabels > 0 && nclobbers == 0) 983 { 984 gcc_assert (noutputs == 0); 985 emit_jump_insn (body); 986 } 987 else if (noutputs == 0 && nclobbers == 0) 988 { 989 /* No output operands: put in a raw ASM_OPERANDS rtx. */ 990 emit_insn (body); 991 } 992 else if (noutputs == 1 && nclobbers == 0) 993 { 994 ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = ggc_strdup (constraints[0]); 995 emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body)); 996 } 997 else 998 { 999 rtx obody = body; 1000 int num = noutputs; 1001 1002 if (num == 0) 1003 num = 1; 1004 1005 body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers)); 1006 1007 /* For each output operand, store a SET. */ 1008 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 1009 { 1010 XVECEXP (body, 0, i) 1011 = gen_rtx_SET (VOIDmode, 1012 output_rtx[i], 1013 gen_rtx_ASM_OPERANDS 1014 (GET_MODE (output_rtx[i]), 1015 ggc_strdup (TREE_STRING_POINTER (string)), 1016 ggc_strdup (constraints[i]), 1017 i, argvec, constraintvec, labelvec, locus)); 1018 1019 MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol; 1020 } 1021 1022 /* If there are no outputs (but there are some clobbers) 1023 store the bare ASM_OPERANDS into the PARALLEL. */ 1024 1025 if (i == 0) 1026 XVECEXP (body, 0, i++) = obody; 1027 1028 /* Store (clobber REG) for each clobbered register specified. */ 1029 1030 for (tail = clobbers; tail; tail = TREE_CHAIN (tail)) 1031 { 1032 const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail)); 1033 int j = decode_reg_name (regname); 1034 rtx clobbered_reg; 1035 1036 if (j < 0) 1037 { 1038 if (j == -3) /* `cc', which is not a register */ 1039 continue; 1040 1041 if (j == -4) /* `memory', don't cache memory across asm */ 1042 { 1043 XVECEXP (body, 0, i++) 1044 = gen_rtx_CLOBBER (VOIDmode, 1045 gen_rtx_MEM 1046 (BLKmode, 1047 gen_rtx_SCRATCH (VOIDmode))); 1048 continue; 1049 } 1050 1051 /* Ignore unknown register, error already signaled. */ 1052 continue; 1053 } 1054 1055 /* Use QImode since that's guaranteed to clobber just one reg. */ 1056 clobbered_reg = gen_rtx_REG (QImode, j); 1057 1058 /* Do sanity check for overlap between clobbers and respectively 1059 input and outputs that hasn't been handled. Such overlap 1060 should have been detected and reported above. */ 1061 if (!clobber_conflict_found) 1062 { 1063 int opno; 1064 1065 /* We test the old body (obody) contents to avoid tripping 1066 over the under-construction body. */ 1067 for (opno = 0; opno < noutputs; opno++) 1068 if (reg_overlap_mentioned_p (clobbered_reg, output_rtx[opno])) 1069 internal_error ("asm clobber conflict with output operand"); 1070 1071 for (opno = 0; opno < ninputs - ninout; opno++) 1072 if (reg_overlap_mentioned_p (clobbered_reg, 1073 ASM_OPERANDS_INPUT (obody, opno))) 1074 internal_error ("asm clobber conflict with input operand"); 1075 } 1076 1077 XVECEXP (body, 0, i++) 1078 = gen_rtx_CLOBBER (VOIDmode, clobbered_reg); 1079 } 1080 1081 if (nlabels > 0) 1082 emit_jump_insn (body); 1083 else 1084 emit_insn (body); 1085 } 1086 1087 /* For any outputs that needed reloading into registers, spill them 1088 back to where they belong. */ 1089 for (i = 0; i < noutputs; ++i) 1090 if (real_output_rtx[i]) 1091 emit_move_insn (real_output_rtx[i], output_rtx[i]); 1092 1093 crtl->has_asm_statement = 1; 1094 free_temp_slots (); 1095 } 1096 1097 void 1098 expand_asm_stmt (gimple stmt) 1099 { 1100 int noutputs; 1101 tree outputs, tail, t; 1102 tree *o; 1103 size_t i, n; 1104 const char *s; 1105 tree str, out, in, cl, labels; 1106 location_t locus = gimple_location (stmt); 1107 1108 /* Meh... convert the gimple asm operands into real tree lists. 1109 Eventually we should make all routines work on the vectors instead 1110 of relying on TREE_CHAIN. */ 1111 out = NULL_TREE; 1112 n = gimple_asm_noutputs (stmt); 1113 if (n > 0) 1114 { 1115 t = out = gimple_asm_output_op (stmt, 0); 1116 for (i = 1; i < n; i++) 1117 t = TREE_CHAIN (t) = gimple_asm_output_op (stmt, i); 1118 } 1119 1120 in = NULL_TREE; 1121 n = gimple_asm_ninputs (stmt); 1122 if (n > 0) 1123 { 1124 t = in = gimple_asm_input_op (stmt, 0); 1125 for (i = 1; i < n; i++) 1126 t = TREE_CHAIN (t) = gimple_asm_input_op (stmt, i); 1127 } 1128 1129 cl = NULL_TREE; 1130 n = gimple_asm_nclobbers (stmt); 1131 if (n > 0) 1132 { 1133 t = cl = gimple_asm_clobber_op (stmt, 0); 1134 for (i = 1; i < n; i++) 1135 t = TREE_CHAIN (t) = gimple_asm_clobber_op (stmt, i); 1136 } 1137 1138 labels = NULL_TREE; 1139 n = gimple_asm_nlabels (stmt); 1140 if (n > 0) 1141 { 1142 t = labels = gimple_asm_label_op (stmt, 0); 1143 for (i = 1; i < n; i++) 1144 t = TREE_CHAIN (t) = gimple_asm_label_op (stmt, i); 1145 } 1146 1147 s = gimple_asm_string (stmt); 1148 str = build_string (strlen (s), s); 1149 1150 if (gimple_asm_input_p (stmt)) 1151 { 1152 expand_asm_loc (str, gimple_asm_volatile_p (stmt), locus); 1153 return; 1154 } 1155 1156 outputs = out; 1157 noutputs = gimple_asm_noutputs (stmt); 1158 /* o[I] is the place that output number I should be written. */ 1159 o = (tree *) alloca (noutputs * sizeof (tree)); 1160 1161 /* Record the contents of OUTPUTS before it is modified. */ 1162 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 1163 o[i] = TREE_VALUE (tail); 1164 1165 /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of 1166 OUTPUTS some trees for where the values were actually stored. */ 1167 expand_asm_operands (str, outputs, in, cl, labels, 1168 gimple_asm_volatile_p (stmt), locus); 1169 1170 /* Copy all the intermediate outputs into the specified outputs. */ 1171 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 1172 { 1173 if (o[i] != TREE_VALUE (tail)) 1174 { 1175 expand_assignment (o[i], TREE_VALUE (tail), false); 1176 free_temp_slots (); 1177 1178 /* Restore the original value so that it's correct the next 1179 time we expand this function. */ 1180 TREE_VALUE (tail) = o[i]; 1181 } 1182 } 1183 } 1184 1185 /* A subroutine of expand_asm_operands. Check that all operands have 1186 the same number of alternatives. Return true if so. */ 1187 1188 static bool 1189 check_operand_nalternatives (tree outputs, tree inputs) 1190 { 1191 if (outputs || inputs) 1192 { 1193 tree tmp = TREE_PURPOSE (outputs ? outputs : inputs); 1194 int nalternatives 1195 = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp))); 1196 tree next = inputs; 1197 1198 if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES) 1199 { 1200 error ("too many alternatives in %<asm%>"); 1201 return false; 1202 } 1203 1204 tmp = outputs; 1205 while (tmp) 1206 { 1207 const char *constraint 1208 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp))); 1209 1210 if (n_occurrences (',', constraint) != nalternatives) 1211 { 1212 error ("operand constraints for %<asm%> differ " 1213 "in number of alternatives"); 1214 return false; 1215 } 1216 1217 if (TREE_CHAIN (tmp)) 1218 tmp = TREE_CHAIN (tmp); 1219 else 1220 tmp = next, next = 0; 1221 } 1222 } 1223 1224 return true; 1225 } 1226 1227 /* A subroutine of expand_asm_operands. Check that all operand names 1228 are unique. Return true if so. We rely on the fact that these names 1229 are identifiers, and so have been canonicalized by get_identifier, 1230 so all we need are pointer comparisons. */ 1231 1232 static bool 1233 check_unique_operand_names (tree outputs, tree inputs, tree labels) 1234 { 1235 tree i, j, i_name = NULL_TREE; 1236 1237 for (i = outputs; i ; i = TREE_CHAIN (i)) 1238 { 1239 i_name = TREE_PURPOSE (TREE_PURPOSE (i)); 1240 if (! i_name) 1241 continue; 1242 1243 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j)) 1244 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) 1245 goto failure; 1246 } 1247 1248 for (i = inputs; i ; i = TREE_CHAIN (i)) 1249 { 1250 i_name = TREE_PURPOSE (TREE_PURPOSE (i)); 1251 if (! i_name) 1252 continue; 1253 1254 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j)) 1255 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) 1256 goto failure; 1257 for (j = outputs; j ; j = TREE_CHAIN (j)) 1258 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) 1259 goto failure; 1260 } 1261 1262 for (i = labels; i ; i = TREE_CHAIN (i)) 1263 { 1264 i_name = TREE_PURPOSE (i); 1265 if (! i_name) 1266 continue; 1267 1268 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j)) 1269 if (simple_cst_equal (i_name, TREE_PURPOSE (j))) 1270 goto failure; 1271 for (j = inputs; j ; j = TREE_CHAIN (j)) 1272 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) 1273 goto failure; 1274 } 1275 1276 return true; 1277 1278 failure: 1279 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name)); 1280 return false; 1281 } 1282 1283 /* A subroutine of expand_asm_operands. Resolve the names of the operands 1284 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in 1285 STRING and in the constraints to those numbers. */ 1286 1287 tree 1288 resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels) 1289 { 1290 char *buffer; 1291 char *p; 1292 const char *c; 1293 tree t; 1294 1295 check_unique_operand_names (outputs, inputs, labels); 1296 1297 /* Substitute [<name>] in input constraint strings. There should be no 1298 named operands in output constraints. */ 1299 for (t = inputs; t ; t = TREE_CHAIN (t)) 1300 { 1301 c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t))); 1302 if (strchr (c, '[') != NULL) 1303 { 1304 p = buffer = xstrdup (c); 1305 while ((p = strchr (p, '[')) != NULL) 1306 p = resolve_operand_name_1 (p, outputs, inputs, NULL); 1307 TREE_VALUE (TREE_PURPOSE (t)) 1308 = build_string (strlen (buffer), buffer); 1309 free (buffer); 1310 } 1311 } 1312 1313 /* Now check for any needed substitutions in the template. */ 1314 c = TREE_STRING_POINTER (string); 1315 while ((c = strchr (c, '%')) != NULL) 1316 { 1317 if (c[1] == '[') 1318 break; 1319 else if (ISALPHA (c[1]) && c[2] == '[') 1320 break; 1321 else 1322 { 1323 c += 1; 1324 continue; 1325 } 1326 } 1327 1328 if (c) 1329 { 1330 /* OK, we need to make a copy so we can perform the substitutions. 1331 Assume that we will not need extra space--we get to remove '[' 1332 and ']', which means we cannot have a problem until we have more 1333 than 999 operands. */ 1334 buffer = xstrdup (TREE_STRING_POINTER (string)); 1335 p = buffer + (c - TREE_STRING_POINTER (string)); 1336 1337 while ((p = strchr (p, '%')) != NULL) 1338 { 1339 if (p[1] == '[') 1340 p += 1; 1341 else if (ISALPHA (p[1]) && p[2] == '[') 1342 p += 2; 1343 else 1344 { 1345 p += 1; 1346 continue; 1347 } 1348 1349 p = resolve_operand_name_1 (p, outputs, inputs, labels); 1350 } 1351 1352 string = build_string (strlen (buffer), buffer); 1353 free (buffer); 1354 } 1355 1356 return string; 1357 } 1358 1359 /* A subroutine of resolve_operand_names. P points to the '[' for a 1360 potential named operand of the form [<name>]. In place, replace 1361 the name and brackets with a number. Return a pointer to the 1362 balance of the string after substitution. */ 1363 1364 static char * 1365 resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels) 1366 { 1367 char *q; 1368 int op; 1369 tree t; 1370 1371 /* Collect the operand name. */ 1372 q = strchr (++p, ']'); 1373 if (!q) 1374 { 1375 error ("missing close brace for named operand"); 1376 return strchr (p, '\0'); 1377 } 1378 *q = '\0'; 1379 1380 /* Resolve the name to a number. */ 1381 for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++) 1382 { 1383 tree name = TREE_PURPOSE (TREE_PURPOSE (t)); 1384 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0) 1385 goto found; 1386 } 1387 for (t = inputs; t ; t = TREE_CHAIN (t), op++) 1388 { 1389 tree name = TREE_PURPOSE (TREE_PURPOSE (t)); 1390 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0) 1391 goto found; 1392 } 1393 for (t = labels; t ; t = TREE_CHAIN (t), op++) 1394 { 1395 tree name = TREE_PURPOSE (t); 1396 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0) 1397 goto found; 1398 } 1399 1400 error ("undefined named operand %qs", identifier_to_locale (p)); 1401 op = 0; 1402 1403 found: 1404 /* Replace the name with the number. Unfortunately, not all libraries 1405 get the return value of sprintf correct, so search for the end of the 1406 generated string by hand. */ 1407 sprintf (--p, "%d", op); 1408 p = strchr (p, '\0'); 1409 1410 /* Verify the no extra buffer space assumption. */ 1411 gcc_assert (p <= q); 1412 1413 /* Shift the rest of the buffer down to fill the gap. */ 1414 memmove (p, q + 1, strlen (q + 1) + 1); 1415 1416 return p; 1417 } 1418 1419 /* Generate RTL to evaluate the expression EXP. */ 1420 1421 void 1422 expand_expr_stmt (tree exp) 1423 { 1424 rtx value; 1425 tree type; 1426 1427 value = expand_expr (exp, const0_rtx, VOIDmode, EXPAND_NORMAL); 1428 type = TREE_TYPE (exp); 1429 1430 /* If all we do is reference a volatile value in memory, 1431 copy it to a register to be sure it is actually touched. */ 1432 if (value && MEM_P (value) && TREE_THIS_VOLATILE (exp)) 1433 { 1434 if (TYPE_MODE (type) == VOIDmode) 1435 ; 1436 else if (TYPE_MODE (type) != BLKmode) 1437 value = copy_to_reg (value); 1438 else 1439 { 1440 rtx lab = gen_label_rtx (); 1441 1442 /* Compare the value with itself to reference it. */ 1443 emit_cmp_and_jump_insns (value, value, EQ, 1444 expand_normal (TYPE_SIZE (type)), 1445 BLKmode, 0, lab); 1446 emit_label (lab); 1447 } 1448 } 1449 1450 /* Free any temporaries used to evaluate this expression. */ 1451 free_temp_slots (); 1452 } 1453 1454 /* Warn if EXP contains any computations whose results are not used. 1455 Return 1 if a warning is printed; 0 otherwise. LOCUS is the 1456 (potential) location of the expression. */ 1457 1458 int 1459 warn_if_unused_value (const_tree exp, location_t locus) 1460 { 1461 restart: 1462 if (TREE_USED (exp) || TREE_NO_WARNING (exp)) 1463 return 0; 1464 1465 /* Don't warn about void constructs. This includes casting to void, 1466 void function calls, and statement expressions with a final cast 1467 to void. */ 1468 if (VOID_TYPE_P (TREE_TYPE (exp))) 1469 return 0; 1470 1471 if (EXPR_HAS_LOCATION (exp)) 1472 locus = EXPR_LOCATION (exp); 1473 1474 switch (TREE_CODE (exp)) 1475 { 1476 case PREINCREMENT_EXPR: 1477 case POSTINCREMENT_EXPR: 1478 case PREDECREMENT_EXPR: 1479 case POSTDECREMENT_EXPR: 1480 case MODIFY_EXPR: 1481 case INIT_EXPR: 1482 case TARGET_EXPR: 1483 case CALL_EXPR: 1484 case TRY_CATCH_EXPR: 1485 case WITH_CLEANUP_EXPR: 1486 case EXIT_EXPR: 1487 case VA_ARG_EXPR: 1488 return 0; 1489 1490 case BIND_EXPR: 1491 /* For a binding, warn if no side effect within it. */ 1492 exp = BIND_EXPR_BODY (exp); 1493 goto restart; 1494 1495 case SAVE_EXPR: 1496 case NON_LVALUE_EXPR: 1497 exp = TREE_OPERAND (exp, 0); 1498 goto restart; 1499 1500 case TRUTH_ORIF_EXPR: 1501 case TRUTH_ANDIF_EXPR: 1502 /* In && or ||, warn if 2nd operand has no side effect. */ 1503 exp = TREE_OPERAND (exp, 1); 1504 goto restart; 1505 1506 case COMPOUND_EXPR: 1507 if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus)) 1508 return 1; 1509 /* Let people do `(foo (), 0)' without a warning. */ 1510 if (TREE_CONSTANT (TREE_OPERAND (exp, 1))) 1511 return 0; 1512 exp = TREE_OPERAND (exp, 1); 1513 goto restart; 1514 1515 case COND_EXPR: 1516 /* If this is an expression with side effects, don't warn; this 1517 case commonly appears in macro expansions. */ 1518 if (TREE_SIDE_EFFECTS (exp)) 1519 return 0; 1520 goto warn; 1521 1522 case INDIRECT_REF: 1523 /* Don't warn about automatic dereferencing of references, since 1524 the user cannot control it. */ 1525 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE) 1526 { 1527 exp = TREE_OPERAND (exp, 0); 1528 goto restart; 1529 } 1530 /* Fall through. */ 1531 1532 default: 1533 /* Referencing a volatile value is a side effect, so don't warn. */ 1534 if ((DECL_P (exp) || REFERENCE_CLASS_P (exp)) 1535 && TREE_THIS_VOLATILE (exp)) 1536 return 0; 1537 1538 /* If this is an expression which has no operands, there is no value 1539 to be unused. There are no such language-independent codes, 1540 but front ends may define such. */ 1541 if (EXPRESSION_CLASS_P (exp) && TREE_OPERAND_LENGTH (exp) == 0) 1542 return 0; 1543 1544 warn: 1545 warning_at (locus, OPT_Wunused_value, "value computed is not used"); 1546 return 1; 1547 } 1548 } 1549 1550 1551 /* Generate RTL to return from the current function, with no value. 1552 (That is, we do not do anything about returning any value.) */ 1553 1554 void 1555 expand_null_return (void) 1556 { 1557 /* If this function was declared to return a value, but we 1558 didn't, clobber the return registers so that they are not 1559 propagated live to the rest of the function. */ 1560 clobber_return_register (); 1561 1562 expand_null_return_1 (); 1563 } 1564 1565 /* Generate RTL to return directly from the current function. 1566 (That is, we bypass any return value.) */ 1567 1568 void 1569 expand_naked_return (void) 1570 { 1571 rtx end_label; 1572 1573 clear_pending_stack_adjust (); 1574 do_pending_stack_adjust (); 1575 1576 end_label = naked_return_label; 1577 if (end_label == 0) 1578 end_label = naked_return_label = gen_label_rtx (); 1579 1580 emit_jump (end_label); 1581 } 1582 1583 /* Generate RTL to return from the current function, with value VAL. */ 1584 1585 static void 1586 expand_value_return (rtx val) 1587 { 1588 /* Copy the value to the return location unless it's already there. */ 1589 1590 tree decl = DECL_RESULT (current_function_decl); 1591 rtx return_reg = DECL_RTL (decl); 1592 if (return_reg != val) 1593 { 1594 tree funtype = TREE_TYPE (current_function_decl); 1595 tree type = TREE_TYPE (decl); 1596 int unsignedp = TYPE_UNSIGNED (type); 1597 enum machine_mode old_mode = DECL_MODE (decl); 1598 enum machine_mode mode = promote_function_mode (type, old_mode, 1599 &unsignedp, funtype, 1); 1600 1601 if (mode != old_mode) 1602 val = convert_modes (mode, old_mode, val, unsignedp); 1603 1604 if (GET_CODE (return_reg) == PARALLEL) 1605 emit_group_load (return_reg, val, type, int_size_in_bytes (type)); 1606 else 1607 emit_move_insn (return_reg, val); 1608 } 1609 1610 expand_null_return_1 (); 1611 } 1612 1613 /* Output a return with no value. */ 1614 1615 static void 1616 expand_null_return_1 (void) 1617 { 1618 clear_pending_stack_adjust (); 1619 do_pending_stack_adjust (); 1620 emit_jump (return_label); 1621 } 1622 1623 /* Generate RTL to evaluate the expression RETVAL and return it 1624 from the current function. */ 1625 1626 void 1627 expand_return (tree retval) 1628 { 1629 rtx result_rtl; 1630 rtx val = 0; 1631 tree retval_rhs; 1632 1633 /* If function wants no value, give it none. */ 1634 if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE) 1635 { 1636 expand_normal (retval); 1637 expand_null_return (); 1638 return; 1639 } 1640 1641 if (retval == error_mark_node) 1642 { 1643 /* Treat this like a return of no value from a function that 1644 returns a value. */ 1645 expand_null_return (); 1646 return; 1647 } 1648 else if ((TREE_CODE (retval) == MODIFY_EXPR 1649 || TREE_CODE (retval) == INIT_EXPR) 1650 && TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL) 1651 retval_rhs = TREE_OPERAND (retval, 1); 1652 else 1653 retval_rhs = retval; 1654 1655 result_rtl = DECL_RTL (DECL_RESULT (current_function_decl)); 1656 1657 /* If we are returning the RESULT_DECL, then the value has already 1658 been stored into it, so we don't have to do anything special. */ 1659 if (TREE_CODE (retval_rhs) == RESULT_DECL) 1660 expand_value_return (result_rtl); 1661 1662 /* If the result is an aggregate that is being returned in one (or more) 1663 registers, load the registers here. The compiler currently can't handle 1664 copying a BLKmode value into registers. We could put this code in a 1665 more general area (for use by everyone instead of just function 1666 call/return), but until this feature is generally usable it is kept here 1667 (and in expand_call). */ 1668 1669 else if (retval_rhs != 0 1670 && TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode 1671 && REG_P (result_rtl)) 1672 { 1673 int i; 1674 unsigned HOST_WIDE_INT bitpos, xbitpos; 1675 unsigned HOST_WIDE_INT padding_correction = 0; 1676 unsigned HOST_WIDE_INT bytes 1677 = int_size_in_bytes (TREE_TYPE (retval_rhs)); 1678 int n_regs = (bytes + UNITS_PER_WORD - 1) / UNITS_PER_WORD; 1679 unsigned int bitsize 1680 = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)), BITS_PER_WORD); 1681 rtx *result_pseudos = XALLOCAVEC (rtx, n_regs); 1682 rtx result_reg, src = NULL_RTX, dst = NULL_RTX; 1683 rtx result_val = expand_normal (retval_rhs); 1684 enum machine_mode tmpmode, result_reg_mode; 1685 1686 if (bytes == 0) 1687 { 1688 expand_null_return (); 1689 return; 1690 } 1691 1692 /* If the structure doesn't take up a whole number of words, see 1693 whether the register value should be padded on the left or on 1694 the right. Set PADDING_CORRECTION to the number of padding 1695 bits needed on the left side. 1696 1697 In most ABIs, the structure will be returned at the least end of 1698 the register, which translates to right padding on little-endian 1699 targets and left padding on big-endian targets. The opposite 1700 holds if the structure is returned at the most significant 1701 end of the register. */ 1702 if (bytes % UNITS_PER_WORD != 0 1703 && (targetm.calls.return_in_msb (TREE_TYPE (retval_rhs)) 1704 ? !BYTES_BIG_ENDIAN 1705 : BYTES_BIG_ENDIAN)) 1706 padding_correction = (BITS_PER_WORD - ((bytes % UNITS_PER_WORD) 1707 * BITS_PER_UNIT)); 1708 1709 /* Copy the structure BITSIZE bits at a time. */ 1710 for (bitpos = 0, xbitpos = padding_correction; 1711 bitpos < bytes * BITS_PER_UNIT; 1712 bitpos += bitsize, xbitpos += bitsize) 1713 { 1714 /* We need a new destination pseudo each time xbitpos is 1715 on a word boundary and when xbitpos == padding_correction 1716 (the first time through). */ 1717 if (xbitpos % BITS_PER_WORD == 0 1718 || xbitpos == padding_correction) 1719 { 1720 /* Generate an appropriate register. */ 1721 dst = gen_reg_rtx (word_mode); 1722 result_pseudos[xbitpos / BITS_PER_WORD] = dst; 1723 1724 /* Clear the destination before we move anything into it. */ 1725 emit_move_insn (dst, CONST0_RTX (GET_MODE (dst))); 1726 } 1727 1728 /* We need a new source operand each time bitpos is on a word 1729 boundary. */ 1730 if (bitpos % BITS_PER_WORD == 0) 1731 src = operand_subword_force (result_val, 1732 bitpos / BITS_PER_WORD, 1733 BLKmode); 1734 1735 /* Use bitpos for the source extraction (left justified) and 1736 xbitpos for the destination store (right justified). */ 1737 store_bit_field (dst, bitsize, xbitpos % BITS_PER_WORD, word_mode, 1738 extract_bit_field (src, bitsize, 1739 bitpos % BITS_PER_WORD, 1, 1740 NULL_RTX, word_mode, word_mode)); 1741 } 1742 1743 tmpmode = GET_MODE (result_rtl); 1744 if (tmpmode == BLKmode) 1745 { 1746 /* Find the smallest integer mode large enough to hold the 1747 entire structure and use that mode instead of BLKmode 1748 on the USE insn for the return register. */ 1749 for (tmpmode = GET_CLASS_NARROWEST_MODE (MODE_INT); 1750 tmpmode != VOIDmode; 1751 tmpmode = GET_MODE_WIDER_MODE (tmpmode)) 1752 /* Have we found a large enough mode? */ 1753 if (GET_MODE_SIZE (tmpmode) >= bytes) 1754 break; 1755 1756 /* A suitable mode should have been found. */ 1757 gcc_assert (tmpmode != VOIDmode); 1758 1759 PUT_MODE (result_rtl, tmpmode); 1760 } 1761 1762 if (GET_MODE_SIZE (tmpmode) < GET_MODE_SIZE (word_mode)) 1763 result_reg_mode = word_mode; 1764 else 1765 result_reg_mode = tmpmode; 1766 result_reg = gen_reg_rtx (result_reg_mode); 1767 1768 for (i = 0; i < n_regs; i++) 1769 emit_move_insn (operand_subword (result_reg, i, 0, result_reg_mode), 1770 result_pseudos[i]); 1771 1772 if (tmpmode != result_reg_mode) 1773 result_reg = gen_lowpart (tmpmode, result_reg); 1774 1775 expand_value_return (result_reg); 1776 } 1777 else if (retval_rhs != 0 1778 && !VOID_TYPE_P (TREE_TYPE (retval_rhs)) 1779 && (REG_P (result_rtl) 1780 || (GET_CODE (result_rtl) == PARALLEL))) 1781 { 1782 /* Calculate the return value into a temporary (usually a pseudo 1783 reg). */ 1784 tree ot = TREE_TYPE (DECL_RESULT (current_function_decl)); 1785 tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST); 1786 1787 val = assign_temp (nt, 0, 0, 1); 1788 val = expand_expr (retval_rhs, val, GET_MODE (val), EXPAND_NORMAL); 1789 val = force_not_mem (val); 1790 /* Return the calculated value. */ 1791 expand_value_return (val); 1792 } 1793 else 1794 { 1795 /* No hard reg used; calculate value into hard return reg. */ 1796 expand_expr (retval, const0_rtx, VOIDmode, EXPAND_NORMAL); 1797 expand_value_return (result_rtl); 1798 } 1799 } 1800 1801 /* Emit code to restore vital registers at the beginning of a nonlocal goto 1802 handler. */ 1803 static void 1804 expand_nl_goto_receiver (void) 1805 { 1806 rtx chain; 1807 1808 /* Clobber the FP when we get here, so we have to make sure it's 1809 marked as used by this function. */ 1810 emit_use (hard_frame_pointer_rtx); 1811 1812 /* Mark the static chain as clobbered here so life information 1813 doesn't get messed up for it. */ 1814 chain = targetm.calls.static_chain (current_function_decl, true); 1815 if (chain && REG_P (chain)) 1816 emit_clobber (chain); 1817 1818 #ifdef HAVE_nonlocal_goto 1819 if (! HAVE_nonlocal_goto) 1820 #endif 1821 /* First adjust our frame pointer to its actual value. It was 1822 previously set to the start of the virtual area corresponding to 1823 the stacked variables when we branched here and now needs to be 1824 adjusted to the actual hardware fp value. 1825 1826 Assignments are to virtual registers are converted by 1827 instantiate_virtual_regs into the corresponding assignment 1828 to the underlying register (fp in this case) that makes 1829 the original assignment true. 1830 So the following insn will actually be 1831 decrementing fp by STARTING_FRAME_OFFSET. */ 1832 emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx); 1833 1834 #if ARG_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 1835 if (fixed_regs[ARG_POINTER_REGNUM]) 1836 { 1837 #ifdef ELIMINABLE_REGS 1838 /* If the argument pointer can be eliminated in favor of the 1839 frame pointer, we don't need to restore it. We assume here 1840 that if such an elimination is present, it can always be used. 1841 This is the case on all known machines; if we don't make this 1842 assumption, we do unnecessary saving on many machines. */ 1843 static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS; 1844 size_t i; 1845 1846 for (i = 0; i < ARRAY_SIZE (elim_regs); i++) 1847 if (elim_regs[i].from == ARG_POINTER_REGNUM 1848 && elim_regs[i].to == HARD_FRAME_POINTER_REGNUM) 1849 break; 1850 1851 if (i == ARRAY_SIZE (elim_regs)) 1852 #endif 1853 { 1854 /* Now restore our arg pointer from the address at which it 1855 was saved in our stack frame. */ 1856 emit_move_insn (crtl->args.internal_arg_pointer, 1857 copy_to_reg (get_arg_pointer_save_area ())); 1858 } 1859 } 1860 #endif 1861 1862 #ifdef HAVE_nonlocal_goto_receiver 1863 if (HAVE_nonlocal_goto_receiver) 1864 emit_insn (gen_nonlocal_goto_receiver ()); 1865 #endif 1866 1867 /* We must not allow the code we just generated to be reordered by 1868 scheduling. Specifically, the update of the frame pointer must 1869 happen immediately, not later. */ 1870 emit_insn (gen_blockage ()); 1871 } 1872 1873 /* Generate RTL for the automatic variable declaration DECL. 1874 (Other kinds of declarations are simply ignored if seen here.) */ 1875 1876 void 1877 expand_decl (tree decl) 1878 { 1879 tree type; 1880 1881 type = TREE_TYPE (decl); 1882 1883 /* For a CONST_DECL, set mode, alignment, and sizes from those of the 1884 type in case this node is used in a reference. */ 1885 if (TREE_CODE (decl) == CONST_DECL) 1886 { 1887 DECL_MODE (decl) = TYPE_MODE (type); 1888 DECL_ALIGN (decl) = TYPE_ALIGN (type); 1889 DECL_SIZE (decl) = TYPE_SIZE (type); 1890 DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type); 1891 return; 1892 } 1893 1894 /* Otherwise, only automatic variables need any expansion done. Static and 1895 external variables, and external functions, will be handled by 1896 `assemble_variable' (called from finish_decl). TYPE_DECL requires 1897 nothing. PARM_DECLs are handled in `assign_parms'. */ 1898 if (TREE_CODE (decl) != VAR_DECL) 1899 return; 1900 1901 if (TREE_STATIC (decl) || DECL_EXTERNAL (decl)) 1902 return; 1903 1904 /* Create the RTL representation for the variable. */ 1905 1906 if (type == error_mark_node) 1907 SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx)); 1908 1909 else if (DECL_SIZE (decl) == 0) 1910 { 1911 /* Variable with incomplete type. */ 1912 rtx x; 1913 if (DECL_INITIAL (decl) == 0) 1914 /* Error message was already done; now avoid a crash. */ 1915 x = gen_rtx_MEM (BLKmode, const0_rtx); 1916 else 1917 /* An initializer is going to decide the size of this array. 1918 Until we know the size, represent its address with a reg. */ 1919 x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode)); 1920 1921 set_mem_attributes (x, decl, 1); 1922 SET_DECL_RTL (decl, x); 1923 } 1924 else if (use_register_for_decl (decl)) 1925 { 1926 /* Automatic variable that can go in a register. */ 1927 enum machine_mode reg_mode = promote_decl_mode (decl, NULL); 1928 1929 SET_DECL_RTL (decl, gen_reg_rtx (reg_mode)); 1930 1931 /* Note if the object is a user variable. */ 1932 if (!DECL_ARTIFICIAL (decl)) 1933 mark_user_reg (DECL_RTL (decl)); 1934 1935 if (POINTER_TYPE_P (type)) 1936 mark_reg_pointer (DECL_RTL (decl), 1937 TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl)))); 1938 } 1939 1940 else 1941 { 1942 rtx oldaddr = 0; 1943 rtx addr; 1944 rtx x; 1945 1946 /* Variable-sized decls are dealt with in the gimplifier. */ 1947 gcc_assert (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST); 1948 1949 /* If we previously made RTL for this decl, it must be an array 1950 whose size was determined by the initializer. 1951 The old address was a register; set that register now 1952 to the proper address. */ 1953 if (DECL_RTL_SET_P (decl)) 1954 { 1955 gcc_assert (MEM_P (DECL_RTL (decl))); 1956 gcc_assert (REG_P (XEXP (DECL_RTL (decl), 0))); 1957 oldaddr = XEXP (DECL_RTL (decl), 0); 1958 } 1959 1960 /* Set alignment we actually gave this decl. */ 1961 DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT 1962 : GET_MODE_BITSIZE (DECL_MODE (decl))); 1963 DECL_USER_ALIGN (decl) = 0; 1964 1965 x = assign_temp (decl, 1, 1, 1); 1966 set_mem_attributes (x, decl, 1); 1967 SET_DECL_RTL (decl, x); 1968 1969 if (oldaddr) 1970 { 1971 addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr); 1972 if (addr != oldaddr) 1973 emit_move_insn (oldaddr, addr); 1974 } 1975 } 1976 } 1977 1978 /* Emit code to save the current value of stack. */ 1979 rtx 1980 expand_stack_save (void) 1981 { 1982 rtx ret = NULL_RTX; 1983 1984 do_pending_stack_adjust (); 1985 emit_stack_save (SAVE_BLOCK, &ret, NULL_RTX); 1986 return ret; 1987 } 1988 1989 /* Emit code to restore the current value of stack. */ 1990 void 1991 expand_stack_restore (tree var) 1992 { 1993 rtx sa = expand_normal (var); 1994 1995 sa = convert_memory_address (Pmode, sa); 1996 emit_stack_restore (SAVE_BLOCK, sa, NULL_RTX); 1997 } 1998 1999 /* Do the insertion of a case label into case_list. The labels are 2000 fed to us in descending order from the sorted vector of case labels used 2001 in the tree part of the middle end. So the list we construct is 2002 sorted in ascending order. The bounds on the case range, LOW and HIGH, 2003 are converted to case's index type TYPE. */ 2004 2005 static struct case_node * 2006 add_case_node (struct case_node *head, tree type, tree low, tree high, 2007 tree label, alloc_pool case_node_pool) 2008 { 2009 tree min_value, max_value; 2010 struct case_node *r; 2011 2012 gcc_assert (TREE_CODE (low) == INTEGER_CST); 2013 gcc_assert (!high || TREE_CODE (high) == INTEGER_CST); 2014 2015 min_value = TYPE_MIN_VALUE (type); 2016 max_value = TYPE_MAX_VALUE (type); 2017 2018 /* If there's no HIGH value, then this is not a case range; it's 2019 just a simple case label. But that's just a degenerate case 2020 range. 2021 If the bounds are equal, turn this into the one-value case. */ 2022 if (!high || tree_int_cst_equal (low, high)) 2023 { 2024 /* If the simple case value is unreachable, ignore it. */ 2025 if ((TREE_CODE (min_value) == INTEGER_CST 2026 && tree_int_cst_compare (low, min_value) < 0) 2027 || (TREE_CODE (max_value) == INTEGER_CST 2028 && tree_int_cst_compare (low, max_value) > 0)) 2029 return head; 2030 low = fold_convert (type, low); 2031 high = low; 2032 } 2033 else 2034 { 2035 /* If the entire case range is unreachable, ignore it. */ 2036 if ((TREE_CODE (min_value) == INTEGER_CST 2037 && tree_int_cst_compare (high, min_value) < 0) 2038 || (TREE_CODE (max_value) == INTEGER_CST 2039 && tree_int_cst_compare (low, max_value) > 0)) 2040 return head; 2041 2042 /* If the lower bound is less than the index type's minimum 2043 value, truncate the range bounds. */ 2044 if (TREE_CODE (min_value) == INTEGER_CST 2045 && tree_int_cst_compare (low, min_value) < 0) 2046 low = min_value; 2047 low = fold_convert (type, low); 2048 2049 /* If the upper bound is greater than the index type's maximum 2050 value, truncate the range bounds. */ 2051 if (TREE_CODE (max_value) == INTEGER_CST 2052 && tree_int_cst_compare (high, max_value) > 0) 2053 high = max_value; 2054 high = fold_convert (type, high); 2055 } 2056 2057 2058 /* Add this label to the chain. Make sure to drop overflow flags. */ 2059 r = (struct case_node *) pool_alloc (case_node_pool); 2060 r->low = build_int_cst_wide (TREE_TYPE (low), TREE_INT_CST_LOW (low), 2061 TREE_INT_CST_HIGH (low)); 2062 r->high = build_int_cst_wide (TREE_TYPE (high), TREE_INT_CST_LOW (high), 2063 TREE_INT_CST_HIGH (high)); 2064 r->code_label = label; 2065 r->parent = r->left = NULL; 2066 r->right = head; 2067 return r; 2068 } 2069 2070 /* Maximum number of case bit tests. */ 2071 #define MAX_CASE_BIT_TESTS 3 2072 2073 /* By default, enable case bit tests on targets with ashlsi3. */ 2074 #ifndef CASE_USE_BIT_TESTS 2075 #define CASE_USE_BIT_TESTS (optab_handler (ashl_optab, word_mode)->insn_code \ 2076 != CODE_FOR_nothing) 2077 #endif 2078 2079 2080 /* A case_bit_test represents a set of case nodes that may be 2081 selected from using a bit-wise comparison. HI and LO hold 2082 the integer to be tested against, LABEL contains the label 2083 to jump to upon success and BITS counts the number of case 2084 nodes handled by this test, typically the number of bits 2085 set in HI:LO. */ 2086 2087 struct case_bit_test 2088 { 2089 HOST_WIDE_INT hi; 2090 HOST_WIDE_INT lo; 2091 rtx label; 2092 int bits; 2093 }; 2094 2095 /* Determine whether "1 << x" is relatively cheap in word_mode. */ 2096 2097 static 2098 bool lshift_cheap_p (void) 2099 { 2100 static bool init = false; 2101 static bool cheap = true; 2102 2103 if (!init) 2104 { 2105 rtx reg = gen_rtx_REG (word_mode, 10000); 2106 int cost = rtx_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg), SET, 2107 optimize_insn_for_speed_p ()); 2108 cheap = cost < COSTS_N_INSNS (3); 2109 init = true; 2110 } 2111 2112 return cheap; 2113 } 2114 2115 /* Comparison function for qsort to order bit tests by decreasing 2116 number of case nodes, i.e. the node with the most cases gets 2117 tested first. */ 2118 2119 static int 2120 case_bit_test_cmp (const void *p1, const void *p2) 2121 { 2122 const struct case_bit_test *const d1 = (const struct case_bit_test *) p1; 2123 const struct case_bit_test *const d2 = (const struct case_bit_test *) p2; 2124 2125 if (d2->bits != d1->bits) 2126 return d2->bits - d1->bits; 2127 2128 /* Stabilize the sort. */ 2129 return CODE_LABEL_NUMBER (d2->label) - CODE_LABEL_NUMBER (d1->label); 2130 } 2131 2132 /* Expand a switch statement by a short sequence of bit-wise 2133 comparisons. "switch(x)" is effectively converted into 2134 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are 2135 integer constants. 2136 2137 INDEX_EXPR is the value being switched on, which is of 2138 type INDEX_TYPE. MINVAL is the lowest case value of in 2139 the case nodes, of INDEX_TYPE type, and RANGE is highest 2140 value minus MINVAL, also of type INDEX_TYPE. NODES is 2141 the set of case nodes, and DEFAULT_LABEL is the label to 2142 branch to should none of the cases match. 2143 2144 There *MUST* be MAX_CASE_BIT_TESTS or less unique case 2145 node targets. */ 2146 2147 static void 2148 emit_case_bit_tests (tree index_type, tree index_expr, tree minval, 2149 tree range, case_node_ptr nodes, rtx default_label) 2150 { 2151 struct case_bit_test test[MAX_CASE_BIT_TESTS]; 2152 enum machine_mode mode; 2153 rtx expr, index, label; 2154 unsigned int i,j,lo,hi; 2155 struct case_node *n; 2156 unsigned int count; 2157 2158 count = 0; 2159 for (n = nodes; n; n = n->right) 2160 { 2161 label = label_rtx (n->code_label); 2162 for (i = 0; i < count; i++) 2163 if (label == test[i].label) 2164 break; 2165 2166 if (i == count) 2167 { 2168 gcc_assert (count < MAX_CASE_BIT_TESTS); 2169 test[i].hi = 0; 2170 test[i].lo = 0; 2171 test[i].label = label; 2172 test[i].bits = 1; 2173 count++; 2174 } 2175 else 2176 test[i].bits++; 2177 2178 lo = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 2179 n->low, minval), 1); 2180 hi = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 2181 n->high, minval), 1); 2182 for (j = lo; j <= hi; j++) 2183 if (j >= HOST_BITS_PER_WIDE_INT) 2184 test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT); 2185 else 2186 test[i].lo |= (HOST_WIDE_INT) 1 << j; 2187 } 2188 2189 qsort (test, count, sizeof(*test), case_bit_test_cmp); 2190 2191 index_expr = fold_build2 (MINUS_EXPR, index_type, 2192 fold_convert (index_type, index_expr), 2193 fold_convert (index_type, minval)); 2194 index = expand_normal (index_expr); 2195 do_pending_stack_adjust (); 2196 2197 mode = TYPE_MODE (index_type); 2198 expr = expand_normal (range); 2199 if (default_label) 2200 emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1, 2201 default_label); 2202 2203 index = convert_to_mode (word_mode, index, 0); 2204 index = expand_binop (word_mode, ashl_optab, const1_rtx, 2205 index, NULL_RTX, 1, OPTAB_WIDEN); 2206 2207 for (i = 0; i < count; i++) 2208 { 2209 expr = immed_double_const (test[i].lo, test[i].hi, word_mode); 2210 expr = expand_binop (word_mode, and_optab, index, expr, 2211 NULL_RTX, 1, OPTAB_WIDEN); 2212 emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX, 2213 word_mode, 1, test[i].label); 2214 } 2215 2216 if (default_label) 2217 emit_jump (default_label); 2218 } 2219 2220 #ifndef HAVE_casesi 2221 #define HAVE_casesi 0 2222 #endif 2223 2224 #ifndef HAVE_tablejump 2225 #define HAVE_tablejump 0 2226 #endif 2227 2228 /* Terminate a case (Pascal/Ada) or switch (C) statement 2229 in which ORIG_INDEX is the expression to be tested. 2230 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX 2231 type as given in the source before any compiler conversions. 2232 Generate the code to test it and jump to the right place. */ 2233 2234 void 2235 expand_case (gimple stmt) 2236 { 2237 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE; 2238 rtx default_label = 0; 2239 struct case_node *n; 2240 unsigned int count, uniq; 2241 rtx index; 2242 rtx table_label; 2243 int ncases; 2244 rtx *labelvec; 2245 int i; 2246 rtx before_case, end, lab; 2247 2248 tree index_expr = gimple_switch_index (stmt); 2249 tree index_type = TREE_TYPE (index_expr); 2250 int unsignedp = TYPE_UNSIGNED (index_type); 2251 2252 /* The insn after which the case dispatch should finally 2253 be emitted. Zero for a dummy. */ 2254 rtx start; 2255 2256 /* A list of case labels; it is first built as a list and it may then 2257 be rearranged into a nearly balanced binary tree. */ 2258 struct case_node *case_list = 0; 2259 2260 /* Label to jump to if no case matches. */ 2261 tree default_label_decl = NULL_TREE; 2262 2263 alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool", 2264 sizeof (struct case_node), 2265 100); 2266 2267 do_pending_stack_adjust (); 2268 2269 /* An ERROR_MARK occurs for various reasons including invalid data type. */ 2270 if (index_type != error_mark_node) 2271 { 2272 tree elt; 2273 bitmap label_bitmap; 2274 int stopi = 0; 2275 2276 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index 2277 expressions being INTEGER_CST. */ 2278 gcc_assert (TREE_CODE (index_expr) != INTEGER_CST); 2279 2280 /* The default case, if ever taken, is the first element. */ 2281 elt = gimple_switch_label (stmt, 0); 2282 if (!CASE_LOW (elt) && !CASE_HIGH (elt)) 2283 { 2284 default_label_decl = CASE_LABEL (elt); 2285 stopi = 1; 2286 } 2287 2288 for (i = gimple_switch_num_labels (stmt) - 1; i >= stopi; --i) 2289 { 2290 tree low, high; 2291 elt = gimple_switch_label (stmt, i); 2292 2293 low = CASE_LOW (elt); 2294 gcc_assert (low); 2295 high = CASE_HIGH (elt); 2296 2297 /* Discard empty ranges. */ 2298 if (high && tree_int_cst_lt (high, low)) 2299 continue; 2300 2301 case_list = add_case_node (case_list, index_type, low, high, 2302 CASE_LABEL (elt), case_node_pool); 2303 } 2304 2305 2306 before_case = start = get_last_insn (); 2307 if (default_label_decl) 2308 default_label = label_rtx (default_label_decl); 2309 2310 /* Get upper and lower bounds of case values. */ 2311 2312 uniq = 0; 2313 count = 0; 2314 label_bitmap = BITMAP_ALLOC (NULL); 2315 for (n = case_list; n; n = n->right) 2316 { 2317 /* Count the elements and track the largest and smallest 2318 of them (treating them as signed even if they are not). */ 2319 if (count++ == 0) 2320 { 2321 minval = n->low; 2322 maxval = n->high; 2323 } 2324 else 2325 { 2326 if (tree_int_cst_lt (n->low, minval)) 2327 minval = n->low; 2328 if (tree_int_cst_lt (maxval, n->high)) 2329 maxval = n->high; 2330 } 2331 /* A range counts double, since it requires two compares. */ 2332 if (! tree_int_cst_equal (n->low, n->high)) 2333 count++; 2334 2335 /* If we have not seen this label yet, then increase the 2336 number of unique case node targets seen. */ 2337 lab = label_rtx (n->code_label); 2338 if (!bitmap_bit_p (label_bitmap, CODE_LABEL_NUMBER (lab))) 2339 { 2340 bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab)); 2341 uniq++; 2342 } 2343 } 2344 2345 BITMAP_FREE (label_bitmap); 2346 2347 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single 2348 destination, such as one with a default case only. However, 2349 it doesn't remove cases that are out of range for the switch 2350 type, so we may still get a zero here. */ 2351 if (count == 0) 2352 { 2353 if (default_label) 2354 emit_jump (default_label); 2355 free_alloc_pool (case_node_pool); 2356 return; 2357 } 2358 2359 /* Compute span of values. */ 2360 range = fold_build2 (MINUS_EXPR, index_type, maxval, minval); 2361 2362 /* Try implementing this switch statement by a short sequence of 2363 bit-wise comparisons. However, we let the binary-tree case 2364 below handle constant index expressions. */ 2365 if (CASE_USE_BIT_TESTS 2366 && ! TREE_CONSTANT (index_expr) 2367 && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0 2368 && compare_tree_int (range, 0) > 0 2369 && lshift_cheap_p () 2370 && ((uniq == 1 && count >= 3) 2371 || (uniq == 2 && count >= 5) 2372 || (uniq == 3 && count >= 6))) 2373 { 2374 /* Optimize the case where all the case values fit in a 2375 word without having to subtract MINVAL. In this case, 2376 we can optimize away the subtraction. */ 2377 if (compare_tree_int (minval, 0) > 0 2378 && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0) 2379 { 2380 minval = build_int_cst (index_type, 0); 2381 range = maxval; 2382 } 2383 emit_case_bit_tests (index_type, index_expr, minval, range, 2384 case_list, default_label); 2385 } 2386 2387 /* If range of values is much bigger than number of values, 2388 make a sequence of conditional branches instead of a dispatch. 2389 If the switch-index is a constant, do it this way 2390 because we can optimize it. */ 2391 2392 else if (count < targetm.case_values_threshold () 2393 || compare_tree_int (range, 2394 (optimize_insn_for_size_p () ? 3 : 10) * count) > 0 2395 /* RANGE may be signed, and really large ranges will show up 2396 as negative numbers. */ 2397 || compare_tree_int (range, 0) < 0 2398 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT 2399 || flag_pic 2400 #endif 2401 || !flag_jump_tables 2402 || TREE_CONSTANT (index_expr) 2403 /* If neither casesi or tablejump is available, we can 2404 only go this way. */ 2405 || (!HAVE_casesi && !HAVE_tablejump)) 2406 { 2407 index = expand_normal (index_expr); 2408 2409 /* If the index is a short or char that we do not have 2410 an insn to handle comparisons directly, convert it to 2411 a full integer now, rather than letting each comparison 2412 generate the conversion. */ 2413 2414 if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT 2415 && ! have_insn_for (COMPARE, GET_MODE (index))) 2416 { 2417 enum machine_mode wider_mode; 2418 for (wider_mode = GET_MODE (index); wider_mode != VOIDmode; 2419 wider_mode = GET_MODE_WIDER_MODE (wider_mode)) 2420 if (have_insn_for (COMPARE, wider_mode)) 2421 { 2422 index = convert_to_mode (wider_mode, index, unsignedp); 2423 break; 2424 } 2425 } 2426 2427 do_pending_stack_adjust (); 2428 2429 if (MEM_P (index)) 2430 index = copy_to_reg (index); 2431 2432 /* We generate a binary decision tree to select the 2433 appropriate target code. This is done as follows: 2434 2435 The list of cases is rearranged into a binary tree, 2436 nearly optimal assuming equal probability for each case. 2437 2438 The tree is transformed into RTL, eliminating 2439 redundant test conditions at the same time. 2440 2441 If program flow could reach the end of the 2442 decision tree an unconditional jump to the 2443 default code is emitted. */ 2444 2445 use_cost_table = estimate_case_costs (case_list); 2446 balance_case_nodes (&case_list, NULL); 2447 emit_case_nodes (index, case_list, default_label, index_type); 2448 if (default_label) 2449 emit_jump (default_label); 2450 } 2451 else 2452 { 2453 rtx fallback_label = label_rtx (case_list->code_label); 2454 table_label = gen_label_rtx (); 2455 if (! try_casesi (index_type, index_expr, minval, range, 2456 table_label, default_label, fallback_label)) 2457 { 2458 bool ok; 2459 2460 /* Index jumptables from zero for suitable values of 2461 minval to avoid a subtraction. */ 2462 if (optimize_insn_for_speed_p () 2463 && compare_tree_int (minval, 0) > 0 2464 && compare_tree_int (minval, 3) < 0) 2465 { 2466 minval = build_int_cst (index_type, 0); 2467 range = maxval; 2468 } 2469 2470 ok = try_tablejump (index_type, index_expr, minval, range, 2471 table_label, default_label); 2472 gcc_assert (ok); 2473 } 2474 2475 /* Get table of labels to jump to, in order of case index. */ 2476 2477 ncases = tree_low_cst (range, 0) + 1; 2478 labelvec = XALLOCAVEC (rtx, ncases); 2479 memset (labelvec, 0, ncases * sizeof (rtx)); 2480 2481 for (n = case_list; n; n = n->right) 2482 { 2483 /* Compute the low and high bounds relative to the minimum 2484 value since that should fit in a HOST_WIDE_INT while the 2485 actual values may not. */ 2486 HOST_WIDE_INT i_low 2487 = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 2488 n->low, minval), 1); 2489 HOST_WIDE_INT i_high 2490 = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 2491 n->high, minval), 1); 2492 HOST_WIDE_INT i; 2493 2494 for (i = i_low; i <= i_high; i ++) 2495 labelvec[i] 2496 = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label)); 2497 } 2498 2499 /* Fill in the gaps with the default. We may have gaps at 2500 the beginning if we tried to avoid the minval subtraction, 2501 so substitute some label even if the default label was 2502 deemed unreachable. */ 2503 if (!default_label) 2504 default_label = fallback_label; 2505 for (i = 0; i < ncases; i++) 2506 if (labelvec[i] == 0) 2507 labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label); 2508 2509 /* Output the table. */ 2510 emit_label (table_label); 2511 2512 if (CASE_VECTOR_PC_RELATIVE || flag_pic) 2513 emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE, 2514 gen_rtx_LABEL_REF (Pmode, table_label), 2515 gen_rtvec_v (ncases, labelvec), 2516 const0_rtx, const0_rtx)); 2517 else 2518 emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE, 2519 gen_rtvec_v (ncases, labelvec))); 2520 2521 /* Record no drop-through after the table. */ 2522 emit_barrier (); 2523 } 2524 2525 before_case = NEXT_INSN (before_case); 2526 end = get_last_insn (); 2527 reorder_insns (before_case, end, start); 2528 } 2529 2530 free_temp_slots (); 2531 free_alloc_pool (case_node_pool); 2532 } 2533 2534 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */ 2535 2536 static void 2537 do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label, 2538 int unsignedp) 2539 { 2540 do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode, 2541 NULL_RTX, NULL_RTX, label, -1); 2542 } 2543 2544 /* Not all case values are encountered equally. This function 2545 uses a heuristic to weight case labels, in cases where that 2546 looks like a reasonable thing to do. 2547 2548 Right now, all we try to guess is text, and we establish the 2549 following weights: 2550 2551 chars above space: 16 2552 digits: 16 2553 default: 12 2554 space, punct: 8 2555 tab: 4 2556 newline: 2 2557 other "\" chars: 1 2558 remaining chars: 0 2559 2560 If we find any cases in the switch that are not either -1 or in the range 2561 of valid ASCII characters, or are control characters other than those 2562 commonly used with "\", don't treat this switch scanning text. 2563 2564 Return 1 if these nodes are suitable for cost estimation, otherwise 2565 return 0. */ 2566 2567 static int 2568 estimate_case_costs (case_node_ptr node) 2569 { 2570 tree min_ascii = integer_minus_one_node; 2571 tree max_ascii = build_int_cst (TREE_TYPE (node->high), 127); 2572 case_node_ptr n; 2573 int i; 2574 2575 /* If we haven't already made the cost table, make it now. Note that the 2576 lower bound of the table is -1, not zero. */ 2577 2578 if (! cost_table_initialized) 2579 { 2580 cost_table_initialized = 1; 2581 2582 for (i = 0; i < 128; i++) 2583 { 2584 if (ISALNUM (i)) 2585 COST_TABLE (i) = 16; 2586 else if (ISPUNCT (i)) 2587 COST_TABLE (i) = 8; 2588 else if (ISCNTRL (i)) 2589 COST_TABLE (i) = -1; 2590 } 2591 2592 COST_TABLE (' ') = 8; 2593 COST_TABLE ('\t') = 4; 2594 COST_TABLE ('\0') = 4; 2595 COST_TABLE ('\n') = 2; 2596 COST_TABLE ('\f') = 1; 2597 COST_TABLE ('\v') = 1; 2598 COST_TABLE ('\b') = 1; 2599 } 2600 2601 /* See if all the case expressions look like text. It is text if the 2602 constant is >= -1 and the highest constant is <= 127. Do all comparisons 2603 as signed arithmetic since we don't want to ever access cost_table with a 2604 value less than -1. Also check that none of the constants in a range 2605 are strange control characters. */ 2606 2607 for (n = node; n; n = n->right) 2608 { 2609 if (tree_int_cst_lt (n->low, min_ascii) 2610 || tree_int_cst_lt (max_ascii, n->high)) 2611 return 0; 2612 2613 for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low); 2614 i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++) 2615 if (COST_TABLE (i) < 0) 2616 return 0; 2617 } 2618 2619 /* All interesting values are within the range of interesting 2620 ASCII characters. */ 2621 return 1; 2622 } 2623 2624 /* Take an ordered list of case nodes 2625 and transform them into a near optimal binary tree, 2626 on the assumption that any target code selection value is as 2627 likely as any other. 2628 2629 The transformation is performed by splitting the ordered 2630 list into two equal sections plus a pivot. The parts are 2631 then attached to the pivot as left and right branches. Each 2632 branch is then transformed recursively. */ 2633 2634 static void 2635 balance_case_nodes (case_node_ptr *head, case_node_ptr parent) 2636 { 2637 case_node_ptr np; 2638 2639 np = *head; 2640 if (np) 2641 { 2642 int cost = 0; 2643 int i = 0; 2644 int ranges = 0; 2645 case_node_ptr *npp; 2646 case_node_ptr left; 2647 2648 /* Count the number of entries on branch. Also count the ranges. */ 2649 2650 while (np) 2651 { 2652 if (!tree_int_cst_equal (np->low, np->high)) 2653 { 2654 ranges++; 2655 if (use_cost_table) 2656 cost += COST_TABLE (TREE_INT_CST_LOW (np->high)); 2657 } 2658 2659 if (use_cost_table) 2660 cost += COST_TABLE (TREE_INT_CST_LOW (np->low)); 2661 2662 i++; 2663 np = np->right; 2664 } 2665 2666 if (i > 2) 2667 { 2668 /* Split this list if it is long enough for that to help. */ 2669 npp = head; 2670 left = *npp; 2671 if (use_cost_table) 2672 { 2673 /* Find the place in the list that bisects the list's total cost, 2674 Here I gets half the total cost. */ 2675 int n_moved = 0; 2676 i = (cost + 1) / 2; 2677 while (1) 2678 { 2679 /* Skip nodes while their cost does not reach that amount. */ 2680 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high)) 2681 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high)); 2682 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low)); 2683 if (i <= 0) 2684 break; 2685 npp = &(*npp)->right; 2686 n_moved += 1; 2687 } 2688 if (n_moved == 0) 2689 { 2690 /* Leave this branch lopsided, but optimize left-hand 2691 side and fill in `parent' fields for right-hand side. */ 2692 np = *head; 2693 np->parent = parent; 2694 balance_case_nodes (&np->left, np); 2695 for (; np->right; np = np->right) 2696 np->right->parent = np; 2697 return; 2698 } 2699 } 2700 /* If there are just three nodes, split at the middle one. */ 2701 else if (i == 3) 2702 npp = &(*npp)->right; 2703 else 2704 { 2705 /* Find the place in the list that bisects the list's total cost, 2706 where ranges count as 2. 2707 Here I gets half the total cost. */ 2708 i = (i + ranges + 1) / 2; 2709 while (1) 2710 { 2711 /* Skip nodes while their cost does not reach that amount. */ 2712 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high)) 2713 i--; 2714 i--; 2715 if (i <= 0) 2716 break; 2717 npp = &(*npp)->right; 2718 } 2719 } 2720 *head = np = *npp; 2721 *npp = 0; 2722 np->parent = parent; 2723 np->left = left; 2724 2725 /* Optimize each of the two split parts. */ 2726 balance_case_nodes (&np->left, np); 2727 balance_case_nodes (&np->right, np); 2728 } 2729 else 2730 { 2731 /* Else leave this branch as one level, 2732 but fill in `parent' fields. */ 2733 np = *head; 2734 np->parent = parent; 2735 for (; np->right; np = np->right) 2736 np->right->parent = np; 2737 } 2738 } 2739 } 2740 2741 /* Search the parent sections of the case node tree 2742 to see if a test for the lower bound of NODE would be redundant. 2743 INDEX_TYPE is the type of the index expression. 2744 2745 The instructions to generate the case decision tree are 2746 output in the same order as nodes are processed so it is 2747 known that if a parent node checks the range of the current 2748 node minus one that the current node is bounded at its lower 2749 span. Thus the test would be redundant. */ 2750 2751 static int 2752 node_has_low_bound (case_node_ptr node, tree index_type) 2753 { 2754 tree low_minus_one; 2755 case_node_ptr pnode; 2756 2757 /* If the lower bound of this node is the lowest value in the index type, 2758 we need not test it. */ 2759 2760 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type))) 2761 return 1; 2762 2763 /* If this node has a left branch, the value at the left must be less 2764 than that at this node, so it cannot be bounded at the bottom and 2765 we need not bother testing any further. */ 2766 2767 if (node->left) 2768 return 0; 2769 2770 low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), 2771 node->low, 2772 build_int_cst (TREE_TYPE (node->low), 1)); 2773 2774 /* If the subtraction above overflowed, we can't verify anything. 2775 Otherwise, look for a parent that tests our value - 1. */ 2776 2777 if (! tree_int_cst_lt (low_minus_one, node->low)) 2778 return 0; 2779 2780 for (pnode = node->parent; pnode; pnode = pnode->parent) 2781 if (tree_int_cst_equal (low_minus_one, pnode->high)) 2782 return 1; 2783 2784 return 0; 2785 } 2786 2787 /* Search the parent sections of the case node tree 2788 to see if a test for the upper bound of NODE would be redundant. 2789 INDEX_TYPE is the type of the index expression. 2790 2791 The instructions to generate the case decision tree are 2792 output in the same order as nodes are processed so it is 2793 known that if a parent node checks the range of the current 2794 node plus one that the current node is bounded at its upper 2795 span. Thus the test would be redundant. */ 2796 2797 static int 2798 node_has_high_bound (case_node_ptr node, tree index_type) 2799 { 2800 tree high_plus_one; 2801 case_node_ptr pnode; 2802 2803 /* If there is no upper bound, obviously no test is needed. */ 2804 2805 if (TYPE_MAX_VALUE (index_type) == NULL) 2806 return 1; 2807 2808 /* If the upper bound of this node is the highest value in the type 2809 of the index expression, we need not test against it. */ 2810 2811 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type))) 2812 return 1; 2813 2814 /* If this node has a right branch, the value at the right must be greater 2815 than that at this node, so it cannot be bounded at the top and 2816 we need not bother testing any further. */ 2817 2818 if (node->right) 2819 return 0; 2820 2821 high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), 2822 node->high, 2823 build_int_cst (TREE_TYPE (node->high), 1)); 2824 2825 /* If the addition above overflowed, we can't verify anything. 2826 Otherwise, look for a parent that tests our value + 1. */ 2827 2828 if (! tree_int_cst_lt (node->high, high_plus_one)) 2829 return 0; 2830 2831 for (pnode = node->parent; pnode; pnode = pnode->parent) 2832 if (tree_int_cst_equal (high_plus_one, pnode->low)) 2833 return 1; 2834 2835 return 0; 2836 } 2837 2838 /* Search the parent sections of the 2839 case node tree to see if both tests for the upper and lower 2840 bounds of NODE would be redundant. */ 2841 2842 static int 2843 node_is_bounded (case_node_ptr node, tree index_type) 2844 { 2845 return (node_has_low_bound (node, index_type) 2846 && node_has_high_bound (node, index_type)); 2847 } 2848 2849 /* Emit step-by-step code to select a case for the value of INDEX. 2850 The thus generated decision tree follows the form of the 2851 case-node binary tree NODE, whose nodes represent test conditions. 2852 INDEX_TYPE is the type of the index of the switch. 2853 2854 Care is taken to prune redundant tests from the decision tree 2855 by detecting any boundary conditions already checked by 2856 emitted rtx. (See node_has_high_bound, node_has_low_bound 2857 and node_is_bounded, above.) 2858 2859 Where the test conditions can be shown to be redundant we emit 2860 an unconditional jump to the target code. As a further 2861 optimization, the subordinates of a tree node are examined to 2862 check for bounded nodes. In this case conditional and/or 2863 unconditional jumps as a result of the boundary check for the 2864 current node are arranged to target the subordinates associated 2865 code for out of bound conditions on the current node. 2866 2867 We can assume that when control reaches the code generated here, 2868 the index value has already been compared with the parents 2869 of this node, and determined to be on the same side of each parent 2870 as this node is. Thus, if this node tests for the value 51, 2871 and a parent tested for 52, we don't need to consider 2872 the possibility of a value greater than 51. If another parent 2873 tests for the value 50, then this node need not test anything. */ 2874 2875 static void 2876 emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, 2877 tree index_type) 2878 { 2879 /* If INDEX has an unsigned type, we must make unsigned branches. */ 2880 int unsignedp = TYPE_UNSIGNED (index_type); 2881 enum machine_mode mode = GET_MODE (index); 2882 enum machine_mode imode = TYPE_MODE (index_type); 2883 2884 /* Handle indices detected as constant during RTL expansion. */ 2885 if (mode == VOIDmode) 2886 mode = imode; 2887 2888 /* See if our parents have already tested everything for us. 2889 If they have, emit an unconditional jump for this node. */ 2890 if (node_is_bounded (node, index_type)) 2891 emit_jump (label_rtx (node->code_label)); 2892 2893 else if (tree_int_cst_equal (node->low, node->high)) 2894 { 2895 /* Node is single valued. First see if the index expression matches 2896 this node and then check our children, if any. */ 2897 2898 do_jump_if_equal (mode, index, 2899 convert_modes (mode, imode, 2900 expand_normal (node->low), 2901 unsignedp), 2902 label_rtx (node->code_label), unsignedp); 2903 2904 if (node->right != 0 && node->left != 0) 2905 { 2906 /* This node has children on both sides. 2907 Dispatch to one side or the other 2908 by comparing the index value with this node's value. 2909 If one subtree is bounded, check that one first, 2910 so we can avoid real branches in the tree. */ 2911 2912 if (node_is_bounded (node->right, index_type)) 2913 { 2914 emit_cmp_and_jump_insns (index, 2915 convert_modes 2916 (mode, imode, 2917 expand_normal (node->high), 2918 unsignedp), 2919 GT, NULL_RTX, mode, unsignedp, 2920 label_rtx (node->right->code_label)); 2921 emit_case_nodes (index, node->left, default_label, index_type); 2922 } 2923 2924 else if (node_is_bounded (node->left, index_type)) 2925 { 2926 emit_cmp_and_jump_insns (index, 2927 convert_modes 2928 (mode, imode, 2929 expand_normal (node->high), 2930 unsignedp), 2931 LT, NULL_RTX, mode, unsignedp, 2932 label_rtx (node->left->code_label)); 2933 emit_case_nodes (index, node->right, default_label, index_type); 2934 } 2935 2936 /* If both children are single-valued cases with no 2937 children, finish up all the work. This way, we can save 2938 one ordered comparison. */ 2939 else if (tree_int_cst_equal (node->right->low, node->right->high) 2940 && node->right->left == 0 2941 && node->right->right == 0 2942 && tree_int_cst_equal (node->left->low, node->left->high) 2943 && node->left->left == 0 2944 && node->left->right == 0) 2945 { 2946 /* Neither node is bounded. First distinguish the two sides; 2947 then emit the code for one side at a time. */ 2948 2949 /* See if the value matches what the right hand side 2950 wants. */ 2951 do_jump_if_equal (mode, index, 2952 convert_modes (mode, imode, 2953 expand_normal (node->right->low), 2954 unsignedp), 2955 label_rtx (node->right->code_label), 2956 unsignedp); 2957 2958 /* See if the value matches what the left hand side 2959 wants. */ 2960 do_jump_if_equal (mode, index, 2961 convert_modes (mode, imode, 2962 expand_normal (node->left->low), 2963 unsignedp), 2964 label_rtx (node->left->code_label), 2965 unsignedp); 2966 } 2967 2968 else 2969 { 2970 /* Neither node is bounded. First distinguish the two sides; 2971 then emit the code for one side at a time. */ 2972 2973 tree test_label 2974 = build_decl (CURR_INSN_LOCATION, 2975 LABEL_DECL, NULL_TREE, NULL_TREE); 2976 2977 /* See if the value is on the right. */ 2978 emit_cmp_and_jump_insns (index, 2979 convert_modes 2980 (mode, imode, 2981 expand_normal (node->high), 2982 unsignedp), 2983 GT, NULL_RTX, mode, unsignedp, 2984 label_rtx (test_label)); 2985 2986 /* Value must be on the left. 2987 Handle the left-hand subtree. */ 2988 emit_case_nodes (index, node->left, default_label, index_type); 2989 /* If left-hand subtree does nothing, 2990 go to default. */ 2991 if (default_label) 2992 emit_jump (default_label); 2993 2994 /* Code branches here for the right-hand subtree. */ 2995 expand_label (test_label); 2996 emit_case_nodes (index, node->right, default_label, index_type); 2997 } 2998 } 2999 3000 else if (node->right != 0 && node->left == 0) 3001 { 3002 /* Here we have a right child but no left so we issue a conditional 3003 branch to default and process the right child. 3004 3005 Omit the conditional branch to default if the right child 3006 does not have any children and is single valued; it would 3007 cost too much space to save so little time. */ 3008 3009 if (node->right->right || node->right->left 3010 || !tree_int_cst_equal (node->right->low, node->right->high)) 3011 { 3012 if (!node_has_low_bound (node, index_type)) 3013 { 3014 emit_cmp_and_jump_insns (index, 3015 convert_modes 3016 (mode, imode, 3017 expand_normal (node->high), 3018 unsignedp), 3019 LT, NULL_RTX, mode, unsignedp, 3020 default_label); 3021 } 3022 3023 emit_case_nodes (index, node->right, default_label, index_type); 3024 } 3025 else 3026 /* We cannot process node->right normally 3027 since we haven't ruled out the numbers less than 3028 this node's value. So handle node->right explicitly. */ 3029 do_jump_if_equal (mode, index, 3030 convert_modes 3031 (mode, imode, 3032 expand_normal (node->right->low), 3033 unsignedp), 3034 label_rtx (node->right->code_label), unsignedp); 3035 } 3036 3037 else if (node->right == 0 && node->left != 0) 3038 { 3039 /* Just one subtree, on the left. */ 3040 if (node->left->left || node->left->right 3041 || !tree_int_cst_equal (node->left->low, node->left->high)) 3042 { 3043 if (!node_has_high_bound (node, index_type)) 3044 { 3045 emit_cmp_and_jump_insns (index, 3046 convert_modes 3047 (mode, imode, 3048 expand_normal (node->high), 3049 unsignedp), 3050 GT, NULL_RTX, mode, unsignedp, 3051 default_label); 3052 } 3053 3054 emit_case_nodes (index, node->left, default_label, index_type); 3055 } 3056 else 3057 /* We cannot process node->left normally 3058 since we haven't ruled out the numbers less than 3059 this node's value. So handle node->left explicitly. */ 3060 do_jump_if_equal (mode, index, 3061 convert_modes 3062 (mode, imode, 3063 expand_normal (node->left->low), 3064 unsignedp), 3065 label_rtx (node->left->code_label), unsignedp); 3066 } 3067 } 3068 else 3069 { 3070 /* Node is a range. These cases are very similar to those for a single 3071 value, except that we do not start by testing whether this node 3072 is the one to branch to. */ 3073 3074 if (node->right != 0 && node->left != 0) 3075 { 3076 /* Node has subtrees on both sides. 3077 If the right-hand subtree is bounded, 3078 test for it first, since we can go straight there. 3079 Otherwise, we need to make a branch in the control structure, 3080 then handle the two subtrees. */ 3081 tree test_label = 0; 3082 3083 if (node_is_bounded (node->right, index_type)) 3084 /* Right hand node is fully bounded so we can eliminate any 3085 testing and branch directly to the target code. */ 3086 emit_cmp_and_jump_insns (index, 3087 convert_modes 3088 (mode, imode, 3089 expand_normal (node->high), 3090 unsignedp), 3091 GT, NULL_RTX, mode, unsignedp, 3092 label_rtx (node->right->code_label)); 3093 else 3094 { 3095 /* Right hand node requires testing. 3096 Branch to a label where we will handle it later. */ 3097 3098 test_label = build_decl (CURR_INSN_LOCATION, 3099 LABEL_DECL, NULL_TREE, NULL_TREE); 3100 emit_cmp_and_jump_insns (index, 3101 convert_modes 3102 (mode, imode, 3103 expand_normal (node->high), 3104 unsignedp), 3105 GT, NULL_RTX, mode, unsignedp, 3106 label_rtx (test_label)); 3107 } 3108 3109 /* Value belongs to this node or to the left-hand subtree. */ 3110 3111 emit_cmp_and_jump_insns (index, 3112 convert_modes 3113 (mode, imode, 3114 expand_normal (node->low), 3115 unsignedp), 3116 GE, NULL_RTX, mode, unsignedp, 3117 label_rtx (node->code_label)); 3118 3119 /* Handle the left-hand subtree. */ 3120 emit_case_nodes (index, node->left, default_label, index_type); 3121 3122 /* If right node had to be handled later, do that now. */ 3123 3124 if (test_label) 3125 { 3126 /* If the left-hand subtree fell through, 3127 don't let it fall into the right-hand subtree. */ 3128 if (default_label) 3129 emit_jump (default_label); 3130 3131 expand_label (test_label); 3132 emit_case_nodes (index, node->right, default_label, index_type); 3133 } 3134 } 3135 3136 else if (node->right != 0 && node->left == 0) 3137 { 3138 /* Deal with values to the left of this node, 3139 if they are possible. */ 3140 if (!node_has_low_bound (node, index_type)) 3141 { 3142 emit_cmp_and_jump_insns (index, 3143 convert_modes 3144 (mode, imode, 3145 expand_normal (node->low), 3146 unsignedp), 3147 LT, NULL_RTX, mode, unsignedp, 3148 default_label); 3149 } 3150 3151 /* Value belongs to this node or to the right-hand subtree. */ 3152 3153 emit_cmp_and_jump_insns (index, 3154 convert_modes 3155 (mode, imode, 3156 expand_normal (node->high), 3157 unsignedp), 3158 LE, NULL_RTX, mode, unsignedp, 3159 label_rtx (node->code_label)); 3160 3161 emit_case_nodes (index, node->right, default_label, index_type); 3162 } 3163 3164 else if (node->right == 0 && node->left != 0) 3165 { 3166 /* Deal with values to the right of this node, 3167 if they are possible. */ 3168 if (!node_has_high_bound (node, index_type)) 3169 { 3170 emit_cmp_and_jump_insns (index, 3171 convert_modes 3172 (mode, imode, 3173 expand_normal (node->high), 3174 unsignedp), 3175 GT, NULL_RTX, mode, unsignedp, 3176 default_label); 3177 } 3178 3179 /* Value belongs to this node or to the left-hand subtree. */ 3180 3181 emit_cmp_and_jump_insns (index, 3182 convert_modes 3183 (mode, imode, 3184 expand_normal (node->low), 3185 unsignedp), 3186 GE, NULL_RTX, mode, unsignedp, 3187 label_rtx (node->code_label)); 3188 3189 emit_case_nodes (index, node->left, default_label, index_type); 3190 } 3191 3192 else 3193 { 3194 /* Node has no children so we check low and high bounds to remove 3195 redundant tests. Only one of the bounds can exist, 3196 since otherwise this node is bounded--a case tested already. */ 3197 int high_bound = node_has_high_bound (node, index_type); 3198 int low_bound = node_has_low_bound (node, index_type); 3199 3200 if (!high_bound && low_bound) 3201 { 3202 emit_cmp_and_jump_insns (index, 3203 convert_modes 3204 (mode, imode, 3205 expand_normal (node->high), 3206 unsignedp), 3207 GT, NULL_RTX, mode, unsignedp, 3208 default_label); 3209 } 3210 3211 else if (!low_bound && high_bound) 3212 { 3213 emit_cmp_and_jump_insns (index, 3214 convert_modes 3215 (mode, imode, 3216 expand_normal (node->low), 3217 unsignedp), 3218 LT, NULL_RTX, mode, unsignedp, 3219 default_label); 3220 } 3221 else if (!low_bound && !high_bound) 3222 { 3223 /* Widen LOW and HIGH to the same width as INDEX. */ 3224 tree type = lang_hooks.types.type_for_mode (mode, unsignedp); 3225 tree low = build1 (CONVERT_EXPR, type, node->low); 3226 tree high = build1 (CONVERT_EXPR, type, node->high); 3227 rtx low_rtx, new_index, new_bound; 3228 3229 /* Instead of doing two branches, emit one unsigned branch for 3230 (index-low) > (high-low). */ 3231 low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL); 3232 new_index = expand_simple_binop (mode, MINUS, index, low_rtx, 3233 NULL_RTX, unsignedp, 3234 OPTAB_WIDEN); 3235 new_bound = expand_expr (fold_build2 (MINUS_EXPR, type, 3236 high, low), 3237 NULL_RTX, mode, EXPAND_NORMAL); 3238 3239 emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX, 3240 mode, 1, default_label); 3241 } 3242 3243 emit_jump (label_rtx (node->code_label)); 3244 } 3245 } 3246 } 3247