1 /* src/vm/jit/intrp/dynamic-super.c dynamic superinstruction support
3 Copyright (C) 1995,1996,1997,1998,2000,2003,2004 Free Software Foundation, Inc.
6 Copyright (C) 1996-2005, 2006, 2007, 2008
7 CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
9 This file is part of CACAO.
11 This program is free software; you can redistribute it and/or
12 modify it under the terms of the GNU General Public License as
13 published by the Free Software Foundation; either version 2, or (at
14 your option) any later version.
16 This program is distributed in the hope that it will be useful, but
17 WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 General Public License for more details.
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
29 #define NO_IP 0 /* proper native code, without interpreter's ip */
39 #include "mm/memory.hpp"
41 #include "threads/lock.hpp"
43 #include "toolbox/hashtable.h"
44 #include "toolbox/logging.hpp"
46 #include "vm/options.h"
48 #include "vm/jit/disass.h"
49 #include "vm/jit/intrp/intrp.h"
52 s4 no_super=0; /* option: just use replication, but no dynamic superinsts */
54 static char MAYBE_UNUSED superend[]={
55 #include <java-superend.i>
58 const char * const prim_names[]={
59 #include <java-names.i>
63 #define INST_ADDR(_inst) N_##_inst
64 #include <java-labels.i>
71 Label start; /* NULL if not relocatable */
72 s4 length; /* only includes the jump iff superend is true*/
73 s4 restlength; /* length of the rest (i.e., the jump or (on superend) 0) */
74 char superend; /* true if primitive ends superinstruction, i.e.,
75 unconditional branch, execute, etc. */
78 s4 offset; /* offset of immarg within prim */
79 char rel; /* true if immarg is relative */
80 } immargs[MAX_IMMARGS];
88 typedef struct superstart {
89 struct superstart *next;
90 s4 patcherm; /* offset of patcher, -1 if super has no patcher */
91 u4 length; /* length of superinstruction */
92 u1 *oldsuper; /* reused superinstruction: NULL if there is none */
99 static hashtable hashtable_patchersupers;
100 #define HASHTABLE_PATCHERSUPERS_BITS 14
102 #if defined(ENABLE_THREADS)
103 static java_objectheader *lock_hashtable_patchersupers;
106 /* stuff for -no-replication */
107 typedef struct superreuse {
108 struct superreuse *next;
113 static hashtable hashtable_superreuse;
114 #define HASHTABLE_SUPERREUSE_BITS 14
116 #if defined(ENABLE_THREADS)
117 static java_objectheader *lock_hashtable_superreuse;
120 # define debugp(x...) if (opt_verbose) fprintf(x)
121 #define debugp1(x...)
123 /* statistics variables */
125 u4 count_supers = 0; /* dynamic superinstructions, including replicas */
126 u4 count_supers_unique = 0; /* dynamic superinstructions, without replicas */
127 u4 count_supers_reused = 0; /* reused dynamic superinstructions */
128 u4 count_patchers_exec = 0; /* executed patchers */
129 u4 count_patchers_last = 0; /* executed last patchers */
130 u4 count_patchers_ins = 0; /* patchers inserted in patchersupers table */
131 u4 count_patchers = 0; /* superstarts with patcherm!=-1 */
132 u4 count_supers_nopatch= 0; /* superinstructions for code without patchers */
133 u4 count_supers_patch = 0; /* superinstructions for code with patchers */
134 u4 count_dispatches = 0; /* dynamic superinstructions generated */
135 u4 count_disp_nonreloc = 0; /* */
136 u4 count_insts_reloc = 0; /* relocatable insts compiled (append_prim) */
137 u4 count_insts = 0; /* compiled insts (gen_inst) */
138 u4 count_native_code = 0; /* native code bytes */
139 u4 count_native_saved = 0; /* reclaimed native code */
141 /* determine priminfos */
144 java_objectheader *engine2(Inst *ip0, Cell * sp, Cell * fp);
146 static int compare_labels(const void *pa, const void *pb)
148 char *a = *(char **)pa;
149 char *b = *(char **)pb;
153 static Label bsearch_next(Label key, Label *a, u4 n)
154 /* a is sorted; return the label >=key that is the closest in a;
155 return NULL if there is no label in a >=key */
167 return bsearch_next(key, a+mid+1, n-mid-1);
169 return bsearch_next(key, a, mid+1);
173 each VM instruction <x> looks like this:
176 I_<x>: /* entry point */
178 J_<x>: /* start of dispatch */
179 NEXT_P1_5; /* dispatch except GOTO */
180 K_<x>: /* just before goto */
181 DO_GOTO; /* goto part of dispatch */
184 * We need I_<x> for threaded code: this is the code address stored in
185 * direct threaded code.
187 * We need the <skip> to detect non-relocatability (by comparing
188 * engine and engine2 with different skips). H_<x> is there to ensure
189 * that gcc does not think that <skip> is dead code.
191 * We need J_<x> to implement dynamic superinstructions: copy
192 * everything between I_<x> and J_<x> to get a VM instruction without
195 * At the end of a dynamic superinstruction we need a dispatch. We
196 * need the DO_GOTO to work around gcc bug 15242: we copy everything
197 * up to K_<x> and then copy the indirect jump from &&before_goto.
202 static void check_prims(Label symbols1[])
205 Label *symbols2, *symbols3, *js1, *ks1, *ks1sorted;
206 Label after_goto, before_goto2;
210 fprintf(stderr, "Compiled with gcc-" __VERSION__ "\n");
212 for (i=0; symbols1[i]!=0; i++)
219 symbols2=(Inst *)engine2(0,0,0);
221 symbols3=(Inst *)engine3(0,0,0);
227 before_goto = ks1[i+1]; /* after ks and after after_last */
228 after_goto = ks1[i+2];
229 before_goto2 = (ks1+(symbols2-symbols1))[i+1];
230 /* some gccs reorder the code; below we look for the next K label
231 with binary search, and whether it belongs to the current
232 instruction; prepare for this by sorting the K labels */
233 ks1sorted = (Label *)alloca((i+1)*sizeof(Label));
234 MCOPY(ks1sorted,ks1,Label,i+1);
235 qsort(ks1sorted, i+1, sizeof(Label), compare_labels);
237 /* check whether the "goto *" is relocatable */
238 goto_len = after_goto-before_goto;
239 debugp(stderr, "goto * %p %p len=%d\n",
240 before_goto,before_goto2,goto_len);
241 if (memcmp(before_goto, before_goto2, goto_len)!=0) { /* unequal */
242 opt_no_dynamic = true;
243 debugp(stderr," not relocatable, disabling dynamic code generation\n");
247 priminfos = calloc(i,sizeof(PrimInfo));
248 for (i=0; symbols1[i]!=0; i++) {
249 /* check whether the VM instruction i has the same code in
250 symbols1 and symbols2 (then it is relocatable). Also, for real
251 native code (not activated), check where the versions in
252 symbols1 and symbols 3 differ; these are places for
254 int prim_len = js1[i]-symbols1[i];
255 PrimInfo *pi=&priminfos[i];
257 char *s1 = (char *)symbols1[i];
258 char *s2 = (char *)symbols2[i];
259 char *s3 = (char *)symbols3[i];
260 Label endlabel = bsearch_next(s1+1,ks1sorted,npriminfos+1);
263 pi->superend = superend[i]|no_super;
264 pi->length = prim_len;
265 pi->restlength = endlabel - symbols1[i] - pi->length;
268 debugp(stderr, "%-15s %3d %p %p %p len=%3ld restlen=%2ld s-end=%1d",
269 prim_names[i], i, s1, s2, s3, (long)(pi->length), (long)(pi->restlength), pi->superend);
270 if (endlabel == NULL) {
271 pi->start = NULL; /* not relocatable */
272 if (pi->length<0) pi->length=1000;
273 debugp(stderr,"\n non_reloc: no K label > start found\n");
276 if (js1[i] > endlabel && !pi->superend) {
277 pi->start = NULL; /* not relocatable */
278 pi->length = endlabel-symbols1[i];
279 debugp(stderr,"\n non_reloc: there is a K label before the J label (restlength<0)\n");
282 if (js1[i] < pi->start && !pi->superend) {
283 pi->start = NULL; /* not relocatable */
284 pi->length = endlabel-symbols1[i];
285 debugp(stderr,"\n non_reloc: J label before I label (length<0)\n");
288 assert(pi->length>=0);
289 assert(pi->restlength >=0);
290 while (j<(pi->length+pi->restlength)) {
292 if (s1[j] != s2[j]) {
293 pi->start = NULL; /* not relocatable */
294 debugp(stderr,"\n non_reloc: engine1!=engine2 offset %3d",j);
295 /* assert(j<prim_len); */
300 /* only used for NO_IP native code generation */
301 /* here we find differences in inline arguments */
310 static bool is_relocatable(ptrint p)
312 return !opt_no_dynamic && priminfos[p].start != NULL;
316 void append_prim(codegendata *cd, ptrint p)
318 PrimInfo *pi = &priminfos[p];
319 debugp1(stderr,"append_prim %p %s\n",cd->lastmcodeptr, prim_names[p]);
320 if (cd->ncodeptr + pi->length + pi->restlength + goto_len >
321 cd->ncodebase + cd->ncodesize) {
322 cd->ncodeptr = codegen_ncode_increase(cd, cd->ncodeptr);
324 memcpy(cd->ncodeptr, pi->start, pi->length);
325 cd->ncodeptr += pi->length;
329 static void init_dynamic_super(codegendata *cd)
331 cd->lastpatcheroffset = -1;
332 cd->dynsuperm = -1; /* the next VM instr may be non-relocatable */
333 cd->dynsupern = cd->ncodeptr - cd->ncodebase;
337 /******************* -no-replication stuff **********************/
339 /* bugs: superinstructions are inserted into the table only after the
340 end of a method, so there may be replication within a method even
341 with -no-replication. Moreover, there is a race condition that can
342 cause varying amounts of replication between different threads;
343 this could only be avoided by eliminating the bug above and having
346 static u4 hash_superreuse(u1 *code, u4 length)
347 /* calculates a hash value for given code length */
352 for (i=0; i<(length&(~3)); i+=sizeof(u4)) {
353 r += *(s4 *)(code+i); /* !! align each superinstruction */
355 return (r+(r>>HASHTABLE_SUPERREUSE_BITS))&((1<<HASHTABLE_SUPERREUSE_BITS)-1);
358 static void superreuse_insert(u1 *code, u4 length)
360 u4 slot = hash_superreuse(code, length);
361 superreuse **listp = (superreuse **)&hashtable_superreuse.ptr[slot];
362 superreuse *sr = NEW(superreuse);
366 LOCK_MONITOR_ENTER(lock_hashtable_superreuse);
371 LOCK_MONITOR_EXIT(lock_hashtable_superreuse);
373 count_supers_unique++;
376 static u1 *superreuse_lookup(u1 *code, u4 length)
377 /* returns earlier instances code address, or NULL */
379 u4 slot = hash_superreuse(code, length);
380 superreuse *sr = (superreuse *)hashtable_superreuse.ptr[slot];
381 /* since there is another race condition anyway, we don't bother
382 locking here; both race conditions don't affect the correctness */
383 for (; sr != NULL; sr = sr->next)
384 if (length == sr->length && memcmp(code, sr->code, length)==0)
389 /******************* patcher stuff *******************************/
391 void patchersuper_rewrite(Inst *p)
392 /* p is the address of a patcher; if this is the last patcher in
393 a dynamic superinstruction, rewrite the threaded code to use
394 the dynamic superinstruction; the data for that comes from
395 hashtable_patchersupers */
397 ptrint key = (ptrint)p;
398 u4 slot = ((key + (key>>HASHTABLE_PATCHERSUPERS_BITS)) &
399 ((1<<HASHTABLE_PATCHERSUPERS_BITS)-1));
400 superstart **listp = (superstart **)&hashtable_patchersupers.ptr[slot];
402 count_patchers_exec++;
404 LOCK_MONITOR_ENTER(lock_hashtable_patchersupers);
406 for (; ss=*listp, ss!=NULL; listp = &(ss->next)) {
407 if (p == ((Inst *)(ss->mcodebase + ss->patcherm))) {
409 if (ss->oldsuper != NULL)
410 target = (Inst)ss->oldsuper;
412 target = (Inst)(ss->ncodebase + ss->dynsupern);
413 *(Inst *)(ss->mcodebase + ss->dynsuperm) = target;
414 debugp1(stderr, "patcher rewrote %p into %p\n",
415 ss->mcodebase + ss->dynsuperm, target);
417 FREE(ss, superstart);
418 count_patchers_last++;
423 LOCK_MONITOR_EXIT(lock_hashtable_patchersupers);
426 static void hashtable_patchersupers_insert(superstart *ss)
428 ptrint key = (ptrint)(ss->mcodebase + ss->patcherm);
429 u4 slot = ((key + (key>>HASHTABLE_PATCHERSUPERS_BITS)) &
430 ((1<<HASHTABLE_PATCHERSUPERS_BITS)-1));
431 void **listp = &hashtable_patchersupers.ptr[slot];
433 LOCK_MONITOR_ENTER(lock_hashtable_patchersupers);
435 ss->next = (superstart *)*listp;
438 LOCK_MONITOR_EXIT(lock_hashtable_patchersupers);
440 count_patchers_ins++;
443 void dynamic_super_rewrite(codegendata *cd)
444 /* rewrite the threaded code in the superstarts list to point to
445 the dynamic superinstructions */
447 superstart *ss = cd->superstarts;
449 for (; ss != NULL; ss = ssnext) {
451 if (opt_no_replication && ss->oldsuper == NULL)
452 superreuse_insert(cd->ncodebase + ss->dynsupern, ss->length);
453 if (ss->patcherm == -1) {
454 assert(ss->oldsuper == NULL);
455 *(Inst *)(cd->mcodebase + ss->dynsuperm) =
456 (Inst)(cd->ncodebase + ss->dynsupern);
457 debugp1(stderr, "rewrote %p into %p\n",
458 cd->mcodebase + ss->dynsuperm, cd->ncodebase + ss->dynsupern);
459 count_supers_nopatch++;
461 /* fprintf(stderr,"%p stage2\n", ss); */
462 ss->mcodebase = cd->mcodebase;
463 ss->ncodebase = cd->ncodebase;
464 hashtable_patchersupers_insert(ss);
465 count_supers_patch++;
470 static void new_dynamic_super(codegendata *cd)
471 /* add latest dynamic superinstruction to the appropriate table
472 for rewriting the threaded code either on relocation (if there
473 is no patcher), or when the last patcher is executed (if there
478 u1 *code = cd->ncodebase + cd->dynsupern;
479 u4 length = cd->ncodeptr - code;
481 if (opt_no_replication) {
482 oldsuper = superreuse_lookup(code, length);
483 if (oldsuper != NULL) {
484 count_supers_reused++;
485 count_native_saved += length;
487 if (cd->lastpatcheroffset == -1) {
488 *(Inst *)(cd->mcodebase + cd->dynsuperm) = (Inst)oldsuper;
489 debugp1(stderr, "rewrote %p into %p (reused)\n",
490 cd->mcodebase + ss->dynsuperm, oldsuper);
495 if (cd->lastpatcheroffset == -1) {
496 ss = DNEW(superstart);
498 ss = NEW(superstart);
500 /* fprintf(stderr,"%p stage1\n", ss); */
502 ss->patcherm = cd->lastpatcheroffset;
503 ss->oldsuper = oldsuper;
505 ss->dynsuperm = cd->dynsuperm;
506 ss->dynsupern = cd->dynsupern;
507 ss->next = cd->superstarts;
508 cd->superstarts = ss;
509 count_native_code += cd->ncodeptr - code;
512 void append_dispatch(codegendata *cd)
514 debugp1(stderr,"append_dispatch %p\n",cd->lastmcodeptr);
515 if (cd->lastinstwithoutdispatch != ~0) {
516 PrimInfo *pi = &priminfos[cd->lastinstwithoutdispatch];
518 memcpy(cd->ncodeptr, pi->start + pi->length, pi->restlength);
519 cd->ncodeptr += pi->restlength;
520 memcpy(cd->ncodeptr, before_goto, goto_len);
521 cd->ncodeptr += goto_len;
522 cd->lastinstwithoutdispatch = ~0;
523 new_dynamic_super(cd);
526 init_dynamic_super(cd);
529 static void compile_prim_dyn(codegendata *cd, ptrint p)
530 /* compile prim #p dynamically (mod flags etc.) */
534 assert(p<npriminfos);
535 if (!is_relocatable(p)) {
536 if (cd->lastinstwithoutdispatch != ~0) /* only count real dispatches */
537 count_disp_nonreloc++;
538 append_dispatch(cd); /* to previous dynamic superinstruction */
541 if (cd->dynsuperm == -1)
542 cd->dynsuperm = cd->lastmcodeptr - cd->mcodebase;
544 cd->lastinstwithoutdispatch = p;
545 if (priminfos[p].superend)
550 static void replace_patcher(codegendata *cd, ptrint p)
551 /* compile p dynamically, and note that there is a patcher here */
553 if (opt_no_quicksuper) {
556 cd->lastpatcheroffset = cd->lastmcodeptr - cd->mcodebase;
557 compile_prim_dyn(cd, p);
561 void gen_inst1(codegendata *cd, ptrint instr)
563 /* actually generate the threaded code instruction */
565 debugp1(stderr, "gen_inst %p, %s\n", cd->lastmcodeptr, prim_names[instr]);
566 *((Inst *) cd->lastmcodeptr) = vm_prim[instr];
568 case N_PATCHER_ACONST: replace_patcher(cd, N_ACONST1); break;
569 case N_PATCHER_ARRAYCHECKCAST: replace_patcher(cd, N_ARRAYCHECKCAST); break;
570 case N_PATCHER_GETSTATIC_INT: replace_patcher(cd, N_GETSTATIC_INT); break;
571 case N_PATCHER_GETSTATIC_LONG: replace_patcher(cd, N_GETSTATIC_LONG); break;
572 case N_PATCHER_GETSTATIC_CELL: replace_patcher(cd, N_GETSTATIC_CELL); break;
573 case N_PATCHER_PUTSTATIC_INT: replace_patcher(cd, N_PUTSTATIC_INT); break;
574 case N_PATCHER_PUTSTATIC_LONG: replace_patcher(cd, N_PUTSTATIC_LONG); break;
575 case N_PATCHER_PUTSTATIC_CELL: replace_patcher(cd, N_PUTSTATIC_CELL); break;
576 case N_PATCHER_GETFIELD_INT: replace_patcher(cd, N_GETFIELD_INT); break;
577 case N_PATCHER_GETFIELD_LONG: replace_patcher(cd, N_GETFIELD_LONG); break;
578 case N_PATCHER_GETFIELD_CELL: replace_patcher(cd, N_GETFIELD_CELL); break;
579 case N_PATCHER_PUTFIELD_INT: replace_patcher(cd, N_PUTFIELD_INT); break;
580 case N_PATCHER_PUTFIELD_LONG: replace_patcher(cd, N_PUTFIELD_LONG); break;
581 case N_PATCHER_PUTFIELD_CELL: replace_patcher(cd, N_PUTFIELD_CELL); break;
582 case N_PATCHER_MULTIANEWARRAY: replace_patcher(cd, N_MULTIANEWARRAY); break;
583 case N_PATCHER_INVOKESTATIC: replace_patcher(cd, N_INVOKESTATIC); break;
584 case N_PATCHER_INVOKESPECIAL: replace_patcher(cd, N_INVOKESPECIAL); break;
585 case N_PATCHER_INVOKEVIRTUAL: replace_patcher(cd, N_INVOKEVIRTUAL); break;
586 case N_PATCHER_INVOKEINTERFACE:replace_patcher(cd, N_INVOKEINTERFACE); break;
587 case N_PATCHER_CHECKCAST: replace_patcher(cd, N_CHECKCAST); break;
588 case N_PATCHER_INSTANCEOF: replace_patcher(cd, N_INSTANCEOF); break;
589 case N_PATCHER_NATIVECALL:
591 replace_patcher(cd, N_TRACENATIVECALL);
593 replace_patcher(cd, N_NATIVECALL);
595 case N_TRANSLATE: break;
598 compile_prim_dyn(cd, instr);
604 void finish_ss(codegendata *cd)
605 /* conclude the last static super and compile it dynamically */
608 if (cd->lastmcodeptr != NULL) {
609 gen_inst1(cd, *(ptrint *)(cd->lastmcodeptr));
610 cd->lastmcodeptr = NULL;
616 void gen_inst(codegendata *cd, ptrint instr)
618 cd->lastmcodeptr = cd->mcodeptr;
619 gen_inst1(cd, instr);
620 cd->mcodeptr += sizeof(Inst);
621 cd->lastmcodeptr = NULL;
624 void gen_inst(codegendata *cd, ptrint instr)
626 /* vmgen-0.6.2 generates gen_... calls with Inst ** as first
627 parameter, but we need to pass in cd to make lastmcodeptr
629 ptrint *lastmcodeptr = (ptrint *)cd->lastmcodeptr;
631 if (lastmcodeptr != NULL) {
634 assert((u1 *) lastmcodeptr < cd->mcodeptr &&
635 cd->mcodeptr < (u1 *) (lastmcodeptr + 40));
637 combo = peephole_opt(*lastmcodeptr, instr, peeptable);
640 *lastmcodeptr = combo;
646 /* actually generate the threaded code instruction */
648 *((Inst *) cd->mcodeptr) = (Inst) instr;
650 cd->lastmcodeptr = cd->mcodeptr;
651 cd->mcodeptr += sizeof(Inst);
655 void print_dynamic_super_statistics(void)
657 dolog("count_supers = %d", count_supers );
658 dolog("count_supers_unique = %d", count_supers_unique );
659 dolog("count_supers_reused = %d", count_supers_reused );
660 dolog("count_patchers_exec = %d", count_patchers_exec );
661 dolog("count_patchers_last = %d", count_patchers_last );
662 dolog("count_patchers_ins = %d", count_patchers_ins );
663 dolog("count_patchers = %d", count_patchers );
664 dolog("count_supers_nopatch= %d", count_supers_nopatch);
665 dolog("count_supers_patch = %d", count_supers_patch );
666 dolog("count_dispatches = %d", count_dispatches );
667 dolog("count_disp_nonreloc = %d", count_disp_nonreloc );
668 dolog("count_insts_reloc = %d", count_insts_reloc );
669 dolog("count_insts = %d", count_insts );
670 dolog("count_native_code = %d", count_native_code );
671 dolog("count_native_saved = %d", count_native_saved );
674 #if defined(ENABLE_DISASSEMBLER)
675 void disassemble_prim(int n)
677 PrimInfo *p = &(priminfos[n]);
678 u1 *start = vm_prim[n];
680 #if defined(ENABLE_JIT)
681 printf("%s (len=%d, restlen=%d):\n",prim_names[n],p->length, p->restlength);
682 disassemble(start, start + p->length + p->restlength);
685 #endif /* defined(ENABLE_DISASSEMBLER) */
687 void dynamic_super_init(void)
689 check_prims(vm_prim);
691 #if defined(ENABLE_DISASSEMBLER)
693 disassemble_prim(N_IADD);
694 disassemble_prim(N_ILOAD);
695 disassemble_prim(N_GETFIELD_INT);
699 hashtable_create(&hashtable_patchersupers, 1<<HASHTABLE_PATCHERSUPERS_BITS);
700 if (opt_no_replication)
701 hashtable_create(&hashtable_superreuse, 1<<HASHTABLE_SUPERREUSE_BITS);
703 #if defined(ENABLE_THREADS)
704 /* create patchersupers hashtable lock object */
706 lock_hashtable_patchersupers = NEW(java_objectheader);
707 lock_hashtable_superreuse = NEW(java_objectheader);
709 lock_init_object_lock(lock_hashtable_patchersupers);
710 lock_init_object_lock(lock_hashtable_superreuse);