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 /* Return whether the GINSN is an unconditional jump to a label which is
 448    defined locally in the scope of the block of insns, which are currently
 449    being processed for GCFG creation.  */
 450
 451 static bool
 452 ginsn_direct_local_jump_p (ginsnS *ginsn)
 453 {
 454   bool local_p = false;
 455   const symbolS *taken_label;
 456
 457   if (!ginsn)
 458     return local_p;
 459
 460   if (ginsn->type == GINSN_TYPE_JUMP
 461       && ginsn->src[0].type == GINSN_SRC_SYMBOL)
 462     {
 463       taken_label = ginsn->src[0].sym;
 464       local_p = (label_ginsn_map_find (taken_label) != NULL);
 465     }
 466   return local_p;
 467 }
 468
 469 static char *
 470 ginsn_src_print (struct ginsn_src *src)
 471 {
 472   size_t len = 40;
 473   char *src_str = XNEWVEC (char, len);
 474
 475   memset (src_str, 0, len);
 476
 477   switch (src->type)
 478     {
 479     case GINSN_SRC_REG:
 480       snprintf (src_str, len, "%%r%d, ", ginsn_get_src_reg (src));
 481       break;
 482     case GINSN_SRC_IMM:
 483       snprintf (src_str, len, "%lld, ",
 484                 (long long int) ginsn_get_src_imm (src));
 485       break;
 486     case GINSN_SRC_INDIRECT:
 487       snprintf (src_str, len, "[%%r%d+%lld], ", ginsn_get_src_reg (src),
 488                 (long long int) ginsn_get_src_disp (src));
 489       break;
 490     default:
 491       break;
 492     }
 493
 494   return src_str;
 495 }
 496
 497 static char*
 498 ginsn_dst_print (struct ginsn_dst *dst)
 499 {
 500   int str_size = 0;
 501   size_t len = GINSN_LISTING_OPND_LEN;
 502   char *dst_str = XNEWVEC (char, len);
 503
 504   memset (dst_str, 0, len);
 505
 506   if (dst->type == GINSN_DST_REG)
 507     str_size = snprintf (dst_str, GINSN_LISTING_OPND_LEN,
 508                          "%%r%d", ginsn_get_dst_reg (dst));
 509   else if (dst->type == GINSN_DST_INDIRECT)
 510     str_size = snprintf (dst_str, GINSN_LISTING_OPND_LEN,
 511                          "[%%r%d+%lld]", ginsn_get_dst_reg (dst),
 512                          (long long int) ginsn_get_dst_disp (dst));
 513   else if (dst->type != GINSN_DST_UNKNOWN)
 514     /* Other dst types are unexpected.  */
 515     gas_assert (false);
 516
 517   /* str_size will remain 0 when GINSN_DST_UNKNOWN.  */
 518   gas_assert (str_size >= 0 && str_size < GINSN_LISTING_OPND_LEN);
 519
 520   return dst_str;
 521 }
 522
 523 static const char*
 524 ginsn_type_func_marker_print (ginsnS *ginsn)
 525 {
 526   int id = 0;
 527   static const char * const ginsn_sym_strs[] =
 528     { "", "FUNC_BEGIN", "FUNC_END" };
 529
 530   if (GINSN_F_FUNC_BEGIN_P (ginsn))
 531     id = 1;
 532   else if (GINSN_F_FUNC_END_P (ginsn))
 533     id = 2;
 534
 535   return ginsn_sym_strs[id];
 536 }
 537
 538 static char*
 539 ginsn_print (ginsnS *ginsn)
 540 {
 541   struct ginsn_src *src;
 542   struct ginsn_dst *dst;
 543   int str_size = 0;
 544   size_t len = GINSN_LISTING_LEN;
 545   char *ginsn_str = XNEWVEC (char, len);
 546
 547   memset (ginsn_str, 0, len);
 548
 549   str_size = snprintf (ginsn_str, GINSN_LISTING_LEN, "ginsn: %s",
 550                        ginsn_type_names[ginsn->type]);
 551   gas_assert (str_size >= 0 && str_size < GINSN_LISTING_LEN);
 552
 553   /* For some ginsn types, no further information is printed for now.  */
 554   if (ginsn->type == GINSN_TYPE_CALL
 555       || ginsn->type == GINSN_TYPE_RETURN)
 556     goto end;
 557   else if (ginsn->type == GINSN_TYPE_SYMBOL)
 558     {
 559       if (GINSN_F_USER_LABEL_P (ginsn))
 560         str_size += snprintf (ginsn_str + str_size,
 561                               GINSN_LISTING_LEN - str_size,
 562                               " %s", S_GET_NAME (ginsn->sym));
 563       else
 564         str_size += snprintf (ginsn_str + str_size,
 565                               GINSN_LISTING_LEN - str_size,
 566                               " %s", ginsn_type_func_marker_print (ginsn));
 567       goto end;
 568     }
 569
 570   /* src 1.  */
 571   src = ginsn_get_src1 (ginsn);
 572   char *src_buf = ginsn_src_print (src);
 573   str_size += snprintf (ginsn_str + str_size, GINSN_LISTING_LEN - str_size,
 574                         " %s", src_buf);
 575   free (src_buf);
 576   gas_assert (str_size >= 0 && str_size < GINSN_LISTING_LEN);
 577
 578   /* src 2.  */
 579   src = ginsn_get_src2 (ginsn);
 580   src_buf = ginsn_src_print (src);
 581   str_size += snprintf (ginsn_str + str_size, GINSN_LISTING_LEN - str_size,
 582                         "%s", src_buf);
 583   free (src_buf);
 584   gas_assert (str_size >= 0 && str_size < GINSN_LISTING_LEN);
 585
 586   /* dst.  */
 587   dst = ginsn_get_dst (ginsn);
 588   char *dst_buf = ginsn_dst_print (dst);
 589   str_size += snprintf (ginsn_str + str_size, GINSN_LISTING_LEN - str_size,
 590                         "%s", dst_buf);
 591   free (dst_buf);
 592
 593 end:
 594   gas_assert (str_size >= 0 && str_size < GINSN_LISTING_LEN);
 595   return ginsn_str;
 596 }
 597
 598 static void
 599 gbb_cleanup (gbbS **bbp)
 600 {
 601   gbbS *bb = NULL;
 602
 603   if (!bbp && !*bbp)
 604     return;
 605
 606   bb = *bbp;
 607
 608   if (bb->entry_state)
 609     {
 610       free (bb->entry_state);
 611       bb->entry_state = NULL;
 612     }
 613   if (bb->exit_state)
 614     {
 615       free (bb->exit_state);
 616       bb->exit_state = NULL;
 617     }
 618   free (bb);
 619   *bbp = NULL;
 620 }
 621
 622 /* Add an edge from the source bb FROM_BB to the sink bb TO_BB.  */
 623
 624 static void
 625 bb_add_edge (gbbS* from_bb, gbbS *to_bb)
 626 {
 627   gedgeS *tmpedge = NULL;
 628   gedgeS *gedge;
 629   bool exists = false;
 630
 631   if (!from_bb || !to_bb)
 632     return;
 633
 634   /* Create a new edge object.  */
 635   gedge = XCNEW (gedgeS);
 636   gedge->dst_bb = to_bb;
 637   gedge->next = NULL;
 638   gedge->visited = false;
 639
 640   /* Add it in.  */
 641   if (from_bb->out_gedges == NULL)
 642     {
 643       from_bb->out_gedges = gedge;
 644       from_bb->num_out_gedges++;
 645     }
 646   else
 647     {
 648       /* Get the head of the list.  */
 649       tmpedge = from_bb->out_gedges;
 650       while (tmpedge)
 651         {
 652           /* Do not add duplicate edges.  Duplicated edges will cause unwanted
 653              failures in the forward and backward passes for SCFI.  */
 654           if (tmpedge->dst_bb == to_bb)
 655             {
 656               exists = true;
 657               break;
 658             }
 659           if (tmpedge->next)
 660             tmpedge = tmpedge->next;
 661           else
 662             break;
 663         }
 664
 665       if (!exists)
 666         {
 667           tmpedge->next = gedge;
 668           from_bb->num_out_gedges++;
 669         }
 670       else
 671         free (gedge);
 672     }
 673 }
 674
 675 static void
 676 cfg_add_bb (gcfgS *gcfg, gbbS *gbb)
 677 {
 678   gbbS *last_bb = NULL;
 679
 680   if (!gcfg->root_bb)
 681     gcfg->root_bb = gbb;
 682   else
 683     {
 684       last_bb = gcfg->root_bb;
 685       while (last_bb->next)
 686         last_bb = last_bb->next;
 687
 688       last_bb->next = gbb;
 689     }
 690   gcfg->num_gbbs++;
 691
 692   gbb->id = gcfg->num_gbbs;
 693 }
 694
 695 static gbbS *
 696 add_bb_at_ginsn (const symbolS *func, gcfgS *gcfg, ginsnS *ginsn, gbbS *prev_bb,
 697                  int *errp);
 698
 699 /* Return the already existing basic block (if present), which begins with
 700    GINSN, in the given GCFG.  Return NULL otherwise.  */
 701
 702 static gbbS *
 703 find_bb (gcfgS *gcfg, ginsnS *ginsn)
 704 {
 705   gbbS *found_bb = NULL;
 706   gbbS *gbb = NULL;
 707
 708   if (!ginsn)
 709     return found_bb;
 710
 711   if (ginsn->visited)
 712     {
 713       cfg_for_each_bb (gcfg, gbb)
 714         {
 715           if (gbb->first_ginsn == ginsn)
 716             {
 717               found_bb = gbb;
 718               break;
 719             }
 720         }
 721       /* Must be found because ginsn is visited.  */
 722       gas_assert (found_bb);
 723     }
 724
 725   return found_bb;
 726 }
 727
 728 /* Get the basic block starting at GINSN in the GCFG.
 729
 730    If not already present, the function will make one, while adding an edge
 731    from the PREV_BB to it.  */
 732
 733 static gbbS *
 734 find_or_make_bb (const symbolS *func, gcfgS *gcfg, ginsnS *ginsn, gbbS *prev_bb,
 735                  int *errp)
 736 {
 737   gbbS *found_bb = NULL;
 738
 739   found_bb = find_bb (gcfg, ginsn);
 740   if (!found_bb)
 741     found_bb = add_bb_at_ginsn (func, gcfg, ginsn, prev_bb, errp);
 742
 743   gas_assert (found_bb);
 744   gas_assert (found_bb->first_ginsn == ginsn);
 745
 746   return found_bb;
 747 }
 748
 749 /* Add basic block(s) for all reachable, unvisited ginsns, starting from GINSN,
 750    to the given GCFG.  Also add an edge from the PREV_BB to the root of the
 751    newly added basic block(s).
 752
 753    This is a recursive function which returns the root of the added basic
 754    blocks.  */
 755
 756 static gbbS *
 757 add_bb_at_ginsn (const symbolS *func, gcfgS *gcfg, ginsnS *ginsn, gbbS *prev_bb,
 758                  int *errp)
 759 {
 760   gbbS *root_bb = NULL;
 761   gbbS *current_bb = NULL;
 762   ginsnS *target_ginsn = NULL;
 763   const symbolS *taken_label;
 764
 765   /* Create a new bb.  N.B. The caller must ensure bb with this ginsn does not
 766      already exist.  */
 767   gas_assert (!find_bb (gcfg, ginsn));
 768   root_bb = XCNEW (gbbS);
 769   cfg_add_bb (gcfg, root_bb);
 770   root_bb->first_ginsn = ginsn;
 771
 772   current_bb = root_bb;
 773
 774   while (ginsn)
 775     {
 776       /* Skip these as they may be right after a GINSN_TYPE_RETURN.
 777          For GINSN_TYPE_RETURN, we have already considered that as
 778          end of bb, and a logical exit from function.  */
 779       if (GINSN_F_FUNC_END_P (ginsn))
 780         {
 781           /* Dont mark them visited yet though, leaving the option of these
 782              being visited via other control flows as applicable.  */
 783           ginsn = ginsn->next;
 784           continue;
 785         }
 786
 787       if (ginsn->visited)
 788         {
 789           /* If the ginsn has been visited earlier, the bb must exist by now
 790              in the cfg.  */
 791           prev_bb = current_bb;
 792           current_bb = find_bb (gcfg, ginsn);
 793           gas_assert (current_bb);
 794           /* Add edge from the prev_bb.  */
 795           if (prev_bb)
 796             bb_add_edge (prev_bb, current_bb);
 797           break;
 798         }
 799       else if (current_bb && current_bb->first_ginsn != ginsn
 800                && GINSN_F_USER_LABEL_P (ginsn))
 801         {
 802           /* Create new bb starting at ginsn for (user-defined) label.  This is
 803              likely going to be a destination of a some control flow.  */
 804           prev_bb = current_bb;
 805           current_bb = find_or_make_bb (func, gcfg, ginsn, prev_bb, errp);
 806           bb_add_edge (prev_bb, current_bb);
 807           break;
 808         }
 809
 810       if (current_bb == NULL)
 811         {
 812           current_bb = XCNEW (gbbS);
 813           cfg_add_bb (gcfg, current_bb);
 814           current_bb->first_ginsn = ginsn;
 815           /* Add edge for the Not Taken, or Fall-through path.  */
 816           if (prev_bb)
 817             bb_add_edge (prev_bb, current_bb);
 818         }
 819
 820       ginsn->visited = true;
 821       current_bb->num_ginsns++;
 822       current_bb->last_ginsn = ginsn;
 823
 824       /* Note that BB is _not_ split on ginsn of type GINSN_TYPE_CALL.  */
 825       if (ginsn->type == GINSN_TYPE_JUMP
 826           || ginsn->type == GINSN_TYPE_JUMP_COND
 827           || ginsn->type == GINSN_TYPE_RETURN)
 828         {
 829           /* Indirect jumps must not be seen here.  The caller must have
 830              already checked for that.  */
 831           gas_assert (!ginsn_indirect_jump_p (ginsn));
 832
 833           /* Handle direct jumps.  For unconditional direct jumps, where the
 834              target is not local to the function, treat them later as similar
 835              to an exit from function (in the else block).  */
 836           if (ginsn->type == GINSN_TYPE_JUMP_COND
 837               || ginsn_direct_local_jump_p (ginsn))
 838             {
 839               gas_assert (ginsn->src[0].type == GINSN_SRC_SYMBOL);
 840               taken_label = ginsn->src[0].sym;
 841               gas_assert (taken_label);
 842
 843               /* Preserve the prev_bb to be the source bb as we are going to
 844                  follow the taken path of the conditional branch soon.  */
 845               prev_bb = current_bb;
 846
 847               /* Follow the target on the taken path.  */
 848               target_ginsn = label_ginsn_map_find (taken_label);
 849               /* Add the bb for the target of the taken branch.  */
 850               if (target_ginsn)
 851                 {
 852                   current_bb = find_or_make_bb (func, gcfg, target_ginsn,
 853                                                 prev_bb, errp);
 854                   gas_assert (prev_bb);
 855                   bb_add_edge (prev_bb, current_bb);
 856                   current_bb = NULL;
 857                 }
 858               else
 859                 {
 860                   *errp = GCFG_JLABEL_NOT_PRESENT;
 861                   as_warn_where (ginsn->file, ginsn->line,
 862                                  _("missing label '%s' in func '%s' may result in imprecise cfg"),
 863                                  S_GET_NAME (taken_label), S_GET_NAME (func));
 864                 }
 865
 866               if (ginsn->type == GINSN_TYPE_JUMP_COND)
 867                 {
 868                   /* Add the bb for the fall through path.  */
 869                   current_bb = find_or_make_bb (func, gcfg, ginsn->next,
 870                                                 prev_bb, errp);
 871                   gas_assert (prev_bb);
 872                   bb_add_edge (prev_bb, current_bb);
 873                   current_bb = NULL;
 874                 }
 875               else
 876                 {
 877                   /* Unconditional jump.  Current BB has been processed.  */
 878                   current_bb = NULL;
 879                   /* We'll come back to the ginsns following these (local)
 880                      unconditional jmps from another path if they are indeed
 881                      reachable code.  */
 882                   break;
 883                 }
 884             }
 885          else
 886            {
 887              gas_assert (ginsn->type == GINSN_TYPE_RETURN
 888                          || (ginsn->type == GINSN_TYPE_JUMP
 889                              && !ginsn_direct_local_jump_p (ginsn)));
 890              /* Current BB has been processed.  */
 891              current_bb = NULL;
 892
 893              /* We'll come back to the ginsns following GINSN_TYPE_RETURN or
 894                 other (non-local) unconditional jmps from another path if they
 895                 are indeed reachable code.  */
 896              break;
 897            }
 898         }
 899
 900       ginsn = ginsn->next;
 901     }
 902
 903   return root_bb;
 904 }
 905
 906 static int
 907 gbbs_compare (const void *v1, const void *v2)
 908 {
 909   const gbbS *bb1 = *(const gbbS **) v1;
 910   const gbbS *bb2 = *(const gbbS **) v2;
 911
 912   if (bb1->first_ginsn->id < bb2->first_ginsn->id)
 913     return -1;
 914   else if (bb1->first_ginsn->id > bb2->first_ginsn->id)
 915     return 1;
 916   else if (bb1->first_ginsn->id == bb2->first_ginsn->id)
 917     return 0;
 918
 919   return 0;
 920 }
 921
 922 /* Synthesize DWARF CFI and emit it.  */
 923
 924 static int
 925 ginsn_pass_execute_scfi (const symbolS *func, gcfgS *gcfg, gbbS *root_bb)
 926 {
 927   int err = scfi_synthesize_dw2cfi (func, gcfg, root_bb);
 928   if (!err)
 929     scfi_emit_dw2cfi (func);
 930
 931   return err;
 932 }
 933
 934 /* Traverse the list of ginsns for the function and warn if some
 935    ginsns are not visited.
 936
 937    FIXME - this code assumes the caller has already performed a pass over
 938    ginsns such that the reachable ginsns are already marked.  Revisit this - we
 939    should ideally make this pass self-sufficient.  */
 940
 941 static int
 942 ginsn_pass_warn_unreachable_code (const symbolS *func,
 943                                   gcfgS *gcfg ATTRIBUTE_UNUSED,
 944                                   ginsnS *root_ginsn)
 945 {
 946   ginsnS *ginsn;
 947   bool unreach_p = false;
 948
 949   if (!gcfg || !func || !root_ginsn)
 950     return 0;
 951
 952   ginsn = root_ginsn;
 953
 954   while (ginsn)
 955     {
 956       /* Some ginsns of type GINSN_TYPE_SYMBOL remain unvisited.  Some
 957          may even be excluded from the CFG as they are not reachable, given
 958          their function, e.g., user labels after return machine insn.  */
 959       if (!ginsn->visited
 960           && !GINSN_F_FUNC_END_P (ginsn)
 961           && !GINSN_F_USER_LABEL_P (ginsn))
 962         {
 963           unreach_p = true;
 964           break;
 965         }
 966       ginsn = ginsn->next;
 967     }
 968
 969   if (unreach_p)
 970     as_warn_where (ginsn->file, ginsn->line,
 971                    _("GINSN: found unreachable code in func '%s'"),
 972                    S_GET_NAME (func));
 973
 974   return unreach_p;
 975 }
 976
 977 void
 978 gcfg_get_bbs_in_prog_order (gcfgS *gcfg, gbbS **prog_order_bbs)
 979 {
 980   uint64_t i = 0;
 981   gbbS *gbb;
 982
 983   if (!prog_order_bbs)
 984     return;
 985
 986   cfg_for_each_bb (gcfg, gbb)
 987     {
 988       gas_assert (i < gcfg->num_gbbs);
 989       prog_order_bbs[i++] = gbb;
 990     }
 991
 992   qsort (prog_order_bbs, gcfg->num_gbbs, sizeof (gbbS *), gbbs_compare);
 993 }
 994
 995 /* Build the control flow graph for the ginsns of the function.
 996
 997    It is important that the target adds an appropriate ginsn:
 998      - GINSN_TYPE_JUMP,
 999      - GINSN_TYPE_JUMP_COND,
1000      - GINSN_TYPE_CALL,
1001      - GINSN_TYPE_RET
1002   at the associated points in the function.  The correctness of the CFG
1003   depends on the accuracy of these 'change of flow instructions'.  */
1004
1005 gcfgS *
1006 gcfg_build (const symbolS *func, int *errp)
1007 {
1008   gcfgS *gcfg;
1009   ginsnS *first_ginsn;
1010
1011   gcfg = XCNEW (gcfgS);
1012   first_ginsn = frchain_now->frch_ginsn_data->gins_rootP;
1013   add_bb_at_ginsn (func, gcfg, first_ginsn, NULL /* prev_bb.  */, errp);
1014
1015   return gcfg;
1016 }
1017
1018 void
1019 gcfg_cleanup (gcfgS **gcfgp)
1020 {
1021   gcfgS *cfg;
1022   gbbS *bb, *next_bb;
1023   gedgeS *edge, *next_edge;
1024
1025   if (!gcfgp || !*gcfgp)
1026     return;
1027
1028   cfg = *gcfgp;
1029   bb = gcfg_get_rootbb (cfg);
1030
1031   while (bb)
1032     {
1033       next_bb = bb->next;
1034
1035       /* Cleanup all the edges.  */
1036       edge = bb->out_gedges;
1037       while (edge)
1038         {
1039           next_edge = edge->next;
1040           free (edge);
1041           edge = next_edge;
1042         }
1043
1044       gbb_cleanup (&bb);
1045       bb = next_bb;
1046     }
1047
1048   free (cfg);
1049   *gcfgp = NULL;
1050 }
1051
1052 gbbS *
1053 gcfg_get_rootbb (gcfgS *gcfg)
1054 {
1055   gbbS *rootbb = NULL;
1056
1057   if (!gcfg || !gcfg->num_gbbs)
1058     return NULL;
1059
1060   rootbb = gcfg->root_bb;
1061
1062   return rootbb;
1063 }
1064
1065 void
1066 gcfg_print (const gcfgS *gcfg, FILE *outfile)
1067 {
1068   gbbS *gbb = NULL;
1069   gedgeS *gedge = NULL;
1070   uint64_t total_ginsns = 0;
1071
1072   cfg_for_each_bb(gcfg, gbb)
1073     {
1074       fprintf (outfile, "BB [%" PRIu64 "] with num insns: %" PRIu64,
1075                gbb->id, gbb->num_ginsns);
1076       fprintf (outfile, " [insns: %u to %u]\n",
1077                gbb->first_ginsn->line, gbb->last_ginsn->line);
1078       total_ginsns += gbb->num_ginsns;
1079       bb_for_each_edge(gbb, gedge)
1080         fprintf (outfile, "  outgoing edge to %" PRIu64 "\n",
1081                  gedge->dst_bb->id);
1082     }
1083   fprintf (outfile, "\nTotal ginsns in all GBBs = %" PRIu64 "\n",
1084            total_ginsns);
1085 }
1086
1087 void
1088 frch_ginsn_data_init (const symbolS *func, symbolS *start_addr,
1089                       enum ginsn_gen_mode gmode)
1090 {
1091   /* FIXME - error out if prev object is not free'd ?  */
1092   frchain_now->frch_ginsn_data = XCNEW (struct frch_ginsn_data);
1093
1094   frchain_now->frch_ginsn_data->mode = gmode;
1095   /* Annotate with the current function symbol.  */
1096   frchain_now->frch_ginsn_data->func = func;
1097   /* Create a new start address symbol now.  */
1098   frchain_now->frch_ginsn_data->start_addr = start_addr;
1099   /* Assume the set of ginsn are apt for CFG creation, by default.  */
1100   frchain_now->frch_ginsn_data->gcfg_apt_p = true;
1101
1102   frchain_now->frch_ginsn_data->label_ginsn_map = str_htab_create ();
1103 }
1104
1105 void
1106 frch_ginsn_data_cleanup (void)
1107 {
1108   ginsnS *ginsn = NULL;
1109   ginsnS *next_ginsn = NULL;
1110
1111   ginsn = frchain_now->frch_ginsn_data->gins_rootP;
1112   while (ginsn)
1113     {
1114       next_ginsn = ginsn->next;
1115       ginsn_cleanup (&ginsn);
1116       ginsn = next_ginsn;
1117     }
1118
1119   if (frchain_now->frch_ginsn_data->label_ginsn_map)
1120     htab_delete (frchain_now->frch_ginsn_data->label_ginsn_map);
1121
1122   free (frchain_now->frch_ginsn_data);
1123   frchain_now->frch_ginsn_data = NULL;
1124 }
1125
1126 /* Append GINSN to the list of ginsns for the current function being
1127    assembled.  */
1128
1129 int
1130 frch_ginsn_data_append (ginsnS *ginsn)
1131 {
1132   ginsnS *last = NULL;
1133   ginsnS *temp = NULL;
1134   uint64_t id = 0;
1135
1136   if (!ginsn)
1137     return 1;
1138
1139   if (frchain_now->frch_ginsn_data->gins_lastP)
1140     id = frchain_now->frch_ginsn_data->gins_lastP->id;
1141
1142   /* Do the necessary preprocessing on the set of input GINSNs:
1143        - Update each ginsn with its ID.
1144      While you iterate, also keep gcfg_apt_p updated by checking whether any
1145      ginsn is inappropriate for GCFG creation.  */
1146   temp = ginsn;
1147   while (temp)
1148     {
1149       temp->id = ++id;
1150
1151       if (ginsn_indirect_jump_p (temp))
1152         frchain_now->frch_ginsn_data->gcfg_apt_p = false;
1153
1154       if (listing & LISTING_GINSN_SCFI)
1155         listing_newline (ginsn_print (temp));
1156
1157       /* The input GINSN may be a linked list of multiple ginsns chained
1158          together.  Find the last ginsn in the input chain of ginsns.  */
1159       last = temp;
1160
1161       temp = temp->next;
1162     }
1163
1164   /* Link in the ginsn to the tail.  */
1165   if (!frchain_now->frch_ginsn_data->gins_rootP)
1166     frchain_now->frch_ginsn_data->gins_rootP = ginsn;
1167   else
1168     ginsn_link_next (frchain_now->frch_ginsn_data->gins_lastP, ginsn);
1169
1170   frchain_now->frch_ginsn_data->gins_lastP = last;
1171
1172   return 0;
1173 }
1174
1175 enum ginsn_gen_mode
1176 frch_ginsn_gen_mode (void)
1177 {
1178   enum ginsn_gen_mode gmode = GINSN_GEN_NONE;
1179
1180   if (frchain_now->frch_ginsn_data)
1181     gmode = frchain_now->frch_ginsn_data->mode;
1182
1183   return gmode;
1184 }
1185
1186 int
1187 ginsn_data_begin (const symbolS *func)
1188 {
1189   ginsnS *ginsn;
1190
1191   /* The previous block of asm must have been processed by now.  */
1192   if (frchain_now->frch_ginsn_data)
1193     as_bad (_("GINSN process for prev func not done"));
1194
1195   /* FIXME - hard code the mode to GINSN_GEN_SCFI.
1196      This can be changed later when other passes on ginsns are formalised.  */
1197   frch_ginsn_data_init (func, symbol_temp_new_now (), GINSN_GEN_SCFI);
1198
1199   /* Create and insert ginsn with function begin marker.  */
1200   ginsn = ginsn_new_symbol_func_begin (func);
1201   frch_ginsn_data_append (ginsn);
1202
1203   return 0;
1204 }
1205
1206 int
1207 ginsn_data_end (const symbolS *label)
1208 {
1209   ginsnS *ginsn;
1210   gbbS *root_bb;
1211   gcfgS *gcfg = NULL;
1212   const symbolS *func;
1213   int err = 0;
1214
1215   if (!frchain_now->frch_ginsn_data)
1216     return err;
1217
1218   /* Insert Function end marker.  */
1219   ginsn = ginsn_new_symbol_func_end (label);
1220   frch_ginsn_data_append (ginsn);
1221
1222   func = frchain_now->frch_ginsn_data->func;
1223
1224   /* Build the cfg of ginsn(s) of the function.  */
1225   if (!frchain_now->frch_ginsn_data->gcfg_apt_p)
1226     {
1227       as_bad (_("untraceable control flow for func '%s'"),
1228               S_GET_NAME (func));
1229       goto end;
1230     }
1231
1232   gcfg = gcfg_build (func, &err);
1233
1234   root_bb = gcfg_get_rootbb (gcfg);
1235   if (!root_bb)
1236     {
1237       as_bad (_("Bad cfg of ginsn of func '%s'"), S_GET_NAME (func));
1238       goto end;
1239     }
1240
1241   /* Execute the desired passes on ginsns.  */
1242   err = ginsn_pass_execute_scfi (func, gcfg, root_bb);
1243   if (err)
1244     goto end;
1245
1246   /* Other passes, e.g., warn for unreachable code can be enabled too.  */
1247   ginsn = frchain_now->frch_ginsn_data->gins_rootP;
1248   err = ginsn_pass_warn_unreachable_code (func, gcfg, ginsn);
1249
1250 end:
1251   if (gcfg)
1252     gcfg_cleanup (&gcfg);
1253   frch_ginsn_data_cleanup ();
1254
1255   return err;
1256 }
1257
1258 /* Add GINSN_TYPE_SYMBOL type ginsn for user-defined labels.  These may be
1259    branch targets, and hence are necessary for control flow graph.  */
1260
1261 void
1262 ginsn_frob_label (const symbolS *label)
1263 {
1264   ginsnS *label_ginsn;
1265   const char *file;
1266   unsigned int line;
1267
1268   if (frchain_now->frch_ginsn_data)
1269     {
1270       /* PS: Note how we keep the actual LABEL symbol as ginsn->sym.
1271          Take care to avoid inadvertent updates or cleanups of symbols.  */
1272       label_ginsn = ginsn_new_symbol_user_label (label);
1273       /* Keep the location updated.  */
1274       file = as_where (&line);
1275       ginsn_set_file_line (label_ginsn, file, line);
1276
1277       frch_ginsn_data_append (label_ginsn);
1278
1279       label_ginsn_map_insert (label, label_ginsn);
1280     }
1281 }
1282
1283 const symbolS *
1284 ginsn_data_func_symbol (void)
1285 {
1286   const symbolS *func = NULL;
1287
1288   if (frchain_now->frch_ginsn_data)
1289     func = frchain_now->frch_ginsn_data->func;
1290
1291   return func;
1292 }
1293
1294 #else
1295
1296 int
1297 ginsn_data_begin (const symbolS *func ATTRIBUTE_UNUSED)
1298 {
1299   as_bad (_("ginsn unsupported for target"));
1300   return 1;
1301 }
1302
1303 int
1304 ginsn_data_end (const symbolS *label ATTRIBUTE_UNUSED)
1305 {
1306   as_bad (_("ginsn unsupported for target"));
1307   return 1;
1308 }
1309
1310 void
1311 ginsn_frob_label (const symbolS *sym ATTRIBUTE_UNUSED)
1312 {
1313   return;
1314 }
1315
1316 const symbolS *
1317 ginsn_data_func_symbol (void)
1318 {
1319   return NULL;
1320 }
1321
1322 #endif  /* TARGET_USE_GINSN.  */