genrecog.c revision 52284
117721Speter/* Generate code from machine description to recognize rtl as insns. 2175261Sobrien Copyright (C) 1987, 88, 92-95, 97-98, 1999 Free Software Foundation, Inc. 3175261Sobrien 4175261SobrienThis file is part of GNU CC. 5175261Sobrien 6175261SobrienGNU CC is free software; you can redistribute it and/or modify 7175261Sobrienit under the terms of the GNU General Public License as published by 817721Speterthe Free Software Foundation; either version 2, or (at your option) 917721Speterany later version. 1032785Speter 1117721SpeterGNU CC is distributed in the hope that it will be useful, 1217721Speterbut WITHOUT ANY WARRANTY; without even the implied warranty of 1317721SpeterMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1417721SpeterGNU General Public License for more details. 1517721Speter 1617721SpeterYou should have received a copy of the GNU General Public License 1717721Speteralong with GNU CC; see the file COPYING. If not, write to 1825839Speterthe Free Software Foundation, 59 Temple Place - Suite 330, 1925839SpeterBoston, MA 02111-1307, USA. */ 2025839Speter 2125839Speter 2217721Speter/* This program is used to produce insn-recog.c, which contains 2317721Speter a function called `recog' plus its subroutines. 2417721Speter These functions contain a decision tree 2517721Speter that recognizes whether an rtx, the argument given to recog, 2617721Speter is a valid instruction. 2717721Speter 2817721Speter recog returns -1 if the rtx is not valid. 2917721Speter If the rtx is valid, recog returns a nonnegative number 3017721Speter which is the insn code number for the pattern that matched. 3117721Speter This is the same as the order in the machine description of the 3217721Speter entry that matched. This number can be used as an index into various 3317721Speter insn_* tables, such as insn_template, insn_outfun, and insn_n_operands 3417721Speter (found in insn-output.c). 3517721Speter 3617721Speter The third argument to recog is an optional pointer to an int. 3717721Speter If present, recog will accept a pattern if it matches except for 3817721Speter missing CLOBBER expressions at the end. In that case, the value 3917721Speter pointed to by the optional pointer will be set to the number of 4017721Speter CLOBBERs that need to be added (it should be initialized to zero by 4117721Speter the caller). If it is set nonzero, the caller should allocate a 4217721Speter PARALLEL of the appropriate size, copy the initial entries, and call 4317721Speter add_clobbers (found in insn-emit.c) to fill in the CLOBBERs. 4417721Speter 4517721Speter This program also generates the function `split_insns', 4617721Speter which returns 0 if the rtl could not be split, or 4717721Speter it returns the split rtl in a SEQUENCE. */ 4817721Speter 4917721Speter#include "hconfig.h" 5017721Speter#include "system.h" 5117721Speter#include "rtl.h" 5217721Speter#include "obstack.h" 5317721Speter 5417721Speter#define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \ 5517721Speter printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER)) 5617721Speter 5717721Speterstatic struct obstack obstack; 5817721Speterstruct obstack *rtl_obstack = &obstack; 5917721Speter 6017721Speter#define obstack_chunk_alloc xmalloc 6117721Speter#define obstack_chunk_free free 6217721Speter 6317721Speter/* Holds an array of names indexed by insn_code_number. */ 6417721Speterchar **insn_name_ptr = 0; 6517721Speterint insn_name_ptr_size = 0; 6617721Speter 6717721Speter/* Data structure for a listhead of decision trees. The alternatives 6817721Speter to a node are kept in a doublely-linked list so we can easily add nodes 6917721Speter to the proper place when merging. */ 7017721Speter 7117721Speterstruct decision_head { struct decision *first, *last; }; 7217721Speter 7317721Speter/* Data structure for decision tree for recognizing 7417721Speter legitimate instructions. */ 7517721Speter 7617721Speterstruct decision 7717721Speter{ 7817721Speter int number; /* Node number, used for labels */ 7917721Speter char *position; /* String denoting position in pattern */ 8017721Speter RTX_CODE code; /* Code to test for or UNKNOWN to suppress */ 8117721Speter char ignore_code; /* If non-zero, need not test code */ 8217721Speter char ignore_mode; /* If non-zero, need not test mode */ 8317721Speter int veclen; /* Length of vector, if nonzero */ 8417721Speter enum machine_mode mode; /* Machine mode of node */ 8517721Speter char enforce_mode; /* If non-zero, test `mode' */ 8617721Speter char retest_code, retest_mode; /* See write_tree_1 */ 8717721Speter int test_elt_zero_int; /* Nonzero if should test XINT (rtl, 0) */ 8817721Speter int elt_zero_int; /* Required value for XINT (rtl, 0) */ 8917721Speter int test_elt_one_int; /* Nonzero if should test XINT (rtl, 1) */ 9017721Speter int elt_one_int; /* Required value for XINT (rtl, 1) */ 9117721Speter int test_elt_zero_wide; /* Nonzero if should test XWINT (rtl, 0) */ 9217721Speter HOST_WIDE_INT elt_zero_wide; /* Required value for XWINT (rtl, 0) */ 9317721Speter const char *tests; /* If nonzero predicate to call */ 9417721Speter int pred; /* `preds' index of predicate or -1 */ 9517721Speter char *c_test; /* Additional test to perform */ 9617721Speter struct decision_head success; /* Nodes to test on success */ 9717721Speter int insn_code_number; /* Insn number matched, if success */ 9817721Speter int num_clobbers_to_add; /* Number of CLOBBERs to be added to pattern */ 9917721Speter struct decision *next; /* Node to test on failure */ 10017721Speter struct decision *prev; /* Node whose failure tests us */ 10117721Speter struct decision *afterward; /* Node to test on success, but failure of 10217721Speter successor nodes */ 10317721Speter int opno; /* Operand number, if >= 0 */ 10417721Speter int dupno; /* Number of operand to compare against */ 10517721Speter int label_needed; /* Nonzero if label needed when writing tree */ 10617721Speter int subroutine_number; /* Number of subroutine this node starts */ 10717721Speter}; 10817721Speter 10925839Speter#define SUBROUTINE_THRESHOLD 50 11066525Speter 11117721Speterstatic int next_subroutine_number; 11217721Speter 11325839Speter/* We can write two types of subroutines: One for insn recognition and 11425839Speter one to split insns. This defines which type is being written. */ 11525839Speter 11625839Speterenum routine_type {RECOG, SPLIT}; 11725839Speter 11825839Speter/* Next available node number for tree nodes. */ 11917721Speter 12017721Speterstatic int next_number; 12117721Speter 12217721Speter/* Next number to use as an insn_code. */ 12325839Speter 12417721Speterstatic int next_insn_code; 12517721Speter 12625839Speter/* Similar, but counts all expressions in the MD file; used for 12725839Speter error messages. */ 12825839Speter 12925839Speterstatic int next_index; 13017721Speter 13117721Speter/* Record the highest depth we ever have so we know how many variables to 13217721Speter allocate in each subroutine we make. */ 13317721Speter 13417721Speterstatic int max_depth; 13517721Speter 13617721Speter/* This table contains a list of the rtl codes that can possibly match a 13717721Speter predicate defined in recog.c. The function `not_both_true' uses it to 13817721Speter deduce that there are no expressions that can be matches by certain pairs 13917721Speter of tree nodes. Also, if a predicate can match only one code, we can 14017721Speter hardwire that code into the node testing the predicate. */ 14117721Speter 14217721Speterstatic struct pred_table 14317721Speter{ 14417721Speter const char *name; 14517721Speter RTX_CODE codes[NUM_RTX_CODE]; 14617721Speter} preds[] 14717721Speter = {{"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF, 14817721Speter LABEL_REF, SUBREG, REG, MEM}}, 14917721Speter#ifdef PREDICATE_CODES 15017721Speter PREDICATE_CODES 15117721Speter#endif 15217721Speter {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF, 15317721Speter LABEL_REF, SUBREG, REG, MEM, PLUS, MINUS, MULT}}, 15417721Speter {"register_operand", {SUBREG, REG}}, 15566525Speter {"scratch_operand", {SCRATCH, REG}}, 15617721Speter {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF, 15717721Speter LABEL_REF}}, 15817721Speter {"const_int_operand", {CONST_INT}}, 15917721Speter {"const_double_operand", {CONST_INT, CONST_DOUBLE}}, 16017721Speter {"nonimmediate_operand", {SUBREG, REG, MEM}}, 16117721Speter {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF, 16217721Speter LABEL_REF, SUBREG, REG}}, 16317721Speter {"push_operand", {MEM}}, 16417721Speter {"pop_operand", {MEM}}, 16517721Speter {"memory_operand", {SUBREG, MEM}}, 16617721Speter {"indirect_operand", {SUBREG, MEM}}, 16717721Speter {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU}}, 16817721Speter {"mode_independent_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF, 16917721Speter LABEL_REF, SUBREG, REG, MEM}}}; 17017721Speter 17117721Speter#define NUM_KNOWN_PREDS (sizeof preds / sizeof preds[0]) 17217721Speter 17317721Speterstatic struct decision_head make_insn_sequence PROTO((rtx, enum routine_type)); 17417721Speterstatic struct decision *add_to_sequence PROTO((rtx, struct decision_head *, 17517721Speter const char *)); 17617721Speterstatic int not_both_true PROTO((struct decision *, struct decision *, 17717721Speter int)); 17817721Speterstatic int position_merit PROTO((struct decision *, enum machine_mode, 17917721Speter enum rtx_code)); 18017721Speterstatic struct decision_head merge_trees PROTO((struct decision_head, 18117721Speter struct decision_head)); 18217721Speterstatic int break_out_subroutines PROTO((struct decision_head, 18317721Speter enum routine_type, int)); 18417721Speterstatic void write_subroutine PROTO((struct decision *, enum routine_type)); 18517721Speterstatic void write_tree_1 PROTO((struct decision *, const char *, 18617721Speter struct decision *, enum routine_type)); 18717721Speterstatic void print_code PROTO((enum rtx_code)); 18817721Speterstatic int same_codes PROTO((struct decision *, enum rtx_code)); 18917721Speterstatic void clear_codes PROTO((struct decision *)); 19017721Speterstatic int same_modes PROTO((struct decision *, enum machine_mode)); 19117721Speterstatic void clear_modes PROTO((struct decision *)); 19217721Speterstatic void write_tree PROTO((struct decision *, const char *, 19317721Speter struct decision *, int, 19417721Speter enum routine_type)); 19517721Speterstatic void change_state PROTO((const char *, const char *, int)); 19617721Spetervoid fatal PVPROTO((const char *, ...)) 19717721Speter ATTRIBUTE_PRINTF_1 ATTRIBUTE_NORETURN; 19817721Spetervoid fancy_abort PROTO((void)) ATTRIBUTE_NORETURN; 19917721Speter 20017721Speter/* Construct and return a sequence of decisions 20117721Speter that will recognize INSN. 20217721Speter 203128266Speter TYPE says what type of routine we are recognizing (RECOG or SPLIT). */ 20417721Speter 20517721Speterstatic struct decision_head 20617721Spetermake_insn_sequence (insn, type) 20717721Speter rtx insn; 20817721Speter enum routine_type type; 20917721Speter{ 21017721Speter rtx x; 21117721Speter char *c_test = XSTR (insn, type == RECOG ? 2 : 1); 21217721Speter struct decision *last; 21317721Speter struct decision_head head; 21417721Speter 21517721Speter { 21617721Speter static char *last_real_name = "insn"; 21717721Speter static int last_real_code = 0; 21825839Speter char *name; 21966525Speter 22017721Speter if (insn_name_ptr_size <= next_insn_code) 22117721Speter { 22225839Speter int new_size; 22325839Speter new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512); 22425839Speter insn_name_ptr = 22517721Speter (char **) xrealloc (insn_name_ptr, sizeof(char *) * new_size); 22617721Speter bzero ((PTR)(insn_name_ptr + insn_name_ptr_size), 22717721Speter sizeof(char *) * (new_size - insn_name_ptr_size)); 22832785Speter insn_name_ptr_size = new_size; 22932785Speter } 23032785Speter 23117721Speter name = XSTR (insn, 0); 23217721Speter if (!name || name[0] == '\0') 23317721Speter { 23417721Speter name = xmalloc (strlen (last_real_name) + 10); 23532785Speter sprintf (name, "%s+%d", last_real_name, 23617721Speter next_insn_code - last_real_code); 23732785Speter } 23817721Speter else 23917721Speter { 24017721Speter last_real_name = name; 24117721Speter last_real_code = next_insn_code; 24232785Speter } 24332785Speter 24432785Speter insn_name_ptr[next_insn_code] = name; 24517721Speter } 24617721Speter 24717721Speter if (XVECLEN (insn, type == RECOG) == 1) 24817721Speter x = XVECEXP (insn, type == RECOG, 0); 24917721Speter else 25017721Speter { 25117721Speter x = rtx_alloc (PARALLEL); 25217721Speter XVEC (x, 0) = XVEC (insn, type == RECOG); 25317721Speter PUT_MODE (x, VOIDmode); 25417721Speter } 25517721Speter 25617721Speter last = add_to_sequence (x, &head, ""); 25717721Speter 25817721Speter if (c_test[0]) 25917721Speter last->c_test = c_test; 26017721Speter last->insn_code_number = next_insn_code; 26117721Speter last->num_clobbers_to_add = 0; 26217721Speter 26317721Speter /* If this is not a DEFINE_SPLIT and X is a PARALLEL, see if it ends with a 26417721Speter group of CLOBBERs of (hard) registers or MATCH_SCRATCHes. If so, set up 26517721Speter to recognize the pattern without these CLOBBERs. */ 26617721Speter 26732785Speter if (type == RECOG && GET_CODE (x) == PARALLEL) 26832785Speter { 26932785Speter int i; 27032785Speter 27117721Speter for (i = XVECLEN (x, 0); i > 0; i--) 27217721Speter if (GET_CODE (XVECEXP (x, 0, i - 1)) != CLOBBER 27317721Speter || (GET_CODE (XEXP (XVECEXP (x, 0, i - 1), 0)) != REG 27417721Speter && GET_CODE (XEXP (XVECEXP (x, 0, i - 1), 0)) != MATCH_SCRATCH)) 27532785Speter break; 27632785Speter 27732785Speter if (i != XVECLEN (x, 0)) 27832785Speter { 27932785Speter rtx new; 28032785Speter struct decision_head clobber_head; 28132785Speter 28232785Speter if (i == 1) 28332785Speter new = XVECEXP (x, 0, 0); 28432785Speter else 28532785Speter { 28632785Speter int j; 28732785Speter 28832785Speter new = rtx_alloc (PARALLEL); 28932785Speter XVEC (new, 0) = rtvec_alloc (i); 29032785Speter for (j = i - 1; j >= 0; j--) 29132785Speter XVECEXP (new, 0, j) = XVECEXP (x, 0, j); 29232785Speter } 29332785Speter 29432785Speter last = add_to_sequence (new, &clobber_head, ""); 29532785Speter 29632785Speter if (c_test[0]) 29732785Speter last->c_test = c_test; 29832785Speter last->insn_code_number = next_insn_code; 29932785Speter last->num_clobbers_to_add = XVECLEN (x, 0) - i; 30032785Speter 30117721Speter head = merge_trees (head, clobber_head); 30217721Speter } 30317721Speter } 30417721Speter 30517721Speter next_insn_code++; 30617721Speter 30717721Speter if (type == SPLIT) 30817721Speter /* Define the subroutine we will call below and emit in genemit. */ 30917721Speter printf ("extern rtx gen_split_%d ();\n", last->insn_code_number); 31017721Speter 31117721Speter return head; 31217721Speter} 31317721Speter 31417721Speter/* Create a chain of nodes to verify that an rtl expression matches 31517721Speter PATTERN. 31617721Speter 31717721Speter LAST is a pointer to the listhead in the previous node in the chain (or 31817721Speter in the calling function, for the first node). 31917721Speter 32017721Speter POSITION is the string representing the current position in the insn. 32117721Speter 32217721Speter A pointer to the final node in the chain is returned. */ 32317721Speter 32417721Speterstatic struct decision * 32517721Speteradd_to_sequence (pattern, last, position) 32617721Speter rtx pattern; 32717721Speter struct decision_head *last; 32817721Speter const char *position; 32917721Speter{ 33017721Speter register RTX_CODE code; 33117721Speter register struct decision *new 33217721Speter = (struct decision *) xmalloc (sizeof (struct decision)); 33317721Speter struct decision *this; 33417721Speter char *newpos; 33517721Speter register char *fmt; 33617721Speter register size_t i; 33717721Speter int depth = strlen (position); 33817721Speter int len; 33917721Speter 34017721Speter if (depth > max_depth) 34117721Speter max_depth = depth; 34217721Speter 34317721Speter new->number = next_number++; 34417721Speter new->position = xstrdup (position); 34517721Speter new->ignore_code = 0; 34617721Speter new->ignore_mode = 0; 34717721Speter new->enforce_mode = 1; 34817721Speter new->retest_code = new->retest_mode = 0; 34917721Speter new->veclen = 0; 35017721Speter new->test_elt_zero_int = 0; 35117721Speter new->test_elt_one_int = 0; 35217721Speter new->test_elt_zero_wide = 0; 35317721Speter new->elt_zero_int = 0; 35417721Speter new->elt_one_int = 0; 35517721Speter new->elt_zero_wide = 0; 35617721Speter new->tests = 0; 35717721Speter new->pred = -1; 35817721Speter new->c_test = 0; 35917721Speter new->success.first = new->success.last = 0; 36017721Speter new->insn_code_number = -1; 36117721Speter new->num_clobbers_to_add = 0; 36217721Speter new->next = 0; 36317721Speter new->prev = 0; 36417721Speter new->afterward = 0; 36517721Speter new->opno = -1; 36617721Speter new->dupno = -1; 36717721Speter new->label_needed = 0; 36817721Speter new->subroutine_number = 0; 36917721Speter 37017721Speter this = new; 37117721Speter 37217721Speter last->first = last->last = new; 37317721Speter 37417721Speter newpos = (char *) alloca (depth + 2); 37517721Speter strcpy (newpos, position); 37617721Speter newpos[depth + 1] = 0; 37717721Speter 37817721Speter restart: 37917721Speter 38017721Speter new->mode = GET_MODE (pattern); 38117721Speter new->code = code = GET_CODE (pattern); 38217721Speter 38317721Speter switch (code) 38417721Speter { 38517721Speter case MATCH_OPERAND: 38625839Speter case MATCH_SCRATCH: 38725839Speter case MATCH_OPERATOR: 38825839Speter case MATCH_PARALLEL: 38925839Speter case MATCH_INSN2: 39025839Speter new->opno = XINT (pattern, 0); 39125839Speter new->code = (code == MATCH_PARALLEL ? PARALLEL : UNKNOWN); 39225839Speter new->enforce_mode = 0; 39325839Speter 39425839Speter if (code == MATCH_SCRATCH) 39525839Speter new->tests = "scratch_operand"; 39625839Speter else 39725839Speter new->tests = XSTR (pattern, 1); 39825839Speter 39917721Speter if (*new->tests == 0) 40017721Speter new->tests = 0; 40117721Speter 40217721Speter /* See if we know about this predicate and save its number. If we do, 40317721Speter and it only accepts one code, note that fact. The predicate 40417721Speter `const_int_operand' only tests for a CONST_INT, so if we do so we 40517721Speter can avoid calling it at all. 40617721Speter 40725839Speter Finally, if we know that the predicate does not allow CONST_INT, we 40825839Speter know that the only way the predicate can match is if the modes match 40917721Speter (here we use the kludge of relying on the fact that "address_operand" 410128266Speter accepts CONST_INT; otherwise, it would have to be a special case), 411128266Speter so we can test the mode (but we need not). This fact should 412128266Speter considerably simplify the generated code. */ 41317721Speter 41417721Speter if (new->tests) 41517721Speter { 41617721Speter for (i = 0; i < NUM_KNOWN_PREDS; i++) 41725839Speter if (! strcmp (preds[i].name, new->tests)) 41825839Speter { 41925839Speter int j; 42025839Speter int allows_const_int = 0; 42125839Speter 42225839Speter new->pred = i; 42325839Speter 42425839Speter if (preds[i].codes[1] == 0 && new->code == UNKNOWN) 42525839Speter { 42625839Speter new->code = preds[i].codes[0]; 42725839Speter if (! strcmp ("const_int_operand", new->tests)) 42825839Speter new->tests = 0, new->pred = -1; 42925839Speter } 43025839Speter 43125839Speter for (j = 0; j < NUM_RTX_CODE && preds[i].codes[j] != 0; j++) 43225839Speter if (preds[i].codes[j] == CONST_INT) 43317721Speter allows_const_int = 1; 43425839Speter 43517721Speter if (! allows_const_int) 43625839Speter new->enforce_mode = new->ignore_mode= 1; 43725839Speter 43825839Speter break; 43925839Speter } 44025839Speter 44125839Speter#ifdef PREDICATE_CODES 44217721Speter /* If the port has a list of the predicates it uses but omits 44325839Speter one, warn. */ 44425839Speter if (i == NUM_KNOWN_PREDS) 44517721Speter fprintf (stderr, "Warning: `%s' not in PREDICATE_CODES\n", 44617721Speter new->tests); 44734461Speter#endif 44834461Speter } 44934461Speter 45034461Speter if (code == MATCH_OPERATOR || code == MATCH_PARALLEL) 45134461Speter { 45234461Speter for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++) 45334461Speter { 45434461Speter newpos[depth] = i + (code == MATCH_OPERATOR ? '0': 'a'); 45534461Speter new = add_to_sequence (XVECEXP (pattern, 2, i), 45634461Speter &new->success, newpos); 45734461Speter } 45817721Speter } 45917721Speter 46025839Speter return new; 46125839Speter 46225839Speter case MATCH_OP_DUP: 46317721Speter new->opno = XINT (pattern, 0); 46417721Speter new->dupno = XINT (pattern, 0); 46517721Speter new->code = UNKNOWN; 46617721Speter new->tests = 0; 46766525Speter for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++) 46817721Speter { 46917721Speter newpos[depth] = i + '0'; 47017721Speter new = add_to_sequence (XVECEXP (pattern, 1, i), 47117721Speter &new->success, newpos); 47217721Speter } 47317721Speter return new; 47417721Speter 47517721Speter case MATCH_DUP: 47617721Speter case MATCH_PAR_DUP: 47717721Speter new->dupno = XINT (pattern, 0); 47817721Speter new->code = UNKNOWN; 47917721Speter new->enforce_mode = 0; 48025839Speter return new; 48166525Speter 48217721Speter case ADDRESS: 48317721Speter pattern = XEXP (pattern, 0); 48417721Speter goto restart; 48517721Speter 48617721Speter case SET: 48717721Speter /* The operands of a SET must have the same mode unless one is VOIDmode. */ 48817721Speter if (GET_MODE (SET_SRC (pattern)) != VOIDmode 48917721Speter && GET_MODE (SET_DEST (pattern)) != VOIDmode 49017721Speter && GET_MODE (SET_SRC (pattern)) != GET_MODE (SET_DEST (pattern)) 49117721Speter /* The mode of an ADDRESS_OPERAND is the mode of the memory reference, 49217721Speter not the mode of the address. */ 49317721Speter && ! (GET_CODE (SET_SRC (pattern)) == MATCH_OPERAND 49417721Speter && ! strcmp (XSTR (SET_SRC (pattern), 1), "address_operand"))) 49517721Speter { 49617721Speter print_rtl (stderr, pattern); 49717721Speter fputc ('\n', stderr); 49817721Speter fatal ("mode mismatch in SET"); 499128266Speter } 500128266Speter newpos[depth] = '0'; 501128266Speter new = add_to_sequence (SET_DEST (pattern), &new->success, newpos); 502128266Speter this->success.first->enforce_mode = 1; 50317721Speter newpos[depth] = '1'; 50417721Speter new = add_to_sequence (SET_SRC (pattern), &new->success, newpos); 50517721Speter 50617721Speter /* If set are setting CC0 from anything other than a COMPARE, we 50725839Speter must enforce the mode so that we do not produce ambiguous insns. */ 50825839Speter if (GET_CODE (SET_DEST (pattern)) == CC0 50925839Speter && GET_CODE (SET_SRC (pattern)) != COMPARE) 51025839Speter this->success.first->enforce_mode = 1; 51125839Speter return new; 51217721Speter 51317721Speter case SIGN_EXTEND: 51417721Speter case ZERO_EXTEND: 51517721Speter case STRICT_LOW_PART: 51617721Speter newpos[depth] = '0'; 51717721Speter new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos); 51817721Speter this->success.first->enforce_mode = 1; 51917721Speter return new; 52017721Speter 52117721Speter case SUBREG: 522128266Speter this->test_elt_one_int = 1; 523128266Speter this->elt_one_int = XINT (pattern, 1); 52417721Speter newpos[depth] = '0'; 52517721Speter new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos); 52617721Speter this->success.first->enforce_mode = 1; 52717721Speter return new; 52817721Speter 529 case ZERO_EXTRACT: 530 case SIGN_EXTRACT: 531 newpos[depth] = '0'; 532 new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos); 533 this->success.first->enforce_mode = 1; 534 newpos[depth] = '1'; 535 new = add_to_sequence (XEXP (pattern, 1), &new->success, newpos); 536 newpos[depth] = '2'; 537 new = add_to_sequence (XEXP (pattern, 2), &new->success, newpos); 538 return new; 539 540 case EQ: case NE: case LE: case LT: case GE: case GT: 541 case LEU: case LTU: case GEU: case GTU: 542 /* If the first operand is (cc0), we don't have to do anything 543 special. */ 544 if (GET_CODE (XEXP (pattern, 0)) == CC0) 545 break; 546 547 /* ... fall through ... */ 548 549 case COMPARE: 550 /* Enforce the mode on the first operand to avoid ambiguous insns. */ 551 newpos[depth] = '0'; 552 new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos); 553 this->success.first->enforce_mode = 1; 554 newpos[depth] = '1'; 555 new = add_to_sequence (XEXP (pattern, 1), &new->success, newpos); 556 return new; 557 558 default: 559 break; 560 } 561 562 fmt = GET_RTX_FORMAT (code); 563 len = GET_RTX_LENGTH (code); 564 for (i = 0; i < (size_t) len; i++) 565 { 566 newpos[depth] = '0' + i; 567 if (fmt[i] == 'e' || fmt[i] == 'u') 568 new = add_to_sequence (XEXP (pattern, i), &new->success, newpos); 569 else if (fmt[i] == 'i' && i == 0) 570 { 571 this->test_elt_zero_int = 1; 572 this->elt_zero_int = XINT (pattern, i); 573 } 574 else if (fmt[i] == 'i' && i == 1) 575 { 576 this->test_elt_one_int = 1; 577 this->elt_one_int = XINT (pattern, i); 578 } 579 else if (fmt[i] == 'w' && i == 0) 580 { 581 this->test_elt_zero_wide = 1; 582 this->elt_zero_wide = XWINT (pattern, i); 583 } 584 else if (fmt[i] == 'E') 585 { 586 register int j; 587 /* We do not handle a vector appearing as other than 588 the first item, just because nothing uses them 589 and by handling only the special case 590 we can use one element in newpos for either 591 the item number of a subexpression 592 or the element number in a vector. */ 593 if (i != 0) 594 abort (); 595 this->veclen = XVECLEN (pattern, i); 596 for (j = 0; j < XVECLEN (pattern, i); j++) 597 { 598 newpos[depth] = 'a' + j; 599 new = add_to_sequence (XVECEXP (pattern, i, j), 600 &new->success, newpos); 601 } 602 } 603 else if (fmt[i] != '0') 604 abort (); 605 } 606 return new; 607} 608 609/* Return 1 if we can prove that there is no RTL that can match both 610 D1 and D2. Otherwise, return 0 (it may be that there is an RTL that 611 can match both or just that we couldn't prove there wasn't such an RTL). 612 613 TOPLEVEL is non-zero if we are to only look at the top level and not 614 recursively descend. */ 615 616static int 617not_both_true (d1, d2, toplevel) 618 struct decision *d1, *d2; 619 int toplevel; 620{ 621 struct decision *p1, *p2; 622 623 /* If they are both to test modes and the modes are different, they aren't 624 both true. Similarly for codes, integer elements, and vector lengths. */ 625 626 if ((d1->enforce_mode && d2->enforce_mode 627 && d1->mode != VOIDmode && d2->mode != VOIDmode && d1->mode != d2->mode) 628 || (d1->code != UNKNOWN && d2->code != UNKNOWN && d1->code != d2->code) 629 || (d1->test_elt_zero_int && d2->test_elt_zero_int 630 && d1->elt_zero_int != d2->elt_zero_int) 631 || (d1->test_elt_one_int && d2->test_elt_one_int 632 && d1->elt_one_int != d2->elt_one_int) 633 || (d1->test_elt_zero_wide && d2->test_elt_zero_wide 634 && d1->elt_zero_wide != d2->elt_zero_wide) 635 || (d1->veclen && d2->veclen && d1->veclen != d2->veclen)) 636 return 1; 637 638 /* If either is a wild-card MATCH_OPERAND without a predicate, it can match 639 absolutely anything, so we can't say that no intersection is possible. 640 This case is detected by having a zero TESTS field with a code of 641 UNKNOWN. */ 642 643 if ((d1->tests == 0 && d1->code == UNKNOWN) 644 || (d2->tests == 0 && d2->code == UNKNOWN)) 645 return 0; 646 647 /* If either has a predicate that we know something about, set things up so 648 that D1 is the one that always has a known predicate. Then see if they 649 have any codes in common. */ 650 651 if (d1->pred >= 0 || d2->pred >= 0) 652 { 653 int i, j; 654 655 if (d2->pred >= 0) 656 p1 = d1, d1 = d2, d2 = p1; 657 658 /* If D2 tests an explicit code, see if it is in the list of valid codes 659 for D1's predicate. */ 660 if (d2->code != UNKNOWN) 661 { 662 for (i = 0; i < NUM_RTX_CODE && preds[d1->pred].codes[i] != 0; i++) 663 if (preds[d1->pred].codes[i] == d2->code) 664 break; 665 666 if (preds[d1->pred].codes[i] == 0) 667 return 1; 668 } 669 670 /* Otherwise see if the predicates have any codes in common. */ 671 672 else if (d2->pred >= 0) 673 { 674 for (i = 0; i < NUM_RTX_CODE && preds[d1->pred].codes[i] != 0; i++) 675 { 676 for (j = 0; j < NUM_RTX_CODE; j++) 677 if (preds[d2->pred].codes[j] == 0 678 || preds[d2->pred].codes[j] == preds[d1->pred].codes[i]) 679 break; 680 681 if (preds[d2->pred].codes[j] != 0) 682 break; 683 } 684 685 if (preds[d1->pred].codes[i] == 0) 686 return 1; 687 } 688 } 689 690 /* If we got here, we can't prove that D1 and D2 cannot both be true. 691 If we are only to check the top level, return 0. Otherwise, see if 692 we can prove that all choices in both successors are mutually 693 exclusive. If either does not have any successors, we can't prove 694 they can't both be true. */ 695 696 if (toplevel || d1->success.first == 0 || d2->success.first == 0) 697 return 0; 698 699 for (p1 = d1->success.first; p1; p1 = p1->next) 700 for (p2 = d2->success.first; p2; p2 = p2->next) 701 if (! not_both_true (p1, p2, 0)) 702 return 0; 703 704 return 1; 705} 706 707/* Assuming that we can reorder all the alternatives at a specific point in 708 the tree (see discussion in merge_trees), we would prefer an ordering of 709 nodes where groups of consecutive nodes test the same mode and, within each 710 mode, groups of nodes test the same code. With this order, we can 711 construct nested switch statements, the inner one to test the code and 712 the outer one to test the mode. 713 714 We would like to list nodes testing for specific codes before those 715 that test predicates to avoid unnecessary function calls. Similarly, 716 tests for specific modes should precede nodes that allow any mode. 717 718 This function returns the merit (with 0 being the best) of inserting 719 a test involving the specified MODE and CODE after node P. If P is 720 zero, we are to determine the merit of inserting the test at the front 721 of the list. */ 722 723static int 724position_merit (p, mode, code) 725 struct decision *p; 726 enum machine_mode mode; 727 enum rtx_code code; 728{ 729 enum machine_mode p_mode; 730 731 /* The only time the front of the list is anything other than the worst 732 position is if we are testing a mode that isn't VOIDmode. */ 733 if (p == 0) 734 return mode == VOIDmode ? 3 : 2; 735 736 p_mode = p->enforce_mode ? p->mode : VOIDmode; 737 738 /* The best case is if the codes and modes both match. */ 739 if (p_mode == mode && p->code== code) 740 return 0; 741 742 /* If the codes don't match, the next best case is if the modes match. 743 In that case, the best position for this node depends on whether 744 we are testing for a specific code or not. If we are, the best place 745 is after some other test for an explicit code and our mode or after 746 the last test in the previous mode if every test in our mode is for 747 an unknown code. 748 749 If we are testing for UNKNOWN, then the next best case is at the end of 750 our mode. */ 751 752 if ((code != UNKNOWN 753 && ((p_mode == mode && p->code != UNKNOWN) 754 || (p_mode != mode && p->next 755 && (p->next->enforce_mode ? p->next->mode : VOIDmode) == mode 756 && (p->next->code == UNKNOWN)))) 757 || (code == UNKNOWN && p_mode == mode 758 && (p->next == 0 759 || (p->next->enforce_mode ? p->next->mode : VOIDmode) != mode))) 760 return 1; 761 762 /* The third best case occurs when nothing is testing MODE. If MODE 763 is not VOIDmode, then the third best case is after something of any 764 mode that is not VOIDmode. If we are testing VOIDmode, the third best 765 place is the end of the list. */ 766 767 if (p_mode != mode 768 && ((mode != VOIDmode && p_mode != VOIDmode) 769 || (mode == VOIDmode && p->next == 0))) 770 return 2; 771 772 /* Otherwise, we have the worst case. */ 773 return 3; 774} 775 776/* Merge two decision tree listheads OLDH and ADDH, 777 modifying OLDH destructively, and return the merged tree. */ 778 779static struct decision_head 780merge_trees (oldh, addh) 781 register struct decision_head oldh, addh; 782{ 783 struct decision *add, *next; 784 785 if (oldh.first == 0) 786 return addh; 787 788 if (addh.first == 0) 789 return oldh; 790 791 /* If we are adding things at different positions, something is wrong. */ 792 if (strcmp (oldh.first->position, addh.first->position)) 793 abort (); 794 795 for (add = addh.first; add; add = next) 796 { 797 enum machine_mode add_mode = add->enforce_mode ? add->mode : VOIDmode; 798 struct decision *best_position = 0; 799 int best_merit = 4; 800 struct decision *old; 801 802 next = add->next; 803 804 /* The semantics of pattern matching state that the tests are done in 805 the order given in the MD file so that if an insn matches two 806 patterns, the first one will be used. However, in practice, most, 807 if not all, patterns are unambiguous so that their order is 808 independent. In that case, we can merge identical tests and 809 group all similar modes and codes together. 810 811 Scan starting from the end of OLDH until we reach a point 812 where we reach the head of the list or where we pass a pattern 813 that could also be true if NEW is true. If we find an identical 814 pattern, we can merge them. Also, record the last node that tests 815 the same code and mode and the last one that tests just the same mode. 816 817 If we have no match, place NEW after the closest match we found. */ 818 819 for (old = oldh.last; old; old = old->prev) 820 { 821 int our_merit; 822 823 /* If we don't have anything to test except an additional test, 824 do not consider the two nodes equal. If we did, the test below 825 would cause an infinite recursion. */ 826 if (old->tests == 0 && old->test_elt_zero_int == 0 827 && old->test_elt_one_int == 0 && old->veclen == 0 828 && old->test_elt_zero_wide == 0 829 && old->dupno == -1 && old->mode == VOIDmode 830 && old->code == UNKNOWN 831 && (old->c_test != 0 || add->c_test != 0)) 832 ; 833 834 else if ((old->tests == add->tests 835 || (old->pred >= 0 && old->pred == add->pred) 836 || (old->tests && add->tests 837 && !strcmp (old->tests, add->tests))) 838 && old->test_elt_zero_int == add->test_elt_zero_int 839 && old->elt_zero_int == add->elt_zero_int 840 && old->test_elt_one_int == add->test_elt_one_int 841 && old->elt_one_int == add->elt_one_int 842 && old->test_elt_zero_wide == add->test_elt_zero_wide 843 && old->elt_zero_wide == add->elt_zero_wide 844 && old->veclen == add->veclen 845 && old->dupno == add->dupno 846 && old->opno == add->opno 847 && old->code == add->code 848 && old->enforce_mode == add->enforce_mode 849 && old->mode == add->mode) 850 { 851 /* If the additional test is not the same, split both nodes 852 into nodes that just contain all things tested before the 853 additional test and nodes that contain the additional test 854 and actions when it is true. This optimization is important 855 because of the case where we have almost identical patterns 856 with different tests on target flags. */ 857 858 if (old->c_test != add->c_test 859 && ! (old->c_test && add->c_test 860 && !strcmp (old->c_test, add->c_test))) 861 { 862 if (old->insn_code_number >= 0 || old->opno >= 0) 863 { 864 struct decision *split 865 = (struct decision *) xmalloc (sizeof (struct decision)); 866 867 memcpy (split, old, sizeof (struct decision)); 868 869 old->success.first = old->success.last = split; 870 old->c_test = 0; 871 old->opno = -1; 872 old->insn_code_number = -1; 873 old->num_clobbers_to_add = 0; 874 875 split->number = next_number++; 876 split->next = split->prev = 0; 877 split->mode = VOIDmode; 878 split->code = UNKNOWN; 879 split->veclen = 0; 880 split->test_elt_zero_int = 0; 881 split->test_elt_one_int = 0; 882 split->test_elt_zero_wide = 0; 883 split->tests = 0; 884 split->pred = -1; 885 split->dupno = -1; 886 } 887 888 if (add->insn_code_number >= 0 || add->opno >= 0) 889 { 890 struct decision *split 891 = (struct decision *) xmalloc (sizeof (struct decision)); 892 893 memcpy (split, add, sizeof (struct decision)); 894 895 add->success.first = add->success.last = split; 896 add->c_test = 0; 897 add->opno = -1; 898 add->insn_code_number = -1; 899 add->num_clobbers_to_add = 0; 900 901 split->number = next_number++; 902 split->next = split->prev = 0; 903 split->mode = VOIDmode; 904 split->code = UNKNOWN; 905 split->veclen = 0; 906 split->test_elt_zero_int = 0; 907 split->test_elt_one_int = 0; 908 split->test_elt_zero_wide = 0; 909 split->tests = 0; 910 split->pred = -1; 911 split->dupno = -1; 912 } 913 } 914 915 if (old->insn_code_number >= 0 && add->insn_code_number >= 0) 916 { 917 /* If one node is for a normal insn and the second is 918 for the base insn with clobbers stripped off, the 919 second node should be ignored. */ 920 921 if (old->num_clobbers_to_add == 0 922 && add->num_clobbers_to_add > 0) 923 /* Nothing to do here. */ 924 ; 925 else if (old->num_clobbers_to_add > 0 926 && add->num_clobbers_to_add == 0) 927 { 928 /* In this case, replace OLD with ADD. */ 929 old->insn_code_number = add->insn_code_number; 930 old->num_clobbers_to_add = 0; 931 } 932 else 933 fatal ("Two actions at one point in tree for insns \"%s\" (%d) and \"%s\" (%d)", 934 insn_name_ptr[old->insn_code_number], 935 old->insn_code_number, 936 insn_name_ptr[add->insn_code_number], 937 add->insn_code_number); 938 } 939 940 if (old->insn_code_number == -1) 941 old->insn_code_number = add->insn_code_number; 942 old->success = merge_trees (old->success, add->success); 943 add = 0; 944 break; 945 } 946 947 /* Unless we have already found the best possible insert point, 948 see if this position is better. If so, record it. */ 949 950 if (best_merit != 0 951 && ((our_merit = position_merit (old, add_mode, add->code)) 952 < best_merit)) 953 best_merit = our_merit, best_position = old; 954 955 if (! not_both_true (old, add, 0)) 956 break; 957 } 958 959 /* If ADD was duplicate, we are done. */ 960 if (add == 0) 961 continue; 962 963 /* Otherwise, find the best place to insert ADD. Normally this is 964 BEST_POSITION. However, if we went all the way to the top of 965 the list, it might be better to insert at the top. */ 966 967 if (best_position == 0) 968 abort (); 969 970 if (old == 0 971 && position_merit (NULL_PTR, add_mode, add->code) < best_merit) 972 { 973 add->prev = 0; 974 add->next = oldh.first; 975 oldh.first->prev = add; 976 oldh.first = add; 977 } 978 979 else 980 { 981 add->prev = best_position; 982 add->next = best_position->next; 983 best_position->next = add; 984 if (best_position == oldh.last) 985 oldh.last = add; 986 else 987 add->next->prev = add; 988 } 989 } 990 991 return oldh; 992} 993 994/* Count the number of subnodes of HEAD. If the number is high enough, 995 make the first node in HEAD start a separate subroutine in the C code 996 that is generated. 997 998 TYPE gives the type of routine we are writing. 999 1000 INITIAL is non-zero if this is the highest-level node. We never write 1001 it out here. */ 1002 1003static int 1004break_out_subroutines (head, type, initial) 1005 struct decision_head head; 1006 enum routine_type type; 1007 int initial; 1008{ 1009 int size = 0; 1010 struct decision *sub; 1011 1012 for (sub = head.first; sub; sub = sub->next) 1013 size += 1 + break_out_subroutines (sub->success, type, 0); 1014 1015 if (size > SUBROUTINE_THRESHOLD && ! initial) 1016 { 1017 head.first->subroutine_number = ++next_subroutine_number; 1018 write_subroutine (head.first, type); 1019 size = 1; 1020 } 1021 return size; 1022} 1023 1024/* Write out a subroutine of type TYPE to do comparisons starting at node 1025 TREE. */ 1026 1027static void 1028write_subroutine (tree, type) 1029 struct decision *tree; 1030 enum routine_type type; 1031{ 1032 int i; 1033 1034 if (type == SPLIT) 1035 printf ("rtx\nsplit"); 1036 else 1037 printf ("int\nrecog"); 1038 1039 if (tree != 0 && tree->subroutine_number > 0) 1040 printf ("_%d", tree->subroutine_number); 1041 else if (type == SPLIT) 1042 printf ("_insns"); 1043 1044 printf (" (x0, insn"); 1045 if (type == RECOG) 1046 printf (", pnum_clobbers"); 1047 1048 printf (")\n"); 1049 printf (" register rtx x0;\n rtx insn ATTRIBUTE_UNUSED;\n"); 1050 if (type == RECOG) 1051 printf (" int *pnum_clobbers ATTRIBUTE_UNUSED;\n"); 1052 1053 printf ("{\n"); 1054 printf (" register rtx *ro = &recog_operand[0];\n"); 1055 1056 printf (" register rtx "); 1057 for (i = 1; i < max_depth; i++) 1058 printf ("x%d ATTRIBUTE_UNUSED, ", i); 1059 1060 printf ("x%d ATTRIBUTE_UNUSED;\n", max_depth); 1061 printf (" %s tem ATTRIBUTE_UNUSED;\n", type == SPLIT ? "rtx" : "int"); 1062 write_tree (tree, "", NULL_PTR, 1, type); 1063 printf (" ret0: return %d;\n}\n\n", type == SPLIT ? 0 : -1); 1064} 1065 1066/* This table is used to indent the recog_* functions when we are inside 1067 conditions or switch statements. We only support small indentations 1068 and always indent at least two spaces. */ 1069 1070static const char *indents[] 1071 = {" ", " ", " ", " ", " ", " ", " ", " ", 1072 "\t", "\t ", "\t ", "\t ", "\t ", "\t ", "\t ", 1073 "\t\t", "\t\t ", "\t\t ", "\t\t ", "\t\t ", "\t\t "}; 1074 1075/* Write out C code to perform the decisions in TREE for a subroutine of 1076 type TYPE. If all of the choices fail, branch to node AFTERWARD, if 1077 non-zero, otherwise return. PREVPOS is the position of the node that 1078 branched to this test. 1079 1080 When we merged all alternatives, we tried to set up a convenient order. 1081 Specifically, tests involving the same mode are all grouped together, 1082 followed by a group that does not contain a mode test. Within each group 1083 of the same mode, we also group tests with the same code, followed by a 1084 group that does not test a code. 1085 1086 Occasionally, we cannot arbitrarily reorder the tests so that multiple 1087 sequence of groups as described above are present. 1088 1089 We generate two nested switch statements, the outer statement for 1090 testing modes, and the inner switch for testing RTX codes. It is 1091 not worth optimizing cases when only a small number of modes or 1092 codes is tested, since the compiler can do that when compiling the 1093 resulting function. We do check for when every test is the same mode 1094 or code. */ 1095 1096static void 1097write_tree_1 (tree, prevpos, afterward, type) 1098 struct decision *tree; 1099 const char *prevpos; 1100 struct decision *afterward; 1101 enum routine_type type; 1102{ 1103 register struct decision *p, *p1; 1104 register int depth = tree ? strlen (tree->position) : 0; 1105 enum machine_mode switch_mode = VOIDmode; 1106 RTX_CODE switch_code = UNKNOWN; 1107 int uncond = 0; 1108 char modemap[NUM_MACHINE_MODES]; 1109 char codemap[NUM_RTX_CODE]; 1110 int indent = 2; 1111 int i; 1112 1113 /* One tricky area is what is the exact state when we branch to a 1114 node's label. There are two cases where we branch: when looking at 1115 successors to a node, or when a set of tests fails. 1116 1117 In the former case, we are always branching to the first node in a 1118 decision list and we want all required tests to be performed. We 1119 put the labels for such nodes in front of any switch or test statements. 1120 These branches are done without updating the position to that of the 1121 target node. 1122 1123 In the latter case, we are branching to a node that is not the first 1124 node in a decision list. We have already checked that it is possible 1125 for both the node we originally tested at this level and the node we 1126 are branching to to both match some pattern. That means that they 1127 usually will be testing the same mode and code. So it is normally safe 1128 for such labels to be inside switch statements, since the tests done 1129 by virtue of arriving at that label will usually already have been 1130 done. The exception is a branch from a node that does not test a 1131 mode or code to one that does. In such cases, we set the `retest_mode' 1132 or `retest_code' flags. That will ensure that we start a new switch 1133 at that position and put the label before the switch. 1134 1135 The branches in the latter case must set the position to that of the 1136 target node. */ 1137 1138 1139 printf ("\n"); 1140 if (tree && tree->subroutine_number == 0) 1141 { 1142 OUTPUT_LABEL (" ", tree->number); 1143 tree->label_needed = 0; 1144 } 1145 1146 if (tree) 1147 { 1148 change_state (prevpos, tree->position, 2); 1149 prevpos = tree->position; 1150 } 1151 1152 for (p = tree; p; p = p->next) 1153 { 1154 enum machine_mode mode = p->enforce_mode ? p->mode : VOIDmode; 1155 int need_bracket; 1156 int wrote_bracket = 0; 1157 int inner_indent; 1158 1159 if (p->success.first == 0 && p->insn_code_number < 0) 1160 abort (); 1161 1162 /* Find the next alternative to p that might be true when p is true. 1163 Test that one next if p's successors fail. */ 1164 1165 for (p1 = p->next; p1 && not_both_true (p, p1, 1); p1 = p1->next) 1166 ; 1167 p->afterward = p1; 1168 1169 if (p1) 1170 { 1171 if (mode == VOIDmode && p1->enforce_mode && p1->mode != VOIDmode) 1172 p1->retest_mode = 1; 1173 if (p->code == UNKNOWN && p1->code != UNKNOWN) 1174 p1->retest_code = 1; 1175 p1->label_needed = 1; 1176 } 1177 1178 /* If we have a different code or mode than the last node and 1179 are in a switch on codes, we must either end the switch or 1180 go to another case. We must also end the switch if this 1181 node needs a label and to retest either the mode or code. */ 1182 1183 if (switch_code != UNKNOWN 1184 && (switch_code != p->code || switch_mode != mode 1185 || (p->label_needed && (p->retest_mode || p->retest_code)))) 1186 { 1187 enum rtx_code code = p->code; 1188 1189 /* If P is testing a predicate that we know about and we haven't 1190 seen any of the codes that are valid for the predicate, we 1191 can write a series of "case" statement, one for each possible 1192 code. Since we are already in a switch, these redundant tests 1193 are very cheap and will reduce the number of predicate called. */ 1194 1195 if (p->pred >= 0) 1196 { 1197 for (i = 0; i < NUM_RTX_CODE && preds[p->pred].codes[i] != 0; i++) 1198 if (codemap[(int) preds[p->pred].codes[i]]) 1199 break; 1200 1201 if (preds[p->pred].codes[i] == 0) 1202 code = MATCH_OPERAND; 1203 } 1204 1205 if (code == UNKNOWN || codemap[(int) code] 1206 || switch_mode != mode 1207 || (p->label_needed && (p->retest_mode || p->retest_code))) 1208 { 1209 printf ("%s}\n", indents[indent - 2]); 1210 switch_code = UNKNOWN; 1211 indent -= 4; 1212 } 1213 else 1214 { 1215 if (! uncond) 1216 printf ("%sbreak;\n", indents[indent]); 1217 1218 if (code == MATCH_OPERAND) 1219 { 1220 for (i = 0; i < NUM_RTX_CODE && preds[p->pred].codes[i] != 0; i++) 1221 { 1222 printf ("%scase ", indents[indent - 2]); 1223 print_code (preds[p->pred].codes[i]); 1224 printf (":\n"); 1225 codemap[(int) preds[p->pred].codes[i]] = 1; 1226 } 1227 } 1228 else 1229 { 1230 printf ("%scase ", indents[indent - 2]); 1231 print_code (code); 1232 printf (":\n"); 1233 codemap[(int) p->code] = 1; 1234 } 1235 1236 switch_code = code; 1237 } 1238 1239 uncond = 0; 1240 } 1241 1242 /* If we were previously in a switch on modes and now have a different 1243 mode, end at least the case, and maybe end the switch if we are 1244 not testing a mode or testing a mode whose case we already saw. */ 1245 1246 if (switch_mode != VOIDmode 1247 && (switch_mode != mode || (p->label_needed && p->retest_mode))) 1248 { 1249 if (mode == VOIDmode || modemap[(int) mode] 1250 || (p->label_needed && p->retest_mode)) 1251 { 1252 printf ("%s}\n", indents[indent - 2]); 1253 switch_mode = VOIDmode; 1254 indent -= 4; 1255 } 1256 else 1257 { 1258 if (! uncond) 1259 printf (" break;\n"); 1260 printf (" case %smode:\n", GET_MODE_NAME (mode)); 1261 switch_mode = mode; 1262 modemap[(int) mode] = 1; 1263 } 1264 1265 uncond = 0; 1266 } 1267 1268 /* If we are about to write dead code, something went wrong. */ 1269 if (! p->label_needed && uncond) 1270 abort (); 1271 1272 /* If we need a label and we will want to retest the mode or code at 1273 that label, write the label now. We have already ensured that 1274 things will be valid for the test. */ 1275 1276 if (p->label_needed && (p->retest_mode || p->retest_code)) 1277 { 1278 OUTPUT_LABEL (indents[indent - 2], p->number); 1279 p->label_needed = 0; 1280 } 1281 1282 uncond = 0; 1283 1284 /* If we are not in any switches, see if we can shortcut things 1285 by checking for identical modes and codes. */ 1286 1287 if (switch_mode == VOIDmode && switch_code == UNKNOWN) 1288 { 1289 /* If p and its alternatives all want the same mode, 1290 reject all others at once, first, then ignore the mode. */ 1291 1292 if (mode != VOIDmode && p->next && same_modes (p, mode)) 1293 { 1294 printf (" if (GET_MODE (x%d) != %smode)\n", 1295 depth, GET_MODE_NAME (p->mode)); 1296 if (afterward) 1297 { 1298 printf (" {\n"); 1299 change_state (p->position, afterward->position, 6); 1300 printf (" goto L%d;\n }\n", afterward->number); 1301 } 1302 else 1303 printf (" goto ret0;\n"); 1304 clear_modes (p); 1305 mode = VOIDmode; 1306 } 1307 1308 /* If p and its alternatives all want the same code, 1309 reject all others at once, first, then ignore the code. */ 1310 1311 if (p->code != UNKNOWN && p->next && same_codes (p, p->code)) 1312 { 1313 printf (" if (GET_CODE (x%d) != ", depth); 1314 print_code (p->code); 1315 printf (")\n"); 1316 if (afterward) 1317 { 1318 printf (" {\n"); 1319 change_state (p->position, afterward->position, indent + 4); 1320 printf (" goto L%d;\n }\n", afterward->number); 1321 } 1322 else 1323 printf (" goto ret0;\n"); 1324 clear_codes (p); 1325 } 1326 } 1327 1328 /* If we are not in a mode switch and we are testing for a specific 1329 mode, start a mode switch unless we have just one node or the next 1330 node is not testing a mode (we have already tested for the case of 1331 more than one mode, but all of the same mode). */ 1332 1333 if (switch_mode == VOIDmode && mode != VOIDmode && p->next != 0 1334 && p->next->enforce_mode && p->next->mode != VOIDmode) 1335 { 1336 memset (modemap, 0, sizeof modemap); 1337 printf ("%sswitch (GET_MODE (x%d))\n", indents[indent], depth); 1338 printf ("%s{\n", indents[indent + 2]); 1339 indent += 4; 1340 printf ("%sdefault:\n%sbreak;\n", indents[indent - 2], 1341 indents[indent]); 1342 printf ("%scase %smode:\n", indents[indent - 2], 1343 GET_MODE_NAME (mode)); 1344 modemap[(int) mode] = 1; 1345 switch_mode = mode; 1346 } 1347 1348 /* Similarly for testing codes. */ 1349 1350 if (switch_code == UNKNOWN && p->code != UNKNOWN && ! p->ignore_code 1351 && p->next != 0 && p->next->code != UNKNOWN) 1352 { 1353 memset (codemap, 0, sizeof codemap); 1354 printf ("%sswitch (GET_CODE (x%d))\n", indents[indent], depth); 1355 printf ("%s{\n", indents[indent + 2]); 1356 indent += 4; 1357 printf ("%sdefault:\n%sbreak;\n", indents[indent - 2], 1358 indents[indent]); 1359 printf ("%scase ", indents[indent - 2]); 1360 print_code (p->code); 1361 printf (":\n"); 1362 codemap[(int) p->code] = 1; 1363 switch_code = p->code; 1364 } 1365 1366 /* Now that most mode and code tests have been done, we can write out 1367 a label for an inner node, if we haven't already. */ 1368 if (p->label_needed) 1369 OUTPUT_LABEL (indents[indent - 2], p->number); 1370 1371 inner_indent = indent; 1372 1373 /* The only way we can have to do a mode or code test here is if 1374 this node needs such a test but is the only node to be tested. 1375 In that case, we won't have started a switch. Note that this is 1376 the only way the switch and test modes can disagree. */ 1377 1378 if ((mode != switch_mode && ! p->ignore_mode) 1379 || (p->code != switch_code && p->code != UNKNOWN && ! p->ignore_code) 1380 || p->test_elt_zero_int || p->test_elt_one_int 1381 || p->test_elt_zero_wide || p->veclen 1382 || p->dupno >= 0 || p->tests || p->num_clobbers_to_add) 1383 { 1384 printf ("%sif (", indents[indent]); 1385 1386 if (mode != switch_mode && ! p->ignore_mode) 1387 printf ("GET_MODE (x%d) == %smode && ", 1388 depth, GET_MODE_NAME (mode)); 1389 if (p->code != switch_code && p->code != UNKNOWN && ! p->ignore_code) 1390 { 1391 printf ("GET_CODE (x%d) == ", depth); 1392 print_code (p->code); 1393 printf (" && "); 1394 } 1395 1396 if (p->test_elt_zero_int) 1397 printf ("XINT (x%d, 0) == %d && ", depth, p->elt_zero_int); 1398 if (p->test_elt_one_int) 1399 printf ("XINT (x%d, 1) == %d && ", depth, p->elt_one_int); 1400 if (p->test_elt_zero_wide) 1401 { 1402 /* Set offset to 1 iff the number might get propagated to 1403 unsigned long by ANSI C rules, else 0. 1404 Prospective hosts are required to have at least 32 bit 1405 ints, and integer constants in machine descriptions 1406 must fit in 32 bit, thus it suffices to check only 1407 for 1 << 31 . */ 1408 HOST_WIDE_INT offset = p->elt_zero_wide == -2147483647 - 1; 1409 printf ("XWINT (x%d, 0) == ", depth); 1410 printf (HOST_WIDE_INT_PRINT_DEC, p->elt_zero_wide + offset); 1411 printf ("%s && ", offset ? "-1" : ""); 1412 } 1413 if (p->veclen) 1414 printf ("XVECLEN (x%d, 0) == %d && ", depth, p->veclen); 1415 if (p->dupno >= 0) 1416 printf ("rtx_equal_p (x%d, ro[%d]) && ", depth, p->dupno); 1417 if (p->num_clobbers_to_add) 1418 printf ("pnum_clobbers != 0 && "); 1419 if (p->tests) 1420 printf ("%s (x%d, %smode)", p->tests, depth, 1421 GET_MODE_NAME (p->mode)); 1422 else 1423 printf ("1"); 1424 1425 printf (")\n"); 1426 inner_indent += 2; 1427 } 1428 else 1429 uncond = 1; 1430 1431 need_bracket = ! uncond; 1432 1433 if (p->opno >= 0) 1434 { 1435 if (need_bracket) 1436 { 1437 printf ("%s{\n", indents[inner_indent]); 1438 inner_indent += 2; 1439 wrote_bracket = 1; 1440 need_bracket = 0; 1441 } 1442 1443 printf ("%sro[%d] = x%d;\n", indents[inner_indent], p->opno, depth); 1444 } 1445 1446 if (p->c_test) 1447 { 1448 printf ("%sif (%s)\n", indents[inner_indent], p->c_test); 1449 inner_indent += 2; 1450 uncond = 0; 1451 need_bracket = 1; 1452 } 1453 1454 if (p->insn_code_number >= 0) 1455 { 1456 if (type == SPLIT) 1457 printf ("%sreturn gen_split_%d (operands);\n", 1458 indents[inner_indent], p->insn_code_number); 1459 else 1460 { 1461 if (p->num_clobbers_to_add) 1462 { 1463 if (need_bracket) 1464 { 1465 printf ("%s{\n", indents[inner_indent]); 1466 inner_indent += 2; 1467 } 1468 1469 printf ("%s*pnum_clobbers = %d;\n", 1470 indents[inner_indent], p->num_clobbers_to_add); 1471 printf ("%sreturn %d;\n", 1472 indents[inner_indent], p->insn_code_number); 1473 1474 if (need_bracket) 1475 { 1476 inner_indent -= 2; 1477 printf ("%s}\n", indents[inner_indent]); 1478 } 1479 } 1480 else 1481 printf ("%sreturn %d;\n", 1482 indents[inner_indent], p->insn_code_number); 1483 } 1484 } 1485 else 1486 printf ("%sgoto L%d;\n", indents[inner_indent], 1487 p->success.first->number); 1488 1489 if (wrote_bracket) 1490 printf ("%s}\n", indents[inner_indent - 2]); 1491 } 1492 1493 /* We have now tested all alternatives. End any switches we have open 1494 and branch to the alternative node unless we know that we can't fall 1495 through to the branch. */ 1496 1497 if (switch_code != UNKNOWN) 1498 { 1499 printf ("%s}\n", indents[indent - 2]); 1500 indent -= 4; 1501 uncond = 0; 1502 } 1503 1504 if (switch_mode != VOIDmode) 1505 { 1506 printf ("%s}\n", indents[indent - 2]); 1507 indent -= 4; 1508 uncond = 0; 1509 } 1510 1511 if (indent != 2) 1512 abort (); 1513 1514 if (uncond) 1515 return; 1516 1517 if (afterward) 1518 { 1519 change_state (prevpos, afterward->position, 2); 1520 printf (" goto L%d;\n", afterward->number); 1521 } 1522 else 1523 printf (" goto ret0;\n"); 1524} 1525 1526static void 1527print_code (code) 1528 enum rtx_code code; 1529{ 1530 register char *p1; 1531 for (p1 = GET_RTX_NAME (code); *p1; p1++) 1532 { 1533 if (*p1 >= 'a' && *p1 <= 'z') 1534 putchar (*p1 + 'A' - 'a'); 1535 else 1536 putchar (*p1); 1537 } 1538} 1539 1540static int 1541same_codes (p, code) 1542 register struct decision *p; 1543 register enum rtx_code code; 1544{ 1545 for (; p; p = p->next) 1546 if (p->code != code) 1547 return 0; 1548 1549 return 1; 1550} 1551 1552static void 1553clear_codes (p) 1554 register struct decision *p; 1555{ 1556 for (; p; p = p->next) 1557 p->ignore_code = 1; 1558} 1559 1560static int 1561same_modes (p, mode) 1562 register struct decision *p; 1563 register enum machine_mode mode; 1564{ 1565 for (; p; p = p->next) 1566 if ((p->enforce_mode ? p->mode : VOIDmode) != mode) 1567 return 0; 1568 1569 return 1; 1570} 1571 1572static void 1573clear_modes (p) 1574 register struct decision *p; 1575{ 1576 for (; p; p = p->next) 1577 p->enforce_mode = 0; 1578} 1579 1580/* Write out the decision tree starting at TREE for a subroutine of type TYPE. 1581 1582 PREVPOS is the position at the node that branched to this node. 1583 1584 INITIAL is nonzero if this is the first node we are writing in a subroutine. 1585 1586 If all nodes are false, branch to the node AFTERWARD. */ 1587 1588static void 1589write_tree (tree, prevpos, afterward, initial, type) 1590 struct decision *tree; 1591 const char *prevpos; 1592 struct decision *afterward; 1593 int initial; 1594 enum routine_type type; 1595{ 1596 register struct decision *p; 1597 const char *name_prefix = (type == SPLIT ? "split" : "recog"); 1598 const char *call_suffix = (type == SPLIT ? "" : ", pnum_clobbers"); 1599 1600 if (! initial && tree->subroutine_number > 0) 1601 { 1602 OUTPUT_LABEL (" ", tree->number); 1603 1604 if (afterward) 1605 { 1606 printf (" tem = %s_%d (x0, insn%s);\n", 1607 name_prefix, tree->subroutine_number, call_suffix); 1608 if (type == SPLIT) 1609 printf (" if (tem != 0) return tem;\n"); 1610 else 1611 printf (" if (tem >= 0) return tem;\n"); 1612 change_state (tree->position, afterward->position, 2); 1613 printf (" goto L%d;\n", afterward->number); 1614 } 1615 else 1616 printf (" return %s_%d (x0, insn%s);\n", 1617 name_prefix, tree->subroutine_number, call_suffix); 1618 return; 1619 } 1620 1621 write_tree_1 (tree, prevpos, afterward, type); 1622 1623 for (p = tree; p; p = p->next) 1624 if (p->success.first) 1625 write_tree (p->success.first, p->position, 1626 p->afterward ? p->afterward : afterward, 0, type); 1627} 1628 1629 1630/* Assuming that the state of argument is denoted by OLDPOS, take whatever 1631 actions are necessary to move to NEWPOS. 1632 1633 INDENT says how many blanks to place at the front of lines. */ 1634 1635static void 1636change_state (oldpos, newpos, indent) 1637 const char *oldpos; 1638 const char *newpos; 1639 int indent; 1640{ 1641 int odepth = strlen (oldpos); 1642 int depth = odepth; 1643 int ndepth = strlen (newpos); 1644 1645 /* Pop up as many levels as necessary. */ 1646 1647 while (strncmp (oldpos, newpos, depth)) 1648 --depth; 1649 1650 /* Go down to desired level. */ 1651 1652 while (depth < ndepth) 1653 { 1654 if (newpos[depth] >= 'a' && newpos[depth] <= 'z') 1655 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n", 1656 indents[indent], depth + 1, depth, newpos[depth] - 'a'); 1657 else 1658 printf ("%sx%d = XEXP (x%d, %c);\n", 1659 indents[indent], depth + 1, depth, newpos[depth]); 1660 ++depth; 1661 } 1662} 1663 1664char * 1665xstrdup (input) 1666 const char *input; 1667{ 1668 register size_t len = strlen (input) + 1; 1669 register char *output = xmalloc (len); 1670 memcpy (output, input, len); 1671 return output; 1672} 1673 1674PTR 1675xrealloc (old, size) 1676 PTR old; 1677 size_t size; 1678{ 1679 register PTR ptr; 1680 if (old) 1681 ptr = (PTR) realloc (old, size); 1682 else 1683 ptr = (PTR) malloc (size); 1684 if (!ptr) 1685 fatal ("virtual memory exhausted"); 1686 return ptr; 1687} 1688 1689PTR 1690xmalloc (size) 1691 size_t size; 1692{ 1693 register PTR val = (PTR) malloc (size); 1694 1695 if (val == 0) 1696 fatal ("virtual memory exhausted"); 1697 return val; 1698} 1699 1700void 1701fatal VPROTO ((const char *format, ...)) 1702{ 1703#ifndef ANSI_PROTOTYPES 1704 const char *format; 1705#endif 1706 va_list ap; 1707 1708 VA_START (ap, format); 1709 1710#ifndef ANSI_PROTOTYPES 1711 format = va_arg (ap, const char *); 1712#endif 1713 1714 fprintf (stderr, "genrecog: "); 1715 vfprintf (stderr, format, ap); 1716 va_end (ap); 1717 fprintf (stderr, "\n"); 1718 fprintf (stderr, "after %d definitions\n", next_index); 1719 exit (FATAL_EXIT_CODE); 1720} 1721 1722/* More 'friendly' abort that prints the line and file. 1723 config.h can #define abort fancy_abort if you like that sort of thing. */ 1724 1725void 1726fancy_abort () 1727{ 1728 fatal ("Internal gcc abort."); 1729} 1730 1731int 1732main (argc, argv) 1733 int argc; 1734 char **argv; 1735{ 1736 rtx desc; 1737 struct decision_head recog_tree; 1738 struct decision_head split_tree; 1739 FILE *infile; 1740 register int c; 1741 1742 obstack_init (rtl_obstack); 1743 recog_tree.first = recog_tree.last = split_tree.first = split_tree.last = 0; 1744 1745 if (argc <= 1) 1746 fatal ("No input file name."); 1747 1748 infile = fopen (argv[1], "r"); 1749 if (infile == 0) 1750 { 1751 perror (argv[1]); 1752 exit (FATAL_EXIT_CODE); 1753 } 1754 1755 init_rtl (); 1756 next_insn_code = 0; 1757 next_index = 0; 1758 1759 printf ("/* Generated automatically by the program `genrecog'\n\ 1760from the machine description file `md'. */\n\n"); 1761 1762 printf ("#include \"config.h\"\n"); 1763 printf ("#include \"system.h\"\n"); 1764 printf ("#include \"rtl.h\"\n"); 1765 printf ("#include \"insn-config.h\"\n"); 1766 printf ("#include \"recog.h\"\n"); 1767 printf ("#include \"real.h\"\n"); 1768 printf ("#include \"output.h\"\n"); 1769 printf ("#include \"flags.h\"\n"); 1770 printf ("\n"); 1771 1772 /* Read the machine description. */ 1773 1774 while (1) 1775 { 1776 c = read_skip_spaces (infile); 1777 if (c == EOF) 1778 break; 1779 ungetc (c, infile); 1780 1781 desc = read_rtx (infile); 1782 if (GET_CODE (desc) == DEFINE_INSN) 1783 recog_tree = merge_trees (recog_tree, 1784 make_insn_sequence (desc, RECOG)); 1785 else if (GET_CODE (desc) == DEFINE_SPLIT) 1786 split_tree = merge_trees (split_tree, 1787 make_insn_sequence (desc, SPLIT)); 1788 if (GET_CODE (desc) == DEFINE_PEEPHOLE 1789 || GET_CODE (desc) == DEFINE_EXPAND) 1790 next_insn_code++; 1791 next_index++; 1792 } 1793 1794 printf ("\n\ 1795/* `recog' contains a decision tree\n\ 1796 that recognizes whether the rtx X0 is a valid instruction.\n\ 1797\n\ 1798 recog returns -1 if the rtx is not valid.\n\ 1799 If the rtx is valid, recog returns a nonnegative number\n\ 1800 which is the insn code number for the pattern that matched.\n"); 1801 printf (" This is the same as the order in the machine description of\n\ 1802 the entry that matched. This number can be used as an index into various\n\ 1803 insn_* tables, such as insn_templates, insn_outfun, and insn_n_operands\n\ 1804 (found in insn-output.c).\n\n"); 1805 printf (" The third argument to recog is an optional pointer to an int.\n\ 1806 If present, recog will accept a pattern if it matches except for\n\ 1807 missing CLOBBER expressions at the end. In that case, the value\n\ 1808 pointed to by the optional pointer will be set to the number of\n\ 1809 CLOBBERs that need to be added (it should be initialized to zero by\n\ 1810 the caller). If it is set nonzero, the caller should allocate a\n\ 1811 PARALLEL of the appropriate size, copy the initial entries, and call\n\ 1812 add_clobbers (found in insn-emit.c) to fill in the CLOBBERs."); 1813 1814 if (split_tree.first) 1815 printf ("\n\n The function split_insns returns 0 if the rtl could not\n\ 1816 be split or the split rtl in a SEQUENCE if it can be."); 1817 1818 printf ("*/\n\n"); 1819 1820 printf ("#define operands recog_operand\n\n"); 1821 1822 next_subroutine_number = 0; 1823 break_out_subroutines (recog_tree, RECOG, 1); 1824 write_subroutine (recog_tree.first, RECOG); 1825 1826 next_subroutine_number = 0; 1827 break_out_subroutines (split_tree, SPLIT, 1); 1828 write_subroutine (split_tree.first, SPLIT); 1829 1830 fflush (stdout); 1831 exit (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE); 1832 /* NOTREACHED */ 1833 return 0; 1834} 1835