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