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