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