  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.
