2002-11-28 Dietmar Maurer <dietmar@ximian.com>
[mono.git] / mono / jit / interp.brg
1 /*
2  * interp.brg: experimental interpreter code
3  *
4  * This is another approach for an interpreter. CIL is translated into another
5  * byte code which can be interpreted more efficiently. First measurements
6  * showed a quite good performance.
7  *
8  * We do not develop this further at the moment because of a lack of time.
9  *
10  * Author:
11  *   Dietmar Maurer (dietmar@ximian.com)
12  *
13  * (C) 2001 Ximian, Inc.  */
14
15 #include <glib.h>
16 #include <stdio.h>
17
18 #include <mono/metadata/blob.h>
19 #include <mono/metadata/metadata.h>
20 #include <mono/metadata/loader.h>
21 #include <mono/metadata/tabledefs.h>
22 #include <mono/metadata/class.h>
23
24 #include "mempool.h"
25
26 #define MBTREE_TYPE  MBTree
27 #define MBCGEN_TYPE  MBCodeGenStatus
28 #define MBCOST_DATA  MBCodeGenStatus
29 #define MBALLOC_STATE mono_mempool_alloc (data->mp, sizeof (MBState))
30
31 #define d(x) 
32
33 typedef struct _MonoInvocation MonoInvocation;
34
35 typedef void (*MIntFunc) (MonoInvocation *frame);
36
37 typedef struct {
38         MonoMemPool *mp;
39         guint8      *start;
40         guint8      *code;
41         GPtrArray   *forest;
42 } MBCodeGenStatus;
43
44 typedef struct _MBTree MBTree;
45 struct _MBTree {
46         guint16   op;
47         MBTree   *left, *right;
48         gpointer  state;
49         gpointer  emit;
50
51         guint     is_jump:1;
52         guint     last_instr:1;
53         guint     jump_target:1;
54
55         gint32    cli_addr;   /* virtual cli address */
56         gint32    addr;       /* address of emitted instruction */
57         gint32    first_addr; /* first code address of a tree */ 
58
59         gint32    size;
60
61         union {
62                 gint32 i;
63                 gint64 l;
64                 gpointer p;
65         } data;
66 };
67
68 typedef struct {
69         union {
70                 gint32 i;
71                 gint64 l;
72                 double f;
73                 gpointer p;
74         } data;
75 } stackval;
76
77 struct _MonoInvocation {
78         MonoInvocation *parent; /* parent */
79         MonoInvocation *child;
80         MonoMethod     *method; /* parent */
81         stackval       *retval; /* parent */
82         void           *obj;    /* this - parent */
83         char           *locals;
84         char           *args;
85         stackval       *stack;
86 };
87
88 typedef enum {
89         IC_CONST_I4,
90         IC_ADDR_L,
91         IC_ADDR_A,
92         IC_LDIND_I4,
93         IC_LDIND_LOC_I4,
94         IC_LDIND_ARG_I4,
95         IC_STIND_I4,
96         IC_STIND_LOC_I4,
97         IC_MUL_I4,
98         IC_ADD_I4,
99         IC_ADD_LOC_LOC_I4,
100         IC_SUB_I4,
101         IC_SUB_ARG_CI4,
102         IC_BR,
103         IC_BRTRUE_I4,
104         IC_BRTRUE_LOC_I4,
105         IC_BLT_I4,
106         IC_BEQ_I4,
107         IC_BGE_I4,
108         IC_BGE_I4_C,
109         IC_RET,
110         IC_RETV_I4,
111         IC_CALL_I4,
112         IC_PUSH_I4,
113 } MIntCommands;
114
115 #define INIT_FRAME(frame,parent_frame,obj_this,method_args,method_retval,mono_method)   \
116         do {    \
117                 (frame)->parent = (parent_frame);       \
118                 (frame)->obj = (obj_this);      \
119                 (frame)->args = (method_args);  \
120                 (frame)->retval = (method_retval);      \
121                 (frame)->method = (mono_method);        \
122         } while (0)
123
124 #define COMMAND(c,name) do { *(c)++ = name; } while (0)
125
126 #define MB_OPT_LEVEL 1
127
128 #if MB_OPT_LEVEL == 0
129 #define MB_USE_OPT1(c) 65535
130 #define MB_USE_OPT2(c) 65535
131 #endif
132 #if MB_OPT_LEVEL == 1
133 #define MB_USE_OPT1(c) c
134 #define MB_USE_OPT2(c) 65535
135 #endif
136 #if MB_OPT_LEVEL >= 2
137 #define MB_USE_OPT1(c) c
138 #define MB_USE_OPT2(c) c
139 #endif
140
141 %%
142
143 #
144 # terminal definitions
145 #
146
147 # constatnts
148 %term CONST_I4 CONST_I8 CONST_R4 CONST_R8
149 %term LDIND_I1 LDIND_U1 LDIND_I2 LDIND_U2 LDIND_I4 LDIND_I8 LDIND_R4 LDIND_R8
150 %term LDIND_U4
151 %term STIND_I1 STIND_I2 STIND_I4 STIND_I8 STIND_R4 STIND_R8
152 %term ADDR_L ADDR_A ADDR_G ARG ARG_END CALL_I4 CALL_I8 CALL_R8
153 %term BREAK SWITCH BR RET RETV 
154 %term ADD SUB MUL DIV DIV_UN REM REM_UN AND OR XOR SHL SHR SHR_UN NEG NOT
155 %term BLT BLT_UN BEQ BNE_UN BRTRUE BRFALSE BGE BGE_UN BLE BLE_UN BGT BGT_UN 
156 %term CONV_I4 CONV_I1 CONV_I2 CONV_I8 CONV_R8
157
158 #
159 # we start at stmt
160 #
161 %start stmt
162
163 #
164 # tree definitions
165 #
166
167 reg: CONST_I4 1 {
168         COMMAND (s->code, IC_CONST_I4);
169         *((gint32*)s->code)++ = tree->data.i;
170 }
171
172 # do nothing
173 reg: CONV_I4 (reg) 
174
175 reg: ADDR_L 1 {
176         COMMAND (s->code, IC_ADDR_L);
177         *((gint32*)s->code)++ = tree->data.i;
178 }
179
180 reg: ADDR_A 1 {
181         COMMAND (s->code, IC_ADDR_A);
182         *((gint32*)s->code)++ = tree->data.i;
183 }
184
185 reg: LDIND_I4 (reg) {
186         COMMAND (s->code, IC_LDIND_I4);
187 }
188
189 reg: LDIND_I4 (ADDR_L) "MB_USE_OPT1(0)" {
190         COMMAND (s->code, IC_LDIND_LOC_I4);
191         *((gint32*)s->code)++ = tree->left->data.i;
192 }
193
194 reg: LDIND_I4 (ADDR_A) "MB_USE_OPT1(0)" {
195         COMMAND (s->code, IC_LDIND_ARG_I4);
196         *((gint32*)s->code)++ = tree->left->data.i;
197 }
198
199 reg: MUL (reg, reg) {
200         COMMAND (s->code, IC_MUL_I4);
201 }
202
203
204 reg: ADD (reg, reg) {
205         COMMAND (s->code, IC_ADD_I4);
206 }
207
208 reg: SUB (reg, reg) {
209         COMMAND (s->code, IC_SUB_I4);
210 }
211
212 # just an optimisations
213 reg: SUB (LDIND_I4 (ADDR_A), CONST_I4) "MB_USE_OPT1(0)" {
214         COMMAND (s->code, IC_SUB_ARG_CI4);
215         *((gint32*)s->code)++ = tree->left->left->data.i;
216         *((gint32*)s->code)++ = tree->right->data.i;
217 }
218
219 stmt: STIND_I4 (reg, reg) {
220         COMMAND (s->code, IC_STIND_I4);
221 }
222
223 stmt: STIND_I4 (ADDR_L, reg) "MB_USE_OPT1(0)" {
224         COMMAND (s->code, IC_STIND_LOC_I4);
225         *((gint32*)s->code)++ = tree->left->data.i;
226 }
227
228 stmt: BR {
229         tree->is_jump = 1;    
230
231         COMMAND (s->code, IC_BR);
232         *((gint32*)s->code)++ = tree->data.i - 5;
233 }
234
235 stmt: BLT (reg, reg) 1 {
236         tree->is_jump = 1;    
237
238         COMMAND (s->code, IC_BLT_I4);
239         *((gint32*)s->code)++ = tree->data.i - 5;
240 }
241
242 stmt: BEQ (reg, reg) {
243         tree->is_jump = 1;    
244
245         COMMAND (s->code, IC_BEQ_I4);
246         *((gint32*)s->code)++ = tree->data.i - 5;
247 }
248
249 stmt: BGE (reg, reg) 1 {
250         tree->is_jump = 1;    
251
252         COMMAND (s->code, IC_BGE_I4);
253         *((gint32*)s->code)++ = tree->data.i - 5;
254 }
255
256 stmt: BGE (reg, CONST_I4) "MB_USE_OPT1(0)" {
257         tree->is_jump = 1;    
258
259         COMMAND (s->code, IC_BGE_I4_C);
260         *((gint32*)s->code)++ = tree->right->data.i;
261         *((gint32*)s->code)++ = tree->data.i - 9;
262 }
263
264 stmt: BRTRUE (reg) 1 {
265         tree->is_jump = 1;
266
267         COMMAND (s->code, IC_BRTRUE_I4);
268         *((gint32*)s->code)++ = tree->data.i - 5;
269 }
270
271 stmt: BRTRUE (LDIND_I4 (ADDR_L)) "MB_USE_OPT1(0)" {
272         tree->is_jump = 1;
273
274         COMMAND (s->code, IC_BRTRUE_LOC_I4);
275         *((gint32*)s->code)++ = tree->left->left->data.i;
276         *((gint32*)s->code)++ = tree->data.i - 9;
277 }
278
279 stmt: RETV (reg) {
280         COMMAND (s->code, IC_RETV_I4);
281 }
282
283 stmt: RET {
284         COMMAND (s->code, IC_RET);
285 }
286
287 argl: ARG (argl, reg) {
288         COMMAND (s->code, IC_PUSH_I4);
289 }
290
291 argl: ARG_END
292
293 reg: CALL_I4 (argl) {
294         COMMAND (s->code, IC_CALL_I4);
295         *((gint32*)s->code)++ = tree->data.i;
296 }
297
298 stmt: CALL_I4 (argl) {
299         COMMAND (s->code, IC_CALL_I4);
300         *((gint32*)s->code)++ = tree->data.i;
301 }
302
303 %% 
304
305 #include "jit.h"
306
307
308 MBTree *
309 mono_ctree_new (MonoMemPool *mp, int op, MBTree *left, MBTree *right)
310 {
311         MBTree *t = mono_mempool_alloc0 (mp, sizeof (MBTree));
312
313         t->op = op;
314         t->left = left;
315         t->right = right;
316         t->cli_addr = -1;
317         return t;
318 }
319
320 MBTree *
321 mono_ctree_new_leaf (MonoMemPool *mp, int op)
322 {
323         return mono_ctree_new (mp, op, NULL, NULL);
324 }
325
326 static void 
327 interp_exec_method (MonoInvocation *frame)
328 {
329         MonoInvocation child_frame;
330         MonoMethodHeader *header;
331         guint8 *ip, *ap, *args;
332         register stackval *sp;
333
334         d(printf ("EXEC METHOD %p\n", frame->args));
335
336         g_assert (frame->method->addr != NULL);
337
338         if (!frame->method->klass->inited)
339                 mono_jit_init_class (frame->method->klass);
340
341         child_frame.parent = frame;
342
343         header = ((MonoMethodNormal *)frame->method)->header;
344
345         ip = frame->method->addr;
346
347         sp = frame->stack = alloca (sizeof (stackval) * header->max_stack);
348
349         args = ap = alloca (256); // fixme: use max args size
350
351         if (header->num_locals) {
352                 frame->locals = alloca (header->locals_size);
353                 memset (frame->locals, 0, header->locals_size);
354                 frame->locals += header->locals_size;
355         }
356
357         while (1) {
358
359                 switch (*ip++) {
360                 case IC_CONST_I4: {
361                         sp->data.i = *((gint32*)ip);
362                         d(printf ("IC_CONST_I4 %d:\n", sp->data.i));
363                         ip += 4;
364                         sp++;
365                         break;
366                 }
367                 case IC_ADDR_L: {
368                         d(printf ("IC_ADDR_L: %p\n", sp));
369                         sp->data.p = frame->locals + *((gint32*)ip); 
370                         ip += 4;
371                         sp++;
372                         break;
373                 }
374                 case IC_ADDR_A: {
375                         sp->data.p = frame->args + *((gint32*)ip); 
376                         d(printf ("IC_ADDR_A: %p\n", sp->data.p));
377                         ip += 4;
378                         sp++;
379                         break;
380                 }
381                 case IC_LDIND_I4: {
382                         sp--;
383                         sp->data.i = *(gint32*)sp->data.p;
384                         d(printf ("IC_LDIND_I4: %p %d\n", sp->data.p, sp->data.i));
385                         sp++;
386                         break;
387                 }
388                 case IC_LDIND_LOC_I4: {
389                         gint32 *p = (gint32 *)frame->locals + *((gint32*)ip);
390                         sp->data.i = *p;
391                         d(printf ("IC_LDIND_LOC_I4: %p %d\n", p, sp->data.i));
392                         sp++;
393                         ip += 4;
394                         break;
395                 }
396                 case IC_LDIND_ARG_I4: {
397                         gint32 *p = (gint32 *)frame->args + *((gint32*)ip);
398                         sp->data.i = *p;
399                         d(printf ("IC_LDIND_LOC_I4: %p %d\n", p, sp->data.i));
400                         sp++;
401                         ip += 4;
402                         break;
403                 }
404                 case IC_STIND_I4: {
405                         sp -= 2;
406                         d(printf ("IC_STIND_I4: %p %d\n", sp->data.p, sp [1].data.i));
407                         *(gint32*)sp->data.p = sp [1].data.i;
408                         break;
409                 }
410                 case IC_STIND_LOC_I4: {
411                         gint32 *p = (gint32 *)frame->locals + *((gint32*)ip);
412                         sp -= 1;
413                         d(printf ("IC_STIND_LOC_I4: %p %d\n", p, sp->data.i));
414                         *p = sp->data.i;
415                         ip += 4;
416                         break;
417                 }
418                 case IC_MUL_I4: {
419                         d(printf ("IC_MUL_I4:\n"));
420                         g_assert_not_reached ();
421                         break;
422                 }
423                 case IC_ADD_I4: {
424                         sp -= 2;
425                         sp->data.i = sp [0].data.i + sp [1].data.i;
426                         d(printf ("IC_ADD_I4: %d\n", sp->data.i));
427                         sp++;
428                         break;
429                 }
430                 case IC_SUB_I4: {
431                         sp -= 2;
432                         sp->data.i = sp [0].data.i - sp [1].data.i;
433                         d(printf ("IC_SUB_I4: %d\n", sp->data.i));
434                         sp++;
435                         break;
436                 }
437                 case IC_ADD_LOC_LOC_I4: {
438                         gint32 *p1 = (gint32 *)frame->args + *((gint32*)ip);
439                         gint32 *p2 = (gint32 *)frame->args + *((gint32*)ip+1);
440                         
441                         sp->data.i = *p1 + *p2;
442                         d(printf ("IC_ADD_LOC_LOC_I4: %d\n", sp->data.i));
443                         sp++;
444                         ip += 8;
445
446                         break;
447                 }
448                 case IC_SUB_ARG_CI4: {
449                         gint32 *p = (gint32 *)frame->args + *((gint32*)ip);
450                         sp->data.i = *p - *(((gint32*)ip) + 1);
451                         d(printf ("IC_SUB_ARG_CI4: %d\n", sp->data.i));
452                         sp++;
453                         ip += 8;
454
455                         break;
456                 }
457                 case IC_BR: {
458                         d(printf ("IC_BR:\n"));
459                         ip += 4 + *((gint32*)ip);
460                         break;
461                 }
462                 case IC_BLT_I4: {
463                         d(printf ("IC_BLT_I4:\n"));
464                         ip += 4;
465                         g_assert_not_reached ();
466                         break;
467                 }
468                 case IC_BRTRUE_I4: {
469                         sp -= 1;
470                         d(printf ("IC_BRTRUE_I4: (%d) %d\n", sp [0].data.i, *((gint32*)ip)));
471                         
472                         if (sp [0].data.i) 
473                                 ip += 4 + *((gint32*)ip);
474                         else
475                                 ip += 4;
476                         break;
477                 }
478                 case IC_BRTRUE_LOC_I4: {
479                         gint32 *p = (gint32 *)frame->locals + *((gint32*)ip);
480                        
481                         d(printf ("IC_BRTRUE_LOC_I4: %d %d\n", p, *((gint32*)ip+1)));
482                        
483                         if (*p) 
484                                 ip += 8 + *((gint32*)ip+1);
485                         else
486                                 ip += 8;
487                         break;
488                 }
489                 case IC_BEQ_I4: {
490                         sp -= 2;
491                         d(printf ("IC_BEQ_I4: (%d == %d) %d\n", sp [0].data.i, sp [1].data.i, *((gint32*)ip)));
492                         
493                         if (sp [0].data.i == sp [1].data.i) 
494                                 ip += 4 + *((gint32*)ip);
495                         else
496                                 ip += 4;
497                         break;
498                 }
499                 case IC_BGE_I4: {
500                         sp -= 2;
501                         d(printf ("IC_BGE_I4: (%d >= %d) %d\n", sp [0].data.i, sp [1].data.i, *((gint32*)ip)));
502                         
503                         if (sp [0].data.i >= sp [1].data.i) 
504                                 ip += 4 + *((gint32*)ip);
505                         else
506                                 ip += 4;
507                         break;
508                 }
509                 case IC_BGE_I4_C: {
510                         sp--;
511                         d(printf ("IC_BGE_I4: (%d >= %d) %d\n", sp [0].data.i, 
512                                 *((gint32*)ip), *(((gint32*)ip) + 1)));
513                         if (sp [0].data.i >= *((gint32*)ip)) 
514                                 ip += 8 + *(((gint32*)ip) + 1);
515                         else
516                                 ip += 8;
517                         break;
518                 }
519                 case IC_RET: {
520                         d(printf ("IC_RET:\n"));
521                         g_error ("RETURN");
522                         break;
523                 }
524                 case IC_RETV_I4: {
525                         --sp;
526                         d(printf ("IC_RETV_I4: %d\n", sp->data.i));
527                         frame->retval->data.i = sp->data.i;
528                         return;
529                         break;
530                 }
531                 case IC_PUSH_I4: {
532                         sp--;
533                         *((gint32*)ap) = sp->data.i;
534                         d(printf ("IC_PUSH: %d\n", sp->data.i));
535                         ap += 4;
536                         break;
537                 }
538                 case IC_CALL_I4: {
539                         MonoMethod *m = (MonoMethod *)*((gint32*)ip);
540                         gpointer p;
541
542                         if (!m->addr)
543                                 arch_compile_method (m);
544
545                         p = sp [-1].data.p;
546
547                         INIT_FRAME (&child_frame, NULL, NULL, args, sp, m);
548                         
549                         interp_exec_method (&child_frame);
550                         d(printf ("RESULT: %d\n", sp->data.i));
551                         ap = args;
552
553                         sp++;
554                         ip += 4;
555                         break;
556                 }
557                 default:
558                         g_warning ("unknown interpreter opcode %d\n", *(ip -1));
559                         g_assert_not_reached ();
560                         break;
561                 }
562                 
563         }
564 }
565
566 static gint32
567 get_address (GPtrArray *forest, gint32 cli_addr, gint base, gint len)
568 {
569         gint32 ind, pos;
570         MBTree *t1;
571
572         ind = (len / 2);
573         pos = base + ind;
574
575         /* skip trees with cli_addr == -1 */
576         while ((t1 = (MBTree *) g_ptr_array_index (forest, pos)) &&
577                t1->cli_addr == -1 && ind) {
578                 ind--;
579                 pos--;
580         }
581
582         if (t1->cli_addr == cli_addr) {
583                 t1->jump_target = 1;
584                 return t1->first_addr;
585         }
586
587         if (len <= 1)
588                 return -1;
589
590         if (t1->cli_addr > cli_addr) {
591                 return get_address (forest, cli_addr, base, ind);
592         } else {
593                 ind = (len / 2);                
594                 return get_address (forest, cli_addr, base + ind, len - ind);
595         }
596 }
597
598 static void
599 compute_branches (MBCodeGenStatus *s)
600 {
601         GPtrArray *forest = s->forest;
602         const int top = forest->len;
603         gint32 addr;
604         guint8 *end;
605         int i;
606
607         end = s->code;
608
609         for (i = 0; i < top; i++) {
610                 MBTree *t1 = (MBTree *) g_ptr_array_index (forest, i);
611
612                 if (t1->is_jump) {
613
614                         if ((i + 1) < forest->len) {
615                                 MBTree *t2 = (MBTree *) g_ptr_array_index (forest, i + 1);
616                                 t2->jump_target = 1;
617                         }
618
619                         addr = get_address (forest, t1->data.i, 0, forest->len);
620                         if (addr == -1) {
621                                 g_error ("address 0x%x not found at IL_%04x",
622                                          t1->data.i, t1->cli_addr);
623                         }
624                         t1->data.i = addr - t1->addr;
625
626                         /* emit the jump instruction again to update addresses */
627                         s->code = s->start + t1->addr;
628                         ((MBEmitFunc)t1->emit) (t1, s);
629
630                 }
631         }
632
633         s->code = end;
634 }
635
636 static void
637 tree_emit (int goal, MBCodeGenStatus *s, MBTree *tree) 
638 {
639         MBTree *kids[10];
640         int i, ern = mono_burg_rule (tree->state, goal);
641         guint16 *nts = mono_burg_nts [ern];
642
643         mono_burg_kids (tree, ern, kids);
644
645         for (i = 0; nts [i]; i++) 
646                 tree_emit (nts [i], s, kids [i]);
647
648         tree->addr = s->code - s->start;
649
650         if ((tree->emit = mono_burg_func [ern]))
651                 ((MBEmitFunc)tree->emit) (tree, s);
652 }
653
654 static void
655 forest_emit (MBCodeGenStatus *s)
656 {
657         GPtrArray *forest = s->forest;
658         const int top = forest->len;
659         int i;
660                 
661         for (i = 0; i < top; i++) {
662                 MBTree *t1 = (MBTree *) g_ptr_array_index (forest, i);
663                 t1->first_addr = s->code - s->start;
664                 tree_emit (1, s, t1);
665         }
666 }
667
668 static void
669 emit_method (MonoMethod *method, MBCodeGenStatus *s)
670 {
671         method->addr = s->start = s->code = g_malloc (1024);
672
673         if (mono_jit_dump_forest)
674                 mono_print_forest (s->forest);
675
676         mono_jit_label_forest (s);
677
678         forest_emit (s);
679         compute_branches (s);
680
681
682         //if (mono_jit_dump_asm)
683         //      mono_disassemble_code (s->start, s->code - s->start);
684 }
685
686 gpointer
687 arch_compile_method (MonoMethod *method)
688 {
689         MBCodeGenStatus cgstat;
690         MonoMemPool *mp = mono_mempool_new ();
691         guint locals_size;
692
693         g_assert (!(method->iflags & METHOD_IMPL_ATTRIBUTE_INTERNAL_CALL));
694         g_assert (!(method->flags & METHOD_ATTRIBUTE_PINVOKE_IMPL));
695
696         printf ("Start JIT compilation of %s\n", method->name);
697
698         cgstat.forest = mono_create_forest (method, mp, &locals_size);
699         cgstat.code = NULL;
700         cgstat.mp = mp;
701
702         emit_method (method, &cgstat);
703
704         g_ptr_array_free (cgstat.forest, TRUE);
705
706         mono_mempool_destroy (mp);
707
708         return method->addr;
709 }
710
711 gpointer
712 arch_create_jit_trampoline (MonoMethod *method)
713 {
714
715         return NULL;
716 }
717
718 int
719 arch_exec (MonoMethod *method)
720 {
721         stackval result;
722         MonoInvocation call;
723
724         arch_compile_method (method);
725
726         INIT_FRAME (&call, NULL, NULL, NULL, &result, method);
727         
728         interp_exec_method (&call);
729
730         return result.data.i;
731 }