Global sparse analysis framework

Hakjoo Oh, Kihong Heo, Wonchan Lee, Woosuk Lee, Daejun Park, Jeehoon Kang, Kwangkeun Yi

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)


In this article, we present a general method for achieving global static analyzers that are precise and sound, yet also scalable. Our method, on top of the abstract interpretation framework, is a general sparse analysis technique that supports relational as well as nonrelational semantics properties for various programming languages. Analysis designers first use the abstract interpretation framework to have a global and correct static analyzer whose scalability is unattended. Upon this underlying sound static analyzer, analysis designers add our generalized sparse analysis techniques to improve its scalability while preserving the precision of the underlying analysis. Our method prescribes what to prove to guarantee that the resulting sparse version should preserve the precision of the underlying analyzer. We formally present our framework and show that existing sparse analyses are all restricted instances of our framework. In addition, we show more semantically elaborate design examples of sparse nonrelational and relational static analyses. We then present their implementation results that scale to globally analyze up to one million lines of C programs. We also show a set of implementation techniques that turn out to be critical to economically support the sparse analysis process.

Original languageEnglish
Article number8
JournalACM Transactions on Programming Languages and Systems
Issue number3
Publication statusPublished - 2014 Aug 1
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2014 ACM.

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Global sparse analysis framework'. Together they form a unique fingerprint.

Cite this