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                                 if (next->getType()==STORE) {
  74                                         stores[index]->push_back(next);
  75                                         next=getNextRecord(next);
  76                                 } else if (next->getType()==FENCE) {
  77                                         if (!stores[index]->empty())
  78                                                 scheduler->addWaitPair(next, stores[index]->back());
  79                                         next=getNextRecord(next);
  80                                 } else if (next->getType()==RMW) {
  81                                         if (!stores[index]->empty())
  82                                                 scheduler->addWaitPair(next, stores[index]->back());
  83                                 }
  84                         }
  85 #endif
  86                         if (next!=record) {
  87 #ifdef DUMP_SAT_SCHEDULE
  88                                 neatPrint(record, cg, satsolution);
  89 #endif
  90                                 threads[index]=next;
  91                                 index=index-1;
  92                         }
  93                 }
  94                 //Now we have just memory operations, find the first one...make it go first
  95                 EPRecord *earliest=NULL;
  96                 for(uint index=0;index<threads.size();index++) {
  97                         EPRecord *record=threads[index];
  98
  99                         if (record!=NULL && (earliest==NULL ||
 100                                                                                                          cg->getOrder(record, earliest, satsolution))) {
 101                                 earliest=record;
 102                         }
 103 #ifdef TSO
 104                         if (!stores[index]->empty()) {
 105                                 record=stores[index]->front();
 106                                 if (record!=NULL && (earliest==NULL ||
 107                                                                                                                  cg->getOrder(record, earliest, satsolution))) {
 108                                         earliest=record;
 109                                 }
 110                         }
 111 #endif
 112                 }
 113
 114                 if (earliest == NULL)
 115                         break;
 116
 117 #ifdef DUMP_SAT_SCHEDULE
 118                 neatPrint(earliest, cg, satsolution);
 119 #endif
 120
 121                 for(uint index=0;index<threads.size();index++) {
 122                         EPRecord *record=threads[index];
 123                         if (record==earliest) {
 124                                 //Update index in vector for current thread
 125                                 EPRecord *next=getNextRecord(record);
 126                                 threads[index]=next;
 127                                 lastoperation[index]=record;
 128                         } else {
 129                                 EPRecord *last=lastoperation[index];
 130                                 if (last!=NULL) {
 131                                         scheduler->addWaitPair(earliest, last);
 132                                 }
 133                         }
 134 #ifdef TSO
 135                         EPRecord *recstore;
 136                         if (!stores[index]->empty() && (recstore=stores[index]->front())==earliest) {
 137                                 //Update index in vector for current thread
 138                                 stores[index]->pop_front();
 139                                 storelastoperation[index]=recstore;
 140                         } else {
 141                                 EPRecord *last=storelastoperation[index];
 142                                 if (last!=NULL) {
 143                                         scheduler->addWaitPair(earliest, last);
 144                                 }
 145                         }
 146 #endif
 147                 }
 148         }
 149 }
 150
 151 EPRecord * ScheduleBuilder::getNextRecord(EPRecord *record) {
 152         EPRecord *next=record->getNextRecord();
 153
 154         //If this branch exit isn't in the current model, we should not go
 155         //there...
 156         if (record->getType()==BRANCHDIR && next!=NULL) {
 157                 BranchRecord *br=cg->getBranchRecord(record);
 158                 if (!br->hasNextRecord())
 159                         next=NULL;
 160         }
 161
 162         if (next==NULL && record->getBranch()!=NULL) {
 163                 EPValue * epbr=record->getBranch();
 164                 EPRecord *branch=epbr->getRecord();
 165                 if (branch!=NULL) {
 166                         return getNextRecord(branch);
 167                 }
 168         }
 169         return next;
 170 }
 171
 172 EPRecord * ScheduleBuilder::processRecord(EPRecord *record, bool *satsolution) {
 173         switch(record->getType()) {
 174         case LOAD:
 175         case STORE:
 176         case RMW:
 177 #ifdef TSO
 178         case FENCE:
 179 #endif
 180                 return record;
 181         case LOOPENTER: {
 182                 return record->getChildRecord();
 183                 break;
 184         }
 185         case BRANCHDIR: {
 186                 BranchRecord *br=cg->getBranchRecord(record);
 187                 int index=br->getBranchValue(satsolution);
 188
 189                 if (index>=0 && index < br->numDirections()) {
 190                         EPValue *val=record->getValue(index);
 191                         EPRecord *branchrecord=val->getFirstRecord();
 192                         if (branchrecord!=NULL)
 193                                 return branchrecord;
 194                 }
 195                 //otherwise just go past the branch...we don't know what this code is going to do
 196                 break;
 197         }
 198         case LOOPSTART:
 199         case MERGE:
 200         case ALLOC:
 201         case EQUALS:
 202         case FUNCTION:
 203                 /* Continue executing */
 204                 break;
 205         case THREADCREATE:
 206                 /* Start next thread */
 207                 threads.push_back(record->getChildRecord());
 208                 lastoperation.push_back(NULL);
 209 #ifdef TSO
 210                 stores.push_back(new SnapList<EPRecord *>());
 211                 storelastoperation.push_back(NULL);
 212 #endif
 213                 break;
 214         case THREADBEGIN:
 215                 break;
 216         case THREADJOIN:
 217                 break;
 218         case NONLOCALTRANS:
 219                 break;
 220         case LOOPEXIT:
 221                 break;
 222         case LABEL:
 223                 break;
 224         case YIELD:
 225                 if (model->params.noexecyields)
 226                         return NULL;
 227                 break;
 228         default:
 229                 ASSERT(0);
 230         }
 231         return getNextRecord(record);
 232 }