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