To fully leverage the capabilities of modern computer hardware, compilers become a necessity. By automatically applying hundreds of varied optimizations, compilers generate binaries that make efficient use of these capabilities. The intermediate representation (IR) of an optimizing compiler is the most important decision in its design, clearly laying out the scope and goal of optimizations. For example, the now ubiquitous use of static single assignment (SSA) forms enhances the compiler’s ability to perform data flow analysis both accurately and efficiently. However, modern optimizing compilers have turned a blind eye to the representation of memory in the program, leaving optimizations on the layout and usage of memory as a secondary consideration. This decision hands developers the arduous task of describing both the semantics and layout of their data in memory. As a result, high-level concepts like data collections are prematurely lowered to low-level memory representations. From this, the compiler can only glean conservative information about the memory in a program—e.g., alias analysis—and can make little to no strong guarantees for data collections more complex than arrays. This poses a barrier to optimization.
To remedy this issue, we propose MEMOIR, a language-agnostic SSA IR for irregular data collections. At the core of MEMOIR is a decoupling of the memory used to store data from that used to logically organize data. With this decoupling, compiler optimizations can reason about the state of a collection at any given program point without ambiguity. Through its SSA form, MEMOIR generalizes a wealth of scalar optimizations to operate on data collections at the element granularity. Additionally, it opens the door for an entirely new class of memory layout and reuse optimizations that are impossible in modern compilers.
