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-2018 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 ("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-2018 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 }