Tutorial part 3: Loops and variables

Consider this C function:

int loop_test (int n)
{
  int sum = 0;
  for (int i = 0; i < n; i++)
    sum += i * i;
    return sum;
}

This examples demonstrates some more features of libgccjit, with local variables and a loop.

To break this down into libgccjit terms, it's usually easire to reword the for loop as a while loop, giving:

int loop_test (int n)
{
  int sum = 0;
  int i = 0;
  while (i < n)
  {
    sum += i * i;
    i++;
  }
  return sum;
}

Here's what the final control flow graph will look like:

As before, we open the Gccjit module and make a Gccjit.context.

open Gccjit

let test () =
  let ctx = Context.create () in

The function works with the C int type:

let the_type = Type.(get ctx Int) in
let return_type = the_type in

Let's build the function:

let param_n = Param.create ctx the_type "n" in
let func = Function.create ctx Function.Exported return_type "loop_test" [ param_n ] in

Expressions: lvalues and rvalues

The type of expressions is Gccjit.rvalue, representing an expression that can be on the right-hand side of an assignment: a value that can be computed somehow, and assigned to a storage area (such as a variable). It has a specific Gccjit.type_.

Another important type is Gccjit.lvalue. A Gccjit.lvalue is something that can be the left-hand side of an assignment: a storage area (such as a variable).

In other words, every assignment can be thought of as:

LVALUE = RVALUE

Note that Gccjit.lvalue is a subtype of Gccjit.rvalue, where in an assignment of the form

LVALUE_A = LVALUE_B

the LVALUE_B implies reading the current value of that storage area, assigning it into the LVALUE_A.

So far the only expressions we've seen are i * i:

let expr = RValue.binary_op ctx Mult int_type (RValue.param param_i) (RValue.param param_i) in

which is a Gccjit.rvalue, and the various function parameters: param_i and param_n, of type Gccjit.param, which is a subtype of Gccjit.lvalue (and, in turn of Gccjit.rvalue): we can both read from and write to function parameters within the body of a function.

Our new example has a couple of local variables. We create them by calling Gccjit.Function.local, supplying a type and a name:

(* Build locals *)
let local_i = Function.local func the_type "i" in
let sum = Function.local func the_type "sum" in

These are instances of Gccjit.lvalue -- they can be read from and written to.

Note that there is no precanned way to create and initialize a variable like in C:

int i = 0;

Instead, having added the local to the function, we have to separately add an assignment of 0 to local_i at the beginning of the function.

Control flow

This function has a loop, so we need to build some basic blocks to handle the control flow. In this case, we need 4 blocks:

1. before the loop (initializing the locals)
2. the conditional at the top of the loop (comparing i < n)
3. the body of the loop
4. after the loop terminates (return sum)

so we create these as Gccjit.block instances within the Gccjit.function_:

let b_initial = Block.create ~name:"initial" fn in
let b_loop_cond = Block.create ~name:"loop_cond" fn in
let b_loop_body = Block.create ~name:"loop_body" fn in
let b_after_loop = Block.create ~nmae:"after_loop" fn in

We now populate each block with statements.

The entry block b_initial consists of initializations followed by a jump to the conditional. We assign 0 to i and sum, using Gccjit.add_assignment to add an assignment statement, and using Gccjit.zero to get the constant value 0 for the relevant type for the right-hand side of the assignment:

(* sum = 0; *)
Block.assign b_initial sum (RValue.zero ctx the_type);
Block.assign b_initial i (RValue.zero ctx the_type);

We can the terminate the entry block by jumping to the conditional:

Block.jump b_initial b_loop_cond;

The conditional block is equivalent to the line while (i < n) from our C example. It contains a single statement: a conditional, which jumps to one of two destination blocks depending on a boolean Gccjit.rvalue, in this case the comparison of i and n. We build the comparison using Gccjit.new_comparison:

(* (i >= n) *)
let guard = RValue.comparison ctx Ge (RValue.lvalue local_i) (RValue.param param_n) in

and can then use this to add b_loop_cond's sole statement, via Gccjit.end_with_conditional:

(* Equivalent to:
    if (guard)
      goto after_loop;
    else
      goto loop_body; *)
Block.cond_jump b_loop_cond guard
  b_after_loop (* on true *)
  b_loop_body; (* on false *)

Next, we populate the body of the loop.

