1132718Skan/* Expands front end tree to back end RTL for GCC 290075Sobrien Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 3169689Skan 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 4169689Skan Free Software Foundation, Inc. 518334Speter 690075SobrienThis file is part of GCC. 718334Speter 890075SobrienGCC is free software; you can redistribute it and/or modify it under 990075Sobrienthe terms of the GNU General Public License as published by the Free 1090075SobrienSoftware Foundation; either version 2, or (at your option) any later 1190075Sobrienversion. 1218334Speter 1390075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1490075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1590075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1690075Sobrienfor more details. 1718334Speter 1818334SpeterYou should have received a copy of the GNU General Public License 1990075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 20169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 21169689Skan02110-1301, USA. */ 2218334Speter 2318334Speter/* This file handles the generation of rtl code from tree structure 2418334Speter above the level of expressions, using subroutines in exp*.c and emit-rtl.c. 2518334Speter The functions whose names start with `expand_' are called by the 26169689Skan expander to generate RTL instructions for various kinds of constructs. */ 2718334Speter 2818334Speter#include "config.h" 2950397Sobrien#include "system.h" 30132718Skan#include "coretypes.h" 31132718Skan#include "tm.h" 3218334Speter 3318334Speter#include "rtl.h" 34169689Skan#include "hard-reg-set.h" 3518334Speter#include "tree.h" 3690075Sobrien#include "tm_p.h" 3718334Speter#include "flags.h" 3850397Sobrien#include "except.h" 3918334Speter#include "function.h" 4018334Speter#include "insn-config.h" 4118334Speter#include "expr.h" 4290075Sobrien#include "libfuncs.h" 4318334Speter#include "recog.h" 4418334Speter#include "machmode.h" 4550397Sobrien#include "toplev.h" 4650397Sobrien#include "output.h" 4790075Sobrien#include "ggc.h" 48117395Skan#include "langhooks.h" 49117395Skan#include "predict.h" 50132718Skan#include "optabs.h" 51132718Skan#include "target.h" 52169689Skan#include "regs.h" 5318334Speter 5418334Speter/* Functions and data structures for expanding case statements. */ 5518334Speter 5618334Speter/* Case label structure, used to hold info on labels within case 5718334Speter statements. We handle "range" labels; for a single-value label 5818334Speter as in C, the high and low limits are the same. 5918334Speter 60169689Skan We start with a vector of case nodes sorted in ascending order, and 61169689Skan the default label as the last element in the vector. Before expanding 62169689Skan to RTL, we transform this vector into a list linked via the RIGHT 63169689Skan fields in the case_node struct. Nodes with higher case values are 64169689Skan later in the list. 6518334Speter 66169689Skan Switch statements can be output in three forms. A branch table is 67169689Skan used if there are more than a few labels and the labels are dense 6818334Speter within the range between the smallest and largest case value. If a 6918334Speter branch table is used, no further manipulations are done with the case 7018334Speter node chain. 7118334Speter 7218334Speter The alternative to the use of a branch table is to generate a series 7318334Speter of compare and jump insns. When that is done, we use the LEFT, RIGHT, 7418334Speter and PARENT fields to hold a binary tree. Initially the tree is 7518334Speter totally unbalanced, with everything on the right. We balance the tree 7618334Speter with nodes on the left having lower case values than the parent 7718334Speter and nodes on the right having higher values. We then output the tree 78169689Skan in order. 7918334Speter 80169689Skan For very small, suitable switch statements, we can generate a series 81169689Skan of simple bit test and branches instead. */ 82169689Skan 83117395Skanstruct case_node GTY(()) 8418334Speter{ 8518334Speter struct case_node *left; /* Left son in binary tree */ 8618334Speter struct case_node *right; /* Right son in binary tree; also node chain */ 8718334Speter struct case_node *parent; /* Parent of node in binary tree */ 8818334Speter tree low; /* Lowest index value for this label */ 8918334Speter tree high; /* Highest index value for this label */ 9018334Speter tree code_label; /* Label to jump to when node matches */ 9118334Speter}; 9218334Speter 9318334Spetertypedef struct case_node case_node; 9418334Spetertypedef struct case_node *case_node_ptr; 9518334Speter 9618334Speter/* These are used by estimate_case_costs and balance_case_nodes. */ 9718334Speter 9818334Speter/* This must be a signed type, and non-ANSI compilers lack signed char. */ 9990075Sobrienstatic short cost_table_[129]; 10018334Speterstatic int use_cost_table; 10190075Sobrienstatic int cost_table_initialized; 10290075Sobrien 10390075Sobrien/* Special care is needed because we allow -1, but TREE_INT_CST_LOW 10490075Sobrien is unsigned. */ 10590075Sobrien#define COST_TABLE(I) cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)] 10618334Speter 107132718Skanstatic int n_occurrences (int, const char *); 108169689Skanstatic bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *); 109132718Skanstatic void expand_nl_goto_receiver (void); 110132718Skanstatic bool check_operand_nalternatives (tree, tree); 111132718Skanstatic bool check_unique_operand_names (tree, tree); 112132718Skanstatic char *resolve_operand_name_1 (char *, tree, tree); 113169689Skanstatic void expand_null_return_1 (void); 114132718Skanstatic void expand_value_return (rtx); 115132718Skanstatic int estimate_case_costs (case_node_ptr); 116132718Skanstatic bool lshift_cheap_p (void); 117132718Skanstatic int case_bit_test_cmp (const void *, const void *); 118132718Skanstatic void emit_case_bit_tests (tree, tree, tree, tree, case_node_ptr, rtx); 119132718Skanstatic void balance_case_nodes (case_node_ptr *, case_node_ptr); 120132718Skanstatic int node_has_low_bound (case_node_ptr, tree); 121132718Skanstatic int node_has_high_bound (case_node_ptr, tree); 122132718Skanstatic int node_is_bounded (case_node_ptr, tree); 123132718Skanstatic void emit_case_nodes (rtx, case_node_ptr, rtx, tree); 124169689Skanstatic struct case_node *add_case_node (struct case_node *, tree, 125169689Skan tree, tree, tree); 12650397Sobrien 12790075Sobrien 12818334Speter/* Return the rtx-label that corresponds to a LABEL_DECL, 12918334Speter creating it if necessary. */ 13018334Speter 13118334Speterrtx 132132718Skanlabel_rtx (tree label) 13318334Speter{ 134169689Skan gcc_assert (TREE_CODE (label) == LABEL_DECL); 13518334Speter 13690075Sobrien if (!DECL_RTL_SET_P (label)) 137169689Skan { 138169689Skan rtx r = gen_label_rtx (); 139260918Spfg/* APPLE LOCAL begin for-fsf-4_4 3274130 5295549 */ \ 140260918Spfg unsigned align = DECL_ALIGN_UNIT (label); 141260918Spfg int align_log2 = exact_log2 (align); 142260918Spfg 143260918Spfg/* APPLE LOCAL end for-fsf-4_4 3274130 5295549 */ \ 144169689Skan SET_DECL_RTL (label, r); 145169689Skan if (FORCED_LABEL (label) || DECL_NONLOCAL (label)) 146169689Skan LABEL_PRESERVE_P (r) = 1; 147260918Spfg/* APPLE LOCAL begin for-fsf-4_4 3274130 5295549 */ \ 148260918Spfg 149260918Spfg if (align_log2 >= 0 && align_log2 <= 0xFF) 150260918Spfg SET_LABEL_ALIGN (r, align_log2, align - 1); 151260918Spfg/* APPLE LOCAL end for-fsf-4_4 3274130 5295549 */ \ 152169689Skan } 15318334Speter 15490075Sobrien return DECL_RTL (label); 15518334Speter} 15618334Speter 157132718Skan/* As above, but also put it on the forced-reference list of the 158132718Skan function that contains it. */ 159132718Skanrtx 160132718Skanforce_label_rtx (tree label) 161132718Skan{ 162132718Skan rtx ref = label_rtx (label); 163132718Skan tree function = decl_function_context (label); 164132718Skan struct function *p; 16590075Sobrien 166169689Skan gcc_assert (function); 167132718Skan 168169689Skan if (function != current_function_decl) 169132718Skan p = find_function_data (function); 170132718Skan else 171132718Skan p = cfun; 172132718Skan 173132718Skan p->expr->x_forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref, 174132718Skan p->expr->x_forced_labels); 175132718Skan return ref; 176132718Skan} 177132718Skan 17818334Speter/* Add an unconditional jump to LABEL as the next sequential instruction. */ 17918334Speter 18018334Spetervoid 181132718Skanemit_jump (rtx label) 18218334Speter{ 18318334Speter do_pending_stack_adjust (); 18418334Speter emit_jump_insn (gen_jump (label)); 18518334Speter emit_barrier (); 18618334Speter} 18718334Speter 18818334Speter/* Emit code to jump to the address 18918334Speter specified by the pointer expression EXP. */ 19018334Speter 19118334Spetervoid 192132718Skanexpand_computed_goto (tree exp) 19318334Speter{ 194169689Skan rtx x = expand_normal (exp); 19518334Speter 196132718Skan x = convert_memory_address (Pmode, x); 19718334Speter 198169689Skan do_pending_stack_adjust (); 199169689Skan emit_indirect_jump (x); 20018334Speter} 20118334Speter 20218334Speter/* Handle goto statements and the labels that they can go to. */ 20318334Speter 20418334Speter/* Specify the location in the RTL code of a label LABEL, 20518334Speter which is a LABEL_DECL tree node. 20618334Speter 207260918Spfg APPLE LOCAL begin for-fsf-4_4 3274130 5295549 208260918Spfg This is used for those labels created by the front-end that survive 209260918Spfg through CFG generation, including all user labels. (Some labels 210260918Spfg are removed by cleanup_dead_labels in tree-cfg.c.) 21118334Speter 212260918Spfg APPLE LOCAL end for-fsf-4_4 3274130 5295549 21318334Speter Note that this has nothing to do with defining label *names*. 21418334Speter Languages vary in how they do that and what that even means. */ 21518334Speter 21618334Spetervoid 217132718Skanexpand_label (tree label) 21818334Speter{ 219169689Skan rtx label_r = label_rtx (label); 22018334Speter 22118334Speter do_pending_stack_adjust (); 222169689Skan emit_label (label_r); 22318334Speter if (DECL_NAME (label)) 22418334Speter LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label)); 22518334Speter 226169689Skan if (DECL_NONLOCAL (label)) 22718334Speter { 228169689Skan expand_nl_goto_receiver (); 229169689Skan nonlocal_goto_handler_labels 230169689Skan = gen_rtx_EXPR_LIST (VOIDmode, label_r, 231169689Skan nonlocal_goto_handler_labels); 23218334Speter } 23318334Speter 234169689Skan if (FORCED_LABEL (label)) 235169689Skan forced_labels = gen_rtx_EXPR_LIST (VOIDmode, label_r, forced_labels); 23618334Speter 237169689Skan if (DECL_NONLOCAL (label) || FORCED_LABEL (label)) 238169689Skan maybe_set_first_label_num (label_r); 23918334Speter} 24018334Speter 24118334Speter/* Generate RTL code for a `goto' statement with target label LABEL. 24218334Speter LABEL should be a LABEL_DECL tree node that was or will later be 24318334Speter defined with `expand_label'. */ 24418334Speter 24518334Spetervoid 246132718Skanexpand_goto (tree label) 24718334Speter{ 248169689Skan#ifdef ENABLE_CHECKING 249169689Skan /* Check for a nonlocal goto to a containing function. Should have 250169689Skan gotten translated to __builtin_nonlocal_goto. */ 251169689Skan tree context = decl_function_context (label); 252169689Skan gcc_assert (!context || context == current_function_decl); 25318334Speter#endif 254132718Skan 255169689Skan emit_jump (label_rtx (label)); 25618334Speter} 25718334Speter 25852284Sobrien/* Return the number of times character C occurs in string S. */ 25952284Sobrienstatic int 260132718Skann_occurrences (int c, const char *s) 26152284Sobrien{ 26252284Sobrien int n = 0; 26352284Sobrien while (*s) 26452284Sobrien n += (*s++ == c); 26552284Sobrien return n; 26652284Sobrien} 26752284Sobrien 26818334Speter/* Generate RTL for an asm statement (explicit assembler code). 269110611Skan STRING is a STRING_CST node containing the assembler code text, 270110611Skan or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the 271110611Skan insn is volatile; don't optimize it. */ 272117395Skan 273169689Skanstatic void 274132718Skanexpand_asm (tree string, int vol) 27518334Speter{ 276110611Skan rtx body; 27718334Speter 278110611Skan if (TREE_CODE (string) == ADDR_EXPR) 279110611Skan string = TREE_OPERAND (string, 0); 280110611Skan 281169689Skan body = gen_rtx_ASM_INPUT (VOIDmode, 282169689Skan ggc_strdup (TREE_STRING_POINTER (string))); 283110611Skan 284110611Skan MEM_VOLATILE_P (body) = vol; 285110611Skan 286110611Skan emit_insn (body); 28718334Speter} 28818334Speter 28990075Sobrien/* Parse the output constraint pointed to by *CONSTRAINT_P. It is the 29090075Sobrien OPERAND_NUMth output operand, indexed from zero. There are NINPUTS 29190075Sobrien inputs and NOUTPUTS outputs to this extended-asm. Upon return, 29290075Sobrien *ALLOWS_MEM will be TRUE iff the constraint allows the use of a 29390075Sobrien memory operand. Similarly, *ALLOWS_REG will be TRUE iff the 29490075Sobrien constraint allows the use of a register operand. And, *IS_INOUT 29590075Sobrien will be true if the operand is read-write, i.e., if it is used as 29690075Sobrien an input as well as an output. If *CONSTRAINT_P is not in 29790075Sobrien canonical form, it will be made canonical. (Note that `+' will be 298132718Skan replaced with `=' as part of this process.) 29990075Sobrien 30090075Sobrien Returns TRUE if all went well; FALSE if an error occurred. */ 30190075Sobrien 30290075Sobrienbool 303132718Skanparse_output_constraint (const char **constraint_p, int operand_num, 304132718Skan int ninputs, int noutputs, bool *allows_mem, 305132718Skan bool *allows_reg, bool *is_inout) 30690075Sobrien{ 30790075Sobrien const char *constraint = *constraint_p; 30890075Sobrien const char *p; 30990075Sobrien 31090075Sobrien /* Assume the constraint doesn't allow the use of either a register 31190075Sobrien or memory. */ 31290075Sobrien *allows_mem = false; 31390075Sobrien *allows_reg = false; 31490075Sobrien 31590075Sobrien /* Allow the `=' or `+' to not be at the beginning of the string, 31690075Sobrien since it wasn't explicitly documented that way, and there is a 31790075Sobrien large body of code that puts it last. Swap the character to 31890075Sobrien the front, so as not to uglify any place else. */ 31990075Sobrien p = strchr (constraint, '='); 32090075Sobrien if (!p) 32190075Sobrien p = strchr (constraint, '+'); 32290075Sobrien 32390075Sobrien /* If the string doesn't contain an `=', issue an error 32490075Sobrien message. */ 32590075Sobrien if (!p) 32690075Sobrien { 327169689Skan error ("output operand constraint lacks %<=%>"); 32890075Sobrien return false; 32990075Sobrien } 33090075Sobrien 33190075Sobrien /* If the constraint begins with `+', then the operand is both read 33290075Sobrien from and written to. */ 33390075Sobrien *is_inout = (*p == '+'); 33490075Sobrien 33590075Sobrien /* Canonicalize the output constraint so that it begins with `='. */ 336169689Skan if (p != constraint || *is_inout) 33790075Sobrien { 33890075Sobrien char *buf; 33990075Sobrien size_t c_len = strlen (constraint); 34090075Sobrien 34190075Sobrien if (p != constraint) 342169689Skan warning (0, "output constraint %qc for operand %d " 343169689Skan "is not at the beginning", 34490075Sobrien *p, operand_num); 34590075Sobrien 34690075Sobrien /* Make a copy of the constraint. */ 34790075Sobrien buf = alloca (c_len + 1); 34890075Sobrien strcpy (buf, constraint); 34990075Sobrien /* Swap the first character and the `=' or `+'. */ 35090075Sobrien buf[p - constraint] = buf[0]; 35190075Sobrien /* Make sure the first character is an `='. (Until we do this, 35290075Sobrien it might be a `+'.) */ 35390075Sobrien buf[0] = '='; 35490075Sobrien /* Replace the constraint with the canonicalized string. */ 35590075Sobrien *constraint_p = ggc_alloc_string (buf, c_len); 35690075Sobrien constraint = *constraint_p; 35790075Sobrien } 35890075Sobrien 35990075Sobrien /* Loop through the constraint string. */ 360132718Skan for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p)) 36190075Sobrien switch (*p) 36290075Sobrien { 36390075Sobrien case '+': 36490075Sobrien case '=': 365169689Skan error ("operand constraint contains incorrectly positioned " 366169689Skan "%<+%> or %<=%>"); 36790075Sobrien return false; 368117395Skan 36990075Sobrien case '%': 37090075Sobrien if (operand_num + 1 == ninputs + noutputs) 37190075Sobrien { 372169689Skan error ("%<%%%> constraint used with last operand"); 37390075Sobrien return false; 37490075Sobrien } 37590075Sobrien break; 37690075Sobrien 37790075Sobrien case 'V': case 'm': case 'o': 37890075Sobrien *allows_mem = true; 37990075Sobrien break; 38090075Sobrien 38190075Sobrien case '?': case '!': case '*': case '&': case '#': 38290075Sobrien case 'E': case 'F': case 'G': case 'H': 38390075Sobrien case 's': case 'i': case 'n': 38490075Sobrien case 'I': case 'J': case 'K': case 'L': case 'M': 38590075Sobrien case 'N': case 'O': case 'P': case ',': 38690075Sobrien break; 38790075Sobrien 38890075Sobrien case '0': case '1': case '2': case '3': case '4': 38990075Sobrien case '5': case '6': case '7': case '8': case '9': 39090075Sobrien case '[': 39190075Sobrien error ("matching constraint not valid in output operand"); 39290075Sobrien return false; 39390075Sobrien 39490075Sobrien case '<': case '>': 39590075Sobrien /* ??? Before flow, auto inc/dec insns are not supposed to exist, 39690075Sobrien excepting those that expand_call created. So match memory 39790075Sobrien and hope. */ 39890075Sobrien *allows_mem = true; 39990075Sobrien break; 40090075Sobrien 40190075Sobrien case 'g': case 'X': 40290075Sobrien *allows_reg = true; 40390075Sobrien *allows_mem = true; 40490075Sobrien break; 405117395Skan 40690075Sobrien case 'p': case 'r': 40790075Sobrien *allows_reg = true; 40890075Sobrien break; 40990075Sobrien 41090075Sobrien default: 41190075Sobrien if (!ISALPHA (*p)) 41290075Sobrien break; 413132718Skan if (REG_CLASS_FROM_CONSTRAINT (*p, p) != NO_REGS) 41490075Sobrien *allows_reg = true; 415132718Skan#ifdef EXTRA_CONSTRAINT_STR 416132718Skan else if (EXTRA_ADDRESS_CONSTRAINT (*p, p)) 417117395Skan *allows_reg = true; 418132718Skan else if (EXTRA_MEMORY_CONSTRAINT (*p, p)) 419117395Skan *allows_mem = true; 42090075Sobrien else 42190075Sobrien { 42290075Sobrien /* Otherwise we can't assume anything about the nature of 42390075Sobrien the constraint except that it isn't purely registers. 42490075Sobrien Treat it like "g" and hope for the best. */ 42590075Sobrien *allows_reg = true; 42690075Sobrien *allows_mem = true; 42790075Sobrien } 42890075Sobrien#endif 42990075Sobrien break; 43090075Sobrien } 43190075Sobrien 43290075Sobrien return true; 43390075Sobrien} 43490075Sobrien 43590075Sobrien/* Similar, but for input constraints. */ 43690075Sobrien 437132718Skanbool 438132718Skanparse_input_constraint (const char **constraint_p, int input_num, 439132718Skan int ninputs, int noutputs, int ninout, 440132718Skan const char * const * constraints, 441132718Skan bool *allows_mem, bool *allows_reg) 44290075Sobrien{ 44390075Sobrien const char *constraint = *constraint_p; 44490075Sobrien const char *orig_constraint = constraint; 44590075Sobrien size_t c_len = strlen (constraint); 44690075Sobrien size_t j; 447132718Skan bool saw_match = false; 44890075Sobrien 44990075Sobrien /* Assume the constraint doesn't allow the use of either 45090075Sobrien a register or memory. */ 45190075Sobrien *allows_mem = false; 45290075Sobrien *allows_reg = false; 45390075Sobrien 45490075Sobrien /* Make sure constraint has neither `=', `+', nor '&'. */ 45590075Sobrien 456132718Skan for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j)) 45790075Sobrien switch (constraint[j]) 45890075Sobrien { 45990075Sobrien case '+': case '=': case '&': 46090075Sobrien if (constraint == orig_constraint) 46190075Sobrien { 462169689Skan error ("input operand constraint contains %qc", constraint[j]); 46390075Sobrien return false; 46490075Sobrien } 46590075Sobrien break; 46690075Sobrien 46790075Sobrien case '%': 46890075Sobrien if (constraint == orig_constraint 46990075Sobrien && input_num + 1 == ninputs - ninout) 47090075Sobrien { 471169689Skan error ("%<%%%> constraint used with last operand"); 47290075Sobrien return false; 47390075Sobrien } 47490075Sobrien break; 47590075Sobrien 47690075Sobrien case 'V': case 'm': case 'o': 47790075Sobrien *allows_mem = true; 47890075Sobrien break; 47990075Sobrien 48090075Sobrien case '<': case '>': 48190075Sobrien case '?': case '!': case '*': case '#': 48290075Sobrien case 'E': case 'F': case 'G': case 'H': 48390075Sobrien case 's': case 'i': case 'n': 48490075Sobrien case 'I': case 'J': case 'K': case 'L': case 'M': 48590075Sobrien case 'N': case 'O': case 'P': case ',': 48690075Sobrien break; 48790075Sobrien 48890075Sobrien /* Whether or not a numeric constraint allows a register is 48990075Sobrien decided by the matching constraint, and so there is no need 49090075Sobrien to do anything special with them. We must handle them in 49190075Sobrien the default case, so that we don't unnecessarily force 49290075Sobrien operands to memory. */ 49390075Sobrien case '0': case '1': case '2': case '3': case '4': 49490075Sobrien case '5': case '6': case '7': case '8': case '9': 49590075Sobrien { 49690075Sobrien char *end; 49790075Sobrien unsigned long match; 49890075Sobrien 499132718Skan saw_match = true; 500132718Skan 50190075Sobrien match = strtoul (constraint + j, &end, 10); 50290075Sobrien if (match >= (unsigned long) noutputs) 50390075Sobrien { 50490075Sobrien error ("matching constraint references invalid operand number"); 50590075Sobrien return false; 50690075Sobrien } 50790075Sobrien 50890075Sobrien /* Try and find the real constraint for this dup. Only do this 50990075Sobrien if the matching constraint is the only alternative. */ 51090075Sobrien if (*end == '\0' 51190075Sobrien && (j == 0 || (j == 1 && constraint[0] == '%'))) 51290075Sobrien { 51390075Sobrien constraint = constraints[match]; 51490075Sobrien *constraint_p = constraint; 51590075Sobrien c_len = strlen (constraint); 51690075Sobrien j = 0; 517132718Skan /* ??? At the end of the loop, we will skip the first part of 518132718Skan the matched constraint. This assumes not only that the 519132718Skan other constraint is an output constraint, but also that 520132718Skan the '=' or '+' come first. */ 52190075Sobrien break; 52290075Sobrien } 52390075Sobrien else 52490075Sobrien j = end - constraint; 525132718Skan /* Anticipate increment at end of loop. */ 526132718Skan j--; 52790075Sobrien } 52890075Sobrien /* Fall through. */ 52990075Sobrien 53090075Sobrien case 'p': case 'r': 53190075Sobrien *allows_reg = true; 53290075Sobrien break; 53390075Sobrien 53490075Sobrien case 'g': case 'X': 53590075Sobrien *allows_reg = true; 53690075Sobrien *allows_mem = true; 53790075Sobrien break; 53890075Sobrien 53990075Sobrien default: 54090075Sobrien if (! ISALPHA (constraint[j])) 54190075Sobrien { 542169689Skan error ("invalid punctuation %qc in constraint", constraint[j]); 54390075Sobrien return false; 54490075Sobrien } 545132718Skan if (REG_CLASS_FROM_CONSTRAINT (constraint[j], constraint + j) 546132718Skan != NO_REGS) 54790075Sobrien *allows_reg = true; 548132718Skan#ifdef EXTRA_CONSTRAINT_STR 549132718Skan else if (EXTRA_ADDRESS_CONSTRAINT (constraint[j], constraint + j)) 550117395Skan *allows_reg = true; 551132718Skan else if (EXTRA_MEMORY_CONSTRAINT (constraint[j], constraint + j)) 552117395Skan *allows_mem = true; 55390075Sobrien else 55490075Sobrien { 55590075Sobrien /* Otherwise we can't assume anything about the nature of 55690075Sobrien the constraint except that it isn't purely registers. 55790075Sobrien Treat it like "g" and hope for the best. */ 55890075Sobrien *allows_reg = true; 55990075Sobrien *allows_mem = true; 56090075Sobrien } 56190075Sobrien#endif 56290075Sobrien break; 56390075Sobrien } 56490075Sobrien 565132718Skan if (saw_match && !*allows_reg) 566169689Skan warning (0, "matching constraint does not allow a register"); 567132718Skan 56890075Sobrien return true; 56990075Sobrien} 57090075Sobrien 571169689Skan/* Return DECL iff there's an overlap between *REGS and DECL, where DECL 572169689Skan can be an asm-declared register. Called via walk_tree. */ 573169689Skan 574169689Skanstatic tree 575169689Skandecl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED, 576169689Skan void *data) 577169689Skan{ 578169689Skan tree decl = *declp; 579169689Skan const HARD_REG_SET *regs = data; 580169689Skan 581169689Skan if (TREE_CODE (decl) == VAR_DECL) 582169689Skan { 583169689Skan if (DECL_HARD_REGISTER (decl) 584169689Skan && REG_P (DECL_RTL (decl)) 585169689Skan && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER) 586169689Skan { 587169689Skan rtx reg = DECL_RTL (decl); 588169689Skan unsigned int regno; 589169689Skan 590169689Skan for (regno = REGNO (reg); 591169689Skan regno < (REGNO (reg) 592169689Skan + hard_regno_nregs[REGNO (reg)][GET_MODE (reg)]); 593169689Skan regno++) 594169689Skan if (TEST_HARD_REG_BIT (*regs, regno)) 595169689Skan return decl; 596169689Skan } 597169689Skan walk_subtrees = 0; 598169689Skan } 599169689Skan else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL) 600169689Skan walk_subtrees = 0; 601169689Skan return NULL_TREE; 602169689Skan} 603169689Skan 604169689Skan/* If there is an overlap between *REGS and DECL, return the first overlap 605169689Skan found. */ 606169689Skantree 607169689Skantree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs) 608169689Skan{ 609169689Skan return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL); 610169689Skan} 611169689Skan 612117395Skan/* Check for overlap between registers marked in CLOBBERED_REGS and 613169689Skan anything inappropriate in T. Emit error and return the register 614169689Skan variable definition for error, NULL_TREE for ok. */ 615117395Skan 616117395Skanstatic bool 617169689Skantree_conflicts_with_clobbers_p (tree t, HARD_REG_SET *clobbered_regs) 618117395Skan{ 619117395Skan /* Conflicts between asm-declared register variables and the clobber 620117395Skan list are not allowed. */ 621169689Skan tree overlap = tree_overlaps_hard_reg_set (t, clobbered_regs); 622169689Skan 623169689Skan if (overlap) 624117395Skan { 625169689Skan error ("asm-specifier for variable %qs conflicts with asm clobber list", 626169689Skan IDENTIFIER_POINTER (DECL_NAME (overlap))); 627117395Skan 628169689Skan /* Reset registerness to stop multiple errors emitted for a single 629169689Skan variable. */ 630169689Skan DECL_REGISTER (overlap) = 0; 631169689Skan return true; 632169689Skan } 633117395Skan 634117395Skan return false; 635117395Skan} 636117395Skan 63718334Speter/* Generate RTL for an asm statement with arguments. 63818334Speter STRING is the instruction template. 63918334Speter OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs. 64018334Speter Each output or input has an expression in the TREE_VALUE and 64190075Sobrien and a tree list in TREE_PURPOSE which in turn contains a constraint 642117395Skan name in TREE_VALUE (or NULL_TREE) and a constraint string 64390075Sobrien in TREE_PURPOSE. 64418334Speter CLOBBERS is a list of STRING_CST nodes each naming a hard register 64518334Speter that is clobbered by this insn. 64618334Speter 64718334Speter Not all kinds of lvalue that may appear in OUTPUTS can be stored directly. 64818334Speter Some elements of OUTPUTS may be replaced with trees representing temporary 64918334Speter values. The caller should copy those temporary values to the originally 65018334Speter specified lvalues. 65118334Speter 65218334Speter VOL nonzero means the insn is volatile; don't optimize it. */ 65318334Speter 654169689Skanstatic void 655132718Skanexpand_asm_operands (tree string, tree outputs, tree inputs, 656132718Skan tree clobbers, int vol, location_t locus) 65718334Speter{ 65890075Sobrien rtvec argvec, constraintvec; 65918334Speter rtx body; 66018334Speter int ninputs = list_length (inputs); 66118334Speter int noutputs = list_length (outputs); 66290075Sobrien int ninout; 66318334Speter int nclobbers; 664117395Skan HARD_REG_SET clobbered_regs; 665117395Skan int clobber_conflict_found = 0; 66618334Speter tree tail; 667132718Skan tree t; 66890075Sobrien int i; 66918334Speter /* Vector of RTX's of evaluated output operands. */ 670132718Skan rtx *output_rtx = alloca (noutputs * sizeof (rtx)); 671132718Skan int *inout_opnum = alloca (noutputs * sizeof (int)); 672132718Skan rtx *real_output_rtx = alloca (noutputs * sizeof (rtx)); 67350397Sobrien enum machine_mode *inout_mode 674132718Skan = alloca (noutputs * sizeof (enum machine_mode)); 67590075Sobrien const char **constraints 676132718Skan = alloca ((noutputs + ninputs) * sizeof (const char *)); 67790075Sobrien int old_generating_concat_p = generating_concat_p; 67818334Speter 67950397Sobrien /* An ASM with no outputs needs to be treated as volatile, for now. */ 68050397Sobrien if (noutputs == 0) 68150397Sobrien vol = 1; 68250397Sobrien 68390075Sobrien if (! check_operand_nalternatives (outputs, inputs)) 68490075Sobrien return; 68518334Speter 686132718Skan string = resolve_asm_operand_names (string, outputs, inputs); 68790075Sobrien 688132718Skan /* Collect constraints. */ 689132718Skan i = 0; 690132718Skan for (t = outputs; t ; t = TREE_CHAIN (t), i++) 691132718Skan constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t))); 692132718Skan for (t = inputs; t ; t = TREE_CHAIN (t), i++) 693132718Skan constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t))); 69490075Sobrien 69590075Sobrien /* Sometimes we wish to automatically clobber registers across an asm. 69690075Sobrien Case in point is when the i386 backend moved from cc0 to a hard reg -- 69790075Sobrien maintaining source-level compatibility means automatically clobbering 69890075Sobrien the flags register. */ 699169689Skan clobbers = targetm.md_asm_clobbers (outputs, inputs, clobbers); 70090075Sobrien 70118334Speter /* Count the number of meaningful clobbered registers, ignoring what 70218334Speter we would ignore later. */ 70318334Speter nclobbers = 0; 704117395Skan CLEAR_HARD_REG_SET (clobbered_regs); 70518334Speter for (tail = clobbers; tail; tail = TREE_CHAIN (tail)) 70618334Speter { 707169689Skan const char *regname; 70890075Sobrien 709169689Skan if (TREE_VALUE (tail) == error_mark_node) 710169689Skan return; 711169689Skan regname = TREE_STRING_POINTER (TREE_VALUE (tail)); 712169689Skan 71318334Speter i = decode_reg_name (regname); 71418334Speter if (i >= 0 || i == -4) 71518334Speter ++nclobbers; 71618334Speter else if (i == -2) 717169689Skan error ("unknown register name %qs in %<asm%>", regname); 718117395Skan 719117395Skan /* Mark clobbered registers. */ 720117395Skan if (i >= 0) 721132718Skan { 722169689Skan /* Clobbering the PIC register is an error. */ 723132718Skan if (i == (int) PIC_OFFSET_TABLE_REGNUM) 724132718Skan { 725169689Skan error ("PIC register %qs clobbered in %<asm%>", regname); 726132718Skan return; 727132718Skan } 728132718Skan 729132718Skan SET_HARD_REG_BIT (clobbered_regs, i); 730132718Skan } 73118334Speter } 73218334Speter 73390075Sobrien /* First pass over inputs and outputs checks validity and sets 73490075Sobrien mark_addressable if needed. */ 73552284Sobrien 73690075Sobrien ninout = 0; 73718334Speter for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 73818334Speter { 73918334Speter tree val = TREE_VALUE (tail); 74018334Speter tree type = TREE_TYPE (val); 74190075Sobrien const char *constraint; 74290075Sobrien bool is_inout; 74390075Sobrien bool allows_reg; 74490075Sobrien bool allows_mem; 74518334Speter 74618334Speter /* If there's an erroneous arg, emit no insn. */ 74790075Sobrien if (type == error_mark_node) 74818334Speter return; 74918334Speter 75090075Sobrien /* Try to parse the output constraint. If that fails, there's 75190075Sobrien no point in going further. */ 75290075Sobrien constraint = constraints[i]; 75390075Sobrien if (!parse_output_constraint (&constraint, i, ninputs, noutputs, 75490075Sobrien &allows_mem, &allows_reg, &is_inout)) 75590075Sobrien return; 75618334Speter 75790075Sobrien if (! allows_reg 75890075Sobrien && (allows_mem 75990075Sobrien || is_inout 76090075Sobrien || (DECL_P (val) 761169689Skan && REG_P (DECL_RTL (val)) 76290075Sobrien && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))) 763169689Skan lang_hooks.mark_addressable (val); 76452284Sobrien 76590075Sobrien if (is_inout) 76690075Sobrien ninout++; 76790075Sobrien } 76852284Sobrien 76990075Sobrien ninputs += ninout; 77090075Sobrien if (ninputs + noutputs > MAX_RECOG_OPERANDS) 77190075Sobrien { 772169689Skan error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS); 77390075Sobrien return; 77490075Sobrien } 77552284Sobrien 77690075Sobrien for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail)) 77790075Sobrien { 77890075Sobrien bool allows_reg, allows_mem; 77990075Sobrien const char *constraint; 78052284Sobrien 78190075Sobrien /* If there's an erroneous arg, emit no insn, because the ASM_INPUT 78290075Sobrien would get VOIDmode and that could cause a crash in reload. */ 78390075Sobrien if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node) 78490075Sobrien return; 78552284Sobrien 78690075Sobrien constraint = constraints[i + noutputs]; 78790075Sobrien if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout, 78890075Sobrien constraints, &allows_mem, &allows_reg)) 78990075Sobrien return; 79052284Sobrien 79190075Sobrien if (! allows_reg && allows_mem) 792169689Skan lang_hooks.mark_addressable (TREE_VALUE (tail)); 79390075Sobrien } 79450397Sobrien 79590075Sobrien /* Second pass evaluates arguments. */ 79618334Speter 79790075Sobrien ninout = 0; 79890075Sobrien for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 79990075Sobrien { 80090075Sobrien tree val = TREE_VALUE (tail); 80190075Sobrien tree type = TREE_TYPE (val); 80290075Sobrien bool is_inout; 80390075Sobrien bool allows_reg; 80490075Sobrien bool allows_mem; 805117395Skan rtx op; 806169689Skan bool ok; 80750397Sobrien 808169689Skan ok = parse_output_constraint (&constraints[i], i, ninputs, 80990075Sobrien noutputs, &allows_mem, &allows_reg, 810169689Skan &is_inout); 811169689Skan gcc_assert (ok); 81252284Sobrien 81318334Speter /* If an output operand is not a decl or indirect ref and our constraint 81418334Speter allows a register, make a temporary to act as an intermediate. 81518334Speter Make the asm insn write into that, then our caller will copy it to 81618334Speter the real output operand. Likewise for promoted variables. */ 81718334Speter 81890075Sobrien generating_concat_p = 0; 81990075Sobrien 82052284Sobrien real_output_rtx[i] = NULL_RTX; 82152284Sobrien if ((TREE_CODE (val) == INDIRECT_REF 82252284Sobrien && allows_mem) 82390075Sobrien || (DECL_P (val) 824169689Skan && (allows_mem || REG_P (DECL_RTL (val))) 825169689Skan && ! (REG_P (DECL_RTL (val)) 82618334Speter && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))) 82750397Sobrien || ! allows_reg 82852284Sobrien || is_inout) 82918334Speter { 830117395Skan op = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE); 831169689Skan if (MEM_P (op)) 832117395Skan op = validize_mem (op); 83318334Speter 834169689Skan if (! allows_reg && !MEM_P (op)) 83518334Speter error ("output number %d not directly addressable", i); 836169689Skan if ((! allows_mem && MEM_P (op)) 837117395Skan || GET_CODE (op) == CONCAT) 83852284Sobrien { 839169689Skan real_output_rtx[i] = op; 840117395Skan op = gen_reg_rtx (GET_MODE (op)); 84152284Sobrien if (is_inout) 842117395Skan emit_move_insn (op, real_output_rtx[i]); 84352284Sobrien } 84418334Speter } 84518334Speter else 84618334Speter { 847117395Skan op = assign_temp (type, 0, 0, 1); 848117395Skan op = validize_mem (op); 849117395Skan TREE_VALUE (tail) = make_tree (type, op); 85018334Speter } 851117395Skan output_rtx[i] = op; 85250397Sobrien 85390075Sobrien generating_concat_p = old_generating_concat_p; 85490075Sobrien 85552284Sobrien if (is_inout) 85650397Sobrien { 85790075Sobrien inout_mode[ninout] = TYPE_MODE (type); 85850397Sobrien inout_opnum[ninout++] = i; 85950397Sobrien } 860117395Skan 861169689Skan if (tree_conflicts_with_clobbers_p (val, &clobbered_regs)) 862117395Skan clobber_conflict_found = 1; 86318334Speter } 86418334Speter 86590075Sobrien /* Make vectors for the expression-rtx, constraint strings, 86690075Sobrien and named operands. */ 86718334Speter 86818334Speter argvec = rtvec_alloc (ninputs); 86990075Sobrien constraintvec = rtvec_alloc (ninputs); 87018334Speter 87190075Sobrien body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode 87290075Sobrien : GET_MODE (output_rtx[0])), 873169689Skan ggc_strdup (TREE_STRING_POINTER (string)), 87490075Sobrien empty_string, 0, argvec, constraintvec, 875169689Skan locus); 87650397Sobrien 87718334Speter MEM_VOLATILE_P (body) = vol; 87818334Speter 87918334Speter /* Eval the inputs and put them into ARGVEC. 88018334Speter Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */ 88118334Speter 88290075Sobrien for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i) 88318334Speter { 88490075Sobrien bool allows_reg, allows_mem; 88590075Sobrien const char *constraint; 88690075Sobrien tree val, type; 88752284Sobrien rtx op; 888169689Skan bool ok; 88918334Speter 89090075Sobrien constraint = constraints[i + noutputs]; 891169689Skan ok = parse_input_constraint (&constraint, i, ninputs, noutputs, ninout, 892169689Skan constraints, &allows_mem, &allows_reg); 893169689Skan gcc_assert (ok); 89452284Sobrien 89590075Sobrien generating_concat_p = 0; 89618334Speter 89790075Sobrien val = TREE_VALUE (tail); 89890075Sobrien type = TREE_TYPE (val); 899169689Skan /* EXPAND_INITIALIZER will not generate code for valid initializer 900169689Skan constants, but will still generate code for other types of operand. 901169689Skan This is the behavior we want for constant constraints. */ 902117395Skan op = expand_expr (val, NULL_RTX, VOIDmode, 903169689Skan allows_reg ? EXPAND_NORMAL 904169689Skan : allows_mem ? EXPAND_MEMORY 905169689Skan : EXPAND_INITIALIZER); 90618334Speter 90790075Sobrien /* Never pass a CONCAT to an ASM. */ 90890075Sobrien if (GET_CODE (op) == CONCAT) 90990075Sobrien op = force_reg (GET_MODE (op), op); 910169689Skan else if (MEM_P (op)) 911117395Skan op = validize_mem (op); 91252284Sobrien 91352284Sobrien if (asm_operand_ok (op, constraint) <= 0) 91418334Speter { 915169689Skan if (allows_reg && TYPE_MODE (type) != BLKmode) 91690075Sobrien op = force_reg (TYPE_MODE (type), op); 91752284Sobrien else if (!allows_mem) 918169689Skan warning (0, "asm operand %d probably doesn%'t match constraints", 91990075Sobrien i + noutputs); 920169689Skan else if (MEM_P (op)) 92152284Sobrien { 922117395Skan /* We won't recognize either volatile memory or memory 923117395Skan with a queued address as available a memory_operand 924117395Skan at this point. Ignore it: clearly this *is* a memory. */ 92552284Sobrien } 926117395Skan else 927117395Skan { 928169689Skan warning (0, "use of memory input without lvalue in " 929132718Skan "asm operand %d is deprecated", i + noutputs); 93090075Sobrien 931117395Skan if (CONSTANT_P (op)) 932117395Skan { 933132718Skan rtx mem = force_const_mem (TYPE_MODE (type), op); 934132718Skan if (mem) 935132718Skan op = validize_mem (mem); 936132718Skan else 937132718Skan op = force_reg (TYPE_MODE (type), op); 938117395Skan } 939169689Skan if (REG_P (op) 940132718Skan || GET_CODE (op) == SUBREG 941132718Skan || GET_CODE (op) == CONCAT) 942117395Skan { 943117395Skan tree qual_type = build_qualified_type (type, 944117395Skan (TYPE_QUALS (type) 945117395Skan | TYPE_QUAL_CONST)); 946117395Skan rtx memloc = assign_temp (qual_type, 1, 1, 1); 947117395Skan memloc = validize_mem (memloc); 948117395Skan emit_move_insn (memloc, op); 949117395Skan op = memloc; 950117395Skan } 95190075Sobrien } 95218334Speter } 95318334Speter 95490075Sobrien generating_concat_p = old_generating_concat_p; 95590075Sobrien ASM_OPERANDS_INPUT (body, i) = op; 95690075Sobrien 95790075Sobrien ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i) 958169689Skan = gen_rtx_ASM_INPUT (TYPE_MODE (type), 959169689Skan ggc_strdup (constraints[i + noutputs])); 960117395Skan 961169689Skan if (tree_conflicts_with_clobbers_p (val, &clobbered_regs)) 962117395Skan clobber_conflict_found = 1; 96318334Speter } 96418334Speter 96590075Sobrien /* Protect all the operands from the queue now that they have all been 96690075Sobrien evaluated. */ 96718334Speter 96890075Sobrien generating_concat_p = 0; 96990075Sobrien 97090075Sobrien /* For in-out operands, copy output rtx to input rtx. */ 97150397Sobrien for (i = 0; i < ninout; i++) 97250397Sobrien { 97350397Sobrien int j = inout_opnum[i]; 97490075Sobrien char buffer[16]; 97550397Sobrien 97690075Sobrien ASM_OPERANDS_INPUT (body, ninputs - ninout + i) 97750397Sobrien = output_rtx[j]; 97890075Sobrien 97990075Sobrien sprintf (buffer, "%d", j); 98090075Sobrien ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i) 981132718Skan = gen_rtx_ASM_INPUT (inout_mode[i], ggc_strdup (buffer)); 98250397Sobrien } 98350397Sobrien 98490075Sobrien generating_concat_p = old_generating_concat_p; 98590075Sobrien 98618334Speter /* Now, for each output, construct an rtx 98790075Sobrien (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER 98890075Sobrien ARGVEC CONSTRAINTS OPNAMES)) 98918334Speter If there is more than one, put them inside a PARALLEL. */ 99018334Speter 99118334Speter if (noutputs == 1 && nclobbers == 0) 99218334Speter { 993169689Skan ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = ggc_strdup (constraints[0]); 994132718Skan emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body)); 99518334Speter } 99690075Sobrien 99718334Speter else if (noutputs == 0 && nclobbers == 0) 99818334Speter { 99918334Speter /* No output operands: put in a raw ASM_OPERANDS rtx. */ 1000132718Skan emit_insn (body); 100118334Speter } 100290075Sobrien 100318334Speter else 100418334Speter { 100518334Speter rtx obody = body; 100618334Speter int num = noutputs; 100790075Sobrien 100890075Sobrien if (num == 0) 100990075Sobrien num = 1; 101090075Sobrien 101150397Sobrien body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers)); 101218334Speter 101318334Speter /* For each output operand, store a SET. */ 101418334Speter for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 101518334Speter { 101618334Speter XVECEXP (body, 0, i) 101750397Sobrien = gen_rtx_SET (VOIDmode, 101850397Sobrien output_rtx[i], 101990075Sobrien gen_rtx_ASM_OPERANDS 102090075Sobrien (GET_MODE (output_rtx[i]), 1021169689Skan ggc_strdup (TREE_STRING_POINTER (string)), 1022169689Skan ggc_strdup (constraints[i]), 1023169689Skan i, argvec, constraintvec, locus)); 102490075Sobrien 102518334Speter MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol; 102618334Speter } 102718334Speter 102818334Speter /* If there are no outputs (but there are some clobbers) 102918334Speter store the bare ASM_OPERANDS into the PARALLEL. */ 103018334Speter 103118334Speter if (i == 0) 103218334Speter XVECEXP (body, 0, i++) = obody; 103318334Speter 103418334Speter /* Store (clobber REG) for each clobbered register specified. */ 103518334Speter 103618334Speter for (tail = clobbers; tail; tail = TREE_CHAIN (tail)) 103718334Speter { 103890075Sobrien const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail)); 103918334Speter int j = decode_reg_name (regname); 1040117395Skan rtx clobbered_reg; 104118334Speter 104218334Speter if (j < 0) 104318334Speter { 104418334Speter if (j == -3) /* `cc', which is not a register */ 104518334Speter continue; 104618334Speter 104718334Speter if (j == -4) /* `memory', don't cache memory across asm */ 104818334Speter { 104918334Speter XVECEXP (body, 0, i++) 105050397Sobrien = gen_rtx_CLOBBER (VOIDmode, 105190075Sobrien gen_rtx_MEM 105290075Sobrien (BLKmode, 105390075Sobrien gen_rtx_SCRATCH (VOIDmode))); 105418334Speter continue; 105518334Speter } 105618334Speter 105750397Sobrien /* Ignore unknown register, error already signaled. */ 105818334Speter continue; 105918334Speter } 106018334Speter 106118334Speter /* Use QImode since that's guaranteed to clobber just one reg. */ 1062117395Skan clobbered_reg = gen_rtx_REG (QImode, j); 1063117395Skan 1064117395Skan /* Do sanity check for overlap between clobbers and respectively 1065117395Skan input and outputs that hasn't been handled. Such overlap 1066117395Skan should have been detected and reported above. */ 1067117395Skan if (!clobber_conflict_found) 1068117395Skan { 1069117395Skan int opno; 1070117395Skan 1071117395Skan /* We test the old body (obody) contents to avoid tripping 1072117395Skan over the under-construction body. */ 1073117395Skan for (opno = 0; opno < noutputs; opno++) 1074117395Skan if (reg_overlap_mentioned_p (clobbered_reg, output_rtx[opno])) 1075117395Skan internal_error ("asm clobber conflict with output operand"); 1076117395Skan 1077117395Skan for (opno = 0; opno < ninputs - ninout; opno++) 1078117395Skan if (reg_overlap_mentioned_p (clobbered_reg, 1079117395Skan ASM_OPERANDS_INPUT (obody, opno))) 1080117395Skan internal_error ("asm clobber conflict with input operand"); 1081117395Skan } 1082117395Skan 108318334Speter XVECEXP (body, 0, i++) 1084117395Skan = gen_rtx_CLOBBER (VOIDmode, clobbered_reg); 108518334Speter } 108618334Speter 1087132718Skan emit_insn (body); 108818334Speter } 108918334Speter 109052284Sobrien /* For any outputs that needed reloading into registers, spill them 109152284Sobrien back to where they belong. */ 109252284Sobrien for (i = 0; i < noutputs; ++i) 109352284Sobrien if (real_output_rtx[i]) 109452284Sobrien emit_move_insn (real_output_rtx[i], output_rtx[i]); 109552284Sobrien 109618334Speter free_temp_slots (); 109718334Speter} 109890075Sobrien 1099169689Skanvoid 1100169689Skanexpand_asm_expr (tree exp) 1101169689Skan{ 1102169689Skan int noutputs, i; 1103169689Skan tree outputs, tail; 1104169689Skan tree *o; 1105169689Skan 1106169689Skan if (ASM_INPUT_P (exp)) 1107169689Skan { 1108169689Skan expand_asm (ASM_STRING (exp), ASM_VOLATILE_P (exp)); 1109169689Skan return; 1110169689Skan } 1111169689Skan 1112169689Skan outputs = ASM_OUTPUTS (exp); 1113169689Skan noutputs = list_length (outputs); 1114169689Skan /* o[I] is the place that output number I should be written. */ 1115169689Skan o = (tree *) alloca (noutputs * sizeof (tree)); 1116169689Skan 1117169689Skan /* Record the contents of OUTPUTS before it is modified. */ 1118169689Skan for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 1119169689Skan o[i] = TREE_VALUE (tail); 1120169689Skan 1121169689Skan /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of 1122169689Skan OUTPUTS some trees for where the values were actually stored. */ 1123169689Skan expand_asm_operands (ASM_STRING (exp), outputs, ASM_INPUTS (exp), 1124169689Skan ASM_CLOBBERS (exp), ASM_VOLATILE_P (exp), 1125169689Skan input_location); 1126169689Skan 1127169689Skan /* Copy all the intermediate outputs into the specified outputs. */ 1128169689Skan for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 1129169689Skan { 1130169689Skan if (o[i] != TREE_VALUE (tail)) 1131169689Skan { 1132169689Skan expand_assignment (o[i], TREE_VALUE (tail)); 1133169689Skan free_temp_slots (); 1134169689Skan 1135169689Skan /* Restore the original value so that it's correct the next 1136169689Skan time we expand this function. */ 1137169689Skan TREE_VALUE (tail) = o[i]; 1138169689Skan } 1139169689Skan } 1140169689Skan} 1141169689Skan 114290075Sobrien/* A subroutine of expand_asm_operands. Check that all operands have 114390075Sobrien the same number of alternatives. Return true if so. */ 114490075Sobrien 114590075Sobrienstatic bool 1146132718Skancheck_operand_nalternatives (tree outputs, tree inputs) 114790075Sobrien{ 114890075Sobrien if (outputs || inputs) 114990075Sobrien { 115090075Sobrien tree tmp = TREE_PURPOSE (outputs ? outputs : inputs); 115190075Sobrien int nalternatives 115290075Sobrien = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp))); 115390075Sobrien tree next = inputs; 115490075Sobrien 115590075Sobrien if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES) 115690075Sobrien { 1157169689Skan error ("too many alternatives in %<asm%>"); 115890075Sobrien return false; 115990075Sobrien } 116090075Sobrien 116190075Sobrien tmp = outputs; 116290075Sobrien while (tmp) 116390075Sobrien { 116490075Sobrien const char *constraint 116590075Sobrien = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp))); 116690075Sobrien 116790075Sobrien if (n_occurrences (',', constraint) != nalternatives) 116890075Sobrien { 1169169689Skan error ("operand constraints for %<asm%> differ " 1170169689Skan "in number of alternatives"); 117190075Sobrien return false; 117290075Sobrien } 117390075Sobrien 117490075Sobrien if (TREE_CHAIN (tmp)) 117590075Sobrien tmp = TREE_CHAIN (tmp); 117690075Sobrien else 117790075Sobrien tmp = next, next = 0; 117890075Sobrien } 117990075Sobrien } 118090075Sobrien 118190075Sobrien return true; 118290075Sobrien} 118390075Sobrien 118490075Sobrien/* A subroutine of expand_asm_operands. Check that all operand names 118590075Sobrien are unique. Return true if so. We rely on the fact that these names 118690075Sobrien are identifiers, and so have been canonicalized by get_identifier, 118790075Sobrien so all we need are pointer comparisons. */ 118890075Sobrien 118990075Sobrienstatic bool 1190132718Skancheck_unique_operand_names (tree outputs, tree inputs) 119190075Sobrien{ 119290075Sobrien tree i, j; 119390075Sobrien 119490075Sobrien for (i = outputs; i ; i = TREE_CHAIN (i)) 119590075Sobrien { 119690075Sobrien tree i_name = TREE_PURPOSE (TREE_PURPOSE (i)); 119790075Sobrien if (! i_name) 119890075Sobrien continue; 119990075Sobrien 120090075Sobrien for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j)) 1201117395Skan if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) 120290075Sobrien goto failure; 120390075Sobrien } 120490075Sobrien 120590075Sobrien for (i = inputs; i ; i = TREE_CHAIN (i)) 120690075Sobrien { 120790075Sobrien tree i_name = TREE_PURPOSE (TREE_PURPOSE (i)); 120890075Sobrien if (! i_name) 120990075Sobrien continue; 121090075Sobrien 121190075Sobrien for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j)) 1212117395Skan if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) 121390075Sobrien goto failure; 121490075Sobrien for (j = outputs; j ; j = TREE_CHAIN (j)) 1215117395Skan if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) 121690075Sobrien goto failure; 121790075Sobrien } 121890075Sobrien 121990075Sobrien return true; 122090075Sobrien 122190075Sobrien failure: 1222169689Skan error ("duplicate asm operand name %qs", 1223117395Skan TREE_STRING_POINTER (TREE_PURPOSE (TREE_PURPOSE (i)))); 122490075Sobrien return false; 122590075Sobrien} 122690075Sobrien 122790075Sobrien/* A subroutine of expand_asm_operands. Resolve the names of the operands 122890075Sobrien in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in 122990075Sobrien STRING and in the constraints to those numbers. */ 123090075Sobrien 1231132718Skantree 1232132718Skanresolve_asm_operand_names (tree string, tree outputs, tree inputs) 123390075Sobrien{ 1234132718Skan char *buffer; 123590075Sobrien char *p; 1236132718Skan const char *c; 123790075Sobrien tree t; 123890075Sobrien 1239132718Skan check_unique_operand_names (outputs, inputs); 124090075Sobrien 1241132718Skan /* Substitute [<name>] in input constraint strings. There should be no 1242132718Skan named operands in output constraints. */ 1243132718Skan for (t = inputs; t ; t = TREE_CHAIN (t)) 124490075Sobrien { 1245132718Skan c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t))); 1246132718Skan if (strchr (c, '[') != NULL) 1247132718Skan { 1248132718Skan p = buffer = xstrdup (c); 1249132718Skan while ((p = strchr (p, '[')) != NULL) 1250132718Skan p = resolve_operand_name_1 (p, outputs, inputs); 1251132718Skan TREE_VALUE (TREE_PURPOSE (t)) 1252132718Skan = build_string (strlen (buffer), buffer); 1253132718Skan free (buffer); 1254132718Skan } 1255132718Skan } 1256132718Skan 1257132718Skan /* Now check for any needed substitutions in the template. */ 1258132718Skan c = TREE_STRING_POINTER (string); 1259132718Skan while ((c = strchr (c, '%')) != NULL) 1260132718Skan { 1261132718Skan if (c[1] == '[') 1262132718Skan break; 1263132718Skan else if (ISALPHA (c[1]) && c[2] == '[') 1264132718Skan break; 126590075Sobrien else 126690075Sobrien { 1267132718Skan c += 1; 126890075Sobrien continue; 126990075Sobrien } 127090075Sobrien } 127190075Sobrien 1272132718Skan if (c) 127390075Sobrien { 1274132718Skan /* OK, we need to make a copy so we can perform the substitutions. 1275132718Skan Assume that we will not need extra space--we get to remove '[' 1276132718Skan and ']', which means we cannot have a problem until we have more 1277132718Skan than 999 operands. */ 1278132718Skan buffer = xstrdup (TREE_STRING_POINTER (string)); 1279132718Skan p = buffer + (c - TREE_STRING_POINTER (string)); 1280169689Skan 1281132718Skan while ((p = strchr (p, '%')) != NULL) 128290075Sobrien { 1283132718Skan if (p[1] == '[') 1284132718Skan p += 1; 1285132718Skan else if (ISALPHA (p[1]) && p[2] == '[') 1286132718Skan p += 2; 1287132718Skan else 1288132718Skan { 1289132718Skan p += 1; 1290132718Skan continue; 1291132718Skan } 129290075Sobrien 1293132718Skan p = resolve_operand_name_1 (p, outputs, inputs); 129490075Sobrien } 1295132718Skan 1296132718Skan string = build_string (strlen (buffer), buffer); 1297132718Skan free (buffer); 129890075Sobrien } 129990075Sobrien 130090075Sobrien return string; 130190075Sobrien} 130290075Sobrien 130390075Sobrien/* A subroutine of resolve_operand_names. P points to the '[' for a 130490075Sobrien potential named operand of the form [<name>]. In place, replace 1305117395Skan the name and brackets with a number. Return a pointer to the 130690075Sobrien balance of the string after substitution. */ 130790075Sobrien 130890075Sobrienstatic char * 1309132718Skanresolve_operand_name_1 (char *p, tree outputs, tree inputs) 131090075Sobrien{ 131190075Sobrien char *q; 131290075Sobrien int op; 131390075Sobrien tree t; 131490075Sobrien size_t len; 131590075Sobrien 131690075Sobrien /* Collect the operand name. */ 131790075Sobrien q = strchr (p, ']'); 131890075Sobrien if (!q) 131990075Sobrien { 132090075Sobrien error ("missing close brace for named operand"); 132190075Sobrien return strchr (p, '\0'); 132290075Sobrien } 132390075Sobrien len = q - p - 1; 132490075Sobrien 132590075Sobrien /* Resolve the name to a number. */ 132690075Sobrien for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++) 132790075Sobrien { 1328117395Skan tree name = TREE_PURPOSE (TREE_PURPOSE (t)); 1329117395Skan if (name) 133096263Sobrien { 1331117395Skan const char *c = TREE_STRING_POINTER (name); 133296263Sobrien if (strncmp (c, p + 1, len) == 0 && c[len] == '\0') 133396263Sobrien goto found; 133496263Sobrien } 133590075Sobrien } 133690075Sobrien for (t = inputs; t ; t = TREE_CHAIN (t), op++) 133790075Sobrien { 1338117395Skan tree name = TREE_PURPOSE (TREE_PURPOSE (t)); 1339117395Skan if (name) 134096263Sobrien { 1341117395Skan const char *c = TREE_STRING_POINTER (name); 134296263Sobrien if (strncmp (c, p + 1, len) == 0 && c[len] == '\0') 134396263Sobrien goto found; 134496263Sobrien } 134590075Sobrien } 134690075Sobrien 134790075Sobrien *q = '\0'; 1348169689Skan error ("undefined named operand %qs", p + 1); 134990075Sobrien op = 0; 135090075Sobrien found: 135190075Sobrien 135290075Sobrien /* Replace the name with the number. Unfortunately, not all libraries 135390075Sobrien get the return value of sprintf correct, so search for the end of the 135490075Sobrien generated string by hand. */ 135590075Sobrien sprintf (p, "%d", op); 135690075Sobrien p = strchr (p, '\0'); 135790075Sobrien 135890075Sobrien /* Verify the no extra buffer space assumption. */ 1359169689Skan gcc_assert (p <= q); 136090075Sobrien 136190075Sobrien /* Shift the rest of the buffer down to fill the gap. */ 136290075Sobrien memmove (p, q + 1, strlen (q + 1) + 1); 136390075Sobrien 136490075Sobrien return p; 136590075Sobrien} 136618334Speter 1367169689Skan/* Generate RTL to evaluate the expression EXP. */ 136818334Speter 136918334Spetervoid 1370132718Skanexpand_expr_stmt (tree exp) 137118334Speter{ 137290075Sobrien rtx value; 137390075Sobrien tree type; 137490075Sobrien 1375169689Skan value = expand_expr (exp, const0_rtx, VOIDmode, 0); 137690075Sobrien type = TREE_TYPE (exp); 137718334Speter 137818334Speter /* If all we do is reference a volatile value in memory, 137918334Speter copy it to a register to be sure it is actually touched. */ 1380169689Skan if (value && MEM_P (value) && TREE_THIS_VOLATILE (exp)) 138118334Speter { 138290075Sobrien if (TYPE_MODE (type) == VOIDmode) 138318334Speter ; 138490075Sobrien else if (TYPE_MODE (type) != BLKmode) 138590075Sobrien value = copy_to_reg (value); 138618334Speter else 138718334Speter { 138818334Speter rtx lab = gen_label_rtx (); 138990075Sobrien 139018334Speter /* Compare the value with itself to reference it. */ 139190075Sobrien emit_cmp_and_jump_insns (value, value, EQ, 1392169689Skan expand_normal (TYPE_SIZE (type)), 139390075Sobrien BLKmode, 0, lab); 139418334Speter emit_label (lab); 139518334Speter } 139618334Speter } 139718334Speter 1398169689Skan /* Free any temporaries used to evaluate this expression. */ 139918334Speter free_temp_slots (); 140018334Speter} 140118334Speter 140218334Speter/* Warn if EXP contains any computations whose results are not used. 1403169689Skan Return 1 if a warning is printed; 0 otherwise. LOCUS is the 1404169689Skan (potential) location of the expression. */ 140518334Speter 140618334Speterint 1407169689Skanwarn_if_unused_value (tree exp, location_t locus) 140818334Speter{ 1409169689Skan restart: 1410169689Skan if (TREE_USED (exp) || TREE_NO_WARNING (exp)) 141118334Speter return 0; 141218334Speter 141390075Sobrien /* Don't warn about void constructs. This includes casting to void, 141490075Sobrien void function calls, and statement expressions with a final cast 141590075Sobrien to void. */ 141690075Sobrien if (VOID_TYPE_P (TREE_TYPE (exp))) 141790075Sobrien return 0; 141890075Sobrien 1419169689Skan if (EXPR_HAS_LOCATION (exp)) 1420169689Skan locus = EXPR_LOCATION (exp); 1421169689Skan 142218334Speter switch (TREE_CODE (exp)) 142318334Speter { 142418334Speter case PREINCREMENT_EXPR: 142518334Speter case POSTINCREMENT_EXPR: 142618334Speter case PREDECREMENT_EXPR: 142718334Speter case POSTDECREMENT_EXPR: 142818334Speter case MODIFY_EXPR: 142918334Speter case INIT_EXPR: 143018334Speter case TARGET_EXPR: 143118334Speter case CALL_EXPR: 143250397Sobrien case TRY_CATCH_EXPR: 143318334Speter case WITH_CLEANUP_EXPR: 143418334Speter case EXIT_EXPR: 1435169689Skan case VA_ARG_EXPR: 143618334Speter return 0; 143718334Speter 143818334Speter case BIND_EXPR: 143918334Speter /* For a binding, warn if no side effect within it. */ 1440169689Skan exp = BIND_EXPR_BODY (exp); 1441169689Skan goto restart; 144218334Speter 144318334Speter case SAVE_EXPR: 1444169689Skan exp = TREE_OPERAND (exp, 0); 1445169689Skan goto restart; 144618334Speter 144718334Speter case TRUTH_ORIF_EXPR: 144818334Speter case TRUTH_ANDIF_EXPR: 144918334Speter /* In && or ||, warn if 2nd operand has no side effect. */ 1450169689Skan exp = TREE_OPERAND (exp, 1); 1451169689Skan goto restart; 145218334Speter 145318334Speter case COMPOUND_EXPR: 1454169689Skan if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus)) 145518334Speter return 1; 145618334Speter /* Let people do `(foo (), 0)' without a warning. */ 145718334Speter if (TREE_CONSTANT (TREE_OPERAND (exp, 1))) 145818334Speter return 0; 1459169689Skan exp = TREE_OPERAND (exp, 1); 1460169689Skan goto restart; 146118334Speter 1462169689Skan case COND_EXPR: 1463169689Skan /* If this is an expression with side effects, don't warn; this 1464169689Skan case commonly appears in macro expansions. */ 1465169689Skan if (TREE_SIDE_EFFECTS (exp)) 146618334Speter return 0; 1467169689Skan goto warn; 146818334Speter 146918334Speter case INDIRECT_REF: 147018334Speter /* Don't warn about automatic dereferencing of references, since 147118334Speter the user cannot control it. */ 147218334Speter if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE) 1473169689Skan { 1474169689Skan exp = TREE_OPERAND (exp, 0); 1475169689Skan goto restart; 1476169689Skan } 147790075Sobrien /* Fall through. */ 147890075Sobrien 147918334Speter default: 148018334Speter /* Referencing a volatile value is a side effect, so don't warn. */ 1481169689Skan if ((DECL_P (exp) || REFERENCE_CLASS_P (exp)) 148218334Speter && TREE_THIS_VOLATILE (exp)) 148318334Speter return 0; 148490075Sobrien 148590075Sobrien /* If this is an expression which has no operands, there is no value 148690075Sobrien to be unused. There are no such language-independent codes, 148790075Sobrien but front ends may define such. */ 1488169689Skan if (EXPRESSION_CLASS_P (exp) && TREE_CODE_LENGTH (TREE_CODE (exp)) == 0) 148990075Sobrien return 0; 149090075Sobrien 1491169689Skan warn: 1492169689Skan warning (0, "%Hvalue computed is not used", &locus); 149318334Speter return 1; 149418334Speter } 149518334Speter} 149618334Speter 149718334Speter 149818334Speter/* Generate RTL to return from the current function, with no value. 149918334Speter (That is, we do not do anything about returning any value.) */ 150018334Speter 150118334Spetervoid 1502132718Skanexpand_null_return (void) 150318334Speter{ 150490075Sobrien /* If this function was declared to return a value, but we 150590075Sobrien didn't, clobber the return registers so that they are not 150690075Sobrien propagated live to the rest of the function. */ 150790075Sobrien clobber_return_register (); 150818334Speter 1509169689Skan expand_null_return_1 (); 151018334Speter} 151118334Speter 1512132718Skan/* Generate RTL to return directly from the current function. 1513132718Skan (That is, we bypass any return value.) */ 1514132718Skan 1515132718Skanvoid 1516132718Skanexpand_naked_return (void) 1517132718Skan{ 1518169689Skan rtx end_label; 1519132718Skan 1520132718Skan clear_pending_stack_adjust (); 1521132718Skan do_pending_stack_adjust (); 1522132718Skan 1523169689Skan end_label = naked_return_label; 1524132718Skan if (end_label == 0) 1525132718Skan end_label = naked_return_label = gen_label_rtx (); 1526132718Skan 1527169689Skan emit_jump (end_label); 1528117395Skan} 1529117395Skan 153018334Speter/* Generate RTL to return from the current function, with value VAL. */ 153118334Speter 153218334Speterstatic void 1533132718Skanexpand_value_return (rtx val) 153418334Speter{ 153518334Speter /* Copy the value to the return location 153618334Speter unless it's already there. */ 153718334Speter 1538169689Skan rtx return_reg = DECL_RTL (DECL_RESULT (current_function_decl)); 153918334Speter if (return_reg != val) 154018334Speter { 154190075Sobrien tree type = TREE_TYPE (DECL_RESULT (current_function_decl)); 1542132718Skan if (targetm.calls.promote_function_return (TREE_TYPE (current_function_decl))) 1543132718Skan { 1544169689Skan int unsignedp = TYPE_UNSIGNED (type); 1545132718Skan enum machine_mode old_mode 1546132718Skan = DECL_MODE (DECL_RESULT (current_function_decl)); 1547132718Skan enum machine_mode mode 1548132718Skan = promote_mode (type, old_mode, &unsignedp, 1); 154918334Speter 1550132718Skan if (mode != old_mode) 1551132718Skan val = convert_modes (mode, old_mode, val, unsignedp); 1552132718Skan } 155390075Sobrien if (GET_CODE (return_reg) == PARALLEL) 1554132718Skan emit_group_load (return_reg, val, type, int_size_in_bytes (type)); 155590075Sobrien else 155690075Sobrien emit_move_insn (return_reg, val); 155718334Speter } 155818334Speter 1559169689Skan expand_null_return_1 (); 156018334Speter} 156118334Speter 1562169689Skan/* Output a return with no value. */ 156318334Speter 156418334Speterstatic void 1565169689Skanexpand_null_return_1 (void) 156618334Speter{ 156718334Speter clear_pending_stack_adjust (); 156818334Speter do_pending_stack_adjust (); 1569169689Skan emit_jump (return_label); 157018334Speter} 157118334Speter 157218334Speter/* Generate RTL to evaluate the expression RETVAL and return it 157318334Speter from the current function. */ 157418334Speter 157518334Spetervoid 1576132718Skanexpand_return (tree retval) 157718334Speter{ 157890075Sobrien rtx result_rtl; 157990075Sobrien rtx val = 0; 158018334Speter tree retval_rhs; 158118334Speter 158218334Speter /* If function wants no value, give it none. */ 158318334Speter if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE) 158418334Speter { 1585169689Skan expand_normal (retval); 158618334Speter expand_null_return (); 158718334Speter return; 158818334Speter } 158918334Speter 159090075Sobrien if (retval == error_mark_node) 159190075Sobrien { 159290075Sobrien /* Treat this like a return of no value from a function that 159390075Sobrien returns a value. */ 159490075Sobrien expand_null_return (); 1595117395Skan return; 159690075Sobrien } 1597169689Skan else if ((TREE_CODE (retval) == MODIFY_EXPR 1598169689Skan || TREE_CODE (retval) == INIT_EXPR) 159918334Speter && TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL) 160018334Speter retval_rhs = TREE_OPERAND (retval, 1); 1601169689Skan else 160218334Speter retval_rhs = retval; 160318334Speter 1604169689Skan result_rtl = DECL_RTL (DECL_RESULT (current_function_decl)); 160518334Speter 1606169689Skan /* If we are returning the RESULT_DECL, then the value has already 1607169689Skan been stored into it, so we don't have to do anything special. */ 1608169689Skan if (TREE_CODE (retval_rhs) == RESULT_DECL) 1609169689Skan expand_value_return (result_rtl); 161018334Speter 161118334Speter /* If the result is an aggregate that is being returned in one (or more) 161218334Speter registers, load the registers here. The compiler currently can't handle 161318334Speter copying a BLKmode value into registers. We could put this code in a 161418334Speter more general area (for use by everyone instead of just function 161518334Speter call/return), but until this feature is generally usable it is kept here 1616169689Skan (and in expand_call). */ 161718334Speter 1618169689Skan else if (retval_rhs != 0 1619169689Skan && TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode 1620169689Skan && REG_P (result_rtl)) 162118334Speter { 162290075Sobrien int i; 162390075Sobrien unsigned HOST_WIDE_INT bitpos, xbitpos; 1624132718Skan unsigned HOST_WIDE_INT padding_correction = 0; 162590075Sobrien unsigned HOST_WIDE_INT bytes 162690075Sobrien = int_size_in_bytes (TREE_TYPE (retval_rhs)); 162718334Speter int n_regs = (bytes + UNITS_PER_WORD - 1) / UNITS_PER_WORD; 162890075Sobrien unsigned int bitsize 162990075Sobrien = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)), BITS_PER_WORD); 1630132718Skan rtx *result_pseudos = alloca (sizeof (rtx) * n_regs); 163150397Sobrien rtx result_reg, src = NULL_RTX, dst = NULL_RTX; 1632169689Skan rtx result_val = expand_normal (retval_rhs); 163318334Speter enum machine_mode tmpmode, result_reg_mode; 163418334Speter 163590075Sobrien if (bytes == 0) 163690075Sobrien { 163790075Sobrien expand_null_return (); 163890075Sobrien return; 163990075Sobrien } 164090075Sobrien 1641132718Skan /* If the structure doesn't take up a whole number of words, see 1642132718Skan whether the register value should be padded on the left or on 1643132718Skan the right. Set PADDING_CORRECTION to the number of padding 1644132718Skan bits needed on the left side. 164518334Speter 1646132718Skan In most ABIs, the structure will be returned at the least end of 1647132718Skan the register, which translates to right padding on little-endian 1648132718Skan targets and left padding on big-endian targets. The opposite 1649132718Skan holds if the structure is returned at the most significant 1650132718Skan end of the register. */ 1651132718Skan if (bytes % UNITS_PER_WORD != 0 1652132718Skan && (targetm.calls.return_in_msb (TREE_TYPE (retval_rhs)) 1653132718Skan ? !BYTES_BIG_ENDIAN 1654132718Skan : BYTES_BIG_ENDIAN)) 1655132718Skan padding_correction = (BITS_PER_WORD - ((bytes % UNITS_PER_WORD) 1656132718Skan * BITS_PER_UNIT)); 1657132718Skan 165890075Sobrien /* Copy the structure BITSIZE bits at a time. */ 1659132718Skan for (bitpos = 0, xbitpos = padding_correction; 166018334Speter bitpos < bytes * BITS_PER_UNIT; 166118334Speter bitpos += bitsize, xbitpos += bitsize) 166218334Speter { 166318334Speter /* We need a new destination pseudo each time xbitpos is 1664132718Skan on a word boundary and when xbitpos == padding_correction 166518334Speter (the first time through). */ 166618334Speter if (xbitpos % BITS_PER_WORD == 0 1667132718Skan || xbitpos == padding_correction) 166818334Speter { 166918334Speter /* Generate an appropriate register. */ 167018334Speter dst = gen_reg_rtx (word_mode); 167118334Speter result_pseudos[xbitpos / BITS_PER_WORD] = dst; 167218334Speter 167390075Sobrien /* Clear the destination before we move anything into it. */ 167490075Sobrien emit_move_insn (dst, CONST0_RTX (GET_MODE (dst))); 167518334Speter } 167618334Speter 167718334Speter /* We need a new source operand each time bitpos is on a word 167818334Speter boundary. */ 167918334Speter if (bitpos % BITS_PER_WORD == 0) 168018334Speter src = operand_subword_force (result_val, 168118334Speter bitpos / BITS_PER_WORD, 168218334Speter BLKmode); 168318334Speter 168418334Speter /* Use bitpos for the source extraction (left justified) and 168518334Speter xbitpos for the destination store (right justified). */ 168618334Speter store_bit_field (dst, bitsize, xbitpos % BITS_PER_WORD, word_mode, 168718334Speter extract_bit_field (src, bitsize, 168818334Speter bitpos % BITS_PER_WORD, 1, 1689169689Skan NULL_RTX, word_mode, word_mode)); 169018334Speter } 169118334Speter 1692132718Skan tmpmode = GET_MODE (result_rtl); 1693132718Skan if (tmpmode == BLKmode) 1694132718Skan { 1695132718Skan /* Find the smallest integer mode large enough to hold the 1696132718Skan entire structure and use that mode instead of BLKmode 1697132718Skan on the USE insn for the return register. */ 1698132718Skan for (tmpmode = GET_CLASS_NARROWEST_MODE (MODE_INT); 1699132718Skan tmpmode != VOIDmode; 1700132718Skan tmpmode = GET_MODE_WIDER_MODE (tmpmode)) 1701132718Skan /* Have we found a large enough mode? */ 1702132718Skan if (GET_MODE_SIZE (tmpmode) >= bytes) 1703132718Skan break; 170418334Speter 1705169689Skan /* A suitable mode should have been found. */ 1706169689Skan gcc_assert (tmpmode != VOIDmode); 170718334Speter 1708132718Skan PUT_MODE (result_rtl, tmpmode); 1709132718Skan } 171018334Speter 171118334Speter if (GET_MODE_SIZE (tmpmode) < GET_MODE_SIZE (word_mode)) 171218334Speter result_reg_mode = word_mode; 171318334Speter else 171418334Speter result_reg_mode = tmpmode; 171518334Speter result_reg = gen_reg_rtx (result_reg_mode); 171618334Speter 171718334Speter for (i = 0; i < n_regs; i++) 171818334Speter emit_move_insn (operand_subword (result_reg, i, 0, result_reg_mode), 171918334Speter result_pseudos[i]); 172018334Speter 172118334Speter if (tmpmode != result_reg_mode) 172218334Speter result_reg = gen_lowpart (tmpmode, result_reg); 172318334Speter 172418334Speter expand_value_return (result_reg); 172518334Speter } 172690075Sobrien else if (retval_rhs != 0 172790075Sobrien && !VOID_TYPE_P (TREE_TYPE (retval_rhs)) 1728169689Skan && (REG_P (result_rtl) 172990075Sobrien || (GET_CODE (result_rtl) == PARALLEL))) 173018334Speter { 173190075Sobrien /* Calculate the return value into a temporary (usually a pseudo 173290075Sobrien reg). */ 173390075Sobrien tree ot = TREE_TYPE (DECL_RESULT (current_function_decl)); 173490075Sobrien tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST); 173590075Sobrien 173690075Sobrien val = assign_temp (nt, 0, 0, 1); 173750397Sobrien val = expand_expr (retval_rhs, val, GET_MODE (val), 0); 173850397Sobrien val = force_not_mem (val); 1739169689Skan /* Return the calculated value. */ 1740169689Skan expand_value_return (val); 174118334Speter } 174218334Speter else 174318334Speter { 1744169689Skan /* No hard reg used; calculate value into hard return reg. */ 174518334Speter expand_expr (retval, const0_rtx, VOIDmode, 0); 174690075Sobrien expand_value_return (result_rtl); 174718334Speter } 174818334Speter} 174918334Speter 1750117395Skan/* Given a pointer to a BLOCK node return nonzero if (and only if) the node 175190075Sobrien in question represents the outermost pair of curly braces (i.e. the "body 175290075Sobrien block") of a function or method. 175350397Sobrien 175490075Sobrien For any BLOCK node representing a "body block" of a function or method, the 175590075Sobrien BLOCK_SUPERCONTEXT of the node will point to another BLOCK node which 175690075Sobrien represents the outermost (function) scope for the function or method (i.e. 175790075Sobrien the one which includes the formal parameters). The BLOCK_SUPERCONTEXT of 175890075Sobrien *that* node in turn will point to the relevant FUNCTION_DECL node. */ 175990075Sobrien 176090075Sobrienint 1761132718Skanis_body_block (tree stmt) 176250397Sobrien{ 1763132718Skan if (lang_hooks.no_body_blocks) 1764132718Skan return 0; 1765132718Skan 176690075Sobrien if (TREE_CODE (stmt) == BLOCK) 176718334Speter { 176890075Sobrien tree parent = BLOCK_SUPERCONTEXT (stmt); 176990075Sobrien 177090075Sobrien if (parent && TREE_CODE (parent) == BLOCK) 177190075Sobrien { 177290075Sobrien tree grandparent = BLOCK_SUPERCONTEXT (parent); 177390075Sobrien 177490075Sobrien if (grandparent && TREE_CODE (grandparent) == FUNCTION_DECL) 177590075Sobrien return 1; 177690075Sobrien } 177718334Speter } 177890075Sobrien 177990075Sobrien return 0; 178018334Speter} 178118334Speter 178252284Sobrien/* Emit code to restore vital registers at the beginning of a nonlocal goto 178352284Sobrien handler. */ 178452284Sobrienstatic void 1785132718Skanexpand_nl_goto_receiver (void) 178652284Sobrien{ 1787169689Skan /* Clobber the FP when we get here, so we have to make sure it's 1788132718Skan marked as used by this function. */ 1789132718Skan emit_insn (gen_rtx_USE (VOIDmode, hard_frame_pointer_rtx)); 1790132718Skan 1791132718Skan /* Mark the static chain as clobbered here so life information 1792132718Skan doesn't get messed up for it. */ 1793132718Skan emit_insn (gen_rtx_CLOBBER (VOIDmode, static_chain_rtx)); 1794132718Skan 179552284Sobrien#ifdef HAVE_nonlocal_goto 179652284Sobrien if (! HAVE_nonlocal_goto) 179752284Sobrien#endif 179852284Sobrien /* First adjust our frame pointer to its actual value. It was 179952284Sobrien previously set to the start of the virtual area corresponding to 180052284Sobrien the stacked variables when we branched here and now needs to be 180152284Sobrien adjusted to the actual hardware fp value. 180252284Sobrien 180352284Sobrien Assignments are to virtual registers are converted by 180452284Sobrien instantiate_virtual_regs into the corresponding assignment 180552284Sobrien to the underlying register (fp in this case) that makes 180652284Sobrien the original assignment true. 180752284Sobrien So the following insn will actually be 180852284Sobrien decrementing fp by STARTING_FRAME_OFFSET. */ 180952284Sobrien emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx); 181052284Sobrien 181152284Sobrien#if ARG_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 181252284Sobrien if (fixed_regs[ARG_POINTER_REGNUM]) 181352284Sobrien { 181452284Sobrien#ifdef ELIMINABLE_REGS 181552284Sobrien /* If the argument pointer can be eliminated in favor of the 181652284Sobrien frame pointer, we don't need to restore it. We assume here 181752284Sobrien that if such an elimination is present, it can always be used. 181852284Sobrien This is the case on all known machines; if we don't make this 181952284Sobrien assumption, we do unnecessary saving on many machines. */ 182090075Sobrien static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS; 182152284Sobrien size_t i; 182252284Sobrien 182390075Sobrien for (i = 0; i < ARRAY_SIZE (elim_regs); i++) 182452284Sobrien if (elim_regs[i].from == ARG_POINTER_REGNUM 182552284Sobrien && elim_regs[i].to == HARD_FRAME_POINTER_REGNUM) 182652284Sobrien break; 182752284Sobrien 182890075Sobrien if (i == ARRAY_SIZE (elim_regs)) 182952284Sobrien#endif 183052284Sobrien { 183152284Sobrien /* Now restore our arg pointer from the address at which it 183290075Sobrien was saved in our stack frame. */ 183352284Sobrien emit_move_insn (virtual_incoming_args_rtx, 183490075Sobrien copy_to_reg (get_arg_pointer_save_area (cfun))); 183552284Sobrien } 183652284Sobrien } 183752284Sobrien#endif 183852284Sobrien 183952284Sobrien#ifdef HAVE_nonlocal_goto_receiver 184052284Sobrien if (HAVE_nonlocal_goto_receiver) 184152284Sobrien emit_insn (gen_nonlocal_goto_receiver ()); 184252284Sobrien#endif 1843132718Skan 1844132718Skan /* @@@ This is a kludge. Not all machine descriptions define a blockage 1845132718Skan insn, but we must not allow the code we just generated to be reordered 1846132718Skan by scheduling. Specifically, the update of the frame pointer must 1847132718Skan happen immediately, not later. So emit an ASM_INPUT to act as blockage 1848132718Skan insn. */ 1849132718Skan emit_insn (gen_rtx_ASM_INPUT (VOIDmode, "")); 185052284Sobrien} 185118334Speter 185218334Speter/* Generate RTL for the automatic variable declaration DECL. 185318334Speter (Other kinds of declarations are simply ignored if seen here.) */ 185418334Speter 185518334Spetervoid 1856132718Skanexpand_decl (tree decl) 185718334Speter{ 185818334Speter tree type; 185918334Speter 186018334Speter type = TREE_TYPE (decl); 186118334Speter 186290075Sobrien /* For a CONST_DECL, set mode, alignment, and sizes from those of the 186390075Sobrien type in case this node is used in a reference. */ 186490075Sobrien if (TREE_CODE (decl) == CONST_DECL) 186590075Sobrien { 186690075Sobrien DECL_MODE (decl) = TYPE_MODE (type); 186790075Sobrien DECL_ALIGN (decl) = TYPE_ALIGN (type); 186890075Sobrien DECL_SIZE (decl) = TYPE_SIZE (type); 186990075Sobrien DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type); 187090075Sobrien return; 187190075Sobrien } 187218334Speter 187390075Sobrien /* Otherwise, only automatic variables need any expansion done. Static and 187490075Sobrien external variables, and external functions, will be handled by 187590075Sobrien `assemble_variable' (called from finish_decl). TYPE_DECL requires 187690075Sobrien nothing. PARM_DECLs are handled in `assign_parms'. */ 187718334Speter if (TREE_CODE (decl) != VAR_DECL) 187818334Speter return; 187990075Sobrien 188018334Speter if (TREE_STATIC (decl) || DECL_EXTERNAL (decl)) 188118334Speter return; 188218334Speter 188318334Speter /* Create the RTL representation for the variable. */ 188418334Speter 188518334Speter if (type == error_mark_node) 188690075Sobrien SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx)); 188790075Sobrien 188818334Speter else if (DECL_SIZE (decl) == 0) 188918334Speter /* Variable with incomplete type. */ 189018334Speter { 189190075Sobrien rtx x; 189218334Speter if (DECL_INITIAL (decl) == 0) 189318334Speter /* Error message was already done; now avoid a crash. */ 189490075Sobrien x = gen_rtx_MEM (BLKmode, const0_rtx); 189518334Speter else 189618334Speter /* An initializer is going to decide the size of this array. 189718334Speter Until we know the size, represent its address with a reg. */ 189890075Sobrien x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode)); 189990075Sobrien 190090075Sobrien set_mem_attributes (x, decl, 1); 190190075Sobrien SET_DECL_RTL (decl, x); 190218334Speter } 1903169689Skan else if (use_register_for_decl (decl)) 190418334Speter { 190518334Speter /* Automatic variable that can go in a register. */ 1906169689Skan int unsignedp = TYPE_UNSIGNED (type); 190718334Speter enum machine_mode reg_mode 190818334Speter = promote_mode (type, DECL_MODE (decl), &unsignedp, 0); 190918334Speter 191090075Sobrien SET_DECL_RTL (decl, gen_reg_rtx (reg_mode)); 191190075Sobrien 1912169689Skan /* Note if the object is a user variable. */ 1913132718Skan if (!DECL_ARTIFICIAL (decl)) 1914169689Skan { 1915169689Skan mark_user_reg (DECL_RTL (decl)); 191690075Sobrien 1917169689Skan /* Trust user variables which have a pointer type to really 1918169689Skan be pointers. Do not trust compiler generated temporaries 1919169689Skan as our type system is totally busted as it relates to 1920169689Skan pointer arithmetic which translates into lots of compiler 1921169689Skan generated objects with pointer types, but which are not really 1922169689Skan pointers. */ 1923169689Skan if (POINTER_TYPE_P (type)) 1924169689Skan mark_reg_pointer (DECL_RTL (decl), 1925169689Skan TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl)))); 1926169689Skan } 192718334Speter } 192850397Sobrien 192990075Sobrien else if (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST 193050397Sobrien && ! (flag_stack_check && ! STACK_CHECK_BUILTIN 193190075Sobrien && 0 < compare_tree_int (DECL_SIZE_UNIT (decl), 193290075Sobrien STACK_CHECK_MAX_VAR_SIZE))) 193318334Speter { 193418334Speter /* Variable of fixed size that goes on the stack. */ 193518334Speter rtx oldaddr = 0; 193618334Speter rtx addr; 193790075Sobrien rtx x; 193818334Speter 193918334Speter /* If we previously made RTL for this decl, it must be an array 194018334Speter whose size was determined by the initializer. 194118334Speter The old address was a register; set that register now 194218334Speter to the proper address. */ 194390075Sobrien if (DECL_RTL_SET_P (decl)) 194418334Speter { 1945169689Skan gcc_assert (MEM_P (DECL_RTL (decl))); 1946169689Skan gcc_assert (REG_P (XEXP (DECL_RTL (decl), 0))); 194718334Speter oldaddr = XEXP (DECL_RTL (decl), 0); 194818334Speter } 194918334Speter 195018334Speter /* Set alignment we actually gave this decl. */ 195118334Speter DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT 195218334Speter : GET_MODE_BITSIZE (DECL_MODE (decl))); 195390075Sobrien DECL_USER_ALIGN (decl) = 0; 195418334Speter 195596263Sobrien x = assign_temp (decl, 1, 1, 1); 195690075Sobrien set_mem_attributes (x, decl, 1); 195790075Sobrien SET_DECL_RTL (decl, x); 195890075Sobrien 195918334Speter if (oldaddr) 196018334Speter { 196118334Speter addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr); 196218334Speter if (addr != oldaddr) 196318334Speter emit_move_insn (oldaddr, addr); 196418334Speter } 196518334Speter } 196618334Speter else 196718334Speter /* Dynamic-size object: must push space on the stack. */ 196818334Speter { 196990075Sobrien rtx address, size, x; 197018334Speter 197118334Speter /* Record the stack pointer on entry to block, if have 197218334Speter not already done so. */ 197390075Sobrien do_pending_stack_adjust (); 197418334Speter 1975169689Skan /* Compute the variable's size, in bytes. This will expand any 1976169689Skan needed SAVE_EXPRs for the first time. */ 1977169689Skan size = expand_normal (DECL_SIZE_UNIT (decl)); 197818334Speter free_temp_slots (); 197918334Speter 198050397Sobrien /* Allocate space on the stack for the variable. Note that 198190075Sobrien DECL_ALIGN says how the variable is to be aligned and we 198250397Sobrien cannot use it to conclude anything about the alignment of 198350397Sobrien the size. */ 198418334Speter address = allocate_dynamic_stack_space (size, NULL_RTX, 198550397Sobrien TYPE_ALIGN (TREE_TYPE (decl))); 198618334Speter 198718334Speter /* Reference the variable indirect through that rtx. */ 198890075Sobrien x = gen_rtx_MEM (DECL_MODE (decl), address); 198990075Sobrien set_mem_attributes (x, decl, 1); 199090075Sobrien SET_DECL_RTL (decl, x); 199118334Speter 199218334Speter 199318334Speter /* Indicate the alignment we actually gave this variable. */ 199418334Speter#ifdef STACK_BOUNDARY 199518334Speter DECL_ALIGN (decl) = STACK_BOUNDARY; 199618334Speter#else 199718334Speter DECL_ALIGN (decl) = BIGGEST_ALIGNMENT; 199818334Speter#endif 199990075Sobrien DECL_USER_ALIGN (decl) = 0; 200018334Speter } 200118334Speter} 200218334Speter 2003169689Skan/* Emit code to save the current value of stack. */ 2004169689Skanrtx 2005169689Skanexpand_stack_save (void) 200618334Speter{ 2007169689Skan rtx ret = NULL_RTX; 200818334Speter 2009169689Skan do_pending_stack_adjust (); 2010169689Skan emit_stack_save (SAVE_BLOCK, &ret, NULL_RTX); 2011169689Skan return ret; 201218334Speter} 201318334Speter 2014169689Skan/* Emit code to restore the current value of stack. */ 2015169689Skanvoid 2016169689Skanexpand_stack_restore (tree var) 201718334Speter{ 2018169689Skan rtx sa = DECL_RTL (var); 201918334Speter 2020169689Skan emit_stack_restore (SAVE_BLOCK, sa, NULL_RTX); 202150397Sobrien} 202218334Speter 202318334Speter/* DECL is an anonymous union. CLEANUP is a cleanup for DECL. 202418334Speter DECL_ELTS is the list of elements that belong to DECL's type. 202518334Speter In each, the TREE_VALUE is a VAR_DECL, and the TREE_PURPOSE a cleanup. */ 202618334Speter 202718334Spetervoid 2028169689Skanexpand_anon_union_decl (tree decl, tree cleanup ATTRIBUTE_UNUSED, 2029169689Skan tree decl_elts) 203018334Speter{ 203118334Speter rtx x; 203290075Sobrien tree t; 203318334Speter 203490075Sobrien /* If any of the elements are addressable, so is the entire union. */ 203590075Sobrien for (t = decl_elts; t; t = TREE_CHAIN (t)) 203690075Sobrien if (TREE_ADDRESSABLE (TREE_VALUE (t))) 203790075Sobrien { 203890075Sobrien TREE_ADDRESSABLE (decl) = 1; 203990075Sobrien break; 204090075Sobrien } 204190075Sobrien 204218334Speter expand_decl (decl); 204318334Speter x = DECL_RTL (decl); 204418334Speter 204590075Sobrien /* Go through the elements, assigning RTL to each. */ 204690075Sobrien for (t = decl_elts; t; t = TREE_CHAIN (t)) 204718334Speter { 204890075Sobrien tree decl_elt = TREE_VALUE (t); 204918334Speter enum machine_mode mode = TYPE_MODE (TREE_TYPE (decl_elt)); 2050169689Skan rtx decl_rtl; 205118334Speter 205296263Sobrien /* If any of the elements are addressable, so is the entire 205396263Sobrien union. */ 205496263Sobrien if (TREE_USED (decl_elt)) 205596263Sobrien TREE_USED (decl) = 1; 205696263Sobrien 205718334Speter /* Propagate the union's alignment to the elements. */ 205818334Speter DECL_ALIGN (decl_elt) = DECL_ALIGN (decl); 205990075Sobrien DECL_USER_ALIGN (decl_elt) = DECL_USER_ALIGN (decl); 206018334Speter 206118334Speter /* If the element has BLKmode and the union doesn't, the union is 206218334Speter aligned such that the element doesn't need to have BLKmode, so 206318334Speter change the element's mode to the appropriate one for its size. */ 206418334Speter if (mode == BLKmode && DECL_MODE (decl) != BLKmode) 206518334Speter DECL_MODE (decl_elt) = mode 206690075Sobrien = mode_for_size_tree (DECL_SIZE (decl_elt), MODE_INT, 1); 206718334Speter 2068169689Skan if (mode == GET_MODE (x)) 2069169689Skan decl_rtl = x; 2070169689Skan else if (MEM_P (x)) 2071169689Skan /* (SUBREG (MEM ...)) at RTL generation time is invalid, so we 2072169689Skan instead create a new MEM rtx with the proper mode. */ 2073169689Skan decl_rtl = adjust_address_nv (x, mode, 0); 2074169689Skan else 207518334Speter { 2076169689Skan gcc_assert (REG_P (x)); 2077169689Skan decl_rtl = gen_lowpart_SUBREG (mode, x); 207818334Speter } 2079169689Skan SET_DECL_RTL (decl_elt, decl_rtl); 208018334Speter } 208118334Speter} 208218334Speter 2083169689Skan/* Do the insertion of a case label into case_list. The labels are 2084169689Skan fed to us in descending order from the sorted vector of case labels used 2085169689Skan in the tree part of the middle end. So the list we construct is 2086169689Skan sorted in ascending order. The bounds on the case range, LOW and HIGH, 2087169689Skan are converted to case's index type TYPE. */ 208818334Speter 2089169689Skanstatic struct case_node * 2090169689Skanadd_case_node (struct case_node *head, tree type, tree low, tree high, 2091169689Skan tree label) 209218334Speter{ 2093169689Skan tree min_value, max_value; 2094169689Skan struct case_node *r; 2095132718Skan 2096169689Skan gcc_assert (TREE_CODE (low) == INTEGER_CST); 2097169689Skan gcc_assert (!high || TREE_CODE (high) == INTEGER_CST); 209818334Speter 2099169689Skan min_value = TYPE_MIN_VALUE (type); 2100169689Skan max_value = TYPE_MAX_VALUE (type); 210150397Sobrien 210290075Sobrien /* If there's no HIGH value, then this is not a case range; it's 210390075Sobrien just a simple case label. But that's just a degenerate case 2104169689Skan range. 2105169689Skan If the bounds are equal, turn this into the one-value case. */ 2106169689Skan if (!high || tree_int_cst_equal (low, high)) 210790075Sobrien { 2108169689Skan /* If the simple case value is unreachable, ignore it. */ 2109169689Skan if ((TREE_CODE (min_value) == INTEGER_CST 2110169689Skan && tree_int_cst_compare (low, min_value) < 0) 2111169689Skan || (TREE_CODE (max_value) == INTEGER_CST 2112169689Skan && tree_int_cst_compare (low, max_value) > 0)) 2113169689Skan return head; 2114169689Skan low = fold_convert (type, low); 2115169689Skan high = low; 211690075Sobrien } 2117169689Skan else 211818334Speter { 2119169689Skan /* If the entire case range is unreachable, ignore it. */ 2120169689Skan if ((TREE_CODE (min_value) == INTEGER_CST 2121169689Skan && tree_int_cst_compare (high, min_value) < 0) 2122169689Skan || (TREE_CODE (max_value) == INTEGER_CST 2123169689Skan && tree_int_cst_compare (low, max_value) > 0)) 2124169689Skan return head; 212550397Sobrien 2126169689Skan /* If the lower bound is less than the index type's minimum 2127169689Skan value, truncate the range bounds. */ 2128169689Skan if (TREE_CODE (min_value) == INTEGER_CST 2129169689Skan && tree_int_cst_compare (low, min_value) < 0) 2130169689Skan low = min_value; 2131169689Skan low = fold_convert (type, low); 213250397Sobrien 2133169689Skan /* If the upper bound is greater than the index type's maximum 2134169689Skan value, truncate the range bounds. */ 2135169689Skan if (TREE_CODE (max_value) == INTEGER_CST 2136169689Skan && tree_int_cst_compare (high, max_value) > 0) 2137169689Skan high = max_value; 2138169689Skan high = fold_convert (type, high); 213918334Speter } 214018334Speter 214118334Speter 2142169689Skan /* Add this label to the chain. Make sure to drop overflow flags. */ 2143132718Skan r = ggc_alloc (sizeof (struct case_node)); 2144169689Skan r->low = build_int_cst_wide (TREE_TYPE (low), TREE_INT_CST_LOW (low), 2145169689Skan TREE_INT_CST_HIGH (low)); 2146169689Skan r->high = build_int_cst_wide (TREE_TYPE (high), TREE_INT_CST_LOW (high), 2147169689Skan TREE_INT_CST_HIGH (high)); 214850397Sobrien r->code_label = label; 2149169689Skan r->parent = r->left = NULL; 2150169689Skan r->right = head; 2151169689Skan return r; 215218334Speter} 215318334Speter 2154132718Skan/* Maximum number of case bit tests. */ 2155132718Skan#define MAX_CASE_BIT_TESTS 3 215690075Sobrien 2157132718Skan/* By default, enable case bit tests on targets with ashlsi3. */ 2158132718Skan#ifndef CASE_USE_BIT_TESTS 2159132718Skan#define CASE_USE_BIT_TESTS (ashl_optab->handlers[word_mode].insn_code \ 2160132718Skan != CODE_FOR_nothing) 2161132718Skan#endif 2162132718Skan 2163132718Skan 2164132718Skan/* A case_bit_test represents a set of case nodes that may be 2165132718Skan selected from using a bit-wise comparison. HI and LO hold 2166132718Skan the integer to be tested against, LABEL contains the label 2167132718Skan to jump to upon success and BITS counts the number of case 2168132718Skan nodes handled by this test, typically the number of bits 2169132718Skan set in HI:LO. */ 2170132718Skan 2171132718Skanstruct case_bit_test 2172132718Skan{ 2173132718Skan HOST_WIDE_INT hi; 2174132718Skan HOST_WIDE_INT lo; 2175132718Skan rtx label; 2176132718Skan int bits; 2177132718Skan}; 2178132718Skan 2179132718Skan/* Determine whether "1 << x" is relatively cheap in word_mode. */ 2180132718Skan 2181132718Skanstatic 2182132718Skanbool lshift_cheap_p (void) 2183132718Skan{ 2184132718Skan static bool init = false; 2185132718Skan static bool cheap = true; 2186132718Skan 2187132718Skan if (!init) 2188132718Skan { 2189132718Skan rtx reg = gen_rtx_REG (word_mode, 10000); 2190132718Skan int cost = rtx_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg), SET); 2191132718Skan cheap = cost < COSTS_N_INSNS (3); 2192132718Skan init = true; 2193132718Skan } 2194132718Skan 2195132718Skan return cheap; 2196132718Skan} 2197132718Skan 2198132718Skan/* Comparison function for qsort to order bit tests by decreasing 2199132718Skan number of case nodes, i.e. the node with the most cases gets 2200132718Skan tested first. */ 2201132718Skan 2202169689Skanstatic int 2203169689Skancase_bit_test_cmp (const void *p1, const void *p2) 2204132718Skan{ 2205132718Skan const struct case_bit_test *d1 = p1; 2206132718Skan const struct case_bit_test *d2 = p2; 2207132718Skan 2208169689Skan if (d2->bits != d1->bits) 2209169689Skan return d2->bits - d1->bits; 2210169689Skan 2211169689Skan /* Stabilize the sort. */ 2212169689Skan return CODE_LABEL_NUMBER (d2->label) - CODE_LABEL_NUMBER (d1->label); 2213132718Skan} 2214132718Skan 2215132718Skan/* Expand a switch statement by a short sequence of bit-wise 2216132718Skan comparisons. "switch(x)" is effectively converted into 2217132718Skan "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are 2218132718Skan integer constants. 2219132718Skan 2220132718Skan INDEX_EXPR is the value being switched on, which is of 2221132718Skan type INDEX_TYPE. MINVAL is the lowest case value of in 2222132718Skan the case nodes, of INDEX_TYPE type, and RANGE is highest 2223132718Skan value minus MINVAL, also of type INDEX_TYPE. NODES is 2224132718Skan the set of case nodes, and DEFAULT_LABEL is the label to 2225132718Skan branch to should none of the cases match. 2226132718Skan 2227132718Skan There *MUST* be MAX_CASE_BIT_TESTS or less unique case 2228132718Skan node targets. */ 2229132718Skan 2230132718Skanstatic void 2231132718Skanemit_case_bit_tests (tree index_type, tree index_expr, tree minval, 2232132718Skan tree range, case_node_ptr nodes, rtx default_label) 2233132718Skan{ 2234132718Skan struct case_bit_test test[MAX_CASE_BIT_TESTS]; 2235132718Skan enum machine_mode mode; 2236132718Skan rtx expr, index, label; 2237132718Skan unsigned int i,j,lo,hi; 2238132718Skan struct case_node *n; 2239132718Skan unsigned int count; 2240132718Skan 2241132718Skan count = 0; 2242132718Skan for (n = nodes; n; n = n->right) 2243132718Skan { 2244132718Skan label = label_rtx (n->code_label); 2245132718Skan for (i = 0; i < count; i++) 2246169689Skan if (label == test[i].label) 2247132718Skan break; 2248132718Skan 2249132718Skan if (i == count) 2250132718Skan { 2251169689Skan gcc_assert (count < MAX_CASE_BIT_TESTS); 2252169689Skan test[i].hi = 0; 2253169689Skan test[i].lo = 0; 2254132718Skan test[i].label = label; 2255132718Skan test[i].bits = 1; 2256132718Skan count++; 2257132718Skan } 2258132718Skan else 2259132718Skan test[i].bits++; 2260132718Skan 2261169689Skan lo = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 2262169689Skan n->low, minval), 1); 2263169689Skan hi = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 2264169689Skan n->high, minval), 1); 2265132718Skan for (j = lo; j <= hi; j++) 2266132718Skan if (j >= HOST_BITS_PER_WIDE_INT) 2267132718Skan test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT); 2268132718Skan else 2269132718Skan test[i].lo |= (HOST_WIDE_INT) 1 << j; 2270132718Skan } 2271132718Skan 2272132718Skan qsort (test, count, sizeof(*test), case_bit_test_cmp); 2273132718Skan 2274169689Skan index_expr = fold_build2 (MINUS_EXPR, index_type, 2275169689Skan fold_convert (index_type, index_expr), 2276169689Skan fold_convert (index_type, minval)); 2277169689Skan index = expand_normal (index_expr); 2278132718Skan do_pending_stack_adjust (); 2279132718Skan 2280132718Skan mode = TYPE_MODE (index_type); 2281169689Skan expr = expand_normal (range); 2282132718Skan emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1, 2283132718Skan default_label); 2284132718Skan 2285132718Skan index = convert_to_mode (word_mode, index, 0); 2286132718Skan index = expand_binop (word_mode, ashl_optab, const1_rtx, 2287132718Skan index, NULL_RTX, 1, OPTAB_WIDEN); 2288132718Skan 2289132718Skan for (i = 0; i < count; i++) 2290132718Skan { 2291132718Skan expr = immed_double_const (test[i].lo, test[i].hi, word_mode); 2292132718Skan expr = expand_binop (word_mode, and_optab, index, expr, 2293132718Skan NULL_RTX, 1, OPTAB_WIDEN); 2294132718Skan emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX, 2295132718Skan word_mode, 1, test[i].label); 2296132718Skan } 2297132718Skan 2298132718Skan emit_jump (default_label); 2299132718Skan} 2300132718Skan 2301169689Skan#ifndef HAVE_casesi 2302169689Skan#define HAVE_casesi 0 2303169689Skan#endif 2304169689Skan 2305169689Skan#ifndef HAVE_tablejump 2306169689Skan#define HAVE_tablejump 0 2307169689Skan#endif 2308169689Skan 2309169689Skan/* Terminate a case (Pascal/Ada) or switch (C) statement 231018334Speter in which ORIG_INDEX is the expression to be tested. 231196263Sobrien If ORIG_TYPE is not NULL, it is the original ORIG_INDEX 231296263Sobrien type as given in the source before any compiler conversions. 231318334Speter Generate the code to test it and jump to the right place. */ 231418334Speter 231518334Spetervoid 2316169689Skanexpand_case (tree exp) 231718334Speter{ 231890075Sobrien tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE; 231918334Speter rtx default_label = 0; 2320169689Skan struct case_node *n; 2321132718Skan unsigned int count, uniq; 232218334Speter rtx index; 232318334Speter rtx table_label; 232418334Speter int ncases; 232518334Speter rtx *labelvec; 2326169689Skan int i, fail; 2327132718Skan rtx before_case, end, lab; 232818334Speter 2329169689Skan tree vec = SWITCH_LABELS (exp); 2330169689Skan tree orig_type = TREE_TYPE (exp); 2331169689Skan tree index_expr = SWITCH_COND (exp); 2332169689Skan tree index_type = TREE_TYPE (index_expr); 2333169689Skan int unsignedp = TYPE_UNSIGNED (index_type); 233490075Sobrien 2335169689Skan /* The insn after which the case dispatch should finally 2336169689Skan be emitted. Zero for a dummy. */ 2337169689Skan rtx start; 233818334Speter 2339169689Skan /* A list of case labels; it is first built as a list and it may then 2340169689Skan be rearranged into a nearly balanced binary tree. */ 2341169689Skan struct case_node *case_list = 0; 2342169689Skan 2343169689Skan /* Label to jump to if no case matches. */ 2344169689Skan tree default_label_decl; 2345169689Skan 2346169689Skan /* The switch body is lowered in gimplify.c, we should never have 2347169689Skan switches with a non-NULL SWITCH_BODY here. */ 2348169689Skan gcc_assert (!SWITCH_BODY (exp)); 2349169689Skan gcc_assert (SWITCH_LABELS (exp)); 2350169689Skan 235118334Speter do_pending_stack_adjust (); 235218334Speter 235318334Speter /* An ERROR_MARK occurs for various reasons including invalid data type. */ 235418334Speter if (index_type != error_mark_node) 235518334Speter { 2356169689Skan tree elt; 2357169689Skan bitmap label_bitmap; 235818334Speter 2359169689Skan /* cleanup_tree_cfg removes all SWITCH_EXPR with their index 2360169689Skan expressions being INTEGER_CST. */ 2361169689Skan gcc_assert (TREE_CODE (index_expr) != INTEGER_CST); 2362117395Skan 2363169689Skan /* The default case is at the end of TREE_VEC. */ 2364169689Skan elt = TREE_VEC_ELT (vec, TREE_VEC_LENGTH (vec) - 1); 2365169689Skan gcc_assert (!CASE_HIGH (elt)); 2366169689Skan gcc_assert (!CASE_LOW (elt)); 2367169689Skan default_label_decl = CASE_LABEL (elt); 2368169689Skan 2369169689Skan for (i = TREE_VEC_LENGTH (vec) - 1; --i >= 0; ) 237018334Speter { 2371169689Skan tree low, high; 2372169689Skan elt = TREE_VEC_ELT (vec, i); 2373169689Skan 2374169689Skan low = CASE_LOW (elt); 2375169689Skan gcc_assert (low); 2376169689Skan high = CASE_HIGH (elt); 2377169689Skan 2378169689Skan /* Discard empty ranges. */ 2379169689Skan if (high && INT_CST_LT (high, low)) 2380169689Skan continue; 2381169689Skan 2382169689Skan case_list = add_case_node (case_list, index_type, low, high, 2383169689Skan CASE_LABEL (elt)); 238418334Speter } 238518334Speter 238618334Speter 2387169689Skan before_case = start = get_last_insn (); 2388169689Skan default_label = label_rtx (default_label_decl); 238950397Sobrien 2390169689Skan /* Get upper and lower bounds of case values. */ 239118334Speter 2392132718Skan uniq = 0; 239318334Speter count = 0; 2394169689Skan label_bitmap = BITMAP_ALLOC (NULL); 2395169689Skan for (n = case_list; n; n = n->right) 239618334Speter { 239718334Speter /* Count the elements and track the largest and smallest 239818334Speter of them (treating them as signed even if they are not). */ 239918334Speter if (count++ == 0) 240018334Speter { 240118334Speter minval = n->low; 240218334Speter maxval = n->high; 240318334Speter } 240418334Speter else 240518334Speter { 240618334Speter if (INT_CST_LT (n->low, minval)) 240718334Speter minval = n->low; 240818334Speter if (INT_CST_LT (maxval, n->high)) 240918334Speter maxval = n->high; 241018334Speter } 241118334Speter /* A range counts double, since it requires two compares. */ 241218334Speter if (! tree_int_cst_equal (n->low, n->high)) 241318334Speter count++; 2414132718Skan 2415169689Skan /* If we have not seen this label yet, then increase the 2416169689Skan number of unique case node targets seen. */ 2417132718Skan lab = label_rtx (n->code_label); 2418169689Skan if (!bitmap_bit_p (label_bitmap, CODE_LABEL_NUMBER (lab))) 2419169689Skan { 2420169689Skan bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab)); 2421169689Skan uniq++; 2422169689Skan } 242318334Speter } 242418334Speter 2425169689Skan BITMAP_FREE (label_bitmap); 242618334Speter 2427169689Skan /* cleanup_tree_cfg removes all SWITCH_EXPR with a single 2428169689Skan destination, such as one with a default case only. However, 2429169689Skan it doesn't remove cases that are out of range for the switch 2430169689Skan type, so we may still get a zero here. */ 243118334Speter if (count == 0) 243218334Speter { 243318334Speter emit_jump (default_label); 2434169689Skan return; 243518334Speter } 243618334Speter 2437169689Skan /* Compute span of values. */ 2438169689Skan range = fold_build2 (MINUS_EXPR, index_type, maxval, minval); 2439169689Skan 2440132718Skan /* Try implementing this switch statement by a short sequence of 2441132718Skan bit-wise comparisons. However, we let the binary-tree case 2442132718Skan below handle constant index expressions. */ 2443169689Skan if (CASE_USE_BIT_TESTS 2444169689Skan && ! TREE_CONSTANT (index_expr) 2445169689Skan && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0 2446169689Skan && compare_tree_int (range, 0) > 0 2447169689Skan && lshift_cheap_p () 2448169689Skan && ((uniq == 1 && count >= 3) 2449169689Skan || (uniq == 2 && count >= 5) 2450169689Skan || (uniq == 3 && count >= 6))) 2451132718Skan { 2452132718Skan /* Optimize the case where all the case values fit in a 2453132718Skan word without having to subtract MINVAL. In this case, 2454132718Skan we can optimize away the subtraction. */ 2455132718Skan if (compare_tree_int (minval, 0) > 0 2456132718Skan && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0) 2457132718Skan { 2458169689Skan minval = build_int_cst (index_type, 0); 2459132718Skan range = maxval; 2460132718Skan } 2461132718Skan emit_case_bit_tests (index_type, index_expr, minval, range, 2462169689Skan case_list, default_label); 2463132718Skan } 2464132718Skan 246518334Speter /* If range of values is much bigger than number of values, 246618334Speter make a sequence of conditional branches instead of a dispatch. 246718334Speter If the switch-index is a constant, do it this way 246818334Speter because we can optimize it. */ 246918334Speter 247090075Sobrien else if (count < case_values_threshold () 2471132718Skan || compare_tree_int (range, 2472132718Skan (optimize_size ? 3 : 10) * count) > 0 247390075Sobrien /* RANGE may be signed, and really large ranges will show up 247490075Sobrien as negative numbers. */ 247590075Sobrien || compare_tree_int (range, 0) < 0 247650397Sobrien#ifndef ASM_OUTPUT_ADDR_DIFF_ELT 247750397Sobrien || flag_pic 247850397Sobrien#endif 2479169689Skan || !flag_jump_tables 2480169689Skan || TREE_CONSTANT (index_expr) 2481169689Skan /* If neither casesi or tablejump is available, we can 2482169689Skan only go this way. */ 2483169689Skan || (!HAVE_casesi && !HAVE_tablejump)) 248418334Speter { 2485169689Skan index = expand_normal (index_expr); 248618334Speter 248718334Speter /* If the index is a short or char that we do not have 248818334Speter an insn to handle comparisons directly, convert it to 248918334Speter a full integer now, rather than letting each comparison 249018334Speter generate the conversion. */ 249118334Speter 249218334Speter if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT 249390075Sobrien && ! have_insn_for (COMPARE, GET_MODE (index))) 249418334Speter { 249518334Speter enum machine_mode wider_mode; 249618334Speter for (wider_mode = GET_MODE (index); wider_mode != VOIDmode; 249718334Speter wider_mode = GET_MODE_WIDER_MODE (wider_mode)) 249890075Sobrien if (have_insn_for (COMPARE, wider_mode)) 249918334Speter { 250018334Speter index = convert_to_mode (wider_mode, index, unsignedp); 250118334Speter break; 250218334Speter } 250318334Speter } 250418334Speter 250518334Speter do_pending_stack_adjust (); 250618334Speter 2507169689Skan if (MEM_P (index)) 250818334Speter index = copy_to_reg (index); 250918334Speter 2510169689Skan /* We generate a binary decision tree to select the 2511169689Skan appropriate target code. This is done as follows: 251218334Speter 2513169689Skan The list of cases is rearranged into a binary tree, 2514169689Skan nearly optimal assuming equal probability for each case. 251518334Speter 2516169689Skan The tree is transformed into RTL, eliminating 2517169689Skan redundant test conditions at the same time. 251818334Speter 2519169689Skan If program flow could reach the end of the 2520169689Skan decision tree an unconditional jump to the 2521169689Skan default code is emitted. */ 252218334Speter 2523169689Skan use_cost_table 2524169689Skan = (TREE_CODE (orig_type) != ENUMERAL_TYPE 2525169689Skan && estimate_case_costs (case_list)); 2526169689Skan balance_case_nodes (&case_list, NULL); 2527169689Skan emit_case_nodes (index, case_list, default_label, index_type); 2528169689Skan emit_jump (default_label); 252918334Speter } 253018334Speter else 253118334Speter { 2532132718Skan table_label = gen_label_rtx (); 253390075Sobrien if (! try_casesi (index_type, index_expr, minval, range, 253490075Sobrien table_label, default_label)) 253518334Speter { 2536169689Skan bool ok; 253718334Speter 2538117395Skan /* Index jumptables from zero for suitable values of 253990075Sobrien minval to avoid a subtraction. */ 2540117395Skan if (! optimize_size 2541117395Skan && compare_tree_int (minval, 0) > 0 2542117395Skan && compare_tree_int (minval, 3) < 0) 2543117395Skan { 2544169689Skan minval = build_int_cst (index_type, 0); 2545117395Skan range = maxval; 2546117395Skan } 254718334Speter 2548169689Skan ok = try_tablejump (index_type, index_expr, minval, range, 2549169689Skan table_label, default_label); 2550169689Skan gcc_assert (ok); 255118334Speter } 2552117395Skan 255318334Speter /* Get table of labels to jump to, in order of case index. */ 255418334Speter 255590075Sobrien ncases = tree_low_cst (range, 0) + 1; 2556132718Skan labelvec = alloca (ncases * sizeof (rtx)); 2557132718Skan memset (labelvec, 0, ncases * sizeof (rtx)); 255818334Speter 2559169689Skan for (n = case_list; n; n = n->right) 256018334Speter { 256190075Sobrien /* Compute the low and high bounds relative to the minimum 256290075Sobrien value since that should fit in a HOST_WIDE_INT while the 256390075Sobrien actual values may not. */ 256490075Sobrien HOST_WIDE_INT i_low 2565169689Skan = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 2566169689Skan n->low, minval), 1); 256790075Sobrien HOST_WIDE_INT i_high 2568169689Skan = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 2569169689Skan n->high, minval), 1); 257090075Sobrien HOST_WIDE_INT i; 257118334Speter 257290075Sobrien for (i = i_low; i <= i_high; i ++) 257390075Sobrien labelvec[i] 257490075Sobrien = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label)); 257518334Speter } 257618334Speter 257718334Speter /* Fill in the gaps with the default. */ 257818334Speter for (i = 0; i < ncases; i++) 257918334Speter if (labelvec[i] == 0) 258050397Sobrien labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label); 258118334Speter 2582132718Skan /* Output the table. */ 258318334Speter emit_label (table_label); 258418334Speter 258550397Sobrien if (CASE_VECTOR_PC_RELATIVE || flag_pic) 258650397Sobrien emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE, 258750397Sobrien gen_rtx_LABEL_REF (Pmode, table_label), 258850397Sobrien gen_rtvec_v (ncases, labelvec), 258990075Sobrien const0_rtx, const0_rtx)); 259018334Speter else 259150397Sobrien emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE, 259250397Sobrien gen_rtvec_v (ncases, labelvec))); 259318334Speter 2594169689Skan /* Record no drop-through after the table. */ 259518334Speter emit_barrier (); 259618334Speter } 259718334Speter 259890075Sobrien before_case = NEXT_INSN (before_case); 259990075Sobrien end = get_last_insn (); 2600169689Skan fail = squeeze_notes (&before_case, &end); 2601169689Skan gcc_assert (!fail); 2602169689Skan reorder_insns (before_case, end, start); 260318334Speter } 260418334Speter 260518334Speter free_temp_slots (); 260618334Speter} 260718334Speter 2608169689Skan/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */ 260918334Speter 261018334Speterstatic void 2611169689Skando_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label, 2612169689Skan int unsignedp) 261318334Speter{ 2614169689Skan do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode, 2615169689Skan NULL_RTX, NULL_RTX, label); 261618334Speter} 261718334Speter 261818334Speter/* Not all case values are encountered equally. This function 261918334Speter uses a heuristic to weight case labels, in cases where that 262018334Speter looks like a reasonable thing to do. 262118334Speter 262218334Speter Right now, all we try to guess is text, and we establish the 262318334Speter following weights: 262418334Speter 262518334Speter chars above space: 16 262618334Speter digits: 16 262718334Speter default: 12 262818334Speter space, punct: 8 262918334Speter tab: 4 263018334Speter newline: 2 263118334Speter other "\" chars: 1 263218334Speter remaining chars: 0 263318334Speter 263418334Speter If we find any cases in the switch that are not either -1 or in the range 263518334Speter of valid ASCII characters, or are control characters other than those 263618334Speter commonly used with "\", don't treat this switch scanning text. 263718334Speter 263818334Speter Return 1 if these nodes are suitable for cost estimation, otherwise 263918334Speter return 0. */ 264018334Speter 264118334Speterstatic int 2642132718Skanestimate_case_costs (case_node_ptr node) 264318334Speter{ 264490075Sobrien tree min_ascii = integer_minus_one_node; 2645169689Skan tree max_ascii = build_int_cst (TREE_TYPE (node->high), 127); 264618334Speter case_node_ptr n; 264718334Speter int i; 264818334Speter 264918334Speter /* If we haven't already made the cost table, make it now. Note that the 265018334Speter lower bound of the table is -1, not zero. */ 265118334Speter 265290075Sobrien if (! cost_table_initialized) 265318334Speter { 265490075Sobrien cost_table_initialized = 1; 265518334Speter 265618334Speter for (i = 0; i < 128; i++) 265718334Speter { 265850397Sobrien if (ISALNUM (i)) 265990075Sobrien COST_TABLE (i) = 16; 266050397Sobrien else if (ISPUNCT (i)) 266190075Sobrien COST_TABLE (i) = 8; 266250397Sobrien else if (ISCNTRL (i)) 266390075Sobrien COST_TABLE (i) = -1; 266418334Speter } 266518334Speter 266690075Sobrien COST_TABLE (' ') = 8; 266790075Sobrien COST_TABLE ('\t') = 4; 266890075Sobrien COST_TABLE ('\0') = 4; 266990075Sobrien COST_TABLE ('\n') = 2; 267090075Sobrien COST_TABLE ('\f') = 1; 267190075Sobrien COST_TABLE ('\v') = 1; 267290075Sobrien COST_TABLE ('\b') = 1; 267318334Speter } 267418334Speter 267518334Speter /* See if all the case expressions look like text. It is text if the 267618334Speter constant is >= -1 and the highest constant is <= 127. Do all comparisons 267718334Speter as signed arithmetic since we don't want to ever access cost_table with a 267818334Speter value less than -1. Also check that none of the constants in a range 267918334Speter are strange control characters. */ 268018334Speter 268118334Speter for (n = node; n; n = n->right) 268218334Speter { 268318334Speter if ((INT_CST_LT (n->low, min_ascii)) || INT_CST_LT (max_ascii, n->high)) 268418334Speter return 0; 268518334Speter 268690075Sobrien for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low); 268790075Sobrien i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++) 268890075Sobrien if (COST_TABLE (i) < 0) 268918334Speter return 0; 269018334Speter } 269118334Speter 269218334Speter /* All interesting values are within the range of interesting 269318334Speter ASCII characters. */ 269418334Speter return 1; 269518334Speter} 269618334Speter 269718334Speter/* Take an ordered list of case nodes 269818334Speter and transform them into a near optimal binary tree, 269918334Speter on the assumption that any target code selection value is as 270018334Speter likely as any other. 270118334Speter 270218334Speter The transformation is performed by splitting the ordered 270318334Speter list into two equal sections plus a pivot. The parts are 270418334Speter then attached to the pivot as left and right branches. Each 270550397Sobrien branch is then transformed recursively. */ 270618334Speter 270718334Speterstatic void 2708132718Skanbalance_case_nodes (case_node_ptr *head, case_node_ptr parent) 270918334Speter{ 271090075Sobrien case_node_ptr np; 271118334Speter 271218334Speter np = *head; 271318334Speter if (np) 271418334Speter { 271518334Speter int cost = 0; 271618334Speter int i = 0; 271718334Speter int ranges = 0; 271890075Sobrien case_node_ptr *npp; 271918334Speter case_node_ptr left; 272018334Speter 272118334Speter /* Count the number of entries on branch. Also count the ranges. */ 272218334Speter 272318334Speter while (np) 272418334Speter { 272518334Speter if (!tree_int_cst_equal (np->low, np->high)) 272618334Speter { 272718334Speter ranges++; 272818334Speter if (use_cost_table) 272990075Sobrien cost += COST_TABLE (TREE_INT_CST_LOW (np->high)); 273018334Speter } 273118334Speter 273218334Speter if (use_cost_table) 273390075Sobrien cost += COST_TABLE (TREE_INT_CST_LOW (np->low)); 273418334Speter 273518334Speter i++; 273618334Speter np = np->right; 273718334Speter } 273818334Speter 273918334Speter if (i > 2) 274018334Speter { 274118334Speter /* Split this list if it is long enough for that to help. */ 274218334Speter npp = head; 274318334Speter left = *npp; 274418334Speter if (use_cost_table) 274518334Speter { 274618334Speter /* Find the place in the list that bisects the list's total cost, 274718334Speter Here I gets half the total cost. */ 274818334Speter int n_moved = 0; 274918334Speter i = (cost + 1) / 2; 275018334Speter while (1) 275118334Speter { 275218334Speter /* Skip nodes while their cost does not reach that amount. */ 275318334Speter if (!tree_int_cst_equal ((*npp)->low, (*npp)->high)) 275490075Sobrien i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high)); 275590075Sobrien i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low)); 275618334Speter if (i <= 0) 275718334Speter break; 275818334Speter npp = &(*npp)->right; 275918334Speter n_moved += 1; 276018334Speter } 276118334Speter if (n_moved == 0) 276218334Speter { 276318334Speter /* Leave this branch lopsided, but optimize left-hand 276418334Speter side and fill in `parent' fields for right-hand side. */ 276518334Speter np = *head; 276618334Speter np->parent = parent; 276718334Speter balance_case_nodes (&np->left, np); 276818334Speter for (; np->right; np = np->right) 276918334Speter np->right->parent = np; 277018334Speter return; 277118334Speter } 277218334Speter } 277318334Speter /* If there are just three nodes, split at the middle one. */ 277418334Speter else if (i == 3) 277518334Speter npp = &(*npp)->right; 277618334Speter else 277718334Speter { 277818334Speter /* Find the place in the list that bisects the list's total cost, 277918334Speter where ranges count as 2. 278018334Speter Here I gets half the total cost. */ 278118334Speter i = (i + ranges + 1) / 2; 278218334Speter while (1) 278318334Speter { 278418334Speter /* Skip nodes while their cost does not reach that amount. */ 278518334Speter if (!tree_int_cst_equal ((*npp)->low, (*npp)->high)) 278618334Speter i--; 278718334Speter i--; 278818334Speter if (i <= 0) 278918334Speter break; 279018334Speter npp = &(*npp)->right; 279118334Speter } 279218334Speter } 279318334Speter *head = np = *npp; 279418334Speter *npp = 0; 279518334Speter np->parent = parent; 279618334Speter np->left = left; 279718334Speter 279818334Speter /* Optimize each of the two split parts. */ 279918334Speter balance_case_nodes (&np->left, np); 280018334Speter balance_case_nodes (&np->right, np); 280118334Speter } 280218334Speter else 280318334Speter { 280418334Speter /* Else leave this branch as one level, 280518334Speter but fill in `parent' fields. */ 280618334Speter np = *head; 280718334Speter np->parent = parent; 280818334Speter for (; np->right; np = np->right) 280918334Speter np->right->parent = np; 281018334Speter } 281118334Speter } 281218334Speter} 281318334Speter 281418334Speter/* Search the parent sections of the case node tree 281518334Speter to see if a test for the lower bound of NODE would be redundant. 281618334Speter INDEX_TYPE is the type of the index expression. 281718334Speter 281818334Speter The instructions to generate the case decision tree are 281918334Speter output in the same order as nodes are processed so it is 282018334Speter known that if a parent node checks the range of the current 282118334Speter node minus one that the current node is bounded at its lower 282218334Speter span. Thus the test would be redundant. */ 282318334Speter 282418334Speterstatic int 2825132718Skannode_has_low_bound (case_node_ptr node, tree index_type) 282618334Speter{ 282718334Speter tree low_minus_one; 282818334Speter case_node_ptr pnode; 282918334Speter 283018334Speter /* If the lower bound of this node is the lowest value in the index type, 283118334Speter we need not test it. */ 283218334Speter 283318334Speter if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type))) 283418334Speter return 1; 283518334Speter 283618334Speter /* If this node has a left branch, the value at the left must be less 283718334Speter than that at this node, so it cannot be bounded at the bottom and 283818334Speter we need not bother testing any further. */ 283918334Speter 284018334Speter if (node->left) 284118334Speter return 0; 284218334Speter 2843169689Skan low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), 2844169689Skan node->low, 2845169689Skan build_int_cst (TREE_TYPE (node->low), 1)); 284618334Speter 284718334Speter /* If the subtraction above overflowed, we can't verify anything. 284818334Speter Otherwise, look for a parent that tests our value - 1. */ 284918334Speter 285018334Speter if (! tree_int_cst_lt (low_minus_one, node->low)) 285118334Speter return 0; 285218334Speter 285318334Speter for (pnode = node->parent; pnode; pnode = pnode->parent) 285418334Speter if (tree_int_cst_equal (low_minus_one, pnode->high)) 285518334Speter return 1; 285618334Speter 285718334Speter return 0; 285818334Speter} 285918334Speter 286018334Speter/* Search the parent sections of the case node tree 286118334Speter to see if a test for the upper bound of NODE would be redundant. 286218334Speter INDEX_TYPE is the type of the index expression. 286318334Speter 286418334Speter The instructions to generate the case decision tree are 286518334Speter output in the same order as nodes are processed so it is 286618334Speter known that if a parent node checks the range of the current 286718334Speter node plus one that the current node is bounded at its upper 286818334Speter span. Thus the test would be redundant. */ 286918334Speter 287018334Speterstatic int 2871132718Skannode_has_high_bound (case_node_ptr node, tree index_type) 287218334Speter{ 287318334Speter tree high_plus_one; 287418334Speter case_node_ptr pnode; 287518334Speter 287650397Sobrien /* If there is no upper bound, obviously no test is needed. */ 287750397Sobrien 287850397Sobrien if (TYPE_MAX_VALUE (index_type) == NULL) 287950397Sobrien return 1; 288050397Sobrien 288118334Speter /* If the upper bound of this node is the highest value in the type 288218334Speter of the index expression, we need not test against it. */ 288318334Speter 288418334Speter if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type))) 288518334Speter return 1; 288618334Speter 288718334Speter /* If this node has a right branch, the value at the right must be greater 288818334Speter than that at this node, so it cannot be bounded at the top and 288918334Speter we need not bother testing any further. */ 289018334Speter 289118334Speter if (node->right) 289218334Speter return 0; 289318334Speter 2894169689Skan high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), 2895169689Skan node->high, 2896169689Skan build_int_cst (TREE_TYPE (node->high), 1)); 289718334Speter 289818334Speter /* If the addition above overflowed, we can't verify anything. 289918334Speter Otherwise, look for a parent that tests our value + 1. */ 290018334Speter 290118334Speter if (! tree_int_cst_lt (node->high, high_plus_one)) 290218334Speter return 0; 290318334Speter 290418334Speter for (pnode = node->parent; pnode; pnode = pnode->parent) 290518334Speter if (tree_int_cst_equal (high_plus_one, pnode->low)) 290618334Speter return 1; 290718334Speter 290818334Speter return 0; 290918334Speter} 291018334Speter 291118334Speter/* Search the parent sections of the 291218334Speter case node tree to see if both tests for the upper and lower 291318334Speter bounds of NODE would be redundant. */ 291418334Speter 291518334Speterstatic int 2916132718Skannode_is_bounded (case_node_ptr node, tree index_type) 291718334Speter{ 291818334Speter return (node_has_low_bound (node, index_type) 291918334Speter && node_has_high_bound (node, index_type)); 292018334Speter} 292118334Speter 292218334Speter/* Emit step-by-step code to select a case for the value of INDEX. 292318334Speter The thus generated decision tree follows the form of the 292418334Speter case-node binary tree NODE, whose nodes represent test conditions. 292518334Speter INDEX_TYPE is the type of the index of the switch. 292618334Speter 292718334Speter Care is taken to prune redundant tests from the decision tree 292818334Speter by detecting any boundary conditions already checked by 292918334Speter emitted rtx. (See node_has_high_bound, node_has_low_bound 293018334Speter and node_is_bounded, above.) 293118334Speter 293218334Speter Where the test conditions can be shown to be redundant we emit 293318334Speter an unconditional jump to the target code. As a further 293418334Speter optimization, the subordinates of a tree node are examined to 293518334Speter check for bounded nodes. In this case conditional and/or 293618334Speter unconditional jumps as a result of the boundary check for the 293718334Speter current node are arranged to target the subordinates associated 293850397Sobrien code for out of bound conditions on the current node. 293918334Speter 294018334Speter We can assume that when control reaches the code generated here, 294118334Speter the index value has already been compared with the parents 294218334Speter of this node, and determined to be on the same side of each parent 294318334Speter as this node is. Thus, if this node tests for the value 51, 294418334Speter and a parent tested for 52, we don't need to consider 294518334Speter the possibility of a value greater than 51. If another parent 294618334Speter tests for the value 50, then this node need not test anything. */ 294718334Speter 294818334Speterstatic void 2949132718Skanemit_case_nodes (rtx index, case_node_ptr node, rtx default_label, 2950132718Skan tree index_type) 295118334Speter{ 295218334Speter /* If INDEX has an unsigned type, we must make unsigned branches. */ 2953169689Skan int unsignedp = TYPE_UNSIGNED (index_type); 295418334Speter enum machine_mode mode = GET_MODE (index); 295590075Sobrien enum machine_mode imode = TYPE_MODE (index_type); 295618334Speter 2957169689Skan /* Handle indices detected as constant during RTL expansion. */ 2958169689Skan if (mode == VOIDmode) 2959169689Skan mode = imode; 2960169689Skan 296118334Speter /* See if our parents have already tested everything for us. 296218334Speter If they have, emit an unconditional jump for this node. */ 296318334Speter if (node_is_bounded (node, index_type)) 296418334Speter emit_jump (label_rtx (node->code_label)); 296518334Speter 296618334Speter else if (tree_int_cst_equal (node->low, node->high)) 296718334Speter { 296818334Speter /* Node is single valued. First see if the index expression matches 296950397Sobrien this node and then check our children, if any. */ 297018334Speter 2971169689Skan do_jump_if_equal (mode, index, 297290075Sobrien convert_modes (mode, imode, 2973169689Skan expand_normal (node->low), 297490075Sobrien unsignedp), 297518334Speter label_rtx (node->code_label), unsignedp); 297618334Speter 297718334Speter if (node->right != 0 && node->left != 0) 297818334Speter { 297918334Speter /* This node has children on both sides. 298018334Speter Dispatch to one side or the other 298118334Speter by comparing the index value with this node's value. 298218334Speter If one subtree is bounded, check that one first, 298318334Speter so we can avoid real branches in the tree. */ 298418334Speter 298518334Speter if (node_is_bounded (node->right, index_type)) 298618334Speter { 298790075Sobrien emit_cmp_and_jump_insns (index, 298890075Sobrien convert_modes 298990075Sobrien (mode, imode, 2990169689Skan expand_normal (node->high), 299190075Sobrien unsignedp), 299290075Sobrien GT, NULL_RTX, mode, unsignedp, 299390075Sobrien label_rtx (node->right->code_label)); 299418334Speter emit_case_nodes (index, node->left, default_label, index_type); 299518334Speter } 299618334Speter 299718334Speter else if (node_is_bounded (node->left, index_type)) 299818334Speter { 299990075Sobrien emit_cmp_and_jump_insns (index, 300090075Sobrien convert_modes 300190075Sobrien (mode, imode, 3002169689Skan expand_normal (node->high), 300390075Sobrien unsignedp), 300490075Sobrien LT, NULL_RTX, mode, unsignedp, 300552284Sobrien label_rtx (node->left->code_label)); 300618334Speter emit_case_nodes (index, node->right, default_label, index_type); 300718334Speter } 300818334Speter 3009169689Skan /* If both children are single-valued cases with no 3010169689Skan children, finish up all the work. This way, we can save 3011169689Skan one ordered comparison. */ 3012169689Skan else if (tree_int_cst_equal (node->right->low, node->right->high) 3013169689Skan && node->right->left == 0 3014169689Skan && node->right->right == 0 3015169689Skan && tree_int_cst_equal (node->left->low, node->left->high) 3016169689Skan && node->left->left == 0 3017169689Skan && node->left->right == 0) 3018169689Skan { 3019169689Skan /* Neither node is bounded. First distinguish the two sides; 3020169689Skan then emit the code for one side at a time. */ 3021169689Skan 3022169689Skan /* See if the value matches what the right hand side 3023169689Skan wants. */ 3024169689Skan do_jump_if_equal (mode, index, 3025169689Skan convert_modes (mode, imode, 3026169689Skan expand_normal (node->right->low), 3027169689Skan unsignedp), 3028169689Skan label_rtx (node->right->code_label), 3029169689Skan unsignedp); 3030169689Skan 3031169689Skan /* See if the value matches what the left hand side 3032169689Skan wants. */ 3033169689Skan do_jump_if_equal (mode, index, 3034169689Skan convert_modes (mode, imode, 3035169689Skan expand_normal (node->left->low), 3036169689Skan unsignedp), 3037169689Skan label_rtx (node->left->code_label), 3038169689Skan unsignedp); 3039169689Skan } 3040169689Skan 304118334Speter else 304218334Speter { 304318334Speter /* Neither node is bounded. First distinguish the two sides; 304418334Speter then emit the code for one side at a time. */ 304518334Speter 304690075Sobrien tree test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE); 304718334Speter 304818334Speter /* See if the value is on the right. */ 304990075Sobrien emit_cmp_and_jump_insns (index, 305090075Sobrien convert_modes 305190075Sobrien (mode, imode, 3052169689Skan expand_normal (node->high), 305390075Sobrien unsignedp), 305490075Sobrien GT, NULL_RTX, mode, unsignedp, 305552284Sobrien label_rtx (test_label)); 305618334Speter 305718334Speter /* Value must be on the left. 305818334Speter Handle the left-hand subtree. */ 305918334Speter emit_case_nodes (index, node->left, default_label, index_type); 306018334Speter /* If left-hand subtree does nothing, 306118334Speter go to default. */ 3062169689Skan emit_jump (default_label); 306318334Speter 306418334Speter /* Code branches here for the right-hand subtree. */ 306518334Speter expand_label (test_label); 306618334Speter emit_case_nodes (index, node->right, default_label, index_type); 306718334Speter } 306818334Speter } 306918334Speter 307018334Speter else if (node->right != 0 && node->left == 0) 307118334Speter { 3072169689Skan /* Here we have a right child but no left so we issue a conditional 307318334Speter branch to default and process the right child. 307418334Speter 3075169689Skan Omit the conditional branch to default if the right child 3076169689Skan does not have any children and is single valued; it would 3077169689Skan cost too much space to save so little time. */ 307818334Speter 307918334Speter if (node->right->right || node->right->left 308018334Speter || !tree_int_cst_equal (node->right->low, node->right->high)) 308118334Speter { 308218334Speter if (!node_has_low_bound (node, index_type)) 308318334Speter { 308490075Sobrien emit_cmp_and_jump_insns (index, 308590075Sobrien convert_modes 308690075Sobrien (mode, imode, 3087169689Skan expand_normal (node->high), 308890075Sobrien unsignedp), 308990075Sobrien LT, NULL_RTX, mode, unsignedp, 309052284Sobrien default_label); 309118334Speter } 309218334Speter 309318334Speter emit_case_nodes (index, node->right, default_label, index_type); 309418334Speter } 309518334Speter else 309618334Speter /* We cannot process node->right normally 309718334Speter since we haven't ruled out the numbers less than 309818334Speter this node's value. So handle node->right explicitly. */ 3099169689Skan do_jump_if_equal (mode, index, 310090075Sobrien convert_modes 310190075Sobrien (mode, imode, 3102169689Skan expand_normal (node->right->low), 310390075Sobrien unsignedp), 310418334Speter label_rtx (node->right->code_label), unsignedp); 310518334Speter } 310618334Speter 310718334Speter else if (node->right == 0 && node->left != 0) 310818334Speter { 310918334Speter /* Just one subtree, on the left. */ 311090075Sobrien if (node->left->left || node->left->right 311118334Speter || !tree_int_cst_equal (node->left->low, node->left->high)) 311218334Speter { 311318334Speter if (!node_has_high_bound (node, index_type)) 311418334Speter { 311590075Sobrien emit_cmp_and_jump_insns (index, 311690075Sobrien convert_modes 311790075Sobrien (mode, imode, 3118169689Skan expand_normal (node->high), 311990075Sobrien unsignedp), 312090075Sobrien GT, NULL_RTX, mode, unsignedp, 312152284Sobrien default_label); 312218334Speter } 312318334Speter 312418334Speter emit_case_nodes (index, node->left, default_label, index_type); 312518334Speter } 312618334Speter else 312718334Speter /* We cannot process node->left normally 312818334Speter since we haven't ruled out the numbers less than 312918334Speter this node's value. So handle node->left explicitly. */ 3130169689Skan do_jump_if_equal (mode, index, 313190075Sobrien convert_modes 313290075Sobrien (mode, imode, 3133169689Skan expand_normal (node->left->low), 313490075Sobrien unsignedp), 313518334Speter label_rtx (node->left->code_label), unsignedp); 313618334Speter } 313718334Speter } 313818334Speter else 313918334Speter { 314018334Speter /* Node is a range. These cases are very similar to those for a single 314118334Speter value, except that we do not start by testing whether this node 314218334Speter is the one to branch to. */ 314318334Speter 314418334Speter if (node->right != 0 && node->left != 0) 314518334Speter { 314618334Speter /* Node has subtrees on both sides. 314718334Speter If the right-hand subtree is bounded, 314818334Speter test for it first, since we can go straight there. 314918334Speter Otherwise, we need to make a branch in the control structure, 315018334Speter then handle the two subtrees. */ 315118334Speter tree test_label = 0; 315218334Speter 315318334Speter if (node_is_bounded (node->right, index_type)) 315418334Speter /* Right hand node is fully bounded so we can eliminate any 315518334Speter testing and branch directly to the target code. */ 315690075Sobrien emit_cmp_and_jump_insns (index, 315790075Sobrien convert_modes 315890075Sobrien (mode, imode, 3159169689Skan expand_normal (node->high), 316090075Sobrien unsignedp), 316190075Sobrien GT, NULL_RTX, mode, unsignedp, 316252284Sobrien label_rtx (node->right->code_label)); 316318334Speter else 316418334Speter { 316518334Speter /* Right hand node requires testing. 316618334Speter Branch to a label where we will handle it later. */ 316718334Speter 316818334Speter test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE); 316990075Sobrien emit_cmp_and_jump_insns (index, 317090075Sobrien convert_modes 317190075Sobrien (mode, imode, 3172169689Skan expand_normal (node->high), 317390075Sobrien unsignedp), 317490075Sobrien GT, NULL_RTX, mode, unsignedp, 317552284Sobrien label_rtx (test_label)); 317618334Speter } 317718334Speter 317818334Speter /* Value belongs to this node or to the left-hand subtree. */ 317918334Speter 318090075Sobrien emit_cmp_and_jump_insns (index, 318190075Sobrien convert_modes 318290075Sobrien (mode, imode, 3183169689Skan expand_normal (node->low), 318490075Sobrien unsignedp), 318590075Sobrien GE, NULL_RTX, mode, unsignedp, 318652284Sobrien label_rtx (node->code_label)); 318718334Speter 318818334Speter /* Handle the left-hand subtree. */ 318918334Speter emit_case_nodes (index, node->left, default_label, index_type); 319018334Speter 319118334Speter /* If right node had to be handled later, do that now. */ 319218334Speter 319318334Speter if (test_label) 319418334Speter { 319518334Speter /* If the left-hand subtree fell through, 319618334Speter don't let it fall into the right-hand subtree. */ 3197169689Skan emit_jump (default_label); 319818334Speter 319918334Speter expand_label (test_label); 320018334Speter emit_case_nodes (index, node->right, default_label, index_type); 320118334Speter } 320218334Speter } 320318334Speter 320418334Speter else if (node->right != 0 && node->left == 0) 320518334Speter { 320618334Speter /* Deal with values to the left of this node, 320718334Speter if they are possible. */ 320818334Speter if (!node_has_low_bound (node, index_type)) 320918334Speter { 321090075Sobrien emit_cmp_and_jump_insns (index, 321190075Sobrien convert_modes 321290075Sobrien (mode, imode, 3213169689Skan expand_normal (node->low), 321490075Sobrien unsignedp), 321590075Sobrien LT, NULL_RTX, mode, unsignedp, 321652284Sobrien default_label); 321718334Speter } 321818334Speter 321918334Speter /* Value belongs to this node or to the right-hand subtree. */ 322018334Speter 322190075Sobrien emit_cmp_and_jump_insns (index, 322290075Sobrien convert_modes 322390075Sobrien (mode, imode, 3224169689Skan expand_normal (node->high), 322590075Sobrien unsignedp), 322690075Sobrien LE, NULL_RTX, mode, unsignedp, 322752284Sobrien label_rtx (node->code_label)); 322818334Speter 322918334Speter emit_case_nodes (index, node->right, default_label, index_type); 323018334Speter } 323118334Speter 323218334Speter else if (node->right == 0 && node->left != 0) 323318334Speter { 323418334Speter /* Deal with values to the right of this node, 323518334Speter if they are possible. */ 323618334Speter if (!node_has_high_bound (node, index_type)) 323718334Speter { 323890075Sobrien emit_cmp_and_jump_insns (index, 323990075Sobrien convert_modes 324090075Sobrien (mode, imode, 3241169689Skan expand_normal (node->high), 324290075Sobrien unsignedp), 324390075Sobrien GT, NULL_RTX, mode, unsignedp, 324452284Sobrien default_label); 324518334Speter } 324618334Speter 324718334Speter /* Value belongs to this node or to the left-hand subtree. */ 324818334Speter 324990075Sobrien emit_cmp_and_jump_insns (index, 325090075Sobrien convert_modes 325190075Sobrien (mode, imode, 3252169689Skan expand_normal (node->low), 325390075Sobrien unsignedp), 325490075Sobrien GE, NULL_RTX, mode, unsignedp, 325552284Sobrien label_rtx (node->code_label)); 325618334Speter 325718334Speter emit_case_nodes (index, node->left, default_label, index_type); 325818334Speter } 325918334Speter 326018334Speter else 326118334Speter { 326218334Speter /* Node has no children so we check low and high bounds to remove 326318334Speter redundant tests. Only one of the bounds can exist, 326418334Speter since otherwise this node is bounded--a case tested already. */ 326590075Sobrien int high_bound = node_has_high_bound (node, index_type); 326690075Sobrien int low_bound = node_has_low_bound (node, index_type); 326718334Speter 326890075Sobrien if (!high_bound && low_bound) 326918334Speter { 327090075Sobrien emit_cmp_and_jump_insns (index, 327190075Sobrien convert_modes 327290075Sobrien (mode, imode, 3273169689Skan expand_normal (node->high), 327490075Sobrien unsignedp), 327590075Sobrien GT, NULL_RTX, mode, unsignedp, 327652284Sobrien default_label); 327718334Speter } 327818334Speter 327990075Sobrien else if (!low_bound && high_bound) 328018334Speter { 328190075Sobrien emit_cmp_and_jump_insns (index, 328290075Sobrien convert_modes 328390075Sobrien (mode, imode, 3284169689Skan expand_normal (node->low), 328590075Sobrien unsignedp), 328690075Sobrien LT, NULL_RTX, mode, unsignedp, 328752284Sobrien default_label); 328818334Speter } 328990075Sobrien else if (!low_bound && !high_bound) 329090075Sobrien { 329190075Sobrien /* Widen LOW and HIGH to the same width as INDEX. */ 3292169689Skan tree type = lang_hooks.types.type_for_mode (mode, unsignedp); 329390075Sobrien tree low = build1 (CONVERT_EXPR, type, node->low); 329490075Sobrien tree high = build1 (CONVERT_EXPR, type, node->high); 329590075Sobrien rtx low_rtx, new_index, new_bound; 329618334Speter 329790075Sobrien /* Instead of doing two branches, emit one unsigned branch for 329890075Sobrien (index-low) > (high-low). */ 3299169689Skan low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL); 330090075Sobrien new_index = expand_simple_binop (mode, MINUS, index, low_rtx, 330190075Sobrien NULL_RTX, unsignedp, 330290075Sobrien OPTAB_WIDEN); 3303169689Skan new_bound = expand_expr (fold_build2 (MINUS_EXPR, type, 3304169689Skan high, low), 3305169689Skan NULL_RTX, mode, EXPAND_NORMAL); 3306117395Skan 330790075Sobrien emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX, 330890075Sobrien mode, 1, default_label); 330990075Sobrien } 331090075Sobrien 331118334Speter emit_jump (label_rtx (node->code_label)); 331218334Speter } 331318334Speter } 331418334Speter} 3315