Layered Region Based Flow-Sensitive Demand-Driven Alias Analysis

Abstract:

The pointer alias is indispensable for program analysis. Comparing to point-to set, it’s more efficient to formulate the alias as the context free language (CFL) reachability problem. However, the precision is limited to flow-insensitivity. To solve this problem, we propose a flow sensitive, demand-driven analysis algorithm for answering may-alias queries. First the partial single static assignment is used to discriminate the address-taken pointers. Then the order of control flow is encoded in the level linearization code to ease comparison. Finally, the query of alias in demand driven is converted into the search of CFL reachability with feasible flows. The experiments demonstrate the effectiveness of the proposed approach.

• Periodical: Applied Mechanics and Materials (Volume 577)
• Pages: 917-920
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.577.917
• Online since: July 2014
• Authors: Long Pang*, Xiao Hong Su, Pei Jun Ma, Ling Ling Zhao
• Keywords: Alias Analysis, Dyck-CFL-Reachability, Flow Sensitive Analysis, Graph Reachability

References

[1] Lei Shang, Xinwei Xie, and Jingling Xue. On-demand dynamic summary-based points-to analysis. In Proceedings of the Tenth International Symposium on Code Generation and Optimization, ACM, (2012), p.264–274.

DOI: 10.1145/2259016.2259050

[2] Dacong Yan, Guoqing Xu, and Atanas Rountev. Demand-driven context-sensitive alias analysis for java. In Proceedings of the 2011 International Symposium on Software Testing and Analysis, ACM, (2011), p.155–165.

DOI: 10.1145/2001420.2001440

[3] Xin Zheng and Radu Rugina. Demand-driven alias analysis for C. ACM SIGPLAN Notices, 43 (1): (2008), p.197–208.

DOI: 10.1145/1328897.1328464

[4] Qirun Zhang, Michael R Lyu, Hao Yuan, and Zhendong Su. Fast algorithms for Dyck-CFL-reachability with applications to alias analysis. In Proceedings of the 34th ACM SIGPLAN conference on Programming language design and implementation, ACM, (2013).

DOI: 10.1145/2491956.2462159

[5] Lian Li, Cristina Cifuentes, and Nathan Keynes. Boosting the performance of flow-sensitive points-to analysis using value flow. In Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering, pages 343–353. ACM, (2011).

DOI: 10.1145/2025113.2025160

[6] Hongtao Yu, Jingling Xue, Wei Huo, Xiaobing Feng, and Zhaoqing Zhang. Level by level: making flow-and context-sensitive pointer analysis scalable for millions of lines of code. In Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization, ACM, (2010).

DOI: 10.1145/1772954.1772985

[7] Ben Hardekopf and Calvin Lin. Flow-sensitive pointer analysis for millions of lines of code. In Code Generation and Optimization (CGO), 2011 9th Annual IEEE/ACM International Symposium on, IEEE, (2011), p.289–298.

DOI: 10.1109/cgo.2011.5764696

[8] Lattner, Chris, and Vikram Adve. LLVM: A compilation framework for lifelong program analysis & transformation., Code Generation and Optimization, 2004. CGO 2004. International Symposium on. IEEE, (2004), pp.75-86.

DOI: 10.1109/cgo.2004.1281665