Projection Merging: Reducing Redundancies in Inclusion Constraint Graphs

Zhendong Su, Manuel Fähndrich, and Alexander Aiken

Abstract

Inclusion-based program analyses are implemented by adding new edges to directed graphs. In most analyses, there are many different ways to add a transitive edge between two nodes, namely through each different path connecting the nodes. This path redundancy limits the scalability of these analyses. We present projection merging, a technique to reduce path redundancy. Combined with cycle elimination, projection merging achieves orders of magnitude speedup of analysis time on programs over that of using cycle elimination alone.

Details

Publication typeInproceedings
Published inProceedings POPL 2000, 27'th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
> Publications > Projection Merging: Reducing Redundancies in Inclusion Constraint Graphs