Hybrid top-down and bottom-up interprocedural analysis

Conference item

Interprocedural static analyses are broadly classified into top-down and bottom-up, depending upon how they compute, instantiate, and reuse procedure summaries. Both kinds of analyses are challenging to scale: top-down analyses are hindered by ineffective reuse of summaries whereas bottom-up analyses are hindered by inefficient computation and instantiation of summaries. This paper presents a hybrid approach SWIFT that combines top-down and bottomup analyses in a manner that gains their benefits without suffering their drawbacks. SWIFT is general in that it is parametrized by the top-down and bottom-up analyses it combines. We show an instantiation of SWIFT on a type-state analysis and evaluate it on a suite of 12 Java programs of size 60-250 KLOC each. SWIFT outperforms both conventional approaches, finishing on all the programs while both of those approaches fail on the larger programs

Authors: Zhang, X; Mangal, R; Naik, M; Yang, H

• Publication status: Published
• Peer review status: Reviewed (other)
• Publisher: Association for Computing Machinery
• Host title: Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation
• Journal: Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation
• Pages: 249-258
• Publication date: 2014-09-06
• Acceptance date: 2014-02-05
• DOI: 10.1145/2594291.2594328
• ISBN: 9781450327848