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 = acquire () in

The function works with the C int type:

let the_type = get_standard_type ctx Int in
let return_type = the_type in

Let's build the function:

let param_n = new_param ctx the_type "n" in
let func = new_function ctx 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 = new_binary_op ctx Mult int_type param_i 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.new_local, supplying a type and a name:

(* Build locals *)
let local_i = new_local func the_type "i" in
let sum = new_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 = new_block fn ~name:"initial" () in
let b_loop_cond = new_block fn ~name:"loop_cond" () in
let b_loop_body = new_block fn ~name:"loop_body" () in
let b_after_loop = new_block fn ~nmae:"after_loop" () 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; *)
add_assignment b_initial sum (zero ctx the_type);
add_assignment b_initial i (zero ctx the_type);

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

end_with_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 = new_comparison ctx Ge local_i 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; *)
end_with_conditional 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:

add_assignment_op b_loop_body sum Plus (new_binary_op ctx Mult the_type local_i 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++ *)
add_assignment_op b_loop_body local_i Plus (one ctx the_type)

NOTE: For numeric constants other than 0 and 1, we could use Gccjit.new_rvalue_from_int and Gccjit.new_rvalue_from_double.

The loop body completes by jumping back to the conditional:

end_with_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:

end_with_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 = compile ctx in
let loop_test = get_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:

dump_to_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 the_type = get_standard_type ctx Int in
  let return_type = the_type in
  let n = new_param ctx the_type "n" in
  let func = new_function ctx Exported return_type "loop_test" [ n ] in

  (* Build locals:  *)
  let i = new_local func the_type "i" in
  let sum = new_local func the_type "sum" in

  let b_initial = new_block func ~name:"initial" () in
  let b_loop_cond = new_block func ~name:"loop_cond" () in
  let b_loop_body = new_block func ~name:"loop_body" () in
  let b_after_loop = new_block func ~name:"after_loop" () in

  (* sum = 0; *)
  add_assignment b_initial sum (zero ctx the_type);

  (* i = 0; *)
  add_assignment b_initial i (zero ctx the_type);

  end_with_jump b_initial b_loop_cond;

  (* if (i >= n) *)
  end_with_conditional b_loop_cond (new_comparison ctx Ge i n) b_after_loop b_loop_body;

  (* sum += i * i *)
  add_assignment_op b_loop_body sum Plus (new_binary_op ctx Mult the_type i i);

  (* i++ *)
  add_assignment_op b_loop_body i Plus (one ctx the_type);

  end_with_jump b_loop_body b_loop_cond;

  (* return sum *)
  end_with_return b_after_loop sum

let () =
  try
    (* Get a "context" object for working with the library. *)
    let ctx = acquire () in

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

    (* Populate the context. *)
    create_code ctx;

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

    (* Extract the generated code from "result". *)
    let loop_test = get_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
  with
  | Error _ -> exit 1

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