//===- subzero/src/IceThreading.h - Threading functions ---------*- C++ -*-===//
//
//                        The Subzero Code Generator
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file declares threading-related functions.
///
//===----------------------------------------------------------------------===//

#ifndef SUBZERO_SRC_ICETHREADING_H
#define SUBZERO_SRC_ICETHREADING_H

#include "IceDefs.h"

#include <condition_variable>
#include <mutex>

namespace Ice {

/// BoundedProducerConsumerQueue is a work queue that allows multiple
/// producers and multiple consumers.  A producer adds entries using
/// blockingPush(), and may block if the queue is "full".  A producer
/// uses notifyEnd() to indicate that no more entries will be added.  A
/// consumer removes an item using blockingPop(), which will return
/// nullptr if notifyEnd() has been called and the queue is empty (it
/// never returns nullptr if the queue contained any items).
///
/// The MaxSize ctor arg controls the maximum size the queue can grow
/// to (subject to a hard limit of MaxStaticSize-1).  The Sequential
/// arg indicates purely sequential execution in which the single
/// thread should never wait().
///
/// Two condition variables are used in the implementation.
/// GrewOrEnded signals a waiting worker that a producer has changed
/// the state of the queue.  Shrunk signals a blocked producer that a
/// consumer has changed the state of the queue.
///
/// The methods begin with Sequential-specific code to be most clear.
/// The lock and condition variables are not used in the Sequential
/// case.
///
/// Internally, the queue is implemented as a circular array of size
/// MaxStaticSize, where the queue boundaries are denoted by the Front
/// and Back fields.  Front==Back indicates an empty queue.
template <typename T, size_t MaxStaticSize = 128>
class BoundedProducerConsumerQueue {
  BoundedProducerConsumerQueue() = delete;
  BoundedProducerConsumerQueue(const BoundedProducerConsumerQueue &) = delete;
  BoundedProducerConsumerQueue &
  operator=(const BoundedProducerConsumerQueue &) = delete;

public:
  BoundedProducerConsumerQueue(bool Sequential, size_t MaxSize = MaxStaticSize)
      : MaxSize(std::min(MaxSize, MaxStaticSize)), Sequential(Sequential) {}
  void blockingPush(T *Item) {
    {
      std::unique_lock<GlobalLockType> L(Lock);
      // If the work queue is already "full", wait for a consumer to
      // grab an element and shrink the queue.
      Shrunk.wait(L, [this] { return size() < MaxSize || Sequential; });
      push(Item);
    }
    GrewOrEnded.notify_one();
  }
  T *blockingPop() {
    T *Item = nullptr;
    bool ShouldNotifyProducer = false;
    {
      std::unique_lock<GlobalLockType> L(Lock);
      GrewOrEnded.wait(L, [this] { return IsEnded || !empty() || Sequential; });
      if (!empty()) {
        Item = pop();
        ShouldNotifyProducer = !IsEnded;
      }
    }
    if (ShouldNotifyProducer)
      Shrunk.notify_one();
    return Item;
  }
  void notifyEnd() {
    {
      std::lock_guard<GlobalLockType> L(Lock);
      IsEnded = true;
    }
    GrewOrEnded.notify_all();
  }

private:
  const static size_t MaxStaticSizeMask = MaxStaticSize - 1;
  static_assert(!(MaxStaticSize & (MaxStaticSize - 1)),
                "MaxStaticSize must be a power of 2");

  ICE_CACHELINE_BOUNDARY;
  /// WorkItems and Lock are read/written by all.
  T *WorkItems[MaxStaticSize];
  ICE_CACHELINE_BOUNDARY;
  /// Lock guards access to WorkItems, Front, Back, and IsEnded.
  GlobalLockType Lock;

  ICE_CACHELINE_BOUNDARY;
  /// GrewOrEnded is written by the producers and read by the
  /// consumers.  It is notified (by the producer) when something is
  /// added to the queue, in case consumers are waiting for a non-empty
  /// queue.
  std::condition_variable GrewOrEnded;
  /// Back is the index into WorkItems[] of where the next element will
  /// be pushed.  (More precisely, Back&MaxStaticSize is the index.)
  /// It is written by the producers, and read by all via size() and
  /// empty().
  size_t Back = 0;

