cpu/minor/buffers.hh

/*
 * Copyright (c) 2013-2014 ARM Limited
 * All rights reserved
 *
 * The license below extends only to copyright in the software and shall
 * not be construed as granting a license to any other intellectual
 * property including but not limited to intellectual property relating
 * to a hardware implementation of the functionality of the software
 * licensed hereunder.  You may use the software subject to the license
 * terms below provided that you ensure that this notice is replicated
 * unmodified and in its entirety in all distributions of the software,
 * modified or unmodified, in source code or in binary form.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Andrew Bardsley
 */

/**
 * @file
 *
 * Classes for buffer, queue and FIFO behaviour.
 */

#ifndef __CPU_MINOR_BUFFERS_HH__
#define __CPU_MINOR_BUFFERS_HH__

#include <iostream>
#include <queue>
#include <sstream>

#include "base/logging.hh"
#include "cpu/activity.hh"
#include "cpu/minor/trace.hh"
#include "cpu/timebuf.hh"

namespace Minor
{

/** Interface class for data with reporting/tracing facilities.  This
 *  interface doesn't actually have to be used as other classes which need
 *  this interface uses templating rather than inheritance but it's provided
 *  here to document the interface needed by those classes. */
class ReportIF
{
  public:
    /** Print the data in a format suitable to be the value in "name=value"
     *  trace lines */
    virtual void reportData(std::ostream &os) const = 0;

    virtual ~ReportIF() { }
};

/** Interface class for data with 'bubble' values.  This interface doesn't
 *  actually have to be used as other classes which need this interface uses
 *  templating rather than inheritance but it's provided here to document
 *  the interface needed by those classes. */
class BubbleIF
{
  public:
    virtual bool isBubble() const = 0;
};

/** ...ReportTraits are trait classes with the same functionality as
 *  ReportIF, but with elements explicitly passed into the report...
 *  functions. */

/** Allow a template using ReportTraits to call report... functions of
 *  ReportIF-bearing elements themselves */
template <typename ElemType> /* ElemType should implement ReportIF */
class ReportTraitsAdaptor
{
  public:
    static void
    reportData(std::ostream &os, const ElemType &elem)
    { elem.reportData(os); }
};

/** A similar adaptor but for elements held by pointer
 *  ElemType should implement ReportIF */
template <typename PtrType>
class ReportTraitsPtrAdaptor
{
  public:
    static void
    reportData(std::ostream &os, const PtrType &elem)
    { elem->reportData(os); }
};

/** ... BubbleTraits are trait classes to add BubbleIF interface
 *  functionality to templates which process elements which don't necessarily
 *  implement BubbleIF themselves */

/** Default behaviour, no bubbles */
template <typename ElemType>
class NoBubbleTraits
{
  public:
    static bool isBubble(const ElemType &) { return false; }
    static ElemType bubble() { assert(false); }
};

/** Pass on call to the element */
template <typename ElemType>
class BubbleTraitsAdaptor
{
  public:
    static bool isBubble(const ElemType &elem)
    { return elem.isBubble(); }

    static ElemType bubble() { return ElemType::bubble(); }
};

/** Pass on call to the element where the element is a pointer */
template <typename PtrType, typename ElemType>
class BubbleTraitsPtrAdaptor
{
  public:
    static bool isBubble(const PtrType &elem)
    { return elem->isBubble(); }

    static PtrType bubble() { return ElemType::bubble(); }
};

/** TimeBuffer with MinorTrace and Named interfaces */
template <typename ElemType,
    typename ReportTraits = ReportTraitsAdaptor<ElemType>,
    typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
class MinorBuffer : public Named, public TimeBuffer<ElemType>
{
  protected:
    /** The range of elements that should appear in trace lines */
    int reportLeft, reportRight;

    /** Name to use for the data in a MinorTrace line */
    std::string dataName;

  public:
    MinorBuffer(const std::string &name,
        const std::string &data_name,
        int num_past, int num_future,
        int report_left = -1, int report_right = -1) :
        Named(name), TimeBuffer<ElemType>(num_past, num_future),
        reportLeft(report_left), reportRight(report_right),
            dataName(data_name)
    { }

  public:
    /* Is this buffer full of only bubbles */
    bool
    empty() const
    {
        bool ret = true;

        for (int i = -this->past; i <= this->future; i++) {
            if (!BubbleTraits::isBubble((*this)[i]))
                ret = false;
        }

        return ret;
    }

