A Collaborative Dependence Analysis Framework [abstract] (ACM DL, PDF)
Nick P. Johnson, Jordan Fix, Taewook Oh, Stephen R. Beard, Thomas B. Jablin, and David I. August
Proceedings of the 2017 International Symposium on Code Generation
and Optimization (CGO), February 2017.
Accept Rate: 22% (26/114).
Highest ranked paper in double-blind review process.
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