Category: llvm

How the Device Images of LLVM OpenMP are Organized?

Starting from this post, I’ll introduce all implementation details that I know about LLVM OpenMP target offloading support, which is what libomptarget does. However, I don’t have a clear plan yet about what will be covered and what the order will be. One thing is clear: since I’m not very familiar with the front end, though I’ve also contributed some patches to clang, I’ll not talk about front end support. Despite this, some high level ideas will also be discussed if necessary.

This post is about how the device images are organized. Without further ado, let’s get started.

The entry point of libomptarget is __tgt_register_lib, whose only argument is of type __tgt_bin_desc *. We will talk about __tgt_bin_desc soon. __tgt_register_lib is defined in libomptarget, but you would not find any explicit function call to it. The call is actually inserted by the tool clang-offload-wrapper provided by clang, which is responsible to wrap the device image into the host object file. As you can probably tell now, the address of device image is not available until we wrap it to the host object file. That’s the reason that we can’t call the function __tgt_register_lib beforehand. We will talk about more details about the compilation flow in the future post.

__tgt_bin_desc stands for “target binary descriptor”, which is defined as:

struct __tgt_bin_desc {
  int32_t NumDeviceImages;
  __tgt_device_image *DeviceImages;
  __tgt_offload_entry *HostEntriesBegin;
 __tgt_offload_entry *HostEntriesEnd;
};

It’s a container of all device images and host entries. We will talk about host entry later. Let’s first discuss device image here. The binary descriptor does support multiple device images, which means you can have one executable for all potential target devices (remember the compilation flag for OpenMP target offloading is -fopenmp-targets and it is “targets“). However, design and implementation sometimes are different. At the time of this writing, I kind of doubt our toolchain can actually support to embed images for different architecture into one executable.

__tgt_device_image describes a device image.

struct __tgt_device_image {
  void *ImageStart;
  void *ImageEnd;
  __tgt_offload_entry *EntriesBegin;
  __tgt_offload_entry *EntriesEnd;
};

The first and second data members point to where the image is stored, which will be loaded to a target device later. EntriesBegin and EntriesEnd point to the offload entry table. In most cases, the EntriesBegin and EntriesEnd are same as HostEntriesBegin and HostEntriesEnd in __tgt_bin_desc respectively, but they can also be a subset. For example, even with the same user code, a target device might need extra code, usually inserted by the compiler, to run properly, like initialization. That’s one of the reasons I doubt we can have multiple images for different architectures, because the offload entry table has to be continuous. If more than one architecture require extra entries, how the table will be organized. It can’t be continuous for every architecture.

Now let’s talk about the offload entry. As its name suggests, it is the entry point for offloading, so it can be a kernel function that can be launched on the host. In addition to that, a global variable (on the device) is also an offload entry. The reason is, most of target devices don’t support global variable initialization. As a result, you cannot just write int a = 1; and hope a is initialized to 1 when the image is loaded to a device. Global variables have to be initialized explicitly by transferring data from host to device. Therefore, we need to know at runtime what global variables are on the device, and what’s their values are. Please note that, like host global variables, they are only initialized once, right after the image is loaded to the device, before the execution of host user code (well, technically, this could be inaccurate. I’m currently working on the JIT support for OpenMP, and we propose a new feature to generate device image at kernel launch time, not global initialization time). Another reason to have global variables as offload entry is for data mapping. Data mapping is a map from host address to device address because we need to pass device address to the corresponding kernel function when we launch it. It’s very complicated and worth a quite long post to discuss the implementation details, but here let me only say a few words about its relation to global variables. Some data mapping could use the information of global variables, so we also need to maintain the mapping for each global variable as well. It can only be done in the following way. After the image is loaded to a device, collect the addresses of all global variables and store that information in the mapping table. So we need the information to tell us what global variables we have.

Another entry points are global constructors (c’tors) and destructors (d’tors). That is for C++ global objects. On the host, the compiler inserts function calls to c’tors of those global variables during the global construction, and function calls to d’tors as well during the global destruction. Same thing happens to device code as well. However, since all current target devices feature a host-centric execution model, which means a device can only execute code if the host “asks” it to, basically to launch it. Those global c’tors and d’tors will not be executed by themselves if we don’t launch them. As a result, we need to know all those functions and their corresponding device handles, and launch them explicitly at the right time.

Now we know what inside the binary descriptor and what they are used for. In next post, I’ll introduce how libomptarget is initialized.

COMDAT in LLVM

I have been working on LLVM heterogenous IR module (see this video for more details) for several days. The first thing I need is to modify the class llvm::Module to make it accommodate multiple modules. Frankly speaking, it was my first time to hear COMDAT when I went through every member data in the class. So I did some research and dig into LLVM source code to learn what it is and how it is used. I’m gonna share my thoughts in this post. Feel free to point it out if something is wrong.

What is COMDAT?

