Field Experience
The relationship classes described in this article were originally written for and used in the construction of an interprocedural data-flow analyzer for programs written in Ada. Data-flow analysis is used for various compiler optimizations and automatic generation of test cases. As is true for the majority of compilation-related tools, data-flow analyzers are extremely data intensive, making use of many data structures such as symbol tables, type tables, data-flow graphs, and others. These data structures must be efficiently representable in memory, providing quick access to the required information. In order to manage the complexity of the task, it makes sense to organize the analyzer as a set of logical software modules. These modules have distinct functionality and many of them need access to a common set of shared data structures.
For example, the symbol table structure is constructed by the parser module and then used by many other modules. The symbol table must keep track of local definitions and uses of variables. The table of local definition uses is constructed by walking the parse tree; it is subsequently used in several other phases, such as constructing data-flow equations. To make such data easily accessible, we made all data structures global. Placing each data structure into its own namespace helped avoid name clashes:
namespace LocDefUse{
ManyMany<Def*, Line> _defs;
ManyMany<Use*, Line> _uses;
...
};
namespace SymbolTable {
...
}
As a result of using the described association classes, many complex algorithms in our analyzer became easier to implement. In data-flow analysis, a definition of a variable is an action that changes the value of the variable’s memory location. An assignment is the most common form of a definition. Thus, definitions and line numbers form a many-to-many association: there can be many definitions on a line and the same variable may be defined on many lines.
The kill set of a variable definition consists of all other assignments to the variable in the same function. (It’s called the “kill set” because a definition “kills” all other definitions, including itself if it’s part of a loop.)
The following snippet shows how an association class can be used to construct the kill set for each definition on a given line:
ManyMany<Def*, Line>::iterator1
it1 = LocDefUse::_defs.begin(line),
end1 = LocDefUse::_defs.end(line);
//for all definition on this line
for(; it1 != end1; ++it1){
Def* pDef = *it1;
ManyMany<Def*, Line>::iterator2
it1 = LocDefUse::_defs.begin(pDef),
end2 = LocDefUse::_defs.end(pDef);
//for all definitions of this variable in the function
for(; it2 != end2; ++it2){
Line l = *it2;
...
}
}
The second for-loop goes through all the lines that also define this definition’s variable. The pseudocode for the example might look like this:
For all definitions on this line
For each definition of a variable,
go through all the lines where this
variable is defined.
Since a definition kills all other definitions, the second for-loop produces the kill set. Thus the use of ManyMany association here significantly simplifies the kill set computation.
