% -*- mode: Noweb; noweb-code-mode: caml-mode -*- % $Id: frame.nw,v 1.15 2004-11-11 20:22:52 govereau Exp $ % --------------------------------------------------------------------------- \section{Stack Frames} \label{sec:frame} % --------------------------------------------------------------------------- The [[Frame]] module manages the stack frames of generated functions. Since we are generating [[C--]] code, we do not have access to the real stack frame, but we still need to track function parameters, local variables, and temporaries. This module provides the compiler with a mechanism for allocating new variables and temporaries within a function, and is responsible for generating the corresponding [[C--]] code. In addition, it is also convenient to track string literals using this module. A stack frame is represented by an abstract type [[frame]]. Each parameter, local, or temporary allocated results in a variable access specification. The variable access specification is represented by the type [[access]]. <>= type frame type access = Temp of Tree.label | Stack of frame * int * bool @ This module provides functions for reading elements of a stack frame. There are functions for reading the frame pointer, the name of the function associated with the frame, and the nesting level. <>= val fp : frame -> Tree.exp val name : frame -> Tree.label val level : frame -> int @ There are two functions for creating new stack frames. The [[base_frame]] function will create a stack frame for a top-level function, and [[new_frame]] will create a stack frame for a nested function. In Tiger, all functions are nested inside of the [[tiger_main]] function, so the compiler only uses [[new_frame]] for generated functions; [[base_frame]] is used for external library functions. <>= val base_frame : frame val new_frame : Tree.label -> frame -> frame @ There are four functions for allocating new parameters, local variables, temporary variables, and string literals. <>= val alloc_param : frame -> Tree.label -> bool -> access val alloc_local : frame -> Tree.label -> bool -> access val alloc_temp : frame -> Tree.label -> bool -> access val alloc_string : string -> Tree.label @ During code generation, this module will output a [[C--]] header and footer for each function that initializes the stack frame. In addition, this module will also output the string literals as initialized data. <>= val output_header : frame -> unit val output_footer : frame -> unit val output_strings : unit -> unit @ % --------------------------------------------------------------------------- \subsection{Stack Frame Implementation} % --------------------------------------------------------------------------- <>= module S = Symbol module T = Tree module H = Hashtbl @ A stack frame is a record containing a name, and nesting level, the size of the stack, and a list of variables. There are three types of variables: function parameters, stack allocated variables, and temporaries. For each variable we store the name and a boolean that is true if the variable holds a pointer. <>= type frame = { name : T.label ; level : int ; mutable size : int ; mutable params : (T.label * bool) list ; mutable vars : (T.label * bool) list ; mutable temps : (T.label * bool) list } type access = Temp of T.label | Stack of frame * int * bool @ The accessor functions for frames just read the appropriate elements from the record. In the case of the frame pointer, we return the name of the variable that holds the frame pointer. The name of the frame pointer variable is always [[fp]]. <>= let fp frm = T.NAME (S.symbol "fp") let name frm = frm.name let level frm = frm.level @ The base frame is a record with defaults for each field. Every function takes at least one parameter---its parent's frame pointer [[pfp]]. To create a new nested frame, we need to get the nesting level of the parent frame. Otherwise, a nested frame starts out with the same defaults as the base frame. <>= let base_frame = { name = (S.symbol "frame0") ; level = 0 ; params = [(S.symbol "pfp", true)] ; size = 1 ; vars = [] ; temps = [] } let new_frame lbl parent = { base_frame with name = lbl; level = parent.level + 1 } @ Allocated parameters and local variables both end up on the stack. In theory, a local variable could be allocated as a temporary variable as long as it is not referenced by a nested function. However, this optimization would require an escape analysis that this compiler does not currently do. To allocate parameters and locals, we update the appropriate list, increment the stack size and return a stack access specification. Function parameters must be kept in order they are allocated. <>= let stack_alloc frm ptr = let v = Stack(frm, frm.size, ptr) in frm.size <- frm.size + 1; v let alloc_param frm name ptr = frm.params <- frm.params @ [(name,ptr)]; stack_alloc frm ptr let alloc_local frm name ptr = frm.vars <- (name,ptr) :: frm.vars; stack_alloc frm ptr @ Allocating temporaries is similar, but we return an access specification for a temporary variable. A temporary variable is just a [[C--]] local variable, and we only need to remember the name of the variable. <>= let alloc_temp frm name ptr = frm.temps <- (name,ptr) :: frm.temps; Temp name @ When a new string literal is allocated, we first check to see if the same literal has already been allocated, and if so, we return a reference to the previously allocated string. Otherwise, we add the new string to the set, and return a new label. The implementation uses the standard library [[Hashtbl]] module to store the set of allocated strings. <>= let strings = H.create 20 let alloc_string s = try H.find strings s with Not_found -> let lbl = T.new_label "gbl" in (H.add strings s lbl; lbl) @ The output functions are a bit tedious to write and even more tedious to read. However, we can at least attempt to control the ensuing insanity with a few nice abbreviations and utility functions. <>= let pf = Printf.printf let spf = Printf.sprintf let join_map f l = String.concat "," (List.map f l) let iter_ndx f = let n = ref(-1) in let g x = incr n; f !n x in List.iter g @ For each function header, we output the function name and parameters. The function body is enclosed in a span that references the pointer data for the garbage collector. The body of each function begins by initializing the stack data locations that correspond to the formal parameters, and declaring of all temporaries. <>= let output_header frm = let param (p,_) = spf "bits32 %s" (S.name p) and init n (p,_) = pf " bits32[fp+%d] = %s;\n" (4*n) (S.name p) and temp (t,_) = pf " bits32 %s;\n" (S.name t) and name = (S.name frm.name) in pf "%s(%s) {\n" name (join_map param frm.params); pf " span 1 %s_gc_data {\n" name; pf " stackdata { align 4; fp : bits32[%d]; }\n" frm.size; iter_ndx init frm.params; List.iter temp frm.temps @ Each function is followed by the pointer information for the stack data and the [[C--]] variables. The stack data information is output first as an array of [[bits32]]. A second array follows with the pointer information for the [[C--]] variables. <>= let output_footer frm = let var_data vl = let int_of_var (_,p) = if p then 1 else 0 in let data = List.length vl :: List.map int_of_var vl in join_map string_of_int data in pf "}}\n"; pf "section \"data\" {\n"; pf " %s_gc_data:\n" (S.name frm.name); pf " bits32[] { %s };\n" (var_data (frm.params @ List.rev frm.vars)); pf " bits32[] { %s };\n" (var_data (frm.params @ frm.temps)); pf "}\n\n" @ For the string literals, we output a data section containing a label and initialized data for each string. <>= (* output *) let output_strings() = let print_string str lbl = let len = String.length str and str = String.escaped str in pf " %s: bits32 { %d }; bits8[] \"%s\\000\";\n" (S.name lbl) len str in pf "section \"data\" { align 4;\n"; H.iter print_string strings; pf "}\n\n" @