CodeGenAbacus Module
This module implements functions for translating cmd programs to Abacus assembler programs. To this end, functions for dataflow analysis, in particular, the liveness of variables are provided that are used to build interference graphs of the variables used, which in turn are used to compute static register allocators with a graph coloring approach. Based on such a register allocator, the final generation of Abacus assembler instructions from a cmd program is not difficult (and also provided).
Types
Type | Description |
CompiledThread holds the results obtained by compiling a thread |
Functions and values
Function or value | Description |
|
Compute a static register allocation by the optimistic ChaitinBriggs heuristic: remove a node with minimal number of neighbors, color the remaining graph, and then give the formerly removed node a color different to its neighbors. The function expects an undirected graph given as Set<'a> of nodes and Set<'a * 'a> of nodes, such that each edge defines a conflict between the nodes. The function returns a Map<'a,int> where nodes of the graph are mapped to colors (=integers). Note that the function below will color every graph with as few colors as possible (thought this is not guaranteed as it is only a heuristic). It may exceed the number of allowed colors (=registers) in which case, some of the colors must be identified with the main memory.
|
|
This function implements a code generator for Abacus based on a given static register mapping regMap (it maps variables to register indices) and a memory mapping memMap (it maps variables to memory addresses). Global variables are always mapped to memory, and local variables can either be mapped to memory or to a register. Several local variables can share a register if and only if they are not in conflict. If a local variable is mapped to a register, there is no memory address for it, and it is therefore never loaded nor stored to memory. If these variables are not initialized, they may inherit the value of another local variable that is mapped to the same register if that other variable was located before in their register. Moreover, the code generator needs two registers as temporary registers, and to this end, registers r0 and r7 are chosen. The result is a pair (abcProg,comments) where abcProg is a map that maps program lines to Abacus instructions, and comments is a map that adds comments to these program lines (which are the cmd instructions that produced that Abacus code).
|
Full Usage:
CompileMC ostr (arg2, arg3, arg4, arg5) cgi mcp
Parameters:
'a option
arg1 : bool
arg2 : bool
arg3 : bool
arg4 : bool
cgi : bool
mcp : MiniCProgram
Returns: int * Map<string, int> * CompiledThread array
|
Function CompileMC is used to compile all threads of a MiniC program. Functions in the MiniC program are ignored here, since it is assumed that the functions were inlined before calling this function, or by this function. The result is a triple (nxtAdr,memMap,abcThrds) where [0..nxtAdr-1] are the memory addresses needed for the static memory allocation, memMap defines where global and some of the local and temporary variables are mapped in that memory, and abcThrds is an array that holds the results of the compilation of the threads of the MiniC program mcp.
|
Full Usage:
CompileThread ostr (arg2, arg3, arg4, arg5) cgi glbDcls funcArr (nxtAdr, oldMemMap, abcThrds) (thName, thStmt)
Parameters:
'a option
arg1 : bool
arg2 : bool
arg3 : bool
arg4 : bool
cgi : bool
glbDcls : (string * TypeC) array
funcArr : MiniCFunction[]
nxtAdr : int
oldMemMap : Map<string, int>
abcThrds : CompiledThread array
thName : string
thStmt : StmtC
Returns: int * Map<string, int> * CompiledThread array
|
Function CompileThread is used as a folding function over the thread array of a MiniC program. It is given an optional output stream ostr, a flag cgi to indicate whether run in a cgi-script (in that case, the control and control dataflow graphs are included as svg graphics), and the declaration of the global/shared variables. A state of the folding function is given by (nxtAdr,oldMemMap,abcThrds) where nxtAdr is the next address that can be allocated by the memory mappings, oldMemMap is the so far constructed memory mapping of the variables, and abcThrds is the array of CompiledThread results obtained so far. Hence, the function computes a new CompiledThread result for the thread (thName,thStmt) and adds that result to abcThrds with obvious updates to nxtAdr,oldMemMap for folding further.
|
Full Usage:
DependenceGraph2DotFile ostr (raw, war, waw)
Parameters:
TextWriter
raw : (int * int * string) seq
war : (int * int * string) seq
waw : (int * int * string) seq
|
Writes colored dependence graph as dot file.
|
This function computes the interference graph of the given cmd program, where additionally the mappings of live and used variables as computed by functions LivenessAnalysis and UsedAnalysis are expected as arguments. The nodes of the generated graph are the variables of the cmd program, and there is an edge between variables x1 and x2 if both occur in the intersection of Used(l) and Live(l) of some command line l. Since the interference graph is an undirected graph, it is represented as the set of its edges (x1,x2) between variables. Note that an uninitialized variable is already live before it is used at the first time, so that we compute the intersection of Used(l) and Live(l) to avoid this.
|
|
Full Usage:
InferenceGraph2DotFile ostr colorMap nodesIG edgesIG
Parameters:
TextWriter
colorMap : Map<string, int>
nodesIG : Set<string>
edgesIG : Set<string * string>
|
Writes colored interference graph as dot file.
|
Compute the set of live variables for every line of a cmd program. We compute the may/must approximations of the live variables, i.e. the following least fixpoints:
|
|
|
|
Function MkMemRegMaps is given the global and local declarations of a MiniC thread as well as the temporary variables generated by translating the thread's statement to a cmd program. Moreover, the function expects the coloring of the interference graph as computed by function ChaitinBriggsColoring, and a preliminary memory mapping of the global and maybe other thread's variables which allocated memory up to address strtAdr-1. This function computes then a graph coloring and reduces it to the available six registers of Abacus (two are needed by the code generator) and then computes register and memory mappings of the local and temporary variables (the global ones need to be mapped independent of a thread), and the address ranges (strtAdr,endAdr) of the allocated memory for the non-register variables. |
|
Compute for each line of a cmd program a map which maps the variables to the set of program lines that defined their value before (if so). Note that a variable may have several definitions iff several paths can reach that line. A variable may also have no definition if it has not yet been defined before. |
|
Compute the set of used variables for every line of an cmd program. We compute the may/must approximations of the used variables, i.e. the following least fixpoints:
|
|
Full Usage:
WriteAbacusProgramsToFile filename (nxtAdr, memMap, cpThrds)
Parameters:
string
nxtAdr : int
memMap : Map<string, int>
cpThrds : CompiledThread array
|
WriteAbacusProgramsToFile writes all Abacus programs contained in the compiled threads to a file with the specified filename.
|
Full Usage:
WriteAbacusProgramsToStream ostr (nxtAdr, memMap, cpThrds)
Parameters:
TextWriter
nxtAdr : int
memMap : Map<string, int>
cpThrds : CompiledThread array
|
WriteAbacusProgramsToStream writes all Abacus programs contained in the compiled threads to a file with the specified filename.
|
Full Usage:
WriteCdfgProgramsToFile minicDir minicName (nxtAdr, memMap, cpThrds)
Parameters:
string
minicName : string
nxtAdr : 'a
memMap : 'b
cpThrds : CompiledThread array
|
WriteCdfgProgramsToFile writes for all threads their control flow graphs to corresponding dot files.
|
Full Usage:
WriteCfgProgramsToFile minicDir minicName (nxtAdr, memMap, cpThrds)
Parameters:
string
minicName : string
nxtAdr : 'a
memMap : 'b
cpThrds : CompiledThread array
|
WriteCfgProgramsToFile writes for all threads their control flow graphs to corresponding dot files.
|
Full Usage:
WriteCmdProgramsToFile filename glbDcl (nxtAdr, memMap, cpThrds)
Parameters:
string
glbDcl : (string * 'a) array
nxtAdr : 'b
memMap : 'c
cpThrds : CompiledThread array
|
WriteCmdProgramsToFile writes all Cmd programs contained in the compiled threads to a file with the specified filename.
|
|
Compute live intervals of the variables; note that a live interval is determined by the minimal and maximal command line where a variable is active. The function expects a mapping "activeVars" that maps cmd lines to the set of variables active at that line (i.e., both live and used). It returns a map that maps variable x to its liveness interval (minL,maxL).
|