One of the UIUC researchers was assigned to add threading support to LLVM. I
forget who, but it has been thought about/started. In any event, there's nothing
stopping someone from using a library like pthreads today. Its possible to make
a multi-threaded application with LLVM, we just don't support it natively in LLVM.

Adding this to the LLVM JIT would be really trivial, it's just that noone has
started looking into it. All it would take is putting mutexes (defined in
"Support/ThreadSupport.h", around the critical JIT data structures.

Noone has started looking at this, but if you're interested, it would be a
really easy (and useful) LLVM enhancement.

-Chris

First attempt at adding locks to the JIT

I've made a first attempt at adding locking to the JIT. Unfortunately, since I do not really understand the
structure of LLVM, I could have very easily screwed something up. In other words, this definitely needs
review. I touched two classes, the JIT and the ExecutionEngine. I need some help from someone who is
more familiar with the code to make sure that I have protected the correct data structures. I'm also
looking for suggestion about how to test this for correctness.

To make sure that I added locks where required, I moved "dangerous" members of the classes into a
new class, called JITState and ExecutionEngineState, respectively. These classes only allow access to the
variables if a lock is held. This allows the compiler to verify that locks are held in the correct places,
although there could still easily be bugs if the locks are released too early. The data structures that are
protected are:

ExecutionEngine:
std::map<const GlobalValue*, void *> GlobalAddressMap; // R/W data structure
std::map<void , const GlobalValue> GlobalAddressReverseMap; // R/W data structure

JIT:
std::vector<const GlobalVariable*> PendingGlobals; // R/W data structure
FunctionPassManager PM; // Could call passes which are not thread safe

Both of these classes have additional members which I have not protected. It looked to my brief
analysis that they were used in a read-only fashion. Can anyone tell me if I am wrong:

ExecutionEngine:
Module &CurMod;
const TargetData *TD;

JIT:
TargetMachine &TM;
TargetJITInfo &TJI;
MachineCodeEmitter *MCE;

I specifically did not protect the ExecutionEngine::CurMod member because a reference is returned via
ExecutionEngine::getModule(). If access to it must be serialized, it must be done very carefully. I tried to
make getModule return a constant reference, but that quickly led me into deep trouble in the world of
const correctness.

I've attached my patch against the latest CVS. There is one "trivial" fix which should be committed, even
if this patch is incorrect. In ThreadSupport.h, the include guard macro needs to have "LLVM_" prefixed
to it. The ThreadSupport-PThread.h and ThreadSupport-NoSupport.h files look for the macro with this
prefix.

Overall, the patch looks very good. Here are a couple of suggestions:

1. Please pull the unrelated bits and pieces (e.g.
   s/SUPPORT_THREADSUPPORT_H/LLVM_SUPPORT_THREADSUPPORT_H and the iterator -> const
   iterator changes) into a seperate patch. These changes are "obvious" and can be
   applied immediately.

2. I like your use of methods like "getPM" to force the client to demonstrate
   that they own the lock. Very nice idiom. However, it would be nice to change
   the JIT ctor to look something like this:

MutexLocker locked(lock);
PassManager &PM = state.getPM(locked);

instead of using getPM multiple times.

3. I'm not sure that the pthreads implementation of the mutex class is right,
   can you take a look? In particular, the ctor looks like this
   (include/llvm/Support/ThreadSupport-PThreads.h):

   Mutex() {
   pthread_mutexattr_t Attr;
   pthread_mutex_init(&mutex, &Attr);
   }

It seems like pthread_mutexattr_init should be used, or
PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP should be used. Note that we do want a
recursive mutex here.

I think your patch is correct. To test it, the first thing you want to do is
make sure that no non-threaded programs are broken. If you use the llvm-test
suite, you can pick a subdirectory (e.g. MultiSource/Benchmarks/Olden) type
'make' and it will test all of the programs in that subdir.

For the threaded case, it's more difficult. You can try writing programs that
would cause multiple functions to be JIT'd at the same time, for example, but
I'm not sure the best way to ensure the bad behavior would happen...

If you take care of the above and attach both patches (the trivial stuff and
non-trivial stuff patches), I would be happy to apply them for you. :)

Thanks a lot!

-Chris

Trivial fixes from the thread patch
I've split out the trival changes from my previous patch, while I resolve the
other comments that were made about it.

