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-2016 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 #include "aarch64-tbl.h"
  32
  33 static int debug = 0;
  34
  35 /* Structure used in the decoding tree to group a list of aarch64_opcode
  36    entries.  */
  37
  38 struct opcode_node
  39 {
  40   aarch64_insn opcode;
  41   aarch64_insn mask;
  42   /* Index of the entry in the original table; the top 2 bits help
  43      determine the table.  */
  44   unsigned int index;
  45   struct opcode_node *next;
  46 };
  47
  48 typedef struct opcode_node opcode_node;
  49
  50 /* Head of the list of the opcode_node after read_table.  */
  51 static opcode_node opcode_nodes_head;
  52
  53 /* Node in the decoding tree.  */
  54
  55 struct bittree
  56 {
  57   unsigned int bitno;
  58   /* 0, 1, and X (don't care).  */
  59   struct bittree *bits[2];
  60   /* List of opcodes; only valid for the leaf node.  */
  61   opcode_node *list;
  62 };
  63
  64 /* Allocate and initialize an opcode_node.  */
  65 static opcode_node*
  66 new_opcode_node (void)
  67 {
  68   opcode_node* ent = malloc (sizeof (opcode_node));
  69
  70   if (!ent)
  71     abort ();
  72
  73   ent->opcode = 0;
  74   ent->mask = 0;
  75   ent->index = -1;
  76   ent->next = NULL;
  77
  78   return ent;
  79 }
  80
  81 /* Multiple tables are supported, although currently only one table is
  82    in use.  N.B. there are still some functions have the table name
  83    'aarch64_opcode_table' hard-coded in, e.g. print_find_next_opcode;
  84    therefore some amount of work needs to be done if the full support
  85    for multiple tables needs to be enabled.  */
  86 static const struct aarch64_opcode *aarch64_opcode_tables[] =
  87 {aarch64_opcode_table};
  88
  89 /* Use top 2 bits to indiate which table.  */
  90 static unsigned int
  91 initialize_index (const struct aarch64_opcode* table)
  92 {
  93   int i;
  94   const int num_of_tables = sizeof (aarch64_opcode_tables)
  95     / sizeof (struct aarch64_opcode *);
  96   for (i = 0; i < num_of_tables; ++i)
  97     if (table == aarch64_opcode_tables [i])
  98       break;
  99   if (i == num_of_tables)
 100     abort ();
 101   return (unsigned int)i << 30;
 102 }
 103
 104 static inline const struct aarch64_opcode *
 105 index2table (unsigned int index)
 106 {
 107   return aarch64_opcode_tables[(index >> 30) & 0x3];
 108 }
 109
 110 static inline unsigned int
 111 real_index (unsigned int index)
 112 {
 113   return index & ((1 << 30) - 1);
 114 }
 115
 116 /* Given OPCODE_NODE, return the corresponding aarch64_opcode*.  */
 117 static const aarch64_opcode*
 118 get_aarch64_opcode (const opcode_node *opcode_node)
 119 {
 120   if (opcode_node == NULL)
 121     return NULL;
 122   return &index2table (opcode_node->index)[real_index (opcode_node->index)];
 123 }
 124
 125 static void
 126 read_table (const struct aarch64_opcode* table)
 127 {
 128   const struct aarch64_opcode *ent = table;
 129   opcode_node **new_ent;
 130   unsigned int index = initialize_index (table);
 131
 132   if (!ent->name)
 133     return;
 134
 135   new_ent = &opcode_nodes_head.next;
 136
 137   while (*new_ent)
 138     new_ent = &(*new_ent)->next;
 139
 140   do
 141     {
 142       /* F_PSEUDO needs to be used together with F_ALIAS to indicate an alias
 143          opcode is a programmer friendly pseudo instruction available only in
 144          the assembly code (thus will not show up in the disassembly).  */
 145       assert (pseudo_opcode_p (ent) == FALSE || alias_opcode_p (ent) == TRUE);
 146       /* Skip alias (inc. pseudo) opcode.  */
 147       if (alias_opcode_p (ent) == TRUE)
 148         {
 149           index++;
 150           continue;
 151         }
 152       *new_ent = new_opcode_node ();
 153       (*new_ent)->opcode = ent->opcode;
 154       (*new_ent)->mask = ent->mask;
 155       (*new_ent)->index = index++;
 156       new_ent = &((*new_ent)->next);
 157     } while ((++ent)->name);
 158 }
 159
 160 static inline void
 161 print_one_opcode_node (opcode_node* ent)
 162 {
 163   printf ("%s\t%08x\t%08x\t%d\n", get_aarch64_opcode (ent)->name,
 164           get_aarch64_opcode (ent)->opcode, get_aarch64_opcode (ent)->mask,
 165           (int)real_index (ent->index));
 166 }
 167
 168 /* As an internal debugging utility, print out the list of nodes pointed
 169    by opcode_nodes_head.  */
 170 static void
 171 print_opcode_nodes (void)
 172 {
 173   opcode_node* ent = opcode_nodes_head.next;
 174   printf ("print_opcode_nodes table:\n");
 175   while (ent)
 176     {
 177       print_one_opcode_node (ent);
 178       ent = ent->next;
 179     }
 180 }
 181
 182 static struct bittree*
 183 new_bittree_node (void)
 184 {
 185   struct bittree* node;
 186   node = malloc (sizeof (struct bittree));
 187   if (!node)
 188     abort ();
 189   node->bitno = -1;
 190   node->bits[0] = NULL;
 191   node->bits[1] = NULL;
 192   return node;
 193 }
 194
 195 /* The largest number of opcode entries that exist at a leaf node of the
 196    decoding decision tree.  The reason that there can be more than one
 197    opcode entry is because some opcodes have shared field that is partially
 198    constrained and thus cannot be fully isolated using the algorithm
 199    here.  */
 200 static int max_num_opcodes_at_leaf_node = 0;
 201
 202 /* Given a list of opcodes headed by *OPCODE, try to establish one bit that
 203    is shared by all the opcodes in the list as one of base opcode bits.  If
 204    such a bit is found, divide the list of the opcodes into two based on the
 205    value of the bit.
 206
 207    Store the bit number in BITTREE->BITNO if the division succeeds.  If unable
 208    to determine such a bit or there is only one opcode in the list, the list
 209    is decided to be undividable and OPCODE will be assigned to BITTREE->LIST.
 210
 211    The function recursively call itself until OPCODE is undividable.
 212
 213    N.B. the nature of this algrithm determines that given any value in the
 214    32-bit space, the computed decision tree will always be able to find one or
 215    more opcodes entries for it, regardless whether there is a valid instruction
 216    defined for this value or not.  In order to detect the undefined values,
 217    when the caller obtains the opcode entry/entries, it should at least compare
 218    the bit-wise AND result of the value and the mask with the base opcode
 219    value; if the two are different, it means that the value is undefined
 220    (although the value may be still undefined when the comparison is the same,
 221    in which case call aarch64_opcode_decode to carry out further checks).  */
 222
 223 static void
 224 divide_table_1 (struct bittree *bittree, opcode_node *opcode)
 225 {
 226   aarch64_insn mask_and;
 227   opcode_node *ent;
 228   unsigned int bitno;
 229   aarch64_insn bitmask;
 230   opcode_node list0, list1, **ptr0, **ptr1;
 231   static int depth = 0;
 232
 233   ++depth;
 234
 235   if (debug)
 236     printf ("Enter into depth %d\n", depth);
 237
 238   assert (opcode != NULL);
 239
 240   /* Succeed when there is only one opcode left.  */
 241   if (!opcode->next)
 242     {
 243       if (debug)
 244         {
 245           printf ("opcode isolated:\n");
 246           print_one_opcode_node (opcode);
 247         }
 248       goto divide_table_1_finish;
 249     }
 250
 251 divide_table_1_try_again:
 252   mask_and = -1;
 253   ent = opcode;
 254   while (ent)
 255     {
 256       mask_and &= ent->mask;
 257       ent = ent->next;
 258     }
 259
 260   if (debug)
 261     printf ("mask and result: %08x\n", (unsigned int)mask_and);
 262
 263   /* If no more bit to look into, we have to accept the reality then.  */
 264   if (!mask_and)
 265     {
 266       int i;
 267       opcode_node *ptr;
 268       if (debug)
 269         {
 270           ptr = opcode;
 271           printf ("Isolated opcode group:\n");
 272           do {
 273               print_one_opcode_node (ptr);
 274               ptr = ptr->next;
 275           } while (ptr);
 276         }
 277       /* Count the number of opcodes.  */
 278       for (i = 0, ptr = opcode; ptr; ++i)
 279         ptr = ptr->next;
 280       if (i > max_num_opcodes_at_leaf_node)
 281         max_num_opcodes_at_leaf_node = i;
 282       goto divide_table_1_finish;
 283     }
 284
 285   /* Pick up the right most bit that is 1.  */
 286   bitno = 0;
 287   while (!(mask_and & (1 << bitno)))
 288     ++bitno;
 289   bitmask = (1 << bitno);
 290
 291   if (debug)
 292     printf ("use bit %d\n", bitno);
 293
 294   /* Record in the bittree.  */
 295   bittree->bitno = bitno;
 296
 297   /* Get two new opcode lists; adjust their masks.  */
 298   list0.next = NULL;
 299   list1.next = NULL;
 300   ptr0 = &list0.next;
 301   ptr1 = &list1.next;
 302   ent = opcode;
 303   while (ent)
 304     {
 305       if (ent->opcode & bitmask)
 306         {
 307           ent->mask &= (~bitmask);
 308           *ptr1 = ent;
 309           ent = ent->next;
 310           (*ptr1)->next = NULL;
 311           ptr1 = &(*ptr1)->next;
 312         }
 313       else
 314         {
 315           ent->mask &= (~bitmask);
 316           *ptr0 = ent;
 317           ent = ent->next;
 318           (*ptr0)->next = NULL;
 319           ptr0 = &(*ptr0)->next;
 320         }
 321     }
 322
 323   /* If BITNO can NOT divide the opcode group, try next bit.  */
 324   if (list0.next == NULL)
 325     {
 326       opcode = list1.next;
 327       goto divide_table_1_try_again;
 328     }
 329   else if (list1.next == NULL)
 330     {
 331       opcode = list0.next;
 332       goto divide_table_1_try_again;
 333     }
 334
 335   /* Further divide.  */
 336   bittree->bits[0] = new_bittree_node ();
 337   bittree->bits[1] = new_bittree_node ();
 338   divide_table_1 (bittree->bits[0], list0.next);
 339   divide_table_1 (bittree->bits[1], list1.next);
 340
 341 divide_table_1_finish:
 342   if (debug)
 343     printf ("Leave from depth %d\n", depth);
 344   --depth;
 345
 346   /* Record the opcode entries on this leaf node.  */
 347   bittree->list = opcode;
 348
 349   return;
 350 }
 351
 352 /* Call divide_table_1 to divide the all the opcodes and thus create the
 353    decoding decision tree.  */
 354 static struct bittree *
 355 divide_table (void)
 356 {
 357   struct bittree *bittree = new_bittree_node ();
 358   divide_table_1 (bittree, opcode_nodes_head.next);
 359   return bittree;
 360 }
 361
 362 /* Read in all of the tables, create the decoding decision tree and return
 363    the tree root.  */
 364 static struct bittree *
 365 initialize_decoder_tree (void)
 366 {
 367   int i;
 368   const int num_of_tables = (sizeof (aarch64_opcode_tables)
 369                              / sizeof (struct aarch64_opcode *));
 370   for (i = 0; i < num_of_tables; ++i)
 371     read_table (aarch64_opcode_tables [i]);
 372   if (debug)
 373     print_opcode_nodes ();
 374   return divide_table ();
 375 }
 376
 377 static void __attribute__ ((format (printf, 2, 3)))
 378 indented_print (unsigned int indent, const char *format, ...)
 379 {
 380   /* 80 number of spaces pluc a NULL terminator.  */
 381   static const char spaces[81] =
 382     "                                                                                ";
 383   va_list ap;
 384   va_start (ap, format);
 385   assert (indent <= 80);
 386   printf ("%s", &spaces[80 - indent]);
 387   vprintf (format, ap);
 388   va_end (ap);
 389 }
 390
 391 /* N.B. read the comment above divide_table_1 for the reason why the generated
 392    decision tree function never returns NULL.  */
 393
 394 static void
 395 print_decision_tree_1 (unsigned int indent, struct bittree* bittree)
 396 {
 397   /* PATTERN is only used to generate comment in the code.  */
 398   static char pattern[33] = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
 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[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[bittree->bitno] = '1';
 424   print_decision_tree_1 (indent + 4, bittree->bits[1]);
 425   indented_print (indent, "  }\n");
 426   pattern[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 16 disassemble preference candidates.  */
 694   const int max_num_aliases = 16;
 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) == TRUE
 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 ("const char*\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   printf ("{\n");
 992   printf ("  /* Use the index as the key.  */\n");
 993   printf ("  int key = self - aarch64_operands;\n");
 994   printf ("  switch (key)\n");
 995   printf ("    {\n");
 996
 997   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
 998     opnd->processed = 0;
 999
1000   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
1001     {
1002       if (!opnd->processed && opnd->has_inserter)
1003         {
1004           int j = i + 1;
1005           const int len = strlen (opnd->inserter);
1006           operand *opnd2 = opnd + 1;
1007           printf ("    case %u:\n", (unsigned int)(opnd - operands));
1008           opnd->processed = 1;
1009           for (; j < num; ++j, ++opnd2)
1010             {
1011               if (!opnd2->processed
1012                   && opnd2->has_inserter
1013                   && len == strlen (opnd2->inserter)
1014                   && strncmp (opnd->inserter, opnd2->inserter, len) == 0)
1015                 {
1016                   printf ("    case %u:\n", (unsigned int)(opnd2 - operands));
1017                   opnd2->processed = 1;
1018                 }
1019             }
1020           printf ("      return aarch64_%s (self, info, code, inst);\n",
1021                   opnd->inserter);
1022         }
1023     }
1024
1025   printf ("    default: assert (0); abort ();\n");
1026   printf ("    }\n");
1027   printf ("}\n");
1028 }
1029
1030 /* Generate aarch64_extract_operand in C to the standard output.  */
1031
1032 static void
1033 print_operand_extractor (void)
1034 {
1035   int i;
1036   operand *opnd;
1037   const int num = sizeof (operands) / sizeof (operand);
1038
1039   if (debug)
1040     printf ("Enter print_operand_extractor\n");
1041
1042   printf ("\n");
1043   printf ("int\n");
1044   printf ("aarch64_extract_operand (const aarch64_operand *self,\n\
1045                            aarch64_opnd_info *info,\n\
1046                            aarch64_insn code, const aarch64_inst *inst)\n");
1047   printf ("{\n");
1048   printf ("  /* Use the index as the key.  */\n");
1049   printf ("  int key = self - aarch64_operands;\n");
1050   printf ("  switch (key)\n");
1051   printf ("    {\n");
1052
1053   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
1054     opnd->processed = 0;
1055
1056   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
1057     {
1058       if (!opnd->processed && opnd->has_extractor)
1059         {
1060           int j = i + 1;
1061           const int len = strlen (opnd->extractor);
1062           operand *opnd2 = opnd + 1;
1063           printf ("    case %u:\n", (unsigned int)(opnd - operands));
1064           opnd->processed = 1;
1065           for (; j < num; ++j, ++opnd2)
1066             {
1067               if (!opnd2->processed
1068                   && opnd2->has_extractor
1069                   && len == strlen (opnd2->extractor)
1070                   && strncmp (opnd->extractor, opnd2->extractor, len) == 0)
1071                 {
1072                   printf ("    case %u:\n", (unsigned int)(opnd2 - operands));
1073                   opnd2->processed = 1;
1074                 }
1075             }
1076           printf ("      return aarch64_%s (self, info, code, inst);\n",
1077                   opnd->extractor);
1078         }
1079     }
1080
1081   printf ("    default: assert (0); abort ();\n");
1082   printf ("    }\n");
1083   printf ("}\n");
1084 }
1085 \f
1086 /* Table indexed by opcode enumerator stores the index of the corresponding
1087    opcode entry in aarch64_opcode_table.  */
1088 static unsigned op_enum_table [OP_TOTAL_NUM];
1089
1090 /* Print out the routine which, given the opcode enumerator, returns the
1091    corresponding opcode entry pointer.  */
1092
1093 static void
1094 print_get_opcode (void)
1095 {
1096   int i;
1097   const int num = OP_TOTAL_NUM;
1098   const aarch64_opcode *opcode;
1099
1100   if (debug)
1101     printf ("Enter print_get_opcode\n");
1102
1103   /* Fill in the internal table.  */
1104   opcode = aarch64_opcode_table;
1105   while (opcode->name != NULL)
1106     {
1107       if (opcode->op != OP_NIL)
1108         {
1109           /* Assert opcode enumerator be unique, in other words, no shared by
1110              different opcodes.  */
1111           if (op_enum_table[opcode->op] != 0)
1112             {
1113               fprintf (stderr, "Opcode %u is shared by different %s and %s.\n",
1114                        opcode->op,
1115                        aarch64_opcode_table[op_enum_table[opcode->op]].name,
1116                        opcode->name);
1117               assert (0);
1118               abort ();
1119             }
1120           assert (opcode->op < OP_TOTAL_NUM);
1121           op_enum_table[opcode->op] = opcode - aarch64_opcode_table;
1122         }
1123       ++opcode;
1124     }
1125
1126   /* Print the table.  */
1127   printf ("\n");
1128   printf ("/* Indexed by an enum aarch64_op enumerator, the value is the offset of\n\
1129    the corresponding aarch64_opcode entry in the aarch64_opcode_table.  */\n\n");
1130   printf ("static const unsigned op_enum_table [] =\n");
1131   printf ("{\n");
1132   for (i = 0; i < num; ++i)
1133     printf ("  %u,\n", op_enum_table[i]);
1134   printf ("};\n");
1135
1136   /* Print the function.  */
1137   printf ("\n");
1138   printf ("/* Given the opcode enumerator OP, return the pointer to the corresponding\n");
1139   printf ("   opcode entry.  */\n");
1140   printf ("\n");
1141   printf ("const aarch64_opcode *\n");
1142   printf ("aarch64_get_opcode (enum aarch64_op op)\n");
1143   printf ("{\n");
1144   printf ("  return aarch64_opcode_table + op_enum_table[op];\n");
1145   printf ("}\n");
1146 }
1147
1148 /* Print out the content of an opcode table (not in use).  */
1149 static void ATTRIBUTE_UNUSED
1150 print_table (struct aarch64_opcode* table)
1151 {
1152   struct aarch64_opcode *ent = table;
1153   do
1154     {
1155       printf ("%s\t%08x\t%08x\n", ent->name, (unsigned int)ent->opcode,
1156               (unsigned int)ent->mask);
1157     } while ((++ent)->name);
1158 }
1159 \f
1160 static const char * program_name = NULL;
1161
1162 /* Program options.  */
1163 struct option long_options[] =
1164 {
1165   {"debug",   no_argument,       NULL, 'd'},
1166   {"version", no_argument,       NULL, 'V'},
1167   {"help",    no_argument,       NULL, 'h'},
1168   {"gen-opc", no_argument,       NULL, 'c'},
1169   {"gen-asm", no_argument,       NULL, 'a'},
1170   {"gen-dis", no_argument,       NULL, 's'},
1171   {0,         no_argument,       NULL, 0}
1172 };
1173
1174 static void
1175 print_version (void)
1176 {
1177   printf ("%s: version 1.0\n", program_name);
1178   xexit (0);
1179 }
1180
1181 static void
1182 usage (FILE * stream, int status)
1183 {
1184   fprintf (stream, "Usage: %s [-V | --version] [-d | --debug] [--help]\n",
1185            program_name);
1186   fprintf (stream, "\t[ [-c | --gen-opc] | [-a | --gen-asm] | [-s | --gen-dis] ]\n");
1187   xexit (status);
1188 }
1189
1190 int
1191 main (int argc, char **argv)
1192 {
1193   extern int chdir (char *);
1194   int c;
1195   int gen_opcode_p = 0;
1196   int gen_assembler_p = 0;
1197   int gen_disassembler_p = 0;
1198
1199   program_name = *argv;
1200   xmalloc_set_program_name (program_name);
1201
1202   while ((c = getopt_long (argc, argv, "vVdhacs", long_options, 0)) != EOF)
1203     switch (c)
1204       {
1205       case 'V':
1206       case 'v':
1207         print_version ();
1208         break;
1209       case 'd':
1210         debug = 1;
1211         break;
1212       case 'h':
1213       case '?':
1214         usage (stderr, 0);
1215         break;
1216       case 'c':
1217         gen_opcode_p = 1;
1218         break;
1219       case 'a':
1220         gen_assembler_p = 1;
1221         break;
1222       case 's':
1223         gen_disassembler_p = 1;
1224         break;
1225       default:
1226       case 0:
1227         break;
1228       }
1229
1230   if (argc == 1 || optind != argc)
1231     usage (stdout, 1);
1232
1233   if (gen_opcode_p + gen_assembler_p + gen_disassembler_p > 1)
1234     {
1235       printf ("Please specify only one of the following options\n\
1236               [-c | --gen-opc] [-a | --gen-asm] [-s | --gen-dis]\n");
1237       xexit (2);
1238     }
1239
1240   struct bittree *decoder_tree;
1241
1242   decoder_tree = initialize_decoder_tree ();
1243   if (debug)
1244     print_divide_result (decoder_tree);
1245
1246   printf ("/* This file is automatically generated by aarch64-gen.  Do not edit!  */\n");
1247   printf ("/* Copyright (C) 2012-2016 Free Software Foundation, Inc.\n\
1248    Contributed by ARM Ltd.\n\
1249 \n\
1250    This file is part of the GNU opcodes library.\n\
1251 \n\
1252    This library is free software; you can redistribute it and/or modify\n\
1253    it under the terms of the GNU General Public License as published by\n\
1254    the Free Software Foundation; either version 3, or (at your option)\n\
1255    any later version.\n\
1256 \n\
1257    It is distributed in the hope that it will be useful, but WITHOUT\n\
1258    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY\n\
1259    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public\n\
1260    License for more details.\n\
1261 \n\
1262    You should have received a copy of the GNU General Public License\n\
1263    along with this program; see the file COPYING3. If not,\n\
1264    see <http://www.gnu.org/licenses/>.  */\n");
1265
1266   printf ("\n");
1267   printf ("#include \"sysdep.h\"\n");
1268   if (gen_opcode_p)
1269     printf ("#include \"aarch64-opc.h\"\n");
1270   if (gen_assembler_p)
1271     printf ("#include \"aarch64-asm.h\"\n");
1272   if (gen_disassembler_p)
1273     printf ("#include \"aarch64-dis.h\"\n");
1274   printf ("\n");
1275
1276   /* Generate opcode entry lookup for the disassembler.  */
1277   if (gen_disassembler_p)
1278     {
1279       print_decision_tree (decoder_tree);
1280       print_find_next_opcode (decoder_tree);
1281       release_resource_decoder_tree (decoder_tree);
1282     }
1283
1284   /* Generate alias opcode handling for the assembler or the disassembler.  */
1285   if (gen_assembler_p || gen_disassembler_p)
1286     {
1287       int num;
1288       opcode_node *alias_info = create_alias_info (&num);
1289
1290       if (gen_assembler_p)
1291         print_find_real_opcode (alias_info, num);
1292
1293       if (gen_disassembler_p)
1294         {
1295           print_find_alias_opcode (alias_info, num);
1296           print_find_next_alias_opcode (alias_info, num);
1297         }
1298
1299       release_resource_alias_info (alias_info, num);
1300     }
1301
1302   /* Generate operand table.  */
1303   process_operand_table ();
1304
1305   if (gen_assembler_p)
1306     print_operand_inserter ();
1307
1308   if (gen_disassembler_p)
1309     print_operand_extractor ();
1310
1311   if (gen_opcode_p)
1312     print_operand_table ();
1313
1314   /* Generate utility to return aarch64_opcode entry given an enumerator.  */
1315   if (gen_opcode_p)
1316     print_get_opcode ();
1317
1318   exit (0);
1319 }