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