Rambles around computer science

LLVM structural typing

I'm learning about the LLVM compiler infrastructure at the moment.

LLVM bitcode includes a notion of data types. These are used to control implicitly the size and encoding of values generated by various operations, to hint about mappings to underlying machine data types (e.g. on architectures that distinguish floating-point from integer registers) and to implicitly cause certain transformations to be effected, such as padding or sign extension. (I'm not yet sure whether all such operations need to be explicitly rendered as an LLVM “bitcast” operation or not. At least, LLVM's notion of types can be used to define validity of these operations, whether or not they happen implicitly.)

Moreover, addresses (pointers) are typed according to the type of the values they reference (point to). The data types are in this sense higher-order. (This is a weaker case of “higher-order” than types specifying the behaviour of functions. But it has some things in common. I will blog about this more in the future.) These data types control implicitly how much data is read or written by indirect loads and stores.

A typical C front-end will encode C data types directly into this type system. However, this is just a convenience. The encoding discards some of the semantics of the C type system, because in LLVM, composite types are treated purely structurally, whereas in C, they are always treated nominally. Consider this program.

#include <stdlib.h>

struct Foo {
  int a;
  int b;
};

struct Bar {
  int x;
  int y;
};

int main(void)
{
  struct Foo *f = (struct Foo *) malloc(sizeof (struct Foo));
  struct Bar *b = (struct Bar *) malloc(sizeof (struct Bar));

  free(f);
  free(b);

  return 0;
}

In LLVM bitcode, using llvm-gcc, we get the following.

; ModuleID = 'test.o'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-f128:128:128-n8:16:32:64"
target triple = "x86_64-unknown-linux-gnu"

%struct.Bar = type { i32, i32 }
%struct.Foo = type { i32, i32 }

define i32 @main() nounwind {
entry:
  %retval = alloca i32
  %0 = alloca i32
  %f = alloca %struct.Bar*
  %b = alloca %struct.Bar*
  %"alloca point" = bitcast i32 0 to i32
  %1 = call noalias i8* @malloc(i64 8) nounwind
  %2 = bitcast i8* %1 to %struct.Bar*
  store %struct.Bar* %2, %struct.Bar** %f, align 8
  %3 = call noalias i8* @malloc(i64 8) nounwind
  %4 = bitcast i8* %3 to %struct.Bar*
  store %struct.Bar* %4, %struct.Bar** %b, align 8
  %5 = load %struct.Bar** %f, align 8
  %6 = bitcast %struct.Bar* %5 to i8*
  call void @free(i8* %6) nounwind
  %7 = load %struct.Bar** %b, align 8
  %8 = bitcast %struct.Bar* %7 to i8*
  call void @free(i8* %8) nounwind
  store i32 0, i32* %0, align 4
  %9 = load i32* %0, align 4
  store i32 %9, i32* %retval, align 4
  br label %return

return:                                           ; preds = %entry
  %retval1 = load i32* %retval
  ret i32 %retval1
}

declare noalias i8* @malloc(i64) nounwind

declare void @free(i8*) nounwind

Notice that although the compiler has emitted two LLVM type definitions, one for each of our struct types, it then proceeds to use only the first one of them. The second is redundant, because the two are structurally equivalent. This starts to look even more peculiar when we make our data types recursive.

#include <stdlib.h>

struct Foo {
  int a;
  int b;
};

struct Bar {
  int x;
  int y;
};

struct FooRecursive {
  int a;
  struct FooRecursive *next;
};

struct BarRecursive {
  int a;
  struct BarRecursive *next;
};

int main(void)
{
  struct Foo *f = (struct Foo *) malloc(sizeof (struct Foo));
  struct Bar *b = (struct Bar *) malloc(sizeof (struct Bar));

  struct FooRecursive *fr = (struct FooRecursive *) malloc(sizeof (struct FooRecursive));
  struct BarRecursive *br = (struct BarRecursive *) malloc(sizeof (struct BarRecursive));
  
  free(f);
  free(b);
  free(fr);
  free(br);
  
  return 0;
}

This gives us the following.

; ModuleID = 'test.o'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-f128:128:128-n8:16:32:64"
target triple = "x86_64-unknown-linux-gnu"

%struct.Bar = type { i32, i32 }
%struct.BarRecursive = type { i32, %struct.BarRecursive* }
%struct.Foo = type { i32, i32 }
%struct.FooRecursive = type { i32, %struct.BarRecursive* }

