I participated in GSoC 2019 and worked on improving LLVM support within the Chapel compiler. This post discusses 3 tasks I undertook: adding llvm.lifetime.start and llvm.lifetime.end intrinsics, improving debugger support, and limiting C code generation when using the LLVM backend.

Table of Contents

• 1. Introduction
  • 1.1 What is Google Summer of Code?
  • 1.2 What is Chapel?
  • 1.3 My prior knowledge of compilers
• 2. The Project
  • 2.1 Background knowledge
    • 2.1.1 What is LLVM and what are LLVM intrinsics?
    • 2.1.2 What are the llvm.lifetime.start and llvm.lifetime.end intrinsics?
  • 2.2 Implementing llvm.lifetime.start and llvm.lifetime.end intrinsics
    • 2.2.1 Method 1: Call llvm.lifetime.end at the end of the dynamic scope
    • 2.2.2 Method 2: Call llvm.lifetime.end at end of the static scope
  • 2.3 Improving LLVM debug info generation
    • 2.3.1 Implementing llvm.dbg.declare intrinsic for variables
  • 2.4 Streamlining C code generation when using LLVM
• 3. Conclusion

From May 27th to August 26th, I worked on the Chapel Parallel Programming Language as a Google Summer of Code (often just referred to as GSoC) student. It was an amazing experience working on an actual compiler and this is a rundown of my journey.

Google Summer of Code is an annual programme for University students organised under the umbrella of Google Open Source Programs that gives them a platform to introduce themselves to open source and contribute to a project of their interest for a period of 3 months. The students can submit up to 3 proposals to one or more organisations. These open source organisations are chosen by Google before the student proposal submissions begin. The organisations then select student projects from the list of proposals they receive. Selected students work on their respective projects with the guidance and help from mentors belonging to the organisation(s) for a period of 3 months usually from May until August.

The official Chapel website states the following

Chapel is a programming language designed for productive parallel computing on large-scale systems. Chapel’s design and implementation have been undertaken with portability in mind, permitting Chapel to run on multicore desktops and laptops, commodity clusters, and the cloud, in addition to the high-end supercomputers for which it was designed. Chapel’s design and development are being led by Cray Inc. in collaboration with contributors from academia, computing centers, industry, and the open-source community.

You can learn more about it here.

The “Hello World” program looks like the following in Chapel

writeln("Hello, world!");

The Chapel compiler is named chpl (just like the extension for Chapel source code files) and can be executed as follows

$ chpl hello.chpl

Before working on the Chapel compiler during GSoC, I had no professional nor open source experience working on a real world compiler. Back when I was in grade 9, I had attempted to write a LOGO interpreter for the younger students of my high school. After this, my first technical introduction to compilers was only in 2nd year of University. I had always been interested in compilers and slowly started to look into the LLVM suite of compiler tools. It was only then that I understood my natural interest in this field and so I decided to work on a compiler project for GSoC.

Now that I have given you a little bit of background, let us dive right into the technical details of my work.

Currently, the Chapel compiler has 2 modes or backends - the default C backend that transpiles Chapel code to C code and the LLVM backend that generates LLVM IR. My project was to work on the Chapel LLVM backend and add features to improve support via better LLVM IR intrinsics among other improvements as we move towards making the LLVM backend as the default.

There is some amount of background knowledge that I am going to presume you have as I proceed forward with the blogpost. The following is some primer on concepts I will talking about.

The most straight forward way to describe LLVM (Low-Level Virtual Machine) is that it is a suite of compiler tools that let you define and implement compiler frontends and backends. For instance, mainstream languages like Swift and Rust have frontends to the LLVM IR. LLVM IR stands for LLVM Intermediate Representation. Think of it as LLVM’s own version of Assembly Language. Things like Kotlin Native are made possible due to the LLVM IR. You can also extend LLVM with a custom backend for a new processor architecture like the RISC-V. However, LLVM is much more than just this. It is a combination of many tools and libraries that are useful not only for compiler designing and implementation but also for formatting code and debugging, for instance.

So now that we have a basic idea of what LLVM is mainly used for, let us understand what LLVM intrinsics are. LLVM intrinsics are funtions built into a compiler, generated at the optimisation stage of LLVM IR generation and always begin with the llvm. prefix. The compiler knows best how to implement a particular intrinsic function depending on the backend being used (x86-64, ARM etc.). If you are analysing a program’s generated LLVM IR, you can see these intrinsics in the form of function calls like call void @llvm.va_start(...) or call @llvm.memcpy.p0i8.p0i8.i32(...) (a standard C library intrinsic for the memcpy C function).

