GCC Middle and Back End API Reference
genrecog.c File Reference

Data Structures

struct  position
struct  decision_head
struct  decision_test
struct  decision


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 }


void debug_decision (struct decision *)
void debug_decision_list (struct decision *)
static struct positionnext_position (struct position **next_ptr, struct position *base, enum position_type type, int arg)
static int compare_positions ()
static struct decisionnew_decision ()
static struct decision_testnew_decision_test ()
static rtx find_operand ()
static rtx find_matching_operand ()
static void validate_pattern ()
static struct decisionadd_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 decisionwrite_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 ()


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 positionpeep2_insn_pos_list = &root_pos

Enumeration Type Documentation

   These types are roughly in the order in which we'd like to test them.  
   Ways of obtaining an rtx to be tested.  
     PATTERN (peep2_next_insn (ARG)).  
     XEXP (BASE, ARG).  
     XVECEXP (BASE, 0, ARG).  
   We can write three types of subroutines: One for insn recognition,
   one to split insns, and one for peephole-type optimizations.  This
   defines which type is being written.  

Function Documentation

static struct decision* add_to_sequence ( rtx  pattern,
struct decision_head last,
struct position pos,
enum routine_type  insn_type,
int  top 
   Create a chain of nodes to verify that an rtl expression matches

   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 int break_out_subroutines ( )
   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 void change_state ( struct position oldpos,
struct position newpos,
const char *  indent 
   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 int compare_positions ( )
   Compare positions POS1 and POS2 lexicographically.  
void debug_decision ( struct decision )
DEBUG_FUNCTION void debug_decision ( )
static void debug_decision_0 ( )
static void debug_decision_1 ( )
static void debug_decision_2 ( )
void debug_decision_list ( struct decision )
DEBUG_FUNCTION void debug_decision_list ( )
static void factor_tests ( )
   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.  

References DT_code, DT_mode, decision_test::next, decision::tests, and decision_test::type.

static void find_afterward ( )
   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.  
     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.  


static rtx find_matching_operand ( )
   Search for and return operand M, such that it has a matching
   constraint for operand N.  
             Fall through.  
static rtx find_operand ( )
   Search for and return operand N, stop when reaching node STOP.  
             Fall through.  
static int is_unconditional ( )
   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(), decision::number, decision::position, and decision::subroutine_number.

int main ( int  ,
char **   
int main ( )
     Read the machine description.  
             do nothing 

References indent.

static struct decision_head make_insn_sequence ( )
   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
         Define the subroutine we will call below and emit in genemit.  
         Define the subroutine we will call below and emit in genemit.  
static int maybe_both_true ( struct decision d1,
struct decision d2,
int  toplevel 
   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))]
        [(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 int maybe_both_true_1 ( )
   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 int maybe_both_true_2 ( )
   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, decision_test::pred, decision_test::type, and decision_test::u.

static void merge_accept_insn ( )
   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 void merge_trees ( )
   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

References new_decision(), decision_test::next, decision::position, decision::success, and decision::tests.

static struct decision* new_decision ( )
   Create a new node in sequence after LAST.  

References decision_test::code, and len.

Referenced by merge_trees(), write_header(), and write_subroutines().

static struct decision_test* new_decision_test ( )
   Create a new test and link it in at PLACE.  

Referenced by write_header().

static struct position* next_position ( struct position **  next_ptr,
struct position base,
enum position_type  type,
int  arg 
   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 int nodes_identical ( )
   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
static int nodes_identical_1 ( )
   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, decision::tests, decision_test::type, and decision_test::u.

static void print_code ( )
   Print the enumerator constant for CODE -- the upcase version of
   the name.  
static void print_host_wide_int ( )
   Emit a HOST_WIDE_INT as an integer constant expression.  We need to take
   special care to avoid "decimal constant is so large that it is unsigned"
   warnings in the resulting code.  
static void process_tree ( )
         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 void simplify_tests ( )
   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.  

References position::arg, position::base, change_state(), position::depth, POS_PEEP2_INSN, POS_XEXP, POS_XVECEXP0, and position::type.

static void validate_pattern ( )
   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.  
               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 void write_action ( struct decision p,
struct decision_test test,
int  depth,
int  uncond,
struct decision success,
enum routine_type  subroutine_type 
   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 void write_afterward ( struct decision start,
struct decision afterward,
const char *  indent 
   Emit code to cross an afterward link -- change state and branch.  
static void write_cond ( struct decision_test p,
int  depth,
enum routine_type  subroutine_type 
static int write_node ( struct decision p,
int  depth,
enum routine_type  subroutine_type 
   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
static void write_subroutine ( )
   Write out a subroutine of type TYPE to do comparisons starting at
   node TREE.  
static void write_subroutines ( )
   In break_out_subroutines, we discovered the boundaries for the
   subroutines, but did not write them out.  Do so now.  

References new_decision().

static struct decision* write_switch ( )
   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
             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 void write_tree ( struct decision_head head,
struct position prevpos,
enum routine_type  type,
int  initial 
   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 void write_tree_1 ( struct decision_head head,
int  depth,
enum routine_type  subroutine_type 
   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

int max_depth
   Record the highest depth we ever have so we know how many variables to
   allocate in each subroutine we make.  
int next_insn_code
   Next number to use as an insn_code.  

Referenced by write_header().

int next_number
   Next available node number for tree nodes.  
int next_subroutine_number
int pattern_lineno
   The line number of the start of the pattern currently being processed.  

Referenced by write_header().

struct position* peep2_insn_pos_list = &root_pos
   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.  
struct position root_pos
   The root position (x0).  

Referenced by write_header().