funcnode.cc

   1 #include "action.h"
   2 #include "history.h"
   3 #include "funcnode.h"
   4 #include "funcinst.h"
   5 #include "predicate.h"
   6 #include "concretepredicate.h"
   7
   8 #include "model.h"
   9
  10 FuncNode::FuncNode(ModelHistory * history) :
  11         history(history),
  12         exit_count(0),
  13         marker(1),
  14         func_inst_map(),
  15         inst_list(),
  16         entry_insts(),
  17         predicate_tree_position(),
  18         edge_table(32),
  19         out_edges()
  20 {
  21         predicate_tree_entry = new Predicate(NULL, true);
  22         predicate_tree_entry->add_predicate_expr(NOPREDICATE, NULL, true);
  23         predicate_tree_exit = new Predicate(NULL, false, true);
  24         predicate_tree_exit->set_depth(MAX_DEPTH);
  25
  26         /* Snapshot data structures below */
  27         action_list_buffer = new SnapList<action_list_t *>();
  28         read_locations = new loc_set_t();
  29         write_locations = new loc_set_t();
  30         val_loc_map = new HashTable<uint64_t, loc_set_t *, uint64_t, 0, snapshot_malloc, snapshot_calloc, snapshot_free, int64_hash>();
  31         loc_may_equal_map = new HashTable<void *, loc_set_t *, uintptr_t, 0>();
  32
  33         //values_may_read_from = new value_set_t();
  34 }
  35
  36 /* Reallocate snapshotted memories when new executions start */
  37 void FuncNode::set_new_exec_flag()
  38 {
  39         action_list_buffer = new SnapList<action_list_t *>();
  40         read_locations = new loc_set_t();
  41         write_locations = new loc_set_t();
  42         val_loc_map = new HashTable<uint64_t, loc_set_t *, uint64_t, 0, snapshot_malloc, snapshot_calloc, snapshot_free, int64_hash>();
  43         loc_may_equal_map = new HashTable<void *, loc_set_t *, uintptr_t, 0>();
  44
  45         //values_may_read_from = new value_set_t();
  46 }
  47
  48 /* Check whether FuncInst with the same type, position, and location
  49  * as act has been added to func_inst_map or not. If not, add it.
  50  */
  51 void FuncNode::add_inst(ModelAction *act)
  52 {
  53         ASSERT(act);
  54         const char * position = act->get_position();
  55
  56         /* THREAD* actions, ATOMIC_LOCK, ATOMIC_TRYLOCK, and ATOMIC_UNLOCK
  57          * actions are not tagged with their source line numbers
  58          */
  59         if (position == NULL)
  60                 return;
  61
  62         FuncInst * func_inst = func_inst_map.get(position);
  63
  64         /* This position has not been inserted into hashtable before */
  65         if (func_inst == NULL) {
  66                 func_inst = create_new_inst(act);
  67                 func_inst_map.put(position, func_inst);
  68                 return;
  69         }
  70
  71         /* Volatile variables that use ++ or -- syntax may result in read and write actions with the same position */
  72         if (func_inst->get_type() != act->get_type()) {
  73                 FuncInst * collision_inst = func_inst->search_in_collision(act);
  74
  75                 if (collision_inst == NULL) {
  76                         collision_inst = create_new_inst(act);
  77                         func_inst->add_to_collision(collision_inst);
  78                         return;
  79                 } else {
  80                         func_inst = collision_inst;
  81                 }
  82         }
  83
  84         ASSERT(func_inst->get_type() == act->get_type());
  85         int curr_execution_number = model->get_execution_number();
  86
  87         /* Reset locations when new executions start */
  88         if (func_inst->get_execution_number() != curr_execution_number) {
  89                 func_inst->set_location(act->get_location());
  90                 func_inst->set_execution_number(curr_execution_number);
  91         }
  92
  93         /* Mark the memory location of such inst as not unique */
  94         if (func_inst->get_location() != act->get_location())
  95                 func_inst->not_single_location();
  96 }
  97
  98 FuncInst * FuncNode::create_new_inst(ModelAction * act)
  99 {
 100         FuncInst * func_inst = new FuncInst(act, this);
 101         int exec_num = model->get_execution_number();
 102         func_inst->set_execution_number(exec_num);
 103
 104         inst_list.push_back(func_inst);
 105
 106         return func_inst;
 107 }
 108
 109
 110 /* Get the FuncInst with the same type, position, and location
 111  * as act
 112  *
 113  * @return FuncInst with the same type, position, and location as act */
 114 FuncInst * FuncNode::get_inst(ModelAction *act)
 115 {
 116         ASSERT(act);
 117         const char * position = act->get_position();
 118
 119         /* THREAD* actions, ATOMIC_LOCK, ATOMIC_TRYLOCK, and ATOMIC_UNLOCK
 120          * actions are not tagged with their source line numbers
 121          */
 122         if (position == NULL)
 123                 return NULL;
 124
 125         FuncInst * inst = func_inst_map.get(position);
 126         if (inst == NULL)
 127                 return NULL;
 128
 129         action_type inst_type = inst->get_type();
 130         action_type act_type = act->get_type();
 131
 132         if (inst_type == act_type) {
 133                 return inst;
 134         }
 135         /* RMWRCAS actions are converted to RMW or READ actions */
 136         else if (inst_type == ATOMIC_RMWRCAS &&
 137                                          (act_type == ATOMIC_RMW || act_type == ATOMIC_READ)) {
 138                 return inst;
 139         }
 140         /* Return the FuncInst in the collision list */
 141         else {
 142                 return inst->search_in_collision(act);
 143         }
 144 }
 145
 146
 147 void FuncNode::add_entry_inst(FuncInst * inst)
 148 {
 149         if (inst == NULL)
 150                 return;
 151
 152         mllnode<FuncInst *> * it;
 153         for (it = entry_insts.begin();it != NULL;it = it->getNext()) {
 154                 if (inst == it->getVal())
 155                         return;
 156         }
 157
 158         entry_insts.push_back(inst);
 159 }
 160
 161 /**
 162  * @brief Convert ModelAdtion list to FuncInst list
 163  * @param act_list A list of ModelActions
 164  */
 165 void FuncNode::update_tree(action_list_t * act_list)
 166 {
 167         if (act_list == NULL || act_list->size() == 0)
 168                 return;
 169
 170         HashTable<void *, value_set_t *, uintptr_t, 0> * write_history = history->getWriteHistory();
 171
 172         /* build inst_list from act_list for later processing */
 173         func_inst_list_t inst_list;
 174         action_list_t rw_act_list;
 175
 176         for (sllnode<ModelAction *> * it = act_list->begin();it != NULL;it = it->getNext()) {
 177                 ModelAction * act = it->getVal();
 178                 FuncInst * func_inst = get_inst(act);
 179                 void * loc = act->get_location();
 180
 181                 if (func_inst == NULL)
 182                         continue;
 183
 184                 inst_list.push_back(func_inst);
 185                 bool act_added = false;
 186
 187                 if (act->is_write()) {
 188                         rw_act_list.push_back(act);
 189                         act_added = true;
 190                         if (!write_locations->contains(loc)) {
 191                                 write_locations->add(loc);
 192                                 history->update_loc_wr_func_nodes_map(loc, this);
 193                         }
 194                 }
 195
 196                 if (act->is_read()) {
 197                         if (!act_added)
 198                                 rw_act_list.push_back(act);
 199
 200                         /* If func_inst may only read_from a single location, then:
 201                          *
 202                          * The first time an action reads from some location,
 203                          * import all the values that have been written to this
 204                          * location from ModelHistory and notify ModelHistory
 205                          * that this FuncNode may read from this location.
 206                          */
 207                         if (!read_locations->contains(loc) && func_inst->is_single_location()) {
 208                                 read_locations->add(loc);
 209                                 value_set_t * write_values = write_history->get(loc);
 210                                 add_to_val_loc_map(write_values, loc);
 211                                 history->update_loc_rd_func_nodes_map(loc, this);
 212                         }
 213                 }
 214         }
 215
 216 //      model_print("function %s\n", func_name);
 217 //      print_val_loc_map();
 218
 219         update_inst_tree(&inst_list);
 220         update_predicate_tree(&rw_act_list);
 221
 222 //      print_predicate_tree();
 223 }
 224
 225 /**
 226  * @brief Link FuncInsts in inst_list  - add one FuncInst to another's predecessors and successors
 227  * @param inst_list A list of FuncInsts
 228  */
 229 void FuncNode::update_inst_tree(func_inst_list_t * inst_list)
 230 {
 231         if (inst_list == NULL)
 232                 return;
 233         else if (inst_list->size() == 0)
 234                 return;
 235
 236         /* start linking */
 237         sllnode<FuncInst *>* it = inst_list->begin();
 238         sllnode<FuncInst *>* prev;
 239
 240         /* add the first instruction to the list of entry insts */
 241         FuncInst * entry_inst = it->getVal();
 242         add_entry_inst(entry_inst);
 243
 244         it = it->getNext();
 245         while (it != NULL) {
 246                 prev = it->getPrev();
 247
 248                 FuncInst * prev_inst = prev->getVal();
 249                 FuncInst * curr_inst = it->getVal();
 250
 251                 prev_inst->add_succ(curr_inst);
 252                 curr_inst->add_pred(prev_inst);
 253
 254                 it = it->getNext();
 255         }
 256 }
 257
 258 void FuncNode::update_predicate_tree(action_list_t * act_list)
 259 {
 260         if (act_list == NULL || act_list->size() == 0)
 261                 return;
 262
 263         incr_marker();
 264
 265         /* Map a FuncInst to the its predicate */
 266         HashTable<FuncInst *, Predicate *, uintptr_t, 0> inst_pred_map(128);
 267
 268         // Number FuncInsts to detect loops
 269         HashTable<FuncInst *, uint32_t, uintptr_t, 0> inst_id_map(128);
 270         uint32_t inst_counter = 0;
 271
 272         /* Only need to store the locations of read actions */
 273         HashTable<void *, ModelAction *, uintptr_t, 0> loc_act_map(128);
 274
 275         sllnode<ModelAction *> *it = act_list->begin();
 276         Predicate * curr_pred = predicate_tree_entry;
 277         while (it != NULL) {
 278                 ModelAction * next_act = it->getVal();
 279                 FuncInst * next_inst = get_inst(next_act);
 280                 next_inst->set_associated_act(next_act, marker);
 281
 282                 SnapVector<Predicate *> unset_predicates = SnapVector<Predicate *>();
 283                 bool branch_found = follow_branch(&curr_pred, next_inst, next_act, &unset_predicates);
 284
 285                 // A branch with unset predicate expression is detected
 286                 if (!branch_found && unset_predicates.size() != 0) {
 287                         ASSERT(unset_predicates.size() == 1);
 288                         Predicate * one_branch = unset_predicates[0];
 289
 290                         bool amended = amend_predicate_expr(&curr_pred, next_inst, next_act);
 291                         if (amended)
 292                                 continue;
 293                         else {
 294                                 curr_pred = one_branch;
 295                                 branch_found = true;
 296                         }
 297                 }
 298
 299                 // Detect loops
 300                 if (!branch_found && inst_id_map.contains(next_inst)) {
 301                         FuncInst * curr_inst = curr_pred->get_func_inst();
 302                         uint32_t curr_id = inst_id_map.get(curr_inst);
 303                         uint32_t next_id = inst_id_map.get(next_inst);
 304
 305                         if (curr_id >= next_id) {
 306                                 Predicate * old_pred = inst_pred_map.get(next_inst);
 307                                 Predicate * back_pred = old_pred->get_parent();
 308
 309                                 curr_pred->add_backedge(back_pred);
 310                                 curr_pred = back_pred;
 311                                 continue;
 312                         }
 313                 }
 314
 315                 // Generate new branches
 316                 if (!branch_found) {
 317                         SnapVector<struct half_pred_expr *> half_pred_expressions;
 318                         infer_predicates(next_inst, next_act, &loc_act_map, &half_pred_expressions);
 319                         generate_predicates(&curr_pred, next_inst, &half_pred_expressions);
 320                         continue;
 321                 }
 322
 323                 if (next_act->is_write())
 324                         curr_pred->set_write(true);
 325
 326                 if (next_act->is_read()) {
 327                         loc_act_map.put(next_act->get_location(), next_act);
 328                 }
 329
 330                 inst_pred_map.put(next_inst, curr_pred);
 331                 if (!inst_id_map.contains(next_inst))
 332                         inst_id_map.put(next_inst, inst_counter++);
 333
 334                 it = it->getNext();
 335                 curr_pred->incr_expl_count();
 336         }
 337
 338         curr_pred->set_exit(predicate_tree_exit);
 339 }
 340
 341 /* Given curr_pred and next_inst, find the branch following curr_pred that
 342  * contains next_inst and the correct predicate.
 343  * @return true if branch found, false otherwise.
 344  */
 345 bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst,
 346 ModelAction * next_act, SnapVector<Predicate *> * unset_predicates)
 347 {
 348         /* Check if a branch with func_inst and corresponding predicate exists */
 349         bool branch_found = false;
 350         ModelVector<Predicate *> * branches = (*curr_pred)->get_children();
 351         for (uint i = 0;i < branches->size();i++) {
 352                 Predicate * branch = (*branches)[i];
 353                 if (branch->get_func_inst() != next_inst)
 354                         continue;
 355
 356                 /* Check against predicate expressions */
 357                 bool predicate_correct = true;
 358                 PredExprSet * pred_expressions = branch->get_pred_expressions();
 359                 PredExprSetIter * pred_expr_it = pred_expressions->iterator();
 360
 361                 /* Only read and rmw actions my have unset predicate expressions */
 362                 if (pred_expressions->getSize() == 0) {
 363                         predicate_correct = false;
 364                         unset_predicates->push_back(branch);
 365                 }
 366
 367                 while (pred_expr_it->hasNext()) {
 368                         pred_expr * pred_expression = pred_expr_it->next();
 369                         uint64_t last_read, next_read;
 370                         bool equality;
 371
 372                         switch(pred_expression->token) {
 373                                 case NOPREDICATE:
 374                                         predicate_correct = true;
 375                                         break;
 376                                 case EQUALITY:
 377                                         FuncInst * to_be_compared;
 378                                         ModelAction * last_act;
 379
 380                                         to_be_compared = pred_expression->func_inst;
 381                                         last_act = to_be_compared->get_associated_act(marker);
 382
 383                                         last_read = last_act->get_reads_from_value();
 384                                         next_read = next_act->get_reads_from_value();
 385                                         equality = (last_read == next_read);
 386                                         if (equality != pred_expression->value)
 387                                                 predicate_correct = false;
 388
 389                                         break;
 390                                 case NULLITY:
 391                                         next_read = next_act->get_reads_from_value();
 392                                         // TODO: implement likely to be null
 393                                         equality = ( (void*) (next_read & 0xffffffff) == NULL);
 394                                         if (equality != pred_expression->value)
 395                                                 predicate_correct = false;
 396                                         break;
 397                                 default:
 398                                         predicate_correct = false;
 399                                         model_print("unkown predicate token\n");
 400                                         break;
 401                         }
 402                 }
 403
 404                 if (predicate_correct) {
 405                         *curr_pred = branch;
 406                         branch_found = true;
 407                         break;
 408                 }
 409         }
 410
 411         return branch_found;
 412 }
 413
 414 /* Infer predicate expressions, which are generated in FuncNode::generate_predicates */
 415 void FuncNode::infer_predicates(FuncInst * next_inst, ModelAction * next_act,
 416 HashTable<void *, ModelAction *, uintptr_t, 0> * loc_act_map,
 417 SnapVector<struct half_pred_expr *> * half_pred_expressions)
 418 {
 419         void * loc = next_act->get_location();
 420
 421         if (next_inst->is_read()) {
 422                 /* read + rmw */
 423                 if ( loc_act_map->contains(loc) ) {
 424                         ModelAction * last_act = loc_act_map->get(loc);
 425                         FuncInst * last_inst = get_inst(last_act);
 426                         struct half_pred_expr * expression = new half_pred_expr(EQUALITY, last_inst);
 427                         half_pred_expressions->push_back(expression);
 428                 } else if ( next_inst->is_single_location() ) {
 429                         loc_set_t * loc_may_equal = loc_may_equal_map->get(loc);
 430
 431                         if (loc_may_equal != NULL) {
 432                                 loc_set_iter * loc_it = loc_may_equal->iterator();
 433                                 while (loc_it->hasNext()) {
 434                                         void * neighbor = loc_it->next();
 435                                         if (loc_act_map->contains(neighbor)) {
 436                                                 ModelAction * last_act = loc_act_map->get(neighbor);
 437                                                 FuncInst * last_inst = get_inst(last_act);
 438
 439                                                 struct half_pred_expr * expression = new half_pred_expr(EQUALITY, last_inst);
 440                                                 half_pred_expressions->push_back(expression);
 441                                         }
 442                                 }
 443                         }
 444                 } else {
 445                         // next_inst is not single location
 446                         uint64_t read_val = next_act->get_reads_from_value();
 447
 448                         // only infer NULLITY predicate when it is actually NULL.
 449                         if ( (void*)read_val == NULL) {
 450                                 struct half_pred_expr * expression = new half_pred_expr(NULLITY, NULL);
 451                                 half_pred_expressions->push_back(expression);
 452                         }
 453                 }
 454         } else {
 455                 /* Pure writes */
 456                 // TODO: do anything here?
 457         }
 458 }
 459
 460 /* Able to generate complex predicates when there are multiple predciate expressions */
 461 void FuncNode::generate_predicates(Predicate ** curr_pred, FuncInst * next_inst,
 462 SnapVector<struct half_pred_expr *> * half_pred_expressions)
 463 {
 464         if (half_pred_expressions->size() == 0) {
 465                 Predicate * new_pred = new Predicate(next_inst);
 466                 (*curr_pred)->add_child(new_pred);
 467                 new_pred->set_parent(*curr_pred);
 468
 469                 /* entry predicates and predicates containing pure write actions
 470                  * have no predicate expressions */
 471                 if ( (*curr_pred)->is_entry_predicate() )
 472                         new_pred->add_predicate_expr(NOPREDICATE, NULL, true);
 473                 else if (next_inst->is_write()) {
 474                         /* next_inst->is_write() <==> pure writes */
 475                         new_pred->add_predicate_expr(NOPREDICATE, NULL, true);
 476                 }
 477
 478                 return;
 479         }
 480
 481         SnapVector<Predicate *> predicates;
 482
 483         struct half_pred_expr * half_expr = (*half_pred_expressions)[0];
 484         predicates.push_back(new Predicate(next_inst));
 485         predicates.push_back(new Predicate(next_inst));
 486
 487         predicates[0]->add_predicate_expr(half_expr->token, half_expr->func_inst, true);
 488         predicates[1]->add_predicate_expr(half_expr->token, half_expr->func_inst, false);
 489
 490         for (uint i = 1;i < half_pred_expressions->size();i++) {
 491                 half_expr = (*half_pred_expressions)[i];
 492
 493                 uint old_size = predicates.size();
 494                 for (uint j = 0;j < old_size;j++) {
 495                         Predicate * pred = predicates[j];
 496                         Predicate * new_pred = new Predicate(next_inst);
 497                         new_pred->copy_predicate_expr(pred);
 498
 499                         pred->add_predicate_expr(half_expr->token, half_expr->func_inst, true);
 500                         new_pred->add_predicate_expr(half_expr->token, half_expr->func_inst, false);
 501
 502                         predicates.push_back(new_pred);
 503                 }
 504         }
 505
 506         for (uint i = 0;i < predicates.size();i++) {
 507                 Predicate * pred= predicates[i];
 508                 (*curr_pred)->add_child(pred);
 509                 pred->set_parent(*curr_pred);
 510         }
 511
 512         /* Free memories allocated by infer_predicate */
 513         for (uint i = 0;i < half_pred_expressions->size();i++) {
 514                 struct half_pred_expr * tmp = (*half_pred_expressions)[i];
 515                 snapshot_free(tmp);
 516         }
 517 }
 518
 519 /* Amend predicates that contain no predicate expressions. Currenlty only amend with NULLITY predicates */
 520 bool FuncNode::amend_predicate_expr(Predicate ** curr_pred, FuncInst * next_inst, ModelAction * next_act)
 521 {
 522         // there should only be only child
 523         Predicate * unset_pred = (*curr_pred)->get_children()->back();
 524         uint64_t read_val = next_act->get_reads_from_value();
 525
 526         // only generate NULLITY predicate when it is actually NULL.
 527         if ( !next_inst->is_single_location() && (void*)read_val == NULL ) {
 528                 Predicate * new_pred = new Predicate(next_inst);
 529
 530                 (*curr_pred)->add_child(new_pred);
 531                 new_pred->set_parent(*curr_pred);
 532
 533                 unset_pred->add_predicate_expr(NULLITY, NULL, false);
 534                 new_pred->add_predicate_expr(NULLITY, NULL, true);
 535
 536                 return true;
 537         }
 538
 539         return false;
 540 }
 541
 542 void FuncNode::add_to_val_loc_map(uint64_t val, void * loc)
 543 {
 544         loc_set_t * locations = val_loc_map->get(val);
 545
 546         if (locations == NULL) {
 547                 locations = new loc_set_t();
 548                 val_loc_map->put(val, locations);
 549         }
 550
 551         update_loc_may_equal_map(loc, locations);
 552         locations->add(loc);
 553         // values_may_read_from->add(val);
 554 }
 555
 556 void FuncNode::add_to_val_loc_map(value_set_t * values, void * loc)
 557 {
 558         if (values == NULL)
 559                 return;
 560
 561         value_set_iter * it = values->iterator();
 562         while (it->hasNext()) {
 563                 uint64_t val = it->next();
 564                 add_to_val_loc_map(val, loc);
 565         }
 566 }
 567
 568 void FuncNode::update_loc_may_equal_map(void * new_loc, loc_set_t * old_locations)
 569 {
 570         if ( old_locations->contains(new_loc) )
 571                 return;
 572
 573         loc_set_t * neighbors = loc_may_equal_map->get(new_loc);
 574
 575         if (neighbors == NULL) {
 576                 neighbors = new loc_set_t();
 577                 loc_may_equal_map->put(new_loc, neighbors);
 578         }
 579
 580         loc_set_iter * loc_it = old_locations->iterator();
 581         while (loc_it->hasNext()) {
 582                 // new_loc: { old_locations, ... }
 583                 void * member = loc_it->next();
 584                 neighbors->add(member);
 585
 586                 // for each i in old_locations, i : { new_loc, ... }
 587                 loc_set_t * _neighbors = loc_may_equal_map->get(member);
 588                 if (_neighbors == NULL) {
 589                         _neighbors = new loc_set_t();
 590                         loc_may_equal_map->put(member, _neighbors);
 591                 }
 592                 _neighbors->add(new_loc);
 593         }
 594 }
 595
 596 /* Every time a thread enters a function, set its position to the predicate tree entry */
 597 void FuncNode::init_predicate_tree_position(thread_id_t tid)
 598 {
 599         int thread_id = id_to_int(tid);
 600         if (predicate_tree_position.size() <= (uint) thread_id)
 601                 predicate_tree_position.resize(thread_id + 1);
 602
 603         predicate_tree_position[thread_id] = predicate_tree_entry;
 604 }
 605
 606 void FuncNode::set_predicate_tree_position(thread_id_t tid, Predicate * pred)
 607 {
 608         int thread_id = id_to_int(tid);
 609         predicate_tree_position[thread_id] = pred;
 610 }
 611
 612 /* @return The position of a thread in a predicate tree */
 613 Predicate * FuncNode::get_predicate_tree_position(thread_id_t tid)
 614 {
 615         int thread_id = id_to_int(tid);
 616         return predicate_tree_position[thread_id];
 617 }
 618
 619 /* Make sure elements of thrd_inst_act_map are initialized properly when threads enter functions */
 620 void FuncNode::init_inst_act_map(thread_id_t tid)
 621 {
 622         int thread_id = id_to_int(tid);
 623         SnapVector<inst_act_map_t *> * thrd_inst_act_map = history->getThrdInstActMap(func_id);
 624         uint old_size = thrd_inst_act_map->size();
 625
 626         if (thrd_inst_act_map->size() <= (uint) thread_id) {
 627                 uint new_size = thread_id + 1;
 628                 thrd_inst_act_map->resize(new_size);
 629
 630                 for (uint i = old_size;i < new_size;i++)
 631                         (*thrd_inst_act_map)[i] = new inst_act_map_t(128);
 632         }
 633 }
 634
 635 /* Reset elements of thrd_inst_act_map when threads exit functions */
 636 void FuncNode::reset_inst_act_map(thread_id_t tid)
 637 {
 638         int thread_id = id_to_int(tid);
 639         SnapVector<inst_act_map_t *> * thrd_inst_act_map = history->getThrdInstActMap(func_id);
 640
 641         inst_act_map_t * map = (*thrd_inst_act_map)[thread_id];
 642         map->reset();
 643 }
 644
 645 void FuncNode::update_inst_act_map(thread_id_t tid, ModelAction * read_act)
 646 {
 647         int thread_id = id_to_int(tid);
 648         SnapVector<inst_act_map_t *> * thrd_inst_act_map = history->getThrdInstActMap(func_id);
 649
 650         inst_act_map_t * map = (*thrd_inst_act_map)[thread_id];
 651         FuncInst * read_inst = get_inst(read_act);
 652         map->put(read_inst, read_act);
 653 }
 654
 655 inst_act_map_t * FuncNode::get_inst_act_map(thread_id_t tid)
 656 {
 657         int thread_id = id_to_int(tid);
 658         SnapVector<inst_act_map_t *> * thrd_inst_act_map = history->getThrdInstActMap(func_id);
 659
 660         return (*thrd_inst_act_map)[thread_id];
 661 }
 662
 663 /* Add FuncNodes that this node may follow */
 664 void FuncNode::add_out_edge(FuncNode * other)
 665 {
 666         if ( !edge_table.contains(other) ) {
 667                 edge_table.put(other, OUT_EDGE);
 668                 out_edges.push_back(other);
 669                 return;
 670         }
 671
 672         edge_type_t edge = edge_table.get(other);
 673         if (edge == IN_EDGE) {
 674                 edge_table.put(other, BI_EDGE);
 675                 out_edges.push_back(other);
 676         }
 677 }
 678
 679 /* Compute the distance between this FuncNode and the target node.
 680  * Return -1 if the target node is unreachable or the actual distance
 681  * is greater than max_step.
 682  */
 683 int FuncNode::compute_distance(FuncNode * target, int max_step)
 684 {
 685         if (target == NULL)
 686                 return -1;
 687         else if (target == this)
 688                 return 0;
 689
 690         SnapList<FuncNode *> queue;
 691         HashTable<FuncNode *, int, uintptr_t, 0> distances(128);
 692
 693         queue.push_back(this);
 694         distances.put(this, 0);
 695
 696         while (!queue.empty()) {
 697                 FuncNode * curr = queue.front();
 698                 queue.pop_front();
 699                 int dist = distances.get(curr);
 700
 701                 if (max_step <= dist)
 702                         return -1;
 703
 704                 ModelList<FuncNode *> * outEdges = curr->get_out_edges();
 705                 mllnode<FuncNode *> * it;
 706                 for (it = outEdges->begin();it != NULL;it = it->getNext()) {
 707                         FuncNode * out_node = it->getVal();
 708
 709                         /* This node has not been visited before */
 710                         if ( !distances.contains(out_node) ) {
 711                                 if (out_node == target)
 712                                         return dist + 1;
 713
 714                                 queue.push_back(out_node);
 715                                 distances.put(out_node, dist + 1);
 716                         }
 717                 }
 718         }
 719
 720         /* Target node is unreachable */
 721         return -1;
 722 }
 723
 724 void FuncNode::print_predicate_tree()
 725 {
 726         model_print("digraph function_%s {\n", func_name);
 727         predicate_tree_entry->print_pred_subtree();
 728         predicate_tree_exit->print_predicate();
 729         model_print("}\n");     // end of graph
 730 }
 731
 732 void FuncNode::print_val_loc_map()
 733 {
 734 /*
 735         value_set_iter * val_it = values_may_read_from->iterator();
 736         while (val_it->hasNext()) {
 737                 uint64_t value = val_it->next();
 738                 model_print("val %llx: ", value);
 739
 740                 loc_set_t * locations = val_loc_map->get(value);
 741                 loc_set_iter * loc_it = locations->iterator();
 742                 while (loc_it->hasNext()) {
 743                         void * location = loc_it->next();
 744                         model_print("%p ", location);
 745                 }
 746                 model_print("\n");
 747         }
 748  */
 749 }