schedulebuilder.cc

   1 /*      Copyright (c) 2015 Regents of the University of California
   2  *
   3  *      Author: Brian Demsky <bdemsky@uci.edu>
   4  *
   5  *      This program is free software; you can redistribute it and/or
   6  *      modify it under the terms of the GNU General Public License
   7  *      version 2 as published by the Free Software Foundation.
   8  */
   9
  10 #include "schedulebuilder.h"
  11 #include "mcexecution.h"
  12 #include "mcschedule.h"
  13 #include "constgen.h"
  14 #include "branchrecord.h"
  15 #include "storeloadset.h"
  16
  17 ScheduleBuilder::ScheduleBuilder(MCExecution *_execution, ConstGen *cgen) :
  18         cg(cgen),
  19         execution(_execution),
  20         scheduler(execution->get_scheduler())
  21 {
  22 }
  23
  24 ScheduleBuilder::~ScheduleBuilder() {
  25 }
  26
  27
  28 void neatPrint(EPRecord *r, ConstGen *cgen, bool *satsolution) {
  29         StoreLoadSet * sls=cgen->getStoreLoadSet(r);
  30         r->print();
  31         model_print("address=%p ",  sls->getAddressEncoding(cgen, r, satsolution));
  32         switch(r->getType()) {
  33         case LOAD: {
  34                 model_print("rd=%lu ", sls->getValueEncoding(cgen, r, satsolution));
  35         }
  36                 break;
  37         case STORE: {
  38                 model_print("wr=%lu ", sls->getValueEncoding(cgen, r, satsolution));
  39
  40         }
  41                 break;
  42         case RMW: {
  43                 model_print("rd=%lu ", sls->getRMWRValueEncoding(cgen, r, satsolution));
  44                 model_print("wr=%lu ", sls->getValueEncoding(cgen, r, satsolution));
  45         }
  46         default:
  47                 ;
  48         }
  49         model_print("\n");
  50 }
  51
  52 void ScheduleBuilder::buildSchedule(bool * satsolution) {
  53         threads.push_back(execution->getEPRecord(MCID_FIRST));
  54         lastoperation.push_back(NULL);
  55 #ifdef TSO
  56         stores.push_back(new SnapList<EPRecord *>());
  57         storelastoperation.push_back(NULL);
  58 #endif
  59         while(true) {
  60                 //Loop over threads...getting rid of non-load/store actions
  61                 for(uint index=0;index<threads.size();index++) {
  62                         EPRecord *record=threads[index];
  63                         if (record==NULL)
  64                                 continue;
  65                         EPRecord *next=processRecord(record, satsolution);
  66 #ifdef TSO
  67                         if (next != NULL) {
  68
  69                                 if (next->getType()==STORE) {
  70                                         stores[index]->push_back(next);
  71                                         next=getNextRecord(next);
  72                                 } else if (next->getType()==FENCE) {
  73                                         if (!stores[index]->empty())
  74                                                 scheduler->addWaitPair(next, stores[index]->back());
  75                                         next=getNextRecord(next);
  76                                 } else if (next->getType()==RMW) {
  77                                         if (!stores[index]->empty())
  78                                                 scheduler->addWaitPair(next, stores[index]->back());
  79                                 }
  80                         }
  81 #endif
  82                         if (next!=record) {
  83                                 threads[index]=next;
  84                                 index=index-1;
  85                         }
  86                 }
  87                 //Now we have just memory operations, find the first one...make it go first
  88                 EPRecord *earliest=NULL;
  89
  90                 for(uint index=0;index<threads.size();index++) {
  91                         EPRecord *record=threads[index];
  92
  93                         if (record!=NULL && (earliest==NULL ||
  94                                                                                                          cg->getOrder(record, earliest, satsolution))) {
  95                                 earliest=record;
  96                         }
  97 #ifdef TSO
  98                         if (!stores[index]->empty()) {
  99                                 record=stores[index]->front();
 100
 101                                 if (record!=NULL && (earliest==NULL ||
 102                                                                                                                  cg->getOrder(record, earliest, satsolution))) {
 103                                         earliest=record;
 104                                 }
 105                         }
 106 #endif
 107                 }
 108
 109                 if (earliest == NULL)
 110                         break;
 111
 112                 for(uint index=0;index<threads.size();index++) {
 113                         EPRecord *record=threads[index];
 114                         if (record==earliest) {
 115                                 //Update index in vector for current thread
 116                                 EPRecord *next=getNextRecord(record);
 117                                 threads[index]=next;
 118                                 lastoperation[index]=record;
 119                         } else {
 120                                 EPRecord *last=lastoperation[index];
 121                                 if (last!=NULL) {
 122                                         scheduler->addWaitPair(earliest, last);
 123                                 }
 124                         }
 125 #ifdef TSO
 126                         EPRecord *recstore;
 127                         if (!stores[index]->empty() && (recstore=stores[index]->front())==earliest) {
 128                                 //Update index in vector for current thread
 129                                 stores[index]->pop_front();
 130                                 storelastoperation[index]=recstore;
 131                         } else {
 132                                 EPRecord *last=storelastoperation[index];
 133                                 if (last!=NULL) {
 134                                         scheduler->addWaitPair(earliest, last);
 135                                 }
 136                         }
 137 #endif
 138                 }
 139         }
 140 }
 141
 142 EPRecord * ScheduleBuilder::getNextRecord(EPRecord *record) {
 143         EPRecord *next=record->getNextRecord();
 144
 145         //If this branch exit isn't in the current model, we should not go
 146         //there...
 147         if (record->getType()==BRANCHDIR && next!=NULL) {
 148                 BranchRecord *br=cg->getBranchRecord(record);
 149                 if (!br->hasNextRecord())
 150                         next=NULL;
 151         }
 152
 153         if (next==NULL && record->getBranch()!=NULL) {
 154                 EPValue * epbr=record->getBranch();
 155                 EPRecord *branch=epbr->getRecord();
 156                 if (branch!=NULL) {
 157                         return getNextRecord(branch);
 158                 }
 159         }
 160         return next;
 161 }
 162
 163 EPRecord * ScheduleBuilder::processRecord(EPRecord *record, bool *satsolution) {
 164         switch(record->getType()) {
 165         case LOAD:
 166         case STORE:
 167         case RMW:
 168 #ifdef TSO
 169         case FENCE:
 170 #endif
 171                 return record;
 172         case LOOPENTER: {
 173                 return record->getChildRecord();
 174                 break;
 175         }
 176         case BRANCHDIR: {
 177                 BranchRecord *br=cg->getBranchRecord(record);
 178                 int index=br->getBranchValue(satsolution);
 179
 180                 if (index>=0 && index < br->numDirections()) {
 181                         EPValue *val=record->getValue(index);
 182                         EPRecord *branchrecord=val->getFirstRecord();
 183                         if (branchrecord!=NULL)
 184                                 return branchrecord;
 185                 }
 186                 //otherwise just go past the branch...we don't know what this code is going to do
 187                 break;
 188         }
 189         case LOOPSTART:
 190         case MERGE:
 191         case ALLOC:
 192         case EQUALS:
 193         case FUNCTION:
 194                 /* Continue executing */
 195                 break;
 196         case THREADCREATE:
 197                 /* Start next thread */
 198                 threads.push_back(record->getChildRecord());
 199                 lastoperation.push_back(NULL);
 200 #ifdef TSO
 201                 stores.push_back(new SnapList<EPRecord *>());
 202                 storelastoperation.push_back(NULL);
 203 #endif
 204                 break;
 205         case THREADBEGIN:
 206                 break;
 207         case THREADJOIN:
 208                 break;
 209         case NONLOCALTRANS:
 210                 break;
 211         case LABEL:
 212                 break;
 213         case YIELD:
 214                 break;
 215         default:
 216                 ASSERT(0);
 217         }
 218         return getNextRecord(record);
 219 }