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