/* Expands front end tree to back end RTL for GCC | |

Copyright (C) 1987-2013 Free Software Foundation, Inc. | |

This file is part of GCC. | |

GCC is free software; you can redistribute it and/or modify it under | |

the terms of the GNU General Public License as published by the Free | |

Software Foundation; either version 3, or (at your option) any later | |

version. | |

GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |

WARRANTY; without even the implied warranty of MERCHANTABILITY or | |

FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |

for more details. | |

You should have received a copy of the GNU General Public License | |

along with GCC; see the file COPYING3. If not see | |

<http://www.gnu.org/licenses/>. */ | |

/* This file handles the generation of rtl code from tree structure | |

above the level of expressions, using subroutines in exp*.c and emit-rtl.c. | |

The functions whose names start with `expand_' are called by the | |

expander to generate RTL instructions for various kinds of constructs. */ | |

#include "config.h" | |

#include "system.h" | |

#include "coretypes.h" | |

#include "tm.h" | |

#include "rtl.h" | |

#include "hard-reg-set.h" | |

#include "tree.h" | |

#include "tm_p.h" | |

#include "flags.h" | |

#include "except.h" | |

#include "function.h" | |

#include "insn-config.h" | |

#include "expr.h" | |

#include "libfuncs.h" | |

#include "recog.h" | |

#include "machmode.h" | |

#include "diagnostic-core.h" | |

#include "output.h" | |

#include "ggc.h" | |

#include "langhooks.h" | |

#include "predict.h" | |

#include "optabs.h" | |

#include "target.h" | |

#include "gimple.h" | |

#include "regs.h" | |

#include "alloc-pool.h" | |

#include "pretty-print.h" | |

#include "pointer-set.h" | |

#include "params.h" | |

#include "dumpfile.h" | |

/* Functions and data structures for expanding case statements. */ | |

/* Case label structure, used to hold info on labels within case | |

statements. We handle "range" labels; for a single-value label | |

as in C, the high and low limits are the same. | |

We start with a vector of case nodes sorted in ascending order, and | |

the default label as the last element in the vector. Before expanding | |

to RTL, we transform this vector into a list linked via the RIGHT | |

fields in the case_node struct. Nodes with higher case values are | |

later in the list. | |

Switch statements can be output in three forms. A branch table is | |

used if there are more than a few labels and the labels are dense | |

within the range between the smallest and largest case value. If a | |

branch table is used, no further manipulations are done with the case | |

node chain. | |

The alternative to the use of a branch table is to generate a series | |

of compare and jump insns. When that is done, we use the LEFT, RIGHT, | |

and PARENT fields to hold a binary tree. Initially the tree is | |

totally unbalanced, with everything on the right. We balance the tree | |

with nodes on the left having lower case values than the parent | |

and nodes on the right having higher values. We then output the tree | |

in order. | |

For very small, suitable switch statements, we can generate a series | |

of simple bit test and branches instead. */ | |

struct case_node | |

{ | |

struct case_node *left; /* Left son in binary tree */ | |

struct case_node *right; /* Right son in binary tree; also node chain */ | |

struct case_node *parent; /* Parent of node in binary tree */ | |

tree low; /* Lowest index value for this label */ | |

tree high; /* Highest index value for this label */ | |

tree code_label; /* Label to jump to when node matches */ | |

int prob; /* Probability of taking this case. */ | |

/* Probability of reaching subtree rooted at this node */ | |

int subtree_prob; | |

}; | |

typedef struct case_node case_node; | |

typedef struct case_node *case_node_ptr; | |

extern basic_block label_to_block_fn (struct function *, tree); | |

static int n_occurrences (int, const char *); | |

static bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *); | |

static void expand_nl_goto_receiver (void); | |

static bool check_operand_nalternatives (tree, tree); | |

static bool check_unique_operand_names (tree, tree, tree); | |

static char *resolve_operand_name_1 (char *, tree, tree, tree); | |

static void expand_null_return_1 (void); | |

static void expand_value_return (rtx); | |

static void balance_case_nodes (case_node_ptr *, case_node_ptr); | |

static int node_has_low_bound (case_node_ptr, tree); | |

static int node_has_high_bound (case_node_ptr, tree); | |

static int node_is_bounded (case_node_ptr, tree); | |

static void emit_case_nodes (rtx, case_node_ptr, rtx, int, tree); | |

/* Return the rtx-label that corresponds to a LABEL_DECL, | |

creating it if necessary. */ | |

rtx | |

label_rtx (tree label) | |

{ | |

gcc_assert (TREE_CODE (label) == LABEL_DECL); | |

if (!DECL_RTL_SET_P (label)) | |

{ | |

rtx r = gen_label_rtx (); | |

SET_DECL_RTL (label, r); | |

if (FORCED_LABEL (label) || DECL_NONLOCAL (label)) | |

LABEL_PRESERVE_P (r) = 1; | |

} | |

return DECL_RTL (label); | |

} | |

/* As above, but also put it on the forced-reference list of the | |

function that contains it. */ | |

rtx | |

force_label_rtx (tree label) | |

{ | |

rtx ref = label_rtx (label); | |

tree function = decl_function_context (label); | |

gcc_assert (function); | |

forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref, forced_labels); | |

return ref; | |

} | |

/* Add an unconditional jump to LABEL as the next sequential instruction. */ | |

void | |

emit_jump (rtx label) | |

{ | |

do_pending_stack_adjust (); | |

emit_jump_insn (gen_jump (label)); | |

emit_barrier (); | |

} | |

/* Emit code to jump to the address | |

specified by the pointer expression EXP. */ | |

void | |

expand_computed_goto (tree exp) | |

{ | |

rtx x = expand_normal (exp); | |

x = convert_memory_address (Pmode, x); | |

do_pending_stack_adjust (); | |

emit_indirect_jump (x); | |

} | |

/* Handle goto statements and the labels that they can go to. */ | |

/* Specify the location in the RTL code of a label LABEL, | |

which is a LABEL_DECL tree node. | |

This is used for the kind of label that the user can jump to with a | |

goto statement, and for alternatives of a switch or case statement. | |

RTL labels generated for loops and conditionals don't go through here; | |

they are generated directly at the RTL level, by other functions below. | |

Note that this has nothing to do with defining label *names*. | |

Languages vary in how they do that and what that even means. */ | |

void | |

expand_label (tree label) | |

{ | |

rtx label_r = label_rtx (label); | |

do_pending_stack_adjust (); | |

emit_label (label_r); | |

if (DECL_NAME (label)) | |

LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label)); | |

if (DECL_NONLOCAL (label)) | |

{ | |

expand_nl_goto_receiver (); | |

nonlocal_goto_handler_labels | |

= gen_rtx_EXPR_LIST (VOIDmode, label_r, | |

nonlocal_goto_handler_labels); | |

} | |

if (FORCED_LABEL (label)) | |

forced_labels = gen_rtx_EXPR_LIST (VOIDmode, label_r, forced_labels); | |

if (DECL_NONLOCAL (label) || FORCED_LABEL (label)) | |

maybe_set_first_label_num (label_r); | |

} | |

/* Generate RTL code for a `goto' statement with target label LABEL. | |

LABEL should be a LABEL_DECL tree node that was or will later be | |

defined with `expand_label'. */ | |

void | |

expand_goto (tree label) | |

{ | |

#ifdef ENABLE_CHECKING | |

/* Check for a nonlocal goto to a containing function. Should have | |

gotten translated to __builtin_nonlocal_goto. */ | |

tree context = decl_function_context (label); | |

gcc_assert (!context || context == current_function_decl); | |

#endif | |

emit_jump (label_rtx (label)); | |

} | |

/* Return the number of times character C occurs in string S. */ | |

static int | |

n_occurrences (int c, const char *s) | |

{ | |

int n = 0; | |

while (*s) | |

n += (*s++ == c); | |

return n; | |

} | |

/* Generate RTL for an asm statement (explicit assembler code). | |

STRING is a STRING_CST node containing the assembler code text, | |

or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the | |

insn is volatile; don't optimize it. */ | |

static void | |

expand_asm_loc (tree string, int vol, location_t locus) | |

{ | |

rtx body; | |

if (TREE_CODE (string) == ADDR_EXPR) | |

string = TREE_OPERAND (string, 0); | |

body = gen_rtx_ASM_INPUT_loc (VOIDmode, | |

ggc_strdup (TREE_STRING_POINTER (string)), | |

locus); | |

MEM_VOLATILE_P (body) = vol; | |

emit_insn (body); | |

} | |

/* Parse the output constraint pointed to by *CONSTRAINT_P. It is the | |

OPERAND_NUMth output operand, indexed from zero. There are NINPUTS | |

inputs and NOUTPUTS outputs to this extended-asm. Upon return, | |

*ALLOWS_MEM will be TRUE iff the constraint allows the use of a | |

memory operand. Similarly, *ALLOWS_REG will be TRUE iff the | |

constraint allows the use of a register operand. And, *IS_INOUT | |

will be true if the operand is read-write, i.e., if it is used as | |

an input as well as an output. If *CONSTRAINT_P is not in | |

canonical form, it will be made canonical. (Note that `+' will be | |

replaced with `=' as part of this process.) | |

Returns TRUE if all went well; FALSE if an error occurred. */ | |

bool | |

parse_output_constraint (const char **constraint_p, int operand_num, | |

int ninputs, int noutputs, bool *allows_mem, | |

bool *allows_reg, bool *is_inout) | |

{ | |

const char *constraint = *constraint_p; | |

const char *p; | |

/* Assume the constraint doesn't allow the use of either a register | |

or memory. */ | |

*allows_mem = false; | |

*allows_reg = false; | |

/* Allow the `=' or `+' to not be at the beginning of the string, | |

since it wasn't explicitly documented that way, and there is a | |

large body of code that puts it last. Swap the character to | |

the front, so as not to uglify any place else. */ | |

p = strchr (constraint, '='); | |

if (!p) | |

p = strchr (constraint, '+'); | |

/* If the string doesn't contain an `=', issue an error | |

message. */ | |

if (!p) | |

{ | |

error ("output operand constraint lacks %<=%>"); | |

return false; | |

} | |

/* If the constraint begins with `+', then the operand is both read | |

from and written to. */ | |

*is_inout = (*p == '+'); | |

/* Canonicalize the output constraint so that it begins with `='. */ | |

if (p != constraint || *is_inout) | |

{ | |

char *buf; | |

size_t c_len = strlen (constraint); | |

if (p != constraint) | |

warning (0, "output constraint %qc for operand %d " | |

"is not at the beginning", | |

*p, operand_num); | |

/* Make a copy of the constraint. */ | |

buf = XALLOCAVEC (char, c_len + 1); | |

strcpy (buf, constraint); | |

/* Swap the first character and the `=' or `+'. */ | |

buf[p - constraint] = buf[0]; | |

/* Make sure the first character is an `='. (Until we do this, | |

it might be a `+'.) */ | |

buf[0] = '='; | |

/* Replace the constraint with the canonicalized string. */ | |

*constraint_p = ggc_alloc_string (buf, c_len); | |

constraint = *constraint_p; | |

} | |

/* Loop through the constraint string. */ | |

for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p)) | |

switch (*p) | |

