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.
11 #include "mcexecution.h"
12 #include "mcschedule.h"
17 Planner::Planner(MCExecution * execution) :
19 changeset(new ChangeHashSet()),
20 completedset(new ChangeHashSet()),
21 cgen(new ConstGen(execution)),
32 bool Planner::is_finished() {
36 void Planner::plan() {
38 e->get_scheduler()->reset();
40 if (!cgen->canReuseEncoding()) {
48 void Planner::addChange(MCChange *change) {
49 if (!changeset->add(change)) {
54 void Planner::processChanges() {
55 while(!changeset->isEmpty()) {
56 MCChange *change=changeset->getFirstKey();
59 changeset->remove(change);
60 if (completedset->contains(change)) {
64 if (change->isFunction()) {
65 processFunction(change);
66 } else if (change->isEquals()) {
67 processEquals(change);
68 } else if (change->isLoad()) {
70 } else if (change->isRMW()) {
72 } else if (change->isStore()) {
75 completedset->add(change);
78 ChangeIterator *cit=completedset->iterator();
80 for(;cit->hasNext();) {
81 MCChange *change=cit->next();
88 void Planner::processFunction(MCChange * change) {
89 processNewReturnValue(change);
92 void Planner::processEquals(MCChange * change) {
93 processNewReturnValue(change);
96 void Planner::processRMW(MCChange * change) {
97 switch(change->getIndex()) {
99 processNewStoreAddress(change);
102 processNewStoreValue(change);
105 //Return value of the RMW action
106 processNewReturnValue(change);
113 void Planner::processLoad(MCChange * change) {
114 switch(change->getIndex()) {
116 processNewLoadAddress(change);
119 processNewReturnValue(change);
126 void Planner::processStore(MCChange * change) {
127 switch(change->getIndex()) {
129 processNewStoreAddress(change);
132 processNewStoreValue(change);
139 /** This function propagate news values that a function or add
140 operation may generate.
143 void Planner::processNewReturnValue(MCChange *change) {
144 EPRecord *record=change->getRecord();
145 EPRecordSet *dependences=e->getDependences(record);
146 if (dependences==NULL)
148 EPRecordIterator *rit=dependences->iterator();
149 while(rit->hasNext()) {
150 struct RecordIntPair *deprecord=rit->next();
151 registerValue(deprecord->record, change->getValue(), deprecord->index);
156 /** This function registers a new address for a load operation. We
157 iterate over all stores to that new address and grab their values
161 void Planner::processNewLoadAddress(MCChange *change) {
162 EPRecord *load=change->getRecord();
163 void *addr=(void *)change->getValue();
164 RecordSet *storeset=e->getStoreTable(addr);
165 if (storeset == NULL)
167 RecordIterator *rit=storeset->iterator();
168 while(rit->hasNext()) {
169 EPRecord *store=rit->next();
170 if (e->compatibleStoreLoad(store, load)) {
171 IntIterator * it=store->getStoreSet()->iterator();
172 while(it->hasNext()) {
173 uint64_t st_val=it->next();
174 //should propagate value further
175 //we should worry about redudant values...
176 registerValue(load, st_val, VC_RFINDEX);
184 /** This function processes a new address for a store. We push our
185 values to all loads from that address. */
187 void Planner::processNewStoreAddress(MCChange *change) {
188 EPRecord *store=change->getRecord();
189 void *addr=(void *)change->getValue();
190 RecordSet *rset=e->getLoadTable(addr);
193 RecordIterator *rit=rset->iterator();
194 IntHashSet *valset=store->getStoreSet();
195 while(rit->hasNext()) {
196 EPRecord *load=rit->next();
197 if (e->compatibleStoreLoad(store, load)) {
198 //iterate through all values
199 IntIterator *iit=valset->iterator();
200 while(iit->hasNext()) {
201 uint64_t val=iit->next();
202 registerValue(load, val, VC_RFINDEX);
211 /** This function pushes a new store value to all loads that share an
214 void Planner::processNewStoreValue(MCChange *change) {
215 EPRecord *store=change->getRecord();
216 uint64_t val=change->getValue();
217 IntHashSet *addrset=store->getSet(VC_ADDRINDEX);
218 IntIterator *ait=addrset->iterator();
219 while(ait->hasNext()) {
220 void *addr=(void*)ait->next();
221 RecordSet *rset=e->getLoadTable(addr);
224 RecordIterator *rit=rset->iterator();
225 while(rit->hasNext()) {
226 EPRecord *load=rit->next();
227 if (e->compatibleStoreLoad(store, load)) {
228 registerValue(load, val, VC_RFINDEX);
237 void Planner::registerValue(EPRecord *record, uint64_t val, unsigned int index) {
238 switch(record->getType()) {
240 registerLoadValue(record, val, index);
243 registerRMWValue(record, val, index);
246 registerStoreValue(record, val, index);
249 registerFunctionValue(record, val, index);
252 registerEqualsValue(record, val, index);
255 registerBranchValue(record, val, index);
260 model_print("Unrecognized event %u\n",record->getType());
264 void Planner::registerBranchValue(EPRecord *record, uint64_t val, unsigned int index) {
265 record->getSet(index)->add(val);
268 void Planner::registerLoadValue(EPRecord *record, uint64_t val, unsigned int index) {
269 if (index==VC_ADDRINDEX)
270 val+=record->getOffset();
272 bool is_new=record->getSet(index)->add(val);
276 e->addLoadTable((void *)val, record);
277 MCChange *change=new MCChange(record, val, VC_ADDRINDEX);
282 //New value we can read...Push it...
283 MCChange *change=new MCChange(record, val, VC_VALOUTINDEX);
294 void Planner::registerRMWValue(EPRecord *record, uint64_t val, unsigned int index) {
295 if (index==VC_ADDRINDEX)
296 val+=record->getOffset();
298 bool is_new=record->getSet(index)->add(val);
302 doRMWNewAddrChange(record, val);
305 doRMWRFChange(record, val);
308 doRMWBaseChange(record, val);
310 case VC_OLDVALCASINDEX:
311 ASSERT(record->getOp()==CAS);
312 doRMWOldValChange(record);
320 void Planner::doRMWNewAddrChange(EPRecord *record, uint64_t val) {
321 e->addLoadTable((void *)val, record);
322 e->addStoreTable((void *)val, record);
324 //propagate our value to new loads
325 MCChange * change=new MCChange(record, val, VC_ADDRINDEX);
328 //look at new stores and update our read from set
329 RecordSet *storeset=e->getStoreTable((void *)val);
330 RecordIterator *rit=storeset->iterator();
331 while(rit->hasNext()) {
332 EPRecord *store=rit->next();
334 if (e->compatibleStoreLoad(store, record)) {
335 IntIterator * it=store->getStoreSet()->iterator();
336 while(it->hasNext()) {
337 uint64_t st_val=it->next();
338 //should propagate value further
339 //we should worry about redudant values...
340 registerRMWValue(record, st_val, VC_RFINDEX);
348 void Planner::doRMWRFChange(EPRecord *record, uint64_t readval) {
349 //Register the new value we might return
350 MCChange *change=new MCChange(record, readval, VC_VALOUTINDEX);
353 if (record->getOp()==CAS) {
354 //Register the new value we might store if we are a CAS
355 bool is_new=record->getStoreSet()->add(readval);
357 MCChange *change=new MCChange(record, readval, VC_RMWOUTINDEX);
363 void Planner::doRMWBaseChange(EPRecord *record, uint64_t baseval) {
364 if (record->getOp()==CAS) {
365 //Just push the value as though it is our output
366 bool is_new=record->getStoreSet()->add(baseval);
368 MCChange *change=new MCChange(record, baseval, VC_RMWOUTINDEX);
371 } else if (record->getOp()==ADD) {
372 //Tricky here because we could create an infinite propagation...
374 //TODO: HANDLE THIS CASE
375 } else if (record->getOp()==EXC) {
376 //no need to propagate output
382 void Planner::doRMWOldValChange(EPRecord *record) {
383 //Do nothing, no need to propagate old value...
386 void Planner::registerStoreValue(EPRecord *record, uint64_t val, unsigned int index) {
387 if (index==VC_ADDRINDEX)
388 val+=record->getOffset();
390 bool is_new=record->getSet(index)->add(val);
392 if (index==VC_ADDRINDEX) {
394 e->addStoreTable((void *)val, record);
395 MCChange * change=new MCChange(record, val, index);
397 } else if (index==VC_BASEINDEX) {
398 MCChange * change=new MCChange(record, val, index);
400 } else model_print("ERROR in RSV\n");
403 void Planner::registerEqualsValue(EPRecord *record, uint64_t val, unsigned int index) {
404 record->getSet(index)->add(val);
407 void Planner::registerFunctionValue(EPRecord *record, uint64_t val, unsigned int index) {
408 bool newval=record->getSet(index)->add(val);
410 if (record->getPhi()) {
411 MCChange * change=new MCChange(record, val, VC_FUNCOUTINDEX);
414 } else if (newval && record->isSharedGoals()) {
415 CGoalIterator *cit=record->completedGoalSet()->iterator();
416 while(cit->hasNext()) {
417 CGoal *goal=cit->next();
418 if (goal->getValue(index)==val) {
419 e->evalGoal(record, goal);