Miasm2
 All Classes Namespaces Files Functions Variables Typedefs Properties Macros
Public Member Functions | Public Attributes | Private Member Functions | Private Attributes | Static Private Attributes | List of all members
miasm2.analysis.depgraph.DependencyDict Class Reference
+ Inheritance diagram for miasm2.analysis.depgraph.DependencyDict:
+ Collaboration diagram for miasm2.analysis.depgraph.DependencyDict:

Public Member Functions

def __init__
 
def __eq__
 
def __cmp__
 
def is_head
 
def copy
 
def extend
 
def heads
 
def label
 
def history
 
def cache
 
def pending
 
def clean_modifiers_in_cache
 
def as_graph
 
def filter_used_nodes
 
def filter_unmodifier_loops
 

Public Attributes

 cache
 
 label
 

Private Member Functions

def _get_modifiers_in_cache
 
def _build_depgraph
 
def _non_modifier_in_loop
 

Private Attributes

 _label
 
 _history
 
 _pending
 
 _cache
 

Static Private Attributes

list __slots__ = ["_label", "_history", "_pending", "_cache"]
 

Detailed Description

Internal structure for the DependencyGraph algorithm

Definition at line 164 of file depgraph.py.

Constructor & Destructor Documentation

def miasm2.analysis.depgraph.DependencyDict.__init__ (   self,
  label,
  history 
) 
Create a DependencyDict
@label: asm_label, current IRblock label
@history: list of DependencyDict

Definition at line 169 of file depgraph.py.

169 
170  def __init__(self, label, history):
171  """Create a DependencyDict
172  @label: asm_label, current IRblock label
173  @history: list of DependencyDict
174  """
175  self._label = label
176  self._history = history
177  self._pending = set()
178 
179  # DepNode -> set(DepNode)
180  self._cache = CacheWrapper()

Member Function Documentation

def miasm2.analysis.depgraph.DependencyDict.__cmp__ (   self,
  depdict 
)

Definition at line 187 of file depgraph.py.

187 
188  def __cmp__(self, depdict):
189  if not isinstance(depdict, self.__class__):
190  raise ValueError("Compare error %s != %s" % (self.__class__,
191  depdict.__class__))
192  return cmp((self._label, self._cache, self._pending),
193  (depdict.label, depdict.cache, depdict.pending))

+ Here is the call graph for this function:

def miasm2.analysis.depgraph.DependencyDict.__eq__ (   self,
  depdict 
)

Definition at line 181 of file depgraph.py.

181 
182  def __eq__(self, depdict):
183  if not isinstance(depdict, self.__class__):
184  return False
185  return (self._label == depdict.label and
186  self.cache == depdict.cache)

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyDict._build_depgraph (   self,
  depnode 
)
private 
Recursively build the final list of DiGraph, and clean up unmodifier
nodes
@depnode: starting node

Definition at line 304 of file depgraph.py.

304 
305  def _build_depgraph(self, depnode):
306  """Recursively build the final list of DiGraph, and clean up unmodifier
307  nodes
308  @depnode: starting node
309  """
310 
311  if depnode not in self._cache or \
312  not self._cache[depnode]:
313  # There is no dependency
314  graph = DiGraph()
315  graph.add_node(depnode)
316  return graph
317 
318  # Recursion
319  dependencies = list(self._cache[depnode])
320 
321  graphs = []
322  for sub_depnode in dependencies:
323  graphs.append(self._build_depgraph(sub_depnode))
324 
325  # head(graphs[i]) == dependencies[i]
326  graph = DiGraph()
327  graph.add_node(depnode)
328  for head in dependencies:
329  graph.add_uniq_edge(head, depnode)
330 
331  for subgraphs in itertools.product(graphs):
332  for sourcegraph in subgraphs:
333  for node in sourcegraph.nodes():
334  graph.add_node(node)
335  for edge in sourcegraph.edges():
336  graph.add_uniq_edge(*edge)
337 
338  # Update the running queue
339  return graph

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyDict._get_modifiers_in_cache (   self,
  nodes_heads 
)
private 
Find modifier nodes in cache starting from @nodes_heads.
Returns new cache

Definition at line 251 of file depgraph.py.

