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