planner.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 "planner.h"
  11 #include "mcexecution.h"
  12 #include "mcschedule.h"
  13 #include "mcutil.h"
  14 #include "constgen.h"
  15 #include "change.h"
  16
  17 Planner::Planner(MCExecution * execution) :
  18         e(execution),
  19         changeset(new ChangeHashSet()),
  20         completedset(new ChangeHashSet()),
  21         cgen(new ConstGen(execution)),
  22         finished(false)
  23 {
  24 }
  25
  26 Planner::~Planner() {
  27         delete changeset;
  28         delete completedset;
  29         delete cgen;
  30 }
  31
  32 bool Planner::is_finished() {
  33         return finished;
  34 }
  35
  36 void Planner::plan() {
  37         DEBUG("Planning\n");
  38         e->get_scheduler()->reset();
  39
  40         if (!cgen->canReuseEncoding()) {
  41                 processChanges();
  42                 cgen->reset();
  43                 if (cgen->process())
  44                         finished=true;
  45         }
  46 }
  47
  48 void Planner::addChange(MCChange *change) {
  49         if (!changeset->add(change)) {
  50                 delete change;
  51         }
  52 }
  53
  54 void Planner::processChanges() {
  55         while(!changeset->isEmpty()) {
  56                 MCChange *change=changeset->getFirstKey();
  57                 if (change==NULL)
  58                         break;
  59                 changeset->remove(change);
  60                 if (completedset->contains(change)) {
  61                         delete change;
  62                         continue;
  63                 }
  64                 if (change->isFunction()) {
  65                         processFunction(change);
  66                 } else if (change->isEquals()) {
  67                         processEquals(change);
  68                 } else if (change->isLoad()) {
  69                         processLoad(change);
  70                 } else if (change->isRMW()) {
  71                         processRMW(change);
  72                 } else if (change->isStore()) {
  73                         processStore(change);
  74                 } else ASSERT(false);
  75                 completedset->add(change);
  76         }
  77
  78         ChangeIterator *cit=completedset->iterator();
  79
  80         for(;cit->hasNext();) {
  81                 MCChange *change=cit->next();
  82                 cit->remove();
  83                 delete change;
  84         }
  85         delete cit;
  86 }
  87
  88 void Planner::processFunction(MCChange * change) {
  89         processNewReturnValue(change);
  90 }
  91
  92 void Planner::processEquals(MCChange * change) {
  93         processNewReturnValue(change);
  94 }
  95
  96 void Planner::processRMW(MCChange * change) {
  97         switch(change->getIndex()) {
  98         case VC_ADDRINDEX:
  99                 processNewStoreAddress(change);
 100                 break;
 101         case VC_RMWOUTINDEX:
 102                 processNewStoreValue(change);
 103                 break;
 104         case VC_VALOUTINDEX:
 105                 //Return value of the RMW action
 106                 processNewReturnValue(change);
 107                 break;
 108         default:
 109                 ASSERT(false);
 110         }
 111 }
 112
 113 void Planner::processLoad(MCChange * change) {
 114         switch(change->getIndex()) {
 115         case VC_ADDRINDEX:
 116                 processNewLoadAddress(change);
 117                 break;
 118         case VC_VALOUTINDEX:
 119                 processNewReturnValue(change);
 120                 break;
 121         default:
 122                 ASSERT(0);
 123         }
 124 }
 125
 126 void Planner::processStore(MCChange * change) {
 127         switch(change->getIndex()) {
 128         case VC_ADDRINDEX:
 129                 processNewStoreAddress(change);
 130                 break;
 131         case VC_BASEINDEX:
 132                 processNewStoreValue(change);
 133                 break;
 134         default:
 135                 ASSERT(0);
 136         }
 137 }
 138
 139 /** This function propagate news values that a function or add
 140                 operation may generate.
 141 */
 142
 143 void Planner::processNewReturnValue(MCChange *change) {
 144         EPRecord *record=change->getRecord();
 145         EPRecordSet *dependences=e->getDependences(record);
 146         if (dependences==NULL)
 147                 return;
 148         EPRecordIterator *rit=dependences->iterator();
 149         while(rit->hasNext()) {
 150                 struct RecordIntPair *deprecord=rit->next();
 151                 registerValue(deprecord->record, change->getValue(), deprecord->index);
 152         }
 153         delete rit;
 154 }
 155
 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
 158                 and propagate them.
 159 */
 160
 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)
 166                 return;
 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);
 177                         }
 178                         delete it;
 179                 }
 180         }
 181         delete rit;
 182 }
 183
 184 /** This function processes a new address for a store.  We push our
 185                 values to all loads from that address. */
 186
 187 void Planner::processNewStoreAddress(MCChange *change) {
 188         EPRecord *store=change->getRecord();
 189         void *addr=(void *)change->getValue();
 190         RecordSet *rset=e->getLoadTable(addr);
 191         if (rset == NULL)
 192                 return;
 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);
 203                         }
 204                         delete iit;
 205                 }
 206         }
 207         delete rit;
 208 }
 209
 210
 211 /** This function pushes a new store value to all loads that share an
 212                 address. */
 213
 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);
 222                 if (rset == NULL)
 223                         continue;
 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);
 229                         }
 230                 }
 231                 delete rit;
 232         }
 233         delete ait;
 234 }
 235
 236
 237 void Planner::registerValue(EPRecord *record, uint64_t val, unsigned int index) {
 238         switch(record->getType()) {
 239         case LOAD:
 240                 registerLoadValue(record, val, index);
 241                 break;
 242         case RMW:
 243                 registerRMWValue(record, val, index);
 244                 break;
 245         case STORE:
 246                 registerStoreValue(record, val, index);
 247                 break;
 248         case FUNCTION:
 249                 registerFunctionValue(record, val, index);
 250                 break;
 251         case EQUALS:
 252                 registerEqualsValue(record, val, index);
 253                 break;
 254         case BRANCHDIR:
 255                 registerBranchValue(record, val, index);
 256                 break;
 257         case MERGE:
 258                 break;
 259         default:
 260                 model_print("Unrecognized event %u\n",record->getType());
 261         }
 262 }
 263
 264 void Planner::registerBranchValue(EPRecord *record, uint64_t val, unsigned int index) {
 265         record->getSet(index)->add(val);
 266 }
 267
 268 void Planner::registerLoadValue(EPRecord *record, uint64_t val, unsigned int index) {
 269         if (index==VC_ADDRINDEX)
 270                 val+=record->getOffset();
 271
 272         bool is_new=record->getSet(index)->add(val);
 273         if (is_new) {
 274                 switch(index) {
 275                 case VC_ADDRINDEX: {
 276                         e->addLoadTable((void *)val, record);
 277                         MCChange *change=new MCChange(record, val, VC_ADDRINDEX);
 278                         addChange(change);
 279                         break;
 280                 }
 281                 case VC_RFINDEX: {
 282                         //New value we can read...Push it...
 283                         MCChange *change=new MCChange(record, val, VC_VALOUTINDEX);
 284                         addChange(change);
 285                         break;
 286                 }
 287                 default:
 288                         ASSERT(0);
 289                 }
 290         }
 291 }
 292
 293
 294 void Planner::registerRMWValue(EPRecord *record, uint64_t val, unsigned int index) {
 295         if (index==VC_ADDRINDEX)
 296                 val+=record->getOffset();
 297
 298         bool is_new=record->getSet(index)->add(val);
 299         if (is_new) {
 300                 switch(index) {
 301                 case VC_ADDRINDEX:
 302                         doRMWNewAddrChange(record, val);
 303                         break;
 304                 case VC_RFINDEX:
 305                         doRMWRFChange(record, val);
 306                         break;
 307                 case VC_BASEINDEX:
 308                         doRMWBaseChange(record, val);
 309                         break;
 310                 case VC_OLDVALCASINDEX:
 311                         ASSERT(record->getOp()==CAS);
 312                         doRMWOldValChange(record);
 313                         break;
 314                 default:
 315                         ASSERT(0);
 316                 }
 317         }
 318 }
 319
 320 void Planner::doRMWNewAddrChange(EPRecord *record, uint64_t val) {
 321         e->addLoadTable((void *)val, record);
 322         e->addStoreTable((void *)val, record);
 323
 324         //propagate our value to new loads
 325         MCChange * change=new MCChange(record, val, VC_ADDRINDEX);
 326         addChange(change);
 327
 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();
 333
 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);
 341                         }
 342                         delete it;
 343                 }
 344         }
 345         delete rit;
 346 }
 347
 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);
 351         addChange(change);
 352
 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);
 356                 if (is_new) {
 357                         MCChange *change=new MCChange(record, readval, VC_RMWOUTINDEX);
 358                         addChange(change);
 359                 }
 360         }
 361 }
 362
 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);
 367                 if (is_new) {
 368                         MCChange *change=new MCChange(record, baseval, VC_RMWOUTINDEX);
 369                         addChange(change);
 370                 }
 371         } else if (record->getOp()==ADD) {
 372                 //Tricky here because we could create an infinite propagation...
 373                 //So we drop it...
 374                 //TODO: HANDLE THIS CASE
 375         } else if (record->getOp()==EXC) {
 376                 //no need to propagate output
 377         } else {
 378                 ASSERT(0);
 379         }
 380 }
 381
 382 void Planner::doRMWOldValChange(EPRecord *record) {
 383         //Do nothing, no need to propagate old value...
 384 }
 385
 386 void Planner::registerStoreValue(EPRecord *record, uint64_t val, unsigned int index) {
 387         if (index==VC_ADDRINDEX)
 388                 val+=record->getOffset();
 389
 390         bool is_new=record->getSet(index)->add(val);
 391
 392         if (index==VC_ADDRINDEX) {
 393                 if (is_new)
 394                         e->addStoreTable((void *)val, record);
 395                 MCChange * change=new MCChange(record, val, index);
 396                 addChange(change);
 397         } else if (index==VC_BASEINDEX) {
 398                 MCChange * change=new MCChange(record, val, index);
 399                 addChange(change);
 400         } else model_print("ERROR in RSV\n");
 401 }
 402
 403 void Planner::registerEqualsValue(EPRecord *record, uint64_t val, unsigned int index) {
 404         record->getSet(index)->add(val);
 405 }
 406
 407 void Planner::registerFunctionValue(EPRecord *record, uint64_t val, unsigned int index) {
 408         bool newval=record->getSet(index)->add(val);
 409
 410         if (record->getPhi()) {
 411                 MCChange * change=new MCChange(record, val, VC_FUNCOUTINDEX);
 412                 addChange(change);
 413                 return;
 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);
 420                         }
 421                 }
 422                 delete cit;
 423         }
 424 }