251 
252  def _get_modifiers_in_cache(self, nodes_heads):
253  """Find modifier nodes in cache starting from @nodes_heads.
254  Returns new cache"""
255  # 'worklist_depnode' order is needed (depth first)
256  worklist_depnodes = list(nodes_heads)
257  # Temporary cache
258  cache = {}
259  # Partially resolved 'cache' elements
260  worklist = []
261 
262  # Build worklist and cache for non modifiers
263  while worklist_depnodes:
264  depnode = worklist_depnodes.pop()
265  # Resolve node dependencies
266  if depnode in cache:
267  # Depnode previously resolved
268  continue
269 
270  if depnode not in self._cache:
271  # Final node
272  if not depnode.modifier:
273  cache[depnode] = []
274  continue
275 
276  # Propagate to son
277  dependencies = self._cache[depnode]
278  for son in dependencies:
279  worklist_depnodes.append(son)
280  # Save partially resolved dependency
281  worklist.append((depnode, dependencies))
282 
283  # Convert worklist to cache
284  while worklist:
285  depnode, dependencies = worklist.pop()
286  parallels = []
287  for node in dependencies:
288  if node.modifier:
289  parallels.append([node])
290  else:
291  parallels.append(cache[node])
292  out = set()
293  for parallel in itertools.product(*[p for p in parallels if p]):
294  out.update(parallel)
295  cache[depnode] = out
296 
297  return cache

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyDict._non_modifier_in_loop (   self,
  depnode 
)
private 
Walk from @depnode until a node with the same nostep_repr is
encountered.
Returns a set of unmodifier nodes met in the path if no modifier was
found.
Returns set() if there exist a modifier node on the path.

Definition at line 429 of file depgraph.py.

429 
430  def _non_modifier_in_loop(self, depnode):
431  """
432  Walk from @depnode until a node with the same nostep_repr is
433  encountered.
434  Returns a set of unmodifier nodes met in the path if no modifier was
435  found.
436  Returns set() if there exist a modifier node on the path.
437  """
438  if not self.cache.has_key(depnode):
439  return set()
440  # Init
441  todo = set(self.cache[depnode])
442  unmodifier_nodes = []
443 
444  # Map
445  while todo:
446  node = todo.pop()
447  if node in unmodifier_nodes:
448  continue
449  if node.modifier:
450  return set()
451  unmodifier_nodes.append(node)
452  if not node in self._cache:
453  continue
454  if node.nostep_repr == depnode.nostep_repr:
455  unmodifier_nodes.append(node)
456  break
457 
458  for sub_node in self._cache[node]:
459  todo.add(sub_node)
460 
461  return unmodifier_nodes
462 

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyDict.as_graph (   self,
  starting_nodes 
) 
Return a DiGraph corresponding to computed dependencies, with
@starting_nodes as leafs
@starting_nodes: set of DependencyNode instance

Definition at line 340 of file depgraph.py.

340 
341  def as_graph(self, starting_nodes):
342  """Return a DiGraph corresponding to computed dependencies, with
343  @starting_nodes as leafs
344  @starting_nodes: set of DependencyNode instance
345  """
346 
347  # Build subgraph for each starting_node
348  subgraphs = []
349  for starting_node in starting_nodes:
350  subgraphs.append(self._build_depgraph(starting_node))
351 
352  # Merge subgraphs into a final DiGraph
353  graph = DiGraph()
354  for sourcegraph in subgraphs:
355  for node in sourcegraph.nodes():
356  graph.add_node(node)
357  for edge in sourcegraph.edges():
358  graph.add_uniq_edge(*edge)
359  return graph

+ Here is the call graph for this function:

def miasm2.analysis.depgraph.DependencyDict.cache (   self)

Definition at line 241 of file depgraph.py.

241 
242  def cache(self):
243  "Dictionnary of DependencyNode and their dependencies"
244  return self._cache
def miasm2.analysis.depgraph.DependencyDict.clean_modifiers_in_cache (   self,
  node_heads 
) 
Remove intermediary states (non modifier depnodes) in the internal
cache values

Definition at line 298 of file depgraph.py.

298 
299  def clean_modifiers_in_cache(self, node_heads):
300  """Remove intermediary states (non modifier depnodes) in the internal
301  cache values"""
302 
303  self._cache = CacheWrapper(self._get_modifiers_in_cache(node_heads))

+ Here is the call graph for this function:

def miasm2.analysis.depgraph.DependencyDict.copy (   self)

Definition at line 200 of file depgraph.py.

200 
201  def copy(self):
202  "Return a copy of itself"
203 
204  # Initialize
205  new_history = list(self.history)
206  depdict = DependencyDict(self.label, new_history)
207 
208  # Copy values
209  for key, values in self.cache.iteritems():
210  depdict.cache[key] = set(values)
211  depdict.pending.update(self.pending)
212 
213  return depdict

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyDict.extend (   self,
  label 
) 
Return a copy of itself, with itself in history and pending clean
@label: asm_label instance for the new DependencyDict's label

Definition at line 214 of file depgraph.py.

214 
215  def extend(self, label):
216  """Return a copy of itself, with itself in history and pending clean
217  @label: asm_label instance for the new DependencyDict's label
218  """
219  depdict = DependencyDict(label, list(self.history) + [self])
220  for key, values in self.cache.iteritems():
221  depdict.cache[key] = set(values)
222  return depdict

+ Here is the call graph for this function:

def miasm2.analysis.depgraph.DependencyDict.filter_unmodifier_loops (   self,
  implicit,
  irdst 
) 
Remove unmodifier node creating dependency loops over
pending elements in cache.
@implicit: boolean
@irdst: ExprId instance of IRDst register

Definition at line 385 of file depgraph.py.

