gas/ginsn.c

   1 /* ginsn.h - GAS instruction representation.
   2    Copyright (C) 2023 Free Software Foundation, Inc.
   3
   4    This file is part of GAS, the GNU Assembler.
   5
   6    GAS is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3, or (at your option)
   9    any later version.
  10
  11    GAS is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with GAS; see the file COPYING.  If not, write to the Free
  18    Software Foundation, 51 Franklin Street - Fifth Floor, Boston, MA
  19    02110-1301, USA.  */
  20
  21 #include "as.h"
  22 #include "subsegs.h"
  23 #include "ginsn.h"
  24 #include "scfi.h"
  25
  26 #ifdef TARGET_USE_GINSN
  27
  28 static const char *const ginsn_type_names[] =
  29 {
  30 #define _GINSN_TYPE_ITEM(NAME, STR) STR,
  31   _GINSN_TYPES
  32 #undef _GINSN_TYPE_ITEM
  33 };
  34
  35 static ginsnS *
  36 ginsn_alloc (void)
  37 {
  38   ginsnS *ginsn = XCNEW (ginsnS);
  39   return ginsn;
  40 }
  41
  42 static ginsnS *
  43 ginsn_init (enum ginsn_type type, const symbolS *sym, bool real_p)
  44 {
  45   ginsnS *ginsn = ginsn_alloc ();
  46   ginsn->type = type;
  47   ginsn->sym = sym;
  48   if (real_p)
  49     ginsn->flags |= GINSN_F_INSN_REAL;
  50   return ginsn;
  51 }
  52
  53 static void
  54 ginsn_cleanup (ginsnS **ginsnp)
  55 {
  56   ginsnS *ginsn;
  57
  58   if (!ginsnp || !*ginsnp)
  59     return;
  60
  61   ginsn = *ginsnp;
  62   if (ginsn->scfi_ops)
  63     {
  64       scfi_ops_cleanup (ginsn->scfi_ops);
  65       ginsn->scfi_ops = NULL;
  66     }
  67
  68   free (ginsn);
  69   *ginsnp = NULL;
  70 }
  71
  72 static void
  73 ginsn_set_src (struct ginsn_src *src, enum ginsn_src_type type, unsigned int reg,
  74                offsetT immdisp)
  75 {
  76   if (!src)
  77     return;
  78
  79   src->type = type;
  80   /* Even when the use-case is SCFI, the value of reg may be > SCFI_MAX_REG_ID.
  81      E.g., in AMD64, push fs etc.  */
  82   src->reg = reg;
  83   src->immdisp = immdisp;
  84 }
  85
  86 static void
  87 ginsn_set_dst (struct ginsn_dst *dst, enum ginsn_dst_type type, unsigned int reg,
  88                offsetT disp)
  89 {
  90   if (!dst)
  91     return;
  92
  93   dst->type = type;
  94   dst->reg = reg;
  95
  96   if (type == GINSN_DST_INDIRECT)
  97     dst->disp = disp;
  98 }
  99
 100 static void
 101 ginsn_set_file_line (ginsnS *ginsn, const char *file, unsigned int line)
 102 {
 103   if (!ginsn)
 104     return;
 105
 106   ginsn->file = file;
 107   ginsn->line = line;
 108 }
 109
 110 struct ginsn_src *
 111 ginsn_get_src1 (ginsnS *ginsn)
 112 {
 113   return &ginsn->src[0];
 114 }
 115
 116 struct ginsn_src *
 117 ginsn_get_src2 (ginsnS *ginsn)
 118 {
 119   return &ginsn->src[1];
 120 }
 121
 122 struct ginsn_dst *
 123 ginsn_get_dst (ginsnS *ginsn)
 124 {
 125   return &ginsn->dst;
 126 }
 127
 128 unsigned int
 129 ginsn_get_src_reg (struct ginsn_src *src)
 130 {
 131   return src->reg;
 132 }
 133
 134 enum ginsn_src_type
 135 ginsn_get_src_type (struct ginsn_src *src)
 136 {
 137   return src->type;
 138 }
 139
 140 offsetT
 141 ginsn_get_src_disp (struct ginsn_src *src)
 142 {
 143   return src->immdisp;
 144 }
 145
 146 offsetT
 147 ginsn_get_src_imm (struct ginsn_src *src)
 148 {
 149   return src->immdisp;
 150 }
 151
 152 unsigned int
 153 ginsn_get_dst_reg (struct ginsn_dst *dst)
 154 {
 155   return dst->reg;
 156 }
 157
 158 enum ginsn_dst_type
 159 ginsn_get_dst_type (struct ginsn_dst *dst)
 160 {
 161   return dst->type;
 162 }
 163
 164 offsetT
 165 ginsn_get_dst_disp (struct ginsn_dst *dst)
 166 {
 167   return dst->disp;
 168 }
 169
 170 void
 171 label_ginsn_map_insert (const symbolS *label, ginsnS *ginsn)
 172 {
 173   const char *name = S_GET_NAME (label);
 174   str_hash_insert (frchain_now->frch_ginsn_data->label_ginsn_map,
 175                    name, ginsn, 0 /* noreplace.  */);
 176 }
 177
 178 ginsnS *
 179 label_ginsn_map_find (const symbolS *label)
 180 {
 181   const char *name = S_GET_NAME (label);
 182   ginsnS *ginsn
 183     = (ginsnS *) str_hash_find (frchain_now->frch_ginsn_data->label_ginsn_map,
 184                                 name);
 185   return ginsn;
 186 }
 187
 188 ginsnS *
 189 ginsn_new_phantom (const symbolS *sym)
 190 {
 191   ginsnS *ginsn = ginsn_alloc ();
 192   ginsn->type = GINSN_TYPE_PHANTOM;
 193   ginsn->sym = sym;
 194   /* By default, GINSN_F_INSN_REAL is not set in ginsn->flags.  */
 195   return ginsn;
 196 }
 197
 198 ginsnS *
 199 ginsn_new_symbol (const symbolS *sym, bool func_begin_p)
 200 {
 201   ginsnS *ginsn = ginsn_alloc ();
 202   ginsn->type = GINSN_TYPE_SYMBOL;
 203   ginsn->sym = sym;
 204   if (func_begin_p)
 205     ginsn->flags |= GINSN_F_FUNC_MARKER;
 206   return ginsn;
 207 }
 208
 209 ginsnS *
 210 ginsn_new_symbol_func_begin (const symbolS *sym)
 211 {
 212   return ginsn_new_symbol (sym, true);
 213 }
 214
 215 ginsnS *
 216 ginsn_new_symbol_func_end (const symbolS *sym)
 217 {
 218   return ginsn_new_symbol (sym, false);
 219 }
 220
 221 ginsnS *
 222 ginsn_new_symbol_user_label (const symbolS *sym)
 223 {
 224   ginsnS *ginsn = ginsn_new_symbol (sym, false);
 225   ginsn->flags |= GINSN_F_USER_LABEL;
 226   return ginsn;
 227 }
 228
 229 ginsnS *
 230 ginsn_new_add (const symbolS *sym, bool real_p,
 231                enum ginsn_src_type src1_type, unsigned int src1_reg, offsetT src1_disp,
 232                enum ginsn_src_type src2_type, unsigned int src2_reg, offsetT src2_disp,
 233                enum ginsn_dst_type dst_type, unsigned int dst_reg, offsetT dst_disp)
 234 {
 235   ginsnS *ginsn = ginsn_init (GINSN_TYPE_ADD, sym, real_p);
 236   /* src info.  */
 237   ginsn_set_src (&ginsn->src[0], src1_type, src1_reg, src1_disp);
 238   ginsn_set_src (&ginsn->src[1], src2_type, src2_reg, src2_disp);
 239   /* dst info.  */
 240   ginsn_set_dst (&ginsn->dst, dst_type, dst_reg, dst_disp);
 241
 242   return ginsn;
 243 }
 244
 245 ginsnS *
 246 ginsn_new_and (const symbolS *sym, bool real_p,
 247                enum ginsn_src_type src1_type, unsigned int src1_reg, offsetT src1_disp,
 248                enum ginsn_src_type src2_type, unsigned int src2_reg, offsetT src2_disp,
 249                enum ginsn_dst_type dst_type, unsigned int dst_reg, offsetT dst_disp)
 250 {
 251   ginsnS *ginsn = ginsn_init (GINSN_TYPE_AND, sym, real_p);
 252   /* src info.  */
 253   ginsn_set_src (&ginsn->src[0], src1_type, src1_reg, src1_disp);
 254   ginsn_set_src (&ginsn->src[1], src2_type, src2_reg, src2_disp);
 255   /* dst info.  */
 256   ginsn_set_dst (&ginsn->dst, dst_type, dst_reg, dst_disp);
 257
 258   return ginsn;
 259 }
 260
 261 ginsnS *
 262 ginsn_new_call (const symbolS *sym, bool real_p,
 263                 enum ginsn_src_type src_type, unsigned int src_reg,
 264                 const symbolS *src_text_sym)
 265
 266 {
 267   ginsnS *ginsn = ginsn_init (GINSN_TYPE_CALL, sym, real_p);
 268   /* src info.  */
 269   ginsn_set_src (&ginsn->src[0], src_type, src_reg, 0);
 270
 271   if (src_type == GINSN_SRC_SYMBOL)
 272     ginsn->src[0].sym = src_text_sym;
 273
 274   return ginsn;
 275 }
 276
 277 ginsnS *
 278 ginsn_new_jump (const symbolS *sym, bool real_p,
 279                 enum ginsn_src_type src_type, unsigned int src_reg,
 280                 const symbolS *src_ginsn_sym)
 281 {
 282   ginsnS *ginsn = ginsn_init (GINSN_TYPE_JUMP, sym, real_p);
 283   /* src info.  */
 284   ginsn_set_src (&ginsn->src[0], src_type, src_reg, 0);
 285
 286   if (src_type == GINSN_SRC_SYMBOL)
 287     ginsn->src[0].sym = src_ginsn_sym;
 288
 289   return ginsn;
 290 }
 291
 292 ginsnS *
 293 ginsn_new_jump_cond (const symbolS *sym, bool real_p,
 294                      enum ginsn_src_type src_type, unsigned int src_reg,
 295                      const symbolS *src_ginsn_sym)
 296 {
 297   ginsnS *ginsn = ginsn_init (GINSN_TYPE_JUMP_COND, sym, real_p);
 298   /* src info.  */
 299   ginsn_set_src (&ginsn->src[0], src_type, src_reg, 0);
 300
 301   if (src_type == GINSN_SRC_SYMBOL)
 302     ginsn->src[0].sym = src_ginsn_sym;
 303
 304   return ginsn;
 305 }
 306
 307 ginsnS *
 308 ginsn_new_mov (const symbolS *sym, bool real_p,
 309                enum ginsn_src_type src_type, unsigned int src_reg, offsetT src_disp,
 310                enum ginsn_dst_type dst_type, unsigned int dst_reg, offsetT dst_disp)
 311 {
 312   ginsnS *ginsn = ginsn_init (GINSN_TYPE_MOV, sym, real_p);
 313   /* src info.  */
 314   ginsn_set_src (&ginsn->src[0], src_type, src_reg, src_disp);
 315   /* dst info.  */
 316   ginsn_set_dst (&ginsn->dst, dst_type, dst_reg, dst_disp);
 317
 318   return ginsn;
 319 }
 320
 321 ginsnS *
 322 ginsn_new_store (const symbolS *sym, bool real_p,
 323                  enum ginsn_src_type src_type, unsigned int src_reg,
 324                  enum ginsn_dst_type dst_type, unsigned int dst_reg, offsetT dst_disp)
 325 {
 326   ginsnS *ginsn = ginsn_init (GINSN_TYPE_STORE, sym, real_p);
 327   /* src info.  */
 328   ginsn_set_src (&ginsn->src[0], src_type, src_reg, 0);
 329   /* dst info.  */
 330   gas_assert (dst_type == GINSN_DST_INDIRECT);
 331   ginsn_set_dst (&ginsn->dst, dst_type, dst_reg, dst_disp);
 332
 333   return ginsn;
 334 }
 335
 336 ginsnS *
 337 ginsn_new_load (const symbolS *sym, bool real_p,
 338                 enum ginsn_src_type src_type, unsigned int src_reg, offsetT src_disp,
 339                 enum ginsn_dst_type dst_type, unsigned int dst_reg)
 340 {
 341   ginsnS *ginsn = ginsn_init (GINSN_TYPE_LOAD, sym, real_p);
 342   /* src info.  */
 343   gas_assert (src_type == GINSN_SRC_INDIRECT);
 344   ginsn_set_src (&ginsn->src[0], src_type, src_reg, src_disp);
 345   /* dst info.  */
 346   ginsn_set_dst (&ginsn->dst, dst_type, dst_reg, 0);
 347
 348   return ginsn;
 349 }
 350
 351 ginsnS *
 352 ginsn_new_sub (const symbolS *sym, bool real_p,
 353                enum ginsn_src_type src1_type, unsigned int src1_reg, offsetT src1_disp,
 354                enum ginsn_src_type src2_type, unsigned int src2_reg, offsetT src2_disp,
 355                enum ginsn_dst_type dst_type, unsigned int dst_reg, offsetT dst_disp)
 356 {
 357   ginsnS *ginsn = ginsn_init (GINSN_TYPE_SUB, sym, real_p);
 358   /* src info.  */
 359   ginsn_set_src (&ginsn->src[0], src1_type, src1_reg, src1_disp);
 360   ginsn_set_src (&ginsn->src[1], src2_type, src2_reg, src2_disp);
 361   /* dst info.  */
 362   ginsn_set_dst (&ginsn->dst, dst_type, dst_reg, dst_disp);
 363
 364   return ginsn;
 365 }
 366
 367 /* PS: Note this API does not identify the displacement values of
 368    src1/src2/dst.  At this time, it is unnecessary for correctness to support
 369    the additional argument.  */
 370
 371 ginsnS *
 372 ginsn_new_other (const symbolS *sym, bool real_p,
 373                  enum ginsn_src_type src1_type, unsigned int src1_val,
 374                  enum ginsn_src_type src2_type, unsigned int src2_val,
 375                  enum ginsn_dst_type dst_type, unsigned int dst_reg)
 376 {
 377   ginsnS *ginsn = ginsn_init (GINSN_TYPE_OTHER, sym, real_p);
 378   /* src info.  */
 379   ginsn_set_src (&ginsn->src[0], src1_type, src1_val, src1_val);
 380   /* GINSN_SRC_INDIRECT src2_type is not expected.  */
 381   gas_assert (src2_type != GINSN_SRC_INDIRECT);
 382   ginsn_set_src (&ginsn->src[1], src2_type, src2_val, src2_val);
 383   /* dst info.  */
 384   ginsn_set_dst (&ginsn->dst, dst_type, dst_reg, 0);
 385
 386   return ginsn;
 387 }
 388
 389 ginsnS *
 390 ginsn_new_return (const symbolS *sym, bool real_p)
 391 {
 392   ginsnS *ginsn = ginsn_init (GINSN_TYPE_RETURN, sym, real_p);
 393   return ginsn;
 394 }
 395
 396 void
 397 ginsn_set_where (ginsnS *ginsn)
 398 {
 399   const char *file;
 400   unsigned int line;
 401   file = as_where (&line);
 402   ginsn_set_file_line (ginsn, file, line);
 403 }
 404
 405 int
 406 ginsn_link_next (ginsnS *ginsn, ginsnS *next)
 407 {
 408   int ret = 0;
 409
 410   /* Avoid data corruption by limiting the scope of the API.  */
 411   if (!ginsn || ginsn->next)
 412     return 1;
 413
 414   ginsn->next = next;
 415
 416   return ret;
 417 }
 418
 419 bool
 420 ginsn_track_reg_p (unsigned int dw2reg, enum ginsn_gen_mode gmode)
 421 {
 422   bool track_p = false;
 423
 424   if (gmode == GINSN_GEN_SCFI && dw2reg <= SCFI_MAX_REG_ID)
 425     {
 426       /* FIXME - rename this to tc_ ? */
 427       track_p |= SCFI_CALLEE_SAVED_REG_P (dw2reg);
 428       track_p |= (dw2reg == REG_FP);
 429       track_p |= (dw2reg == REG_SP);
 430     }
 431
 432   return track_p;
 433 }
 434
 435 static bool
 436 ginsn_indirect_jump_p (ginsnS *ginsn)
 437 {
 438   bool ret_p = false;
 439   if (!ginsn)
 440     return ret_p;
 441
 442   ret_p = (ginsn->type == GINSN_TYPE_JUMP
 443            && ginsn->src[0].type == GINSN_SRC_REG);
 444   return ret_p;
 445 }
 446
 447 static bool
 448 ginsn_direct_local_jump_p (ginsnS *ginsn)
 449 {
 450   bool ret_p = false;
 451   if (!ginsn)
 452     return ret_p;
 453
 454   ret_p |= (ginsn->type == GINSN_TYPE_JUMP
 455             && ginsn->src[0].type == GINSN_SRC_SYMBOL);
 456   return ret_p;
 457 }
 458
 459 static char *
 460 ginsn_src_print (struct ginsn_src *src)
 461 {
 462   size_t len = 40;
 463   char *src_str = XNEWVEC (char, len);
 464
 465   memset (src_str, 0, len);
 466
 467   switch (src->type)
 468     {
 469     case GINSN_SRC_REG:
 470       snprintf (src_str, len, "%%r%d, ", ginsn_get_src_reg (src));
 471       break;
 472     case GINSN_SRC_IMM:
 473       snprintf (src_str, len, "%lld, ",
 474                 (long long int) ginsn_get_src_imm (src));
 475       break;
 476     case GINSN_SRC_INDIRECT:
 477       snprintf (src_str, len, "[%%r%d+%lld], ", ginsn_get_src_reg (src),
 478                 (long long int) ginsn_get_src_disp (src));
 479       break;
 480     default:
 481       break;
 482     }
 483
 484   return src_str;
 485 }
 486
 487 static char*
 488 ginsn_dst_print (struct ginsn_dst *dst)
 489 {
 490   size_t len = GINSN_LISTING_OPND_LEN;
 491   char *dst_str = XNEWVEC (char, len);
 492
 493   memset (dst_str, 0, len);
 494
 495   if (dst->type == GINSN_DST_REG)
 496     {
 497       char *buf = XNEWVEC (char, 32);
 498       sprintf (buf, "%%r%d", ginsn_get_dst_reg (dst));
 499       strcat (dst_str, buf);
 500     }
 501   else if (dst->type == GINSN_DST_INDIRECT)
 502     {
 503       char *buf = XNEWVEC (char, 32);
 504       sprintf (buf, "[%%r%d+%lld]", ginsn_get_dst_reg (dst),
 505                  (long long int) ginsn_get_dst_disp (dst));
 506       strcat (dst_str, buf);
 507     }
 508
 509   gas_assert (strlen (dst_str) < GINSN_LISTING_OPND_LEN);
 510
 511   return dst_str;
 512 }
 513
 514 static const char*
 515 ginsn_type_func_marker_print (ginsnS *ginsn)
 516 {
 517   int id = 0;
 518   static const char * const ginsn_sym_strs[] =
 519     { "", "FUNC_BEGIN", "FUNC_END" };
 520
 521   if (GINSN_F_FUNC_BEGIN_P (ginsn))
 522     id = 1;
 523   else if (GINSN_F_FUNC_END_P (ginsn))
 524     id = 2;
 525
 526   return ginsn_sym_strs[id];
 527 }
 528
 529 static char*
 530 ginsn_print (ginsnS *ginsn)
 531 {
 532   struct ginsn_src *src;
 533   struct ginsn_dst *dst;
 534   int str_size = 0;
 535   size_t len = GINSN_LISTING_LEN;
 536   char *ginsn_str = XNEWVEC (char, len);
 537
 538   memset (ginsn_str, 0, len);
 539
 540   str_size = snprintf (ginsn_str, GINSN_LISTING_LEN, "ginsn: %s",
 541                        ginsn_type_names[ginsn->type]);
 542   gas_assert (str_size >= 0 && str_size < GINSN_LISTING_LEN);
 543
 544   /* For some ginsn types, no further information is printed for now.  */
 545   if (ginsn->type == GINSN_TYPE_CALL
 546       || ginsn->type == GINSN_TYPE_RETURN)
 547     goto end;
 548   else if (ginsn->type == GINSN_TYPE_SYMBOL)
 549     {
 550       if (GINSN_F_USER_LABEL_P (ginsn))
 551         str_size += snprintf (ginsn_str + str_size,
 552                               GINSN_LISTING_LEN - str_size,
 553                               " %s", S_GET_NAME (ginsn->sym));
 554       else
 555         str_size += snprintf (ginsn_str + str_size,
 556                               GINSN_LISTING_LEN - str_size,
 557                               " %s", ginsn_type_func_marker_print (ginsn));
 558       goto end;
 559     }
 560
 561   /* src 1.  */
 562   src = ginsn_get_src1 (ginsn);
 563   str_size += snprintf (ginsn_str + str_size, GINSN_LISTING_LEN - str_size,
 564                         " %s", ginsn_src_print (src));
 565   gas_assert (str_size >= 0 && str_size < GINSN_LISTING_LEN);
 566
 567   /* src 2.  */
 568   src = ginsn_get_src2 (ginsn);
 569   str_size += snprintf (ginsn_str + str_size, GINSN_LISTING_LEN - str_size,
 570                         "%s", ginsn_src_print (src));
 571   gas_assert (str_size >= 0 && str_size < GINSN_LISTING_LEN);
 572
 573   /* dst.  */
 574   dst = ginsn_get_dst (ginsn);
 575   str_size += snprintf (ginsn_str + str_size, GINSN_LISTING_LEN - str_size,
 576                         "%s", ginsn_dst_print (dst));
 577
 578 end:
 579   gas_assert (str_size >= 0 && str_size < GINSN_LISTING_LEN);
 580   return ginsn_str;
 581 }
 582
 583 static void
 584 gbb_cleanup (gbbS **bbp)
 585 {
 586   gbbS *bb = NULL;
 587
 588   if (!bbp && !*bbp)
 589     return;
 590
 591   bb = *bbp;
 592
 593   if (bb->entry_state)
 594     {
 595       free (bb->entry_state);
 596       bb->entry_state = NULL;
 597     }
 598   if (bb->exit_state)
 599     {
 600       free (bb->exit_state);
 601       bb->exit_state = NULL;
 602     }
 603   free (bb);
 604   *bbp = NULL;
 605 }
 606
 607 static void
 608 bb_add_edge (gbbS* from_bb, gbbS *to_bb)
 609 {
 610   gedgeS *tmpedge = NULL;
 611   gedgeS *gedge;
 612   bool exists = false;
 613
 614   if (!from_bb || !to_bb)
 615     return;
 616
 617   /* Create a new edge object.  */
 618   gedge = XCNEW (gedgeS);
 619   gedge->dst_bb = to_bb;
 620   gedge->next = NULL;
 621   gedge->visited = false;
 622
 623   /* Add it in.  */
 624   if (from_bb->out_gedges == NULL)
 625     {
 626       from_bb->out_gedges = gedge;
 627       from_bb->num_out_gedges++;
 628     }
 629   else
 630     {
 631       /* Get the tail of the list.  */
 632       tmpedge = from_bb->out_gedges;
 633       while (tmpedge)
 634         {
 635           /* Do not add duplicate edges.  Duplicated edges will cause unwanted
 636              failures in the forward and backward passes for SCFI.  */
 637           if (tmpedge->dst_bb == to_bb)
 638             {
 639               exists = true;
 640               break;
 641             }
 642           if (tmpedge->next)
 643             tmpedge = tmpedge->next;
 644           else
 645             break;
 646         }
 647
 648       if (!exists)
 649         {
 650           tmpedge->next = gedge;
 651           from_bb->num_out_gedges++;
 652         }
 653       else
 654         free (gedge);
 655     }
 656 }
 657
 658 static void
 659 cfg_add_bb (gcfgS *gcfg, gbbS *gbb)
 660 {
 661   gbbS *last_bb = NULL;
 662
 663   if (!gcfg->root_bb)
 664     gcfg->root_bb = gbb;
 665   else
 666     {
 667       last_bb = gcfg->root_bb;
 668       while (last_bb->next)
 669         last_bb = last_bb->next;
 670
 671       last_bb->next = gbb;
 672     }
 673   gcfg->num_gbbs++;
 674
 675   gbb->id = gcfg->num_gbbs;
 676 }
 677
 678 static gbbS *
 679 add_bb_at_ginsn (const symbolS *func, gcfgS *gcfg, ginsnS *ginsn, gbbS *prev_bb,
 680                  int *errp);
 681
 682 static gbbS *
 683 find_bb (gcfgS *gcfg, ginsnS *ginsn)
 684 {
 685   gbbS *found_bb = NULL;
 686   gbbS *gbb = NULL;
 687
 688   if (!ginsn)
 689     return found_bb;
 690
 691   if (ginsn->visited)
 692     {
 693       cfg_for_each_bb (gcfg, gbb)
 694         {
 695           if (gbb->first_ginsn == ginsn)
 696             {
 697               found_bb = gbb;
 698               break;
 699             }
 700         }
 701       /* Must be found if ginsn is visited.  */
 702       gas_assert (found_bb);
 703     }
 704
 705   return found_bb;
 706 }
 707
 708 static gbbS *
 709 find_or_make_bb (const symbolS *func, gcfgS *gcfg, ginsnS *ginsn, gbbS *prev_bb,
 710                  int *errp)
 711 {
 712   gbbS *found_bb = NULL;
 713
 714   found_bb = find_bb (gcfg, ginsn);
 715   if (found_bb)
 716     return found_bb;
 717
 718   return add_bb_at_ginsn (func, gcfg, ginsn, prev_bb, errp);
 719 }
 720
 721 /* Add the basic block starting at GINSN to the given GCFG.
 722    Also adds an edge from the PREV_BB to the newly added basic block.
 723
 724    This is a recursive function which returns the root of the added
 725    basic blocks.  */
 726
 727 static gbbS *
 728 add_bb_at_ginsn (const symbolS *func, gcfgS *gcfg, ginsnS *ginsn, gbbS *prev_bb,
 729                  int *errp)
 730 {
 731   gbbS *current_bb = NULL;
 732   ginsnS *target_ginsn = NULL;
 733   const symbolS *taken_label;
 734
 735   while (ginsn)
 736     {
 737       /* Skip these as they may be right after a GINSN_TYPE_RETURN.
 738          For GINSN_TYPE_RETURN, we have already considered that as
 739          end of bb, and a logical exit from function.  */
 740       if (GINSN_F_FUNC_END_P (ginsn))
 741         {
 742           ginsn = ginsn->next;
 743           continue;
 744         }
 745
 746       if (ginsn->visited)
 747         {
 748           /* If the ginsn has been visited earlier, the bb must exist by now
 749              in the cfg.  */
 750           prev_bb = current_bb;
 751           current_bb = find_bb (gcfg, ginsn);
 752           gas_assert (current_bb);
 753           /* Add edge from the prev_bb.  */
 754           if (prev_bb)
 755             bb_add_edge (prev_bb, current_bb);
 756           break;
 757         }
 758       else if (current_bb && GINSN_F_USER_LABEL_P (ginsn))
 759         {
 760           /* Create new bb starting at this label ginsn.  */
 761           prev_bb = current_bb;
 762           find_or_make_bb (func, gcfg, ginsn, prev_bb, errp);
 763           break;
 764         }
 765
 766       if (current_bb == NULL)
 767         {
 768           /* Create a new bb.  */
 769           current_bb = XCNEW (gbbS);
 770           cfg_add_bb (gcfg, current_bb);
 771           /* Add edge for the Not Taken, or Fall-through path.  */
 772           if (prev_bb)
 773             bb_add_edge (prev_bb, current_bb);
 774         }
 775
 776       if (current_bb->first_ginsn == NULL)
 777         current_bb->first_ginsn = ginsn;
 778
 779       ginsn->visited = true;
 780       current_bb->num_ginsns++;
 781       current_bb->last_ginsn = ginsn;
 782
 783       /* Note that BB is _not_ split on ginsn of type GINSN_TYPE_CALL.  */
 784       if (ginsn->type == GINSN_TYPE_JUMP
 785           || ginsn->type == GINSN_TYPE_JUMP_COND
 786           || ginsn->type == GINSN_TYPE_RETURN)
 787         {
 788           /* Indirect Jumps or direct jumps to symbols non-local to the
 789              function must not be seen here.  The caller must have already
 790              checked for that.  */
 791           gas_assert (!ginsn_indirect_jump_p (ginsn));
 792           if (ginsn->type == GINSN_TYPE_JUMP)
 793             gas_assert (ginsn_direct_local_jump_p (ginsn));
 794
 795           /* Direct Jumps.  May include conditional or unconditional change of
 796              flow.  What is important for CFG creation is that the target be
 797              local to function.  */
 798           if (ginsn->type == GINSN_TYPE_JUMP_COND
 799               || ginsn_direct_local_jump_p (ginsn))
 800             {
 801               gas_assert (ginsn->src[0].type == GINSN_SRC_SYMBOL);
 802               taken_label = ginsn->src[0].sym;
 803               gas_assert (taken_label);
 804
 805               /* Preserve the prev_bb to be the dominator bb as we are
 806                  going to follow the taken path of the conditional branch
 807                  soon.  */
 808               prev_bb = current_bb;
 809
 810               /* Follow the target on the taken path.  */
 811               target_ginsn = label_ginsn_map_find (taken_label);
 812               /* Add the bb for the target of the taken branch.  */
 813               if (target_ginsn)
 814                 find_or_make_bb (func, gcfg, target_ginsn, prev_bb, errp);
 815               else
 816                 {
 817                   *errp = GCFG_JLABEL_NOT_PRESENT;
 818                   as_warn_where (ginsn->file, ginsn->line,
 819                                  _("missing label '%s' in func '%s' may result in imprecise cfg"),
 820                                  S_GET_NAME (taken_label), S_GET_NAME (func));
 821                 }
 822               /* Add the bb for the fall through path.  */
 823               find_or_make_bb (func, gcfg, ginsn->next, prev_bb, errp);
 824             }
 825          else if (ginsn->type == GINSN_TYPE_RETURN)
 826            {
 827              /* We'll come back to the ginsns following GINSN_TYPE_RETURN
 828                 from another path if they are indeed reachable code.  */
 829              break;
 830            }
 831
 832          /* Current BB has been processed.  */
 833          current_bb = NULL;
 834         }
 835       ginsn = ginsn->next;
 836     }
 837
 838   return current_bb;
 839 }
 840
 841 static int
 842 gbbs_compare (const void *v1, const void *v2)
 843 {
 844   const gbbS *bb1 = *(const gbbS **) v1;
 845   const gbbS *bb2 = *(const gbbS **) v2;
 846
 847   if (bb1->first_ginsn->id < bb2->first_ginsn->id)
 848     return -1;
 849   else if (bb1->first_ginsn->id > bb2->first_ginsn->id)
 850     return 1;
 851   else if (bb1->first_ginsn->id == bb2->first_ginsn->id)
 852     return 0;
 853
 854   return 0;
 855 }
 856
 857 /* Synthesize DWARF CFI and emit it.  */
 858
 859 static int
 860 ginsn_pass_execute_scfi (const symbolS *func, gcfgS *gcfg, gbbS *root_bb)
 861 {
 862   int err = scfi_synthesize_dw2cfi (func, gcfg, root_bb);
 863   if (!err)
 864     scfi_emit_dw2cfi (func);
 865
 866   return err;
 867 }
 868
 869 /* Traverse the list of ginsns for the function and warn if some
 870    ginsns are not visited.
 871
 872    FIXME - this code assumes the caller has already performed a pass over
 873    ginsns such that the reachable ginsns are already marked.  Revisit this - we
 874    should ideally make this pass self-sufficient.  */
 875
 876 static int
 877 ginsn_pass_warn_unreachable_code (const symbolS *func,
 878                                   gcfgS *gcfg ATTRIBUTE_UNUSED,
 879                                   ginsnS *root_ginsn)
 880 {
 881   ginsnS *ginsn;
 882   bool unreach_p = false;
 883
 884   if (!gcfg || !func || !root_ginsn)
 885     return 0;
 886
 887   ginsn = root_ginsn;
 888
 889   while (ginsn)
 890     {
 891       /* Some ginsns of type GINSN_TYPE_SYMBOL remain unvisited.  Some
 892          may even be excluded from the CFG as they are not reachable, given
 893          their function, e.g., user labels after return machine insn.  */
 894       if (!ginsn->visited
 895           && !GINSN_F_FUNC_END_P (ginsn)
 896           && !GINSN_F_USER_LABEL_P (ginsn))
 897         {
 898           unreach_p = true;
 899           break;
 900         }
 901       ginsn = ginsn->next;
 902     }
 903
 904   if (unreach_p)
 905     as_warn_where (ginsn->file, ginsn->line,
 906                    _("GINSN: found unreachable code in func '%s'"),
 907                    S_GET_NAME (func));
 908
 909   return unreach_p;
 910 }
 911
 912 void
 913 gcfg_get_bbs_in_prog_order (gcfgS *gcfg, gbbS **prog_order_bbs)
 914 {
 915   uint64_t i = 0;
 916   gbbS *gbb;
 917
 918   if (!prog_order_bbs)
 919     return;
 920
 921   cfg_for_each_bb (gcfg, gbb)
 922     {
 923       gas_assert (i < gcfg->num_gbbs);
 924       prog_order_bbs[i++] = gbb;
 925     }
 926
 927   qsort (prog_order_bbs, gcfg->num_gbbs, sizeof (gbbS *), gbbs_compare);
 928 }
 929
 930 /* Build the control flow graph for the ginsns of the function.
 931
 932    It is important that the target adds an appropriate ginsn:
 933      - GINSN_TYPE_JUMP,
 934      - GINSN_TYPE_JUMP_COND,
 935      - GINSN_TYPE_CALL,
 936      - GINSN_TYPE_RET
 937   at the associated points in the function.  The correctness of the CFG
 938   depends on the accuracy of these 'change of flow instructions'.  */
 939
 940 gcfgS *
 941 gcfg_build (const symbolS *func, int *errp)
 942 {
 943   gcfgS *gcfg;
 944   ginsnS *first_ginsn;
 945
 946   gcfg = XCNEW (gcfgS);
 947   first_ginsn = frchain_now->frch_ginsn_data->gins_rootP;
 948   add_bb_at_ginsn (func, gcfg, first_ginsn, NULL /* prev_bb.  */, errp);
 949
 950   return gcfg;
 951 }
 952
 953 void
 954 gcfg_cleanup (gcfgS **gcfgp)
 955 {
 956   gcfgS *cfg;
 957   gbbS *bb, *next_bb;
 958   gedgeS *edge, *next_edge;
 959
 960   if (!gcfgp || !*gcfgp)
 961     return;
 962
 963   cfg = *gcfgp;
 964   bb = gcfg_get_rootbb (cfg);
 965
 966   while (bb)
 967     {
 968       next_bb = bb->next;
 969
 970       /* Cleanup all the edges.  */
 971       edge = bb->out_gedges;
 972       while (edge)
 973         {
 974           next_edge = edge->next;
 975           free (edge);
 976           edge = next_edge;
 977         }
 978
 979       gbb_cleanup (&bb);
 980       bb = next_bb;
 981     }
 982
 983   free (cfg);
 984   *gcfgp = NULL;
 985 }
 986
 987 gbbS *
 988 gcfg_get_rootbb (gcfgS *gcfg)
 989 {
 990   gbbS *rootbb = NULL;
 991
 992   if (!gcfg || !gcfg->num_gbbs)
 993     return NULL;
 994
 995   rootbb = gcfg->root_bb;
 996
 997   return rootbb;
 998 }
 999
