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
--- | --- | --- | ---
`RCX`in | `float8` | `RCX` | `double`
`RDX`in | `float8` | `RDX` | `double`
`RAX`1 | `float8` | `RAX` | `double`
`EBX`in | `float4` | `EBX` | `float`
`0x3f800000:4` | `float4`
`EAX`2 | `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`1 and `EAX`2 are coalesced to `RAX`. `RAX`1 casts its vote for `double`; whereas, `EAX`2 casts its vote for `long`. This is because placing `EAX`2'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.

Implementation Notes:
  There are many artifacts below that anticipate supporting p-code types greater than 8 bytes in size. One method to support that is to allocate multiple JVM locals per p-code varnode. Consider a 16-byte (128-bit) integer. We could allocate 4 JVM `int` locals and then emit bytecode that performs the gradeschool-style arithmetic. I suspect this would perform better than just using refs to `BigInteger`, because it avoids heap pollution, and also may avoid some unnecessary arithmetic, esp., for the more significant portions that get dropped., TODO: It would be nice to detect varnode re-use under a different type and generate the appropriate declarations and handlers. This doesn't seem terribly complex, and it stands to spare us some casts. What's not clear is whether this offers any real run-time benefit.

- ## 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 interface`
  `JitAllocationModel.FixedLocal`
  A local that is always allocated in its respective method
  `static final record`
  `JitAllocationModel.FloatVarAlloc`
  The handler for a p-code variable allocated in one JVM `float`.
  `static enum`
  `JitAllocationModel.InitFixedLocal`
  Locals that exist in every compiled passage's constructor.
  `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
  `class`
  `JitAllocationModel.JvmTempAlloc`
  `static final record`
  `JitAllocationModel.LongVarAlloc`
  The handler for a p-code variable allocated in one JVM `long`.
  `static final record`
  `JitAllocationModel.MultiLocalPart`
  `static final record`
  `JitAllocationModel.MultiLocalSub`
  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 enum`
  `JitAllocationModel.RunFixedLocal`
  Locals that exist in every compiled passage's `run` method.
  `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.JvmTempAlloc`
  `allocateTemp(org.objectweb.asm.MethodVisitor mv, String prefix, int count)`
  Temporarily allocate the next `count` indices of local `int` variables
  `JitAllocationModel.JvmTempAlloc`
  `allocateTemp(org.objectweb.asm.MethodVisitor mv, String prefix, Class<?> primitiveType, int count)`
  Temporarily allocate the next `count` indices of local variables
  `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

  ### 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 model
      `vsm` - the variable scope model
      `tm` - the type model

- ## Method Details

  - ### allocateTemp

    public JitAllocationModel.JvmTempAlloc allocateTemp(org.objectweb.asm.MethodVisitor mv, String prefix, Class<?> primitiveType, int count)
    Temporarily allocate the next `count` indices of local variables

    These indices are reserved only within the scope of the `try-with-resources` block creating the allocation. If the `primitiveType` is a `long` or `double`, then the number of actual indices allocated is multiplied by 2, such that the total number of variables is given by `count`.

    This should be used by operator code generators after all the local variables, including those used to bypass `state`, have been allocated, or else this may generate colliding indices. These variables ought to be released before the next operator's code generator is invoked.

    NOTE: This will automatically invoke `MethodVisitor.visitLocalVariable(String, String, String, Label, Label, int)` and place the appropriate labels for you.

    Parameters:
      `mv` - the method visitor
      `prefix` - the name of the local variable, or its prefix if count > 1
      `primitiveType` - the type of each variable. NOTE: If heterogeneous allocations are needed, invoke this method more than once in the `try-with-resources` assignment.
      `count` - the number of variables to allocate
    Returns:
      the handle to the allocation.

  - ### allocateTemp

    public JitAllocationModel.JvmTempAlloc allocateTemp(org.objectweb.asm.MethodVisitor mv, String prefix, int count)
    Temporarily allocate the next `count` indices of local `int` variables
    Parameters:
      `mv` - the method visitor
      `prefix` - the name of the local variable, or its prefix if count > 1
      `count` - the number of variables to allocate
    Returns:
      the handle to the allocation.
    See Also:
      - `allocateTemp(MethodVisitor, String, Class, int)`

  - ### 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
    Implementation Notes:
      This is used by the code generator to birth and retire the local variables, given that scope is analyzed in terms of varnodes.