    /** Report buffer states from 'slot' 'from' to 'to'.  For example 0,-1
      * will produce two slices with current (just assigned) and last (one
      * advance() old) slices with the current (0) one on the left.
      * Reverse the numbers to change the order of slices */
    void
    minorTrace() const
    {
        std::ostringstream data;

        int step = (reportLeft > reportRight ? -1 : 1);
        int end = reportRight + step;
        int i = reportLeft;

        while (i != end) {
            const ElemType &datum = (*this)[i];

            ReportTraits::reportData(data, datum);
            i += step;
            if (i != end)
                data << ',';
        }

        MINORTRACE("%s=%s\n", dataName, data.str());
    }
};

/** Wraps a MinorBuffer with Input/Output interfaces to ensure that units
 *  within the model can only see the right end of buffers between them. */
template <typename Data>
class Latch
{
  public:
    typedef MinorBuffer<Data> Buffer;

  protected:
    /** Delays, in cycles, writing data into the latch and seeing it on the
     *  latched wires */
    Cycles delay;

    Buffer buffer;

  public:
    /** forward/backwardDelay specify the delay from input to output in each
     *  direction.  These arguments *must* be >= 1 */
    Latch(const std::string &name,
        const std::string &data_name,
        Cycles delay_ = Cycles(1),
        bool report_backwards = false) :
        delay(delay_),
        buffer(name, data_name, delay_, 0, (report_backwards ? -delay_ : 0),
            (report_backwards ? 0 : -delay_))
    { }

  public:
    /** Encapsulate wires on either input or output of the latch.
     *  forward/backward correspond to data direction relative to the
     *  pipeline.  Latched and Immediate specify delay for backward data.
     *  Immediate data is available to earlier stages *during* the cycle it
     *  is written */
    class Input
    {
      public:
        typename Buffer::wire inputWire;

      public:
        Input(typename Buffer::wire input_wire) :
            inputWire(input_wire)
        { }
    };

    class Output
    {
      public:
        typename Buffer::wire outputWire;

      public:
        Output(typename Buffer::wire output_wire) :
            outputWire(output_wire)
        { }
    };

    bool empty() const { return buffer.empty(); }

    /** An interface to just the input of the buffer */
    Input input() { return Input(buffer.getWire(0)); }

    /** An interface to just the output of the buffer */
    Output output() { return Output(buffer.getWire(-delay)); }

    void minorTrace() const { buffer.minorTrace(); }

    void evaluate() { buffer.advance(); }
};

/** A pipeline simulating class that will stall (not advance when advance()
 *  is called) if a non-bubble value lies at the far end of the pipeline.
 *  The user can clear the stall before calling advance to unstall the
 *  pipeline. */
template <typename ElemType,
    typename ReportTraits,
    typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
class SelfStallingPipeline : public MinorBuffer<ElemType, ReportTraits>
{
  protected:
    /** Wire at the input end of the pipeline (for convenience) */
    typename TimeBuffer<ElemType>::wire pushWire;
    /** Wire at the output end of the pipeline (for convenience) */
    typename TimeBuffer<ElemType>::wire popWire;

  public:
    /** If true, advance will not advance the pipeline */
    bool stalled;

    /** The number of slots with non-bubbles in them */
    unsigned int occupancy;

  public:
    SelfStallingPipeline(const std::string &name,
        const std::string &data_name,
        unsigned depth) :
        MinorBuffer<ElemType, ReportTraits>
            (name, data_name, depth, 0, -1, -depth),
        pushWire(this->getWire(0)),
        popWire(this->getWire(-depth)),
        stalled(false),
        occupancy(0)
    {
        assert(depth > 0);

        /* Write explicit bubbles to get around the case where the default
         *  constructor for the element type isn't good enough */
        for (unsigned i = 0; i <= depth; i++)
            (*this)[-i] = BubbleTraits::bubble();
    }

  public:
    /** Write an element to the back of the pipeline.  This doesn't cause
     *  the pipeline to advance until advance is called.  Pushing twice
     *  without advance-ing will just cause an overwrite of the last push's
     *  data. */
    void push(ElemType &elem)
    {
        assert(!alreadyPushed());
        *pushWire = elem;
        if (!BubbleTraits::isBubble(elem))
            occupancy++;
    }

    /** Peek at the end element of the pipe */
    ElemType &front() { return *popWire; }

    const ElemType &front() const { return *popWire; }

