On-Line Graph Algorithms for Incremental Compilation

TitleOn-Line Graph Algorithms for Incremental Compilation
Publication TypeTechnical Report
Year of Publication1992
AuthorsMarchetti-Spaccamela, A., Nanni U., & Rohnert H.
Other Numbers761

Compilers usually construct various data structures which often vary only slightly from compilation run to compilation run. This paper gives various solutions to the problems of quickly updating these data structures instead of building them from scratch each time. All problems we found can be reduced to graph problems. Specifically, we give algorithms for updating data structures for the problems of topological order, loop detection, and reachability from the start routine.

Bibliographic Notes

ICSI Technical Report TR-92-056

Abbreviated Authors

A. Marchetti-Spaccamela, U. Nanni, and H. Rohnert

ICSI Publication Type

Technical Report