Fragments

Fragments are the main data structure in the compiler used to represent code objects as they are rendered. A Fragment is modelled as a map from Strings to S-Expressions.

It is not wrong to think of a Fragment as only a data structure that maps Strings to S-Expressions. However, in LM programming, there is also the implicit interaction between Fragments and the LM Type System.

To demonstrate the interaction between fragments and types, consider:

What is a Local Variable?

The definition of a Local Variable may depend on several things:

• what compiler and what language are you working with
• what optimization pass are you currently looking at
• what architecture and operating system are you targeting

When designing a compiler you need to remain aware of all of these concerns and configurations. If you forget any of these issues then you may introduce bugs into your compiler.

To prevent such issues inside the compiler, LM uses what are called Typed Fragments to sort out expectations surrounding outgoing code objects. For example, a LocalVariable in LM might be defined as a relative offset from a base pointer. This notion can be represented as follows:

LocalVariable:
   datatype: x
   .offset-from-base-pointer: I64
   expect: typeof-address(%rbp + .offset-from-base-pointer) = x

Here any LocalVariable fragment is associated with some constraints. The first datatype constraint requires that the datatype of the fragment is equal to x: this always unifies so the constraint is only used to grab more information from the type system. Next we expect that a fragment has an .offset-from-base-pointer field which is a signed integer. Finally, we expect that the datatype of the LocalVariable is the same as the known type at that address.

Compiler bugs are annoying to work with, so LM introduced Typed Fragments to help resolve this potential confusion. When working with Typed Fragments, you can leverage the Type System to sanity check your code generation step, completely eliminating the potential for many types of errors.