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