Subzero: Add locking to prepare for multithreaded translation.

src/IceGlobalContext.h

 //===- subzero/src/IceGlobalContext.h - Global context defs -----*- C++ -*-===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file declares aspects of the compilation that persist across
 // multiple functions.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SUBZERO_SRC_ICEGLOBALCONTEXT_H
 #define SUBZERO_SRC_ICEGLOBALCONTEXT_H
 
 #include <memory>
+#include <mutex>
 
 #include "IceDefs.h"
 #include "IceClFlags.h"
 #include "IceIntrinsics.h"
 #include "IceRNG.h"
 #include "IceTimerTree.h"
 #include "IceTypes.h"
 
 namespace Ice {
 
 class ClFlags;
+class ConstantPool;
 class FuncSigType;
 
-// This class collects rudimentary statistics during translation.
-class CodeStats {
-  CodeStats(const CodeStats &) = delete;
-  CodeStats &operator=(const CodeStats &) = default;
+typedef std::mutex GlobalLockType;
+
+// LockedPtr is a way to provide automatically locked access to some
+// object.
+template <typename T> class LockedPtr {
+  LockedPtr() = delete;
+
+  // This inner class holds the actual payload.  The outer class adds
+  // the unique_ptr and provides a more convenient -> operator.
+  class LockedPtrWrapper {
+    LockedPtrWrapper() = delete;
+
+  public:
+    LockedPtrWrapper(T *Value, GlobalLockType &Lock) : Value(Value), Lock(Lock) {
+      Lock.lock();
+    }
+    ~LockedPtrWrapper() { Lock.unlock(); }
+    T *operator->() const { return Value; }
+    T *operator*() const { return Value; }
+
+  private:
+    T *const Value;
+    GlobalLockType &Lock;
+  };
 
 public:

[JF, 2015/01/18 03:14:19]

This is already public.

[Jim Stichnoth, 2015/01/20 16:22:54]

I don't think so -- the only thing public above was the public portion of the
private inner class.  It's moot though since I redid LockedPtr.

-  CodeStats()
-      : InstructionsEmitted(0), RegistersSaved(0), FrameBytes(0), Spills(0),
-        Fills(0) {}
-  void reset() { *this = CodeStats(); }
-  void updateEmitted(uint32_t InstCount) { InstructionsEmitted += InstCount; }
-  void updateRegistersSaved(uint32_t Num) { RegistersSaved += Num; }
-  void updateFrameBytes(uint32_t Bytes) { FrameBytes += Bytes; }
-  void updateSpills() { ++Spills; }
-  void updateFills() { ++Fills; }
-  void dump(const IceString &Name, Ostream &Str);
+  LockedPtr(T *Value, GlobalLockType &Lock) : Ptr(new LockedPtrWrapper(Value, Lock)) {}

[JF, 2015/01/18 03:14:19]

The allocation here is pretty unfortunate. You want the move and unique
ownership semantics of unique_ptr, but without the extra allocation (you want
unique_ptr to contain the LockedPtrWrapper itself, not a pointer to one).

I think you can use unique_ptr's Deleter class template argument to only call
Ptr.~LockedPtrWrapper? If not it's probably better to replicate unique_ptr's
semantics (move constructible, move assignable, not copy constructible, not copy
assignable) but containing the value/lock pair instead of a pointer.

[Jim Stichnoth, 2015/01/19 21:44:05]

Yeah, I think trying to use unique_ptr without an actual pointer may be
overkill.  We only want to lock the resource for a lexically scoped region,
never stashing it away or transferring its ownership.

How about this updated version of LockedPtr?  (I think I do not want move
assignment enabled.)

[JF, 2015/01/20 01:23:04]

Much better.

+  LockedPtrWrapper &operator->() const { return *(Ptr.get()); }
+  LockedPtrWrapper &operator*() const { return *(Ptr.get()); }
 
 private:
-  uint32_t InstructionsEmitted;
-  uint32_t RegistersSaved;
-  uint32_t FrameBytes;
-  uint32_t Spills;
-  uint32_t Fills;
+  std::unique_ptr<LockedPtrWrapper> Ptr;
 };
 
-// TODO: Accesses to all non-const fields of GlobalContext need to
-// be synchronized, especially the constant pool, the allocator, and
-// the output streams.
 class GlobalContext {
   GlobalContext(const GlobalContext &) = delete;
   GlobalContext &operator=(const GlobalContext &) = delete;
 
+  // CodeStats collects rudimentary statistics during translation.
+  class CodeStats {
+    CodeStats(const CodeStats &) = delete;
+    CodeStats &operator=(const CodeStats &) = default;
+
+  public:
+    CodeStats()
+        : InstructionsEmitted(0), RegistersSaved(0), FrameBytes(0), Spills(0),
+          Fills(0) {}
+    void reset() { *this = CodeStats(); }
+    void updateEmitted(uint32_t InstCount) { InstructionsEmitted += InstCount; }
+    void updateRegistersSaved(uint32_t Num) { RegistersSaved += Num; }
+    void updateFrameBytes(uint32_t Bytes) { FrameBytes += Bytes; }
+    void updateSpills() { ++Spills; }
+    void updateFills() { ++Fills; }
+    void dump(const IceString &Name, Ostream &Str);
+
+  private:
+    uint32_t InstructionsEmitted;
+    uint32_t RegistersSaved;
+    uint32_t FrameBytes;
+    uint32_t Spills;
+    uint32_t Fills;
+  };
+
+  // ThreadContext contains thread-local data.  This data can be
+  // combined/reduced as needed after all threads complete.
+  class ThreadContext {
+    ThreadContext(const ThreadContext &) = delete;
+    ThreadContext &operator=(const ThreadContext &) = delete;
+
+  public:
+    ThreadContext() {}
+    CodeStats StatsFunction;
+    std::vector<TimerStack> Timers;
+  };
+
 public:
   GlobalContext(Ostream *OsDump, Ostream *OsEmit, ELFStreamer *ELFStreamer,
                 VerboseMask Mask, TargetArch Arch, OptLevel Opt,
                 IceString TestPrefix, const ClFlags &Flags);
   ~GlobalContext();
 
   // Returns true if any of the specified options in the verbose mask
   // are set.  If the argument is omitted, it checks if any verbose
   // options at all are set.
   VerboseMask getVerbose() const { return VMask; }
   bool isVerbose(VerboseMask Mask = IceV_All) const { return VMask & Mask; }
   void setVerbose(VerboseMask Mask) { VMask = Mask; }
   void addVerbose(VerboseMask Mask) { VMask |= Mask; }
   void subVerbose(VerboseMask Mask) { VMask &= ~Mask; }
 
-  Ostream &getStrDump() { return *StrDump; }
-  Ostream &getStrEmit() { return *StrEmit; }
+  // The dump and emit streams need to be used by only one thread at a
+  // time.  This is done by exclusively reserving the streams via
+  // lockStr() and unlockStr().  The OstreamLocker class can be used
+  // to conveniently manage this.
+  //
+  // The model is that a thread grabs the stream lock, then does an
+  // arbitrary amount of work during which far-away callees may grab
+  // the stream and do something with it, and finally the thread
+  // releases the stream lock.  This allows large chunks of output to
+  // be dumped or emitted without risking interleaving from multiple
+  // threads.  When a worker locks the streams via lockStr(), we use
+  // IsStrLocked to verify that it wasn't already locked (i.e. no
+  // recursive lockStr() calls).  When a worker grabs one of the
+  // streams via getStrDump() or getStrEmit(), we lock StrLock
+  // (recursively, if lockStr() was correctly used, hence the need for
+  // recursive_mutex) and check that IsStrLocked is set.
+  void lockStr() {
+    StrLock.lock();
+    assert(!isStrLocked());
+    IsStrLocked = true;
+  }
+  void unlockStr() {
+    assert(isStrLocked());
+    IsStrLocked = false;
+    StrLock.unlock();
+  }
+  // Test whether we are already holding StrLock, by first doing a
+  // lock() and when it (eventually) succeeds, checking that we didn't
+  // recursively lock it.
+  bool isStrLocked() {
+    StrLock.lock();
+    bool WasLocked = IsStrLocked;
+    StrLock.unlock();
+    return WasLocked;
+  }
+  Ostream &getStrDump() {
+    assert(isStrLocked());
+    return *StrDump;
+  }
+  Ostream &getStrEmit() {
+    assert(isStrLocked());
+    return *StrEmit;
+  }
 
   TargetArch getTargetArch() const { return Arch; }
   OptLevel getOptLevel() const { return Opt; }
 
   // When emitting assembly, we allow a string to be prepended to
   // names of translated functions.  This makes it easier to create an
   // execution test against a reference translator like llc, with both
   // translators using the same bitcode as input.
   IceString getTestPrefix() const { return TestPrefix; }
   IceString mangleName(const IceString &Name) const;
@@ skipping 11 matching lines @@
   Constant *getConstantDouble(double Value);
   // Returns a symbolic constant.
   Constant *getConstantSym(RelocOffsetT Offset, const IceString &Name,
                            bool SuppressMangling);
   // Returns an undef.
   Constant *getConstantUndef(Type Ty);
   // Returns a zero value.
   Constant *getConstantZero(Type Ty);
   // getConstantPool() returns a copy of the constant pool for
   // constants of a given type.
-  ConstantList getConstantPool(Type Ty) const;
+  ConstantList getConstantPool(Type Ty);
   // Returns a new function declaration, allocated in an internal
   // memory pool.  Ownership of the function is maintained by this
   // class instance.
   FunctionDeclaration *newFunctionDeclaration(const FuncSigType *Signature,
                                               unsigned CallingConv,
                                               unsigned Linkage, bool IsProto);
 
   // Returns a new global variable declaration, allocated in an
   // internal memory pool.  Ownership of the function is maintained by
   // this class instance.
   VariableDeclaration *newVariableDeclaration();
 
   const ClFlags &getFlags() const { return Flags; }
 
   bool isIRGenerationDisabled() const {
     return ALLOW_DISABLE_IR_GEN ? getFlags().DisableIRGeneration : false;
   }
 
   // Allocate data of type T using the global allocator.
-  template <typename T> T *allocate() { return Allocator.Allocate<T>(); }
+  template <typename T> T *allocate() {
+    return getAllocator()->Allocate<T>();
+  }
 
   const Intrinsics &getIntrinsicsInfo() const { return IntrinsicsInfo; }
 
   // TODO(wala,stichnot): Make the RNG play nicely with multithreaded
   // translation.
   RandomNumberGenerator &getRNG() { return RNG; }
 
   ELFObjectWriter *getObjectWriter() const { return ObjectWriter.get(); }
 
   // Reset stats at the beginning of a function.
   void resetStats() {
     if (ALLOW_DUMP)
-      StatsFunction.reset();
+      TLS->StatsFunction.reset();
   }
   void dumpStats(const IceString &Name, bool Final = false);
   void statsUpdateEmitted(uint32_t InstCount) {
-    if (!ALLOW_DUMP)
+    if (!ALLOW_DUMP || !getFlags().DumpStats)
       return;
-    StatsFunction.updateEmitted(InstCount);
-    StatsCumulative.updateEmitted(InstCount);
+    TLS->StatsFunction.updateEmitted(InstCount);
+    getStatsCumulative()->updateEmitted(InstCount);
   }
   void statsUpdateRegistersSaved(uint32_t Num) {
-    if (!ALLOW_DUMP)
+    if (!ALLOW_DUMP || !getFlags().DumpStats)
       return;
-    StatsFunction.updateRegistersSaved(Num);
-    StatsCumulative.updateRegistersSaved(Num);
+    TLS->StatsFunction.updateRegistersSaved(Num);
+    getStatsCumulative()->updateRegistersSaved(Num);
   }
   void statsUpdateFrameBytes(uint32_t Bytes) {
-    if (!ALLOW_DUMP)
+    if (!ALLOW_DUMP || !getFlags().DumpStats)
       return;
-    StatsFunction.updateFrameBytes(Bytes);
-    StatsCumulative.updateFrameBytes(Bytes);
+    TLS->StatsFunction.updateFrameBytes(Bytes);
+    getStatsCumulative()->updateFrameBytes(Bytes);
   }
   void statsUpdateSpills() {
-    if (!ALLOW_DUMP)
+    if (!ALLOW_DUMP || !getFlags().DumpStats)
       return;
-    StatsFunction.updateSpills();
-    StatsCumulative.updateSpills();
+    TLS->StatsFunction.updateSpills();
+    getStatsCumulative()->updateSpills();
   }
   void statsUpdateFills() {
-    if (!ALLOW_DUMP)
+    if (!ALLOW_DUMP || !getFlags().DumpStats)
       return;
-    StatsFunction.updateFills();
-    StatsCumulative.updateFills();
+    TLS->StatsFunction.updateFills();
+    getStatsCumulative()->updateFills();
   }
 
   // These are predefined TimerStackIdT values.
   enum TimerStackKind {
     TSK_Default = 0,
     TSK_Funcs,
     TSK_Num
   };
 
+  TimerStackIdT newTimerStackID(const IceString &Name);
   TimerIdT getTimerID(TimerStackIdT StackID, const IceString &Name);
-  TimerStackIdT newTimerStackID(const IceString &Name);
   void pushTimer(TimerIdT ID, TimerStackIdT StackID = TSK_Default);
   void popTimer(TimerIdT ID, TimerStackIdT StackID = TSK_Default);
   void resetTimer(TimerStackIdT StackID);
   void setTimerName(TimerStackIdT StackID, const IceString &NewName);
   void dumpTimers(TimerStackIdT StackID = TSK_Default,
                   bool DumpCumulative = true);
 
 private:
+  // Try to make sure the mutexes are allocated on separate cache
+  // lines, assuming the maximum cache line size is 64.
+  const static size_t MaxCacheLineSize = 64;
+  alignas(MaxCacheLineSize) GlobalLockType AllocLock;
+  alignas(MaxCacheLineSize) GlobalLockType ConstPoolLock;
+  alignas(MaxCacheLineSize) GlobalLockType StatsLock;
+  alignas(MaxCacheLineSize) GlobalLockType TimerLock;
+
+  // StrLock is a global lock on the dump and emit output streams.
+  // IsStrLocked is used to validate the locking protocol, and can
+  // only be meaningfully inspected when StrLock is held.  Note that
+  // in a production build, the dump and emit streams are not used in
+  // any meaningful way, so this locking is more for
+  // development/debugging purposes.
+  typedef std::recursive_mutex StrLockType;
+  StrLockType StrLock;
+  bool IsStrLocked;

[JF, 2015/01/18 03:14:19]

I would still drop IsStrLocked, since tsan should do the same and be simpler.

[Jim Stichnoth, 2015/01/19 21:44:04]

Right, I didn't get to that part yet. :)

Here's what I'm thinking.  Continue with a std::lock_guard scoped locking
pattern for reserving the stream lock.  The dump stream's lock can be recursive
so you can grab the lock anywhere for debugging output as needed.  The emit
stream's lock can be non-recursive if desired.  (Though performance is not an
issue with the textual dump/emit code.)

Agreed that tsan can catch conflicting uses of the streams without taking the
lock, though that depends on running tsan builds with suitably high levels of
debugging output.  It would also be possible to use a second lock along with
LockedPtr<> to make it safer.

[JF, 2015/01/20 01:23:05]

Is recursive locking of the stream actually needed? It seems like passing a
reference to the already-locked stream would be better.
A lot of this discussion is hinging on having a tsan build tested
systematically. Maybe Subzero should have that build? :-)

[Jim Stichnoth, 2015/01/20 16:22:54]

Currently Subzero is pretty sparing with its dump output, so there may not be an
example in the code base I can point to.  But what I have in mind is this. 
Suppose I have a method like this:

void Inst::validate() {
  if (something_wrong) {
    OstreamLocker L(...);
    Ostream &Str = getStrDump();
    Str << "Validation error: ";
    this->dumpDecorated();
    Str << "\n";
  }
}

This method might be called as part of Cfg::dump() while the stream lock is
held, or it might be called as part of another analysis/transformation phase
while the stream lock is not held.  Of course one can deal with this by having
separate locking and non-locking versions of validate(), or passing the locked
state through the call chain.  But I think the most user-friendly solution,
especially with textual dumping/emitting where performance is not a concern, is
to use a recursive mutex.
Yes, and actual threading.  And blackjack. :)  I'll do that as part of the next
CL.

