diff options
| author | serpilliere <serpilliere@users.noreply.github.com> | 2015-03-06 12:53:57 +0100 |
|---|---|---|
| committer | serpilliere <serpilliere@users.noreply.github.com> | 2015-03-06 12:53:57 +0100 |
| commit | 75e2d1688bfa735d7a6ee9d8839045c5cc9b7acf (patch) | |
| tree | a68a36a65212e87e27691d729a026a2e1b4d2e6f | |
| parent | f54b1c0296a07456c9ceb03fe013e6eca97a0e1e (diff) | |
| parent | ef71abfe1fe4fc235a4bb1008911f8ec496cecd2 (diff) | |
| download | miasm-75e2d1688bfa735d7a6ee9d8839045c5cc9b7acf.tar.gz miasm-75e2d1688bfa735d7a6ee9d8839045c5cc9b7acf.zip | |
Merge pull request #101 from commial/faster-depgraph
Faster depgraph
| -rw-r--r-- | miasm2/analysis/depgraph.py | 13 |
1 files changed, 10 insertions, 3 deletions
diff --git a/miasm2/analysis/depgraph.py b/miasm2/analysis/depgraph.py index 72d0176b..7ec9d7fa 100644 --- a/miasm2/analysis/depgraph.py +++ b/miasm2/analysis/depgraph.py @@ -1,5 +1,6 @@ """Provide dependency graph""" import itertools + import miasm2.expression.expression as m2_expr from miasm2.core.graph import DiGraph from miasm2.core.asmbloc import asm_label @@ -274,6 +275,8 @@ class DependencyDict(object): # Map while todo: node = todo.pop() + if node in used_nodes: + continue used_nodes.add(node) if not node in self._cache: continue @@ -492,7 +495,7 @@ class DependencyGraph(object): current_depdict.pending.update(depnodes) # Init the work list - done = [] + done = {} todo = [current_depdict] while todo: @@ -501,10 +504,14 @@ class DependencyGraph(object): # Update the dependencydict until fixed point is reached self._updateDependencyDict(depdict) + # Clean irrelevant path + depdict.filter_used_nodes(depnodes) + # Avoid infinite loops - if depdict in done: + label = depdict.label + if depdict in done.get(label, []): continue - done.append(depdict) + done.setdefault(label, []).append(depdict) # No more dependencies if len(depdict.pending) == 0: |