A C++ data dependence graph library for optimizing compilation

We are pleased to announce the release of an object oriented data
dependence graph library (built on top of the LEDA library). Our graph
library is specially though for people willing to make quick, robust and
modular implementations of code optimization techniques for basic blocks
and simple loops (modeled by regular mono-dimensional data
    dependences). We plan to extend it to model non-perfectly nested loops
(multi-dimensional data dependences using algebraic polyhedrons).


At present, we manage directed acyclic graphs (DAGs) for basic blocks
and cyclic graphs for innermost loops. The user is able to take
advantage of many standard algorithms for graphs and general data
structures. Also, some well known algorithms on data dependence graphs
are implemented (such as computing critical cycles and so on). It is
also possible to configure the library for different instruction set
architectures.


Some Algorithms Implemented by LEDA that we can use inside our DDG library


          * Basic Graph Algorithms
                    1. Sorts algorithms (DFS, BFS, etc.)
                    2. Computing strongly connected components, connected
components, bipartite components, transitive closure, transitive reduction
          * Shortest Path Algorithms
          * Maximum Flow
          * Min Cost Flow Algorithms
          * Minimum Cut
          * Maximum Cardinality Matchings in Bipartite Graphs
          * Bipartite Weighted Matchings and Assignments
          * Maximum Cardinality Matchings in General Graphs
          * General Weighted Matchings
          * Stable Matching
          * Minimum Spanning Trees
          * Euler Tours
          * Algorithms for Planar Graphs
          * Graph Drawing Algorithms
          * Graph Morphism Algorithms
          * Graph Morphism Algorithm Functionality


Some Algorithms Implemented by the DDG Library


          * DAG algorithms
                    1. Shortest and longest paths between any pair of nodes
                    2. Dilworth decomposition, maximal antichain, etc.
                    3. Register Saturation of a DAG (maximal register pressure
independently of instruction schedules).
                    4. Import and export methods to gl format (see The gl format
for importing and exporting data dependence graphs).
                    5. Exporting to graph visualization tool (xvcg).
          * Loop algorithms
                    1. Critical cycle (even null cycles are detected)
                    2. Import and export methods to gl format
                    3. Exporting to graph visualization tool (xvcg).




Online documentation: http://www.prism.uvsq.fr/~touati/sw/DDG


Download software and reference manual :
http://www.prism.uvsq.fr/~touati/sw/DDG/DDG-0.9.tgz

Return to the comp.compilers page.
Search the comp.compilers archives again.