From d80e8e4cb554d09807e2ec5e9acadd917579f600 Mon Sep 17 00:00:00 2001 From: weiyu Date: Fri, 16 Aug 2019 16:59:31 -0700 Subject: [PATCH] change the way to detect loops --- funcnode.cc | 38 ++++++++++++++++++++------------------ predicate.cc | 9 ++++++--- predicate.h | 10 +++++----- 3 files changed, 31 insertions(+), 26 deletions(-) diff --git a/funcnode.cc b/funcnode.cc index 3a7e4dbe..085ab5bd 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -120,7 +120,7 @@ void FuncNode::update_tree(action_list_t * act_list) 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); @@ -224,6 +224,11 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) */ /* map a FuncInst to the its predicate */ HashTable inst_pred_map(128); + + // number FuncInsts to detect loops + HashTable inst_id_map(128); + uint32_t inst_counter = 0; + HashTable loc_act_map(128); HashTable inst_act_map(128); @@ -236,7 +241,7 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) 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]; @@ -246,25 +251,21 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) 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) { @@ -320,8 +321,9 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) } } - 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); diff --git a/predicate.cc b/predicate.cc index 5bc23098..c8e39891 100644 --- a/predicate.cc +++ b/predicate.cc @@ -3,10 +3,10 @@ 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) @@ -93,6 +93,9 @@ void Predicate::print_pred_subtree() 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); + } } diff --git a/predicate.h b/predicate.h index dd101149..732e39ab 100644 --- a/predicate.h +++ b/predicate.h @@ -43,12 +43,12 @@ public: 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 * 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; } @@ -61,15 +61,15 @@ private: FuncInst * func_inst; bool entry_predicate; - /* may have multiple predicates */ + /* may have multiple predicate expressions */ PredExprSet pred_expressions; ModelVector 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__ */ -- 2.34.1