gcc/genrecog.c

   1 /* Generate code from machine description to recognize rtl as insns.
   2    Copyright (C) 1987-1991 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19
  20
  21 /* This program is used to produce insn-recog.c, which contains
  22    a function called `recog' plus its subroutines.
  23    These functions contain a decision tree
  24    that recognizes whether an rtx, the argument given to recog,
  25    is a valid instruction.
  26
  27    recog returns -1 if the rtx is not valid.
  28    If the rtx is valid, recog returns a nonnegative number
  29    which is the insn code number for the pattern that matched.
  30    This is the same as the order in the machine description of the
  31    entry that matched.  This number can be used as an index into various
  32    insn_* tables, such as insn_templates, insn_outfun, and insn_n_operands
  33    (found in insn-output.c).
  34
  35    The third argument to recog is an optional pointer to an int.
  36    If present, recog will accept a pattern if it matches except for
  37    missing CLOBBER expressions at the end.  In that case, the value
  38    pointed to by the optional pointer will be set to the number of
  39    CLOBBERs that need to be added (it should be initialized to zero by
  40    the caller).  If it is set nonzero, the caller should allocate a
  41    PARALLEL of the appropriate size, copy the initial entries, and call
  42    add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
  43
  44    This program also generates the function `split_insns',
  45    which returns 0 if the rtl could not be split, or
  46    it returns the split rtl in a SEQUENCE.  */
  47
  48 #include <stdio.h>
  49 #include "config.h"
  50 #include "rtl.h"
  51 #include "obstack.h"
  52
  53 static struct obstack obstack;
  54 struct obstack *rtl_obstack = &obstack;
  55
  56 #define obstack_chunk_alloc xmalloc
  57 #define obstack_chunk_free free
  58
  59 extern void free ();
  60
  61 /* Data structure for decision tree for recognizing
  62    legitimate instructions.  */
  63
  64 struct decision
  65 {
  66   int number;
  67   char *position;
  68   RTX_CODE code;
  69   char *exact;
  70   enum machine_mode mode;
  71   char *tests;
  72   int insn_code_number;
  73   int num_clobbers_to_add;
  74   struct decision *next;
  75   struct decision *success;
  76   int opno;
  77   int dupno;
  78   int test_elt_zero_int;
  79   int elt_zero_int;
  80   int test_elt_one_int;
  81   int elt_one_int;
  82   int ignmode;
  83   struct decision *afterward;
  84   int label_needed;
  85   char *c_test;
  86   char enforce_mode;
  87   int veclen;
  88   int subroutine_number;
  89   /* Used for DEFINE_SPLITs.  */
  90   char *c_hook;
  91   rtx split_sequence;
  92 };
  93
  94 #define SUBROUTINE_THRESHOLD 50
  95
  96 static int next_subroutine_number;
  97
  98 /* We can write two types of subroutines: One for insn recognition and
  99    one to split insns.  This defines which type is being written.  */
 100
 101 enum routine_type {RECOG, SPLIT};
 102
 103 static int try_merge_1 ();
 104 static int no_same_mode ();
 105 static int same_codes ();
 106 static int same_modes ();
 107
 108 /*
 109 static int
 110 recognize (top)
 111 {
 112  staten:
 113   x = XVECEXP (top, 0, 3);
 114   if (test_code (GET_CODE (x))
 115       && test_mode (MODE (x))
 116       && whatever_else)
 117     goto statep;
 118   else if (next one...)
 119     goto statem:
 120   goto stater;
 121
 122  statep:
 123   actions...;
 124   return 1;
 125
 126  statem:
 127   x = stack[depth--];
 128   more tests...;
 129
 130  stateq:
 131   stack[++depth] = x;
 132   x = XEXP (stack[depth], 0);
 133   more tests...;
 134
 135  stater:
 136   x = XEXP (stack[depth], 1);
 137 }
 138
 139 */
 140
 141 static int next_number;
 142
 143 static int next_insn_code;
 144
 145 static int next_index;
 146
 147 char *xmalloc ();
 148 static struct decision *add_to_sequence ();
 149 static struct decision *merge_trees ();
 150 static struct decision *try_merge_2 ();
 151 static void write_subroutine ();
 152 static void print_code ();
 153 static void clear_codes ();
 154 static void clear_modes ();
 155 static void change_state ();
 156 static void write_tree ();
 157 static char *copystr ();
 158 static char *concat ();
 159 static void fatal ();
 160 void fancy_abort ();
 161 static void mybzero ();
 162 \f
 163 static struct decision *first;
 164
 165 /* Construct and return a sequence of decisions
 166    that will recognize INSN.  */
 167
 168 static struct decision *
 169 make_insn_sequence (insn)
 170      rtx insn;
 171 {
 172   rtx x;
 173   char *c_test = XSTR (insn, 2);
 174   struct decision *last;
 175
 176   if (XVECLEN (insn, 1) == 1)
 177     x = XVECEXP (insn, 1, 0);
 178   else
 179     {
 180       x = rtx_alloc (PARALLEL);
 181       XVEC (x, 0) = XVEC (insn, 1);
 182       PUT_MODE (x, VOIDmode);
 183     }
 184
 185   last = add_to_sequence (x, 0, "");
 186
 187   if (c_test[0])
 188     last->c_test = c_test;
 189   last->insn_code_number = next_insn_code;
 190   last->num_clobbers_to_add = 0;
 191
 192   /* If X is a PARALLEL, see if it ends with a group of CLOBBERs of (hard)
 193      registers or MATCH_SCRATCHes.  If so, set up to recognize the pattern
 194      without these CLOBBERs.  */
 195
 196   if (GET_CODE (x) == PARALLEL)
 197     {
 198       int i;
 199
 200       for (i = XVECLEN (x, 0); i > 0; i--)
 201         if (GET_CODE (XVECEXP (x, 0, i - 1)) != CLOBBER
 202             || (GET_CODE (XEXP (XVECEXP (x, 0, i - 1), 0)) != REG
 203                 && GET_CODE (XEXP (XVECEXP (x, 0, i - 1), 0)) != MATCH_SCRATCH))
 204           break;
 205
 206       if (i != XVECLEN (x, 0))
 207         {
 208           rtx new;
 209           struct decision *previous_first = first;
 210
 211           if (i == 1)
 212             new = XVECEXP (x, 0, 0);
 213           else
 214             {
 215               int j;
 216
 217               new = rtx_alloc (PARALLEL);
 218               XVEC (new, 0) = rtvec_alloc (i);
 219               for (j = i - 1; j >= 0; j--)
 220                 XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
 221             }
 222
 223           last = add_to_sequence (new, 0, "");
 224
 225           if (c_test[0])
 226             last->c_test = c_test;
 227           last->insn_code_number = next_insn_code;
 228           last->num_clobbers_to_add = XVECLEN (x, 0) - i;
 229           first = merge_trees (previous_first, first);
 230         }
 231     }
 232
 233   next_insn_code++;
 234   return first;
 235 }
 236
 237 static struct decision *
 238 make_split_sequence (insn)
 239      rtx insn;
 240 {
 241   rtx x;
 242   char *c_test = XSTR (insn, 1);
 243   char *c_hook = XSTR (insn, 3);
 244   struct decision *last;
 245
 246   if (XVECLEN (insn, 0) == 1)
 247     x = XVECEXP (insn, 0, 0);
 248   else
 249     {
 250       x = rtx_alloc (PARALLEL);
 251       XVEC (x, 0) = XVEC (insn, 0);
 252       PUT_MODE (x, VOIDmode);
 253     }
 254
 255   last = add_to_sequence (x, 0, "");
 256
 257   if (c_test[0])
 258     last->c_test = c_test;
 259   if (c_hook != 0 && c_hook[0] != 0)
 260     last->c_hook = c_hook;
 261   last->split_sequence = XEXP (insn, 2);
 262   last->insn_code_number = next_insn_code++;
 263
 264   /* Define the subroutine we will call below and emit in genemit.  */
 265   printf ("extern rtx gen_split_%d ();\n", last->insn_code_number);
 266
 267   return first;
 268 }
 269
 270 static struct decision *
 271 add_to_sequence (pattern, last, position)
 272      rtx pattern;
 273      struct decision *last;
 274      char *position;
 275 {
 276   register RTX_CODE code;
 277   register struct decision *new
 278     = (struct decision *) xmalloc (sizeof (struct decision));
 279   struct decision *this;
 280   char *newpos;
 281   register char *fmt;
 282   register int i;
 283   int depth;
 284   int len;
 285
 286   new->number = next_number++;
 287   new->position = copystr (position);
 288   new->exact = 0;
 289   new->next = 0;
 290   new->success = 0;
 291   new->insn_code_number = -1;
 292   new->num_clobbers_to_add = 0;
 293   new->tests = 0;
 294   new->opno = -1;
 295   new->dupno = -1;
 296   new->test_elt_zero_int = 0;
 297   new->test_elt_one_int = 0;
 298   new->elt_zero_int = 0;
 299   new->elt_one_int = 0;
 300   new->enforce_mode = 0;
 301   new->ignmode = 0;
 302   new->afterward = 0;
 303   new->label_needed = 0;
 304   new->c_test = 0;
 305   new->c_hook = 0;
 306   new->split_sequence = 0;
 307   new->veclen = 0;
 308   new->subroutine_number = 0;
 309
 310   this = new;
 311
 312   if (last == 0)
 313     first = new;
 314   else
 315     last->success = new;
 316
 317   depth = strlen (position);
 318   newpos = (char *) alloca (depth + 2);
 319   strcpy (newpos, position);
 320   newpos[depth + 1] = 0;
 321
 322  restart:
 323
 324   if (pattern == 0)
 325     {
 326       new->exact = "0";
 327       new->code = UNKNOWN;
 328       new->mode = VOIDmode;
 329       return new;
 330     }
 331
 332   new->mode = GET_MODE (pattern);
 333   new->code = code = GET_CODE (pattern);
 334
 335   switch (code)
 336     {
 337     case MATCH_OPERAND:
 338       new->opno = XINT (pattern, 0);
 339       new->code = UNKNOWN;
 340       new->tests = XSTR (pattern, 1);
 341       if (*new->tests == 0)
 342         new->tests = 0;
 343       return new;
 344
 345     case MATCH_SCRATCH:
 346       new->opno = XINT (pattern, 0);
 347       new->code = UNKNOWN;
 348       new->tests = "scratch_operand";
 349       if (*new->tests == 0)
 350         new->tests = 0;
 351       return new;
 352
 353     case MATCH_OPERATOR:
 354       new->opno = XINT (pattern, 0);
 355       new->code = UNKNOWN;
 356       new->tests = XSTR (pattern, 1);
 357       if (*new->tests == 0)
 358         new->tests = 0;
 359       for (i = 0; i < XVECLEN (pattern, 2); i++)
 360         {
 361           newpos[depth] = i + '0';
 362           new = add_to_sequence (XVECEXP (pattern, 2, i), new, newpos);
 363         }
 364       this->success->enforce_mode = 0;
 365       return new;
 366
 367     case MATCH_PARALLEL:
 368       new->opno = XINT (pattern, 0);
 369       new->code = PARALLEL;
 370       new->tests = XSTR (pattern, 1);
 371       if (*new->tests == 0)
 372         new->tests = 0;
 373       for (i = 0; i < XVECLEN (pattern, 2); i++)
 374         {
 375           newpos[depth] = i + 'a';
 376           new = add_to_sequence (XVECEXP (pattern, 2, i), new, newpos);
 377         }
 378       this->success->enforce_mode = 0;
 379       return new;
 380
 381     case MATCH_OP_DUP:
 382       new->opno = XINT (pattern, 0);
 383       new->dupno = XINT (pattern, 0);
 384       new->code = UNKNOWN;
 385       new->tests = 0;
 386       for (i = 0; i < XVECLEN (pattern, 1); i++)
 387         {
 388           newpos[depth] = i + '0';
 389           new = add_to_sequence (XVECEXP (pattern, 1, i), new, newpos);
 390         }
 391       this->success->enforce_mode = 0;
 392       return new;
 393
 394     case MATCH_DUP:
 395       new->dupno = XINT (pattern, 0);
 396       new->code = UNKNOWN;
 397       return new;
 398
 399     case ADDRESS:
 400       pattern = XEXP (pattern, 0);
 401       goto restart;
 402
 403     case PC:
 404       new->exact = "pc_rtx";
 405       return new;
 406
 407     case CC0:
 408       new->exact = "cc0_rtx";
 409       return new;
 410
 411     case CONST_INT:
 412       if (INTVAL (pattern) == 0)
 413         {
 414           new->exact = "const0_rtx";
 415           return new;
 416         }
 417       if (INTVAL (pattern) == 1)
 418         {
 419           new->exact = "const1_rtx";
 420           return new;
 421         }
 422       if (INTVAL (pattern) == -1)
 423         {
 424           new->exact = "constm1_rtx";
 425           return new;
 426         }
 427       if (INTVAL (pattern) == STORE_FLAG_VALUE)
 428         {
 429           new->exact = "const_true_rtx";
 430           return new;
 431         }
 432       break;
 433
 434     case SET:
 435       newpos[depth] = '0';
 436       new = add_to_sequence (SET_DEST (pattern), new, newpos);
 437       this->success->enforce_mode = 1;
 438       newpos[depth] = '1';
 439       new = add_to_sequence (SET_SRC (pattern), new, newpos);
 440       return new;
 441
 442     case STRICT_LOW_PART:
 443       newpos[depth] = '0';
 444       new = add_to_sequence (XEXP (pattern, 0), new, newpos);
 445       this->success->enforce_mode = 1;
 446       return new;
 447
 448     case SUBREG:
 449       this->test_elt_one_int = 1;
 450       this->elt_one_int = XINT (pattern, 1);
 451       newpos[depth] = '0';
 452       new = add_to_sequence (XEXP (pattern, 0), new, newpos);
 453       this->success->enforce_mode = 1;
 454       return new;
 455
 456     case ZERO_EXTRACT:
 457     case SIGN_EXTRACT:
 458       newpos[depth] = '0';
 459       new = add_to_sequence (XEXP (pattern, 0), new, newpos);
 460       this->success->enforce_mode = 1;
 461       newpos[depth] = '1';
 462       new = add_to_sequence (XEXP (pattern, 1), new, newpos);
 463       newpos[depth] = '2';
 464       new = add_to_sequence (XEXP (pattern, 2), new, newpos);
 465       return new;
 466     }
 467
 468   fmt = GET_RTX_FORMAT (code);
 469   len = GET_RTX_LENGTH (code);
 470   for (i = 0; i < len; i++)
 471     {
 472       newpos[depth] = '0' + i;
 473       if (fmt[i] == 'e' || fmt[i] == 'u')
 474         new = add_to_sequence (XEXP (pattern, i), new, newpos);
 475       else if (fmt[i] == 'i' && i == 0)
 476         {
 477           this->test_elt_zero_int = 1;
 478           this->elt_zero_int = XINT (pattern, i);
 479         }
 480       else if (fmt[i] == 'i' && i == 1)
 481         {
 482           this->test_elt_one_int = 1;
 483           this->elt_one_int = XINT (pattern, i);
 484         }
 485       else if (fmt[i] == 'E')
 486         {
 487           register int j;
 488           /* We do not handle a vector appearing as other than
 489              the first item, just because nothing uses them
 490              and by handling only the special case
 491              we can use one element in newpos for either
 492              the item number of a subexpression
 493              or the element number in a vector.  */
 494           if (i != 0)
 495             abort ();
 496           this->veclen = XVECLEN (pattern, i);
 497           for (j = 0; j < XVECLEN (pattern, i); j++)
 498             {
 499               newpos[depth] = 'a' + j;
 500               new = add_to_sequence (XVECEXP (pattern, i, j),
 501                                      new, newpos);
 502             }
 503         }
 504       else if (fmt[i] != '0')
 505         abort ();
 506     }
 507   return new;
 508 }
 509
 510 /* Merge two decision trees OLD and ADD,
 511    modifying OLD destructively,
 512    and return the merged tree.  */
 513
 514 static struct decision *
 515 merge_trees (old, add)
 516      register struct decision *old, *add;
 517 {
 518   while (add)
 519     {
 520       register struct decision *next = add->next;
 521       add->next = 0;
 522       if (!try_merge_1 (old, add))
 523         old = try_merge_2 (old, add);
 524       add = next;
 525     }
 526   return old;
 527 }
 528
 529 /* Merge ADD into the next-chain starting with OLD
 530    only if it overlaps a condition already tested in OLD.
 531    Returns 1 if successful (OLD is modified),
 532    0 if nothing has been done.  */
 533
 534 static int
 535 try_merge_1 (old, add)
 536      register struct decision *old, *add;
 537 {
 538   while (old)
 539     {
 540       if ((old->position == add->position
 541            || (old->position && add->position
 542                && !strcmp (old->position, add->position)))
 543           && (old->tests == add->tests
 544               || (old->tests && add->tests && !strcmp (old->tests, add->tests)))
 545           && (old->c_test == add->c_test
 546               || (old->c_test && add->c_test && !strcmp (old->c_test, add->c_test)))
 547           && (old->c_hook == add->c_hook
 548               || (old->c_hook && add->c_hook && !strcmp (old->c_hook, add->c_hook)))
 549           && old->test_elt_zero_int == add->test_elt_zero_int
 550           && old->elt_zero_int == add->elt_zero_int
 551           && old->test_elt_one_int == add->test_elt_one_int
 552           && old->elt_one_int == add->elt_one_int
 553           && old->veclen == add->veclen
 554           && old->dupno == add->dupno
 555           && old->opno == add->opno
 556 /* In a collection of nodes that don't have predicates,
 557    we can always merge a new one with any node that matches it.
 558    This is because we know that two different nodes can't possibly match
 559    the same RTL object.  So we can reorder the tests to simplify the
 560    whole collection of them.
 561
 562    But when predicates are involved, we have to preserve the order of
 563    testing them.  This means that a new node can only be merged with the
 564    last existing node.
 565
 566    enforce_mode indicates that at this level each of the nodes
 567    requires a particular mode.  When this is true, then we know
 568    that two nodes with different modes can't possibly both match.
 569    Therefore, it is ok to merge a new node with the last node
 570    that wants the same mode, even if other nodes for different modes
 571    appear after it.  no_same_mode tests for this condition.  */
 572           && (old->tests == 0
 573               || (add->enforce_mode ? no_same_mode (old) : old->next == 0))
 574           && old->code == add->code
 575           && old->mode == add->mode
 576           && (old->exact == add->exact
 577               || (old->exact && add->exact && ! strcmp (old->exact, add->exact))))
 578         {
 579           old->success = merge_trees (old->success, add->success);
 580           if (old->insn_code_number >= 0 && add->insn_code_number >= 0)
 581             fatal ("Two actions at one point in tree");
 582           if (old->insn_code_number == -1)
 583             old->insn_code_number = add->insn_code_number;
 584           return 1;
 585         }
 586       old = old->next;
 587     }
 588   return 0;
 589 }
 590
 591 /* Merge ADD into the next-chain that starts with OLD,
 592    preferably after something that tests the same place
 593    that ADD does.
 594    The next-chain of ADD itself is ignored, and it is set
 595    up for entering ADD into the new chain.
 596    Returns the new chain.  */
 597
 598 static struct decision *
 599 try_merge_2 (old, add)
 600      struct decision *old, *add;
 601 {
 602   register struct decision *p;
 603   struct decision *last = 0;
 604   struct decision *last_same_place = 0;
 605
 606   /* Put this in after the others that test the same place,
 607      if there are any.  If not, find the last chain element
 608      and insert there.
 609
 610      One modification: if this one is NOT a MATCH_OPERAND,
 611      put it before any MATCH_OPERANDS that test the same place.
 612
 613      Another: if enforce_mode (i.e. this is first operand of a SET),
 614      put this after the last thing that tests the same place for
 615      the same mode.  */
 616
 617 #if 0
 618   int operand = 0 != add->tests;
 619 #endif
 620
 621   for (p = old; p; p = p->next)
 622     {
 623       if (p->position == add->position
 624           || (p->position && add->position
 625               && !strcmp (p->position, add->position)))
 626         {
 627           last_same_place = p;
 628           /* If enforce_mode, segregate the modes in numerical order.  */
 629           if (p->enforce_mode && (int) add->mode < (int) p->mode)
 630             break;
 631 #if 0
 632           /* Keep explicit decompositions before those that test predicates.
 633              If enforce_mode, do this separately within each mode.  */
 634           if (! p->enforce_mode || p->mode == add->mode)
 635             if (!operand && p->tests)
 636               break;
 637 #endif
 638         }
 639       /* If this is past the end of the decisions at the same place as ADD,
 640          stop looking now; add ADD before here.  */
 641       else if (last_same_place)
 642         break;
 643       last = p;
 644     }
 645
 646   /* Insert before P, which means after LAST.  */
 647
 648   if (last)
 649     {
 650       add->next = last->next;
 651       last->next = add;
 652       return old;
 653     }
 654
 655   add->next = old;
 656   return add;
 657 }
 658
 659 static int
 660 no_same_mode (node)
 661      struct decision *node;
 662 {
 663   register struct decision *p;
 664   register enum machine_mode mode = node->mode;
 665
 666   for (p = node->next; p; p = p->next)
 667     if (p->mode == mode)
 668       return 0;
 669
 670   return 1;
 671 }
 672 \f
 673 /* Count the number of subnodes of node NODE, assumed to be the start
 674    of a next-chain.  If the number is high enough, make NODE start
 675    a separate subroutine in the C code that is generated.
 676
 677    TYPE gives the type of routine we are writing.  */
 678
 679 static int
 680 break_out_subroutines (node, type)
 681      struct decision *node;
 682      enum routine_type type;
 683 {
 684   int size = 0;
 685   struct decision *sub;
 686   for (sub = node; sub; sub = sub->next)
 687     size += 1 + break_out_subroutines (sub->success, type);
 688   if (size > SUBROUTINE_THRESHOLD)
 689     {
 690       node->subroutine_number = ++next_subroutine_number;
 691       write_subroutine (node, type);
 692       size = 1;
 693     }
 694   return size;
 695 }
 696
 697 static void
 698 write_subroutine (tree, type)
 699      struct decision *tree;
 700      enum routine_type type;
 701 {
 702   char *return_type = (type == SPLIT ? "rtx" : "int");
 703
 704   if (type == SPLIT)
 705     {
 706       printf ("rtx\nsplit_%d (x0, insn)\n", tree->subroutine_number);
 707       printf ("     register rtx x0;\n     rtx insn;\n");
 708     }
 709   else
 710     {
 711       printf ("int\nrecog_%d (x0, insn, pnum_clobbers)\n",
 712               tree->subroutine_number);
 713       printf ("     register rtx x0;\n     rtx insn;\n");
 714       printf ("     int *pnum_clobbers;\n");
 715     }
 716
 717   printf ("{\n");
 718   printf ("  register rtx *ro = &recog_operand[0];\n");
 719   printf ("  register rtx x1, x2, x3, x4, x5;\n  rtx x6, x7, x8, x9, x10, x11;\n");
 720   printf ("  %s tem;\n", return_type);
 721   write_tree (tree, "", 0, "", 1, type);
 722   printf (" ret0: return %d;\n}\n\n", type == SPLIT ? 0 : -1);
 723 }
 724 \f
 725 /* Write out C code to perform the decisions in the tree.  */
 726
 727 static char *
 728 write_tree_1 (tree, prevpos, afterward, afterpos, initial, type)
 729      struct decision *tree;
 730      char *prevpos;
 731      int afterward;
 732      char *afterpos;
 733      int initial;
 734      enum routine_type type;
 735 {
 736   register struct decision *p, *p1;
 737   char *pos;
 738   register int depth;
 739   int ignmode;
 740   enum anon1 { NO_SWITCH, CODE_SWITCH, MODE_SWITCH } in_switch = NO_SWITCH;
 741   char modemap[NUM_MACHINE_MODES];
 742   char codemap[NUM_RTX_CODE];
 743
 744   pos = prevpos;
 745
 746   tree->label_needed = 1;
 747   for (p = tree; p; p = p->next)
 748     {
 749       /* Find the next alternative to p
 750          that might be true when p is true.
 751          Test that one next if p's successors fail.
 752          Note that when the `tests' field is nonzero
 753          it is up to the specified test-function to compare machine modes
 754          and some (such as general_operand) don't always do so.
 755          But when inside a switch-on-modes we ignore this and
 756          consider all modes mutually exclusive.  */
 757       for (p1 = p->next; p1; p1 = p1->next)
 758         if (((p->code == UNKNOWN || p1->code == UNKNOWN || p->code == p1->code)
 759              && (p->mode == VOIDmode || p1->mode == VOIDmode
 760                  || p->mode == p1->mode
 761                  || (in_switch != MODE_SWITCH && (p->tests || p1->tests))))
 762             || strcmp (p1->position, p->position))
 763           break;
 764       p->afterward = p1;
 765       if (p1) p1->label_needed = 1;
 766
 767       if (in_switch == MODE_SWITCH
 768           && (p->mode == VOIDmode || (! p->enforce_mode && p->tests != 0)))
 769         {
 770           in_switch = NO_SWITCH;
 771           printf ("  }\n");
 772         }
 773       if (in_switch == CODE_SWITCH && p->code == UNKNOWN)
 774         {
 775           in_switch = NO_SWITCH;
 776           printf ("  }\n");
 777         }
 778
 779       if (p->label_needed)
 780         printf (" L%d:\n", p->number);
 781
 782       if (p->success == 0 && p->insn_code_number < 0)
 783         abort ();
 784
 785       change_state (pos, p->position);
 786       pos = p->position;
 787       depth = strlen (pos);
 788
 789       ignmode = (p->ignmode || p->tests);
 790
 791       if (in_switch == NO_SWITCH)
 792         {
 793           /* If p and its alternatives all want the same mode,
 794              reject all others at once, first, then ignore the mode.  */
 795           if (!ignmode && p->mode != VOIDmode && p->next && same_modes (p, p->mode))
 796             {
 797               printf ("  if (GET_MODE (x%d) != %smode)\n",
 798                       depth, GET_MODE_NAME (p->mode));
 799               if (afterward)
 800                 {
 801                   printf ("    {\n    ");
 802                   change_state (pos, afterpos);
 803                   printf ("      goto L%d;\n    }\n", afterward);
 804                 }
 805               else
 806                 printf ("    goto ret0;\n");
 807               clear_modes (p);
 808               ignmode = 1;
 809             }
 810
 811           /* If p and its alternatives all want the same code,
 812              reject all others at once, first, then ignore the code.  */
 813           if (p->code != UNKNOWN && p->next && same_codes (p, p->code))
 814             {
 815               printf ("  if (GET_CODE (x%d) != ", depth);
 816               print_code (p->code);
 817               printf (")\n");
 818               if (afterward)
 819                 {
 820                   printf ("    {");
 821                   change_state (pos, afterpos);
 822                   printf ("    goto L%d; }\n", afterward);
 823                 }
 824               else
 825                 printf ("    goto ret0;\n");
 826               clear_codes (p);
 827             }
 828         }
 829
 830       /* If p and its alternatives all have different modes
 831          and there are at least 4 of them, make a switch.  */
 832       if (in_switch == NO_SWITCH)
 833         {
 834           register int i;
 835           int lose = 0;
 836
 837           mybzero (modemap, sizeof modemap);
 838           for (p1 = p, i = 0;
 839                (p1 && p1->mode != VOIDmode
 840                 && (p1->tests == 0 || p1->enforce_mode));
 841                p1 = p1->next, i++)
 842             {
 843               if (! p->enforce_mode && modemap[(int) p1->mode])
 844                 {
 845                   lose = 1;
 846                   break;
 847                 }
 848               modemap[(int) p1->mode] = 1;
 849             }
 850           if (!lose && i >= 4)
 851             {
 852               in_switch = MODE_SWITCH;
 853               printf (" switch (GET_MODE (x%d))\n  {\n", depth);
 854             }
 855         }
 856
 857       if (in_switch == NO_SWITCH)
 858         {
 859           register int i;
 860           mybzero (codemap, sizeof codemap);
 861           for (p1 = p, i = 0; p1 && p1->code != UNKNOWN; p1 = p1->next, i++)
 862             {
 863               if (codemap[(int) p1->code])
 864                 break;
 865               codemap[(int) p1->code] = 1;
 866             }
 867           if ((p1 == 0 || p1->code == UNKNOWN) && i >= 4)
 868             {
 869               in_switch = CODE_SWITCH;
 870               printf (" switch (GET_CODE (x%d))\n  {\n", depth);
 871             }
 872         }
 873
 874       if (in_switch == MODE_SWITCH)
 875         {
 876           if (modemap[(int) p->mode])
 877             {
 878               printf ("  case %smode:\n", GET_MODE_NAME (p->mode));
 879               modemap[(int) p->mode] = 0;
 880             }
 881         }
 882       if (in_switch == CODE_SWITCH)
 883         {
 884           if (codemap[(int) p->code])
 885             {
 886               printf ("  case ");
 887               print_code (p->code);
 888               printf (":\n");
 889               codemap[(int) p->code] = 0;
 890             }
 891         }
 892
 893       printf ("  if (");
 894       if (p->exact || (p->code != UNKNOWN && in_switch != CODE_SWITCH))
 895         {
 896           if (p->exact)
 897             printf ("x%d == %s", depth, p->exact);
 898           else
 899             {
 900               printf ("GET_CODE (x%d) == ", depth);
 901               print_code (p->code);
 902             }
 903           printf (" && ");
 904         }
 905       if (p->mode != VOIDmode && !ignmode && in_switch != MODE_SWITCH)
 906         printf ("GET_MODE (x%d) == %smode && ",
 907                 depth, GET_MODE_NAME (p->mode));
 908       if (p->test_elt_zero_int)
 909         printf ("XINT (x%d, 0) == %d && ", depth, p->elt_zero_int);
 910       if (p->veclen)
 911         printf ("XVECLEN (x%d, 0) == %d && ", depth, p->veclen);
 912       if (p->test_elt_one_int)
 913         printf ("XINT (x%d, 1) == %d && ", depth, p->elt_one_int);
 914       if (p->dupno >= 0)
 915         printf ("rtx_equal_p (x%d, ro[%d]) && ", depth, p->dupno);
 916       if (p->tests)
 917         printf ("%s (x%d, %smode)", p->tests, depth,
 918                 GET_MODE_NAME (p->mode));
 919       else
 920         printf ("1");
 921
 922       if (p->opno >= 0)
 923         printf (")\n    { ro[%d] = x%d; ",
 924                 p->opno, depth);
 925       else
 926         printf (")\n    ");
 927
 928       if (p->c_test)
 929         printf ("if (%s) ", p->c_test);
 930
 931       if (p->insn_code_number >= 0)
 932         {
 933           if (type == SPLIT)
 934             printf ("return gen_split_%d (operands);", p->insn_code_number);
 935           else
 936             {
 937               if (p->num_clobbers_to_add)
 938                 {
 939                   printf ("\n      {\n");
 940                   printf ("\tif (pnum_clobbers == 0) goto ret0; ");
 941                   printf ("*pnum_clobbers = %d; ", p->num_clobbers_to_add);
 942                   printf ("return %d;\n      }", p->insn_code_number);
 943                 }
 944               else
 945                 printf ("return %d;", p->insn_code_number);
 946             }
 947         }
 948       else
 949         printf ("goto L%d;", p->success->number);
 950
 951       if (p->opno >= 0)
 952         printf (" }\n");
 953       else
 954         printf ("\n");
 955
 956       /* Now, if inside a switch, branch to next switch member
 957          that might also need to be tested if this one fails.  */
 958
 959       if (in_switch == CODE_SWITCH)
 960         {
 961           /* Find the next alternative to p
 962              that might be applicable if p was applicable.  */
 963           for (p1 = p->next; p1; p1 = p1->next)
 964             if (p1->code == UNKNOWN || p->code == p1->code)
 965               break;
 966           if (p1 == 0 || p1->code == UNKNOWN)
 967             printf ("  break;\n");
 968           else if (p1 != p->next)
 969             {
 970               printf (" goto L%d;\n", p1->number);
 971               p1->label_needed = 1;
 972             }
 973         }
 974
 975       if (in_switch == MODE_SWITCH)
 976         {
 977           /* Find the next alternative to p
 978              that might be applicable if p was applicable.  */
 979           for (p1 = p->next; p1; p1 = p1->next)
 980             if (p1->mode == VOIDmode || p->mode == p1->mode)
 981               break;
 982           if (p1 == 0 || p1->mode == VOIDmode)
 983             printf ("  break;\n");
 984           else if (p1 != p->next)
 985             {
 986               printf (" goto L%d;\n", p1->number);
 987               p1->label_needed = 1;
 988             }
 989         }
 990     }
 991
 992   if (in_switch != NO_SWITCH)
 993     printf ("  }\n");
 994
 995   if (afterward)
 996     {
 997       change_state (pos, afterpos);
 998       printf ("  goto L%d;\n", afterward);
 999     }
1000   else
1001     printf ("  goto ret0;\n");
1002   return pos;
1003 }
1004
1005 static void
1006 write_tree (tree, prevpos, afterward, afterpos, initial, type)
1007      struct decision *tree;
1008      char *prevpos;
1009      int afterward;
1010      char *afterpos;
1011      int initial;
1012      enum routine_type type;
1013 {
1014   register struct decision *p;
1015   char *pos = prevpos;
1016   char *name_prefix = (type == SPLIT ? "split" : "recog");
1017   char *call_suffix = (type == SPLIT ? "" : ", pnum_clobbers");
1018
1019   if (tree->subroutine_number > 0 && ! initial)
1020     {
1021       printf (" L%d:\n", tree->number);
1022
1023       if (afterward)
1024         {
1025           printf ("  tem = %s_%d (x0, insn%s);\n",
1026                   name_prefix, tree->subroutine_number, call_suffix);
1027           printf ("  if (tem >= 0) return tem;\n");
1028           change_state (pos, afterpos);
1029           printf ("  goto L%d;\n", afterward);
1030         }
1031       else
1032         printf ("  return %s_%d (x0, insn%s);\n",
1033                 name_prefix, tree->subroutine_number, call_suffix);
1034       return;
1035     }
1036
1037   pos = write_tree_1 (tree, prevpos, afterward, afterpos, initial, type);
1038
1039   for (p = tree; p; p = p->next)
1040     if (p->success)
1041       {
1042         pos = p->position;
1043         write_tree (p->success, pos,
1044                     p->afterward ? p->afterward->number : afterward,
1045                     p->afterward ? pos : afterpos, 0, type);
1046       }
1047 }
1048
1049 static void
1050 print_code (code)
1051      RTX_CODE code;
1052 {
1053   register char *p1;
1054   for (p1 = GET_RTX_NAME (code); *p1; p1++)
1055     {
1056       if (*p1 >= 'a' && *p1 <= 'z')
1057         putchar (*p1 + 'A' - 'a');
1058       else
1059         putchar (*p1);
1060     }
1061 }
1062
1063 static int
1064 same_codes (p, code)
1065      register struct decision *p;
1066      register RTX_CODE code;
1067 {
1068   for (; p; p = p->next)
1069     if (p->code != code)
1070       return 0;
1071
1072   return 1;
1073 }
1074
1075 static void
1076 clear_codes (p)
1077      register struct decision *p;
1078 {
1079   for (; p; p = p->next)
1080     p->code = UNKNOWN;
1081 }
1082
1083 static int
1084 same_modes (p, mode)
1085      register struct decision *p;
1086      register enum machine_mode mode;
1087 {
1088   for (; p; p = p->next)
1089     if (p->mode != mode || p->tests)
1090       return 0;
1091
1092   return 1;
1093 }
1094
1095 static void
1096 clear_modes (p)
1097      register struct decision *p;
1098 {
1099   for (; p; p = p->next)
1100     p->ignmode = 1;
1101 }
1102 \f
1103 static void
1104 change_state (oldpos, newpos)
1105      char *oldpos;
1106      char *newpos;
1107 {
1108   int odepth = strlen (oldpos);
1109   int depth = odepth;
1110   int ndepth = strlen (newpos);
1111
1112   /* Pop up as many levels as necessary.  */
1113
1114   while (strncmp (oldpos, newpos, depth))
1115     --depth;
1116
1117   /* Go down to desired level.  */
1118
1119   while (depth < ndepth)
1120     {
1121       if (newpos[depth] >= 'a' && newpos[depth] <= 'z')
1122         printf ("  x%d = XVECEXP (x%d, 0, %d);\n",
1123                 depth + 1, depth, newpos[depth] - 'a');
1124       else
1125         printf ("  x%d = XEXP (x%d, %c);\n",
1126                 depth + 1, depth, newpos[depth]);
1127       ++depth;
1128     }
1129 }
1130 \f
1131 static char *
1132 copystr (s1)
1133      char *s1;
1134 {
1135   register char *tem;
1136
1137   if (s1 == 0)
1138     return 0;
1139
1140   tem = (char *) xmalloc (strlen (s1) + 1);
1141   strcpy (tem, s1);
1142
1143   return tem;
1144 }
1145
1146 static void
1147 mybzero (b, length)
1148      register char *b;
1149      register unsigned length;
1150 {
1151   while (length-- > 0)
1152     *b++ = 0;
1153 }
1154
1155 static char *
1156 concat (s1, s2)
1157      char *s1, *s2;
1158 {
1159   register char *tem;
1160
1161   if (s1 == 0)
1162     return s2;
1163   if (s2 == 0)
1164     return s1;
1165
1166   tem = (char *) xmalloc (strlen (s1) + strlen (s2) + 2);
1167   strcpy (tem, s1);
1168   strcat (tem, " ");
1169   strcat (tem, s2);
1170
1171   return tem;
1172 }
1173
1174 char *
1175 xrealloc (ptr, size)
1176      char *ptr;
1177      unsigned size;
1178 {
1179   char *result = (char *) realloc (ptr, size);
1180   if (!result)
1181     fatal ("virtual memory exhausted");
1182   return result;
1183 }
1184
1185 char *
1186 xmalloc (size)
1187      unsigned size;
1188 {
1189   register char *val = (char *) malloc (size);
1190
1191   if (val == 0)
1192     fatal ("virtual memory exhausted");
1193   return val;
1194 }
1195
1196 static void
1197 fatal (s, a1, a2)
1198      char *s;
1199 {
1200   fprintf (stderr, "genrecog: ");
1201   fprintf (stderr, s, a1, a2);
1202   fprintf (stderr, "\n");
1203   fprintf (stderr, "after %d instruction definitions\n", next_index);
1204   exit (FATAL_EXIT_CODE);
1205 }
1206
1207 /* More 'friendly' abort that prints the line and file.
1208    config.h can #define abort fancy_abort if you like that sort of thing.  */
1209
1210 void
1211 fancy_abort ()
1212 {
1213   fatal ("Internal gcc abort.");
1214 }
1215 \f
1216 int
1217 main (argc, argv)
1218      int argc;
1219      char **argv;
1220 {
1221   rtx desc;
1222   struct decision *tree = 0;
1223   struct decision *split_tree = 0;
1224   FILE *infile;
1225   extern rtx read_rtx ();
1226   register int c;
1227
1228   obstack_init (rtl_obstack);
1229
1230   if (argc <= 1)
1231     fatal ("No input file name.");
1232
1233   infile = fopen (argv[1], "r");
1234   if (infile == 0)
1235     {
1236       perror (argv[1]);
1237       exit (FATAL_EXIT_CODE);
1238     }
1239
1240   init_rtl ();
1241   next_insn_code = 0;
1242   next_index = 0;
1243
1244   printf ("/* Generated automatically by the program `genrecog'\n\
1245 from the machine description file `md'.  */\n\n");
1246
1247   printf ("#include \"config.h\"\n");
1248   printf ("#include \"rtl.h\"\n");
1249   printf ("#include \"insn-config.h\"\n");
1250   printf ("#include \"recog.h\"\n");
1251   printf ("#include \"real.h\"\n");
1252   printf ("#include \"output.h\"\n");
1253   printf ("#include \"flags.h\"\n");
1254   printf ("\n");
1255
1256   /* Read the machine description.  */
1257
1258   while (1)
1259     {
1260       c = read_skip_spaces (infile);
1261       if (c == EOF)
1262         break;
1263       ungetc (c, infile);
1264
1265       desc = read_rtx (infile);
1266       if (GET_CODE (desc) == DEFINE_INSN)
1267         tree = merge_trees (tree, make_insn_sequence (desc));
1268       else if (GET_CODE (desc) == DEFINE_SPLIT)
1269         split_tree = merge_trees (split_tree, make_split_sequence (desc));
1270       if (GET_CODE (desc) == DEFINE_PEEPHOLE
1271           || GET_CODE (desc) == DEFINE_EXPAND)
1272         next_insn_code++;
1273       next_index++;
1274     }
1275
1276   printf ("\n\
1277 /* `recog' contains a decision tree\n\
1278    that recognizes whether the rtx X0 is a valid instruction.\n\
1279 \n\
1280    recog returns -1 if the rtx is not valid.\n\
1281    If the rtx is valid, recog returns a nonnegative number\n\
1282    which is the insn code number for the pattern that matched.\n");
1283   printf ("   This is the same as the order in the machine description of\n\
1284    the entry that matched.  This number can be used as an index into\n\
1285    entry that matched.  This number can be used as an index into various\n\
1286    insn_* tables, such as insn_templates, insn_outfun, and insn_n_operands\n\
1287    (found in insn-output.c).\n\n");
1288   printf ("   The third argument to recog is an optional pointer to an int.\n\
1289    If present, recog will accept a pattern if it matches except for\n\
1290    missing CLOBBER expressions at the end.  In that case, the value\n\
1291    pointed to by the optional pointer will be set to the number of\n\
1292    CLOBBERs that need to be added (it should be initialized to zero by\n\
1293    the caller).  If it is set nonzero, the caller should allocate a\n\
1294    PARALLEL of the appropriate size, copy the initial entries, and call\n\
1295    add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.");
1296
1297   if (split_tree)
1298     printf ("\n\n   The function split_insns returns 0 if the rtl could not\n\
1299    be split or the split rtl in a SEQUENCE if it can be.");
1300
1301   printf ("*/\n\n");
1302
1303   printf ("rtx recog_operand[MAX_RECOG_OPERANDS];\n\n");
1304   printf ("rtx *recog_operand_loc[MAX_RECOG_OPERANDS];\n\n");
1305   printf ("rtx *recog_dup_loc[MAX_DUP_OPERANDS];\n\n");
1306   printf ("char recog_dup_num[MAX_DUP_OPERANDS];\n\n");
1307   printf ("#define operands recog_operand\n\n");
1308
1309   next_subroutine_number = 0;
1310   break_out_subroutines (tree, RECOG);
1311
1312   printf ("int\nrecog (x0, insn, pnum_clobbers)\n");
1313   printf ("     register rtx x0;\n     rtx insn;\n");
1314   printf ("     int *pnum_clobbers;\n{\n");
1315   printf ("  register rtx *ro = &recog_operand[0];\n");
1316   printf ("  register rtx x1, x2, x3, x4, x5;\n  rtx x6, x7, x8, x9, x10, x11;\n");
1317   printf ("  int tem;\n");
1318
1319   if (tree)
1320     write_tree (tree, "", 0, "", 1, RECOG);
1321   printf (" ret0: return -1;\n}\n");
1322
1323   next_subroutine_number = 0;
1324   break_out_subroutines (split_tree, SPLIT);
1325
1326   printf ("rtx\nsplit_insns (x0, insn)\n     register rtx x0;\n     rtx insn;\n{\n");
1327   printf ("  register rtx *ro = &recog_operand[0];\n");
1328   printf ("  register rtx x1, x2, x3, x4, x5;\n  rtx x6, x7, x8, x9, x10, x11;\n");
1329   printf ("  rtx tem;\n");
1330
1331   if (split_tree)
1332     write_tree (split_tree, "", 0, "", 1, SPLIT);
1333   printf (" ret0: return 0;\n}\n");
1334
1335   fflush (stdout);
1336   exit (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
1337   /* NOTREACHED */
1338   return 0;
1339 }