385 
386  def filter_unmodifier_loops(self, implicit, irdst):
387  """
388  Remove unmodifier node creating dependency loops over
389  pending elements in cache.
390  @implicit: boolean
391  @irdst: ExprId instance of IRDst register
392  """
393 
394  previous_dict = None
395  # Get pending nodes of last time the label was handled
396  for hist_dict in reversed(self.history):
397  if hist_dict.label == self.label:
398  previous_dict = hist_dict
399  break
400 
401  if not previous_dict:
402  return
403 
404  nostep_pending = [node.nostep_repr for node in self.pending]
405 
406  to_remove = set()
407  for depnode in previous_dict.pending:
408  if (depnode.nostep_repr not in nostep_pending or
409  implicit and depnode.element == irdst):
410  continue
411 
412  to_remove.update(self._non_modifier_in_loop(depnode))
413 
414  # Replace unused keys by previous ones
415  for key in to_remove:
416  if depnode.nostep_repr == key.nostep_repr:
417  self._cache[depnode] = self._cache.get(key, set()).copy()
418  self.pending.discard(key)
419  self.pending.add(depnode)
420 
421  # Replace occurences of key to remove
422  for dependencies in self._cache.itervalues():
423  if key in dependencies:
424  dependencies.remove(key)
425  dependencies.add(depnode)
426 
427  if self._cache.has_key(key):
428  del self._cache[key]

+ Here is the call graph for this function:

def miasm2.analysis.depgraph.DependencyDict.filter_used_nodes (   self,
  node_heads 
) 
Keep only depnodes which are in the path of @node_heads in the
internal cache
@node_heads: set of DependencyNode instance

Definition at line 360 of file depgraph.py.

360 
361  def filter_used_nodes(self, node_heads):
362  """Keep only depnodes which are in the path of @node_heads in the
363  internal cache
364  @node_heads: set of DependencyNode instance
365  """
366  # Init
367  todo = set(node_heads)
368  used_nodes = set()
369 
370  # Map
371  while todo:
372  node = todo.pop()
373  if node in used_nodes:
374  continue
375  used_nodes.add(node)
376  if not node in self._cache:
377  continue
378  for sub_node in self._cache[node]:
379  todo.add(sub_node)
380 
381  # Remove unused elements
382  for key in list(self._cache.keys()):
383  if key not in used_nodes:
384  del self._cache[key]
def miasm2.analysis.depgraph.DependencyDict.heads (   self) 
Return an iterator on the list of heads as defined in 'is_head'

Definition at line 223 of file depgraph.py.

223 
224  def heads(self):
225  """Return an iterator on the list of heads as defined in 'is_head'"""
226  for key in self.cache:
227  if self.is_head(key):
228  yield key

+ Here is the call graph for this function:

def miasm2.analysis.depgraph.DependencyDict.history (   self) 
List of DependencyDict needed to reach the current DependencyDict
The first is the oldest

Definition at line 235 of file depgraph.py.

235 
236  def history(self):
237  """List of DependencyDict needed to reach the current DependencyDict
238  The first is the oldest"""
239  return self._history

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyDict.is_head (   self,
  depnode 
) 
Return True iff @depnode is at the head of the current block
@depnode: DependencyNode instance

Definition at line 194 of file depgraph.py.

194 
195  def is_head(self, depnode):
196  """Return True iff @depnode is at the head of the current block
197  @depnode: DependencyNode instance"""
198  return (self.label == depnode.label and
199  depnode.line_nb == 0)

+ Here is the caller graph for this function:

def miasm2.analysis.depgraph.DependencyDict.label (   self)

Definition at line 230 of file depgraph.py.

230 
231  def label(self):
232  "Label of the current block"
233  return self._label
def miasm2.analysis.depgraph.DependencyDict.pending (   self) 
Dictionnary of DependencyNode and their dependencies, waiting for
resolution

Definition at line 246 of file depgraph.py.

246 
247  def pending(self):
248  """Dictionnary of DependencyNode and their dependencies, waiting for
249  resolution"""
250  return self._pending

+ Here is the caller graph for this function:

Member Data Documentation

list miasm2.analysis.depgraph.DependencyDict.__slots__ = ["_label", "_history", "_pending", "_cache"]
staticprivate

Definition at line 167 of file depgraph.py.

miasm2.analysis.depgraph.DependencyDict._cache
private

Definition at line 179 of file depgraph.py.

miasm2.analysis.depgraph.DependencyDict._history
private

Definition at line 175 of file depgraph.py.

miasm2.analysis.depgraph.DependencyDict._label
private

Definition at line 174 of file depgraph.py.

miasm2.analysis.depgraph.DependencyDict._pending
private

Definition at line 176 of file depgraph.py.

miasm2.analysis.depgraph.DependencyDict.cache

Definition at line 185 of file depgraph.py.

miasm2.analysis.depgraph.DependencyDict.label

Definition at line 197 of file depgraph.py.

The documentation for this class was generated from the following file:
Generated by   doxygen 1.8.8