Article

A collaborative dependence analysis framework

Authors:

Nick P. Johnson,

Stephen R. Beard,

Thomas B. Jablin,

David I. AugustAuthors Info & Claims

CGO '17: Proceedings of the 2017 International Symposium on Code Generation and Optimization

Pages 148 - 159

Published: 04 February 2017 Publication History

Abstract

Compiler optimizations discover facts about program behavior by querying static analysis. However, developing or extending precise analysis is difficult. Some prior works implement analysis with a single algorithm, but the algorithm becomes more complex as it is extended for greater precision. Other works achieve modularity by implementing several simple algorithms and trivially composing them to report the best result from among them. Such a modular approach has limited precision because it employs only one algorithm in response to one query, without synergy between algorithms. This paper presents a framework for dependence analysis algorithms to collaborate and achieve precision greater than the trivial combination of those algorithms. With this framework, developers can achieve the high precision of complex analysis algorithms through collaboration of simple and orthogonal algorithms, without sacrificing the ease of implementation of the modular approach. Results demonstrate that collaboration of simple analyses enables advanced compiler optimizations.

References

[1]

L. O. Andersen. Program analysis and specialization for the C programming language, May 1994.

[2]

U. Banerjee. Loop Parallelization. Kluwer Academic Publishers, Boston, MA, 1994.

Digital Library

[3]

S. Blackshear, B.-Y. E. Chang, and M. Sridharan. Thresher: precise refutations for heap reachability. In Proceedings of the 34th ACM SIGPLAN conference on Programming language design and implementation, PLDI ’13, pages 275–286, New York, NY, USA, 2013. ACM.

Digital Library

[4]

M. Bravenboer and Y. Smaragdakis. Exception analysis and points-to analysis: Better together. In Proceedings of the Eighteenth International Symposium on Software Testing and Analysis, ISSTA ’09, pages 1–12, New York, NY, USA, 2009. ACM.

Digital Library

[5]

M. Bravenboer and Y. Smaragdakis. Strictly declarative specification of sophisticated points-to analyses. In Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications, OOPSLA ’09, pages 243–262, New York, NY, USA, 2009. ACM.

Digital Library

[6]

C. Click and K. D. Cooper. Combining analyses, combining optimizations. ACM Transactions on Programming Languages and Systems, 17, 1995.

Digital Library

[7]

P. Cousot, R. Cousot, and L. Mauborgne. The reduced product of abstract domains and the combination of decision procedures. In Proceedings of the 14th International Conference on Foundations of Software Science and Computational Structures: Part of the Joint European Conferences on Theory and Practice of Software, FOSSACS’11 /ETAPS’11, pages 456– 472, Berlin, Heidelberg, 2011. Springer-Verlag.

Digital Library

[8]

J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 9:319–349, July 1987.

Digital Library

[9]

R. Ghiya and L. J. Hendren. Is it a Tree, DAG, or Cyclic Graph? In Proceedings of the ACM Symposium on Principles of Programming Languages, January 1996.

Digital Library

[10]

B. Guo, N. Vachharajani, and D. I. August. Shape analysis with inductive recursion synthesis. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 256–265, June 2007.

Digital Library

[11]

S. Z. Guyer and C. Lin. Client-driven pointer analysis. In In International Static Analysis Symposium, pages 214–236. Springer-Verlag, 2003.

Digital Library

[12]

M. Hind. Pointer analysis: Haven’t we solved this problem yet? In 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE), 2001.

Digital Library

[13]

S. Horwitz. Precise flow-insensitive may-alias analysis is NPhard. ACM Transactions on Programming Languages and Systems, 19(1), January 1997.

Digital Library

[14]

N. P. Johnson, T. Oh, A. Zaks, and D. I. August. Fast condensation of the program dependence graph. In Proceedings of the 34th ACM SIGPLAN conference on Programming language design and implementation, PLDI ’13, pages 39–50, New York, NY, USA, 2013. ACM.

Digital Library

[15]

H. Kim. ASAP: Automatic Speculative Acyclic Parallelization for Clusters. PhD thesis, Princeton, NJ, USA, 2013.

[16]

M. S. Lam, J. Whaley, V. B. Livshits, M. C. Martin, D. Avots, M. Carbin, and C. Unkel. Context-sensitive program analysis as database queries. In Proceedings of the Twenty-fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’05, pages 1–12, New York, NY, USA, 2005. ACM.

Digital Library

[17]

C. Lattner and V. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In Proceedings of the Annual International Symposium on Code Generation and Optimization (CGO), pages 75–86, 2004.

Digital Library

[18]

C. Lattner, A. Lenharth, and V. Adve. Making Context-Sensitive Points-to Analysis with Heap Cloning Practical For The Real World. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), San Diego, California, June 2007.

Digital Library

[19]

S. Lerner, D. Grove, and C. Chambers. Composing dataflow analyses and transformations. In Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’02, pages 270–282, New York, NY, USA, 2002. ACM. ISBN 1-58113-450-9.

Digital Library

[20]

O. Lhotak. Program Analysis using Binary Decision Diagrams. PhD thesis, School of Computer Science, McGill University, Montreal, Quebec, Canada, January 2006.

Digital Library

[21]

O. Lhoták and L. Hendren. Evaluating the benefits of contextsensitive points-to analysis using a bdd-based implementation. ACM Trans. Softw. Eng. Methodol., 18(1):3:1–3:53, Oct. 2008.

Digital Library