{ | |

case '+': | |

case '=': | |

error ("operand constraint contains incorrectly positioned " | |

"%<+%> or %<=%>"); | |

return false; | |

case '%': | |

if (operand_num + 1 == ninputs + noutputs) | |

{ | |

error ("%<%%%> constraint used with last operand"); | |

return false; | |

} | |

break; | |

case 'V': case TARGET_MEM_CONSTRAINT: case 'o': | |

*allows_mem = true; | |

break; | |

case '?': case '!': case '*': case '&': case '#': | |

case 'E': case 'F': case 'G': case 'H': | |

case 's': case 'i': case 'n': | |

case 'I': case 'J': case 'K': case 'L': case 'M': | |

case 'N': case 'O': case 'P': case ',': | |

break; | |

case '0': case '1': case '2': case '3': case '4': | |

case '5': case '6': case '7': case '8': case '9': | |

case '[': | |

error ("matching constraint not valid in output operand"); | |

return false; | |

case '<': case '>': | |

/* ??? Before flow, auto inc/dec insns are not supposed to exist, | |

excepting those that expand_call created. So match memory | |

and hope. */ | |

*allows_mem = true; | |

break; | |

case 'g': case 'X': | |

*allows_reg = true; | |

*allows_mem = true; | |

break; | |

case 'p': case 'r': | |

*allows_reg = true; | |

break; | |

default: | |

if (!ISALPHA (*p)) | |

break; | |

if (REG_CLASS_FROM_CONSTRAINT (*p, p) != NO_REGS) | |

*allows_reg = true; | |

#ifdef EXTRA_CONSTRAINT_STR | |

else if (EXTRA_ADDRESS_CONSTRAINT (*p, p)) | |

*allows_reg = true; | |

else if (EXTRA_MEMORY_CONSTRAINT (*p, p)) | |

*allows_mem = true; | |

else | |

{ | |

/* Otherwise we can't assume anything about the nature of | |

the constraint except that it isn't purely registers. | |

Treat it like "g" and hope for the best. */ | |

*allows_reg = true; | |

*allows_mem = true; | |

} | |

#endif | |

break; | |

} | |

return true; | |

} | |

/* Similar, but for input constraints. */ | |

bool | |

parse_input_constraint (const char **constraint_p, int input_num, | |

int ninputs, int noutputs, int ninout, | |

const char * const * constraints, | |

bool *allows_mem, bool *allows_reg) | |

{ | |

const char *constraint = *constraint_p; | |

const char *orig_constraint = constraint; | |

size_t c_len = strlen (constraint); | |

size_t j; | |

bool saw_match = false; | |

/* Assume the constraint doesn't allow the use of either | |

a register or memory. */ | |

*allows_mem = false; | |

*allows_reg = false; | |

/* Make sure constraint has neither `=', `+', nor '&'. */ | |

for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j)) | |

switch (constraint[j]) | |

{ | |

case '+': case '=': case '&': | |

if (constraint == orig_constraint) | |

{ | |

error ("input operand constraint contains %qc", constraint[j]); | |

return false; | |

} | |

break; | |

case '%': | |

if (constraint == orig_constraint | |

&& input_num + 1 == ninputs - ninout) | |

{ | |

error ("%<%%%> constraint used with last operand"); | |

return false; | |

} | |

break; | |

case 'V': case TARGET_MEM_CONSTRAINT: case 'o': | |

*allows_mem = true; | |

break; | |

case '<': case '>': | |

case '?': case '!': case '*': case '#': | |

case 'E': case 'F': case 'G': case 'H': | |

case 's': case 'i': case 'n': | |

case 'I': case 'J': case 'K': case 'L': case 'M': | |

case 'N': case 'O': case 'P': case ',': | |

break; | |

/* Whether or not a numeric constraint allows a register is | |

decided by the matching constraint, and so there is no need | |

to do anything special with them. We must handle them in | |

the default case, so that we don't unnecessarily force | |

operands to memory. */ | |

case '0': case '1': case '2': case '3': case '4': | |

case '5': case '6': case '7': case '8': case '9': | |

{ | |

char *end; | |

unsigned long match; | |

saw_match = true; | |

match = strtoul (constraint + j, &end, 10); | |

if (match >= (unsigned long) noutputs) | |

{ | |

error ("matching constraint references invalid operand number"); | |

return false; | |

} | |

/* Try and find the real constraint for this dup. Only do this | |

if the matching constraint is the only alternative. */ | |

if (*end == '\0' | |

&& (j == 0 || (j == 1 && constraint[0] == '%'))) | |

{ | |

constraint = constraints[match]; | |

*constraint_p = constraint; | |

c_len = strlen (constraint); | |

j = 0; | |

/* ??? At the end of the loop, we will skip the first part of | |

the matched constraint. This assumes not only that the | |

other constraint is an output constraint, but also that | |

the '=' or '+' come first. */ | |

break; | |

} | |

else | |

j = end - constraint; | |

/* Anticipate increment at end of loop. */ | |

j--; | |

} | |

/* Fall through. */ | |

case 'p': case 'r': | |

*allows_reg = true; | |

break; | |

case 'g': case 'X': | |

*allows_reg = true; | |

*allows_mem = true; | |

break; | |

default: | |

if (! ISALPHA (constraint[j])) | |

{ | |

error ("invalid punctuation %qc in constraint", constraint[j]); | |

return false; | |

} | |

if (REG_CLASS_FROM_CONSTRAINT (constraint[j], constraint + j) | |

!= NO_REGS) | |

*allows_reg = true; | |

#ifdef EXTRA_CONSTRAINT_STR | |

else if (EXTRA_ADDRESS_CONSTRAINT (constraint[j], constraint + j)) | |

*allows_reg = true; | |

else if (EXTRA_MEMORY_CONSTRAINT (constraint[j], constraint + j)) | |

*allows_mem = true; | |

else | |

{ | |

/* Otherwise we can't assume anything about the nature of | |

the constraint except that it isn't purely registers. | |

Treat it like "g" and hope for the best. */ | |

*allows_reg = true; | |

*allows_mem = true; | |

} | |

#endif | |

break; | |

} | |

if (saw_match && !*allows_reg) | |

warning (0, "matching constraint does not allow a register"); | |

return true; | |

} | |

/* Return DECL iff there's an overlap between *REGS and DECL, where DECL | |

can be an asm-declared register. Called via walk_tree. */ | |

static tree | |

decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED, | |

void *data) | |

{ | |

tree decl = *declp; | |

const HARD_REG_SET *const regs = (const HARD_REG_SET *) data; | |

if (TREE_CODE (decl) == VAR_DECL) | |

{ | |

if (DECL_HARD_REGISTER (decl) | |

&& REG_P (DECL_RTL (decl)) | |

&& REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER) | |

{ | |

rtx reg = DECL_RTL (decl); | |

if (overlaps_hard_reg_set_p (*regs, GET_MODE (reg), REGNO (reg))) | |

return decl; | |

} | |

walk_subtrees = 0; | |

} | |

else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL) | |

walk_subtrees = 0; | |

return NULL_TREE; | |

} | |

/* If there is an overlap between *REGS and DECL, return the first overlap | |

found. */ | |

tree | |

tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs) | |

{ | |

return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL); | |

} | |

/* Check for overlap between registers marked in CLOBBERED_REGS and | |

anything inappropriate in T. Emit error and return the register | |

variable definition for error, NULL_TREE for ok. */ | |

static bool | |

tree_conflicts_with_clobbers_p (tree t, HARD_REG_SET *clobbered_regs) | |

{ | |

/* Conflicts between asm-declared register variables and the clobber | |

list are not allowed. */ | |

tree overlap = tree_overlaps_hard_reg_set (t, clobbered_regs); | |

if (overlap) | |

{ | |

error ("asm-specifier for variable %qE conflicts with asm clobber list", | |

DECL_NAME (overlap)); | |

/* Reset registerness to stop multiple errors emitted for a single | |

variable. */ | |

DECL_REGISTER (overlap) = 0; | |

return true; | |

} | |

return false; | |

} | |

/* Generate RTL for an asm statement with arguments. | |

STRING is the instruction template. | |

OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs. | |

Each output or input has an expression in the TREE_VALUE and | |

a tree list in TREE_PURPOSE which in turn contains a constraint | |

name in TREE_VALUE (or NULL_TREE) and a constraint string | |

in TREE_PURPOSE. | |

CLOBBERS is a list of STRING_CST nodes each naming a hard register | |

that is clobbered by this insn. | |

LABELS is a list of labels, and if LABELS is non-NULL, FALLTHRU_BB | |

should be the fallthru basic block of the asm goto. | |

Not all kinds of lvalue that may appear in OUTPUTS can be stored directly. | |

Some elements of OUTPUTS may be replaced with trees representing temporary | |

values. The caller should copy those temporary values to the originally | |

specified lvalues. | |

VOL nonzero means the insn is volatile; don't optimize it. */ | |

static void | |

expand_asm_operands (tree string, tree outputs, tree inputs, | |

tree clobbers, tree labels, basic_block fallthru_bb, | |

int vol, location_t locus) | |

{ | |

rtvec argvec, constraintvec, labelvec; | |

rtx body; | |

int ninputs = list_length (inputs); | |

int noutputs = list_length (outputs); | |

int nlabels = list_length (labels); | |

int ninout; | |

int nclobbers; | |

HARD_REG_SET clobbered_regs; | |

int clobber_conflict_found = 0; | |

tree tail; | |

tree t; | |

int i; | |

/* Vector of RTX's of evaluated output operands. */ | |

rtx *output_rtx = XALLOCAVEC (rtx, noutputs); | |

int *inout_opnum = XALLOCAVEC (int, noutputs); | |

rtx *real_output_rtx = XALLOCAVEC (rtx, noutputs); | |

enum machine_mode *inout_mode = XALLOCAVEC (enum machine_mode, noutputs); | |

const char **constraints = XALLOCAVEC (const char *, noutputs + ninputs); | |

int old_generating_concat_p = generating_concat_p; | |

rtx fallthru_label = NULL_RTX; | |

/* An ASM with no outputs needs to be treated as volatile, for now. */ | |

if (noutputs == 0) | |

vol = 1; | |

if (! check_operand_nalternatives (outputs, inputs)) | |

return; | |

string = resolve_asm_operand_names (string, outputs, inputs, labels); | |

/* Collect constraints. */ | |

i = 0; | |

for (t = outputs; t ; t = TREE_CHAIN (t), i++) | |

constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t))); | |

for (t = inputs; t ; t = TREE_CHAIN (t), i++) | |

constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t))); | |

/* Sometimes we wish to automatically clobber registers across an asm. | |

Case in point is when the i386 backend moved from cc0 to a hard reg -- | |

maintaining source-level compatibility means automatically clobbering | |

the flags register. */ | |

clobbers = targetm.md_asm_clobbers (outputs, inputs, clobbers); | |

/* Count the number of meaningful clobbered registers, ignoring what | |

we would ignore later. */ | |

nclobbers = 0; | |

CLEAR_HARD_REG_SET (clobbered_regs); | |

for (tail = clobbers; tail; tail = TREE_CHAIN (tail)) | |

{ | |

const char *regname; | |

int nregs; | |

if (TREE_VALUE (tail) == error_mark_node) | |

return; | |

regname = TREE_STRING_POINTER (TREE_VALUE (tail)); | |

i = decode_reg_name_and_count (regname, &nregs); | |

if (i == -4) | |

++nclobbers; | |

else if (i == -2) | |

error ("unknown register name %qs in %<asm%>", regname); | |

/* Mark clobbered registers. */ | |

if (i >= 0) | |

{ | |

int reg; | |

for (reg = i; reg < i + nregs; reg++) | |

{ | |

++nclobbers; | |

/* Clobbering the PIC register is an error. */ | |

if (reg == (int) PIC_OFFSET_TABLE_REGNUM) | |

{ | |

error ("PIC register clobbered by %qs in %<asm%>", regname); | |

return; | |

} | |

SET_HARD_REG_BIT (clobbered_regs, reg); | |

} | |

} | |

} | |

/* First pass over inputs and outputs checks validity and sets | |

mark_addressable if needed. */ | |

ninout = 0; | |

for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) | |

{ | |

tree val = TREE_VALUE (tail); | |

tree type = TREE_TYPE (val); | |

const char *constraint; | |

bool is_inout; | |

bool allows_reg; | |

bool allows_mem; | |

/* If there's an erroneous arg, emit no insn. */ | |

if (type == error_mark_node) | |

return; | |

/* Try to parse the output constraint. If that fails, there's | |

no point in going further. */ | |

constraint = constraints[i]; | |

if (!parse_output_constraint (&constraint, i, ninputs, noutputs, | |

&allows_mem, &allows_reg, &is_inout)) | |

return; | |

if (! allows_reg | |

&& (allows_mem | |

|| is_inout | |

|| (DECL_P (val) | |

&& REG_P (DECL_RTL (val)) | |

&& GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))) | |

mark_addressable (val); | |

if (is_inout) | |

ninout++; | |

} | |

