#include "bconfig.h"#include "system.h"#include "coretypes.h"#include "tm.h"#include "rtl.h"#include "errors.h"#include "read-md.h"#include "gensupport.h"
Data Structures | |
| struct | position |
| struct | decision_head |
| struct | decision_test |
| struct | decision |
Macros | |
| #define | OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) printf ("%sL%d:_LABEL\n", (INDENT_STRING), (LABEL_NUMBER)) |
| #define | SUBROUTINE_THRESHOLD 100 |
| #define | IS_SPLIT(X) ((X) != RECOG) |
Enumerations | |
| enum | position_type { POS_PEEP2_INSN, POS_XEXP, POS_XVECEXP0 } |
| enum | decision_type { DT_num_insns, DT_mode, DT_code, DT_veclen, DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide, DT_elt_zero_wide_safe, DT_const_int, DT_veclen_ge, DT_dup, DT_pred, DT_c_test, DT_accept_op, DT_accept_insn } |
| enum | routine_type { RECOG, SPLIT, PEEPHOLE2 } |
Functions | |
| void | debug_decision (struct decision *) |
| void | debug_decision_list (struct decision *) |
| static struct position * | next_position (struct position **next_ptr, struct position *base, enum position_type type, int arg) |
| static int | compare_positions () |
| static struct decision * | new_decision () |
| static struct decision_test * | new_decision_test () |
| static rtx | find_operand () |
| static rtx | find_matching_operand () |
| static void | validate_pattern () |
| static struct decision * | add_to_sequence (rtx pattern, struct decision_head *last, struct position *pos, enum routine_type insn_type, int top) |
| static int | maybe_both_true_2 () |
| static int | maybe_both_true_1 () |
| static int | maybe_both_true (struct decision *d1, struct decision *d2, int toplevel) |
| static int | nodes_identical_1 () |
| static int | nodes_identical () |
| static void | merge_accept_insn () |
| static void | merge_trees () |
| static void | factor_tests () |
| static void | simplify_tests () |
| static int | break_out_subroutines () |
| static void | find_afterward () |
| static void | change_state (struct position *oldpos, struct position *newpos, const char *indent) |
| static void | print_code () |
| static void | write_afterward (struct decision *start, struct decision *afterward, const char *indent) |
| static void | print_host_wide_int () |
| static struct decision * | write_switch () |
| static void | write_cond (struct decision_test *p, int depth, enum routine_type subroutine_type) |
| static void | write_action (struct decision *p, struct decision_test *test, int depth, int uncond, struct decision *success, enum routine_type subroutine_type) |
| static int | is_unconditional () |
| static int | write_node (struct decision *p, int depth, enum routine_type subroutine_type) |
| static void | write_tree_1 (struct decision_head *head, int depth, enum routine_type subroutine_type) |
| static void | write_tree (struct decision_head *head, struct position *prevpos, enum routine_type type, int initial) |
| static void | write_subroutine () |
| static void | write_subroutines () |
| static void | write_header () |
| static struct decision_head | make_insn_sequence () |
| static void | process_tree () |
| int | main (int, char **) |
| int | main () |
| static void | debug_decision_2 () |
| static void | debug_decision_1 () |
| static void | debug_decision_0 () |
| DEBUG_FUNCTION void | debug_decision () |
| DEBUG_FUNCTION void | debug_decision_list () |
Variables | |
| static int | next_subroutine_number |
| static int | next_number |
| static int | next_insn_code |
| static int | max_depth |
| static int | pattern_lineno |
| static struct position | root_pos |
| static struct position * | peep2_insn_pos_list = &root_pos |
Macro Definition Documentation
| #define IS_SPLIT | ( | X | ) | ((X) != RECOG) |
Referenced by is_unconditional().
| #define OUTPUT_LABEL | ( | INDENT_STRING, | |
| LABEL_NUMBER | |||
| ) | printf ("%sL%d:_LABEL\n", (INDENT_STRING), (LABEL_NUMBER)) |
Generate code from machine description to recognize rtl as insns. Copyright (C) 1987-2013 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/. This program is used to produce insn-recog.c, which contains a function called `recog' plus its subroutines. These functions contain a decision tree that recognizes whether an rtx, the argument given to recog, is a valid instruction.
recog returns -1 if the rtx is not valid. If the rtx is valid, recog returns a nonnegative number which is the insn code number for the pattern that matched. This is the same as the order in the machine description of the entry that matched. This number can be used as an index into various insn_* tables, such as insn_template, insn_outfun, and insn_n_operands (found in insn-output.c).
The third argument to recog is an optional pointer to an int. If present, recog will accept a pattern if it matches except for missing CLOBBER expressions at the end. In that case, the value pointed to by the optional pointer will be set to the number of CLOBBERs that need to be added (it should be initialized to zero by the caller). If it is set nonzero, the caller should allocate a PARALLEL of the appropriate size, copy the initial entries, and call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
This program also generates the function `split_insns', which returns 0 if the rtl could not be split, or it returns the split rtl as an INSN list.
This program also generates the function `peephole2_insns', which returns 0 if the rtl could not be matched. If there was a match, the new rtl is returned in an INSN list, and LAST_INSN will point to the last recognized insn in the old sequence.
| #define SUBROUTINE_THRESHOLD 100 |
Enumeration Type Documentation
| enum decision_type |
| enum position_type |
| enum routine_type |
Function Documentation
|
staticread |
Create a chain of nodes to verify that an rtl expression matches PATTERN.
LAST is a pointer to the listhead in the previous node in the chain (or in the calling function, for the first node).
POSITION is the current position in the insn.
INSN_TYPE is the type of insn for which we are emitting code.
A pointer to the final node in the chain is returned.
Toplevel peephole pattern.
Check we have sufficient insns. This avoids complications
because we then know peep2_next_insn never fails. We don't need the node we just created – unlink it.
Else nothing special.
The explicit patterns within a match_parallel enforce a minimum
length on the vector. The match_parallel predicate may allow
for more elements. We do need to check for this minimum here
or the code generated to match the internals may reference data
beyond the end of the vector. Fall through.
See if we know about this predicate.
If we do, remember it for use below.
We can optimize the generated code a little if either
(a) the predicate only accepts one code, or (b) the
predicate does not allow CONST_INT, in which case it
can match only if the modes match. Can't enforce a mode if we allow const_int.
Accept the operand, i.e. record it in `operands'.
Do tests against the current node first.
If this value actually fits in an int, we can use a switch
statement here, so indicate that. Now test our sub-patterns.
Handled above.
Insert nodes testing mode and code, if they're still relevant, before any of the nodes we may have added above.
If we didn't insert any tests or accept nodes, hork.
Referenced by write_header().
|
static |
Count the number of subnodes of HEAD. If the number is high enough, make the first node in HEAD start a separate subroutine in the C code that is generated.
References change_state(), decision::number, decision::position, and decision::subroutine_number.
|
static |
Assuming that the state of argument is denoted by OLDPOS, take whatever actions are necessary to move to NEWPOS. If we fail to move to the new state, branch to node AFTERWARD if nonzero, otherwise return.
Failure to move to the new state can only occur if we are trying to match multiple insns and we try to step past the end of the stream.
Referenced by break_out_subroutines(), is_unconditional(), and simplify_tests().
|
static |
Compare positions POS1 and POS2 lexicographically.
| void debug_decision | ( | struct decision * | ) |
| DEBUG_FUNCTION void debug_decision | ( | ) |
|
static |
|
static |
|
static |
| void debug_decision_list | ( | struct decision * | ) |
| DEBUG_FUNCTION void debug_decision_list | ( | ) |
|
static |
Walk the tree looking for sub-nodes that perform common tests. Factor out the common test into a new node. This enables us (depending on the test type) to emit switch statements later.
Want at least two compatible sequential nodes.
Don't want all node types, just those we can turn into
switch statements. If we'd been performing more than one test, create a new node
below our first test. Crop the node tree off after our first test.
For each compatible test, adjust to perform only one test in
the top level node, then merge the node back into the tree. After we run out of compatible tests, graft the remaining nodes
back onto the tree. Recurse.
References DT_code, DT_mode, decision_test::next, decision::tests, and decision_test::type.
|
static |
For each node p, find the next alternative that might be true when p is true.
We can't propagate alternatives across subroutine boundaries. This is not incorrect, merely a minor optimization loss.
Find the next node that might be true if this one fails.
If we reached the end of the list without finding one,
use the incoming afterward position. Recurse.
When we are generating a subroutine, record the real afterward position in the first node where write_tree can find it, and we can do the right thing at the subroutine call site.
References HOST_BITS_PER_WIDE_INT, HOST_WIDE_INT, and HOST_WIDE_INT_PRINT_DEC_C.
|
static |
Search for and return operand M, such that it has a matching constraint for operand N.
Fall through.
|
static |
Search for and return operand N, stop when reaching node STOP.
Fall through.
|
static |
Return 1 if the test is always true and has no fallthru path. Return -1 if the test does have a fallthru path, but requires that the condition be terminated. Otherwise return 0 for a normal test. ??? is_unconditional is a stupid name for a tri-state function.
References decision::afterward, change_state(), IS_SPLIT, decision::number, decision::position, and decision::subroutine_number.
| int main | ( | int | , |
| char ** | |||
| ) |
| int main | ( | ) |
|
staticread |
Construct and return a sequence of decisions that will recognize INSN.
TYPE says what type of routine we are recognizing (RECOG or SPLIT).
We should never see an insn whose C test is false at compile time.
peephole2 gets special treatment:
- X always gets an outer parallel even if it's only one entry
- we remove all traces of outer-level match_scratch and match_dup
expressions here. Find the end of the test chain on the last node.
Skip the C test if it's known to be true at compile time.
Need a new node if we have another test to add.
If this is a DEFINE_INSN and X is a PARALLEL, see if it ends
with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
If so, set up to recognize the pattern without these CLOBBERs. Find the last non-clobber in the parallel.
Build a similar insn without the clobbers.
Recognize it.
Find the end of the test chain on the last node.
We definitely have a new test to add – create a new
node if needed. Skip the C test if it's known to be true at compile
time. Define the subroutine we will call below and emit in genemit.
Define the subroutine we will call below and emit in genemit.
Return 0 if we can prove that there is no RTL that can match both D1 and D2. Otherwise, return 1 (it may be that there is an RTL that can match both or just that we couldn't prove there wasn't such an RTL).
TOPLEVEL is nonzero if we are to only look at the top level and not recursively descend.
Don't compare strings on the different positions in insn. Doing so
is incorrect and results in false matches from constructs like
[(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
(subreg:HI (match_operand:SI "register_operand" "r") 0))]
vs
[(set (match_operand:HI "register_operand" "r")
(match_operand:HI "register_operand" "r"))]
If we are presented with such, we are recursing through the remainder
of a node's success nodes (from the loop at the end of this function).
Skip forward until we come to a position that matches.
Due to the way positions are constructed, we know that iterating
forward from the lexically lower position will run into the lexically
higher position and not the other way around. This saves a bit
of effort.
If the d2->position was lexically lower, swap.
Test the current level.
We can't prove that D1 and D2 cannot both be true. If we are only to check the top level, return 1. Otherwise, see if we can prove that all choices in both successors are mutually exclusive. If either does not have any successors, we can't prove they can't both be true.
|
static |
A subroutine of maybe_both_true; examines all the tests for a given node. Returns > 0 for "definitely both true" and < 0 for "maybe both true".
A match_operand with no predicate can match anything. Recognize this by the existence of a lone DT_accept_op test.
Eliminate pairs of tests while they can exactly match.
After that, consider all pairs.
|
static |
A subroutine of maybe_both_true; examines only one test. Returns > 0 for "definitely both true" and < 0 for "maybe both true".
If either has a predicate that we know something about, set things up so that D1 is the one that always has a known predicate. Then see if they have any codes in common.
If D2 tests a mode, see if it matches D1.
The mode of an address_operand predicate is the
mode of the memory, not the operand. It can only
be used for testing the predicate, so we must
ignore it here. Don't check two predicate modes here, because if both predicates
accept CONST_INT, then both can still be true even if the modes
are different. If they don't accept CONST_INT, there will be a
separate DT_mode that will make maybe_both_true_1 return 0. If D2 tests a code, see if it is in the list of valid
codes for D1's predicate. Otherwise see if the predicates have any codes in common.
Tests vs veclen may be known when strict equality is involved.
References decision_test::code, DT_code, DT_pred, NUM_RTX_CODE, decision_test::pred, decision_test::type, and decision_test::u.
|
static |
A subroutine of merge_trees; given two nodes that have been declared identical, cope with two insn accept states. If they differ in the number of clobbers, then the conflict was created by make_insn_sequence and we can drop the with-clobbers version on the floor. If both nodes have no additional clobbers, we have found an ambiguity in the source machine description.
If one node is for a normal insn and the second is for the base insn with clobbers stripped off, the second node should be ignored.
Nothing to do here.
In this case, replace OLD with ADD.
|
static |
Merge two decision trees OLDH and ADDH, modifying OLDH destructively.
Trying to merge bits at different positions isn't possible.
The semantics of pattern matching state that the tests are
done in the order given in the MD file so that if an insn
matches two patterns, the first one will be used. However,
in practice, most, if not all, patterns are unambiguous so
that their order is independent. In that case, we can merge
identical tests and group all similar modes and codes together.
Scan starting from the end of OLDH until we reach a point
where we reach the head of the list or where we pass a
pattern that could also be true if NEW is true. If we find
an identical pattern, we can merge them. Also, record the
last node that tests the same code and mode and the last one
that tests just the same mode.
If we have no match, place NEW after the closest match we found. Insert the nodes in DT test type order, which is roughly
how expensive/important the test is. Given that the tests
are also ordered within the list, examining the first is
sufficient.
References new_decision(), decision_test::next, NULL, decision::position, decision::success, and decision::tests.
|
staticread |
Create a new node in sequence after LAST.
References decision_test::code, GET_CODE, and RTX_CODE.
Referenced by merge_trees(), write_header(), and write_subroutines().
|
staticread |
Create a new test and link it in at PLACE.
Referenced by write_header().
|
staticread |
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.
References position::arg, position::base, and position::type.
|
static |
True iff the two nodes are identical (on one level only). Due to the way these lists are constructed, we shouldn't have to consider different orderings on the tests.
For success, they should now both be null.
Check that their subnodes are at the same position, as any one set of sibling decisions must be at the same position. Allowing this requires complications to find_afterward and when change_state is invoked.
|
static |
A subroutine of nodes_identical. Examine two tests for equivalence.
Differences will be handled in merge_accept_insn.
References DT_accept_insn, error_with_line(), get_insn_name(), decision_test::insn, message_with_line(), decision_test::next, NULL, decision::tests, decision_test::type, and decision_test::u.
|
static |
Print the enumerator constant for CODE – the upcase version of the name.
|
static |
Emit a HOST_WIDE_INT as an integer constant expression. We need to take special care to avoid "decimal constant is so large that it is unsigned" warnings in the resulting code.
|
static |
We can elide peephole2_insns, but not recog or split_insns.
We run this after find_afterward, because find_afterward needs
the redundant DT_mode tests on predicates to determine whether
two tests can both be true or not.
|
static |
After factoring, try to simplify the tests on any one node. Tests that are useful for switch statements are recognizable by having only a single test on a node – we'll be manipulating nodes with multiple tests:
If we have mode tests or code tests that are redundant with predicates, remove them.
Find a predicate node.
Due to how these tests are constructed, we don't even need
to check that the mode and code are compatible – they were
generated from the predicate in the first place. Recurse.
References position::arg, position::base, change_state(), position::depth, POS_PEEP2_INSN, POS_XEXP, POS_XVECEXP0, and position::type.
|
static |
Check for various errors in patterns. SET is nonnull for a destination, and is the complete set pattern. SET_CODE is '=' for normal sets, and '+' within a context that requires in-out constraints.
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.
A MATCH_OPERAND that is a SET should have an output reload.
If we've only got an output reload for this operand,
we'd better have a matching input operand. Allowing non-lvalues in destinations – particularly CONST_INT –
while not likely to occur at runtime, results in less efficient
code from insn-recog.c. 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. STRICT_LOW_PART is a wrapper. Its argument is the real
destination, and it's mode should match the source. Find the referent for a DUP.
The mode of an ADDRESS_OPERAND is the mode of the memory
reference, not the mode of the address. The operands of a SET must have the same mode unless one
is VOIDmode. If only one of the operands is VOIDmode, and PC or CC0 is
not involved, it's probably a mistake.
|
static |
Emit code for one action. The previous tests have succeeded; TEST is the last of the chain. In the normal case we simply perform a state change. For the `accept' tests we must do more work.
Only allow DT_accept_insn to follow.
Sanity check that we're now at the end of the list of tests.
References DT_const_int, decision_test::intval, decision_test::next, decision_test::type, and decision_test::u.
|
static |
Emit code to cross an afterward link – change state and branch.
|
static |
Emit code for one test.
References position::arg, position::base, decision_test::insn, POS_PEEP2_INSN, decision::position, position::type, and decision_test::u.
|
static |
Begin the output file.
References add_to_sequence(), decision_test::c_test, DT_accept_insn, DT_accept_op, DT_c_test, GET_CODE, decision_test::insn, new_decision(), new_decision_test(), decision_test::next, next_insn_code, pattern_lineno, REG_P, root_pos, rtvec_alloc(), rtx_alloc, decision_test::type, decision_test::u, XEXP, XVEC, XVECEXP, and XVECLEN.
|
static |
Emit code for one node – the conditional and the accompanying action. Return true if there is no fallthru path.
Scan the tests and simplify comparisons against small constants.
|
static |
Write out a subroutine of type TYPE to do comparisons starting at node TREE.
|
static |
In break_out_subroutines, we discovered the boundaries for the subroutines, but did not write them out. Do so now.
References new_decision().
|
staticread |
Emit a switch statement, if possible, for an initial sequence of nodes at START. Return the first node yet untested.
If we have two or more nodes in sequence that test the same one thing, we may be able to use a switch statement.
DT_code is special in that we can do interesting things with known predicates at the same time.
If P is testing a predicate that we know about and we haven't
seen any of the codes that are valid for the predicate, we can
write a series of "case" statement, one for each possible code.
Since we are already in a switch, these redundant tests are very
cheap and will reduce the number of predicates called. Note that while we write out cases for these predicates here,
we don't actually write the test here, as it gets kinda messy.
It is trivial to leave this to later by telling our caller that
we only processed the CODE tests. Make the default case skip the predicates we managed to match.
We cast switch parameter to integer, so we must ensure that the value
fits. Convert result of XWINT to int for portability since some C
compilers won't do it and some will. Merge trees will not unify identical nodes if their
sub-nodes are at different levels. Thus we must check
for duplicate cases. None of the other tests are amenable.
|
static |
Write out the decision tree starting at HEAD. PREVPOS is the position at the node that branched to this node.
This node has been broken out into a separate subroutine. Call it, test the result, and branch accordingly.
|
static |
Emit code for all of the sibling nodes of HEAD.
The label for the first element was printed in write_tree.
Attempt to write a switch statement for a whole sequence.
Failed – fall back and write one node.
Finished with this chain. Close a fallthru path by branching to the afterward node.
Variable Documentation
|
static |
Record the highest depth we ever have so we know how many variables to allocate in each subroutine we make.
|
static |
Next number to use as an insn_code.
Referenced by write_header().
|
static |
Next available node number for tree nodes.
|
static |
|
static |
The line number of the start of the pattern currently being processed.
Referenced by write_header().
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 |
The root position (x0).
Referenced by write_header().
