118334Speter/* Generate code from machine description to recognize rtl as insns. 290075Sobrien Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1997, 1998, 3169689Skan 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 418334Speter 590075Sobrien This file is part of GCC. 618334Speter 790075Sobrien GCC is free software; you can redistribute it and/or modify it 890075Sobrien under the terms of the GNU General Public License as published by 990075Sobrien the Free Software Foundation; either version 2, or (at your option) 1090075Sobrien any later version. 1118334Speter 1290075Sobrien GCC is distributed in the hope that it will be useful, but WITHOUT 1390075Sobrien ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 1490075Sobrien or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 1590075Sobrien License for more details. 1618334Speter 1790075Sobrien You should have received a copy of the GNU General Public License 1890075Sobrien along with GCC; see the file COPYING. If not, write to the Free 19169689Skan Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan 02110-1301, USA. */ 2118334Speter 2218334Speter 2390075Sobrien/* This program is used to produce insn-recog.c, which contains a 2490075Sobrien function called `recog' plus its subroutines. These functions 2590075Sobrien contain a decision tree that recognizes whether an rtx, the 2690075Sobrien argument given to recog, is a valid instruction. 2718334Speter 2890075Sobrien recog returns -1 if the rtx is not valid. If the rtx is valid, 2990075Sobrien recog returns a nonnegative number which is the insn code number 3090075Sobrien for the pattern that matched. This is the same as the order in the 3190075Sobrien machine description of the entry that matched. This number can be 3290075Sobrien used as an index into various insn_* tables, such as insn_template, 3390075Sobrien insn_outfun, and insn_n_operands (found in insn-output.c). 3418334Speter 3590075Sobrien The third argument to recog is an optional pointer to an int. If 3690075Sobrien present, recog will accept a pattern if it matches except for 3718334Speter missing CLOBBER expressions at the end. In that case, the value 3818334Speter pointed to by the optional pointer will be set to the number of 3918334Speter CLOBBERs that need to be added (it should be initialized to zero by 4018334Speter the caller). If it is set nonzero, the caller should allocate a 4190075Sobrien PARALLEL of the appropriate size, copy the initial entries, and 4290075Sobrien call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs. 4318334Speter 4490075Sobrien This program also generates the function `split_insns', which 4590075Sobrien returns 0 if the rtl could not be split, or it returns the split 46117395Skan rtl as an INSN list. 4718334Speter 4890075Sobrien This program also generates the function `peephole2_insns', which 4990075Sobrien returns 0 if the rtl could not be matched. If there was a match, 50117395Skan the new rtl is returned in an INSN list, and LAST_INSN will point 5190075Sobrien to the last recognized insn in the old sequence. */ 5290075Sobrien 53132718Skan#include "bconfig.h" 5450397Sobrien#include "system.h" 55132718Skan#include "coretypes.h" 56132718Skan#include "tm.h" 5718334Speter#include "rtl.h" 5890075Sobrien#include "errors.h" 5990075Sobrien#include "gensupport.h" 6018334Speter 6152284Sobrien#define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \ 6252284Sobrien printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER)) 6352284Sobrien 6490075Sobrien/* A listhead of decision trees. The alternatives to a node are kept 65132718Skan in a doubly-linked list so we can easily add nodes to the proper 6690075Sobrien place when merging. */ 6718334Speter 6890075Sobrienstruct decision_head 6990075Sobrien{ 7090075Sobrien struct decision *first; 7190075Sobrien struct decision *last; 7290075Sobrien}; 7318334Speter 7490075Sobrien/* A single test. The two accept types aren't tests per-se, but 7590075Sobrien their equality (or lack thereof) does affect tree merging so 7690075Sobrien it is convenient to keep them here. */ 7718334Speter 7890075Sobrienstruct decision_test 7990075Sobrien{ 8090075Sobrien /* A linked list through the tests attached to a node. */ 8190075Sobrien struct decision_test *next; 8218334Speter 8390075Sobrien /* These types are roughly in the order in which we'd like to test them. */ 8490075Sobrien enum decision_type 8590075Sobrien { 86169689Skan DT_num_insns, 8790075Sobrien DT_mode, DT_code, DT_veclen, 8890075Sobrien DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide, DT_elt_zero_wide_safe, 89169689Skan DT_const_int, 9090075Sobrien DT_veclen_ge, DT_dup, DT_pred, DT_c_test, 9190075Sobrien DT_accept_op, DT_accept_insn 9290075Sobrien } type; 9318334Speter 9490075Sobrien union 9590075Sobrien { 96169689Skan int num_insns; /* Number if insn in a define_peephole2. */ 9790075Sobrien enum machine_mode mode; /* Machine mode of node. */ 9890075Sobrien RTX_CODE code; /* Code to test. */ 9990075Sobrien 10090075Sobrien struct 10190075Sobrien { 10290075Sobrien const char *name; /* Predicate to call. */ 103169689Skan const struct pred_data *data; 104169689Skan /* Optimization hints for this predicate. */ 10590075Sobrien enum machine_mode mode; /* Machine mode for node. */ 10690075Sobrien } pred; 10790075Sobrien 10890075Sobrien const char *c_test; /* Additional test to perform. */ 10990075Sobrien int veclen; /* Length of vector. */ 11090075Sobrien int dup; /* Number of operand to compare against. */ 11190075Sobrien HOST_WIDE_INT intval; /* Value for XINT for XWINT. */ 11290075Sobrien int opno; /* Operand number matched. */ 11390075Sobrien 11490075Sobrien struct { 11590075Sobrien int code_number; /* Insn number matched. */ 11690075Sobrien int lineno; /* Line number of the insn. */ 11790075Sobrien int num_clobbers_to_add; /* Number of CLOBBERs to be added. */ 11890075Sobrien } insn; 11990075Sobrien } u; 12090075Sobrien}; 12190075Sobrien 12290075Sobrien/* Data structure for decision tree for recognizing legitimate insns. */ 12390075Sobrien 12418334Speterstruct decision 12518334Speter{ 12690075Sobrien struct decision_head success; /* Nodes to test on success. */ 12790075Sobrien struct decision *next; /* Node to test on failure. */ 12890075Sobrien struct decision *prev; /* Node whose failure tests us. */ 12990075Sobrien struct decision *afterward; /* Node to test on success, 13090075Sobrien but failure of successor nodes. */ 13190075Sobrien 13290075Sobrien const char *position; /* String denoting position in pattern. */ 13390075Sobrien 13490075Sobrien struct decision_test *tests; /* The tests for this node. */ 13590075Sobrien 13618334Speter int number; /* Node number, used for labels */ 13718334Speter int subroutine_number; /* Number of subroutine this node starts */ 13890075Sobrien int need_label; /* Label needs to be output. */ 13918334Speter}; 14018334Speter 14190075Sobrien#define SUBROUTINE_THRESHOLD 100 14218334Speter 14318334Speterstatic int next_subroutine_number; 14418334Speter 14590075Sobrien/* We can write three types of subroutines: One for insn recognition, 14690075Sobrien one to split insns, and one for peephole-type optimizations. This 14790075Sobrien defines which type is being written. */ 14818334Speter 14990075Sobrienenum routine_type { 15090075Sobrien RECOG, SPLIT, PEEPHOLE2 15190075Sobrien}; 15218334Speter 15390075Sobrien#define IS_SPLIT(X) ((X) != RECOG) 15490075Sobrien 15518334Speter/* Next available node number for tree nodes. */ 15618334Speter 15718334Speterstatic int next_number; 15818334Speter 15918334Speter/* Next number to use as an insn_code. */ 16018334Speter 16118334Speterstatic int next_insn_code; 16218334Speter 16318334Speter/* Record the highest depth we ever have so we know how many variables to 16418334Speter allocate in each subroutine we make. */ 16518334Speter 16618334Speterstatic int max_depth; 16790075Sobrien 16890075Sobrien/* The line number of the start of the pattern currently being processed. */ 16990075Sobrienstatic int pattern_lineno; 17090075Sobrien 17190075Sobrien/* Count of errors. */ 17290075Sobrienstatic int error_count; 17318334Speter 174169689Skan/* Predicate handling. 17518334Speter 176169689Skan We construct from the machine description a table mapping each 177169689Skan predicate to a list of the rtl codes it can possibly match. The 178169689Skan function 'maybe_both_true' uses it to deduce that there are no 179169689Skan expressions that can be matches by certain pairs of tree nodes. 180169689Skan Also, if a predicate can match only one code, we can hardwire that 181169689Skan code into the node testing the predicate. 182169689Skan 183169689Skan Some predicates are flagged as special. validate_pattern will not 184169689Skan warn about modeless match_operand expressions if they have a 185169689Skan special predicate. Predicates that allow only constants are also 186169689Skan treated as special, for this purpose. 187169689Skan 188169689Skan validate_pattern will warn about predicates that allow non-lvalues 189169689Skan when they appear in destination operands. 190169689Skan 191169689Skan Calculating the set of rtx codes that can possibly be accepted by a 192169689Skan predicate expression EXP requires a three-state logic: any given 193169689Skan subexpression may definitively accept a code C (Y), definitively 194169689Skan reject a code C (N), or may have an indeterminate effect (I). N 195169689Skan and I is N; Y or I is Y; Y and I, N or I are both I. Here are full 196169689Skan truth tables. 197169689Skan 198169689Skan a b a&b a|b 199169689Skan Y Y Y Y 200169689Skan N Y N Y 201169689Skan N N N N 202169689Skan I Y I Y 203169689Skan I N N I 204169689Skan I I I I 205169689Skan 206169689Skan We represent Y with 1, N with 0, I with 2. If any code is left in 207169689Skan an I state by the complete expression, we must assume that that 208169689Skan code can be accepted. */ 209169689Skan 210169689Skan#define N 0 211169689Skan#define Y 1 212169689Skan#define I 2 213169689Skan 214169689Skan#define TRISTATE_AND(a,b) \ 215169689Skan ((a) == I ? ((b) == N ? N : I) : \ 216169689Skan (b) == I ? ((a) == N ? N : I) : \ 217169689Skan (a) && (b)) 218169689Skan 219169689Skan#define TRISTATE_OR(a,b) \ 220169689Skan ((a) == I ? ((b) == Y ? Y : I) : \ 221169689Skan (b) == I ? ((a) == Y ? Y : I) : \ 222169689Skan (a) || (b)) 223169689Skan 224169689Skan#define TRISTATE_NOT(a) \ 225169689Skan ((a) == I ? I : !(a)) 226169689Skan 227169689Skan/* 0 means no warning about that code yet, 1 means warned. */ 228169689Skanstatic char did_you_mean_codes[NUM_RTX_CODE]; 229169689Skan 230169689Skan/* Recursively calculate the set of rtx codes accepted by the 231169689Skan predicate expression EXP, writing the result to CODES. */ 232169689Skanstatic void 233169689Skancompute_predicate_codes (rtx exp, char codes[NUM_RTX_CODE]) 23418334Speter{ 235169689Skan char op0_codes[NUM_RTX_CODE]; 236169689Skan char op1_codes[NUM_RTX_CODE]; 237169689Skan char op2_codes[NUM_RTX_CODE]; 238169689Skan int i; 23918334Speter 240169689Skan switch (GET_CODE (exp)) 241169689Skan { 242169689Skan case AND: 243169689Skan compute_predicate_codes (XEXP (exp, 0), op0_codes); 244169689Skan compute_predicate_codes (XEXP (exp, 1), op1_codes); 245169689Skan for (i = 0; i < NUM_RTX_CODE; i++) 246169689Skan codes[i] = TRISTATE_AND (op0_codes[i], op1_codes[i]); 247169689Skan break; 24818334Speter 249169689Skan case IOR: 250169689Skan compute_predicate_codes (XEXP (exp, 0), op0_codes); 251169689Skan compute_predicate_codes (XEXP (exp, 1), op1_codes); 252169689Skan for (i = 0; i < NUM_RTX_CODE; i++) 253169689Skan codes[i] = TRISTATE_OR (op0_codes[i], op1_codes[i]); 254169689Skan break; 255169689Skan case NOT: 256169689Skan compute_predicate_codes (XEXP (exp, 0), op0_codes); 257169689Skan for (i = 0; i < NUM_RTX_CODE; i++) 258169689Skan codes[i] = TRISTATE_NOT (op0_codes[i]); 259169689Skan break; 26090075Sobrien 261169689Skan case IF_THEN_ELSE: 262169689Skan /* a ? b : c accepts the same codes as (a & b) | (!a & c). */ 263169689Skan compute_predicate_codes (XEXP (exp, 0), op0_codes); 264169689Skan compute_predicate_codes (XEXP (exp, 1), op1_codes); 265169689Skan compute_predicate_codes (XEXP (exp, 2), op2_codes); 266169689Skan for (i = 0; i < NUM_RTX_CODE; i++) 267169689Skan codes[i] = TRISTATE_OR (TRISTATE_AND (op0_codes[i], op1_codes[i]), 268169689Skan TRISTATE_AND (TRISTATE_NOT (op0_codes[i]), 269169689Skan op2_codes[i])); 270169689Skan break; 27190075Sobrien 272169689Skan case MATCH_CODE: 273169689Skan /* MATCH_CODE allows a specified list of codes. However, if it 274169689Skan does not apply to the top level of the expression, it does not 275169689Skan constrain the set of codes for the top level. */ 276169689Skan if (XSTR (exp, 1)[0] != '\0') 277169689Skan { 278169689Skan memset (codes, Y, NUM_RTX_CODE); 279169689Skan break; 280169689Skan } 281169689Skan 282169689Skan memset (codes, N, NUM_RTX_CODE); 283169689Skan { 284169689Skan const char *next_code = XSTR (exp, 0); 285169689Skan const char *code; 286169689Skan 287169689Skan if (*next_code == '\0') 288169689Skan { 289169689Skan message_with_line (pattern_lineno, "empty match_code expression"); 290169689Skan error_count++; 291169689Skan break; 292169689Skan } 293169689Skan 294169689Skan while ((code = scan_comma_elt (&next_code)) != 0) 295169689Skan { 296169689Skan size_t n = next_code - code; 297169689Skan int found_it = 0; 298169689Skan 299169689Skan for (i = 0; i < NUM_RTX_CODE; i++) 300169689Skan if (!strncmp (code, GET_RTX_NAME (i), n) 301169689Skan && GET_RTX_NAME (i)[n] == '\0') 302169689Skan { 303169689Skan codes[i] = Y; 304169689Skan found_it = 1; 305169689Skan break; 306169689Skan } 307169689Skan if (!found_it) 308169689Skan { 309169689Skan message_with_line (pattern_lineno, "match_code \"%.*s\" matches nothing", 310169689Skan (int) n, code); 311169689Skan error_count ++; 312169689Skan for (i = 0; i < NUM_RTX_CODE; i++) 313169689Skan if (!strncasecmp (code, GET_RTX_NAME (i), n) 314169689Skan && GET_RTX_NAME (i)[n] == '\0' 315169689Skan && !did_you_mean_codes[i]) 316169689Skan { 317169689Skan did_you_mean_codes[i] = 1; 318169689Skan message_with_line (pattern_lineno, "(did you mean \"%s\"?)", GET_RTX_NAME (i)); 319169689Skan } 320169689Skan } 321169689Skan 322169689Skan } 323169689Skan } 324169689Skan break; 325169689Skan 326169689Skan case MATCH_OPERAND: 327169689Skan /* MATCH_OPERAND disallows the set of codes that the named predicate 328169689Skan disallows, and is indeterminate for the codes that it does allow. */ 329169689Skan { 330169689Skan struct pred_data *p = lookup_predicate (XSTR (exp, 1)); 331169689Skan if (!p) 332169689Skan { 333169689Skan message_with_line (pattern_lineno, 334169689Skan "reference to unknown predicate '%s'", 335169689Skan XSTR (exp, 1)); 336169689Skan error_count++; 337169689Skan break; 338169689Skan } 339169689Skan for (i = 0; i < NUM_RTX_CODE; i++) 340169689Skan codes[i] = p->codes[i] ? I : N; 341169689Skan } 342169689Skan break; 343169689Skan 344169689Skan 345169689Skan case MATCH_TEST: 346169689Skan /* (match_test WHATEVER) is completely indeterminate. */ 347169689Skan memset (codes, I, NUM_RTX_CODE); 348169689Skan break; 349169689Skan 350169689Skan default: 351169689Skan message_with_line (pattern_lineno, 352169689Skan "'%s' cannot be used in a define_predicate expression", 353169689Skan GET_RTX_NAME (GET_CODE (exp))); 354169689Skan error_count++; 355169689Skan memset (codes, I, NUM_RTX_CODE); 356169689Skan break; 357169689Skan } 358169689Skan} 359169689Skan 360169689Skan#undef TRISTATE_OR 361169689Skan#undef TRISTATE_AND 362169689Skan#undef TRISTATE_NOT 363169689Skan 364169689Skan/* Process a define_predicate expression: compute the set of predicates 365169689Skan that can be matched, and record this as a known predicate. */ 366169689Skanstatic void 367169689Skanprocess_define_predicate (rtx desc) 368169689Skan{ 369169689Skan struct pred_data *pred = xcalloc (sizeof (struct pred_data), 1); 370169689Skan char codes[NUM_RTX_CODE]; 371169689Skan bool seen_one = false; 372169689Skan int i; 373169689Skan 374169689Skan pred->name = XSTR (desc, 0); 375169689Skan if (GET_CODE (desc) == DEFINE_SPECIAL_PREDICATE) 376169689Skan pred->special = 1; 377169689Skan 378169689Skan compute_predicate_codes (XEXP (desc, 1), codes); 379169689Skan 380169689Skan for (i = 0; i < NUM_RTX_CODE; i++) 381169689Skan if (codes[i] != N) 382169689Skan { 383169689Skan pred->codes[i] = true; 384169689Skan if (GET_RTX_CLASS (i) != RTX_CONST_OBJ) 385169689Skan pred->allows_non_const = true; 386169689Skan if (i != REG 387169689Skan && i != SUBREG 388169689Skan && i != MEM 389169689Skan && i != CONCAT 390169689Skan && i != PARALLEL 391169689Skan && i != STRICT_LOW_PART) 392169689Skan pred->allows_non_lvalue = true; 393169689Skan 394169689Skan if (seen_one) 395169689Skan pred->singleton = UNKNOWN; 396169689Skan else 397169689Skan { 398169689Skan pred->singleton = i; 399169689Skan seen_one = true; 400169689Skan } 401169689Skan } 402169689Skan add_predicate (pred); 403169689Skan} 404169689Skan#undef I 405169689Skan#undef N 406169689Skan#undef Y 407169689Skan 408169689Skan 40990075Sobrienstatic struct decision *new_decision 410132718Skan (const char *, struct decision_head *); 41190075Sobrienstatic struct decision_test *new_decision_test 412132718Skan (enum decision_type, struct decision_test ***); 41390075Sobrienstatic rtx find_operand 414132718Skan (rtx, int, rtx); 41590075Sobrienstatic rtx find_matching_operand 416132718Skan (rtx, int); 41790075Sobrienstatic void validate_pattern 418132718Skan (rtx, rtx, rtx, int); 41990075Sobrienstatic struct decision *add_to_sequence 420132718Skan (rtx, struct decision_head *, const char *, enum routine_type, int); 42190075Sobrien 42290075Sobrienstatic int maybe_both_true_2 423132718Skan (struct decision_test *, struct decision_test *); 42490075Sobrienstatic int maybe_both_true_1 425132718Skan (struct decision_test *, struct decision_test *); 42690075Sobrienstatic int maybe_both_true 427132718Skan (struct decision *, struct decision *, int); 42890075Sobrien 42990075Sobrienstatic int nodes_identical_1 430132718Skan (struct decision_test *, struct decision_test *); 43190075Sobrienstatic int nodes_identical 432132718Skan (struct decision *, struct decision *); 43390075Sobrienstatic void merge_accept_insn 434132718Skan (struct decision *, struct decision *); 43590075Sobrienstatic void merge_trees 436132718Skan (struct decision_head *, struct decision_head *); 43790075Sobrien 43890075Sobrienstatic void factor_tests 439132718Skan (struct decision_head *); 44090075Sobrienstatic void simplify_tests 441132718Skan (struct decision_head *); 44290075Sobrienstatic int break_out_subroutines 443132718Skan (struct decision_head *, int); 44490075Sobrienstatic void find_afterward 445132718Skan (struct decision_head *, struct decision *); 44690075Sobrien 44790075Sobrienstatic void change_state 448169689Skan (const char *, const char *, const char *); 44990075Sobrienstatic void print_code 450132718Skan (enum rtx_code); 45190075Sobrienstatic void write_afterward 452132718Skan (struct decision *, struct decision *, const char *); 45390075Sobrienstatic struct decision *write_switch 454132718Skan (struct decision *, int); 45590075Sobrienstatic void write_cond 456132718Skan (struct decision_test *, int, enum routine_type); 45790075Sobrienstatic void write_action 458132718Skan (struct decision *, struct decision_test *, int, int, 459132718Skan struct decision *, enum routine_type); 46090075Sobrienstatic int is_unconditional 461132718Skan (struct decision_test *, enum routine_type); 46290075Sobrienstatic int write_node 463132718Skan (struct decision *, int, enum routine_type); 46490075Sobrienstatic void write_tree_1 465132718Skan (struct decision_head *, int, enum routine_type); 46690075Sobrienstatic void write_tree 467132718Skan (struct decision_head *, const char *, enum routine_type, int); 46890075Sobrienstatic void write_subroutine 469132718Skan (struct decision_head *, enum routine_type); 47090075Sobrienstatic void write_subroutines 471132718Skan (struct decision_head *, enum routine_type); 47290075Sobrienstatic void write_header 473132718Skan (void); 47490075Sobrien 47590075Sobrienstatic struct decision_head make_insn_sequence 476132718Skan (rtx, enum routine_type); 47790075Sobrienstatic void process_tree 478132718Skan (struct decision_head *, enum routine_type); 47990075Sobrien 48090075Sobrienstatic void debug_decision_0 481132718Skan (struct decision *, int, int); 48290075Sobrienstatic void debug_decision_1 483132718Skan (struct decision *, int); 48490075Sobrienstatic void debug_decision_2 485132718Skan (struct decision_test *); 48690075Sobrienextern void debug_decision 487132718Skan (struct decision *); 48890075Sobrienextern void debug_decision_list 489132718Skan (struct decision *); 49018334Speter 49190075Sobrien/* Create a new node in sequence after LAST. */ 49218334Speter 49390075Sobrienstatic struct decision * 494132718Skannew_decision (const char *position, struct decision_head *last) 49590075Sobrien{ 496132718Skan struct decision *new = xcalloc (1, sizeof (struct decision)); 49718334Speter 49890075Sobrien new->success = *last; 49990075Sobrien new->position = xstrdup (position); 50090075Sobrien new->number = next_number++; 50190075Sobrien 50290075Sobrien last->first = last->last = new; 50390075Sobrien return new; 50490075Sobrien} 50590075Sobrien 50690075Sobrien/* Create a new test and link it in at PLACE. */ 50790075Sobrien 50890075Sobrienstatic struct decision_test * 509132718Skannew_decision_test (enum decision_type type, struct decision_test ***pplace) 51018334Speter{ 51190075Sobrien struct decision_test **place = *pplace; 51290075Sobrien struct decision_test *test; 51318334Speter 514169689Skan test = XNEW (struct decision_test); 51590075Sobrien test->next = *place; 51690075Sobrien test->type = type; 51790075Sobrien *place = test; 51852284Sobrien 51990075Sobrien place = &test->next; 52090075Sobrien *pplace = place; 52152284Sobrien 52290075Sobrien return test; 52390075Sobrien} 52452284Sobrien 525132718Skan/* Search for and return operand N, stop when reaching node STOP. */ 52690075Sobrien 52790075Sobrienstatic rtx 528132718Skanfind_operand (rtx pattern, int n, rtx stop) 52990075Sobrien{ 53090075Sobrien const char *fmt; 53190075Sobrien RTX_CODE code; 53290075Sobrien int i, j, len; 53390075Sobrien rtx r; 53490075Sobrien 535132718Skan if (pattern == stop) 536132718Skan return stop; 537132718Skan 53890075Sobrien code = GET_CODE (pattern); 53990075Sobrien if ((code == MATCH_SCRATCH 54090075Sobrien || code == MATCH_OPERAND 54190075Sobrien || code == MATCH_OPERATOR 54290075Sobrien || code == MATCH_PARALLEL) 54390075Sobrien && XINT (pattern, 0) == n) 54490075Sobrien return pattern; 54590075Sobrien 54690075Sobrien fmt = GET_RTX_FORMAT (code); 54790075Sobrien len = GET_RTX_LENGTH (code); 54890075Sobrien for (i = 0; i < len; i++) 54918334Speter { 55090075Sobrien switch (fmt[i]) 55190075Sobrien { 55290075Sobrien case 'e': case 'u': 553132718Skan if ((r = find_operand (XEXP (pattern, i), n, stop)) != NULL_RTX) 55490075Sobrien return r; 55590075Sobrien break; 55690075Sobrien 55790075Sobrien case 'V': 55890075Sobrien if (! XVEC (pattern, i)) 55990075Sobrien break; 560132718Skan /* Fall through. */ 56190075Sobrien 56290075Sobrien case 'E': 56390075Sobrien for (j = 0; j < XVECLEN (pattern, i); j++) 564132718Skan if ((r = find_operand (XVECEXP (pattern, i, j), n, stop)) 565132718Skan != NULL_RTX) 56690075Sobrien return r; 56790075Sobrien break; 56890075Sobrien 56990075Sobrien case 'i': case 'w': case '0': case 's': 57090075Sobrien break; 57190075Sobrien 57290075Sobrien default: 573169689Skan gcc_unreachable (); 57490075Sobrien } 57518334Speter } 57618334Speter 57790075Sobrien return NULL; 57890075Sobrien} 57918334Speter 58090075Sobrien/* Search for and return operand M, such that it has a matching 58190075Sobrien constraint for operand N. */ 58218334Speter 58390075Sobrienstatic rtx 584132718Skanfind_matching_operand (rtx pattern, int n) 58590075Sobrien{ 58690075Sobrien const char *fmt; 58790075Sobrien RTX_CODE code; 58890075Sobrien int i, j, len; 58990075Sobrien rtx r; 59018334Speter 59190075Sobrien code = GET_CODE (pattern); 59290075Sobrien if (code == MATCH_OPERAND 59390075Sobrien && (XSTR (pattern, 2)[0] == '0' + n 59490075Sobrien || (XSTR (pattern, 2)[0] == '%' 59590075Sobrien && XSTR (pattern, 2)[1] == '0' + n))) 59690075Sobrien return pattern; 59790075Sobrien 59890075Sobrien fmt = GET_RTX_FORMAT (code); 59990075Sobrien len = GET_RTX_LENGTH (code); 60090075Sobrien for (i = 0; i < len; i++) 60118334Speter { 60290075Sobrien switch (fmt[i]) 60390075Sobrien { 60490075Sobrien case 'e': case 'u': 60590075Sobrien if ((r = find_matching_operand (XEXP (pattern, i), n))) 60690075Sobrien return r; 60790075Sobrien break; 60818334Speter 60990075Sobrien case 'V': 61090075Sobrien if (! XVEC (pattern, i)) 61190075Sobrien break; 612132718Skan /* Fall through. */ 61390075Sobrien 61490075Sobrien case 'E': 61590075Sobrien for (j = 0; j < XVECLEN (pattern, i); j++) 61690075Sobrien if ((r = find_matching_operand (XVECEXP (pattern, i, j), n))) 61790075Sobrien return r; 61818334Speter break; 61918334Speter 62090075Sobrien case 'i': case 'w': case '0': case 's': 62190075Sobrien break; 62218334Speter 62390075Sobrien default: 624169689Skan gcc_unreachable (); 62590075Sobrien } 62690075Sobrien } 62718334Speter 62890075Sobrien return NULL; 62990075Sobrien} 63018334Speter 63118334Speter 63290075Sobrien/* Check for various errors in patterns. SET is nonnull for a destination, 63390075Sobrien and is the complete set pattern. SET_CODE is '=' for normal sets, and 63490075Sobrien '+' within a context that requires in-out constraints. */ 63518334Speter 63690075Sobrienstatic void 637132718Skanvalidate_pattern (rtx pattern, rtx insn, rtx set, int set_code) 63890075Sobrien{ 63990075Sobrien const char *fmt; 64090075Sobrien RTX_CODE code; 64190075Sobrien size_t i, len; 64290075Sobrien int j; 64390075Sobrien 64490075Sobrien code = GET_CODE (pattern); 64590075Sobrien switch (code) 64690075Sobrien { 64790075Sobrien case MATCH_SCRATCH: 64890075Sobrien return; 649132718Skan case MATCH_DUP: 650132718Skan case MATCH_OP_DUP: 651132718Skan case MATCH_PAR_DUP: 652132718Skan if (find_operand (insn, XINT (pattern, 0), pattern) == pattern) 653132718Skan { 654132718Skan message_with_line (pattern_lineno, 655132718Skan "operand %i duplicated before defined", 656132718Skan XINT (pattern, 0)); 657132718Skan error_count++; 658132718Skan } 659132718Skan break; 66090075Sobrien case MATCH_OPERAND: 66190075Sobrien case MATCH_OPERATOR: 66290075Sobrien { 66390075Sobrien const char *pred_name = XSTR (pattern, 1); 664169689Skan const struct pred_data *pred; 66590075Sobrien const char *c_test; 66690075Sobrien 66790075Sobrien if (GET_CODE (insn) == DEFINE_INSN) 66890075Sobrien c_test = XSTR (insn, 2); 66990075Sobrien else 67090075Sobrien c_test = XSTR (insn, 1); 67190075Sobrien 67290075Sobrien if (pred_name[0] != 0) 67390075Sobrien { 674169689Skan pred = lookup_predicate (pred_name); 675169689Skan if (!pred) 676169689Skan message_with_line (pattern_lineno, 677169689Skan "warning: unknown predicate '%s'", 678169689Skan pred_name); 67990075Sobrien } 680169689Skan else 681169689Skan pred = 0; 68290075Sobrien 68390075Sobrien if (code == MATCH_OPERAND) 68490075Sobrien { 68590075Sobrien const char constraints0 = XSTR (pattern, 2)[0]; 68690075Sobrien 687132718Skan /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we 68890075Sobrien don't use the MATCH_OPERAND constraint, only the predicate. 68990075Sobrien This is confusing to folks doing new ports, so help them 69090075Sobrien not make the mistake. */ 69190075Sobrien if (GET_CODE (insn) == DEFINE_EXPAND 69290075Sobrien || GET_CODE (insn) == DEFINE_SPLIT 69390075Sobrien || GET_CODE (insn) == DEFINE_PEEPHOLE2) 69490075Sobrien { 69590075Sobrien if (constraints0) 69690075Sobrien message_with_line (pattern_lineno, 69790075Sobrien "warning: constraints not supported in %s", 69890075Sobrien rtx_name[GET_CODE (insn)]); 69990075Sobrien } 700132718Skan 70190075Sobrien /* A MATCH_OPERAND that is a SET should have an output reload. */ 70290075Sobrien else if (set && constraints0) 70390075Sobrien { 70490075Sobrien if (set_code == '+') 70590075Sobrien { 70690075Sobrien if (constraints0 == '+') 70790075Sobrien ; 70890075Sobrien /* If we've only got an output reload for this operand, 70990075Sobrien we'd better have a matching input operand. */ 71090075Sobrien else if (constraints0 == '=' 71190075Sobrien && find_matching_operand (insn, XINT (pattern, 0))) 71290075Sobrien ; 71390075Sobrien else 71490075Sobrien { 71590075Sobrien message_with_line (pattern_lineno, 71690075Sobrien "operand %d missing in-out reload", 71790075Sobrien XINT (pattern, 0)); 71890075Sobrien error_count++; 71990075Sobrien } 72090075Sobrien } 72190075Sobrien else if (constraints0 != '=' && constraints0 != '+') 72290075Sobrien { 72390075Sobrien message_with_line (pattern_lineno, 724132718Skan "operand %d missing output reload", 72590075Sobrien XINT (pattern, 0)); 72690075Sobrien error_count++; 72790075Sobrien } 72890075Sobrien } 72990075Sobrien } 73090075Sobrien 73190075Sobrien /* Allowing non-lvalues in destinations -- particularly CONST_INT -- 73290075Sobrien while not likely to occur at runtime, results in less efficient 73390075Sobrien code from insn-recog.c. */ 734169689Skan if (set && pred && pred->allows_non_lvalue) 735169689Skan message_with_line (pattern_lineno, 736169689Skan "warning: destination operand %d " 737169689Skan "allows non-lvalue", 738169689Skan XINT (pattern, 0)); 73990075Sobrien 740169689Skan /* A modeless MATCH_OPERAND can be handy when we can check for 741169689Skan multiple modes in the c_test. In most other cases, it is a 742169689Skan mistake. Only DEFINE_INSN is eligible, since SPLIT and 743169689Skan PEEP2 can FAIL within the output pattern. Exclude special 744169689Skan predicates, which check the mode themselves. Also exclude 745169689Skan predicates that allow only constants. Exclude the SET_DEST 746169689Skan of a call instruction, as that is a common idiom. */ 74790075Sobrien 74890075Sobrien if (GET_MODE (pattern) == VOIDmode 74990075Sobrien && code == MATCH_OPERAND 75090075Sobrien && GET_CODE (insn) == DEFINE_INSN 751169689Skan && pred 752169689Skan && !pred->special 753169689Skan && pred->allows_non_const 75490075Sobrien && strstr (c_test, "operands") == NULL 75590075Sobrien && ! (set 75690075Sobrien && GET_CODE (set) == SET 75790075Sobrien && GET_CODE (SET_SRC (set)) == CALL)) 758169689Skan message_with_line (pattern_lineno, 759169689Skan "warning: operand %d missing mode?", 760169689Skan XINT (pattern, 0)); 76190075Sobrien return; 76290075Sobrien } 76390075Sobrien 76490075Sobrien case SET: 76590075Sobrien { 76690075Sobrien enum machine_mode dmode, smode; 76790075Sobrien rtx dest, src; 76890075Sobrien 76990075Sobrien dest = SET_DEST (pattern); 77090075Sobrien src = SET_SRC (pattern); 77190075Sobrien 77290075Sobrien /* STRICT_LOW_PART is a wrapper. Its argument is the real 77390075Sobrien destination, and it's mode should match the source. */ 77490075Sobrien if (GET_CODE (dest) == STRICT_LOW_PART) 77590075Sobrien dest = XEXP (dest, 0); 77690075Sobrien 777132718Skan /* Find the referent for a DUP. */ 77890075Sobrien 77990075Sobrien if (GET_CODE (dest) == MATCH_DUP 78090075Sobrien || GET_CODE (dest) == MATCH_OP_DUP 78190075Sobrien || GET_CODE (dest) == MATCH_PAR_DUP) 782132718Skan dest = find_operand (insn, XINT (dest, 0), NULL); 78390075Sobrien 78490075Sobrien if (GET_CODE (src) == MATCH_DUP 78590075Sobrien || GET_CODE (src) == MATCH_OP_DUP 78690075Sobrien || GET_CODE (src) == MATCH_PAR_DUP) 787132718Skan src = find_operand (insn, XINT (src, 0), NULL); 78890075Sobrien 78990075Sobrien dmode = GET_MODE (dest); 79090075Sobrien smode = GET_MODE (src); 79190075Sobrien 79290075Sobrien /* The mode of an ADDRESS_OPERAND is the mode of the memory 79390075Sobrien reference, not the mode of the address. */ 79490075Sobrien if (GET_CODE (src) == MATCH_OPERAND 79590075Sobrien && ! strcmp (XSTR (src, 1), "address_operand")) 79690075Sobrien ; 79790075Sobrien 79890075Sobrien /* The operands of a SET must have the same mode unless one 79990075Sobrien is VOIDmode. */ 80090075Sobrien else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode) 80190075Sobrien { 80290075Sobrien message_with_line (pattern_lineno, 80390075Sobrien "mode mismatch in set: %smode vs %smode", 80490075Sobrien GET_MODE_NAME (dmode), GET_MODE_NAME (smode)); 80590075Sobrien error_count++; 80690075Sobrien } 80790075Sobrien 80890075Sobrien /* If only one of the operands is VOIDmode, and PC or CC0 is 80990075Sobrien not involved, it's probably a mistake. */ 81090075Sobrien else if (dmode != smode 81190075Sobrien && GET_CODE (dest) != PC 81290075Sobrien && GET_CODE (dest) != CC0 81390075Sobrien && GET_CODE (src) != PC 81490075Sobrien && GET_CODE (src) != CC0 81590075Sobrien && GET_CODE (src) != CONST_INT) 81690075Sobrien { 81790075Sobrien const char *which; 81890075Sobrien which = (dmode == VOIDmode ? "destination" : "source"); 81990075Sobrien message_with_line (pattern_lineno, 82090075Sobrien "warning: %s missing a mode?", which); 82190075Sobrien } 82290075Sobrien 82390075Sobrien if (dest != SET_DEST (pattern)) 82490075Sobrien validate_pattern (dest, insn, pattern, '='); 82590075Sobrien validate_pattern (SET_DEST (pattern), insn, pattern, '='); 82690075Sobrien validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0); 82790075Sobrien return; 82890075Sobrien } 82990075Sobrien 83090075Sobrien case CLOBBER: 83190075Sobrien validate_pattern (SET_DEST (pattern), insn, pattern, '='); 83290075Sobrien return; 83390075Sobrien 83490075Sobrien case ZERO_EXTRACT: 83590075Sobrien validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0); 83690075Sobrien validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0); 83790075Sobrien validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0); 83890075Sobrien return; 83990075Sobrien 84090075Sobrien case STRICT_LOW_PART: 84190075Sobrien validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0); 84290075Sobrien return; 84390075Sobrien 84490075Sobrien case LABEL_REF: 84590075Sobrien if (GET_MODE (XEXP (pattern, 0)) != VOIDmode) 84690075Sobrien { 84790075Sobrien message_with_line (pattern_lineno, 84890075Sobrien "operand to label_ref %smode not VOIDmode", 84990075Sobrien GET_MODE_NAME (GET_MODE (XEXP (pattern, 0)))); 85090075Sobrien error_count++; 85118334Speter } 85290075Sobrien break; 85390075Sobrien 85490075Sobrien default: 85590075Sobrien break; 85618334Speter } 85718334Speter 85890075Sobrien fmt = GET_RTX_FORMAT (code); 85990075Sobrien len = GET_RTX_LENGTH (code); 86090075Sobrien for (i = 0; i < len; i++) 86190075Sobrien { 86290075Sobrien switch (fmt[i]) 86390075Sobrien { 86490075Sobrien case 'e': case 'u': 86590075Sobrien validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0); 86690075Sobrien break; 86718334Speter 86890075Sobrien case 'E': 86990075Sobrien for (j = 0; j < XVECLEN (pattern, i); j++) 87090075Sobrien validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX, 0); 87190075Sobrien break; 87218334Speter 87390075Sobrien case 'i': case 'w': case '0': case 's': 87490075Sobrien break; 87590075Sobrien 87690075Sobrien default: 877169689Skan gcc_unreachable (); 87890075Sobrien } 87990075Sobrien } 88018334Speter} 88190075Sobrien 88218334Speter/* Create a chain of nodes to verify that an rtl expression matches 88318334Speter PATTERN. 88418334Speter 88518334Speter LAST is a pointer to the listhead in the previous node in the chain (or 88618334Speter in the calling function, for the first node). 88718334Speter 88818334Speter POSITION is the string representing the current position in the insn. 88918334Speter 89090075Sobrien INSN_TYPE is the type of insn for which we are emitting code. 89190075Sobrien 89218334Speter A pointer to the final node in the chain is returned. */ 89318334Speter 89418334Speterstatic struct decision * 895132718Skanadd_to_sequence (rtx pattern, struct decision_head *last, const char *position, 896132718Skan enum routine_type insn_type, int top) 89718334Speter{ 89890075Sobrien RTX_CODE code; 89990075Sobrien struct decision *this, *sub; 90090075Sobrien struct decision_test *test; 90190075Sobrien struct decision_test **place; 90290075Sobrien char *subpos; 90390075Sobrien size_t i; 90490075Sobrien const char *fmt; 90518334Speter int depth = strlen (position); 90618334Speter int len; 90790075Sobrien enum machine_mode mode; 90818334Speter 90918334Speter if (depth > max_depth) 91018334Speter max_depth = depth; 91118334Speter 912132718Skan subpos = xmalloc (depth + 2); 91390075Sobrien strcpy (subpos, position); 91490075Sobrien subpos[depth + 1] = 0; 91518334Speter 91690075Sobrien sub = this = new_decision (position, last); 91790075Sobrien place = &this->tests; 91818334Speter 91990075Sobrien restart: 92090075Sobrien mode = GET_MODE (pattern); 92190075Sobrien code = GET_CODE (pattern); 92218334Speter 92390075Sobrien switch (code) 92490075Sobrien { 92590075Sobrien case PARALLEL: 92690075Sobrien /* Toplevel peephole pattern. */ 92790075Sobrien if (insn_type == PEEPHOLE2 && top) 92890075Sobrien { 929169689Skan int num_insns; 93018334Speter 931169689Skan /* Check we have sufficient insns. This avoids complications 932169689Skan because we then know peep2_next_insn never fails. */ 933169689Skan num_insns = XVECLEN (pattern, 0); 934169689Skan if (num_insns > 1) 935169689Skan { 936169689Skan test = new_decision_test (DT_num_insns, &place); 937169689Skan test->u.num_insns = num_insns; 938169689Skan last = &sub->success; 939169689Skan } 940169689Skan else 941169689Skan { 942169689Skan /* We don't need the node we just created -- unlink it. */ 943169689Skan last->first = last->last = NULL; 944169689Skan } 945169689Skan 94690075Sobrien for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++) 94790075Sobrien { 94890075Sobrien /* Which insn we're looking at is represented by A-Z. We don't 94990075Sobrien ever use 'A', however; it is always implied. */ 95018334Speter 95190075Sobrien subpos[depth] = (i > 0 ? 'A' + i : 0); 95290075Sobrien sub = add_to_sequence (XVECEXP (pattern, 0, i), 95390075Sobrien last, subpos, insn_type, 0); 95490075Sobrien last = &sub->success; 95590075Sobrien } 95690075Sobrien goto ret; 95790075Sobrien } 95818334Speter 95990075Sobrien /* Else nothing special. */ 96090075Sobrien break; 96190075Sobrien 96290075Sobrien case MATCH_PARALLEL: 96390075Sobrien /* The explicit patterns within a match_parallel enforce a minimum 96490075Sobrien length on the vector. The match_parallel predicate may allow 96590075Sobrien for more elements. We do need to check for this minimum here 96690075Sobrien or the code generated to match the internals may reference data 96790075Sobrien beyond the end of the vector. */ 96890075Sobrien test = new_decision_test (DT_veclen_ge, &place); 96990075Sobrien test->u.veclen = XVECLEN (pattern, 2); 970132718Skan /* Fall through. */ 97190075Sobrien 97218334Speter case MATCH_OPERAND: 97318334Speter case MATCH_SCRATCH: 97418334Speter case MATCH_OPERATOR: 97590075Sobrien { 976169689Skan RTX_CODE was_code = code; 97790075Sobrien const char *pred_name; 978169689Skan bool allows_const_int = true; 97918334Speter 98090075Sobrien if (code == MATCH_SCRATCH) 98190075Sobrien { 98290075Sobrien pred_name = "scratch_operand"; 98390075Sobrien code = UNKNOWN; 98490075Sobrien } 98590075Sobrien else 98690075Sobrien { 98790075Sobrien pred_name = XSTR (pattern, 1); 98890075Sobrien if (code == MATCH_PARALLEL) 98990075Sobrien code = PARALLEL; 99090075Sobrien else 99190075Sobrien code = UNKNOWN; 99290075Sobrien } 99318334Speter 99490075Sobrien if (pred_name[0] != 0) 99590075Sobrien { 996169689Skan const struct pred_data *pred; 997169689Skan 99890075Sobrien test = new_decision_test (DT_pred, &place); 99990075Sobrien test->u.pred.name = pred_name; 100090075Sobrien test->u.pred.mode = mode; 100118334Speter 1002169689Skan /* See if we know about this predicate. 1003169689Skan If we do, remember it for use below. 100418334Speter 1005169689Skan We can optimize the generated code a little if either 1006169689Skan (a) the predicate only accepts one code, or (b) the 1007169689Skan predicate does not allow CONST_INT, in which case it 1008169689Skan can match only if the modes match. */ 1009169689Skan pred = lookup_predicate (pred_name); 1010169689Skan if (pred) 101118334Speter { 1012169689Skan test->u.pred.data = pred; 1013169689Skan allows_const_int = pred->codes[CONST_INT]; 1014169689Skan if (was_code == MATCH_PARALLEL 1015169689Skan && pred->singleton != PARALLEL) 1016169689Skan message_with_line (pattern_lineno, 1017169689Skan "predicate '%s' used in match_parallel " 1018169689Skan "does not allow only PARALLEL", pred->name); 1019169689Skan else 1020169689Skan code = pred->singleton; 102190075Sobrien } 102290075Sobrien else 1023169689Skan message_with_line (pattern_lineno, 1024169689Skan "warning: unknown predicate '%s' in '%s' expression", 1025169689Skan pred_name, GET_RTX_NAME (was_code)); 102690075Sobrien } 102718334Speter 102890075Sobrien /* Can't enforce a mode if we allow const_int. */ 102990075Sobrien if (allows_const_int) 103090075Sobrien mode = VOIDmode; 103118334Speter 1032169689Skan /* Accept the operand, i.e. record it in `operands'. */ 103390075Sobrien test = new_decision_test (DT_accept_op, &place); 103490075Sobrien test->u.opno = XINT (pattern, 0); 103590075Sobrien 103690075Sobrien if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL) 103790075Sobrien { 103890075Sobrien char base = (was_code == MATCH_OPERATOR ? '0' : 'a'); 103990075Sobrien for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++) 104090075Sobrien { 104190075Sobrien subpos[depth] = i + base; 104290075Sobrien sub = add_to_sequence (XVECEXP (pattern, 2, i), 104390075Sobrien &sub->success, subpos, insn_type, 0); 104418334Speter } 104590075Sobrien } 104690075Sobrien goto fini; 104790075Sobrien } 104818334Speter 104990075Sobrien case MATCH_OP_DUP: 105090075Sobrien code = UNKNOWN; 105118334Speter 105290075Sobrien test = new_decision_test (DT_dup, &place); 105390075Sobrien test->u.dup = XINT (pattern, 0); 105418334Speter 105590075Sobrien test = new_decision_test (DT_accept_op, &place); 105690075Sobrien test->u.opno = XINT (pattern, 0); 105718334Speter 105852284Sobrien for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++) 105918334Speter { 106090075Sobrien subpos[depth] = i + '0'; 106190075Sobrien sub = add_to_sequence (XVECEXP (pattern, 1, i), 106290075Sobrien &sub->success, subpos, insn_type, 0); 106318334Speter } 106490075Sobrien goto fini; 106518334Speter 106618334Speter case MATCH_DUP: 106718334Speter case MATCH_PAR_DUP: 106890075Sobrien code = UNKNOWN; 106918334Speter 107090075Sobrien test = new_decision_test (DT_dup, &place); 107190075Sobrien test->u.dup = XINT (pattern, 0); 107290075Sobrien goto fini; 107390075Sobrien 107418334Speter case ADDRESS: 107518334Speter pattern = XEXP (pattern, 0); 107618334Speter goto restart; 107718334Speter 107890075Sobrien default: 107990075Sobrien break; 108090075Sobrien } 108190075Sobrien 108290075Sobrien fmt = GET_RTX_FORMAT (code); 108390075Sobrien len = GET_RTX_LENGTH (code); 108490075Sobrien 108590075Sobrien /* Do tests against the current node first. */ 108690075Sobrien for (i = 0; i < (size_t) len; i++) 108790075Sobrien { 108890075Sobrien if (fmt[i] == 'i') 108952284Sobrien { 1090169689Skan gcc_assert (i < 2); 1091169689Skan 1092169689Skan if (!i) 109390075Sobrien { 109490075Sobrien test = new_decision_test (DT_elt_zero_int, &place); 109590075Sobrien test->u.intval = XINT (pattern, i); 109690075Sobrien } 1097169689Skan else 109890075Sobrien { 109990075Sobrien test = new_decision_test (DT_elt_one_int, &place); 110090075Sobrien test->u.intval = XINT (pattern, i); 110190075Sobrien } 110252284Sobrien } 110390075Sobrien else if (fmt[i] == 'w') 110490075Sobrien { 110590075Sobrien /* If this value actually fits in an int, we can use a switch 110690075Sobrien statement here, so indicate that. */ 110790075Sobrien enum decision_type type 110890075Sobrien = ((int) XWINT (pattern, i) == XWINT (pattern, i)) 110990075Sobrien ? DT_elt_zero_wide_safe : DT_elt_zero_wide; 111018334Speter 1111169689Skan gcc_assert (!i); 111218334Speter 111390075Sobrien test = new_decision_test (type, &place); 111490075Sobrien test->u.intval = XWINT (pattern, i); 111590075Sobrien } 111690075Sobrien else if (fmt[i] == 'E') 111790075Sobrien { 1118169689Skan gcc_assert (!i); 111918334Speter 112090075Sobrien test = new_decision_test (DT_veclen, &place); 112190075Sobrien test->u.veclen = XVECLEN (pattern, i); 112290075Sobrien } 112390075Sobrien } 112418334Speter 112590075Sobrien /* Now test our sub-patterns. */ 112690075Sobrien for (i = 0; i < (size_t) len; i++) 112790075Sobrien { 112890075Sobrien switch (fmt[i]) 112990075Sobrien { 113090075Sobrien case 'e': case 'u': 113190075Sobrien subpos[depth] = '0' + i; 113290075Sobrien sub = add_to_sequence (XEXP (pattern, i), &sub->success, 113390075Sobrien subpos, insn_type, 0); 113490075Sobrien break; 113518334Speter 113690075Sobrien case 'E': 113790075Sobrien { 113890075Sobrien int j; 113990075Sobrien for (j = 0; j < XVECLEN (pattern, i); j++) 114090075Sobrien { 114190075Sobrien subpos[depth] = 'a' + j; 114290075Sobrien sub = add_to_sequence (XVECEXP (pattern, i, j), 114390075Sobrien &sub->success, subpos, insn_type, 0); 114490075Sobrien } 114590075Sobrien break; 114690075Sobrien } 114718334Speter 114890075Sobrien case 'i': case 'w': 114990075Sobrien /* Handled above. */ 115090075Sobrien break; 115190075Sobrien case '0': 115290075Sobrien break; 115390075Sobrien 115490075Sobrien default: 1155169689Skan gcc_unreachable (); 115690075Sobrien } 115718334Speter } 115818334Speter 115990075Sobrien fini: 116090075Sobrien /* Insert nodes testing mode and code, if they're still relevant, 116190075Sobrien before any of the nodes we may have added above. */ 116290075Sobrien if (code != UNKNOWN) 116318334Speter { 116490075Sobrien place = &this->tests; 116590075Sobrien test = new_decision_test (DT_code, &place); 116690075Sobrien test->u.code = code; 116790075Sobrien } 116890075Sobrien 116990075Sobrien if (mode != VOIDmode) 117090075Sobrien { 117190075Sobrien place = &this->tests; 117290075Sobrien test = new_decision_test (DT_mode, &place); 117390075Sobrien test->u.mode = mode; 117490075Sobrien } 117590075Sobrien 117690075Sobrien /* If we didn't insert any tests or accept nodes, hork. */ 1177169689Skan gcc_assert (this->tests); 117890075Sobrien 117990075Sobrien ret: 118090075Sobrien free (subpos); 118190075Sobrien return sub; 118290075Sobrien} 118390075Sobrien 118490075Sobrien/* A subroutine of maybe_both_true; examines only one test. 118590075Sobrien Returns > 0 for "definitely both true" and < 0 for "maybe both true". */ 118690075Sobrien 118790075Sobrienstatic int 1188132718Skanmaybe_both_true_2 (struct decision_test *d1, struct decision_test *d2) 118990075Sobrien{ 119090075Sobrien if (d1->type == d2->type) 119190075Sobrien { 119290075Sobrien switch (d1->type) 119318334Speter { 1194169689Skan case DT_num_insns: 1195169689Skan if (d1->u.num_insns == d2->u.num_insns) 1196169689Skan return 1; 1197169689Skan else 1198169689Skan return -1; 1199169689Skan 120090075Sobrien case DT_mode: 120196263Sobrien return d1->u.mode == d2->u.mode; 120290075Sobrien 120390075Sobrien case DT_code: 120490075Sobrien return d1->u.code == d2->u.code; 120590075Sobrien 120690075Sobrien case DT_veclen: 120790075Sobrien return d1->u.veclen == d2->u.veclen; 120890075Sobrien 120990075Sobrien case DT_elt_zero_int: 121090075Sobrien case DT_elt_one_int: 121190075Sobrien case DT_elt_zero_wide: 121290075Sobrien case DT_elt_zero_wide_safe: 121390075Sobrien return d1->u.intval == d2->u.intval; 121490075Sobrien 121590075Sobrien default: 121690075Sobrien break; 121718334Speter } 121890075Sobrien } 121990075Sobrien 122090075Sobrien /* If either has a predicate that we know something about, set 122190075Sobrien things up so that D1 is the one that always has a known 122290075Sobrien predicate. Then see if they have any codes in common. */ 122390075Sobrien 122490075Sobrien if (d1->type == DT_pred || d2->type == DT_pred) 122590075Sobrien { 122690075Sobrien if (d2->type == DT_pred) 122718334Speter { 122890075Sobrien struct decision_test *tmp; 122990075Sobrien tmp = d1, d1 = d2, d2 = tmp; 123018334Speter } 123190075Sobrien 123290075Sobrien /* If D2 tests a mode, see if it matches D1. */ 123390075Sobrien if (d1->u.pred.mode != VOIDmode) 123418334Speter { 123590075Sobrien if (d2->type == DT_mode) 123690075Sobrien { 123796263Sobrien if (d1->u.pred.mode != d2->u.mode 123890075Sobrien /* The mode of an address_operand predicate is the 123990075Sobrien mode of the memory, not the operand. It can only 124090075Sobrien be used for testing the predicate, so we must 124190075Sobrien ignore it here. */ 124290075Sobrien && strcmp (d1->u.pred.name, "address_operand") != 0) 124390075Sobrien return 0; 124490075Sobrien } 124590075Sobrien /* Don't check two predicate modes here, because if both predicates 124690075Sobrien accept CONST_INT, then both can still be true even if the modes 124790075Sobrien are different. If they don't accept CONST_INT, there will be a 124890075Sobrien separate DT_mode that will make maybe_both_true_1 return 0. */ 124918334Speter } 125090075Sobrien 1251169689Skan if (d1->u.pred.data) 125218334Speter { 125390075Sobrien /* If D2 tests a code, see if it is in the list of valid 125490075Sobrien codes for D1's predicate. */ 125590075Sobrien if (d2->type == DT_code) 125618334Speter { 1257169689Skan if (!d1->u.pred.data->codes[d2->u.code]) 125890075Sobrien return 0; 125918334Speter } 126090075Sobrien 126190075Sobrien /* Otherwise see if the predicates have any codes in common. */ 1262169689Skan else if (d2->type == DT_pred && d2->u.pred.data) 126390075Sobrien { 1264169689Skan bool common = false; 1265169689Skan enum rtx_code c; 126690075Sobrien 1267169689Skan for (c = 0; c < NUM_RTX_CODE; c++) 1268169689Skan if (d1->u.pred.data->codes[c] && d2->u.pred.data->codes[c]) 1269169689Skan { 1270169689Skan common = true; 1271169689Skan break; 1272169689Skan } 127390075Sobrien 127490075Sobrien if (!common) 127590075Sobrien return 0; 127690075Sobrien } 127718334Speter } 127818334Speter } 127990075Sobrien 128090075Sobrien /* Tests vs veclen may be known when strict equality is involved. */ 128190075Sobrien if (d1->type == DT_veclen && d2->type == DT_veclen_ge) 128290075Sobrien return d1->u.veclen >= d2->u.veclen; 128390075Sobrien if (d1->type == DT_veclen_ge && d2->type == DT_veclen) 128490075Sobrien return d2->u.veclen >= d1->u.veclen; 128590075Sobrien 128690075Sobrien return -1; 128718334Speter} 128890075Sobrien 128990075Sobrien/* A subroutine of maybe_both_true; examines all the tests for a given node. 129090075Sobrien Returns > 0 for "definitely both true" and < 0 for "maybe both true". */ 129190075Sobrien 129290075Sobrienstatic int 1293132718Skanmaybe_both_true_1 (struct decision_test *d1, struct decision_test *d2) 129490075Sobrien{ 129590075Sobrien struct decision_test *t1, *t2; 129690075Sobrien 129790075Sobrien /* A match_operand with no predicate can match anything. Recognize 129890075Sobrien this by the existence of a lone DT_accept_op test. */ 129990075Sobrien if (d1->type == DT_accept_op || d2->type == DT_accept_op) 130090075Sobrien return 1; 130190075Sobrien 130290075Sobrien /* Eliminate pairs of tests while they can exactly match. */ 130390075Sobrien while (d1 && d2 && d1->type == d2->type) 130490075Sobrien { 130590075Sobrien if (maybe_both_true_2 (d1, d2) == 0) 130690075Sobrien return 0; 130790075Sobrien d1 = d1->next, d2 = d2->next; 130890075Sobrien } 130990075Sobrien 131090075Sobrien /* After that, consider all pairs. */ 131190075Sobrien for (t1 = d1; t1 ; t1 = t1->next) 131290075Sobrien for (t2 = d2; t2 ; t2 = t2->next) 131390075Sobrien if (maybe_both_true_2 (t1, t2) == 0) 131490075Sobrien return 0; 131590075Sobrien 131690075Sobrien return -1; 131790075Sobrien} 131890075Sobrien 131990075Sobrien/* Return 0 if we can prove that there is no RTL that can match both 132090075Sobrien D1 and D2. Otherwise, return 1 (it may be that there is an RTL that 132118334Speter can match both or just that we couldn't prove there wasn't such an RTL). 132218334Speter 1323117395Skan TOPLEVEL is nonzero if we are to only look at the top level and not 132418334Speter recursively descend. */ 132518334Speter 132618334Speterstatic int 1327132718Skanmaybe_both_true (struct decision *d1, struct decision *d2, 1328132718Skan int toplevel) 132918334Speter{ 133018334Speter struct decision *p1, *p2; 133190075Sobrien int cmp; 133218334Speter 133390075Sobrien /* Don't compare strings on the different positions in insn. Doing so 133490075Sobrien is incorrect and results in false matches from constructs like 133518334Speter 133690075Sobrien [(set (subreg:HI (match_operand:SI "register_operand" "r") 0) 133790075Sobrien (subreg:HI (match_operand:SI "register_operand" "r") 0))] 133890075Sobrien vs 133990075Sobrien [(set (match_operand:HI "register_operand" "r") 134090075Sobrien (match_operand:HI "register_operand" "r"))] 134118334Speter 134290075Sobrien If we are presented with such, we are recursing through the remainder 134390075Sobrien of a node's success nodes (from the loop at the end of this function). 134490075Sobrien Skip forward until we come to a position that matches. 134518334Speter 134690075Sobrien Due to the way position strings are constructed, we know that iterating 134790075Sobrien forward from the lexically lower position (e.g. "00") will run into 134890075Sobrien the lexically higher position (e.g. "1") and not the other way around. 134990075Sobrien This saves a bit of effort. */ 135018334Speter 135190075Sobrien cmp = strcmp (d1->position, d2->position); 135290075Sobrien if (cmp != 0) 135318334Speter { 1354169689Skan gcc_assert (!toplevel); 135518334Speter 135690075Sobrien /* If the d2->position was lexically lower, swap. */ 135790075Sobrien if (cmp > 0) 135818334Speter p1 = d1, d1 = d2, d2 = p1; 135918334Speter 136090075Sobrien if (d1->success.first == 0) 136190075Sobrien return 1; 136290075Sobrien for (p1 = d1->success.first; p1; p1 = p1->next) 136390075Sobrien if (maybe_both_true (p1, d2, 0)) 136490075Sobrien return 1; 136518334Speter 136690075Sobrien return 0; 136790075Sobrien } 136818334Speter 136990075Sobrien /* Test the current level. */ 137090075Sobrien cmp = maybe_both_true_1 (d1->tests, d2->tests); 137190075Sobrien if (cmp >= 0) 137290075Sobrien return cmp; 137318334Speter 137490075Sobrien /* We can't prove that D1 and D2 cannot both be true. If we are only 137590075Sobrien to check the top level, return 1. Otherwise, see if we can prove 137690075Sobrien that all choices in both successors are mutually exclusive. If 137790075Sobrien either does not have any successors, we can't prove they can't both 137890075Sobrien be true. */ 137918334Speter 138018334Speter if (toplevel || d1->success.first == 0 || d2->success.first == 0) 138190075Sobrien return 1; 138218334Speter 138318334Speter for (p1 = d1->success.first; p1; p1 = p1->next) 138418334Speter for (p2 = d2->success.first; p2; p2 = p2->next) 138590075Sobrien if (maybe_both_true (p1, p2, 0)) 138690075Sobrien return 1; 138718334Speter 138890075Sobrien return 0; 138918334Speter} 139018334Speter 139190075Sobrien/* A subroutine of nodes_identical. Examine two tests for equivalence. */ 139218334Speter 139390075Sobrienstatic int 1394132718Skannodes_identical_1 (struct decision_test *d1, struct decision_test *d2) 139590075Sobrien{ 139690075Sobrien switch (d1->type) 139790075Sobrien { 1398169689Skan case DT_num_insns: 1399169689Skan return d1->u.num_insns == d2->u.num_insns; 1400169689Skan 140190075Sobrien case DT_mode: 140290075Sobrien return d1->u.mode == d2->u.mode; 140318334Speter 140490075Sobrien case DT_code: 140590075Sobrien return d1->u.code == d2->u.code; 140690075Sobrien 140790075Sobrien case DT_pred: 140890075Sobrien return (d1->u.pred.mode == d2->u.pred.mode 140990075Sobrien && strcmp (d1->u.pred.name, d2->u.pred.name) == 0); 141090075Sobrien 141190075Sobrien case DT_c_test: 141290075Sobrien return strcmp (d1->u.c_test, d2->u.c_test) == 0; 141390075Sobrien 141490075Sobrien case DT_veclen: 141590075Sobrien case DT_veclen_ge: 141690075Sobrien return d1->u.veclen == d2->u.veclen; 141790075Sobrien 141890075Sobrien case DT_dup: 141990075Sobrien return d1->u.dup == d2->u.dup; 142090075Sobrien 142190075Sobrien case DT_elt_zero_int: 142290075Sobrien case DT_elt_one_int: 142390075Sobrien case DT_elt_zero_wide: 142490075Sobrien case DT_elt_zero_wide_safe: 142590075Sobrien return d1->u.intval == d2->u.intval; 142690075Sobrien 142790075Sobrien case DT_accept_op: 142890075Sobrien return d1->u.opno == d2->u.opno; 142990075Sobrien 143090075Sobrien case DT_accept_insn: 143190075Sobrien /* Differences will be handled in merge_accept_insn. */ 143290075Sobrien return 1; 143390075Sobrien 143490075Sobrien default: 1435169689Skan gcc_unreachable (); 143690075Sobrien } 143790075Sobrien} 143890075Sobrien 143990075Sobrien/* True iff the two nodes are identical (on one level only). Due 144090075Sobrien to the way these lists are constructed, we shouldn't have to 144190075Sobrien consider different orderings on the tests. */ 144290075Sobrien 144318334Speterstatic int 1444132718Skannodes_identical (struct decision *d1, struct decision *d2) 144518334Speter{ 144690075Sobrien struct decision_test *t1, *t2; 144718334Speter 144890075Sobrien for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next) 144990075Sobrien { 145090075Sobrien if (t1->type != t2->type) 145190075Sobrien return 0; 145290075Sobrien if (! nodes_identical_1 (t1, t2)) 145390075Sobrien return 0; 145490075Sobrien } 145518334Speter 145690075Sobrien /* For success, they should now both be null. */ 145790075Sobrien if (t1 != t2) 145890075Sobrien return 0; 145918334Speter 146090075Sobrien /* Check that their subnodes are at the same position, as any one set 146190075Sobrien of sibling decisions must be at the same position. Allowing this 146290075Sobrien requires complications to find_afterward and when change_state is 146390075Sobrien invoked. */ 146490075Sobrien if (d1->success.first 146590075Sobrien && d2->success.first 146690075Sobrien && strcmp (d1->success.first->position, d2->success.first->position)) 146718334Speter return 0; 146818334Speter 146990075Sobrien return 1; 147090075Sobrien} 147118334Speter 147290075Sobrien/* A subroutine of merge_trees; given two nodes that have been declared 147390075Sobrien identical, cope with two insn accept states. If they differ in the 147490075Sobrien number of clobbers, then the conflict was created by make_insn_sequence 147590075Sobrien and we can drop the with-clobbers version on the floor. If both 147690075Sobrien nodes have no additional clobbers, we have found an ambiguity in the 147790075Sobrien source machine description. */ 147818334Speter 147990075Sobrienstatic void 1480132718Skanmerge_accept_insn (struct decision *oldd, struct decision *addd) 148190075Sobrien{ 148290075Sobrien struct decision_test *old, *add; 148318334Speter 148490075Sobrien for (old = oldd->tests; old; old = old->next) 148590075Sobrien if (old->type == DT_accept_insn) 148690075Sobrien break; 148790075Sobrien if (old == NULL) 148890075Sobrien return; 148918334Speter 149090075Sobrien for (add = addd->tests; add; add = add->next) 149190075Sobrien if (add->type == DT_accept_insn) 149290075Sobrien break; 149390075Sobrien if (add == NULL) 149490075Sobrien return; 149518334Speter 149690075Sobrien /* If one node is for a normal insn and the second is for the base 149790075Sobrien insn with clobbers stripped off, the second node should be ignored. */ 149890075Sobrien 149990075Sobrien if (old->u.insn.num_clobbers_to_add == 0 150090075Sobrien && add->u.insn.num_clobbers_to_add > 0) 150190075Sobrien { 150290075Sobrien /* Nothing to do here. */ 150390075Sobrien } 150490075Sobrien else if (old->u.insn.num_clobbers_to_add > 0 150590075Sobrien && add->u.insn.num_clobbers_to_add == 0) 150690075Sobrien { 150790075Sobrien /* In this case, replace OLD with ADD. */ 150890075Sobrien old->u.insn = add->u.insn; 150990075Sobrien } 151090075Sobrien else 151190075Sobrien { 151290075Sobrien message_with_line (add->u.insn.lineno, "`%s' matches `%s'", 151390075Sobrien get_insn_name (add->u.insn.code_number), 151490075Sobrien get_insn_name (old->u.insn.code_number)); 151590075Sobrien message_with_line (old->u.insn.lineno, "previous definition of `%s'", 151690075Sobrien get_insn_name (old->u.insn.code_number)); 151790075Sobrien error_count++; 151890075Sobrien } 151918334Speter} 152018334Speter 152190075Sobrien/* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */ 152290075Sobrien 152390075Sobrienstatic void 1524132718Skanmerge_trees (struct decision_head *oldh, struct decision_head *addh) 152518334Speter{ 152690075Sobrien struct decision *next, *add; 152718334Speter 152890075Sobrien if (addh->first == 0) 152990075Sobrien return; 153090075Sobrien if (oldh->first == 0) 153190075Sobrien { 153290075Sobrien *oldh = *addh; 153390075Sobrien return; 153490075Sobrien } 153518334Speter 153690075Sobrien /* Trying to merge bits at different positions isn't possible. */ 1537169689Skan gcc_assert (!strcmp (oldh->first->position, addh->first->position)); 153818334Speter 153990075Sobrien for (add = addh->first; add ; add = next) 154018334Speter { 154190075Sobrien struct decision *old, *insert_before = NULL; 154218334Speter 154318334Speter next = add->next; 154418334Speter 154590075Sobrien /* The semantics of pattern matching state that the tests are 154690075Sobrien done in the order given in the MD file so that if an insn 154790075Sobrien matches two patterns, the first one will be used. However, 154890075Sobrien in practice, most, if not all, patterns are unambiguous so 154990075Sobrien that their order is independent. In that case, we can merge 155090075Sobrien identical tests and group all similar modes and codes together. 155118334Speter 155218334Speter Scan starting from the end of OLDH until we reach a point 155390075Sobrien where we reach the head of the list or where we pass a 155490075Sobrien pattern that could also be true if NEW is true. If we find 155590075Sobrien an identical pattern, we can merge them. Also, record the 155690075Sobrien last node that tests the same code and mode and the last one 155790075Sobrien that tests just the same mode. 155818334Speter 155918334Speter If we have no match, place NEW after the closest match we found. */ 156090075Sobrien 156190075Sobrien for (old = oldh->last; old; old = old->prev) 156218334Speter { 156390075Sobrien if (nodes_identical (old, add)) 156490075Sobrien { 156590075Sobrien merge_accept_insn (old, add); 156690075Sobrien merge_trees (&old->success, &add->success); 156790075Sobrien goto merged_nodes; 156890075Sobrien } 156918334Speter 157090075Sobrien if (maybe_both_true (old, add, 0)) 157190075Sobrien break; 157218334Speter 157390075Sobrien /* Insert the nodes in DT test type order, which is roughly 157490075Sobrien how expensive/important the test is. Given that the tests 157590075Sobrien are also ordered within the list, examining the first is 157690075Sobrien sufficient. */ 157790075Sobrien if ((int) add->tests->type < (int) old->tests->type) 157890075Sobrien insert_before = old; 157990075Sobrien } 158018334Speter 158190075Sobrien if (insert_before == NULL) 158290075Sobrien { 158390075Sobrien add->next = NULL; 158490075Sobrien add->prev = oldh->last; 158590075Sobrien oldh->last->next = add; 158690075Sobrien oldh->last = add; 158790075Sobrien } 158890075Sobrien else 158990075Sobrien { 159090075Sobrien if ((add->prev = insert_before->prev) != NULL) 159190075Sobrien add->prev->next = add; 159290075Sobrien else 159390075Sobrien oldh->first = add; 159490075Sobrien add->next = insert_before; 159590075Sobrien insert_before->prev = add; 159690075Sobrien } 159718334Speter 159890075Sobrien merged_nodes:; 159990075Sobrien } 160090075Sobrien} 160190075Sobrien 160290075Sobrien/* Walk the tree looking for sub-nodes that perform common tests. 160390075Sobrien Factor out the common test into a new node. This enables us 160490075Sobrien (depending on the test type) to emit switch statements later. */ 160518334Speter 160690075Sobrienstatic void 1607132718Skanfactor_tests (struct decision_head *head) 160890075Sobrien{ 160990075Sobrien struct decision *first, *next; 161018334Speter 161190075Sobrien for (first = head->first; first && first->next; first = next) 161290075Sobrien { 161390075Sobrien enum decision_type type; 161490075Sobrien struct decision *new, *old_last; 161518334Speter 161690075Sobrien type = first->tests->type; 161790075Sobrien next = first->next; 161818334Speter 161990075Sobrien /* Want at least two compatible sequential nodes. */ 162090075Sobrien if (next->tests->type != type) 162190075Sobrien continue; 162218334Speter 162390075Sobrien /* Don't want all node types, just those we can turn into 162490075Sobrien switch statements. */ 162590075Sobrien if (type != DT_mode 162690075Sobrien && type != DT_code 162790075Sobrien && type != DT_veclen 162890075Sobrien && type != DT_elt_zero_int 162990075Sobrien && type != DT_elt_one_int 163090075Sobrien && type != DT_elt_zero_wide_safe) 163190075Sobrien continue; 163218334Speter 163390075Sobrien /* If we'd been performing more than one test, create a new node 163490075Sobrien below our first test. */ 163590075Sobrien if (first->tests->next != NULL) 163690075Sobrien { 163790075Sobrien new = new_decision (first->position, &first->success); 163890075Sobrien new->tests = first->tests->next; 163990075Sobrien first->tests->next = NULL; 164090075Sobrien } 164118334Speter 164290075Sobrien /* Crop the node tree off after our first test. */ 164390075Sobrien first->next = NULL; 164490075Sobrien old_last = head->last; 164590075Sobrien head->last = first; 164618334Speter 164790075Sobrien /* For each compatible test, adjust to perform only one test in 164890075Sobrien the top level node, then merge the node back into the tree. */ 164990075Sobrien do 165090075Sobrien { 165190075Sobrien struct decision_head h; 165218334Speter 165390075Sobrien if (next->tests->next != NULL) 165490075Sobrien { 165590075Sobrien new = new_decision (next->position, &next->success); 165690075Sobrien new->tests = next->tests->next; 165790075Sobrien next->tests->next = NULL; 165818334Speter } 165990075Sobrien new = next; 166090075Sobrien next = next->next; 166190075Sobrien new->next = NULL; 166290075Sobrien h.first = h.last = new; 166318334Speter 166490075Sobrien merge_trees (head, &h); 166590075Sobrien } 166690075Sobrien while (next && next->tests->type == type); 166718334Speter 166890075Sobrien /* After we run out of compatible tests, graft the remaining nodes 166990075Sobrien back onto the tree. */ 167090075Sobrien if (next) 167190075Sobrien { 167290075Sobrien next->prev = head->last; 167390075Sobrien head->last->next = next; 167490075Sobrien head->last = old_last; 167518334Speter } 167690075Sobrien } 167718334Speter 167890075Sobrien /* Recurse. */ 167990075Sobrien for (first = head->first; first; first = first->next) 168090075Sobrien factor_tests (&first->success); 168190075Sobrien} 168218334Speter 168390075Sobrien/* After factoring, try to simplify the tests on any one node. 168490075Sobrien Tests that are useful for switch statements are recognizable 168590075Sobrien by having only a single test on a node -- we'll be manipulating 168690075Sobrien nodes with multiple tests: 168718334Speter 168890075Sobrien If we have mode tests or code tests that are redundant with 168990075Sobrien predicates, remove them. */ 169018334Speter 169190075Sobrienstatic void 1692132718Skansimplify_tests (struct decision_head *head) 169390075Sobrien{ 169490075Sobrien struct decision *tree; 169518334Speter 169690075Sobrien for (tree = head->first; tree; tree = tree->next) 169790075Sobrien { 169890075Sobrien struct decision_test *a, *b; 169990075Sobrien 170090075Sobrien a = tree->tests; 170190075Sobrien b = a->next; 170290075Sobrien if (b == NULL) 170390075Sobrien continue; 170490075Sobrien 170590075Sobrien /* Find a predicate node. */ 170690075Sobrien while (b && b->type != DT_pred) 170790075Sobrien b = b->next; 170890075Sobrien if (b) 170918334Speter { 171090075Sobrien /* Due to how these tests are constructed, we don't even need 171190075Sobrien to check that the mode and code are compatible -- they were 171290075Sobrien generated from the predicate in the first place. */ 171390075Sobrien while (a->type == DT_mode || a->type == DT_code) 171490075Sobrien a = a->next; 171590075Sobrien tree->tests = a; 171618334Speter } 171718334Speter } 171818334Speter 171990075Sobrien /* Recurse. */ 172090075Sobrien for (tree = head->first; tree; tree = tree->next) 172190075Sobrien simplify_tests (&tree->success); 172218334Speter} 172390075Sobrien 172418334Speter/* Count the number of subnodes of HEAD. If the number is high enough, 172518334Speter make the first node in HEAD start a separate subroutine in the C code 172690075Sobrien that is generated. */ 172718334Speter 172818334Speterstatic int 1729132718Skanbreak_out_subroutines (struct decision_head *head, int initial) 173018334Speter{ 173118334Speter int size = 0; 173218334Speter struct decision *sub; 173318334Speter 173490075Sobrien for (sub = head->first; sub; sub = sub->next) 173590075Sobrien size += 1 + break_out_subroutines (&sub->success, 0); 173618334Speter 173718334Speter if (size > SUBROUTINE_THRESHOLD && ! initial) 173818334Speter { 173990075Sobrien head->first->subroutine_number = ++next_subroutine_number; 174018334Speter size = 1; 174118334Speter } 174218334Speter return size; 174318334Speter} 174418334Speter 174590075Sobrien/* For each node p, find the next alternative that might be true 174690075Sobrien when p is true. */ 174790075Sobrien 174818334Speterstatic void 1749132718Skanfind_afterward (struct decision_head *head, struct decision *real_afterward) 175018334Speter{ 175190075Sobrien struct decision *p, *q, *afterward; 175218334Speter 175390075Sobrien /* We can't propagate alternatives across subroutine boundaries. 175490075Sobrien This is not incorrect, merely a minor optimization loss. */ 175518334Speter 175690075Sobrien p = head->first; 175790075Sobrien afterward = (p->subroutine_number > 0 ? NULL : real_afterward); 175818334Speter 175990075Sobrien for ( ; p ; p = p->next) 176090075Sobrien { 176190075Sobrien /* Find the next node that might be true if this one fails. */ 176290075Sobrien for (q = p->next; q ; q = q->next) 176390075Sobrien if (maybe_both_true (p, q, 1)) 176490075Sobrien break; 176518334Speter 176690075Sobrien /* If we reached the end of the list without finding one, 176790075Sobrien use the incoming afterward position. */ 176890075Sobrien if (!q) 176990075Sobrien q = afterward; 177090075Sobrien p->afterward = q; 177190075Sobrien if (q) 177290075Sobrien q->need_label = 1; 177390075Sobrien } 177418334Speter 177590075Sobrien /* Recurse. */ 177690075Sobrien for (p = head->first; p ; p = p->next) 177790075Sobrien if (p->success.first) 177890075Sobrien find_afterward (&p->success, p->afterward); 177918334Speter 178090075Sobrien /* When we are generating a subroutine, record the real afterward 178190075Sobrien position in the first node where write_tree can find it, and we 178290075Sobrien can do the right thing at the subroutine call site. */ 178390075Sobrien p = head->first; 178490075Sobrien if (p->subroutine_number > 0) 178590075Sobrien p->afterward = real_afterward; 178618334Speter} 178718334Speter 178890075Sobrien/* Assuming that the state of argument is denoted by OLDPOS, take whatever 178990075Sobrien actions are necessary to move to NEWPOS. If we fail to move to the 1790117395Skan new state, branch to node AFTERWARD if nonzero, otherwise return. 179118334Speter 179290075Sobrien Failure to move to the new state can only occur if we are trying to 179390075Sobrien match multiple insns and we try to step past the end of the stream. */ 179418334Speter 179590075Sobrienstatic void 1796169689Skanchange_state (const char *oldpos, const char *newpos, const char *indent) 179790075Sobrien{ 179890075Sobrien int odepth = strlen (oldpos); 179990075Sobrien int ndepth = strlen (newpos); 180090075Sobrien int depth; 180190075Sobrien int old_has_insn, new_has_insn; 180218334Speter 180390075Sobrien /* Pop up as many levels as necessary. */ 180490075Sobrien for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth) 180590075Sobrien continue; 180618334Speter 180790075Sobrien /* Hunt for the last [A-Z] in both strings. */ 180890075Sobrien for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn) 180990075Sobrien if (ISUPPER (oldpos[old_has_insn])) 181090075Sobrien break; 181190075Sobrien for (new_has_insn = ndepth - 1; new_has_insn >= 0; --new_has_insn) 181290075Sobrien if (ISUPPER (newpos[new_has_insn])) 181390075Sobrien break; 181418334Speter 181590075Sobrien /* Go down to desired level. */ 181690075Sobrien while (depth < ndepth) 181790075Sobrien { 181890075Sobrien /* It's a different insn from the first one. */ 181990075Sobrien if (ISUPPER (newpos[depth])) 182090075Sobrien { 1821169689Skan printf ("%stem = peep2_next_insn (%d);\n", 1822169689Skan indent, newpos[depth] - 'A'); 182390075Sobrien printf ("%sx%d = PATTERN (tem);\n", indent, depth + 1); 182490075Sobrien } 182590075Sobrien else if (ISLOWER (newpos[depth])) 182690075Sobrien printf ("%sx%d = XVECEXP (x%d, 0, %d);\n", 182790075Sobrien indent, depth + 1, depth, newpos[depth] - 'a'); 182890075Sobrien else 182990075Sobrien printf ("%sx%d = XEXP (x%d, %c);\n", 183090075Sobrien indent, depth + 1, depth, newpos[depth]); 183190075Sobrien ++depth; 183290075Sobrien } 183390075Sobrien} 183490075Sobrien 183590075Sobrien/* Print the enumerator constant for CODE -- the upcase version of 183690075Sobrien the name. */ 183718334Speter 183818334Speterstatic void 1839132718Skanprint_code (enum rtx_code code) 184018334Speter{ 184190075Sobrien const char *p; 184290075Sobrien for (p = GET_RTX_NAME (code); *p; p++) 184390075Sobrien putchar (TOUPPER (*p)); 184490075Sobrien} 184518334Speter 184690075Sobrien/* Emit code to cross an afterward link -- change state and branch. */ 184718334Speter 184890075Sobrienstatic void 1849132718Skanwrite_afterward (struct decision *start, struct decision *afterward, 1850132718Skan const char *indent) 185190075Sobrien{ 185290075Sobrien if (!afterward || start->subroutine_number > 0) 185390075Sobrien printf("%sgoto ret0;\n", indent); 185490075Sobrien else 185590075Sobrien { 1856169689Skan change_state (start->position, afterward->position, indent); 185790075Sobrien printf ("%sgoto L%d;\n", indent, afterward->number); 185890075Sobrien } 185990075Sobrien} 186018334Speter 1861132718Skan/* Emit a HOST_WIDE_INT as an integer constant expression. We need to take 1862132718Skan special care to avoid "decimal constant is so large that it is unsigned" 1863132718Skan warnings in the resulting code. */ 1864132718Skan 1865132718Skanstatic void 1866132718Skanprint_host_wide_int (HOST_WIDE_INT val) 1867132718Skan{ 1868132718Skan HOST_WIDE_INT min = (unsigned HOST_WIDE_INT)1 << (HOST_BITS_PER_WIDE_INT-1); 1869132718Skan if (val == min) 1870132718Skan printf ("(" HOST_WIDE_INT_PRINT_DEC_C "-1)", val + 1); 1871132718Skan else 1872132718Skan printf (HOST_WIDE_INT_PRINT_DEC_C, val); 1873132718Skan} 1874132718Skan 187590075Sobrien/* Emit a switch statement, if possible, for an initial sequence of 187690075Sobrien nodes at START. Return the first node yet untested. */ 187718334Speter 187890075Sobrienstatic struct decision * 1879132718Skanwrite_switch (struct decision *start, int depth) 188090075Sobrien{ 188190075Sobrien struct decision *p = start; 188290075Sobrien enum decision_type type = p->tests->type; 188390075Sobrien struct decision *needs_label = NULL; 188418334Speter 188590075Sobrien /* If we have two or more nodes in sequence that test the same one 188690075Sobrien thing, we may be able to use a switch statement. */ 188718334Speter 188890075Sobrien if (!p->next 188990075Sobrien || p->tests->next 189090075Sobrien || p->next->tests->type != type 189190075Sobrien || p->next->tests->next 189290075Sobrien || nodes_identical_1 (p->tests, p->next->tests)) 189390075Sobrien return p; 189418334Speter 189590075Sobrien /* DT_code is special in that we can do interesting things with 189690075Sobrien known predicates at the same time. */ 189790075Sobrien if (type == DT_code) 189818334Speter { 189990075Sobrien char codemap[NUM_RTX_CODE]; 190090075Sobrien struct decision *ret; 190190075Sobrien RTX_CODE code; 190218334Speter 190390075Sobrien memset (codemap, 0, sizeof(codemap)); 190418334Speter 190590075Sobrien printf (" switch (GET_CODE (x%d))\n {\n", depth); 190690075Sobrien code = p->tests->u.code; 190790075Sobrien do 190890075Sobrien { 190990075Sobrien if (p != start && p->need_label && needs_label == NULL) 191090075Sobrien needs_label = p; 191118334Speter 191290075Sobrien printf (" case "); 191390075Sobrien print_code (code); 191490075Sobrien printf (":\n goto L%d;\n", p->success.first->number); 191590075Sobrien p->success.first->need_label = 1; 191618334Speter 191790075Sobrien codemap[code] = 1; 191890075Sobrien p = p->next; 191918334Speter } 192090075Sobrien while (p 192190075Sobrien && ! p->tests->next 192290075Sobrien && p->tests->type == DT_code 192390075Sobrien && ! codemap[code = p->tests->u.code]); 192418334Speter 192590075Sobrien /* If P is testing a predicate that we know about and we haven't 192690075Sobrien seen any of the codes that are valid for the predicate, we can 192790075Sobrien write a series of "case" statement, one for each possible code. 192890075Sobrien Since we are already in a switch, these redundant tests are very 192990075Sobrien cheap and will reduce the number of predicates called. */ 193018334Speter 193190075Sobrien /* Note that while we write out cases for these predicates here, 193290075Sobrien we don't actually write the test here, as it gets kinda messy. 193390075Sobrien It is trivial to leave this to later by telling our caller that 193490075Sobrien we only processed the CODE tests. */ 193590075Sobrien if (needs_label != NULL) 193690075Sobrien ret = needs_label; 193790075Sobrien else 193890075Sobrien ret = p; 193990075Sobrien 1940169689Skan while (p && p->tests->type == DT_pred && p->tests->u.pred.data) 194118334Speter { 1942169689Skan const struct pred_data *data = p->tests->u.pred.data; 1943169689Skan RTX_CODE c; 1944169689Skan for (c = 0; c < NUM_RTX_CODE; c++) 1945169689Skan if (codemap[c] && data->codes[c]) 194690075Sobrien goto pred_done; 194718334Speter 1948169689Skan for (c = 0; c < NUM_RTX_CODE; c++) 1949169689Skan if (data->codes[c]) 1950169689Skan { 1951169689Skan fputs (" case ", stdout); 1952169689Skan print_code (c); 1953169689Skan fputs (":\n", stdout); 1954169689Skan codemap[c] = 1; 1955169689Skan } 195618334Speter 195790075Sobrien printf (" goto L%d;\n", p->number); 195890075Sobrien p->need_label = 1; 195990075Sobrien p = p->next; 196018334Speter } 196118334Speter 196290075Sobrien pred_done: 196390075Sobrien /* Make the default case skip the predicates we managed to match. */ 196418334Speter 196590075Sobrien printf (" default:\n"); 196690075Sobrien if (p != ret) 196718334Speter { 196890075Sobrien if (p) 196918334Speter { 197090075Sobrien printf (" goto L%d;\n", p->number); 197190075Sobrien p->need_label = 1; 197218334Speter } 197318334Speter else 197490075Sobrien write_afterward (start, start->afterward, " "); 197518334Speter } 197690075Sobrien else 197790075Sobrien printf (" break;\n"); 197890075Sobrien printf (" }\n"); 197918334Speter 198090075Sobrien return ret; 198190075Sobrien } 198290075Sobrien else if (type == DT_mode 198390075Sobrien || type == DT_veclen 198490075Sobrien || type == DT_elt_zero_int 198590075Sobrien || type == DT_elt_one_int 198690075Sobrien || type == DT_elt_zero_wide_safe) 198790075Sobrien { 198890075Sobrien const char *indent = ""; 198918334Speter 199090075Sobrien /* We cast switch parameter to integer, so we must ensure that the value 199190075Sobrien fits. */ 199290075Sobrien if (type == DT_elt_zero_wide_safe) 199318334Speter { 199490075Sobrien indent = " "; 199590075Sobrien printf(" if ((int) XWINT (x%d, 0) == XWINT (x%d, 0))\n", depth, depth); 199618334Speter } 199790075Sobrien printf ("%s switch (", indent); 199890075Sobrien switch (type) 199990075Sobrien { 200090075Sobrien case DT_mode: 200190075Sobrien printf ("GET_MODE (x%d)", depth); 200290075Sobrien break; 200390075Sobrien case DT_veclen: 200490075Sobrien printf ("XVECLEN (x%d, 0)", depth); 200590075Sobrien break; 200690075Sobrien case DT_elt_zero_int: 200790075Sobrien printf ("XINT (x%d, 0)", depth); 200890075Sobrien break; 200990075Sobrien case DT_elt_one_int: 201090075Sobrien printf ("XINT (x%d, 1)", depth); 201190075Sobrien break; 201290075Sobrien case DT_elt_zero_wide_safe: 201390075Sobrien /* Convert result of XWINT to int for portability since some C 201490075Sobrien compilers won't do it and some will. */ 201590075Sobrien printf ("(int) XWINT (x%d, 0)", depth); 201690075Sobrien break; 201790075Sobrien default: 2018169689Skan gcc_unreachable (); 201990075Sobrien } 202090075Sobrien printf (")\n%s {\n", indent); 202118334Speter 202290075Sobrien do 202318334Speter { 202490075Sobrien /* Merge trees will not unify identical nodes if their 202590075Sobrien sub-nodes are at different levels. Thus we must check 202690075Sobrien for duplicate cases. */ 202790075Sobrien struct decision *q; 202890075Sobrien for (q = start; q != p; q = q->next) 202990075Sobrien if (nodes_identical_1 (p->tests, q->tests)) 203090075Sobrien goto case_done; 203118334Speter 203290075Sobrien if (p != start && p->need_label && needs_label == NULL) 203390075Sobrien needs_label = p; 203418334Speter 203590075Sobrien printf ("%s case ", indent); 203690075Sobrien switch (type) 203718334Speter { 203890075Sobrien case DT_mode: 203990075Sobrien printf ("%smode", GET_MODE_NAME (p->tests->u.mode)); 204090075Sobrien break; 204190075Sobrien case DT_veclen: 204290075Sobrien printf ("%d", p->tests->u.veclen); 204390075Sobrien break; 204490075Sobrien case DT_elt_zero_int: 204590075Sobrien case DT_elt_one_int: 204690075Sobrien case DT_elt_zero_wide: 204790075Sobrien case DT_elt_zero_wide_safe: 2048132718Skan print_host_wide_int (p->tests->u.intval); 204990075Sobrien break; 205090075Sobrien default: 2051169689Skan gcc_unreachable (); 205218334Speter } 205390075Sobrien printf (":\n%s goto L%d;\n", indent, p->success.first->number); 205490075Sobrien p->success.first->need_label = 1; 205518334Speter 205690075Sobrien p = p->next; 205718334Speter } 205890075Sobrien while (p && p->tests->type == type && !p->tests->next); 205918334Speter 206090075Sobrien case_done: 206190075Sobrien printf ("%s default:\n%s break;\n%s }\n", 206290075Sobrien indent, indent, indent); 206318334Speter 206490075Sobrien return needs_label != NULL ? needs_label : p; 206590075Sobrien } 206690075Sobrien else 206790075Sobrien { 2068132718Skan /* None of the other tests are amenable. */ 206990075Sobrien return p; 207090075Sobrien } 207190075Sobrien} 207218334Speter 207390075Sobrien/* Emit code for one test. */ 207418334Speter 207590075Sobrienstatic void 2076132718Skanwrite_cond (struct decision_test *p, int depth, 2077132718Skan enum routine_type subroutine_type) 207890075Sobrien{ 207990075Sobrien switch (p->type) 208090075Sobrien { 2081169689Skan case DT_num_insns: 2082169689Skan printf ("peep2_current_count >= %d", p->u.num_insns); 2083169689Skan break; 2084169689Skan 208590075Sobrien case DT_mode: 208690075Sobrien printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode)); 208790075Sobrien break; 208818334Speter 208990075Sobrien case DT_code: 209090075Sobrien printf ("GET_CODE (x%d) == ", depth); 209190075Sobrien print_code (p->u.code); 209290075Sobrien break; 209318334Speter 209490075Sobrien case DT_veclen: 209590075Sobrien printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen); 209690075Sobrien break; 209718334Speter 209890075Sobrien case DT_elt_zero_int: 209990075Sobrien printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval); 210090075Sobrien break; 210118334Speter 210290075Sobrien case DT_elt_one_int: 210390075Sobrien printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval); 210490075Sobrien break; 210518334Speter 210690075Sobrien case DT_elt_zero_wide: 210790075Sobrien case DT_elt_zero_wide_safe: 210890075Sobrien printf ("XWINT (x%d, 0) == ", depth); 2109132718Skan print_host_wide_int (p->u.intval); 211090075Sobrien break; 211118334Speter 2112169689Skan case DT_const_int: 2113169689Skan printf ("x%d == const_int_rtx[MAX_SAVED_CONST_INT + (%d)]", 2114169689Skan depth, (int) p->u.intval); 2115169689Skan break; 2116169689Skan 211790075Sobrien case DT_veclen_ge: 211890075Sobrien printf ("XVECLEN (x%d, 0) >= %d", depth, p->u.veclen); 211990075Sobrien break; 212018334Speter 212190075Sobrien case DT_dup: 212290075Sobrien printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup); 212390075Sobrien break; 212418334Speter 212590075Sobrien case DT_pred: 212690075Sobrien printf ("%s (x%d, %smode)", p->u.pred.name, depth, 212790075Sobrien GET_MODE_NAME (p->u.pred.mode)); 212890075Sobrien break; 212918334Speter 213090075Sobrien case DT_c_test: 2131169689Skan print_c_condition (p->u.c_test); 213290075Sobrien break; 213318334Speter 213490075Sobrien case DT_accept_insn: 2135169689Skan gcc_assert (subroutine_type == RECOG); 2136169689Skan gcc_assert (p->u.insn.num_clobbers_to_add); 2137169689Skan printf ("pnum_clobbers != NULL"); 213890075Sobrien break; 213918334Speter 214090075Sobrien default: 2141169689Skan gcc_unreachable (); 214218334Speter } 214390075Sobrien} 214418334Speter 214590075Sobrien/* Emit code for one action. The previous tests have succeeded; 214690075Sobrien TEST is the last of the chain. In the normal case we simply 214790075Sobrien perform a state change. For the `accept' tests we must do more work. */ 214818334Speter 214990075Sobrienstatic void 2150132718Skanwrite_action (struct decision *p, struct decision_test *test, 2151132718Skan int depth, int uncond, struct decision *success, 2152132718Skan enum routine_type subroutine_type) 215390075Sobrien{ 215490075Sobrien const char *indent; 215590075Sobrien int want_close = 0; 215690075Sobrien 215790075Sobrien if (uncond) 215890075Sobrien indent = " "; 215990075Sobrien else if (test->type == DT_accept_op || test->type == DT_accept_insn) 216018334Speter { 216190075Sobrien fputs (" {\n", stdout); 216290075Sobrien indent = " "; 216390075Sobrien want_close = 1; 216418334Speter } 216590075Sobrien else 216690075Sobrien indent = " "; 216718334Speter 216890075Sobrien if (test->type == DT_accept_op) 216918334Speter { 217090075Sobrien printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth); 217190075Sobrien 217290075Sobrien /* Only allow DT_accept_insn to follow. */ 217390075Sobrien if (test->next) 217490075Sobrien { 217590075Sobrien test = test->next; 2176169689Skan gcc_assert (test->type == DT_accept_insn); 217790075Sobrien } 217818334Speter } 217918334Speter 218090075Sobrien /* Sanity check that we're now at the end of the list of tests. */ 2181169689Skan gcc_assert (!test->next); 218218334Speter 218390075Sobrien if (test->type == DT_accept_insn) 218490075Sobrien { 218590075Sobrien switch (subroutine_type) 218690075Sobrien { 218790075Sobrien case RECOG: 218890075Sobrien if (test->u.insn.num_clobbers_to_add != 0) 218990075Sobrien printf ("%s*pnum_clobbers = %d;\n", 219090075Sobrien indent, test->u.insn.num_clobbers_to_add); 2191169689Skan printf ("%sreturn %d; /* %s */\n", indent, 2192169689Skan test->u.insn.code_number, 2193169689Skan get_insn_name (test->u.insn.code_number)); 219490075Sobrien break; 219518334Speter 219690075Sobrien case SPLIT: 2197169689Skan printf ("%sreturn gen_split_%d (insn, operands);\n", 219890075Sobrien indent, test->u.insn.code_number); 219990075Sobrien break; 220090075Sobrien 220190075Sobrien case PEEPHOLE2: 220290075Sobrien { 220390075Sobrien int match_len = 0, i; 220490075Sobrien 220590075Sobrien for (i = strlen (p->position) - 1; i >= 0; --i) 220690075Sobrien if (ISUPPER (p->position[i])) 220790075Sobrien { 220890075Sobrien match_len = p->position[i] - 'A'; 220990075Sobrien break; 221090075Sobrien } 221190075Sobrien printf ("%s*_pmatch_len = %d;\n", indent, match_len); 221290075Sobrien printf ("%stem = gen_peephole2_%d (insn, operands);\n", 221390075Sobrien indent, test->u.insn.code_number); 221490075Sobrien printf ("%sif (tem != 0)\n%s return tem;\n", indent, indent); 221590075Sobrien } 221690075Sobrien break; 221790075Sobrien 221890075Sobrien default: 2219169689Skan gcc_unreachable (); 222090075Sobrien } 222118334Speter } 222218334Speter else 222318334Speter { 222490075Sobrien printf("%sgoto L%d;\n", indent, success->number); 222590075Sobrien success->need_label = 1; 222618334Speter } 222790075Sobrien 222890075Sobrien if (want_close) 222990075Sobrien fputs (" }\n", stdout); 223018334Speter} 223118334Speter 223290075Sobrien/* Return 1 if the test is always true and has no fallthru path. Return -1 223390075Sobrien if the test does have a fallthru path, but requires that the condition be 223490075Sobrien terminated. Otherwise return 0 for a normal test. */ 223590075Sobrien/* ??? is_unconditional is a stupid name for a tri-state function. */ 223690075Sobrien 223718334Speterstatic int 2238132718Skanis_unconditional (struct decision_test *t, enum routine_type subroutine_type) 223918334Speter{ 224090075Sobrien if (t->type == DT_accept_op) 224190075Sobrien return 1; 224218334Speter 224390075Sobrien if (t->type == DT_accept_insn) 224490075Sobrien { 224590075Sobrien switch (subroutine_type) 224690075Sobrien { 224790075Sobrien case RECOG: 224890075Sobrien return (t->u.insn.num_clobbers_to_add == 0); 224990075Sobrien case SPLIT: 225090075Sobrien return 1; 225190075Sobrien case PEEPHOLE2: 225290075Sobrien return -1; 225390075Sobrien default: 2254169689Skan gcc_unreachable (); 225590075Sobrien } 225690075Sobrien } 225718334Speter 225890075Sobrien return 0; 225918334Speter} 226018334Speter 226190075Sobrien/* Emit code for one node -- the conditional and the accompanying action. 226290075Sobrien Return true if there is no fallthru path. */ 226390075Sobrien 226418334Speterstatic int 2265132718Skanwrite_node (struct decision *p, int depth, 2266132718Skan enum routine_type subroutine_type) 226718334Speter{ 226890075Sobrien struct decision_test *test, *last_test; 226990075Sobrien int uncond; 227018334Speter 2271169689Skan /* Scan the tests and simplify comparisons against small 2272169689Skan constants. */ 2273169689Skan for (test = p->tests; test; test = test->next) 2274169689Skan { 2275169689Skan if (test->type == DT_code 2276169689Skan && test->u.code == CONST_INT 2277169689Skan && test->next 2278169689Skan && test->next->type == DT_elt_zero_wide_safe 2279169689Skan && -MAX_SAVED_CONST_INT <= test->next->u.intval 2280169689Skan && test->next->u.intval <= MAX_SAVED_CONST_INT) 2281169689Skan { 2282169689Skan test->type = DT_const_int; 2283169689Skan test->u.intval = test->next->u.intval; 2284169689Skan test->next = test->next->next; 2285169689Skan } 2286169689Skan } 2287169689Skan 228890075Sobrien last_test = test = p->tests; 228990075Sobrien uncond = is_unconditional (test, subroutine_type); 229090075Sobrien if (uncond == 0) 229190075Sobrien { 229290075Sobrien printf (" if ("); 229390075Sobrien write_cond (test, depth, subroutine_type); 229490075Sobrien 229590075Sobrien while ((test = test->next) != NULL) 229690075Sobrien { 229790075Sobrien last_test = test; 2298169689Skan if (is_unconditional (test, subroutine_type)) 229990075Sobrien break; 230090075Sobrien 230190075Sobrien printf ("\n && "); 230290075Sobrien write_cond (test, depth, subroutine_type); 230390075Sobrien } 230490075Sobrien 230590075Sobrien printf (")\n"); 230690075Sobrien } 230790075Sobrien 230890075Sobrien write_action (p, last_test, depth, uncond, p->success.first, subroutine_type); 230990075Sobrien 231090075Sobrien return uncond > 0; 231118334Speter} 231218334Speter 231390075Sobrien/* Emit code for all of the sibling nodes of HEAD. */ 231490075Sobrien 231518334Speterstatic void 2316132718Skanwrite_tree_1 (struct decision_head *head, int depth, 2317132718Skan enum routine_type subroutine_type) 231818334Speter{ 231990075Sobrien struct decision *p, *next; 232090075Sobrien int uncond = 0; 232118334Speter 232290075Sobrien for (p = head->first; p ; p = next) 232390075Sobrien { 232490075Sobrien /* The label for the first element was printed in write_tree. */ 232590075Sobrien if (p != head->first && p->need_label) 232690075Sobrien OUTPUT_LABEL (" ", p->number); 232718334Speter 232890075Sobrien /* Attempt to write a switch statement for a whole sequence. */ 232990075Sobrien next = write_switch (p, depth); 233090075Sobrien if (p != next) 233190075Sobrien uncond = 0; 233290075Sobrien else 233390075Sobrien { 233490075Sobrien /* Failed -- fall back and write one node. */ 233590075Sobrien uncond = write_node (p, depth, subroutine_type); 233690075Sobrien next = p->next; 233790075Sobrien } 233890075Sobrien } 233918334Speter 234090075Sobrien /* Finished with this chain. Close a fallthru path by branching 234190075Sobrien to the afterward node. */ 234290075Sobrien if (! uncond) 234390075Sobrien write_afterward (head->last, head->last->afterward, " "); 234490075Sobrien} 234518334Speter 234690075Sobrien/* Write out the decision tree starting at HEAD. PREVPOS is the 234790075Sobrien position at the node that branched to this node. */ 234890075Sobrien 234918334Speterstatic void 2350132718Skanwrite_tree (struct decision_head *head, const char *prevpos, 2351132718Skan enum routine_type type, int initial) 235218334Speter{ 235390075Sobrien struct decision *p = head->first; 235418334Speter 235590075Sobrien putchar ('\n'); 235690075Sobrien if (p->need_label) 235790075Sobrien OUTPUT_LABEL (" ", p->number); 235890075Sobrien 235990075Sobrien if (! initial && p->subroutine_number > 0) 236018334Speter { 236190075Sobrien static const char * const name_prefix[] = { 236290075Sobrien "recog", "split", "peephole2" 236390075Sobrien }; 236418334Speter 236590075Sobrien static const char * const call_suffix[] = { 236690075Sobrien ", pnum_clobbers", "", ", _pmatch_len" 236790075Sobrien }; 236890075Sobrien 236990075Sobrien /* This node has been broken out into a separate subroutine. 237090075Sobrien Call it, test the result, and branch accordingly. */ 237190075Sobrien 237290075Sobrien if (p->afterward) 237318334Speter { 237418334Speter printf (" tem = %s_%d (x0, insn%s);\n", 237590075Sobrien name_prefix[type], p->subroutine_number, call_suffix[type]); 237690075Sobrien if (IS_SPLIT (type)) 237790075Sobrien printf (" if (tem != 0)\n return tem;\n"); 237818334Speter else 237990075Sobrien printf (" if (tem >= 0)\n return tem;\n"); 238090075Sobrien 2381169689Skan change_state (p->position, p->afterward->position, " "); 238290075Sobrien printf (" goto L%d;\n", p->afterward->number); 238318334Speter } 238418334Speter else 238590075Sobrien { 238690075Sobrien printf (" return %s_%d (x0, insn%s);\n", 238790075Sobrien name_prefix[type], p->subroutine_number, call_suffix[type]); 238890075Sobrien } 238918334Speter } 239090075Sobrien else 239190075Sobrien { 239290075Sobrien int depth = strlen (p->position); 239318334Speter 2394169689Skan change_state (prevpos, p->position, " "); 239590075Sobrien write_tree_1 (head, depth, type); 239618334Speter 239790075Sobrien for (p = head->first; p; p = p->next) 239890075Sobrien if (p->success.first) 239990075Sobrien write_tree (&p->success, p->position, type, 0); 240090075Sobrien } 240118334Speter} 240218334Speter 240390075Sobrien/* Write out a subroutine of type TYPE to do comparisons starting at 240490075Sobrien node TREE. */ 240518334Speter 240618334Speterstatic void 2407132718Skanwrite_subroutine (struct decision_head *head, enum routine_type type) 240818334Speter{ 240990075Sobrien int subfunction = head->first ? head->first->subroutine_number : 0; 241090075Sobrien const char *s_or_e; 241190075Sobrien char extension[32]; 241290075Sobrien int i; 241318334Speter 241490075Sobrien s_or_e = subfunction ? "static " : ""; 241518334Speter 241690075Sobrien if (subfunction) 241790075Sobrien sprintf (extension, "_%d", subfunction); 241890075Sobrien else if (type == RECOG) 241990075Sobrien extension[0] = '\0'; 242090075Sobrien else 242190075Sobrien strcpy (extension, "_insns"); 242218334Speter 242390075Sobrien switch (type) 242418334Speter { 242590075Sobrien case RECOG: 242690075Sobrien printf ("%sint\n\ 2427132718Skanrecog%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n", s_or_e, extension); 242890075Sobrien break; 242990075Sobrien case SPLIT: 243090075Sobrien printf ("%srtx\n\ 2431132718Skansplit%s (rtx x0 ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED)\n", 2432132718Skan s_or_e, extension); 243390075Sobrien break; 243490075Sobrien case PEEPHOLE2: 2435132718Skan printf ("%srtx\n\ 2436132718Skanpeephole2%s (rtx x0 ATTRIBUTE_UNUSED,\n\trtx insn ATTRIBUTE_UNUSED,\n\tint *_pmatch_len ATTRIBUTE_UNUSED)\n", 243790075Sobrien s_or_e, extension); 243890075Sobrien break; 243918334Speter } 244090075Sobrien 244190075Sobrien printf ("{\n rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n"); 244290075Sobrien for (i = 1; i <= max_depth; i++) 244390075Sobrien printf (" rtx x%d ATTRIBUTE_UNUSED;\n", i); 244490075Sobrien 244590075Sobrien printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int"); 244690075Sobrien 244790075Sobrien if (!subfunction) 244890075Sobrien printf (" recog_data.insn = NULL_RTX;\n"); 244990075Sobrien 245090075Sobrien if (head->first) 245190075Sobrien write_tree (head, "", type, 1); 245290075Sobrien else 245390075Sobrien printf (" goto ret0;\n"); 245490075Sobrien 245590075Sobrien printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1); 245618334Speter} 245790075Sobrien 245890075Sobrien/* In break_out_subroutines, we discovered the boundaries for the 245990075Sobrien subroutines, but did not write them out. Do so now. */ 246090075Sobrien 246190075Sobrienstatic void 2462132718Skanwrite_subroutines (struct decision_head *head, enum routine_type type) 246318334Speter{ 246490075Sobrien struct decision *p; 246590075Sobrien 246690075Sobrien for (p = head->first; p ; p = p->next) 246790075Sobrien if (p->success.first) 246890075Sobrien write_subroutines (&p->success, type); 246990075Sobrien 247090075Sobrien if (head->first->subroutine_number > 0) 247190075Sobrien write_subroutine (head, type); 247218334Speter} 247318334Speter 247490075Sobrien/* Begin the output file. */ 247590075Sobrien 247690075Sobrienstatic void 2477132718Skanwrite_header (void) 247818334Speter{ 247990075Sobrien puts ("\ 248090075Sobrien/* Generated automatically by the program `genrecog' from the target\n\ 248190075Sobrien machine description file. */\n\ 248290075Sobrien\n\ 248390075Sobrien#include \"config.h\"\n\ 248490075Sobrien#include \"system.h\"\n\ 2485132718Skan#include \"coretypes.h\"\n\ 2486132718Skan#include \"tm.h\"\n\ 248790075Sobrien#include \"rtl.h\"\n\ 248890075Sobrien#include \"tm_p.h\"\n\ 248990075Sobrien#include \"function.h\"\n\ 249090075Sobrien#include \"insn-config.h\"\n\ 249190075Sobrien#include \"recog.h\"\n\ 249290075Sobrien#include \"real.h\"\n\ 249390075Sobrien#include \"output.h\"\n\ 249490075Sobrien#include \"flags.h\"\n\ 249590075Sobrien#include \"hard-reg-set.h\"\n\ 249690075Sobrien#include \"resource.h\"\n\ 249790075Sobrien#include \"toplev.h\"\n\ 249890075Sobrien#include \"reload.h\"\n\ 2499169689Skan#include \"tm-constrs.h\"\n\ 250090075Sobrien\n"); 250190075Sobrien 250290075Sobrien puts ("\n\ 250390075Sobrien/* `recog' contains a decision tree that recognizes whether the rtx\n\ 250490075Sobrien X0 is a valid instruction.\n\ 250590075Sobrien\n\ 250690075Sobrien recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\ 250790075Sobrien returns a nonnegative number which is the insn code number for the\n\ 250890075Sobrien pattern that matched. This is the same as the order in the machine\n\ 250990075Sobrien description of the entry that matched. This number can be used as an\n\ 251090075Sobrien index into `insn_data' and other tables.\n"); 251190075Sobrien puts ("\ 251290075Sobrien The third argument to recog is an optional pointer to an int. If\n\ 251390075Sobrien present, recog will accept a pattern if it matches except for missing\n\ 251490075Sobrien CLOBBER expressions at the end. In that case, the value pointed to by\n\ 251590075Sobrien the optional pointer will be set to the number of CLOBBERs that need\n\ 251690075Sobrien to be added (it should be initialized to zero by the caller). If it"); 251790075Sobrien puts ("\ 251890075Sobrien is set nonzero, the caller should allocate a PARALLEL of the\n\ 251990075Sobrien appropriate size, copy the initial entries, and call add_clobbers\n\ 252090075Sobrien (found in insn-emit.c) to fill in the CLOBBERs.\n\ 252190075Sobrien"); 252290075Sobrien 252390075Sobrien puts ("\n\ 252490075Sobrien The function split_insns returns 0 if the rtl could not\n\ 2525117395Skan be split or the split rtl as an INSN list if it can be.\n\ 252690075Sobrien\n\ 252790075Sobrien The function peephole2_insns returns 0 if the rtl could not\n\ 2528117395Skan be matched. If there was a match, the new rtl is returned in an INSN list,\n\ 252990075Sobrien and LAST_INSN will point to the last recognized insn in the old sequence.\n\ 253090075Sobrien*/\n\n"); 253118334Speter} 253218334Speter 253390075Sobrien 253490075Sobrien/* Construct and return a sequence of decisions 253590075Sobrien that will recognize INSN. 253690075Sobrien 253790075Sobrien TYPE says what type of routine we are recognizing (RECOG or SPLIT). */ 253890075Sobrien 253990075Sobrienstatic struct decision_head 2540132718Skanmake_insn_sequence (rtx insn, enum routine_type type) 254118334Speter{ 254290075Sobrien rtx x; 254390075Sobrien const char *c_test = XSTR (insn, type == RECOG ? 2 : 1); 2544117395Skan int truth = maybe_eval_c_test (c_test); 254590075Sobrien struct decision *last; 254690075Sobrien struct decision_test *test, **place; 254790075Sobrien struct decision_head head; 254890075Sobrien char c_test_pos[2]; 254918334Speter 2550117395Skan /* We should never see an insn whose C test is false at compile time. */ 2551169689Skan gcc_assert (truth); 2552117395Skan 255390075Sobrien c_test_pos[0] = '\0'; 255490075Sobrien if (type == PEEPHOLE2) 255590075Sobrien { 255690075Sobrien int i, j; 255790075Sobrien 255890075Sobrien /* peephole2 gets special treatment: 255990075Sobrien - X always gets an outer parallel even if it's only one entry 256090075Sobrien - we remove all traces of outer-level match_scratch and match_dup 256190075Sobrien expressions here. */ 256290075Sobrien x = rtx_alloc (PARALLEL); 256390075Sobrien PUT_MODE (x, VOIDmode); 256490075Sobrien XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0)); 256590075Sobrien for (i = j = 0; i < XVECLEN (insn, 0); i++) 256690075Sobrien { 256790075Sobrien rtx tmp = XVECEXP (insn, 0, i); 256890075Sobrien if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP) 256990075Sobrien { 257090075Sobrien XVECEXP (x, 0, j) = tmp; 257190075Sobrien j++; 257290075Sobrien } 257390075Sobrien } 257490075Sobrien XVECLEN (x, 0) = j; 257590075Sobrien 257690075Sobrien c_test_pos[0] = 'A' + j - 1; 257790075Sobrien c_test_pos[1] = '\0'; 257890075Sobrien } 257990075Sobrien else if (XVECLEN (insn, type == RECOG) == 1) 258090075Sobrien x = XVECEXP (insn, type == RECOG, 0); 258190075Sobrien else 258290075Sobrien { 258390075Sobrien x = rtx_alloc (PARALLEL); 258490075Sobrien XVEC (x, 0) = XVEC (insn, type == RECOG); 258590075Sobrien PUT_MODE (x, VOIDmode); 258690075Sobrien } 258790075Sobrien 258890075Sobrien validate_pattern (x, insn, NULL_RTX, 0); 258990075Sobrien 259090075Sobrien memset(&head, 0, sizeof(head)); 259190075Sobrien last = add_to_sequence (x, &head, "", type, 1); 259290075Sobrien 259390075Sobrien /* Find the end of the test chain on the last node. */ 259490075Sobrien for (test = last->tests; test->next; test = test->next) 259590075Sobrien continue; 259690075Sobrien place = &test->next; 259790075Sobrien 2598117395Skan /* Skip the C test if it's known to be true at compile time. */ 2599117395Skan if (truth == -1) 260090075Sobrien { 260190075Sobrien /* Need a new node if we have another test to add. */ 260290075Sobrien if (test->type == DT_accept_op) 260390075Sobrien { 260490075Sobrien last = new_decision (c_test_pos, &last->success); 260590075Sobrien place = &last->tests; 260690075Sobrien } 260790075Sobrien test = new_decision_test (DT_c_test, &place); 260890075Sobrien test->u.c_test = c_test; 260990075Sobrien } 261090075Sobrien 261190075Sobrien test = new_decision_test (DT_accept_insn, &place); 261290075Sobrien test->u.insn.code_number = next_insn_code; 261390075Sobrien test->u.insn.lineno = pattern_lineno; 261490075Sobrien test->u.insn.num_clobbers_to_add = 0; 261590075Sobrien 261690075Sobrien switch (type) 261790075Sobrien { 261890075Sobrien case RECOG: 2619132718Skan /* If this is a DEFINE_INSN and X is a PARALLEL, see if it ends 262090075Sobrien with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes. 262190075Sobrien If so, set up to recognize the pattern without these CLOBBERs. */ 262290075Sobrien 262390075Sobrien if (GET_CODE (x) == PARALLEL) 262490075Sobrien { 262590075Sobrien int i; 262690075Sobrien 262790075Sobrien /* Find the last non-clobber in the parallel. */ 262890075Sobrien for (i = XVECLEN (x, 0); i > 0; i--) 262990075Sobrien { 263090075Sobrien rtx y = XVECEXP (x, 0, i - 1); 263190075Sobrien if (GET_CODE (y) != CLOBBER 2632169689Skan || (!REG_P (XEXP (y, 0)) 263390075Sobrien && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH)) 263490075Sobrien break; 263590075Sobrien } 263690075Sobrien 263790075Sobrien if (i != XVECLEN (x, 0)) 263890075Sobrien { 263990075Sobrien rtx new; 264090075Sobrien struct decision_head clobber_head; 264190075Sobrien 264290075Sobrien /* Build a similar insn without the clobbers. */ 264390075Sobrien if (i == 1) 264490075Sobrien new = XVECEXP (x, 0, 0); 264590075Sobrien else 264690075Sobrien { 264790075Sobrien int j; 264890075Sobrien 264990075Sobrien new = rtx_alloc (PARALLEL); 265090075Sobrien XVEC (new, 0) = rtvec_alloc (i); 265190075Sobrien for (j = i - 1; j >= 0; j--) 265290075Sobrien XVECEXP (new, 0, j) = XVECEXP (x, 0, j); 265390075Sobrien } 265490075Sobrien 265590075Sobrien /* Recognize it. */ 265690075Sobrien memset (&clobber_head, 0, sizeof(clobber_head)); 265790075Sobrien last = add_to_sequence (new, &clobber_head, "", type, 1); 265890075Sobrien 265990075Sobrien /* Find the end of the test chain on the last node. */ 266090075Sobrien for (test = last->tests; test->next; test = test->next) 266190075Sobrien continue; 266290075Sobrien 266390075Sobrien /* We definitely have a new test to add -- create a new 266490075Sobrien node if needed. */ 266590075Sobrien place = &test->next; 266690075Sobrien if (test->type == DT_accept_op) 266790075Sobrien { 266890075Sobrien last = new_decision ("", &last->success); 266990075Sobrien place = &last->tests; 267090075Sobrien } 267190075Sobrien 2672117395Skan /* Skip the C test if it's known to be true at compile 2673117395Skan time. */ 2674117395Skan if (truth == -1) 267590075Sobrien { 267690075Sobrien test = new_decision_test (DT_c_test, &place); 267790075Sobrien test->u.c_test = c_test; 267890075Sobrien } 267990075Sobrien 268090075Sobrien test = new_decision_test (DT_accept_insn, &place); 268190075Sobrien test->u.insn.code_number = next_insn_code; 268290075Sobrien test->u.insn.lineno = pattern_lineno; 268390075Sobrien test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i; 268490075Sobrien 268590075Sobrien merge_trees (&head, &clobber_head); 268690075Sobrien } 268790075Sobrien } 268890075Sobrien break; 268990075Sobrien 269090075Sobrien case SPLIT: 269190075Sobrien /* Define the subroutine we will call below and emit in genemit. */ 2692169689Skan printf ("extern rtx gen_split_%d (rtx, rtx *);\n", next_insn_code); 269390075Sobrien break; 269490075Sobrien 269590075Sobrien case PEEPHOLE2: 269690075Sobrien /* Define the subroutine we will call below and emit in genemit. */ 2697132718Skan printf ("extern rtx gen_peephole2_%d (rtx, rtx *);\n", 269890075Sobrien next_insn_code); 269990075Sobrien break; 270090075Sobrien } 270190075Sobrien 270290075Sobrien return head; 270318334Speter} 270418334Speter 270590075Sobrienstatic void 2706132718Skanprocess_tree (struct decision_head *head, enum routine_type subroutine_type) 270718334Speter{ 270890075Sobrien if (head->first == NULL) 270990075Sobrien { 271090075Sobrien /* We can elide peephole2_insns, but not recog or split_insns. */ 271190075Sobrien if (subroutine_type == PEEPHOLE2) 271290075Sobrien return; 271390075Sobrien } 271490075Sobrien else 271590075Sobrien { 271690075Sobrien factor_tests (head); 271750397Sobrien 271890075Sobrien next_subroutine_number = 0; 271990075Sobrien break_out_subroutines (head, 1); 272090075Sobrien find_afterward (head, NULL); 272150397Sobrien 272290075Sobrien /* We run this after find_afterward, because find_afterward needs 272390075Sobrien the redundant DT_mode tests on predicates to determine whether 272490075Sobrien two tests can both be true or not. */ 272590075Sobrien simplify_tests(head); 272650397Sobrien 272790075Sobrien write_subroutines (head, subroutine_type); 272890075Sobrien } 272918334Speter 273090075Sobrien write_subroutine (head, subroutine_type); 273118334Speter} 273218334Speter 2733132718Skanextern int main (int, char **); 273490075Sobrien 273518334Speterint 2736132718Skanmain (int argc, char **argv) 273718334Speter{ 273818334Speter rtx desc; 273990075Sobrien struct decision_head recog_tree, split_tree, peephole2_tree, h; 274018334Speter 274190075Sobrien progname = "genrecog"; 274218334Speter 274390075Sobrien memset (&recog_tree, 0, sizeof recog_tree); 274490075Sobrien memset (&split_tree, 0, sizeof split_tree); 274590075Sobrien memset (&peephole2_tree, 0, sizeof peephole2_tree); 274690075Sobrien 274790075Sobrien if (init_md_reader_args (argc, argv) != SUCCESS_EXIT_CODE) 274890075Sobrien return (FATAL_EXIT_CODE); 274918334Speter 275018334Speter next_insn_code = 0; 275118334Speter 275290075Sobrien write_header (); 275318334Speter 275418334Speter /* Read the machine description. */ 275518334Speter 275618334Speter while (1) 275718334Speter { 275890075Sobrien desc = read_md_rtx (&pattern_lineno, &next_insn_code); 275990075Sobrien if (desc == NULL) 276018334Speter break; 276118334Speter 2762169689Skan switch (GET_CODE (desc)) 276390075Sobrien { 2764169689Skan case DEFINE_PREDICATE: 2765169689Skan case DEFINE_SPECIAL_PREDICATE: 2766169689Skan process_define_predicate (desc); 2767169689Skan break; 2768169689Skan 2769169689Skan case DEFINE_INSN: 277090075Sobrien h = make_insn_sequence (desc, RECOG); 277190075Sobrien merge_trees (&recog_tree, &h); 2772169689Skan break; 2773169689Skan 2774169689Skan case DEFINE_SPLIT: 277590075Sobrien h = make_insn_sequence (desc, SPLIT); 277690075Sobrien merge_trees (&split_tree, &h); 2777169689Skan break; 2778169689Skan 2779169689Skan case DEFINE_PEEPHOLE2: 278090075Sobrien h = make_insn_sequence (desc, PEEPHOLE2); 278190075Sobrien merge_trees (&peephole2_tree, &h); 2782169689Skan 2783169689Skan default: 2784169689Skan /* do nothing */; 278590075Sobrien } 278618334Speter } 278718334Speter 2788169689Skan if (error_count || have_error) 278990075Sobrien return FATAL_EXIT_CODE; 279018334Speter 279190075Sobrien puts ("\n\n"); 279218334Speter 279390075Sobrien process_tree (&recog_tree, RECOG); 279490075Sobrien process_tree (&split_tree, SPLIT); 279590075Sobrien process_tree (&peephole2_tree, PEEPHOLE2); 279618334Speter 279790075Sobrien fflush (stdout); 279890075Sobrien return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE); 279990075Sobrien} 280090075Sobrien 280190075Sobrienstatic void 2802132718Skandebug_decision_2 (struct decision_test *test) 280390075Sobrien{ 280490075Sobrien switch (test->type) 280590075Sobrien { 2806169689Skan case DT_num_insns: 2807169689Skan fprintf (stderr, "num_insns=%d", test->u.num_insns); 2808169689Skan break; 280990075Sobrien case DT_mode: 281090075Sobrien fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode)); 281190075Sobrien break; 281290075Sobrien case DT_code: 281390075Sobrien fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code)); 281490075Sobrien break; 281590075Sobrien case DT_veclen: 281690075Sobrien fprintf (stderr, "veclen=%d", test->u.veclen); 281790075Sobrien break; 281890075Sobrien case DT_elt_zero_int: 281990075Sobrien fprintf (stderr, "elt0_i=%d", (int) test->u.intval); 282090075Sobrien break; 282190075Sobrien case DT_elt_one_int: 282290075Sobrien fprintf (stderr, "elt1_i=%d", (int) test->u.intval); 282390075Sobrien break; 282490075Sobrien case DT_elt_zero_wide: 2825132718Skan fprintf (stderr, "elt0_w=" HOST_WIDE_INT_PRINT_DEC, test->u.intval); 282690075Sobrien break; 282790075Sobrien case DT_elt_zero_wide_safe: 2828132718Skan fprintf (stderr, "elt0_ws=" HOST_WIDE_INT_PRINT_DEC, test->u.intval); 282990075Sobrien break; 283090075Sobrien case DT_veclen_ge: 283190075Sobrien fprintf (stderr, "veclen>=%d", test->u.veclen); 283290075Sobrien break; 283390075Sobrien case DT_dup: 283490075Sobrien fprintf (stderr, "dup=%d", test->u.dup); 283590075Sobrien break; 283690075Sobrien case DT_pred: 283790075Sobrien fprintf (stderr, "pred=(%s,%s)", 283890075Sobrien test->u.pred.name, GET_MODE_NAME(test->u.pred.mode)); 283990075Sobrien break; 284090075Sobrien case DT_c_test: 284190075Sobrien { 284290075Sobrien char sub[16+4]; 284390075Sobrien strncpy (sub, test->u.c_test, sizeof(sub)); 284490075Sobrien memcpy (sub+16, "...", 4); 284590075Sobrien fprintf (stderr, "c_test=\"%s\"", sub); 284690075Sobrien } 284790075Sobrien break; 284890075Sobrien case DT_accept_op: 284990075Sobrien fprintf (stderr, "A_op=%d", test->u.opno); 285090075Sobrien break; 285190075Sobrien case DT_accept_insn: 285290075Sobrien fprintf (stderr, "A_insn=(%d,%d)", 285390075Sobrien test->u.insn.code_number, test->u.insn.num_clobbers_to_add); 285490075Sobrien break; 285590075Sobrien 285690075Sobrien default: 2857169689Skan gcc_unreachable (); 285890075Sobrien } 285990075Sobrien} 286090075Sobrien 286190075Sobrienstatic void 2862132718Skandebug_decision_1 (struct decision *d, int indent) 286390075Sobrien{ 286490075Sobrien int i; 286590075Sobrien struct decision_test *test; 286690075Sobrien 286790075Sobrien if (d == NULL) 286890075Sobrien { 286990075Sobrien for (i = 0; i < indent; ++i) 287090075Sobrien putc (' ', stderr); 287190075Sobrien fputs ("(nil)\n", stderr); 287290075Sobrien return; 287390075Sobrien } 287490075Sobrien 287590075Sobrien for (i = 0; i < indent; ++i) 287690075Sobrien putc (' ', stderr); 287790075Sobrien 287890075Sobrien putc ('{', stderr); 287990075Sobrien test = d->tests; 288090075Sobrien if (test) 288190075Sobrien { 288290075Sobrien debug_decision_2 (test); 288390075Sobrien while ((test = test->next) != NULL) 288490075Sobrien { 288590075Sobrien fputs (" + ", stderr); 288690075Sobrien debug_decision_2 (test); 288790075Sobrien } 288890075Sobrien } 288990075Sobrien fprintf (stderr, "} %d n %d a %d\n", d->number, 289090075Sobrien (d->next ? d->next->number : -1), 289190075Sobrien (d->afterward ? d->afterward->number : -1)); 289290075Sobrien} 289390075Sobrien 289490075Sobrienstatic void 2895132718Skandebug_decision_0 (struct decision *d, int indent, int maxdepth) 289690075Sobrien{ 289790075Sobrien struct decision *n; 289890075Sobrien int i; 289990075Sobrien 290090075Sobrien if (maxdepth < 0) 290190075Sobrien return; 290290075Sobrien if (d == NULL) 290390075Sobrien { 290490075Sobrien for (i = 0; i < indent; ++i) 290590075Sobrien putc (' ', stderr); 290690075Sobrien fputs ("(nil)\n", stderr); 290790075Sobrien return; 290890075Sobrien } 290990075Sobrien 291090075Sobrien debug_decision_1 (d, indent); 291190075Sobrien for (n = d->success.first; n ; n = n->next) 291290075Sobrien debug_decision_0 (n, indent + 2, maxdepth - 1); 291390075Sobrien} 291490075Sobrien 291590075Sobrienvoid 2916132718Skandebug_decision (struct decision *d) 291790075Sobrien{ 291890075Sobrien debug_decision_0 (d, 0, 1000000); 291990075Sobrien} 292090075Sobrien 292190075Sobrienvoid 2922132718Skandebug_decision_list (struct decision *d) 292390075Sobrien{ 292490075Sobrien while (d) 292590075Sobrien { 292690075Sobrien debug_decision_0 (d, 0, 0); 292790075Sobrien d = d->next; 292890075Sobrien } 292990075Sobrien} 2930