ninputs += ninout; | |

if (ninputs + noutputs > MAX_RECOG_OPERANDS) | |

{ | |

error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS); | |

return; | |

} | |

for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail)) | |

{ | |

bool allows_reg, allows_mem; | |

const char *constraint; | |

/* If there's an erroneous arg, emit no insn, because the ASM_INPUT | |

would get VOIDmode and that could cause a crash in reload. */ | |

if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node) | |

return; | |

constraint = constraints[i + noutputs]; | |

if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout, | |

constraints, &allows_mem, &allows_reg)) | |

return; | |

if (! allows_reg && allows_mem) | |

mark_addressable (TREE_VALUE (tail)); | |

} | |

/* Second pass evaluates arguments. */ | |

/* Make sure stack is consistent for asm goto. */ | |

if (nlabels > 0) | |

do_pending_stack_adjust (); | |

ninout = 0; | |

for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) | |

{ | |

tree val = TREE_VALUE (tail); | |

tree type = TREE_TYPE (val); | |

bool is_inout; | |

bool allows_reg; | |

bool allows_mem; | |

rtx op; | |

bool ok; | |

ok = parse_output_constraint (&constraints[i], i, ninputs, | |

noutputs, &allows_mem, &allows_reg, | |

&is_inout); | |

gcc_assert (ok); | |

/* If an output operand is not a decl or indirect ref and our constraint | |

allows a register, make a temporary to act as an intermediate. | |

Make the asm insn write into that, then our caller will copy it to | |

the real output operand. Likewise for promoted variables. */ | |

generating_concat_p = 0; | |

real_output_rtx[i] = NULL_RTX; | |

if ((TREE_CODE (val) == INDIRECT_REF | |

&& allows_mem) | |

|| (DECL_P (val) | |

&& (allows_mem || REG_P (DECL_RTL (val))) | |

&& ! (REG_P (DECL_RTL (val)) | |

&& GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))) | |

|| ! allows_reg | |

|| is_inout) | |

{ | |

op = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE); | |

if (MEM_P (op)) | |

op = validize_mem (op); | |

if (! allows_reg && !MEM_P (op)) | |

error ("output number %d not directly addressable", i); | |

if ((! allows_mem && MEM_P (op)) | |

|| GET_CODE (op) == CONCAT) | |

{ | |

real_output_rtx[i] = op; | |

op = gen_reg_rtx (GET_MODE (op)); | |

if (is_inout) | |

emit_move_insn (op, real_output_rtx[i]); | |

} | |

} | |

else | |

{ | |

op = assign_temp (type, 0, 1); | |

op = validize_mem (op); | |

if (!MEM_P (op) && TREE_CODE (TREE_VALUE (tail)) == SSA_NAME) | |

set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (TREE_VALUE (tail)), op); | |

TREE_VALUE (tail) = make_tree (type, op); | |

} | |

output_rtx[i] = op; | |

generating_concat_p = old_generating_concat_p; | |

if (is_inout) | |

{ | |

inout_mode[ninout] = TYPE_MODE (type); | |

inout_opnum[ninout++] = i; | |

} | |

if (tree_conflicts_with_clobbers_p (val, &clobbered_regs)) | |

clobber_conflict_found = 1; | |

} | |

/* Make vectors for the expression-rtx, constraint strings, | |

and named operands. */ | |

argvec = rtvec_alloc (ninputs); | |

constraintvec = rtvec_alloc (ninputs); | |

labelvec = rtvec_alloc (nlabels); | |

body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode | |

: GET_MODE (output_rtx[0])), | |

ggc_strdup (TREE_STRING_POINTER (string)), | |

empty_string, 0, argvec, constraintvec, | |

labelvec, locus); | |

MEM_VOLATILE_P (body) = vol; | |

/* Eval the inputs and put them into ARGVEC. | |

Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */ | |

for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i) | |

{ | |

bool allows_reg, allows_mem; | |

const char *constraint; | |

tree val, type; | |

rtx op; | |

bool ok; | |

constraint = constraints[i + noutputs]; | |

ok = parse_input_constraint (&constraint, i, ninputs, noutputs, ninout, | |

constraints, &allows_mem, &allows_reg); | |

gcc_assert (ok); | |

generating_concat_p = 0; | |

val = TREE_VALUE (tail); | |

type = TREE_TYPE (val); | |

/* EXPAND_INITIALIZER will not generate code for valid initializer | |

constants, but will still generate code for other types of operand. | |

This is the behavior we want for constant constraints. */ | |

op = expand_expr (val, NULL_RTX, VOIDmode, | |

allows_reg ? EXPAND_NORMAL | |

: allows_mem ? EXPAND_MEMORY | |

: EXPAND_INITIALIZER); | |

/* Never pass a CONCAT to an ASM. */ | |

if (GET_CODE (op) == CONCAT) | |

op = force_reg (GET_MODE (op), op); | |

else if (MEM_P (op)) | |

op = validize_mem (op); | |

if (asm_operand_ok (op, constraint, NULL) <= 0) | |

{ | |

if (allows_reg && TYPE_MODE (type) != BLKmode) | |

op = force_reg (TYPE_MODE (type), op); | |

else if (!allows_mem) | |

warning (0, "asm operand %d probably doesn%'t match constraints", | |

i + noutputs); | |

else if (MEM_P (op)) | |

{ | |

/* We won't recognize either volatile memory or memory | |

with a queued address as available a memory_operand | |

at this point. Ignore it: clearly this *is* a memory. */ | |

} | |

else | |

gcc_unreachable (); | |

} | |

generating_concat_p = old_generating_concat_p; | |

ASM_OPERANDS_INPUT (body, i) = op; | |

ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i) | |

= gen_rtx_ASM_INPUT (TYPE_MODE (type), | |

ggc_strdup (constraints[i + noutputs])); | |

if (tree_conflicts_with_clobbers_p (val, &clobbered_regs)) | |

clobber_conflict_found = 1; | |

} | |

/* Protect all the operands from the queue now that they have all been | |

evaluated. */ | |

generating_concat_p = 0; | |

/* For in-out operands, copy output rtx to input rtx. */ | |

for (i = 0; i < ninout; i++) | |

{ | |

int j = inout_opnum[i]; | |

char buffer[16]; | |

ASM_OPERANDS_INPUT (body, ninputs - ninout + i) | |

= output_rtx[j]; | |

sprintf (buffer, "%d", j); | |

ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i) | |

= gen_rtx_ASM_INPUT (inout_mode[i], ggc_strdup (buffer)); | |

} | |

/* Copy labels to the vector. */ | |

for (i = 0, tail = labels; i < nlabels; ++i, tail = TREE_CHAIN (tail)) | |

{ | |

rtx r; | |

/* If asm goto has any labels in the fallthru basic block, use | |

a label that we emit immediately after the asm goto. Expansion | |

may insert further instructions into the same basic block after | |

asm goto and if we don't do this, insertion of instructions on | |

the fallthru edge might misbehave. See PR58670. */ | |

if (fallthru_bb | |

&& label_to_block_fn (cfun, TREE_VALUE (tail)) == fallthru_bb) | |

{ | |

if (fallthru_label == NULL_RTX) | |

fallthru_label = gen_label_rtx (); | |

r = fallthru_label; | |

} | |

else | |

r = label_rtx (TREE_VALUE (tail)); | |

ASM_OPERANDS_LABEL (body, i) = gen_rtx_LABEL_REF (Pmode, r); | |

} | |

generating_concat_p = old_generating_concat_p; | |

/* Now, for each output, construct an rtx | |

(set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER | |

ARGVEC CONSTRAINTS OPNAMES)) | |

If there is more than one, put them inside a PARALLEL. */ | |

if (nlabels > 0 && nclobbers == 0) | |

{ | |

gcc_assert (noutputs == 0); | |

emit_jump_insn (body); | |

} | |

else if (noutputs == 0 && nclobbers == 0) | |

{ | |

/* No output operands: put in a raw ASM_OPERANDS rtx. */ | |

emit_insn (body); | |

} | |

else if (noutputs == 1 && nclobbers == 0) | |

{ | |

ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = ggc_strdup (constraints[0]); | |

emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body)); | |

} | |

else | |

{ | |

rtx obody = body; | |

int num = noutputs; | |

if (num == 0) | |

num = 1; | |

body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers)); | |

/* For each output operand, store a SET. */ | |

for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) | |

{ | |

XVECEXP (body, 0, i) | |

= gen_rtx_SET (VOIDmode, | |

output_rtx[i], | |

gen_rtx_ASM_OPERANDS | |

(GET_MODE (output_rtx[i]), | |

ggc_strdup (TREE_STRING_POINTER (string)), | |

ggc_strdup (constraints[i]), | |

i, argvec, constraintvec, labelvec, locus)); | |

MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol; | |

} | |

/* If there are no outputs (but there are some clobbers) | |

store the bare ASM_OPERANDS into the PARALLEL. */ | |

if (i == 0) | |

XVECEXP (body, 0, i++) = obody; | |

/* Store (clobber REG) for each clobbered register specified. */ | |

for (tail = clobbers; tail; tail = TREE_CHAIN (tail)) | |

{ | |

const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail)); | |

int reg, nregs; | |

int j = decode_reg_name_and_count (regname, &nregs); | |

rtx clobbered_reg; | |

if (j < 0) | |

{ | |

if (j == -3) /* `cc', which is not a register */ | |

continue; | |

if (j == -4) /* `memory', don't cache memory across asm */ | |

{ | |

XVECEXP (body, 0, i++) | |

= gen_rtx_CLOBBER (VOIDmode, | |

gen_rtx_MEM | |

(BLKmode, | |

gen_rtx_SCRATCH (VOIDmode))); | |

continue; | |

} | |

/* Ignore unknown register, error already signaled. */ | |

continue; | |

} | |

for (reg = j; reg < j + nregs; reg++) | |

{ | |

/* Use QImode since that's guaranteed to clobber just | |

* one reg. */ | |

clobbered_reg = gen_rtx_REG (QImode, reg); | |

/* Do sanity check for overlap between clobbers and | |

respectively input and outputs that hasn't been | |

handled. Such overlap should have been detected and | |

reported above. */ | |

if (!clobber_conflict_found) | |

{ | |

int opno; | |

/* We test the old body (obody) contents to avoid | |

tripping over the under-construction body. */ | |

for (opno = 0; opno < noutputs; opno++) | |

if (reg_overlap_mentioned_p (clobbered_reg, | |

output_rtx[opno])) | |

internal_error | |

("asm clobber conflict with output operand"); | |

for (opno = 0; opno < ninputs - ninout; opno++) | |

if (reg_overlap_mentioned_p (clobbered_reg, | |

ASM_OPERANDS_INPUT (obody, | |

opno))) | |

internal_error | |

("asm clobber conflict with input operand"); | |

} | |

XVECEXP (body, 0, i++) | |

= gen_rtx_CLOBBER (VOIDmode, clobbered_reg); | |

} | |

} | |

if (nlabels > 0) | |

emit_jump_insn (body); | |

else | |

emit_insn (body); | |

} | |

if (fallthru_label) | |

emit_label (fallthru_label); | |

/* For any outputs that needed reloading into registers, spill them | |

back to where they belong. */ | |

for (i = 0; i < noutputs; ++i) | |

if (real_output_rtx[i]) | |

emit_move_insn (real_output_rtx[i], output_rtx[i]); | |

crtl->has_asm_statement = 1; | |

free_temp_slots (); | |

} | |

void | |

expand_asm_stmt (gimple stmt) | |

