[kaffe] Allocating objects in the stack
Jim Pick
jim at kaffe.org
Thu Jun 19 08:06:02 PDT 2003
Nice work.
What do people think of this?
I guess one problem might be that Kaffe's stack is already under pretty
heavy pressure, because it's used to store the Java stack as well. If
we use it to store objects as well, we might have to increase the
default stack size.
Cheers,
- Jim
On Tue, 2003-06-17 at 11:26, Heikki Linnakangas wrote:
> Hello,
>
> I've been pondering for some time if it was possible to allocate some
> objects in the stack insted of the heap. Stack allocation is faster,
> stack doesn't need to be garbage collected, and it keeps the memory
> footprint smaller.
>
> Last weekend I decided to look into the problem. I figured that if a
> method constructs a new object, and never assigns it to member variable,
> never gives it as an argument to other methods etc. it should be safe to
> allocate it in the stack. Little googleing revealed that indeed I wasn't
> the first one to think about this, and I found a nice paper [1] that
> outlines the above restrictions in a more formal way. Gay and Steensgard
> also discuss some other code transformations that could leverage stack
> allocation even more.
>
> I grapped the kaffe source code and implemented a very crude version of
> the method described in the paper. This initial implementation is very
> limited. Stack allocation is done only for primitive arrays, and only if
> the method doesn't contain any loops. Escape analysis is very limited.
> And no JIT implementation yet.
>
> I thought I'd post the initial implementation right away before I
> tackle the more complicated stuff because I'd like to receive comments as
> early as possible.
>
> The implementation introduces a new synthetic instruction, NEWARRAY_STACK,
> which is identical to NEWARRAY, except that those allocations have been
> determined safe to be made in the stack. NEWARRAY instructions are changed
> to NEWARRAY_STACK instructions in the code analyzation phase if the
> reference doesn't escape the method.
>
> Obviously there is a lot of room for improvement:
>
> 1. Allocations that are made inside a loop are not suitable for stack
> allocation. The current implementation just checks if the method has any
> loops at all, and doesn't do stack allocation if there is. A proper
> loop detection should determine if the allocation is made inside the loop.
>
> I believe it would be fairly easy by looking at the relations between the
> basic blocks. I haven't looked at that yet.
>
> 2. Currently, only primitive arrays are supported. Reference arrays would
> be trivial to add, but objects are more complicated because they have
> constructors that could let the reference to escape. Objects would need
> item 3 solved.
>
> 3. Currently all references that are given as arguments to method
> calls are considered to escape, including the "this" variable of the
> callee and most importantly all constructors. However, I'd say that most
> methods don't really let the argument escape. Think about all the
> setter/getter-methods, toString etc.
>
> Escape analysis should be made for method arguments also. That way most
> method calls would not inhibit stack allocation. Flags should be attached
> to all methods that indicates which arguments the implementation let's
> escape.
>
> 4. JIT implementation. Could someone help me to figure out how to allocate
> something in the stack?
>
> I've included the initial implementation as a diff against the current CVS
> head. You'll have to compile with "--with-engine=INTRP". AFAIK, it
> works, but I haven't tested it very much. The regression tests passed.
>
> It's hard to find code that really benefits from this limited
> implementation, but you can try the following simple example:
>
> public class StackAllocationTest {
> public static void main(String[] args) {
> int i = 0;
> while(i < 10) {
> i = inc(i);
> }
> System.out.println(i);
> }
> public static int inc(int i) {
> int[] ii = new int[1];
> ii[0] = i;
> ii[0]++;
> return ii[0];
> }
> }
>
> Run the above code with "-vmdebug INTRPA" to see the NEWARRAY_STACK
> instruction in action. CODEANALYSE will show some details of the escape
> analysis.
>
> [1] Fast Escape Analysis and Stack Allocation for Object-Based Programs
> (2000), David Gay, Bjarne Steensgaard
> http://citeseer.nj.nec.com/gay00fast.html
>
> PS. The KaffeInternal.java regression test is broken. It expects a
> ClassNotFoundException, but a SecurityException is thrown.
>
> - Heikki
>
> Index: kaffevm/bytecode.h
> ===================================================================
> RCS file: /cvs/kaffe/kaffe/kaffe/kaffevm/bytecode.h,v
> retrieving revision 1.2
> diff -c -r1.2 bytecode.h
> *** kaffevm/bytecode.h 29 Jul 2002 16:02:32 -0000 1.2
> --- kaffevm/bytecode.h 16 Jun 2003 20:19:54 -0000
> ***************
> *** 217,220 ****
> --- 217,223 ----
> #define JSR_W 201
> #define BREAKPOINT 202
>
> + /* Synthetic bytecodes */
> + #define NEWARRAY_STACK 255
> +
> #endif
> Index: kaffevm/code-analyse.c
> ===================================================================
> RCS file: /cvs/kaffe/kaffe/kaffe/kaffevm/code-analyse.c,v
> retrieving revision 1.37
> diff -c -r1.37 code-analyse.c
> *** kaffevm/code-analyse.c 6 Feb 2003 21:35:07 -0000 1.37
> --- kaffevm/code-analyse.c 16 Jun 2003 20:19:57 -0000
> ***************
> *** 49,55 ****
> 3, 3, 1, 1, 1, 4, 3, 3, 5, 5, 1, 1, 1, 1, 1, 1,
> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
> ! 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
> };
>
> static void mergeFrame(codeinfo*, int, int, frameElement*, Method*);
> --- 49,55 ----
> 3, 3, 1, 1, 1, 4, 3, 3, 5, 5, 1, 1, 1, 1, 1, 1,
> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
> ! 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2,
> };
>
> static void mergeFrame(codeinfo*, int, int, frameElement*, Method*);
> ***************
> *** 74,79 ****
> --- 74,80 ----
> bool wide;
> codeinfo *codeInfo;
> localUse* localuse;
> + bool containsLoops = false;
>
> DBG(CODEANALYSE,
> dprintf(__FUNCTION__ " %p: %s.%s\n", THREAD_NATIVE(),
> ***************
> *** 150,155 ****
> --- 151,158 ----
> case IF_ACMPEQ: case IF_ACMPNE:
> case IFNULL: case IFNONNULL:
> tabpc = pc + WORD(pc+1);
> + if(tabpc <= pc)
> + containsLoops = true;
> SET_STARTOFBASICBLOCK(tabpc);
> SET_JUMPFLOW(pc, tabpc);
> pc = pc + INSNLEN(pc);
> ***************
> *** 158,163 ****
> --- 161,168 ----
> break;
> case GOTO:
> tabpc = pc + WORD(pc+1);
> + if(tabpc <= pc)
> + containsLoops = true;
> SET_STARTOFBASICBLOCK(tabpc);
> SET_JUMPFLOW(pc, tabpc);
> pc = pc + INSNLEN(pc);
> ***************
> *** 167,172 ****
> --- 172,179 ----
> break;
> case GOTO_W:
> tabpc = pc + DWORD(pc+1);
> + if(tabpc <= pc)
> + containsLoops = true;
> SET_STARTOFBASICBLOCK(tabpc);
> SET_JUMPFLOW(pc, tabpc);
> pc = pc + INSNLEN(pc);
> ***************
> *** 175,180 ****
> --- 182,188 ----
> }
> break;
> case JSR:
> + containsLoops = true;
> tabpc = pc + WORD(pc+1);
> SET_STARTOFBASICBLOCK(tabpc);
> SET_JUMPFLOW(pc, tabpc);
> ***************
> *** 183,188 ****
> --- 191,197 ----
> SET_NORMALFLOW(pc);
> break;
> case JSR_W:
> + containsLoops = true;
> tabpc = pc + DWORD(pc+1);
> SET_STARTOFBASICBLOCK(tabpc);
> SET_JUMPFLOW(pc, tabpc);
> ***************
> *** 363,368 ****
> --- 372,387 ----
> }
> }
> #endif
> +
> + /* Scan the code for stack allocation candidates */
> + if(!containsLoops) {
> + for (pc = 0; pc < codeInfo->codelen; pc++) {
> + if(IS_STARTOFINSTRUCTION(pc) && INSN(pc) == NEWARRAY && !IS_ESCAPES(pc)) {
> + INSN(pc) = NEWARRAY_STACK;
> + }
> + }
> + }
> +
> return (true);
> }
>
> ***************
> *** 877,882 ****
> --- 896,902 ----
> STACKIN(1, TINT);
> STACKIN(0, TOBJ);
> STKPOP(3);
> + STACKESCAPE(0);
> INCPC(1);
> break;
>
> ***************
> *** 1385,1390 ****
> --- 1405,1411 ----
>
> case ARETURN:
> STACKIN(0, TOBJ);
> + STACKESCAPE(0);
> STKPOP(1);
> INCPC(1);
> break;
> ***************
> *** 1468,1473 ****
> --- 1489,1495 ----
> case '[':
> case 'L':
> STACKIN(0, TOBJ);
> + STACKESCAPE(0);
> STKPOP(1);
> break;
> default:
> ***************
> *** 1521,1526 ****
> --- 1543,1549 ----
> }
> if (!FIELD_ISPRIM(finfo.field)) {
> STACKIN(0, TOBJ);
> + STACKESCAPE(0);
> STACKIN(1, TOBJ);
> STKPOP(2);
> }
> ***************
> *** 1580,1585 ****
> --- 1603,1609 ----
> switch (sig[0]) {
> case '[':
> STACKIN(idx, TOBJ);
> + STACKESCAPE(idx);
> idx -= 1;
> while (sig[0] == '[') {
> sig++;
> ***************
> *** 1593,1598 ****
> --- 1617,1623 ----
> break;
> case 'L':
> STACKIN(idx, TOBJ);
> + STACKESCAPE(idx);
> idx -= 1;
> while (sig[0] != ';') {
> sig++;
> ***************
> *** 1682,1687 ****
> --- 1707,1713 ----
> switch (sig[0]) {
> case '[':
> STACKIN(idx, TOBJ);
> + STACKESCAPE(idx);
> idx -= 1;
> while (sig[0] == '[') {
> sig++;
> ***************
> *** 1695,1700 ****
> --- 1721,1727 ----
> break;
> case 'L':
> STACKIN(idx, TOBJ);
> + STACKESCAPE(idx);
> idx -= 1;
> while (sig[0] != ';') {
> sig++;
> ***************
> *** 1782,1787 ****
> --- 1809,1815 ----
> switch (sig[0]) {
> case '[':
> STACKIN(idx, TOBJ);
> + STACKESCAPE(idx);
> idx -= 1;
> while (sig[0] == '[') {
> sig++;
> ***************
> *** 1795,1800 ****
> --- 1823,1829 ----
> break;
> case 'L':
> STACKIN(idx, TOBJ);
> + STACKESCAPE(idx);
> idx -= 1;
> while (sig[0] != ';') {
> sig++;
> ***************
> *** 1877,1884 ****
> --- 1906,1918 ----
> break;
>
> case NEWARRAY:
> + case NEWARRAY_STACK:
> STACKIN(0, TINT);
> STACKOUT(0, TOBJ);
> + DBG(CODEANALYSE,
> + dprintf("stack candidate at %d\n", pc);
> + )
> + STACKMARKALLOC(0);
> INCPC(2);
> break;
>
> ***************
> *** 1917,1922 ****
> --- 1951,1957 ----
>
> case ATHROW:
> STACKIN(0, TOBJ);
> + STACKESCAPE(0);
> STKPOP(1);
> INCPC(1);
> break;
> ***************
> *** 2006,2011 ****
> --- 2041,2048 ----
>
> /* Merge locals */
> for (m = 0; m < meth->localsz; m++) {
> + if(from[m].type != TUNASSIGNED)
> + to[m].introducedpc = from[m].introducedpc;
> if (from[m].type != TUNASSIGNED && from[m].type != to[m].type && to[m].type != TUNSTABLE) {
> SET_NEEDVERIFY(pc);
> if (to[m].type == TUNASSIGNED) {
> ***************
> *** 2019,2024 ****
> --- 2056,2063 ----
>
> /* Merge stacks */
> for (m = sp; m < meth->localsz + meth->stacksz; m++) {
> + if(from[m].type != TUNASSIGNED)
> + to[m].introducedpc = from[m].introducedpc;
> if (from[m].type != TUNASSIGNED && from[m].type != to[m].type && to[m].type != TUNSTABLE) {
> SET_NEEDVERIFY(pc);
> if (to[m].type == TUNASSIGNED) {
> Index: kaffevm/code-analyse.h
> ===================================================================
> RCS file: /cvs/kaffe/kaffe/kaffe/kaffevm/code-analyse.h,v
> retrieving revision 1.17
> diff -c -r1.17 code-analyse.h
> *** kaffevm/code-analyse.h 6 Feb 2003 21:35:07 -0000 1.17
> --- kaffevm/code-analyse.h 16 Jun 2003 20:19:58 -0000
> ***************
> *** 15,20 ****
> --- 15,21 ----
> Hjava_lang_Class* type;
> uint8 used;
> uint8 modified;
> + int32 introducedpc;
> } frameElement;
>
> typedef struct perPCInfo {
> ***************
> *** 85,90 ****
> --- 86,92 ----
> #define FLAG_NEEDVERIFY 0x0040
> #define FLAG_DONEVERIFY 0x0080
> #define FLAG_STARTOFINSTRUCTION 0x0100
> + #define FLAG_ESCAPES 0x0200
>
> #define FLAGS(_pc) codeInfo->perPC[_pc].flags
> #define STACKPOINTER(_pc) codeInfo->perPC[_pc].stackPointer
> ***************
> *** 102,107 ****
> --- 104,111 ----
> (meth->c.bcode.code[(pc)+3]))
> #define INCPC(V) pc += (V)
>
> + #define SET_ESCAPES(PC) FLAGS(PC) |= FLAG_ESCAPES
> +
> #define SET_STARTOFBASICBLOCK(PC) ATTACH_NEW_BASICBLOCK(PC); \
> SET_NEWFRAME(PC); \
> FLAGS(PC) |= FLAG_STARTOFBASICBLOCK
> ***************
> *** 146,151 ****
> --- 150,156 ----
> #define IS_UNREACHABLE(pc) ((IS_STARTOFBASICBLOCK(pc) || \
> IS_STARTOFEXCEPTION(pc)) && \
> !IS_DONEVERIFY(pc))
> + #define IS_ESCAPES(pc) (FLAGS(pc) & FLAG_ESCAPES)
>
> #define ALLOCFRAME() KMALLOC((codeInfo->stacksz+codeInfo->localsz+1) * sizeof(frameElement))
>
> ***************
> *** 250,255 ****
> --- 255,274 ----
> FRAME(pc)[(L)].used = 1
> #define LOCALIN(L, T) LOCAL_CHECKTYPE(L, T); \
> LCL(L).used = 1
> +
> + #define ESCAPE(E) { \
> + if((E).introducedpc != 0) { \
> + DBG(CODEANALYSE, \
> + dprintf(__FUNCTION__" %d escapes at (%d)\n", \
> + (E).introducedpc, pc); \
> + ) \
> + SET_ESCAPES((E).introducedpc); \
> + } \
> + }
> +
> + #define STACKESCAPE(S) ESCAPE(SF(S))
> + #define STACKMARKALLOC(S) SF(S).introducedpc = pc;
> + #define LOCALESCAPE(L) ESCAPE(LCL(L))
>
> struct _methods;
> bool analyzeMethod(struct _methods*, codeinfo**, errorInfo*);
> Index: kaffevm/kaffe.def
> ===================================================================
> RCS file: /cvs/kaffe/kaffe/kaffe/kaffevm/kaffe.def,v
> retrieving revision 1.25
> diff -c -r1.25 kaffe.def
> *** kaffevm/kaffe.def 26 May 2003 07:27:00 -0000 1.25
> --- kaffevm/kaffe.def 16 Jun 2003 20:20:02 -0000
> ***************
> *** 2795,2800 ****
> --- 2795,2815 ----
> softcall_newarray(stack(0), stack(0), low);
> }
>
> + define_insn(NEWARRAY_STACK)
> + {
> + /*
> + * ... size -> ..., object ref
> + */
> + check_pc (0);
> + check_stack_int(0);
> +
> + low = (uint8)getpc(0);
> + trace_jcode (("newarray_stack %d\n", low));
> +
> + softcall_newarray_stack(stack(0), stack(0), low);
> + }
> +
> +
> define_insn(ANEWARRAY)
> {
> /*
> Index: kaffevm/object.c
> ===================================================================
> RCS file: /cvs/kaffe/kaffe/kaffe/kaffevm/object.c,v
> retrieving revision 1.19
> diff -c -r1.19 object.c
> *** kaffevm/object.c 23 Apr 2002 10:43:41 -0000 1.19
> --- kaffevm/object.c 16 Jun 2003 20:20:03 -0000
> ***************
> *** 103,108 ****
> --- 103,154 ----
> return (cls);
> }
>
> +
> + /*
> + * Returns the amount of memory that should be allocated for an
> + * array of given type and length
> + */
> + size_t soft_array_size(jint type, int count) {
> + Hjava_lang_Class* elclass = TYPE_CLASS(type);
> + DBG(NEWOBJECT,
> + dprintf("soft_array_size class %s count %d\n", (elclass ? elclass->name->data : "<none>"), count);
> + )
> + if (CLASS_IS_PRIMITIVE(elclass) || elclass == PtrClass) {
> + size_t total_count = (TYPE_SIZE(elclass) * count) + ARRAY_DATA_OFFSET;
> + return total_count;
> + }
> + else {
> + size_t total_count = (PTR_TYPE_SIZE * count) + ARRAY_DATA_OFFSET;
> + return total_count;
> + }
> + }
> +
> + /*
> + * Allocate a new array, of whatever types.
> + */
> + Hjava_lang_Object*
> + newArrayChecked_stack(Hjava_lang_Class* elclass, int count, errorInfo *info, void *location)
> + {
> + Hjava_lang_Class* class = 0;
> + Hjava_lang_Object* obj = (Hjava_lang_Object*) location;
> +
> + if (obj) {
> + class = lookupArray(elclass, info);
> + } else {
> + postOutOfMemory(info);
> + }
> +
> + if (class) {
> + obj->dtable = class->dtable;
> + ARRAY_SIZE(obj) = count;
> + }
> + DBG(NEWOBJECT,
> + dprintf("newArrayStack %p class %scount %d\n", obj,
> + (class ? class->name->data : "<none>"), count);
> + )
> + return (obj);
> + }
> +
> /*
> * Allocate a new array, of whatever types.
> */
> Index: kaffevm/object.h
> ===================================================================
> RCS file: /cvs/kaffe/kaffe/kaffe/kaffevm/object.h,v
> retrieving revision 1.4
> diff -c -r1.4 object.h
> *** kaffevm/object.h 20 Dec 2000 02:41:52 -0000 1.4
> --- kaffevm/object.h 16 Jun 2003 20:20:03 -0000
> ***************
> *** 40,45 ****
> --- 40,49 ----
> struct _errorInfo *);
> Hjava_lang_Object* newObject(struct Hjava_lang_Class*);
> struct Hjava_lang_Class* newClass(void);
> +
> + size_t soft_array_size(jint type, int count);
> + Hjava_lang_Object* newArrayChecked_stack(struct Hjava_lang_Class*, int,
> + struct _errorInfo *, void *);
> Hjava_lang_Object* newArrayChecked(struct Hjava_lang_Class*, int,
> struct _errorInfo *);
> Hjava_lang_Object* newArray(struct Hjava_lang_Class*, int);
> Index: kaffevm/soft.c
> ===================================================================
> RCS file: /cvs/kaffe/kaffe/kaffe/kaffevm/soft.c,v
> retrieving revision 1.51
> diff -c -r1.51 soft.c
> *** kaffevm/soft.c 7 Aug 2002 08:40:39 -0000 1.51
> --- kaffevm/soft.c 16 Jun 2003 20:20:04 -0000
> ***************
> *** 65,70 ****
> --- 65,95 ----
> }
>
> /*
> + * soft_newarray_stack
> + */
> + void*
> + soft_newarray_stack(jint type, jint size, void *location)
> + {
> + Hjava_lang_Object* obj;
> + errorInfo info;
> +
> + if (size < 0) {
> + throwException(NegativeArraySizeException);
> + }
> +
> + obj = newArrayChecked_stack(TYPE_CLASS(type), size, &info, location);
> + if (obj == 0) {
> + throwError(&info);
> + }
> +
> + DBG(NEWINSTR,
> + dprintf("New array of %s [%d] (%p)\n",
> + TYPE_CLASS(type)->name->data, size, obj); )
> +
> + return (obj);
> + }
> +
> + /*
> * soft_newarray
> */
> void*
> Index: kaffevm/soft.h
> ===================================================================
> RCS file: /cvs/kaffe/kaffe/kaffe/kaffevm/soft.h,v
> retrieving revision 1.9
> diff -c -r1.9 soft.h
> *** kaffevm/soft.h 30 May 2002 22:47:32 -0000 1.9
> --- kaffevm/soft.h 16 Jun 2003 20:20:05 -0000
> ***************
> *** 17,22 ****
> --- 17,23 ----
> struct Hjava_lang_Object;
>
> void* soft_new(struct Hjava_lang_Class*);
> + void* soft_newarray_stack(jint, jint, void *location);
> void* soft_newarray(jint, jint);
> void* soft_anewarray(struct Hjava_lang_Class*, jint);
> void soft_initialise_class(struct Hjava_lang_Class*);
> Index: kaffevm/intrp/icode.h
> ===================================================================
> RCS file: /cvs/kaffe/kaffe/kaffe/kaffevm/intrp/icode.h,v
> retrieving revision 1.15
> diff -c -r1.15 icode.h
> *** kaffevm/intrp/icode.h 7 May 2001 10:04:35 -0000 1.15
> --- kaffevm/intrp/icode.h 16 Jun 2003 20:20:06 -0000
> ***************
> *** 293,298 ****
> --- 293,299 ----
> #define softcall_lookupinterfacemethod(r, n, t) (r)[0].v.taddr = soft_lookupinterfacemethod((t)[0].v.taddr, (n)->class, (n)->idx)
> #define softcall_new(r, t) (r)->v.taddr = soft_new(t)
> #define softcall_newarray(r, s, t) (r)->v.taddr = soft_newarray(t, (s)->v.tint)
> + #define softcall_newarray_stack(r, s, t) (r)->v.taddr = soft_newarray_stack(t, (s)->v.tint, alloca(soft_array_size(t, (s)->v.tint)));
> #define softcall_anewarray(r, s, t) (r)->v.taddr = soft_anewarray(t, (s)->v.tint)
> #define softcall_athrow(s) soft_athrow((s)[0].v.taddr)
> #define softcall_checkcast(n, o, t) soft_checkcast(t, (o)->v.taddr)
>
>
> _______________________________________________
> kaffe mailing list
> kaffe at kaffe.org
> http://kaffe.org/cgi-bin/mailman/listinfo/kaffe
More information about the kaffe
mailing list