funcnode.cc

   1 #include "funcnode.h"
   2
   3 FuncNode::FuncNode() :
   4         predicate_tree_initialized(false),
   5         func_inst_map(),
   6         inst_list(),
   7         entry_insts(),
   8         thrd_read_map()
   9 {}
  10
  11 /* Check whether FuncInst with the same type, position, and location
  12  * as act has been added to func_inst_map or not. If so, return it;
  13  * if not, add it and return it.
  14  *
  15  * @return FuncInst with the same type, position, and location as act */
  16 FuncInst * FuncNode::get_or_add_inst(ModelAction *act)
  17 {
  18         ASSERT(act);
  19         const char * position = act->get_position();
  20
  21         /* Actions THREAD_CREATE, THREAD_START, THREAD_YIELD, THREAD_JOIN,
  22          * THREAD_FINISH, PTHREAD_CREATE, PTHREAD_JOIN,
  23          * ATOMIC_LOCK, ATOMIC_TRYLOCK, and ATOMIC_UNLOCK are not tagged with their
  24          * 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 /* @param act_list a list of ModelActions; this argument comes from ModelExecution
  74  * convert act_inst to inst_list do linking - add one FuncInst to another's predecessors and successors
  75  */
  76 void FuncNode::update_inst_tree(action_list_t * act_list)
  77 {
  78         if (act_list == NULL)
  79                 return;
  80         else if (act_list->size() == 0)
  81                 return;
  82
  83         /* build inst_list from act_list for later processing */
  84         func_inst_list_t inst_list;
  85         for (sllnode<ModelAction *> * it = act_list->begin(); it != NULL; it = it->getNext()) {
  86                 ModelAction * act = it->getVal();
  87                 FuncInst * func_inst = get_or_add_inst(act);
  88
  89                 if (func_inst != NULL)
  90                         inst_list.push_back(func_inst);
  91         }
  92
  93         /* start linking */
  94         sllnode<FuncInst *>* it = inst_list.begin();
  95         sllnode<FuncInst *>* prev;
  96
  97         /* add the first instruction to the list of entry insts */
  98         FuncInst * entry_inst = it->getVal();
  99         add_entry_inst(entry_inst);
 100
 101         it = it->getNext();
 102         while (it != NULL) {
 103                 prev = it->getPrev();
 104
 105                 FuncInst * prev_inst = prev->getVal();
 106                 FuncInst * curr_inst = it->getVal();
 107
 108                 prev_inst->add_succ(curr_inst);
 109                 curr_inst->add_pred(prev_inst);
 110
 111                 it = it->getNext();
 112         }
 113 }
 114
 115 /* @param tid thread id
 116  * Store the values read by atomic read actions into thrd_read_map */
 117 void FuncNode::store_read(ModelAction * act, uint32_t tid)
 118 {
 119         ASSERT(act);
 120
 121         void * location = act->get_location();
 122         uint64_t read_from_val = act->get_reads_from_value();
 123
 124         /* resize and initialize */
 125         uint32_t old_size = thrd_read_map.size();
 126         if (old_size <= tid) {
 127                 thrd_read_map.resize(tid + 1);
 128                 for (uint32_t i = old_size; i < tid + 1;i++)
 129                         thrd_read_map[i] = new read_map_t();
 130         }
 131
 132         read_map_t * read_map = thrd_read_map[tid];
 133         read_map->put(location, read_from_val);
 134
 135         /* Store the memory locations where atomic reads happen */
 136         // read_locations.add(location);
 137 }
 138
 139 uint64_t FuncNode::query_last_read(void * location, uint32_t tid)
 140 {
 141         if (thrd_read_map.size() <= tid)
 142                 return 0xdeadbeef;
 143
 144         read_map_t * read_map = thrd_read_map[tid];
 145
 146         /* last read value not found */
 147         if ( !read_map->contains(location) )
 148                 return 0xdeadbeef;
 149
 150         uint64_t read_val = read_map->get(location);
 151         return read_val;
 152 }
 153
 154 /* @param tid thread id
 155  * Reset read map for a thread. This function shall only be called
 156  * when a thread exits a function
 157  */
 158 void FuncNode::clear_read_map(uint32_t tid)
 159 {
 160         if (thrd_read_map.size() <= tid)
 161                 return;
 162
 163         thrd_read_map[tid]->reset();
 164 }
 165
 166 void FuncNode::init_predicate_tree(func_inst_list_t * inst_list)
 167 {
 168         if (inst_list == NULL || inst_list->size() == 0)
 169                 return;
 170
 171         if (predicate_tree_initialized)
 172                 return;
 173
 174         predicate_tree_initialized = true;
 175
 176         // maybe restrict the size of hashtable to save calloc time
 177         HashTable<void *, FuncInst *, uintptr_t, 4> loc_inst_map;
 178
 179         sllnode<FuncInst *> *it = inst_list->begin();
 180         sllnode<FuncInst *> *prev;
 181
 182         FuncInst * entry_inst = it->getVal();
 183
 184         /* entry instruction has no predicate expression */
 185         Predicate * pred_entry = new Predicate(entry_inst);
 186         loc_inst_map.put(entry_inst->get_location(), entry_inst);
 187
 188         it = it->getNext();
 189         while (it != NULL) {
 190                 prev = it->getPrev();
 191
 192                 FuncInst * curr_inst = it->getVal();
 193                 FuncInst * prev_inst = prev->getVal();
 194
 195                 if ( loc_inst_map.contains(curr_inst->get_location()) ) {
 196                         Predicate * pred1 = new Predicate(curr_inst);
 197                         pred1->add_predicate(EQUALITY, curr_inst->get_location(), 0);
 198
 199                         Predicate * pred2 = new Predicate(curr_inst);
 200                         pred2->add_predicate(EQUALITY, curr_inst->get_location(), 1);
 201                 }
 202
 203                 loc_inst_map.put(curr_inst->get_location(), curr_inst);
 204
 205                 it = it->getNext();
 206         }
 207 }
 208
 209
 210 void FuncNode::generate_predicate(FuncInst *func_inst)
 211 {
 212
 213 }
 214
 215 /* @param tid thread id
 216  * Print the values read by the last read actions for each memory location
 217  */
 218 void FuncNode::print_last_read(uint32_t tid)
 219 {
 220         ASSERT(thrd_read_map.size() > tid);
 221         read_map_t * read_map = thrd_read_map[tid];
 222 /*
 223         mllnode<void *> * it;
 224         for (it = read_locations.begin();it != NULL;it=it->getNext()) {
 225                 if ( !read_map->contains(it->getVal()) )
 226                         break;
 227
 228                 uint64_t read_val = read_map->get(it->getVal());
 229                 model_print("last read of thread %d at %p: 0x%x\n", tid, it->getVal(), read_val);
 230         }
 231 */
 232 }