1000 void
1001 gcfg_print (const gcfgS *gcfg, FILE *outfile)
1002 {
1003   gbbS *gbb = NULL;
1004   gedgeS *gedge = NULL;
1005   uint64_t total_ginsns = 0;
1006
1007   cfg_for_each_bb(gcfg, gbb)
1008     {
1009       fprintf (outfile, "BB [%" PRIu64 "] with num insns: %" PRIu64,
1010                gbb->id, gbb->num_ginsns);
1011       fprintf (outfile, " [insns: %u to %u]\n",
1012                gbb->first_ginsn->line, gbb->last_ginsn->line);
1013       total_ginsns += gbb->num_ginsns;
1014       bb_for_each_edge(gbb, gedge)
1015         fprintf (outfile, "  outgoing edge to %" PRIu64 "\n",
1016                  gedge->dst_bb->id);
1017     }
1018   fprintf (outfile, "\nTotal ginsns in all GBBs = %" PRIu64 "\n",
1019            total_ginsns);
1020 }
1021
1022 void
1023 frch_ginsn_data_init (const symbolS *func, symbolS *start_addr,
1024                       enum ginsn_gen_mode gmode)
1025 {
1026   /* FIXME - error out if prev object is not free'd ?  */
1027   frchain_now->frch_ginsn_data = XCNEW (struct frch_ginsn_data);
1028
1029   frchain_now->frch_ginsn_data->mode = gmode;
1030   /* Annotate with the current function symbol.  */
1031   frchain_now->frch_ginsn_data->func = func;
1032   /* Create a new start address symbol now.  */
1033   frchain_now->frch_ginsn_data->start_addr = start_addr;
1034   /* Assume the set of ginsn are apt for CFG creation, by default.  */
1035   frchain_now->frch_ginsn_data->gcfg_apt_p = true;
1036
1037   frchain_now->frch_ginsn_data->label_ginsn_map = str_htab_create ();
1038 }
1039
1040 void
1041 frch_ginsn_data_cleanup (void)
1042 {
1043   ginsnS *ginsn = NULL;
1044   ginsnS *next_ginsn = NULL;
1045
1046   ginsn = frchain_now->frch_ginsn_data->gins_rootP;
1047   while (ginsn)
1048     {
1049       next_ginsn = ginsn->next;
1050       ginsn_cleanup (&ginsn);
1051       ginsn = next_ginsn;
1052     }
1053
1054   if (frchain_now->frch_ginsn_data->label_ginsn_map)
1055     htab_delete (frchain_now->frch_ginsn_data->label_ginsn_map);
1056
1057   free (frchain_now->frch_ginsn_data);
1058   frchain_now->frch_ginsn_data = NULL;
1059 }
1060
1061 /* Append GINSN to the list of ginsns for the current function being
1062    assembled.  */
1063
1064 int
1065 frch_ginsn_data_append (ginsnS *ginsn)
1066 {
1067   ginsnS *last = NULL;
1068   ginsnS *temp = NULL;
1069   uint64_t id = 0;
1070
1071   if (!ginsn)
1072     return 1;
1073
1074   if (frchain_now->frch_ginsn_data->gins_lastP)
1075     id = frchain_now->frch_ginsn_data->gins_lastP->id;
1076
1077   /* Do the necessary preprocessing on the set of input GINSNs:
1078        - Update each ginsn with its ID.
1079      While you iterate, also keep gcfg_apt_p updated by checking whether any
1080      ginsn is inappropriate for GCFG creation.  */
1081   temp = ginsn;
1082   while (temp)
1083     {
1084       temp->id = ++id;
1085
1086       if (ginsn_indirect_jump_p (temp)
1087           || (ginsn->type == GINSN_TYPE_JUMP
1088               && !ginsn_direct_local_jump_p (temp)))
1089         frchain_now->frch_ginsn_data->gcfg_apt_p = false;
1090
1091       if (listing & LISTING_GINSN_SCFI)
1092         listing_newline (ginsn_print (temp));
1093
1094       /* The input GINSN may be a linked list of multiple ginsns chained
1095          together.  Find the last ginsn in the input chain of ginsns.  */
1096       last = temp;
1097
1098       temp = temp->next;
1099     }
1100
1101   /* Link in the ginsn to the tail.  */
1102   if (!frchain_now->frch_ginsn_data->gins_rootP)
1103     frchain_now->frch_ginsn_data->gins_rootP = ginsn;
1104   else
1105     ginsn_link_next (frchain_now->frch_ginsn_data->gins_lastP, ginsn);
1106
1107   frchain_now->frch_ginsn_data->gins_lastP = last;
1108
1109   return 0;
1110 }
1111
1112 enum ginsn_gen_mode
1113 frch_ginsn_gen_mode (void)
1114 {
1115   enum ginsn_gen_mode gmode = GINSN_GEN_NONE;
1116
1117   if (frchain_now->frch_ginsn_data)
1118     gmode = frchain_now->frch_ginsn_data->mode;
1119
1120   return gmode;
1121 }
1122
1123 int
1124 ginsn_data_begin (const symbolS *func)
1125 {
1126   ginsnS *ginsn;
1127
1128   /* The previous block of asm must have been processed by now.  */
1129   if (frchain_now->frch_ginsn_data)
1130     as_bad (_("GINSN process for prev func not done"));
1131
1132   /* FIXME - hard code the mode to GINSN_GEN_SCFI.
1133      This can be changed later when other passes on ginsns are formalised.  */
1134   frch_ginsn_data_init (func, symbol_temp_new_now (), GINSN_GEN_SCFI);
1135
1136   /* Create and insert ginsn with function begin marker.  */
1137   ginsn = ginsn_new_symbol_func_begin (func);
1138   frch_ginsn_data_append (ginsn);
1139
1140   return 0;
1141 }
1142
1143 int
1144 ginsn_data_end (const symbolS *label)
1145 {
1146   ginsnS *ginsn;
1147   gbbS *root_bb;
1148   gcfgS *gcfg = NULL;
1149   const symbolS *func;
1150   int err = 0;
1151
1152   if (!frchain_now->frch_ginsn_data)
1153     return err;
1154
1155   /* Insert Function end marker.  */
1156   ginsn = ginsn_new_symbol_func_end (label);
1157   frch_ginsn_data_append (ginsn);
1158
1159   func = frchain_now->frch_ginsn_data->func;
1160
1161   /* Build the cfg of ginsn(s) of the function.  */
1162   if (!frchain_now->frch_ginsn_data->gcfg_apt_p)
1163     {
1164       as_bad (_("untraceable control flow for func '%s'"),
1165               S_GET_NAME (func));
1166       goto end;
1167     }
1168
1169   gcfg = gcfg_build (func, &err);
1170
1171   root_bb = gcfg_get_rootbb (gcfg);
1172   if (!root_bb)
1173     {
1174       as_bad (_("Bad cfg of ginsn of func '%s'"), S_GET_NAME (func));
1175       goto end;
1176     }
1177
1178   /* Execute the desired passes on ginsns.  */
1179   err = ginsn_pass_execute_scfi (func, gcfg, root_bb);
1180   if (err)
1181     goto end;
1182
1183   /* Other passes, e.g., warn for unreachable code can be enabled too.  */
1184   ginsn = frchain_now->frch_ginsn_data->gins_rootP;
1185   err = ginsn_pass_warn_unreachable_code (func, gcfg, ginsn);
1186
1187 end:
1188   if (gcfg)
1189     gcfg_cleanup (&gcfg);
1190   frch_ginsn_data_cleanup ();
1191
1192   return err;
1193 }
1194
1195 /* Add GINSN_TYPE_SYMBOL type ginsn for user-defined labels.  These may be
1196    branch targets, and hence are necessary for control flow graph.  */
1197
1198 void
1199 ginsn_frob_label (const symbolS *label)
1200 {
1201   ginsnS *label_ginsn;
1202   const char *file;
1203   unsigned int line;
1204
1205   if (frchain_now->frch_ginsn_data)
1206     {
1207       /* PS: Note how we keep the actual LABEL symbol as ginsn->sym.
1208          Take care to avoid inadvertent updates or cleanups of symbols.  */
1209       label_ginsn = ginsn_new_symbol_user_label (label);
1210       /* Keep the location updated.  */
1211       file = as_where (&line);
1212       ginsn_set_file_line (label_ginsn, file, line);
1213
1214       frch_ginsn_data_append (label_ginsn);
1215
1216       label_ginsn_map_insert (label, label_ginsn);
1217     }
1218 }
1219
1220 const symbolS *
1221 ginsn_data_func_symbol (void)
1222 {
1223   const symbolS *func = NULL;
1224
1225   if (frchain_now->frch_ginsn_data)
1226     func = frchain_now->frch_ginsn_data->func;
1227
1228   return func;
1229 }
1230
1231 #else
1232
1233 int
1234 ginsn_data_begin (const symbolS *func ATTRIBUTE_UNUSED)
1235 {
1236   as_bad (_("ginsn unsupported for target"));
1237   return 1;
1238 }
1239
1240 int
1241 ginsn_data_end (const symbolS *label ATTRIBUTE_UNUSED)
1242 {
1243   as_bad (_("ginsn unsupported for target"));
1244   return 1;
1245 }
1246
1247 void
1248 ginsn_frob_label (const symbolS *sym ATTRIBUTE_UNUSED)
1249 {
1250   return;
1251 }
1252
1253 const symbolS *
1254 ginsn_data_func_symbol (void)
1255 {
1256   return NULL;
1257 }
1258
1259 #endif  /* TARGET_USE_GINSN.  */