Composable, Sound Transformations of Nested Recursion and Loops

Kirshanthan Sundararajah and Milind Kulkarni

PLDI 2019 · Programming Language Design and Implementation · June 2019 · pp. 902-917

Acceptance rate 27%

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.

BibTeX

@inproceedings{sundararajah19pldi,
  author    = {Kirshanthan Sundararajah and Milind Kulkarni},
  title     = {Composable, Sound Transformations of Nested Recursion and Loops},
  booktitle = {Proceedings of the Programming Language Design and Implementation (PLDI)},
  pages     = {902--917},
  publisher = {Association for Computing Machinery},
  address   = {Phoenix, AZ, USA},
  year      = {2019},
  month     = jun,
  doi       = {10.1145/3314221.3314592}
}

Group members