Ultra-fast Aliasing Analysis using CLA: A Million Lines of C Code in a Second

We describe the design and implementation of a system for very fast points-to analysis. On code bases of about a million lines of u unpreprocessed C code, our system performs Andersen-style points-to analysis in less than a second and uses less than 10MB of memory. Our two main contributions are a database-centric analysis architecture called compile-link-analyze (CLA), and a new algorithm for implementing dynamic transitive closure. Our points-to analysis system is built into a forward data-dependence analysis tool that is deployed within Lucent to help with consistent type modifications to large legacy C code bases.