A Time and Space-Efficient Compositional Method for Data Flow Analysis

This paper investigates the problem of static data flow analysis, which is an important problem in program comprehension, optimization, and bug detection. However, its application to large-scale, real-world software often faces significant challenges related to computational time and memory consumption, particularly for programs exhibiting extremely large Npath complexities. Existing approaches frequently struggle to scale efficiently while maintaining precision. To address this deficiency, we propose a novel compositional method for classical data flow analyses, specifically focusing on Available Expressions, Very Busy Expressions, Reaching Definitions, and Live Variables. Our approach leverages the decomposition of the Control Flow Graph into its Strongly Connected Components (SCCs), employing a divide-and-conquer strategy that analyzes smaller, more manageable program corpora. A key innovation is the Two-level Set Accessing Method (TSAM), a non-contiguous, pointer-based data structure that significantly reduces memory overhead for storing the dynamic data flow information. We prove that our algorithm, which utilizes a queueing mechanism for fixed-point computation, eventually terminates while achieving the same level of precision as traditional, exhaustive global analyses. Our extensive experimental evaluation against the traditional iterative method demonstrates that the SCC-based method, coupled with TSAM, significantly outperforms existing techniques, consuming on average 53% less memory and utilizing 43% less processing time, particularly for programs with high Npath complexity. This work provides a practical and scalable solution for precise data flow analysis of complex software systems.