+ return branch_found;
+}
+
+/* Infer predicate expressions, which are generated in FuncNode::generate_predicates */
+void FuncNode::infer_predicates(FuncInst * next_inst, ModelAction * next_act,
+ HashTable<void *, ModelAction *, uintptr_t, 0> * loc_act_map,
+ SnapVector<struct half_pred_expr *> * half_pred_expressions)
+{
+ void * loc = next_act->get_location();
+
+ if (next_inst->is_read()) {
+ /* read + rmw */
+ if ( loc_act_map->contains(loc) ) {
+ ModelAction * last_act = loc_act_map->get(loc);
+ FuncInst * last_inst = get_inst(last_act);
+ struct half_pred_expr * expression = new half_pred_expr(EQUALITY, last_inst);
+ half_pred_expressions->push_back(expression);
+ } else if ( next_inst->is_single_location() ){
+ loc_set_t * loc_may_equal = loc_may_equal_map->get(loc);
+
+ if (loc_may_equal != NULL) {
+ loc_set_iter * loc_it = loc_may_equal->iterator();
+ while (loc_it->hasNext()) {
+ void * neighbor = loc_it->next();
+ if (loc_act_map->contains(neighbor)) {
+ ModelAction * last_act = loc_act_map->get(neighbor);
+ FuncInst * last_inst = get_inst(last_act);
+
+ struct half_pred_expr * expression = new half_pred_expr(EQUALITY, last_inst);
+ half_pred_expressions->push_back(expression);
+ }
+ }
+ }
+ } else {
+ // next_inst is not single location
+ uint64_t read_val = next_act->get_reads_from_value();
+
+ // only infer NULLITY predicate when it is actually NULL.
+ if ( (void*)read_val == NULL) {
+ struct half_pred_expr * expression = new half_pred_expr(NULLITY, NULL);
+ half_pred_expressions->push_back(expression);
+ }
+ }
+ } else {
+ /* Pure writes */
+ // TODO: do anything here?
+ }
+}
+
+/* Able to generate complex predicates when there are multiple predciate expressions */
+void FuncNode::generate_predicates(Predicate ** curr_pred, FuncInst * next_inst,
+ SnapVector<struct half_pred_expr *> * half_pred_expressions)
+{
+ if (half_pred_expressions->size() == 0) {
+ Predicate * new_pred = new Predicate(next_inst);
+ (*curr_pred)->add_child(new_pred);
+ new_pred->set_parent(*curr_pred);
+
+ /* entry predicates and predicates containing pure write actions
+ * have no predicate expressions */
+ if ( (*curr_pred)->is_entry_predicate() )
+ new_pred->add_predicate_expr(NOPREDICATE, NULL, true);
+ else if (next_inst->is_write()) {
+ /* next_inst->is_write() <==> pure writes */
+ new_pred->add_predicate_expr(NOPREDICATE, NULL, true);
+ }
+
+ return;
+ }
+
+ SnapVector<Predicate *> predicates;
+
+ struct half_pred_expr * half_expr = (*half_pred_expressions)[0];
+ predicates.push_back(new Predicate(next_inst));
+ predicates.push_back(new Predicate(next_inst));
+
+ predicates[0]->add_predicate_expr(half_expr->token, half_expr->func_inst, true);
+ predicates[1]->add_predicate_expr(half_expr->token, half_expr->func_inst, false);
+
+ for (uint i = 1; i < half_pred_expressions->size(); i++) {
+ half_expr = (*half_pred_expressions)[i];
+
+ uint old_size = predicates.size();
+ for (uint j = 0; j < old_size; j++) {
+ Predicate * pred = predicates[j];
+ Predicate * new_pred = new Predicate(next_inst);
+ new_pred->copy_predicate_expr(pred);
+
+ pred->add_predicate_expr(half_expr->token, half_expr->func_inst, true);
+ new_pred->add_predicate_expr(half_expr->token, half_expr->func_inst, false);
+
+ predicates.push_back(new_pred);
+ }
+ }
+
+ for (uint i = 0; i < predicates.size(); i++) {
+ Predicate * pred= predicates[i];
+ (*curr_pred)->add_child(pred);
+ pred->set_parent(*curr_pred);
+ }
+
+ /* Free memories allocated by infer_predicate */
+ for (uint i = 0; i < half_pred_expressions->size(); i++) {
+ struct half_pred_expr * tmp = (*half_pred_expressions)[i];
+ snapshot_free(tmp);
+ }