Constrained Tagged Graph

Constrained Tagged Graph

The Constrained Tagged Graph (CTG) stores information in a way that corresponds to the indications stored in the instruction library. Every vertex is put into correspondence with one macro in the constraints. The CTG uses tags to store information whose type is defined in the constraints.

Every CTG is divided into a number of subgraphs, not necessarily connected with the rest of the structure, each of which corresponds to a subsection.

When the CTG has to represent an assembly program from every vertex in a subgraph, except one, there is a privileged edge that goes to a next vertex. In this way the subgraph forms a linear structure, exactly corresponding to the sequential program structure. The edge going to the next vertex is identified by its name tag. This makes it easy to distinguish edges that simply represent the linear structure of an assembly program from those that imply an explicit reference to other points of the code, such as jumps or data references.