{ | |

int noutputs; | |

tree outputs, tail, t; | |

tree *o; | |

size_t i, n; | |

const char *s; | |

tree str, out, in, cl, labels; | |

location_t locus = gimple_location (stmt); | |

basic_block fallthru_bb = NULL; | |

/* Meh... convert the gimple asm operands into real tree lists. | |

Eventually we should make all routines work on the vectors instead | |

of relying on TREE_CHAIN. */ | |

out = NULL_TREE; | |

n = gimple_asm_noutputs (stmt); | |

if (n > 0) | |

{ | |

t = out = gimple_asm_output_op (stmt, 0); | |

for (i = 1; i < n; i++) | |

t = TREE_CHAIN (t) = gimple_asm_output_op (stmt, i); | |

} | |

in = NULL_TREE; | |

n = gimple_asm_ninputs (stmt); | |

if (n > 0) | |

{ | |

t = in = gimple_asm_input_op (stmt, 0); | |

for (i = 1; i < n; i++) | |

t = TREE_CHAIN (t) = gimple_asm_input_op (stmt, i); | |

} | |

cl = NULL_TREE; | |

n = gimple_asm_nclobbers (stmt); | |

if (n > 0) | |

{ | |

t = cl = gimple_asm_clobber_op (stmt, 0); | |

for (i = 1; i < n; i++) | |

t = TREE_CHAIN (t) = gimple_asm_clobber_op (stmt, i); | |

} | |

labels = NULL_TREE; | |

n = gimple_asm_nlabels (stmt); | |

if (n > 0) | |

{ | |

edge fallthru = find_fallthru_edge (gimple_bb (stmt)->succs); | |

if (fallthru) | |

fallthru_bb = fallthru->dest; | |

t = labels = gimple_asm_label_op (stmt, 0); | |

for (i = 1; i < n; i++) | |

t = TREE_CHAIN (t) = gimple_asm_label_op (stmt, i); | |

} | |

s = gimple_asm_string (stmt); | |

str = build_string (strlen (s), s); | |

if (gimple_asm_input_p (stmt)) | |

{ | |

expand_asm_loc (str, gimple_asm_volatile_p (stmt), locus); | |

return; | |

} | |

outputs = out; | |

noutputs = gimple_asm_noutputs (stmt); | |

/* o[I] is the place that output number I should be written. */ | |

o = (tree *) alloca (noutputs * sizeof (tree)); | |

/* Record the contents of OUTPUTS before it is modified. */ | |

for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) | |

o[i] = TREE_VALUE (tail); | |

/* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of | |

OUTPUTS some trees for where the values were actually stored. */ | |

expand_asm_operands (str, outputs, in, cl, labels, fallthru_bb, | |

gimple_asm_volatile_p (stmt), locus); | |

/* Copy all the intermediate outputs into the specified outputs. */ | |

for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++) | |

{ | |

if (o[i] != TREE_VALUE (tail)) | |

{ | |

expand_assignment (o[i], TREE_VALUE (tail), false); | |

free_temp_slots (); | |

/* Restore the original value so that it's correct the next | |

time we expand this function. */ | |

TREE_VALUE (tail) = o[i]; | |

} | |

} | |

} | |

/* A subroutine of expand_asm_operands. Check that all operands have | |

the same number of alternatives. Return true if so. */ | |

static bool | |

check_operand_nalternatives (tree outputs, tree inputs) | |

{ | |

if (outputs || inputs) | |

{ | |

tree tmp = TREE_PURPOSE (outputs ? outputs : inputs); | |

int nalternatives | |

= n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp))); | |

tree next = inputs; | |

if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES) | |

{ | |

error ("too many alternatives in %<asm%>"); | |

return false; | |

} | |

tmp = outputs; | |

while (tmp) | |

{ | |

const char *constraint | |

= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp))); | |

if (n_occurrences (',', constraint) != nalternatives) | |

{ | |

error ("operand constraints for %<asm%> differ " | |

"in number of alternatives"); | |

return false; | |

} | |

if (TREE_CHAIN (tmp)) | |

tmp = TREE_CHAIN (tmp); | |

else | |

tmp = next, next = 0; | |

} | |

} | |

return true; | |

} | |

/* A subroutine of expand_asm_operands. Check that all operand names | |

are unique. Return true if so. We rely on the fact that these names | |

are identifiers, and so have been canonicalized by get_identifier, | |

so all we need are pointer comparisons. */ | |

static bool | |

check_unique_operand_names (tree outputs, tree inputs, tree labels) | |

{ | |

tree i, j, i_name = NULL_TREE; | |

for (i = outputs; i ; i = TREE_CHAIN (i)) | |

{ | |

i_name = TREE_PURPOSE (TREE_PURPOSE (i)); | |

if (! i_name) | |

continue; | |

for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j)) | |

if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) | |

goto failure; | |

} | |

for (i = inputs; i ; i = TREE_CHAIN (i)) | |

{ | |

i_name = TREE_PURPOSE (TREE_PURPOSE (i)); | |

if (! i_name) | |

continue; | |

for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j)) | |

if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) | |

goto failure; | |

for (j = outputs; j ; j = TREE_CHAIN (j)) | |

if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) | |

goto failure; | |

} | |

for (i = labels; i ; i = TREE_CHAIN (i)) | |

{ | |

i_name = TREE_PURPOSE (i); | |

if (! i_name) | |

continue; | |

for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j)) | |

if (simple_cst_equal (i_name, TREE_PURPOSE (j))) | |

goto failure; | |

for (j = inputs; j ; j = TREE_CHAIN (j)) | |

if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j)))) | |

goto failure; | |

} | |

return true; | |

failure: | |

error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name)); | |

return false; | |

} | |

/* A subroutine of expand_asm_operands. Resolve the names of the operands | |

in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in | |

STRING and in the constraints to those numbers. */ | |

tree | |

resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels) | |

{ | |

char *buffer; | |

char *p; | |

const char *c; | |

tree t; | |

check_unique_operand_names (outputs, inputs, labels); | |

/* Substitute [<name>] in input constraint strings. There should be no | |

named operands in output constraints. */ | |

for (t = inputs; t ; t = TREE_CHAIN (t)) | |

{ | |

c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t))); | |

if (strchr (c, '[') != NULL) | |

{ | |

p = buffer = xstrdup (c); | |

while ((p = strchr (p, '[')) != NULL) | |

p = resolve_operand_name_1 (p, outputs, inputs, NULL); | |

TREE_VALUE (TREE_PURPOSE (t)) | |

= build_string (strlen (buffer), buffer); | |

free (buffer); | |

} | |

} | |

/* Now check for any needed substitutions in the template. */ | |

c = TREE_STRING_POINTER (string); | |

while ((c = strchr (c, '%')) != NULL) | |

{ | |

if (c[1] == '[') | |

break; | |

else if (ISALPHA (c[1]) && c[2] == '[') | |

break; | |

else | |

{ | |

c += 1 + (c[1] == '%'); | |

continue; | |

} | |

} | |

if (c) | |

{ | |

/* OK, we need to make a copy so we can perform the substitutions. | |

Assume that we will not need extra space--we get to remove '[' | |

and ']', which means we cannot have a problem until we have more | |

than 999 operands. */ | |

buffer = xstrdup (TREE_STRING_POINTER (string)); | |

p = buffer + (c - TREE_STRING_POINTER (string)); | |

while ((p = strchr (p, '%')) != NULL) | |

{ | |

if (p[1] == '[') | |

p += 1; | |

else if (ISALPHA (p[1]) && p[2] == '[') | |

p += 2; | |

else | |

{ | |

p += 1 + (p[1] == '%'); | |

continue; | |

} | |

p = resolve_operand_name_1 (p, outputs, inputs, labels); | |

} | |

string = build_string (strlen (buffer), buffer); | |

free (buffer); | |

} | |

return string; | |

} | |

/* A subroutine of resolve_operand_names. P points to the '[' for a | |

potential named operand of the form [<name>]. In place, replace | |

the name and brackets with a number. Return a pointer to the | |

balance of the string after substitution. */ | |

static char * | |

resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels) | |

{ | |

char *q; | |

int op; | |

tree t; | |

/* Collect the operand name. */ | |

q = strchr (++p, ']'); | |

if (!q) | |

{ | |

error ("missing close brace for named operand"); | |

return strchr (p, '\0'); | |

} | |

*q = '\0'; | |

/* Resolve the name to a number. */ | |

for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++) | |

{ | |

tree name = TREE_PURPOSE (TREE_PURPOSE (t)); | |

if (name && strcmp (TREE_STRING_POINTER (name), p) == 0) | |

goto found; | |

} | |

for (t = inputs; t ; t = TREE_CHAIN (t), op++) | |

{ | |

tree name = TREE_PURPOSE (TREE_PURPOSE (t)); | |

if (name && strcmp (TREE_STRING_POINTER (name), p) == 0) | |

goto found; | |

} | |

for (t = labels; t ; t = TREE_CHAIN (t), op++) | |

{ | |

tree name = TREE_PURPOSE (t); | |

if (name && strcmp (TREE_STRING_POINTER (name), p) == 0) | |

goto found; | |

} | |

error ("undefined named operand %qs", identifier_to_locale (p)); | |

op = 0; | |

found: | |

/* Replace the name with the number. Unfortunately, not all libraries | |

get the return value of sprintf correct, so search for the end of the | |

generated string by hand. */ | |

sprintf (--p, "%d", op); | |

p = strchr (p, '\0'); | |

/* Verify the no extra buffer space assumption. */ | |

gcc_assert (p <= q); | |

/* Shift the rest of the buffer down to fill the gap. */ | |

memmove (p, q + 1, strlen (q + 1) + 1); | |

return p; | |

} | |

/* Generate RTL to return from the current function, with no value. | |

(That is, we do not do anything about returning any value.) */ | |

void | |

expand_null_return (void) | |

{ | |

/* If this function was declared to return a value, but we | |

didn't, clobber the return registers so that they are not | |

propagated live to the rest of the function. */ | |

clobber_return_register (); | |

expand_null_return_1 (); | |

} | |

/* Generate RTL to return directly from the current function. | |

(That is, we bypass any return value.) */ | |

void | |

expand_naked_return (void) | |

{ | |

rtx end_label; | |

clear_pending_stack_adjust (); | |

do_pending_stack_adjust (); | |

end_label = naked_return_label; | |

if (end_label == 0) | |

end_label = naked_return_label = gen_label_rtx (); | |

emit_jump (end_label); | |

} | |

/* Generate RTL to return from the current function, with value VAL. */ | |

static void | |

expand_value_return (rtx val) | |

{ | |

/* Copy the value to the return location unless it's already there. */ | |

tree decl = DECL_RESULT (current_function_decl); | |

rtx return_reg = DECL_RTL (decl); | |

if (return_reg != val) | |

{ | |

tree funtype = TREE_TYPE (current_function_decl); | |

tree type = TREE_TYPE (decl); | |

int unsignedp = TYPE_UNSIGNED (type); | |

enum machine_mode old_mode = DECL_MODE (decl); | |

enum machine_mode mode; | |

if (DECL_BY_REFERENCE (decl)) | |

mode = promote_function_mode (type, old_mode, &unsignedp, funtype, 2); | |

else | |

mode = promote_function_mode (type, old_mode, &unsignedp, funtype, 1); | |

if (mode != old_mode) | |

val = convert_modes (mode, old_mode, val, unsignedp); | |

if (GET_CODE (return_reg) == PARALLEL) | |

emit_group_load (return_reg, val, type, int_size_in_bytes (type)); | |

else | |

emit_move_insn (return_reg, val); | |

} | |

expand_null_return_1 (); | |

} | |

/* Output a return with no value. */ | |

static void | |

expand_null_return_1 (void) | |

{ | |

clear_pending_stack_adjust (); | |

do_pending_stack_adjust (); | |

emit_jump (return_label); | |

} | |

/* Generate RTL to evaluate the expression RETVAL and return it | |

from the current function. */ | |

void | |

expand_return (tree retval) | |

{ | |

rtx result_rtl; | |

rtx val = 0; | |

tree retval_rhs; | |

/* If function wants no value, give it none. */ | |

if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE) | |

{ | |

expand_normal (retval); | |

expand_null_return (); | |

return; | |

} | |

if (retval == error_mark_node) | |

{ | |

/* Treat this like a return of no value from a function that | |

returns a value. */ | |

expand_null_return (); | |

return; | |

} | |

else if ((TREE_CODE (retval) == MODIFY_EXPR | |

|| TREE_CODE (retval) == INIT_EXPR) | |

&& TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL) | |

retval_rhs = TREE_OPERAND (retval, 1); | |

else | |

retval_rhs = retval; | |