    /** Have we already pushed onto this pipe without advancing */
    bool alreadyPushed() { return !BubbleTraits::isBubble(*pushWire); }

    /** There's data (not a bubble) at the end of the pipe */
    bool isPopable() { return !BubbleTraits::isBubble(front()); }

    /** Try to advance the pipeline.  If we're stalled, don't advance.  If
     *  we're not stalled, advance then check to see if we become stalled
     *  (a non-bubble at the end of the pipe) */
    void
    advance()
    {
        bool data_at_end = isPopable();

        if (!stalled) {
            TimeBuffer<ElemType>::advance();
            /* If there was data at the end of the pipe that has now been
             *  advanced out of the pipe, we've lost data */
            if (data_at_end)
                occupancy--;
            /* Is there data at the end of the pipe now? */
            stalled = isPopable();
            /* Insert a bubble into the empty input slot to make sure that
             *  element is correct in the case where the default constructor
             *  for ElemType doesn't produce a bubble */
            ElemType bubble = BubbleTraits::bubble();
            *pushWire = bubble;
        }
    }
};

/** Base class for space reservation requestable objects */
class Reservable
{
  public:
    /** Can a slot be reserved? */
    virtual bool canReserve() const = 0;

    /** Reserve a slot in whatever structure this is attached to */
    virtual void reserve() = 0;

    /** Free a reserved slot */
    virtual void freeReservation() = 0;
};

/** Wrapper for a queue type to act as a pipeline stage input queue.
 *  Handles capacity management, bubble value suppression and provides
 *  reporting.
 *
 *  In an ideal world, ElemType would be derived from ReportIF and BubbleIF,
 *  but here we use traits and allow the Adaptors ReportTraitsAdaptor and
 *  BubbleTraitsAdaptor to work on data which *does* directly implement
 *  those interfaces. */
template <typename ElemType,
    typename ReportTraits = ReportTraitsAdaptor<ElemType>,
    typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
class Queue : public Named, public Reservable
{
  private:
      std::deque<ElemType> queue;

    /** Number of slots currently reserved for future (reservation
     *  respecting) pushes */
    unsigned int numReservedSlots;

    /** Need this here as queues usually don't have a limited capacity */
    unsigned int capacity;

    /** Name to use for the data in MinorTrace */
    std::string dataName;

  public:
    Queue(const std::string &name, const std::string &data_name,
        unsigned int capacity_) :
        Named(name),
        numReservedSlots(0),
        capacity(capacity_),
        dataName(data_name)
    { }

    virtual ~Queue() { }

  public:
    /** Push an element into the buffer if it isn't a bubble.  Bubbles are
     *  just discarded.  It is assummed that any push into a queue with
     *  reserved space intends to take that space */
    void
    push(ElemType &data)
    {
        if (!BubbleTraits::isBubble(data)) {
            freeReservation();
            queue.push_back(data);

            if (queue.size() > capacity) {
                warn("%s: No space to push data into queue of capacity"
                    " %u, pushing anyway\n", name(), capacity);
            }

        }
    }

    /** Clear all allocated space.  Be careful how this is used */
    void clearReservedSpace() { numReservedSlots = 0; }

    /** Clear a single reserved slot */
    void freeReservation()
    {
        if (numReservedSlots != 0)
            numReservedSlots--;
    }

    /** Reserve space in the queue for future pushes.  Enquiries about space
     *  in the queue using unreservedRemainingSpace will only tell about
     *  space which is not full and not reserved. */
    void
    reserve()
    {
        /* Check reservable space */
        if (unreservedRemainingSpace() == 0)
            warn("%s: No space is reservable in queue", name());

        numReservedSlots++;
    }

    bool canReserve() const { return unreservedRemainingSpace() != 0; }

    /** Number of slots available in an empty buffer */
    unsigned int totalSpace() const { return capacity; }

    /** Number of slots already occupied in this buffer */
    unsigned int occupiedSpace() const { return queue.size(); }

    /** Number of slots which are reserved. */
    unsigned int reservedSpace() const { return numReservedSlots; }

    /** Number of slots yet to fill in this buffer.  This doesn't include
     *  reservation. */
    unsigned int
    remainingSpace() const
    {
        int ret = capacity - queue.size();

        return (ret < 0 ? 0 : ret);
    }

    /** Like remainingSpace but does not count reserved spaces */
    unsigned int
    unreservedRemainingSpace() const
    {
        int ret = capacity - (queue.size() + numReservedSlots);

        return (ret < 0 ? 0 : ret);
    }

