Code Generation from Functional to Imperative: Combining Destination-Passing Style and Views

Zhitao Lin
School of Computer Science, McGill University, Montréal, Québec, Canada
McGill University, 2022


   title={Code generation from functional to imperative: Combining destination-passing style and views},

   author={Lin, Zhitao},



Download Download (PDF)   View View   Source Source   



Programming in low-level imperative languages provides good performance but is error-prone. In contrast, high-level functional programming is usually free from low-level errors but performance suffers from costly abstractions. To benefit from both worlds, approaches like Lift compile from high-level functional programs to high-performance imperative code. However, problems such as removing high-level abstraction costs and handling lazy operations are not tackled ideally, which makes such compilation remains an open challenge. This thesis presents an approach to compiling a high-level array-based functional Intermediate Representation (IR) into high-performance imperative code. It combines the existing work on Destination-Passing Style (DPS) with the Lift views system by extending the notion of view to destinations. Destination views can be seen as lazy operations that work in reverse and affect how data is being produced into memory, rather than how data is being consumed. This approach produces imperative code that existing techniques cannot produce. The evaluation shows that the code produced outperforms the existing DPS approach on several real-world workloads when targeting sequential CPU code. The thesis also demonstrates how destination views can be used to generate high-performance stencil code on Graphics Processing Units (GPUs), by encoding the 2.5D tiling optimization in a functional style.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: