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          insn_field_entry *field,
  35          int first_pos,
  36          int last_pos)
  37 {
  38   return ((val >> (field->last - 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->processor != NULL)
  77         print (line, "%s", table->top->processor);
  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
 111 /* same as strcmp */
 112 static int
 113 insn_word_cmp (insn_word_entry *l, insn_word_entry *r)
 114 {
 115   while (1)
 116     {
 117       int bit_nr;
 118       if (l == NULL && r == NULL)
 119         return 0; /* all previous fields the same */
 120       if (l == NULL)
 121         return -1; /* left shorter than right */
 122       if (r == NULL)
 123         return +1; /* left longer than right */
 124       for (bit_nr = 0;
 125            bit_nr < options.insn_bit_size;
 126            bit_nr++)
 127         {
 128           if (l->bit[bit_nr]->mask < r->bit[bit_nr]->mask)
 129             return -1;
 130           if (l->bit[bit_nr]->mask > r->bit[bit_nr]->mask)
 131             return 1;
 132           if (l->bit[bit_nr]->value < r->bit[bit_nr]->value)
 133             return -1;
 134           if (l->bit[bit_nr]->value > r->bit[bit_nr]->value)
 135             return 1;
 136         }
 137       l = l->next;
 138       r = r->next;
 139     }
 140 }
 141
 142 static int
 143 opcode_bit_cmp (opcode_bits *l,
 144                 opcode_bits *r)
 145 {
 146   if (l == NULL && r == NULL)
 147     return 0; /* all previous bits the same */
 148   if (l == NULL)
 149     return -1; /* left shorter than right */
 150   if (r == NULL)
 151     return +1; /* left longer than right */
 152   /* most significant word */
 153   if (l->field->word_nr < r->field->word_nr)
 154     return +1; /* left has more significant word */
 155   if (l->field->word_nr > r->field->word_nr)
 156     return -1; /* right has more significant word */
 157   /* most significant bit? */
 158   if (l->first < r->first)
 159     return +1; /* left as more significant bit */
 160   if (l->first > r->first)
 161     return -1; /* right as more significant bit */
 162   /* nr bits? */
 163   if (l->last < r->last)
 164     return +1; /* left as less bits */
 165   if (l->last > r->last)
 166     return -1; /* right as less bits */
 167   /* value? */
 168   if (l->value < r->value)
 169     return -1;
 170   if (l->value > r->value)
 171     return 1;
 172   return 0;
 173 }
 174
 175 static int
 176 opcode_bits_cmp (opcode_bits *l,
 177                  opcode_bits *r)
 178 {
 179   while (1)
 180     {
 181       int cmp;
 182       if (l == NULL && r == NULL)
 183         return 0; /* all previous bits the same */
 184       cmp = opcode_bit_cmp (l, r);
 185       if (cmp != 0)
 186         return cmp;
 187       l = l->next;
 188       r = r->next;
 189     }
 190 }
 191
 192 static opcode_bits *
 193 new_opcode_bits (opcode_bits *old_bits,
 194                  int value,
 195                  int first,
 196                  int last,
 197                  insn_field_entry *field,
 198                  opcode_field *opcode)
 199 {
 200   opcode_bits *new_bits = ZALLOC (opcode_bits);
 201   new_bits->field = field;
 202   new_bits->value = value;
 203   new_bits->first = first;
 204   new_bits->last = last;
 205   new_bits->opcode = opcode;
 206
 207   if (old_bits != NULL)
 208     {
 209       opcode_bits *new_list;
 210       opcode_bits **last = &new_list;
 211       new_list = new_opcode_bits (old_bits->next,
 212                                   old_bits->value,
 213                                   old_bits->first,
 214                                   old_bits->last,
 215                                   old_bits->field,
 216                                   old_bits->opcode);
 217       while (*last != NULL)
 218         {
 219           int cmp = opcode_bit_cmp (new_bits, *last);
 220           if (cmp < 0) /* new < new_list */
 221             {
 222               break;
 223             }
 224           if (cmp == 0)
 225             {
 226               ERROR ("Duplicated insn bits in list");
 227             }
 228           last = &(*last)->next;
 229         }
 230       new_bits->next = *last;
 231       *last = new_bits;
 232       return new_list;
 233     }
 234   else
 235     {
 236       return new_bits;
 237     }
 238 }
 239
 240
 241
 242
 243 typedef enum {
 244   merge_duplicate_insns,
 245   report_duplicate_insns,
 246 } duplicate_insn_actions;
 247
 248 static insn_list *
 249 insn_list_insert (insn_list **cur_insn_ptr,
 250                   int *nr_insns,
 251                   insn_entry *insn,
 252                   opcode_bits *expanded_bits,
 253                   opcode_field *opcodes,
 254                   int nr_prefetched_words,
 255                   duplicate_insn_actions duplicate_action)
 256 {
 257   /* insert it according to the order of the fields & bits */
 258   while ((*cur_insn_ptr) != NULL)
 259     {
 260       int word_cmp = insn_word_cmp (insn->words,
 261                                     (*cur_insn_ptr)->insn->words);
 262       if (word_cmp < 0)
 263         {
 264           /* found insertion point - new_insn < cur_insn->next */
 265           break;
 266         }
 267       else if (word_cmp == 0)
 268         {
 269           /* words same, try for bit fields */
 270           int bit_cmp = opcode_bits_cmp (expanded_bits,
 271                                          (*cur_insn_ptr)->expanded_bits);
 272           if (bit_cmp < 0)
 273             {
 274               /* found insertion point - new_insn < cur_insn->next */
 275               break;
 276             }
 277           else if (bit_cmp == 0)
 278             {
 279               switch (duplicate_action)
 280                 {
 281                 case report_duplicate_insns:
 282                   /* two instructions with the same constant field
 283                      values across all words and bits */
 284                   warning (insn->line,
 285                            "Location of second (duplicated?) instruction");
 286                   error ((*cur_insn_ptr)->insn->line,
 287                          "Two instructions with identical constant fields\n");
 288                 case merge_duplicate_insns:
 289                   /* Add the opcode path to the instructions list */
 290                   if (opcodes != NULL)
 291                     {
 292                       insn_opcodes **last = &(*cur_insn_ptr)->opcodes;
 293                       while (*last != NULL)
 294                         {
 295                           last = &(*last)->next;
 296                         }
 297                       (*last) = ZALLOC (insn_opcodes);
 298                       (*last)->opcode = opcodes;
 299                     }
 300                   /* Use the larger nr_prefetched_words */
 301                   if ((*cur_insn_ptr)->nr_prefetched_words < nr_prefetched_words)
 302                     (*cur_insn_ptr)->nr_prefetched_words = nr_prefetched_words;
 303                   return (*cur_insn_ptr);
 304                 }
 305             }
 306         }
 307       /* keep looking - new_insn > cur_insn->next */
 308       cur_insn_ptr = &(*cur_insn_ptr)->next;
 309     }
 310
 311   /* create a new list entry and insert it */
 312   {
 313     insn_list *new_insn = ZALLOC (insn_list);
 314     new_insn->insn = insn;
 315     new_insn->expanded_bits = expanded_bits;
 316     new_insn->next = (*cur_insn_ptr);
 317     new_insn->nr_prefetched_words = nr_prefetched_words;
 318     if (opcodes != NULL)
 319       {
 320         new_insn->opcodes = ZALLOC (insn_opcodes);
 321         new_insn->opcodes->opcode = opcodes;
 322       }
 323     (*cur_insn_ptr) = new_insn;
 324   }
 325
 326   *nr_insns += 1;
 327
 328   return (*cur_insn_ptr);
 329 }
 330
 331
 332 extern void
 333 gen_entry_traverse_tree (lf *file,
 334                          gen_entry *table,
 335                          int depth,
 336                          gen_entry_handler *start,
 337                          gen_entry_handler *leaf,
 338                          gen_entry_handler *end,
 339                          void *data)
 340 {
 341   gen_entry *entry;
 342
 343   ASSERT (table != NULL);
 344   ASSERT (table->opcode != NULL);
 345   ASSERT (table->nr_entries > 0);
 346   ASSERT (table->entries != 0);
 347
 348   /* prefix */
 349   if (start != NULL && depth >= 0)
 350     {
 351       start (file, table, depth, data);
 352     }
 353   /* infix leaves */
 354   for (entry = table->entries;
 355        entry != NULL;
 356        entry = entry->sibling)
 357     {
 358       if (entry->entries != NULL && depth != 0)
 359         {
 360           gen_entry_traverse_tree (file, entry, depth + 1,
 361                                    start, leaf, end, data);
 362         }
 363       else if (depth >= 0)
 364         {
 365           if (leaf != NULL)
 366             {
 367               leaf (file, entry, depth, data);
 368             }
 369         }
 370     }
 371   /* postfix */
 372   if (end != NULL && depth >= 0)
 373     {
 374       end (file, table, depth, data);
 375     }
 376 }
 377
 378
 379
 380 /* create a list element containing a single gen_table entry */
 381
 382 static gen_list *
 383 make_table (insn_table *isa,
 384             decode_table *rules,
 385             char *processor)
 386 {
 387   insn_entry *insn;
 388   gen_list *entry = ZALLOC (gen_list);
 389   entry->table = ZALLOC (gen_entry);
 390   entry->table->top = entry;
 391   entry->processor = processor;
 392   entry->isa = isa;
 393   for (insn = isa->insns; insn != NULL; insn = insn->next)
 394     {
 395       if (processor == NULL
 396           || insn->processors == NULL
 397           || filter_is_member (insn->processors, processor))
 398         {
 399           insn_list_insert (&entry->table->insns,
 400                             &entry->table->nr_insns,
 401                             insn,
 402                             NULL, /* expanded_bits - none yet */
 403                             NULL, /* opcodes - none yet */
 404                             0, /* nr_prefetched_words - none yet */
 405                             report_duplicate_insns);
 406         }
 407     }
 408   entry->table->opcode_rule = rules;
 409   return entry;
 410 }
 411
 412
 413 gen_table *
 414 make_gen_tables (insn_table *isa,
 415                  decode_table *rules)
 416 {
 417   gen_table *gen = ZALLOC (gen_table);
 418   gen->isa = isa;
 419   gen->rules = rules;
 420   if (options.gen.multi_sim)
 421     {
 422       gen_list **last = &gen->tables;
 423       char *processor;
 424       filter *processors;
 425       if (options.model_filter != NULL)
 426         processors = options.model_filter;
 427       else
 428         processors = isa->model->processors;
 429       for (processor = filter_next (processors, "");
 430            processor != NULL;
 431            processor = filter_next (processors, processor))
 432         {
 433           *last = make_table (isa, rules, processor);
 434           last = &(*last)->next;
 435         }
 436     }
 437   else
 438     {
 439       gen->tables = make_table (isa, rules, NULL);
 440     }
 441   return gen;
 442 }
 443
 444
 445 /****************************************************************/
 446
 447 #if 0
 448 typedef enum {
 449   field_is_not_constant = 0,
 450   field_constant_int = 1,
 451   field_constant_reserved = 2,
 452   field_constant_string = 3
 453 } constant_field_types;
 454
 455 static constant_field_types
 456 insn_field_is_constant (insn_field *field,
 457                         decode_table *rule)
 458 {
 459   switch (field->type)
 460     {
 461     case insn_field_int:
 462       /* field is an integer */
 463       return field_constant_int;
 464     case insn_field_reserved:
 465       /* field is `/' and treating that as a constant */
 466       if (rule->with_zero_reserved)
 467         return field_constant_reserved;
 468       else
 469         return field_is_not_constant;
 470     case insn_field_wild:
 471       return field_is_not_constant; /* never constant */
 472     case insn_field_string:
 473       /* field, though variable, is on the list of forced constants */
 474       if (filter_is_member (rule->constant_field_names, field->val_string))
 475         return field_constant_string;
 476       else
 477         return field_is_not_constant;
 478     }
 479   ERROR ("Internal error");
 480   return field_is_not_constant;
 481 }
 482 #endif
 483
 484
 485 /****************************************************************/
 486
 487
 488 /* Is the bit, according to the decode rule, identical across all the
 489    instructions? */
 490 static int
 491 insns_bit_useless (insn_list *insns,
 492                    decode_table *rule,
 493                    int bit_nr)
 494 {
 495   insn_list *entry;
 496   int value = -1;
 497   int is_useless = 1; /* cleared if something actually found */
 498   for (entry = insns; entry != NULL; entry = entry->next)
 499     {
 500       insn_word_entry *word = entry->insn->word[rule->word_nr];
 501       insn_bit_entry *bit = word->bit[bit_nr];
 502       switch (bit->field->type)
 503         {
 504         case insn_field_wild:
 505         case insn_field_reserved:
 506           /* neither useless or useful - ignore */
 507           break;
 508         case insn_field_int:
 509           switch (rule->search)
 510             {
 511             case decode_find_strings:
 512               /* an integer isn't a string */
 513               return 1;
 514             case decode_find_constants:
 515             case decode_find_mixed:
 516               /* an integer is useful if its value isn't the same
 517                  between all instructions? */
 518               if (value < 0)
 519                 value = bit->value;
 520               else if (value != bit->value)
 521                 is_useless = 0;
 522               break;
 523             }
 524           break;
 525         case insn_field_string:
 526           switch (rule->search)
 527             {
 528             case decode_find_strings:
 529               /* at least one string, keep checking */
 530               is_useless = 0;
 531               break;
 532             case decode_find_constants:
 533             case decode_find_mixed:
 534               /* a string field forced to constant */
 535               if (filter_is_member (rule->constant_field_names,
 536                                     bit->field->val_string))
 537                 is_useless = 0;
 538               else if (rule->search == decode_find_constants)
 539                 /* the string field isn't constant */
 540                 return 1;
 541               break;
 542             }
 543         }
 544     }
 545   return is_useless;
 546 }
 547
 548
 549 /* go through a gen-table's list of instruction formats looking for a
 550    range of bits that meet the decode table RULEs requirements */
 551
 552 static opcode_field *
 553 gen_entry_find_opcode_field (insn_list *insns,
 554                              decode_table *rule,
 555                              int string_only)
 556 {
 557   opcode_field curr_opcode;
 558   ASSERT (rule != NULL);
 559
 560   memset (&curr_opcode, 0, sizeof (curr_opcode));
 561   curr_opcode.word_nr = rule->word_nr;
 562   curr_opcode.first = rule->first;
 563   curr_opcode.last = rule->last;
 564
 565   /* Try to reduce the size of first..last in accordance with the
 566      decode rules */
 567
 568   while (curr_opcode.first <= rule->last)
 569     {
 570       if (insns_bit_useless (insns, rule, curr_opcode.first))
 571         curr_opcode.first ++;
 572       else
 573         break;
 574     }
 575   while (curr_opcode.last >= rule->first)
 576     {
 577       if (insns_bit_useless (insns, rule, curr_opcode.last))
 578         curr_opcode.last --;
 579       else
 580         break;
 581     }
 582
 583
 584 #if 0
 585   for (entry = insns; entry != NULL; entry = entry->next)
 586     {
 587       insn_word_entry *fields = entry->insn->word[rule->word_nr];
 588       opcode_field new_opcode;
 589
 590       ASSERT (fields != NULL);
 591
 592       /* find a start point for the opcode field */
 593       new_opcode.first = rule->first;
 594       while (new_opcode.first <= rule->last
 595              && (!string_only
 596                  || (insn_field_is_constant(fields->bit[new_opcode.first], rule)
 597                      != field_constant_string))
 598              && (string_only
 599                  || (insn_field_is_constant(fields->bit[new_opcode.first], rule)
 600                      == field_is_not_constant)))
 601         {
 602           int new_first = fields->bit[new_opcode.first]->last + 1;
 603           ASSERT (new_first > new_opcode.first);
 604           new_opcode.first = new_first;
 605         }
 606       ASSERT(new_opcode.first > rule->last
 607              || (string_only
 608                  && insn_field_is_constant(fields->bit[new_opcode.first],
 609                                            rule) == field_constant_string)
 610              || (!string_only
 611                  && insn_field_is_constant(fields->bit[new_opcode.first],
 612                                            rule)));
 613
 614       /* find the end point for the opcode field */
 615       new_opcode.last = rule->last;
 616       while (new_opcode.last >= rule->first
 617              && (!string_only
 618                  || insn_field_is_constant(fields->bit[new_opcode.last],
 619                                            rule) != field_constant_string)
 620              && (string_only
 621                  || !insn_field_is_constant(fields->bit[new_opcode.last],
 622                                             rule)))
 623         {
 624           int new_last = fields->bit[new_opcode.last]->first - 1;
 625           ASSERT (new_last < new_opcode.last);
 626           new_opcode.last = new_last;
 627         }
 628       ASSERT(new_opcode.last < rule->first
 629              || (string_only
 630                  && insn_field_is_constant(fields->bit[new_opcode.last],
 631                                            rule) == field_constant_string)
 632              || (!string_only
 633                  && insn_field_is_constant(fields->bit[new_opcode.last],
 634                                            rule)));
 635
 636       /* now see if our current opcode needs expanding to include the
 637          interesting fields within this instruction */
 638       if (new_opcode.first <= rule->last
 639           && curr_opcode.first > new_opcode.first)
 640         curr_opcode.first = new_opcode.first;
 641       if (new_opcode.last >= rule->first
 642           && curr_opcode.last < new_opcode.last)
 643         curr_opcode.last = new_opcode.last;
 644
 645     }
 646 #endif
 647
 648   /* did the final opcode field end up being empty? */
 649   if (curr_opcode.first > curr_opcode.last)
 650     {
 651       return NULL;
 652     }
 653   ASSERT (curr_opcode.last >= rule->first);
 654   ASSERT (curr_opcode.first <= rule->last);
 655   ASSERT (curr_opcode.first <= curr_opcode.last);
 656
 657   /* Ensure that, for the non string only case, the opcode includes
 658      the range forced_first .. forced_last */
 659   if (!string_only
 660       && curr_opcode.first > rule->force_first)
 661     {
 662       curr_opcode.first = rule->force_first;
 663     }
 664   if (!string_only
 665       && curr_opcode.last < rule->force_last)
 666     {
 667       curr_opcode.last = rule->force_last;
 668     }
 669
 670   /* For the string only case, force just the lower bound (so that the
 671      shift can be eliminated) */
 672   if (string_only
 673       && rule->force_last == options.insn_bit_size - 1)
 674     {
 675       curr_opcode.last = options.insn_bit_size - 1;
 676     }
 677
 678   /* handle any special cases */
 679   switch (rule->type)
 680     {
 681     case normal_decode_rule:
 682       /* let the above apply */
 683       curr_opcode.nr_opcodes =
 684         (1 << (curr_opcode.last - curr_opcode.first + 1));
 685       break;
 686     case boolean_rule:
 687       curr_opcode.is_boolean = 1;
 688       curr_opcode.boolean_constant = rule->constant;
 689       curr_opcode.nr_opcodes = 2;
 690       break;
 691     }
 692
 693   {
 694     opcode_field *new_field = ZALLOC (opcode_field);
 695     memcpy (new_field, &curr_opcode, sizeof (opcode_field));
 696     return new_field;
 697   }
 698 }
 699
 700
 701 static void
 702 gen_entry_insert_insn (gen_entry *table,
 703                        insn_entry *old_insn,
 704                        int new_word_nr,
 705                        int new_nr_prefetched_words,
 706                        int new_opcode_nr,
 707                        opcode_bits *new_bits)
 708 {
 709   gen_entry **entry = &table->entries;
 710
 711   /* find the new table for this entry */
 712   while ((*entry) != NULL && (*entry)->opcode_nr < new_opcode_nr)
 713     {
 714       entry = &(*entry)->sibling;
 715     }
 716
 717   if ((*entry) == NULL || (*entry)->opcode_nr != new_opcode_nr)
 718     {
 719       /* insert the missing entry */
 720       gen_entry *new_entry = ZALLOC (gen_entry);
 721       new_entry->sibling = (*entry);
 722       (*entry) = new_entry;
 723       table->nr_entries++;
 724       /* fill it in */
 725       new_entry->top = table->top;
 726       new_entry->opcode_nr = new_opcode_nr;
 727       new_entry->word_nr = new_word_nr;
 728       new_entry->expanded_bits = new_bits;
 729       new_entry->opcode_rule = table->opcode_rule->next;
 730       new_entry->parent = table;
 731       new_entry->nr_prefetched_words = new_nr_prefetched_words;
 732     }
 733   /* ASSERT new_bits == cur_entry bits */
 734   ASSERT ((*entry) != NULL && (*entry)->opcode_nr == new_opcode_nr);
 735   insn_list_insert (&(*entry)->insns,
 736                     &(*entry)->nr_insns,
 737                     old_insn,
 738                     NULL, /* expanded_bits - only in final list */
 739                     NULL, /* opcodes - only in final list */
 740                     new_nr_prefetched_words, /* for this table */
 741                     report_duplicate_insns);
 742 }
 743
 744
 745 static void
 746 gen_entry_expand_opcode (gen_entry *table,
 747                          insn_entry *instruction,
 748                          int bit_nr,
 749                          int opcode_nr,
 750                          opcode_bits *bits)
 751 {
 752   if (bit_nr > table->opcode->last)
 753     {
 754       /* Only include the hardwired bit information with an entry IF
 755          that entry (and hence its functions) are being duplicated.  */
 756       if (table->opcode_rule->with_duplicates)
 757         {
 758           gen_entry_insert_insn (table, instruction,
 759                                  table->opcode->word_nr,
 760                                  table->nr_prefetched_words,
 761                                  opcode_nr, bits);
 762         }
 763       else
 764         {
 765           gen_entry_insert_insn (table, instruction,
 766                                  table->opcode->word_nr,
 767                                  table->nr_prefetched_words,
 768                                  opcode_nr, NULL);
 769         }
 770     }
 771   else
 772     {
 773       insn_word_entry *word = instruction->word[table->opcode->word_nr];
 774       insn_field_entry *field = word->bit[bit_nr]->field;
 775       int last_pos = ((field->last < table->opcode->last)
 776                       ? field->last : table->opcode->last);
 777       int first_pos = ((field->first > table->opcode->first)
 778                        ? field->first : table->opcode->first);
 779       int width = last_pos - first_pos + 1;
 780       switch (field->type)
 781         {
 782         case insn_field_int:
 783           {
 784             int val;
 785             val = sub_val (field->val_int, field, first_pos, last_pos);
 786             gen_entry_expand_opcode (table, instruction,
 787                                      last_pos + 1,
 788                                      ((opcode_nr << width) | val),
 789                                      bits);
 790             break;
 791           }
 792         default:
 793           {
 794             if (field->type == insn_field_reserved)
 795               gen_entry_expand_opcode (table, instruction,
 796                                        last_pos + 1,
 797                                        ((opcode_nr << width)),
 798                                        bits);
 799             else
 800               {
 801                 int val;
 802                 int last_val = (table->opcode->is_boolean
 803                                 ? 2 : (1 << width));
 804                 for (val = 0; val < last_val; val++)
 805                   {
 806                     /* check to see if the value has been limited */
 807                     insn_field_exclusion *exclusion;
 808                     for (exclusion = field->exclusions;
 809                          exclusion != NULL;
 810                          exclusion = exclusion->next)
 811                       {
 812                         int value = sub_val (exclusion->value, field,
 813                                              first_pos, last_pos);
 814                         if (value == val)
 815                           break;
 816                       }
 817                     if (exclusion == NULL)
 818                       {
 819                         /* Only add additional hardwired bit
 820                            information if the entry is not going to
 821                            later be combined */
 822                         if (table->opcode_rule->with_combine)
 823                           {
 824                             gen_entry_expand_opcode (table, instruction,
 825                                                      last_pos + 1,
 826                                                      ((opcode_nr << width) | val),
 827                                                      bits);
 828                           }
 829                         else
 830                           {
 831                             opcode_bits *new_bits = new_opcode_bits (bits, val,
 832                                                                      first_pos, last_pos,
 833                                                                      field,
 834                                                                      table->opcode);
 835                             gen_entry_expand_opcode (table, instruction,
 836                                                      last_pos + 1,
 837                                                      ((opcode_nr << width) | val),
 838                                                      new_bits);
 839                           }
 840                       }
 841                   }
 842               }
 843           }
 844         }
 845     }
 846 }
 847
 848 static void
 849 gen_entry_insert_expanding (gen_entry *table,
 850                             insn_entry *instruction)
 851 {
 852   gen_entry_expand_opcode (table,
 853                            instruction,
 854                            table->opcode->first,
 855                            0,
 856                            table->expanded_bits);
 857 }
 858
 859
 860 static int
 861 insns_match_format_names (insn_list *insns,
 862                           filter *format_names)
 863 {
 864   if (format_names != NULL)
 865     {
 866       insn_list *i;
 867       for (i = insns; i != NULL; i = i->next)
 868         {
 869           if ( i->insn->format_name != NULL
 870                && !filter_is_member (format_names, i->insn->format_name))
 871             return 0;
 872         }
 873     }
 874   return 1;
 875 }
 876
 877 static int
 878 table_matches_path (gen_entry *table,
 879                     decode_path_list *paths)
 880 {
 881   if (paths == NULL)
 882     return 1;
 883   while (paths != NULL)
 884     {
 885       gen_entry *entry = table;
 886       decode_path *path = paths->path;
 887       while (1)
 888         {
 889           if (entry == NULL && path == NULL)
 890             return 1;
 891           if (entry == NULL || path == NULL)
 892             break;
 893           if (entry->opcode_nr != path->opcode_nr)
 894             break;
 895           entry = entry->parent;
 896           path = path->parent;
 897         }
 898       paths = paths->next;
 899     }
 900   return 0;
 901 }
 902
 903
 904 static int
 905 insns_match_conditions (insn_list *insns,
 906                         decode_cond *conditions)
 907 {
 908   if (conditions != NULL)
 909     {
 910       insn_list *i;
 911       for (i = insns; i != NULL; i = i->next)
 912         {
 913           decode_cond *cond;
 914           for (cond = conditions; cond != NULL; cond = cond->next)
 915             {
 916               int bit_nr;
 917               if (i->insn->nr_words <= cond->word_nr)
 918                 return 0;
 919               for (bit_nr = 0; bit_nr < options.insn_bit_size; bit_nr++)
 920                 {
 921                   if (!cond->mask[bit_nr])
 922                     continue;
 923                   if (!i->insn->word[cond->word_nr]->bit[bit_nr]->mask)
 924                     return 0;
 925                   if ((i->insn->word[cond->word_nr]->bit[bit_nr]->value
 926                        == cond->value[bit_nr])
 927                       == !cond->is_equal)
 928                     return 0;
 929                 }
 930             }
 931         }
 932     }
 933   return 1;
 934 }
 935
 936 static int
 937 insns_match_nr_words (insn_list *insns,
 938                       int nr_words)
 939 {
 940   insn_list *i;
 941   for (i = insns; i != NULL; i = i->next)
 942     {
 943       if (i->insn->nr_words < nr_words)
 944         return 0;
 945     }
 946   return 1;
 947 }
 948
 949 static int
 950 insn_list_cmp (insn_list *l,
 951                insn_list *r)
 952 {
 953   while (1)
 954     {
 955       insn_entry *insn;
 956       if (l == NULL && r == NULL)
 957         return 0;
 958       if (l == NULL)
 959         return -1;
 960       if (r == NULL)
 961         return 1;
 962       if (l->insn != r->insn)
 963         return -1; /* somewhat arbitrary at present */
 964       /* skip this insn */
 965       insn = l->insn;
 966       while (l != NULL && l->insn == insn)
 967         l = l->next;
 968       while (r != NULL && r->insn == insn)
 969         r = r->next;
 970     }
 971 }
 972
 973
 974
 975 static void
 976 gen_entry_expand_insns (gen_entry *table)
 977 {
 978   decode_table *opcode_rule;
 979
 980   ASSERT(table->nr_insns >= 1);
 981
 982   /* determine a valid opcode */
 983   for (opcode_rule = table->opcode_rule;
 984        opcode_rule != NULL;
 985        opcode_rule = opcode_rule->next)
 986     {
 987       char *discard_reason;
 988       if (table->top->processor != NULL
 989           && opcode_rule->model_names != NULL
 990           && !filter_is_member (opcode_rule->model_names,
 991                                 table->top->processor))
 992         {
 993           /* the rule isn't applicable to this processor */
 994           discard_reason = "wrong model";
 995         }
 996       else if (table->nr_insns == 1 && opcode_rule->conditions == NULL)
 997         {
 998           /* for safety, require a pre-codition when attempting to
 999              apply a rule to a single instruction */
1000           discard_reason = "need pre-condition when nr-insn == 1";
1001         }
1002       else if (table->nr_insns == 1 && !opcode_rule->with_duplicates)
1003         {
1004           /* Little point in expanding a single instruction when we're
1005              not duplicating the semantic functions that this table
1006              calls */
1007           discard_reason = "need duplication with nr-insns == 1";
1008         }
1009       else if (!insns_match_format_names (table->insns, opcode_rule->format_names))
1010         {
1011           discard_reason = "wrong format name";
1012         }
1013       else if (!insns_match_nr_words (table->insns, opcode_rule->word_nr + 1))
1014         {
1015           discard_reason = "wrong nr words";
1016         }
1017       else if (!table_matches_path (table, opcode_rule->paths))
1018         {
1019           discard_reason = "path failed";
1020         }
1021       else if (!insns_match_conditions (table->insns, opcode_rule->conditions))
1022         {
1023           discard_reason = "condition failed";
1024         }
1025       else
1026         {
1027           discard_reason = "no opcode field";
1028           table->opcode =
1029             gen_entry_find_opcode_field (table->insns,
1030                                          opcode_rule,
1031                                          table->nr_insns == 1/*string-only*/
1032                                          );
1033           if (table->opcode != NULL)
1034             {
1035               table->opcode_rule = opcode_rule;
1036               break;
1037             }
1038         }
1039
1040       if (options.trace.rule_rejection)
1041         {
1042           print_gen_entry_path (opcode_rule->line, table, notify);
1043           notify (NULL, ": rule discarded - %s\n", discard_reason);
1044         }
1045     }
1046
1047   /* did we find anything */
1048   if (opcode_rule == NULL)
1049     {
1050       /* the decode table failed, this set of instructions haven't
1051          been uniquely identified */
1052       if (table->nr_insns > 1)
1053         {
1054           print_gen_entry_insns (table, warning,
1055                                  "was not uniquely decoded",
1056                                  "decodes to the same entry");
1057           error (NULL, "");
1058         }
1059       return;
1060     }
1061
1062   /* Determine the number of words that must have been prefetched for
1063      this table to function */
1064   if (table->parent == NULL)
1065     table->nr_prefetched_words = table->opcode_rule->word_nr + 1;
1066   else if (table->opcode_rule->word_nr + 1 > table->parent->nr_prefetched_words)
1067     table->nr_prefetched_words = table->opcode_rule->word_nr + 1;
1068   else
1069     table->nr_prefetched_words = table->parent->nr_prefetched_words;
1070
1071   /* back link what we found to its parent */
1072   if (table->parent != NULL)
1073     {
1074       ASSERT(table->parent->opcode != NULL);
1075       table->opcode->parent = table->parent->opcode;
1076     }
1077
1078   /* expand the raw instructions according to the opcode */
1079   {
1080     insn_list *entry;
1081     for (entry = table->insns; entry != NULL; entry = entry->next)
1082       {
1083         gen_entry_insert_expanding (table, entry->insn);
1084       }
1085   }
1086
1087   if (options.trace.rule_selection)
1088     {
1089       print_gen_entry_path (table->opcode_rule->line, table, notify);
1090       notify (NULL,
1091               ": decode - word %d, bits [%d..%d] in [%d..%d], opcodes %d, entries %d\n",
1092               table->opcode->word_nr,
1093               i2target (options.hi_bit_nr, table->opcode->first),
1094               i2target (options.hi_bit_nr, table->opcode->last),
1095               i2target (options.hi_bit_nr, table->opcode_rule->first),
1096               i2target (options.hi_bit_nr, table->opcode_rule->last),
1097               table->opcode->nr_opcodes,
1098               table->nr_entries);
1099     }
1100
1101   /* dump the results */
1102   if (options.trace.entries)
1103     {
1104       gen_entry *entry;
1105       for (entry = table->entries; entry != NULL; entry = entry->sibling)
1106         {
1107           insn_list *l;
1108           print_gen_entry_path (table->opcode_rule->line, entry, notify);
1109           notify (NULL, ": %d - entries %d -",
1110                   entry->opcode_nr,
1111                   entry->nr_insns);
1112           for (l = entry->insns; l != NULL; l = l->next)
1113             notify (NULL, " %s.%s", l->insn->format_name, l->insn->name);
1114           notify (NULL, "\n");
1115         }
1116     }
1117
1118   /* perform a combine pass if needed */
1119   if (table->opcode_rule->with_combine)
1120     {
1121       gen_entry *entry;
1122       for (entry = table->entries; entry != NULL; entry = entry->sibling)
1123         {
1124           if (entry->combined_parent == NULL)
1125             {
1126               gen_entry **last = &entry->combined_next;
1127               gen_entry *alt;
1128               for (alt = entry->sibling; alt != NULL; alt = alt->sibling)
1129                 {
1130                   if (alt->combined_parent == NULL
1131                       && insn_list_cmp (entry->insns, alt->insns) == 0)
1132                     {
1133                       alt->combined_parent = entry;
1134                       *last = alt;
1135                       last = &alt->combined_next;
1136                     }
1137                 }
1138             }
1139         }
1140       if (options.trace.combine)
1141         {
1142           int nr_unique = 0;
1143           gen_entry *entry;
1144           for (entry = table->entries; entry != NULL; entry = entry->sibling)
1145             {
1146               if (entry->combined_parent == NULL)
1147                 {
1148                   insn_list *l;
1149                   gen_entry *duplicate;
1150                   nr_unique++;
1151                   print_gen_entry_path (table->opcode_rule->line, entry, notify);
1152                   for (duplicate = entry->combined_next;
1153                        duplicate != NULL;
1154                        duplicate = duplicate->combined_next)
1155                     {
1156                       notify (NULL, "+%d", duplicate->opcode_nr);
1157                     }
1158                   notify (NULL, ": entries %d -", entry->nr_insns);
1159                   for (l = entry->insns; l != NULL; l = l->next)
1160                     {
1161                       notify (NULL, " %s.%s",
1162                               l->insn->format_name,
1163                               l->insn->name);
1164                     }
1165                   notify (NULL, "\n");
1166                 }
1167             }
1168           print_gen_entry_path (table->opcode_rule->line, table, notify);
1169           notify (NULL, ": combine - word %d, bits [%d..%d] in [%d..%d], opcodes %d, entries %d, unique %d\n",
1170                   table->opcode->word_nr,
1171                   i2target (options.hi_bit_nr, table->opcode->first),
1172                   i2target (options.hi_bit_nr, table->opcode->last),
1173                   i2target (options.hi_bit_nr, table->opcode_rule->first),
1174                   i2target (options.hi_bit_nr, table->opcode_rule->last),
1175                   table->opcode->nr_opcodes,
1176                   table->nr_entries,
1177                   nr_unique);
1178         }
1179     }
1180
1181   /* Check that the rule did more than re-arange the order of the
1182      instructions */
1183   {
1184       gen_entry *entry;
1185       for (entry = table->entries; entry != NULL; entry = entry->sibling)
1186         {
1187           if (entry->combined_parent == NULL)
1188             {
1189               if (insn_list_cmp (table->insns, entry->insns) == 0)
1190                 {
1191                   print_gen_entry_path (table->opcode_rule->line, table, warning);
1192                   warning (NULL, ": Applying rule just copied all instructions\n");
1193                   print_gen_entry_insns (entry, warning, "Copied", NULL);
1194                   error (NULL, "");
1195                 }
1196             }
1197         }
1198   }
1199
1200   /* if some form of expanded table, fill in the missing dots */
1201   switch (table->opcode_rule->gen)
1202     {
1203     case padded_switch_gen:
1204     case array_gen:
1205     case goto_switch_gen:
1206       if (!table->opcode->is_boolean)
1207         {
1208           gen_entry **entry = &table->entries;
1209           gen_entry *illegals = NULL;
1210           gen_entry **last_illegal = &illegals;
1211           int opcode_nr = 0;
1212           while (opcode_nr < table->opcode->nr_opcodes)
1213             {
1214               if ((*entry) == NULL || (*entry)->opcode_nr != opcode_nr)
1215                 {
1216                   /* missing - insert it under our feet at *entry */
1217                   gen_entry_insert_insn (table,
1218                                          table->top->isa->illegal_insn,
1219                                          table->opcode->word_nr,
1220                                          0, /* nr_prefetched_words == 0 for invalid */
1221                                          opcode_nr, NULL);
1222                   ASSERT ((*entry) != NULL);
1223                   ASSERT ((*entry)->opcode_nr == opcode_nr);
1224                   (*last_illegal) = *entry;
1225                   (*last_illegal)->combined_parent = illegals;
1226                   last_illegal = &(*last_illegal)->combined_next;
1227                 }
1228               entry = &(*entry)->sibling;
1229               opcode_nr++;
1230             }
1231           /* oops, will have pointed the first illegal insn back to
1232              its self.  Fix this */
1233           if (illegals != NULL)
1234             illegals->combined_parent = NULL;
1235         }
1236       break;
1237     case switch_gen:
1238     case invalid_gen:
1239       /* ignore */
1240       break;
1241     }
1242
1243   /* and do the same for the newly created sub entries but *only*
1244      expand entries that haven't been combined. */
1245   {
1246     gen_entry *entry;
1247     for (entry = table->entries; entry != NULL; entry =  entry->sibling)
1248       {
1249         if (entry->combined_parent == NULL)
1250           {
1251             gen_entry_expand_insns (entry);
1252           }
1253       }
1254   }
1255 }
1256
1257 void
1258 gen_tables_expand_insns (gen_table *gen)
1259 {
1260   gen_list *entry;
1261   for (entry = gen->tables; entry != NULL; entry = entry->next)
1262     {
1263       gen_entry_expand_insns (entry->table);
1264     }
1265 }
1266
1267
1268 /* create a list of all the semantic functions that need to be
1269    generated.  Eliminate any duplicates. Verify that the decode stage
1270    worked. */
1271
1272 static void
1273 make_gen_semantics_list (lf *file,
1274                          gen_entry *entry,
1275                          int depth,
1276                          void *data)
1277 {
1278   gen_table *gen = (gen_table*) data;
1279   insn_list *insn;
1280   /* Not interested in an entrie that have been combined into some
1281      other entry at the same level */
1282   if (entry->combined_parent != NULL)
1283     return;
1284
1285   /* a leaf should contain exactly one instruction. If not the decode
1286      stage failed. */
1287   ASSERT (entry->nr_insns == 1);
1288
1289   /* Enter this instruction into the list of semantic functions. */
1290   insn = insn_list_insert (&gen->semantics, &gen->nr_semantics,
1291                            entry->insns->insn,
1292                            entry->expanded_bits,
1293                            entry->parent->opcode,
1294                            entry->insns->nr_prefetched_words,
1295                            merge_duplicate_insns);
1296   /* point the table entry at the real semantic function */
1297   ASSERT (insn != NULL);
1298   entry->insns->semantic = insn;
1299 }
1300
1301
1302 void
1303 gen_tables_expand_semantics (gen_table *gen)
1304 {
1305   gen_list *entry;
1306   for (entry = gen->tables; entry != NULL; entry = entry->next)
1307     {
1308       gen_entry_traverse_tree (NULL,
1309                                entry->table,
1310                                1, /* depth */
1311                                NULL, /* start-handler */
1312                                make_gen_semantics_list, /* leaf-handler */
1313                                NULL, /* end-handler */
1314                                gen); /* data */
1315   }
1316 }
1317
1318
1319
1320 #ifdef MAIN
1321
1322
1323 static void
1324 dump_opcode_field (lf *file,
1325                    char *prefix,
1326                    opcode_field *field,
1327                    char *suffix,
1328                    int levels)
1329 {
1330   lf_printf (file, "%s(opcode_field *) 0x%lx", prefix, (long) field);
1331   if (levels && field != NULL) {
1332     lf_indent (file, +1);
1333     lf_printf (file, "\n(first %d)", field->first);
1334     lf_printf (file, "\n(last %d)", field->last);
1335     lf_printf (file, "\n(nr_opcodes %d)", field->nr_opcodes);
1336     lf_printf (file, "\n(is_boolean %d)", field->is_boolean);
1337     lf_printf (file, "\n(boolean_constant %d)", field->boolean_constant);
1338     dump_opcode_field(file, "\n(parent ", field->parent, ")", levels - 1);
1339     lf_indent (file, -1);
1340   }
1341   lf_printf (file, "%s", suffix);
1342 }
1343
1344
1345 static void
1346 dump_opcode_bits (lf *file,
1347                   char *prefix,
1348                   opcode_bits *bits,
1349                   char *suffix,
1350                   int levels)
1351 {
1352   lf_printf (file, "%s(opcode_bits *) 0x%lx", prefix, (long) bits);
1353
1354   if (levels && bits != NULL)
1355     {
1356       lf_indent (file, +1);
1357       lf_printf (file, "\n(value %d)", bits->value);
1358       dump_opcode_field (file, "\n(opcode ", bits->opcode, ")", 0);
1359       dump_insn_field (file, "\n(field ", bits->field, ")");
1360       dump_opcode_bits (file, "\n(next ", bits->next, ")", levels - 1);
1361       lf_indent (file, -1);
1362     }
1363   lf_printf (file, "%s", suffix);
1364 }
1365
1366
1367
1368 static void
1369 dump_insn_list (lf *file,
1370                 char *prefix,
1371                 insn_list *entry,
1372                 char *suffix)
1373 {
1374   lf_printf (file, "%s(insn_list *) 0x%lx", prefix, (long) entry);
1375
1376   if (entry != NULL) {
1377     lf_indent (file, +1);
1378     dump_insn_entry (file, "\n(insn ", entry->insn, ")");
1379     lf_printf (file, "\n(next 0x%lx)", (long) entry->next);
1380     lf_indent (file, -1);
1381   }
1382   lf_printf (file, "%s", suffix);
1383 }
1384
1385
1386 static void
1387 dump_insn_word_entry_list_entries (lf *file,
1388                                char *prefix,
1389                                insn_list *entry,
1390                                char *suffix)
1391 {
1392   lf_printf (file, "%s", prefix);
1393   while (entry != NULL)
1394     {
1395       dump_insn_list (file, "\n(", entry, ")");
1396       entry = entry->next;
1397     }
1398   lf_printf (file, "%s", suffix);
1399 }
1400
1401
1402 static void
1403 dump_gen_entry (lf *file,
1404                 char *prefix,
1405                 gen_entry *table,
1406                 char *suffix,
1407                 int levels)
1408 {
1409
1410   lf_printf (file, "%s(gen_entry *) 0x%lx", prefix, (long) table);
1411
1412   if (levels && table != NULL) {
1413
1414     lf_indent (file, +1);
1415     lf_printf (file, "\n(opcode_nr %d)", table->opcode_nr);
1416     lf_printf (file, "\n(word_nr %d)", table->word_nr);
1417     dump_opcode_bits (file, "\n(expanded_bits ", table->expanded_bits, ")", -1);
1418     lf_printf (file, "\n(nr_insns %d)", table->nr_insns);
1419     dump_insn_word_entry_list_entries (file, "\n(insns ", table->insns, ")");
1420     dump_decode_rule (file, "\n(opcode_rule ", table->opcode_rule, ")");
1421     dump_opcode_field (file, "\n(opcode ", table->opcode, ")", 0);
1422     lf_printf (file, "\n(nr_entries %d)", table->nr_entries);
1423     dump_gen_entry (file, "\n(entries ", table->entries, ")", table->nr_entries);
1424     dump_gen_entry (file, "\n(sibling ", table->sibling, ")", levels - 1);
1425     dump_gen_entry (file, "\n(parent ", table->parent, ")", 0);
1426     lf_indent (file, -1);
1427   }
1428   lf_printf (file, "%s", suffix);
1429 }
1430
1431 static void
1432 dump_gen_list (lf *file,
1433                char *prefix,
1434                gen_list *entry,
1435                char *suffix,
1436                int levels)
1437 {
1438   while (entry != NULL)
1439     {
1440       lf_printf (file, "%s(gen_list *) 0x%lx", prefix, (long) entry);
1441       dump_gen_entry (file, "\n(", entry->table, ")", levels);
1442       lf_printf (file, "\n(next (gen_list *) 0x%lx)", (long) entry->next);
1443       lf_printf (file, "%s", suffix);
1444     }
1445 }
1446
1447
1448 static void
1449 dump_gen_table (lf *file,
1450                 char *prefix,
1451                 gen_table *gen,
1452                 char *suffix,
1453                 int levels)
1454 {
1455   lf_printf (file, "%s(gen_table *) 0x%lx", prefix, (long) gen);
1456   lf_printf (file, "\n(isa (insn_table *) 0x%lx)", (long) gen->isa);
1457   lf_printf (file, "\n(rules (decode_table *) 0x%lx)", (long) gen->rules);
1458   dump_gen_list (file, "\n(", gen->tables, ")", levels);
1459   lf_printf (file, "%s", suffix);
1460 }
1461
1462
1463 igen_options options;
1464
1465 int
1466 main (int argc,
1467       char **argv)
1468 {
1469   decode_table *decode_rules;
1470   insn_table *instructions;
1471   gen_table *gen;
1472   lf *l;
1473
1474   if (argc != 7)
1475     error (NULL, "Usage: insn <filter-in> <hi-bit-nr> <insn-bit-size> <widths> <decode-table> <insn-table>\n");
1476
1477   INIT_OPTIONS (options);
1478
1479   filter_parse (&options.flags_filter, argv[1]);
1480
1481   options.hi_bit_nr = a2i(argv[2]);
1482   options.insn_bit_size = a2i(argv[3]);
1483   options.insn_specifying_widths = a2i(argv[4]);
1484   ASSERT(options.hi_bit_nr < options.insn_bit_size);
1485
1486   instructions = load_insn_table (argv[6], NULL);
1487   decode_rules = load_decode_table (argv[5]);
1488   gen = make_gen_tables (instructions, decode_rules);
1489
1490   gen_tables_expand_insns (gen);
1491
1492   l = lf_open ("-", "stdout", lf_omit_references, lf_is_text, "tmp-ld-insn");
1493
1494   dump_gen_table (l, "(", gen, ")\n", -1);
1495   return 0;
1496 }
1497
1498 #endif