read_act_list.push_back(act);
}
- model_print("function %s\n", func_name);
+// model_print("function %s\n", func_name);
update_inst_tree(&inst_list);
update_predicate_tree(&read_act_list);
// deep_update(predicate_tree_entry);
*/
/* map a FuncInst to the its predicate */
HashTable<FuncInst *, Predicate *, uintptr_t, 0> inst_pred_map(128);
+
+ // number FuncInsts to detect loops
+ HashTable<FuncInst *, uint32_t, uintptr_t, 0> inst_id_map(128);
+ uint32_t inst_counter = 0;
+
HashTable<void *, ModelAction *, uintptr_t, 0> loc_act_map(128);
HashTable<FuncInst *, ModelAction *, uintptr_t, 0> inst_act_map(128);
bool branch_found = follow_branch(&curr_pred, next_inst, next_act, &inst_act_map, unset_predicates);
- /* no predicate, follow the only branch */
+ // no predicate expressions, follow the only branch
if (!branch_found && unset_predicates->size() != 0) {
ASSERT(unset_predicates->size() == 1);
Predicate * one_branch = (*unset_predicates)[0];
delete unset_predicates;
- // check back edges
- if (!branch_found) {
- bool backedge_found = false;
- Predicate * back_pred = curr_pred->get_backedge();
- if (back_pred != NULL) {
- curr_pred = back_pred;
- backedge_found = true;
- } else if (inst_pred_map.contains(next_inst)) {
- inst_pred_map.remove(curr_pred->get_func_inst());
+ // detect loops
+ if (!branch_found && inst_id_map.contains(next_inst)) {
+ FuncInst * curr_inst = curr_pred->get_func_inst();
+ uint32_t curr_id = inst_id_map.get(curr_inst);
+ uint32_t next_id = inst_id_map.get(next_inst);
+
+ if (curr_id >= next_id) {
Predicate * old_pred = inst_pred_map.get(next_inst);
- back_pred = old_pred->get_parent();
+ Predicate * back_pred = old_pred->get_parent();
- curr_pred->set_backedge(back_pred);
+ curr_pred->add_backedge(back_pred);
curr_pred = back_pred;
- backedge_found = true;
- }
- if (backedge_found)
continue;
+ }
}
if (!branch_found) {
}
}
- if (!inst_pred_map.contains(next_inst))
- inst_pred_map.put(next_inst, curr_pred);
+ inst_pred_map.put(next_inst, curr_pred);
+ if (!inst_id_map.contains(next_inst))
+ inst_id_map.put(next_inst, inst_counter++);
loc_act_map.put(next_act->get_location(), next_act);
inst_act_map.put(next_inst, next_act);
Predicate::Predicate(FuncInst * func_inst, bool is_entry) :
func_inst(func_inst),
entry_predicate(is_entry),
- pred_expressions(),
+ pred_expressions(16),
children(),
parent(NULL),
- backedge(NULL)
+ backedges(16)
{}
unsigned int pred_expr_hash(struct pred_expr * expr)
model_print("\"%p\" -> \"%p\"\n", this, child);
}
- if (backedge != NULL)
+ PredSetIter * it = backedges.iterator();
+ while (it->hasNext()) {
+ Predicate * backedge = it->next();
model_print("\"%p\" -> \"%p\"[style=dashed, color=grey]\n", this, backedge);
+ }
}
void add_predicate_expr(token_t token, FuncInst * func_inst, bool value);
void add_child(Predicate * child);
void set_parent(Predicate * parent_pred) { parent = parent_pred; }
- void set_backedge(Predicate * back_pred) { backedge = back_pred; }
+ void add_backedge(Predicate * back_pred) { backedges.add(back_pred); }
void copy_predicate_expr(Predicate * other);
ModelVector<Predicate *> * get_children() { return &children; }
Predicate * get_parent() { return parent; }
- Predicate * get_backedge() { return backedge; }
+ PredSet * get_backedges() { return &backedges; }
bool is_entry_predicate() { return entry_predicate; }
void set_entry_predicate() { entry_predicate = true; }
FuncInst * func_inst;
bool entry_predicate;
- /* may have multiple predicates */
+ /* may have multiple predicate expressions */
PredExprSet pred_expressions;
ModelVector<Predicate *> children;
/* only a single parent may exist */
Predicate * parent;
- /* assume almost one back edge exists */
- Predicate * backedge;
+ /* may have multiple back edges, e.g. nested loops */
+ PredSet backedges;
};
#endif /* __PREDICATE_H__ */