+}
+
+/* Return the type of value that can be used to parameterize test KIND,
+ or parameter::UNSET if none. */
+
+parameter::type_enum
+transition_parameter_type (rtx_test::kind_enum kind)
+{
+ switch (kind)
+ {
+ case rtx_test::CODE:
+ return parameter::CODE;
+
+ case rtx_test::MODE:
+ return parameter::MODE;
+
+ case rtx_test::REGNO_FIELD:
+ return parameter::UINT;
+
+ case rtx_test::INT_FIELD:
+ case rtx_test::VECLEN:
+ case rtx_test::PATTERN:
+ return parameter::INT;
+
+ case rtx_test::WIDE_INT_FIELD:
+ return parameter::WIDE_INT;
+
+ case rtx_test::PEEP2_COUNT:
+ case rtx_test::VECLEN_GE:
+ case rtx_test::SAVED_CONST_INT:
+ case rtx_test::PREDICATE:
+ case rtx_test::DUPLICATE:
+ case rtx_test::HAVE_NUM_CLOBBERS:
+ case rtx_test::C_TEST:
+ case rtx_test::SET_OP:
+ case rtx_test::ACCEPT:
+ return parameter::UNSET;
+ }
+ gcc_unreachable ();
+}
+
+/* Initialize the pos_operand fields of each state reachable from S.
+ If OPERAND_POS[ID] >= 0, the position with id ID is stored in
+ operands[OPERAND_POS[ID]] on entry to S. */
+
+static void
+find_operand_positions (state *s, vec <int> &operand_pos)
+{
+ for (decision *d = s->first; d; d = d->next)
+ {
+ int this_operand = (d->test.pos ? operand_pos[d->test.pos->id] : -1);
+ if (this_operand >= 0)
+ d->test.pos_operand = this_operand;
+ if (d->test.kind == rtx_test::SET_OP)
+ operand_pos[d->test.pos->id] = d->test.u.opno;
+ for (transition *trans = d->first; trans; trans = trans->next)
+ find_operand_positions (trans->to, operand_pos);
+ if (d->test.kind == rtx_test::SET_OP)
+ operand_pos[d->test.pos->id] = this_operand;
+ }
+}
+
+/* Statistics about a matching routine. */
+struct stats
+{
+ stats ();
+
+ /* The total number of decisions in the routine, excluding trivial
+ ones that never fail. */
+ unsigned int num_decisions;
+
+ /* The number of non-trivial decisions on the longest path through
+ the routine, and the return value that contributes most to that
+ long path. */
+ unsigned int longest_path;
+ int longest_path_code;
+
+ /* The maximum number of times that a single call to the routine
+ can backtrack, and the value returned at the end of that path.
+ "Backtracking" here means failing one decision in state and
+ going onto to the next. */
+ unsigned int longest_backtrack;
+ int longest_backtrack_code;
+};
+
+stats::stats ()
+ : num_decisions (0), longest_path (0), longest_path_code (-1),
+ longest_backtrack (0), longest_backtrack_code (-1) {}
+
+/* Return statistics about S. */
+
+static stats
+get_stats (state *s)
+{
+ stats for_s;
+ unsigned int longest_path = 0;
+ for (decision *d = s->first; d; d = d->next)
+ {
+ /* Work out the statistics for D. */
+ stats for_d;
+ for (transition *trans = d->first; trans; trans = trans->next)
+ {
+ stats for_trans = get_stats (trans->to);
+ for_d.num_decisions += for_trans.num_decisions;
+ /* Each transition is mutually-exclusive, so just pick the
+ longest of the individual paths. */
+ if (for_d.longest_path <= for_trans.longest_path)
+ {
+ for_d.longest_path = for_trans.longest_path;
+ for_d.longest_path_code = for_trans.longest_path_code;
+ }
+ /* Likewise for backtracking. */
+ if (for_d.longest_backtrack <= for_trans.longest_backtrack)
+ {
+ for_d.longest_backtrack = for_trans.longest_backtrack;
+ for_d.longest_backtrack_code = for_trans.longest_backtrack_code;
+ }
+ }
+
+ /* Account for D's test in its statistics. */
+ if (!d->test.single_outcome_p ())
+ {
+ for_d.num_decisions += 1;
+ for_d.longest_path += 1;
+ }
+ if (d->test.kind == rtx_test::ACCEPT)
+ {
+ for_d.longest_path_code = d->test.u.acceptance.u.full.code;
+ for_d.longest_backtrack_code = d->test.u.acceptance.u.full.code;
+ }
+
+ /* Keep a running count of the number of backtracks. */
+ if (d->prev)
+ for_s.longest_backtrack += 1;
+
+ /* Accumulate D's statistics into S's. */
+ for_s.num_decisions += for_d.num_decisions;
+ for_s.longest_path += for_d.longest_path;
+ for_s.longest_backtrack += for_d.longest_backtrack;
+
+ /* Use the code from the decision with the longest individual path,
+ since that's more likely to be useful if trying to make the
+ path shorter. In the event of a tie, pick the later decision,
+ since that's closer to the end of the path. */
+ if (longest_path <= for_d.longest_path)
+ {
+ longest_path = for_d.longest_path;
+ for_s.longest_path_code = for_d.longest_path_code;
+ }
+
+ /* Later decisions in a state are necessarily in a longer backtrack
+ than earlier decisions. */
+ for_s.longest_backtrack_code = for_d.longest_backtrack_code;
+ }
+ return for_s;
+}
+
+/* Optimize ROOT. Use TYPE to describe ROOT in status messages. */
+
+static void
+optimize_subroutine_group (const char *type, state *root)
+{
+ /* Remove optional transitions that turned out not to be worthwhile. */
+ if (collapse_optional_decisions_p)
+ collapse_optional_decisions (root);
+
+ /* Try to remove duplicated tests and to rearrange tests into a more
+ logical order. */
+ if (cse_tests_p)
+ {
+ known_conditions kc;
+ kc.position_tests.safe_grow_cleared (num_positions);
+ kc.set_operands.safe_grow_cleared (num_operands);
+ kc.peep2_count = 1;
+ cse_tests (&root_pos, root, &kc);
+ }
+
+ /* Try to simplify two or more tests into one. */
+ if (simplify_tests_p)
+ simplify_tests (root);
+
+ /* Try to use operands[] instead of xN variables. */
+ if (use_operand_variables_p)
+ {
+ auto_vec <int> operand_pos (num_positions);
+ for (unsigned int i = 0; i < num_positions; ++i)
+ operand_pos.quick_push (-1);
+ find_operand_positions (root, operand_pos);
+ }
+
+ /* Print a summary of the new state. */
+ stats st = get_stats (root);
+ fprintf (stderr, "Statistics for %s:\n", type);
+ fprintf (stderr, " Number of decisions: %6d\n", st.num_decisions);
+ fprintf (stderr, " longest path: %6d (code: %6d)\n",
+ st.longest_path, st.longest_path_code);
+ fprintf (stderr, " longest backtrack: %6d (code: %6d)\n",
+ st.longest_backtrack, st.longest_backtrack_code);
+}
+
+struct merge_pattern_info;
+
+/* Represents a transition from one pattern to another. */
+struct merge_pattern_transition
+{
+ merge_pattern_transition (merge_pattern_info *);
+
+ /* The target pattern. */
+ merge_pattern_info *to;
+
+ /* The parameters that the source pattern passes to the target pattern.
+ "parameter (TYPE, true, I)" represents parameter I of the source
+ pattern. */
+ auto_vec <parameter, MAX_PATTERN_PARAMS> params;
+};
+
+merge_pattern_transition::merge_pattern_transition (merge_pattern_info *to_in)
+ : to (to_in)
+{
+}
+
+/* Represents a pattern that can might match several states. The pattern
+ may replace parts of the test with a parameter value. It may also
+ replace transition labels with parameters. */
+struct merge_pattern_info
+{
+ merge_pattern_info (unsigned int);
+
+ /* If PARAM_TEST_P, the state's singleton test should be generalized
+ to use the runtime value of PARAMS[PARAM_TEST]. */
+ unsigned int param_test : 8;
+
+ /* If PARAM_TRANSITION_P, the state's single transition label should
+ be replaced by the runtime value of PARAMS[PARAM_TRANSITION]. */
+ unsigned int param_transition : 8;
+
+ /* True if we have decided to generalize the root decision's test,
+ as per PARAM_TEST. */
+ unsigned int param_test_p : 1;
+
+ /* Likewise for the root decision's transition, as per PARAM_TRANSITION. */
+ unsigned int param_transition_p : 1;
+
+ /* True if the contents of the structure are completely filled in. */
+ unsigned int complete_p : 1;
+
+ /* The number of pseudo-statements in the pattern. Used to decide
+ whether it's big enough to break out into a subroutine. */
+ unsigned int num_statements;
+
+ /* The number of states that use this pattern. */
+ unsigned int num_users;
+
+ /* The number of distinct success values that the pattern returns. */
+ unsigned int num_results;
+
+ /* This array has one element for each runtime parameter to the pattern.
+ PARAMS[I] gives the default value of parameter I, which is always
+ constant.
+
+ These default parameters are used in cases where we match the
+ pattern against some state S1, then add more parameters while
+ matching against some state S2. S1 is then left passing fewer
+ parameters than S2. The array gives us enough informatino to
+ construct a full parameter list for S1 (see update_parameters).
+
+ If we decide to create a subroutine for this pattern,
+ PARAMS[I].type determines the C type of parameter I. */
+ auto_vec <parameter, MAX_PATTERN_PARAMS> params;
+
+ /* All states that match this pattern must have the same number of
+ transitions. TRANSITIONS[I] describes the subpattern for transition
+ number I; it is null if transition I represents a successful return
+ from the pattern. */
+ auto_vec <merge_pattern_transition *, 1> transitions;
+
+ /* The routine associated with the pattern, or null if we haven't generated
+ one yet. */
+ pattern_routine *routine;
+};
+
+merge_pattern_info::merge_pattern_info (unsigned int num_transitions)
+ : param_test (0),
+ param_transition (0),
+ param_test_p (false),
+ param_transition_p (false),
+ complete_p (false),
+ num_statements (0),
+ num_users (0),
+ num_results (0),
+ routine (0)
+{
+ transitions.safe_grow_cleared (num_transitions);
+}
+
+/* Describes one way of matching a particular state to a particular
+ pattern. */
+struct merge_state_result
+{
+ merge_state_result (merge_pattern_info *, position *, merge_state_result *);
+
+ /* A pattern that matches the state. */
+ merge_pattern_info *pattern;
+
+ /* If we decide to use this match and create a subroutine for PATTERN,
+ the state should pass the rtx at position ROOT to the pattern's
+ rtx parameter. A null root means that the pattern doesn't need
+ an rtx parameter; all the rtxes it matches come from elsewhere. */
+ position *root;
+
+ /* The parameters that should be passed to PATTERN for this state.
+ If the array is shorter than PATTERN->params, the missing entries
+ should be taken from the corresponding element of PATTERN->params. */
+ auto_vec <parameter, MAX_PATTERN_PARAMS> params;
+
+ /* An earlier match for the same state, or null if none. Patterns
+ matched by earlier entries are smaller than PATTERN. */
+ merge_state_result *prev;
+};
+
+merge_state_result::merge_state_result (merge_pattern_info *pattern_in,
+ position *root_in,
+ merge_state_result *prev_in)
+ : pattern (pattern_in), root (root_in), prev (prev_in)
+{}
+
+/* Information about a state, used while trying to match it against
+ a pattern. */
+struct merge_state_info
+{
+ merge_state_info (state *);
+
+ /* The state itself. */
+ state *s;
+
+ /* Index I gives information about the target of transition I. */
+ merge_state_info *to_states;
+
+ /* The number of transitions in S. */
+ unsigned int num_transitions;
+
+ /* True if the state has been deleted in favor of a call to a
+ pattern routine. */
+ bool merged_p;
+
+ /* The previous state that might be a merge candidate for S, or null
+ if no previous states could be merged with S. */
+ merge_state_info *prev_same_test;
+
+ /* A list of pattern matches for this state. */
+ merge_state_result *res;
+};
+
+merge_state_info::merge_state_info (state *s_in)
+ : s (s_in),
+ to_states (0),
+ num_transitions (0),
+ merged_p (false),
+ prev_same_test (0),
+ res (0) {}
+
+/* True if PAT would be useful as a subroutine. */
+
+static bool
+useful_pattern_p (merge_pattern_info *pat)
+{
+ return pat->num_statements >= MIN_COMBINE_COST;
+}
+
+/* PAT2 is a subpattern of PAT1. Return true if PAT2 should be inlined
+ into PAT1's C routine. */
+
+static bool
+same_pattern_p (merge_pattern_info *pat1, merge_pattern_info *pat2)
+{
+ return pat1->num_users == pat2->num_users || !useful_pattern_p (pat2);
+}
+
+/* PAT was previously matched against SINFO based on tentative matches
+ for the target states of SINFO's state. Return true if the match
+ still holds; that is, if the target states of SINFO's state still
+ match the corresponding transitions of PAT. */
+
+static bool
+valid_result_p (merge_pattern_info *pat, merge_state_info *sinfo)
+{
+ for (unsigned int j = 0; j < sinfo->num_transitions; ++j)
+ if (merge_pattern_transition *ptrans = pat->transitions[j])
+ {
+ merge_state_result *to_res = sinfo->to_states[j].res;
+ if (!to_res || to_res->pattern != ptrans->to)
+ return false;
+ }
+ return true;
+}
+
+/* Remove any matches that are no longer valid from the head of SINFO's
+ list of matches. */
+
+static void
+prune_invalid_results (merge_state_info *sinfo)
+{
+ while (sinfo->res && !valid_result_p (sinfo->res->pattern, sinfo))
+ {
+ sinfo->res = sinfo->res->prev;
+ gcc_assert (sinfo->res);
+ }
+}
+
+/* Return true if PAT represents the biggest posssible match for SINFO;
+ that is, if the next action of SINFO's state on return from PAT will
+ be something that cannot be merged with any other state. */
+
+static bool
+complete_result_p (merge_pattern_info *pat, merge_state_info *sinfo)
+{
+ for (unsigned int j = 0; j < sinfo->num_transitions; ++j)
+ if (sinfo->to_states[j].res && !pat->transitions[j])
+ return false;
+ return true;
+}
+
+/* Update TO for any parameters that have been added to FROM since TO
+ was last set. The extra parameters in FROM will be constants or
+ instructions to duplicate earlier parameters. */
+
+static void
+update_parameters (vec <parameter> &to, const vec <parameter> &from)
+{
+ for (unsigned int i = to.length (); i < from.length (); ++i)
+ to.quick_push (from[i]);
+}
+
+/* Return true if A and B can be tested by a single test. If the test
+ can be parameterised, store the parameter value for A in *PARAMA and
+ the parameter value for B in *PARAMB, otherwise leave PARAMA and
+ PARAMB alone. */
+
+static bool
+compatible_tests_p (const rtx_test &a, const rtx_test &b,
+ parameter *parama, parameter *paramb)
+{
+ if (a.kind != b.kind)
+ return false;
+ switch (a.kind)
+ {
+ case rtx_test::PREDICATE:
+ if (a.u.predicate.data != b.u.predicate.data)
+ return false;
+ *parama = parameter (parameter::MODE, false, a.u.predicate.mode);
+ *paramb = parameter (parameter::MODE, false, b.u.predicate.mode);
+ return true;
+
+ case rtx_test::SAVED_CONST_INT:
+ *parama = parameter (parameter::INT, false, a.u.integer.value);
+ *paramb = parameter (parameter::INT, false, b.u.integer.value);
+ return true;
+
+ default:
+ return a == b;
+ }
+}
+
+/* PARAMS is an array of the parameters that a state is going to pass
+ to a pattern routine. It is still incomplete; index I has a kind of
+ parameter::UNSET if we don't yet know what the state will pass
+ as parameter I. Try to make parameter ID equal VALUE, returning
+ true on success. */
+
+static bool
+set_parameter (vec <parameter> ¶ms, unsigned int id,
+ const parameter &value)
+{
+ if (params[id].type == parameter::UNSET)
+ {
+ if (force_unique_params_p)
+ for (unsigned int i = 0; i < params.length (); ++i)
+ if (params[i] == value)
+ return false;
+ params[id] = value;
+ return true;
+ }
+ return params[id] == value;
+}
+
+/* PARAMS2 is the "params" array for a pattern and PARAMS1 is the
+ set of parameters that a particular state is going to pass to
+ that pattern.
+
+ Try to extend PARAMS1 and PARAMS2 so that there is a parameter
+ that is equal to PARAM1 for the state and has a default value of
+ PARAM2. Parameters beginning at START were added as part of the
+ same match and so may be reused. */
+
+static bool
+add_parameter (vec <parameter> ¶ms1, vec <parameter> ¶ms2,
+ const parameter ¶m1, const parameter ¶m2,
+ unsigned int start, unsigned int *res)
+{
+ gcc_assert (params1.length () == params2.length ());
+ gcc_assert (!param1.is_param && !param2.is_param);
+
+ for (unsigned int i = start; i < params2.length (); ++i)
+ if (params1[i] == param1 && params2[i] == param2)
+ {
+ *res = i;
+ return true;
+ }
+
+ if (force_unique_params_p)
+ for (unsigned int i = 0; i < params2.length (); ++i)
+ if (params1[i] == param1 || params2[i] == param2)
+ return false;
+
+ if (params2.length () >= MAX_PATTERN_PARAMS)
+ return false;
+
+ *res = params2.length ();
+ params1.quick_push (param1);
+ params2.quick_push (param2);
+ return true;
+}
+
+/* If *ROOTA is nonnull, return true if the same sequence of steps are
+ required to reach A from *ROOTA as to reach B from ROOTB. If *ROOTA
+ is null, update it if necessary in order to make the condition hold. */
+
+static bool
+merge_relative_positions (position **roota, position *a,
+ position *rootb, position *b)
+{
+ if (!relative_patterns_p)
+ {
+ if (a != b)
+ return false;
+ if (!*roota)
+ {
+ *roota = rootb;
+ return true;
+ }
+ return *roota == rootb;
+ }
+ /* If B does not belong to the same instruction as ROOTB, we don't
+ start with ROOTB but instead start with a call to peep2_next_insn.
+ In that case the sequences for B and A are identical iff B and A
+ are themselves identical. */
+ if (rootb->insn_id != b->insn_id)
+ return a == b;
+ while (rootb != b)
+ {
+ if (!a || b->type != a->type || b->arg != a->arg)
+ return false;
+ b = b->base;
+ a = a->base;
+ }
+ if (!*roota)
+ *roota = a;
+ return *roota == a;
+}
+
+/* A hasher of states that treats two states as "equal" if they might be
+ merged (but trying to be more discriminating than "return true"). */
+struct test_pattern_hasher : typed_noop_remove <merge_state_info>
+{
+ typedef merge_state_info *value_type;
+ typedef merge_state_info *compare_type;
+ static inline hashval_t hash (const value_type &);
+ static inline bool equal (const value_type &, const compare_type &);
+};
+
+hashval_t
+test_pattern_hasher::hash (merge_state_info *const &sinfo)
+{
+ inchash::hash h;
+ decision *d = sinfo->s->singleton ();
+ h.add_int (d->test.pos_operand + 1);
+ if (!relative_patterns_p)
+ h.add_int (d->test.pos ? d->test.pos->id + 1 : 0);
+ h.add_int (d->test.kind);
+ h.add_int (sinfo->num_transitions);
+ return h.end ();
+}
+
+bool
+test_pattern_hasher::equal (merge_state_info *const &sinfo1,
+ merge_state_info *const &sinfo2)
+{
+ decision *d1 = sinfo1->s->singleton ();
+ decision *d2 = sinfo2->s->singleton ();
+ gcc_assert (d1 && d2);
+
+ parameter new_param1, new_param2;
+ return (d1->test.pos_operand == d2->test.pos_operand
+ && (relative_patterns_p || d1->test.pos == d2->test.pos)
+ && compatible_tests_p (d1->test, d2->test, &new_param1, &new_param2)
+ && sinfo1->num_transitions == sinfo2->num_transitions);
+}
+
+/* Try to make the state described by SINFO1 use the same pattern as the
+ state described by SINFO2. Return true on success.
+
+ SINFO1 and SINFO2 are known to have the same hash value. */
+
+static bool
+merge_patterns (merge_state_info *sinfo1, merge_state_info *sinfo2)
+{
+ merge_state_result *res2 = sinfo2->res;
+ merge_pattern_info *pat = res2->pattern;
+
+ /* Write to temporary arrays while matching, in case we have to abort
+ half way through. */
+ auto_vec <parameter, MAX_PATTERN_PARAMS> params1;
+ auto_vec <parameter, MAX_PATTERN_PARAMS> params2;
+ params1.quick_grow_cleared (pat->params.length ());
+ params2.splice (pat->params);
+ unsigned int start_param = params2.length ();
+
+ /* An array for recording changes to PAT->transitions[?].params.
+ All changes involve replacing a constant parameter with some
+ PAT->params[N], where N is the second element of the pending_param. */
+ typedef std::pair <parameter *, unsigned int> pending_param;
+ auto_vec <pending_param, 32> pending_params;
+
+ decision *d1 = sinfo1->s->singleton ();
+ decision *d2 = sinfo2->s->singleton ();
+ gcc_assert (d1 && d2);
+
+ /* If D2 tests a position, SINFO1's root relative to D1 is the same
+ as SINFO2's root relative to D2. */
+ position *root1 = 0;
+ position *root2 = res2->root;
+ if (d2->test.pos_operand < 0
+ && d1->test.pos
+ && !merge_relative_positions (&root1, d1->test.pos,
+ root2, d2->test.pos))
+ return false;
+
+ /* Check whether the patterns have the same shape. */
+ unsigned int num_transitions = sinfo1->num_transitions;
+ gcc_assert (num_transitions == sinfo2->num_transitions);
+ for (unsigned int i = 0; i < num_transitions; ++i)
+ if (merge_pattern_transition *ptrans = pat->transitions[i])
+ {
+ merge_state_result *to1_res = sinfo1->to_states[i].res;
+ merge_state_result *to2_res = sinfo2->to_states[i].res;
+ merge_pattern_info *to_pat = ptrans->to;
+ gcc_assert (to2_res && to2_res->pattern == to_pat);
+ if (!to1_res || to1_res->pattern != to_pat)
+ return false;
+ if (to2_res->root
+ && !merge_relative_positions (&root1, to1_res->root,
+ root2, to2_res->root))
+ return false;
+ /* Match the parameters that TO1_RES passes to TO_PAT with the
+ parameters that PAT passes to TO_PAT. */
+ update_parameters (to1_res->params, to_pat->params);
+ for (unsigned int j = 0; j < to1_res->params.length (); ++j)
+ {
+ const parameter ¶m1 = to1_res->params[j];
+ const parameter ¶m2 = ptrans->params[j];
+ gcc_assert (!param1.is_param);
+ if (param2.is_param)
+ {
+ if (!set_parameter (params1, param2.value, param1))
+ return false;
+ }
+ else if (param1 != param2)
+ {
+ unsigned int id;
+ if (!add_parameter (params1, params2,
+ param1, param2, start_param, &id))
+ return false;
+ /* Record that PAT should now pass parameter ID to TO_PAT,
+ instead of the current contents of *PARAM2. We only
+ make the change if the rest of the match succeeds. */
+ pending_params.safe_push
+ (pending_param (&ptrans->params[j], id));
+ }
+ }
+ }
+
+ unsigned int param_test = pat->param_test;
+ unsigned int param_transition = pat->param_transition;
+ bool param_test_p = pat->param_test_p;
+ bool param_transition_p = pat->param_transition_p;
+
+ /* If the tests don't match exactly, try to parameterize them. */
+ parameter new_param1, new_param2;
+ if (!compatible_tests_p (d1->test, d2->test, &new_param1, &new_param2))
+ gcc_unreachable ();
+ if (new_param1.type != parameter::UNSET)
+ {
+ /* If the test has not already been parameterized, all existing
+ matches use constant NEW_PARAM2. */
+ if (param_test_p)
+ {
+ if (!set_parameter (params1, param_test, new_param1))
+ return false;
+ }
+ else if (new_param1 != new_param2)
+ {
+ if (!add_parameter (params1, params2, new_param1, new_param2,
+ start_param, ¶m_test))
+ return false;
+ param_test_p = true;
+ }
+ }
+
+ /* Match the transitions. */
+ transition *trans1 = d1->first;
+ transition *trans2 = d2->first;
+ for (unsigned int i = 0; i < num_transitions; ++i)
+ {
+ if (param_transition_p || trans1->labels != trans2->labels)
+ {
+ /* We can only generalize a single transition with a single
+ label. */
+ if (num_transitions != 1
+ || trans1->labels.length () != 1
+ || trans2->labels.length () != 1)
+ return false;
+
+ /* Although we can match wide-int fields, in practice it leads
+ to some odd results for const_vectors. We end up
+ parameterizing the first N const_ints of the vector
+ and then (once we reach the maximum number of parameters)
+ we go on to match the other elements exactly. */
+ if (d1->test.kind == rtx_test::WIDE_INT_FIELD)
+ return false;
+
+ /* See whether the label has a generalizable type. */
+ parameter::type_enum param_type
+ = transition_parameter_type (d1->test.kind);
+ if (param_type == parameter::UNSET)
+ return false;
+
+ /* Match the labels using parameters. */
+ new_param1 = parameter (param_type, false, trans1->labels[0]);
+ if (param_transition_p)
+ {
+ if (!set_parameter (params1, param_transition, new_param1))
+ return false;
+ }
+ else
+ {
+ new_param2 = parameter (param_type, false, trans2->labels[0]);
+ if (!add_parameter (params1, params2, new_param1, new_param2,
+ start_param, ¶m_transition))
+ return false;
+ param_transition_p = true;
+ }
+ }
+ trans1 = trans1->next;
+ trans2 = trans2->next;
+ }
+
+ /* Set any unset parameters to their default values. This occurs if some
+ other state needed something to be parameterized in order to match SINFO2,
+ but SINFO1 on its own does not. */
+ for (unsigned int i = 0; i < params1.length (); ++i)
+ if (params1[i].type == parameter::UNSET)
+ params1[i] = params2[i];
+
+ /* The match was successful. Commit all pending changes to PAT. */
+ update_parameters (pat->params, params2);
+ {
+ pending_param *pp;
+ unsigned int i;
+ FOR_EACH_VEC_ELT (pending_params, i, pp)
+ *pp->first = parameter (pp->first->type, true, pp->second);
+ }
+ pat->param_test = param_test;
+ pat->param_transition = param_transition;
+ pat->param_test_p = param_test_p;
+ pat->param_transition_p = param_transition_p;
+
+ /* Record the match of SINFO1. */
+ merge_state_result *new_res1 = new merge_state_result (pat, root1,
+ sinfo1->res);
+ new_res1->params.splice (params1);
+ sinfo1->res = new_res1;
+ return true;
+}
+
+/* The number of states that were removed by calling pattern routines. */
+static unsigned int pattern_use_states;
+
+/* The number of states used while defining pattern routines. */
+static unsigned int pattern_def_states;
+
+/* Information used while constructing a use or definition of a pattern
+ routine. */
+struct create_pattern_info
+{
+ /* The routine itself. */
+ pattern_routine *routine;
+
+ /* The first unclaimed return value for this particular use or definition.
+ We walk the substates of uses and definitions in the same order
+ so each return value always refers to the same position within
+ the pattern. */
+ unsigned int next_result;
+};
+
+static void populate_pattern_routine (create_pattern_info *,
+ merge_state_info *, state *,
+ const vec <parameter> &);
+
+/* SINFO matches a pattern for which we've decided to create a C routine.
+ Return a decision that performs a call to the pattern routine,
+ but leave the caller to add the transitions to it. Initialize CPI
+ for this purpose. Also create a definition for the pattern routine,
+ if it doesn't already have one.
+
+ PARAMS are the parameters that SINFO passes to its pattern. */
+
+static decision *
+init_pattern_use (create_pattern_info *cpi, merge_state_info *sinfo,
+ const vec <parameter> ¶ms)
+{
+ state *s = sinfo->s;
+ merge_state_result *res = sinfo->res;
+ merge_pattern_info *pat = res->pattern;
+ cpi->routine = pat->routine;
+ if (!cpi->routine)
+ {
+ /* We haven't defined the pattern routine yet, so create
+ a definition now. */
+ pattern_routine *routine = new pattern_routine;
+ pat->routine = routine;
+ cpi->routine = routine;
+ routine->s = new state;
+ routine->insn_p = false;
+ routine->pnum_clobbers_p = false;
+
+ /* Create an "idempotent" mapping of parameter I to parameter I.
+ Also record the C type of each parameter to the routine. */
+ auto_vec <parameter, MAX_PATTERN_PARAMS> def_params;
+ for (unsigned int i = 0; i < pat->params.length (); ++i)
+ {
+ def_params.quick_push (parameter (pat->params[i].type, true, i));
+ routine->param_types.quick_push (pat->params[i].type);
+ }
+
+ /* Any of the states that match the pattern could be used to
+ create the routine definition. We might as well use SINFO
+ since it's already to hand. This means that all positions
+ in the definition will be relative to RES->root. */
+ routine->pos = res->root;
+ cpi->next_result = 0;
+ populate_pattern_routine (cpi, sinfo, routine->s, def_params);
+ gcc_assert (cpi->next_result == pat->num_results);
+
+ /* Add the routine to the global list, after the subroutines
+ that it calls. */
+ routine->pattern_id = patterns.length ();
+ patterns.safe_push (routine);
+ }
+
+ /* Create a decision to call the routine, passing PARAMS to it. */
+ pattern_use *use = new pattern_use;
+ use->routine = pat->routine;
+ use->params.splice (params);
+ decision *d = new decision (rtx_test::pattern (res->root, use));
+
+ /* If the original decision could use an element of operands[] instead
+ of an rtx variable, try to transfer it to the new decision. */
+ if (s->first->test.pos && res->root == s->first->test.pos)
+ d->test.pos_operand = s->first->test.pos_operand;
+
+ cpi->next_result = 0;
+ return d;
+}
+
+/* Make S return the next unclaimed pattern routine result for CPI. */
+
+static void
+add_pattern_acceptance (create_pattern_info *cpi, state *s)
+{
+ acceptance_type acceptance;
+ acceptance.type = SUBPATTERN;
+ acceptance.partial_p = false;
+ acceptance.u.full.code = cpi->next_result;
+ add_decision (s, rtx_test::accept (acceptance), true, false);
+ cpi->next_result += 1;
+}
+
+/* Initialize new empty state NEWS so that it implements SINFO's pattern
+ (here referred to as "P"). P may be the top level of a pattern routine
+ or a subpattern that should be inlined into its parent pattern's routine
+ (as per same_pattern_p). The choice of SINFO for a top-level pattern is
+ arbitrary; it could be any of the states that use P. The choice for
+ subpatterns follows the choice for the parent pattern.
+
+ PARAMS gives the value of each parameter to P in terms of the parameters
+ to the top-level pattern. If P itself is the top level pattern, PARAMS[I]
+ is always "parameter (TYPE, true, I)". */
+
+static void
+populate_pattern_routine (create_pattern_info *cpi, merge_state_info *sinfo,
+ state *news, const vec <parameter> ¶ms)
+{
+ pattern_def_states += 1;
+
+ decision *d = sinfo->s->singleton ();
+ merge_pattern_info *pat = sinfo->res->pattern;
+ pattern_routine *routine = cpi->routine;
+
+ /* Create a copy of D's test for the pattern routine and generalize it
+ as appropriate. */
+ decision *newd = new decision (d->test);
+ gcc_assert (newd->test.pos_operand >= 0
+ || !newd->test.pos
+ || common_position (newd->test.pos,
+ routine->pos) == routine->pos);
+ if (pat->param_test_p)
+ {
+ const parameter ¶m = params[pat->param_test];
+ switch (newd->test.kind)
+ {
+ case rtx_test::PREDICATE:
+ newd->test.u.predicate.mode_is_param = param.is_param;
+ newd->test.u.predicate.mode = param.value;
+ break;
+
+ case rtx_test::SAVED_CONST_INT:
+ newd->test.u.integer.is_param = param.is_param;
+ newd->test.u.integer.value = param.value;
+ break;
+
+ default:
+ gcc_unreachable ();
+ break;
+ }
+ }
+ if (d->test.kind == rtx_test::C_TEST)
+ routine->insn_p = true;
+ else if (d->test.kind == rtx_test::HAVE_NUM_CLOBBERS)
+ routine->pnum_clobbers_p = true;
+ news->push_back (newd);
+
+ /* Fill in the transitions of NEWD. */
+ unsigned int i = 0;
+ for (transition *trans = d->first; trans; trans = trans->next)
+ {
+ /* Create a new state to act as the target of the new transition. */
+ state *to_news = new state;
+ if (merge_pattern_transition *ptrans = pat->transitions[i])
+ {
+ /* The pattern hasn't finished matching yet. Get the target
+ pattern and the corresponding target state of SINFO. */
+ merge_pattern_info *to_pat = ptrans->to;
+ merge_state_info *to = sinfo->to_states + i;
+ gcc_assert (to->res->pattern == to_pat);
+ gcc_assert (ptrans->params.length () == to_pat->params.length ());
+
+ /* Express the parameters to TO_PAT in terms of the parameters
+ to the top-level pattern. */
+ auto_vec <parameter, MAX_PATTERN_PARAMS> to_params;
+ for (unsigned int j = 0; j < ptrans->params.length (); ++j)
+ {
+ const parameter ¶m = ptrans->params[j];
+ to_params.quick_push (param.is_param
+ ? params[param.value]
+ : param);
+ }
+
+ if (same_pattern_p (pat, to_pat))
+ /* TO_PAT is part of the current routine, so just recurse. */
+ populate_pattern_routine (cpi, to, to_news, to_params);
+ else
+ {
+ /* TO_PAT should be matched by calling a separate routine. */
+ create_pattern_info sub_cpi;
+ decision *subd = init_pattern_use (&sub_cpi, to, to_params);
+ routine->insn_p |= sub_cpi.routine->insn_p;
+ routine->pnum_clobbers_p |= sub_cpi.routine->pnum_clobbers_p;
+
+ /* Add the pattern routine call to the new target state. */
+ to_news->push_back (subd);
+
+ /* Add a transition for each successful call result. */
+ for (unsigned int j = 0; j < to_pat->num_results; ++j)
+ {
+ state *res = new state;
+ add_pattern_acceptance (cpi, res);
+ subd->push_back (new transition (j, res, false));
+ }
+ }
+ }
+ else
+ /* This transition corresponds to a successful match. */
+ add_pattern_acceptance (cpi, to_news);
+
+ /* Create the transition itself, generalizing as necessary. */
+ transition *new_trans = new transition (trans->labels, to_news,
+ trans->optional);
+ if (pat->param_transition_p)
+ {
+ const parameter ¶m = params[pat->param_transition];
+ new_trans->is_param = param.is_param;
+ new_trans->labels[0] = param.value;
+ }
+ newd->push_back (new_trans);
+ i += 1;
+ }
+}
+
+/* USE is a decision that calls a pattern routine and SINFO is part of the
+ original state tree that the call is supposed to replace. Add the
+ transitions for SINFO and its substates to USE. */
+
+static void
+populate_pattern_use (create_pattern_info *cpi, decision *use,
+ merge_state_info *sinfo)
+{
+ pattern_use_states += 1;
+ gcc_assert (!sinfo->merged_p);
+ sinfo->merged_p = true;
+ merge_state_result *res = sinfo->res;
+ merge_pattern_info *pat = res->pattern;
+ decision *d = sinfo->s->singleton ();
+ unsigned int i = 0;
+ for (transition *trans = d->first; trans; trans = trans->next)
+ {
+ if (pat->transitions[i])
+ /* The target state is also part of the pattern. */
+ populate_pattern_use (cpi, use, sinfo->to_states + i);
+ else
+ {
+ /* The transition corresponds to a successful return from the
+ pattern routine. */
+ use->push_back (new transition (cpi->next_result, trans->to, false));
+ cpi->next_result += 1;
+ }
+ i += 1;
+ }
+}
+
+/* We have decided to replace SINFO's state with a call to a pattern
+ routine. Make the change, creating a definition of the pattern routine
+ if it doesn't have one already. */
+
+static void
+use_pattern (merge_state_info *sinfo)
+{
+ merge_state_result *res = sinfo->res;
+ merge_pattern_info *pat = res->pattern;
+ state *s = sinfo->s;
+
+ /* The pattern may have acquired new parameters after it was matched
+ against SINFO. Update the parameters that SINFO passes accordingly. */
+ update_parameters (res->params, pat->params);
+
+ create_pattern_info cpi;
+ decision *d = init_pattern_use (&cpi, sinfo, res->params);
+ populate_pattern_use (&cpi, d, sinfo);
+ s->release ();
+ s->push_back (d);
+}
+
+/* Look through the state trees in STATES for common patterns and
+ split them into subroutines. */
+
+static void
+split_out_patterns (vec <merge_state_info> &states)
+{
+ unsigned int first_transition = states.length ();
+ hash_table <test_pattern_hasher> hashtab (128);
+ /* Stage 1: Create an order in which parent states come before their child
+ states and in which sibling states are at consecutive locations.
+ Having consecutive sibling states allows merge_state_info to have
+ a single to_states pointer. */
+ for (unsigned int i = 0; i < states.length (); ++i)
+ for (decision *d = states[i].s->first; d; d = d->next)
+ for (transition *trans = d->first; trans; trans = trans->next)
+ {
+ states.safe_push (trans->to);
+ states[i].num_transitions += 1;
+ }
+ /* Stage 2: Now that the addresses are stable, set up the to_states
+ pointers. Look for states that might be merged and enter them
+ into the hash table. */
+ for (unsigned int i = 0; i < states.length (); ++i)
+ {
+ merge_state_info *sinfo = &states[i];
+ if (sinfo->num_transitions)
+ {
+ sinfo->to_states = &states[first_transition];
+ first_transition += sinfo->num_transitions;
+ }
+ /* For simplicity, we only try to merge states that have a single
+ decision. This is in any case the best we can do for peephole2,
+ since whether a peephole2 ACCEPT succeeds or not depends on the
+ specific peephole2 pattern (which is unique to each ACCEPT
+ and so couldn't be shared between states). */
+ if (decision *d = sinfo->s->singleton ())
+ /* ACCEPT states are unique, so don't even try to merge them. */
+ if (d->test.kind != rtx_test::ACCEPT
+ && (pattern_have_num_clobbers_p
+ || d->test.kind != rtx_test::HAVE_NUM_CLOBBERS)
+ && (pattern_c_test_p
+ || d->test.kind != rtx_test::C_TEST))
+ {
+ merge_state_info **slot = hashtab.find_slot (sinfo, INSERT);
+ sinfo->prev_same_test = *slot;
+ *slot = sinfo;
+ }
+ }
+ /* Stage 3: Walk backwards through the list of states and try to merge
+ them. This is a greedy, bottom-up match; parent nodes can only start
+ a new leaf pattern if they fail to match when combined with all child
+ nodes that have matching patterns.
+
+ For each state we keep a list of potential matches, with each
+ potential match being larger (and deeper) than the next match in
+ the list. The final element in the list is a leaf pattern that
+ matches just a single state.
+
+ Each candidate pattern created in this loop is unique -- it won't
+ have been seen by an earlier iteration. We try to match each pattern
+ with every state that appears earlier in STATES.
+
+ Because the patterns created in the loop are unique, any state
+ that already has a match must have a final potential match that
+ is different from any new leaf pattern. Therefore, when matching
+ leaf patterns, we need only consider states whose list of matches
+ is empty.
+
+ The non-leaf patterns that we try are as deep as possible
+ and are an extension of the state's previous best candidate match (PB).
+ We need only consider states whose current potential match is also PB;
+ any states that don't match as much as PB cannnot match the new pattern,
+ while any states that already match more than PB must be different from
+ the new pattern. */
+ for (unsigned int i2 = states.length (); i2-- > 0; )
+ {
+ merge_state_info *sinfo2 = &states[i2];
+
+ /* Enforce the bottom-upness of the match: remove matches with later
+ states if SINFO2's child states ended up finding a better match. */
+ prune_invalid_results (sinfo2);
+
+ /* Do nothing if the state doesn't match a later one and if there are
+ no earlier states it could match. */
+ if (!sinfo2->res && !sinfo2->prev_same_test)
+ 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]))
+ 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))
+ {
+ /* 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. */
+struct pattern_pos {
+ 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;
+}
+
+/* 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);
+}
+
+/* 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, rtx top_pattern, 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 (top_pattern, 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_with_line (pattern_lineno,
+ "unknown predicate '%s'"
+ " in '%s' expression",
+ pred_name, GET_RTX_NAME (code));
+ else if (code == MATCH_PARALLEL
+ && pred->singleton != PARALLEL)
+ error_with_line (pattern_lineno,
+ "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 '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 (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) C_TEST 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, rtx top_pattern, const char *c_test,
+ 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 (top_pattern, 0); ++i)
+ {
+ rtx x = XVECEXP (top_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, top_pattern, 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, top_pattern, &root_pos, top_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. */
+ 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, rtx top_pattern, const char *c_test,
+ 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, top_pattern, c_test, acceptance);
+ merge_into_state (s, &root);
+ }
+ else
+ match_pattern_1 (s, top_pattern, c_test, 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\
+#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 \"hashtab.h\"\n\
+#include \"hash-set.h\"\n\
+#include \"vec.h\"\n\
+#include \"machmode.h\"\n\
+#include \"hard-reg-set.h\"\n\
+#include \"input.h\"\n\
+#include \"function.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 \"hard-reg-set.h\"\n\
+#include \"predict.h\"\n\
+#include \"basic-block.h\"\n\
+#include \"resource.h\"\n\
+#include \"diagnostic-core.h\"\n\
+#include \"reload.h\"\n\
+#include \"regs.h\"\n\
+#include \"tm-constrs.h\"\n\
+#include \"predict.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. */
+
+struct output_state
+{
+ /* 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;