result_rtl = DECL_RTL (DECL_RESULT (current_function_decl)); | |

/* If we are returning the RESULT_DECL, then the value has already | |

been stored into it, so we don't have to do anything special. */ | |

if (TREE_CODE (retval_rhs) == RESULT_DECL) | |

expand_value_return (result_rtl); | |

/* If the result is an aggregate that is being returned in one (or more) | |

registers, load the registers here. */ | |

else if (retval_rhs != 0 | |

&& TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode | |

&& REG_P (result_rtl)) | |

{ | |

val = copy_blkmode_to_reg (GET_MODE (result_rtl), retval_rhs); | |

if (val) | |

{ | |

/* Use the mode of the result value on the return register. */ | |

PUT_MODE (result_rtl, GET_MODE (val)); | |

expand_value_return (val); | |

} | |

else | |

expand_null_return (); | |

} | |

else if (retval_rhs != 0 | |

&& !VOID_TYPE_P (TREE_TYPE (retval_rhs)) | |

&& (REG_P (result_rtl) | |

|| (GET_CODE (result_rtl) == PARALLEL))) | |

{ | |

/* Calculate the return value into a temporary (usually a pseudo | |

reg). */ | |

tree ot = TREE_TYPE (DECL_RESULT (current_function_decl)); | |

tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST); | |

val = assign_temp (nt, 0, 1); | |

val = expand_expr (retval_rhs, val, GET_MODE (val), EXPAND_NORMAL); | |

val = force_not_mem (val); | |

/* Return the calculated value. */ | |

expand_value_return (val); | |

} | |

else | |

{ | |

/* No hard reg used; calculate value into hard return reg. */ | |

expand_expr (retval, const0_rtx, VOIDmode, EXPAND_NORMAL); | |

expand_value_return (result_rtl); | |

} | |

} | |

/* Emit code to restore vital registers at the beginning of a nonlocal goto | |

handler. */ | |

static void | |

expand_nl_goto_receiver (void) | |

{ | |

rtx chain; | |

/* Clobber the FP when we get here, so we have to make sure it's | |

marked as used by this function. */ | |

emit_use (hard_frame_pointer_rtx); | |

/* Mark the static chain as clobbered here so life information | |

doesn't get messed up for it. */ | |

chain = targetm.calls.static_chain (current_function_decl, true); | |

if (chain && REG_P (chain)) | |

emit_clobber (chain); | |

#ifdef HAVE_nonlocal_goto | |

if (! HAVE_nonlocal_goto) | |

#endif | |

{ | |

/* First adjust our frame pointer to its actual value. It was | |

previously set to the start of the virtual area corresponding to | |

the stacked variables when we branched here and now needs to be | |

adjusted to the actual hardware fp value. | |

Assignments to virtual registers are converted by | |

instantiate_virtual_regs into the corresponding assignment | |

to the underlying register (fp in this case) that makes | |

the original assignment true. | |

So the following insn will actually be decrementing fp by | |

STARTING_FRAME_OFFSET. */ | |

emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx); | |

/* Restoring the frame pointer also modifies the hard frame pointer. | |

Mark it used (so that the previous assignment remains live once | |

the frame pointer is eliminated) and clobbered (to represent the | |

implicit update from the assignment). */ | |

emit_use (hard_frame_pointer_rtx); | |

emit_clobber (hard_frame_pointer_rtx); | |

} | |

#if !HARD_FRAME_POINTER_IS_ARG_POINTER | |

if (fixed_regs[ARG_POINTER_REGNUM]) | |

{ | |

#ifdef ELIMINABLE_REGS | |

/* If the argument pointer can be eliminated in favor of the | |

frame pointer, we don't need to restore it. We assume here | |

that if such an elimination is present, it can always be used. | |

This is the case on all known machines; if we don't make this | |

assumption, we do unnecessary saving on many machines. */ | |

static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS; | |

size_t i; | |

for (i = 0; i < ARRAY_SIZE (elim_regs); i++) | |

if (elim_regs[i].from == ARG_POINTER_REGNUM | |

&& elim_regs[i].to == HARD_FRAME_POINTER_REGNUM) | |

break; | |

if (i == ARRAY_SIZE (elim_regs)) | |

#endif | |

{ | |

/* Now restore our arg pointer from the address at which it | |

was saved in our stack frame. */ | |

emit_move_insn (crtl->args.internal_arg_pointer, | |

copy_to_reg (get_arg_pointer_save_area ())); | |

} | |

} | |

#endif | |

#ifdef HAVE_nonlocal_goto_receiver | |

if (HAVE_nonlocal_goto_receiver) | |

emit_insn (gen_nonlocal_goto_receiver ()); | |

#endif | |

/* We must not allow the code we just generated to be reordered by | |

scheduling. Specifically, the update of the frame pointer must | |

happen immediately, not later. */ | |

emit_insn (gen_blockage ()); | |

} | |

/* Emit code to save the current value of stack. */ | |

rtx | |

expand_stack_save (void) | |

{ | |

rtx ret = NULL_RTX; | |

do_pending_stack_adjust (); | |

emit_stack_save (SAVE_BLOCK, &ret); | |

return ret; | |

} | |

/* Emit code to restore the current value of stack. */ | |

void | |

expand_stack_restore (tree var) | |

{ | |

rtx prev, sa = expand_normal (var); | |

sa = convert_memory_address (Pmode, sa); | |

prev = get_last_insn (); | |

emit_stack_restore (SAVE_BLOCK, sa); | |

fixup_args_size_notes (prev, get_last_insn (), 0); | |

} | |

/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB | |

is the probability of jumping to LABEL. */ | |

static void | |

do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label, | |

int unsignedp, int prob) | |

{ | |

gcc_assert (prob <= REG_BR_PROB_BASE); | |

do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode, | |

NULL_RTX, NULL_RTX, label, prob); | |

} | |

/* Do the insertion of a case label into case_list. The labels are | |

fed to us in descending order from the sorted vector of case labels used | |

in the tree part of the middle end. So the list we construct is | |

sorted in ascending order. | |

LABEL is the case label to be inserted. LOW and HIGH are the bounds | |

against which the index is compared to jump to LABEL and PROB is the | |

estimated probability LABEL is reached from the switch statement. */ | |

static struct case_node * | |

add_case_node (struct case_node *head, tree low, tree high, | |

tree label, int prob, alloc_pool case_node_pool) | |

{ | |

struct case_node *r; | |

gcc_checking_assert (low); | |

gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high))); | |

/* Add this label to the chain. */ | |

r = (struct case_node *) pool_alloc (case_node_pool); | |

r->low = low; | |

r->high = high; | |

r->code_label = label; | |

r->parent = r->left = NULL; | |

r->prob = prob; | |

r->subtree_prob = prob; | |

r->right = head; | |

return r; | |

} | |

/* Dump ROOT, a list or tree of case nodes, to file. */ | |

static void | |

dump_case_nodes (FILE *f, struct case_node *root, | |

int indent_step, int indent_level) | |

{ | |

HOST_WIDE_INT low, high; | |

if (root == 0) | |

return; | |

indent_level++; | |

dump_case_nodes (f, root->left, indent_step, indent_level); | |

low = tree_low_cst (root->low, 0); | |

high = tree_low_cst (root->high, 0); | |

fputs (";; ", f); | |

if (high == low) | |

fprintf(f, "%*s" HOST_WIDE_INT_PRINT_DEC, | |

indent_step * indent_level, "", low); | |

else | |

fprintf(f, "%*s" HOST_WIDE_INT_PRINT_DEC " ... " HOST_WIDE_INT_PRINT_DEC, | |

indent_step * indent_level, "", low, high); | |

fputs ("\n", f); | |

dump_case_nodes (f, root->right, indent_step, indent_level); | |

} | |

#ifndef HAVE_casesi | |

#define HAVE_casesi 0 | |

#endif | |

#ifndef HAVE_tablejump | |

#define HAVE_tablejump 0 | |

#endif | |

/* Return the smallest number of different values for which it is best to use a | |

jump-table instead of a tree of conditional branches. */ | |

static unsigned int | |

case_values_threshold (void) | |

{ | |

unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD); | |

if (threshold == 0) | |

threshold = targetm.case_values_threshold (); | |

return threshold; | |

} | |

/* Return true if a switch should be expanded as a decision tree. | |

RANGE is the difference between highest and lowest case. | |

UNIQ is number of unique case node targets, not counting the default case. | |

COUNT is the number of comparisons needed, not counting the default case. */ | |

static bool | |

expand_switch_as_decision_tree_p (tree range, | |

unsigned int uniq ATTRIBUTE_UNUSED, | |

unsigned int count) | |

{ | |

int max_ratio; | |

/* If neither casesi or tablejump is available, or flag_jump_tables | |

over-ruled us, we really have no choice. */ | |

if (!HAVE_casesi && !HAVE_tablejump) | |

return true; | |

if (!flag_jump_tables) | |

return true; | |

#ifndef ASM_OUTPUT_ADDR_DIFF_ELT | |

if (flag_pic) | |

return true; | |

#endif | |

/* If the switch is relatively small such that the cost of one | |

indirect jump on the target are higher than the cost of a | |

decision tree, go with the decision tree. | |

If range of values is much bigger than number of values, | |

or if it is too large to represent in a HOST_WIDE_INT, | |

make a sequence of conditional branches instead of a dispatch. | |

The definition of "much bigger" depends on whether we are | |

optimizing for size or for speed. If the former, the maximum | |

ratio range/count = 3, because this was found to be the optimal | |

ratio for size on i686-pc-linux-gnu, see PR11823. The ratio | |

10 is much older, and was probably selected after an extensive | |

benchmarking investigation on numerous platforms. Or maybe it | |

just made sense to someone at some point in the history of GCC, | |

who knows... */ | |

max_ratio = optimize_insn_for_size_p () ? 3 : 10; | |

if (count < case_values_threshold () | |

|| ! host_integerp (range, /*pos=*/1) | |

|| compare_tree_int (range, max_ratio * count) > 0) | |

return true; | |

return false; | |

} | |

/* Generate a decision tree, switching on INDEX_EXPR and jumping to | |

one of the labels in CASE_LIST or to the DEFAULT_LABEL. | |

DEFAULT_PROB is the estimated probability that it jumps to | |

DEFAULT_LABEL. | |

We generate a binary decision tree to select the appropriate target | |

code. This is done as follows: | |

If the index is a short or char that we do not have | |

an insn to handle comparisons directly, convert it to | |

a full integer now, rather than letting each comparison | |

generate the conversion. | |

Load the index into a register. | |

The list of cases is rearranged into a binary tree, | |

nearly optimal assuming equal probability for each case. | |

The tree is transformed into RTL, eliminating redundant | |

test conditions at the same time. | |

If program flow could reach the end of the decision tree | |

an unconditional jump to the default code is emitted. | |

The above process is unaware of the CFG. The caller has to fix up | |

the CFG itself. This is done in cfgexpand.c. */ | |

static void | |

emit_case_decision_tree (tree index_expr, tree index_type, | |

struct case_node *case_list, rtx default_label, | |

int default_prob) | |

{ | |

rtx index = expand_normal (index_expr); | |

if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT | |

&& ! have_insn_for (COMPARE, GET_MODE (index))) | |

{ | |

int unsignedp = TYPE_UNSIGNED (index_type); | |

enum machine_mode wider_mode; | |

for (wider_mode = GET_MODE (index); wider_mode != VOIDmode; | |

wider_mode = GET_MODE_WIDER_MODE (wider_mode)) | |

if (have_insn_for (COMPARE, wider_mode)) | |

{ | |

index = convert_to_mode (wider_mode, index, unsignedp); | |

break; | |

} | |

} | |

do_pending_stack_adjust (); | |

if (MEM_P (index)) | |

{ | |

index = copy_to_reg (index); | |

if (TREE_CODE (index_expr) == SSA_NAME) | |

set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr), index); | |

} | |

balance_case_nodes (&case_list, NULL); | |

if (dump_file && (dump_flags & TDF_DETAILS)) | |

{ | |

int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2; | |

fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n"); | |

dump_case_nodes (dump_file, case_list, indent_step, 0); | |

} | |