    /** Head value.  Like std::queue::front */
    ElemType &front() { return queue.front(); }

    const ElemType &front() const { return queue.front(); }

    /** Pop the head item.  Like std::queue::pop */
    void pop() { queue.pop_front(); }

    /** Is the queue empty? */
    bool empty() const { return queue.empty(); }

    void
    minorTrace() const
    {
        std::ostringstream data;
        /* If we become over-full, totalSpace() can actually be smaller than
         * occupiedSpace().  Handle this */
        unsigned int num_total = (occupiedSpace() > totalSpace() ?
            occupiedSpace() : totalSpace());

        unsigned int num_reserved = reservedSpace();
        unsigned int num_occupied = occupiedSpace();

        int num_printed = 1;
        /* Bodge to rotate queue to report elements */
        while (num_printed <= num_occupied) {
            ReportTraits::reportData(data, queue[num_printed - 1]);
            num_printed++;

            if (num_printed <= num_total)
                data << ',';
        }

        int num_printed_reserved = 1;
        /* Show reserved slots */
        while (num_printed_reserved <= num_reserved &&
            num_printed <= num_total)
        {
            data << 'R';
            num_printed_reserved++;
            num_printed++;

            if (num_printed <= num_total)
                data << ',';
        }

        /* And finally pad with empty slots (if there are any) */
        while (num_printed <= num_total) {
            num_printed++;

            if (num_printed <= num_total)
                data << ',';
        }

        MINORTRACE("%s=%s\n", dataName, data.str());
    }
};

/** Like a Queue but with a restricted interface and a setTail function
 *  which, when the queue is empty, just takes a reference to the pushed
 *  item as the single element.  Calling pushTail will push that element
 *  onto the queue.
 *
 *  The purpose of this class is to allow the faster operation of queues of
 *  items which usually don't get deeper than one item and for which the copy
 *  associated with a push is expensive enough to want to avoid
 *
 *  The intended use case is the input buffer for pipeline stages, hence the
 *  class name */
template <typename ElemType,
    typename ReportTraits = ReportTraitsAdaptor<ElemType>,
    typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
class InputBuffer : public Reservable
{
  protected:
    /** Underlying queue */
    mutable Queue<ElemType, ReportTraits, BubbleTraits> queue;

    /** Pointer to the single element (if not NULL) */
    mutable ElemType *elementPtr;

  public:
    InputBuffer(const std::string &name, const std::string &data_name,
        unsigned int capacity_) :
        queue(name, data_name, capacity_),
        elementPtr(NULL)
    { }

  public:
    /** Set the tail of the queue, this is like push but needs
     *  to be followed by pushTail for the new tail to make its
     *  way into the queue proper */
    void
    setTail(ElemType &new_element)
    {
        assert(!elementPtr);
        if (!BubbleTraits::isBubble(new_element)) {
            if (queue.empty())
                elementPtr = &new_element;
            else
                queue.push(new_element);
        }
    }

    /** No single element or queue entries */
    bool empty() const { return !elementPtr && queue.empty(); }

    /** Return the element, or the front of the queue */
    const ElemType &front() const
    { return (elementPtr ? *elementPtr : queue.front()); }

    ElemType &front()
    { return (elementPtr ? *elementPtr : queue.front()); }

    /** Pop either the head, or if none, the head of the queue */
    void
    pop()
    {
        if (elementPtr) {
            /* A popped element was expected to be pushed into queue
             *  and so take a reserved space */
            elementPtr = NULL;
            queue.freeReservation();
        } else {
            queue.pop();
        }
    }

    /** Push the single element (if any) into the queue proper.  If the
     *  element's reference points to a transient object, remember to
     *  always do this before the end of that object's life */
    void
    pushTail() const
    {
        if (elementPtr)
            queue.push(*elementPtr);
        elementPtr = NULL;
    }

    /** Report elements */
    void
    minorTrace() const
    {
        pushTail();
        queue.minorTrace();
    }

    /** Reservable interface, passed on to queue */
    bool canReserve() const { return queue.canReserve(); }
    void reserve() { queue.reserve(); }
    void freeReservation() { queue.freeReservation(); }

    /** Like remainingSpace but does not count reserved spaces */
    unsigned int
    unreservedRemainingSpace()
    {
        pushTail();
        return queue.unreservedRemainingSpace();
    }
};

}

#endif /* __CPU_MINOR_BUFFERS_HH__ */