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