Step 2: Adding Bit Operations To Golo

As discussed in the previous post, we will eventually try to improve the numerical performance of Golo by adding Graal JIT compilation. However, for the chosen Mandelbrot benchmark we first need to add support for bit operations to Golo. The main reason for doing this exercise first is to get a better understanding of how the current Golo implementation works. It was designed as dynamic language to exploit the invokedynamic support of the JVM. To be able to do that, Golo uses a bytecode compilation approach. So, instead of using the abstract-syntax-tree (AST) the parser creates from the source program directly for execution, the AST is first compiled to bytecodes, which are then executed by the JVM. While this post dives into some of the details, an earlier paper on Golo can provide a few more insights.

Adapting the Parser

Golo’s parser is built with JavaCC. Thus, the Golo grammar is specified in some extended variant of BNF. The parser generated by JavaCC takes .golo files and produces ASTs, which are then in multiple steps transformed to bytecodes.

To add bit operations, we need to add new binary operators to the language. Currently, Golo does neither support xor (^), left shift (<<), nor or (|). To avoid messing with the language designer’s desired aesthetics, we will use the simplest and ugliest solution here and just hope they won’t adopt it, but find something that fits in the language instead. So, we are simply adding the three keywords bitXOR, bitLSHIFT, and bitOR.

This means, we extend the Golo grammar by adding BIT_OPERATOR to the definition of TOKEN:

TOKEN :
{
  < MULTIPLICATIVE_OPERATOR: ("*" | "/" | "%") >
  |
  < BIT_OPERATOR: ("bitOR" | "bitLSHIFT" | "bitXOR") >
  |
// ...

Now, the parser can recognize these tokens in a program. To parse them as part of an expression, we need to adapt how binary expressions, i.e., expressions with two operands are parsed. In many languages, bit operators have the highest precedence. Thus, we adapt the rule for MultiplicativeExpression, which currently is the one that then falls back to unary expressions. The new rule for BitExpressions is listed below. It essentially means that the left operand of a BitExpression is parsed as a UnaryExpression, then there might by blank lines, then we need a BIT_OPERATOR, and eventually we expect the right operand, which itself can be some invocation.

void BitExpression() #void:
{
  Token token = null;
}
{
  UnaryExpression()
  (
    LOOKAHEAD(2) (BlankLine())? token=<BIT_OPERATOR> (BlankLine())? InvocationExpression()
    {
      jjtThis.addOperator(token.image);
    }
  )* #BitExpression(token != null)
}

The JavaCC parser uses these rules to produce code that instantiates an ASTBitExpression object, which holds the operator and the child expressions. As we see in later posts, this structure is already very close to the Truffle ASTs we will use for execution. For basic Golo however, we first need some more changes to get the bit operations working.

Implementing The Bit Operations

The basic operators are implemented in the OperatorSupport class. We merely add the following three functions:

public static Object bit_lshift(Integer a, Integer b) {
  return a << b;
}

public static Object bit_or(Integer a, Integer b) {
  return a | b;
}

public static Object bit_xor(Integer a, Integer b) {
  return a ^ b;
}

One might notice that all arguments and return values are proper objects. In our case, the arguments are Integer instead of the primitive int. Thus, the values on which basic operations are performed need to be boxed. The main reason for this design is most likely the use of invokedynamic and the benefits of a simple uniform representation.

Using InvokeDynamic To Execute Bit Operations

Before these methods can be invoked, the necessary bytecode needs to be generated. Golo uses an intermediate representation to simplify bytecode generation by ensuring some basic properties of the language. For the bit operations, we needed to add a visit(.) method for ASTBitExpression in the visitor that transforms the JavaCC AST into the Golo intermediate representation. For brevity, we skip over the details, which can be seen in the corresponding patch.

For the bytecode generation, we can have a look at the JavaBytecodeGenerationGoloIrVisitor class. The following method handles all binary operations, which includes our bit operators:

void genericBinaryOperator(BinaryOperation binaryOperation, OperatorType operatorType) {
  binaryOperation.getLeftExpression().accept(this);
  binaryOperation.getRightExpression().accept(this);
  if (!isMethodCall(binaryOperation)) {
    String name = operatorType.name().toLowerCase();
    methodVisitor.visitInvokeDynamicInsn(
      name, goloFunctionSignature(2), OPERATOR_HANDLE, (Integer) 2);
  }
}

While this is a small and simple method, one gets a bit of the feeling of how the bytecode generation works. The first thing the method does is to take the left expression and generate bytecode for it. Afterwards, it generates the bytecode for the right expression. To fully understand what this means, we need to recall that the JVM is a stack machine. So, after the bytecode was executed that belongs to the left expression, the result will remain on the stack. This is not obvious here, and only implied by the JVM’s execution semantics. Similarly, the right hand side will also be evaluated to a value on the stack. In the simplest case, this means, there are now two values on the stack.

For our bit operations, the next step is crucial. It will take the operator type and convert its name into lower case, which then corresponds to our bit_xor, bit_lshift, or bit_or methods. Afterwards, it creates an invokedynamic call to these methods. The call consumes the two values on the stack that the left and right expression produced, and will push a new result value onto the stack. The code of the bytecode generation hides much of these details. But, I hope this discussion gives an impression of what happens during compilation as well as later during execution.

Conclusion

To summarize, Golo uses a three-step approach to bytecode generation. In the first step, the JavaCC-based parser generates an AST. This AST is than transformed in a more convenient intermediate representation, which is then in a third step compiled to bytecodes.

As we could see above, Golo relies on invokedynamic and uses a uniform Object-based representation for all values.

In the next post, we will finally start with the basics of how to apply Graal and Truffle to Golo and implement as sufficient set of the language to run a classic Fibonacci computation.

Acknowledgements

I’d like to thank Julien Ponge for his comments on drafts of this tutorial and his help with the technical details of Golo.

“Add Graal JIT Compilation to Your JVM Language in 5 Easy Steps” by Stefan Marr is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Permissions beyond the scope of this license are available on request.