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