Package ghidra.pcode.emu.jit.analysis

Class JitAllocationModel

java.lang.Object

ghidra.pcode.emu.jit.analysis.JitAllocationModel

public class JitAllocationModel
extends Object

Type variable allocation phase for JIT-accelerated emulation.

The implements the Variable Allocation phase of the JitCompiler using a very simple placement and another "voting" algorithm to decide the allocated JVM variable types. We place/map variables by their storage varnodes, coalescing them as needed. Coalescing is performed for overlapping, but not abutting varnodes. This allocation is anticipated by the JitVarScopeModel, which performs the actual coalescing. Because multiple SSA variables will almost certainly occupy the same varnode, we employ another voting system. For example, the register RAX may be re-used many times within a passage. In some cases, it might be used to return a floating-point value. In others (and probably more commonly) it will be used to return an integral value. The more common case in the passage determines the JVM type of the local variable allocated for RAX. Note that variables which occupy only part of a coalesced varnode always vote for a JVM int, because of the shifting and masking required to extract that part.

The allocation process is very simple, presuming successful type assignment:

1. Vote Tabulation
2. Index Reservation
3. Handler Creation

Vote Tabulation

Every SSA variable (excluding constants and memory variables) contributes a vote for the type of its allocated local. If the varnode matches exactly, the vote is for the JVM type of the variable's assigned p-code type. The type mapping is simple: For integral types, we allocate using the smaller JVM type that fits the p-code type. For floating-point types, we allocate using the JVM type that exactly matches the p-code type. If the varnode is larger, i.e., because it's the result of coalescing, then the vote is for the smaller JVM integer type that fits the full varnode. Consider the following p-code:

 1. RAX = FLOAT_ADD RCX, RDX
 2. EAX = FLOAT_ADD EBX, 0x3f800000:4 # 1.0f
 

Several values and variables are at play here. We tabulate the type assignments and resulting votes:

SSA Var	Type	Varnode	Vote
RCXin	float8	RCX	double
RDXin	float8	RDX	double
RAX1	float8	RAX	double
EBXin	float4	EBX	float
0x3f800000:4	float4
EAX2	float4	RAX	long

The registers RCX, RDX, and EBX are trivially allocated as locals of JVM types double, double, and float, respectively. It is also worth noting that 0x3f800000 is allocated as a float constant in the classfile's constant pool. Now, we consider RAX. The varnodes for RAX₁ and EAX₂ are coalesced to RAX. RAX₁ casts its vote for double; whereas, EAX₂ casts its vote for long. This is because placing EAX₂'s value into the larger varnode requires bitwise operators, which on the JVM, require integer operands. Thus the votes result in a tie, and favoring integral types, we allocate RAX in a JVM long.

Index Reservation

After all the votes have been tabulated, we go through the results in address order, reserving JVM local indices and assigning types. Note that we must reserve two indices for every variable of type long or double, as specific by the JVM. Each of these reservations is tracked in a JitAllocationModel.JvmLocal. Note that index 0 is already reserved by the JVM for the this ref, so we start our counting at 1. Also, some portions of the code generator may need to allocate additional temporary locals, so we must allow access to the next free index after all reservations are complete.

Handler Creation

This actually extends a little beyond allocation, but this is a suitable place for it: All SSA values are assigned a handler, including constants and memory variables. Variables which access the same varnode get the same handler. For varnodes that are allocated in a JVM local, we create a handler that generates loads and stores to that local, e.g., iload. For constant varnodes, we create a handler that generates ldc instructions. For memory varnodes, we create a handler that generates a sequence of method invocations on the state. The code generator will delegate to these handlers in order to generate reads and writes of the corresponding variables, as well as to prepare any resources to facilitate access, e.g., pre-fetching items from the state in the generated constructor.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static final record	JitAllocationModel.DoubleVarAlloc	The handler for a p-code variable allocated in one JVM double.
static final record	JitAllocationModel.FloatVarAlloc	The handler for a p-code variable allocated in one JVM float.
static final record	JitAllocationModel.IntVarAlloc	The handler for a p-code variable allocated in one JVM int.
static final record	JitAllocationModel.JvmLocal	An allocated JVM local
static final record	JitAllocationModel.LongVarAlloc	The handler for a p-code variable allocated in one JVM long.
static final record	JitAllocationModel.MultiLocalPart	A portion of a multi-local variable handler.
static final record	JitAllocationModel.MultiLocalVarHandler	The handler for a variable allocated in a composition of locals
static enum	JitAllocationModel.NoHandler	A dummy handler for values/variables that are not allocated in JVM locals
static interface	JitAllocationModel.OneLocalVarHandler	A handler for p-code variables composed of a single JVM local variable.
static interface	JitAllocationModel.VarHandler	A handler that knows how to load and store variable values onto and from the JVM stack.

Constructor Summary

Constructors

Constructor	Description
JitAllocationModel(JitAnalysisContext context, JitDataFlowModel dfm, JitVarScopeModel vsm, JitTypeModel tm)	Construct the allocation model.

Method Summary

Modifier and Type	Method	Description
Collection<JitAllocationModel.JvmLocal>	allLocals()	Get all of the locals allocated
JitAllocationModel.VarHandler	getHandler(JitVal v)	Get the handler for the given value (constant or variable in the use-def graph)
Collection<JitAllocationModel.JvmLocal>	localsForVn(Varnode vn)	Get all of the locals allocated for the given varnode
int	nextFreeLocal()	Get the next free local index without reserving it

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

JitAllocationModel

public JitAllocationModel(JitAnalysisContext context,
 JitDataFlowModel dfm,
 JitVarScopeModel vsm,
 JitTypeModel tm)

Construct the allocation model.

Parameters:

context - the analysis context

dfm - the data flow moel

vsm - the variable scope model

tm - the type model

Method Details

nextFreeLocal

public int nextFreeLocal()

Get the next free local index without reserving it

This should be used by operator code generators after all the state bypassing local variables have been allocated. The variables should be scoped to that operator only, so that the ids used are freed for the next operator.

Returns:

the next id

getHandler

public JitAllocationModel.VarHandler getHandler(JitVal v)

Get the handler for the given value (constant or variable in the use-def graph)

Parameters:

v - the value

Returns:

the handler

allLocals

public Collection<JitAllocationModel.JvmLocal> allLocals()

Get all of the locals allocated

Returns:

the locals

localsForVn

public Collection<JitAllocationModel.JvmLocal> localsForVn(Varnode vn)

Get all of the locals allocated for the given varnode

Parameters:

vn - the varnode

Returns:

the locals