Data collections—such as arrays, lists, sets, and maps—are among the most commonly used abstractions in modern programs, yet compilers discard their rich semantic structure before performing analysis and optimization.
Once lowered to raw memory, the logical organization of a collection is lost, leaving the compiler to reason about undecidable problems, such as pointer aliasing.
I present MEMOIR: a general-purpose compiler intermediate representation (IR) that preserves data collections in static single assignment (SSA) form, making their logical structure explicit for analysis and optimization.
I demonstrate the benefits of MEMOIR with novel layout-agnostic optimizations that operate directly on logical collections.
Furthermore, I show how the compiler can manufacture data properties to enable specialized implementations, such as bitsets, achieving significant performance and memory savings compared to industry-standard implementations.
Representing collections in SSA form makes these analyses efficient through sparse dataflow, but introduces two challenges.
First, SSA represents updates functionally.
Lowering them back to imperative code risks introducing copies that turn an O(1) update into an O(n) operation.
I formally prove that MEMOIR programs can always be lowered without such copies, and show that standard compiler transformations can be made to maintain this guarantee with 100% effectiveness and negligible overhead.
Second, references and iterators, which are ubiquitous in languages like C++, identify elements independently of the collection that owns them.
However, SSA value semantics have no way to express this.
I introduce bookmark semantics to resolve this tension.