mono/mini/seq-points.c

   1 /*
   2  * seq-points.c: Sequence Points functions
   3  *
   4  * Authors:
   5  *   Marcos Henrich (marcos.henrich@xamarin.com)
   6  *
   7  * Copyright 2014 Xamarin, Inc (http://www.xamarin.com)
   8  */
   9
  10 #include "mini.h"
  11 #include "seq-points.h"
  12
  13 typedef struct {
  14         guint8 *data;
  15         int len;
  16         /* When has_debug_data is set to false only il and native deltas are saved */
  17         gboolean has_debug_data;
  18         /* When alloc_data is set to true data allocation/deallocation is managed by this structure */
  19         gboolean alloc_data;
  20 } SeqPointInfoInflated;
  21
  22 static int
  23 encode_var_int (guint8 *buf, guint8 **out_buf, int val)
  24 {
  25         guint8 size = 0;
  26
  27         do {
  28                 guint8 byte = val & 0x7f;
  29                 g_assert (size < 4 && "value has more than 28 bits");
  30                 val >>= 7;
  31                 if(val) byte |= 0x80;
  32                 *(buf++) = byte;
  33                 size++;
  34         } while (val);
  35
  36         if (out_buf)
  37                 *out_buf = buf;
  38
  39         return size;
  40 }
  41
  42 static int
  43 decode_var_int (guint8* buf, guint8 **out_buf)
  44 {
  45         guint8* p = buf;
  46
  47         int low;
  48         int b;
  49         b = *(p++); low   = (b & 0x7f)      ; if(!(b & 0x80)) goto done;
  50         b = *(p++); low  |= (b & 0x7f) <<  7; if(!(b & 0x80)) goto done;
  51         b = *(p++); low  |= (b & 0x7f) << 14; if(!(b & 0x80)) goto done;
  52         b = *(p++); low  |= (b & 0x7f) << 21; if(!(b & 0x80)) goto done;
  53
  54         g_assert (FALSE && "value has more than 28 bits");
  55
  56 done:
  57
  58         if (out_buf)
  59                 *out_buf = p;
  60
  61         return low;
  62 }
  63
  64 static guint32
  65 encode_zig_zag (int val)
  66 {
  67         return (val << 1) ^ (val >> 31);
  68 }
  69
  70 static int
  71 decode_zig_zag (guint32 val)
  72 {
  73         int n = val;
  74         return (n >> 1) ^ (-(n & 1));
  75 }
  76
  77 static SeqPointInfoInflated
  78 seq_point_info_inflate (MonoSeqPointInfo *info)
  79 {
  80         SeqPointInfoInflated info_inflated;
  81         guint8 *ptr = (guint8*) info;
  82         int value;
  83
  84         value = decode_var_int (ptr, &ptr);
  85
  86         info_inflated.len = value >> 2;
  87         info_inflated.has_debug_data = (value & 1) != 0;
  88         info_inflated.alloc_data = (value & 2) != 0;
  89
  90         if (info_inflated.alloc_data)
  91                 info_inflated.data = ptr;
  92         else
  93                 memcpy (&info_inflated.data, ptr, sizeof (guint8*));
  94
  95         return info_inflated;
  96 }
  97
  98 static MonoSeqPointInfo*
  99 seq_point_info_new (int len, gboolean alloc_data, guint8 *data, gboolean has_debug_data)
 100 {
 101         MonoSeqPointInfo *info;
 102         guint8 *info_ptr;
 103         guint8 buffer[4];
 104         int buffer_len;
 105         int value;
 106         int data_size;
 107
 108         value = len << 2;
 109         if (has_debug_data)
 110                 value |= 1;
 111         if (alloc_data)
 112                 value |= 2;
 113
 114         buffer_len = encode_var_int (buffer, NULL, value);
 115
 116         data_size = buffer_len + (alloc_data? len : sizeof (guint8*));
 117         info_ptr = g_new0 (guint8, data_size);
 118         info = (MonoSeqPointInfo*) info_ptr;
 119
 120         memcpy (info_ptr, buffer, buffer_len);
 121         info_ptr += buffer_len;
 122
 123         if (alloc_data)
 124                 memcpy (info_ptr, data, len);
 125         else
 126                 memcpy (info_ptr, &data, sizeof (guint8*));
 127
 128         mono_jit_stats.allocated_seq_points_size += data_size;
 129
 130         return info;
 131 }
 132
 133 void
 134 seq_point_info_free (gpointer ptr)
 135 {
 136         MonoSeqPointInfo* info = (MonoSeqPointInfo*) ptr;
 137         g_free (info);
 138 }
 139
 140 static int
 141 seq_point_read (SeqPoint* seq_point, guint8* ptr, guint8* buffer_ptr, gboolean has_debug_data)
 142 {
 143         int value, i;
 144         guint8* ptr0 = ptr;
 145
 146         value = decode_var_int (ptr, &ptr);
 147         seq_point->il_offset += decode_zig_zag (value);
 148
 149         value = decode_var_int (ptr, &ptr);
 150         seq_point->native_offset += decode_zig_zag (value);
 151
 152         if (has_debug_data) {
 153                 value = decode_var_int (ptr, &ptr);
 154                 seq_point->flags = value;
 155
 156                 if (seq_point->flags & MONO_SEQ_POINT_FLAG_EXIT_IL)
 157                         seq_point->il_offset = METHOD_EXIT_IL_OFFSET;
 158
 159                 value = decode_var_int (ptr, &ptr);
 160                 seq_point->next_len = value;
 161
 162                 if (seq_point->next_len) {
 163                         // store next offset and skip it
 164                         seq_point->next_offset = ptr - buffer_ptr;
 165                         for (i = 0; i < seq_point->next_len; ++i)
 166                                 decode_var_int (ptr, &ptr);
 167                 }
 168         }
 169
 170         return ptr - ptr0;
 171 }
 172
 173 static gboolean
 174 seq_point_info_add_seq_point (GByteArray* array, SeqPoint *sp, SeqPoint *last_seq_point, GSList *next, gboolean has_debug_data)
 175 {
 176         int il_delta, native_delta;
 177         GSList *l;
 178         guint8 buffer[4];
 179         guint8 len;
 180         int flags;
 181
 182         if (!has_debug_data &&
 183                 (sp->il_offset == METHOD_ENTRY_IL_OFFSET || sp->il_offset == METHOD_EXIT_IL_OFFSET))
 184                 return FALSE;
 185
 186         il_delta = sp->il_offset - last_seq_point->il_offset;
 187         native_delta = sp->native_offset - last_seq_point->native_offset;
 188
 189         flags = sp->flags;
 190
 191         if (has_debug_data && sp->il_offset == METHOD_EXIT_IL_OFFSET) {
 192                 il_delta = 0;
 193                 flags |= MONO_SEQ_POINT_FLAG_EXIT_IL;
 194         }
 195
 196         len = encode_var_int (buffer, NULL, encode_zig_zag (il_delta));
 197         g_byte_array_append (array, buffer, len);
 198
 199         len = encode_var_int (buffer, NULL, encode_zig_zag (native_delta));
 200         g_byte_array_append (array, buffer, len);
 201
 202         if (has_debug_data) {
 203                 sp->next_offset = array->len;
 204                 sp->next_len = g_slist_length (next);
 205
 206                 len = encode_var_int (buffer, NULL, flags);
 207                 g_byte_array_append (array, buffer, len);
 208
 209                 len = encode_var_int (buffer, NULL, sp->next_len);
 210                 g_byte_array_append (array, buffer, len);
 211
 212                 for (l = next; l; l = l->next) {
 213                         int next_index = GPOINTER_TO_UINT (l->data);
 214                         guint8 buffer[4];
 215                         int len = encode_var_int (buffer, NULL, next_index);
 216                         g_byte_array_append (array, buffer, len);
 217                 }
 218         }
 219
 220         return TRUE;
 221 }
 222
 223 static void
 224 collect_pred_seq_points (MonoBasicBlock *bb, MonoInst *ins, GSList **next, int depth)
 225 {
 226         int i;
 227         MonoBasicBlock *in_bb;
 228         GSList *l;
 229
 230         for (i = 0; i < bb->in_count; ++i) {
 231                 in_bb = bb->in_bb [i];
 232
 233                 if (in_bb->last_seq_point) {
 234                         int src_index = in_bb->last_seq_point->backend.size;
 235                         int dst_index = ins->backend.size;
 236
 237                         /* bb->in_bb might contain duplicates */
 238                         for (l = next [src_index]; l; l = l->next)
 239                                 if (GPOINTER_TO_UINT (l->data) == dst_index)
 240                                         break;
 241                         if (!l)
 242                                 next [src_index] = g_slist_append (next [src_index], GUINT_TO_POINTER (dst_index));
 243                 } else {
 244                         /* Have to look at its predecessors */
 245                         if (depth < 5)
 246                                 collect_pred_seq_points (in_bb, ins, next, depth + 1);
 247                 }
 248         }
 249 }
 250
 251 void
 252 mono_save_seq_point_info (MonoCompile *cfg)
 253 {
 254         MonoBasicBlock *bb;
 255         GSList *bb_seq_points, *l;
 256         MonoInst *last;
 257         MonoDomain *domain = cfg->domain;
 258         int i;
 259         GSList **next = NULL;
 260         SeqPoint* seq_points;
 261         GByteArray* array;
 262         gboolean has_debug_data = cfg->gen_seq_points_debug_data;
 263
 264         if (!cfg->seq_points)
 265                 return;
 266
 267         seq_points = g_new0 (SeqPoint, cfg->seq_points->len);
 268
 269         for (i = 0; i < cfg->seq_points->len; ++i) {
 270                 SeqPoint *sp = &seq_points [i];
 271                 MonoInst *ins = g_ptr_array_index (cfg->seq_points, i);
 272
 273                 sp->il_offset = ins->inst_imm;
 274                 sp->native_offset = ins->inst_offset;
 275                 if (ins->flags & MONO_INST_NONEMPTY_STACK)
 276                         sp->flags |= MONO_SEQ_POINT_FLAG_NONEMPTY_STACK;
 277
 278                 /* Used below */
 279                 ins->backend.size = i;
 280         }
 281
 282         if (has_debug_data) {
 283                 /*
 284                  * For each sequence point, compute the list of sequence points immediately
 285                  * following it, this is needed to implement 'step over' in the debugger agent.
 286                  */
 287                 next = g_new0 (GSList*, cfg->seq_points->len);
 288                 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 289                         bb_seq_points = g_slist_reverse (bb->seq_points);
 290                         last = NULL;
 291                         for (l = bb_seq_points; l; l = l->next) {
 292                                 MonoInst *ins = l->data;
 293
 294                                 if (ins->inst_imm == METHOD_ENTRY_IL_OFFSET || ins->inst_imm == METHOD_EXIT_IL_OFFSET)
 295                                 /* Used to implement method entry/exit events */
 296                                         continue;
 297                                 if (ins->inst_offset == SEQ_POINT_NATIVE_OFFSET_DEAD_CODE)
 298                                         continue;
 299
 300                                 if (last != NULL) {
 301                                         /* Link with the previous seq point in the same bb */
 302                                         next [last->backend.size] = g_slist_append (next [last->backend.size], GUINT_TO_POINTER (ins->backend.size));
 303                                 } else {
 304                                         /* Link with the last bb in the previous bblocks */
 305                                         collect_pred_seq_points (bb, ins, next, 0);
 306                                 }
 307
 308                                 last = ins;
 309                         }
 310
 311                         if (bb->last_ins && bb->last_ins->opcode == OP_ENDFINALLY && bb->seq_points) {
 312                                 MonoBasicBlock *bb2;
 313                                 MonoInst *endfinally_seq_point = NULL;
 314
 315                                 /*
 316                                  * The ENDFINALLY branches are not represented in the cfg, so link it with all seq points starting bbs.
 317                                  */
 318                                 l = g_slist_last (bb->seq_points);
 319                                 if (l) {
 320                                         endfinally_seq_point = l->data;
 321
 322                                         for (bb2 = cfg->bb_entry; bb2; bb2 = bb2->next_bb) {
 323                                                 GSList *l = g_slist_last (bb2->seq_points);
 324
 325                                                 if (l) {
 326                                                         MonoInst *ins = l->data;
 327
 328                                                         if (!(ins->inst_imm == METHOD_ENTRY_IL_OFFSET || ins->inst_imm == METHOD_EXIT_IL_OFFSET) && ins != endfinally_seq_point)
 329                                                                 next [endfinally_seq_point->backend.size] = g_slist_append (next [endfinally_seq_point->backend.size], GUINT_TO_POINTER (ins->backend.size));
 330                                                 }
 331                                         }
 332                                 }
 333                         }
 334                 }
 335
 336                 if (cfg->verbose_level > 2) {
 337                         printf ("\nSEQ POINT MAP: \n");
 338
 339                         for (i = 0; i < cfg->seq_points->len; ++i) {
 340                                 SeqPoint *sp = &seq_points [i];
 341                                 GSList *l;
 342
 343                                 if (!next [i])
 344                                         continue;
 345
 346                                 printf ("\tIL0x%x[0x%0x] ->", sp->il_offset, sp->native_offset);
 347                                 for (l = next [i]; l; l = l->next) {
 348                                         int next_index = GPOINTER_TO_UINT (l->data);
 349                                         printf (" IL0x%x", seq_points [next_index].il_offset);
 350                                 }
 351                                 printf ("\n");
 352                         }
 353                 }
 354         }
 355
 356         array = g_byte_array_new ();
 357
 358         { /* Add sequence points to seq_point_info */
 359                 SeqPoint zero_seq_point = {0};
 360                 SeqPoint* last_seq_point = &zero_seq_point;
 361
 362                 for (i = 0; i < cfg->seq_points->len; ++i) {
 363                         SeqPoint *sp = &seq_points [i];
 364                         GSList* next_list = NULL;
 365
 366                         if (has_debug_data)
 367                                 next_list = next[i];
 368
 369                         if (seq_point_info_add_seq_point (array, sp, last_seq_point, next_list, has_debug_data))
 370                                 last_seq_point = sp;
 371
 372                         if (has_debug_data)
 373                                 g_slist_free (next [i]);
 374                 }
 375         }
 376
 377         if (has_debug_data)
 378                 g_free (next);
 379
 380         cfg->seq_point_info = seq_point_info_new (array->len, TRUE, array->data, has_debug_data);
 381
 382         g_byte_array_free (array, TRUE);
 383
 384         // FIXME: dynamic methods
 385         if (!cfg->compile_aot) {
 386                 mono_domain_lock (domain);
 387                 // FIXME: How can the lookup succeed ?
 388                 if (!g_hash_table_lookup (domain_jit_info (domain)->seq_points, cfg->method_to_register))
 389                         g_hash_table_insert (domain_jit_info (domain)->seq_points, cfg->method_to_register, cfg->seq_point_info);
 390                 mono_domain_unlock (domain);
 391         }
 392
 393         g_ptr_array_free (cfg->seq_points, TRUE);
 394         cfg->seq_points = NULL;
 395 }
 396
 397 MonoSeqPointInfo*
 398 get_seq_points (MonoDomain *domain, MonoMethod *method)
 399 {
 400         MonoSeqPointInfo *seq_points;
 401
 402         mono_domain_lock (domain);
 403         seq_points = g_hash_table_lookup (domain_jit_info (domain)->seq_points, method);
 404         if (!seq_points && method->is_inflated) {
 405                 /* generic sharing + aot */
 406                 seq_points = g_hash_table_lookup (domain_jit_info (domain)->seq_points, mono_method_get_declaring_generic_method (method));
 407                 if (!seq_points)
 408                         seq_points = g_hash_table_lookup (domain_jit_info (domain)->seq_points, mini_get_shared_method (method));
 409         }
 410         mono_domain_unlock (domain);
 411
 412         return seq_points;
 413 }
 414
 415 static gboolean
 416 seq_point_find_next_by_native_offset (MonoSeqPointInfo* info, int native_offset, SeqPoint* seq_point)
 417 {
 418         SeqPointIterator it;
 419         seq_point_iterator_init (&it, info);
 420         while (seq_point_iterator_next (&it)) {
 421                 if (it.seq_point.native_offset >= native_offset) {
 422                         memcpy (seq_point, &it.seq_point, sizeof (SeqPoint));
 423                         return TRUE;
 424                 }
 425         }
 426
 427         return FALSE;
 428 }
 429
 430 static gboolean
 431 seq_point_find_prev_by_native_offset (MonoSeqPointInfo* info, int native_offset, SeqPoint* seq_point)
 432 {
 433         SeqPoint prev_seq_point;
 434         gboolean  is_first = TRUE;
 435         SeqPointIterator it;
 436         seq_point_iterator_init (&it, info);
 437         while (seq_point_iterator_next (&it) && it.seq_point.native_offset <= native_offset) {
 438                 memcpy (&prev_seq_point, &it.seq_point, sizeof (SeqPoint));
 439                 is_first = FALSE;
 440         }
 441
 442         if (!is_first && prev_seq_point.native_offset <= native_offset) {
 443                 memcpy (seq_point, &prev_seq_point, sizeof (SeqPoint));
 444                 return TRUE;
 445         }
 446
 447         return FALSE;
 448 }
 449
 450 static gboolean
 451 seq_point_find_by_il_offset (MonoSeqPointInfo* info, int il_offset, SeqPoint* seq_point)
 452 {
 453         SeqPointIterator it;
 454         seq_point_iterator_init (&it, info);
 455         while (seq_point_iterator_next (&it)) {
 456                 if (it.seq_point.il_offset == il_offset) {
 457                         memcpy (seq_point, &it.seq_point, sizeof (SeqPoint));
 458                         return TRUE;
 459                 }
 460         }
 461
 462         return FALSE;
 463 }
 464
 465 /*
 466  * find_next_seq_point_for_native_offset:
 467  *
 468  *   Find the first sequence point after NATIVE_OFFSET.
 469  */
 470 gboolean
 471 find_next_seq_point_for_native_offset (MonoDomain *domain, MonoMethod *method, gint32 native_offset, MonoSeqPointInfo **info, SeqPoint* seq_point)
 472 {
 473         MonoSeqPointInfo *seq_points;
 474
 475         seq_points = get_seq_points (domain, method);
 476         if (!seq_points) {
 477                 if (info)
 478                         *info = NULL;
 479                 return FALSE;
 480         }
 481         if (info)
 482                 *info = seq_points;
 483
 484         return seq_point_find_next_by_native_offset (seq_points, native_offset, seq_point);
 485 }
 486
 487 /*
 488  * find_prev_seq_point_for_native_offset:
 489  *
 490  *   Find the first sequence point before NATIVE_OFFSET.
 491  */
 492 gboolean
 493 find_prev_seq_point_for_native_offset (MonoDomain *domain, MonoMethod *method, gint32 native_offset, MonoSeqPointInfo **info, SeqPoint* seq_point)
 494 {
 495         MonoSeqPointInfo *seq_points;
 496
 497         seq_points = get_seq_points (domain, method);
 498         if (!seq_points) {
 499                 if (info)
 500                         *info = NULL;
 501                 return FALSE;
 502         }
 503         if (info)
 504                 *info = seq_points;
 505
 506         return seq_point_find_prev_by_native_offset (seq_points, native_offset, seq_point);
 507 }
 508
 509 /*
 510  * find_seq_point:
 511  *
 512  *   Find the sequence point corresponding to the IL offset IL_OFFSET, which
 513  * should be the location of a sequence point.
 514  */
 515 gboolean
 516 find_seq_point (MonoDomain *domain, MonoMethod *method, gint32 il_offset, MonoSeqPointInfo **info, SeqPoint *seq_point)
 517 {
 518         MonoSeqPointInfo *seq_points;
 519
 520         seq_points = get_seq_points (domain, method);
 521         if (!seq_points) {
 522                 if (info)
 523                         *info = NULL;
 524                 return FALSE;
 525         }
 526         if (info)
 527                 *info = seq_points;
 528
 529         return seq_point_find_by_il_offset (seq_points, il_offset, seq_point);
 530 }
 531
 532 void
 533 seq_point_init_next (MonoSeqPointInfo* info, SeqPoint sp, SeqPoint* next)
 534 {
 535         int i;
 536         guint8* ptr;
 537         SeqPointIterator it;
 538         GArray* seq_points = g_array_new (FALSE, TRUE, sizeof (SeqPoint));
 539         SeqPointInfoInflated info_inflated = seq_point_info_inflate (info);
 540
 541         g_assert (info_inflated.has_debug_data);
 542
 543         seq_point_iterator_init (&it, info);
 544         while (seq_point_iterator_next (&it))
 545                 g_array_append_vals (seq_points, &it.seq_point, 1);
 546
 547         ptr = info_inflated.data + sp.next_offset;
 548         for (i = 0; i < sp.next_len; i++) {
 549                 int next_index;
 550                 next_index = decode_var_int (ptr, &ptr);
 551                 g_assert (next_index < seq_points->len);
 552                 memcpy (&next[i], seq_points->data + next_index * sizeof (SeqPoint), sizeof (SeqPoint));
 553         }
 554
 555         g_array_free (seq_points, TRUE);
 556 }
 557
 558 gboolean
 559 seq_point_iterator_next (SeqPointIterator* it)
 560 {
 561         if (it->ptr >= it->end)
 562                 return FALSE;
 563
 564         it->ptr += seq_point_read (&it->seq_point, it->ptr, it->begin, it->has_debug_data);
 565
 566         return TRUE;
 567 }
 568
 569 void
 570 seq_point_iterator_init (SeqPointIterator* it, MonoSeqPointInfo* info)
 571 {
 572         SeqPointInfoInflated info_inflated = seq_point_info_inflate (info);
 573         it->ptr = info_inflated.data;
 574         it->begin = info_inflated.data;
 575         it->end = it->begin + info_inflated.len;
 576         it->has_debug_data = info_inflated.has_debug_data;
 577         memset(&it->seq_point, 0, sizeof(SeqPoint));
 578 }
 579
 580 int
 581 seq_point_info_write (MonoSeqPointInfo* info, guint8* buffer)
 582 {
 583         guint8* buffer0 = buffer;
 584         SeqPointInfoInflated info_inflated = seq_point_info_inflate (info);
 585
 586         memcpy (buffer, &info_inflated.has_debug_data, 1);
 587         buffer++;
 588
 589         //Write sequence points
 590         encode_var_int (buffer, &buffer, info_inflated.len);
 591         memcpy (buffer, info_inflated.data, info_inflated.len);
 592         buffer += info_inflated.len;
 593
 594         return buffer - buffer0;
 595 }
 596
 597 int
 598 seq_point_info_read (MonoSeqPointInfo** info, guint8* buffer, gboolean copy)
 599 {
 600         guint8* buffer0 = buffer;
 601         int size;
 602         gboolean has_debug_data;
 603
 604         memcpy (&has_debug_data, buffer, 1);
 605         buffer++;
 606
 607         size = decode_var_int (buffer, &buffer);
 608         (*info) = seq_point_info_new (size, copy, buffer, has_debug_data);
 609         buffer += size;
 610
 611         return buffer - buffer0;
 612 }
 613
 614 /*
 615  * Returns the maximum size of mono_seq_point_info_write.
 616  */
 617 int
 618 seq_point_info_get_write_size (MonoSeqPointInfo* info)
 619 {
 620         SeqPointInfoInflated info_inflated = seq_point_info_inflate (info);
 621
 622         //4 is the maximum size required to store the size of the data.
 623         //1 is the byte used to store has_debug_data.
 624         int size = 4 + 1 + info_inflated.len;
 625
 626         return size;
 627 }
 628
 629 void
 630 bb_deduplicate_op_il_seq_points (MonoCompile *cfg, MonoBasicBlock *bb)
 631 {
 632         MonoInst *ins, *n, *prev;
 633
 634         MONO_BB_FOR_EACH_INS_SAFE (bb, n, ins) {
 635                 if (ins->opcode != OP_IL_SEQ_POINT)
 636                         continue;
 637
 638                 prev = mono_inst_prev (ins, FILTER_NOP);
 639
 640                 if (!prev || ins == prev || prev->opcode != OP_IL_SEQ_POINT)
 641                         continue;
 642
 643                 MONO_REMOVE_INS (bb, prev);
 644         };
 645 }