Skip to content
GitLab

adding a traversal · Changes

Page history
added tutorials for adding a traversal tutorial and a tutorial about project... authored by quinten-cabo's avatar quinten-cabo 
added tutorials for adding a traversal tutorial and a tutorial about project structure and ast.xml. Also added tutorials from other people I found in the source code and a concepts directory with phm and ref counting also added a faq file
Show whitespace changes
Inline Side-by-side
tutorials/adding-a-traversal.md 0 → 100644
View page @ 66bc47a8
In this tutorial you will hopefully learn how to add a traversal to the sac compiler.
# What is a traversal?
Compiling code is complicated.
The complexity has even been [likend to a dragon](https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools).
To deal with this complexity the sac compiler is broken up into compiler phases each of which tackle a certain part of the complexity.
For instance currently the first phase is`scp` or `Loading SAC program`.
The second phase is currently `pre` or `Preprocessing SAC program` and so it continues on all the way to the code generation phase.
Each of these phases is further divided into subphases.
For instance currently the first subphase of the `pre` phase is `ffc` which is `Assigning type pattern constraints to pre- and post-conditions`.
Each phase is a composition of traversals/subphases.
These subphases are implemented as AST traversals.
*So what is a traversal?*
The idea of a traversal is that you traverse the abstract syntax tree and visit the nodes you are interested in.
You traverse the tree and make changes to the nodes.
You only need to implement functions for the nodes of the AST which you care about in your traversal.
Implemented default behaviour takes care of the other nodes.
This follows the [visitor pattern](https://en.wikipedia.org/wiki/Visitor_pattern).
## Inspecting & debugging existing traversals
There are already a lot of AST traversals in the sac compiler.
If you want you can actually stop the compiler after each traversal using the `-b` flag.
This will pretty print the AST as SAC code at that point in the compiling process.
This is very useful when you want to learn what a traversal is doing or when you are implementing your own traversal to see what's going on.
You can see all the traversals you can break using the `sac2c -help` command and then at BREAK OPTION SPECIFIERS.
I recommend copying this section of the help text and saving it to a `.txt` file.
You will often look at the available compiler phases and traversals.
You can break at a specific traversal or subphase using `-b phaseid:travid`
These compiler phases are also numbered.
You can also break at a compiler phase using the number.
# Step 0: Consider at which point your traversal should be added
Look at the already existing traversals.
Before implementing a new traversal you should decide where you want to put your new traversal.
Here are some tips on how to decide where to insert your traversal:
- First decide in which compiler phase you want to add your traversal and then decide after which traversal. This way you break up your decision.
- Maybe it is very clear that your traversal can only happen after another traversal. In that case try to add your traversal right after this earlier traversal if it makes sense.
- Use common sense
- The later you add your traversal the more complicated the sac code your traversal has to process will be. Keep that in mind.
# Step 1: Add your traversal to ast.xml
Open the `src/sac2clib/xml/ast.xml` file.
> If you are not familiar with this important file then it is a good idea to read [the tutorial about ast.xml](./ast.xml.md) first. Especially the [traversals](./ast.xml.md#Traversals) section.
Inside the `<traversals>` tag add a new `<traversal></traversal>` tag.
Just copy another traversal that is already there and adjust the attributes for your traversal.
Here is an example:
```xml
<traversal id="EX" name="Example Traversal" default="sons" include="example_traversal.h">
<travuser>
<node name="Module" />
<node name="Fundef" />
</travuser>
</traversal>
```
Make sure that the id attribute of the `<traversal>` tag is all UPPERCASE.
Put the nodes you want to visit inside the `<travuser>` tag.
> It is nice if you order the nodes by how far they are up in the tree.
> A fundef node is a son of module so it should be below module and so on.
> By applying this ordering everywhere the code becomes much more readable.
# Step 2: Create the header and implementation file
Now you should make a header file with the same name that you specified in the `include` attribute of the `<traversal>` tag.
*But where should I put this header file?*
This depends on which compiler phase you decided to add your traversal to in step 0.
Each compiler phase has a corresponding directory in `src/sac2clib`.
So for example if you choose the preprocessing phase (phase 2) then you should add your header file to `src/sac2clib/precompile` directory.
In this example I would create `src/sac2clib/precompile/example_traversal.h`.
Now also create a `.c` file of the same name in the same directory.
In this example it would be `src/sac2clib/precompile/example_traversal.c`
# Step 3: Add the c implementation file to the build system
You need to tell `cmake` about your new `.c` file otherwise it won't be compiled.
You can add the in `src/libsac2c/CMakeLists.txt` file.
You have to add it after `SET (SAC2C_SRC` there will be a lot of examples here that you can just copy.
You have to add something like this:
```cmake
${CMAKE_CURRENT_SOURCE_DIR}/precompile/example_traversal.c
```
But replace `precompile` with the correct directory.
Also, please place your new line with the other c files in your directory (`precompile` directory in the example).
For intelligence to pick up on the files you might need to rerun `cmake`.
```shell
cmake -DCMAKE_BUILD_TYPE=DEBUG -B cmake-build-debug
```
Replace `cmake-build-debug` with the directory where you keep the build version of the compiler. Or don't.
# Step 4 Create the Header file
Copy this template traversal header code into the file you created in step 2.
```c
/** <!-**********************************************************-->
* author: <Your name>
* created-at: dd-mm-yyyy
* description:
* What does this traversal do?
*
* Prefix: TEMP
*
*********************************************************************/
#ifndef _SAC_TRAVTEMPLATE_H_
#define _SAC_TRAVTEMPLATE_H_
#include "types.h"
extern node *TEMPdoTemplateTraversal (node *syntax_tree);
extern node *TEMPmodule (node *arg_node, info *arg_info);
extern node *TEMPfundef (node *arg_node, info *arg_info);
#endif /* _SAC_TRAVTEMPLATE_H_ */
```
> This template was taken from the `doc/trav_template` directory.
Now do a couple search and replace to make the template your own.
1. Replace `TEMPLATE` with your traversal id, but the acronym spelled out without spaces in upper case
2. Replace Template with your traversal id, but the acronym spelled out but in PascalCase
3. Replace `TEMP` with your traversal id.
In vim, you can this like so :
1. `:%s/TEMPLATE/EXAMPLE/g`
2. `:%s/Template/Example/g`
3. `:%s/TEMP/EX/g`
Obviously replace `EXAMPLE`, `Example` and `EX` with your traversal id.
Now add the required functions the nodes you specified in step 1.
The next section should give you the knowledge to do this succesfully.
## OK so what is actually in this header file?
The `#include types.h` just gives you the types you need to define this header.
Namely, the `node` type and `info` type.
In this header file the compiler does actually not yet know the concrete type of `node` and `info`, this will be specified later.
The first function you specify is the top-level function of your traversal.
When people want to use your traversal this is the function they use.
In the template the function is called `TEMPdoTemplateTraversal`.
This function should follow the following format:
- Marked as `extern`
- Returns `node *`
- Named `<traversal_id>do<TraversalName>`. The `<TraversalName>` should be the header filename in PascalCase.
- Takes a single argument of type `node *` of name `syntax_tree`
Then you have to define a traversal function for each `<node>` tag you added to the `<tavuser>` tag in step 1.
These functions have a very specific format which you must follow.
Each of these traverse functions should follow this format:
- Marked as `extern`
- Returns a `node *`
- Named `<traversal_id><node_name>`
- Takes exactly two arguments
- The first argument is of type `node *` and called `arg_node`
- The second argument is of type `info *` and called `arg_info`
> Again it is a good idea if you order the traversal functions by how the node is up in the tree.
> A fundef node is a son of the module node so it should be below module node and so on.
> By applying this ordering everywhere the code becomes much more readable.
# Step 5: Create the implementation c file
Now that you have your header file we add content to the `.c` file.
In the case of this example this would be `src/sac2clib/precompile/example_traversal.c`.
This file will hold the implementations for the functions defined in `src/sac2clib/precompile/example_traversal.h`
Here is a very basic example for the traversal implementation:
```c
#include "example_traversal.h"
#define DBUG_PREFIX "EX"
#include "debug.h"
#include "traverse.h"
struct INFO {
node *fundef; // some random info
};
node *EXdoExampleTraversal (node *syntax_tree) {
return syntax_tree;
}
node *EXmodule (node *arg_node, info *arg_info) {
return arg_node;
}
node *EXfundef (node *arg_node, info *arg_info) {
return arg_node;
}
```
You should try this one first to check if you did everything correctly and see if the compiler still compiles.
Because this is the minimum amount of code just to test if you did everything correctly I already used example instead of template so that you can just copy this if you are following the `EX` example.
To make this template your own you need to fix to include the correct header instead of `example_traversal.h` and replace the ``EX` traversal id with your traversal id: `:%s/EX/FOO`.
Make sure the functions match up with the functions match up with the functions in the header file.
Once this works you can copy the actual template below:
There is also a template for your traversal `.c` file, here it is:
```c
/********************************************************
*
* @defgroup TEMP My cool traversal
* @ingroup prec Precompile // todo Update to match phase
*
* prefix: TEMP
*
* @brief short description
*
* description:
* Longer traversal description goes here with examples.
*
* @{
**********************************************************/
#include "template_traversal.h" // update to your .h file
#define DBUG_PREFIX "TEMP"
#include "debug.h"
#include "traverse.h"
#include "tree_basic.h"
#include "memory.h"
/* @name INFO structure */
struct INFO {
node *foo;
};
/* INFO macros */
#define INFO_FOO(n) ((n)->foo)
/* INFO functions */
static info *
MakeInfo ()
{
info *result;
DBUG_ENTER ();
result = MEMmalloc (sizeof (info));
INFO_TEMP (result) = NULL;
DBUG_RETURN (result);
}
static info *
FreeInfo (info *info)
{
DBUG_ENTER ();
info = MEMfree (info);
DBUG_RETURN (info);
}
/********************************************************
* Traversal start function
*********************************************************/
/**
*
* @brief short description
*
* description:
* Longer traversal description goes here with examples.
* The is the function that will be called from the outside
*
* @return the modified syntaxtree
*
*/
node *
TEMPdoTemplateTraversal (node *syntax_tree)
{
info *info;
DBUG_ENTER ();
info = MakeInfo ();
DBUG_PRINT ("TEMP", ("Starting template traversal."));
TRAVpush (TR_temp);
syntax_tree = TRAVdo (syntax_tree, info);
TRAVpop ();
DBUG_PRINT ("TEMP", ("Template traversal complete."));
info = FreeInfo (info);
DBUG_RETURN (syntax_tree);
}
/********************************************************
* Traversal functions
*********************************************************/
/**
* @brief Traverses only the fundef chain and leaves out special thread
**/
node *
TEMPmodule (node *arg_node, info *arg_info)
{
DBUG_ENTER ();
FUNDEF_NEXT (arg_node) = TRAVopt(FUNDEF_NEXT (arg_node), arg_info);
DBUG_RETURN (arg_node);
}
/**
* @brief Performs a traversal of the fundef and prints the name of each function without entering the body
**/
node *
TEMPfundef (node *arg_node, info *arg_info)
{
DBUG_ENTER ();
FUNDEF_NEXT (arg_node) = TRAVopt(FUNDEF_NEXT (arg_node), arg_info);
DBUG_RETURN (arg_node);
}
/**********************************************************
* Helper functions (static)
***********************************************************/
static node *
DummyStaticHelper (node *arg_node)
{
DBUG_ENTER ();
DBUG_RETURN (arg_node);
}
/* @} */
```
Copy this template into your `.c` file.
To make the template your own perform the following search and replace operations:
1. `:%s/template_traversal.h/example_traversal.h/g`
2. `:%s/TemplateTraversal/ExampleTraversal/g`
3. `:%s/TEMP/EX/g`
4. `:%s/tr_temp/tr_ex/g`
Do not forget to update `@ingroup` to match the correct compiler phase and add a description of your phase.
## Understanding what is going on in the c file
In a traversal you visit each part of the tree.
You only have to implement functions to deal with the nodes you are actually interested in.
Default behaviour deals with the rest.
If you need to traverse a node for which you did not define a function yourself you can use the `TRAVdo` function from `tree.h`.
Each traversal starts with a function with the word `do` in it.
This is the top level of your traversal, meaning this is the function that should be called to start the traversal.
As you have seen the `do` function takes a single argument of type `node*` called `syntax_tree`.
This syntax tree argument refers to the `<syntaxtree>` tag in `ast.xml`.
Each other traversal function takes the node which it is traversing and an info struct.
Info struct is like red riding hood basket for information.
The idea of the info struct is that you can carry information from one node to the next.
**Example** Imagine you want to count the number of **if-statements** inside a function definition. To do this, you can use an **info struct** to keep track of the count as you traverse the function’s body.
1. Allocate the info struct with your counter set to 0 in the do function.
2. When you visit a function definition node, set the counter on the past in **info struct** to `0`.
3. As you traverse the function body, every time you encounter an **if-statement**, increase the counter in the info struct.
4. Once the body traversal is complete, the counter in the info struct tells you how many **if-statements** were inside that function body.
The info struct serves the same purpose as a state monad.
It is not a state monad, but the info struct serves the same purpose.
It is the job of the `do` function to allocate and free the `info` struct.
You should define accessor macros for all the fields of your info struct.
You can actually alter the AST by returning a modified node.
Think if you need to make a copy of the node before returning it.
Special recursive copy functions are generated from `ast.xml` which can copy nodes correctly.
# Step 6: Register your phase in the compiler
Once your traversal compiles, and you are happy, you can actually add it the compiler.
This done in the `sac2clib/global/phase_sac2c.mac` file.
This file specifies the phases and subphases using macros.
When you open this file you can see that it spells out the phases and subphases of the compiler.
You need to add another call to the subphase macro in the correct position that you decided in step 0.
This macro takes a few arguments.
```c
SUBPHASE (ex, "An example traversal", EXdoExampleTraversal, ALWAYS, pre)
```
1. The first argument is the id of your traversal in lower case
2. The second argument is a brief description, I would put the same as you put in the name attribute of the `<traversal>` tag you put in the ast.xml.
3. The `do` function name to start the traversal
4. A boolean flag for when to execute the phase. ALWAYS is a macro for true to always start the traversal. Most subphases use ALWAYS, but you can also use flags on a variable called global. For example: `global.runtime` or `global.elf`. The `global.insertconformitychecks` varialbe is true when the compiler ran with `-check c`. I think you can find the globals in `src/libsac2c/global/globals.mac`.
5. The name of the phase in lower case. You can find this in the same file. The phases are defined with the `PHASE` macro.
Just copy one that is already there and make it your own.
\ No newline at end of file