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