Partial Online Cycle Elimination in Inclusion Constraint Graphs

M. Fähndrich, J. Foster, Z. Su, and A. Aiken

Abstract

Many program analyses are naturally formulated and implemented using inclusion constraints. We present newresults on the scalable implementation of such analyses based on two insights: first, that online elimination of cyclic constraints yields orders-of magnitude improvements in analysis time for large problems; second, that the choice of constraint representation affects the quality and efficiency of online cycle elimination. We present an analytical model that explains our design choices and show that the model's predictions match well with results from a substantial experiment.

Details

Publication typeInproceedings
Published inProceedings of the 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation
Pages85–96
Number33:5
SeriesSIGPLAN notices
> Publications > Partial Online Cycle Elimination in Inclusion Constraint Graphs