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 (); 139169689Skan SET_DECL_RTL (label, r); 140169689Skan if (FORCED_LABEL (label) || DECL_NONLOCAL (label)) 141169689Skan LABEL_PRESERVE_P (r) = 1; 142169689Skan } 14318334Speter 14490075Sobrien return DECL_RTL (label); 14518334Speter} 14618334Speter 147132718Skan/* As above, but also put it on the forced-reference list of the 148132718Skan function that contains it. */ 149132718Skanrtx 150132718Skanforce_label_rtx (tree label) 151132718Skan{ 152132718Skan rtx ref = label_rtx (label); 153132718Skan tree function = decl_function_context (label); 154132718Skan struct function *p; 15590075Sobrien 156169689Skan gcc_assert (function); 157132718Skan 158169689Skan if (function != current_function_decl) 159132718Skan p = find_function_data (function); 160132718Skan else 161132718Skan p = cfun; 162132718Skan 163132718Skan p->expr->x_forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref, 164132718Skan p->expr->x_forced_labels); 165132718Skan return ref; 166132718Skan} 167132718Skan 16818334Speter/* Add an unconditional jump to LABEL as the next sequential instruction. */ 16918334Speter 17018334Spetervoid 171132718Skanemit_jump (rtx label) 17218334Speter{ 17318334Speter do_pending_stack_adjust (); 17418334Speter emit_jump_insn (gen_jump (label)); 17518334Speter emit_barrier (); 17618334Speter} 17718334Speter 17818334Speter/* Emit code to jump to the address 17918334Speter specified by the pointer expression EXP. */ 18018334Speter 18118334Spetervoid 182132718Skanexpand_computed_goto (tree exp) 18318334Speter{ 184169689Skan rtx x = expand_normal (exp); 18518334Speter 186132718Skan x = convert_memory_address (Pmode, x); 18718334Speter 188169689Skan do_pending_stack_adjust (); 189169689Skan emit_indirect_jump (x); 19018334Speter} 19118334Speter 19218334Speter/* Handle goto statements and the labels that they can go to. */ 19318334Speter 19418334Speter/* Specify the location in the RTL code of a label LABEL, 19518334Speter which is a LABEL_DECL tree node. 19618334Speter 19718334Speter This is used for the kind of label that the user can jump to with a 19818334Speter goto statement, and for alternatives of a switch or case statement. 19918334Speter RTL labels generated for loops and conditionals don't go through here; 20018334Speter they are generated directly at the RTL level, by other functions below. 20118334Speter 20218334Speter Note that this has nothing to do with defining label *names*. 20318334Speter Languages vary in how they do that and what that even means. */ 20418334Speter 20518334Spetervoid 206132718Skanexpand_label (tree label) 20718334Speter{ 208169689Skan rtx label_r = label_rtx (label); 20918334Speter 21018334Speter do_pending_stack_adjust (); 211169689Skan emit_label (label_r); 21218334Speter if (DECL_NAME (label)) 21318334Speter LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label)); 21418334Speter 215169689Skan if (DECL_NONLOCAL (label)) 21618334Speter { 217169689Skan expand_nl_goto_receiver (); 218169689Skan nonlocal_goto_handler_labels 219169689Skan = gen_rtx_EXPR_LIST (VOIDmode, label_r, 220169689Skan nonlocal_goto_handler_labels); 22118334Speter } 22218334Speter 223169689Skan if (FORCED_LABEL (label)) 224169689Skan forced_labels = gen_rtx_EXPR_LIST (VOIDmode, label_r, forced_labels); 22518334Speter 226169689Skan if (DECL_NONLOCAL (label) || FORCED_LABEL (label)) 227169689Skan maybe_set_first_label_num (label_r); 22818334Speter} 22918334Speter 23018334Speter/* Generate RTL code for a `goto' statement with target label LABEL. 23118334Speter LABEL should be a LABEL_DECL tree node that was or will later be 23218334Speter defined with `expand_label'. */ 23318334Speter 23418334Spetervoid 235132718Skanexpand_goto (tree label) 23618334Speter{ 237169689Skan#ifdef ENABLE_CHECKING 238169689Skan /* Check for a nonlocal goto to a containing function. Should have 239169689Skan gotten translated to __builtin_nonlocal_goto. */ 240169689Skan tree context = decl_function_context (label); 241169689Skan gcc_assert (!context || context == current_function_decl); 24218334Speter#endif 243132718Skan 244169689Skan emit_jump (label_rtx (label)); 24518334Speter} 24618334Speter 24752284Sobrien/* Return the number of times character C occurs in string S. */ 24852284Sobrienstatic int 249132718Skann_occurrences (int c, const char *s) 25052284Sobrien{ 25152284Sobrien int n = 0; 25252284Sobrien while (*s) 25352284Sobrien n += (*s++ == c); 25452284Sobrien return n; 25552284Sobrien} 25652284Sobrien 25718334Speter/* Generate RTL for an asm statement (explicit assembler code). 258110611Skan STRING is a STRING_CST node containing the assembler code text, 259110611Skan or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the 260110611Skan insn is volatile; don't optimize it. */ 261117395Skan 262169689Skanstatic void 263132718Skanexpand_asm (tree string, int vol) 26418334Speter{ 265110611Skan rtx body; 26618334Speter 267110611Skan if (TREE_CODE (string) == ADDR_EXPR) 268110611Skan string = TREE_OPERAND (string, 0); 269110611Skan 270169689Skan body = gen_rtx_ASM_INPUT (VOIDmode, 271169689Skan ggc_strdup (TREE_STRING_POINTER (string))); 272110611Skan 273110611Skan MEM_VOLATILE_P (body) = vol; 274110611Skan 275110611Skan emit_insn (body); 27618334Speter} 27718334Speter 27890075Sobrien/* Parse the output constraint pointed to by *CONSTRAINT_P. It is the 27990075Sobrien OPERAND_NUMth output operand, indexed from zero. There are NINPUTS 28090075Sobrien inputs and NOUTPUTS outputs to this extended-asm. Upon return, 28190075Sobrien *ALLOWS_MEM will be TRUE iff the constraint allows the use of a 28290075Sobrien memory operand. Similarly, *ALLOWS_REG will be TRUE iff the 28390075Sobrien constraint allows the use of a register operand. And, *IS_INOUT 28490075Sobrien will be true if the operand is read-write, i.e., if it is used as 28590075Sobrien an input as well as an output. If *CONSTRAINT_P is not in 28690075Sobrien canonical form, it will be made canonical. (Note that `+' will be 287132718Skan replaced with `=' as part of this process.) 28890075Sobrien 28990075Sobrien Returns TRUE if all went well; FALSE if an error occurred. */ 29090075Sobrien 29190075Sobrienbool 292132718Skanparse_output_constraint (const char **constraint_p, int operand_num, 293132718Skan int ninputs, int noutputs, bool *allows_mem, 294132718Skan bool *allows_reg, bool *is_inout) 29590075Sobrien{ 29690075Sobrien const char *constraint = *constraint_p; 29790075Sobrien const char *p; 29890075Sobrien 29990075Sobrien /* Assume the constraint doesn't allow the use of either a register 30090075Sobrien or memory. */ 30190075Sobrien *allows_mem = false; 30290075Sobrien *allows_reg = false; 30390075Sobrien 30490075Sobrien /* Allow the `=' or `+' to not be at the beginning of the string, 30590075Sobrien since it wasn't explicitly documented that way, and there is a 30690075Sobrien large body of code that puts it last. Swap the character to 30790075Sobrien the front, so as not to uglify any place else. */ 30890075Sobrien p = strchr (constraint, '='); 30990075Sobrien if (!p) 31090075Sobrien p = strchr (constraint, '+'); 31190075Sobrien 31290075Sobrien /* If the string doesn't contain an `=', issue an error 31390075Sobrien message. */ 31490075Sobrien if (!p) 31590075Sobrien { 316169689Skan error ("output operand constraint lacks %<=%>"); 31790075Sobrien return false; 31890075Sobrien } 31990075Sobrien 32090075Sobrien /* If the constraint begins with `+', then the operand is both read 32190075Sobrien from and written to. */ 32290075Sobrien *is_inout = (*p == '+'); 32390075Sobrien 32490075Sobrien /* Canonicalize the output constraint so that it begins with `='. */ 325169689Skan if (p != constraint || *is_inout) 32690075Sobrien { 32790075Sobrien char *buf; 32890075Sobrien size_t c_len = strlen (constraint); 32990075Sobrien 33090075Sobrien if (p != constraint) 331169689Skan warning (0, "output constraint %qc for operand %d " 332169689Skan "is not at the beginning", 33390075Sobrien *p, operand_num); 33490075Sobrien 33590075Sobrien /* Make a copy of the constraint. */ 33690075Sobrien buf = alloca (c_len + 1); 33790075Sobrien strcpy (buf, constraint); 33890075Sobrien /* Swap the first character and the `=' or `+'. */ 33990075Sobrien buf[p - constraint] = buf[0]; 34090075Sobrien /* Make sure the first character is an `='. (Until we do this, 34190075Sobrien it might be a `+'.) */ 34290075Sobrien buf[0] = '='; 34390075Sobrien /* Replace the constraint with the canonicalized string. */ 34490075Sobrien *constraint_p = ggc_alloc_string (buf, c_len); 34590075Sobrien constraint = *constraint_p; 34690075Sobrien } 34790075Sobrien 34890075Sobrien /* Loop through the constraint string. */ 349132718Skan for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p)) 35090075Sobrien switch (*p) 35190075Sobrien { 35290075Sobrien case '+': 35390075Sobrien case '=': 354169689Skan error ("operand constraint contains incorrectly positioned " 355169689Skan "%<+%> or %<=%>"); 35690075Sobrien return false; 357117395Skan 35890075Sobrien case '%': 35990075Sobrien if (operand_num + 1 == ninputs + noutputs) 36090075Sobrien { 361169689Skan error ("%<%%%> constraint used with last operand"); 36290075Sobrien return false; 36390075Sobrien } 36490075Sobrien break; 36590075Sobrien 36690075Sobrien case 'V': case 'm': case 'o': 36790075Sobrien *allows_mem = true; 36890075Sobrien break; 36990075Sobrien 37090075Sobrien case '?': case '!': case '*': case '&': case '#': 37190075Sobrien case 'E': case 'F': case 'G': case 'H': 37290075Sobrien case 's': case 'i': case 'n': 37390075Sobrien case 'I': case 'J': case 'K': case 'L': case 'M': 37490075Sobrien case 'N': case 'O': case 'P': case ',': 37590075Sobrien break; 37690075Sobrien 37790075Sobrien case '0': case '1': case '2': case '3': case '4': 37890075Sobrien case '5': case '6': case '7': case '8': case '9': 37990075Sobrien case '[': 38090075Sobrien error ("matching constraint not valid in output operand"); 38190075Sobrien return false; 38290075Sobrien 38390075Sobrien case '<': case '>': 38490075Sobrien /* ??? Before flow, auto inc/dec insns are not supposed to exist, 38590075Sobrien excepting those that expand_call created. So match memory 38690075Sobrien and hope. */ 38790075Sobrien *allows_mem = true; 38890075Sobrien break; 38990075Sobrien 39090075Sobrien case 'g': case 'X': 39190075Sobrien *allows_reg = true; 39290075Sobrien *allows_mem = true; 39390075Sobrien break; 394117395Skan 39590075Sobrien case 'p': case 'r': 39690075Sobrien *allows_reg = true; 39790075Sobrien break; 39890075Sobrien 39990075Sobrien default: 40090075Sobrien if (!ISALPHA (*p)) 40190075Sobrien break; 402132718Skan if (REG_CLASS_FROM_CONSTRAINT (*p, p) != NO_REGS) 40390075Sobrien *allows_reg = true; 404132718Skan#ifdef EXTRA_CONSTRAINT_STR 405132718Skan else if (EXTRA_ADDRESS_CONSTRAINT (*p, p)) 406117395Skan *allows_reg = true; 407132718Skan else if (EXTRA_MEMORY_CONSTRAINT (*p, p)) 408117395Skan *allows_mem = true; 40990075Sobrien else 41090075Sobrien { 41190075Sobrien /* Otherwise we can't assume anything about the nature of 41290075Sobrien the constraint except that it isn't purely registers. 41390075Sobrien Treat it like "g" and hope for the best. */ 41490075Sobrien *allows_reg = true; 41590075Sobrien *allows_mem = true; 41690075Sobrien } 41790075Sobrien#endif 41890075Sobrien break; 41990075Sobrien } 42090075Sobrien 42190075Sobrien return true; 42290075Sobrien} 42390075Sobrien 42490075Sobrien/* Similar, but for input constraints. */ 42590075Sobrien 426132718Skanbool 427132718Skanparse_input_constraint (const char **constraint_p, int input_num, 428132718Skan int ninputs, int noutputs, int ninout, 429132718Skan const char * const * constraints, 430132718Skan bool *allows_mem, bool *allows_reg) 43190075Sobrien{ 43290075Sobrien const char *constraint = *constraint_p; 43390075Sobrien const char *orig_constraint = constraint; 43490075Sobrien size_t c_len = strlen (constraint); 43590075Sobrien size_t j; 436132718Skan bool saw_match = false; 43790075Sobrien 43890075Sobrien /* Assume the constraint doesn't allow the use of either 43990075Sobrien a register or memory. */ 44090075Sobrien *allows_mem = false; 44190075Sobrien *allows_reg = false; 44290075Sobrien 44390075Sobrien /* Make sure constraint has neither `=', `+', nor '&'. */ 44490075Sobrien 445132718Skan for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j)) 44690075Sobrien switch (constraint[j]) 44790075Sobrien { 44890075Sobrien case '+': case '=': case '&': 44990075Sobrien if (constraint == orig_constraint) 45090075Sobrien { 451169689Skan error ("input operand constraint contains %qc", constraint[j]); 45290075Sobrien return false; 45390075Sobrien } 45490075Sobrien break; 45590075Sobrien 45690075Sobrien case '%': 45790075Sobrien if (constraint == orig_constraint 45890075Sobrien && input_num + 1 == ninputs - ninout) 45990075Sobrien { 460169689Skan error ("%<%%%> constraint used with last operand"); 46190075Sobrien return false; 46290075Sobrien } 46390075Sobrien break; 46490075Sobrien 46590075Sobrien case 'V': case 'm': case 'o': 46690075Sobrien *allows_mem = true; 46790075Sobrien break; 46890075Sobrien 46990075Sobrien case '<': case '>': 47090075Sobrien case '?': case '!': case '*': case '#': 47190075Sobrien case 'E': case 'F': case 'G': case 'H': 47290075Sobrien case 's': case 'i': case 'n': 47390075Sobrien case 'I': case 'J': case 'K': case 'L': case 'M': 47490075Sobrien case 'N': case 'O': case 'P': case ',': 47590075Sobrien break; 47690075Sobrien 47790075Sobrien /* Whether or not a numeric constraint allows a register is 47890075Sobrien decided by the matching constraint, and so there is no need 47990075Sobrien to do anything special with them. We must handle them in 48090075Sobrien the default case, so that we don't unnecessarily force 48190075Sobrien operands to memory. */ 48290075Sobrien case '0': case '1': case '2': case '3': case '4': 48390075Sobrien case '5': case '6': case '7': case '8': case '9': 48490075Sobrien { 48590075Sobrien char *end; 48690075Sobrien unsigned long match; 48790075Sobrien 488132718Skan saw_match = true; 489132718Skan 49090075Sobrien match = strtoul (constraint + j, &end, 10); 49190075Sobrien if (match >= (unsigned long) noutputs) 49290075Sobrien { 49390075Sobrien error ("matching constraint references invalid operand number"); 49490075Sobrien return false; 49590075Sobrien } 49690075Sobrien 49790075Sobrien /* Try and find the real constraint for this dup. Only do this 49890075Sobrien if the matching constraint is the only alternative. */ 49990075Sobrien if (*end == '\0' 50090075Sobrien && (j == 0 || (j == 1 && constraint[0] == '%'))) 50190075Sobrien { 50290075Sobrien constraint = constraints[match]; 50390075Sobrien *constraint_p = constraint; 50490075Sobrien c_len = strlen (constraint); 50590075Sobrien j = 0; 506132718Skan /* ??? At the end of the loop, we will skip the first part of 507132718Skan the matched constraint. This assumes not only that the 508132718Skan other constraint is an output constraint, but also that 509132718Skan the '=' or '+' come first. */ 51090075Sobrien break; 51190075Sobrien } 51290075Sobrien else 51390075Sobrien j = end - constraint; 514132718Skan /* Anticipate increment at end of loop. */ 515132718Skan j--; 51690075Sobrien } 51790075Sobrien /* Fall through. */ 51890075Sobrien 51990075Sobrien case 'p': case 'r': 52090075Sobrien *allows_reg = true; 52190075Sobrien break; 52290075Sobrien 52390075Sobrien case 'g': case 'X': 52490075Sobrien *allows_reg = true; 52590075Sobrien *allows_mem = true; 52690075Sobrien break; 52790075Sobrien 52890075Sobrien default: 52990075Sobrien if (! ISALPHA (constraint[j])) 53090075Sobrien { 531169689Skan error ("invalid punctuation %qc in constraint", constraint[j]); 53290075Sobrien return false; 53390075Sobrien } 534132718Skan if (REG_CLASS_FROM_CONSTRAINT (constraint[j], constraint + j) 535132718Skan != NO_REGS) 53690075Sobrien *allows_reg = true; 537132718Skan#ifdef EXTRA_CONSTRAINT_STR 538132718Skan else if (EXTRA_ADDRESS_CONSTRAINT (constraint[j], constraint + j)) 539117395Skan *allows_reg = true; 540132718Skan else if (EXTRA_MEMORY_CONSTRAINT (constraint[j], constraint + j)) 541117395Skan *allows_mem = true; 54290075Sobrien else 54390075Sobrien { 54490075Sobrien /* Otherwise we can't assume anything about the nature of 54590075Sobrien the constraint except that it isn't purely registers. 54690075Sobrien Treat it like "g" and hope for the best. */ 54790075Sobrien *allows_reg = true; 54890075Sobrien *allows_mem = true; 54990075Sobrien } 55090075Sobrien#endif 55190075Sobrien break; 55290075Sobrien } 55390075Sobrien 554132718Skan if (saw_match && !*allows_reg) 555169689Skan warning (0, "matching constraint does not allow a register"); 556132718Skan 55790075Sobrien return true; 55890075Sobrien} 55990075Sobrien 560169689Skan/* Return DECL iff there's an overlap between *REGS and DECL, where DECL 561169689Skan can be an asm-declared register. Called via walk_tree. */ 562169689Skan 563169689Skanstatic tree 564169689Skandecl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED, 565169689Skan void *data) 566169689Skan{ 567169689Skan tree decl = *declp; 568169689Skan const HARD_REG_SET *regs = data; 569169689Skan 570169689Skan if (TREE_CODE (decl) == VAR_DECL) 571169689Skan { 572169689Skan if (DECL_HARD_REGISTER (decl) 573169689Skan && REG_P (DECL_RTL (decl)) 574169689Skan && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER) 575169689Skan { 576169689Skan rtx reg = DECL_RTL (decl); 577169689Skan unsigned int regno; 578169689Skan 579169689Skan for (regno = REGNO (reg); 580169689Skan regno < (REGNO (reg) 581169689Skan + hard_regno_nregs[REGNO (reg)][GET_MODE (reg)]); 582169689Skan regno++) 583169689Skan if (TEST_HARD_REG_BIT (*regs, regno)) 584169689Skan return decl; 585169689Skan } 586169689Skan walk_subtrees = 0; 587169689Skan } 588169689Skan else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL) 589169689Skan walk_subtrees = 0; 590169689Skan return NULL_TREE; 591169689Skan} 592169689Skan 593169689Skan/* If there is an overlap between *REGS and DECL, return the first overlap 594169689Skan found. */ 595169689Skantree 596169689Skantree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs) 597169689Skan{ 598169689Skan return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL); 599169689Skan} 600169689Skan 601117395Skan/* Check for overlap between registers marked in CLOBBERED_REGS and 602169689Skan anything inappropriate in T. Emit error and return the register 603169689Skan variable definition for error, NULL_TREE for ok. */ 604117395Skan 605117395Skanstatic bool 606169689Skantree_conflicts_with_clobbers_p (tree t, HARD_REG_SET *clobbered_regs) 607117395Skan{ 608117395Skan /* Conflicts between asm-declared register variables and the clobber 609117395Skan list are not allowed. */ 610169689Skan tree overlap = tree_overlaps_hard_reg_set (t, clobbered_regs); 611169689Skan 612169689Skan if (overlap) 613117395Skan { 614169689Skan error ("asm-specifier for variable %qs conflicts with asm clobber list", 615169689Skan IDENTIFIER_POINTER (DECL_NAME (overlap))); 616117395Skan 617169689Skan /* Reset registerness to stop multiple errors emitted for a single 618169689Skan variable. */ 619169689Skan DECL_REGISTER (overlap) = 0; 620169689Skan return true; 621169689Skan } 622117395Skan 623117395Skan return false; 624117395Skan} 625117395Skan 62618334Speter/* Generate RTL for an asm statement with arguments. 62718334Speter STRING is the instruction template. 62818334Speter OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs. 62918334Speter Each output or input has an expression in the TREE_VALUE and 63090075Sobrien and a tree list in TREE_PURPOSE which in turn contains a constraint 631117395Skan name in TREE_VALUE (or NULL_TREE) and a constraint string 63290075Sobrien in TREE_PURPOSE. 63318334Speter CLOBBERS is a list of STRING_CST nodes each naming a hard register 63418334Speter that is clobbered by this insn. 63518334Speter 63618334Speter Not all kinds of lvalue that may appear in OUTPUTS can be stored directly. 63718334Speter Some elements of OUTPUTS may be replaced with trees representing temporary 63818334Speter values. The caller should copy those temporary values to the originally 63918334Speter specified lvalues. 64018334Speter 64118334Speter VOL nonzero means the insn is volatile; don't optimize it. */ 64218334Speter 643169689Skanstatic void 644132718Skanexpand_asm_operands (tree string, tree outputs, tree inputs, 645132718Skan tree clobbers, int vol, location_t locus) 64618334Speter{ 64790075Sobrien rtvec argvec, constraintvec; 64818334Speter rtx body; 64918334Speter int ninputs = list_length (inputs); 65018334Speter int noutputs = list_length (outputs); 65190075Sobrien int ninout; 65218334Speter int nclobbers; 653117395Skan HARD_REG_SET clobbered_regs; 654117395Skan int clobber_conflict_found = 0; 65518334Speter tree tail; 656132718Skan tree t; 65790075Sobrien int i; 65818334Speter /* Vector of RTX's of evaluated output operands. */ 659132718Skan rtx *output_rtx = alloca (noutputs * sizeof (rtx)); 660132718Skan int *inout_opnum = alloca (noutputs * sizeof (int)); 661132718Skan rtx *real_output_rtx = alloca (noutputs * sizeof (rtx)); 66250397Sobrien enum machine_mode *inout_mode 663132718Skan = alloca (noutputs * sizeof (enum machine_mode)); 66490075Sobrien const char **constraints 665132718Skan = alloca ((noutputs + ninputs) * sizeof (const char *)); 66690075Sobrien int old_generating_concat_p = generating_concat_p; 66718334Speter 66850397Sobrien /* An ASM with no outputs needs to be treated as volatile, for now. */ 66950397Sobrien if (noutputs == 0) 67050397Sobrien vol = 1; 67150397Sobrien 67290075Sobrien if (! check_operand_nalternatives (outputs, inputs)) 67390075Sobrien return; 67418334Speter 675132718Skan string = resolve_asm_operand_names (string, outputs, inputs); 67690075Sobrien 677132718Skan /* Collect constraints. */ 678132718Skan i = 0; 679132718Skan for (t = outputs; t ; t = TREE_CHAIN (t), i++) 680132718Skan constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t))); 681132718Skan for (t = inputs; t ; t = TREE_CHAIN (t), i++) 682132718Skan constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t))); 68390075Sobrien 68490075Sobrien /* Sometimes we wish to automatically clobber registers across an asm. 68590075Sobrien Case in point is when the i386 backend moved from cc0 to a hard reg -- 68690075Sobrien maintaining source-level compatibility means automatically clobbering 68790075Sobrien the flags register. */ 688169689Skan clobbers = targetm.md_asm_clobbers (outputs, inputs, clobbers); 68990075Sobrien 69018334Speter /* Count the number of meaningful clobbered registers, ignoring what 69118334Speter we would ignore later. */ 69218334Speter nclobbers = 0; 693117395Skan CLEAR_HARD_REG_SET (clobbered_regs); 69418334Speter for (tail = clobbers; tail; tail = TREE_CHAIN (tail)) 69518334Speter { 696169689Skan const char *regname; 69790075Sobrien 698169689Skan if (TREE_VALUE (tail) == error_mark_node) 699169689Skan return; 700169689Skan regname = TREE_STRING_POINTER (TREE_VALUE (tail)); 701169689Skan 70218334Speter i = decode_reg_name (regname); 70318334Speter if (i >= 0 || i == -4) 70418334Speter ++nclobbers; 70518334Speter else if (i == -2) 706169689Skan error ("unknown register name %qs in %<asm%>", regname); 707117395Skan 708117395Skan /* Mark clobbered registers. */ 709117395Skan if (i >= 0) 710132718Skan { 711169689Skan /* Clobbering the PIC register is an error. */ 712132718Skan if (i == (int) PIC_OFFSET_TABLE_REGNUM) 713132718Skan { 714169689Skan error ("PIC register %qs clobbered in %<asm%>", regname); 715132718Skan return; 716132718Skan } 717132718Skan 718132718Skan SET_HARD_REG_BIT (clobbered_regs, i); 719132718Skan } 72018334Speter } 72118334Speter 72290075Sobrien /* First pass over inputs and outputs checks validity and sets 72390075Sobrien mark_addressable if needed. */ 72452284Sobrien 72590075Sobrien ninout = 0; 72618334Speter for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 72718334Speter { 72818334Speter tree val = TREE_VALUE (tail); 72918334Speter tree type = TREE_TYPE (val); 73090075Sobrien const char *constraint; 73190075Sobrien bool is_inout; 73290075Sobrien bool allows_reg; 73390075Sobrien bool allows_mem; 73418334Speter 73518334Speter /* If there's an erroneous arg, emit no insn. */ 73690075Sobrien if (type == error_mark_node) 73718334Speter return; 73818334Speter 73990075Sobrien /* Try to parse the output constraint. If that fails, there's 74090075Sobrien no point in going further. */ 74190075Sobrien constraint = constraints[i]; 74290075Sobrien if (!parse_output_constraint (&constraint, i, ninputs, noutputs, 74390075Sobrien &allows_mem, &allows_reg, &is_inout)) 74490075Sobrien return; 74518334Speter 74690075Sobrien if (! allows_reg 74790075Sobrien && (allows_mem 74890075Sobrien || is_inout 74990075Sobrien || (DECL_P (val) 750169689Skan && REG_P (DECL_RTL (val)) 75190075Sobrien && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))) 752169689Skan lang_hooks.mark_addressable (val); 75352284Sobrien 75490075Sobrien if (is_inout) 75590075Sobrien ninout++; 75690075Sobrien } 75752284Sobrien 75890075Sobrien ninputs += ninout; 75990075Sobrien if (ninputs + noutputs > MAX_RECOG_OPERANDS) 76090075Sobrien { 761169689Skan error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS); 76290075Sobrien return; 76390075Sobrien } 76452284Sobrien 76590075Sobrien for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail)) 76690075Sobrien { 76790075Sobrien bool allows_reg, allows_mem; 76890075Sobrien const char *constraint; 76952284Sobrien 77090075Sobrien /* If there's an erroneous arg, emit no insn, because the ASM_INPUT 77190075Sobrien would get VOIDmode and that could cause a crash in reload. */ 77290075Sobrien if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node) 77390075Sobrien return; 77452284Sobrien 77590075Sobrien constraint = constraints[i + noutputs]; 77690075Sobrien if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout, 77790075Sobrien constraints, &allows_mem, &allows_reg)) 77890075Sobrien return; 77952284Sobrien 78090075Sobrien if (! allows_reg && allows_mem) 781169689Skan lang_hooks.mark_addressable (TREE_VALUE (tail)); 78290075Sobrien } 78350397Sobrien 78490075Sobrien /* Second pass evaluates arguments. */ 78518334Speter 78690075Sobrien ninout = 0; 78790075Sobrien for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 78890075Sobrien { 78990075Sobrien tree val = TREE_VALUE (tail); 79090075Sobrien tree type = TREE_TYPE (val); 79190075Sobrien bool is_inout; 79290075Sobrien bool allows_reg; 79390075Sobrien bool allows_mem; 794117395Skan rtx op; 795169689Skan bool ok; 79650397Sobrien 797169689Skan ok = parse_output_constraint (&constraints[i], i, ninputs, 79890075Sobrien noutputs, &allows_mem, &allows_reg, 799169689Skan &is_inout); 800169689Skan gcc_assert (ok); 80152284Sobrien 80218334Speter /* If an output operand is not a decl or indirect ref and our constraint 80318334Speter allows a register, make a temporary to act as an intermediate. 80418334Speter Make the asm insn write into that, then our caller will copy it to 80518334Speter the real output operand. Likewise for promoted variables. */ 80618334Speter 80790075Sobrien generating_concat_p = 0; 80890075Sobrien 80952284Sobrien real_output_rtx[i] = NULL_RTX; 81052284Sobrien if ((TREE_CODE (val) == INDIRECT_REF 81152284Sobrien && allows_mem) 81290075Sobrien || (DECL_P (val) 813169689Skan && (allows_mem || REG_P (DECL_RTL (val))) 814169689Skan && ! (REG_P (DECL_RTL (val)) 81518334Speter && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))) 81650397Sobrien || ! allows_reg 81752284Sobrien || is_inout) 81818334Speter { 819117395Skan op = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE); 820169689Skan if (MEM_P (op)) 821117395Skan op = validize_mem (op); 82218334Speter 823169689Skan if (! allows_reg && !MEM_P (op)) 82418334Speter error ("output number %d not directly addressable", i); 825169689Skan if ((! allows_mem && MEM_P (op)) 826117395Skan || GET_CODE (op) == CONCAT) 82752284Sobrien { 828169689Skan real_output_rtx[i] = op; 829117395Skan op = gen_reg_rtx (GET_MODE (op)); 83052284Sobrien if (is_inout) 831117395Skan emit_move_insn (op, real_output_rtx[i]); 83252284Sobrien } 83318334Speter } 83418334Speter else 83518334Speter { 836117395Skan op = assign_temp (type, 0, 0, 1); 837117395Skan op = validize_mem (op); 838117395Skan TREE_VALUE (tail) = make_tree (type, op); 83918334Speter } 840117395Skan output_rtx[i] = op; 84150397Sobrien 84290075Sobrien generating_concat_p = old_generating_concat_p; 84390075Sobrien 84452284Sobrien if (is_inout) 84550397Sobrien { 84690075Sobrien inout_mode[ninout] = TYPE_MODE (type); 84750397Sobrien inout_opnum[ninout++] = i; 84850397Sobrien } 849117395Skan 850169689Skan if (tree_conflicts_with_clobbers_p (val, &clobbered_regs)) 851117395Skan clobber_conflict_found = 1; 85218334Speter } 85318334Speter 85490075Sobrien /* Make vectors for the expression-rtx, constraint strings, 85590075Sobrien and named operands. */ 85618334Speter 85718334Speter argvec = rtvec_alloc (ninputs); 85890075Sobrien constraintvec = rtvec_alloc (ninputs); 85918334Speter 86090075Sobrien body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode 86190075Sobrien : GET_MODE (output_rtx[0])), 862169689Skan ggc_strdup (TREE_STRING_POINTER (string)), 86390075Sobrien empty_string, 0, argvec, constraintvec, 864169689Skan locus); 86550397Sobrien 86618334Speter MEM_VOLATILE_P (body) = vol; 86718334Speter 86818334Speter /* Eval the inputs and put them into ARGVEC. 86918334Speter Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */ 87018334Speter 87190075Sobrien for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i) 87218334Speter { 87390075Sobrien bool allows_reg, allows_mem; 87490075Sobrien const char *constraint; 87590075Sobrien tree val, type; 87652284Sobrien rtx op; 877169689Skan bool ok; 87818334Speter 87990075Sobrien constraint = constraints[i + noutputs]; 880169689Skan ok = parse_input_constraint (&constraint, i, ninputs, noutputs, ninout, 881169689Skan constraints, &allows_mem, &allows_reg); 882169689Skan gcc_assert (ok); 88352284Sobrien 88490075Sobrien generating_concat_p = 0; 88518334Speter 88690075Sobrien val = TREE_VALUE (tail); 88790075Sobrien type = TREE_TYPE (val); 888169689Skan /* EXPAND_INITIALIZER will not generate code for valid initializer 889169689Skan constants, but will still generate code for other types of operand. 890169689Skan This is the behavior we want for constant constraints. */ 891117395Skan op = expand_expr (val, NULL_RTX, VOIDmode, 892169689Skan allows_reg ? EXPAND_NORMAL 893169689Skan : allows_mem ? EXPAND_MEMORY 894169689Skan : EXPAND_INITIALIZER); 89518334Speter 89690075Sobrien /* Never pass a CONCAT to an ASM. */ 89790075Sobrien if (GET_CODE (op) == CONCAT) 89890075Sobrien op = force_reg (GET_MODE (op), op); 899169689Skan else if (MEM_P (op)) 900117395Skan op = validize_mem (op); 90152284Sobrien 90252284Sobrien if (asm_operand_ok (op, constraint) <= 0) 90318334Speter { 904169689Skan if (allows_reg && TYPE_MODE (type) != BLKmode) 90590075Sobrien op = force_reg (TYPE_MODE (type), op); 90652284Sobrien else if (!allows_mem) 907169689Skan warning (0, "asm operand %d probably doesn%'t match constraints", 90890075Sobrien i + noutputs); 909169689Skan else if (MEM_P (op)) 91052284Sobrien { 911117395Skan /* We won't recognize either volatile memory or memory 912117395Skan with a queued address as available a memory_operand 913117395Skan at this point. Ignore it: clearly this *is* a memory. */ 91452284Sobrien } 915117395Skan else 916117395Skan { 917169689Skan warning (0, "use of memory input without lvalue in " 918132718Skan "asm operand %d is deprecated", i + noutputs); 91990075Sobrien 920117395Skan if (CONSTANT_P (op)) 921117395Skan { 922132718Skan rtx mem = force_const_mem (TYPE_MODE (type), op); 923132718Skan if (mem) 924132718Skan op = validize_mem (mem); 925132718Skan else 926132718Skan op = force_reg (TYPE_MODE (type), op); 927117395Skan } 928169689Skan if (REG_P (op) 929132718Skan || GET_CODE (op) == SUBREG 930132718Skan || GET_CODE (op) == CONCAT) 931117395Skan { 932117395Skan tree qual_type = build_qualified_type (type, 933117395Skan (TYPE_QUALS (type) 934117395Skan | TYPE_QUAL_CONST)); 935117395Skan rtx memloc = assign_temp (qual_type, 1, 1, 1); 936117395Skan memloc = validize_mem (memloc); 937117395Skan emit_move_insn (memloc, op); 938117395Skan op = memloc; 939117395Skan } 94090075Sobrien } 94118334Speter } 94218334Speter 94390075Sobrien generating_concat_p = old_generating_concat_p; 94490075Sobrien ASM_OPERANDS_INPUT (body, i) = op; 94590075Sobrien 94690075Sobrien ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i) 947169689Skan = gen_rtx_ASM_INPUT (TYPE_MODE (type), 948169689Skan ggc_strdup (constraints[i + noutputs])); 949117395Skan 950169689Skan if (tree_conflicts_with_clobbers_p (val, &clobbered_regs)) 951117395Skan clobber_conflict_found = 1; 95218334Speter } 95318334Speter 95490075Sobrien /* Protect all the operands from the queue now that they have all been 95590075Sobrien evaluated. */ 95618334Speter 95790075Sobrien generating_concat_p = 0; 95890075Sobrien 95990075Sobrien /* For in-out operands, copy output rtx to input rtx. */ 96050397Sobrien for (i = 0; i < ninout; i++) 96150397Sobrien { 96250397Sobrien int j = inout_opnum[i]; 96390075Sobrien char buffer[16]; 96450397Sobrien 96590075Sobrien ASM_OPERANDS_INPUT (body, ninputs - ninout + i) 96650397Sobrien = output_rtx[j]; 96790075Sobrien 96890075Sobrien sprintf (buffer, "%d", j); 96990075Sobrien ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i) 970132718Skan = gen_rtx_ASM_INPUT (inout_mode[i], ggc_strdup (buffer)); 97150397Sobrien } 97250397Sobrien 97390075Sobrien generating_concat_p = old_generating_concat_p; 97490075Sobrien 97518334Speter /* Now, for each output, construct an rtx 97690075Sobrien (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER 97790075Sobrien ARGVEC CONSTRAINTS OPNAMES)) 97818334Speter If there is more than one, put them inside a PARALLEL. */ 97918334Speter 98018334Speter if (noutputs == 1 && nclobbers == 0) 98118334Speter { 982169689Skan ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = ggc_strdup (constraints[0]); 983132718Skan emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body)); 98418334Speter } 98590075Sobrien 98618334Speter else if (noutputs == 0 && nclobbers == 0) 98718334Speter { 98818334Speter /* No output operands: put in a raw ASM_OPERANDS rtx. */ 989132718Skan emit_insn (body); 99018334Speter } 99190075Sobrien 99218334Speter else 99318334Speter { 99418334Speter rtx obody = body; 99518334Speter int num = noutputs; 99690075Sobrien 99790075Sobrien if (num == 0) 99890075Sobrien num = 1; 99990075Sobrien 100050397Sobrien body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers)); 100118334Speter 100218334Speter /* For each output operand, store a SET. */ 100318334Speter for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 100418334Speter { 100518334Speter XVECEXP (body, 0, i) 100650397Sobrien = gen_rtx_SET (VOIDmode, 100750397Sobrien output_rtx[i], 100890075Sobrien gen_rtx_ASM_OPERANDS 100990075Sobrien (GET_MODE (output_rtx[i]), 1010169689Skan ggc_strdup (TREE_STRING_POINTER (string)), 1011169689Skan ggc_strdup (constraints[i]), 1012169689Skan i, argvec, constraintvec, locus)); 101390075Sobrien 101418334Speter MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol; 101518334Speter } 101618334Speter 101718334Speter /* If there are no outputs (but there are some clobbers) 101818334Speter store the bare ASM_OPERANDS into the PARALLEL. */ 101918334Speter 102018334Speter if (i == 0) 102118334Speter XVECEXP (body, 0, i++) = obody; 102218334Speter 102318334Speter /* Store (clobber REG) for each clobbered register specified. */ 102418334Speter 102518334Speter for (tail = clobbers; tail; tail = TREE_CHAIN (tail)) 102618334Speter { 102790075Sobrien const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail)); 102818334Speter int j = decode_reg_name (regname); 1029117395Skan rtx clobbered_reg; 103018334Speter 103118334Speter if (j < 0) 103218334Speter { 103318334Speter if (j == -3) /* `cc', which is not a register */ 103418334Speter continue; 103518334Speter 103618334Speter if (j == -4) /* `memory', don't cache memory across asm */ 103718334Speter { 103818334Speter XVECEXP (body, 0, i++) 103950397Sobrien = gen_rtx_CLOBBER (VOIDmode, 104090075Sobrien gen_rtx_MEM 104190075Sobrien (BLKmode, 104290075Sobrien gen_rtx_SCRATCH (VOIDmode))); 104318334Speter continue; 104418334Speter } 104518334Speter 104650397Sobrien /* Ignore unknown register, error already signaled. */ 104718334Speter continue; 104818334Speter } 104918334Speter 105018334Speter /* Use QImode since that's guaranteed to clobber just one reg. */ 1051117395Skan clobbered_reg = gen_rtx_REG (QImode, j); 1052117395Skan 1053117395Skan /* Do sanity check for overlap between clobbers and respectively 1054117395Skan input and outputs that hasn't been handled. Such overlap 1055117395Skan should have been detected and reported above. */ 1056117395Skan if (!clobber_conflict_found) 1057117395Skan { 1058117395Skan int opno; 1059117395Skan 1060117395Skan /* We test the old body (obody) contents to avoid tripping 1061117395Skan over the under-construction body. */ 1062117395Skan for (opno = 0; opno < noutputs; opno++) 1063117395Skan if (reg_overlap_mentioned_p (clobbered_reg, output_rtx[opno])) 1064117395Skan internal_error ("asm clobber conflict with output operand"); 1065117395Skan 1066117395Skan for (opno = 0; opno < ninputs - ninout; opno++) 1067117395Skan if (reg_overlap_mentioned_p (clobbered_reg, 1068117395Skan ASM_OPERANDS_INPUT (obody, opno))) 1069117395Skan internal_error ("asm clobber conflict with input operand"); 1070117395Skan } 1071117395Skan 107218334Speter XVECEXP (body, 0, i++) 1073117395Skan = gen_rtx_CLOBBER (VOIDmode, clobbered_reg); 107418334Speter } 107518334Speter 1076132718Skan emit_insn (body); 107718334Speter } 107818334Speter 107952284Sobrien /* For any outputs that needed reloading into registers, spill them 108052284Sobrien back to where they belong. */ 108152284Sobrien for (i = 0; i < noutputs; ++i) 108252284Sobrien if (real_output_rtx[i]) 108352284Sobrien emit_move_insn (real_output_rtx[i], output_rtx[i]); 108452284Sobrien 108518334Speter free_temp_slots (); 108618334Speter} 108790075Sobrien 1088169689Skanvoid 1089169689Skanexpand_asm_expr (tree exp) 1090169689Skan{ 1091169689Skan int noutputs, i; 1092169689Skan tree outputs, tail; 1093169689Skan tree *o; 1094169689Skan 1095169689Skan if (ASM_INPUT_P (exp)) 1096169689Skan { 1097169689Skan expand_asm (ASM_STRING (exp), ASM_VOLATILE_P (exp)); 1098169689Skan return; 1099169689Skan } 1100169689Skan 1101169689Skan outputs = ASM_OUTPUTS (exp); 1102169689Skan noutputs = list_length (outputs); 1103169689Skan /* o[I] is the place that output number I should be written. */ 1104169689Skan o = (tree *) alloca (noutputs * sizeof (tree)); 1105169689Skan 1106169689Skan /* Record the contents of OUTPUTS before it is modified. */ 1107169689Skan for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 1108169689Skan o[i] = TREE_VALUE (tail); 1109169689Skan 1110169689Skan /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of 1111169689Skan OUTPUTS some trees for where the values were actually stored. */ 1112169689Skan expand_asm_operands (ASM_STRING (exp), outputs, ASM_INPUTS (exp), 1113169689Skan ASM_CLOBBERS (exp), ASM_VOLATILE_P (exp), 1114169689Skan input_location); 1115169689Skan 1116169689Skan /* Copy all the intermediate outputs into the specified outputs. */ 1117169689Skan for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) 1118169689Skan { 1119169689Skan if (o[i] != TREE_VALUE (tail)) 1120169689Skan { 1121169689Skan expand_assignment (o[i], TREE_VALUE (tail)); 1122169689Skan free_temp_slots (); 1123169689Skan 1124169689Skan /* Restore the original value so that it's correct the next 1125169689Skan time we expand this function. */ 1126169689Skan TREE_VALUE (tail) = o[i]; 1127169689Skan } 1128169689Skan } 1129169689Skan} 1130169689Skan 113190075Sobrien/* A subroutine of expand_asm_operands. Check that all operands have 113290075Sobrien the same number of alternatives. Return true if so. */ 113390075Sobrien 113490075Sobrienstatic bool 1135132718Skancheck_operand_nalternatives (tree outputs, tree inputs) 113690075Sobrien{ 113790075Sobrien if (outputs || inputs) 113890075Sobrien { 113990075Sobrien tree tmp = TREE_PURPOSE (outputs ? outputs : inputs); 114090075Sobrien int nalternatives 114190075Sobrien = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp))); 114290075Sobrien tree next = inputs; 114390075Sobrien 114490075Sobrien if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES) 114590075Sobrien { 1146169689Skan error ("too many alternatives in %<asm%>"); 114790075Sobrien return false; 114890075Sobrien } 114990075Sobrien 115090075Sobrien tmp = outputs; 115190075Sobrien while (tmp) 115290075Sobrien { 115390075Sobrien const char *constraint 115490075Sobrien = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp))); 115590075Sobrien 115690075Sobrien if (n_occurrences (',', constraint) != nalternatives) 115790075Sobrien { 1158169689Skan error ("operand constraints for %<asm%> differ " 1159169689Skan "in number of alternatives"); 116090075Sobrien return false; 116190075Sobrien } 116290075Sobrien 116390075Sobrien if (TREE_CHAIN (tmp)) 116490075Sobrien tmp = TREE_CHAIN (tmp); 116590075Sobrien else 116690075Sobrien tmp = next, next = 0; 116790075Sobrien } 116890075Sobrien } 116990075Sobrien 117090075Sobrien return true; 117190075Sobrien} 117290075Sobrien 117390075Sobrien/* A subroutine of expand_asm_operands. Check that all operand names 117490075Sobrien are unique. Return true if so. We rely on the fact that these names 117590075Sobrien are identifiers, and so have been canonicalized by get_identifier, 117690075Sobrien so all we need are pointer comparisons. */ 117790075Sobrien 117890075Sobrienstatic bool 1179132718Skancheck_unique_operand_names (tree outputs, tree inputs) 118090075Sobrien{ 118190075Sobrien tree i, j; 118290075Sobrien 118390075Sobrien for (i = outputs; i ; i = TREE_CHAIN (i)) 118490075Sobrien { 118590075Sobrien tree i_name = TREE_PURPOSE (TREE_PURPOSE (i)); 118690075Sobrien if (! i_name) 118790075Sobrien continue; 118890075Sobrien 118990075Sobrien for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j)) 1190117395Skan if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) 119190075Sobrien goto failure; 119290075Sobrien } 119390075Sobrien 119490075Sobrien for (i = inputs; 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 for (j = outputs; j ; j = TREE_CHAIN (j)) 1204117395Skan if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) 120590075Sobrien goto failure; 120690075Sobrien } 120790075Sobrien 120890075Sobrien return true; 120990075Sobrien 121090075Sobrien failure: 1211169689Skan error ("duplicate asm operand name %qs", 1212117395Skan TREE_STRING_POINTER (TREE_PURPOSE (TREE_PURPOSE (i)))); 121390075Sobrien return false; 121490075Sobrien} 121590075Sobrien 121690075Sobrien/* A subroutine of expand_asm_operands. Resolve the names of the operands 121790075Sobrien in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in 121890075Sobrien STRING and in the constraints to those numbers. */ 121990075Sobrien 1220132718Skantree 1221132718Skanresolve_asm_operand_names (tree string, tree outputs, tree inputs) 122290075Sobrien{ 1223132718Skan char *buffer; 122490075Sobrien char *p; 1225132718Skan const char *c; 122690075Sobrien tree t; 122790075Sobrien 1228132718Skan check_unique_operand_names (outputs, inputs); 122990075Sobrien 1230132718Skan /* Substitute [<name>] in input constraint strings. There should be no 1231132718Skan named operands in output constraints. */ 1232132718Skan for (t = inputs; t ; t = TREE_CHAIN (t)) 123390075Sobrien { 1234132718Skan c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t))); 1235132718Skan if (strchr (c, '[') != NULL) 1236132718Skan { 1237132718Skan p = buffer = xstrdup (c); 1238132718Skan while ((p = strchr (p, '[')) != NULL) 1239132718Skan p = resolve_operand_name_1 (p, outputs, inputs); 1240132718Skan TREE_VALUE (TREE_PURPOSE (t)) 1241132718Skan = build_string (strlen (buffer), buffer); 1242132718Skan free (buffer); 1243132718Skan } 1244132718Skan } 1245132718Skan 1246132718Skan /* Now check for any needed substitutions in the template. */ 1247132718Skan c = TREE_STRING_POINTER (string); 1248132718Skan while ((c = strchr (c, '%')) != NULL) 1249132718Skan { 1250132718Skan if (c[1] == '[') 1251132718Skan break; 1252132718Skan else if (ISALPHA (c[1]) && c[2] == '[') 1253132718Skan break; 125490075Sobrien else 125590075Sobrien { 1256132718Skan c += 1; 125790075Sobrien continue; 125890075Sobrien } 125990075Sobrien } 126090075Sobrien 1261132718Skan if (c) 126290075Sobrien { 1263132718Skan /* OK, we need to make a copy so we can perform the substitutions. 1264132718Skan Assume that we will not need extra space--we get to remove '[' 1265132718Skan and ']', which means we cannot have a problem until we have more 1266132718Skan than 999 operands. */ 1267132718Skan buffer = xstrdup (TREE_STRING_POINTER (string)); 1268132718Skan p = buffer + (c - TREE_STRING_POINTER (string)); 1269169689Skan 1270132718Skan while ((p = strchr (p, '%')) != NULL) 127190075Sobrien { 1272132718Skan if (p[1] == '[') 1273132718Skan p += 1; 1274132718Skan else if (ISALPHA (p[1]) && p[2] == '[') 1275132718Skan p += 2; 1276132718Skan else 1277132718Skan { 1278132718Skan p += 1; 1279132718Skan continue; 1280132718Skan } 128190075Sobrien 1282132718Skan p = resolve_operand_name_1 (p, outputs, inputs); 128390075Sobrien } 1284132718Skan 1285132718Skan string = build_string (strlen (buffer), buffer); 1286132718Skan free (buffer); 128790075Sobrien } 128890075Sobrien 128990075Sobrien return string; 129090075Sobrien} 129190075Sobrien 129290075Sobrien/* A subroutine of resolve_operand_names. P points to the '[' for a 129390075Sobrien potential named operand of the form [<name>]. In place, replace 1294117395Skan the name and brackets with a number. Return a pointer to the 129590075Sobrien balance of the string after substitution. */ 129690075Sobrien 129790075Sobrienstatic char * 1298132718Skanresolve_operand_name_1 (char *p, tree outputs, tree inputs) 129990075Sobrien{ 130090075Sobrien char *q; 130190075Sobrien int op; 130290075Sobrien tree t; 130390075Sobrien size_t len; 130490075Sobrien 130590075Sobrien /* Collect the operand name. */ 130690075Sobrien q = strchr (p, ']'); 130790075Sobrien if (!q) 130890075Sobrien { 130990075Sobrien error ("missing close brace for named operand"); 131090075Sobrien return strchr (p, '\0'); 131190075Sobrien } 131290075Sobrien len = q - p - 1; 131390075Sobrien 131490075Sobrien /* Resolve the name to a number. */ 131590075Sobrien for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++) 131690075Sobrien { 1317117395Skan tree name = TREE_PURPOSE (TREE_PURPOSE (t)); 1318117395Skan if (name) 131996263Sobrien { 1320117395Skan const char *c = TREE_STRING_POINTER (name); 132196263Sobrien if (strncmp (c, p + 1, len) == 0 && c[len] == '\0') 132296263Sobrien goto found; 132396263Sobrien } 132490075Sobrien } 132590075Sobrien for (t = inputs; t ; t = TREE_CHAIN (t), op++) 132690075Sobrien { 1327117395Skan tree name = TREE_PURPOSE (TREE_PURPOSE (t)); 1328117395Skan if (name) 132996263Sobrien { 1330117395Skan const char *c = TREE_STRING_POINTER (name); 133196263Sobrien if (strncmp (c, p + 1, len) == 0 && c[len] == '\0') 133296263Sobrien goto found; 133396263Sobrien } 133490075Sobrien } 133590075Sobrien 133690075Sobrien *q = '\0'; 1337169689Skan error ("undefined named operand %qs", p + 1); 133890075Sobrien op = 0; 133990075Sobrien found: 134090075Sobrien 134190075Sobrien /* Replace the name with the number. Unfortunately, not all libraries 134290075Sobrien get the return value of sprintf correct, so search for the end of the 134390075Sobrien generated string by hand. */ 134490075Sobrien sprintf (p, "%d", op); 134590075Sobrien p = strchr (p, '\0'); 134690075Sobrien 134790075Sobrien /* Verify the no extra buffer space assumption. */ 1348169689Skan gcc_assert (p <= q); 134990075Sobrien 135090075Sobrien /* Shift the rest of the buffer down to fill the gap. */ 135190075Sobrien memmove (p, q + 1, strlen (q + 1) + 1); 135290075Sobrien 135390075Sobrien return p; 135490075Sobrien} 135518334Speter 1356169689Skan/* Generate RTL to evaluate the expression EXP. */ 135718334Speter 135818334Spetervoid 1359132718Skanexpand_expr_stmt (tree exp) 136018334Speter{ 136190075Sobrien rtx value; 136290075Sobrien tree type; 136390075Sobrien 1364169689Skan value = expand_expr (exp, const0_rtx, VOIDmode, 0); 136590075Sobrien type = TREE_TYPE (exp); 136618334Speter 136718334Speter /* If all we do is reference a volatile value in memory, 136818334Speter copy it to a register to be sure it is actually touched. */ 1369169689Skan if (value && MEM_P (value) && TREE_THIS_VOLATILE (exp)) 137018334Speter { 137190075Sobrien if (TYPE_MODE (type) == VOIDmode) 137218334Speter ; 137390075Sobrien else if (TYPE_MODE (type) != BLKmode) 137490075Sobrien value = copy_to_reg (value); 137518334Speter else 137618334Speter { 137718334Speter rtx lab = gen_label_rtx (); 137890075Sobrien 137918334Speter /* Compare the value with itself to reference it. */ 138090075Sobrien emit_cmp_and_jump_insns (value, value, EQ, 1381169689Skan expand_normal (TYPE_SIZE (type)), 138290075Sobrien BLKmode, 0, lab); 138318334Speter emit_label (lab); 138418334Speter } 138518334Speter } 138618334Speter 1387169689Skan /* Free any temporaries used to evaluate this expression. */ 138818334Speter free_temp_slots (); 138918334Speter} 139018334Speter 139118334Speter/* Warn if EXP contains any computations whose results are not used. 1392169689Skan Return 1 if a warning is printed; 0 otherwise. LOCUS is the 1393169689Skan (potential) location of the expression. */ 139418334Speter 139518334Speterint 1396169689Skanwarn_if_unused_value (tree exp, location_t locus) 139718334Speter{ 1398169689Skan restart: 1399169689Skan if (TREE_USED (exp) || TREE_NO_WARNING (exp)) 140018334Speter return 0; 140118334Speter 140290075Sobrien /* Don't warn about void constructs. This includes casting to void, 140390075Sobrien void function calls, and statement expressions with a final cast 140490075Sobrien to void. */ 140590075Sobrien if (VOID_TYPE_P (TREE_TYPE (exp))) 140690075Sobrien return 0; 140790075Sobrien 1408169689Skan if (EXPR_HAS_LOCATION (exp)) 1409169689Skan locus = EXPR_LOCATION (exp); 1410169689Skan 141118334Speter switch (TREE_CODE (exp)) 141218334Speter { 141318334Speter case PREINCREMENT_EXPR: 141418334Speter case POSTINCREMENT_EXPR: 141518334Speter case PREDECREMENT_EXPR: 141618334Speter case POSTDECREMENT_EXPR: 141718334Speter case MODIFY_EXPR: 141818334Speter case INIT_EXPR: 141918334Speter case TARGET_EXPR: 142018334Speter case CALL_EXPR: 142150397Sobrien case TRY_CATCH_EXPR: 142218334Speter case WITH_CLEANUP_EXPR: 142318334Speter case EXIT_EXPR: 1424169689Skan case VA_ARG_EXPR: 142518334Speter return 0; 142618334Speter 142718334Speter case BIND_EXPR: 142818334Speter /* For a binding, warn if no side effect within it. */ 1429169689Skan exp = BIND_EXPR_BODY (exp); 1430169689Skan goto restart; 143118334Speter 143218334Speter case SAVE_EXPR: 1433169689Skan exp = TREE_OPERAND (exp, 0); 1434169689Skan goto restart; 143518334Speter 143618334Speter case TRUTH_ORIF_EXPR: 143718334Speter case TRUTH_ANDIF_EXPR: 143818334Speter /* In && or ||, warn if 2nd operand has no side effect. */ 1439169689Skan exp = TREE_OPERAND (exp, 1); 1440169689Skan goto restart; 144118334Speter 144218334Speter case COMPOUND_EXPR: 1443169689Skan if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus)) 144418334Speter return 1; 144518334Speter /* Let people do `(foo (), 0)' without a warning. */ 144618334Speter if (TREE_CONSTANT (TREE_OPERAND (exp, 1))) 144718334Speter return 0; 1448169689Skan exp = TREE_OPERAND (exp, 1); 1449169689Skan goto restart; 145018334Speter 1451169689Skan case COND_EXPR: 1452169689Skan /* If this is an expression with side effects, don't warn; this 1453169689Skan case commonly appears in macro expansions. */ 1454169689Skan if (TREE_SIDE_EFFECTS (exp)) 145518334Speter return 0; 1456169689Skan goto warn; 145718334Speter 145818334Speter case INDIRECT_REF: 145918334Speter /* Don't warn about automatic dereferencing of references, since 146018334Speter the user cannot control it. */ 146118334Speter if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE) 1462169689Skan { 1463169689Skan exp = TREE_OPERAND (exp, 0); 1464169689Skan goto restart; 1465169689Skan } 146690075Sobrien /* Fall through. */ 146790075Sobrien 146818334Speter default: 146918334Speter /* Referencing a volatile value is a side effect, so don't warn. */ 1470169689Skan if ((DECL_P (exp) || REFERENCE_CLASS_P (exp)) 147118334Speter && TREE_THIS_VOLATILE (exp)) 147218334Speter return 0; 147390075Sobrien 147490075Sobrien /* If this is an expression which has no operands, there is no value 147590075Sobrien to be unused. There are no such language-independent codes, 147690075Sobrien but front ends may define such. */ 1477169689Skan if (EXPRESSION_CLASS_P (exp) && TREE_CODE_LENGTH (TREE_CODE (exp)) == 0) 147890075Sobrien return 0; 147990075Sobrien 1480169689Skan warn: 1481169689Skan warning (0, "%Hvalue computed is not used", &locus); 148218334Speter return 1; 148318334Speter } 148418334Speter} 148518334Speter 148618334Speter 148718334Speter/* Generate RTL to return from the current function, with no value. 148818334Speter (That is, we do not do anything about returning any value.) */ 148918334Speter 149018334Spetervoid 1491132718Skanexpand_null_return (void) 149218334Speter{ 149390075Sobrien /* If this function was declared to return a value, but we 149490075Sobrien didn't, clobber the return registers so that they are not 149590075Sobrien propagated live to the rest of the function. */ 149690075Sobrien clobber_return_register (); 149718334Speter 1498169689Skan expand_null_return_1 (); 149918334Speter} 150018334Speter 1501132718Skan/* Generate RTL to return directly from the current function. 1502132718Skan (That is, we bypass any return value.) */ 1503132718Skan 1504132718Skanvoid 1505132718Skanexpand_naked_return (void) 1506132718Skan{ 1507169689Skan rtx end_label; 1508132718Skan 1509132718Skan clear_pending_stack_adjust (); 1510132718Skan do_pending_stack_adjust (); 1511132718Skan 1512169689Skan end_label = naked_return_label; 1513132718Skan if (end_label == 0) 1514132718Skan end_label = naked_return_label = gen_label_rtx (); 1515132718Skan 1516169689Skan emit_jump (end_label); 1517117395Skan} 1518117395Skan 151918334Speter/* Generate RTL to return from the current function, with value VAL. */ 152018334Speter 152118334Speterstatic void 1522132718Skanexpand_value_return (rtx val) 152318334Speter{ 152418334Speter /* Copy the value to the return location 152518334Speter unless it's already there. */ 152618334Speter 1527169689Skan rtx return_reg = DECL_RTL (DECL_RESULT (current_function_decl)); 152818334Speter if (return_reg != val) 152918334Speter { 153090075Sobrien tree type = TREE_TYPE (DECL_RESULT (current_function_decl)); 1531132718Skan if (targetm.calls.promote_function_return (TREE_TYPE (current_function_decl))) 1532132718Skan { 1533169689Skan int unsignedp = TYPE_UNSIGNED (type); 1534132718Skan enum machine_mode old_mode 1535132718Skan = DECL_MODE (DECL_RESULT (current_function_decl)); 1536132718Skan enum machine_mode mode 1537132718Skan = promote_mode (type, old_mode, &unsignedp, 1); 153818334Speter 1539132718Skan if (mode != old_mode) 1540132718Skan val = convert_modes (mode, old_mode, val, unsignedp); 1541132718Skan } 154290075Sobrien if (GET_CODE (return_reg) == PARALLEL) 1543132718Skan emit_group_load (return_reg, val, type, int_size_in_bytes (type)); 154490075Sobrien else 154590075Sobrien emit_move_insn (return_reg, val); 154618334Speter } 154718334Speter 1548169689Skan expand_null_return_1 (); 154918334Speter} 155018334Speter 1551169689Skan/* Output a return with no value. */ 155218334Speter 155318334Speterstatic void 1554169689Skanexpand_null_return_1 (void) 155518334Speter{ 155618334Speter clear_pending_stack_adjust (); 155718334Speter do_pending_stack_adjust (); 1558169689Skan emit_jump (return_label); 155918334Speter} 156018334Speter 156118334Speter/* Generate RTL to evaluate the expression RETVAL and return it 156218334Speter from the current function. */ 156318334Speter 156418334Spetervoid 1565132718Skanexpand_return (tree retval) 156618334Speter{ 156790075Sobrien rtx result_rtl; 156890075Sobrien rtx val = 0; 156918334Speter tree retval_rhs; 157018334Speter 157118334Speter /* If function wants no value, give it none. */ 157218334Speter if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE) 157318334Speter { 1574169689Skan expand_normal (retval); 157518334Speter expand_null_return (); 157618334Speter return; 157718334Speter } 157818334Speter 157990075Sobrien if (retval == error_mark_node) 158090075Sobrien { 158190075Sobrien /* Treat this like a return of no value from a function that 158290075Sobrien returns a value. */ 158390075Sobrien expand_null_return (); 1584117395Skan return; 158590075Sobrien } 1586169689Skan else if ((TREE_CODE (retval) == MODIFY_EXPR 1587169689Skan || TREE_CODE (retval) == INIT_EXPR) 158818334Speter && TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL) 158918334Speter retval_rhs = TREE_OPERAND (retval, 1); 1590169689Skan else 159118334Speter retval_rhs = retval; 159218334Speter 1593169689Skan result_rtl = DECL_RTL (DECL_RESULT (current_function_decl)); 159418334Speter 1595169689Skan /* If we are returning the RESULT_DECL, then the value has already 1596169689Skan been stored into it, so we don't have to do anything special. */ 1597169689Skan if (TREE_CODE (retval_rhs) == RESULT_DECL) 1598169689Skan expand_value_return (result_rtl); 159918334Speter 160018334Speter /* If the result is an aggregate that is being returned in one (or more) 160118334Speter registers, load the registers here. The compiler currently can't handle 160218334Speter copying a BLKmode value into registers. We could put this code in a 160318334Speter more general area (for use by everyone instead of just function 160418334Speter call/return), but until this feature is generally usable it is kept here 1605169689Skan (and in expand_call). */ 160618334Speter 1607169689Skan else if (retval_rhs != 0 1608169689Skan && TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode 1609169689Skan && REG_P (result_rtl)) 161018334Speter { 161190075Sobrien int i; 161290075Sobrien unsigned HOST_WIDE_INT bitpos, xbitpos; 1613132718Skan unsigned HOST_WIDE_INT padding_correction = 0; 161490075Sobrien unsigned HOST_WIDE_INT bytes 161590075Sobrien = int_size_in_bytes (TREE_TYPE (retval_rhs)); 161618334Speter int n_regs = (bytes + UNITS_PER_WORD - 1) / UNITS_PER_WORD; 161790075Sobrien unsigned int bitsize 161890075Sobrien = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)), BITS_PER_WORD); 1619132718Skan rtx *result_pseudos = alloca (sizeof (rtx) * n_regs); 162050397Sobrien rtx result_reg, src = NULL_RTX, dst = NULL_RTX; 1621169689Skan rtx result_val = expand_normal (retval_rhs); 162218334Speter enum machine_mode tmpmode, result_reg_mode; 162318334Speter 162490075Sobrien if (bytes == 0) 162590075Sobrien { 162690075Sobrien expand_null_return (); 162790075Sobrien return; 162890075Sobrien } 162990075Sobrien 1630132718Skan /* If the structure doesn't take up a whole number of words, see 1631132718Skan whether the register value should be padded on the left or on 1632132718Skan the right. Set PADDING_CORRECTION to the number of padding 1633132718Skan bits needed on the left side. 163418334Speter 1635132718Skan In most ABIs, the structure will be returned at the least end of 1636132718Skan the register, which translates to right padding on little-endian 1637132718Skan targets and left padding on big-endian targets. The opposite 1638132718Skan holds if the structure is returned at the most significant 1639132718Skan end of the register. */ 1640132718Skan if (bytes % UNITS_PER_WORD != 0 1641132718Skan && (targetm.calls.return_in_msb (TREE_TYPE (retval_rhs)) 1642132718Skan ? !BYTES_BIG_ENDIAN 1643132718Skan : BYTES_BIG_ENDIAN)) 1644132718Skan padding_correction = (BITS_PER_WORD - ((bytes % UNITS_PER_WORD) 1645132718Skan * BITS_PER_UNIT)); 1646132718Skan 164790075Sobrien /* Copy the structure BITSIZE bits at a time. */ 1648132718Skan for (bitpos = 0, xbitpos = padding_correction; 164918334Speter bitpos < bytes * BITS_PER_UNIT; 165018334Speter bitpos += bitsize, xbitpos += bitsize) 165118334Speter { 165218334Speter /* We need a new destination pseudo each time xbitpos is 1653132718Skan on a word boundary and when xbitpos == padding_correction 165418334Speter (the first time through). */ 165518334Speter if (xbitpos % BITS_PER_WORD == 0 1656132718Skan || xbitpos == padding_correction) 165718334Speter { 165818334Speter /* Generate an appropriate register. */ 165918334Speter dst = gen_reg_rtx (word_mode); 166018334Speter result_pseudos[xbitpos / BITS_PER_WORD] = dst; 166118334Speter 166290075Sobrien /* Clear the destination before we move anything into it. */ 166390075Sobrien emit_move_insn (dst, CONST0_RTX (GET_MODE (dst))); 166418334Speter } 166518334Speter 166618334Speter /* We need a new source operand each time bitpos is on a word 166718334Speter boundary. */ 166818334Speter if (bitpos % BITS_PER_WORD == 0) 166918334Speter src = operand_subword_force (result_val, 167018334Speter bitpos / BITS_PER_WORD, 167118334Speter BLKmode); 167218334Speter 167318334Speter /* Use bitpos for the source extraction (left justified) and 167418334Speter xbitpos for the destination store (right justified). */ 167518334Speter store_bit_field (dst, bitsize, xbitpos % BITS_PER_WORD, word_mode, 167618334Speter extract_bit_field (src, bitsize, 167718334Speter bitpos % BITS_PER_WORD, 1, 1678169689Skan NULL_RTX, word_mode, word_mode)); 167918334Speter } 168018334Speter 1681132718Skan tmpmode = GET_MODE (result_rtl); 1682132718Skan if (tmpmode == BLKmode) 1683132718Skan { 1684132718Skan /* Find the smallest integer mode large enough to hold the 1685132718Skan entire structure and use that mode instead of BLKmode 1686132718Skan on the USE insn for the return register. */ 1687132718Skan for (tmpmode = GET_CLASS_NARROWEST_MODE (MODE_INT); 1688132718Skan tmpmode != VOIDmode; 1689132718Skan tmpmode = GET_MODE_WIDER_MODE (tmpmode)) 1690132718Skan /* Have we found a large enough mode? */ 1691132718Skan if (GET_MODE_SIZE (tmpmode) >= bytes) 1692132718Skan break; 169318334Speter 1694169689Skan /* A suitable mode should have been found. */ 1695169689Skan gcc_assert (tmpmode != VOIDmode); 169618334Speter 1697132718Skan PUT_MODE (result_rtl, tmpmode); 1698132718Skan } 169918334Speter 170018334Speter if (GET_MODE_SIZE (tmpmode) < GET_MODE_SIZE (word_mode)) 170118334Speter result_reg_mode = word_mode; 170218334Speter else 170318334Speter result_reg_mode = tmpmode; 170418334Speter result_reg = gen_reg_rtx (result_reg_mode); 170518334Speter 170618334Speter for (i = 0; i < n_regs; i++) 170718334Speter emit_move_insn (operand_subword (result_reg, i, 0, result_reg_mode), 170818334Speter result_pseudos[i]); 170918334Speter 171018334Speter if (tmpmode != result_reg_mode) 171118334Speter result_reg = gen_lowpart (tmpmode, result_reg); 171218334Speter 171318334Speter expand_value_return (result_reg); 171418334Speter } 171590075Sobrien else if (retval_rhs != 0 171690075Sobrien && !VOID_TYPE_P (TREE_TYPE (retval_rhs)) 1717169689Skan && (REG_P (result_rtl) 171890075Sobrien || (GET_CODE (result_rtl) == PARALLEL))) 171918334Speter { 172090075Sobrien /* Calculate the return value into a temporary (usually a pseudo 172190075Sobrien reg). */ 172290075Sobrien tree ot = TREE_TYPE (DECL_RESULT (current_function_decl)); 172390075Sobrien tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST); 172490075Sobrien 172590075Sobrien val = assign_temp (nt, 0, 0, 1); 172650397Sobrien val = expand_expr (retval_rhs, val, GET_MODE (val), 0); 172750397Sobrien val = force_not_mem (val); 1728169689Skan /* Return the calculated value. */ 1729169689Skan expand_value_return (val); 173018334Speter } 173118334Speter else 173218334Speter { 1733169689Skan /* No hard reg used; calculate value into hard return reg. */ 173418334Speter expand_expr (retval, const0_rtx, VOIDmode, 0); 173590075Sobrien expand_value_return (result_rtl); 173618334Speter } 173718334Speter} 173818334Speter 1739117395Skan/* Given a pointer to a BLOCK node return nonzero if (and only if) the node 174090075Sobrien in question represents the outermost pair of curly braces (i.e. the "body 174190075Sobrien block") of a function or method. 174250397Sobrien 174390075Sobrien For any BLOCK node representing a "body block" of a function or method, the 174490075Sobrien BLOCK_SUPERCONTEXT of the node will point to another BLOCK node which 174590075Sobrien represents the outermost (function) scope for the function or method (i.e. 174690075Sobrien the one which includes the formal parameters). The BLOCK_SUPERCONTEXT of 174790075Sobrien *that* node in turn will point to the relevant FUNCTION_DECL node. */ 174890075Sobrien 174990075Sobrienint 1750132718Skanis_body_block (tree stmt) 175150397Sobrien{ 1752132718Skan if (lang_hooks.no_body_blocks) 1753132718Skan return 0; 1754132718Skan 175590075Sobrien if (TREE_CODE (stmt) == BLOCK) 175618334Speter { 175790075Sobrien tree parent = BLOCK_SUPERCONTEXT (stmt); 175890075Sobrien 175990075Sobrien if (parent && TREE_CODE (parent) == BLOCK) 176090075Sobrien { 176190075Sobrien tree grandparent = BLOCK_SUPERCONTEXT (parent); 176290075Sobrien 176390075Sobrien if (grandparent && TREE_CODE (grandparent) == FUNCTION_DECL) 176490075Sobrien return 1; 176590075Sobrien } 176618334Speter } 176790075Sobrien 176890075Sobrien return 0; 176918334Speter} 177018334Speter 177152284Sobrien/* Emit code to restore vital registers at the beginning of a nonlocal goto 177252284Sobrien handler. */ 177352284Sobrienstatic void 1774132718Skanexpand_nl_goto_receiver (void) 177552284Sobrien{ 1776169689Skan /* Clobber the FP when we get here, so we have to make sure it's 1777132718Skan marked as used by this function. */ 1778132718Skan emit_insn (gen_rtx_USE (VOIDmode, hard_frame_pointer_rtx)); 1779132718Skan 1780132718Skan /* Mark the static chain as clobbered here so life information 1781132718Skan doesn't get messed up for it. */ 1782132718Skan emit_insn (gen_rtx_CLOBBER (VOIDmode, static_chain_rtx)); 1783132718Skan 178452284Sobrien#ifdef HAVE_nonlocal_goto 178552284Sobrien if (! HAVE_nonlocal_goto) 178652284Sobrien#endif 178752284Sobrien /* First adjust our frame pointer to its actual value. It was 178852284Sobrien previously set to the start of the virtual area corresponding to 178952284Sobrien the stacked variables when we branched here and now needs to be 179052284Sobrien adjusted to the actual hardware fp value. 179152284Sobrien 179252284Sobrien Assignments are to virtual registers are converted by 179352284Sobrien instantiate_virtual_regs into the corresponding assignment 179452284Sobrien to the underlying register (fp in this case) that makes 179552284Sobrien the original assignment true. 179652284Sobrien So the following insn will actually be 179752284Sobrien decrementing fp by STARTING_FRAME_OFFSET. */ 179852284Sobrien emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx); 179952284Sobrien 180052284Sobrien#if ARG_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 180152284Sobrien if (fixed_regs[ARG_POINTER_REGNUM]) 180252284Sobrien { 180352284Sobrien#ifdef ELIMINABLE_REGS 180452284Sobrien /* If the argument pointer can be eliminated in favor of the 180552284Sobrien frame pointer, we don't need to restore it. We assume here 180652284Sobrien that if such an elimination is present, it can always be used. 180752284Sobrien This is the case on all known machines; if we don't make this 180852284Sobrien assumption, we do unnecessary saving on many machines. */ 180990075Sobrien static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS; 181052284Sobrien size_t i; 181152284Sobrien 181290075Sobrien for (i = 0; i < ARRAY_SIZE (elim_regs); i++) 181352284Sobrien if (elim_regs[i].from == ARG_POINTER_REGNUM 181452284Sobrien && elim_regs[i].to == HARD_FRAME_POINTER_REGNUM) 181552284Sobrien break; 181652284Sobrien 181790075Sobrien if (i == ARRAY_SIZE (elim_regs)) 181852284Sobrien#endif 181952284Sobrien { 182052284Sobrien /* Now restore our arg pointer from the address at which it 182190075Sobrien was saved in our stack frame. */ 182252284Sobrien emit_move_insn (virtual_incoming_args_rtx, 182390075Sobrien copy_to_reg (get_arg_pointer_save_area (cfun))); 182452284Sobrien } 182552284Sobrien } 182652284Sobrien#endif 182752284Sobrien 182852284Sobrien#ifdef HAVE_nonlocal_goto_receiver 182952284Sobrien if (HAVE_nonlocal_goto_receiver) 183052284Sobrien emit_insn (gen_nonlocal_goto_receiver ()); 183152284Sobrien#endif 1832132718Skan 1833132718Skan /* @@@ This is a kludge. Not all machine descriptions define a blockage 1834132718Skan insn, but we must not allow the code we just generated to be reordered 1835132718Skan by scheduling. Specifically, the update of the frame pointer must 1836132718Skan happen immediately, not later. So emit an ASM_INPUT to act as blockage 1837132718Skan insn. */ 1838132718Skan emit_insn (gen_rtx_ASM_INPUT (VOIDmode, "")); 183952284Sobrien} 184018334Speter 184118334Speter/* Generate RTL for the automatic variable declaration DECL. 184218334Speter (Other kinds of declarations are simply ignored if seen here.) */ 184318334Speter 184418334Spetervoid 1845132718Skanexpand_decl (tree decl) 184618334Speter{ 184718334Speter tree type; 184818334Speter 184918334Speter type = TREE_TYPE (decl); 185018334Speter 185190075Sobrien /* For a CONST_DECL, set mode, alignment, and sizes from those of the 185290075Sobrien type in case this node is used in a reference. */ 185390075Sobrien if (TREE_CODE (decl) == CONST_DECL) 185490075Sobrien { 185590075Sobrien DECL_MODE (decl) = TYPE_MODE (type); 185690075Sobrien DECL_ALIGN (decl) = TYPE_ALIGN (type); 185790075Sobrien DECL_SIZE (decl) = TYPE_SIZE (type); 185890075Sobrien DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type); 185990075Sobrien return; 186090075Sobrien } 186118334Speter 186290075Sobrien /* Otherwise, only automatic variables need any expansion done. Static and 186390075Sobrien external variables, and external functions, will be handled by 186490075Sobrien `assemble_variable' (called from finish_decl). TYPE_DECL requires 186590075Sobrien nothing. PARM_DECLs are handled in `assign_parms'. */ 186618334Speter if (TREE_CODE (decl) != VAR_DECL) 186718334Speter return; 186890075Sobrien 186918334Speter if (TREE_STATIC (decl) || DECL_EXTERNAL (decl)) 187018334Speter return; 187118334Speter 187218334Speter /* Create the RTL representation for the variable. */ 187318334Speter 187418334Speter if (type == error_mark_node) 187590075Sobrien SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx)); 187690075Sobrien 187718334Speter else if (DECL_SIZE (decl) == 0) 187818334Speter /* Variable with incomplete type. */ 187918334Speter { 188090075Sobrien rtx x; 188118334Speter if (DECL_INITIAL (decl) == 0) 188218334Speter /* Error message was already done; now avoid a crash. */ 188390075Sobrien x = gen_rtx_MEM (BLKmode, const0_rtx); 188418334Speter else 188518334Speter /* An initializer is going to decide the size of this array. 188618334Speter Until we know the size, represent its address with a reg. */ 188790075Sobrien x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode)); 188890075Sobrien 188990075Sobrien set_mem_attributes (x, decl, 1); 189090075Sobrien SET_DECL_RTL (decl, x); 189118334Speter } 1892169689Skan else if (use_register_for_decl (decl)) 189318334Speter { 189418334Speter /* Automatic variable that can go in a register. */ 1895169689Skan int unsignedp = TYPE_UNSIGNED (type); 189618334Speter enum machine_mode reg_mode 189718334Speter = promote_mode (type, DECL_MODE (decl), &unsignedp, 0); 189818334Speter 189990075Sobrien SET_DECL_RTL (decl, gen_reg_rtx (reg_mode)); 190090075Sobrien 1901169689Skan /* Note if the object is a user variable. */ 1902132718Skan if (!DECL_ARTIFICIAL (decl)) 1903169689Skan { 1904169689Skan mark_user_reg (DECL_RTL (decl)); 190590075Sobrien 1906169689Skan /* Trust user variables which have a pointer type to really 1907169689Skan be pointers. Do not trust compiler generated temporaries 1908169689Skan as our type system is totally busted as it relates to 1909169689Skan pointer arithmetic which translates into lots of compiler 1910169689Skan generated objects with pointer types, but which are not really 1911169689Skan pointers. */ 1912169689Skan if (POINTER_TYPE_P (type)) 1913169689Skan mark_reg_pointer (DECL_RTL (decl), 1914169689Skan TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl)))); 1915169689Skan } 191618334Speter } 191750397Sobrien 191890075Sobrien else if (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST 191950397Sobrien && ! (flag_stack_check && ! STACK_CHECK_BUILTIN 192090075Sobrien && 0 < compare_tree_int (DECL_SIZE_UNIT (decl), 192190075Sobrien STACK_CHECK_MAX_VAR_SIZE))) 192218334Speter { 192318334Speter /* Variable of fixed size that goes on the stack. */ 192418334Speter rtx oldaddr = 0; 192518334Speter rtx addr; 192690075Sobrien rtx x; 192718334Speter 192818334Speter /* If we previously made RTL for this decl, it must be an array 192918334Speter whose size was determined by the initializer. 193018334Speter The old address was a register; set that register now 193118334Speter to the proper address. */ 193290075Sobrien if (DECL_RTL_SET_P (decl)) 193318334Speter { 1934169689Skan gcc_assert (MEM_P (DECL_RTL (decl))); 1935169689Skan gcc_assert (REG_P (XEXP (DECL_RTL (decl), 0))); 193618334Speter oldaddr = XEXP (DECL_RTL (decl), 0); 193718334Speter } 193818334Speter 193918334Speter /* Set alignment we actually gave this decl. */ 194018334Speter DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT 194118334Speter : GET_MODE_BITSIZE (DECL_MODE (decl))); 194290075Sobrien DECL_USER_ALIGN (decl) = 0; 194318334Speter 194496263Sobrien x = assign_temp (decl, 1, 1, 1); 194590075Sobrien set_mem_attributes (x, decl, 1); 194690075Sobrien SET_DECL_RTL (decl, x); 194790075Sobrien 194818334Speter if (oldaddr) 194918334Speter { 195018334Speter addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr); 195118334Speter if (addr != oldaddr) 195218334Speter emit_move_insn (oldaddr, addr); 195318334Speter } 195418334Speter } 195518334Speter else 195618334Speter /* Dynamic-size object: must push space on the stack. */ 195718334Speter { 195890075Sobrien rtx address, size, x; 195918334Speter 196018334Speter /* Record the stack pointer on entry to block, if have 196118334Speter not already done so. */ 196290075Sobrien do_pending_stack_adjust (); 196318334Speter 1964169689Skan /* Compute the variable's size, in bytes. This will expand any 1965169689Skan needed SAVE_EXPRs for the first time. */ 1966169689Skan size = expand_normal (DECL_SIZE_UNIT (decl)); 196718334Speter free_temp_slots (); 196818334Speter 196950397Sobrien /* Allocate space on the stack for the variable. Note that 197090075Sobrien DECL_ALIGN says how the variable is to be aligned and we 197150397Sobrien cannot use it to conclude anything about the alignment of 197250397Sobrien the size. */ 197318334Speter address = allocate_dynamic_stack_space (size, NULL_RTX, 197450397Sobrien TYPE_ALIGN (TREE_TYPE (decl))); 197518334Speter 197618334Speter /* Reference the variable indirect through that rtx. */ 197790075Sobrien x = gen_rtx_MEM (DECL_MODE (decl), address); 197890075Sobrien set_mem_attributes (x, decl, 1); 197990075Sobrien SET_DECL_RTL (decl, x); 198018334Speter 198118334Speter 198218334Speter /* Indicate the alignment we actually gave this variable. */ 198318334Speter#ifdef STACK_BOUNDARY 198418334Speter DECL_ALIGN (decl) = STACK_BOUNDARY; 198518334Speter#else 198618334Speter DECL_ALIGN (decl) = BIGGEST_ALIGNMENT; 198718334Speter#endif 198890075Sobrien DECL_USER_ALIGN (decl) = 0; 198918334Speter } 199018334Speter} 199118334Speter 1992169689Skan/* Emit code to save the current value of stack. */ 1993169689Skanrtx 1994169689Skanexpand_stack_save (void) 199518334Speter{ 1996169689Skan rtx ret = NULL_RTX; 199718334Speter 1998169689Skan do_pending_stack_adjust (); 1999169689Skan emit_stack_save (SAVE_BLOCK, &ret, NULL_RTX); 2000169689Skan return ret; 200118334Speter} 200218334Speter 2003169689Skan/* Emit code to restore the current value of stack. */ 2004169689Skanvoid 2005169689Skanexpand_stack_restore (tree var) 200618334Speter{ 2007169689Skan rtx sa = DECL_RTL (var); 200818334Speter 2009169689Skan emit_stack_restore (SAVE_BLOCK, sa, NULL_RTX); 201050397Sobrien} 201118334Speter 201218334Speter/* DECL is an anonymous union. CLEANUP is a cleanup for DECL. 201318334Speter DECL_ELTS is the list of elements that belong to DECL's type. 201418334Speter In each, the TREE_VALUE is a VAR_DECL, and the TREE_PURPOSE a cleanup. */ 201518334Speter 201618334Spetervoid 2017169689Skanexpand_anon_union_decl (tree decl, tree cleanup ATTRIBUTE_UNUSED, 2018169689Skan tree decl_elts) 201918334Speter{ 202018334Speter rtx x; 202190075Sobrien tree t; 202218334Speter 202390075Sobrien /* If any of the elements are addressable, so is the entire union. */ 202490075Sobrien for (t = decl_elts; t; t = TREE_CHAIN (t)) 202590075Sobrien if (TREE_ADDRESSABLE (TREE_VALUE (t))) 202690075Sobrien { 202790075Sobrien TREE_ADDRESSABLE (decl) = 1; 202890075Sobrien break; 202990075Sobrien } 203090075Sobrien 203118334Speter expand_decl (decl); 203218334Speter x = DECL_RTL (decl); 203318334Speter 203490075Sobrien /* Go through the elements, assigning RTL to each. */ 203590075Sobrien for (t = decl_elts; t; t = TREE_CHAIN (t)) 203618334Speter { 203790075Sobrien tree decl_elt = TREE_VALUE (t); 203818334Speter enum machine_mode mode = TYPE_MODE (TREE_TYPE (decl_elt)); 2039169689Skan rtx decl_rtl; 204018334Speter 204196263Sobrien /* If any of the elements are addressable, so is the entire 204296263Sobrien union. */ 204396263Sobrien if (TREE_USED (decl_elt)) 204496263Sobrien TREE_USED (decl) = 1; 204596263Sobrien 204618334Speter /* Propagate the union's alignment to the elements. */ 204718334Speter DECL_ALIGN (decl_elt) = DECL_ALIGN (decl); 204890075Sobrien DECL_USER_ALIGN (decl_elt) = DECL_USER_ALIGN (decl); 204918334Speter 205018334Speter /* If the element has BLKmode and the union doesn't, the union is 205118334Speter aligned such that the element doesn't need to have BLKmode, so 205218334Speter change the element's mode to the appropriate one for its size. */ 205318334Speter if (mode == BLKmode && DECL_MODE (decl) != BLKmode) 205418334Speter DECL_MODE (decl_elt) = mode 205590075Sobrien = mode_for_size_tree (DECL_SIZE (decl_elt), MODE_INT, 1); 205618334Speter 2057169689Skan if (mode == GET_MODE (x)) 2058169689Skan decl_rtl = x; 2059169689Skan else if (MEM_P (x)) 2060169689Skan /* (SUBREG (MEM ...)) at RTL generation time is invalid, so we 2061169689Skan instead create a new MEM rtx with the proper mode. */ 2062169689Skan decl_rtl = adjust_address_nv (x, mode, 0); 2063169689Skan else 206418334Speter { 2065169689Skan gcc_assert (REG_P (x)); 2066169689Skan decl_rtl = gen_lowpart_SUBREG (mode, x); 206718334Speter } 2068169689Skan SET_DECL_RTL (decl_elt, decl_rtl); 206918334Speter } 207018334Speter} 207118334Speter 2072169689Skan/* Do the insertion of a case label into case_list. The labels are 2073169689Skan fed to us in descending order from the sorted vector of case labels used 2074169689Skan in the tree part of the middle end. So the list we construct is 2075169689Skan sorted in ascending order. The bounds on the case range, LOW and HIGH, 2076169689Skan are converted to case's index type TYPE. */ 207718334Speter 2078169689Skanstatic struct case_node * 2079169689Skanadd_case_node (struct case_node *head, tree type, tree low, tree high, 2080169689Skan tree label) 208118334Speter{ 2082169689Skan tree min_value, max_value; 2083169689Skan struct case_node *r; 2084132718Skan 2085169689Skan gcc_assert (TREE_CODE (low) == INTEGER_CST); 2086169689Skan gcc_assert (!high || TREE_CODE (high) == INTEGER_CST); 208718334Speter 2088169689Skan min_value = TYPE_MIN_VALUE (type); 2089169689Skan max_value = TYPE_MAX_VALUE (type); 209050397Sobrien 209190075Sobrien /* If there's no HIGH value, then this is not a case range; it's 209290075Sobrien just a simple case label. But that's just a degenerate case 2093169689Skan range. 2094169689Skan If the bounds are equal, turn this into the one-value case. */ 2095169689Skan if (!high || tree_int_cst_equal (low, high)) 209690075Sobrien { 2097169689Skan /* If the simple case value is unreachable, ignore it. */ 2098169689Skan if ((TREE_CODE (min_value) == INTEGER_CST 2099169689Skan && tree_int_cst_compare (low, min_value) < 0) 2100169689Skan || (TREE_CODE (max_value) == INTEGER_CST 2101169689Skan && tree_int_cst_compare (low, max_value) > 0)) 2102169689Skan return head; 2103169689Skan low = fold_convert (type, low); 2104169689Skan high = low; 210590075Sobrien } 2106169689Skan else 210718334Speter { 2108169689Skan /* If the entire case range is unreachable, ignore it. */ 2109169689Skan if ((TREE_CODE (min_value) == INTEGER_CST 2110169689Skan && tree_int_cst_compare (high, min_value) < 0) 2111169689Skan || (TREE_CODE (max_value) == INTEGER_CST 2112169689Skan && tree_int_cst_compare (low, max_value) > 0)) 2113169689Skan return head; 211450397Sobrien 2115169689Skan /* If the lower bound is less than the index type's minimum 2116169689Skan value, truncate the range bounds. */ 2117169689Skan if (TREE_CODE (min_value) == INTEGER_CST 2118169689Skan && tree_int_cst_compare (low, min_value) < 0) 2119169689Skan low = min_value; 2120169689Skan low = fold_convert (type, low); 212150397Sobrien 2122169689Skan /* If the upper bound is greater than the index type's maximum 2123169689Skan value, truncate the range bounds. */ 2124169689Skan if (TREE_CODE (max_value) == INTEGER_CST 2125169689Skan && tree_int_cst_compare (high, max_value) > 0) 2126169689Skan high = max_value; 2127169689Skan high = fold_convert (type, high); 212818334Speter } 212918334Speter 213018334Speter 2131169689Skan /* Add this label to the chain. Make sure to drop overflow flags. */ 2132132718Skan r = ggc_alloc (sizeof (struct case_node)); 2133169689Skan r->low = build_int_cst_wide (TREE_TYPE (low), TREE_INT_CST_LOW (low), 2134169689Skan TREE_INT_CST_HIGH (low)); 2135169689Skan r->high = build_int_cst_wide (TREE_TYPE (high), TREE_INT_CST_LOW (high), 2136169689Skan TREE_INT_CST_HIGH (high)); 213750397Sobrien r->code_label = label; 2138169689Skan r->parent = r->left = NULL; 2139169689Skan r->right = head; 2140169689Skan return r; 214118334Speter} 214218334Speter 2143132718Skan/* Maximum number of case bit tests. */ 2144132718Skan#define MAX_CASE_BIT_TESTS 3 214590075Sobrien 2146132718Skan/* By default, enable case bit tests on targets with ashlsi3. */ 2147132718Skan#ifndef CASE_USE_BIT_TESTS 2148132718Skan#define CASE_USE_BIT_TESTS (ashl_optab->handlers[word_mode].insn_code \ 2149132718Skan != CODE_FOR_nothing) 2150132718Skan#endif 2151132718Skan 2152132718Skan 2153132718Skan/* A case_bit_test represents a set of case nodes that may be 2154132718Skan selected from using a bit-wise comparison. HI and LO hold 2155132718Skan the integer to be tested against, LABEL contains the label 2156132718Skan to jump to upon success and BITS counts the number of case 2157132718Skan nodes handled by this test, typically the number of bits 2158132718Skan set in HI:LO. */ 2159132718Skan 2160132718Skanstruct case_bit_test 2161132718Skan{ 2162132718Skan HOST_WIDE_INT hi; 2163132718Skan HOST_WIDE_INT lo; 2164132718Skan rtx label; 2165132718Skan int bits; 2166132718Skan}; 2167132718Skan 2168132718Skan/* Determine whether "1 << x" is relatively cheap in word_mode. */ 2169132718Skan 2170132718Skanstatic 2171132718Skanbool lshift_cheap_p (void) 2172132718Skan{ 2173132718Skan static bool init = false; 2174132718Skan static bool cheap = true; 2175132718Skan 2176132718Skan if (!init) 2177132718Skan { 2178132718Skan rtx reg = gen_rtx_REG (word_mode, 10000); 2179132718Skan int cost = rtx_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg), SET); 2180132718Skan cheap = cost < COSTS_N_INSNS (3); 2181132718Skan init = true; 2182132718Skan } 2183132718Skan 2184132718Skan return cheap; 2185132718Skan} 2186132718Skan 2187132718Skan/* Comparison function for qsort to order bit tests by decreasing 2188132718Skan number of case nodes, i.e. the node with the most cases gets 2189132718Skan tested first. */ 2190132718Skan 2191169689Skanstatic int 2192169689Skancase_bit_test_cmp (const void *p1, const void *p2) 2193132718Skan{ 2194132718Skan const struct case_bit_test *d1 = p1; 2195132718Skan const struct case_bit_test *d2 = p2; 2196132718Skan 2197169689Skan if (d2->bits != d1->bits) 2198169689Skan return d2->bits - d1->bits; 2199169689Skan 2200169689Skan /* Stabilize the sort. */ 2201169689Skan return CODE_LABEL_NUMBER (d2->label) - CODE_LABEL_NUMBER (d1->label); 2202132718Skan} 2203132718Skan 2204132718Skan/* Expand a switch statement by a short sequence of bit-wise 2205132718Skan comparisons. "switch(x)" is effectively converted into 2206132718Skan "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are 2207132718Skan integer constants. 2208132718Skan 2209132718Skan INDEX_EXPR is the value being switched on, which is of 2210132718Skan type INDEX_TYPE. MINVAL is the lowest case value of in 2211132718Skan the case nodes, of INDEX_TYPE type, and RANGE is highest 2212132718Skan value minus MINVAL, also of type INDEX_TYPE. NODES is 2213132718Skan the set of case nodes, and DEFAULT_LABEL is the label to 2214132718Skan branch to should none of the cases match. 2215132718Skan 2216132718Skan There *MUST* be MAX_CASE_BIT_TESTS or less unique case 2217132718Skan node targets. */ 2218132718Skan 2219132718Skanstatic void 2220132718Skanemit_case_bit_tests (tree index_type, tree index_expr, tree minval, 2221132718Skan tree range, case_node_ptr nodes, rtx default_label) 2222132718Skan{ 2223132718Skan struct case_bit_test test[MAX_CASE_BIT_TESTS]; 2224132718Skan enum machine_mode mode; 2225132718Skan rtx expr, index, label; 2226132718Skan unsigned int i,j,lo,hi; 2227132718Skan struct case_node *n; 2228132718Skan unsigned int count; 2229132718Skan 2230132718Skan count = 0; 2231132718Skan for (n = nodes; n; n = n->right) 2232132718Skan { 2233132718Skan label = label_rtx (n->code_label); 2234132718Skan for (i = 0; i < count; i++) 2235169689Skan if (label == test[i].label) 2236132718Skan break; 2237132718Skan 2238132718Skan if (i == count) 2239132718Skan { 2240169689Skan gcc_assert (count < MAX_CASE_BIT_TESTS); 2241169689Skan test[i].hi = 0; 2242169689Skan test[i].lo = 0; 2243132718Skan test[i].label = label; 2244132718Skan test[i].bits = 1; 2245132718Skan count++; 2246132718Skan } 2247132718Skan else 2248132718Skan test[i].bits++; 2249132718Skan 2250169689Skan lo = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 2251169689Skan n->low, minval), 1); 2252169689Skan hi = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 2253169689Skan n->high, minval), 1); 2254132718Skan for (j = lo; j <= hi; j++) 2255132718Skan if (j >= HOST_BITS_PER_WIDE_INT) 2256132718Skan test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT); 2257132718Skan else 2258132718Skan test[i].lo |= (HOST_WIDE_INT) 1 << j; 2259132718Skan } 2260132718Skan 2261132718Skan qsort (test, count, sizeof(*test), case_bit_test_cmp); 2262132718Skan 2263169689Skan index_expr = fold_build2 (MINUS_EXPR, index_type, 2264169689Skan fold_convert (index_type, index_expr), 2265169689Skan fold_convert (index_type, minval)); 2266169689Skan index = expand_normal (index_expr); 2267132718Skan do_pending_stack_adjust (); 2268132718Skan 2269132718Skan mode = TYPE_MODE (index_type); 2270169689Skan expr = expand_normal (range); 2271132718Skan emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1, 2272132718Skan default_label); 2273132718Skan 2274132718Skan index = convert_to_mode (word_mode, index, 0); 2275132718Skan index = expand_binop (word_mode, ashl_optab, const1_rtx, 2276132718Skan index, NULL_RTX, 1, OPTAB_WIDEN); 2277132718Skan 2278132718Skan for (i = 0; i < count; i++) 2279132718Skan { 2280132718Skan expr = immed_double_const (test[i].lo, test[i].hi, word_mode); 2281132718Skan expr = expand_binop (word_mode, and_optab, index, expr, 2282132718Skan NULL_RTX, 1, OPTAB_WIDEN); 2283132718Skan emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX, 2284132718Skan word_mode, 1, test[i].label); 2285132718Skan } 2286132718Skan 2287132718Skan emit_jump (default_label); 2288132718Skan} 2289132718Skan 2290169689Skan#ifndef HAVE_casesi 2291169689Skan#define HAVE_casesi 0 2292169689Skan#endif 2293169689Skan 2294169689Skan#ifndef HAVE_tablejump 2295169689Skan#define HAVE_tablejump 0 2296169689Skan#endif 2297169689Skan 2298169689Skan/* Terminate a case (Pascal/Ada) or switch (C) statement 229918334Speter in which ORIG_INDEX is the expression to be tested. 230096263Sobrien If ORIG_TYPE is not NULL, it is the original ORIG_INDEX 230196263Sobrien type as given in the source before any compiler conversions. 230218334Speter Generate the code to test it and jump to the right place. */ 230318334Speter 230418334Spetervoid 2305169689Skanexpand_case (tree exp) 230618334Speter{ 230790075Sobrien tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE; 230818334Speter rtx default_label = 0; 2309169689Skan struct case_node *n; 2310132718Skan unsigned int count, uniq; 231118334Speter rtx index; 231218334Speter rtx table_label; 231318334Speter int ncases; 231418334Speter rtx *labelvec; 2315169689Skan int i, fail; 2316132718Skan rtx before_case, end, lab; 231718334Speter 2318169689Skan tree vec = SWITCH_LABELS (exp); 2319169689Skan tree orig_type = TREE_TYPE (exp); 2320169689Skan tree index_expr = SWITCH_COND (exp); 2321169689Skan tree index_type = TREE_TYPE (index_expr); 2322169689Skan int unsignedp = TYPE_UNSIGNED (index_type); 232390075Sobrien 2324169689Skan /* The insn after which the case dispatch should finally 2325169689Skan be emitted. Zero for a dummy. */ 2326169689Skan rtx start; 232718334Speter 2328169689Skan /* A list of case labels; it is first built as a list and it may then 2329169689Skan be rearranged into a nearly balanced binary tree. */ 2330169689Skan struct case_node *case_list = 0; 2331169689Skan 2332169689Skan /* Label to jump to if no case matches. */ 2333169689Skan tree default_label_decl; 2334169689Skan 2335169689Skan /* The switch body is lowered in gimplify.c, we should never have 2336169689Skan switches with a non-NULL SWITCH_BODY here. */ 2337169689Skan gcc_assert (!SWITCH_BODY (exp)); 2338169689Skan gcc_assert (SWITCH_LABELS (exp)); 2339169689Skan 234018334Speter do_pending_stack_adjust (); 234118334Speter 234218334Speter /* An ERROR_MARK occurs for various reasons including invalid data type. */ 234318334Speter if (index_type != error_mark_node) 234418334Speter { 2345169689Skan tree elt; 2346169689Skan bitmap label_bitmap; 234718334Speter 2348169689Skan /* cleanup_tree_cfg removes all SWITCH_EXPR with their index 2349169689Skan expressions being INTEGER_CST. */ 2350169689Skan gcc_assert (TREE_CODE (index_expr) != INTEGER_CST); 2351117395Skan 2352169689Skan /* The default case is at the end of TREE_VEC. */ 2353169689Skan elt = TREE_VEC_ELT (vec, TREE_VEC_LENGTH (vec) - 1); 2354169689Skan gcc_assert (!CASE_HIGH (elt)); 2355169689Skan gcc_assert (!CASE_LOW (elt)); 2356169689Skan default_label_decl = CASE_LABEL (elt); 2357169689Skan 2358169689Skan for (i = TREE_VEC_LENGTH (vec) - 1; --i >= 0; ) 235918334Speter { 2360169689Skan tree low, high; 2361169689Skan elt = TREE_VEC_ELT (vec, i); 2362169689Skan 2363169689Skan low = CASE_LOW (elt); 2364169689Skan gcc_assert (low); 2365169689Skan high = CASE_HIGH (elt); 2366169689Skan 2367169689Skan /* Discard empty ranges. */ 2368169689Skan if (high && INT_CST_LT (high, low)) 2369169689Skan continue; 2370169689Skan 2371169689Skan case_list = add_case_node (case_list, index_type, low, high, 2372169689Skan CASE_LABEL (elt)); 237318334Speter } 237418334Speter 237518334Speter 2376169689Skan before_case = start = get_last_insn (); 2377169689Skan default_label = label_rtx (default_label_decl); 237850397Sobrien 2379169689Skan /* Get upper and lower bounds of case values. */ 238018334Speter 2381132718Skan uniq = 0; 238218334Speter count = 0; 2383169689Skan label_bitmap = BITMAP_ALLOC (NULL); 2384169689Skan for (n = case_list; n; n = n->right) 238518334Speter { 238618334Speter /* Count the elements and track the largest and smallest 238718334Speter of them (treating them as signed even if they are not). */ 238818334Speter if (count++ == 0) 238918334Speter { 239018334Speter minval = n->low; 239118334Speter maxval = n->high; 239218334Speter } 239318334Speter else 239418334Speter { 239518334Speter if (INT_CST_LT (n->low, minval)) 239618334Speter minval = n->low; 239718334Speter if (INT_CST_LT (maxval, n->high)) 239818334Speter maxval = n->high; 239918334Speter } 240018334Speter /* A range counts double, since it requires two compares. */ 240118334Speter if (! tree_int_cst_equal (n->low, n->high)) 240218334Speter count++; 2403132718Skan 2404169689Skan /* If we have not seen this label yet, then increase the 2405169689Skan number of unique case node targets seen. */ 2406132718Skan lab = label_rtx (n->code_label); 2407169689Skan if (!bitmap_bit_p (label_bitmap, CODE_LABEL_NUMBER (lab))) 2408169689Skan { 2409169689Skan bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab)); 2410169689Skan uniq++; 2411169689Skan } 241218334Speter } 241318334Speter 2414169689Skan BITMAP_FREE (label_bitmap); 241518334Speter 2416169689Skan /* cleanup_tree_cfg removes all SWITCH_EXPR with a single 2417169689Skan destination, such as one with a default case only. However, 2418169689Skan it doesn't remove cases that are out of range for the switch 2419169689Skan type, so we may still get a zero here. */ 242018334Speter if (count == 0) 242118334Speter { 242218334Speter emit_jump (default_label); 2423169689Skan return; 242418334Speter } 242518334Speter 2426169689Skan /* Compute span of values. */ 2427169689Skan range = fold_build2 (MINUS_EXPR, index_type, maxval, minval); 2428169689Skan 2429132718Skan /* Try implementing this switch statement by a short sequence of 2430132718Skan bit-wise comparisons. However, we let the binary-tree case 2431132718Skan below handle constant index expressions. */ 2432169689Skan if (CASE_USE_BIT_TESTS 2433169689Skan && ! TREE_CONSTANT (index_expr) 2434169689Skan && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0 2435169689Skan && compare_tree_int (range, 0) > 0 2436169689Skan && lshift_cheap_p () 2437169689Skan && ((uniq == 1 && count >= 3) 2438169689Skan || (uniq == 2 && count >= 5) 2439169689Skan || (uniq == 3 && count >= 6))) 2440132718Skan { 2441132718Skan /* Optimize the case where all the case values fit in a 2442132718Skan word without having to subtract MINVAL. In this case, 2443132718Skan we can optimize away the subtraction. */ 2444132718Skan if (compare_tree_int (minval, 0) > 0 2445132718Skan && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0) 2446132718Skan { 2447169689Skan minval = build_int_cst (index_type, 0); 2448132718Skan range = maxval; 2449132718Skan } 2450132718Skan emit_case_bit_tests (index_type, index_expr, minval, range, 2451169689Skan case_list, default_label); 2452132718Skan } 2453132718Skan 245418334Speter /* If range of values is much bigger than number of values, 245518334Speter make a sequence of conditional branches instead of a dispatch. 245618334Speter If the switch-index is a constant, do it this way 245718334Speter because we can optimize it. */ 245818334Speter 245990075Sobrien else if (count < case_values_threshold () 2460132718Skan || compare_tree_int (range, 2461132718Skan (optimize_size ? 3 : 10) * count) > 0 246290075Sobrien /* RANGE may be signed, and really large ranges will show up 246390075Sobrien as negative numbers. */ 246490075Sobrien || compare_tree_int (range, 0) < 0 246550397Sobrien#ifndef ASM_OUTPUT_ADDR_DIFF_ELT 246650397Sobrien || flag_pic 246750397Sobrien#endif 2468169689Skan || !flag_jump_tables 2469169689Skan || TREE_CONSTANT (index_expr) 2470169689Skan /* If neither casesi or tablejump is available, we can 2471169689Skan only go this way. */ 2472169689Skan || (!HAVE_casesi && !HAVE_tablejump)) 247318334Speter { 2474169689Skan index = expand_normal (index_expr); 247518334Speter 247618334Speter /* If the index is a short or char that we do not have 247718334Speter an insn to handle comparisons directly, convert it to 247818334Speter a full integer now, rather than letting each comparison 247918334Speter generate the conversion. */ 248018334Speter 248118334Speter if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT 248290075Sobrien && ! have_insn_for (COMPARE, GET_MODE (index))) 248318334Speter { 248418334Speter enum machine_mode wider_mode; 248518334Speter for (wider_mode = GET_MODE (index); wider_mode != VOIDmode; 248618334Speter wider_mode = GET_MODE_WIDER_MODE (wider_mode)) 248790075Sobrien if (have_insn_for (COMPARE, wider_mode)) 248818334Speter { 248918334Speter index = convert_to_mode (wider_mode, index, unsignedp); 249018334Speter break; 249118334Speter } 249218334Speter } 249318334Speter 249418334Speter do_pending_stack_adjust (); 249518334Speter 2496169689Skan if (MEM_P (index)) 249718334Speter index = copy_to_reg (index); 249818334Speter 2499169689Skan /* We generate a binary decision tree to select the 2500169689Skan appropriate target code. This is done as follows: 250118334Speter 2502169689Skan The list of cases is rearranged into a binary tree, 2503169689Skan nearly optimal assuming equal probability for each case. 250418334Speter 2505169689Skan The tree is transformed into RTL, eliminating 2506169689Skan redundant test conditions at the same time. 250718334Speter 2508169689Skan If program flow could reach the end of the 2509169689Skan decision tree an unconditional jump to the 2510169689Skan default code is emitted. */ 251118334Speter 2512169689Skan use_cost_table 2513169689Skan = (TREE_CODE (orig_type) != ENUMERAL_TYPE 2514169689Skan && estimate_case_costs (case_list)); 2515169689Skan balance_case_nodes (&case_list, NULL); 2516169689Skan emit_case_nodes (index, case_list, default_label, index_type); 2517169689Skan emit_jump (default_label); 251818334Speter } 251918334Speter else 252018334Speter { 2521132718Skan table_label = gen_label_rtx (); 252290075Sobrien if (! try_casesi (index_type, index_expr, minval, range, 252390075Sobrien table_label, default_label)) 252418334Speter { 2525169689Skan bool ok; 252618334Speter 2527117395Skan /* Index jumptables from zero for suitable values of 252890075Sobrien minval to avoid a subtraction. */ 2529117395Skan if (! optimize_size 2530117395Skan && compare_tree_int (minval, 0) > 0 2531117395Skan && compare_tree_int (minval, 3) < 0) 2532117395Skan { 2533169689Skan minval = build_int_cst (index_type, 0); 2534117395Skan range = maxval; 2535117395Skan } 253618334Speter 2537169689Skan ok = try_tablejump (index_type, index_expr, minval, range, 2538169689Skan table_label, default_label); 2539169689Skan gcc_assert (ok); 254018334Speter } 2541117395Skan 254218334Speter /* Get table of labels to jump to, in order of case index. */ 254318334Speter 254490075Sobrien ncases = tree_low_cst (range, 0) + 1; 2545132718Skan labelvec = alloca (ncases * sizeof (rtx)); 2546132718Skan memset (labelvec, 0, ncases * sizeof (rtx)); 254718334Speter 2548169689Skan for (n = case_list; n; n = n->right) 254918334Speter { 255090075Sobrien /* Compute the low and high bounds relative to the minimum 255190075Sobrien value since that should fit in a HOST_WIDE_INT while the 255290075Sobrien actual values may not. */ 255390075Sobrien HOST_WIDE_INT i_low 2554169689Skan = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 2555169689Skan n->low, minval), 1); 255690075Sobrien HOST_WIDE_INT i_high 2557169689Skan = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, 2558169689Skan n->high, minval), 1); 255990075Sobrien HOST_WIDE_INT i; 256018334Speter 256190075Sobrien for (i = i_low; i <= i_high; i ++) 256290075Sobrien labelvec[i] 256390075Sobrien = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label)); 256418334Speter } 256518334Speter 256618334Speter /* Fill in the gaps with the default. */ 256718334Speter for (i = 0; i < ncases; i++) 256818334Speter if (labelvec[i] == 0) 256950397Sobrien labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label); 257018334Speter 2571132718Skan /* Output the table. */ 257218334Speter emit_label (table_label); 257318334Speter 257450397Sobrien if (CASE_VECTOR_PC_RELATIVE || flag_pic) 257550397Sobrien emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE, 257650397Sobrien gen_rtx_LABEL_REF (Pmode, table_label), 257750397Sobrien gen_rtvec_v (ncases, labelvec), 257890075Sobrien const0_rtx, const0_rtx)); 257918334Speter else 258050397Sobrien emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE, 258150397Sobrien gen_rtvec_v (ncases, labelvec))); 258218334Speter 2583169689Skan /* Record no drop-through after the table. */ 258418334Speter emit_barrier (); 258518334Speter } 258618334Speter 258790075Sobrien before_case = NEXT_INSN (before_case); 258890075Sobrien end = get_last_insn (); 2589169689Skan fail = squeeze_notes (&before_case, &end); 2590169689Skan gcc_assert (!fail); 2591169689Skan reorder_insns (before_case, end, start); 259218334Speter } 259318334Speter 259418334Speter free_temp_slots (); 259518334Speter} 259618334Speter 2597169689Skan/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */ 259818334Speter 259918334Speterstatic void 2600169689Skando_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label, 2601169689Skan int unsignedp) 260218334Speter{ 2603169689Skan do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode, 2604169689Skan NULL_RTX, NULL_RTX, label); 260518334Speter} 260618334Speter 260718334Speter/* Not all case values are encountered equally. This function 260818334Speter uses a heuristic to weight case labels, in cases where that 260918334Speter looks like a reasonable thing to do. 261018334Speter 261118334Speter Right now, all we try to guess is text, and we establish the 261218334Speter following weights: 261318334Speter 261418334Speter chars above space: 16 261518334Speter digits: 16 261618334Speter default: 12 261718334Speter space, punct: 8 261818334Speter tab: 4 261918334Speter newline: 2 262018334Speter other "\" chars: 1 262118334Speter remaining chars: 0 262218334Speter 262318334Speter If we find any cases in the switch that are not either -1 or in the range 262418334Speter of valid ASCII characters, or are control characters other than those 262518334Speter commonly used with "\", don't treat this switch scanning text. 262618334Speter 262718334Speter Return 1 if these nodes are suitable for cost estimation, otherwise 262818334Speter return 0. */ 262918334Speter 263018334Speterstatic int 2631132718Skanestimate_case_costs (case_node_ptr node) 263218334Speter{ 263390075Sobrien tree min_ascii = integer_minus_one_node; 2634169689Skan tree max_ascii = build_int_cst (TREE_TYPE (node->high), 127); 263518334Speter case_node_ptr n; 263618334Speter int i; 263718334Speter 263818334Speter /* If we haven't already made the cost table, make it now. Note that the 263918334Speter lower bound of the table is -1, not zero. */ 264018334Speter 264190075Sobrien if (! cost_table_initialized) 264218334Speter { 264390075Sobrien cost_table_initialized = 1; 264418334Speter 264518334Speter for (i = 0; i < 128; i++) 264618334Speter { 264750397Sobrien if (ISALNUM (i)) 264890075Sobrien COST_TABLE (i) = 16; 264950397Sobrien else if (ISPUNCT (i)) 265090075Sobrien COST_TABLE (i) = 8; 265150397Sobrien else if (ISCNTRL (i)) 265290075Sobrien COST_TABLE (i) = -1; 265318334Speter } 265418334Speter 265590075Sobrien COST_TABLE (' ') = 8; 265690075Sobrien COST_TABLE ('\t') = 4; 265790075Sobrien COST_TABLE ('\0') = 4; 265890075Sobrien COST_TABLE ('\n') = 2; 265990075Sobrien COST_TABLE ('\f') = 1; 266090075Sobrien COST_TABLE ('\v') = 1; 266190075Sobrien COST_TABLE ('\b') = 1; 266218334Speter } 266318334Speter 266418334Speter /* See if all the case expressions look like text. It is text if the 266518334Speter constant is >= -1 and the highest constant is <= 127. Do all comparisons 266618334Speter as signed arithmetic since we don't want to ever access cost_table with a 266718334Speter value less than -1. Also check that none of the constants in a range 266818334Speter are strange control characters. */ 266918334Speter 267018334Speter for (n = node; n; n = n->right) 267118334Speter { 267218334Speter if ((INT_CST_LT (n->low, min_ascii)) || INT_CST_LT (max_ascii, n->high)) 267318334Speter return 0; 267418334Speter 267590075Sobrien for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low); 267690075Sobrien i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++) 267790075Sobrien if (COST_TABLE (i) < 0) 267818334Speter return 0; 267918334Speter } 268018334Speter 268118334Speter /* All interesting values are within the range of interesting 268218334Speter ASCII characters. */ 268318334Speter return 1; 268418334Speter} 268518334Speter 268618334Speter/* Take an ordered list of case nodes 268718334Speter and transform them into a near optimal binary tree, 268818334Speter on the assumption that any target code selection value is as 268918334Speter likely as any other. 269018334Speter 269118334Speter The transformation is performed by splitting the ordered 269218334Speter list into two equal sections plus a pivot. The parts are 269318334Speter then attached to the pivot as left and right branches. Each 269450397Sobrien branch is then transformed recursively. */ 269518334Speter 269618334Speterstatic void 2697132718Skanbalance_case_nodes (case_node_ptr *head, case_node_ptr parent) 269818334Speter{ 269990075Sobrien case_node_ptr np; 270018334Speter 270118334Speter np = *head; 270218334Speter if (np) 270318334Speter { 270418334Speter int cost = 0; 270518334Speter int i = 0; 270618334Speter int ranges = 0; 270790075Sobrien case_node_ptr *npp; 270818334Speter case_node_ptr left; 270918334Speter 271018334Speter /* Count the number of entries on branch. Also count the ranges. */ 271118334Speter 271218334Speter while (np) 271318334Speter { 271418334Speter if (!tree_int_cst_equal (np->low, np->high)) 271518334Speter { 271618334Speter ranges++; 271718334Speter if (use_cost_table) 271890075Sobrien cost += COST_TABLE (TREE_INT_CST_LOW (np->high)); 271918334Speter } 272018334Speter 272118334Speter if (use_cost_table) 272290075Sobrien cost += COST_TABLE (TREE_INT_CST_LOW (np->low)); 272318334Speter 272418334Speter i++; 272518334Speter np = np->right; 272618334Speter } 272718334Speter 272818334Speter if (i > 2) 272918334Speter { 273018334Speter /* Split this list if it is long enough for that to help. */ 273118334Speter npp = head; 273218334Speter left = *npp; 273318334Speter if (use_cost_table) 273418334Speter { 273518334Speter /* Find the place in the list that bisects the list's total cost, 273618334Speter Here I gets half the total cost. */ 273718334Speter int n_moved = 0; 273818334Speter i = (cost + 1) / 2; 273918334Speter while (1) 274018334Speter { 274118334Speter /* Skip nodes while their cost does not reach that amount. */ 274218334Speter if (!tree_int_cst_equal ((*npp)->low, (*npp)->high)) 274390075Sobrien i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high)); 274490075Sobrien i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low)); 274518334Speter if (i <= 0) 274618334Speter break; 274718334Speter npp = &(*npp)->right; 274818334Speter n_moved += 1; 274918334Speter } 275018334Speter if (n_moved == 0) 275118334Speter { 275218334Speter /* Leave this branch lopsided, but optimize left-hand 275318334Speter side and fill in `parent' fields for right-hand side. */ 275418334Speter np = *head; 275518334Speter np->parent = parent; 275618334Speter balance_case_nodes (&np->left, np); 275718334Speter for (; np->right; np = np->right) 275818334Speter np->right->parent = np; 275918334Speter return; 276018334Speter } 276118334Speter } 276218334Speter /* If there are just three nodes, split at the middle one. */ 276318334Speter else if (i == 3) 276418334Speter npp = &(*npp)->right; 276518334Speter else 276618334Speter { 276718334Speter /* Find the place in the list that bisects the list's total cost, 276818334Speter where ranges count as 2. 276918334Speter Here I gets half the total cost. */ 277018334Speter i = (i + ranges + 1) / 2; 277118334Speter while (1) 277218334Speter { 277318334Speter /* Skip nodes while their cost does not reach that amount. */ 277418334Speter if (!tree_int_cst_equal ((*npp)->low, (*npp)->high)) 277518334Speter i--; 277618334Speter i--; 277718334Speter if (i <= 0) 277818334Speter break; 277918334Speter npp = &(*npp)->right; 278018334Speter } 278118334Speter } 278218334Speter *head = np = *npp; 278318334Speter *npp = 0; 278418334Speter np->parent = parent; 278518334Speter np->left = left; 278618334Speter 278718334Speter /* Optimize each of the two split parts. */ 278818334Speter balance_case_nodes (&np->left, np); 278918334Speter balance_case_nodes (&np->right, np); 279018334Speter } 279118334Speter else 279218334Speter { 279318334Speter /* Else leave this branch as one level, 279418334Speter but fill in `parent' fields. */ 279518334Speter np = *head; 279618334Speter np->parent = parent; 279718334Speter for (; np->right; np = np->right) 279818334Speter np->right->parent = np; 279918334Speter } 280018334Speter } 280118334Speter} 280218334Speter 280318334Speter/* Search the parent sections of the case node tree 280418334Speter to see if a test for the lower bound of NODE would be redundant. 280518334Speter INDEX_TYPE is the type of the index expression. 280618334Speter 280718334Speter The instructions to generate the case decision tree are 280818334Speter output in the same order as nodes are processed so it is 280918334Speter known that if a parent node checks the range of the current 281018334Speter node minus one that the current node is bounded at its lower 281118334Speter span. Thus the test would be redundant. */ 281218334Speter 281318334Speterstatic int 2814132718Skannode_has_low_bound (case_node_ptr node, tree index_type) 281518334Speter{ 281618334Speter tree low_minus_one; 281718334Speter case_node_ptr pnode; 281818334Speter 281918334Speter /* If the lower bound of this node is the lowest value in the index type, 282018334Speter we need not test it. */ 282118334Speter 282218334Speter if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type))) 282318334Speter return 1; 282418334Speter 282518334Speter /* If this node has a left branch, the value at the left must be less 282618334Speter than that at this node, so it cannot be bounded at the bottom and 282718334Speter we need not bother testing any further. */ 282818334Speter 282918334Speter if (node->left) 283018334Speter return 0; 283118334Speter 2832169689Skan low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), 2833169689Skan node->low, 2834169689Skan build_int_cst (TREE_TYPE (node->low), 1)); 283518334Speter 283618334Speter /* If the subtraction above overflowed, we can't verify anything. 283718334Speter Otherwise, look for a parent that tests our value - 1. */ 283818334Speter 283918334Speter if (! tree_int_cst_lt (low_minus_one, node->low)) 284018334Speter return 0; 284118334Speter 284218334Speter for (pnode = node->parent; pnode; pnode = pnode->parent) 284318334Speter if (tree_int_cst_equal (low_minus_one, pnode->high)) 284418334Speter return 1; 284518334Speter 284618334Speter return 0; 284718334Speter} 284818334Speter 284918334Speter/* Search the parent sections of the case node tree 285018334Speter to see if a test for the upper bound of NODE would be redundant. 285118334Speter INDEX_TYPE is the type of the index expression. 285218334Speter 285318334Speter The instructions to generate the case decision tree are 285418334Speter output in the same order as nodes are processed so it is 285518334Speter known that if a parent node checks the range of the current 285618334Speter node plus one that the current node is bounded at its upper 285718334Speter span. Thus the test would be redundant. */ 285818334Speter 285918334Speterstatic int 2860132718Skannode_has_high_bound (case_node_ptr node, tree index_type) 286118334Speter{ 286218334Speter tree high_plus_one; 286318334Speter case_node_ptr pnode; 286418334Speter 286550397Sobrien /* If there is no upper bound, obviously no test is needed. */ 286650397Sobrien 286750397Sobrien if (TYPE_MAX_VALUE (index_type) == NULL) 286850397Sobrien return 1; 286950397Sobrien 287018334Speter /* If the upper bound of this node is the highest value in the type 287118334Speter of the index expression, we need not test against it. */ 287218334Speter 287318334Speter if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type))) 287418334Speter return 1; 287518334Speter 287618334Speter /* If this node has a right branch, the value at the right must be greater 287718334Speter than that at this node, so it cannot be bounded at the top and 287818334Speter we need not bother testing any further. */ 287918334Speter 288018334Speter if (node->right) 288118334Speter return 0; 288218334Speter 2883169689Skan high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), 2884169689Skan node->high, 2885169689Skan build_int_cst (TREE_TYPE (node->high), 1)); 288618334Speter 288718334Speter /* If the addition above overflowed, we can't verify anything. 288818334Speter Otherwise, look for a parent that tests our value + 1. */ 288918334Speter 289018334Speter if (! tree_int_cst_lt (node->high, high_plus_one)) 289118334Speter return 0; 289218334Speter 289318334Speter for (pnode = node->parent; pnode; pnode = pnode->parent) 289418334Speter if (tree_int_cst_equal (high_plus_one, pnode->low)) 289518334Speter return 1; 289618334Speter 289718334Speter return 0; 289818334Speter} 289918334Speter 290018334Speter/* Search the parent sections of the 290118334Speter case node tree to see if both tests for the upper and lower 290218334Speter bounds of NODE would be redundant. */ 290318334Speter 290418334Speterstatic int 2905132718Skannode_is_bounded (case_node_ptr node, tree index_type) 290618334Speter{ 290718334Speter return (node_has_low_bound (node, index_type) 290818334Speter && node_has_high_bound (node, index_type)); 290918334Speter} 291018334Speter 291118334Speter/* Emit step-by-step code to select a case for the value of INDEX. 291218334Speter The thus generated decision tree follows the form of the 291318334Speter case-node binary tree NODE, whose nodes represent test conditions. 291418334Speter INDEX_TYPE is the type of the index of the switch. 291518334Speter 291618334Speter Care is taken to prune redundant tests from the decision tree 291718334Speter by detecting any boundary conditions already checked by 291818334Speter emitted rtx. (See node_has_high_bound, node_has_low_bound 291918334Speter and node_is_bounded, above.) 292018334Speter 292118334Speter Where the test conditions can be shown to be redundant we emit 292218334Speter an unconditional jump to the target code. As a further 292318334Speter optimization, the subordinates of a tree node are examined to 292418334Speter check for bounded nodes. In this case conditional and/or 292518334Speter unconditional jumps as a result of the boundary check for the 292618334Speter current node are arranged to target the subordinates associated 292750397Sobrien code for out of bound conditions on the current node. 292818334Speter 292918334Speter We can assume that when control reaches the code generated here, 293018334Speter the index value has already been compared with the parents 293118334Speter of this node, and determined to be on the same side of each parent 293218334Speter as this node is. Thus, if this node tests for the value 51, 293318334Speter and a parent tested for 52, we don't need to consider 293418334Speter the possibility of a value greater than 51. If another parent 293518334Speter tests for the value 50, then this node need not test anything. */ 293618334Speter 293718334Speterstatic void 2938132718Skanemit_case_nodes (rtx index, case_node_ptr node, rtx default_label, 2939132718Skan tree index_type) 294018334Speter{ 294118334Speter /* If INDEX has an unsigned type, we must make unsigned branches. */ 2942169689Skan int unsignedp = TYPE_UNSIGNED (index_type); 294318334Speter enum machine_mode mode = GET_MODE (index); 294490075Sobrien enum machine_mode imode = TYPE_MODE (index_type); 294518334Speter 2946169689Skan /* Handle indices detected as constant during RTL expansion. */ 2947169689Skan if (mode == VOIDmode) 2948169689Skan mode = imode; 2949169689Skan 295018334Speter /* See if our parents have already tested everything for us. 295118334Speter If they have, emit an unconditional jump for this node. */ 295218334Speter if (node_is_bounded (node, index_type)) 295318334Speter emit_jump (label_rtx (node->code_label)); 295418334Speter 295518334Speter else if (tree_int_cst_equal (node->low, node->high)) 295618334Speter { 295718334Speter /* Node is single valued. First see if the index expression matches 295850397Sobrien this node and then check our children, if any. */ 295918334Speter 2960169689Skan do_jump_if_equal (mode, index, 296190075Sobrien convert_modes (mode, imode, 2962169689Skan expand_normal (node->low), 296390075Sobrien unsignedp), 296418334Speter label_rtx (node->code_label), unsignedp); 296518334Speter 296618334Speter if (node->right != 0 && node->left != 0) 296718334Speter { 296818334Speter /* This node has children on both sides. 296918334Speter Dispatch to one side or the other 297018334Speter by comparing the index value with this node's value. 297118334Speter If one subtree is bounded, check that one first, 297218334Speter so we can avoid real branches in the tree. */ 297318334Speter 297418334Speter if (node_is_bounded (node->right, index_type)) 297518334Speter { 297690075Sobrien emit_cmp_and_jump_insns (index, 297790075Sobrien convert_modes 297890075Sobrien (mode, imode, 2979169689Skan expand_normal (node->high), 298090075Sobrien unsignedp), 298190075Sobrien GT, NULL_RTX, mode, unsignedp, 298290075Sobrien label_rtx (node->right->code_label)); 298318334Speter emit_case_nodes (index, node->left, default_label, index_type); 298418334Speter } 298518334Speter 298618334Speter else if (node_is_bounded (node->left, index_type)) 298718334Speter { 298890075Sobrien emit_cmp_and_jump_insns (index, 298990075Sobrien convert_modes 299090075Sobrien (mode, imode, 2991169689Skan expand_normal (node->high), 299290075Sobrien unsignedp), 299390075Sobrien LT, NULL_RTX, mode, unsignedp, 299452284Sobrien label_rtx (node->left->code_label)); 299518334Speter emit_case_nodes (index, node->right, default_label, index_type); 299618334Speter } 299718334Speter 2998169689Skan /* If both children are single-valued cases with no 2999169689Skan children, finish up all the work. This way, we can save 3000169689Skan one ordered comparison. */ 3001169689Skan else if (tree_int_cst_equal (node->right->low, node->right->high) 3002169689Skan && node->right->left == 0 3003169689Skan && node->right->right == 0 3004169689Skan && tree_int_cst_equal (node->left->low, node->left->high) 3005169689Skan && node->left->left == 0 3006169689Skan && node->left->right == 0) 3007169689Skan { 3008169689Skan /* Neither node is bounded. First distinguish the two sides; 3009169689Skan then emit the code for one side at a time. */ 3010169689Skan 3011169689Skan /* See if the value matches what the right hand side 3012169689Skan wants. */ 3013169689Skan do_jump_if_equal (mode, index, 3014169689Skan convert_modes (mode, imode, 3015169689Skan expand_normal (node->right->low), 3016169689Skan unsignedp), 3017169689Skan label_rtx (node->right->code_label), 3018169689Skan unsignedp); 3019169689Skan 3020169689Skan /* See if the value matches what the left hand side 3021169689Skan wants. */ 3022169689Skan do_jump_if_equal (mode, index, 3023169689Skan convert_modes (mode, imode, 3024169689Skan expand_normal (node->left->low), 3025169689Skan unsignedp), 3026169689Skan label_rtx (node->left->code_label), 3027169689Skan unsignedp); 3028169689Skan } 3029169689Skan 303018334Speter else 303118334Speter { 303218334Speter /* Neither node is bounded. First distinguish the two sides; 303318334Speter then emit the code for one side at a time. */ 303418334Speter 303590075Sobrien tree test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE); 303618334Speter 303718334Speter /* See if the value is on the right. */ 303890075Sobrien emit_cmp_and_jump_insns (index, 303990075Sobrien convert_modes 304090075Sobrien (mode, imode, 3041169689Skan expand_normal (node->high), 304290075Sobrien unsignedp), 304390075Sobrien GT, NULL_RTX, mode, unsignedp, 304452284Sobrien label_rtx (test_label)); 304518334Speter 304618334Speter /* Value must be on the left. 304718334Speter Handle the left-hand subtree. */ 304818334Speter emit_case_nodes (index, node->left, default_label, index_type); 304918334Speter /* If left-hand subtree does nothing, 305018334Speter go to default. */ 3051169689Skan emit_jump (default_label); 305218334Speter 305318334Speter /* Code branches here for the right-hand subtree. */ 305418334Speter expand_label (test_label); 305518334Speter emit_case_nodes (index, node->right, default_label, index_type); 305618334Speter } 305718334Speter } 305818334Speter 305918334Speter else if (node->right != 0 && node->left == 0) 306018334Speter { 3061169689Skan /* Here we have a right child but no left so we issue a conditional 306218334Speter branch to default and process the right child. 306318334Speter 3064169689Skan Omit the conditional branch to default if the right child 3065169689Skan does not have any children and is single valued; it would 3066169689Skan cost too much space to save so little time. */ 306718334Speter 306818334Speter if (node->right->right || node->right->left 306918334Speter || !tree_int_cst_equal (node->right->low, node->right->high)) 307018334Speter { 307118334Speter if (!node_has_low_bound (node, index_type)) 307218334Speter { 307390075Sobrien emit_cmp_and_jump_insns (index, 307490075Sobrien convert_modes 307590075Sobrien (mode, imode, 3076169689Skan expand_normal (node->high), 307790075Sobrien unsignedp), 307890075Sobrien LT, NULL_RTX, mode, unsignedp, 307952284Sobrien default_label); 308018334Speter } 308118334Speter 308218334Speter emit_case_nodes (index, node->right, default_label, index_type); 308318334Speter } 308418334Speter else 308518334Speter /* We cannot process node->right normally 308618334Speter since we haven't ruled out the numbers less than 308718334Speter this node's value. So handle node->right explicitly. */ 3088169689Skan do_jump_if_equal (mode, index, 308990075Sobrien convert_modes 309090075Sobrien (mode, imode, 3091169689Skan expand_normal (node->right->low), 309290075Sobrien unsignedp), 309318334Speter label_rtx (node->right->code_label), unsignedp); 309418334Speter } 309518334Speter 309618334Speter else if (node->right == 0 && node->left != 0) 309718334Speter { 309818334Speter /* Just one subtree, on the left. */ 309990075Sobrien if (node->left->left || node->left->right 310018334Speter || !tree_int_cst_equal (node->left->low, node->left->high)) 310118334Speter { 310218334Speter if (!node_has_high_bound (node, index_type)) 310318334Speter { 310490075Sobrien emit_cmp_and_jump_insns (index, 310590075Sobrien convert_modes 310690075Sobrien (mode, imode, 3107169689Skan expand_normal (node->high), 310890075Sobrien unsignedp), 310990075Sobrien GT, NULL_RTX, mode, unsignedp, 311052284Sobrien default_label); 311118334Speter } 311218334Speter 311318334Speter emit_case_nodes (index, node->left, default_label, index_type); 311418334Speter } 311518334Speter else 311618334Speter /* We cannot process node->left normally 311718334Speter since we haven't ruled out the numbers less than 311818334Speter this node's value. So handle node->left explicitly. */ 3119169689Skan do_jump_if_equal (mode, index, 312090075Sobrien convert_modes 312190075Sobrien (mode, imode, 3122169689Skan expand_normal (node->left->low), 312390075Sobrien unsignedp), 312418334Speter label_rtx (node->left->code_label), unsignedp); 312518334Speter } 312618334Speter } 312718334Speter else 312818334Speter { 312918334Speter /* Node is a range. These cases are very similar to those for a single 313018334Speter value, except that we do not start by testing whether this node 313118334Speter is the one to branch to. */ 313218334Speter 313318334Speter if (node->right != 0 && node->left != 0) 313418334Speter { 313518334Speter /* Node has subtrees on both sides. 313618334Speter If the right-hand subtree is bounded, 313718334Speter test for it first, since we can go straight there. 313818334Speter Otherwise, we need to make a branch in the control structure, 313918334Speter then handle the two subtrees. */ 314018334Speter tree test_label = 0; 314118334Speter 314218334Speter if (node_is_bounded (node->right, index_type)) 314318334Speter /* Right hand node is fully bounded so we can eliminate any 314418334Speter testing and branch directly to the target code. */ 314590075Sobrien emit_cmp_and_jump_insns (index, 314690075Sobrien convert_modes 314790075Sobrien (mode, imode, 3148169689Skan expand_normal (node->high), 314990075Sobrien unsignedp), 315090075Sobrien GT, NULL_RTX, mode, unsignedp, 315152284Sobrien label_rtx (node->right->code_label)); 315218334Speter else 315318334Speter { 315418334Speter /* Right hand node requires testing. 315518334Speter Branch to a label where we will handle it later. */ 315618334Speter 315718334Speter test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE); 315890075Sobrien emit_cmp_and_jump_insns (index, 315990075Sobrien convert_modes 316090075Sobrien (mode, imode, 3161169689Skan expand_normal (node->high), 316290075Sobrien unsignedp), 316390075Sobrien GT, NULL_RTX, mode, unsignedp, 316452284Sobrien label_rtx (test_label)); 316518334Speter } 316618334Speter 316718334Speter /* Value belongs to this node or to the left-hand subtree. */ 316818334Speter 316990075Sobrien emit_cmp_and_jump_insns (index, 317090075Sobrien convert_modes 317190075Sobrien (mode, imode, 3172169689Skan expand_normal (node->low), 317390075Sobrien unsignedp), 317490075Sobrien GE, NULL_RTX, mode, unsignedp, 317552284Sobrien label_rtx (node->code_label)); 317618334Speter 317718334Speter /* Handle the left-hand subtree. */ 317818334Speter emit_case_nodes (index, node->left, default_label, index_type); 317918334Speter 318018334Speter /* If right node had to be handled later, do that now. */ 318118334Speter 318218334Speter if (test_label) 318318334Speter { 318418334Speter /* If the left-hand subtree fell through, 318518334Speter don't let it fall into the right-hand subtree. */ 3186169689Skan emit_jump (default_label); 318718334Speter 318818334Speter expand_label (test_label); 318918334Speter emit_case_nodes (index, node->right, default_label, index_type); 319018334Speter } 319118334Speter } 319218334Speter 319318334Speter else if (node->right != 0 && node->left == 0) 319418334Speter { 319518334Speter /* Deal with values to the left of this node, 319618334Speter if they are possible. */ 319718334Speter if (!node_has_low_bound (node, index_type)) 319818334Speter { 319990075Sobrien emit_cmp_and_jump_insns (index, 320090075Sobrien convert_modes 320190075Sobrien (mode, imode, 3202169689Skan expand_normal (node->low), 320390075Sobrien unsignedp), 320490075Sobrien LT, NULL_RTX, mode, unsignedp, 320552284Sobrien default_label); 320618334Speter } 320718334Speter 320818334Speter /* Value belongs to this node or to the right-hand subtree. */ 320918334Speter 321090075Sobrien emit_cmp_and_jump_insns (index, 321190075Sobrien convert_modes 321290075Sobrien (mode, imode, 3213169689Skan expand_normal (node->high), 321490075Sobrien unsignedp), 321590075Sobrien LE, NULL_RTX, mode, unsignedp, 321652284Sobrien label_rtx (node->code_label)); 321718334Speter 321818334Speter emit_case_nodes (index, node->right, default_label, index_type); 321918334Speter } 322018334Speter 322118334Speter else if (node->right == 0 && node->left != 0) 322218334Speter { 322318334Speter /* Deal with values to the right of this node, 322418334Speter if they are possible. */ 322518334Speter if (!node_has_high_bound (node, index_type)) 322618334Speter { 322790075Sobrien emit_cmp_and_jump_insns (index, 322890075Sobrien convert_modes 322990075Sobrien (mode, imode, 3230169689Skan expand_normal (node->high), 323190075Sobrien unsignedp), 323290075Sobrien GT, NULL_RTX, mode, unsignedp, 323352284Sobrien default_label); 323418334Speter } 323518334Speter 323618334Speter /* Value belongs to this node or to the left-hand subtree. */ 323718334Speter 323890075Sobrien emit_cmp_and_jump_insns (index, 323990075Sobrien convert_modes 324090075Sobrien (mode, imode, 3241169689Skan expand_normal (node->low), 324290075Sobrien unsignedp), 324390075Sobrien GE, NULL_RTX, mode, unsignedp, 324452284Sobrien label_rtx (node->code_label)); 324518334Speter 324618334Speter emit_case_nodes (index, node->left, default_label, index_type); 324718334Speter } 324818334Speter 324918334Speter else 325018334Speter { 325118334Speter /* Node has no children so we check low and high bounds to remove 325218334Speter redundant tests. Only one of the bounds can exist, 325318334Speter since otherwise this node is bounded--a case tested already. */ 325490075Sobrien int high_bound = node_has_high_bound (node, index_type); 325590075Sobrien int low_bound = node_has_low_bound (node, index_type); 325618334Speter 325790075Sobrien if (!high_bound && low_bound) 325818334Speter { 325990075Sobrien emit_cmp_and_jump_insns (index, 326090075Sobrien convert_modes 326190075Sobrien (mode, imode, 3262169689Skan expand_normal (node->high), 326390075Sobrien unsignedp), 326490075Sobrien GT, NULL_RTX, mode, unsignedp, 326552284Sobrien default_label); 326618334Speter } 326718334Speter 326890075Sobrien else if (!low_bound && high_bound) 326918334Speter { 327090075Sobrien emit_cmp_and_jump_insns (index, 327190075Sobrien convert_modes 327290075Sobrien (mode, imode, 3273169689Skan expand_normal (node->low), 327490075Sobrien unsignedp), 327590075Sobrien LT, NULL_RTX, mode, unsignedp, 327652284Sobrien default_label); 327718334Speter } 327890075Sobrien else if (!low_bound && !high_bound) 327990075Sobrien { 328090075Sobrien /* Widen LOW and HIGH to the same width as INDEX. */ 3281169689Skan tree type = lang_hooks.types.type_for_mode (mode, unsignedp); 328290075Sobrien tree low = build1 (CONVERT_EXPR, type, node->low); 328390075Sobrien tree high = build1 (CONVERT_EXPR, type, node->high); 328490075Sobrien rtx low_rtx, new_index, new_bound; 328518334Speter 328690075Sobrien /* Instead of doing two branches, emit one unsigned branch for 328790075Sobrien (index-low) > (high-low). */ 3288169689Skan low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL); 328990075Sobrien new_index = expand_simple_binop (mode, MINUS, index, low_rtx, 329090075Sobrien NULL_RTX, unsignedp, 329190075Sobrien OPTAB_WIDEN); 3292169689Skan new_bound = expand_expr (fold_build2 (MINUS_EXPR, type, 3293169689Skan high, low), 3294169689Skan NULL_RTX, mode, EXPAND_NORMAL); 3295117395Skan 329690075Sobrien emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX, 329790075Sobrien mode, 1, default_label); 329890075Sobrien } 329990075Sobrien 330018334Speter emit_jump (label_rtx (node->code_label)); 330118334Speter } 330218334Speter } 330318334Speter} 3304