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-2017 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) == FALSE || alias_opcode_p (ent) == TRUE);
 147       /* Skip alias (inc. pseudo) opcode.  */
 148       if (alias_opcode_p (ent) == TRUE)
 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   assert (bittree != NULL);
 397
 398   /* Leaf node located.  */
 399   if (bittree->bits[0] == NULL && bittree->bits[1] == NULL)
 400     {
 401       assert (bittree->list != NULL);
 402       indented_print (indent, "/* 33222222222211111111110000000000\n");
 403       indented_print (indent, "   10987654321098765432109876543210\n");
 404       indented_print (indent, "   %s\n", pattern);
 405       indented_print (indent, "   %s.  */\n",
 406                       get_aarch64_opcode (bittree->list)->name);
 407       indented_print (indent, "return %u;\n",
 408                       real_index (bittree->list->index));
 409       return;
 410     }
 411
 412   /* Walk down the decoder tree.  */
 413   indented_print (indent, "if (((word >> %d) & 0x1) == 0)\n", bittree->bitno);
 414   indented_print (indent, "  {\n");
 415   pattern[bittree->bitno] = '0';
 416   print_decision_tree_1 (indent + 4, bittree->bits[0]);
 417   indented_print (indent, "  }\n");
 418   indented_print (indent, "else\n");
 419   indented_print (indent, "  {\n");
 420   pattern[bittree->bitno] = '1';
 421   print_decision_tree_1 (indent + 4, bittree->bits[1]);
 422   indented_print (indent, "  }\n");
 423   pattern[bittree->bitno] = 'x';
 424 }
 425
 426 /* Generate aarch64_opcode_lookup in C code to the standard output.  */
 427
 428 static void
 429 print_decision_tree (struct bittree* bittree)
 430 {
 431   if (debug)
 432     printf ("Enter print_decision_tree\n");
 433
 434   printf ("/* Called by aarch64_opcode_lookup.  */\n\n");
 435
 436   printf ("static int\n");
 437   printf ("aarch64_opcode_lookup_1 (uint32_t word)\n");
 438   printf ("{\n");
 439
 440   print_decision_tree_1 (2, bittree);
 441
 442   printf ("}\n\n");
 443
 444
 445   printf ("/* Lookup opcode WORD in the opcode table.  N.B. all alias\n");
 446   printf ("   opcodes are ignored here.  */\n\n");
 447
 448   printf ("const aarch64_opcode *\n");
 449   printf ("aarch64_opcode_lookup (uint32_t word)\n");
 450   printf ("{\n");
 451   printf ("  return aarch64_opcode_table + aarch64_opcode_lookup_1 (word);\n");
 452   printf ("}\n");
 453 }
 454
 455 static void
 456 print_find_next_opcode_1 (struct bittree* bittree)
 457 {
 458   assert (bittree != NULL);
 459
 460   /* Leaf node located.  */
 461   if (bittree->bits[0] == NULL && bittree->bits[1] == NULL)
 462     {
 463       assert (bittree->list != NULL);
 464       /* Find multiple opcode entries in one leaf node.  */
 465       if (bittree->list->next != NULL)
 466         {
 467           opcode_node *list = bittree->list;
 468           while (list != NULL)
 469             {
 470               const aarch64_opcode *curr = get_aarch64_opcode (list);
 471               const aarch64_opcode *next = get_aarch64_opcode (list->next);
 472
 473               printf ("    case %u: ",
 474                       (unsigned int)(curr - aarch64_opcode_table));
 475               if (list->next != NULL)
 476                 {
 477                   printf ("value = %u; break;\t", real_index (list->next->index));
 478                   printf ("/* %s --> %s.  */\n", curr->name, next->name);
 479                 }
 480               else
 481                 {
 482                   printf ("return NULL;\t\t");
 483                   printf ("/* %s --> NULL.  */\n", curr->name);
 484                 }
 485
 486               list = list->next;
 487             }
 488         }
 489       return;
 490     }
 491
 492   /* Walk down the decoder tree.  */
 493   print_find_next_opcode_1 (bittree->bits[0]);
 494   print_find_next_opcode_1 (bittree->bits[1]);
 495 }
 496
 497 /* Generate aarch64_find_next_opcode in C code to the standard output.  */
 498
 499 static void
 500 print_find_next_opcode (struct bittree* bittree)
 501 {
 502   if (debug)
 503     printf ("Enter print_find_next_opcode\n");
 504
 505   printf ("\n");
 506   printf ("const aarch64_opcode *\n");
 507   printf ("aarch64_find_next_opcode (const aarch64_opcode *opcode)\n");
 508   printf ("{\n");
 509   printf ("  /* Use the index as the key to locate the next opcode.  */\n");
 510   printf ("  int key = opcode - aarch64_opcode_table;\n");
 511   printf ("  int value;\n");
 512   printf ("  switch (key)\n");
 513   printf ("    {\n");
 514
 515   print_find_next_opcode_1 (bittree);
 516
 517   printf ("    default: return NULL;\n");
 518   printf ("    }\n\n");
 519
 520   printf ("  return aarch64_opcode_table + value;\n");
 521   printf ("}\n");
 522 }
 523
 524 /* Release the dynamic memory resource allocated for the generation of the
 525    decoder tree.  */
 526
 527 static void
 528 release_resource_decoder_tree (struct bittree* bittree)
 529 {
 530   assert (bittree != NULL);
 531
 532   /* Leaf node located.  */
 533   if (bittree->bits[0] == NULL && bittree->bits[1] == NULL)
 534     {
 535       assert (bittree->list != NULL);
 536       /* Free opcode_nodes.  */
 537       opcode_node *list = bittree->list;
 538       while (list != NULL)
 539         {
 540           opcode_node *next = list->next;
 541           free (list);
 542           list = next;
 543         }
 544       /* Free the tree node.  */
 545       free (bittree);
 546       return;
 547     }
 548
 549   /* Walk down the decoder tree.  */
 550   release_resource_decoder_tree (bittree->bits[0]);
 551   release_resource_decoder_tree (bittree->bits[1]);
 552
 553   /* Free the tree node.  */
 554   free (bittree);
 555 }
 556
 557 /* Generate aarch64_find_real_opcode in C code to the standard output.
 558    TABLE points to the alias info table, while NUM indicates the number of
 559    entries in the table.  */
 560
 561 static void
 562 print_find_real_opcode (const opcode_node *table, int num)
 563 {
 564   int i;
 565
 566   if (debug)
 567     printf ("Enter print_find_real_opcode\n");
 568
 569   printf ("\n");
 570   printf ("const aarch64_opcode *\n");
 571   printf ("aarch64_find_real_opcode (const aarch64_opcode *opcode)\n");
 572   printf ("{\n");
 573   printf ("  /* Use the index as the key to locate the real opcode.  */\n");
 574   printf ("  int key = opcode - aarch64_opcode_table;\n");
 575   printf ("  int value;\n");
 576   printf ("  switch (key)\n");
 577   printf ("    {\n");
 578
 579   for (i = 0; i < num; ++i)
 580     {
 581       const opcode_node *real = table + i;
 582       const opcode_node *alias = real->next;
 583       for (; alias; alias = alias->next)
 584         printf ("    case %u:\t/* %s */\n", real_index (alias->index),
 585                 get_aarch64_opcode (alias)->name);
 586       printf ("      value = %u;\t/* --> %s.  */\n", real_index (real->index),
 587               get_aarch64_opcode (real)->name);
 588       printf ("      break;\n");
 589     }
 590
 591   printf ("    default: return NULL;\n");
 592   printf ("    }\n\n");
 593
 594   printf ("  return aarch64_opcode_table + value;\n");
 595   printf ("}\n");
 596 }
 597
 598 /* Generate aarch64_find_alias_opcode in C code to the standard output.
 599    TABLE points to the alias info table, while NUM indicates the number of
 600    entries in the table.  */
 601
 602 static void
 603 print_find_alias_opcode (const opcode_node *table, int num)
 604 {
 605   int i;
 606
 607   if (debug)
 608     printf ("Enter print_find_alias_opcode\n");
 609
 610   printf ("\n");
 611   printf ("const aarch64_opcode *\n");
 612   printf ("aarch64_find_alias_opcode (const aarch64_opcode *opcode)\n");
 613   printf ("{\n");
 614   printf ("  /* Use the index as the key to locate the alias opcode.  */\n");
 615   printf ("  int key = opcode - aarch64_opcode_table;\n");
 616   printf ("  int value;\n");
 617   printf ("  switch (key)\n");
 618   printf ("    {\n");
 619
 620   for (i = 0; i < num; ++i)
 621     {
 622       const opcode_node *node = table + i;
 623       assert (node->next);
 624       printf ("    case %u: value = %u; break;", real_index (node->index),
 625               real_index (node->next->index));
 626       printf ("\t/* %s --> %s.  */\n", get_aarch64_opcode (node)->name,
 627               get_aarch64_opcode (node->next)->name);
 628     }
 629
 630   printf ("    default: return NULL;\n");
 631   printf ("    }\n\n");
 632
 633   printf ("  return aarch64_opcode_table + value;\n");
 634   printf ("}\n");
 635 }
 636
 637 /* Generate aarch64_find_next_alias_opcode in C code to the standard output.
 638    TABLE points to the alias info table, while NUM indicates the number of
 639    entries in the table.  */
 640
 641 static void
 642 print_find_next_alias_opcode (const opcode_node *table, int num)
 643 {
 644   int i;
 645
 646   if (debug)
 647     printf ("Enter print_find_next_alias_opcode\n");
 648
 649   printf ("\n");
 650   printf ("const aarch64_opcode *\n");
 651   printf ("aarch64_find_next_alias_opcode (const aarch64_opcode *opcode)\n");
 652   printf ("{\n");
 653   printf ("  /* Use the index as the key to locate the next opcode.  */\n");
 654   printf ("  int key = opcode - aarch64_opcode_table;\n");
 655   printf ("  int value;\n");
 656   printf ("  switch (key)\n");
 657   printf ("    {\n");
 658
 659   for (i = 0; i < num; ++i)
 660     {
 661       const opcode_node *node = table + i;
 662       assert (node->next);
 663       if (node->next->next == NULL)
 664         continue;
 665       while (node->next->next)
 666         {
 667           printf ("    case %u: value = %u; break;", real_index (node->next->index),
 668                  real_index (node->next->next->index));
 669           printf ("\t/* %s --> %s.  */\n",
 670                   get_aarch64_opcode (node->next)->name,
 671                   get_aarch64_opcode (node->next->next)->name);
 672           node = node->next;
 673         }
 674     }
 675
 676   printf ("    default: return NULL;\n");
 677   printf ("    }\n\n");
 678
 679   printf ("  return aarch64_opcode_table + value;\n");
 680   printf ("}\n");
 681 }
 682
 683 /* Given OPCODE, establish and return a link list of alias nodes in the
 684    preferred order.  */
 685
 686 opcode_node *
 687 find_alias_opcode (const aarch64_opcode *opcode)
 688 {
 689   int i;
 690   /* Assume maximum of 32 disassemble preference candidates.  */
 691   const int max_num_aliases = 32;
 692   const aarch64_opcode *ent;
 693   const aarch64_opcode *preferred[max_num_aliases + 1];
 694   opcode_node head, **next;
 695
 696   assert (opcode_has_alias (opcode));
 697
 698   i = 0;
 699   if (opcode->name != NULL)
 700     preferred[i++] = opcode;
 701   ent = aarch64_opcode_table;
 702   while (ent->name != NULL)
 703     {
 704       /* The mask of an alias opcode must be equal to or a super-set (i.e.
 705          more constrained) of that of the aliased opcode; so is the base
 706          opcode value.  */
 707       if (alias_opcode_p (ent) == TRUE
 708           && (ent->mask & opcode->mask) == opcode->mask
 709           && (opcode->mask & ent->opcode) == (opcode->mask & opcode->opcode))
 710         {
 711           assert (i < max_num_aliases);
 712           preferred[i++] = ent;
 713           if (debug)
 714             printf ("found %s for %s.", ent->name, opcode->name);
 715         }
 716       ++ent;
 717     }
 718
 719   if (debug)
 720     {
 721       int m;
 722       printf ("un-orderd list: ");
 723       for (m = 0; m < i; ++m)
 724         printf ("%s, ", preferred[m]->name);
 725       printf ("\n");
 726     }
 727
 728   /* There must be at least one alias.  */
 729   assert (i >= 1);
 730
 731   /* Sort preferred array according to the priority (from the lowest to the
 732      highest.  */
 733   if (i > 1)
 734     {
 735       int j, k;
 736       for (j = 0; j < i - 1; ++j)
 737         {
 738           for (k = 0; k < i - 1 - j; ++k)
 739             {
 740               const aarch64_opcode *t;
 741               t = preferred [k+1];
 742               if (opcode_priority (t) < opcode_priority (preferred [k]))
 743                 {
 744                   preferred [k+1] = preferred [k];
 745                   preferred [k] = t;
 746                 }
 747             }
 748         }
 749     }
 750
 751   if (debug)
 752     {
 753       int m;
 754       printf ("orderd list: ");
 755       for (m = 0; m < i; ++m)
 756         printf ("%s, ", preferred[m]->name);
 757       printf ("\n");
 758     }
 759
 760   /* Create a link-list of opcode_node with disassemble preference from
 761      higher to lower.  */
 762   next = &head.next;
 763   --i;
 764   while (i >= 0)
 765     {
 766       const aarch64_opcode *alias = preferred [i];
 767       opcode_node *node = new_opcode_node ();
 768
 769       if (debug)
 770         printf ("add %s.\n", alias->name);
 771
 772       node->index = alias - aarch64_opcode_table;
 773       *next = node;
 774       next = &node->next;
 775
 776       --i;
 777     }
 778   *next = NULL;
 779
 780   return head.next;
 781 }
 782
 783 /* Create and return alias information.
 784    Return the address of the created alias info table; return the number
 785    of table entries in *NUM_PTR.  */
 786
 787 opcode_node *
 788 create_alias_info (int *num_ptr)
 789 {
 790   int i, num;
 791   opcode_node *ret;
 792   const aarch64_opcode *ent;
 793
 794   /* Calculate the total number of opcodes that have alias.  */
 795   num = 0;
 796   ent = aarch64_opcode_table;
 797   while (ent->name != NULL)
 798     {
 799       if (opcode_has_alias (ent))
 800         {
 801           /* Assert the alias relationship be flat-structured to keep
 802              algorithms simple; not allow F_ALIAS and F_HAS_ALIAS both
 803              specified.  */
 804           assert (!alias_opcode_p (ent));
 805           ++num;
 806         }
 807       ++ent;
 808     }
 809   assert (num_ptr);
 810   *num_ptr = num;
 811
 812   /* The array of real opcodes that have alias(es).  */
 813   ret = malloc (sizeof (opcode_node) * num);
 814
 815   /* For each opcode, establish a list of alias nodes in a preferred
 816      order.  */
 817   for (i = 0, ent = aarch64_opcode_table; i < num; ++i, ++ent)
 818     {
 819       opcode_node *node = ret + i;
 820       while (ent->name != NULL && !opcode_has_alias (ent))
 821         ++ent;
 822       assert (ent->name != NULL);
 823       node->index = ent - aarch64_opcode_table;
 824       node->next = find_alias_opcode (ent);
 825       assert (node->next);
 826     }
 827   assert (i == num);
 828
 829   return ret;
 830 }
 831
 832 /* Release the dynamic memory resource allocated for the generation of the
 833    alias information.  */
 834
 835 void
 836 release_resource_alias_info (opcode_node *alias_info, int num)
 837 {
 838   int i = 0;
 839   opcode_node *node = alias_info;
 840
 841   /* Free opcode_node list.  */
 842   for (; i < num; ++i, ++node)
 843     {
 844       opcode_node *list = node->next;
 845       do
 846         {
 847           opcode_node *next = list->next;
 848           free (list);
 849           list = next;
 850         } while (list != NULL);
 851     }
 852
 853   /* Free opcode_node array.  */
 854   free (alias_info);
 855 }
 856
 857 /* As a debugging utility, print out the result of the table division, although
 858    it is not doing much this moment.  */
 859 static void
 860 print_divide_result (const struct bittree *bittree ATTRIBUTE_UNUSED)
 861 {
 862   printf ("max_num_opcodes_at_leaf_node: %d\n", max_num_opcodes_at_leaf_node);
 863   return;
 864 }
 865 \f
 866 /* Structure to help generate the operand table.  */
 867 struct operand
 868 {
 869   const char *class;
 870   const char *inserter;
 871   const char *extractor;
 872   const char *str;
 873   const char *flags;
 874   const char *fields;
 875   const char *desc;
 876   unsigned processed : 1;
 877   unsigned has_inserter : 1;
 878   unsigned has_extractor : 1;
 879 };
 880
 881 typedef struct operand operand;
 882
 883 #ifdef X
 884 #undef X
 885 #endif
 886
 887 #ifdef Y
 888 #undef Y
 889 #endif
 890
 891 #ifdef F
 892 #undef F
 893 #endif
 894
 895 /* Get the operand information in strings.  */
 896
 897 static operand operands[] =
 898 {
 899     {"NIL", "0", "0", "", "0", "{0}", "<none>", 0, 0, 0},
 900 #define F(...)  #__VA_ARGS__
 901 #define X(a,b,c,d,e,f,g)        \
 902     {#a, #b, #c, d, #e, "{"f"}", g, 0, 0, 0},
 903 #define Y(a,b,d,e,f,g)          \
 904     {#a, "ins_"#b, "ext_"#b, d, #e, "{"f"}", g, 0, 0, 0},
 905     AARCH64_OPERANDS
 906     {"NIL", "0", "0", "", "0", "{0}", "DUMMY", 0, 0, 0},
 907 };
 908
 909 #undef F
 910 #undef X
 911
 912 static void
 913 process_operand_table (void)
 914 {
 915   int i;
 916   operand *opnd;
 917   const int num = sizeof (operands) / sizeof (operand);
 918
 919   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
 920     {
 921       opnd->has_inserter = opnd->inserter[0] != '0';
 922       opnd->has_extractor = opnd->extractor[0] != '0';
 923     }
 924 }
 925
 926 /* Generate aarch64_operands in C to the standard output.  */
 927
 928 static void
 929 print_operand_table (void)
 930 {
 931   int i;
 932   operand *opnd;
 933   const int num = sizeof (operands) / sizeof (operand);
 934
 935   if (debug)
 936     printf ("Enter print_operand_table\n");
 937
 938   printf ("\n");
 939   printf ("const struct aarch64_operand aarch64_operands[] =\n");
 940   printf ("{\n");
 941
 942   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
 943     {
 944       char flags[256];
 945       flags[0] = '\0';
 946       if (opnd->flags[0] != '0')
 947         sprintf (flags, "%s", opnd->flags);
 948       if (opnd->has_inserter)
 949         {
 950           if (flags[0] != '\0')
 951             strcat (flags, " | ");
 952           strcat (flags, "OPD_F_HAS_INSERTER");
 953         }
 954       if (opnd->has_extractor)
 955         {
 956           if (flags[0] != '\0')
 957             strcat (flags, " | ");
 958           strcat (flags, "OPD_F_HAS_EXTRACTOR");
 959         }
 960       if (flags[0] == '\0')
 961         {
 962           flags[0] = '0';
 963           flags[1] = '\0';
 964         }
 965     printf ("  {AARCH64_OPND_CLASS_%s, \"%s\", %s, %s, \"%s\"},\n",
 966             opnd->class, opnd->str, flags, opnd->fields, opnd->desc);
 967     }
 968   printf ("};\n");
 969 }
 970
 971 /* Generate aarch64_insert_operand in C to the standard output.  */
 972
 973 static void
 974 print_operand_inserter (void)
 975 {
 976   int i;
 977   operand *opnd;
 978   const int num = sizeof (operands) / sizeof (operand);
 979
 980   if (debug)
 981     printf ("Enter print_operand_inserter\n");
 982
 983   printf ("\n");
 984   printf ("const char*\n");
 985   printf ("aarch64_insert_operand (const aarch64_operand *self,\n\
 986                            const aarch64_opnd_info *info,\n\
 987                            aarch64_insn *code, const aarch64_inst *inst)\n");
 988   printf ("{\n");
 989   printf ("  /* Use the index as the key.  */\n");
 990   printf ("  int key = self - aarch64_operands;\n");
 991   printf ("  switch (key)\n");
 992   printf ("    {\n");
 993
 994   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
 995     opnd->processed = 0;
 996
 997   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
 998     {
 999       if (!opnd->processed && opnd->has_inserter)
1000         {
1001           int j = i + 1;
1002           const int len = strlen (opnd->inserter);
1003           operand *opnd2 = opnd + 1;
1004           printf ("    case %u:\n", (unsigned int)(opnd - operands));
1005           opnd->processed = 1;
1006           for (; j < num; ++j, ++opnd2)
1007             {
1008               if (!opnd2->processed
1009                   && opnd2->has_inserter
1010                   && len == strlen (opnd2->inserter)
1011                   && strncmp (opnd->inserter, opnd2->inserter, len) == 0)
1012                 {
1013                   printf ("    case %u:\n", (unsigned int)(opnd2 - operands));
1014                   opnd2->processed = 1;
1015                 }
1016             }
1017           printf ("      return aarch64_%s (self, info, code, inst);\n",
1018                   opnd->inserter);
1019         }
1020     }
1021
1022   printf ("    default: assert (0); abort ();\n");
1023   printf ("    }\n");
1024   printf ("}\n");
1025 }
1026
1027 /* Generate aarch64_extract_operand in C to the standard output.  */
1028
1029 static void
1030 print_operand_extractor (void)
1031 {
1032   int i;
1033   operand *opnd;
1034   const int num = sizeof (operands) / sizeof (operand);
1035
1036   if (debug)
1037     printf ("Enter print_operand_extractor\n");
1038
1039   printf ("\n");
1040   printf ("int\n");
1041   printf ("aarch64_extract_operand (const aarch64_operand *self,\n\
1042                            aarch64_opnd_info *info,\n\
1043                            aarch64_insn code, const aarch64_inst *inst)\n");
1044   printf ("{\n");
1045   printf ("  /* Use the index as the key.  */\n");
1046   printf ("  int key = self - aarch64_operands;\n");
1047   printf ("  switch (key)\n");
1048   printf ("    {\n");
1049
1050   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
1051     opnd->processed = 0;
1052
1053   for (i = 0, opnd = operands; i < num; ++i, ++opnd)
1054     {
1055       if (!opnd->processed && opnd->has_extractor)
1056         {
1057           int j = i + 1;
1058           const int len = strlen (opnd->extractor);
1059           operand *opnd2 = opnd + 1;
1060           printf ("    case %u:\n", (unsigned int)(opnd - operands));
1061           opnd->processed = 1;
1062           for (; j < num; ++j, ++opnd2)
1063             {
1064               if (!opnd2->processed
1065                   && opnd2->has_extractor
1066                   && len == strlen (opnd2->extractor)
1067                   && strncmp (opnd->extractor, opnd2->extractor, len) == 0)
1068                 {
1069                   printf ("    case %u:\n", (unsigned int)(opnd2 - operands));
1070                   opnd2->processed = 1;
1071                 }
1072             }
1073           printf ("      return aarch64_%s (self, info, code, inst);\n",
1074                   opnd->extractor);
1075         }
1076     }
1077
1078   printf ("    default: assert (0); abort ();\n");
1079   printf ("    }\n");
1080   printf ("}\n");
1081 }
1082 \f
1083 /* Table indexed by opcode enumerator stores the index of the corresponding
1084    opcode entry in aarch64_opcode_table.  */
1085 static unsigned op_enum_table [OP_TOTAL_NUM];
1086
1087 /* Print out the routine which, given the opcode enumerator, returns the
1088    corresponding opcode entry pointer.  */
1089
1090 static void
1091 print_get_opcode (void)
1092 {
1093   int i;
1094   const int num = OP_TOTAL_NUM;
1095   const aarch64_opcode *opcode;
1096
1097   if (debug)
1098     printf ("Enter print_get_opcode\n");
1099
1100   /* Fill in the internal table.  */
1101   opcode = aarch64_opcode_table;
1102   while (opcode->name != NULL)
1103     {
1104       if (opcode->op != OP_NIL)
1105         {
1106           /* Assert opcode enumerator be unique, in other words, no shared by
1107              different opcodes.  */
1108           if (op_enum_table[opcode->op] != 0)
1109             {
1110               fprintf (stderr, "Opcode %u is shared by different %s and %s.\n",
1111                        opcode->op,
1112                        aarch64_opcode_table[op_enum_table[opcode->op]].name,
1113                        opcode->name);
1114               assert (0);
1115               abort ();
1116             }
1117           assert (opcode->op < OP_TOTAL_NUM);
1118           op_enum_table[opcode->op] = opcode - aarch64_opcode_table;
1119         }
1120       ++opcode;
1121     }
1122
1123   /* Print the table.  */
1124   printf ("\n");
1125   printf ("/* Indexed by an enum aarch64_op enumerator, the value is the offset of\n\
1126    the corresponding aarch64_opcode entry in the aarch64_opcode_table.  */\n\n");
1127   printf ("static const unsigned op_enum_table [] =\n");
1128   printf ("{\n");
1129   for (i = 0; i < num; ++i)
1130     printf ("  %u,\n", op_enum_table[i]);
1131   printf ("};\n");
1132
1133   /* Print the function.  */
1134   printf ("\n");
1135   printf ("/* Given the opcode enumerator OP, return the pointer to the corresponding\n");
1136   printf ("   opcode entry.  */\n");
1137   printf ("\n");
1138   printf ("const aarch64_opcode *\n");
1139   printf ("aarch64_get_opcode (enum aarch64_op op)\n");
1140   printf ("{\n");
1141   printf ("  return aarch64_opcode_table + op_enum_table[op];\n");
1142   printf ("}\n");
1143 }
1144
1145 /* Print out the content of an opcode table (not in use).  */
1146 static void ATTRIBUTE_UNUSED
1147 print_table (struct aarch64_opcode* table)
1148 {
1149   struct aarch64_opcode *ent = table;
1150   do
1151     {
1152       printf ("%s\t%08x\t%08x\n", ent->name, (unsigned int)ent->opcode,
1153               (unsigned int)ent->mask);
1154     } while ((++ent)->name);
1155 }
1156 \f
1157 static const char * program_name = NULL;
1158
1159 /* Program options.  */
1160 struct option long_options[] =
1161 {
1162   {"debug",   no_argument,       NULL, 'd'},
1163   {"version", no_argument,       NULL, 'V'},
1164   {"help",    no_argument,       NULL, 'h'},
1165   {"gen-opc", no_argument,       NULL, 'c'},
1166   {"gen-asm", no_argument,       NULL, 'a'},
1167   {"gen-dis", no_argument,       NULL, 's'},
1168   {0,         no_argument,       NULL, 0}
1169 };
1170
1171 static void
1172 print_version (void)
1173 {
1174   printf ("%s: version 1.0\n", program_name);
1175   xexit (0);
1176 }
1177
1178 static void
1179 usage (FILE * stream, int status)
1180 {
1181   fprintf (stream, "Usage: %s [-V | --version] [-d | --debug] [--help]\n",
1182            program_name);
1183   fprintf (stream, "\t[ [-c | --gen-opc] | [-a | --gen-asm] | [-s | --gen-dis] ]\n");
1184   xexit (status);
1185 }
1186
1187 int
1188 main (int argc, char **argv)
1189 {
1190   extern int chdir (char *);
1191   int c;
1192   int gen_opcode_p = 0;
1193   int gen_assembler_p = 0;
1194   int gen_disassembler_p = 0;
1195
1196   program_name = *argv;
1197   xmalloc_set_program_name (program_name);
1198
1199   while ((c = getopt_long (argc, argv, "vVdhacs", long_options, 0)) != EOF)
1200     switch (c)
1201       {
1202       case 'V':
1203       case 'v':
1204         print_version ();
1205         break;
1206       case 'd':
1207         debug = 1;
1208         break;
1209       case 'h':
1210       case '?':
1211         usage (stderr, 0);
1212         break;
1213       case 'c':
1214         gen_opcode_p = 1;
1215         break;
1216       case 'a':
1217         gen_assembler_p = 1;
1218         break;
1219       case 's':
1220         gen_disassembler_p = 1;
1221         break;
1222       default:
1223       case 0:
1224         break;
1225       }
1226
1227   if (argc == 1 || optind != argc)
1228     usage (stdout, 1);
1229
1230   if (gen_opcode_p + gen_assembler_p + gen_disassembler_p > 1)
1231     {
1232       printf ("Please specify only one of the following options\n\
1233               [-c | --gen-opc] [-a | --gen-asm] [-s | --gen-dis]\n");
1234       xexit (2);
1235     }
1236
1237   struct bittree *decoder_tree;
1238
1239   decoder_tree = initialize_decoder_tree ();
1240   if (debug)
1241     print_divide_result (decoder_tree);
1242
1243   printf ("/* This file is automatically generated by aarch64-gen.  Do not edit!  */\n");
1244   printf ("/* Copyright (C) 2012-2017 Free Software Foundation, Inc.\n\
1245    Contributed by ARM Ltd.\n\
1246 \n\
1247    This file is part of the GNU opcodes library.\n\
1248 \n\
1249    This library is free software; you can redistribute it and/or modify\n\
1250    it under the terms of the GNU General Public License as published by\n\
1251    the Free Software Foundation; either version 3, or (at your option)\n\
1252    any later version.\n\
1253 \n\
1254    It is distributed in the hope that it will be useful, but WITHOUT\n\
1255    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY\n\
1256    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public\n\
1257    License for more details.\n\
1258 \n\
1259    You should have received a copy of the GNU General Public License\n\
1260    along with this program; see the file COPYING3. If not,\n\
1261    see <http://www.gnu.org/licenses/>.  */\n");
1262
1263   printf ("\n");
1264   printf ("#include \"sysdep.h\"\n");
1265   if (gen_opcode_p)
1266     printf ("#include \"aarch64-opc.h\"\n");
1267   if (gen_assembler_p)
1268     printf ("#include \"aarch64-asm.h\"\n");
1269   if (gen_disassembler_p)
1270     printf ("#include \"aarch64-dis.h\"\n");
1271   printf ("\n");
1272
1273   /* Generate opcode entry lookup for the disassembler.  */
1274   if (gen_disassembler_p)
1275     {
1276       print_decision_tree (decoder_tree);
1277       print_find_next_opcode (decoder_tree);
1278       release_resource_decoder_tree (decoder_tree);
1279     }
1280
1281   /* Generate alias opcode handling for the assembler or the disassembler.  */
1282   if (gen_assembler_p || gen_disassembler_p)
1283     {
1284       int num;
1285       opcode_node *alias_info = create_alias_info (&num);
1286
1287       if (gen_assembler_p)
1288         print_find_real_opcode (alias_info, num);
1289
1290       if (gen_disassembler_p)
1291         {
1292           print_find_alias_opcode (alias_info, num);
1293           print_find_next_alias_opcode (alias_info, num);
1294         }
1295
1296       release_resource_alias_info (alias_info, num);
1297     }
1298
1299   /* Generate operand table.  */
1300   process_operand_table ();
1301
1302   if (gen_assembler_p)
1303     print_operand_inserter ();
1304
1305   if (gen_disassembler_p)
1306     print_operand_extractor ();
1307
1308   if (gen_opcode_p)
1309     print_operand_table ();
1310
1311   /* Generate utility to return aarch64_opcode entry given an enumerator.  */
1312   if (gen_opcode_p)
1313     print_get_opcode ();
1314
1315   exit (0);
1316 }