define i32 @main() nounwind {
entry:
  %retval = alloca i32
  %0 = alloca i32
  %f = alloca %struct.Bar*
  %b = alloca %struct.Bar*
  %fr = alloca %struct.BarRecursive*
  %br = alloca %struct.BarRecursive*
  %"alloca point" = bitcast i32 0 to i32
  %1 = call noalias i8* @malloc(i64 8) nounwind
  %2 = bitcast i8* %1 to %struct.Bar*
  store %struct.Bar* %2, %struct.Bar** %f, align 8
  %3 = call noalias i8* @malloc(i64 8) nounwind
  %4 = bitcast i8* %3 to %struct.Bar*
  store %struct.Bar* %4, %struct.Bar** %b, align 8
  %5 = call noalias i8* @malloc(i64 16) nounwind
  %6 = bitcast i8* %5 to %struct.BarRecursive*
  store %struct.BarRecursive* %6, %struct.BarRecursive** %fr, align 8
  %7 = call noalias i8* @malloc(i64 16) nounwind
  %8 = bitcast i8* %7 to %struct.BarRecursive*
  store %struct.BarRecursive* %8, %struct.BarRecursive** %br, align 8
  %9 = load %struct.Bar** %f, align 8
  %10 = bitcast %struct.Bar* %9 to i8*
  call void @free(i8* %10) nounwind
  %11 = load %struct.Bar** %b, align 8
  %12 = bitcast %struct.Bar* %11 to i8*
  call void @free(i8* %12) nounwind
  %13 = load %struct.BarRecursive** %fr, align 8
  %14 = bitcast %struct.BarRecursive* %13 to i8*
  call void @free(i8* %14) nounwind
  %15 = load %struct.BarRecursive** %br, align 8
  %16 = bitcast %struct.BarRecursive* %15 to i8*
  call void @free(i8* %16) nounwind
  store i32 0, i32* %0, align 4
  %17 = load i32* %0, align 4
  store i32 %17, i32* %retval, align 4
  br label %return

return:                                           ; preds = %entry
  %retval1 = load i32* %retval
  ret i32 %retval1
}

declare noalias i8* @malloc(i64) nounwind

declare void @free(i8*) nounwind

Notice that the self-referencing structure of FooRecursive has been lost, again because a different type is structurally equivalent.

Now for a final experiment: what about singleton structs? Are they structurally equivalent to a single element? I'll throw in a typedef too, to see whether that appears.

#include <stdlib.h>

struct Foo {
  int a;
};
typedef int Baz;

int main(void)
{
  struct Foo *f = (struct Foo *) malloc(sizeof (struct Foo));
         Baz *b =        (Baz *) malloc(sizeof        (Baz));
  
  free(f);
  free(b);
  
  return 0;
}

Here's the code it generates.

; ModuleID = 'test.o'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-f128:128:128-n8:16:32:64"
target triple = "x86_64-unknown-linux-gnu"

%struct.Foo = type { i32 }

define i32 @main() nounwind {
entry:
  %retval = alloca i32
  %0 = alloca i32
  %f = alloca %struct.Foo*
  %b = alloca i32*
  %"alloca point" = bitcast i32 0 to i32
  %1 = call noalias i8* @malloc(i64 4) nounwind
  %2 = bitcast i8* %1 to %struct.Foo*
  store %struct.Foo* %2, %struct.Foo** %f, align 8
  %3 = call noalias i8* @malloc(i64 4) nounwind
  %4 = bitcast i8* %3 to i32*
  store i32* %4, i32** %b, align 8
  %5 = load %struct.Foo** %f, align 8
  %6 = bitcast %struct.Foo* %5 to i8*
  call void @free(i8* %6) nounwind
  %7 = load i32** %b, align 8
  %8 = bitcast i32* %7 to i8*
  call void @free(i8* %8) nounwind
  store i32 0, i32* %0, align 4
  %9 = load i32* %0, align 4
  store i32 %9, i32* %retval, align 4
  br label %return

return:                                           ; preds = %entry
  %retval1 = load i32* %retval
  ret i32 %retval1
}

declare noalias i8* @malloc(i64) nounwind

declare void @free(i8*) nounwind

Predictably, the typedef has gone away entirely, because it introduces no new structure. However, our singleton struct has stayed around. This isn't surprising either, because LLVM has instructions for accessing field members, whose semantics are affected by these structural differences. Composite types are not just sugar for arrays of bytes or words.

This does mean that if we wanted to encode nominal types into our LLVM bitcode, we could do it by wrapping nominally distinct types in differing depths of layered singleton structs. This would affect the bitcode that came out, e.g. inserting extra GetElementPtr operations, but shouldn't affect the optimised compiler output.

Overall, we can say that LLVM's data types are an annotation useful primarily for propagating and/or inferring data size and encoding information contextually through load and store operations. They are also used for checking: the bitcode is checked for first-order type errors. Since they are raised at the point of pointer use (e.g. a pointer assignment without appropriate bitcast is an error), they can catch likely first-order errors early, i.e. when a pointer is generated or stored, rather than later when it is dereferenced and its target data is misinterpreted. Here by “first-order type errors” I roughly mean those at the machine level, meaning they always concern the misinterpretation of bit-patterns encoding primitive values (integers, addresses, floating-point numbers). Since nominally distinct data types are conflated when they are structurally equivalent, then without using the encoding trick I mentioned, the bitcode will not capture, say, that one variable encodes polar coordinates by x and r, and another by r and theta. Detecting violation of these abstractions is beyond the reach of any analysis based (only) on LLVM data types using the standard encoding.

This includes dynamic analyses. Right now I'm writing an is_a function for KLEE. KLEE is (effectively) a fancy LLVM interpreter. Without recourse to the source code and/or hacking the C front-end, we can only do structural is_a, which is slightly disappointing. I should add that I'm not criticising LLVM here at all. Intermediate representations are not the place for fancy type systems, and the structural approach works nicely. It just means more work for me, when it looked for a moment as though I could abuse pre-existing functionality.