There are multiple classes of LLVM intrinsics and one of them is labelled as “Memory Use Markers”. The LLVM Language Reference describes them as

This class of intrinsics provides information about the lifetime of memory objects and ranges where variables are immutable.

The very first two intrinsic functions mentioned under this class of intrinsics are llvm.lifetime.start and llvm.lifetime.end. Their function signatures are as follows

void @llvm.lifetime.start(i64 <size>, i8* nocapture <ptr>)
void @llvm.lifetime.end(i64 <size>, i8* nocapture <ptr>)

Intuitively speaking, the naming of these two intrinsics suggest that llvm.lifetime.start is called to indicate that the value of a particular memory pointed to by ptr is never used before and that llvm.lifetime.end is called to indicate that the value pointed to by ptr is no longer used after that. Indeed, this is how these intrinsics work. Speaking in terms of a high-level programming language, the compiler calls llvm.lifetime.start right after a particular variable is instantiated and it calls llvm.lifetime.end right before the end of scope (at the end of a non-returning function body or right before a return statement, for instance).

For an optimising compiler, it is very important to manage memory in a meaningful way. LLVM employs memory markers for this purpose using intrinsics such as llvm.lifetime.start and llvm.lifetime.end.

One of the major tasks for me this summer was to implement these two intrinsics in the Chapel compiler. Since this was dealing with memory, my mentor had already warned me about possible memory corruption issues. Since this was my first time working with LLVM IR, I had to pay extra attention on not only implementing these two intrinsics on the generated IR, but also learning about how the Chapel compiler worked.

Since a previous GSoC student had already implemented the llvm.invariant.start intrinsic, my first step was to check out that piece of code and understand how the Chapel compiler’s internals were used to implement it. llvm.invariant.start is another memory use marker intrinsic used by LLVM. After having a look at that implementation, my first step was to write functions for generating the intrinsics given an llvm::Value (representing the address of a variable) and llvm::Type (the type of a variable). A rough pseudocode resembling the actual implementation in the compiler would look something like the following

codegenLifetimeStart(addr, type) {
    Let s be the calculated size in bytes using information from type
    Call IRBuilder::CreateLifetimeStart(addr, s)
}

Similarly, we can write a function for codegenLifetimeEnd by calling IRBuilder::CreateLifetimeEnd(addr, s).

In order to be able to emit llvm.lifetime.end, my mentor helped me by creating a std::vector of all variables in the current stack for which we had emitted a corresponding llvm.lifetime.start intrinsic for. The implementation of calling the llvm.lifetime.start intrinsic was quite straight forward - right when a local variable was declared, emit the intrinsic. The rough pseudocode would be

codegenVariables() {
    For all variables in current scope:
        Generate LLVM alloca instruction for variable
        Call codegenLifetimeStart(addr, type)
        Add variable information to vector of current stack variables
        ...
}

While implementing the llvm.lifetime.end intrinsic, we decided upon two ways of accomplishing it.

2.2.1 Method 1: Call llvm.lifetime.end at the end of the dynamic scope

Our initial idea was to call this intrinsic every time a variable was no longer used. A rough idea of how this implementation would look like in a piece of Chapel code would be

proc someProcedure() {
    var x: int(32) = 0
    // call llvm.lifetime.start for x in the generated IR
    readln(x);
    if x < 42 {
        return 1;
        // call llvm.lifetime.end for x in the generated IR
    } else if x == 42 {
        return 2;
        // call llvm.lifetime.end for x in the generated IR
    }
    return x;
    // call llvm.lifetime.end for x in the generated IR
}

This is how Swift generates this intrinsic in its LLVM IR.

Chapel currently officially supports LLVM 8 and while this approach seemed the right way to do it, I ended up with some serious memory corruption issues. Interestingly, the error went away with LLVM’s master branch (LLVM 9.0) but seemed to come back yet again after some other changes. I was unable to properly debug the issue and it ended up taking more than two weeks of time for me to finally give up. After serious reconsideration with my mentors, we instead decided to follow the next method of implementation even though we would have preferred this one.

2.2.2 Method 2: Call llvm.lifetime.end at the end of the static scope

This method made is pretty straight forward since we already had all the variables that we had generated a llvm.lifetime.start for. The implementation looked roughly like the following

