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).

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.

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.

Compute all data dependencies on scalar variables of a cmd program

Writes colored interference 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.

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:

• MayLive(l) = Read(l) ∪ ((U_{l' in Succ(l)} MayLive(l')) \ Write(l))
• MstLive(l) = Read(l) ∪ ((∩_{l' in Succ(l)} MstLive(l')) \ Write(l))

Note: MayLive(l) is the set of variables whose current value is read now or later before it is overwritten on at least one computation path, and MustLive(l) is the same on all computation paths. The result it a mapping of program lines to (MustLiveVars,MayLiveVars) where MustLiveVars and MayLiveVars are the variables that must/may be live at that line. The additional input determines whether intermediate states of the computation are written to an optional output stream.

Function MkMemMaps is given the global declarations of a MiniC program and generates a memory mapping of the shared variables declared there. It returns the memory mapping plus the next free memory address.

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:

• MayUsed(l) = Read(l) ∪ (U_{l' in pred(l)} MayUsed(l') ∪ Write(l'))
• MstUsed(l) = Read(l) ∪ (∩_{l' in pred(l)} MstUsed(l') ∪ Write(l'))

Note: If we assume an infinite amount of registers, then a variable is used at l, if that variable is in its register at that line (since it has already been used before). This is due to the fact that we can assume previous load instructions before current reads of that variable. The result it a mapping of program lines to (MustUsedVars,MayUsedVars) where MustUsedVars and MayUsedVars are the variables that must/may have been already used at that line. The additional input determines whether intermediate states of the computation are written to an optional output stream.

WriteAbacusProgramsToFile writes all Abacus programs contained in the compiled threads to a file with the specified filename.

WriteAbacusProgramsToStream writes all Abacus programs contained in the compiled threads to a file with the specified filename.

WriteCdfgProgramsToFile writes for all threads their control flow graphs to corresponding dot files.

WriteCfgProgramsToFile writes for all threads their control flow graphs to corresponding dot files.

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).