X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=gcc%2Fstmt.c;h=16a080a623aa8eba891689f779dd69fc1133a860;hb=14e40d7efcebb33770d6f51d51f5df6eb1ac69cc;hp=952388aff91c55279380068d12958bbec70f0d9f;hpb=d34b4f64c879442fb29b59301425fc0087fea5dd;p=gcc.git diff --git a/gcc/stmt.c b/gcc/stmt.c index 952388aff91..16a080a623a 100644 --- a/gcc/stmt.c +++ b/gcc/stmt.c @@ -1,7 +1,5 @@ /* Expands front end tree to back end RTL for GCC - Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, - 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, - 2010 Free Software Foundation, Inc. + Copyright (C) 1987-2015 Free Software Foundation, Inc. This file is part of GCC. @@ -31,28 +29,57 @@ along with GCC; see the file COPYING3. If not see #include "rtl.h" #include "hard-reg-set.h" +#include "hash-set.h" +#include "machmode.h" +#include "vec.h" +#include "double-int.h" +#include "input.h" +#include "alias.h" +#include "symtab.h" +#include "wide-int.h" +#include "inchash.h" #include "tree.h" +#include "fold-const.h" +#include "varasm.h" +#include "stor-layout.h" #include "tm_p.h" #include "flags.h" #include "except.h" #include "function.h" #include "insn-config.h" +#include "hashtab.h" +#include "statistics.h" +#include "real.h" +#include "fixed-value.h" +#include "expmed.h" +#include "dojump.h" +#include "explow.h" +#include "calls.h" +#include "emit-rtl.h" +#include "stmt.h" #include "expr.h" #include "libfuncs.h" #include "recog.h" -#include "machmode.h" -#include "toplev.h" +#include "diagnostic-core.h" #include "output.h" -#include "ggc.h" #include "langhooks.h" #include "predict.h" +#include "insn-codes.h" #include "optabs.h" #include "target.h" +#include "cfganal.h" +#include "basic-block.h" +#include "tree-ssa-alias.h" +#include "internal-fn.h" +#include "gimple-expr.h" +#include "is-a.h" #include "gimple.h" #include "regs.h" #include "alloc-pool.h" #include "pretty-print.h" -#include "bitmap.h" +#include "params.h" +#include "dumpfile.h" +#include "builtins.h" /* Functions and data structures for expanding case statements. */ @@ -92,76 +119,65 @@ struct case_node 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; -/* These are used by estimate_case_costs and balance_case_nodes. */ - -/* This must be a signed type, and non-ANSI compilers lack signed char. */ -static short cost_table_[129]; -static int use_cost_table; -static int cost_table_initialized; - -/* Special care is needed because we allow -1, but TREE_INT_CST_LOW - is unsigned. */ -#define COST_TABLE(I) cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)] +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 int estimate_case_costs (case_node_ptr); -static bool lshift_cheap_p (void); -static int case_bit_test_cmp (const void *, const void *); -static void emit_case_bit_tests (tree, tree, tree, tree, case_node_ptr, 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, tree); -static struct case_node *add_case_node (struct case_node *, tree, - tree, tree, tree, alloc_pool); - +static void emit_case_nodes (rtx, case_node_ptr, rtx_code_label *, int, tree); /* Return the rtx-label that corresponds to a LABEL_DECL, creating it if necessary. */ -rtx +rtx_insn * label_rtx (tree label) { gcc_assert (TREE_CODE (label) == LABEL_DECL); if (!DECL_RTL_SET_P (label)) { - rtx r = gen_label_rtx (); + rtx_code_label *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); + return as_a (DECL_RTL (label)); } /* As above, but also put it on the forced-reference list of the function that contains it. */ -rtx +rtx_insn * force_label_rtx (tree label) { - rtx ref = label_rtx (label); + rtx_insn *ref = label_rtx (label); tree function = decl_function_context (label); gcc_assert (function); - forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref, forced_labels); + forced_labels = gen_rtx_INSN_LIST (VOIDmode, ref, forced_labels); return ref; } +/* As label_rtx, but ensures (in check build), that returned value is + an existing label (i.e. rtx with code CODE_LABEL). */ +rtx_code_label * +jump_target_rtx (tree label) +{ + return as_a (label_rtx (label)); +} + /* Add an unconditional jump to LABEL as the next sequential instruction. */ void @@ -171,20 +187,6 @@ emit_jump (rtx label) 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. */ @@ -202,7 +204,7 @@ expand_computed_goto (tree exp) void expand_label (tree label) { - rtx label_r = label_rtx (label); + rtx_code_label *label_r = jump_target_rtx (label); do_pending_stack_adjust (); emit_label (label_r); @@ -211,68 +213,19 @@ expand_label (tree label) if (DECL_NONLOCAL (label)) { - expand_nl_goto_receiver (); + expand_builtin_setjmp_receiver (NULL); nonlocal_goto_handler_labels - = gen_rtx_EXPR_LIST (VOIDmode, label_r, + = gen_rtx_INSN_LIST (VOIDmode, label_r, nonlocal_goto_handler_labels); } if (FORCED_LABEL (label)) - forced_labels = gen_rtx_EXPR_LIST (VOIDmode, label_r, forced_labels); + forced_labels = gen_rtx_INSN_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, @@ -361,11 +314,8 @@ parse_output_constraint (const char **constraint_p, int operand_num, } break; - case 'V': case TARGET_MEM_CONSTRAINT: case 'o': - *allows_mem = true; - break; - case '?': 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': @@ -390,29 +340,17 @@ parse_output_constraint (const char **constraint_p, int operand_num, *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) + enum constraint_num cn = lookup_constraint (p); + if (reg_class_for_constraint (cn) != NO_REGS + || insn_extra_address_constraint (cn)) *allows_reg = true; -#ifdef EXTRA_CONSTRAINT_STR - else if (EXTRA_ADDRESS_CONSTRAINT (*p, p)) - *allows_reg = true; - else if (EXTRA_MEMORY_CONSTRAINT (*p, p)) + else if (insn_extra_memory_constraint (cn)) *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 + insn_extra_constraint_allows_reg_mem (cn, allows_reg, allows_mem); break; } @@ -460,12 +398,9 @@ parse_input_constraint (const char **constraint_p, int input_num, } break; - case 'V': case TARGET_MEM_CONSTRAINT: case 'o': - *allows_mem = true; - break; - case '<': case '>': 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': @@ -514,10 +449,6 @@ parse_input_constraint (const char **constraint_p, int input_num, } /* Fall through. */ - case 'p': case 'r': - *allows_reg = true; - break; - case 'g': case 'X': *allows_reg = true; *allows_mem = true; @@ -529,23 +460,14 @@ parse_input_constraint (const char **constraint_p, int input_num, error ("invalid punctuation %qc in constraint", constraint[j]); return false; } - if (REG_CLASS_FROM_CONSTRAINT (constraint[j], constraint + j) - != NO_REGS) + enum constraint_num cn = lookup_constraint (constraint + j); + if (reg_class_for_constraint (cn) != NO_REGS + || insn_extra_address_constraint (cn)) *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)) + else if (insn_extra_memory_constraint (cn)) *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 + insn_extra_constraint_allows_reg_mem (cn, allows_reg, allows_mem); break; } @@ -591,636 +513,6 @@ 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. - - 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, 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; - - /* 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; - - if (TREE_VALUE (tail) == error_mark_node) - return; - regname = TREE_STRING_POINTER (TREE_VALUE (tail)); - - i = decode_reg_name (regname); - if (i >= 0 || i == -4) - ++nclobbers; - else if (i == -2) - error ("unknown register name %qs in %", regname); - - /* Mark clobbered registers. */ - if (i >= 0) - { - /* Clobbering the PIC register is an error. */ - if (i == (int) PIC_OFFSET_TABLE_REGNUM) - { - error ("PIC register %qs clobbered in %", regname); - return; - } - - SET_HARD_REG_BIT (clobbered_regs, i); - } - } - - /* 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 %", 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. */ - - 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, 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 - { - warning (0, "use of memory input without lvalue in " - "asm operand %d is deprecated", i + noutputs); - - if (CONSTANT_P (op)) - { - rtx mem = force_const_mem (TYPE_MODE (type), op); - if (mem) - op = validize_mem (mem); - else - op = force_reg (TYPE_MODE (type), op); - } - if (REG_P (op) - || GET_CODE (op) == SUBREG - || GET_CODE (op) == CONCAT) - { - tree qual_type = build_qualified_type (type, - (TYPE_QUALS (type) - | TYPE_QUAL_CONST)); - rtx memloc = assign_temp (qual_type, 1, 1, 1); - memloc = validize_mem (memloc); - emit_move_insn (memloc, op); - op = memloc; - } - } - } - - 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)) - ASM_OPERANDS_LABEL (body, i) - = gen_rtx_LABEL_REF (Pmode, label_rtx (TREE_VALUE (tail))); - - 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 j = decode_reg_name (regname); - 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; - } - - /* Use QImode since that's guaranteed to clobber just one reg. */ - clobbered_reg = gen_rtx_REG (QImode, j); - - /* 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); - } - - /* 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); - - /* 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) - { - 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, - 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 %"); - 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 % 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 @@ -1230,11 +522,11 @@ check_operand_nalternatives (tree outputs, tree inputs) static bool check_unique_operand_names (tree outputs, tree inputs, tree labels) { - tree i, j; + tree i, j, i_name = NULL_TREE; for (i = outputs; i ; i = TREE_CHAIN (i)) { - tree i_name = TREE_PURPOSE (TREE_PURPOSE (i)); + i_name = TREE_PURPOSE (TREE_PURPOSE (i)); if (! i_name) continue; @@ -1245,7 +537,7 @@ check_unique_operand_names (tree outputs, tree inputs, tree labels) for (i = inputs; i ; i = TREE_CHAIN (i)) { - tree i_name = TREE_PURPOSE (TREE_PURPOSE (i)); + i_name = TREE_PURPOSE (TREE_PURPOSE (i)); if (! i_name) continue; @@ -1259,7 +551,7 @@ check_unique_operand_names (tree outputs, tree inputs, tree labels) for (i = labels; i ; i = TREE_CHAIN (i)) { - tree i_name = TREE_PURPOSE (i); + i_name = TREE_PURPOSE (i); if (! i_name) continue; @@ -1274,14 +566,14 @@ check_unique_operand_names (tree outputs, tree inputs, tree labels) return true; failure: - error ("duplicate asm operand name %qs", - TREE_STRING_POINTER (TREE_PURPOSE (TREE_PURPOSE (i)))); + 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. */ +/* 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. This is generally done in the front end while creating + the ASM_EXPR generic tree that eventually becomes the GIMPLE_ASM. */ tree resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels) @@ -1415,815 +707,439 @@ resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels) return p; } -/* Generate RTL to evaluate the expression EXP. */ + +/* Generate RTL to return directly from the current function. + (That is, we bypass any return value.) */ void -expand_expr_stmt (tree exp) +expand_naked_return (void) { - rtx value; - tree type; - - value = expand_expr (exp, const0_rtx, VOIDmode, EXPAND_NORMAL); - type = TREE_TYPE (exp); + rtx_code_label *end_label; - /* If all we do is reference a volatile value in memory, - copy it to a register to be sure it is actually touched. */ - if (value && MEM_P (value) && TREE_THIS_VOLATILE (exp)) - { - if (TYPE_MODE (type) == VOIDmode) - ; - else if (TYPE_MODE (type) != BLKmode) - value = copy_to_reg (value); - else - { - rtx lab = gen_label_rtx (); + clear_pending_stack_adjust (); + do_pending_stack_adjust (); - /* Compare the value with itself to reference it. */ - emit_cmp_and_jump_insns (value, value, EQ, - expand_normal (TYPE_SIZE (type)), - BLKmode, 0, lab); - emit_label (lab); - } - } + end_label = naked_return_label; + if (end_label == 0) + end_label = naked_return_label = gen_label_rtx (); - /* Free any temporaries used to evaluate this expression. */ - free_temp_slots (); + emit_jump (end_label); } -/* Warn if EXP contains any computations whose results are not used. - Return 1 if a warning is printed; 0 otherwise. LOCUS is the - (potential) location of the expression. */ - -int -warn_if_unused_value (const_tree exp, location_t locus) +/* 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 (machine_mode mode, rtx op0, rtx op1, rtx_code_label *label, + int unsignedp, int prob) { - restart: - if (TREE_USED (exp) || TREE_NO_WARNING (exp)) - return 0; - - /* Don't warn about void constructs. This includes casting to void, - void function calls, and statement expressions with a final cast - to void. */ - if (VOID_TYPE_P (TREE_TYPE (exp))) - return 0; - - if (EXPR_HAS_LOCATION (exp)) - locus = EXPR_LOCATION (exp); - - switch (TREE_CODE (exp)) - { - case PREINCREMENT_EXPR: - case POSTINCREMENT_EXPR: - case PREDECREMENT_EXPR: - case POSTDECREMENT_EXPR: - case MODIFY_EXPR: - case INIT_EXPR: - case TARGET_EXPR: - case CALL_EXPR: - case TRY_CATCH_EXPR: - case WITH_CLEANUP_EXPR: - case EXIT_EXPR: - case VA_ARG_EXPR: - return 0; - - case BIND_EXPR: - /* For a binding, warn if no side effect within it. */ - exp = BIND_EXPR_BODY (exp); - goto restart; - - case SAVE_EXPR: - case NON_LVALUE_EXPR: - exp = TREE_OPERAND (exp, 0); - goto restart; - - case TRUTH_ORIF_EXPR: - case TRUTH_ANDIF_EXPR: - /* In && or ||, warn if 2nd operand has no side effect. */ - exp = TREE_OPERAND (exp, 1); - goto restart; - - case COMPOUND_EXPR: - if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus)) - return 1; - /* Let people do `(foo (), 0)' without a warning. */ - if (TREE_CONSTANT (TREE_OPERAND (exp, 1))) - return 0; - exp = TREE_OPERAND (exp, 1); - goto restart; - - case COND_EXPR: - /* If this is an expression with side effects, don't warn; this - case commonly appears in macro expansions. */ - if (TREE_SIDE_EFFECTS (exp)) - return 0; - goto warn; - - case INDIRECT_REF: - /* Don't warn about automatic dereferencing of references, since - the user cannot control it. */ - if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE) - { - exp = TREE_OPERAND (exp, 0); - goto restart; - } - /* Fall through. */ - - default: - /* Referencing a volatile value is a side effect, so don't warn. */ - if ((DECL_P (exp) || REFERENCE_CLASS_P (exp)) - && TREE_THIS_VOLATILE (exp)) - return 0; - - /* If this is an expression which has no operands, there is no value - to be unused. There are no such language-independent codes, - but front ends may define such. */ - if (EXPRESSION_CLASS_P (exp) && TREE_OPERAND_LENGTH (exp) == 0) - return 0; - - warn: - warning_at (locus, OPT_Wunused_value, "value computed is not used"); - return 1; - } + gcc_assert (prob <= REG_BR_PROB_BASE); + do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode, + NULL_RTX, NULL, label, prob); } - -/* 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.) */ +/* 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. */ -void -expand_naked_return (void) +static struct case_node * +add_case_node (struct case_node *head, tree low, tree high, + tree label, int prob, alloc_pool case_node_pool) { - rtx end_label; - - clear_pending_stack_adjust (); - do_pending_stack_adjust (); + struct case_node *r; - end_label = naked_return_label; - if (end_label == 0) - end_label = naked_return_label = gen_label_rtx (); + gcc_checking_assert (low); + gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high))); - emit_jump (end_label); + /* 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; } - -/* Generate RTL to return from the current function, with value VAL. */ + +/* Dump ROOT, a list or tree of case nodes, to file. */ static void -expand_value_return (rtx val) +dump_case_nodes (FILE *f, struct case_node *root, + int indent_step, int indent_level) { - /* Copy the value to the return location unless it's already there. */ + if (root == 0) + return; + indent_level++; - tree decl = DECL_RESULT (current_function_decl); - rtx return_reg = DECL_RTL (decl); - if (return_reg != val) + dump_case_nodes (f, root->left, indent_step, indent_level); + + fputs (";; ", f); + fprintf (f, "%*s", indent_step * indent_level, ""); + print_dec (root->low, f, TYPE_SIGN (TREE_TYPE (root->low))); + if (!tree_int_cst_equal (root->low, root->high)) { - 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 = 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); + fprintf (f, " ... "); + print_dec (root->high, f, TYPE_SIGN (TREE_TYPE (root->high))); } + fputs ("\n", f); - 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); + dump_case_nodes (f, root->right, indent_step, indent_level); } -/* Generate RTL to evaluate the expression RETVAL and return it - from the current function. */ +#ifndef HAVE_casesi +#define HAVE_casesi 0 +#endif -void -expand_return (tree retval) -{ - rtx result_rtl; - rtx val = 0; - tree retval_rhs; +#ifndef HAVE_tablejump +#define HAVE_tablejump 0 +#endif - /* 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; - } +/* Return the smallest number of different values for which it is best to use a + jump-table instead of a tree of conditional branches. */ - 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; +static unsigned int +case_values_threshold (void) +{ + unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD); - result_rtl = DECL_RTL (DECL_RESULT (current_function_decl)); + if (threshold == 0) + threshold = targetm.case_values_threshold (); - /* 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); + return threshold; +} - /* If the result is an aggregate that is being returned in one (or more) - registers, load the registers here. The compiler currently can't handle - copying a BLKmode value into registers. We could put this code in a - more general area (for use by everyone instead of just function - call/return), but until this feature is generally usable it is kept here - (and in expand_call). */ +/* 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. */ - else if (retval_rhs != 0 - && TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode - && REG_P (result_rtl)) - { - int i; - unsigned HOST_WIDE_INT bitpos, xbitpos; - unsigned HOST_WIDE_INT padding_correction = 0; - unsigned HOST_WIDE_INT bytes - = int_size_in_bytes (TREE_TYPE (retval_rhs)); - int n_regs = (bytes + UNITS_PER_WORD - 1) / UNITS_PER_WORD; - unsigned int bitsize - = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)), BITS_PER_WORD); - rtx *result_pseudos = XALLOCAVEC (rtx, n_regs); - rtx result_reg, src = NULL_RTX, dst = NULL_RTX; - rtx result_val = expand_normal (retval_rhs); - enum machine_mode tmpmode, result_reg_mode; - - if (bytes == 0) - { - expand_null_return (); - return; - } +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 structure doesn't take up a whole number of words, see - whether the register value should be padded on the left or on - the right. Set PADDING_CORRECTION to the number of padding - bits needed on the left side. - - In most ABIs, the structure will be returned at the least end of - the register, which translates to right padding on little-endian - targets and left padding on big-endian targets. The opposite - holds if the structure is returned at the most significant - end of the register. */ - if (bytes % UNITS_PER_WORD != 0 - && (targetm.calls.return_in_msb (TREE_TYPE (retval_rhs)) - ? !BYTES_BIG_ENDIAN - : BYTES_BIG_ENDIAN)) - padding_correction = (BITS_PER_WORD - ((bytes % UNITS_PER_WORD) - * BITS_PER_UNIT)); - - /* Copy the structure BITSIZE bits at a time. */ - for (bitpos = 0, xbitpos = padding_correction; - bitpos < bytes * BITS_PER_UNIT; - bitpos += bitsize, xbitpos += bitsize) - { - /* We need a new destination pseudo each time xbitpos is - on a word boundary and when xbitpos == padding_correction - (the first time through). */ - if (xbitpos % BITS_PER_WORD == 0 - || xbitpos == padding_correction) - { - /* Generate an appropriate register. */ - dst = gen_reg_rtx (word_mode); - result_pseudos[xbitpos / BITS_PER_WORD] = dst; + /* 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 () + || ! tree_fits_uhwi_p (range) + || compare_tree_int (range, max_ratio * count) > 0) + return true; - /* Clear the destination before we move anything into it. */ - emit_move_insn (dst, CONST0_RTX (GET_MODE (dst))); - } + return false; +} - /* We need a new source operand each time bitpos is on a word - boundary. */ - if (bitpos % BITS_PER_WORD == 0) - src = operand_subword_force (result_val, - bitpos / BITS_PER_WORD, - BLKmode); - - /* Use bitpos for the source extraction (left justified) and - xbitpos for the destination store (right justified). */ - store_bit_field (dst, bitsize, xbitpos % BITS_PER_WORD, word_mode, - extract_bit_field (src, bitsize, - bitpos % BITS_PER_WORD, 1, - NULL_RTX, word_mode, word_mode)); - } +/* 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: - tmpmode = GET_MODE (result_rtl); - if (tmpmode == BLKmode) - { - /* Find the smallest integer mode large enough to hold the - entire structure and use that mode instead of BLKmode - on the USE insn for the return register. */ - for (tmpmode = GET_CLASS_NARROWEST_MODE (MODE_INT); - tmpmode != VOIDmode; - tmpmode = GET_MODE_WIDER_MODE (tmpmode)) - /* Have we found a large enough mode? */ - if (GET_MODE_SIZE (tmpmode) >= bytes) - break; + 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. - /* A suitable mode should have been found. */ - gcc_assert (tmpmode != VOIDmode); + Load the index into a register. - PUT_MODE (result_rtl, tmpmode); - } + The list of cases is rearranged into a binary tree, + nearly optimal assuming equal probability for each case. - if (GET_MODE_SIZE (tmpmode) < GET_MODE_SIZE (word_mode)) - result_reg_mode = word_mode; - else - result_reg_mode = tmpmode; - result_reg = gen_reg_rtx (result_reg_mode); + The tree is transformed into RTL, eliminating redundant + test conditions at the same time. - for (i = 0; i < n_regs; i++) - emit_move_insn (operand_subword (result_reg, i, 0, result_reg_mode), - result_pseudos[i]); + If program flow could reach the end of the decision tree + an unconditional jump to the default code is emitted. - if (tmpmode != result_reg_mode) - result_reg = gen_lowpart (tmpmode, result_reg); + The above process is unaware of the CFG. The caller has to fix up + the CFG itself. This is done in cfgexpand.c. */ - expand_value_return (result_reg); - } - 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, 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) +emit_case_decision_tree (tree index_expr, tree index_type, + case_node_ptr case_list, rtx_code_label *default_label, + int default_prob) { - 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); + rtx index = expand_normal (index_expr); -#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 are 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); - -#if ARG_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM - if (fixed_regs[ARG_POINTER_REGNUM]) + if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT + && ! have_insn_for (COMPARE, GET_MODE (index))) { -#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 ())); - } + int unsignedp = TYPE_UNSIGNED (index_type); + 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; + } } -#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 ()); -} - -/* Generate RTL for the automatic variable declaration DECL. - (Other kinds of declarations are simply ignored if seen here.) */ + do_pending_stack_adjust (); -void -expand_decl (tree decl) -{ - tree type; + 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); + } - type = TREE_TYPE (decl); + balance_case_nodes (&case_list, NULL); - /* For a CONST_DECL, set mode, alignment, and sizes from those of the - type in case this node is used in a reference. */ - if (TREE_CODE (decl) == CONST_DECL) + if (dump_file && (dump_flags & TDF_DETAILS)) { - DECL_MODE (decl) = TYPE_MODE (type); - DECL_ALIGN (decl) = TYPE_ALIGN (type); - DECL_SIZE (decl) = TYPE_SIZE (type); - DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type); - return; + 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); } - /* Otherwise, only automatic variables need any expansion done. Static and - external variables, and external functions, will be handled by - `assemble_variable' (called from finish_decl). TYPE_DECL requires - nothing. PARM_DECLs are handled in `assign_parms'. */ - if (TREE_CODE (decl) != VAR_DECL) - return; + emit_case_nodes (index, case_list, default_label, default_prob, index_type); + if (default_label) + emit_jump (default_label); +} - if (TREE_STATIC (decl) || DECL_EXTERNAL (decl)) - return; +/* Return the sum of probabilities of outgoing edges of basic block BB. */ - /* Create the RTL representation for the variable. */ +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; +} - if (type == error_mark_node) - SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx)); +/* 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. */ - else if (DECL_SIZE (decl) == 0) +static inline int +conditional_probability (int target_prob, int base_prob) +{ + if (base_prob > 0) { - /* Variable with incomplete type. */ - rtx x; - if (DECL_INITIAL (decl) == 0) - /* Error message was already done; now avoid a crash. */ - x = gen_rtx_MEM (BLKmode, const0_rtx); - else - /* An initializer is going to decide the size of this array. - Until we know the size, represent its address with a reg. */ - x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode)); - - set_mem_attributes (x, decl, 1); - SET_DECL_RTL (decl, x); + gcc_assert (target_prob >= 0); + gcc_assert (target_prob <= base_prob); + return GCOV_COMPUTE_SCALE (target_prob, base_prob); } - else if (use_register_for_decl (decl)) - { - /* Automatic variable that can go in a register. */ - enum machine_mode reg_mode = promote_decl_mode (decl, NULL); - - SET_DECL_RTL (decl, gen_reg_rtx (reg_mode)); + return -1; +} - /* Note if the object is a user variable. */ - if (!DECL_ARTIFICIAL (decl)) - mark_user_reg (DECL_RTL (decl)); +/* 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. - if (POINTER_TYPE_P (type)) - mark_reg_pointer (DECL_RTL (decl), - TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl)))); - } + First, a jump insn is emitted. First we try "casesi". If that + fails, try "tablejump". A target *must* have one of them (or both). - else - { - rtx oldaddr = 0; - rtx addr; - rtx x; - - /* Variable-sized decls are dealt with in the gimplifier. */ - gcc_assert (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST); - - /* If we previously made RTL for this decl, it must be an array - whose size was determined by the initializer. - The old address was a register; set that register now - to the proper address. */ - if (DECL_RTL_SET_P (decl)) - { - gcc_assert (MEM_P (DECL_RTL (decl))); - gcc_assert (REG_P (XEXP (DECL_RTL (decl), 0))); - oldaddr = XEXP (DECL_RTL (decl), 0); - } + Then, a table with the target labels is emitted. - /* Set alignment we actually gave this decl. */ - DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT - : GET_MODE_BITSIZE (DECL_MODE (decl))); - DECL_USER_ALIGN (decl) = 0; + The process is unaware of the CFG. The caller has to fix up + the CFG itself. This is done in cfgexpand.c. */ - x = assign_temp (decl, 1, 1, 1); - set_mem_attributes (x, decl, 1); - SET_DECL_RTL (decl, x); - - if (oldaddr) +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_code_label *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) { - addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr); - if (addr != oldaddr) - emit_move_insn (oldaddr, addr); + minval = build_int_cst (index_type, 0); + range = maxval; + has_gaps = true; } + try_with_tablejump = true; } -} - -/* 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, NULL_RTX); - return ret; -} + /* Get table of labels to jump to, in order of case index. */ -/* Emit code to restore the current value of stack. */ -void -expand_stack_restore (tree var) -{ - rtx sa = expand_normal (var); + ncases = tree_to_shwi (range) + 1; + labelvec = XALLOCAVEC (rtx, ncases); + memset (labelvec, 0, ncases * sizeof (rtx)); - sa = convert_memory_address (Pmode, sa); - emit_stack_restore (SAVE_BLOCK, sa, NULL_RTX); -} - -/* 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. The bounds on the case range, LOW and HIGH, - are converted to case's index type TYPE. */ - -static struct case_node * -add_case_node (struct case_node *head, tree type, tree low, tree high, - tree label, alloc_pool case_node_pool) -{ - tree min_value, max_value; - struct case_node *r; - - gcc_assert (TREE_CODE (low) == INTEGER_CST); - gcc_assert (!high || TREE_CODE (high) == INTEGER_CST); + 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_to_uhwi (fold_build2 (MINUS_EXPR, index_type, + n->low, minval)); + HOST_WIDE_INT i_high + = tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type, + n->high, minval)); + HOST_WIDE_INT i; + + for (i = i_low; i <= i_high; i ++) + labelvec[i] + = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label)); + } - min_value = TYPE_MIN_VALUE (type); - max_value = TYPE_MAX_VALUE (type); + /* 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 there's no HIGH value, then this is not a case range; it's - just a simple case label. But that's just a degenerate case - range. - If the bounds are equal, turn this into the one-value case. */ - if (!high || tree_int_cst_equal (low, high)) + if (has_gaps) { - /* If the simple case value is unreachable, ignore it. */ - if ((TREE_CODE (min_value) == INTEGER_CST - && tree_int_cst_compare (low, min_value) < 0) - || (TREE_CODE (max_value) == INTEGER_CST - && tree_int_cst_compare (low, max_value) > 0)) - return head; - low = fold_convert (type, low); - high = low; + /* 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 { - /* If the entire case range is unreachable, ignore it. */ - if ((TREE_CODE (min_value) == INTEGER_CST - && tree_int_cst_compare (high, min_value) < 0) - || (TREE_CODE (max_value) == INTEGER_CST - && tree_int_cst_compare (low, max_value) > 0)) - return head; - - /* If the lower bound is less than the index type's minimum - value, truncate the range bounds. */ - if (TREE_CODE (min_value) == INTEGER_CST - && tree_int_cst_compare (low, min_value) < 0) - low = min_value; - low = fold_convert (type, low); - - /* If the upper bound is greater than the index type's maximum - value, truncate the range bounds. */ - if (TREE_CODE (max_value) == INTEGER_CST - && tree_int_cst_compare (high, max_value) > 0) - high = max_value; - high = fold_convert (type, high); + base -= default_prob; + default_prob = 0; } + if (default_edge) + default_edge->probability = default_prob; - /* Add this label to the chain. Make sure to drop overflow flags. */ - r = (struct case_node *) pool_alloc (case_node_pool); - r->low = build_int_cst_wide (TREE_TYPE (low), TREE_INT_CST_LOW (low), - TREE_INT_CST_HIGH (low)); - r->high = build_int_cst_wide (TREE_TYPE (high), TREE_INT_CST_LOW (high), - TREE_INT_CST_HIGH (high)); - r->code_label = label; - r->parent = r->left = NULL; - r->right = head; - return r; -} - -/* Maximum number of case bit tests. */ -#define MAX_CASE_BIT_TESTS 3 - -/* By default, enable case bit tests on targets with ashlsi3. */ -#ifndef CASE_USE_BIT_TESTS -#define CASE_USE_BIT_TESTS (optab_handler (ashl_optab, word_mode)->insn_code \ - != CODE_FOR_nothing) -#endif - - -/* A case_bit_test represents a set of case nodes that may be - selected from using a bit-wise comparison. HI and LO hold - the integer to be tested against, LABEL contains the label - to jump to upon success and BITS counts the number of case - nodes handled by this test, typically the number of bits - set in HI:LO. */ - -struct case_bit_test -{ - HOST_WIDE_INT hi; - HOST_WIDE_INT lo; - rtx label; - int bits; -}; - -/* Determine whether "1 << x" is relatively cheap in word_mode. */ - -static -bool lshift_cheap_p (void) -{ - static bool init = false; - static bool cheap = true; + /* 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 = GCOV_COMPUTE_SCALE (e->probability, base); + } - if (!init) + if (try_with_tablejump) { - rtx reg = gen_rtx_REG (word_mode, 10000); - int cost = rtx_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg), SET, - optimize_insn_for_speed_p ()); - cheap = cost < COSTS_N_INSNS (3); - init = true; + 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_table_data (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_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE, + gen_rtvec_v (ncases, labelvec))); - return cheap; + /* Record no drop-through after the table. */ + emit_barrier (); } -/* Comparison function for qsort to order bit tests by decreasing - number of case nodes, i.e. the node with the most cases gets - tested first. */ +/* Reset the aux field of all outgoing edges of basic block BB. */ -static int -case_bit_test_cmp (const void *p1, const void *p2) +static inline void +reset_out_edges_aux (basic_block bb) { - const struct case_bit_test *const d1 = (const struct case_bit_test *) p1; - const struct case_bit_test *const d2 = (const struct case_bit_test *) p2; - - if (d2->bits != d1->bits) - return d2->bits - d1->bits; - - /* Stabilize the sort. */ - return CODE_LABEL_NUMBER (d2->label) - CODE_LABEL_NUMBER (d1->label); + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, bb->succs) + e->aux = (void *)0; } -/* Expand a switch statement by a short sequence of bit-wise - comparisons. "switch(x)" is effectively converted into - "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are - integer constants. - - INDEX_EXPR is the value being switched on, which is of - type INDEX_TYPE. MINVAL is the lowest case value of in - the case nodes, of INDEX_TYPE type, and RANGE is highest - value minus MINVAL, also of type INDEX_TYPE. NODES is - the set of case nodes, and DEFAULT_LABEL is the label to - branch to should none of the cases match. - - There *MUST* be MAX_CASE_BIT_TESTS or less unique case - node targets. */ +/* 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 void -emit_case_bit_tests (tree index_type, tree index_expr, tree minval, - tree range, case_node_ptr nodes, rtx default_label) +static inline void +compute_cases_per_edge (gswitch *stmt) { - struct case_bit_test test[MAX_CASE_BIT_TESTS]; - enum machine_mode mode; - rtx expr, index, label; - unsigned int i,j,lo,hi; - struct case_node *n; - unsigned int count; - - count = 0; - for (n = nodes; n; n = n->right) + 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) { - label = label_rtx (n->code_label); - for (i = 0; i < count; i++) - if (label == test[i].label) - break; - - if (i == count) - { - gcc_assert (count < MAX_CASE_BIT_TESTS); - test[i].hi = 0; - test[i].lo = 0; - test[i].label = label; - test[i].bits = 1; - count++; - } - else - test[i].bits++; - - lo = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, - n->low, minval), 1); - hi = tree_low_cst (fold_build2 (MINUS_EXPR, index_type, - n->high, minval), 1); - for (j = lo; j <= hi; j++) - if (j >= HOST_BITS_PER_WIDE_INT) - test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT); - else - test[i].lo |= (HOST_WIDE_INT) 1 << j; + 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); } - - qsort (test, count, sizeof(*test), case_bit_test_cmp); - - index_expr = fold_build2 (MINUS_EXPR, index_type, - fold_convert (index_type, index_expr), - fold_convert (index_type, minval)); - index = expand_normal (index_expr); - do_pending_stack_adjust (); - - mode = TYPE_MODE (index_type); - expr = expand_normal (range); - if (default_label) - emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1, - default_label); - - index = convert_to_mode (word_mode, index, 0); - index = expand_binop (word_mode, ashl_optab, const1_rtx, - index, NULL_RTX, 1, OPTAB_WIDEN); - - for (i = 0; i < count; i++) - { - expr = immed_double_const (test[i].lo, test[i].hi, word_mode); - expr = expand_binop (word_mode, and_optab, index, expr, - NULL_RTX, 1, OPTAB_WIDEN); - emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX, - word_mode, 1, test[i].label); - } - - if (default_label) - emit_jump (default_label); } -#ifndef HAVE_casesi -#define HAVE_casesi 0 -#endif - -#ifndef HAVE_tablejump -#define HAVE_tablejump 0 -#endif - /* 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 @@ -2231,395 +1147,237 @@ emit_case_bit_tests (tree index_type, tree index_expr, tree minval, Generate the code to test it and jump to the right place. */ void -expand_case (gimple stmt) +expand_case (gswitch *stmt) { tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE; - rtx default_label = 0; - struct case_node *n; + rtx_code_label *default_label = NULL; unsigned int count, uniq; - rtx index; - rtx table_label; - int ncases; - rtx *labelvec; int i; - rtx before_case, end, lab; - + int ncases = gimple_switch_num_labels (stmt); tree index_expr = gimple_switch_index (stmt); tree index_type = TREE_TYPE (index_expr); - int unsignedp = TYPE_UNSIGNED (index_type); - - /* The insn after which the case dispatch should finally - be emitted. Zero for a dummy. */ - rtx start; + 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; - /* Label to jump to if no case matches. */ - tree default_label_decl = NULL_TREE; - - alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool", - sizeof (struct case_node), - 100); - - do_pending_stack_adjust (); - - /* An ERROR_MARK occurs for various reasons including invalid data type. */ - if (index_type != error_mark_node) - { - tree elt; - bitmap label_bitmap; - int stopi = 0; - - /* cleanup_tree_cfg removes all SWITCH_EXPR with their index - expressions being INTEGER_CST. */ - gcc_assert (TREE_CODE (index_expr) != INTEGER_CST); - - /* The default case, if ever taken, is the first element. */ - elt = gimple_switch_label (stmt, 0); - if (!CASE_LOW (elt) && !CASE_HIGH (elt)) - { - default_label_decl = CASE_LABEL (elt); - stopi = 1; - } - - for (i = gimple_switch_num_labels (stmt) - 1; i >= stopi; --i) - { - tree low, high; - elt = gimple_switch_label (stmt, i); - - low = CASE_LOW (elt); - gcc_assert (low); - high = CASE_HIGH (elt); - - /* Discard empty ranges. */ - if (high && tree_int_cst_lt (high, low)) - continue; + /* A pool for case nodes. */ + alloc_pool case_node_pool; - case_list = add_case_node (case_list, index_type, low, high, - CASE_LABEL (elt), case_node_pool); - } - - - before_case = start = get_last_insn (); - if (default_label_decl) - default_label = label_rtx (default_label_decl); - - /* Get upper and lower bounds of case values. */ - - uniq = 0; - count = 0; - label_bitmap = BITMAP_ALLOC (NULL); - for (n = case_list; n; n = n->right) - { - /* Count the elements and track the largest and smallest - of them (treating them as signed even if they are not). */ - if (count++ == 0) - { - minval = n->low; - maxval = n->high; - } - else - { - if (tree_int_cst_lt (n->low, minval)) - minval = n->low; - if (tree_int_cst_lt (maxval, n->high)) - maxval = n->high; - } - /* A range counts double, since it requires two compares. */ - if (! tree_int_cst_equal (n->low, n->high)) - count++; - - /* If we have not seen this label yet, then increase the - number of unique case node targets seen. */ - lab = label_rtx (n->code_label); - if (!bitmap_bit_p (label_bitmap, CODE_LABEL_NUMBER (lab))) - { - bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab)); - uniq++; - } - } - - BITMAP_FREE (label_bitmap); - - /* cleanup_tree_cfg removes all SWITCH_EXPR with a single - destination, such as one with a default case only. However, - it doesn't remove cases that are out of range for the switch - type, so we may still get a zero here. */ - if (count == 0) - { - if (default_label) - emit_jump (default_label); - free_alloc_pool (case_node_pool); - return; - } - - /* Compute span of values. */ - range = fold_build2 (MINUS_EXPR, index_type, maxval, minval); - - /* Try implementing this switch statement by a short sequence of - bit-wise comparisons. However, we let the binary-tree case - below handle constant index expressions. */ - if (CASE_USE_BIT_TESTS - && ! TREE_CONSTANT (index_expr) - && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0 - && compare_tree_int (range, 0) > 0 - && lshift_cheap_p () - && ((uniq == 1 && count >= 3) - || (uniq == 2 && count >= 5) - || (uniq == 3 && count >= 6))) - { - /* Optimize the case where all the case values fit in a - word without having to subtract MINVAL. In this case, - we can optimize away the subtraction. */ - if (compare_tree_int (minval, 0) > 0 - && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0) - { - minval = build_int_cst (index_type, 0); - range = maxval; - } - emit_case_bit_tests (index_type, index_expr, minval, range, - case_list, default_label); - } - - /* If range of values is much bigger than number of values, - make a sequence of conditional branches instead of a dispatch. - If the switch-index is a constant, do it this way - because we can optimize it. */ - - else if (count < targetm.case_values_threshold () - || compare_tree_int (range, - (optimize_insn_for_size_p () ? 3 : 10) * count) > 0 - /* RANGE may be signed, and really large ranges will show up - as negative numbers. */ - || compare_tree_int (range, 0) < 0 -#ifndef ASM_OUTPUT_ADDR_DIFF_ELT - || flag_pic -#endif - || !flag_jump_tables - || TREE_CONSTANT (index_expr) - /* If neither casesi or tablejump is available, we can - only go this way. */ - || (!HAVE_casesi && !HAVE_tablejump)) - { - index = expand_normal (index_expr); - - /* 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. */ - - if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT - && ! have_insn_for (COMPARE, GET_MODE (index))) - { - 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); + /* 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; - /* We generate a binary decision tree to select the - appropriate target code. This is done as follows: + /* 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); - The list of cases is rearranged into a binary tree, - nearly optimal assuming equal probability for each case. + do_pending_stack_adjust (); - The tree is transformed into RTL, eliminating - redundant test conditions at the same time. + /* Find the default case target label. */ + default_label = jump_target_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)); - If program flow could reach the end of the - decision tree an unconditional jump to the - default code is emitted. */ + /* Compute span of values. */ + range = fold_build2 (MINUS_EXPR, index_type, maxval, minval); - use_cost_table = estimate_case_costs (case_list); - balance_case_nodes (&case_list, NULL); - emit_case_nodes (index, case_list, default_label, index_type); - if (default_label) - emit_jump (default_label); - } - else - { - rtx fallback_label = label_rtx (case_list->code_label); - table_label = gen_label_rtx (); - if (! try_casesi (index_type, index_expr, minval, range, - table_label, default_label, fallback_label)) - { - bool ok; - - /* Index jumptables from zero for suitable values of - minval to avoid a subtraction. */ - 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; - } + /* Listify the labels queue and gather some numbers to decide + how to expand this switch(). */ + uniq = 0; + count = 0; + hash_set seen_labels; + compute_cases_per_edge (stmt); - ok = try_tablejump (index_type, index_expr, minval, range, - table_label, default_label); - gcc_assert (ok); - } + 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 (!seen_labels.add (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 = wide_int_to_tree (index_type, 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 = wide_int_to_tree (index_type, 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); + } + reset_out_edges_aux (bb); - /* Get table of labels to jump to, in order of case index. */ + /* 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); - ncases = tree_low_cst (range, 0) + 1; - labelvec = XALLOCAVEC (rtx, ncases); - memset (labelvec, 0, ncases * sizeof (rtx)); + rtx_insn *before_case = get_last_insn (); - 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)); - } + /* Decide how to expand this switch. + The two options at this point are a dispatch table (casesi or + tablejump) or a decision tree. */ - /* 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) - labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label); - - /* 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))); + 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); - /* Record no drop-through after the table. */ - emit_barrier (); - } - - before_case = NEXT_INSN (before_case); - end = get_last_insn (); - reorder_insns (before_case, end, start); - } + reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case); free_temp_slots (); free_alloc_pool (case_node_pool); } -/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */ +/* 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. -static void -do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label, - int unsignedp) + 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 dispatch_table) { - do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode, - NULL_RTX, NULL_RTX, label, -1); -} - -/* Not all case values are encountered equally. This function - uses a heuristic to weight case labels, in cases where that - looks like a reasonable thing to do. + tree index_type = integer_type_node; + machine_mode index_mode = TYPE_MODE (index_type); - Right now, all we try to guess is text, and we establish the - following weights: + int ncases = dispatch_table.length (); - chars above space: 16 - digits: 16 - default: 12 - space, punct: 8 - tab: 4 - newline: 2 - other "\" chars: 1 - remaining chars: 0 + do_pending_stack_adjust (); + rtx_insn *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: - If we find any cases in the switch that are not either -1 or in the range - of valid ASCII characters, or are control characters other than those - commonly used with "\", don't treat this switch scanning text. + "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}" - Return 1 if these nodes are suitable for cost estimation, otherwise - return 0. */ + ==> -static int -estimate_case_costs (case_node_ptr node) -{ - tree min_ascii = integer_minus_one_node; - tree max_ascii = build_int_cst (TREE_TYPE (node->high), 127); - case_node_ptr n; - int i; - - /* If we haven't already made the cost table, make it now. Note that the - lower bound of the table is -1, not zero. */ + if (index == 0) do_0; else index--; + if (index == 0) do_1; else index--; + ... + if (index == 0) do_N; else index--; - if (! cost_table_initialized) + 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_code_label *lab = jump_target_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 { - cost_table_initialized = 1; - - for (i = 0; i < 128; i++) + /* 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_code_label *default_label = gen_label_rtx (); + + for (int i = ncases - 1; i >= 0; --i) { - if (ISALNUM (i)) - COST_TABLE (i) = 16; - else if (ISPUNCT (i)) - COST_TABLE (i) = 8; - else if (ISCNTRL (i)) - COST_TABLE (i) = -1; + 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); } - COST_TABLE (' ') = 8; - COST_TABLE ('\t') = 4; - COST_TABLE ('\0') = 4; - COST_TABLE ('\n') = 2; - COST_TABLE ('\f') = 1; - COST_TABLE ('\v') = 1; - COST_TABLE ('\b') = 1; + 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); } - /* See if all the case expressions look like text. It is text if the - constant is >= -1 and the highest constant is <= 127. Do all comparisons - as signed arithmetic since we don't want to ever access cost_table with a - value less than -1. Also check that none of the constants in a range - are strange control characters. */ + /* Dispatching something not handled? Trap! */ + expand_builtin_trap (); - for (n = node; n; n = n->right) - { - if (tree_int_cst_lt (n->low, min_ascii) - || tree_int_cst_lt (max_ascii, n->high)) - return 0; - - for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low); - i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++) - if (COST_TABLE (i) < 0) - return 0; - } + reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case); - /* All interesting values are within the range of interesting - ASCII characters. */ - return 1; + 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 @@ -2638,7 +1396,6 @@ balance_case_nodes (case_node_ptr *head, case_node_ptr parent) np = *head; if (np) { - int cost = 0; int i = 0; int ranges = 0; case_node_ptr *npp; @@ -2649,14 +1406,7 @@ balance_case_nodes (case_node_ptr *head, case_node_ptr parent) while (np) { if (!tree_int_cst_equal (np->low, np->high)) - { - ranges++; - if (use_cost_table) - cost += COST_TABLE (TREE_INT_CST_LOW (np->high)); - } - - if (use_cost_table) - cost += COST_TABLE (TREE_INT_CST_LOW (np->low)); + ranges++; i++; np = np->right; @@ -2667,37 +1417,9 @@ balance_case_nodes (case_node_ptr *head, case_node_ptr parent) /* Split this list if it is long enough for that to help. */ npp = head; left = *npp; - if (use_cost_table) - { - /* Find the place in the list that bisects the list's total cost, - Here I gets half the total cost. */ - int n_moved = 0; - i = (cost + 1) / 2; - while (1) - { - /* Skip nodes while their cost does not reach that amount. */ - if (!tree_int_cst_equal ((*npp)->low, (*npp)->high)) - i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high)); - i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low)); - if (i <= 0) - break; - npp = &(*npp)->right; - n_moved += 1; - } - if (n_moved == 0) - { - /* Leave this branch lopsided, but optimize left-hand - side and fill in `parent' fields for right-hand side. */ - np = *head; - np->parent = parent; - balance_case_nodes (&np->left, np); - for (; np->right; np = np->right) - np->right->parent = np; - return; - } - } + /* If there are just three nodes, split at the middle one. */ - else if (i == 3) + if (i == 3) npp = &(*npp)->right; else { @@ -2724,6 +1446,9 @@ balance_case_nodes (case_node_ptr *head, case_node_ptr parent) /* 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 { @@ -2731,8 +1456,12 @@ balance_case_nodes (case_node_ptr *head, case_node_ptr parent) 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; + { + np->right->parent = np; + (*head)->subtree_prob += np->right->subtree_prob; + } } } } @@ -2845,6 +1574,7 @@ node_is_bounded (case_node_ptr node, tree 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. @@ -2872,13 +1602,15 @@ node_is_bounded (case_node_ptr node, tree index_type) 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, - tree index_type) +emit_case_nodes (rtx index, case_node_ptr node, rtx_code_label *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); - enum machine_mode mode = GET_MODE (index); - enum machine_mode imode = TYPE_MODE (index_type); + int probability; + int prob = node->prob, subtree_prob = node->subtree_prob; + machine_mode mode = GET_MODE (index); + machine_mode imode = TYPE_MODE (index_type); /* Handle indices detected as constant during RTL expansion. */ if (mode == VOIDmode) @@ -2891,15 +1623,18 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_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); - + jump_target_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. @@ -2910,26 +1645,36 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, 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)); - emit_case_nodes (index, node->left, default_label, index_type); + 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)); - emit_case_nodes (index, node->right, default_label, index_type); + 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 @@ -2947,21 +1692,27 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, /* 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); + jump_target_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); + jump_target_rtx (node->left->code_label), + unsignedp, probability); } else @@ -2970,9 +1721,15 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, then emit the code for one side at a time. */ tree test_label - = build_decl (CURR_INSN_LOCATION, - LABEL_DECL, NULL_TREE, NULL_TREE); - + = build_decl (curr_insn_location (), + LABEL_DECL, NULL_TREE, void_type_node); + + /* 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 @@ -2980,11 +1737,13 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, expand_normal (node->high), unsignedp), GT, NULL_RTX, mode, unsignedp, - label_rtx (test_label)); + 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, index_type); + emit_case_nodes (index, node->left, default_label, default_prob, index_type); /* If left-hand subtree does nothing, go to default. */ if (default_label) @@ -2992,7 +1751,7 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, /* Code branches here for the right-hand subtree. */ expand_label (test_label); - emit_case_nodes (index, node->right, default_label, index_type); + emit_case_nodes (index, node->right, default_label, default_prob, index_type); } } @@ -3010,28 +1769,39 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, { 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); + default_label, + probability); + default_prob /= 2; } - emit_case_nodes (index, node->right, default_label, index_type); + emit_case_nodes (index, node->right, default_label, default_prob, index_type); } else - /* 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 = 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), + jump_target_rtx (node->right->code_label), + unsignedp, probability); + } + } else if (node->right == 0 && node->left != 0) { @@ -3041,27 +1811,39 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, { 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); + default_label, + probability); + default_prob /= 2; } - emit_case_nodes (index, node->left, default_label, index_type); + emit_case_nodes (index, node->left, default_label, + default_prob, index_type); } else - /* 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 = 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), + jump_target_rtx (node->left->code_label), + unsignedp, probability); + } } } else @@ -3080,43 +1862,58 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, 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. */ - 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)); + { + /* 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); + test_label = build_decl (curr_insn_location (), + LABEL_DECL, NULL_TREE, void_type_node); + 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)); + 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)); + label_rtx (node->code_label), + probability); /* Handle the left-hand subtree. */ - emit_case_nodes (index, node->left, default_label, index_type); + emit_case_nodes (index, node->left, default_label, default_prob, index_type); /* If right node had to be handled later, do that now. */ @@ -3128,7 +1925,7 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, emit_jump (default_label); expand_label (test_label); - emit_case_nodes (index, node->right, default_label, index_type); + emit_case_nodes (index, node->right, default_label, default_prob, index_type); } } @@ -3138,26 +1935,35 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, 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); + 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)); + label_rtx (node->code_label), + probability); - emit_case_nodes (index, node->right, default_label, index_type); + emit_case_nodes (index, node->right, default_label, default_prob, index_type); } else if (node->right == 0 && node->left != 0) @@ -3166,26 +1972,35 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, 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); + 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)); + label_rtx (node->code_label), + probability); - emit_case_nodes (index, node->left, default_label, index_type); + emit_case_nodes (index, node->left, default_label, default_prob, index_type); } else @@ -3198,24 +2013,32 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, 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); + 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); + default_label, + probability); } else if (!low_bound && !high_bound) { @@ -3235,11 +2058,14 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, 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); + mode, 1, default_label, probability); } - emit_jump (label_rtx (node->code_label)); + emit_jump (jump_target_rtx (node->code_label)); } } }