mono/jit/emit-x86.c

   1 /*
   2  * emit-x86.c: Support functions for emitting x86 code
   3  *
   4  * Authors:
   5  *   Dietmar Maurer (dietmar@ximian.com)
   6  *   Miguel de Icaza (miguel@ximian.com)
   7  *
   8  * (C) 2001 Ximian, Inc.
   9  */
  10
  11 #include <config.h>
  12 #include <glib.h>
  13
  14 #include <mono/metadata/assembly.h>
  15 #include <mono/metadata/loader.h>
  16 #include <mono/metadata/cil-coff.h>
  17 #include <mono/metadata/tabledefs.h>
  18 #include <mono/metadata/class.h>
  19 #include <mono/metadata/debug-helpers.h>
  20 #include <mono/metadata/mono-endian.h>
  21 #include <mono/arch/x86/x86-codegen.h>
  22 #include <mono/metadata/profiler-private.h>
  23
  24 #include "jit.h"
  25 #include "codegen.h"
  26 #include "debug.h"
  27
  28
  29 //#define DEBUG_REGALLOC
  30 //#define DEBUG_SPILLS
  31
  32 /*
  33  * we may want a x86-specific header or we
  34  * can just declare it extern in x86.brg.
  35  */
  36 int mono_x86_have_cmov = 0;
  37
  38 static int
  39 cpuid (int id, int* p_eax, int* p_ebx, int* p_ecx, int* p_edx)
  40 {
  41         int have_cpuid = 0;
  42         __asm__  __volatile__ (
  43                 "pushfl\n"
  44                 "popl %%eax\n"
  45                 "movl %%eax, %%edx\n"
  46                 "xorl $0x200000, %%eax\n"
  47                 "pushl %%eax\n"
  48                 "popfl\n"
  49                 "pushfl\n"
  50                 "popl %%eax\n"
  51                 "xorl %%edx, %%eax\n"
  52                 "andl $0x200000, %%eax\n"
  53                 "movl %%eax, %0"
  54                 : "=r" (have_cpuid)
  55                 :
  56                 : "%eax", "%edx"
  57         );
  58
  59         if (have_cpuid) {
  60                 __asm__ __volatile__ ("cpuid"
  61                         : "=a" (*p_eax), "=b" (*p_ebx), "=c" (*p_ecx), "=d" (*p_edx)
  62                         : "a" (id));
  63                 return 1;
  64         }
  65         return 0;
  66 }
  67
  68 void
  69 mono_cpu_detect (void) {
  70         int eax, ebx, ecx, edx;
  71
  72         /* Feature Flags function, flags returned in EDX. */
  73         if (cpuid(1, &eax, &ebx, &ecx, &edx)) {
  74                 if (edx & (1U << 15)) {
  75                         mono_x86_have_cmov = 1;
  76                 }
  77         }
  78 }
  79
  80 static void
  81 enter_method (MonoMethod *method, char *ebp)
  82 {
  83         int i, j;
  84         MonoClass *class;
  85         MonoObject *o;
  86
  87         printf ("ENTER: %s.%s::%s\n(", method->klass->name_space,
  88                 method->klass->name, method->name);
  89
  90
  91         if (((int)ebp & 3) != 0) {
  92                 g_error ("unaligned stack detected (%p)", ebp);
  93         }
  94
  95         ebp += 8;
  96
  97         if (ISSTRUCT (method->signature->ret)) {
  98                 int size, align;
  99
 100                 g_assert (!method->signature->ret->byref);
 101
 102                 size = mono_type_stack_size (method->signature->ret, &align);
 103
 104                 printf ("VALUERET:%p, ", *((gpointer *)ebp));
 105                 ebp += sizeof (gpointer);
 106         }
 107
 108         if (method->signature->hasthis) {
 109                 if (method->klass->valuetype) {
 110                         printf ("value:%p, ", *((gpointer *)ebp));
 111                 } else {
 112                         o = *((MonoObject **)ebp);
 113
 114                         g_assert (o);
 115
 116                         class = o->vtable->klass;
 117
 118                         if (class == mono_defaults.string_class) {
 119                                 printf ("this:[STRING:%p:%s], ", o, mono_string_to_utf8 ((MonoString *)o));
 120                         } else {
 121                                 printf ("this:%p[%s.%s], ", o, class->name_space, class->name);
 122                         }
 123                 }
 124                 ebp += sizeof (gpointer);
 125         }
 126
 127         for (i = 0; i < method->signature->param_count; ++i) {
 128                 MonoType *type = method->signature->params [i];
 129                 int size, align;
 130                 size = mono_type_stack_size (type, &align);
 131
 132                 if (type->byref) {
 133                         printf ("[BYREF:%p], ", *((gpointer *)ebp));
 134                 } else switch (type->type) {
 135
 136                 case MONO_TYPE_BOOLEAN:
 137                 case MONO_TYPE_CHAR:
 138                 case MONO_TYPE_I1:
 139                 case MONO_TYPE_U1:
 140                 case MONO_TYPE_I2:
 141                 case MONO_TYPE_U2:
 142                 case MONO_TYPE_I4:
 143                 case MONO_TYPE_U4:
 144                 case MONO_TYPE_I:
 145                 case MONO_TYPE_U:
 146                         printf ("%d, ", *((int *)(ebp)));
 147                         break;
 148                 case MONO_TYPE_STRING: {
 149                         MonoString *s = *((MonoString **)ebp);
 150                         if (s) {
 151                                 g_assert (((MonoObject *)s)->vtable->klass == mono_defaults.string_class);
 152                                 printf ("[STRING:%p:%s], ", s, mono_string_to_utf8 (s));
 153                         } else
 154                                 printf ("[STRING:null], ");
 155                         break;
 156                 }
 157                 case MONO_TYPE_CLASS:
 158                 case MONO_TYPE_OBJECT: {
 159                         o = *((MonoObject **)ebp);
 160                         if (o) {
 161                                 class = o->vtable->klass;
 162
 163                                 if (class == mono_defaults.string_class) {
 164                                         printf ("[STRING:%p:%s], ", o, mono_string_to_utf8 ((MonoString *)o));
 165                                 } else if (class == mono_defaults.int32_class) {
 166                                         printf ("[INT32:%p:%d], ", o, *(gint32 *)((char *)o + sizeof (MonoObject)));
 167                                 } else
 168                                         printf ("[%s.%s:%p], ", class->name_space, class->name, o);
 169                         } else {
 170                                 printf ("%p, ", *((gpointer *)(ebp)));
 171                         }
 172                         break;
 173                 }
 174                 case MONO_TYPE_PTR:
 175                 case MONO_TYPE_FNPTR:
 176                 case MONO_TYPE_ARRAY:
 177                 case MONO_TYPE_SZARRAY:
 178                         printf ("%p, ", *((gpointer *)(ebp)));
 179                         break;
 180                 case MONO_TYPE_I8:
 181                         printf ("%lld, ", *((gint64 *)(ebp)));
 182                         break;
 183                 case MONO_TYPE_R4:
 184                         printf ("%f, ", *((float *)(ebp)));
 185                         break;
 186                 case MONO_TYPE_R8:
 187                         printf ("%f, ", *((double *)(ebp)));
 188                         break;
 189                 case MONO_TYPE_VALUETYPE:
 190                         printf ("[");
 191                         for (j = 0; j < size; j++)
 192                                 printf ("%02x,", *((guint8*)ebp +j));
 193                         printf ("], ");
 194                         break;
 195                 default:
 196                         printf ("XX, ");
 197                 }
 198
 199                 g_assert (align == 4 || align == 8);
 200                 ebp += size + align - 1;
 201                 ebp = (gpointer)((unsigned)ebp & ~(align - 1));
 202         }
 203
 204         printf (")\n");
 205 }
 206
 207 static void
 208 leave_method (MonoMethod *method, int edx, int eax, double test)
 209 {
 210         gint64 l;
 211
 212         printf ("LEAVE: %s.%s::%s ", method->klass->name_space,
 213                 method->klass->name, method->name);
 214
 215         switch (method->signature->ret->type) {
 216         case MONO_TYPE_VOID:
 217                 break;
 218         case MONO_TYPE_BOOLEAN:
 219                 if (eax)
 220                         printf ("TRUE:%d", eax);
 221                 else
 222                         printf ("FALSE");
 223
 224                 break;
 225         case MONO_TYPE_CHAR:
 226         case MONO_TYPE_I1:
 227         case MONO_TYPE_U1:
 228         case MONO_TYPE_I2:
 229         case MONO_TYPE_U2:
 230         case MONO_TYPE_I4:
 231         case MONO_TYPE_U4:
 232         case MONO_TYPE_I:
 233         case MONO_TYPE_U:
 234                 printf ("EAX=%d", eax);
 235                 break;
 236         case MONO_TYPE_STRING: {
 237                 MonoString *s = (MonoString *)eax;
 238
 239                 if (s) {
 240                         g_assert (((MonoObject *)s)->vtable->klass == mono_defaults.string_class);
 241                         printf ("[STRING:%p:%s]", s, mono_string_to_utf8 (s));
 242                 } else
 243                         printf ("[STRING:null], ");
 244                 break;
 245         }
 246         case MONO_TYPE_OBJECT: {
 247                 MonoObject *o = (MonoObject *)eax;
 248
 249                 if (o) {
 250                         if (o->vtable->klass == mono_defaults.boolean_class) {
 251                                 printf ("[BOOLEAN:%p:%d]", o, *((guint8 *)o + sizeof (MonoObject)));
 252                         } else if  (o->vtable->klass == mono_defaults.int32_class) {
 253                                 printf ("[INT32:%p:%d]", o, *((gint32 *)((char *)o + sizeof (MonoObject))));
 254                         } else
 255                                 printf ("[%s.%s:%p]", o->vtable->klass->name_space, o->vtable->klass->name, o);
 256                 } else
 257                         printf ("[OBJECT:%p]", o);
 258
 259                 break;
 260         }
 261         case MONO_TYPE_CLASS:
 262         case MONO_TYPE_PTR:
 263         case MONO_TYPE_FNPTR:
 264         case MONO_TYPE_ARRAY:
 265         case MONO_TYPE_SZARRAY:
 266                 printf ("EAX=%p", (gpointer)eax);
 267                 break;
 268         case MONO_TYPE_I8:
 269                 *((gint32 *)&l) = eax;
 270                 *((gint32 *)&l + 1) = edx;
 271                 printf ("EAX/EDX=%lld", l);
 272                 break;
 273         case MONO_TYPE_R8:
 274                 printf ("FP=%f\n", test);
 275                 break;
 276         default:
 277                 printf ("(unknown return type)");
 278         }
 279
 280         printf ("\n");
 281 }
 282
 283 /**
 284  * arch_emit_prologue:
 285  * @cfg: pointer to status information
 286  *
 287  * Emits the function prolog.
 288  */
 289 static void
 290 arch_emit_prologue (MonoFlowGraph *cfg)
 291 {
 292         MonoMethod *method = cfg->method;
 293         MonoMethodHeader *header = ((MonoMethodNormal *)method)->header;
 294         int i, j;
 295
 296         x86_push_reg (cfg->code, X86_EBP);
 297         x86_mov_reg_reg (cfg->code, X86_EBP, X86_ESP, 4);
 298
 299         if (cfg->locals_size)
 300                 x86_alu_reg_imm (cfg->code, X86_SUB, X86_ESP, cfg->locals_size);
 301
 302         if (mono_regset_reg_used (cfg->rs, X86_EBX))
 303                 x86_push_reg (cfg->code, X86_EBX);
 304
 305         if (mono_regset_reg_used (cfg->rs, X86_EDI))
 306                 x86_push_reg (cfg->code, X86_EDI);
 307
 308         if (mono_regset_reg_used (cfg->rs, X86_ESI))
 309                 x86_push_reg (cfg->code, X86_ESI);
 310
 311         if (mono_jit_trace_calls) {
 312                 x86_push_reg (cfg->code, X86_EBP);
 313                 x86_push_imm (cfg->code, cfg->method);
 314                 x86_mov_reg_imm (cfg->code, X86_EAX, enter_method);
 315                 x86_call_reg (cfg->code, X86_EAX);
 316                 x86_alu_reg_imm (cfg->code, X86_ADD, X86_ESP, 8);
 317         }
 318         if (mono_jit_profile) {
 319                 x86_push_imm (cfg->code, cfg->method);
 320                 x86_mov_reg_imm (cfg->code, X86_EAX, mono_profiler_method_enter);
 321                 x86_call_reg (cfg->code, X86_EAX);
 322                 x86_alu_reg_imm (cfg->code, X86_ADD, X86_ESP, 4);
 323         }
 324
 325         /* initialize local vars */
 326         if (header->num_locals) {
 327
 328                 if (header->init_locals) {
 329                         int offset = g_array_index (cfg->varinfo, MonoVarInfo,
 330                                                     cfg->locals_start_index + header->num_locals - 1).offset;
 331                         int size = - offset;
 332
 333                         if (size == 1 || size == 2 || size == 4) {
 334                                 x86_mov_membase_imm (cfg->code, X86_EBP, offset, 0, size);
 335                                 return;
 336                         }
 337
 338                         i = size / 4;
 339                         j = size % 4;
 340
 341                         if (i) {
 342                                 if (!mono_regset_reg_used (cfg->rs, X86_EDI))
 343                                         x86_push_reg (cfg->code, X86_EDI);
 344                                 x86_lea_membase (cfg->code, X86_EDI, X86_EBP, offset);
 345                                 x86_alu_reg_reg (cfg->code, X86_XOR, X86_EAX, X86_EAX);
 346                                 x86_mov_reg_imm (cfg->code, X86_ECX, i);
 347                                 x86_cld (cfg->code);
 348                                 x86_prefix (cfg->code, X86_REP_PREFIX);
 349                                 x86_stosl (cfg->code);
 350                                 for (i = 0; i < j; i++)
 351                                         x86_stosb (cfg->code);
 352                                 if (!mono_regset_reg_used (cfg->rs, X86_EDI))
 353                                         x86_pop_reg (cfg->code, X86_EDI);
 354                         } else {
 355
 356                                 g_assert (j == 3);
 357                                 x86_mov_membase_imm (cfg->code, X86_EBP, offset, 0, 2);
 358                                 x86_mov_membase_imm (cfg->code, X86_EBP, offset + 2, 0, 1);
 359                         }
 360
 361                 } else {
 362
 363                         /* we always need to initialize object pointers */
 364
 365                         for (i = 0; i < header->num_locals; ++i) {
 366                                 MonoType *t = header->locals [i];
 367                                 int offset = g_array_index (cfg->varinfo, MonoVarInfo, cfg->locals_start_index + i).offset;
 368
 369                                 if (t->byref) {
 370                                         x86_mov_membase_imm (cfg->code, X86_EBP, offset, 0, 4);
 371                                         continue;
 372                                 }
 373
 374                                 switch (t->type) {
 375                                 case MONO_TYPE_STRING:
 376                                 case MONO_TYPE_CLASS:
 377                                 case MONO_TYPE_ARRAY:
 378                                 case MONO_TYPE_SZARRAY:
 379                                 case MONO_TYPE_OBJECT:
 380                                         x86_mov_membase_imm (cfg->code, X86_EBP, offset, 0, 4);
 381                                         break;
 382                                 }
 383
 384                         }
 385                 }
 386         }
 387 }
 388
 389 /**
 390  * arch_emit_epilogue:
 391  * @cfg: pointer to status information
 392  *
 393  * Emits the function epilog.
 394  */
 395 static void
 396 arch_emit_epilogue (MonoFlowGraph *cfg)
 397 {
 398         /*
 399          * note: with trace and profiling the value on the FP stack may get clobbered.
 400          */
 401         if (mono_jit_trace_calls) {
 402                 x86_fld_reg (cfg->code, 0);
 403                 x86_alu_reg_imm (cfg->code, X86_SUB, X86_ESP, 8);
 404                 x86_fst_membase (cfg->code, X86_ESP, 0, TRUE, TRUE);
 405                 x86_push_reg (cfg->code, X86_EAX);
 406                 x86_push_reg (cfg->code, X86_EDX);
 407                 x86_push_imm (cfg->code, cfg->method);
 408                 x86_mov_reg_imm (cfg->code, X86_EAX, leave_method);
 409                 x86_call_reg (cfg->code, X86_EAX);
 410                 x86_alu_reg_imm (cfg->code, X86_ADD, X86_ESP, 4);
 411                 x86_pop_reg (cfg->code, X86_EDX);
 412                 x86_pop_reg (cfg->code, X86_EAX);
 413                 x86_alu_reg_imm (cfg->code, X86_ADD, X86_ESP, 8);
 414         }
 415         if (mono_jit_profile) {
 416                 x86_push_reg (cfg->code, X86_EAX);
 417                 x86_push_reg (cfg->code, X86_EDX);
 418                 x86_push_imm (cfg->code, cfg->method);
 419                 x86_mov_reg_imm (cfg->code, X86_EAX, mono_profiler_method_leave);
 420                 x86_call_reg (cfg->code, X86_EAX);
 421                 x86_alu_reg_imm (cfg->code, X86_ADD, X86_ESP, 4);
 422                 x86_pop_reg (cfg->code, X86_EDX);
 423                 x86_pop_reg (cfg->code, X86_EAX);
 424         }
 425
 426         if (mono_regset_reg_used (cfg->rs, X86_ESI))
 427                 x86_pop_reg (cfg->code, X86_ESI);
 428
 429         if (mono_regset_reg_used (cfg->rs, X86_EDI))
 430                 x86_pop_reg (cfg->code, X86_EDI);
 431
 432         if (mono_regset_reg_used (cfg->rs, X86_EBX))
 433                 x86_pop_reg (cfg->code, X86_EBX);
 434
 435         x86_leave (cfg->code);
 436         x86_ret (cfg->code);
 437 }
 438
 439 static void
 440 mono_label_cfg (MonoFlowGraph *cfg)
 441 {
 442         int i, j;
 443
 444         for (i = 0; i < cfg->block_count; i++) {
 445                 GPtrArray *forest = cfg->bblocks [i].forest;
 446                 int top;
 447
 448                 if (!cfg->bblocks [i].reached) /* unreachable code */
 449                         continue;
 450
 451                 top = forest->len;
 452
 453                 for (j = 0; j < top; j++) {
 454                         MBTree *t1 = (MBTree *) g_ptr_array_index (forest, j);
 455                         MBState *mbstate;
 456
 457                         mbstate =  mono_burg_label (t1, cfg);
 458
 459                         if (!mbstate) {
 460                                 cfg->invalid = 1;
 461                                 if (mono_debug_handle)
 462                                         return;
 463                                 g_warning ("tree does not match");
 464                                 mono_print_ctree (t1); printf ("\n\n");
 465
 466                                 mono_print_forest (forest);
 467                                 g_assert_not_reached ();
 468                         }
 469                 }
 470         }
 471 }
 472
 473 static gboolean
 474 tree_allocate_regs (MBTree *tree, int goal, MonoRegSet *rs, guint8 exclude_mask, int *spillcount)
 475 {
 476         MBTree *kids[10];
 477         int ern = mono_burg_rule (tree->state, goal);
 478         const guint16 *nts = mono_burg_nts [ern];
 479         guint8 left_exclude_mask = 0, right_exclude_mask = 0;
 480         int i;
 481
 482 #ifdef DEBUG_REGALLOC
 483         printf ("tree_allocate_regs start %d %08x %d %d\n",  tree->op, rs->free_mask, goal,
 484                 (nts [0] && kids [0] == tree));
 485 #endif
 486
 487         mono_burg_kids (tree, ern, kids);
 488
 489         switch (tree->op) {
 490         case MB_TERM_SHL:
 491         case MB_TERM_SHR:
 492         case MB_TERM_SHR_UN:
 493                 exclude_mask |= (1 << X86_ECX);
 494                 left_exclude_mask |= (1 << X86_ECX);
 495                 break;
 496         case MB_TERM_MUL:
 497         case MB_TERM_MUL_OVF:
 498         case MB_TERM_MUL_OVF_UN:
 499         case MB_TERM_DIV:
 500         case MB_TERM_DIV_UN:
 501         case MB_TERM_REM:
 502         case MB_TERM_REM_UN:
 503                 if (goal == MB_NTERM_reg) {
 504                         left_exclude_mask |= (1 << X86_EDX);
 505                         right_exclude_mask |= (1 << X86_EDX) | (1 << X86_EAX);
 506                 }
 507                 break;
 508         default:
 509                 break;
 510         }
 511
 512         if (nts [0] && kids [0] == tree) {
 513                 /* chain rule */
 514                 if (!tree_allocate_regs (kids [0], nts [0], rs, exclude_mask, spillcount))
 515                         return FALSE;
 516                 /* special case reg: coni4 */
 517                 if (goal == MB_NTERM_reg) {
 518                         if (tree->reg1 == -1)
 519                                 tree->reg1 = mono_regset_alloc_reg (rs, -1, exclude_mask);
 520                         if (tree->reg1 == -1)
 521                                 return FALSE;
 522                 }
 523                 return TRUE;
 524         }
 525
 526         if (tree->spilled) {
 527                 if (tree->reg1 >= 0)
 528                         (*spillcount)--;
 529                 if (tree->reg2 >= 0)
 530                         (*spillcount)--;
 531                 if (tree->reg3 >= 0)
 532                         (*spillcount)--;
 533         }
 534
 535         tree->reg1 = -1;
 536         tree->reg2 = -1;
 537         tree->reg3 = -1;
 538
 539         tree->spilled = 0;
 540
 541         if (nts [0]) {
 542                 if (nts [1]) { /* two kids */
 543                         MonoRegSet saved_rs;
 544                         if (nts [2]) /* we cant handle tree kids */
 545                                 g_assert_not_reached ();
 546
 547                         if (!tree_allocate_regs (kids [0], nts [0], rs, left_exclude_mask, spillcount))
 548                                 return FALSE;
 549
 550                         saved_rs = *rs;
 551
 552                         if (!tree_allocate_regs (kids [1], nts [1], rs, right_exclude_mask, spillcount)) {
 553
 554 #ifdef DEBUG_REGALLOC
 555                                 printf ("tree_allocate_regs try 1 failed %d %d %d %d\n",
 556                                         nts [1], kids [1]->reg1,
 557                                         kids [1]->reg2,kids [1]->reg3);
 558 #endif
 559                                 *rs = saved_rs;
 560
 561                                 if (kids [0]->reg1 != -1) {
 562                                         right_exclude_mask |= 1 << kids [0]->reg1;
 563                                         (*spillcount)++;
 564                                 }
 565                                 if (kids [0]->reg2 != -1) {
 566                                         right_exclude_mask |= 1 << kids [0]->reg2;
 567                                         (*spillcount)++;
 568                                 }
 569                                 if (kids [0]->reg3 != -1) {
 570                                         right_exclude_mask |= 1 << kids [0]->reg3;
 571                                         (*spillcount)++;
 572                                 }
 573
 574                                 mono_regset_free_reg (rs, kids [0]->reg1);
 575                                 mono_regset_free_reg (rs, kids [0]->reg2);
 576                                 mono_regset_free_reg (rs, kids [0]->reg3);
 577
 578                                 kids [0]->spilled = 1;
 579
 580                                 if (!tree_allocate_regs (kids [1], nts [1], rs, right_exclude_mask, spillcount)) {
 581 #ifdef DEBUG_REGALLOC
 582                                         printf ("tree_allocate_regs try 2 failed\n");
 583 #endif
 584                                         return FALSE;
 585                                 }
 586 #ifdef DEBUG_REGALLOC
 587                                 printf ("tree_allocate_regs try 2 succesfull\n");
 588 #endif
 589                         }
 590
 591                 } else { /* one kid */
 592                         if (!tree_allocate_regs (kids [0], nts [0], rs, left_exclude_mask, spillcount))
 593                                 return FALSE;
 594                 }
 595         }
 596
 597
 598         for (i = 0; nts [i]; i++) {
 599                 mono_regset_free_reg (rs, kids [i]->reg1);
 600                 mono_regset_free_reg (rs, kids [i]->reg2);
 601                 mono_regset_free_reg (rs, kids [i]->reg3);
 602         }
 603
 604         tree->emit = mono_burg_func [ern];
 605
 606         switch (tree->op) {
 607         case MB_TERM_CALL_I4:
 608         case MB_TERM_CALL_I8:
 609         case MB_TERM_CALL_R8:
 610         // case MB_TERM_CALL_VOID :
 611                 if ((tree->reg1 = mono_regset_alloc_reg (rs, X86_EAX, exclude_mask)) == -1)
 612                         return FALSE;
 613                 if ((tree->reg2 = mono_regset_alloc_reg (rs, X86_EDX, exclude_mask)) == -1)
 614                         return FALSE;
 615                 if ((tree->reg3 = mono_regset_alloc_reg (rs, X86_ECX, exclude_mask)) == -1)
 616                         return FALSE;
 617                 return TRUE;
 618         }
 619
 620         switch (goal) {
 621         case MB_NTERM_reg:
 622                 switch (tree->op) {
 623                 case MB_TERM_MUL_OVF_UN:
 624                 case MB_TERM_DIV:
 625                 case MB_TERM_DIV_UN:
 626                 case MB_TERM_REM:
 627                 case MB_TERM_REM_UN:
 628                         if ((tree->reg1 = mono_regset_alloc_reg (rs, X86_EAX, exclude_mask)) == -1)
 629                                 return FALSE;
 630                         if ((tree->reg2 = mono_regset_alloc_reg (rs, X86_EDX, exclude_mask)) == -1)
 631                                 return FALSE;
 632                         break;
 633                 default:
 634                         if ((tree->reg1 = mono_regset_alloc_reg (rs, -1, exclude_mask)) == -1)
 635                                 return FALSE;
 636                 }
 637                 break;
 638
 639         case MB_NTERM_lreg:
 640                 switch (tree->op) {
 641                 case MB_TERM_MUL:
 642                 case MB_TERM_MUL_OVF:
 643                 case MB_TERM_MUL_OVF_UN:
 644                 case MB_TERM_DIV:
 645                 case MB_TERM_DIV_UN:
 646                 case MB_TERM_REM:
 647                 case MB_TERM_REM_UN:
 648                         if ((tree->reg1 = mono_regset_alloc_reg (rs, X86_EAX, exclude_mask)) == -1)
 649                                 return FALSE;
 650                         if ((tree->reg2 = mono_regset_alloc_reg (rs, X86_EDX, exclude_mask)) == -1)
 651                                 return FALSE;
 652                         break;
 653                 default:
 654                         if ((tree->reg1 = mono_regset_alloc_reg (rs, -1, exclude_mask)) == -1)
 655                                 return FALSE;
 656                         if ((tree->reg2 = mono_regset_alloc_reg (rs, -1, exclude_mask)) == -1)
 657                                 return FALSE;
 658                 }
 659                 break;
 660
 661         case MB_NTERM_freg:
 662                 /* fixme: allocate floating point registers */
 663                 break;
 664
 665         case MB_NTERM_addr:
 666                 if (tree->op == MB_TERM_ADD) {
 667                         if ((tree->reg1 = mono_regset_alloc_reg (rs, tree->left->reg1, exclude_mask)) == -1)
 668                                 return FALSE;
 669                         if ((tree->reg2 = mono_regset_alloc_reg (rs, tree->right->reg1, exclude_mask)) == -1)
 670                                 return FALSE;
 671                 }
 672                 break;
 673
 674         case MB_NTERM_base:
 675                 if (tree->op == MB_TERM_ADD) {
 676                         if ((tree->reg1 = mono_regset_alloc_reg (rs, tree->left->reg1, exclude_mask)) == -1)
 677                                 return FALSE;
 678                 }
 679                 break;
 680
 681         case MB_NTERM_index:
 682                 if (tree->op == MB_TERM_SHL ||
 683                     tree->op == MB_TERM_MUL) {
 684                         if ((tree->reg1 = mono_regset_alloc_reg (rs, tree->left->reg1, exclude_mask)) == -1)
 685                                 return FALSE;
 686                 }
 687                 break;
 688
 689         default:
 690                 /* do nothing */
 691         }
 692
 693 #ifdef DEBUG_REGALLOC
 694         printf ("tree_allocate_regs end %d %08x\n",  tree->op, rs->free_mask);
 695 #endif
 696         return TRUE;
 697 }
 698
 699 static void
 700 arch_allocate_regs (MonoFlowGraph *cfg)
 701 {
 702         int i, j, max_spillcount = 0;
 703
 704         for (i = 0; i < cfg->block_count; i++) {
 705                 GPtrArray *forest = cfg->bblocks [i].forest;
 706                 int top;
 707
 708                 if (!cfg->bblocks [i].reached) /* unreachable code */
 709                         continue;
 710
 711                 top = forest->len;
 712
 713                 for (j = 0; j < top; j++) {
 714                         MBTree *t1 = (MBTree *) g_ptr_array_index (forest, j);
 715                         int spillcount = 0;
 716 #ifdef DEBUG_REGALLOC
 717                         printf ("arch_allocate_regs start %d:%d %08x\n", i, j, cfg->rs->free_mask);
 718 #endif
 719                         if (!tree_allocate_regs (t1, 1, cfg->rs, 0, &spillcount)) {
 720                                 mono_print_ctree (t1);
 721                                 g_error ("register allocation failed");
 722                         }
 723
 724                         max_spillcount = MAX (max_spillcount, spillcount);
 725
 726 #ifdef DEBUG_REGALLOC
 727                         printf ("arch_allocate_regs end %d:%d %08x\n", i, j, cfg->rs->free_mask);
 728 #endif
 729                         g_assert (cfg->rs->free_mask == 0xffffffff);
 730                 }
 731         }
 732
 733         /* allocate space for spilled regs */
 734
 735         cfg->spillvars = mono_mempool_alloc0 (cfg->mp, sizeof (gint) *  max_spillcount);
 736         cfg->spillcount = max_spillcount;
 737
 738         for (i = 0; i < max_spillcount; i++) {
 739                 int spillvar;
 740                 spillvar = arch_allocate_var (cfg, sizeof (gpointer), sizeof (gpointer),
 741                                               MONO_TEMPVAR, VAL_I32);
 742                 cfg->spillvars [i] = VAROFFSET (cfg, spillvar);
 743         }
 744 }
 745
 746 static void
 747 tree_emit (int goal, MonoFlowGraph *cfg, MBTree *tree, int *spillcount)
 748 {
 749         MBTree *kids[10];
 750         int ern = mono_burg_rule (tree->state, goal);
 751         const guint16 *nts = mono_burg_nts [ern];
 752         MBEmitFunc emit;
 753         int offset;
 754
 755         mono_burg_kids (tree, ern, kids);
 756
 757         if (nts [0]) {
 758                 if (nts [1]) {
 759                         int spilloffset1, spilloffset2, spilloffset3;
 760
 761                         if (nts [2])
 762                                 g_assert_not_reached ();
 763
 764                         tree_emit (nts [0], cfg, kids [0], spillcount);
 765
 766                         if (kids [0]->spilled) {
 767 #ifdef DEBUG_SPILLS
 768                                 printf ("SPILL_REGS %d %03x %s.%s:%s\n",
 769                                         nts [0], cfg->code - cfg->start,
 770                                         cfg->method->klass->name_space,
 771                                         cfg->method->klass->name, cfg->method->name);
 772
 773                                 mono_print_ctree (kids [0]);printf ("\n\n");
 774 #endif
 775                                 spilloffset1 = 0;
 776                                 spilloffset2 = 0;
 777                                 spilloffset3 = 0;
 778
 779                                 if (kids [0]->reg1 != -1) {
 780                                         spilloffset1 = cfg->spillvars [(*spillcount)++];
 781                                         x86_mov_membase_reg (cfg->code, X86_EBP, spilloffset1,
 782                                                              kids [0]->reg1, 4);
 783                                 }
 784                                 if (kids [0]->reg2 != -1) {
 785                                         spilloffset2 = cfg->spillvars [(*spillcount)++];
 786                                         x86_mov_membase_reg (cfg->code, X86_EBP, spilloffset2,
 787                                                              kids [0]->reg2, 4);
 788                                 }
 789                                 if (kids [0]->reg3 != -1) {
 790                                         spilloffset3 = cfg->spillvars [(*spillcount)++];
 791                                         x86_mov_membase_reg (cfg->code, X86_EBP, spilloffset3,
 792                                                              kids [0]->reg3, 4);
 793                                 }
 794                         }
 795
 796                         tree_emit (nts [1], cfg, kids [1], spillcount);
 797
 798                         if (kids [0]->spilled) {
 799
 800 #ifdef DEBUG_SPILLS
 801                                 printf ("RELOAD_REGS %03x %s.%s:%s\n",
 802                                         cfg->code - cfg->start,
 803                                         cfg->method->klass->name_space,
 804                                         cfg->method->klass->name, cfg->method->name);
 805 #endif
 806
 807                                 if (kids [0]->reg3 != -1)
 808                                         x86_mov_reg_membase (cfg->code, kids [0]->reg3, X86_EBP,
 809                                                              spilloffset3, 4);
 810                                 if (kids [0]->reg2 != -1)
 811                                         x86_mov_reg_membase (cfg->code, kids [0]->reg2, X86_EBP,
 812                                                              spilloffset2, 4);
 813                                 if (kids [0]->reg1 != -1)
 814                                         x86_mov_reg_membase (cfg->code, kids [0]->reg1, X86_EBP,
 815                                                              spilloffset1, 4);
 816                         }
 817                 } else {
 818                         tree_emit (nts [0], cfg, kids [0], spillcount);
 819                 }
 820         }
 821
 822         g_assert ((*spillcount) <= cfg->spillcount);
 823
 824         tree->addr = offset = cfg->code - cfg->start;
 825
 826         // we assume an instruction uses a maximum of 128 bytes
 827         if ((cfg->code_size - offset) <= 128) {
 828                 int add = MIN (cfg->code_size, 128);
 829                 cfg->code_size += add;
 830                 mono_jit_stats.code_reallocs++;
 831                 cfg->start = g_realloc (cfg->start, cfg->code_size);
 832                 g_assert (cfg->start);
 833                 cfg->code = cfg->start + offset;
 834         }
 835
 836         if ((emit = mono_burg_func [ern]))
 837                 emit (tree, cfg);
 838
 839         g_assert ((cfg->code - cfg->start) < cfg->code_size);
 840 }
 841
 842 static void
 843 mono_emit_cfg (MonoFlowGraph *cfg)
 844 {
 845         int i, j, spillcount;
 846
 847         for (i = 0; i < cfg->block_count; i++) {
 848                 MonoBBlock *bb = &cfg->bblocks [i];
 849                 GPtrArray *forest = bb->forest;
 850                 int top;
 851
 852                 if (!bb->reached) /* unreachable code */
 853                         continue;
 854
 855                 top = forest->len;
 856
 857                 bb->addr = cfg->code - cfg->start;
 858
 859                 for (j = 0; j < top; j++) {
 860                         MBTree *t1 = (MBTree *) g_ptr_array_index (forest, j);
 861
 862                         spillcount = 0;
 863                         tree_emit (1, cfg, t1, &spillcount);
 864                 }
 865         }
 866
 867         cfg->epilog = cfg->code - cfg->start;
 868 }
 869
 870 static void
 871 mono_compute_branches (MonoFlowGraph *cfg)
 872 {
 873         MonoJumpInfo *ji;
 874         guint8 *end;
 875         int i, j;
 876
 877         end = cfg->code;
 878
 879         for (j = 0; j < cfg->block_count; j++) {
 880                 MonoBBlock *bb = &cfg->bblocks [j];
 881                 GPtrArray *forest = bb->forest;
 882                 int top;
 883
 884                 if (!bb->reached) /* unreachable code */
 885                         continue;
 886
 887                 top = forest->len;
 888
 889                 for (i = 0; i < top; i++) {
 890                         MBTree *t1 = (MBTree *) g_ptr_array_index (forest, i);
 891
 892                         if (t1->op == MB_TERM_SWITCH) {
 893                                 MonoBBlock **jt = (MonoBBlock **)t1->data.p;
 894                                 guint32 *rt = (guint32 *)t1->data.p;
 895                                 int m = *((guint32 *)t1->data.p) + 1;
 896                                 int k;
 897
 898                                 for (k = 1; k <= m; k++)
 899                                         rt [k] = (int)(jt [k]->addr + cfg->start);
 900
 901                                 /* emit the switch instruction again to update addresses */
 902                                 cfg->code = cfg->start + t1->addr;
 903                                 ((MBEmitFunc)t1->emit) (t1, cfg);
 904                         }
 905                 }
 906         }
 907
 908         cfg->code = end;
 909
 910         for (ji = cfg->jump_info; ji; ji = ji->next) {
 911                 gpointer *ip = GUINT_TO_POINTER (GPOINTER_TO_UINT (ji->ip) + cfg->start);
 912                 char *target;
 913
 914                 switch (ji->type) {
 915                 case MONO_JUMP_INFO_BB:
 916                         target = ji->data.bb->addr + cfg->start;
 917                         *ip = target - GPOINTER_TO_UINT(ip) - 4;
 918                         break;
 919                 case MONO_JUMP_INFO_ABS:
 920                         target = ji->data.target;
 921                         *ip = target - GPOINTER_TO_UINT(ip) - 4;
 922                         break;
 923                 case MONO_JUMP_INFO_EPILOG:
 924                         target = cfg->epilog + cfg->start;
 925                         *ip = target - GPOINTER_TO_UINT(ip) - 4;
 926                         break;
 927                 case MONO_JUMP_INFO_IP:
 928                         *ip = ip;
 929                         break;
 930                 default:
 931                         g_assert_not_reached ();
 932                 }
 933         }
 934 }
 935
 936 void
 937 mono_add_jump_info (MonoFlowGraph *cfg, gpointer ip, MonoJumpInfoType type, gpointer target)
 938 {
 939         MonoJumpInfo *ji = mono_mempool_alloc (cfg->mp, sizeof (MonoJumpInfo));
 940
 941         ji->type = type;
 942         ji->ip = GUINT_TO_POINTER (GPOINTER_TO_UINT (ip) - GPOINTER_TO_UINT (cfg->start));
 943         ji->data.target = target;
 944         ji->next = cfg->jump_info;
 945
 946         cfg->jump_info = ji;
 947 }
 948
 949 static int
 950 match_debug_method (MonoMethod* method)
 951 {
 952         GList *tmp = mono_debug_methods;
 953
 954         for (; tmp; tmp = tmp->next) {
 955                 if (mono_method_desc_full_match (tmp->data, method))
 956                         return 1;
 957         }
 958         return 0;
 959 }
 960
 961 /**
 962  * arch_compile_method:
 963  * @method: pointer to the method info
 964  *
 965  * JIT compilation of a single method.
 966  *
 967  * Returns: a pointer to the newly created code.
 968  */
 969 gpointer
 970 arch_compile_method (MonoMethod *method)
 971 {
 972         MonoDomain *target_domain, *domain = mono_domain_get ();
 973         MonoJitInfo *ji;
 974         guint8 *addr;
 975         GHashTable *jit_code_hash;
 976
 977         if ((method->iflags & METHOD_IMPL_ATTRIBUTE_INTERNAL_CALL) ||
 978             (method->flags & METHOD_ATTRIBUTE_PINVOKE_IMPL)) {
 979                 if (!method->info)
 980                         method->info = arch_create_native_wrapper (method);
 981                 return method->info;
 982         }
 983
 984         if (mono_jit_share_code)
 985                 target_domain = mono_root_domain;
 986         else
 987                 target_domain = domain;
 988
 989         jit_code_hash = target_domain->jit_code_hash;
 990
 991         if ((addr = g_hash_table_lookup (jit_code_hash, method))) {
 992                 mono_jit_stats.methods_lookups++;
 993                 return addr;
 994         }
 995
 996         mono_jit_stats.methods_compiled++;
 997
 998         if (mono_jit_trace_calls || mono_jit_dump_asm || mono_jit_dump_forest) {
 999                 printf ("Start JIT compilation of %s.%s:%s\n", method->klass->name_space,
1000                         method->klass->name, method->name);
1001         }
1002
1003         if (method->iflags & METHOD_IMPL_ATTRIBUTE_RUNTIME) {
1004                 const char *name = method->name;
1005                 guint8 *code;
1006                 gboolean delegate = FALSE;
1007
1008                 if (method->klass->parent == mono_defaults.multicastdelegate_class)
1009                         delegate = TRUE;
1010
1011                 if (delegate && *name == '.' && (strcmp (name, ".ctor") == 0)) {
1012                         addr = (gpointer)mono_delegate_ctor;
1013                 } else if (delegate && *name == 'I' && (strcmp (name, "Invoke") == 0)) {
1014                         int size;
1015
1016                         addr = arch_get_delegate_invoke (method, &size);
1017
1018                         if (mono_jit_dump_asm) {
1019                                 char *id = g_strdup_printf ("%s.%s_%s", method->klass->name_space,
1020                                                             method->klass->name, method->name);
1021                                 mono_disassemble_code (addr, size, id);
1022                                 g_free (id);
1023                         }
1024                 } else if (delegate && *name == 'B' && (strcmp (name, "BeginInvoke") == 0)) {
1025                         code = addr = g_malloc (32);
1026                         x86_push_imm (code, method);
1027                         x86_call_code (code, arch_begin_invoke);
1028                         x86_alu_reg_imm (code, X86_ADD, X86_ESP, 4);
1029                         x86_ret (code);
1030                         g_assert ((code - addr) <= 32);
1031                 } else if (delegate && *name == 'E' && (strcmp (name, "EndInvoke") == 0)) {
1032                         /* this can raise exceptions, so we need a wrapper to save/restore LMF */
1033                         method->addr = (gpointer)arch_end_invoke;
1034                         addr = arch_create_native_wrapper (method);
1035                 } else {
1036                         mono_profiler_method_end_jit (method, MONO_PROFILE_FAILED);
1037                         if (mono_debug_handle)
1038                                 return NULL;
1039
1040                         g_error ("Don't know how to exec runtime method %s.%s::%s",
1041                                  method->klass->name_space, method->klass->name, method->name);
1042                 }
1043
1044         } else {
1045                 MonoMethodHeader *header = ((MonoMethodNormal *)method)->header;
1046                 MonoFlowGraph *cfg;
1047                 MonoMemPool *mp;
1048                 gulong code_size_ratio;
1049
1050                 mono_profiler_method_jit (method);
1051
1052                 ji = mono_mempool_alloc0 (target_domain->mp, sizeof (MonoJitInfo));
1053
1054                 mp = mono_mempool_new ();
1055
1056                 cfg = mono_cfg_new (method, mp);
1057
1058                 mono_analyze_flow (cfg);
1059                 if (cfg->invalid) {
1060                         mono_profiler_method_end_jit (method, MONO_PROFILE_FAILED);
1061                         return NULL;
1062                 }
1063
1064                 mono_analyze_stack (cfg);
1065                 if (cfg->invalid) {
1066                         mono_profiler_method_end_jit (method, MONO_PROFILE_FAILED);
1067                         return NULL;
1068                 }
1069
1070                 cfg->rs = mono_regset_new (X86_NREG);
1071                 mono_regset_reserve_reg (cfg->rs, X86_ESP);
1072                 mono_regset_reserve_reg (cfg->rs, X86_EBP);
1073
1074                 /* we can use this regs for global register allocation */
1075                 mono_regset_reserve_reg (cfg->rs, X86_EBX);
1076                 mono_regset_reserve_reg (cfg->rs, X86_ESI);
1077
1078                 cfg->code_size = MAX (header->code_size * 5, 256);
1079                 cfg->start = cfg->code = g_malloc (cfg->code_size);
1080
1081                 mono_debug_last_breakpoint_address = cfg->code;
1082
1083                 if (match_debug_method (method) || mono_debug_insert_breakpoint)
1084                         x86_breakpoint (cfg->code);
1085                 else if (mono_debug_handle)
1086                         x86_nop (cfg->code);
1087
1088                 if (mono_debug_insert_breakpoint > 0)
1089                         mono_debug_insert_breakpoint--;
1090
1091                 if (mono_jit_dump_forest) {
1092                         int i;
1093                         printf ("FOREST %s.%s:%s\n", method->klass->name_space,
1094                                 method->klass->name, method->name);
1095                         for (i = 0; i < cfg->block_count; i++) {
1096                                 printf ("BLOCK %d:\n", i);
1097                                 mono_print_forest (cfg->bblocks [i].forest);
1098                         }
1099                 }
1100
1101                 mono_label_cfg (cfg);
1102                 if (cfg->invalid) {
1103                         mono_profiler_method_end_jit (method, MONO_PROFILE_FAILED);
1104                         return NULL;
1105                 }
1106
1107                 arch_allocate_regs (cfg);
1108
1109                 /* align to 8 byte boundary */
1110                 cfg->locals_size += 7;
1111                 cfg->locals_size &= ~7;
1112
1113                 arch_emit_prologue (cfg);
1114                 cfg->prologue_end = cfg->code - cfg->start;
1115                 mono_emit_cfg (cfg);
1116                 arch_emit_epilogue (cfg);
1117                 cfg->epilogue_end = cfg->code - cfg->start;
1118
1119                 addr = cfg->start;
1120
1121                 mono_jit_stats.allocated_code_size += cfg->code_size;
1122
1123                 code_size_ratio = cfg->code - cfg->start;
1124                 if (code_size_ratio > mono_jit_stats.biggest_method_size) {
1125                         mono_jit_stats.biggest_method_size = code_size_ratio;
1126                         mono_jit_stats.biggest_method = method;
1127                 }
1128                 code_size_ratio = (code_size_ratio * 100) / header->code_size;
1129                 if (code_size_ratio > mono_jit_stats.max_code_size_ratio) {
1130                         mono_jit_stats.max_code_size_ratio = code_size_ratio;
1131                         mono_jit_stats.max_ratio_method = method;
1132                 }
1133
1134                 mono_compute_branches (cfg);
1135
1136                 if (mono_jit_dump_asm) {
1137                         char *id = g_strdup_printf ("%s.%s_%s", method->klass->name_space,
1138                                                     method->klass->name, method->name);
1139                         mono_disassemble_code (cfg->start, cfg->code - cfg->start, id);
1140                         g_free (id);
1141                 }
1142                 if (mono_debug_handle)
1143                         mono_debug_add_method (mono_debug_handle, cfg);
1144
1145                 ji->code_size = cfg->code - cfg->start;
1146                 ji->used_regs = cfg->rs->used_mask;
1147                 ji->method = method;
1148                 ji->code_start = addr;
1149
1150                 mono_jit_stats.native_code_size += ji->code_size;
1151
1152                 if (header->num_clauses) {
1153                         int i, start_block, end_block;
1154
1155                         ji->num_clauses = header->num_clauses;
1156                         ji->clauses = mono_mempool_alloc0 (target_domain->mp,
1157                                 sizeof (MonoJitExceptionInfo) * header->num_clauses);
1158
1159                         for (i = 0; i < header->num_clauses; i++) {
1160                                 MonoExceptionClause *ec = &header->clauses [i];
1161                                 MonoJitExceptionInfo *ei = &ji->clauses [i];
1162
1163                                 ei->flags = ec->flags;
1164                                 ei->token_or_filter = ec->token_or_filter;
1165
1166                                 g_assert (cfg->bcinfo [ec->try_offset].is_block_start);
1167                                 start_block = cfg->bcinfo [ec->try_offset].block_id;
1168                                 end_block = cfg->bcinfo [ec->try_offset + ec->try_len].block_id;
1169                                 g_assert (cfg->bcinfo [ec->try_offset + ec->try_len].is_block_start);
1170
1171                                 ei->try_start = cfg->start + cfg->bblocks [start_block].addr;
1172                                 ei->try_end = cfg->start + cfg->bblocks [end_block].addr;
1173
1174                                 g_assert (cfg->bcinfo [ec->handler_offset].is_block_start);
1175                                 start_block = cfg->bcinfo [ec->handler_offset].block_id;
1176                                 ei->handler_start = cfg->start + cfg->bblocks [start_block].addr;
1177
1178                                 //printf ("TEST %x %x %x\n", ei->try_start, ei->try_end, ei->handler_start);
1179                         }
1180                 }
1181
1182                 mono_jit_info_table_add (target_domain, ji);
1183
1184                 mono_regset_free (cfg->rs);
1185
1186                 mono_cfg_free (cfg);
1187
1188                 mono_mempool_destroy (mp);
1189
1190                 mono_profiler_method_end_jit (method, MONO_PROFILE_OK);
1191         }
1192
1193         if (mono_jit_trace_calls || mono_jit_dump_asm || mono_jit_dump_forest) {
1194                 printf ("END JIT compilation of %s.%s:%s %p %p\n", method->klass->name_space,
1195                         method->klass->name, method->name, method, addr);
1196         }
1197
1198         g_hash_table_insert (jit_code_hash, method, addr);
1199
1200         return addr;
1201 }
1202