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