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