If you search this concept in Google, the first result jumping out should be from StackOverflow (at least in my case).

The purpose of a COMDAT section is to allow “duplicate” sections to be defined in multiple object files. Normally, if the same symbol is defined in multiple object files, the linker will report errors. This can cause problems for some C++ language features, like templates, that may instantiate the same symbols in different cpp files.

COMDAT is actually a section in an object file. It contains symbols that can be potentially with same name in different objects. This could happen when different C++ source files instantiate same template functions. Consider the following example:

// header.hpp
template <typename T>
T add(T a, T b) { return a + b; }
// foo.cpp
#include "header.hpp"
int foo(int a, int b) { return add(a, b); }
// bar.cpp
#include "header.hpp"
int bar(int a, int b) { return add(a, b); }

After we compile foo.cpp and bar.cpp and get foo.o and bar.o, both the two objects contain a symbol named __Z3addIiET_S0_S0_, which is a mangled name. It stands for int add<int>(int, int), which is exactly the instance function of the template function in header.hpp. When the linker links the two objects, if we don’t do something, there will be a linker error because there are two symbols with the same name.

COMDAT is to solve this problem. The symbol __Z3addIiET_S0_S0_ is put into a special section (COMDAT section). Since symbols in an object must have different names, when multiple objects are linked together, only one of those symbols with different names from different COMDAT sections in different objects can be kept. The linker must determine which one to stay. There are a couple of strategies that will be covered in next section.

But wait, why? Shouldn’t they be the same, like the above case, such that we can choose whatever we want? They should work fine because they’re same. Well, that’s true. However, things are not always like that. Consider the following code:

// foo.cpp
template <typename T>
T add(T a, T b) { return a + b; }
int foo(int a, int b) { return add(a, b); }
// bar.cpp
template <typename T>
T add(T a, T b) { return a + b + 2; }
int bar(int a, int b) { return add(a, b); }

Every file has its own template function add, and they work differently. However, they’re all called __Z3addIiET_S0_S0_ in their own objects, without any difference! During the linkage, the linker knows they’re different, but which one to choose? Here comes the strategy. You might be thinking, does it mean either foo or bar will not work correctly after the linkage?! Unfortunately, that’s true. That is how C++ works! That’s why we have millions of articles titled “Best Practice in C++” or “Ten things you should never do in C++”, etc. 🙂

How COMDAT works in LLVM?

Let’s first take a look how llvm::Comdat is defined:

class Comdat {
public:
  enum SelectionKind {
    Any,
    ExactMatch,
    Largest,
    NoDuplicates,
    SameSize,
  };
  Comdat(const Comdat &) = delete;
  Comdat(Comdat &&C);
  SelectionKind getSelectionKind() const;
  void setSelectionKind(SelectionKind Val);
  StringRef getName() const;
private:
  friend class Module;
  Comdat();
  StringMapEntry<Comdat> *Name = nullptr;
  SelectionKind SK = Any;
};

Form simplicity, I only kept meaningful parts. The class is very simple. It only contains two data members, a pointer to StringMapEntry and a SelectionKind. The latter one is pretty straightforward, which defines how to deal with the corresponding symbol. It has five kinds (strategies):

  • Any: The linker can choose whichever it wants when it has multiple symbols with the same name from different objects.
  • ExactMatch: The linker needs to check every instance from different objects whether they’re exact matched. If so, it can choose any of them (obviously). Others will be dropped. If any of them is different from others, a linkage error will be emitted. As for what is exact match, it just means different instances must have same size, same functionalities, etc.
  • Largest: The linker should choose the largest one if multiple instances are of different sizes.
  • NoDuplicates: This symbol should NOT be defined in another object, which means it can only exist in one object. Neither example in the previous section can pass if the COMDAT is this kind.
  • SameSize: The linker needs to check whether the corresponding symbols from different objects are of same size. It is different from ExactMatch because it only requires the same size. It is possible that different symbols can have the same size but different functionalities.

From the class definition, llvm::Comdat is like a property of a symbol. Therefore, each llvm::GlobalObject holds a pointer to a llvm::Comdat. The llvm::Module contains a mapping from a symbol name to its corresponding llvm::Comdat, and llvm::Comdats are actually stored in the map. For efficient look-up, llvm::Comdat contains a pointer to its corresponding entry in the map. It has three advantages:

  • The owner of the llvm::Comdat is the map (part of the llvm::Module) not a symbol. In this way, all COMDATs for a single module are in a same place. We can easily traverse all COMDATs if necessary.
  • A symbol only needs to hold a pointer to its llvm::Comdat without taking care of its lifetime.
  • The symbol name can be easily got via the pointer to the entry.

Every time we need to check whether a symbol is in the COMDAT section, we can either use function llvm::GlobalObject::hasComdat()or check whether the return value of llvm::GlobalObject::getComdat() is nullptr.