LFCS 2012: LLVM and Linux

The LLVM compiler, and its Clang C-family front-end, are getting increasing attention as they mature. At last year's Linux Foundation Collaboration Summit (LFCS), Bryce Lelbach talked about building the kernel with Clang. This year, Mark Charlebois of the Qualcomm Innovation Center (QuIC) picked up where Lelbach left off and, along with his Qualcomm colleague David Kipping, gave a talk at this year's LFCS about LLVM, what its attractions are, and where things stand in building the Linux kernel with Clang.

An introduction to LLVM

Kipping started off with a brief introduction to LLVM, which came from an experiment in compiler construction that Chris Lattner started as part of his PhD. work in 2000. It is a framework for building compilers, rather than a compiler itself. The idea is that components can be assembled into a compiler, and that those components can be reused by other tools. For example, he said, debuggers can use the same parser that the compiler does. But one of the basic premises that underlies LLVM is that no one component is able to serve all of the possible use-cases, so there is no "one true register allocator", no single scheduler, nor a required optimization order in LLVM, he said.

A secondary mission of the LLVM project was to build compilers using the components. "LLVM" is an overloaded term these days, and many use it when they really mean "Clang", Kipping said. LLVM is actually an "umbrella project" with multiple sub-projects.

Clang is the best known of these sub-projects, and is a front-end that supports C, C++, and Objective-C. Clang is known as a fast-to-run compiler, but it is getting slower as more features, optimizations in particular, are added. But it is still a fast compiler, he said. It is designed for conformance with standards and, at least to some extent, compatibility with GCC.

Clang is a strict compiler that is known for the quality of its error messages. It will complain about things that GCC does not, which is part of what led Google to become a "large supporter of LLVM". Google does simultaneous builds of its internal code, using GCC for the code generation and Clang for its static analysis and error/warning messages. By reworking some of the code that Clang was complaining about, Google actually found some "potential problems" in its source code, he said.

Another project under the umbrella is DragonEgg, which is a plug-in that implements a back-end for GCC. That can either provide more GCC compatibility for LLVM code generation or allow one to use GCC language front-ends, like Fortran, that there is no LLVM compiler for. The LLVM debugger (LLDB) is still probably two years away from being ready for production but, because of LLVM's component model, it provides some opportunities for better debugger integration. "Polly" is another area of work for the project. It implements polyhedral optimization, which is an "immature technology" that shows promise for improving the amount of parallelization and vectorization in generated code.

Clang architecture

Clang has a fairly common architecture, with front, middle, and back-ends. It has a "fairly clean" architecture-independent intermediate representation called "Bitcode", though it does have some architecture dependencies, which can cause problems for some back-ends. But, Bitcode can be separated by "space, time, and architecture", so it can be used for code generation at a later time or on a different machine or architecture.

That separability means that Clang can not only be used as a static compiler, but also as JIT compiler. For example, in using Renderscript for Android, developers can package up the Bitcode into the .apk file and the actual code generation is done for the proper target when the app is run for the first time. For example, scalar code would be generated for an ARMv7, but vectorized code would be generated for a Neon core.

LLVM development is "accelerating", Kipping said, with a lot of activity taking place in the last few years. The Android adoption of LLVM for Renderscript in its Honeycomb (3.0) and Qualcomm's contribution of VLIW (very long instruction word) support for LLVM in just the last year or so are some examples he gave of this acceleration. In addition, LLVM is being adopted widely for graphics (e.g. Renderscript, LLVMpipe), parallel programming (e.g. OpenCL), and for things like the Chrome Portable Native Client (PNaCl).

LLVM is also becoming more important in academia. Kipping noted that Lattner gave a keynote speech at the 2012 International Symposium on Code Generation and Optimization, which is one of the most important technical conferences for compiler technology. This year's Proceedings has 103 references to LLVM, which is up from 34 the previous year, he said.

The performance of LLVM's generated code is improving as well. Comparing it to that of GCC, which is the "gold standard today", shows that the LLVM tip is within 1-3% of GCC 4.6 performance for ARM, and within about 4% for x86. The tests need to be re-run for GCC 4.7, he said.

Qualcomm is interested in LLVM because of the "exceedingly complex" nature of ARM system-on-chips (SoCs), with multiple processor cores and multiple graphics pipelines. Code may run on a DSP in one configuration, or on the CPU or GPU in another. The decision on where to run the code may be made based on power saving scenarios. Having a common toolchain that generates code for any of those situations is helpful. In addition, any optimizations that are done in LLVM will be available for multiple code generators, he said.

