blob: 864b29e0cef161bb13cbfe56c8c959320c1b91d7 [file] [log] [blame]
/*
* 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__ */