buffers.hh revision 10259:ebb376f73dd2
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 "cpu/minor/trace.hh" 54#include "cpu/activity.hh" 55#include "cpu/timebuf.hh" 56 57namespace Minor 58{ 59 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. */ 64class ReportIF 65{ 66 public: 67 /** Print the data in a format suitable to be the value in "name=value" 68 * trace lines */ 69 virtual void reportData(std::ostream &os) const = 0; 70 71 virtual ~ReportIF() { } 72}; 73 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. */ 78class BubbleIF 79{ 80 public: 81 virtual bool isBubble() const = 0; 82}; 83 84/** ...ReportTraits are trait classes with the same functionality as 85 * ReportIF, but with elements explicitly passed into the report... 86 * functions. */ 87 88/** Allow a template using ReportTraits to call report... functions of 89 * ReportIF-bearing elements themselves */ 90template <typename ElemType> /* ElemType should implement ReportIF */ 91class ReportTraitsAdaptor 92{ 93 public: 94 static void 95 reportData(std::ostream &os, const ElemType &elem) 96 { elem.reportData(os); } 97}; 98 99/** A similar adaptor but for elements held by pointer 100 * ElemType should implement ReportIF */ 101template <typename PtrType> 102class ReportTraitsPtrAdaptor 103{ 104 public: 105 static void 106 reportData(std::ostream &os, const PtrType &elem) 107 { elem->reportData(os); } 108}; 109 110/** ... BubbleTraits are trait classes to add BubbleIF interface 111 * functionality to templates which process elements which don't necessarily 112 * implement BubbleIF themselves */ 113 114/** Default behaviour, no bubbles */ 115template <typename ElemType> 116class NoBubbleTraits 117{ 118 public: 119 static bool isBubble(const ElemType &) { return false; } 120 static ElemType bubble() { assert(false); } 121}; 122 123/** Pass on call to the element */ 124template <typename ElemType> 125class BubbleTraitsAdaptor 126{ 127 public: 128 static bool isBubble(const ElemType &elem) 129 { return elem.isBubble(); } 130 131 static ElemType bubble() { return ElemType::bubble(); } 132}; 133 134/** Pass on call to the element where the element is a pointer */ 135template <typename PtrType, typename ElemType> 136class BubbleTraitsPtrAdaptor 137{ 138 public: 139 static bool isBubble(const PtrType &elem) 140 { return elem->isBubble(); } 141 142 static PtrType bubble() { return ElemType::bubble(); } 143}; 144 145/** TimeBuffer with MinorTrace and Named interfaces */ 146template <typename ElemType, 147 typename ReportTraits = ReportTraitsAdaptor<ElemType>, 148 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> > 149class MinorBuffer : public Named, public TimeBuffer<ElemType> 150{ 151 protected: 152 /** The range of elements that should appear in trace lines */ 153 int reportLeft, reportRight; 154 155 /** Name to use for the data in a MinorTrace line */ 156 std::string dataName; 157 158 public: 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), 165 dataName(data_name) 166 { } 167 168 public: 169 /* Is this buffer full of only bubbles */ 170 bool 171 empty() const 172 { 173 bool ret = true; 174 175 for (int i = -this->past; i <= this->future; i++) { 176 if (!BubbleTraits::isBubble((*this)[i])) 177 ret = false; 178 } 179 180 return ret; 181 } 182 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 */ 187 void 188 minorTrace() const 189 { 190 std::ostringstream data; 191 192 int step = (reportLeft > reportRight ? -1 : 1); 193 int end = reportRight + step; 194 int i = reportLeft; 195 196 while (i != end) { 197 const ElemType &datum = (*this)[i]; 198 199 ReportTraits::reportData(data, datum); 200 i += step; 201 if (i != end) 202 data << ','; 203 } 204 205 MINORTRACE("%s=%s\n", dataName, data.str()); 206 } 207}; 208 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. */ 211template <typename Data> 212class Latch 213{ 214 public: 215 typedef MinorBuffer<Data> Buffer; 216 217 protected: 218 /** Delays, in cycles, writing data into the latch and seeing it on the 219 * latched wires */ 220 Cycles delay; 221 222 Buffer buffer; 223 224 public: 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) : 231 delay(delay_), 232 buffer(name, data_name, delay_, 0, (report_backwards ? -delay_ : 0), 233 (report_backwards ? 0 : -delay_)) 234 { } 235 236 public: 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 241 * is written */ 242 class Input 243 { 244 public: 245 typename Buffer::wire inputWire; 246 247 public: 248 Input(typename Buffer::wire input_wire) : 249 inputWire(input_wire) 250 { } 251 }; 252 253 class Output 254 { 255 public: 256 typename Buffer::wire outputWire; 257 258 public: 259 Output(typename Buffer::wire output_wire) : 260 outputWire(output_wire) 261 { } 262 }; 263 264 bool empty() const { return buffer.empty(); } 265 266 /** An interface to just the input of the buffer */ 267 Input input() { return Input(buffer.getWire(0)); } 268 269 /** An interface to just the output of the buffer */ 270 Output output() { return Output(buffer.getWire(-delay)); } 271 272 void minorTrace() const { buffer.minorTrace(); } 273 274 void evaluate() { buffer.advance(); } 275}; 276 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 280 * pipeline. */ 281template <typename ElemType, 282 typename ReportTraits, 283 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> > 284class SelfStallingPipeline : public MinorBuffer<ElemType, ReportTraits> 285{ 286 protected: 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; 291 292 public: 293 /** If true, advance will not advance the pipeline */ 294 bool stalled; 295 296 /** The number of slots with non-bubbles in them */ 297 unsigned int occupancy; 298 299 public: 300 SelfStallingPipeline(const std::string &name, 301 const std::string &data_name, 302 unsigned depth) : 303 MinorBuffer<ElemType, ReportTraits> 304 (name, data_name, depth, 0, -1, -depth), 305 pushWire(this->getWire(0)), 306 popWire(this->getWire(-depth)), 307 stalled(false), 308 occupancy(0) 309 { 310 assert(depth > 0); 311 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(); 316 } 317 318 public: 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 322 * data. */ 323 void push(ElemType &elem) 324 { 325 assert(!alreadyPushed()); 326 *pushWire = elem; 327 if (!BubbleTraits::isBubble(elem)) 328 occupancy++; 329 } 330 331 /** Peek at the end element of the pipe */ 332 ElemType &front() { return *popWire; } 333 334 const ElemType &front() const { return *popWire; } 335 336 /** Have we already pushed onto this pipe without advancing */ 337 bool alreadyPushed() { return !BubbleTraits::isBubble(*pushWire); } 338 339 /** There's data (not a bubble) at the end of the pipe */ 340 bool isPopable() { return !BubbleTraits::isBubble(front()); } 341 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) */ 345 void 346 advance() 347 { 348 bool data_at_end = isPopable(); 349 350 if (!stalled) { 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 */ 354 if (data_at_end) 355 occupancy--; 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(); 362 *pushWire = bubble; 363 } 364 } 365}; 366 367/** Base class for space reservation requestable objects */ 368class Reservable 369{ 370 public: 371 /** Can a slot be reserved? */ 372 virtual bool canReserve() const = 0; 373 374 /** Reserve a slot in whatever structure this is attached to */ 375 virtual void reserve() = 0; 376 377 /** Free a reserved slot */ 378 virtual void freeReservation() = 0; 379}; 380 381/** Wrapper for a queue type to act as a pipeline stage input queue. 382 * Handles capacity management, bubble value suppression and provides 383 * reporting. 384 * 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. */ 389template <typename ElemType, 390 typename ReportTraits = ReportTraitsAdaptor<ElemType>, 391 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> > 392class Queue : public Named, public Reservable 393{ 394 private: 395 std::deque<ElemType> queue; 396 397 /** Number of slots currently reserved for future (reservation 398 * respecting) pushes */ 399 unsigned int numReservedSlots; 400 401 /** Need this here as queues usually don't have a limited capacity */ 402 unsigned int capacity; 403 404 /** Name to use for the data in MinorTrace */ 405 std::string dataName; 406 407 public: 408 Queue(const std::string &name, const std::string &data_name, 409 unsigned int capacity_) : 410 Named(name), 411 numReservedSlots(0), 412 capacity(capacity_), 413 dataName(data_name) 414 { } 415 416 virtual ~Queue() { } 417 418 public: 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 */ 422 void 423 push(ElemType &data) 424 { 425 if (!BubbleTraits::isBubble(data)) { 426 freeReservation(); 427 queue.push_back(data); 428 429 if (queue.size() > capacity) { 430 warn("%s: No space to push data into queue of capacity" 431 " %u, pushing anyway\n", name(), capacity); 432 } 433 434 } 435 } 436 437 /** Clear all allocated space. Be careful how this is used */ 438 void clearReservedSpace() { numReservedSlots = 0; } 439 440 /** Clear a single reserved slot */ 441 void freeReservation() 442 { 443 if (numReservedSlots != 0) 444 numReservedSlots--; 445 } 446 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. */ 450 void 451 reserve() 452 { 453 /* Check reservable space */ 454 if (unreservedRemainingSpace() == 0) 455 warn("%s: No space is reservable in queue", name()); 456 457 numReservedSlots++; 458 } 459 460 bool canReserve() const { return unreservedRemainingSpace() != 0; } 461 462 /** Number of slots available in an empty buffer */ 463 unsigned int totalSpace() const { return capacity; } 464 465 /** Number of slots already occupied in this buffer */ 466 unsigned int occupiedSpace() const { return queue.size(); } 467 468 /** Number of slots which are reserved. */ 469 unsigned int reservedSpace() const { return numReservedSlots; } 470 471 /** Number of slots yet to fill in this buffer. This doesn't include 472 * reservation. */ 473 unsigned int 474 remainingSpace() const 475 { 476 int ret = capacity - queue.size(); 477 478 return (ret < 0 ? 0 : ret); 479 } 480 481 /** Like remainingSpace but does not count reserved spaces */ 482 unsigned int 483 unreservedRemainingSpace() const 484 { 485 int ret = capacity - (queue.size() + numReservedSlots); 486 487 return (ret < 0 ? 0 : ret); 488 } 489 490 /** Head value. Like std::queue::front */ 491 ElemType &front() { return queue.front(); } 492 493 const ElemType &front() const { return queue.front(); } 494 495 /** Pop the head item. Like std::queue::pop */ 496 void pop() { queue.pop_front(); } 497 498 /** Is the queue empty? */ 499 bool empty() const { return queue.empty(); } 500 501 void 502 minorTrace() const 503 { 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()); 509 510 unsigned int num_reserved = reservedSpace(); 511 unsigned int num_occupied = occupiedSpace(); 512 513 int num_printed = 1; 514 /* Bodge to rotate queue to report elements */ 515 while (num_printed <= num_occupied) { 516 ReportTraits::reportData(data, queue[num_printed - 1]); 517 num_printed++; 518 519 if (num_printed <= num_total) 520 data << ','; 521 } 522 523 int num_printed_reserved = 1; 524 /* Show reserved slots */ 525 while (num_printed_reserved <= num_reserved && 526 num_printed <= num_total) 527 { 528 data << 'R'; 529 num_printed_reserved++; 530 num_printed++; 531 532 if (num_printed <= num_total) 533 data << ','; 534 } 535 536 /* And finally pad with empty slots (if there are any) */ 537 while (num_printed <= num_total) { 538 num_printed++; 539 540 if (num_printed <= num_total) 541 data << ','; 542 } 543 544 MINORTRACE("%s=%s\n", dataName, data.str()); 545 } 546}; 547 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 551 * onto the queue. 552 * 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 556 * 557 * The intended use case is the input buffer for pipeline stages, hence the 558 * class name */ 559template <typename ElemType, 560 typename ReportTraits = ReportTraitsAdaptor<ElemType>, 561 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> > 562class InputBuffer : public Reservable 563{ 564 protected: 565 /** Underlying queue */ 566 mutable Queue<ElemType, ReportTraits, BubbleTraits> queue; 567 568 /** Pointer to the single element (if not NULL) */ 569 mutable ElemType *elementPtr; 570 571 public: 572 InputBuffer(const std::string &name, const std::string &data_name, 573 unsigned int capacity_) : 574 queue(name, data_name, capacity_), 575 elementPtr(NULL) 576 { } 577 578 public: 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 */ 582 void 583 setTail(ElemType &new_element) 584 { 585 assert(!elementPtr); 586 if (!BubbleTraits::isBubble(new_element)) { 587 if (queue.empty()) 588 elementPtr = &new_element; 589 else 590 queue.push(new_element); 591 } 592 } 593 594 /** No single element or queue entries */ 595 bool empty() const { return !elementPtr && queue.empty(); } 596 597 /** Return the element, or the front of the queue */ 598 const ElemType &front() const 599 { return (elementPtr ? *elementPtr : queue.front()); } 600 601 ElemType &front() 602 { return (elementPtr ? *elementPtr : queue.front()); } 603 604 /** Pop either the head, or if none, the head of the queue */ 605 void 606 pop() 607 { 608 if (elementPtr) { 609 /* A popped element was expected to be pushed into queue 610 * and so take a reserved space */ 611 elementPtr = NULL; 612 queue.freeReservation(); 613 } else { 614 queue.pop(); 615 } 616 } 617 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 */ 621 void 622 pushTail() const 623 { 624 if (elementPtr) 625 queue.push(*elementPtr); 626 elementPtr = NULL; 627 } 628 629 /** Report elements */ 630 void 631 minorTrace() const 632 { 633 pushTail(); 634 queue.minorTrace(); 635 } 636 637 /** Reservable interface, passed on to queue */ 638 bool canReserve() const { return queue.canReserve(); } 639 void reserve() { queue.reserve(); } 640 void freeReservation() { queue.freeReservation(); } 641 642 /** Like remainingSpace but does not count reserved spaces */ 643 unsigned int 644 unreservedRemainingSpace() 645 { 646 pushTail(); 647 return queue.unreservedRemainingSpace(); 648 } 649}; 650 651} 652 653#endif /* __CPU_MINOR_BUFFERS_HH__ */ 654