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