Understanding how memory allocation works (LLVM)

Question

I'm making progress on a toy compiler (first time), and trying to understand how to allocate/construct an LLVM struct type. The Kaleidoscope tutorial doesn't include or even mention this and I don't know what I'm looking for in the LLVM source/tests to find possible examples.

So I've written a simply C++ example, dumped the IR with clang in an effort to try to understand what it produces but to be honest I don't follow it all. The things obvious to me are the function definition/declarations and some function calls and a memset call so I get pieces of it but it doesn't all come together for me yet. (P.S my interpretation of the alloca instruction docs is that it anything created from that gets freed on return so I can't use that right, it's essentially only for local variables?)

What I've done is:

alloc.cpp

struct Alloc {
  int age;
};

//Alloc allocCpy() {
//  return *new Alloc();
//}

Alloc *allocPtr() {
  return new Alloc();
}

int main() {
  Alloc *ptr = allocPtr();
//  ptr->name = "Courtney";
//  Alloc cpy = allocCpy();
//  cpy.name = "Robinson";
//  std::cout << ptr->name << std::endl;
//  std::cout << cpy.name << std::endl;
  return 0;
}

Then run clang -S -emit-llvm alloc.cpp to produce alloc.ll

; ModuleID = 'alloc.cpp'
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.11.0"

%struct.Alloc = type { i32 }

; Function Attrs: ssp uwtable
define %struct.Alloc* @_Z8allocPtrv() #0 {
entry:
  %call = call noalias i8* @_Znwm(i64 4) #3
  %0 = bitcast i8* %call to %struct.Alloc*
  %1 = bitcast %struct.Alloc* %0 to i8*
  call void @llvm.memset.p0i8.i64(i8* %1, i8 0, i64 4, i32 4, i1 false)
  ret %struct.Alloc* %0
}

; Function Attrs: nobuiltin
declare noalias i8* @_Znwm(i64) #1

; Function Attrs: nounwind
declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) #2

; Function Attrs: ssp uwtable
define i32 @main() #0 {
entry:
  %retval = alloca i32, align 4
  %ptr = alloca %struct.Alloc*, align 8
  store i32 0, i32* %retval
  %call = call %struct.Alloc* @_Z8allocPtrv()
  store %struct.Alloc* %call, %struct.Alloc** %ptr, align 8
  ret i32 0
}

attributes #0 = { ssp uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="core2" "target-features"="+cx16,+sse,+sse2,+sse3,+ssse3" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { nobuiltin "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="core2" "target-features"="+cx16,+sse,+sse2,+sse3,+ssse3" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #2 = { nounwind }
attributes #3 = { builtin }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 3.7.0 (tags/RELEASE_370/final)"}

Can someone explain what's happening in this IR and how it maps back to the C++? Or ignoring this specific example how one would/should go about allocating heap memory for an LLVM StructType that out lives the function within which it was created (and if you're feeling generous, how to later release the memory).

The bits I've commented out are from my original example but being a total novice the IR from that was even less insightful...

Answer 1

my interpretation of the alloca instruction docs is that it anything created from that gets freed on return so I can't use that right, it's essentially only for local variables?

Yes. Furthermore, the current advice on LLVM IR is that although alloca works as you expect it to, optimizations are another case. They advise that you alloca all of your locals in the entry block right away, even if you don't allow the user access to them or they don't always contain meaningful data.

Heap allocation is a library feature. It is not a feature of LLVM or the compiler. When you use new T(), the compiler simply calls operator new to get the memory and then constructs T there. There is no magic involved. Most of the junk that you see there is C++-ABI specific rather than any requirement of LLVM. It eventually lowers into something like void* p = malloc(size); new(p) T();. For pretty much all types T, this pretty much boils down to a series of stores into p or calling a user-defined function.

You can use the memory allocation function from the runtime library of your choice.

trying to understand how to allocate/construct an LLVM struct type

The LLVM type system does not include the notion of construction. That is a notion of the source language.

As far as LLVM is concerned, a struct is just a bunch of bits, and all memory locations are more-or-less the same. If you want the bits to be a particular thing, then store the bits you want to that location. If you want to put the bits on the heap, then call a runtime library heap allocation function and store the bits into that location.

Note that garbage collection, however, is a somewhat different story, as there is some awkward stuff going on w.r.t. finding locals on the stack for marking.

For the record, you will not get far trying to understand Clang's LLVM IR. I've been doing that for several years now and it is batshit crazy and will take you that long to start to get a grip, not to mention full of C++-specific ABI details that you don't want to know about. You will get a lot further asking in #llvm in their IRC channel or asking specific questions here than in trying to reverse-engineer that.

Answer 2

I don't recommend looking at unoptimized IR emitted by Clang - it's way too verbose. -O1 makes it a lot more readable - here's the -O1 version with comments annotating the lines (also I've reordered two lines to make it slightly more readable):

%struct.Alloc = type { i32 }                   ; Define the Alloc type.

define noalias %struct.Alloc* @_Z8allocPtrv() #0 {
  %1 = tail call noalias i8* @_Znwj(i32 4) #2  ; Call _Znwj(4). This retuns i8*.
  %3 = bitcast i8* %1 to i32*                  ; Cast the returned value to i32* (int*)...
  store i32 0, i32* %3, align 4                ; ...and zero its content.
  %2 = bitcast i8* %1 to %struct.Alloc*        ; Cast the returned value to Alloc*...
  ret %struct.Alloc* %2                        ; ...and return it.
}

; Declare the _Znwj function. This doesn't need to be defined since it's already defined
; in libstdc++: this is 'operator new'. You can see this by passing this string through a
; C++ demangler, for example the one at http://demangler.com/.
declare noalias i8* @_Znwj(i32) #1

define i32 @main() #0 {
  %1 = tail call %struct.Alloc* @_Z8allocPtrv()  ; Call _Z8allocPtrv (Defined above).
  ret i32 0
}

This is a new call, not a local allocation, so it will not be cleared when leaving @_Z8allocPtrv. Local allocations are indeed performed in LLVM IR with the alloca instruction, and not a new call.

If you're curious how new works, I believe its standard implementation uses malloc, which is translated by the compiler that compiled the library to some function that includes system call(s).