@inproceedings{sundararajah19pldi, author = {Sundararajah, Kirshanthan and Kulkarni, Milind}, title = {Composable, Sound Transformations of Nested Recursion and Loops}, year = {2019}, isbn = {9781450367127}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3314221.3314592}, doi = {10.1145/3314221.3314592}, abstract = {Scheduling transformations reorder a program’s operations to improve locality and/or parallelism. The polyhedral model is a general framework for composing and applying instance-wise scheduling transformations for loop-based programs, but there is no analogous framework for recursive programs. This paper presents an approach for composing and applying scheduling transformations—like inlining, interchange, and code motion—to nested recursive programs. This paper describes the phases of the approach—representing dynamic instances, composing and applying transformations, reasoning about correctness—and shows that these techniques can verify the soundness of composed transformations.}, booktitle = {Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation}, pages = {902–917}, numpages = {16}, keywords = {Locality, Recursion, Scheduling Transformations, Dependence Testing}, location = {Phoenix, AZ, USA}, series = {PLDI 2019} }