The C statement sum += i * i; is an assignment operation, where an lvalue is modified "in-place". We use Gccjit.add_assignment_op to handle these operations:

Block.assign_op b_loop_body sum Plus
  (RValue.binary_op ctx Mult the_type (RValue.lvalue local_i) (RValue.lvalue local_i))

The i++ can be thought of as i += 1, and can thus be handled in a similar way. We use Gccjit.one to get the constant value 1 (fro the relevant type) for the right-hand side of the assignment.

(* i++ *)
Block.assign_op b_loop_body local_i Plus (RValue.one ctx the_type)

NOTE: For numeric constants other than 0 and 1, we could use Gccjit.RValue.int and Gccjit.RValue.double.

The loop body completes by jumping back to the conditional:

Block.jump b_loop_body b_loop_cond;

Finally, we populate the b_after_loop block, reached when the loop conditional is false. We want to generate the equivalent of:

return sum;

so the block is just one statement:

Block.return b_after_loop local_sum;

NOTE: You can intermingle block creation with statement creation, but given that the terminator statements generally include references to other blocks, I find it's clearer to create all the blocks, then all the statements.

We've finished populating the function. As before, we can compile it to machine code:

let result = Context.compile ctx in
let loop_test = Result.code result Ctypes.(int @-> returning int) in
Printf.printf "result: %d\n%!" (loop_test 10)

result: 285

Visualizing the control flow graph

You can see the control flow graph of a function using Gccjit.dump_to_dot:

Function.dump_dot func "/tmp/sum-of-squares.dot"

giving a .dot file in GraphViz format.

You can convert this to an image using dot:

$ dot -Tpng /tmp/sum-of-squares.dot -o /tmp/sum-of-squares.png

or use a viewer (on OS X you can install one with brew install --with-app graphviz).

Full example

(* Usage example for libgccjit *)

open Gccjit

let create_code ctx =
  (*
    Simple sum-of-squares, to test conditionals and looping

    int loop_test (int n)
    {
      int i;
      int sum = 0;
      for (i = 0; i < n ; i ++)
      {
	sum += i * i;
      }
      return sum;
   *)

  let n = Param.create ctx Type.(get ctx Int) "n" in
  let func = Function.create ctx Function.Exported Type.(get ctx Int) "loop_test" [ n ] in

  (* Build locals:  *)
  let i = Function.local func Type.(get ctx Int) "i" in
  let sum = Function.local func Type.(get ctx Int) "sum" in

  let b_initial = Block.create ~name:"initial" func in
  let b_loop_cond = Block.create ~name:"loop_cond" func in
  let b_loop_body = Block.create ~name:"loop_body" func in
  let b_after_loop = Block.create ~name:"after_loop" func in

  (* sum = 0; *)
  Block.assign b_initial sum (RValue.zero ctx Type.(get ctx Int));

  (* i = 0; *)
  Block.assign b_initial i (RValue.zero ctx Type.(get ctx Int));

  Block.jump b_initial b_loop_cond;

  (* if (i >= n) *)
  Block.cond_jump b_loop_cond (RValue.comparison ctx Ge (RValue.lvalue i) (RValue.param n))
    b_after_loop b_loop_body;

  (* sum += i * i *)
  Block.assign_op b_loop_body sum Plus
    (RValue.binary_op ctx Mult Type.(get ctx Int) (RValue.lvalue i) (RValue.lvalue i));

  (* i++ *)
  Block.assign_op b_loop_body i Plus (RValue.one ctx Type.(get ctx Int));

  Block.jump b_loop_body b_loop_cond;

  (* return sum *)
  Block.return b_after_loop (RValue.lvalue sum)

let () =
  let ctx = Context.create () in

  (* Set some options on the context.  Let's see the code being generated, in
     assembler form. *)
  Context.set_option ctx Context.Dump_generated_code true;

  (* Populate the context. *)
  create_code ctx;

  (* Compile the code. *)
  let result = Context.compile ctx in

  (* Extract the generated code from "result". *)
  let loop_test = Result.code result "loop_test" Ctypes.(int @-> returning int) in

  (* Run the generated code. *)
  let v = loop_test 10 in
  Printf.printf "loop_test returned: %d\n%!" v;

  Context.release ctx;
  Result.release result

Building and running it:

$ ocamlbuild -package gccjit tut03_sum_of_squares.byte
# Run the built program:
$ ./tut03_sum_of_squares.byte
loop_test returned: 285