Tue 16 Jun 2015 15:15 - 15:40 at PLDI Main BLUE (Portland 254-255) - Analysis Chair(s): Yannis Smaragdakis

We develop a new framework for analyzing recursive methods that perform traversals over trees, called tree dependence analysis. This analysis translates dependence analysis techniques for regular programs to the irregular space, identifying the structure of dependences within a recursive method that traverses trees. We develop a dependence test that exploits the dependence structure of such programs, and can prove that several locality- and parallelism-enhancing transformations are legal. In addition, we extend our analysis with a novel path-dependent, conditional analysis to refine the dependence test and prove the legality of transformations for a wider range of algorithms. We then use these analyses to show that several common algorithms that manipulate trees recursively are amenable to several locality- and parallelism enhancing transformations. This work shows that classical dependence analysis techniques, which have largely been confined to nested loops over array data structures, can be extended and translated to work for complex, recursive programs that operate over pointer-based data structures.

PLDI 2015 Artifact Evaluated Badge

Conference Day
Tue 16 Jun

Displayed time zone: Tijuana, Baja California change

14:00 - 15:40
14:00
25m
Talk
DAG Inlining: A Decision Procedure for Reachability-Modulo-Theories in Hierarchical Programs
Research Papers
Akash LalMicrosoft Research India, Shaz QadeerMicrosoft Research
Media Attached File Attached
14:25
25m
Talk
Exploring and Enforcing Security Guarantees via Program Dependence Graphs
Research Papers
Andrew JohnsonHarvard University, Lucas WayeHarvard University, Scott MooreHarvard University, Stephen ChongHarvard University
Media Attached
14:50
25m
Talk
Making Numerical Program Analysis Fast
Research Papers
Gagandeep SinghETH Zurich, Switzerland, Markus PüschelETH Zurich, Martin VechevETH Zurich
Media Attached
15:15
25m
Talk
Tree Dependence Analysis
Research Papers
Yusheng WeijiangPurdue University, Shruthi BalakrishnaPurdue University, Jianqiao LiuPurdue University, Milind KulkarniPurdue University
Media Attached