Partial Online Cycle Elimination in Inclusion Constraint Graphs

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.

pldi98.pdf
PDF file

In  Proceedings of the 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation

Details

TypeInproceedings
Pages85–96
Number33:5
SeriesSIGPLAN notices
> Publications > Partial Online Cycle Elimination in Inclusion Constraint Graphs