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