Annotated control flow graph with magnification?

Question

I have a control flow graph representing one procedure of my intermediate language code. The nodes and edges are annotated using the properties of the vertices / borders and contain instructions and information about the branches.

Now I want to perform data flow analysis on this graph and transfer this graph to each data flow analysis module. Each module should be able to annotate CFG with its own data.
Problems to be solved:

• I don’t know in advance how many annotations are implemented by data flow analysis modules (since in the future I will use additional analysis modules)
• I don’t know anything about the type of annotation represented by a particular data flow analysis module
• Each data flow analysis module must exist independently of other modules, i.e. module A does not have to care about the annotations introduced by module B

Do you see any chance to fulfill all of the above requirements? Any comments or recommendations are greatly appreciated.

Update:
To be more specific, I basically want to separate my annotations from the Graph type. When using the usual properties of vertices / edges, the Graph type itself is always "dirty" (and therefore depends on the types of properties of vertices / borders) by the contained types of properties.

Answer 1

See the chapter “Using Properties” in the accelerator library documentation. Especially in the section "Creating an appearance map." If this does not answer your question, could you clarify what is missing?

Answer 2

I do not know a standard way to associate an unlimited set of properties with adjacenty_list. Since I assume you care about performance, I would suggest the following approach. First, enter tag types for each property that you want to use, like BGL. Properties do not have to be defined in one place - a module that implements specialized analysis can determine the type of tag in the header or source file. For instance:

struct execution_count { typedef int value_type; }; 

value_type typedef should indicate the type of value that the property has.

Then create a new graph type derived from adjacently_list and add a new get_dynamic_property_map method. This method will return a property map for a specific regular property. The dynamic_property_map class will be explained later. It is assumed that your algorithm calls this method at startup, and this method is not needed very quickly.

 std::map<std::type_info, boost::any> dynamic_properties_; template<class Property> dynamic_property_map<typename Property::value_type> get_dynamic_property_map() { typedef typename Property::value_type V; if (!dynamic_properties_.count(typeid(Property)) dynamic_properties_.insert(make_pair(typeid(Property), new dynamic_property_map<V>(); boost::any a = dynamic_properties_[typeid(Property)]; return *boost::any_cast<dynamic_property_map<V>*>(a); } 

Here you can use boost :: any and type_info to store an arbitrary set of property maps for the chart without specifying types in advance.

The dynamic_property_map class takes a vertex and returns a value, but in the simplest form it can be:

 template<class T> class dynamic_property_map : public std::vector<T> {}; 

This assumes that (1) the vertex_descriptor is an integer and (2) you are not adding new vertices after creating the map. If you add new vertices, you must override the [] operator to check if the index is greater than or equal to. If so, resize the vector.

If vertex_descriptor not an integer, you need more code. dynamic_property_map must also have a graph type as a template parameter, and must also contain a link to the graph. get_dynamic_property_map will need to be adjusted. operator[] will have to do this:

 template<class V, class G> V& dynamic_property_map<V, G>::operator[]( typename graph_traits<G>::vertex_descriptor v) { int index = get(vertex_index_t, g_ /* member referring to graph */, v); return std::vector<V>::operator[](index); } 

You probably need a way to store properties around the edges. Then add another overload as above.

Unfortunately, BGL does not support "autonumbering" edges, but you can get from adjacency_list and override methods that add edges to populate the edge_index_t property.

Hope this helps.

Note 0. I did not even try to compile the code above. While I had one working solution, it now has several computers.

Note 1. The map from type_info does not actually work, since type_info does not define the <operator. You can define such an operator yourself or put the result of type_info::name on the map, which is technically less reliable.

Note 2. The output from std::vector used only for presentation. Decide if it is a good idea for a final decision.