funcnode.cc

   1 #include "funcnode.h"
   2
   3 FuncNode::FuncNode() :
   4         predicate_tree_initialized(false),
   5         predicate_tree_entry(new Predicate(NULL, true)),
   6         func_inst_map(),
   7         inst_list(),
   8         entry_insts(),
   9         thrd_read_map()
  10 {
  11         predicate_tree_entry->add_predicate_expr(NOPREDICATE, NULL, true);
  12 }
  13
  14 /* Check whether FuncInst with the same type, position, and location
  15  * as act has been added to func_inst_map or not. If not, add it.
  16  *
  17  * Note: currently, actions with the same position are filtered out by process_action,
  18  * so the collision list of FuncInst is not used. May remove it later.
  19  */
  20 void FuncNode::add_inst(ModelAction *act)
  21 {
  22         ASSERT(act);
  23         const char * position = act->get_position();
  24
  25         /* THREAD* actions, ATOMIC_LOCK, ATOMIC_TRYLOCK, and ATOMIC_UNLOCK
  26          * actions are not tagged with their source line numbers
  27          */
  28         if (position == NULL)
  29                 return;
  30
  31         if ( func_inst_map.contains(position) ) {
  32                 FuncInst * inst = func_inst_map.get(position);
  33
  34                 ASSERT(inst->get_type() == act->get_type());
  35                 if (inst->get_location() != act->get_location())
  36                         inst->not_single_location();
  37
  38                 return;
  39         }
  40
  41         FuncInst * func_inst = new FuncInst(act, this);
  42
  43         func_inst_map.put(position, func_inst);
  44         inst_list.push_back(func_inst);
  45 }
  46
  47 /* Get the FuncInst with the same type, position, and location
  48  * as act
  49  *
  50  * @return FuncInst with the same type, position, and location as act */
  51 FuncInst * FuncNode::get_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 NULL;
  61
  62         FuncInst * inst = func_inst_map.get(position);
  63         if (inst == NULL)
  64                 return NULL;
  65
  66         action_type inst_type = inst->get_type();
  67         action_type act_type = act->get_type();
  68
  69         // else if branch: an RMWRCAS action is converted to a RMW or READ action
  70         if (inst_type == act_type)
  71                 return inst;
  72         else if (inst_type == ATOMIC_RMWRCAS &&
  73                         (act_type == ATOMIC_RMW || act_type == ATOMIC_READ))
  74                 return inst;
  75
  76         return NULL;
  77 }
  78
  79
  80 void FuncNode::add_entry_inst(FuncInst * inst)
  81 {
  82         if (inst == NULL)
  83                 return;
  84
  85         mllnode<FuncInst *> * it;
  86         for (it = entry_insts.begin(); it != NULL; it = it->getNext()) {
  87                 if (inst == it->getVal())
  88                         return;
  89         }
  90
  91         entry_insts.push_back(inst);
  92 }
  93
  94 /**
  95  * @brief Convert ModelAdtion list to FuncInst list
  96  * @param act_list A list of ModelActions
  97  */
  98 void FuncNode::update_tree(action_list_t * act_list)
  99 {
 100         if (act_list == NULL)
 101                 return;
 102         else if (act_list->size() == 0)
 103                 return;
 104
 105         /* build inst_list from act_list for later processing */
 106         func_inst_list_t inst_list;
 107         action_list_t read_act_list;
 108
 109         for (sllnode<ModelAction *> * it = act_list->begin(); it != NULL; it = it->getNext()) {
 110                 ModelAction * act = it->getVal();
 111                 FuncInst * func_inst = get_inst(act);
 112
 113                 if (func_inst == NULL)
 114                         continue;
 115
 116                 inst_list.push_back(func_inst);
 117
 118                 if (func_inst->is_read())
 119                         read_act_list.push_back(act);
 120         }
 121
 122         model_print("function %s\n", func_name);
 123         update_inst_tree(&inst_list);
 124         update_predicate_tree(&read_act_list);
 125 //      deep_update(predicate_tree_entry);
 126
 127         print_predicate_tree();
 128 }
 129
 130 /**
 131  * @brief Link FuncInsts in inst_list  - add one FuncInst to another's predecessors and successors
 132  * @param inst_list A list of FuncInsts
 133  */
 134 void FuncNode::update_inst_tree(func_inst_list_t * inst_list)
 135 {
 136         if (inst_list == NULL)
 137                 return;
 138         else if (inst_list->size() == 0)
 139                 return;
 140
 141         /* start linking */
 142         sllnode<FuncInst *>* it = inst_list->begin();
 143         sllnode<FuncInst *>* prev;
 144
 145         /* add the first instruction to the list of entry insts */
 146         FuncInst * entry_inst = it->getVal();
 147         add_entry_inst(entry_inst);
 148
 149         it = it->getNext();
 150         while (it != NULL) {
 151                 prev = it->getPrev();
 152
 153                 FuncInst * prev_inst = prev->getVal();
 154                 FuncInst * curr_inst = it->getVal();
 155
 156                 prev_inst->add_succ(curr_inst);
 157                 curr_inst->add_pred(prev_inst);
 158
 159                 it = it->getNext();
 160         }
 161 }
 162
 163 /* @param tid thread id
 164  * Store the values read by atomic read actions into thrd_read_map */
 165 void FuncNode::store_read(ModelAction * act, uint32_t tid)
 166 {
 167         ASSERT(act);
 168
 169         void * location = act->get_location();
 170         uint64_t read_from_val = act->get_reads_from_value();
 171
 172         /* resize and initialize */
 173         uint32_t old_size = thrd_read_map.size();
 174         if (old_size <= tid) {
 175                 thrd_read_map.resize(tid + 1);
 176                 for (uint32_t i = old_size; i < tid + 1;i++)
 177                         thrd_read_map[i] = new read_map_t();
 178         }
 179
 180         read_map_t * read_map = thrd_read_map[tid];
 181         read_map->put(location, read_from_val);
 182
 183         /* Store the memory locations where atomic reads happen */
 184         // read_locations.add(location);
 185 }
 186
 187 uint64_t FuncNode::query_last_read(void * location, uint32_t tid)
 188 {
 189         if (thrd_read_map.size() <= tid)
 190                 return VALUE_NONE;
 191
 192         read_map_t * read_map = thrd_read_map[tid];
 193
 194         /* last read value not found */
 195         if ( !read_map->contains(location) )
 196                 return VALUE_NONE;
 197
 198         uint64_t read_val = read_map->get(location);
 199         return read_val;
 200 }
 201
 202 /* @param tid thread id
 203  * Reset read map for a thread. This function shall only be called
 204  * when a thread exits a function
 205  */
 206 void FuncNode::clear_read_map(uint32_t tid)
 207 {
 208         if (thrd_read_map.size() <= tid)
 209                 return;
 210
 211         thrd_read_map[tid]->reset();
 212 }
 213
 214 void FuncNode::update_predicate_tree(action_list_t * act_list)
 215 {
 216         if (act_list == NULL || act_list->size() == 0)
 217                 return;
 218 /*
 219         if (predicate_tree_initialized) {
 220                 return;
 221         }
 222         predicate_tree_initialized = true;
 223 */
 224         /* map a FuncInst to the its predicate */
 225         HashTable<FuncInst *, Predicate *, uintptr_t, 0> inst_pred_map(128);
 226         HashTable<void *, ModelAction *, uintptr_t, 0> loc_act_map(128);
 227         HashTable<FuncInst *, ModelAction *, uintptr_t, 0> inst_act_map(128);
 228
 229         sllnode<ModelAction *> *it = act_list->begin();
 230         Predicate * curr_pred = predicate_tree_entry;
 231         while (it != NULL) {
 232                 ModelAction * next_act = it->getVal();
 233                 FuncInst * next_inst = get_inst(next_act);
 234                 SnapVector<Predicate *> * unset_predicates = new SnapVector<Predicate *>();
 235
 236                 bool branch_found = follow_branch(&curr_pred, next_inst, next_act, &inst_act_map, unset_predicates);
 237
 238                 /* no predicate, follow the only branch */
 239                 if (!branch_found && unset_predicates->size() != 0) {
 240                         ASSERT(unset_predicates->size() == 1);
 241                         Predicate * one_branch = (*unset_predicates)[0];
 242
 243                         if (!next_inst->is_single_location()) {
 244                                 Predicate * another_branch = new Predicate(next_inst);
 245                                 // another_branch->copy_predicate_expr(one_branch);
 246
 247                                 uint64_t next_read = next_act->get_reads_from_value();
 248                                 bool isnull = ((void*)next_read == NULL);
 249                                 if (isnull) {
 250                                         one_branch->add_predicate_expr(NULLITY, NULL, 1);
 251                                         another_branch->add_predicate_expr(NULLITY, NULL, 0);
 252                                 } else {
 253                                         another_branch->add_predicate_expr(NULLITY, NULL, 1);
 254                                         one_branch->add_predicate_expr(NULLITY, NULL, 0);
 255                                 }
 256
 257                                 curr_pred->add_child(another_branch);
 258                                 another_branch->set_parent(curr_pred);
 259                         }
 260
 261                         curr_pred = one_branch;
 262                         branch_found = true;
 263                 }
 264
 265                 delete unset_predicates;
 266
 267                 // check back edges
 268                 if (!branch_found) {
 269                         bool backedge_found = false;
 270                         Predicate * back_pred = curr_pred->get_backedge();
 271                         if (back_pred != NULL) {
 272                                 curr_pred = back_pred;
 273                                 backedge_found = true;
 274                         } else if (inst_pred_map.contains(next_inst)) {
 275                                 inst_pred_map.remove(curr_pred->get_func_inst());
 276                                 Predicate * old_pred = inst_pred_map.get(next_inst);
 277                                 back_pred = old_pred->get_parent();
 278
 279                                 curr_pred->set_backedge(back_pred);
 280                                 curr_pred = back_pred;
 281                                 backedge_found = true;
 282                         }
 283
 284                         if (backedge_found)
 285                                 continue;
 286                 }
 287
 288                 if (!branch_found) {
 289                         if ( loc_act_map.contains(next_act->get_location()) ) {
 290                                 ModelAction * last_act = loc_act_map.get(next_act->get_location());
 291                                 FuncInst * last_inst = get_inst(last_act);
 292
 293                                 Predicate * new_pred1 = new Predicate(next_inst);
 294                                 new_pred1->add_predicate_expr(EQUALITY, last_inst, true);
 295
 296                                 Predicate * new_pred2 = new Predicate(next_inst);
 297                                 new_pred2->add_predicate_expr(EQUALITY, last_inst, false);
 298
 299                                 curr_pred->add_child(new_pred1);
 300                                 curr_pred->add_child(new_pred2);
 301                                 new_pred1->set_parent(curr_pred);
 302                                 new_pred2->set_parent(curr_pred);
 303
 304                                 uint64_t last_read = last_act->get_reads_from_value();
 305                                 uint64_t next_read = next_act->get_reads_from_value();
 306
 307                                 if ( last_read == next_read )
 308                                         curr_pred = new_pred1;
 309                                 else
 310                                         curr_pred = new_pred2;
 311                         } else {
 312                                 Predicate * new_pred = new Predicate(next_inst);
 313                                 curr_pred->add_child(new_pred);
 314                                 new_pred->set_parent(curr_pred);
 315
 316                                 if (curr_pred->is_entry_predicate())
 317                                         new_pred->add_predicate_expr(NOPREDICATE, NULL, true);
 318
 319                                 curr_pred = new_pred;
 320                         }
 321                 }
 322
 323                 if (!inst_pred_map.contains(next_inst))
 324                         inst_pred_map.put(next_inst, curr_pred);
 325
 326                 loc_act_map.put(next_act->get_location(), next_act);
 327                 inst_act_map.put(next_inst, next_act);
 328                 it = it->getNext();
 329         }
 330 }
 331
 332 void FuncNode::deep_update(Predicate * curr_pred)
 333 {
 334         FuncInst * func_inst = curr_pred->get_func_inst();
 335         if (func_inst != NULL && !func_inst->is_single_location()) {
 336                 bool has_null_pred = false;
 337                 PredExprSet * pred_expressions = curr_pred->get_pred_expressions();
 338                 PredExprSetIter * pred_expr_it = pred_expressions->iterator();
 339                 while (pred_expr_it->hasNext()) {
 340                         pred_expr * pred_expression = pred_expr_it->next();
 341                         if (pred_expression->token == NULLITY) {
 342                                 has_null_pred = true;
 343                                 break;
 344                         }
 345                 }
 346
 347                 if (!has_null_pred) {
 348 //                      func_inst->print();
 349                         Predicate * another_branch = new Predicate(func_inst);
 350                         another_branch->copy_predicate_expr(curr_pred);
 351                         another_branch->add_predicate_expr(NULLITY, NULL, 1);
 352                         curr_pred->add_predicate_expr(NULLITY, NULL, 0);
 353
 354                         Predicate * parent = curr_pred->get_parent();
 355                         parent->add_child(another_branch);
 356 //                      another_branch.add_children(i);
 357                 }
 358         }
 359
 360         ModelVector<Predicate *> * branches = curr_pred->get_children();
 361         for (uint i = 0; i < branches->size(); i++) {
 362                 Predicate * branch = (*branches)[i];
 363                 deep_update(branch);
 364         }
 365 }
 366
 367 /* Given curr_pred and next_inst, find the branch following curr_pred that
 368  * contains next_inst and the correct predicate.
 369  * @return true if branch found, false otherwise.
 370  */
 371 bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst, ModelAction * next_act,
 372         HashTable<FuncInst *, ModelAction *, uintptr_t, 0> * inst_act_map,
 373         SnapVector<Predicate *> * unset_predicates)
 374 {
 375         /* check if a branch with func_inst and corresponding predicate exists */
 376         bool branch_found = false;
 377         ModelVector<Predicate *> * branches = (*curr_pred)->get_children();
 378         for (uint i = 0; i < branches->size(); i++) {
 379                 Predicate * branch = (*branches)[i];
 380                 if (branch->get_func_inst() != next_inst)
 381                         continue;
 382
 383                 /* check against predicate expressions */
 384                 bool predicate_correct = true;
 385                 PredExprSet * pred_expressions = branch->get_pred_expressions();
 386                 PredExprSetIter * pred_expr_it = pred_expressions->iterator();
 387
 388                 if (pred_expressions->getSize() == 0) {
 389                         predicate_correct = false;
 390                         unset_predicates->push_back(branch);
 391                 }
 392
 393                 while (pred_expr_it->hasNext()) {
 394                         pred_expr * pred_expression = pred_expr_it->next();
 395                         uint64_t last_read, next_read;
 396                         bool equality;
 397
 398                         switch(pred_expression->token) {
 399                                 case NOPREDICATE:
 400                                         predicate_correct = true;
 401                                         break;
 402                                 case EQUALITY:
 403                                         FuncInst * to_be_compared;
 404                                         ModelAction * last_act;
 405
 406                                         to_be_compared = pred_expression->func_inst;
 407                                         last_act = inst_act_map->get(to_be_compared);
 408
 409                                         last_read = last_act->get_reads_from_value();
 410                                         next_read = next_act->get_reads_from_value();
 411                                         equality = (last_read == next_read);
 412                                         if (equality != pred_expression->value)
 413                                                 predicate_correct = false;
 414
 415                                         break;
 416                                 case NULLITY:
 417                                         next_read = next_act->get_reads_from_value();
 418                                         equality = ((void*)next_read == NULL);
 419                                         if (equality != pred_expression->value)
 420                                                 predicate_correct = false;
 421                                         break;
 422                                 default:
 423                                         predicate_correct = false;
 424                                         model_print("unkown predicate token\n");
 425                                         break;
 426                         }
 427                 }
 428
 429                 if (predicate_correct) {
 430                         *curr_pred = branch;
 431                         branch_found = true;
 432                         break;
 433                 }
 434         }
 435
 436         return branch_found;
 437 }
 438
 439 void FuncNode::print_predicate_tree()
 440 {
 441         model_print("digraph function_%s {\n", func_name);
 442         predicate_tree_entry->print_pred_subtree();
 443         model_print("}\n");     // end of graph
 444 }
 445
 446 /* @param tid thread id
 447  * Print the values read by the last read actions for each memory location
 448  */
 449 /*
 450 void FuncNode::print_last_read(uint32_t tid)
 451 {
 452         ASSERT(thrd_read_map.size() > tid);
 453         read_map_t * read_map = thrd_read_map[tid];
 454
 455         mllnode<void *> * it;
 456         for (it = read_locations.begin();it != NULL;it=it->getNext()) {
 457                 if ( !read_map->contains(it->getVal()) )
 458                         break;
 459
 460                 uint64_t read_val = read_map->get(it->getVal());
 461                 model_print("last read of thread %d at %p: 0x%x\n", tid, it->getVal(), read_val);
 462         }
 463 }
 464 */