In the following assignment you have to extend the MiniC Framework which translates an OIL-program (see slides) to a C-program. The grammar of OIL can be found here.
To get an object, the OIL-program is translated to a C-program. For running the C-program, we need a stub, i.e. a main-function, that invokes the OIL-functions. The generated C-program and the stub are compiled by a C-compiler. This means, that the MiniC Framework is a pure source-to-source translator.
The whole framework is written for the Linux operating system and can be simply installed on host b3.complang.tuwien.ac.at. However, it is also possible to develop the project under Windows. The Cygwin Project provides a complete Unix-environment for Windows.
The tarball of the framework can be found here. The tarball can be decompressed and unpacked in the current directory by the following command:
tar zxvf minic.tgz
After invoking tar, you will find following files in your minic directory:
| Files/Directories | Description |
|---|---|
| run | invokes make-files of the source and example directory |
| src/ | source-code directory of miniC |
| src/Makefile | makefile for building minic |
| src/parser.y | parser |
| src/scan.l | scanner | src/output.c | output program as C-program |
| src/minic.h | header-file for the framework |
| src/alloc.c | allocating and removing structures |
| src/symtab.c | routines for managing the symbol table |
| src/sbitmap.h | set library, header file |
| src/sbitmap.c | set library, implementation |
| examples/ | example directory (contains two examples written in OIL) |
| examples/Makefile | makefile for building the examples |
| examples/bubble.mc | bubble sort written in OIL |
| examples/bubble_main.c | main program that calls OIL-functions in bubble.mc |
| examples/fac.mc | factorial number written in OIL |
| examples/fac_main.c | main program that calls OIL-functions in fac.mc |
The MiniC Framework and the examples written in MiniC can be compiled and executed by the command: ./run. In directory src all the relevant source files of the MiniC Framework are stored. In directory example all the MiniC Examples (written in OIL) and the stubs are kept.
The whole framework is kept as simple as possible. Since the project has no commercial background, memory structures don't need be deallocated. A bonus is given for very simplistic solution to the following problems.
In the examples archive you find plenty of test programs written in OIL.
Write a module for the MiniC Framework that constructs a control flow graph. The data structures for the control-flow graph is given below. For every control flow graph node, a dynamic record is allocated. The dynamic record contains following fields:
struct cfg_node {
struct stmt *first,
*last; /* fist and last statement of sequence */
int num_preds; /* number of predecessors */
int *preds; /* predecessors */
int num_succs; /* number of successors */
int *succs; /* successors */
};
Extend the dynamic record definition for functions (struct func) as follows:
struct func {
...
int num_nodes; /* number of cfg nodes */
struct cfg_node **nodes; /* nodes of cfg */
...
};
Each node in the control-flow graph has a unique number between zero and a number which is less than the number of nodes in the graph (num_nodes). The number is used as an index for the array of pointers nodes in order to get hold of the node information. E.g., nodes[0]->num_succs gives the number of successor nodes of node 0.
A node in the control flow graph represents a sequence of statements. The first statements is given by the element first -- the last statement by last. Moreover, the data structure holds the successors and predecessors of a cfg node. This information is stored in num_preds, preds,num_succs, and succs. Field elements num_succs and num_preds give the number of successors and number of predecessors respectively. The node numbers of the predecessors and successors are stored in succs and preds.
In the control-flow graph the start node and end node are artificial nodes without basic blocks (The fields first and last are set to NULL). The start node has always the number zero and the end node has always the number 1. Because there can be many exit nodes due to return-statements we introduce an artificial exit node and insert an control flow edge between the real exit nodes and the artificial exit node. NB: The dynamic record of the start node is accessed by nodes[0] and the record of the end node by nodes[1].
To build the control-flow graph it is useful to decompose the problem. Following steps are proposed:
The function process_unit(struct func *unit) in parser.y is to be extended for building the control flow graph. At this place in the code you have full access to the data structures of functions. In main() an option for building the control flow graph should be added, e.g. -c.
Write a function which dumps the control-flow graph in a file. The dump should contain number of nodes and for each node:
Add an option that enables the dump facility, e.g. ./minic -ddump-file input-file.
Visualize the control flow graph by using the program dot. (NB: If you want to work at home, you will need to install graphviz on your linux system. This is a quite easy task: (1) download the tarball , (2) in the directory of graphviz type ./configure, (3) type make, and (4) make install). The program reads in a graph file and produces a graphical representation of the graph. Extend the framework such that graph files with the filenames filename.fn.dot are generated for all functions fn in a MiniC-program. Then, a graph can be depicted by following commands:
dot -Tps -ofilename.eps filename.dot ghostview filename.eps
In the following a simple graph file and its output is shown.
| Input | Output |
|---|---|
|
digraph cfg { node [shape = doublecircle]; 0 1 ; node [shape = circle]; 0 -> 2; 2 -> 3; 3 -> 2; 2 -> 1; } |
|
More documentation can be found here.
Eliminate all statements of a function which cannot be reached from the start node. Employ the control flow graph as an underlying data structure for eliminating unreachable statements. Note that function delete_stmt(f,s) deletes statement s in function f. A range of statements can be deleted by delete_range(f,first,last). Use the iterative algorithm described in the slides.
For set-operations a set-library is provided in the file sbitmap.h and sbitmap.c. The library provides two data types. The first data type (sbitmap) is a simple set of fixed length. The second data type (sbitmap *) is an array of sets. Note that every element of a set has an index. The function TEST_BIT(set,i) checks whether the ith element is in the set. Function RESET_BIT(set,i) and SET_BIT(set,i) reset and set the ith element, respectively.
Please find below a fragment of a function that uses library routines of the set library:
....
sbitmap a,b,c;
sbitmap *v;
/* allocate three sets with 3 elements */
a = sbitmap_alloc(3);
b = sbitmap_alloc(3);
c = sbitmap_alloc(3);
/* allocate a vector of sets. The vector
includes 10 sets. All sets have three elements. */
v = sbitmap_vector_alloc(10,3);
/* a = b - c */
sbitmap_difference(a,b,c);
/* a = - b */
sbitmap_not(a,b);
/* a = b /\ c */
sbitmap_a_and_b(a,b,c);
/* a = b \/ c */
sbitmap_a_or_b(a,b,c);
/* print set */
dump_sbitmap(stdout,a);
...
/* v[0] = - v[1] */
sbitmap_not(v[0],v[1]);
Please lookup in the header file. There is a variety of functions for utilizing most of the set-operations for both data types (array of sets and sets).
Back.