28. pyxc: Heap Allocation

What I Am Building

Chapter 27 gave me fixed-size arrays, but they have two limits I can't get around: their size has to be known at compile time, and they die the moment the function that declared them returns. Neither works for data whose size I only know at runtime, or that needs to outlive the function that created it. For that I need the heap, and the heap means calling malloc and free.

After this chapter:

extern def malloc(n: int64) -> ptr[int8]
extern def free(p: ptr[int8])
extern def printd(x: float64)

def main() -> int:
  var n: int64 = 5
  var raw: ptr[int8] = ptr[int8](malloc(n * sizeof(int64)))
  var p: ptr[int64] = ptr[int64](raw)
  p[0] = 5
  p[1] = 7
  p[2] = 9
  p[3] = 6
  p[4] = 8
  var q: ptr[int64] = p + 2
  printd(float64(q[0] + q[1] + q[2]))  # 23.000000
  free(raw)
  return 0

malloc and free are just the C standard library functions. I don't need any new machinery to call them; extern already lets me call any C function. What I'm actually missing is two smaller things: a way to tell malloc how many bytes I want, and a way to tell pyxc what type the bytes it hands back should be treated as.

sizeof(T) gives me the byte size of type T as a compile-time constant, so I can compute the right argument to malloc.
ptr[T](expr) reinterprets a pointer of one type as a pointer of another, which I need because malloc only ever hands me ptr[int8] (raw bytes), and I want to treat them as, say, ptr[int64].

Source Code

git clone --depth 1 https://github.com/alankarmisra/pyxc-llvm-tutorial
cd pyxc-llvm-tutorial/code/chapter-28

Grammar

Two productions change this chapter: primary gains a sizeof-expression alternative, and cast-type gains pointer-type, since a pointer cast target is now legal where it wasn't before. Everything else is exactly what Chapter 27 already had:

