Fri May 10 15:43:53 CEST 2002 Paolo Molaro <lupus@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
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
328                 if (header->init_locals) {
329                         MonoVarInfo *vi = &VARINFO (cfg, cfg->locals_start_index + header->num_locals - 1);
330                         int offset = vi->offset;  
331                         int size = - offset;
332                         int inited = 0;
333                         
334                         for (i = 0; i < header->num_locals; ++i) {
335                                 MonoVarInfo *rv = &VARINFO (cfg, cfg->locals_start_index + i);
336
337                                 if (rv->reg >= 0) {
338                                         int ind = 1 << rv->reg;
339                                         if (!(inited & ind))
340                                                 x86_alu_reg_reg (cfg->code, X86_XOR, rv->reg, rv->reg);
341                                         inited |= ind;
342                                 }
343                         }
344
345                         if (size == 1 || size == 2 || size == 4) {
346                                 x86_mov_membase_imm (cfg->code, X86_EBP, offset, 0, size);
347                                 return;
348                         }
349                         
350                         i = size / 4;
351                         j = size % 4;
352
353                         if (i < 3) {
354                                 for (k = 0; k < i; k++) {
355                                         x86_mov_membase_imm (cfg->code, X86_EBP, offset, 0, 4);
356                                         offset += 4;
357                                 }
358
359                                 if (j & 2) {
360                                         x86_mov_membase_imm (cfg->code, X86_EBP, offset, 0, 2);
361                                         offset += 2;
362                                 }
363                                 if (j & 1)
364                                         x86_mov_membase_imm (cfg->code, X86_EBP, offset, 0, 1);
365                                 return;
366                         }
367                         
368                         if (i) {
369                                 if (!mono_regset_reg_used (cfg->rs, X86_EDI)) 
370                                         x86_push_reg (cfg->code, X86_EDI);
371                                 x86_lea_membase (cfg->code, X86_EDI, X86_EBP, offset);
372                                 x86_alu_reg_reg (cfg->code, X86_XOR, X86_EAX, X86_EAX);
373                                 x86_mov_reg_imm (cfg->code, X86_ECX, i);
374                                 x86_cld (cfg->code);
375                                 x86_prefix (cfg->code, X86_REP_PREFIX);
376                                 x86_stosl (cfg->code);
377                                 for (i = 0; i < j; i++)
378                                         x86_stosb (cfg->code);
379                                 if (!mono_regset_reg_used (cfg->rs, X86_EDI)) 
380                                         x86_pop_reg (cfg->code, X86_EDI);
381                         } else {
382
383                                 g_assert (j == 3);
384                                 x86_mov_membase_imm (cfg->code, X86_EBP, offset, 0, 2);
385                                 x86_mov_membase_imm (cfg->code, X86_EBP, offset + 2, 0, 1);
386                         }
387                         
388                 } else {
389
390                         /* we always need to initialize object pointers */
391
392                         for (i = 0; i < header->num_locals; ++i) {
393                                 MonoType *t = header->locals [i];
394                                 int offset = VARINFO (cfg, cfg->locals_start_index + i).offset;  
395
396                                 if (t->byref) {
397                                         x86_mov_membase_imm (cfg->code, X86_EBP, offset, 0, 4);
398                                         continue;
399                                 }
400
401                                 switch (t->type) {
402                                 case MONO_TYPE_STRING:
403                                 case MONO_TYPE_CLASS:
404                                 case MONO_TYPE_ARRAY:
405                                 case MONO_TYPE_SZARRAY:
406                                 case MONO_TYPE_OBJECT:
407                                         x86_mov_membase_imm (cfg->code, X86_EBP, offset, 0, 4);
408                                         break;
409                                 }
410
411                         }
412                 }
413         }
414 }
415
416 /**
417  * arch_emit_epilogue:
418  * @cfg: pointer to status information
419  *
420  * Emits the function epilog.
421  */
422 static void
423 arch_emit_epilogue (MonoFlowGraph *cfg)
424 {
425         int pos = 4;
426         /*
427          * note: with trace and profiling the value on the FP stack may get clobbered.
428          */
429         if (mono_jit_trace_calls) {
430                 x86_fld_reg (cfg->code, 0);
431                 x86_alu_reg_imm (cfg->code, X86_SUB, X86_ESP, 8);
432                 x86_fst_membase (cfg->code, X86_ESP, 0, TRUE, TRUE);
433                 x86_push_reg (cfg->code, X86_EAX);
434                 x86_push_reg (cfg->code, X86_EDX);
435                 x86_push_imm (cfg->code, cfg->method);
436                 x86_mov_reg_imm (cfg->code, X86_EAX, leave_method);
437                 x86_call_reg (cfg->code, X86_EAX);
438                 x86_alu_reg_imm (cfg->code, X86_ADD, X86_ESP, 4);
439                 x86_pop_reg (cfg->code, X86_EDX);
440                 x86_pop_reg (cfg->code, X86_EAX);
441                 x86_alu_reg_imm (cfg->code, X86_ADD, X86_ESP, 8);
442         }
443         if (mono_jit_profile) {
444                 x86_push_reg (cfg->code, X86_EAX);
445                 x86_push_reg (cfg->code, X86_EDX);
446                 x86_push_imm (cfg->code, cfg->method);
447                 x86_mov_reg_imm (cfg->code, X86_EAX, mono_profiler_method_leave);
448                 x86_call_reg (cfg->code, X86_EAX);
449                 x86_alu_reg_imm (cfg->code, X86_ADD, X86_ESP, 4);
450                 x86_pop_reg (cfg->code, X86_EDX);
451                 x86_pop_reg (cfg->code, X86_EAX);
452         }
453
454         if (mono_regset_reg_used (cfg->rs, X86_EBX)) {
455                 x86_mov_reg_membase (cfg->code, X86_EBX, X86_EBP, - (cfg->locals_size + pos), 4);
456                 pos += 4;
457         }
458         if (mono_regset_reg_used (cfg->rs, X86_EDI)) {
459                 x86_mov_reg_membase (cfg->code, X86_EDI, X86_EBP, - (cfg->locals_size + pos), 4);
460                 pos += 4;
461         }
462         if (mono_regset_reg_used (cfg->rs, X86_ESI)) {
463                 x86_mov_reg_membase (cfg->code, X86_ESI, X86_EBP, - (cfg->locals_size + pos), 4);
464                 pos += 4;
465         }
466
467         x86_leave (cfg->code);
468         x86_ret (cfg->code);
469 }
470
471 static void
472 mono_label_cfg (MonoFlowGraph *cfg)
473 {
474         int i, j;
475
476         for (i = 0; i < cfg->block_count; i++) {
477                 GPtrArray *forest = cfg->bblocks [i].forest;
478                 int top;
479
480                 if (!cfg->bblocks [i].reached) /* unreachable code */
481                         continue;
482                 
483                 top = forest->len;
484
485                 for (j = 0; j < top; j++) {
486                         MBTree *t1 = (MBTree *) g_ptr_array_index (forest, j);
487                         MBState *mbstate;
488
489                         mbstate =  mono_burg_label (t1, cfg);
490
491                         if (!mbstate) {
492                                 cfg->invalid = 1;
493                                 if (mono_debug_handle)
494                                         return;
495                                 g_warning ("tree does not match");
496                                 mono_print_ctree (cfg, t1); printf ("\n\n");
497
498                                 mono_print_forest (cfg, forest);
499                                 g_assert_not_reached ();
500                         }
501                 }
502         }
503 }
504
505 static gboolean
506 tree_allocate_regs (MonoFlowGraph *cfg, MBTree *tree, int goal, MonoRegSet *rs, 
507                     guint8 exclude_mask, int *spillcount) 
508 {
509         MBTree *kids[10];
510         int ern = mono_burg_rule (tree->state, goal);
511         const guint16 *nts = mono_burg_nts [ern];
512         guint8 left_exclude_mask = 0, right_exclude_mask = 0;
513         int i;
514         
515 #ifdef DEBUG_REGALLOC
516         printf ("tree_allocate_regs start %d %08x %d %d\n",  tree->op, rs->free_mask, goal, 
517                 (nts [0] && kids [0] == tree));
518 #endif
519
520         mono_burg_kids (tree, ern, kids);
521
522         switch (tree->op) {
523         case MB_TERM_SHL:
524         case MB_TERM_SHR:
525         case MB_TERM_SHR_UN:
526                 exclude_mask |= (1 << X86_ECX);
527                 left_exclude_mask |= (1 << X86_ECX);
528                 break;
529         case MB_TERM_MUL:
530         case MB_TERM_MUL_OVF:
531         case MB_TERM_MUL_OVF_UN:
532         case MB_TERM_DIV:
533         case MB_TERM_DIV_UN:
534         case MB_TERM_REM:
535         case MB_TERM_REM_UN:
536                 if (goal == MB_NTERM_reg) {
537                         left_exclude_mask |= (1 << X86_EDX);
538                         right_exclude_mask |= (1 << X86_EDX) | (1 << X86_EAX);
539                 }
540                 break;
541         default:
542                 break;
543         }
544
545         if (nts [0] && kids [0] == tree) {
546                 /* chain rule */
547                 if (!tree_allocate_regs (cfg, kids [0], nts [0], rs, exclude_mask, spillcount))
548                         return FALSE;
549                 /* special case reg: coni4 */
550                 if (goal == MB_NTERM_reg) {
551                         if (tree->reg1 == -1)
552                                 tree->reg1 = mono_regset_alloc_reg (rs, -1, exclude_mask);
553                         if (tree->reg1 == -1)
554                                 return FALSE;
555                 }
556                 return TRUE;
557         }
558
559         if (tree->spilled) {
560                 if (tree->reg1 >= 0)
561                         (*spillcount)--;
562                 if (tree->reg2 >= 0)
563                         (*spillcount)--;
564                 if (tree->reg3 >= 0)
565                         (*spillcount)--;
566         }
567
568         tree->reg1 = -1;
569         tree->reg2 = -1;
570         tree->reg3 = -1;
571         
572         tree->spilled = 0;
573  
574         if (nts [0]) {
575                 if (nts [1]) { /* two kids */
576                         MonoRegSet saved_rs;
577                         if (nts [2]) /* we cant handle three kids */
578                                 g_assert_not_reached ();
579
580                         if (!tree_allocate_regs (cfg, kids [0], nts [0], rs, left_exclude_mask, spillcount))
581                                 return FALSE;
582
583                         saved_rs = *rs;
584
585                         if (!tree_allocate_regs (cfg, kids [1], nts [1], rs, right_exclude_mask, spillcount)) {
586
587 #ifdef DEBUG_REGALLOC
588                                 printf ("tree_allocate_regs try 1 failed %d %d %d %d\n", 
589                                         nts [1], kids [1]->reg1,
590                                         kids [1]->reg2,kids [1]->reg3);
591 #endif
592                                 *rs = saved_rs;
593
594                                 if (kids [0]->reg1 != -1) {
595                                         right_exclude_mask |= 1 << kids [0]->reg1;
596                                         (*spillcount)++;
597                                 }
598                                 if (kids [0]->reg2 != -1) {
599                                         right_exclude_mask |= 1 << kids [0]->reg2;
600                                         (*spillcount)++;
601                                 }
602                                 if (kids [0]->reg3 != -1) {
603                                         right_exclude_mask |= 1 << kids [0]->reg3;
604                                         (*spillcount)++;
605                                 }
606
607                                 mono_regset_free_reg (rs, kids [0]->reg1);
608                                 mono_regset_free_reg (rs, kids [0]->reg2);
609                                 mono_regset_free_reg (rs, kids [0]->reg3);
610
611                                 kids [0]->spilled = 1;
612
613                                 if (!tree_allocate_regs (cfg, kids [1], nts [1], rs, right_exclude_mask, spillcount)) {
614 #ifdef DEBUG_REGALLOC
615                                         printf ("tree_allocate_regs try 2 failed\n");
616 #endif
617                                         return FALSE;
618                                 }
619 #ifdef DEBUG_REGALLOC
620                                 printf ("tree_allocate_regs try 2 succesfull\n");
621 #endif
622                         }
623
624                 } else { /* one kid */
625                         if (!tree_allocate_regs (cfg, kids [0], nts [0], rs, left_exclude_mask, spillcount))
626                                 return FALSE;                   
627                 }
628         }
629
630
631         for (i = 0; nts [i]; i++) {
632                 mono_regset_free_reg (rs, kids [i]->reg1);
633                 mono_regset_free_reg (rs, kids [i]->reg2);
634                 mono_regset_free_reg (rs, kids [i]->reg3);
635         }
636
637         tree->emit = mono_burg_func [ern];
638
639         switch (tree->op) {
640         case MB_TERM_CALL_I4:
641         case MB_TERM_CALL_I8:
642         case MB_TERM_CALL_R8:
643         // case MB_TERM_CALL_VOID :
644                 if ((tree->reg1 = mono_regset_alloc_reg (rs, X86_EAX, exclude_mask)) == -1)
645                         return FALSE;
646                 if ((tree->reg2 = mono_regset_alloc_reg (rs, X86_EDX, exclude_mask)) == -1)
647                         return FALSE;
648                 if ((tree->reg3 = mono_regset_alloc_reg (rs, X86_ECX, exclude_mask)) == -1)
649                         return FALSE;
650                 return TRUE;
651         }
652
653         switch (goal) {
654         case MB_NTERM_reg:
655                 switch (tree->op) {
656                 case MB_TERM_MUL_OVF_UN:
657                 case MB_TERM_DIV:
658                 case MB_TERM_DIV_UN:
659                 case MB_TERM_REM:
660                 case MB_TERM_REM_UN:
661                         if ((tree->reg1 = mono_regset_alloc_reg (rs, X86_EAX, exclude_mask)) == -1)
662                                 return FALSE;                   
663                         if ((tree->reg2 = mono_regset_alloc_reg (rs, X86_EDX, exclude_mask)) == -1)
664                                 return FALSE;
665                         break;
666                 default:
667                         if ((tree->reg1 = mono_regset_alloc_reg (rs, -1, exclude_mask)) == -1)
668                                 return FALSE;
669                 }
670                 break;
671
672         case MB_NTERM_lreg:
673                 switch (tree->op) {
674                 case MB_TERM_MUL:
675                 case MB_TERM_MUL_OVF:
676                 case MB_TERM_MUL_OVF_UN:
677                 case MB_TERM_DIV:
678                 case MB_TERM_DIV_UN:
679                 case MB_TERM_REM:
680                 case MB_TERM_REM_UN:
681                         if ((tree->reg1 = mono_regset_alloc_reg (rs, X86_EAX, exclude_mask)) == -1)
682                                 return FALSE;                   
683                         if ((tree->reg2 = mono_regset_alloc_reg (rs, X86_EDX, exclude_mask)) == -1)
684                                 return FALSE;
685                         break;
686                 default:
687                         if ((tree->reg1 = mono_regset_alloc_reg (rs, -1, exclude_mask)) == -1)
688                                 return FALSE;
689                         if ((tree->reg2 = mono_regset_alloc_reg (rs, -1, exclude_mask)) == -1)
690                                 return FALSE;
691                 }
692                 break;
693
694         case MB_NTERM_freg:
695                 /* fixme: allocate floating point registers */
696                 break;
697       
698         case MB_NTERM_addr:
699                 if (tree->op == MB_TERM_ADD) {
700                         if ((tree->reg1 = mono_regset_alloc_reg (rs, tree->left->reg1, exclude_mask)) == -1)
701                                 return FALSE;
702                         if ((tree->reg2 = mono_regset_alloc_reg (rs, tree->right->reg1, exclude_mask)) == -1)
703                                 return FALSE;
704                 }
705                 break;
706                 
707         case MB_NTERM_base:
708                 if (tree->op == MB_TERM_ADD) {
709                         if ((tree->reg1 = mono_regset_alloc_reg (rs, tree->left->reg1, exclude_mask)) == -1)
710                                 return FALSE;
711                 }
712                 break;
713                
714         case MB_NTERM_index:
715                 if (tree->op == MB_TERM_SHL ||
716                     tree->op == MB_TERM_MUL) {
717                         if ((tree->reg1 = mono_regset_alloc_reg (rs, tree->left->reg1, exclude_mask)) == -1)
718                                 return FALSE;
719                 }
720                 break;
721                
722         default:
723                 /* do nothing */
724         }
725
726 #ifdef DEBUG_REGALLOC
727         printf ("tree_allocate_regs end %d %08x\n",  tree->op, rs->free_mask);
728 #endif
729         return TRUE;
730 }
731
732 static void
733 arch_allocate_regs (MonoFlowGraph *cfg)
734 {
735         int i, j, max_spillcount = 0;
736         
737         for (i = 0; i < cfg->block_count; i++) {
738                 GPtrArray *forest = cfg->bblocks [i].forest;
739                 int top;
740
741                 if (!cfg->bblocks [i].reached) /* unreachable code */
742                         continue;
743
744                 top = forest->len;
745
746                 for (j = 0; j < top; j++) {
747                         MBTree *t1 = (MBTree *) g_ptr_array_index (forest, j);
748                         int spillcount = 0;
749 #ifdef DEBUG_REGALLOC
750                         printf ("arch_allocate_regs start %d:%d %08x\n", i, j, cfg->rs->free_mask);
751 #endif
752                         if (!tree_allocate_regs (cfg, t1, 1, cfg->rs, 0, &spillcount)) {
753                                 mono_print_ctree (cfg, t1);
754                                 g_error ("register allocation failed");
755                         }
756
757                         max_spillcount = MAX (max_spillcount, spillcount);
758
759 #ifdef DEBUG_REGALLOC
760                         printf ("arch_allocate_regs end %d:%d %08x\n", i, j, cfg->rs->free_mask);
761 #endif
762                         g_assert (cfg->rs->free_mask == 0xffffffff);
763                 }
764         }
765
766         /* allocate space for spilled regs */
767
768         cfg->spillvars = mono_mempool_alloc0 (cfg->mp, sizeof (gint) *  max_spillcount);
769         cfg->spillcount = max_spillcount;
770
771         for (i = 0; i < max_spillcount; i++) {
772                 int spillvar;
773                 spillvar = arch_allocate_var (cfg, sizeof (gpointer), sizeof (gpointer),
774                                               MONO_TEMPVAR, VAL_I32);
775                 cfg->spillvars [i] = VARINFO (cfg, spillvar).offset;
776         }
777 }
778
779 static void
780 tree_emit (int goal, MonoFlowGraph *cfg, MBTree *tree, int *spillcount) 
781 {
782         MBTree *kids[10];
783         int ern = mono_burg_rule (tree->state, goal);
784         const guint16 *nts = mono_burg_nts [ern];
785         MBEmitFunc emit;
786         int offset;
787
788         mono_burg_kids (tree, ern, kids);
789
790         if (nts [0]) {
791                 if (nts [1]) {
792                         int spilloffset1, spilloffset2, spilloffset3;
793                         
794                         if (nts [2])
795                                 g_assert_not_reached ();
796
797                         tree_emit (nts [0], cfg, kids [0], spillcount);
798
799                         if (kids [0]->spilled) {
800 #ifdef DEBUG_SPILLS
801                                 printf ("SPILL_REGS %d %03x %s.%s:%s\n", 
802                                         nts [0], cfg->code - cfg->start,
803                                         cfg->method->klass->name_space,
804                                         cfg->method->klass->name, cfg->method->name);
805
806                                 mono_print_ctree (cfg, kids [0]);printf ("\n\n");
807 #endif
808                                 spilloffset1 = 0;
809                                 spilloffset2 = 0;
810                                 spilloffset3 = 0;
811
812                                 if (kids [0]->reg1 != -1) {
813                                         spilloffset1 = cfg->spillvars [(*spillcount)++];
814                                         x86_mov_membase_reg (cfg->code, X86_EBP, spilloffset1, 
815                                                              kids [0]->reg1, 4);
816                                 }
817                                 if (kids [0]->reg2 != -1) {
818                                         spilloffset2 = cfg->spillvars [(*spillcount)++];
819                                         x86_mov_membase_reg (cfg->code, X86_EBP, spilloffset2, 
820                                                              kids [0]->reg2, 4);
821                                 }
822                                 if (kids [0]->reg3 != -1) {
823                                         spilloffset3 = cfg->spillvars [(*spillcount)++];
824                                         x86_mov_membase_reg (cfg->code, X86_EBP, spilloffset3, 
825                                                              kids [0]->reg3, 4);
826                                 }
827                         }
828
829                         tree_emit (nts [1], cfg, kids [1], spillcount);
830
831                         if (kids [0]->spilled) {
832
833 #ifdef DEBUG_SPILLS
834                                 printf ("RELOAD_REGS %03x %s.%s:%s\n", 
835                                         cfg->code - cfg->start,
836                                         cfg->method->klass->name_space,
837                                         cfg->method->klass->name, cfg->method->name);
838 #endif
839
840                                 if (kids [0]->reg3 != -1) 
841                                         x86_mov_reg_membase (cfg->code, kids [0]->reg3, X86_EBP, 
842                                                              spilloffset3, 4);
843                                 if (kids [0]->reg2 != -1) 
844                                         x86_mov_reg_membase (cfg->code, kids [0]->reg2, X86_EBP, 
845                                                              spilloffset2, 4);
846                                 if (kids [0]->reg1 != -1) 
847                                         x86_mov_reg_membase (cfg->code, kids [0]->reg1, X86_EBP, 
848                                                              spilloffset1, 4);
849                         }
850                 } else {
851                         tree_emit (nts [0], cfg, kids [0], spillcount);
852                 }
853         }
854
855         g_assert ((*spillcount) <= cfg->spillcount);
856
857         tree->addr = offset = cfg->code - cfg->start;
858
859         /* we assume an instruction uses a maximum of 128 bytes */
860         if ((cfg->code_size - offset) <= 128) {
861                 int add = MIN (cfg->code_size, 128);
862                 cfg->code_size += add;
863                 mono_jit_stats.code_reallocs++;
864                 cfg->start = g_realloc (cfg->start, cfg->code_size);
865                 g_assert (cfg->start);
866                 cfg->code = cfg->start + offset;
867         }
868
869         if ((emit = mono_burg_func [ern]))
870                 emit (tree, cfg);
871
872         g_assert ((cfg->code - cfg->start) < cfg->code_size);
873 }
874
875 static void
876 mono_emit_cfg (MonoFlowGraph *cfg)
877 {
878         int i, j, spillcount;
879
880         for (i = 0; i < cfg->block_count; i++) {
881                 MonoBBlock *bb = &cfg->bblocks [i];
882                 GPtrArray *forest = bb->forest;
883                 int top;
884
885                 if (!bb->reached) /* unreachable code */
886                         continue;
887                 
888                 top = forest->len;
889
890                 bb->addr = cfg->code - cfg->start;
891           
892                 for (j = 0; j < top; j++) {
893                         MBTree *t1 = (MBTree *) g_ptr_array_index (forest, j);
894                         
895                         spillcount = 0;
896                         tree_emit (1, cfg, t1, &spillcount);
897                 }
898         }
899                 
900         cfg->epilog = cfg->code - cfg->start;
901 }
902
903 static void
904 mono_compute_branches (MonoFlowGraph *cfg)
905 {
906         MonoJumpInfo *ji;
907         guint8 *end;
908         int i, j;
909
910         end = cfg->code;
911
912         for (j = 0; j < cfg->block_count; j++) {
913                 MonoBBlock *bb = &cfg->bblocks [j];
914                 GPtrArray *forest = bb->forest;
915                 int top;
916                 
917                 if (!bb->reached) /* unreachable code */
918                         continue;
919
920                 top = forest->len;
921         
922                 for (i = 0; i < top; i++) {
923                         MBTree *t1 = (MBTree *) g_ptr_array_index (forest, i);
924
925                         if (t1->op == MB_TERM_SWITCH) {
926                                 MonoBBlock **jt = (MonoBBlock **)t1->data.p;
927                                 guint32 *rt = (guint32 *)t1->data.p;
928                                 int m = *((guint32 *)t1->data.p) + 1;
929                                 int k;
930                                 
931                                 for (k = 1; k <= m; k++)
932                                         rt [k] = (int)(jt [k]->addr + cfg->start);
933                                 
934                                 /* emit the switch instruction again to update addresses */
935                                 cfg->code = cfg->start + t1->addr;
936                                 ((MBEmitFunc)t1->emit) (t1, cfg);
937                         }
938                 }
939         }
940
941         cfg->code = end;
942
943         for (ji = cfg->jump_info; ji; ji = ji->next) {
944                 unsigned char *ip = GUINT_TO_POINTER (GPOINTER_TO_UINT (ji->ip) + cfg->start);
945                 unsigned char *target;
946
947                 switch (ji->type) {
948                 case MONO_JUMP_INFO_BB:
949                         target = ji->data.bb->addr + cfg->start;
950                         break;
951                 case MONO_JUMP_INFO_ABS:
952                         target = ji->data.target;
953                         break;
954                 case MONO_JUMP_INFO_EPILOG:
955                         target = cfg->epilog + cfg->start;
956                         break;
957                 case MONO_JUMP_INFO_IP:
958                         *(unsigned char**)ip = ip;
959                         continue;
960                 default:
961                         g_assert_not_reached ();
962                 }
963                 x86_patch (ip, target);
964         }
965 }
966
967 void
968 mono_add_jump_info (MonoFlowGraph *cfg, gpointer ip, MonoJumpInfoType type, gpointer target)
969 {
970         MonoJumpInfo *ji = mono_mempool_alloc (cfg->mp, sizeof (MonoJumpInfo));
971
972         ji->type = type;
973         ji->ip = GUINT_TO_POINTER (GPOINTER_TO_UINT (ip) - GPOINTER_TO_UINT (cfg->start));
974         ji->data.target = target;
975         ji->next = cfg->jump_info;
976
977         cfg->jump_info = ji;
978 }
979
980 static int
981 match_debug_method (MonoMethod* method)
982 {
983         GList *tmp = mono_debug_methods;
984
985         for (; tmp; tmp = tmp->next) {
986                 if (mono_method_desc_full_match (tmp->data, method))
987                         return 1;
988         }
989         return 0;
990 }
991
992 /**
993  * arch_compile_method:
994  * @method: pointer to the method info
995  *
996  * JIT compilation of a single method. 
997  *
998  * Returns: a pointer to the newly created code.
999  */
1000 gpointer
1001 arch_compile_method (MonoMethod *method)
1002 {
1003         MonoDomain *target_domain, *domain = mono_domain_get ();
1004         MonoJitInfo *ji;
1005         guint8 *addr;
1006         GHashTable *jit_code_hash;
1007
1008         if ((method->iflags & METHOD_IMPL_ATTRIBUTE_INTERNAL_CALL) ||
1009             (method->flags & METHOD_ATTRIBUTE_PINVOKE_IMPL)) {
1010                 if (!method->info)
1011                         method->info = arch_create_native_wrapper (method);
1012                 return method->info;
1013         }
1014
1015         if (mono_jit_share_code)
1016                 target_domain = mono_root_domain;
1017         else 
1018                 target_domain = domain;
1019
1020         jit_code_hash = target_domain->jit_code_hash;
1021
1022         if ((addr = g_hash_table_lookup (jit_code_hash, method))) {
1023                 mono_jit_stats.methods_lookups++;
1024                 return addr;
1025         }
1026
1027         mono_jit_stats.methods_compiled++;
1028         
1029         if (mono_jit_trace_calls || mono_jit_dump_asm || mono_jit_dump_forest) {
1030                 printf ("Start JIT compilation of %s.%s:%s\n", method->klass->name_space,
1031                         method->klass->name, method->name);
1032         }
1033
1034         if (method->iflags & METHOD_IMPL_ATTRIBUTE_RUNTIME) {
1035                 const char *name = method->name;
1036                 guint8 *code;
1037                 gboolean delegate = FALSE;
1038
1039                 if (method->klass->parent == mono_defaults.multicastdelegate_class)
1040                         delegate = TRUE;
1041                                 
1042                 if (delegate && *name == '.' && (strcmp (name, ".ctor") == 0)) {
1043                         addr = (gpointer)mono_delegate_ctor;
1044                 } else if (delegate && *name == 'I' && (strcmp (name, "Invoke") == 0)) {
1045                         int size;
1046
1047                         addr = arch_get_delegate_invoke (method, &size);
1048
1049                         if (mono_jit_dump_asm) {
1050                                 char *id = g_strdup_printf ("%s.%s_%s", method->klass->name_space,
1051                                                             method->klass->name, method->name);
1052                                 mono_disassemble_code (addr, size, id);
1053                                 g_free (id);
1054                         }
1055                 } else if (delegate && *name == 'B' && (strcmp (name, "BeginInvoke") == 0)) {
1056                         code = addr = g_malloc (32);
1057                         x86_push_imm (code, method);
1058                         x86_call_code (code, arch_begin_invoke);
1059                         x86_alu_reg_imm (code, X86_ADD, X86_ESP, 4);
1060                         x86_ret (code);
1061                         g_assert ((code - addr) <= 32);
1062                 } else if (delegate && *name == 'E' && (strcmp (name, "EndInvoke") == 0)) {
1063                         /* this can raise exceptions, so we need a wrapper to save/restore LMF */
1064                         method->addr = (gpointer)arch_end_invoke;
1065                         addr = arch_create_native_wrapper (method);
1066                 } else {
1067                         mono_profiler_method_end_jit (method, MONO_PROFILE_FAILED);
1068                         if (mono_debug_handle) 
1069                                 return NULL;
1070
1071                         g_error ("Don't know how to exec runtime method %s.%s::%s", 
1072                                  method->klass->name_space, method->klass->name, method->name);
1073                 }
1074         
1075         } else {
1076                 MonoMethodHeader *header = ((MonoMethodNormal *)method)->header;
1077                 MonoFlowGraph *cfg;
1078                 MonoMemPool *mp;
1079                 gulong code_size_ratio;
1080                 guint32 ls_used_mask = 0;
1081         
1082                 mono_profiler_method_jit (method);
1083         
1084                 ji = mono_mempool_alloc0 (target_domain->mp, sizeof (MonoJitInfo));
1085                 
1086                 mp = mono_mempool_new ();
1087
1088                 cfg = mono_cfg_new (method, mp);
1089
1090                 mono_analyze_flow (cfg);
1091                 if (cfg->invalid) {
1092                         mono_profiler_method_end_jit (method, MONO_PROFILE_FAILED);
1093                         return NULL;
1094                 }
1095                 
1096                 mono_analyze_stack (cfg);
1097                 if (cfg->invalid) {
1098                         mono_profiler_method_end_jit (method, MONO_PROFILE_FAILED);
1099                         return NULL;
1100                 }
1101                 
1102                 cfg->rs = mono_regset_new (X86_NREG);
1103                 mono_regset_reserve_reg (cfg->rs, X86_ESP);
1104                 mono_regset_reserve_reg (cfg->rs, X86_EBP);
1105
1106                 /* we can use this regs for global register allocation */
1107                 mono_regset_reserve_reg (cfg->rs, X86_EBX);
1108                 mono_regset_reserve_reg (cfg->rs, X86_ESI);
1109
1110                 cfg->code_size = MAX (header->code_size * 5, 256);
1111                 cfg->start = cfg->code = g_malloc (cfg->code_size);
1112
1113                 mono_debug_last_breakpoint_address = cfg->code;
1114
1115                 if (match_debug_method (method) || mono_debug_insert_breakpoint)
1116                         x86_breakpoint (cfg->code);
1117                 else if (mono_debug_handle)
1118                         x86_nop (cfg->code);
1119
1120                 if (mono_debug_insert_breakpoint > 0)
1121                         mono_debug_insert_breakpoint--;
1122
1123                 if (mono_use_linear_scan) {
1124                         mono_linear_scan (cfg, &ls_used_mask);
1125                         cfg->rs->used_mask |= ls_used_mask;
1126                 }
1127
1128                 if (mono_jit_dump_forest) {
1129                         int i;
1130                         printf ("FOREST %s.%s:%s\n", method->klass->name_space,
1131                                 method->klass->name, method->name);
1132                         for (i = 0; i < cfg->block_count; i++) {
1133                                 printf ("BLOCK %d:\n", i);
1134                                 mono_print_forest (cfg, cfg->bblocks [i].forest);
1135                         }
1136                 }
1137                         
1138                 mono_label_cfg (cfg);
1139
1140                 if (cfg->invalid) {
1141                         mono_profiler_method_end_jit (method, MONO_PROFILE_FAILED);
1142                         return NULL;
1143                 }
1144                 
1145                 arch_allocate_regs (cfg);
1146
1147                 /* align to 8 byte boundary */
1148                 cfg->locals_size += 7;
1149                 cfg->locals_size &= ~7;
1150
1151                 arch_emit_prologue (cfg);
1152                 cfg->prologue_end = cfg->code - cfg->start;
1153                 mono_emit_cfg (cfg);
1154                 arch_emit_epilogue (cfg);               
1155                 cfg->epilogue_end = cfg->code - cfg->start;
1156
1157                 addr = cfg->start;
1158
1159                 mono_jit_stats.allocated_code_size += cfg->code_size;
1160
1161                 code_size_ratio = cfg->code - cfg->start;
1162                 if (code_size_ratio > mono_jit_stats.biggest_method_size) {
1163                         mono_jit_stats.biggest_method_size = code_size_ratio;
1164                         mono_jit_stats.biggest_method = method;
1165                 }
1166                 code_size_ratio = (code_size_ratio * 100) / header->code_size;
1167                 if (code_size_ratio > mono_jit_stats.max_code_size_ratio) {
1168                         mono_jit_stats.max_code_size_ratio = code_size_ratio;
1169                         mono_jit_stats.max_ratio_method = method;
1170                 }
1171
1172                 mono_compute_branches (cfg);
1173                 
1174                 if (mono_jit_dump_asm) {
1175                         char *id = g_strdup_printf ("%s.%s_%s", method->klass->name_space,
1176                                                     method->klass->name, method->name);
1177                         mono_disassemble_code (cfg->start, cfg->code - cfg->start, id);
1178                         g_free (id);
1179                 }
1180                 if (mono_debug_handle)
1181                         mono_debug_add_method (mono_debug_handle, cfg);
1182
1183                 ji->code_size = cfg->code - cfg->start;
1184                 ji->used_regs = cfg->rs->used_mask;
1185                 ji->method = method;
1186                 ji->code_start = addr;
1187
1188                 mono_jit_stats.native_code_size += ji->code_size;
1189
1190                 if (header->num_clauses) {
1191                         int i, start_block, end_block;
1192
1193                         ji->num_clauses = header->num_clauses;
1194                         ji->clauses = mono_mempool_alloc0 (target_domain->mp, 
1195                                 sizeof (MonoJitExceptionInfo) * header->num_clauses);
1196
1197                         for (i = 0; i < header->num_clauses; i++) {
1198                                 MonoExceptionClause *ec = &header->clauses [i];
1199                                 MonoJitExceptionInfo *ei = &ji->clauses [i];
1200                         
1201                                 ei->flags = ec->flags;
1202                                 ei->token_or_filter = ec->token_or_filter;
1203
1204                                 g_assert (cfg->bcinfo [ec->try_offset].is_block_start);
1205                                 start_block = cfg->bcinfo [ec->try_offset].block_id;
1206                                 end_block = cfg->bcinfo [ec->try_offset + ec->try_len].block_id;
1207                                 g_assert (cfg->bcinfo [ec->try_offset + ec->try_len].is_block_start);
1208                                 
1209                                 ei->try_start = cfg->start + cfg->bblocks [start_block].addr;
1210                                 ei->try_end = cfg->start + cfg->bblocks [end_block].addr;
1211                                 
1212                                 g_assert (cfg->bcinfo [ec->handler_offset].is_block_start);
1213                                 start_block = cfg->bcinfo [ec->handler_offset].block_id;
1214                                 ei->handler_start = cfg->start + cfg->bblocks [start_block].addr;       
1215                                 
1216                                 //printf ("TEST %x %x %x\n", ei->try_start, ei->try_end, ei->handler_start);
1217                         }
1218                 }
1219                 
1220                 mono_jit_info_table_add (target_domain, ji);
1221
1222                 mono_regset_free (cfg->rs);
1223
1224                 mono_cfg_free (cfg);
1225
1226                 mono_mempool_destroy (mp);
1227
1228                 mono_profiler_method_end_jit (method, MONO_PROFILE_OK);
1229         }
1230
1231         if (mono_jit_trace_calls || mono_jit_dump_asm || mono_jit_dump_forest) {
1232                 printf ("END JIT compilation of %s.%s:%s %p %p\n", method->klass->name_space,
1233                         method->klass->name, method->name, method, addr);
1234         }
1235
1236         g_hash_table_insert (jit_code_hash, method, addr);
1237
1238         return addr;
1239 }
1240