stmt.c revision 260918
155682Smarkm/* Expands front end tree to back end RTL for GCC 2233294Sstas Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 3233294Sstas 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 4233294Sstas Free Software Foundation, Inc. 555682Smarkm 6233294SstasThis file is part of GCC. 7233294Sstas 8233294SstasGCC is free software; you can redistribute it and/or modify it under 955682Smarkmthe terms of the GNU General Public License as published by the Free 10233294SstasSoftware Foundation; either version 2, or (at your option) any later 11233294Sstasversion. 1255682Smarkm 13233294SstasGCC is distributed in the hope that it will be useful, but WITHOUT ANY 14233294SstasWARRANTY; without even the implied warranty of MERCHANTABILITY or 15233294SstasFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1655682Smarkmfor more details. 17233294Sstas 18233294SstasYou should have received a copy of the GNU General Public License 19233294Sstasalong with GCC; see the file COPYING. If not, write to the Free 2055682SmarkmSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 21233294Sstas02110-1301, USA. */ 22233294Sstas 23233294Sstas/* This file handles the generation of rtl code from tree structure 24233294Sstas above the level of expressions, using subroutines in exp*.c and emit-rtl.c. 25233294Sstas The functions whose names start with `expand_' are called by the 26233294Sstas expander to generate RTL instructions for various kinds of constructs. */ 27233294Sstas 28233294Sstas#include "config.h" 29233294Sstas#include "system.h" 30233294Sstas#include "coretypes.h" 31233294Sstas#include "tm.h" 3255682Smarkm 3355682Smarkm#include "rtl.h" 3455682Smarkm#include "hard-reg-set.h" 3555682Smarkm#include "tree.h" 36233294Sstas#include "tm_p.h" 3755682Smarkm#include "flags.h" 38233294Sstas#include "except.h" 3955682Smarkm#include "function.h" 4055682Smarkm#include "insn-config.h" 4155682Smarkm#include "expr.h" 42233294Sstas#include "libfuncs.h" 43233294Sstas#include "recog.h" 4455682Smarkm#include "machmode.h" 4555682Smarkm#include "toplev.h" 46233294Sstas#include "output.h" 47233294Sstas#include "ggc.h" 48233294Sstas#include "langhooks.h" 4955682Smarkm#include "predict.h" 50233294Sstas#include "optabs.h" 51233294Sstas#include "target.h" 52233294Sstas#include "regs.h" 5355682Smarkm 54233294Sstas/* Functions and data structures for expanding case statements. */ 55233294Sstas 56233294Sstas/* Case label structure, used to hold info on labels within case 57233294Sstas statements. We handle "range" labels; for a single-value label 58233294Sstas as in C, the high and low limits are the same. 5955682Smarkm 6055682Smarkm We start with a vector of case nodes sorted in ascending order, and 6155682Smarkm the default label as the last element in the vector. Before expanding 62233294Sstas to RTL, we transform this vector into a list linked via the RIGHT 6355682Smarkm fields in the case_node struct. Nodes with higher case values are 64178828Sdfr later in the list. 65233294Sstas 6655682Smarkm Switch statements can be output in three forms. A branch table is 67233294Sstas used if there are more than a few labels and the labels are dense 68233294Sstas within the range between the smallest and largest case value. If a 69120948Snectar branch table is used, no further manipulations are done with the case 70120948Snectar node chain. 71233294Sstas 72233294Sstas The alternative to the use of a branch table is to generate a series 73233294Sstas of compare and jump insns. When that is done, we use the LEFT, RIGHT, 74233294Sstas and PARENT fields to hold a binary tree. Initially the tree is 75233294Sstas totally unbalanced, with everything on the right. We balance the tree 76120948Snectar with nodes on the left having lower case values than the parent 77120948Snectar and nodes on the right having higher values. We then output the tree 78120948Snectar in order. 79120948Snectar 80120948Snectar For very small, suitable switch statements, we can generate a series 81120948Snectar of simple bit test and branches instead. */ 82233294Sstas 83120948Snectarstruct case_node GTY(()) 84120948Snectar{ 85120948Snectar struct case_node *left; /* Left son in binary tree */ 86120948Snectar struct case_node *right; /* Right son in binary tree; also node chain */ 87233294Sstas struct case_node *parent; /* Parent of node in binary tree */ 88120948Snectar tree low; /* Lowest index value for this label */ 89233294Sstas tree high; /* Highest index value for this label */ 90120948Snectar tree code_label; /* Label to jump to when node matches */ 91120948Snectar}; 92120948Snectar 93120948Snectartypedef struct case_node case_node; 94120948Snectartypedef struct case_node *case_node_ptr; 95233294Sstas 96178828Sdfr/* These are used by estimate_case_costs and balance_case_nodes. */ 97178828Sdfr 98178828Sdfr/* This must be a signed type, and non-ANSI compilers lack signed char. */ 99178828Sdfrstatic short cost_table_[129]; 100233294Sstasstatic int use_cost_table; 101178828Sdfrstatic int cost_table_initialized; 102233294Sstas 103178828Sdfr/* Special care is needed because we allow -1, but TREE_INT_CST_LOW 104178828Sdfr is unsigned. */ 105178828Sdfr#define COST_TABLE(I) cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)] 106178828Sdfr 107178828Sdfrstatic int n_occurrences (int, const char *); 108233294Sstasstatic bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *); 10955682Smarkmstatic void expand_nl_goto_receiver (void); 11055682Smarkmstatic bool check_operand_nalternatives (tree, tree); 11155682Smarkmstatic bool check_unique_operand_names (tree, tree); 11255682Smarkmstatic char *resolve_operand_name_1 (char *, tree, tree); 11355682Smarkmstatic void expand_null_return_1 (void); 114233294Sstasstatic void expand_value_return (rtx); 11578536Sassarstatic int estimate_case_costs (case_node_ptr); 116233294Sstasstatic bool lshift_cheap_p (void); 11778536Sassarstatic int case_bit_test_cmp (const void *, const void *); 11855682Smarkmstatic void emit_case_bit_tests (tree, tree, tree, tree, case_node_ptr, rtx); 119233294Sstasstatic void balance_case_nodes (case_node_ptr *, case_node_ptr); 12055682Smarkmstatic int node_has_low_bound (case_node_ptr, tree); 12155682Smarkmstatic int node_has_high_bound (case_node_ptr, tree); 12255682Smarkmstatic int node_is_bounded (case_node_ptr, tree); 12355682Smarkmstatic void emit_case_nodes (rtx, case_node_ptr, rtx, tree); 12455682Smarkmstatic struct case_node *add_case_node (struct case_node *, tree, 125233294Sstas tree, tree, tree); 12655682Smarkm 12755682Smarkm 12855682Smarkm/* Return the rtx-label that corresponds to a LABEL_DECL, 12955682Smarkm creating it if necessary. */ 13055682Smarkm 13155682Smarkmrtx 132233294Sstaslabel_rtx (tree label) 13355682Smarkm{ 13455682Smarkm gcc_assert (TREE_CODE (label) == LABEL_DECL); 135233294Sstas 136233294Sstas if (!DECL_RTL_SET_P (label)) 13755682Smarkm { 138233294Sstas rtx r = gen_label_rtx (); 139233294Sstas/* APPLE LOCAL begin for-fsf-4_4 3274130 5295549 */ \ 140233294Sstas unsigned align = DECL_ALIGN_UNIT (label); 141233294Sstas int align_log2 = exact_log2 (align); 142233294Sstas 143233294Sstas/* APPLE LOCAL end for-fsf-4_4 3274130 5295549 */ \ 144233294Sstas SET_DECL_RTL (label, r); 14555682Smarkm if (FORCED_LABEL (label) || DECL_NONLOCAL (label)) 14655682Smarkm LABEL_PRESERVE_P (r) = 1; 14772448Sassar/* APPLE LOCAL begin for-fsf-4_4 3274130 5295549 */ \ 14872448Sassar 14955682Smarkm if (align_log2 >= 0 && align_log2 <= 0xFF) 15078536Sassar SET_LABEL_ALIGN (r, align_log2, align - 1); 151233294Sstas/* APPLE LOCAL end for-fsf-4_4 3274130 5295549 */ \ 15255682Smarkm } 15378536Sassar 15455682Smarkm return DECL_RTL (label); 15555682Smarkm} 15655682Smarkm 15755682Smarkm/* As above, but also put it on the forced-reference list of the 15855682Smarkm function that contains it. */ 15955682Smarkmrtx 160233294Sstasforce_label_rtx (tree label) 16155682Smarkm{ 16255682Smarkm rtx ref = label_rtx (label); 16355682Smarkm tree function = decl_function_context (label); 16455682Smarkm struct function *p; 16555682Smarkm 16655682Smarkm gcc_assert (function); 16755682Smarkm 168233294Sstas if (function != current_function_decl) 169233294Sstas p = find_function_data (function); 170233294Sstas else 17172448Sassar p = cfun; 17255682Smarkm 17372448Sassar p->expr->x_forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref, 17455682Smarkm p->expr->x_forced_labels); 17555682Smarkm return ref; 176233294Sstas} 177233294Sstas 178233294Sstas/* Add an unconditional jump to LABEL as the next sequential instruction. */ 17955682Smarkm 18055682Smarkmvoid 181233294Sstasemit_jump (rtx label) 182233294Sstas{ 183233294Sstas do_pending_stack_adjust (); 184233294Sstas emit_jump_insn (gen_jump (label)); 18572448Sassar emit_barrier (); 18655682Smarkm} 18772448Sassar 188233294Sstas/* Emit code to jump to the address 189233294Sstas specified by the pointer expression EXP. */ 19055682Smarkm 19155682Smarkmvoid 19255682Smarkmexpand_computed_goto (tree exp) 19355682Smarkm{ 194233294Sstas rtx x = expand_normal (exp); 195233294Sstas 196127811Snectar x = convert_memory_address (Pmode, x); 197127811Snectar 198127811Snectar do_pending_stack_adjust (); 199127811Snectar emit_indirect_jump (x); 200127811Snectar} 201127811Snectar 202127811Snectar/* Handle goto statements and the labels that they can go to. */ 203127811Snectar 204127811Snectar/* Specify the location in the RTL code of a label LABEL, 205127811Snectar which is a LABEL_DECL tree node. 206127811Snectar 20755682Smarkm APPLE LOCAL begin for-fsf-4_4 3274130 5295549 208233294Sstas This is used for those labels created by the front-end that survive 209233294Sstas through CFG generation, including all user labels. (Some labels 210233294Sstas are removed by cleanup_dead_labels in tree-cfg.c.) 211233294Sstas 21272448Sassar APPLE LOCAL end for-fsf-4_4 3274130 5295549 21355682Smarkm Note that this has nothing to do with defining label *names*. 21455682Smarkm Languages vary in how they do that and what that even means. */ 21555682Smarkm 21655682Smarkmvoid 21755682Smarkmexpand_label (tree label) 21855682Smarkm{ 21955682Smarkm rtx label_r = label_rtx (label); 22055682Smarkm 22155682Smarkm do_pending_stack_adjust (); 22255682Smarkm emit_label (label_r); 22355682Smarkm if (DECL_NAME (label)) 22455682Smarkm LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label)); 22572448Sassar 22672448Sassar if (DECL_NONLOCAL (label)) 227233294Sstas { 22855682Smarkm expand_nl_goto_receiver (); 229233294Sstas nonlocal_goto_handler_labels 23072448Sassar = gen_rtx_EXPR_LIST (VOIDmode, label_r, 23155682Smarkm nonlocal_goto_handler_labels); 23255682Smarkm } 23355682Smarkm 23455682Smarkm if (FORCED_LABEL (label)) 235127811Snectar forced_labels = gen_rtx_EXPR_LIST (VOIDmode, label_r, forced_labels); 236127811Snectar 23755682Smarkm if (DECL_NONLOCAL (label) || FORCED_LABEL (label)) 23855682Smarkm maybe_set_first_label_num (label_r); 239233294Sstas} 240127811Snectar 241127811Snectar/* Generate RTL code for a `goto' statement with target label LABEL. 242127811Snectar LABEL should be a LABEL_DECL tree node that was or will later be 243127811Snectar defined with `expand_label'. */ 244233294Sstas 245127811Snectarvoid 246127811Snectarexpand_goto (tree label) 247127811Snectar{ 248233294Sstas#ifdef ENABLE_CHECKING 249233294Sstas /* Check for a nonlocal goto to a containing function. Should have 250127811Snectar gotten translated to __builtin_nonlocal_goto. */ 251127811Snectar tree context = decl_function_context (label); 252127811Snectar gcc_assert (!context || context == current_function_decl); 253233294Sstas#endif 254233294Sstas 255233294Sstas emit_jump (label_rtx (label)); 256127811Snectar} 257127811Snectar 258127811Snectar/* Return the number of times character C occurs in string S. */ 259127811Snectarstatic int 260127811Snectarn_occurrences (int c, const char *s) 261127811Snectar{ 262233294Sstas int n = 0; 263127811Snectar while (*s) 264127811Snectar n += (*s++ == c); 265127811Snectar return n; 266127811Snectar} 267127811Snectar 268233294Sstas/* Generate RTL for an asm statement (explicit assembler code). 269127811Snectar STRING is a STRING_CST node containing the assembler code text, 270233294Sstas or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the 271233294Sstas insn is volatile; don't optimize it. */ 272233294Sstas 273233294Sstasstatic void 274233294Sstasexpand_asm (tree string, int vol) 275233294Sstas{ 276233294Sstas rtx body; 27755682Smarkm 278233294Sstas if (TREE_CODE (string) == ADDR_EXPR) 279120948Snectar string = TREE_OPERAND (string, 0); 280120948Snectar 281127811Snectar body = gen_rtx_ASM_INPUT (VOIDmode, 28255682Smarkm ggc_strdup (TREE_STRING_POINTER (string))); 283120948Snectar 284120948Snectar MEM_VOLATILE_P (body) = vol; 285120948Snectar 286233294Sstas emit_insn (body); 287127811Snectar} 288127811Snectar 289120948Snectar/* Parse the output constraint pointed to by *CONSTRAINT_P. It is the 290233294Sstas OPERAND_NUMth output operand, indexed from zero. There are NINPUTS 29155682Smarkm inputs and NOUTPUTS outputs to this extended-asm. Upon return, 29255682Smarkm *ALLOWS_MEM will be TRUE iff the constraint allows the use of a 293233294Sstas memory operand. Similarly, *ALLOWS_REG will be TRUE iff the 29455682Smarkm constraint allows the use of a register operand. And, *IS_INOUT 29555682Smarkm will be true if the operand is read-write, i.e., if it is used as 29655682Smarkm an input as well as an output. If *CONSTRAINT_P is not in 29755682Smarkm canonical form, it will be made canonical. (Note that `+' will be 29855682Smarkm replaced with `=' as part of this process.) 29955682Smarkm 30055682Smarkm Returns TRUE if all went well; FALSE if an error occurred. */ 30155682Smarkm 30255682Smarkmbool 303233294Sstasparse_output_constraint (const char **constraint_p, int operand_num, 304233294Sstas int ninputs, int noutputs, bool *allows_mem, 30555682Smarkm bool *allows_reg, bool *is_inout) 30655682Smarkm{ 307233294Sstas const char *constraint = *constraint_p; 308233294Sstas const char *p; 309233294Sstas 31055682Smarkm /* Assume the constraint doesn't allow the use of either a register 31155682Smarkm or memory. */ 31255682Smarkm *allows_mem = false; 31355682Smarkm *allows_reg = false; 314233294Sstas 31555682Smarkm /* Allow the `=' or `+' to not be at the beginning of the string, 31655682Smarkm since it wasn't explicitly documented that way, and there is a 317233294Sstas large body of code that puts it last. Swap the character to 318233294Sstas the front, so as not to uglify any place else. */ 31955682Smarkm p = strchr (constraint, '='); 32055682Smarkm if (!p) 32155682Smarkm p = strchr (constraint, '+'); 32255682Smarkm 32355682Smarkm /* If the string doesn't contain an `=', issue an error 32455682Smarkm message. */ 325233294Sstas if (!p) 32655682Smarkm { 32755682Smarkm error ("output operand constraint lacks %<=%>"); 32878536Sassar return false; 329233294Sstas } 33055682Smarkm 33178536Sassar /* If the constraint begins with `+', then the operand is both read 33255682Smarkm from and written to. */ 333233294Sstas *is_inout = (*p == '+'); 33455682Smarkm 33555682Smarkm /* Canonicalize the output constraint so that it begins with `='. */ 33655682Smarkm if (p != constraint || *is_inout) 33755682Smarkm { 338233294Sstas char *buf; 33955682Smarkm size_t c_len = strlen (constraint); 34055682Smarkm 34155682Smarkm if (p != constraint) 34255682Smarkm warning (0, "output constraint %qc for operand %d " 34355682Smarkm "is not at the beginning", 34455682Smarkm *p, operand_num); 34555682Smarkm 346127811Snectar /* Make a copy of the constraint. */ 347233294Sstas buf = alloca (c_len + 1); 348127811Snectar strcpy (buf, constraint); 349127811Snectar /* Swap the first character and the `=' or `+'. */ 350127811Snectar buf[p - constraint] = buf[0]; 351127811Snectar /* Make sure the first character is an `='. (Until we do this, 352127811Snectar it might be a `+'.) */ 35355682Smarkm buf[0] = '='; 35455682Smarkm /* Replace the constraint with the canonicalized string. */ 355233294Sstas *constraint_p = ggc_alloc_string (buf, c_len); 35655682Smarkm constraint = *constraint_p; 357233294Sstas } 358178828Sdfr 359233294Sstas /* Loop through the constraint string. */ 360178828Sdfr for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p)) 361178828Sdfr switch (*p) 36255682Smarkm { 36378536Sassar case '+': 364233294Sstas case '=': 365233294Sstas error ("operand constraint contains incorrectly positioned " 366233294Sstas "%<+%> or %<=%>"); 367233294Sstas return false; 36855682Smarkm 36978536Sassar case '%': 37072448Sassar if (operand_num + 1 == ninputs + noutputs) 37155682Smarkm { 37272448Sassar error ("%<%%%> constraint used with last operand"); 37372448Sassar return false; 37472448Sassar } 37555682Smarkm break; 37655682Smarkm 377178828Sdfr case 'V': case 'm': case 'o': 378178828Sdfr *allows_mem = true; 379178828Sdfr break; 380233294Sstas 38155682Smarkm case '?': case '!': case '*': case '&': case '#': 38255682Smarkm case 'E': case 'F': case 'G': case 'H': 383127811Snectar case 's': case 'i': case 'n': 384233294Sstas case 'I': case 'J': case 'K': case 'L': case 'M': 38555682Smarkm case 'N': case 'O': case 'P': case ',': 386127811Snectar break; 387127811Snectar 388127811Snectar case '0': case '1': case '2': case '3': case '4': 389127811Snectar case '5': case '6': case '7': case '8': case '9': 390233294Sstas case '[': 391127811Snectar error ("matching constraint not valid in output operand"); 392127811Snectar return false; 393127811Snectar 394127811Snectar case '<': case '>': 395127811Snectar /* ??? Before flow, auto inc/dec insns are not supposed to exist, 396127811Snectar excepting those that expand_call created. So match memory 397127811Snectar and hope. */ 398127811Snectar *allows_mem = true; 399233294Sstas break; 400127811Snectar 40155682Smarkm case 'g': case 'X': 402127811Snectar *allows_reg = true; 40378536Sassar *allows_mem = true; 404233294Sstas break; 40578536Sassar 40655682Smarkm case 'p': case 'r': 40778536Sassar *allows_reg = true; 40878536Sassar break; 40978536Sassar 41078536Sassar default: 41178536Sassar if (!ISALPHA (*p)) 412233294Sstas break; 413233294Sstas if (REG_CLASS_FROM_CONSTRAINT (*p, p) != NO_REGS) 414233294Sstas *allows_reg = true; 41555682Smarkm#ifdef EXTRA_CONSTRAINT_STR 41678536Sassar else if (EXTRA_ADDRESS_CONSTRAINT (*p, p)) 41755682Smarkm *allows_reg = true; 418127811Snectar else if (EXTRA_MEMORY_CONSTRAINT (*p, p)) 419127811Snectar *allows_mem = true; 420233294Sstas else 421127811Snectar { 422127811Snectar /* Otherwise we can't assume anything about the nature of 423127811Snectar the constraint except that it isn't purely registers. 424127811Snectar Treat it like "g" and hope for the best. */ 425127811Snectar *allows_reg = true; 42655682Smarkm *allows_mem = true; 42755682Smarkm } 42855682Smarkm#endif 42955682Smarkm break; 43055682Smarkm } 43155682Smarkm 43255682Smarkm return true; 43355682Smarkm} 43455682Smarkm 43555682Smarkm/* Similar, but for input constraints. */ 43655682Smarkm 437233294Sstasbool 43855682Smarkmparse_input_constraint (const char **constraint_p, int input_num, 43955682Smarkm int ninputs, int noutputs, int ninout, 440233294Sstas const char * const * constraints, 44155682Smarkm bool *allows_mem, bool *allows_reg) 442233294Sstas{ 443178828Sdfr const char *constraint = *constraint_p; 444233294Sstas const char *orig_constraint = constraint; 445233294Sstas size_t c_len = strlen (constraint); 446233294Sstas size_t j; 44755682Smarkm bool saw_match = false; 44878536Sassar 44978536Sassar /* Assume the constraint doesn't allow the use of either 450233294Sstas a register or memory. */ 451233294Sstas *allows_mem = false; 452233294Sstas *allows_reg = false; 453233294Sstas 454233294Sstas /* Make sure constraint has neither `=', `+', nor '&'. */ 455233294Sstas 456233294Sstas for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j)) 45755682Smarkm switch (constraint[j]) 45878536Sassar { 45955682Smarkm case '+': case '=': case '&': 460233294Sstas if (constraint == orig_constraint) 461233294Sstas { 462233294Sstas error ("input operand constraint contains %qc", constraint[j]); 463233294Sstas return false; 464233294Sstas } 465233294Sstas break; 466233294Sstas 467233294Sstas case '%': 468233294Sstas if (constraint == orig_constraint 469233294Sstas && input_num + 1 == ninputs - ninout) 470234027Sstas { 471233294Sstas error ("%<%%%> constraint used with last operand"); 472233294Sstas return false; 473233294Sstas } 474233294Sstas break; 475233294Sstas 476233294Sstas case 'V': case 'm': case 'o': 477233294Sstas *allows_mem = true; 478233294Sstas break; 47955682Smarkm 480233294Sstas case '<': case '>': 481233294Sstas case '?': case '!': case '*': case '#': 482233294Sstas case 'E': case 'F': case 'G': case 'H': 48355682Smarkm case 's': case 'i': case 'n': 48455682Smarkm case 'I': case 'J': case 'K': case 'L': case 'M': 485233294Sstas case 'N': case 'O': case 'P': case ',': 486233294Sstas break; 487233294Sstas 488233294Sstas /* Whether or not a numeric constraint allows a register is 489233294Sstas decided by the matching constraint, and so there is no need 490233294Sstas to do anything special with them. We must handle them in 491233294Sstas the default case, so that we don't unnecessarily force 492233294Sstas operands to memory. */ 493233294Sstas case '0': case '1': case '2': case '3': case '4': 494233294Sstas case '5': case '6': case '7': case '8': case '9': 495233294Sstas { 496233294Sstas char *end; 497233294Sstas unsigned long match; 498233294Sstas 499233294Sstas saw_match = true; 50055682Smarkm 50155682Smarkm match = strtoul (constraint + j, &end, 10); 50255682Smarkm if (match >= (unsigned long) noutputs) 50355682Smarkm { 504233294Sstas error ("matching constraint references invalid operand number"); 505233294Sstas return false; 506233294Sstas } 507233294Sstas 508233294Sstas /* Try and find the real constraint for this dup. Only do this 50955682Smarkm if the matching constraint is the only alternative. */ 510233294Sstas if (*end == '\0' 51155682Smarkm && (j == 0 || (j == 1 && constraint[0] == '%'))) 512233294Sstas { 513233294Sstas constraint = constraints[match]; 514233294Sstas *constraint_p = constraint; 515233294Sstas c_len = strlen (constraint); 51678536Sassar j = 0; 51755682Smarkm /* ??? At the end of the loop, we will skip the first part of 51878536Sassar the matched constraint. This assumes not only that the 51955682Smarkm other constraint is an output constraint, but also that 52055682Smarkm the '=' or '+' come first. */ 52155682Smarkm break; 52255682Smarkm } 523233294Sstas else 52455682Smarkm j = end - constraint; 52555682Smarkm /* Anticipate increment at end of loop. */ 526233294Sstas j--; 52755682Smarkm } 52855682Smarkm /* Fall through. */ 52955682Smarkm 53055682Smarkm case 'p': case 'r': 531233294Sstas *allows_reg = true; 532127811Snectar break; 533127811Snectar 534233294Sstas case 'g': case 'X': 535127811Snectar *allows_reg = true; 536233294Sstas *allows_mem = true; 537233294Sstas break; 538233294Sstas 539127811Snectar default: 540127811Snectar if (! ISALPHA (constraint[j])) 541127811Snectar { 542127811Snectar error ("invalid punctuation %qc in constraint", constraint[j]); 543127811Snectar return false; 544233294Sstas } 545127811Snectar if (REG_CLASS_FROM_CONSTRAINT (constraint[j], constraint + j) 546127811Snectar != NO_REGS) 547127811Snectar *allows_reg = true; 548127811Snectar#ifdef EXTRA_CONSTRAINT_STR 549127811Snectar else if (EXTRA_ADDRESS_CONSTRAINT (constraint[j], constraint + j)) 55055682Smarkm *allows_reg = true; 55155682Smarkm else if (EXTRA_MEMORY_CONSTRAINT (constraint[j], constraint + j)) 552233294Sstas *allows_mem = true; 553178828Sdfr else 554178828Sdfr { 555178828Sdfr /* Otherwise we can't assume anything about the nature of 556178828Sdfr the constraint except that it isn't purely registers. 557233294Sstas Treat it like "g" and hope for the best. */ 558233294Sstas *allows_reg = true; 559178828Sdfr *allows_mem = true; 560178828Sdfr } 561178828Sdfr#endif 562178828Sdfr break; 563178828Sdfr } 564233294Sstas 565178828Sdfr if (saw_match && !*allows_reg) 566233294Sstas warning (0, "matching constraint does not allow a register"); 567233294Sstas 568178828Sdfr return true; 569233294Sstas} 570178828Sdfr 571178828Sdfr/* Return DECL iff there's an overlap between *REGS and DECL, where DECL 572233294Sstas can be an asm-declared register. Called via walk_tree. */ 573233294Sstas 574178828Sdfrstatic tree 575178828Sdfrdecl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED, 576178828Sdfr void *data) 577233294Sstas{ 57855682Smarkm tree decl = *declp; 57955682Smarkm const HARD_REG_SET *regs = data; 58055682Smarkm 58155682Smarkm if (TREE_CODE (decl) == VAR_DECL) 582233294Sstas { 58378536Sassar if (DECL_HARD_REGISTER (decl) 584233294Sstas && REG_P (DECL_RTL (decl)) 585233294Sstas && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER) 586233294Sstas { 58755682Smarkm rtx reg = DECL_RTL (decl); 58878536Sassar unsigned int regno; 58955682Smarkm 59055682Smarkm for (regno = REGNO (reg); 59155682Smarkm regno < (REGNO (reg) 59255682Smarkm + hard_regno_nregs[REGNO (reg)][GET_MODE (reg)]); 593233294Sstas regno++) 59455682Smarkm if (TEST_HARD_REG_BIT (*regs, regno)) 59555682Smarkm return decl; 59655682Smarkm } 597233294Sstas walk_subtrees = 0; 59878536Sassar } 599178828Sdfr else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL) 600233294Sstas walk_subtrees = 0; 601233294Sstas return NULL_TREE; 602233294Sstas} 60355682Smarkm 60478536Sassar/* If there is an overlap between *REGS and DECL, return the first overlap 60555682Smarkm found. */ 60655682Smarkmtree 60755682Smarkmtree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs) 608233294Sstas{ 60955682Smarkm return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL); 61055682Smarkm} 61155682Smarkm 612233294Sstas/* Check for overlap between registers marked in CLOBBERED_REGS and 61378536Sassar anything inappropriate in T. Emit error and return the register 614178828Sdfr variable definition for error, NULL_TREE for ok. */ 615233294Sstas 616233294Sstasstatic bool 617233294Sstastree_conflicts_with_clobbers_p (tree t, HARD_REG_SET *clobbered_regs) 61855682Smarkm{ 61978536Sassar /* Conflicts between asm-declared register variables and the clobber 62055682Smarkm list are not allowed. */ 62155682Smarkm tree overlap = tree_overlaps_hard_reg_set (t, clobbered_regs); 62255682Smarkm 623233294Sstas if (overlap) 624178828Sdfr { 625178828Sdfr error ("asm-specifier for variable %qs conflicts with asm clobber list", 626178828Sdfr IDENTIFIER_POINTER (DECL_NAME (overlap))); 627233294Sstas 628178828Sdfr /* Reset registerness to stop multiple errors emitted for a single 629178828Sdfr variable. */ 630233294Sstas DECL_REGISTER (overlap) = 0; 631233294Sstas return true; 632233294Sstas } 633178828Sdfr 634178828Sdfr return false; 635178828Sdfr} 636178828Sdfr 637178828Sdfr/* Generate RTL for an asm statement with arguments. 638178828Sdfr STRING is the instruction template. 63955682Smarkm OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs. 64055682Smarkm Each output or input has an expression in the TREE_VALUE and 64155682Smarkm and a tree list in TREE_PURPOSE which in turn contains a constraint 64255682Smarkm name in TREE_VALUE (or NULL_TREE) and a constraint string 643233294Sstas in TREE_PURPOSE. 644233294Sstas CLOBBERS is a list of STRING_CST nodes each naming a hard register 64555682Smarkm that is clobbered by this insn. 646120948Snectar 647233294Sstas Not all kinds of lvalue that may appear in OUTPUTS can be stored directly. 648233294Sstas Some elements of OUTPUTS may be replaced with trees representing temporary 649233294Sstas values. The caller should copy those temporary values to the originally 65055682Smarkm specified lvalues. 65155682Smarkm 65255682Smarkm VOL nonzero means the insn is volatile; don't optimize it. */ 65355682Smarkm 654233294Sstasstatic void 65555682Smarkmexpand_asm_operands (tree string, tree outputs, tree inputs, 65655682Smarkm tree clobbers, int vol, location_t locus) 65755682Smarkm{ 65855682Smarkm rtvec argvec, constraintvec; 659233294Sstas rtx body; 660233294Sstas int ninputs = list_length (inputs); 66178536Sassar int noutputs = list_length (outputs); 662233294Sstas int ninout; 663233294Sstas int nclobbers; 664233294Sstas HARD_REG_SET clobbered_regs; 665178828Sdfr int clobber_conflict_found = 0; 66655682Smarkm tree tail; 66778536Sassar tree t; 66855682Smarkm int i; 66978536Sassar /* Vector of RTX's of evaluated output operands. */ 670233294Sstas rtx *output_rtx = alloca (noutputs * sizeof (rtx)); 67155682Smarkm int *inout_opnum = alloca (noutputs * sizeof (int)); 67278536Sassar rtx *real_output_rtx = alloca (noutputs * sizeof (rtx)); 67355682Smarkm enum machine_mode *inout_mode 67455682Smarkm = alloca (noutputs * sizeof (enum machine_mode)); 67555682Smarkm const char **constraints 676233294Sstas = alloca ((noutputs + ninputs) * sizeof (const char *)); 67755682Smarkm int old_generating_concat_p = generating_concat_p; 67855682Smarkm 67955682Smarkm /* An ASM with no outputs needs to be treated as volatile, for now. */ 68055682Smarkm if (noutputs == 0) 68155682Smarkm vol = 1; 682233294Sstas 683233294Sstas if (! check_operand_nalternatives (outputs, inputs)) 684233294Sstas return; 68555682Smarkm 68655682Smarkm string = resolve_asm_operand_names (string, outputs, inputs); 687233294Sstas 688233294Sstas /* Collect constraints. */ 689233294Sstas i = 0; 69055682Smarkm for (t = outputs; t ; t = TREE_CHAIN (t), i++) 69155682Smarkm constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t))); 69255682Smarkm for (t = inputs; t ; t = TREE_CHAIN (t), i++) 693233294Sstas constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t))); 69455682Smarkm 69555682Smarkm /* Sometimes we wish to automatically clobber registers across an asm. 69655682Smarkm Case in point is when the i386 backend moved from cc0 to a hard reg -- 69755682Smarkm maintaining source-level compatibility means automatically clobbering 698233294Sstas the flags register. */ 69978536Sassar clobbers = targetm.md_asm_clobbers (outputs, inputs, clobbers); 700233294Sstas 70178536Sassar /* Count the number of meaningful clobbered registers, ignoring what 70255682Smarkm we would ignore later. */ 70355682Smarkm nclobbers = 0; 70455682Smarkm CLEAR_HARD_REG_SET (clobbered_regs); 70555682Smarkm for (tail = clobbers; tail; tail = TREE_CHAIN (tail)) 706233294Sstas { 707233294Sstas const char *regname; 708233294Sstas 709233294Sstas if (TREE_VALUE (tail) == error_mark_node) 710233294Sstas return; 711233294Sstas regname = TREE_STRING_POINTER (TREE_VALUE (tail)); 712233294Sstas 713233294Sstas i = decode_reg_name (regname); 714233294Sstas if (i >= 0 || i == -4) 715233294Sstas ++nclobbers; 716233294Sstas else if (i == -2) 717233294Sstas error ("unknown register name %qs in %<asm%>", regname); 718233294Sstas 71955682Smarkm /* Mark clobbered registers. */ 720233294Sstas if (i >= 0) 721233294Sstas { 722233294Sstas /* Clobbering the PIC register is an error. */ 723233294Sstas if (i == (int) PIC_OFFSET_TABLE_REGNUM) 724233294Sstas { 725233294Sstas error ("PIC register %qs clobbered in %<asm%>", regname); 726233294Sstas return; 72755682Smarkm } 728233294Sstas 729233294Sstas SET_HARD_REG_BIT (clobbered_regs, i); 730233294Sstas } 731233294Sstas } 732233294Sstas 73355682Smarkm /* First pass over inputs and outputs checks validity and sets 73455682Smarkm mark_addressable if needed. */ 735233294Sstas 736233294Sstas ninout = 0; 737233294Sstas for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 738233294Sstas { 739233294Sstas tree val = TREE_VALUE (tail); 740233294Sstas tree type = TREE_TYPE (val); 741233294Sstas const char *constraint; 742233294Sstas bool is_inout; 743233294Sstas bool allows_reg; 744233294Sstas bool allows_mem; 74555682Smarkm 74655682Smarkm /* If there's an erroneous arg, emit no insn. */ 747233294Sstas if (type == error_mark_node) 748233294Sstas return; 749233294Sstas 750233294Sstas /* Try to parse the output constraint. If that fails, there's 751233294Sstas no point in going further. */ 75255682Smarkm constraint = constraints[i]; 753233294Sstas if (!parse_output_constraint (&constraint, i, ninputs, noutputs, 75455682Smarkm &allows_mem, &allows_reg, &is_inout)) 755233294Sstas return; 75655682Smarkm 757233294Sstas if (! allows_reg 758233294Sstas && (allows_mem 759233294Sstas || is_inout 760233294Sstas || (DECL_P (val) 761233294Sstas && REG_P (DECL_RTL (val)) 762233294Sstas && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))) 763233294Sstas lang_hooks.mark_addressable (val); 76478536Sassar 76555682Smarkm if (is_inout) 766233294Sstas ninout++; 767233294Sstas } 768233294Sstas 769233294Sstas ninputs += ninout; 77055682Smarkm if (ninputs + noutputs > MAX_RECOG_OPERANDS) 77155682Smarkm { 772233294Sstas error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS); 773233294Sstas return; 774233294Sstas } 775178828Sdfr 776178828Sdfr for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail)) 777233294Sstas { 778178828Sdfr bool allows_reg, allows_mem; 779233294Sstas const char *constraint; 780233294Sstas 781233294Sstas /* If there's an erroneous arg, emit no insn, because the ASM_INPUT 782178828Sdfr would get VOIDmode and that could cause a crash in reload. */ 783178828Sdfr if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node) 784178828Sdfr return; 785233294Sstas 786233294Sstas constraint = constraints[i + noutputs]; 787233294Sstas if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout, 788178828Sdfr constraints, &allows_mem, &allows_reg)) 789178828Sdfr return; 790178828Sdfr 791178828Sdfr if (! allows_reg && allows_mem) 792178828Sdfr lang_hooks.mark_addressable (TREE_VALUE (tail)); 793178828Sdfr } 79455682Smarkm 79555682Smarkm /* Second pass evaluates arguments. */ 79655682Smarkm 79755682Smarkm ninout = 0; 79855682Smarkm for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 79955682Smarkm { 80055682Smarkm tree val = TREE_VALUE (tail); 80172448Sassar tree type = TREE_TYPE (val); 80272448Sassar bool is_inout; 80372448Sassar bool allows_reg; 80472448Sassar bool allows_mem; 80572448Sassar rtx op; 80672448Sassar bool ok; 80755682Smarkm 80855682Smarkm ok = parse_output_constraint (&constraints[i], i, ninputs, 80955682Smarkm noutputs, &allows_mem, &allows_reg, 81055682Smarkm &is_inout); 81155682Smarkm gcc_assert (ok); 81255682Smarkm 81355682Smarkm /* If an output operand is not a decl or indirect ref and our constraint 81455682Smarkm allows a register, make a temporary to act as an intermediate. 815178828Sdfr Make the asm insn write into that, then our caller will copy it to 81655682Smarkm the real output operand. Likewise for promoted variables. */ 81772448Sassar 81872448Sassar generating_concat_p = 0; 81955682Smarkm 82090929Snectar real_output_rtx[i] = NULL_RTX; 82155682Smarkm if ((TREE_CODE (val) == INDIRECT_REF 82255682Smarkm && allows_mem) 82355682Smarkm || (DECL_P (val) 824233294Sstas && (allows_mem || REG_P (DECL_RTL (val))) 825233294Sstas && ! (REG_P (DECL_RTL (val)) 826233294Sstas && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))) 82755682Smarkm || ! allows_reg 82855682Smarkm || is_inout) 82990929Snectar { 830120948Snectar op = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE); 83190929Snectar if (MEM_P (op)) 83290929Snectar op = validize_mem (op); 83390929Snectar 834233294Sstas if (! allows_reg && !MEM_P (op)) 83555682Smarkm error ("output number %d not directly addressable", i); 83690929Snectar if ((! allows_mem && MEM_P (op)) 837233294Sstas || GET_CODE (op) == CONCAT) 83855682Smarkm { 83955682Smarkm real_output_rtx[i] = op; 84055682Smarkm op = gen_reg_rtx (GET_MODE (op)); 84155682Smarkm if (is_inout) 842233294Sstas emit_move_insn (op, real_output_rtx[i]); 843233294Sstas } 844127811Snectar } 845233294Sstas else 84655682Smarkm { 847233294Sstas op = assign_temp (type, 0, 0, 1); 84855682Smarkm op = validize_mem (op); 84955682Smarkm TREE_VALUE (tail) = make_tree (type, op); 85072448Sassar } 85172448Sassar output_rtx[i] = op; 852233294Sstas 85372448Sassar generating_concat_p = old_generating_concat_p; 85472448Sassar 85590929Snectar if (is_inout) 85690929Snectar { 85755682Smarkm inout_mode[ninout] = TYPE_MODE (type); 85872448Sassar inout_opnum[ninout++] = i; 85955682Smarkm } 86090929Snectar 86190929Snectar if (tree_conflicts_with_clobbers_p (val, &clobbered_regs)) 86255682Smarkm clobber_conflict_found = 1; 86390929Snectar } 86490929Snectar 86590929Snectar /* Make vectors for the expression-rtx, constraint strings, 86690929Snectar and named operands. */ 86790929Snectar 86855682Smarkm argvec = rtvec_alloc (ninputs); 86990929Snectar constraintvec = rtvec_alloc (ninputs); 87055682Smarkm 87190929Snectar body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode 87290929Snectar : GET_MODE (output_rtx[0])), 87390929Snectar ggc_strdup (TREE_STRING_POINTER (string)), 87490929Snectar empty_string, 0, argvec, constraintvec, 87555682Smarkm locus); 87655682Smarkm 87790929Snectar MEM_VOLATILE_P (body) = vol; 87855682Smarkm 87955682Smarkm /* Eval the inputs and put them into ARGVEC. 88055682Smarkm Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */ 881178828Sdfr 88255682Smarkm for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i) 88372448Sassar { 88472448Sassar bool allows_reg, allows_mem; 88555682Smarkm const char *constraint; 88655682Smarkm tree val, type; 88755682Smarkm rtx op; 88855682Smarkm bool ok; 88955682Smarkm 890233294Sstas constraint = constraints[i + noutputs]; 891233294Sstas ok = parse_input_constraint (&constraint, i, ninputs, noutputs, ninout, 89278536Sassar constraints, &allows_mem, &allows_reg); 893233294Sstas gcc_assert (ok); 89455682Smarkm 895120948Snectar generating_concat_p = 0; 89655682Smarkm 89778536Sassar val = TREE_VALUE (tail); 898233294Sstas type = TREE_TYPE (val); 89955682Smarkm /* EXPAND_INITIALIZER will not generate code for valid initializer 90078536Sassar constants, but will still generate code for other types of operand. 901233294Sstas This is the behavior we want for constant constraints. */ 90255682Smarkm op = expand_expr (val, NULL_RTX, VOIDmode, 90355682Smarkm allows_reg ? EXPAND_NORMAL 90455682Smarkm : allows_mem ? EXPAND_MEMORY 90555682Smarkm : EXPAND_INITIALIZER); 90655682Smarkm 90755682Smarkm /* Never pass a CONCAT to an ASM. */ 90855682Smarkm if (GET_CODE (op) == CONCAT) 909233294Sstas op = force_reg (GET_MODE (op), op); 910127811Snectar else if (MEM_P (op)) 91178536Sassar op = validize_mem (op); 91255682Smarkm 913233294Sstas if (asm_operand_ok (op, constraint) <= 0) 91455682Smarkm { 91555682Smarkm if (allows_reg && TYPE_MODE (type) != BLKmode) 91655682Smarkm op = force_reg (TYPE_MODE (type), op); 917233294Sstas else if (!allows_mem) 91890929Snectar warning (0, "asm operand %d probably doesn%'t match constraints", 91955682Smarkm i + noutputs); 92055682Smarkm else if (MEM_P (op)) 92190929Snectar { 92290929Snectar /* We won't recognize either volatile memory or memory 92355682Smarkm with a queued address as available a memory_operand 92455682Smarkm at this point. Ignore it: clearly this *is* a memory. */ 92555682Smarkm } 92690929Snectar else 92790929Snectar { 92890929Snectar warning (0, "use of memory input without lvalue in " 92990929Snectar "asm operand %d is deprecated", i + noutputs); 93055682Smarkm 93155682Smarkm if (CONSTANT_P (op)) 93255682Smarkm { 93355682Smarkm rtx mem = force_const_mem (TYPE_MODE (type), op); 93455682Smarkm if (mem) 93555682Smarkm op = validize_mem (mem); 93655682Smarkm else 93790929Snectar op = force_reg (TYPE_MODE (type), op); 93890929Snectar } 93990929Snectar if (REG_P (op) 94090929Snectar || GET_CODE (op) == SUBREG 94155682Smarkm || GET_CODE (op) == CONCAT) 94255682Smarkm { 94355682Smarkm tree qual_type = build_qualified_type (type, 94472448Sassar (TYPE_QUALS (type) 94572448Sassar | TYPE_QUAL_CONST)); 94672448Sassar rtx memloc = assign_temp (qual_type, 1, 1, 1); 947178828Sdfr memloc = validize_mem (memloc); 94872448Sassar emit_move_insn (memloc, op); 94972448Sassar op = memloc; 95072448Sassar } 95172448Sassar } 952233294Sstas } 95378536Sassar 95472448Sassar generating_concat_p = old_generating_concat_p; 95572448Sassar ASM_OPERANDS_INPUT (body, i) = op; 95690929Snectar 95772448Sassar ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i) 95872448Sassar = gen_rtx_ASM_INPUT (TYPE_MODE (type), 95978536Sassar ggc_strdup (constraints[i + noutputs])); 960233294Sstas 96172448Sassar if (tree_conflicts_with_clobbers_p (val, &clobbered_regs)) 96278536Sassar clobber_conflict_found = 1; 96372448Sassar } 96472448Sassar 96572448Sassar /* Protect all the operands from the queue now that they have all been 96672448Sassar evaluated. */ 96772448Sassar 96872448Sassar generating_concat_p = 0; 96990929Snectar 97090929Snectar /* For in-out operands, copy output rtx to input rtx. */ 97190929Snectar for (i = 0; i < ninout; i++) 97290929Snectar { 97390929Snectar int j = inout_opnum[i]; 97490929Snectar char buffer[16]; 97572448Sassar 97672448Sassar ASM_OPERANDS_INPUT (body, ninputs - ninout + i) 97772448Sassar = output_rtx[j]; 97872448Sassar 97972448Sassar sprintf (buffer, "%d", j); 98072448Sassar ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i) 98155682Smarkm = gen_rtx_ASM_INPUT (inout_mode[i], ggc_strdup (buffer)); 98255682Smarkm } 98355682Smarkm 98455682Smarkm generating_concat_p = old_generating_concat_p; 98555682Smarkm 98672448Sassar /* Now, for each output, construct an rtx 98772448Sassar (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER 98855682Smarkm ARGVEC CONSTRAINTS OPNAMES)) 98955682Smarkm If there is more than one, put them inside a PARALLEL. */ 99055682Smarkm 99155682Smarkm if (noutputs == 1 && nclobbers == 0) 99255682Smarkm { 993233294Sstas ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = ggc_strdup (constraints[0]); 994233294Sstas emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body)); 99555682Smarkm } 996233294Sstas 99772448Sassar else if (noutputs == 0 && nclobbers == 0) 998178828Sdfr { 999233294Sstas /* No output operands: put in a raw ASM_OPERANDS rtx. */ 1000233294Sstas emit_insn (body); 1001233294Sstas } 1002178828Sdfr 100378536Sassar else 100472448Sassar { 1005127811Snectar rtx obody = body; 1006233294Sstas int num = noutputs; 1007127811Snectar 1008127811Snectar if (num == 0) 1009127811Snectar num = 1; 101055682Smarkm 101178536Sassar body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers)); 1012233294Sstas 101355682Smarkm /* For each output operand, store a SET. */ 101478536Sassar for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 101555682Smarkm { 101655682Smarkm XVECEXP (body, 0, i) 101755682Smarkm = gen_rtx_SET (VOIDmode, 101855682Smarkm output_rtx[i], 101955682Smarkm gen_rtx_ASM_OPERANDS 102055682Smarkm (GET_MODE (output_rtx[i]), 102155682Smarkm ggc_strdup (TREE_STRING_POINTER (string)), 102255682Smarkm ggc_strdup (constraints[i]), 102355682Smarkm i, argvec, constraintvec, locus)); 102455682Smarkm 102555682Smarkm MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol; 102655682Smarkm } 102755682Smarkm 102855682Smarkm /* If there are no outputs (but there are some clobbers) 102990929Snectar store the bare ASM_OPERANDS into the PARALLEL. */ 103090929Snectar 103190929Snectar if (i == 0) 103290929Snectar XVECEXP (body, 0, i++) = obody; 103390929Snectar 103455682Smarkm /* Store (clobber REG) for each clobbered register specified. */ 103555682Smarkm 103655682Smarkm for (tail = clobbers; tail; tail = TREE_CHAIN (tail)) 103755682Smarkm { 103855682Smarkm const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail)); 103955682Smarkm int j = decode_reg_name (regname); 104055682Smarkm rtx clobbered_reg; 104155682Smarkm 104255682Smarkm if (j < 0) 104355682Smarkm { 104455682Smarkm if (j == -3) /* `cc', which is not a register */ 104555682Smarkm continue; 104655682Smarkm 104755682Smarkm if (j == -4) /* `memory', don't cache memory across asm */ 104855682Smarkm { 104955682Smarkm XVECEXP (body, 0, i++) 105055682Smarkm = gen_rtx_CLOBBER (VOIDmode, 105155682Smarkm gen_rtx_MEM 1052178828Sdfr (BLKmode, 105355682Smarkm gen_rtx_SCRATCH (VOIDmode))); 1054233294Sstas continue; 105555682Smarkm } 105655682Smarkm 105755682Smarkm /* Ignore unknown register, error already signaled. */ 105855682Smarkm continue; 105955682Smarkm } 106055682Smarkm 106155682Smarkm /* Use QImode since that's guaranteed to clobber just one reg. */ 106255682Smarkm clobbered_reg = gen_rtx_REG (QImode, j); 106355682Smarkm 106455682Smarkm /* Do sanity check for overlap between clobbers and respectively 106555682Smarkm input and outputs that hasn't been handled. Such overlap 106672448Sassar should have been detected and reported above. */ 106772448Sassar if (!clobber_conflict_found) 106855682Smarkm { 106955682Smarkm int opno; 107055682Smarkm 107155682Smarkm /* We test the old body (obody) contents to avoid tripping 107255682Smarkm over the under-construction body. */ 1073233294Sstas for (opno = 0; opno < noutputs; opno++) 1074233294Sstas if (reg_overlap_mentioned_p (clobbered_reg, output_rtx[opno])) 1075127811Snectar internal_error ("asm clobber conflict with output operand"); 1076233294Sstas 1077127811Snectar for (opno = 0; opno < ninputs - ninout; opno++) 1078127811Snectar if (reg_overlap_mentioned_p (clobbered_reg, 1079233294Sstas ASM_OPERANDS_INPUT (obody, opno))) 1080233294Sstas internal_error ("asm clobber conflict with input operand"); 1081233294Sstas } 1082233294Sstas 1083233294Sstas XVECEXP (body, 0, i++) 1084233294Sstas = gen_rtx_CLOBBER (VOIDmode, clobbered_reg); 1085233294Sstas } 1086127811Snectar 108755682Smarkm emit_insn (body); 108878536Sassar } 1089233294Sstas 109055682Smarkm /* For any outputs that needed reloading into registers, spill them 109178536Sassar back to where they belong. */ 109255682Smarkm for (i = 0; i < noutputs; ++i) 1093233294Sstas if (real_output_rtx[i]) 109455682Smarkm emit_move_insn (real_output_rtx[i], output_rtx[i]); 109555682Smarkm 109655682Smarkm free_temp_slots (); 109755682Smarkm} 109855682Smarkm 109990929Snectarvoid 110090929Snectarexpand_asm_expr (tree exp) 110190929Snectar{ 110290929Snectar int noutputs, i; 110390929Snectar tree outputs, tail; 110455682Smarkm tree *o; 110555682Smarkm 110672448Sassar if (ASM_INPUT_P (exp)) 110772448Sassar { 110855682Smarkm expand_asm (ASM_STRING (exp), ASM_VOLATILE_P (exp)); 110955682Smarkm return; 111078536Sassar } 111155682Smarkm 111255682Smarkm outputs = ASM_OUTPUTS (exp); 111355682Smarkm noutputs = list_length (outputs); 111455682Smarkm /* o[I] is the place that output number I should be written. */ 111555682Smarkm o = (tree *) alloca (noutputs * sizeof (tree)); 111655682Smarkm 111755682Smarkm /* Record the contents of OUTPUTS before it is modified. */ 111855682Smarkm for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 111955682Smarkm o[i] = TREE_VALUE (tail); 1120178828Sdfr 112155682Smarkm /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of 1122233294Sstas OUTPUTS some trees for where the values were actually stored. */ 112355682Smarkm expand_asm_operands (ASM_STRING (exp), outputs, ASM_INPUTS (exp), 112455682Smarkm ASM_CLOBBERS (exp), ASM_VOLATILE_P (exp), 112555682Smarkm input_location); 112655682Smarkm 112755682Smarkm /* Copy all the intermediate outputs into the specified outputs. */ 112855682Smarkm for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 112972448Sassar { 113072448Sassar if (o[i] != TREE_VALUE (tail)) 113172448Sassar { 113272448Sassar expand_assignment (o[i], TREE_VALUE (tail)); 113372448Sassar free_temp_slots (); 113472448Sassar 113572448Sassar /* Restore the original value so that it's correct the next 113672448Sassar time we expand this function. */ 113772448Sassar TREE_VALUE (tail) = o[i]; 1138233294Sstas } 113978536Sassar } 114072448Sassar} 1141127811Snectar 114290929Snectar/* A subroutine of expand_asm_operands. Check that all operands have 114372448Sassar the same number of alternatives. Return true if so. */ 1144127811Snectar 1145233294Sstasstatic bool 1146127811Snectarcheck_operand_nalternatives (tree outputs, tree inputs) 1147127811Snectar{ 1148233294Sstas if (outputs || inputs) 1149233294Sstas { 1150233294Sstas tree tmp = TREE_PURPOSE (outputs ? outputs : inputs); 1151233294Sstas int nalternatives 1152233294Sstas = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp))); 1153233294Sstas tree next = inputs; 1154127811Snectar 1155127811Snectar if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES) 1156127811Snectar { 1157233294Sstas error ("too many alternatives in %<asm%>"); 115872448Sassar return false; 115978536Sassar } 1160127811Snectar 1161233294Sstas tmp = outputs; 1162127811Snectar while (tmp) 116390929Snectar { 1164127811Snectar const char *constraint 116590929Snectar = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp))); 116690929Snectar 116772448Sassar if (n_occurrences (',', constraint) != nalternatives) 1168127811Snectar { 1169127811Snectar error ("operand constraints for %<asm%> differ " 1170178828Sdfr "in number of alternatives"); 1171127811Snectar return false; 1172233294Sstas } 1173127811Snectar 1174127811Snectar if (TREE_CHAIN (tmp)) 117572448Sassar tmp = TREE_CHAIN (tmp); 117672448Sassar else 117772448Sassar tmp = next, next = 0; 117872448Sassar } 1179233294Sstas } 1180233294Sstas 1181233294Sstas return true; 1182233294Sstas} 1183233294Sstas 1184233294Sstas/* A subroutine of expand_asm_operands. Check that all operand names 1185233294Sstas are unique. Return true if so. We rely on the fact that these names 1186233294Sstas are identifiers, and so have been canonicalized by get_identifier, 1187233294Sstas so all we need are pointer comparisons. */ 118872448Sassar 1189233294Sstasstatic bool 1190233294Sstascheck_unique_operand_names (tree outputs, tree inputs) 1191233294Sstas{ 1192233294Sstas tree i, j; 1193233294Sstas 1194233294Sstas for (i = outputs; i ; i = TREE_CHAIN (i)) 1195233294Sstas { 1196233294Sstas tree i_name = TREE_PURPOSE (TREE_PURPOSE (i)); 1197233294Sstas if (! i_name) 1198233294Sstas continue; 1199233294Sstas 1200233294Sstas for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j)) 1201233294Sstas if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) 1202233294Sstas goto failure; 1203233294Sstas } 1204233294Sstas 1205233294Sstas for (i = inputs; i ; i = TREE_CHAIN (i)) 1206233294Sstas { 1207233294Sstas tree i_name = TREE_PURPOSE (TREE_PURPOSE (i)); 1208233294Sstas if (! i_name) 1209233294Sstas continue; 1210233294Sstas 1211233294Sstas for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j)) 1212233294Sstas if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) 1213233294Sstas goto failure; 1214233294Sstas for (j = outputs; j ; j = TREE_CHAIN (j)) 1215233294Sstas if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) 1216233294Sstas goto failure; 1217233294Sstas } 1218233294Sstas 1219233294Sstas return true; 1220233294Sstas 1221233294Sstas failure: 1222233294Sstas error ("duplicate asm operand name %qs", 1223233294Sstas TREE_STRING_POINTER (TREE_PURPOSE (TREE_PURPOSE (i)))); 1224233294Sstas return false; 1225233294Sstas} 1226233294Sstas 1227233294Sstas/* A subroutine of expand_asm_operands. Resolve the names of the operands 1228233294Sstas in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in 1229233294Sstas STRING and in the constraints to those numbers. */ 1230233294Sstas 1231233294Sstastree 1232233294Sstasresolve_asm_operand_names (tree string, tree outputs, tree inputs) 1233233294Sstas{ 1234233294Sstas char *buffer; 1235233294Sstas char *p; 1236233294Sstas const char *c; 1237233294Sstas tree t; 1238233294Sstas 1239233294Sstas check_unique_operand_names (outputs, inputs); 1240233294Sstas 1241233294Sstas /* Substitute [<name>] in input constraint strings. There should be no 1242233294Sstas named operands in output constraints. */ 1243233294Sstas for (t = inputs; t ; t = TREE_CHAIN (t)) 1244233294Sstas { 1245233294Sstas c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t))); 1246233294Sstas if (strchr (c, '[') != NULL) 1247233294Sstas { 1248233294Sstas p = buffer = xstrdup (c); 1249233294Sstas while ((p = strchr (p, '[')) != NULL) 1250233294Sstas p = resolve_operand_name_1 (p, outputs, inputs); 1251233294Sstas TREE_VALUE (TREE_PURPOSE (t)) 1252233294Sstas = build_string (strlen (buffer), buffer); 1253233294Sstas free (buffer); 1254233294Sstas } 1255233294Sstas } 1256233294Sstas 1257233294Sstas /* Now check for any needed substitutions in the template. */ 1258233294Sstas c = TREE_STRING_POINTER (string); 1259233294Sstas while ((c = strchr (c, '%')) != NULL) 1260233294Sstas { 1261233294Sstas if (c[1] == '[') 1262233294Sstas break; 1263233294Sstas else if (ISALPHA (c[1]) && c[2] == '[') 1264233294Sstas break; 1265233294Sstas else 1266233294Sstas { 1267233294Sstas c += 1; 1268233294Sstas continue; 1269233294Sstas } 1270233294Sstas } 1271233294Sstas 1272233294Sstas if (c) 1273233294Sstas { 1274233294Sstas /* OK, we need to make a copy so we can perform the substitutions. 1275233294Sstas Assume that we will not need extra space--we get to remove '[' 1276233294Sstas and ']', which means we cannot have a problem until we have more 1277233294Sstas than 999 operands. */ 1278233294Sstas buffer = xstrdup (TREE_STRING_POINTER (string)); 1279233294Sstas p = buffer + (c - TREE_STRING_POINTER (string)); 1280233294Sstas 1281233294Sstas while ((p = strchr (p, '%')) != NULL) 1282233294Sstas { 1283233294Sstas if (p[1] == '[') 1284233294Sstas p += 1; 1285233294Sstas else if (ISALPHA (p[1]) && p[2] == '[') 1286233294Sstas p += 2; 1287233294Sstas else 1288233294Sstas { 1289233294Sstas p += 1; 1290233294Sstas continue; 1291233294Sstas } 1292233294Sstas 1293233294Sstas p = resolve_operand_name_1 (p, outputs, inputs); 1294233294Sstas } 1295233294Sstas 1296233294Sstas string = build_string (strlen (buffer), buffer); 1297233294Sstas free (buffer); 1298233294Sstas } 1299233294Sstas 1300233294Sstas return string; 1301233294Sstas} 1302233294Sstas 1303233294Sstas/* A subroutine of resolve_operand_names. P points to the '[' for a 1304233294Sstas potential named operand of the form [<name>]. In place, replace 1305233294Sstas the name and brackets with a number. Return a pointer to the 1306233294Sstas balance of the string after substitution. */ 1307233294Sstas 1308233294Sstasstatic char * 1309233294Sstasresolve_operand_name_1 (char *p, tree outputs, tree inputs) 1310233294Sstas{ 1311233294Sstas char *q; 1312233294Sstas int op; 1313233294Sstas tree t; 1314233294Sstas size_t len; 1315233294Sstas 1316233294Sstas /* Collect the operand name. */ 1317233294Sstas q = strchr (p, ']'); 1318233294Sstas if (!q) 1319233294Sstas { 1320233294Sstas error ("missing close brace for named operand"); 1321233294Sstas return strchr (p, '\0'); 1322233294Sstas } 1323233294Sstas len = q - p - 1; 1324233294Sstas 1325233294Sstas /* Resolve the name to a number. */ 1326233294Sstas for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++) 1327233294Sstas { 1328233294Sstas tree name = TREE_PURPOSE (TREE_PURPOSE (t)); 1329233294Sstas if (name) 1330233294Sstas { 1331233294Sstas const char *c = TREE_STRING_POINTER (name); 1332233294Sstas if (strncmp (c, p + 1, len) == 0 && c[len] == '\0') 1333233294Sstas goto found; 1334233294Sstas } 1335233294Sstas } 1336233294Sstas for (t = inputs; t ; t = TREE_CHAIN (t), op++) 1337233294Sstas { 1338233294Sstas tree name = TREE_PURPOSE (TREE_PURPOSE (t)); 1339233294Sstas if (name) 1340233294Sstas { 1341233294Sstas const char *c = TREE_STRING_POINTER (name); 1342233294Sstas if (strncmp (c, p + 1, len) == 0 && c[len] == '\0') 1343233294Sstas goto found; 1344233294Sstas } 1345233294Sstas } 1346233294Sstas 1347233294Sstas *q = '\0'; 1348233294Sstas error ("undefined named operand %qs", p + 1); 1349233294Sstas op = 0; 1350233294Sstas found: 1351233294Sstas 1352233294Sstas /* Replace the name with the number. Unfortunately, not all libraries 1353233294Sstas get the return value of sprintf correct, so search for the end of the 1354233294Sstas generated string by hand. */ 1355233294Sstas sprintf (p, "%d", op); 1356233294Sstas p = strchr (p, '\0'); 1357233294Sstas 1358233294Sstas /* Verify the no extra buffer space assumption. */ 1359233294Sstas gcc_assert (p <= q); 1360233294Sstas 1361233294Sstas /* Shift the rest of the buffer down to fill the gap. */ 1362233294Sstas memmove (p, q + 1, strlen (q + 1) + 1); 1363233294Sstas 1364233294Sstas return p; 1365233294Sstas} 1366233294Sstas 1367233294Sstas/* Generate RTL to evaluate the expression EXP. */ 1368233294Sstas 1369233294Sstasvoid 1370233294Sstasexpand_expr_stmt (tree exp) 1371233294Sstas{ 1372233294Sstas rtx value; 1373233294Sstas tree type; 1374233294Sstas 1375233294Sstas value = expand_expr (exp, const0_rtx, VOIDmode, 0); 1376233294Sstas type = TREE_TYPE (exp); 1377233294Sstas 1378233294Sstas /* If all we do is reference a volatile value in memory, 1379233294Sstas copy it to a register to be sure it is actually touched. */ 1380233294Sstas if (value && MEM_P (value) && TREE_THIS_VOLATILE (exp)) 1381233294Sstas { 1382233294Sstas if (TYPE_MODE (type) == VOIDmode) 1383233294Sstas ; 1384233294Sstas else if (TYPE_MODE (type) != BLKmode) 1385233294Sstas value = copy_to_reg (value); 1386233294Sstas else 1387233294Sstas { 1388233294Sstas rtx lab = gen_label_rtx (); 1389233294Sstas 1390233294Sstas /* Compare the value with itself to reference it. */ 1391233294Sstas emit_cmp_and_jump_insns (value, value, EQ, 1392233294Sstas expand_normal (TYPE_SIZE (type)), 1393233294Sstas BLKmode, 0, lab); 1394233294Sstas emit_label (lab); 1395233294Sstas } 1396233294Sstas } 1397233294Sstas 1398233294Sstas /* Free any temporaries used to evaluate this expression. */ 1399233294Sstas free_temp_slots (); 1400233294Sstas} 1401233294Sstas 1402233294Sstas/* Warn if EXP contains any computations whose results are not used. 1403233294Sstas Return 1 if a warning is printed; 0 otherwise. LOCUS is the 1404233294Sstas (potential) location of the expression. */ 1405233294Sstas 1406233294Sstasint 1407233294Sstaswarn_if_unused_value (tree exp, location_t locus) 1408233294Sstas{ 1409233294Sstas restart: 1410233294Sstas if (TREE_USED (exp) || TREE_NO_WARNING (exp)) 1411233294Sstas return 0; 1412233294Sstas 1413233294Sstas /* Don't warn about void constructs. This includes casting to void, 1414233294Sstas void function calls, and statement expressions with a final cast 1415233294Sstas to void. */ 1416233294Sstas if (VOID_TYPE_P (TREE_TYPE (exp))) 1417233294Sstas return 0; 1418233294Sstas 1419233294Sstas if (EXPR_HAS_LOCATION (exp)) 1420233294Sstas locus = EXPR_LOCATION (exp); 1421233294Sstas 1422233294Sstas switch (TREE_CODE (exp)) 1423233294Sstas { 1424233294Sstas case PREINCREMENT_EXPR: 1425233294Sstas case POSTINCREMENT_EXPR: 1426233294Sstas case PREDECREMENT_EXPR: 1427233294Sstas case POSTDECREMENT_EXPR: 1428233294Sstas case MODIFY_EXPR: 1429233294Sstas case INIT_EXPR: 1430233294Sstas case TARGET_EXPR: 1431233294Sstas case CALL_EXPR: 1432233294Sstas case TRY_CATCH_EXPR: 1433233294Sstas case WITH_CLEANUP_EXPR: 1434233294Sstas case EXIT_EXPR: 1435233294Sstas case VA_ARG_EXPR: 1436233294Sstas return 0; 1437233294Sstas 1438233294Sstas case BIND_EXPR: 1439233294Sstas /* For a binding, warn if no side effect within it. */ 1440233294Sstas exp = BIND_EXPR_BODY (exp); 1441233294Sstas goto restart; 1442233294Sstas 1443233294Sstas case SAVE_EXPR: 1444233294Sstas exp = TREE_OPERAND (exp, 0); 1445233294Sstas goto restart; 1446233294Sstas 1447233294Sstas case TRUTH_ORIF_EXPR: 1448233294Sstas case TRUTH_ANDIF_EXPR: 1449233294Sstas /* In && or ||, warn if 2nd operand has no side effect. */ 1450233294Sstas exp = TREE_OPERAND (exp, 1); 1451233294Sstas goto restart; 1452233294Sstas 1453233294Sstas case COMPOUND_EXPR: 1454233294Sstas if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus)) 1455233294Sstas return 1; 1456233294Sstas /* Let people do `(foo (), 0)' without a warning. */ 1457233294Sstas if (TREE_CONSTANT (TREE_OPERAND (exp, 1))) 1458233294Sstas return 0; 1459233294Sstas exp = TREE_OPERAND (exp, 1); 1460233294Sstas goto restart; 1461233294Sstas 1462233294Sstas case COND_EXPR: 1463233294Sstas /* If this is an expression with side effects, don't warn; this 1464233294Sstas case commonly appears in macro expansions. */ 1465233294Sstas if (TREE_SIDE_EFFECTS (exp)) 1466233294Sstas return 0; 1467233294Sstas goto warn; 1468233294Sstas 1469233294Sstas case INDIRECT_REF: 1470233294Sstas /* Don't warn about automatic dereferencing of references, since 1471233294Sstas the user cannot control it. */ 1472233294Sstas if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE) 1473233294Sstas { 1474233294Sstas exp = TREE_OPERAND (exp, 0); 1475233294Sstas goto restart; 1476233294Sstas } 1477233294Sstas /* Fall through. */ 1478233294Sstas 1479233294Sstas default: 1480233294Sstas /* Referencing a volatile value is a side effect, so don't warn. */ 1481233294Sstas if ((DECL_P (exp) || REFERENCE_CLASS_P (exp)) 1482233294Sstas && TREE_THIS_VOLATILE (exp)) 1483233294Sstas return 0; 1484233294Sstas 1485233294Sstas /* If this is an expression which has no operands, there is no value 1486233294Sstas to be unused. There are no such language-independent codes, 1487233294Sstas but front ends may define such. */ 1488233294Sstas if (EXPRESSION_CLASS_P (exp) && TREE_CODE_LENGTH (TREE_CODE (exp)) == 0) 1489233294Sstas return 0; 1490233294Sstas 1491233294Sstas warn: 1492233294Sstas warning (0, "%Hvalue computed is not used", &locus); 1493233294Sstas return 1; 1494233294Sstas } 1495233294Sstas} 1496233294Sstas 1497233294Sstas 1498233294Sstas/* Generate RTL to return from the current function, with no value. 1499233294Sstas (That is, we do not do anything about returning any value.) */ 1500233294Sstas 1501233294Sstasvoid 1502233294Sstasexpand_null_return (void) 1503233294Sstas{ 1504233294Sstas /* If this function was declared to return a value, but we 1505233294Sstas didn't, clobber the return registers so that they are not 1506233294Sstas propagated live to the rest of the function. */ 1507233294Sstas clobber_return_register (); 1508233294Sstas 1509233294Sstas expand_null_return_1 (); 1510233294Sstas} 1511233294Sstas 1512233294Sstas/* Generate RTL to return directly from the current function. 1513233294Sstas (That is, we bypass any return value.) */ 1514233294Sstas 1515233294Sstasvoid 1516233294Sstasexpand_naked_return (void) 1517233294Sstas{ 1518233294Sstas rtx end_label; 1519233294Sstas 1520233294Sstas clear_pending_stack_adjust (); 1521233294Sstas do_pending_stack_adjust (); 1522233294Sstas 1523233294Sstas end_label = naked_return_label; 1524233294Sstas if (end_label == 0) 1525233294Sstas end_label = naked_return_label = gen_label_rtx (); 1526233294Sstas 1527233294Sstas emit_jump (end_label); 1528233294Sstas} 1529233294Sstas 1530233294Sstas/* Generate RTL to return from the current function, with value VAL. */ 1531233294Sstas 1532233294Sstasstatic void 1533233294Sstasexpand_value_return (rtx val) 1534233294Sstas{ 1535233294Sstas /* Copy the value to the return location 1536233294Sstas unless it's already there. */ 1537233294Sstas 1538233294Sstas rtx return_reg = DECL_RTL (DECL_RESULT (current_function_decl)); 1539233294Sstas if (return_reg != val) 1540233294Sstas { 1541233294Sstas tree type = TREE_TYPE (DECL_RESULT (current_function_decl)); 1542233294Sstas if (targetm.calls.promote_function_return (TREE_TYPE (current_function_decl))) 1543233294Sstas { 1544233294Sstas int unsignedp = TYPE_UNSIGNED (type); 1545233294Sstas enum machine_mode old_mode 1546233294Sstas = DECL_MODE (DECL_RESULT (current_function_decl)); 1547233294Sstas enum machine_mode mode 1548233294Sstas = promote_mode (type, old_mode, &unsignedp, 1); 1549233294Sstas 1550233294Sstas if (mode != old_mode) 1551233294Sstas val = convert_modes (mode, old_mode, val, unsignedp); 1552233294Sstas } 1553233294Sstas if (GET_CODE (return_reg) == PARALLEL) 1554233294Sstas emit_group_load (return_reg, val, type, int_size_in_bytes (type)); 1555233294Sstas else 1556233294Sstas emit_move_insn (return_reg, val); 1557233294Sstas } 1558233294Sstas 1559233294Sstas expand_null_return_1 (); 1560233294Sstas} 1561233294Sstas 1562233294Sstas/* Output a return with no value. */ 1563233294Sstas 1564233294Sstasstatic void 1565233294Sstasexpand_null_return_1 (void) 1566233294Sstas{ 1567233294Sstas clear_pending_stack_adjust (); 1568233294Sstas do_pending_stack_adjust (); 1569233294Sstas emit_jump (return_label); 1570233294Sstas} 1571233294Sstas 1572233294Sstas/* Generate RTL to evaluate the expression RETVAL and return it 1573233294Sstas from the current function. */ 1574233294Sstas 1575233294Sstasvoid 1576233294Sstasexpand_return (tree retval) 1577233294Sstas{ 1578233294Sstas rtx result_rtl; 1579233294Sstas rtx val = 0; 1580233294Sstas tree retval_rhs; 1581233294Sstas 1582233294Sstas /* If function wants no value, give it none. */ 1583233294Sstas if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE) 1584233294Sstas { 1585233294Sstas expand_normal (retval); 1586233294Sstas expand_null_return (); 1587233294Sstas return; 1588233294Sstas } 1589233294Sstas 1590233294Sstas if (retval == error_mark_node) 1591233294Sstas { 1592233294Sstas /* Treat this like a return of no value from a function that 1593233294Sstas returns a value. */ 1594233294Sstas expand_null_return (); 1595233294Sstas return; 1596233294Sstas } 1597233294Sstas else if ((TREE_CODE (retval) == MODIFY_EXPR 1598233294Sstas || TREE_CODE (retval) == INIT_EXPR) 1599233294Sstas && TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL) 1600233294Sstas retval_rhs = TREE_OPERAND (retval, 1); 1601233294Sstas else 1602233294Sstas retval_rhs = retval; 1603233294Sstas 1604233294Sstas result_rtl = DECL_RTL (DECL_RESULT (current_function_decl)); 1605233294Sstas 1606233294Sstas /* If we are returning the RESULT_DECL, then the value has already 1607233294Sstas been stored into it, so we don't have to do anything special. */ 1608233294Sstas if (TREE_CODE (retval_rhs) == RESULT_DECL) 1609233294Sstas expand_value_return (result_rtl); 1610233294Sstas 1611233294Sstas /* If the result is an aggregate that is being returned in one (or more) 1612233294Sstas registers, load the registers here. The compiler currently can't handle 1613233294Sstas copying a BLKmode value into registers. We could put this code in a 1614233294Sstas more general area (for use by everyone instead of just function 1615233294Sstas call/return), but until this feature is generally usable it is kept here 1616233294Sstas (and in expand_call). */ 1617233294Sstas 1618233294Sstas else if (retval_rhs != 0 1619233294Sstas && TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode 1620233294Sstas && REG_P (result_rtl)) 1621233294Sstas { 1622233294Sstas int i; 1623233294Sstas unsigned HOST_WIDE_INT bitpos, xbitpos; 1624233294Sstas unsigned HOST_WIDE_INT padding_correction = 0; 1625233294Sstas unsigned HOST_WIDE_INT bytes 1626233294Sstas = int_size_in_bytes (TREE_TYPE (retval_rhs)); 1627233294Sstas int n_regs = (bytes + UNITS_PER_WORD - 1) / UNITS_PER_WORD; 1628233294Sstas unsigned int bitsize 1629233294Sstas = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)), BITS_PER_WORD); 1630233294Sstas rtx *result_pseudos = alloca (sizeof (rtx) * n_regs); 1631233294Sstas rtx result_reg, src = NULL_RTX, dst = NULL_RTX; 1632233294Sstas rtx result_val = expand_normal (retval_rhs); 1633233294Sstas enum machine_mode tmpmode, result_reg_mode; 1634233294Sstas 1635233294Sstas if (bytes == 0) 1636233294Sstas { 1637233294Sstas expand_null_return (); 1638233294Sstas return; 1639233294Sstas } 1640233294Sstas 1641233294Sstas /* If the structure doesn't take up a whole number of words, see 1642233294Sstas whether the register value should be padded on the left or on 1643233294Sstas the right. Set PADDING_CORRECTION to the number of padding 1644233294Sstas bits needed on the left side. 1645233294Sstas 1646233294Sstas In most ABIs, the structure will be returned at the least end of 1647233294Sstas the register, which translates to right padding on little-endian 1648233294Sstas targets and left padding on big-endian targets. The opposite 1649233294Sstas holds if the structure is returned at the most significant 1650233294Sstas end of the register. */ 1651233294Sstas if (bytes % UNITS_PER_WORD != 0 1652233294Sstas && (targetm.calls.return_in_msb (TREE_TYPE (retval_rhs)) 1653233294Sstas ? !BYTES_BIG_ENDIAN 1654233294Sstas : BYTES_BIG_ENDIAN)) 1655233294Sstas padding_correction = (BITS_PER_WORD - ((bytes % UNITS_PER_WORD) 1656233294Sstas * BITS_PER_UNIT)); 1657233294Sstas 1658233294Sstas /* Copy the structure BITSIZE bits at a time. */ 1659233294Sstas for (bitpos = 0, xbitpos = padding_correction; 1660233294Sstas bitpos < bytes * BITS_PER_UNIT; 1661233294Sstas bitpos += bitsize, xbitpos += bitsize) 1662233294Sstas { 1663233294Sstas /* We need a new destination pseudo each time xbitpos is 1664233294Sstas on a word boundary and when xbitpos == padding_correction 1665233294Sstas (the first time through). */ 1666233294Sstas if (xbitpos % BITS_PER_WORD == 0 1667233294Sstas || xbitpos == padding_correction) 1668233294Sstas { 1669233294Sstas /* Generate an appropriate register. */ 1670233294Sstas dst = gen_reg_rtx (word_mode); 1671233294Sstas result_pseudos[xbitpos / BITS_PER_WORD] = dst; 1672233294Sstas 1673233294Sstas /* Clear the destination before we move anything into it. */ 1674233294Sstas emit_move_insn (dst, CONST0_RTX (GET_MODE (dst))); 1675233294Sstas } 1676233294Sstas 1677233294Sstas /* We need a new source operand each time bitpos is on a word 1678233294Sstas boundary. */ 1679233294Sstas if (bitpos % BITS_PER_WORD == 0) 1680233294Sstas src = operand_subword_force (result_val, 1681233294Sstas bitpos / BITS_PER_WORD, 1682233294Sstas BLKmode); 1683233294Sstas 1684233294Sstas /* Use bitpos for the source extraction (left justified) and 1685233294Sstas xbitpos for the destination store (right justified). */ 1686233294Sstas store_bit_field (dst, bitsize, xbitpos % BITS_PER_WORD, word_mode, 1687233294Sstas extract_bit_field (src, bitsize, 1688233294Sstas bitpos % BITS_PER_WORD, 1, 1689233294Sstas NULL_RTX, word_mode, word_mode)); 1690233294Sstas } 1691233294Sstas 1692233294Sstas tmpmode = GET_MODE (result_rtl); 1693233294Sstas if (tmpmode == BLKmode) 1694233294Sstas { 1695233294Sstas /* Find the smallest integer mode large enough to hold the 1696233294Sstas entire structure and use that mode instead of BLKmode 1697233294Sstas on the USE insn for the return register. */ 1698233294Sstas for (tmpmode = GET_CLASS_NARROWEST_MODE (MODE_INT); 1699233294Sstas tmpmode != VOIDmode; 1700233294Sstas tmpmode = GET_MODE_WIDER_MODE (tmpmode)) 1701233294Sstas /* Have we found a large enough mode? */ 1702233294Sstas if (GET_MODE_SIZE (tmpmode) >= bytes) 1703233294Sstas break; 1704233294Sstas 1705233294Sstas /* A suitable mode should have been found. */ 1706233294Sstas gcc_assert (tmpmode != VOIDmode); 1707233294Sstas 1708233294Sstas PUT_MODE (result_rtl, tmpmode); 1709233294Sstas } 1710233294Sstas 1711233294Sstas if (GET_MODE_SIZE (tmpmode) < GET_MODE_SIZE (word_mode)) 1712233294Sstas result_reg_mode = word_mode; 1713233294Sstas else 1714233294Sstas result_reg_mode = tmpmode; 1715233294Sstas result_reg = gen_reg_rtx (result_reg_mode); 1716233294Sstas 1717233294Sstas for (i = 0; i < n_regs; i++) 1718233294Sstas emit_move_insn (operand_subword (result_reg, i, 0, result_reg_mode), 1719233294Sstas result_pseudos[i]); 1720233294Sstas 1721233294Sstas if (tmpmode != result_reg_mode) 1722233294Sstas result_reg = gen_lowpart (tmpmode, result_reg); 1723233294Sstas 1724233294Sstas expand_value_return (result_reg); 1725233294Sstas } 1726233294Sstas else if (retval_rhs != 0 1727233294Sstas && !VOID_TYPE_P (TREE_TYPE (retval_rhs)) 1728233294Sstas && (REG_P (result_rtl) 1729233294Sstas || (GET_CODE (result_rtl) == PARALLEL))) 1730233294Sstas { 1731233294Sstas /* Calculate the return value into a temporary (usually a pseudo 1732233294Sstas reg). */ 1733233294Sstas tree ot = TREE_TYPE (DECL_RESULT (current_function_decl)); 1734233294Sstas tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST); 1735233294Sstas 1736233294Sstas val = assign_temp (nt, 0, 0, 1); 1737233294Sstas val = expand_expr (retval_rhs, val, GET_MODE (val), 0); 1738233294Sstas val = force_not_mem (val); 1739233294Sstas /* Return the calculated value. */ 1740233294Sstas expand_value_return (val); 1741233294Sstas } 1742233294Sstas else 1743233294Sstas { 1744233294Sstas /* No hard reg used; calculate value into hard return reg. */ 1745233294Sstas expand_expr (retval, const0_rtx, VOIDmode, 0); 1746233294Sstas expand_value_return (result_rtl); 1747233294Sstas } 1748233294Sstas} 174972448Sassar 175072448Sassar/* Given a pointer to a BLOCK node return nonzero if (and only if) the node 175172448Sassar in question represents the outermost pair of curly braces (i.e. the "body 1752178828Sdfr block") of a function or method. 175372448Sassar 175472448Sassar For any BLOCK node representing a "body block" of a function or method, the 175572448Sassar BLOCK_SUPERCONTEXT of the node will point to another BLOCK node which 175672448Sassar represents the outermost (function) scope for the function or method (i.e. 175772448Sassar the one which includes the formal parameters). The BLOCK_SUPERCONTEXT of 1758233294Sstas *that* node in turn will point to the relevant FUNCTION_DECL node. */ 175972448Sassar 176072448Sassarint 176172448Sassaris_body_block (tree stmt) 176272448Sassar{ 176372448Sassar if (lang_hooks.no_body_blocks) 176472448Sassar return 0; 176572448Sassar 176672448Sassar if (TREE_CODE (stmt) == BLOCK) 1767233294Sstas { 176855682Smarkm tree parent = BLOCK_SUPERCONTEXT (stmt); 176955682Smarkm 177055682Smarkm if (parent && TREE_CODE (parent) == BLOCK) 1771178828Sdfr { 177255682Smarkm tree grandparent = BLOCK_SUPERCONTEXT (parent); 177355682Smarkm 177455682Smarkm if (grandparent && TREE_CODE (grandparent) == FUNCTION_DECL) 177572448Sassar return 1; 177655682Smarkm } 177755682Smarkm } 1778233294Sstas 177955682Smarkm return 0; 178055682Smarkm} 178155682Smarkm 178255682Smarkm/* Emit code to restore vital registers at the beginning of a nonlocal goto 178355682Smarkm handler. */ 178455682Smarkmstatic void 178555682Smarkmexpand_nl_goto_receiver (void) 178655682Smarkm{ 178755682Smarkm /* Clobber the FP when we get here, so we have to make sure it's 178855682Smarkm marked as used by this function. */ 178955682Smarkm emit_insn (gen_rtx_USE (VOIDmode, hard_frame_pointer_rtx)); 179055682Smarkm 179155682Smarkm /* Mark the static chain as clobbered here so life information 179255682Smarkm doesn't get messed up for it. */ 179355682Smarkm emit_insn (gen_rtx_CLOBBER (VOIDmode, static_chain_rtx)); 179455682Smarkm 179555682Smarkm#ifdef HAVE_nonlocal_goto 1796233294Sstas if (! HAVE_nonlocal_goto) 179772448Sassar#endif 179872448Sassar /* First adjust our frame pointer to its actual value. It was 179972448Sassar previously set to the start of the virtual area corresponding to 180072448Sassar the stacked variables when we branched here and now needs to be 180172448Sassar adjusted to the actual hardware fp value. 180272448Sassar 180372448Sassar Assignments are to virtual registers are converted by 180472448Sassar instantiate_virtual_regs into the corresponding assignment 180572448Sassar to the underlying register (fp in this case) that makes 1806233294Sstas the original assignment true. 180772448Sassar So the following insn will actually be 180872448Sassar decrementing fp by STARTING_FRAME_OFFSET. */ 180972448Sassar emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx); 181072448Sassar 181172448Sassar#if ARG_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 181272448Sassar if (fixed_regs[ARG_POINTER_REGNUM]) 181372448Sassar { 181472448Sassar#ifdef ELIMINABLE_REGS 1815233294Sstas /* If the argument pointer can be eliminated in favor of the 181655682Smarkm frame pointer, we don't need to restore it. We assume here 181755682Smarkm that if such an elimination is present, it can always be used. 181855682Smarkm This is the case on all known machines; if we don't make this 181955682Smarkm assumption, we do unnecessary saving on many machines. */ 182055682Smarkm static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS; 182155682Smarkm size_t i; 182255682Smarkm 182372448Sassar for (i = 0; i < ARRAY_SIZE (elim_regs); i++) 182472448Sassar if (elim_regs[i].from == ARG_POINTER_REGNUM 182555682Smarkm && elim_regs[i].to == HARD_FRAME_POINTER_REGNUM) 182655682Smarkm break; 1827233294Sstas 182855682Smarkm if (i == ARRAY_SIZE (elim_regs)) 182955682Smarkm#endif 183055682Smarkm { 183172448Sassar /* Now restore our arg pointer from the address at which it 183255682Smarkm was saved in our stack frame. */ 183355682Smarkm emit_move_insn (virtual_incoming_args_rtx, 1834233294Sstas copy_to_reg (get_arg_pointer_save_area (cfun))); 183555682Smarkm } 183655682Smarkm } 183755682Smarkm#endif 183855682Smarkm 183955682Smarkm#ifdef HAVE_nonlocal_goto_receiver 184055682Smarkm if (HAVE_nonlocal_goto_receiver) 184155682Smarkm emit_insn (gen_nonlocal_goto_receiver ()); 1842233294Sstas#endif 1843233294Sstas 1844233294Sstas /* @@@ This is a kludge. Not all machine descriptions define a blockage 1845233294Sstas insn, but we must not allow the code we just generated to be reordered 1846233294Sstas by scheduling. Specifically, the update of the frame pointer must 1847233294Sstas happen immediately, not later. So emit an ASM_INPUT to act as blockage 184878536Sassar insn. */ 1849233294Sstas emit_insn (gen_rtx_ASM_INPUT (VOIDmode, "")); 185055682Smarkm} 185155682Smarkm 1852233294Sstas/* Generate RTL for the automatic variable declaration DECL. 1853178828Sdfr (Other kinds of declarations are simply ignored if seen here.) */ 185455682Smarkm 185555682Smarkmvoid 185655682Smarkmexpand_decl (tree decl) 1857178828Sdfr{ 185855682Smarkm tree type; 185955682Smarkm 186078536Sassar type = TREE_TYPE (decl); 1861233294Sstas 1862233294Sstas /* For a CONST_DECL, set mode, alignment, and sizes from those of the 1863233294Sstas type in case this node is used in a reference. */ 186478536Sassar if (TREE_CODE (decl) == CONST_DECL) 1865178828Sdfr { 1866178828Sdfr DECL_MODE (decl) = TYPE_MODE (type); 1867233294Sstas DECL_ALIGN (decl) = TYPE_ALIGN (type); 1868233294Sstas DECL_SIZE (decl) = TYPE_SIZE (type); 1869178828Sdfr DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type); 1870233294Sstas return; 187155682Smarkm } 187255682Smarkm 1873233294Sstas /* Otherwise, only automatic variables need any expansion done. Static and 187455682Smarkm external variables, and external functions, will be handled by 187555682Smarkm `assemble_variable' (called from finish_decl). TYPE_DECL requires 187678536Sassar nothing. PARM_DECLs are handled in `assign_parms'. */ 187778536Sassar if (TREE_CODE (decl) != VAR_DECL) 187855682Smarkm return; 187955682Smarkm 188072448Sassar if (TREE_STATIC (decl) || DECL_EXTERNAL (decl)) 188155682Smarkm return; 188255682Smarkm 188355682Smarkm /* Create the RTL representation for the variable. */ 188478536Sassar 1885233294Sstas if (type == error_mark_node) 1886233294Sstas SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx)); 1887233294Sstas 188878536Sassar else if (DECL_SIZE (decl) == 0) 188955682Smarkm /* Variable with incomplete type. */ 189078536Sassar { 189155682Smarkm rtx x; 189278536Sassar if (DECL_INITIAL (decl) == 0) 189378536Sassar /* Error message was already done; now avoid a crash. */ 1894233294Sstas x = gen_rtx_MEM (BLKmode, const0_rtx); 1895233294Sstas else 1896233294Sstas /* An initializer is going to decide the size of this array. 189778536Sassar Until we know the size, represent its address with a reg. */ 1898178828Sdfr x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode)); 1899233294Sstas 1900178828Sdfr set_mem_attributes (x, decl, 1); 1901233294Sstas SET_DECL_RTL (decl, x); 1902233294Sstas } 1903178828Sdfr else if (use_register_for_decl (decl)) 190455682Smarkm { 1905233294Sstas /* Automatic variable that can go in a register. */ 190655682Smarkm int unsignedp = TYPE_UNSIGNED (type); 190755682Smarkm enum machine_mode reg_mode 1908233294Sstas = promote_mode (type, DECL_MODE (decl), &unsignedp, 0); 1909233294Sstas 191055682Smarkm SET_DECL_RTL (decl, gen_reg_rtx (reg_mode)); 1911233294Sstas 1912233294Sstas /* Note if the object is a user variable. */ 1913120948Snectar if (!DECL_ARTIFICIAL (decl)) 1914120948Snectar { 191555682Smarkm mark_user_reg (DECL_RTL (decl)); 191655682Smarkm 1917233294Sstas /* Trust user variables which have a pointer type to really 1918233294Sstas be pointers. Do not trust compiler generated temporaries 1919233294Sstas as our type system is totally busted as it relates to 192055682Smarkm pointer arithmetic which translates into lots of compiler 192155682Smarkm generated objects with pointer types, but which are not really 1922233294Sstas pointers. */ 1923178828Sdfr if (POINTER_TYPE_P (type)) 1924233294Sstas mark_reg_pointer (DECL_RTL (decl), 1925178828Sdfr TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl)))); 1926178828Sdfr } 1927233294Sstas } 1928233294Sstas 1929233294Sstas else if (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST 1930233294Sstas && ! (flag_stack_check && ! STACK_CHECK_BUILTIN 193155682Smarkm && 0 < compare_tree_int (DECL_SIZE_UNIT (decl), 193255682Smarkm STACK_CHECK_MAX_VAR_SIZE))) 193355682Smarkm { 1934233294Sstas /* Variable of fixed size that goes on the stack. */ 193555682Smarkm rtx oldaddr = 0; 193655682Smarkm rtx addr; 1937233294Sstas rtx x; 193855682Smarkm 193955682Smarkm /* If we previously made RTL for this decl, it must be an array 194055682Smarkm whose size was determined by the initializer. 194155682Smarkm The old address was a register; set that register now 194255682Smarkm to the proper address. */ 194355682Smarkm if (DECL_RTL_SET_P (decl)) 194455682Smarkm { 194555682Smarkm gcc_assert (MEM_P (DECL_RTL (decl))); 194655682Smarkm gcc_assert (REG_P (XEXP (DECL_RTL (decl), 0))); 194755682Smarkm oldaddr = XEXP (DECL_RTL (decl), 0); 1948233294Sstas } 194978536Sassar 195078536Sassar /* Set alignment we actually gave this decl. */ 195178536Sassar DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT 195278536Sassar : GET_MODE_BITSIZE (DECL_MODE (decl))); 195378536Sassar DECL_USER_ALIGN (decl) = 0; 195478536Sassar 195578536Sassar x = assign_temp (decl, 1, 1, 1); 195678536Sassar set_mem_attributes (x, decl, 1); 1957233294Sstas SET_DECL_RTL (decl, x); 1958233294Sstas 195978536Sassar if (oldaddr) 1960178828Sdfr { 1961178828Sdfr addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr); 1962233294Sstas if (addr != oldaddr) 196378536Sassar emit_move_insn (oldaddr, addr); 1964233294Sstas } 196578536Sassar } 196678536Sassar else 1967178828Sdfr /* Dynamic-size object: must push space on the stack. */ 196878536Sassar { 196978536Sassar rtx address, size, x; 197078536Sassar 197178536Sassar /* Record the stack pointer on entry to block, if have 1972233294Sstas not already done so. */ 1973178828Sdfr do_pending_stack_adjust (); 1974178828Sdfr 1975233294Sstas /* Compute the variable's size, in bytes. This will expand any 197678536Sassar needed SAVE_EXPRs for the first time. */ 197778536Sassar size = expand_normal (DECL_SIZE_UNIT (decl)); 197878536Sassar free_temp_slots (); 197955682Smarkm 1980233294Sstas /* Allocate space on the stack for the variable. Note that 1981233294Sstas DECL_ALIGN says how the variable is to be aligned and we 1982233294Sstas cannot use it to conclude anything about the alignment of 1983233294Sstas the size. */ 198455682Smarkm address = allocate_dynamic_stack_space (size, NULL_RTX, 198555682Smarkm TYPE_ALIGN (TREE_TYPE (decl))); 1986233294Sstas 198755682Smarkm /* Reference the variable indirect through that rtx. */ 198855682Smarkm x = gen_rtx_MEM (DECL_MODE (decl), address); 198955682Smarkm set_mem_attributes (x, decl, 1); 199055682Smarkm SET_DECL_RTL (decl, x); 199155682Smarkm 199255682Smarkm 199355682Smarkm /* Indicate the alignment we actually gave this variable. */ 199455682Smarkm#ifdef STACK_BOUNDARY 199578536Sassar DECL_ALIGN (decl) = STACK_BOUNDARY; 1996233294Sstas#else 199755682Smarkm DECL_ALIGN (decl) = BIGGEST_ALIGNMENT; 199878536Sassar#endif 199955682Smarkm DECL_USER_ALIGN (decl) = 0; 200055682Smarkm } 2001233294Sstas} 200255682Smarkm 200355682Smarkm/* Emit code to save the current value of stack. */ 200455682Smarkmrtx 200555682Smarkmexpand_stack_save (void) 2006233294Sstas{ 2007233294Sstas rtx ret = NULL_RTX; 2008233294Sstas 2009233294Sstas do_pending_stack_adjust (); 2010233294Sstas emit_stack_save (SAVE_BLOCK, &ret, NULL_RTX); 2011233294Sstas return ret; 2012233294Sstas} 2013233294Sstas 2014233294Sstas/* Emit code to restore the current value of stack. */ 2015233294Sstasvoid 2016233294Sstasexpand_stack_restore (tree var) 2017233294Sstas{ 2018233294Sstas rtx sa = DECL_RTL (var); 2019233294Sstas 2020233294Sstas emit_stack_restore (SAVE_BLOCK, sa, NULL_RTX); 2021233294Sstas} 2022233294Sstas 202355682Smarkm/* DECL is an anonymous union. CLEANUP is a cleanup for DECL. 2024233294Sstas DECL_ELTS is the list of elements that belong to DECL's type. 202555682Smarkm In each, the TREE_VALUE is a VAR_DECL, and the TREE_PURPOSE a cleanup. */ 202678536Sassar 202755682Smarkmvoid 202855682Smarkmexpand_anon_union_decl (tree decl, tree cleanup ATTRIBUTE_UNUSED, 202955682Smarkm tree decl_elts) 203055682Smarkm{ 203155682Smarkm rtx x; 203278536Sassar tree t; 2033233294Sstas 203455682Smarkm /* If any of the elements are addressable, so is the entire union. */ 203578536Sassar for (t = decl_elts; t; t = TREE_CHAIN (t)) 203655682Smarkm if (TREE_ADDRESSABLE (TREE_VALUE (t))) 203755682Smarkm { 2038233294Sstas TREE_ADDRESSABLE (decl) = 1; 2039178828Sdfr break; 204055682Smarkm } 2041178828Sdfr 2042233294Sstas expand_decl (decl); 204355682Smarkm x = DECL_RTL (decl); 2044102647Snectar 2045102647Snectar /* Go through the elements, assigning RTL to each. */ 2046178828Sdfr for (t = decl_elts; t; t = TREE_CHAIN (t)) 2047233294Sstas { 2048233294Sstas tree decl_elt = TREE_VALUE (t); 2049102647Snectar enum machine_mode mode = TYPE_MODE (TREE_TYPE (decl_elt)); 2050102647Snectar rtx decl_rtl; 205155682Smarkm 205255682Smarkm /* If any of the elements are addressable, so is the entire 205355682Smarkm union. */ 2054178828Sdfr if (TREE_USED (decl_elt)) 205555682Smarkm TREE_USED (decl) = 1; 205655682Smarkm 205755682Smarkm /* Propagate the union's alignment to the elements. */ 205855682Smarkm DECL_ALIGN (decl_elt) = DECL_ALIGN (decl); 205955682Smarkm DECL_USER_ALIGN (decl_elt) = DECL_USER_ALIGN (decl); 206055682Smarkm 206155682Smarkm /* If the element has BLKmode and the union doesn't, the union is 206255682Smarkm aligned such that the element doesn't need to have BLKmode, so 206355682Smarkm change the element's mode to the appropriate one for its size. */ 2064233294Sstas if (mode == BLKmode && DECL_MODE (decl) != BLKmode) 2065233294Sstas DECL_MODE (decl_elt) = mode 2066233294Sstas = mode_for_size_tree (DECL_SIZE (decl_elt), MODE_INT, 1); 206755682Smarkm 2068233294Sstas if (mode == GET_MODE (x)) 2069233294Sstas decl_rtl = x; 2070233294Sstas else if (MEM_P (x)) 2071233294Sstas /* (SUBREG (MEM ...)) at RTL generation time is invalid, so we 2072233294Sstas instead create a new MEM rtx with the proper mode. */ 2073233294Sstas decl_rtl = adjust_address_nv (x, mode, 0); 2074233294Sstas else 2075233294Sstas { 2076233294Sstas gcc_assert (REG_P (x)); 2077233294Sstas decl_rtl = gen_lowpart_SUBREG (mode, x); 207855682Smarkm } 207955682Smarkm SET_DECL_RTL (decl_elt, decl_rtl); 2080233294Sstas } 2081233294Sstas} 208255682Smarkm 208355682Smarkm/* Do the insertion of a case label into case_list. The labels are 208455682Smarkm fed to us in descending order from the sorted vector of case labels used 208555682Smarkm in the tree part of the middle end. So the list we construct is 2086233294Sstas sorted in ascending order. The bounds on the case range, LOW and HIGH, 2087233294Sstas are converted to case's index type TYPE. */ 208855682Smarkm 2089233294Sstasstatic struct case_node * 209055682Smarkmadd_case_node (struct case_node *head, tree type, tree low, tree high, 209155682Smarkm tree label) 2092233294Sstas{ 2093233294Sstas tree min_value, max_value; 2094233294Sstas struct case_node *r; 2095233294Sstas 2096233294Sstas gcc_assert (TREE_CODE (low) == INTEGER_CST); 2097233294Sstas gcc_assert (!high || TREE_CODE (high) == INTEGER_CST); 2098233294Sstas 2099233294Sstas min_value = TYPE_MIN_VALUE (type); 2100233294Sstas max_value = TYPE_MAX_VALUE (type); 2101233294Sstas 2102233294Sstas /* If there's no HIGH value, then this is not a case range; it's 2103233294Sstas just a simple case label. But that's just a degenerate case 210455682Smarkm range. 210555682Smarkm If the bounds are equal, turn this into the one-value case. */ 210655682Smarkm if (!high || tree_int_cst_equal (low, high)) 210755682Smarkm { 2108233294Sstas /* If the simple case value is unreachable, ignore it. */ 210955682Smarkm if ((TREE_CODE (min_value) == INTEGER_CST 2110233294Sstas && tree_int_cst_compare (low, min_value) < 0) 211155682Smarkm || (TREE_CODE (max_value) == INTEGER_CST 2112233294Sstas && tree_int_cst_compare (low, max_value) > 0)) 211355682Smarkm return head; 211455682Smarkm low = fold_convert (type, low); 211555682Smarkm high = low; 211655682Smarkm } 2117233294Sstas else 2118233294Sstas { 2119233294Sstas /* If the entire case range is unreachable, ignore it. */ 2120233294Sstas if ((TREE_CODE (min_value) == INTEGER_CST 2121233294Sstas && tree_int_cst_compare (high, min_value) < 0) 2122233294Sstas || (TREE_CODE (max_value) == INTEGER_CST 2123233294Sstas && tree_int_cst_compare (low, max_value) > 0)) 2124233294Sstas return head; 2125233294Sstas 2126233294Sstas /* If the lower bound is less than the index type's minimum 2127233294Sstas value, truncate the range bounds. */ 2128233294Sstas if (TREE_CODE (min_value) == INTEGER_CST 2129233294Sstas && tree_int_cst_compare (low, min_value) < 0) 2130103426Snectar low = min_value; 2131103426Snectar low = fold_convert (type, low); 2132103426Snectar 2133103426Snectar /* If the upper bound is greater than the index type's maximum 2134103426Snectar value, truncate the range bounds. */ 2135103426Snectar if (TREE_CODE (max_value) == INTEGER_CST 2136103426Snectar && tree_int_cst_compare (high, max_value) > 0) 2137103426Snectar high = max_value; 2138233294Sstas high = fold_convert (type, high); 2139233294Sstas } 2140233294Sstas 2141233294Sstas 2142233294Sstas /* Add this label to the chain. Make sure to drop overflow flags. */ 2143233294Sstas r = ggc_alloc (sizeof (struct case_node)); 2144233294Sstas r->low = build_int_cst_wide (TREE_TYPE (low), TREE_INT_CST_LOW (low), 2145233294Sstas TREE_INT_CST_HIGH (low)); 2146233294Sstas r->high = build_int_cst_wide (TREE_TYPE (high), TREE_INT_CST_LOW (high), 2147233294Sstas TREE_INT_CST_HIGH (high)); 2148233294Sstas r->code_label = label; 2149233294Sstas r->parent = r->left = NULL; 2150233294Sstas r->right = head; 2151178828Sdfr return r; 2152178828Sdfr} 2153178828Sdfr 2154178828Sdfr/* Maximum number of case bit tests. */ 2155178828Sdfr#define MAX_CASE_BIT_TESTS 3 2156233294Sstas 2157178828Sdfr/* By default, enable case bit tests on targets with ashlsi3. */ 2158178828Sdfr#ifndef CASE_USE_BIT_TESTS 2159233294Sstas#define CASE_USE_BIT_TESTS (ashl_optab->handlers[word_mode].insn_code \ 2160233294Sstas != CODE_FOR_nothing) 2161233294Sstas#endif 2162233294Sstas 2163233294Sstas 2164233294Sstas/* A case_bit_test represents a set of case nodes that may be 2165233294Sstas selected from using a bit-wise comparison. HI and LO hold 2166233294Sstas the integer to be tested against, LABEL contains the label 2167233294Sstas to jump to upon success and BITS counts the number of case 2168233294Sstas nodes handled by this test, typically the number of bits 2169233294Sstas set in HI:LO. */ 2170233294Sstas 2171233294Sstasstruct case_bit_test 2172178828Sdfr{ 2173178828Sdfr HOST_WIDE_INT hi; 2174233294Sstas HOST_WIDE_INT lo; 2175178828Sdfr rtx label; 2176178828Sdfr int bits; 2177178828Sdfr}; 2178178828Sdfr 2179178828Sdfr/* Determine whether "1 << x" is relatively cheap in word_mode. */ 2180233294Sstas 2181233294Sstasstatic 2182233294Sstasbool lshift_cheap_p (void) 2183233294Sstas{ 2184233294Sstas static bool init = false; 2185233294Sstas static bool cheap = true; 2186233294Sstas 2187233294Sstas if (!init) 2188233294Sstas { 2189233294Sstas rtx reg = gen_rtx_REG (word_mode, 10000); 2190233294Sstas int cost = rtx_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg), SET); 2191233294Sstas cheap = cost < COSTS_N_INSNS (3); 2192233294Sstas init = true; 2193178828Sdfr } 2194178828Sdfr 2195178828Sdfr return cheap; 2196178828Sdfr} 2197178828Sdfr 2198178828Sdfr/* Comparison function for qsort to order bit tests by decreasing 2199178828Sdfr number of case nodes, i.e. the node with the most cases gets 2200178828Sdfr tested first. */ 2201233294Sstas 2202233294Sstasstatic int 2203233294Sstascase_bit_test_cmp (const void *p1, const void *p2) 2204233294Sstas{ 2205233294Sstas const struct case_bit_test *d1 = p1; 2206233294Sstas const struct case_bit_test *d2 = p2; 2207233294Sstas 2208233294Sstas if (d2->bits != d1->bits) 2209233294Sstas return d2->bits - d1->bits; 2210233294Sstas 2211233294Sstas /* Stabilize the sort. */ 2212233294Sstas return CODE_LABEL_NUMBER (d2->label) - CODE_LABEL_NUMBER (d1->label); 2213233294Sstas} 2214178828Sdfr 2215178828Sdfr/* Expand a switch statement by a short sequence of bit-wise 2216178828Sdfr comparisons. "switch(x)" is effectively converted into 2217233294Sstas "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are 2218178828Sdfr integer constants. 2219178828Sdfr 2220233294Sstas INDEX_EXPR is the value being switched on, which is of 2221233294Sstas type INDEX_TYPE. MINVAL is the lowest case value of in 2222233294Sstas the case nodes, of INDEX_TYPE type, and RANGE is highest 2223178828Sdfr value minus MINVAL, also of type INDEX_TYPE. NODES is 2224178828Sdfr the set of case nodes, and DEFAULT_LABEL is the label to 2225178828Sdfr branch to should none of the cases match. 2226178828Sdfr 2227178828Sdfr There *MUST* be MAX_CASE_BIT_TESTS or less unique case 2228178828Sdfr node targets. */ 2229233294Sstas 2230233294Sstasstatic void 2231233294Sstasemit_case_bit_tests (tree index_type, tree index_expr, tree minval, 2232233294Sstas tree range, case_node_ptr nodes, rtx default_label) 2233233294Sstas{ 2234233294Sstas struct case_bit_test test[MAX_CASE_BIT_TESTS]; 2235233294Sstas enum machine_mode mode; 2236233294Sstas rtx expr, index, label; 2237233294Sstas unsigned int i,j,lo,hi; 2238233294Sstas struct case_node *n; 2239233294Sstas unsigned int count; 2240233294Sstas 2241233294Sstas count = 0; 2242233294Sstas for (n = nodes; n; n = n->right) 224355682Smarkm { 2244233294Sstas label = label_rtx (n->code_label); 224578536Sassar for (i = 0; i < count; i++) 2246233294Sstas if (label == test[i].label) 2247233294Sstas break; 2248233294Sstas 2249233294Sstas if (i == count) 225055682Smarkm { 225178536Sassar gcc_assert (count < MAX_CASE_BIT_TESTS); 2252233294Sstas test[i].hi = 0; 2253233294Sstas test[i].lo = 0; 2254233294Sstas test[i].label = label; 2255178828Sdfr test[i].bits = 1; 2256233294Sstas count++; 2257233294Sstas } 2258233294Sstas else 2259233294Sstas test[i].bits++; 2260233294Sstas 2261233294Sstas lo = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 2262233294Sstas n->low, minval), 1); 2263233294Sstas hi = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 2264233294Sstas n->high, minval), 1); 2265233294Sstas for (j = lo; j <= hi; j++) 2266233294Sstas if (j >= HOST_BITS_PER_WIDE_INT) 2267233294Sstas test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT); 2268233294Sstas else 2269233294Sstas test[i].lo |= (HOST_WIDE_INT) 1 << j; 2270233294Sstas } 2271233294Sstas 2272233294Sstas qsort (test, count, sizeof(*test), case_bit_test_cmp); 2273233294Sstas 2274233294Sstas index_expr = fold_build2 (MINUS_EXPR, index_type, 2275233294Sstas fold_convert (index_type, index_expr), 2276233294Sstas fold_convert (index_type, minval)); 2277233294Sstas index = expand_normal (index_expr); 2278233294Sstas do_pending_stack_adjust (); 2279233294Sstas 2280233294Sstas mode = TYPE_MODE (index_type); 228155682Smarkm expr = expand_normal (range); 228255682Smarkm emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1, 228372448Sassar default_label); 228472448Sassar 228572448Sassar index = convert_to_mode (word_mode, index, 0); 228672448Sassar index = expand_binop (word_mode, ashl_optab, const1_rtx, 228772448Sassar index, NULL_RTX, 1, OPTAB_WIDEN); 2288233294Sstas 2289120948Snectar for (i = 0; i < count; i++) 2290178828Sdfr { 229172448Sassar expr = immed_double_const (test[i].lo, test[i].hi, word_mode); 229272448Sassar expr = expand_binop (word_mode, and_optab, index, expr, 2293178828Sdfr NULL_RTX, 1, OPTAB_WIDEN); 2294120948Snectar emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX, 229572448Sassar word_mode, 1, test[i].label); 229672448Sassar } 229772448Sassar 229872448Sassar emit_jump (default_label); 229972448Sassar} 230072448Sassar 230172448Sassar#ifndef HAVE_casesi 230272448Sassar#define HAVE_casesi 0 2303233294Sstas#endif 2304120948Snectar 230572448Sassar#ifndef HAVE_tablejump 230672448Sassar#define HAVE_tablejump 0 230772448Sassar#endif 2308120948Snectar 2309178828Sdfr/* Terminate a case (Pascal/Ada) or switch (C) statement 2310178828Sdfr in which ORIG_INDEX is the expression to be tested. 2311178828Sdfr If ORIG_TYPE is not NULL, it is the original ORIG_INDEX 2312178828Sdfr type as given in the source before any compiler conversions. 231372448Sassar Generate the code to test it and jump to the right place. */ 231472448Sassar 231572448Sassarvoid 231655682Smarkmexpand_case (tree exp) 231755682Smarkm{ 231855682Smarkm tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE; 231955682Smarkm rtx default_label = 0; 2320233294Sstas struct case_node *n; 232155682Smarkm unsigned int count, uniq; 232255682Smarkm rtx index; 232355682Smarkm rtx table_label; 232455682Smarkm int ncases; 232572448Sassar rtx *labelvec; 232672448Sassar int i, fail; 232772448Sassar rtx before_case, end, lab; 232872448Sassar 232955682Smarkm tree vec = SWITCH_LABELS (exp); 233055682Smarkm tree orig_type = TREE_TYPE (exp); 2331178828Sdfr tree index_expr = SWITCH_COND (exp); 2332178828Sdfr tree index_type = TREE_TYPE (index_expr); 2333178828Sdfr int unsignedp = TYPE_UNSIGNED (index_type); 2334178828Sdfr 2335178828Sdfr /* The insn after which the case dispatch should finally 2336178828Sdfr be emitted. Zero for a dummy. */ 2337178828Sdfr rtx start; 2338178828Sdfr 2339233294Sstas /* A list of case labels; it is first built as a list and it may then 2340178828Sdfr be rearranged into a nearly balanced binary tree. */ 2341178828Sdfr struct case_node *case_list = 0; 2342178828Sdfr 2343178828Sdfr /* Label to jump to if no case matches. */ 2344178828Sdfr tree default_label_decl; 2345178828Sdfr 2346178828Sdfr /* The switch body is lowered in gimplify.c, we should never have 2347178828Sdfr switches with a non-NULL SWITCH_BODY here. */ 2348178828Sdfr gcc_assert (!SWITCH_BODY (exp)); 2349178828Sdfr gcc_assert (SWITCH_LABELS (exp)); 2350178828Sdfr 2351178828Sdfr do_pending_stack_adjust (); 2352178828Sdfr 2353233294Sstas /* An ERROR_MARK occurs for various reasons including invalid data type. */ 2354178828Sdfr if (index_type != error_mark_node) 2355178828Sdfr { 2356178828Sdfr tree elt; 2357178828Sdfr bitmap label_bitmap; 2358178828Sdfr 2359178828Sdfr /* cleanup_tree_cfg removes all SWITCH_EXPR with their index 2360178828Sdfr expressions being INTEGER_CST. */ 2361178828Sdfr gcc_assert (TREE_CODE (index_expr) != INTEGER_CST); 2362178828Sdfr 2363178828Sdfr /* The default case is at the end of TREE_VEC. */ 2364178828Sdfr elt = TREE_VEC_ELT (vec, TREE_VEC_LENGTH (vec) - 1); 2365178828Sdfr gcc_assert (!CASE_HIGH (elt)); 2366233294Sstas gcc_assert (!CASE_LOW (elt)); 2367178828Sdfr default_label_decl = CASE_LABEL (elt); 2368178828Sdfr 2369178828Sdfr for (i = TREE_VEC_LENGTH (vec) - 1; --i >= 0; ) 2370178828Sdfr { 2371178828Sdfr tree low, high; 2372178828Sdfr elt = TREE_VEC_ELT (vec, i); 2373178828Sdfr 2374178828Sdfr low = CASE_LOW (elt); 2375233294Sstas gcc_assert (low); 2376233294Sstas high = CASE_HIGH (elt); 2377233294Sstas 2378233294Sstas /* Discard empty ranges. */ 2379233294Sstas if (high && INT_CST_LT (high, low)) 2380233294Sstas continue; 2381233294Sstas 2382233294Sstas case_list = add_case_node (case_list, index_type, low, high, 2383233294Sstas CASE_LABEL (elt)); 2384233294Sstas } 2385233294Sstas 2386233294Sstas 2387233294Sstas before_case = start = get_last_insn (); 2388233294Sstas default_label = label_rtx (default_label_decl); 2389233294Sstas 2390233294Sstas /* Get upper and lower bounds of case values. */ 2391233294Sstas 2392233294Sstas uniq = 0; 2393178828Sdfr count = 0; 2394178828Sdfr label_bitmap = BITMAP_ALLOC (NULL); 2395178828Sdfr for (n = case_list; n; n = n->right) 2396178828Sdfr { 2397178828Sdfr /* Count the elements and track the largest and smallest 2398178828Sdfr of them (treating them as signed even if they are not). */ 2399178828Sdfr if (count++ == 0) 2400233294Sstas { 2401178828Sdfr minval = n->low; 2402233294Sstas maxval = n->high; 2403233294Sstas } 2404233294Sstas else 2405178828Sdfr { 2406178828Sdfr if (INT_CST_LT (n->low, minval)) 2407178828Sdfr minval = n->low; 2408233294Sstas if (INT_CST_LT (maxval, n->high)) 2409233294Sstas maxval = n->high; 2410233294Sstas } 2411233294Sstas /* A range counts double, since it requires two compares. */ 2412233294Sstas if (! tree_int_cst_equal (n->low, n->high)) 2413178828Sdfr count++; 2414178828Sdfr 2415178828Sdfr /* If we have not seen this label yet, then increase the 2416233294Sstas number of unique case node targets seen. */ 2417178828Sdfr lab = label_rtx (n->code_label); 2418178828Sdfr if (!bitmap_bit_p (label_bitmap, CODE_LABEL_NUMBER (lab))) 2419178828Sdfr { 2420178828Sdfr bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab)); 2421178828Sdfr uniq++; 2422178828Sdfr } 2423178828Sdfr } 2424178828Sdfr 2425178828Sdfr BITMAP_FREE (label_bitmap); 2426178828Sdfr 2427178828Sdfr /* cleanup_tree_cfg removes all SWITCH_EXPR with a single 2428178828Sdfr destination, such as one with a default case only. However, 2429233294Sstas it doesn't remove cases that are out of range for the switch 2430178828Sdfr type, so we may still get a zero here. */ 2431178828Sdfr if (count == 0) 2432178828Sdfr { 2433178828Sdfr emit_jump (default_label); 2434233294Sstas return; 2435178828Sdfr } 2436178828Sdfr 2437233294Sstas /* Compute span of values. */ 2438233294Sstas range = fold_build2 (MINUS_EXPR, index_type, maxval, minval); 2439233294Sstas 2440178828Sdfr /* Try implementing this switch statement by a short sequence of 2441178828Sdfr bit-wise comparisons. However, we let the binary-tree case 2442178828Sdfr below handle constant index expressions. */ 2443178828Sdfr if (CASE_USE_BIT_TESTS 2444178828Sdfr && ! TREE_CONSTANT (index_expr) 2445178828Sdfr && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0 2446178828Sdfr && compare_tree_int (range, 0) > 0 2447233294Sstas && lshift_cheap_p () 2448178828Sdfr && ((uniq == 1 && count >= 3) 2449178828Sdfr || (uniq == 2 && count >= 5) 2450233294Sstas || (uniq == 3 && count >= 6))) 2451178828Sdfr { 2452178828Sdfr /* Optimize the case where all the case values fit in a 2453233294Sstas word without having to subtract MINVAL. In this case, 2454178828Sdfr we can optimize away the subtraction. */ 2455178828Sdfr if (compare_tree_int (minval, 0) > 0 2456178828Sdfr && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0) 2457178828Sdfr { 2458233294Sstas minval = build_int_cst (index_type, 0); 2459233294Sstas range = maxval; 2460233294Sstas } 2461178828Sdfr emit_case_bit_tests (index_type, index_expr, minval, range, 2462178828Sdfr case_list, default_label); 2463178828Sdfr } 2464178828Sdfr 2465178828Sdfr /* If range of values is much bigger than number of values, 2466178828Sdfr make a sequence of conditional branches instead of a dispatch. 2467233294Sstas If the switch-index is a constant, do it this way 2468233294Sstas because we can optimize it. */ 2469233294Sstas 2470233294Sstas else if (count < case_values_threshold () 2471233294Sstas || compare_tree_int (range, 2472233294Sstas (optimize_size ? 3 : 10) * count) > 0 2473233294Sstas /* RANGE may be signed, and really large ranges will show up 2474233294Sstas as negative numbers. */ 2475233294Sstas || compare_tree_int (range, 0) < 0 2476233294Sstas#ifndef ASM_OUTPUT_ADDR_DIFF_ELT 2477233294Sstas || flag_pic 2478178828Sdfr#endif 2479233294Sstas || !flag_jump_tables 2480233294Sstas || TREE_CONSTANT (index_expr) 2481178828Sdfr /* If neither casesi or tablejump is available, we can 2482233294Sstas only go this way. */ 248355682Smarkm || (!HAVE_casesi && !HAVE_tablejump)) 2484233294Sstas { 2485233294Sstas index = expand_normal (index_expr); 2486233294Sstas 2487233294Sstas /* If the index is a short or char that we do not have 248857416Smarkm an insn to handle comparisons directly, convert it to 2489233294Sstas a full integer now, rather than letting each comparison 2490233294Sstas generate the conversion. */ 2491233294Sstas 2492233294Sstas if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT 2493233294Sstas && ! have_insn_for (COMPARE, GET_MODE (index))) 2494233294Sstas { 2495233294Sstas enum machine_mode wider_mode; 2496233294Sstas for (wider_mode = GET_MODE (index); wider_mode != VOIDmode; 2497233294Sstas wider_mode = GET_MODE_WIDER_MODE (wider_mode)) 2498233294Sstas if (have_insn_for (COMPARE, wider_mode)) 2499233294Sstas { 2500233294Sstas index = convert_to_mode (wider_mode, index, unsignedp); 2501233294Sstas break; 2502233294Sstas } 2503233294Sstas } 2504233294Sstas 2505233294Sstas do_pending_stack_adjust (); 2506233294Sstas 2507233294Sstas if (MEM_P (index)) 2508233294Sstas index = copy_to_reg (index); 2509233294Sstas 2510233294Sstas /* We generate a binary decision tree to select the 2511233294Sstas appropriate target code. This is done as follows: 2512233294Sstas 2513233294Sstas The list of cases is rearranged into a binary tree, 2514233294Sstas nearly optimal assuming equal probability for each case. 2515233294Sstas 2516233294Sstas The tree is transformed into RTL, eliminating 2517233294Sstas redundant test conditions at the same time. 2518233294Sstas 251955682Smarkm If program flow could reach the end of the 252055682Smarkm decision tree an unconditional jump to the 252155682Smarkm default code is emitted. */ 2522233294Sstas 2523233294Sstas use_cost_table 2524233294Sstas = (TREE_CODE (orig_type) != ENUMERAL_TYPE 2525233294Sstas && estimate_case_costs (case_list)); 2526233294Sstas balance_case_nodes (&case_list, NULL); 2527233294Sstas emit_case_nodes (index, case_list, default_label, index_type); 2528233294Sstas emit_jump (default_label); 2529233294Sstas } 2530233294Sstas else 2531233294Sstas { 2532233294Sstas table_label = gen_label_rtx (); 2533233294Sstas if (! try_casesi (index_type, index_expr, minval, range, 2534233294Sstas table_label, default_label)) 2535233294Sstas { 2536233294Sstas bool ok; 253755682Smarkm 2538233294Sstas /* Index jumptables from zero for suitable values of 2539233294Sstas minval to avoid a subtraction. */ 2540233294Sstas if (! optimize_size 2541233294Sstas && compare_tree_int (minval, 0) > 0 2542233294Sstas && compare_tree_int (minval, 3) < 0) 2543233294Sstas { 2544233294Sstas minval = build_int_cst (index_type, 0); 2545233294Sstas range = maxval; 254672448Sassar } 254772448Sassar 2548233294Sstas ok = try_tablejump (index_type, index_expr, minval, range, 2549233294Sstas table_label, default_label); 255072448Sassar gcc_assert (ok); 2551233294Sstas } 2552233294Sstas 2553233294Sstas /* Get table of labels to jump to, in order of case index. */ 255472448Sassar 2555233294Sstas ncases = tree_low_cst (range, 0) + 1; 255672448Sassar labelvec = alloca (ncases * sizeof (rtx)); 2557233294Sstas memset (labelvec, 0, ncases * sizeof (rtx)); 2558233294Sstas 2559233294Sstas for (n = case_list; n; n = n->right) 2560233294Sstas { 2561233294Sstas /* Compute the low and high bounds relative to the minimum 2562233294Sstas value since that should fit in a HOST_WIDE_INT while the 2563233294Sstas actual values may not. */ 2564233294Sstas HOST_WIDE_INT i_low 2565233294Sstas = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 256672448Sassar n->low, minval), 1); 2567233294Sstas HOST_WIDE_INT i_high 2568233294Sstas = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 2569233294Sstas n->high, minval), 1); 2570233294Sstas HOST_WIDE_INT i; 2571233294Sstas 2572233294Sstas for (i = i_low; i <= i_high; i ++) 2573233294Sstas labelvec[i] 2574233294Sstas = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label)); 2575233294Sstas } 2576233294Sstas 2577233294Sstas /* Fill in the gaps with the default. */ 257872448Sassar for (i = 0; i < ncases; i++) 2579233294Sstas if (labelvec[i] == 0) 2580233294Sstas labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label); 258172448Sassar 258272448Sassar /* Output the table. */ 258372448Sassar emit_label (table_label); 2584233294Sstas 258572448Sassar if (CASE_VECTOR_PC_RELATIVE || flag_pic) 2586233294Sstas emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE, 2587233294Sstas gen_rtx_LABEL_REF (Pmode, table_label), 2588233294Sstas gen_rtvec_v (ncases, labelvec), 2589233294Sstas const0_rtx, const0_rtx)); 2590233294Sstas else 259172448Sassar emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE, 2592233294Sstas gen_rtvec_v (ncases, labelvec))); 2593233294Sstas 2594233294Sstas /* Record no drop-through after the table. */ 2595233294Sstas emit_barrier (); 2596233294Sstas } 2597233294Sstas 2598233294Sstas before_case = NEXT_INSN (before_case); 2599233294Sstas end = get_last_insn (); 2600233294Sstas fail = squeeze_notes (&before_case, &end); 2601233294Sstas gcc_assert (!fail); 2602233294Sstas reorder_insns (before_case, end, start); 2603233294Sstas } 2604233294Sstas 2605233294Sstas free_temp_slots (); 2606233294Sstas} 2607233294Sstas 2608233294Sstas/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */ 2609233294Sstas 2610233294Sstasstatic void 2611233294Sstasdo_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label, 2612233294Sstas int unsignedp) 2613233294Sstas{ 2614233294Sstas do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode, 2615233294Sstas NULL_RTX, NULL_RTX, label); 2616233294Sstas} 2617233294Sstas 2618233294Sstas/* Not all case values are encountered equally. This function 2619233294Sstas uses a heuristic to weight case labels, in cases where that 2620233294Sstas looks like a reasonable thing to do. 2621233294Sstas 2622233294Sstas Right now, all we try to guess is text, and we establish the 2623233294Sstas following weights: 2624233294Sstas 2625233294Sstas chars above space: 16 2626233294Sstas digits: 16 2627233294Sstas default: 12 2628233294Sstas space, punct: 8 262972448Sassar tab: 4 263072448Sassar newline: 2 2631233294Sstas other "\" chars: 1 2632233294Sstas remaining chars: 0 2633233294Sstas 2634233294Sstas If we find any cases in the switch that are not either -1 or in the range 2635233294Sstas of valid ASCII characters, or are control characters other than those 2636233294Sstas commonly used with "\", don't treat this switch scanning text. 2637233294Sstas 2638233294Sstas Return 1 if these nodes are suitable for cost estimation, otherwise 2639233294Sstas return 0. */ 2640233294Sstas 2641233294Sstasstatic int 2642233294Sstasestimate_case_costs (case_node_ptr node) 2643233294Sstas{ 2644233294Sstas tree min_ascii = integer_minus_one_node; 2645233294Sstas tree max_ascii = build_int_cst (TREE_TYPE (node->high), 127); 2646233294Sstas case_node_ptr n; 2647233294Sstas int i; 2648233294Sstas 2649233294Sstas /* If we haven't already made the cost table, make it now. Note that the 2650233294Sstas lower bound of the table is -1, not zero. */ 2651 2652 if (! cost_table_initialized) 2653 { 2654 cost_table_initialized = 1; 2655 2656 for (i = 0; i < 128; i++) 2657 { 2658 if (ISALNUM (i)) 2659 COST_TABLE (i) = 16; 2660 else if (ISPUNCT (i)) 2661 COST_TABLE (i) = 8; 2662 else if (ISCNTRL (i)) 2663 COST_TABLE (i) = -1; 2664 } 2665 2666 COST_TABLE (' ') = 8; 2667 COST_TABLE ('\t') = 4; 2668 COST_TABLE ('\0') = 4; 2669 COST_TABLE ('\n') = 2; 2670 COST_TABLE ('\f') = 1; 2671 COST_TABLE ('\v') = 1; 2672 COST_TABLE ('\b') = 1; 2673 } 2674 2675 /* See if all the case expressions look like text. It is text if the 2676 constant is >= -1 and the highest constant is <= 127. Do all comparisons 2677 as signed arithmetic since we don't want to ever access cost_table with a 2678 value less than -1. Also check that none of the constants in a range 2679 are strange control characters. */ 2680 2681 for (n = node; n; n = n->right) 2682 { 2683 if ((INT_CST_LT (n->low, min_ascii)) || INT_CST_LT (max_ascii, n->high)) 2684 return 0; 2685 2686 for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low); 2687 i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++) 2688 if (COST_TABLE (i) < 0) 2689 return 0; 2690 } 2691 2692 /* All interesting values are within the range of interesting 2693 ASCII characters. */ 2694 return 1; 2695} 2696 2697/* Take an ordered list of case nodes 2698 and transform them into a near optimal binary tree, 2699 on the assumption that any target code selection value is as 2700 likely as any other. 2701 2702 The transformation is performed by splitting the ordered 2703 list into two equal sections plus a pivot. The parts are 2704 then attached to the pivot as left and right branches. Each 2705 branch is then transformed recursively. */ 2706 2707static void 2708balance_case_nodes (case_node_ptr *head, case_node_ptr parent) 2709{ 2710 case_node_ptr np; 2711 2712 np = *head; 2713 if (np) 2714 { 2715 int cost = 0; 2716 int i = 0; 2717 int ranges = 0; 2718 case_node_ptr *npp; 2719 case_node_ptr left; 2720 2721 /* Count the number of entries on branch. Also count the ranges. */ 2722 2723 while (np) 2724 { 2725 if (!tree_int_cst_equal (np->low, np->high)) 2726 { 2727 ranges++; 2728 if (use_cost_table) 2729 cost += COST_TABLE (TREE_INT_CST_LOW (np->high)); 2730 } 2731 2732 if (use_cost_table) 2733 cost += COST_TABLE (TREE_INT_CST_LOW (np->low)); 2734 2735 i++; 2736 np = np->right; 2737 } 2738 2739 if (i > 2) 2740 { 2741 /* Split this list if it is long enough for that to help. */ 2742 npp = head; 2743 left = *npp; 2744 if (use_cost_table) 2745 { 2746 /* Find the place in the list that bisects the list's total cost, 2747 Here I gets half the total cost. */ 2748 int n_moved = 0; 2749 i = (cost + 1) / 2; 2750 while (1) 2751 { 2752 /* Skip nodes while their cost does not reach that amount. */ 2753 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high)) 2754 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high)); 2755 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low)); 2756 if (i <= 0) 2757 break; 2758 npp = &(*npp)->right; 2759 n_moved += 1; 2760 } 2761 if (n_moved == 0) 2762 { 2763 /* Leave this branch lopsided, but optimize left-hand 2764 side and fill in `parent' fields for right-hand side. */ 2765 np = *head; 2766 np->parent = parent; 2767 balance_case_nodes (&np->left, np); 2768 for (; np->right; np = np->right) 2769 np->right->parent = np; 2770 return; 2771 } 2772 } 2773 /* If there are just three nodes, split at the middle one. */ 2774 else if (i == 3) 2775 npp = &(*npp)->right; 2776 else 2777 { 2778 /* Find the place in the list that bisects the list's total cost, 2779 where ranges count as 2. 2780 Here I gets half the total cost. */ 2781 i = (i + ranges + 1) / 2; 2782 while (1) 2783 { 2784 /* Skip nodes while their cost does not reach that amount. */ 2785 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high)) 2786 i--; 2787 i--; 2788 if (i <= 0) 2789 break; 2790 npp = &(*npp)->right; 2791 } 2792 } 2793 *head = np = *npp; 2794 *npp = 0; 2795 np->parent = parent; 2796 np->left = left; 2797 2798 /* Optimize each of the two split parts. */ 2799 balance_case_nodes (&np->left, np); 2800 balance_case_nodes (&np->right, np); 2801 } 2802 else 2803 { 2804 /* Else leave this branch as one level, 2805 but fill in `parent' fields. */ 2806 np = *head; 2807 np->parent = parent; 2808 for (; np->right; np = np->right) 2809 np->right->parent = np; 2810 } 2811 } 2812} 2813 2814/* Search the parent sections of the case node tree 2815 to see if a test for the lower bound of NODE would be redundant. 2816 INDEX_TYPE is the type of the index expression. 2817 2818 The instructions to generate the case decision tree are 2819 output in the same order as nodes are processed so it is 2820 known that if a parent node checks the range of the current 2821 node minus one that the current node is bounded at its lower 2822 span. Thus the test would be redundant. */ 2823 2824static int 2825node_has_low_bound (case_node_ptr node, tree index_type) 2826{ 2827 tree low_minus_one; 2828 case_node_ptr pnode; 2829 2830 /* If the lower bound of this node is the lowest value in the index type, 2831 we need not test it. */ 2832 2833 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type))) 2834 return 1; 2835 2836 /* If this node has a left branch, the value at the left must be less 2837 than that at this node, so it cannot be bounded at the bottom and 2838 we need not bother testing any further. */ 2839 2840 if (node->left) 2841 return 0; 2842 2843 low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), 2844 node->low, 2845 build_int_cst (TREE_TYPE (node->low), 1)); 2846 2847 /* If the subtraction above overflowed, we can't verify anything. 2848 Otherwise, look for a parent that tests our value - 1. */ 2849 2850 if (! tree_int_cst_lt (low_minus_one, node->low)) 2851 return 0; 2852 2853 for (pnode = node->parent; pnode; pnode = pnode->parent) 2854 if (tree_int_cst_equal (low_minus_one, pnode->high)) 2855 return 1; 2856 2857 return 0; 2858} 2859 2860/* Search the parent sections of the case node tree 2861 to see if a test for the upper bound of NODE would be redundant. 2862 INDEX_TYPE is the type of the index expression. 2863 2864 The instructions to generate the case decision tree are 2865 output in the same order as nodes are processed so it is 2866 known that if a parent node checks the range of the current 2867 node plus one that the current node is bounded at its upper 2868 span. Thus the test would be redundant. */ 2869 2870static int 2871node_has_high_bound (case_node_ptr node, tree index_type) 2872{ 2873 tree high_plus_one; 2874 case_node_ptr pnode; 2875 2876 /* If there is no upper bound, obviously no test is needed. */ 2877 2878 if (TYPE_MAX_VALUE (index_type) == NULL) 2879 return 1; 2880 2881 /* If the upper bound of this node is the highest value in the type 2882 of the index expression, we need not test against it. */ 2883 2884 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type))) 2885 return 1; 2886 2887 /* If this node has a right branch, the value at the right must be greater 2888 than that at this node, so it cannot be bounded at the top and 2889 we need not bother testing any further. */ 2890 2891 if (node->right) 2892 return 0; 2893 2894 high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), 2895 node->high, 2896 build_int_cst (TREE_TYPE (node->high), 1)); 2897 2898 /* If the addition above overflowed, we can't verify anything. 2899 Otherwise, look for a parent that tests our value + 1. */ 2900 2901 if (! tree_int_cst_lt (node->high, high_plus_one)) 2902 return 0; 2903 2904 for (pnode = node->parent; pnode; pnode = pnode->parent) 2905 if (tree_int_cst_equal (high_plus_one, pnode->low)) 2906 return 1; 2907 2908 return 0; 2909} 2910 2911/* Search the parent sections of the 2912 case node tree to see if both tests for the upper and lower 2913 bounds of NODE would be redundant. */ 2914 2915static int 2916node_is_bounded (case_node_ptr node, tree index_type) 2917{ 2918 return (node_has_low_bound (node, index_type) 2919 && node_has_high_bound (node, index_type)); 2920} 2921 2922/* Emit step-by-step code to select a case for the value of INDEX. 2923 The thus generated decision tree follows the form of the 2924 case-node binary tree NODE, whose nodes represent test conditions. 2925 INDEX_TYPE is the type of the index of the switch. 2926 2927 Care is taken to prune redundant tests from the decision tree 2928 by detecting any boundary conditions already checked by 2929 emitted rtx. (See node_has_high_bound, node_has_low_bound 2930 and node_is_bounded, above.) 2931 2932 Where the test conditions can be shown to be redundant we emit 2933 an unconditional jump to the target code. As a further 2934 optimization, the subordinates of a tree node are examined to 2935 check for bounded nodes. In this case conditional and/or 2936 unconditional jumps as a result of the boundary check for the 2937 current node are arranged to target the subordinates associated 2938 code for out of bound conditions on the current node. 2939 2940 We can assume that when control reaches the code generated here, 2941 the index value has already been compared with the parents 2942 of this node, and determined to be on the same side of each parent 2943 as this node is. Thus, if this node tests for the value 51, 2944 and a parent tested for 52, we don't need to consider 2945 the possibility of a value greater than 51. If another parent 2946 tests for the value 50, then this node need not test anything. */ 2947 2948static void 2949emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, 2950 tree index_type) 2951{ 2952 /* If INDEX has an unsigned type, we must make unsigned branches. */ 2953 int unsignedp = TYPE_UNSIGNED (index_type); 2954 enum machine_mode mode = GET_MODE (index); 2955 enum machine_mode imode = TYPE_MODE (index_type); 2956 2957 /* Handle indices detected as constant during RTL expansion. */ 2958 if (mode == VOIDmode) 2959 mode = imode; 2960 2961 /* See if our parents have already tested everything for us. 2962 If they have, emit an unconditional jump for this node. */ 2963 if (node_is_bounded (node, index_type)) 2964 emit_jump (label_rtx (node->code_label)); 2965 2966 else if (tree_int_cst_equal (node->low, node->high)) 2967 { 2968 /* Node is single valued. First see if the index expression matches 2969 this node and then check our children, if any. */ 2970 2971 do_jump_if_equal (mode, index, 2972 convert_modes (mode, imode, 2973 expand_normal (node->low), 2974 unsignedp), 2975 label_rtx (node->code_label), unsignedp); 2976 2977 if (node->right != 0 && node->left != 0) 2978 { 2979 /* This node has children on both sides. 2980 Dispatch to one side or the other 2981 by comparing the index value with this node's value. 2982 If one subtree is bounded, check that one first, 2983 so we can avoid real branches in the tree. */ 2984 2985 if (node_is_bounded (node->right, index_type)) 2986 { 2987 emit_cmp_and_jump_insns (index, 2988 convert_modes 2989 (mode, imode, 2990 expand_normal (node->high), 2991 unsignedp), 2992 GT, NULL_RTX, mode, unsignedp, 2993 label_rtx (node->right->code_label)); 2994 emit_case_nodes (index, node->left, default_label, index_type); 2995 } 2996 2997 else if (node_is_bounded (node->left, index_type)) 2998 { 2999 emit_cmp_and_jump_insns (index, 3000 convert_modes 3001 (mode, imode, 3002 expand_normal (node->high), 3003 unsignedp), 3004 LT, NULL_RTX, mode, unsignedp, 3005 label_rtx (node->left->code_label)); 3006 emit_case_nodes (index, node->right, default_label, index_type); 3007 } 3008 3009 /* If both children are single-valued cases with no 3010 children, finish up all the work. This way, we can save 3011 one ordered comparison. */ 3012 else if (tree_int_cst_equal (node->right->low, node->right->high) 3013 && node->right->left == 0 3014 && node->right->right == 0 3015 && tree_int_cst_equal (node->left->low, node->left->high) 3016 && node->left->left == 0 3017 && node->left->right == 0) 3018 { 3019 /* Neither node is bounded. First distinguish the two sides; 3020 then emit the code for one side at a time. */ 3021 3022 /* See if the value matches what the right hand side 3023 wants. */ 3024 do_jump_if_equal (mode, index, 3025 convert_modes (mode, imode, 3026 expand_normal (node->right->low), 3027 unsignedp), 3028 label_rtx (node->right->code_label), 3029 unsignedp); 3030 3031 /* See if the value matches what the left hand side 3032 wants. */ 3033 do_jump_if_equal (mode, index, 3034 convert_modes (mode, imode, 3035 expand_normal (node->left->low), 3036 unsignedp), 3037 label_rtx (node->left->code_label), 3038 unsignedp); 3039 } 3040 3041 else 3042 { 3043 /* Neither node is bounded. First distinguish the two sides; 3044 then emit the code for one side at a time. */ 3045 3046 tree test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE); 3047 3048 /* See if the value is on the right. */ 3049 emit_cmp_and_jump_insns (index, 3050 convert_modes 3051 (mode, imode, 3052 expand_normal (node->high), 3053 unsignedp), 3054 GT, NULL_RTX, mode, unsignedp, 3055 label_rtx (test_label)); 3056 3057 /* Value must be on the left. 3058 Handle the left-hand subtree. */ 3059 emit_case_nodes (index, node->left, default_label, index_type); 3060 /* If left-hand subtree does nothing, 3061 go to default. */ 3062 emit_jump (default_label); 3063 3064 /* Code branches here for the right-hand subtree. */ 3065 expand_label (test_label); 3066 emit_case_nodes (index, node->right, default_label, index_type); 3067 } 3068 } 3069 3070 else if (node->right != 0 && node->left == 0) 3071 { 3072 /* Here we have a right child but no left so we issue a conditional 3073 branch to default and process the right child. 3074 3075 Omit the conditional branch to default if the right child 3076 does not have any children and is single valued; it would 3077 cost too much space to save so little time. */ 3078 3079 if (node->right->right || node->right->left 3080 || !tree_int_cst_equal (node->right->low, node->right->high)) 3081 { 3082 if (!node_has_low_bound (node, index_type)) 3083 { 3084 emit_cmp_and_jump_insns (index, 3085 convert_modes 3086 (mode, imode, 3087 expand_normal (node->high), 3088 unsignedp), 3089 LT, NULL_RTX, mode, unsignedp, 3090 default_label); 3091 } 3092 3093 emit_case_nodes (index, node->right, default_label, index_type); 3094 } 3095 else 3096 /* We cannot process node->right normally 3097 since we haven't ruled out the numbers less than 3098 this node's value. So handle node->right explicitly. */ 3099 do_jump_if_equal (mode, index, 3100 convert_modes 3101 (mode, imode, 3102 expand_normal (node->right->low), 3103 unsignedp), 3104 label_rtx (node->right->code_label), unsignedp); 3105 } 3106 3107 else if (node->right == 0 && node->left != 0) 3108 { 3109 /* Just one subtree, on the left. */ 3110 if (node->left->left || node->left->right 3111 || !tree_int_cst_equal (node->left->low, node->left->high)) 3112 { 3113 if (!node_has_high_bound (node, index_type)) 3114 { 3115 emit_cmp_and_jump_insns (index, 3116 convert_modes 3117 (mode, imode, 3118 expand_normal (node->high), 3119 unsignedp), 3120 GT, NULL_RTX, mode, unsignedp, 3121 default_label); 3122 } 3123 3124 emit_case_nodes (index, node->left, default_label, index_type); 3125 } 3126 else 3127 /* We cannot process node->left normally 3128 since we haven't ruled out the numbers less than 3129 this node's value. So handle node->left explicitly. */ 3130 do_jump_if_equal (mode, index, 3131 convert_modes 3132 (mode, imode, 3133 expand_normal (node->left->low), 3134 unsignedp), 3135 label_rtx (node->left->code_label), unsignedp); 3136 } 3137 } 3138 else 3139 { 3140 /* Node is a range. These cases are very similar to those for a single 3141 value, except that we do not start by testing whether this node 3142 is the one to branch to. */ 3143 3144 if (node->right != 0 && node->left != 0) 3145 { 3146 /* Node has subtrees on both sides. 3147 If the right-hand subtree is bounded, 3148 test for it first, since we can go straight there. 3149 Otherwise, we need to make a branch in the control structure, 3150 then handle the two subtrees. */ 3151 tree test_label = 0; 3152 3153 if (node_is_bounded (node->right, index_type)) 3154 /* Right hand node is fully bounded so we can eliminate any 3155 testing and branch directly to the target code. */ 3156 emit_cmp_and_jump_insns (index, 3157 convert_modes 3158 (mode, imode, 3159 expand_normal (node->high), 3160 unsignedp), 3161 GT, NULL_RTX, mode, unsignedp, 3162 label_rtx (node->right->code_label)); 3163 else 3164 { 3165 /* Right hand node requires testing. 3166 Branch to a label where we will handle it later. */ 3167 3168 test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE); 3169 emit_cmp_and_jump_insns (index, 3170 convert_modes 3171 (mode, imode, 3172 expand_normal (node->high), 3173 unsignedp), 3174 GT, NULL_RTX, mode, unsignedp, 3175 label_rtx (test_label)); 3176 } 3177 3178 /* Value belongs to this node or to the left-hand subtree. */ 3179 3180 emit_cmp_and_jump_insns (index, 3181 convert_modes 3182 (mode, imode, 3183 expand_normal (node->low), 3184 unsignedp), 3185 GE, NULL_RTX, mode, unsignedp, 3186 label_rtx (node->code_label)); 3187 3188 /* Handle the left-hand subtree. */ 3189 emit_case_nodes (index, node->left, default_label, index_type); 3190 3191 /* If right node had to be handled later, do that now. */ 3192 3193 if (test_label) 3194 { 3195 /* If the left-hand subtree fell through, 3196 don't let it fall into the right-hand subtree. */ 3197 emit_jump (default_label); 3198 3199 expand_label (test_label); 3200 emit_case_nodes (index, node->right, default_label, index_type); 3201 } 3202 } 3203 3204 else if (node->right != 0 && node->left == 0) 3205 { 3206 /* Deal with values to the left of this node, 3207 if they are possible. */ 3208 if (!node_has_low_bound (node, index_type)) 3209 { 3210 emit_cmp_and_jump_insns (index, 3211 convert_modes 3212 (mode, imode, 3213 expand_normal (node->low), 3214 unsignedp), 3215 LT, NULL_RTX, mode, unsignedp, 3216 default_label); 3217 } 3218 3219 /* Value belongs to this node or to the right-hand subtree. */ 3220 3221 emit_cmp_and_jump_insns (index, 3222 convert_modes 3223 (mode, imode, 3224 expand_normal (node->high), 3225 unsignedp), 3226 LE, NULL_RTX, mode, unsignedp, 3227 label_rtx (node->code_label)); 3228 3229 emit_case_nodes (index, node->right, default_label, index_type); 3230 } 3231 3232 else if (node->right == 0 && node->left != 0) 3233 { 3234 /* Deal with values to the right of this node, 3235 if they are possible. */ 3236 if (!node_has_high_bound (node, index_type)) 3237 { 3238 emit_cmp_and_jump_insns (index, 3239 convert_modes 3240 (mode, imode, 3241 expand_normal (node->high), 3242 unsignedp), 3243 GT, NULL_RTX, mode, unsignedp, 3244 default_label); 3245 } 3246 3247 /* Value belongs to this node or to the left-hand subtree. */ 3248 3249 emit_cmp_and_jump_insns (index, 3250 convert_modes 3251 (mode, imode, 3252 expand_normal (node->low), 3253 unsignedp), 3254 GE, NULL_RTX, mode, unsignedp, 3255 label_rtx (node->code_label)); 3256 3257 emit_case_nodes (index, node->left, default_label, index_type); 3258 } 3259 3260 else 3261 { 3262 /* Node has no children so we check low and high bounds to remove 3263 redundant tests. Only one of the bounds can exist, 3264 since otherwise this node is bounded--a case tested already. */ 3265 int high_bound = node_has_high_bound (node, index_type); 3266 int low_bound = node_has_low_bound (node, index_type); 3267 3268 if (!high_bound && low_bound) 3269 { 3270 emit_cmp_and_jump_insns (index, 3271 convert_modes 3272 (mode, imode, 3273 expand_normal (node->high), 3274 unsignedp), 3275 GT, NULL_RTX, mode, unsignedp, 3276 default_label); 3277 } 3278 3279 else if (!low_bound && high_bound) 3280 { 3281 emit_cmp_and_jump_insns (index, 3282 convert_modes 3283 (mode, imode, 3284 expand_normal (node->low), 3285 unsignedp), 3286 LT, NULL_RTX, mode, unsignedp, 3287 default_label); 3288 } 3289 else if (!low_bound && !high_bound) 3290 { 3291 /* Widen LOW and HIGH to the same width as INDEX. */ 3292 tree type = lang_hooks.types.type_for_mode (mode, unsignedp); 3293 tree low = build1 (CONVERT_EXPR, type, node->low); 3294 tree high = build1 (CONVERT_EXPR, type, node->high); 3295 rtx low_rtx, new_index, new_bound; 3296 3297 /* Instead of doing two branches, emit one unsigned branch for 3298 (index-low) > (high-low). */ 3299 low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL); 3300 new_index = expand_simple_binop (mode, MINUS, index, low_rtx, 3301 NULL_RTX, unsignedp, 3302 OPTAB_WIDEN); 3303 new_bound = expand_expr (fold_build2 (MINUS_EXPR, type, 3304 high, low), 3305 NULL_RTX, mode, EXPAND_NORMAL); 3306 3307 emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX, 3308 mode, 1, default_label); 3309 } 3310 3311 emit_jump (label_rtx (node->code_label)); 3312 } 3313 } 3314} 3315