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