1 /* Copyright (c) 2015 Regents of the University of California
3 * Author: Brian Demsky <bdemsky@uci.edu>
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.
10 #include "schedulebuilder.h"
11 #include "mcexecution.h"
12 #include "mcschedule.h"
14 #include "branchrecord.h"
15 #include "storeloadset.h"
18 ScheduleBuilder::ScheduleBuilder(MCExecution *_execution, ConstGen *cgen) :
20 execution(_execution),
21 scheduler(execution->get_scheduler())
25 ScheduleBuilder::~ScheduleBuilder() {
29 void neatPrint(EPRecord *r, ConstGen *cgen, bool *satsolution) {
31 switch(r->getType()) {
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));
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));
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));
57 void ScheduleBuilder::buildSchedule(bool * satsolution) {
58 threads.push_back(execution->getEPRecord(MCID_FIRST));
59 lastoperation.push_back(NULL);
61 stores.push_back(new SnapList<EPRecord *>());
62 storelastoperation.push_back(NULL);
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];
70 EPRecord *next=processRecord(record, satsolution);
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());
87 #ifdef DUMP_SAT_SCHEDULE
88 neatPrint(record, cg, satsolution);
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];
99 if (record!=NULL && (earliest==NULL ||
100 cg->getOrder(record, earliest, satsolution))) {
104 if (!stores[index]->empty()) {
105 record=stores[index]->front();
106 if (record!=NULL && (earliest==NULL ||
107 cg->getOrder(record, earliest, satsolution))) {
114 if (earliest == NULL)
117 #ifdef DUMP_SAT_SCHEDULE
118 neatPrint(earliest, cg, satsolution);
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);
127 lastoperation[index]=record;
129 EPRecord *last=lastoperation[index];
131 scheduler->addWaitPair(earliest, last);
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;
141 EPRecord *last=storelastoperation[index];
143 scheduler->addWaitPair(earliest, last);
151 EPRecord * ScheduleBuilder::getNextRecord(EPRecord *record) {
152 EPRecord *next=record->getNextRecord();
154 //If this branch exit isn't in the current model, we should not go
156 if (record->getType()==BRANCHDIR && next!=NULL) {
157 BranchRecord *br=cg->getBranchRecord(record);
158 if (!br->hasNextRecord())
162 if (next==NULL && record->getBranch()!=NULL) {
163 EPValue * epbr=record->getBranch();
164 EPRecord *branch=epbr->getRecord();
166 return getNextRecord(branch);
172 EPRecord * ScheduleBuilder::processRecord(EPRecord *record, bool *satsolution) {
173 switch(record->getType()) {
182 return record->getChildRecord();
186 BranchRecord *br=cg->getBranchRecord(record);
187 int index=br->getBranchValue(satsolution);
189 if (index>=0 && index < br->numDirections()) {
190 EPValue *val=record->getValue(index);
191 EPRecord *branchrecord=val->getFirstRecord();
192 if (branchrecord!=NULL)
195 //otherwise just go past the branch...we don't know what this code is going to do
203 /* Continue executing */
206 /* Start next thread */
207 threads.push_back(record->getChildRecord());
208 lastoperation.push_back(NULL);
210 stores.push_back(new SnapList<EPRecord *>());
211 storelastoperation.push_back(NULL);
225 if (model->params.noexecyields)
231 return getNextRecord(record);