[JF, 2015/01/20 17:20:21]

As we discussed offline: recursive mutexes make me sad, I don't think you need
them here if the code follows some form of standard for locking.
Let me get my fur coat.

[Jim Stichnoth, 2015/01/20 18:14:53]

OK, changed to non-recursive mutex, keeping the separate typedef in case we need
to revisit later.

+
   Ostream *StrDump; // Stream for dumping / diagnostics
   Ostream *StrEmit; // Stream for code emission
 
   ArenaAllocator<> Allocator;
   VerboseMask VMask;
-  std::unique_ptr<class ConstantPool> ConstPool;
+  std::unique_ptr<ConstantPool> ConstPool;
   Intrinsics IntrinsicsInfo;
   const TargetArch Arch;
   const OptLevel Opt;
   const IceString TestPrefix;
   const ClFlags &Flags;
   RandomNumberGenerator RNG;
   std::unique_ptr<ELFObjectWriter> ObjectWriter;
-  CodeStats StatsFunction;
   CodeStats StatsCumulative;
   std::vector<TimerStack> Timers;
   std::vector<GlobalDeclaration *> GlobalDeclarations;
 
+  LockedPtr<ArenaAllocator<>> getAllocator() {
+    return LockedPtr<ArenaAllocator<>>(&Allocator, AllocLock);
+  }
+  LockedPtr<ConstantPool> getConstPool() {
+    return LockedPtr<ConstantPool>(ConstPool.get(), ConstPoolLock);
+  }
+  LockedPtr<CodeStats> getStatsCumulative() {
+    return LockedPtr<CodeStats>(&StatsCumulative, StatsLock);
+  }
+  LockedPtr<std::vector<TimerStack>> getTimers() {
+    return LockedPtr<std::vector<TimerStack>>(&Timers, TimerLock);
+  }
+
+  std::vector<ThreadContext *> AllThreadContexts;
+  // Each thread has its own TLS pointer which is also held in
+  // AllThreadContexts.
+  thread_local static ThreadContext *TLS;
+
   // Private helpers for mangleName()
   typedef llvm::SmallVector<char, 32> ManglerVector;
   void incrementSubstitutions(ManglerVector &OldName) const;
 };
 
 // Helper class to push and pop a timer marker.  The constructor
 // pushes a marker, and the destructor pops it.  This is for
 // convenient timing of regions of code.
 class TimerMarker {
   TimerMarker(const TimerMarker &) = delete;
@@ skipping 14 matching lines @@
     if (ALLOW_DUMP && Active)
       Ctx->popTimer(ID);
   }
 
 private:
   TimerIdT ID;
   GlobalContext *const Ctx;
   bool Active;
 };
 
+// Helper class for locking the streams and then automatically
+// unlocking them.
+class OstreamLocker {
+private:
+  OstreamLocker() = delete;
+  OstreamLocker(const OstreamLocker &) = delete;
+  OstreamLocker &operator=(const OstreamLocker &) = delete;
+
+public:
+  explicit OstreamLocker(GlobalContext *Ctx) : Ctx(Ctx) { Ctx->lockStr(); }
+  ~OstreamLocker() { Ctx->unlockStr(); }
+
+private:
+  GlobalContext *const Ctx;
+};
+
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEGLOBALCONTEXT_H