Projection merging
- 5 January 2000
- conference paper
- Published by Association for Computing Machinery (ACM)
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 [7], projection merging achieves orders of magnitude speedup of analysis time on programs over that of using cycle elimination alone.Keywords
This publication has 13 references indexed in Scilit:
- Partial online cycle elimination in inclusion constraint graphsPublished by Association for Computing Machinery (ACM) ,1998
- Interconvertbility of set constraints and context-free language reachabilityPublished by Association for Computing Machinery (ACM) ,1997
- A practical subtyping system for ErlangPublished by Association for Computing Machinery (ACM) ,1997
- Linear-time subtransitive control flow analysisPublished by Association for Computing Machinery (ACM) ,1997
- Catching bugs in the web of program invariantsPublished by Association for Computing Machinery (ACM) ,1996
- Points-to analysis in almost linear timePublished by Association for Computing Machinery (ACM) ,1996
- Soft typing with conditional typesPublished by Association for Computing Machinery (ACM) ,1994
- Type inclusion constraints and type inferencePublished by Association for Computing Machinery (ACM) ,1993
- Control flow analysis in schemePublished by Association for Computing Machinery (ACM) ,1988
- Flow analysis and optimization of LISP-like structuresPublished by Association for Computing Machinery (ACM) ,1979