Previous Up Next

4  Graphs

Graph is tested and ok, the use of table is unclear.

The module implements a general graph data type, with later two specializations: the control flow graph and the interference graph which is the result of the liveness analysis.

The graph is implemented imperatively and with side-effects, i.e., as a class. Getting a new graph with Graph.new_graph gives an (implicity) reference to a graph-structure, since it is implemented as an array! Note that it is possible to add an edge twice and consequently to remove it twice, so more correctly, the set of edges E is not a subset of N × N, were N is the set of nodes, but rather a multiset. Note also that removing nodes is not possible, only addition of new nodes. gr

The interface is described at page [App98b, p. 222].

To do:
The graph data type contains temp as a type. Actually, it seems not used. Why is that for?
To do:
Think of a more efficient and cleaner way to implement this. It seems like a curious mixture of oo-style and functional style. Perhaps it’s better to make the whole module a class? Disentangle the implementation after testing it. Remove/internalize the inc() function
To do:
Array bounds errrors are still possible, for instance for the nodes.

Must one add the node before one has to add an edge? What happens if one tries to add a node twice?

[Invariant of the array implementation] Is it true that the invariant of the array is that right to a bogus element, there are no real elements? It seems that the access functions depend on that assumption? Is that true?

Arrays are reference values in Ocaml.

[Dynamic arrays] The SML-implementation of the graphs uses dynamic array. This data structure is not available in the Ocaml-library.

In Ocaml, we can append two arrays, but this gives a new copy of the appended array, the identity or references is broken. This makes the data structure not usable for the graph implementation which relies heavily on sharing among the array of nodes. Array.blit can desctructively copy elements of one arry into the fields of an existing other array, but it cannot extend the size of the array.

For the time being, I use hashtables as replacement. One reason is that, like SML’s dynamic arrays, the hashtables of Ocaml are an imperative structure with sharing and side effects, which means, their in the implementation of the graphs is similar. Later we can look for a different way to implement graphs if it is clear how they are used. It seems that also the graphs rely on sharing. [Implementation of Appel] How does the graph-implementation provided by Appel work?

The provided implementation uses dynamic arrays. Those arrays, unlike the ones from the Ocaml-library, can be dynamically extended in-place (i.e., preserving potentially aliases to the array).

ocaml does not have dynamic arrays, but arrays from the Array-module are appendable, which is not the same, since this copies the appended arrays into a new one, so the reference to the array is not preserved, something that we want for the graph implementation.

Graphs are then represented by an integer array where for each node the list of predecessors and successors is given. Conceptually, the dynamic array is an “infinite” map where only a finite number of elements are not the default value, which in the case of graphs is a bogus node.

Everything works with side-effects. This means, getting a new node has the side effect of extending the graph by the new node (and giving back its identity).

How does the implementation cope with situations that an edge is added twice or that a non-existing edge is removed. Is this ignored?

I introduced an extra module type GRAPH, since mentioning it is necessary at different places, for instance for flowgraphs needs to import the graph structure. Therefore, just using the graph.mli and files does not work.

Previous Up Next