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