From: edwin Date: Mon, 13 Mar 2006 21:26:05 +0000 (+0000) Subject: * design_onstack_replacement.txt: Added file. X-Git-Url: http://wien.tomnetworks.com/gitweb/?p=cacao.git;a=commitdiff_plain;h=0db1380c5822a59b60536f3427e278c18ff9417f * design_onstack_replacement.txt: Added file. --- diff --git a/doc/design_onstack_replacement.txt b/doc/design_onstack_replacement.txt new file mode 100644 index 000000000..2b1befb13 --- /dev/null +++ b/doc/design_onstack_replacement.txt @@ -0,0 +1,210 @@ +ONSTACK REPLACEMENT IN CACAO +============================ +Author: Edwin Steiner + +** This is a design sketch! ** + + +Overview +-------- + +On the whole, method replacement works like this: + + * a method foo is compiled into a replaceable version fooV1. fooV1 + has a set of "replacement points" and for each replacement point it + has a description (either a data structure or generated code) how to + map the "execution state" at this point to the "source state". + + when the compiler decides to replace fooV2, it does the + following: + + * a new version fooV2 of the method is compiled. Together with fooV2 + the compiler creates a "replacement mapping" that maps each + replacement point of fooV1 to a point in fooV2 and specifies how the + source state has to be mapped to the execution state at this point. + + * fooV2 replaces fooV1 in the vftbl. From now on all threads that + enter foo will got to fooV2. + + * If not already done, the compiler creates a chunk of + "replacement-out code" for each replacement point of fooV1. If there + is pre-generated replacement-out code it may have fields that are set + now. + + * each replacement point in fooV1 is patched with a jump to its chunk + of replacement-out code. + + * eventually threads will reach replacement points in fooV1 and be + "beamed" to fooV2. + + * fooV1 has to be kept around undefinitely because it is not possible + (not feasible?) to determine if there is a thread that may reach fooV1 + code in the future. + + +Replacement Points +------------------ + +Replacement points must be placed in a way such that there is a _static_ +upper bound to the number of instructions that a thread must execute +_inside the method body_ until it reaches a replacement point. + +NOTE that this does _not_ place an upper bound on the _time_ it takes to +reach a replacement point, because execution can enter a blocking +instruction or a method call at any point and take a possibly unlimited +amount of time to complete that. + +CACAO will place a replacement point at method entry and at each target +of a backward branch. + +XXX Is the replacement point at the method entry necessary? +Replacement-at-entry is performed by the vftbl anyway. + + +Execution State +--------------- + +The execution state that has to be transformed during +onstack replacement consists of: + + 1) the program counter + + 2) live CPU registers + XXX caution: BSR return values!! + + 3a) live local variables and spill slots + on the stack + XXX caution: BSR return values!! + + 3b) the locked object of the method if it is synchronized + + 3c) the return address to the caller and the + link to the previous activation record + + 3d) saved callee-save registers + + +ad 1) The program counter is in 1-to-1 correspondance to the replacement +point reached. + +ad 2) the register allocator knows which registers are live at the +replacement point. This information can be encoded either in a special +data structure or be transformed into generated replacement-out code +that is created at the same time the method is compiled. + +ad 3*) These data are similarily organized for all replacement points in +a method so we probably want to treat these with common code in order to +save space. + + +Source State +------------ + +The source state is a virtual state comprising: + + 1) the Java Bytecode program counter + + 2) the values on the Java stack + + 3) the values in Java local variables + + 4) synchronization state and locked object of the method + + 5) the frames (activation records) of Java methods + on the VM stack + +The source state is "virtual" in the sense that there does not exists a +real data structure containing these data. However, the source state +must be reconstructable from the execution state at each replacement +point. + +It does not matter if the source state values are actually constructed +or if there is a direct translation (execution state V1) -> (execution +state V2) that uses the source state as a conceptual link +between these states. + + +One-Step vs. Multi-Step Replacement +----------------------------------- + +Conceptually the actions from reaching the replacement point in fooV1 +to continuing execution in fooV2 are the following: + + 1) read the execution state of the fooV1 activation + + 2) remove the activation record corresponding to this invocation + of fooV1 + + 3) build an activation record for the (faked) + invocation of fooV2. + + 4) write the execution state of the fooV2 activation + + 5) jump to the fooV2 code + + +It would be possible to perform all these actions with a single +big chunk of generated code for each replacement point. I think, +however, that a clean separation of the phases has many +advantages. + +Phases: + + 1) done by generated replacement-out code. (Possibly + a replacement-point specific part and a method + specific part). + + 2-3) implemented in C. Some parts are architecture + specific, however, as they depend on the structure + of the stack frames. + + 4-5) done by generated replacement-in code or a + general replacement-in function written in assembler. + +This separation minimizes platform specific assembler code +and opens possibilities for debugging/logging that will +probably be invaluable when implementing this stuff. + + +Replacement-Out Code +-------------------- + +Replacement-out code could look like this: + + replacement_point_jumps_here: + sub %esp,SIZE_OF_STRUCT + mov REPLACEMENT_POINT_INDEX,ofsindex(%esp) + mov %regX,ofsX(%esp) + mov %regY,ofsX(%esp) + jmp method_specific_code + + /* code for other replacement points */ + + method_specific_code: + mov %esp,%eax + add %eax,OFFSET_OF_STACKFRAME_FROM_CURRENT_ESP + mov %eax,ofsframe(%esp) + /* other method specific copying ... */ + push %esp /* arg0 */ + call method_replace(execution_state *es) + +Note that the current method can be found in the +stack frame, so we do not have to explicitely pass that +info. Information on the new code (fooV2) will be +in the methodinfo. + + +Splitting methodinfo and codeinfo +--------------------------------- + +Recompilation will require that cacao deal with +a method (repr. by a `methodinfo`) that has several +realizations in JIT code (`codeinfo` or something +like that). There will always be a current codeinfo +and zero or more old codeinfos that have to be +kept around. (For example we may have to do stack +traces from pcs in old code.) + + +vim: tw=72 +