  ICE_CACHELINE_BOUNDARY;
  /// Shrunk is notified (by the consumer) when something is removed
  /// from the queue, in case a producer is waiting for the queue to
  /// drop below maximum capacity.  It is written by the consumers and
  /// read by the producers.
  std::condition_variable Shrunk;
  /// Front is the index into WorkItems[] of the oldest element,
  /// i.e. the next to be popped.  (More precisely Front&MaxStaticSize
  /// is the index.)  It is written by the consumers, and read by all
  /// via size() and empty().
  size_t Front = 0;

  ICE_CACHELINE_BOUNDARY;

  /// MaxSize and Sequential are read by all and written by none.
  const size_t MaxSize;
  const bool Sequential;
  /// IsEnded is read by the consumers, and only written once by the
  /// producer.
  bool IsEnded = false;

  /// The lock must be held when the following methods are called.
  bool empty() const { return Front == Back; }
  size_t size() const { return Back - Front; }
  void push(T *Item) {
    WorkItems[Back++ & MaxStaticSizeMask] = Item;
    assert(size() <= MaxStaticSize);
  }
  T *pop() {
    assert(!empty());
    return WorkItems[Front++ & MaxStaticSizeMask];
  }
};

/// EmitterWorkItem is a simple wrapper around a pointer that
/// represents a work item to be emitted, i.e. a function or a set of
/// global declarations and initializers, and it includes a sequence
/// number so that work items can be emitted in a particular order for
/// deterministic output.  It acts like an interface class, but instead
/// of making the classes of interest inherit from EmitterWorkItem, it
/// wraps pointers to these classes.  Some space is wasted compared to
/// storing the pointers in a union, but not too much due to the work
/// granularity.
class EmitterWorkItem {
  EmitterWorkItem() = delete;
  EmitterWorkItem(const EmitterWorkItem &) = delete;
  EmitterWorkItem &operator=(const EmitterWorkItem &) = delete;

public:
  /// ItemKind can be one of the following:
  ///
  /// WI_Nop: No actual work.  This is a placeholder to maintain
  /// sequence numbers in case there is a translation error.
  ///
  /// WI_GlobalInits: A list of global declarations and initializers.
  ///
  /// WI_Asm: A function that has already had emitIAS() called on it.
  /// The work is transferred via the Assembler buffer, and the
  /// originating Cfg has been deleted (to recover lots of memory).
  ///
  /// WI_Cfg: A Cfg that has not yet had emit() or emitIAS() called on
  /// it.  This is only used as a debugging configuration when we want
  /// to emit "readable" assembly code, possibly annotated with
  /// liveness and other information only available in the Cfg and not
  /// in the Assembler buffer.
  enum ItemKind { WI_Nop, WI_GlobalInits, WI_Asm, WI_Cfg };
  /// Constructor for a WI_Nop work item.
  explicit EmitterWorkItem(uint32_t Seq);
  /// Constructor for a WI_GlobalInits work item.
  EmitterWorkItem(uint32_t Seq, VariableDeclarationList *D);
  /// Constructor for a WI_Asm work item.
  EmitterWorkItem(uint32_t Seq, Assembler *A);
  /// Constructor for a WI_Cfg work item.
  EmitterWorkItem(uint32_t Seq, Cfg *F);
  uint32_t getSequenceNumber() const { return Sequence; }
  ItemKind getKind() const { return Kind; }
  void setGlobalInits(std::unique_ptr<VariableDeclarationList> GloblInits);
  std::unique_ptr<VariableDeclarationList> getGlobalInits();
  std::unique_ptr<Assembler> getAsm();
  std::unique_ptr<Cfg> getCfg();

private:
  const uint32_t Sequence;
  const ItemKind Kind;
  std::unique_ptr<VariableDeclarationList> GlobalInits;
  std::unique_ptr<Assembler> Function;
  std::unique_ptr<Cfg> RawFunc;
};

} // end of namespace Ice

#endif // SUBZERO_SRC_ICETHREADING_H