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