LLVM is "not there yet" to do complete Linux system builds, Kipping said, which would be a good way to reduce build complexity while getting the advantages of bug fixes and optimizations that have been going into LLVM. Linux is a great source of code that can be used to test and improve LLVM as well. LLVM has a "great community" that is open for participation in various ways including LLVM.org, developer meetings, and conferences. With that, he turned the floor over to Charlebois to talk about LLVM and Linux.

Compiling Linux with Clang

Charlebois began with an explanation of the reasons to build the kernel using Clang. One reason is to get to the point where Clang can be the compiler for the whole system, as Kipping described, and the kernel is a core part of that system. The better diagnostics produced by Clang, which show the actual code where the problem is, are useful, he said. In addition, the kernel uses lots of GCC extensions, which Clang helps find.

The "fix-it" hints that are produced by Clang are very helpful as well because they not only show the problem that produced the warning or error, but also often show how to fix the code. Another area where Clang shines is that it fully expands macros in the diagnostics, which makes it easier to spot problems with macros. Clang has a "still maturing" static analyzer that can show code flow paths. Bringing these kinds of diagnostics to the kernel "will be great", he said.

MINIX has switched to Clang as its default compiler and FreeBSD is working on building its system using Clang. FreeBSD is also using LLVM and KLEE for automatic test generation. LLVM is also being used in graphics applications, like Renderscript for Android and LLVMpipe for Gallium3D. In addition, he noted Sylvestre Ledru's efforts to build Debian with Clang, which LWN also looked at in March.

Most of Charlebois's work on building Linux with Clang focused on cross-compiling for ARM. One of the difficulties he encountered was in finding the right parameters for cross-compilation. The Clang mailing list is very helpful with suggestions, but it is an unsupported configuration and getting all of the flags (e.g. the "triplet") just right can be difficult.

Most of the conversations on the mailing list centered on solving this configuration problem "the right way", which involves a "universal driver" for Clang. That driver would have access to all of the information on the location for the compilers and other tools needed, and users would just point it at a configuration file that specified the target. It's a great idea, he said, but he hasn't seen much movement on it yet.

Another project that he mentioned is ELLCC (Embedded LLVM Compiler Collection), which is a single cross-compiler code base that is based on Clang and LLVM and targets many different architectures (ARM, x86, MIPS, PowerPC, ...). The project has a live web page where you can submit source code, choose a target, and examine the generated code. He said he is "quite impressed" with ELLCC.

Challenges

There are, of course, some challenges building with Clang. Cross-compilation is not a supported configuration, and it is dependent on a GNU cross-toolchain for its assembler and linker. There are lots of warnings produced by Clang which slows down compilation, for example all of the functions that are called (e.g. memcpy()) where the return value is ignored. There are also some bugs in Clang and LLVM for ARM, he said, which he has reported and QuIC has worked on fixing some of them.

The kernel expects to be able to use some GCC behavior that is not supported by Clang. The scripts/Kbuild.include files are GCC-specific, for example. Clang does not have a way to check which options are supported, while GCC does. Clang warns for unused options, but not unsupported ones. In addition, GCC returns false when it it gives an error that there is an unsupported flag, while Clang returns true when it warns about unused flags. There are also "a bunch" of unsupported GCC flags, he said.

There is a master LLVM bug for building the kernel with Clang. The blockers are mostly x86-specific and there are 8-11 of them currently. That bug is a good way to keep track of the status, he said.

The problem with variable-length arrays in structures that Lelbach reported persists. Charlebois patched the kernel to avoid those constructs. It is a non-standard feature of C that is a "GCC-ism", he said. It may come from the fact that GCC supports Ada, so it was probably easy to throw that into C as well.

Explicit register variables are also not supported by Clang, so things like putting the stack pointer into a named variable do not work. In fact, Clang sets the value to null, which doesn't make for a very good stack pointer. Nested functions are also not supported, but they are only present in the Thinkpad driver; since he has been focusing on ARM, he hasn't looked into that.

There are thousands of instances where return values are unused in the kernel, which causes a huge number of warnings when using -Wunused in Clang. It's not desirable to turn off that warning, he said, so he patched around the problem in the kernel. The semantics of the inline keyword for functions is different between GCC's gnu89 and Clang's C99 behavior. There is a gnu89 compatibility flag for Clang, but he has not used it because he wanted to get the kernel to build with Clang's semantics. In addition, EXPORT_SYMBOL() for inline functions makes Clang crash, he said.

