Data Structure & Algo - part - II ( Interpreter Only)

Disassembling and trace collection function is divided into 3 parts as follows:

1.Interpreter

a.This will disassemble the instructions and call trace selector for all control transfer instructions to update TLT (trace lookup table).
b.It will also simulate the control transfer instruction by checking the hardware flags thereby taking decisions whether the branch will be taken or not.

2.Trace selector

a.This will update TLT (trace lookup table) for control transfer instructions and return to interpreter the next target address to interprete.
b.If the trace is already present in the fragment cache then it will give control to the fragment cache to execute the fragment directly. In this case the control will go from:
Trace selector--> Fragment cache --> Interpreter.
c.If not in fragment cache and the count exceeds threshold while
After updating TLT then call trace collector.



3. Trace collector

a. It collects the trace till either of the following condition occurs:
Trace size exceeds the MAX LIMIT.
It encounters a return instruction.
It gets a backedge which is outside the hot loop.

b. It works in two modes: Pure and Interrupted.
The idea is that if during trace collection a call instruction is
encountered then the called function is not included as a part of the trace instead it is executed separately and then trace collection is resumed where it was halted.
So initially trace collector is in pure mode where it simply
copies the trace into the trace collection page.
Then if a call or a trace already exising in fragment cache is
encountered then trace collection is halted. And next time when
it resumes, it is in interrupted mode.In this interrupted mode
instead of starting a new trace it simply appends the remaing
trace into the trace collecting page.

d.It also emits the complementary execution page which contains
all the code inside the loop which may or may not be included in the trace collecting page.


Interpreter


Input:

1.address := Address of instruction to start interpretation.
This will be a global variable accessible to all.

Functions:

1. bytes := disassemble_retbytes (address);
This will return the number of bytes for linear code before a control
transfer instruction.

2.insn_buffer := disassemble_ct_insn (address);
This will return the pointer to decoded control transfer instruction.

3.tar_add := take_branch_decision( insn_buffer from above)
It will simulate the control transfer instruction and then returns the taken branch address for conditional control transfer instruction.

It will consist of following steps:
If instruction is “call”
Return( target_add in the instruction).
If instruction is “return”
Store the context
Return( top of dos’s stack)
If insruction is “unconditional jump”
Return( target add in the instruction);
If instruction is ”conditional jump”
Flag = simulate(opcode of instruction)
If(flag) // the branch is taken
Then return (tar add in the instruction)
Else return (add of instruction below CT insn)



4. copy_exec_LEP(bytes);
In this the linear code from (address) to (address + bytes) will be copied
and then executed after adding the prolog and epilog.

5. trace_selector( tar_add)
call to a trace selection to update the TLT.


Algorithm:


1.bytes := disassemble_retbytes (address);
2. copy_exec_LEP(bytes);
3. add_CT_insn = bytes + address;
4. insn_buffer := disassemble_ct_insn (address);
5. tar_add := take_branch_decision( insn_buffer from above)
6. trace_selector( insn_buffer,tar_add)
// trace selector will update address variable also so the loop can be continued.


Trace selector

Input:

1. insn_buffer := which is a pointer to decoded instruction of the control transfer instruction.
2.tar_add := next instruction to interprete / target address in insn

Functions used:

1.update_TLT( add )

It will perform the following functions:
search_in_TLT(add);
if found increment counter
if not found add_entry_TLT(add)
if counter > threshold and already present in fragment cache then start excuting from the fragment cache
If counter > threshold and not present in fragment cache
Call trace_collect(add);
if counter < address =" tar_add;" address =" tar_add;"> curr_prog_counter // forward jump
Address = tar_add;

4.If instruction is “return”
Address= tar_add;


Trace Collector

Input:

1.add := this is the start address for trace collection
2.mode := this indicates mode of working for trace collector.
It can be PURE or INTERRUPTED

Functions used:

1. bytes := disassemble_block(pointer to buffer,add)
This function will return number of bytes of linear code and also disassembled code in the buffer.
2. rawcode := read_from_executable(add,bytes)
This function returns a pointer rawcode to another buffer containing code in executable format.
3. copy_exec_LEP(rawcode)
copy the rawcode into the linear executable page and execute.
4. copy_DA_TCP(pointer to buffer containing DA_code)
It will copy the Disassembled code into the Trace collecting page.
5. insn_buffer:= disassemble_ct_insn(address of CT instruction)
this will decode only the control transfer instruction into insn_buffer
6. action_CT_insn(buffer)
This will perform following functions:
a.if instruction = unconditional jump
* check if the target_add is in fragment cache using function
check_in_FC(target_add);
if not in fragment cache then return target address

* if target_add > start address of trace then return tar_of_jump
else stop collecting trace
// this will ensure that no backedge outside the loop is collected //


b.If instruction is conditional jump

i)

Flag := Simulate(opcode)
If(flag = true) // condition true & branch is taken
{
TBA = (add of target in the instruction)
NTBA = (add of instruction + length of instruction)
}
if(branch is not taken)
{
NTBA = (add of target in the instruction)
TBA = (add of instruction + length of instruction)
}

ii)If NTBA > start_address
Copy NTBA in complementary address table CAT

iii) if TBA > start address
check_in_FC(st_add);
if not in FC then return TBA

iii)if TBA = start_address then stop_collecting_trace()

c.If instruction = call

Copy the instruction in TCP
Check_in_FC(call site address)

If not in fragment cache then we have to execute the call natively and return back to the trace collection in interrupted mode.
Push the address of trace collector user stack
Set flag = INTERRUPTED
Push (return add which is the call_site + length of call)

If in the fragment cache then again the control must be given to FC and then back to trace collector in INTERRUPTED mode.

d.If instruction is “return”
Then stop_collecting_trace()


7. stop_collecting_trace()

In this the lowest address from complementary address table CAT is chosen. And all the code from lowest adress to end address is copied into the complementary executing page (CEP) .
This CEP and TCP is then given further to optimizer.

8. check_in_FC(add)

It will check if the given trace is already present in the fragment cache if present it will push the trace collector address on the user stack and set flag to INTERRUPTED and push the return address on the DOS’s stack and then execute from the fragment cache.

Algorithm: (add)


If mode is PURE TCP_off = 0
Else TCP_off = INTERRUPTED_address

1. bytes := disassemble_block(ptr_DA,add)
2. rawcode := read_from_executable(add,bytes)
3. copy_exec_LEP(rawcode)
4. copy_DA_TCP(pointer to buffer containing DA_code)
It will copy or append the Disassembled code into the Trace collecting page depending upon TCP_off value.
5. insn_buffer:= disassemble_ct_insn(address of CT instruction)
this will decode only the control transfer instruction into insn_buffer
6. add=action_CT_insn(buffer) then loop to 1.