Leading items

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.

Comments (30 posted)

GCC and static analysis

Concurrency tends to make programming hard. Kernel development obviously involves dealing with a lot of concurrency, but there is also a lot of multi-threaded user-space development that suffers from the same issues. It would be nice if the computer could help developers avoid race conditions and other problems that arise in concurrent environments. Some developers at Google have been working on just such a project for some time, but they have just relocated the project from GCC to the LLVM Clang compiler, saying that GCC is not suited to the work they want to do. The result has been a sort of wake-up call for GCC developers. Is the GCC compiler suite not well suited to the creation of static analysis tools?

Like kernel programming, multi-threaded user-space programming involves creating and using locks to prevent concurrent access to shared data. In a properly designed and implemented locking scheme, code will never see inconsistent views of shared data, and that data will not change when the code is not expecting changes. Getting to that point is hard, though, and the bugs that result from locking mistakes can be hard to reproduce and hard to diagnose. There are few things more frustrating than a highly intermittent bug that seemingly makes no sense and defies efforts to track it down.

In 2008, Google developer Le-Chun Wu announced a project to add support for "thread safety annotations" in C and C++ programs to the GCC compiler. Since then, work has progressed to the point that the developers have a useful system that is employed by a number of internal projects. The ideas are relatively straightforward. Shared data requiring a lock is annotated with something like:

    Mutex data_mutex;
    struct shared_data Data GUARDED_BY(data_mutex);

Functions that manipulate locks are annotated with:

    class some_class {
  	Mutex mutex;
	void get_lock() EXCLUSIVE_LOCK_FUNCTION(mutex) { ... }
	void put_lock() UNLOCK_FUNCTION(mutex) { ... }
	/* ... */
    };

There are also annotations for shared locks and "trylock" functions that may not succeed. If a function expects a given lock to be held when it is called, it can be annotated with EXCLUSIVE_LOCKS_REQUIRED(); there is also a LOCKS_EXCLUDED() annotation for functions that will acquire non-nesting locks themselves. Finally, this construction can be used for lock ordering constraints:

    class some_class {
	Mutex m1;
	Mutex m2 ACQUIRED_AFTER(m1);
	/* ... */
    };

Some other annotations exist; they can be seen in this slide deck [PDF], which is where your editor stole the above examples from.

The GCC implementation sets itself up as an early optimization pass. It builds a representation of the code from the GIMPLE internal representation, tracking which locks are held at each point through the function. When problems or inconsistencies are found, the compiler raises the alarm, hopefully causing the problem to be fixed before it gets into production code and bites somebody.

This code is available in a branch in the GCC repository and appears to be useful, so it came as a bit of a surprise when, on April 19, Google developer Diego Novillo announced that the project had been terminated, and that the group was now working to implement the same functionality in the LLVM Clang compiler instead. When asked why the group was making this change, developer Delesley Hutchins responded:

The response added that the GCC implementation has "some issues" that would make it hard to merge into the GCC mainline, while the Clang implementation has been in the trunk all along.

The GCC developers, naturally, would like to understand what it is about their compiler that made this project hard. The Google team was hesitant to respond, seemingly unwilling to criticize GCC or to cause a compiler flame war. Eventually, though, Delesley posted a more detailed description of the kinds of difficulties they had run into. There is a lot of information there, but it seems to come down to two crucial points:

• The GIMPLE representation loses information about the structure of the original program that the static analysis pass really needs to have. LLVM, instead, builds an abstract syntax tree that much more closely matches the original C/C++ syntax; additional structures are then based on that tree. LLVM's tree is evidently well suited to the task of static analysis.

• The GIMPLE representation changes significantly from one compiler release to the next, causing a lot of things to break. That adds a maintenance cost that the Google developers are unwilling to pay - especially if basing on LLVM instead makes that cost go away.

There were other things that were better for their purposes in GCC, but, in the balance, the developers concluded that LLVM is the better platform for their work. They seem determined to make the shift and feel that attempts to fix the problems they encountered in GCC would create difficulties elsewhere in the compiler. So this move appears to be a done deal.

In one sense, this decision lacks serious implications for the free software community. LLVM, too, is free software and the static analysis code will be part of it. That said, it is worrisome if GCC's internal structure truly turns out to be poorly suited to static analysis tasks. There is a lot of interesting work being done in the static analysis area; it offers the prospect of finding large numbers of bugs early in the development process. Static analysis tools will almost certainly be an increasingly important part of many developers' tool boxes. If those tools cannot easily be implemented with GCC, that compiler's future may not be as bright as it otherwise should be.

That said, it is dangerous to extrapolate from one project to the whole field of static analysis tools. The GCC plugin mechanism is just beginning to mature; it really has not had the time to turn into a platform that complex tools can be built on top of. So, while this episode is a warning that the GCC developers should hear (and evidently have heard quite well), it should not be seen as evidence of fatal design flaws. Likely as not, it is just an indication of a problem in need of solution - something the GCC community is good at.

Comments (76 posted)

The return of the Unix wars?

Once upon a time, Unix was the up-and-coming operating system that was the future of computing. But something happened on the way to world domination, and, while Unix was certainly a commercial success for many years, it has mostly been supplanted by other things - including Linux. It has often been said that Linux cannot suffer the same fate that brought down Unix, but it is worth thinking about whether that is really true.

Unix had been growing in popularity for many years before its commercial explosion, but the key to its commercial success was a new wave of low-cost workstations that quickly pushed aside centralized minicomputers. These workstations ran an operating system that was, in many cases, nearly identical to the one found on the larger systems, but they were smaller and cheaper, to the point that they could be deployed on the desktops of individual employees. Several vendors jumped into that market and the related market for storage and compute servers.

