Modeling Recursion with Iteration: Enabling LLVM Loop Optimizations for Recursive Data Structure Traversal

Recursive algorithms are a natural and expressive way to traverse complex data structures, but they often miss opportunities for optimization in modern compiler infrastructures like LLVM. This thesis explores a novel technique that temporarily transforms recursive traversals into synthetic loop-like structures, enabling existing loop-specific optimizations to apply, before transforming them back. By extending Clang’s semantic analysis and implementing a custom LLVM transformation pass, recursive traversals are initially structured into synthetic loops that can benefit from existing loop analyses and optimizations. After these optimizations are applied, the transformation restores the original recursive semantics, preserving program behavior while incorporating performance gains. Evaluation across custom microbenchmarks shows that while general recursive traversals suffer a modest overhead, workloads designed to benefit specific loop-focused optimizations achieve up to a 30% performance improvement. This demonstrates that even though the approach requires temporarily "misrepresenting" code to the compiler, selective exposure of recursive patterns to loop-based optimization infrastructure is practical and effective. This work establishes a proof-of-concept for compiler transformations that bridge recursion and iteration, paving the way for future systems that better optimize real-world recursive code without sacrificing clarity or maintainability.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2025

Author dc:creator

• Cuevas, Elie E.

Advisor dc:contributor.advisor

• Schardl, Tao B.

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/162684

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/162684