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 "cpu/minor/trace.hh"
54 #include "cpu/activity.hh"
55 #include "cpu/timebuf.hh"
60 /** Interface class for data with reporting/tracing facilities. This
61 * interface doesn't actually have to be used as other classes which need
62 * this interface uses templating rather than inheritance but it's provided
63 * here to document the interface needed by those classes. */
67 /** Print the data in a format suitable to be the value in "name=value"
69 virtual void reportData(std::ostream &os) const = 0;
71 virtual ~ReportIF() { }
74 /** Interface class for data with 'bubble' values. This interface doesn't
75 * actually have to be used as other classes which need this interface uses
76 * templating rather than inheritance but it's provided here to document
77 * the interface needed by those classes. */
81 virtual bool isBubble() const = 0;
84 /** ...ReportTraits are trait classes with the same functionality as
85 * ReportIF, but with elements explicitly passed into the report...
88 /** Allow a template using ReportTraits to call report... functions of
89 * ReportIF-bearing elements themselves */
90 template <typename ElemType> /* ElemType should implement ReportIF */
91 class ReportTraitsAdaptor
95 reportData(std::ostream &os, const ElemType &elem)
96 { elem.reportData(os); }
99 /** A similar adaptor but for elements held by pointer
100 * ElemType should implement ReportIF */
101 template <typename PtrType>
102 class ReportTraitsPtrAdaptor
106 reportData(std::ostream &os, const PtrType &elem)
107 { elem->reportData(os); }
110 /** ... BubbleTraits are trait classes to add BubbleIF interface
111 * functionality to templates which process elements which don't necessarily
112 * implement BubbleIF themselves */
114 /** Default behaviour, no bubbles */
115 template <typename ElemType>
119 static bool isBubble(const ElemType &) { return false; }
120 static ElemType bubble() { assert(false); }
123 /** Pass on call to the element */
124 template <typename ElemType>
125 class BubbleTraitsAdaptor
128 static bool isBubble(const ElemType &elem)
129 { return elem.isBubble(); }
131 static ElemType bubble() { return ElemType::bubble(); }
134 /** Pass on call to the element where the element is a pointer */
135 template <typename PtrType, typename ElemType>
136 class BubbleTraitsPtrAdaptor
139 static bool isBubble(const PtrType &elem)
140 { return elem->isBubble(); }
142 static PtrType bubble() { return ElemType::bubble(); }
145 /** TimeBuffer with MinorTrace and Named interfaces */
146 template <typename ElemType,
147 typename ReportTraits = ReportTraitsAdaptor<ElemType>,
148 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
149 class MinorBuffer : public Named, public TimeBuffer<ElemType>
152 /** The range of elements that should appear in trace lines */
153 int reportLeft, reportRight;
155 /** Name to use for the data in a MinorTrace line */
156 std::string dataName;
159 MinorBuffer(const std::string &name,
160 const std::string &data_name,
161 int num_past, int num_future,
162 int report_left = -1, int report_right = -1) :
163 Named(name), TimeBuffer<ElemType>(num_past, num_future),
164 reportLeft(report_left), reportRight(report_right),
169 /* Is this buffer full of only bubbles */
175 for (int i = -this->past; i <= this->future; i++) {
176 if (!BubbleTraits::isBubble((*this)[i]))
183 /** Report buffer states from 'slot' 'from' to 'to'. For example 0,-1
184 * will produce two slices with current (just assigned) and last (one
185 * advance() old) slices with the current (0) one on the left.
186 * Reverse the numbers to change the order of slices */
190 std::ostringstream data;
192 int step = (reportLeft > reportRight ? -1 : 1);
193 int end = reportRight + step;
197 const ElemType &datum = (*this)[i];
199 ReportTraits::reportData(data, datum);
205 MINORTRACE("%s=%s\n", dataName, data.str());
209 /** Wraps a MinorBuffer with Input/Output interfaces to ensure that units
210 * within the model can only see the right end of buffers between them. */
211 template <typename Data>
215 typedef MinorBuffer<Data> Buffer;
218 /** Delays, in cycles, writing data into the latch and seeing it on the
225 /** forward/backwardDelay specify the delay from input to output in each
226 * direction. These arguments *must* be >= 1 */
227 Latch(const std::string &name,
228 const std::string &data_name,
229 Cycles delay_ = Cycles(1),
230 bool report_backwards = false) :
232 buffer(name, data_name, delay_, 0, (report_backwards ? -delay_ : 0),
233 (report_backwards ? 0 : -delay_))
237 /** Encapsulate wires on either input or output of the latch.
238 * forward/backward correspond to data direction relative to the
239 * pipeline. Latched and Immediate specify delay for backward data.
240 * Immediate data is available to earlier stages *during* the cycle it
245 typename Buffer::wire inputWire;
248 Input(typename Buffer::wire input_wire) :
249 inputWire(input_wire)
256 typename Buffer::wire outputWire;
259 Output(typename Buffer::wire output_wire) :
260 outputWire(output_wire)
264 bool empty() const { return buffer.empty(); }
266 /** An interface to just the input of the buffer */
267 Input input() { return Input(buffer.getWire(0)); }
269 /** An interface to just the output of the buffer */
270 Output output() { return Output(buffer.getWire(-delay)); }
272 void minorTrace() const { buffer.minorTrace(); }
274 void evaluate() { buffer.advance(); }
277 /** A pipeline simulating class that will stall (not advance when advance()
278 * is called) if a non-bubble value lies at the far end of the pipeline.
279 * The user can clear the stall before calling advance to unstall the
281 template <typename ElemType,
282 typename ReportTraits,
283 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
284 class SelfStallingPipeline : public MinorBuffer<ElemType, ReportTraits>
287 /** Wire at the input end of the pipeline (for convenience) */
288 typename TimeBuffer<ElemType>::wire pushWire;
289 /** Wire at the output end of the pipeline (for convenience) */
290 typename TimeBuffer<ElemType>::wire popWire;
293 /** If true, advance will not advance the pipeline */
296 /** The number of slots with non-bubbles in them */
297 unsigned int occupancy;
300 SelfStallingPipeline(const std::string &name,
301 const std::string &data_name,
303 MinorBuffer<ElemType, ReportTraits>
304 (name, data_name, depth, 0, -1, -depth),
305 pushWire(this->getWire(0)),
306 popWire(this->getWire(-depth)),
312 /* Write explicit bubbles to get around the case where the default
313 * constructor for the element type isn't good enough */
314 for (unsigned i = 0; i <= depth; i++)
315 (*this)[-i] = BubbleTraits::bubble();
319 /** Write an element to the back of the pipeline. This doesn't cause
320 * the pipeline to advance until advance is called. Pushing twice
321 * without advance-ing will just cause an overwrite of the last push's
323 void push(ElemType &elem)
325 assert(!alreadyPushed());
327 if (!BubbleTraits::isBubble(elem))
331 /** Peek at the end element of the pipe */
332 ElemType &front() { return *popWire; }
334 const ElemType &front() const { return *popWire; }
336 /** Have we already pushed onto this pipe without advancing */
337 bool alreadyPushed() { return !BubbleTraits::isBubble(*pushWire); }
339 /** There's data (not a bubble) at the end of the pipe */
340 bool isPopable() { return !BubbleTraits::isBubble(front()); }
342 /** Try to advance the pipeline. If we're stalled, don't advance. If
343 * we're not stalled, advance then check to see if we become stalled
344 * (a non-bubble at the end of the pipe) */
348 bool data_at_end = isPopable();
351 TimeBuffer<ElemType>::advance();
352 /* If there was data at the end of the pipe that has now been
353 * advanced out of the pipe, we've lost data */
356 /* Is there data at the end of the pipe now? */
357 stalled = isPopable();
358 /* Insert a bubble into the empty input slot to make sure that
359 * element is correct in the case where the default constructor
360 * for ElemType doesn't produce a bubble */
361 ElemType bubble = BubbleTraits::bubble();
367 /** Base class for space reservation requestable objects */
371 /** Can a slot be reserved? */
372 virtual bool canReserve() const = 0;
374 /** Reserve a slot in whatever structure this is attached to */
375 virtual void reserve() = 0;
377 /** Free a reserved slot */
378 virtual void freeReservation() = 0;
381 /** Wrapper for a queue type to act as a pipeline stage input queue.
382 * Handles capacity management, bubble value suppression and provides
385 * In an ideal world, ElemType would be derived from ReportIF and BubbleIF,
386 * but here we use traits and allow the Adaptors ReportTraitsAdaptor and
387 * BubbleTraitsAdaptor to work on data which *does* directly implement
388 * those interfaces. */
389 template <typename ElemType,
390 typename ReportTraits = ReportTraitsAdaptor<ElemType>,
391 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
392 class Queue : public Named, public Reservable
395 std::deque<ElemType> queue;
397 /** Number of slots currently reserved for future (reservation
398 * respecting) pushes */
399 unsigned int numReservedSlots;
401 /** Need this here as queues usually don't have a limited capacity */
402 unsigned int capacity;
404 /** Name to use for the data in MinorTrace */
405 std::string dataName;
408 Queue(const std::string &name, const std::string &data_name,
409 unsigned int capacity_) :
419 /** Push an element into the buffer if it isn't a bubble. Bubbles are
420 * just discarded. It is assummed that any push into a queue with
421 * reserved space intends to take that space */
425 if (!BubbleTraits::isBubble(data)) {
427 queue.push_back(data);
429 if (queue.size() > capacity) {
430 warn("%s: No space to push data into queue of capacity"
431 " %u, pushing anyway\n", name(), capacity);
437 /** Clear all allocated space. Be careful how this is used */
438 void clearReservedSpace() { numReservedSlots = 0; }
440 /** Clear a single reserved slot */
441 void freeReservation()
443 if (numReservedSlots != 0)
447 /** Reserve space in the queue for future pushes. Enquiries about space
448 * in the queue using unreservedRemainingSpace will only tell about
449 * space which is not full and not reserved. */
453 /* Check reservable space */
454 if (unreservedRemainingSpace() == 0)
455 warn("%s: No space is reservable in queue", name());
460 bool canReserve() const { return unreservedRemainingSpace() != 0; }
462 /** Number of slots available in an empty buffer */
463 unsigned int totalSpace() const { return capacity; }
465 /** Number of slots already occupied in this buffer */
466 unsigned int occupiedSpace() const { return queue.size(); }
468 /** Number of slots which are reserved. */
469 unsigned int reservedSpace() const { return numReservedSlots; }
471 /** Number of slots yet to fill in this buffer. This doesn't include
474 remainingSpace() const
476 int ret = capacity - queue.size();
478 return (ret < 0 ? 0 : ret);
481 /** Like remainingSpace but does not count reserved spaces */
483 unreservedRemainingSpace() const
485 int ret = capacity - (queue.size() + numReservedSlots);
487 return (ret < 0 ? 0 : ret);
490 /** Head value. Like std::queue::front */
491 ElemType &front() { return queue.front(); }
493 const ElemType &front() const { return queue.front(); }
495 /** Pop the head item. Like std::queue::pop */
496 void pop() { queue.pop_front(); }
498 /** Is the queue empty? */
499 bool empty() const { return queue.empty(); }
504 std::ostringstream data;
505 /* If we become over-full, totalSpace() can actually be smaller than
506 * occupiedSpace(). Handle this */
507 unsigned int num_total = (occupiedSpace() > totalSpace() ?
508 occupiedSpace() : totalSpace());
510 unsigned int num_reserved = reservedSpace();
511 unsigned int num_occupied = occupiedSpace();
514 /* Bodge to rotate queue to report elements */
515 while (num_printed <= num_occupied) {
516 ReportTraits::reportData(data, queue[num_printed - 1]);
519 if (num_printed <= num_total)
523 int num_printed_reserved = 1;
524 /* Show reserved slots */
525 while (num_printed_reserved <= num_reserved &&
526 num_printed <= num_total)
529 num_printed_reserved++;
532 if (num_printed <= num_total)
536 /* And finally pad with empty slots (if there are any) */
537 while (num_printed <= num_total) {
540 if (num_printed <= num_total)
544 MINORTRACE("%s=%s\n", dataName, data.str());
548 /** Like a Queue but with a restricted interface and a setTail function
549 * which, when the queue is empty, just takes a reference to the pushed
550 * item as the single element. Calling pushTail will push that element
553 * The purpose of this class is to allow the faster operation of queues of
554 * items which usually don't get deeper than one item and for which the copy
555 * associated with a push is expensive enough to want to avoid
557 * The intended use case is the input buffer for pipeline stages, hence the
559 template <typename ElemType,
560 typename ReportTraits = ReportTraitsAdaptor<ElemType>,
561 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
562 class InputBuffer : public Reservable
565 /** Underlying queue */
566 mutable Queue<ElemType, ReportTraits, BubbleTraits> queue;
568 /** Pointer to the single element (if not NULL) */
569 mutable ElemType *elementPtr;
572 InputBuffer(const std::string &name, const std::string &data_name,
573 unsigned int capacity_) :
574 queue(name, data_name, capacity_),
579 /** Set the tail of the queue, this is like push but needs
580 * to be followed by pushTail for the new tail to make its
581 * way into the queue proper */
583 setTail(ElemType &new_element)
586 if (!BubbleTraits::isBubble(new_element)) {
588 elementPtr = &new_element;
590 queue.push(new_element);
594 /** No single element or queue entries */
595 bool empty() const { return !elementPtr && queue.empty(); }
597 /** Return the element, or the front of the queue */
598 const ElemType &front() const
599 { return (elementPtr ? *elementPtr : queue.front()); }
602 { return (elementPtr ? *elementPtr : queue.front()); }
604 /** Pop either the head, or if none, the head of the queue */
609 /* A popped element was expected to be pushed into queue
610 * and so take a reserved space */
612 queue.freeReservation();
618 /** Push the single element (if any) into the queue proper. If the
619 * element's reference points to a transient object, remember to
620 * always do this before the end of that object's life */
625 queue.push(*elementPtr);
629 /** Report elements */
637 /** Reservable interface, passed on to queue */
638 bool canReserve() const { return queue.canReserve(); }
639 void reserve() { queue.reserve(); }
640 void freeReservation() { queue.freeReservation(); }
642 /** Like remainingSpace but does not count reserved spaces */
644 unreservedRemainingSpace()
647 return queue.unreservedRemainingSpace();
653 #endif /* __CPU_MINOR_BUFFERS_HH__ */