[22]

O. Lhoták, Y. Smaragdakis, and M. Sridharan. Pointer Analysis (Dagstuhl Seminar 13162). Dagstuhl Reports, 3(4): 91–113, 2013.

[23]

P. Liang and M. Naik. Scaling abstraction refinement via pruning. In Proceedings of the 2011 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI).

Digital Library

[24]

LLVM Project. LLVM Alias Analysis Infrastructure, October 2013. http: //llvm.org/docs/AliasAnalysis.html.

[25]

T. R. Mason. Lampview: A loop-aware toolset for facilitating parallelization. Master’s thesis, Department of Electrical Engineering, Princeton University, Princeton, New Jersey, United States, August 2009.

[26]

R. Muth and S. Debray. On the complexity of flow-sensitive dataflow analyses. In In Proc. ACM Symp. on Principles of Programming Languages, pages 67–80. ACM Press, 2000.

Digital Library

[27]

G. Nelson and D. C. Oppen. Simplification by cooperating decision procedures. ACM Transactions on Programming Languages and Systems, 1:245–257, 1979.

Digital Library

[28]

W. Pugh. The omega test: a fast and practical integer programming algorithm for dependence analysis. In Proceedings of Supercomputing 1991, pages 4–13, November 1991.

Digital Library

[29]

E. Raman, G. Ottoni, A. Raman, M. Bridges, and D. I. August. Parallel-stage decoupled software pipelining. In Proceedings of the Annual International Symposium on Code Generation and Optimization (CGO), 2008.

Digital Library

[30]

M. Sagiv, T. Reps, and R.Wilhelm. Solving shape-analysis problems in languages with destructive updating. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 16–31, January 1996.

Digital Library

[31]

spec. Standard Performance Evaluation Corporation. http: //www.spec.org.

[32]

B. Steensgaard. Points-to analysis in almost linear time. In Proceedings of the ACM Symposium on Principles of Programming Languages, pages 32–41, January 1996.

Digital Library

[33]

J. Whaley and M. S. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, (PLDI), pages 131–144, New York, NY, 2004.

Digital Library

Cited By

Licker NJones T(2020)Duplo: a framework for OCaml post-link optimisationProceedings of the ACM on Programming Languages10.1145/34089804:ICFP(1-29)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3408980
Helm DKübler FReif MEichberg MMezini MDevanbu PCohen MZimmermann T(2020)Modular collaborative program analysis in OPALProceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3368089.3409765(184-196)Online publication date: 8-Nov-2020
https://dl.acm.org/doi/10.1145/3368089.3409765
Zyrianov VNewman CGuarnera DCollard MMaletic JGuéhéneuc YKhomh FSarro F(2019)srcPtrProceedings of the 27th International Conference on Program Comprehension10.1109/ICPC.2019.00031(144-147)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICPC.2019.00031

Recommendations

On-demand dynamic summary-based points-to analysis
CGO '12: Proceedings of the Tenth International Symposium on Code Generation and Optimization

Static analyses can be typically accelerated by reducing redundancies. Modern demand-driven points-to or alias analysis techniques rest on the foundation of Context-Free Language (CFL) reachability. These techniques achieve high precision efficiently ...
Refinement-based context-sensitive points-to analysis for Java
Proceedings of the 2006 PLDI Conference

We present a scalable and precise context-sensitive points-to analysis with three key properties: (1) filtering out of unrealizable paths, (2) a context-sensitive heap abstraction, and (3) a context-sensitive call graph. Previous work [21] has shown ...
Refinement-based context-sensitive points-to analysis for Java
PLDI '06: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation

We present a scalable and precise context-sensitive points-to analysis with three key properties: (1) filtering out of unrealizable paths, (2) a context-sensitive heap abstraction, and (3) a context-sensitive call graph. Previous work [21] has shown ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CGO '17: Proceedings of the 2017 International Symposium on Code Generation and Optimization

February 2017

317 pages

ISBN:9781509049318

General Chair:
Vijay Janapa Reddi
University of Texas at Austin, USA
,
Program Chairs:
Aaron Smith
Microsoft Research, UK / University of Edinburgh, UK
,
Lingjia Tang
University of Michigan, USA

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing
IEEE-CS: Computer Society

Publisher

IEEE Press

Publication History

Published: 04 February 2017

Check for updates

Author Tags

Qualifiers

Article

Conference

CGO '17

Sponsor:

CGO '17: 15th Annual IEEE/ACM International Symposium on Code Generation and Optimization

February 4 - 8, 2017

Austin, USA

Acceptance Rates

CGO '17 Paper Acceptance Rate 26 of 116 submissions, 22%;

Overall Acceptance Rate 312 of 1,061 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
245
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Licker NJones T(2020)Duplo: a framework for OCaml post-link optimisationProceedings of the ACM on Programming Languages10.1145/34089804:ICFP(1-29)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3408980
Helm DKübler FReif MEichberg MMezini MDevanbu PCohen MZimmermann T(2020)Modular collaborative program analysis in OPALProceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3368089.3409765(184-196)Online publication date: 8-Nov-2020
https://dl.acm.org/doi/10.1145/3368089.3409765
Zyrianov VNewman CGuarnera DCollard MMaletic JGuéhéneuc YKhomh FSarro F(2019)srcPtrProceedings of the 27th International Conference on Program Comprehension10.1109/ICPC.2019.00031(144-147)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICPC.2019.00031

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents