ForeC Compilation Process

The ForeC compiler is focussed on generating C-code that is amenable to static timing analysis. The static thread schedule of a ForeC program is based on a total ordering of its threads. Each type of scheduling routine follows a general template, which is instantiated core and thread information. The optimisation of C-code generated by the ForeC compiler is left to the C-compiler.

Front-end

1. Lexical analysis and tokenisation using Flex
2. Construction of abstract syntax tree (AST) of ForeC source program and header file using Bison
3. Semantic analysis: mostly recursive depth-first search (DFS) of AST
   1. Symbol table of variables, inputs, outputs, shared, typedefs, enums, labels, functions, threads
   2. Computation of each thread's variable accesses (read/write). At each par statement, take the union of the threads' variable accesses. Propagate variable accesses up the thread hierarchy until the main thread is reached. If a variable is associated with multiple threads, then it is a shared variable
   3. Propagate knowledge of shared variables back down to all the (nested) par statements to determine the necessary handling of shared variable copying and combining. A shared variable does not need a combine function if it never has parallel writers (sequential writers are inherently mutually exclusive)
   4. Check that all defined threads have a core allocation, and that all allocated threads have been defined
   5. Check for instantaneous loops. Conservatively evaluate the reaching of pause statements in if-else, switch, and abort statements, or that loops have a defined upper-bound
4. Construct abstract control-flow graph from the AST, focussing on the forking-joining of threads, conditionals, pauses, and abort scopes. Threads and functions are linked to their "call sites"

Middle-end

1. Check that threads do not recursively fork each other: DFS of CFG and identifying revisited threads
2. Derive a CFG for each core, based on their allocated threads: DFS of CFG. Create stubs for parent threads. Helps in defining the master and slave cores of each par statement and the inter-core synchronisation points needed to manage the distributed forking and joining of threads

Back-end

1. Generate a linked list for each core to manage the run-time scheduling of thread execution and inter-core synchronisation: DFS of CFG
   • Cooperative scheduling is assumed with left-to-right assignment of thread execution priority
   • The master core's initial linked list contains the main thread, and scheduling routines to handle par-specific thread forking and global tick synchronisation
   • Each slave core's initial linked list contains scheduling routines that handle par-specific thread forking and global tick synchronisation
   • For each par statement, generate a linked list for each participating core. Include scheduling routines that check abort conditions and handle par termination. Handle nested par statements by inserting scheduling routines, that handle par-specific thread forking into the linked lists, after their parent thread
   • When a thread executes a par statement, the parent thread (master core) and corresponding par routines (slave cores) are replaced by the par's linked lists. When threads terminate (join), they remove themselves from their core's linked list
   • When a par statement terminates, the remnants of the par's linked lists are removed and the parent thread and par routines are reinstated
2. Generate core and par-specific scheduling routines for global tick synchronisation, par execution, par termination, combining of shared variables, and checking of abort conditions. Works on unique par IDs and busy waiting on status variables, updated atomically. C and ASM comments are used to demarcate the scheduling routines for analysis
3. Generate C-code for each thread body by walking their AST. Insert C-code for copying shared variables, but only for threads that possibly write to the shared variables. From the original thread body, regenerate the existing C statements and expand the ForeC statements into C-code. The par and pause statements and their corresponding scheduling routines will jump between each other
4. Generate C-code for each function by walking their AST