How to Unleash Array Optimizations on Code Using Recursive Data Structures

摘要

Loop optimization and parallelization have been most successful on code using arrays exclusively. Preferably, such code does not contain indirect access and has only simple, counted loops. The use of recursive data structures makes matters even worse, and optimization of such code has been less successful. Traversal of such data structures is often done using loops with data-dependent loop conditions. In this paper, we present a compiler transformation chain that transforms pointer traversal loops into counted loops operating on arrays that are indirectly accessed. We also show that this indirect access can in some cases be eliminated if the traversed data structure is reordered in memory. This results in a representation on which many existing techniques can be applied. Our system requires monitoring of actual arguments and heap data on which loop conditions depend so that preconditions for the optimized functions can be checked. Our experiments show that this overhead is small, considering the optimization opportunities the representation of the transformed code provides, and well worth the price.