opcodes/aarch64-gen.c

   1 /* aarch64-gen.c -- Generate tables and routines for opcode lookup and
   2    instruction encoding and decoding.
   3    Copyright (C) 2012-2019 Free Software Foundation, Inc.
   4    Contributed by ARM Ltd.
   5
   6    This file is part of the GNU opcodes library.
   7
   8    This library is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 3, or (at your option)
  11    any later version.
  12
  13    It is distributed in the hope that it will be useful, but WITHOUT
  14    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  15    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  16    License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; see the file COPYING3. If not,
  20    see <http://www.gnu.org/licenses/>.  */
  21
  22 #include "sysdep.h"
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <stdarg.h>
  26
  27 #include "libiberty.h"
  28 #include "getopt.h"
  29 #include "opcode/aarch64.h"
  30
  31 #define VERIFIER(x) NULL
  32 #include "aarch64-tbl.h"
  33
  34 static int debug = 0;
  35
  36 /* Structure used in the decoding tree to group a list of aarch64_opcode
  37    entries.  */
  38
  39 struct opcode_node
  40 {
  41   aarch64_insn opcode;
  42   aarch64_insn mask;
  43   /* Index of the entry in the original table; the top 2 bits help
  44      determine the table.  */
  45   unsigned int index;
  46   struct opcode_node *next;
  47 };
  48
  49 typedef struct opcode_node opcode_node;
  50
  51 /* Head of the list of the opcode_node after read_table.  */
  52 static opcode_node opcode_nodes_head;
  53
  54 /* Node in the decoding tree.  */
  55
  56 struct bittree
  57 {
  58   unsigned int bitno;
  59   /* 0, 1, and X (don't care).  */
  60   struct bittree *bits[2];
  61   /* List of opcodes; only valid for the leaf node.  */
  62   opcode_node *list;
  63 };
  64
  65 /* Allocate and initialize an opcode_node.  */
  66 static opcode_node*
  67 new_opcode_node (void)
  68 {
  69   opcode_node* ent = malloc (sizeof (opcode_node));
  70
  71   if (!ent)
  72     abort ();
  73
  74   ent->opcode = 0;
  75   ent->mask = 0;
  76   ent->index = -1;
  77   ent->next = NULL;
  78
  79   return ent;
  80 }
  81
  82 /* Multiple tables are supported, although currently only one table is
  83    in use.  N.B. there are still some functions have the table name
  84    'aarch64_opcode_table' hard-coded in, e.g. print_find_next_opcode;
  85    therefore some amount of work needs to be done if the full support
  86    for multiple tables needs to be enabled.  */
  87 static const struct aarch64_opcode *aarch64_opcode_tables[] =
  88 {aarch64_opcode_table};
  89
  90 /* Use top 2 bits to indiate which table.  */
  91 static unsigned int
  92 initialize_index (const struct aarch64_opcode* table)
  93 {
  94   int i;
  95   const int num_of_tables = sizeof (aarch64_opcode_tables)
  96     / sizeof (struct aarch64_opcode *);
  97   for (i = 0; i < num_of_tables; ++i)
  98     if (table == aarch64_opcode_tables [i])
  99       break;
 100   if (i == num_of_tables)
 101     abort ();
 102   return (unsigned int)i << 30;
 103 }
 104
 105 static inline const struct aarch64_opcode *
 106 index2table (unsigned int index)
 107 {
 108   return aarch64_opcode_tables[(index >> 30) & 0x3];
 109 }
 110
 111 static inline unsigned int
 112 real_index (unsigned int index)
 113 {
 114   return index & ((1 << 30) - 1);
 115 }
 116
 117 /* Given OPCODE_NODE, return the corresponding aarch64_opcode*.  */
 118 static const aarch64_opcode*
 119 get_aarch64_opcode (const opcode_node *opcode_node)
 120 {
 121   if (opcode_node == NULL)
 122     return NULL;
 123   return &index2table (opcode_node->index)[real_index (opcode_node->index)];
 124 }
 125
 126 static void
 127 read_table (const struct aarch64_opcode* table)
 128 {
 129   const struct aarch64_opcode *ent = table;
 130   opcode_node **new_ent;
 131   unsigned int index = initialize_index (table);
 132
 133   if (!ent->name)
 134     return;
 135
 136   new_ent = &opcode_nodes_head.next;
 137
 138   while (*new_ent)
 139     new_ent = &(*new_ent)->next;
 140
 141   do
 142     {
 143       /* F_PSEUDO needs to be used together with F_ALIAS to indicate an alias
 144          opcode is a programmer friendly pseudo instruction available only in
 145          the assembly code (thus will not show up in the disassembly).  */
 146       assert (!pseudo_opcode_p (ent) || alias_opcode_p (ent));
 147       /* Skip alias (inc. pseudo) opcode.  */
 148       if (alias_opcode_p (ent))
 149         {
 150           index++;
 151           continue;
 152         }
 153       *new_ent = new_opcode_node ();
 154       (*new_ent)->opcode = ent->opcode;
 155       (*new_ent)->mask = ent->mask;
 156       (*new_ent)->index = index++;
 157       new_ent = &((*new_ent)->next);
 158     } while ((++ent)->name);
 159 }
 160
 161 static inline void
 162 print_one_opcode_node (opcode_node* ent)
 163 {
 164   printf ("%s\t%08x\t%08x\t%d\n", get_aarch64_opcode (ent)->name,
 165           get_aarch64_opcode (ent)->opcode, get_aarch64_opcode (ent)->mask,
 166           (int)real_index (ent->index));
 167 }
 168
 169 /* As an internal debugging utility, print out the list of nodes pointed
 170    by opcode_nodes_head.  */
 171 static void
 172 print_opcode_nodes (void)
 173 {
 174   opcode_node* ent = opcode_nodes_head.next;
 175   printf ("print_opcode_nodes table:\n");
 176   while (ent)
 177     {
 178       print_one_opcode_node (ent);
 179       ent = ent->next;
 180     }
 181 }
 182
 183 static struct bittree*
 184 new_bittree_node (void)
 185 {
 186   struct bittree* node;
 187   node = malloc (sizeof (struct bittree));
 188   if (!node)
 189     abort ();
 190   node->bitno = -1;
 191   node->bits[0] = NULL;
 192   node->bits[1] = NULL;
 193   return node;
 194 }
 195
 196 /* The largest number of opcode entries that exist at a leaf node of the
 197    decoding decision tree.  The reason that there can be more than one
 198    opcode entry is because some opcodes have shared field that is partially
 199    constrained and thus cannot be fully isolated using the algorithm
 200    here.  */
 201 static int max_num_opcodes_at_leaf_node = 0;
 202
 203 /* Given a list of opcodes headed by *OPCODE, try to establish one bit that
 204    is shared by all the opcodes in the list as one of base opcode bits.  If
 205    such a bit is found, divide the list of the opcodes into two based on the
 206    value of the bit.
 207
 208    Store the bit number in BITTREE->BITNO if the division succeeds.  If unable
 209    to determine such a bit or there is only one opcode in the list, the list
 210    is decided to be undividable and OPCODE will be assigned to BITTREE->LIST.
 211
 212    The function recursively call itself until OPCODE is undividable.
 213
 214    N.B. the nature of this algrithm determines that given any value in the
 215    32-bit space, the computed decision tree will always be able to find one or
 216    more opcodes entries for it, regardless whether there is a valid instruction
 217    defined for this value or not.  In order to detect the undefined values,
 218    when the caller obtains the opcode entry/entries, it should at least compare
 219    the bit-wise AND result of the value and the mask with the base opcode
 220    value; if the two are different, it means that the value is undefined
 221    (although the value may be still undefined when the comparison is the same,
 222    in which case call aarch64_opcode_decode to carry out further checks).  */
 223
 224 static void
 225 divide_table_1 (struct bittree *bittree, opcode_node *opcode)
 226 {
 227   aarch64_insn mask_and;
 228   opcode_node *ent;
 229   unsigned int bitno;
 230   aarch64_insn bitmask;
 231   opcode_node list0, list1, **ptr0, **ptr1;
 232   static int depth = 0;
 233
 234   ++depth;
 235
 236   if (debug)
 237     printf ("Enter into depth %d\n", depth);
 238
 239   assert (opcode != NULL);
 240
 241   /* Succeed when there is only one opcode left.  */
 242   if (!opcode->next)
 243     {
 244       if (debug)
 245         {
 246           printf ("opcode isolated:\n");
 247           print_one_opcode_node (opcode);
 248         }
 249       goto divide_table_1_finish;
 250     }
 251
 252 divide_table_1_try_again:
 253   mask_and = -1;
 254   ent = opcode;
 255   while (ent)
 256     {
 257       mask_and &= ent->mask;
 258       ent = ent->next;
 259     }
 260
 261   if (debug)
 262     printf ("mask and result: %08x\n", (unsigned int)mask_and);
 263
 264   /* If no more bit to look into, we have to accept the reality then.  */
 265   if (!mask_and)
 266     {
 267       int i;
 268       opcode_node *ptr;
 269       if (debug)
 270         {
 271           ptr = opcode;
 272           printf ("Isolated opcode group:\n");
 273           do {
 274               print_one_opcode_node (ptr);
 275               ptr = ptr->next;
 276           } while (ptr);
 277         }
 278       /* Count the number of opcodes.  */
 279       for (i = 0, ptr = opcode; ptr; ++i)
 280         ptr = ptr->next;
 281       if (i > max_num_opcodes_at_leaf_node)
 282         max_num_opcodes_at_leaf_node = i;
 283       goto divide_table_1_finish;
 284     }
 285
 286   /* Pick up the right most bit that is 1.  */
 287   bitno = 0;
 288   while (!(mask_and & (1 << bitno)))
 289     ++bitno;
 290   bitmask = (1 << bitno);
 291
 292   if (debug)
 293     printf ("use bit %d\n", bitno);
 294
 295   /* Record in the bittree.  */
 296   bittree->bitno = bitno;
 297
 298   /* Get two new opcode lists; adjust their masks.  */
 299   list0.next = NULL;
 300   list1.next = NULL;
 301   ptr0 = &list0.next;
 302   ptr1 = &list1.next;
 303   ent = opcode;
 304   while (ent)
 305     {
 306       if (ent->opcode & bitmask)
 307         {
 308           ent->mask &= (~bitmask);
 309           *ptr1 = ent;
 310           ent = ent->next;
 311           (*ptr1)->next = NULL;
 312           ptr1 = &(*ptr1)->next;
 313         }
 314       else
 315         {
 316           ent->mask &= (~bitmask);
 317           *ptr0 = ent;
 318           ent = ent->next;
 319           (*ptr0)->next = NULL;
 320           ptr0 = &(*ptr0)->next;
 321         }
 322     }
 323
 324   /* If BITNO can NOT divide the opcode group, try next bit.  */
 325   if (list0.next == NULL)
 326     {
 327       opcode = list1.next;
 328       goto divide_table_1_try_again;
 329     }
 330   else if (list1.next == NULL)
 331     {
 332       opcode = list0.next;
 333       goto divide_table_1_try_again;
 334     }
 335
 336   /* Further divide.  */
 337   bittree->bits[0] = new_bittree_node ();
 338   bittree->bits[1] = new_bittree_node ();
 339   divide_table_1 (bittree->bits[0], list0.next);
 340   divide_table_1 (bittree->bits[1], list1.next);
 341
 342 divide_table_1_finish:
 343   if (debug)
 344     printf ("Leave from depth %d\n", depth);
 345   --depth;
 346
 347   /* Record the opcode entries on this leaf node.  */
 348   bittree->list = opcode;
 349
 350   return;
 351 }
 352
 353 /* Call divide_table_1 to divide the all the opcodes and thus create the
 354    decoding decision tree.  */
 355 static struct bittree *
 356 divide_table (void)
 357 {
 358   struct bittree *bittree = new_bittree_node ();
 359   divide_table_1 (bittree, opcode_nodes_head.next);
 360   return bittree;
 361 }
 362
 363 /* Read in all of the tables, create the decoding decision tree and return
 364    the tree root.  */
 365 static struct bittree *
 366 initialize_decoder_tree (void)
 367 {
 368   int i;
 369   const int num_of_tables = (sizeof (aarch64_opcode_tables)
 370                              / sizeof (struct aarch64_opcode *));
 371   for (i = 0; i < num_of_tables; ++i)
 372     read_table (aarch64_opcode_tables [i]);
 373   if (debug)
 374     print_opcode_nodes ();
 375   return divide_table ();
 376 }
 377
 378 static void __attribute__ ((format (printf, 2, 3)))
 379 indented_print (unsigned int indent, const char *format, ...)
 380 {
 381   va_list ap;
 382   va_start (ap, format);
 383   printf ("%*s", (int) indent, "");
 384   vprintf (format, ap);
 385   va_end (ap);
 386 }
 387
 388 /* N.B. read the comment above divide_table_1 for the reason why the generated
 389    decision tree function never returns NULL.  */
 390
 391 static void
 392 print_decision_tree_1 (unsigned int indent, struct bittree* bittree)
 393 {
 394   /* PATTERN is only used to generate comment in the code.  */
 395   static char pattern[33] = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
 396   /* Low bits in PATTERN will be printed first which then look as the high
 397      bits in comment.  We need to reverse the index to get correct print.  */
 398   unsigned int msb = sizeof (pattern) - 2;
 399   assert (bittree != NULL);
 400
 401   /* Leaf node located.  */
 402   if (bittree->bits[0] == NULL && bittree->bits[1] == NULL)
 403     {
 404       assert (bittree->list != NULL);
 405       indented_print (indent, "/* 33222222222211111111110000000000\n");
 406       indented_print (indent, "   10987654321098765432109876543210\n");
 407       indented_print (indent, "   %s\n", pattern);
 408       indented_print (indent, "   %s.  */\n",
 409                       get_aarch64_opcode (bittree->list)->name);
 410       indented_print (indent, "return %u;\n",
 411                       real_index (bittree->list->index));
 412       return;
 413     }
 414
 415   /* Walk down the decoder tree.  */
 416   indented_print (indent, "if (((word >> %d) & 0x1) == 0)\n", bittree->bitno);
 417   indented_print (indent, "  {\n");
 418   pattern[msb - bittree->bitno] = '0';
 419   print_decision_tree_1 (indent + 4, bittree->bits[0]);
 420   indented_print (indent, "  }\n");
 421   indented_print (indent, "else\n");
 422   indented_print (indent, "  {\n");
 423   pattern[msb - bittree->bitno] = '1';
 424   print_decision_tree_1 (indent + 4, bittree->bits[1]);
 425   indented_print (indent, "  }\n");
 426   pattern[msb - bittree->bitno] = 'x';
 427 }
 428
 429 /* Generate aarch64_opcode_lookup in C code to the standard output.  */
 430
 431 static void
 432 print_decision_tree (struct bittree* bittree)
 433 {
 434   if (debug)
 435     printf ("Enter print_decision_tree\n");
 436
 437   printf ("/* Called by aarch64_opcode_lookup.  */\n\n");
 438
 439   printf ("static int\n");
 440   printf ("aarch64_opcode_lookup_1 (uint32_t word)\n");
 441   printf ("{\n");
 442
 443   print_decision_tree_1 (2, bittree);
 444
 445   printf ("}\n\n");
 446
 447
 448   printf ("/* Lookup opcode WORD in the opcode table.  N.B. all alias\n");
 449   printf ("   opcodes are ignored here.  */\n\n");
 450
 451   printf ("const aarch64_opcode *\n");
 452   printf ("aarch64_opcode_lookup (uint32_t word)\n");
 453   printf ("{\n");
 454   printf ("  return aarch64_opcode_table + aarch64_opcode_lookup_1 (word);\n");
 455   printf ("}\n");
 456 }
 457
 458 static void
 459 print_find_next_opcode_1 (struct bittree* bittree)
 460 {
 461   assert (bittree != NULL);
 462
 463   /* Leaf node located.  */
 464   if (bittree->bits[0] == NULL && bittree->bits[1] == NULL)
 465     {
 466       assert (bittree->list != NULL);
 467       /* Find multiple opcode entries in one leaf node.  */
 468       if (bittree->list->next != NULL)
 469         {
 470           opcode_node *list = bittree->list;
 471           while (list != NULL)
 472             {
 473               const aarch64_opcode *curr = get_aarch64_opcode (list);
 474               const aarch64_opcode *next = get_aarch64_opcode (list->next);
 475
 476               printf ("    case %u: ",
 477                       (unsigned int)(curr - aarch64_opcode_table));
 478               if (list->next != NULL)
 479                 {
 480                   printf ("value = %u; break;\t", real_index (list->next->index));
 481                   printf ("/* %s --> %s.  */\n", curr->name, next->name);
 482                 }
 483               else
 484                 {
 485                   printf ("return NULL;\t\t");
 486                   printf ("/* %s --> NULL.  */\n", curr->name);
 487                 }
 488
 489               list = list->next;
 490             }
 491         }
 492       return;
 493     }
 494
 495   /* Walk down the decoder tree.  */
 496   print_find_next_opcode_1 (bittree->bits[0]);
 497   print_find_next_opcode_1 (bittree->bits[1]);
 498 }
 499
 500 /* Generate aarch64_find_next_opcode in C code to the standard output.  */
 501
 502 static void
 503 print_find_next_opcode (struct bittree* bittree)
 504 {
 505   if (debug)
 506     printf ("Enter print_find_next_opcode\n");
 507
 508   printf ("\n");
 509   printf ("const aarch64_opcode *\n");
 510   printf ("aarch64_find_next_opcode (const aarch64_opcode *opcode)\n");
 511   printf ("{\n");
 512   printf ("  /* Use the index as the key to locate the next opcode.  */\n");
 513   printf ("  int key = opcode - aarch64_opcode_table;\n");
 514   printf ("  int value;\n");
 515   printf ("  switch (key)\n");
 516   printf ("    {\n");
 517
 518   print_find_next_opcode_1 (bittree);
 519
 520   printf ("    default: return NULL;\n");
 521   printf ("    }\n\n");
 522
 523   printf ("  return aarch64_opcode_table + value;\n");
 524   printf ("}\n");
 525 }
 526
 527 /* Release the dynamic memory resource allocated for the generation of the
 528    decoder tree.  */
 529
 530 static void
 531 release_resource_decoder_tree (struct bittree* bittree)
 532 {
 533   assert (bittree != NULL);
 534
 535   /* Leaf node located.  */
 536   if (bittree->bits[0] == NULL && bittree->bits[1] == NULL)
 537     {
 538       assert (bittree->list != NULL);
 539       /* Free opcode_nodes.  */
 540       opcode_node *list = bittree->list;
 541       while (list != NULL)
 542         {
 543           opcode_node *next = list->next;
 544           free (list);
 545           list = next;
 546         }
 547       /* Free the tree node.  */
 548       free (bittree);
 549       return;
 550     }
 551
 552   /* Walk down the decoder tree.  */
 553   release_resource_decoder_tree (bittree->bits[0]);
 554   release_resource_decoder_tree (bittree->bits[1]);
 555
 556   /* Free the tree node.  */
 557   free (bittree);
 558 }
 559
 560 /* Generate aarch64_find_real_opcode in C code to the standard output.
 561    TABLE points to the alias info table, while NUM indicates the number of
 562    entries in the table.  */
 563
 564 static void
 565 print_find_real_opcode (const opcode_node *table, int num)
 566 {
 567   int i;
 568
 569   if (debug)
 570     printf ("Enter print_find_real_opcode\n");
 571
 572   printf ("\n");
 573   printf ("const aarch64_opcode *\n");
 574   printf ("aarch64_find_real_opcode (const aarch64_opcode *opcode)\n");
 575   printf ("{\n");
 576   printf ("  /* Use the index as the key to locate the real opcode.  */\n");
 577   printf ("  int key = opcode - aarch64_opcode_table;\n");
 578   printf ("  int value;\n");
 579   printf ("  switch (key)\n");
 580   printf ("    {\n");
 581
 582   for (i = 0; i < num; ++i)
 583     {
 584       const opcode_node *real = table + i;
 585       const opcode_node *alias = real->next;
 586       for (; alias; alias = alias->next)
 587         printf ("    case %u:\t/* %s */\n", real_index (alias->index),
 588                 get_aarch64_opcode (alias)->name);
 589       printf ("      value = %u;\t/* --> %s.  */\n", real_index (real->index),
 590               get_aarch64_opcode (real)->name);
 591       printf ("      break;\n");
 592     }
 593
 594   printf ("    default: return NULL;\n");
 595   printf ("    }\n\n");
 596
 597   printf ("  return aarch64_opcode_table + value;\n");
 598   printf ("}\n");
 599 }
 600
 601 /* Generate aarch64_find_alias_opcode in C code to the standard output.
 602    TABLE points to the alias info table, while NUM indicates the number of
 603    entries in the table.  */
 604
 605 static void
 606 print_find_alias_opcode (const opcode_node *table, int num)
 607 {
 608   int i;
 609
 610   if (debug)
 611     printf ("Enter print_find_alias_opcode\n");
 612
 613   printf ("\n");
 614   printf ("const aarch64_opcode *\n");
 615   printf ("aarch64_find_alias_opcode (const aarch64_opcode *opcode)\n");
 616   printf ("{\n");
 617   printf ("  /* Use the index as the key to locate the alias opcode.  */\n");
 618   printf ("  int key = opcode - aarch64_opcode_table;\n");
 619   printf ("  int value;\n");
 620   printf ("  switch (key)\n");
 621   printf ("    {\n");
 622
 623   for (i = 0; i < num; ++i)
 624     {
 625       const opcode_node *node = table + i;
 626       assert (node->next);
 627       printf ("    case %u: value = %u; break;", real_index (node->index),
 628               real_index (node->next->index));
 629       printf ("\t/* %s --> %s.  */\n", get_aarch64_opcode (node)->name,
 630               get_aarch64_opcode (node->next)->name);
 631     }
 632
 633   printf ("    default: return NULL;\n");
 634   printf ("    }\n\n");
 635
 636   printf ("  return aarch64_opcode_table + value;\n");
 637   printf ("}\n");
 638 }
 639
 640 /* Generate aarch64_find_next_alias_opcode in C code to the standard output.
 641    TABLE points to the alias info table, while NUM indicates the number of
 642    entries in the table.  */
 643
 644 static void
 645 print_find_next_alias_opcode (const opcode_node *table, int num)
 646 {
 647   int i;
 648
 649   if (debug)
 650     printf ("Enter print_find_next_alias_opcode\n");
 651
 652   printf ("\n");
 653   printf ("const aarch64_opcode *\n");
 654   printf ("aarch64_find_next_alias_opcode (const aarch64_opcode *opcode)\n");
 655   printf ("{\n");
 656   printf ("  /* Use the index as the key to locate the next opcode.  */\n");
 657   printf ("  int key = opcode - aarch64_opcode_table;\n");
 658   printf ("  int value;\n");
 659   printf ("  switch (key)\n");
 660   printf ("    {\n");
 661
 662   for (i = 0; i < num; ++i)
 663     {
 664       const opcode_node *node = table + i;
 665       assert (node->next);
 666       if (node->next->next == NULL)
 667         continue;
 668       while (node->next->next)
 669         {
 670           printf ("    case %u: value = %u; break;", real_index (node->next->index),
 671                  real_index (node->next->next->index));
 672           printf ("\t/* %s --> %s.  */\n",
 673                   get_aarch64_opcode (node->next)->name,
 674                   get_aarch64_opcode (node->next->next)->name);
 675           node = node->next;
 676         }
 677     }
 678
 679   printf ("    default: return NULL;\n");
 680   printf ("    }\n\n");
 681
 682   printf ("  return aarch64_opcode_table + value;\n");
 683   printf ("}\n");
 684 }
 685
 686 /* Given OPCODE, establish and return a link list of alias nodes in the
 687    preferred order.  */
 688
 689 opcode_node *
 690 find_alias_opcode (const aarch64_opcode *opcode)
 691 {
 692   int i;
 693   /* Assume maximum of 32 disassemble preference candidates.  */
 694   const int max_num_aliases = 32;
 695   const aarch64_opcode *ent;
 696   const aarch64_opcode *preferred[max_num_aliases + 1];
 697   opcode_node head, **next;
 698
 699   assert (opcode_has_alias (opcode));
 700
 701   i = 0;
 702   if (opcode->name != NULL)
 703     preferred[i++] = opcode;
 704   ent = aarch64_opcode_table;
 705   while (ent->name != NULL)
 706     {
 707       /* The mask of an alias opcode must be equal to or a super-set (i.e.
 708          more constrained) of that of the aliased opcode; so is the base
 709          opcode value.  */
 710       if (alias_opcode_p (ent)
 711           && (ent->mask & opcode->mask) == opcode->mask
 712           && (opcode->mask & ent->opcode) == (opcode->mask & opcode->opcode))
 713         {
 714           assert (i < max_num_aliases);
 715           preferred[i++] = ent;
 716           if (debug)
 717             printf ("found %s for %s.", ent->name, opcode->name);
 718         }
 719       ++ent;
 720     }
 721
 722   if (debug)
 723     {
 724       int m;
 725       printf ("un-orderd list: ");
 726       for (m = 0; m < i; ++m)
 727         printf ("%s, ", preferred[m]->name);
 728       printf ("\n");
 729     }
 730
 731   /* There must be at least one alias.  */
 732   assert (i >= 1);
 733
 734   /* Sort preferred array according to the priority (from the lowest to the
 735      highest.  */
 736   if (i > 1)
 737     {
 738       int j, k;
 739       for (j = 0; j < i - 1; ++j)
 740         {
 741           for (k = 0; k < i - 1 - j; ++k)
 742             {
 743               const aarch64_opcode *t;
 744               t = preferred [k+1];
 745               if (opcode_priority (t) < opcode_priority (preferred [k]))
 746                 {
 747                   preferred [k+1] = preferred [k];
 748                   preferred [k] = t;
 749                 }
 750             }
 751         }
 752     }
 753
 754   if (debug)
 755     {
 756       int m;
 757       printf ("orderd list: ");
 758       for (m = 0; m < i; ++m)
 759         printf ("%s, ", preferred[m]->name);
 760       printf ("\n");
 761     }
 762
 763   /* Create a link-list of opcode_node with disassemble preference from
 764      higher to lower.  */
 765   next = &head.next;
 766   --i;
 767   while (i >= 0)
 768     {
 769       const aarch64_opcode *alias = preferred [i];
 770       opcode_node *node = new_opcode_node ();
 771
 772       if (debug)
 773         printf ("add %s.\n", alias->name);
 774
 775       node->index = alias - aarch64_opcode_table;
 776       *next = node;
 777       next = &node->next;
 778
 779       --i;
 780     }
 781   *next = NULL;
 782
 783   return head.next;
 784 }
 785
 786 /* Create and return alias information.
 787    Return the address of the created alias info table; return the number
 788    of table entries in *NUM_PTR.  */
 789
 790 opcode_node *
 791 create_alias_info (int *num_ptr)
 792 {
 793   int i, num;
 794   opcode_node *ret;
 795   const aarch64_opcode *ent;
 796
 797   /* Calculate the total number of opcodes that have alias.  */
 798   num = 0;
 799   ent = aarch64_opcode_table;
 800   while (ent->name != NULL)
 801     {
 802       if (opcode_has_alias (ent))
 803         {
 804           /* Assert the alias relationship be flat-structured to keep
 805              algorithms simple; not allow F_ALIAS and F_HAS_ALIAS both
 806              specified.  */
 807           assert (!alias_opcode_p (ent));
 808           ++num;
 809         }
 810       ++ent;
 811     }
 812   assert (num_ptr);
 813   *num_ptr = num;
 814
 815   /* The array of real opcodes that have alias(es).  */
 816   ret = malloc (sizeof (opcode_node) * num);
 817
 818   /* For each opcode, establish a list of alias nodes in a preferred
 819      order.  */
 820   for (i = 0, ent = aarch64_opcode_table; i < num; ++i, ++ent)
 821     {
 822       opcode_node *node = ret + i;
 823       while (ent->name != NULL && !opcode_has_alias (ent))
 824         ++ent;
 825       assert (ent->name != NULL);
 826       node->index = ent - aarch64_opcode_table;
 827       node->next = find_alias_opcode (ent);
 828       assert (node->next);
 829     }
 830   assert (i == num);
 831
 832   return ret;
 833 }
 834
 835 /* Release the dynamic memory resource allocated for the generation of the
 836    alias information.  */
 837
 838 void
 839 release_resource_alias_info (opcode_node *alias_info, int num)
 840 {
 841   int i = 0;
 842   opcode_node *node = alias_info;
 843
 844   /* Free opcode_node list.  */
 845   for (; i < num; ++i, ++node)
 846     {
 847       opcode_node *list = node->next;
 848       do
 849         {
 850           opcode_node *next = list->next;
 851           free (list);
 852           list = next;
 853         } while (list != NULL);
 854     }
 855
 856   /* Free opcode_node array.  */
 857   free (alias_info);
 858 }
 859
 860 /* As a debugging utility, print out the result of the table division, although
 861    it is not doing much this moment.  */
 862 static void
 863 print_divide_result (const struct bittree *bittree ATTRIBUTE_UNUSED)
 864 {
 865   printf ("max_num_opcodes_at_leaf_node: %d\n", max_num_opcodes_at_leaf_node);
 866   return;
 867 }
 868 \f
 869 /* Structure to help generate the operand table.  */
 870 struct operand
 871 {
 872   const char *class;
 873   const char *inserter;
 874   const char *extractor;
 875   const char *str;
 876   const char *flags;
 877   const char *fields;
 878   const char *desc;
 879   unsigned processed : 1;
 880   unsigned has_inserter : 1;
 881   unsigned has_extractor : 1;
 882 };
 883
 884 typedef struct operand operand;
 885
 886 #ifdef X
 887 #undef X
 888 #endif
 889
 890 #ifdef Y
 891 #undef Y
 892 #endif
 893
 894 #ifdef F
 895 #undef F
 896 #endif
 897
 898 /* Get the operand information in strings.  */
 899
 900 static operand operands[] =
 901 {
 902     {"NIL", "0", "0", "", "0", "{0}", "<none>", 0, 0, 0},
 903 #define F(...)  #__VA_ARGS__
 904 #define X(a,b,c,d,e,f,g)        \
 905     {#a, #b, #c, d, #e, "{"f"}", g, 0, 0, 0},
 906 #define Y(a,b,d,e,f,g)          \
 907     {#a, "ins_"#b, "ext_"#b, d, #e, "{"f"}", g, 0, 0, 0},
 908     AARCH64_OPERANDS
 909     {"NIL", "0", "0", "", "0", "{0}", "DUMMY", 0, 0, 0},
 910 };
 911
 912 #undef F
 913 #undef X
 914
 915 static void
 916 process_operand_table (void)
 917 {
 918   int i;
 919   operand *opnd;
 920   const int num = sizeof (operands) / sizeof (operand);
 921
 922   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
 923     {
 924       opnd->has_inserter = opnd->inserter[0] != '0';
 925       opnd->has_extractor = opnd->extractor[0] != '0';
 926     }
 927 }
 928
 929 /* Generate aarch64_operands in C to the standard output.  */
 930
 931 static void
 932 print_operand_table (void)
 933 {
 934   int i;
 935   operand *opnd;
 936   const int num = sizeof (operands) / sizeof (operand);
 937
 938   if (debug)
 939     printf ("Enter print_operand_table\n");
 940
 941   printf ("\n");
 942   printf ("const struct aarch64_operand aarch64_operands[] =\n");
 943   printf ("{\n");
 944
 945   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
 946     {
 947       char flags[256];
 948       flags[0] = '\0';
 949       if (opnd->flags[0] != '0')
 950         sprintf (flags, "%s", opnd->flags);
 951       if (opnd->has_inserter)
 952         {
 953           if (flags[0] != '\0')
 954             strcat (flags, " | ");
 955           strcat (flags, "OPD_F_HAS_INSERTER");
 956         }
 957       if (opnd->has_extractor)
 958         {
 959           if (flags[0] != '\0')
 960             strcat (flags, " | ");
 961           strcat (flags, "OPD_F_HAS_EXTRACTOR");
 962         }
 963       if (flags[0] == '\0')
 964         {
 965           flags[0] = '0';
 966           flags[1] = '\0';
 967         }
 968     printf ("  {AARCH64_OPND_CLASS_%s, \"%s\", %s, %s, \"%s\"},\n",
 969             opnd->class, opnd->str, flags, opnd->fields, opnd->desc);
 970     }
 971   printf ("};\n");
 972 }
 973
 974 /* Generate aarch64_insert_operand in C to the standard output.  */
 975
 976 static void
 977 print_operand_inserter (void)
 978 {
 979   int i;
 980   operand *opnd;
 981   const int num = sizeof (operands) / sizeof (operand);
 982
 983   if (debug)
 984     printf ("Enter print_operand_inserter\n");
 985
 986   printf ("\n");
 987   printf ("bfd_boolean\n");
 988   printf ("aarch64_insert_operand (const aarch64_operand *self,\n\
 989                            const aarch64_opnd_info *info,\n\
 990                            aarch64_insn *code, const aarch64_inst *inst,\n\
 991                            aarch64_operand_error *errors)\n");
 992   printf ("{\n");
 993   printf ("  /* Use the index as the key.  */\n");
 994   printf ("  int key = self - aarch64_operands;\n");
 995   printf ("  switch (key)\n");
 996   printf ("    {\n");
 997
 998   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
 999     opnd->processed = 0;
1000
1001   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
1002     {
1003       if (!opnd->processed && opnd->has_inserter)
1004         {
1005           int j = i + 1;
1006           const int len = strlen (opnd->inserter);
1007           operand *opnd2 = opnd + 1;
1008           printf ("    case %u:\n", (unsigned int)(opnd - operands));
1009           opnd->processed = 1;
1010           for (; j < num; ++j, ++opnd2)
1011             {
1012               if (!opnd2->processed
1013                   && opnd2->has_inserter
1014                   && len == strlen (opnd2->inserter)
1015                   && strncmp (opnd->inserter, opnd2->inserter, len) == 0)
1016                 {
1017                   printf ("    case %u:\n", (unsigned int)(opnd2 - operands));
1018                   opnd2->processed = 1;
1019                 }
1020             }
1021           printf ("      return aarch64_%s (self, info, code, inst, errors);\n",
1022                   opnd->inserter);
1023         }
1024     }
1025
1026   printf ("    default: assert (0); abort ();\n");
1027   printf ("    }\n");
1028   printf ("}\n");
1029 }
1030
1031 /* Generate aarch64_extract_operand in C to the standard output.  */
1032
1033 static void
1034 print_operand_extractor (void)
1035 {
1036   int i;
1037   operand *opnd;
1038   const int num = sizeof (operands) / sizeof (operand);
1039
1040   if (debug)
1041     printf ("Enter print_operand_extractor\n");
1042
1043   printf ("\n");
1044   printf ("bfd_boolean\n");
1045   printf ("aarch64_extract_operand (const aarch64_operand *self,\n\
1046                            aarch64_opnd_info *info,\n\
1047                            aarch64_insn code, const aarch64_inst *inst,\n\
1048                            aarch64_operand_error *errors)\n");
1049   printf ("{\n");
1050   printf ("  /* Use the index as the key.  */\n");
1051   printf ("  int key = self - aarch64_operands;\n");
1052   printf ("  switch (key)\n");
1053   printf ("    {\n");
1054
1055   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
1056     opnd->processed = 0;
1057
1058   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
1059     {
1060       if (!opnd->processed && opnd->has_extractor)
1061         {
1062           int j = i + 1;
1063           const int len = strlen (opnd->extractor);
1064           operand *opnd2 = opnd + 1;
1065           printf ("    case %u:\n", (unsigned int)(opnd - operands));
1066           opnd->processed = 1;
1067           for (; j < num; ++j, ++opnd2)
1068             {
1069               if (!opnd2->processed
1070                   && opnd2->has_extractor
1071                   && len == strlen (opnd2->extractor)
1072                   && strncmp (opnd->extractor, opnd2->extractor, len) == 0)
1073                 {
1074                   printf ("    case %u:\n", (unsigned int)(opnd2 - operands));
1075                   opnd2->processed = 1;
1076                 }
1077             }
1078           printf ("      return aarch64_%s (self, info, code, inst, errors);\n",
1079                   opnd->extractor);
1080         }
1081     }
1082
1083   printf ("    default: assert (0); abort ();\n");
1084   printf ("    }\n");
1085   printf ("}\n");
1086 }
1087 \f
1088 /* Table indexed by opcode enumerator stores the index of the corresponding
1089    opcode entry in aarch64_opcode_table.  */
1090 static unsigned op_enum_table [OP_TOTAL_NUM];
1091
1092 /* Print out the routine which, given the opcode enumerator, returns the
1093    corresponding opcode entry pointer.  */
1094
1095 static void
1096 print_get_opcode (void)
1097 {
1098   int i;
1099   const int num = OP_TOTAL_NUM;
1100   const aarch64_opcode *opcode;
1101
1102   if (debug)
1103     printf ("Enter print_get_opcode\n");
1104
1105   /* Fill in the internal table.  */
1106   opcode = aarch64_opcode_table;
1107   while (opcode->name != NULL)
1108     {
1109       if (opcode->op != OP_NIL)
1110         {
1111           /* Assert opcode enumerator be unique, in other words, no shared by
1112              different opcodes.  */
1113           if (op_enum_table[opcode->op] != 0)
1114             {
1115               fprintf (stderr, "Opcode %u is shared by different %s and %s.\n",
1116                        opcode->op,
1117                        aarch64_opcode_table[op_enum_table[opcode->op]].name,
1118                        opcode->name);
1119               assert (0);
1120               abort ();
1121             }
1122           assert (opcode->op < OP_TOTAL_NUM);
1123           op_enum_table[opcode->op] = opcode - aarch64_opcode_table;
1124         }
1125       ++opcode;
1126     }
1127
1128   /* Print the table.  */
1129   printf ("\n");
1130   printf ("/* Indexed by an enum aarch64_op enumerator, the value is the offset of\n\
1131    the corresponding aarch64_opcode entry in the aarch64_opcode_table.  */\n\n");
1132   printf ("static const unsigned op_enum_table [] =\n");
1133   printf ("{\n");
1134   for (i = 0; i < num; ++i)
1135     printf ("  %u,\n", op_enum_table[i]);
1136   printf ("};\n");
1137
1138   /* Print the function.  */
1139   printf ("\n");
1140   printf ("/* Given the opcode enumerator OP, return the pointer to the corresponding\n");
1141   printf ("   opcode entry.  */\n");
1142   printf ("\n");
1143   printf ("const aarch64_opcode *\n");
1144   printf ("aarch64_get_opcode (enum aarch64_op op)\n");
1145   printf ("{\n");
1146   printf ("  return aarch64_opcode_table + op_enum_table[op];\n");
1147   printf ("}\n");
1148 }
1149
1150 /* Print out the content of an opcode table (not in use).  */
1151 static void ATTRIBUTE_UNUSED
1152 print_table (struct aarch64_opcode* table)
1153 {
1154   struct aarch64_opcode *ent = table;
1155   do
1156     {
1157       printf ("%s\t%08x\t%08x\n", ent->name, (unsigned int)ent->opcode,
1158               (unsigned int)ent->mask);
1159     } while ((++ent)->name);
1160 }
1161 \f
1162 static const char * program_name = NULL;
1163
1164 /* Program options.  */
1165 struct option long_options[] =
1166 {
1167   {"debug",   no_argument,       NULL, 'd'},
1168   {"version", no_argument,       NULL, 'V'},
1169   {"help",    no_argument,       NULL, 'h'},
1170   {"gen-opc", no_argument,       NULL, 'c'},
1171   {"gen-asm", no_argument,       NULL, 'a'},
1172   {"gen-dis", no_argument,       NULL, 's'},
1173   {0,         no_argument,       NULL, 0}
1174 };
1175
1176 static void
1177 print_version (void)
1178 {
1179   printf ("%s: version 1.0\n", program_name);
1180   xexit (0);
1181 }
1182
1183 static void
1184 usage (FILE * stream, int status)
1185 {
1186   fprintf (stream, "Usage: %s [-V | --version] [-d | --debug] [--help]\n",
1187            program_name);
1188   fprintf (stream, "\t[ [-c | --gen-opc] | [-a | --gen-asm] | [-s | --gen-dis] ]\n");
1189   xexit (status);
1190 }
1191
1192 int
1193 main (int argc, char **argv)
1194 {
1195   extern int chdir (char *);
1196   int c;
1197   int gen_opcode_p = 0;
1198   int gen_assembler_p = 0;
1199   int gen_disassembler_p = 0;
1200
1201   program_name = *argv;
1202   xmalloc_set_program_name (program_name);
1203
1204   while ((c = getopt_long (argc, argv, "vVdhacs", long_options, 0)) != EOF)
1205     switch (c)
1206       {
1207       case 'V':
1208       case 'v':
1209         print_version ();
1210         break;
1211       case 'd':
1212         debug = 1;
1213         break;
1214       case 'h':
1215       case '?':
1216         usage (stderr, 0);
1217         break;
1218       case 'c':
1219         gen_opcode_p = 1;
1220         break;
1221       case 'a':
1222         gen_assembler_p = 1;
1223         break;
1224       case 's':
1225         gen_disassembler_p = 1;
1226         break;
1227       default:
1228       case 0:
1229         break;
1230       }
1231
1232   if (argc == 1 || optind != argc)
1233     usage (stdout, 1);
1234
1235   if (gen_opcode_p + gen_assembler_p + gen_disassembler_p > 1)
1236     {
1237       printf ("Please specify only one of the following options\n\
1238               [-c | --gen-opc] [-a | --gen-asm] [-s | --gen-dis]\n");
1239       xexit (2);
1240     }
1241
1242   struct bittree *decoder_tree;
1243
1244   decoder_tree = initialize_decoder_tree ();
1245   if (debug)
1246     print_divide_result (decoder_tree);
1247
1248   printf ("/* This file is automatically generated by aarch64-gen.  Do not edit!  */\n");
1249   printf ("/* Copyright (C) 2012-2019 Free Software Foundation, Inc.\n\
1250    Contributed by ARM Ltd.\n\
1251 \n\
1252    This file is part of the GNU opcodes library.\n\
1253 \n\
1254    This library is free software; you can redistribute it and/or modify\n\
1255    it under the terms of the GNU General Public License as published by\n\
1256    the Free Software Foundation; either version 3, or (at your option)\n\
1257    any later version.\n\
1258 \n\
1259    It is distributed in the hope that it will be useful, but WITHOUT\n\
1260    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY\n\
1261    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public\n\
1262    License for more details.\n\
1263 \n\
1264    You should have received a copy of the GNU General Public License\n\
1265    along with this program; see the file COPYING3. If not,\n\
1266    see <http://www.gnu.org/licenses/>.  */\n");
1267
1268   printf ("\n");
1269   printf ("#include \"sysdep.h\"\n");
1270   if (gen_opcode_p)
1271     printf ("#include \"aarch64-opc.h\"\n");
1272   if (gen_assembler_p)
1273     printf ("#include \"aarch64-asm.h\"\n");
1274   if (gen_disassembler_p)
1275     printf ("#include \"aarch64-dis.h\"\n");
1276   printf ("\n");
1277
1278   /* Generate opcode entry lookup for the disassembler.  */
1279   if (gen_disassembler_p)
1280     {
1281       print_decision_tree (decoder_tree);
1282       print_find_next_opcode (decoder_tree);
1283       release_resource_decoder_tree (decoder_tree);
1284     }
1285
1286   /* Generate alias opcode handling for the assembler or the disassembler.  */
1287   if (gen_assembler_p || gen_disassembler_p)
1288     {
1289       int num;
1290       opcode_node *alias_info = create_alias_info (&num);
1291
1292       if (gen_assembler_p)
1293         print_find_real_opcode (alias_info, num);
1294
1295       if (gen_disassembler_p)
1296         {
1297           print_find_alias_opcode (alias_info, num);
1298           print_find_next_alias_opcode (alias_info, num);
1299         }
1300
1301       release_resource_alias_info (alias_info, num);
1302     }
1303
1304   /* Generate operand table.  */
1305   process_operand_table ();
1306
1307   if (gen_assembler_p)
1308     print_operand_inserter ();
1309
1310   if (gen_disassembler_p)
1311     print_operand_extractor ();
1312
1313   if (gen_opcode_p)
1314     print_operand_table ();
1315
1316   /* Generate utility to return aarch64_opcode entry given an enumerator.  */
1317   if (gen_opcode_p)
1318     print_get_opcode ();
1319
1320   exit (0);
1321 }