2 * Copyright (c) 2013-2014 ARM Limited
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder. You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions are
16 * met: redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer;
18 * redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution;
21 * neither the name of the copyright holders nor the names of its
22 * contributors may be used to endorse or promote products derived from
23 * this software without specific prior written permission.
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 * Authors: Andrew Bardsley
43 * Classes for buffer, queue and FIFO behaviour.
46 #ifndef __CPU_MINOR_BUFFERS_HH__
47 #define __CPU_MINOR_BUFFERS_HH__
53 #include "base/logging.hh"
54 #include "cpu/activity.hh"
55 #include "cpu/minor/trace.hh"
56 #include "cpu/timebuf.hh"
61 /** Interface class for data with reporting/tracing facilities. This
62 * interface doesn't actually have to be used as other classes which need
63 * this interface uses templating rather than inheritance but it's provided
64 * here to document the interface needed by those classes. */
68 /** Print the data in a format suitable to be the value in "name=value"
70 virtual void reportData(std::ostream &os) const = 0;
72 virtual ~ReportIF() { }
75 /** Interface class for data with 'bubble' values. This interface doesn't
76 * actually have to be used as other classes which need this interface uses
77 * templating rather than inheritance but it's provided here to document
78 * the interface needed by those classes. */
82 virtual bool isBubble() const = 0;
85 /** ...ReportTraits are trait classes with the same functionality as
86 * ReportIF, but with elements explicitly passed into the report...
89 /** Allow a template using ReportTraits to call report... functions of
90 * ReportIF-bearing elements themselves */
91 template <typename ElemType> /* ElemType should implement ReportIF */
92 class ReportTraitsAdaptor
96 reportData(std::ostream &os, const ElemType &elem)
97 { elem.reportData(os); }
100 /** A similar adaptor but for elements held by pointer
101 * ElemType should implement ReportIF */
102 template <typename PtrType>
103 class ReportTraitsPtrAdaptor
107 reportData(std::ostream &os, const PtrType &elem)
108 { elem->reportData(os); }
111 /** ... BubbleTraits are trait classes to add BubbleIF interface
112 * functionality to templates which process elements which don't necessarily
113 * implement BubbleIF themselves */
115 /** Default behaviour, no bubbles */
116 template <typename ElemType>
120 static bool isBubble(const ElemType &) { return false; }
121 static ElemType bubble() { assert(false); }
124 /** Pass on call to the element */
125 template <typename ElemType>
126 class BubbleTraitsAdaptor
129 static bool isBubble(const ElemType &elem)
130 { return elem.isBubble(); }
132 static ElemType bubble() { return ElemType::bubble(); }
135 /** Pass on call to the element where the element is a pointer */
136 template <typename PtrType, typename ElemType>
137 class BubbleTraitsPtrAdaptor
140 static bool isBubble(const PtrType &elem)
141 { return elem->isBubble(); }
143 static PtrType bubble() { return ElemType::bubble(); }
146 /** TimeBuffer with MinorTrace and Named interfaces */
147 template <typename ElemType,
148 typename ReportTraits = ReportTraitsAdaptor<ElemType>,
149 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
150 class MinorBuffer : public Named, public TimeBuffer<ElemType>
153 /** The range of elements that should appear in trace lines */
154 int reportLeft, reportRight;
156 /** Name to use for the data in a MinorTrace line */
157 std::string dataName;
160 MinorBuffer(const std::string &name,
161 const std::string &data_name,
162 int num_past, int num_future,
163 int report_left = -1, int report_right = -1) :
164 Named(name), TimeBuffer<ElemType>(num_past, num_future),
165 reportLeft(report_left), reportRight(report_right),
170 /* Is this buffer full of only bubbles */
176 for (int i = -this->past; i <= this->future; i++) {
177 if (!BubbleTraits::isBubble((*this)[i]))
184 /** Report buffer states from 'slot' 'from' to 'to'. For example 0,-1
185 * will produce two slices with current (just assigned) and last (one
186 * advance() old) slices with the current (0) one on the left.
187 * Reverse the numbers to change the order of slices */
191 std::ostringstream data;
193 int step = (reportLeft > reportRight ? -1 : 1);
194 int end = reportRight + step;
198 const ElemType &datum = (*this)[i];
200 ReportTraits::reportData(data, datum);
206 MINORTRACE("%s=%s\n", dataName, data.str());
210 /** Wraps a MinorBuffer with Input/Output interfaces to ensure that units
211 * within the model can only see the right end of buffers between them. */
212 template <typename Data>
216 typedef MinorBuffer<Data> Buffer;
219 /** Delays, in cycles, writing data into the latch and seeing it on the
226 /** forward/backwardDelay specify the delay from input to output in each
227 * direction. These arguments *must* be >= 1 */
228 Latch(const std::string &name,
229 const std::string &data_name,
230 Cycles delay_ = Cycles(1),
231 bool report_backwards = false) :
233 buffer(name, data_name, delay_, 0, (report_backwards ? -delay_ : 0),
234 (report_backwards ? 0 : -delay_))
238 /** Encapsulate wires on either input or output of the latch.
239 * forward/backward correspond to data direction relative to the
240 * pipeline. Latched and Immediate specify delay for backward data.
241 * Immediate data is available to earlier stages *during* the cycle it
246 typename Buffer::wire inputWire;
249 Input(typename Buffer::wire input_wire) :
250 inputWire(input_wire)
257 typename Buffer::wire outputWire;
260 Output(typename Buffer::wire output_wire) :
261 outputWire(output_wire)
265 bool empty() const { return buffer.empty(); }
267 /** An interface to just the input of the buffer */
268 Input input() { return Input(buffer.getWire(0)); }
270 /** An interface to just the output of the buffer */
271 Output output() { return Output(buffer.getWire(-delay)); }
273 void minorTrace() const { buffer.minorTrace(); }
275 void evaluate() { buffer.advance(); }
278 /** A pipeline simulating class that will stall (not advance when advance()
279 * is called) if a non-bubble value lies at the far end of the pipeline.
280 * The user can clear the stall before calling advance to unstall the
282 template <typename ElemType,
283 typename ReportTraits,
284 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
285 class SelfStallingPipeline : public MinorBuffer<ElemType, ReportTraits>
288 /** Wire at the input end of the pipeline (for convenience) */
289 typename TimeBuffer<ElemType>::wire pushWire;
290 /** Wire at the output end of the pipeline (for convenience) */
291 typename TimeBuffer<ElemType>::wire popWire;
294 /** If true, advance will not advance the pipeline */
297 /** The number of slots with non-bubbles in them */
298 unsigned int occupancy;
301 SelfStallingPipeline(const std::string &name,
302 const std::string &data_name,
304 MinorBuffer<ElemType, ReportTraits>
305 (name, data_name, depth, 0, -1, -depth),
306 pushWire(this->getWire(0)),
307 popWire(this->getWire(-depth)),
313 /* Write explicit bubbles to get around the case where the default
314 * constructor for the element type isn't good enough */
315 for (unsigned i = 0; i <= depth; i++)
316 (*this)[-i] = BubbleTraits::bubble();
320 /** Write an element to the back of the pipeline. This doesn't cause
321 * the pipeline to advance until advance is called. Pushing twice
322 * without advance-ing will just cause an overwrite of the last push's
324 void push(ElemType &elem)
326 assert(!alreadyPushed());
328 if (!BubbleTraits::isBubble(elem))
332 /** Peek at the end element of the pipe */
333 ElemType &front() { return *popWire; }
335 const ElemType &front() const { return *popWire; }
337 /** Have we already pushed onto this pipe without advancing */
338 bool alreadyPushed() { return !BubbleTraits::isBubble(*pushWire); }
340 /** There's data (not a bubble) at the end of the pipe */
341 bool isPopable() { return !BubbleTraits::isBubble(front()); }
343 /** Try to advance the pipeline. If we're stalled, don't advance. If
344 * we're not stalled, advance then check to see if we become stalled
345 * (a non-bubble at the end of the pipe) */
349 bool data_at_end = isPopable();
352 TimeBuffer<ElemType>::advance();
353 /* If there was data at the end of the pipe that has now been
354 * advanced out of the pipe, we've lost data */
357 /* Is there data at the end of the pipe now? */
358 stalled = isPopable();
359 /* Insert a bubble into the empty input slot to make sure that
360 * element is correct in the case where the default constructor
361 * for ElemType doesn't produce a bubble */
362 ElemType bubble = BubbleTraits::bubble();
368 /** Base class for space reservation requestable objects */
372 /** Can a slot be reserved? */
373 virtual bool canReserve() const = 0;
375 /** Reserve a slot in whatever structure this is attached to */
376 virtual void reserve() = 0;
378 /** Free a reserved slot */
379 virtual void freeReservation() = 0;
382 /** Wrapper for a queue type to act as a pipeline stage input queue.
383 * Handles capacity management, bubble value suppression and provides
386 * In an ideal world, ElemType would be derived from ReportIF and BubbleIF,
387 * but here we use traits and allow the Adaptors ReportTraitsAdaptor and
388 * BubbleTraitsAdaptor to work on data which *does* directly implement
389 * those interfaces. */
390 template <typename ElemType,
391 typename ReportTraits = ReportTraitsAdaptor<ElemType>,
392 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
393 class Queue : public Named, public Reservable
396 std::deque<ElemType> queue;
398 /** Number of slots currently reserved for future (reservation
399 * respecting) pushes */
400 unsigned int numReservedSlots;
402 /** Need this here as queues usually don't have a limited capacity */
403 unsigned int capacity;
405 /** Name to use for the data in MinorTrace */
406 std::string dataName;
409 Queue(const std::string &name, const std::string &data_name,
410 unsigned int capacity_) :
420 /** Push an element into the buffer if it isn't a bubble. Bubbles are
421 * just discarded. It is assummed that any push into a queue with
422 * reserved space intends to take that space */
426 if (!BubbleTraits::isBubble(data)) {
428 queue.push_back(data);
430 if (queue.size() > capacity) {
431 warn("%s: No space to push data into queue of capacity"
432 " %u, pushing anyway\n", name(), capacity);
438 /** Clear all allocated space. Be careful how this is used */
439 void clearReservedSpace() { numReservedSlots = 0; }
441 /** Clear a single reserved slot */
442 void freeReservation()
444 if (numReservedSlots != 0)
448 /** Reserve space in the queue for future pushes. Enquiries about space
449 * in the queue using unreservedRemainingSpace will only tell about
450 * space which is not full and not reserved. */
454 /* Check reservable space */
455 if (unreservedRemainingSpace() == 0)
456 warn("%s: No space is reservable in queue", name());
461 bool canReserve() const { return unreservedRemainingSpace() != 0; }
463 /** Number of slots available in an empty buffer */
464 unsigned int totalSpace() const { return capacity; }
466 /** Number of slots already occupied in this buffer */
467 unsigned int occupiedSpace() const { return queue.size(); }
469 /** Number of slots which are reserved. */
470 unsigned int reservedSpace() const { return numReservedSlots; }
472 /** Number of slots yet to fill in this buffer. This doesn't include
475 remainingSpace() const
477 int ret = capacity - queue.size();
479 return (ret < 0 ? 0 : ret);
482 /** Like remainingSpace but does not count reserved spaces */
484 unreservedRemainingSpace() const
486 int ret = capacity - (queue.size() + numReservedSlots);
488 return (ret < 0 ? 0 : ret);
491 /** Head value. Like std::queue::front */
492 ElemType &front() { return queue.front(); }
494 const ElemType &front() const { return queue.front(); }
496 /** Pop the head item. Like std::queue::pop */
497 void pop() { queue.pop_front(); }
499 /** Is the queue empty? */
500 bool empty() const { return queue.empty(); }
505 std::ostringstream data;
506 /* If we become over-full, totalSpace() can actually be smaller than
507 * occupiedSpace(). Handle this */
508 unsigned int num_total = (occupiedSpace() > totalSpace() ?
509 occupiedSpace() : totalSpace());
511 unsigned int num_reserved = reservedSpace();
512 unsigned int num_occupied = occupiedSpace();
515 /* Bodge to rotate queue to report elements */
516 while (num_printed <= num_occupied) {
517 ReportTraits::reportData(data, queue[num_printed - 1]);
520 if (num_printed <= num_total)
524 int num_printed_reserved = 1;
525 /* Show reserved slots */
526 while (num_printed_reserved <= num_reserved &&
527 num_printed <= num_total)
530 num_printed_reserved++;
533 if (num_printed <= num_total)
537 /* And finally pad with empty slots (if there are any) */
538 while (num_printed <= num_total) {
541 if (num_printed <= num_total)
545 MINORTRACE("%s=%s\n", dataName, data.str());
549 /** Like a Queue but with a restricted interface and a setTail function
550 * which, when the queue is empty, just takes a reference to the pushed
551 * item as the single element. Calling pushTail will push that element
554 * The purpose of this class is to allow the faster operation of queues of
555 * items which usually don't get deeper than one item and for which the copy
556 * associated with a push is expensive enough to want to avoid
558 * The intended use case is the input buffer for pipeline stages, hence the
560 template <typename ElemType,
561 typename ReportTraits = ReportTraitsAdaptor<ElemType>,
562 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
563 class InputBuffer : public Reservable
566 /** Underlying queue */
567 mutable Queue<ElemType, ReportTraits, BubbleTraits> queue;
569 /** Pointer to the single element (if not NULL) */
570 mutable ElemType *elementPtr;
573 InputBuffer(const std::string &name, const std::string &data_name,
574 unsigned int capacity_) :
575 queue(name, data_name, capacity_),
580 /** Set the tail of the queue, this is like push but needs
581 * to be followed by pushTail for the new tail to make its
582 * way into the queue proper */
584 setTail(ElemType &new_element)
587 if (!BubbleTraits::isBubble(new_element)) {
589 elementPtr = &new_element;
591 queue.push(new_element);
595 /** No single element or queue entries */
596 bool empty() const { return !elementPtr && queue.empty(); }
598 /** Return the element, or the front of the queue */
599 const ElemType &front() const
600 { return (elementPtr ? *elementPtr : queue.front()); }
603 { return (elementPtr ? *elementPtr : queue.front()); }
605 /** Pop either the head, or if none, the head of the queue */
610 /* A popped element was expected to be pushed into queue
611 * and so take a reserved space */
613 queue.freeReservation();
619 /** Push the single element (if any) into the queue proper. If the
620 * element's reference points to a transient object, remember to
621 * always do this before the end of that object's life */
626 queue.push(*elementPtr);
630 /** Report elements */
638 /** Reservable interface, passed on to queue */
639 bool canReserve() const { return queue.canReserve(); }
640 void reserve() { queue.reserve(); }
641 void freeReservation() { queue.freeReservation(); }
643 /** Like remainingSpace but does not count reserved spaces */
645 unreservedRemainingSpace()
648 return queue.unreservedRemainingSpace();
654 #endif /* __CPU_MINOR_BUFFERS_HH__ */