|
|
|
An incomplete short summary of all the compiler phases & traversals.
|
|
|
|
|
|
|
|
If you are reading a traversal you can come here and create or improve a summary of it to improve your and later others understanding of the traversal and the compiler as a whole.
|
|
|
|
|
|
|
|
For the full picture of each traversal see the corresponding file in the `src` directory.
|
|
|
|
|
|
|
|
# Loading SAC program
|
|
|
|
|
|
|
|
In this phase the compiler loads the given SAC program.
|
|
|
|
|
|
|
|
## Locating source code (loc)
|
|
|
|
|
|
|
|
In this phase the compiler checks if the given file actually exists.
|
|
|
|
|
|
|
|
## Locating source code (cpp)
|
|
|
|
|
|
|
|
In this phase the compiler runs the c preprocessor on the given source code.
|
|
|
|
This is done by calling the c compiler using the `-E` flag.
|
|
|
|
|
|
|
|
## Parsing input file (prs)
|
|
|
|
|
|
|
|
In this phase the file is actually parsed.
|
|
|
|
After this phase you get a syntax tree of type `node`.
|
|
|
|
|
|
|
|
# Preprocessing Type patterns
|
|
|
|
|
|
|
|
In this phase the type patterns are preprocessed.
|
|
|
|
The type patterns are turned into sac code which means that the rest of the compiler does not really have to know about them.
|
|
|
|
|
|
|
|
## Flag all function definition blocks as safe if module is safe (tsm)
|
|
|
|
|
|
|
|
Simple phase that checks if the module is safe and if so, flags all function body block nodes as safe.
|
|
|
|
This will later in `rss` cause all `spap` nodes to be treated flagged as safe and be replaced with their `_impl` version.
|
|
|
|
|
|
|
|
## Moving type pattern constraints to pre- or post-conditions (ffc)
|
|
|
|
|
|
|
|
In this phase the ast is traversed 3 times to filter the type pattern constraints into either pre- or post-conditions.
|
|
|
|
|
|
|
|
This is done by first checking which names come from the arguments of the function.
|
|
|
|
If all names in the constraint are from the argumentsa of the fundef, the constraint is put as a pre-condition.
|
|
|
|
If the constraint uses a name that is from the return types, the constraint is put as post-condition.
|
|
|
|
|
|
|
|
The pre conditions and post conditions are actually stored in the `fundef` node using the
|
|
|
|
`FUNDEF_PRECONDS` and `FUNDEF_POSTCONDS` macros.
|
|
|
|
|
|
|
|
## Analysing type patterns and converting to built-in types (atp)
|
|
|
|
|
|
|
|
This traversal converts types that include type patterns like `int[d:shp]` to simpler pre-existing types like `int[+]`.
|
|
|
|
|
|
|
|
For example, the following function signature:
|
|
|
|
|
|
|
|
`int[3,.] foo (int[7,5] a, int[n,m] b, int[.,d:shp] c)`
|
|
|
|
|
|
|
|
is converted to:
|
|
|
|
|
|
|
|
`int[.,.] foo (int[7,5] a, int[.,.] b, int[+] c)`
|
|
|
|
|
|
|
|
We convert type patterns to one of four following cases:
|
|
|
|
|
|
|
|
- Array of unknown dimensionality: int[*] (AUD)
|
|
|
|
- Array of non-zero dimensionality: int[+] (AUDGZ)
|
|
|
|
- Array of known dimensionality: int[.,.,.] (AKD)
|
|
|
|
- Array of known shape: int[5,3,7] (AKS)
|
|
|
|
|
|
|
|
This is done to avoid having to modify the type checker to work well with type patterns.
|
|
|
|
Importantly the type patterns are not thrown away they are still stored on the TYPEPATTERN son.
|
|
|
|
|
|
|
|
Warnings are given when traversing type patterns on `structelem`, `objectdef`, `casts` and `array` because no checks for these are implemented.
|
|
|
|
For instance casting something to a type with a type pattern like `(int[d:shp]) a` will just turn into a cast to `(int[*])`
|
|
|
|
and no additional checks are generated later.
|
|
|
|
|
|
|
|
That means this code:
|
|
|
|
|
|
|
|
```
|
|
|
|
int foo (int[*] x) {
|
|
|
|
a = (int [d:shp])x;
|
|
|
|
return d;
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
Will be changed to
|
|
|
|
|
|
|
|
```
|
|
|
|
int foo (int[*] x) {
|
|
|
|
a = (int [*])x;
|
|
|
|
return d;
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
And later the programmer will get the `Variable 'd' used without previous definition` error.
|
|
|
|
|
|
|
|
The most important part of this traversal is the `AnalyseTP` function where the type is actually generated.
|
|
|
|
|
|
|
|
The number of fixed dimensions and the variable dimension identifiers are stored in the `N_typepattern`.
|
|
|
|
This is required in the type_pattern_resolve traversal.
|
|
|
|
|
|
|
|
## Turning type patterns of functions into code (rtpf)
|
|
|
|
|
|
|
|
This traversal actually turns the pre- and post-conditions of the fundef into code.
|
|
|
|
The implementation of this traversal lives in the same c file as the next traversal `rtpe`.
|
|
|
|
|
|
|
|
For each function definition this traversal first traverses the arguments and the return type a function definition to collect checks and variable assignments.
|
|
|
|
|
|
|
|
- **Checks** are predicates that need to hold for the function to be correct.
|
|
|
|
The order in which these predicates are checked during runtime is important because some predicates might depend on the result of previous predicates.
|
|
|
|
The traversal handles the order correctly by resolving the collected checks to a correct order with the `Resolve` function.
|
|
|
|
- **Assignments** are variable definitions which are created in the type pattern.
|
|
|
|
These variable definitions from the type patterns can be used by the programmer in the body.
|
|
|
|
Thus, the compiler has to actually generate the assignments for the type pattern variable definitions and insert these assignments at the start of the function body.
|
|
|
|
|
|
|
|
Once the checks and assignments are collected and resolved the compiler generates new pre- and post-conditions functions to actually check the checks.
|
|
|
|
|
|
|
|
First a function is generated that checks the pre-conditions of the function `_<fname>_pre`.
|
|
|
|
This function will execute all the pre-condition checks collected from the type patterns.
|
|
|
|
|
|
|
|
Then a function is generated that checks the post-conditions of the function `_<fname>_post`.
|
|
|
|
|
|
|
|
Whether something is a pre- or post-condition was determined in the previous `ffc` traversal.
|
|
|
|
|
|
|
|
If one of the predicates does not hold during runtime an error message is raised.
|
|
|
|
The code to raise these error messages if the predicate does not hold is known as a guard.
|
|
|
|
|
|
|
|
Then the original function is renamed to `_<fname>_impl`.
|
|
|
|
The compiler then inserts the resolved assignments (collected from the variable definitions in the type patterns of the arguments and return type) at the start of the `impl` function body.
|
|
|
|
|
|
|
|
Then a new inline function is generated with the name `<fname>`.
|
|
|
|
This function brings everything together.
|
|
|
|
In this new `<fname>` function the `_impl` function is decorated/wrapped with calls to the pre- and post-condition functions.
|
|
|
|
The `<fname>` function first calls the pre-condition check along with a guards to check the resulting boolean.
|
|
|
|
Then the original function (renamed to `_<fname>_impl`) is called.
|
|
|
|
Then then the post-condition check function is called with the return value of the `impl` function.
|
|
|
|
Finally result of the `post` function is checked in a guard.
|
|
|
|
|
|
|
|
Here is an example from `type_pattern_resolve.c`:
|
|
|
|
|
|
|
|
```c
|
|
|
|
int[d:shp] sel (int[n] idx, int[n:outer,d:shp] arr) {
|
|
|
|
return { iv -> arr[idx ++ iv] | iv < shp };
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
Goes to
|
|
|
|
```c
|
|
|
|
inline int[+] sel (int[*] idx, int[*] arr) {
|
|
|
|
pred = sel_pre (idx, arr);
|
|
|
|
idx, arr = guard (idx, arr, pred);
|
|
|
|
res = sel_impl (idx, arr);
|
|
|
|
res = guard (res, pred);
|
|
|
|
pred' = sel_post (idx, arr, res);
|
|
|
|
res = guard (res, pred');
|
|
|
|
return res;
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
It is important that the new function makes sure that the result of all functions `_pre` `_impl` and `_post` are used to compute the result of the function.
|
|
|
|
Otherwise, they would be removed by the compiler.
|
|
|
|
|
|
|
|
At the end of this phase the pre cond preconditions nodes are removed from the fundef.
|
|
|
|
|
|
|
|
## Turning type patterns of externals into code
|
|
|
|
|
|
|
|
This traversal is similar to the previous traversal but now for external functions.
|
|
|
|
The major difference with external functions to normal functions is that external functions do not have a body.
|
|
|
|
This currently means that they will never be able to use the variables defined in a type pattern.
|
|
|
|
|
|
|
|
As such only the checks are generated for external functions.
|
|
|
|
No variable assignments are prepended to the body of the external function because the compiler doesn't have it.
|
|
|
|
|
|
|
|
The rest is similar, the external function is renamed to `<fname>_impl` and if needed the `_pre` and `_post` functions are generated.
|
|
|
|
Then a wrapper function is generated that calls the `_pre` `_impl` and `_post` functions.
|
|
|
|
|
|
|
|
Important is resolving keeping the linkname because the compiler renamed the function by the programmer from `<fname>` to `<fname>_impl` but the linker still needs to find the original function.
|
|
|
|
For this reason the `impl` function is given the `linkname` attribute to the orignal name if it didn't have it.
|
|
|
|
If the original function had a `linkname` attribute the `impl` function is given the same `linkname` attribute.
|
|
|
|
|
|
|
|
```c
|
|
|
|
external int[+] foo_impl (int[*] a, int[*] b); #pragma linkname "foo"
|
|
|
|
```
|
|
|
|
|
|
|
|
## Rename safe SPap to skip checks generated by type patterns (RSS)
|
|
|
|
|
|
|
|
The programmer can indicate that they know that the pre and post condtions of a function application can be skipped.
|
|
|
|
The programmer makes this indication by annotating the function call as safe with `#pragma safe`.
|
|
|
|
|
|
|
|
In practice the pre- and post-conditions are skipped by replacing safe function calls with a call to the `_impl` version of the function.
|
|
|
|
In this phase this renaming is done.
|
|
|
|
To make sure the renaming is consistent with the previous 2 phases the same rename function is used.
|
|
|
|
|
|
|
|
# Preprocessing SAC program
|
|
|
|
|
|
|
|
## Hiding struct definition behind typedefs and accessors (hs)
|
|
|
|
|
|
|
|
|
Quinten Cabo