emit_case_nodes (index, case_list, default_label, default_prob, index_type); | |

if (default_label) | |

emit_jump (default_label); | |

} | |

/* Return the sum of probabilities of outgoing edges of basic block BB. */ | |

static int | |

get_outgoing_edge_probs (basic_block bb) | |

{ | |

edge e; | |

edge_iterator ei; | |

int prob_sum = 0; | |

if (!bb) | |

return 0; | |

FOR_EACH_EDGE(e, ei, bb->succs) | |

prob_sum += e->probability; | |

return prob_sum; | |

} | |

/* Computes the conditional probability of jumping to a target if the branch | |

instruction is executed. | |

TARGET_PROB is the estimated probability of jumping to a target relative | |

to some basic block BB. | |

BASE_PROB is the probability of reaching the branch instruction relative | |

to the same basic block BB. */ | |

static inline int | |

conditional_probability (int target_prob, int base_prob) | |

{ | |

if (base_prob > 0) | |

{ | |

gcc_assert (target_prob >= 0); | |

gcc_assert (target_prob <= base_prob); | |

return RDIV (target_prob * REG_BR_PROB_BASE, base_prob); | |

} | |

return -1; | |

} | |

/* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to | |

one of the labels in CASE_LIST or to the DEFAULT_LABEL. | |

MINVAL, MAXVAL, and RANGE are the extrema and range of the case | |

labels in CASE_LIST. STMT_BB is the basic block containing the statement. | |

First, a jump insn is emitted. First we try "casesi". If that | |

fails, try "tablejump". A target *must* have one of them (or both). | |

Then, a table with the target labels is emitted. | |

The process is unaware of the CFG. The caller has to fix up | |

the CFG itself. This is done in cfgexpand.c. */ | |

static void | |

emit_case_dispatch_table (tree index_expr, tree index_type, | |

struct case_node *case_list, rtx default_label, | |

tree minval, tree maxval, tree range, | |

basic_block stmt_bb) | |

{ | |

int i, ncases; | |

struct case_node *n; | |

rtx *labelvec; | |

rtx fallback_label = label_rtx (case_list->code_label); | |

rtx table_label = gen_label_rtx (); | |

bool has_gaps = false; | |

edge default_edge = stmt_bb ? EDGE_SUCC(stmt_bb, 0) : NULL; | |

int default_prob = default_edge ? default_edge->probability : 0; | |

int base = get_outgoing_edge_probs (stmt_bb); | |

bool try_with_tablejump = false; | |

int new_default_prob = conditional_probability (default_prob, | |

base); | |

if (! try_casesi (index_type, index_expr, minval, range, | |

table_label, default_label, fallback_label, | |

new_default_prob)) | |

{ | |

/* Index jumptables from zero for suitable values of minval to avoid | |

a subtraction. For the rationale see: | |

"http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */ | |

if (optimize_insn_for_speed_p () | |

&& compare_tree_int (minval, 0) > 0 | |

&& compare_tree_int (minval, 3) < 0) | |

{ | |

minval = build_int_cst (index_type, 0); | |

range = maxval; | |

has_gaps = true; | |

} | |

try_with_tablejump = true; | |

} | |

/* Get table of labels to jump to, in order of case index. */ | |

ncases = tree_low_cst (range, 0) + 1; | |

labelvec = XALLOCAVEC (rtx, ncases); | |

memset (labelvec, 0, ncases * sizeof (rtx)); | |

for (n = case_list; n; n = n->right) | |

{ | |

/* Compute the low and high bounds relative to the minimum | |

value since that should fit in a HOST_WIDE_INT while the | |

actual values may not. */ | |

HOST_WIDE_INT i_low | |

= tree_low_cst (fold_build2 (MINUS_EXPR, index_type, | |

n->low, minval), 1); | |

HOST_WIDE_INT i_high | |

= tree_low_cst (fold_build2 (MINUS_EXPR, index_type, | |

n->high, minval), 1); | |

HOST_WIDE_INT i; | |

for (i = i_low; i <= i_high; i ++) | |

labelvec[i] | |

= gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label)); | |

} | |

/* Fill in the gaps with the default. We may have gaps at | |

the beginning if we tried to avoid the minval subtraction, | |

so substitute some label even if the default label was | |

deemed unreachable. */ | |

if (!default_label) | |

default_label = fallback_label; | |

for (i = 0; i < ncases; i++) | |

if (labelvec[i] == 0) | |

{ | |

has_gaps = true; | |

labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label); | |

} | |

if (has_gaps) | |

{ | |

/* There is at least one entry in the jump table that jumps | |

to default label. The default label can either be reached | |

through the indirect jump or the direct conditional jump | |

before that. Split the probability of reaching the | |

default label among these two jumps. */ | |

new_default_prob = conditional_probability (default_prob/2, | |

base); | |

default_prob /= 2; | |

base -= default_prob; | |

} | |

else | |

{ | |

base -= default_prob; | |

default_prob = 0; | |

} | |

if (default_edge) | |

default_edge->probability = default_prob; | |

/* We have altered the probability of the default edge. So the probabilities | |

of all other edges need to be adjusted so that it sums up to | |

REG_BR_PROB_BASE. */ | |

if (base) | |

{ | |

edge e; | |

edge_iterator ei; | |

FOR_EACH_EDGE (e, ei, stmt_bb->succs) | |

e->probability = RDIV (e->probability * REG_BR_PROB_BASE, base); | |

} | |

if (try_with_tablejump) | |

{ | |

bool ok = try_tablejump (index_type, index_expr, minval, range, | |

table_label, default_label, new_default_prob); | |

gcc_assert (ok); | |

} | |

/* Output the table. */ | |

emit_label (table_label); | |

if (CASE_VECTOR_PC_RELATIVE || flag_pic) | |

emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE, | |

gen_rtx_LABEL_REF (Pmode, table_label), | |

gen_rtvec_v (ncases, labelvec), | |

const0_rtx, const0_rtx)); | |

else | |

emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE, | |

gen_rtvec_v (ncases, labelvec))); | |

/* Record no drop-through after the table. */ | |

emit_barrier (); | |

} | |

/* Reset the aux field of all outgoing edges of basic block BB. */ | |

static inline void | |

reset_out_edges_aux (basic_block bb) | |

{ | |

edge e; | |

edge_iterator ei; | |

FOR_EACH_EDGE(e, ei, bb->succs) | |

e->aux = (void *)0; | |

} | |

/* Compute the number of case labels that correspond to each outgoing edge of | |

STMT. Record this information in the aux field of the edge. */ | |

static inline void | |

compute_cases_per_edge (gimple stmt) | |

{ | |

basic_block bb = gimple_bb (stmt); | |

reset_out_edges_aux (bb); | |

int ncases = gimple_switch_num_labels (stmt); | |

for (int i = ncases - 1; i >= 1; --i) | |

{ | |

tree elt = gimple_switch_label (stmt, i); | |

tree lab = CASE_LABEL (elt); | |

basic_block case_bb = label_to_block_fn (cfun, lab); | |

edge case_edge = find_edge (bb, case_bb); | |

case_edge->aux = (void *)((intptr_t)(case_edge->aux) + 1); | |

} | |

} | |

/* Terminate a case (Pascal/Ada) or switch (C) statement | |

in which ORIG_INDEX is the expression to be tested. | |

If ORIG_TYPE is not NULL, it is the original ORIG_INDEX | |

type as given in the source before any compiler conversions. | |

Generate the code to test it and jump to the right place. */ | |

void | |

expand_case (gimple stmt) | |

{ | |

tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE; | |

rtx default_label = NULL_RTX; | |

unsigned int count, uniq; | |

int i; | |

int ncases = gimple_switch_num_labels (stmt); | |

tree index_expr = gimple_switch_index (stmt); | |

tree index_type = TREE_TYPE (index_expr); | |

tree elt; | |

basic_block bb = gimple_bb (stmt); | |

/* A list of case labels; it is first built as a list and it may then | |

be rearranged into a nearly balanced binary tree. */ | |

struct case_node *case_list = 0; | |

/* A pool for case nodes. */ | |

alloc_pool case_node_pool; | |

/* An ERROR_MARK occurs for various reasons including invalid data type. | |

??? Can this still happen, with GIMPLE and all? */ | |

if (index_type == error_mark_node) | |

return; | |

/* cleanup_tree_cfg removes all SWITCH_EXPR with their index | |

expressions being INTEGER_CST. */ | |

gcc_assert (TREE_CODE (index_expr) != INTEGER_CST); | |

case_node_pool = create_alloc_pool ("struct case_node pool", | |

sizeof (struct case_node), | |

100); | |

do_pending_stack_adjust (); | |

/* Find the default case target label. */ | |

default_label = label_rtx (CASE_LABEL (gimple_switch_default_label (stmt))); | |

edge default_edge = EDGE_SUCC(bb, 0); | |

int default_prob = default_edge->probability; | |

/* Get upper and lower bounds of case values. */ | |

elt = gimple_switch_label (stmt, 1); | |

minval = fold_convert (index_type, CASE_LOW (elt)); | |

elt = gimple_switch_label (stmt, ncases - 1); | |

if (CASE_HIGH (elt)) | |

maxval = fold_convert (index_type, CASE_HIGH (elt)); | |

else | |

maxval = fold_convert (index_type, CASE_LOW (elt)); | |

/* Compute span of values. */ | |

range = fold_build2 (MINUS_EXPR, index_type, maxval, minval); | |

/* Listify the labels queue and gather some numbers to decide | |

how to expand this switch(). */ | |

uniq = 0; | |

count = 0; | |

struct pointer_set_t *seen_labels = pointer_set_create (); | |

compute_cases_per_edge (stmt); | |

for (i = ncases - 1; i >= 1; --i) | |

{ | |

elt = gimple_switch_label (stmt, i); | |

tree low = CASE_LOW (elt); | |

gcc_assert (low); | |

tree high = CASE_HIGH (elt); | |

gcc_assert (! high || tree_int_cst_lt (low, high)); | |

tree lab = CASE_LABEL (elt); | |

/* Count the elements. | |

A range counts double, since it requires two compares. */ | |

count++; | |

if (high) | |

count++; | |

/* If we have not seen this label yet, then increase the | |

number of unique case node targets seen. */ | |

if (!pointer_set_insert (seen_labels, lab)) | |

uniq++; | |

/* The bounds on the case range, LOW and HIGH, have to be converted | |

to case's index type TYPE. Note that the original type of the | |

case index in the source code is usually "lost" during | |

gimplification due to type promotion, but the case labels retain the | |

original type. Make sure to drop overflow flags. */ | |

low = fold_convert (index_type, low); | |

if (TREE_OVERFLOW (low)) | |

low = build_int_cst_wide (index_type, | |

TREE_INT_CST_LOW (low), | |

TREE_INT_CST_HIGH (low)); | |

/* The canonical from of a case label in GIMPLE is that a simple case | |

has an empty CASE_HIGH. For the casesi and tablejump expanders, | |

the back ends want simple cases to have high == low. */ | |

if (! high) | |

high = low; | |

high = fold_convert (index_type, high); | |

if (TREE_OVERFLOW (high)) | |

high = build_int_cst_wide (index_type, | |

TREE_INT_CST_LOW (high), | |

TREE_INT_CST_HIGH (high)); | |

basic_block case_bb = label_to_block_fn (cfun, lab); | |

edge case_edge = find_edge (bb, case_bb); | |

case_list = add_case_node ( | |

case_list, low, high, lab, | |

case_edge->probability / (intptr_t)(case_edge->aux), | |

case_node_pool); | |

} | |

pointer_set_destroy (seen_labels); | |

reset_out_edges_aux (bb); | |

/* cleanup_tree_cfg removes all SWITCH_EXPR with a single | |

destination, such as one with a default case only. | |

It also removes cases that are out of range for the switch | |

type, so we should never get a zero here. */ | |

gcc_assert (count > 0); | |

rtx before_case = get_last_insn (); | |

/* Decide how to expand this switch. | |

The two options at this point are a dispatch table (casesi or | |

tablejump) or a decision tree. */ | |

if (expand_switch_as_decision_tree_p (range, uniq, count)) | |

emit_case_decision_tree (index_expr, index_type, | |

case_list, default_label, | |

default_prob); | |

else | |

emit_case_dispatch_table (index_expr, index_type, | |

case_list, default_label, | |

minval, maxval, range, bb); | |

reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case); | |

