Projection Merging: Reducing Redundancies in Inclusion Constraint Graphs

  • Zhendong Su ,
  • Manuel Fahndrich ,
  • Alexander Aiken

Proceedings POPL 2000, 27'th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages |

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.