A collaborative dependence analysis framework

Nick P. Johnson; Jordan Fix; Stephen R. Beard; Taewook Oh; Thomas B. Jablin; David I. August

doi:10.1109/CGO.2017.7863736

A collaborative dependence analysis framework

Nick P. Johnson, Jordan Fix, Stephen R. Beard, Taewook Oh, Thomas B. Jablin, David I. August

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

14 Scopus citations

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.

Original language	English (US)
Title of host publication	CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization
Editors	Vijay Janapa Reddi, Aaron Smith, Lingjia Tang
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	148-159
Number of pages	12
ISBN (Electronic)	9781509049318
DOIs	https://doi.org/10.1109/CGO.2017.7863736
State	Published - Feb 23 2017
Event	2017 International Symposium on Code Generation and Optimization, CGO 2017 - Austin, United States Duration: Feb 4 2017 → Feb 8 2017

Publication series

Name	CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization

Other

Other	2017 International Symposium on Code Generation and Optimization, CGO 2017
Country/Territory	United States
City	Austin
Period	2/4/17 → 2/8/17

All Science Journal Classification (ASJC) codes

Software
Control and Optimization

Keywords

Collaborative analysis
Demand-driven analysis
Dependence analysis
Program Dependence Graph

Access to Document

10.1109/CGO.2017.7863736

Cite this

Johnson, N. P., Fix, J., Beard, S. R., Oh, T., Jablin, T. B., & August, D. I. (2017). A collaborative dependence analysis framework. In V. J. Reddi, A. Smith, & L. Tang (Eds.), CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization (pp. 148-159). Article 7863736 (CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CGO.2017.7863736

Johnson, Nick P. ; Fix, Jordan ; Beard, Stephen R. et al. / A collaborative dependence analysis framework. CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization. editor / Vijay Janapa Reddi ; Aaron Smith ; Lingjia Tang. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 148-159 (CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization).

@inproceedings{0a36bbeb835f4c4abf3e2cac7554cecc,

title = "A collaborative dependence analysis framework",

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.",

keywords = "Collaborative analysis, Demand-driven analysis, Dependence analysis, Program Dependence Graph",

author = "Johnson, {Nick P.} and Jordan Fix and Beard, {Stephen R.} and Taewook Oh and Jablin, {Thomas B.} and August, {David I.}",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 2017 International Symposium on Code Generation and Optimization, CGO 2017 ; Conference date: 04-02-2017 Through 08-02-2017",

year = "2017",

month = feb,

day = "23",

doi = "10.1109/CGO.2017.7863736",

language = "English (US)",

series = "CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "148--159",

editor = "Reddi, {Vijay Janapa} and Aaron Smith and Lingjia Tang",

booktitle = "CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization",

address = "United States",

}

Johnson, NP, Fix, J, Beard, SR, Oh, T, Jablin, TB & August, DI 2017, A collaborative dependence analysis framework. in VJ Reddi, A Smith & L Tang (eds), CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization., 7863736, CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization, Institute of Electrical and Electronics Engineers Inc., pp. 148-159, 2017 International Symposium on Code Generation and Optimization, CGO 2017, Austin, United States, 2/4/17. https://doi.org/10.1109/CGO.2017.7863736

A collaborative dependence analysis framework. / Johnson, Nick P.; Fix, Jordan; Beard, Stephen R. et al.
CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization. ed. / Vijay Janapa Reddi; Aaron Smith; Lingjia Tang. Institute of Electrical and Electronics Engineers Inc., 2017. p. 148-159 7863736 (CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A collaborative dependence analysis framework

AU - Johnson, Nick P.

AU - Fix, Jordan

AU - Beard, Stephen R.

AU - Oh, Taewook

AU - Jablin, Thomas B.

AU - August, David I.

PY - 2017/2/23

Y1 - 2017/2/23

N2 - 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.

AB - 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.

KW - Collaborative analysis

KW - Demand-driven analysis

KW - Dependence analysis

KW - Program Dependence Graph

UR - http://www.scopus.com/inward/record.url?scp=85016068585&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85016068585&partnerID=8YFLogxK

U2 - 10.1109/CGO.2017.7863736

DO - 10.1109/CGO.2017.7863736

M3 - Conference contribution

AN - SCOPUS:85016068585

T3 - CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization

SP - 148

EP - 159

BT - CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization

A2 - Reddi, Vijay Janapa

A2 - Smith, Aaron

A2 - Tang, Lingjia

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2017 International Symposium on Code Generation and Optimization, CGO 2017

Y2 - 4 February 2017 through 8 February 2017

ER -

Johnson NP, Fix J, Beard SR, Oh T, Jablin TB, August DI. A collaborative dependence analysis framework. In Reddi VJ, Smith A, Tang L, editors, CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization. Institute of Electrical and Electronics Engineers Inc. 2017. p. 148-159. 7863736. (CGO 2017 - Proceedings of the 2017 International Symposium on Code Generation and Optimization). doi: 10.1109/CGO.2017.7863736

A collaborative dependence analysis framework

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this