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