Package ghidra.pcode.emu.jit.analysis

# Class JitVarScopeModel

java.lang.Object
ghidra.pcode.emu.jit.analysis.JitVarScopeModel

public class JitVarScopeModel extends Object
The variable scope analysis of JIT-accelerated emulation.

This implements the Variable Scope Analysis phase of the `JitCompiler`. The result provides the set of in-scope (alive) varnodes for each basic block. The design of this analysis, and the shortcuts we take, are informed by the design of downstream phases. In particular, we do not intend to allocate each SSA variable. There are often many, many such variables, and attempting to allocate them to as few target resources, e.g., JVM locals, as possible is probably a complicated and expensive algorithm. I don't think we'd gain much from it either. Instead, we'll just allocate by varnode. To do that, though, we still have to consider that some varnodes overlap and otherwise alias others. If we are able to handle all that aliasing in place, then we need not generate code for the synthetic ops. One might ask, well then why do any of the Data Flow Analysis in the first place? 1) We still need data flow to inform the selection of JVM local types. We have not measured the run-time cost of the bitwise casts, but we do know the bytecode for each cast occupies space, counted against the 65,535-byte max. 2) We also need data flow to inform operation elimination, which removes many wasted flag computations.

To handle the aliasing, we coalesce overlapping varnodes. For example, `EAX` will get coalesced with `RAX`, but `BH` will not get coalesced with `BL`, assuming no other part of `RBX` is accessed. The `JitDataFlowModel` records all varnodes accessed in the course of its intra-block analysis. Only those actually accessed are considered. We then compute scope in terms of these coalesced varnodes. For example, if both `RAX` and `EAX` are used by a passage, then an access of `EAX` causes `RAX` to remain in scope.

The decision to compute scope on a block-by-block basis instead of op-by-op is for simplicity. We intend to birth and retire variables along block transitions by considering what variables are coming into or leaving scope on the flow edge. Birthing is just reading a variable's value from the run-time `state` into its allocated JVM local. Conversely, retiring is writing the value back out to the state. There's little to be gained by retiring a variable midway through a block as opposed to the end of the block. Perhaps if one giant block handles a series of variables in sequence, we could have used a single JVM local to allocate each, but we're already committed to allocating a JVM local per (coalesced) varnode. So, while that may ensure only one variable is alive at a time, the number of JVM locals required remains the same. Furthermore, the amount of bytecode emitted remains the same, but at different locations in the block. The case where this might be worth considering is a userop invocation, because all live variables must be forcefully retired.

We then consider what common cases we want to ensure are optimized, when we're limited to a block-by-block analysis. One that comes to mind is a function with an early bail. Consider the following C source:

     int func(my_struct* ptr) {
       if (ptr == NULL) {
         return ERR;
       }
       // Do some serious work
       return ptr->v;
     }

Often, the C compiler will group all the returns into one final basic block, so we might get the following p-code:

      1   RSP    = INT_SUB RSP, 0x20:8
      2   $U00:1 = INT_EQUAL RDI, 0:8     # RDI is ptr
      3            CBRANCH <err>, $U0:1

      4            # Do some serious work
      5   $U10:8 = INT_ADD RDI, 0xc:8     # Offset to field v
      6   EAX    = LOAD [ram] $U10:8
      7            BRANCH <exit>
     <err>
      8   EAX    = COPY 0xffffffff:4
     <exit>
      9   RSP    = INT_ADD RSP, 0x20:8
      10  RIP    = LOAD [ram] RSP
      11  RSP    = INT_ADD RSP, 8:8
      12           RETURN RIP

Note that I've elided the actual x86 machine code and all of the noise generated by C compilation and p-code lifting, and I've presumed the decoded passage contains exactly the example function. The result is your typical if-else diamond. We'll place the error case on the left:

         +---------+
         |   1--3  |
         | CBRANCH |
         +-T-----F-+
          /       \
         /         \
     +--------+ +--------+
     |   8    | |  4--7  |
     | (fall) | | BRANCH |
     +--------+ +--------+
         \         /
          \       /
         +---------+
         |  9--12  |
         | RETURN  |
         +---------+