The problem is that each of those vendors had its own variety of Unix. All of the Unix variants may have had some sort of common heritage, but, by the time they showed up on deployed systems, they were quite different. Heterogeneous networks of Unix-like systems posed challenges for system administrators, developers, and users alike; each new system type brought its own set of quirks, bugs, and misfeatures to deal with. As the various Unix implementations diverged, they became increasingly obnoxious to deal with. As a result, many groups tried to standardize on a single vendor, hoping that they had chosen the right one.

Either that, or they moved to those cheap new PC systems which, at that time, did not run Unix in any convincing way. But they did run DOS (and, eventually, Windows), and, once you got them running, they were all the same. Packaged software became readily available, and, by the mid 1990's, it became increasingly clear that the desktop systems of the future were not going to run Unix. Discouragingly, almost all of the Unix workstation vendors were making deals with Microsoft and announcing that future workstations (and servers) would run NT instead. It was a dark time.

It is fair to say that Linux saved the world from an all-Windows future that was rapidly approaching. Almost since the beginning, though, critics started to say that Linux would fragment just as badly as Unix did; indeed, they predicted that the situation would be even worse. How could things stay coherent, after all, without a benevolent corporate overlord to keep fragmentation from happening?

But that fragmentation did not happen. Lots of distributions exist, but they have all followed roughly the same course and, for the most part, do not differ by all that much. Efforts like the Linux Standard Base and Filesystem Hierarchy Standard have helped in this area. Arguably, a strong focus on avoiding proprietary drivers and basing every distribution on something close to a mainline kernel has helped even more. Moving from one Linux distribution to another can be mildly disorienting for a brief period, but the administration skills are mostly the same, the software still mostly works, and one comes up to speed relatively quickly. Linux has not suffered the fate of proprietary Unix, or even the fragmentation seen in the current free Unix distributions.

But that situation may be changing. An obvious example is Android which, while being based on a Linux kernel, is hardly recognizable as Linux otherwise. Other mobile distributions—MeeGo, Tizen, webOS, etc.—may differ less from "standard" Linux, but they still don't look much like the desktop on which this article is being written. Enterprise distributions increasingly emphasize their own special features - see Oracle's addition of features like Ksplice and Dtrace, for example.

Most recently, we have seen Ubuntu seemingly determined to diverge from other Linux distributions. In particular, the recent announcement that Ubuntu would not move to systemd has led to some charges that they are fragmenting the Linux ecosystem. Such charges do not ring fully true: remember that upstart was there first and was in use by a number of distributions before those distributions (not Ubuntu) switched to something newer and shinier. But, with developments like Unity, Ubuntu does show signs of wanting to be its own world, increasingly removed from the rest of Linux. It is becoming harder for a user of another distribution to sit down at a Ubuntu system and quickly feel at home.

So one could argue that we are heading into a repeat of the Unix wars. It is noteworthy that the word "Linux" does not appear on the ubuntu.com front page; its absence from android.com, instead, has lost its ability to surprise. Distributions were once promoted as a superior form of Linux; now they are given an identity as a separate operating system altogether. Linux, one could say, is just a set of components that a company grabs to build its own special operating system.

That said, there are a couple of things to keep in mind, starting with the fact that the amount of shared code is still high and likely to remain that way. The notable exception, of course, is Android, but that may well be the exception that proves the rule: only a company with the financial resources of Google can hope to take on responsibility for that much code and hope to maintain it over the long term. For most other companies, the cost of going it alone will simply be too high; economics will tend to place an upper limit on how much divergence we will see. That divergence may grow as projects try to do things that Unix-like systems have never done before, but it can also be expected to shrink as the best solutions win and are adopted by others.

The other relevant point is that the computing environment as a whole is becoming far more diverse. A world that was once made up of "desktops" and "servers" now has a far wider variety of computers, most of which are not marketed as such. It seems natural that the Linux that runs on a traditional desktop will be quite different from the Linux that lives on a phone handset, a television, or a logic analyzer. We are not necessarily seeing destructive fragmentation; instead, we're seeing the flexibility of Linux as it easily adapts to a wide range of uses.

In summary: it is probably too soon to declare that the Unix wars have come to Linux. Every Unix was different because vendors felt the need to differentiate their offerings and lock the customer in. Linux vendors, too, are trying to differentiate, but they are doing so (mostly) with free software, which limits how effective such a strategy can be. If Unity truly ends up taking the world by storm, other distributions can ship it overnight. As long as the software remains free, Linux, as a whole, will be as unified as it needs to be.

Comments (38 posted)

A new editor for LWN

We put out a call for applicants for a job as an LWN editor in January, and were quite surprised by all of the excellent responses we received. It took us a while to narrow the list down, but we eventually got there and we are excited to announce that longtime LWN guest author Nathan Willis has accepted our offer to join the staff.

Not surprisingly, based on the great work he has done for us over the last few years, Nate had the right mix of skills and experience for the job. We look forward to him building on those to help LWN expand its coverage and reach over the coming years. Readers undoubtedly already know about his writing, but we asked him to give us a little biographical background; here's what he had to say:

Nate will be starting on April 27 and will quickly be tossed into the fire with trips to two conferences shortly after he starts. Please join us in welcoming Nate to LWN.

We'd also like to thank all of the folks who took the time and effort to apply for the job. There was a long series of hard decisions, which is part of what took us so long. But the result was a good one, and Nate's help will be important in our efforts to make LWN better.

Comments (14 posted)