Skip to content

Automatic Variable Localization

Jump to bottom
demarey edited this page Sep 22, 2021 · 2 revisions

One common optimization for language interpreters is to put critical variables in registers. From the point of view of a C program, this is implementable by caching those variables in local variables, hinting the C compiler to better optimize the reads/writes to those variables. Usual candidates for those optimizations are variables such as the stackPointer, the framePointer, the instructionPointer or even the value at the top of the stack.

A more general description of the optimization can be found in the following article: VMGen - A Generator of Efficient Virtual Machine Interpreters

This page describes the (in-progress) approach and the historical implementation of localization within the Slang VM generator.

Variable Localization in Slang

Status before

The Slang VM generator peforms as of today (21/09/2021) two simple localization algorithms:

  • (automatic) after inlining and removal of unreferenced methods, if a variable is only referenced a single method, the variable definition is moved locally to the said function
  • (semi-automatic) after inlining and customization of the interpreter switch cases, a fixed list of variables (localIP, localSP, localFP...) are always localized inside the function defining the interpreter loop. All other methods referencing those variables are considered broken. The goal being that within the interpreter, the local variable is used, and outside of it functions should refer to a global variable (i.e., respectively instructionPointer, stackPointer, framePointer...).

A consequence of this semi-automatic localization of the variables in the interpreter loop function (e.g., localIP) is that values should be copied from/to the local and global variables. Moreover, nowadays such copies are explicitly managed in the VM's source code. This means that every piece of code that is supposed to escape the scope of the interpreter loop function, is surrounded with so-called externalization and internalization of those variable values. In general, this means that all functions that are meant to be inlined can freely access the localized versions of the variables, and those that are never inlined (e.g., by means of a inline:false annotation) should always access the global versions.

bytecodePrimBitOr
  | rcvr arg |
  arg := self internalStackTop.
  rcvr := self internalStackValue: 1.
  
  "Type checks and fast path"
  [...]

  "Slow path, call the primitive code, which is not inlined and thus requires externalization/internalization"
  self externalizeIPandSP.
  self primitiveBitOr.
  self internalizeIPandSP.

  "Continue and check the values
  [...]

Objective

In order to make the VM easier to read, understand and modify, variable localization is certainly a task that can be automated in the VM generator. The goal of this proposal is to present an automatic approach for variable localization, where VM developers hint the translator with the variables to localize, and the translator performs the correct transformations automatically in the target source code. The manual localization historically used in the VM will still be functional, although ideally replaceable by the automatic approach.

In the proposed approach, VM developers hint methods with the variables to localize inside that method the following manner:

interpret
  <localizedVariable: #autoLocalizedVariable>

  [...]

The VM translator will then:

  • create a local variable for the global variable inside that method
  • surround all escaping calls with proper copies (local->global upon call, global->local upon return)

Transformations

This transformation will be implemented as a series of transformations:

  1. During inlining, all inlined usages of the global variable are replaced by the corresponding local variable
  2. During inlining, all non-inlined messages are surrounded by copy instructions (local->global upon call, global->local upon return)
  3. At the entry of the method, all localized variables are initialized with the values of the global variables
  4. At each return point, all values in localized variables are copied back to their corresponding global variables

Special care must be taken when calls are used as expressions, and in particular when those expressions modify the localized variables.

Moreover, this process can be enhanced with an optimization pass that:

  • avoids copies when we can statically determine that the called function does not use the localized variable
  • collapses sequences of copies when we find sequences of non-inlined calls

Current Status

The current status can be found in the following branch.

DONE

  • We should internalize it at the beginning of the function
  • If we inline a method, we should replace the localizable variables by their localized versions
  • We should externalize it at the return of the function
  • Wrapping non-inlined calls Scenario)
    self call
    =>
    externalize
    self call
    internalize

TODO

  • Wrapping non-inlined calls Scenario 2) assignments to calls, nested calls?
  x := self call

  externalize
  r := self call (careful that x is not affected by the transformation)
  internalize
  x := r
  • Wrapping non-inlined calls Scenario 3) optimizing to wrap only with variables in the called methods!
  • externalize at return with multiple returns
  • extenralize at return when the return has an expression (using the conflictive variables)!!!
  • manage name conflicts and automatic name mangling. What if a variable claled local_autoLocalizedVariable already existed?
Clone this wiki locally