Extending the LIFT Intermediate Language for GPGPU

LIFT IL is an array-oriented intermediate language (IL) for GPGPU programming. The LIFT compiler translates a high-level language program into LIFT IL, applies hardware-specific optimizations, and then generates an OpenCL program. The IL has a dependent type system that infers the length of arrays as a symbol. This forces every array to have a length that can be statically determined, preventing one from expressing arrays having a dynamic length. This project extends LIFT IL to support arrays having a dynamic length by using existential types. We also propose an algorithm that automatically inserts pack and unpack operations, which are necessary for existential types. Based on the proposal, we implemented a LIFT IL compiler and added a filter function. In order to assess the usefulness to real world problems, we confirmed the problems that require the dynamic length array in a subset of Project Euler can successfully be written, compiled and executed in the extended LIFT IL compiler.