free_temp_slots (); | |

free_alloc_pool (case_node_pool); | |

} | |

/* Expand the dispatch to a short decrement chain if there are few cases | |

to dispatch to. Likewise if neither casesi nor tablejump is available, | |

or if flag_jump_tables is set. Otherwise, expand as a casesi or a | |

tablejump. The index mode is always the mode of integer_type_node. | |

Trap if no case matches the index. | |

DISPATCH_INDEX is the index expression to switch on. It should be a | |

memory or register operand. | |

DISPATCH_TABLE is a set of case labels. The set should be sorted in | |

ascending order, be contiguous, starting with value 0, and contain only | |

single-valued case labels. */ | |

void | |

expand_sjlj_dispatch_table (rtx dispatch_index, | |

vec<tree> dispatch_table) | |

{ | |

tree index_type = integer_type_node; | |

enum machine_mode index_mode = TYPE_MODE (index_type); | |

int ncases = dispatch_table.length (); | |

do_pending_stack_adjust (); | |

rtx before_case = get_last_insn (); | |

/* Expand as a decrement-chain if there are 5 or fewer dispatch | |

labels. This covers more than 98% of the cases in libjava, | |

and seems to be a reasonable compromise between the "old way" | |

of expanding as a decision tree or dispatch table vs. the "new | |

way" with decrement chain or dispatch table. */ | |

if (dispatch_table.length () <= 5 | |

|| (!HAVE_casesi && !HAVE_tablejump) | |

|| !flag_jump_tables) | |

{ | |

/* Expand the dispatch as a decrement chain: | |

"switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}" | |

==> | |

if (index == 0) do_0; else index--; | |

if (index == 0) do_1; else index--; | |

... | |

if (index == 0) do_N; else index--; | |

This is more efficient than a dispatch table on most machines. | |

The last "index--" is redundant but the code is trivially dead | |

and will be cleaned up by later passes. */ | |

rtx index = copy_to_mode_reg (index_mode, dispatch_index); | |

rtx zero = CONST0_RTX (index_mode); | |

for (int i = 0; i < ncases; i++) | |

{ | |

tree elt = dispatch_table[i]; | |

rtx lab = label_rtx (CASE_LABEL (elt)); | |

do_jump_if_equal (index_mode, index, zero, lab, 0, -1); | |

force_expand_binop (index_mode, sub_optab, | |

index, CONST1_RTX (index_mode), | |

index, 0, OPTAB_DIRECT); | |

} | |

} | |

else | |

{ | |

/* Similar to expand_case, but much simpler. */ | |

struct case_node *case_list = 0; | |

alloc_pool case_node_pool = create_alloc_pool ("struct sjlj_case pool", | |

sizeof (struct case_node), | |

ncases); | |

tree index_expr = make_tree (index_type, dispatch_index); | |

tree minval = build_int_cst (index_type, 0); | |

tree maxval = CASE_LOW (dispatch_table.last ()); | |

tree range = maxval; | |

rtx default_label = gen_label_rtx (); | |

for (int i = ncases - 1; i >= 0; --i) | |

{ | |

tree elt = dispatch_table[i]; | |

tree low = CASE_LOW (elt); | |

tree lab = CASE_LABEL (elt); | |

case_list = add_case_node (case_list, low, low, lab, 0, case_node_pool); | |

} | |

emit_case_dispatch_table (index_expr, index_type, | |

case_list, default_label, | |

minval, maxval, range, | |

BLOCK_FOR_INSN (before_case)); | |

emit_label (default_label); | |

free_alloc_pool (case_node_pool); | |

} | |

/* Dispatching something not handled? Trap! */ | |

expand_builtin_trap (); | |

reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case); | |

free_temp_slots (); | |

} | |

/* Take an ordered list of case nodes | |

and transform them into a near optimal binary tree, | |

on the assumption that any target code selection value is as | |

likely as any other. | |

The transformation is performed by splitting the ordered | |

list into two equal sections plus a pivot. The parts are | |

then attached to the pivot as left and right branches. Each | |

branch is then transformed recursively. */ | |

static void | |

balance_case_nodes (case_node_ptr *head, case_node_ptr parent) | |

{ | |

case_node_ptr np; | |

np = *head; | |

if (np) | |

{ | |

int i = 0; | |

int ranges = 0; | |

case_node_ptr *npp; | |

case_node_ptr left; | |

/* Count the number of entries on branch. Also count the ranges. */ | |

while (np) | |

{ | |

if (!tree_int_cst_equal (np->low, np->high)) | |

ranges++; | |

i++; | |

np = np->right; | |

} | |

if (i > 2) | |

{ | |

/* Split this list if it is long enough for that to help. */ | |

npp = head; | |

left = *npp; | |

/* If there are just three nodes, split at the middle one. */ | |

if (i == 3) | |

npp = &(*npp)->right; | |

else | |

{ | |

/* Find the place in the list that bisects the list's total cost, | |

where ranges count as 2. | |

Here I gets half the total cost. */ | |

i = (i + ranges + 1) / 2; | |

while (1) | |

{ | |

/* Skip nodes while their cost does not reach that amount. */ | |

if (!tree_int_cst_equal ((*npp)->low, (*npp)->high)) | |

i--; | |

i--; | |

if (i <= 0) | |

break; | |

npp = &(*npp)->right; | |

} | |

} | |

*head = np = *npp; | |

*npp = 0; | |

np->parent = parent; | |

np->left = left; | |

/* Optimize each of the two split parts. */ | |

balance_case_nodes (&np->left, np); | |

balance_case_nodes (&np->right, np); | |

np->subtree_prob = np->prob; | |

np->subtree_prob += np->left->subtree_prob; | |

np->subtree_prob += np->right->subtree_prob; | |

} | |

else | |

{ | |

/* Else leave this branch as one level, | |

but fill in `parent' fields. */ | |

np = *head; | |

np->parent = parent; | |

np->subtree_prob = np->prob; | |

for (; np->right; np = np->right) | |

{ | |

np->right->parent = np; | |

(*head)->subtree_prob += np->right->subtree_prob; | |

} | |

} | |

} | |

} | |

/* Search the parent sections of the case node tree | |

to see if a test for the lower bound of NODE would be redundant. | |

INDEX_TYPE is the type of the index expression. | |

The instructions to generate the case decision tree are | |

output in the same order as nodes are processed so it is | |

known that if a parent node checks the range of the current | |

node minus one that the current node is bounded at its lower | |

span. Thus the test would be redundant. */ | |

static int | |

node_has_low_bound (case_node_ptr node, tree index_type) | |

{ | |

tree low_minus_one; | |

case_node_ptr pnode; | |

/* If the lower bound of this node is the lowest value in the index type, | |

we need not test it. */ | |

if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type))) | |

return 1; | |

/* If this node has a left branch, the value at the left must be less | |

than that at this node, so it cannot be bounded at the bottom and | |

we need not bother testing any further. */ | |

if (node->left) | |

return 0; | |

low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), | |

node->low, | |

build_int_cst (TREE_TYPE (node->low), 1)); | |

/* If the subtraction above overflowed, we can't verify anything. | |

Otherwise, look for a parent that tests our value - 1. */ | |

if (! tree_int_cst_lt (low_minus_one, node->low)) | |

return 0; | |

for (pnode = node->parent; pnode; pnode = pnode->parent) | |

if (tree_int_cst_equal (low_minus_one, pnode->high)) | |

return 1; | |

return 0; | |

} | |

/* Search the parent sections of the case node tree | |

to see if a test for the upper bound of NODE would be redundant. | |

INDEX_TYPE is the type of the index expression. | |

The instructions to generate the case decision tree are | |

output in the same order as nodes are processed so it is | |

known that if a parent node checks the range of the current | |

node plus one that the current node is bounded at its upper | |

span. Thus the test would be redundant. */ | |

static int | |

node_has_high_bound (case_node_ptr node, tree index_type) | |

{ | |

tree high_plus_one; | |

case_node_ptr pnode; | |

/* If there is no upper bound, obviously no test is needed. */ | |

if (TYPE_MAX_VALUE (index_type) == NULL) | |

return 1; | |

/* If the upper bound of this node is the highest value in the type | |

of the index expression, we need not test against it. */ | |

if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type))) | |

return 1; | |

/* If this node has a right branch, the value at the right must be greater | |

than that at this node, so it cannot be bounded at the top and | |

we need not bother testing any further. */ | |

if (node->right) | |

return 0; | |

high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), | |

node->high, | |

build_int_cst (TREE_TYPE (node->high), 1)); | |

/* If the addition above overflowed, we can't verify anything. | |

Otherwise, look for a parent that tests our value + 1. */ | |

if (! tree_int_cst_lt (node->high, high_plus_one)) | |

return 0; | |

for (pnode = node->parent; pnode; pnode = pnode->parent) | |

if (tree_int_cst_equal (high_plus_one, pnode->low)) | |

return 1; | |

return 0; | |

} | |

/* Search the parent sections of the | |

case node tree to see if both tests for the upper and lower | |

bounds of NODE would be redundant. */ | |

static int | |

node_is_bounded (case_node_ptr node, tree index_type) | |

{ | |

return (node_has_low_bound (node, index_type) | |

&& node_has_high_bound (node, index_type)); | |

} | |

/* Emit step-by-step code to select a case for the value of INDEX. | |

The thus generated decision tree follows the form of the | |

case-node binary tree NODE, whose nodes represent test conditions. | |

INDEX_TYPE is the type of the index of the switch. | |

Care is taken to prune redundant tests from the decision tree | |

by detecting any boundary conditions already checked by | |

emitted rtx. (See node_has_high_bound, node_has_low_bound | |

and node_is_bounded, above.) | |

Where the test conditions can be shown to be redundant we emit | |

an unconditional jump to the target code. As a further | |

optimization, the subordinates of a tree node are examined to | |

check for bounded nodes. In this case conditional and/or | |

unconditional jumps as a result of the boundary check for the | |

current node are arranged to target the subordinates associated | |

code for out of bound conditions on the current node. | |

We can assume that when control reaches the code generated here, | |

the index value has already been compared with the parents | |

of this node, and determined to be on the same side of each parent | |

as this node is. Thus, if this node tests for the value 51, | |

and a parent tested for 52, we don't need to consider | |

the possibility of a value greater than 51. If another parent | |

tests for the value 50, then this node need not test anything. */ | |

static void | |

emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, | |

int default_prob, tree index_type) | |

{ | |

/* If INDEX has an unsigned type, we must make unsigned branches. */ | |

int unsignedp = TYPE_UNSIGNED (index_type); | |

int probability; | |

int prob = node->prob, subtree_prob = node->subtree_prob; | |

enum machine_mode mode = GET_MODE (index); | |

enum machine_mode imode = TYPE_MODE (index_type); | |

/* Handle indices detected as constant during RTL expansion. */ | |

if (mode == VOIDmode) | |

mode = imode; | |

/* See if our parents have already tested everything for us. | |

If they have, emit an unconditional jump for this node. */ | |

if (node_is_bounded (node, index_type)) | |

emit_jump (label_rtx (node->code_label)); | |

else if (tree_int_cst_equal (node->low, node->high)) | |

{ | |

probability = conditional_probability (prob, subtree_prob + default_prob); | |

/* Node is single valued. First see if the index expression matches | |

this node and then check our children, if any. */ | |

do_jump_if_equal (mode, index, | |

convert_modes (mode, imode, | |

expand_normal (node->low), | |

unsignedp), | |

label_rtx (node->code_label), unsignedp, probability); | |

/* Since this case is taken at this point, reduce its weight from | |

subtree_weight. */ | |

subtree_prob -= prob; | |

if (node->right != 0 && node->left != 0) | |

{ | |

/* This node has children on both sides. | |

Dispatch to one side or the other | |

by comparing the index value with this node's value. | |

If one subtree is bounded, check that one first, | |

so we can avoid real branches in the tree. */ | |

if (node_is_bounded (node->right, index_type)) | |

{ | |

probability = conditional_probability ( | |

node->right->prob, | |

subtree_prob + default_prob); | |

emit_cmp_and_jump_insns (index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->high), | |

unsignedp), | |

GT, NULL_RTX, mode, unsignedp, | |

label_rtx (node->right->code_label), | |

probability); | |

emit_case_nodes (index, node->left, default_label, default_prob, | |

index_type); | |

} | |

else if (node_is_bounded (node->left, index_type)) | |

{ | |

probability = conditional_probability ( | |

node->left->prob, | |

subtree_prob + default_prob); | |

emit_cmp_and_jump_insns (index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->high), | |

unsignedp), | |

LT, NULL_RTX, mode, unsignedp, | |

label_rtx (node->left->code_label), | |

probability); | |

emit_case_nodes (index, node->right, default_label, default_prob, index_type); | |

} | |

/* If both children are single-valued cases with no | |

children, finish up all the work. This way, we can save | |

one ordered comparison. */ | |

else if (tree_int_cst_equal (node->right->low, node->right->high) | |

&& node->right->left == 0 | |

&& node->right->right == 0 | |

&& tree_int_cst_equal (node->left->low, node->left->high) | |

&& node->left->left == 0 | |

&& node->left->right == 0) | |

{ | |

/* Neither node is bounded. First distinguish the two sides; | |

then emit the code for one side at a time. */ | |

/* See if the value matches what the right hand side | |

wants. */ | |

probability = conditional_probability ( | |

node->right->prob, | |

subtree_prob + default_prob); | |

do_jump_if_equal (mode, index, | |

convert_modes (mode, imode, | |

expand_normal (node->right->low), | |

unsignedp), | |

label_rtx (node->right->code_label), | |

unsignedp, probability); | |

/* See if the value matches what the left hand side | |

wants. */ | |

probability = conditional_probability ( | |

node->left->prob, | |

subtree_prob + default_prob); | |

do_jump_if_equal (mode, index, | |

convert_modes (mode, imode, | |

expand_normal (node->left->low), | |

unsignedp), | |

label_rtx (node->left->code_label), | |

unsignedp, probability); | |

} | |

else | |

{ | |

/* Neither node is bounded. First distinguish the two sides; | |

then emit the code for one side at a time. */ | |

tree test_label | |

= build_decl (curr_insn_location (), | |

LABEL_DECL, NULL_TREE, NULL_TREE); | |

/* The default label could be reached either through the right | |

subtree or the left subtree. Divide the probability | |

equally. */ | |

probability = conditional_probability ( | |

node->right->subtree_prob + default_prob/2, | |

subtree_prob + default_prob); | |

/* See if the value is on the right. */ | |

emit_cmp_and_jump_insns (index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->high), | |

unsignedp), | |

GT, NULL_RTX, mode, unsignedp, | |

label_rtx (test_label), | |

probability); | |

default_prob /= 2; | |

/* Value must be on the left. | |

Handle the left-hand subtree. */ | |

emit_case_nodes (index, node->left, default_label, default_prob, index_type); | |

/* If left-hand subtree does nothing, | |

go to default. */ | |

if (default_label) | |

emit_jump (default_label); | |

/* Code branches here for the right-hand subtree. */ | |

expand_label (test_label); | |

emit_case_nodes (index, node->right, default_label, default_prob, index_type); | |

} | |

} | |

else if (node->right != 0 && node->left == 0) | |

{ | |

/* Here we have a right child but no left so we issue a conditional | |

branch to default and process the right child. | |

Omit the conditional branch to default if the right child | |

does not have any children and is single valued; it would | |

cost too much space to save so little time. */ | |

if (node->right->right || node->right->left | |

|| !tree_int_cst_equal (node->right->low, node->right->high)) | |

{ | |

if (!node_has_low_bound (node, index_type)) | |

{ | |

probability = conditional_probability ( | |

default_prob/2, | |

subtree_prob + default_prob); | |

emit_cmp_and_jump_insns (index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->high), | |

unsignedp), | |

LT, NULL_RTX, mode, unsignedp, | |

default_label, | |

probability); | |

default_prob /= 2; | |

} | |

emit_case_nodes (index, node->right, default_label, default_prob, index_type); | |

} | |

else | |

{ | |

probability = conditional_probability ( | |

node->right->subtree_prob, | |

subtree_prob + default_prob); | |

/* We cannot process node->right normally | |

since we haven't ruled out the numbers less than | |

this node's value. So handle node->right explicitly. */ | |

do_jump_if_equal (mode, index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->right->low), | |

unsignedp), | |

label_rtx (node->right->code_label), unsignedp, probability); | |

} | |

} | |

else if (node->right == 0 && node->left != 0) | |

{ | |

/* Just one subtree, on the left. */ | |

if (node->left->left || node->left->right | |

|| !tree_int_cst_equal (node->left->low, node->left->high)) | |

{ | |

if (!node_has_high_bound (node, index_type)) | |

{ | |

probability = conditional_probability ( | |

default_prob/2, | |

subtree_prob + default_prob); | |

emit_cmp_and_jump_insns (index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->high), | |

unsignedp), | |

GT, NULL_RTX, mode, unsignedp, | |

default_label, | |

probability); | |

default_prob /= 2; | |

} | |

emit_case_nodes (index, node->left, default_label, | |

default_prob, index_type); | |

} | |

else | |

{ | |

probability = conditional_probability ( | |

node->left->subtree_prob, | |

subtree_prob + default_prob); | |

/* We cannot process node->left normally | |

since we haven't ruled out the numbers less than | |

this node's value. So handle node->left explicitly. */ | |

do_jump_if_equal (mode, index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->left->low), | |

unsignedp), | |

label_rtx (node->left->code_label), unsignedp, probability); | |

} | |

} | |

} | |

else | |

{ | |

/* Node is a range. These cases are very similar to those for a single | |

value, except that we do not start by testing whether this node | |

is the one to branch to. */ | |

if (node->right != 0 && node->left != 0) | |

{ | |

/* Node has subtrees on both sides. | |

If the right-hand subtree is bounded, | |

test for it first, since we can go straight there. | |

Otherwise, we need to make a branch in the control structure, | |

then handle the two subtrees. */ | |

tree test_label = 0; | |

if (node_is_bounded (node->right, index_type)) | |

{ | |

/* Right hand node is fully bounded so we can eliminate any | |

testing and branch directly to the target code. */ | |

probability = conditional_probability ( | |

node->right->subtree_prob, | |

subtree_prob + default_prob); | |

emit_cmp_and_jump_insns (index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->high), | |

unsignedp), | |

GT, NULL_RTX, mode, unsignedp, | |

label_rtx (node->right->code_label), | |

probability); | |

} | |

else | |

{ | |

/* Right hand node requires testing. | |

Branch to a label where we will handle it later. */ | |

test_label = build_decl (curr_insn_location (), | |

LABEL_DECL, NULL_TREE, NULL_TREE); | |

probability = conditional_probability ( | |

node->right->subtree_prob + default_prob/2, | |

subtree_prob + default_prob); | |

emit_cmp_and_jump_insns (index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->high), | |

unsignedp), | |

GT, NULL_RTX, mode, unsignedp, | |

label_rtx (test_label), | |

probability); | |

default_prob /= 2; | |

} | |

/* Value belongs to this node or to the left-hand subtree. */ | |

probability = conditional_probability ( | |

prob, | |

subtree_prob + default_prob); | |

emit_cmp_and_jump_insns (index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->low), | |

unsignedp), | |

GE, NULL_RTX, mode, unsignedp, | |

label_rtx (node->code_label), | |

probability); | |

/* Handle the left-hand subtree. */ | |

emit_case_nodes (index, node->left, default_label, default_prob, index_type); | |

/* If right node had to be handled later, do that now. */ | |

if (test_label) | |

{ | |

/* If the left-hand subtree fell through, | |

don't let it fall into the right-hand subtree. */ | |

if (default_label) | |

emit_jump (default_label); | |

expand_label (test_label); | |

emit_case_nodes (index, node->right, default_label, default_prob, index_type); | |

} | |

} | |

else if (node->right != 0 && node->left == 0) | |

{ | |

/* Deal with values to the left of this node, | |

if they are possible. */ | |

if (!node_has_low_bound (node, index_type)) | |

{ | |

probability = conditional_probability ( | |

default_prob/2, | |

subtree_prob + default_prob); | |

emit_cmp_and_jump_insns (index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->low), | |

unsignedp), | |

LT, NULL_RTX, mode, unsignedp, | |

default_label, | |

probability); | |

default_prob /= 2; | |

} | |

/* Value belongs to this node or to the right-hand subtree. */ | |

probability = conditional_probability ( | |

prob, | |

subtree_prob + default_prob); | |

emit_cmp_and_jump_insns (index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->high), | |

unsignedp), | |

LE, NULL_RTX, mode, unsignedp, | |

label_rtx (node->code_label), | |

probability); | |

emit_case_nodes (index, node->right, default_label, default_prob, index_type); | |

} | |

else if (node->right == 0 && node->left != 0) | |

{ | |

/* Deal with values to the right of this node, | |

if they are possible. */ | |

if (!node_has_high_bound (node, index_type)) | |

{ | |

probability = conditional_probability ( | |

default_prob/2, | |

subtree_prob + default_prob); | |

emit_cmp_and_jump_insns (index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->high), | |

unsignedp), | |

GT, NULL_RTX, mode, unsignedp, | |

default_label, | |

probability); | |

default_prob /= 2; | |

} | |

/* Value belongs to this node or to the left-hand subtree. */ | |

probability = conditional_probability ( | |

prob, | |

subtree_prob + default_prob); | |

emit_cmp_and_jump_insns (index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->low), | |

unsignedp), | |

GE, NULL_RTX, mode, unsignedp, | |

label_rtx (node->code_label), | |

probability); | |

emit_case_nodes (index, node->left, default_label, default_prob, index_type); | |

} | |

else | |

{ | |

/* Node has no children so we check low and high bounds to remove | |

redundant tests. Only one of the bounds can exist, | |

since otherwise this node is bounded--a case tested already. */ | |

int high_bound = node_has_high_bound (node, index_type); | |

int low_bound = node_has_low_bound (node, index_type); | |

if (!high_bound && low_bound) | |

{ | |

probability = conditional_probability ( | |

default_prob, | |

subtree_prob + default_prob); | |

emit_cmp_and_jump_insns (index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->high), | |

unsignedp), | |

GT, NULL_RTX, mode, unsignedp, | |

default_label, | |

probability); | |

} | |

else if (!low_bound && high_bound) | |

{ | |

probability = conditional_probability ( | |

default_prob, | |

subtree_prob + default_prob); | |

emit_cmp_and_jump_insns (index, | |

convert_modes | |

(mode, imode, | |

expand_normal (node->low), | |

unsignedp), | |

LT, NULL_RTX, mode, unsignedp, | |

default_label, | |

probability); | |

} | |

else if (!low_bound && !high_bound) | |

{ | |

/* Widen LOW and HIGH to the same width as INDEX. */ | |

tree type = lang_hooks.types.type_for_mode (mode, unsignedp); | |

tree low = build1 (CONVERT_EXPR, type, node->low); | |

tree high = build1 (CONVERT_EXPR, type, node->high); | |

rtx low_rtx, new_index, new_bound; | |

/* Instead of doing two branches, emit one unsigned branch for | |

(index-low) > (high-low). */ | |

low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL); | |

new_index = expand_simple_binop (mode, MINUS, index, low_rtx, | |

NULL_RTX, unsignedp, | |

OPTAB_WIDEN); | |

new_bound = expand_expr (fold_build2 (MINUS_EXPR, type, | |

high, low), | |

NULL_RTX, mode, EXPAND_NORMAL); | |

probability = conditional_probability ( | |

default_prob, | |

subtree_prob + default_prob); | |

emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX, | |

mode, 1, default_label, probability); | |

} | |

emit_jump (label_rtx (node->code_label)); | |

} | |

} | |

} |