3 Apr 2006 01:36:31 -0400

Related articles |
---|

A C++ data dependence graph library for optimizing compilation touati@prism.uvsq.fr (Touati Sid) (2006-04-03) |

From: | Touati Sid <touati@prism.uvsq.fr> |

Newsgroups: | comp.compilers |

Date: | 3 Apr 2006 01:36:31 -0400 |

Organization: | Universite de Versailles Saint-Quentin-en-Yvelines |

Keywords: | available, C++, analysis |

Posted-Date: | 03 Apr 2006 01:36:31 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.