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