ThreadSupport-PThreads.h: Use recursive mutexes
I've added a patch that correctly initializes the mutexes as a recursive mutex
for the pthreads implementation. The patch also adds assertions to verify that
each pthread function call succeeded.

Both patches look great, and are applied:
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050221/024322.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050221/024323.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050221/024324.html

Thanks!

-Chris

Updated JIT thread support patch

I have finally ran the test suite, and created an example that actually calls into the JIT from multiple
threads. These all seem to work. I've attached the current version of my patch. Would you also like me
to include my example program somehow? I could attempt to reformat it as a test, although the only
thing that it could verify is that the program runs and generates the expected result.

This bug depends on configure and Makefile support to add "-lpthreads" to the linker command line for
all LLVM based tools. Without this change, the tools will fail to link on Linux. This bug depends on my
enhancement request for this feature.

Updated JIT thread support patch
I found a bug with the original patch, as noted in the following mailing list
post. Thus, the patch is obsolete:

http://mail.cs.uiuc.edu/pipermail/llvmdev/2005-April/003809.html

Makes the JIT thread-safe
I've attached the latest version of my thread patch. This is against the latest
CVS, as of today. The differences from the previous version are as follows:

1. Fixes a bug that I found while using LLVM, by adding locks to the
   JITResolver class.
2. Adds a "holds" method to the MutexLocker class that can be used to verify
   that the correct Mutex is being held.

I ran the regression tests on Linux and it did not break anything on my
machine.

Let's review this again after 1.5 is released.

Mine

I have applied Evan's patch in my own tree and determined that it does not, at
least, cause any harm. Whether it actually keeps the JIT thread-safe, I don't
know since there aren't any multi-threaded programs in llvm-test. However, all
the llvm-test tests pass with the patch applied.

Unfortunately, this patch causes lli to require linking with libpthread.a which
I'm not sure everyone wants. Furthermore, I think this will render lli as a
"unix only" tool because I doubt we want threading done with libpthread on Win32
even if it was available. I don't particularly care so I'm happy to commit the
patch, but others might object.

Anyone want to chime in on this?

There is no libpthread in VC++. It won't even compile, much less link. Win32
sychronization primitives, probably critical sections, must be used. Suggest
that these be added to lib/System.

My patch doesn't directly depend on libpthread, so it would be very possible to add Win32 support by
creating a Win32 version of the libSystem lock classes, and hacking the build system to select the
appropriate macros and linker flags. I would make a Win32 version of this class myself, except that I
don't have easy access to a Windows machine with Visual Studio, nor do I know Win32's synchronization
primitives.

As for threaded test programs, I have a couple that I used to test the patch myself that I could provide.
However, there is a similar issue there: the test program needs a way to spawn threads and perform
synchronization. I just wrote my tests to be Linux specific, but to be included as part of LLVM's test
suite they would need to be made cross platform.

Evan, could you please add your threaded test programs to
llvm-test/SingleSource/UnitTests, please? They need to be public domain or very
lax open source licensed (e.g. BSD like). If you're in doubt, just attach them
to this bug and I'll take care of it.

Resolved via Evans patch and these patches:

http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027019.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027020.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027021.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027022.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027023.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027024.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027025.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050711/027026.html

Don't forget to update the release notes:

1. Mention the new feature
2. Remove the 'known problem' that says the JIT is not thread safe.

Thanks!

-Chris

Parallel JIT test
Great work! Thanks for committing this.

I apologize: I'm not working with LLVM at the moment, and I don't really have
time to go update my installation in order to be able to make a clean patch
against llvm-test. I'm going to do the lazy thing and take you up on your
offer: I've attached my test to this bug. This test doesn't use LLVM's
indentation style, and is a little bit of a hack of a couple of the LLVM
examples. Here is the description from the top of the file:

This test program creates two LLVM functions then calls them from three
separate threads.
It requires the pthreads library.

The three threads are created and then block waiting on a condition variable.
Once all threads are blocked on the conditional variable, the main thread
wakes them up. This complicated work is performed so that all three threads
call into the JIT at the same time (or the best possible approximation of the
same time). This test had assertion errors until I got the locking right.

This code can be licenced under whatever licence you choose. Technically, it is
a derivative of the examples in llvm/examples directory.

mentioned in issue llvm/llvm-bugzilla-archive#540