The Cinder JIT compiler does some cool stuff with how they represent types so I’m going to share it with you here. The core of it is thinking about types as sets (lattices, even), and picking a compact representation. Compilers will create and manipulate types with abandon, so all operations have to be fast.
We’ll start from first principles, assuming we’re analyzing a language like Python, and build our way up to roughly what Cinder has (and we could go further from there).
Note that this post is about a compiler internal view of SSA value types and nothing to do with surface level type annotations. We’ll use Python code snippets (as if they were IR) to sketch ideas, though.
Types, as a concept, name sets of objects—sets of instances. Some types (say,
int8) have finite members. There are only ever 256 potential values for an
8-bit integer. Some times, (say, list) are infinite. Given enough storage,
one could keep generating bigger and bigger instances. Since it’s not possible
to store all elements of a set, we refer to types by a name.
This reduces precision. Maybe there is some bizarre case where you know that
an object could be one of a thousand different possible lists, so giving up
and saying “it’s a list” loses information. But it also saves a bunch of
space and analysis time, because now we’re dealing with very small labels.
Let’s start off by giving a couple built-in types names and calling it a day.
A reasonable first way to give types names is with an enum:
enum {
Int,
List,
String,
Object, // catch-all
};
Not bad. We can represent some built-in types and we have a catch-all case to
use when we don’t know what type something is or the type doesn’t fit neatly
into our enum (Object), which captures the object type and all of its
subclasses.
Using this enum, we can assign types to variables (for the purposes of this post, SSA values) and use those types to optimize. For example, we might see the following pseudo-Python snippet:
a = [...]
return len(a)
If we know that the type of a is List, we can optimize the call to
len1 to a direct call to the list class’s __len__ method,
or—even better, since we know about CPython’s runtime details—read the
ob_size field directly off the object.
That’s great! It will catch a bunch of real-world cases and speed up code.
Unfortunately, it gives up a little too easily. Consider some silly-ish code
that either assigns a str or a list depending on some condition:
def foo(cond):
if cond:
a = "..."
else:
a = [...]
return len(a)
Because a could have either type, we have to union the type information we
know into a more general type. Since we don’t have ListOrString case in our
enum (nor should we), we have to pick something more general: Object.
That’s a bummer, because we as runtime implementors know that both str and
list have __len__ methods that just read the ob_size field. Now that we
have lost so much information in the type union, we have to do a very generic
call to the len function.
To get around this, we can turn the straightforward enum into a bitset.
Bitsets encode set information by assigning each bit in some number (say, a 64-bit word) a value. If that bit is 1, the value is in the set. Otherwise, it isn’t.
Here’s the enum from earlier, remade as a bitset:
enum {
Int = 1 << 0, // 0b001
List = 1 << 1, // 0b010
String = 1 << 2, // 0b100
Object = 7, // 0b111; catch-all
};
We have three elements: Int, List, and String. Since we have a bit for
each object and they can be addressed individually, we can very
straightforwardly encode the ListOrString type using bitwise arithmetic:
List | String // 0b110
It doesn’t even need to be a basic type in our enum. We can construct it using our built-in building blocks.
We have also set our unknown/catch-all/Object type as the value with all
bits set, so that if we or together all of our known types
(Int|List|String), the unknown-ness falls out naturally.
…but what does the unnamed 0 value represent? If we are thinking in terms of sets still (which we should be), then 0 means no bits set, which means it represents 0 elements, which means it’s the empty set!
We’re starting to approach a very useful mathematical structure called a semilattice.
I’m not going to quote you any formal definitions because I’m not very mathy. I’ll give you a one sentence abstract sounding definition and then make it concrete very soon after.
A semilattice is a partial (not total) order of a set with a join operation. The lattice also has a top element and a bottom element. Ok, let’s talk about what that means for us.
For our limited type data structure, our partial order is determined by set membership and our join is set union. Top represents “all possible objects” and bottom represents “no objects”:
Check out this handy diagram of our original enum-based type lattice:
The arrows indicate that applying a join will only ever move us upward along
an arrow. For example, join(Int, String) is Top (we don’t have any
finer-grained way to represent all ints and all strings).
Compare this with, for example, what we can represent with our bitset type representation:
See how we have two new layers! We have a Bottom (empty) type now. For example,
join(Bottom, Bottom) is Bottom (it remains empty), and join(Bottom, List)
is List (no new elements).
We can also address the set of all ints and all strings with Int|String,
which is ordered above each of the invidual int and string sets.
As I alluded to earlier, we can conveniently represent a bottom element in our bitset type:
enum Type {
Bottom = 0, // 0b000
Int = 1 << 0, // 0b001
List = 1 << 1, // 0b010
String = 1 << 2, // 0b100
Top = 7, // 0b111
};
enum Type join(enum Type left, enum Type right) {
return left | right;
}
// Ask if `left` is a subtype of `right`
bool is_subtype(enum Type left, enum Type right) {
return (left & right) == left;
}
This type representation is neat, but we can go further. Sometimes, you know more than just the type of an object: you know exactly what object it is. We’ll introduce what Cinder calls specialization.
In addition to our existing type lattice, Cinder keeps a second lattice called
a specialization. Its job is to keep track of what specific object an SSA value
is. For example, if we know that a = 5, its type would be Int and its
specialization would be 5.
The specialization lattice is much simpler:
struct Spec {
enum {
SpecTop,
SpecInt,
SpecBottom,
} spec_kind;
int value;
};
In Rust syntax—to make the validity of the value field clearer—that’s:
enum SpecKind {
SpecTop,
SpecInt(int),
SpecBottom,
}
There’s an internal enum that says what we know about the specialization and an optional value. There are a couple of cases:
SpecTop, we don’t have any information about the specializationSpecInt, we know exactly the integer value, and the value
field is valid (initialized, readable)SpecBottom, we know that the spec contains no elements (and
therefore also must have a type of Bottom)Here’s what the diagram looks like:
Where N represents some integer stored in the value field.
This complicates things a bit. Let’s put both the type bits and the specialization together in one structure and admire:
struct Type {
enum TypeBits {
Bottom = 0, // 0b000
Int = 1 << 0, // 0b001
List = 1 << 1, // 0b010
String = 1 << 2, // 0b100
Top = 7, // 0b111
} type;
// If you are feeling clever, you can also steal some `type` bits for the
// `spec_kind` instead of putting it in a separate field.
struct Spec {
enum {
SpecTop,
SpecInt,
SpecBottom,
} spec_kind;
int value;
} spec;
};
const struct Type TTop = (struct Type) {
.type = Top,
.spec = (struct Spec) { .spec_kind = SpecTop },
};
const struct Type TInt = (struct Type) {
.type = Int,
.spec = (struct Spec) { .spec_kind = SpecTop },
};
const struct Type TThree = (struct Type) {
.type = Int,
.spec = (struct Spec) { .spec_kind = SpecInt, .value = 3 },
};
// Invariant: .type == Bottom if and only if .spec_kind == SpecBottom.
const struct Type Bottom = (struct Type) {
.type = Bottom,
.spec = (struct Spec) { .spec_kind = SpecBottom },
};
That’s very nice and more precise, but now our join and is_subtype
operators don’t make a whole lot of sense. We can’t just use bitwise operations
any more. We have to also do the lattice operations on the Spec field:
struct Type join(struct Type left, struct Type right) {
struct Type result;
result.type = left.type | right.type;
result.spec = spec_join(left.spec, right.spec);
return result;
}
// Ask if `left` is a subtype of `right`
bool is_subtype(struct Type left, struct Type right) {
return (left & right) == left && spec_is_subtype(left.spec, right.spec);
}
If we decompose the problem that way, we can write some lattice operations for
Spec. Let’s start with is_subtype:
// Ask if `left` is a subtype of `right`
bool spec_is_subtype(struct Spec left, struct Spec right) {
if (right.spec_kind == SpecTop || left.spec_kind == SpecBottom) {
// Top is a supertype of everything and Bottom is a subtype of
// everything
return true;
}
// left is now either SpecInt or SpecTop
// right is now either SpecInt or SpecBottom
// The only way left could be a subtype of right is if they are both
// SpecInt and the value is the same
if (left.spec_kind == SpecInt &&
right.spec_kind == SpecInt &&
left.value == right.value) {
return true;
}
return false;
}
That takes a bit of time to internalize, so please read over it a couple of
times and work out the cases by hand. It’s really useful for implementing
spec_join:
struct Spec spec_join(struct Spec left, struct Spec right) {
if (spec_is_subtype(left, right)) { return right; }
if (spec_is_subtype(right, left)) { return left; }
// We know that neither left nor right is either SpecTop or SpecBottom
// because that would have been covered in one of the subtype cases, so
// we're join-ing two SpecInts. That's SpecTop.
struct Spec result;
result.spec_kind = SpecTop;
return result;
}
It’s a couple more instructions than a single bitwise operation and a compare, but it’s still compact and fast.
Let’s talk about some problems you might run into while using this API.
A common mistake when handling Bottom is treating it as an error, or assuming
it will never show up in your program. To expand on its brief introduction
above, the two main consequences of Bottom’s place at the bottom of the type
lattice are:
Bottom can never be defined. An instruction with an
output of type Bottom will therefore never define its output. Such an
instruction might loop infinitely, it might crash your program, or it might
jump to another location in the program (if your compiler supports
control-flow instructions that define values).Bottom can never be used, so an instruction with an
input of type Bottom is unreachable. This follows from the previous item
(since you obviously can’t use a value you can’t define), but is worth
calling out separately.These two properties make checking for Bottom useful in an unreachable code
elimination pass. Otherwise, though, Bottom is just another type, and your
type predicates will generally be cleaner if you design them to correctly
handle Bottom without explicitly testing for it.
Most of the time, Bottom support happens out naturally. Cinder, for
example, calls the exact integer type LongExact. We can check if a type is
an exact integer with:
if (t.is_subtype(LongExact)) {
// generate int-specific code
}
In this example, t == Bottom will be fine: any code that is generated (if
your compiler doesn’t eliminate unreachable code) will never run, so it’s
perfectly fine to call a helper function that expects an int, or to load a
field of PyLongObject, etc.
Sometimes, however, we want to get a concrete value out of a type at
compile-time for an optimization such as constant folding. It may be tempting
to assume that if your type t is a strict subtype of (can’t be equal to)
LongExact, it represents a specific int object:
if (t.is_strict_subtype(LongExact)) {
PyLongObject* a_long = t.asPyObject();
// ... optimize based on a_long
}
This code is broken for plenty of cases other than Bottom (e.g.,
range-constrained int types), but in many compilers, Bottom will usually be
the first type that causes a crash or failed assertion here. Rather than
excluding Bottom by name, with code like if (t != Bottom && t.is_strict_subtype(LongExact)), you can handle Bottom (and all other types!) correctly by
refining your type predicate to what you really mean.
In this case, you want to know if t represents exactly one value, so you
might use an API like t.admitsSingleValue(LongExact). That will correctly
exclude Bottom, which represents zero values, but it will also correctly
exclude a type that means “an int that is less than 0”, which is a strict
subtype of LongExact but doesn’t represent a single value.
Now, these type bits are a pain to write down by hand. Instead, it would be nice to generate them automatically given a class hierarchy. That’s what Cinder does.
Here is an abridged sketch of the Cinder script to generate it, since the Cinder version has a couple more quirks that are not crucial to understanding the core of this post:
class UnionSpec(NamedTuple):
name: str
components: List[str]
# All the leaf types, each of which gets a bit
BASIC_FINAL_TYPES: List[str] = [
"Bool",
"NoneType",
# ...
]
BASIC_BASE_TYPES: List[str] = [
"Bytes",
"Dict",
# ...
]
BASIC_EXACT_TYPES: List[str] = [
"ObjectExact",
*[ty + "Exact" for ty in BASIC_BASE_TYPES],
]
BASIC_USER_TYPES: List[str] = [
"ObjectUser",
*[ty + "User" for ty in BASIC_BASE_TYPES],
]
BASIC_PYTYPES: List[str] = BASIC_FINAL_TYPES + BASIC_EXACT_TYPES + BASIC_USER_TYPES
# The unions, which have multiple bits set
PYTYPE_UNIONS: List[UnionSpec] = [
UnionSpec("BuiltinExact", BASIC_FINAL_TYPES + BASIC_EXACT_TYPES),
*[UnionSpec(ty, [ty + "User", ty + "Exact"]) for ty in BASIC_BASE_TYPES],
UnionSpec("User", BASIC_USER_TYPES),
UnionSpec("Object", BASIC_PYTYPES),
UnionSpec("Top", BASIC_PYTYPES),
UnionSpec("Bottom", []),
]
def assign_bits() -> Tuple[Dict[str, int], int]:
"""Create the bit patterns for all predefined types: basic types are given
one bit each, then union types are constructed from the basic types.
"""
bit_idx = 0
bits = {}
for ty in BASIC_PYTYPES:
bits[ty] = 1 << bit_idx
bit_idx += 1
for ty, components, _ in PYTYPE_UNIONS:
bits[ty] = reduce(operator.or_, [bits[t] for t in components], 0)
return bits, bit_idx
It’s a bit of a funky snippet, but the gist is that it creates a bunch of leaf
types such as DictExact and BytesUser and assigns each a bit. Then, it goes
through all of the unions and bitwise ors their component bits together. Last
(not pictured), it prints out a uint64_t for each of these.
The output is an X-macro that looks something like this:
// For all types, call X(name, bits)
#define HIR_TYPES(X) \
X(Array, 0x00000000001UL) \
X(BaseException, 0x00000801000UL) \
X(BaseExceptionExact, 0x00000001000UL) \
X(BaseExceptionUser, 0x00000800000UL) \
X(Bool, 0x00000000002UL) \
/* ... */ \
X(User, 0x000ffe00000UL) \
X(WaitHandle, 0x00000000200UL)
const size_t kNumTypeBits = 44;
Check out the Cinder implementation.
Cinder also has some other features embedded into the same type bitset:
CInt32, CDouble,
CBool, Null, …), which inherently handles nullabilitySee also the type.md document which goes into detail about Cinder’s type system.
There are some features Cinder does not (currently) support but would be cool to implement:
Thanks to CF Bolz-Tereick, Cliff Click, Tom Hebb, Kai Williams, and Thomas Gardner for feedback on this post.
Pretend for now that we can’t redefine or shadow len
because that trickiness is unrelated to this post. ↩