There are also missing features or bugs in Clang/LLVM for ARM that he has had to work around. The -mabi-linux flag is not fully supported for Linux. GCC uses four bytes for all enums, while Clang has variable-length enums, which creates incorrect structure offsets, so he doesn't use -mabi-linux in Clang.

64-bit parameter passing requires paired registers in ARM, which is broken in LLVM. There are also problems accessing the upper 32 bits of 64-bit atomic types, which use GCC-specific features to do so in Linux. QuIC has submitted a patch for the first 64-bit problem and is developing one for the second, he said; once they are merged, he can uncomment the affected code in the kernel he is building.

The Clang integrated assembler (IA) is not the default for ARM, because it is still not finished. Finding the right "triplet" for the kernel vs. the one for user-space programs is a problem as "arm-none-linux-gnueabi", for example, works fine for user space, but not for the kernel. Using just "arm" or "armv7" works for the kernel, but gives warnings about not having EABI support. There is also difference in the definition of __kernel_size_t (which is an unsigned long) and size_t (which is defined by Clang to be an unsigned int) which required him to patch the kernel definition to avoid warnings for different argument types for various library functions.

Building

A project has been set up at llvm.linuxfoundation.org that has an automated build framework. It will download the latest LLVM, Clang, QEMU, and the kernel, then patch and build the kernel, and run it in QEMU. It supports the ARM Versatile Express board and Qualcomm's MSM processor, though there is no QEMU target for the MSM, so you can only build for that platform. The Versatile Express boots a 3.3 kernel and runs a toybox user space.

The project site also has Git trees with the patches that he made to the kernel for some of the problems he mentioned earlier. No patches are applied to Clang or LLVM, he said. It is easy to add new architectures to the build framework, and he would love to see people add things like x86, MIPS, and other targets. There is a set of Python tools available to help manage any patches required.

There are still lots of things left to do, of course, and Charlebois wrapped up with his list. First up was to check the status of the problems that Lelbach had reported a year ago. The status of the ARM IA for Clang is also something he needs to look into, as are some of the bugs and problems he mentioned earlier in the talk (inline differences, segment linkage differences, etc.). He would like to build the Linux Test Project with Clang onto a virtual SD card filesystem to use with QEMU and do some regression testing using that. The last item on his list was to set up a test suite for known LLVM bugs so that fixes for those bugs can be detected in newer releases.

It is "pretty exciting" that he can build and run Linux using Clang for one of the ARM architectures, he said. None of the changes that he has made to the kernel stop it from building with GCC, they "just make the kernel less dependent on GCC". He has not tried to merge any of his work upstream, yet, but he hopes that at some point there is interest in making Clang an officially supported compiler for building the kernel. If that happens, he is hopeful that his patches will be helpful in that endeavor.

  static const char* GccVersions[] = {"4.6.1", "4.6.0", "4.6",
                                      "4.5.3", "4.5.2", "4.5.1", "4.5",
                                      "4.4.6", "4.4.5", "4.4.4", "4.4.3", "4.4",
                                      "4.3.4", "4.3.3", "4.3.2", "4.3",
                                      "4.2.4", "4.2.3", "4.2.2", "4.2.1",
                                      "4.2", "4.1.1"};

...

        if (GccTriple == "i386-linux-gnu") {
          // Ubuntu 11.04 uses an unusual path.
          std::string t4 =
              std::string(*it + "lib/i386-linux-gnu/gcc/i686-linux-gnu/") +
              GccVersions[i];
          if (!llvm::sys::fs::exists(t4 + "/crtbegin.o", Exists) && Exists)
            return t4;
        }

...

    else if (!llvm::sys::fs::exists("/usr/lib/gcc/x86_64-redhat-linux",
             Exists) && Exists)
      GccTriple = "x86_64-redhat-linux";
    else if (!llvm::sys::fs::exists("/usr/lib64/gcc/x86_64-suse-linux",
             Exists) && Exists)
      GccTriple = "x86_64-suse-linux";

...

  LinuxDistro Distro = DetectLinuxDistro(Arch);

  if (IsOpenSuse(Distro) || IsUbuntu(Distro)) {
    ExtraOpts.push_back("-z");
    ExtraOpts.push_back("relro");
  }

...

  if (IsDebian(Distro) || IsOpenSuse(Distro) || Distro == UbuntuLucid ||
      Distro == UbuntuJaunty || Distro == UbuntuKarmic)
    ExtraOpts.push_back("--hash-style=both");