From 006159e2092bcf1222830a5702169f88d17eecdc Mon Sep 17 00:00:00 2001 From: Caroline Leman Date: Thu, 20 Aug 2015 10:46:15 +0200 Subject: Analysis/Depgraph: Remove duplicates treatments --- miasm2/analysis/depgraph.py | 32 +++++++++++++++++++++++++------- 1 file changed, 25 insertions(+), 7 deletions(-) (limited to 'miasm2/analysis') diff --git a/miasm2/analysis/depgraph.py b/miasm2/analysis/depgraph.py index 66c3f546..30638e18 100644 --- a/miasm2/analysis/depgraph.py +++ b/miasm2/analysis/depgraph.py @@ -394,6 +394,13 @@ class DependencyDict(object): self._cache[depnode] = self._cache.get(key, set()).copy() self.pending.discard(key) self.pending.add(depnode) + + # Replace occurence of key to remove + for dependencies in self._cache.values(): + if key in dependencies: + dependencies.remove(key) + dependencies.add(depnode) + if self._cache.has_key(key): del self._cache[key] @@ -613,7 +620,7 @@ class FollowExpr(object): self.element = element @staticmethod - def to_depnodes(follow_exprs, label, line, modifier, counter): + def to_depnodes(follow_exprs, label, line, modifier, step): """Build a set of FollowExpr(DependencyNode) from the @follow_exprs set of FollowExpr""" dependencies = set() @@ -622,7 +629,7 @@ class FollowExpr(object): DependencyNode(label, follow_expr.element, line, - next(counter), + step, modifier=modifier))) return dependencies @@ -662,6 +669,7 @@ class DependencyGraph(object): self._ira = ira self._implicit = implicit self._step_counter = itertools.count() + self._current_step = next(self._step_counter) # The IRA graph must be computed assert hasattr(self._ira, 'g') @@ -683,6 +691,16 @@ class DependencyGraph(object): "Iteration counter" return self._step_counter + @property + def current_step(self): + "Current value of iteration counter" + return self._current_step + + def inc_step(self): + "Increment and return the current step" + self._current_step = next(self._step_counter) + return self._current_step + @staticmethod def _follow_simp_expr(exprs): """Simplify expression so avoid tracking useless elements, @@ -788,8 +806,7 @@ class DependencyGraph(object): # Build output output = FollowExpr.to_depnodes(read, depnode.label, depnode.line_nb - 1, modifier, - self.step_counter) - + self.current_step) return output def _resolve_intrablock_dep(self, depdict): @@ -854,6 +871,7 @@ class DependencyGraph(object): # Update the dependencydict until fixed point is reached self._resolve_intrablock_dep(depdict) + self.inc_step() # Clean irrelevant path depdict.filter_unmodifier_loops(self._implicit, self._ira.IRDst) @@ -883,7 +901,7 @@ class DependencyGraph(object): # Implicit dependencies: IRDst will be link with heads implicit_depnode = DependencyNode(label, self._ira.IRDst, irb_len, - next(self.step_counter), + self.current_step, modifier=False) # Create links between DependencyDict @@ -891,7 +909,7 @@ class DependencyGraph(object): # Follow the head element in the parent new_depnode = DependencyNode(label, depnode_head.element, irb_len, - next(self.step_counter)) + self.current_step) # The new node has to be analysed new_depdict.cache[depnode_head] = set([new_depnode]) new_depdict.pending.add(new_depnode) @@ -924,7 +942,7 @@ class DependencyGraph(object): input_depnodes = set() for element in elements: input_depnodes.add(DependencyNode(label, element, line_nb, - next(self.step_counter))) + self.current_step)) # Compute final depdicts depdicts = self._compute_interblock_dep(input_depnodes, heads) -- cgit 1.4.1 From 2a58bb46e9b6a6e472299b07bb11c6b636ff1939 Mon Sep 17 00:00:00 2001 From: Caroline Leman Date: Fri, 21 Aug 2015 10:53:49 +0200 Subject: Analysis/Depgraph: Coding convention and cleanups --- miasm2/analysis/depgraph.py | 52 ++++++++++++++++++++++++++++----------------- test/analysis/depgraph.py | 3 +-- 2 files changed, 33 insertions(+), 22 deletions(-) (limited to 'miasm2/analysis') diff --git a/miasm2/analysis/depgraph.py b/miasm2/analysis/depgraph.py index 30638e18..bbe84f58 100644 --- a/miasm2/analysis/depgraph.py +++ b/miasm2/analysis/depgraph.py @@ -68,9 +68,10 @@ class DependencyNode(object): def __str__(self): """Returns a string representation of DependencyNode""" - return "<%s %s %s %s M:%s>" % (self.__class__.__name__, - self.label.name, self.element, - self.line_nb, self.modifier) + return "<%s %s %s %s M:%s S:%s>" % (self.__class__.__name__, + self.label.name, self.element, + self.line_nb, self.modifier, + self.step) def __repr__(self): """Returns a string representation of DependencyNode""" @@ -110,9 +111,8 @@ class DependencyNode(object): @modifier.setter def modifier(self, value): """Evaluating the current line involves a modification of tracked - dependencies""" - if not isinstance(value, bool): - raise ValueError("Modifier must be a boolean") + dependencies if @value. + @value: boolean""" self._modifier = value @@ -139,7 +139,7 @@ class CacheWrapper(IterableUserDict): afterward. """ if self._nostep_keys is None: - self._nostep_keys = set([key.nostep_repr for key in self.data]) + self._nostep_keys = set(key.nostep_repr for key in self.data) return self._nostep_keys @property @@ -153,7 +153,7 @@ class CacheWrapper(IterableUserDict): self._nostep_cache = {} for (node, values) in self.data.iteritems(): self._nostep_cache.setdefault(node.nostep_repr, set()).update( - set([val.nostep_repr for val in values])) + set(val.nostep_repr for val in values)) return self._nostep_cache @@ -245,8 +245,12 @@ class DependencyDict(object): def _get_modifiers_in_cache(self, depnode, force=False): """Recursively find nodes in the path of @depnode which are modifiers. - Update the internal cache - If @depnode is already managed (ie. in @depnode_queued), abort""" + Update the internal cache If @depnode is already managed (ie. in + @depnode_queued), abort + @depnode: DependencyNode + @force (optionnal): boolean, compute modifiers even if @depnode is a + modifier node. + """ # Base case if depnode not in self._cache: @@ -266,7 +270,7 @@ class DependencyDict(object): parallels.append(self._get_modifiers_in_cache(depnode)) if parallels: - for parallel in itertools.product(*[p for p in parallels if p]): + for parallel in itertools.product(*(p for p in parallels if p)): out.update(parallel) return out @@ -366,6 +370,8 @@ class DependencyDict(object): """ Remove unmodifier node creating dependency loops over pending elements in cache. + @implicit: boolean + @irdst: ExprId instance of IRDst register """ previous_dict = None @@ -388,15 +394,15 @@ class DependencyDict(object): to_remove.update(self._non_modifier_in_loop(depnode)) - # Remove unused elements + # Replace unused keys by previous ones for key in to_remove: if depnode.nostep_repr == key.nostep_repr: self._cache[depnode] = self._cache.get(key, set()).copy() self.pending.discard(key) self.pending.add(depnode) - # Replace occurence of key to remove - for dependencies in self._cache.values(): + # Replace occurences of key to remove + for dependencies in self._cache.itervalues(): if key in dependencies: dependencies.remove(key) dependencies.add(depnode) @@ -473,8 +479,8 @@ class DependencyResult(object): @property def unresolved(self): """Set of nodes whose dependencies weren't found""" - return set([node.nostep_repr for node in self._depdict.pending - if node.element != self._ira.IRDst]) + return set(node.nostep_repr for node in self._depdict.pending + if node.element != self._ira.IRDst) @property def relevant_nodes(self): @@ -491,7 +497,7 @@ class DependencyResult(object): The history order is preserved. """ # Get used labels - used_labels = set([depnode.label for depnode in self.relevant_nodes]) + used_labels = set(depnode.label for depnode in self.relevant_nodes) # Keep history order output = [] @@ -622,7 +628,13 @@ class FollowExpr(object): @staticmethod def to_depnodes(follow_exprs, label, line, modifier, step): """Build a set of FollowExpr(DependencyNode) from the @follow_exprs set - of FollowExpr""" + of FollowExpr + @follow_exprs: set of FollowExpr + @label: asm_label instance + @line: integer + @modifier: boolean + @step: integer + """ dependencies = set() for follow_expr in follow_exprs: dependencies.add(FollowExpr(follow_expr.follow, @@ -858,7 +870,7 @@ class DependencyGraph(object): """Create a DependencyDict from @depnodes, and propagate DependencyDicts through all blocs """ - # Create an DependencyDict which will only contain our depnodes + # Create a DependencyDict which will only contain our depnodes current_depdict = DependencyDict(list(depnodes)[0].label, []) current_depdict.pending.update(depnodes) @@ -972,7 +984,7 @@ class DependencyGraph(object): @heads: set of asm_label instances """ lead = list(depnodes)[0] - elements = set([depnode.element for depnode in depnodes]) + elements = set(depnode.element for depnode in depnodes) return self.get(lead.label, elements, lead.line_nb, heads) def get_from_end(self, label, elements, heads): diff --git a/test/analysis/depgraph.py b/test/analysis/depgraph.py index 00b17760..90f2962c 100644 --- a/test/analysis/depgraph.py +++ b/test/analysis/depgraph.py @@ -13,7 +13,6 @@ try: import z3 except ImportError: EMULATION=False - pass STEP_COUNTER = count() A = ExprId("a") @@ -116,7 +115,7 @@ class GraphTest(DiGraph): def node2str(self, node): if isinstance(node, asm_label): - if not node in self.ira.blocs: + if node not in self.ira.blocs: return str(node) else: return str(self.ira.blocs[node]) -- cgit 1.4.1