sim/igen/gen.c

   1 /*  This file is part of the program psim.
   2
   3     Copyright (C) 1994-1997, Andrew Cagney <cagney@highland.com.au>
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with this program; if not, write to the Free Software
  17     Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  18
  19     */
  20
  21
  22 #include "misc.h"
  23 #include "lf.h"
  24 #include "table.h"
  25 #include "filter.h"
  26
  27 #include "igen.h"
  28 #include "ld-insn.h"
  29 #include "ld-decode.h"
  30 #include "gen.h"
  31
  32 static insn_uint
  33 sub_val (insn_uint val,
  34          int val_last_pos,
  35          int first_pos,
  36          int last_pos)
  37 {
  38   return ((val >> (val_last_pos - last_pos))
  39           & (((insn_uint)1 << (last_pos - first_pos + 1)) - 1));
  40 }
  41
  42 static void
  43 update_depth (lf *file,
  44               gen_entry *entry,
  45               int depth,
  46               void *data)
  47 {
  48   int *max_depth = (int*)data;
  49   if (*max_depth < depth)
  50     *max_depth = depth;
  51 }
  52
  53
  54 int
  55 gen_entry_depth (gen_entry *table)
  56 {
  57   int depth = 0;
  58   gen_entry_traverse_tree (NULL,
  59                            table,
  60                            1,
  61                            NULL, /*start*/
  62                            update_depth,
  63                            NULL, /*end*/
  64                            &depth); /* data */
  65   return depth;
  66 }
  67
  68
  69 static void
  70 print_gen_entry_path (line_ref *line,
  71                       gen_entry *table,
  72                       error_func *print)
  73 {
  74   if (table->parent == NULL)
  75     {
  76       if (table->top->model != NULL)
  77         print (line, "%s", table->top->model->name);
  78       else
  79         print (line, "");
  80     }
  81   else
  82     {
  83       print_gen_entry_path (line, table->parent, print);
  84       print (NULL, ".%d", table->opcode_nr);
  85     }
  86 }
  87
  88 static void
  89 print_gen_entry_insns (gen_entry *table,
  90                        error_func *print,
  91                        char *first_message,
  92                        char *next_message)
  93 {
  94   insn_list *i;
  95   char *message;
  96   message = first_message;
  97   for (i = table->insns; i != NULL; i = i->next)
  98     {
  99       insn_entry *insn = i->insn;
 100       print_gen_entry_path (insn->line, table, print);
 101       print (NULL, ": %s.%s %s\n",
 102              insn->format_name,
 103              insn->name,
 104              message);
 105       if (next_message != NULL)
 106         message = next_message;
 107     }
 108 }
 109
 110 /* same as strcmp */
 111 static int
 112 insn_field_cmp (insn_word_entry *l, insn_word_entry *r)
 113 {
 114   while (1)
 115     {
 116       int bit_nr;
 117       if (l == NULL && r == NULL)
 118         return 0; /* all previous fields the same */
 119       if (l == NULL)
 120         return -1; /* left shorter than right */
 121       if (r == NULL)
 122         return +1; /* left longer than right */
 123       for (bit_nr = 0;
 124            bit_nr < options.insn_bit_size;
 125            bit_nr++)
 126         {
 127           if (l->bit[bit_nr]->field->type != insn_field_string)
 128             continue;
 129           if (r->bit[bit_nr]->field->type != insn_field_string)
 130             continue;
 131           if (l->bit[bit_nr]->field->conditions == NULL)
 132             continue;
 133           if (r->bit[bit_nr]->field->conditions == NULL)
 134             continue;
 135           if (0)
 136             printf ("%s%s%s VS %s%s%s\n",
 137                     l->bit[bit_nr]->field->val_string,
 138                     l->bit[bit_nr]->field->conditions->test == insn_field_cond_eq ? "=" : "!",
 139                     l->bit[bit_nr]->field->conditions->string,
 140                     r->bit[bit_nr]->field->val_string,
 141                     r->bit[bit_nr]->field->conditions->test == insn_field_cond_eq ? "=" : "!",
 142                     r->bit[bit_nr]->field->conditions->string);
 143           if (l->bit[bit_nr]->field->conditions->test == insn_field_cond_eq
 144               && r->bit[bit_nr]->field->conditions->test == insn_field_cond_eq)
 145             {
 146               if (l->bit[bit_nr]->field->conditions->type == insn_field_cond_field
 147                   && r->bit[bit_nr]->field->conditions->type == insn_field_cond_field)
 148                 /* somewhat arbitrary */
 149                 {
 150                   int cmp = strcmp (l->bit[bit_nr]->field->conditions->string,
 151                                     r->bit[bit_nr]->field->conditions->string);
 152                   if (cmp != 0)
 153                     return cmp;
 154                   else
 155                     continue;
 156                 }
 157               if (l->bit[bit_nr]->field->conditions->type == insn_field_cond_field)
 158                 return +1;
 159               if (r->bit[bit_nr]->field->conditions->type == insn_field_cond_field)
 160                 return -1;
 161               /* The case of both fields having constant values should have
 162                  already have been handled because such fields are converted
 163                  into normal constant fields. */
 164               continue;
 165             }
 166           if (l->bit[bit_nr]->field->conditions->test == insn_field_cond_eq)
 167             return +1; /* left = only */
 168           if (r->bit[bit_nr]->field->conditions->test == insn_field_cond_eq)
 169             return -1; /* right = only */
 170           /* FIXME: Need to some what arbitrarily order conditional lists */
 171           continue;
 172         }
 173       l = l->next;
 174       r = r->next;
 175     }
 176 }
 177
 178 /* same as strcmp */
 179 static int
 180 insn_word_cmp (insn_word_entry *l, insn_word_entry *r)
 181 {
 182   while (1)
 183     {
 184       int bit_nr;
 185       if (l == NULL && r == NULL)
 186         return 0; /* all previous fields the same */
 187       if (l == NULL)
 188         return -1; /* left shorter than right */
 189       if (r == NULL)
 190         return +1; /* left longer than right */
 191       for (bit_nr = 0;
 192            bit_nr < options.insn_bit_size;
 193            bit_nr++)
 194         {
 195           if (l->bit[bit_nr]->mask < r->bit[bit_nr]->mask)
 196             return -1;
 197           if (l->bit[bit_nr]->mask > r->bit[bit_nr]->mask)
 198             return 1;
 199           if (l->bit[bit_nr]->value < r->bit[bit_nr]->value)
 200             return -1;
 201           if (l->bit[bit_nr]->value > r->bit[bit_nr]->value)
 202             return 1;
 203         }
 204       l = l->next;
 205       r = r->next;
 206     }
 207 }
 208
 209 /* same as strcmp */
 210 static int
 211 opcode_bit_cmp (opcode_bits *l,
 212                 opcode_bits *r)
 213 {
 214   if (l == NULL && r == NULL)
 215     return 0; /* all previous bits the same */
 216   if (l == NULL)
 217     return -1; /* left shorter than right */
 218   if (r == NULL)
 219     return +1; /* left longer than right */
 220   /* most significant word */
 221   if (l->field->word_nr < r->field->word_nr)
 222     return +1; /* left has more significant word */
 223   if (l->field->word_nr > r->field->word_nr)
 224     return -1; /* right has more significant word */
 225   /* most significant bit? */
 226   if (l->first < r->first)
 227     return +1; /* left as more significant bit */
 228   if (l->first > r->first)
 229     return -1; /* right as more significant bit */
 230   /* nr bits? */
 231   if (l->last < r->last)
 232     return +1; /* left as less bits */
 233   if (l->last > r->last)
 234     return -1; /* right as less bits */
 235   /* value? */
 236   if (l->value < r->value)
 237     return -1;
 238   if (l->value > r->value)
 239     return 1;
 240   return 0;
 241 }
 242
 243
 244 /* same as strcmp */
 245 static int
 246 opcode_bits_cmp (opcode_bits *l,
 247                  opcode_bits *r)
 248 {
 249   while (1)
 250     {
 251       int cmp;
 252       if (l == NULL && r == NULL)
 253         return 0; /* all previous bits the same */
 254       cmp = opcode_bit_cmp (l, r);
 255       if (cmp != 0)
 256         return cmp;
 257       l = l->next;
 258       r = r->next;
 259     }
 260 }
 261
 262 /* same as strcmp */
 263 static opcode_bits *
 264 new_opcode_bits (opcode_bits *old_bits,
 265                  int value,
 266                  int first,
 267                  int last,
 268                  insn_field_entry *field,
 269                  opcode_field *opcode)
 270 {
 271   opcode_bits *new_bits = ZALLOC (opcode_bits);
 272   new_bits->field = field;
 273   new_bits->value = value;
 274   new_bits->first = first;
 275   new_bits->last = last;
 276   new_bits->opcode = opcode;
 277
 278   if (old_bits != NULL)
 279     {
 280       opcode_bits *new_list;
 281       opcode_bits **last = &new_list;
 282       new_list = new_opcode_bits (old_bits->next,
 283                                   old_bits->value,
 284                                   old_bits->first,
 285                                   old_bits->last,
 286                                   old_bits->field,
 287                                   old_bits->opcode);
 288       while (*last != NULL)
 289         {
 290           int cmp = opcode_bit_cmp (new_bits, *last);
 291           if (cmp < 0) /* new < new_list */
 292             {
 293               break;
 294             }
 295           if (cmp == 0)
 296             {
 297               ERROR ("Duplicated insn bits in list");
 298             }
 299           last = &(*last)->next;
 300         }
 301       new_bits->next = *last;
 302       *last = new_bits;
 303       return new_list;
 304     }
 305   else
 306     {
 307       return new_bits;
 308     }
 309 }
 310
 311 /* Same as strcmp().  */
 312 static int
 313 format_name_cmp (const char *l, const char *r)
 314 {
 315   if (l == NULL && r == NULL)
 316     return 0;
 317   if (l != NULL && r == NULL)
 318     return -1;
 319   if (l == NULL && r != NULL)
 320     return +1;
 321   return strcmp (l, r);
 322 }
 323
 324
 325 typedef enum {
 326   merge_duplicate_insns,
 327   report_duplicate_insns,
 328 } duplicate_insn_actions;
 329
 330 static insn_list *
 331 insn_list_insert (insn_list **cur_insn_ptr,
 332                   int *nr_insns,
 333                   insn_entry *insn,
 334                   opcode_bits *expanded_bits,
 335                   opcode_field *opcodes,
 336                   int nr_prefetched_words,
 337                   duplicate_insn_actions duplicate_action)
 338 {
 339   /* insert it according to the order of the fields & bits */
 340   for (; (*cur_insn_ptr) != NULL; cur_insn_ptr = &(*cur_insn_ptr)->next)
 341     {
 342       int cmp;
 343
 344       /* key#1 sort according to the constant fields of each instruction */
 345       cmp = insn_word_cmp (insn->words, (*cur_insn_ptr)->insn->words);
 346       if (cmp < 0)
 347         break;
 348       else if (cmp > 0)
 349         continue;
 350
 351       /* key#2 sort according to the expanded bits of each instruction */
 352       cmp = opcode_bits_cmp (expanded_bits, (*cur_insn_ptr)->expanded_bits);
 353       if (cmp < 0)
 354         break;
 355       else if (cmp > 0)
 356         continue;
 357
 358       /* key#3 sort according to the non-constant fields of each instruction */
 359       cmp = insn_field_cmp (insn->words, (*cur_insn_ptr)->insn->words);
 360       if (cmp < 0)
 361         break;
 362       else if (cmp > 0)
 363         continue;
 364
 365       /* key#4 sort according to the format-name.  If two apparently
 366          identical instructions have unique format-names, then the
 367          instructions are different.  This is because the
 368          format-name's use is overloaded, it not only indicates the
 369          format name but also provides a unique semantic name for the
 370          function.  */
 371       cmp = format_name_cmp (insn->format_name, (*cur_insn_ptr)->insn->format_name);
 372       if (cmp < 0)
 373         break;
 374       else if (cmp > 0)
 375         continue;
 376
 377       /* duplicate keys, report problem */
 378       switch (duplicate_action)
 379         {
 380         case report_duplicate_insns:
 381           /* It would appear that we have two instructions with the
 382              same constant field values across all words and bits.
 383              This error can also occure when insn_field_cmp() is
 384              failing to differentiate between two instructions that
 385              differ only in their conditional fields. */
 386           warning (insn->line,
 387                    "Two instructions with identical constant fields\n");
 388           error ((*cur_insn_ptr)->insn->line,
 389                  "Location of duplicate instruction\n");
 390         case merge_duplicate_insns:
 391           /* Add the opcode path to the instructions list */
 392           if (opcodes != NULL)
 393             {
 394               insn_opcodes **last = &(*cur_insn_ptr)->opcodes;
 395               while (*last != NULL)
 396                 {
 397                   last = &(*last)->next;
 398                 }
 399               (*last) = ZALLOC (insn_opcodes);
 400               (*last)->opcode = opcodes;
 401             }
 402           /* Use the larger nr_prefetched_words */
 403           if ((*cur_insn_ptr)->nr_prefetched_words < nr_prefetched_words)
 404             (*cur_insn_ptr)->nr_prefetched_words = nr_prefetched_words;
 405           return (*cur_insn_ptr);
 406         }
 407
 408     }
 409
 410   /* create a new list entry and insert it */
 411   {
 412     insn_list *new_insn = ZALLOC (insn_list);
 413     new_insn->insn = insn;
 414     new_insn->expanded_bits = expanded_bits;
 415     new_insn->next = (*cur_insn_ptr);
 416     new_insn->nr_prefetched_words = nr_prefetched_words;
 417     if (opcodes != NULL)
 418       {
 419         new_insn->opcodes = ZALLOC (insn_opcodes);
 420         new_insn->opcodes->opcode = opcodes;
 421       }
 422     (*cur_insn_ptr) = new_insn;
 423   }
 424
 425   *nr_insns += 1;
 426
 427   return (*cur_insn_ptr);
 428 }
 429
 430
 431 extern void
 432 gen_entry_traverse_tree (lf *file,
 433                          gen_entry *table,
 434                          int depth,
 435                          gen_entry_handler *start,
 436                          gen_entry_handler *leaf,
 437                          gen_entry_handler *end,
 438                          void *data)
 439 {
 440   gen_entry *entry;
 441
 442   ASSERT (table != NULL);
 443   ASSERT (table->opcode != NULL);
 444   ASSERT (table->nr_entries > 0);
 445   ASSERT (table->entries != 0);
 446
 447   /* prefix */
 448   if (start != NULL && depth >= 0)
 449     {
 450       start (file, table, depth, data);
 451     }
 452   /* infix leaves */
 453   for (entry = table->entries;
 454        entry != NULL;
 455        entry = entry->sibling)
 456     {
 457       if (entry->entries != NULL && depth != 0)
 458         {
 459           gen_entry_traverse_tree (file, entry, depth + 1,
 460                                    start, leaf, end, data);
 461         }
 462       else if (depth >= 0)
 463         {
 464           if (leaf != NULL)
 465             {
 466               leaf (file, entry, depth, data);
 467             }
 468         }
 469     }
 470   /* postfix */
 471   if (end != NULL && depth >= 0)
 472     {
 473       end (file, table, depth, data);
 474     }
 475 }
 476
 477
 478
 479 /* create a list element containing a single gen_table entry */
 480
 481 static gen_list *
 482 make_table (insn_table *isa,
 483             decode_table *rules,
 484             model_entry *model)
 485 {
 486   insn_entry *insn;
 487   gen_list *entry = ZALLOC (gen_list);
 488   entry->table = ZALLOC (gen_entry);
 489   entry->table->top = entry;
 490   entry->model = model;
 491   entry->isa = isa;
 492   for (insn = isa->insns; insn != NULL; insn = insn->next)
 493     {
 494       if (model == NULL
 495           || insn->processors == NULL
 496           || filter_is_member (insn->processors, model->name))
 497         {
 498           insn_list_insert (&entry->table->insns,
 499                             &entry->table->nr_insns,
 500                             insn,
 501                             NULL, /* expanded_bits - none yet */
 502                             NULL, /* opcodes - none yet */
 503                             0, /* nr_prefetched_words - none yet */
 504                             report_duplicate_insns);
 505         }
 506     }
 507   entry->table->opcode_rule = rules;
 508   return entry;
 509 }
 510
 511
 512 gen_table *
 513 make_gen_tables (insn_table *isa,
 514                  decode_table *rules)
 515 {
 516   gen_table *gen = ZALLOC (gen_table);
 517   gen->isa = isa;
 518   gen->rules = rules;
 519   if (options.gen.multi_sim)
 520     {
 521       gen_list **last = &gen->tables;
 522       model_entry *model;
 523       filter *processors;
 524       if (options.model_filter != NULL)
 525         processors = options.model_filter;
 526       else
 527         processors = isa->model->processors;
 528       for (model = isa->model->models;
 529            model != NULL;
 530            model = model->next)
 531         {
 532           if (filter_is_member (processors, model->name))
 533             {
 534               *last = make_table (isa, rules, model);
 535               last = &(*last)->next;
 536             }
 537         }
 538     }
 539   else
 540     {
 541       gen->tables = make_table (isa, rules, NULL);
 542     }
 543   return gen;
 544 }
 545
 546
 547 /****************************************************************/
 548
 549 #if 0
 550 typedef enum {
 551   field_is_not_constant = 0,
 552   field_constant_int = 1,
 553   field_constant_reserved = 2,
 554   field_constant_string = 3
 555 } constant_field_types;
 556
 557 static constant_field_types
 558 insn_field_is_constant (insn_field *field,
 559                         decode_table *rule)
 560 {
 561   switch (field->type)
 562     {
 563     case insn_field_int:
 564       /* field is an integer */
 565       return field_constant_int;
 566     case insn_field_reserved:
 567       /* field is `/' and treating that as a constant */
 568       if (rule->with_zero_reserved)
 569         return field_constant_reserved;
 570       else
 571         return field_is_not_constant;
 572     case insn_field_wild:
 573       return field_is_not_constant; /* never constant */
 574     case insn_field_string:
 575       /* field, though variable, is on the list of forced constants */
 576       if (filter_is_member (rule->constant_field_names, field->val_string))
 577         return field_constant_string;
 578       else
 579         return field_is_not_constant;
 580     }
 581   ERROR ("Internal error");
 582   return field_is_not_constant;
 583 }
 584 #endif
 585
 586
 587 /****************************************************************/
 588
 589
 590 /* Is the bit, according to the decode rule, identical across all the
 591    instructions? */
 592 static int
 593 insns_bit_useless (insn_list *insns,
 594                    decode_table *rule,
 595                    int bit_nr)
 596 {
 597   insn_list *entry;
 598   int value = -1;
 599   int is_useless = 1; /* cleared if something actually found */
 600
 601   /* check the instructions for some constant value in at least one of
 602      the bit fields */
 603   for (entry = insns; entry != NULL; entry = entry->next)
 604     {
 605       insn_word_entry *word = entry->insn->word[rule->word_nr];
 606       insn_bit_entry *bit = word->bit[bit_nr];
 607       switch (bit->field->type)
 608         {
 609         case insn_field_invalid:
 610           ASSERT (0);
 611           break;
 612         case insn_field_wild:
 613         case insn_field_reserved:
 614           /* neither useless or useful - ignore */
 615           break;
 616         case insn_field_int:
 617           switch (rule->search)
 618             {
 619             case decode_find_strings:
 620               /* an integer isn't a string */
 621               return 1;
 622             case decode_find_constants:
 623             case decode_find_mixed:
 624               /* an integer is useful if its value isn't the same
 625                  between all instructions.  The first time through the
 626                  value is saved, the second time through (if the
 627                  values differ) it is marked as useful. */
 628               if (value < 0)
 629                 value = bit->value;
 630               else if (value != bit->value)
 631                 is_useless = 0;
 632               break;
 633             }
 634           break;
 635         case insn_field_string:
 636           switch (rule->search)
 637             {
 638             case decode_find_strings:
 639               /* at least one string, keep checking */
 640               is_useless = 0;
 641               break;
 642             case decode_find_constants:
 643             case decode_find_mixed:
 644               if (filter_is_member (rule->constant_field_names,
 645                                     bit->field->val_string))
 646                 /* a string field forced to constant? */
 647                 is_useless = 0;
 648               else if (rule->search == decode_find_constants)
 649                 /* the string field isn't constant */
 650                 return 1;
 651               break;
 652             }
 653         }
 654     }
 655
 656   /* Given only one constant value has been found, check through all
 657      the instructions to see if at least one conditional makes it
 658      usefull */
 659   if (value >= 0 && is_useless)
 660     {
 661       for (entry = insns; entry != NULL; entry = entry->next)
 662         {
 663           insn_word_entry *word = entry->insn->word[rule->word_nr];
 664           insn_bit_entry *bit = word->bit[bit_nr];
 665           switch (bit->field->type)
 666             {
 667             case insn_field_invalid:
 668               ASSERT (0);
 669               break;
 670             case insn_field_wild:
 671             case insn_field_reserved:
 672             case insn_field_int:
 673               /* already processed */
 674               break;
 675             case insn_field_string:
 676               switch (rule->search)
 677                 {
 678                 case decode_find_strings:
 679                 case decode_find_constants:
 680                   /* already processed */
 681                   break;
 682                 case decode_find_mixed:
 683                   /* string field with conditions.  If this condition
 684                      eliminates the value then the compare is useful */
 685                   if (bit->field->conditions != NULL)
 686                     {
 687                       insn_field_cond *condition;
 688                       int shift = bit->field->last - bit_nr;
 689                       for (condition = bit->field->conditions;
 690                            condition != NULL;
 691                            condition = condition->next)
 692                         {
 693                           switch (condition->type)
 694                             {
 695                             case insn_field_cond_value:
 696                               switch (condition->test)
 697                                 {
 698                                 case insn_field_cond_ne:
 699                                   if (((condition->value >> shift) & 1)
 700                                       == (unsigned) value)
 701                                     /* conditional field excludes the
 702                                        current value */
 703                                     is_useless = 0;
 704                                   break;
 705                                 case insn_field_cond_eq:
 706                                   if (((condition->value >> shift) & 1)
 707                                       != (unsigned) value)
 708                                     /* conditional field requires the
 709                                        current value */
 710                                     is_useless = 0;
 711                                   break;
 712                                 }
 713                               break;
 714                             case insn_field_cond_field:
 715                               /* are these handled separatly? */
 716                               break;
 717                             }
 718                         }
 719                     }
 720                 }
 721             }
 722         }
 723     }
 724
 725   return is_useless;
 726 }
 727
 728
 729 /* go through a gen-table's list of instruction formats looking for a
 730    range of bits that meet the decode table RULEs requirements */
 731
 732 static opcode_field *
 733 gen_entry_find_opcode_field (insn_list *insns,
 734                              decode_table *rule,
 735                              int string_only)
 736 {
 737   opcode_field curr_opcode;
 738   ASSERT (rule != NULL);
 739
 740   memset (&curr_opcode, 0, sizeof (curr_opcode));
 741   curr_opcode.word_nr = rule->word_nr;
 742   curr_opcode.first = rule->first;
 743   curr_opcode.last = rule->last;
 744
 745   /* Try to reduce the size of first..last in accordance with the
 746      decode rules */
 747
 748   while (curr_opcode.first <= rule->last)
 749     {
 750       if (insns_bit_useless (insns, rule, curr_opcode.first))
 751         curr_opcode.first ++;
 752       else
 753         break;
 754     }
 755   while (curr_opcode.last >= rule->first)
 756     {
 757       if (insns_bit_useless (insns, rule, curr_opcode.last))
 758         curr_opcode.last --;
 759       else
 760         break;
 761     }
 762
 763
 764 #if 0
 765   for (entry = insns; entry != NULL; entry = entry->next)
 766     {
 767       insn_word_entry *fields = entry->insn->word[rule->word_nr];
 768       opcode_field new_opcode;
 769
 770       ASSERT (fields != NULL);
 771
 772       /* find a start point for the opcode field */
 773       new_opcode.first = rule->first;
 774       while (new_opcode.first <= rule->last
 775              && (!string_only
 776                  || (insn_field_is_constant(fields->bit[new_opcode.first], rule)
 777                      != field_constant_string))
 778              && (string_only
 779                  || (insn_field_is_constant(fields->bit[new_opcode.first], rule)
 780                      == field_is_not_constant)))
 781         {
 782           int new_first = fields->bit[new_opcode.first]->last + 1;
 783           ASSERT (new_first > new_opcode.first);
 784           new_opcode.first = new_first;
 785         }
 786       ASSERT(new_opcode.first > rule->last
 787              || (string_only
 788                  && insn_field_is_constant(fields->bit[new_opcode.first],
 789                                            rule) == field_constant_string)
 790              || (!string_only
 791                  && insn_field_is_constant(fields->bit[new_opcode.first],
 792                                            rule)));
 793
 794       /* find the end point for the opcode field */
 795       new_opcode.last = rule->last;
 796       while (new_opcode.last >= rule->first
 797              && (!string_only
 798                  || insn_field_is_constant(fields->bit[new_opcode.last],
 799                                            rule) != field_constant_string)
 800              && (string_only
 801                  || !insn_field_is_constant(fields->bit[new_opcode.last],
 802                                             rule)))
 803         {
 804           int new_last = fields->bit[new_opcode.last]->first - 1;
 805           ASSERT (new_last < new_opcode.last);
 806           new_opcode.last = new_last;
 807         }
 808       ASSERT(new_opcode.last < rule->first
 809              || (string_only
 810                  && insn_field_is_constant(fields->bit[new_opcode.last],
 811                                            rule) == field_constant_string)
 812              || (!string_only
 813                  && insn_field_is_constant(fields->bit[new_opcode.last],
 814                                            rule)));
 815
 816       /* now see if our current opcode needs expanding to include the
 817          interesting fields within this instruction */
 818       if (new_opcode.first <= rule->last
 819           && curr_opcode.first > new_opcode.first)
 820         curr_opcode.first = new_opcode.first;
 821       if (new_opcode.last >= rule->first
 822           && curr_opcode.last < new_opcode.last)
 823         curr_opcode.last = new_opcode.last;
 824
 825     }
 826 #endif
 827
 828   /* did the final opcode field end up being empty? */
 829   if (curr_opcode.first > curr_opcode.last)
 830     {
 831       return NULL;
 832     }
 833   ASSERT (curr_opcode.last >= rule->first);
 834   ASSERT (curr_opcode.first <= rule->last);
 835   ASSERT (curr_opcode.first <= curr_opcode.last);
 836
 837   /* Ensure that, for the non string only case, the opcode includes
 838      the range forced_first .. forced_last */
 839   if (!string_only
 840       && curr_opcode.first > rule->force_first)
 841     {
 842       curr_opcode.first = rule->force_first;
 843     }
 844   if (!string_only
 845       && curr_opcode.last < rule->force_last)
 846     {
 847       curr_opcode.last = rule->force_last;
 848     }
 849
 850   /* For the string only case, force just the lower bound (so that the
 851      shift can be eliminated) */
 852   if (string_only
 853       && rule->force_last == options.insn_bit_size - 1)
 854     {
 855       curr_opcode.last = options.insn_bit_size - 1;
 856     }
 857
 858   /* handle any special cases */
 859   switch (rule->type)
 860     {
 861     case normal_decode_rule:
 862       /* let the above apply */
 863       curr_opcode.nr_opcodes =
 864         (1 << (curr_opcode.last - curr_opcode.first + 1));
 865       break;
 866     case boolean_rule:
 867       curr_opcode.is_boolean = 1;
 868       curr_opcode.boolean_constant = rule->constant;
 869       curr_opcode.nr_opcodes = 2;
 870       break;
 871     }
 872
 873   {
 874     opcode_field *new_field = ZALLOC (opcode_field);
 875     memcpy (new_field, &curr_opcode, sizeof (opcode_field));
 876     return new_field;
 877   }
 878 }
 879
 880
 881 static void
 882 gen_entry_insert_insn (gen_entry *table,
 883                        insn_entry *old_insn,
 884                        int new_word_nr,
 885                        int new_nr_prefetched_words,
 886                        int new_opcode_nr,
 887                        opcode_bits *new_bits)
 888 {
 889   gen_entry **entry = &table->entries;
 890
 891   /* find the new table for this entry */
 892   while ((*entry) != NULL && (*entry)->opcode_nr < new_opcode_nr)
 893     {
 894       entry = &(*entry)->sibling;
 895     }
 896
 897   if ((*entry) == NULL || (*entry)->opcode_nr != new_opcode_nr)
 898     {
 899       /* insert the missing entry */
 900       gen_entry *new_entry = ZALLOC (gen_entry);
 901       new_entry->sibling = (*entry);
 902       (*entry) = new_entry;
 903       table->nr_entries++;
 904       /* fill it in */
 905       new_entry->top = table->top;
 906       new_entry->opcode_nr = new_opcode_nr;
 907       new_entry->word_nr = new_word_nr;
 908       new_entry->expanded_bits = new_bits;
 909       new_entry->opcode_rule = table->opcode_rule->next;
 910       new_entry->parent = table;
 911       new_entry->nr_prefetched_words = new_nr_prefetched_words;
 912     }
 913   /* ASSERT new_bits == cur_entry bits */
 914   ASSERT ((*entry) != NULL && (*entry)->opcode_nr == new_opcode_nr);
 915   insn_list_insert (&(*entry)->insns,
 916                     &(*entry)->nr_insns,
 917                     old_insn,
 918                     NULL, /* expanded_bits - only in final list */
 919                     NULL, /* opcodes - only in final list */
 920                     new_nr_prefetched_words, /* for this table */
 921                     report_duplicate_insns);
 922 }
 923
 924
 925 static void
 926 gen_entry_expand_opcode (gen_entry *table,
 927                          insn_entry *instruction,
 928                          int bit_nr,
 929                          int opcode_nr,
 930                          opcode_bits *bits)
 931 {
 932   if (bit_nr > table->opcode->last)
 933     {
 934       /* Only include the hardwired bit information with an entry IF
 935          that entry (and hence its functions) are being duplicated.  */
 936       if (options.trace.insn_expansion)
 937         {
 938           print_gen_entry_path (table->opcode_rule->line, table, notify);
 939           notify (NULL, ": insert %d - %s.%s%s\n",
 940                   opcode_nr,
 941                   instruction->format_name,
 942                   instruction->name,
 943                   (table->opcode_rule->with_duplicates ? " (duplicated)" : ""));
 944         }
 945       if (table->opcode_rule->with_duplicates)
 946         {
 947           gen_entry_insert_insn (table, instruction,
 948                                  table->opcode->word_nr,
 949                                  table->nr_prefetched_words,
 950                                  opcode_nr, bits);
 951         }
 952       else
 953         {
 954           gen_entry_insert_insn (table, instruction,
 955                                  table->opcode->word_nr,
 956                                  table->nr_prefetched_words,
 957                                  opcode_nr, NULL);
 958         }
 959     }
 960   else
 961     {
 962       insn_word_entry *word = instruction->word[table->opcode->word_nr];
 963       insn_field_entry *field = word->bit[bit_nr]->field;
 964       int last_pos = ((field->last < table->opcode->last)
 965                       ? field->last
 966                       : table->opcode->last);
 967       int first_pos = ((field->first > table->opcode->first)
 968                        ? field->first
 969                        : table->opcode->first);
 970       int width = last_pos - first_pos + 1;
 971       switch (field->type)
 972         {
 973         case insn_field_int:
 974           {
 975             int val;
 976             val = sub_val (field->val_int, field->last,
 977                            first_pos, last_pos);
 978             gen_entry_expand_opcode (table, instruction,
 979                                      last_pos + 1,
 980                                      ((opcode_nr << width) | val),
 981                                      bits);
 982             break;
 983           }
 984         default:
 985           {
 986             if (field->type == insn_field_reserved)
 987               gen_entry_expand_opcode (table, instruction,
 988                                        last_pos + 1,
 989                                        ((opcode_nr << width)),
 990                                        bits);
 991             else
 992               {
 993                 int val;
 994                 int last_val = (table->opcode->is_boolean
 995                                 ? 2
 996                                 : (1 << width));
 997                 for (val = 0; val < last_val; val++)
 998                   {
 999                     /* check to see if the value has been precluded
1000                        (by a conditional) in some way */
1001                     int is_precluded;
1002                     insn_field_cond *condition;
1003                     for (condition = field->conditions, is_precluded = 0;
1004                          condition != NULL && !is_precluded;
1005                          condition = condition->next)
1006                       {
1007                         switch (condition->type)
1008                           {
1009                           case insn_field_cond_value:
1010                             {
1011                               int value = sub_val (condition->value, field->last,
1012                                                    first_pos, last_pos);
1013                               switch (condition->test)
1014                                 {
1015                                 case insn_field_cond_ne:
1016                                   if (value == val)
1017                                     is_precluded = 1;
1018                                   break;
1019                                 case insn_field_cond_eq:
1020                                   if (value != val)
1021                                     is_precluded = 1;
1022                                   break;
1023                                 }
1024                               break;
1025                             }
1026                           case insn_field_cond_field:
1027                             {
1028                               int value;
1029                               opcode_bits *bit;
1030                               gen_entry *t;
1031                               /* Try to find a value for the
1032                                  conditional by looking back through
1033                                  the previously defined bits for one
1034                                  that covers the designated
1035                                  conditional field */
1036                               for (bit = bits;
1037                                    bit != NULL;
1038                                    bit = bit->next)
1039                                 {
1040                                   if (bit->field->word_nr == condition->field->word_nr
1041                                       && bit->first <= condition->field->first
1042                                       && bit->last >= condition->field->last)
1043                                     {
1044                                       /* the bit field fully specified
1045                                          the conditional field's value */
1046                                       value = sub_val (bit->value, bit->last,
1047                                                        condition->field->first,
1048                                                        condition->field->last);
1049                                     }
1050                                 }
1051                               /* Try to find a value by looking
1052                                  through this and previous tables */
1053                               if (bit == NULL)
1054                                 {
1055                                   for (t = table;
1056                                        t->parent != NULL;
1057                                        t = t->parent)
1058                                     {
1059                                       if (t->parent->opcode->word_nr == condition->field->word_nr
1060                                           && t->parent->opcode->first <= condition->field->first
1061                                           && t->parent->opcode->last >= condition->field->last)
1062                                         {
1063                                           /* the table entry fully
1064                                              specified the condition
1065                                              field's value */
1066                                           /* extract the field's value
1067                                              from the opcode */
1068                                           value = sub_val (t->opcode_nr, t->parent->opcode->last,
1069                                                            condition->field->first, condition->field->last);
1070                                           /* this is a requirement of
1071                                              a conditonal field
1072                                              refering to another field */
1073                                           ASSERT ((condition->field->first - condition->field->last)
1074                                                   == (first_pos - last_pos));
1075 printf ("value=%d, opcode_nr=%d, last=%d, [%d..%d]\n",
1076         value, t->opcode_nr, t->parent->opcode->last, condition->field->first, condition->field->last);
1077                                         }
1078                                     }
1079                                 }
1080                               if (bit == NULL && t == NULL)
1081                                 error (instruction->line,
1082                                        "Conditional `%s' of field `%s' isn't expanded",
1083                                        condition->string, field->val_string);
1084                               switch (condition->test)
1085                                 {
1086                                 case insn_field_cond_ne:
1087                                   if (value == val)
1088                                     is_precluded = 1;
1089                                   break;
1090                                 case insn_field_cond_eq:
1091                                   if (value != val)
1092                                     is_precluded = 1;
1093                                   break;
1094                                 }
1095                               break;
1096                             }
1097                           }
1098                       }
1099                     if (!is_precluded)
1100                       {
1101                         /* Only add additional hardwired bit
1102                            information if the entry is not going to
1103                            later be combined */
1104                         if (table->opcode_rule->with_combine)
1105                           {
1106                             gen_entry_expand_opcode (table, instruction,
1107                                                      last_pos + 1,
1108                                                      ((opcode_nr << width) | val),
1109                                                      bits);
1110                           }
1111                         else
1112                           {
1113                             opcode_bits *new_bits = new_opcode_bits (bits, val,
1114                                                                      first_pos, last_pos,
1115                                                                      field,
1116                                                                      table->opcode);
1117                             gen_entry_expand_opcode (table, instruction,
1118                                                      last_pos + 1,
1119                                                      ((opcode_nr << width) | val),
1120                                                      new_bits);
1121                           }
1122                       }
1123                   }
1124               }
1125           }
1126         }
1127     }
1128 }
1129
1130 static void
1131 gen_entry_insert_expanding (gen_entry *table,
1132                             insn_entry *instruction)
1133 {
1134   gen_entry_expand_opcode (table,
1135                            instruction,
1136                            table->opcode->first,
1137                            0,
1138                            table->expanded_bits);
1139 }
1140
1141
1142 static int
1143 insns_match_format_names (insn_list *insns,
1144                           filter *format_names)
1145 {
1146   if (format_names != NULL)
1147     {
1148       insn_list *i;
1149       for (i = insns; i != NULL; i = i->next)
1150         {
1151           if ( i->insn->format_name != NULL
1152                && !filter_is_member (format_names, i->insn->format_name))
1153             return 0;
1154         }
1155     }
1156   return 1;
1157 }
1158
1159 static int
1160 table_matches_path (gen_entry *table,
1161                     decode_path_list *paths)
1162 {
1163   if (paths == NULL)
1164     return 1;
1165   while (paths != NULL)
1166     {
1167       gen_entry *entry = table;
1168       decode_path *path = paths->path;
1169       while (1)
1170         {
1171           if (entry == NULL && path == NULL)
1172             return 1;
1173           if (entry == NULL || path == NULL)
1174             break;
1175           if (entry->opcode_nr != path->opcode_nr)
1176             break;
1177           entry = entry->parent;
1178           path = path->parent;
1179         }
1180       paths = paths->next;
1181     }
1182   return 0;
1183 }
1184
1185
1186 static int
1187 insns_match_conditions (insn_list *insns,
1188                         decode_cond *conditions)
1189 {
1190   if (conditions != NULL)
1191     {
1192       insn_list *i;
1193       for (i = insns; i != NULL; i = i->next)
1194         {
1195           decode_cond *cond;
1196           for (cond = conditions; cond != NULL; cond = cond->next)
1197             {
1198               int bit_nr;
1199               if (i->insn->nr_words <= cond->word_nr)
1200                 return 0;
1201               for (bit_nr = 0; bit_nr < options.insn_bit_size; bit_nr++)
1202                 {
1203                   if (!cond->mask[bit_nr])
1204                     continue;
1205                   if (!i->insn->word[cond->word_nr]->bit[bit_nr]->mask)
1206                     return 0;
1207                   if ((i->insn->word[cond->word_nr]->bit[bit_nr]->value
1208                        == cond->value[bit_nr])
1209                       == !cond->is_equal)
1210                     return 0;
1211                 }
1212             }
1213         }
1214     }
1215   return 1;
1216 }
1217
1218 static int
1219 insns_match_nr_words (insn_list *insns,
1220                       int nr_words)
1221 {
1222   insn_list *i;
1223   for (i = insns; i != NULL; i = i->next)
1224     {
1225       if (i->insn->nr_words < nr_words)
1226         return 0;
1227     }
1228   return 1;
1229 }
1230
1231 static int
1232 insn_list_cmp (insn_list *l,
1233                insn_list *r)
1234 {
1235   while (1)
1236     {
1237       insn_entry *insn;
1238       if (l == NULL && r == NULL)
1239         return 0;
1240       if (l == NULL)
1241         return -1;
1242       if (r == NULL)
1243         return 1;
1244       if (l->insn != r->insn)
1245         return -1; /* somewhat arbitrary at present */
1246       /* skip this insn */
1247       insn = l->insn;
1248       while (l != NULL && l->insn == insn)
1249         l = l->next;
1250       while (r != NULL && r->insn == insn)
1251         r = r->next;
1252     }
1253 }
1254
1255
1256
1257 static void
1258 gen_entry_expand_insns (gen_entry *table)
1259 {
1260   decode_table *opcode_rule;
1261
1262   ASSERT(table->nr_insns >= 1);
1263
1264   /* determine a valid opcode */
1265   for (opcode_rule = table->opcode_rule;
1266        opcode_rule != NULL;
1267        opcode_rule = opcode_rule->next)
1268     {
1269       char *discard_reason;
1270       if (table->top->model != NULL
1271           && opcode_rule->model_names != NULL
1272           && !filter_is_member (opcode_rule->model_names,
1273                                 table->top->model->name))
1274         {
1275           /* the rule isn't applicable to this processor */
1276           discard_reason = "wrong model";
1277         }
1278       else if (table->nr_insns == 1 && opcode_rule->conditions == NULL)
1279         {
1280           /* for safety, require a pre-codition when attempting to
1281              apply a rule to a single instruction */
1282           discard_reason = "need pre-condition when nr-insn == 1";
1283         }
1284       else if (table->nr_insns == 1 && !opcode_rule->with_duplicates)
1285         {
1286           /* Little point in expanding a single instruction when we're
1287              not duplicating the semantic functions that this table
1288              calls */
1289           discard_reason = "need duplication with nr-insns == 1";
1290         }
1291       else if (!insns_match_format_names (table->insns, opcode_rule->format_names))
1292         {
1293           discard_reason = "wrong format name";
1294         }
1295       else if (!insns_match_nr_words (table->insns, opcode_rule->word_nr + 1))
1296         {
1297           discard_reason = "wrong nr words";
1298         }
1299       else if (!table_matches_path (table, opcode_rule->paths))
1300         {
1301           discard_reason = "path failed";
1302         }
1303       else if (!insns_match_conditions (table->insns, opcode_rule->conditions))
1304         {
1305           discard_reason = "condition failed";
1306         }
1307       else
1308         {
1309           discard_reason = "no opcode field";
1310           table->opcode =
1311             gen_entry_find_opcode_field (table->insns,
1312                                          opcode_rule,
1313                                          table->nr_insns == 1/*string-only*/
1314                                          );
1315           if (table->opcode != NULL)
1316             {
1317               table->opcode_rule = opcode_rule;
1318               break;
1319             }
1320         }
1321
1322       if (options.trace.rule_rejection)
1323         {
1324           print_gen_entry_path (opcode_rule->line, table, notify);
1325           notify (NULL, ": rule discarded - %s\n", discard_reason);
1326         }
1327     }
1328
1329   /* did we find anything */
1330   if (opcode_rule == NULL)
1331     {
1332       /* the decode table failed, this set of instructions haven't
1333          been uniquely identified */
1334       if (table->nr_insns > 1)
1335         {
1336           print_gen_entry_insns (table, warning,
1337                                  "was not uniquely decoded",
1338                                  "decodes to the same entry");
1339           error (NULL, "");
1340         }
1341       return;
1342     }
1343
1344   /* Determine the number of words that must have been prefetched for
1345      this table to function */
1346   if (table->parent == NULL)
1347     table->nr_prefetched_words = table->opcode_rule->word_nr + 1;
1348   else if (table->opcode_rule->word_nr + 1 > table->parent->nr_prefetched_words)
1349     table->nr_prefetched_words = table->opcode_rule->word_nr + 1;
1350   else
1351     table->nr_prefetched_words = table->parent->nr_prefetched_words;
1352
1353   /* back link what we found to its parent */
1354   if (table->parent != NULL)
1355     {
1356       ASSERT(table->parent->opcode != NULL);
1357       table->opcode->parent = table->parent->opcode;
1358     }
1359
1360   /* report the rule being used to expand the instructions */
1361   if (options.trace.rule_selection)
1362     {
1363       print_gen_entry_path (table->opcode_rule->line, table, notify);
1364       notify (NULL,
1365               ": decode - word %d, bits [%d..%d] in [%d..%d], opcodes %d, entries %d\n",
1366               table->opcode->word_nr,
1367               i2target (options.hi_bit_nr, table->opcode->first),
1368               i2target (options.hi_bit_nr, table->opcode->last),
1369               i2target (options.hi_bit_nr, table->opcode_rule->first),
1370               i2target (options.hi_bit_nr, table->opcode_rule->last),
1371               table->opcode->nr_opcodes,
1372               table->nr_entries);
1373     }
1374
1375   /* expand the raw instructions according to the opcode */
1376   {
1377     insn_list *entry;
1378     for (entry = table->insns; entry != NULL; entry = entry->next)
1379       {
1380         if (options.trace.insn_expansion)
1381           {
1382             print_gen_entry_path (table->opcode_rule->line, table, notify);
1383             notify (NULL, ": expand - %s.%s\n",
1384                     entry->insn->format_name,
1385                     entry->insn->name);
1386           }
1387         gen_entry_insert_expanding (table, entry->insn);
1388       }
1389   }
1390
1391   /* dump the results */
1392   if (options.trace.entries)
1393     {
1394       gen_entry *entry;
1395       for (entry = table->entries; entry != NULL; entry = entry->sibling)
1396         {
1397           insn_list *l;
1398           print_gen_entry_path (table->opcode_rule->line, entry, notify);
1399           notify (NULL, ": %d - entries %d -",
1400                   entry->opcode_nr,
1401                   entry->nr_insns);
1402           for (l = entry->insns; l != NULL; l = l->next)
1403             notify (NULL, " %s.%s", l->insn->format_name, l->insn->name);
1404           notify (NULL, "\n");
1405         }
1406     }
1407
1408   /* perform a combine pass if needed */
1409   if (table->opcode_rule->with_combine)
1410     {
1411       gen_entry *entry;
1412       for (entry = table->entries; entry != NULL; entry = entry->sibling)
1413         {
1414           if (entry->combined_parent == NULL)
1415             {
1416               gen_entry **last = &entry->combined_next;
1417               gen_entry *alt;
1418               for (alt = entry->sibling; alt != NULL; alt = alt->sibling)
1419                 {
1420                   if (alt->combined_parent == NULL
1421                       && insn_list_cmp (entry->insns, alt->insns) == 0)
1422                     {
1423                       alt->combined_parent = entry;
1424                       *last = alt;
1425                       last = &alt->combined_next;
1426                     }
1427                 }
1428             }
1429         }
1430       if (options.trace.combine)
1431         {
1432           int nr_unique = 0;
1433           gen_entry *entry;
1434           for (entry = table->entries; entry != NULL; entry = entry->sibling)
1435             {
1436               if (entry->combined_parent == NULL)
1437                 {
1438                   insn_list *l;
1439                   gen_entry *duplicate;
1440                   nr_unique++;
1441                   print_gen_entry_path (table->opcode_rule->line, entry, notify);
1442                   for (duplicate = entry->combined_next;
1443                        duplicate != NULL;
1444                        duplicate = duplicate->combined_next)
1445                     {
1446                       notify (NULL, "+%d", duplicate->opcode_nr);
1447                     }
1448                   notify (NULL, ": entries %d -", entry->nr_insns);
1449                   for (l = entry->insns; l != NULL; l = l->next)
1450                     {
1451                       notify (NULL, " %s.%s",
1452                               l->insn->format_name,
1453                               l->insn->name);
1454                     }
1455                   notify (NULL, "\n");
1456                 }
1457             }
1458           print_gen_entry_path (table->opcode_rule->line, table, notify);
1459           notify (NULL, ": combine - word %d, bits [%d..%d] in [%d..%d], opcodes %d, entries %d, unique %d\n",
1460                   table->opcode->word_nr,
1461                   i2target (options.hi_bit_nr, table->opcode->first),
1462                   i2target (options.hi_bit_nr, table->opcode->last),
1463                   i2target (options.hi_bit_nr, table->opcode_rule->first),
1464                   i2target (options.hi_bit_nr, table->opcode_rule->last),
1465                   table->opcode->nr_opcodes,
1466                   table->nr_entries,
1467                   nr_unique);
1468         }
1469     }
1470
1471   /* Check that the rule did more than re-arange the order of the
1472      instructions */
1473   {
1474       gen_entry *entry;
1475       for (entry = table->entries; entry != NULL; entry = entry->sibling)
1476         {
1477           if (entry->combined_parent == NULL)
1478             {
1479               if (insn_list_cmp (table->insns, entry->insns) == 0)
1480                 {
1481                   print_gen_entry_path (table->opcode_rule->line, table, warning);
1482                   warning (NULL, ": Applying rule just copied all instructions\n");
1483                   print_gen_entry_insns (entry, warning, "Copied", NULL);
1484                   error (NULL, "");
1485                 }
1486             }
1487         }
1488   }
1489
1490   /* if some form of expanded table, fill in the missing dots */
1491   switch (table->opcode_rule->gen)
1492     {
1493     case padded_switch_gen:
1494     case array_gen:
1495     case goto_switch_gen:
1496       if (!table->opcode->is_boolean)
1497         {
1498           gen_entry **entry = &table->entries;
1499           gen_entry *illegals = NULL;
1500           gen_entry **last_illegal = &illegals;
1501           int opcode_nr = 0;
1502           while (opcode_nr < table->opcode->nr_opcodes)
1503             {
1504               if ((*entry) == NULL || (*entry)->opcode_nr != opcode_nr)
1505                 {
1506                   /* missing - insert it under our feet at *entry */
1507                   gen_entry_insert_insn (table,
1508                                          table->top->isa->illegal_insn,
1509                                          table->opcode->word_nr,
1510                                          0, /* nr_prefetched_words == 0 for invalid */
1511                                          opcode_nr, NULL);
1512                   ASSERT ((*entry) != NULL);
1513                   ASSERT ((*entry)->opcode_nr == opcode_nr);
1514                   (*last_illegal) = *entry;
1515                   (*last_illegal)->combined_parent = illegals;
1516                   last_illegal = &(*last_illegal)->combined_next;
1517                 }
1518               entry = &(*entry)->sibling;
1519               opcode_nr++;
1520             }
1521           /* oops, will have pointed the first illegal insn back to
1522              its self.  Fix this */
1523           if (illegals != NULL)
1524             illegals->combined_parent = NULL;
1525         }
1526       break;
1527     case switch_gen:
1528     case invalid_gen:
1529       /* ignore */
1530       break;
1531     }
1532
1533   /* and do the same for the newly created sub entries but *only*
1534      expand entries that haven't been combined. */
1535   {
1536     gen_entry *entry;
1537     for (entry = table->entries; entry != NULL; entry =  entry->sibling)
1538       {
1539         if (entry->combined_parent == NULL)
1540           {
1541             gen_entry_expand_insns (entry);
1542           }
1543       }
1544   }
1545 }
1546
1547 void
1548 gen_tables_expand_insns (gen_table *gen)
1549 {
1550   gen_list *entry;
1551   for (entry = gen->tables; entry != NULL; entry = entry->next)
1552     {
1553       gen_entry_expand_insns (entry->table);
1554     }
1555 }
1556
1557
1558 /* create a list of all the semantic functions that need to be
1559    generated.  Eliminate any duplicates. Verify that the decode stage
1560    worked. */
1561
1562 static void
1563 make_gen_semantics_list (lf *file,
1564                          gen_entry *entry,
1565                          int depth,
1566                          void *data)
1567 {
1568   gen_table *gen = (gen_table*) data;
1569   insn_list *insn;
1570   /* Not interested in an entrie that have been combined into some
1571      other entry at the same level */
1572   if (entry->combined_parent != NULL)
1573     return;
1574
1575   /* a leaf should contain exactly one instruction. If not the decode
1576      stage failed. */
1577   ASSERT (entry->nr_insns == 1);
1578
1579   /* Enter this instruction into the list of semantic functions. */
1580   insn = insn_list_insert (&gen->semantics, &gen->nr_semantics,
1581                            entry->insns->insn,
1582                            entry->expanded_bits,
1583                            entry->parent->opcode,
1584                            entry->insns->nr_prefetched_words,
1585                            merge_duplicate_insns);
1586   /* point the table entry at the real semantic function */
1587   ASSERT (insn != NULL);
1588   entry->insns->semantic = insn;
1589 }
1590
1591
1592 void
1593 gen_tables_expand_semantics (gen_table *gen)
1594 {
1595   gen_list *entry;
1596   for (entry = gen->tables; entry != NULL; entry = entry->next)
1597     {
1598       gen_entry_traverse_tree (NULL,
1599                                entry->table,
1600                                1, /* depth */
1601                                NULL, /* start-handler */
1602                                make_gen_semantics_list, /* leaf-handler */
1603                                NULL, /* end-handler */
1604                                gen); /* data */
1605   }
1606 }
1607
1608
1609
1610 #ifdef MAIN
1611
1612
1613 static void
1614 dump_opcode_field (lf *file,
1615                    char *prefix,
1616                    opcode_field *field,
1617                    char *suffix,
1618                    int levels)
1619 {
1620   lf_printf (file, "%s(opcode_field *) 0x%lx", prefix, (long) field);
1621   if (levels && field != NULL) {
1622     lf_indent (file, +1);
1623     lf_printf (file, "\n(first %d)", field->first);
1624     lf_printf (file, "\n(last %d)", field->last);
1625     lf_printf (file, "\n(nr_opcodes %d)", field->nr_opcodes);
1626     lf_printf (file, "\n(is_boolean %d)", field->is_boolean);
1627     lf_printf (file, "\n(boolean_constant %d)", field->boolean_constant);
1628     dump_opcode_field(file, "\n(parent ", field->parent, ")", levels - 1);
1629     lf_indent (file, -1);
1630   }
1631   lf_printf (file, "%s", suffix);
1632 }
1633
1634
1635 static void
1636 dump_opcode_bits (lf *file,
1637                   char *prefix,
1638                   opcode_bits *bits,
1639                   char *suffix,
1640                   int levels)
1641 {
1642   lf_printf (file, "%s(opcode_bits *) 0x%lx", prefix, (long) bits);
1643
1644   if (levels && bits != NULL)
1645     {
1646       lf_indent (file, +1);
1647       lf_printf (file, "\n(value %d)", bits->value);
1648       dump_opcode_field (file, "\n(opcode ", bits->opcode, ")", 0);
1649       dump_insn_field (file, "\n(field ", bits->field, ")");
1650       dump_opcode_bits (file, "\n(next ", bits->next, ")", levels - 1);
1651       lf_indent (file, -1);
1652     }
1653   lf_printf (file, "%s", suffix);
1654 }
1655
1656
1657
1658 static void
1659 dump_insn_list (lf *file,
1660                 char *prefix,
1661                 insn_list *entry,
1662                 char *suffix)
1663 {
1664   lf_printf (file, "%s(insn_list *) 0x%lx", prefix, (long) entry);
1665
1666   if (entry != NULL) {
1667     lf_indent (file, +1);
1668     dump_insn_entry (file, "\n(insn ", entry->insn, ")");
1669     lf_printf (file, "\n(next 0x%lx)", (long) entry->next);
1670     lf_indent (file, -1);
1671   }
1672   lf_printf (file, "%s", suffix);
1673 }
1674
1675
1676 static void
1677 dump_insn_word_entry_list_entries (lf *file,
1678                                char *prefix,
1679                                insn_list *entry,
1680                                char *suffix)
1681 {
1682   lf_printf (file, "%s", prefix);
1683   while (entry != NULL)
1684     {
1685       dump_insn_list (file, "\n(", entry, ")");
1686       entry = entry->next;
1687     }
1688   lf_printf (file, "%s", suffix);
1689 }
1690
1691
1692 static void
1693 dump_gen_entry (lf *file,
1694                 char *prefix,
1695                 gen_entry *table,
1696                 char *suffix,
1697                 int levels)
1698 {
1699
1700   lf_printf (file, "%s(gen_entry *) 0x%lx", prefix, (long) table);
1701
1702   if (levels && table != NULL) {
1703
1704     lf_indent (file, +1);
1705     lf_printf (file, "\n(opcode_nr %d)", table->opcode_nr);
1706     lf_printf (file, "\n(word_nr %d)", table->word_nr);
1707     dump_opcode_bits (file, "\n(expanded_bits ", table->expanded_bits, ")", -1);
1708     lf_printf (file, "\n(nr_insns %d)", table->nr_insns);
1709     dump_insn_word_entry_list_entries (file, "\n(insns ", table->insns, ")");
1710     dump_decode_rule (file, "\n(opcode_rule ", table->opcode_rule, ")");
1711     dump_opcode_field (file, "\n(opcode ", table->opcode, ")", 0);
1712     lf_printf (file, "\n(nr_entries %d)", table->nr_entries);
1713     dump_gen_entry (file, "\n(entries ", table->entries, ")", table->nr_entries);
1714     dump_gen_entry (file, "\n(sibling ", table->sibling, ")", levels - 1);
1715     dump_gen_entry (file, "\n(parent ", table->parent, ")", 0);
1716     lf_indent (file, -1);
1717   }
1718   lf_printf (file, "%s", suffix);
1719 }
1720
1721 static void
1722 dump_gen_list (lf *file,
1723                char *prefix,
1724                gen_list *entry,
1725                char *suffix,
1726                int levels)
1727 {
1728   while (entry != NULL)
1729     {
1730       lf_printf (file, "%s(gen_list *) 0x%lx", prefix, (long) entry);
1731       dump_gen_entry (file, "\n(", entry->table, ")", levels);
1732       lf_printf (file, "\n(next (gen_list *) 0x%lx)", (long) entry->next);
1733       lf_printf (file, "%s", suffix);
1734     }
1735 }
1736
1737
1738 static void
1739 dump_gen_table (lf *file,
1740                 char *prefix,
1741                 gen_table *gen,
1742                 char *suffix,
1743                 int levels)
1744 {
1745   lf_printf (file, "%s(gen_table *) 0x%lx", prefix, (long) gen);
1746   lf_printf (file, "\n(isa (insn_table *) 0x%lx)", (long) gen->isa);
1747   lf_printf (file, "\n(rules (decode_table *) 0x%lx)", (long) gen->rules);
1748   dump_gen_list (file, "\n(", gen->tables, ")", levels);
1749   lf_printf (file, "%s", suffix);
1750 }
1751
1752
1753 igen_options options;
1754
1755 int
1756 main (int argc,
1757       char **argv)
1758 {
1759   decode_table *decode_rules;
1760   insn_table *instructions;
1761   gen_table *gen;
1762   lf *l;
1763
1764   if (argc != 7)
1765     error (NULL, "Usage: insn <filter-in> <hi-bit-nr> <insn-bit-size> <widths> <decode-table> <insn-table>\n");
1766
1767   INIT_OPTIONS (options);
1768
1769   filter_parse (&options.flags_filter, argv[1]);
1770
1771   options.hi_bit_nr = a2i(argv[2]);
1772   options.insn_bit_size = a2i(argv[3]);
1773   options.insn_specifying_widths = a2i(argv[4]);
1774   ASSERT(options.hi_bit_nr < options.insn_bit_size);
1775
1776   instructions = load_insn_table (argv[6], NULL);
1777   decode_rules = load_decode_table (argv[5]);
1778   gen = make_gen_tables (instructions, decode_rules);
1779
1780   gen_tables_expand_insns (gen);
1781
1782   l = lf_open ("-", "stdout", lf_omit_references, lf_is_text, "tmp-ld-insn");
1783
1784   dump_gen_table (l, "(", gen, ")\n", -1);
1785   return 0;
1786 }
1787
1788 #endif