Suppose the "serious work" on line 4 accesses several varnodes: RBX, RCX, RDX, and RSI. If execution follows the error path, we'd rather not birth any of those variables. Thus, we might like the result of the scope analysis to be:

Block | Live Vars
--- | ---
1–3 | RDI, RSP, $U00:1
4–7 | EAX, RBX, RCX, RDI, RDX, RSI, RSP, $U10:8
8 | EAX, RSP
9–12 | RIP, RSP

This can be achieved rather simply: Define two sets for each block, the upward view and the downward view. The first corresponds to all varnodes that could be accessed before entering this block or while in it. The second corresponds to all varnodes that could be access while in this block or after leaving it. The upward view is computed by initializing each set to the varnodes accessed by its block. Then we "push" each set upward by adding its elements into the set for each block with flows into this one, until the sets converge. The downward sets are similarly computed, independently of the upward sets. The result is the intersection of these sets, per block. The algorithm is somewhat intuitive in that we accrue live variables as we move toward the "body" of the control flow graph, and they begin to drop off as we approach an exit. The accrual is captured by the downward set, and the drop off is captured by intersection with the upward set. This will also prevent retirement and rebirth of variables. Essentially, if we are between two accesses of a varnode, then that varnode is alive. Consider `RSP` from the example above. The algorithm considers it alive in blocks 4–7 and 8, despite the fact neither actually accesses it. Nevertheless, we'd rather generate one birth upon entering block 1–3, keep it alive in the body, and then generate one retirement upon leaving block 9–12.

One notable effect of this algorithm is that all blocks in a loop will have the same variables in scope.... I think this is okay. We'll birth the relevant variables upon entering the loop, keep them all alive during loop execution, and then retire them (unless they're accessed downstream) upon leaving.

Implementation Notes:
  TODO: There's some nonsense to figure out with types. It would be nice if we could allow variables of different types to occupy the same location at different times. This can be the case, e.g., if a register is used as a temporary location for copying values around. If there are times when it's treated as an int and other times when it's treated as a float, we could avoid unnecessary Java type conversions. However, this would require us to track liveness with types, and at that granularity, it could get unwieldy. My inclination is to just consider location liveness and then have the allocator decide what type to assign the local variable for that location based on some voting system. This is not the best, because some access sites are executed more often than others, but it'll suffice.

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `JitVarScopeModel(JitControlFlowModel cfm, JitDataFlowModel dfm)`
  Construct the model

- ## Method Summary

  Modifier and Type
  Method
  Description
  `Iterable<Varnode>`
  `coalescedVarnodes()`
  Get the collection of all coalesced varnodes
  `void`
  `dumpResult()`
  For diagnostics: Dump the analysis result to stderr
  `Varnode`
  `getCoalesced(Varnode part)`
  Get the varnode into which the given varnode was coalesced
  `Set<Varnode>`
  `getLiveVars(JitControlFlowModel.JitBlock block)`
  Get the set of live varnodes for the given block

  ### Methods inherited from class java.lang.Object

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

- ## Constructor Details

  - ### JitVarScopeModel

    public JitVarScopeModel(JitControlFlowModel cfm, JitDataFlowModel dfm)
    Construct the model
    Parameters:
      `cfm` - the control flow model
      `dfm` - the data flow model

- ## Method Details

  - ### getCoalesced

    public Varnode getCoalesced(Varnode part)
    Get the varnode into which the given varnode was coalesced

    In many cases, the result is the same varnode.

    Parameters:
      `part` - the varnode
    Returns:
      the coalesced varnode

  - ### coalescedVarnodes

    public Iterable<Varnode> coalescedVarnodes()
    Get the collection of all coalesced varnodes
    Returns:
      the varnodes

  - ### getLiveVars

    public Set<Varnode> getLiveVars(JitControlFlowModel.JitBlock block)
    Get the set of live varnodes for the given block
    Parameters:
      `block` - the block
    Returns:
      the live varnodes

  - ### dumpResult

    public void dumpResult()
    For diagnostics: Dump the analysis result to stderr
    See Also:
      - `JitCompiler.Diag.PRINT_VSM`