codegenFunction() {
    Call codegenVariables()
    ...
    For all variables in vector of current stack variables:
        Call codegenLifetimeEnd(addr, type)
    Clear vector of current stack variables
    ...
}

Although this method works fine, we still are unsure why the previous method did not work with LLVM 8. If you have faced a similar issue with the llvm.lifetime.end intrinsic, please get in touch with me!

Everyone who has used GDB or LLDB in their programming career knows how important debugging is. And so it is equally important for a programming language to enable its users to debug their code. Thankfully, there are standard debug information formats to enable debuggers. One of them is the DWARF Debug Information Format. It is a standardised format that is picked up by debuggers like GDB for source level debugging. LLVM supports the emission of debug information using the DWARF format, thereby allowing frontends built on top of LLVM to also support debugging their code with traditional debuggers.

Chapel’s LLVM implementation has a good preliminary debug info generation support and generates useful DWARF information such as the source code file name, its path, information about variables, functions and global constants, to name a few.

2.3.1 Implementing llvm.dbg.declare intrinsic for variables

As with the normal intrinsic functions, LLVM uses certain other debug intrinsic functions in its IR to track local variables through optimisation and code generation.

One of them is llvm.dbg.declare with the function signature as follows

void @llvm.dbg.declare(metadata, metadata, metadata)

Speaking in simple terms, this intrinsic can be called right after a local variable is allocated/instantiated to indicate useful information like the line number of the variable in the original source code file.

The implementation of this intrinsic in the Chapel compiler was very simple, thanks to its well structured codebase. Remember the codegenVariables() method we talked about earlier? By adding support for the llvm.dbg.declare intrinsic, it would now look something like

codegenVariables() {
    For all variables in current scope:
        Generate LLVM alloca instruction for variable
        Call codegenLifetimeStart(addr, type)
        Add variable information to vector of current stack variables
        if (needDebugInfo) { // !!! this if block is new !!!
            Call codegenDbgDeclare()
        }
        ...
}

There are still some issues to resolve before debugging a Chapel program with the --llvm -g flags becomes satisfying.

As mentioned earlier, the Chapel compiler currently supports 2 modes (or backends) - the default C backend that transpiles Chapel code to C code and the LLVM backend that generates LLVM IR. The LLVM backend is still not complete and as such still depends on C code generation for some parts. This means that while we would generate LLVM IR for our AST, some peripheral tasks like linking still depends on functions and classes that are generated by our C backend. However, we want to reduce this dependence on C code when using LLVM to compile Chapel code. I got to work on a small part of this task.

Every compiled Chapel program contains information about the general environment including the compiler command, the compiler version, the target architecture and a lot of other useful information. This information can be viewed using the -a flag when executing a compiled Chapel executable file. The generated information can look something like

$ ./hello -a
Compilation command: chpl hello.chpl
Chapel compiler version: 1.20.0 pre-release (81bf032380)
Chapel environment:
  CHPL_HOME: /home/git/chapel
  CHPL_ATOMICS: cstdlib
  CHPL_AUX_FILESYS: none
  CHPL_COMM: none
  CHPL_COMM_SUBSTRATE: none
  CHPL_COMPILER_SUBDIR: linux64/gnu/x86_64/llvm-llvm

The C backend generates this information in the form of a large (200+ lines of code) C file named chpl_compilation_config.c that contains a function named chpl_program_about() that holds all this information among other declarations and definitions. Previously, the LLVM backend also depended on this C file for this information.

We found that since the C file constitutes simple functions, variable definitions and structs, this dependence on C code can be completely removed for the LLVM backend by incorporating all of that information into the generated LLVM IR. This was a very trivial but interesting code change. With this change in place, we not do not generate chpl_compilation_config.c at all when using the LLVM backend. It seemed like a small step but in the bigger picture of our migration to a default LLVM backend, this was a viable and important change nonetheless.

Working on Chapel during GSoC has been an amazing and enriching experience for me, to say the least. I now have proper hands on experience with working on a compiler. I am very thankful to my mentors Michael Ferguson and Przemysław Leśniak for helping me throughout the programme timeline, and to all the Chapel developers who helped me on the Gitter channel. I would also like to thank the Google Open Source Programs Office for giving thousands of students like me a chance to work on real world projects like Chapel every year.

This doesn’t conclude my journey with Chapel as I plan to keep contributing to the codebase in the near future.

Thank you!