rapid type analysis - carolyn
[cacao.git] / global.h
1 /* global.h ********************************************************************
2
3         Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst
4
5         See file COPYRIGHT for information on usage and disclaimer of warranties
6
7         Contains global definitions which are used in the whole program, includes
8         some files and contains global used macros.
9
10         Authors: Reinhard Grafl              EMAIL: cacao@complang.tuwien.ac.at
11                  Andreas  Krall   (andi)     EMAIL: cacao@complang.tuwien.ac.at
12         Changes: Mark     Probst  (schani)   EMAIL: cacao@complang.tuwien.ac.at
13                          Philipp  Tomsich (phil)     EMAIL: cacao@complang.tuwien.ac.at
14
15         Last Change: $Id: global.h 274 2003-05-09 13:39:39Z carolyn $
16
17 *******************************************************************************/
18
19 #ifndef __global_h_
20 #define __global_h_
21
22 #include "config.h"
23
24 #define NEW_GC              /* if enabled, includes the new gc. -- phil.      */
25
26 #define STATISTICS          /* if enabled collects program statistics         */
27
28 /* 
29  * JIT_MARKER_SUPPORT is the define used to toggle Just-in-time generated
30  * marker functions on and off.
31  *
32  * SIZE_FROM_CLASSINFO toggles between the bitmap_based and the new method 
33  * of determining the sizes of objects on the heap.
34  */
35 #undef JIT_MARKER_SUPPORT        /* phil */
36 #define SIZE_FROM_CLASSINFO
37
38 /* standard includes **********************************************************/
39
40 #include <stdio.h>
41 #include <stdlib.h>
42 #include <string.h>
43 #include <time.h>
44
45 #include "toolbox/memory.h"
46 #include "toolbox/chain.h"
47 #include "toolbox/list.h"
48 #include "toolbox/loging.h"
49
50 /* system dependent types *****************************************************/
51
52 #include "types.h"
53
54
55 /* additional data types ******************************************************/
56
57 typedef void *voidptr;          /* generic pointer */
58
59 typedef int   bool;             /* boolean data type */
60
61 #define true  1
62 #define false 0
63
64 #define PRIMITIVETYPE_COUNT  9  /* number of primitive types */
65
66 typedef void (*functionptr) (); /* generic function pointer */
67
68
69 #define MAX_ALIGN 8             /* most generic alignment for JavaVM values   */
70
71
72 /* shutdown function **********************************************************/
73
74 void cacao_shutdown(s4 status);
75
76
77 /* basic data types ***********************************************************/
78
79 #define TYPE_INT      0         /* the JavaVM types must numbered in the      */
80 #define TYPE_LONG     1         /* same order as the ICMD_Ixxx to ICMD_Axxx   */
81 #define TYPE_FLOAT    2         /* instructions (LOAD and STORE)              */
82 #define TYPE_DOUBLE   3         /* integer, long, float, double, address      */
83 #define TYPE_ADDRESS  4         /* all other types can be numbered arbitrarly */
84
85 #define TYPE_VOID    10
86
87
88 /* Java class file constants **************************************************/
89
90 #define MAGIC         0xcafebabe
91 #define MINOR_VERSION 3
92 #define MAJOR_VERSION 45
93
94 #define CONSTANT_Class                 7
95 #define CONSTANT_Fieldref              9
96 #define CONSTANT_Methodref            10
97 #define CONSTANT_InterfaceMethodref   11
98 #define CONSTANT_String                8
99 #define CONSTANT_Integer               3
100 #define CONSTANT_Float                 4
101 #define CONSTANT_Long                  5
102 #define CONSTANT_Double                6
103 #define CONSTANT_NameAndType          12
104 #define CONSTANT_Utf8                  1
105
106 #define CONSTANT_Arraydescriptor      13
107 #define CONSTANT_UNUSED                0
108
109 #define ACC_PUBLIC                0x0001
110 #define ACC_PRIVATE               0x0002
111 #define ACC_PROTECTED             0x0004
112 #define ACC_STATIC                0x0008
113 #define ACC_FINAL                 0x0010
114 #define ACC_SYNCHRONIZED          0x0020
115 #define ACC_VOLATILE              0x0040
116 #define ACC_TRANSIENT             0x0080
117 #define ACC_NATIVE                0x0100
118 #define ACC_INTERFACE             0x0200
119 #define ACC_ABSTRACT              0x0400
120
121
122 /* resolve typedef cycles *****************************************************/
123
124 typedef struct utf utf;
125 typedef struct literalstring literalstring;
126 typedef struct java_objectheader java_objectheader; 
127 typedef struct classinfo classinfo; 
128 typedef struct vftbl vftbl;
129 typedef u1* methodptr;
130
131
132 /* constant pool entries *******************************************************
133
134         All constant pool entries need a data structure which contain the entrys
135         value. In some cases this structure exist already, in the remaining cases
136         this structure must be generated:
137
138                 kind                      structure                     generated?
139         ----------------------------------------------------------------------
140     CONSTANT_Class               classinfo                           no
141     CONSTANT_Fieldref            constant_FMIref                    yes
142     CONSTANT_Methodref           constant_FMIref                    yes
143     CONSTANT_InterfaceMethodref  constant_FMIref                    yes
144     CONSTANT_String              unicode                             no
145     CONSTANT_Integer             constant_integer                   yes
146     CONSTANT_Float               constant_float                     yes
147     CONSTANT_Long                constant_long                      yes
148     CONSTANT_Double              constant_double                    yes
149     CONSTANT_NameAndType         constant_nameandtype               yes
150     CONSTANT_Utf8                unicode                             no
151     CONSTANT_Arraydescriptor     constant_arraydescriptor           yes
152     CONSTANT_UNUSED              -
153
154 *******************************************************************************/
155
156 /* data structures for hashtables ********************************************
157
158
159         All utf-symbols, javastrings and classes are stored in global hashtables,
160         so every symbol exists only once. Equal symbols have identical pointers.
161         The functions for adding hashtable elements search the table for the 
162         element with the specified name/text and return it on success. Otherwise a 
163         new hashtable element is created.
164
165     The hashtables use external linking for handling collisions. The hashtable 
166         structure contains a pointer <ptr> to the array of hashtable slots. The 
167         number of hashtable slots and therefore the size of this array is specified 
168         by the element <size> of hashtable structure. <entries> contains the number
169         of all hashtable elements stored in the table, including those in the 
170         external chains.
171         The hashtable element structures (utf, literalstring, classinfo) contain
172         both a pointer to the next hashtable element as a link for the external hash 
173         chain and the key of the element. The key is computed from the text of
174         the string or the classname by using up to 8 characters.
175         
176         If the number of entries in the hashtable exceeds twice the size of the 
177         hashtableslot-array it is supposed that the average length of the 
178         external chains has reached a value beyond 2. Therefore the functions for
179         adding hashtable elements (utf_new, class_new, literalstring_new) double
180         the hashtableslot-array. In this restructuring process all elements have
181         to be inserted into the new hashtable and new external chains must be built.
182
183
184 example for the layout of a hashtable:
185
186 hashtable.ptr-->  +-------------------+
187                   |                   |
188                            ...
189                   |                   |
190                   +-------------------+   +-------------------+   +-------------------+
191                   | hashtable element |-->| hashtable element |-->| hashtable element |-->NULL
192                   +-------------------+   +-------------------+   +-------------------+
193                   | hashtable element |
194                   +-------------------+   +-------------------+   
195                   | hashtable element |-->| hashtable element |-->NULL
196                   +-------------------+   +-------------------+   
197                   | hashtable element |-->NULL
198                   +-------------------+
199                   |                   |
200                            ...
201                   |                   |
202                   +-------------------+
203
204 */
205
206
207 /* data structure for utf8 symbols ********************************************/
208
209 struct utf {
210         utf        *hashlink;       /* link for external hash chain               */
211         int         blength;        /* text length in bytes                       */           
212         char       *text;           /* pointer to text                            */
213 };
214
215 /* data structure of internal javastrings stored in global hashtable **********/
216
217 struct literalstring {
218         literalstring     *hashlink;     /* link for external hash chain          */
219         java_objectheader *string;  
220 };
221
222 /* data structure for accessing hashtables ************************************/
223
224 typedef struct {            
225   u4 size;
226   u4 entries;        /* number of entries in the table */
227   void **ptr;        /* pointer to hashtable */
228 } hashtable;
229
230 /* data structures of remaining constant pool entries *************************/
231
232 typedef struct {                /* Fieldref, Methodref and InterfaceMethodref     */
233         classinfo *class;       /* class containing this field/method/interface   */
234         utf       *name;        /* field/method/interface name                    */
235         utf       *descriptor;  /* field/method/interface type descriptor string  */
236 } constant_FMIref;
237
238 typedef struct {            /* Integer                                        */
239         s4 value;
240 } constant_integer;
241         
242 typedef struct {            /* Float                                          */
243         float value;
244 } constant_float;
245
246 typedef struct {            /* Long                                           */
247         s8 value;
248 } constant_long;
249         
250 typedef struct {            /* Double                                         */
251         double value;
252 } constant_double;
253
254 typedef struct {            /* NameAndType (Field or Method)                  */
255         utf *name;              /* field/method name                              */
256         utf *descriptor;        /* field/method type descriptor string            */
257 } constant_nameandtype;
258
259 /*  arraydescriptor describes array types. Basic array types contain their
260         type in the arraytype field, objectclass contains a class pointer for
261         arrays of objects (arraytype == ARRAYTYPE_OBJECT), elementdescriptor
262         contains a pointer to an arraydescriptor which describes the element
263         types in the case of arrays of arrays (arraytype == ARRAYTYPE_ARRAY).
264 */
265
266 typedef struct constant_arraydescriptor {
267         int arraytype;
268         classinfo *objectclass;
269         struct constant_arraydescriptor *elementdescriptor;
270 } constant_arraydescriptor;
271
272
273 /* data structures of the runtime system **************************************/
274
275 /* objects *********************************************************************
276
277         All objects (and arrays) which resides on the heap need the following
278         header at the beginning of the data structure.
279 */
280
281 struct java_objectheader {              /* header for all objects             */
282         vftbl *vftbl;                       /* pointer to virtual function table  */
283 };
284
285
286
287 /* arrays **********************************************************************
288
289         All arrays are objects (they need the object header with a pointer to a
290         vvftbl (array class table). There is only one class for all arrays. The
291         type of an array is stored directly in the array object. Following types
292         are defined:
293 */
294
295 #define ARRAYTYPE_INT      0
296 #define ARRAYTYPE_LONG     1
297 #define ARRAYTYPE_FLOAT    2
298 #define ARRAYTYPE_DOUBLE   3
299 #define ARRAYTYPE_BYTE     4
300 #define ARRAYTYPE_CHAR     5
301 #define ARRAYTYPE_SHORT    6
302 #define ARRAYTYPE_BOOLEAN  7
303 #define ARRAYTYPE_OBJECT   8
304 #define ARRAYTYPE_ARRAY    9
305
306 typedef struct java_arrayheader {       /* header for all arrays              */
307         java_objectheader objheader;        /* object header                      */
308         s4 size;                            /* array size                         */
309 #ifdef SIZE_FROM_CLASSINFO
310         s4 alignedsize; /* phil */
311 #endif
312         s4 arraytype;                       /* array type from previous list      */
313 } java_arrayheader;
314
315
316
317 /* structs for all kinds of arrays ********************************************/
318
319 typedef struct java_chararray {
320         java_arrayheader header;
321         u2 data[1];
322 } java_chararray;
323
324 typedef struct java_floatheader {
325         java_arrayheader header;
326         float data[1];
327 } java_floatarray;
328
329 typedef struct java_doublearray {
330         java_arrayheader header;
331         double data[1];
332 } java_doublearray;
333
334 /*  booleanarray and bytearray need identical memory layout (access methods
335     use the same machine code */
336
337 typedef struct java_booleanarray {
338         java_arrayheader header;
339         u1 data[1];
340 } java_booleanarray;
341
342 typedef struct java_bytearray {
343         java_arrayheader header;
344         s1 data[1];
345 } java_bytearray;
346
347 typedef struct java_shortarray {
348         java_arrayheader header;
349         s2 data[1];
350 } java_shortarray;
351
352 typedef struct java_intarray {
353         java_arrayheader header;
354         s4 data[1];
355 } java_intarray;
356
357 typedef struct java_longarray {
358         java_arrayheader header;
359         s8 data[1];
360 } java_longarray;
361
362 /*  objectarray and arrayarray need identical memory layout (access methods
363     use the same machine code */
364
365 typedef struct java_objectarray {
366         java_arrayheader header;
367         classinfo *elementtype;
368         java_objectheader *data[1];
369 } java_objectarray;
370
371 typedef struct java_arrayarray {
372         java_arrayheader header;
373         constant_arraydescriptor *elementdescriptor;
374         java_arrayheader *data[1];
375 } java_arrayarray;
376
377
378 /* structure for primitive classes ********************************************/
379
380 typedef struct primitivetypeinfo {
381         classinfo *class_wrap;               /* class for wrapping primitive type */
382         classinfo *class_primitive;          /* primitive class                   */
383         char *wrapname;                      /* name of class for wrapping        */
384         char typesig;                        /* one character type signature      */
385         char *name;                          /* name of primitive class           */
386 } primitivetypeinfo;
387
388 /* field, method and class structures *****************************************/
389
390 /* fieldinfo ******************************************************************/
391
392 typedef struct fieldinfo {/* field of a class                                 */
393         s4       flags;       /* ACC flags                                        */
394         s4       type;        /* basic data type                                  */
395         utf *name;            /* name of field                                    */
396         utf *descriptor;      /* JavaVM descriptor string of field                */
397         
398         s4       offset;      /* offset from start of object (instance variables) */
399
400         union {               /* storage for static values (class variables)      */
401                 s4 i; 
402                 s8 l;
403                 float f;
404                 double d;
405                 void *a; 
406         } value;
407
408 } fieldinfo;
409
410 struct basicblock;
411
412 /* exceptiontable *************************************************************/
413
414 typedef struct xtable { /* exceptiontable entry in a method           */ 
415         s4         startpc;         /* start pc of guarded area (inclusive)       */
416         struct basicblock *start;
417
418         s4         endpc;           /* end pc of guarded area (exklusive)         */
419         struct basicblock *end;
420
421         s4         handlerpc;       /* pc of exception handler                    */
422         struct basicblock *handler;
423
424         classinfo *catchtype;       /* catchtype of exception (NULL == catchall)  */
425         struct xtable *next;        /* used to build a list of exception when     */
426                                     /* loops are copied */
427         struct xtable *down;        /* instead of the old array, a list is used   */
428 } xtable;
429
430
431 typedef struct exceptiontable { /* exceptiontable entry in a method           */ 
432         s4         startpc;         /* start pc of guarded area (inclusive)       */
433         s4         endpc;           /* end pc of guarded area (exklusive)         */
434         s4         handlerpc;       /* pc of exception handler                    */
435         classinfo *catchtype;       /* catchtype of exception (NULL == catchall)  */
436 } exceptiontable;
437
438
439 /* methodinfo *****************************************************************/
440
441 typedef struct methodinfo {         /* method structure                       */
442         s4             flags;               /* ACC flags                              */
443         utf       *name;                /* name of method                         */
444         utf       *descriptor;          /* JavaVM descriptor string of method     */
445         s4         returntype;          /* only temporary valid, return type      */
446         s4         paramcount;          /* only temporary valid, parameter count  */
447         u1        *paramtypes;          /* only temporary valid, parameter types  */
448         classinfo *class;               /* class, the method belongs to           */
449         s4         vftblindex;          /* index of method in virtual function table
450                                            (if it is a virtual method)            */
451         s4         maxstack;            /* maximum stack depth of method          */
452         s4         maxlocals;           /* maximum number of local variables      */
453         s4         jcodelength;         /* length of JavaVM code                  */
454         u1        *jcode;               /* pointer to JavaVM code                 */
455
456         s4         exceptiontablelength;/* exceptiontable length                  */
457         exceptiontable *exceptiontable; 
458                                     /* the exceptiontable                     */
459
460         u1        *stubroutine;         /* stub for compiling or calling natives  */    
461         s4         mcodelength;         /* legth of generated machine code        */
462         u1        *mcode;               /* pointer to machine code                */
463         u1        *entrypoint;          /* entry point in machine code            */
464
465         s4        methodUsed; /* -1=marked (might be used) 0=not used 1=used CO-RT*/
466
467 } methodinfo;
468
469
470 /* innerclassinfo *************************************************************/
471
472 typedef struct innerclassinfo {
473         classinfo *inner_class;       /* inner class pointer                      */
474         classinfo *outer_class;       /* outer class pointer                      */
475         utf *name;                    /* innerclass name                          */ 
476         s4 flags;                     /* ACC flags                                */
477 } innerclassinfo;
478
479 /* classinfo ******************************************************************/
480
481 struct classinfo {                /* class structure                          */
482         java_objectheader header;     /* classes are also objects                 */
483
484         s4          flags;            /* ACC flags                                */
485         utf        *name;             /* class name                               */ 
486
487         s4          cpcount;          /* number of entries in constant pool       */
488         u1         *cptags;           /* constant pool tags                       */
489         voidptr    *cpinfos;          /* pointer to constant pool info structures */
490
491         classinfo  *super;            /* super class pointer                      */
492         classinfo  *sub;              /* sub class pointer                        */
493         classinfo  *nextsub;          /* pointer to next class in sub class list  */
494
495         s4          interfacescount;  /* number of interfaces                     */
496         classinfo **interfaces;       /* pointer to interfaces                    */
497
498         s4          fieldscount;      /* number of fields                         */
499         fieldinfo  *fields;           /* field table                              */
500
501         s4          methodscount;     /* number of methods                        */
502         methodinfo *methods;          /* method table                             */
503
504         listnode    listnode;         /* linkage                                  */
505
506         bool        initialized;      /* true, if class already initialised       */ 
507         bool        linked;           /* true, if class already linked            */
508         s4                      index;            /* hierarchy depth (classes) or index
509                                          (interfaces)                             */ 
510         s4          instancesize;     /* size of an instance of this class        */
511 #ifdef SIZE_FROM_CLASSINFO
512         s4          alignedsize;      /* size of an instance, aligned to the 
513                                                                          allocation size on the heap */
514 #endif
515
516         vftbl      *vftbl;            /* pointer to virtual function table        */
517
518         methodinfo *finalizer;        /* finalizer method                         */
519 #ifdef JIT_MARKER_SUPPORT
520         methodinfo *marker; 
521 #endif
522
523     u2             innerclasscount;   /* number of inner classes              */
524     innerclassinfo *innerclass;
525
526     classinfo      *hashlink;         /* link for external hash chain         */
527         bool        classvftbl;       /* has its own copy of the Class vtbl       */
528
529         s4          classUsed;        /* 0= not used 1 = used   CO-RT             */
530
531 };
532
533
534 /* virtual function table ******************************************************
535
536         The vtbl has a bidirectional layout with open ends at both sides.
537         interfacetablelength gives the number of entries of the interface table at
538         the start of the vftbl. The vftbl pointer points to &interfacetable[0].
539         vftbllength gives the number of entries of table at the end of the vftbl.
540
541         runtime type check (checkcast):
542
543         Different methods are used for runtime type check depending on the
544         argument of checkcast/instanceof.
545         
546         A check against a class is implemented via relative numbering on the class
547         hierachy tree. The tree is numbered in a depth first traversal setting
548         the base field and the diff field. The diff field gets the result of
549         (high - base) so that a range check can be implemented by an unsigned
550         compare. A sub type test is done by checking the inclusion of base of
551         the sub class in the range of the superclass.
552
553         A check against an interface is implemented via the interfacevftbl. If the
554         interfacevftbl contains a nonnull value a class is a subclass of this
555         interface.
556
557         interfacetable:
558
559         Like standard virtual methods interface methods are called using
560         virtual function tables. All interfaces are numbered sequentially
561         (starting with zero). For each class there exist an interface table
562         of virtual function tables for each implemented interface. The length
563         of the interface table is determined by the highest number of an
564         implemented interface.
565
566         The following example assumes a class which implements interface 0 and 3:
567
568         interfacetablelength = 4
569
570                   | ...       |            +----------+
571                       +-----------+            | method 2 |---> method z
572                       | class     |            | method 1 |---> method y
573                       +-----------+            | method 0 |---> method x
574                       | ivftbl  0 |----------> +----------+
575         vftblptr ---> +-----------+
576                   | ivftbl -1 |--> NULL    +----------+
577                   | ivftbl -2 |--> NULL    | method 1 |---> method x
578                   | ivftbl -3 |-----+      | method 0 |---> method a
579                   +-----------+     +----> +----------+
580      
581                               +---------------+
582                                   | length 3 = 2  |
583                                   | length 2 = 0  |
584                                   | length 1 = 0  |
585                                   | length 0 = 3  |
586         interfacevftbllength ---> +---------------+
587
588 *******************************************************************************/
589
590 struct vftbl {
591         methodptr   *interfacetable[1];    /* interface table (access via macro)  */
592
593         classinfo   *class;                /* class, the vtbl belongs to          */
594
595         s4           vftbllength;          /* virtual function table length       */
596         s4           interfacetablelength; /* interface table length              */
597
598         s4           baseval;              /* base for runtime type check         */
599         s4           diffval;              /* high - base for runtime type check  */
600
601         s4          *interfacevftbllength; /* length of interface vftbls          */
602         
603         methodptr    table[1];             /* class vftbl                         */
604 };
605
606 #define VFTBLINTERFACETABLE(v,i)       (v)->interfacetable[-i]
607
608
609 /* references to some system classes ******************************************/
610
611 extern classinfo *class_java_lang_Object;
612 extern classinfo *class_java_lang_String;
613 extern classinfo *class_java_lang_ClassCastException;
614 extern classinfo *class_java_lang_NullPointerException;
615 extern classinfo *class_java_lang_ArrayIndexOutOfBoundsException;
616 extern classinfo *class_java_lang_NegativeArraySizeException;
617 extern classinfo *class_java_lang_OutOfMemoryError;
618 extern classinfo *class_java_lang_ArithmeticException;
619 extern classinfo *class_java_lang_ArrayStoreException;
620 extern classinfo *class_java_lang_ThreadDeath;
621 extern classinfo *class_array;
622
623 /* instances of some system classes *******************************************/
624
625 extern java_objectheader *proto_java_lang_ClassCastException;
626 extern java_objectheader *proto_java_lang_NullPointerException;
627 extern java_objectheader *proto_java_lang_ArrayIndexOutOfBoundsException;
628 extern java_objectheader *proto_java_lang_NegativeArraySizeException;
629 extern java_objectheader *proto_java_lang_OutOfMemoryError;
630 extern java_objectheader *proto_java_lang_ArithmeticException;
631 extern java_objectheader *proto_java_lang_ArrayStoreException;
632 extern java_objectheader *proto_java_lang_ThreadDeath;
633
634
635 /* flag variables *************************************************************/
636
637 extern bool compileall;
638 extern bool runverbose;         
639 extern bool verbose;         
640 extern bool opt_rt;             /* Rapid Type Analysis for better inlining CO-RT*/
641
642 extern int pClassHeir;
643 extern int pCallgraph;
644 extern int pOpcodes;
645
646 extern void RT_jit_parse(methodinfo *m);
647 extern void printCallgraph ();
648 extern void printRThierarchyInfo(methodinfo *m);
649
650
651 /* statistic variables ********************************************************/
652
653 extern int count_class_infos;
654 extern int count_const_pool_len;
655 extern int count_vftbl_len;
656 extern int count_utf_len;
657 extern int count_all_methods;
658 extern int count_vmcode_len;
659 extern int count_extable_len;
660 extern int count_class_loads;
661 extern int count_class_inits;
662 extern int count_utf_new;
663 extern int count_utf_new_found;
664
665 /* table of primitive types ***************************************************/
666
667 extern primitivetypeinfo primitivetype_table[PRIMITIVETYPE_COUNT];
668
669 #endif
670
671
672 /*
673  * These are local overrides for various environment variables in Emacs.
674  * Please do not remove this and leave it at the end of the file, where
675  * Emacs will automagically detect them.
676  * ---------------------------------------------------------------------
677  * Local variables:
678  * mode: c
679  * indent-tabs-mode: t
680  * c-basic-offset: 4
681  * tab-width: 4
682  * End:
683  */