/* Generate code from machine description to recognize rtl as insns.
- Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1997, 1998,
- 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 1987-2020 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 2, or (at your option)
+ 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
License for more details.
You should have received a copy of the GNU General Public License
- along with GCC; see the file COPYING. If not, write to the Free
- Software Foundation, 59 Temple Place - Suite 330, Boston, MA
- 02111-1307, USA. */
+ 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
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. */
-
-#include "bconfig.h"
-#include "system.h"
-#include "coretypes.h"
-#include "tm.h"
-#include "rtl.h"
-#include "errors.h"
-#include "gensupport.h"
+ to the last recognized insn in the old sequence.
-#define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
- printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
+ At a high level, the algorithm used in this file is as follows:
-/* Holds an array of names indexed by insn_code_number. */
-static char **insn_name_ptr = 0;
-static int insn_name_ptr_size = 0;
+ 1. Build up a decision tree for each routine, using the following
+ approach to matching an rtx:
-/* A listhead of decision trees. The alternatives to a node are kept
- in a doubly-linked list so we can easily add nodes to the proper
- place when merging. */
+ - 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.
-struct decision_head
-{
- struct decision *first;
- struct decision *last;
-};
+ - 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.
-/* A single test. The two accept types aren't tests per-se, but
- their equality (or lack thereof) does affect tree merging so
- it is convenient to keep them here. */
+ - Next check match_dups.
-struct decision_test
-{
- /* A linked list through the tests attached to a node. */
- struct decision_test *next;
+ - Finally check the C condition and (where appropriate) pnum_clobbers.
- /* These types are roughly in the order in which we'd like to test them. */
- enum decision_type
- {
- DT_mode, DT_code, DT_veclen,
- DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide, DT_elt_zero_wide_safe,
- DT_const_int,
- DT_veclen_ge, DT_dup, DT_pred, DT_c_test,
- DT_accept_op, DT_accept_insn
- } type;
+ 2. Try to optimize the tree by removing redundant tests, CSEing tests,
+ folding tests together, etc.
- union
- {
- enum machine_mode mode; /* Machine mode of node. */
- RTX_CODE code; /* Code to test. */
+ 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:
- struct
- {
- const char *name; /* Predicate to call. */
- int index; /* Index into `preds' or -1. */
- enum machine_mode mode; /* Machine mode for node. */
- } pred;
-
- const char *c_test; /* Additional test to perform. */
- int veclen; /* Length of vector. */
- int dup; /* Number of operand to compare against. */
- HOST_WIDE_INT intval; /* Value for XINT for XWINT. */
- int opno; /* Operand number matched. */
-
- struct {
- int code_number; /* Insn number matched. */
- int lineno; /* Line number of the insn. */
- int num_clobbers_to_add; /* Number of CLOBBERs to be added. */
- } insn;
- } u;
-};
+ (plus:SI (match_operand:SI 1 "register_operand")
+ (match_operand:SI 2 "register_operand"))
-/* Data structure for decision tree for recognizing legitimate insns. */
+ we can split the associated matching code out into a subroutine.
+ If a pattern contains:
-struct decision
-{
- struct decision_head success; /* Nodes to test on success. */
- struct decision *next; /* Node to test on failure. */
- struct decision *prev; /* Node whose failure tests us. */
- struct decision *afterward; /* Node to test on success,
- but failure of successor nodes. */
+ (minus:DI (match_operand:DI 1 "register_operand")
+ (match_operand:DI 2 "register_operand"))
- const char *position; /* String denoting position in pattern. */
+ 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.
- struct decision_test *tests; /* The tests for this node. */
+ 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.
- int number; /* Node number, used for labels */
- int subroutine_number; /* Number of subroutine this node starts */
- int need_label; /* Label needs to be output. */
-};
+ 4. Split the matching trees into functions, trying to limit the
+ size of each function to a sensible amount.
-#define SUBROUTINE_THRESHOLD 100
+ 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.)
-static int next_subroutine_number;
+ 5. Write out C++ code for each function. */
-/* We can write three types of subroutines: One for insn recognition,
- one to split insns, and one for peephole-type optimizations. This
- defines which type is being written. */
+#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"
-enum routine_type {
- RECOG, SPLIT, PEEPHOLE2
+#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
};
-#define IS_SPLIT(X) ((X) != RECOG)
-
-/* Next available node number for tree nodes. */
+/* 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;
-static int next_number;
+ /* A position with the same BASE and TYPE, but with the next value
+ of ARG. */
+ struct position *next;
-/* Next number to use as an insn_code. */
+ /* 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;
-static int next_insn_code;
+ /* 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;
-/* Similar, but counts all expressions in the MD file; used for
- error messages. */
+ /* The type of position. */
+ enum position_type type;
-static int next_index;
+ /* The argument to TYPE (shown as ARG in the position_type comments). */
+ int arg;
-/* Record the highest depth we ever have so we know how many variables to
- allocate in each subroutine we make. */
+ /* The instruction to which the position belongs. */
+ unsigned int insn_id;
-static int max_depth;
+ /* 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;
-/* The line number of the start of the pattern currently being processed. */
-static int pattern_lineno;
+ /* A unique identifier for this position. */
+ unsigned int id;
+};
-/* Count of errors. */
-static int error_count;
-\f
-/* This table contains a list of the rtl codes that can possibly match a
- predicate defined in recog.c. The function `maybe_both_true' uses it to
- deduce that there are no expressions that can be matches by certain pairs
- of tree nodes. Also, if a predicate can match only one code, we can
- hardwire that code into the node testing the predicate. */
-
-static const struct pred_table
-{
- const char *const name;
- const RTX_CODE codes[NUM_RTX_CODE];
-} preds[] = {
- {"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
- LABEL_REF, SUBREG, REG, MEM }},
-#ifdef PREDICATE_CODES
- PREDICATE_CODES
-#endif
- {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
- LABEL_REF, SUBREG, REG, MEM,
- PLUS, MINUS, MULT}},
- {"register_operand", {SUBREG, REG}},
- {"pmode_register_operand", {SUBREG, REG}},
- {"scratch_operand", {SCRATCH, REG}},
- {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
- LABEL_REF}},
- {"const_int_operand", {CONST_INT}},
- {"const_double_operand", {CONST_INT, CONST_DOUBLE}},
- {"nonimmediate_operand", {SUBREG, REG, MEM}},
- {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF,
- LABEL_REF, SUBREG, REG}},
- {"push_operand", {MEM}},
- {"pop_operand", {MEM}},
- {"memory_operand", {SUBREG, MEM}},
- {"indirect_operand", {SUBREG, MEM}},
- {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU,
- UNORDERED, ORDERED, UNEQ, UNGE, UNGT, UNLE,
- UNLT, LTGT}}
+enum routine_type {
+ SUBPATTERN, RECOG, SPLIT, PEEPHOLE2
};
-#define NUM_KNOWN_PREDS ARRAY_SIZE (preds)
+/* The root position (x0). */
+static struct position root_pos;
-static const char *const special_mode_pred_table[] = {
-#ifdef SPECIAL_MODE_PREDICATES
- SPECIAL_MODE_PREDICATES
-#endif
- "pmode_register_operand"
-};
+/* The number of positions created. Also one higher than the maximum
+ position id. */
+static unsigned int num_positions = 1;
-#define NUM_SPECIAL_MODE_PREDS ARRAY_SIZE (special_mode_pred_table)
-
-static struct decision *new_decision
- (const char *, struct decision_head *);
-static struct decision_test *new_decision_test
- (enum decision_type, struct decision_test ***);
-static rtx find_operand
- (rtx, int, rtx);
-static rtx find_matching_operand
- (rtx, int);
-static void validate_pattern
- (rtx, rtx, rtx, int);
-static struct decision *add_to_sequence
- (rtx, struct decision_head *, const char *, enum routine_type, int);
-
-static int maybe_both_true_2
- (struct decision_test *, struct decision_test *);
-static int maybe_both_true_1
- (struct decision_test *, struct decision_test *);
-static int maybe_both_true
- (struct decision *, struct decision *, int);
-
-static int nodes_identical_1
- (struct decision_test *, struct decision_test *);
-static int nodes_identical
- (struct decision *, struct decision *);
-static void merge_accept_insn
- (struct decision *, struct decision *);
-static void merge_trees
- (struct decision_head *, struct decision_head *);
-
-static void factor_tests
- (struct decision_head *);
-static void simplify_tests
- (struct decision_head *);
-static int break_out_subroutines
- (struct decision_head *, int);
-static void find_afterward
- (struct decision_head *, struct decision *);
-
-static void change_state
- (const char *, const char *, struct decision *, const char *);
-static void print_code
- (enum rtx_code);
-static void write_afterward
- (struct decision *, struct decision *, const char *);
-static struct decision *write_switch
- (struct decision *, int);
-static void write_cond
- (struct decision_test *, int, enum routine_type);
-static void write_action
- (struct decision *, struct decision_test *, int, int,
- struct decision *, enum routine_type);
-static int is_unconditional
- (struct decision_test *, enum routine_type);
-static int write_node
- (struct decision *, int, enum routine_type);
-static void write_tree_1
- (struct decision_head *, int, enum routine_type);
-static void write_tree
- (struct decision_head *, const char *, enum routine_type, int);
-static void write_subroutine
- (struct decision_head *, enum routine_type);
-static void write_subroutines
- (struct decision_head *, enum routine_type);
-static void write_header
- (void);
-
-static struct decision_head make_insn_sequence
- (rtx, enum routine_type);
-static void process_tree
- (struct decision_head *, enum routine_type);
-
-static void record_insn_name
- (int, const char *);
-
-static void debug_decision_0
- (struct decision *, int, int);
-static void debug_decision_1
- (struct decision *, int);
-static void debug_decision_2
- (struct decision_test *);
-extern void debug_decision
- (struct decision *);
-extern void debug_decision_list
- (struct decision *);
+/* 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;
\f
-/* Create a new node in sequence after LAST. */
-
-static struct decision *
-new_decision (const char *position, struct decision_head *last)
+/* 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 decision *new = xcalloc (1, sizeof (struct decision));
+ struct position *pos;
- new->success = *last;
- new->position = xstrdup (position);
- new->number = next_number++;
-
- last->first = last->last = new;
- return new;
+ 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;
}
-/* Create a new test and link it in at PLACE. */
+/* Compare positions POS1 and POS2 lexicographically. */
-static struct decision_test *
-new_decision_test (enum decision_type type, struct decision_test ***pplace)
+static int
+compare_positions (struct position *pos1, struct position *pos2)
{
- struct decision_test **place = *pplace;
- struct decision_test *test;
-
- test = xmalloc (sizeof (*test));
- test->next = *place;
- test->type = type;
- *place = test;
+ 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;
+}
- place = &test->next;
- *pplace = place;
+/* 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. */
- return test;
+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;
}
-
+\f
/* Search for and return operand N, stop when reaching node STOP. */
static rtx
return r;
break;
- case 'i': case 'w': case '0': case 's':
+ case 'r': case 'p': case 'i': case 'w': case '0': case 's':
break;
default:
- abort ();
+ gcc_unreachable ();
}
}
return r;
break;
- case 'i': case 'w': case '0': case 's':
+ case 'r': case 'p': case 'i': case 'w': case '0': case 's':
break;
default:
- abort ();
+ 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 patterns. 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. */
+/* 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, rtx insn, rtx set, int set_code)
+validate_pattern (rtx pattern, md_rtx_info *info, rtx set, int set_code)
{
const char *fmt;
RTX_CODE code;
switch (code)
{
case MATCH_SCRATCH:
- return;
+ {
+ 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 (insn, XINT (pattern, 0), pattern) == pattern)
- {
- message_with_line (pattern_lineno,
- "operand %i duplicated before defined",
- XINT (pattern, 0));
- error_count++;
- }
+ 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);
- int allows_non_lvalue = 1, allows_non_const = 1;
- int special_mode_pred = 0;
+ const struct pred_data *pred;
const char *c_test;
- if (GET_CODE (insn) == DEFINE_INSN)
- c_test = XSTR (insn, 2);
- else
- c_test = XSTR (insn, 1);
+ c_test = get_c_test (info->def);
if (pred_name[0] != 0)
{
- for (i = 0; i < NUM_KNOWN_PREDS; i++)
- if (! strcmp (preds[i].name, pred_name))
- break;
-
- if (i < NUM_KNOWN_PREDS)
- {
- int j;
-
- allows_non_lvalue = allows_non_const = 0;
- for (j = 0; preds[i].codes[j] != 0; j++)
- {
- RTX_CODE c = preds[i].codes[j];
- if (c != LABEL_REF
- && c != SYMBOL_REF
- && c != CONST_INT
- && c != CONST_DOUBLE
- && c != CONST
- && c != HIGH)
- allows_non_const = 1;
-
- if (c != REG
- && c != SUBREG
- && c != MEM
- && c != CONCAT
- && c != PARALLEL
- && c != STRICT_LOW_PART)
- allows_non_lvalue = 1;
- }
- }
- else
- {
-#ifdef PREDICATE_CODES
- /* If the port has a list of the predicates it uses but
- omits one, warn. */
- message_with_line (pattern_lineno,
- "warning: `%s' not in PREDICATE_CODES",
- pred_name);
-#endif
- }
-
- for (i = 0; i < NUM_SPECIAL_MODE_PREDS; ++i)
- if (strcmp (pred_name, special_mode_pred_table[i]) == 0)
- {
- special_mode_pred = 1;
- break;
- }
+ 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 constraints0 = XSTR (pattern, 2)[0];
-
- /* 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. */
- if (GET_CODE (insn) == DEFINE_EXPAND
- || GET_CODE (insn) == DEFINE_SPLIT
- || GET_CODE (insn) == DEFINE_PEEPHOLE2)
+ const char *constraints = XSTR (pattern, 2);
+ const char constraints0 = constraints[0];
+
+ if (!constraints_supported_in_insn_p (info->def))
{
if (constraints0)
- message_with_line (pattern_lineno,
- "warning: constraints not supported in %s",
- rtx_name[GET_CODE (insn)]);
+ {
+ 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. */
/* 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 (insn, XINT (pattern, 0)))
+ && find_matching_operand (info->def,
+ XINT (pattern, 0)))
;
else
- {
- message_with_line (pattern_lineno,
- "operand %d missing in-out reload",
- XINT (pattern, 0));
- error_count++;
- }
+ 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')
{
- message_with_line (pattern_lineno,
- "operand %d missing output reload",
- XINT (pattern, 0));
- error_count++;
+ 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_name[0] != '\0'
- && allows_non_lvalue)
- {
- message_with_line (pattern_lineno,
- "warning: 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
- address_operand, since its mode is related to the mode of
- the memory not the operand. Exclude the SET_DEST of a call
- instruction, as that is a common idiom. */
+ 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 (insn) == DEFINE_INSN
- && allows_non_const
- && ! special_mode_pred
- && pred_name[0] != '\0'
- && strcmp (pred_name, "address_operand") != 0
+ && 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_with_line (pattern_lineno,
- "warning: operand %d missing mode?",
- XINT (pattern, 0));
- }
+ message_at (info->loc, "warning: operand %d missing mode?",
+ XINT (pattern, 0));
return;
}
case SET:
{
- enum machine_mode dmode, smode;
+ machine_mode dmode, smode;
rtx dest, src;
dest = SET_DEST (pattern);
if (GET_CODE (dest) == MATCH_DUP
|| GET_CODE (dest) == MATCH_OP_DUP
|| GET_CODE (dest) == MATCH_PAR_DUP)
- dest = find_operand (insn, XINT (dest, 0), NULL);
+ 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 (insn, XINT (src, 0), NULL);
+ src = find_operand (info->def, XINT (src, 0), NULL);
dmode = GET_MODE (dest);
smode = GET_MODE (src);
- /* The mode of an ADDRESS_OPERAND is the mode of the memory
- reference, not the mode of the address. */
- if (GET_CODE (src) == MATCH_OPERAND
- && ! strcmp (XSTR (src, 1), "address_operand"))
+ /* 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)
- {
- message_with_line (pattern_lineno,
- "mode mismatch in set: %smode vs %smode",
- GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
- error_count++;
- }
+ 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. */
&& GET_CODE (dest) != CC0
&& GET_CODE (src) != PC
&& GET_CODE (src) != CC0
- && GET_CODE (src) != CONST_INT)
+ && !CONST_INT_P (src)
+ && !CONST_WIDE_INT_P (src)
+ && GET_CODE (src) != CALL)
{
const char *which;
which = (dmode == VOIDmode ? "destination" : "source");
- message_with_line (pattern_lineno,
- "warning: %s missing a mode?", which);
+ message_at (info->loc, "warning: %s missing a mode?", which);
}
if (dest != SET_DEST (pattern))
- validate_pattern (dest, insn, pattern, '=');
- validate_pattern (SET_DEST (pattern), insn, pattern, '=');
- validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0);
+ 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), insn, pattern, '=');
+ validate_pattern (SET_DEST (pattern), info, pattern, '=');
return;
case ZERO_EXTRACT:
- validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
- validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0);
- validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0);
+ 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), insn, set, set ? '+' : 0);
+ 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)
{
- message_with_line (pattern_lineno,
- "operand to label_ref %smode not VOIDmode",
- GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
- error_count++;
+ 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 = 1;
+ unsigned int nelems;
+ if (VECTOR_MODE_P (mode)
+ && !GET_MODE_NUNITS (mode).is_constant (&expected))
+ error_at (info->loc,
+ "vec_select with variable-sized mode %s",
+ GET_MODE_NAME (mode));
+ else 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)
+ && GET_MODE_NUNITS (imode).is_constant (&nelems))
+ {
+ 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;
switch (fmt[i])
{
case 'e': case 'u':
- validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0);
+ 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), insn, NULL_RTX, 0);
+ validate_pattern (XVECEXP (pattern, i, j), info, NULL_RTX, 0);
break;
- case 'i': case 'w': case '0': case 's':
+ case 'r': case 'p': case 'i': case 'w': case '0': case 's':
break;
default:
- abort ();
+ gcc_unreachable ();
}
}
}
+\f
+/* 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>
+class list_head
+{
+public:
+ /* A range of linked items. */
+ class range
+ {
+ public:
+ 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 chain of nodes to verify that an rtl expression matches
- PATTERN.
-
- LAST is a pointer to the listhead in the previous node in the chain (or
- in the calling function, for the first node).
+/* Create a range [START_IN, START_IN]. */
- POSITION is the string representing the current position in the insn.
+template <typename T>
+list_head <T>::range::range (T *start_in) : start (start_in), end (start_in) {}
- INSN_TYPE is the type of insn for which we are emitting code.
+/* Create a range [START_IN, END_IN], linked by next and prev fields. */
- A pointer to the final node in the chain is returned. */
+template <typename T>
+list_head <T>::range::range (T *start_in, T *end_in)
+ : start (start_in), end (end_in) {}
-static struct decision *
-add_to_sequence (rtx pattern, struct decision_head *last, const char *position,
- enum routine_type insn_type, int top)
+template <typename T>
+void
+list_head <T>::range::set_parent (list_head <T> *owner)
{
- RTX_CODE code;
- struct decision *this, *sub;
- struct decision_test *test;
- struct decision_test **place;
- char *subpos;
- size_t i;
- const char *fmt;
- int depth = strlen (position);
- int len;
- enum machine_mode mode;
+ for (T *item = start; item != end; item = item->next)
+ item->set_parent (owner);
+ end->set_parent (owner);
+}
- if (depth > max_depth)
- max_depth = depth;
+template <typename T>
+list_head <T>::list_head () : first (0), last (0) {}
- subpos = xmalloc (depth + 2);
- strcpy (subpos, position);
- subpos[depth + 1] = 0;
+/* Add R to the end of the list. */
- sub = this = new_decision (position, last);
- place = &this->tests;
+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);
+}
- restart:
- mode = GET_MODE (pattern);
- code = GET_CODE (pattern);
+/* Remove R from the list. R remains valid and can be inserted into
+ other lists. */
- switch (code)
- {
- case PARALLEL:
- /* Toplevel peephole pattern. */
- if (insn_type == PEEPHOLE2 && top)
- {
- /* We don't need the node we just created -- unlink it. */
- last->first = last->last = NULL;
+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;
+}
- for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
- {
- /* Which insn we're looking at is represented by A-Z. We don't
- ever use 'A', however; it is always implied. */
+/* Replace OLDR with NEWR. OLDR remains valid and can be inserted into
+ other lists. */
- subpos[depth] = (i > 0 ? 'A' + i : 0);
- sub = add_to_sequence (XVECEXP (pattern, 0, i),
- last, subpos, insn_type, 0);
- last = &sub->success;
- }
- goto ret;
- }
+template <typename T>
+void
+list_head <T>::replace (range oldr, range newr)
+{
+ newr.start->prev = oldr.start->prev;
+ newr.end->next = oldr.end->next;
- /* Else nothing special. */
- break;
+ oldr.start->prev = 0;
+ oldr.end->next = 0;
+ oldr.set_parent (0);
- case MATCH_PARALLEL:
- /* The explicit patterns within a match_parallel enforce a minimum
- length on the vector. The match_parallel predicate may allow
- for more elements. We do need to check for this minimum here
- or the code generated to match the internals may reference data
- beyond the end of the vector. */
- test = new_decision_test (DT_veclen_ge, &place);
- test->u.veclen = XVECLEN (pattern, 2);
- /* Fall through. */
+ 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);
+}
- case MATCH_OPERAND:
- case MATCH_SCRATCH:
- case MATCH_OPERATOR:
- {
- const char *pred_name;
- RTX_CODE was_code = code;
- int allows_const_int = 1;
+/* Empty the list and return the previous contents as a range that can
+ be inserted into other lists. */
- if (code == MATCH_SCRATCH)
- {
- pred_name = "scratch_operand";
- code = UNKNOWN;
- }
- else
- {
- pred_name = XSTR (pattern, 1);
- if (code == MATCH_PARALLEL)
- code = PARALLEL;
- else
- code = UNKNOWN;
- }
+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 (pred_name[0] != 0)
- {
- test = new_decision_test (DT_pred, &place);
- test->u.pred.name = pred_name;
- test->u.pred.mode = mode;
-
- /* See if we know about this predicate and save its number.
- If we do, and it only accepts one code, note that fact.
-
- If we know that the predicate does not allow CONST_INT,
- we know that the only way the predicate can match is if
- the modes match (here we use the kludge of relying on the
- fact that "address_operand" accepts CONST_INT; otherwise,
- it would have to be a special case), so we can test the
- mode (but we need not). This fact should considerably
- simplify the generated code. */
-
- for (i = 0; i < NUM_KNOWN_PREDS; i++)
- if (! strcmp (preds[i].name, pred_name))
- break;
+/* If the list contains a single item, return that item, otherwise return
+ null. */
- if (i < NUM_KNOWN_PREDS)
- {
- int j;
+template <typename T>
+T *
+list_head <T>::singleton () const
+{
+ return first == last ? first : 0;
+}
+\f
+class state;
- test->u.pred.index = i;
+/* Describes a possible successful return from a routine. */
+struct acceptance_type
+{
+ /* The type of routine we're returning from. */
+ routine_type type : 16;
- if (preds[i].codes[1] == 0 && code == UNKNOWN)
- code = preds[i].codes[0];
+ /* 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.
- allows_const_int = 0;
- for (j = 0; preds[i].codes[j] != 0; j++)
- if (preds[i].codes[j] == CONST_INT)
- {
- allows_const_int = 1;
- break;
- }
- }
- else
- test->u.pred.index = -1;
- }
+ False if this structure presents a full match. */
+ unsigned int partial_p : 1;
- /* Can't enforce a mode if we allow const_int. */
- if (allows_const_int)
- mode = VOIDmode;
+ union
+ {
+ /* If PARTIAL_P, this is the number of the subroutine to call. */
+ int subroutine_id;
- /* Accept the operand, ie. record it in `operands'. */
- test = new_decision_test (DT_accept_op, &place);
- test->u.opno = XINT (pattern, 0);
+ /* 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;
+};
- if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
- {
- char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
- for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
- {
- subpos[depth] = i + base;
- sub = add_to_sequence (XVECEXP (pattern, 2, i),
- &sub->success, subpos, insn_type, 0);
- }
- }
- goto fini;
- }
+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;
+}
- case MATCH_OP_DUP:
- code = UNKNOWN;
+bool
+operator != (const acceptance_type &a, const acceptance_type &b)
+{
+ return !operator == (a, b);
+}
- test = new_decision_test (DT_dup, &place);
- test->u.dup = XINT (pattern, 0);
+/* Represents a parameter to a pattern routine. */
+class parameter
+{
+public:
+ /* The C type of parameter. */
+ enum type_enum {
+ /* Represents an invalid parameter. */
+ UNSET,
- test = new_decision_test (DT_accept_op, &place);
- test->u.opno = XINT (pattern, 0);
+ /* A machine_mode parameter. */
+ MODE,
- for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
- {
- subpos[depth] = i + '0';
- sub = add_to_sequence (XVECEXP (pattern, 1, i),
- &sub->success, subpos, insn_type, 0);
- }
- goto fini;
+ /* An rtx_code parameter. */
+ CODE,
- case MATCH_DUP:
- case MATCH_PAR_DUP:
- code = UNKNOWN;
+ /* An int parameter. */
+ INT,
- test = new_decision_test (DT_dup, &place);
- test->u.dup = XINT (pattern, 0);
- goto fini;
+ /* An unsigned int parameter. */
+ UINT,
- case ADDRESS:
- pattern = XEXP (pattern, 0);
- goto restart;
+ /* A HOST_WIDE_INT parameter. */
+ WIDE_INT
+ };
- default:
- break;
- }
+ parameter ();
+ parameter (type_enum, bool, uint64_t);
- fmt = GET_RTX_FORMAT (code);
- len = GET_RTX_LENGTH (code);
+ /* The type of the parameter. */
+ type_enum type;
- /* Do tests against the current node first. */
- for (i = 0; i < (size_t) len; i++)
- {
- if (fmt[i] == 'i')
- {
- if (i == 0)
- {
- test = new_decision_test (DT_elt_zero_int, &place);
- test->u.intval = XINT (pattern, i);
- }
- else if (i == 1)
- {
- test = new_decision_test (DT_elt_one_int, &place);
- test->u.intval = XINT (pattern, i);
- }
- else
- abort ();
- }
- else if (fmt[i] == 'w')
- {
- /* If this value actually fits in an int, we can use a switch
- statement here, so indicate that. */
- enum decision_type type
- = ((int) XWINT (pattern, i) == XWINT (pattern, i))
- ? DT_elt_zero_wide_safe : DT_elt_zero_wide;
+ /* True if the value passed is variable, false if it is constant. */
+ bool is_param;
- if (i != 0)
- abort ();
+ /* 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;
+};
- test = new_decision_test (type, &place);
- test->u.intval = XWINT (pattern, i);
- }
- else if (fmt[i] == 'E')
- {
- if (i != 0)
- abort ();
+parameter::parameter ()
+ : type (UNSET), is_param (false), value (0) {}
- test = new_decision_test (DT_veclen, &place);
- test->u.veclen = XVECLEN (pattern, i);
- }
- }
+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) {}
- /* Now test our sub-patterns. */
- for (i = 0; i < (size_t) len; i++)
- {
- switch (fmt[i])
- {
- case 'e': case 'u':
- subpos[depth] = '0' + i;
- sub = add_to_sequence (XEXP (pattern, i), &sub->success,
- subpos, insn_type, 0);
- break;
+bool
+operator == (const parameter ¶m1, const parameter ¶m2)
+{
+ return (param1.type == param2.type
+ && param1.is_param == param2.is_param
+ && param1.value == param2.value);
+}
- case 'E':
- {
- int j;
- for (j = 0; j < XVECLEN (pattern, i); j++)
- {
- subpos[depth] = 'a' + j;
- sub = add_to_sequence (XVECEXP (pattern, i, j),
- &sub->success, subpos, insn_type, 0);
- }
- break;
- }
+bool
+operator != (const parameter ¶m1, const parameter ¶m2)
+{
+ return !operator == (param1, param2);
+}
- case 'i': case 'w':
- /* Handled above. */
- break;
- case '0':
- break;
+/* 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. */
+class pattern_routine
+{
+public:
+ /* The state that implements the pattern. */
+ state *s;
- default:
- abort ();
- }
- }
+ /* 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;
- fini:
- /* Insert nodes testing mode and code, if they're still relevant,
- before any of the nodes we may have added above. */
- if (code != UNKNOWN)
- {
- place = &this->tests;
- test = new_decision_test (DT_code, &place);
- test->u.code = code;
- }
+ /* A unique identifier for the routine. */
+ unsigned int pattern_id;
- if (mode != VOIDmode)
- {
- place = &this->tests;
- test = new_decision_test (DT_mode, &place);
- test->u.mode = mode;
- }
+ /* True if the routine takes pnum_clobbers as argument. */
+ bool pnum_clobbers_p;
- /* If we didn't insert any tests or accept nodes, hork. */
- if (this->tests == NULL)
- abort ();
+ /* True if the routine takes the enclosing instruction as argument. */
+ bool insn_p;
- ret:
- free (subpos);
- return sub;
-}
-\f
-/* A subroutine of maybe_both_true; examines only one test.
- Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
+ /* The types of the other parameters to the routine, if any. */
+ auto_vec <parameter::type_enum, MAX_PATTERN_PARAMS> param_types;
+};
-static int
-maybe_both_true_2 (struct decision_test *d1, struct decision_test *d2)
+/* All defined patterns. */
+static vec <pattern_routine *> patterns;
+
+/* Represents one use of a pattern routine. */
+class pattern_use
{
- if (d1->type == d2->type)
- {
- switch (d1->type)
- {
- case DT_mode:
- return d1->u.mode == d2->u.mode;
+public:
+ /* The pattern routine to use. */
+ pattern_routine *routine;
- case DT_code:
- return d1->u.code == d2->u.code;
+ /* The values to pass as parameters. This vector has the same length
+ as ROUTINE->PARAM_TYPES. */
+ auto_vec <parameter, MAX_PATTERN_PARAMS> params;
+};
- case DT_veclen:
- return d1->u.veclen == d2->u.veclen;
-
- case DT_elt_zero_int:
- case DT_elt_one_int:
- case DT_elt_zero_wide:
- case DT_elt_zero_wide_safe:
- return d1->u.intval == d2->u.intval;
-
- default:
- break;
- }
- }
-
- /* If either has a predicate that we know something about, set
- things up so that D1 is the one that always has a known
- predicate. Then see if they have any codes in common. */
-
- if (d1->type == DT_pred || d2->type == DT_pred)
- {
- if (d2->type == DT_pred)
- {
- struct decision_test *tmp;
- tmp = d1, d1 = d2, d2 = tmp;
- }
+/* Represents a test performed by a decision. */
+class rtx_test
+{
+public:
+ rtx_test ();
- /* If D2 tests a mode, see if it matches D1. */
- if (d1->u.pred.mode != VOIDmode)
- {
- if (d2->type == DT_mode)
- {
- if (d1->u.pred.mode != d2->u.mode
- /* The mode of an address_operand predicate is the
- mode of the memory, not the operand. It can only
- be used for testing the predicate, so we must
- ignore it here. */
- && strcmp (d1->u.pred.name, "address_operand") != 0)
- return 0;
- }
- /* Don't check two predicate modes here, because if both predicates
- accept CONST_INT, then both can still be true even if the modes
- are different. If they don't accept CONST_INT, there will be a
- separate DT_mode that will make maybe_both_true_1 return 0. */
- }
+ /* 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".
- if (d1->u.pred.index >= 0)
- {
- /* If D2 tests a code, see if it is in the list of valid
- codes for D1's predicate. */
- if (d2->type == DT_code)
- {
- const RTX_CODE *c = &preds[d1->u.pred.index].codes[0];
- while (*c != 0)
- {
- if (*c == d2->u.code)
- break;
- ++c;
- }
- if (*c == 0)
- return 0;
- }
+ The order of the enum isn't important. */
+ enum kind_enum {
+ /* Check GET_CODE (X) == LABEL. */
+ CODE,
- /* Otherwise see if the predicates have any codes in common. */
- else if (d2->type == DT_pred && d2->u.pred.index >= 0)
- {
- const RTX_CODE *c1 = &preds[d1->u.pred.index].codes[0];
- int common = 0;
+ /* Check GET_MODE (X) == LABEL. */
+ MODE,
- while (*c1 != 0 && !common)
- {
- const RTX_CODE *c2 = &preds[d2->u.pred.index].codes[0];
- while (*c2 != 0 && !common)
- {
- common = (*c1 == *c2);
- ++c2;
- }
- ++c1;
- }
+ /* Check REGNO (X) == LABEL. */
+ REGNO_FIELD,
- if (!common)
- return 0;
- }
- }
- }
+ /* Check known_eq (SUBREG_BYTE (X), LABEL). */
+ SUBREG_FIELD,
- /* Tests vs veclen may be known when strict equality is involved. */
- if (d1->type == DT_veclen && d2->type == DT_veclen_ge)
- return d1->u.veclen >= d2->u.veclen;
- if (d1->type == DT_veclen_ge && d2->type == DT_veclen)
- return d2->u.veclen >= d1->u.veclen;
+ /* Check XINT (X, u.opno) == LABEL. */
+ INT_FIELD,
- return -1;
-}
+ /* Check XWINT (X, u.opno) == LABEL. */
+ WIDE_INT_FIELD,
-/* A subroutine of maybe_both_true; examines all the tests for a given node.
- Returns > 0 for "definitely both true" and < 0 for "maybe both true". */
+ /* Check XVECLEN (X, 0) == LABEL. */
+ VECLEN,
-static int
-maybe_both_true_1 (struct decision_test *d1, struct decision_test *d2)
-{
- struct decision_test *t1, *t2;
+ /* Check peep2_current_count >= u.min_len. */
+ PEEP2_COUNT,
- /* A match_operand with no predicate can match anything. Recognize
- this by the existence of a lone DT_accept_op test. */
- if (d1->type == DT_accept_op || d2->type == DT_accept_op)
- return 1;
+ /* Check XVECLEN (X, 0) >= u.min_len. */
+ VECLEN_GE,
- /* Eliminate pairs of tests while they can exactly match. */
- while (d1 && d2 && d1->type == d2->type)
- {
- if (maybe_both_true_2 (d1, d2) == 0)
- return 0;
- d1 = d1->next, d2 = d2->next;
- }
+ /* Check whether X is a cached const_int with value u.integer. */
+ SAVED_CONST_INT,
- /* After that, consider all pairs. */
- for (t1 = d1; t1 ; t1 = t1->next)
- for (t2 = d2; t2 ; t2 = t2->next)
- if (maybe_both_true_2 (t1, t2) == 0)
- return 0;
+ /* Check u.predicate.data (X, u.predicate.mode). */
+ PREDICATE,
- return -1;
-}
+ /* Check rtx_equal_p (X, operands[u.opno]). */
+ DUPLICATE,
-/* Return 0 if we can prove that there is no RTL that can match both
- D1 and D2. Otherwise, return 1 (it may be that there is an RTL that
- can match both or just that we couldn't prove there wasn't such an RTL).
+ /* Check whether X matches pattern u.pattern. */
+ PATTERN,
- TOPLEVEL is nonzero if we are to only look at the top level and not
- recursively descend. */
+ /* Check whether pnum_clobbers is nonnull (RECOG only). */
+ HAVE_NUM_CLOBBERS,
-static int
-maybe_both_true (struct decision *d1, struct decision *d2,
- int toplevel)
-{
- struct decision *p1, *p2;
- int cmp;
+ /* Check whether general C test u.string holds. In general the condition
+ needs access to "insn" and the full operand list. */
+ C_TEST,
- /* Don't compare strings on the different positions in insn. Doing so
- is incorrect and results in false matches from constructs like
+ /* Execute operands[u.opno] = X. (Always succeeds.) */
+ SET_OP,
- [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
- (subreg:HI (match_operand:SI "register_operand" "r") 0))]
- vs
- [(set (match_operand:HI "register_operand" "r")
- (match_operand:HI "register_operand" "r"))]
+ /* Accept u.acceptance. Always succeeds for SUBPATTERN, RECOG and SPLIT.
+ May fail for PEEPHOLE2 if the define_peephole2 C code executes FAIL. */
+ ACCEPT
+ };
- If we are presented with such, we are recursing through the remainder
- of a node's success nodes (from the loop at the end of this function).
- Skip forward until we come to a position that matches.
+ /* 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;
- Due to the way position strings are constructed, we know that iterating
- forward from the lexically lower position (e.g. "00") will run into
- the lexically higher position (e.g. "1") and not the other way around.
- This saves a bit of effort. */
+ /* Which element of operands[] already contains POS, or -1 if no element
+ is known to hold POS. */
+ int pos_operand;
- cmp = strcmp (d1->position, d2->position);
- if (cmp != 0)
+ /* The type of test and its parameters, as described above. */
+ kind_enum kind;
+ union
+ {
+ int opno;
+ int min_len;
+ struct
{
- if (toplevel)
- abort ();
-
- /* If the d2->position was lexically lower, swap. */
- if (cmp > 0)
- p1 = d1, d1 = d2, d2 = p1;
-
- if (d1->success.first == 0)
- return 1;
- for (p1 = d1->success.first; p1; p1 = p1->next)
- if (maybe_both_true (p1, d2, 0))
- return 1;
-
- return 0;
- }
-
- /* Test the current level. */
- cmp = maybe_both_true_1 (d1->tests, d2->tests);
- if (cmp >= 0)
- return cmp;
+ 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;
- /* We can't prove that D1 and D2 cannot both be true. If we are only
- to check the top level, return 1. Otherwise, see if we can prove
- that all choices in both successors are mutually exclusive. If
- either does not have any successors, we can't prove they can't both
- be true. */
+ static rtx_test code (position *);
+ static rtx_test mode (position *);
+ static rtx_test regno_field (position *);
+ static rtx_test subreg_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);
+};
- if (toplevel || d1->success.first == 0 || d2->success.first == 0)
- return 1;
+rtx_test::rtx_test () {}
- for (p1 = d1->success.first; p1; p1 = p1->next)
- for (p2 = d2->success.first; p2; p2 = p2->next)
- if (maybe_both_true (p1, p2, 0))
- return 1;
+rtx_test::rtx_test (position *pos_in, kind_enum kind_in)
+ : pos (pos_in), pos_operand (-1), kind (kind_in) {}
- return 0;
+rtx_test
+rtx_test::code (position *pos)
+{
+ return rtx_test (pos, rtx_test::CODE);
}
-/* A subroutine of nodes_identical. Examine two tests for equivalence. */
-
-static int
-nodes_identical_1 (struct decision_test *d1, struct decision_test *d2)
+rtx_test
+rtx_test::mode (position *pos)
{
- switch (d1->type)
- {
- case DT_mode:
- return d1->u.mode == d2->u.mode;
-
- case DT_code:
- return d1->u.code == d2->u.code;
+ return rtx_test (pos, rtx_test::MODE);
+}
- case DT_pred:
- return (d1->u.pred.mode == d2->u.pred.mode
- && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
+rtx_test
+rtx_test::regno_field (position *pos)
+{
+ rtx_test res (pos, rtx_test::REGNO_FIELD);
+ return res;
+}
- case DT_c_test:
- return strcmp (d1->u.c_test, d2->u.c_test) == 0;
+rtx_test
+rtx_test::subreg_field (position *pos)
+{
+ rtx_test res (pos, rtx_test::SUBREG_FIELD);
+ return res;
+}
- case DT_veclen:
- case DT_veclen_ge:
- return d1->u.veclen == d2->u.veclen;
+rtx_test
+rtx_test::int_field (position *pos, int opno)
+{
+ rtx_test res (pos, rtx_test::INT_FIELD);
+ res.u.opno = opno;
+ return res;
+}
- case DT_dup:
- return d1->u.dup == d2->u.dup;
+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;
+}
- case DT_elt_zero_int:
- case DT_elt_one_int:
- case DT_elt_zero_wide:
- case DT_elt_zero_wide_safe:
- return d1->u.intval == d2->u.intval;
+rtx_test
+rtx_test::veclen (position *pos)
+{
+ return rtx_test (pos, rtx_test::VECLEN);
+}
- case DT_accept_op:
- return d1->u.opno == d2->u.opno;
+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;
+}
- case DT_accept_insn:
- /* Differences will be handled in merge_accept_insn. */
- return 1;
+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;
+}
- default:
- abort ();
- }
+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;
}
-/* True iff the two nodes are identical (on one level only). Due
- to the way these lists are constructed, we shouldn't have to
- consider different orderings on the tests. */
+rtx_test
+rtx_test::duplicate (position *pos, int opno)
+{
+ rtx_test res (pos, rtx_test::DUPLICATE);
+ res.u.opno = opno;
+ return res;
+}
-static int
-nodes_identical (struct decision *d1, struct decision *d2)
+rtx_test
+rtx_test::pattern (position *pos, pattern_use *pattern)
{
- struct decision_test *t1, *t2;
+ rtx_test res (pos, rtx_test::PATTERN);
+ res.u.pattern = pattern;
+ return res;
+}
- for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
- {
- if (t1->type != t2->type)
- return 0;
- if (! nodes_identical_1 (t1, t2))
- return 0;
- }
+rtx_test
+rtx_test::have_num_clobbers ()
+{
+ return rtx_test (0, rtx_test::HAVE_NUM_CLOBBERS);
+}
- /* For success, they should now both be null. */
- if (t1 != t2)
- return 0;
+rtx_test
+rtx_test::c_test (const char *string)
+{
+ rtx_test res (0, rtx_test::C_TEST);
+ res.u.string = string;
+ return res;
+}
- /* Check that their subnodes are at the same position, as any one set
- of sibling decisions must be at the same position. Allowing this
- requires complications to find_afterward and when change_state is
- invoked. */
- if (d1->success.first
- && d2->success.first
- && strcmp (d1->success.first->position, d2->success.first->position))
- return 0;
+rtx_test
+rtx_test::set_op (position *pos, int opno)
+{
+ rtx_test res (pos, rtx_test::SET_OP);
+ res.u.opno = opno;
+ return res;
+}
- return 1;
+rtx_test
+rtx_test::accept (const acceptance_type &acceptance)
+{
+ rtx_test res (0, rtx_test::ACCEPT);
+ res.u.acceptance = acceptance;
+ return res;
}
-/* A subroutine of merge_trees; given two nodes that have been declared
- identical, cope with two insn accept states. If they differ in the
- number of clobbers, then the conflict was created by make_insn_sequence
- and we can drop the with-clobbers version on the floor. If both
- nodes have no additional clobbers, we have found an ambiguity in the
- source machine description. */
+/* Return true if the test represents an unconditionally successful match. */
-static void
-merge_accept_insn (struct decision *oldd, struct decision *addd)
+bool
+rtx_test::terminal_p () const
{
- struct decision_test *old, *add;
-
- for (old = oldd->tests; old; old = old->next)
- if (old->type == DT_accept_insn)
- break;
- if (old == NULL)
- return;
+ return kind == rtx_test::ACCEPT && u.acceptance.type != PEEPHOLE2;
+}
- for (add = addd->tests; add; add = add->next)
- if (add->type == DT_accept_insn)
- break;
- if (add == NULL)
- return;
+/* Return true if the test is a boolean that is always true. */
- /* If one node is for a normal insn and the second is for the base
- insn with clobbers stripped off, the second node should be ignored. */
+bool
+rtx_test::single_outcome_p () const
+{
+ return terminal_p () || kind == rtx_test::SET_OP;
+}
- if (old->u.insn.num_clobbers_to_add == 0
- && add->u.insn.num_clobbers_to_add > 0)
- {
- /* Nothing to do here. */
- }
- else if (old->u.insn.num_clobbers_to_add > 0
- && add->u.insn.num_clobbers_to_add == 0)
- {
- /* In this case, replace OLD with ADD. */
- old->u.insn = add->u.insn;
- }
- else
+bool
+operator == (const rtx_test &a, const rtx_test &b)
+{
+ if (a.pos != b.pos || a.kind != b.kind)
+ return false;
+ switch (a.kind)
{
- message_with_line (add->u.insn.lineno, "`%s' matches `%s'",
- get_insn_name (add->u.insn.code_number),
- get_insn_name (old->u.insn.code_number));
- message_with_line (old->u.insn.lineno, "previous definition of `%s'",
- get_insn_name (old->u.insn.code_number));
- error_count++;
+ case rtx_test::CODE:
+ case rtx_test::MODE:
+ case rtx_test::REGNO_FIELD:
+ case rtx_test::SUBREG_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 ();
}
-/* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */
-
-static void
-merge_trees (struct decision_head *oldh, struct decision_head *addh)
+bool
+operator != (const rtx_test &a, const rtx_test &b)
{
- struct decision *next, *add;
-
- if (addh->first == 0)
- return;
- if (oldh->first == 0)
- {
- *oldh = *addh;
- return;
- }
+ return !operator == (a, b);
+}
- /* Trying to merge bits at different positions isn't possible. */
- if (strcmp (oldh->first->position, addh->first->position))
- abort ();
+/* A simple set of transition labels. Most transitions have a singleton
+ label, so try to make that case as efficient as possible. */
+class int_set : public auto_vec <uint64_t, 1>
+{
+public:
+ typedef uint64_t *iterator;
- for (add = addh->first; add ; add = next)
- {
- struct decision *old, *insert_before = NULL;
+ int_set ();
+ int_set (uint64_t);
+ int_set (const int_set &);
- next = add->next;
+ int_set &operator = (const int_set &);
- /* The semantics of pattern matching state that the tests are
- done in the order given in the MD file so that if an insn
- matches two patterns, the first one will be used. However,
- in practice, most, if not all, patterns are unambiguous so
- that their order is independent. In that case, we can merge
- identical tests and group all similar modes and codes together.
+ iterator begin ();
+ iterator end ();
+};
- Scan starting from the end of OLDH until we reach a point
- where we reach the head of the list or where we pass a
- pattern that could also be true if NEW is true. If we find
- an identical pattern, we can merge them. Also, record the
- last node that tests the same code and mode and the last one
- that tests just the same mode.
+int_set::int_set () : auto_vec<uint64_t, 1> () {}
- If we have no match, place NEW after the closest match we found. */
+int_set::int_set (uint64_t label) :
+ auto_vec<uint64_t, 1> ()
+{
+ safe_push (label);
+}
- for (old = oldh->last; old; old = old->prev)
- {
- if (nodes_identical (old, add))
- {
- merge_accept_insn (old, add);
- merge_trees (&old->success, &add->success);
- goto merged_nodes;
- }
+int_set::int_set (const int_set &other) :
+ auto_vec<uint64_t, 1> ()
+{
+ safe_splice (other);
+}
- if (maybe_both_true (old, add, 0))
- break;
+int_set &
+int_set::operator = (const int_set &other)
+{
+ truncate (0);
+ safe_splice (other);
+ return *this;
+}
- /* Insert the nodes in DT test type order, which is roughly
- how expensive/important the test is. Given that the tests
- are also ordered within the list, examining the first is
- sufficient. */
- if ((int) add->tests->type < (int) old->tests->type)
- insert_before = old;
- }
+int_set::iterator
+int_set::begin ()
+{
+ return address ();
+}
- if (insert_before == NULL)
- {
- add->next = NULL;
- add->prev = oldh->last;
- oldh->last->next = add;
- oldh->last = add;
- }
- else
- {
- if ((add->prev = insert_before->prev) != NULL)
- add->prev->next = add;
- else
- oldh->first = add;
- add->next = insert_before;
- insert_before->prev = add;
- }
+int_set::iterator
+int_set::end ()
+{
+ return address () + length ();
+}
- merged_nodes:;
- }
+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;
}
-\f
-/* Walk the tree looking for sub-nodes that perform common tests.
- Factor out the common test into a new node. This enables us
- (depending on the test type) to emit switch statements later. */
-static void
-factor_tests (struct decision_head *head)
+bool
+operator != (const int_set &a, const int_set &b)
{
- struct decision *first, *next;
+ return !operator == (a, b);
+}
- for (first = head->first; first && first->next; first = next)
- {
- enum decision_type type;
- struct decision *new, *old_last;
+class decision;
- type = first->tests->type;
- next = first->next;
+/* Represents a transition between states, dependent on the result of
+ a test T. */
+class transition
+{
+public:
+ 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;
+};
- /* Want at least two compatible sequential nodes. */
- if (next->tests->type != type)
- continue;
+/* 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. */
+class decision : public list_head <transition>
+{
+public:
+ decision (const rtx_test &);
- /* Don't want all node types, just those we can turn into
- switch statements. */
- if (type != DT_mode
- && type != DT_code
- && type != DT_veclen
- && type != DT_elt_zero_int
- && type != DT_elt_one_int
- && type != DT_elt_zero_wide_safe)
- continue;
+ void set_parent (list_head <decision> *s);
+ bool if_statement_p (uint64_t * = 0) const;
- /* If we'd been performing more than one test, create a new node
- below our first test. */
- if (first->tests->next != NULL)
- {
- new = new_decision (first->position, &first->success);
- new->tests = first->tests->next;
- first->tests->next = NULL;
- }
+ /* The state to which this decision belongs. */
+ state *s;
- /* Crop the node tree off after our first test. */
- first->next = NULL;
- old_last = head->last;
- head->last = first;
+ /* Links to other decisions in the same state. */
+ decision *prev, *next;
- /* For each compatible test, adjust to perform only one test in
- the top level node, then merge the node back into the tree. */
- do
- {
- struct decision_head h;
+ /* The test to perform. */
+ rtx_test test;
+};
- if (next->tests->next != NULL)
- {
- new = new_decision (next->position, &next->success);
- new->tests = next->tests->next;
- next->tests->next = NULL;
- }
- new = next;
- next = next->next;
- new->next = NULL;
- h.first = h.last = new;
+/* 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. */
+class state : public list_head <decision>
+{
+public:
+ void set_parent (list_head <state> *) {}
+};
- merge_trees (head, &h);
- }
- while (next && next->tests->type == type);
+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) {}
- /* After we run out of compatible tests, graft the remaining nodes
- back onto the tree. */
- if (next)
- {
- next->prev = head->last;
- head->last->next = next;
- head->last = old_last;
- }
- }
+/* Set the source decision of the transition. */
- /* Recurse. */
- for (first = head->first; first; first = first->next)
- factor_tests (&first->success);
+void
+transition::set_parent (list_head <transition> *from_in)
+{
+ from = static_cast <decision *> (from_in);
}
-/* After factoring, try to simplify the tests on any one node.
- Tests that are useful for switch statements are recognizable
- by having only a single test on a node -- we'll be manipulating
- nodes with multiple tests:
+decision::decision (const rtx_test &test_in)
+ : prev (0), next (0), test (test_in) {}
- If we have mode tests or code tests that are redundant with
- predicates, remove them. */
+/* Set the state to which this decision belongs. */
-static void
-simplify_tests (struct decision_head *head)
+void
+decision::set_parent (list_head <decision> *s_in)
{
- struct decision *tree;
-
- for (tree = head->first; tree; tree = tree->next)
- {
- struct decision_test *a, *b;
-
- a = tree->tests;
- b = a->next;
- if (b == NULL)
- continue;
-
- /* Find a predicate node. */
- while (b && b->type != DT_pred)
- b = b->next;
- if (b)
- {
- /* Due to how these tests are constructed, we don't even need
- to check that the mode and code are compatible -- they were
- generated from the predicate in the first place. */
- while (a->type == DT_mode || a->type == DT_code)
- a = a->next;
- tree->tests = a;
- }
- }
-
- /* Recurse. */
- for (tree = head->first; tree; tree = tree->next)
- simplify_tests (&tree->success);
+ s = static_cast <state *> (s_in);
}
-/* Count the number of subnodes of HEAD. If the number is high enough,
- make the first node in HEAD start a separate subroutine in the C code
- that is generated. */
+/* Return true if the decision has a single transition with a single label.
+ If so, return the label in *LABEL if nonnull. */
-static int
-break_out_subroutines (struct decision_head *head, int initial)
+inline bool
+decision::if_statement_p (uint64_t *label) const
{
- int size = 0;
- struct decision *sub;
-
- for (sub = head->first; sub; sub = sub->next)
- size += 1 + break_out_subroutines (&sub->success, 0);
-
- if (size > SUBROUTINE_THRESHOLD && ! initial)
+ if (singleton () && first->labels.length () == 1)
{
- head->first->subroutine_number = ++next_subroutine_number;
- size = 1;
+ if (label)
+ *label = first->labels[0];
+ return true;
}
- return size;
+ return false;
}
-/* For each node p, find the next alternative that might be true
- when p is true. */
+/* Add to FROM a decision that performs TEST and has a single transition
+ TRANS. */
static void
-find_afterward (struct decision_head *head, struct decision *real_afterward)
+add_decision (state *from, const rtx_test &test, transition *trans)
{
- struct decision *p, *q, *afterward;
-
- /* We can't propagate alternatives across subroutine boundaries.
- This is not incorrect, merely a minor optimization loss. */
-
- p = head->first;
- afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
+ decision *d = new decision (test);
+ from->push_back (d);
+ d->push_back (trans);
+}
- for ( ; p ; p = p->next)
- {
- /* Find the next node that might be true if this one fails. */
- for (q = p->next; q ; q = q->next)
- if (maybe_both_true (p, q, 1))
- break;
+/* 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. */
- /* If we reached the end of the list without finding one,
- use the incoming afterward position. */
- if (!q)
- q = afterward;
- p->afterward = q;
- if (q)
- q->need_label = 1;
- }
+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;
+}
- /* Recurse. */
- for (p = head->first; p ; p = p->next)
- if (p->success.first)
- find_afterward (&p->success, p->afterward);
+/* Insert a decision before decisions R to make them dependent on
+ TEST == LABELS. OPTIONAL says whether the new transition should be
+ optional. */
- /* When we are generating a subroutine, record the real afterward
- position in the first node where write_tree can find it, and we
- can do the right thing at the subroutine call site. */
- p = head->first;
- if (p->subroutine_number > 0)
- p->afterward = real_afterward;
+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;
}
-\f
-/* Assuming that the state of argument is denoted by OLDPOS, take whatever
- actions are necessary to move to NEWPOS. If we fail to move to the
- new state, branch to node AFTERWARD if nonzero, otherwise return.
- Failure to move to the new state can only occur if we are trying to
- match multiple insns and we try to step past the end of the stream. */
+/* Remove any optional transitions from S that turned out not to be useful. */
static void
-change_state (const char *oldpos, const char *newpos,
- struct decision *afterward, const char *indent)
+collapse_optional_decisions (state *s)
{
- int odepth = strlen (oldpos);
- int ndepth = strlen (newpos);
- int depth;
- int old_has_insn, new_has_insn;
-
- /* Pop up as many levels as necessary. */
- for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
- continue;
+ 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;
+ }
+}
- /* Hunt for the last [A-Z] in both strings. */
- for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn)
- if (ISUPPER (oldpos[old_has_insn]))
- break;
- for (new_has_insn = ndepth - 1; new_has_insn >= 0; --new_has_insn)
- if (ISUPPER (newpos[new_has_insn]))
- break;
+/* Try to squash several separate tests into simpler ones. */
- /* Go down to desired level. */
- while (depth < ndepth)
+static void
+simplify_tests (state *s)
+{
+ for (decision *d = s->first; d; d = d->next)
{
- /* It's a different insn from the first one. */
- if (ISUPPER (newpos[depth]))
- {
- /* We can only fail if we're moving down the tree. */
- if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth])
- {
- printf ("%stem = peep2_next_insn (%d);\n",
- indent, newpos[depth] - 'A');
- }
- else
+ 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))
{
- printf ("%stem = peep2_next_insn (%d);\n",
- indent, newpos[depth] - 'A');
- printf ("%sif (tem == NULL_RTX)\n", indent);
- if (afterward)
- printf ("%s goto L%d;\n", indent, afterward->number);
- else
- printf ("%s goto ret0;\n", indent);
+ 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;
}
- printf ("%sx%d = PATTERN (tem);\n", indent, depth + 1);
- }
- else if (ISLOWER (newpos[depth]))
- printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
- indent, depth + 1, depth, newpos[depth] - 'a');
- else
- printf ("%sx%d = XEXP (x%d, %c);\n",
- indent, depth + 1, depth, newpos[depth]);
- ++depth;
+ /* 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);
}
}
-\f
-/* Print the enumerator constant for CODE -- the upcase version of
- the name. */
-static void
-print_code (enum rtx_code code)
-{
- const char *p;
- for (p = GET_RTX_NAME (code); *p; p++)
- putchar (TOUPPER (*p));
-}
+/* Return true if all successful returns passing through D require the
+ condition tested by COMMON to be true.
-/* Emit code to cross an afterward link -- change state and branch. */
+ When returning true, add all transitions like COMMON in D to WHERE.
+ WHERE may contain a partial result on failure. */
-static void
-write_afterward (struct decision *start, struct decision *afterward,
- const char *indent)
+static bool
+common_test_p (decision *d, transition *common, vec <transition *> *where)
{
- if (!afterward || start->subroutine_number > 0)
- printf("%sgoto ret0;\n", indent);
- else
+ 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)
{
- change_state (start->position, afterward->position, NULL, indent);
- printf ("%sgoto L%d;\n", indent, afterward->number);
+ 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;
}
-/* Emit a HOST_WIDE_INT as an integer constant expression. We need to take
- special care to avoid "decimal constant is so large that it is unsigned"
- warnings in the resulting code. */
-
-static void
-print_host_wide_int (HOST_WIDE_INT val)
-{
- HOST_WIDE_INT min = (unsigned HOST_WIDE_INT)1 << (HOST_BITS_PER_WIDE_INT-1);
- if (val == min)
- printf ("(" HOST_WIDE_INT_PRINT_DEC_C "-1)", val + 1);
- else
- printf (HOST_WIDE_INT_PRINT_DEC_C, val);
-}
+/* Indicates that we have tested GET_CODE (X) for a particular rtx X. */
+const unsigned char TESTED_CODE = 1;
-/* Emit a switch statement, if possible, for an initial sequence of
- nodes at START. Return the first node yet untested. */
+/* Indicates that we have tested XVECLEN (X, 0) for a particular rtx X. */
+const unsigned char TESTED_VECLEN = 2;
-static struct decision *
-write_switch (struct decision *start, int depth)
+/* Represents a set of conditions that are known to hold. */
+class known_conditions
{
- struct decision *p = start;
- enum decision_type type = p->tests->type;
- struct decision *needs_label = NULL;
-
- /* If we have two or more nodes in sequence that test the same one
- thing, we may be able to use a switch statement. */
+public:
+ /* A mask of TESTED_ values for each position, indexed by the position's
+ id field. */
+ auto_vec <unsigned char> position_tests;
- if (!p->next
- || p->tests->next
- || p->next->tests->type != type
- || p->next->tests->next
- || nodes_identical_1 (p->tests, p->next->tests))
- return p;
+ /* Index N says whether operands[N] has been set. */
+ auto_vec <bool> set_operands;
- /* DT_code is special in that we can do interesting things with
- known predicates at the same time. */
- if (type == DT_code)
- {
- char codemap[NUM_RTX_CODE];
- struct decision *ret;
- RTX_CODE code;
+ /* A guranteed lower bound on the value of peep2_current_count. */
+ int peep2_count;
+};
- memset (codemap, 0, sizeof(codemap));
+/* 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. */
- printf (" switch (GET_CODE (x%d))\n {\n", depth);
- code = p->tests->u.code;
- do
+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)
{
- if (p != start && p->need_label && needs_label == NULL)
- needs_label = p;
+ case POS_PEEP2_INSN:
+ return test.pos->arg < kc->peep2_count;
- printf (" case ");
- print_code (code);
- printf (":\n goto L%d;\n", p->success.first->number);
- p->success.first->need_label = 1;
+ case POS_XEXP:
+ return kc->position_tests[test.pos->base->id] & TESTED_CODE;
- codemap[code] = 1;
- p = p->next;
+ case POS_XVECEXP0:
+ return kc->position_tests[test.pos->base->id] & TESTED_VECLEN;
}
- while (p
- && ! p->tests->next
- && p->tests->type == DT_code
- && ! codemap[code = p->tests->u.code]);
-
- /* If P is testing a predicate that we know about and we haven't
- seen any of the codes that are valid for the predicate, we can
- write a series of "case" statement, one for each possible code.
- Since we are already in a switch, these redundant tests are very
- cheap and will reduce the number of predicates called. */
-
- /* Note that while we write out cases for these predicates here,
- we don't actually write the test here, as it gets kinda messy.
- It is trivial to leave this to later by telling our caller that
- we only processed the CODE tests. */
- if (needs_label != NULL)
- ret = needs_label;
- else
- ret = p;
+ gcc_unreachable ();
+
+ case rtx_test::REGNO_FIELD:
+ case rtx_test::SUBREG_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 ();
+}
- while (p && p->tests->type == DT_pred
- && p->tests->u.pred.index >= 0)
+/* 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))
{
- const RTX_CODE *c;
-
- for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
- if (codemap[(int) *c] != 0)
- goto pred_done;
-
- for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c)
+ if (common_test_p (outer, trans, where))
{
- printf (" case ");
- print_code (*c);
- printf (":\n");
- codemap[(int) *c] = 1;
+ 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;
}
-
- printf (" goto L%d;\n", p->number);
- p->need_label = 1;
- p = p->next;
+ where->truncate (0);
}
+ }
+ return 0;
+}
- pred_done:
- /* Make the default case skip the predicates we managed to match. */
+/* 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. */
- printf (" default:\n");
- if (p != ret)
+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)
{
- if (p)
+ /* 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)
{
- printf (" goto L%d;\n", p->number);
- p->need_label = 1;
+ 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 ());
+ }
}
- else
- write_afterward (start, start->afterward, " ");
}
- else
- printf (" break;\n");
- printf (" }\n");
-
- return ret;
- }
- else if (type == DT_mode
- || type == DT_veclen
- || type == DT_elt_zero_int
- || type == DT_elt_one_int
- || type == DT_elt_zero_wide_safe)
- {
- const char *indent = "";
- /* We cast switch parameter to integer, so we must ensure that the value
- fits. */
- if (type == DT_elt_zero_wide_safe)
- {
- indent = " ";
- printf(" if ((int) XWINT (x%d, 0) == XWINT (x%d, 0))\n", depth, depth);
- }
- printf ("%s switch (", indent);
- switch (type)
+ /* 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 DT_mode:
- printf ("GET_MODE (x%d)", depth);
+ case rtx_test::CODE:
+ prev = kc->position_tests[d->test.pos->id];
+ kc->position_tests[d->test.pos->id] |= TESTED_CODE;
break;
- case DT_veclen:
- printf ("XVECLEN (x%d, 0)", depth);
- break;
- case DT_elt_zero_int:
- printf ("XINT (x%d, 0)", depth);
+
+ 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 DT_elt_one_int:
- printf ("XINT (x%d, 1)", depth);
+
+ 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 DT_elt_zero_wide_safe:
- /* Convert result of XWINT to int for portability since some C
- compilers won't do it and some will. */
- printf ("(int) XWINT (x%d, 0)", depth);
+
+ case rtx_test::PEEP2_COUNT:
+ prev = kc->peep2_count;
+ kc->peep2_count = MAX (prev, d->test.u.min_len);
break;
+
default:
- abort ();
+ break;
}
- printf (")\n%s {\n", indent);
-
- do
+ 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)
{
- /* Merge trees will not unify identical nodes if their
- sub-nodes are at different levels. Thus we must check
- for duplicate cases. */
- struct decision *q;
- for (q = start; q != p; q = q->next)
- if (nodes_identical_1 (p->tests, q->tests))
- goto case_done;
-
- if (p != start && p->need_label && needs_label == NULL)
- needs_label = p;
-
- printf ("%s case ", indent);
- switch (type)
- {
- case DT_mode:
- printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
- break;
- case DT_veclen:
- printf ("%d", p->tests->u.veclen);
- break;
- case DT_elt_zero_int:
- case DT_elt_one_int:
- case DT_elt_zero_wide:
- case DT_elt_zero_wide_safe:
- print_host_wide_int (p->tests->u.intval);
- break;
- default:
- abort ();
- }
- printf (":\n%s goto L%d;\n", indent, p->success.first->number);
- p->success.first->need_label = 1;
+ case rtx_test::CODE:
+ case rtx_test::VECLEN:
+ case rtx_test::VECLEN_GE:
+ kc->position_tests[d->test.pos->id] = prev;
+ break;
- p = p->next;
- }
- while (p && p->tests->type == type && !p->tests->next);
+ case rtx_test::SET_OP:
+ kc->set_operands[d->test.u.opno] = prev;
+ break;
- case_done:
- printf ("%s default:\n%s break;\n%s }\n",
- indent, indent, indent);
+ case rtx_test::PEEP2_COUNT:
+ kc->peep2_count = prev;
+ break;
- return needs_label != NULL ? needs_label : p;
+ default:
+ break;
+ }
}
- else
+}
+
+/* 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)
{
- /* None of the other tests are amenable. */
- return p;
+ case rtx_test::CODE:
+ return parameter::CODE;
+
+ case rtx_test::MODE:
+ return parameter::MODE;
+
+ case rtx_test::REGNO_FIELD:
+ case rtx_test::SUBREG_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 ();
}
-/* Emit code for one test. */
+/* 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
-write_cond (struct decision_test *p, int depth,
- enum routine_type subroutine_type)
+find_operand_positions (state *s, vec <int> &operand_pos)
{
- switch (p->type)
+ for (decision *d = s->first; d; d = d->next)
{
- case DT_mode:
- printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
- break;
-
- case DT_code:
- printf ("GET_CODE (x%d) == ", depth);
- print_code (p->u.code);
- break;
-
- case DT_veclen:
- printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
- break;
-
- case DT_elt_zero_int:
- printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
- break;
+ 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;
+ }
+}
- case DT_elt_one_int:
- printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
- break;
+/* Statistics about a matching routine. */
+class stats
+{
+public:
+ 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;
+};
- case DT_elt_zero_wide:
- case DT_elt_zero_wide_safe:
- printf ("XWINT (x%d, 0) == ", depth);
- print_host_wide_int (p->u.intval);
- break;
+stats::stats ()
+ : num_decisions (0), longest_path (0), longest_path_code (-1),
+ longest_backtrack (0), longest_backtrack_code (-1) {}
- case DT_const_int:
- printf ("x%d == const_int_rtx[MAX_SAVED_CONST_INT + (%d)]",
- depth, (int) p->u.intval);
- break;
+/* Return statistics about S. */
- case DT_veclen_ge:
- printf ("XVECLEN (x%d, 0) >= %d", depth, p->u.veclen);
- break;
+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;
+ }
+ }
- case DT_dup:
- printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
- break;
+ /* 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;
+ }
- case DT_pred:
- printf ("%s (x%d, %smode)", p->u.pred.name, depth,
- GET_MODE_NAME (p->u.pred.mode));
- break;
+ /* Keep a running count of the number of backtracks. */
+ if (d->prev)
+ for_s.longest_backtrack += 1;
- case DT_c_test:
- printf ("(%s)", p->u.c_test);
- break;
+ /* 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;
- case DT_accept_insn:
- switch (subroutine_type)
+ /* 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)
{
- case RECOG:
- if (p->u.insn.num_clobbers_to_add == 0)
- abort ();
- printf ("pnum_clobbers != NULL");
- break;
-
- default:
- abort ();
+ longest_path = for_d.longest_path;
+ for_s.longest_path_code = for_d.longest_path_code;
}
- break;
- default:
- abort ();
+ /* 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;
}
-/* Emit code for one action. The previous tests have succeeded;
- TEST is the last of the chain. In the normal case we simply
- perform a state change. For the `accept' tests we must do more work. */
+/* Optimize ROOT. Use TYPE to describe ROOT in status messages. */
static void
-write_action (struct decision *p, struct decision_test *test,
- int depth, int uncond, struct decision *success,
- enum routine_type subroutine_type)
+optimize_subroutine_group (const char *type, state *root)
{
- const char *indent;
- int want_close = 0;
+ /* Remove optional transitions that turned out not to be worthwhile. */
+ if (collapse_optional_decisions_p)
+ collapse_optional_decisions (root);
- if (uncond)
- indent = " ";
- else if (test->type == DT_accept_op || test->type == DT_accept_insn)
+ /* Try to remove duplicated tests and to rearrange tests into a more
+ logical order. */
+ if (cse_tests_p)
{
- fputs (" {\n", stdout);
- indent = " ";
- want_close = 1;
+ 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);
}
- else
- indent = " ";
- if (test->type == DT_accept_op)
- {
- printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
+ /* Try to simplify two or more tests into one. */
+ if (simplify_tests_p)
+ simplify_tests (root);
- /* Only allow DT_accept_insn to follow. */
- if (test->next)
- {
- test = test->next;
- if (test->type != DT_accept_insn)
- abort ();
- }
+ /* 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);
}
- /* Sanity check that we're now at the end of the list of tests. */
- if (test->next)
- abort ();
-
- if (test->type == DT_accept_insn)
- {
- switch (subroutine_type)
- {
- case RECOG:
- if (test->u.insn.num_clobbers_to_add != 0)
- printf ("%s*pnum_clobbers = %d;\n",
- indent, test->u.insn.num_clobbers_to_add);
- printf ("%sreturn %d;\n", indent, test->u.insn.code_number);
- break;
+ /* 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);
+}
- case SPLIT:
- printf ("%sreturn gen_split_%d (insn, operands);\n",
- indent, test->u.insn.code_number);
- break;
+class merge_pattern_info;
- case PEEPHOLE2:
- {
- int match_len = 0, i;
+/* Represents a transition from one pattern to another. */
+class merge_pattern_transition
+{
+public:
+ merge_pattern_transition (merge_pattern_info *);
- for (i = strlen (p->position) - 1; i >= 0; --i)
- if (ISUPPER (p->position[i]))
- {
- match_len = p->position[i] - 'A';
- break;
- }
- printf ("%s*_pmatch_len = %d;\n", indent, match_len);
- printf ("%stem = gen_peephole2_%d (insn, operands);\n",
- indent, test->u.insn.code_number);
- printf ("%sif (tem != 0)\n%s return tem;\n", indent, indent);
- }
- break;
+ /* The target pattern. */
+ merge_pattern_info *to;
- default:
- abort ();
- }
- }
- else
- {
- printf("%sgoto L%d;\n", indent, success->number);
- success->need_label = 1;
- }
+ /* 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;
+};
- if (want_close)
- fputs (" }\n", stdout);
+merge_pattern_transition::merge_pattern_transition (merge_pattern_info *to_in)
+ : to (to_in)
+{
}
-/* Return 1 if the test is always true and has no fallthru path. Return -1
- if the test does have a fallthru path, but requires that the condition be
- terminated. Otherwise return 0 for a normal test. */
-/* ??? is_unconditional is a stupid name for a tri-state function. */
-
-static int
-is_unconditional (struct decision_test *t, enum routine_type subroutine_type)
+/* 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. */
+class merge_pattern_info
{
- if (t->type == DT_accept_op)
- return 1;
+public:
+ merge_pattern_info (unsigned int);
- if (t->type == DT_accept_insn)
- {
- switch (subroutine_type)
- {
- case RECOG:
- return (t->u.insn.num_clobbers_to_add == 0);
- case SPLIT:
- return 1;
- case PEEPHOLE2:
- return -1;
- default:
- abort ();
- }
- }
-
- return 0;
-}
+ /* 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;
-/* Emit code for one node -- the conditional and the accompanying action.
- Return true if there is no fallthru path. */
+ /* 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;
-static int
-write_node (struct decision *p, int depth,
- enum routine_type subroutine_type)
-{
- struct decision_test *test, *last_test;
- int uncond;
-
- /* Scan the tests and simplify comparisons against small
- constants. */
- for (test = p->tests; test; test = test->next)
- {
- if (test->type == DT_code
- && test->u.code == CONST_INT
- && test->next
- && test->next->type == DT_elt_zero_wide_safe
- && -MAX_SAVED_CONST_INT <= test->next->u.intval
- && test->next->u.intval <= MAX_SAVED_CONST_INT)
- {
- test->type = DT_const_int;
- test->u.intval = test->next->u.intval;
- test->next = test->next->next;
- }
- }
+ /* True if we have decided to generalize the root decision's test,
+ as per PARAM_TEST. */
+ unsigned int param_test_p : 1;
- last_test = test = p->tests;
- uncond = is_unconditional (test, subroutine_type);
- if (uncond == 0)
- {
- printf (" if (");
- write_cond (test, depth, subroutine_type);
+ /* Likewise for the root decision's transition, as per PARAM_TRANSITION. */
+ unsigned int param_transition_p : 1;
- while ((test = test->next) != NULL)
- {
- last_test = test;
- if (is_unconditional (test, subroutine_type))
- break;
+ /* True if the contents of the structure are completely filled in. */
+ unsigned int complete_p : 1;
- printf ("\n && ");
- write_cond (test, depth, subroutine_type);
- }
+ /* 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;
- printf (")\n");
- }
+ /* The number of states that use this pattern. */
+ unsigned int num_users;
- write_action (p, last_test, depth, uncond, p->success.first, subroutine_type);
+ /* The number of distinct success values that the pattern returns. */
+ unsigned int num_results;
- return uncond > 0;
-}
+ /* 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.
-/* Emit code for all of the sibling nodes of HEAD. */
+ 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).
-static void
-write_tree_1 (struct decision_head *head, int depth,
- enum routine_type subroutine_type)
-{
- struct decision *p, *next;
- int uncond = 0;
+ 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;
- for (p = head->first; p ; p = next)
- {
- /* The label for the first element was printed in write_tree. */
- if (p != head->first && p->need_label)
- OUTPUT_LABEL (" ", p->number);
+ /* 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;
- /* Attempt to write a switch statement for a whole sequence. */
- next = write_switch (p, depth);
- if (p != next)
- uncond = 0;
- else
- {
- /* Failed -- fall back and write one node. */
- uncond = write_node (p, depth, subroutine_type);
- next = p->next;
- }
- }
+ /* The routine associated with the pattern, or null if we haven't generated
+ one yet. */
+ pattern_routine *routine;
+};
- /* Finished with this chain. Close a fallthru path by branching
- to the afterward node. */
- if (! uncond)
- write_afterward (head->last, head->last->afterward, " ");
+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);
}
-/* Write out the decision tree starting at HEAD. PREVPOS is the
- position at the node that branched to this node. */
+/* Describes one way of matching a particular state to a particular
+ pattern. */
+class merge_state_result
+{
+public:
+ 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;
+};
-static void
-write_tree (struct decision_head *head, const char *prevpos,
- enum routine_type type, int initial)
+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. */
+class merge_state_info
{
- struct decision *p = head->first;
+public:
+ merge_state_info (state *);
- putchar ('\n');
- if (p->need_label)
- OUTPUT_LABEL (" ", p->number);
+ /* The state itself. */
+ state *s;
- if (! initial && p->subroutine_number > 0)
- {
- static const char * const name_prefix[] = {
- "recog", "split", "peephole2"
- };
+ /* Index I gives information about the target of transition I. */
+ merge_state_info *to_states;
- static const char * const call_suffix[] = {
- ", pnum_clobbers", "", ", _pmatch_len"
- };
+ /* The number of transitions in S. */
+ unsigned int num_transitions;
- /* This node has been broken out into a separate subroutine.
- Call it, test the result, and branch accordingly. */
+ /* True if the state has been deleted in favor of a call to a
+ pattern routine. */
+ bool merged_p;
- if (p->afterward)
- {
- printf (" tem = %s_%d (x0, insn%s);\n",
- name_prefix[type], p->subroutine_number, call_suffix[type]);
- if (IS_SPLIT (type))
- printf (" if (tem != 0)\n return tem;\n");
- else
- printf (" if (tem >= 0)\n return tem;\n");
+ /* 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;
- change_state (p->position, p->afterward->position, NULL, " ");
- printf (" goto L%d;\n", p->afterward->number);
- }
- else
- {
- printf (" return %s_%d (x0, insn%s);\n",
- name_prefix[type], p->subroutine_number, call_suffix[type]);
- }
- }
- else
- {
- int depth = strlen (p->position);
+ /* A list of pattern matches for this state. */
+ merge_state_result *res;
+};
- change_state (prevpos, p->position, head->last->afterward, " ");
- write_tree_1 (head, depth, type);
+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) {}
- for (p = head->first; p; p = p->next)
- if (p->success.first)
- write_tree (&p->success, p->position, type, 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;
}
-/* Write out a subroutine of type TYPE to do comparisons starting at
- node TREE. */
+/* PAT2 is a subpattern of PAT1. Return true if PAT2 should be inlined
+ into PAT1's C routine. */
-static void
-write_subroutine (struct decision_head *head, enum routine_type type)
+static bool
+same_pattern_p (merge_pattern_info *pat1, merge_pattern_info *pat2)
{
- int subfunction = head->first ? head->first->subroutine_number : 0;
- const char *s_or_e;
- char extension[32];
- int i;
+ return pat1->num_users == pat2->num_users || !useful_pattern_p (pat2);
+}
- s_or_e = subfunction ? "static " : "";
+/* 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. */
- if (subfunction)
- sprintf (extension, "_%d", subfunction);
- else if (type == RECOG)
- extension[0] = '\0';
- else
- strcpy (extension, "_insns");
+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;
+}
- switch (type)
+/* 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))
{
- case RECOG:
- printf ("%sint\n\
-recog%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n", s_or_e, extension);
- break;
- case SPLIT:
- printf ("%srtx\n\
-split%s (rtx x0 ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED)\n",
- s_or_e, extension);
- break;
- case PEEPHOLE2:
- printf ("%srtx\n\
-peephole2%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *_pmatch_len ATTRIBUTE_UNUSED)\n",
- s_or_e, extension);
- break;
+ sinfo->res = sinfo->res->prev;
+ gcc_assert (sinfo->res);
}
+}
- printf ("{\n rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
- for (i = 1; i <= max_depth; i++)
- printf (" rtx x%d ATTRIBUTE_UNUSED;\n", i);
-
- printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
-
- if (!subfunction)
- printf (" recog_data.insn = NULL_RTX;\n");
-
- if (head->first)
- write_tree (head, "", type, 1);
- else
- printf (" goto ret0;\n");
+/* 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. */
- printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
+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;
}
-/* In break_out_subroutines, we discovered the boundaries for the
- subroutines, but did not write them out. Do so now. */
+/* 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
-write_subroutines (struct decision_head *head, enum routine_type type)
+update_parameters (vec <parameter> &to, const vec <parameter> &from)
{
- struct decision *p;
-
- for (p = head->first; p ; p = p->next)
- if (p->success.first)
- write_subroutines (&p->success, type);
-
- if (head->first->subroutine_number > 0)
- write_subroutine (head, type);
+ for (unsigned int i = to.length (); i < from.length (); ++i)
+ to.quick_push (from[i]);
}
-/* Begin the output file. */
+/* 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 void
-write_header (void)
+static bool
+compatible_tests_p (const rtx_test &a, const rtx_test &b,
+ parameter *parama, parameter *paramb)
{
- puts ("\
-/* Generated automatically by the program `genrecog' from the target\n\
- machine description file. */\n\
-\n\
-#include \"config.h\"\n\
-#include \"system.h\"\n\
-#include \"coretypes.h\"\n\
-#include \"tm.h\"\n\
-#include \"rtl.h\"\n\
-#include \"tm_p.h\"\n\
-#include \"function.h\"\n\
-#include \"insn-config.h\"\n\
-#include \"recog.h\"\n\
-#include \"real.h\"\n\
-#include \"output.h\"\n\
-#include \"flags.h\"\n\
-#include \"hard-reg-set.h\"\n\
-#include \"resource.h\"\n\
-#include \"toplev.h\"\n\
-#include \"reload.h\"\n\
-\n");
-
- puts ("\n\
-/* `recog' contains a decision tree that recognizes whether the rtx\n\
- X0 is a valid instruction.\n\
-\n\
- recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
- returns a nonnegative number which is the insn code number for the\n\
- pattern that matched. This is the same as the order in the machine\n\
- description of the entry that matched. This number can be used as an\n\
- index into `insn_data' and other tables.\n");
- puts ("\
- The third argument to recog is an optional pointer to an int. If\n\
- present, recog will accept a pattern if it matches except for missing\n\
- CLOBBER expressions at the end. In that case, the value pointed to by\n\
- the optional pointer will be set to the number of CLOBBERs that need\n\
- to be added (it should be initialized to zero by the caller). If it");
- puts ("\
- is set nonzero, the caller should allocate a PARALLEL of the\n\
- appropriate size, copy the initial entries, and call add_clobbers\n\
- (found in insn-emit.c) to fill in the CLOBBERs.\n\
-");
+ 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;
- puts ("\n\
- The function split_insns returns 0 if the rtl could not\n\
- be split or the split rtl as an INSN list if it can be.\n\
-\n\
- The function peephole2_insns returns 0 if the rtl could not\n\
- be matched. If there was a match, the new rtl is returned in an INSN list,\n\
- and LAST_INSN will point to the last recognized insn in the old sequence.\n\
-*/\n\n");
+ default:
+ return a == b;
+ }
}
-\f
-/* Construct and return a sequence of decisions
- that will recognize INSN.
-
- TYPE says what type of routine we are recognizing (RECOG or SPLIT). */
+/* 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 struct decision_head
-make_insn_sequence (rtx insn, enum routine_type type)
+static bool
+set_parameter (vec <parameter> ¶ms, unsigned int id,
+ const parameter &value)
{
- rtx x;
- const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
- int truth = maybe_eval_c_test (c_test);
- struct decision *last;
- struct decision_test *test, **place;
- struct decision_head head;
- char c_test_pos[2];
+ 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;
+}
- /* We should never see an insn whose C test is false at compile time. */
- if (truth == 0)
- abort ();
+/* 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.
- record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL));
+ 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. */
- c_test_pos[0] = '\0';
- if (type == PEEPHOLE2)
- {
- int i, j;
+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);
- /* peephole2 gets special treatment:
- - X always gets an outer parallel even if it's only one entry
- - we remove all traces of outer-level match_scratch and match_dup
- expressions here. */
- x = rtx_alloc (PARALLEL);
- PUT_MODE (x, VOIDmode);
- XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
- for (i = j = 0; i < XVECLEN (insn, 0); i++)
- {
- rtx tmp = XVECEXP (insn, 0, i);
- if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
- {
- XVECEXP (x, 0, j) = tmp;
- j++;
- }
- }
- XVECLEN (x, 0) = j;
+ for (unsigned int i = start; i < params2.length (); ++i)
+ if (params1[i] == param1 && params2[i] == param2)
+ {
+ *res = i;
+ return true;
+ }
- c_test_pos[0] = 'A' + j - 1;
- c_test_pos[1] = '\0';
- }
- else if (XVECLEN (insn, type == RECOG) == 1)
- x = XVECEXP (insn, type == RECOG, 0);
- else
- {
- x = rtx_alloc (PARALLEL);
- XVEC (x, 0) = XVEC (insn, type == RECOG);
- PUT_MODE (x, VOIDmode);
- }
+ if (force_unique_params_p)
+ for (unsigned int i = 0; i < params2.length (); ++i)
+ if (params1[i] == param1 || params2[i] == param2)
+ return false;
- validate_pattern (x, insn, NULL_RTX, 0);
+ if (params2.length () >= MAX_PATTERN_PARAMS)
+ return false;
- memset(&head, 0, sizeof(head));
- last = add_to_sequence (x, &head, "", type, 1);
+ *res = params2.length ();
+ params1.quick_push (param1);
+ params2.quick_push (param2);
+ return true;
+}
- /* Find the end of the test chain on the last node. */
- for (test = last->tests; test->next; test = test->next)
- continue;
- place = &test->next;
+/* 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. */
- /* Skip the C test if it's known to be true at compile time. */
- if (truth == -1)
+static bool
+merge_relative_positions (position **roota, position *a,
+ position *rootb, position *b)
+{
+ if (!relative_patterns_p)
{
- /* Need a new node if we have another test to add. */
- if (test->type == DT_accept_op)
+ if (a != b)
+ return false;
+ if (!*roota)
{
- last = new_decision (c_test_pos, &last->success);
- place = &last->tests;
+ *roota = rootb;
+ return true;
}
- test = new_decision_test (DT_c_test, &place);
- test->u.c_test = c_test;
+ 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;
+}
- test = new_decision_test (DT_accept_insn, &place);
- test->u.insn.code_number = next_insn_code;
- test->u.insn.lineno = pattern_lineno;
- test->u.insn.num_clobbers_to_add = 0;
+/* 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 &);
+};
- switch (type)
- {
- case RECOG:
- /* If this is a DEFINE_INSN and X is a PARALLEL, see if it ends
- with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
- If so, set up to recognize the pattern without these CLOBBERs. */
+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 ();
+}
- if (GET_CODE (x) == PARALLEL)
- {
- int i;
+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);
+}
- /* Find the last non-clobber in the parallel. */
- for (i = XVECLEN (x, 0); i > 0; i--)
- {
- rtx y = XVECEXP (x, 0, i - 1);
- if (GET_CODE (y) != CLOBBER
- || (!REG_P (XEXP (y, 0))
- && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
- break;
- }
+/* Try to make the state described by SINFO1 use the same pattern as the
+ state described by SINFO2. Return true on success.
- if (i != XVECLEN (x, 0))
- {
- rtx new;
- struct decision_head clobber_head;
+ SINFO1 and SINFO2 are known to have the same hash value. */
- /* Build a similar insn without the clobbers. */
- if (i == 1)
- new = XVECEXP (x, 0, 0);
- else
+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)
+ continue;
+
+ merge_state_result *res2 = sinfo2->res;
+ decision *d2 = sinfo2->s->singleton ();
+ position *root2 = (d2->test.pos_operand < 0 ? d2->test.pos : 0);
+ unsigned int num_transitions = sinfo2->num_transitions;
+
+ /* If RES2 is null then SINFO2's test in isolation has not been seen
+ before. First try matching that on its own. */
+ if (!res2)
+ {
+ merge_pattern_info *new_pat
+ = new merge_pattern_info (num_transitions);
+ merge_state_result *new_res2
+ = new merge_state_result (new_pat, root2, res2);
+ sinfo2->res = new_res2;
+
+ new_pat->num_statements = !d2->test.single_outcome_p ();
+ new_pat->num_results = num_transitions;
+ bool matched_p = false;
+ /* Look for states that don't currently match anything but
+ can be made to match SINFO2 on its own. */
+ for (merge_state_info *sinfo1 = sinfo2->prev_same_test; sinfo1;
+ sinfo1 = sinfo1->prev_same_test)
+ if (!sinfo1->res && merge_patterns (sinfo1, sinfo2))
+ matched_p = true;
+ if (!matched_p)
+ {
+ /* No other states match. */
+ sinfo2->res = res2;
+ delete new_pat;
+ delete new_res2;
+ continue;
+ }
+ else
+ res2 = new_res2;
+ }
+
+ /* Keep the existing pattern if it's as good as anything we'd
+ create for SINFO2. */
+ if (complete_result_p (res2->pattern, sinfo2))
+ {
+ res2->pattern->num_users += 1;
+ continue;
+ }
+
+ /* Create a new pattern for SINFO2. */
+ merge_pattern_info *new_pat = new merge_pattern_info (num_transitions);
+ merge_state_result *new_res2
+ = new merge_state_result (new_pat, root2, res2);
+ sinfo2->res = new_res2;
+
+ /* Fill in details about the pattern. */
+ new_pat->num_statements = !d2->test.single_outcome_p ();
+ new_pat->num_results = 0;
+ for (unsigned int j = 0; j < num_transitions; ++j)
+ if (merge_state_result *to_res = sinfo2->to_states[j].res)
+ {
+ /* Count the target state as part of this pattern.
+ First update the root position so that it can reach
+ the target state's root. */
+ if (to_res->root)
+ {
+ if (new_res2->root)
+ new_res2->root = common_position (new_res2->root,
+ to_res->root);
+ else
+ new_res2->root = to_res->root;
+ }
+ merge_pattern_info *to_pat = to_res->pattern;
+ merge_pattern_transition *ptrans
+ = new merge_pattern_transition (to_pat);
+
+ /* TO_PAT may have acquired more parameters when matching
+ states earlier in STATES than TO_RES's, but the list is
+ now final. Make sure that TO_RES is up to date. */
+ update_parameters (to_res->params, to_pat->params);
+
+ /* Start out by assuming that every user of NEW_PAT will
+ want to pass the same (constant) parameters as TO_RES. */
+ update_parameters (ptrans->params, to_res->params);
+
+ new_pat->transitions[j] = ptrans;
+ new_pat->num_statements += to_pat->num_statements;
+ new_pat->num_results += to_pat->num_results;
+ }
+ else
+ /* The target state doesn't match anything and so is not part
+ of the pattern. */
+ new_pat->num_results += 1;
+
+ /* See if any earlier states that match RES2's pattern also match
+ NEW_PAT. */
+ bool matched_p = false;
+ for (merge_state_info *sinfo1 = sinfo2->prev_same_test; sinfo1;
+ sinfo1 = sinfo1->prev_same_test)
+ {
+ prune_invalid_results (sinfo1);
+ if (sinfo1->res
+ && sinfo1->res->pattern == res2->pattern
+ && merge_patterns (sinfo1, sinfo2))
+ matched_p = true;
+ }
+ if (!matched_p)
+ {
+ /* Nothing else matches NEW_PAT, so go back to the previous
+ pattern (possibly just a single-state one). */
+ sinfo2->res = res2;
+ delete new_pat;
+ delete new_res2;
+ }
+ /* Assume that SINFO2 will use RES. At this point we don't know
+ whether earlier states that match the same pattern will use
+ that match or a different one. */
+ sinfo2->res->pattern->num_users += 1;
+ }
+ /* Step 4: Finalize the choice of pattern for each state, ignoring
+ patterns that were only used once. Update each pattern's size
+ so that it doesn't include subpatterns that are going to be split
+ out into subroutines. */
+ for (unsigned int i = 0; i < states.length (); ++i)
+ {
+ merge_state_info *sinfo = &states[i];
+ merge_state_result *res = sinfo->res;
+ /* Wind past patterns that are only used by SINFO. */
+ while (res && res->pattern->num_users == 1)
+ {
+ res = res->prev;
+ sinfo->res = res;
+ if (res)
+ res->pattern->num_users += 1;
+ }
+ if (!res)
+ continue;
+
+ /* We have a shared pattern and are now committed to the match. */
+ merge_pattern_info *pat = res->pattern;
+ gcc_assert (valid_result_p (pat, sinfo));
+
+ if (!pat->complete_p)
+ {
+ /* Look for subpatterns that are going to be split out and remove
+ them from the number of statements. */
+ for (unsigned int j = 0; j < sinfo->num_transitions; ++j)
+ if (merge_pattern_transition *ptrans = pat->transitions[j])
+ {
+ merge_pattern_info *to_pat = ptrans->to;
+ if (!same_pattern_p (pat, to_pat))
+ pat->num_statements -= to_pat->num_statements;
+ }
+ pat->complete_p = true;
+ }
+ }
+ /* Step 5: Split out the patterns. */
+ for (unsigned int i = 0; i < states.length (); ++i)
+ {
+ merge_state_info *sinfo = &states[i];
+ merge_state_result *res = sinfo->res;
+ if (!sinfo->merged_p && res && useful_pattern_p (res->pattern))
+ use_pattern (sinfo);
+ }
+ fprintf (stderr, "Shared %d out of %d states by creating %d new states,"
+ " saving %d\n",
+ pattern_use_states, states.length (), pattern_def_states,
+ pattern_use_states - pattern_def_states);
+}
+
+/* Information about a state tree that we're considering splitting into a
+ subroutine. */
+struct state_size
+{
+ /* The number of pseudo-statements in the state tree. */
+ unsigned int num_statements;
+
+ /* The approximate number of nested "if" and "switch" statements that
+ would be required if control could fall through to a later state. */
+ unsigned int depth;
+};
+
+/* Pairs a transition with information about its target state. */
+typedef std::pair <transition *, state_size> subroutine_candidate;
+
+/* Sort two subroutine_candidates so that the one with the largest
+ number of statements comes last. */
+
+static int
+subroutine_candidate_cmp (const void *a, const void *b)
+{
+ return int (((const subroutine_candidate *) a)->second.num_statements
+ - ((const subroutine_candidate *) b)->second.num_statements);
+}
+
+/* Turn S into a subroutine of type TYPE and add it to PROCS. Return a new
+ state that performs a subroutine call to S. */
+
+static state *
+create_subroutine (routine_type type, state *s, vec <state *> &procs)
+{
+ procs.safe_push (s);
+ acceptance_type acceptance;
+ acceptance.type = type;
+ acceptance.partial_p = true;
+ acceptance.u.subroutine_id = procs.length ();
+ state *news = new state;
+ add_decision (news, rtx_test::accept (acceptance), true, false);
+ return news;
+}
+
+/* Walk state tree S, of type TYPE, and look for subtrees that would be
+ better split into subroutines. Accumulate all such subroutines in PROCS.
+ Return the size of the new state tree (excluding subroutines). */
+
+static state_size
+find_subroutines (routine_type type, state *s, vec <state *> &procs)
+{
+ auto_vec <subroutine_candidate, 16> candidates;
+ state_size size;
+ size.num_statements = 0;
+ size.depth = 0;
+ for (decision *d = s->first; d; d = d->next)
+ {
+ if (!d->test.single_outcome_p ())
+ size.num_statements += 1;
+ for (transition *trans = d->first; trans; trans = trans->next)
+ {
+ /* Keep chains of simple decisions together if we know that no
+ change of position is required. We'll output this chain as a
+ single "if" statement, so it counts as a single nesting level. */
+ if (d->test.pos && d->if_statement_p ())
+ for (;;)
+ {
+ decision *newd = trans->to->singleton ();
+ if (!newd
+ || (newd->test.pos
+ && newd->test.pos_operand < 0
+ && newd->test.pos != d->test.pos)
+ || !newd->if_statement_p ())
+ break;
+ if (!newd->test.single_outcome_p ())
+ size.num_statements += 1;
+ trans = newd->singleton ();
+ if (newd->test.kind == rtx_test::SET_OP
+ || newd->test.kind == rtx_test::ACCEPT)
+ break;
+ }
+ /* The target of TRANS is a subroutine candidate. First recurse
+ on it to see how big it is after subroutines have been
+ split out. */
+ state_size to_size = find_subroutines (type, trans->to, procs);
+ if (d->next && to_size.depth > MAX_DEPTH)
+ /* Keeping the target state in the same routine would lead
+ to an excessive nesting of "if" and "switch" statements.
+ Split it out into a subroutine so that it can use
+ inverted tests that return early on failure. */
+ trans->to = create_subroutine (type, trans->to, procs);
+ else
+ {
+ size.num_statements += to_size.num_statements;
+ if (to_size.num_statements < MIN_NUM_STATEMENTS)
+ /* The target state is too small to be worth splitting.
+ Keep it in the same routine as S. */
+ size.depth = MAX (size.depth, to_size.depth);
+ else
+ /* Assume for now that we'll keep the target state in the
+ same routine as S, but record it as a subroutine candidate
+ if S grows too big. */
+ candidates.safe_push (subroutine_candidate (trans, to_size));
+ }
+ }
+ }
+ if (size.num_statements > MAX_NUM_STATEMENTS)
+ {
+ /* S is too big. Sort the subroutine candidates so that bigger ones
+ are nearer the end. */
+ candidates.qsort (subroutine_candidate_cmp);
+ while (!candidates.is_empty ()
+ && size.num_statements > MAX_NUM_STATEMENTS)
+ {
+ /* Peel off a candidate and force it into a subroutine. */
+ subroutine_candidate cand = candidates.pop ();
+ size.num_statements -= cand.second.num_statements;
+ cand.first->to = create_subroutine (type, cand.first->to, procs);
+ }
+ }
+ /* Update the depth for subroutine candidates that we decided not to
+ split out. */
+ for (unsigned int i = 0; i < candidates.length (); ++i)
+ size.depth = MAX (size.depth, candidates[i].second.depth);
+ size.depth += 1;
+ return size;
+}
+
+/* Return true if, for all X, PRED (X, MODE) implies that X has mode MODE. */
+
+static bool
+safe_predicate_mode (const struct pred_data *pred, machine_mode mode)
+{
+ /* Scalar integer constants have VOIDmode. */
+ if (GET_MODE_CLASS (mode) == MODE_INT
+ && (pred->codes[CONST_INT]
+ || pred->codes[CONST_DOUBLE]
+ || pred->codes[CONST_WIDE_INT]
+ || pred->codes[LABEL_REF]))
+ return false;
+
+ return !pred->special && mode != VOIDmode;
+}
+
+/* Fill CODES with the set of codes that could be matched by PRED. */
+
+static void
+get_predicate_codes (const struct pred_data *pred, int_set *codes)
+{
+ for (int i = 0; i < NUM_TRUE_RTX_CODE; ++i)
+ if (!pred || pred->codes[i])
+ codes->safe_push (i);
+}
+
+/* Return true if the first path through D1 tests the same thing as D2. */
+
+static bool
+has_same_test_p (decision *d1, decision *d2)
+{
+ do
+ {
+ if (d1->test == d2->test)
+ return true;
+ d1 = d1->first->to->first;
+ }
+ while (d1);
+ return false;
+}
+
+/* Return true if D1 and D2 cannot match the same rtx. All states reachable
+ from D2 have single decisions and all those decisions have single
+ transitions. */
+
+static bool
+mutually_exclusive_p (decision *d1, decision *d2)
+{
+ /* If one path through D1 fails to test the same thing as D2, assume
+ that D2's test could be true for D1 and look for a later, more useful,
+ test. This isn't as expensive as it looks in practice. */
+ while (!has_same_test_p (d1, d2))
+ {
+ d2 = d2->singleton ()->to->singleton ();
+ if (!d2)
+ return false;
+ }
+ if (d1->test == d2->test)
+ {
+ /* Look for any transitions from D1 that have the same labels as
+ the transition from D2. */
+ transition *trans2 = d2->singleton ();
+ for (transition *trans1 = d1->first; trans1; trans1 = trans1->next)
+ {
+ int_set::iterator i1 = trans1->labels.begin ();
+ int_set::iterator end1 = trans1->labels.end ();
+ int_set::iterator i2 = trans2->labels.begin ();
+ int_set::iterator end2 = trans2->labels.end ();
+ while (i1 != end1 && i2 != end2)
+ if (*i1 < *i2)
+ ++i1;
+ else if (*i2 < *i1)
+ ++i2;
+ else
+ {
+ /* TRANS1 has some labels in common with TRANS2. Assume
+ that D1 and D2 could match the same rtx if the target
+ of TRANS1 could match the same rtx as D2. */
+ for (decision *subd1 = trans1->to->first;
+ subd1; subd1 = subd1->next)
+ if (!mutually_exclusive_p (subd1, d2))
+ return false;
+ break;
+ }
+ }
+ return true;
+ }
+ for (transition *trans1 = d1->first; trans1; trans1 = trans1->next)
+ for (decision *subd1 = trans1->to->first; subd1; subd1 = subd1->next)
+ if (!mutually_exclusive_p (subd1, d2))
+ return false;
+ return true;
+}
+
+/* Try to merge S2's decision into D1, given that they have the same test.
+ Fail only if EXCLUDE is nonnull and the new transition would have the
+ same labels as *EXCLUDE. When returning true, set *NEXT_S1, *NEXT_S2
+ and *NEXT_EXCLUDE as for merge_into_state_1, or set *NEXT_S2 to null
+ if the merge is complete. */
+
+static bool
+merge_into_decision (decision *d1, state *s2, const int_set *exclude,
+ state **next_s1, state **next_s2,
+ const int_set **next_exclude)
+{
+ decision *d2 = s2->singleton ();
+ transition *trans2 = d2->singleton ();
+
+ /* Get a list of the transitions that intersect TRANS2. */
+ auto_vec <transition *, 32> intersecting;
+ for (transition *trans1 = d1->first; trans1; trans1 = trans1->next)
+ {
+ int_set::iterator i1 = trans1->labels.begin ();
+ int_set::iterator end1 = trans1->labels.end ();
+ int_set::iterator i2 = trans2->labels.begin ();
+ int_set::iterator end2 = trans2->labels.end ();
+ bool trans1_is_subset = true;
+ bool trans2_is_subset = true;
+ bool intersect_p = false;
+ while (i1 != end1 && i2 != end2)
+ if (*i1 < *i2)
+ {
+ trans1_is_subset = false;
+ ++i1;
+ }
+ else if (*i2 < *i1)
+ {
+ trans2_is_subset = false;
+ ++i2;
+ }
+ else
+ {
+ intersect_p = true;
+ ++i1;
+ ++i2;
+ }
+ if (i1 != end1)
+ trans1_is_subset = false;
+ if (i2 != end2)
+ trans2_is_subset = false;
+ if (trans1_is_subset && trans2_is_subset)
+ {
+ /* There's already a transition that matches exactly.
+ Merge the target states. */
+ trans1->optional &= trans2->optional;
+ *next_s1 = trans1->to;
+ *next_s2 = trans2->to;
+ *next_exclude = 0;
+ return true;
+ }
+ if (trans2_is_subset)
+ {
+ /* TRANS1 has all the labels that TRANS2 needs. Merge S2 into
+ the target of TRANS1, but (to avoid infinite recursion)
+ make sure that we don't end up creating another transition
+ like TRANS1. */
+ *next_s1 = trans1->to;
+ *next_s2 = s2;
+ *next_exclude = &trans1->labels;
+ return true;
+ }
+ if (intersect_p)
+ intersecting.safe_push (trans1);
+ }
+
+ if (intersecting.is_empty ())
+ {
+ /* No existing labels intersect the new ones. We can just add
+ TRANS2 itself. */
+ d1->push_back (d2->release ());
+ *next_s1 = 0;
+ *next_s2 = 0;
+ *next_exclude = 0;
+ return true;
+ }
+
+ /* Take the union of the labels in INTERSECTING and TRANS2. Store the
+ result in COMBINED and use NEXT as a temporary. */
+ int_set tmp1 = trans2->labels, tmp2;
+ int_set *combined = &tmp1, *next = &tmp2;
+ for (unsigned int i = 0; i < intersecting.length (); ++i)
+ {
+ transition *trans1 = intersecting[i];
+ next->truncate (0);
+ next->safe_grow (trans1->labels.length () + combined->length ());
+ int_set::iterator end
+ = std::set_union (trans1->labels.begin (), trans1->labels.end (),
+ combined->begin (), combined->end (),
+ next->begin ());
+ next->truncate (end - next->begin ());
+ std::swap (next, combined);
+ }
+
+ /* Stop now if we've been told not to create a transition with these
+ labels. */
+ if (exclude && *combined == *exclude)
+ return false;
+
+ /* Get the transition that should carry the new labels. */
+ transition *new_trans = intersecting[0];
+ if (intersecting.length () == 1)
+ {
+ /* We're merging with one existing transition whose labels are a
+ subset of those required. If both transitions are optional,
+ we can just expand the set of labels so that it's suitable
+ for both transitions. It isn't worth preserving the original
+ transitions since we know that they can't be merged; we would
+ need to backtrack to S2 if TRANS1->to fails. In contrast,
+ we might be able to merge the targets of the transitions
+ without any backtracking.
+
+ If instead the existing transition is not optional, ensure that
+ all target decisions are suitably protected. Some decisions
+ might already have a more specific requirement than NEW_TRANS,
+ in which case there's no point testing NEW_TRANS as well. E.g. this
+ would have happened if a test for an (eq ...) rtx had been
+ added to a decision that tested whether the code is suitable
+ for comparison_operator. The original comparison_operator
+ transition would have been non-optional and the (eq ...) test
+ would be performed by a second decision in the target of that
+ transition.
+
+ The remaining case -- keeping the original optional transition
+ when adding a non-optional TRANS2 -- is a wash. Preserving
+ the optional transition only helps if we later merge another
+ state S3 that is mutually exclusive with S2 and whose labels
+ belong to *COMBINED - TRANS1->labels. We can then test the
+ original NEW_TRANS and S3 in the same decision. We keep the
+ optional transition around for that case, but it occurs very
+ rarely. */
+ gcc_assert (new_trans->labels != *combined);
+ if (!new_trans->optional || !trans2->optional)
+ {
+ decision *start = 0;
+ for (decision *end = new_trans->to->first; end; end = end->next)
+ {
+ if (!start && end->test != d1->test)
+ /* END belongs to a range of decisions that need to be
+ protected by NEW_TRANS. */
+ start = end;
+ if (start && (!end->next || end->next->test == d1->test))
{
- int j;
+ /* Protect [START, END] with NEW_TRANS. The decisions
+ move to NEW_S and NEW_D becomes part of NEW_TRANS->to. */
+ state *new_s = new state;
+ decision *new_d = new decision (d1->test);
+ new_d->push_back (new transition (new_trans->labels, new_s,
+ new_trans->optional));
+ state::range r (start, end);
+ new_trans->to->replace (r, new_d);
+ new_s->push_back (r);
+
+ /* Continue with an empty range. */
+ start = 0;
+
+ /* Continue from the decision after NEW_D. */
+ end = new_d;
+ }
+ }
+ }
+ new_trans->optional = true;
+ new_trans->labels = *combined;
+ }
+ else
+ {
+ /* We're merging more than one existing transition together.
+ Those transitions are successfully dividing the matching space
+ and so we want to preserve them, even if they're optional.
+
+ Create a new transition with the union set of labels and make
+ it go to a state that has the original transitions. */
+ decision *new_d = new decision (d1->test);
+ for (unsigned int i = 0; i < intersecting.length (); ++i)
+ new_d->push_back (d1->remove (intersecting[i]));
+
+ state *new_s = new state;
+ new_s->push_back (new_d);
+
+ new_trans = new transition (*combined, new_s, true);
+ d1->push_back (new_trans);
+ }
+
+ /* We now have an optional transition with labels *COMBINED. Decide
+ whether we can use it as TRANS2 or whether we need to merge S2
+ into the target of NEW_TRANS. */
+ gcc_assert (new_trans->optional);
+ if (new_trans->labels == trans2->labels)
+ {
+ /* NEW_TRANS matches TRANS2. Just merge the target states. */
+ new_trans->optional = trans2->optional;
+ *next_s1 = new_trans->to;
+ *next_s2 = trans2->to;
+ *next_exclude = 0;
+ }
+ else
+ {
+ /* Try to merge TRANS2 into the target of the overlapping transition,
+ but (to prevent infinite recursion or excessive redundancy) without
+ creating another transition of the same type. */
+ *next_s1 = new_trans->to;
+ *next_s2 = s2;
+ *next_exclude = &new_trans->labels;
+ }
+ return true;
+}
+
+/* Make progress in merging S2 into S1, given that each state in S2
+ has a single decision. If EXCLUDE is nonnull, avoid creating a new
+ transition with the same test as S2's decision and with the labels
+ in *EXCLUDE.
+
+ Return true if there is still work to do. When returning true,
+ set *NEXT_S1, *NEXT_S2 and *NEXT_EXCLUDE to the values that
+ S1, S2 and EXCLUDE should have next time round.
+
+ If S1 and S2 both match a particular rtx, give priority to S1. */
+
+static bool
+merge_into_state_1 (state *s1, state *s2, const int_set *exclude,
+ state **next_s1, state **next_s2,
+ const int_set **next_exclude)
+{
+ decision *d2 = s2->singleton ();
+ if (decision *d1 = s1->last)
+ {
+ if (d1->test.terminal_p ())
+ /* D1 is an unconditional return, so S2 can never match. This can
+ sometimes be a bug in the .md description, but might also happen
+ if genconditions forces some conditions to true for certain
+ configurations. */
+ return false;
+
+ /* Go backwards through the decisions in S1, stopping once we find one
+ that could match the same thing as S2. */
+ while (d1->prev && mutually_exclusive_p (d1, d2))
+ d1 = d1->prev;
+
+ /* Search forwards from that point, merging D2 into the first
+ decision we can. */
+ for (; d1; d1 = d1->next)
+ {
+ /* If S2 performs some optional tests before testing the same thing
+ as D1, those tests do not help to distinguish D1 and S2, so it's
+ better to drop them. Search through such optional decisions
+ until we find something that tests the same thing as D1. */
+ state *sub_s2 = s2;
+ for (;;)
+ {
+ decision *sub_d2 = sub_s2->singleton ();
+ if (d1->test == sub_d2->test)
+ {
+ /* Only apply EXCLUDE if we're testing the same thing
+ as D2. */
+ const int_set *sub_exclude = (d2 == sub_d2 ? exclude : 0);
+
+ /* Try to merge SUB_S2 into D1. This can only fail if
+ it would involve creating a new transition with
+ labels SUB_EXCLUDE. */
+ if (merge_into_decision (d1, sub_s2, sub_exclude,
+ next_s1, next_s2, next_exclude))
+ return *next_s2 != 0;
+
+ /* Can't merge with D1; try a later decision. */
+ break;
+ }
+ transition *sub_trans2 = sub_d2->singleton ();
+ if (!sub_trans2->optional)
+ /* Can't merge with D1; try a later decision. */
+ break;
+ sub_s2 = sub_trans2->to;
+ }
+ }
+ }
+
+ /* We can't merge D2 with any existing decision. Just add it to the end. */
+ s1->push_back (s2->release ());
+ return false;
+}
+
+/* Merge S2 into S1. If they both match a particular rtx, give
+ priority to S1. Each state in S2 has a single decision. */
+
+static void
+merge_into_state (state *s1, state *s2)
+{
+ const int_set *exclude = 0;
+ while (s2 && merge_into_state_1 (s1, s2, exclude, &s1, &s2, &exclude))
+ continue;
+}
+
+/* Pairs a pattern that needs to be matched with the rtx position at
+ which the pattern should occur. */
+class pattern_pos {
+public:
+ pattern_pos () {}
+ pattern_pos (rtx, position *);
+
+ rtx pattern;
+ position *pos;
+};
+
+pattern_pos::pattern_pos (rtx pattern_in, position *pos_in)
+ : pattern (pattern_in), pos (pos_in)
+{}
+
+/* Compare entries according to their depth-first order. There shouldn't
+ be two entries at the same position. */
+
+bool
+operator < (const pattern_pos &e1, const pattern_pos &e2)
+{
+ int diff = compare_positions (e1.pos, e2.pos);
+ gcc_assert (diff != 0 || e1.pattern == e2.pattern);
+ return diff < 0;
+}
+
+/* Add new decisions to S that check whether the rtx at position POS
+ matches PATTERN. Return the state that is reached in that case.
+ TOP_PATTERN is the overall pattern, as passed to match_pattern_1. */
+
+static state *
+match_pattern_2 (state *s, md_rtx_info *info, position *pos, rtx pattern)
+{
+ auto_vec <pattern_pos, 32> worklist;
+ auto_vec <pattern_pos, 32> pred_and_mode_tests;
+ auto_vec <pattern_pos, 32> dup_tests;
+
+ worklist.safe_push (pattern_pos (pattern, pos));
+ while (!worklist.is_empty ())
+ {
+ pattern_pos next = worklist.pop ();
+ pattern = next.pattern;
+ pos = next.pos;
+ unsigned int reverse_s = worklist.length ();
+
+ enum rtx_code code = GET_CODE (pattern);
+ switch (code)
+ {
+ case MATCH_OP_DUP:
+ case MATCH_DUP:
+ case MATCH_PAR_DUP:
+ /* Add a test that the rtx matches the earlier one, but only
+ after the structure and predicates have been checked. */
+ dup_tests.safe_push (pattern_pos (pattern, pos));
+
+ /* Use the same code check as the original operand. */
+ pattern = find_operand (info->def, XINT (pattern, 0), NULL_RTX);
+ /* Fall through. */
+
+ case MATCH_PARALLEL:
+ case MATCH_OPERAND:
+ case MATCH_SCRATCH:
+ case MATCH_OPERATOR:
+ {
+ const char *pred_name = predicate_name (pattern);
+ const struct pred_data *pred = 0;
+ if (pred_name[0] != 0)
+ {
+ pred = lookup_predicate (pred_name);
+ /* Only report errors once per rtx. */
+ if (code == GET_CODE (pattern))
+ {
+ if (!pred)
+ error_at (info->loc, "unknown predicate '%s' used in %s",
+ pred_name, GET_RTX_NAME (code));
+ else if (code == MATCH_PARALLEL
+ && pred->singleton != PARALLEL)
+ error_at (info->loc, "predicate '%s' used in"
+ " match_parallel does not allow only PARALLEL",
+ pred->name);
+ }
+ }
+
+ if (code == MATCH_PARALLEL || code == MATCH_PAR_DUP)
+ {
+ /* Check that we have a parallel with enough elements. */
+ s = add_decision (s, rtx_test::code (pos), PARALLEL, false);
+ int min_len = XVECLEN (pattern, 2);
+ s = add_decision (s, rtx_test::veclen_ge (pos, min_len),
+ true, false);
+ }
+ else
+ {
+ /* Check that the rtx has one of codes accepted by the
+ predicate. This is necessary when matching suboperands
+ of a MATCH_OPERATOR or MATCH_OP_DUP, since we can't
+ call XEXP (X, N) without checking that X has at least
+ N+1 operands. */
+ int_set codes;
+ get_predicate_codes (pred, &codes);
+ bool need_codes = (pred
+ && (code == MATCH_OPERATOR
+ || code == MATCH_OP_DUP));
+ s = add_decision (s, rtx_test::code (pos), codes, !need_codes);
+ }
+
+ /* Postpone the predicate check until we've checked the rest
+ of the rtx structure. */
+ if (code == GET_CODE (pattern))
+ pred_and_mode_tests.safe_push (pattern_pos (pattern, pos));
+
+ /* If we need to match suboperands, add them to the worklist. */
+ if (code == MATCH_OPERATOR || code == MATCH_PARALLEL)
+ {
+ position **subpos_ptr;
+ enum position_type pos_type;
+ int i;
+ if (code == MATCH_OPERATOR || code == MATCH_OP_DUP)
+ {
+ pos_type = POS_XEXP;
+ subpos_ptr = &pos->xexps;
+ i = (code == MATCH_OPERATOR ? 2 : 1);
+ }
+ else
+ {
+ pos_type = POS_XVECEXP0;
+ subpos_ptr = &pos->xvecexp0s;
+ i = 2;
+ }
+ for (int j = 0; j < XVECLEN (pattern, i); ++j)
+ {
+ position *subpos = next_position (subpos_ptr, pos,
+ pos_type, j);
+ worklist.safe_push (pattern_pos (XVECEXP (pattern, i, j),
+ subpos));
+ subpos_ptr = &subpos->next;
+ }
+ }
+ break;
+ }
+
+ default:
+ {
+ /* Check that the rtx has the right code. */
+ s = add_decision (s, rtx_test::code (pos), code, false);
+
+ /* Queue a test for the mode if one is specified. */
+ if (GET_MODE (pattern) != VOIDmode)
+ pred_and_mode_tests.safe_push (pattern_pos (pattern, pos));
+
+ /* Push subrtxes onto the worklist. Match nonrtx operands now. */
+ const char *fmt = GET_RTX_FORMAT (code);
+ position **subpos_ptr = &pos->xexps;
+ for (size_t i = 0; fmt[i]; ++i)
+ {
+ position *subpos = next_position (subpos_ptr, pos,
+ POS_XEXP, i);
+ switch (fmt[i])
+ {
+ case 'e': case 'u':
+ worklist.safe_push (pattern_pos (XEXP (pattern, i),
+ subpos));
+ break;
+
+ case 'E':
+ {
+ /* Make sure the vector has the right number of
+ elements. */
+ int length = XVECLEN (pattern, i);
+ s = add_decision (s, rtx_test::veclen (pos),
+ length, false);
+
+ position **subpos2_ptr = &pos->xvecexp0s;
+ for (int j = 0; j < length; j++)
+ {
+ position *subpos2 = next_position (subpos2_ptr, pos,
+ POS_XVECEXP0, j);
+ rtx x = XVECEXP (pattern, i, j);
+ worklist.safe_push (pattern_pos (x, subpos2));
+ subpos2_ptr = &subpos2->next;
+ }
+ break;
+ }
+
+ case 'i':
+ /* Make sure that XINT (X, I) has the right value. */
+ s = add_decision (s, rtx_test::int_field (pos, i),
+ XINT (pattern, i), false);
+ break;
+
+ case 'r':
+ /* Make sure that REGNO (X) has the right value. */
+ gcc_assert (i == 0);
+ s = add_decision (s, rtx_test::regno_field (pos),
+ REGNO (pattern), false);
+ break;
+
+ case 'w':
+ /* Make sure that XWINT (X, I) has the right value. */
+ s = add_decision (s, rtx_test::wide_int_field (pos, i),
+ XWINT (pattern, 0), false);
+ break;
+
+ case 'p':
+ /* We don't have a way of parsing polynomial offsets yet,
+ and hopefully never will. */
+ s = add_decision (s, rtx_test::subreg_field (pos),
+ SUBREG_BYTE (pattern).to_constant (),
+ false);
+ break;
+
+ case '0':
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ subpos_ptr = &subpos->next;
+ }
+ }
+ break;
+ }
+ /* Operands are pushed onto the worklist so that later indices are
+ nearer the top. That's what we want for SETs, since a SET_SRC
+ is a better discriminator than a SET_DEST. In other cases it's
+ usually better to match earlier indices first. This is especially
+ true of PARALLELs, where the first element tends to be the most
+ individual. It's also true for commutative operators, where the
+ canonicalization rules say that the more complex operand should
+ come first. */
+ if (code != SET && worklist.length () > reverse_s)
+ std::reverse (&worklist[0] + reverse_s,
+ &worklist[0] + worklist.length ());
+ }
+
+ /* Sort the predicate and mode tests so that they're in depth-first order.
+ The main goal of this is to put SET_SRC match_operands after SET_DEST
+ match_operands and after mode checks for the enclosing SET_SRC operators
+ (such as the mode of a PLUS in an addition instruction). The latter
+ two types of test can determine the mode exactly, whereas a SET_SRC
+ match_operand often has to cope with the possibility of the operand
+ being a modeless constant integer. E.g. something that matches
+ register_operand (x, SImode) never matches register_operand (x, DImode),
+ but a const_int that matches immediate_operand (x, SImode) also matches
+ immediate_operand (x, DImode). The register_operand cases can therefore
+ be distinguished by a switch on the mode, but the immediate_operand
+ cases can't. */
+ if (pred_and_mode_tests.length () > 1)
+ std::sort (&pred_and_mode_tests[0],
+ &pred_and_mode_tests[0] + pred_and_mode_tests.length ());
+
+ /* Add the mode and predicate tests. */
+ pattern_pos *e;
+ unsigned int i;
+ FOR_EACH_VEC_ELT (pred_and_mode_tests, i, e)
+ {
+ switch (GET_CODE (e->pattern))
+ {
+ case MATCH_PARALLEL:
+ case MATCH_OPERAND:
+ case MATCH_SCRATCH:
+ case MATCH_OPERATOR:
+ {
+ int opno = XINT (e->pattern, 0);
+ num_operands = MAX (num_operands, opno + 1);
+ const char *pred_name = predicate_name (e->pattern);
+ if (pred_name[0])
+ {
+ const struct pred_data *pred = lookup_predicate (pred_name);
+ /* Check the mode first, to distinguish things like SImode
+ and DImode register_operands, as described above. */
+ machine_mode mode = GET_MODE (e->pattern);
+ if (pred && safe_predicate_mode (pred, mode))
+ s = add_decision (s, rtx_test::mode (e->pos), mode, true);
+
+ /* Assign to operands[] first, so that the rtx usually doesn't
+ need to be live across the call to the predicate.
+
+ This shouldn't cause a problem with dirtying the page,
+ since we fully expect to assign to operands[] at some point,
+ and since the caller usually writes to other parts of
+ recog_data anyway. */
+ s = add_decision (s, rtx_test::set_op (e->pos, opno),
+ true, false);
+ s = add_decision (s, rtx_test::predicate (e->pos, pred, mode),
+ true, false);
+ }
+ else
+ /* Historically we've ignored the mode when there's no
+ predicate. Just set up operands[] unconditionally. */
+ s = add_decision (s, rtx_test::set_op (e->pos, opno),
+ true, false);
+ break;
+ }
+
+ default:
+ s = add_decision (s, rtx_test::mode (e->pos),
+ GET_MODE (e->pattern), false);
+ break;
+ }
+ }
+
+ /* Finally add rtx_equal_p checks for duplicated operands. */
+ FOR_EACH_VEC_ELT (dup_tests, i, e)
+ s = add_decision (s, rtx_test::duplicate (e->pos, XINT (e->pattern, 0)),
+ true, false);
+ return s;
+}
+
+/* Add new decisions to S that make it return ACCEPTANCE if:
+
+ (1) the rtx doesn't match anything already matched by S
+ (2) the rtx matches TOP_PATTERN and
+ (3) the C test required by INFO->def is true
+
+ For peephole2, TOP_PATTERN is a SEQUENCE of the instruction patterns
+ to match, otherwise it is a single instruction pattern. */
+
+static void
+match_pattern_1 (state *s, md_rtx_info *info, rtx pattern,
+ acceptance_type acceptance)
+{
+ if (acceptance.type == PEEPHOLE2)
+ {
+ /* Match each individual instruction. */
+ position **subpos_ptr = &peep2_insn_pos_list;
+ int count = 0;
+ for (int i = 0; i < XVECLEN (pattern, 0); ++i)
+ {
+ rtx x = XVECEXP (pattern, 0, i);
+ position *subpos = next_position (subpos_ptr, &root_pos,
+ POS_PEEP2_INSN, count);
+ if (count > 0)
+ s = add_decision (s, rtx_test::peep2_count (count + 1),
+ true, false);
+ s = match_pattern_2 (s, info, subpos, x);
+ subpos_ptr = &subpos->next;
+ count += 1;
+ }
+ acceptance.u.full.u.match_len = count - 1;
+ }
+ else
+ {
+ /* Make the rtx itself. */
+ s = match_pattern_2 (s, info, &root_pos, pattern);
+
+ /* If the match is only valid when extra clobbers are added,
+ make sure we're able to pass that information to the caller. */
+ if (acceptance.type == RECOG && acceptance.u.full.u.num_clobbers)
+ s = add_decision (s, rtx_test::have_num_clobbers (), true, false);
+ }
+
+ /* Make sure that the C test is true. */
+ const char *c_test = get_c_test (info->def);
+ if (maybe_eval_c_test (c_test) != 1)
+ s = add_decision (s, rtx_test::c_test (c_test), true, false);
+
+ /* Accept the pattern. */
+ add_decision (s, rtx_test::accept (acceptance), true, false);
+}
+
+/* Like match_pattern_1, but (if merge_states_p) try to merge the
+ decisions with what's already in S, to reduce the amount of
+ backtracking. */
+
+static void
+match_pattern (state *s, md_rtx_info *info, rtx pattern,
+ acceptance_type acceptance)
+{
+ if (merge_states_p)
+ {
+ state root;
+ /* Add the decisions to a fresh state and then merge the full tree
+ into the existing one. */
+ match_pattern_1 (&root, info, pattern, acceptance);
+ merge_into_state (s, &root);
+ }
+ else
+ match_pattern_1 (s, info, pattern, acceptance);
+}
+
+/* Begin the output file. */
+
+static void
+write_header (void)
+{
+ puts ("\
+/* Generated automatically by the program `genrecog' from the target\n\
+ machine description file. */\n\
+\n\
+#define IN_TARGET_CODE 1\n\
+\n\
+#include \"config.h\"\n\
+#include \"system.h\"\n\
+#include \"coretypes.h\"\n\
+#include \"backend.h\"\n\
+#include \"predict.h\"\n\
+#include \"rtl.h\"\n\
+#include \"memmodel.h\"\n\
+#include \"tm_p.h\"\n\
+#include \"emit-rtl.h\"\n\
+#include \"insn-config.h\"\n\
+#include \"recog.h\"\n\
+#include \"output.h\"\n\
+#include \"flags.h\"\n\
+#include \"df.h\"\n\
+#include \"resource.h\"\n\
+#include \"diagnostic-core.h\"\n\
+#include \"reload.h\"\n\
+#include \"regs.h\"\n\
+#include \"tm-constrs.h\"\n\
+\n");
+
+ puts ("\n\
+/* `recog' contains a decision tree that recognizes whether the rtx\n\
+ X0 is a valid instruction.\n\
+\n\
+ recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
+ returns a nonnegative number which is the insn code number for the\n\
+ pattern that matched. This is the same as the order in the machine\n\
+ description of the entry that matched. This number can be used as an\n\
+ index into `insn_data' and other tables.\n");
+ puts ("\
+ The third parameter to recog is an optional pointer to an int. If\n\
+ present, recog will accept a pattern if it matches except for missing\n\
+ CLOBBER expressions at the end. In that case, the value pointed to by\n\
+ the optional pointer will be set to the number of CLOBBERs that need\n\
+ to be added (it should be initialized to zero by the caller). If it");
+ puts ("\
+ is set nonzero, the caller should allocate a PARALLEL of the\n\
+ appropriate size, copy the initial entries, and call add_clobbers\n\
+ (found in insn-emit.c) to fill in the CLOBBERs.\n\
+");
+
+ puts ("\n\
+ The function split_insns returns 0 if the rtl could not\n\
+ be split or the split rtl as an INSN list if it can be.\n\
+\n\
+ The function peephole2_insns returns 0 if the rtl could not\n\
+ be matched. If there was a match, the new rtl is returned in an INSN list,\n\
+ and LAST_INSN will point to the last recognized insn in the old sequence.\n\
+*/\n\n");
+}
+
+/* Return the C type of a parameter with type TYPE. */
+
+static const char *
+parameter_type_string (parameter::type_enum type)
+{
+ switch (type)
+ {
+ case parameter::UNSET:
+ break;
+
+ case parameter::CODE:
+ return "rtx_code";
+
+ case parameter::MODE:
+ return "machine_mode";
+
+ case parameter::INT:
+ return "int";
+
+ case parameter::UINT:
+ return "unsigned int";
+
+ case parameter::WIDE_INT:
+ return "HOST_WIDE_INT";
+ }
+ gcc_unreachable ();
+}
+
+/* Return true if ACCEPTANCE requires only a single C statement even in
+ a backtracking context. */
+
+static bool
+single_statement_p (const acceptance_type &acceptance)
+{
+ if (acceptance.partial_p)
+ /* We need to handle failures of the subroutine. */
+ return false;
+ switch (acceptance.type)
+ {
+ case SUBPATTERN:
+ case SPLIT:
+ return true;
+
+ case RECOG:
+ /* False if we need to assign to pnum_clobbers. */
+ return acceptance.u.full.u.num_clobbers == 0;
+
+ case PEEPHOLE2:
+ /* We need to assign to pmatch_len_ and handle null returns from the
+ peephole2 routine. */
+ return false;
+ }
+ gcc_unreachable ();
+}
+
+/* Return the C failure value for a routine of type TYPE. */
+
+static const char *
+get_failure_return (routine_type type)
+{
+ switch (type)
+ {
+ case SUBPATTERN:
+ case RECOG:
+ return "-1";
+
+ case SPLIT:
+ case PEEPHOLE2:
+ return "NULL";
+ }
+ gcc_unreachable ();
+}
+
+/* Indicates whether a block of code always returns or whether it can fall
+ through. */
+
+enum exit_state {
+ ES_RETURNED,
+ ES_FALLTHROUGH
+};
+
+/* Information used while writing out code. */
+
+class output_state
+{
+public:
+ /* The type of routine that we're generating. */
+ routine_type type;
+
+ /* Maps position ids to xN variable numbers. The entry is only valid if
+ it is less than the length of VAR_TO_ID, but this holds for every position
+ tested by a state when writing out that state. */
+ auto_vec <unsigned int> id_to_var;
+
+ /* Maps xN variable numbers to position ids. */
+ auto_vec <unsigned int> var_to_id;
+
+ /* Index N is true if variable xN has already been set. */
+ auto_vec <bool> seen_vars;
+};
+
+/* Return true if D is a call to a pattern routine and if there is some X
+ such that the transition for pattern result N goes to a successful return
+ with code X+N. When returning true, set *BASE_OUT to this X and *COUNT_OUT
+ to the number of return values. (We know that every PATTERN decision has
+ a transition for every successful return.) */
+
+static bool
+terminal_pattern_p (decision *d, unsigned int *base_out,
+ unsigned int *count_out)
+{
+ if (d->test.kind != rtx_test::PATTERN)
+ return false;
+ unsigned int base = 0;
+ unsigned int count = 0;
+ for (transition *trans = d->first; trans; trans = trans->next)
+ {
+ if (trans->is_param || trans->labels.length () != 1)
+ return false;
+ decision *subd = trans->to->singleton ();
+ if (!subd || subd->test.kind != rtx_test::ACCEPT)
+ return false;
+ unsigned int this_base = (subd->test.u.acceptance.u.full.code
+ - trans->labels[0]);
+ if (trans == d->first)
+ base = this_base;
+ else if (base != this_base)
+ return false;
+ count += 1;
+ }
+ *base_out = base;
+ *count_out = count;
+ return true;
+}
+
+/* Return true if TEST doesn't test an rtx or if the rtx it tests is
+ already available in state OS. */
+
+static bool
+test_position_available_p (output_state *os, const rtx_test &test)
+{
+ return (!test.pos
+ || test.pos_operand >= 0
+ || os->seen_vars[os->id_to_var[test.pos->id]]);
+}
+
+/* Like printf, but print INDENT spaces at the beginning. */
+
+static void ATTRIBUTE_PRINTF_2
+printf_indent (unsigned int indent, const char *format, ...)
+{
+ va_list ap;
+ va_start (ap, format);
+ printf ("%*s", indent, "");
+ vprintf (format, ap);
+ va_end (ap);
+}
+
+/* Emit code to initialize the variable associated with POS, if it isn't
+ already valid in state OS. Indent each line by INDENT spaces. Update
+ OS with the new state. */
+
+static void
+change_state (output_state *os, position *pos, unsigned int indent)
+{
+ unsigned int var = os->id_to_var[pos->id];
+ gcc_assert (var < os->var_to_id.length () && os->var_to_id[var] == pos->id);
+ if (os->seen_vars[var])
+ return;
+ switch (pos->type)
+ {
+ case POS_PEEP2_INSN:
+ printf_indent (indent, "x%d = PATTERN (peep2_next_insn (%d));\n",
+ var, pos->arg);
+ break;
+
+ case POS_XEXP:
+ change_state (os, pos->base, indent);
+ printf_indent (indent, "x%d = XEXP (x%d, %d);\n",
+ var, os->id_to_var[pos->base->id], pos->arg);
+ break;
+
+ case POS_XVECEXP0:
+ change_state (os, pos->base, indent);
+ printf_indent (indent, "x%d = XVECEXP (x%d, 0, %d);\n",
+ var, os->id_to_var[pos->base->id], pos->arg);
+ break;
+ }
+ os->seen_vars[var] = true;
+}
+
+/* Print the enumerator constant for CODE -- the upcase version of
+ the name. */
+
+static void
+print_code (enum rtx_code code)
+{
+ const char *p;
+ for (p = GET_RTX_NAME (code); *p; p++)
+ putchar (TOUPPER (*p));
+}
+
+/* Emit a uint64_t as an integer constant expression. We need to take
+ special care to avoid "decimal constant is so large that it is unsigned"
+ warnings in the resulting code. */
+
+static void
+print_host_wide_int (uint64_t val)
+{
+ uint64_t min = uint64_t (1) << (HOST_BITS_PER_WIDE_INT - 1);
+ if (val == min)
+ printf ("(" HOST_WIDE_INT_PRINT_DEC_C " - 1)", val + 1);
+ else
+ printf (HOST_WIDE_INT_PRINT_DEC_C, val);
+}
+
+/* Print the C expression for actual parameter PARAM. */
+
+static void
+print_parameter_value (const parameter ¶m)
+{
+ if (param.is_param)
+ printf ("i%d", (int) param.value + 1);
+ else
+ switch (param.type)
+ {
+ case parameter::UNSET:
+ gcc_unreachable ();
+ break;
+
+ case parameter::CODE:
+ print_code ((enum rtx_code) param.value);
+ break;
+
+ case parameter::MODE:
+ printf ("E_%smode", GET_MODE_NAME ((machine_mode) param.value));
+ break;
+
+ case parameter::INT:
+ printf ("%d", (int) param.value);
+ break;
+
+ case parameter::UINT:
+ printf ("%u", (unsigned int) param.value);
+ break;
- new = rtx_alloc (PARALLEL);
- XVEC (new, 0) = rtvec_alloc (i);
- for (j = i - 1; j >= 0; j--)
- XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
- }
+ case parameter::WIDE_INT:
+ print_host_wide_int (param.value);
+ break;
+ }
+}
- /* Recognize it. */
- memset (&clobber_head, 0, sizeof(clobber_head));
- last = add_to_sequence (new, &clobber_head, "", type, 1);
+/* Print the C expression for the rtx tested by TEST. */
- /* Find the end of the test chain on the last node. */
- for (test = last->tests; test->next; test = test->next)
- continue;
+static void
+print_test_rtx (output_state *os, const rtx_test &test)
+{
+ if (test.pos_operand >= 0)
+ printf ("operands[%d]", test.pos_operand);
+ else
+ printf ("x%d", os->id_to_var[test.pos->id]);
+}
- /* We definitely have a new test to add -- create a new
- node if needed. */
- place = &test->next;
- if (test->type == DT_accept_op)
- {
- last = new_decision ("", &last->success);
- place = &last->tests;
- }
+/* Print the C expression for non-boolean test TEST. */
- /* Skip the C test if it's known to be true at compile
- time. */
- if (truth == -1)
- {
- test = new_decision_test (DT_c_test, &place);
- test->u.c_test = c_test;
- }
+static void
+print_nonbool_test (output_state *os, const rtx_test &test)
+{
+ switch (test.kind)
+ {
+ case rtx_test::CODE:
+ printf ("GET_CODE (");
+ print_test_rtx (os, test);
+ printf (")");
+ break;
- test = new_decision_test (DT_accept_insn, &place);
- test->u.insn.code_number = next_insn_code;
- test->u.insn.lineno = pattern_lineno;
- test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
+ case rtx_test::MODE:
+ printf ("GET_MODE (");
+ print_test_rtx (os, test);
+ printf (")");
+ break;
- merge_trees (&head, &clobber_head);
- }
- }
+ case rtx_test::VECLEN:
+ printf ("XVECLEN (");
+ print_test_rtx (os, test);
+ printf (", 0)");
break;
- case SPLIT:
- /* Define the subroutine we will call below and emit in genemit. */
- printf ("extern rtx gen_split_%d (rtx, rtx *);\n", next_insn_code);
+ case rtx_test::INT_FIELD:
+ printf ("XINT (");
+ print_test_rtx (os, test);
+ printf (", %d)", test.u.opno);
break;
- case PEEPHOLE2:
- /* Define the subroutine we will call below and emit in genemit. */
- printf ("extern rtx gen_peephole2_%d (rtx, rtx *);\n",
- next_insn_code);
+ case rtx_test::REGNO_FIELD:
+ printf ("REGNO (");
+ print_test_rtx (os, test);
+ printf (")");
+ break;
+
+ case rtx_test::SUBREG_FIELD:
+ printf ("SUBREG_BYTE (");
+ print_test_rtx (os, test);
+ printf (")");
break;
+
+ case rtx_test::WIDE_INT_FIELD:
+ printf ("XWINT (");
+ print_test_rtx (os, test);
+ printf (", %d)", test.u.opno);
+ break;
+
+ case rtx_test::PATTERN:
+ {
+ pattern_routine *routine = test.u.pattern->routine;
+ printf ("pattern%d (", routine->pattern_id);
+ const char *sep = "";
+ if (test.pos)
+ {
+ print_test_rtx (os, test);
+ sep = ", ";
+ }
+ if (routine->insn_p)
+ {
+ printf ("%sinsn", sep);
+ sep = ", ";
+ }
+ if (routine->pnum_clobbers_p)
+ {
+ printf ("%spnum_clobbers", sep);
+ sep = ", ";
+ }
+ for (unsigned int i = 0; i < test.u.pattern->params.length (); ++i)
+ {
+ fputs (sep, stdout);
+ print_parameter_value (test.u.pattern->params[i]);
+ sep = ", ";
+ }
+ printf (")");
+ break;
+ }
+
+ case rtx_test::PEEP2_COUNT:
+ case rtx_test::VECLEN_GE:
+ case rtx_test::SAVED_CONST_INT:
+ case rtx_test::DUPLICATE:
+ case rtx_test::PREDICATE:
+ case rtx_test::SET_OP:
+ case rtx_test::HAVE_NUM_CLOBBERS:
+ case rtx_test::C_TEST:
+ case rtx_test::ACCEPT:
+ gcc_unreachable ();
}
+}
- return head;
+/* IS_PARAM and LABEL are taken from a transition whose source
+ decision performs TEST. Print the C code for the label. */
+
+static void
+print_label_value (const rtx_test &test, bool is_param, uint64_t value)
+{
+ print_parameter_value (parameter (transition_parameter_type (test.kind),
+ is_param, value));
}
+/* If IS_PARAM, print code to compare TEST with the C variable i<VALUE+1>.
+ If !IS_PARAM, print code to compare TEST with the C constant VALUE.
+ Test for inequality if INVERT_P, otherwise test for equality. */
+
static void
-process_tree (struct decision_head *head, enum routine_type subroutine_type)
+print_test (output_state *os, const rtx_test &test, bool is_param,
+ uint64_t value, bool invert_p)
{
- if (head->first == NULL)
+ switch (test.kind)
{
- /* We can elide peephole2_insns, but not recog or split_insns. */
- if (subroutine_type == PEEPHOLE2)
- return;
+ /* Handle the non-boolean TESTs. */
+ case rtx_test::CODE:
+ case rtx_test::MODE:
+ case rtx_test::VECLEN:
+ case rtx_test::REGNO_FIELD:
+ case rtx_test::INT_FIELD:
+ case rtx_test::WIDE_INT_FIELD:
+ case rtx_test::PATTERN:
+ print_nonbool_test (os, test);
+ printf (" %s ", invert_p ? "!=" : "==");
+ print_label_value (test, is_param, value);
+ break;
+
+ case rtx_test::SUBREG_FIELD:
+ printf ("%s (", invert_p ? "maybe_ne" : "known_eq");
+ print_nonbool_test (os, test);
+ printf (", ");
+ print_label_value (test, is_param, value);
+ printf (")");
+ break;
+
+ case rtx_test::SAVED_CONST_INT:
+ gcc_assert (!is_param && value == 1);
+ print_test_rtx (os, test);
+ printf (" %s const_int_rtx[MAX_SAVED_CONST_INT + ",
+ invert_p ? "!=" : "==");
+ print_parameter_value (parameter (parameter::INT,
+ test.u.integer.is_param,
+ test.u.integer.value));
+ printf ("]");
+ break;
+
+ case rtx_test::PEEP2_COUNT:
+ gcc_assert (!is_param && value == 1);
+ printf ("peep2_current_count %s %d", invert_p ? "<" : ">=",
+ test.u.min_len);
+ break;
+
+ case rtx_test::VECLEN_GE:
+ gcc_assert (!is_param && value == 1);
+ printf ("XVECLEN (");
+ print_test_rtx (os, test);
+ printf (", 0) %s %d", invert_p ? "<" : ">=", test.u.min_len);
+ break;
+
+ case rtx_test::PREDICATE:
+ gcc_assert (!is_param && value == 1);
+ printf ("%s%s (", invert_p ? "!" : "", test.u.predicate.data->name);
+ print_test_rtx (os, test);
+ printf (", ");
+ print_parameter_value (parameter (parameter::MODE,
+ test.u.predicate.mode_is_param,
+ test.u.predicate.mode));
+ printf (")");
+ break;
+
+ case rtx_test::DUPLICATE:
+ gcc_assert (!is_param && value == 1);
+ printf ("%srtx_equal_p (", invert_p ? "!" : "");
+ print_test_rtx (os, test);
+ printf (", operands[%d])", test.u.opno);
+ break;
+
+ case rtx_test::HAVE_NUM_CLOBBERS:
+ gcc_assert (!is_param && value == 1);
+ printf ("pnum_clobbers %s NULL", invert_p ? "==" : "!=");
+ break;
+
+ case rtx_test::C_TEST:
+ gcc_assert (!is_param && value == 1);
+ if (invert_p)
+ printf ("!");
+ rtx_reader_ptr->print_c_condition (test.u.string);
+ break;
+
+ case rtx_test::ACCEPT:
+ case rtx_test::SET_OP:
+ gcc_unreachable ();
}
- else
- {
- factor_tests (head);
+}
- next_subroutine_number = 0;
- break_out_subroutines (head, 1);
- find_afterward (head, NULL);
+static exit_state print_decision (output_state *, decision *,
+ unsigned int, bool);
- /* We run this after find_afterward, because find_afterward needs
- the redundant DT_mode tests on predicates to determine whether
- two tests can both be true or not. */
- simplify_tests(head);
+/* Print code to perform S, indent each line by INDENT spaces.
+ IS_FINAL is true if there are no fallback decisions to test on failure;
+ if the state fails then the entire routine fails. */
- write_subroutines (head, subroutine_type);
+static exit_state
+print_state (output_state *os, state *s, unsigned int indent, bool is_final)
+{
+ exit_state es = ES_FALLTHROUGH;
+ for (decision *d = s->first; d; d = d->next)
+ es = print_decision (os, d, indent, is_final && !d->next);
+ if (es != ES_RETURNED && is_final)
+ {
+ printf_indent (indent, "return %s;\n", get_failure_return (os->type));
+ es = ES_RETURNED;
}
+ return es;
+}
+
+/* Print the code for subroutine call ACCEPTANCE (for which partial_p
+ is known to be true). Return the C condition that indicates a successful
+ match. */
+
+static const char *
+print_subroutine_call (const acceptance_type &acceptance)
+{
+ switch (acceptance.type)
+ {
+ case SUBPATTERN:
+ gcc_unreachable ();
+
+ case RECOG:
+ printf ("recog_%d (x1, insn, pnum_clobbers)",
+ acceptance.u.subroutine_id);
+ return ">= 0";
+
+ case SPLIT:
+ printf ("split_%d (x1, insn)", acceptance.u.subroutine_id);
+ return "!= NULL_RTX";
- write_subroutine (head, subroutine_type);
+ case PEEPHOLE2:
+ printf ("peephole2_%d (x1, insn, pmatch_len_)",
+ acceptance.u.subroutine_id);
+ return "!= NULL_RTX";
+ }
+ gcc_unreachable ();
}
-\f
-extern int main (int, char **);
-int
-main (int argc, char **argv)
+/* Print code for the successful match described by ACCEPTANCE.
+ INDENT and IS_FINAL are as for print_state. */
+
+static exit_state
+print_acceptance (const acceptance_type &acceptance, unsigned int indent,
+ bool is_final)
{
- rtx desc;
- struct decision_head recog_tree, split_tree, peephole2_tree, h;
+ if (acceptance.partial_p)
+ {
+ /* Defer the rest of the match to a subroutine. */
+ if (is_final)
+ {
+ printf_indent (indent, "return ");
+ print_subroutine_call (acceptance);
+ printf (";\n");
+ return ES_RETURNED;
+ }
+ else
+ {
+ printf_indent (indent, "res = ");
+ const char *res_test = print_subroutine_call (acceptance);
+ printf (";\n");
+ printf_indent (indent, "if (res %s)\n", res_test);
+ printf_indent (indent + 2, "return res;\n");
+ return ES_FALLTHROUGH;
+ }
+ }
+ switch (acceptance.type)
+ {
+ case SUBPATTERN:
+ printf_indent (indent, "return %d;\n", acceptance.u.full.code);
+ return ES_RETURNED;
- progname = "genrecog";
+ case RECOG:
+ if (acceptance.u.full.u.num_clobbers != 0)
+ printf_indent (indent, "*pnum_clobbers = %d;\n",
+ acceptance.u.full.u.num_clobbers);
+ printf_indent (indent, "return %d; /* %s */\n", acceptance.u.full.code,
+ get_insn_name (acceptance.u.full.code));
+ return ES_RETURNED;
+
+ case SPLIT:
+ printf_indent (indent, "return gen_split_%d (insn, operands);\n",
+ acceptance.u.full.code);
+ return ES_RETURNED;
+
+ case PEEPHOLE2:
+ printf_indent (indent, "*pmatch_len_ = %d;\n",
+ acceptance.u.full.u.match_len);
+ if (is_final)
+ {
+ printf_indent (indent, "return gen_peephole2_%d (insn, operands);\n",
+ acceptance.u.full.code);
+ return ES_RETURNED;
+ }
+ else
+ {
+ printf_indent (indent, "res = gen_peephole2_%d (insn, operands);\n",
+ acceptance.u.full.code);
+ printf_indent (indent, "if (res != NULL_RTX)\n");
+ printf_indent (indent + 2, "return res;\n");
+ return ES_FALLTHROUGH;
+ }
+ }
+ gcc_unreachable ();
+}
+
+/* Print code to perform D. INDENT and IS_FINAL are as for print_state. */
- memset (&recog_tree, 0, sizeof recog_tree);
- memset (&split_tree, 0, sizeof split_tree);
- memset (&peephole2_tree, 0, sizeof peephole2_tree);
+static exit_state
+print_decision (output_state *os, decision *d, unsigned int indent,
+ bool is_final)
+{
+ uint64_t label;
+ unsigned int base, count;
- if (argc <= 1)
- fatal ("no input file name");
+ /* Make sure the rtx under test is available either in operands[] or
+ in an xN variable. */
+ if (d->test.pos && d->test.pos_operand < 0)
+ change_state (os, d->test.pos, indent);
- if (init_md_reader_args (argc, argv) != SUCCESS_EXIT_CODE)
- return (FATAL_EXIT_CODE);
+ /* Look for cases where a pattern routine P1 calls another pattern routine
+ P2 and where P1 returns X + BASE whenever P2 returns X. If IS_FINAL
+ is true and BASE is zero we can simply use:
- next_insn_code = 0;
- next_index = 0;
+ return patternN (...);
- write_header ();
+ Otherwise we can use:
- /* Read the machine description. */
+ res = patternN (...);
+ if (res >= 0)
+ return res + BASE;
- while (1)
+ However, if BASE is nonzero and patternN only returns 0 or -1,
+ the usual "return BASE;" is better than "return res + BASE;".
+ If BASE is zero, "return res;" should be better than "return 0;",
+ since no assignment to the return register is required. */
+ if (os->type == SUBPATTERN
+ && terminal_pattern_p (d, &base, &count)
+ && (base == 0 || count > 1))
{
- desc = read_md_rtx (&pattern_lineno, &next_insn_code);
- if (desc == NULL)
- break;
+ if (is_final && base == 0)
+ {
+ printf_indent (indent, "return ");
+ print_nonbool_test (os, d->test);
+ printf ("; /* [-1, %d] */\n", count - 1);
+ return ES_RETURNED;
+ }
+ else
+ {
+ printf_indent (indent, "res = ");
+ print_nonbool_test (os, d->test);
+ printf (";\n");
+ printf_indent (indent, "if (res >= 0)\n");
+ printf_indent (indent + 2, "return res");
+ if (base != 0)
+ printf (" + %d", base);
+ printf ("; /* [%d, %d] */\n", base, base + count - 1);
+ return ES_FALLTHROUGH;
+ }
+ }
+ else if (d->test.kind == rtx_test::ACCEPT)
+ return print_acceptance (d->test.u.acceptance, indent, is_final);
+ else if (d->test.kind == rtx_test::SET_OP)
+ {
+ printf_indent (indent, "operands[%d] = ", d->test.u.opno);
+ print_test_rtx (os, d->test);
+ printf (";\n");
+ return print_state (os, d->singleton ()->to, indent, is_final);
+ }
+ /* Handle decisions with a single transition and a single transition
+ label. */
+ else if (d->if_statement_p (&label))
+ {
+ transition *trans = d->singleton ();
+ if (mark_optional_transitions_p && trans->optional)
+ printf_indent (indent, "/* OPTIONAL IF */\n");
+
+ /* Print the condition associated with TRANS. Invert it if IS_FINAL,
+ so that we return immediately on failure and fall through on
+ success. */
+ printf_indent (indent, "if (");
+ print_test (os, d->test, trans->is_param, label, is_final);
+
+ /* Look for following states that would be handled by this code
+ on recursion. If they don't need any preparatory statements,
+ include them in the current "if" statement rather than creating
+ a new one. */
+ for (;;)
+ {
+ d = trans->to->singleton ();
+ if (!d
+ || d->test.kind == rtx_test::ACCEPT
+ || d->test.kind == rtx_test::SET_OP
+ || !d->if_statement_p (&label)
+ || !test_position_available_p (os, d->test))
+ break;
+ trans = d->first;
+ printf ("\n");
+ if (mark_optional_transitions_p && trans->optional)
+ printf_indent (indent + 4, "/* OPTIONAL IF */\n");
+ printf_indent (indent + 4, "%s ", is_final ? "||" : "&&");
+ print_test (os, d->test, trans->is_param, label, is_final);
+ }
+ printf (")\n");
- if (GET_CODE (desc) == DEFINE_INSN)
+ /* Print the conditional code with INDENT + 2 and the fallthrough
+ code with indent INDENT. */
+ state *to = trans->to;
+ if (is_final)
{
- h = make_insn_sequence (desc, RECOG);
- merge_trees (&recog_tree, &h);
+ /* We inverted the condition above, so return failure in the
+ "if" body and fall through to the target of the transition. */
+ printf_indent (indent + 2, "return %s;\n",
+ get_failure_return (os->type));
+ return print_state (os, to, indent, is_final);
}
- else if (GET_CODE (desc) == DEFINE_SPLIT)
+ else if (to->singleton ()
+ && to->first->test.kind == rtx_test::ACCEPT
+ && single_statement_p (to->first->test.u.acceptance))
{
- h = make_insn_sequence (desc, SPLIT);
- merge_trees (&split_tree, &h);
+ /* The target of the transition is a simple "return" statement.
+ It doesn't need any braces and doesn't fall through. */
+ if (print_acceptance (to->first->test.u.acceptance,
+ indent + 2, true) != ES_RETURNED)
+ gcc_unreachable ();
+ return ES_FALLTHROUGH;
}
- else if (GET_CODE (desc) == DEFINE_PEEPHOLE2)
+ else
{
- h = make_insn_sequence (desc, PEEPHOLE2);
- merge_trees (&peephole2_tree, &h);
+ /* The general case. Output code for the target of the transition
+ in braces. This will not invalidate any of the xN variables
+ that are already valid, but we mustn't rely on any that are
+ set by the "if" body. */
+ auto_vec <bool, 32> old_seen;
+ old_seen.safe_splice (os->seen_vars);
+
+ printf_indent (indent + 2, "{\n");
+ print_state (os, trans->to, indent + 4, is_final);
+ printf_indent (indent + 2, "}\n");
+
+ os->seen_vars.truncate (0);
+ os->seen_vars.splice (old_seen);
+ return ES_FALLTHROUGH;
}
+ }
+ else
+ {
+ /* Output the decision as a switch statement. */
+ printf_indent (indent, "switch (");
+ print_nonbool_test (os, d->test);
+ printf (")\n");
+
+ /* Each case statement starts with the same set of valid variables.
+ These are also the only variables will be valid on fallthrough. */
+ auto_vec <bool, 32> old_seen;
+ old_seen.safe_splice (os->seen_vars);
- next_index++;
+ printf_indent (indent + 2, "{\n");
+ for (transition *trans = d->first; trans; trans = trans->next)
+ {
+ gcc_assert (!trans->is_param);
+ if (mark_optional_transitions_p && trans->optional)
+ printf_indent (indent + 2, "/* OPTIONAL CASE */\n");
+ for (int_set::iterator j = trans->labels.begin ();
+ j != trans->labels.end (); ++j)
+ {
+ printf_indent (indent + 2, "case ");
+ print_label_value (d->test, trans->is_param, *j);
+ printf (":\n");
+ }
+ if (print_state (os, trans->to, indent + 4, is_final))
+ {
+ /* The state can fall through. Add an explicit break. */
+ gcc_assert (!is_final);
+ printf_indent (indent + 4, "break;\n");
+ }
+ printf ("\n");
+
+ /* Restore the original set of valid variables. */
+ os->seen_vars.truncate (0);
+ os->seen_vars.splice (old_seen);
+ }
+ /* Add a default case. */
+ printf_indent (indent + 2, "default:\n");
+ if (is_final)
+ printf_indent (indent + 4, "return %s;\n",
+ get_failure_return (os->type));
+ else
+ printf_indent (indent + 4, "break;\n");
+ printf_indent (indent + 2, "}\n");
+ return is_final ? ES_RETURNED : ES_FALLTHROUGH;
}
+}
- if (error_count)
- return FATAL_EXIT_CODE;
+/* Make sure that OS has a position variable for POS. ROOT_P is true if
+ POS is the root position for the routine. */
- puts ("\n\n");
+static void
+assign_position_var (output_state *os, position *pos, bool root_p)
+{
+ unsigned int idx = os->id_to_var[pos->id];
+ if (idx < os->var_to_id.length () && os->var_to_id[idx] == pos->id)
+ return;
+ if (!root_p && pos->type != POS_PEEP2_INSN)
+ assign_position_var (os, pos->base, false);
+ os->id_to_var[pos->id] = os->var_to_id.length ();
+ os->var_to_id.safe_push (pos->id);
+}
- process_tree (&recog_tree, RECOG);
- process_tree (&split_tree, SPLIT);
- process_tree (&peephole2_tree, PEEPHOLE2);
+/* Make sure that OS has the position variables required by S. */
- fflush (stdout);
- return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
+static void
+assign_position_vars (output_state *os, state *s)
+{
+ for (decision *d = s->first; d; d = d->next)
+ {
+ /* Positions associated with operands can be read from the
+ operands[] array. */
+ if (d->test.pos && d->test.pos_operand < 0)
+ assign_position_var (os, d->test.pos, false);
+ for (transition *trans = d->first; trans; trans = trans->next)
+ assign_position_vars (os, trans->to);
+ }
}
-\f
-/* Define this so we can link with print-rtl.o to get debug_rtx function. */
-const char *
-get_insn_name (int code)
+
+/* Print the open brace and variable definitions for a routine that
+ implements S. ROOT is the deepest rtx from which S can access all
+ relevant parts of the first instruction it matches. Initialize OS
+ so that every relevant position has an rtx variable xN and so that
+ only ROOT's variable has a valid value. */
+
+static void
+print_subroutine_start (output_state *os, state *s, position *root)
{
- if (code < insn_name_ptr_size)
- return insn_name_ptr[code];
+ printf ("{\n rtx * const operands ATTRIBUTE_UNUSED"
+ " = &recog_data.operand[0];\n");
+ os->var_to_id.truncate (0);
+ os->seen_vars.truncate (0);
+ if (root)
+ {
+ /* Create a fake entry for position 0 so that an id_to_var of 0
+ is always invalid. This also makes the xN variables naturally
+ 1-based rather than 0-based. */
+ os->var_to_id.safe_push (num_positions);
+
+ /* Associate ROOT with x1. */
+ assign_position_var (os, root, true);
+
+ /* Assign xN variables to all other relevant positions. */
+ assign_position_vars (os, s);
+
+ /* Output the variable declarations (except for ROOT's, which is
+ passed in as a parameter). */
+ unsigned int num_vars = os->var_to_id.length ();
+ if (num_vars > 2)
+ {
+ for (unsigned int i = 2; i < num_vars; ++i)
+ /* Print 8 rtx variables to a line. */
+ printf ("%s x%d",
+ i == 2 ? " rtx" : (i - 2) % 8 == 0 ? ";\n rtx" : ",", i);
+ printf (";\n");
+ }
+
+ /* Say that x1 is valid and the rest aren't. */
+ os->seen_vars.safe_grow_cleared (num_vars);
+ os->seen_vars[1] = true;
+ }
+ if (os->type == SUBPATTERN || os->type == RECOG)
+ printf (" int res ATTRIBUTE_UNUSED;\n");
else
- return NULL;
+ printf (" rtx_insn *res ATTRIBUTE_UNUSED;\n");
}
+/* Output the definition of pattern routine ROUTINE. */
+
static void
-record_insn_name (int code, const char *name)
+print_pattern (output_state *os, pattern_routine *routine)
{
- static const char *last_real_name = "insn";
- static int last_real_code = 0;
- char *new;
-
- if (insn_name_ptr_size <= code)
+ printf ("\nstatic int\npattern%d (", routine->pattern_id);
+ const char *sep = "";
+ /* Add the top-level rtx parameter, if any. */
+ if (routine->pos)
{
- int new_size;
- new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
- insn_name_ptr = xrealloc (insn_name_ptr, sizeof(char *) * new_size);
- memset (insn_name_ptr + insn_name_ptr_size, 0,
- sizeof(char *) * (new_size - insn_name_ptr_size));
- insn_name_ptr_size = new_size;
+ printf ("%srtx x1", sep);
+ sep = ", ";
}
-
- if (!name || name[0] == '\0')
+ /* Add the optional parameters. */
+ if (routine->insn_p)
{
- new = xmalloc (strlen (last_real_name) + 10);
- sprintf (new, "%s+%d", last_real_name, code - last_real_code);
+ /* We can't easily tell whether a C condition actually reads INSN,
+ so add an ATTRIBUTE_UNUSED just in case. */
+ printf ("%srtx_insn *insn ATTRIBUTE_UNUSED", sep);
+ sep = ", ";
}
- else
+ if (routine->pnum_clobbers_p)
{
- last_real_name = new = xstrdup (name);
- last_real_code = code;
+ printf ("%sint *pnum_clobbers", sep);
+ sep = ", ";
}
-
- insn_name_ptr[code] = new;
+ /* Add the "i" parameters. */
+ for (unsigned int i = 0; i < routine->param_types.length (); ++i)
+ {
+ printf ("%s%s i%d", sep,
+ parameter_type_string (routine->param_types[i]), i + 1);
+ sep = ", ";
+ }
+ printf (")\n");
+ os->type = SUBPATTERN;
+ print_subroutine_start (os, routine->s, routine->pos);
+ print_state (os, routine->s, 2, true);
+ printf ("}\n");
}
-\f
+
+/* Output a routine of type TYPE that implements S. PROC_ID is the
+ number of the subroutine associated with S, or 0 if S is the main
+ routine. */
+
static void
-debug_decision_2 (struct decision_test *test)
+print_subroutine (output_state *os, state *s, int proc_id)
{
- switch (test->type)
+ printf ("\n");
+ switch (os->type)
{
- case DT_mode:
- fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
- break;
- case DT_code:
- fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
- break;
- case DT_veclen:
- fprintf (stderr, "veclen=%d", test->u.veclen);
- break;
- case DT_elt_zero_int:
- fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
- break;
- case DT_elt_one_int:
- fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
- break;
- case DT_elt_zero_wide:
- fprintf (stderr, "elt0_w=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
- break;
- case DT_elt_zero_wide_safe:
- fprintf (stderr, "elt0_ws=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
- break;
- case DT_veclen_ge:
- fprintf (stderr, "veclen>=%d", test->u.veclen);
- break;
- case DT_dup:
- fprintf (stderr, "dup=%d", test->u.dup);
- break;
- case DT_pred:
- fprintf (stderr, "pred=(%s,%s)",
- test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
- break;
- case DT_c_test:
- {
- char sub[16+4];
- strncpy (sub, test->u.c_test, sizeof(sub));
- memcpy (sub+16, "...", 4);
- fprintf (stderr, "c_test=\"%s\"", sub);
- }
- break;
- case DT_accept_op:
- fprintf (stderr, "A_op=%d", test->u.opno);
+ case SUBPATTERN:
+ gcc_unreachable ();
+
+ case RECOG:
+ if (proc_id)
+ printf ("static int\nrecog_%d", proc_id);
+ else
+ printf ("int\nrecog");
+ printf (" (rtx x1 ATTRIBUTE_UNUSED,\n"
+ "\trtx_insn *insn ATTRIBUTE_UNUSED,\n"
+ "\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n");
break;
- case DT_accept_insn:
- fprintf (stderr, "A_insn=(%d,%d)",
- test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
+
+ case SPLIT:
+ if (proc_id)
+ printf ("static rtx_insn *\nsplit_%d", proc_id);
+ else
+ printf ("rtx_insn *\nsplit_insns");
+ printf (" (rtx x1 ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED)\n");
break;
- default:
- abort ();
+ case PEEPHOLE2:
+ if (proc_id)
+ printf ("static rtx_insn *\npeephole2_%d", proc_id);
+ else
+ printf ("rtx_insn *\npeephole2_insns");
+ printf (" (rtx x1 ATTRIBUTE_UNUSED,\n"
+ "\trtx_insn *insn ATTRIBUTE_UNUSED,\n"
+ "\tint *pmatch_len_ ATTRIBUTE_UNUSED)\n");
+ break;
+ }
+ print_subroutine_start (os, s, &root_pos);
+ if (proc_id == 0)
+ {
+ printf (" recog_data.insn = NULL;\n");
}
+ print_state (os, s, 2, true);
+ printf ("}\n");
}
+/* Print out a routine of type TYPE that performs ROOT. */
+
static void
-debug_decision_1 (struct decision *d, int indent)
+print_subroutine_group (output_state *os, routine_type type, state *root)
{
- int i;
- struct decision_test *test;
-
- if (d == NULL)
+ os->type = type;
+ if (use_subroutines_p)
{
- for (i = 0; i < indent; ++i)
- putc (' ', stderr);
- fputs ("(nil)\n", stderr);
- return;
+ /* Split ROOT up into smaller pieces, both for readability and to
+ help the compiler. */
+ auto_vec <state *> subroutines;
+ find_subroutines (type, root, subroutines);
+
+ /* Output the subroutines (but not ROOT itself). */
+ unsigned int i;
+ state *s;
+ FOR_EACH_VEC_ELT (subroutines, i, s)
+ print_subroutine (os, s, i + 1);
}
+ /* Output the main routine. */
+ print_subroutine (os, root, 0);
+}
- for (i = 0; i < indent; ++i)
- putc (' ', stderr);
+/* Return the rtx pattern for the list of rtxes in a define_peephole2. */
- putc ('{', stderr);
- test = d->tests;
- if (test)
+static rtx
+get_peephole2_pattern (md_rtx_info *info)
+{
+ int i, j;
+ rtvec vec = XVEC (info->def, 0);
+ rtx pattern = rtx_alloc (SEQUENCE);
+ XVEC (pattern, 0) = rtvec_alloc (GET_NUM_ELEM (vec));
+ for (i = j = 0; i < GET_NUM_ELEM (vec); i++)
{
- debug_decision_2 (test);
- while ((test = test->next) != NULL)
+ rtx x = RTVEC_ELT (vec, i);
+ /* Ignore scratch register requirements. */
+ if (GET_CODE (x) != MATCH_SCRATCH && GET_CODE (x) != MATCH_DUP)
{
- fputs (" + ", stderr);
- debug_decision_2 (test);
+ XVECEXP (pattern, 0, j) = x;
+ j++;
}
}
- fprintf (stderr, "} %d n %d a %d\n", d->number,
- (d->next ? d->next->number : -1),
- (d->afterward ? d->afterward->number : -1));
+ XVECLEN (pattern, 0) = j;
+ if (j == 0)
+ error_at (info->loc, "empty define_peephole2");
+ return pattern;
}
-static void
-debug_decision_0 (struct decision *d, int indent, int maxdepth)
+/* Return true if *PATTERN_PTR is a PARALLEL in which at least one trailing
+ rtx can be added automatically by add_clobbers. If so, update
+ *ACCEPTANCE_PTR so that its num_clobbers field contains the number
+ of such trailing rtxes and update *PATTERN_PTR so that it contains
+ the pattern without those rtxes. */
+
+static bool
+remove_clobbers (acceptance_type *acceptance_ptr, rtx *pattern_ptr)
{
- struct decision *n;
int i;
+ rtx new_pattern;
- if (maxdepth < 0)
- return;
- if (d == NULL)
+ /* Find the last non-clobber in the parallel. */
+ rtx pattern = *pattern_ptr;
+ for (i = XVECLEN (pattern, 0); i > 0; i--)
{
- for (i = 0; i < indent; ++i)
- putc (' ', stderr);
- fputs ("(nil)\n", stderr);
- return;
+ rtx x = XVECEXP (pattern, 0, i - 1);
+ if (GET_CODE (x) != CLOBBER
+ || (!REG_P (XEXP (x, 0))
+ && GET_CODE (XEXP (x, 0)) != MATCH_SCRATCH))
+ break;
}
- debug_decision_1 (d, indent);
- for (n = d->success.first; n ; n = n->next)
- debug_decision_0 (n, indent + 2, maxdepth - 1);
-}
+ if (i == XVECLEN (pattern, 0))
+ return false;
-void
-debug_decision (struct decision *d)
-{
- debug_decision_0 (d, 0, 1000000);
+ /* Build a similar insn without the clobbers. */
+ if (i == 1)
+ new_pattern = XVECEXP (pattern, 0, 0);
+ else
+ {
+ new_pattern = rtx_alloc (PARALLEL);
+ XVEC (new_pattern, 0) = rtvec_alloc (i);
+ for (int j = 0; j < i; ++j)
+ XVECEXP (new_pattern, 0, j) = XVECEXP (pattern, 0, j);
+ }
+
+ /* Recognize it. */
+ acceptance_ptr->u.full.u.num_clobbers = XVECLEN (pattern, 0) - i;
+ *pattern_ptr = new_pattern;
+ return true;
}
-void
-debug_decision_list (struct decision *d)
+int
+main (int argc, const char **argv)
{
- while (d)
+ state insn_root, split_root, peephole2_root;
+
+ progname = "genrecog";
+
+ if (!init_rtx_reader_args (argc, argv))
+ return (FATAL_EXIT_CODE);
+
+ write_header ();
+
+ /* Read the machine description. */
+
+ md_rtx_info info;
+ while (read_md_rtx (&info))
+ {
+ rtx def = info.def;
+
+ acceptance_type acceptance;
+ acceptance.partial_p = false;
+ acceptance.u.full.code = info.index;
+
+ rtx pattern;
+ switch (GET_CODE (def))
+ {
+ case DEFINE_INSN:
+ {
+ /* Match the instruction in the original .md form. */
+ acceptance.type = RECOG;
+ acceptance.u.full.u.num_clobbers = 0;
+ pattern = add_implicit_parallel (XVEC (def, 1));
+ validate_pattern (pattern, &info, NULL_RTX, 0);
+ match_pattern (&insn_root, &info, pattern, acceptance);
+
+ /* If the pattern is a PARALLEL with trailing CLOBBERs,
+ allow recog_for_combine to match without the clobbers. */
+ if (GET_CODE (pattern) == PARALLEL
+ && remove_clobbers (&acceptance, &pattern))
+ match_pattern (&insn_root, &info, pattern, acceptance);
+ break;
+ }
+
+ case DEFINE_SPLIT:
+ acceptance.type = SPLIT;
+ pattern = add_implicit_parallel (XVEC (def, 0));
+ validate_pattern (pattern, &info, NULL_RTX, 0);
+ match_pattern (&split_root, &info, pattern, acceptance);
+
+ /* Declare the gen_split routine that we'll call if the
+ pattern matches. The definition comes from insn-emit.c. */
+ printf ("extern rtx_insn *gen_split_%d (rtx_insn *, rtx *);\n",
+ info.index);
+ break;
+
+ case DEFINE_PEEPHOLE2:
+ acceptance.type = PEEPHOLE2;
+ pattern = get_peephole2_pattern (&info);
+ validate_pattern (pattern, &info, NULL_RTX, 0);
+ match_pattern (&peephole2_root, &info, pattern, acceptance);
+
+ /* Declare the gen_peephole2 routine that we'll call if the
+ pattern matches. The definition comes from insn-emit.c. */
+ printf ("extern rtx_insn *gen_peephole2_%d (rtx_insn *, rtx *);\n",
+ info.index);
+ break;
+
+ default:
+ /* do nothing */;
+ }
+ }
+
+ if (have_error)
+ return FATAL_EXIT_CODE;
+
+ puts ("\n\n");
+
+ /* Optimize each routine in turn. */
+ optimize_subroutine_group ("recog", &insn_root);
+ optimize_subroutine_group ("split_insns", &split_root);
+ optimize_subroutine_group ("peephole2_insns", &peephole2_root);
+
+ output_state os;
+ os.id_to_var.safe_grow_cleared (num_positions);
+
+ if (use_pattern_routines_p)
{
- debug_decision_0 (d, 0, 0);
- d = d->next;
+ /* Look for common patterns and split them out into subroutines. */
+ auto_vec <merge_state_info> states;
+ states.safe_push (&insn_root);
+ states.safe_push (&split_root);
+ states.safe_push (&peephole2_root);
+ split_out_patterns (states);
+
+ /* Print out the routines that we just created. */
+ unsigned int i;
+ pattern_routine *routine;
+ FOR_EACH_VEC_ELT (patterns, i, routine)
+ print_pattern (&os, routine);
}
+
+ /* Print out the matching routines. */
+ print_subroutine_group (&os, RECOG, &insn_root);
+ print_subroutine_group (&os, SPLIT, &split_root);
+ print_subroutine_group (&os, PEEPHOLE2, &peephole2_root);
+
+ fflush (stdout);
+ return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
}
projects / thirdparty / gcc.git / blobdiff