Partial Online Cycle Elimination in Inclusion Constraint Graphs
- Manuel Fahndrich ,
- Jeffrey S. Foster ,
- Zhendong Su ,
- Alexander Aiken
Proceedings of the 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation |
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.