change the way to detect loops

diff --git a/funcnode.cc b/funcnode.cc
index 3a7e4dbe014d116fbd95ba9b649cd6efa31ed361..085ab5bd49e2d2e12ebc82402bf42a39da727905 100644 (file)
--- 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);
        }
 
                        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);
        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<FuncInst *, Predicate *, uintptr_t, 0> inst_pred_map(128);
 */
        /* 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);
 
        HashTable<void *, ModelAction *, uintptr_t, 0> loc_act_map(128);
        HashTable<FuncInst *, ModelAction *, uintptr_t, 0> 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);
 
 
                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];
                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;
 
 
                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);
                                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;
                                curr_pred = back_pred;

-                               backedge_found = true;
-                       }

 
 

-                       if (backedge_found)

                                continue;
                                continue;

+                       }

                }
 
                if (!branch_found) {
                }
 
                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);
 
                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 5bc23098ecb62d57018a2c47e473fa5e4a15dd42..c8e3989133fddedb009a8bc8544dfe48d893fdb4 100644 (file)
--- 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),
 Predicate::Predicate(FuncInst * func_inst, bool is_entry) :
        func_inst(func_inst),
        entry_predicate(is_entry),

-       pred_expressions(),
+       pred_expressions(16),

        children(),
        parent(NULL),
        children(),
        parent(NULL),

-       backedge(NULL)
+       backedges(16)

 {}
 
 unsigned int pred_expr_hash(struct pred_expr * expr)
 {}
 
 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);
        }
 
                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);
                model_print("\"%p\" -> \"%p\"[style=dashed, color=grey]\n", this, backedge);

+       }

 }
 }

diff --git a/predicate.h b/predicate.h
index dd1011495fad8d3bc2d848f04e195305435f15c6..732e39abd8b7644d5f5d9d37df1e9a133594b06e 100644 (file)
--- 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 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; }
        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; }
 
        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;
 
        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;
 
        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__ */
 };
 
 #endif /* __PREDICATE_H__ */