Exercises for Week 5

Exercise overview

This week’s exercises are about programmatic generation of LLVM. There are two workhorse modules that we give you:

• ll.ml that is the module for representing LLVM programs.

• cfgBuilder is the module for on-the-fly generation of LLVM programs.

Using Ll and CfgBuilder modules

Ll module includes the auxiliary data structures for representing LLVM– programs. The main top-level declaration is that of prog. This module includes a pretty printer for LLVM programs in the function string_of_prog. CfgBuilder provides an API for representing LLVM fragments.

As a starting exercise, try out the following example programs from the lecture

module Sym = Symbol 
let symbol = Sym.symbol

(* minimal LLVM program returning 0 *)

let llprog_01 = let open Ll in 
   let cfg = { insns =  []; terminator = Ret (I64, Some (IConst64 0L))}, [] in

   { tdecls    = []
   ; extgdecls = []
   ; gdecls    = []
   ; extfuns   = [ (symbol "print_integer",  ([I64], Void))
                 ; (symbol "read_integer", ([], I64))]
   ; fdecls = [ (Sym.symbol "dolphin_main", 
                 { fty = ([],  I64); param = []; cfg}  
                )] 
   }
 
(* Different ways of expressing the following computation 
   
   var x = read_integer () ;
   var y = x + 1;
   print_integer (y);
   return 0;
   
*)

let llprog_02 = let open Ll in 
   let insns = [
      Some (symbol "x" ), Call (I64, (Gid (symbol "read_integer")), []) 
   ;  Some (symbol "y"), Binop (Add, I64, Id (symbol "x"), IConst64 1L)
   ;  None, Call (Void, Gid (symbol "print_integer"), [I64, Id (symbol "y")])
   ] in

   let cfg = { insns 
             ; terminator = Ret (I64, Some (IConst64 0L))}, [] in

   { tdecls    = []
   ; extgdecls = []
   ; gdecls    = []
   ; extfuns   = [ (symbol "print_integer",  ([I64], Void))
                 ; (symbol "read_integer", ([], I64))]
   ; fdecls = [ (Sym.symbol "dolphin_main", 
                 { fty = ([],  I64); param = []; cfg}  
                )] 
   }

let llprog_03 = let open Ll in 
   let sym_x = symbol "x" in 
   let sym_y = symbol "y" in 
   let sym_read_integer = symbol "read_integer" in 
   let sym_print_integer = symbol "print_integer" in 
   let insns = [
      Some sym_x, Call (I64, (Gid sym_read_integer), []) 
   ;  Some sym_y, Binop (Add, I64, Id sym_x, IConst64 1L)
   ;  None, Call (Void, Gid sym_print_integer, [I64, Id sym_y])
   ] in

   let cfg = { insns 
             ; terminator = Ret (I64, Some (IConst64 0L))}, [] in

   { tdecls    = []
   ; extgdecls = []
   ; gdecls    = []
   ; extfuns   = [ (symbol "print_integer",  ([I64], Void))
                 ; (symbol "read_integer", ([], I64))]
   ; fdecls = [ (Sym.symbol "dolphin_main", 
                 { fty = ([],  I64); param = []; cfg}  
                )] 
   }


let llprog_04 = let open Ll in let open CfgBuilder in  
   let sym_x = symbol "x" in 
   let sym_y = symbol "y" in 
   let sym_read_integer = symbol "read_integer" in 
   let sym_print_integer = symbol "print_integer" in 

   let b1 = empty_cfg_builder in 
   let b2 = add_insn (Some sym_x, Call (I64, Gid sym_read_integer, [])) b1 in 
   let b3 = add_insn (Some sym_y, Binop (Add, I64, Id sym_x, IConst64 1L)) b2 in 
   let b4 = add_insn (None      , Call (Void, Gid sym_print_integer, [I64, Id sym_y])) b3 in
   let b5 = term_block (Ret (I64, Some (IConst64 0L))) b4 in 
   let cfg = get_cfg b5 in 
   { tdecls    = []
   ; extgdecls = []
   ; gdecls    = []
   ; extfuns   = [ (symbol "print_integer",  ([I64], Void))
                 ; (symbol "read_integer", ([], I64))]
   ; fdecls = [ (Sym.symbol "dolphin_main", 
                 { fty = ([],  I64); param = []; cfg}  
                )] 
   }

let llprog_05 = let open Ll in let open CfgBuilder in  
   let sym_x = symbol "x" in 
   let sym_y = symbol "y" in 
   let sym_read_integer = symbol "read_integer" in 
   let sym_print_integer = symbol "print_integer" in 

   let i1 = add_insn (Some sym_x, Call (I64, Gid sym_read_integer, [])) in 
   let i2 = add_insn (Some sym_y, Binop (Add, I64, Id sym_x, IConst64 1L)) in 
   let i3 = add_insn (None      , Call (Void, Gid sym_print_integer, [I64, Id sym_y])) in

   let tr = term_block (Ret (I64, Some (IConst64 0L))) in

   let cfg = get_cfg (tr (i3 (i2 (i1 empty_cfg_builder)))) in 

   { tdecls    = []
   ; extgdecls = []
   ; gdecls    = []
   ; extfuns   = [ (symbol "print_integer",  ([I64], Void))
                 ; (symbol "read_integer", ([], I64))]
   ; fdecls = [ (Sym.symbol "dolphin_main", 
                 { fty = ([],  I64); param = []; cfg}  
                )] 
   }

let llprog_06 = let open Ll in let open CfgBuilder in  
   let sym_x = symbol "x" in 
   let sym_y = symbol "y" in 
   let sym_read_integer = symbol "read_integer" in 
   let sym_print_integer = symbol "print_integer" in 

   let i1 = add_insn (Some sym_x, Call (I64, Gid sym_read_integer, [])) in 
   let i2 = add_insn (Some sym_y, Binop (Add, I64, Id sym_x, IConst64 1L)) in 
   let i3 = add_insn (None      , Call (Void, Gid sym_print_integer, [I64, Id sym_y])) in
   let tr = term_block (Ret (I64, Some (IConst64 0L))) in

   let composed_block = seq_buildlets [i1; i2; i3; tr] in 

   let cfg = get_cfg (composed_block empty_cfg_builder) in 

   { tdecls    = []
   ; extgdecls = []
   ; gdecls    = []
   ; extfuns   = [ (symbol "print_integer",  ([I64], Void))
                 ; (symbol "read_integer", ([], I64))]
   ; fdecls = [ (Sym.symbol "dolphin_main", 
                 { fty = ([],  I64); param = []; cfg}  
                )] 
   }
    

let () = 
   let s = Ll.string_of_prog llprog_06 in 
   output_string stdout s 

More complicated example with CfgBuilder

As a follow-up exercise, generate the code for a factorial function in LLVM using the available API.