| /* Generate code from machine description to recognize rtl as insns. |
| Copyright (C) 1987-2017 Free Software Foundation, Inc. |
| |
| This file is part of GCC. |
| |
| GCC is free software; you can redistribute it and/or modify it |
| under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 3, or (at your option) |
| any later version. |
| |
| GCC is distributed in the hope that it will be useful, but WITHOUT |
| ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
| or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public |
| License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GCC; see the file COPYING3. If not see |
| <http://www.gnu.org/licenses/>. */ |
| |
| |
| /* This program is used to produce insn-recog.c, which contains a |
| function called `recog' plus its subroutines. These functions |
| contain a decision tree that recognizes whether an rtx, the |
| argument given to recog, is a valid instruction. |
| |
| recog returns -1 if the rtx is not valid. If the rtx is valid, |
| recog returns a nonnegative number which is the insn code number |
| for the pattern that matched. This is the same as the order in the |
| machine description of the entry that matched. This number can be |
| used as an index into various insn_* tables, such as insn_template, |
| insn_outfun, and insn_n_operands (found in insn-output.c). |
| |
| The third argument to recog is an optional pointer to an int. If |
| present, recog will accept a pattern if it matches except for |
| missing CLOBBER expressions at the end. In that case, the value |
| pointed to by the optional pointer will be set to the number of |
| CLOBBERs that need to be added (it should be initialized to zero by |
| the caller). If it is set nonzero, the caller should allocate a |
| PARALLEL of the appropriate size, copy the initial entries, and |
| call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs. |
| |
| This program also generates the function `split_insns', which |
| returns 0 if the rtl could not be split, or it returns the split |
| rtl as an INSN list. |
| |
| This program also generates the function `peephole2_insns', which |
| returns 0 if the rtl could not be matched. If there was a match, |
| the new rtl is returned in an INSN list, and LAST_INSN will point |
| to the last recognized insn in the old sequence. |
| |
| |
| At a high level, the algorithm used in this file is as follows: |
| |
| 1. Build up a decision tree for each routine, using the following |
| approach to matching an rtx: |
| |
| - First determine the "shape" of the rtx, based on GET_CODE, |
| XVECLEN and XINT. This phase examines SET_SRCs before SET_DESTs |
| since SET_SRCs tend to be more distinctive. It examines other |
| operands in numerical order, since the canonicalization rules |
| prefer putting complex operands of commutative operators first. |
| |
| - Next check modes and predicates. This phase examines all |
| operands in numerical order, even for SETs, since the mode of a |
| SET_DEST is exact while the mode of a SET_SRC can be VOIDmode |
| for constant integers. |
| |
| - Next check match_dups. |
| |
| - Finally check the C condition and (where appropriate) pnum_clobbers. |
| |
| 2. Try to optimize the tree by removing redundant tests, CSEing tests, |
| folding tests together, etc. |
| |
| 3. Look for common subtrees and split them out into "pattern" routines. |
| These common subtrees can be identical or they can differ in mode, |
| code, or integer (usually an UNSPEC or UNSPEC_VOLATILE code). |
| In the latter case the users of the pattern routine pass the |
| appropriate mode, etc., as argument. For example, if two patterns |
| contain: |
| |
| (plus:SI (match_operand:SI 1 "register_operand") |
| (match_operand:SI 2 "register_operand")) |
| |
| we can split the associated matching code out into a subroutine. |
| If a pattern contains: |
| |
| (minus:DI (match_operand:DI 1 "register_operand") |
| (match_operand:DI 2 "register_operand")) |
| |
| then we can consider using the same matching routine for both |
| the plus and minus expressions, passing PLUS and SImode in the |
| former case and MINUS and DImode in the latter case. |
| |
| The main aim of this phase is to reduce the compile time of the |
| insn-recog.c code and to reduce the amount of object code in |
| insn-recog.o. |
| |
| 4. Split the matching trees into functions, trying to limit the |
| size of each function to a sensible amount. |
| |
| Again, the main aim of this phase is to reduce the compile time |
| of insn-recog.c. (It doesn't help with the size of insn-recog.o.) |
| |
| 5. Write out C++ code for each function. */ |
| |
| #include "bconfig.h" |
| #define INCLUDE_ALGORITHM |
| #include "system.h" |
| #include "coretypes.h" |
| #include "tm.h" |
| #include "rtl.h" |
| #include "errors.h" |
| #include "read-md.h" |
| #include "gensupport.h" |
| |
| #undef GENERATOR_FILE |
| enum true_rtx_doe { |
| #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS) TRUE_##ENUM, |
| #include "rtl.def" |
| #undef DEF_RTL_EXPR |
| FIRST_GENERATOR_RTX_CODE |
| }; |
| #define NUM_TRUE_RTX_CODE ((int) FIRST_GENERATOR_RTX_CODE) |
| #define GENERATOR_FILE 1 |
| |
| /* Debugging variables to control which optimizations are performed. |
| Note that disabling merge_states_p leads to very large output. */ |
| static const bool merge_states_p = true; |
| static const bool collapse_optional_decisions_p = true; |
| static const bool cse_tests_p = true; |
| static const bool simplify_tests_p = true; |
| static const bool use_operand_variables_p = true; |
| static const bool use_subroutines_p = true; |
| static const bool use_pattern_routines_p = true; |
| |
| /* Whether to add comments for optional tests that we decided to keep. |
| Can be useful when debugging the generator itself but is noise when |
| debugging the generated code. */ |
| static const bool mark_optional_transitions_p = false; |
| |
| /* Whether pattern routines should calculate positions relative to their |
| rtx parameter rather than use absolute positions. This e.g. allows |
| a pattern routine to be shared between a plain SET and a PARALLEL |
| that includes a SET. |
| |
| In principle it sounds like this should be useful, especially for |
| recog_for_combine, where the plain SET form is generated automatically |
| from a PARALLEL of a single SET and some CLOBBERs. In practice it doesn't |
| seem to help much and leads to slightly bigger object files. */ |
| static const bool relative_patterns_p = false; |
| |
| /* Whether pattern routines should be allowed to test whether pnum_clobbers |
| is null. This requires passing pnum_clobbers around as a parameter. */ |
| static const bool pattern_have_num_clobbers_p = true; |
| |
| /* Whether pattern routines should be allowed to test .md file C conditions. |
| This requires passing insn around as a parameter, in case the C |
| condition refers to it. In practice this tends to lead to bigger |
| object files. */ |
| static const bool pattern_c_test_p = false; |
| |
| /* Whether to require each parameter passed to a pattern routine to be |
| unique. Disabling this check for example allows unary operators with |
| matching modes (like NEG) and unary operators with mismatched modes |
| (like ZERO_EXTEND) to be matched by a single pattern. However, we then |
| often have cases where the same value is passed too many times. */ |
| static const bool force_unique_params_p = true; |
| |
| /* The maximum (approximate) depth of block nesting that an individual |
| routine or subroutine should have. This limit is about keeping the |
| output readable rather than reducing compile time. */ |
| static const unsigned int MAX_DEPTH = 6; |
| |
| /* The minimum number of pseudo-statements that a state must have before |
| we split it out into a subroutine. */ |
| static const unsigned int MIN_NUM_STATEMENTS = 5; |
| |
| /* The number of pseudo-statements a state can have before we consider |
| splitting out substates into subroutines. This limit is about avoiding |
| compile-time problems with very big functions (and also about keeping |
| functions within --param optimization limits, etc.). */ |
| static const unsigned int MAX_NUM_STATEMENTS = 200; |
| |
| /* The minimum number of pseudo-statements that can be used in a pattern |
| routine. */ |
| static const unsigned int MIN_COMBINE_COST = 4; |
| |
| /* The maximum number of arguments that a pattern routine can have. |
| The idea is to prevent one pattern getting a ridiculous number of |
| arguments when it would be more beneficial to have a separate pattern |
| routine instead. */ |
| static const unsigned int MAX_PATTERN_PARAMS = 5; |
| |
| /* The maximum operand number plus one. */ |
| int num_operands; |
| |
| /* Ways of obtaining an rtx to be tested. */ |
| enum position_type { |
| /* PATTERN (peep2_next_insn (ARG)). */ |
| POS_PEEP2_INSN, |
| |
| /* XEXP (BASE, ARG). */ |
| POS_XEXP, |
| |
| /* XVECEXP (BASE, 0, ARG). */ |
| POS_XVECEXP0 |
| }; |
| |
| /* The position of an rtx relative to X0. Each useful position is |
| represented by exactly one instance of this structure. */ |
| struct position |
| { |
| /* The parent rtx. This is the root position for POS_PEEP2_INSNs. */ |
| struct position *base; |
| |
| /* A position with the same BASE and TYPE, but with the next value |
| of ARG. */ |
| struct position *next; |
| |
| /* A list of all POS_XEXP positions that use this one as their base, |
| chained by NEXT fields. The first entry represents XEXP (this, 0), |
| the second represents XEXP (this, 1), and so on. */ |
| struct position *xexps; |
| |
| /* A list of POS_XVECEXP0 positions that use this one as their base, |
| chained by NEXT fields. The first entry represents XVECEXP (this, 0, 0), |
| the second represents XVECEXP (this, 0, 1), and so on. */ |
| struct position *xvecexp0s; |
| |
| /* The type of position. */ |
| enum position_type type; |
| |
| /* The argument to TYPE (shown as ARG in the position_type comments). */ |
| int arg; |
| |
| /* The instruction to which the position belongs. */ |
| unsigned int insn_id; |
| |
| /* The depth of this position relative to the instruction pattern. |
| E.g. if the instruction pattern is a SET, the SET itself has a |
| depth of 0 while the SET_DEST and SET_SRC have depths of 1. */ |
| unsigned int depth; |
| |
| /* A unique identifier for this position. */ |
| unsigned int id; |
| }; |
| |
| enum routine_type { |
| SUBPATTERN, RECOG, SPLIT, PEEPHOLE2 |
| }; |
| |
| /* The root position (x0). */ |
| static struct position root_pos; |
| |
| /* The number of positions created. Also one higher than the maximum |
| position id. */ |
| static unsigned int num_positions = 1; |
| |
| /* A list of all POS_PEEP2_INSNs. The entry for insn 0 is the root position, |
| since we are given that instruction's pattern as x0. */ |
| static struct position *peep2_insn_pos_list = &root_pos; |
| |
| /* Return a position with the given BASE, TYPE and ARG. NEXT_PTR |
| points to where the unique object that represents the position |
| should be stored. Create the object if it doesn't already exist, |
| otherwise reuse the object that is already there. */ |
| |
| static struct position * |
| next_position (struct position **next_ptr, struct position *base, |
| enum position_type type, int arg) |
| { |
| struct position *pos; |
| |
| pos = *next_ptr; |
| if (!pos) |
| { |
| pos = XCNEW (struct position); |
| pos->type = type; |
| pos->arg = arg; |
| if (type == POS_PEEP2_INSN) |
| { |
| pos->base = 0; |
| pos->insn_id = arg; |
| pos->depth = base->depth; |
| } |
| else |
| { |
| pos->base = base; |
| pos->insn_id = base->insn_id; |
| pos->depth = base->depth + 1; |
| } |
| pos->id = num_positions++; |
| *next_ptr = pos; |
| } |
| return pos; |
| } |
| |
| /* Compare positions POS1 and POS2 lexicographically. */ |
| |
| static int |
| compare_positions (struct position *pos1, struct position *pos2) |
| { |
| int diff; |
| |
| diff = pos1->depth - pos2->depth; |
| if (diff < 0) |
| do |
| pos2 = pos2->base; |
| while (pos1->depth != pos2->depth); |
| else if (diff > 0) |
| do |
| pos1 = pos1->base; |
| while (pos1->depth != pos2->depth); |
| while (pos1 != pos2) |
| { |
| diff = (int) pos1->type - (int) pos2->type; |
| if (diff == 0) |
| diff = pos1->arg - pos2->arg; |
| pos1 = pos1->base; |
| pos2 = pos2->base; |
| } |
| return diff; |
| } |
| |
| /* Return the most deeply-nested position that is common to both |
| POS1 and POS2. If the positions are from different instructions, |
| return the one with the lowest insn_id. */ |
| |
| static struct position * |
| common_position (struct position *pos1, struct position *pos2) |
| { |
| if (pos1->insn_id != pos2->insn_id) |
| return pos1->insn_id < pos2->insn_id ? pos1 : pos2; |
| if (pos1->depth > pos2->depth) |
| std::swap (pos1, pos2); |
| while (pos1->depth != pos2->depth) |
| pos2 = pos2->base; |
| while (pos1 != pos2) |
| { |
| pos1 = pos1->base; |
| pos2 = pos2->base; |
| } |
| return pos1; |
| } |
| |
| /* Search for and return operand N, stop when reaching node STOP. */ |
| |
| static rtx |
| find_operand (rtx pattern, int n, rtx stop) |
| { |
| const char *fmt; |
| RTX_CODE code; |
| int i, j, len; |
| rtx r; |
| |
| if (pattern == stop) |
| return stop; |
| |
| code = GET_CODE (pattern); |
| if ((code == MATCH_SCRATCH |
| || code == MATCH_OPERAND |
| || code == MATCH_OPERATOR |
| || code == MATCH_PARALLEL) |
| && XINT (pattern, 0) == n) |
| return pattern; |
| |
| fmt = GET_RTX_FORMAT (code); |
| len = GET_RTX_LENGTH (code); |
| for (i = 0; i < len; i++) |
| { |
| switch (fmt[i]) |
| { |
| case 'e': case 'u': |
| if ((r = find_operand (XEXP (pattern, i), n, stop)) != NULL_RTX) |
| return r; |
| break; |
| |
| case 'V': |
| if (! XVEC (pattern, i)) |
| break; |
| /* Fall through. */ |
| |
| case 'E': |
| for (j = 0; j < XVECLEN (pattern, i); j++) |
| if ((r = find_operand (XVECEXP (pattern, i, j), n, stop)) |
| != NULL_RTX) |
| return r; |
| break; |
| |
| case 'i': case 'r': case 'w': case '0': case 's': |
| break; |
| |
| default: |
| gcc_unreachable (); |
| } |
| } |
| |
| return NULL; |
| } |
| |
| /* Search for and return operand M, such that it has a matching |
| constraint for operand N. */ |
| |
| static rtx |
| find_matching_operand (rtx pattern, int n) |
| { |
| const char *fmt; |
| RTX_CODE code; |
| int i, j, len; |
| rtx r; |
| |
| code = GET_CODE (pattern); |
| if (code == MATCH_OPERAND |
| && (XSTR (pattern, 2)[0] == '0' + n |
| || (XSTR (pattern, 2)[0] == '%' |
| && XSTR (pattern, 2)[1] == '0' + n))) |
| return pattern; |
| |
| fmt = GET_RTX_FORMAT (code); |
| len = GET_RTX_LENGTH (code); |
| for (i = 0; i < len; i++) |
| { |
| switch (fmt[i]) |
| { |
| case 'e': case 'u': |
| if ((r = find_matching_operand (XEXP (pattern, i), n))) |
| return r; |
| break; |
| |
| case 'V': |
| if (! XVEC (pattern, i)) |
| break; |
| /* Fall through. */ |
| |
| case 'E': |
| for (j = 0; j < XVECLEN (pattern, i); j++) |
| if ((r = find_matching_operand (XVECEXP (pattern, i, j), n))) |
| return r; |
| break; |
| |
| case 'i': case 'r': case 'w': case '0': case 's': |
| break; |
| |
| default: |
| gcc_unreachable (); |
| } |
| } |
| |
| return NULL; |
| } |
| |
| /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we |
| don't use the MATCH_OPERAND constraint, only the predicate. |
| This is confusing to folks doing new ports, so help them |
| not make the mistake. */ |
| |
| static bool |
| constraints_supported_in_insn_p (rtx insn) |
| { |
| return !(GET_CODE (insn) == DEFINE_EXPAND |
| || GET_CODE (insn) == DEFINE_SPLIT |
| || GET_CODE (insn) == DEFINE_PEEPHOLE2); |
| } |
| |
| /* Return the name of the predicate matched by MATCH_RTX. */ |
| |
| static const char * |
| predicate_name (rtx match_rtx) |
| { |
| if (GET_CODE (match_rtx) == MATCH_SCRATCH) |
| return "scratch_operand"; |
| else |
| return XSTR (match_rtx, 1); |
| } |
| |
| /* Return true if OPERAND is a MATCH_OPERAND using a special predicate |
| function. */ |
| |
| static bool |
| special_predicate_operand_p (rtx operand) |
| { |
| if (GET_CODE (operand) == MATCH_OPERAND) |
| { |
| const char *pred_name = predicate_name (operand); |
| if (pred_name[0] != 0) |
| { |
| const struct pred_data *pred; |
| |
| pred = lookup_predicate (pred_name); |
| return pred != NULL && pred->special; |
| } |
| } |
| |
| return false; |
| } |
| |
| /* Check for various errors in PATTERN, which is part of INFO. |
| SET is nonnull for a destination, and is the complete set pattern. |
| SET_CODE is '=' for normal sets, and '+' within a context that |
| requires in-out constraints. */ |
| |
| static void |
| validate_pattern (rtx pattern, md_rtx_info *info, rtx set, int set_code) |
| { |
| const char *fmt; |
| RTX_CODE code; |
| size_t i, len; |
| int j; |
| |
| code = GET_CODE (pattern); |
| switch (code) |
| { |
| case MATCH_SCRATCH: |
| { |
| const char constraints0 = XSTR (pattern, 1)[0]; |
| |
| if (!constraints_supported_in_insn_p (info->def)) |
| { |
| if (constraints0) |
| { |
| error_at (info->loc, "constraints not supported in %s", |
| GET_RTX_NAME (GET_CODE (info->def))); |
| } |
| return; |
| } |
| |
| /* If a MATCH_SCRATCH is used in a context requiring an write-only |
| or read/write register, validate that. */ |
| if (set_code == '=' |
| && constraints0 |
| && constraints0 != '=' |
| && constraints0 != '+') |
| { |
| error_at (info->loc, "operand %d missing output reload", |
| XINT (pattern, 0)); |
| } |
| return; |
| } |
| case MATCH_DUP: |
| case MATCH_OP_DUP: |
| case MATCH_PAR_DUP: |
| if (find_operand (info->def, XINT (pattern, 0), pattern) == pattern) |
| error_at (info->loc, "operand %i duplicated before defined", |
| XINT (pattern, 0)); |
| break; |
| case MATCH_OPERAND: |
| case MATCH_OPERATOR: |
| { |
| const char *pred_name = XSTR (pattern, 1); |
| const struct pred_data *pred; |
| const char *c_test; |
| |
| c_test = get_c_test (info->def); |
| |
| if (pred_name[0] != 0) |
| { |
| pred = lookup_predicate (pred_name); |
| if (!pred) |
| error_at (info->loc, "unknown predicate '%s'", pred_name); |
| } |
| else |
| pred = 0; |
| |
| if (code == MATCH_OPERAND) |
| { |
| const char *constraints = XSTR (pattern, 2); |
| const char constraints0 = constraints[0]; |
| |
| if (!constraints_supported_in_insn_p (info->def)) |
| { |
| if (constraints0) |
| { |
| error_at (info->loc, "constraints not supported in %s", |
| GET_RTX_NAME (GET_CODE (info->def))); |
| } |
| } |
| |
| /* A MATCH_OPERAND that is a SET should have an output reload. */ |
| else if (set && constraints0) |
| { |
| if (set_code == '+') |
| { |
| if (constraints0 == '+') |
| ; |
| /* If we've only got an output reload for this operand, |
| we'd better have a matching input operand. */ |
| else if (constraints0 == '=' |
| && find_matching_operand (info->def, |
| XINT (pattern, 0))) |
| ; |
| else |
| error_at (info->loc, "operand %d missing in-out reload", |
| XINT (pattern, 0)); |
| } |
| else if (constraints0 != '=' && constraints0 != '+') |
| error_at (info->loc, "operand %d missing output reload", |
| XINT (pattern, 0)); |
| } |
| |
| /* For matching constraint in MATCH_OPERAND, the digit must be a |
| smaller number than the number of the operand that uses it in the |
| constraint. */ |
| while (1) |
| { |
| while (constraints[0] |
| && (constraints[0] == ' ' || constraints[0] == ',')) |
| constraints++; |
| if (!constraints[0]) |
| break; |
| |
| if (constraints[0] >= '0' && constraints[0] <= '9') |
| { |
| int val; |
| |
| sscanf (constraints, "%d", &val); |
| if (val >= XINT (pattern, 0)) |
| error_at (info->loc, "constraint digit %d is not" |
| " smaller than operand %d", |
| val, XINT (pattern, 0)); |
| } |
| |
| while (constraints[0] && constraints[0] != ',') |
| constraints++; |
| } |
| } |
| |
| /* Allowing non-lvalues in destinations -- particularly CONST_INT -- |
| while not likely to occur at runtime, results in less efficient |
| code from insn-recog.c. */ |
| if (set && pred && pred->allows_non_lvalue) |
| error_at (info->loc, "destination operand %d allows non-lvalue", |
| XINT (pattern, 0)); |
| |
| /* A modeless MATCH_OPERAND can be handy when we can check for |
| multiple modes in the c_test. In most other cases, it is a |
| mistake. Only DEFINE_INSN is eligible, since SPLIT and |
| PEEP2 can FAIL within the output pattern. Exclude special |
| predicates, which check the mode themselves. Also exclude |
| predicates that allow only constants. Exclude the SET_DEST |
| of a call instruction, as that is a common idiom. */ |
| |
| if (GET_MODE (pattern) == VOIDmode |
| && code == MATCH_OPERAND |
| && GET_CODE (info->def) == DEFINE_INSN |
| && pred |
| && !pred->special |
| && pred->allows_non_const |
| && strstr (c_test, "operands") == NULL |
| && ! (set |
| && GET_CODE (set) == SET |
| && GET_CODE (SET_SRC (set)) == CALL)) |
| message_at (info->loc, "warning: operand %d missing mode?", |
| XINT (pattern, 0)); |
| return; |
| } |
| |
| case SET: |
| { |
| machine_mode dmode, smode; |
| rtx dest, src; |
| |
| dest = SET_DEST (pattern); |
| src = SET_SRC (pattern); |
| |
| /* STRICT_LOW_PART is a wrapper. Its argument is the real |
| destination, and it's mode should match the source. */ |
| if (GET_CODE (dest) == STRICT_LOW_PART) |
| dest = XEXP (dest, 0); |
| |
| /* Find the referent for a DUP. */ |
| |
| if (GET_CODE (dest) == MATCH_DUP |
| || GET_CODE (dest) == MATCH_OP_DUP |
| || GET_CODE (dest) == MATCH_PAR_DUP) |
| dest = find_operand (info->def, XINT (dest, 0), NULL); |
| |
| if (GET_CODE (src) == MATCH_DUP |
| || GET_CODE (src) == MATCH_OP_DUP |
| || GET_CODE (src) == MATCH_PAR_DUP) |
| src = find_operand (info->def, XINT (src, 0), NULL); |
| |
| dmode = GET_MODE (dest); |
| smode = GET_MODE (src); |
| |
| /* Mode checking is not performed for special predicates. */ |
| if (special_predicate_operand_p (src) |
| || special_predicate_operand_p (dest)) |
| ; |
| |
| /* The operands of a SET must have the same mode unless one |
| is VOIDmode. */ |
| else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode) |
| error_at (info->loc, "mode mismatch in set: %smode vs %smode", |
| GET_MODE_NAME (dmode), GET_MODE_NAME (smode)); |
| |
| /* If only one of the operands is VOIDmode, and PC or CC0 is |
| not involved, it's probably a mistake. */ |
| else if (dmode != smode |
| && GET_CODE (dest) != PC |
| && GET_CODE (dest) != CC0 |
| && GET_CODE (src) != PC |
| && GET_CODE (src) != CC0 |
| && !CONST_INT_P (src) |
| && !CONST_WIDE_INT_P (src) |
| && GET_CODE (src) != CALL) |
| { |
| const char *which; |
| which = (dmode == VOIDmode ? "destination" : "source"); |
| message_at (info->loc, "warning: %s missing a mode?", which); |
| } |
| |
| if (dest != SET_DEST (pattern)) |
| validate_pattern (dest, info, pattern, '='); |
| validate_pattern (SET_DEST (pattern), info, pattern, '='); |
| validate_pattern (SET_SRC (pattern), info, NULL_RTX, 0); |
| return; |
| } |
| |
| case CLOBBER: |
| validate_pattern (SET_DEST (pattern), info, pattern, '='); |
| return; |
| |
| case ZERO_EXTRACT: |
| validate_pattern (XEXP (pattern, 0), info, set, set ? '+' : 0); |
| validate_pattern (XEXP (pattern, 1), info, NULL_RTX, 0); |
| validate_pattern (XEXP (pattern, 2), info, NULL_RTX, 0); |
| return; |
| |
| case STRICT_LOW_PART: |
| validate_pattern (XEXP (pattern, 0), info, set, set ? '+' : 0); |
| return; |
| |
| case LABEL_REF: |
| if (GET_MODE (XEXP (pattern, 0)) != VOIDmode) |
| error_at (info->loc, "operand to label_ref %smode not VOIDmode", |
| GET_MODE_NAME (GET_MODE (XEXP (pattern, 0)))); |
| break; |
| |
| case VEC_SELECT: |
| if (GET_MODE (pattern) != VOIDmode) |
| { |
| machine_mode mode = GET_MODE (pattern); |
| machine_mode imode = GET_MODE (XEXP (pattern, 0)); |
| machine_mode emode |
| = VECTOR_MODE_P (mode) ? GET_MODE_INNER (mode) : mode; |
| if (GET_CODE (XEXP (pattern, 1)) == PARALLEL) |
| { |
| int expected = VECTOR_MODE_P (mode) ? GET_MODE_NUNITS (mode) : 1; |
| if (XVECLEN (XEXP (pattern, 1), 0) != expected) |
| error_at (info->loc, |
| "vec_select parallel with %d elements, expected %d", |
| XVECLEN (XEXP (pattern, 1), 0), expected); |
| else if (VECTOR_MODE_P (imode)) |
| { |
| unsigned int nelems = GET_MODE_NUNITS (imode); |
| int i; |
| for (i = 0; i < expected; ++i) |
| if (CONST_INT_P (XVECEXP (XEXP (pattern, 1), 0, i)) |
| && (UINTVAL (XVECEXP (XEXP (pattern, 1), 0, i)) |
| >= nelems)) |
| error_at (info->loc, |
| "out of bounds selector %u in vec_select, " |
| "expected at most %u", |
| (unsigned) |
| UINTVAL (XVECEXP (XEXP (pattern, 1), 0, i)), |
| nelems - 1); |
| } |
| } |
| if (imode != VOIDmode && !VECTOR_MODE_P (imode)) |
| error_at (info->loc, "%smode of first vec_select operand is not a " |
| "vector mode", GET_MODE_NAME (imode)); |
| else if (imode != VOIDmode && GET_MODE_INNER (imode) != emode) |
| error_at (info->loc, "element mode mismatch between vec_select " |
| "%smode and its operand %smode", |
| GET_MODE_NAME (emode), |
| GET_MODE_NAME (GET_MODE_INNER (imode))); |
| } |
| break; |
| |
| default: |
| break; |
| } |
| |
| fmt = GET_RTX_FORMAT (code); |
| len = GET_RTX_LENGTH (code); |
| for (i = 0; i < len; i++) |
| { |
| switch (fmt[i]) |
| { |
| case 'e': case 'u': |
| validate_pattern (XEXP (pattern, i), info, NULL_RTX, 0); |
| break; |
| |
| case 'E': |
| for (j = 0; j < XVECLEN (pattern, i); j++) |
| validate_pattern (XVECEXP (pattern, i, j), info, NULL_RTX, 0); |
| break; |
| |
| case 'i': case 'r': case 'w': case '0': case 's': |
| break; |
| |
| default: |
| gcc_unreachable (); |
| } |
| } |
| } |
| |
| /* Simple list structure for items of type T, for use when being part |
| of a list is an inherent property of T. T must have members equivalent |
| to "T *prev, *next;" and a function "void set_parent (list_head <T> *)" |
| to set the parent list. */ |
| template <typename T> |
| struct list_head |
| { |
| /* A range of linked items. */ |
| struct range |
| { |
| range (T *); |
| range (T *, T *); |
| |
| T *start, *end; |
| void set_parent (list_head *); |
| }; |
| |
| list_head (); |
| range release (); |
| void push_back (range); |
| range remove (range); |
| void replace (range, range); |
| T *singleton () const; |
| |
| T *first, *last; |
| }; |
| |
| /* Create a range [START_IN, START_IN]. */ |
| |
| template <typename T> |
| list_head <T>::range::range (T *start_in) : start (start_in), end (start_in) {} |
| |
| /* Create a range [START_IN, END_IN], linked by next and prev fields. */ |
| |
| template <typename T> |
| list_head <T>::range::range (T *start_in, T *end_in) |
| : start (start_in), end (end_in) {} |
| |
| template <typename T> |
| void |
| list_head <T>::range::set_parent (list_head <T> *owner) |
| { |
| for (T *item = start; item != end; item = item->next) |
| item->set_parent (owner); |
| end->set_parent (owner); |
| } |
| |
| template <typename T> |
| list_head <T>::list_head () : first (0), last (0) {} |
| |
| /* Add R to the end of the list. */ |
| |
| template <typename T> |
| void |
| list_head <T>::push_back (range r) |
| { |
| if (last) |
| last->next = r.start; |
| else |
| first = r.start; |
| r.start->prev = last; |
| last = r.end; |
| r.set_parent (this); |
| } |
| |
| /* Remove R from the list. R remains valid and can be inserted into |
| other lists. */ |
| |
| template <typename T> |
| typename list_head <T>::range |
| list_head <T>::remove (range r) |
| { |
| if (r.start->prev) |
| r.start->prev->next = r.end->next; |
| else |
| first = r.end->next; |
| if (r.end->next) |
| r.end->next->prev = r.start->prev; |
| else |
| last = r.start->prev; |
| r.start->prev = 0; |
| r.end->next = 0; |
| r.set_parent (0); |
| return r; |
| } |
| |
| /* Replace OLDR with NEWR. OLDR remains valid and can be inserted into |
| other lists. */ |
| |
| template <typename T> |
| void |
| list_head <T>::replace (range oldr, range newr) |
| { |
| newr.start->prev = oldr.start->prev; |
| newr.end->next = oldr.end->next; |
| |
| oldr.start->prev = 0; |
| oldr.end->next = 0; |
| oldr.set_parent (0); |
| |
| if (newr.start->prev) |
| newr.start->prev->next = newr.start; |
| else |
| first = newr.start; |
| if (newr.end->next) |
| newr.end->next->prev = newr.end; |
| else |
| last = newr.end; |
| newr.set_parent (this); |
| } |
| |
| /* Empty the list and return the previous contents as a range that can |
| be inserted into other lists. */ |
| |
| template <typename T> |
| typename list_head <T>::range |
| list_head <T>::release () |
| { |
| range r (first, last); |
| first = 0; |
| last = 0; |
| r.set_parent (0); |
| return r; |
| } |
| |
| /* If the list contains a single item, return that item, otherwise return |
| null. */ |
| |
| template <typename T> |
| T * |
| list_head <T>::singleton () const |
| { |
| return first == last ? first : 0; |
| } |
| |
| struct state; |
| |
| /* Describes a possible successful return from a routine. */ |
| struct acceptance_type |
| { |
| /* The type of routine we're returning from. */ |
| routine_type type : 16; |
| |
| /* True if this structure only really represents a partial match, |
| and if we must call a subroutine of type TYPE to complete the match. |
| In this case we'll call the subroutine and, if it succeeds, return |
| whatever the subroutine returned. |
| |
| False if this structure presents a full match. */ |
| unsigned int partial_p : 1; |
| |
| union |
| { |
| /* If PARTIAL_P, this is the number of the subroutine to call. */ |
| int subroutine_id; |
| |
| /* Valid if !PARTIAL_P. */ |
| struct |
| { |
| /* The identifier of the matching pattern. For SUBPATTERNs this |
| value belongs to an ad-hoc routine-specific enum. For the |
| others it's the number of an .md file pattern. */ |
| int code; |
| union |
| { |
| /* For RECOG, the number of clobbers that must be added to the |
| pattern in order for it to match CODE. */ |
| int num_clobbers; |
| |
| /* For PEEPHOLE2, the number of additional instructions that were |
| included in the optimization. */ |
| int match_len; |
| } u; |
| } full; |
| } u; |
| }; |
| |
| bool |
| operator == (const acceptance_type &a, const acceptance_type &b) |
| { |
| if (a.partial_p != b.partial_p) |
| return false; |
| if (a.partial_p) |
| return a.u.subroutine_id == b.u.subroutine_id; |
| else |
| return a.u.full.code == b.u.full.code; |
| } |
| |
| bool |
| operator != (const acceptance_type &a, const acceptance_type &b) |
| { |
| return !operator == (a, b); |
| } |
| |
| /* Represents a parameter to a pattern routine. */ |
| struct parameter |
| { |
| /* The C type of parameter. */ |
| enum type_enum { |
| /* Represents an invalid parameter. */ |
| UNSET, |
| |
| /* A machine_mode parameter. */ |
| MODE, |
| |
| /* An rtx_code parameter. */ |
| CODE, |
| |
| /* An int parameter. */ |
| INT, |
| |
| /* An unsigned int parameter. */ |
| UINT, |
| |
| /* A HOST_WIDE_INT parameter. */ |
| WIDE_INT |
| }; |
| |
| parameter (); |
| parameter (type_enum, bool, uint64_t); |
| |
| /* The type of the parameter. */ |
| type_enum type; |
| |
| /* True if the value passed is variable, false if it is constant. */ |
| bool is_param; |
| |
| /* If IS_PARAM, this is the number of the variable passed, for an "i%d" |
| format string. If !IS_PARAM, this is the constant value passed. */ |
| uint64_t value; |
| }; |
| |
| parameter::parameter () |
| : type (UNSET), is_param (false), value (0) {} |
| |
| parameter::parameter (type_enum type_in, bool is_param_in, uint64_t value_in) |
| : type (type_in), is_param (is_param_in), value (value_in) {} |
| |
| bool |
| operator == (const parameter ¶m1, const parameter ¶m2) |
| { |
| return (param1.type == param2.type |
| && param1.is_param == param2.is_param |
| && param1.value == param2.value); |
| } |
| |
| bool |
| operator != (const parameter ¶m1, const parameter ¶m2) |
| { |
| return !operator == (param1, param2); |
| } |
| |
| /* Represents a routine that matches a partial rtx pattern, returning |
| an ad-hoc enum value on success and -1 on failure. The routine can |
| be used by any subroutine type. The match can be parameterized by |
| things like mode, code and UNSPEC number. */ |
| struct pattern_routine |
| { |
| /* The state that implements the pattern. */ |
| state *s; |
| |
| /* The deepest root position from which S can access all the rtxes it needs. |
| This is NULL if the pattern doesn't need an rtx input, usually because |
| all matching is done on operands[] instead. */ |
| position *pos; |
| |
| /* A unique identifier for the routine. */ |
| unsigned int pattern_id; |
| |
| /* True if the routine takes pnum_clobbers as argument. */ |
| bool pnum_clobbers_p; |
| |
| /* True if the routine takes the enclosing instruction as argument. */ |
| bool insn_p; |
| |
| /* The types of the other parameters to the routine, if any. */ |
| auto_vec <parameter::type_enum, MAX_PATTERN_PARAMS> param_types; |
| }; |
| |
| /* All defined patterns. */ |
| static vec <pattern_routine *> patterns; |
| |
| /* Represents one use of a pattern routine. */ |
| struct pattern_use |
| { |
| /* The pattern routine to use. */ |
| pattern_routine *routine; |
| |
| /* The values to pass as parameters. This vector has the same length |
| as ROUTINE->PARAM_TYPES. */ |
| auto_vec <parameter, MAX_PATTERN_PARAMS> params; |
| }; |
| |
| /* Represents a test performed by a decision. */ |
| struct rtx_test |
| { |
| rtx_test (); |
| |
| /* The types of test that can be performed. Most of them take as input |
| an rtx X. Some also take as input a transition label LABEL; the others |
| are booleans for which the transition label is always "true". |
| |
| The order of the enum isn't important. */ |
| enum kind_enum { |
| /* Check GET_CODE (X) == LABEL. */ |
| CODE, |
| |
| /* Check GET_MODE (X) == LABEL. */ |
| MODE, |
| |
| /* Check REGNO (X) == LABEL. */ |
| REGNO_FIELD, |
| |
| /* Check XINT (X, u.opno) == LABEL. */ |
| INT_FIELD, |
| |
| /* Check XWINT (X, u.opno) == LABEL. */ |
| WIDE_INT_FIELD, |
| |
| /* Check XVECLEN (X, 0) == LABEL. */ |
| VECLEN, |
| |
| /* Check peep2_current_count >= u.min_len. */ |
| PEEP2_COUNT, |
| |
| /* Check XVECLEN (X, 0) >= u.min_len. */ |
| VECLEN_GE, |
| |
| /* Check whether X is a cached const_int with value u.integer. */ |
| SAVED_CONST_INT, |
| |
| /* Check u.predicate.data (X, u.predicate.mode). */ |
| PREDICATE, |
| |
| /* Check rtx_equal_p (X, operands[u.opno]). */ |
| DUPLICATE, |
| |
| /* Check whether X matches pattern u.pattern. */ |
| PATTERN, |
| |
| /* Check whether pnum_clobbers is nonnull (RECOG only). */ |
| HAVE_NUM_CLOBBERS, |
| |
| /* Check whether general C test u.string holds. In general the condition |
| needs access to "insn" and the full operand list. */ |
| C_TEST, |
| |
| /* Execute operands[u.opno] = X. (Always succeeds.) */ |
| SET_OP, |
| |
| /* Accept u.acceptance. Always succeeds for SUBPATTERN, RECOG and SPLIT. |
| May fail for PEEPHOLE2 if the define_peephole2 C code executes FAIL. */ |
| ACCEPT |
| }; |
| |
| /* The position of rtx X in the above description, relative to the |
| incoming instruction "insn". The position is null if the test |
| doesn't take an X as input. */ |
| position *pos; |
| |
| /* Which element of operands[] already contains POS, or -1 if no element |
| is known to hold POS. */ |
| int pos_operand; |
| |
| /* The type of test and its parameters, as described above. */ |
| kind_enum kind; |
| union |
| { |
| int opno; |
| int min_len; |
| struct |
| { |
| bool is_param; |
| int value; |
| } integer; |
| struct |
| { |
| const struct pred_data *data; |
| /* True if the mode is taken from a machine_mode parameter |
| to the routine rather than a constant machine_mode. If true, |
| MODE is the number of the parameter (for an "i%d" format string), |
| otherwise it is the mode itself. */ |
| bool mode_is_param; |
| unsigned int mode; |
| } predicate; |
| pattern_use *pattern; |
| const char *string; |
| acceptance_type acceptance; |
| } u; |
| |
| static rtx_test code (position *); |
| static rtx_test mode (position *); |
| static rtx_test regno_field (position *); |
| static rtx_test int_field (position *, int); |
| static rtx_test wide_int_field (position *, int); |
| static rtx_test veclen (position *); |
| static rtx_test peep2_count (int); |
| static rtx_test veclen_ge (position *, int); |
| static rtx_test predicate (position *, const pred_data *, machine_mode); |
| static rtx_test duplicate (position *, int); |
| static rtx_test pattern (position *, pattern_use *); |
| static rtx_test have_num_clobbers (); |
| static rtx_test c_test (const char *); |
| static rtx_test set_op (position *, int); |
| static rtx_test accept (const acceptance_type &); |
| |
| bool terminal_p () const; |
| bool single_outcome_p () const; |
| |
| private: |
| rtx_test (position *, kind_enum); |
| }; |
| |
| rtx_test::rtx_test () {} |
| |
| rtx_test::rtx_test (position *pos_in, kind_enum kind_in) |
| : pos (pos_in), pos_operand (-1), kind (kind_in) {} |
| |
| rtx_test |
| rtx_test::code (position *pos) |
| { |
| return rtx_test (pos, rtx_test::CODE); |
| } |
| |
| rtx_test |
| rtx_test::mode (position *pos) |
| { |
| return rtx_test (pos, rtx_test::MODE); |
| } |
| |
| rtx_test |
| rtx_test::regno_field (position *pos) |
| { |
| rtx_test res (pos, rtx_test::REGNO_FIELD); |
| return res; |
| } |
| |
| rtx_test |
| rtx_test::int_field (position *pos, int opno) |
| { |
| rtx_test res (pos, rtx_test::INT_FIELD); |
| res.u.opno = opno; |
| return res; |
| } |
| |
| rtx_test |
| rtx_test::wide_int_field (position *pos, int opno) |
| { |
| rtx_test res (pos, rtx_test::WIDE_INT_FIELD); |
| res.u.opno = opno; |
| return res; |
| } |
| |
| rtx_test |
| rtx_test::veclen (position *pos) |
| { |
| return rtx_test (pos, rtx_test::VECLEN); |
| } |
| |
| rtx_test |
| rtx_test::peep2_count (int min_len) |
| { |
| rtx_test res (0, rtx_test::PEEP2_COUNT); |
| res.u.min_len = min_len; |
| return res; |
| } |
| |
| rtx_test |
| rtx_test::veclen_ge (position *pos, int min_len) |
| { |
| rtx_test res (pos, rtx_test::VECLEN_GE); |
| res.u.min_len = min_len; |
| return res; |
| } |
| |
| rtx_test |
| rtx_test::predicate (position *pos, const struct pred_data *data, |
| machine_mode mode) |
| { |
| rtx_test res (pos, rtx_test::PREDICATE); |
| res.u.predicate.data = data; |
| res.u.predicate.mode_is_param = false; |
| res.u.predicate.mode = mode; |
| return res; |
| } |
| |
| rtx_test |
| rtx_test::duplicate (position *pos, int opno) |
| { |
| rtx_test res (pos, rtx_test::DUPLICATE); |
| res.u.opno = opno; |
| return res; |
| } |
| |
| rtx_test |
| rtx_test::pattern (position *pos, pattern_use *pattern) |
| { |
| rtx_test res (pos, rtx_test::PATTERN); |
| res.u.pattern = pattern; |
| return res; |
| } |
| |
| rtx_test |
| rtx_test::have_num_clobbers () |
| { |
| return rtx_test (0, rtx_test::HAVE_NUM_CLOBBERS); |
| } |
| |
| rtx_test |
| rtx_test::c_test (const char *string) |
| { |
| rtx_test res (0, rtx_test::C_TEST); |
| res.u.string = string; |
| return res; |
| } |
| |
| rtx_test |
| rtx_test::set_op (position *pos, int opno) |
| { |
| rtx_test res (pos, rtx_test::SET_OP); |
| res.u.opno = opno; |
| return res; |
| } |
| |
| rtx_test |
| rtx_test::accept (const acceptance_type &acceptance) |
| { |
| rtx_test res (0, rtx_test::ACCEPT); |
| res.u.acceptance = acceptance; |
| return res; |
| } |
| |
| /* Return true if the test represents an unconditionally successful match. */ |
| |
| bool |
| rtx_test::terminal_p () const |
| { |
| return kind == rtx_test::ACCEPT && u.acceptance.type != PEEPHOLE2; |
| } |
| |
| /* Return true if the test is a boolean that is always true. */ |
| |
| bool |
| rtx_test::single_outcome_p () const |
| { |
| return terminal_p () || kind == rtx_test::SET_OP; |
| } |
| |
| bool |
| operator == (const rtx_test &a, const rtx_test &b) |
| { |
| if (a.pos != b.pos || a.kind != b.kind) |
| return false; |
| switch (a.kind) |
| { |
| case rtx_test::CODE: |
| case rtx_test::MODE: |
| case rtx_test::REGNO_FIELD: |
| case rtx_test::VECLEN: |
| case rtx_test::HAVE_NUM_CLOBBERS: |
| return true; |
| |
| case rtx_test::PEEP2_COUNT: |
| case rtx_test::VECLEN_GE: |
| return a.u.min_len == b.u.min_len; |
| |
| case rtx_test::INT_FIELD: |
| case rtx_test::WIDE_INT_FIELD: |
| case rtx_test::DUPLICATE: |
| case rtx_test::SET_OP: |
| return a.u.opno == b.u.opno; |
| |
| case rtx_test::SAVED_CONST_INT: |
| return (a.u.integer.is_param == b.u.integer.is_param |
| && a.u.integer.value == b.u.integer.value); |
| |
| case rtx_test::PREDICATE: |
| return (a.u.predicate.data == b.u.predicate.data |
| && a.u.predicate.mode_is_param == b.u.predicate.mode_is_param |
| && a.u.predicate.mode == b.u.predicate.mode); |
| |
| case rtx_test::PATTERN: |
| return (a.u.pattern->routine == b.u.pattern->routine |
| && a.u.pattern->params == b.u.pattern->params); |
| |
| case rtx_test::C_TEST: |
| return strcmp (a.u.string, b.u.string) == 0; |
| |
| case rtx_test::ACCEPT: |
| return a.u.acceptance == b.u.acceptance; |
| } |
| gcc_unreachable (); |
| } |
| |
| bool |
| operator != (const rtx_test &a, const rtx_test &b) |
| { |
| return !operator == (a, b); |
| } |
| |
| /* A simple set of transition labels. Most transitions have a singleton |
| label, so try to make that case as efficient as possible. */ |
| struct int_set : public auto_vec <uint64_t, 1> |
| { |
| typedef uint64_t *iterator; |
| |
| int_set (); |
| int_set (uint64_t); |
| int_set (const int_set &); |
| |
| int_set &operator = (const int_set &); |
| |
| iterator begin (); |
| iterator end (); |
| }; |
| |
| int_set::int_set () : auto_vec<uint64_t, 1> () {} |
| |
| int_set::int_set (uint64_t label) : |
| auto_vec<uint64_t, 1> () |
| { |
| safe_push (label); |
| } |
| |
| int_set::int_set (const int_set &other) : |
| auto_vec<uint64_t, 1> () |
| { |
| safe_splice (other); |
| } |
| |
| int_set & |
| int_set::operator = (const int_set &other) |
| { |
| truncate (0); |
| safe_splice (other); |
| return *this; |
| } |
| |
| int_set::iterator |
| int_set::begin () |
| { |
| return address (); |
| } |
| |
| int_set::iterator |
| int_set::end () |
| { |
| return address () + length (); |
| } |
| |
| bool |
| operator == (const int_set &a, const int_set &b) |
| { |
| if (a.length () != b.length ()) |
| return false; |
| for (unsigned int i = 0; i < a.length (); ++i) |
| if (a[i] != b[i]) |
| return false; |
| return true; |
| } |
| |
| bool |
| operator != (const int_set &a, const int_set &b) |
| { |
| return !operator == (a, b); |
| } |
| |
| struct decision; |
| |
| /* Represents a transition between states, dependent on the result of |
| a test T. */ |
| struct transition |
| { |
| transition (const int_set &, state *, bool); |
| |
| void set_parent (list_head <transition> *); |
| |
| /* Links to other transitions for T. Always null for boolean tests. */ |
| transition *prev, *next; |
| |
| /* The transition should be taken when T has one of these values. |
| E.g. for rtx_test::CODE this is a set of codes, while for booleans like |
| rtx_test::PREDICATE it is always a singleton "true". The labels are |
| sorted in ascending order. */ |
| int_set labels; |
| |
| /* The source decision. */ |
| decision *from; |
| |
| /* The target state. */ |
| state *to; |
| |
| /* True if TO would function correctly even if TEST wasn't performed. |
| E.g. it isn't necessary to check whether GET_MODE (x1) is SImode |
| before calling register_operand (x1, SImode), since register_operand |
| performs its own mode check. However, checking GET_MODE can be a cheap |
| way of disambiguating SImode and DImode register operands. */ |
| bool optional; |
| |
| /* True if LABELS contains parameter numbers rather than constants. |
| E.g. if this is true for a rtx_test::CODE, the label is the number |
| of an rtx_code parameter rather than an rtx_code itself. |
| LABELS is always a singleton when this variable is true. */ |
| bool is_param; |
| }; |
| |
| /* Represents a test and the action that should be taken on the result. |
| If a transition exists for the test outcome, the machine switches |
| to the transition's target state. If no suitable transition exists, |
| the machine either falls through to the next decision or, if there are no |
| more decisions to try, fails the match. */ |
| struct decision : list_head <transition> |
| { |
| decision (const rtx_test &); |
| |
| void set_parent (list_head <decision> *s); |
| bool if_statement_p (uint64_t * = 0) const; |
| |
| /* The state to which this decision belongs. */ |
| state *s; |
| |
| /* Links to other decisions in the same state. */ |
| decision *prev, *next; |
| |
| /* The test to perform. */ |
| rtx_test test; |
| }; |
| |
| /* Represents one machine state. For each state the machine tries a list |
| of decisions, in order, and acts on the first match. It fails without |
| further backtracking if no decisions match. */ |
| struct state : list_head <decision> |
| { |
| void set_parent (list_head <state> *) {} |
| }; |
| |
| transition::transition (const int_set &labels_in, state *to_in, |
| bool optional_in) |
| : prev (0), next (0), labels (labels_in), from (0), to (to_in), |
| optional (optional_in), is_param (false) {} |
| |
| /* Set the source decision of the transition. */ |
| |
| void |
| transition::set_parent (list_head <transition> *from_in) |
| { |
| from = static_cast <decision *> (from_in); |
| } |
| |
| decision::decision (const rtx_test &test_in) |
| : prev (0), next (0), test (test_in) {} |
| |
| /* Set the state to which this decision belongs. */ |
| |
| void |
| decision::set_parent (list_head <decision> *s_in) |
| { |
| s = static_cast <state *> (s_in); |
| } |
| |
| /* Return true if the decision has a single transition with a single label. |
| If so, return the label in *LABEL if nonnull. */ |
| |
| inline bool |
| decision::if_statement_p (uint64_t *label) const |
| { |
| if (singleton () && first->labels.length () == 1) |
| { |
| if (label) |
| *label = first->labels[0]; |
| return true; |
| } |
| return false; |
| } |
| |
| /* Add to FROM a decision that performs TEST and has a single transition |
| TRANS. */ |
| |
| static void |
| add_decision (state *from, const rtx_test &test, transition *trans) |
| { |
| decision *d = new decision (test); |
| from->push_back (d); |
| d->push_back (trans); |
| } |
| |
| /* Add a transition from FROM to a new, empty state that is taken |
| when TEST == LABELS. OPTIONAL says whether the new transition |
| should be optional. Return the new state. */ |
| |
| static state * |
| add_decision (state *from, const rtx_test &test, int_set labels, bool optional) |
| { |
| state *to = new state; |
| add_decision (from, test, new transition (labels, to, optional)); |
| return to; |
| } |
| |
| /* Insert a decision before decisions R to make them dependent on |
| TEST == LABELS. OPTIONAL says whether the new transition should be |
| optional. */ |
| |
| static decision * |
| insert_decision_before (state::range r, const rtx_test &test, |
| const int_set &labels, bool optional) |
| { |
| decision *newd = new decision (test); |
| state *news = new state; |
| newd->push_back (new transition (labels, news, optional)); |
| r.start->s->replace (r, newd); |
| news->push_back (r); |
| return newd; |
| } |
| |
| /* Remove any optional transitions from S that turned out not to be useful. */ |
| |
| static void |
| collapse_optional_decisions (state *s) |
| { |
| decision *d = s->first; |
| while (d) |
| { |
| decision *next = d->next; |
| for (transition *trans = d->first; trans; trans = trans->next) |
| collapse_optional_decisions (trans->to); |
| /* A decision with a single optional transition doesn't help |
| partition the potential matches and so is unlikely to be |
| worthwhile. In particular, if the decision that performs the |
| test is the last in the state, the best it could do is reject |
| an invalid pattern slightly earlier. If instead the decision |
| is not the last in the state, the condition it tests could hold |
| even for the later decisions in the state. The best it can do |
| is save work in some cases where only the later decisions can |
| succeed. |
| |
| In both cases the optional transition would add extra work to |
| successful matches when the tested condition holds. */ |
| if (transition *trans = d->singleton ()) |
| if (trans->optional) |
| s->replace (d, trans->to->release ()); |
| d = next; |
| } |
| } |
| |
| /* Try to squash several separate tests into simpler ones. */ |
| |
| static void |
| simplify_tests (state *s) |
| { |
| for (decision *d = s->first; d; d = d->next) |
| { |
| uint64_t label; |
| /* Convert checks for GET_CODE (x) == CONST_INT and XWINT (x, 0) == N |
| into checks for const_int_rtx[N'], if N is suitably small. */ |
| if (d->test.kind == rtx_test::CODE |
| && d->if_statement_p (&label) |
| && label == CONST_INT) |
| if (decision *second = d->first->to->singleton ()) |
| if (d->test.pos == second->test.pos |
| && second->test.kind == rtx_test::WIDE_INT_FIELD |
| && second->test.u.opno == 0 |
| && second->if_statement_p (&label) |
| && IN_RANGE (int64_t (label), |
| -MAX_SAVED_CONST_INT, MAX_SAVED_CONST_INT)) |
| { |
| d->test.kind = rtx_test::SAVED_CONST_INT; |
| d->test.u.integer.is_param = false; |
| d->test.u.integer.value = label; |
| d->replace (d->first, second->release ()); |
| d->first->labels[0] = true; |
| } |
| /* If we have a CODE test followed by a PREDICATE test, rely on |
| the predicate to test the code. |
| |
| This case exists for match_operators. We initially treat the |
| CODE test for a match_operator as non-optional so that we can |
| safely move down to its operands. It may turn out that all |
| paths that reach that code test require the same predicate |
| to be true. cse_tests will then put the predicate test in |
| series with the code test. */ |
| if (d->test.kind == rtx_test::CODE) |
| if (transition *trans = d->singleton ()) |
| { |
| state *s = trans->to; |
| while (decision *d2 = s->singleton ()) |
| { |
| if (d->test.pos != d2->test.pos) |
| break; |
| transition *trans2 = d2->singleton (); |
| if (!trans2) |
| break; |
| if (d2->test.kind == rtx_test::PREDICATE) |
| { |
| d->test = d2->test; |
| trans->labels = int_set (true); |
| s->replace (d2, trans2->to->release ()); |
| break; |
| } |
| s = trans2->to; |
| } |
| } |
| for (transition *trans = d->first; trans; trans = trans->next) |
| simplify_tests (trans->to); |
| } |
| } |
| |
| /* Return true if all successful returns passing through D require the |
| condition tested by COMMON to be true. |
| |
| When returning true, add all transitions like COMMON in D to WHERE. |
| WHERE may contain a partial result on failure. */ |
| |
| static bool |
| common_test_p (decision *d, transition *common, vec <transition *> *where) |
| { |
| if (d->test.kind == rtx_test::ACCEPT) |
| /* We found a successful return that didn't require COMMON. */ |
| return false; |
| if (d->test == common->from->test) |
| { |
| transition *trans = d->singleton (); |
| if (!trans |
| || trans->optional != common->optional |
| || trans->labels != common->labels) |
| return false; |
| where->safe_push (trans); |
| return true; |
| } |
| for (transition *trans = d->first; trans; trans = trans->next) |
| for (decision *subd = trans->to->first; subd; subd = subd->next) |
| if (!common_test_p (subd, common, where)) |
| return false; |
| return true; |
| } |
| |
| /* Indicates that we have tested GET_CODE (X) for a particular rtx X. */ |
| const unsigned char TESTED_CODE = 1; |
| |
| /* Indicates that we have tested XVECLEN (X, 0) for a particular rtx X. */ |
| const unsigned char TESTED_VECLEN = 2; |
| |
| /* Represents a set of conditions that are known to hold. */ |
| struct known_conditions |
| { |
| /* A mask of TESTED_ values for each position, indexed by the position's |
| id field. */ |
| auto_vec <unsigned char> position_tests; |
| |
| /* Index N says whether operands[N] has been set. */ |
| auto_vec <bool> set_operands; |
| |
| /* A guranteed lower bound on the value of peep2_current_count. */ |
| int peep2_count; |
| }; |
| |
| /* Return true if TEST can safely be performed at D, where |
| the conditions in KC hold. TEST is known to occur along the |
| first path from D (i.e. always following the first transition |
| of the first decision). Any intervening tests can be used as |
| negative proof that hoisting isn't safe, but only KC can be used |
| as positive proof. */ |
| |
| static bool |
| safe_to_hoist_p (decision *d, const rtx_test &test, known_conditions *kc) |
| { |
| switch (test.kind) |
| { |
| case rtx_test::C_TEST: |
| /* In general, C tests require everything else to have been |
| verified and all operands to have been set up. */ |
| return false; |
| |
| case rtx_test::ACCEPT: |
| /* Don't accept something before all conditions have been tested. */ |
| return false; |
| |
| case rtx_test::PREDICATE: |
| /* Don't move a predicate over a test for VECLEN_GE, since the |
| predicate used in a match_parallel can legitimately expect the |
| length to be checked first. */ |
| for (decision *subd = d; |
| subd->test != test; |
| subd = subd->first->to->first) |
| if (subd->test.pos == test.pos |
| && subd->test.kind == rtx_test::VECLEN_GE) |
| return false; |
| goto any_rtx; |
| |
| case rtx_test::DUPLICATE: |
| /* Don't test for a match_dup until the associated operand has |
| been set. */ |
| if (!kc->set_operands[test.u.opno]) |
| return false; |
| goto any_rtx; |
| |
| case rtx_test::CODE: |
| case rtx_test::MODE: |
| case rtx_test::SAVED_CONST_INT: |
| case rtx_test::SET_OP: |
| any_rtx: |
| /* Check whether it is safe to access the rtx under test. */ |
| switch (test.pos->type) |
| { |
| case POS_PEEP2_INSN: |
| return test.pos->arg < kc->peep2_count; |
| |
| case POS_XEXP: |
| return kc->position_tests[test.pos->base->id] & TESTED_CODE; |
| |
| case POS_XVECEXP0: |
| return kc->position_tests[test.pos->base->id] & TESTED_VECLEN; |
| } |
| gcc_unreachable (); |
| |
| case rtx_test::REGNO_FIELD: |
| case rtx_test::INT_FIELD: |
| case rtx_test::WIDE_INT_FIELD: |
| case rtx_test::VECLEN: |
| case rtx_test::VECLEN_GE: |
| /* These tests access a specific part of an rtx, so are only safe |
| once we know what the rtx is. */ |
| return kc->position_tests[test.pos->id] & TESTED_CODE; |
| |
| case rtx_test::PEEP2_COUNT: |
| case rtx_test::HAVE_NUM_CLOBBERS: |
| /* These tests can be performed anywhere. */ |
| return true; |
| |
| case rtx_test::PATTERN: |
| gcc_unreachable (); |
| } |
| gcc_unreachable (); |
| } |
| |
| /* Look for a transition that is taken by all successful returns from a range |
| of decisions starting at OUTER and that would be better performed by |
| OUTER's state instead. On success, store all instances of that transition |
| in WHERE and return the last decision in the range. The range could |
| just be OUTER, or it could include later decisions as well. |
| |
| WITH_POSITION_P is true if only tests with position POS should be tried, |
| false if any test should be tried. WORTHWHILE_SINGLE_P is true if the |
| result is useful even when the range contains just a single decision |
| with a single transition. KC are the conditions that are known to |
| hold at OUTER. */ |
| |
| static decision * |
| find_common_test (decision *outer, bool with_position_p, |
| position *pos, bool worthwhile_single_p, |
| known_conditions *kc, vec <transition *> *where) |
| { |
| /* After this, WORTHWHILE_SINGLE_P indicates whether a range that contains |
| just a single decision is useful, regardless of the number of |
| transitions it has. */ |
| if (!outer->singleton ()) |
| worthwhile_single_p = true; |
| /* Quick exit if we don't have enough decisions to form a worthwhile |
| range. */ |
| if (!worthwhile_single_p && !outer->next) |
| return 0; |
| /* Follow the first chain down, as one example of a path that needs |
| to contain the common test. */ |
| for (decision *d = outer; d; d = d->first->to->first) |
| { |
| transition *trans = d->singleton (); |
| if (trans |
| && (!with_position_p || d->test.pos == pos) |
| && safe_to_hoist_p (outer, d->test, kc)) |
| { |
| if (common_test_p (outer, trans, where)) |
| { |
| if (!outer->next) |
| /* We checked above whether the move is worthwhile. */ |
| return outer; |
| /* See how many decisions in OUTER's chain could reuse |
| the same test. */ |
| decision *outer_end = outer; |
| do |
| { |
| unsigned int length = where->length (); |
| if (!common_test_p (outer_end->next, trans, where)) |
| { |
| where->truncate (length); |
| break; |
| } |
| outer_end = outer_end->next; |
| } |
| while (outer_end->next); |
| /* It is worth moving TRANS if it can be shared by more than |
| one decision. */ |
| if (outer_end != outer || worthwhile_single_p) |
| return outer_end; |
| } |
| where->truncate (0); |
| } |
| } |
| return 0; |
| } |
| |
| /* Try to promote common subtests in S to a single, shared decision. |
| Also try to bunch tests for the same position together. POS is the |
| position of the rtx tested before reaching S. KC are the conditions |
| that are known to hold on entry to S. */ |
| |
| static void |
| cse_tests (position *pos, state *s, known_conditions *kc) |
| { |
| for (decision *d = s->first; d; d = d->next) |
| { |
| auto_vec <transition *, 16> where; |
| if (d->test.pos) |
| { |
| /* Try to find conditions that don't depend on a particular rtx, |
| such as pnum_clobbers != NULL or peep2_current_count >= X. |
| It's usually better to check these conditions as soon as |
| possible, so the change is worthwhile even if there is |
| only one copy of the test. */ |
| decision *endd = find_common_test (d, true, 0, true, kc, &where); |
| if (!endd && d->test.pos != pos) |
| /* Try to find other conditions related to position POS |
| before moving to the new position. Again, this is |
| worthwhile even if there is only one copy of the test, |
| since it means that fewer position variables are live |
| at a given time. */ |
| endd = find_common_test (d, true, pos, true, kc, &where); |
| if (!endd) |
| /* Try to find any condition that is used more than once. */ |
| endd = find_common_test (d, false, 0, false, kc, &where); |
| if (endd) |
| { |
| transition *common = where[0]; |
| /* Replace [D, ENDD] with a test like COMMON. We'll recurse |
| on the common test and see the original D again next time. */ |
| d = insert_decision_before (state::range (d, endd), |
| common->from->test, |
| common->labels, |
| common->optional); |
| /* Remove the old tests. */ |
| while (!where.is_empty ()) |
| { |
| transition *trans = where.pop (); |
| trans->from->s->replace (trans->from, trans->to->release ()); |
| } |
| } |
| } |
| |
| /* Make sure that safe_to_hoist_p isn't being overly conservative. |
| It should realize that D's test is safe in the current |
| environment. */ |
| gcc_assert (d->test.kind == rtx_test::C_TEST |
| || d->test.kind == rtx_test::ACCEPT |
| || safe_to_hoist_p (d, d->test, kc)); |
| |
| /* D won't be changed any further by the current optimization. |
| Recurse with the state temporarily updated to include D. */ |
| int prev = 0; |
| switch (d->test.kind) |
| { |
| case rtx_test::CODE: |
| prev = kc->position_tests[d->test.pos->id]; |
| kc->position_tests[d->test.pos->id] |= TESTED_CODE; |
| break; |
| |
| case rtx_test::VECLEN: |
| case rtx_test::VECLEN_GE: |
| prev = kc->position_tests[d->test.pos->id]; |
| kc->position_tests[d->test.pos->id] |= TESTED_VECLEN; |
| break; |
| |
| case rtx_test::SET_OP: |
| prev = kc->set_operands[d->test.u.opno]; |
| gcc_assert (!prev); |
| kc->set_operands[d->test.u.opno] = true; |
| break; |
| |
| case rtx_test::PEEP2_COUNT: |
| prev = kc->peep2_count; |
| kc->peep2_count = MAX (prev, d->test.u.min_len); |
| break; |
| |
| default: |
| break; |
| } |
| for (transition *trans = d->first; trans; trans = trans->next) |
| cse_tests (d->test.pos ? d->test.pos : pos, trans->to, kc); |
| switch (d->test.kind) |
| { |
| case rtx_test::CODE: |
| case rtx_test::VECLEN: |
| case rtx_test::VECLEN_GE: |
| kc->position_tests[d->test.pos->id] = prev; |
| break; |
| |
| case rtx_test::SET_OP: |
| kc->set_operands[d->test.u.opno] = prev; |
| break; |
| |
| case rtx_test::PEEP2_COUNT: |
| kc->peep2_count = prev; |
| break; |
| |
| default: |
| break; |
| } |
| } |
| } |
| |
| /* Return the type of value that can be used to parameterize test KIND, |
| or parameter::UNSET if none. */ |
| |
| parameter::type_enum |
| transition_parameter_type (rtx_test::kind_enum kind) |
| { |
| switch (kind) |
| { |
| case rtx_test::CODE: |
| return parameter::CODE; |
| |
| case rtx_test::MODE: |
| return parameter::MODE; |
| |
| case rtx_test::REGNO_FIELD: |
| return parameter::UINT; |
| |
| case rtx_test::INT_FIELD: |
| case rtx_test::VECLEN: |
| case rtx_test::PATTERN: |
| return parameter::INT; |
| |
| case rtx_test::WIDE_INT_FIELD: |
| return parameter::WIDE_INT; |
| |
| case rtx_test::PEEP2_COUNT: |
| case rtx_test::VECLEN_GE: |
| case rtx_test::SAVED_CONST_INT: |
| case rtx_test::PREDICATE: |
| case rtx_test::DUPLICATE: |
| case rtx_test::HAVE_NUM_CLOBBERS: |
| case rtx_test::C_TEST: |
| case rtx_test::SET_OP: |
| case rtx_test::ACCEPT: |
| return parameter::UNSET; |
| } |
| gcc_unreachable (); |
| } |
| |
| /* Initialize the pos_operand fields of each state reachable from S. |
| If OPERAND_POS[ID] >= 0, the position with id ID is stored in |
| operands[OPERAND_POS[ID]] on entry to S. */ |
| |
| static void |
| find_operand_positions (state *s, vec <int> &operand_pos) |
| { |
| for (decision *d = s->first; d; d = d->next) |
| { |
| int this_operand = (d->test.pos ? operand_pos[d->test.pos->id] : -1); |
| if (this_operand >= 0) |
| d->test.pos_operand = this_operand; |
| if (d->test.kind == rtx_test::SET_OP) |
| operand_pos[d->test.pos->id] = d->test.u.opno; |
| for (transition *trans = d->first; trans; trans = trans->next) |
| find_operand_positions (trans->to, operand_pos); |
| if (d->test.kind == rtx_test::SET_OP) |
| operand_pos[d->test.pos->id] = this_operand; |
| } |
| } |
| |
| /* Statistics about a matching routine. */ |
| struct stats |
| { |
| stats (); |
| |
| /* The total number of decisions in the routine, excluding trivial |
| ones that never fail. */ |
| unsigned int num_decisions; |
| |
| /* The number of non-trivial decisions on the longest path through |
| the routine, and the return value that contributes most to that |
| long path. */ |
| unsigned int longest_path; |
| int longest_path_code; |
| |
| /* The maximum number of times that a single call to the routine |
| can backtrack, and the value returned at the end of that path. |
| "Backtracking" here means failing one decision in state and |
| going onto to the next. */ |
| unsigned int longest_backtrack; |
| int longest_backtrack_code; |
| }; |
| |
| stats::stats () |
| : num_decisions (0), longest_path (0), longest_path_code (-1), |
| longest_backtrack (0), longest_backtrack_code (-1) {} |
| |
| /* Return statistics about S. */ |
| |
| static stats |
| get_stats (state *s) |
| { |
| stats for_s; |
| unsigned int longest_path = 0; |
| for (decision *d = s->first; d; d = d->next) |
| { |
| /* Work out the statistics for D. */ |
| stats for_d; |
| for (transition *trans = d->first; trans; trans = trans->next) |
| { |
| stats for_trans = get_stats (trans->to); |
| for_d.num_decisions += for_trans.num_decisions; |
| /* Each transition is mutually-exclusive, so just pick the |
| longest of the individual paths. */ |
| if (for_d.longest_path <= for_trans.longest_path) |
| { |
| for_d.longest_path = for_trans.longest_path; |
| for_d.longest_path_code = for_trans.longest_path_code; |
| } |
| /* Likewise for backtracking. */ |
| if (for_d.longest_backtrack <= for_trans.longest_backtrack) |
| { |
| for_d.longest_backtrack = for_trans.longest_backtrack; |
| for_d.longest_backtrack_code = for_trans.longest_backtrack_code; |
| } |
| } |
| |
| /* Account for D's test in its statistics. */ |
| if (!d->test.single_outcome_p ()) |
| { |
| for_d.num_decisions += 1; |
| for_d.longest_path += 1; |
| } |
| if (d->test.kind == rtx_test::ACCEPT) |
| { |
| for_d.longest_path_code = d->test.u.acceptance.u.full.code; |
| for_d.longest_backtrack_code = d->test.u.acceptance.u.full.code; |
| } |
| |
| /* Keep a running count of the number of backtracks. */ |
| if (d->prev) |
| for_s.longest_backtrack += 1; |
| |
| /* Accumulate D's statistics into S's. */ |
| for_s.num_decisions += for_d.num_decisions; |
| for_s.longest_path += for_d.longest_path; |
| for_s.longest_backtrack += for_d.longest_backtrack; |
| |
| /* Use the code from the decision with the longest individual path, |
| since that's more likely to be useful if trying to make the |
| path shorter. In the event of a tie, pick the later decision, |
| since that's closer to the end of the path. */ |
| if (longest_path <= for_d.longest_path) |
| { |
| longest_path = for_d.longest_path; |
| for_s.longest_path_code = for_d.longest_path_code; |
| } |
| |
| /* Later decisions in a state are necessarily in a longer backtrack |
| than earlier decisions. */ |
| for_s.longest_backtrack_code = for_d.longest_backtrack_code; |
| } |
| return for_s; |
| } |
| |
| /* Optimize ROOT. Use TYPE to describe ROOT in status messages. */ |
| |
| static void |
| optimize_subroutine_group (const char *type, state *root) |
| { |
| /* Remove optional transitions that turned out not to be worthwhile. */ |
| if (collapse_optional_decisions_p) |
| collapse_optional_decisions (root); |
| |
| /* Try to remove duplicated tests and to rearrange tests into a more |
| logical order. */ |
| if (cse_tests_p) |
| { |
| known_conditions kc; |
| kc.position_tests.safe_grow_cleared (num_positions); |
| kc.set_operands.safe_grow_cleared (num_operands); |
| kc.peep2_count = 1; |
| cse_tests (&root_pos, root, &kc); |
| } |
| |
| /* Try to simplify two or more tests into one. */ |
| if (simplify_tests_p) |
| simplify_tests (root); |
| |
| /* Try to use operands[] instead of xN variables. */ |
| if (use_operand_variables_p) |
| { |
| auto_vec <int> operand_pos (num_positions); |
| for (unsigned int i = 0; i < num_positions; ++i) |
| operand_pos.quick_push (-1); |
| find_operand_positions (root, operand_pos); |
| } |
| |
| /* Print a summary of the new state. */ |
| stats st = get_stats (root); |
| fprintf (stderr, "Statistics for %s:\n", type); |
| fprintf (stderr, " Number of decisions: %6d\n", st.num_decisions); |
| fprintf (stderr, " longest path: %6d (code: %6d)\n", |
| st.longest_path, st.longest_path_code); |
| fprintf (stderr, " longest backtrack: %6d (code: %6d)\n", |
| st.longest_backtrack, st.longest_backtrack_code); |
| } |
| |
| struct merge_pattern_info; |
| |
| /* Represents a transition from one pattern to another. */ |
| struct merge_pattern_transition |
| { |
| merge_pattern_transition (merge_pattern_info *); |
| |
| /* The target pattern. */ |
| merge_pattern_info *to; |
| |
| /* The parameters that the source pattern passes to the target pattern. |
| "parameter (TYPE, true, I)" represents parameter I of the source |
| pattern. */ |
| auto_vec <parameter, MAX_PATTERN_PARAMS> params; |
| }; |
| |
| merge_pattern_transition::merge_pattern_transition (merge_pattern_info *to_in) |
| : to (to_in) |
| { |
| } |
| |
| /* Represents a pattern that can might match several states. The pattern |
| may replace parts of the test with a parameter value. It may also |
| replace transition labels with parameters. */ |
| struct merge_pattern_info |
| { |
| merge_pattern_info (unsigned int); |
| |
| /* If PARAM_TEST_P, the state's singleton test should be generalized |
| to use the runtime value of PARAMS[PARAM_TEST]. */ |
| unsigned int param_test : 8; |
| |
| /* If PARAM_TRANSITION_P, the state's single transition label should |
| be replaced by the runtime value of PARAMS[PARAM_TRANSITION]. */ |
| unsigned int param_transition : 8; |
| |
| /* True if we have decided to generalize the root decision's test, |
| as per PARAM_TEST. */ |
| unsigned int param_test_p : 1; |
| |
| /* Likewise for the root decision's transition, as per PARAM_TRANSITION. */ |
| unsigned int param_transition_p : 1; |
| |
| /* True if the contents of the structure are completely filled in. */ |
| unsigned int complete_p : 1; |
| |
| /* The number of pseudo-statements in the pattern. Used to decide |
| whether it's big enough to break out into a subroutine. */ |
| unsigned int num_statements; |
| |
| /* The number of states that use this pattern. */ |
| unsigned int num_users; |
| |
| /* The number of distinct success values that the pattern returns. */ |
| unsigned int num_results; |
| |
| /* This array has one element for each runtime parameter to the pattern. |
| PARAMS[I] gives the default value of parameter I, which is always |
| constant. |
| |
| These default parameters are used in cases where we match the |
| pattern against some state S1, then add more parameters while |
| matching against some state S2. S1 is then left passing fewer |
| parameters than S2. The array gives us enough informatino to |
| construct a full parameter list for S1 (see update_parameters). |
| |
| If we decide to create a subroutine for this pattern, |
| PARAMS[I].type determines the C type of parameter I. */ |
| auto_vec <parameter, MAX_PATTERN_PARAMS> params; |
| |
| /* All states that match this pattern must have the same number of |
| transitions. TRANSITIONS[I] describes the subpattern for transition |
| number I; it is null if transition I represents a successful return |
| from the pattern. */ |
| auto_vec <merge_pattern_transition *, 1> transitions; |
| |
| /* The routine associated with the pattern, or null if we haven't generated |
| one yet. */ |
| pattern_routine *routine; |
| }; |
| |
| merge_pattern_info::merge_pattern_info (unsigned int num_transitions) |
| : param_test (0), |
| param_transition (0), |
| param_test_p (false), |
| param_transition_p (false), |
| complete_p (false), |
| num_statements (0), |
| num_users (0), |
| num_results (0), |
| routine (0) |
| { |
| transitions.safe_grow_cleared (num_transitions); |
| } |
| |
| /* Describes one way of matching a particular state to a particular |
| pattern. */ |
| struct merge_state_result |
| { |
| merge_state_result (merge_pattern_info *, position *, merge_state_result *); |
| |
| /* A pattern that matches the state. */ |
| merge_pattern_info *pattern; |
| |
| /* If we decide to use this match and create a subroutine for PATTERN, |
| the state should pass the rtx at position ROOT to the pattern's |
| rtx parameter. A null root means that the pattern doesn't need |
| an rtx parameter; all the rtxes it matches come from elsewhere. */ |
| position *root; |
| |
| /* The parameters that should be passed to PATTERN for this state. |
| If the array is shorter than PATTERN->params, the missing entries |
| should be taken from the corresponding element of PATTERN->params. */ |
| auto_vec <parameter, MAX_PATTERN_PARAMS> params; |
| |
| /* An earlier match for the same state, or null if none. Patterns |
| matched by earlier entries are smaller than PATTERN. */ |
| merge_state_result *prev; |
| }; |
| |
| merge_state_result::merge_state_result (merge_pattern_info *pattern_in, |
| position *root_in, |
| merge_state_result *prev_in) |
| : pattern (pattern_in), root (root_in), prev (prev_in) |
| {} |
| |
| /* Information about a state, used while trying to match it against |
| a pattern. */ |
| struct merge_state_info |
| { |
| merge_state_info (state *); |
| |
| /* The state itself. */ |
| state *s; |
| |
| /* Index I gives information about the target of transition I. */ |
| merge_state_info *to_states; |
| |
| /* The number of transitions in S. */ |
| unsigned int num_transitions; |
| |
| /* True if the state has been deleted in favor of a call to a |
| pattern routine. */ |
| bool merged_p; |
| |
| /* The previous state that might be a merge candidate for S, or null |
| if no previous states could be merged with S. */ |
| merge_state_info *prev_same_test; |
| |
| /* A list of pattern matches for this state. */ |
| merge_state_result *res; |
| }; |
| |
| merge_state_info::merge_state_info (state *s_in) |
| : s (s_in), |
| to_states (0), |
| num_transitions (0), |
| merged_p (false), |
| prev_same_test (0), |
| res (0) {} |
| |
| /* True if PAT would be useful as a subroutine. */ |
| |
| static bool |
| useful_pattern_p (merge_pattern_info *pat) |
| { |
| return pat->num_statements >= MIN_COMBINE_COST; |
| } |
| |
| /* PAT2 is a subpattern of PAT1. Return true if PAT2 should be inlined |
| into PAT1's C routine. */ |
| |
| static bool |
| same_pattern_p (merge_pattern_info *pat1, merge_pattern_info *pat2) |
| { |
| return pat1->num_users == pat2->num_users || !useful_pattern_p (pat2); |
| } |
| |
| /* PAT was previously matched against SINFO based on tentative matches |
| for the target states of SINFO's state. Return true if the match |
| still holds; that is, if the target states of SINFO's state still |
| match the corresponding transitions of PAT. */ |
| |
| static bool |
| valid_result_p (merge_pattern_info *pat, merge_state_info *sinfo) |
| { |
| for (unsigned int j = 0; j < sinfo->num_transitions; ++j) |
| if (merge_pattern_transition *ptrans = pat->transitions[j]) |
| { |
| merge_state_result *to_res = sinfo->to_states[j].res; |
| if (!to_res || to_res->pattern != ptrans->to) |
| return false; |
| } |
| return true; |
| } |
| |
| /* Remove any matches that are no longer valid from the head of SINFO's |
| list of matches. */ |
| |
| static void |
| prune_invalid_results (merge_state_info *sinfo) |
| { |
| while (sinfo->res && !valid_result_p (sinfo->res->pattern, sinfo)) |
| { |
| sinfo->res = sinfo->res->prev; |
| gcc_assert (sinfo->res); |
| } |
| } |
| |
| /* Return true if PAT represents the biggest posssible match for SINFO; |
| that is, if the next action of SINFO's state on return from PAT will |
| be something that cannot be merged with any other state. */ |
| |
| static bool |
| complete_result_p (merge_pattern_info *pat, merge_state_info *sinfo) |
| { |
| for (unsigned int j = 0; j < sinfo->num_transitions; ++j) |
| if (sinfo->to_states[j].res && !pat->transitions[j]) |
| return false; |
| return true; |
| } |
| |
| /* Update TO for any parameters that have been added to FROM since TO |
| was last set. The extra parameters in FROM will be constants or |
| instructions to duplicate earlier parameters. */ |
| |
| static void |
| update_parameters (vec <parameter> &to, const vec <parameter> &from) |
| { |
| for (unsigned int i = to.length (); i < from.length (); ++i) |
| to.quick_push (from[i]); |
| } |
| |
| /* Return true if A and B can be tested by a single test. If the test |
| can be parameterised, store the parameter value for A in *PARAMA and |
| the parameter value for B in *PARAMB, otherwise leave PARAMA and |
| PARAMB alone. */ |
| |
| static bool |
| compatible_tests_p (const rtx_test &a, const rtx_test &b, |
| parameter *parama, parameter *paramb) |
| { |
| if (a.kind != b.kind) |
| return false; |
| switch (a.kind) |
| { |
| case rtx_test::PREDICATE: |
| if (a.u.predicate.data != b.u.predicate.data) |
| return false; |
| *parama = parameter (parameter::MODE, false, a.u.predicate.mode); |
| *paramb = parameter (parameter::MODE, false, b.u.predicate.mode); |
| return true; |
| |
| case rtx_test::SAVED_CONST_INT: |
| *parama = parameter (parameter::INT, false, a.u.integer.value); |
| *paramb = parameter (parameter::INT, false, b.u.integer.value); |
| return true; |
| |
| default: |
| return a == b; |
| } |
| } |
| |
| /* PARAMS is an array of the parameters that a state is going to pass |
| to a pattern routine. It is still incomplete; index I has a kind of |
| parameter::UNSET if we don't yet know what the state will pass |
| as parameter I. Try to make parameter ID equal VALUE, returning |
| true on success. */ |
| |
| static bool |
| set_parameter (vec <parameter> ¶ms, unsigned int id, |
| const parameter &value) |
| { |
| if (params[id].type == parameter::UNSET) |
| { |
| if (force_unique_params_p) |
| for (unsigned int i = 0; i < params.length (); ++i) |
| if (params[i] == value) |
| return false; |
| params[id] = value; |
| return true; |
| } |
| return params[id] == value; |
| } |
| |
| /* PARAMS2 is the "params" array for a pattern and PARAMS1 is the |
| set of parameters that a particular state is going to pass to |
| that pattern. |
| |
| Try to extend PARAMS1 and PARAMS2 so that there is a parameter |
| that is equal to PARAM1 for the state and has a default value of |
| PARAM2. Parameters beginning at START were added as part of the |
| same match and so may be reused. */ |
| |
| static bool |
| add_parameter (vec <parameter> ¶ms1, vec <parameter> ¶ms2, |
| const parameter ¶m1, const parameter ¶m2, |
| unsigned int start, unsigned int *res) |
| { |
| gcc_assert (params1.length () == params2.length ()); |
| gcc_assert (!param1.is_param && !param2.is_param); |
| |
| for (unsigned int i = start; i < params2.length (); ++i) |
| if (params1[i] == param1 && params2[i] == param2) |
| { |
| *res = i; |
| return true; |
| } |
| |
| if (force_unique_params_p) |
| for (unsigned int i = 0; i < params2.length (); ++i) |
| if (params1[i] == param1 || params2[i] == param2) |
| return false; |
| |
| if (params2.length () >= MAX_PATTERN_PARAMS) |
| return false; |
| |
| *res = params2.length (); |
| params1.quick_push (param1); |
| params2.quick_push (param2); |
| return true; |
| } |
| |
| /* If *ROOTA is nonnull, return true if the same sequence of steps are |
| required to reach A from *ROOTA as to reach B from ROOTB. If *ROOTA |
| is null, update it if necessary in order to make the condition hold. */ |
| |
| static bool |
| merge_relative_positions (position **roota, position *a, |
| position *rootb, position *b) |
| { |
| if (!relative_patterns_p) |
| { |
| if (a != b) |
| return false; |
| if (!*roota) |
| { |
| *roota = rootb; |
| return true; |
| } |
| return *roota == rootb; |
| } |
| /* If B does not belong to the same instruction as ROOTB, we don't |
| start with ROOTB but instead start with a call to peep2_next_insn. |
| In that case the sequences for B and A are identical iff B and A |
| are themselves identical. */ |
| if (rootb->insn_id != b->insn_id) |
| return a == b; |
| while (rootb != b) |
| { |
| if (!a || b->type != a->type || b->arg != a->arg) |
| return false; |
| b = b->base; |
| a = a->base; |
| } |
| if (!*roota) |
| *roota = a; |
| return *roota == a; |
| } |
| |
| /* A hasher of states that treats two states as "equal" if they might be |
| merged (but trying to be more discriminating than "return true"). */ |
| struct test_pattern_hasher : nofree_ptr_hash <merge_state_info> |
| { |
| static inline hashval_t hash (const value_type &); |
| static inline bool equal (const value_type &, const compare_type &); |
| }; |
| |
| hashval_t |
| test_pattern_hasher::hash (merge_state_info *const &sinfo) |
| { |
| inchash::hash h; |
| decision *d = sinfo->s->singleton (); |
| h.add_int (d->test.pos_operand + 1); |
| if (!relative_patterns_p) |
| h.add_int (d->test.pos ? d->test.pos->id + 1 : 0); |
| h.add_int (d->test.kind); |
| h.add_int (sinfo->num_transitions); |
| return h.end (); |
| } |
| |
| bool |
| test_pattern_hasher::equal (merge_state_info *const &sinfo1, |
| merge_state_info *const &sinfo2) |
| { |
| decision *d1 = sinfo1->s->singleton (); |
| decision *d2 = sinfo2->s->singleton (); |
| gcc_assert (d1 && d2); |
| |
| parameter new_param1, new_param2; |
| return (d1->test.pos_operand == d2->test.pos_operand |
| && (relative_patterns_p || d1->test.pos == d2->test.pos) |
| && compatible_tests_p (d1->test, d2->test, &new_param1, &new_param2) |
| && sinfo1->num_transitions == sinfo2->num_transitions); |
| } |
| |
| /* Try to make the state described by SINFO1 use the same pattern as the |
| state described by SINFO2. Return true on success. |
| |
| SINFO1 and SINFO2 are known to have the same hash value. */ |
| |
| static bool |
| merge_patterns (merge_state_info *sinfo1, merge_state_info *sinfo2) |
| { |
| merge_state_result *res2 = sinfo2->res; |
| merge_pattern_info *pat = res2->pattern; |
| |
| /* Write to temporary arrays while matching, in case we have to abort |
| half way through. */ |
| auto_vec <parameter, MAX_PATTERN_PARAMS> params1; |
| auto_vec <parameter, MAX_PATTERN_PARAMS> params2; |
| params1.quick_grow_cleared (pat->params.length ()); |
| params2.splice (pat->params); |
| unsigned int start_param = params2.length (); |
| |
| /* An array for recording changes to PAT->transitions[?].params. |
| All changes involve replacing a constant parameter with some |
| PAT->params[N], where N is the second element of the pending_param. */ |
| typedef std::pair <parameter *, unsigned int> pending_param; |
| auto_vec <pending_param, 32> pending_params; |
| |
| decision *d1 = sinfo1->s->singleton (); |
| decision *d2 = sinfo2->s->singleton (); |
| gcc_assert (d1 && d2); |
| |
| /* If D2 tests a position, SINFO1's root relative to D1 is the same |
| as SINFO2's root relative to D2. */ |
| position *root1 = 0; |
| position *root2 = res2->root; |
| if (d2->test.pos_operand < 0 |
| && d1->test.pos |
| && !merge_relative_positions (&root1, d1->test.pos, |
| root2, d2->test.pos)) |
| return false; |
| |
| /* Check whether the patterns have the same shape. */ |
| unsigned int num_transitions = sinfo1->num_transitions; |
| gcc_assert (num_transitions == sinfo2->num_transitions); |
| for (unsigned int i = 0; i < num_transitions; ++i) |
| if (merge_pattern_transition *ptrans = pat->transitions[i]) |
| { |
| merge_state_result *to1_res = sinfo1->to_states[i].res; |
| merge_state_result *to2_res = sinfo2->to_states[i].res; |
| merge_pattern_info *to_pat = ptrans->to; |
| gcc_assert (to2_res && to2_res->pattern == to_pat); |
| if (!to1_res || to1_res->pattern != to_pat) |
| return false; |
| if (to2_res->root |
| && !merge_relative_positions (&root1, to1_res->root, |
| root2, to2_res->root)) |
| return false; |
| /* Match the parameters that TO1_RES passes to TO_PAT with the |
| parameters that PAT passes to TO_PAT. */ |
| update_parameters (to1_res->params, to_pat->params); |
| for (unsigned int j = 0; j < to1_res->params.length (); ++j) |
| { |
| const parameter ¶m1 = to1_res->params[j]; |
| const parameter ¶m2 = ptrans->params[j]; |
| gcc_assert (!param1.is_param); |
| if (param2.is_param) |
| { |
| if (!set_parameter (params1, param2.value, param1)) |
| return false; |
| } |
| else if (param1 != param2) |
| { |
| unsigned int id; |
| if (!add_parameter (params1, params2, |
| param1, param2, start_param, &id)) |
| return false; |
| /* Record that PAT should now pass parameter ID to TO_PAT, |
| instead of the current contents of *PARAM2. We only |
| make the change if the rest of the match succeeds. */ |
| pending_params.safe_push |
| (pending_param (&ptrans->params[j], id)); |
| } |
| } |
| } |
| |
| unsigned int param_test = pat->param_test; |
| unsigned int param_transition = pat->param_transition; |
| bool param_test_p = pat->param_test_p; |
| bool param_transition_p = pat->param_transition_p; |
| |
| /* If the tests don't match exactly, try to parameterize them. */ |
| parameter new_param1, new_param2; |
| if (!compatible_tests_p (d1->test, d2->test, &new_param1, &new_param2)) |
| gcc_unreachable (); |
| if (new_param1.type != parameter::UNSET) |
| { |
| /* If the test has not already been parameterized, all existing |
| matches use constant NEW_PARAM2. */ |
| if (param_test_p) |
| { |
| if (!set_parameter (params1, param_test, new_param1)) |
| return false; |
| } |
| else if (new_param1 != new_param2) |
| { |
| if (!add_parameter (params1, params2, new_param1, new_param2, |
| start_param, ¶m_test)) |
| return false; |
| param_test_p = true; |
| } |
| } |
| |
| /* Match the transitions. */ |
| transition *trans1 = d1->first; |
| transition *trans2 = d2->first; |
| for (unsigned int i = 0; i < num_transitions; ++i) |
| { |
| if (param_transition_p || trans1->labels != trans2->labels) |
| { |
| /* We can only generalize a single transition with a single |
| label. */ |
| if (num_transitions != 1 |
| || trans1->labels.length () != 1 |
| || trans2->labels.length () != 1) |
| return false; |
| |
| /* Although we can match wide-int fields, in practice it leads |
| to some odd results for const_vectors. We end up |
| parameterizing the first N const_ints of the vector |
| and then (once we reach the maximum number of parameters) |
| we go on to match the other elements exactly. */ |
| if (d1->test.kind == rtx_test::WIDE_INT_FIELD) |
| return false; |
| |
| /* See whether the label has a generalizable type. */ |
| parameter::type_enum param_type |
| = transition_parameter_type (d1->test.kind); |
| if (param_type == parameter::UNSET) |
| return false; |
| |
| /* Match the labels using parameters. */ |
| new_param1 = parameter (param_type, false, trans1->labels[0]); |
| if (param_transition_p) |
| { |
| if (!set_parameter (params1, param_transition, new_param1)) |
| return false; |
| } |
| else |
| { |
| new_param2 = parameter (param_type, false, trans2->labels[0]); |
| if (!add_parameter (params1, params2, new_param1, new_param2, |
| start_param, ¶m_transition)) |
| return false; |
| param_transition_p = true; |
| } |
| } |
| trans1 = trans1->next; |
| trans2 = trans2->next; |
| } |
| |
| /* Set any unset parameters to their default values. This occurs if some |
| other state needed something to be parameterized in order to match SINFO2, |
| but SINFO1 on its own does not. */ |
| for (unsigned int i = 0; i < params1.length (); ++i) |
| if (params1[i].type == parameter::UNSET) |
| params1[i] = params2[i]; |
| |
| /* The match was successful. Commit all pending changes to PAT. */ |
| update_parameters (pat->params, params2); |
| { |
| pending_param *pp; |
| unsigned int i; |
| FOR_EACH_VEC_ELT (pending_params, i, pp) |
| *pp->first = parameter (pp->first->type, true, pp->second); |
| } |
| pat->param_test = param_test; |
| pat->param_transition = param_transition; |
| pat->param_test_p = param_test_p; |
| pat->param_transition_p = param_transition_p; |
| |
| /* Record the match of SINFO1. */ |
| merge_state_result *new_res1 = new merge_state_result (pat, root1, |
| sinfo1->res); |
| new_res1->params.splice (params1); |
| sinfo1->res = new_res1; |
| return true; |
| } |
| |
| /* The number of states that were removed by calling pattern routines. */ |
| static unsigned int pattern_use_states; |
| |
| /* The number of states used while defining pattern routines. */ |
| static unsigned int pattern_def_states; |
| |
| /* Information used while constructing a use or definition of a pattern |
| routine. */ |
| struct create_pattern_info |
| { |
| /* The routine itself. */ |
| pattern_routine *routine; |
| |
| /* The first unclaimed return value for this particular use or definition. |
| We walk the substates of uses and definitions in the same order |
| so each return value always refers to the same position within |
| the pattern. */ |
| unsigned int next_result; |
| }; |
| |
| static void populate_pattern_routine (create_pattern_info *, |
| merge_state_info *, state *, |
| const vec <parameter> &); |
| |
| /* SINFO matches a pattern for which we've decided to create a C routine. |
| Return a decision that performs a call to the pattern routine, |
| but leave the caller to add the transitions to it. Initialize CPI |
| for this purpose. Also create a definition for the pattern routine, |
| if it doesn't already have one. |
| |
| PARAMS are the parameters that SINFO passes to its pattern. */ |
| |
| static decision * |
| init_pattern_use (create_pattern_info *cpi, merge_state_info *sinfo, |
| const vec <parameter> ¶ms) |
| { |
| state *s = sinfo->s; |
| merge_state_result *res = sinfo->res; |
| merge_pattern_info *pat = res->pattern; |
| cpi->routine = pat->routine; |
| if (!cpi->routine) |
| { |
| /* We haven't defined the pattern routine yet, so create |
| a definition now. */ |
| pattern_routine *routine = new pattern_routine; |
| pat->routine = routine; |
| cpi->routine = routine; |
| routine->s = new state; |
| routine->insn_p = false; |
| routine->pnum_clobbers_p = false; |
| |
| /* Create an "idempotent" mapping of parameter I to parameter I. |
| Also record the C type of each parameter to the routine. */ |
| auto_vec <parameter, MAX_PATTERN_PARAMS> def_params; |
| for (unsigned int i = 0; i < pat->params.length (); ++i) |
| { |
| def_params.quick_push (parameter (pat->params[i].type, true, i)); |
| routine->param_types.quick_push (pat->params[i].type); |
| } |
| |
| /* Any of the states that match the pattern could be used to |
| create the routine definition. We might as well use SINFO |
| since it's already to hand. This means that all positions |
| in the definition will be relative to RES->root. */ |
| routine->pos = res->root; |
| cpi->next_result = 0; |
| populate_pattern_routine (cpi, sinfo, routine->s, def_params); |
| gcc_assert (cpi->next_result == pat->num_results); |
| |
| /* Add the routine to the global list, after the subroutines |
| that it calls. */ |
| routine->pattern_id = patterns.length (); |
| patterns.safe_push (routine); |
| } |
| |
| /* Create a decision to call the routine, passing PARAMS to it. */ |
| pattern_use *use = new pattern_use; |
| use->routine = pat->routine; |
| use->params.splice (params); |
| decision *d = new decision (rtx_test::pattern (res->root, use)); |
| |
| /* If the original decision could use an element of operands[] instead |
| of an rtx variable, try to transfer it to the new decision. */ |
| if (s->first->test.pos && res->root == s->first->test.pos) |
| d->test.pos_operand = s->first->test.pos_operand; |
| |
| cpi->next_result = 0; |
| return d; |
| } |
| |
| /* Make S return the next unclaimed pattern routine result for CPI. */ |
| |
| static void |
| add_pattern_acceptance (create_pattern_info *cpi, state *s) |
| { |
| acceptance_type acceptance; |
| acceptance.type = SUBPATTERN; |
| acceptance.partial_p = false; |
| acceptance.u.full.code = cpi->next_result; |
| add_decision (s, rtx_test::accept (acceptance), true, false); |
| cpi->next_result += 1; |
| } |
| |
| /* Initialize new empty state NEWS so that it implements SINFO's pattern |
| (here referred to as "P"). P may be the top level of a pattern routine |
| or a subpattern that should be inlined into its parent pattern's routine |
| (as per same_pattern_p). The choice of SINFO for a top-level pattern is |
| arbitrary; it could be any of the states that use P. The choice for |
| subpatterns follows the choice for the parent pattern. |
| |
| PARAMS gives the value of each parameter to P in terms of the parameters |
| to the top-level pattern. If P itself is the top level pattern, PARAMS[I] |
| is always "parameter (TYPE, true, I)". */ |
| |
| static void |
| populate_pattern_routine (create_pattern_info *cpi, merge_state_info *sinfo, |
| state *news, const vec <parameter> ¶ms) |
| { |
| pattern_def_states += 1; |
| |
| decision *d = sinfo->s->singleton (); |
| merge_pattern_info *pat = sinfo->res->pattern; |
| pattern_routine *routine = cpi->routine; |
| |
| /* Create a copy of D's test for the pattern routine and generalize it |
| as appropriate. */ |
| decision *newd = new decision (d->test); |
| gcc_assert (newd->test.pos_operand >= 0 |
| || !newd->test.pos |
| || common_position (newd->test.pos, |
| routine->pos) == routine->pos); |
| if (pat->param_test_p) |
| { |
| const parameter ¶m = params[pat->param_test]; |
| switch (newd->test.kind) |
| { |
| case rtx_test::PREDICATE: |
| newd->test.u.predicate.mode_is_param = param.is_param; |
| newd->test.u.predicate.mode = param.value; |
| break; |
| |
| case rtx_test::SAVED_CONST_INT: |
| newd->test.u.integer.is_param = param.is_param; |
| newd->test.u.integer.value = param.value; |
| break; |
| |
| default: |
| gcc_unreachable (); |
| break; |
| } |
| } |
| if (d->test.kind == rtx_test::C_TEST) |
| routine->insn_p = true; |
| else if (d->test.kind == rtx_test::HAVE_NUM_CLOBBERS) |
| routine->pnum_clobbers_p = true; |
| news->push_back (newd); |
| |
| /* Fill in the transitions of NEWD. */ |
| unsigned int i = 0; |
| for (transition *trans = d->first; trans; trans = trans->next) |
| { |
| /* Create a new state to act as the target of the new transition. */ |
| state *to_news = new state; |
| if (merge_pattern_transition *ptrans = pat->transitions[i]) |
| { |
| /* The pattern hasn't finished matching yet. Get the target |
| pattern and the corresponding target state of SINFO. */ |
| merge_pattern_info *to_pat = ptrans->to; |
| merge_state_info *to = sinfo->to_states + i; |
| gcc_assert (to->res->pattern == to_pat); |
| gcc_assert (ptrans->params.length () == to_pat->params.length ()); |
| |
| /* Express the parameters to TO_PAT in terms of the parameters |
| to the top-level pattern. */ |
| auto_vec <parameter, MAX_PATTERN_PARAMS> to_params; |
| for (unsigned int j = 0; j < ptrans->params.length (); ++j) |
| { |
| const parameter ¶m = ptrans->params[j]; |
| to_params.quick_push (param.is_param |
| ? params[param.value] |
| : param); |
| } |
| |
| if (same_pattern_p (pat, to_pat)) |
| /* TO_PAT is part of the current routine, so just recurse. */ |
| populate_pattern_routine (cpi, to, to_news, to_params); |
| else |
| { |
| /* TO_PAT should be matched by calling a separate routine. */ |
| create_pattern_info sub_cpi; |
| decision *subd = init_pattern_use (&sub_cpi, to, to_params); |
| routine->insn_p |= sub_cpi.routine->insn_p; |
| routine->pnum_clobbers_p |= sub_cpi.routine->pnum_clobbers_p; |
| |
| /* Add the pattern routine call to the new target state. */ |
| to_news->push_back (subd); |
| |
| /* Add a transition for each successful call result. */ |
| for (unsigned int j = 0; j < to_pat->num_results; ++j) |
| { |
| state *res = new state; |
| add_pattern_acceptance (cpi, res); |
| subd->push_back (new transition (j, res, false)); |
| } |
| } |
| } |
| else |
| /* This transition corresponds to a successful match. */ |
| add_pattern_acceptance (cpi, to_news); |
| |
| /* Create the transition itself, generalizing as necessary. */ |
| transition *new_trans = new transition (trans->labels, to_news, |
| trans->optional); |
| if (pat->param_transition_p) |
| { |
| const parameter ¶m = params[pat->param_transition]; |
| new_trans->is_param = param.is_param; |
| new_trans->labels[0] = param.value; |
| } |
| newd->push_back (new_trans); |
| i += 1; |
| } |
| } |
| |
| /* USE is a decision that calls a pattern routine and SINFO is part of the |
| original state tree that the call is supposed to replace. Add the |
| transitions for SINFO and its substates to USE. */ |
| |
| static void |
| populate_pattern_use (create_pattern_info *cpi, decision *use, |
| merge_state_info *sinfo) |
| { |
| pattern_use_states += 1; |
| gcc_assert (!sinfo->merged_p); |
| sinfo->merged_p = true; |
| merge_state_result *res = sinfo->res; |
| merge_pattern_info *pat = res->pattern; |
| decision *d = sinfo->s->singleton (); |
| unsigned int i = 0; |
| for (transition *trans = d->first; trans; trans = trans->next) |
| { |
| if (pat->transitions[i]) |
| /* The target state is also part of the pattern. */ |
| populate_pattern_use (cpi, use, sinfo->to_states + i); |
| else |
| { |
| /* The transition corresponds to a successful return from the |
| pattern routine. */ |
| use->push_back (new transition (cpi->next_result, trans->to, false)); |
| cpi->next_result += 1; |
| } |
| i += 1; |
| } |
| } |
| |
| /* We have decided to replace SINFO's state with a call to a pattern |
| routine. Make the change, creating a definition of the pattern routine |
| if it doesn't have one already. */ |
| |
| static void |
| use_pattern (merge_state_info *sinfo) |
| { |
| merge_state_result *res = sinfo->res; |
| merge_pattern_info *pat = res->pattern; |
| state *s = sinfo->s; |
| |
| /* The pattern may have acquired new parameters after it was matched |
| against SINFO. Update the parameters that SINFO passes accordingly. */ |
| update_parameters (res->params, pat->params); |
| |
| create_pattern_info cpi; |
| decision *d = init_pattern_use (&cpi, sinfo, res->params); |
| populate_pattern_use (&cpi, d, sinfo); |
| s->release (); |
| s->push_back (d); |
| } |
| |
| /* Look through the state trees in STATES for common patterns and |
| split them into subroutines. */ |
| |
| static void |
| split_out_patterns (vec <merge_state_info> &states) |
| { |
| unsigned int first_transition = states.length (); |
| hash_table <test_pattern_hasher> hashtab (128); |
| /* Stage 1: Create an order in which parent states come before their child |
| states and in which sibling states are at consecutive locations. |
| Having consecutive sibling states allows merge_state_info to have |
| a single to_states pointer. */ |
| for (unsigned int i = 0; i < states.length (); ++i) |
| for (decision *d = states[i].s->first; d; d = d->next) |
| for (transition *trans = d->first; trans; trans = trans->next) |
| { |
| states.safe_push (trans->to); |
| states[i].num_transitions += 1; |
| } |
| /* Stage 2: Now that the addresses are stable, set up the to_states |
| pointers. Look for states that might be merged and enter them |
| into the hash table. */ |
| for (unsigned int i = 0; i < states.length (); ++i) |
| { |
| merge_state_info *sinfo = &states[i]; |
| if (sinfo->num_transitions) |
| { |
| sinfo->to_states = &states[first_transition]; |
| first_transition += sinfo->num_transitions; |
| } |
| /* For simplicity, we only try to merge states that have a single |
| decision. This is in any case the best we can do for peephole2, |
| since whether a peephole2 ACCEPT succeeds or not depends on the |
| specific peephole2 pattern (which is unique to each ACCEPT |
| and so couldn't be shared between states). */ |
| if (decision *d = sinfo->s->singleton ()) |
| /* ACCEPT states are unique, so don't even try to merge them. */ |
| if (d->test.kind != rtx_test::ACCEPT |
| && (pattern_have_num_clobbers_p |
| || d->test.kind != rtx_test::HAVE_NUM_CLOBBERS) |
| && (pattern_c_test_p |
| || d->test.kind != rtx_test::C_TEST)) |
| { |
| merge_state_info **slot = hashtab.find_slot (sinfo, INSERT); |
| sinfo->prev_same_test = *slot; |
| *slot = sinfo; |
| } |
| } |
| /* Stage 3: Walk backwards through the list of states and try to merge |
| them. This is a greedy, bottom-up match; parent nodes can only start |
| a new leaf pattern if they fail to match when combined with all child |
| nodes that have matching patterns. |
| |
| For each state we keep a list of potential matches, with each |
| potential match being larger (and deeper) than the next match in |
| the list. The final element in the list is a leaf pattern that |
| matches just a single state. |
| |
| Each candidate pattern created in this loop is unique -- it won't |
| have been seen by an earlier iteration. We try to match each pattern |
| with every state that appears earlier in STATES. |
| |
| Because the patterns created in the loop are unique, any state |
| that already has a match must have a final potential match that |
| is different from any new leaf pattern. Therefore, when matching |
| leaf patterns, we need only consider states whose list of matches |
| is empty. |
| |
| The non-leaf patterns that we try are as deep as possible |
| and are an extension of the state's previous best candidate match (PB). |
| We need only consider states whose current potential match is also PB; |
| any states that don't match as much as PB cannnot match the new pattern, |
| while any states that already match more than PB must be different from |
| the new pattern. */ |
| for (unsigned int i2 = states.length (); i2-- > 0; ) |
| { |
| merge_state_info *sinfo2 = &states[i2]; |
| |
| /* Enforce the bottom-upness of the match: remove matches with later |
| states if SINFO2's child states ended up finding a better match. */ |
| prune_invalid_results (sinfo2); |
| |
| /* Do nothing if the state doesn't match a later one and if there are |
| no earlier states it could match. */ |
| if (!sinfo2->res && !sinfo2->prev_same_test) |
| con
|