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);
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());
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];
97 if (record!=NULL && (earliest==NULL ||
98 cg->getOrder(record, earliest, satsolution))) {
102 if (!stores[index]->empty()) {
103 record=stores[index]->front();
104 if (record!=NULL && (earliest==NULL ||
105 cg->getOrder(record, earliest, satsolution))) {
112 if (earliest == NULL)
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);
121 lastoperation[index]=record;
123 EPRecord *last=lastoperation[index];
125 scheduler->addWaitPair(earliest, last);
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;
135 EPRecord *last=storelastoperation[index];
137 scheduler->addWaitPair(earliest, last);
145 EPRecord * ScheduleBuilder::getNextRecord(EPRecord *record) {
146 EPRecord *next=record->getNextRecord();
148 //If this branch exit isn't in the current model, we should not go
150 if (record->getType()==BRANCHDIR && next!=NULL) {
151 BranchRecord *br=cg->getBranchRecord(record);
152 if (!br->hasNextRecord())
156 if (next==NULL && record->getBranch()!=NULL) {
157 EPValue * epbr=record->getBranch();
158 EPRecord *branch=epbr->getRecord();
160 return getNextRecord(branch);
166 EPRecord * ScheduleBuilder::processRecord(EPRecord *record, bool *satsolution) {
167 switch(record->getType()) {
176 return record->getChildRecord();
180 BranchRecord *br=cg->getBranchRecord(record);
181 int index=br->getBranchValue(satsolution);
183 if (index>=0 && index < br->numDirections()) {
184 EPValue *val=record->getValue(index);
185 EPRecord *branchrecord=val->getFirstRecord();
186 if (branchrecord!=NULL)
189 //otherwise just go past the branch...we don't know what this code is going to do
197 /* Continue executing */
200 /* Start next thread */
201 threads.push_back(record->getChildRecord());
202 lastoperation.push_back(NULL);
204 stores.push_back(new SnapList<EPRecord *>());
205 storelastoperation.push_back(NULL);
219 if (model->params.noexecyields)
225 return getNextRecord(record);