funcnode.cc

   1 #include "funcnode.h"
   2 #include <fcntl.h>
   3
   4 FuncNode::FuncNode() :
   5         predicate_tree_initialized(false),
   6         func_inst_map(),
   7         inst_list(),
   8         entry_insts(),
   9         thrd_read_map(),
  10         predicate_tree_entry()
  11 {}
  12
  13 /* Check whether FuncInst with the same type, position, and location
  14  * as act has been added to func_inst_map or not. If so, return it;
  15  * if not, add it and return it.
  16  *
  17  * @return FuncInst with the same type, position, and location as act */
  18 FuncInst * FuncNode::get_or_add_inst(ModelAction *act)
  19 {
  20         ASSERT(act);
  21         const char * position = act->get_position();
  22
  23         /* THREAD* actions, ATOMIC_LOCK, ATOMIC_TRYLOCK, and ATOMIC_UNLOCK
  24          * actions are not tagged with their source line numbers
  25          */
  26         if (position == NULL)
  27                 return NULL;
  28
  29         if ( func_inst_map.contains(position) ) {
  30                 FuncInst * inst = func_inst_map.get(position);
  31
  32                 if (inst->get_type() != act->get_type() ) {
  33                         // model_print("action with a different type occurs at line number %s\n", position);
  34                         FuncInst * func_inst = inst->search_in_collision(act);
  35
  36                         if (func_inst != NULL) {
  37                                 // return the FuncInst found in the collision list
  38                                 return func_inst;
  39                         }
  40
  41                         func_inst = new FuncInst(act, this);
  42                         inst->get_collisions()->push_back(func_inst);
  43                         inst_list.push_back(func_inst); // delete?
  44
  45                         return func_inst;
  46                 }
  47
  48                 return inst;
  49         }
  50
  51         FuncInst * func_inst = new FuncInst(act, this);
  52
  53         func_inst_map.put(position, func_inst);
  54         inst_list.push_back(func_inst);
  55
  56         return func_inst;
  57 }
  58
  59 void FuncNode::add_entry_inst(FuncInst * inst)
  60 {
  61         if (inst == NULL)
  62                 return;
  63
  64         mllnode<FuncInst *> * it;
  65         for (it = entry_insts.begin(); it != NULL; it = it->getNext()) {
  66                 if (inst == it->getVal())
  67                         return;
  68         }
  69
  70         entry_insts.push_back(inst);
  71 }
  72
  73 /**
  74  * @brief Convert ModelAdtion list to FuncInst list
  75  * @param act_list A list of ModelActions
  76  */
  77 void FuncNode::update_tree(action_list_t * act_list)
  78 {
  79         if (act_list == NULL)
  80                 return;
  81         else if (act_list->size() == 0)
  82                 return;
  83
  84         /* build inst_list from act_list for later processing */
  85         func_inst_list_t inst_list;
  86         func_inst_list_t read_inst_list;
  87         HashTable<FuncInst *, uint64_t, uintptr_t, 4> read_val_map;
  88
  89         for (sllnode<ModelAction *> * it = act_list->begin(); it != NULL; it = it->getNext()) {
  90                 ModelAction * act = it->getVal();
  91                 FuncInst * func_inst = get_or_add_inst(act);
  92
  93                 if (func_inst == NULL)
  94                         continue;
  95
  96                 inst_list.push_back(func_inst);
  97
  98 /*              if (!predicate_tree_initialized) {
  99                         model_print("position: %s ", act->get_position());
 100                         act->print();
 101                 }
 102 */
 103
 104                 if (func_inst->is_read()) {
 105                         read_inst_list.push_back(func_inst);
 106                         read_val_map.put(func_inst, act->get_reads_from_value());
 107                 }
 108         }
 109
 110         update_inst_tree(&inst_list);
 111         init_predicate_tree(&read_inst_list, &read_val_map);
 112 }
 113
 114 /**
 115  * @brief Link FuncInsts in inst_list  - add one FuncInst to another's predecessors and successors
 116  * @param inst_list A list of FuncInsts
 117  */
 118 void FuncNode::update_inst_tree(func_inst_list_t * inst_list)
 119 {
 120         if (inst_list == NULL)
 121                 return;
 122         else if (inst_list->size() == 0)
 123                 return;
 124
 125         /* start linking */
 126         sllnode<FuncInst *>* it = inst_list->begin();
 127         sllnode<FuncInst *>* prev;
 128
 129         /* add the first instruction to the list of entry insts */
 130         FuncInst * entry_inst = it->getVal();
 131         add_entry_inst(entry_inst);
 132
 133         it = it->getNext();
 134         while (it != NULL) {
 135                 prev = it->getPrev();
 136
 137                 FuncInst * prev_inst = prev->getVal();
 138                 FuncInst * curr_inst = it->getVal();
 139
 140                 prev_inst->add_succ(curr_inst);
 141                 curr_inst->add_pred(prev_inst);
 142
 143                 it = it->getNext();
 144         }
 145 }
 146
 147 /* @param tid thread id
 148  * Store the values read by atomic read actions into thrd_read_map */
 149 void FuncNode::store_read(ModelAction * act, uint32_t tid)
 150 {
 151         ASSERT(act);
 152
 153         void * location = act->get_location();
 154         uint64_t read_from_val = act->get_reads_from_value();
 155
 156         /* resize and initialize */
 157         uint32_t old_size = thrd_read_map.size();
 158         if (old_size <= tid) {
 159                 thrd_read_map.resize(tid + 1);
 160                 for (uint32_t i = old_size; i < tid + 1;i++)
 161                         thrd_read_map[i] = new read_map_t();
 162         }
 163
 164         read_map_t * read_map = thrd_read_map[tid];
 165         read_map->put(location, read_from_val);
 166
 167         /* Store the memory locations where atomic reads happen */
 168         // read_locations.add(location);
 169 }
 170
 171 uint64_t FuncNode::query_last_read(void * location, uint32_t tid)
 172 {
 173         if (thrd_read_map.size() <= tid)
 174                 return 0xdeadbeef;
 175
 176         read_map_t * read_map = thrd_read_map[tid];
 177
 178         /* last read value not found */
 179         if ( !read_map->contains(location) )
 180                 return 0xdeadbeef;
 181
 182         uint64_t read_val = read_map->get(location);
 183         return read_val;
 184 }
 185
 186 /* @param tid thread id
 187  * Reset read map for a thread. This function shall only be called
 188  * when a thread exits a function
 189  */
 190 void FuncNode::clear_read_map(uint32_t tid)
 191 {
 192         if (thrd_read_map.size() <= tid)
 193                 return;
 194
 195         thrd_read_map[tid]->reset();
 196 }
 197
 198 void FuncNode::init_predicate_tree(func_inst_list_t * inst_list, HashTable<FuncInst *, uint64_t, uintptr_t, 4> * read_val_map)
 199 {
 200         if (inst_list == NULL || inst_list->size() == 0)
 201                 return;
 202
 203 /*
 204         if (predicate_tree_initialized) {
 205                 return;
 206         }
 207         predicate_tree_initialized = true;
 208 */
 209         // maybe restrict the size of hashtable to save calloc time
 210         HashTable<void *, FuncInst *, uintptr_t, 4> loc_inst_map(64);
 211
 212         sllnode<FuncInst *> *it = inst_list->begin();
 213         FuncInst * entry_inst = it->getVal();
 214
 215         /* get the unique Predicate pointer, assuming entry instructions have no predicate expression */
 216         Predicate * curr_pred = NULL;
 217         PredSetIter * pit = predicate_tree_entry.iterator();
 218         while (pit->hasNext()) {
 219                 Predicate * p = pit->next();
 220                 p->get_func_inst()->print();
 221                 if (p->get_func_inst() == entry_inst) {
 222                         curr_pred = p;
 223                         break;
 224                 }
 225         }
 226         if (curr_pred == NULL) {
 227                 curr_pred = new Predicate(entry_inst);
 228                 predicate_tree_entry.add(curr_pred);
 229         }
 230
 231         loc_inst_map.put(entry_inst->get_location(), entry_inst);
 232
 233         it = it->getNext();
 234         while (it != NULL) {
 235                 FuncInst * curr_inst = it->getVal();
 236                 bool child_found = false;
 237
 238                 /* check if a child with the same func_inst and corresponding predicate exists */
 239                 ModelVector<Predicate *> * children = curr_pred->get_children();
 240                 for (uint i = 0; i < children->size(); i++) {
 241                         Predicate * child = (*children)[i];
 242                         if (child->get_func_inst() != curr_inst)
 243                                 continue;
 244
 245                         PredExprSet * pred_expressions = child->get_pred_expressions();
 246
 247                         /* no predicate, follow the only child */
 248                         if (pred_expressions->getSize() == 0) {
 249                                 model_print("no predicate exists: ");
 250                                 curr_inst->print();
 251                                 curr_pred = child;
 252                                 child_found = true;
 253                                 break;
 254                         }
 255                 }
 256
 257                 if (!child_found) {
 258                         if ( loc_inst_map.contains(curr_inst->get_location()) ) {
 259                                 Predicate * new_pred1 = new Predicate(curr_inst);
 260                                 new_pred1->add_predicate(EQUALITY, curr_inst->get_location(), true);
 261
 262                                 Predicate * new_pred2 = new Predicate(curr_inst);
 263                                 new_pred2->add_predicate(EQUALITY, curr_inst->get_location(), false);
 264
 265                                 curr_pred->add_child(new_pred1);
 266                                 curr_pred->add_child(new_pred2);
 267
 268                                 FuncInst * last_inst = loc_inst_map.get(curr_inst->get_location());
 269                                 uint64_t last_read = read_val_map->get(last_inst);
 270                                 if ( last_read == read_val_map->get(curr_inst) )
 271                                         curr_pred = new_pred1;
 272                                 else
 273                                         curr_pred = new_pred2;
 274                         } else {
 275                                 Predicate * new_pred = new Predicate(curr_inst);
 276                                 curr_pred->add_child(new_pred);
 277                                 curr_pred = new_pred;
 278                         }
 279                 }
 280
 281                 loc_inst_map.put(curr_inst->get_location(), curr_inst);
 282
 283                 it = it->getNext();
 284         }
 285
 286 //      model_print("function %s\n", func_name);
 287 //      print_predicate_tree();
 288 }
 289
 290
 291 void FuncNode::print_predicate_tree()
 292 {
 293         model_print("digraph function_%s {\n", func_name);
 294         PredSetIter * it = predicate_tree_entry.iterator();
 295
 296         while (it->hasNext()) {
 297                 Predicate * p = it->next();
 298                 p->print_pred_subtree();
 299         }
 300         model_print("}\n");     // end of graph
 301 }
 302
 303 /* @param tid thread id
 304  * Print the values read by the last read actions for each memory location
 305  */
 306 /*
 307 void FuncNode::print_last_read(uint32_t tid)
 308 {
 309         ASSERT(thrd_read_map.size() > tid);
 310         read_map_t * read_map = thrd_read_map[tid];
 311
 312         mllnode<void *> * it;
 313         for (it = read_locations.begin();it != NULL;it=it->getNext()) {
 314                 if ( !read_map->contains(it->getVal()) )
 315                         break;
 316
 317                 uint64_t read_val = read_map->get(it->getVal());
 318                 model_print("last read of thread %d at %p: 0x%x\n", tid, it->getVal(), read_val);
 319         }
 320 }
 321 */