@inproceedings{sakka19pldi, author = {Sakka, Laith and Sundararajah, Kirshanthan and Newton, Ryan R. and Kulkarni, Milind}, title = {Sound, Fine-Grained Traversal Fusion for Heterogeneous Trees}, year = {2019}, isbn = {9781450367127}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3314221.3314626}, doi = {10.1145/3314221.3314626}, abstract = {Applications in many domains are based on a series of traversals of tree structures, and fusing these traversals together to reduce the total number of passes over the tree is a common, important optimization technique. In applications such as compilers and render trees, these trees are heterogeneous: different nodes of the tree have different types. Unfortunately, prior work for fusing traversals falls short in different ways: they do not handle heterogeneity; they require using domain-specific languages to express an application; they rely on the programmer to aver that fusing traversals is safe, without any soundness guarantee; or they can only perform coarse-grain fusion, leading to missed fusion opportunities. This paper addresses these shortcomings to build a framework for fusing traversals of heterogeneous trees that is automatic, sound, and fine-grained. We show across several case studies that our approach is able to allow programmers to write simple, intuitive traversals, and then automatically fuse them to substantially improve performance.}, booktitle = {Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation}, pages = {830–844}, numpages = {15}, keywords = {Locality, Fusion, Tree traversals}, location = {Phoenix, AZ, USA}, series = {PLDI 2019} }