*...
*factor                            = ("-" | "!" | "~") factor | primary ;
*primary                           = cast-expression
+                                    | sizeof-expression
*                                    | address-expression
*                                    | array-literal
*...
*                                    | parenthesized-expression ;
*cast-expression                   = cast-type "(" expression ")" ;
+sizeof-expression                 = "sizeof" "(" type ")" ;
*address-expression                = "addr" "(" lvalue ")" ;
*array-literal                     = "[" [ expression
*...
*                                    | "float64" | "bool" | "None" ;
*struct-type                       = name ;
-cast-type                         = "int" | "int8" | "int16" | "int32"
+cast-type                         = builtin-cast-type | pointer-type ;
+builtin-cast-type                 = "int" | "int8" | "int16" | "int32"
*                                    | "int64" | "uint8" | "uint16"
*                                    | "uint32" | "uint64"
*...

One New Keyword

sizeof needs a token like every other keyword I've added:

*enum Token {
*  ...
*  tok_struct = -50,
*  tok_ptr = -51,
*  tok_addr = -52,
+  tok_sizeof = -53,
*
*  // punctuation and operators
*  ...
*};

*static map<string, Token> Keywords = {
*    ...
*    {"ptr", tok_ptr},         {"addr", tok_addr},
+    {"sizeof", tok_sizeof},
*    {"float", tok_float},
*    ...
*};

`sizeof(T)`: A Size I Don't Have to Compute Myself

I could compute a struct's size by hand: add up its fields, account for padding, remember that pointers are 8 bytes on a 64-bit target. But I already have all of that information, since I just built the LLVM type for every struct I've declared. Asking LLVM for the size directly is both less error-prone and correct across whatever target I eventually compile for.

sizeof(T) always produces an int64, no matter what T is:

class SizeofExpressionNode : public ExpressionNode {
  ValueType TargetType;
  string TargetTypeInfo;

public:
  SizeofExpressionNode(ValueType TargetType,
                       const string &TargetTypeInfo = "")
      : TargetType(TargetType), TargetTypeInfo(TargetTypeInfo) {
    setType(ValueType::Int64);
  }
  Value *codegen() override;
};

I call setType(ValueType::Int64) in the constructor rather than leaving it to be inferred later, since the result type never depends on TargetType: sizeof(int8) and sizeof(Point) are both int64.

Parsing it means reusing ParseTypeToken, the same function every other type annotation in pyxc goes through:

static unique_ptr<ExpressionNode> ParseSizeofExpression() {
  getNextToken(); // eat 'sizeof'
  if (CurrentToken != tok_lparen)
    return LogErrorExpression("Expected '(' after sizeof");
  getNextToken(); // eat '('
  string TargetTypeInfo;
  ValueType TargetType = ParseTypeToken(&TargetTypeInfo);
  if (TargetType == ValueType::Error)
    return nullptr;
  if (TargetType == ValueType::None)
    return LogErrorExpression("Cannot take sizeof(None)");
  if (CurrentToken != tok_rparen)
    return LogErrorExpression("Expected ')' after sizeof type");
  getNextToken(); // eat ')'
  return make_unique<SizeofExpressionNode>(TargetType, TargetTypeInfo);
}

sizeof(None) is the one type I reject outright: None isn't a value at all, so asking for its size is a question that shouldn't have been asked. ParsePrimary routes tok_sizeof here:

*  switch (CurrentToken) {
*  ...
*  case tok_bool:
*    return ParseCastExpression();
+  case tok_sizeof:
+    return ParseSizeofExpression();
*  case tok_addr:
*    return ParseAddrExpression();
*  ...
*  }

Codegen doesn't emit an instruction, since there's nothing to compute at runtime:

Value *SizeofExpressionNode::codegen() {
  llvm::Type *TargetLLVMType = LLVMTypeFor(TargetType, TargetTypeInfo);
  if (!TargetLLVMType)
    return LogErrorValue("Invalid sizeof target type");
  uint64_t Bytes = TheModule->getDataLayout()
                       .getTypeAllocSize(TargetLLVMType)
                       .getFixedValue();
  return ConstantInt::get(Type::getInt64Ty(*TheContext), Bytes);
}

getTypeAllocSize is LLVM's own answer to "how many bytes does one of these take up in an array," padding included, for whatever target I'm compiling for. I hand it a type and get back a number I fold directly into a constant. For a function that just returns sizeof(int64), the generated IR is:

define i64 @size_i64() {
entry:
  ret i64 8
}

No call, no load: the size was already known once code generation started, so it's just a literal by the time IR exists.

Sizes I get on a 64-bit target:

Type	`sizeof`
`int8`	1
`int32`	4
`int64`	8
`ptr[int8]`	8
`Point` (two `int` fields)	16

Every pointer is 8 bytes here regardless of what it points to. LLVM's opaque pointer model means there's only one pointer representation at the IR level; pyxc is the one tracking what it points to, not LLVM.

`ptr[T](expr)`: Reinterpreting a Pointer

Before this chapter, ptr[int64](raw) wasn't rejected by any type check, it was rejected by the parser before it got that far: ParsePrimary had no case tok_ptr at all, so a leading ptr in expression position was simply "unknown token when expecting an expression." I confirmed this against Chapter 27's binary directly rather than guess at it.

So the fix isn't lifting a guard, it's adding a case, falling through to the exact same call every other cast target already uses:

*  case tok_bool:
+  case tok_ptr:
*    return ParseCastExpression();
*  case tok_sizeof:
*    return ParseSizeofExpression();

Once tok_ptr is reachable, though, I do need one new guard, since ParseCastExpression will now happily see Type == ValueType::Pointer and I don't want to allow casting just anything to a pointer:

*static unique_ptr<ExpressionNode> ParseCastExpression() {
-  ValueType Type = ParseTypeToken();
+  string TargetTypeInfo;
+  ValueType Type = ParseTypeToken(&TargetTypeInfo);
*  if (Type == ValueType::Error)
*    return nullptr;
*  if (Type == ValueType::None)
*    return LogErrorExpression("Cannot cast to None");
*  if (CurrentToken != tok_lparen)
*    return LogErrorExpression("Expected '(' after cast type");
*  getNextToken(); // eat '('
*  auto Expr = ParseExpression();
*  if (!Expr)
*    return nullptr;
*  if (CurrentToken != tok_rparen)
*    return LogErrorExpression("Expected ')' after cast expression");
*  getNextToken(); // eat ')'
+  if (Type == ValueType::Pointer && Expr->getType() != ValueType::Pointer)
+    return LogErrorExpression("Pointer casts require a pointer operand");
-  return make_unique<CastExpressionNode>(Type, std::move(Expr));
+  return make_unique<CastExpressionNode>(Type, std::move(Expr),
+                                          TargetTypeInfo);
*}

I don't allow casting an integer to a pointer. There's no address I could hand it that pyxc could vouch for, and letting that through would just be a way to smuggle in undefined behavior with a friendlier syntax.

CastExpressionNode needs a TargetTypeInfo now, for the same reason SizeofExpressionNode does: ptr[Point] and ptr[int64] are both ValueType::Pointer, so the pointee type has to travel separately:

*class CastExpressionNode : public ExpressionNode {
*  ValueType TargetType;
+  string TargetTypeInfo;
*  unique_ptr<ExpressionNode> Expr;
*
*public:
-  CastExpressionNode(ValueType TargetType, unique_ptr<ExpressionNode> Expr)
-      : TargetType(TargetType), Expr(std::move(Expr)) {
-    setType(TargetType);
+  CastExpressionNode(ValueType TargetType, unique_ptr<ExpressionNode> Expr,
+                     const string &TargetTypeInfo = "")
+      : TargetType(TargetType), TargetTypeInfo(TargetTypeInfo),
+        Expr(std::move(Expr)) {
+    setType(TargetType, TargetTypeInfo);
*  }
*  Value *codegen() override;
*};

Without it, a cast to ptr[int64] would carry no pointee information at all, and anything downstream that indexes or reads through the result wouldn't know what it's pointing at.

Codegen for the pointer-to-pointer case is nothing at all, because at the LLVM level there's nothing to do:

*static Value *EmitCast(Value *V, ValueType From, ValueType To) {
*  if (!V)
*    return nullptr;
*  if (From == To)
*    return V;
+  if (From == ValueType::Pointer && To == ValueType::Pointer)
+    return V;
*  // Integer ↔ float conversions.
*  ...
*}

With opaque pointers, every pointer is the same IR type regardless of what it points to, so there's no instruction to emit between two of them: the value just passes through unchanged. I confirmed this by compiling a cast and reading the IR:

%calltmp = call ptr @malloc(i64 8)
store ptr %calltmp, ptr %raw, align 8
%raw1 = load ptr, ptr %raw, align 8
store ptr %raw1, ptr %p, align 8

No bitcast anywhere. The cast's only real effect is at the pyxc level: the result is now typed ptr[int64] instead of ptr[int8], so any GEP or load I generate from it afterward uses the right element type.

Calling `malloc` and `free`

extern def malloc(n: int64) -> ptr[int8]
extern def free(p: ptr[int8])

Nothing about these declarations is special; any C function with compatible types can be called the same way. malloc always hands back ptr[int8], raw bytes with no notion of what they're eventually going to hold. Assigning that straight to a var raw: ptr[int8] works fine, since the declared pointee and the call's pointee already match. What doesn't work is going straight to the type I actually want:

var p: ptr[Point] = malloc(sizeof(Point))

Error: Type mismatch in variable initialization

This is the same pointee-type check every other pointer assignment goes through: the declared variable's pointee (Point) doesn't match the initializer's pointee (int8), so it's rejected exactly like assigning a ptr[int8] local to a ptr[Point] variable would be. sizeof(Point) tells malloc how many bytes to hand back, but it doesn't change what type those bytes come back as. The fix is the cast I just added: ptr[Point](expr) reinterprets the ptr[int8] result as a ptr[Point].

var raw: ptr[int8] = malloc(sizeof(Point))
var p: ptr[Point] = ptr[Point](raw)

The full pattern for heap-allocating a single struct:

struct Point:
  x: int
  y: int

def main() -> int:
  var raw: ptr[int8] = ptr[int8](malloc(sizeof(Point)))
  var p: ptr[Point] = ptr[Point](raw)
  p[0].x = 77
  printd(float64(p[0].x))
  free(raw)
  return 0

malloc hands back raw bytes as ptr[int8]. ptr[Point](raw) tells pyxc to treat those same bytes as a Point, so p[0].x generates the right field offset. free gets the original ptr[int8] back. Passing p directly would be a type error, since p is ptr[Point], not ptr[int8].

Build and Run

cd code/chapter-28
cmake -S . -B build && cmake --build build

llvm-lit -v test/

Try It

`sizeof` of Scalar Types and a Struct

extern def printd(x: float64)

struct Point:
  x: int
  y: int

def main() -> int:
  printd(float64(sizeof(int8)))
  printd(float64(sizeof(int32)))
  printd(float64(sizeof(int64)))
  printd(float64(sizeof(ptr[int8])))
  printd(float64(sizeof(Point)))
  return 0

`malloc`, a Pointer Cast, and Field Access

extern def malloc(n: int64) -> ptr[int8]
extern def free(p: ptr[int8])
extern def printd(x: float64)

struct Point:
  x: int
  y: int

def main() -> int:
  var raw: ptr[int8] = ptr[int8](malloc(sizeof(Point)))
  var p: ptr[Point] = ptr[Point](raw)
  p[0].x = 77
  p[0].y = 33
  printd(float64(p[0].x))
  printd(float64(p[0].y))
  free(raw)
  return 0

77.000000
33.000000

`malloc` and Pointer Arithmetic: A Heap Array

extern def malloc(n: int64) -> ptr[int8]
extern def free(p: ptr[int8])
extern def printd(x: float64)

def main() -> int:
  var n: int64 = 5
  var raw: ptr[int8] = ptr[int8](malloc(n * sizeof(int64)))
  var p: ptr[int64] = ptr[int64](raw)
  p[0] = 5
  p[1] = 7
  p[2] = 9
  p[3] = 6
  p[4] = 8
  var q: ptr[int64] = p + 2
  printd(float64(q[0] + q[1] + q[2]))
  free(raw)
  return 0

23.000000

Inspecting the IR: `sizeof` Really Is Just a Constant

pyxc --emit llvm-ir -o out.ll program.pyxc
grep 'ret i64' out.ll

ret i64 8

Known Limitations

No null check. malloc can return null when the system is out of memory. I don't insert a null check; dereferencing a null pointer crashes silently.

No bounds checking. Accessing p[n] on a heap buffer of size n is an out-of-bounds write. I don't track buffer sizes anywhere.

Manual ownership. There's no destructor, no reference counting, no garbage collector. Forgetting to call free leaks memory; calling it twice or reading after free is undefined behavior: silently corrupted data, or a crash, with no diagnostic pointing at why.

Pointer casts are pointer-only. ptr[T](expr) requires expr to already be a pointer; I don't let an integer become a pointer through a cast. And the cast doesn't do anything at the LLVM level, since every pointer already has the same IR representation; its only job is telling pyxc what pointee type to track from here on.

What's Next

Chapter 29 adds type aliases.

Need Help?

Build issues? Questions?

GitHub Issues: Report problems
Discussions: Ask questions

Include:

Your OS and version
Full error message
Output of cmake --version, ninja --version, and llvm-config --version

I'll help you figure it out.

< 27. pyxc: Arrays

29. pyxc: Type Aliases >