1/*
2 * Copyright (c) 2013-2014 ARM Limited
3 * All rights reserved
4 *
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.
13 *
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.
24 *
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.
36 *
37 * Authors: Andrew Bardsley
38 */
39
40/**
41 * @file
42 *
43 * Classes for buffer, queue and FIFO behaviour.
44 */
45
46#ifndef __CPU_MINOR_BUFFERS_HH__
47#define __CPU_MINOR_BUFFERS_HH__
48
49#include <iostream>
50#include <queue>
51#include <sstream>
52
53#include "base/logging.hh"
54#include "cpu/activity.hh"
55#include "cpu/minor/trace.hh"
56#include "cpu/timebuf.hh"
57
58namespace Minor
59{
60
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. */
65class ReportIF
66{
67  public:
68    /** Print the data in a format suitable to be the value in "name=value"
69     *  trace lines */
70    virtual void reportData(std::ostream &os) const = 0;
71
72    virtual ~ReportIF() { }
73};
74
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. */
79class BubbleIF
80{
81  public:
82    virtual bool isBubble() const = 0;
83};
84
85/** ...ReportTraits are trait classes with the same functionality as
86 *  ReportIF, but with elements explicitly passed into the report...
87 *  functions. */
88
89/** Allow a template using ReportTraits to call report... functions of
90 *  ReportIF-bearing elements themselves */
91template <typename ElemType> /* ElemType should implement ReportIF */
92class ReportTraitsAdaptor
93{
94  public:
95    static void
96    reportData(std::ostream &os, const ElemType &elem)
97    { elem.reportData(os); }
98};
99
100/** A similar adaptor but for elements held by pointer
101 *  ElemType should implement ReportIF */
102template <typename PtrType>
103class ReportTraitsPtrAdaptor
104{
105  public:
106    static void
107    reportData(std::ostream &os, const PtrType &elem)
108    { elem->reportData(os); }
109};
110
111/** ... BubbleTraits are trait classes to add BubbleIF interface
112 *  functionality to templates which process elements which don't necessarily
113 *  implement BubbleIF themselves */
114
115/** Default behaviour, no bubbles */
116template <typename ElemType>
117class NoBubbleTraits
118{
119  public:
120    static bool isBubble(const ElemType &) { return false; }
121    static ElemType
122    bubble()
123    {
124        panic("bubble called but no bubble interface");
125    }
126};
127
128/** Pass on call to the element */
129template <typename ElemType>
130class BubbleTraitsAdaptor
131{
132  public:
133    static bool isBubble(const ElemType &elem)
134    { return elem.isBubble(); }
135
136    static ElemType bubble() { return ElemType::bubble(); }
137};
138
139/** Pass on call to the element where the element is a pointer */
140template <typename PtrType, typename ElemType>
141class BubbleTraitsPtrAdaptor
142{
143  public:
144    static bool isBubble(const PtrType &elem)
145    { return elem->isBubble(); }
146
147    static PtrType bubble() { return ElemType::bubble(); }
148};
149
150/** TimeBuffer with MinorTrace and Named interfaces */
151template <typename ElemType,
152    typename ReportTraits = ReportTraitsAdaptor<ElemType>,
153    typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
154class MinorBuffer : public Named, public TimeBuffer<ElemType>
155{
156  protected:
157    /** The range of elements that should appear in trace lines */
158    int reportLeft, reportRight;
159
160    /** Name to use for the data in a MinorTrace line */
161    std::string dataName;
162
163  public:
164    MinorBuffer(const std::string &name,
165        const std::string &data_name,
166        int num_past, int num_future,
167        int report_left = -1, int report_right = -1) :
168        Named(name), TimeBuffer<ElemType>(num_past, num_future),
169        reportLeft(report_left), reportRight(report_right),
170            dataName(data_name)
171    { }
172
173  public:
174    /* Is this buffer full of only bubbles */
175    bool
176    empty() const
177    {
178        bool ret = true;
179
180        for (int i = -this->past; i <= this->future; i++) {
181            if (!BubbleTraits::isBubble((*this)[i]))
182                ret = false;
183        }
184
185        return ret;
186    }
187
188    /** Report buffer states from 'slot' 'from' to 'to'.  For example 0,-1
189      * will produce two slices with current (just assigned) and last (one
190      * advance() old) slices with the current (0) one on the left.
191      * Reverse the numbers to change the order of slices */
192    void
193    minorTrace() const
194    {
195        std::ostringstream data;
196
197        int step = (reportLeft > reportRight ? -1 : 1);
198        int end = reportRight + step;
199        int i = reportLeft;
200
201        while (i != end) {
202            const ElemType &datum = (*this)[i];
203
204            ReportTraits::reportData(data, datum);
205            i += step;
206            if (i != end)
207                data << ',';
208        }
209
210        MINORTRACE("%s=%s\n", dataName, data.str());
211    }
212};
213
214/** Wraps a MinorBuffer with Input/Output interfaces to ensure that units
215 *  within the model can only see the right end of buffers between them. */
216template <typename Data>
217class Latch
218{
219  public:
220    typedef MinorBuffer<Data> Buffer;
221
222  protected:
223    /** Delays, in cycles, writing data into the latch and seeing it on the
224     *  latched wires */
225    Cycles delay;
226
227    Buffer buffer;
228
229  public:
230    /** forward/backwardDelay specify the delay from input to output in each
231     *  direction.  These arguments *must* be >= 1 */
232    Latch(const std::string &name,
233        const std::string &data_name,
234        Cycles delay_ = Cycles(1),
235        bool report_backwards = false) :
236        delay(delay_),
237        buffer(name, data_name, delay_, 0, (report_backwards ? -delay_ : 0),
238            (report_backwards ? 0 : -delay_))
239    { }
240
241  public:
242    /** Encapsulate wires on either input or output of the latch.
243     *  forward/backward correspond to data direction relative to the
244     *  pipeline.  Latched and Immediate specify delay for backward data.
245     *  Immediate data is available to earlier stages *during* the cycle it
246     *  is written */
247    class Input
248    {
249      public:
250        typename Buffer::wire inputWire;
251
252      public:
253        Input(typename Buffer::wire input_wire) :
254            inputWire(input_wire)
255        { }
256    };
257
258    class Output
259    {
260      public:
261        typename Buffer::wire outputWire;
262
263      public:
264        Output(typename Buffer::wire output_wire) :
265            outputWire(output_wire)
266        { }
267    };
268
269    bool empty() const { return buffer.empty(); }
270
271    /** An interface to just the input of the buffer */
272    Input input() { return Input(buffer.getWire(0)); }
273
274    /** An interface to just the output of the buffer */
275    Output output() { return Output(buffer.getWire(-delay)); }
276
277    void minorTrace() const { buffer.minorTrace(); }
278
279    void evaluate() { buffer.advance(); }
280};
281
282/** A pipeline simulating class that will stall (not advance when advance()
283 *  is called) if a non-bubble value lies at the far end of the pipeline.
284 *  The user can clear the stall before calling advance to unstall the
285 *  pipeline. */
286template <typename ElemType,
287    typename ReportTraits,
288    typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
289class SelfStallingPipeline : public MinorBuffer<ElemType, ReportTraits>
290{
291  protected:
292    /** Wire at the input end of the pipeline (for convenience) */
293    typename TimeBuffer<ElemType>::wire pushWire;
294    /** Wire at the output end of the pipeline (for convenience) */
295    typename TimeBuffer<ElemType>::wire popWire;
296
297  public:
298    /** If true, advance will not advance the pipeline */
299    bool stalled;
300
301    /** The number of slots with non-bubbles in them */
302    unsigned int occupancy;
303
304  public:
305    SelfStallingPipeline(const std::string &name,
306        const std::string &data_name,
307        unsigned depth) :
308        MinorBuffer<ElemType, ReportTraits>
309            (name, data_name, depth, 0, -1, -depth),
310        pushWire(this->getWire(0)),
311        popWire(this->getWire(-depth)),
312        stalled(false),
313        occupancy(0)
314    {
315        assert(depth > 0);
316
317        /* Write explicit bubbles to get around the case where the default
318         *  constructor for the element type isn't good enough */
319        for (unsigned i = 0; i <= depth; i++)
320            (*this)[-i] = BubbleTraits::bubble();
321    }
322
323  public:
324    /** Write an element to the back of the pipeline.  This doesn't cause
325     *  the pipeline to advance until advance is called.  Pushing twice
326     *  without advance-ing will just cause an overwrite of the last push's
327     *  data. */
328    void push(ElemType &elem)
329    {
330        assert(!alreadyPushed());
331        *pushWire = elem;
332        if (!BubbleTraits::isBubble(elem))
333            occupancy++;
334    }
335
336    /** Peek at the end element of the pipe */
337    ElemType &front() { return *popWire; }
338
339    const ElemType &front() const { return *popWire; }
340
341    /** Have we already pushed onto this pipe without advancing */
342    bool alreadyPushed() { return !BubbleTraits::isBubble(*pushWire); }
343
344    /** There's data (not a bubble) at the end of the pipe */
345    bool isPopable() { return !BubbleTraits::isBubble(front()); }
346
347    /** Try to advance the pipeline.  If we're stalled, don't advance.  If
348     *  we're not stalled, advance then check to see if we become stalled
349     *  (a non-bubble at the end of the pipe) */
350    void
351    advance()
352    {
353        bool data_at_end = isPopable();
354
355        if (!stalled) {
356            TimeBuffer<ElemType>::advance();
357            /* If there was data at the end of the pipe that has now been
358             *  advanced out of the pipe, we've lost data */
359            if (data_at_end)
360                occupancy--;
361            /* Is there data at the end of the pipe now? */
362            stalled = isPopable();
363            /* Insert a bubble into the empty input slot to make sure that
364             *  element is correct in the case where the default constructor
365             *  for ElemType doesn't produce a bubble */
366            ElemType bubble = BubbleTraits::bubble();
367            *pushWire = bubble;
368        }
369    }
370};
371
372/** Base class for space reservation requestable objects */
373class Reservable
374{
375  public:
376    /** Can a slot be reserved? */
377    virtual bool canReserve() const = 0;
378
379    /** Reserve a slot in whatever structure this is attached to */
380    virtual void reserve() = 0;
381
382    /** Free a reserved slot */
383    virtual void freeReservation() = 0;
384
385    virtual ~Reservable() {};
386};
387
388/** Wrapper for a queue type to act as a pipeline stage input queue.
389 *  Handles capacity management, bubble value suppression and provides
390 *  reporting.
391 *
392 *  In an ideal world, ElemType would be derived from ReportIF and BubbleIF,
393 *  but here we use traits and allow the Adaptors ReportTraitsAdaptor and
394 *  BubbleTraitsAdaptor to work on data which *does* directly implement
395 *  those interfaces. */
396template <typename ElemType,
397    typename ReportTraits = ReportTraitsAdaptor<ElemType>,
398    typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
399class Queue : public Named, public Reservable
400{
401  private:
402      std::deque<ElemType> queue;
403
404    /** Number of slots currently reserved for future (reservation
405     *  respecting) pushes */
406    unsigned int numReservedSlots;
407
408    /** Need this here as queues usually don't have a limited capacity */
409    unsigned int capacity;
410
411    /** Name to use for the data in MinorTrace */
412    std::string dataName;
413
414  public:
415    Queue(const std::string &name, const std::string &data_name,
416        unsigned int capacity_) :
417        Named(name),
418        numReservedSlots(0),
419        capacity(capacity_),
420        dataName(data_name)
421    { }
422
423  public:
424    /** Push an element into the buffer if it isn't a bubble.  Bubbles are
425     *  just discarded.  It is assummed that any push into a queue with
426     *  reserved space intends to take that space */
427    void
428    push(ElemType &data)
429    {
430        if (!BubbleTraits::isBubble(data)) {
431            freeReservation();
432            queue.push_back(data);
433
434            if (queue.size() > capacity) {
435                warn("%s: No space to push data into queue of capacity"
436                    " %u, pushing anyway\n", name(), capacity);
437            }
438
439        }
440    }
441
442    /** Clear all allocated space.  Be careful how this is used */
443    void clearReservedSpace() { numReservedSlots = 0; }
444
445    /** Clear a single reserved slot */
446    void freeReservation()
447    {
448        if (numReservedSlots != 0)
449            numReservedSlots--;
450    }
451
452    /** Reserve space in the queue for future pushes.  Enquiries about space
453     *  in the queue using unreservedRemainingSpace will only tell about
454     *  space which is not full and not reserved. */
455    void
456    reserve()
457    {
458        /* Check reservable space */
459        if (unreservedRemainingSpace() == 0)
460            warn("%s: No space is reservable in queue", name());
461
462        numReservedSlots++;
463    }
464
465    bool canReserve() const { return unreservedRemainingSpace() != 0; }
466
467    /** Number of slots available in an empty buffer */
468    unsigned int totalSpace() const { return capacity; }
469
470    /** Number of slots already occupied in this buffer */
471    unsigned int occupiedSpace() const { return queue.size(); }
472
473    /** Number of slots which are reserved. */
474    unsigned int reservedSpace() const { return numReservedSlots; }
475
476    /** Number of slots yet to fill in this buffer.  This doesn't include
477     *  reservation. */
478    unsigned int
479    remainingSpace() const
480    {
481        int ret = capacity - queue.size();
482
483        return (ret < 0 ? 0 : ret);
484    }
485
486    /** Like remainingSpace but does not count reserved spaces */
487    unsigned int
488    unreservedRemainingSpace() const
489    {
490        int ret = capacity - (queue.size() + numReservedSlots);
491
492        return (ret < 0 ? 0 : ret);
493    }
494
495    /** Head value.  Like std::queue::front */
496    ElemType &front() { return queue.front(); }
497
498    const ElemType &front() const { return queue.front(); }
499
500    /** Pop the head item.  Like std::queue::pop */
501    void pop() { queue.pop_front(); }
502
503    /** Is the queue empty? */
504    bool empty() const { return queue.empty(); }
505
506    void
507    minorTrace() const
508    {
509        std::ostringstream data;
510        /* If we become over-full, totalSpace() can actually be smaller than
511         * occupiedSpace().  Handle this */
512        unsigned int num_total = (occupiedSpace() > totalSpace() ?
513            occupiedSpace() : totalSpace());
514
515        unsigned int num_reserved = reservedSpace();
516        unsigned int num_occupied = occupiedSpace();
517
518        int num_printed = 1;
519        /* Bodge to rotate queue to report elements */
520        while (num_printed <= num_occupied) {
521            ReportTraits::reportData(data, queue[num_printed - 1]);
522            num_printed++;
523
524            if (num_printed <= num_total)
525                data << ',';
526        }
527
528        int num_printed_reserved = 1;
529        /* Show reserved slots */
530        while (num_printed_reserved <= num_reserved &&
531            num_printed <= num_total)
532        {
533            data << 'R';
534            num_printed_reserved++;
535            num_printed++;
536
537            if (num_printed <= num_total)
538                data << ',';
539        }
540
541        /* And finally pad with empty slots (if there are any) */
542        while (num_printed <= num_total) {
543            num_printed++;
544
545            if (num_printed <= num_total)
546                data << ',';
547        }
548
549        MINORTRACE("%s=%s\n", dataName, data.str());
550    }
551};
552
553/** Like a Queue but with a restricted interface and a setTail function
554 *  which, when the queue is empty, just takes a reference to the pushed
555 *  item as the single element.  Calling pushTail will push that element
556 *  onto the queue.
557 *
558 *  The purpose of this class is to allow the faster operation of queues of
559 *  items which usually don't get deeper than one item and for which the copy
560 *  associated with a push is expensive enough to want to avoid
561 *
562 *  The intended use case is the input buffer for pipeline stages, hence the
563 *  class name */
564template <typename ElemType,
565    typename ReportTraits = ReportTraitsAdaptor<ElemType>,
566    typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
567class InputBuffer : public Reservable
568{
569  protected:
570    /** Underlying queue */
571    mutable Queue<ElemType, ReportTraits, BubbleTraits> queue;
572
573    /** Pointer to the single element (if not NULL) */
574    mutable ElemType *elementPtr;
575
576  public:
577    InputBuffer(const std::string &name, const std::string &data_name,
578        unsigned int capacity_) :
579        queue(name, data_name, capacity_),
580        elementPtr(NULL)
581    { }
582
583  public:
584    /** Set the tail of the queue, this is like push but needs
585     *  to be followed by pushTail for the new tail to make its
586     *  way into the queue proper */
587    void
588    setTail(ElemType &new_element)
589    {
590        assert(!elementPtr);
591        if (!BubbleTraits::isBubble(new_element)) {
592            if (queue.empty())
593                elementPtr = &new_element;
594            else
595                queue.push(new_element);
596        }
597    }
598
599    /** No single element or queue entries */
600    bool empty() const { return !elementPtr && queue.empty(); }
601
602    /** Return the element, or the front of the queue */
603    const ElemType &front() const
604    { return (elementPtr ? *elementPtr : queue.front()); }
605
606    ElemType &front()
607    { return (elementPtr ? *elementPtr : queue.front()); }
608
609    /** Pop either the head, or if none, the head of the queue */
610    void
611    pop()
612    {
613        if (elementPtr) {
614            /* A popped element was expected to be pushed into queue
615             *  and so take a reserved space */
616            elementPtr = NULL;
617            queue.freeReservation();
618        } else {
619            queue.pop();
620        }
621    }
622
623    /** Push the single element (if any) into the queue proper.  If the
624     *  element's reference points to a transient object, remember to
625     *  always do this before the end of that object's life */
626    void
627    pushTail() const
628    {
629        if (elementPtr)
630            queue.push(*elementPtr);
631        elementPtr = NULL;
632    }
633
634    /** Report elements */
635    void
636    minorTrace() const
637    {
638        pushTail();
639        queue.minorTrace();
640    }
641
642    /** Reservable interface, passed on to queue */
643    bool canReserve() const { return queue.canReserve(); }
644    void reserve() { queue.reserve(); }
645    void freeReservation() { queue.freeReservation(); }
646
647    /** Like remainingSpace but does not count reserved spaces */
648    unsigned int
649    unreservedRemainingSpace()
650    {
651        pushTail();
652        return queue.unreservedRemainingSpace();
653    }
654};
655
656}
657
658#endif /* __CPU_MINOR_BUFFERS_HH__ */
659