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         ChangeIterator *cit=changeset->iterator();
  56         for(;cit->hasNext();) {
  57                 MCChange *change=cit->next();
  58                 cit->remove();
  59                 if (completedset->contains(change)) {
  60                         delete change;
  61                         continue;
  62                 }
  63                 if (change->isFunction()) {
  64                         processFunction(change);
  65                 } else if (change->isEquals()) {
  66                         processEquals(change);
  67                 } else if (change->isLoad()) {
  68                         processLoad(change);
  69                 } else if (change->isRMW()) {
  70                         processRMW(change);
  71                 } else if (change->isStore()) {
  72                         processStore(change);
  73                 } else ASSERT(false);
  74                 completedset->add(change);
  75         }
  76         delete cit;
  77
  78         for(cit=completedset->iterator();cit->hasNext();) {
  79                 MCChange *change=cit->next();
  80                 cit->remove();
  81                 delete change;
  82         }
  83         delete cit;
  84 }
  85
  86 void Planner::processFunction(MCChange * change) {
  87         processNewReturnValue(change);
  88 }
  89
  90 void Planner::processEquals(MCChange * change) {
  91         processNewReturnValue(change);
  92 }
  93
  94 void Planner::processRMW(MCChange * change) {
  95         switch(change->getIndex()) {
  96         case VC_ADDRINDEX:
  97                 processNewStoreAddress(change);
  98                 break;
  99         case VC_RMWOUTINDEX:
 100                 processNewStoreValue(change);
 101                 break;
 102         case VC_VALOUTINDEX:
 103                 //Return value of the RMW action
 104                 processNewReturnValue(change);
 105                 break;
 106         default:
 107                 ASSERT(false);
 108         }
 109 }
 110
 111 void Planner::processLoad(MCChange * change) {
 112         switch(change->getIndex()) {
 113         case VC_ADDRINDEX:
 114                 processNewLoadAddress(change);
 115                 break;
 116         case VC_VALOUTINDEX:
 117                 processNewReturnValue(change);
 118                 break;
 119         default:
 120                 ASSERT(0);
 121         }
 122 }
 123
 124 void Planner::processStore(MCChange * change) {
 125         switch(change->getIndex()) {
 126         case VC_ADDRINDEX:
 127                 processNewStoreAddress(change);
 128                 break;
 129         case VC_BASEINDEX:
 130                 processNewStoreValue(change);
 131                 break;
 132         default:
 133                 ASSERT(0);
 134         }
 135 }
 136
 137 /** This function propagate news values that a function or add
 138                 operation may generate.
 139 */
 140
 141 void Planner::processNewReturnValue(MCChange *change) {
 142         EPRecord *record=change->getRecord();
 143         EPRecordSet *dependences=e->getDependences(record);
 144         if (dependences==NULL)
 145                 return;
 146         EPRecordIterator *rit=dependences->iterator();
 147         while(rit->hasNext()) {
 148                 struct RecordIntPair *deprecord=rit->next();
 149                 registerValue(deprecord->record, change->getValue(), deprecord->index);
 150         }
 151         delete rit;
 152 }
 153
 154 /** This function registers a new address for a load operation.  We
 155                 iterate over all stores to that new address and grab their values
 156                 and propagate them.
 157 */
 158
 159 void Planner::processNewLoadAddress(MCChange *change) {
 160         EPRecord *load=change->getRecord();
 161         void *addr=(void *)change->getValue();
 162         RecordSet *storeset=e->getStoreTable(addr);
 163         if (storeset == NULL)
 164                 return;
 165         RecordIterator *rit=storeset->iterator();
 166         while(rit->hasNext()) {
 167                 EPRecord *store=rit->next();
 168                 if (e->compatibleStoreLoad(store, load)) {
 169                         IntIterator * it=store->getStoreSet()->iterator();
 170                         while(it->hasNext()) {
 171                                 uint64_t st_val=it->next();
 172                                 //should propagate value further
 173                                 //we should worry about redudant values...
 174                                 registerValue(load, st_val, VC_RFINDEX);
 175                         }
 176                         delete it;
 177                 }
 178         }
 179         delete rit;
 180 }
 181
 182 /** This function processes a new address for a store.  We push our
 183                 values to all loads from that address. */
 184
 185 void Planner::processNewStoreAddress(MCChange *change) {
 186         EPRecord *store=change->getRecord();
 187         void *addr=(void *)change->getValue();
 188         RecordSet *rset=e->getLoadTable(addr);
 189         if (rset == NULL)
 190                 return;
 191         RecordIterator *rit=rset->iterator();
 192         IntHashSet *valset=store->getStoreSet();
 193         while(rit->hasNext()) {
 194                 EPRecord *load=rit->next();
 195                 if (e->compatibleStoreLoad(store, load)) {
 196                         //iterate through all values
 197                         IntIterator *iit=valset->iterator();
 198                         while(iit->hasNext()) {
 199                                 uint64_t val=iit->next();
 200                                 registerValue(load, val, VC_RFINDEX);
 201                         }
 202                         delete iit;
 203                 }
 204         }
 205         delete rit;
 206 }
 207
 208
 209 /** This function pushes a new store value to all loads that share an
 210                 address. */
 211
 212 void Planner::processNewStoreValue(MCChange *change) {
 213         EPRecord *store=change->getRecord();
 214         uint64_t val=change->getValue();
 215         IntHashSet *addrset=store->getSet(VC_ADDRINDEX);
 216         IntIterator *ait=addrset->iterator();
 217         while(ait->hasNext()) {
 218                 void *addr=(void*)ait->next();
 219                 RecordSet *rset=e->getLoadTable(addr);
 220                 if (rset == NULL)
 221                         continue;
 222                 RecordIterator *rit=rset->iterator();
 223                 while(rit->hasNext()) {
 224                         EPRecord *load=rit->next();
 225                         if (e->compatibleStoreLoad(store, load)) {
 226                                 registerValue(load, val, VC_RFINDEX);
 227                         }
 228                 }
 229                 delete rit;
 230         }
 231         delete ait;
 232 }
 233
 234
 235 void Planner::registerValue(EPRecord *record, uint64_t val, unsigned int index) {
 236         switch(record->getType()) {
 237         case LOAD:
 238                 registerLoadValue(record, val, index);
 239                 break;
 240         case RMW:
 241                 registerRMWValue(record, val, index);
 242                 break;
 243         case STORE:
 244                 registerStoreValue(record, val, index);
 245                 break;
 246         case FUNCTION:
 247                 registerFunctionValue(record, val, index);
 248                 break;
 249         case EQUALS:
 250                 registerEqualsValue(record, val, index);
 251                 break;
 252         case BRANCHDIR:
 253                 registerBranchValue(record, val, index);
 254                 break;
 255         case MERGE:
 256                 break;
 257         default:
 258                 model_print("Unrecognized event %u\n",record->getType());
 259         }
 260 }
 261
 262 void Planner::registerBranchValue(EPRecord *record, uint64_t val, unsigned int index) {
 263         record->getSet(index)->add(val);
 264 }
 265
 266 void Planner::registerLoadValue(EPRecord *record, uint64_t val, unsigned int index) {
 267         if (index==VC_ADDRINDEX)
 268                 val+=record->getOffset();
 269
 270         bool is_new=record->getSet(index)->add(val);
 271         if (is_new) {
 272                 switch(index) {
 273                 case VC_ADDRINDEX: {
 274                         e->addLoadTable((void *)val, record);
 275                         MCChange *change=new MCChange(record, val, VC_ADDRINDEX);
 276                         addChange(change);
 277                         break;
 278                 }
 279                 case VC_RFINDEX: {
 280                         //New value we can read...Push it...
 281                         MCChange *change=new MCChange(record, val, VC_VALOUTINDEX);
 282                         addChange(change);
 283                         break;
 284                 }
 285                 default:
 286                         ASSERT(0);
 287                 }
 288         }
 289 }
 290
 291
 292 void Planner::registerRMWValue(EPRecord *record, uint64_t val, unsigned int index) {
 293         if (index==VC_ADDRINDEX)
 294                 val+=record->getOffset();
 295
 296         bool is_new=record->getSet(index)->add(val);
 297         if (is_new) {
 298                 switch(index) {
 299                 case VC_ADDRINDEX:
 300                         doRMWNewAddrChange(record, val);
 301                         break;
 302                 case VC_RFINDEX:
 303                         doRMWRFChange(record, val);
 304                         break;
 305                 case VC_BASEINDEX:
 306                         doRMWBaseChange(record, val);
 307                         break;
 308                 case VC_OLDVALCASINDEX:
 309                         ASSERT(record->getOp()==CAS);
 310                         doRMWOldValChange(record);
 311                         break;
 312                 default:
 313                         ASSERT(0);
 314                 }
 315         }
 316 }
 317
 318 void Planner::doRMWNewAddrChange(EPRecord *record, uint64_t val) {
 319         e->addLoadTable((void *)val, record);
 320         e->addStoreTable((void *)val, record);
 321
 322         //propagate our value to new loads
 323         MCChange * change=new MCChange(record, val, VC_ADDRINDEX);
 324         addChange(change);
 325
 326         //look at new stores and update our read from set
 327         RecordSet *storeset=e->getStoreTable((void *)val);
 328         RecordIterator *rit=storeset->iterator();
 329         while(rit->hasNext()) {
 330                 EPRecord *store=rit->next();
 331
 332                 if (e->compatibleStoreLoad(store, record)) {
 333                         IntIterator * it=store->getStoreSet()->iterator();
 334                         while(it->hasNext()) {
 335                                 uint64_t st_val=it->next();
 336                                 //should propagate value further
 337                                 //we should worry about redudant values...
 338                                 registerRMWValue(record, st_val, VC_RFINDEX);
 339                         }
 340                         delete it;
 341                 }
 342         }
 343         delete rit;
 344 }
 345
 346 void Planner::doRMWRFChange(EPRecord *record, uint64_t readval) {
 347         //Register the new value we might return
 348         MCChange *change=new MCChange(record, readval, VC_VALOUTINDEX);
 349         addChange(change);
 350
 351         if (record->getOp()==CAS) {
 352                 //Register the new value we might store if we are a CAS
 353                 bool is_new=record->getStoreSet()->add(readval);
 354                 if (is_new) {
 355                         MCChange *change=new MCChange(record, readval, VC_RMWOUTINDEX);
 356                         addChange(change);
 357                 }
 358         }
 359 }
 360
 361 void Planner::doRMWBaseChange(EPRecord *record, uint64_t baseval) {
 362         if (record->getOp()==CAS) {
 363                 //Just push the value as though it is our output
 364                 bool is_new=record->getStoreSet()->add(baseval);
 365                 if (is_new) {
 366                         MCChange *change=new MCChange(record, baseval, VC_RMWOUTINDEX);
 367                         addChange(change);
 368                 }
 369         } else if (record->getOp()==ADD) {
 370                 //Tricky here because we could create an infinite propagation...
 371                 //So we drop it...
 372                 //TODO: HANDLE THIS CASE
 373         } else if (record->getOp()==EXC) {
 374                 //no need to propagate output
 375         } else {
 376                 ASSERT(0);
 377         }
 378 }
 379
 380 void Planner::doRMWOldValChange(EPRecord *record) {
 381         //Do nothing, no need to propagate old value...
 382 }
 383
 384 void Planner::registerStoreValue(EPRecord *record, uint64_t val, unsigned int index) {
 385         if (index==VC_ADDRINDEX)
 386                 val+=record->getOffset();
 387
 388         bool is_new=record->getSet(index)->add(val);
 389
 390         if (index==VC_ADDRINDEX) {
 391                 if (is_new)
 392                         e->addStoreTable((void *)val, record);
 393                 MCChange * change=new MCChange(record, val, index);
 394                 addChange(change);
 395         } else if (index==VC_BASEINDEX) {
 396                 MCChange * change=new MCChange(record, val, index);
 397                 addChange(change);
 398         } else model_print("ERROR in RSV\n");
 399 }
 400
 401 void Planner::registerEqualsValue(EPRecord *record, uint64_t val, unsigned int index) {
 402         record->getSet(index)->add(val);
 403 }
 404
 405 void Planner::registerFunctionValue(EPRecord *record, uint64_t val, unsigned int index) {
 406         bool newval=record->getSet(index)->add(val);
 407
 408         if (record->getPhi()) {
 409                 MCChange * change=new MCChange(record, val, VC_FUNCOUTINDEX);
 410                 addChange(change);
 411                 return;
 412         } else if (newval && record->isSharedGoals()) {
 413                 CGoalIterator *cit=record->completedGoalSet()->iterator();
 414                 while(cit->hasNext()) {
 415                         CGoal *goal=cit->next();
 416                         if (goal->getValue(index)==val) {
 417                                 e->evalGoal(record, goal);
 418                         }
 419                 }
 420                 delete cit;
 421         }
 422 }