buffers.hh

Go to the documentation of this file.

/*
 * 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
 */

#ifndef __CPU_MINOR_BUFFERS_HH__
#define __CPU_MINOR_BUFFERS_HH__

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

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

namespace Minor
{

class ReportIF
{
  public:
    virtual void reportData(std::ostream &os) const = 0;

    virtual ~ReportIF() { }
};

class BubbleIF
{
  public:
    virtual bool isBubble() const = 0;
};

template <typename ElemType> /* ElemType should implement ReportIF */
class ReportTraitsAdaptor
{
  public:
    static void
    reportData(std::ostream &os, const ElemType &elem)
    { elem.reportData(os); }
};

template <typename PtrType>
class ReportTraitsPtrAdaptor
{
  public:
    static void
    reportData(std::ostream &os, const PtrType &elem)
    { elem->reportData(os); }
};

template <typename ElemType>
class NoBubbleTraits
{
  public:
    static bool isBubble(const ElemType &) { return false; }
    static ElemType bubble() { assert(false); }
};

template <typename ElemType>
class BubbleTraitsAdaptor
{
  public:
    static bool isBubble(const ElemType &elem)
    { return elem.isBubble(); }

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

template <typename PtrType, typename ElemType>
class BubbleTraitsPtrAdaptor
{
  public:
    static bool isBubble(const PtrType &elem)
    { return elem->isBubble(); }

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

template <typename ElemType,
    typename ReportTraits = ReportTraitsAdaptor<ElemType>,
    typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
class MinorBuffer : public Named, public TimeBuffer<ElemType>
{
  protected:
    int reportLeft, reportRight;

    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;
    }

    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());
    }
};

template <typename Data>
class Latch
{
  public:
    typedef MinorBuffer<Data> Buffer;

  protected:
    Cycles delay;

    Buffer buffer;

  public:
    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:
    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(); }

    Input input() { return Input(buffer.getWire(0)); }

    Output output() { return Output(buffer.getWire(-delay)); }

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

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

template <typename ElemType,
    typename ReportTraits,
    typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
class SelfStallingPipeline : public MinorBuffer<ElemType, ReportTraits>
{
  protected:
    typename TimeBuffer<ElemType>::wire pushWire;
    typename TimeBuffer<ElemType>::wire popWire;

  public:
    bool stalled;

    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:
    void push(ElemType &elem)
    {
        assert(!alreadyPushed());
        *pushWire = elem;
        if (!BubbleTraits::isBubble(elem))
            occupancy++;
    }

    ElemType &front() { return *popWire; }

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

    bool alreadyPushed() { return !BubbleTraits::isBubble(*pushWire); }

    bool isPopable() { return !BubbleTraits::isBubble(front()); }

    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;
        }
    }
};

class Reservable
{
  public:
    virtual bool canReserve() const = 0;

    virtual void reserve() = 0;

    virtual void freeReservation() = 0;
};

template <typename ElemType,
    typename ReportTraits = ReportTraitsAdaptor<ElemType>,
    typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
class Queue : public Named, public Reservable
{
  private:
      std::deque<ElemType> queue;

    unsigned int numReservedSlots;

    unsigned int capacity;

    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:
    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);
            }

        }
    }

    void clearReservedSpace() { numReservedSlots = 0; }

    void freeReservation()
    {
        if (numReservedSlots != 0)
            numReservedSlots--;
    }

    void
    reserve()
    {
        /* Check reservable space */
        if (unreservedRemainingSpace() == 0)
            warn("%s: No space is reservable in queue", name());

        numReservedSlots++;
    }

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

    unsigned int totalSpace() const { return capacity; }

    unsigned int occupiedSpace() const { return queue.size(); }

    unsigned int reservedSpace() const { return numReservedSlots; }

    unsigned int
    remainingSpace() const
    {
        int ret = capacity - queue.size();

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

    unsigned int
    unreservedRemainingSpace() const
    {
        int ret = capacity - (queue.size() + numReservedSlots);

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

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

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

    void pop() { queue.pop_front(); }

    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());
    }
};

template <typename ElemType,
    typename ReportTraits = ReportTraitsAdaptor<ElemType>,
    typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
class InputBuffer : public Reservable
{
  protected:
    mutable Queue<ElemType, ReportTraits, BubbleTraits> queue;

    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:
    void
    setTail(ElemType &new_element)
    {
        assert(!elementPtr);
        if (!BubbleTraits::isBubble(new_element)) {
            if (queue.empty())
                elementPtr = &new_element;
            else
                queue.push(new_element);
        }
    }

    bool empty() const { return !elementPtr && queue.empty(); }

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

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

    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();
        }
    }

    void
    pushTail() const
    {
        if (elementPtr)
            queue.push(*elementPtr);
        elementPtr = NULL;
    }

    void
    minorTrace() const
    {
        pushTail();
        queue.minorTrace();
    }

    bool canReserve() const { return queue.canReserve(); }
    void reserve() { queue.reserve(); }
    void freeReservation() { queue.freeReservation(); }

    unsigned int
    unreservedRemainingSpace()
    {
        pushTail();
        return queue.unreservedRemainingSpace();
    }
};

}

#endif /* __CPU_MINOR_BUFFERS_HH__ */