src/cpu/inorder/resource_sked.hh

   1 /*
   2  * Copyright (c) 2010-2011 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Korey Sewell
  29  *
  30  */
  31
  32 #ifndef __CPU_INORDER_RESOURCE_SKED_HH__
  33 #define __CPU_INORDER_RESOURCE_SKED_HH__
  34
  35 #include <cstdlib>
  36 #include <list>
  37 #include <vector>
  38
  39 /** ScheduleEntry class represents a single function that an instruction
  40     wants to do at any pipeline stage. For example, if an instruction
  41     needs to be decoded and do a branch prediction all in one stage
  42     then each of those tasks would need it's own ScheduleEntry.
  43
  44     Each schedule entry corresponds to some resource that the instruction
  45     wants to interact with.
  46
  47     The file pipeline_traits.cc shows how a typical instruction schedule is
  48     made up of these schedule entries.
  49 */
  50 class ScheduleEntry {
  51   public:
  52     ScheduleEntry(int stage_num, int _priority, int res_num, int _cmd = 0,
  53                   int _idx = 0) :
  54         stageNum(stage_num), resNum(res_num), cmd(_cmd),
  55         idx(_idx), priority(_priority)
  56     { }
  57
  58     /** Stage number to perform this service. */
  59     int stageNum;
  60
  61     /** Resource ID to access */
  62     int resNum;
  63
  64     /** See specific resource for meaning */
  65     unsigned cmd;
  66
  67     /** See specific resource for meaning */
  68     unsigned idx;
  69
  70     /** Some Resources May Need Priority */
  71     int priority;
  72 };
  73
  74 /** The ResourceSked maintains the complete schedule
  75     for an instruction. That schedule includes what
  76     resources an instruction wants to acquire at each
  77     pipeline stage and is represented by a collection
  78     of ScheduleEntry objects (described above) that
  79     must be executed in-order.
  80
  81     In every pipeline stage, the InOrder model will
  82     process all entries on the resource schedule for
  83     that stage and then send the instruction to the next
  84     stage if and only if the instruction successfully
  85     completed each ScheduleEntry.
  86 */
  87 class ResourceSked {
  88   public:
  89     typedef std::list<ScheduleEntry*>::iterator SkedIt;
  90     typedef std::vector<std::list<ScheduleEntry*> > StageList;
  91
  92     ResourceSked();
  93
  94     /** Initializee the current entry pointer to
  95         pipeline stage 0 and the 1st schedule entry
  96     */
  97     void init();
  98
  99     /** Goes through the remaining stages on the schedule
 100         and sums all the remaining entries left to be
 101         processed
 102     */
 103     int size();
 104
 105     /** Is the schedule empty? */
 106     bool empty();
 107
 108     /** Beginning Entry of this schedule */
 109     SkedIt begin();
 110
 111     /** Ending Entry of this schedule */
 112     SkedIt end();
 113
 114     /** Ending Entry of a specified stage */
 115     SkedIt end(int stage_num);
 116
 117     /** Find a schedule entry based on stage and command */
 118     SkedIt find(int stage_num, int cmd);
 119
 120     /** What is the next task for this instruction schedule? */
 121     ScheduleEntry* top();
 122
 123     /** Top() Task is completed, remove it from schedule */
 124     void pop();
 125
 126     /** Add To Schedule based on stage num and priority of
 127         Schedule Entry
 128     */
 129     void push(ScheduleEntry* sked_entry);
 130
 131     /** Add Schedule Entry to be in front of another Entry */
 132     void pushBefore(ScheduleEntry* sked_entry, int sked_cmd, int sked_cmd_idx);
 133
 134     /** Print what's left on the instruction schedule */
 135     void print();
 136
 137     StageList *getStages()
 138     {
 139         return &stages;
 140     }
 141
 142   private:
 143     /** Current Schedule Entry Pointer */
 144     SkedIt curSkedEntry;
 145
 146     /** The Stage-by-Stage Resource Schedule:
 147         Resized to Number of Stages in the constructor
 148     */
 149     StageList stages;
 150
 151     /** Find a place to insert the instruction using  the
 152         schedule entries priority
 153     */
 154     SkedIt findIterByPriority(ScheduleEntry *sked_entry, int stage_num);
 155
 156     /** Find a place to insert the instruction using a particular command
 157         to look for.
 158     */
 159     SkedIt findIterByCommand(ScheduleEntry *sked_entry, int stage_num,
 160                              int sked_cmd, int sked_cmd_idx = -1);
 161 };
 162
 163 /** Wrapper class around the SkedIt iterator in the Resource Sked so that
 164     we can use ++ operator to automatically go to the next available
 165     resource schedule entry but otherwise maintain same functionality
 166     as a normal iterator.
 167 */
 168 class RSkedIt
 169 {
 170   public:
 171     RSkedIt()
 172         : curStage(0), numStages(0)
 173     { }
 174
 175
 176     /** init() must be called before the use of any other member
 177         in the RSkedIt class.
 178     */
 179     void init(ResourceSked* rsked)
 180     {
 181         stages = rsked->getStages();
 182         numStages = stages->size();
 183     }
 184
 185     /* Update the encapsulated "myIt" iterator, but only
 186        update curStage/curStage_end if the iterator is valid.
 187        The iterator could be invalid in the case where
 188        someone is saving the end of a list (i.e. std::list->end())
 189     */
 190     RSkedIt operator=(ResourceSked::SkedIt const &rhs)
 191     {
 192         myIt = rhs;
 193         if (myIt != (*stages)[numStages-1].end()) {
 194             curStage = (*myIt)->stageNum;
 195             curStage_end = (*stages)[curStage].end();
 196         }
 197         return *this;
 198     }
 199
 200     /** Increment to the next entry in current stage.
 201         If no more entries then find the next stage that has
 202         resource schedule to complete.
 203         If no more stages, then return the end() iterator from
 204         the last stage to indicate we are done.
 205     */
 206     RSkedIt &operator++(int unused)
 207     {
 208         if (++myIt == curStage_end) {
 209             curStage++;
 210             while (curStage < numStages) {
 211                 if ((*stages)[curStage].empty()) {
 212                     curStage++;
 213                 } else {
 214                     myIt = (*stages)[curStage].begin();
 215                     curStage_end = (*stages)[curStage].end();
 216                     return *this;
 217                 }
 218             }
 219
 220             myIt = (*stages)[numStages - 1].end();
 221         }
 222
 223         return *this;
 224     }
 225
 226     /** The "pointer" operator can be used on a RSkedIt and it
 227         will use the encapsulated iterator
 228     */
 229     ScheduleEntry* operator->()
 230     {
 231         return *myIt;
 232     }
 233
 234     /** Dereferencing a RSKedIt will access the encapsulated
 235         iterator
 236     */
 237     ScheduleEntry* operator*()
 238     {
 239         return *myIt;
 240     }
 241
 242     /** Equality for RSkedIt only compares the "myIt" iterators,
 243         as the other members are just ancillary
 244     */
 245     bool operator==(RSkedIt const &rhs)
 246     {
 247         return this->myIt == rhs.myIt;
 248     }
 249
 250     /** Inequality for RSkedIt only compares the "myIt" iterators,
 251         as the other members are just ancillary
 252     */
 253     bool operator!=(RSkedIt const &rhs)
 254     {
 255         return this->myIt != rhs.myIt;
 256     }
 257
 258     /* The == and != operator overloads should be sufficient
 259        here if need otherwise direct access to the schedule
 260        iterator, then this can be used */
 261     ResourceSked::SkedIt getIt()
 262     {
 263         return myIt;
 264     }
 265
 266   private:
 267     /** Schedule Iterator that this class is encapsulating */
 268     ResourceSked::SkedIt myIt;
 269
 270     /** Ptr to resource schedule that the 'myIt' iterator
 271         belongs to
 272     */
 273     ResourceSked::StageList *stages;
 274
 275     /**  The last iterator in the current stage. */
 276     ResourceSked::SkedIt curStage_end;
 277
 278     /** Current Stage that "myIt" refers to. */
 279     int curStage;
 280
 281     /** Number of stages in the "*stages" object. */
 282     int numStages;
 283 };
 284
 285 #endif //__CPU_INORDER_RESOURCE_SKED_HH__