gyre.graph

The ADT which most closely resembles Gyre's structure is the directed multigraph: a set of nodes and directed edges, where different edges can have the same nodes at their endpoints. Although theoretically quadratic in the worst case, we expect the number of edges to be rougly proportional to the number of nodes in the graph; and we estimate that the number of nodes will grow as a polynomial function of source program size (varying by language being compiled, of course). Therefore, we want to keep nodes as slim as possible (and edges even more so), while still being able to transform subgraphs in an efficient manner.

As seen in libFIRM, some optimizations can become inherent to the IR if we're able to identify common substructures in the graph. In order to make this as efficient as possible, we'll use hash tables and specially crafted hash functions for each node, leveraging SSA form to approximate semantic equivalence from structural equality. This means that hashing a node or comparing two nodes won't be trivial operations, so we better (a) cache hash values; and (b) be careful during structural comparisons, since Gyre graphs can be cyclic. More details here.

Click's sea of nodes uses objects and pointers to represent a graph; lets copy that. In order to maintain referential integrity (i.e. keeping our pointers valid), we can either (a) allocate all nodes on the global heap and keep that memory pinned for as long as there are references to it (easily done with D's GC), or (b) allocate in bulk and manually manage our memory, fixing references whenever objects are moved (more performant but harder to get right). Since we'll want to call this library from other languages, we better err on the side of the betterC-compatible option, so (b) it is. We'll always manage memory like this in the context of a Graph.