diff options
Diffstat (limited to 'miasm2')
| -rw-r--r-- | miasm2/analysis/depgraph.py | 6 | ||||
| -rw-r--r-- | miasm2/core/graph.py | 28 |
2 files changed, 31 insertions, 3 deletions
diff --git a/miasm2/analysis/depgraph.py b/miasm2/analysis/depgraph.py index aec159aa..b574e421 100644 --- a/miasm2/analysis/depgraph.py +++ b/miasm2/analysis/depgraph.py @@ -252,10 +252,10 @@ class DependencyResult(DependencyState): @property def has_loop(self): - """True if current dictionary has a loop""" + """True iff there is at least one data dependencies cycle (regarding + the associated depgraph)""" if self._has_loop is None: - self._has_loop = (len(self.relevant_labels) != - len(set(self.relevant_labels))) + self._has_loop = self.graph.has_loop() return self._has_loop def irblock_slice(self, irb): diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py index c98bf8a9..d97ca8be 100644 --- a/miasm2/core/graph.py +++ b/miasm2/core/graph.py @@ -478,6 +478,34 @@ class DiGraph(object): """Performs a depth first search on the reversed graph from @head""" return self._walk_generic_first(head, -1, self.predecessors_iter) + def has_loop(self): + """Return True if the graph contains at least a cycle""" + todo = list(self.nodes()) + # tested nodes + done = set() + # current DFS nodes + current = set() + while todo: + node = todo.pop() + if node in done: + continue + + if node in current: + # DFS branch end + for succ in self.successors_iter(node): + if succ in current: + return True + # A node cannot be in current AND in done + current.remove(node) + done.add(node) + else: + # Launch DFS from node + todo.append(node) + current.add(node) + todo += self.successors(node) + + return False + def compute_natural_loops(self, head): """ Computes all natural loops in the graph. |